沈超， 王斌， 吳曉峰

(復(fù)旦大學(xué) 信息科學(xué)與工程學(xué)院， 上海 200433)

0 引言

隨著深度傳感器的不斷發(fā)展成熟，普通用戶可以使用手機(jī)、廉價深度相機(jī)，例如蘋果iPhone X、微軟Kinect等設(shè)備獲取周圍場景的深度信息。深度信息可以反映周圍場景的空間拓?fù)浣Y(jié)構(gòu)，是色彩信息的有力補充。根據(jù)獲取的場景RGBD信息，可以對RGBD數(shù)據(jù)進(jìn)行場景解析。這在場景識別，增強現(xiàn)實，三維重建等計算機(jī)視覺應(yīng)用中有著重要應(yīng)用。受場景復(fù)雜度、紋理噪聲、光照條件等因素的影響，目前使用的場景解析算法還存在較多問題。

場景解析作為計算機(jī)視覺任務(wù)的前端一環(huán)，對算法效果和運算速度都有較高的要求?，F(xiàn)有的高速場景解析算法[1-3]大多數(shù)只處理場景圖像的色彩數(shù)據(jù)，沒有考慮深度信息。而已有的面向RGBD場景的解析算法大多要對法向量、重力方向等進(jìn)行計算優(yōu)化，難以保證算法的實時性。另外，現(xiàn)有場景解析算法基本都難以達(dá)到30 Hz以上的運行速度。為此難以滿足解析算法可以實時運行、面向RGBD場景的需求。

本文的主要工作是提出了一種新的高速RGBD場景解析算法。使用加入空間平滑約束和邊緣支持、含深度信息的高速過分割算法，對場景的RGBD圖像進(jìn)行過分割，并將過分割塊構(gòu)成無向圖。然后運用層級結(jié)構(gòu)的多特征求權(quán)Felzen-Hutten算法[2]進(jìn)行無向圖圖割優(yōu)化，完成場景解析。本文在RGBD場景數(shù)據(jù)集上對算法進(jìn)行了實驗，并得出實驗結(jié)果。接下來從整體架構(gòu)和步驟細(xì)節(jié)兩方面論述整個算法，之后進(jìn)行實驗驗證，最后給出文章結(jié)論。

1 算法論述

1.1 整體架構(gòu)

本文提出的算法整體架構(gòu)主要分為兩大部分，一是高速RGBD場景過分割，二是過分割塊的層級圖割歸并，都在CUDA架構(gòu)上實現(xiàn)。具體如圖1所示。

整個算法的輸入數(shù)據(jù)為場景的RGBD信息。每個場景的RGBD信息由色彩信息(RGB)和深度信息(D)兩部分組成，具體為一組色彩與深度圖像對。本文結(jié)合圖像的色彩和深度四個維度的信息，首先運用提出的超高速過分割算法BSD-gSLICr，對場景圖像對進(jìn)行過分割，將圖像分解為過分

圖1 算法整體框架

割塊。然后將過分割塊視為頂點，結(jié)合過分割塊間相鄰關(guān)系構(gòu)建無向圖，并根據(jù)塊間特征計算相鄰邊權(quán)重。最后應(yīng)用層次結(jié)構(gòu)的Felzen-Hutten算法，對過分割塊組成的無向圖進(jìn)行多層次圖割分塊，從而得到最終的場景解析結(jié)果。

我們之所以使用過分割與層級Felzen-Hutten圖割的兩步架構(gòu)，一方面是利用BSD-gSLICr超高速的過分割能力，降低后續(xù)算法運算量，保證算法實時性，同時削弱噪聲的影響。另一方面，對處理后的過分割塊，采用層級結(jié)構(gòu)的Felzen-Hutten算法進(jìn)行圖割歸并，可以實現(xiàn)在不同層級注重不同的分塊特征，從而應(yīng)用不同的圖割策略，這也具有現(xiàn)實的物理意義?？傊疚奶岢龅募軜?gòu)在底層可以緩解噪聲干擾，在高層可以改變算法策略，具有高度的靈活性和適應(yīng)性。

1.2 步驟細(xì)節(jié)

1.2.1 BSD-gSLICr算法

本文提出的BSD-gSLICr算法是高速RGBD場景過分割部分的核心。2015年，牛津動視實驗室開發(fā)了gSLICr算法[4]，在GPU上實現(xiàn)了250Hz的圖像過分割速率。

本文在參考gSLICr架構(gòu)的基礎(chǔ)上，進(jìn)一步引入場景深度信息，并添加了空間平滑約束。同時加入了邊緣支持，減輕了空間信息比重增加造成的不利影響。我們精心設(shè)計了運算架構(gòu)，用CUDA技術(shù)實現(xiàn)了BSD-gSLICr算法。具體如圖2所示。

圖2 CUDA架構(gòu)下實現(xiàn)的BSD-gSLICr算法流程

除了讀取圖像部分，其余操作步驟都在GPU上處理。

(1) 空間平滑約束

gSLICr算法本質(zhì)是一種快速SLIC算法[5]，通過對像素點進(jìn)行聚類形成超像素，達(dá)到過分割圖像的效果。gSLICr算法中的距離度量公式?jīng)Q定了像素聚類策略，是整個算法的關(guān)鍵。我們在距離度量公式中，加入了場景深度信息，并創(chuàng)新地添加了三維空間平滑約束項，以提升分割效果和魯棒性。具體改進(jìn)的距離度量式如式(1)～式(4)。

(1)

(2)

(3)

(4)

其中dc、ds分別為像素點與聚類中心間的lab色彩空間距離、xy坐標(biāo)位置距離。dge為像素點深度距離，其中根式內(nèi)第一項即為添加的三維空間平滑約束，式中cn,fn是場景拍攝相機(jī)的內(nèi)參。D為像素點到聚類中心的總加權(quán)距離，其中N是像素總數(shù)量，K是聚類中心數(shù)量，m為緊密度，λ為深度信息權(quán)重。

(2) 邊緣支持

由于距離度量公式中添加了深度信息，增強了空間因素在像素聚類中的作用。這導(dǎo)致圖像中某些實體間的顏色邊緣會因為深度信息的干擾被聚類到同一個塊中，這對后面場景解析中具體實體的分割有較大影響。為此，在算法中引入了邊緣支持。分別對RGB圖像和深度圖像，用canny算子檢測邊緣，合并形成邊緣支持圖。同時在距離度量公式中加入懲罰項如式(5)、(6)。

Dbs=D+Penalty(path((x,y)->(xc,yc)))

(5)

(6)

根據(jù)像素點與超像素中心的方位，采用分段的曼哈頓式折線形成連通路徑。如圖3所示。圖3如果路徑上存在邊緣支持點，則在距離公式中添加懲罰項，使得像素點不會聚類到邊緣另一邊的超像素中心。這可以改善添加深度信息以后，聚類時空間因素過度優(yōu)先的問題。

圖3 根據(jù)像素點和超像素中心選擇連通路徑的選擇

1.2.2 層級Felzen-Hutten圖割歸并

在第一部分，場景RGBD圖像對BSD-gSLICr算法被分解為了超像素的過分割塊。我們把每個過分割塊看作一個頂點，塊間相鄰關(guān)系作為邊，鄰接塊特征的不相似程度作為邊權(quán)值，形成一個以超像素的過分割塊為單位的無向圖。并采用層次結(jié)構(gòu)的Felzen-Hutten算法對無向圖進(jìn)行快速圖割歸并，完成超像素分割塊的聚類，達(dá)到高速場景解析的目的。

Felzen-Hutten算法偽代碼如下：

Felzen-Hutten算法：

輸入：超像素?zé)o向圖G=(V,E,W)，

輸出：分割結(jié)果S=(C1,…,Cr)

初始化:將所有邊權(quán)值w按從小到大排序P=(w1,…,wm)

forq=1,…,mdo

for eachwq=w(vi,vj) do

end if

end if

end for

end for

原始的FH算法中，無向圖中邊的權(quán)值只由相鄰分塊間的均色差異來決定。我們在RGBD場景解析的背景下，提出了新的邊權(quán)值計算方法。充分利用RGBD場景提供的深度信息，在相鄰分塊間均色差異的基礎(chǔ)上，引入邊緣均色梯度、邊緣均深梯度、分塊位置差異，來共同決定相鄰邊的權(quán)值。其中，分塊均色差異distmc計算相鄰過分割塊間的平均lab空間顏色距離，

distmc(sp1,sp2)=‖mColorsp1-mColorsp2‖2

(7)

分塊位置差異distmp計算相鄰過分割塊中心間的二維坐標(biāo)距離，

distmp(sp1,sp2)=‖mPositionsp1-mPositionsp2‖2

(8)

邊緣均色梯度mBGc計算相鄰過分割塊間共同邊緣上，每個像素與周圍像素的色差，如式(9)。

(9)

邊緣均深梯度mBGd計算相鄰過分割塊間共同邊緣上，每個像素與周圍像素的深度差異，為式(10)。

(10)

相鄰過分割塊間總的邊權(quán)值w，由上述四個部分加權(quán)組成，為式(11)。

(11)

其中加權(quán)權(quán)值ω根據(jù)預(yù)訓(xùn)練集，采用線性svm預(yù)測回歸的方法訓(xùn)練得到?？紤]到在過分割塊歸并整合的不同階段，各個塊特征的重要性也應(yīng)該不同。所以對不同層的訓(xùn)練，采用上一層得到的結(jié)果更新數(shù)據(jù)集，然后進(jìn)行訓(xùn)練得到每層特有的加權(quán)權(quán)值。

得到每層的邊權(quán)計算公式之后，我們就可以使用層次結(jié)構(gòu)的方式，逐次對過分割塊組成的無向圖，采用Felzen-Hutten算法進(jìn)行優(yōu)化歸并。經(jīng)層級Felzen-Hutten算法優(yōu)化之后，最終可以得到場景的解析結(jié)果。

2 仿真結(jié)果

我們用CUDA架構(gòu)實現(xiàn)了本文提出的算法并進(jìn)行測試，測試平臺使用的CPU為Intel i7-6700K,使用的GPU為NVIDIA GTX1070。我們在紐約大學(xué)深度場景數(shù)據(jù)集v2[6]、明德雙目視數(shù)據(jù)集[7]等RGBD場景數(shù)據(jù)庫上做了測試。我們與一些快速分割及場景解析算法進(jìn)行了比較，主要包括經(jīng)典的分水嶺算法、Felzen-Hutten算法、MeanShift算法，以及近期出現(xiàn)的快速場景解析算法如FGBOS算法[8]、HFS算法。最后得到了實驗結(jié)論。

2.1 場景解析效果及拓展性

(1) 在明德雙目視數(shù)據(jù)庫上對算法進(jìn)行了仿真，效果如圖4所示。

圖4 明德雙目視數(shù)據(jù)庫算法測試結(jié)果

圖4中從第2列至第7列依次為分水嶺算法、Felzen-Hutten算法、MeanShift算法、FGBOS算法、HFS算法和本文提出的算法。

(2) 在紐約大學(xué)深度場景數(shù)據(jù)集v2中對上述算法進(jìn)行了測試，部分場景解析效果圖，如下圖5所示：

可以看到相對其他方法，本文提出的算法能夠?qū)?fù)雜場景進(jìn)行有效分解，分離出其中的具體實體，取得較好的場景解析效果。同時可以看到，本文提出的算法相對其他算法，能較好地避免過分割和欠分割現(xiàn)象，對于各個完整實體的區(qū)分度也更高。

另外，由于綜合考慮了色彩和深度信息等多個特征，本

圖5 Nyu Depth Dataset v2數(shù)據(jù)庫算法測試結(jié)果

文提出的算法不易受到高頻紋理變化的干擾，例如對原始場景1中幕墻上的光點和桌面上的紋理就有很好的抑制作用。同時即使在光照條件惡劣，場景顏色區(qū)分度差的極端情況下，如原始場景2中，前景物體與背景幾乎難以區(qū)分，本文提出的算法在其他算法幾乎失效時，場景解析的魯棒性依然較強。

值得指出的是，本文算法根據(jù)應(yīng)用場景的不同，也可以方便的拓展到單張RGB場景圖像或單張深度場景圖像上。例如在只有場景深度信息時，在BSD-gSLICr算法分割部分，只需根據(jù)場景深度圖像檢測邊緣，計算(2)、(3)兩式，同時將(4)式修改為式(12)。

(12)

然后在層級Felzen-Hutten圖割歸并部分，把邊權(quán)值計算公式中的色彩特征項distmc、mBGc消除，只計算深度特征項，并調(diào)整相應(yīng)權(quán)值，將(11)式修改為式(13)。

w=ωmpdistmp(sp1,sp2)+ωdmBGd(sp1,sp2)

(13)

就形成了本文提出的算法針對單深度場景的簡約版本。以此類推，只需將算法中深度信息項消除，也可以形成本文算法針對單RGB色彩場景的簡約版本。當(dāng)然可以根據(jù)需要，在簡約版算法的邊權(quán)值計算公式中，加入更多色彩或者深度的塊特征項，以提高算法效果。

2.2 算法復(fù)雜度及運行速度

表1 不同算法平均運行速度(ms)

由表1可見，本文提出的算法由于在CUDA架構(gòu)上經(jīng)優(yōu)化實現(xiàn)，在保證算法精度的前提下,速度有較大提高，與目前最快速的HFS算法基本接近。對于常見的640*480的圖像分辨率，本文提出的算法運行速度平均在25 ms左右。特別在高圖像分辨率的情況下，本文算法由于應(yīng)用了過分割算法降低復(fù)雜度，相對傳統(tǒng)算法速度有明顯優(yōu)勢。由于滿足實時要求，本文算法可以廣泛應(yīng)用在各類計算機(jī)視覺任務(wù)中，提升運算速度。

3 總結(jié)

本文提出了并在CUDA架構(gòu)上實現(xiàn)一種新的高速RGBD場景解析算法。在gSLICr算法基礎(chǔ)上，引入了帶空間平滑約束的深度信息，并加入邊緣支持，提出了BSD-gSLICr算法。并使用BSD-gSLICr算法對RGBD場景圖像進(jìn)行過分割，然后采用改進(jìn)邊權(quán)計算方式的Felzen-Hutten算法，將過分割塊構(gòu)成的無向圖進(jìn)行多層級的圖割歸并，得到最終的場景解析結(jié)果。在多個RGBD數(shù)據(jù)庫上的實驗結(jié)果表明，本文提出的算法兼具速度和效果優(yōu)勢。相對一些傳統(tǒng)算法，在速度及效果上均有較大的提高。而與目前先進(jìn)水平的算法相比，在處理高頻紋理或者光照條件惡劣的場景時，本文算法也有獨有優(yōu)勢。未來會針對場景深度信息缺失、噪聲等情況，考慮添加置信度，進(jìn)一步增加算法的魯棒性。

[1] Cheng MM，YUN Liu, Qibin Hou. et al. (2016) HFS: Hierarchical Feature Selection for Efficient Image Segmentation[C]∥Eccv 2016 Amsterdam Netherlands. Lecture Notes in Computer Science[M]. V. 9907. Springer.

[2] Felzenszwalb PF, Huttenlocher DP. Efficient graph-based image segmentation[J]. IJCV, 2004,59(2), 167-181.

[3] Jean Cousty, Gilles Bertrand, Laurent Najman, and Michel Couprie. Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(8): 1362-1374.

[4] Ren, Carl & Prisacariu, Victor & D Reid, Ian. gSLICr: SLIC superpixels at over 250 Hz[R]. arXiv preprint arXiv:1509.04232,2015.

[5] Achanta R, Shaji A, Smith K, et al. SLIC Superpixels Compared to State-of-the-Art Superpixel Methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(11): 2274-2282.

[6] Silberman N, Hoiem D, Kohli P, et al. Indoor Segmentation and Support Inference from RGBD Images∥Lecture Notes in Computer Science (vvl 7576)[M]. Berlin: Springer.

[7] Scharstein, C. Pal. Learning conditional random fields for stereo[C]∥In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2007), Minneapolis, 2007.pp1-8.

[8] Toscana G, Rosa S, Bona B. Fast Graph-Based Object Segmentation for RGB-D Images[C]. Intellisys 2016, London, UK. pp42-58.