[發(fā)明專利]用改進(jìn)的k-means對三維模型進(jìn)行空域分割的方法

有效

• 申請?zhí)枺?/td>: 201510975157.0
• 申請日: 2015-12-21
• 公開（公告）號: CN105590320B
• 公開（公告）日: 2018-07-03
• 發(fā)明（設(shè)計(jì)）人: 楊柏林;宋超;張露紅;張勛
• 申請（專利權(quán)）人: 浙江工商大學(xué)
• 主分類號: G06T7/11
• 分類號: G06T7/11
• 代理公司: 浙江杭州金通專利事務(wù)所有限公司 33100
• 代理人: 王佳健

本發(fā)明公開了一種用改進(jìn)的k?means對三維模型進(jìn)行空域分割的方法。本發(fā)明首先將待求曲率的頂點(diǎn)在所有幀中的坐標(biāo)連接成曲線并用光譜分析法對目標(biāo)模型進(jìn)行分割。其次根據(jù)頂點(diǎn)曲率期望將頂點(diǎn)初始?xì)w為塊，即將曲率期望相近的頂點(diǎn)分為一塊；分別計(jì)算其他頂點(diǎn)到這s個(gè)頂點(diǎn)的度量d。然后更新每一簇的中心，即根據(jù)每一部分中所有頂點(diǎn)度量值的期望，找到此部分中與期望值最接近的頂點(diǎn)度量作為此部分新的聚類中心點(diǎn)，最后重復(fù)直到閾值threshold小于某個(gè)設(shè)定的值為止。本發(fā)明用曲率表示模型的運(yùn)動劇烈程度，創(chuàng)新性地用歐幾里德距離與曲率期望的加權(quán)平均定義為聚類度量，這樣聚類結(jié)果不僅保證了空間連續(xù)性又保證了模型的運(yùn)動性。

技術(shù)領(lǐng)域

本發(fā)明屬于三維動畫模型壓縮的多媒體技術(shù)領(lǐng)域，具體涉及一種改進(jìn)的k-means空域分割方法。

背景技術(shù)

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

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

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

發(fā)明內(nèi)容

本發(fā)明針對現(xiàn)有空域分割技術(shù)在三維場景應(yīng)用方面的不足，提出了一種用改進(jìn)的k-means對三維模型進(jìn)行空域分割的方法。

本發(fā)明解決其技術(shù)問題所采用的技術(shù)方案如下：

本發(fā)明包括以下步驟：

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

步驟二:用光譜分析法對目標(biāo)模型進(jìn)行分割，假設(shè)分割的塊數(shù)為s，然后微調(diào)塊數(shù)s，具體是：

將重構(gòu)前后的差值存入矩陣d中，d為1×N的矩陣，然后再對d做歸一化，歸一化后的結(jié)果保存至矩陣y中。將歸一化后的數(shù)據(jù)用不同深度的顏色標(biāo)記在模型上。

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

步驟四：分別計(jì)算其他頂點(diǎn)到這S個(gè)頂點(diǎn)的度量d，其具體計(jì)算公式如下：