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)