規(guī)則碎片拼接算法

李 猛，劉家保

(1.合肥市統(tǒng)計(jì)局，合肥230071;2.安徽新華學(xué)院 公共課教學(xué)部，合肥230088)

如今世界上紙質(zhì)碎片的拼接技術(shù)分人工和計(jì)算機(jī)自動(dòng)拼接兩種。由人工完成的拼接復(fù)原的正確率高，但效率非常低，當(dāng)碎片數(shù)量多時(shí)，人工拼接難以在短時(shí)間里完成。隨著計(jì)算機(jī)技術(shù)的發(fā)展，現(xiàn)代碎片拼接研究方向主要集中在計(jì)算機(jī)自動(dòng)拼接［1－6］，但在處理碎片拼接時(shí)，當(dāng)今主流是采用形狀匹配、邊緣比較、數(shù)據(jù)庫(kù)匹配等技術(shù)，對(duì)硬件運(yùn)算能力和儲(chǔ)存能力都有著極高的要求。而很多情況下，并不需要處理太過(guò)復(fù)雜的碎片，如一般辦公室通常采用的是碎紙機(jī)碎紙，所得的碎片形狀比較規(guī)則，拼接不需要考慮形狀匹配等因素，因此使用主流的對(duì)高硬件運(yùn)行速度和存儲(chǔ)空間消耗的算法就比較浪費(fèi)。因此，以文件碎片邊緣的黑白色匹配程度為依據(jù)，結(jié)合動(dòng)態(tài)規(guī)劃［8］理論，以普通家用電腦為硬件基礎(chǔ)，提出了一種簡(jiǎn)潔有效的規(guī)則碎片自動(dòng)拼接算法。

1 相關(guān)設(shè)定與定義

1.1 設(shè) 定

(1)無(wú)切割誤差。碎紙機(jī)在切割文件時(shí)沒(méi)有誤差，切出來(lái)的碎片中文字方向平行于上下邊緣，同一文件碎片大小完全一致;

(2)無(wú)打印誤差。紙質(zhì)文件按同一標(biāo)準(zhǔn)打印出來(lái)，行號(hào)、字號(hào)、行間矩完全一致，中文字體完全一致，英文字體完全一致;

(3)無(wú)物理誤差。碎片圖片無(wú)污跡，無(wú)毛邊等干擾情況;

(4)論文中使用的誤差為根據(jù)拼接實(shí)驗(yàn)中碎片的數(shù)據(jù)選定，可根據(jù)實(shí)際碎片數(shù)據(jù)進(jìn)行更改。

1.2 定 義

(1)兩文件碎片之間的匹配率［5］。讀取每一個(gè)碎紙片圖片文件為數(shù)據(jù)矩陣，選取適當(dāng)閥值，將其用二值法化為0－1矩陣。任取碎紙片i和碎紙片j進(jìn)行比較，記:

(2)已分組文件之間的行匹配率。在以將碎片文件分組排序的基礎(chǔ)上，任取第i組和第j組進(jìn)行比較，記

(3)碎片文字行高估計(jì)值。碎片所在行的每行文字所占碎片文件象素行數(shù)的最大值與最小值的估計(jì)值，簡(jiǎn)稱為文字行高估計(jì)值。根據(jù)一碎片包含文字行數(shù)，每一碎片的行高估計(jì)值約有4～6個(gè)。如圖1中碎片000.bmp 的行高估計(jì)值可記為 0，26，56，96，124，165。

圖1 待拼接碎片000.bmp

2 碎片的按行分組

此時(shí)，仍可以碎片之間的匹配率為標(biāo)準(zhǔn)，利用貪心法［8］逐行拼接后再按行匹配率進(jìn)行排序。但通過(guò)對(duì)中國(guó)2013年數(shù)學(xué)建模競(jìng)賽B題附件3提供碎片實(shí)際拼接結(jié)果發(fā)現(xiàn)，直接拼接誤差非常大，正確率僅為30.81%。因此，在此采用先按行分組，再進(jìn)行拼接的方法來(lái)降低誤差。

在假定中，碎片文件的四邊平行于原紙張相應(yīng)邊緣，且其中文字是按同一標(biāo)準(zhǔn)逐行打印而成的。所以從理論上，同行碎片文件的同行文字的行高與行間距都應(yīng)該是對(duì)應(yīng)相等的(圖2)。

從圖2中可以看出000.bmp，007.bmp，045.bmp行間矩基本相同，因此可以歸成一類。且因?yàn)楣P劃、字形、灰度等情況可能會(huì)產(chǎn)生部分誤差，通過(guò)圖形對(duì)比，可把誤差額度設(shè)置為(－5，5)。

分組算法:

第1步，按每一文件第一行象素全為255，和有多行不為255分類，為避免特殊情況產(chǎn)生誤差，僅有前面連續(xù)2行以內(nèi)不全為255的情況單獨(dú)歸為一類。

第2步，將按順序選擇一個(gè)未分組文件單獨(dú)分為一組，提取每一行漢字所占象素行數(shù)的最小值和最大值，可得到3對(duì)數(shù)據(jù)。

第3步，以上述3對(duì)數(shù)據(jù)為基礎(chǔ)，設(shè)為上述碎片文件的初始文字行高估計(jì)值，以同一類中其它文件的相應(yīng)數(shù)據(jù)進(jìn)行比較，選取方差小于閥值k的文件，將其加入001文件所在組，并將碎片文字行高估計(jì)值改為已加入該組的所有碎片文件相應(yīng)數(shù)據(jù)的平均值。k的值根據(jù)實(shí)際需要選定，如根據(jù)允許誤差范圍(－5，5)，則可取閥值k=6×25=150。

第4步，以新得到的估計(jì)值為標(biāo)準(zhǔn)，重復(fù)步驟3，篩選出所有符合條件的文件，歸為一組。

第5步，重復(fù)步驟2、3、4，直至完成全部分組。

第6步，根據(jù)整張紙片切割的行數(shù)m和列數(shù)n，對(duì)以上各組數(shù)據(jù)進(jìn)行現(xiàn)次處理，按每組包含文件個(gè)數(shù)從大到小排列，以前11為基礎(chǔ)。包含文件個(gè)數(shù)超過(guò)列數(shù)n的，以所在組每一碎片文件相應(yīng)數(shù)據(jù)與碎片文字行高估計(jì)值比較，選出與標(biāo)準(zhǔn)差最小的n個(gè)文件，其余文件從組中移出。小于列數(shù)n的，以該組的碎片文字行高估計(jì)值為基礎(chǔ)，將未分組文件和包含文件個(gè)數(shù)不超過(guò)3個(gè)的組包含文件依次比較，選出方差最小的若干個(gè)文件加入組中，補(bǔ)足n個(gè)。

圖2 待拼接碎片示例圖

以圖2 中000.bmp，001.bmp，007.bmp，045.bmp 4個(gè)文件為例。

(1)000.bmp、007.bmp、045.bmp 同屬于多行不全為255 的一類。

(2)按編號(hào)順序從000.bmp開(kāi)始分組處理，此時(shí)分組數(shù)為0，所以001不屬于任何一組，將其單獨(dú)分為1組{000.bmp}。提取碎片文件000.bmp每一行漢字所占象素行數(shù)的最小值和最大值，得到一組數(shù)據(jù)1、26、57、96、125、165，將其設(shè)為組{000.bmp}對(duì)應(yīng)碎片所在行的相應(yīng)數(shù)據(jù)的初始估計(jì)值。經(jīng)檢測(cè)，001.bmp屬于第一行象素值全為255這一類別，此時(shí)，沒(méi)有與其同一組的碎片文件，因此001.bmp單獨(dú)分為一組{001.bmp}。

(3)經(jīng)檢測(cè)007.bmp每一行漢字所占象素行數(shù)的最小值和最大值為1、26、59、96、125、165，與初始估計(jì)值相比較，方差為4小于閥值k，所以將007.bmp并入組{000.bmp}，取新的碎片文字行高估計(jì)值為00.bmp和001.bmp 相應(yīng)數(shù)據(jù)的平均值，1、26、58、96、125、165。

(4)依次將045.bmp 相應(yīng)數(shù)據(jù)與之比較，最終將文件分為兩組{000.bmp，001.bmp，045.bmp}和{001.bmp}。

每組內(nèi)碎紙片的排序?yàn)?以分組數(shù)據(jù)為基礎(chǔ)，對(duì)每一組文件，以同組文件之間的匹配率為標(biāo)準(zhǔn)，應(yīng)用貪心法，將同組碎片文件排序。對(duì)已排序數(shù)據(jù)，以不同組文件之間的組匹配率為基礎(chǔ)，應(yīng)用貪心法，將各組進(jìn)行排序。

3 人工較正和計(jì)算機(jī)輔助人工較正

在碎片過(guò)多的情況下，計(jì)算機(jī)拼接可能會(huì)由于打印、筆劃、字型的不同等原因產(chǎn)生一定的誤差，此時(shí)就需要通過(guò)手工對(duì)已處理結(jié)果進(jìn)行較正。但受視力、思考速度等身體條件影響，在需要較正碎片量較大的情況下，人工較正可能會(huì)產(chǎn)生速度較慢、有一定誤差等問(wèn)題。

對(duì)此，在人工較正過(guò)程中，仍可以使用計(jì)算機(jī)進(jìn)行輔助，用以加快較正速度，減少較正工作量。在處理過(guò)程中，可以采用遍歷法，仍以碎片之間的匹配律為基礎(chǔ)，讓計(jì)算機(jī)按順序推薦出與錯(cuò)拼的文件最匹配的5個(gè)(根據(jù)需要可自由選擇數(shù)目)文件，便于快速較正誤差。

4 拼接實(shí)驗(yàn)

試驗(yàn)以中國(guó)2013年數(shù)學(xué)建模競(jìng)賽B題提供文件為實(shí)驗(yàn)對(duì)象，使用MATLAB程序作為編程工具［7］。

4.1 僅縱向切割的碎片拼接

此時(shí)所有碎片均為一行，跳過(guò)行分組階段，直接應(yīng)用貪心法進(jìn)行排序，即可直接得到正確順序。此種情況下因計(jì)算匹配率時(shí)相應(yīng)象素點(diǎn)數(shù)量較大，因而所得匹配率數(shù)據(jù)值可信度高，拼接結(jié)果錯(cuò)誤率極小，一般不需要人工較正。

4.2 縱橫切碎片拼接的問(wèn)題

第1步，把所有碎片按前面的分組算法分組。以附件3為例，得表1:

表1 分組后得到的碎片組合

此處根據(jù)實(shí)際情況可適當(dāng)調(diào)整閥值、誤差區(qū)域。

第2步，對(duì)每一組分別排序，得表2:

表2 每一分組內(nèi)部的碎片排序結(jié)果

第3步，人工較正?？v橫切割的碎片在計(jì)算匹配率時(shí)進(jìn)行比較的象素點(diǎn)較少，因此出錯(cuò)的可能性相對(duì)僅縱切的情況較高，偶爾需要進(jìn)行人工較正。

通過(guò)上述結(jié)果，觀察可得，上述結(jié)果中094號(hào)碎片與201號(hào)碎片不在正確的位置上，因?yàn)橹挥袃蓚€(gè)錯(cuò)誤碎片，將094和201交換所在組重新排序即可。

若錯(cuò)誤碎片也可采用計(jì)算機(jī)輔助，利用程序依次將094以外的其它碎片遍歷一遍，得到與094匹配率最高的5個(gè)文件034、058、090、149、164，人工對(duì)比發(fā)現(xiàn)034號(hào)碎片與094號(hào)拼接最符合要求。同理可找到與201最適碎片005。

第4步，行間排序。利用兩行之間的行匹配率，應(yīng)用貪心法進(jìn)行排序，得到表3正確順序。

表3 附件3碎片附原順序

5 傾斜切割的理論算法

從理論上來(lái)說(shuō)，碎紙機(jī)切割縱橫切割相結(jié)合，但實(shí)際上由于紙張變形、文件放置、機(jī)器精度等問(wèn)題，很難做到標(biāo)準(zhǔn)的垂直和平行切割，在實(shí)際情況中難免會(huì)出現(xiàn)一些誤差。這時(shí)仍可根據(jù)碎片文件之間的匹配率進(jìn)行拼接，但如前所述，直接拼接誤差太大所有仍然要先考慮分組。以下僅針對(duì)文件產(chǎn)生一定傾斜角的情況從理論上提出分組，其余情況可依此拓展。針對(duì)以下3個(gè)碎片文件(圖3):

圖3 傾斜切割所得到的文件碎片

現(xiàn)采用兩種思路進(jìn)行行分組:

(1)對(duì)碎片一分析，得到圖片傾斜角大小，由此判斷出與文字方向平行的空白行位置與相應(yīng)行數(shù)。文字傾斜時(shí)因其上下兩行文字高度始終改變，縱橫切割拼接方法中按一行文字高度分組的方法就不適用了。這里采用相連接的兩碎片左右文字的銜接度來(lái)分組。由于文字傾斜時(shí)一行文字所占最大值與最小值始終改變，因此采用按列抽樣的方法。如對(duì)上面第一個(gè)碎片，抽取最左側(cè)n列，取一行文字所占象素位置，逐列取其最大值和最小值(為避免誤差，對(duì)一行文字最高處明顯與前后不符的列舍去)，分別取其平均值，設(shè)為碎片文件左側(cè)行高參數(shù)的估計(jì)值。同理，可得到碎片文件右側(cè)參數(shù)的估計(jì)值。在允許一定的誤差情況下，根據(jù)前一文件最右側(cè)參數(shù)的估計(jì)值和最右側(cè)參數(shù)估計(jì)值的比較進(jìn)行行分組即可。

(2)在掃描碎片文件時(shí)通過(guò)手動(dòng)，將碎片中文字方向恢復(fù)為水平，如上面碎片文件可掃描為圖4:

圖4 將文字方向調(diào)為水平后得到的文件碎片

此時(shí)可將文件按斜行分組，且每?jī)蓚€(gè)碎片要以如下兩個(gè)標(biāo)準(zhǔn)進(jìn)行拼接:兩個(gè)碎片文件之間的匹配律;前一碎片文件最右側(cè)文字行高與后一文件最左側(cè)文字行高相匹配。

［1］羅智中.基于線段掃描的碎紙片邊界檢測(cè)算法研究［J］.儀器儀表學(xué)報(bào)，2011，32(2):289-294

［2］王欣潔.基于灰度矩陣的中文碎紙片的拼接復(fù)原算法［J］.智能計(jì)算機(jī)與應(yīng)用，2013，3(6):95-97

［3］徐雅平，王運(yùn)生.碎紙片的拼接復(fù)原［J］.上海商學(xué)院學(xué)報(bào)，2013，4(5):79-84

［4］李曉霞，高志鵬，張蕊倚，等.關(guān)于中英文的碎紙片拼接復(fù)原問(wèn)題研究［J］.運(yùn)城學(xué)報(bào)2013，31(5):12-15

［5］楊雯雯，陶佳琪，鄭路通，等.單頁(yè)單面漢字縱橫切碎片拼接復(fù)原算法［J］.運(yùn)城學(xué)報(bào)2013，31(5):16-20

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

［7］王沫然.MATLAB6.0與科學(xué)計(jì)算［M］.北京:電子工業(yè)出版社，2011

［8］THOMASH C，CHARLESE L，RONALD L R.Introduction to Algorithms算法導(dǎo)論［M］.北京:機(jī)械工業(yè)出版社，2010