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

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

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

0 引言

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

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

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

1 相關(guān)知識

1.1 ORB特征

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

1.2 Canny算子

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

1.3 形狀上下文描述子

形狀上下文是一種基于輪廓的形狀描述子，由Belongie等[10]在2002年提出，是為輪廓上的像素點(diǎn)提供上下文信息的描述子.形狀上下文描述子的基本思想[11]：對于給定的一個(gè)形狀，通過邊緣檢測子獲取輪廓邊緣，對輪廓邊緣均勻采樣得到一組離散的點(diǎn)集P={pi|i=1，2，…,n}，依次選取每個(gè)采樣點(diǎn)作為參考點(diǎn).以其中任意一參考點(diǎn)p為例，以p為中心建立極坐標(biāo)系，在以p為圓心R為半徑的區(qū)域內(nèi)，按距離和角度劃分區(qū)域，形成靶狀.按照距離和角度統(tǒng)計(jì)落入每個(gè)區(qū)域的點(diǎn)的個(gè)數(shù)，形成點(diǎn)的分布直方圖hp，稱為點(diǎn)p的形狀上下文.形狀上下文描述子是對輪廓特征點(diǎn)的進(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個(gè)獨(dú)立的0元素，就可確定最優(yōu)置換，程序終止；否則轉(zhuǎn)(3).

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

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

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

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

2.1 多視圖投影

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

圖2 杯子模型Fig.2 Cup model

圖3 投影視圖Fig.3 Projection views

2.2 特征提取

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

2.2.1 提取ORB特征

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

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

(1)

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

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

Sθ=S×Rθ.

(2)

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

2.2.2 提取Canny輪廓特征

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

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

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

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

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

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

圖4 ORB特征點(diǎn)提取Fig.4 ORB feature points detection

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

2.2.3 提取形狀上下文描述子

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

(3)

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

(4)

2.3 計(jì)算相似度

2.3.1 計(jì)算ORB特征點(diǎn)對

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

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

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

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

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

(5)

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

(6)

2.3.2 計(jì)算形狀上下文描述子相似度

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

(7)

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

(8)

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

2.4 特征融合

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

(9)

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

3 試驗(yàn)

3.1 試驗(yàn)環(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.

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

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

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

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

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

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

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

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

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

3.3 試驗(yàn)結(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)行對比試驗(yàn).前4項(xiàng)指標(biāo)NN、FT、ST、E的對比結(jié)果如表1所示，P-R曲線的對比情況見圖6.

表1 SHREC2012GTB模型庫上的試驗(yàn)對比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)行對比試驗(yàn).

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

通過對比實(shí)驗(yàn)表明，本章提出的方法在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兩個(gè)數(shù)據(jù)庫上的對比試驗(yàn)表明，使用該方法檢索精度都有提高.但距離加權(quán)求和的融合方式不具有通用性且計(jì)算復(fù)雜，在下一步工作中，考慮將多模態(tài)應(yīng)用于特征融合，將視覺顯著性應(yīng)用到模型提取中，通過深度卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，采用更高效的輪廓提取方式和局部特征，使模型描述更精準(zhǔn)全面.