一種基於張量的三維模型檢索方法與流程

2023-05-25 12:35:32 1

本發明涉及基於模型的三維模型檢索領域，尤其涉及一種基於張量的三維模型檢索方法。

背景技術：

隨著計算機技術的提高和網際網路的高速發展，面對如此浩瀚的虛擬信息世界，人們對於多媒體數據形式以及規模的要求也就越來越高。由於人類正常的生產生活中所面對的都是三維的物體，相比較而言三維模型數據就要有更強的直觀視覺特性，更加符合人類的真實感知，因此三維模型數據也就繼傳統的聲音、圖像、視頻數據形式之後，成為第四大多媒體數據類型[1]。三維模型檢索技術和常用的一維和二維多媒體數據也即文字圖片等多媒體數據的檢索大有不同[2]。實際上三維模型數據本身就攜帶有大量的傳統一維、二維信息，此外還含有模型獨特的空間結構。傳統的檢索方法就不再能夠滿足對三維模型進行高效快速的數據檢索[3]。如何從海量的數據中快速、有效地獲取正確的目標模型就成為了當下亟待解決的關鍵問題。三維模型檢索技術正是在這種背景下應運而生，引起了諸多學者的關注，成為近些年來的熱點課題。

三維模型檢索的算法有很多種，但是無論採用的檢索算法是哪一種，最終的目的都是為了幫助用戶在資料庫中高效、快速、準確的自動獲取與用戶的檢索目標相匹配的三維模型。基於內容的檢索方法是近年來的研究熱點[4]，在基於內容的檢索算法中，由於三維模型信息的表示不同又可以分為兩種不同的方法：一種是基於視圖的檢索方法，一種是基於模型的檢索方法。基於視圖的檢索方法實際上是把三維模型用二維視圖來表示，再根據二維視圖進行特徵計算和比較匹配的過程[5]。基於模型的檢索方式則是把三維模型採用三維的表示法表示，一般為點和面的空間幾何結構存儲表面輪廓[6]，採用的是直接處理三維模型，從三維模型獲取結構信息等特徵。目前兩種基於內容的方法都有廣泛應用。

基於模型的三維模型檢索目前面臨的主要挑戰為：三維模型應該用什麼方法進行描述以及相似度的計算和匹配過程。根據三維模型的特性，所要提取的特徵應該滿足平移不變、尺度不變、旋轉不變等特性，在模型的變化中仍然能代表模型的特性。相似度的計算則直接影響著檢索效果。

技術實現要素：

本發明提供了一種基於張量的三維模型檢索方法，本發明避免了三維模型之間相似性計算的複雜度，解決了三維模型在形態、大小、尺寸等方面的差異造成的檢索難度等問題，詳見下文描述：

一種基於張量的三維模型檢索方法，所述三維模型檢索方法包括以下步驟：

根據關鍵點構造三角形並計算三角形描述子，所有的三角形描述子構成描述符；其中，所述關鍵點用於表徵三維模型的空間幾何特性；

使用最近鄰算法，計算出查詢模型中每個三角形描述子在參考模型中相似程度最大的k個三角形，根據每個三角形與得到的k個三角形的距離構建張量；

根據張量對查詢模型與參考模型之間的相似度進行計算，將相似度進行降序排列，獲取檢索結果序列。

所述三維模型檢索方法還包括：

根據三維模型的空間信息即點、線和面的關係，計算出資料庫中每個三維模型的關鍵點。

所述根據關鍵點構造三角形並計算三角形描述子，所有的三角形描述子構成描述符的步驟具體為：

對得到的關鍵點隨機選取三個點構造出一定數目的三角形，計算三角形的三個角度以及三個頂點的法線作為幾何特徵，每個三角形都會得到一個6維的向量作為特徵描述子，所有的三角形描述子構成整個描述符。

所述根據每個三角形與得到的k個三角形的距離構建張量的步驟具體為：

其中，hα,β,ε表示的是描述子相似度，{α,β,ε}表示的是由3個點組成三角形而形成的張量的3階來源，和分別表示兩個模型不同點{α,β,ε}得到的三角形描述子，設置為所計算的所有與最近鄰描述子歐式距離平方均值的倒數，這樣就得到了一個3階張量hα,β,ε。

所述根據張量對查詢模型與參考模型之間的相似度進行計算的步驟具體為：

根據張量計算查詢模型與參考模型之間的相似度分數；

利用l1-範數進行冪迭代，使得分配乘數x更接近布爾型二進位數值；對不同階時的v分別計算直到收斂並對其歸一化；

在得到向量v後，根據v中最大值給x賦值，隨後完成查詢模型與參考模型相似度分數的計算。

本發明提供的技術方案的有益效果是：

1、基於對三維模型的數據模式，以及模型的幾何特徵，採用計算關鍵點的方式對三維模型的空間幾何特徵進行表述；

2、根據三角形信息的表徵能力，通過利用關鍵點構造三角形，對三角形幾何信息進行計算並描述，進而由一定數目的三角形描述符來表徵該三維模型的空間幾何特徵；

3、將張量應用於模型描述符相似性的計算中，避免了由於三維模型在形態、大小、尺寸等方面差異所造成的相似性計算難度，使用l1-範數而不是經典的l2-範數稀疏化約束同樣能夠進行有效的冪迭代計算，以此降低計算複雜度。

附圖說明

圖1為一種基於張量的三維模型檢索方法的流程圖；

圖2為三維模型資料庫樣例；

圖3為對於給定的一個模型其檢索結果樣例；

圖4為本發明所提出的三維模型檢索方法的查準-查全曲線。

具體實施方式

為使本發明的目的、技術方案和優點更加清楚，下面對本發明實施方式作進一步地詳細描述。

研究表明：基於模型的檢索與基於多視圖的檢索差別在於，多視圖實際上是把三維模型轉化為一組二維視圖進行特徵提取，進而轉化為圖匹配的過程，而基於模型的檢索則要求直接在模型基礎上提取模型幾何特徵，進行特徵描述符計算和相似度計算，最後完成檢索的過程，正是由於模型特徵提取和相似度計算與二維圖匹配存在不同，本發明實施例提出了基於張量的三維模型檢索方法。

如圖1所示，本發明實施例所提出的基於張量的三維模型檢索方法，詳細步驟如下文所述：

101：根據關鍵點構造三角形並計算三角形描述子，所有的三角形描述子構成描述符；其中，關鍵點用於表徵三維模型的空間幾何特性；

102：使用最近鄰算法，計算出查詢模型中每個三角形描述子在參考模型中相似程度最大的k個三角形，根據每個三角形與得到的k個三角形的距離構建張量；

103：根據張量對查詢模型與參考模型之間的相似度進行計算，將相似度進行降序排列，獲取檢索結果序列。

其中，在步驟101之前，該三維模型檢索方法還包括：

根據三維模型的空間信息即點、線和面的關係，計算出資料庫中每個三維模型的關鍵點。

其中，步驟101中的根據關鍵點構造三角形並計算三角形描述子，所有的三角形描述子構成描述符的步驟具體為：

對得到的關鍵點隨機選取三個點構造出一定數目的三角形，計算三角形的三個角度以及三個頂點的法線作為幾何特徵，每個三角形都會得到一個6維的向量作為特徵描述子，所有的三角形描述子構成整個描述符。

其中，步驟103中的根據張量對查詢模型與參考模型之間的相似度進行計算的步驟具體為：

根據張量計算查詢模型與參考模型之間的相似度分數；

利用l1-範數進行冪迭代，使得分配乘數x更接近布爾型二進位數值；對不同階時的v分別計算直到收斂並對其歸一化；

在得到向量v後，根據v中最大值給x賦值，隨後完成查詢模型與參考模型相似度分數的計算。

綜上所述，本發明實施例通過上述步驟101至步驟103避免了三維模型之間相似性計算的複雜度，解決了三維模型在形態、大小、尺寸等方面的差異造成的檢索難度等問題。

實施例2

下面結合具體的計算公式、實例對實施例1中的方案進行進一步地介紹，詳見下文描述：

201：根據三維模型的空間信息即點、線和面的關係，計算出資料庫中每個三維模型的關鍵點，該些關鍵點用於表徵模型的空間幾何特性；

其中，本發明實施例採用了k-medoids聚類算法[7]，k-medoids是一種類似於k-means的聚類算法，對於一組要計算聚類中心的對象，在本發明實施例中對應的是某一個模型o的點集p＝{p1,p2,...,pi,...,pn}，pi為該模型的第i個點，i∈{1,2,...,n}。

對於給定的模型本發明實施例要得到m(m＜n)個關鍵點即要通過k-medoids算法得到m個中心pn,m＝{pn,1,pn,2,...,pn,k,...,pn,m}，k∈{1,2,...,m}，計算過程如下：

計算每兩個點pi,pj之間的歐氏距離也即di,j＝‖pi-pj‖，其中i,j∈{1,2,...,n}，進而對於點pj計算：

其中，di,l為點pi,pj之間的歐氏距離；vj為其餘點到點pj的距離和的衡量；i,j,l∈{1,2,...n},。

對所有點的vj進行升序排列，選取前m個最小值vj對應的pj為初始的medoids中心點，通過比較其餘點到各中心點的歐氏距離將每個點分配給離其最近的中心，獲得初始的聚類結果，並計算全部點到各自中心點的距離總和。

根據得到的聚類結果找到m個新聚類中心點，要求滿足該類中其他點到該新聚類中心點的總距離最小，替換中心點為每個新聚類中心點。重複進行比較其餘點到新聚類中心點歐式距離的大小，把各點按照這些距離重新分為m類，繼續上述步驟以更新medoids聚類中心點直至m個聚類中心點pn,m＝{pn,1,pn,2,...,pn,i,...,pn,m}都不再變化的時候停止。

202：根據關鍵點構造三角形並計算三角形描述子，所有的三角形描述子就構成了整個模型的描述符；

針對每個模型得到的關鍵點的點集，需要計算有空間特徵表示能力的描述符，本方法中採用構建三角形的方式來計算描述符。利用得到的關鍵點構造三角形並按照一定的方法計算三角形描述子，所有的三角形描述子就構成了整個模型的描述符。

大多數傳統的方法集中於在點之間使用相當簡單的幾何關係。一般試圖用一些算法直接提取特徵來對模型進行描述，通常，用於計算成對關係相似度的描述符是標量或低維向量。因此，這樣的描述符具有低辨別力，並且許多不同的點對具有類似的描述符，相似度計算將變得模糊。與普通的點和線段不同，三角形具有內部，所以能夠更好的描述這個模型結構。一個模型的三角形組在另一個圖像中具有較少的相似三角形。在這種情況下，相似度將變得不在模糊並且更容易計算。

本發明實施例進行三維模型的特徵描述符計算時，採用的是根據前述的方法得到的關鍵點按照三個點構造一個三角形，因為實際上如果兩個點是匹配的，那麼相應的三角形就是相似的，因此三角形的屬性就能夠非常好的表現整個模型點之間的結構關係。如果關鍵點的數目為m，則一共能生成個三角形，為避免信息冗餘，對查詢模型的每個點隨機選取s個三角形，即每個點由s個三角形描述，整個模型就是一共用m·s個三角形描述，然後計算這些三角形的一些特徵。

本發明實施例中對於一個模型的三角形描述符進行如下定義：

計算三角形的三個邊的向量夾角正弦值，即三角形三個外角餘弦值，計算方法為：對於某一個三角形其三個頂點為(x1,y1,z1)，(x2,y2,z2)，(x3,y3,z3)先計算這個三角形的三條邊的向量得到三條邊的向量之後，計算每個夾角的正弦值：

這樣每個三角形就得到了這樣的三個正弦值，同時再把這個三角形的三個點在z方向上歸一化，即與z方向的夾角作為一種特徵：

因此對於每個構造三角形也就獲得了一個6維的特徵描述符：

這個6維的特徵具備了相似不變性，本發明實施例採用的是一種比較簡單的三角形描述符，但實際上因為三角形所決定的空間信息更完備，能夠採用更複雜的表徵方式。

在本發明實施例中，對於每一個查詢模型，聚類得到的m個中心點被s個三角形描述符t表示，相應的查詢模型就能夠被這m·s個三角形描述符表示為t＝{t1,t2,...,tu,...,tm·s}，其中u＝{1,2,...,m·s}，對於參考模型本方法計算其全部三角形組合的描述子構成的描述符表示為r＝{r1,r2,...,rτ,...,rn}，其中τ＝{1,2,...,n}，n表示的是對參考模型m個關鍵點隨機選3個點構成的組合數。

203：使用最近鄰算法k-nn，計算出查詢模型中每個三角形描述子在參考模型中相似程度最大的k個三角形，根據每個三角形與得到的k個三角形的距離構建張量；

對於給定的查詢模型，任取三維模型庫中的一個模型作為參考模型，在得到三角形描述子之後，為了降低計算量，使用最近鄰算法k-nn計算出查詢模型中每個三角形描述子在參考模型中相似程度最大的k個三角形，根據每個三角形與得到的k個三角形的距離構建張量。

在本方法中對於給定的查詢模型，該模型o1被表示為t＝{t1,t2,...,tu,...,tm·s}，相應的對於資料庫中的參考模型o2同樣可以被表示為r＝{r1,r2,...,rτ,...,rn}。在本方法中計算模型相似度的關鍵在於計算三角形描述符的相似性計算，對於要計算相似度的兩個模型，考慮到如果計算全部的m·s個三角形要從n個三角形描述符找到與其最相似的三角形，這樣會導致模型相似度匹配的計算複雜度較高。因此本方法中利用最近鄰算法降低計算複雜度，對於每一個三角形用k-nn算法[8]，按照兩模型三角形描述子的歐氏距離即：

d(t,r)＝||t-r||2

從參考模型o2的n個三角形中找到與其最近似的k個三角形描述子。在本方法中令k＝300，即對於模型o1的每一個三角形計算得到近似度最高的300個三角形，然後再計算其與模型o2的相似度。

張量的構造是根據三角形描述子之間的相似程度來定義，由於每3個點構成一個三角形描述符，因此兩個模型的描述子之間相似度就能夠根據查詢模型3個點表示為3階張量，定義描述子之間的相似度為：

其中，hα,β,ε表示描述子相似度，{α,β,ε}表示的是由3個點組成三角形而形成的張量的3階來源，和分別表示兩個模型不同點{α,β,ε}得到的三角形描述子，設置為所計算的所有與最近鄰描述子歐式距離平方均值的倒數，這樣就得到了一個3階張量hα,β,ε，根據張量的定義可以認識到。釆用更高階的量，不僅能增加圖像特徵的幾何不變性，同時還能更好地對模型進行表述。

204：根據構造的張量，對兩個模型之間的相似度進行計算，然後重複上述步驟遍歷整個模型資料庫，得到查詢模型與所有參考模型的相似度；

在計算兩個模型相似度之前，利用步驟203中k-nn算法結果得到的相似度矩陣，減少不必要的運算。在步驟203中查詢模型的每個三角形都得到與其近似的300個參考模型的三角形描述子，在計算相似度時，若參考模型的描述子在所得300個近似描述子範圍內，則賦值為步驟203中的相似度值hα,β,ε，否則賦值為0，通過這樣的稀疏化計算能夠更快的計算模型之間的相似度，忽略不必要的計算。在計算查詢模型與參考模型的相似度時，本方法定義模型相似度的計算過程如下所示：

根據步驟203所得到的張量各個元素的值，計算兩個模型之間的相似度分數：

式中，score為兩模型相似度分數，hα,β,ε為其前述描述子相似度，xαxβxε為2進位的乘數矩陣。如果查詢模型的點組合{α1,β1,ε1}和參考模型的點組合{α2,β2,ε2}是近似的，則xαxβxε等於1，使得兩個描述子之間的近似程度hα,β,ε被累加到總分數score上，否則不相似xαxβxε將為0。

在進行相似度計算時，有一個重要的問題在於張量hα,β,ε的數值計算量是很大的，為了減少運算時間和運算量，不必計算整個張量的相似度，上式由克羅內克積表示的推導為：

其中，是將hα,β,ε表示成階數為3的張量，是乘數分配矩陣xαxβxε的向量表示，為克羅內克積，表示的是令與的第k階相乘。

實際上在進行相似度計算匹配的過程中，score的值反映了模型匹配的相似程度，其值越大，二者越相似，匹配就是使得score最大化的過程。為了獲得score的最大值使用冪迭代算法[9]。

冪迭代算法是一種簡單的算法，用來計算在匹配中需要用到的矩陣的特徵向量。在本方法中計算的是非常稀疏的，實際上在運用迭代算法時將會因此而減少很大的運算量，因為事實上，每次迭代只需要計算非零值的迭代，在計算中只需要很少的迭代次數就能達到收斂的條件。而且的所有值都是非負值，這就能保證最終收斂結果的真實性。通過冪迭代算法計算張量不同階下的特徵向量v，直至收斂：

對不同階時的向量v分別計算直到收斂，例α階如下：

其中，vα為α階的特徵向量；vβ為β階的特徵向量；vε為ε階的特徵向量。並對各階特徵向量v進行歸一化：

接下來根據各階下的特徵向量v計算2進位矩陣x最後完成相似度匹配得分score的計算。在本方法中，採用l1-範數而不是l2-範數對v進行規範化約束[10]，以達到對乘數矩陣x的計算，這樣能夠保證得到的x幾乎是2進位的，能夠保證其滿足要求。

根據前述，想要得到的是score的最大值，為了保證最大的score，採用了冪迭代算法，利用l1-範數進行冪迭代，能夠更好的稀疏化，並使得分配乘數x更接近布爾型二進位數值。

其中，表示的是hadamard積，對不同階時的v分別計算直到收斂並對其歸一化，α階如下：

其中，v(α,:,:)表示的是張量在α階下的特徵向量。在得到向量v後，根據v中最大值給x賦值，隨後完成兩個模型o1和o2相似度匹配分數score的計算。經過對整個資料庫遍歷，即可得到查詢模型與所有參考模型的近似度匹配得分score。

205：將查詢模型與所有參考模型的相似度進行降序排列，即可得到檢索結果序列。

通過對步驟204中得到的所有近似度匹配得分score進行降序排序，score分值越大則相似度越高，由此得到檢索結果序列。

綜上所述，本發明實施例通過上述步驟201至步驟205避免了三維模型之間相似性計算的複雜度，解決了三維模型在形態、大小、尺寸等方面的差異造成的檢索難度等問題。

實施例3

下面結合具體的計算公式、圖3、圖4、以及實例對實施例1和2中的方案進行可行性驗證，詳見下文描述：

本實驗使用的資料庫是基於psb(普林斯頓三維模型資料庫)資料庫的基礎上進行的，所用資料庫的部分模型示例如圖2所示。psb資料庫是由普林斯頓大學(princetonuniversity)收集並提供的。該資料庫存儲了1814個三維模型，這些模型是工作人員從293個不同域名的網上收集而來，模型資料庫有不同的存儲形式包括*.obj以及*.off等，在本設計的實驗中使用了*.off形式的數據格式。

在實驗中本方法針對選取關鍵點數目的不同即k＝20,60,100,140,180，以及每個關鍵點構造的三角形個數的不同即s＝20,40,60,80,100，進行了實驗。

查準-查全曲線(precision-recall)：查準-查全曲線是三維物體檢索的性能評估的重要指標之一，以查全率(recall)為橫坐標，查準率(precision)為縱坐標。根據以下公式求得recall和precision，做出查準-查全曲線：

其中，recall是查全率，nz是正確檢索模型的數量，nr是所有相關模型的數量。

其中，precision是查準率，nall是所有檢索模型的數量。

實驗結果顯示運用k-medoids提取關鍵點的數目在140左右達到較好的結果，對於構造三角形的數目，結果顯示數目為100時有較好的評價結果，這是因為越多的三角形數目越能表現三維模型的特徵，檢索結果越好。

本發明實施例提出的一個檢索示例如圖3所示，其中分數score表示的是查詢模型與檢索結果的相似度匹配得分，其值越大則相似度越高。查準-查全曲線結果如圖4所示，查準-查全曲線與橫縱坐標所圍面積越大，代表檢索性能越優良。由圖4可知，本方法具有較好的可行性，且實驗結果驗證了本方法的可行性與優越性。

參考文獻：

[1]李洪安.三維模型檢索及相關方法研究[d].西北大學,2014

[2]osadar,funkhousert,chazelleb,etal.matching3dmodelswithshapedistributions[c].shapemodelingandapplications,smi2001internationalconferenceon.2010:0154-0154.

[3]lamd,desouzagn.virtualdermatologist:anapplicationof3dmodelingtotele-healthcare[c].e-healthnetworkingapplicationsandservices(healthcom),201113thieeeinternationalconferenceon.ieee,2011:28-33.

[4]石林林.基於視圖的三維模型檢索技術研究[d].華中科技大學,2014.

[5]劉曉靜.基於內容的三維模型檢索方法研究及實現[d].西北大學,2008.

[6]hilagam.etal,2001,topologymatchingforfullyautomaticsimilarityestimationof3dshapes[c].2001.

[7]parkhs,junch.asimpleandfastalgorithmfork-medoidsclustering[j].expertsystemswithapplications,2009,36(2):3336-3341.

[8]shortrd,fukunagak.theoptimaldistancemeasurefornearestneighborclassification[j].informationtheoryieeetransactionson,1981,27(5):622-627.

[9]shix,lingh,huw,etal.multi-targettrackingwithmotioncontextintensorpoweriteration[c]computervisionandpatternrecognition.ieee,2014:3518-3525.

[10]liuj,jis,yej.multi-taskfeaturelearningviaefficientl2,1-normminimization[c]conferenceonuncertaintyinartificialintelligence.auaipress,2009:339-348.

本發明實施例對各器件的型號除做特殊說明的以外，其他器件的型號不做限制，只要能完成上述功能的器件均可。

本領域技術人員可以理解附圖只是一個優選實施例的示意圖，上述本發明實施例序號僅僅為了描述，不代表實施例的優劣。

以上所述僅為本發明的較佳實施例，並不用以限制本發明，凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。