基于聚類分析的雙面文檔半自動(dòng)拼接

梁慧超　于紅斌　喬路遙　崔玉亮

摘 要：針對(duì)雙面規(guī)格碎片，提出了一種基于聚類分析的半自動(dòng)拼接方法。根據(jù)碎片邊緣的文字特征，構(gòu)造碎片的相似性判別函數(shù)，進(jìn)行最大相似性判別并聚類分析，找到同一行的碎片排列，最終實(shí)現(xiàn)了文檔的橫向、縱向拼接，在MATLAB下的實(shí)驗(yàn)表明該算法效率高，相對(duì)人工干預(yù)少。

關(guān)鍵詞：聚類分析；邊緣特征提??；碎紙片拼接

碎紙片的人工拼接復(fù)工作效率很低，隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。目前，國(guó)內(nèi)外在碎片拼接技術(shù)的研究中已經(jīng)取得了一定的成就，如：Ying Shan等提出了一種概率框架的曲線匹配算法[1]，李軍等人提出一種改進(jìn)Harris算子的圖像拼接方法[2]，何鵬飛等人提出了基于蟻群優(yōu)化算法的碎片拼接技術(shù)[3]，但這些算法主要解決單面不規(guī)則碎片的輪廓提取及匹配上，對(duì)于碎片雙面均有文字且碎片數(shù)量巨大的情況難以適用。

針對(duì)當(dāng)前圖像拼接技術(shù)的缺陷，本文充分利用文字行的行高、文字行的間距等信息，對(duì)碎片進(jìn)行分類，并綜合采用相似性判別函數(shù)和聚類分析，最終將同一行的碎片劃為一類，拼接時(shí)利用碎紙片的邊界矩陣，進(jìn)行最小絕對(duì)值距離判別，從形狀相似的多碎片中挑選出相鄰碎片。該方法便于理解，利用MATLAB軟件，容易實(shí)現(xiàn)。

1 拼接原理

碎片拼接由于碎片數(shù)目過(guò)多，故不能人為的進(jìn)行全過(guò)程拼接。首先要將根據(jù)碎片特征利用相似性判別函數(shù)分進(jìn)行分類，然后利用聚類分析將屬于同一面同一行的碎片聚成一類，在人工篩選劃錯(cuò)行的圖片后，對(duì)碎紙片進(jìn)行橫向和縱向拼接即可。

聚類分析是一組將研究對(duì)象分為相對(duì)同質(zhì)的群組的統(tǒng)計(jì)分析技術(shù)，其依據(jù)研究對(duì)象（樣品或指標(biāo)）的特征，對(duì)研究對(duì)象進(jìn)行分類，達(dá)到減少研究對(duì)象的數(shù)目的目的。因?yàn)槲臋n的行高、字間距具有一定規(guī)律性，因此可以依據(jù)每張碎片的特征，進(jìn)行聚類分析。

2 拼接步驟

2.1 觀察碎片特征

通過(guò)觀察碎片，根據(jù)碎片中完整文字行數(shù)、完整空白行數(shù)，碎片上方是否為空白、碎片下方是否為空白等特征人工將碎片分為N類。以文獻(xiàn)[5]中數(shù)據(jù)為例，a有3行完整文字、兩行完整空白、上方為空白、下方為空白；b有兩行完整文字、兩行完整空白、碎片上方為空白、碎片下方不為空白；c有兩行完整文字、兩行完整空白、碎片上方不為空白、碎片下方為空白，這3張碎片分別屬于3大類。

人為地將文檔分為N類后，挑選出屬于每一類的碎片一張作為比較對(duì)象，任意碎片Si的特征矢量，求每一個(gè)碎片在第i類碎片上的矢量與該矢量上的特征矢量的距離，進(jìn)行最大相似性判別，為每一碎片分類。但由于文檔的雙面性，可能會(huì)存在差錯(cuò)，為了讓位于同一面同一行的碎片聚在一起，在劃分好的每一類中，提取各個(gè)碎片的反面進(jìn)行聚類分析，將這些碎片分為m類后，仍需要人工將少數(shù)不屬于該行的碎片劃分開(kāi)來(lái)。

2.2 相鄰碎片拼接

若想要找出其左鄰碎紙片，只需提取每個(gè)碎紙片像素矩陣最左邊的一列和最右邊的一列，記每個(gè)碎紙片的像素矩陣中的最左邊一列為ιi，同理，提取每個(gè)碎紙片的最右邊一列為ri，計(jì)算兩碎片的相關(guān)程度時(shí)，可以用絕對(duì)值距離[3]表示，此時(shí)的目標(biāo)函數(shù)即求下式的最小值：

其中，xik表示像素矩陣第k行的ιi的值，yik表示ri的第k行的值。當(dāng)k從第1行取到第最后一行時(shí)，若此差值的絕對(duì)值和最小，則表示兩個(gè)左右兩個(gè)邊緣的相似性越高，即可認(rèn)為這兩個(gè)矩陣是左右相鄰的即可確定每個(gè)碎紙片左右相鄰的碎紙片，從而獲得橫向同一行上各碎片的排列順序，同理，用同樣方法可獲得縱向各行的排列順序，從而得到拼接復(fù)原的完整圖像。

3 拼接試驗(yàn)

根據(jù)該算法研制了MATLAB程序，并對(duì)一實(shí)際碎紙片進(jìn)行了拼接試驗(yàn)。將碎紙片平均切割為418塊，根據(jù)文字行的分布形式及空白行高人為的將碎紙片分為5類，用MATLAB中的相似度函數(shù)對(duì)418張碎片做相似處理并用SPSS對(duì)該矩陣做聚類分析，然后施加人工干預(yù)，將這些圖片插入到正確的行類中，最后進(jìn)行橫向縱向拼接。拼接結(jié)果的部分圖像見(jiàn)圖2。

試驗(yàn)表明本文提出的半自動(dòng)拼接算法誤差率較小。

4 結(jié)束語(yǔ)

本文提出了基于聚類分析的雙面文檔碎片半自動(dòng)拼接方法，實(shí)現(xiàn)簡(jiǎn)單，但只適用于橫向、縱向切割的文檔碎紙片的拼接，需要加入兩次人工干預(yù)。

碎片文件的拼接在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用，在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)、軍事情報(bào)獲取、虛擬仿真培訓(xùn)、工業(yè)制造設(shè)計(jì)等領(lǐng)域，有一定的指導(dǎo)意義。

[參考文獻(xiàn)]

[1]Ying Shan etc.New Measurements and Corner一Guidance for Curve Matching With Probabilistic Relaxation[J].International Journal of Computer Vision.2002，46（2）：157-171.

[2]李軍，吳潔明.一種改進(jìn)圖像拼接算法的仿真研究[J].計(jì)算機(jī)仿真，2012，29（2）：273-313.

[3]何鵬飛.基于蟻群優(yōu)化算法的碎紙拼接[D].國(guó)防科學(xué)技術(shù)大學(xué)，2005.

[4]程永清，莊永明，楊靜宇.基于矩陣相似度的圖像特征抽取和識(shí)別[J].計(jì)算機(jī)研究與發(fā)展，1992，14（5）：42-48.

[5]全國(guó)大學(xué)生數(shù)學(xué)建模（官網(wǎng)）.2013賽題：[DB/OL]，教育部高等教育司和中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)協(xié)會(huì)，2013[2013-9-11].http：//www.mcm.edu.cn/problem/2013/2013.html.

[6]羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（5）：207-210.