做項目時碰到特征的骨架提取，找了挺多相關資料，發現這篇博客講的最完整，而且通俗易懂，完美解決碰到的問題，特轉載如下，供更多的人學習。轉自：https://www.cnblogs.com/mikewolf2002/p/3327183.html

本章我們學習一下Hilditch算法的基本原理，從網上找資料的時候，竟然發現兩個有很大差別的算法描述，而且都叫Hilditch算法。不知道那一個才是正宗的，兩個算法實現的效果接近，第一種算法更好一些。

第一種算法描述參考paper和代碼：

Linear Skeletons from Square Cupboards

Speedup Method for Real-Time Thinning Algorithm

http://cis.k.hosei.ac.jp/~wakahara/Hilditch.c

第二種算法描述參考資料：

http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/azar/skeleton.html#algorithm

?

下面我們分別看一下這兩種算法描述：

一、第一種算法描述

假設當前被處理的像素為p0，我們使用下圖所示的8鄰域表示方式。

???? 我們處理的為二值圖像，背景為黑色，值為0，要細化的前景物體像素值為255。

???? 對于Hilditch算法來說，它并不是一個完全的并行算法，而是串行并行相結合。當前像素是否是能夠刪除的骨架點，不僅是由它周圍的8鄰域決定，而且和前面像素的判定結果有關。一個像素判定為可以刪除，我們并不直接刪除它，而是在目地圖像中設置像素值為GRAY=128,這個信息可能會影響之后其它像素的判定。

????? 當圖像一次掃描迭代完成后，我們把所有置為GRAY的像素設置為0，從而刪除它。

?算法的描述如下。

迭代掃描當前圖像

??? 對于當前像素點，掃描它的8鄰域，如果鄰域的像素值為255，則b[i]=1(i=0…8)，像素值為128(GRAY，表示該像素點在前面的循環中被標記為刪除)，b[i]=-1，如果像素值為0，則b[i]=0。

下面會根據b[i]的值進行6個條件判斷，如果條件滿足，則會標記該像素值為GRAY(128)。

1. b[0]=1，即當前像素必須為前景點。

2. 1-abs(b1) + 1 – abs(b3) + 1 – abs(b5) + 1 – abs(b7) >= 1，該條件表示當前像素為邊界點，即東西南北四個點至少有一個b[i]=0。

3. abs(b1)+…+abs(b8)>=2， 該條件表示不能刪除端點，即p0點周圍只有一個點為1或-1的情況。

4.? 統計b1到b8等于1的數量，該數量值必須大于1，該條件表示不能刪除端點。

5.? 連通性檢測，使用下面的公式：首先根據當前像素周圍3*3域的值，記錄d[9]數組，如果b[i]等于0，則d[i]=0， 否則d[i]=1，最后計算 d1-d1*d2*d3+d3-d3*d4*d5+d5-d5*d6*d7+d7-d7*d8*d1是否為1，為1則滿足連通性，可以刪除。

6.最后一個條件保證當輪廓是2個像素寬時，只刪除一邊。統計sum的值，當值為8時候，可以刪除。

sum = 0;?
for (i = 1; i <= 8; i++)?
{?
??? if (b[i] != -1)?
??? {?
??????? sum++;?
??? } else?
??? {?
??????? copy = b[i];?
??????? b[i] = 0;?
??????? if (func_nc8(b) == 1) sum++;?
??????? b[i] = copy;?
??? }

???? 當這6個條件都滿足時候，標記當前像素值為GRAY(128)，然后在判斷別的像素。當所有像素都掃描一遍后，完成一次迭代。

此時我們會把剛才標記為GARY的像素，都設置為0，真正的刪除它，如果上一次循環已經沒有標記刪除的像素，則退出迭代，否則進行下一次迭代。

算法代碼：

int gThin::func_nc8(int *b)//端點的連通性檢測 {int n_odd[4] = { 1, 3, 5, 7 }; //四鄰域int i, j, sum, d[10]; for (i = 0; i <= 9; i++) {j = i;if (i == 9) j = 1;if (abs(*(b + j)) == 1){d[i] = 1;} else {d[i] = 0;}}sum = 0;for (i = 0; i < 4; i++){j = n_odd[i];sum = sum + d[j] - d[j] * d[j + 1] * d[j + 2];}return (sum); }void gThin::cvHilditchThin(cv::Mat& src, cv::Mat& dst) {if(src.type()!=CV_8UC1){printf("只能處理二值或灰度圖像\n");return;}//非原地操作時候，copy src到dstif(dst.data!=src.data){src.copyTo(dst);}//8鄰域的偏移量int offset[9][2] = {{0,0},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1} };//四鄰域的偏移量int n_odd[4] = { 1, 3, 5, 7 }; int px, py; int b[9]; //3*3格子的灰度信息int condition[6]; //1-6個條件是否滿足int counter; //移去像素的數量int i, x, y, copy, sum; uchar* img;int width, height;width = dst.cols;height = dst.rows;img = dst.data;int step = dst.step ;do{counter = 0;for (y = 0; y < height; y++){for (x = 0; x < width; x++) {//前面標記為刪除的像素，我們置其相應鄰域值為-1for (i = 0; i < 9; i++) {b[i] = 0;px = x + offset[i][0];py = y + offset[i][1];if (px >= 0 && px < width && py >= 0 && py <height) {// printf("%d\n", img[py*step+px]);if (img[py*step+px] == WHITE){b[i] = 1;} else if (img[py*step+px] == GRAY) {b[i] = -1;}}}for (i = 0; i < 6; i++){condition[i] = 0;}//條件1，是前景點if (b[0] == 1) condition[0] = 1;//條件2，是邊界點sum = 0;for (i = 0; i < 4; i++) {sum = sum + 1 - abs(b[n_odd[i]]);}if (sum >= 1) condition[1] = 1;//條件3， 端點不能刪除sum = 0;for (i = 1; i <= 8; i++){sum = sum + abs(b[i]);}if (sum >= 2) condition[2] = 1;//條件4， 孤立點不能刪除sum = 0;for (i = 1; i <= 8; i++){if (b[i] == 1) sum++;}if (sum >= 1) condition[3] = 1;//條件5， 連通性檢測if (func_nc8(b) == 1) condition[4] = 1;//條件6，寬度為2的骨架只能刪除1邊sum = 0;for (i = 1; i <= 8; i++){if (b[i] != -1) {sum++;} else {copy = b[i];b[i] = 0;if (func_nc8(b) == 1) sum++;b[i] = copy;}}if (sum == 8) condition[5] = 1;if (condition[0] && condition[1] && condition[2] &&condition[3] && condition[4] && condition[5]){img[y*step+x] = GRAY; //可以刪除，置位GRAY，GRAY是刪除標記，但該信息對后面像素的判斷有用counter++;//printf("----------------------------------------------\n");//PrintMat(dst);}} }if (counter != 0){for (y = 0; y < height; y++){for (x = 0; x < width; x++){if (img[y*step+x] == GRAY)img[y*step+x] = BLACK;}}}}while (counter != 0);}

?

二、第二種算法描述

?????? 第二種算法描述和Zhang的并行算法很相似，特別是前2個條件一模一樣，不同的是3，4兩個條件，還有就是該描述算法并沒有像zhang算法那樣，把一次迭代分成2個階段。

此時我們使用的8鄰域標記為：

下面看下它的算法描述：

復制目地圖像到臨時圖像，對臨時圖像進行一次掃描，對于不為0的點，如果滿足以下四個條件，則在目地圖像中刪除該點(就是設置該像素為0)

a.?2<= p2+p3+p4+p5+p6+p7+p8+p9<=6

??? 大于等于2會保證p1點不是端點或孤立點，因為刪除端點和孤立點是不合理的，小于等于6保證p1點是一個邊界點，而不是一個內部點。等于0時候，周圍沒有等于1的像素，所以p1為孤立點，等于1的時候，周圍只有1個灰度等于1的像素，所以是端點（注：端點是周圍有且只能有1個值為1的像素)。

b. p2->p9的排列順序中，01模式的數量為1，比如下面的圖中，有p2p3 => 01, p6p7=>01,所以該像素01模式的數量為2。

? 之所以要01模式數量為1，是要保證刪除當前像素點后的連通性。比如下面的圖中，01模式數量大于1，如果刪除當前點p1，則連通性不能保證。

?

c. p2.p4.p8 = 0?or?A(p2)!=1，A(p2)表示p2周圍8鄰域的01模式和。這個條件保證2個像素寬的垂直條不完全被腐蝕掉。

d.p2.p4.p6 = 0?or?A(p4)!=1，A(p4)表示p4周圍8鄰域的01模式和。這個條件保證2個像素寬的水平條不完全被腐蝕掉。

算法代碼：

void gThin::cvHilditchThin1(cv::Mat& src, cv::Mat& dst) {//http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/azar/skeleton.html#algorithm//算法有問題，得不到想要的效果if(src.type()!=CV_8UC1){printf("只能處理二值或灰度圖像\n");return;}//非原地操作時候，copy src到dstif(dst.data!=src.data){src.copyTo(dst);}int i, j;int width, height;//之所以減2，是方便處理8鄰域，防止越界width = src.cols -2;height = src.rows -2;int step = src.step;int p2,p3,p4,p5,p6,p7,p8,p9;uchar* img;bool ifEnd;int A1;cv::Mat tmpimg;while(1){dst.copyTo(tmpimg);ifEnd = false;img = tmpimg.data+step;for(i = 2; i < height; i++){img += step;for(j =2; j<width; j++){uchar* p = img + j;A1 = 0;if( p[0] > 0){if(p[-step]==0&&p[-step+1]>0) //p2,p3 01模式{A1++;}if(p[-step+1]==0&&p[1]>0) //p3,p4 01模式{A1++;}if(p[1]==0&&p[step+1]>0) //p4,p5 01模式{A1++;}if(p[step+1]==0&&p[step]>0) //p5,p6 01模式{A1++;}if(p[step]==0&&p[step-1]>0) //p6,p7 01模式{A1++;}if(p[step-1]==0&&p[-1]>0) //p7,p8 01模式{A1++;}if(p[-1]==0&&p[-step-1]>0) //p8,p9 01模式{A1++;}if(p[-step-1]==0&&p[-step]>0) //p9,p2 01模式{A1++;}p2 = p[-step]>0?1:0;p3 = p[-step+1]>0?1:0;p4 = p[1]>0?1:0;p5 = p[step+1]>0?1:0;p6 = p[step]>0?1:0;p7 = p[step-1]>0?1:0;p8 = p[-1]>0?1:0;p9 = p[-step-1]>0?1:0;//計算AP2,AP4int A2, A4;A2 = 0;//if(p[-step]>0){if(p[-2*step]==0&&p[-2*step+1]>0) A2++;if(p[-2*step+1]==0&&p[-step+1]>0) A2++;if(p[-step+1]==0&&p[1]>0) A2++;if(p[1]==0&&p[0]>0) A2++;if(p[0]==0&&p[-1]>0) A2++;if(p[-1]==0&&p[-step-1]>0) A2++;if(p[-step-1]==0&&p[-2*step-1]>0) A2++;if(p[-2*step-1]==0&&p[-2*step]>0) A2++;}A4 = 0;//if(p[1]>0){if(p[-step+1]==0&&p[-step+2]>0) A4++;if(p[-step+2]==0&&p[2]>0) A4++;if(p[2]==0&&p[step+2]>0) A4++;if(p[step+2]==0&&p[step+1]>0) A4++;if(p[step+1]==0&&p[step]>0) A4++;if(p[step]==0&&p[0]>0) A4++;if(p[0]==0&&p[-step]>0) A4++;if(p[-step]==0&&p[-step+1]>0) A4++;}//printf("p2=%d p3=%d p4=%d p5=%d p6=%d p7=%d p8=%d p9=%d\n", p2, p3, p4, p5, p6,p7, p8, p9);//printf("A1=%d A2=%d A4=%d\n", A1, A2, A4);if((p2+p3+p4+p5+p6+p7+p8+p9)>1 && (p2+p3+p4+p5+p6+p7+p8+p9)<7 && A1==1){if(((p2==0||p4==0||p8==0)||A2!=1)&&((p2==0||p4==0||p6==0)||A4!=1)) {dst.at<uchar>(i,j) = 0; //滿足刪除條件，設置當前像素為0ifEnd = true;//printf("\n");//PrintMat(dst);}}}}}//printf("\n");//PrintMat(dst);//PrintMat(dst);//已經沒有可以細化的像素了，則退出迭代if(!ifEnd) break;} }

本人使用cvHilditchThin1函數的實驗結果如下：

? ? ? ? ? ? ? ? ? ? 細化前：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 細化后：

? ? ? ? ? ? ? ? ? ? ? ? ??

總結

以上是生活随笔為你收集整理的【opencv】经典的细化提取骨架理论及源代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。