基于改進(jìn)遺傳算法的大批量單面碎紙片拼接復(fù)原

中國(guó)電子科技集團(tuán)公司第五十四研究所 杜 浩 劉雪峰

東北大學(xué) 蔡立晨

1.引言

碎紙片的拼接復(fù)原問(wèn)題在歷史文獻(xiàn)修復(fù)、物證復(fù)原及情報(bào)獲取等諸多領(lǐng)域都有著重要的應(yīng)用。目前拼接復(fù)原工作大部分由傳統(tǒng)的人工方式完成，但是在大批量碎紙片的情況下，人工拼接將變得十分緩慢并且低效。在計(jì)算機(jī)視覺(jué)極大發(fā)展的今天，采用計(jì)算機(jī)技術(shù)，運(yùn)用機(jī)器視覺(jué)的原理對(duì)碎紙片進(jìn)行拼接復(fù)原的方法應(yīng)運(yùn)而生。

2.模型假設(shè)與分析

再進(jìn)行算法設(shè)計(jì)之前，本文對(duì)問(wèn)題做出如下假設(shè)：假設(shè)碎片無(wú)噪聲污染；各個(gè)碎片之間相互關(guān)聯(lián)；同時(shí)假設(shè)文件中文字的行間距確定；沒(méi)有兩個(gè)相同的碎紙片并且不涉及手寫(xiě)稿。

對(duì)于僅有縱向切割或者橫向切割的情況，各個(gè)碎紙片的邊界信息豐富，可以通過(guò)使用邊緣像素值作為特征進(jìn)行匹配。在橫向切割和縱向切割的影響下，碎紙片包含信息更少，本文首先采用積分投影的方式進(jìn)行按行分類，并設(shè)計(jì)的基因融合算法，針對(duì)大批量的碎片匹配效率低下的問(wèn)題，在遺傳算法的迭代過(guò)程中融合個(gè)體，能在很大一定程度上保留最優(yōu)的匹配，極大程度加速了算法的收斂，可以很好地解決大批量碎紙片匹配效率低下的問(wèn)題。

3.算法設(shè)計(jì)

符號(hào)約定：

圖像的水平積分投影特征以及邊緣特征：

3.1 特征提取

在僅縱向切割或者僅橫向切割的情況下，本文提取邊緣像素特征。以縱向切割為例，相鄰的碎片相似程度高，左右邊緣可拼接在一起形成完整的文字。如果被拼接的兩個(gè)碎紙片不相鄰，那么其拼接之后的邊緣不能形成完整的文字，相似程度較低。本文對(duì)比不同碎紙片特征之間的余弦距離以得到最優(yōu)匹配[1]。

在雙向切割的情況下，本文首先進(jìn)行按行分類。橫切和縱切的影響下，碎紙片所包含的文本信息變少，使得拼接難度增大。由于文字字高不一致，直接按行分類難度大。在進(jìn)行水平積分投影之后可減少字高不一致帶來(lái)的影響。本文首先對(duì)碎紙片提取到的水平積分投影特征進(jìn)行了二值化，進(jìn)一步減少字高不一致帶來(lái)的影響。按行分類如圖1(a)所示：

圖1

3.2 余弦距離

余弦距離通過(guò)計(jì)算兩個(gè)向量夾角的余弦值來(lái)評(píng)估其相似程度[2]。假設(shè)：

本文通過(guò)計(jì)算特征之間的余弦相似度度量碎紙片之間的匹配程度。

3.3 基于基因融合改進(jìn)的遺傳算法

遺傳算法是一種模擬生物界自然進(jìn)化過(guò)程來(lái)解決最優(yōu)問(wèn)題的算法，該算法在求解問(wèn)題的基本步驟為：建立表示可行解的基因編碼；種群初始化；計(jì)算適應(yīng)度函數(shù)；對(duì)個(gè)體進(jìn)行選擇、交叉和變異操作；終止條件判斷[3]。

本文設(shè)計(jì)的遺傳算法中，每個(gè)個(gè)體代表一種碎紙片的排列組合方式，每個(gè)個(gè)體的適應(yīng)程度，由其排列方式?jīng)Q定。不妨假設(shè)當(dāng)前的切割方式為僅縱切，種群中的某一個(gè)個(gè)體代表一種碎紙片的排列方式，即，那么對(duì)于當(dāng)前的排列方式便可以計(jì)算得到當(dāng)前個(gè)體的適應(yīng)度值。種群的初始化由蒙特卡洛方法生成[4]，選擇方式由賭輪盤形式生成。

傳統(tǒng)的遺傳算法中的交叉運(yùn)算在一定程度上會(huì)破壞優(yōu)秀基因的組合。本文針對(duì)大批量碎紙片圖像匹配效率低下的問(wèn)題，提出了基因融合的操作。在計(jì)算個(gè)體適應(yīng)度的同時(shí)，能得到當(dāng)前組合下的相互鄰接的碎紙片的匹配程度，由余弦距離得出。當(dāng)兩個(gè)碎紙片真正相鄰時(shí)，其匹配程度較大，本文利用基因融合的方式將此兩者標(biāo)記為不可分，即每次操作的過(guò)程中兩者將作為一個(gè)整體存在。終止條件是所有基因融合完畢，即每個(gè)碎紙片都找到與之相鄰的最佳匹配。其過(guò)程示意圖如圖二所示：

圖二 （紅色并且加入連接符的表示被融合的基因）

4.實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)在MATLAB平臺(tái)上進(jìn)行，結(jié)果如圖三所示：

圖三 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果表明本文所提出的基于基因融合的遺傳算法效果穩(wěn)定，在實(shí)驗(yàn)過(guò)程中可明顯的具有更快的速度。

5.結(jié)語(yǔ)

本文建立了一種基于基因融合的改進(jìn)遺傳算法對(duì)碎紙片進(jìn)行拼接復(fù)原，通過(guò)實(shí)驗(yàn)取得了較好的結(jié)果。但是實(shí)驗(yàn)過(guò)程中仍然存在諸多問(wèn)題，需要更高的精度以及更加穩(wěn)定的特征提取方式。