基于MATLAB的證物還原技術的研究

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

（湖南城市學院 湖南 益陽 413000）

基于MATLAB的證物還原技術的研究

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

（湖南城市學院 湖南 益陽 413000）

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

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

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

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

1 問題假設

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

1）假設碎紙機在碎紙時不對碎紙片造成損壞；

2）假設碎紙片上的字跡清。

2 圖像處理與算法

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

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

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

圖1 總體設計框圖Fig.1 The overall design diagram

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

3 圖像的拼接

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 封閉曲線起始點鏈接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序列是相似的，所以我們將兩個鏈碼序列所屬的圖片進行拼接，以此類推，直到找到所有相似鏈碼，在基于二維坐標系的旋轉平移變換將圖片拼接復原。且其圖像輪廓曲線特征表示必須是旋轉和平移不變（剛體變換）。其復原效果圖如圖5所示。

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

4 結束語

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

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

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

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

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

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

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

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

［8］潘榮江，孟祥旭，屠長河.一種基于LCS的物體圖像碎片自動拼接方法.計算機學報，2005，28（3）:350-356.

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

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

［11］周曉明，馬秋禾，肖蓉，等.一種改進的Canny算子邊緣檢測算法［J］.測繪工程，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 稿件編號：201504023

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