一種基于鏈碼技術的圖像目標物體面積統計新方法

摘要：論述利用鏈碼進行圖像中目標物體邊界提取的過程。介紹利用基于鏈碼技術的線段表法求封閉區域面積的原理及步驟，提出一種基于鏈碼技術的封閉區域面積統計新方法，并通過實驗對兩種封閉區域面積統計方法進行比較。結果表明新方法具有設計思想簡單、易于實現的特點。

關鍵詞：鏈碼； 邊界； 面積； 圖像

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2008)01－0303－03

細胞是生物體和生命活動的最基本單元結構，木材的細胞體、細胞密度和細胞形狀不同，導致木材材性、物理力學性能不同。以細胞的各項特征參數為依據，對木材的解剖構造特性進行研究，在微觀層次上反映木材的宏觀特性，成為木材材種識別的重要依據，也是木材科學研究中的重要研究內容之一。

在細胞的各項特征參數中，細胞的面積在判斷板材材種的過程中占有重要地位，它是判定板材材種的關鍵參數。以往圖像中的目標物體面積統計方法均是通過畫出目標物體輪廓后，逐行統計區域內的像素點個數。這就要求先計算出目標物體輪廓上各個點的坐標。這樣做既費時又費力。針對以上問題本文提出了一種基于鏈碼技術的圖像目標物體面積統計新方法。

1目標物體邊界提取

在微觀層次上對板材特征進行研究，要求嚴格按照細胞的實際形狀進行各項特征參數的統計。因此，準確地提取細胞（目標物體）的邊緣輪廓很重要。

1．1鏈碼表示法

鏈碼(又稱為freeman 碼)是用曲線起始點的坐標和邊界點方向代碼來描述曲線或邊界的方法，常被用來在圖像處理、計算機圖形學、模式識別等領域中表示曲線和區域邊界[1]。常用的鏈碼按照中心像素點鄰接方向個數的不同分為四連通鏈碼和八連通鏈碼。四連通鏈碼的鄰接點有四個，分別在中心點的上、下、左、右，如圖1所示。八連通比四連通鏈

碼增加了四個斜方向，如圖2所示。因為任意一個像素周圍均有八個鄰接點，而八連通鏈碼正好與像素點的實際情況相符，能夠準確地描述中心像素點與其鄰接點的信息，所以本文選擇八連通鏈碼。

物體的邊界在計算機中是通過多個依次相鄰的像素點表示的。所以，如果知道了遍歷的起始點，根據下一個邊界點相對于起始點的方向碼值就可以找出下一個邊界點的位置。因此，一條曲線可以用曲線遍歷的起始點和各邊界點的方向碼值來定義，該表示曲線的方法被稱為鏈碼表示法。

1．2邊界提取

采用鏈碼表示法表示目標區域邊界時，任何一條曲線均可表示成如下形式： 

在用鏈碼法描述區域邊界時，還應該先確定鏈碼遍歷的方向。本文采用右手法則，即如果當前像素點有多個鄰接點為黑色，那么按圖3中的0，1，2，3，4，5，6，7的方向，查找第一個為黑色的點，將該點作為下一個遍歷點[3]。

以圖4為例說明采用右手法則遍歷圖像邊界的過程。以A點為起始點，應用右手法則可以得到下一個邊界點為B，方向碼值為2，再將B作為起始點找到它的下一個邊界點為C，方向碼值為3，重復上述過程，直到當前邊界點下一個滿足條件的邊界點為起始點A時結束。這樣就得到了區域的邊界，如圖5所示。

圖4的鏈碼為234576712[4]。由此可知，知道了A、B、C、D、E、F、G、H、I中任意一點的坐標及其他各點的鏈碼值，就能夠準確地描繪出區域的邊界。其流程圖如圖6所示。雖然起始點不同，其形成的鏈碼序列不同，但它們描繪出的曲線形態不變[5]。采用鏈碼表示法可以用確定的方向碼值來表示像素點間的位置關系，用較小的數據量存儲圖像中目標物體的形狀及位置信息，降低了信息的冗余，大大減少了計算量，具有節省存儲空間、計算準確、表示簡單的優點。

除了以上特點外，鏈碼還具有平移不變性的優點，即根據鏈碼，可以在任意位置重繪物體的邊界。例如在對圖像進行分析的過程中，有時需要對圖像中的某一個物體進行單獨分析，為了更便于分析，需要將該物體從圖像中提取出來單獨顯示，采用鏈碼技術的平移不變性可以很方便地解決這個問題。

取順時針方向對物體進行遍歷。在遍歷封閉區域邊界的同時，記錄下個點相對于前一個邊界點的方向，將它們依次記錄在一個方向數組lianma中，這樣輪廓的形狀信息就保存了下來。即使改變了起始點A的坐標，但由于lianma數組中記錄的是各點相對于前一邊界點的方向，仍可以在新設定的起始點位置準確地描繪出物體的外輪廓，這對于準確地分析圖像很有幫助。

鏈碼具有上述優點，使對于圖像特征信息的提取和分析變得簡單，所以本文采用鏈碼技術進行封閉區域面積的統計。

2封閉區域的面積統計方法

在黑白二值圖像中，封閉區域為黑色，背景為白色。由于計算機中任何圖形均是通過相互連接在一起的多個黑像素點構成，封閉區域的面積可以用其內部的像素點的個數來表示。

2．1線段表法

將一個封閉區域看做由多條緊密相連的由像素點組成的水平線段構成。其中每一條水平線段均用該線段的左右兩端點來表示。所謂線段表是指將一個封閉區域中的所有水平線段按掃描順序排列起來得到的端點所組成的表。由于線段表具有上述結構特點，使得它可以很方便地獲取封閉區域內部的像素數據，對內部點進行各種處理。

既然封閉區域的面積可以通過內部像素點的個數來表示，而且又可以看做由多條水平線段組成，那么將封閉區域內的所有水平線段的長度相加，就得到了其內部所有像素點的個數，也就計算出了封閉區域的面積。下面介紹利用線段表求封閉區域面積的具體步驟。

1）進行鏈碼表到線段表的轉換

a）根據起始點坐標和鏈碼表計算出封閉區域所有邊界點的坐標。

b）按邊界點類別不同，分為兩種情況處理：

(a)左、右端點，即該點的右（左）邊為區域內的點，而其左（右）邊不是區域中的點如圖7中的B、C 兩點。

(b)單頂點，即由單點構成封閉區域的頂點。如圖7中的A點，可以將它看做既是線的左端點，又是右端點，在線段表中出現兩次，線段長度為1。 

c）對得到的線段表先按縱坐標排序，再按橫坐標排序。

2）計算封閉區域面積

對于縱坐標相同的點，用偶數點橫坐標減去奇數點的橫坐標，如第2點減第1點，第4點減第3點，就得到了相應線段的長度。對于(b)雖然兩個端點的橫坐標差為0，但可以將其看做是只有一個像素點的特殊線段，其長度為1。這樣將各線段的和相加就得到了封閉區域的面積[6]。

2．2基于鏈碼技術的封閉區域面積統計方法

在利用線段表法求封閉區域的面積時，不僅需要通過鏈碼表內的鏈碼值計算出各邊界點的坐標，將鏈碼表轉換為線段表，而且對于圖7中的A點，線段僅有一個像素點的情況還要作特殊處理，算法設計復雜、費力。為解決上述問題，本文提出了一種新的基于鏈碼表的封閉區域面積統計方法。在介紹新方法之前，先討論如下問題：

對于黑白二值圖像，封閉區域為黑色，背景為白色，采用鏈碼法很容易就可找到封閉區域邊緣，但在封閉區域邊緣遍歷完成之后，若不作任何處理，程序會從當前點的下一個像素點找下一個黑色像素點作為下次遍歷的起始點，這就出現對同一個封閉區域進行多次遍歷的情況。 

如圖8所示的封閉區域可以看做由如圖9所示的多個半徑遞增的黑像素邊界構成。在進行封閉區域個數統計時，第三層封閉區域邊界遍歷完成以后不作處理，計算機則又會對第二層進行遍歷，然后再對第一層封閉區域遍歷，直到無黑像素點為止。因此，在對封閉區域的周長計算時，對于圖8要先進行輪廓提取處理，去掉封閉區域內部的黑像素點，或者將鏈碼表轉換為線段表，將封閉區域內的每條線段的左右兩端點之間的像素點設置為白色或訪問過狀態，以確保計算機不再對封閉區域內部點進行遍歷，從而避免對同一個封閉區域進行多次遍歷計數。可以看出，如果不對封閉區域內部像素點進行處理，計算機會自動逐層遍歷其內部像素。

封閉區域的面積可以看做是封閉區域內所包含的像素點個數。在跟蹤封閉區域邊界輪廓時，鏈碼表中記錄了封閉區域各邊界點與前一邊界點的鏈碼值，所以鏈碼表的長度即為封閉區域外邊界的像素點的個數。對于圖8的封閉區域，背景為白色，封閉區域為黑色。把封閉區域看做是一層一層的由像素做成的輪廓圈構成，逐層對封閉區域進行遍歷，在遍歷封閉區域的各層邊界輪廓時不對封閉區域內的黑像素點進行處理，只將遍歷過的外層邊界點設置為白色或訪問過狀態，直至封閉區域內沒有黑像素點為止。這時將每一層鏈碼表的長度值相加，它們的累加和即為該封閉區域的面積值。但應用此方法統計封閉區域面積時，對于鏈碼跟蹤程序要作一些改進。因為有的鏈碼表為了計算封閉區域的周長等參數的方便，只在封閉區域的輪廓構成回路，即又回到起始點時如圖10對角線上方的圖形才記錄其鏈碼值。但對圖像進行一層一層剝離后，最后剩下的像素點集合可能構不成一個回路，即回不到本層遍歷的起始點，如圖10中對角線下方a~e之間的點。在這種情況下，如果不作改進則鏈碼表中鏈碼的個數為0，沒有將剩下的未構成回路的點集中像素點的個數加入總面積中，這會使得對面積的統計誤差較大。因此，在未構成回路的情況下，記錄該層邊緣遍歷的起始點到終點的像素點個數，然后與前面各層鏈碼表長度相加得到的才是封閉區域的總面積。其流程如圖11所示。實驗證明，該方法可以準確統計封閉區域面積。表1給出了新方法和線段表法對圖12所示圖形面積統計的比較，圖12（b）（d）（e）是在計算機中使用圖像學知識畫出的，面積已知分別為3 101、859、3 137，其他圖形是直接從圖像中提取的。

當一幅圖像中存在多個封閉區域時，對上述算法還要加限制條件。因為在遍歷完外層邊界點后（如圖13的虛線），回到起始點A后，程序會尋找與起始點在同一行，橫坐標逐漸增大的像素點中是否有黑像素點。如果存在這樣的像素點且未被遍歷過，則將該點作為新的起始點（如圖13中C點），開始遍歷新的封閉區域的邊界。這時就無法應用上述的求面積方法。因此，在圖像中存在多個封閉區域的情況下，當遍歷完封閉區域的最外層邊界后，還要對下一次遍歷的條件作限制，限制其在封閉區域內部尋找下一次遍歷的起始點。這一條件可以通過查找本次遍歷的起始點還有沒有其他未經遍歷的鄰接點來限制。這樣，在圖像中存在多個封閉區域時仍可以運用新方法求封閉區域面積。 



3結束語

鏈碼具有簡單、節省存儲空間、便于計算，以及平移不變性等特點，使得對于封閉區域特征參數的統計變得簡單易行。本文提出了新的基于鏈碼的面積統計方法，該算法設計思想簡單，易于實現。經過木材細胞面積統計實驗，證明該算法能夠準確地統計出木材顯微圖像中細胞（封閉區域）的面積，為從木材微觀構造入手進行木材材種識別，進一步提高材種識別的準確率提供了有效方法。

參考文獻：

[1]羅振東， 廖光裕.計算機圖形學原理和方法[M].上海：復旦大學出版社，1998：44－53. 

[2]孫永香， 鄭永果.基于鏈碼的果實圖像形狀特征提取方法研究[J].福建電腦，2006 (4):129，168.

[3]楊淑瑩.VC++圖像處理程序設計[M].2版.北京：清華大學出版社；北京交通大學出版社，2005:154－157.

[4]唐振軍，張顯全. 圖像邊界的鏈碼表示研究[J].微計算機信息，2005 (23):105－107.

[5]孫力平，曹軍，李玉峰，等.基于模式識別技術實現木材細胞圖像邊緣跟蹤[J].林業機械與木工設備，1999，27(5):11－12.

[6]陸宗騏.C/C++圖像處理編程[M].北京：清華大學出版社，2005.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”