張藝琨， 唐 雁， 陳 強(qiáng)

(西南大學(xué) 計算機(jī)與信息科學(xué)學(xué)院，重慶 400715)

0 引言

隨著三維模型應(yīng)用領(lǐng)域的不斷增加，提高三維模型的共享率和復(fù)用率成為當(dāng)前的研究熱點.三維模型檢索即從海量三維模型中檢索出與某一特定模型相似的所有模型的過程.根據(jù)所提取對象的不同，三維模型檢索方法分為基于文本的檢索方法和基于內(nèi)容的檢索方法.基于文本的檢索需要人為地為每個模型添加關(guān)鍵字，它帶有很大的主觀性；基于內(nèi)容的檢索是根據(jù)三維模型的特征進(jìn)行檢索，大大減少了人工干預(yù)，是當(dāng)今的研究熱點.

根據(jù)提取特征對象的不同，可將檢索方法分為3類：基于拓?fù)浣Y(jié)構(gòu)的檢索方法、基于形狀的檢索方法、基于圖像比較的檢索方法.基于形狀的檢索方法在效果上直觀且穩(wěn)定，受到廣泛研究.如Ankerst等[1]提出基于形狀直方圖的特征提取方法；Paquet等[2]用離散小波變換的方法對三維模型的特征進(jìn)行描述；Osada等[3]提出形狀分布算法.單一特征的檢索方式不能準(zhǔn)確表達(dá)模型的信息，基于多特征檢索方法融合局部特征和全局特征，成為近年來的研究熱點.如Chen等[4]通過融合Zernike矩和傅里葉系數(shù)檢索三維模型；Vranic等[5]提出基于輪廓、射線和深度信息的描述子；Zou等[6]基于主面分析和群融合提出了聯(lián)合形狀分布描述子；Li等[7]提出一種融合Zernike矩變換、傅里葉變換、深度信息和射線的三維模型檢索方法.

雖然三維模型檢索效率有明顯提高，但仍然存在很多問題，如局部特征點有效性低，影響特征點匹配精度；邊緣特征描述方式復(fù)雜度高，后續(xù)存儲量大且計算費時；局部特征不能表達(dá)模型的整體信息，特征選擇沒有統(tǒng)一的標(biāo)準(zhǔn).針對以上問題，筆者提出基于多特征融合的三維模型檢索方法，結(jié)合快速計算的ORB特征和精簡的形狀上下文特征，形成更全面的描述模型信息.對比試驗證明本方法有效提升了NN、FT、ST、E測度[8]這4個指標(biāo)值，P-R曲線也進(jìn)一步改善，大大提高檢索性能.

1 相關(guān)知識

1.1 ORB特征

ORB(oriented FAST and rotated BRIEF)是由Rublee等在ECCV2011上提出的一種基于視覺信息的特征點檢測與描述算法.它的主要思想是在特征點附近隨機(jī)選取若干點對，將這些點對的灰度值大小組成一個二進(jìn)制串，并將這個二進(jìn)制串作為該特征點的特征描述子.ORB分為提取具有方向的FAST特征點和提取具有旋轉(zhuǎn)不變的BRIEF特征描述子兩個過程.ORB特征計算速度快，它的描述子以二進(jìn)制串形式表示，不僅節(jié)約存儲空間，也大大縮短了匹配時間.

1.2 Canny算子

Canny邊緣檢測算子是Canny[9]于1986年提出的一個多級邊緣檢測算法.邊緣部分集中了圖像的大部分信息，它主要是對灰度變化的度量、檢測和定位，邊緣檢測需要有效地抑制噪聲，且盡量精確地確定邊緣的位置，因此邊緣特征是很有效的整體特征.

1.3 形狀上下文描述子

形狀上下文是一種基于輪廓的形狀描述子，由Belongie等[10]在2002年提出，是為輪廓上的像素點提供上下文信息的描述子.形狀上下文描述子的基本思想[11]：對于給定的一個形狀，通過邊緣檢測子獲取輪廓邊緣，對輪廓邊緣均勻采樣得到一組離散的點集P={pi|i=1，2，…,n}，依次選取每個采樣點作為參考點.以其中任意一參考點p為例，以p為中心建立極坐標(biāo)系，在以p為圓心R為半徑的區(qū)域內(nèi)，按距離和角度劃分區(qū)域，形成靶狀.按照距離和角度統(tǒng)計落入每個區(qū)域的點的個數(shù)，形成點的分布直方圖hp，稱為點p的形狀上下文.形狀上下文描述子是對輪廓特征點的進(jìn)一步提取，提高了特征表示的準(zhǔn)確性和有效性.

1.4 匈牙利算法

匈牙利算法最早是由匈牙利數(shù)學(xué)家King提出，用于解決二分圖的最優(yōu)匹配問題.1955年Kuhn把上述算法推廣用于求解著名的指派問題.算法的基本步驟如下[12]：

(1)對于任意給定的非負(fù)系數(shù)矩陣A,將其進(jìn)行變換，使其在各行各列中都出現(xiàn)0元素.

(2)進(jìn)行試指派，若能夠選出n個獨立的0元素，就可確定最優(yōu)置換，程序終止；否則轉(zhuǎn)(3).

(3)迭代：利用最少直線覆蓋所有0元素，確定系數(shù)矩陣中能夠找到的最多的獨立0元素個數(shù),并在沒有被直線覆蓋的部分，確定最小元素x,在被直線覆蓋的各行減去x，在被直線覆蓋的各列加上x來增減0元素的總數(shù),調(diào)轉(zhuǎn)(2).

2 基于多特征融合的三維模型檢索

為了更高效且全面地描述模型特征，提出基于多特征融合的三維模型檢索方法.對模型多視圖投影，分別對每張投影圖提取具有尺度不變性的ORB特征和準(zhǔn)確統(tǒng)計輪廓分布的形狀上下文特征，對ORB特征匹配點反復(fù)剔除迭代，并計算形狀上下文描述子間的相似度，通過特征融合計算結(jié)果.總體框架如圖1所示.

圖1 基于形狀上下文的多特征三維模型檢索方法框架圖Fig.1 The frame of 3D model retrieval method based on shape context

2.1 多視圖投影

基于視圖投影對三維模型檢索是一種很直觀的方法.單一角度分析三維模型是片面的，而投影角度過多會造成計算復(fù)雜.筆者分析相關(guān)文獻(xiàn)[13]及對比試驗結(jié)果，建立三維模型外圍72面體，選取38個頂點作為角度，進(jìn)行視圖采樣，這38個角度均勻分布于球部空間.避免角度冗余的同時，有效提取模型多個角度的視圖信息.選取杯子模型作為示例，如圖2所示，對該模型的38個角度進(jìn)行多視圖投影，如圖3所示.

圖2 杯子模型Fig.2 Cup model

圖3 投影視圖Fig.3 Projection views

2.2 特征提取

分別提取ORB局部特征點、Canny輪廓特征以及形狀上下文描述子.

2.2.1 提取ORB特征

ORB由提取FAST特征點和BRIEF特征點描述子兩部分組成，并在此基礎(chǔ)上進(jìn)行了改進(jìn)與優(yōu)化.

(1)提取FAST特征點.檢測候選特征點周圍一圈的像素值，如果候選點周圍鄰域內(nèi)有足夠多的像素點與該候選點的灰度值差別夠大，則認(rèn)為該候選點是一個特征點,定義為：

(1)

式中：I(x)為圓周上任意一點的灰度；I(p)為圓心的灰度；εd為灰度值差的閾值.如果N大于給定閾值，一般為周圍圓圈點的3/4，則認(rèn)為p是一個特征點.再計算特征點的主方向，ORB利用質(zhì)心來計算，特征點坐標(biāo)到質(zhì)心形成的向量作為該特征點特征向量，向量角度θ定義為FAST特征點的方向.

(2)提取BRIEF特征點描述子.在特征點附近隨機(jī)選取若干點對組成圖像塊，對它們進(jìn)行旋轉(zhuǎn)，再把圖像塊的灰度值二值化后組成一個二進(jìn)制串，將這個二進(jìn)制串作為該特征點的特征描述子.它的每一位都是由隨機(jī)選取的兩個二進(jìn)制點進(jìn)行比較得來的.如下：S表示隨機(jī)點位置(2×n的矩陣)，Sθ表示旋轉(zhuǎn)后的隨機(jī)點的位置，計算如式(2).得到新的隨機(jī)點位置后，利用積分圖像進(jìn)行二進(jìn)制編碼.ORB特征是BRIEF描述子的一種改進(jìn)，具有旋轉(zhuǎn)不變性、尺度不變性和對噪聲的魯棒性.

Sθ=S×Rθ.

(2)

ORB特征點提取如圖4所示，圓圈為檢測到的特征點.

2.2.2 提取Canny輪廓特征

對38張視圖用Canny算子提取輪廓信息.邊緣部分集中了圖像的大部分信息，Canny邊緣檢測算法的步驟如下.

Step 1：用高斯濾波器平滑圖像；

Step 2：用一階偏導(dǎo)的有限差分來計算梯度的幅值和方向；

Step 3：對梯度幅值進(jìn)行非極大值抑制；

Step 4：用雙閾值算法檢測和連接邊緣.

Canny邊緣檢測如圖5所示，(a)為二維的視圖投影，(b)為Canny算子提取到的邊緣特征.

圖4 ORB特征點提取Fig.4 ORB feature points detection

圖5 Canny邊緣檢測Fig.5 Canny edge detection

2.2.3 提取形狀上下文描述子

輪廓不同點處的形狀上下文是不同的，但相似輪廓對應(yīng)點處形狀上下文是相似的.點p的特征直方圖的計算方法:

(3)

用Canny算子提取模型的輪廓信息后，采集n個代表輪廓點作為采樣點，n值的選取范圍在100～200之間，對采樣點建立形狀上下文描述子，區(qū)域的劃分?jǐn)?shù)量k根據(jù)試驗對比得到.對每個采樣點都可以建立形狀上下文描述子，則每一張視圖都可以用一個矩陣來表示:

(4)

2.3 計算相似度

2.3.1 計算ORB特征點對

(1) 用匹配器檢測特征點對；

(2)設(shè)置閾值，剔除距離比例相差過大的匹配點；

(3)判斷特征點對之間是不是一一對應(yīng)關(guān)系；

(4)反復(fù)迭代消除錯誤的匹配.

檢測模型間特征點對的數(shù)量，對視圖進(jìn)行相對應(yīng)的檢測，統(tǒng)計得到兩個模型特征點對的總和作為最終的結(jié)果.d表示局部特征之間的差異度，m表示兩個模型特征點對的個數(shù)，d為:

(5)

考慮到兩個模型特征點對數(shù)可能為0，造成式(5)的分母為0，對式(5)進(jìn)行修改：

(6)

2.3.2 計算形狀上下文描述子相似度

選取形狀輪廓上任意點pj、di.hi表示點di的形狀直方圖，hj表示點pj的形狀直方圖，k表示區(qū)域劃分的數(shù)量.C(di,pj)表示兩個點之間的相似距離，令Cij=C(di,pj),則

(7)

由此可得，兩個形狀之間的距離為：

(8)

使用匈牙利算法，距離值匹配后的數(shù)值最小.

2.4 特征融合

對ORB特征和形狀上下文特征的相似度進(jìn)行融合，形成新的特征相似度D(mi,mj)，公式為：

(9)

對ORB特征相似度和形狀上下文特征相似度賦予不同的權(quán)值，分別是w1和w2，0

3 試驗

3.1 試驗環(huán)境和數(shù)據(jù)

硬件環(huán)境：Acer Veriton, D4300 Intel(R) Core(TM) i5-3470 CPU @ 3.20 GHz，8 GB內(nèi)存.

軟件環(huán)境：64位的Windows 10，MatlabR2012b和Visual Studio 2013.

試驗?zāi)Ｐ蛶欤篠HREC2012GTB[13]模型庫和普林斯頓大學(xué)提供的PSB模型庫.

SHREC2012GTB模型庫有60個類，總共1 200個模型.PSB模型庫有260個類，總共1 814個模型，該庫有兩個子庫組成：訓(xùn)練庫和測試庫.每組都是907個模型，分別包含90個和92個類，試驗是在PSB庫的測試集上進(jìn)行.

3.2 評價標(biāo)準(zhǔn)

采用行業(yè)內(nèi)5種評價標(biāo)準(zhǔn)進(jìn)行對比試驗，分別是：

(1)NN：表示返回的第一個模型屬于目標(biāo)類的比例.

(2)FT：表示返回的前C-1(C為目標(biāo)類模型的數(shù)量)個模型屬于目標(biāo)類的比例.

(3)ST：表示返回的前2(C-1)個模型屬于目標(biāo)類的比例.

(4)E：表示三維模型檢索的準(zhǔn)確率.

(5)P-R曲線圖：表示三維模型檢索總體的檢索效率.

3.3 試驗結(jié)果

3.3.1 SHREC2012GTB模型庫

本方法3D model retrieval method based on multiple feature fusion(3DMFF)與經(jīng)典算法LSD-sum算法(LSD)[14]、3D model retrieval method based on fourier and shape fusion算法(3DFSF)[15]、D2 bounding box normal angle area算法(DBNAA-DERE)[13]和3DSP-L2_1000_CHi2算法(3DSP)[16]進(jìn)行對比試驗.前4項指標(biāo)NN、FT、ST、E的對比結(jié)果如表1所示，P-R曲線的對比情況見圖6.

表1 SHREC2012GTB模型庫上的試驗對比Tab.1 Experiment comparison on SHREC2012GTB database %

3.3.2 PSB模型庫

本方法3DMFF與經(jīng)典算法D2形狀分布算法(D2)[17]、gaussian euclidean distance transform算法(GEDT)[18]、spherical extent function算法(EXT)[19]和shape histogram算法(SECSHEL)[20]進(jìn)行對比試驗.

前4項指標(biāo)NN、FT、ST、E的對比結(jié)果如表2所示，P-R曲線的對比情況見圖7.

通過對比實驗表明，本章提出的方法在SHREC2012GTB庫上取得相對好的檢索效果.融合局部特征和全局特征能夠更全面地描述模型信息，大大提高了特征匹配的質(zhì)量.

圖6 5種檢索方法的P-R曲線Fig.6 P-R curve of five retrieval methods

Tab.2 Experiment comparison on PSB database %

圖7 5種檢索方法的P-R曲線Fig.7 P-R curve of five retrieval methods

4 總結(jié)

筆者針對現(xiàn)有成果在特征選擇、表示和融合方面存在的問題，提出基于多特征融合的三維模型檢索方法.在SHREC2012GTB和PSB兩個數(shù)據(jù)庫上的對比試驗表明，使用該方法檢索精度都有提高.但距離加權(quán)求和的融合方式不具有通用性且計算復(fù)雜，在下一步工作中，考慮將多模態(tài)應(yīng)用于特征融合，將視覺顯著性應(yīng)用到模型提取中，通過深度卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，采用更高效的輪廓提取方式和局部特征，使模型描述更精準(zhǔn)全面.