王松林 王苑茹

【摘要】破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用.本文主要結(jié)合重要文件不慎被損壞的修復(fù)這一背景，針對(duì)碎紙機(jī)切碎的碎紙片進(jìn)行拼接復(fù)原研究.主要研究?jī)?nèi)容有：利用Matlab軟件將圖像信息轉(zhuǎn)化為數(shù)字信息，得到碎紙片的數(shù)據(jù)矩陣，再對(duì)碎紙片進(jìn)行邊界提取.通過進(jìn)行邊界匹配，對(duì)各碎紙片的邊界序列進(jìn)行匹配.在碎紙片的邊界序列匹配中運(yùn)用了灰色關(guān)聯(lián)度分析的匹配方法.最后利用Matlab軟件圖片處理工具箱，依據(jù)邊界匹配得到的相鄰順序編號(hào)對(duì)碎紙片進(jìn)行了拼接、復(fù)原.

【關(guān)鍵詞】圖像轉(zhuǎn)化；Matlab編程；邊界匹配；碎紙片復(fù)原

一、研究背景及意義

歷史上曾出現(xiàn)過將大量絕密文件進(jìn)行銷毀的案例，在司法鑒定領(lǐng)域也存在類似的問題.本課題的目標(biāo)是利用計(jì)算機(jī)輔助的方法對(duì)碎紙機(jī)切碎的紙片進(jìn)行拼接、復(fù)原.本文主要討論的是針對(duì)碎紙機(jī)切碎的紙片進(jìn)行拼接、復(fù)原的關(guān)鍵技術(shù).本文對(duì)碎紙片進(jìn)行了整體分析，利用Matlab軟件的圖片處理工具箱把碎紙片圖像信息進(jìn)行量化，用灰色關(guān)聯(lián)度分析法找出相鄰碎紙片之間的拼接關(guān)系，最后利用Matlab軟件的圖片處理工具箱對(duì)碎紙片拼接復(fù)原.本文主要結(jié)合重要文件不慎被損壞的修復(fù)這一應(yīng)用背景，針對(duì)碎紙機(jī)切碎的碎紙片進(jìn)行拼接和復(fù)原的研究.

二、碎紙片預(yù)處理

（一）圖像預(yù)處理

本文研究采用的碎紙片是一張單面打印的A4紙由碎紙機(jī)切碎后得到的規(guī)則的矩形小碎紙片，共計(jì)209張小碎紙片，并將每張紙片依次編號(hào)為k（k=001，…，209）.為了便于計(jì)算和處理，先利用圖像掃描儀對(duì)每張小碎紙片進(jìn)行掃描，得到每張小碎紙片的電子圖像信息[2]，如表1所示.

再利用計(jì)算機(jī)Matlab軟件的圖片處理工具箱的a=imread（filename，fmt）命令，將每張小碎紙片的圖像信息轉(zhuǎn)化可直接利用的數(shù)字信息，得到每張碎紙片的數(shù)字信息均為一個(gè)72×180階的數(shù)據(jù)矩陣.

（二）數(shù)據(jù)轉(zhuǎn)化及序列提取[3]

利用Matlab軟件將圖像信息轉(zhuǎn)化成可直接利用的數(shù)字信息，得到每張圖片的數(shù)字信息矩陣后，由于拼接時(shí)只研究每張紙片的邊界，不用考慮碎紙片邊界內(nèi)部的數(shù)字信息，所以再對(duì)每張圖像的72×180階的數(shù)據(jù)矩陣提取第一列和最后一列，分別得到相應(yīng)的數(shù)據(jù)序列如下：

左邊界的序列X1k=（x1，x2，…，x180），k=1，2，…，209.

右邊界的序列X2k=（x1，x2，…，x180），k=1，2，…，209.

三、灰色關(guān)聯(lián)度匹配模型

由于碎紙片邊界序列因素之間關(guān)系比較復(fù)雜，在此采用灰色關(guān)聯(lián)度的方法對(duì)各碎紙片的邊界進(jìn)行匹配.灰色關(guān)聯(lián)度是兩個(gè)系統(tǒng)或兩個(gè)序列間關(guān)聯(lián)性大小的量度，它描述系統(tǒng)發(fā)展過程中序列間相對(duì)變化的情況.關(guān)聯(lián)度是考查兩數(shù)列的接近程度，它的大小反映了兩列數(shù)據(jù)的相互影響程度，關(guān)聯(lián)度大，則說明兩因素間的相互影響程度大.如果兩序列在匹配過程中相對(duì)變化態(tài)勢(shì)一致性高，則兩者的灰色關(guān)聯(lián)度大；反之，灰色關(guān)聯(lián)度就小.在此我們利用灰色關(guān)聯(lián)度的方法來匹配兩個(gè)應(yīng)該拼接在一起的邊界序列.

通過對(duì)碎紙片研究分析發(fā)現(xiàn)，左右字間距明顯小于上下行間距，且左右邊界的序列數(shù)據(jù)多于上下邊界序列的數(shù)據(jù)，因此，先進(jìn)行橫向即左右邊界匹配，精確度更高，再進(jìn)行縱向即上下邊界匹配，最后得到復(fù)原碎紙文件.

（一）確定匹配序列

對(duì)碎紙片的序列進(jìn)行匹配，先考慮左右邊界拼接的情況.首先確定參考序列（又稱母序列），這里選取任意一張碎紙片右邊界的序列作為參考序列：X2a=（x1，x2，…，x180），1≤a≤209.為了和選取的碎紙片的右邊界進(jìn)行匹配，則將剩下的208張碎紙片的左邊界的序列作為比較序列（又稱子序列）：X1b=（x1，x2，…，x180），b=1，2，…，a-1，a+1，…，209.若選取的碎紙片的右邊界和剩下的208張碎紙片中的其中一張進(jìn)行了關(guān)聯(lián)度最大的匹配，則認(rèn)為這兩張碎紙片可以拼接在一起.接著就取該碎紙片的右邊界作為參考序列，繼續(xù)和剩下的左邊界比較序列進(jìn)行關(guān)聯(lián)度匹配，直至左右邊界拼接結(jié)束為止.

再考慮上下邊界拼接的情況.由于上面已經(jīng)對(duì)209張小碎紙片進(jìn)行了左右拼接，左右拼接結(jié)束后，209張小碎紙片變成了若干張（假設(shè)為h張）橫向的紙條.這時(shí)再對(duì)得到的h張橫向紙條利用Matlab軟件的圖片處理工具箱的a=imread（filename，fmt）命令進(jìn)行數(shù)據(jù)提取，分別提取每張橫向紙條的第一行和最后一行，分別得到數(shù)據(jù)序列如下：

上邊界的序列Y1h=（y1，y2，…，yn）.

下邊界的序列Y2h=（y1，y2，…，yn）.

這里同樣選取h張橫向紙條中的任意一張碎紙片的下邊界的序列作為參考序列：Y2c=（y1，y2，…，yn），1≤c≤h.為了和選取的碎紙片的上邊界進(jìn)行匹配，則將剩下的h-1張橫向紙條的上邊界的序列作為比較序列：Y1d=（y1，y2，…，yn）.d=1，2，…，c-1，c+1，…，h.若選取的橫向紙條的下邊界和剩下的h-1張橫向紙條中的一張進(jìn)行了關(guān)聯(lián)度最大的匹配，則認(rèn)為這兩張橫向紙條可以拼接在一起.接著就取該橫向紙條的下邊界作為參考序列，繼續(xù)和剩下的上邊界比較序列進(jìn)行關(guān)聯(lián)度匹配，直至上下邊界拼接結(jié)束為止.最后進(jìn)行碎紙片的拼接及復(fù)原.

（二）序列元素的標(biāo)準(zhǔn)化

由于序列中的數(shù)據(jù)可能因量綱不同，不便于比較或在比較時(shí)難以得到正確的結(jié)論.因此，在進(jìn)行灰色關(guān)聯(lián)度分析時(shí)，一般都要進(jìn)行數(shù)據(jù)的無量綱化處理.利用Matlab軟件的圖片處理工具箱的a=imread（filename，fmt）命令進(jìn)行圖片信息轉(zhuǎn)化為數(shù)字信息，本身就是在同一量綱下進(jìn)行轉(zhuǎn)化的，所以這里不再對(duì)各序列的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化.

（三）計(jì)算序列的關(guān)聯(lián)系數(shù)[4]

ρ∈（0，∞），稱為分辨系數(shù).ρ越小，分辨力越大，一般ρ的取值區(qū)間為（0，1），具體取值可視情況而定.當(dāng)ρ≤0.5436時(shí)，分辨力最好，通常取ρ=0.5，這里也取ρ=0.5來進(jìn)行關(guān)聯(lián)度分析.

（四）計(jì)算序列的關(guān)聯(lián)度

（五）序列的關(guān)聯(lián)度排序

兩序列之間的關(guān)聯(lián)程度，主要是用關(guān)聯(lián)度的大小順序描述，將所有匹配關(guān)聯(lián)度的大小進(jìn)行排序，選出最大的，作為左右邊界相匹配的碎紙片.將子序列對(duì)同一母序列的關(guān)聯(lián)度按大小順序排列起來，如果r1

若任意取一張碎紙片的右邊界和剩下的208張碎紙片中的一張進(jìn)行關(guān)聯(lián)度匹配，并獲得了關(guān)聯(lián)度的最大值，則認(rèn)為這兩張碎紙片可以拼接在一起.接著就取該碎紙片的右邊界作為參考序列，繼續(xù)和剩下的序列進(jìn)行關(guān)聯(lián)度匹配，直到匹配完成為止.

四、灰色關(guān)聯(lián)度匹配算法

（一）數(shù)據(jù)轉(zhuǎn)化及序列提取過程

步驟一：

對(duì)209張碎紙片進(jìn)行編號(hào)，利用Matlab軟件圖片處理工具箱的a=imread（filename，fmt）命令，將圖像信息轉(zhuǎn)化為可直接利用的數(shù)字信息，得到每張碎紙片的數(shù)字信息均為一個(gè)72×180階的數(shù)據(jù)矩陣Xij.

步驟二：

先提取得到每張圖片的左右邊界序列，利用Matlab軟件編程提取出所有碎紙片左邊界序列X1k和右邊界序列X2k.

步驟三：

建立灰色關(guān)聯(lián)度的匹配模型，對(duì)每一對(duì)碎紙片左右邊界序列進(jìn)行序列匹配，可以得出一系列左右邊界的關(guān)聯(lián)度數(shù)據(jù).利用Excel辦公軟件的篩選功能，進(jìn)行數(shù)據(jù)統(tǒng)計(jì)，選出每個(gè)碎紙片左右邊界序列的最大關(guān)聯(lián)度，得出左右相鄰的碎紙片編號(hào).重復(fù)此步驟，再進(jìn)行人工干預(yù)得到h張橫向紙條.

步驟四：

從數(shù)據(jù)矩陣Xij提取得到的h張橫向紙條文件對(duì)應(yīng)的上下碎紙序列，利用灰色關(guān)聯(lián)度的匹配模型，對(duì)h張橫向紙條較大碎紙片進(jìn)行上下邊界序列匹配.同理得出一系列上下邊界的關(guān)聯(lián)度數(shù)據(jù)，利用Excel辦公軟件的篩選功能，進(jìn)行數(shù)據(jù)統(tǒng)計(jì)，選出每個(gè)碎紙片上下邊界序列的最大關(guān)聯(lián)度，得出上下相鄰的碎紙片編號(hào).

步驟五：

利用Matlab圖片處理工具箱的imshow命令對(duì)碎紙片文件進(jìn)行復(fù)原，并輸出到一個(gè)完整的圖片文件中.

（二）關(guān)聯(lián)度匹配模型算法步驟[5]

步驟一：

對(duì)209張碎紙片順序編號(hào)為k1，k2，…，k209，利用Matlab軟件圖片處理工具箱的a=imread（filename，fmt）命令，把碎紙片圖像文件數(shù)據(jù)化得到數(shù)據(jù)矩陣Xij.

步驟二：

由數(shù)據(jù)轉(zhuǎn)化和序列提取，得到每張圖片的左右邊界序列，利用Matlab軟件編程，對(duì)建立的灰色關(guān)聯(lián)度匹配模型進(jìn)行實(shí)現(xiàn).

步驟三：

由步驟二得到了209張碎紙片的左右邊界序列的匹配的關(guān)聯(lián)度，可以得出一系列左右邊界的關(guān)聯(lián)度數(shù)據(jù).利用Excel辦公軟件的篩選功能，進(jìn)行數(shù)據(jù)統(tǒng)計(jì)，選出每個(gè)碎紙片左右邊界序列的最大關(guān)聯(lián)度，得出左右相鄰的碎紙片編號(hào).重復(fù)此步驟，再進(jìn)行人工干預(yù)得到h張橫向紙條.

步驟四：

由步驟二、三，將209張碎紙片拼接成h張橫向紙條，這h張橫向紙條的橫向拼接已經(jīng)完成.從數(shù)據(jù)矩陣Xij中提出這h張橫向紙條的上邊界序列Y1h和下邊界序列Y2h.

步驟五：

先對(duì)得到的h張橫向紙條進(jìn)行編號(hào)（z1，z2，…，zh），分別提取h張橫向紙條上下邊界序列，利用Matlab軟件編程，對(duì)建立的灰色關(guān)聯(lián)度匹配模型進(jìn)行實(shí)現(xiàn).

步驟六：

將運(yùn)行Matlab軟件求解得到一系列相關(guān)的關(guān)聯(lián)度，再進(jìn)行人工干預(yù)，選取上下邊界序列關(guān)聯(lián)度最大的兩張圖片進(jìn)行拼接；

步驟七：

最后將各相鄰碎紙片的拼接順序進(jìn)行列表匯總，再利用Matlab軟件圖片處理工具箱的imshow命令對(duì)所有碎紙片進(jìn)行拼接、復(fù)原.

（三）碎紙片的拼接、復(fù)原結(jié)果

由左右邊界和上下邊界的灰色關(guān)聯(lián)度的分析，灰色關(guān)聯(lián)度越大則數(shù)據(jù)關(guān)系越緊密，碎紙片之間的吻合程度就越高.選取關(guān)聯(lián)度最大的兩張碎紙片作為相鄰的碎紙片進(jìn)行拼接.最后用得到的相鄰碎紙片拼接順序表，利用Matlab軟件圖片處理工具箱的imshow命令，將碎紙片順序編號(hào)依次輸入Matlab軟件，將各碎紙片進(jìn)行拼接，最終對(duì)碎紙片進(jìn)行復(fù)原.

五、結(jié) 論

本文是對(duì)由碎紙機(jī)切碎的碎紙片進(jìn)行拼接、復(fù)原的研究.本文的研究方法適合任何內(nèi)容、任何形式、任何文字等的圖片，使本方法適用更加廣泛.本文研究的方法對(duì)于圖片信息數(shù)據(jù)化轉(zhuǎn)換較快、較方便，運(yùn)用灰色關(guān)聯(lián)度分析方法，對(duì)于數(shù)據(jù)信息較多的碎紙圖片匹配精確度較高.本文的研究方法可以進(jìn)行大量推廣，我們建立的灰色關(guān)聯(lián)度分析方法模型，可以大量應(yīng)用于各種內(nèi)容碎紙圖片拼接問題中的各碎紙圖片拼接吻合程度大小的計(jì)算以及各張碎紙片的拼接、復(fù)原.

【參考文獻(xiàn)】

[1]賈海燕.碎紙片自動(dòng)拼接關(guān)鍵技術(shù)研究[D].長(zhǎng)沙：國(guó)防科技大學(xué)，2005.

[2]蕭樹鐵，姜啟源，張立平.數(shù)學(xué)實(shí)驗(yàn)：第2版[M].北京：高等教育出版社，2006.

[3]汪曉銀，周保平.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M].北京：科學(xué)出版社，2010.

[4]熊翠琳，李旭東.貴州人口受教育程度與經(jīng)濟(jì)發(fā)展灰色關(guān)聯(lián)分析[J].貴州師范大學(xué)學(xué)報(bào)，2012：119-120.

[5]姜啟源，謝金星，葉俊.數(shù)學(xué)模型：第3版[M].北京：高等教育出版社，2003.