基于網(wǎng)格的三維彩色點(diǎn)云分割算法

萬(wàn) 燕，譚 亮，龍文錚，唐洪泰

（1.東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620；2.第二軍醫(yī)大學(xué) 醫(yī)學(xué)學(xué)院，上海 200433）

基于網(wǎng)格的三維彩色點(diǎn)云分割算法

萬(wàn) 燕1，譚 亮1，龍文錚1，唐洪泰2

（1.東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620；2.第二軍醫(yī)大學(xué) 醫(yī)學(xué)學(xué)院，上海 200433）

提出了一種基于HSV顏色空間的區(qū)域增長(zhǎng)算法，利用統(tǒng)計(jì)方法得到區(qū)域增長(zhǎng)的種子點(diǎn)和各點(diǎn)對(duì)應(yīng)的分割閾值，使用網(wǎng)格信息尋找種子點(diǎn)的鄰近點(diǎn)集，并綜合考慮點(diǎn)云在HSV顏色空間中H分量的相近程度劃分點(diǎn)云區(qū)域.試驗(yàn)表明，所提出的算法分割較精確，不容易產(chǎn)生過分割的情況.關(guān)鍵詞：分割；HSV顏色空間；網(wǎng)格；區(qū)域增長(zhǎng)

三維點(diǎn)云分割是計(jì)算機(jī)圖形處理中廣泛應(yīng)用的關(guān)鍵技術(shù)，其利用圖像的特征信息將圖像劃分為多個(gè)互不相交且更有意義的較小區(qū)域，方便機(jī)器分析，常用于目標(biāo)檢測(cè)、醫(yī)學(xué)圖像處理、機(jī)器視覺等領(lǐng)域.工業(yè)中通常采用激光掃描的方法獲取被掃描物體的點(diǎn)云坐標(biāo)數(shù)據(jù)，這使得大部分的分割算法往往關(guān)注點(diǎn)云的幾何特征.一些掃描儀和建模方法則允許在獲取物體三維坐標(biāo)信息的同時(shí)，獲取其相應(yīng)的RGB彩色信息.相較幾何特征而言，彩色信息的獲得為分割提供了更準(zhǔn)確的依據(jù).

目前已有多種三維點(diǎn)云分割算法被提出，這些算法大多針對(duì)2.5維深度圖像或不規(guī)則三角網(wǎng)格（TIN）模型，其往往考慮被掃描物體的幾何特征，如法向量或曲率及其他特征，利用模型的局部形狀特征差異劃分點(diǎn)云.在工業(yè)中，一些物體呈現(xiàn)出規(guī)則的幾何形狀，即這些形狀可用數(shù)學(xué)公式描述.由此，人們提出了一種將這種可量化的幾何形狀從點(diǎn)云中分割出來的算法.文獻(xiàn)［1］用基于平面的分割算法檢測(cè)掃描建筑物的平面屋頂.文獻(xiàn)［2］用基于平面的分割算法，并利用霍夫變換重建出具有屋頂?shù)娜S模型.文獻(xiàn)［3］提出了一種檢測(cè)柱面的分割算法.為了得到一般的幾何形狀，有些算法通過檢測(cè)幾何邊緣對(duì)點(diǎn)云進(jìn)行分割.基于邊緣的算法大致分為兩部分，即根據(jù)特征值檢測(cè)單個(gè)邊緣點(diǎn)和將這些邊緣點(diǎn)連成一條平滑的曲線作為邊緣.這里的“邊緣”是由那些特征值超出給定閾值的點(diǎn)云定義，點(diǎn)云特征包括法向量、坡度、曲率及其他特征.文獻(xiàn)［4］將Robert算子擴(kuò)展到三維空間，提出了三維邊緣檢測(cè)算法.邊緣檢測(cè)算法的優(yōu)點(diǎn)是對(duì)區(qū)域?qū)Ρ容^強(qiáng)烈的數(shù)據(jù)具有很好的分割效果，其缺點(diǎn)是檢測(cè)出所有的邊緣，這使得邊緣與感興趣區(qū)域的關(guān)系不明顯，且分割容易受噪點(diǎn)的影響，常常需要混合其他算法使用.文獻(xiàn)［5］提出了一種應(yīng)用八叉樹理論和圖論進(jìn)行點(diǎn)云的骨架提取和分割算法.文獻(xiàn)［6］提出了一種基于Reeb圖的三維肢體分割算法.

由于技術(shù)和成本的限制，基于幾何特征的方法一度成為主流的三維分割算法.現(xiàn)在，人們可以在獲取物體三維坐標(biāo)信息的同時(shí)獲取它的色彩信息.文獻(xiàn)［7］提出一種基于RGB顏色信息的區(qū)域增長(zhǎng)算法，利用 K Nearest Neighbors（KNN）算法搜索鄰近點(diǎn)，并將RGB顏色空間中的歐氏距離作為顏色差異的標(biāo)準(zhǔn).相較于幾何特征，顏色能夠提供更多用于分割的信息，從而分割效果相較基于幾何特征的算法有了一定改進(jìn).但是KNN算法并未對(duì)種子點(diǎn)進(jìn)行篩選，且利用其尋找的附近點(diǎn)不夠準(zhǔn)確.文獻(xiàn)［8］將激光掃描儀和照相機(jī)結(jié)合，提出了一種快速點(diǎn)云分割的方法，該方法利用點(diǎn)云的法向量和RGB信息對(duì)點(diǎn)云進(jìn)行分割，適合對(duì)三維場(chǎng)景進(jìn)行粗分割.文獻(xiàn)［9］提出了一種結(jié)合顏色和幾何形狀的分割方法，利用擬合平面提取三維模型的混合平面（組成平面），但該方法不適合對(duì)一般物體進(jìn)行分割.

基于幾何特征的分割算法一般需要設(shè)置較多的參數(shù)，且容易出現(xiàn)過分割或分割不完全，受噪點(diǎn)影響較大.基于RGB顏色空間的三維分割算法，由于R，G，B這3個(gè)分量存在較強(qiáng)的相關(guān)性，且分布不均勻性，導(dǎo)致在分割時(shí)不能很好地判斷點(diǎn)云間顏色的差異，容易受到光線的影響.為了減少這種干擾，本文將顏色空間轉(zhuǎn)換到 HSV（H（色度）、S（飽和度）、V（亮度））顏色空間中.掃描獲得的點(diǎn)云通常是不規(guī)則的，這導(dǎo)致二維中一些成熟的分割算法很難應(yīng)用于三維點(diǎn)云的分割.由于不能像在二維圖片中根據(jù)下標(biāo)直接找到鄰域點(diǎn)，在三維中往往采用KNN或Fixed Distance Neighbors（FDN）的鄰域搜索算法，這使得算法本身忽略了物體的形狀特征，容易導(dǎo)致分割不理想.為了更好地利用點(diǎn)云的結(jié)構(gòu)信息，本文對(duì)點(diǎn)云進(jìn)行網(wǎng)格重建，結(jié)合點(diǎn)云的色彩信息和形狀特征對(duì)點(diǎn)云進(jìn)行分割.

1 基于網(wǎng)格的區(qū)域增長(zhǎng)算法

區(qū)域增長(zhǎng)算法由文獻(xiàn)［10］首先提出，并最初應(yīng)用于二維圖像處理.其主要思想是從像素中選取特定像素點(diǎn)作為種子點(diǎn)，在該種子點(diǎn)的附近點(diǎn)中尋找與其某種特征相似的點(diǎn)，并標(biāo)記為同一類，再?gòu)男聵?biāo)記的點(diǎn)中選取新的種子點(diǎn)繼續(xù)擴(kuò)散，直到找不到滿足條件的種子點(diǎn)為止.區(qū)域增長(zhǎng)算法的關(guān)鍵是分割依據(jù)的確定、種子點(diǎn)的選取和相似點(diǎn)的度量或評(píng)價(jià).從點(diǎn)云中獲得的信息越多，理論上分割效果越好.基于彩色的分割算法往往優(yōu)于基于幾何特征的分割算法.

三維區(qū)域增長(zhǎng)算法的流程如圖1所示.本文在搜索鄰近點(diǎn)的方法、種子點(diǎn)的選取和閾值選取方面對(duì)算法進(jìn)行了改進(jìn)，將點(diǎn)云在HSV顏色空間中H值的相近程度和點(diǎn)在網(wǎng)格上的相關(guān)性作為分割依據(jù).

圖1 三維區(qū)域增長(zhǎng)算法流程Fig.1 Flowchart of 3Dregion growing segmentation algorithm

1.1 HSV顏色空間

顏色空間有很多種，常用的RGB顏色空間一般用于機(jī)器顯示，是一種非均勻的顏色空間，并且3個(gè)分量之間存在較強(qiáng)的關(guān)聯(lián)，因此，在RGB顏色空間中不容易找到評(píng)價(jià)點(diǎn)間的顏色差異標(biāo)準(zhǔn).HSV顏色空間由Smith A R在1978年提出.HSV符合人類的觀察，是一種分布較均勻的顏色空間.由于掃描儀獲取物體彩色信息時(shí)不可避免地受環(huán)境和光照的影響，重建后的模型帶有一定失真，為了減少這種影響，本文只采用H分量作為顏色差異評(píng)價(jià)標(biāo)準(zhǔn).令cmax為R，G，B這3個(gè)分量中最大值，cmin為最小值.由RGB獲得H的轉(zhuǎn)換式如式（1）所示.

1.2 鄰近點(diǎn)搜索方法

分割是為了對(duì)物理空間和顏色空間中聚合的點(diǎn)云賦予特殊的標(biāo)記，在進(jìn)行區(qū)域增長(zhǎng)時(shí)需要選擇關(guān)聯(lián)性最強(qiáng)的點(diǎn)來擴(kuò)散.在三維中尋找點(diǎn)在物理空間中鄰近的點(diǎn)一般有KNN和FDN兩種常用方法.對(duì)于給定的點(diǎn)，KNN方法尋找與其歐氏距離最小的K個(gè)點(diǎn)作為其鄰近點(diǎn)，而FDN方法尋找與其相距不超過指定閾值的點(diǎn)作為其鄰近點(diǎn).這兩種方法都認(rèn)為直線距離越近的兩點(diǎn)在空間上關(guān)聯(lián)性越強(qiáng).三維物體表面凹凸不平的特性使得兩點(diǎn)間的直線距離不一定等于其真實(shí)表面距離，因此，利用這兩種算法尋找到的鄰近點(diǎn)不一定是關(guān)聯(lián)性最強(qiáng)的.

為了尋找真實(shí)的最近點(diǎn)集，本文利用網(wǎng)格上的關(guān)聯(lián)信息作為是否鄰近點(diǎn)的判斷依據(jù).區(qū)別于KNN和FDN方法，本文方法更加突出了點(diǎn)云在形狀上的相關(guān)性.圖2（a）為馬的頭部網(wǎng)格.針對(duì)位于耳朵部位的點(diǎn)P（P與N相連，M位于與P點(diǎn)相反的面），按照KNN或FDN算法尋找鄰近點(diǎn)時(shí)會(huì)很容易穿透耳朵找到背面的點(diǎn)M，甚至可能認(rèn)為點(diǎn)M與點(diǎn)P的關(guān)聯(lián)性強(qiáng)于點(diǎn)N與點(diǎn)P的關(guān)聯(lián)性.利用網(wǎng)格信息則可以避免這種錯(cuò)誤，定義過且只過兩點(diǎn)的線段長(zhǎng)度為單位長(zhǎng)度1，則如圖2（b）中的點(diǎn)P與所有方形所標(biāo)記的點(diǎn)的距離為1，與所有心形所標(biāo)記的點(diǎn)的距離為2.

圖2 鄰近點(diǎn)Fig.2 Neighbor points

受重建算法的限制，根據(jù)網(wǎng)格信息尋找鄰近點(diǎn)時(shí)會(huì)出現(xiàn)少量點(diǎn)找不到附近點(diǎn)的情況.對(duì)于這些點(diǎn)，本文采用KNN最近點(diǎn)思想，在根據(jù)點(diǎn)云數(shù)量合并區(qū)域階段尋找它們的最近點(diǎn)，并將其合并到附近區(qū)域中.值得注意的是，尋找的鄰近點(diǎn)與標(biāo)記點(diǎn)間的距離不宜太大，否則容易出現(xiàn)散亂區(qū)域.

1.3 種子點(diǎn)的選取

種子點(diǎn)是一個(gè)區(qū)域中能夠代表該區(qū)域某種特征的點(diǎn)，良好種子點(diǎn)的周圍點(diǎn)H值變化較平緩，適合向各個(gè)方向擴(kuò)散.若某點(diǎn)的H值與較多周圍點(diǎn)的H值相差較大，則不宜作為種子點(diǎn).根據(jù)HSV顏色空間中聚集的大部分點(diǎn)在物理空間中也是聚集的這一特點(diǎn)，一些算法統(tǒng)計(jì)H值的分布，將峰值點(diǎn)作為理想種子點(diǎn).與其他區(qū)域的點(diǎn)相比，峰值點(diǎn)在物理空間中聚集的概率更大，因此更適合作為種子點(diǎn).但這樣得到的種子點(diǎn)有限，且峰值點(diǎn)中存在的一些邊緣點(diǎn)和噪點(diǎn)也易被當(dāng)作理想種子點(diǎn)，為此，本文先采用文獻(xiàn)［11］的平滑函數(shù)對(duì)直方圖進(jìn)行平滑處理.處理前后H值直方圖如圖3所示.

圖3 平滑前后H值直方圖Fig.3 Histogram of H value before and after smooth

為了得到更一般的種子點(diǎn)，本文將H值直方圖中的區(qū)間平滑度ψ（變化平緩）和點(diǎn)的歸屬度η二者的聯(lián)合概率作為良好種子點(diǎn)的評(píng)價(jià)標(biāo)準(zhǔn).令f（x）為x區(qū)間內(nèi)的點(diǎn)云數(shù)目，定義相鄰區(qū)間的相對(duì)變化率ξ（x）為

ξ（x）越小，說明點(diǎn)云H值分布圖中兩鄰近區(qū)間內(nèi)點(diǎn)云數(shù)目相差越小.若某區(qū)間與其左右相鄰區(qū)間的相對(duì)變化率較大，則認(rèn)為該區(qū)間內(nèi)的點(diǎn)不適合作為種子點(diǎn).定義區(qū)間平滑度為

平滑度ψ（x）越大，則區(qū)間內(nèi)的點(diǎn)越適合作為種子點(diǎn).H值的區(qū)間平滑度考慮點(diǎn)云在顏色空間中的分布情況，歸屬度則是考慮點(diǎn)云在物理空間中的分布情況.將某個(gè)點(diǎn)與其附近點(diǎn)同屬一個(gè)區(qū)域的概率定義為歸屬度，則

其中：Neighbors（p）表示與點(diǎn)p相鄰的附近點(diǎn)集；T（p）為與點(diǎn)p顏色差異小于分割閾值的點(diǎn)集.歸屬度η（p）越大，則點(diǎn)p與附近點(diǎn)H值的差異越小，越適合作為種子點(diǎn)擴(kuò)散.再定義優(yōu)先級(jí)為

其中：p（H）為點(diǎn)p的H值；S為直方圖統(tǒng)計(jì)步長(zhǎng)，S不宜過小或過大，過小會(huì)導(dǎo)致分割過細(xì)，過大則忽略了噪點(diǎn)和邊緣點(diǎn)的影響.優(yōu)先級(jí)ω（p）越大，說明點(diǎn)在顏色空間和物理空間的聚集程度越大.建立種子點(diǎn)隊(duì)列Qseed，將優(yōu)先級(jí)大的區(qū)域內(nèi)點(diǎn)優(yōu)先插入Qseed中，進(jìn)行區(qū)域增長(zhǎng)時(shí)依次從初始隊(duì)列中取出種子點(diǎn)進(jìn)行擴(kuò)散.這樣得到的種子點(diǎn)隊(duì)列，先取出的點(diǎn)總比后面的點(diǎn)更適合作為種子點(diǎn).

種子點(diǎn)擴(kuò)散時(shí)，容易出現(xiàn)如圖4（a）所示的散亂區(qū)域，即區(qū)域非閉合，區(qū)域內(nèi)部出現(xiàn)其他區(qū)域的點(diǎn).這種區(qū)域不是所期望的，且很難通過顏色差異和區(qū)域大小控制將其合并到附近區(qū)域中.因此，在種子點(diǎn)擴(kuò)散時(shí)需要對(duì)新種子進(jìn)行必要的篩選，可以通過設(shè)定歸屬度閾值實(shí)現(xiàn)，若某點(diǎn)的歸屬度小于該值，則該點(diǎn)不作為種子點(diǎn)繼續(xù)擴(kuò)散.圖4（b）是篩選種子點(diǎn)后的分割效果，可以看出這些被篩選掉的新種子點(diǎn)絕大部分是邊緣點(diǎn)和噪點(diǎn).篩選種子點(diǎn)可以有效地控制種子的擴(kuò)散，防止過分割.

圖4 區(qū)域增長(zhǎng)后效果Fig.4 Result after region growing

1.4 擴(kuò)散閾值的選取

在進(jìn)行種子點(diǎn)擴(kuò)散時(shí)，需要指定一個(gè)擴(kuò)散閾值.從H值直方圖可以看出，每個(gè)區(qū)域周圍的H值變化程度不一樣，即目標(biāo)區(qū)域之間的顏色差異是不同的，因此，采用固定閾值對(duì)點(diǎn)云進(jìn)行分割時(shí)容易出現(xiàn)過分割或分割不完全的情況.

理想?yún)^(qū)域是在物理空間和顏色空間中都聚集的點(diǎn)云.區(qū)域增長(zhǎng)算法考慮了物理上的鄰近關(guān)系，因此，將H值直方圖中變化較平緩的相鄰區(qū)間作為一個(gè)分割區(qū)域是合理的，這樣可以根據(jù)H值直方圖的變化情況得到每個(gè)點(diǎn)的精確分割閾值.理想?yún)^(qū)域內(nèi)的點(diǎn)（除了噪點(diǎn)）只可能分布在這幾個(gè)區(qū)間內(nèi).

分割的過程也可以看作是尋找邊緣的過程.邊緣點(diǎn)的數(shù)目相對(duì)其相鄰區(qū)域較少，顏色上相近.因此，若某個(gè)區(qū)間與相鄰區(qū)間的相對(duì)變化率ξ小于一定閾值TQ，則認(rèn)為這兩個(gè)區(qū)間屬于同一區(qū)域；若相對(duì)變化率ξ大于TQ，則可能找到區(qū)域邊緣或噪點(diǎn)，不歸為同一區(qū)域.如，對(duì)于直方圖中的x區(qū)間，分別向左右鄰域搜索直到找到相對(duì)變化率ξ大于TQ的橫坐標(biāo)a和b為止，那么該區(qū)間內(nèi)對(duì)應(yīng)點(diǎn)的分割區(qū)間為（a，b）.

1.5 區(qū)域合并

變閾值的分割算法使得區(qū)域內(nèi)的H值分布較窄，容易產(chǎn)生過分割的情況，需要對(duì)這些過分割的區(qū)域進(jìn)行合并.同時(shí)三維掃描及建模過程中容易產(chǎn)生噪點(diǎn)，這些點(diǎn)也需要通過一定規(guī)則合并到周圍區(qū)域中.由于限制了種子點(diǎn)的擴(kuò)散，因此噪點(diǎn)形成的區(qū)域較小，可以通過限制區(qū)域大小將其合并到周圍區(qū)域中.

在合并前，需要尋找在物理空間上的相鄰區(qū)域，這可以通過尋找區(qū)域內(nèi)點(diǎn)的附近點(diǎn)得到.遍歷一個(gè)區(qū)域內(nèi)的所有點(diǎn)，若該點(diǎn)與其附近點(diǎn)不屬于同一區(qū)域，則附近點(diǎn)所在區(qū)域?yàn)楦浇鼌^(qū)域.合并時(shí)考慮兩鄰域內(nèi)點(diǎn)云H均值，若兩相鄰區(qū)域內(nèi)H均值滿足

則合并這兩個(gè)區(qū)域.其中Rih和Rjh分別表示區(qū)域i和j的H均值；TR為閾值.重復(fù)以上過程直到不再有區(qū)域合并.為了減少噪點(diǎn)的影響，將點(diǎn)數(shù)小于閾值N的區(qū)域合并到鄰近區(qū)域中.

2 試驗(yàn)結(jié)果與分析

圖5（a）為利用微軟的Kinect掃描所得的一粘有撲克牌的長(zhǎng)方形紙板.從圖5（a）可以看出，掃描得到的模型與真實(shí)物體對(duì)比有一定的失真，撲克牌的邊緣比較模糊，即產(chǎn)生了一定的漸變.采用基于RGB的分割方法對(duì)模型進(jìn)行分割，其分割效果如圖5（b）所示.從圖5（b）可以看出，由于RGB對(duì)于這種漸變不敏感，導(dǎo)致分割出的撲克牌邊緣過于粗糙，分割效果與人眼的觀測(cè)有較大誤差.圖5（c）為采用本文算法得到的分割效果圖，可以看出，采用本文算法分割后撲克牌的邊緣較規(guī)整，模型最終被分割成4個(gè)不同區(qū)域，與人眼觀察相符，分割較理想.

圖5 紙板模型分割效果Fig.5 Result of segmentation on cardboard model

圖6（a）為一人體彩色3維模型，有221 582個(gè)點(diǎn)和375 299個(gè)面片.圖6（b）為應(yīng)用文獻(xiàn)［7］算法的分割效果.可以看出，應(yīng)用文獻(xiàn)［7］算法進(jìn)行分割后，出現(xiàn)了過分割和分割不完全的現(xiàn)象，這說明文獻(xiàn)［7］的分割算法對(duì)顏色變化判斷不準(zhǔn)確.圖6（c）為采用本文算法的分割效果.其中，設(shè)定H值統(tǒng)計(jì)步長(zhǎng)為1.8，附近點(diǎn)搜索距離為2，區(qū)域合并閾值為3，最小區(qū)域內(nèi)點(diǎn)數(shù)為250，相對(duì)變化率為0.62，歸屬度為0（所有點(diǎn)都將作為種子點(diǎn)擴(kuò)散）.由圖6（c）可以看出，由于未篩選種子點(diǎn)，處理后的圖出現(xiàn)了較多的散亂區(qū)域.試驗(yàn)證明，當(dāng)歸屬度設(shè)為0.62時(shí)，能達(dá)到較好的分割效果，但此時(shí)若搜索距離增大到5，也會(huì)出現(xiàn)與圖6（c）類似的結(jié)果.

圖6 人體模型Fig.6 Human model

區(qū)域增長(zhǎng)后的分割效果如圖7（a）所示，其中歸屬度為0.62，搜索距離為2.從圖7（a）可以看出，經(jīng)區(qū)域增長(zhǎng)后的分割較細(xì)，目標(biāo)區(qū)域基本被分割出來，同時(shí)有效地控制了散亂區(qū)域的出現(xiàn)，如眼部眉毛和眼睛被成功分為4個(gè)部分，但分割后存在較多點(diǎn)云數(shù)目很小的區(qū)域，分割后的區(qū)域總數(shù)為4 642個(gè).將點(diǎn)數(shù)小于閾值N的區(qū)域合并到附近區(qū)域后的分割效果如圖7（b）所示，合并后的區(qū)域總數(shù)為24個(gè).

圖7 人體模型分割效果Fig.7 Result of segmentation on human model

3 結(jié) 語(yǔ)

本文提出了一種基于網(wǎng)格的彩色分割算法，通過統(tǒng)計(jì)直方圖方法得到初始種子點(diǎn)隊(duì)列和分割閾值.在區(qū)域擴(kuò)散時(shí)根據(jù)網(wǎng)格信息尋找關(guān)聯(lián)點(diǎn)，并在HSV顏色空間中比較點(diǎn)的H值.利用區(qū)域增長(zhǎng)算法對(duì)掃描模型進(jìn)行粗分割，并通過相似區(qū)域合并得到分割結(jié)果.試驗(yàn)證明，應(yīng)用本文算法可以取得較好的分割效果，但是本文依據(jù)網(wǎng)格信息尋找附近點(diǎn)，因此提出的分割算法受限于網(wǎng)格重建算法.

參 考 文 獻(xiàn)

［1］HANS－GERD M， GEORGE V. Two algorithms for extracting building models form raw lasers altimetry data［J］.Journal of Photogrammetry and Remote Sensing，1999，54（2／3）：153－163.

［2］VOSSELMAN G， DIJKMAN S. 3Dbuilding model reconstruction from point clouds and ground plans［C］／／International Archives of the Photogrammetry， Remote Sensing and Spatial Information Sciences.2001：37－44.

［3］RABBANI T，VAN DEN HEUVEL F.Efficient hough transform for automatic detection of cylinders in point clouds［C］／／International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences.2005：60－65.

［4 ］LIU H K.Two－and three－dimensional boundary detection［J］.Computer Graphics and Image Processing，1977，6（2）：123－134.

［5 ］BUCKSCH A，VAN WAGENINGEN H A.Skeletonization and segmentation of point clouds using octrees and graph theory［C］／／International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences.2006：1－6.

［6］關(guān)華，郭立，李文.一種基于Reeb圖的3維肢體分割算法［J］.通信技術(shù)，2011，44（11）：63－65.

［7 ］ZHAN Q M，LIANG Y B，XIAO Y H.Color－based segmentation of point clouds［C］／／International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences.2009：248－252.

［8 ］STROM J，RICHARDSON A，OLSON E.Graph－based segmentation for colored 3Dlaser point clouds ［C］／／International Conference on Intelligent Robots and Systems.2010：2131－2136.

［9 ］DELLEN B，ALENYA G，F(xiàn)OIX S，et al.Segmenting color images into surface patches by exploiting sparse depth data［C］／／2011IEEE Workshop on Applications of Computer Vision（WACV）.2011：591－598.

［10］ADAMS R，BISCHOF L.Seeded region growing［C］／／IEEE Transactions on Pattern Analysis and Machine Intelligence.1994，16（6）：641－647.

［11］SURAL S，QIAN G，PRAMANIK S.Segmentation and histogram generation using the HSV color space for image retrieval［C］／／International Conference on Image Processing（ICIP）.2002：589－592.

A New Segmentation Algorithm for 3DColored Point Cloud Based on Grid

WANYan1，TANLiang1，LONGWen－zheng1，TANGHong－tai2
（1.College of Computer Science and Technology，Donghua University，Shanghai 201620，China；2.Medical College，Second Military Medical University，Shanghai 200433，China）

A new segmentation algorithm based on HSV color space and region growing method was presented.Through dimensional histogram statistics method，the seeds and region growing threshold were extracted.Also，the grid information to find points'neighbors was used，and the similarity of H field of HSV space was used to determine whether the two points belong to the same region.The experiments show that the presented algorithm gains more precise result and can reduce oversegmentation phenomena.

segmentation；HSV color space；grid；region growing

TP 391.41

A

1671－0444（2014）04－0481－05

3013－06－21

國(guó)家自然科學(xué)基金資助項(xiàng)目（81372057）；長(zhǎng)海醫(yī)院“1255”學(xué)科建設(shè)計(jì)劃課題資助項(xiàng)目（CH125510211）

萬(wàn) 燕（1970—），女，湖北黃岡人，副教授，博士，研究方向?yàn)閳D像處理與模式識(shí)別.E－mail：winniewan＠dhu.edu.cn