基于降采樣歸一化割的多尺度分層分割方法研究

童昊浩　吳克偉

摘要：圖像分割作為計(jì)算機(jī)視覺的中層任務(wù)，常建立在目標(biāo)輪廓特征的基礎(chǔ)上，但是局部輪廓檢測器的結(jié)果難以保證其產(chǎn)生封閉輪廓。為獲得完整的分割區(qū)域，歸一化割方法提供一種將局部輪廓結(jié)果轉(zhuǎn)化為圖像分割結(jié)果的處理途徑。傳統(tǒng)的歸一化割方法由于長特征向量的聚類導(dǎo)致計(jì)算耗時長、內(nèi)存占用多。在輪廓特征的基礎(chǔ)上，考慮輪廓的全局推斷，提出一種歸一化割的改進(jìn)方法——降采樣歸一化割，以減少圖像分割過程中的計(jì)算耗時。通過多尺度空間下的層級校準(zhǔn)，準(zhǔn)確定位多個尺度下的區(qū)域邊界進(jìn)行區(qū)域合并，從而得到更準(zhǔn)確的多層分割圖。

關(guān)鍵詞：分層分割；降采樣歸一化割；尺度空間；層級校準(zhǔn)；區(qū)域合并

DOIDOI：10.11907/rjdk.151428

中圖分類號：TP317.4

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2015）008019003

0 引言

分割可看作是一種把圖像分成若干區(qū)域的方法。分割問題和輪廓檢測問題是相關(guān)的，但是兩者又不完全一樣。一般情況下，基于局部外觀特征的輪廓檢測器[1]不能保證產(chǎn)生閉合的輪廓，因此不能將圖像的一部分劃分成區(qū)域，但是分割區(qū)域可以根據(jù)邊界恢復(fù)得到閉合輪廓，因此圖像分割常建立在目標(biāo)輪廓特征的基礎(chǔ)上進(jìn)行區(qū)域劃分。

近年來，圖論（Graph Theory）是研究分割的一個熱點(diǎn)[2]。歸一化割（Normalizedcut，Ncut）[3]是基于圖論的分割方法之一。特征向量計(jì)算是歸一化割中聚類算法的計(jì)算瓶頸，特征向量的高效計(jì)算成為研究重點(diǎn)。Sharon等[4]提出了一種替代方法來改進(jìn)歸一化割方法的計(jì)算效率。這種方法受代數(shù)多重網(wǎng)格的啟發(fā)，通過選擇節(jié)點(diǎn)的子集迭代粗化原譜圖。Taylor[5]提出了一種技術(shù)：使用一個簡單的分水嶺過分割用以減少特征向量大小問題，其不足之處是提高計(jì)算效率的同時犧牲了目標(biāo)準(zhǔn)確度。Maire 和Yu[6]提出了一種新型的多網(wǎng)格求解器，用于產(chǎn)生多尺度空間特征向量，利用粗糙尺度的解加速精細(xì)尺度的特征向量計(jì)算。

本文使用圖像的尺度空間結(jié)構(gòu)。相比于多尺度求解，本文方法簡單地降低了空間尺度，在退化空間上求解，并將解進(jìn)行升采樣保留圖像結(jié)構(gòu)，使得在保持性能的前提下計(jì)算更加簡潔、快速，即降采樣歸一化割，這使得歸一化割的效率大大提高。同時，采用一種多尺度層級校準(zhǔn)的方法用于區(qū)域合并，從而得到更準(zhǔn)確的分層分割圖。

1 改進(jìn)歸一化割

歸一化割方法是高性能輪廓檢測器的一個關(guān)鍵全局化機(jī)制[1]。雖然功能強(qiáng)大，但其計(jì)算成本、存儲需求較高，限制了它的可擴(kuò)展性[7]。本文介紹一種高效的降采樣歸一化割方法，不僅充分保留了輪廓檢測性能，而且具有低存儲需求及特征向量計(jì)算效率提升20倍的優(yōu)點(diǎn)。

1.1 降采樣歸一化割

歸一化割主要是依據(jù)給定的編碼像素之間的相似性建立關(guān)聯(lián)矩陣A，并定義對角線矩陣Bii=∑jAij，求解線性系統(tǒng)的廣義特征向量（B-A）v=λBv。由于矩陣A很大，即使有先進(jìn)的求解器，直接計(jì)算也具有較大的計(jì)算成本和存儲需求。

本文采用利用多尺度性質(zhì)技術(shù)以有效得到近似解。定義pixel_decimate（A），表示關(guān)聯(lián)矩陣中對應(yīng)降采樣圖像的行列索引，也就是說，如果i=pixel_decimate（A），則A[i，i]{JP是一個降采樣矩陣，對應(yīng)圖像的行和列交替去除。由于像素大量減少，計(jì)算A[i，i]的特征向量效果并不理想，但是計(jì)算降采樣的平方關(guān)聯(lián)矩陣A2[i，i]的特征向量是和A的特征向量相似的。因?yàn)樵诮挡蓸又?，平方關(guān)聯(lián)矩陣A2[i，i]使得每個像素的信息都傳播到了其領(lǐng)域之中，即使降采樣后依然保留了所有像素的信息。通過A[：，i]TA[：，i]有效計(jì)算A2[i，i]，并計(jì)算A2[i，i]的特征向量，然后通過與A[：，i]相乘升采樣這些特征向量回到原始圖像的尺度空間。這種平方和降采樣的操作可以在輕微降低準(zhǔn)確度的情況下大大提高效率。

本文將這種改進(jìn)歸一化割算法稱為降采樣歸一化割（Downsampled NormalizedCuts，DNCuts），其中D是平方和降采樣操作的循環(huán)次數(shù)。降采樣歸一化割反復(fù)應(yīng)用平方和降采樣操作，并利用標(biāo)準(zhǔn)的歸一化割求解器ncuts（AD，K），計(jì)算最終的降采樣矩陣AD及其對應(yīng)的K個最小特征向量，并重新升采樣這些特征向量。

1.2 輪廓全局推斷

輪廓全局推斷的關(guān)鍵在于使用從歸一化割中獲得的特征向量。文獻(xiàn)[1]展示的是目前世界領(lǐng)先的局部輪廓檢測器之一，將其輪廓檢測結(jié)果lE作為譜圖劃分的輸入，使用輪廓中間線索，即兩像素連接線間的置信度最大值，建立稀疏對稱仿射矩陣A，如圖1所示。連接所有位于固定半徑r中的像素i和j，進(jìn)行關(guān)聯(lián)計(jì)算：

其中，ij為連接i和j的分割線段且ρ為常量，設(shè)置r=5，ρ=0.1。

為了引入全局信息，定義Bii=∑jAij并根據(jù)1.1節(jié)中的降采樣歸一化割，求解（B-A）v=λBv的廣義特征向量v0，v1，...，vn，對應(yīng)于n+1最小特征值λ（實(shí)驗(yàn)中取n=5）。觀察到特征向量本身攜帶了全局輪廓信息（見圖1）。視每個特征向量vk為一幅圖像，將其與高斯方向?qū)?shù)濾波器在多個方向θ上卷積，獲得定向信號θvk（x，y）。來自不同特征向量的信息提供給輪廓檢測器的譜成分，并在方向上取最大值作為譜信號：

其中，權(quán)重為1/λk的動機(jī)來自廣義特征向量問題并作為質(zhì)量彈簧系統(tǒng)[9]的物理解釋，λk=2。

信號lE和sE傳遞不同的信息（局部輪廓線索和全局輪廓線索），簡單的線性結(jié)合足夠獲取兩者的優(yōu)勢。最終輪廓邊緣置信度被寫作局部邊緣置信度和譜信號的加權(quán)和：

其中，權(quán)值δ通過訓(xùn)練圖像使用梯度上升學(xué)習(xí)獲得。

2 多尺度分層分割

首先采用分水嶺轉(zhuǎn)換（Watershed Transform）從邊緣置信度圖中產(chǎn)生一組初始區(qū)域，即生成超像素圖，在超像素圖的基礎(chǔ)上利用輪廓權(quán)值建立一個層次性分割。設(shè)圖像的分割區(qū)域劃分為多個領(lǐng)域S=Sii。一個分割層級結(jié)構(gòu)定義如下的一系列族區(qū)域S*，S1，...，SL：①S*是最精細(xì)級別的超像素塊集合；②SL是整個區(qū)域；③粗糙級區(qū)域是精細(xì)級區(qū)域的聯(lián)合。層次結(jié)構(gòu)中每個級別Si都被分配一個實(shí)值索引λi，這個索引可以通過樹狀圖來表示。在區(qū)域樹中，每個結(jié)點(diǎn)的高度是其索引值。對于分層分割，本文將這種表示稱為超度量輪廓圖（Ultrametric Contour Map，UCM），這個超度量輪廓圖中每條輪廓的權(quán)值即為該輪廓兩邊區(qū)域合并的索引值[8]。這種表示方式將輪廓檢測和多層圖像分割問題統(tǒng)一起來，超度量輪廓圖中的一個閾值λi產(chǎn)生分割塊Si。這種算法使得區(qū)域樹的每個級別上具有視覺線索的同質(zhì)性，超度量輪廓圖的輪廓權(quán)值可以理解為區(qū)域差異性的度量手段。分層分割示例如圖2所示。

尺度空間是計(jì)算機(jī)視覺中一種強(qiáng)大的處理策略。將它用于兩種不同的方式，開發(fā)一種高效、可擴(kuò)展和高精度分割算法：①加速譜圖劃分；②創(chuàng)建對齊的分割層級。下面介紹如何通過校準(zhǔn)來創(chuàng)建對齊的分割層級。

2.1 層級校準(zhǔn)

對于超像素圖的區(qū)域合并，需要校準(zhǔn)對齊分割層級。選擇在多層結(jié)構(gòu)中均勻采樣K層級，并依次將它們的圖像邊緣重構(gòu)為超度量輪廓圖。假設(shè)有兩種不同的分割塊R=Rii和S=Sjj。定義分割塊R映射至區(qū)域Sj∈S的標(biāo)準(zhǔn)為大多數(shù)標(biāo)記的位置區(qū)域。

則R投影至S上

為了將一個超度量輪廓圖映射至目標(biāo)分割塊S，要在層級的每個級別定義π（UCM，S）。

迭代這個操作，遞歸地將超度量輪廓圖投影到一組目標(biāo)分割塊S1*，...，SN*。兩個這樣的映射構(gòu)成可以表示為如下公式：

2.2 多尺度層級

通過升采樣和降采樣原始圖像構(gòu)造一個N尺度的多分辨率空間金字塔，每一個尺度均應(yīng)用單尺度分割器分割圖像。根據(jù)2.1節(jié)層級校準(zhǔn)遞歸轉(zhuǎn)換所有更粗糙級的超度量輪廓圖邊界的權(quán)值。校準(zhǔn)后，圖像有一組固定的邊界位置，每個邊界對應(yīng)N個權(quán)值中的一個，對應(yīng)不同的尺度。將此轉(zhuǎn)換為二值邊界分類問題，并利用邏輯回歸訓(xùn)練一個分類器，用于合并N個權(quán)值到一個單一的邊緣概率估計(jì)值，得到最終的超度量輪廓圖，其中每個層級都對應(yīng)一個級別的層級分割。

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

實(shí)驗(yàn)采用的數(shù)據(jù)集為Carnegie Mellon University的輪廓檢測和分割數(shù)據(jù)集[10]。對于分割算法，其評價策略多種多樣。多種基于區(qū)域的度量標(biāo)準(zhǔn)包括：信息變化（Variation of Information， VI）、蘭德指數(shù)（Rand Index， RI）、分割覆蓋（Covering）。

圖3給出了CMU數(shù)據(jù)集上部分gpbucm和gEucm的超度量輪廓圖結(jié)果，其中圖3（d）為OIS（optimal image scale）分割結(jié)果，即每張圖分別取最優(yōu)閾值時的最優(yōu)分割圖。從整體上看，gEucm的超度量輪廓圖與gpbucm的超度量輪廓圖相比，具有更好的視覺輪廓感官效果，分割塊對應(yīng)目標(biāo)更準(zhǔn)確，并且運(yùn)動目標(biāo)邊緣更加顯著，更加貼近于數(shù)據(jù)集中的手工標(biāo)記輪廓。

為考察gEucm的綜合性能，采用Covering、PRI和VI三種評估策略進(jìn)行定量分析。表1顯示了CMU數(shù)據(jù)集上Covering、PRI和VI三種性能評估指標(biāo)。其中，每個指標(biāo)均有兩個值：ODS和OIS。ODS（optimal dataset scale）指測試結(jié)果在整個數(shù)據(jù)集上取同一閾值得到的性能指標(biāo)，OIS（optimal image scale）指測試結(jié)果在每個數(shù)據(jù)上取最優(yōu)閾值得到的整個數(shù)據(jù)集的平均性能指標(biāo)。理論上，Covering和PRI的值越大，分割性能越好，VI值越小性能越好。從表1可以看出，gEucm和gpbucm的性能明顯好于傳統(tǒng)歸一化割方法Ncuts，而gEucm和gpbucm在Covering和PRI上的指標(biāo)基本一致（個別指標(biāo)gEucm略好）。而在VI指標(biāo)上，gEucm要好于gpbucm（VI值更低）。從指標(biāo)的本義上來說， gEucm的測試結(jié)果和真實(shí)手工標(biāo)記差異較小。定量分析結(jié)果與定性結(jié)果基本一致。

除了考察gEucm的綜合性能外，本文還對gEucm和gpbucm的檢測效率進(jìn)行了測算。表2顯示的是兩者在單幅圖像上（640x480）的平均檢測時間?？梢钥闯霰疚姆椒ㄓ捎谠诮挡蓸託w一化割過程中，特征向量計(jì)算時間比傳統(tǒng)歸一化割方法快了20倍，使得在整體檢測效率上有了較大提升。實(shí)驗(yàn)表明，本文方法在保證分割性能的前提下大幅提高了檢測效率。

4 結(jié)語

針對歸一化割中特征向量計(jì)算耗時長的問題，本文采用在退化空間中降采樣歸一化割，對傳統(tǒng)的歸一化割方法進(jìn)行改進(jìn)，以減少圖像分割過程的計(jì)算耗時，并對輪廓進(jìn)行全局推斷。通過多尺度空間下的層級校準(zhǔn)，準(zhǔn)確定位多個尺度下的區(qū)域邊界進(jìn)行區(qū)域合并，將輪廓置信度圖轉(zhuǎn)換成超度量輪廓圖，從而得到更準(zhǔn)確的多層分割圖。實(shí)驗(yàn)表明，本文方法檢測得到的超度量輪廓圖具有較好的視覺邊界感官效果。在定量分析中，本文方法在保證分割性能的前提下大幅提高了檢測效率。本文的多尺度分層分割方法還可用于后續(xù)的高層視覺任務(wù)中，如從分割結(jié)果中提取目標(biāo)候選用于目標(biāo)識別和跟蹤任務(wù)中，并應(yīng)用到具體實(shí)際環(huán)境（如交通監(jiān)控）中。下一步研究重點(diǎn)是提高本分析方法在執(zhí)行目標(biāo)檢測、視頻跟蹤等高層視覺任務(wù)時的魯棒性、高效性和準(zhǔn)確性。

參考文獻(xiàn)參考文獻(xiàn)：

[1] ARBELAEZ P， MAIRE M， FOWLKES C，et al. Contour detection and hierarchical image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（5）： 898916.

[2] 王梅， 李玉鑑， 全笑梅. 圖像分割的圖論方法綜述[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2014， 31（9）： 112.

[3] SHI J， MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（8）： 888905.

[4] SHARON E， GALUN M， SHARON D，et al.Hierarchy and adaptivity in segmenting visual scenes[J]. Nature， 2006， 442（7104）： 810813.

[5] TATLOR C J. Towards fast and accurate segmentation[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Portland， OR， United states： IEEE， 2013： 19161922.

[6] MAIRE M， YU S X. Progressive multigrid eigensolvers for multiscale spectral segmentation[C]. Proceedings of the IEEE Conference on Computer Vision. Sydney， NSW， Australia： IEEE， 2013： 21842191.