蘇小朋，楊昔陽,2

(1.泉州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院,福建 泉州 362000；2.泉州師范學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 泉州 362000)

基于遺傳算法的條狀文字碎片復(fù)原算法

蘇小朋1，楊昔陽1,2

(1.泉州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院,福建 泉州 362000；2.泉州師范學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 泉州 362000)

規(guī)則碎片復(fù)原是圖片復(fù)原領(lǐng)域的一個研究熱點。本文以碎片的邊緣像素為特征，通過定義恰當(dāng)?shù)倪z傳操作和變異操作,采用遺傳算法建立了一種普適性、推廣性較好的數(shù)學(xué)模型。實驗表明，利用這種算法對中英文條狀碎片進(jìn)行復(fù)原，效果良好。

條狀文字碎片;碎片復(fù)原;遺傳算法

圖像碎片的復(fù)原是計算機(jī)視覺領(lǐng)域中的一個新穎且典型的應(yīng)用，它主要研究如何借助計算機(jī)確定碎片的特征，再采用適當(dāng)?shù)臄?shù)學(xué)模型確定碎片在原圖像中應(yīng)有的位置，從而達(dá)到還原圖片的目的。

目前關(guān)于碎片復(fù)原研究有很多，它們集中把圖像碎片的幾何輪廓當(dāng)作碎片特征，再通過某些數(shù)學(xué)模型逐步完成全局復(fù)原。幾何信息的提取方法主要包括∶（1）輪廓線匹配法[1];（2）多尺度輪廓匹配法[2-3];（3）角序列匹配法[4];（4）邊界鏈碼法[5]。

條狀碎紙機(jī)是現(xiàn)實生活中的一類常見的碎紙方式。針對這種特定的文字碎紙復(fù)原，國內(nèi)有一些人對此提出了解決方法[6-7],但當(dāng)碎片規(guī)模足夠大時，通過經(jīng)典的優(yōu)化算法往往很難得到最優(yōu)解。為此，本文提出了一種基于遺傳算法的文字碎片復(fù)原方法。

1 遺傳算法簡介

在生物進(jìn)化過程中，種群總能通過不斷的進(jìn)化來適應(yīng)環(huán)境。遺傳算法正是這么一種模擬生物進(jìn)化的智能算法。這種算法已經(jīng)簡潔而又高效地解決了若干重要的問題。遺傳算法通過一系列帶有隨機(jī)因素的遺傳操作和變異操作來模擬自然選擇，具有非常強(qiáng)的適應(yīng)性，往往被用于求解一些經(jīng)典算法難以求解的優(yōu)化問題。因為遺傳算法是一種模擬生物進(jìn)化的算法，因而這種算法中的專業(yè)術(shù)語也往往和生物進(jìn)化有關(guān)。在一個優(yōu)化問題中，可行域中的點經(jīng)過適當(dāng)編碼后，稱為染色體。每個可行解對應(yīng)的目標(biāo)函數(shù)值稱為該染色體的適應(yīng)值。一定規(guī)模的染色體組成一個集體，稱為一代的種群。在每代種群中，染色體不斷被遺傳操作和變異操作更新，這些根據(jù)適應(yīng)值精心設(shè)計的遺傳、變異操作可以以極高的概率保證各代的平均適應(yīng)值越來越好，即在種群規(guī)模和代數(shù)足夠大的時候，可以保證最優(yōu)的染色體以百分之百的概率逼近最優(yōu)解。

2 模型的建立和求解

假定條狀文字碎片來源于同一張紙質(zhì)文檔,它們的邊緣在裁減中沒有被損壞,且該張紙片的所有碎片保存完整。每張條狀碎片的大小相同,所以沒有辦法采用現(xiàn)有文獻(xiàn)中的各種拼接算法,因為這些算法大都是基于碎片的幾何形狀來完成拼接的。圖1給出了若干條狀碎片的示意圖，限于篇幅，并非所有圖片全部被列出。筆者在實驗過程中也嘗試?yán)梦淖肿R別的方法來確定兩張圖片是否相鄰,但龐大的計算量使這種算法缺乏可執(zhí)行性。因此本文以兩張條狀碎片邊緣像素的匹配程度為相鄰程度的指標(biāo),建立了一個使整體匹配程度最優(yōu)的優(yōu)化模型,并通過遺傳算法進(jìn)行編碼和求解.對中英文條狀碎片的拼接表明了這種解法的實用性和可行性。

圖1 若干條狀碎片

2.1 復(fù)原模型的建立

提取碎片i最右邊一列的灰度值Ri和碎片j最左邊一列的灰度值Lj,用兩者的差異來構(gòu)建碎片i和碎片j左右相鄰的匹配度fij，即令

2.2 遺傳算法的遺傳和變異操作

在求解模型(1)時，采用從左到右的圖片的序號為編碼構(gòu)造染色體。顯然一組這樣的編碼和一個解矩陣[xij]mxm是等價的，例如如果已知碎片i和碎片j左右相鄰，那么便可知=1，反之亦然。采用模型(1)的目標(biāo)函數(shù)作為適應(yīng)值函數(shù)。在進(jìn)化中，適者生存，所以在遺傳算法運(yùn)行過程中，會不斷地選擇優(yōu)者保留下來，同時也不斷地選擇劣者淘汰下去。在每代中，使用適應(yīng)值處于前50%的染色體繁衍下一代。

恰當(dāng)?shù)倪z傳操作應(yīng)該使得染色體不斷朝著優(yōu)化目標(biāo)函數(shù)的方向進(jìn)化，它可以保證遺傳算法具有局部尋優(yōu)的能力。隨機(jī)選擇兩個適應(yīng)值較好的染色體，采用“順序交叉法”方式作為遺傳操作函數(shù)。從父代A隨機(jī)選一個編碼子串，放到子代A′的對應(yīng)位置；子代A′空余的位置從父代B中按B的順序選?。ㄅc己有編碼不重復(fù)）。同理可得子代B'。例如

變異操作是指依據(jù)變異概率將個體編碼串中的某些數(shù)值用其它值來代替。變異操作是產(chǎn)生新染色體的輔助方法，它反映了遺傳算法的全局搜索能力。通?？梢匀∽儺惛怕蕿?0%。采用隨機(jī)交換染色體兩個元素或者兩個片段的方法構(gòu)造變異函數(shù)。

種群的規(guī)模是指在一代中染色體的個數(shù)。通常比較大的種群規(guī)模有助于更準(zhǔn)確地找到優(yōu)化模型的滿意解，但也需要更長的時間。在解決模型(1)的過程中，我們讓種群規(guī)模取常數(shù)400。

遺傳運(yùn)算的終止條件為進(jìn)化代數(shù)達(dá)到500代,也就是說當(dāng)遺傳算法運(yùn)行500輪之后，最后一代的最優(yōu)解即為解決模型(1)的滿意解。用戶根據(jù)給定的結(jié)果進(jìn)行判斷，如果有必要，可以根據(jù)其中明顯的錯誤修改匹配度矩陣，重新運(yùn)行遺傳算法。終止代數(shù)設(shè)置得越大，可以以更大的概率得到更精確的結(jié)果，但也需要更長的時間。

遺傳算法的流程圖如圖2所示。在遺傳操作中，選擇適應(yīng)值較好的前25%的染色體直接進(jìn)入子代，其余75%的子代染色體由本節(jié)介紹的“順序交叉法”產(chǎn)生，其流程圖如圖3所示。而在變異操作中，根據(jù)變異概率，隨機(jī)從子代中挑選染色體交換其中兩個元素或者兩個片段進(jìn)行重新排序。

圖2 遺傳算法流程圖

圖3 遺傳操作流程圖

2.3 結(jié)果

針對中、英文各一張紙質(zhì)材料進(jìn)行縱向裁剪（碎片如圖1所示），切割成19條條狀碎片。通過Matlab提取每張碎片的左右邊緣灰度值，對全白的邊緣（很有可能是邊界）進(jìn)行特殊處理。采用遺傳算法對模型(1)進(jìn)行求解，經(jīng)過500輪迭代，復(fù)原之后的中英文效果圖如圖4所示。在迭代過程中，每一代的最優(yōu)染色體的適應(yīng)值、平均適應(yīng)值如圖5所示。

圖4 復(fù)原效果圖

3 總結(jié)

采用遺傳算法對條狀文字碎紙進(jìn)行復(fù)原。采用條狀碎片邊緣灰度值的匹配程度作為衡量碎片是否左右相鄰的指標(biāo)，建立了一個整體匹配度最優(yōu)的復(fù)原模型，并利用遺傳算法對該問題進(jìn)行編碼和求解。針對兩張中、英文文件的條狀碎片數(shù)據(jù)進(jìn)行拼接復(fù)原，由于條狀碎片邊緣有足夠的灰度值信息，因而利用遺傳算法可以一次性得到正確結(jié)果，無須人為調(diào)整。表明本文采用的遺傳算法是一種解決條狀復(fù)原模型的切實可行的算法。

圖5 適應(yīng)值函數(shù)

［1］WOLFSON H J．On curvematching．［J］．IEEE T ransactionson P attern A nalysisand M achine I nteigence，1990，12（5）：483-489．

［2］LEITAO，H C，STOFIJ．A multiscalemethod forthereassembleoftwo-dimensional fragmented objects［J］．IEEE Transact ions on Pattern Analysis and Machine Intelligence，2002，24（9）：1239-125l．

［3］朱延娟，周來水，張麗艷，等．基于Hausdorff距離的多尺度輪廓匹配算法［J］．中國機(jī)械工程，2004，15（17）：1553-1561．

［4］周豐，黃曉嗚．基于角序列的二維碎片輪廓匹配方法［J］．科學(xué)技術(shù)與工程，2007，7（15）：3757-3760．

［5］饒芮菱，金雪峰，魯懷偉．基于鏈碼的二維碎片輪廓匹配算法［J］．計算技術(shù)與自動化，2007，26（2）：34-37．

［6］楊雯雯，陶佳琪，鄭路通，等．單頁單面漢字縱橫切碎片拼接復(fù)原算法［J］．運(yùn)城學(xué)院學(xué)報，2013（5）：16-20．

［7］劉俊瑋，王子豪，宋嵩燾，等．條狀碎片文件自動復(fù)原的探討與研究［J］．?dāng)?shù)學(xué)學(xué)習(xí)與研究，2014（1）：115-116．

（責(zé)任編輯：朱聯(lián)九）

An GA Based Automatic Stitching Technology of Strip-shaped Pieces

SU Xiao-peng1,YANG Xi-yang1,2
(1.Quanzhou Vocational College of Economics and Business,Quanzhou 362000,China 2.School of Math and Computer Science，Quanzhou Normal University,Quanzhou 362000,China)

The restoration technology of strip-shaped pieces isone of the hot topics in the field of picture restoration.Using gray degrees in the edges as the characteristics,and after adequate-definite GA operation and mutation operation,digital model,universaland general in solving sim ilar questions,is established based on GA algorithm in this paper.The experiment shows that the proposed GA algorithm hasa good effectin solving the restoration of Chinese and English strip-shaped pieces.

strip-shaped pieces;fragment reassemblymethodology;GA algorithm

TP391．41

A

1673-4343（2014）02-0039-04

2013-12-08

福建省教育廳科技項目（JA12273，JK2013037）;泉州市科技局科技項目（2012Z103）

蘇小朋，男，福建泉州人，高級講師。研究方向：基礎(chǔ)數(shù)學(xué)。通訊作者：楊昔陽，男，福建泉州人，講師。研究方向：模糊數(shù)學(xué)與人工智能。