用於產生模型的形狀描述符的方法和裝置製造方法

2023-04-22 16:08:26

用於產生模型的形狀描述符的方法和裝置製造方法
【專利摘要】本發明提出了一種用於產生n維矢量作為模型的形狀描述符的方法以及相應的裝置和形狀描述符。所述方法包括：確定所述矢量的類型元以描述所述模型的基本外形；並計算所述矢量的n-1個度量元，每個所述度量元表示所述模型的所有特徵落在根據所述類型元劃分的n-1層其中之一的百分比。
【專利說明】用於產生模型的形狀描述符的方法和裝置

【技術領域】
[0001] 本發明總體上涉及計算機圖形學。具體而言，本發明涉及用於產生模型的形狀描 述符的方法和裝置。

【背景技術】
[0002] 3D形狀描述符通常是用於定義整個3D模型或該3D模型的某些部分的特徵的η維 矢量，其是計算機圖形學技術中的基本工具之一。3D形狀描述符廣泛地應用於許多3D模型 處理任務中，例如檢索、對稱性發現和建模。
[0003] MITRA，N. J.、⑶IBAS，L. J.和 PAULY，Μ.在 2006 年的論文 "Partial and approximate symmetry detection for 3D geometry，',ACM Trans. Gr. 25, 3, 560. 568 中提 議利用在採樣點的曲率張量（curvature tensor)的比率作為該採樣點的形狀描述符。
[0004] 為了提高判別性能，提出了數種形狀描述符。下面的幾個文件討論了已知3D形狀 描述符的某些實例。
[0005] (1) 3D shape contexts，M. Kortgen、G.-J. Park, M. Novotni 和 R. Klein, "3D Shape Matching with 3D Shape Contexts，'，the 7th Central European Seminar on Computer Graphics, 2003.
[0006] (2) Spin images, A. E. Johnson和M. Herbert，"Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes，'，IEEE Trans, on ΡΑΜΙ, 21 (5), pp. 433 -449,1999.
[0007] (3) Shape distributions、R. Osada, T. Funkhouser、B. Chazelle 和 D. Dobkin， "Shape Distributions"，ACM Trans, on Graphics，21(4)，pp. 807 - 832, 2002.
[0008] 在上述文件（1)中描述的外形描述符將S. Belongie、J. Malik和J. Puzicha的論 文"Shape Matching and Object Recognition Using Shape Contexts，'，IEEE Trans, on PAMI，24 (4)，pp. 509 - 522, 2002中提出的2D形狀環境的自然擴展應用於3D形狀的檢索和 匹配，其被定義在參考點上，該參考點獲取相對於該點的剩餘點的分布。上述文件（2)所述 的旋轉圖像是表示為2D直方圖（histogram)的數據級形狀描述符。文件（1)和（2)所提 出的方法都是基於局部點採樣幾何學的統計，這對於各種形狀表示（例如網格、多邊形黏 體（polygon soup)和有向點雲（oriented point clouds))而言是合適的。
[0009] 上述文件（3)中描述的形狀分布是代表性全局形狀描述符，其中對象的籤名被 表示為從測量該對象的全局幾何性質的形狀函數採樣的形狀分布。該方法的難處在於 如何選擇判別形狀函數和如何開發有效的方法來對其進行採樣。在J. W. H. Tangelder、 R.C.Veltkamp 的論文"A Survey of Content Based 3D Shape Retrieval Methods"，Shape Modeling International，pp. 145 - 156, 2004中介紹了用於3D模型檢索的多種全局/局 部形狀描述符。
[0010] 但是，大部分現有用於計算3D形狀描述符的算法都是針對水密性 (watertight) 3D模型（即具有平滑表面和緻密頂點分布的3D模型）設計的。圖1示出了 非水密性3D模型的實例。上述的算法對於非水密性3D模型不適合，非水密性3D模型（例 如建築和機械CAD模型）具有尖銳特徵和稀疏頂點分布。某些應用（例如實時3D模型搜 索）需要用於計算3D形狀描述符的快速算法。
[0011] 因此，需要一種對於非水密性3D模型高效的用於產生3D模型的形狀描述符的方 法和裝置。


【發明內容】

[0012] 根據本發明的一個方面，提出了一種用於產生η維矢量作為模型的形狀描述符的 方法。所述方法包括：確定所述矢量的類型元以描述所述模型的基本外形；並計算所述矢 量的η-1個度量元，每個所述度量元表示所述模型的所有特徵落在根據所述類型元劃分的 η-1層其中之一的百分比。
[0013] 根據本發明的另一個方面，提出了一種用於產生η維矢量作為模型的形狀描述符 的裝置。所述裝置包括：確定所述矢量的類型元以描述所述模型的基本外形的裝置；和計 算所述矢量的η-1個度量元的裝置，每個所述度量元表示所述模型的所有特徵落在根據所 述類型元劃分的η-1層其中之一的百分比。
[0014] 根據本發明的另一個方面，提出了一種模型的形狀描述符。所述形狀描述符為η 維矢量，包括：類型元，用於描述所述模型的基本外形；所述矢量的η-1個度量元，每個所述 度量元表示所述模型的所有特徵落在根據所述類型元劃分的η-1層其中之一的百分比。
[0015] 可以理解，下述對本發明的詳細說明將介紹本發明的更多方面和優勢。

【專利附圖】

【附圖說明】
[0016] 附圖與用於解釋本發明原理的文字說明一起使本發明實施方式得到進一步的理 解，本發明不局限於所述實施方式。
[0017] 其中：
[0018] 圖1是非水密性3D模型實例的示意圖；
[0019] 圖2是根據類型元對3D模型的邊框進行劃分的示意圖；
[0020] 圖3是用於計算2D形狀的矢量度量元的過程的圖示；
[0021] 圖4是採用根據本發明實施方式計算的3D形狀描述符構建3D模型的方法的流程 圖；和
[0022] 圖5是採用根據本發明實施方式計算的3D形狀描述符在輸入多分量3D模型的互 連分量中發現重複結構的方法的流程圖。

【具體實施方式】
[0023] 下面將結合附圖對本發明的實施方式進行詳細說明。在下述說明中，出於簡潔之 目的，對已知功能和結構不再進行詳細說明。
[0024] 根據本發明的一個實施方式，提供了一種具有低複雜性的用於產生3D模型的形 狀描述符的方法，該方法魯棒性較好並且能夠有效處理非水密性的3D模型。本發明的該實 施方式可以用於3D建模和對稱性發現網格簡化，其中在輸入網格上檢測到的多尺寸等級 重複結構可以用不同等級的細節來保留。
[0025] 在本發明的實施方式中，產生η維矢量作為形狀描述符來限定3D模型的外形。在 本發明的實施方式中，將對11維矢量進行描述。即，所述3D模型的形狀描述符的矢量含有 11個元。但是，本領域普通技術人員可以理解，上述η可以是任何整數。具有較大維度的矢 量對於形狀定義而言將具有更好的精度。
[0026] 根據本發明的實施方式，確定所述矢量的11個元中的一個元以描述所述3D模型 的基本形狀，該元可以稱為類型元。所述3D模型的基本形狀集在現有技術中是已知的，並 且可以根據發明的應用環境來設置。在一個實施例中，所述基本形狀集包括立方體、球體和 圓柱體。在另外一個實施例中，所述基本形狀集包括平面、開圓柱體（沒有底部和頂部的圓 柱體）、圓柱體、圓錐體和球體。
[0027] 所述類型元可以是整數，例如，0用於立方體，1用於球體，2用於圓柱體。或者0用 於平面，1用於開圓柱體，2用於圓柱體，3用於圓錐體，4用於球體。
[0028] 可以根據3D模型的協方差矩陣的三個特徵值計算所述3D模型的類型元。例如， 對於包括立方體、球體和圓柱體的基本形狀集，可以如下計算所述類型元：
[0029] 如果所述三個特徵值具有明顯差異，即第二最大值小於最大值的95%並且最小值 小於所述第二最大值的95%，將所述類型元設為0,即立方體。
[0030] 如果只有兩個值足夠接近，即一個值為另一個值的95%之內，將所述類型元設為 1，即圓柱體。
[0031] 對於其他情況，所述三個值足夠接近，將所述類型元設為2,即球體。
[0032] 接下來，確定所述矢量的另外10個元以表示所述3D模型的邊框上的全部特徵落 入根據所述類型元劃分的不同層上的百分比，每個所述元素稱為度量矢量元。所述3D模型 的特徵可以是3D模型的頂點、三角形或邊。
[0033] 所述度量矢量元可以是全浮點，其可以如下進行計算。
[0034] 下面將採用3D模型的邊框上的全部頂點詳細說明確定矢量的度量矢量元的實施 例。
[0035] 在模型規範化之後，根據所述類型元將3D模型的的邊框劃分為10層。圖2是根 據類型元對3D模型的邊框進行劃分的示意圖。
[0036] (i)對於立方體，用10個嵌入立方體劃分3D模型邊框。所有立方體具有相同中 心，即3D模型中心。立方體的長度是0.1、0. 2、"·、1，即其中一個包含在另外一個中。
[0037] (ii)對於圓柱體，用10個嵌入圓柱體劃分3D模型邊框。圓柱體的高度是0.1、 0· 2、…、1，下表面的半徑是 0· 05*sqrt (2)、0· l*sqrt (2)、0· 15*sqrt (2)、…、0· 5*sqrt (2)。 所有圓柱體具有相同中心，即3D模型中心。
[0038] (iii)對於球體，用10個嵌入球體劃分3D模型邊框。球體的半徑是 0· 05*sqrt (2)、0· l*sqrt (2)、0· 15*sqrt (2)、…、0· 5*sqrt (2)。所有球體具有相同中心，即 3D模型中心。
[0039] 在對3D模型邊框進行劃分之後，計算落入不同層的頂點，並計算初始度量矢量 元。通過規範化獲得最終的度量矢量元。
[0040] 圖3是用於計算2D形狀的矢量度量元的過程的圖示
[0041] 圖3示出了心形形狀。邊框為矩形。例如可以將該形狀的類型元設為1(用於矩 形）。假設5維矢量用於該2D形狀的形狀描述符，即需要4個度量矢量元，則通過如圖4所 示具有相同中心並且尺寸等級減小的4個矩形劃分所述邊框。如圖3所示，在所述心形形狀 的邊框上一共有19個頂點（由黑點表示）。有12(63.2% )、5 (26.3% )、2 (10.5% )、0個 頂點落入所述4個層。因此，用於此心形形狀的矢量形狀描述符是（1，0. 632,0. 263,0. 105， 0. 0)
[0042] 為了便於說明的目的，在2D形狀的情況下對度量矢量元的計算進行的說明。本領 域普通技術人員可以理解，對於3D模型的計算過程是類似的。
[0043] 兩個模型之間的相似性可以定量計算如下：
[0044] (1)如果兩個形狀元不相等，兩個3D模型之間的相似性為0
[0045] (2)如果形狀元相等，計算兩個度量矢量之間的歐幾裡德距離。假設所述距離為 d，則兩個3D模型之間的相似性是1/d。
[0046] 本發明的另一個實施方式提出了一種用於產生η維矢量作為模型的形狀描述符 的裝置。所述裝置包括：確定所述矢量的類型元以描述所述模型的基本外形的裝置；和計 算所述矢量的η-1個度量元的裝置，每個所述度量元表示所述模型的所有特徵落在根據所 述類型元劃分的η-1層其中之一的百分比。
[0047] 本發明的另一個實施方式提出了一種模型的形狀描述符。所述形狀描述符為η維 矢量，包括：類型元，用於描述所述模型的基本外形；所述矢量的η-1個度量元，每個所述度 量元表示所述模型的所有特徵落在根據所述類型元劃分的η-1層其中之一的百分比。
[0048] 下面，將結合3D建模和重複結構發現的應用場合對根據本發明實施方式的方法 計算的3D形狀描述符的應用進行說明。
[0049] 構建複雜3D模型複雜且耗時。基於現有3D模型的對稱性發現，可以置換某些圖 案而產生新的3D模型。但是，圖案置換非常複雜，因為其需要準備所述模型的全部重複性 部分以使得產生的模型更為合理。下面，對利用根據本發明實施方式計算出的3D形狀描述 符構建3D模型的方法進行說明。
[0050] 根據所述構建3D模型的方法，通過分析已知模型的結構，獲得所述3D模型的全部 重複結構，並且從資料庫中獲得合適的模型以置換某些圖案，以產生新的3D模型。
[0051] 圖4是採用根據本發明實施方式計算的3D形狀描述符構建3D模型的方法的流程 圖。
[0052] 在方框401，檢測原始模型的多尺寸等級重複結構（RS)。
[0053] 為了檢測原始模型的多尺寸等級重複結構，可以採用發明人蔡康穎等的國際專利 申請PCT/CN2010/000984 "檢測三維網格模型中重複結構的方法和設備"中描述的方法。 根據PCT/CN2010/000984,提出了一種用於檢測三維模型中的重複結構的高效多尺寸等級 方法，其中採用了減小的採樣步長的迭代均勻採樣。本發明使用利用遞減的採樣步長大小 的迭代均勻採樣的方法。使用相對較大的初始採樣步長對一個給定的三維網格模型進行均 勻採樣。然後，根據採樣點的曲率對採樣點進行聚類，然後確定屬於同一聚類的採樣點之間 的變換。這些就是所謂的候選變換。因此，只需要為那些其中兩個點具有相似的曲率的採 樣點對確定候選變換。這樣的聚類步驟不僅改善了算法的效率，而且也提高了算法的精度。 由之前計算的所有變換構建的變換空間包含比它在採樣步長大小更小時包含的噪聲元素 更少的噪聲元素。因此，隨後的聚類步驟會更容易發現所有的重複結構。如果模型包括若 乾重復結構，這種聚類的通常的結果是，會出現一個或多個不同的聚類。在下一步驟中，選 擇（最相關的）聚類，並採用對應的變換和採樣點對表示重複結構。最相關的聚類是那些 最重要和明顯的聚類。不屬於某個聚類的其他變換被捨棄。使用遞減的採樣步長迭代執行 此過程。每一次迭代都跳過重複部分，只處理模型的剩餘部分和在上一次迭代中檢測到的 代表性結構的代表。因此，同樣可以發現三維模型上的多尺寸等級的重複結構。當重複結 構的數目穩定時或者當達到預先定義的最小採樣步長大小時，迭代過程停止。另外，也可以 定義一個超時，測量該過程的運行時間，並在運行時間超過該超時時終止該過程。基於上述 說明，根據PCT/CN2010/000984的方法可以獲得輸入網格模型Μ的多尺寸等級重複結構的 檢測，其結果可以用於本發明的實施方式中。
[0054] 如圖4中方框401所示，檢測原始模型的多尺寸等級重複結構1、2、···、!!，用類似 對象置換局部重複部分以產生新模型，如圖4右部所示。
[0055] 在方框403,計算圖案i的矢量3D形狀描述符。首先，將圖案i的朝向與全局坐標 系統對齊，然後將其縮放（scale to)為單位立方體。接下來計算對齊的圖案i的矢量3D 外形描述符。
[0056] 在方框405,對3D資料庫進行搜索以尋找新圖案i。除了 3D模型之外，在所述3D 資料庫中也可以獲得3D模型的矢量3D形狀描述符。通過比較矢量3D形狀描述符，可以從 3D資料庫中找到與舊圖案最相近的新圖案。
[0057] 在方框407,計算新實例分量。首先將新圖案變換為具有由方框401計算出的對應 舊圖案相同位置、朝向和比例因子。隨後在變換和原始實例變換之後由新圖案計算新實例。
[0058] 圖5是採用根據本發明實施方式計算的3D形狀描述符在輸入多分量3D模型的互 連分量中發現重複結構的方法的流程圖。
[0059] 如圖5所示，在方框501對全部分量根據其主曲率進行聚類。本領域已知的聚類 方法可以用於此步驟。
[0060] 在方框503,對方框501得出的分量聚類內的分量根據其形狀描述符進一步進行 聚類。本領域已知的聚類方法可以用於此步驟。
[0061] 在方框505,對方框503得到的分量聚類進行結合。如果兩個分量聚類的代表分量 屬於相同的重複結構，則結合此兩個分量聚類。詳細的算法如下：
[0062] void Combine_Component_Cluster(void) { 計算全部代表分量對的距離； 按照遞增順序根據代表分量對的距離對其進行排序； 對於(每個排序的代表分量對）
[0063] { 對齊兩個代表分量； 計算兩個代表分量之間的距離； 如果(代表分量距離〈閾值） 結合相應的兩個分量聚類； 否則 中斷； } }
[0064] 兩個分量之間的距離如下計算.
[0065] Component_Distance = a*component_principle_curvature_ distance+b氺component-shape-descriptor-distance
[0066] 其中a和b是用戶設定常數。
[0067] 在方框507,發現每個分量聚類內的重複結構。將每個分量與其所屬分量聚類的代 表分量進行比較以判斷其是否屬於相同重複結構。詳細的算法如下：
[0068] oid Discover_Repetitive_Structure_Inside_Component_Cluster (void) { 對於（每個分量聚類Cluster」） { For (屬於Cluster」的每個分量c) { 對齊c和Cluster」的代表分量Repre_i; 計算c和Cluster」的代表分量之間的距離； 如果（分量距離< 閾值） 將Repre_i所屬重複結構加 c; 否則
[0069] 添加新重複結構並將新重複結構加 c; } } }
[0070] 在方框509,將方框507得到的重複結構結合。如果兩個分量聚類的代表分量相 似，則結合該兩個分量聚類。
[0071] 雖然結合3D模型的應用場合對本發明進行了說明，本領域普通技術人員可以理 解，本發明也可以應用於2D形狀。
【權利要求】
1. 一種用於產生η維矢量作為模型的形狀描述符的方法，包括： 確定所述矢量的類型元以描述所述模型的基本外形；並 計算所述矢量的η-1個度量元，每個所述度量元表示所述模型的所有特徵落在根據所 述類型元劃分的η-1層其中之一的百分比。
2. 根據權利要求1所述方法，其中所述模型是3D模型。
3. 根據權利要求2所述方法，其中所述特徵包括所述3D模型的頂點、三角形或邊。
4. 根據權利要求2所述的方法，其中所述3D模型的基本形狀包括立方體、球體和圓柱 體。
5. 根據權利要求2所述的方法，其中所述3D模型的基本形狀包括平面、開圓柱體、圓柱 體、圓錐體和球體。
6. 根據權利要求4所述的方法，其中根據所述3D模型的協方差矩陣的三個特徵值計算 所述類型元。
7. 根據權利要求1 一 6中任一所述的方法，其中所述類型元是整數。
8. 根據權利要求3所述的方法，其中用根據所述類型元確定的η-1個嵌入形狀劃分所 述3D模型的邊框。
9. 根據權利要求1所述的方法，其中所述度量元為全浮點。
10. 根據權利要求8所述的方法，其中通過所述3D模型的全部特徵落入所述η-1個層 其中之一上的百分比的規範化來計算所述度量元之一。
11. 一種用於產生η維矢量作為模型的形狀描述符的裝置，包括： 確定所述矢量的類型元以描述所述模型的基本外形的裝置；和 計算所述矢量的η-1個度量元的裝置，每個所述度量元表示所述模型的所有特徵落在 根據所述類型元劃分的η-1層其中之一的百分比。
12. -種模型的形狀描述符，其為η維矢量，包括： 類型元，用於描述所述模型的基本外形；和 所述矢量的η-1個度量元，每個所述度量元表示所述模型的所有特徵落在根據所述類 型元劃分的η-1層其中之一的百分比。
【文檔編號】G06K9/46GK104272324SQ201280072792
【公開日】2015年1月7日 申請日期:2012年5月22日 優先權日:2012年5月22日
【發明者】蔡康穎, 孟維亮, 羅濤 申請人:湯姆遜許可公司