（西華大學(xué)無線電管理技術(shù)研究中心，四川 成都 610039）

超像素分割作為圖像處理的主要手段，已在大量的計(jì)算機(jī)視覺中得到廣泛應(yīng)用，例如對象跟蹤[1]、語義分割[2]、圖像理解[3]等。作為視覺算法的前端處理，超像素分割有3 個(gè)主要的性能需求：1）分割有效性，即分割區(qū)域需要盡可能準(zhǔn)確貼合對象的邊界；2）計(jì)算有效性，即處理時(shí)間盡可能短；3）區(qū)域緊致性，即形狀盡可能規(guī)則。

已有的超像素分割方法一般分為2 類：基于聚類的超像素分割、基于圖論優(yōu)化的超像素分割。前者首先初始化聚類中心，然后加入聚類元素并更新中心，逐步迭代直到收斂，如TuberPixels(TP)[4]、simple linear iterative clustering(SLIC)[5]。然而這類方法基于顏色空間的歐式距離計(jì)算像素相似性，導(dǎo)致模糊對象邊界及復(fù)雜紋理區(qū)域分割邊界貼合度低。后者將圖像鄰接像素構(gòu)建為圖結(jié)構(gòu)，采用圖論優(yōu)化方法獲得緊致貼合的分割邊界。該類方法聚焦鄰接像素的相似關(guān)系，忽略了像素與種子點(diǎn)的位置關(guān)系，導(dǎo)致分割區(qū)域缺乏規(guī)則性與緊致性。上述2 類方法或采用基于迭代更新的優(yōu)化策略或采用基于復(fù)雜的圖理論優(yōu)化方法，導(dǎo)致分割時(shí)間耗費(fèi)較多。

針對以上問題，本文提出一種基于最小柵欄距離的快速超像素分割方法。直觀上，像素到種子中心的距離由其最短路徑上的最大顏色強(qiáng)度差異決定。一方面，最大顏色差異的計(jì)算避免了傳統(tǒng)測地距離像素誤差累積的問題；另一方面，最小柵欄距離的計(jì)算更多的只需要采用像素強(qiáng)度值大小，提高了計(jì)算效率。另外，本文采用優(yōu)先隊(duì)列實(shí)現(xiàn)像素的線性訪問，獲得了O(n)的線性時(shí)間復(fù)雜度。在BSDS500 圖像分割數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對比，驗(yàn)證了本文方法相比現(xiàn)有主流方法的優(yōu)越性。

1 超像素分割算法

超像素分割方法一般可分為2 類：基于聚類的方法和基于圖論的方法。

1.1 基于聚類的超像素分割算法

基于聚類的算法首先初始化超像素中心點(diǎn)，然后逐步采用添加類別像素成員的方式擴(kuò)張超像素區(qū)域，并通過多次迭代達(dá)到收斂。例如，TP[4]方法初始化種子點(diǎn)并擴(kuò)張超像素的邊界直到梯度最大的邊界。由于引入了基于水平集的曲率代價(jià)項(xiàng)以維持區(qū)域的規(guī)則性，所以不規(guī)則對象及復(fù)雜背景下的分割性能較低。Achanta 等[5]提出了基于快速K-means[6]算法的SLIC，通過約束聚類中心的搜索空間，獲得了快速的分割性能，同時(shí)能生成均勻、緊致的超像素區(qū)域。SNIC[7]采用非迭代的架構(gòu)增強(qiáng)區(qū)域的連通性，克服了SLIC[5]中潛在的區(qū)域不連通的問題。LSC[8]將特征分解與K-means 算法融合，得到了全局感知一致性的超像素分割。為了更準(zhǔn)確逼近圖像的特征本質(zhì)，Ye 等[9]提出了基于查詢的測地距離的超像素分割方法，它在高維空間上計(jì)算測地距離，更好地刻畫了自然圖像流形空間的像素相似性，然而由于其復(fù)雜的高維特征計(jì)算，所以其計(jì)算復(fù)雜度過高。為了適用于深度學(xué)習(xí)的視覺應(yīng)用，Jampani 等[10]及Yang 等[11]分別提出了基于深度學(xué)習(xí)的超像素分割算法。前者[10]采用深度卷積網(wǎng)絡(luò)提取像素的卷積特征，再用后續(xù)的迭代聚類算法獲得超像素分割結(jié)果。后者[11]采用全卷積網(wǎng)絡(luò)[12]直接預(yù)測像素的超像素標(biāo)簽，避免了迭代運(yùn)算，提高了計(jì)算效率。然而它們均需要GPU進(jìn)行特征計(jì)算，限制了其方法的適用性。

1.2 基于圖論的超像素分割算法

基于圖論的算法是將圖像像素構(gòu)建為圖結(jié)構(gòu)并將圖像分割問題構(gòu)建為最小代價(jià)的割邊尋優(yōu)問題。例如，Shi 等[13]提出采用normalized cuts（NC）來平衡不同分割區(qū)域的面積大小，從而保證分割區(qū)域的規(guī)則性。然而高維度的矩陣分解將導(dǎo)致計(jì)算有效性隨著圖像尺度的增加急劇下降。Felzenszwalb等[14]提出了基于圖的圖像分割（graph-based image segmentation），它基于分割區(qū)域內(nèi)部的最小類間差異來構(gòu)建最小生成子樹，以此作為最終的超像素區(qū)域，其運(yùn)算速度較快，超像素的邊界貼合度高，但由于缺乏種子點(diǎn)定位，所以分割區(qū)域不規(guī)則，同時(shí)由于采用最小類間差異及最大類內(nèi)差異，所以弱邊界及復(fù)雜噪聲背景下的分割邊界貼合度低。Liu 等[15]提出的entropy rate superpixel（ERS）同樣將圖像像素構(gòu)建為圖上隨機(jī)的熵率和平衡項(xiàng)2 個(gè)部分組成的目標(biāo)函數(shù)，熵率部分使得超像素的結(jié)構(gòu)均勻且緊湊，平衡項(xiàng)使得超像素具有相差不大的像素個(gè)數(shù)。然而該算法的運(yùn)算復(fù)雜度較高，限制了其作為預(yù)處理算法的實(shí)時(shí)性應(yīng)用。RPS[16]通過構(gòu)造對象邊界點(diǎn)的最小代價(jià)邊來獲得超像素邊界，獲得了規(guī)則區(qū)域的超像素分割區(qū)域，但是由于其采用水平垂直約束，因此分割精度下降。

基于聚類方法的超像素分割采用歐式距離構(gòu)建像素相似性測量，容易在模糊邊界處產(chǎn)生較高的分割誤差。基于圖論的方法采用測地距離以構(gòu)建像素對之間的相似性，容易導(dǎo)致路徑上的誤差累積，使得噪聲背景下分割性能降低。本文提出的采用最小柵欄距離的方法，不僅具有測地距離的最短路徑優(yōu)勢，克服傳統(tǒng)測地距離的誤差累積的缺點(diǎn)，而且能更多地使用邏輯比較運(yùn)算，避免了大量的乘除運(yùn)算，提高了運(yùn)算效率。

2 基于最小柵欄距離的超像素分割

針對傳統(tǒng)測地距離容易產(chǎn)生誤差累積、計(jì)算效率低的問題，本文提出了一種最小柵欄超像素分割算法。首先介紹了最小柵欄距離的定義，然后提出了基于快速行軍法計(jì)算柵欄距離的O(n)線性時(shí)間復(fù)雜度的最優(yōu)化方法。

2.1 最小柵欄距離

最小柵欄距離（minimum barrier distance，MBD）用來測量圖像像素p到種子點(diǎn)集合S的最小測地距離，它被廣泛用來表征像素與圖像邊界的連通性[17－18]。給定灰度圖像I,定義像素p到某個(gè)種子點(diǎn)sk的路徑為P=[p1,p2,···,pn]，其中pi－1與pi相互鄰接構(gòu)成一條連續(xù)路徑，則最小柵欄測地距離表達(dá)為像素到種子點(diǎn)集合的所有路徑集合中的最短路徑。具體地，定義最小柵欄測地距離為

式中，p(0)=t，p(n)=sk。因而，點(diǎn)p到sk的最小柵欄測地距離表示從所有p到sk的候選路徑中選擇路徑上強(qiáng)度差異最小的路徑。給定種子像素集S=[s1,s2,···,sK]，像素p到種子集合S的最小柵欄測地距離為

式中p(n)屬于S，表示為選擇從像素t到所有種子集合S的路徑集合中一條最小柵欄距離的測地路徑。

由于單通道的灰度圖像不能很好地體現(xiàn)對象與背景的邊界差異，因而定義彩色圖像上的最小柵欄距離，為

式中c∈C，為圖像I通道RGB 中的一個(gè)。

2.2 線性復(fù)雜度的超像素分割優(yōu)化算法

MBD 距離計(jì)算的優(yōu)勢在于降低了大量的乘法和平方運(yùn)算，從而提高了訪問中單次像素的計(jì)算速度。同時(shí)，為了獲得線性時(shí)間復(fù)雜度，需要把對圖像像素訪問和操作的次數(shù)降低到線性次數(shù)O(n)。這里采用快速行軍法（fast marching）[19]逐步擴(kuò)張超像素成員，對像素采用單次掃描以快速生成超像素分割區(qū)域。給定基于規(guī)則網(wǎng)格采樣的初始種子點(diǎn)S=[s1,s2,···,sK]，采用優(yōu)先隊(duì)列Q，實(shí)現(xiàn)返回當(dāng)前訪問下最小柵欄距離的最小成員。另外，采用2 個(gè)向量U及L來存儲當(dāng)前路徑下像素i到種子k的最大強(qiáng)度及最小強(qiáng)度。

式中：C是通道數(shù)；D(p)記錄當(dāng)前像素p到種子點(diǎn)集S的最小柵欄距離。算法流程如圖1 所示。其中，ck=I(p)為RGB 顏色特征，xk為空間位置xy的坐標(biāo)值。另外，采用向量Lab記錄p在最小柵欄距離下對應(yīng)的種子點(diǎn)標(biāo)簽。

圖1 基于最小柵欄距離的圖像超像素分割方法

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

本文采用MATLAB 平臺在數(shù)據(jù)集BSDS500上進(jìn)行實(shí)驗(yàn)驗(yàn)證。與當(dāng)前的主流方法進(jìn)行實(shí)驗(yàn)對比，并 在achievable segmentation accuracy (ASA)、boundary recall (BR)、undersegmentation error (UE)以及運(yùn)行時(shí)間等客觀量化指標(biāo)上進(jìn)行評估。當(dāng)前的主流方法包括：NC[13]、linear spectral clustering(LSC)[8]、SLIC[5]、TP[4]、FH[14]、regularity preserved superpixels (RPS)[16]等。

表1 給出了不同方法在100 塊超像素分割下的客觀評價(jià)指標(biāo)。在性能指標(biāo)方面，ASA、BR 是越高越好，UE、Time 是越低越好?？梢姡琇SC[8]、SLIC[5]獲得了前2 名的分割性能，這是因?yàn)樗鼈兙捎玫鷥?yōu)化框架對超像素中心進(jìn)行更新使得能量值更低，從而獲得了更好的分割性能。與LSC 相比，本文方法（MBD）在3 個(gè)指標(biāo)上都接近于LSC 方法，同時(shí)在運(yùn)行時(shí)間上，MBD 獲得了最少運(yùn)行時(shí)間。在ASA、BR 及UE 方面，MBD 明顯優(yōu)于TP[4]、RPS[16]。這是由于：TP[4]采用曲率規(guī)則項(xiàng)約束分割區(qū)域的緊致性從而造成分割邊界貼合度低；RPS[16]采用了垂直水平邊界交叉點(diǎn)的最短路徑連線，約束了其不規(guī)則形狀的分割性能。一方面，MBD 由于采用了基于MBD 的距離測度，導(dǎo)致優(yōu)化過程中無法隨意改動中心，因此限制了其分割邊界貼合度的精確性；另一方面，MBD 避免了其他方法采用的多次迭代直到收斂的優(yōu)化方式，提高了運(yùn)算效率，因此執(zhí)行時(shí)間比其他方法更短。

表1 不同算法在100 塊超像素下的分割性能指標(biāo)

圖2 示出了不同方法在100 塊超像素分割區(qū)域下的一些主觀結(jié)果。圖2 中每個(gè)子圖從上向下依次排序?yàn)榈? 幅圖、第2 幅圖、第3 幅圖、第4 幅圖?？梢钥闯觯疚姆椒ú粌H獲得了高的邊界貼合度，同時(shí)獲得了規(guī)則緊致的分割區(qū)域，驗(yàn)證了本文方法的有效性。例如：第1 幅圖中，相比其他方法，MBD 完整地分割了地面的道路區(qū)域；第2 幅圖中，MBD、FH[14]、LSC[8]和ERS[15]能夠分割出支架；第3 幅圖中，MBD 能夠精確完整地分割出太陽，相反，其他大多數(shù)方法未有效分割出太陽；第4 幅圖中，MBD 準(zhǔn)確地分割出了沙發(fā)的邊緣。綜上所述，本文方法對于具有較強(qiáng)結(jié)構(gòu)性的目標(biāo)區(qū)域有較好的分割性能。這是由于采用了基于最小柵欄距離能有效區(qū)分相同顏色目標(biāo)的邊界結(jié)構(gòu)信息，而基于歐式空間距離的分割方法無法檢測到結(jié)構(gòu)邊界，因而降低了分割性能。圖中還可以看出，F(xiàn)H[14]、LSC[8]、ERS[15]能夠較好地貼合對象邊緣，但是得到的分割區(qū)域缺乏規(guī)則性，而本文方法不僅可以獲得相對高的邊緣貼合度，還保持了較強(qiáng)的區(qū)域規(guī)則性。

圖2 分割結(jié)果

4 結(jié)論

本文針對區(qū)域規(guī)則性及分割有效性問題對圖像超像素分割方法進(jìn)行了研究，提出了一種基于最小柵欄距離的超像素分割方法，避免了傳統(tǒng)測地路徑的誤差累積造成的模糊邊界欠分割問題。另一方面，本文提出了一種基于快速行軍法的線性復(fù)雜度分割算法，采用該算法能快速有效地獲得具有聯(lián)通一致性的超像素區(qū)域。