close

圖像細化（Image Thinning），一般指二值圖像的骨架化（Image Skeletonization） 的一種操作運算。

         所謂的細化就是經過一層層的剝離，從原來的圖中去掉一些點，但仍要保持原來的形狀，直到得到圖像的骨架。骨架，可以理解為圖象的中軸。

    好的細化算法一定要滿足：

  • 收斂性；
  • 保證細化後細線的連通性
  • 保持原圖的基本形狀
  • 減少筆畫相交處的畸變
  • 細化結果是原圖像的中心線
  • 細化的快速性和迭代次數少

 

 

依據是否使用迭代運算可以分為兩類：

 

  • 非迭代算法
    • 一次即產生骨架，如基於距離變換的方法。游程長度編碼細化等。
  • 迭代算法

即重復刪除圖像邊緣滿足一定條件的像素，最終得到單像素寬帶骨架。

迭代方法依據其檢查像素的方法又可以再分成

  • 串行算法

是否刪除像素在每次迭代的執行中是固定順序的，它不僅取決於前次迭代的結果，也取決於本次迭代中已處理過像素點分布情況.

  • 並行算法

像素點刪除與否與像素值圖像中的順序無關，僅取決於前次迭代的結果

 

細化算法:

 

  • Burning Algorithm

使用迭代的方法去除圖像的邊界, 可使用掃描線法來獲取邊界

 

 

  • Zhang並行快速細化算法

模板:

p3 p2 p9

p4 p1 p8

p5 p6 p7

 

 

   第一步，（其中p1為前景點，如果以下四個條件同時滿足，則刪除p1，即令p1=0）

1. 2<=N(p1)<=6                    // 中心為黑點

2. Z0(p1)=1                // Nz為八鄰域中黑點的數目

3. p2*p8*p6=0           // 避免圖像被打斷( 其反條件時不可刪)

4. p4*p8*p6=0 

 

其中，Z0(p1)是以p2,p3,...p8,p9為序時，這些點的值從0->1變化的次數

          N(p1)是p1的非0鄰近點的個數

 

被判定為刪除的點暫不刪除，但要加以記錄。

等所有邊界點都被判斷完後，再一起將所有標記了的點刪除，接下來進入第二階段的刪除步驟。

 

   第二步，按照如下條件進行第二階段的刪除，條件為

1. 2<=N(p1)<=6                       // 中心為黑點

2.  Z0(p1)=1                  // Nz為八鄰域中黑點的數目

3. p2*p4*p6=0                // 避免圖像被打斷( 其反條件時不可刪)

4. p2*p4*p8=0  

同第一步一樣，判定要刪除的點只是加以記錄而暫不刪除，等待最後同時刪除

 

對一副圖像反復執行第一步與第二步的算法步驟，知道都沒有可刪除的點為止

 

我的zhang細化代碼如下：

 

[csharp] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. //                                        p3  p2  p1  
  2. //**********使用zhang並行快速算法進行細化 p4  p   p0  
  3. //                                        p5  p6  p7  
  4. void ZhangThinning(int w,int h,BYTE *imgBuf)  
  5. {  
  6.     int neighbor[8];  
  7.    
  8.     BYTE *mark=new BYTE[w*h];  
  9.     memset(mark,0,w*h);  
  10.    
  11.     BOOL loop=TRUE;  
  12.     int x,y,k;  
  13.     int markNum=0;  
  14.    
  15.     while(loop)  
  16.     {  
  17.        loop=FALSE;  
  18.    
  19.        //第一步  
  20.        markNum=0;  
  21.        for(y=1;y<<span style="line-height: 28px; color: rgb(1, 0, 1);">h-1;y++)  
  22.        {  
  23.            for(x=1;x<<span style="line-height: 28px; color: rgb(1, 0, 1);">w-1;x++)  
  24.            {  
  25.               //條件1：p必須是前景點  
  26.               if(imgBuf[y*w+x]==0 ) continue;  
  27.    
  28.               neighbor[0]= imgBuf[y*w+x+1] ;  
  29.               neighbor[1]= imgBuf[(y-1)*w+x+1];  
  30.               neighbor[2]= imgBuf[(y-1)*w+x];  
  31.               neighbor[3]= imgBuf[(y-1)*w+x-1];  
  32.               neighbor[4]= imgBuf[y*w+x-1];  
  33.               neighbor[5]= imgBuf[(y+1)*w+x-1];  
  34.               neighbor[6]= imgBuf[(y+1)*w+x];  
  35.               neighbor[7]= imgBuf[(y+1)*w+x+1];  
  36.    
  37.               //條件2：2<=N(p）<=6  
  38.               int np=(neighbor[0]+neighbor[1]+neighbor[2]+neighbor[3]+neighbor[4]+neighbor[5]+neighbor[6]+neighbor[7])/255;  
  39.               if(np<2 || np>6) continue;  
  40.    
  41.               //條件3：S(p）=1  
  42.               int sp=0;  
  43.               for(int i=1;i<8;i++)  
  44.               {  
  45.                   if(neighbor[i]-neighbor[i-1]==255)  
  46.                      sp++;  
  47.               }  
  48.               if(neighbor[0]-neighbor[7]==255)  
  49.                   sp++;              
  50.               if(sp!=1) continue;  
  51.    
  52.               //條件4：p2*p0*p6=0  
  53.               if(neighbor[2]&neighbor[0]&neighbor[6]!=0)  
  54.                   continue;  
  55.                 //條件5：p0*p6*p4=0  
  56.               if(neighbor[0]&neighbor[6]&neighbor[4]!=0)  
  57.                   continue;  
  58.    
  59.    
  60.               //標記刪除  
  61.               mark[w*y+x]=1;     
  62.               markNum++;  
  63.               loop=TRUE;  
  64.            }  
  65.        }  
  66.    
  67.        //將標記刪除的點置為背景色  
  68.        if(markNum>0)  
  69.        {  
  70.            for(y=0;y<<span style="line-height: 28px; color: rgb(1, 0, 1);">h;y++)  
  71.            {  
  72.               for(x=0;x<<span style="line-height: 28px; color: rgb(1, 0, 1);">w;x++)  
  73.               {  
  74.                   k=y*w+x;  
  75.                   if(mark[k]==1)  
  76.                   {  
  77.                      imgBuf[k]=0;  
  78.                   }  
  79.               }  
  80.            }  
  81.        }  
  82.         
  83.    
  84.        //第二步  
  85.         markNum=0;  
  86.        for(y=1;y<<span style="line-height: 28px; color: rgb(1, 0, 1);">h-1;y++)  
  87.        {  
  88.            for(x=1;x<<span style="line-height: 28px; color: rgb(1, 0, 1);">w-1;x++)  
  89.            {  
  90.               //條件1：p必須是前景點  
  91.               if(imgBuf[y*w+x]==0 ) continue;  
  92.    
  93.               neighbor[0]= imgBuf[y*w+x+1] ;  
  94.               neighbor[1]= imgBuf[(y-1)*w+x+1];  
  95.               neighbor[2]= imgBuf[(y-1)*w+x];  
  96.               neighbor[3]= imgBuf[(y-1)*w+x-1];  
  97.               neighbor[4]= imgBuf[y*w+x-1];  
  98.               neighbor[5]= imgBuf[(y+1)*w+x-1];  
  99.               neighbor[6]= imgBuf[(y+1)*w+x];  
  100.               neighbor[7]= imgBuf[(y+1)*w+x+1];  
  101.    
  102.               //條件2：<=N(p)<=6  
  103.               int np=(neighbor[0]+neighbor[1]+neighbor[2]+neighbor[3]+neighbor[4]+neighbor[5]+neighbor[6]+neighbor[7])/255;  
  104.               if(np<2 || np>6) continue;  
  105.    
  106.               //條件3：S(p)=1  
  107.               int sp=0;  
  108.               for(int i=1;i<8;i++)  
  109.               {  
  110.                   if(neighbor[i]-neighbor[i-1]==255)  
  111.                      sp++;  
  112.               }  
  113.               if(neighbor[0]-neighbor[7]==255)  
  114.                   sp++;  
  115.               if(sp!=1) continue;  
  116.    
  117.               //條件4：p2*p0*p4==0  
  118.               if(neighbor[2]&neighbor[0]&neighbor[4]!=0)  
  119.                   continue;  
  120.               //條件5：p2*p6*p4==0  
  121.               if(neighbor[2]&neighbor[6]&neighbor[4]!=0)  
  122.                   continue;  
  123.    
  124.               //標記刪除  
  125.               mark[w*y+x]=1;     
  126.               markNum++;  
  127.               loop=TRUE;  
  128.            }  
  129.        }  
  130.    
  131.        //將標記刪除的點置為背景色  
  132.        for(y=0;y<<span style="line-height: 28px; color: rgb(1, 0, 1);">h;y++)  
  133.        {  
  134.            for(x=0;x<<span style="line-height: 28px; color: rgb(1, 0, 1);">w;x++)  
  135.            {  
  136.               k=y*w+x;  
  137.               if(mark[k]==1)  
  138.               {  
  139.                   imgBuf[k]=0;  
  140.               }  
  141.            }  
  142.        }  
  143.    
  144.     }   
  145. }  

 

 

判斷一個點是否能去掉, 要根據它的八個相鄰點的情況來判斷。(中間的點)

 

 

 

       (1)不能刪，因為它是個內部點，我們要求的是骨架，如果連內部點也刪了，骨架也會被掏空的；

       (2)不能刪，和(1)是同樣的道理；

       (3)可以刪，這樣的點不是骨架；

       (4)不能刪，因為刪掉後，原來相連的部分斷開了；

       (5)可以刪，這樣的點不是骨架；

       (6)不能刪，因為它是直線的端點，如果這樣的點刪了，那麼最後整個直線也被刪了，剩不下什麼；

   總結：

(1)內部點不能刪除；

(2)孤立點不能刪除；

(3)直線端點不能刪除；

(4)如果P是邊界點，去掉P後，如果連通分量不增加，則P可以刪除。

 

 

 

  • Hilditch、Pavlidis、Rosenfeld細化算法

這類算法則是在程序中直接運算，根據運算結果來判定是否可以刪除點的算法，差別在於不同算法的判定條件不同。

 

Hilditch算法使用於二值圖像，比較普通，是一般的算法；

Pavlidis算法通過並行和串行混合處理來實現，用位運算進行特定模式的匹配，所得的骨架是8連接的，使用於0－1二值圖像；

Rosenfeld算法是一種並行細化算法，所得的骨架形態是8－連接的，使用於0－1二值圖像。

 

(後兩種算法的效果要更好一些，但是處理某些圖像時效果一般，第一種算法使用性強些。)

 

 

  • 索引表細化算法

經過預處理後得到待細化的圖像是0、1二值圖像。像素值為1的是需要細化的部分，像素值為0的是背景區域。基於索引表的算法就是依據一定的判斷依據，所做出的一張表，然後根據魔鬼要細化的點的八個鄰域的情況查詢，若表中元素是1，若表中元素是1，則刪除該點（改為背景），若是0則保留。因為一個像素的8個鄰域共有256中可能情況，因此，索引表的大小一般為256。

 

 

         查找表為二值圖像處理提供了簡潔而有效的方法。考慮一個像素的３乘３鄰域。由於在這個鄰域范圍有９個像素，每個像素有兩個狀態（二值圖像，取０，１），那麼整個鄰域不同狀態的總數量為２^9=512 .這樣，我們可以相對不同的情況（５１２種），來安排對應的輸出值，而這５１２種可能是事先預知的，給每一個單元（一共９個單元）分別安排不同的權值，

           

１　８　      6４

２　１６　１２８

４　３２　２５６

 

也就是２的不同冪次，０，１，２，３。。。　８次冪

那麼，某種狀態數值就是加權值的和。

比如，

下面一種鄰域組合：

０　１　０

１　１　０

０　０　１

它的值＝２＋８＋１６＋２５６＝２８２

 

這樣的話，我們通過一個數值，就可以表達一種３乘３鄰域的一種空間分布狀態。    

arrow
arrow
    全站熱搜

    Rocky 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄