邵春雨，胡方濤，程明輝，李厚彪

(電子科技大學(xué) a. 光電信息學(xué)院； b.數(shù)學(xué)科學(xué)學(xué)院，成都 611731)

·學(xué)生實(shí)驗(yàn)園地·

基于邊界像素匹配的碎片拼接問題研究

邵春雨a，胡方濤b，程明輝b，李厚彪b

(電子科技大學(xué) a. 光電信息學(xué)院； b.數(shù)學(xué)科學(xué)學(xué)院，成都 611731)

文中針對碎紙機(jī)破碎紙片的雙面文字拼接復(fù)原問題，以邊界像素數(shù)據(jù)差值最小為優(yōu)化目標(biāo)，建立0-1規(guī)劃模型，并設(shè)計了實(shí)現(xiàn)拼接復(fù)原的算法。與以往人工拼接不同，所設(shè)計算法采用分治思想將拼接過程分為橫向和縱向，借助Matlab進(jìn)行機(jī)器拼接，并利用邊界像素匹配得到機(jī)器拼接規(guī)則。實(shí)驗(yàn)結(jié)果表明，該方法可以高效、準(zhǔn)確地完成數(shù)量龐大的單/雙面碎紙片的拼接。

雙面文字; 0-1規(guī)劃; 邊界像素匹配; 分治; Matlab 軟件

灰度使用黑色調(diào)表示物體,即以黑色為基準(zhǔn)色，用不同飽和度的黑色來顯示圖像。根據(jù)黑-灰-白的連續(xù)變化，將灰度值量化為256個灰度級，灰度值的范圍為0～255，表示亮度從深到淺，對應(yīng)圖像中的顏色為從黑到白[1-2]。像素是指基本原色素及其灰度的基本編碼，像素和灰度具有緊密的聯(lián)系。對于給定的圖像，可以用Matlab中imread函數(shù)讀入圖片中的相關(guān)數(shù)據(jù)。

碎紙機(jī)碎紙后產(chǎn)生的矩形碎片形狀相同，無法根據(jù)紙片的形狀進(jìn)行拼接，只能針對紙片圖像內(nèi)容尋找復(fù)原辦法。目前，大部分采用傳統(tǒng)的人工分辨方法，但這種方法很難將大量碎片拼接起來，并且費(fèi)時較多。所以，需要用編程方法將紙片圖像信息轉(zhuǎn)化為像素數(shù)據(jù)進(jìn)行機(jī)器拼接。

對于給定的來自同一頁印刷文字文件的碎紙片，根據(jù)文字文件的印刷方式不同，分為單面印刷和雙面印刷。雙面文字文件被破碎切割后，正反面的不確定性增加了碎紙片的混亂程度，且碎片數(shù)據(jù)量增大了一倍，計算機(jī)發(fā)生誤差的可能性增大，加大了碎紙片拼接復(fù)原的難度。

1 拼接流程

要實(shí)現(xiàn)碎片的拼接，需要根據(jù)一定的拼接流程來進(jìn)行，而碎片的具體匹配將使用人工制定的拼接規(guī)則，整體的拼接流程如圖1所示。

2 碎片拼接的數(shù)學(xué)模型

為使問題更具體，先考慮來自同一頁印刷文件的19條長條碎片[3]，對其進(jìn)行拼接復(fù)原。我們先考慮紙片只被縱切的情況，之后再將模型推廣到既橫切又縱切。

圖1 拼接流程示意圖

模型建立的步驟如下：首先，需要將圖像信息進(jìn)行數(shù)據(jù)化；然后，分析各邊界顏色數(shù)據(jù)條件，數(shù)據(jù)化相鄰關(guān)系；最后，構(gòu)造紙片邊界的拼接準(zhǔn)則，從而找出符合條件的相鄰碎片，完成拼接復(fù)原。

2.1 圖像信息抽象成網(wǎng)格顏色數(shù)據(jù)

碎紙片中的圖像信息需要轉(zhuǎn)化成能夠運(yùn)用數(shù)學(xué)方法進(jìn)行分析的數(shù)學(xué)數(shù)據(jù)。用網(wǎng)格均勻劃分的方法將圖像分成足夠多個小塊，使每個網(wǎng)格塊內(nèi)顏色單一，再統(tǒng)計出每一小塊的顏色信息作為圖像數(shù)據(jù)。

如圖2所示，將每一碎紙片的紙面劃分成無數(shù)個等大的網(wǎng)格，為形象顯示劃分過程，圖中劃分出的網(wǎng)格比較大，因此，很多網(wǎng)格中的顏色不唯一，即在一個網(wǎng)格內(nèi)既有黑色又有白色。當(dāng)劃分的網(wǎng)格數(shù)目足夠大時，可以使每一網(wǎng)格中只存在一種顏色，即不是黑色就是白色。因此，實(shí)際操作時，我們將網(wǎng)格數(shù)目取盡可能多。

圖2 碎紙片的網(wǎng)格劃分示意圖

為達(dá)到圖片拼接的目的，需要找到與其相鄰的碎紙片，因此，我們關(guān)注的只是圖2中邊緣部分的網(wǎng)格顏色。觀察碎紙條邊緣的顏色變化規(guī)律，可以發(fā)現(xiàn)，通常情況下邊界部分的網(wǎng)格顏色具有連續(xù)性，即在網(wǎng)格數(shù)目足夠大的前提下，等高度的邊界網(wǎng)格顏色是相同的。接下來，需要量化邊界網(wǎng)格顏色，便于進(jìn)行拼接設(shè)計分析。

經(jīng)上分析，可知網(wǎng)格中的顏色分為黑和白，不妨引入0-1矩陣變量Rik和Ljk，分別用0和1表示黑色和白色信息。其中：

從上面兩個公式可看出，Rik和Ljk分別表示左右邊界的網(wǎng)格方塊的顏色，且1代表黑色，0代表白色，且對于固定的紙片i與j，Rik和Ljk的值是確定的，即紙片內(nèi)容確定時，邊界網(wǎng)格塊的顏色也是個確定值。

2.2 相鄰關(guān)系的數(shù)學(xué)描述

若網(wǎng)格數(shù)目足夠大，利用每個網(wǎng)格的顏色數(shù)據(jù)量化為圖像信息的基礎(chǔ)上，引入紙片間的相鄰關(guān)系。利用一個0-1決策變量xij對相鄰關(guān)系進(jìn)行刻畫[4]，具體來說，就是用xij表示兩紙片是否相鄰以及相鄰時的左右關(guān)系。只要確定了xij的值，即得到具體的相鄰拼接順序，遍歷每張紙片即可得到拼接復(fù)原紙片的編號順序。

將相鄰關(guān)系用數(shù)學(xué)語言描述的具體表達(dá)式為：

用這種表示方式的目的是：方便最終確定每條碎紙片的相鄰紙片，不僅能將相鄰關(guān)系描述出來，還能將兩紙片的左右位置關(guān)系表示出來。

2.3 拼接規(guī)則的制定

下面以刻畫相鄰關(guān)系的xij為決策變量，先定義邊界網(wǎng)格顏色差值，以此為基礎(chǔ)制定最終的拼接規(guī)則。

2.3.1 邊界網(wǎng)格顏色差值

作為拼接工作，我們關(guān)注的只是紙片邊緣部分的網(wǎng)格顏色，用圖像表示如圖3所示。

圖3 邊界網(wǎng)格顏色對比圖

圖3所示的網(wǎng)格大小十分夸張，實(shí)際拼接網(wǎng)格中，劃分極密，網(wǎng)格極小。另外，此拼接方式需要考慮的僅僅是邊界上的圖片內(nèi)容，也即邊界上網(wǎng)格的顏色，為簡化分析，不考慮圖3中陰影部分的網(wǎng)格顏色。

為了分析出兩張相鄰的碎紙片，需要使邊界部分同高度網(wǎng)格的顏色盡可能相同，或使差異盡可能小。為此，引入邊界網(wǎng)格顏色差值

(1)

式中：Rik和Ljk分別表示紙片的左右邊界顏色信息；N表示網(wǎng)格劃分的列數(shù)目，要求N足夠大。為消除正負(fù)值的影響，用平方值體現(xiàn)這種顏色的差異性[4]。

2.3.2 基于優(yōu)化的拼接規(guī)則

根據(jù)上面對邊界網(wǎng)格顏色差異的定義，可以得到以下拼接規(guī)則：

(2)

式中：Rik和Ljk分別表示紙片的左右邊界顏色信息；xij表示相鄰關(guān)系；N表示網(wǎng)格劃分的列數(shù)目且要求數(shù)目足夠多。

拼接規(guī)則式(2)實(shí)質(zhì)上是滿足相鄰關(guān)系的一個優(yōu)化條件，按照上述條件尋找出相鄰的紙片編號，從而得到各紙片間的相鄰關(guān)系。

3 算法設(shè)計

設(shè)計的算法流程如下：

Step1：用imread讀入所有19幅圖片，保存為矩陣形式；

Step2：按列遍歷所有矩陣的第一列，找到其值全為255(白)的一列，記為第一個矩陣(第一張紙片)；

Step3：遍歷第一個矩陣的最后一列，記為a，與其他矩陣的第一列b，逐行求平方和，再相加,得c，找到最小的c，與之對應(yīng)的矩陣即為第二個矩陣；

Step4：在剩下的矩陣中繼續(xù)找第3個，一直到第19個；

Step 5：用imshow 讀出完整圖片。

計算機(jī)拼接結(jié)束后，需要進(jìn)行人工觀察，即人工干預(yù)，防止出現(xiàn)錯位情況。一般這種帶文字的錯位情況用肉眼很容易判斷出來。

4 算法求解結(jié)果

對于特定無規(guī)律的19張碎紙片，分別用1～19將其編號，將縱切碎片中英文數(shù)據(jù)讀入計算機(jī)中，利用上述算法編程得到碎紙片拼接復(fù)原結(jié)果。程序如下：

A=[];B=[];F=[];A1=[];T=100000;

for i=0:9 %相素數(shù)據(jù)讀入

name=[′00′,num2str(i),′.bmp′];

C=imread(name);

A=[A,double(C(:,1))];B=[B,double(C(:,72))];

end

for i=10:18

name=[′0′,num2str(i),′.bmp′];

C=imread(name);

A=[A,double(C(:,1))];B=[B,double(C(:,72))];

end %讀入結(jié)束

n1=find(sum(A)==max(sum(A)));%尋找左初始圖片

n2=find(sum(B)==max(sum(B)));%尋找右初始圖片

for i=1:19 %拼接圖片

for j=1:19

if sum(abs(A(:,j)-B(:,i)))

T=sum(abs(A(:,j)-B(:,i)));k=j;

end

end

F=[F,[i;k]];T=100000;

end

F1=F(1,:);F2=F(2,:);G=[n1];

for i=1:size(F')-1

G=[G,F2(find(F1==G(i)))];

end

G %顯示拼接順序并顯示圖像

for i=1:size(G')

if G(i)>10

name=[′0′,num2str(G(i)-1),′.bmp′];

C=imread(name);

else

name=[′00′,num2str(G(i)-1),′.bmp′];

C=imread(name);

end

A1=[A1,C];

end

imshow(A1)

用一張帶有文字信息的特定A4紙張進(jìn)行實(shí)驗(yàn)，獲得的拼接順序如表1所示。計算機(jī)編程計算后直接給出了正確的結(jié)果，不需要人工干預(yù)，顯示出這種方法的優(yōu)越性。

表1 縱切碎片復(fù)原編號順序

5 橫縱切紙片的模型推廣

根據(jù)上述模型建立的方法，對于雙面拼接問題其解決思路是相同的，但由于此時圖片數(shù)據(jù)量增加一倍且正反面未知，任意兩張碎片不一定能進(jìn)行同面拼接，大大增加了模型建立和求解的難度。

將橫向邊界顏色差值和縱向邊界顏色差值綜合考慮，得到復(fù)合差值。由于一張紙片存在兩面，計算出兩面的復(fù)合差值并求和得到最終的優(yōu)化條件，差值越小，相鄰的可能性就越大。優(yōu)化得到最小值對應(yīng)的紙片作為相鄰紙片，按紙片編號順序依次向下進(jìn)行排列。

如圖4所示，假設(shè)A為待拼接紙面的頭部紙片的某一面，需要找到其相鄰紙片。取第一張紙片的兩面000a和000b分別與A的每一面進(jìn)行匹配，如與000a面進(jìn)行匹配，同樣分為橫縱兩個邊界方向，即讓A面的下邊界顏色值和000a面的上邊界顏色值進(jìn)行差值計算，讓A面的右邊界顏色值和000a面的左邊界顏色值進(jìn)行差值計算，將兩方向的差值求和就得到了A面紙片和000a面的顏色差值匹配結(jié)果。同理，對000b面進(jìn)行操作，將兩面差值結(jié)果求和就得到了A面紙片對此張雙面碎紙片的最終匹配差值。依次遍歷剩余的紙片，找到最小值對應(yīng)的紙片，即為相鄰紙片。

圖4 雙面拼接規(guī)則示意圖

將上述拼接規(guī)則用數(shù)學(xué)語言描述為：

6 結(jié)束語

本文利用算法編程進(jìn)行碎紙片的機(jī)器拼接，全過程沒有手動操作，節(jié)約了大量時間，降低了工作量，并使得拼接過程較為高效、準(zhǔn)確。拼接過程采用了分治的思想，先橫拼再縱拼并輔以人工干預(yù)，可確保結(jié)果的準(zhǔn)確性，減少計算機(jī)出錯的可能性，同時降低人工干預(yù)的工作量。另外，采用雙向同時進(jìn)行(即首尾同時相對拼接)的方式，可提高計算機(jī)的容錯率，降低人工干預(yù)的復(fù)雜度。本文介紹的模型思路明了，算法簡單實(shí)用，具有很強(qiáng)的可行性，在警察辦案、重要文件復(fù)原等方面有很好的實(shí)用價值。

關(guān)于碎紙片的拼接復(fù)原問題，國內(nèi)外已進(jìn)行了大量研究[5-9]。它們各有不同，我們將繼續(xù)予以關(guān)注。

致謝：衷心感謝電子科技大學(xué)數(shù)學(xué)科學(xué)學(xué)院何國良老師在數(shù)學(xué)建模競賽培訓(xùn)中給予的無私幫助和鼓勵。

[1]灰度.百度百科[EB/OL].(2013-11-07)[2014-4-15].http://baike.baidu.com/link?url=eDoykgmWxgmzp2xi1nbTyrGx3Hfb5-YgL-MgsvZ9yTH HMCUsi6SBNpurQGCNb0As.

[2]岡薩雷斯.數(shù)字圖像處理(Matlab版)[M].3版.北京：電子工業(yè)出版社, 2005:60-72.

[3]全國大學(xué)生數(shù)學(xué)建模組委會.2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題——碎紙片的拼接復(fù)原[EB/OL].(2013-09-13)[2014-4-15].http://www.mcm.edu.cn/html_cn/block/c61dfec317d7a5bd9b 2b8efed81c8af3.html.

[4]姜啟源，謝金星.數(shù)學(xué)模型[M].4版.北京：高等教育出版社，2010: 275-288.

[5]Edson Justino, Luiz S Oliveira, Cinthia Freitas. Reconstructing shredded documents through feature matching[J]. Forensic Science International，2006，160：140-147.

[6]Leitao H C G , Stolfi J. A multi-scale method for the reassembly of two-dimensional fragmented objects[J]. IEEE Trans. Pattern Anal. Mach. Intel，2002(24):1239-1251.

[7]Yao F H , Shao G F. A shape and image merging technique to solve jigsaw puzzles[J].Pattern Recog.Lett.2003(24)：1819-1835.

[8]潘榮江.計算機(jī)輔助文物復(fù)原中的若干問題研究[D].濟(jì)南：山東大學(xué),2005:15-27.

[9]潘榮江,孟祥旭,屠長河.一種基于LCS的物體碎片自動拼接方法[J].計算機(jī)學(xué)報，2005(3):351-356.

Research on the Problem of Shredded Document Reconstruction Based on Matching of Pixels for Boundary

SHAO Chunyua，HU Fangtaob，CHENG Minghuib，LI Houbiaob

(a.School of Optoelectronic Information; b. School of Mathematics Sciences, University of Electronic Science and Technology of China, Chengdu 610054, China)

Based on minimizing the difference value between boundary pixel data, a 0-1 programming model and corresponding algorithm are established for the doubled-sided shredded document reconstruction problem. The designed algorithm is divided into vertical and horizontal reconstruction. Then utilizing the matching of pixels for boundary rule, we obtained the reconstruction of shredded documents. As it is different from the method of artificial recovery we used before, computer becomes the main labor force with Matlab. It turned out that this method of reconstruction can be accomplished efficiently and precisely.

doubled-sided shredded document; 0-1 programming model; divide and conquer; matching of pixels for boundary; Matlab software

2014-04-22；修改日期: 2014-05-13

國家自然科學(xué)基金資助項目(11101071);電子科技大學(xué)教學(xué)研究基金資助項目(2013XJYSL026)。

邵春雨(1994-),女，本科在讀，專業(yè)方向：電子科學(xué)與技術(shù)(光電工程與光通信)專業(yè)。

李厚彪(1976-),男，副教授，主要從事科學(xué)計算與數(shù)值代數(shù)的教學(xué)和研究工作。

O151.2

A

10.3969/j.issn.1672-4550.2015.02.070