基于數字圖像的碎紙復原模型與算法
——2013年全國大學生數學建模B題碎紙片的拼接復原問題

劉 鐵

(安康學院 數學與統計系 數學與應用數學研究所，陜西 安康 725000)

?

基于數字圖像的碎紙復原模型與算法
——2013年全國大學生數學建模B題碎紙片的拼接復原問題

劉 鐵

(安康學院 數學與統計系 數學與應用數學研究所，陜西 安康 725000)

傳統的拼接復原工作需由人工完成，準確率較高，但效率很低。針對該問題，借助數字圖像處理技術，建立了關于圖片匹配度函數的優化模型，依據窮舉思想設計了求解算法，可大幅提高復原效率，但在處理復雜問題時，準確性有所下降，需要一定的人工介入。通過對復原后圖片的驗證結果可知，碎紙片復原拼接模型具有可行性。

數字圖像;碎紙復原;匹配度

數字圖像的拼接復原技術在生產、生活中有著廣泛的應用[1-12]。碎紙片的拼接復原問題有重要的實際研究價值。傳統上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數量巨大時，人工拼接很難在短時間內完成。隨著計算機技術的發展，人們試圖開發碎紙片的自動拼接技術以提高效率。 本文針對2013年全國大學生數學建模競賽中碎紙片的拼接復原問題進行研究[13]。碎紙片拼接復原問題包括以下內容：

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

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

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

1 匹配度定義

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

其中：ni為配對成功的行數；n為矩陣總行數。如此形成匹配度矩陣Dm×m,其中m為圖片張數。顯然該矩陣為非對稱矩陣。

2 問題1的模型與算法

以兩條碎片之間的匹配度取倒數作為距離,將問題轉化為TSP問題[15]。 需要說明的是，為了避免出現分母為零的情形,在取倒數前應統一加上機器零——eps。設

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

編制LINGO程序求解模型，得到最優解。

為提高求解效率，可先提取各矩陣左側頁邊空白寬度信息，即編程查找矩陣左側分量均為1的列向量列數，根據左側空白來確定最左邊的圖片，將它作為起點求一個最佳巡回路線。 附件1中中文頁僅有的008圖左側頁邊空白列數非零，即為起點，其最優結果見表1。附件2中英文頁的003圖為起點，其最優結果見表2。

表1 附件1中文復位次序表

表2 附件2英文復位次序表

3 問題2的模型與算法

問題1僅有縱切，每一條紙片的長度較大，使得可提取的紙邊信息充足，不需要人工干預，復原率可以接近或達到100%。 但問題2不僅對紙張進行縱切還進行橫切，將一張完整的紙張切割為11×19張小紙片。 如果直接應用問題1中的方法，一方面圖片塊數大幅增加，TSP問題無法處理209個點的問題；另一方面，每幅圖邊緣信息量也大幅度減少，極易出現錯配， 需要適當的人工干預。

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

此時的ni為配對成功的列數,n為矩陣總列數。之后的步驟與問題1相同。附件3中的中文頁結果見表3。

表3 附件3中文復位次序表

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

圖1 英文的復雜性示意圖

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

4 問題3的模型與算法

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

本不對應的兩張碎紙片兩面的拼接復原情況均好的情況只可能是個別案例，所以可將碎紙片兩面邊緣匹配度之和作為評判兩張圖片是否匹配的標準,建立邊緣匹配度之和矩陣D′。為進一步提升復原率,通過提取每張圖片左右邊緣空白寬度信息發現，編號為i的碎紙片a面右端(或左端)與b面左端(或右端)邊緣全是白色的圖片一共有22張。考慮到所有的碎紙片應被拼接為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張碎紙片應是原文件紙張的兩端。 為了方便，可以選擇這22張碎紙片作為開端匹配對應的紙片。下面的過程與問題2類似， 結果見表5、6。

表5 附件5雙面英文正面的復位次序表

表6 附件5雙面英文反面的復位次序表

續表

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

5 結束語

通過對復原后圖片的驗證結果發現，本文中的碎紙片復原拼接模型對于本題有很高的可行性。 對于中、英文兩種情況，按照從問題1到問題3、中文到英文的順序依次改進模型與算法，發現中文需要人工干預較少、英文需要人工干預較多的規律，說明不同語言有各自的特性。

對于計算機錯誤匹配的結果，在問題2與問題3中給出了詳細的人工干預的時機與方法，通過檢驗結果說明人工干預是必需的。

本文模型適用于打印文件之類的平面規則碎片的拼接復原問題,且不涉及碎片殘缺不全的情形。對于不規則的立體殘片，例如考古挖掘出的不規則文物或者鈔票殘片等，還需要開發更好的改進模型來進行研究。

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

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

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

[4] 陳黎黎 ,國紅軍.基于文檔內容的碎紙拼接技術[J].衡水學院學報,2014,16(4):34-37.

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

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

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

[8] 王書民,張愛武,崔營營,等.基于無人飛艇數字攝影測量系統及航拍序列圖像拼接[J].測繪科學,2010,35(4):81-83.

[9] 郭丙軒,王文進,劉 波,等.一種基于網格的數碼相機數字化圖像糾正拼接算法[J].測繪科學,2007,32(6):143-145.

[10]潘榮江,孟祥旭,屠長河.一種基于LCS 的物體碎片自動拼接方法[J].計算機學報,2005,28(3):350-156.

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

[12]牛剛.基于特征像素統計的圖像相關匹配算法[EB/OL].[2013-09-13].http://www.docin.com/p-87674921.html.

[13]CVMCM.2013年高教社杯全國大學生數學建模競賽賽題[EB/OL].[2014-09-25].http://www.mcm.edu.cn/problem/2013/2013.html.

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

[15]司守奎、孫璽菁.數學建模算法與應用[M].北京：國防工業出版社，2011:109-152.

[16]袁新生,邵大宏,郁時煉.LINGO和Excel在數學建模中的應用[M].北京：科學出版社,2007:55-105.

(責任編輯 楊黎麗)

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 基金項目：國家自然科學基金資助項目(61152003)

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

基于數字圖像的碎紙復原模型與算法 ——2013年全國大學生數學建模B題碎紙片的拼接復原問題[J].重慶理工大學學報：自然科學版，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