韓盈盈，章毅鵬，沈鴻平，王義康

(中國計(jì)量學(xué)院理學(xué)院，浙江杭州 310018)

圖文碎片拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域均有著重要的應(yīng)用［1］。傳統(tǒng)的人工拼接在效率上已經(jīng)不能滿足實(shí)際需要，因此，借助于計(jì)算機(jī)技術(shù)的快速自動(dòng)拼接方法應(yīng)運(yùn)而生。羅智中提出了基于線段掃描的碎紙片邊界檢測算法研究［2］，Nasir Memon提出了應(yīng)用貪婪算法實(shí)現(xiàn)圖形碎片的自動(dòng)拼接［3］，賈海燕提出了一種碎紙自動(dòng)拼接中的形狀匹配方法［4］，這些方法主要是利用碎片邊界幾何形狀實(shí)現(xiàn)復(fù)原;對于規(guī)則碎片拼接，劉俊瑋提出基于像素點(diǎn)灰度值的條狀碎片文件自動(dòng)復(fù)原的探討和研究［5］，王麗娜提出了基于像素索引值的規(guī)則碎紙片拼接復(fù)原［6］，沈鴻平等人提出利用0－1規(guī)劃對規(guī)則中文文字碎片的拼接進(jìn)行研究［7］，這些方法主要是利用碎片邊緣像素特征來實(shí)現(xiàn)復(fù)原。而對于規(guī)則的圖形碎片，由于缺少文字邊界和行列特征，拼接難度大，不易實(shí)現(xiàn)。

規(guī)則的圖形碎片，碎片邊界輪廓無明顯幾何匹配特征信息。本文通過提取規(guī)則碎片邊緣的像素特征，確立了基于圖片灰度值的匹配度指標(biāo)，并建立了基于0－1規(guī)劃的規(guī)則碎片拼接模型?？紤]到模型本身的復(fù)雜性和求解方法對復(fù)雜模型的適用性，利用無需制定確定性啟發(fā)式搜索規(guī)則的遺傳算法進(jìn)行求解，得到碎片拼接的結(jié)果，結(jié)果表明該方法效果良好。

1 規(guī)則圖形拼接原理

對于規(guī)則的圖形碎片來說，兩碎片之間的拼接結(jié)果是唯一的，因此假設(shè)兩張碎片完全匹配取值為1，否則取為0，從而可設(shè)0－1變量為

其中，xijst表示碎片i的s邊緣與碎片j的t邊緣匹配變量;s，t=1，2，3，4 分別表示碎片的上、下、左、右邊緣。

對于碎片i，其由m×m個(gè)像素組成，取其上、下、左、右4 條邊緣的灰度向量為 ris=(ris1，ris2，L，rism)T，s=1，2，3，4，s取不同值分別表示碎片的上、下、左、右4條邊緣的灰度向量。由此可構(gòu)建出描述碎片i的邊緣灰度矩陣Ri

當(dāng)圖片的內(nèi)容被一次切割之后形成兩張碎片i，j，如圖1所示，則碎片i的右邊緣與碎片j的左邊緣在對應(yīng)同一個(gè)像素點(diǎn)處的灰度值應(yīng)較為接近。

圖1 10號和25號碎片灰度圖及其右、左邊緣掃描線

因?yàn)樗兴槠鶠榇笮∠嗤囊?guī)則正方形，故其邊緣灰度矩陣R均為m×4的矩陣。為了衡量碎片i的s邊緣與碎片j的t邊緣的接近程度，可通過計(jì)算碎片i的s邊緣的灰度向量與碎片j的t邊緣灰度向量的歐氏距離來定義匹配度。定義碎片i的s邊緣與碎片j的t邊緣的匹配度為

rjsn表示碎片j的s邊緣第n個(gè)像素點(diǎn)的灰度值，其中s，t=1，2，3，4，ηijst匹配度越大說明碎片 i的 s邊緣與碎片j的t邊緣接近程度越大，兩碎片拼接吻合度越高;越小，說明碎片i的右邊緣與碎片j的左邊緣拼接吻合度越低。規(guī)定當(dāng)時(shí)，認(rèn)為兩張碎片可完全匹配。

2 遺傳算法的基本思想

傳統(tǒng)的優(yōu)化算法主要有枚舉法、啟發(fā)式算法和搜索算法。對于規(guī)則圖形拼接來說，枚舉空間比較大，求解效率較低;啟發(fā)式算法需要尋求一種產(chǎn)生可行解的啟發(fā)式規(guī)則，雖然求解效率得到提高，但啟發(fā)式規(guī)則對其他模型使用較差，一般得到的也僅是局部最優(yōu)解;當(dāng)可行解的子集較大時(shí)，搜索算法也需要借助一些啟發(fā)知識才能達(dá)到較高的求解效率。

遺傳算法［8］最早由美國 Michigan大學(xué)的 John Holland提出，是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。其特點(diǎn)是自組織、自適應(yīng)、自學(xué)習(xí)性，其不同于啟發(fā)式算法和搜索算法，強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)換規(guī)則，因此有較強(qiáng)的適用性。

遺傳算法是從代表問題可能潛在解集的一個(gè)種群開始，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生越來越好的近似解。在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度大小挑選個(gè)體，并借助于遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生代表新的解集的種群。遺傳算法的基本流程如圖2所示。

圖2 遺傳算法的基本流程圖

3 樣本數(shù)據(jù)及圖像預(yù)處理

樣本數(shù)據(jù)來自某彩色圖片，彩色圖片經(jīng)橫切和縱切，共計(jì)36張碎片，并用1，2，…，36對每張碎片編號。碎片經(jīng)過掃描儀處理，以圖片的形式保存。所有碎片均為大小相同的規(guī)則正方形，圖3為部分碎片圖樣。

圖3 部分碎片圖樣(編號:10號和25號)

掃描后保存在電腦中的圖形碎片可看成是由一個(gè)個(gè)像素平鋪構(gòu)成。對于黑白圖像而言，因是單色圖像，圖片可由每個(gè)像素點(diǎn)處的灰度值形成的灰度矩陣表示;對于彩色圖片而言，則是由多幅單色圖像組合形成。

在RGB彩色系統(tǒng)中，一幅彩色像由3張單色圖像組成，這3幅圖像分別稱為紅(R)、綠(G)、藍(lán)(B)分量圖像［9］。彩色圖像在計(jì)算機(jī)存儲中需要用3個(gè)矩陣來描述，這勢必會使運(yùn)算速度降低，增加問題的復(fù)雜性。因此，研究中運(yùn)用Matlab自帶的適用于RGB和灰度圖像之間進(jìn)行轉(zhuǎn)換的工具箱函數(shù)rgb2gray，將復(fù)雜彩色圖像轉(zhuǎn)換為僅用一個(gè)灰度矩陣便可進(jìn)行簡化描述的灰度圖像。

將樣本數(shù)據(jù)中的36張碎片灰度化，每張碎片均可產(chǎn)生一個(gè)灰度矩陣，矩陣的元素為碎片在每個(gè)像素點(diǎn)處的灰度值，像素灰度值介于0～255之間。以33號碎片為例，圖4展示了碎片由彩色圖像轉(zhuǎn)換成灰度矩陣再進(jìn)行反演成灰度圖的處理過程。

圖4 第33張碎片灰度化預(yù)處理過程

4 0-1規(guī)劃拼接模型的建立

當(dāng)以碎片i為基準(zhǔn)圖片進(jìn)行兩張碎片的拼接時(shí)，以匹配度達(dá)到最大作為兩張碎片拼接的目標(biāo)建立優(yōu)化模型，兩張碎片拼接的目標(biāo)函數(shù)為

對于碎片i而言，在其余35張碎片中至多只有一張碎片的某條邊緣與之拼接，因此可得到拼接約束為

當(dāng)拼接整幅圖片時(shí)，以全局碎片拼接復(fù)原匹配度最大為目標(biāo)建立優(yōu)化模型，則全局目標(biāo)函數(shù)為

對于每個(gè)碎片的左邊緣而言，至多只有一個(gè)碎片與其進(jìn)行右鄰拼接;對于而對于每個(gè)碎片的上邊緣而言，至多只有一個(gè)碎片與其下鄰拼接。因此可得到總的拼接約束為

由式(6)，式(7)式得到碎片拼接的0－1規(guī)劃模型為

5 基于遺傳算法的模型求解

根據(jù)遺傳算法的基本流程設(shè)計(jì)出適合求解0－1規(guī)劃拼接模型的遺傳算法步驟如下:

步驟1 隨機(jī)產(chǎn)生初始種群(個(gè)體數(shù)目為M)。即產(chǎn)生M×36的矩陣，矩陣的每一行是1－36的數(shù)字隨機(jī)排列，代表一種碎片拼接的結(jié)果，以此矩陣作為初始的種群。

步驟2 計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度。即每個(gè)隨機(jī)排列序列對應(yīng)的36張碎片的拼接結(jié)果的匹配度，并判斷是否大于遺傳運(yùn)算的終止進(jìn)化代數(shù)，若符合，輸出最佳個(gè)體及其代表的最優(yōu)解，并結(jié)束運(yùn)算;否則轉(zhuǎn)向步驟3。

步驟3 選擇:依據(jù)適應(yīng)度選擇再生個(gè)體，適應(yīng)度高的個(gè)體被選中的概率高，適應(yīng)度低的個(gè)體被淘汰。

步驟4 交叉:按照一定的交叉概率和交叉方法，生成新的個(gè)體。

步驟5 變異:按照一定的變異概率和變異方法，生成新的個(gè)體。

步驟6 由交叉和變異產(chǎn)生新一代的種群，返回到步驟2。

交叉過程:本文采用1985年Goldberg等針對TSP問題提出的基于路徑表示的部分匹配交叉(PMX)操作，PMX要求隨機(jī)選取兩個(gè)交叉點(diǎn)，以便確定一個(gè)匹配段，根據(jù)兩個(gè)父個(gè)體中兩個(gè)交叉點(diǎn)之間的中間段給出映射關(guān)系生成兩個(gè)子個(gè)體。隨機(jī)選取兩個(gè)交叉點(diǎn)用箭頭表示，如圖5所示。

圖5 遺傳算法中的交叉操作

變異過程:遺傳算法中變異操作有:(1)點(diǎn)位變異，變異以一定概率對解的某些位做值得變異。(2)逆轉(zhuǎn)變異，在某一解中隨機(jī)選擇兩點(diǎn)，再將這兩點(diǎn)內(nèi)的碼串按反序插入原位置。(3)隨機(jī)選擇兩個(gè)交換點(diǎn)，使交換點(diǎn)處的碼值交換。圖6展示了兩個(gè)位點(diǎn)互換的過程。

圖6 遺傳算法中的變異操作

對于圖形樣本文件的36張碎片，運(yùn)用上述遺傳算法進(jìn)行模型求解，取初始種群個(gè)體數(shù)目M=100，得到部分拼接結(jié)果如圖7所示。

圖7 圖形樣本文件部分拼接結(jié)果

6 結(jié)束語

通過對規(guī)則圖形碎片的特征與文字碎片特征進(jìn)行對比，提取了圖形碎片邊緣像素信息，并基于碎片之間的歐氏距離建立了0－1規(guī)劃拼接模型，利用遺傳算法對0－1規(guī)劃模型進(jìn)行求解。求解結(jié)果表明，模型可準(zhǔn)確地對規(guī)則圖形碎片拼接問題進(jìn)行數(shù)學(xué)描述;而遺傳算法可在未設(shè)置啟發(fā)式搜索規(guī)則的情況下快速實(shí)現(xiàn)圖形碎片拼接。本文的結(jié)果是基于規(guī)則邊界且大小相同的正方形的圖形碎片，實(shí)際中則受破碎方式、圖形內(nèi)容等因素影響，碎片拼接復(fù)原過程也會因此而錯(cuò)綜復(fù)雜。當(dāng)碎片數(shù)量較多時(shí)，無需啟發(fā)式規(guī)則的遺傳算法會因問題規(guī)模的增大，導(dǎo)致收斂速度變慢，因此需要進(jìn)一步深入研究，建立更精確的模型，將會有更準(zhǔn)確、快速的拼接結(jié)果。

［1］楊洛斌.形狀匹配技術(shù)在文物復(fù)原中的研究與應(yīng)用［D］.西安:西北大學(xué)，2002.

［2］羅智中.基于線段掃描的碎紙片邊界檢測算法研究［J］.儀器儀表學(xué)報(bào)，2011，23(2):289 －294.

［3］Nasir Memon，Anandabrata Pal.Automated reassembly of file fragmented images using greedy algorithms［J］.IEEE Transactions on Image Processing，2006，15(2):385 －393.

［4］賈海燕，朱良家，周宗潭，等.一種碎片自動(dòng)拼接中形狀匹配方法［J］.計(jì)算機(jī)仿真，2006，23(11):180 －183.

［5］劉俊瑋，宋嵩燾，王子豪.條狀碎片文件自動(dòng)復(fù)原的探討和研究［J］.數(shù)學(xué)學(xué)習(xí)與研究，2014，27(1):113 －114.

［6］姜艷秋，紀(jì)艷俠，王葳，等.基于Matlab規(guī)則碎紙片拼接復(fù)原方法的研究及實(shí)現(xiàn)［J］.自動(dòng)化與儀器儀表，2014(5):172－174.

［7］沈鴻平，章毅鵬，王義康.基于0－1規(guī)劃模型的規(guī)則中文碎片拼接復(fù)原研究［J］.電子科技，2014，27(6):13 －16.

［8］王小平，曹立明.遺傳算法－理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，2001.

［9］Rafael CGonzalez，Richard E Woods，Steven L Eddins.Digital image processing using Matlab［M］.北京:電子工業(yè)出版社，2013.