基于聚類分析與歐氏距離模型的碎紙片拼接復原

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

（1.深圳市建設工程造價管理站 廣東省深圳市 518031 2.?？诮洕鷮W院 海南省?？谑?571127）

（3.貴州數聯銘品科技有限公司 貴州省貴陽市 550005 4.中交一航局生態工程有限公司 廣東省深圳市 518000）

1 引言

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

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

2 問題的思路分析

2.1 問題的分析

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

3 模型的建立與求解

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

3.1 運用系統聚類法模型對數據進行分類

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

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

圖2：人工干預界面

圖3：ab 之間的歐氏距離

圖4：中文碎片復原圖

圖5：英文碎片復原圖

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

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

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

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

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

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

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

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

對眾多數據采用系統聚類法進行分類得到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)間的歐氏距離：

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

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

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

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

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

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

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

4 結語

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