碎紙片的拼接復(fù)原模型

鄧方清　鄧小安

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

【關(guān)鍵詞】像素矩陣；聚類；距離匹配度算法

一、引言

據(jù)了解，傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率和效率都很低.特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù).大量的實(shí)例證明，碎紙拼接技術(shù)在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)等領(lǐng)域都有著非常重要的應(yīng)用.所以提高碎紙數(shù)量巨大拼接復(fù)原的效率和開發(fā)碎紙片的自動(dòng)拼接技術(shù)具有重要的研究意義.本文研究被橫切成11條、縱切成的19條碎片進(jìn)行拼接復(fù)原，結(jié)果顯示，拼接復(fù)原相似度高.

二、縱切又橫切的碎片拼接復(fù)原模型

1.邊緣像素矩陣

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

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

2.數(shù)據(jù)標(biāo)準(zhǔn)化處理

假設(shè)第i條碎紙片取值為aij.將各個(gè)影響因素的值aij轉(zhuǎn)換成標(biāo)準(zhǔn)化指標(biāo)值

（一）模型的建立

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

1.縱切碎紙片模型問題

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

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

2.縱切碎紙片模型問題

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

Ui=ui，-ui，當(dāng)Ma矩陣所有元素為255否則

Di=di，-di，當(dāng)Ma′矩陣所有元素為255否則

其中ui，di>0，Ma是上邊緣像素矩陣，Ma′下邊緣像素矩陣.所以，可知，本文用正數(shù)代表像素值為255的白色邊緣，負(fù)數(shù)代表存在像素值為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

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

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

（二）模型求解

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

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

三、結(jié)束語

通過對(duì)此模型的結(jié)果研究顯示，本文的碎紙片復(fù)原模型的拼接相似度很高.對(duì)于碎紙片較少時(shí)，可以不需要人工干預(yù)，而碎紙片數(shù)量非常大時(shí)，極其需要人工的干預(yù).本模型只適用于單面規(guī)則的碎紙片復(fù)原，而且在自動(dòng)拼接的過程中，如果出現(xiàn)一次相鄰碎紙片拼接錯(cuò)誤，那么就有可能導(dǎo)致后續(xù)一系列的拼接錯(cuò)誤.所以應(yīng)減少人工的干預(yù)次數(shù).

【參考文獻(xiàn)】

[1]賈海燕.碎紙自動(dòng)拼接關(guān)鍵技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2005.

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