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

明 巍, 鹿秀麗

(1. 湖北師范學院 數學與統計學院 ，湖北 黃石 435002；2. 黃石市中心醫院 信息部，湖北 黃石 435002)

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

明 巍1, 鹿秀麗2

(1. 湖北師范學院 數學與統計學院 ，湖北 黃石 435002；2. 黃石市中心醫院 信息部，湖北 黃石 435002)

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

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

破碎文件的拼接在文物碎片的自動修復、虛擬考古、故障分析以及計算機輔助設計、醫學分析、司法物證恢復[1～2]等領域有著重要的應用。傳統上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數量巨大，人工拼接很難在短時間內完成任務。隨著計算機技術的發展，人們試圖開發碎紙片的自動拼接技術，以提高拼接復原效率。破碎文檔的自動拼接問題是計算機視覺和模式識別領域內的一個問題。通過計算機處理，獲取碎紙片的形狀、顏色等內容信息，然后利用這些內容信息對碎紙進行自動拼接，恢復碎紙原始的內容。

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

由于主要解決碎紙機破碎文件后的規則文檔碎紙片問題，現將算法前提假設如下：

1)假設碎紙機對文檔的切割都是垂直和水平方向的，即碎紙片都是長方形紙片。

2)假設所有碎紙片的長和寬均相等。

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

1 特征提取

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

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

提取每張碎紙片上下左右四個邊緣向量，分別用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為零向量，則認為碎紙片的上邊緣為空白區域，設上邊緣空白區域的高度向量

Hupblank={HUBlank1,HUBlank2,…,HUBlankp}

若uk不為零向量，則認為碎紙片的上邊緣為文字區域，設上邊緣文字區域的高度向量

Hupword={HUWord1,HUWord2,…,HUWordq}

其中p表示μk為零向量的個數，q表示μk為非零向量的個數,且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}

通過矩陣Bk列向量和行向量中連續0和連續1的個數的統計，并對他們的個數取眾數，得到每一行文字的高度Hword、行距Dline、寬度Wword和字間距Dword.

2 拼接方法

根據同一橫條的碎片的上邊緣一般同屬于空白區域或同屬于非空白區域，并且空白區域高度或非空白區域高度基本相同的特點。本文設計了一種先通過空白區域高度或非空白區域高度進行聚類，得到有可能屬于同一橫條的碎片的集合，然后再計算邊緣向量相似度來調整碎片的位置關系的算法。

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

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

取定Hupword中的k個數據m1,m2,…,mk作為聚類中心對象，mi所代表的簇Ci是由Hupword中以mi為最近中心對象的數據構成的集合。則k-均值聚類是找k個中心對象m1，m2,…,mk使得目標函數

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

算法：k-均值。

輸入：結果簇的數目k，Hupword包含n個對象的數據集。

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

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

②根據簇中對象的均值，將每個對象分配到最相似的簇；

③更新簇均值，即重新計算每個簇中對象的均值；

④重復②，③直到不再發生變化.

2.2碎紙片拼接模型

由k-均值聚類得到k個簇的集合{C1,C2,…，Ck} ，根據進行聚類的特征，可以初步認為每一個聚類來自同一橫條。對每個一個簇Ci中的圖片進行橫向拼接。

建立最優化模型，計算簇Ci內的每張碎紙片的左右邊沿向量ri，lj的相差度d的最小值，即

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

則當相差度d的值最小時，這兩張碎紙片的匹配度最高。

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

若ri=0,lj=0，則計算

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

其中，WRBlanki∈Wrightblank,WLBlankj∈Wleftblank.

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

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

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

設定經驗閾值λ，若similarity<λ ，則進行拼接，否則不進行拼接。

3 模型計算和分析

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

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

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

圖1 人工干預情況一

圖2 人工干預情況二

碎紙片拼接過程中雖然存在一定的誤拼接，但是總體來看，誤拼接的情況是有限的。定義誤拼率來評價模型，如下式

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

4 結束語

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

[1]何鵬飛.基于蟻群優化算法的碎紙片拼接[D].長沙:國防科技大學，2009.

[2]賈海燕.碎紙自動拼接關鍵技術研究[D].長沙:國防科技大學，2005.

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

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

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

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

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

[8]朱延娟，周來水.二維非規則碎片的匹配算法[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

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

明巍(1983— )，湖北黃岡人，研究方向為多媒體算法、計算機技術.

TP391.41

A

1009-2714(2014)03- 0079- 04

10.3969/j.issn.1009-2714.2014.03.018