[發明專利]用改進的k-means對三維模型進行空域分割的方法

有效

• 申請號: 201510975157.0
• 申請日: 2015-12-21
• 公開（公告）號: CN105590320B
• 公開（公告）日: 2018-07-03
• 發明（設計）人: 楊柏林;宋超;張露紅;張勛
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06T7/11
• 分類號: G06T7/11
• 代理公司: 浙江杭州金通專利事務所有限公司 33100
• 代理人: 王佳健

1.用改進的k-means對三維模型進行空域分割的方法，其特征在于該方法包括如下步驟：

步驟一：假設幀數為F,每一幀所含有的頂點數為N，F>0，N>0；將待求曲率的頂點在所有幀中的坐標連接成曲線，在某幀中的曲率即為該曲線上對應點的曲率；將求出的曲率保存至元胞矩陣k中，其中k＝cell(1,N),k{i}為一行向量，且length(k{i})＝F-2,1≤i≤N；求出每個頂點在所有幀中的曲率期望存入矩陣E中并畫出曲率期望圖，其中E為一行向量，且length(E)＝N：

步驟二:用光譜分析法對目標模型進行分割，假設分割的塊數為s，然后微調塊數s，具體是：

將重構前后的差值存入矩陣d中，d為1×N的矩陣，然后再對d做歸一化，歸一化后的結果保存至矩陣y中；將歸一化后的數據用不同深度的顏色標記在模型上；

步驟三:根據頂點曲率期望將頂點初始歸為s塊，即將曲率期望相近的頂點分為一塊，將其索引存入矩陣clusters中，length(clusters)＝S,clusters{i}均為一列向量；分別找出這s塊中所包含頂點離中心頂點最近的那個頂點放入聚類中心矩陣centers中，用表示，i＝1,…,S；

步驟四：分別計算其他頂點到這S個頂點的度量d，其具體計算公式如下：

此公式為求取頂點v_j到第i塊的度量，度量越小越應該聚為一類；頂點v_j到某一聚類中心c_i的距離所占權重為a，栓釋空間連續性；頂點v_j時域中的曲率期望與某一聚類中心c_i在此類中曲率期望之差的絕對值所占權重為1-a，代表模型的運動性；考慮到運動性與空間連續性兩個因素間的差距比較大，于是均對兩個因素做了歸一化處理；選取最小的d_cij，把頂點v_j歸到第i類，i＝1,…,S；

步驟五：更新每一簇的中心，即根據每一部分中所有頂點度量值的期望，找到此部分中與期望值最接近的頂點度量作為此部分新的聚類中心點；

步驟六：重復以上步驟四、五，直到閾值threshold小于某個設定的值為止；threshold定義為每塊中所有頂點度量的期望之和；閾值越小說明分割的塊中頂點間無論是歐幾里德距離還是運動趨勢都非常接近；

步驟七：把不連續的點提取出來根據拓撲將其歸到相應的塊中。