[發明專利]幾何圖案編碼方法和設備，以及幾何圖案解碼方法和設備

有效

• 申請號: 201080069356.0
• 申請日: 2010-09-30
• 公開（公告）號: CN103329169A
• 公開（公告）日: 2013-09-25
• 發明（設計）人: 蔡康穎;楊繼珩;滕軍;夏志進
• 申請（專利權）人: 湯姆遜許可公司
• 主分類號: G06T15/00
• 分類號: G06T15/00;G06T9/00
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 呂曉章

技術領域

本發明涉及對相似幾何圖案（如，多組件三維網格模型的若干組件）進行高效編碼。

背景技術

本節旨在向讀者介紹可能與下面描述和/或要求保護的本發明的各個方面相關的本技術領域的各個方面。這種討論被認為有助于向讀者提供背景信息以便更好地理解本發明的各個方面。因此，應該理解的是，應該從這個角度閱讀這些陳述，而不是當作對現有技術的認可。

在各種應用中使用最廣泛的3D模型是那些具有大量的較小到中等大小的相互連通的組件的模型，其中平均每個組件具有多達幾百個的多邊形。這種模型被稱為多連通或者多組件3D模型。它們在生物學、物理學、工程學和藝術等不同的領域發揮著重要的作用。這種模型可以用于例如機械CAD設計、建筑設計和化學工廠，在各種現實世界的應用中正越來越多地使用。

緊湊表示是緊湊存儲和高效傳輸的關鍵問題之一。3D模型通常用由坐標數組和面片數組（face?array）組成的“索引化面片集（indexed?face?set）”表示。坐標數組列出所有頂點的坐標，面片數組通過給它在坐標數組中的三個頂點編索引列出每個面片。索引面集不涉及壓縮。“三角形條帶”¹是一種廣泛使用的可以被大多數圖形卡很好地支持的3D模型的緊湊表示。三角形條帶方法嘗試將三維網格分割成若干的三角形長條帶，如圖l所示，然后對這些條帶進行編碼。在圖1中，頂點v₀，……，v₇定義一個三角形條帶，它是三維網格模型的一部分。

最著名的三維壓縮算法都提出了它們自己的三維模型緊湊表示以提升壓縮比。這些緊湊表示對具有密集的小三角形網格的光滑表面最為有效。然而，大型多連通3D模型具有大量有著較少數量的大三角形并通常具有任意連通性的連通組件。建筑和機械CAD模型通常具有許多使得這些方法更加不適用的非光滑表面。此外，大多數已知的方法對每個連通的組件分開進行處理。因此，這些三維模型表示在大型多組件三維模型上的表現不是很好。

近來已經提出一些專門設計用于大型多組件三維模型的緊湊表示。[CAI09VRST]²和[CAI09VRCAI]³提出了一種用于大型多組件三維模型緊湊表示方法，可以檢測出無論旋轉、平移和/或縮放情況下的重復實例。此外，在[SKU2008]⁴中描述了用于定義三維網格模型的表面細節的位移圖（displacement?map）。這些細節被稱為細微結構（mesostructure）（與定義物體形狀的宏觀結構相對），并包括提供紋理或燈光效果的高頻幾何細節。因此，它們相對較小，但仍然可見，如表面上的凸起。

發明內容

本發明人已經認識到上述得益于檢測出重復圖案的緊湊表示方法只能夠檢測出預定義變換類型（即旋轉、平移和縮放）下精確相等的重復圖案。在實際應用中，只有少量3D模型包含此類組件。

本發明正是基于認識到下述事實：大型多組件3D模型緊湊表示的效率可以通過檢測并表示其并不精確相等的組件之間的相似性而得到較大的提升。一般情況下，這些組件是幾何圖案（geometry?pattern）。

本發明的一個創新方面是使用位移圖基于單個基礎模型（single?base?model）對兩個或更多不同但相似的幾何圖案進行差分編碼。

根據本發明的一個方面，一種用于對多個幾何圖案進行編碼的方法包括下列步驟：檢測并聚類相似的幾何圖案；生成聚類代表表面（例如，通過求取所有聚類幾何圖案的平均）；為至少一個聚類幾何圖案生成位移圖；以及編碼共同表面和位移圖。可以在一個歸一化步驟之后確定幾何圖案的相似性。

根據本發明的一個方面，一種用于對多個（可以是一個或多個三維網格模型中連通的組件的）幾何圖案進行編碼的方法包括下列步驟：檢測相似的幾何圖案；將檢測出的相似的幾何圖案聚類到一個共同聚類；生成該共同聚類的聚類代表表面；為被聚類在所述聚類中的至少兩個幾何圖案生成若干單獨的位移圖，其中每個位移圖定義聚類代表表面的頂點和被聚類的幾何圖案的頂點之間的位移；以及通過對聚類代表表面進行編碼和對位移圖進行編碼來對多個幾何圖案進行編碼。對位移圖進行的編碼還可以包括縮放、位置、方向和/或復制信息。