[發明專利]一種基于Reeb圖描述的三維拓撲信息提取方法

有效

• 申請號: 201310290294.1
• 申請日: 2013-07-10
• 公開（公告）號: CN103400372B
• 公開（公告）日: 2016-10-19
• 發明（設計）人: 劉皓;郭立;王成彰
• 申請（專利權）人: 中國科學技術大學
• 主分類號: G06T7/00
• 分類號: G06T7/00
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 成金玉;賈玉忠

技術領域

本發明涉及計算機圖形學、圖形建模、形狀匹配領域，具體而言，本發明涉及一種基于Reeb圖描述的三維拓撲信息提取方法。

背景技術

隨著信息技術的進一步發展，信息處理的對象已經從簡單的二維模型發展到表達內容更加豐富充足的三維模型。三維幾何信息是通過計算機圖形學和圖像處理技術得到的，其是對現實世界的三維物體的原始數據的一種數學再現，并且較為規范，但是由于其多數是僅對原始模型的簡單再現，數據量殊為龐大，冗余信息繁多，不利于進一步應用，因而對三維模型的識別、形狀分析和應用、計算機動畫、三維模型的檢索等，都有較大的限制。

三維拓撲結構信息能準確而精煉的描述三維模型的形狀特性，其在模型的變形、簡化、曲面重建、形狀分析、模型匹配與檢索、壓縮傳輸和三維動畫等許多領域有廣泛的應用和重要的作用。隨著圖形學、圖像處理技術的發展，拓撲結構的描述方法及其提取算法越來越受到人們的重視。

目前，中軸線（骨架）法、Reeb圖法是描述三維模型的拓撲結構的主要方法。中軸線（骨架）法從三維模型的骨架角度來表達三維模型的拓撲結構特征。此類型方法在模型分辨率較高的條件下可以得到較好的提取效果，但是其缺點是對邊界噪聲敏感，對模型的分辨率要求較高，迭代計算復雜度高。

Reeb圖是另一種極為重要的三維拓撲信息描述方法。該方法通過將函數值相同且在同一連通分量上的點聚類來提取拓撲結構特征。Reeb圖的計算方法主要有：高度函數法，根據表面等高線生成Reeb圖，該方法函數定義簡單，計算方便，但是缺點是聯通關系計算復雜，所得的Reeb圖有時處于模型體外；特征點法,利用映射得到Morse函數，然后尋找關鍵點，最終確定Reeb圖，該方法存在連接計算困難，且所得的Reeb圖也有可能處于模型體外。

發明內容

本發明的目的旨在至少解決上述技術缺陷之一，特別是針對拓撲信息提取計算復雜度高、提取的拓撲結構不夠精確的問題，提出了一種基于Reeb圖描述的三維拓撲信息提取方法。

為實現上述目的，本發明提出了一種基于Reeb圖描述的三維拓撲信息提取方法，包括如下步驟：

步驟（1）、讀取目標的三維網格信息，建立網格頂點序列并存儲三角面關系；

步驟（2）、標定源點，利用Dijkstra算法計算網格頂點到源點的測地距離；

步驟（3）、利用測地距離構造Morse函數，將Morse函數歸一化并計算極值點和鞍點；

步驟（4）、利用網格模型的三角面關系，通過三角形簡化法提取得到初始Reeb圖；

步驟（5）、對初始Reeb圖進行濾波，去除冗余信息，得到最終的Reeb圖，完成對三維目標的拓撲信息提取。

其中，建立網格頂點序列并存儲三角面關系，包括建立網格的頂點、邊、三角面的數據結構：

a)、頂點數據結構

讀取網格文件的頂點信息，存儲頂點坐標，并建立頂點索引序列。

b)、邊數據結構

讀取網格文件的三角面信息，對三角形的每條邊，存儲相應頂點的索引，計算邊的歐式距離并存儲。

c)、面數據結構

讀取網格文件的三角面信息，存儲三個頂點的索引。

其中，標定源點，利用Dijkstra算法計算網格頂點到源點的測地距離，具體如下：

為了統一測地距離的可比性，首先需要建立虛擬的標準測地源點，該測地源點的選擇有最高點法、空間距離最遠法，根據模型特征的不同選取合適的源點標定方法，最高點法適合如直立的人體等豎直的模型，空間距離最遠點法適合橫臥的長條形模型。具體如下：

a)、最高點法

選擇三維模型網格的最高點作為基準源點，最高點選擇方法表示為：

V_selected＝max{v_n(y)|n＝1,2,...,N}

其中V_selected代表被選擇的源點，max{}為求最大值，v_n(y)表示第n個頂點的y坐標分量，N為三角形網格的頂點總數。

b)、空間距離最遠點法

選擇歐式空間距離最遠的兩點中一個作為源點的方法，表示為：

V_selected＝max{||v_i-v_j||²|i＝1,2,...,N;j＝1,2,...,N}