明 巍, 鹿秀麗

(1. 湖北師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 ，湖北 黃石 435002；2. 黃石市中心醫(yī)院 信息部，湖北 黃石 435002)

基于聚類的規(guī)則文檔碎紙片拼接模型

明 巍1, 鹿秀麗2

(1. 湖北師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 ，湖北 黃石 435002；2. 黃石市中心醫(yī)院 信息部，湖北 黃石 435002)

針對(duì)碎紙機(jī)破碎文檔后的規(guī)則碎紙片拼接問(wèn)題，通過(guò)對(duì)碎紙片上邊緣的灰度向量將文檔分為上邊緣為空白和非空白區(qū)域兩大類，再分別以上邊緣非空白區(qū)高度和空白區(qū)高度作為聚類參數(shù)，將紙片分為若干簇，在每一個(gè)簇中利用相鄰兩張碎紙片左右邊緣向量相似度來(lái)進(jìn)行拼接，得到若干橫條的紙片，然后以行距和橫條間上下邊緣相似度為參數(shù)來(lái)將若干橫條拼接為完整文檔。

K-均值聚類;碎紙片;拼接模型

破碎文件的拼接在文物碎片的自動(dòng)修復(fù)、虛擬考古、故障分析以及計(jì)算機(jī)輔助設(shè)計(jì)、醫(yī)學(xué)分析、司法物證恢復(fù)[1～2]等領(lǐng)域有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。破碎文檔的自動(dòng)拼接問(wèn)題是計(jì)算機(jī)視覺(jué)和模式識(shí)別領(lǐng)域內(nèi)的一個(gè)問(wèn)題。通過(guò)計(jì)算機(jī)處理，獲取碎紙片的形狀、顏色等內(nèi)容信息，然后利用這些內(nèi)容信息對(duì)碎紙進(jìn)行自動(dòng)拼接，恢復(fù)碎紙?jiān)嫉膬?nèi)容。

本文主要針對(duì)碎紙機(jī)破碎后的規(guī)則文檔碎紙片的拼接問(wèn)題，提出了一種基于k-均值聚類[3～5]的碎紙片拼接模型。通過(guò)提取碎紙片邊緣特征進(jìn)行聚類，將紙片分為若干簇，在每一個(gè)簇中利用相鄰兩張碎紙片左右邊緣向量相似度高來(lái)進(jìn)行拼接，得到若干橫條的紙片，然后以行距和橫條間上下邊緣相似度為參數(shù)來(lái)將若干橫條拼接為完整文檔。本文提出的基于聚類的規(guī)則文檔碎紙片拼接模型減少了邊緣向量相似度的計(jì)算次數(shù)，提高了算法的效率。

由于主要解決碎紙機(jī)破碎文件后的規(guī)則文檔碎紙片問(wèn)題，現(xiàn)將算法前提假設(shè)如下：

1)假設(shè)碎紙機(jī)對(duì)文檔的切割都是垂直和水平方向的，即碎紙片都是長(zhǎng)方形紙片。

2)假設(shè)所有碎紙片的長(zhǎng)和寬均相等。

3)假設(shè)文檔碎紙片恰好能拼成一張完整的文檔。

1 特征提取

假設(shè)一共有M×N張破碎的紙片，每張碎片的大小為m×n.對(duì)每一張碎片用灰度矩陣Ak(k=1,2,3,…,M×N)表示如下：

由于每張碎紙片分為白色區(qū)域和非白色區(qū)域，為了方便計(jì)算將碎紙片進(jìn)行二值化處理，白色區(qū)域的灰度值置為0，非白色區(qū)域的值置為1，得到對(duì)應(yīng)的布爾矩陣Bk(k=1,2, 3,…,M×N)表示如下：

提取每張碎紙片上下左右四個(gè)邊緣向量，分別用uk,dk,lk,rk(k=1,2,…,N) 表示如下：

uk=[b11,b12,b13,…,b1n]

dk=[bm1,bm2,bm3,…,bmn]

lk=[b11,b21,b31,…,bm1]

rk=[b1n,b2n,b3n,…,bmn]

若uk為零向量，則認(rèn)為碎紙片的上邊緣為空白區(qū)域，設(shè)上邊緣空白區(qū)域的高度向量

Hupblank={HUBlank1,HUBlank2,…,HUBlankp}

若uk不為零向量，則認(rèn)為碎紙片的上邊緣為文字區(qū)域，設(shè)上邊緣文字區(qū)域的高度向量

Hupword={HUWord1,HUWord2,…,HUWordq}

其中p表示μk為零向量的個(gè)數(shù)，q表示μk為非零向量的個(gè)數(shù),且p+q=M×N

同理可得到

Hdownblank={HDBlank1,HDBlank2,…,HDBlankp}

Hdownword={HDWord1,HDWord2,…,HDWordq}

Wleftblank={WLBlank1,WLBlank2,…,WLBankp}

Wleftword={WLWord1,WLWord2,…,WLWordq}

Wrightblank={WRBlank1,WRBlank2,…,WRBlankp}

Wrightword={WRWord1,WRWord2,…,WRWordq}

通過(guò)矩陣Bk列向量和行向量中連續(xù)0和連續(xù)1的個(gè)數(shù)的統(tǒng)計(jì)，并對(duì)他們的個(gè)數(shù)取眾數(shù)，得到每一行文字的高度Hword、行距Dline、寬度Wword和字間距Dword.

2 拼接方法

根據(jù)同一橫條的碎片的上邊緣一般同屬于空白區(qū)域或同屬于非空白區(qū)域，并且空白區(qū)域高度或非空白區(qū)域高度基本相同的特點(diǎn)。本文設(shè)計(jì)了一種先通過(guò)空白區(qū)域高度或非空白區(qū)域高度進(jìn)行聚類，得到有可能屬于同一橫條的碎片的集合，然后再計(jì)算邊緣向量相似度來(lái)調(diào)整碎片的位置關(guān)系的算法。

2.1基于k-均值聚類的碎紙片劃分方法

通過(guò)對(duì)碎紙片的特征提取，得到上邊緣是空白的碎片計(jì)算其空白區(qū)域的高度向量Hupblank={HUBlank1,HUBlank2,…，HUBlankp},上邊緣是非空白的碎片計(jì)算其非空白區(qū)域的高度向量Hupword={HUWord1,HUWord2,…,HUWordq} .分別對(duì)Hupblank和Hupword進(jìn)行k-均值聚類，得到可能屬于同一橫條的碎片的簇。下面以Hupword為例來(lái)描述k-均值聚類算法。

取定Hupword中的k個(gè)數(shù)據(jù)m1,m2,…,mk作為聚類中心對(duì)象，mi所代表的簇Ci是由Hupword中以mi為最近中心對(duì)象的數(shù)據(jù)構(gòu)成的集合。則k-均值聚類是找k個(gè)中心對(duì)象m1，m2,…,mk使得目標(biāo)函數(shù)

最小，其中dist(Hwordl,mi) 表示Hwordi到mi的距離。

算法：k-均值。

輸入：結(jié)果簇的數(shù)目k，Hupword包含n個(gè)對(duì)象的數(shù)據(jù)集。

輸出：k個(gè)簇的集合{C1，C2，…,Ck},使得所有對(duì)象與其最近中心對(duì)象的距離之和最小。

①初始化k個(gè)簇的中心對(duì)象集合m1，m2…mk,令m1=min(Hupword)，mk=max(Hupword) ，m2,…,mk-1任意選取，且mi≠mj(1≤i,j≤k且i≠j) ；

②根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象分配到最相似的簇；

③更新簇均值，即重新計(jì)算每個(gè)簇中對(duì)象的均值；

④重復(fù)②，③直到不再發(fā)生變化.

2.2碎紙片拼接模型

由k-均值聚類得到k個(gè)簇的集合{C1,C2,…，Ck} ，根據(jù)進(jìn)行聚類的特征，可以初步認(rèn)為每一個(gè)聚類來(lái)自同一橫條。對(duì)每個(gè)一個(gè)簇Ci中的圖片進(jìn)行橫向拼接。

建立最優(yōu)化模型，計(jì)算簇Ci內(nèi)的每張碎紙片的左右邊沿向量ri，lj的相差度d的最小值，即

目標(biāo)函數(shù)Min(d)=|ri-lj|(i,j∈[1,M×N]且ri≠0且lj≠0 ).

則當(dāng)相差度d的值最小時(shí)，這兩張碎紙片的匹配度最高。

由于簇Ci中可能存在一些并不屬于同一橫行的碎紙片被誤判在同一簇中，所以設(shè)定經(jīng)驗(yàn)閾值ξ.若Min(d)>ξ，則不進(jìn)行碎紙片的橫向拼接。

若ri=0,lj=0，則計(jì)算

similarity=|WRBlanki+WLBlankj-Dword|(i,j∈[1,M×N]且i≠j)

其中，WRBlanki∈Wrightblank,WLBlankj∈Wleftblank.

設(shè)定經(jīng)驗(yàn)閾值η，若similarity<η，則進(jìn)行拼接，否則不進(jìn)行拼接。水平拼接完成后，得到M橫條的碎紙片，記I={L1,L2,…,LM}.計(jì)算I中每一張橫條的上下邊沿向量ui,dj的相差度dis的最小值，即目標(biāo)函數(shù)Min(dis)=|ui-dj|(i,j∈[1,M×N]且i≠j且ui≠0且dj≠0)則當(dāng)相差度 dis的值最小時(shí)，這兩張橫條的匹配度最高。

若ri=0，lj=0則計(jì)算橫條的上邊緣空白區(qū)域的高度LHUBlanki和下邊緣空白區(qū)域的高度LHDBlankj.

similarity=|LHUBlanki+LHDBlankj-Dline|(i,j∈[1,M×N],i≠j)

設(shè)定經(jīng)驗(yàn)閾值λ，若similarity<λ ，則進(jìn)行拼接，否則不進(jìn)行拼接。

3 模型計(jì)算和分析

將規(guī)則文檔縱橫切碎片，被切為11×19個(gè)碎紙片。利用Matlab7.0完成碎紙片的特征提取和拼接算法。提取每張碎紙片的特征數(shù)據(jù)，根據(jù)Hupblank和Hupword兩個(gè)特征向量，利用k-均值聚類的算法劃分碎紙片，分別得到5個(gè)簇和6個(gè)簇，共11個(gè)簇，與水平切文檔的橫條數(shù)相同。

對(duì)簇內(nèi)的碎紙片左右邊緣向量作差，進(jìn)行碎紙片的相似度比較，得到每一橫條的拼接。最后通過(guò)文字高度特征和行距的特征對(duì)橫條進(jìn)行拼接，整個(gè)文檔就拼接完成了。

在碎紙片的拼接過(guò)程中，會(huì)出現(xiàn)一些誤拼接的情況，這些情況需要人工干預(yù)。如下圖1和圖2，列舉了兩種誤拼接的情況。圖1出現(xiàn)誤拼接的原因是文字被分割的位置剛好將一個(gè)文字分成了在兩個(gè)碎紙片的邊緣向量的顏色相反的情況，顯然，計(jì)算圖1(b)中的兩張碎紙片的左右邊緣向量的差值會(huì)比較大，相反圖1(a)中的兩張碎紙片的左右邊緣向量的差值比較小，這樣就引起了誤拼接。圖2出現(xiàn)誤判的原因主要是文字被分割的位置剛好在兩個(gè)字之間的間隙，圖2(a)和圖2(b)的兩張碎紙片的左右邊緣向量的差都等于0，從而引起誤拼接。

圖1 人工干預(yù)情況一

圖2 人工干預(yù)情況二

碎紙片拼接過(guò)程中雖然存在一定的誤拼接，但是總體來(lái)看，誤拼接的情況是有限的。定義誤拼率來(lái)評(píng)價(jià)模型，如下式

本文模型的誤拼率控制在20%左右，所以本文的碎片拼接模型具有比較高的效率。

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

本文在應(yīng)用上雖然有一定的局限性，但是易于操作，計(jì)算量少，在實(shí)際操作中有一定的價(jià)值。推廣到不規(guī)則的分割的拼接是這一應(yīng)用的方向，在不規(guī)則分割碎紙片的拼接中將更多的從模式識(shí)別的角度對(duì)文字本身的結(jié)構(gòu)特征提取和從語(yǔ)義的進(jìn)行拼接[6～8]。

[1]何鵬飛.基于蟻群優(yōu)化算法的碎紙片拼接[D].長(zhǎng)沙:國(guó)防科技大學(xué)，2009.

[2]賈海燕.碎紙自動(dòng)拼接關(guān)鍵技術(shù)研究[D].長(zhǎng)沙:國(guó)防科技大學(xué)，2005.

[3]Jiawei Han,Micheline Kamber,Jian Pei.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2012.

[4]吳景嵐，朱文興.基于k中心點(diǎn)的迭代局部搜索聚類算法[J].計(jì)算機(jī)研究與發(fā)展，2004,41(10):246～252.

[5]王春風(fēng)，唐擁政.結(jié)合近鄰和密度思想的K-均值算法的研究[J].計(jì)算機(jī)工程應(yīng)用，2011，47(19):147～149.

[6]羅智中.基于線段掃描的碎紙片邊界檢測(cè)算法研究[J].儀器儀表學(xué)報(bào)，2011，32(2):289～293.

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

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

Thereconstructionofpaperfragmentsofruledocumentbasedonclustering

MING Wei1, LU Xiu-li2

(1. College of Mathematics and Statistics,Hubei Normal University, Huangshi 435002,China; 2 . Huangshi Central Hospital ,Information Department, Huangshi 435002,China)

In this paper, a method that the paper fragments of rule document is reconstructed is provided. The paper fragments is divided into the upper edge of the blank and non-blank area into two categories by the gray vector on the edges.Respectively, the height of the upper edge of the blank and non-blank area as the clustering parameters is calculated.The paper fragments will be divided into several clusters. The reconstruction of paper fragments depends on computing the similarity of the left and right edges of adjacent pieces of paper in each cluster. After getting the number of bars of the paper, the paper fragments of rule document is reconstructed by computing the similarity between the top and bottom edges of the bar.

k-means clustering;paper fragments;reconstruction

2014—01—03

湖北省教育廳青年自然科學(xué)基金(Q20122203)

明巍(1983— )，湖北黃岡人，研究方向?yàn)槎嗝襟w算法、計(jì)算機(jī)技術(shù).

TP391.41

A

1009-2714(2014)03- 0079- 04

10.3969/j.issn.1009-2714.2014.03.018