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

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

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

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

1 引言

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

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

2 問題的思路分析

2.1 問題的分析

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

3 模型的建立與求解

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

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

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

圖1：z，y 矩陣各列標(biāo)準(zhǔn)值散點圖

圖2：人工干預(yù)界面

圖3：ab 之間的歐氏距離

圖4：中文碎片復(fù)原圖

圖5：英文碎片復(fù)原圖

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

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

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

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

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

得出的標(biāo)準(zhǔn)值散點圖如圖1所示。

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

3.2 運用歐氏距離模型進行相關(guān)性分析與匹配

對眾多數(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ù)各維分量的分布不一樣。所以我們引用標(biāo)準(zhǔn)化歐氏距離。

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

標(biāo)準(zhǔn)化后的值= （標(biāo)準(zhǔn)化前的值-分量的均值） /分量的標(biāo)準(zhǔn)差.

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

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

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

4 結(jié)語

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