一種基于形狀匹配的碎紙片拼接系統(tǒng)設(shè)計

李旭茹+韓冬+劉德磊

摘要：碎片自動拼接技術(shù)主要使用于五大領(lǐng)域：考古研究、刑偵、自動裝配、古生物學(xué)和壁畫保存中，在圖象處理與模式識別中是一個非常經(jīng)典的應(yīng)用。該文的主要工作是利用邊界鏈碼提取碎片的輪廓特征，研究碎片拼接的形狀匹配算法，進而完成碎紙片的拼接。最后，利用matlab軟件，做出GUI界面，實現(xiàn)了碎片的自動拼接。實驗結(jié)果表明，該算法簡單，易于實現(xiàn)，并可以得到更好的結(jié)果。

關(guān)鍵詞：碎片拼接；邊界鏈碼；輪廓提??；形狀匹配；應(yīng)用

1概述

目前，大部分的拼接工作都是手工完成的，雖然國外已經(jīng)做了一些研究，但是由于技術(shù)應(yīng)用的特殊背景，基本沒有可供參考的資料，主要研究在文物的自動修復(fù)、考古研究、自動裝配與失效分析以及古生物學(xué)、醫(yī)學(xué)分析等領(lǐng)域。在計算機視覺領(lǐng)域，輪廓特征包含對象的重要信息，成為一個非常重要的“介質(zhì)”，在碎片復(fù)原的各種算法中，基于輪廓的形狀匹配技術(shù)一直是研究熱點。該文討論了一種改進的應(yīng)用于碎紙拼接的形狀匹配算法，對一種壁畫碎片的形狀匹配方法-引進行了改進，并把它應(yīng)用于碎紙拼接，達到了比較好的效果。

2形狀匹配算法研究

本文的主要工作是研究基于形狀匹配的數(shù)字圖像處理方法，并利用計算機進行圖像處理。在閱讀大量文獻的基礎(chǔ)上，完成了基于圖像處理的碎片拼接方法的研究。算法的流程圖如圖1所示：

2.1碎片的獲取

采用了掃描儀獲取碎片，將掃描結(jié)果以圖片的形式保存下來。如圖2掃描的破碎發(fā)票圖片。

經(jīng)過一系列的圖像灰度化、二值化、輪廓提取等預(yù)處理后，我們可以得到碎片圖像的外輪廓，為后面的形狀匹配奠定基礎(chǔ)。挑選三個碎片的輪廓為例，如圖3所示。

2.2形狀匹配算法研究

碎紙片外輪廓提取出來以后，在所有的碎片輪廓中，首先任意選定一個碎片輪廓，稱之為固定碎片，并把它放在參考坐標(biāo)系中，其余的都是旋轉(zhuǎn)碎片。給定兩個碎片，想知道輪廓是否匹配以及在哪里匹配，總體思路就是將碎片用差分鏈碼表示出來，進而找待匹配碎片。當(dāng)碎片進行匹配時，兩個曲線會有間隙部分，間隙部分統(tǒng)計出的黑色像素點的個數(shù)最少時，有可能匹配；當(dāng)不匹配的時候，統(tǒng)計出的黑色像素點的個數(shù)很多，遠遠超過我們所設(shè)定的閾值范圍。具體可描述如下：

第一步，在固定碎片上取長度為COMP_LEN的比較像素，在待匹配碎片上也取同樣長的長度進行比較匹配。如圖4所示.

匹配過程歸納為四個步驟：

（1）將碎片A和B用差分鏈碼表示出來，差分鏈碼具有旋轉(zhuǎn)不變性的特點。

f21在碎片A上面取一定長COMP_LEN的像素，稱為目標(biāo)邊界，L₁，L₁。是一系列數(shù)字組成的鏈碼，記為L₁={a1，a2，a3…an}；

（3）在待匹配碎片B上面是遍歷搜索，同樣取一定長COMP_LEN的像素，稱為待匹配邊界，L₂，L₂：同樣是一系列數(shù)字組成的鏈碼，記為，L₂={b1，b2，b3…bn}；

（4）將L₁，L₂：相減求平均值Q，如果Q=0，則將碎片B記錄為一個可能匹配碎片，記錄該段鏈碼的中心點位置，作為下一步旋轉(zhuǎn)的待匹配點，這樣就會找到多個可能匹配的曲線，接下來用面積準(zhǔn)則判斷。全部遍歷后，如果沒有找到匹配段，那么繼續(xù)尋找下一個碎片。

第二步，利用面積匹配準(zhǔn)則判斷化，即考慮固定碎片和旋轉(zhuǎn)碎片曲線所封閉的像素數(shù)目的變化。如下圖5所示，要計算出屬于封閉部分的黑色像素數(shù)目。

淺灰：A和B重疊部分黑色：A和B之間的間隙部分

假設(shè)兩個碎片輪廓稱為A和B，在像素#P_A和#P_B之間進行匹配。如果是在兩個相對應(yīng)的曲線之間進行匹配，那么輪廓封閉之間的黑色像素數(shù)目一定小于某個設(shè)定值，我們稱之為MAX_AREA，最合適的MAX_AREA不是人為設(shè)定，而是根據(jù)碎片的受損程度來決定。對于每一個旋轉(zhuǎn)碎片的位置，匹配精度會隨著MAX_AREA值的增大而下降，可能會出現(xiàn)錯誤匹配。所以，選擇合適的MAX_AREA值，降低錯誤匹配的發(fā)生率。本文中，我們是這樣選擇MAX_AREA的：

MAX_AREA=（0.2～0-3）*COMP_LEN

2.3拼接結(jié)果分析

將該算法應(yīng)用于碎紙拼接過程中，取得了較好的效果，我們還可以通過控制比較長度、封閉面積等參數(shù)來優(yōu)化算法，使匹配效率進一步提高。在本文中，令比較長度COMP_LEN=80像素，MAX_AREA=20像素，以下是對拼接過程的具體分析。

為了表示方便，先將這十塊碎片進行編號。將碎紙圖像的上層碎片從左到右編號為1、2、3、4、5，同理，下層碎片從左到右編號為6、7、8、9、10。假設(shè)固定碎片選為1號碎片，其他碎片均為待匹配碎片，然后進行拼接。如表1所示，這是碎片拼接中的匹配順序。

上面的表格顯示了碎片的拼接順序，最后的拼接結(jié)果圖如下圖6所示。

圖6是一幅拼接好的圖形，白色是在拼接的過程中像素的疊加，從實用的角度來看，對原內(nèi)容的識別沒有影響。由圖可知，最后一個碎片的拼接相比較其他碎片，存在匹配誤差，但是這個誤差在預(yù)期范圍內(nèi)，不可能所有的碎片拼接后，都能恢復(fù)成原來的樣子，總有一些客觀因素存在。

最后，設(shè)計一個完整的圖形用戶界面（GUI）的MATLAB應(yīng)用程序，從讀入碎片開始，完整的顯示了碎片拼接的過程。如圖7所示。

3結(jié)論

仿真結(jié)果表明，形狀匹配算法是可行的、快速的。本次實驗所采用的碎紙片數(shù)量不多。但最后也拼接成功，這表明復(fù)原碎片拼接技術(shù)的可行性，接下來的方向就是增加碎片的數(shù)量，看算法是否還可行，并做出進一步的調(diào)整，加快拼接速度，使適用范圍更廣。