王勇勇，趙 鋒，曹晨雅，李韶偉

（臺(tái)州學(xué)院 數(shù)學(xué)與信息工程學(xué)院，浙江 臨海 317000）

1 引言

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。然而，大量的紙質(zhì)物證復(fù)原工作目前基本上都是以手工方式完成的，準(zhǔn)確率較高，但效率很低。目前，德國(guó)等發(fā)達(dá)國(guó)家對(duì)破碎文件的自動(dòng)修復(fù)技術(shù)已經(jīng)進(jìn)行了相當(dāng)長(zhǎng)的研究。而在國(guó)內(nèi)，還沒有類似研究成果問世。因此，通過設(shè)計(jì)相應(yīng)的算法軟件，開展對(duì)碎紙自動(dòng)拼接技術(shù)的研究具有重要的現(xiàn)實(shí)意義。本文的目標(biāo)是利用復(fù)原模型設(shè)計(jì)算法輔助的方法對(duì)碎紙機(jī)切碎的紙片進(jìn)行拼接、復(fù)原。

本文主要討論以下問題:

問題1.對(duì)于來自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法。

問題2.設(shè)計(jì)既縱切又橫切的碎紙片拼接復(fù)原模型和算法。

問題3.設(shè)計(jì)雙面打印文件的碎紙片的拼接復(fù)原模型與算法。

本文數(shù)據(jù)來源于2013年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的A題。

2 變量說明和名詞解釋

二值化:由于本題中所有碎紙片都是黑白的，因此將圖片中灰度值＞200的像素點(diǎn)的灰度值賦值為0，即確定該像素點(diǎn)是白色的。將圖片中灰度值＜200的像素點(diǎn)的灰度值賦值為1，即確定該像素點(diǎn)是黑色的。

最佳匹配:根據(jù)所有圖片的左右兩側(cè)邊緣像素形成2個(gè)列向量，元素逐個(gè)進(jìn)行比較是否相同，一直進(jìn)行到最后一對(duì)元素，找到匹配最好的一對(duì)邊緣。

匹配系數(shù):對(duì)所有圖片的兩個(gè)邊緣灰度值的列矩陣中的元素，進(jìn)行逐個(gè)比較，相同記為1，否則記為0，取1的總數(shù)稱為匹配系數(shù)。

人工干預(yù):在程序?qū)崿F(xiàn)最佳匹配過程中，可能出現(xiàn)一個(gè)對(duì)多個(gè)的情況，此時(shí)需要進(jìn)行人工干預(yù)。

行首（尾）圖片:每一行的左（右）側(cè)首張圖片。找左邊:根據(jù)紙張左側(cè)空白的特點(diǎn)，查找碎片左側(cè)空白像素點(diǎn)，從而確定行首圖片。找右邊:根據(jù)紙張右側(cè)空白的特點(diǎn)，查找碎片右側(cè)空白像素點(diǎn)，從而確定行尾圖片。

3 問題分析與求解

3.1 問題一的算法設(shè)計(jì)

問題一的數(shù)據(jù)量較大，僅考慮縱向匹配，中英文的碎紙張拼接復(fù)原都可按以下步驟程序自動(dòng)匹配完成:

第一步:讀取所有圖片左、右兩側(cè)像素點(diǎn)的灰度值。

第二步:將圖片像素點(diǎn)的灰度值進(jìn)行二值化處理得到像素。由圖片的左、右兩側(cè)像素確定的左列矩陣I11和右列矩陣I22。

第三步:分別將圖片左列矩陣I11中的元素與分別于其余18個(gè)圖片右列矩陣I22中的元素，進(jìn)行逐個(gè)點(diǎn)比較，相同的記錄為1，不同的記錄為0，一直進(jìn)行到最后一對(duì)元素。記錄得到一個(gè)新的矩陣I31。同理將圖片右列矩陣與其余18個(gè)圖片進(jìn)行匹配，從而確定匹配系數(shù)。

第四步:根據(jù)第三步得到的匹配系數(shù)可以得到一個(gè)19×19的矩陣M。根據(jù)矩陣M中行向量每個(gè)元素都為0可以確定行首圖片。

第五步:根據(jù)第四步確定的行首圖片，通過矩陣M的元素（即各個(gè)圖片間的匹配系數(shù)）確定剩余圖片的順序。從而，完成19個(gè)碎紙片的縱向拼接。

3.2 問題二算法設(shè)計(jì)

3.2.1 “行高”的定義

1.中文字體“行高”的定義:

縱向投影一張圖片得到一列像素點(diǎn)的灰度值，將灰度值進(jìn)行二值化處理，得后一個(gè)列向量L，根據(jù)以下流程，確定中文字體“行高”h的值:

注:70為圖片中文字距與行距按上述處理后，在列向量L中元素的個(gè)數(shù)L（i）為L(zhǎng)列向量第i個(gè)元素。

圖1 確定中文行高的算法流程圖

根據(jù)該流程圖可以將所有圖片分成以下三種類型

圖2.1

圖2.2

圖2.3

圖 2.1 類型一:圖片頂部是文字，即 L（1）=1，h=i-1；

圖 2.2 類型二:圖片頂部是空白，即 L（1）=0，h=i-1；

圖2.3類型三:圖片頂部是空白，即L（1）=0，h=i-31.

2.英文“行高”的定義:

縱向投影一張圖片得到一列像素點(diǎn)的灰度值，將灰度值分成兩類，一類灰度值較小的賦值為0，灰度值較大的賦值為1，如下圖所示。

圖3 英文碎紙片的“行高”確定示意圖

與確定中文“行高”h的原理相同，此時(shí)取i=64，其余不變。（注:64為圖片中每個(gè)英文都覆蓋的“中間帶”的高度與行間距之和）

同理，若某碎紙片是雙面的，可確定此碎紙片有兩個(gè)“行高”數(shù)值x和y，定義問題三中的需要用到的“二維行高”。

3.2.2 問題二的算法設(shè)計(jì)

由于不能通過直接的左右匹配獲得碎紙片的前后位置，因此我們提取各碎紙片的“行高”信息作為碎紙片的類別標(biāo)志，區(qū)分碎紙片的類別，通過圖2所示的算法步驟編寫的運(yùn)算程序，極大的提高了匹配的精確度。

第一步:提取所有圖片每行像素點(diǎn)的灰度值并進(jìn)行二值化處理

第二步:根據(jù)行首圖片左側(cè)像素點(diǎn)都為0這一特征，在所有圖片中確定11個(gè)行首圖像。

第三步:根據(jù)“行高”的特征進(jìn)行分類，一共可以分成11類，每類19個(gè)圖片（即同一行上所有圖片為一類）。

第四步:將每組中的圖片采用與問題一相類似的方法進(jìn)行縱向拼接。但是由于每個(gè)圖片的左、右兩側(cè)邊緣的像素相對(duì)“問題一”來說減少了較多，所以此次縱向拼接可能出現(xiàn)誤差。在此處需要加入人工干預(yù)，拼接出11行完整的文字圖片。

第五步:通過程序的運(yùn)行，可匹配出若干行碎塊。加一次人工干預(yù)，可獲得11行完整圖片。

第六步:根據(jù)縱向拼接得到的11行的圖片的進(jìn)行橫向拼接。由于圖片上下邊緣的像素點(diǎn)為可能0，所以在進(jìn)行橫向拼接時(shí)，需要再次人工干預(yù)。

3.3 問題三的算法設(shè)計(jì)

“二維行高”的定義:設(shè)a面的“行高”為x，b面的“行高”為y。

第一步:提取所有圖片每行像素點(diǎn)的灰度值并進(jìn)行二值化處理。

第二步:用matlab軟件計(jì)算依次對(duì)每張圖片進(jìn)行“找左邊”，同時(shí)將提取出來的這些圖片的反面“找右邊”，如003a、009b等圖片，并比較它們找的左邊與右邊是否相等；若提取出來的圖片的a、b面的邊相等，那么，可以確定滿足找左邊的圖片作為完整圖片的最左側(cè)，相應(yīng)的，滿足找右邊的圖片可以作為完整圖片背面的最右側(cè)；最終的到11張“行首圖片”。

第三步:從第二步提取出來的“行首圖片”中任意選擇11張圖片，根據(jù)他們的特征——“二維行高（x,y）”作為標(biāo)準(zhǔn)，進(jìn)行分類，其次，用這11張圖片的反面來檢驗(yàn)之前的分類，形成了22組圖片，使得分類的結(jié)果更加的精確可靠。

第四步:取上述22組圖片中的其中一組的圖片，運(yùn)用matlab軟件，使這些圖片依次匹配，在進(jìn)行匹配的同時(shí)，也對(duì)這些圖像的反面進(jìn)行匹配，從而提高了匹配的正確率。如:000a與002b匹配時(shí)，需要同時(shí)進(jìn)行000b與002a匹配。

第五步:由于“二維行高”中的x和y有可能會(huì)出現(xiàn)相等的可能，那么，我們需要進(jìn)行人工干預(yù)，對(duì)其進(jìn)行匹配。

第六步:根據(jù)上面的步驟，我們得到了11張行的圖片（22面），再用計(jì)算機(jī)程序?qū)γ恳恍羞M(jìn)行橫向匹配。

第七步:由于有一些行的圖片正反兩面上或下同時(shí)為段落分隔處（即為空白部分，無法用計(jì)算機(jī)進(jìn)行匹配），那么，我們需要進(jìn)行人工干預(yù)，對(duì)其進(jìn)行匹配。

4 模型的評(píng)價(jià)及改進(jìn)

由于文字的多樣性，分割情況的復(fù)雜性，信息的丟失殘缺等諸多原因，文字碎片的復(fù)原是一個(gè)十分困難的過程。但是其完全依靠手工或計(jì)算機(jī)進(jìn)行拼接，不是效率低就是準(zhǔn)確率低，所以兩者必須結(jié)合起來。因此較好的算法應(yīng)該具備以下特點(diǎn):

1.由于“行高”的引入，復(fù)原準(zhǔn)確率得到很大提高；

2.自動(dòng)化程度高，即人工干預(yù)量?。?/p>

3.通用性好，盡可能試用多種分割模式下的碎片。

根據(jù)所給出的算法及其運(yùn)行效果，本文的算法較符合上述三個(gè)特點(diǎn)，所以基本上在復(fù)原2013全國(guó)大學(xué)生數(shù)學(xué)建模賽題A題所提供的數(shù)據(jù)碎紙片的效果較好，其人工干預(yù)只涉及到碎塊的拼接和結(jié)果的校對(duì)這兩個(gè)環(huán)節(jié)上。當(dāng)然碎紙片拼接復(fù)原模型算法上還有以下幾種的改進(jìn)可能:

1.關(guān)聯(lián)度定義的改進(jìn)，基于多種文字分割情況的分析、歸類，盡可能設(shè)計(jì)出反映正確匹配的有效指標(biāo)；將單一指標(biāo)擴(kuò)展成多重指標(biāo)體系，提高指標(biāo)精確度；

2.建立文字、單詞、短語(yǔ)甚至常用語(yǔ)句的樣本庫(kù)，通過程序?qū)⑵礈惤Y(jié)果與標(biāo)準(zhǔn)樣本進(jìn)行對(duì)比，提高正誤判別能力；

3.設(shè)計(jì)一種通用的算法，即使碎片中同時(shí)含有中文、英文以及其他的符號(hào)運(yùn)算，字體字號(hào)不同，也可以在較少的人工干預(yù)情況之下自動(dòng)地將碎片拼接成完整的圖片；

4.在現(xiàn)實(shí)情況中，需要復(fù)原的不僅是二維的文字信息，還有可能是三維的物體，例考古中的陶瓷碎片。因此我們需要對(duì)三維圖形進(jìn)行新一輪的討論和分析，得到一個(gè)較精確的算法和程序。

［1］羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接［J］. 計(jì)算機(jī)工程與應(yīng)用，2012，48（5）:1-4.

［2］劉金根，吳志鵬.一種基于特征區(qū)域分割的圖像拼接算法［J］.西安電子科技大學(xué)學(xué)報(bào)，2002,29（6）:769-770.

［3］朱延娟，周來水.二維非規(guī)則碎片的匹配算法［J］. 計(jì)算機(jī)工程，2007,33（24）:290-294.