碎紙片拼接復(fù)原的數(shù)學(xué)模型與優(yōu)化

朱旭++焦熹++李亦凡

摘要 碎紙機(jī)裁出的碎紙片的拼接與復(fù)原技術(shù)是計(jì)算機(jī)算法與人工干預(yù)的結(jié)合，兼顧準(zhǔn)確度與效率。碎紙片的拼接與復(fù)原算法以采用了全新的向量間歐氏距離的匹配模型，在圖片數(shù)據(jù)化處理的基礎(chǔ)上，加之針對(duì)橫向縱向雙向切割的文檔而編寫的檢測(cè)碎片是否在同一行的輔助程序，和針對(duì)英文文件的碎片進(jìn)行行位置標(biāo)識(shí)從而實(shí)現(xiàn)“行分類”的應(yīng)用擴(kuò)展程序；核心算法和輔助及擴(kuò)展程序共同構(gòu)成了碎紙片拼接復(fù)原的數(shù)學(xué)模型。最終對(duì)單面中英文單向和雙向?qū)崿F(xiàn)了裁切的紙張都97%以上的復(fù)原，可以說(shuō)復(fù)原模型是成功且有效的。

關(guān)鍵詞 碎紙拼接復(fù)原 歐氏距離匹配 元胞數(shù)組嵌套結(jié)構(gòu)

中圖分類號(hào)：G642.3

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1002-7661（2015）01-0004-02

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

一、建模思路

1.圖片數(shù)據(jù)化處理

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

2.核心拼接算法

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

②刪除數(shù)值矩陣中的冗余部分?？紤]到印刷文字的特點(diǎn)，每?jī)尚形淖种g會(huì)有一定的行間距，該部分的像素全部為白色，對(duì)應(yīng)到矩陣中該處元素?cái)?shù)值全部為0，對(duì)接下來(lái)的匹配運(yùn)算沒(méi)有意義。為了提高運(yùn)算效率，避免冗余的運(yùn)算，對(duì)整體中的空白行進(jìn)行刪除。

③進(jìn)行碎片間相似度的檢測(cè)。在進(jìn)行相似度的檢測(cè)中，只需用到碎片圖片左右邊界的各一列像素，即數(shù)值矩陣的第1列和第72列列向量；左邊界向量記為l{i}，右邊界向量記為r{i}。計(jì)算19個(gè)左邊界向量和19個(gè)右邊界向量?jī)蓛芍g的歐氏距離。

④根據(jù)得出的距離對(duì)碎片進(jìn)行匹配和排序。優(yōu)先匹配距離最短即相似度最高的兩個(gè)邊界。找到一組相似度最高的兩碎片邊界，將該兩邊界分別與其他所有邊界的距離替換為10000，保證其不再干擾隨后的匹配運(yùn)算。此處需要進(jìn)行人工干預(yù)，因?yàn)樗槠垪l中有兩條是原文本文件的最左，右一條。最后得出碎片排列的編號(hào)順序，記為C。

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

⑥人工檢查復(fù)原結(jié)果是否合理。

3.拼接模型的深度優(yōu)化

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

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

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

二、實(shí)用性討論

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

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

以圖片數(shù)字化處理為基礎(chǔ)，以元胞數(shù)組嵌套結(jié)構(gòu)為媒介，以向量歐氏距離的測(cè)定和匹配為核心的碎紙拼接復(fù)原模型在實(shí)際的運(yùn)用中顯現(xiàn)出了良好的效果，修復(fù)率均在97%以上，運(yùn)行平穩(wěn)，高效便捷。而廣泛的適用范圍和簡(jiǎn)潔的操作更使其在實(shí)際運(yùn)用中顯現(xiàn)出強(qiáng)有力的優(yōu)勢(shì)。本模型在全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽（B組題）中取得了山東省二等獎(jiǎng)的成績(jī)。