周詩豪

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

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

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

1 概念引入

1.1 最小二乘法

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

1.2 圖片灰度值

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

2 基本假設(shè)

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

3 模型的建立與求解

3.1 模型的建立

3.1.1 問題的分析

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

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

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

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

=；

3.2 模型的求解

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)

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

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

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

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