面向制造領域的三視圖模型組件快速檢索方法研究*

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

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

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

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

1 壓縮感知理論

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

y=Φx=ΦΨa=Θa

(1)

稱y為x的測量值。

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

通過重構系數a可以恢復原始信號x，其中δk稱為限制等容系數。其解為下列優化問題：

(2)

(3)

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

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

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

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

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

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

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

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

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

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

(4)

其中：

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

2)由于圖像在小波變換、DCT變換等變換下具有可稀疏性，根據第1節中4)的結論，當Ф滿足相應RIP條件時，由產生的測量值YM×M能夠恢復原始信號XN×N。

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

Y=CS(Φ,X)

(5)

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

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

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

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

對于分塊采用從左到右、從上到下進行編號，把第i行第j列分塊記為Dij，則

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

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

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

三個顏色映射：

(6)

紋理映射：

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

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

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

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

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

(7)

其中:

MR=(MRlh)N×N;

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

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

類似地，可以定義與其他特征相關的映射：

(8)

(9)

(10)

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

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

(11)

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

(12)

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

(13)

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

紋理相關的測量特征如下：

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

(14)

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

2.3 中心點相關的壓縮感知測量特征

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

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 基于三視圖的模型組件檢索方法

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

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

采用以下算法計算兩個組件相對應的視圖之間的相似度。

算法1 計算兩幅視圖之間相似度算法。

輸入：測量矩陣Ф。

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

方法：

STEP1對兩幅圖像按照第2.2節描述方式進行分割；

STEP3按照公式(11)-(14)分別計算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計算并歸一化處理：

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

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

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

對于兩個三維模型組件，采用基于三視圖進行檢索時，使用如圖3表示的檢索框架。

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

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

輸入：測量矩陣Ф。

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

初始化：設定兩組件Z1、Z2。Z1是待檢索組件，Z2是庫中任意組件。設定加權系數：ε1、ε2、ε3、ε。

方法：

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

STEP2 按照視圖圖像間相似度算法1分別計算三個值：

L1=D(ZZ1,ZZ2)

L2=D(CZ1,CZ2)

L3=D(FZ1,FZ2)

STEP3計算組件間的整體相似度：

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

以上方法根據三視圖可以唯一決定組件立體形狀的原理，以三視圖中相對應的兩幅視圖的相似度計算為基礎，給出整體組件的相似度。當相似度滿足閥值ε時，作為組件檢索的結果，最后采用降序原則進行排序。

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

4 仿真實驗

本文實驗數據包含機械CAD設計組件圖、機械制造零件圖、藝術設計圖、陶瓷設計圖、組合實物等共1 000套三維模型數據。在 Visual Studio 2008 環境下，對各種模型應用本文算法進行檢索可看出，本文算法具有較好的檢索結果。并從查全率、查準率這兩個性能指標進行評價，同時與其它三維圖像檢索算法進行比較。

4.1 檢索結果

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

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

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

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

圖6 機械制造零件的檢索結果Fig.6 The retrieval result of machinery manufacturing parts

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

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

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

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

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

4.2 性能分析

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

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

2)查全率、查準率分析。本文算法與文獻[9]、文獻[10]進行比較，結果如圖11所示。從中可以看出，本文算法檢索的查全率和查準率優于文獻[9]和文獻[10]。

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

5 結 論

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

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

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

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

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

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

[6] 王小鳳,耿國華,張飛. 一個相關反饋三維模型深度圖像檢索算法[J]. 計算機應用研究,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] 許志強. 壓縮感知[J]. 中國科學:數學,2012,42(9): 865-877.

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

[16] 方艷梅,楊燦,肖自美,等.基于內容圖像檢索系統的性能改進方法[J]. 中山大學學報:自然科學版,2001,40(6):39-43.

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

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

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