Hilditch 细化算法的C#实现

Hilditch 细化算法是经典的二值图像细化算法，然而，在网上却很难找到一个详细、正确的介绍和实现。可以找到一辆个 Hilditch 算法的C实现，但缺乏注释，代码可读性也很差。在期刊网上找到几篇论文，提及了Hilditch 算法，结果一篇说的罗哩罗嗦根本看不懂，另一篇说的说的易懂，却是错误的！拿来主义是行不通了，于是只好结合着这几个论文和代码，从头写 Hilditch 细化算法。

假设像素p的3×3邻域结构为：

<a href="http://images.cnblogs.com/cnblogs_com/xiaotie/WindowsLiveWriter/HilditchC_2CEF/image_10.png"></a>

Hilditch 细化算法的步骤为：

对图像从左向右从上向下迭代每个像素，是为一个迭代周期。在每个迭代周期中，对于每一个像素p，如果它同时满足6个条件，则标记它。在当前迭代周期结束时，则把所有标记的像素的值设为背景值。如果某次迭代周期中不存在标记点（即满足6个条件的像素），则算法结束。假设背景值为0，前景值为1，则：

6个条件为：

（I）：p 为1，即p不是背景；

（2）：x1,x3,x5,x7不全部为1（否则把p标记删除，图像空心了）；

（3）：x1~x8 中，至少有2个为1（若只有1个为1，则是线段的端点。若没有为1的，则为孤立点）；

（4）：p的8连通联结数为1；

联结数指在像素p的3*3邻域中，和p连接的图形分量的个数：

<a href="http://images.cnblogs.com/cnblogs_com/xiaotie/WindowsLiveWriter/HilditchC_2CEF/image_8.png"></a>

上图中，左图的4连通联结数是2，8连通联结数是1，而右图的4联通联结数和8联通联结数都是2。

4连通联结数计算公式是：

<a href="http://images.cnblogs.com/cnblogs_com/xiaotie/WindowsLiveWriter/HilditchC_2CEF/image_12.png"></a>

8连通联结数计算公式是：

至于公式怎么来的就不管了，直接用就行了。

（5）假设x3已经标记删除，那么当x3为0时，p的8联通联结数为1；

（6）假设x5已经标记删除，那么当x5为0时，p的8联通联结数为1。

======

在程序中，我使用的是这样的邻域编码：

<a href="http://images.cnblogs.com/cnblogs_com/xiaotie/WindowsLiveWriter/HilditchC_2CEF/image_18.png"></a>

/// &lt;summary&gt;  /// 计算八联结的联结数，计算公式为：  ///     (p6 - p6*p7*p0) + sigma(pk - pk*p(k+1)*p(k+2)), k = {0,2,4)  /// &lt;/summary&gt;  /// &lt;param name="list"&gt;&lt;/param&gt;  /// &lt;returns&gt;&lt;/returns&gt;  private unsafe Int32 DetectConnectivity(Int32* list)  {      Int32 count = list[6] - list[6] * list[7] * list[0];      count += list[0] - list[0] * list[1] * list[2];      count += list[2] - list[2] * list[3] * list[4];      count += list[4] - list[4] * list[5] * list[6];      return count;  } private unsafe void FillNeighbors(Byte* p, Int32* list, Int32 width, Byte foreground = 255)      // list 存储的是补集，即前景点为0，背景点为1，以方便联结数的计算     list[0] = p[1] == foreground ? 0 : 1;      list[1] = p[1 - width] == foreground ? 0 : 1;      list[2] = p[-width] == foreground ? 0 : 1;      list[3] = p[-1 - width] == foreground ? 0 : 1;      list[4] = p[-1] == foreground ? 0 : 1;      list[5] = p[-1 + width] == foreground ? 0 : 1;      list[6] = p[width] == foreground ? 0 : 1;      list[7] = p[1 + width] == foreground ? 0 : 1;  /// 使用 hilditch 算法进行细化  public unsafe void Thinning(Byte foreground = 255)      Byte* start = this.Start;      Int32 width = this.Width;      Int32 height = this.Height;      Int32* list = stackalloc Int32[8];      Byte background = (Byte)(255 - foreground);      Int32 length = this.Length;     using (ImageU8 mask = new ImageU8(this.Width, this.Height))      {          mask.Fill(0);         Boolean loop = true;          while (loop == true)          {              loop = false;              for (Int32 r = 1; r &lt; height - 1; r++)              {                  for (Int32 c = 1; c &lt; width - 1; c++)                  {                      Byte* p = start + r * width + c;                     // 条件1：p 必须是前景点                      if (*p != foreground) continue;                     //  p3  p2  p1                      //  p4  p   p0                      //  p5  p6  p7                      // list 存储的是补集，即前景点为0，背景点为1，以方便联结数的计算                      FillNeighbors(p, list, width, foreground);                     // 条件2：p0,p2,p4,p6 不皆为前景点                      if (list[0] == 0 &amp;&amp; list[2] == 0 &amp;&amp; list[4] == 0 &amp;&amp; list[6] == 0)                          continue;                     // 条件3: p0~p7至少两个是前景点                      Int32 count = 0;                      for (int i = 0; i &lt; 8; i++)                      {                          count += list[i];                      }                     if (count &gt; 6) continue;                     // 条件4：联结数等于1                      if (DetectConnectivity(list) != 1) continue;                     // 条件5: 假设p2已标记删除，则令p2为背景，不改变p的联结数                      if (mask[r - 1, c] == 1)                          list[2] = 1;                          if (DetectConnectivity(list) != 1)                              continue;                          list[2] = 0;                      // 条件6: 假设p4已标记删除，则令p4为背景，不改变p的联结数                      if (mask[r, c - 1] == 1)                          list[4] = 1;                      }                      mask[r, c] = 1; // 标记删除                      loop = true;                  }              }             for (int i = 0; i &lt; length; i++)                  if (mask[i] == 1)                      this[i] = background;              }          }      } 

参考文献：

崔凤奎,王晓强,张丰收,等. 二值图像细化算法的比较与改进. 洛阳工学院学报. 1997. 18(4)

注：二值图像细化算法的比较与改进 这篇文章中所述Hilditch算法是错误的：

错误1：Pk(0≤k ≤7)中至少有一个目标像素为1; =&gt; Pk(0≤k ≤7)中至少有两个目标像素为1； 错误2：P2=1或Nc2=1;Nc2为假定P2=0时P的联结数; =&gt; P2被标记删除且Nc2=1;Nc2为假定P2=0时P的联结数; 错误3：P4=1或Nc4=1;Nc4为假定P4=0时P的联结数; =&gt; P4被标记删除且Nc4=1;Nc4为假定P4=0时P的联结数。

另外几篇文章就不提了，以俺的汉语水平，根本看不懂。

本文转自xiaotie博客园博客，原文链接http://www.cnblogs.com/xiaotie/archive/2010/08/12/1797760.html如需转载请自行联系原作者

xiaotie 集异璧实验室(GEBLAB)