基于進(jìn)化計(jì)算的碎紙拼接重構(gòu)算法研究

黨悅晨， 李 婉， 周 強(qiáng)

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

0 引 言

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

目前，在二維碎片拼接方面，國(guó)內(nèi)外已有大量學(xué)者進(jìn)行了相關(guān)研究。針對(duì)規(guī)則碎片，文獻(xiàn)［6-7］中通過(guò)建立基于0-1 規(guī)劃的拼接模型來(lái)實(shí)現(xiàn)拼接。文獻(xiàn)［8-9］中在對(duì)碎片的聚類分析上做了一定的工作。以上的研究對(duì)于規(guī)則碎片的拼接重建均取得較好的效果，能夠?qū)崿F(xiàn)準(zhǔn)確并快速拼接，但并不適用于非規(guī)則碎片。

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

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

1 基于Primal Sketch的特征提取

1.1 Primal Sketch預(yù)處理

根據(jù)Guo等［14］在Marr的計(jì)算視覺(jué)理論基礎(chǔ)上提出的Primal Sketch模型，一幅完整的圖像可以分為可素描部分以及不可素描部分。其中可素描部分去掉了目標(biāo)區(qū)域的紋理信息，用一組包含語(yǔ)義的有向線段來(lái)表示出位置結(jié)構(gòu)信息，即對(duì)圖像進(jìn)行由點(diǎn)和線構(gòu)成的稀疏表示［15］。其實(shí)現(xiàn)方式是由圖1（a）所示的濾波器字典中的基元作為檢測(cè)器去對(duì)圖像中的點(diǎn)和線目標(biāo)進(jìn)行匹配，并在對(duì)應(yīng)位置使用圖1（b）中的符號(hào)進(jìn)行標(biāo)記，得到Primal Sketch特征信息。

圖1 濾波器字典以及標(biāo)記符號(hào)

因Primal Sketch特征所具有獨(dú)特的語(yǔ)義，故通常將該方法用作目標(biāo)識(shí)別［16］或圖像降噪［17-18］。本文通過(guò)利用其所提取的顯著結(jié)構(gòu)信息，得到目標(biāo)區(qū)域的邊緣輪廓，并利用邊緣線段所具有的方向性，結(jié)合改進(jìn)后的弧長(zhǎng)-累計(jì)轉(zhuǎn)角圖的方法，實(shí)現(xiàn)特征提取與特征表示。

以圖2 所示的原始圖像為例，若使用傳統(tǒng)的Canny算子進(jìn)行邊緣檢測(cè)，僅能得到一組如圖3（a）所示離散的點(diǎn)，并未包含任何結(jié)構(gòu)語(yǔ)義信息，故對(duì)于后續(xù)的特征提取操作還需進(jìn)行一系列煩瑣的處理，如角點(diǎn)的尋找。基于Primal Sketch的特征提取所得到的是一組有向線段組成的封閉多邊形，其具有的獨(dú)特語(yǔ)義，可以提取出素描線段的位置信息以及方向信息，同時(shí)具有更強(qiáng)的抗噪性以及稀疏性，如圖3（b）所示。

1.2 轉(zhuǎn)向角特征的提取

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

圖2 原始圖像

圖3 Canny算子與PrimalSketch比對(duì)

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

圖4 轉(zhuǎn)向角特征表示示意圖

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

改進(jìn)后的方法以一維特征串集合的表示形式代替直方圖的建立，降低了數(shù)據(jù)維數(shù)，提高后續(xù)遍歷比對(duì)中的算法效率。該算法實(shí)現(xiàn)簡(jiǎn)單，且具有平移旋轉(zhuǎn)不變性。即便存在有噪聲點(diǎn)，也因其角度差值過(guò)小或線段長(zhǎng)度過(guò)短而被忽略，故具有強(qiáng)魯棒性。

2 匹配碎片數(shù)據(jù)庫(kù)的建立

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

2.1 匹配段的尋找

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

算法的具體步驟如下：

選取長(zhǎng)度較長(zhǎng)的碎片記作seg_A，長(zhǎng)度較短的記作seg_B。取seg_A的方向?yàn)轫槙r(shí)針，seg_B 的方向?yàn)槟鏁r(shí)針。

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

由于碎片的邊緣輪廓是封閉圖形，故在進(jìn)行比對(duì)時(shí)，當(dāng)seg_A移動(dòng)到比對(duì)長(zhǎng)度小于seg_B的長(zhǎng)度時(shí)，需要將seg_A的首部移動(dòng)拼接到尾部，以始終保持seg_

A與seg_B的比對(duì)長(zhǎng)度相同。其移動(dòng)拼接示意圖，如圖6 所示。

圖5 匹配過(guò)程

圖6 移動(dòng)拼接

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

圖7 特征差值比對(duì)

2.2 匹配碎片的拼接

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

式中，rotateangle為旋轉(zhuǎn)角度。

對(duì)碎片進(jìn)行操作，實(shí)現(xiàn)碎片間的兩兩拼合。矩陣形式如式（1）、（2）。

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

圖8 移動(dòng)參數(shù)選取

2.3 拼接碎片的匹配度度量

通過(guò)建立匹配碎片數(shù)據(jù)庫(kù)，來(lái)對(duì)碎片對(duì)之間拼接的優(yōu)劣情況進(jìn)行度量。數(shù)據(jù)庫(kù)的內(nèi)容包含匹配面積度量函數(shù)以及匹配長(zhǎng)度度量函數(shù)。

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

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

匹配長(zhǎng)度度量函數(shù)L(i，j)即為3.1 節(jié)中計(jì)算所得。

3 基于進(jìn)化計(jì)算的全局拼接

二維碎片的拼接屬于非確定性多項(xiàng)式（Non deterministic Polynomial，NP）問(wèn)題，其特點(diǎn)為驗(yàn)證一個(gè)問(wèn)題的解要比生成一個(gè)問(wèn)題的解快得多。對(duì)于此類問(wèn)題，若使用窮舉法來(lái)進(jìn)行處理，算法的復(fù)雜度會(huì)成指數(shù)上升，勢(shì)必大大增加算法的執(zhí)行時(shí)間。

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

3.1 編碼方式

本文采用順序排列的二進(jìn)制編碼對(duì)問(wèn)題的解進(jìn)行表征。與一般形狀為“長(zhǎng)條形”或“正方形”的規(guī)則碎片編碼方式不同，本文研究的碎紙片由于形狀的不規(guī)則性以及碎裂位置的隨機(jī)性，無(wú)法使用傳統(tǒng)的編碼方式。針對(duì)不規(guī)則碎紙片對(duì)象，結(jié)合兩兩匹配數(shù)據(jù)庫(kù)，利用二值符號(hào)集合｛0，1｝表示碎片對(duì)的拼接與否，得到更加靈活的編碼方式。

圖9 進(jìn)化計(jì)算流程圖

隨機(jī)生成一個(gè)個(gè)體數(shù)為M的初始化種群，基因的排列即按照碎片序號(hào)由小到大依次與后面碎片進(jìn)行匹配的順序，若碎片總數(shù)為X，則理想狀態(tài)下其染色體長(zhǎng)度為

但實(shí)際情況下，無(wú)法保證任意2 碎片間均有配對(duì)的可能，故應(yīng)針對(duì)實(shí)際情況調(diào)整染色體長(zhǎng)度。

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的設(shè)置決定了算法的收斂速度以及最終結(jié)果，故合適的適應(yīng)度函數(shù)極其重要。考慮到相關(guān)參數(shù)對(duì)拼接優(yōu)劣的影響，對(duì)于3.1 節(jié)中得到的匹配長(zhǎng)度度量函數(shù)L(i，j)以及3.3 節(jié)中得到的匹配面積度量函數(shù)S(i，j)，通過(guò)

進(jìn)行計(jì)算，得到適應(yīng)度函數(shù)fitness(p) ，用來(lái)判斷個(gè)體p相對(duì)于整個(gè)種群的適應(yīng)度優(yōu)劣。

因匹配面積與匹配長(zhǎng)度的結(jié)果值差距較大，故通過(guò)將其統(tǒng)一到同一數(shù)量級(jí)，并結(jié)合二者在拼接優(yōu)劣判斷中所占的不同權(quán)值比重，設(shè)置比例參數(shù)λ 和μ。λ即關(guān)于匹配長(zhǎng)度的比例參數(shù)，μ 即關(guān)于匹配面積的比例參數(shù)。

3.3 遺傳算子

選擇算子作為實(shí)現(xiàn)“優(yōu)勝劣汰”思想的具體實(shí)施步驟，本文采用錦標(biāo)賽選擇法。即在每一次的迭代過(guò)程中，從種群中抽取一定數(shù)量的個(gè)體，選擇其中適應(yīng)度值最高的進(jìn)入到子代種群，重復(fù)該操作直到種群規(guī)模達(dá)到原來(lái)的規(guī)模。該方法具有更強(qiáng)的隨機(jī)性，在保證種群多樣性的同時(shí)，使算法快速收斂至最優(yōu)結(jié)果。

交叉算子采用一點(diǎn)交叉。當(dāng)條件滿足交叉概率時(shí)，將相鄰兩個(gè)染色體從中間位置進(jìn)行一點(diǎn)交叉，提高遺傳算法的搜索能力。

變異算子采用二進(jìn)制變異。當(dāng)條件滿足變異概率時(shí)，隨機(jī)選取染色體上任一基因位，對(duì)該位置的基因進(jìn)行取反，保證種群的多樣性。

通過(guò)選擇，交叉以及變異操作，不斷地使種群得到進(jìn)化，最終實(shí)現(xiàn)收斂為對(duì)環(huán)境適應(yīng)最佳的個(gè)體，該個(gè)體即所求得問(wèn)題的最優(yōu)解。

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

本文使用Matlab 為平臺(tái)，對(duì)兩張真實(shí)的碎紙片分別進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)一針對(duì)發(fā)票碎紙數(shù)據(jù)。實(shí)驗(yàn)二針對(duì)照片碎紙數(shù)據(jù)。均能實(shí)現(xiàn)100%的復(fù)原成功率。

實(shí)驗(yàn)1：碎紙片的數(shù)字化圖像由CCD 相機(jī)拍照所獲取，如圖10 所示。

圖10 碎紙片數(shù)據(jù)1

對(duì)于碎紙片的數(shù)字化圖像，進(jìn)行基于Primal Sketch的特征提取，并通過(guò)碎片匹配算法得到兩兩匹配數(shù)據(jù)庫(kù)，如圖11 所示。

在最終拼接階段，按照表1 對(duì)進(jìn)化計(jì)算的相關(guān)參數(shù)進(jìn)行設(shè)置。對(duì)于其中適應(yīng)度部分的兩個(gè)參數(shù)λ 和μ，通過(guò)表2 進(jìn)行參數(shù)取值對(duì)比。由表中數(shù)據(jù)可得，當(dāng)參數(shù)取值λ = 0.1、μ = 100 時(shí)，由于給予匹配長(zhǎng)度過(guò)高的權(quán)值，使得適應(yīng)度判斷幾乎沒(méi)有考慮到匹配面積的影響，故最終收斂結(jié)果無(wú)法成功得到最優(yōu)解。而當(dāng)λ =0.01、μ = 1 000 時(shí)，可以在使用最少迭代次數(shù)的情況下找到最優(yōu)解，提高運(yùn)行速度，故本文選取該參數(shù)進(jìn)行實(shí)驗(yàn)。

圖11 匹配碎片數(shù)據(jù)庫(kù)中部分碎片對(duì)

表1 進(jìn)化計(jì)算相關(guān)參數(shù)設(shè)置

表2 適應(yīng)度函數(shù)參數(shù)取值對(duì)比

對(duì)于進(jìn)化計(jì)算通過(guò)“優(yōu)勝劣汰”逐代演化出的全局適應(yīng)度最高的拼合方案，從兩兩匹配數(shù)據(jù)庫(kù)中選擇出相應(yīng)的碎片對(duì)進(jìn)行最終的拼合。其迭代過(guò)程如圖12 所示。碎紙拼接重構(gòu)結(jié)果如圖13 所示。實(shí)驗(yàn)證明，本文所進(jìn)行的算法研究，可以將獨(dú)立的發(fā)票碎紙數(shù)據(jù)還原成完整的紙張形狀。

圖12 進(jìn)化計(jì)算迭代過(guò)程

圖13 重建結(jié)果1

實(shí)驗(yàn)2：照片碎紙?jiān)紨?shù)據(jù)如圖14 所示。最終的拼接結(jié)果如圖15 所示。

圖14 碎紙片數(shù)據(jù)2

圖15 重建結(jié)果2

5 結(jié) 語(yǔ)

針對(duì)碎紙拼接目前所存在的人工拼接難的問(wèn)題，本文提出了一種基于進(jìn)化計(jì)算的碎紙拼接重構(gòu)算法。通過(guò)基于Primal sketch 的特征提取，并結(jié)合進(jìn)化計(jì)算以“優(yōu)勝劣汰”的方式求取基于全局的最優(yōu)拼合方案，實(shí)現(xiàn)較為精準(zhǔn)的碎紙片拼接重構(gòu)，大大地提高了拼接的效率。但對(duì)于待處理碎片數(shù)據(jù)出現(xiàn)磨損的情況，則無(wú)法實(shí)現(xiàn)拼接重建，在后續(xù)的工作中將結(jié)合深度學(xué)習(xí)的方法來(lái)克服該缺陷，增加算法的適用范圍，實(shí)現(xiàn)更加精準(zhǔn)的重構(gòu)結(jié)果。