萬 燕，譚 亮，龍文錚，唐洪泰

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

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

萬 燕1，譚 亮1，龍文錚1，唐洪泰2

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

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

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

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

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

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

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

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

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

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

1.1 HSV顏色空間

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

1.2 鄰近點搜索方法

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

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

圖2 鄰近點Fig.2 Neighbor points

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

1.3 種子點的選取

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

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

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

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

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

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

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

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

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

1.4 擴散閾值的選取

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

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

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

1.5 區(qū)域合并

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

在合并前，需要尋找在物理空間上的相鄰區(qū)域，這可以通過尋找區(qū)域內點的附近點得到.遍歷一個區(qū)域內的所有點，若該點與其附近點不屬于同一區(qū)域，則附近點所在區(qū)域為附近區(qū)域.合并時考慮兩鄰域內點云H均值，若兩相鄰區(qū)域內H均值滿足

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

2 試驗結果與分析

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

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

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

圖6 人體模型Fig.6 Human model

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

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

3 結 語

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

參 考 文 獻

［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］關華，郭立，李文.一種基于Reeb圖的3維肢體分割算法［J］.通信技術，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

國家自然科學基金資助項目（81372057）；長海醫(yī)院“1255”學科建設計劃課題資助項目（CH125510211）

萬 燕（1970—），女，湖北黃岡人，副教授，博士，研究方向為圖像處理與模式識別.E－mail：winniewan＠dhu.edu.cn