[發(fā)明專利]一種基于近鄰傳播聚類的非均勻點云簡化處理方法

無效

• 申請?zhí)枺?/td>: 201010191582.8
• 申請日: 2010-06-04
• 公開（公告）號: CN101853485A
• 公開（公告）日: 2010-10-06
• 發(fā)明（設(shè)計）人: 陳勝勇;李蘭蘭;管秋;劉盛;張建偉
• 申請（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號: G06T1/00
• 分類號: G06T1/00;G06T17/00
• 代理公司: 杭州天正專利事務(wù)所有限公司 33201
• 代理人: 王兵;王利強

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

本發(fā)明涉及計算機視覺、數(shù)據(jù)處理、計算機圖形學(xué)、數(shù)值計算方法和逆向工程領(lǐng)域，尤其是一種非均勻點云簡化處理方法。

背景技術(shù)

通過圖像匹配和掃描真實物體模型技術(shù)可以獲得大規(guī)模的采樣點即點云。點云通常包含大量的數(shù)據(jù)點并且能很好的表達物體的表面。但是大規(guī)模的點云給點的繪制以及編輯都帶來了很大的困難，另一方面，三維模型的表達通常并不需要如此多的點。為了更有效的表達和繪制三維點云模型，近年來提出的很多方法應(yīng)用于點云簡化。在初期對點云的研究中，多數(shù)研究是基于點的拓撲網(wǎng)格，有四種經(jīng)典簡化算法的概述見于Mark?Pauly馬克.波利的文章：M.Pauly，“EfficientSimplification?of?Point-Sampled?Surfaces”，IEEE?Visualization?2002Oct.27-Nov.，即馬克.波利點云曲面的有效簡化IEEE視覺2002.10；包括了一下四種：(1)頂點移除(2)頂點聚類(3)邊收縮(4)粒子仿真。這幾種算法都是基于點拓撲而需要耗費較多的內(nèi)存。于是近來很多研究的重點開始放在直接對點云進行簡化上。Boissonnat引入了一種逐步的由粗糙到精細的簡化方法，參照文獻：J.-D.Boissonnat?and?F.Cazals.“Coarse-to-fine?surface，simplificationwith?geometric?guarantees”.EUROGRAPHICS?01，Conf.Proc.，Manchester，UK，2001；即伯奈特?基于幾何方法的細化點云簡化歐洲圖形學(xué)大會英國2001。11。重采樣方法是通過一些定制的規(guī)則計算初始點云的子集，而聚類的含義是把數(shù)據(jù)集分割為子集并找到每一子集的代表點。大多數(shù)聚類算法都需要在初始數(shù)據(jù)集中隨機的選擇一些聚類中心，通常這些初始聚類中心的選擇會影響到最終選出的代表點的結(jié)果。仿射聚類算法的提出克服了這一缺陷，它的主要思想是初始把每一個點都作為初始的代表點，并在點對之間發(fā)送帶有點信息的消息，但是和其他聚類算法一樣不適合應(yīng)用于稠密的相似矩陣。

對點云簡化的研究主要以點云的網(wǎng)格拓撲結(jié)構(gòu)為基礎(chǔ)，根據(jù)拓撲網(wǎng)格的關(guān)系進行網(wǎng)格簡化以達到點簡化的目的，這種方法的缺陷是存儲大量的網(wǎng)格而需要較大的內(nèi)存。而現(xiàn)在的主流方法主要是直接對點云進行簡化。仿射聚類算法的主要優(yōu)點是能夠在點與點之間發(fā)送消息，并且擁有較快的處理速度，應(yīng)用領(lǐng)域較為廣泛，但是對于稠密的數(shù)據(jù)相似矩陣時需要較大的內(nèi)存。

在通過圖像匹配特征點重建后得到的點云中，由于特征點分布的不均勻，會導(dǎo)致最后得到的點云分布的不均勻，而在采用激光掃描獲取數(shù)據(jù)點云時，也會因為條件的限制而產(chǎn)生非均勻的點云，現(xiàn)有的點云簡化方法計算復(fù)雜、需要占用較大內(nèi)存、不能有效處理非均勻的點云。

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

為了克服已有的點云簡化的處理方法的計算復(fù)雜、需要占用較大內(nèi)存、不能有效處理非均勻的點云的不足，本發(fā)明提供一種簡化計算、減少占用的內(nèi)存容量、能有效簡化非均勻點云的基于近鄰傳播聚類的非均勻點云簡化處理方法。

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

一種基于近鄰傳播聚類的非均勻點云簡化處理方法，所述非均勻點云簡化處理方法包括以下步驟：

1)、首先對整體點云進行k近鄰計算，計算點云模型中每一個點的k個鄰近點，然后根據(jù)鄰近點來計算每一個點的曲率值和密度表示值，并將鄰近點的序列號和其曲率值密度值一一對應(yīng)；

2)、根據(jù)每一個點的密度信息以及曲率信息進行自適應(yīng)的均勻重采樣；

3)、進行近鄰傳播聚類簡化，設(shè)初始點云為D，輸出簡化后點云為FD。過程為：

3.1)：設(shè)定簡化目標點數(shù)目為閾值；

3.2)：對初始點云D采用均勻網(wǎng)格曲率適應(yīng)性采樣方法獲得其子點集SD；

3.3)：計算SD中點與點之間的相似度，得到相似度矩陣S，并通過索引獲得SD中點的u值；

3.4)：運用近鄰聚類算法，S和u作為AP算法輸入，計算點間的代表度矩陣和適選度矩陣；如果最終選出代表點數(shù)目小于閾值，D＝D-SD，則返回到步驟3.2)，每次選出的代表點標號加入到同一個矩陣中，直到達到目標值得到最終點集FD。