一種基於網格分割的三維模型檢索方法
2023-05-02 20:41:01
一種基於網格分割的三維模型檢索方法
【專利摘要】本發明公開了基於網格分割的三維模型檢索方法，包括以下步驟：通過分層譜分析構造分割場，包括：凹頂點判斷，拉普拉斯矩陣構造，矩陣分解與低頻特徵向量選擇，子特徵向量生成與子特徵向量權重計算以及邊符號矩陣構造。在分割場中採樣等值線，利用分組-合併算法對等值線分組和合併，得到若干候選等值線組集合，根據候選等值線組中每條等值線的權重確定最終的分割邊界，完成三維模型自動分割。通過計算三維模型每個分割塊的特徵描述子矩陣得到三維模型混合特徵描述子矩陣，並分別計算待檢索的目標三維模型與待檢索的三維模型資料庫中的每一個三維模型的混合特徵描述子矩陣的相似度，將三維模型間的相似度數值從低到高排序輸出，完成三維模型檢索。
【專利說明】—種基於網格分割的三維模型檢索方法【技術領域】
[0001]本發明涉及一種三維模型比較和檢索的方法，特別是一種基於網格分割的三維模型檢索方法。
【背景技術】
[0002]三維模型檢索是三維模型研究和其他相關應用領域中非常重要的一個研究方向。從大型資料庫中有效檢索三維模型已成為諸多商業應用中的迫切需求，具有較高的商業、經濟價值和市場前景。目前為止，很多學者和研究機構都提出了各種三維模型檢索算法，基於內容的三維模型檢索算法大致可歸為四類，分別是:基於統計數據的檢索算法，基於函數分析的檢索算法，基於拓撲結構的檢索算法和基於視覺特徵的檢索算法。以上各種檢索算法都有自己的優缺點，沒有哪一種算法可以對所有模型提供好的檢索性能。怎樣挖掘新型的檢索算法，提高精確度，是今後算法研究的主要方向。
[0003]三維模型分割可看作網格分割的特殊應用，在幾何處理和形狀理解領域，網格分割是一個基礎問題，它旨在將一個三維多邊形網格分割為不相交但有意義的若干子部分的過程，同時，網格分割可以為網格結構提供高層語義理解。在近年來，網格分割已經成為一個重要的研究熱點。它已經成為許多幾何造型和計算機圖形學應用中的重要組成部分。網格分割技術得益於圖像分割，有限元網格分割，無監督機器學習等領域的發展，它為網格曲面的很多應用提供了便利。在變形過程中，網格分割可以用來指定網格之間的對應。在網格的壓縮和簡化中，可以利用分割來提高壓縮比例。在紋理映射中，分割部分被直接用來進行參數化。現存的網格分割算法大致可分為三類，分別是:譜分析方法，區域增長法和統計學習方法。
【發明內容】
[0004]發明目的:本發明所要解決的技術問題是針對現有三維模型檢索技術的不足，提供一種新穎的基於網格分割的三維模型檢索方法。
[0005]本發明方法首先通過自動分割，將模型中有意義的若干子部分分割出來，然後計算每個分割塊的特徵描述子形成混合特徵描述子，從而從三維模型資料庫中快速準確的查找到與輸入的三維模型最接近的模型。
[0006]為了解決上述技術問題，本發明公開了一種基於網格分割的三維模型檢索方法，包括以下步驟:
[0007]對三維模型資料庫中的以及待檢索的三維模型，執行步驟I~步驟10:
[0008]步驟1:分析三維模型，三維模型由三角面片構成，保存其頂點信息、邊信息和三角面片信息，計算頂點、邊和三角面片之間的拓撲關係，包括每個頂點的鄰接頂點、鄰接面、鄰接邊，每個三角面片的鄰接面以及每條邊的鄰接面；
[0009]步驟2:通過合併三種頂點凹凸性的判斷方法，選擇三維模型中分布在凹區域的頂點集合；[0010]步驟3:根據步驟2得到的凹頂點集合，構造拉普拉斯矩陣並分解拉普拉斯矩陣，得到特徵值集合
【權利要求】
1.一種基於網格分割的三維模型檢索方法，其特徵在於，包括以下步驟: 對三維模型資料庫中的以及待檢索的三維模型，執行步驟I~步驟10: 步驟1:分析三維模型，計算頂點、邊和三角面片之間的拓撲關係，包括每個頂點的鄰接頂點、鄰接面、鄰接邊，每個三角面片的鄰接面以及每條邊的鄰接面； 步驟2:通過合併三種頂點凹凸性的判斷方法，選擇三維模型中分布在凹區域的凹頂點集合； 步驟3:根據步驟2得到的凹頂點集合，構造拉普拉斯矩陣並分解拉普拉斯矩陣，得到特徵值集合認1入,…和特徵向量集合佐石々,…,ξη.}，nVOT表示三維模型頂點個數； 步驟4:從特徵向量集合中選擇能夠表達三維模型局部和全局幾何特徵的低頻特徵向量; 步驟5:利用K-Means聚類算法，以三維模型的頂點位置信息作為輸入進行聚類，根據K-Means聚類結果將步驟4中得到的低頻特徵向量分解為子特徵向量； 步驟6:計算每個子特徵向量的權重和符號，為步驟4中得到的低頻特徵向量構造權重矩陣和符號矩陣； 步驟1:利用步驟6得到的權重矩陣和符號矩陣，構造單值分割場； 步驟8:在單值分割場中採樣等值線並利用分組合併算法構造等值線組集合； 步驟9:計算等值線權重，根據等值線權重，從每個等值線組中選擇最大權重等值線作為分割線，完成三維模型分割，得到一組分割塊； 步驟10:計算每個分割塊的特徵描述子矩陣； 步驟11:計算待檢索三維模型與三維模型資料庫中每一個三維模型的相似度，按照相似度數值從低到高排序輸出，完成三維模型檢索。
2.根據權利要求1所述的一種基於網格分割的三維模型檢索方法，其特徵在於，步驟2包括以下步驟: 第一個頂點凹凸性的判斷方法為:
3.根據權利要求2所述的一種基於網格分割的三維模型檢索方法，其特徵在於，步驟4包括以下步驟: 計算特徵值集合—隊.λ2,…人胃}二階差分，得到集合M11 ?λ2,..., vinvj；
4.根據權利要求3所述的一種基於網格分割的三維模型檢索方法，其特徵在於，步驟5和步驟6中， 步驟5中，利用K-Means聚類算法，將三維模型聚類為50個區域{patchy patch2, patch3,…，patch5(l},相應的每個低頻特徵向量ξ d也被分為50個子特徵向量{SEd；1, SEd；2, - ,SEd；50}且 ξ d=SEd；1 Π SE42-Π SEdj50,1 ≤ d ≤ neigen，neigen 表示步驟 4中得到的低頻特徵向量個數； 步驟6中，計算每個子特徵向量的權重wd，m，子特徵向量的權重由兩部分組成: wd,m=IVd； m.1g(PO4m)，其中，I≤m≤50 ; IVd，m計算公式為:
5.根據權利要求4所述的一種基於網格分割的三維模型檢索方法，其特徵在於，步驟7中，構造單值分割場包括: 構造矩陣A和矩陣b，其定義為:
6.根據權利要求5所述的一種基於網格分割的三維模型檢索方法，其特徵在於，步驟9中，分割線的選擇包括: 計算每條等值線Is的得分scs:
SCs=SCs, c.SCs,廣.SCs, 7， 其中，SCs，。表示凹凸性得分，SCy表示長度得分，SCs，m表示平滑度得分； SCs，。定義計算公式為:
7.根據權利要求6所述的一種基於網格分割的三維模型檢索方法，其特徵在於，步驟10中，分割塊特徵描述子矩陣計算如下， 分割塊中任意兩個三角面片g，h，其中I < g, h < nsegb, nsegb表示分割塊中包含三角面片的數目，由角度Θ和距離d描述的特徵值(dgh，9gh)的計算如下:
(dgh，0gh) = (min( CPj I/I CPj , | CPh | / CPg ), acos ), 其中C為三維模型的質心，Pg和Ph分別是分割後得到的一個分割塊中三角面片g，h各自對應的質心，IlCPgII為三維模型的質心c到三角面片質心Pg所構成的向量的長度，CPhI I為三維模型的質心C到三角面片質心Ph所構成的向量的長度，acos 為向量CPg和向量CPh形成的夾角； 分割塊中所有三角面片對的特徵值計算之後，將其投影到以角度Θ為橫軸，距離d為縱軸的二維坐標系中，所統計出的每一個特徵值(dgh，Θ gh)都對應坐標系中的一點； 根據dgh e [O, I]且Θ gh e [O, π],把橫坐標Θ軸均勻劃分M份,間隔長度為π/Μ,把縱坐標d軸均勻劃分N份，間隔長度為1/N，由此將坐標系劃分成了 MXN份；每一個特徵值(dgh, 9gh)都落於MXN份中的一份，計算每一份中所落入的特徵值佔所有特徵值的百分比，形成了 MXN矩陣。
【文檔編號】G06F17/30GK103914571SQ201410172378
【公開日】2014年7月9日 申請日期:2014年4月25日 優先權日:2014年4月25日
【發明者】路通, 秦龍飛, 王昊 申請人:南京大學