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

姚礪+李瑤

摘要：提出一種基于最小割的彩色點云分割算法，首先找到彩色點云中每個點的臨近點，然后與父點連接，再找到距離最近的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]，但這些傳統方法對設備要求高，而且價格昂貴，不方便操作。近年來，由于獲取設備和計算機技術的發展，通過三維彩色掃描獲取三維物體的顏色及點云信息模型越發便捷?；谌S彩色點云進行分割是點云處理的基礎，但大部分點云分割算法是從二維圖像分割移植而來，不考慮三維圖像的幾何信息，所以應用到點云分割時，造成了一些不連通的區域由于顏色相似也會被分割到同一區域的問題。而利用幾何特點的分割算法大都是基于灰度模型，但如果希望分割出指定顏色的三維表面，特別是復雜顏色的三維表面，如燒傷區域，那么使用以上從二維移植來的算法解決不了連通性的問題，而只利用幾何特征則解決不了鑒別顏色的問題。因此研究結合了二維顏色特征及三維連通性的特征，提出了基于最小割的彩色三維模型的分割算法。

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