周 燕，曾凡智，盧炎生，周月霞

(1.佛山科學(xué)技術(shù)學(xué)院 計(jì)算機(jī)系，廣東 佛山 528000；2.華中科技大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430074)

隨著3D模型建模、數(shù)字化、可視化技術(shù)的進(jìn)步，三維模型在機(jī)械設(shè)計(jì)和制造領(lǐng)域的應(yīng)用越來越廣泛，由此產(chǎn)生了海量的產(chǎn)品模型及組件。如何有效地實(shí)現(xiàn)面向制造領(lǐng)域的存儲(chǔ)、檢索與重用這些模型組件，從而達(dá)到降低設(shè)計(jì)成本和縮短產(chǎn)品研發(fā)周期，已成為目前制造行業(yè)的一個(gè)研究熱點(diǎn)。隨著三維模型組件數(shù)量的不斷激增，現(xiàn)有搜索引擎難以滿足三維模型快速檢索要求，迫切需要一種高效的檢索方法。基于內(nèi)容的三維模型檢索(content based 3D model retrieval)應(yīng)運(yùn)而生[1-10]，從三維模型的基礎(chǔ)數(shù)據(jù)出發(fā)，提取能描述其外觀等基于內(nèi)容的特征信息，該技術(shù)不僅可用在三維模型的檢索，也用于三維物體形狀分析、識(shí)別與分類。

目前對三維模型的特征提取方法主要有：基于統(tǒng)計(jì)的特征提取、基于擴(kuò)展的特征提取、基于體積的特征提取、基于曲面幾何特征提取、基于視圖的特征提取、基于圖的特征提取等[7-8]，這些方法目前還無法從理論上驗(yàn)證它們對模型特征描述的精確度，更多的是通過查準(zhǔn)率和查全率來判斷其優(yōu)劣。特別地，如沒有考慮三維深度信息、所提取特征不能完全表達(dá)三維模型信息、用戶交互操作較難實(shí)現(xiàn)。本文結(jié)合壓縮感知理論和圖像檢索技術(shù)[11-16]，提出一種面向制造領(lǐng)域的三視圖模型組件檢索方法。首先獲得模型庫中組件的三視圖，然后采用壓縮感知方法提取三視圖的顏色、紋理等特征并將特征向量存入模型庫。其次，檢索時(shí)提取待檢索圖像的三視圖特征并與模型庫中的組件特征進(jìn)行相似性匹配，最后，結(jié)合中心點(diǎn)的壓縮測量特征，計(jì)算組件的整體相似度并輸出檢索結(jié)果。算法的核心在于首先計(jì)算單個(gè)視圖之間的相似度，然后通過正、側(cè)、俯視圖像的相似度估算出組件的整體相似度。

1 壓縮感知理論

2)選擇測量矩陣：ΦM×N，(M?N)

y=Φx=ΦΨa=Θa

(1)

稱y為x的測量值。

3)當(dāng)M?N時(shí)，對問題(1)由y計(jì)算出a并得到原始信號(hào)x是一個(gè)未定問題，但當(dāng)Θ滿足RIP條件時(shí)[11]，即對任意x是K稀疏的，如果滿足下列公式：

通過重構(gòu)系數(shù)a可以恢復(fù)原始信號(hào)x，其中δk稱為限制等容系數(shù)。其解為下列優(yōu)化問題：

(2)

(3)

問題(3)是一個(gè)線性凸優(yōu)化問題，已經(jīng)研究了各類算法如單純形法、基于貪婪迭代MP算法、正交匹配追蹤(Orthogonal Matching Pursuit, OMP)算法、稀疏自適應(yīng)匹配追蹤(Sparsity Adaptive Matching Pursuit, SAMP)算法等加以求解[ 17-18]。

上述壓縮感知理論說明，只要選取合適的Ф，就能把一個(gè)高維的可稀疏信號(hào)x∈RN用一個(gè)低維測量值y∈RM表示，并且能夠重構(gòu)原始信號(hào)。這意味著用測量值可以代表原始信號(hào)x的壓縮感知特征，本文稱y為原始信號(hào)x的壓縮測量特征。

2 圖像壓縮感知測量值提取

2.1 基于行列方式的壓縮感知測量

文獻(xiàn)[15]對壓縮感知理論應(yīng)用于圖像快速檢索做了有益的探索，其核心思想是把圖像的顏色、紋理等特征按照行或者列優(yōu)先次序形成一個(gè)高維列向量，然后采用公式(1)進(jìn)行壓縮測量得到測量值y，通過測量值y進(jìn)行圖像相似度檢索，取得了較好的檢索效果。如果能更進(jìn)一步考慮圖像中像素點(diǎn)之間的行、列之間的特征聯(lián)系及位置關(guān)系，使其根據(jù)圖像特征所計(jì)算的測量值y代表性更全面，應(yīng)該能達(dá)到更好的檢索效果。

針對這一新的思想，以下提出一種基于行列的壓縮感知測量過程，同時(shí)考慮行、列的相對位置關(guān)系，從而提取圖像的測量值作為壓縮測量特征，其測量過程如下：

1)設(shè)X是N×N矩陣，代表圖像相應(yīng)特征的原始二維信號(hào)量，記XN×N=(xij)N×N；

2)設(shè)Xi=(x1i,x2i,...,xNi)T為矩陣X的第i列構(gòu)成的列向量。

3)矩陣X可表達(dá)為：X=(X1,X2,...,XN)。

4)選取測量矩陣：ΦM×N=(Φ1,Φ2,...,ΦN)，其中Φi∈RM，測量矩陣ΦM×N的選取可參考文獻(xiàn)[19]中描述的構(gòu)造方式生成高斯隨機(jī)矩陣作為測量矩陣。

(4)

其中：

1)當(dāng)M?N時(shí)，采用以上的測量過程(4)，能夠把一個(gè)高維的N×N原始信號(hào)壓縮到一個(gè)低維的M×M的測量值。實(shí)際應(yīng)用時(shí)，行、列測量矩陣的選取可以是不同的測量矩陣。

2)由于圖像在小波變換、DCT變換等變換下具有可稀疏性，根據(jù)第1節(jié)中4)的結(jié)論，當(dāng)Ф滿足相應(yīng)RIP條件時(shí)，由產(chǎn)生的測量值YM×M能夠恢復(fù)原始信號(hào)XN×N。

3)對公式(4)產(chǎn)生的測量矩陣YM×M稱之為原始二維信號(hào)X的壓縮感知測量特征，記為：

Y=CS(Φ,X)

(5)

其中XN×N∈mN×N(R)，ΦM×N∈mM×N(R)，YM×M∈mM×M(R),mN×N(R)代表實(shí)數(shù)域R上的N×N矩陣集合。

2.2 圖像分塊壓縮感知測量特征提取

采用分塊方法提取整幅圖像的特征。設(shè)原始圖像大小為L×L，采用N×N像素的小分塊對原始圖像進(jìn)行分塊，如圖1所示。分塊行、列數(shù)為B=L/N，則分塊總數(shù)為H=B2。

圖1 圖像分塊示意圖Fig.1 The schematic diagram of image block

對于分塊采用從左到右、從上到下進(jìn)行編號(hào)，把第i行第j列分塊記為Dij，則

Dij={(x,y)|(i-1)*N+1≤x≤i*N,

(j-1)*N+1≤y≤j*N且x,y都為整數(shù)}

1)針對Dij分塊，與其分塊相關(guān)的各類特征值如顏色R(紅)、顏色G(綠)、顏色B(藍(lán))，紋理等特征都是定義在Dij的一個(gè)映射.

三個(gè)顏色映射：

(6)

紋理映射：

其中：對于紋理特征映射，選取如下方式：

P(i,j)=#{(x1,y1)∈Dij|f(x1,y1)=f(i,j)}，其中(i,j)∈Dij。

f(x,y)為二維數(shù)字圖像的灰度函數(shù)，級(jí)別為Ng，P(i,j)代表空間關(guān)系的灰度共生矩陣。顏色特征映射類似。

2)對于Dij上的某類特征如紅色分量R，通過以下映射形成一個(gè)N×N的原始信號(hào)表示的矩陣。

定義域Dij上與紅色分量特征有關(guān)的映射如下：

(7)

其中:

MR=(MRlh)N×N;

MRlh=R((i-1)*N+l,(j-1*N+h))

1≤l,h≤N,函數(shù)R(·,·)由(6)給出。

類似地，可以定義與其他特征相關(guān)的映射：

(8)

(9)

(10)

3)對于Dij分塊，原始信號(hào)包含了顏色(R、G、B)、紋理等相關(guān)信號(hào)，采用公式(7)-(10)分別得到N×N的各類原始信號(hào)，采用公式(5)得到M×M的各類壓縮測量特征值。顏色相關(guān)的三個(gè)測量特征如下：

RYij=CS(Φ,MR(Dij,R(·,·)))

(11)

BYij=CS(Φ,MB(Dij,B(·,·)))

(12)

GYij=CS(Φ,MG(Dij,G(·,·)))

(13)

公式(11)、(12)、(13)分別代表紅、藍(lán)、綠三類顏色的壓縮感知測量特征。

紋理相關(guān)的測量特征如下：

PYij=CS(Φ,MP(Dij,P(·,·)))

(14)

其中，在(11)-(14)中，i,j=1...B。

2.3 中心點(diǎn)相關(guān)的壓縮感知測量特征

以P0(x0,y0)為中心，以D00作為原始信號(hào)的選取窗口。在該觀察窗口上，采用公式(5)得到顏色、紋理等原始信號(hào)的壓縮感知測量特征，記：

RY00=CS(Φ,MR(D00,R(·,·)))

(15)

BY00=CS(Φ,MB(D00,B(·,·)))

(16)

GY00=CS(Φ,MG(D00,G(·,·)))

(17)

PY00=CS(Φ,MP(D00,P(·,·)))

(18)

3 基于三視圖的模型組件檢索方法

在工業(yè)設(shè)計(jì)、藝術(shù)設(shè)計(jì)等領(lǐng)域中，由組件或者零件的正、側(cè)、俯視圖能夠唯一確定一個(gè)組件的立體圖形。因此，要檢索具有相似的兩個(gè)組件或者零件，只需要比較其相應(yīng)三視圖的相似性，從而檢索出具有相似特征的組件或零件。檢索算法的核心是：首先給出單個(gè)視圖之間的相似度，然后通過正、側(cè)、俯視圖像的相似度估算出組件的整體相似度。

1)計(jì)算兩幅三視圖圖像之間的相似度。

采用以下算法計(jì)算兩個(gè)組件相對應(yīng)的視圖之間的相似度。

算法1 計(jì)算兩幅視圖之間相似度算法。

輸入：測量矩陣Ф。

輸出：視圖圖像T,T′的相似度D(T,T′)。

方法：

STEP1對兩幅圖像按照第2.2節(jié)描述方式進(jìn)行分割；

STEP3按照公式(11)-(14)分別計(jì)算T,T′的顏色、紋理壓縮測量特征：

RYij=CS(Φ,MR(Dij,R(·,·)))

BYij=CS(Φ,MB(Dij,B(·,·)))

GYij=CS(Φ,MG(Dij,G(·,·)))

PYij=CS(Φ,MP(Dij,P(·,·)))

(i,j=0...B)

STEP4計(jì)算并歸一化處理：

STEP5計(jì)算兩幅圖像T,T′的相似度，輸出：

D(T,T′)=ε1LR+ε2LB+ε3LG+ε4LP。

2)檢索兩個(gè)三維模型組件匹配算法。

對于兩個(gè)三維模型組件，采用基于三視圖進(jìn)行檢索時(shí)，使用如圖3表示的檢索框架。

圖3 三維模型檢索總體框架Fig.3 The overall framework for three-dimensional model retrieval

算法2 三維模型組件匹配算法。

輸入：測量矩陣Ф。

輸出：相似度滿足要求的檢索組件Z2。

初始化：設(shè)定兩組件Z1、Z2。Z1是待檢索組件，Z2是庫中任意組件。設(shè)定加權(quán)系數(shù)：ε1、ε2、ε3、ε。

方法：

STEP1設(shè)Z1的正、側(cè)、俯圖像分別記為ZZ1、CZ1、FZ1，Z2組件的正、側(cè)、俯圖像分別記為ZZ2、CZ2、FZ2。

STEP2 按照視圖圖像間相似度算法1分別計(jì)算三個(gè)值：

L1=D(ZZ1,ZZ2)

L2=D(CZ1,CZ2)

L3=D(FZ1,FZ2)

STEP3計(jì)算組件間的整體相似度：

STEP4輸出滿足HD≤ε條件的庫中前32幅組件Z2。

以上方法根據(jù)三視圖可以唯一決定組件立體形狀的原理，以三視圖中相對應(yīng)的兩幅視圖的相似度計(jì)算為基礎(chǔ)，給出整體組件的相似度。當(dāng)相似度滿足閥值ε時(shí)，作為組件檢索的結(jié)果，最后采用降序原則進(jìn)行排序。

在本文的仿真試驗(yàn)中，對算法2分別選取ε1=0.4、ε2=0.3、ε3=0.3、ε=0.02。

4 仿真實(shí)驗(yàn)

本文實(shí)驗(yàn)數(shù)據(jù)包含機(jī)械CAD設(shè)計(jì)組件圖、機(jī)械制造零件圖、藝術(shù)設(shè)計(jì)圖、陶瓷設(shè)計(jì)圖、組合實(shí)物等共1 000套三維模型數(shù)據(jù)。在 Visual Studio 2008 環(huán)境下，對各種模型應(yīng)用本文算法進(jìn)行檢索可看出，本文算法具有較好的檢索結(jié)果。并從查全率、查準(zhǔn)率這兩個(gè)性能指標(biāo)進(jìn)行評(píng)價(jià)，同時(shí)與其它三維圖像檢索算法進(jìn)行比較。

4.1 檢索結(jié)果

選擇機(jī)械制造零件類和組合實(shí)物類三維圖像作為待檢索圖像(圖4)。由三維圖像得到相應(yīng)的三視圖(圖5)，并以正、側(cè)、俯視圖作為待檢索圖像，分別檢索出相似度排序前32幅圖像作為檢索結(jié)果。然后，基于三視圖的綜合相似度，檢索出三維圖的檢索結(jié)果，從圖中檢索結(jié)果圖可以看出，檢索效果優(yōu)良，查全率和查準(zhǔn)率高。見圖6-圖9。

1)機(jī)械制造零件三維圖檢索效果。

圖4 機(jī)械制造零件的三維圖Fig.4 The three-dimensional figure for machinery manufacturing parts

圖5 機(jī)械制造零件的三視圖Fig.5 The three-view figure for machinery manufacturing parts

圖6 機(jī)械制造零件的檢索結(jié)果Fig.6 The retrieval result of machinery manufacturing parts

2)組合實(shí)物三維實(shí)體圖檢索效果。

圖7 組合實(shí)物三維實(shí)體圖Fig.7 The three-dimensional figure for combination physical

圖8 組合實(shí)物的三視圖Fig.8 The three-view figure for combination physical

按照機(jī)械制造零件三維圖相同的檢索方法，得到組合實(shí)物三維圖的檢索結(jié)果如圖9所示。

圖9 組合實(shí)物三維圖的檢索結(jié)果Fig.9 The retrieval result of three-dimensional figure for combination physical

4.2 性能分析

1) 魯棒性測試結(jié)果分析。對三維模型沿X、Y、Z軸隨機(jī)地進(jìn)行平移、旋轉(zhuǎn)和縮放后進(jìn)行檢索，得到的魯棒性測試結(jié)果如圖10所示。從圖中看到，本文算法對三維模型的縮放、旋轉(zhuǎn)和平移具有較好的魯棒性。

圖10 魯棒性測試結(jié)果對比Fig.10 The comparison of robustness test result

2)查全率、查準(zhǔn)率分析。本文算法與文獻(xiàn)[9]、文獻(xiàn)[10]進(jìn)行比較，結(jié)果如圖11所示。從中可以看出，本文算法檢索的查全率和查準(zhǔn)率優(yōu)于文獻(xiàn)[9]和文獻(xiàn)[10]。

圖11 查全率、查準(zhǔn)率對比分析Fig.11 The comparative analysis for recall and precision

5 結(jié) 論

三維模型檢索是計(jì)算機(jī)圖形學(xué)、機(jī)器視覺和模式識(shí)別領(lǐng)域中一個(gè)活躍的研究方向。本文應(yīng)用壓縮感知理論結(jié)合圖像的特征，給出了一種基于行列與中心點(diǎn)的壓縮感知測量過程得到壓縮感知特征值，提出一種面向制造領(lǐng)域的三視圖模型組件檢索方案。算法首先計(jì)算模型的正、側(cè)、俯視圖像的相似度，然后通過加權(quán)求和進(jìn)行融合，得到總體上模型間的相似度，在提高檢索準(zhǔn)確率的同時(shí)，也能保證檢索效率。三維模型檢索可以廣泛應(yīng)用在計(jì)算機(jī)輔助設(shè)計(jì)、分子生物學(xué)、機(jī)器人、軍事、虛擬地理環(huán)境等多個(gè)領(lǐng)域，并且在電子商務(wù)和搜索引擎的研究中也將有廣闊的應(yīng)用前景。

[1] 徐士彪,車武軍,張曉鵬. 基于形狀特征的三維模型檢索技術(shù)綜述[J]. 中國體視學(xué)與圖像分析,2010,4:439-450.

[2] 黃瑞,張樹生,白曉亮,等. 融合制造語義的三維CAD模型檢索方法[J]. 計(jì)算機(jī)集成制造系統(tǒng),2013,19(6):1177-1185.

[3] 王小鳳,張飛,耿國華,等. 一個(gè)基于深度圖像的三維模型檢索算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2012,48(7):197-200.

[4] 王羨慧,覃征,莊春曉,等. 基于差異特征協(xié)同語義標(biāo)注的三維模型檢索方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2011,23(1): 152-160.

[5] 鄭贏,周明全,耿國華,等. 多特征動(dòng)態(tài)融合的三維模型檢索方法[J]. 計(jì)算機(jī)科學(xué),2010,37(7):260-263.

[6] 王小鳳,耿國華,張飛. 一個(gè)相關(guān)反饋三維模型深度圖像檢索算法[J]. 計(jì)算機(jī)應(yīng)用研究,2012,29(6):2350-2353.

[7] HORN B K. Extended gaussian images [J]. Proceeding of the IEEE, 1984, 72(12): 1671-1686.

[8] HECZKO M, KEIM D A, DIETMAR S D, et al. Methods for similarity search on 3D databases [J]. Databank Spec-trum, 2002, 2(2): 54-63.

[9] GAO Yue, DAI Qionghai, WANG Meng, et al. 3D model retrieval using weighted bipartite graph matching[J]. Image Communi,2011,26(1):39-47.

[10] ADAN A, MERCHAN P, SALAMANCA S. 3D scene retrieval and recognition with depth gradient images[J]. Pattern Recognition Letters,2011,32(9):1337-1353.

[11] DONOHO D. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[12] CANDES E, WAKIN M. An introduction to compressive sampling [J]. IEEE Signal Processing Magazine, 2008, 25(2): 21-30.

[13] TANER I, ARIF N, NURDAL W. Nonconvex compressed sensing with partially known signal support [J].Signal Processing, 2013, 93(1):338-344.

[14] 許志強(qiáng). 壓縮感知[J]. 中國科學(xué):數(shù)學(xué),2012,42(9): 865-877.

[15] 周燕,曾凡智,盧炎生, 等.基于壓縮感知的圖像檢索方法研究[J]. 中山大學(xué)學(xué)報(bào):自然科學(xué)版,2014,53(1):57-62.

[16] 方艷梅,楊燦,肖自美,等.基于內(nèi)容圖像檢索系統(tǒng)的性能改進(jìn)方法[J]. 中山大學(xué)學(xué)報(bào):自然科學(xué)版,2001,40(6):39-43.

[17] 楊海蓉,張成,末為,等.壓縮傳感理論與重構(gòu)算法[J].電子學(xué)報(bào),2011,39(1):142-148.

[18] 甘偉,許錄平,羅楠,等.一種自適應(yīng)壓縮感知重構(gòu)算法[J]. 系統(tǒng)工程與電子技術(shù),2011,33(9):1948-1953.

[19] 曾凡智,盧炎生,周燕 . 基于壓縮傳感的半脆弱水印的視頻篡檢測算法[J]. 電路與系統(tǒng)學(xué)報(bào),2011,16(4):86-93.