碎紙片的拼接復原模型

鄧方清　鄧小安

【摘要】針對碎紙片的拼接復原問題，本文從邊緣像素矩陣入手，通過對該矩陣數據的標準化處理、求取像素平均值、定義像素255的頻率、矩陣分塊等方法，運用相關的匹配度算法分析，建立了縱切又橫切的碎片拼接復原模型.

【關鍵詞】像素矩陣；聚類；距離匹配度算法

一、引言

據了解，傳統上，拼接復原工作需由人工完成，準確率和效率都很低.特別是當碎片數量巨大，人工拼接很難在短時間內完成任務.大量的實例證明，碎紙拼接技術在司法物證復原、歷史文獻修復等領域都有著非常重要的應用.所以提高碎紙數量巨大拼接復原的效率和開發碎紙片的自動拼接技術具有重要的研究意義.本文研究被橫切成11條、縱切成的19條碎片進行拼接復原，結果顯示，拼接復原相似度高.

二、縱切又橫切的碎片拼接復原模型

1.邊緣像素矩陣

碎紙片的左右兩邊或上下兩邊的被橫縱切的線條是平直的，得到第i條碎片的像素矩陣：

從中各自選取左右邊緣一列的像素矩陣作為邊緣像素矩陣以便于建立模型時可以進行像素點的距離匹配度分析.

2.數據標準化處理

假設第i條碎紙片取值為aij.將各個影響因素的值aij轉換成標準化指標值

（一）模型的建立

針對中文碎片拼接復原模型，先通過求取像素平均值、點像素255單文本數據的頻率等數據處理方法來對209條碎紙片的邊緣像素矩陣進行分塊，再逐步進行聚類分析，從而得到11組包含19個碎紙片左右邊緣的匹配組合，接著在得到條橫切的碎紙片后，通過比較分析每條新的碎紙條上下兩邊邊緣矩陣對應的空白或字體的寬度之和來進行橫條的上下拼接.從而使所有碎紙條得以拼接復原.

1.縱切碎紙片模型問題

假設C表示209條碎紙片的拼接復原圖形，Ci表示第i條的像素矩陣，如下所示：

由以上的算法可知，開始時，在Pl的第1列，頂部分、中部分和底部分共三部分各自都選取了匹配數值最大的前19位匹配度.在各自得到了19個可以拼接復原的組合后，統計出并記錄下連續在頂、中、底三部分中都有被選取出來的組合，以及在任意兩部分或只有一部分被選取出來的組合.如果在三部分都被選取出來的組合，則準確率極高地說明它們的匹配度很高，將其分成一類.如此計算可得出11類碎紙片，可以將這11類中的每一類拼接復原成原圖形的11條橫條.

2.縱切碎紙片模型問題

解決了碎紙片被縱切的拼接復原問題后，接著就是要將這11條橫條上下拼接復原成完整的原圖形.本文借助行高、行間距，根據它們的一般不變性，尋找11條橫條的最佳匹配組合.具體過程如下：

Ui=ui，-ui，當Ma矩陣所有元素為255否則

Di=di，-di，當Ma′矩陣所有元素為255否則

其中ui，di>0，Ma是上邊緣像素矩陣，Ma′下邊緣像素矩陣.所以，可知，本文用正數代表像素值為255的白色邊緣，負數代表存在像素值為0的有字邊緣，ui表示上邊界空白邊緣的最大寬度，-ui表示上邊界字體邊緣的最大寬度，而di表示下邊界空白邊緣的最大寬度，-di表示下邊界字體邊緣的最大寬度.

定義Q1和Q2：

Q1=ux+dyx，y∈[1，11]且x≠y

Q2=|-ux|+|-dy|=ux+dyx，y∈[1，11]且x≠y

在上述等式定義的過程中，假設原圖形文件中文本的行間距為H1，行寬為H2.先任意依次取所有碎紙片的上邊緣空白寬度和不同碎紙片的下邊緣空白寬度進行加法求和的運算，判斷Q1與H1的大小關系；接著在依次取所有碎紙片的下邊緣字體寬度和不同碎紙片的上邊緣字體寬度進行加法求和的運算，判斷Q2與H2的大小關系.

若Q1=H1，則說明第y條碎紙片的下邊緣空白的寬度與第x條碎紙片的上邊緣空白的寬度之和等于文件中文本的行間距，即可知，第y條碎紙片應拼接復原在第x條碎紙片的上方.若Q2=H2則說明第y條碎紙片的下邊緣字體的寬度與第x條碎紙片的上邊緣字體的寬度之和等于文件中文本的行寬，即可知，第y條碎紙片應拼接復原在第x條碎紙片的上方.如此計算循環下去，結合先前進行縱切的拼接復原，剩下的11條碎紙條也可上下拼接復原成原圖形文件.

（二）模型求解

使用MATLAB獲取每一條碎紙片的像素矩陣，對之中的每行像素值進行平均值求取，計算接連的六個平均值為一個單位進行像素255數據單文本的頻率，進而得到一個矩陣30×209矩陣B，

如果在1，2，3三部分都被選取出來的組合，則準確率極高地說明它們的匹配度很高，將其分成一類.最終聚類形成了11個組合類.接著，對這11個類進行匹配分析得到11條橫切的碎紙片.通過比較每條新的碎紙條上下兩邊空白或字體的寬度來進行橫條的上下拼接.

三、結束語

通過對此模型的結果研究顯示，本文的碎紙片復原模型的拼接相似度很高.對于碎紙片較少時，可以不需要人工干預，而碎紙片數量非常大時，極其需要人工的干預.本模型只適用于單面規則的碎紙片復原，而且在自動拼接的過程中，如果出現一次相鄰碎紙片拼接錯誤，那么就有可能導致后續一系列的拼接錯誤.所以應減少人工的干預次數.

【參考文獻】

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

[2]張國林.基于漢字識別的碎紙片拼接復原模型研究[J].科技廣場，2014（01）：62-64.