劉 鐵

(安康學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)系 數(shù)學(xué)與應(yīng)用數(shù)學(xué)研究所，陜西 安康 725000)

?

基于數(shù)字圖像的碎紙復(fù)原模型與算法
——2013年全國(guó)大學(xué)生數(shù)學(xué)建模B題碎紙片的拼接復(fù)原問(wèn)題

劉 鐵

(安康學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)系 數(shù)學(xué)與應(yīng)用數(shù)學(xué)研究所，陜西 安康 725000)

傳統(tǒng)的拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。針對(duì)該問(wèn)題，借助數(shù)字圖像處理技術(shù)，建立了關(guān)于圖片匹配度函數(shù)的優(yōu)化模型，依據(jù)窮舉思想設(shè)計(jì)了求解算法，可大幅提高復(fù)原效率，但在處理復(fù)雜問(wèn)題時(shí)，準(zhǔn)確性有所下降，需要一定的人工介入。通過(guò)對(duì)復(fù)原后圖片的驗(yàn)證結(jié)果可知，碎紙片復(fù)原拼接模型具有可行性。

數(shù)字圖像;碎紙復(fù)原;匹配度

數(shù)字圖像的拼接復(fù)原技術(shù)在生產(chǎn)、生活中有著廣泛的應(yīng)用[1-12]。碎紙片的拼接復(fù)原問(wèn)題有重要的實(shí)際研究?jī)r(jià)值。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大時(shí)，人工拼接很難在短時(shí)間內(nèi)完成。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)碎紙片的自動(dòng)拼接技術(shù)以提高效率。 本文針對(duì)2013年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽中碎紙片的拼接復(fù)原問(wèn)題進(jìn)行研究[13]。碎紙片拼接復(fù)原問(wèn)題包括以下內(nèi)容：

1) 對(duì)于給定的來(lái)自同一頁(yè)文字文件(單面打印)的碎紙機(jī)破碎紙片(僅縱切為19條)，建立碎紙片拼接復(fù)原模型和算法，并針對(duì)題目中附件1(中文縱切圖片)、附件2(英文縱切圖片)給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原；

2) 對(duì)于碎紙機(jī)既縱切又橫切的情形(切為11×19，共209塊)，設(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對(duì)題目中附件3(中文縱、橫切圖片)、附件4(英文縱、橫切圖片)給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原；

3) 解決雙面打印文件的碎紙片拼接復(fù)原問(wèn)題，并對(duì)題目中附件5(英文雙面縱、橫切圖片)給出的一頁(yè)英文印刷文字雙面打印文件的碎片數(shù)據(jù)進(jìn)行拼接。

1 匹配度定義

首先，借助Matlab圖像處理函數(shù)imread讀取題中BMP圖片為灰度圖矩陣。其次，再利用函數(shù)im2bw將圖片轉(zhuǎn)化為二值圖矩陣，0和1分別表示黑色與白色[14]。對(duì)矩陣進(jìn)行兩兩比對(duì),以i矩陣最右邊一列與j矩陣最左邊一列進(jìn)行配對(duì),定義匹配度函數(shù)：

其中：ni為配對(duì)成功的行數(shù)；n為矩陣總行數(shù)。如此形成匹配度矩陣Dm×m,其中m為圖片張數(shù)。顯然該矩陣為非對(duì)稱(chēng)矩陣。

2 問(wèn)題1的模型與算法

以?xún)蓷l碎片之間的匹配度取倒數(shù)作為距離,將問(wèn)題轉(zhuǎn)化為T(mén)SP問(wèn)題[15]。 需要說(shuō)明的是，為了避免出現(xiàn)分母為零的情形,在取倒數(shù)前應(yīng)統(tǒng)一加上機(jī)器零——eps。設(shè)

輔助變量ui可以反映圖片連接的前后次序，取值越小越先連接。 采用破圈法[16]建立如下優(yōu)化模型：

編制LINGO程序求解模型，得到最優(yōu)解。

為提高求解效率，可先提取各矩陣左側(cè)頁(yè)邊空白寬度信息，即編程查找矩陣左側(cè)分量均為1的列向量列數(shù)，根據(jù)左側(cè)空白來(lái)確定最左邊的圖片，將它作為起點(diǎn)求一個(gè)最佳巡回路線(xiàn)。 附件1中中文頁(yè)僅有的008圖左側(cè)頁(yè)邊空白列數(shù)非零，即為起點(diǎn)，其最優(yōu)結(jié)果見(jiàn)表1。附件2中英文頁(yè)的003圖為起點(diǎn)，其最優(yōu)結(jié)果見(jiàn)表2。

表1 附件1中文復(fù)位次序表

表2 附件2英文復(fù)位次序表

3 問(wèn)題2的模型與算法

問(wèn)題1僅有縱切，每一條紙片的長(zhǎng)度較大，使得可提取的紙邊信息充足，不需要人工干預(yù)，復(fù)原率可以接近或達(dá)到100%。 但問(wèn)題2不僅對(duì)紙張進(jìn)行縱切還進(jìn)行橫切，將一張完整的紙張切割為11×19張小紙片。 如果直接應(yīng)用問(wèn)題1中的方法，一方面圖片塊數(shù)大幅增加，TSP問(wèn)題無(wú)法處理209個(gè)點(diǎn)的問(wèn)題；另一方面，每幅圖邊緣信息量也大幅度減少，極易出現(xiàn)錯(cuò)配， 需要適當(dāng)?shù)娜斯じ深A(yù)。

利用Matlab軟件編程提取每張圖片的上下頁(yè)邊空白寬度信息，即查找矩陣上下各分量均為1的行向量行數(shù)記為Ui和Li，分別利用上邊空白寬度數(shù)據(jù)Ui和下邊空白寬度數(shù)據(jù)Li做聚類(lèi)分析。對(duì)于類(lèi)中數(shù)據(jù)多于19的組取交集,不足19的類(lèi)就近取類(lèi)的并集。 也可加入人工甄別,初步獲得各行的大致分類(lèi)。在得到行聚類(lèi)結(jié)果后，利用類(lèi)似于問(wèn)題1中的方法完成每行碎片的排序工作。期間會(huì)出現(xiàn)不少錯(cuò)配情況，此時(shí)將配對(duì)正確的片段記下，然后除去它們，再將剩余的圖片用TSP法尋優(yōu),直到將此行排定,再排其他行。 最后，對(duì)排序后的行作縱向排序。方法與問(wèn)題1中類(lèi)似，只不過(guò)先根據(jù)上邊空白寬度信息確定第1行,以i行矩陣的末行向量與j行矩陣的首行向量做比對(duì),匹配度公式為

此時(shí)的ni為配對(duì)成功的列數(shù),n為矩陣總列數(shù)。之后的步驟與問(wèn)題1相同。附件3中的中文頁(yè)結(jié)果見(jiàn)表3。

表3 附件3中文復(fù)位次序表

如圖1所示,相比中文，英文的情形要復(fù)雜得多。英文中除了存在一些“y”，“b”之類(lèi)的字母與行聚類(lèi)強(qiáng)相關(guān)以外，還有“e”和“a”之類(lèi)無(wú)法判定所屬行的干擾字母，妨礙對(duì)同行信息的判定，聚類(lèi)效果較差，需要大量的人工判定。另外，需要把這些無(wú)法判定所屬行的圖片與最容易判定的行(不足19片)一起做行排序。將使用的圖片剔除后，將剩余圖片與其他行一起再排序，以逐步減少干擾圖片的數(shù)量。其余方法和過(guò)程與中文類(lèi)似。 附件4中英文頁(yè)求解結(jié)果見(jiàn)表4。

圖1 英文的復(fù)雜性示意圖

第1行第2行第3行第4行第5行第6行第7行第8行第9行第10行第11行191201086019159020208070132171081075148051194139041021084181042077011170107093001108007060095066128154196029141129116049014069205200190198040088063136061068167010131184094158121138073119174163157052002113186126153036033137166074125104164098105053207142195188145140180078024155038135168008111083193064103117114123015062047144134087106091150176120076169172206055089004080005182175043054156003018048149101059151085199192096130056072032026058022050045133023034035012204100092057160173118099013016177065006030202187079189122110009124039017037071097161162090025183000067028046165203179197185027152102147146127082031143112109178044115

4 問(wèn)題3的模型與算法

問(wèn)題3是問(wèn)題2的繼續(xù)，基本解決方法與問(wèn)題2的方法相同，不同的是，這里需要充分利用雙面文本的特征信息。 一般認(rèn)為，雙面信息使得任務(wù)量不止增大一倍,干擾信息也更多。 以紙片i與j為例，匹配方式可能為：

本不對(duì)應(yīng)的兩張碎紙片兩面的拼接復(fù)原情況均好的情況只可能是個(gè)別案例，所以可將碎紙片兩面邊緣匹配度之和作為評(píng)判兩張圖片是否匹配的標(biāo)準(zhǔn),建立邊緣匹配度之和矩陣D′。為進(jìn)一步提升復(fù)原率,通過(guò)提取每張圖片左右邊緣空白寬度信息發(fā)現(xiàn)，編號(hào)為i的碎紙片a面右端(或左端)與b面左端(或右端)邊緣全是白色的圖片一共有22張?？紤]到所有的碎紙片應(yīng)被拼接為11行，而左右兩端乘以2就是22，所以136，005，143，083，090，013，035，172，105，009，054，078，089，186，199，088，114，146，165，003，023，099這22張碎紙片應(yīng)是原文件紙張的兩端。 為了方便，可以選擇這22張碎紙片作為開(kāi)端匹配對(duì)應(yīng)的紙片。下面的過(guò)程與問(wèn)題2類(lèi)似， 結(jié)果見(jiàn)表5、6。

表5 附件5雙面英文正面的復(fù)位次序表

表6 附件5雙面英文反面的復(fù)位次序表

續(xù)表

第1行第2行第3行第4行第5行第6行第7行第8行第9行第10行第11行110b124a094a034b166a154a016a075a074a071a113b174a192b098b156b115a197b019a063a032b033a134b183a025a121b206a065a158b092a067b069b119b104b150b044b038b173a191b058b190a046b004b160a006b155b178b030b194a037a207b050b168b077b095b123b140b076a042a169a180b116a201b157b148a051a109b125b036b084a161b149a179a031b128b085a048b096a111a010a153b011a107b184a171a195b007a133b043b078a089b186a199a088a114b146b165a003a023a099b

5 結(jié)束語(yǔ)

通過(guò)對(duì)復(fù)原后圖片的驗(yàn)證結(jié)果發(fā)現(xiàn)，本文中的碎紙片復(fù)原拼接模型對(duì)于本題有很高的可行性。 對(duì)于中、英文兩種情況，按照從問(wèn)題1到問(wèn)題3、中文到英文的順序依次改進(jìn)模型與算法，發(fā)現(xiàn)中文需要人工干預(yù)較少、英文需要人工干預(yù)較多的規(guī)律，說(shuō)明不同語(yǔ)言有各自的特性。

對(duì)于計(jì)算機(jī)錯(cuò)誤匹配的結(jié)果，在問(wèn)題2與問(wèn)題3中給出了詳細(xì)的人工干預(yù)的時(shí)機(jī)與方法，通過(guò)檢驗(yàn)結(jié)果說(shuō)明人工干預(yù)是必需的。

本文模型適用于打印文件之類(lèi)的平面規(guī)則碎片的拼接復(fù)原問(wèn)題,且不涉及碎片殘缺不全的情形。對(duì)于不規(guī)則的立體殘片，例如考古挖掘出的不規(guī)則文物或者鈔票殘片等，還需要開(kāi)發(fā)更好的改進(jìn)模型來(lái)進(jìn)行研究。

[1] 戚文靜,趙敬.基于數(shù)字全息的圖像置亂的研究[J].山東大學(xué)學(xué)報(bào)：理學(xué)版,2005,40(5):93-96.

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

[3] 潘斌，郭小明，陳明明，等.規(guī)則切割碎紙片的復(fù)原[J].遼寧石油化工大學(xué)學(xué)報(bào),2014,34(5):70-73.

[4] 陳黎黎 ,國(guó)紅軍.基于文檔內(nèi)容的碎紙拼接技術(shù)[J].衡水學(xué)院學(xué)報(bào),2014,16(4):34-37.

[5] 王威娜,史彥麗.無(wú)重疊的文檔碎片拼接方法[J].吉 林化工學(xué)院學(xué)報(bào),2014,31(3):85-87.

[6] 林川，張學(xué)新.一種縱切碎紙片拼接算法[J].湖北工程學(xué)院學(xué)報(bào),2014,34(3):37-40.

[7] 樊慶文,王小龍,侯力,等.基于等距序列圖像的快速拼接技術(shù)[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版,2005,37(1):139-142.

[8] 王書(shū)民,張愛(ài)武,崔營(yíng)營(yíng),等.基于無(wú)人飛艇數(shù)字?jǐn)z影測(cè)量系統(tǒng)及航拍序列圖像拼接[J].測(cè)繪科學(xué),2010,35(4):81-83.

[9] 郭丙軒,王文進(jìn),劉 波,等.一種基于網(wǎng)格的數(shù)碼相機(jī)數(shù)字化圖像糾正拼接算法[J].測(cè)繪科學(xué),2007,32(6):143-145.

[10]潘榮江,孟祥旭,屠長(zhǎng)河.一種基于LCS 的物體碎片自動(dòng)拼接方法[J].計(jì)算機(jī)學(xué)報(bào),2005,28(3):350-156.

[11]王晨，杜彥，杜建洪.基于塊缺失圖像修復(fù)技術(shù)的研究與應(yīng)用[J].計(jì)算機(jī)工程,2006,32(11):206-208.

[12]牛剛.基于特征像素統(tǒng)計(jì)的圖像相關(guān)匹配算法[EB/OL].[2013-09-13].http://www.docin.com/p-87674921.html.

[13]CVMCM.2013年高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽賽題[EB/OL].[2014-09-25].http://www.mcm.edu.cn/problem/2013/2013.html.

[14]章毓晉.圖像處理[M].北京:清華大學(xué)出版社，2012:21-43.

[15]司守奎、孫璽菁.數(shù)學(xué)建模算法與應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2011:109-152.

[16]袁新生,邵大宏,郁時(shí)煉.LINGO和Excel在數(shù)學(xué)建模中的應(yīng)用[M].北京：科學(xué)出版社,2007:55-105.

(責(zé)任編輯 楊黎麗)

Mathematical Model and Algorithm Design on Reconstruction of Shredded Document Based on Digital Image：National College Students’ Mathematical Modeling

LIU Tie

(Institute of Mathematics and Applied Mathematics, Department of Mathematics and Statistics, Ankang University, Ankang 725000, China)

Traditionally, restoration works need to be done by hand, which has high accurately, but is inefficiently. With the aid of digital image processing technology, optimization model on matched-degree of image was established, and algorithm based on exhaustive thought was proposed. It can significantly improve the recovery efficiency, but when dealing with complex problems, the accuracy of solutions may be severely degraded, and artificial intervention is required.

digital Image; reconstruction of shredded document; matched-degree

2014-10-23 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61152003)

劉鐵(1978—)，男，黑龍江齊齊哈爾人，碩士，講師，主要從事數(shù)學(xué)建模、微分方程、優(yōu)化理論研究。

基于數(shù)字圖像的碎紙復(fù)原模型與算法 ——2013年全國(guó)大學(xué)生數(shù)學(xué)建模B題碎紙片的拼接復(fù)原問(wèn)題[J].重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2015(3):83-88.

format：LIU Tie.Mathematical Model and Algorithm Design on Reconstruction of Shredded Document Based on Digital Image： Reconstruction of Shredded Papers of Section B in 2013National College Students’ Mathematical Modeling [J].Journal of Chongqing University of Technology:Natural Science,2015(3):83-88.

10.3969/j.issn.1674-8425(z).2015.03.016

TP393; O221

A

1674-8425(2015)03-0083-06