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

周詩豪

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

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

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

1 概念引入

1.1 最小二乘法

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

1.2 圖片灰度值

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

2 基本假設(shè)

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

3 模型的建立與求解

3.1 模型的建立

3.1.1 問題的分析

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

3.1.2 決策變量及目標(biāo)函數(shù)

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

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

=；

3.2 模型的求解

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

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

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

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

解決上述問題的對應(yīng)方法：

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

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

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

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

4 結(jié)語

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

參考文獻

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

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

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

[4]楊梓藝.紙片拼接技術(shù)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2014（5）.