[發明專利]一種基于Mean Shift的三維形狀自動分割方法

有效

• 申請號: 201210357811.8
• 申請日: 2012-09-24
• 公開（公告）號: CN102938161A
• 公開（公告）日: 2013-02-20
• 發明（設計）人: 劉貞報;謝彩麗;布樹輝
• 申請（專利權）人: 西北工業大學
• 主分類號: G06T15/00
• 分類號: G06T15/00
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 顧潮琪

技術領域

本發明涉及一種三維形狀的自動分割方法。?

背景技術

網格分割是幾何建模和計算機圖形學研究和應用的關鍵要素，輔助其進行參數化、紋理映射、形狀匹配、變形、多精度建模，壓縮以及動畫等操作。對形狀的理解和基于物體表示的語義信息的獲得依賴于表示這些物體和形狀的三維網格特征和結構的提取。將三維表面網格自動分割成功能部分是計算機圖形學的基礎問題，分割不僅能夠提供對應物體的語義信息，還能用來指導多種類型的網格處理算法。?

在目前國內外公開的文獻中，Marco?Attene,Bianca?Falcidieno?and?michelaSpagnuolo,“Hierarchical?mesh?segmentation?based?on?fitting?primitives”,TheVisual?Computer,2006中提出了基于Fitting?Primitives的分割算法，對三維形狀進行層次性的分割。該算法完全自動地生成一顆聚類二叉樹，每個節點代表的聚類都被一種基礎圖形如平面，柱面或球面所擬合。三維形狀中的每個三角形面片表示一個聚類，在反復迭代過程中將相鄰的聚類對融合，使得融合后的聚類對能夠更好的被基礎圖形所擬合且生成新的聚類。該算法自底向上遞歸的融合聚類，達到定義的分割數時終止。Shymon?Shlafman,Ayellet?Tal?and?Sagi?Katz，“Metamorphosis?ofPolyhedral?Surfaces?using?Decomposition’’,Computer?Graphics?Forum,2002中在對多邊形曲面進行變形時使用了與k-means聚類算法相似的解構方法。K-means在分割數k確定后，首先在物體表面選擇k個種子網格面片作為初始聚類中心，接著進行遞歸運算：1）將所有面片分配給離其最近的聚類中心；2）計算每個聚類的均值點，將初始聚類中心移動到均值點，將其當作新的聚類中心；直到聚類中心與其均值很接近時停止遞歸。K-means在特征空間進行聚類，采用歐幾里得距離作為相似度測量，使得聚類內特征點間的相似度最高，不同聚類的相似度最低。通過特征點與三維形狀多邊形網格一一對應的關系，將三維形狀分割為有意義的功能部分。?

但上述兩種三維形狀的分割方法有幾點不足：?

基于Fitting?Primitives的三維網格物體分割方法只適合三維CAD模型，分割個數需事先定義，由于算法使用平面、曲面等基礎圖形對三維形狀進行擬合，其擬合誤?差較大，分割效果不好。?

基于k-means的分割方法需要人為定義分割個數，對多個三維形狀進行分割時，需要依次設置分割個數，自動化程度低，另外，分割精度低。?

發明內容

為了克服現有技術自動化性能差、適用范圍小、分割精度低的不足，本發明提供一種基于mean?shift的三維形狀自動分割方法，該分割方法可以對通用物體的三維模型以及CAD模型進行自動分割。首先，為了獲取三維形狀的局部屬性特征和幾何位置特征，分別計算三維形狀中每個網格面片的shape?diameter值和中心坐標，構成shapediameter和幾何坐標組合的四維特征空間。接著，使用mean?shift算法在四維組合特征空間進行約束聚類，通過特征點與網格面片的對應關系得到三維形狀的分割，分割部分數與聚類個數相等。本發明采用k最近鄰分類法對分割結果進行局部修正，然后通過可視化操作將抽象數據轉換為直觀的三維圖像，接著利用基準量度進行量化評價。本發明可以對三維形狀進行自動分割，且無需事先規定分割個數。?

本發明解決其技術問題所采用的技術方案包括以下步驟：?

（1）通過特征化頂點的距離獲取每個三維形狀網格的局部特征，根據三維形狀網格的頂點坐標獲取其網格的中心坐標，得到組合的四維特征空間；?

（2）采用Mean?shift算法在前述四維特征空間進行聚類計算，得到聚類數以及各聚類所包含的特征點；?

（3）采用K最近鄰分類技術對步驟（2）的聚類計算結果進行決策空間建模，局部修正分割結果；?

（4）采用可視化技術將局部修正后的分割結果根據聚類屬性標記顏色的方式進行著色處理，采用普林斯頓分割基準計算該分割方法在不同量度下的基準誤差，從而進行量化評價。?

本發明的有益效果是：?