韓海超，曾 英，吳亞玲，粟陶陶，蔣海鋒，林 龍

（湖南城市學(xué)院 湖南 益陽 413000）

基于MATLAB的證物還原技術(shù)的研究

韓海超，曾 英，吳亞玲，粟陶陶，蔣海鋒，林 龍

（湖南城市學(xué)院 湖南 益陽 413000）

文中提出了借助計(jì)算機(jī)基于MATLAB編程技術(shù)實(shí)現(xiàn)破碎文件（碎紙片）的證物復(fù)原方法，碎紙片證物的復(fù)原技術(shù)是圖像處理和模式識(shí)別等領(lǐng)域一個(gè)較新的且非常實(shí)用的技術(shù)應(yīng)用。應(yīng)用技術(shù)手段對(duì)碎片的顏色，紋理，行距，形狀等特征進(jìn)行掃描和提取，然后通過計(jì)算機(jī)進(jìn)行相應(yīng)的處理，使其在盡可能少的人工干預(yù)情況下實(shí)現(xiàn)證物的復(fù)原。

灰度二值化；最小差值法；聚類分析；canny邊緣檢測(cè)；freeman輪廓提取

破碎文件的拼接復(fù)原在修復(fù)歷史文獻(xiàn)、復(fù)原司法物證、以及在獲取軍事情報(bào)等領(lǐng)域都有著非常重要的應(yīng)用。傳統(tǒng)上，破碎文件的拼接復(fù)原工作都是由人工完成，復(fù)原效果好，準(zhǔn)確率較高，但效率很低，速度慢。尤其是當(dāng)碎片數(shù)量巨大時(shí)，人工拼接就會(huì)很困難，短時(shí)間內(nèi)很難完成任務(wù)。所以我們將借助計(jì)算機(jī)復(fù)原，雖然計(jì)算機(jī)復(fù)原的準(zhǔn)確率不及人工高，但是可以大大減輕工作強(qiáng)度。

比較著名的“東德”事件，1989年12月4日，柏林墻被推倒的一個(gè)月后，東德埃爾福特市的一棟政府大樓內(nèi)有關(guān)國家安全部秘密文件被毀掉，把文件撕成碎片塞進(jìn)1.6萬個(gè)褐色的麻袋里。之后為還原其證據(jù)，大約50名公務(wù)員用了8年時(shí)間費(fèi)勁辛苦，將300個(gè)袋子里的文件恢復(fù)原貌，但是照這樣的速度，要處理完余下的文件還得花費(fèi)450年的時(shí)間。由此可見有關(guān)證物還原技術(shù)的研究是必要的，近些年全世界國家和地區(qū)都對(duì)其進(jìn)行了研究，也取得了一定的進(jìn)展。據(jù)報(bào)道，曾在2011年10月29日，美國國防部高級(jí)研究計(jì)劃局 （DARPA）宣布了一場(chǎng)碎紙復(fù)原挑戰(zhàn)賽。2013年9月我國舉辦的全國大學(xué)生數(shù)學(xué)建模競賽，其B組題即是對(duì)碎紙片的復(fù)原，都旨在尋找到高效有效的算法，對(duì)處理后的碎紙屑進(jìn)行復(fù)原。

1 問題假設(shè)

假設(shè)一張完整的碎紙片被分成若干份規(guī)則碎片或不規(guī)則碎片兩種情況：

1）假設(shè)碎紙機(jī)在碎紙時(shí)不對(duì)碎紙片造成損壞；

2）假設(shè)碎紙片上的字跡清。

2 圖像處理與算法

對(duì)于碎紙片等一些二維平面物體，可以利用數(shù)碼相機(jī)、攝像機(jī)、掃描儀等設(shè)備獲得碎片影像及部分相關(guān)數(shù)據(jù)。為了計(jì)算的效率，凸顯目標(biāo)的輪廓和特征，對(duì)圖像進(jìn)行灰度處理，獲取圖像獨(dú)有的特征屬性。所以圖像特征的描述和提取是碎片匹配拼接的關(guān)鍵技術(shù)之一。常用的圖像特征有紋理特征、顏色特征、邊緣輪廓特征等。本文研究根據(jù)其規(guī)則與非規(guī)則圖像碎片分別采用基于圖像碎片邊緣顏色特征和鏈碼邊緣輪廓的拼接技術(shù)。

本論文結(jié)合算法和實(shí)際情況，通過計(jì)算機(jī)技術(shù)輔助，大大的提高了工作效率，節(jié)約了人力資源。設(shè)計(jì)的總框圖如下圖1所示。

對(duì)圖片進(jìn)行灰度處理，然后進(jìn)行二值化處理規(guī)定某一個(gè)閥值為T，當(dāng)灰度處理后的像素值大于此閥值時(shí)取為1，并將其規(guī)定為白色，反之取0，規(guī)定其為黑色，得到灰度矩陣并用數(shù)學(xué)形態(tài)的方法消除孤立的點(diǎn)。

圖1 總體設(shè)計(jì)框圖Fig.1 The overall design diagram

運(yùn)用Matlab軟件中imread函數(shù)將所有圖像轉(zhuǎn)化為像素點(diǎn)矩陣形式，imread函數(shù)可以把圖像以矩陣的形式讀出，一般是0～255之間的數(shù)值，其中黑色為0，白色為225，這就是象素的灰度值。為了減小數(shù)據(jù)處理過程中的誤差，需將矩陣中大于128的值化取作1，小于的值取作0。得到0-1化的矩陣。

3 圖像的拼接

3.1 針對(duì)規(guī)則形狀碎片的圖像拼接

針對(duì)規(guī)則形狀碎片，我們?cè)龠M(jìn)行基于數(shù)字矩陣之間列（或行）距離的圖片應(yīng)用最小差值法拼接復(fù)原模型。計(jì)算全部圖片對(duì)應(yīng)矩陣的列（或行）偏差值，得到所有碎紙片的排列拼接完整圖形。

建立目標(biāo)函數(shù)為：

觀察圖片被切割邊緣的灰度值可以得到：被切割圖片的兩側(cè)的灰度值基本一致，形成兩個(gè)相似的列矩陣，相似程度越高的兩列灰度值其所屬的兩張圖片復(fù)原的概率就越大，這就是本文針對(duì)規(guī)則碎片提出的優(yōu)先匹配方法最小差值法。

我們可以把圖片的最右側(cè)和最左側(cè)的灰度值矩陣全部提取出來，比較其邊緣相似度，可以記作Ak（i，1）和Ak（i，n），且對(duì)這兩列矩陣進(jìn)行對(duì)應(yīng)行相減取絕對(duì)值最后求和，所求得的和越小兩矩陣越相似，則圖片被復(fù)原的概率就越大，即

此時(shí)差值求和后最小的圖片即為第2張圖片。由數(shù)學(xué)歸納法以此類推，即可求出第3、4、5……n張圖片。

在工作和生活當(dāng)中我們遇到的圖形碎片會(huì)比較多而且復(fù)雜，僅僅依靠圖片被切割邊緣兩側(cè)的灰度矩陣相似度和最小差值法很難快速且完整將圖片復(fù)原，而面對(duì)大量圖片，我們需對(duì)其進(jìn)一步優(yōu)化，運(yùn)用聚類分析方法進(jìn)行匹配。依據(jù)其字體的大小、高度、寬度，圖片切割的均勻性以及文字的行距、段落等同等特征。通過多次類聚分組做出圖片其不同特征的類聚圖，利用計(jì)算機(jī)及在較少的人工干預(yù)下將所有各類圖形進(jìn)行拼接。

聚類分析：聚類分析（cluster analysis）是一組將研究對(duì)象分為相對(duì)同質(zhì)的群組（clusters）的統(tǒng)計(jì)分析技術(shù)。

可以用di，j表示圖片與Xj之間距離，用Di，j表示通過類聚后某類Gi與Gj之間的距離。類Gi與Gj之間的距離最小則最相近，即Di，j=minGi∈Gi，G∫∈G∫，di，j，也可以根據(jù)重心距、行間距，段間距，非對(duì)角間距等文字特征定義不同的新類。

選取若干圖片作為基點(diǎn)，計(jì)算每個(gè)圖片與選取基點(diǎn)的距離，由最小差值法優(yōu)先匹配，進(jìn)行最初的分類，然后根據(jù)文字的行距特征，文字的行間和段落等最小距離，再進(jìn)行第二次分類，以此類推重復(fù)類聚，如此動(dòng)態(tài)類聚直到所有圖片不再調(diào)整。此類聚方法分類迅速，占用計(jì)算機(jī)內(nèi)存少，特別是當(dāng)圖片數(shù)量較大時(shí)，也可以根據(jù)其他文字特征進(jìn)行更多的聚類，對(duì)圖片更好的復(fù)原是非常有利的。復(fù)原效果圖，如圖2所示。

3.2 針對(duì)非規(guī)則形狀碎片的圖像拼接

針對(duì)非規(guī)則形狀碎片，進(jìn)行canny邊緣檢測(cè)，因?yàn)閳D像的邊緣部分包含著圖像的大量信息，圖像邊緣信息的提取與確定對(duì)圖像場(chǎng)景的識(shí)別與理解提供重要的信息依據(jù)，也是圖像被分割所存在的重要特征，邊緣檢測(cè)主要是圖像的灰度變化的定位、檢測(cè)和度量。應(yīng)用canny邊緣檢測(cè)可以獲取二值化圖像的封閉邊界區(qū)域。

通過canny邊緣檢測(cè)后我們需對(duì)其圖像輪廓提取，在這里我們將采用Freeman鏈碼數(shù)字圖像輪廓提取，由Freeman在1961年提出的，根據(jù)二維圖像中線條的不同走勢(shì)方向，用｛0，1，…，7｝8個(gè)元素分別表示八鄰域像素，由此可以用一串由｛0，1，…，7｝中的元素組成的鏈碼近似的描述一個(gè)連續(xù)的平面線條圖像。如果按圈繞行，則可以由Freeman鏈碼的表示一幅二維圖像的輪廓且該鏈碼表示唯一。如圖3所示，兩個(gè)相鄰點(diǎn)的連接，如果以一個(gè)點(diǎn)為基點(diǎn)，其連接有八種可能方向。每一個(gè)方向的連接都是一個(gè)向量，我們用Dx=｛D1，D2，D3，D4，D5，D6，D7，D8｝表示。以八個(gè)向量方向按“先下后上，先左后右”的順序?qū)Χ祷蟮膱D像進(jìn)行跟蹤，每一個(gè)封閉的圖形都可以用一串?dāng)?shù)字作為邊界曲線鏈碼的表示，該鏈碼唯一確定。以跟蹤到的第一個(gè)邊緣點(diǎn)作為鏈碼的起始點(diǎn)，然后按順序跟蹤搜尋該點(diǎn)四周八個(gè)不同方向上是存在邊緣點(diǎn)，如果存在，則鏈碼加長，并將該點(diǎn)標(biāo)記避免重復(fù)掃描和匹配，然后，以此方式繼續(xù)尋找邊緣點(diǎn)進(jìn)行連接直到再也找不出可用邊緣點(diǎn)。如圖4所示。以A″作為起始點(diǎn)其方向取值為1，按照“先下后上，先左后右”的跟蹤原則，首先由A″的“左下”方搜索邊緣點(diǎn)，找到A點(diǎn)，其方向取值為4，然后再以A點(diǎn)作為新的起始點(diǎn)在其“左下”方尋找到邊緣點(diǎn)P″方向取值為4，因?yàn)镻″點(diǎn)已經(jīng)是邊緣，其“左下”方已經(jīng)沒有圖形邊緣可搜索，則向P″點(diǎn)的“右下”方向?qū)ふ疫吘夵c(diǎn)，找到邊緣點(diǎn)P其方向取值為6，按照此方法不斷尋找搜索最后回到A″，最終搜索路徑結(jié)果為：A″-A-P″-P-B″-B-C″-C-A″方向鏈碼為：1-4-4-6-5-0-2-0-2。我們對(duì)8方向鏈碼進(jìn)行一階差分作為圖像拼接時(shí)尋找相似的匹配序列，方向鏈碼一階差分后序列為：3-0-2-1-5-2-2-2。由于計(jì)算量比較大，我們也可以采用更多點(diǎn)的輪廓跟蹤，對(duì)數(shù)據(jù)進(jìn)行優(yōu)化，可以使跟蹤的整體速度得到提高。

圖2 規(guī)則形狀碎片復(fù)原效果圖Fig.2 The rules of fragments restoring effect chart

對(duì)圖形邊緣輪廓進(jìn)行數(shù)字鏈碼提取后，我們需對(duì)圖片進(jìn)行匹配、拼接復(fù)原。在這里我們采用一種叫做最長公共子序列的方法，英文縮寫為LCS（Longest Common Substring）。其定義為，給定一個(gè)序列S，如果該序列分別是兩個(gè)或多個(gè)已知序列的子序列，并且是已知序列的最長公共子序列。通過此方法對(duì)一階方差后的序列進(jìn)行相似匹配，將擁有最長公共子序列的兩張圖像進(jìn)行復(fù)原拼接。例如：

圖3 Freeman8方向取值Fig.3 The direction of freeman8 value

圖4 封閉曲線起始點(diǎn)鏈接Fig.4 The starting point of the curve closed link

差分序列X=［1，2，3，4，5，6］，Y=［0，1，2，4，5，］；已知序列S=［1，2，4，5］和Z=［2，4，5］，則S和Z序列都是X與Y的子序列，而S為最長公共子序列，因此說差分鏈碼X和Y序列是相似的，所以我們將兩個(gè)鏈碼序列所屬的圖片進(jìn)行拼接，以此類推，直到找到所有相似鏈碼，在基于二維坐標(biāo)系的旋轉(zhuǎn)平移變換將圖片拼接復(fù)原。且其圖像輪廓曲線特征表示必須是旋轉(zhuǎn)和平移不變（剛體變換）。其復(fù)原效果圖如圖5所示。

圖5 非規(guī)則形狀碎片復(fù)原效果圖Fig.5 Irregular fragments restoring effect chart

4 結(jié)束語

本文對(duì)計(jì)算機(jī)圖像處理領(lǐng)域進(jìn)行了探究，旨尋找高效，快捷的圖片拼接方法，從而實(shí)現(xiàn)證物的還原。本文方法可以擺脫以往的繁瑣的，大量的工作，實(shí)現(xiàn)簡單，可靠性強(qiáng)，通過計(jì)算機(jī)和信息手段完成一些很難完成的工作。

［1］羅智中.基于線段掃描的碎紙片邊界檢測(cè)算法研究［J］.儀器儀表學(xué)報(bào)，2011，32（2）:289-294.

［2］李利軍，李云偉.基于圖像灰度的拼接技術(shù)研究［J］.計(jì)算機(jī)與數(shù)字工程，2007，35（9）:128-130.

［3］賈海燕，朱良家，周宗潭，等.一種碎紙自動(dòng)拼接中的形狀匹配方法［J］.計(jì)算機(jī)仿真，2006，11:180-183.

［4］zhx19870705，聚類分析［EB/OL］http://wenku.baidu.com/view/ 02e3d-7c8050876323112125f.html.

［5］于萬波.基于MATLAB的圖像處理［M］.北京：清華大學(xué)出版社，2011.

［6］姚文君.基于freeman鏈碼二維圖像輪廓提取與匹配［J］.寧波技術(shù)學(xué)院學(xué)報(bào)，2006（5）:24-26.

［7］朱延娟，周來水，劉毅.二維非規(guī)則碎片匹配的算法［J］.計(jì)算機(jī)工程，2007，24（12）:7-9.

［8］潘榮江，孟祥旭，屠長河.一種基于LCS的物體圖像碎片自動(dòng)拼接方法.計(jì)算機(jī)學(xué)報(bào)，2005，28（3）:350-356.

［9］姜啟源.數(shù)學(xué)建模（第三版）［M］.北京:高等教育出版社，2003.

［10］參加2013全國大學(xué)生數(shù)學(xué)建模競賽，B組題.

［11］周曉明，馬秋禾，肖蓉，等.一種改進(jìn)的Canny算子邊緣檢測(cè)算法［J］.測(cè)繪工程，2008，17（2）:28-31.

Research on MATLAB reduction technology based on evidence

HAN Hai-chao，ZENG Ying，WU Ya-ling，SU Tao-tao，JIANG Hai-feng，LIN Long
（Hunan City University，Yiyang 413000，China）

This paper proposed by the aid of computer implementation of broken file based on the MATLAB programming technology（scraps）restoration method exhibits，scraps of paper evidence recovery technology is a new and very practical technology application field of image processing and pattern recognition.Application of technical means on pieces of color，texture，line spacing，scanning and extraction of shape feature，then the corresponding processing by computer，realize its evidence recovery in the artificial intervention as little as possible under the circumstances.

the gray value of the two；the minimum difference method；cluster analysis；canny edge detection；freeman contour extraction

TP99

A

1674－6236（2016）04-0186-04

2015-04-02 稿件編號(hào)：201504023

韓海超（1992—），男，內(nèi)蒙古赤峰人。研究方向：電子信息與通信工程。