[發明專利]一種基于蟻群優化的網格分割方法

有效

• 申請號: 201611247939.3
• 申請日: 2016-12-29
• 公開（公告）號: CN106650916B
• 公開（公告）日: 2019-02-01
• 發明（設計）人: 張耀楠;周微微;楊本強;周升
• 申請（專利權）人: 西安思源學院
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 北京世譽鑫誠專利代理事務所(普通合伙) 11368
• 代理人: 仲伯煊

本發明屬于圖形學和幾何數字處理技術領域，具體涉及一種基于蟻群優化的網格分割方法。一種基于蟻群優化的網格分割方法，包括以下步驟：(1)輸入待分割三維網格數據和參數，然后進入步驟(2)；(2)計算網格屬性，然后進入步驟(3)；(3)數據預處理，然后進入步驟(4)；(4)在待分割網格中選擇種子點，然后進入步驟(5)；(5)進行網格標簽初始化，然后進入步驟(6)；(6)進行蟻群優化迭代直到滿足迭代標準，然后進入步驟(7)；(7)區域合并，然后進入步驟(8)；(8)輸出分割結果。

技術領域

本發明屬于圖形學和幾何數字處理技術領域，具體涉及一種基于蟻群優化的網格分割方法。

背景技術

近十多年來,三維數據捕獲設備及其技術的進步推動了計算機視覺、醫學成像、基于圖像建模等技術向縱深發展,產生了許多復雜的三維模型,使得基于網格模型(特別是三角網格模型)的幾何處理等相關技術成為近年來計算機輔助設計(CAD)和圖形學的重要研究熱點。

原始三維網格模型缺少足夠的結構特征和語義信息,對原始三維網格模型的理解成為許多幾何處理問題亟待解決的重要問題,網格分割通過按照一定的分割準則將原始三維模型分解為不同的部件或曲面片,有助于相關幾何處理問題(如曲面壓縮、網格重構、參數化、紋理映射、模型檢索)的有效解決,實際上正是來自紋理映射、參數化、網格動畫、網格變形等問題的需求使網格分割作為一個重要的幾何處理問題開始引起人們的重視。

在計算機視覺中,將模型分割為不同部分,有助于進行模型的特征識別,例如將人臉三維模型通過分割識別出臉頰、鼻子、眼睛等。在網格參數化和紋理映射中,通過將模型分割為一系列平坦的區域,可以減少參數化和紋理映射的扭曲變形,提高參數化和紋理映射的質量。

在現有技術中，有些方法需要人工交互，有些需要方法較為復雜，有些方法需要復雜的數據結構。本發明方法較為簡單，不需要復雜的數據結構，可以全自動化，而且由于蟻群算法的特點，可以進行并行處理。

蟻群優化(ant colony optimization,ACO)的靈感來源于螞蟻搜索食物的過程。螞蟻們利用在走過的路徑上遺留和探測外激素(Stigmergy)這種間接的正反饋機制來尋找巢穴到食物源的最短路徑。這樣，一個普通的組合優化問題就被轉變成了一個約束最短路徑問題。蟻群優化最初是為研究旅行商問題(TSP)而被提出的，后來被使用到許多工程問題上。

發明內容

發明目的：本發明針對上述現有技術存在的問題做出改進，即本發明公開了一種基于蟻群優化的網格分割方法。在本發明中，將待分割網格的每個網格視為一個螞蟻，通過蟻群優化迭代將每個網格的標簽不斷更新。初始化時，所有的網格先賦予一個背景標簽。然后隨機產生種子點，每一個種子點賦予一個不同于背景標簽且唯一的標簽，而對于每一個種子點，其鄰域周圍的網格點賦予和種子點一樣的標簽。隨著蟻群優化的迭代，種子點的標簽向外擴散，而標簽更新是在滿足分割標準的條件下通過蟻群優化的更新機制進行，直到滿足迭代標準。蟻群優化完成后，進行區域合并，將較小的區域合并成較大區域，最終完成分割。

技術方案：一種基于蟻群優化的網格分割方法，包括以下步驟：

(1)輸入待分割三維網格數據和參數，然后進入步驟(2)；

(2)計算網格屬性，然后進入步驟(3)；

(3)數據預處理，然后進入步驟(4)；

(4)在待分割網格中選擇種子點，然后進入步驟(5)；

(5)進行網格標簽初始化，然后進入步驟(6)；

(6)進行蟻群優化迭代直到滿足迭代標準，然后進入步驟(7)；

(7)區域合并，然后進入步驟(8)；

(8)輸出分割結果。