基于碎紙機(jī)切割規(guī)則紙片的拼接復(fù)原研究

【摘 要】本文旨在解決規(guī)則的矩形碎紙片拼接復(fù)原問題，要求盡可能實(shí)現(xiàn)程序自動(dòng)拼接，減少人工干預(yù)，以提高拼接復(fù)原效率。對于單面縱切紙片，我們首先根據(jù)圖片左側(cè)邊緣空白部分的寬度，確定寬度最大的圖片為原文件的左邊界。接著將左邊界圖片作為標(biāo)準(zhǔn)圖片，以重合邊界左右兩側(cè)的圖片灰度值向量匹配程度為原則，我們定義兩張圖片邊緣灰度值向量的歐氏距離為邊緣匹配程度指標(biāo)，依次搜索最優(yōu)匹配的圖片。整個(gè)復(fù)原過程并未參與人工干擾。本文建立了邊緣灰度值向量最優(yōu)匹配模型作為基本模型，可完成中英文文件單面縱切的紙片拼接復(fù)原。而隨著將算法遞進(jìn)，也可以進(jìn)一步完成單面橫縱切、雙面橫縱切的紙片復(fù)原問題。

【關(guān)鍵詞】匹配度；圖片邊緣；灰度值

一、研究背景

圖像拼接是數(shù)字圖像處理的一個(gè)重要分支，是將一系列有重疊邊界的圖像拼接成一幅大型的無縫的高分辨率圖像，包括圖像采集、圖像預(yù)處理、圖像配準(zhǔn)、圖像融合以及圖像輸出。在很多場合下，人們都會(huì)用到圖像復(fù)原技術(shù)，而且對拼接的精確度要求極高。破碎文件的拼接是生活中最為簡單常見的情況，在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。我們考慮利用計(jì)算機(jī)技術(shù)，來建立對碎紙機(jī)處理后的碎紙屑進(jìn)行復(fù)原的數(shù)學(xué)模型和算法，替代繁瑣的人工拼接，以提高拼接復(fù)原效率。但這又對文件復(fù)原的正確率提出了很高的要求，避免出現(xiàn)偽拼接。針對碎紙片拼接問題，首先我們首要解決的是一種最基礎(chǔ)的復(fù)原，如何對來自同一頁印刷文字文件、并且僅被碎紙機(jī)縱切的破碎紙片，設(shè)計(jì)拼接模型和算法，將文件進(jìn)行快速準(zhǔn)確復(fù)原。

二、模型假設(shè)

（一）假設(shè)由于碎紙機(jī)等外界因素造成的誤差忽略不計(jì)。

（二）假設(shè)碎紙機(jī)將文件切割成規(guī)則矩形，即切割邊界都是直線。

（三）假設(shè)同一頁印刷文件的每一行字都有上下兩條標(biāo)準(zhǔn)線。

（四）假設(shè)在復(fù)原過程中可以進(jìn)行適當(dāng)?shù)娜斯じ深A(yù)。

（五）假設(shè)不存在兩張圖片能夠同時(shí)與另一張圖片匹配。

三、符號(hào)說明及名詞定義

四、基本模型建立與算法分析

由于在重合的圖片邊界左右兩側(cè)的灰度值較為接近，我們以重合邊界兩側(cè)灰度值分布的近似程度大小來衡量兩張圖片的匹配度，并依此尋找最優(yōu)的匹配圖片。我們記圖片的灰度值矩陣為。

（二）最左側(cè)邊緣圖片的確定.考慮到原文件左邊緣處會(huì)留下較大的空白部分，根據(jù)圖片左邊緣所留空白部分的寬度進(jìn)行判斷，先找出位于原文件最左側(cè)的一張圖片，記為。然后根據(jù)最優(yōu)匹配定義可以依次往右拼接圖片。

（三）算法設(shè)計(jì).記圖片集合，記已經(jīng)復(fù)原的圖片集合（集合中的元素順序即為圖片從左往右的拼接順序），記未排序的圖片集合，即。

Step1：提取圖片的灰度值矩陣，搜索出位于原文件最左側(cè)的圖片，此時(shí)，；

Step2：計(jì)算中所有元素與圖片匹配度 ，取成立時(shí)的為最優(yōu)匹配圖片。記，則此時(shí)，

Step3：重復(fù)Step2，按最優(yōu)匹配定義依次從集合中選出元素，按順序放入集合中進(jìn)行拼接，直到；

Step4：最終得到，按照中元素順序?qū)D片拼接即可完成碎紙片復(fù)原。

（四）模型結(jié)果分析.根據(jù)上述復(fù)原模型和算法，我們可以成功的對給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片（僅縱切）完成碎紙的拼接復(fù)原。同時(shí)中文文件和英文文件在碎紙拼接中并未體現(xiàn)出較大差異，由該模型算法都可以復(fù)原。說明我們的模型對中英文文件的碎片數(shù)據(jù)拼接復(fù)原均適用，算法穩(wěn)定性高。

參考文獻(xiàn)：

[1]林小平，周石琳. 一種基于蟻群算法和互信息測度的圖像拼接技術(shù)[J]. 重慶理工大學(xué)學(xué)報(bào)（自然科學(xué)），2013，27（1）：76-81

[2]Edson Justino， Luiz S. Oliveira， Cinthia Freitas. Reconstructing shredded documents through feature matching[J]. Forensic Science International 160 （2006） ：140-147

[3]Anna Skeoch. An Investigation into Automated Shredded Document Reconstruction using Heuristic Search Algorithms[J].2006.