[發明專利]根據曲率對三維模型進行空域分割的方法

有效

• 申請號: 201510937455.0
• 申請日: 2015-12-15
• 公開（公告）號: CN105574867B
• 公開（公告）日: 2018-06-29
• 發明（設計）人: 楊柏林;張露紅;金劍秋;王勛
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06T19/00
• 分類號: G06T19/00
• 代理公司: 浙江杭州金通專利事務所有限公司 33100
• 代理人: 王佳健

本發明公開了一種根據曲率對三維模型進行空域分割的方法。本發明首先求出每個頂點在所有幀中的曲率期望。其次根據頂點曲率期望將頂點初始歸為塊。然后對上述的s塊根據拓撲進一步分塊，將s塊中拓撲連續的頂點歸為一塊并將頂點索引存入元胞矩陣B中，最后將上述進一步劃分的塊進行相鄰塊間的聚類。本發明用曲率衡量模型的運動劇烈程度，將頂點曲率期望相近且拓撲連續的點聚為一類。這樣便可使拓撲連續且具有相同的運動趨勢的頂點聚為一類，使得分割效果更優。

技術領域

本發明屬于三維動畫模型壓縮的多媒體技術領域，具體涉及一種根據曲率對三維模型進行空域分割的方法。

背景技術

隨著三維數據獲取手段的不斷豐富，計算機圖形學相關理論及技術的日臻成熟和網絡技術的迅猛發展，三維模型作為繼文本、音頻、圖像(圖形)和視頻之后的第五種多媒體數據類型在工業制造、產品展示、建筑設計、機器人技術、醫學、電子商務、教育培訓、軍事模擬仿真以及影視娛樂等諸多領域里扮演著日益重要的角色并發揮其獨有的優勢。

但日益精細完美的三維模型被廣泛應用的同時，其數據量和復雜度的激增給PC機圖形顯示卡、手持移動計算終端的圖形處理能力及網絡帶寬帶來了極大的挑戰，這無疑嚴重阻礙了該類型媒體的使用和傳播。要解決這一問題，僅僅依靠提高處理器的處理速度和能力、增加存儲器容量和網絡帶寬等硬件方面的措施是不現實的，必須還要采取一些相應的算法來減少三維模型數據，三維幾何數據壓縮技術便是其中一種行之有效的方法。

對于客戶端而言，所需的三維模型存儲數據越少、重構誤差越小越好。當然前人也研究了一些方法，對于聚類來說，有效且最常用的是K-means聚類算法。但該算法存在這其固有的缺點，首先算法中k是事先給定的，該k值的選定是很難估計的，因為在大多數情況下，并不知道給定的數據集應該分成多少個類別才合適；其次該算法對初始值的選取依賴性極大，而且算法常陷入局部極小解，不同的初始值結果往往不同；最后該算法需要不斷地進行樣本分類調整，不斷地計算調整后的新聚類中心，因此當數據量非常大時，該算法的時間開銷也很大。

發明內容

本發明針對現有聚類技術在三維場景應用方面的不足，提供了一種根據曲率對三維模型進行空域分割的方法。

本發明解決其技術問題所采用的技術方案如下：

步驟一:求出每個頂點在所有幀中的曲率期望。

假設幀數為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塊，即將曲率期望相近的頂點分為一塊，將其索引存入矩陣A中，length(A)＝S,A{i}均為一列向量；

步驟三：對上述的S塊根據拓撲進一步分塊，將S塊中拓撲連續的頂點歸為一塊并將頂點索引存入元胞矩陣B中，length(B)＝S,具體如下：

假設n表示目前正在處理A{i}中拓撲連續的第n塊，初始n＝1，n的最終值表示本塊即B{i}中所含拓撲連續的塊數。

從A{i}中隨機選取一點t當作特殊點放入矩陣B{i}{n}中，根據拓撲信息將此塊即A{i}中與t拓撲連續的頂點取出繼續放入B{i}{n}中，然后從矩陣B{i}{n}中選取沒有被當作特殊點的頂點作為特殊點繼續從A{i}中找尋與特殊點拓撲連續的點加入到B{i}{n}中，直到任意從A{i}選取一個頂點都不能與B{i}{n}中的頂點拓撲連續為止。