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

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

東北大學 蔡立晨

1.引言

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

2.模型假設與分析

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

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

3.算法設計

符號約定：

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

3.1 特征提取

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

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

圖1

3.2 余弦距離

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

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

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

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

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

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

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

4.實驗結果與分析

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

圖三 實驗結果

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

5.結語

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