基于最小割的彩色點(diǎn)云分割

姚礪+李瑤

摘要：提出一種基于最小割的彩色點(diǎn)云分割算法，首先找到彩色點(diǎn)云中每個(gè)點(diǎn)的臨近點(diǎn)，然后與父點(diǎn)連接，再找到距離最近的2個(gè)塊并連接，重復(fù)連接距離最小的2個(gè)塊，直到只剩1個(gè)塊，從而生成1張點(diǎn)云圖。根據(jù)2點(diǎn)之間的歐氏距離和顏色空間距離設(shè)置2點(diǎn)連線的權(quán)值，當(dāng)選擇待分割點(diǎn)后根據(jù)設(shè)定的閾值大小和分割范圍，查找被選點(diǎn)分割范圍內(nèi)的所有符合條件的點(diǎn)，然后通過區(qū)域生長(zhǎng)算法對(duì)符合條件的點(diǎn)進(jìn)行生長(zhǎng)，進(jìn)而得到顏色相近的三維連通區(qū)域。實(shí)驗(yàn)證明所提方法可行，可有效解決三維分割中連通性的問題。

關(guān)鍵詞： 最小割； 彩色點(diǎn)云； 分割

中圖分類號(hào)：TP391.41

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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

作者簡(jiǎn)介：

收稿日期： 2017-08-30

0引言

隨著三維掃描技術(shù)的發(fā)展，Kinect等手持式設(shè)備使得通過掃描設(shè)備獲得人體三維點(diǎn)云變得越來越便捷。三維掃描在文物修復(fù)、人體燒傷、紋理映射、醫(yī)學(xué)整形、地理測(cè)量、機(jī)器視覺等領(lǐng)域有著重要應(yīng)用。

傳統(tǒng)的測(cè)量方法有光學(xué)測(cè)量法、超聲波法等[1-5]，但這些傳統(tǒng)方法對(duì)設(shè)備要求高，而且價(jià)格昂貴，不方便操作。近年來，由于獲取設(shè)備和計(jì)算機(jī)技術(shù)的發(fā)展，通過三維彩色掃描獲取三維物體的顏色及點(diǎn)云信息模型越發(fā)便捷?；谌S彩色點(diǎn)云進(jìn)行分割是點(diǎn)云處理的基礎(chǔ)，但大部分點(diǎn)云分割算法是從二維圖像分割移植而來，不考慮三維圖像的幾何信息，所以應(yīng)用到點(diǎn)云分割時(shí)，造成了一些不連通的區(qū)域由于顏色相似也會(huì)被分割到同一區(qū)域的問題。而利用幾何特點(diǎn)的分割算法大都是基于灰度模型，但如果希望分割出指定顏色的三維表面，特別是復(fù)雜顏色的三維表面，如燒傷區(qū)域，那么使用以上從二維移植來的算法解決不了連通性的問題，而只利用幾何特征則解決不了鑒別顏色的問題。因此研究結(jié)合了二維顏色特征及三維連通性的特征，提出了基于最小割的彩色三維模型的分割算法。

1背景概述

Kinect v2 是微軟第二代Kinect，搭載于微軟最新一代游戲機(jī)Xbox one 上，用于感知3D 音頻和圖像，Kinect v2的ToF 處理器芯片是TSMC 013 1P5。MKinect v2如圖1 所示，包含一個(gè)彩色相機(jī)、深度相機(jī)、紅外光發(fā)射器。而延續(xù)2代的Kinect的深度效果對(duì)比則如圖2所示。通過Kinect v2 可以獲取場(chǎng)景的深度、彩色、紅外圖像等信息。

分割是把三維空間中的點(diǎn)劃分成較小的、連續(xù)的子集過程。分割之后，得到具有相似屬性的點(diǎn)。這些點(diǎn)的子集應(yīng)該是“有意義的”，分割后應(yīng)該得到一系列研究感興趣的對(duì)象，如屋頂、樹木、街道等。這些分割部分通常以簡(jiǎn)單幾何圖元的形式表示（例如一個(gè)屋頂就可以看做一個(gè)圖元），圖元的分割和提取一般同時(shí)進(jìn)行，而不是分步進(jìn)行。

分割是三維虛擬重建的基礎(chǔ)工作，現(xiàn)在三維掃描儀已經(jīng)可以同時(shí)記錄每個(gè)掃描點(diǎn)的三維坐標(biāo)和相關(guān)的RGB顏色值。

2算法設(shè)計(jì)

本文算法的主要步驟：一般地，彩色點(diǎn)云圖擁有大量的點(diǎn)，是比較適合用圖的概念來理解或操作的數(shù)據(jù)，根據(jù)這一特性，將點(diǎn)云里的每個(gè)點(diǎn)與其他點(diǎn)連接，生成一張全連通圖，然后再根據(jù)2點(diǎn)間的歐氏距離和顏色空間距離定義2點(diǎn)之間邊的權(quán)值。endprint

再根據(jù)設(shè)置的顏色、距離閾值，確定分割范圍，然后選擇一個(gè)點(diǎn)作為種子點(diǎn)對(duì)分割范圍內(nèi)的點(diǎn)進(jìn)行最小割運(yùn)算，最后對(duì)打擊范圍內(nèi)符合要求的點(diǎn)再進(jìn)行區(qū)域生長(zhǎng)，直到在分割范圍內(nèi)找不出符合距離和顏色閾值的點(diǎn)為止，從而得到最后的分割結(jié)果。

3實(shí)驗(yàn)

圖4中默認(rèn)的顏色閾值只適用于一部分點(diǎn)云，由于不同顏色的點(diǎn)分布不同，會(huì)造成一部分點(diǎn)云分割不準(zhǔn)確的情況。

不同的2個(gè)背景罰函數(shù)： a）半徑較小的罰函數(shù)使得背景點(diǎn)初始數(shù)量級(jí)較大但增長(zhǎng)緩慢； b）半徑較大的罰函數(shù)使得背景點(diǎn)初始數(shù)量級(jí)較小但增長(zhǎng)迅速。

可見，罰函數(shù)加重了分割范圍以外的點(diǎn)的權(quán)值，且分割范圍內(nèi)的點(diǎn)被保護(hù)起來，所以罰函數(shù)反映了背景圖中點(diǎn)的數(shù)量級(jí)。不同的罰函數(shù)對(duì)背景圖數(shù)量級(jí)的影響較大。

4實(shí)驗(yàn)結(jié)果與分析

通過對(duì)數(shù)據(jù)使用不同的分割方法進(jìn)行分割，對(duì)比得到的效果發(fā)現(xiàn)，本方法能對(duì)分割中的過分割有較強(qiáng)的改進(jìn)，能較好地改善分割時(shí)非連通區(qū)域的分割問題。具體實(shí)驗(yàn)結(jié)果如圖6所示。[JP]

可以看到，圖中離小兔子身體較遠(yuǎn)的手臂和主體是非連通的，通過設(shè)置適當(dāng)?shù)拈撝?，可以將手臂和主體分割到不同的區(qū)域中，解決了連通性的問題，如果想將手臂和身體加到同一區(qū)域中，則需要增加距離閾值，即需要增大搜索半徑，這樣在查找時(shí)便可以找到離身體較遠(yuǎn)的符合顏色閾值的點(diǎn)，進(jìn)而能夠得到很多個(gè)性化的分割結(jié)果。

5結(jié)束語

本文通過結(jié)合最小割的思想，針對(duì)三維彩色分割中同一顏色區(qū)域的分割這一問題進(jìn)行研究，當(dāng)獲得的數(shù)據(jù)顏色鮮艷，顏色空間差別較大時(shí)，分割效果較為理想。但當(dāng)分割目標(biāo)顏色差異較小，或顏色空間跨度較小時(shí)，分割結(jié)果還有待改進(jìn)。而這些分割方法作為全自動(dòng)分割是不夠理想的，由于面向的是靜態(tài)的三維點(diǎn)云模型，想要做到更為精確的分割，可以通過設(shè)置顏色閾值、距離閾值等方法增加分割精度。應(yīng)用到機(jī)器視覺或者物品檢測(cè)等其它領(lǐng)域有一定局限性，但在醫(yī)療等領(lǐng)域中，Kinect是一種便攜而且造價(jià)較為低廉的手持式掃描設(shè)備，三維彩色分割能夠應(yīng)用在燒傷檢測(cè)、醫(yī)學(xué)整形等領(lǐng)域，能夠?qū)齻つw面積進(jìn)行估算、分割以及不同燒傷程度的識(shí)別。

參考文獻(xiàn)：

李娜， 馬一薇， 楊洋， 等 利用 RANSAC 算法對(duì)建筑物立面進(jìn)行點(diǎn)云分割[J] 測(cè)繪科學(xué)， 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] 傅歡， 梁力， 王飛， 等 采用局部凸性和八叉樹的點(diǎn)云分割算法[J] 西安交通大學(xué)學(xué)報(bào)， 2012， 46（10）： 60-65

[4] 柯映林， 單東日 基于邊特征的點(diǎn)云數(shù)據(jù)區(qū)域分割[J] 浙江大學(xué)學(xué)報(bào)（工學(xué)版）， 2005， 39（3）： 377-380，396

[5] 歐新良， 匡小蘭， 倪問尹 三維散亂點(diǎn)云分割技術(shù)綜述[J] 湖南工業(yè)大學(xué)學(xué)報(bào)， 2010， 24（5）： 45-49

[6] 虞偉民， 王雷， 王津言 基于 HSV 顏色空間的側(cè)方車輛檢測(cè)[J] 軟件導(dǎo)刊， 2016， 15（6）： 218-220

[7] 陳亦欣， 葉鋒， 肖鋒， 等 基于 HSV 空間和形狀特征的交通標(biāo)志檢測(cè)識(shí)別研究[J] 江漢大學(xué)學(xué)報(bào) （自然科學(xué)版）， 2016， 44（2）： 119-125

[8] 金漢均， 曾婷 小波變換在 HSV 顏色空間上的圖像檢索應(yīng)用研究[J] 電子測(cè)量技術(shù)， 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