[發明專利]運用遺傳算法優化碎紙片拼接復原問題的方法

有效

• 申請號: 201711275301.5
• 申請日: 2017-12-06
• 公開（公告）號: CN108073987B
• 公開（公告）日: 2021-07-16
• 發明（設計）人: 張軍;龔月姣;陳偉能;葛勇鋒;張鑫源
• 申請（專利權）人: 華南理工大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06T3/40
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 李斌

本發明公開了一種運用遺傳算法優化碎紙片拼接復原問題的方法，首先，進行基因差異度評估，確定各基因間水平和豎直拼接差異度；然后，按照預設編碼方式初始化整個種群，并利用基因差異度對種群中的染色體適應度進行評估，記錄最優染色體；隨后，進入算法進化流程，每次隨機選擇種群中染色體作為父母染色體組成交叉組合，執行交叉算子并產生子代染色體，隨機選擇四種變異算子的一種對新生成染色體進行變異，并將變異后的染色體插入種群中，在執行完成交叉變異算子后，從新種群中擇優選擇最優的若干個體組成新的種群。若達到終止條件，則終止進化，輸出最優染色體的基因排列情況，否則繼續返回進化流程進行種群進化。

技術領域

本發明涉及圖像處理和進化計算技術領域，具體涉及一種運用遺傳算法優化碎紙片拼接復原問題的方法。

背景技術

破碎文件拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。傳統上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數量巨大，人工拼接很難在短時間內完成任務。隨著計算機技術的發展，人們試圖開發碎紙片的自動拼接技術，以提高拼接復原效率。

發明內容

本發明的目的是為了解決現有技術中的上述缺陷，提供一種運用遺傳算法優化碎紙片拼接復原問題的方法。

本發明的目的可以通過采取如下技術方案達到：

一種運用遺傳算法優化碎紙片拼接復原問題的方法，所述的方法包括：

S1、基因差異度評估：

由于遺傳算法在離散優化領域的廣泛應用及其所展現出的顯著優越性，本發明將基于遺傳算法優化框架來優化碎紙片拼接復原問題。針對碎紙片拼接復原問題的特點，本發明對傳統遺傳算法的算子進行了相應的改進。下面按照遺傳算法的操作流程對本發明做進一步的介紹。

對于遺傳算法而言，首先是對染色體進行編碼，針對碎紙片拼接問題的特點，本發明將染色體編碼成二維矩陣x，n和m分別表示染色體中的基因的行列數。

因碎紙片在該遺傳算法中被編碼成基因，因此基因差異度也即是碎紙片間拼接差異度。按照拼接方向不同，分為水平方向差異度和豎直方向差異度。

水平方向差異度的計算方法如下式所示，其中diff_horizontal(i,j)為將基因i置于基因j水平左側所產生的差異度，edge_i,j為將基因i置于基因j水平左側所產生的邊緣差異度，計算方法后續會具體定義，相似地，blank_i,j為將基因i置于基因j水平左側所產生的空白向量差異度。為基因i右側邊緣向量位置k灰度，相應地，為基因j左側邊緣向量位置k灰度，條件即為基因i右側邊緣和基因j左側邊緣均存在非白內容，也即基因i和基因j存在非空白拼接，在這種條件下，它們水平方向差異度diff_horizontal(i,j)的計算方法為邊緣差異度edge_i,j和空白向量差異度blank_i,j之和，反之則直接計算空白向量差異度blank_i,j。

將基因i置于基因j水平左側所產生的邊緣差異度如下式定義，其中為基因i的右側邊緣向量和基因j的左側邊緣向量在位置k的灰度差異度，h為邊緣向量長度，為基因i的右側邊緣向量和基因j的左側邊緣向量在位置k的灰度加權差，在該加權差大于等于閾值τ時，灰度差異度為1，反之灰度差異度為0。

基因i的右側邊緣向量和基因j的左側邊緣向量在位置k的灰度加權差的計算方式如下式定義，其中表示基因i右邊緣向量位置k灰度，相應地，表示基因j左邊緣向量位置k灰度。