運(yùn)用人工魚(yú)群算法的3D掃描碎片重建探究

劉恩盛,程效軍,黃玉花

(1. 同濟(jì)大學(xué)測(cè)繪與地理信息學(xué)院,上海 200092； 2. 井岡山大學(xué)，江西 吉安 343009；3. 現(xiàn)代工程測(cè)量國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，上海 200092)

隨著三維激光掃描技術(shù)的發(fā)展，其應(yīng)用領(lǐng)域逐步滲透到文物保護(hù)工作中[1-2]。文獻(xiàn)[3]提出了一種利用特征點(diǎn)分割碎片輪廓曲線，并分析各子輪廓之間的相似性以解決陶瓷碎片的計(jì)算機(jī)輔助修復(fù)問(wèn)題。針對(duì)文物模型幾何形狀對(duì)噪聲敏感的特性，文獻(xiàn)[4]利用GPU的高性能圖像處理能力，通過(guò)對(duì)碎片深度圖像進(jìn)行層次分析，實(shí)現(xiàn)了碎片的拼接。文獻(xiàn)[5]通過(guò)提取陶瓷碎片局部紋理、顏色信息特征，并結(jié)合其他知識(shí)，如考古學(xué)家的經(jīng)驗(yàn)、碎片的出處、所處時(shí)期的工藝水平等，對(duì)文物進(jìn)行了虛擬修復(fù)。文獻(xiàn)[6]通過(guò)頂點(diǎn)的積分不變量計(jì)算，勾勒出碎塊表面的尖銳邊緣線，并對(duì)斷裂面進(jìn)行分割，基于向前搜索技術(shù)和表面一致性的約束方法將兩兩斷裂面匹配、融合，從而實(shí)現(xiàn)了整體重建。以上方案存在一定的局限性，當(dāng)碎片缺失時(shí)容易出現(xiàn)拼接錯(cuò)誤，其次是邊緣的提取、順滑處理過(guò)程較為復(fù)雜。此外，三維空間的多碎片拼接是對(duì)象初始模型的重建過(guò)程,需要考慮不同匹配之間的全局一致性。所有碎片的拼接過(guò)程，可以看成是魚(yú)的集群。在一片水域中，魚(yú)生存的數(shù)目最多的地方一般就是本水域中富含營(yíng)養(yǎng)物質(zhì)最多的地方，依據(jù)這一特點(diǎn)來(lái)模仿魚(yú)群的覓食等行為，從而實(shí)現(xiàn)全局尋優(yōu)[7]。

1 基于粗糙集理論的碎片分類方法

碎片包含了多種特征，單一特征作為拼合依據(jù)往往有其弊端，而多碎片及多特征也造成依據(jù)選擇成為難題。粗糙集理論是一種處理不一致信息的數(shù)學(xué)工具[8],可以有效地解決決策分類問(wèn)題，涉及不確定性、不精確或不完整信息[9-10]。本文在前人點(diǎn)云特征提取研究基礎(chǔ)上[11-14]，對(duì)點(diǎn)云提取邊緣和幾何特征，并采用決策表分析得到分類。

1.1 碎片點(diǎn)云特征提取

文物通常具有旋轉(zhuǎn)軸線，其碎片同樣具有軸線和對(duì)應(yīng)的大小不等的半徑。要確定軸線和半徑需要對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行曲線擬合，本文采用三維中心濾波圓弧擬合方法。首先對(duì)碎片點(diǎn)云數(shù)據(jù)進(jìn)行中心濾波處理，再將碎片點(diǎn)云進(jìn)行圓心擬合，最后計(jì)算半徑并求出軸線。算法流程如下：

(1)

(2)

(3) 求取點(diǎn)到中心點(diǎn)的距離方差δ。

(4) 求取點(diǎn)的均方差RMS。

(5) 濾除到中心點(diǎn)距離方差δ大于n倍均方差RMS的點(diǎn)，其中n為給定的閥值。

(6) 使用最小二乘擬合圓并求取半徑值

R=sqrta·a+b·b-4·c/2

(3)

(7) 根據(jù)圓心坐標(biāo)擬合出軸線。

1.2 粗糙集理論的決策表分類

待拼合碎片構(gòu)成一個(gè)集合G，G={T1,T2,…,Ti,Tn}，每塊碎片都有邊緣、顏色、半徑及專家經(jīng)驗(yàn)等屬性。根據(jù)RGB值域范圍，這里把碎片集分成R={顏色1、顏色2，顏色3}3個(gè)大類，則所有顏色1的碎片構(gòu)成集合為X1={T1,T2,T5}，顏色2的碎片構(gòu)成集合為X2={T3,T8}、顏色3的碎片為X3={T4,T6,T7,T8}。按照顏色屬性將碎片集合G進(jìn)行了劃分。三維中心濾波圓弧擬合可以獲得碎片的半徑值，這里取半徑的最大值、最小值和中值。通過(guò)對(duì)半徑值分析構(gòu)成一個(gè)大小集合S={d1，d2,…,dn}。此外還有專家經(jīng)驗(yàn)構(gòu)成的材質(zhì)集合E={e1，e2，…,en}。在屬性決策分類中信息并不完備，見(jiàn)表1，本文“#”代表該值無(wú)法得到(受限于儀器和器物本身遮擋影響，碎片部分掃描數(shù)據(jù)缺失)，“*”表示后面總要作出決策。對(duì)于碎片集G中包含的屬性要素(最大值、中值、最小值、紋理)給定容差值，判斷第i塊碎片與第i+1塊碎片的相似度，作為劃分依據(jù)。

表1 不完備屬性決策分類

雖然決策表提供了決策信息，但依然是粗糙的，而且碎片的某些屬性值無(wú)法全部確定，造成碎片分類集的劃分不完全。對(duì)于不完備信息的處理，目前主要有兩種方法：數(shù)據(jù)補(bǔ)齊法和模型擴(kuò)展法[15-16]。

2 碎片全局匹配

碎片全局匹配問(wèn)題是一個(gè)非線性、多數(shù)量特征匹配優(yōu)化問(wèn)題。針對(duì)碎片，利用編碼機(jī)制將特征匹配方案空間映射到一個(gè)編碼空間，并給定約束條件，基于魚(yú)群算法對(duì)此編碼空間進(jìn)行搜索，以得到最優(yōu)方案，進(jìn)而按照產(chǎn)生的匹配方案來(lái)進(jìn)行碎片整體拼合。

假設(shè)一個(gè)完整的文物破碎之后由n個(gè)碎片組成，這些碎片可以用集合GA表示為GA={TA1,TA2,…,TAi,…,TAn}，n為碎片的個(gè)數(shù)，i為1到n(n≥2)中的任意一個(gè)值，第i個(gè)碎片TAi包含多個(gè)斷裂面。此處研究對(duì)象為薄壁文物，一個(gè)斷裂面近似地用一條最能夠反映出其特征的邊緣表示，則碎片TAi的斷裂面可以用集合LAi表示，LAi={lAi1,lAi2,…,lAii,…,lAin}，其中l(wèi)Ai1表示碎片TAi的第i個(gè)斷裂面上的第1條邊緣，lAi2表示碎片TAi的第i個(gè)斷裂面的第2條邊緣，lAin表示碎片TAi的第i個(gè)碎片的第n條邊緣。

在匹配過(guò)程中，碎片集中任意兩個(gè)斷裂面間可能相互匹配，但是同一碎片內(nèi)的各斷裂面不會(huì)相互匹配，整個(gè)可能匹配斷裂面可以通過(guò)矩陣M=TAijn×n表示，其中，n表示斷裂個(gè)數(shù)，i、j為斷裂面編號(hào)。在不考慮其他約束條件的情況下，得到矩陣為

TA11TA12…TA1nTA21TA22…TA2n…n

(4)

(5)

(6)

3 試驗(yàn)分析

為驗(yàn)證本文碎片匹配方法的有效性，進(jìn)行了如下試驗(yàn)。試驗(yàn)對(duì)象為一個(gè)破碎陶罐和兩個(gè)破碎瓷器的碎片,碎片存在缺失及邊緣磨損情況,如圖1所示。通過(guò)手持式三維掃描儀獲取碎片點(diǎn)云數(shù)據(jù)，如圖2所示。

選取邊緣長(zhǎng)度作為感知因子，步長(zhǎng)為0.83，得到初始矩陣。再選取邊緣對(duì)應(yīng)碎片的擬合半徑區(qū)間中值作為匹配感知因子，步長(zhǎng)為0.9，將前一步得到的匹配矩陣進(jìn)一步優(yōu)化。進(jìn)一步改變感知因子，選取顏色紋理特征作為匹配依據(jù)進(jìn)行優(yōu)化。如斷裂面處于彩色區(qū)域則與之匹配的另一邊一定具有彩色，顏色特征可以通過(guò)灰度值進(jìn)行計(jì)算。設(shè)定步長(zhǎng)為0.2，進(jìn)一步優(yōu)化。通過(guò)不斷優(yōu)化，得到可能匹配對(duì)的信息為

{(TA13,TA26),(TA13,TA411),(TA24,TA513),(TA24,TA514),(TA25,TA612),(TA25,TA615),(TA26,TA38),(TA26,TA615),(TA38,TA512),(TA37,TA616),(TA411,TA514),(TA411,TA616),(TA514,TA616)}=TAij

改變感知因子，可獲得唯一匹配(TA37,TA616)，此時(shí)該匹配作為確認(rèn)匹配對(duì)，進(jìn)而依次去除：(TA411,TA616),(TA514,TA616),(TA13,TA411),(TA24,TA513),(TA26,TA38),(TA26,TA615),(TA25,TA615)。編號(hào)TA11和TA12沒(méi)有獲得匹配結(jié)果，但是TA13得到了匹配。終止算法得到匹配對(duì)

TAij={(TA13,TA26),(TA24,TA513),(TA25,TA615),(TA38,TA512),(TA37,TA616),(TA411,TA514)}

通過(guò)改變感知因子和步長(zhǎng)一次性地得到滿足拼接要求的配對(duì)。在此過(guò)程中，對(duì)所有潛在的配對(duì)碎片都進(jìn)行了比較分析,其結(jié)果在文物碎片修復(fù)中可指導(dǎo)碎片的拼接從而避免由于錯(cuò)誤拼接導(dǎo)致的二次損壞。本文試驗(yàn)最終得到原器物正確重建結(jié)果，如圖3所示。

4 結(jié) 語(yǔ)

本文提出了一種運(yùn)用魚(yú)群算法的文物碎片全局匹配方法。該方法以三維激光掃描儀獲取碎片的點(diǎn)云數(shù)據(jù)，并進(jìn)行特征要素提取。通過(guò)三維中心濾波圓弧擬合獲取圓心與半徑。依據(jù)特征要素，使用粗糙集理論，對(duì)碎片屬性進(jìn)行約簡(jiǎn)后分類。在分類的基礎(chǔ)上，運(yùn)用魚(yú)群算法，對(duì)多特征要素進(jìn)行不斷尋優(yōu)，從而一次性獲得最終優(yōu)化方案。該算法模擬了人工拼合碎片的思維，為實(shí)現(xiàn)智能化碎片匹配提供了思路。通過(guò)實(shí)例驗(yàn)證了本文方法的可行性，能有效避免單一特征匹配造成的缺陷，解決了存在碎片缺失或磨損情況下的匹配問(wèn)題。