尹玉萍，劉萬(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)似的研究較多一些，例如羅智中提出的基于線段掃描的碎紙片邊界檢測(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ù)碎紙片的特征線進(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張碎紙片，并且同一行碎紙片的漢字中線是否在同一水平線。否則進(jìn)行如下操作：

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

（2）求出每一類(lèi)碎紙片所有完整文字行的中線到碎紙片上邊緣的像素?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)第一行文字的中線與碎紙片上邊緣的像素?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à)斜線陰影的方框表示已放入 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ù)原的成功率，提出以同行碎紙片的特征向量及文字中心線為依據(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]羅智中.基于線段掃描的碎紙片邊界檢測(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)線損計(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.