基于動(dòng)態(tài)聚類(lèi)的文檔碎紙片自動(dòng)拼接算法

尹玉萍，劉萬(wàn)軍，張 沖，劉永超

YIN Yuping1,LIU Wanjun2,ZHANG Chong1,LIU Yongchao1

1.遼寧工程技術(shù)大學(xué) 電氣與控制工程學(xué)院，遼寧 葫蘆島 125105

2.遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105

1.School of Electrical and Control Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China

2.School of Software,Liaoning Technical University,Huludao,Liaoning 125105,China

1 引言

碎紙片自動(dòng)拼接技術(shù)是圖像處理與模式識(shí)別領(lǐng)域中的一個(gè)較新但是很典型的應(yīng)用[1]，它是通過(guò)掃描和圖像提取技術(shù)獲取一組碎紙片的形狀、顏色等信息[2-4]，然后利用計(jì)算機(jī)進(jìn)行相應(yīng)的處理從而實(shí)現(xiàn)對(duì)這些碎紙片的全自動(dòng)或半自動(dòng)拼接還原[5-7]。二維碎紙片自動(dòng)拼接問(wèn)題主要有兩種解決方案：基于輪廓的拼接和基于內(nèi)容的拼接[8]。前者類(lèi)似的研究較多一些，例如羅智中提出的基于線(xiàn)段掃描的碎紙片邊界檢測(cè)算法研究[9]，高劍，張彩明，孟祥旭，馮志全提出的一種基于DDTW的三維碎片自動(dòng)拼接方法[10]，朱延娟，周來(lái)水，劉毅提出的二維非規(guī)則碎片匹配的算法[11]，劉金根，吳志鵬，劉上乾，殷世民提出的一種基于特征區(qū)域分割的圖像拼接算法[12]等等。目前，對(duì)于基于內(nèi)容的文檔拼接研究的論文還比較少，但還是有一些，例如羅智中提出的基于文字特征的文檔碎紙片半自動(dòng)拼接[13]等。在碎紙拼接技術(shù)中，從目前的研究現(xiàn)狀來(lái)看，雖然很多的文獻(xiàn)都在這方面做了大量的研究工作，但是迄今為止，仍然沒(méi)有很成熟的方法應(yīng)用于相關(guān)工作中。

為此，本文主要針對(duì)碎紙機(jī)撕碎紙片的三種形式進(jìn)行自動(dòng)拼接和復(fù)原，即分別對(duì)僅縱向碎紙條、橫縱向均進(jìn)行碎紙的單面碎紙塊和橫縱向均進(jìn)行碎紙的雙面碎紙塊，開(kāi)展基于動(dòng)態(tài)聚類(lèi)的文檔碎紙片自動(dòng)拼接算法研究。（1）首先利用定義的行匹配度矩陣解決僅縱切問(wèn)題。（2）在橫縱向均進(jìn)行碎紙的單面碎紙塊的拼接問(wèn)題中，首先求出所有碎紙片的特征向量，以特征向量為聚類(lèi)依據(jù)進(jìn)行動(dòng)態(tài)聚類(lèi)，初步找出哪些碎紙片屬于同一行，然后再根據(jù)碎紙片的特征線(xiàn)進(jìn)行動(dòng)態(tài)聚類(lèi)的后期處理，確定出最終的行分類(lèi)，以及行間排序。利用定義的行匹配度矩陣和列匹配度矩陣，結(jié)合提出的動(dòng)態(tài)聚類(lèi)的四鄰近拼接算法，匹配出每一行碎紙片的行內(nèi)排列順序，最后得到整篇文檔的拼接結(jié)果。（3）對(duì)于橫縱向均進(jìn)行碎紙的雙面碎紙塊的拼接問(wèn)題中，在解決第二種碎紙片問(wèn)題的基礎(chǔ)上，求出行分類(lèi)和行間排序后，考慮到正反兩面均有匹配信息，將待匹配碎紙片的正反面匹配度平均值作為匹配依據(jù)，根據(jù)動(dòng)態(tài)聚類(lèi)的四鄰近拼接算法進(jìn)行拼接。實(shí)驗(yàn)表明，該方法參數(shù)少實(shí)現(xiàn)簡(jiǎn)單有效，能快速得到上述三種碎紙片的拼接復(fù)原結(jié)果。

2 匹配度矩陣

為了能有效地找出對(duì)應(yīng)于原文檔的相鄰碎紙片，將每一個(gè)碎紙片的像素矩陣進(jìn)行黑白二值化處理轉(zhuǎn)化為（0-1）矩陣，當(dāng)像素點(diǎn)是白色時(shí)該位置賦值為0，否則該位置賦值為1，并由此定義行、列匹配度矩陣如下。

定義1若將原文檔碎成m×n塊碎片，則行匹配度矩陣記為 Match1=(mij)m×n，其中

行匹配度矩陣元素mij主要體現(xiàn)了碎紙片i的右邊緣與碎紙片 j的左邊緣的匹配程度。

定義2若將原文檔碎成m×n塊碎片，則列匹配度矩陣記為 Match2=(nij)m×n，其中

列匹配度矩陣元素nij主要體現(xiàn)了碎紙片i的下邊緣與碎紙片 j的上邊緣的匹配程度。

3 基于碎紙片特征向量的動(dòng)態(tài)聚類(lèi)的行聚類(lèi)

3.1 碎紙片特征向量

為了將碎紙片按行進(jìn)行分類(lèi)，即將屬于同一行的碎紙片歸為一類(lèi)，定義碎紙片特征向量如下：

定義3設(shè)每頁(yè)紙被切為m×n個(gè)碎片，每個(gè)碎紙片的像素?cái)?shù)為r×l，將全部m×n張碎片進(jìn)行黑白二值化處理后，若第 j個(gè)碎紙片的第i行為純白色行時(shí)該行標(biāo)記vi=0；否則該行標(biāo)記 vi=1，則稱(chēng)向量 cvj=[v1，v2，…，vr]T為第 j個(gè)碎紙片的特征向量，其中 vi∈{0，1}，i=1,2,…，r。

第j個(gè)碎紙片如圖1所示。

其中22是全零行的行數(shù)，35是非零行的行數(shù)，以此類(lèi)推得到所對(duì)應(yīng)的碎紙片特征向量為：

圖1 第j個(gè)碎紙片

3.2 基于動(dòng)態(tài)聚類(lèi)的行聚類(lèi)

由于處于同一行的碎紙片中文字所占位置是相似的，所以文件中屬于同一行的碎片的特征向量相似度較大。據(jù)此，對(duì)所有碎片基于其特征向量進(jìn)行動(dòng)態(tài)聚類(lèi)[14-15]，初步找出在同一行的碎紙片。設(shè)該聚類(lèi)樣本集合為CV={cv1，cv2，…，cvmn}，其中 cvj=[v1，v2，…，vr]T為第 j個(gè)聚類(lèi)樣本。

動(dòng)態(tài)聚類(lèi)的行聚類(lèi)具體算法步驟如下：

（1）選定一個(gè)合適的動(dòng)態(tài)聚類(lèi)閾值γ，原文有m行，所以選取γ的依據(jù)為使分類(lèi)數(shù)k大于等于m，且每類(lèi)包含碎片個(gè)數(shù)小于等于n。之所以存在k＞m的情況是因?yàn)榭紤]到一些特殊的碎片可能不會(huì)準(zhǔn)確歸類(lèi)問(wèn)題。并設(shè)初始聚類(lèi)數(shù)k=1，聚類(lèi)重心初始值z(mì)1為第一個(gè)輸入樣本。

（2）計(jì)算第1個(gè)聚類(lèi)重心與第2個(gè)樣本之間的距離d21。如果d21＞γ，聚類(lèi)數(shù)k=2，第2類(lèi)的聚類(lèi)重心為第2個(gè)樣本；否則第2個(gè)樣本歸于第1類(lèi)當(dāng)中。為防止聚類(lèi)重心飄移對(duì)該算法的影響，采取將聚類(lèi)重心保持不變策略。

（3）依次計(jì)算剩下樣本與已有的k個(gè)聚類(lèi)重心之間的最小距離dij。如果dij＞γ，聚類(lèi)數(shù)為k=k+1，第k+1類(lèi)的聚類(lèi)重心為第i個(gè)樣本。否則，第i個(gè)樣本就屬于第 j類(lèi)，聚類(lèi)重心不變。

（4）將所有樣本進(jìn)行聚類(lèi)完畢后，若k＜m，返回步驟（1）。若k≥m，則k即為最后的聚類(lèi)數(shù)，zj(j=1,2,…,k)為對(duì)應(yīng)的聚類(lèi)重心。

4 動(dòng)態(tài)聚類(lèi)的后期處理

4.1 聚類(lèi)檢驗(yàn)及調(diào)整

如果k=m，檢驗(yàn)分類(lèi)是否正確，即判斷每類(lèi)是否有n張碎紙片，并且同一行碎紙片的漢字中線(xiàn)是否在同一水平線(xiàn)。否則進(jìn)行如下操作：

（1）將每一類(lèi)中所有碎紙片看作一個(gè)新的碎紙片，根據(jù)3.1節(jié)的定義3求其特征向量。

（2）求出每一類(lèi)碎紙片所有完整文字行的中線(xiàn)到碎紙片上邊緣的像素?cái)?shù) Sij，i=1，2，…，k;j=1，2，…，jmax，其中 jmax表示第i類(lèi)碎紙片中完整文字行的行數(shù)，為了減少工作量，從第i類(lèi)碎紙片中第一行完整文字，計(jì)算其所占像素?cái)?shù)ui，并取第一行完整空白行，計(jì)算其所占像素?cái)?shù)vi。其中，完整文字行表示該類(lèi)碎紙片的特征向量?jī)山M相鄰“0”之間“1”的個(gè)數(shù)；完整空白行表示該類(lèi)碎紙片的特征向量?jī)山M相鄰“1”之間“0”的個(gè)數(shù)。

然后，將k個(gè)類(lèi)中選出的ui與vi分別取平均值，記為uˉ和vˉ，分別作為整個(gè)文檔文字字體大小與行間距的平均度量。

例如圖1所示碎紙片，假設(shè)已按照3.2節(jié)方法將其所在的類(lèi)找出并且該類(lèi)同圖1碎紙片具有兩行完整文字，則 jmax=2，Si1=35/2+22=39.5，Si2=40/2+22+35+30=107；ui=35，vi=30。

（3）將第 i類(lèi) jmax個(gè) Sij對(duì)取余并求平均值，記為，則表示第i類(lèi)第一行文字的中線(xiàn)與碎紙片上邊緣的像素?cái)?shù)。

（5）通過(guò)圖像顯示檢驗(yàn)分類(lèi)是否正確，如果存在分類(lèi)錯(cuò)誤的碎紙片，則進(jìn)行人工干預(yù)調(diào)整，直至將所有碎紙片分成m行，每行有n張碎紙片。

4.2 行間排序

在4.1節(jié)的基礎(chǔ)之上，對(duì)行與行之間的順序進(jìn)行排列。進(jìn)行如下操作：

（1）將所有碎紙片分成m類(lèi)后，按3.2節(jié)所述步驟（1）～（3）得到每類(lèi)碎紙片的。

（2）按如下公式判斷第i類(lèi)碎紙片與第 j類(lèi)碎紙片是否屬于相鄰行：

5 基于動(dòng)態(tài)四鄰近拼接算法

在已確定所有碎紙片的行分類(lèi)以及行間排序的基礎(chǔ)上，進(jìn)行碎紙片的拼接，步驟如下：

（1）從第一行中找出處于第一列和最后一列位置的碎紙片，根據(jù)Match1矩陣元素的定義和一般文檔碎紙片的特點(diǎn)可以得到原文檔兩個(gè)邊緣的相應(yīng)碎紙片，當(dāng)碎紙片a的右邊緣與碎紙片b的左邊緣均無(wú)文字時(shí)，其對(duì)應(yīng)（0-1）矩陣相應(yīng)的列元素均為0，此時(shí)匹配度mab=1，可以以較大概率判斷出碎紙片a為最后一列的碎紙片，碎紙片b為第一列的碎紙片，并將兩個(gè)位置的碎紙片標(biāo)號(hào)存放到碎紙片排序矩陣 pic=(picij)m×n當(dāng)中。表示如下：

（2）以當(dāng)前確定好位置的碎紙片排序矩陣 pic為基礎(chǔ)，計(jì)算所有待匹配區(qū)域的四鄰近加權(quán)匹配度。為了對(duì)一般情況進(jìn)行討論，以圖2中左側(cè)第k次循環(huán)的效果圖為例進(jìn)行說(shuō)明，其中，畫(huà)斜線(xiàn)陰影的方框表示已放入 pic矩陣的碎紙片，箭頭所指空白區(qū)域?yàn)榇ヅ鋮^(qū)域，例如 pichg表示第h行且第g列位置的待匹配區(qū)域所要得到的碎紙片，在第h類(lèi)未匹配的碎片當(dāng)中，求出第h行第g列待匹配區(qū)域與周邊已經(jīng)匹配完碎片的加權(quán)匹配度最大的碎紙片。其中加權(quán)匹配度有兩種情況：

①待匹配區(qū)域與一邊相鄰，其加權(quán)匹配度即為與相鄰一側(cè)碎紙片的匹配度。如 pic15所在待匹配區(qū)域的位置與左邊匹配即可。

②待匹配區(qū)域與多邊相鄰，其加權(quán)匹配度即為與各相鄰側(cè)已匹配完碎紙片的行列匹配度和上下匹配度的加權(quán)平均值，其權(quán)重與該邊長(zhǎng)度成正比。如 pic34、pic22所在待匹配區(qū)域的位置。

（3）比較第（2）步中所有已選出的碎紙片四鄰近加權(quán)匹配度大小，找出最大值對(duì)應(yīng)的碎紙片，并將其添入pic矩陣中。假設(shè) pic15位置的四鄰近加權(quán)匹配度是最大的，則將其位置填上，如圖2右側(cè)第(k+1)次循環(huán)的效果圖。通過(guò)圖像顯示檢驗(yàn)拼接是否正確，如果不正確，暫停程序，并在該行余下的碎紙片中按照匹配度由大到小依次尋找，直到找到正確匹配的碎紙片。如果正確，轉(zhuǎn)下一步。

圖2 程序第k次循環(huán)和第k+1次循環(huán)匹配效果圖

圖3 復(fù)原后僅縱向碎紙片拼貼排列序號(hào)表

（4）判斷所有碎紙片是否均已填入 pic矩陣中，如果沒(méi)有，返回步驟（2）繼續(xù)循環(huán)，否則循環(huán)結(jié)束。

6 拼接實(shí)驗(yàn)

為檢驗(yàn)本文提出的基于動(dòng)態(tài)聚類(lèi)的文檔碎紙片自動(dòng)拼接算法的可行性和有效性，實(shí)驗(yàn)在計(jì)算機(jī)ThinkPad-SL510k上實(shí)踐，操作系統(tǒng)是Windows XP，主頻2.20 GHz，利用Matlab7.5.0運(yùn)行程序。本文以2013年“高教社”杯全國(guó)數(shù)學(xué)建模競(jìng)賽B題為驗(yàn)證對(duì)象。

6.1 僅縱向碎紙條拼接

由于該問(wèn)題中m=1，n=19為簡(jiǎn)單問(wèn)題，屬于上述算法的簡(jiǎn)單特例，具體操作時(shí)無(wú)需運(yùn)用動(dòng)態(tài)聚類(lèi)進(jìn)行行聚類(lèi)和行間排序，僅需使用行匹配度矩陣得到如下結(jié)果，在匹配過(guò)程中沒(méi)有人工干預(yù)，正確率為100%。復(fù)原后僅縱向碎紙片拼貼排列序號(hào)表如圖3所示。僅縱向碎紙片拼貼前后對(duì)比圖如圖4所示。

圖4 僅縱向碎紙片拼貼前后對(duì)比圖

6.2 橫縱向均進(jìn)行碎紙的單面碎紙塊拼接

該問(wèn)題中，m=11，n=19，設(shè)動(dòng)態(tài)聚類(lèi)閾值γ=5，判定兩行碎紙片是否相鄰的閾值δ=2。利用本文所提算法得到如表1及圖5的復(fù)原結(jié)果，在匹配過(guò)程中人工干預(yù)12個(gè)碎紙片，共209個(gè)碎紙片，故正確率為94.3%。

圖5 橫縱向均進(jìn)行碎紙的單面碎紙塊拼貼前后對(duì)比圖

6.3 橫縱向均進(jìn)行碎紙的雙面碎紙塊拼接

此題中同樣m=11，n=19，動(dòng)態(tài)聚類(lèi)閾值γ=5，判定兩行碎紙片是否相鄰的閾值δ=2，區(qū)別于6.2節(jié)的是碎紙片是雙面的（同一序號(hào)分a、b兩種，表示同一碎紙片的正反兩面），使得碎紙片信息量增大，更方便進(jìn)行行聚類(lèi)以及行間排序，在進(jìn)行基于動(dòng)態(tài)聚類(lèi)的四鄰近拼接時(shí)，將碎紙片的正反兩面同時(shí)進(jìn)行加權(quán)匹配拼接，大大減少了人工干預(yù)的幾率，得到如圖6及圖7的復(fù)原結(jié)果。其中圖6的上圖為正面的碎片序號(hào)排序，圖6下圖為反面的碎片序號(hào)排序，且上圖第i行從左到右的順序?yàn)檫@一行的正面碎片排序，下圖為上圖的左右180°翻轉(zhuǎn)，且碎紙片進(jìn)行相應(yīng)翻轉(zhuǎn)（即序號(hào)不變，a、b互換），得到其反面排序，例如圖6上圖中，第2行第2列的152b翻轉(zhuǎn)得到下圖的第2行第18列的152a，它們是原文當(dāng)中同一個(gè)碎紙片的正反面。在匹配過(guò)程中人工干預(yù)9個(gè)碎紙片，共209個(gè)碎紙片，故正確率為95.7%。

表1 復(fù)原后橫縱向均進(jìn)行碎紙的單面碎紙塊拼接序號(hào)表

圖6 復(fù)原后橫縱向均進(jìn)行碎紙的雙面碎紙塊拼接序號(hào)表

圖7 橫縱向均進(jìn)行碎紙的雙面碎紙塊拼貼前后對(duì)比圖

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

本文針對(duì)碎紙機(jī)撕碎紙片的三種形式，提出了基于動(dòng)態(tài)聚類(lèi)的文檔碎紙片自動(dòng)拼接算法，即分別對(duì)僅縱向碎紙條、橫縱向均進(jìn)行碎紙的單面碎紙塊和橫縱向均進(jìn)行碎紙的雙面碎紙塊，進(jìn)行自動(dòng)拼接和復(fù)原。為了初步解決碎紙片的行聚類(lèi)問(wèn)題本文提出了基于碎紙片特征向量的動(dòng)態(tài)聚類(lèi)方法；為了提高拼接的效率和復(fù)原的成功率，提出以同行碎紙片的特征向量及文字中心線(xiàn)為依據(jù)，進(jìn)行動(dòng)態(tài)聚類(lèi)的后期處理，確定出最終的行分類(lèi)以及行間排序，減少了搜索的范圍；在確定出最終的行分類(lèi)以及行間排序后，為了得出每一行碎紙片的行內(nèi)排列順序，最后得到整篇文檔的拼接結(jié)果，提出了四鄰近匹配的拼接算法。

對(duì)上述三種模式的碎紙片拼接算法驗(yàn)證可以看出，該算法不僅可用于漢字文檔的拼接，而且也可用于英文文檔的拼接。該算法能快速有效解決矩形碎片拼接問(wèn)題，人工干預(yù)很少，成功幾率較大。若匹配時(shí)加入文字模式識(shí)別算法，將更加完善該算法，這也是今后的努力方向。隨著碎紙片拼接技術(shù)的成熟，一定會(huì)給相關(guān)行業(yè)帶來(lái)極大的方便。

[1]賈海燕，朱良家，周宗潭，等.一種碎紙自動(dòng)拼接中的形狀匹配方法[J].計(jì)算機(jī)仿真，2006，23（11）：180-183.

[2]王玉亮，沈建新，廖文和.基于SIFT特征的眼底圖像自動(dòng)拼接[J].中國(guó)圖象圖形學(xué)報(bào)，2011，16（4）：654-659.

[3]Gama Leitao H C，Stolfi J.A method for the reassembly of two-dimensional fragmented objects[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（9）：1239-1251.

[4]Kong W，Kimia B B.On solving 2D and 3D puzzles using curve matching[C]//Proceedings of the CVPR，Hawaii，USA，2001：583-590.

[5]Pan Rongjiang，Meng Xiangxu，Tu Changhe.Fragment reassembly based on LCS matching[J].Chinese Journal of Computers，2005，28（3）：350-356.

[6]Dabak A G，Schmidl T，Sengupta C.Equalizaiton and multi user detection for Space Time block coding based Transmit Diversity（STTD）in frequency selective channels[C]//IEEE VTS Fall VTC 2000，2000：506-513.

[7]王磊，莫玉龍，戚飛虎.基于Canny理論的邊緣提取改善方法[J].中國(guó)圖象圖形學(xué)報(bào)，1996，3（1）：191-195.

[8]何鵬飛，周宗潭，胡德文.基于蟻群優(yōu)化算法的碎紙拼接[J].計(jì)算機(jī)工程與科學(xué)，2011，33（7）：67-73.

[9]羅智中.基于線(xiàn)段掃描的碎紙片邊界檢測(cè)算法研究[J].儀器儀表學(xué)報(bào)，2011，32（2）：289-294.

[10]高劍，張彩明，孟祥旭，等.一種基于DDTW的三維碎片自動(dòng)拼接方法[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（2）：342-349.

[11]朱延娟，周來(lái)水，劉毅.二維非規(guī)則碎片匹配的算法[J].計(jì)算機(jī)工程，2007，33（24）：7-9.

[12]劉金根，吳志鵬，劉上乾，等.一種基于特征區(qū)域分割的圖像拼接算法[J].西安電子科技大學(xué)學(xué)報(bào)，2002，29（6）：768-771.

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

[14]姜惠蘭，安敏，劉曉津，等.基于動(dòng)態(tài)聚類(lèi)算法徑向基函數(shù)網(wǎng)絡(luò)的配電網(wǎng)線(xiàn)損計(jì)算[J].中國(guó)電機(jī)工程學(xué)報(bào)，2005，25（10）：35-39.

[15]朱紅霞，沈炯，李益國(guó).一種新的動(dòng)態(tài)聚類(lèi)算法及其在熱工過(guò)程模糊建模中的應(yīng)用[J].中國(guó)電機(jī)工程學(xué)報(bào)，2005，25（7）：23-27.