基于最小割的彩色点云分割

姚砺+李瑶

摘要：提出一种基于最小割的彩色点云分割算法，首先找到彩色点云中每个点的临近点，然后与父点连接，再找到距离最近的2个块并连接，重复连接距离最小的2个块，直到只剩1个块，从而生成1张点云图。根据2点之间的欧氏距离和颜色空间距离设置2点连线的权值，当选择待分割点后根据设定的阈值大小和分割范围，查找被选点分割范围内的所有符合条件的点，然后通过区域生长算法对符合条件的点进行生长，进而得到颜色相近的三维连通区域。实验证明所提方法可行，可有效解决三维分割中连通性的问题。

关键词： 最小割； 彩色点云； 分割

中图分类号：TP391.41

文献标志码：A

文章编号：2095-2163（2017）05-0010-03

The segmentation method of colored point cloud based on mincut algorithm

YAO Li， LI Yao

（School of Computer Science and Technology， Donghua University， Shanghai 201620， China）

Abstract：

Most of the segmentation methods of point cloud are based on the twodimensional image processing which geometric information has been ignored This leads to nonconnected regions with similar color that would be easily divided in the same area The paper proposes a segmentation method based on mincut algorithm Firstly， generate a point cloud graph Then， choose the point which is going to be divided and set the threshold and the segmentation radius based on two points′ Euclidean distance and color space distance Secondly， find other points that in the range of designed radius and its′ color and geometry information is below the threshold Thirdly， use the region growing algorithm to find other points Experimental results demonstrate that this method can efficiently solve the connectivity problems in 3d segmentation

Keywords：mincut； colored point cloud； segmentation

作者简介：

收稿日期： 2017-08-30

0引言

随着三维扫描技术的发展，Kinect等手持式设备使得通过扫描设备获得人体三维点云变得越来越便捷。三维扫描在文物修复、人体烧伤、纹理映射、医学整形、地理测量、机器视觉等领域有着重要应用。

传统的测量方法有光学测量法、超声波法等[1-5]，但这些传统方法对设备要求高，而且价格昂贵，不方便操作。近年来，由于获取设备和计算机技术的发展，通过三维彩色扫描获取三维物体的颜色及点云信息模型越发便捷。基于三维彩色点云进行分割是点云处理的基础，但大部分点云分割算法是从二维图像分割移植而来，不考虑三维图像的几何信息，所以应用到点云分割时，造成了一些不连通的区域由于颜色相似也会被分割到同一区域的问题。而利用几何特点的分割算法大都是基于灰度模型，但如果希望分割出指定颜色的三维表面，特别是复杂颜色的三维表面，如烧伤区域，那么使用以上从二维移植来的算法解决不了连通性的问题，而只利用几何特征则解决不了鉴别颜色的问题。因此研究结合了二维颜色特征及三维连通性的特征，提出了基于最小割的彩色三维模型的分割算法。

1背景概述

Kinect v2 是微软第二代Kinect，搭载于微软最新一代游戏机Xbox one 上，用于感知3D 音频和图像，Kinect v2的ToF 处理器芯片是TSMC 013 1P5。MKinect v2如图1 所示，包含一个彩色相机、深度相机、红外光发射器。而延续2代的Kinect的深度效果对比则如图2所示。通过Kinect v2 可以获取场景的深度、彩色、红外图像等信息。

分割是把三维空间中的点划分成较小的、连续的子集过程。分割之后，得到具有相似属性的点。这些点的子集应该是“有意义的”，分割后应该得到一系列研究感兴趣的对象，如屋顶、树木、街道等。这些分割部分通常以简单几何图元的形式表示（例如一个屋顶就可以看做一个图元），图元的分割和提取一般同时进行，而不是分步进行。

分割是三维虚拟重建的基础工作，现在三维扫描仪已经可以同时记录每个扫描点的三维坐标和相关的RGB顏色值。

2算法设计

本文算法的主要步骤：一般地，彩色点云图拥有大量的点，是比较适合用图的概念来理解或操作的数据，根据这一特性，将点云里的每个点与其他点连接，生成一张全连通图，然后再根据2点间的欧氏距离和颜色空间距离定义2点之间边的权值。endprint

再根據设置的颜色、距离阈值，确定分割范围，然后选择一个点作为种子点对分割范围内的点进行最小割运算，最后对打击范围内符合要求的点再进行区域生长，直到在分割范围内找不出符合距离和颜色阈值的点为止，从而得到最后的分割结果。

3实验

图4中默认的颜色阈值只适用于一部分点云，由于不同颜色的点分布不同，会造成一部分点云分割不准确的情况。

不同的2个背景罚函数： a）半径较小的罚函数使得背景点初始数量级较大但增长缓慢； b）半径较大的罚函数使得背景点初始数量级较小但增长迅速。

可见，罚函数加重了分割范围以外的点的权值，且分割范围内的点被保护起来，所以罚函数反映了背景图中点的数量级。不同的罚函数对背景图数量级的影响较大。

4实验结果与分析

通过对数据使用不同的分割方法进行分割，对比得到的效果发现，本方法能对分割中的过分割有较强的改进，能较好地改善分割时非连通区域的分割问题。具体实验结果如图6所示。[JP]

可以看到，图中离小兔子身体较远的手臂和主体是非连通的，通过设置适当的阈值，可以将手臂和主体分割到不同的区域中，解决了连通性的问题，如果想将手臂和身体加到同一区域中，则需要增加距离阈值，即需要增大搜索半径，这样在查找时便可以找到离身体较远的符合颜色阈值的点，进而能够得到很多个性化的分割结果。

5结束语

本文通过结合最小割的思想，针对三维彩色分割中同一颜色区域的分割这一问题进行研究，当获得的数据颜色鲜艳，颜色空间差别较大时，分割效果较为理想。但当分割目标颜色差异较小，或颜色空间跨度较小时，分割结果还有待改进。而这些分割方法作为全自动分割是不够理想的，由于面向的是静态的三维点云模型，想要做到更为精确的分割，可以通过设置颜色阈值、距离阈值等方法增加分割精度。应用到机器视觉或者物品检测等其它领域有一定局限性，但在医疗等领域中，Kinect是一种便携而且造价较为低廉的手持式扫描设备，三维彩色分割能够应用在烧伤检测、医学整形等领域，能够对烧伤皮肤面积进行估算、分割以及不同烧伤程度的识别。

参考文献：

李娜， 马一薇， 杨洋， 等 利用 RANSAC 算法对建筑物立面进行点云分割[J] 测绘科学， 2011， 36（5）： 144-145，138

[2] URAL S， SHAN J A mincut based filter for airborne lidar data[J] International Archives of the Photogrammetry， Remote Sensing & Spatial Information Sciences， 2016，XLI-B3：395-401

[3] 傅欢， 梁力， 王飞， 等 采用局部凸性和八叉树的点云分割算法[J] 西安交通大学学报， 2012， 46（10）： 60-65

[4] 柯映林， 单东日 基于边特征的点云数据区域分割[J] 浙江大学学报（工学版）， 2005， 39（3）： 377-380，396

[5] 欧新良， 匡小兰， 倪问尹 三维散乱点云分割技术综述[J] 湖南工业大学学报， 2010， 24（5）： 45-49

[6] 虞伟民， 王雷， 王津言 基于 HSV 颜色空间的侧方车辆检测[J] 软件导刊， 2016， 15（6）： 218-220

[7] 陈亦欣， 叶锋， 肖锋， 等 基于 HSV 空间和形状特征的交通标志检测识别研究[J] 江汉大学学报 （自然科学版）， 2016， 44（2）： 119-125

[8] 金汉均， 曾婷 小波变换在 HSV 颜色空间上的图像检索应用研究[J] 电子测量技术， 2016，39 （7）： 106-109

[9] VILARIO D L， MARTINEZ J， RIVERA F F， et al Graphbased segmentation of airborne lidar point clouds[C]//SPIE Remote Sensing Edinburgh， United Kingdom： SPIE， 2016： 100040I-100040I-8

[10]BOGOSLAVSKYI I， STACHNISS C Fast range imagebased segmentation of sparse 3d laser scans for online operation[C]//Intelligent Robots and Systems （IROS）， 2016 IEEE/RSJ International Conference on Daejeon， South Korea： IEEE， 2016： 163-169endprint