一種基於核密度估計的三維模型比較和檢索方法
2024-04-10 13:48:05
專利名稱：一種基於核密度估計的三維模型比較和檢索方法
技術領域：
本發明涉及一種三維模型比較和檢索的方法，特別是一種基於核密度估計的三維 模型比較和檢索方法。
背景技術：
三維掃描技術、三維形狀建模和渲染軟體以及三維系統在娛樂界和工業界的廣泛 應用，使得如何從大量三維模型庫中檢索所需的模型的需求越發迫切。與傳統的二維圖像 數據檢索相比，由於三維數據的特殊性，其檢索問題還存在一些其它的挑戰，如維度高、數 據量多、拓撲結構複雜、模型表示方式多元化等。關於三維比較，現存主要兩大方法，即基於拓撲的比較方法和基於統計的比較方 法。前者把模型轉化為不同類型的拓撲圖，然後用圖匹配的算法找出圖之間的最大公共子 圖，從而計算模型的相似性。該類方法的缺陷除了圖匹配的效率問題外，外形相似的三維模 型多樣的拓撲結構使得基於拓撲的比較算法的可靠性不能被保證。另外該類方法受噪音和 模型的缺損影響較大。後者一般把三維模型轉化為基於統計模型特徵的描述子，這樣通過 比較不同模型的描述子就能完成三維模型的比較。該類方法的缺陷在於原模型的一些拓撲 和幾何約束信息在統計的過程中往往缺失了。三維模型檢索是指「在大型三維模型資料庫中計算三維形狀之間的相似度」。
發明內容
發明目的本發明所要解決的技術問題是針對現有技術的不足，提供一種基於核 密度估計的三維模型比較和檢索方法，用於提高三維模型比較和檢索的準確性和快速性。技術方案為了實現本發明所述的目的，本發明提供的一種基於核密度估計的三 維模型比較和檢索方法，在讀取一個包含η個三角形面片的三維模型數據後，還包括以下 步驟步驟一，三維模型坐標數據的歸一化網格細分、三維模型平移歸一化、三維模型 縮放歸一化；步驟二，三維模型特徵的提取對於有η個面片的模型中的每對面片i和j，提取 它們法向夾角的餘弦值θ μ和沿三維模型表面的測地距離Li, ρ形成η(η-1)/2個特徵對
Seonstraint = Kei,"Li,pli e
, j e [i+l,n]}；步驟三，特徵的重採樣合併相鄰的特徵對數據，使得特徵對的數量從n(n-l)/2 降到η ；步驟四，核密度估計對步驟三中重採樣獲得的合併相鄰的特徵對後的特徵數據 應用多維核密度估計，生成該三維模型的特徵分布函數；步驟五，三維模型比較利用KL距離(Kullback-Leibler divergence)，通過比較 各個三維模型對應特徵分布函數的相似度，實現模型的比較和檢索。本發明中，在所述基於核密度估計的三維模型比較和檢索的方法的步驟一中，網格細分採用如下算法a)對於每個三維模型，設定一個面積閾值tharea，該面積閾值可以定為該三維模型 中所有三角面片面積的算術平均值；b)遍歷模型中的每個三角面片，如果該面片的面積大於面積閾值th ea，則在該面 片最長邊的中點到所對的頂點間連一條邊，此時原面片被分為2個新的較小的面片；c)重複步驟b)直到所有面片的面積小於或等於面積閾值tharea。本發明步驟一中，平移歸一化是把模型的質心平移到坐標原點。本發明步驟一中，縮放歸一化是把三維模型所有頂點坐標乘以一個縮放因子 factorscaling,使得三維模型各頂點到質心距離的方差為1， 即縮放因子
其中Vi為模型頂點，η為頂點個數，
Peentroid為模型質心點，ViPcentroid為從模型頂點Vi到Peentraid所構成的向量。本發明步驟二 中，設{t。，、，-VJ為三維模型的面片集合，面片、={Vil，vi2，vi3}，其中Vil、Vi2、Vi3* 面片ti三個頂點，盡為面片ti的法向量，氣為面片、的法向量，則特徵對中< Θ ^LiJ的計 算公式如下 其中Xtl = i，Xm = j，Li, J為沿三維模型表面從面片ti到面片tj的任意路徑的最 小值，且 dx為面片tx的質心到面片tx與面片ty的公共邊的距離，並使用Floyd算法(弗 洛伊德最短路徑算法)最小化Lm ；即lx,y的計算方法為如果面片tx與面片ty有公共邊， 則lx,y為從面片tx到該公共邊中點的距離與從面片ty到該公共邊中點的距離之和，否則Ix, y為正無窮大；函數min採用弗洛伊德最短路徑算法，Liij為沿三維模型表面從面片、到面 片、的所有路徑中的最小值。本發明中步驟三中，所述合併相鄰的特徵對包括以下步驟a)按法向夾角的餘弦值θ μ值的升序對特徵對S。。nsteaint的元素排序；b)均勻地劃分特徵對S。。nsteaint成l『j+l個子集，即使每個子集中特徵對的數量相 等；c)對於b)中的每個子集，按Ly值的升序對裡面的元素排序；d)均勻地劃分C)中的每個子集，使每個子集被劃分成[7^+1個更小的子集bink(k =1. . η)；e)對於每個子集bink，利用式
生成η個新的特
徵對，完成合併相鄰的特徵對。本發明步驟四中，多維核密度估計的公式為
其中(Xi，yi)為步驟三中合併後的特徵對，、和、為核密度估計中的平滑參數。本發明步驟五中，令p(i)(x)為候選模型的分布函數，q(x)為輸入模型的分布函 數，根據KL距離的理論以及本問題中特徵樣本的離散性，用於本發明的距離計算公式為
其中X為輸入模型，其特徵對為t1;t2，…，tm。有益效果隨著3D圖形硬體成本的降低和技術的成熟，三維設計技術已在影視娛 樂、機械、製造、建築、電子、化工、服裝乃至廣告等眾多領域中得到快速發展和應用。與此相 應的，三維產品數據的復用問題逐步出現，一般而言，設計者平均花費60 %的工作時間用於 產品信息的檢索，進行新產品設計時，僅約20%來自真正的創新，40%可從現有設計獲取， 另外40%則可在修改現有設計的基礎上獲得，同時，超過75%的新設計包含著對以往設計 知識的復用。因此，三維模型的復用已成為相關領域的關鍵問題之一，而三維模型的比較和 檢索檢索是解決三維產品復用的有效途徑，也是最重要的步驟，本發明大大提高了現階段 三維模型的檢索和比較的速度以及準確性，通過對三維模型檢索開展了相關科學實驗，取 得了令人滿意的效果，證明了該方法的有效性。
下面結合附圖和具體實施方式
對本發明做更進一步的具體說明，本發明的上述和 /或其他方面的優點將會變得更加清楚。圖1為本發明流程圖。圖2為本發明網格細分示意圖。圖3為本發明網格細分前後示例圖。圖4為本發明特徵計算示意圖。圖5為本發明特徵重採樣示意圖。圖6為本發明三維檢索方法與現有其它方法的性能比較效果圖。
具體實施例方式如圖1所示，本發明一種基於核密度估計的三維模型比較和檢索方法，在讀取一 個有η個三角形面片的三維模型數據後，包括以下步驟步驟一，三維模型坐標數據的歸一化，包括網格細分、三維模型平移歸一化以及 模型縮放歸一化；步驟二，三維模型特徵的提取對η個面片的三維模型中的每對面片i和j，提 取法向夾角的餘弦值θ i, j和沿三維模型表面的測地距離Li, j,形成n(n-l)/2個特徵對
Seonstraint = Kei,"Li,pli e
, j e [i+l,n]}；步驟三，特徵的重採樣合併相鄰的特徵對，使特徵對的數量從η (n-1)/2降到η ；步驟四，核密度估計進行多維核密度估計，生成三維模型的特徵分布函數；
6
步驟五，三維模型比較使用KL距離比較各個三維模型對應特徵分布函數的相似 度，實現模型的比較和檢索。步驟一中，所述網格細分包括以下步驟對於每個三維模型，設定一個閾值 tha,ea;遍歷三維模型中的每個三角面片，如果該面片的面積大於閾值tharea，則在該面 片最長邊的中點到所對的頂點間連一條邊，此時原面片被分為2個小面片；重複上一 步驟直到所有面片的面積小於等於閾值tharea。所述平移歸一化是把三維模型的質 心點平移到該三維模型所處坐標系的坐標原點。所述縮放歸一化是把三維模型所有 頂點坐標乘以一個縮放因子f ac tors。aling，使得模型各頂點到質心距離的方差為1，即
，其中Vi為模型頂點，η為頂點個數，Pcentroid為模型質心 V n /=0
點，ViPeentraid為從模型頂點Vi到Peentraid所構成的向量。步驟二中，設{t。，、，為三維模型的面片集合，面片、={Vil，vi2，vi3}，其 中Vii、vi2、Vi3為面片ti三個頂點，盡為面片ti的法向量，巧為面片、的法向量，則特徵對中 < θ U，Lu〉的計算公式如下 其中
為沿三維模型表面從面片、到面片、的任意路徑的最 小值，且
l ={ dx+dy,、與％存在公共邊 其中，dx為面片tx的質心到面片tx與面片ty的公共邊的距離，並使用弗洛伊德最 短路徑算法最小化Lu。步驟三中，所述合併相鄰的特徵對包括以下步驟按法向夾角的餘弦值θ μ值的 升序對特徵對s。。nsteaint的元素排序；將特徵對Sranstraint劃分成問+1個子集，使每個子集中特 徵對的數量相等；對上一步驟所述每個子集，按Li, j值的升序對每個子集裡的元素排序；劃 分上一步驟中的每個子集，使每個子集被劃分成l^j+l個更小的子集bink，其中k = 1 η中
任意自然數；對於每個子集bink，利用式=α Σθυ '\bink[Lk = YdL 生成η個 新的特徵對。4 ？變量名或者參數名？步驟四中，所述利用多維核密度估計生成三維模型的特徵分布函數的公式為 其中(Xi，Yi)為步驟三中合併後的特徵對，hx和hy為核密度估計中的平滑參數。步驟五中，令p(i)(x)為候選三維模型的特徵分布函數，q(x)為輸入三維模型的特 徵分布函數，所述KL距離計算公式為
其中X為輸入模型，其特徵對為t1;t2，…，tm。基於核密度估計的三維模型比較和檢索的方法其基本出發點是統計提取三維模 型面片之間的夾角和距離特徵對，並利用多維核密度估計方法生成特徵的聯合分布函數， 並利用分布函數的相似性度量模型的相似性，實現三維模型的比較和檢索。下面結合附圖對本發明做更加詳細的解釋如圖1所示。圖1中的步驟1是初始動作。步驟2輸入一個三維模型文件，該個三維模型文件包含η個三角形面片。步驟3開始遍歷模型的每個三角面片，對所有面積大於面積閾值tha,ea的面片在步 驟4中做處理。處理過程如圖2所示，取該面片的最長邊edgei，連接該邊的中點和所對的 頂點vertex，新生成的邊把原三角面片分為2個面積相等的小面片。遍歷一遍後若所有新 生成的面片的面積都小於面積閾值th_a，則轉到步驟5，否則轉到步驟3再次遍歷。經過以 上處理。可以避免同一個三維模型中各個面片面積相差過大的情況，從而有利於之後的對 特徵的分布估計。圖3是一個原模型及用上述算法對其進行網格細分的例子，可以看出，細 分前該馬模型身體部分的面片明顯大於其它部分，細分後該問題得到很大程度的解決。步驟5和步驟6都是對模型做歸一化處理使之後的比較和檢索不受模型本身位置 和大小的影響。其中步驟5為平移模型使其質心與坐標原點重合。步驟6中利用公式
計算出模型的縮放因子並按
該值對模型進行縮放歸一化。歸一化的結果是把模型各個頂點到模型質心距離的方差歸 一，使模型在頂點坐標方差的意義下尺度統一。步驟7，提取歸一化模型的特徵，如圖4所示，對於有η個三角形面片的模型中的每 對面片i和j，提取它們法向夾角的餘弦值θ υ和沿模型表面的測地距離Ly，，的計算公式如下
其中X(1 = i，Xm = j，Ix y的計算方法為如果面片tx與面片ty有公共邊，則lx,y為 從面片tx到該公共邊中點的距離與從面片ty到該公共邊中點的距離之和，否則lx,y為+⑴。 上式中的函數min指採用弗洛伊德最短路徑算法。因此，上式中的Li, J為沿三維模型表面 從面片、到面片、的所有路徑中的最小值。步驟8，對步驟7中得到的η (η_1) /2個特徵對Sranstaint = { | i e
, j e [i+l，n]}進行重採樣使得特徵對的數量降到η。實現方式是對步驟7中的特徵對進行合併，算法如下a)按θ i, j值的升序對S。。nstaint的元素排序；b)均勻地劃分Sranstraint成μψ 個子集，即使每個子集中特徵對的數量相等；c)對於b)中的每個子集，按Ly值的升序對裡面的元素排序；
d)均勻地劃分C)中的每個子集，使每個子集被劃分成1個更小的子集bink(k =1. . η)；e)對於每個子集bink，利用式
生成η個新的特
徵對，完成重採樣過程。圖5是以上重採樣過程的示意圖，圖中每個點代表一定數量的特徵對，每個柵格 代表一個重採樣後的輸出特徵對。步驟9利用上一步重採樣後的特徵對進行多維核密度估計 其中(Xi，Yi)為步驟(3)中獲得的重採樣樣本，hx和hy為核密度估計中的平滑參 數。步驟10是比較和檢索，令p(i)(X)為候選模型的特徵分布函數，q(x)為輸入模型的 特徵分布函數，根據KL距離的理論以及本問題中特徵樣本的離散性，用於本發明實施例的 距離計算公式為 其中X為輸入模型，其特徵對為t1;t2，…，tm。這樣，第i個分布函數p(i)對應的模型即為檢索得到的結果。圖6給出了本發明方法與現有其它5種典型的三維模型檢索方法性能比較結果， 其中Kernel為本發明方法，SFHM、LFD、SPRH、Ankerst, D2為現有三維模型檢索代表性算 法；此外，橫坐標為三維模型召回率Recal 1，其定義為檢索出的相關結果條數/所有相關結 果總數；縱坐標為檢索精度Precision，其定義是檢索出的正確結果條數/檢索出的結果總 數。可以看出，本發明方法對應曲線反映的檢索性能明顯優於D2、Ankerst，與SPRH、SFHM 接近。本發明提供了一種基於核密度估計的三維模型比較和檢索方法的思路及方法，具 體實現該技術方案的方法和途徑很多，以上所述僅是本發明的優選實施方式，應當指出，對 於本技術領域的普通技術人員來說，在不脫離本發明原理的前提下，還可以做出若干改進 和潤飾，這些改進和潤飾也應視為本發明的保護範圍。本實施例中未明確的各組成部分均 可用現有技術加以實現。
權利要求
一種基於核密度估計的三維模型比較和檢索方法，其特徵在於，在讀取一個包含n個三角形面片的三維模型後，包括以下步驟步驟一，三維模型坐標數據的歸一化，包括網格細分、三維模型平移歸一化以及三維模型縮放歸一化；步驟二，三維模型特徵的提取對n個面片的三維模型中的每對面片i和面片j，提取法向夾角的餘弦值θi，j和沿三維模型表面的測地距離Li，j，形成n(n-1)/2個特徵對Sconstraint，Sconstraint＝{|i∈
，j∈[i+1，n]}；步驟三，特徵的重採樣合併相鄰的特徵對，使特徵對的數量從n(n-1)/2降到n；步驟四，核密度估計進行多維核密度估計，生成三維模型的特徵分布函數；步驟五，三維模型比較使用KL距離比較各個三維模型對應特徵分布函數的相似度，實現三維模型的比較和檢索。
2.根據權利要求1所述的一種基於核密度估計的三維模型比較和檢索方法，其特徵在 於，步驟一中，所述網格細分包括以下步驟對於每個三維模型，設定一個面積閾值th_a ；遍歷三維模型中的每個三角面片，如果該面片的面積大於面積閾值th ea，則在該面片 最長邊的中點到所對的頂點間連一條邊，此時該面片被分為2個小面片； 重複上一步驟直到所有面片的面積小於或者等於面積閾值tharea。
3.根據權利要求1所述的一種基於核密度估計的三維模型比較和檢索方法，其特徵在 於，步驟一中，所述三維模型平移歸一化是把三維模型的質心點平移到該三維模型所處坐 標系的坐標原點。
4.根據權利要求1所述的一種基於核密度估計的三維模型比較和檢索方法，其特徵 在於，步驟一中，所述三維模型縮放歸一化是把三維模型所有頂點坐標乘以一個縮放因子 factorscaling,使得模型各頂點到質心距離的方差為1，縮放因子/_。_ =1/ iU||Vipee_ld||2，其中Vi為模型頂點，η為頂點個數， Pcentroid為模型質心點，ViPcentroid為從三維模型頂點Vi到Peentraid所構成的向量。
5.根據權利要求4所述的一種基於核密度估計的三維模型比較和檢索方法，其特徵在 於，步驟二中，設Ityt1,為三維模型的面片集合，面片ti = {、，\2，\3}，其中、、 vi2、vi3為面片、三個頂點，碎為面片、的法向量，碎為面片、的法向量，則特徵對中的計算公式如下 其中 X0 = i, Xm = j ；lx, y的計算方法為如果面片tx與面片ty有公共邊，則lx, y為從面片tx到該公共邊中 點的距離與從面片ty到該公共邊中點的距離之和，否則lx,y為正無窮大；函數min採用弗 洛伊德最短路徑算法，Liij為沿三維模型表面從面片、到面片、的所有路徑中的最小值。
6.根據權利要求5所述的一種基於核密度估計的三維模型比較和檢索方法，其特徵在 於，步驟三中，所述合併相鄰的特徵對包括以下步驟按法向夾角的餘弦值θ i, j值的升序對特徵對S。。nsteaint的元素排序；將特徵對S。。nsteaint 劃分成個子集，使每個子集中特徵對的數量相等；對上一步驟所述每個子集，按Liij值 的升序對每個子集裡的元素排序；劃分上一步驟中的每個子集，使每個子集被劃分成^j+i 個更小的子集bink，其中k = 1 η中任意自然數；對於每個子集bink，利用 生成η個新的特徵對 ，其中么為在落第k個子集bin中的所有θ值的平均，厶為在落第k個子集bin中的 所有L值的平均。
7.根據權利要求6所述的一種基於核密度估計的三維模型比較和檢索方法，其特徵在 於，步驟四中，所述利用多維核密度估計生成三維模型的特徵分布函數的公式為 其中Upyi)為步驟三中合併後的特徵對，、和、為核密度估計中的平滑參數。
8.根據權利要求1所述的一種基於核密度估計的三維模型比較和檢索方法，其特徵在 於，步驟五中，令p(i)(X)為候選三維模型的特徵分布函數，q(x)為輸入三維模型的特徵分 布函數，所述KL距離計算公式為 ，其中X為輸入模型，其特徵對為t1;t2，…，tm
全文摘要
本發明提供了一種基於核密度估計的三維模型比較和檢索方法，包括以下步驟三維模型坐標數據的歸一化，包括網格細分、三維模型平移歸一化以及三維模型縮放歸一化；三維模型特徵的提取；特徵的重採樣合併相鄰的特徵對，使特徵對的數量從n(n-1)/2降到n；核密度估計進行多維核密度估計，生成三維模型的特徵分布函數；三維模型比較使用KL距離比較各個三維模型對應特徵分布函數的相似度，實現三維模型的比較和檢索。本發明的核密度估計對不同類型、不同形狀的三維模型的特徵分布建模具有較大的靈活性和通用性；多維核密度估計能利用豐富的多維形狀特徵，相比於簡單地對不同維度數據組合方法，能更好地刻畫模型的特徵。
文檔編號G06F17/30GK101882150SQ201010195709
公開日2010年11月10日 申請日期2010年6月9日 優先權日2010年6月9日
發明者王一鳴, 路通 申請人:南京大學