基于進化計算的碎紙拼接重構算法研究

黨悅晨， 李 婉， 周 強

（陜西科技大學a.電氣與控制工程學院；b.電子信息與人工智能學院，西安710021）

0 引 言

二維碎片的拼接重建，在考古［1］、刑偵以及人民幣修復［2-3］等問題上都有著廣泛的應用。當面對基于少量，規則碎片的簡單拼接問題上，可以通過人工比對的方法進行手動拼接，較為準確的還原出碎片的原始形狀。但實際所需要進行拼接的碎片不僅形狀不規則，且數量龐大。這時，如果單純依靠人工的方式將其復原不僅耗時耗力且在碎片已經嚴重破損的基礎上易造成2 次損壞。隨著計算機以及圖形學技術的飛速發展，各類圖像處理算法也在不斷地優化，出于保護碎片，同時提高復原效率的目的，提出利用計算機進行輔助實現碎紙片的自動拼接［4-5］。

目前，在二維碎片拼接方面，國內外已有大量學者進行了相關研究。針對規則碎片，文獻［6-7］中通過建立基于0-1 規劃的拼接模型來實現拼接。文獻［8-9］中在對碎片的聚類分析上做了一定的工作。以上的研究對于規則碎片的拼接重建均取得較好的效果，能夠實現準確并快速拼接，但并不適用于非規則碎片。

針對非規則碎片。文獻［10］中提出了一種比對碎片邊緣邊長以及灰度互相關的方法來實現匹配，該方法簡單快速，容易實現，但通常情況下碎片的邊緣輪廓復雜，若僅用邊緣邊長這一特征值對其進行描述未免過于單薄，且當獲取碎片圖像時，若因光照等外界環境因素的影響而形成的相鄰碎片圖像色彩差異，則無法使用灰度互相關法。故該方法僅適用于極少數較為理想情況下的碎片拼合。文獻［11］中所提出基于角度的粗匹配以及基于角邊長的細匹配在拼接速度上有顯著的提高，但因過度依賴角點尋找的準確度，使得魯棒性較低，且最終的拼接結果精度較低。文獻［12］中采用基于弧長-累計轉角圖的分析方法進行局部匹配，再提出使用蟻群算法，即利用局部匹配所產生的候選對來構建搜索圖，通過信息素的傳遞實現全局拼接。該方法通過正反饋的過程將系統向最優解的方向不斷引導，具有較強的魯棒性，但存在收斂速度過慢，易陷入局部最優解的問題；文獻［13］中在最終拼接部分使用改進的遺傳算法，利用優勝劣汰的進化過程來克服傳統拼接技術回溯性高的問題，但因其在每一次進化當中都將當前最優匹配對進行融合，故易受局部最優的影響，無法實現遺傳算法基于全局進行最優解尋找的優越性。

針對以上所存在的問題，本文提出基于進化計算的碎紙拼接重構算法，旨在改進傳統拼接的基礎上，結合自然計算，克服需要嚴格把控外界環境、角點精準度要求過高以及易受局部最優解影響等問題，提高拼接重建的準確性和魯棒性。在特征提取階段，提出將Primal Sketch模型所得到的稀疏表示應用至目標物體邊緣輪廓的提取，因邊緣線段所具有方向性，故可便利于后續轉向角特征的計算。兩兩匹配階段，遍歷采樣點對齊算法，有效地實現碎片間的匹配對尋找，得到兩兩匹配數據庫。拼接階段采用進化計算，通過設置高效合理的編碼方式，借助迭代實現進化，最終逼近最優解。因進化計算具有良好的全局搜索能力，避免陷入局部最優解的“死循環”當中，該算法可以有效地實現二維碎片的拼接重建。

1 基于Primal Sketch的特征提取

1.1 Primal Sketch預處理

根據Guo等［14］在Marr的計算視覺理論基礎上提出的Primal Sketch模型，一幅完整的圖像可以分為可素描部分以及不可素描部分。其中可素描部分去掉了目標區域的紋理信息，用一組包含語義的有向線段來表示出位置結構信息，即對圖像進行由點和線構成的稀疏表示［15］。其實現方式是由圖1（a）所示的濾波器字典中的基元作為檢測器去對圖像中的點和線目標進行匹配，并在對應位置使用圖1（b）中的符號進行標記，得到Primal Sketch特征信息。

圖1 濾波器字典以及標記符號

因Primal Sketch特征所具有獨特的語義，故通常將該方法用作目標識別［16］或圖像降噪［17-18］。本文通過利用其所提取的顯著結構信息，得到目標區域的邊緣輪廓，并利用邊緣線段所具有的方向性，結合改進后的弧長-累計轉角圖的方法，實現特征提取與特征表示。

以圖2 所示的原始圖像為例，若使用傳統的Canny算子進行邊緣檢測，僅能得到一組如圖3（a）所示離散的點，并未包含任何結構語義信息，故對于后續的特征提取操作還需進行一系列煩瑣的處理，如角點的尋找。基于Primal Sketch的特征提取所得到的是一組有向線段組成的封閉多邊形，其具有的獨特語義，可以提取出素描線段的位置信息以及方向信息，同時具有更強的抗噪性以及稀疏性，如圖3（b）所示。

1.2 轉向角特征的提取

借助于Primal Sketch特征提取所得到的具有方向信息的邊緣線段，通過對弧長-累計轉角圖的特征提取方法進行改進［19］，將碎片的邊緣輪廓表示成一組以轉向角為元素的特征集合，并以此作為基礎進行后續的碎片間特征比對。

圖2 原始圖像

圖3 Canny算子與PrimalSketch比對

相比于文獻［19］中所提出的基于φ-s分析法中對每一段邊的長度以及相鄰邊之間的角度變化進行獨立計算，再依次設置為X 和Y 軸，將兩個度量信息合并為同一條曲線，將曲線轉化為直方圖的形式進行比對。本文在此基礎上進行改進，采取將兩個度量信息融合為一組可直接進行比對的一維特征串集合的方法。

圖4 轉向角特征表示示意圖

以圖4 所示的部分邊緣線段為例：圖中，向量a、b、c、d為組成邊緣輪廓的有向線段，以其中兩段邊緣線段b和c為例，通過計算出當前線段與其前一相鄰線段之間的夾角θ1=〈a，b〉、θ2=〈b，c〉，以此值作為特征值對兩線段的第一個相交頂點以及線段上的全部采樣點個數為代表的具體特征串形式{…，θ1，…，θ1，θ2，…，θ2，…}。其中，特征串所包含的連續元素值相同的個數即表征為該邊緣線段的長度。

改進后的方法以一維特征串集合的表示形式代替直方圖的建立，降低了數據維數，提高后續遍歷比對中的算法效率。該算法實現簡單，且具有平移旋轉不變性。即便存在有噪聲點，也因其角度差值過小或線段長度過短而被忽略，故具有強魯棒性。

2 匹配碎片數據庫的建立

對于全部待拼接碎片，以排列組合的形式得到任意兩個碎片為一組的所有可能，稱為匹配碎片。匹配碎片數據庫的建立分為3 個步驟：①匹配段的尋找。提出遍歷采樣點對齊算法，尋找到待匹配碎片對應的最優匹配段。②按照所得到的最優匹配結果對碎片對進行幾何變換，使匹配段部分重合。③根據拼接結果，對碎片對進行基于面積差值以及長度匹配值的拼接匹配度度量。

2.1 匹配段的尋找

對于2 個真正匹配的碎片而言，在其匹配段部分的轉向角變化必然是一致的，為尋找出該匹配片段，本文提出遍歷采樣點對齊算法，即通過使用遍歷的方式，依次以一個碎片上的每一個單位采樣點為起點，與另一碎片的固定起始點進行對齊，進行差值比對。當轉向角集合的差值在誤差閾值內的個數為最多時則為最佳匹配，同時，得到最佳匹配段的坐標信息。

算法的具體步驟如下：

選取長度較長的碎片記作seg_A，長度較短的記作seg_B。取seg_A的方向為順時針，seg_B 的方向為逆時針。

固定seg_B保持不動，將seg_A 從第1 個采樣點開始依次作為匹配的起點，同時截取與seg_B 相等的長度和其進行比對。完成一次比對，seg_A 向左移動一個采樣間隔的單位，直到seg_A 的所有采樣點均被遍歷到作為起始點與seg_B 的第1 個點對齊進行比對。其匹配過程的算法思想如圖5 所示。

由于碎片的邊緣輪廓是封閉圖形，故在進行比對時，當seg_A移動到比對長度小于seg_B的長度時，需要將seg_A的首部移動拼接到尾部，以始終保持seg_

A與seg_B的比對長度相同。其移動拼接示意圖，如圖6 所示。

圖5 匹配過程

圖6 移動拼接

對于每一次遍歷得到的比對段，計算其特征間的差值，得到多個特征差值集合。同時計算出集合中元素值在閾值內的個數，選取個數最多的情況為該碎片對的最佳匹配，并找到該情況下連續元素值在閾值內的片段為最佳匹配段。提取最佳匹配段首尾兩點的坐標，記為位置信息。統計最佳匹配段所包含采樣點的個數，得到長度信息記為匹配長度度量函數其中：i、j為兩個進行匹配段尋找的碎片編號。特征差值比對如圖7 所示，其中abs 即比對后所得的特征差值集合。在理想情況下，匹配段的特征差值為0，故在此用數值0 表示元素值在閾值內的情況。

圖7 特征差值比對

2.2 匹配碎片的拼接

得到碎片的匹配信息后，使用平移矩陣

式中，rotateangle為旋轉角度。

對碎片進行操作，實現碎片間的兩兩拼合。矩陣形式如式（1）、（2）。

平移距離以及旋轉角度的選取原則如圖8 所示。

圖8 移動參數選取

2.3 拼接碎片的匹配度度量

通過建立匹配碎片數據庫，來對碎片對之間拼接的優劣情況進行度量。數據庫的內容包含匹配面積度量函數以及匹配長度度量函數。

式中：arearepeat為面積疊加值；areaspace為面積空隙值；areai、areaj分別為碎片i與碎片j的獨立面積。

S(i，j)的值越大，其匹配效果越差；反之，匹配效果越好。

匹配長度度量函數L(i，j)即為3.1 節中計算所得。

3 基于進化計算的全局拼接

二維碎片的拼接屬于非確定性多項式（Non deterministic Polynomial，NP）問題，其特點為驗證一個問題的解要比生成一個問題的解快得多。對于此類問題，若使用窮舉法來進行處理，算法的復雜度會成指數上升，勢必大大增加算法的執行時間。

傳統方法通過遍歷的方式尋找局部最優解直接進行拼接，再將二者融合更新為一個整體進行下一次的尋找。一旦某一次的局部最優解尋找錯誤，則導致最終結果錯誤，需要回溯至出錯位置重新向下進行，故效率較為低下。進化計算通過模擬生物進化論，以“優勝劣汰”的方式基于全局尋找適應度最高的匹配方案，進行最終拼接［6，20］。算法流程如圖9 所示。

3.1 編碼方式

本文采用順序排列的二進制編碼對問題的解進行表征。與一般形狀為“長條形”或“正方形”的規則碎片編碼方式不同，本文研究的碎紙片由于形狀的不規則性以及碎裂位置的隨機性，無法使用傳統的編碼方式。針對不規則碎紙片對象，結合兩兩匹配數據庫，利用二值符號集合｛0，1｝表示碎片對的拼接與否，得到更加靈活的編碼方式。

圖9 進化計算流程圖

隨機生成一個個體數為M的初始化種群，基因的排列即按照碎片序號由小到大依次與后面碎片進行匹配的順序，若碎片總數為X，則理想狀態下其染色體長度為

但實際情況下，無法保證任意2 碎片間均有配對的可能，故應針對實際情況調整染色體長度。

3.2 適應度函數

適應度函數的設置決定了算法的收斂速度以及最終結果，故合適的適應度函數極其重要。考慮到相關參數對拼接優劣的影響，對于3.1 節中得到的匹配長度度量函數L(i，j)以及3.3 節中得到的匹配面積度量函數S(i，j)，通過

進行計算，得到適應度函數fitness(p) ，用來判斷個體p相對于整個種群的適應度優劣。

因匹配面積與匹配長度的結果值差距較大，故通過將其統一到同一數量級，并結合二者在拼接優劣判斷中所占的不同權值比重，設置比例參數λ 和μ。λ即關于匹配長度的比例參數，μ 即關于匹配面積的比例參數。

3.3 遺傳算子

選擇算子作為實現“優勝劣汰”思想的具體實施步驟，本文采用錦標賽選擇法。即在每一次的迭代過程中，從種群中抽取一定數量的個體，選擇其中適應度值最高的進入到子代種群，重復該操作直到種群規模達到原來的規模。該方法具有更強的隨機性，在保證種群多樣性的同時，使算法快速收斂至最優結果。

交叉算子采用一點交叉。當條件滿足交叉概率時，將相鄰兩個染色體從中間位置進行一點交叉，提高遺傳算法的搜索能力。

變異算子采用二進制變異。當條件滿足變異概率時，隨機選取染色體上任一基因位，對該位置的基因進行取反，保證種群的多樣性。

通過選擇，交叉以及變異操作，不斷地使種群得到進化，最終實現收斂為對環境適應最佳的個體，該個體即所求得問題的最優解。

4 實驗結果

本文使用Matlab 為平臺，對兩張真實的碎紙片分別進行實驗。實驗一針對發票碎紙數據。實驗二針對照片碎紙數據。均能實現100%的復原成功率。

實驗1：碎紙片的數字化圖像由CCD 相機拍照所獲取，如圖10 所示。

圖10 碎紙片數據1

對于碎紙片的數字化圖像，進行基于Primal Sketch的特征提取，并通過碎片匹配算法得到兩兩匹配數據庫，如圖11 所示。

在最終拼接階段，按照表1 對進化計算的相關參數進行設置。對于其中適應度部分的兩個參數λ 和μ，通過表2 進行參數取值對比。由表中數據可得，當參數取值λ = 0.1、μ = 100 時，由于給予匹配長度過高的權值，使得適應度判斷幾乎沒有考慮到匹配面積的影響，故最終收斂結果無法成功得到最優解。而當λ =0.01、μ = 1 000 時，可以在使用最少迭代次數的情況下找到最優解，提高運行速度，故本文選取該參數進行實驗。

圖11 匹配碎片數據庫中部分碎片對

表1 進化計算相關參數設置

表2 適應度函數參數取值對比

對于進化計算通過“優勝劣汰”逐代演化出的全局適應度最高的拼合方案，從兩兩匹配數據庫中選擇出相應的碎片對進行最終的拼合。其迭代過程如圖12 所示。碎紙拼接重構結果如圖13 所示。實驗證明，本文所進行的算法研究，可以將獨立的發票碎紙數據還原成完整的紙張形狀。

圖12 進化計算迭代過程

圖13 重建結果1

實驗2：照片碎紙原始數據如圖14 所示。最終的拼接結果如圖15 所示。

圖14 碎紙片數據2

圖15 重建結果2

5 結 語

針對碎紙拼接目前所存在的人工拼接難的問題，本文提出了一種基于進化計算的碎紙拼接重構算法。通過基于Primal sketch 的特征提取，并結合進化計算以“優勝劣汰”的方式求取基于全局的最優拼合方案，實現較為精準的碎紙片拼接重構，大大地提高了拼接的效率。但對于待處理碎片數據出現磨損的情況，則無法實現拼接重建，在后續的工作中將結合深度學習的方法來克服該缺陷，增加算法的適用范圍，實現更加精準的重構結果。