基于最小二乘法的橫縱切碎紙片拼接改進算法

周詩豪

摘要：碎紙片拼接技術對于破損文件修復、司法物證復原等領域有重要的應用。傳統人工拼接技術效率低，本文借助算法高效準確地拼接橫縱切碎紙片。首先將碎紙片圖片導入MATLAB轉化為其灰度值矩陣，利用最小二乘原理建立紙片拼接的數學模型，再采用枚舉法并結合Lingo軟件進行數據分析，找出邊緣相似度最高的相鄰矩陣，完成單面11×19張碎紙片的拼接。

關鍵詞：碎紙片拼接 最小二乘 灰度值 改進算法

中圖分類號：TP391.41 文獻標識碼：A 文章編號：1007-9416（2016）05-0000-00

1 概念引入

1.1 最小二乘法

最小二乘法是一種數學優化技術，它通過最小化誤差的平方和尋找數據的最佳函數匹配。一組數據為 ，。令，在回歸分析中稱為殘差。一般使用作為衡量。

1.2 圖片灰度值

在計算機領域中，灰度數字圖像是每個像素只有一個采樣顏色的圖像。我們將19個圖片用imread命令讀入MATLAB，圖片在MATLAB中以灰度圖的形式存在。灰度圖把白色和黑色之間按對數關系分為0～255一共256個等級，0表示黑色，255表示白色。灰度圖是以位圖的格式顯示，整個圖片被分成若干小格。

2 基本假設

1）切割時不丟失信息，紙片的全部信息都包含在所有碎紙片上。2）漢字，英文的字體較規范，每個字所占空間的上下，左右界限一樣。3）原圖排版無錯，不會出現文字錯位、錯寫等情況。

3 模型的建立與求解

3.1 模型的建立

3.1.1 問題的分析

由分析可知，原圖中每行左起第一張碎紙片的左邊白色區域面積最大，即該紙片從左到右連續出現全為255的列數最多。首先，在209個矩陣中找出其中數值全部為255的列數最多的那11個矩陣。然后，以這11個碎紙片為每一行的行首，分別進行每一行的拼接，得到原文橫切割后的11張碎紙片（無序）。最后，將這11條碎紙片進行拼接得到原文圖片。

3.1.2 決策變量及目標函數

決策變量：第個矩陣最左列的第個元素 、第個矩陣最右列的第個元素 ；

為實現碎紙片的拼接復原，則相鄰兩張碎紙片的切割處應幾乎相同，即左邊圖片其對應矩陣的最右邊的列數組的值與右邊圖片其對應數組的最左邊的列數組的值幾乎相等。我們引入表示相鄰兩個碎紙片對應數組的兩個相鄰列不同行元素的差的平方和，即目標函數：

=；

3.2 模型的求解

首先，我們利用MATLAB程序求解出排在原文件最左邊（即第一列）的11張碎紙片的矩陣編號。

拼接方法：以這11張碎紙片為首，各自從左往右進行行拼接。以矩陣編號a的碎紙片為例，利用枚舉法，依次將剩余11*18個未拼接的碎紙片對應矩陣的最左側列數據與矩陣a的最右側列數據一一對應，求出11*18個最小二乘結果。值最小時對應的碎紙片拼接出現錯誤，判斷原因是當切割線在字間空白處時，切割處列向量的最小二乘效果很差，無法保證值最小時拼接正確。故利用MATLAB程序循環求出編號和其他11*18個矩陣上邊際行數值全為255的整行數，其差的絕對值為，，。比較所有的大小，取值最小且最小的矩陣編號值，此時矩陣編號為的碎紙片排在該行的第二列。用相同的方法求出第三列，第四列直到最后一列的碎紙片的編號。相同的，以另外10張碎紙片為首進行行拼接。此時，拼接仍然出現錯誤.可能原因如下：

：原文中漢字或英文字母所占空間大小不一。例如，當切割線在詞“心里”中間分割，這兩張相鄰碎紙片的值卻有的大。即應正確拼接的圖片與已拼接圖片的不一定為最小。

：當行首碎紙片中的第一行字是原文中第二行的字時，該碎紙片上方空白處行數較多，不能用于計算比較。應找出其后第二列的碎紙片，用第二列的碎紙片上方空白處行數與未拼接的碎紙片進行比較。

解決上述問題的對應方法：

：我們給定一個合理的空白處行數差值浮動范圍。方法：從上方有空白的碎紙片中隨機選取7張碎紙片，得出下表相關數據。

表1中表示碎紙片中第二行字上邊界的行數，表示第一行字下邊界的行數，行間距=-：

行間距的值范圍：27～28，則行間距最大差值為2.由于在209張碎紙片中我們只抽取了7張碎紙片且 相鄰碎紙片的空白處行數差值行間距，故我們取0～4作為空白處行數差值浮動范圍。

：由于行首碎紙片的一行字中包含一個完整的字和一個殘缺的字，故可利用殘缺的字所提供的信息，通過最小二乘法，找出第二列的碎紙片。而兩張紙片拼接在一起大約有三個字的寬度。即拼接了第二張碎紙片后，因段首而縮進兩格的第一行會出現第一個字。再對其余的碎紙片進行比較并結合最小二乘結果，得出第三列、第四列直至最后一列的碎紙片。

4 結語

本文提出的拼接模型和相應求解算法的特點在于：綜合各方面干擾因素和各種可能出現的情況，即使在文字分布不規范的情況下也可以完成復原。碎紙片拼接采取的是從左向右依次拼接的方法，在自動拼接的過程中，如果出現依次相鄰碎紙片拼接錯誤，那么就可能導致后續一系列的拼接錯誤。因此，需不斷完善算法使得拼接過程不出差錯方能確保碎紙片拼接復原的實現。

參考文獻

[1]陳冠楠，楊坤濤，陳榮，謝志明.圖像灰度值自然對數比率鄰域濾波方法[J].計算機應用，2009（7）.

[2]陸健.最小二乘法及其應用[J].中國西部科技，2007（19）.

[3]賈小勇，徐傳勝，白欣.最小二乘法的創立及其思想方法[J].西北大學學報（自然科學版），2006（3）.

[4]楊梓藝.紙片拼接技術[J].網絡安全技術與應用，2014（5）.