基于相似度分析的碎紙片拼接復原

孫鵬程+耿大猛+常晶晶+王玲

摘 要：現實生活中，傳統拼接復原工作需要手動拼接，雖準確度較高，但拼接難度較大，效率較低，特別是當碎片的數量極大時，人工手動拼接工作將很難在短時間內完成。基于上述背景，該文利用matlab軟件，對碎紙片二值化矩陣中的邊緣矩陣進行提取，為減少拼接工作量，該文通過觀察并計算出文檔中最左端碎片的排列方式，最后應用統計學中的相關系數最大的條件找到最左端碎片的最佳匹配行，并以此方法完成拼接，得到的拼接結果較為完整，證明方法拼接效果良好。

關鍵詞：圖像識別 二值化 相關系數 邊緣矩陣

中圖分類號：TP301 文獻標識碼：A 文章編號：1672-3791（2017）01（b）-0040-02

傳統人手撕碎片總是無規則的，其拼接一般是利用基于碎片幾何特征的方法，但這種方法對邊緣規則的碎片的拼接效果不是很理想，該文針對目前碎片拼接領域存在的這種不足，進行完善并設計了拼接邊緣規則碎片的方法。

該文利用研究出的拼接邊緣規則碎片的方法，解決2013年數學建模國賽B題的碎片拼接問題，對附件中給出的209張橫縱切中英文碎片進行二值化處理，然后對得到的邊緣矩陣進行相關分析，依據相關性分析完成最終的拼接。

1 圖像處理及分析

灰度變換指黑白圖片的黑白變換或者彩色圖片的色彩變換，一張彩色圖片的像素矩陣中的每個像素由RGB 3種顏色按照規定比例混合而成的一種顏色表示，在處理圖像時，RGB會由于環境光源太暗而偏小，造成圖像不清晰，若光源太亮，則會導致圖像曝光率太高而泛白，該文通過灰度變換方法，將RGB值調到合適的程度。灰度RGB的范圍是0～255，表示亮度從深到淺，對應圖像中的顏色從黑到白。該文運用matlab軟件對209張碎紙片分別進行灰度處理。

2 相似度分析

二值化處理是指通過對灰度變換后的圖像設定閾值而將RGB灰度值分為兩部分，并分別用0、1表示，最終得到二值化矩陣的方法。該文通過對209張既橫切又縱切的碎片進行二值化處理，得到每張碎片的上下左右邊緣矩陣，通過matlab編程對邊緣矩陣的數值進行獲取，若碎片中的文字被橫切或縱切，利用統計方法對所有碎片的上下、左右邊緣矩陣分別進行相關性分析，并計算出兩邊緣矩陣的相關系數，計算順序為從上到下或從左到右，選取其中相關系數最大的兩張碎片即為能夠互相匹配的碎片，計算方法為，例如：中文碎片049、054、065、143、186、002、057能夠拼接在同在一行，碎片左右邊緣相關系數為0.921 4、0.894 7、0.912 3、0.945 3、0.856 8、0.883 6，經觀察比較，上述相關系數均為同比系數中最大。圖1、2為兩張完成拼接的碎片，觀察其拼接之后的“斷”“a”，可發現其邊緣矩陣的相似性。

3 確定文檔首列

首先進行首列的選取，由于第一列每張碎片左邊緣矩陣中空白行列數為一固定值，據此條件在209張碎片中選取出第一列中的11張碎片，具體操作方案為：通過matlab編程確定出每張碎片的二值化矩陣，并對這些數據進行篩選，統計出209張碎片中的左邊緣空白矩陣的個數，得出眾數為中文11個，英文14個，其中左邊緣矩陣個數恰為眾數的碎片即為備選碎片，最后通過人工干預選出第一列中的11張碎片；其次對選出的11張碎片進行排列，對于材料中的中文碎片，可分析每個漢字縱向最大占有距離為40個像素點，中文行間距最大占有距離為30個像素點，如圖3所示，然后將第一列的碎片分為兩類：一類是橫向切割處為漢字；另一類是橫向切割處為空白行。對于第一類，擬采用相關系數法進行拼接，進行縱向排序；對于第二類碎片的拼接方法，根據兩相鄰行字符之間空白最大占有距離為30個像素點的條件，用matlab進行分析計算得到與待匹配碎片匹配度最高的碎片。對于材料中的英文碎片，由于每個英文字母大小不一，故將其放入四線三格中表示，并發現所有英文字母均占滿四線三格中的第二格，據此觀察二值化矩陣中，四線三格的中間行所占最大像素點行數為25，由此確定四線三格的具體分布，如圖4所示，任意一個英文圖片碎片，通過matlab從文檔上邊界進行數值捕捉，當出現任意25行像素矩陣數值之和最小時就可以確定出此時對應的這25行中最上邊的一行就是虛擬四線三格中的第2行，具體實現公式為：，經測算，相鄰兩個四線三格中間行最大垂直距離為40個像素點，然后再將拼接的碎片進行同樣的分類，對于橫向切割處為空白行的碎片，利用相鄰兩四線三格中間行的行間距為40個像素點的條件，應用matlab進行分析計算，得到相配碎片，并綜合所有碎片數據，最終得出第一列英文碎片的排列結果。

另外，中英文第一列縱向匹配若出現一行或多行無字情況，需自行人工干預，按照原始參數，對所有無字行進行假設添字。對于添字處理后的中文碎片，依舊根據兩相鄰字符之間的行間距為30個像素點的條件，找到其最佳匹配碎片，完成縱向拼接。對于英文碎片的空白行，該文僅對英文字母四線三格中的中間格進行添字處理，根據相鄰兩個四線三格中間行垂直距離為40個像素點的條件，找到最佳匹配碎片，完成拼接。

4 所有紙片的拼接復原

對于已確定的第一列的碎片，需要對每一個分別進行橫向排列，分析全部碎片二值化矩陣信息，提取所有碎片的左右邊緣矩陣。以第一列的每一個碎片為起點，依舊利用統計學中的相關系數計算方法，從左向右進行計算，通過篩選找出與每個碎片的右邊緣矩陣相關系數最大的矩陣，并將其還原為碎片，此碎片即為最佳匹配者。依據此法，完成對全文拼接。

5 結論與分析

該文對圖像邊界及其文字進行研究，提出了一種基于相似度分析對碎紙片進行拼接復原的方法，該方法利用matlab軟件對二值化圖像的邊緣矩陣進行了比較，并利用邊緣矩陣的相關系數，找到最佳匹配者，最終完成題材中的碎片拼接難題。該方法減少了大量人工干預，實現簡單，不依賴于碎片的幾何特征，可靠性比較好，在司法物證復原、歷史文獻修復以及軍事情報獲取方面有顯著作用。

參考文獻

[1] 房然然.二維碎片自動拼接技術研究[D].山東師范大學，2015.

[2] 莊俊東.基于數字圖像處理的人民幣碎片拼接方法的研究[D].上海交通大學，2010.

[3] 劉賜德，苗楠茜，常清，等.改進的規則碎片拼接復原算法[J].南陽師范學院學報，2014（3）：22-24.