碎紙片拼接復原的數學模型

【摘要】本文對碎片的拼接復原問題，建立了碎紙片拼接模型， 編寫matlab程序，利用人機交互指令實現碎片的快速拼接.對2013年“高教社杯”全國大學生數學建模競賽的B題中所給11x19個碎片文件進行拼接.

【關鍵詞】碎片拼接模型；matlab；灰度值矩陣；Kmeans聚類；人機交互

一 、研究背景及意義

近年來，大量政府機關、企事業單位采用碎紙機對廢棄文件或失效的機密文件進行破碎，這種破碎方法產生的碎片多為規則的.這使得在進行破碎文件的復原拼接時，只能根據文字內容進行匹配，為此，本文考慮應用當前的計算機識別技術開發碎紙片的自動拼接技術，對所有碎片搜索和篩選，尋找能夠在某種指標上匹配的碎片進行拼接.提高拼接復原效率，從而大大降低人工工作量和難度.對碎片自動拼接問題的研究， 不僅具有廣闊的應用前景， 而且具有很強的理論意義.

二、圖像碎片預處理

首先，利用matlab圖像處理功能對碎紙片進行圖像預處理.即將碎紙片數字化，轉化為圖片文件的數據.即一個二維數組構成的灰度值矩陣，這個矩陣存儲著一張碎紙片各個像素點的顏色值，其中255表示白色，0表示黑色，圖片中顏色均處在黑白、或黑白之間，圖片數字化后的數字范圍在0～255之間.

三、碎紙片拼接模型的假設

1.假設碎片原文件都存在上、下、左、右的頁邊距，且邊距大于行間距和列間距；

2.假設相鄰碎片間紙張信息的損失可以忽略不計；

3.假設碎紙機是沿平行或垂直于文字的方向對紙張進行切割的.

四、碎紙拼接模型的建立

1. 挑出每行最左邊的圖片：根據圖片的邊緣留有空白部分的特性，挑選出圖片最左邊存在空白部分的圖片作為左邊界的候選圖片.

方法實現：計算圖片左邊距

留白寬度：即可用灰度值矩陣中左端豎列上全為255（即左側完全空白）的連續列數度量， 由matlab檢測出每張圖片的留白寬度.

留白寬度排序：對上面得到的留白寬度進行排列，取排在前面的11張圖片作為拼接過程的起始碎片.

2.圖片按行分類：根據Kmeans聚類算法，對碎片進行按行分類.

分類實現：

①先根據底端一行是否為純空白將 209 幅圖分為下端有純空白行和下端有被截文字兩類.

②對于空白行一類，下端空白行數相同或相近的紙條屬于原文件同一行；

③對于下端有被截文字的一類，下端被截文字高度相同或相近的紙條屬于原文件同 一行.

④分析確定好的最左端圖片的特征，依此為11個聚類中心，利用matlab程序分類.

3.對同行碎片進行拼接

①拼配原則——突變數

5.縱向拼接

①觀察 11 條已拼好的橫切紙條，根據所有紙條的上邊緣特征確定位于原文件頂端的橫切紙條，并以該紙條為起始紙條.

②根據起始紙條的下邊緣灰度值特征，利用上述步奏拼出整張文件.

五、模型的評價與改進

1.模型的優點：模型采用突變數和偏差平方和作為評價函數評定碎片間鄰邊的相關度，高效而且實用.能大大減少人工干預的次數.

2.模型的局限性：由于研究的是碎紙機產生的碎片.該模型只考慮了對多個相同的形狀規則的碎片進行拼接，且當碎片的數量增加且單個碎片的文字覆蓋率越小時，更易產生灰度分布情況相似的碎片，需要進行人工干預的次數會相應增多.

六、結 論

本文對碎紙片的匹配原則和人工干預進行了探討和研究，建立了一個可靠高效的數學模型，利用圖片數字化后數值之間的分布規律和相關度引入突變值和偏差平方和作為評價指標，利用matlab軟件實現快速拼接.并為了提高拼接準確性，巧妙地使用人機交互指令進行人工的檢測干預.

【參考文獻】

[1]何鵬飛，等.基于蟻群優化算法的碎紙拼接.計算機工程與科學，2011，33（7）.

[2] 鄧薇.MATLAB 函數速查手冊.北京：人民郵電出版社，2010.

[3] 宋曉闖.基于灰度和幾何特征的圖像匹配算法研究.萬方數據庫，2013-09-13.