Rocky的部落格

Hilditch 細化算法是經典的二值圖像細化算法，然而，在網上卻很難找到一個詳細、正確的介紹和實現。可以找到一輛個 Hilditch 算法的C實現，但缺乏注釋，代碼可讀性也很差。在期刊網上找到幾篇論文，提及了Hilditch 算法，結果一篇說的羅哩羅嗦根本看不懂，另一篇說的說的易懂，卻是錯誤的！拿來主義是行不通了，於是只好結合著這幾個論文和代碼，從頭寫 Hilditch 細化算法。

假設像素p的3×3鄰域結構為：

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連接的圖形分量的個數：

上圖中，左圖的4連通聯結數是2，8連通聯結數是1，而右圖的4聯通聯結數和8聯通聯結數都是2。

4連通聯結數計算公式是：

8連通聯結數計算公式是：

其中，

至於公式怎麼來的就不管了，直接用就行了。

（5）假設x3已經標記刪除，那麼當x3為0時，p的8聯通聯結數為1；

（6）假設x5已經標記刪除，那麼當x5為0時，p的8聯通聯結數為1。

代碼如下：

======

在程序中，我使用的是這樣的鄰域編碼：

為了方便計算聯結數，以0作為前景，1作為背景。程序如下（完整程序見：http://smartimage.googlecode.com/svn/trunk/src/Orc.SmartImage.Common/UnmanagedImage/Ima

[cpp] view plain copy

 

1. ///    
2. /// 計算八聯結的聯結數，計算公式為：   
3. ///     (p6 - p6*p7*p0) + sigma(pk - pk*p(k+1)*p(k+2)), k = {0,2,4)   
4. ///    
5. ///    
6. ///    
7. private unsafe Int32 DetectConnectivity(Int32* list)   
8. {   
9.     Int32 count = list[6] - list[6] * list[7] * list[0];   
10.     count += list[0] - list[0] * list[1] * list[2];   
11.     count += list[2] - list[2] * list[3] * list[4];   
12.     count += list[4] - list[4] * list[5] * list[6];   
13.     return count;   
14. }  
15.   
16. private unsafe void FillNeighbors(Byte* p, Int32* list, Int32 width, Byte foreground = 255)   
17. {   
18.     // list 存儲的是補集，即前景點為0，背景點為1，以方便聯結數的計算  
19.   
20.     list[0] = p[1] == foreground ? 0 : 1;   
21.     list[1] = p[1 - width] == foreground ? 0 : 1;   
22.     list[2] = p[-width] == foreground ? 0 : 1;   
23.     list[3] = p[-1 - width] == foreground ? 0 : 1;   
24.     list[4] = p[-1] == foreground ? 0 : 1;   
25.     list[5] = p[-1 + width] == foreground ? 0 : 1;   
26.     list[6] = p[width] == foreground ? 0 : 1;   
27.     list[7] = p[1 + width] == foreground ? 0 : 1;   
28. }  
29.   
30. ///    
31. /// 使用 hilditch 算法進行細化   
32. ///    
33. public unsafe void Thinning(Byte foreground = 255)   
34. {   
35.     Byte* start = this.Start;   
36.     Int32 width = this.Width;   
37.     Int32 height = this.Height;   
38.     Int32* list = stackalloc Int32[8];   
39.     Byte background = (Byte)(255 - foreground);   
40.     Int32 length = this.Length;  
41.   
42.     using (ImageU8 mask = new ImageU8(this.Width, this.Height))   
43.     {   
44.         mask.Fill(0);  
45.   
46.         Boolean loop = true;   
47.         while (loop == true)   
48.         {   
49.             loop = false;   
50.             for (Int32 r = 1; r < height - 1; r++)   
51.             {   
52.                 for (Int32 c = 1; c < width - 1; c++)   
53.                 {   
54.                     Byte* p = start + r * width + c;  
55.   
56.                     // 條件1：p 必須是前景點   
57.                     if (*p != foreground) continue;  
58.   
59.                     //  p3  p2  p1   
60.                     //  p4  p   p0   
61.                     //  p5  p6  p7   
62.                     // list 存儲的是補集，即前景點為0，背景點為1，以方便聯結數的計算   
63.                     FillNeighbors(p, list, width, foreground);  
64.   
65.                     // 條件2：p0,p2,p4,p6 不皆為前景點   
66.                     if (list[0] == 0 && list[2] == 0 && list[4] == 0 && list[6] == 0)   
67.                         continue;  
68.   
69.                     // 條件3: p0~p7至少兩個是前景點   
70.                     Int32 count = 0;   
71.                     for (int i = 0; i < 8; i++)   
72.                     {   
73.                         count += list[i];   
74.                     }  
75.   
76.                     if (count > 6) continue;  
77.   
78.                     // 條件4：聯結數等於1   
79.                     if (DetectConnectivity(list) != 1) continue;  
80.   
81.                     // 條件5: 假設p2已標記刪除，則令p2為背景，不改變p的聯結數   
82.                     if (mask[r - 1, c] == 1)   
83.                     {   
84.                         list[2] = 1;   
85.                         if (DetectConnectivity(list) != 1)   
86.                             continue;   
87.                         list[2] = 0;   
88.                     }  
89.   
90.                     // 條件6: 假設p4已標記刪除，則令p4為背景，不改變p的聯結數   
91.                     if (mask[r, c - 1] == 1)   
92.                     {   
93.                         list[4] = 1;   
94.                         if (DetectConnectivity(list) != 1)   
95.                             continue;   
96.                     }   
97.                     mask[r, c] = 1; // 標記刪除   
98.                     loop = true;   
99.                 }   
100.             }  
101.   
102.             for (int i = 0; i < length; i++)   
103.             {   
104.                 if (mask[i] == 1)   
105.                 {   
106.                     this[i] = background;   
107.                 }   
108.             }   
109.         }   
110.     }   
111. }  
112.   
113. ======  
114.   
115.   
116.    
117.   
118.    
119.   
120. 我的代碼如下：  
121.   
122.    
123.   
124. void HilditchThinning(int w,int h,BYTE *imgBuf)< xmlnamespace prefix ="o" ns ="urn:schemas-microsoft-com:office:office" />  
125. {  
126.     //           p3  p2  p1  
127.     // 8近鄰     p4  p   p0  
128.     //           p5  p6  p7  
129.     int neighbor[8];   
130.     BYTE *mask=new BYTE[w*h];  
131.     memset(mask,0,w*h);  
132.    
133.     BOOL loop=TRUE;  
134.     int x,y,k,index;  
135.    
136.     while(loop)  
137.     {  
138.        loop=FALSE;  
139.        loopNum++;  
140.    
141.        for(y=0;y<<span style="line-height: 28px; color: rgb(1, 0, 1);">h;y++)  
142.        {  
143.            for(x=0;x<<span style="line-height: 28px; color: rgb(1, 0, 1);">w;x++)  
144.            {  
145.               index=y*w+x; ;  
146.    
147.               //條件1：p必須是前景點  
148.               if(imgBuf[index]==0 ) continue;  
149.    
150.               neighbor[0]=x+1<<span style="line-height: 28px; color: rgb(1, 0, 1);">w ? imgBuf[y*w+x+1] : 0;  
151.               neighbor[1]=y-1>0&&x+1<<span style="line-height: 28px; color: rgb(1, 0, 1);">w ? imgBuf[(y-1)*w+x+1] : 0;  
152.               neighbor[2]=y-1>0 ? imgBuf[(y-1)*w+x] : 0;  
153.               neighbor[3]=y-1>0&&x-1<0 ? imgBuf[(y-1)*w+x-1] : 0;  
154.               neighbor[4]=x-1>0 ? imgBuf[y*w+x-1] : 0;  
155.               neighbor[5]=x-1>0&&y+1<<span style="line-height: 28px; color: rgb(1, 0, 1);">h ? imgBuf[(y+1)*w+x-1] : 0;  
156.               neighbor[6]=y+1<<span style="line-height: 28px; color: rgb(1, 0, 1);">h ? imgBuf[(y+1)*w+x] : 0;  
157.               neighbor[7]=y+1<<span style="line-height: 28px; color: rgb(1, 0, 1);">h&&x+1<<span style="line-height: 28px; color: rgb(1, 0, 1);">w ? imgBuf[(y+1)*w+x+1] : 0;  
158.    
159.               //條件2：p0,p2,p4,p6不全為前景色（否則把點p刪了，圖像空心）  
160.               if(neighbor[0]&&neighbor[2]&&neighbor[4]&&neighbor[6])  
161.                   continue;  
162.    
163.               //條件3：p0~p7中，至少有個為前景色  
164.               //（若只有一個為，則為端點，若沒有為的，則為孤立點）  
165.               int count=0;  
166.               for(int i=0;i<8;i++)  
167.               {  
168.                   if(neighbor[i]==255)  
169.                      count++;  
170.               }  
171.               if(count<2)   
172.               {  
173.                   continue;  
174.               }  
175.    
176.               //條件4：p的八近鄰連接數必須為1  
177.               if(Get8Connectivity(neighbor)!=1) continue;  
178.    
179.               //條件5：若p2已經被標記刪除，則當p2為背景色時，P的連接數仍需為1  
180.               k=(y-1)*w+x;  
181.               if(y-1>0 && mask[k]==1)  
182.               {              
183.                   imgBuf[k]=0;  
184.                   if(Get8Connectivity(neighbor)!=1) continue;  
185.                   imgBuf[k]=1;  
186.               }  
187.    
188.               //條件6：若p4已經被標記刪除，則當p4為背景色時，P的連接數仍需為1  
189.               k=y*w+x-1;  
190.               if(x-1>0 && mask[k]==1)  
191.               {              
192.                   imgBuf[k]=0;  
193.                   if(Get8Connectivity(neighbor)!=1) continue;  
194.                   imgBuf[k]=1;  
195.               }  
196.    
197.               //標記刪除  
198.               mask[w*y+x]=1;     
199.               loop=TRUE;  
200.            }  
201.        }  
202.    
203.    
204.        //將標記刪除的點置為背景色  
205.        for(y=0;y<<span style="line-height: 28px; color: rgb(1, 0, 1);">h;y++)  
206.        {  
207.            for(x=0;x<<span style="line-height: 28px; color: rgb(1, 0, 1);">w;x++)  
208.            {  
209.               k=y*w+x;  
210.               if(mask[k]==1) imgBuf[k]=0;  
211.            }  
212.        }    
213.    
214.    
215.     }  
216.      
217.    
218. }  
219. //                                  p3  p2  p1  
220. //*************計算近鄰的連接數     p4  p   p0  
221. //                                  p5  p6  p7  
222. int Get8Connectivity(int* neighbor)  
223. {    
224.    
225.     //計算補集x^=1-x;  
226.     for(int i=0;i<8;i++)  
227.     {  
228.        neighbor[i]=neighbor[i]==0?1:0;  
229.     }    
230.      
231.     int count= neighbor[0]-(neighbor[0]&neighbor[1]&neighbor[2]);  
232.     count+= neighbor[2]-(neighbor[2]&neighbor[3]&neighbor[4]);  
233.     count+= neighbor[4]-(neighbor[4]&neighbor[5]&neighbor[6]);  
234.     count+= neighbor[6]-(neighbor[6]&neighbor[7]&neighbor[0]);  
235.    
236.     return count;  
237. }  
238.    
239. 這個細化算法，細化後會產生毛刺