童昊浩 吳克偉
摘要:圖像分割作為計(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.