基于特征點匹配的雙面碎紙片自動拼接復原

摘要：本文以2013年全國數學建模競賽B題為背景，主要研究雙面打印碎紙片的拼接復原問題。利用特征點匹配的圖像拼接算法，繪出了基于特征點的圖像拼接流程圖；根據圖像拼接流程圖建立了特征點檢測算法Moravec角點檢測算法模型，通過計算各像素的興趣值、選擇恰當的特征點、候選點，分析運算得到了附件5的碎紙片拼接復原結果。

關鍵詞：拼接復原 特征點匹配 Moravec角點檢測

1 研究背景

破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。傳統上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數量巨大，人工拼接很難在短時間內完成任務。本文利用數學建模，借助MATLAB、SPSS軟件研究試圖雙面打印文件碎紙片的自動拼接復原，以提高拼接復原效率。

2 數據提取

利用題目給的為碎紙片的圖片，先使用MATLAB軟件讀入圖片，把圖片特征位置信息轉換為數字矩陣。

MATLAB函數為：imread（‘file name’）。

3 問題求解

3.1 Moravec角點檢測模型的建立

由于雙面打印文件中碎片數量眾多，利用圖片邊緣灰度矩陣進行匹配時會產生龐大的數據，實際操作過程中進行人工干預會產生很大誤差。

本文采用基于特征點的圖片拼接模型，并取各矩陣的角點為特征點。圖像拼接的質量主要依賴于圖像配準的程度，因此圖像的配準是拼接算法的核心和關鍵。算法的總體思想是既要保證配準的精度，又要保證計算量不要過大。

基于特征點匹配的圖像拼接算法包括：特征點檢測、特征點匹配、空間變換、圖像融合。下圖1是基于特征點的圖像拼接流程圖。

用特征來建立兩幅圖像之間的匹配對應關系，所以提取好的特征是特征匹配的關鍵，那么選擇高精度的提取方法至關重要。特征提取的難點在于自動、穩定、一致性的特征提取。特征點中主要的一類是角點，本文采用的是Moravec角點檢測算法。

Moravec角點檢測算法的基本思想是，以像素的四個主要方向上最小灰度方差表示該像素與鄰近像素的灰度變化情況，即像素的興趣值，然后在圖像的局部選擇具有最大興趣值的點（灰度變化明顯的點）作為特征點。

具體算法如下：

STEP1：計算各像素的興趣值IV（interest value），例如計算像素（c，r）的興趣值，先在以像素（c，r）為中心的 n×n的圖像窗口中（如圖2所示5×5的窗口）計算四個主要方向相鄰像素灰度差的平方和：

STEP2：根據給定的閾值，選擇興趣值大于該閾值的點作為特征點的候選點。

閾值的選擇應以候選點中包括所需要的主要特征點，而又不含過多的非特征點為原則。

STEP3：在候選點中選取局部極大值點作為需要的特征點。在一定大小的窗口內（可不同于興趣值計算窗口），去掉所有不是最大興趣值的候選點，只保留最大興趣值的候選點，該候選點即為一個特征點。

3.2 拼接復原結果

將處理后各組數據帶入特征點檢測算法模型可得即得到附件中各圖片之間的匹配順序。

3.2.1 a面碎紙片拼接復原結果

附件中a面碎紙片復原順序如表1。

3.2.2 b面碎紙片拼接復原結果

附件中b面碎紙片復原順序如表2。

3.2.3 a、b面碎紙片拼接復原圖（如圖3）

3.3 模型評價

雙面打印圖片進行匹配復雜，利用圖片邊緣灰度值矩陣或聚類分析進行匹配時會產生龐大的數據，實際操作過程中進行人工干預產生誤差太大。采用基于特征點檢測算法模型中Moravec角點檢測算法，優點是：

①復原準確率高；

②自動化程度高，即人工干預量小；

③通用性好，盡可能適用多種分割模式下的碎片。

本文在一定意義下得到的結果比較精確。若碎紙片有效特征能進一步提取，既有邊界的像素分布信息、匹配信息、又可利用非邊界區域的文字結構及拓撲信息，行列信息，字體字號，標點符號等，建立正誤判別自動化程序。則依次程序進行拼接復原時，拼接結果可以大大提高精確度并能減少用時。

參考文獻：

[1]賈海燕，碎紙自動拼接關聯技術研究[D].國防科技大學，2005.

[2]云舟工作室，MATLAB數學建模基礎教程[M].北京：人民郵電出版社，2001.

[3]姜啟源等，數學實驗[M].高等教育出版社，1999.

基金項目：

海口經濟學院教育教學改革研究項目（hjyj2012001）。

作者簡介：楊偉芳（1979-），女，海南東方人，講師，教師，研究方向：圖論；王錦升（1984-），男，山東棗莊人，講師，教師，研究方向：小波分析與偏微分方程數值計算。