尹玉萍，劉萬軍，張 沖，劉永超

YIN Yuping1,LIU Wanjun2,ZHANG Chong1,LIU Yongchao1

1.遼寧工程技術大學 電氣與控制工程學院，遼寧 葫蘆島 125105

2.遼寧工程技術大學 軟件學院，遼寧 葫蘆島 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 引言

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

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

2 匹配度矩陣

為了能有效地找出對應于原文檔的相鄰碎紙片，將每一個碎紙片的像素矩陣進行黑白二值化處理轉化為（0-1）矩陣，當像素點是白色時該位置賦值為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 基于碎紙片特征向量的動態(tài)聚類的行聚類

3.1 碎紙片特征向量

為了將碎紙片按行進行分類，即將屬于同一行的碎紙片歸為一類，定義碎紙片特征向量如下：

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

第j個碎紙片如圖1所示。

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

圖1 第j個碎紙片

3.2 基于動態(tài)聚類的行聚類

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

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

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

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

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

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

4 動態(tài)聚類的后期處理

4.1 聚類檢驗及調整

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

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

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

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

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

（3）將第 i類 jmax個 Sij對取余并求平均值，記為，則表示第i類第一行文字的中線與碎紙片上邊緣的像素數(shù)。

（5）通過圖像顯示檢驗分類是否正確，如果存在分類錯誤的碎紙片，則進行人工干預調整，直至將所有碎紙片分成m行，每行有n張碎紙片。

4.2 行間排序

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

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

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

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

在已確定所有碎紙片的行分類以及行間排序的基礎上，進行碎紙片的拼接，步驟如下：

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

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

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

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

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

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

圖3 復原后僅縱向碎紙片拼貼排列序號表

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

6 拼接實驗

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

6.1 僅縱向碎紙條拼接

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

圖4 僅縱向碎紙片拼貼前后對比圖

6.2 橫縱向均進行碎紙的單面碎紙塊拼接

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

圖5 橫縱向均進行碎紙的單面碎紙塊拼貼前后對比圖

6.3 橫縱向均進行碎紙的雙面碎紙塊拼接

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

表1 復原后橫縱向均進行碎紙的單面碎紙塊拼接序號表

圖6 復原后橫縱向均進行碎紙的雙面碎紙塊拼接序號表

圖7 橫縱向均進行碎紙的雙面碎紙塊拼貼前后對比圖

7 結束語

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

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

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

[2]王玉亮，沈建新，廖文和.基于SIFT特征的眼底圖像自動拼接[J].中國圖象圖形學報，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].中國圖象圖形學報，1996，3（1）：191-195.

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

[9]羅智中.基于線段掃描的碎紙片邊界檢測算法研究[J].儀器儀表學報，2011，32（2）：289-294.

[10]高劍，張彩明，孟祥旭，等.一種基于DDTW的三維碎片自動拼接方法[J].計算機學報，2009，32（2）：342-349.

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

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

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

[14]姜惠蘭，安敏，劉曉津，等.基于動態(tài)聚類算法徑向基函數(shù)網(wǎng)絡的配電網(wǎng)線損計算[J].中國電機工程學報，2005，25（10）：35-39.

[15]朱紅霞，沈炯，李益國.一種新的動態(tài)聚類算法及其在熱工過程模糊建模中的應用[J].中國電機工程學報，2005，25（7）：23-27.