謝亞旗 繆楊 梁偉 王韻 安秋平

（1.深圳市建設工程造價管理站 廣東省深圳市 518031 2.?？诮?jīng)濟學院 海南省海口市 571127）

（3.貴州數(shù)聯(lián)銘品科技有限公司 貴州省貴陽市 550005 4.中交一航局生態(tài)工程有限公司 廣東省深圳市 518000）

1 引言

破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域也存在類似的問題，大量的紙質物證復原工作目前基本上都是以手工方式完成的。一旦碎紙的數(shù)量增大到幾百甚至上千塊的時候，如果仍然依靠手工完成，不但耗費大量的人力、物力，而且還可能對物證造成一定的損壞。目前，在國際上，德國等發(fā)達國家對破碎文件的自動修復技術已經(jīng)進行了相當長時間的研究。但是由于技術封鎖的原因，我們所能夠搜集的資料非常有限。而在國內(nèi)，還沒有類似的研究成果問世。因此，結合碎紙自動拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域的應用這一背景，把計算機視覺和模式識別應用于碎片復原，開展對碎紙自動拼接技術的研究具有重要的現(xiàn)實意義。

本文研究如下問題：對于碎紙機既縱切又橫切的情形，每頁紙被切為11×19 個碎片，設計碎紙片拼接復原模型和算法，并針對給出的中、英文各一頁文件的416 塊碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，寫出干預方式及干預的時間節(jié)點。

2 問題的思路分析

2.1 問題的分析

對于此問題圖片數(shù)量較多，圖片匹配除了橫向的匹配拼接還有縱向的匹配拼接。采用利用圖片邊緣灰度矩陣進行匹配時會產(chǎn)生龐大的數(shù)據(jù)人工難以處理。所以我們重新建立了一個歐氏距離模型。首先，運用圖片邊緣灰度矩陣進行匹配的手段，使用Matlab 提取相關的圖片信息；然后，根據(jù)匹配的橫向和縱向，利用聚類分析的系統(tǒng)聚類法模型進行了數(shù)據(jù)分類，得到了初步的數(shù)據(jù)分析的結果，通過spss 軟件對各組數(shù)據(jù)采用標準值代替，得到了標準值散點圖，使用人工干預橫向和縱向匹配得出了比較優(yōu)化的數(shù)據(jù)分析結果；最后，運用歐氏距離進行相關性分析與匹配數(shù)學模型驗證了spss 的最優(yōu)化的數(shù)據(jù)分析結果，解決碎紙片拼接復原。

3 模型的建立與求解

對于此問題圖片數(shù)量較多，圖片匹配除了橫向的匹配拼接還有縱向的匹配拼接。采用利用圖片邊緣灰度矩陣進行匹配時會產(chǎn)生龐大的數(shù)據(jù)人工難以處理。因此我們引入了系統(tǒng)聚類法對數(shù)據(jù)進行分類，使問題簡化。

3.1 運用系統(tǒng)聚類法模型對數(shù)據(jù)進行分類

系統(tǒng)聚類法基本思想：首先，把每個變量（每個樣品）看作一類，并規(guī)定定量間的相似性測度換算成的距離（其中cij表示變量i 和變量j 之間的相關系數(shù)，或樣品i 和樣品j 之間的相似系數(shù)）（或樣品之間的距離）看作類與類之間的距離，然后將距離最近的兩類合成新的一類，每次減少一類，重新進行最近類的合并，直至所有的變量（或樣品）合并成一類。

圖1：z，y 矩陣各列標準值散點圖

圖2：人工干預界面

圖3：ab 之間的歐氏距離

圖4：中文碎片復原圖

圖5：英文碎片復原圖

系統(tǒng)聚類法方法：類與類之間的距離的定義如同樣品間的距離定義一樣，有各種各樣不同的方法。其中，系統(tǒng)聚類方法是用的最多的一種方法。

設dij表示樣品i 與樣品j 之間的距離，G1,G2,...表示類，Dij表示Gi與Gj的距離。

最短距離法：定義類Gi與Gj之間的距離為兩類最近樣品（或指標）的距離，即

設Gp與Gq合并成一個新類，記為Gr，則任一類Gk與Gr的距離是

運用Matlab 提取出來的各組數(shù)據(jù)太多不能直接使用系統(tǒng)聚類法進行分類。所以我們先使用spss 軟件對各組數(shù)據(jù)采用標準值代替，從而使用系統(tǒng)聚類法來進行分類處理。

得出的標準值散點圖如圖1所示。

由于系統(tǒng)聚類法進行的是模糊分類，造成了分類的不準確性，而且運用歐氏距離匹配時方案眾多，為確保最后拼接的準確性需采用人工干預的方式對spss 處理得出的標準值數(shù)據(jù)，進行人為干預和處理。干預時間節(jié)點為，數(shù)據(jù)分類后進行匹配時。干預方式如圖2。

3.2 運用歐氏距離模型進行相關性分析與匹配

對眾多數(shù)據(jù)采用系統(tǒng)聚類法進行分類得到11組不同特征矩陣。再接著使用歐式距離模型對11 組矩陣進行橫向匹配拼接，形成新的11 組矩陣后再進行縱向拼接。

如圖3，歐式距離（ Euclidean distance）也稱歐幾里得距離，它是一個通常采用的距離定義，源自歐氏空間中兩點間的距離公式。它是在m 維空間中兩個點之間的真實距離，歐氏距離是最易于理解的一種距離計算方法。

（1）二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離：

（2）三維空間兩點a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：

（3）兩個n 維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的歐氏距離：

也可以用表示成向量運算的形式：

但是歐氏距離也有其局限性：即數(shù)據(jù)各維分量的分布不一樣。所以我們引用標準化歐氏距離。

標準歐氏距離的思路：既然數(shù)據(jù)各維分量的分布不一樣，先將各個分量都“標準化”到均值、方差相等。假設樣本集X的均值(mean)為m，標準差(standard deviation)為s，而且標準化變量的數(shù)學期望為0，方差為1。因此樣本集的標準化過程(standardization)那么用X 的“標準化變量”模型表示為：

標準化后的值= （標準化前的值-分量的均值） /分量的標準差.

經(jīng)過簡單的推導就可以得到兩個n 維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的標準化歐氏距離的公式：

如果將方差的倒數(shù)看成是一個權重，這個公式可以看成是一種加權歐氏距離。

將各組經(jīng)過人工干預后的數(shù)據(jù)帶入加權歐氏距離模型即得到各圖片之間的匹配順序。復原416 塊碎紙片得到完整的圖像如圖4 和圖5所示。

4 結語

本模型針對圖片數(shù)量龐大，圖片匹配除了橫向的匹配拼接還有縱向的匹配拼接。利用圖片邊緣灰度值矩陣進行匹配時會產(chǎn)生龐大的數(shù)據(jù)人工難以處理。因而我們針對問題在用Matlab 提取的圖片信息后先運用聚類分析的系統(tǒng)聚類法模型進行數(shù)據(jù)分類，用人工干預對數(shù)據(jù)先左右匹配再進行上下匹配。繼而再對人工干預后的數(shù)據(jù)運用歐氏距離分析方法找出各圖片的最佳匹配對象，從而得到碎紙片復原順序，得到完整的碎紙片復原圖，為司法物證復原、歷史文獻修復以及軍事情報獲取等領域提供參考。