基于正交投影的三維模型相似性比較算法研究

摘 要:提出了一種基于二維正交投影圖像的三維模型相似性比較算法。首先計算三維模型的二維正交投影圖像，然后提取二維正交投影圖像的邊緣輪廓夾角特征，并比較這些二維正交投影圖像的相似性，最后通過二維正交投影圖像的輪廓相似性來獲取三維模型的相似性。實驗驗證了該算法的可行性，并且其對于三維模型檢索所要求的平移、旋轉和縮放不變性具有較好的魯棒性。

關鍵詞:三維模型;二維正交投影圖像;邊緣輪廓夾角;相似性

中圖分類號:TP391.41 文獻標志碼:A

文章編號:1001-3695(2010)03-1187-02

doi:10.3969/j.issn.1001-3695.2010.03.107

Research of two-dimensional orthogonal projection similarity-based 3D model retrieval

YANG Shao-bo1， GENG Guo-hua1， ZHOU Ming-quan2

(1.Dept. of Computer， School of Information Science Technology， Northwest University， Xi’an 710127， China;2.Dept. of Computer， School of Information Science Technology， Beijing Normal University， Beijing 100875， China)

Abstract:This paper proposed a two-dimensional orthogonal projection similarity-based 3D model retrieval system.Firstly，obtained two-dimensional orthogonal projections of the 3D models，and then got similarity among 3D models through matching the shape similarity among two-dimensional orthogonal projections.The experiment results show that this method is effective，and this approach is robust against translation， scaling and rotation transform.

Key words:3D model retrieval; two-dimensional orthogonal projection; contour angle; comparability

0 引言

人類視覺系統的感受部分是視網膜，它相當于一個三維采樣系統。三維模型的可見部分投影到網膜上，人們按照投影到視網膜上的二維投影圖像來對該模型進行三維理解。也就是說，人們通過比較兩個三維模型的外觀來辨別三維模型之間的相似性[1]。

計算機視覺是當前新興的一門學科，它是指用攝像機和計算機代替人眼對目標進行識別，通過把三維模型的影像作為輸入源，即輸入計算機的就是三維物體的二維圖像，用這些二維圖像去重建三維模型[2]。計算機視覺研究本來就是與人類視覺研究密切相關的學科，結合以上提到的兩點，即可獲得三維模型的二維投影圖像與用二維圖像能夠重建三維模型，于是可以推導出這樣一個結論:可以通過比較三維模型的二維投影圖像來獲取三維模型的相似性[3]。

通過比較三維模型的二維投影圖像來獲取三維模型的相似性，這是基于計算機視覺的三維模型幾何相似性比較算法的基礎，也是三維模型檢索系統中的幾何相似性比較算法之一[4]。

1 特征提取和相似性匹配

1.1 二維投影圖像的獲取

三維模型的二維投影變換可以分為兩種，即平行投影變換(正交投影)和中心投影變換(透視投影)[5]。如圖1所示，(a)是平行投影變換，平行投影變換的投影射線是相互平行的，本文采用所有投影射線都平行于坐標系中的一個軸(如Z軸)，也就是說三維模型在XOY面上的投影實際上就是模型所有頂點Z軸值為0所產生的投影圖像;(b)是透視投影，透視投影變換的投影射線都是從公共點發出，這種投影也可以稱為錐體投影。二維投影圖像可以通過上面的兩種投影變換獲得，本文采用第一種。

打開一個724個三角面片、368個點的蝴蝶三維模型(圖2(a))，分別要獲取它平行于三個坐標軸的平行投影圖像，該模型的點較少，當投影在三個坐標面上時得到的只是一些離散的點，這些點只是724個三角面片的頂點在三個坐標面上的投影，并不能從這些點中得出模型的平行投影圖像，更不可能提取出投影圖像的邊緣輪廓。為了得到完整的二維投影圖像，需將三維模型投影在坐標面上的三角形中的間隙填充起來。

假設點P和ΔABC都屬于二維投影圖像，設AP×AB代表矢量AP和AB矢性積，其表達式為

AP×AB=(xp-xa)×(yb-ya)-(yp-ya)×(xb-xa)

判別過程如下:

若AP×AB>0 and BP×BC>0 and CP×CA>0或AP×AB<0 and BP×BC<0 and CP×CA<0，則可判定P在ΔABC內。

若AP×AB=0 and (BP×BC>0 and CP×CA>0或BP×BC<0 and CP×CA<0)

若BP×BC=0 and (AP×AB>0 and CP×CA>0或AP×AB<0 and CP×CA<0)

若CP×CA=0 and (AP×AB>0 and BP×BC>0或AP×AB<0 and BP×BC<0)

可判定P在ΔABC輪廓上。將這些屬于ΔABC內和輪廓上的點都標記成屬于投影圖像內的點。用上述方法獲得的三維模型在三個坐標面上的二維投影圖像如圖2(b)~(d)所示。

1.2 二維投影圖像輪廓和邊緣輪廓夾角特征的提取

對投影圖像進行邊緣檢測和輪廓特征提取，得到投影圖像邊緣輪廓線(圖3(a)~(c))，邊緣輪廓線上像素點l(i)的集合:L={l(i)=(x(i)，y(i))|i=0，1，2，…，n-1}

對L求邊緣輪廓夾角曲線[6]:

P={p(i)|i=0，1，2，…，n-1}

圖4是對邊緣輪廓求輪廓夾角的示意圖。Dis_i_t、Dis_i_2t分別為點i到離其第t近和第2t近的點的距離。t必須與邊緣輪廓的長度成正比，令t=n/r，r不能取值太大或者太小。r值太大太小都不能準確反映輪廓夾角的變化，經過實驗證明，r一般取8~15比較合適(r的取值范圍是在本文的數據庫支持下，通過多次實驗測試比較所得結果，具有一定的普遍性)。

對邊緣輪廓夾角曲線P的長度進行歸一化，歸一化的結果為PNormalize=

{pNormalize|i=0，1，2，…，m-1}，其中，m取100。然后對PNormalize進行傅里葉變換，可以得到PFourier=F(pNormalize)，對PNormalize的循環位移只是改變了PFourier的相位，而PFourier的幅度并沒有變化，因而對傅里葉系數進行匹配可以滿足投影圖像檢索的尺度不變性。

1.3 二維投影圖像特征匹配

對兩幅要進行匹配的二維投影圖像，可以分別獲得對應的一條邊緣輪廓夾角曲線P1和P2，P1={p1(i)|i=0，1，2，…，I-1}，P2={p2(j)|j=0，1，2，…，J-1}，令I

P1和P2也有各自相對應的輪廓長度，Length1={Len1(i)|i=0，1，2，…，I-1}，

Length2={Len2(j)|j=0，1，2，…，J-1}。

分別求邊緣輪廓曲線P1和P2的傅里葉系數，即PFourier1和PFourier2，然后對PFourier1和PFourier2計算傅里葉系數的均方誤差Error(PFourier1，PFourier2)。如果該均方誤差值小于某一給定域值，則可以判定這兩幅二維投影圖像相似。

1.4 三維模型的相似匹配

前面已經可以求出三維模型在三個坐標面上的二維投影圖像的相似性了，接下來將這些一一對應的二維投影圖像的相似性綜合起來就可以得到三維模型的相似性[7]。

對于兩個三維模型x和y，將x和y的二維投影圖像邊緣輪廓夾角曲線的傅里葉系數放在x=[(x1)，(x2)，(x3)]和y=[(y1)，(y2)，(y3)]中。這里的x1、x2、x3，分別代表的是三維模型在三個坐標面上的投影輪廓取傅里葉系數后的值。其中:xk=[xk(1)，xk(2)，…，xk(n)]

yk=[yk(1)，yk(2)，…，yk(n)]，k=1，2，3。

從提取的三維模型二維投影圖像的邊緣輪廓可以看出，投影圖像的輪廓越長，對二維投影圖像相似性檢索的貢獻就越大。故令

f=3i=1Length(xi)×Length(yi)

三維模型x和y的距離為

Disx，y=3k=1nr=11f×Length(xk)×Length(yk)×dis(xk(r)，yk(r))

其中，Error(xk，yk)=nr=1dis(xk(r)，yk(r))。

2 實驗結果

本文分別從普林斯頓三維數據庫和Internet網上下載，共選用了200個動物三維模型進行實驗檢索測試。

圖5是針對一個蝴蝶三維模型的檢索結果:左邊第一個蝴蝶三維模型是待檢索模型，后面十個為檢索得到的結果(其中用黑框圈中的五個為蝴蝶模型)。圖6是本文算法和文獻[3]算法的查準率比較。

3 結束語

前面已經提到了，人類視覺系統的感受部分是視網膜，它相當于一個三維采樣系統。也就是說，人類對三維物體的理解主要依賴物體的形狀、輪廓以及邊緣信息，因而基于三維模型二維投影圖像邊緣輪廓的檢索更具說服力。在本文算法的支撐下，對200個三維模型進行了有效性檢索，

檢索得到的結果符合初期的預計。

在本文理論和實驗結果的支持下，得出了這樣的結論:該算法是通過計算三維模型在三個坐標面上正交投影的輪廓夾角來獲取模型相似度的，因而輪廓夾角的值中平角(180°附近)和零值(0°附近)越少，越能代表輪廓特征信息，檢索出來的相似度也越高。文物模型中的陶器、瓷器、瓦罐，以及動物模型中體積較大的動物等具有這類特征的模型，是比較適合于該算法的。可以將這類模型概括為:輪廓上各點到中心距離之間的差距不是過于顯著的三維模型。

本文采用的算法是基于三維模型二維正交投影圖像的檢索，而透視投影的投影射線是由公共點發出，實際上，人眼就是類似于透視投影的公共點。所以，透視投影變換是最能體現人對三維模型的視覺感覺的。基于三維模型二維正交投影圖像的檢索算法，雖然可以查找出兩個三維模型的相似性，但與透視投影圖像變換相比，它就不能直接體現出人類對三維模型的視覺感覺。為了彌補這個缺陷，可以利用透視投影變換來實現基于三維模型二維投影圖像的檢索算法[8]。利用透視投影變換來檢索三維模型，可以通過選擇適當的視點數量和恰當的視點位置來提高三維模型檢索的相似度。

參考文獻:

[1]LOFFLER J.Content-based retrieval of 3D models in distributed Web databases by visual shape information[C]//Proc of Information Visualization.Washington DC:IEEE Computer Society，2000:82-87.

[2]CYR C，KIMIA B.3D object recognition using shape similiarity-based aspect graph[C]//Proc of of the 8th IEEE International Conference on Computer Vision.2001:254-261.

[3]CHEN D Y，TIAN X P，SHEN Y T，et al.On visual similarity based 3D model retrieval[J].Computer Graphics Forum，2003，22(3):223-232.

[4]KAZHDAN M，FUNKHOUSER T，RUSINKIEWICZ S.Shape matching and anisotropy[J]. ACM Trans on Graphics，2004，23(3):623-629.

[5]章志勇.三維模型幾何相似性比較的研究[D].浙江:浙江大學，2005.

[6]曹家武，朱秋煜.一種基于輪廓的圖像檢索方法[J].計算機工程，2002，28(7):159-160.

[7]HILAGA M，SHINAGAWA Y，KOHMURA T. Topology matching for fully automatic similarity estimation of 3D shapes[C]//Proc of ACM SIGGRAPH.Los Angeles:ACM Press，2001:203-212.

[8] 章志勇，楊柏林.視覺圖像相似性在三維模型相似性比較中的應用[J].計算機輔助設計與圖形學學報，2006，18(7):1049-1053.