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

朱旭++焦熹++李亦凡

摘要 碎紙機裁出的碎紙片的拼接與復原技術是計算機算法與人工干預的結合，兼顧準確度與效率。碎紙片的拼接與復原算法以采用了全新的向量間歐氏距離的匹配模型，在圖片數據化處理的基礎上，加之針對橫向縱向雙向切割的文檔而編寫的檢測碎片是否在同一行的輔助程序，和針對英文文件的碎片進行行位置標識從而實現“行分類”的應用擴展程序；核心算法和輔助及擴展程序共同構成了碎紙片拼接復原的數學模型。最終對單面中英文單向和雙向實現了裁切的紙張都97%以上的復原，可以說復原模型是成功且有效的。

關鍵詞 碎紙拼接復原 歐氏距離匹配 元胞數組嵌套結構

中圖分類號：G642.3

文獻標識碼：A 文章編號：1002-7661（2015）01-0004-02

破碎紙張文件的拼接修復在司法物證的復原、歷史文件的修復以及軍事情報的獲取的等多個領域都有重要的作用。人工手工拼接的優勢在于準確性高但耗時長，相比之下，計算機算法進行的拼接速度快也有能力實現大量破碎文件的拼接，而計算機為主后期加入人工干預的方法就有更強的實用性。但是已有的計算機拼接方式是基于邊界幾何特征的拼接方法，并不適用于規則裁切的邊緣形狀相同的碎紙片。本文將針對規則裁切的印有文字的紙張進行全自動和半自動的拼接復原模型建立，利用此類紙張特有的規整性，運用圖片信息數據化、矩陣化，使用向量的歐氏距離測定進行匹配還原。

一、建模思路

1.圖片數據化處理

計算機拼接以圖片的數據化和數據匹配為核心，實現量化處理。碎紙片經過掃描后成為圖片形式的數據，通過一定的降噪和對齊處理之后就可以用Matlab以像素為單位轉換成為矩陣，對矩陣的邊界向量進行匹配，最終得到完整有序的整體矩陣，重新生成為圖片。復原的關鍵點在于圖片信息的讀取與處理。利用Matlab可將圖片中的實體信息轉化為矩陣中的數量信息，矩陣的每一個元素分別代表一個像素點上的顏色信息，預設所有的材料均為黑白印刷，暫不考慮由三維向量構成的彩色像素點。Matlab把有黑到白連續變化的灰度值量化為256個灰度級，0-255分別表示亮度從深到淺，對應圖像中的顏色為從黑到白。至此，碎片的拼接問題即轉化為數值矩陣的運算處理問題。

2.核心拼接算法

①將附件中的碎片圖片轉化為用于運算的數據。假設紙張由19條縱切的紙條構成，使用MATLAB的unread命令將碎片圖片批量導入一個1×19的元胞數組中，即將圖片由bmp格式的文件轉化為數據類型為uint8的數值矩陣。其中第i張碎片的數值矩陣記為元胞數組的第i個數值矩陣，即c{i}。以任一數值矩陣舉例，矩陣的大小為72q1980，其每個元素代表了對應碎片圖片的該像素位置的灰度級，大小在0-255之間，純黑為0，純白為255。

②刪除數值矩陣中的冗余部分?？紤]到印刷文字的特點，每兩行文字之間會有一定的行間距，該部分的像素全部為白色，對應到矩陣中該處元素數值全部為0，對接下來的匹配運算沒有意義。為了提高運算效率，避免冗余的運算，對整體中的空白行進行刪除。

③進行碎片間相似度的檢測。在進行相似度的檢測中，只需用到碎片圖片左右邊界的各一列像素，即數值矩陣的第1列和第72列列向量；左邊界向量記為l{i}，右邊界向量記為r{i}。計算19個左邊界向量和19個右邊界向量兩兩之間的歐氏距離。

④根據得出的距離對碎片進行匹配和排序。優先匹配距離最短即相似度最高的兩個邊界。找到一組相似度最高的兩碎片邊界，將該兩邊界分別與其他所有邊界的距離替換為10000，保證其不再干擾隨后的匹配運算。此處需要進行人工干預，因為碎片紙條中有兩條是原文本文件的最左，右一條。最后得出碎片排列的編號順序，記為C。

⑤拼接并生成完整的圖像。按照上一步驟中得出的編號順序C依次對碎片的數值矩陣c{i}進行拼接，得到完整圖像的數值矩陣，記為Cdata。再根據Cdata生成圖像。

⑥人工檢查復原結果是否合理。

3.拼接模型的深度優化

①垂直雙向裁剪的拼接方案。針對紙張被垂直橫縱切為粒狀的情況，復原模型可以轉化為對碎紙片的分類。分類的原理依然是矩陣邊界向量的歐氏距離計算，測定適度的界限如1100，將歐氏距離小于1100的紙片歸為一類，并默認一類紙片代表出于同一行的所有紙片。在橫向拼接完畢后，紙片部分復原為若干橫條，拼接難度明顯降低，隨后的工作完全可以由人工完成。

②輔助性降噪處理。如果紙張掃描后的圖片有干擾性噪點，可以在圖片導入前先追加一步降噪處理，此過程需要人工干預，對照片處理后的質量進行監控。同時，如果同一批次的掃描照片噪點程度相似也可先進行批量處理，人工只需檢查處理后的圖像，挑選不合格的圖片返回二次處理。最終達到的目的是將掃描圖片內的干擾性噪點降到最低，同時不影響文字和圖像資料的檢測。選用Matlab也可以進行降噪工作，要求先將圖片數據二值化，將二值化后的圖像表示為函數g（X，y），噪聲信號為n（X，y），去噪后的圖像為e（X，y）一g（x，y）-n（X，v）。

③含有圖片紙張的圖片優先處理方案。如果在紙張上出現了圖片則要優先對圖片進行拼接，當圖片特征很明顯的是可以僅采取人工手工拼接的方法，當圖形較為復雜，拼接特征不明顯時可以用計算機算法來拼接。具體的操作是先將碎片掃描如電腦生成圖片文件并進行必要的降噪和二值化處理，再將距離剪裁邊界5-15像素的區域選為研究區域，針對區域內的點的分布做函數擬合，可以假設在10-30像素內的圖像線條基本為直線，擬合的函數便簡化為一次函數，對剪裁邊界以外5-15像素范圍內的函數圖像進行預測，最后將預測的函數圖像與可配對的邊界函數檢測進行匹配，尋找匹配度高的優先匹配即可生成完整文件，輔之以一定的人工校對。

二、實用性討論

本模型適用于所有印有文字的，規則裁切的紙張的拼接復原。印有文字的原始資料具有手寫資料所不具有的規則性，即其有嚴格的字體、字號、頁邊距、行距等規范，而這些規范也自然成為后期拼接時有效的利用點。如相鄰兩行間的行距可以默認為相同，而整個紙張無論是橫向還是縱向碎紙，都可以與文字和行間的方向構成穩定關系，相應的在由圖片形成的矩陣中如果出現連續的若干橫向量都為零，則可以認為是上下頁邊距或行間，同理連續列向量為零則可認為是邊界或縱向的分割空白區域，縱向文字材料剛好相反。

幾乎所有黑白印刷的紙張的修復基本上都可以用已給出的修復模型再配合輔助方案實現完全修復。而彩色的文件的修復則只需將原有的黑白二值的運算和匹配換為相應的三維向量的提取運算和匹配即可。且彩色的材料具有更強的連續型，匹配時的匹配度也會更高。

以圖片數字化處理為基礎，以元胞數組嵌套結構為媒介，以向量歐氏距離的測定和匹配為核心的碎紙拼接復原模型在實際的運用中顯現出了良好的效果，修復率均在97%以上，運行平穩，高效便捷。而廣泛的適用范圍和簡潔的操作更使其在實際運用中顯現出強有力的優勢。本模型在全國大學生數學建模競賽（B組題）中取得了山東省二等獎的成績。