基于网格的三维彩色点云分割算法

万 燕，谭 亮，龙文铮，唐洪泰

（1.东华大学 计算机科学与技术学院，上海 201620；2.第二军医大学 医学学院，上海 200433）

基于网格的三维彩色点云分割算法

万 燕1，谭 亮1，龙文铮1，唐洪泰2

（1.东华大学 计算机科学与技术学院，上海 201620；2.第二军医大学 医学学院，上海 200433）

提出了一种基于HSV颜色空间的区域增长算法，利用统计方法得到区域增长的种子点和各点对应的分割阈值，使用网格信息寻找种子点的邻近点集，并综合考虑点云在HSV颜色空间中H分量的相近程度划分点云区域.试验表明，所提出的算法分割较精确，不容易产生过分割的情况.关键词：分割；HSV颜色空间；网格；区域增长

三维点云分割是计算机图形处理中广泛应用的关键技术，其利用图像的特征信息将图像划分为多个互不相交且更有意义的较小区域，方便机器分析，常用于目标检测、医学图像处理、机器视觉等领域.工业中通常采用激光扫描的方法获取被扫描物体的点云坐标数据，这使得大部分的分割算法往往关注点云的几何特征.一些扫描仪和建模方法则允许在获取物体三维坐标信息的同时，获取其相应的RGB彩色信息.相较几何特征而言，彩色信息的获得为分割提供了更准确的依据.

目前已有多种三维点云分割算法被提出，这些算法大多针对2.5维深度图像或不规则三角网格（TIN）模型，其往往考虑被扫描物体的几何特征，如法向量或曲率及其他特征，利用模型的局部形状特征差异划分点云.在工业中，一些物体呈现出规则的几何形状，即这些形状可用数学公式描述.由此，人们提出了一种将这种可量化的几何形状从点云中分割出来的算法.文献［1］用基于平面的分割算法检测扫描建筑物的平面屋顶.文献［2］用基于平面的分割算法，并利用霍夫变换重建出具有屋顶的三维模型.文献［3］提出了一种检测柱面的分割算法.为了得到一般的几何形状，有些算法通过检测几何边缘对点云进行分割.基于边缘的算法大致分为两部分，即根据特征值检测单个边缘点和将这些边缘点连成一条平滑的曲线作为边缘.这里的“边缘”是由那些特征值超出给定阈值的点云定义，点云特征包括法向量、坡度、曲率及其他特征.文献［4］将Robert算子扩展到三维空间，提出了三维边缘检测算法.边缘检测算法的优点是对区域对比较强烈的数据具有很好的分割效果，其缺点是检测出所有的边缘，这使得边缘与感兴趣区域的关系不明显，且分割容易受噪点的影响，常常需要混合其他算法使用.文献［5］提出了一种应用八叉树理论和图论进行点云的骨架提取和分割算法.文献［6］提出了一种基于Reeb图的三维肢体分割算法.

由于技术和成本的限制，基于几何特征的方法一度成为主流的三维分割算法.现在，人们可以在获取物体三维坐标信息的同时获取它的色彩信息.文献［7］提出一种基于RGB颜色信息的区域增长算法，利用 K Nearest Neighbors（KNN）算法搜索邻近点，并将RGB颜色空间中的欧氏距离作为颜色差异的标准.相较于几何特征，颜色能够提供更多用于分割的信息，从而分割效果相较基于几何特征的算法有了一定改进.但是KNN算法并未对种子点进行筛选，且利用其寻找的附近点不够准确.文献［8］将激光扫描仪和照相机结合，提出了一种快速点云分割的方法，该方法利用点云的法向量和RGB信息对点云进行分割，适合对三维场景进行粗分割.文献［9］提出了一种结合颜色和几何形状的分割方法，利用拟合平面提取三维模型的混合平面（组成平面），但该方法不适合对一般物体进行分割.

基于几何特征的分割算法一般需要设置较多的参数，且容易出现过分割或分割不完全，受噪点影响较大.基于RGB颜色空间的三维分割算法，由于R，G，B这3个分量存在较强的相关性，且分布不均匀性，导致在分割时不能很好地判断点云间颜色的差异，容易受到光线的影响.为了减少这种干扰，本文将颜色空间转换到 HSV（H（色度）、S（饱和度）、V（亮度））颜色空间中.扫描获得的点云通常是不规则的，这导致二维中一些成熟的分割算法很难应用于三维点云的分割.由于不能像在二维图片中根据下标直接找到邻域点，在三维中往往采用KNN或Fixed Distance Neighbors（FDN）的邻域搜索算法，这使得算法本身忽略了物体的形状特征，容易导致分割不理想.为了更好地利用点云的结构信息，本文对点云进行网格重建，结合点云的色彩信息和形状特征对点云进行分割.

1 基于网格的区域增长算法

区域增长算法由文献［10］首先提出，并最初应用于二维图像处理.其主要思想是从像素中选取特定像素点作为种子点，在该种子点的附近点中寻找与其某种特征相似的点，并标记为同一类，再从新标记的点中选取新的种子点继续扩散，直到找不到满足条件的种子点为止.区域增长算法的关键是分割依据的确定、种子点的选取和相似点的度量或评价.从点云中获得的信息越多，理论上分割效果越好.基于彩色的分割算法往往优于基于几何特征的分割算法.

三维区域增长算法的流程如图1所示.本文在搜索邻近点的方法、种子点的选取和阈值选取方面对算法进行了改进，将点云在HSV颜色空间中H值的相近程度和点在网格上的相关性作为分割依据.

图1 三维区域增长算法流程Fig.1 Flowchart of 3Dregion growing segmentation algorithm

1.1 HSV颜色空间

颜色空间有很多种，常用的RGB颜色空间一般用于机器显示，是一种非均匀的颜色空间，并且3个分量之间存在较强的关联，因此，在RGB颜色空间中不容易找到评价点间的颜色差异标准.HSV颜色空间由Smith A R在1978年提出.HSV符合人类的观察，是一种分布较均匀的颜色空间.由于扫描仪获取物体彩色信息时不可避免地受环境和光照的影响，重建后的模型带有一定失真，为了减少这种影响，本文只采用H分量作为颜色差异评价标准.令cmax为R，G，B这3个分量中最大值，cmin为最小值.由RGB获得H的转换式如式（1）所示.

1.2 邻近点搜索方法

分割是为了对物理空间和颜色空间中聚合的点云赋予特殊的标记，在进行区域增长时需要选择关联性最强的点来扩散.在三维中寻找点在物理空间中邻近的点一般有KNN和FDN两种常用方法.对于给定的点，KNN方法寻找与其欧氏距离最小的K个点作为其邻近点，而FDN方法寻找与其相距不超过指定阈值的点作为其邻近点.这两种方法都认为直线距离越近的两点在空间上关联性越强.三维物体表面凹凸不平的特性使得两点间的直线距离不一定等于其真实表面距离，因此，利用这两种算法寻找到的邻近点不一定是关联性最强的.

为了寻找真实的最近点集，本文利用网格上的关联信息作为是否邻近点的判断依据.区别于KNN和FDN方法，本文方法更加突出了点云在形状上的相关性.图2（a）为马的头部网格.针对位于耳朵部位的点P（P与N相连，M位于与P点相反的面），按照KNN或FDN算法寻找邻近点时会很容易穿透耳朵找到背面的点M，甚至可能认为点M与点P的关联性强于点N与点P的关联性.利用网格信息则可以避免这种错误，定义过且只过两点的线段长度为单位长度1，则如图2（b）中的点P与所有方形所标记的点的距离为1，与所有心形所标记的点的距离为2.

图2 邻近点Fig.2 Neighbor points

受重建算法的限制，根据网格信息寻找邻近点时会出现少量点找不到附近点的情况.对于这些点，本文采用KNN最近点思想，在根据点云数量合并区域阶段寻找它们的最近点，并将其合并到附近区域中.值得注意的是，寻找的邻近点与标记点间的距离不宜太大，否则容易出现散乱区域.

1.3 种子点的选取

种子点是一个区域中能够代表该区域某种特征的点，良好种子点的周围点H值变化较平缓，适合向各个方向扩散.若某点的H值与较多周围点的H值相差较大，则不宜作为种子点.根据HSV颜色空间中聚集的大部分点在物理空间中也是聚集的这一特点，一些算法统计H值的分布，将峰值点作为理想种子点.与其他区域的点相比，峰值点在物理空间中聚集的概率更大，因此更适合作为种子点.但这样得到的种子点有限，且峰值点中存在的一些边缘点和噪点也易被当作理想种子点，为此，本文先采用文献［11］的平滑函数对直方图进行平滑处理.处理前后H值直方图如图3所示.

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

为了得到更一般的种子点，本文将H值直方图中的区间平滑度ψ（变化平缓）和点的归属度η二者的联合概率作为良好种子点的评价标准.令f（x）为x区间内的点云数目，定义相邻区间的相对变化率ξ（x）为

ξ（x）越小，说明点云H值分布图中两邻近区间内点云数目相差越小.若某区间与其左右相邻区间的相对变化率较大，则认为该区间内的点不适合作为种子点.定义区间平滑度为

平滑度ψ（x）越大，则区间内的点越适合作为种子点.H值的区间平滑度考虑点云在颜色空间中的分布情况，归属度则是考虑点云在物理空间中的分布情况.将某个点与其附近点同属一个区域的概率定义为归属度，则

其中：Neighbors（p）表示与点p相邻的附近点集；T（p）为与点p颜色差异小于分割阈值的点集.归属度η（p）越大，则点p与附近点H值的差异越小，越适合作为种子点扩散.再定义优先级为

其中：p（H）为点p的H值；S为直方图统计步长，S不宜过小或过大，过小会导致分割过细，过大则忽略了噪点和边缘点的影响.优先级ω（p）越大，说明点在颜色空间和物理空间的聚集程度越大.建立种子点队列Qseed，将优先级大的区域内点优先插入Qseed中，进行区域增长时依次从初始队列中取出种子点进行扩散.这样得到的种子点队列，先取出的点总比后面的点更适合作为种子点.

种子点扩散时，容易出现如图4（a）所示的散乱区域，即区域非闭合，区域内部出现其他区域的点.这种区域不是所期望的，且很难通过颜色差异和区域大小控制将其合并到附近区域中.因此，在种子点扩散时需要对新种子进行必要的筛选，可以通过设定归属度阈值实现，若某点的归属度小于该值，则该点不作为种子点继续扩散.图4（b）是筛选种子点后的分割效果，可以看出这些被筛选掉的新种子点绝大部分是边缘点和噪点.筛选种子点可以有效地控制种子的扩散，防止过分割.

图4 区域增长后效果Fig.4 Result after region growing

1.4 扩散阈值的选取

在进行种子点扩散时，需要指定一个扩散阈值.从H值直方图可以看出，每个区域周围的H值变化程度不一样，即目标区域之间的颜色差异是不同的，因此，采用固定阈值对点云进行分割时容易出现过分割或分割不完全的情况.

理想区域是在物理空间和颜色空间中都聚集的点云.区域增长算法考虑了物理上的邻近关系，因此，将H值直方图中变化较平缓的相邻区间作为一个分割区域是合理的，这样可以根据H值直方图的变化情况得到每个点的精确分割阈值.理想区域内的点（除了噪点）只可能分布在这几个区间内.

分割的过程也可以看作是寻找边缘的过程.边缘点的数目相对其相邻区域较少，颜色上相近.因此，若某个区间与相邻区间的相对变化率ξ小于一定阈值TQ，则认为这两个区间属于同一区域；若相对变化率ξ大于TQ，则可能找到区域边缘或噪点，不归为同一区域.如，对于直方图中的x区间，分别向左右邻域搜索直到找到相对变化率ξ大于TQ的横坐标a和b为止，那么该区间内对应点的分割区间为（a，b）.

1.5 区域合并

变阈值的分割算法使得区域内的H值分布较窄，容易产生过分割的情况，需要对这些过分割的区域进行合并.同时三维扫描及建模过程中容易产生噪点，这些点也需要通过一定规则合并到周围区域中.由于限制了种子点的扩散，因此噪点形成的区域较小，可以通过限制区域大小将其合并到周围区域中.

在合并前，需要寻找在物理空间上的相邻区域，这可以通过寻找区域内点的附近点得到.遍历一个区域内的所有点，若该点与其附近点不属于同一区域，则附近点所在区域为附近区域.合并时考虑两邻域内点云H均值，若两相邻区域内H均值满足

则合并这两个区域.其中Rih和Rjh分别表示区域i和j的H均值；TR为阈值.重复以上过程直到不再有区域合并.为了减少噪点的影响，将点数小于阈值N的区域合并到邻近区域中.

2 试验结果与分析

图5（a）为利用微软的Kinect扫描所得的一粘有扑克牌的长方形纸板.从图5（a）可以看出，扫描得到的模型与真实物体对比有一定的失真，扑克牌的边缘比较模糊，即产生了一定的渐变.采用基于RGB的分割方法对模型进行分割，其分割效果如图5（b）所示.从图5（b）可以看出，由于RGB对于这种渐变不敏感，导致分割出的扑克牌边缘过于粗糙，分割效果与人眼的观测有较大误差.图5（c）为采用本文算法得到的分割效果图，可以看出，采用本文算法分割后扑克牌的边缘较规整，模型最终被分割成4个不同区域，与人眼观察相符，分割较理想.

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

图6（a）为一人体彩色3维模型，有221 582个点和375 299个面片.图6（b）为应用文献［7］算法的分割效果.可以看出，应用文献［7］算法进行分割后，出现了过分割和分割不完全的现象，这说明文献［7］的分割算法对颜色变化判断不准确.图6（c）为采用本文算法的分割效果.其中，设定H值统计步长为1.8，附近点搜索距离为2，区域合并阈值为3，最小区域内点数为250，相对变化率为0.62，归属度为0（所有点都将作为种子点扩散）.由图6（c）可以看出，由于未筛选种子点，处理后的图出现了较多的散乱区域.试验证明，当归属度设为0.62时，能达到较好的分割效果，但此时若搜索距离增大到5，也会出现与图6（c）类似的结果.

图6 人体模型Fig.6 Human model

区域增长后的分割效果如图7（a）所示，其中归属度为0.62，搜索距离为2.从图7（a）可以看出，经区域增长后的分割较细，目标区域基本被分割出来，同时有效地控制了散乱区域的出现，如眼部眉毛和眼睛被成功分为4个部分，但分割后存在较多点云数目很小的区域，分割后的区域总数为4 642个.将点数小于阈值N的区域合并到附近区域后的分割效果如图7（b）所示，合并后的区域总数为24个.

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

3 结 语

本文提出了一种基于网格的彩色分割算法，通过统计直方图方法得到初始种子点队列和分割阈值.在区域扩散时根据网格信息寻找关联点，并在HSV颜色空间中比较点的H值.利用区域增长算法对扫描模型进行粗分割，并通过相似区域合并得到分割结果.试验证明，应用本文算法可以取得较好的分割效果，但是本文依据网格信息寻找附近点，因此提出的分割算法受限于网格重建算法.

参 考 文 献

［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，FOIX 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）；长海医院“1255”学科建设计划课题资助项目（CH125510211）

万 燕（1970—），女，湖北黄冈人，副教授，博士，研究方向为图像处理与模式识别.E－mail：winniewan＠dhu.edu.cn