基于鏈碼的二維碎片輪廓匹配算法

摘 要:首先利用邊界鏈碼的跟蹤技術，提取出二維碎片的輪廓信息，同時對輪廓線進行細化#65380;去噪和編碼處理，得到二維輪廓線的一維鏈碼信息描述，并在此基礎上提出一種基于鏈碼的二維碎片輪廓匹配方法#65377;將二維碎片的形狀匹配變為只對一維字符的處理，從而使得二維碎片的拼合簡單化#65377;實驗表明該方法能夠有效的找出一對復雜輪廓線上恰當的對應特征段，實現碎片物體的復原#65377;

關鍵詞:輪廓匹配;邊界跟蹤;鏈碼;細化;去噪

中圖分類號:TP391文獻標識碼:A

1 引 言

輪廓匹配是計算機視覺#65380;圖像分析和模式識別中的一個重要課題，國內外學者已經對二維輪廓曲線匹配和相似性問題從不同角度展開了研究#65377;Kong^[1]等提出用輪廓線的近似多邊形的配合情況來衡量碎片的匹配程度，有著過多的重復工作#65377;Leitao^[2，3]等通過選取碎片輪廓上的離散點來度量碎片之間的可匹配程度，沒有充分利用輪廓線的幾何特征#65377;Cohen^[4]等人提出了一種基于B樣條的曲線表示和匹配方法，這種方法雖在一定程度上考慮到了輪廓線的幾何特征，但對曲線進行采樣#65380;擬合是一個相當繁瑣的過程#65377;

本文提出了一種基于邊界鏈碼的輪廓匹配方法，給出了具體的實現步驟，該方法能夠充分利用輪廓曲線的幾何信息，基本達到了輪廓自身信息無丟失的狀態#65377;在兩個碎片輪廓之間，利用該方法能有效的找到兩條封閉輪廓線的可匹配特征段，從而完成輪廓的快速匹配#65377;該方法在保證匹配速度的同時，大大提高了匹配精度，且碎片的拼合效果良好#65377;

2 二維碎片輪廓線的表示和處理

在圖像處理和識別中常采用鏈碼^[5]來表示線條的模式，常用的有4-方向和8-方向鏈碼，人們利用鏈碼來計算各種不同的形狀特征^[6]#65377;

在8-方向鏈碼中，鏈碼沿著數字曲線或邊界像素以八鄰接的方式移動和編碼，相鄰兩個像素的偏移量為，八個相鄰方向用數字0到7表示，如圖1所示#65377;

由邊界鏈碼可知，一個物體的邊界可以用一個起始點的坐標和一個方向編碼的序列來表示#65377;針對有清晰輪廓的二維碎片，首先將碎片圖像進行二值化處理，然后用行掃描法得到輪廓的最左上角的邊界點作為跟蹤的起始點，采用一種8-鄰域(如圖2所示)搜索的邊界跟蹤算法，跟蹤算法如下:

計算技術與自動化2007年6月第26卷第2期饒芮菱等:基于鏈碼的二維碎片輪廓匹配算法從第一個邊界點l0(x0， y0)開始，預設起始點的鏈碼值為7，下一邊界點必定在l0的8-鄰域內，從當前點l0的8-鄰域內編碼為7的位置開始，順時針方向移動兩個像素的位置就是8-鄰域搜索下一個邊界點的起始位置#65377;再按逆時針方向依次檢查8-鄰域中的像素值，把最初遇到的0像素記作l1(x1， y1)，記下該點在8-鄰域中的位置編碼m1，然后以l1為下一個搜索的中心點，考察八鄰點，重復上述準則依次跟蹤以后的邊界點，記為:lk (xk， yk) (k=2，3，……n-1)，位置編碼為mk，在搜索完每一個中心點8-鄰域的同時，把該8-鄰域中除進入和離開中心點的0像素之外其余值為0的點的像素值置為1#65377;直到xk=x0#65380;yk=y0，邊界跟蹤結束，得到該輪廓的鏈碼序列:H={m0， m1，……， mn-1}#65377;此時的輪廓線僅擁有一個像素寬度，實現了碎片輪廓的細化，并且由8-鄰域搜索的輪廓線能較好地保持原始輪廓的幾何信息，如圖3所示#65377;

但是把細化后的碎片輪廓線局部放大，發現由于原始輪廓線不可避免的有毛刺現象，在跟蹤過程中，會誤把一些噪聲點當成邊界的像素點，如圖5所示(p， q， r為三個噪聲點)#65377;為克服這些噪聲點對以后輪廓匹配時的影響，要對邊界線做進一步的去噪處理#65377;由8-鄰域搜索的算法得到的單像素曲線，不會出現3類不平滑邊緣^[7]的情況#65377;但是在局部直線段上仍然有噪聲點(如圖4所示)，檢測這些子段上噪聲點的準則是:在局部以五個像素點為一個子段，如果曲線上任一個像素點的前兩個像素值與后兩個像素值相等，而唯獨中間這點的像素值不同，就認為這點是噪聲點#65377;將檢測到的噪聲點像素值置為與前一點相同，即可得到一條局部光滑的單像素輪廓曲線，如圖5所示#65377;

將去噪后的輪廓曲線用上述8-鄰域跟蹤算法重新編碼，起始點不變，得到一組新的鏈碼序列:H′=(x0，y0){m0，m1，……， mn-1}，這便是最終用于輪廓匹配的序列數組#65377;

3 基于鏈碼的輪廓線匹配算法

鏈碼由于具有鏈狀結構描述上的優越性，被廣泛用于模式識別領域中^[8]，本節將給出基于鏈碼的輪廓匹配算法，算法流程圖，如圖6所示#65377;

假定有兩個輪廓A和B，需要先對A和B進行反方向編碼，即一個按順時針編碼，一個按逆時針編碼，編碼方式仍然按8-鄰域搜索的準則#65377;分別用一個長為NA點和NB點的鏈碼序列(x0A，y0A){ai}和(x0B，y0B){bj}表示A#65380;B，為了找到兩條輪廓線A和B的最佳匹配特征段，將輪廓A上從起始點開始長度為s的一段在輪廓B上滑動，具體算法如下:

1)記錄下輪廓A和B的鏈碼點數NA#65380;NB，初始化:d=0#65380;u=s#65380;v=i=0#65380;w=j=0(其中，d和u記錄在比較過程中兩段長度為s的序列中鏈碼值不同的即時個數與最終個數，v和w代表每次比較時鏈碼序列的起始點);

2)從兩個輪廓曲線編碼的起始點(x0A，y0A)#65380;(x0B，y0B)開始，依次比較之后長度為s的鏈碼序列;

3)如果ai≠bj，將d=d+1#65380;i=(i+1)mod NA#65380;j=(j+1)mod NB，否則僅:i=(i+1)mod NA#65380;j=(j+1)mod NB，比較完s個值后，記下d的值，如果d

4)將j=w=w+1#65380;i=v，轉到(3)，直到A中一個長度為s的一段在B上滑動完畢，滑動一次的比較次數是(NB-s+1);

5)然后將i=v=v+1#65380;j=w=0，得到A中下一個長度為s的一段，重復(3)#65380;(4)，使A中所有長度為s的子段與B作比較，記下最終的min{u}和相應的i#65380;j的值#65377;

此時，以i#65380;j對應的點為末端，長度為s的兩個子段就是兩條輪廓上的最佳匹配段，算法時間復雜度為O(NA×NB)#65377;由于s的長短決定了匹配段的起始點，而某些碎片之間只有一小部分是可以粘連在一起的，在實際的匹配工作中，先預設一個較小的s值，找到匹配點后根據匹配程度放寬s的大小，但對s值的選取只是整個匹配過程的后續工作，不會影響匹配算法的運行和有效性#65377;上述算法中，取模是考慮到輪廓都是封閉的曲線#65377;

4 實驗結果

為了驗證上述算法的可行性和效果，以中國地圖中省區圖片為例，采用其進行輪廓的匹配#65377;圖7為青海省地圖，圖8為甘肅省地圖，圖9#65380;10分別為細化和去噪后的輪廓曲線，G1#65380;H1和G2#65380;H2為用基于鏈碼的輪廓匹配算法確定的可匹配特征段的始末端點，在此例中s的值取為125#65377;圖11為地圖上兩省的鄰接情況，圖12是采用本文算法拼合后的輪廓圖#65377;

通過比較圖11的原始鄰接圖和圖12的拼合效果圖，可以看出采用本文的算法找到的兩輪廓間的可匹配特征段是有效的，拼合后的輪廓圖基本上能達到原始的鄰接效果，只是在拼合部分的下端兩條輪廓線的契合不是很好，這是因為原始碎片的輪廓線粗細不均并且帶有噪聲，影響了細化后輪廓線保持原有幾何信息的精確度，但盡管如此，在用本文的算法尋找兩輪廓線的可匹配子段時卻沒有受到影響#65377;

5 結 論

本文提出了基于鏈碼的方法對二維碎片進行輪廓匹配，在對已獲取的碎片原始輪廓通過8-鄰域跟蹤的方法進行細化#65380;去噪的基礎上，得到較理想的輪廓邊界線和鏈碼序列，進而通過文章給出的輪廓匹配算法，比較這些一維的有序數組找到可匹配的輪廓特征段以完成碎片的拼合#65377;應用實例表明本文算法的執行效果和運行精度都是比較另人滿意的#65377;

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