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

中國電子科技集團公司第五十四研究所 杜 浩 劉雪峰

東北大學(xué) 蔡立晨

1.引言

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

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

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

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

3.算法設(shè)計

符號約定：

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

3.1 特征提取

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

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

圖1

3.2 余弦距離

余弦距離通過計算兩個向量夾角的余弦值來評估其相似程度[2]。假設(shè)：

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

3.3 基于基因融合改進的遺傳算法

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

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

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

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

4.實驗結(jié)果與分析

實驗在MATLAB平臺上進行，結(jié)果如圖三所示：

圖三 實驗結(jié)果

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

5.結(jié)語

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