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

童昊浩　吳克偉

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

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

DOIDOI：10.11907/rjdk.151428

中圖分類號(hào)：TP317.4

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

0 引言

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

近年來，圖論（Graph Theory）是研究分割的一個(gè)熱點(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ù)：使用一個(gè)簡(jiǎn)單的分水嶺過分割用以減少特征向量大小問題，其不足之處是提高計(jì)算效率的同時(shí)犧牲了目標(biāo)準(zhǔn)確度。Maire 和Yu[6]提出了一種新型的多網(wǎng)格求解器，用于產(chǎn)生多尺度空間特征向量，利用粗糙尺度的解加速精細(xì)尺度的特征向量計(jì)算。

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

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

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

1.1 降采樣歸一化割

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

本文采用利用多尺度性質(zhì)技術(shù)以有效得到近似解。定義pixel_decimate（A），表示關(guān)聯(lián)矩陣中對(duì)應(yīng)降采樣圖像的行列索引，也就是說，如果i=pixel_decimate（A），則A[i，i]{JP是一個(gè)降采樣矩陣，對(duì)應(yīng)圖像的行和列交替去除。由于像素大量減少，計(jì)算A[i，i]的特征向量效果并不理想，但是計(jì)算降采樣的平方關(guān)聯(lián)矩陣A2[i，i]的特征向量是和A的特征向量相似的。因?yàn)樵诮挡蓸又埃椒疥P(guān)聯(lián)矩陣A2[i，i]使得每個(gè)像素的信息都傳播到了其領(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及其對(duì)應(yīng)的K個(gè)最小特征向量，并重新升采樣這些特征向量。

1.2 輪廓全局推斷

輪廓全局推斷的關(guān)鍵在于使用從歸一化割中獲得的特征向量。文獻(xiàn)[1]展示的是目前世界領(lǐng)先的局部輪廓檢測(cè)器之一，將其輪廓檢測(cè)結(jié)果lE作為譜圖劃分的輸入，使用輪廓中間線索，即兩像素連接線間的置信度最大值，建立稀疏對(duì)稱仿射矩陣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，對(duì)應(yīng)于n+1最小特征值λ（實(shí)驗(yàn)中取n=5）。觀察到特征向量本身攜帶了全局輪廓信息（見圖1）。視每個(gè)特征向量vk為一幅圖像，將其與高斯方向?qū)?shù)濾波器在多個(gè)方向θ上卷積，獲得定向信號(hào)θvk（x，y）。來自不同特征向量的信息提供給輪廓檢測(cè)器的譜成分，并在方向上取最大值作為譜信號(hào)：

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

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

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

2 多尺度分層分割

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

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

2.1 層級(jí)校準(zhǔn)

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

則R投影至S上

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

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

2.2 多尺度層級(jí)

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

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

實(shí)驗(yàn)采用的數(shù)據(jù)集為Carnegie Mellon University的輪廓檢測(cè)和分割數(shù)據(jù)集[10]。對(duì)于分割算法，其評(píng)價(jià)策略多種多樣。多種基于區(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)閾值時(shí)的最優(yōu)分割圖。從整體上看，gEucm的超度量輪廓圖與gpbucm的超度量輪廓圖相比，具有更好的視覺輪廓感官效果，分割塊對(duì)應(yīng)目標(biāo)更準(zhǔn)確，并且運(yùn)動(dòng)目標(biāo)邊緣更加顯著，更加貼近于數(shù)據(jù)集中的手工標(biāo)記輪廓。

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

除了考察gEucm的綜合性能外，本文還對(duì)gEucm和gpbucm的檢測(cè)效率進(jìn)行了測(cè)算。表2顯示的是兩者在單幅圖像上（640x480）的平均檢測(cè)時(shí)間。可以看出本文方法由于在降采樣歸一化割過程中，特征向量計(jì)算時(shí)間比傳統(tǒng)歸一化割方法快了20倍，使得在整體檢測(cè)效率上有了較大提升。實(shí)驗(yàn)表明，本文方法在保證分割性能的前提下大幅提高了檢測(cè)效率。

4 結(jié)語

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