徐新黎，邢少恒，王凱棟，許營(yíng)坤，管 秋，王萬良

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)

1 引 言

作為計(jì)算機(jī)視覺任務(wù)中的重要預(yù)處理步驟，Ren等人[1]提出的超像素算法可以把圖像中具有相似亮度、顏色和其他特征的像素聚合成具有一致性、能夠保持一定圖像局部結(jié)構(gòu)特征的子區(qū)域，從而減少后續(xù)處理的基本單元數(shù)目.超像素因其良好的邊界附著性、語義一致性和高效性等特點(diǎn)，并可以有效降低處理對(duì)象規(guī)模和后續(xù)處理的計(jì)算復(fù)雜度，已被廣泛應(yīng)用于圖像分割[2-4]、目標(biāo)檢測(cè)與跟蹤[5-7]、顯著性檢測(cè)[8，9]、光流估計(jì)[10-12]及其他視覺任務(wù)中.

超像素的好壞由邊界附著性、區(qū)域緊致性、形狀規(guī)則性和復(fù)雜環(huán)境適應(yīng)性等特性決定，近年來，為獲取良好表現(xiàn)的超像素，不少超像素算法被提出，根據(jù)其原理的不同可以概括為基于聚類、基于圖和基于深度學(xué)習(xí)3類超像素算法.基于聚類的超像素算法使用不同的聚類算法對(duì)圖像中的像素點(diǎn)進(jìn)行聚類，如簡(jiǎn)單線性迭代聚類SLIC(Simple Linear Iterative Clustering)[13]使用K-means聚類對(duì)像素空間和顏色信息的五維特征表示(XYlab特征)進(jìn)行迭代聚類，因其簡(jiǎn)單有效而被廣泛使用，但迭代過程中SLIC初始保留的一些邊緣可能會(huì)丟失，這也是迭代聚類方法常見的缺點(diǎn).線性譜聚類LSC(Linear Spectral Clustering)[14]算法將像素特征表示映射到十維特征空間再使用K-means聚類，可以有效捕獲全局圖像屬性，但其分割性能仍有提升的空間.簡(jiǎn)單非線性迭代聚類SNIC(Simple Non-Iterative Clustering)[15]在SLIC基礎(chǔ)上改進(jìn)為不需迭代計(jì)算聚類中心點(diǎn).Peng等人[16]使用高階能量函數(shù)來表達(dá)和優(yōu)化K-means聚類得到的超像素的表示，Liu等人[17]提出了流形簡(jiǎn)單線性迭代MSLIC，將像素的五維特征映射成二維流形特征，可以獲得語義敏感的超像素，相較SLIC略微提升了分割質(zhì)量.除了使用K-means聚類，其他聚類方法也被廣泛應(yīng)用于超像素的生成之中，Shen等人[18]使用DBSCAN聚類方法僅根據(jù)像素的顏色特征生成較為規(guī)則超像素，然而邊緣貼合性能表現(xiàn)不佳.能量驅(qū)動(dòng)采樣SEEDS(Superpixels extracted via energy-driven sampling)[19]通過優(yōu)化邊緣項(xiàng)和顏色項(xiàng)組成的目標(biāo)能量函數(shù)來動(dòng)態(tài)地使初始區(qū)域的邊緣不斷逼近圖像邊緣，以生成超像素，其能量函數(shù)需經(jīng)過多次的的優(yōu)化迭代.Zhang等人提出了密度峰值聚類超像素聚類DPCS(Density Peaks Clustering Superpixel)[20]，通過計(jì)算樣本點(diǎn)的密度，距離和決策值來自動(dòng)發(fā)現(xiàn)聚類中心，實(shí)現(xiàn)對(duì)像素的高效聚類，然而沒有挖掘像素信息的深層聯(lián)系和聚類時(shí)的顏色與空間信息的比重，且生成的超像素不能保證一致性與連通性.

基于圖的算法將分割圖像視為以像素為節(jié)點(diǎn)、以像素鄰接關(guān)系為邊的圖結(jié)構(gòu)，使用圖算法為節(jié)點(diǎn)進(jìn)行分類，如規(guī)一化切割算法NC(Normalized Cuts)[21]使用紋理和邊緣信息構(gòu)成能量函數(shù)，通過最小化全局能量函數(shù)生成形狀規(guī)則的超像素，然而其時(shí)間復(fù)雜度為O(N3/2).懶惰隨機(jī)游走算法LRW(Lazy Random Walks)[22]迭代地計(jì)算隨機(jī)游走到已標(biāo)記像素的最大可能性，自適應(yīng)地調(diào)整種子點(diǎn)的位置，熵率算法ERS(Entropy Rate Superpixel)[23]基于隨機(jī)游走的熵率來最大化目標(biāo)函數(shù)，以連接子圖生成邊緣貼合良好的超像素.偽布爾優(yōu)化算法PB(pseudo-boolean optimization)[24]通過去邊算法實(shí)現(xiàn)圖劃分生成超像素，其時(shí)間復(fù)雜度為O(N)，其速度可達(dá)到實(shí)時(shí)性要求，但生成的超像素邊緣貼合度也相對(duì)較低.通常基于圖的超像素算法的時(shí)間復(fù)雜度都比較高.

基于深度學(xué)習(xí)的算法使用卷積神經(jīng)網(wǎng)絡(luò)來預(yù)測(cè)像素的分類以生成超像素，如超像素采樣網(wǎng)絡(luò)SSN(Superpixel Sampling Networks)[25]先使用卷積神經(jīng)網(wǎng)絡(luò)CNN提取像素特征，根據(jù)目標(biāo)超像素?cái)?shù)目生成初始超像素網(wǎng)格，再通過可微SLIC迭代預(yù)測(cè)每個(gè)像素屬于周圍超像素9鄰域區(qū)域的概率作為關(guān)聯(lián)圖，可以端到端地訓(xùn)練整個(gè)網(wǎng)絡(luò)，生成超像素.然而，為了達(dá)到更高的精度，SSN在訓(xùn)練網(wǎng)絡(luò)的過程中，需要使用圖像的邊緣監(jiān)督信息.像素嵌入網(wǎng)絡(luò)SEN(Superpixel Embedding Network)[26]通過U型深度自編碼器提取像素特征，并在特征空間進(jìn)行Mean-Shift聚類來生成超像素，和SSN一樣，SEN同樣要使用有監(jiān)督信息的圖片進(jìn)行模型訓(xùn)練.這類超像素算法需要長(zhǎng)時(shí)間的訓(xùn)練迭代且對(duì)不同類別圖片集不具有廣泛適用性.

目前的超像素算法或存在邊緣疊合度尚可但時(shí)間復(fù)雜度過高、或存在時(shí)間性能優(yōu)異但邊緣貼合度較低的問題.為了快速、高效地生成高質(zhì)量的超像素，更好地提取圖像的局部邊緣特征，受密度峰值聚類DPC[27]和LSC[14]算法啟發(fā)，本文提出一種基于局部最近鄰密度和顏色特征加權(quán)的超像素生成算法NDPCS(Nearest-neighbor Density Peak and Color Feature Weighting to Generate Superpixel).NDPCS基于密度峰值聚類，無需迭代就可生成具有較高邊緣召回率及可達(dá)分割精度的超像素.

2 基于最近鄰密度和顏色加權(quán)的超像素算法

2.1 基于最近鄰的像素點(diǎn)局部密度

密度峰值搜索聚類DPC[27]是近年提出的聚類方法，其主要思想是尋找被低密度區(qū)域分離的高密度區(qū)域.DPC基于以下兩個(gè)假設(shè)：1)聚類中心點(diǎn)的密度大于周圍鄰居點(diǎn)的密度；2)聚類中心點(diǎn)的密度與其他聚類中心點(diǎn)的距離較大.故DPC需要計(jì)算樣本點(diǎn)i的密度ρi和距離δi，密度為到其他樣本點(diǎn)距離小于截?cái)嗑嚯x的點(diǎn)的個(gè)數(shù)：

(1)

其中：

(2)

(3)

dij為樣本點(diǎn)xi和xj的歐式距離，D為樣本點(diǎn)的維數(shù)，dT為設(shè)定的截?cái)嗑嚯x.密度ρi反映了樣本點(diǎn)在dT鄰域內(nèi)的鄰居個(gè)數(shù).距離δi為樣本點(diǎn)到周圍大密度點(diǎn)的最小距離：

(4)

DPC[27]以具有較大決策值的樣本點(diǎn)為聚類中心，并將其余樣本點(diǎn)分配到它的最近鄰且密度比其大的樣本點(diǎn)所在的簇，完成聚類.密度峰值聚類可以很好地適應(yīng)復(fù)雜形狀的樣本數(shù)據(jù)，無需迭代地完成聚類，但聚類結(jié)果受截?cái)嗑嚯x的影響較大，且需要計(jì)算所有樣本點(diǎn)兩兩之間的距離，計(jì)算開銷較大，時(shí)間復(fù)雜度較高.

對(duì)于輸入的彩色圖像I，每一個(gè)像素點(diǎn)的特征可以表示為一個(gè)5維向量pi=[li，ai，bi，xi，yi]T，其中l(wèi)i，ai，bi為像素點(diǎn)的顏色特征，分別表示亮度、綠紅通道和藍(lán)黃通道，xi，yi像素點(diǎn)的橫坐標(biāo)和縱坐標(biāo).基于密度峰值搜索聚類的超像素分割算法DPCS[20]就是使用密度峰值聚類對(duì)像素的五維特征進(jìn)行簡(jiǎn)單聚類.通常，像素點(diǎn)的局部密度反應(yīng)圖像中像素點(diǎn)周圍相近像素的聚集程度.一般聚類數(shù)據(jù)集中，密集區(qū)域點(diǎn)的密度要大于稀疏區(qū)域點(diǎn)的密度，而密集區(qū)域中點(diǎn)到鄰居點(diǎn)的距離和要小于稀疏區(qū)域中點(diǎn)到鄰居點(diǎn)的距離和.但圖像中像素點(diǎn)是規(guī)則均勻排列的，像素點(diǎn)除了位置信息，還有顏色等特征.DPCS[20]算法指出在以像素點(diǎn)為中心的圓形區(qū)域內(nèi)，根據(jù)特征距離定義的像素點(diǎn)局部密度能反映圓形區(qū)域中所有像素在該像素周圍的聚集程度，即周圍聚集的相似像素越多則該像素點(diǎn)密度越大，反之則密度越小，然而DPCS[20]沒有考慮不同類別的鄰居數(shù)目對(duì)其局部密度的影響.

Wang等人[28]對(duì)密度峰值聚類的研究發(fā)現(xiàn)，使用鄰域部分樣本點(diǎn)計(jì)算密度可以改善聚類結(jié)果.為提取圖像的局部邊緣特征并減少計(jì)算復(fù)雜度，本文方法NDPCS采用基于局部最近鄰的密度，即使用像素點(diǎn)鄰域內(nèi)的最近鄰居而非鄰域內(nèi)的所有鄰居來計(jì)算像素的局部密度，從而可以更好地感知圖像邊緣信息，并在像素聚類時(shí)提高邊緣貼合度.因此，定義最近鄰的像素點(diǎn)pi的局部密度ρi為：

(5)

dij=dc(pi，pj)+ds(pi，pj)

(6)

(7)

(8)

式(6)中dc(pi，pj)為像素pi和pj之間顏色分量的相似度，ds(pi，pj)為像素pi和pj之間空間距離.顯然，像素點(diǎn)之間的距離dij越小，兩像素點(diǎn)的顏色和空間信息越接近，即相似度越大.基于最近鄰的像素局部密度(見式(5))與像素點(diǎn)到周圍最近鄰居點(diǎn)的距離和成反比，距離和越小，則代表其周圍同質(zhì)像素越多，即其局部密度越大.

為了提高超像素分割性能，以便更好地發(fā)現(xiàn)圖像的邊緣細(xì)節(jié)，避免將圖像中細(xì)長(zhǎng)形狀的物體邊緣合并到顏色不相似的區(qū)域，受LSC[14]算法啟發(fā)，可以將像素的5維特征表示映射到10維：

pi=[l1i，l2i，a1i，a2i，b1i，b2i，x1i，x2i，y1i，y2i]T

(9)

其映射函數(shù)為：

(11)

其中Cs/Cc=0.075為控制超像素緊致度的默認(rèn)參數(shù).

10維特征表示的像素pi到周圍最近鄰點(diǎn)pj的顏色距離dc和空間距離ds為：

dc(pi，pj)=

(12)

(13)

和5維特征空間相比，圖像中距離較遠(yuǎn)的相似像素在10維特征空間中距離更近.3.3節(jié)對(duì)使用不同維度特征進(jìn)行超像素分割的結(jié)果進(jìn)行了分析對(duì)比.

圖1 不同最近鄰個(gè)數(shù)時(shí)的密度熱力圖Fig.1 Density heat map with different number of nearest neighbors

使用K近鄰的密度峰值算法可以更好地適應(yīng)聚類中的復(fù)雜形狀.但對(duì)于圖像中紋理簡(jiǎn)單、顏色一致的區(qū)域，可能會(huì)出現(xiàn)多個(gè)等值的局部密度最大值點(diǎn).最近鄰數(shù)量K的取值大小會(huì)影響局部密度最大值點(diǎn)的數(shù)量以及密度對(duì)圖像邊緣的檢測(cè)能力.圖1為在尺寸為321×481圖片上取不同K值的密度熱力圖，隨著K值的增大，密度對(duì)于目標(biāo)邊界的邊緣檢測(cè)能力逐漸減弱.

2.2 像素點(diǎn)距離計(jì)算

計(jì)算像素點(diǎn)pi的距離δi，即為pi尋找最近的大密度像素點(diǎn)，根據(jù)其密度是否為局部極值而采用不同的距離計(jì)算策略.對(duì)于非局部密度最大值點(diǎn)pi，其距離為到鄰域內(nèi)最近的大密度像素點(diǎn)的距離：

(14)

Nr為計(jì)算距離時(shí)的鄰域像素點(diǎn)集合.

若pi為局部密度最大值點(diǎn)，則其大密度點(diǎn)也是局部密度最大值點(diǎn)，因此其距離為：

(15)

NL為所有局部密度最大值的像素點(diǎn)集合.

由于圖像中像素在平面空間中是緊密排列的，且圖像中尤其是紋理較簡(jiǎn)單的自然圖像中往往存在大范圍顏色相近區(qū)域(如天空之類的背景部分)，這可能導(dǎo)致很多圖像上相鄰或距離相近的像素點(diǎn)同為局部密度最大值點(diǎn).如果一個(gè)像素點(diǎn)為局部密度最大值點(diǎn)，則按照密度峰值聚類的距離計(jì)算方法，應(yīng)當(dāng)距離其他局部密度最大值點(diǎn)的距離更遠(yuǎn).因此，局部密度最大值點(diǎn)的距離δi為到最近的擁有相等或較大密度的其他局部密度最大值點(diǎn)的距離.

對(duì)圖像的所有像素點(diǎn)的決策值分布進(jìn)行分析可得，擁有局部最大密度的點(diǎn)往往擁有較大決策值λi=ρiδi，少數(shù)幾個(gè)非局部密度最大值點(diǎn)也擁有稍大的決策值，但其個(gè)數(shù)過少，對(duì)分割結(jié)果的影響可以忽略不計(jì)，因此只計(jì)算這些局部密度最大值點(diǎn)的距離是合理的，在不損失分割精度的情況下，NDPCS選擇僅計(jì)算局部密度最大值點(diǎn)的距離，并以此計(jì)算決策值，從中挑選出聚類中心.

2.3 基于決策值和顏色特征加權(quán)的初始超像素生成

根據(jù)局部密度最大值點(diǎn)的密度ρi和距離δi，以決策值λi=ρiδi為參考可以生成初始的超像素.根據(jù)2.2節(jié)的分析，NDPCS僅從局部密度最大值點(diǎn)中選擇聚類中心，具體為將圖中局部密度最大值點(diǎn)的決策值進(jìn)行排序，選取其中的前k個(gè)作為聚類中心Clu={c1，c2，...，ck}，并將其對(duì)應(yīng)的標(biāo)簽記為label={1，2，…，k}.

不同于密度峰值聚類的按簇搜索歸類，考慮到圖像邊緣和像素空間分布，為了更好地使不同類別標(biāo)簽的像素貼近物體的真實(shí)邊緣，NDPCS為每個(gè)非聚類中心像素i尋找距離最近的聚類中心點(diǎn)ci，具體為計(jì)算每個(gè)聚類中心和其周圍鄰域內(nèi)每個(gè)像素的距離，將像素點(diǎn)的類別標(biāo)簽指派為最近聚類中心的類別標(biāo)簽，生成初始超像素：

(16)

其中d(i，ci)為像素點(diǎn)i到聚類中心點(diǎn)ci的距離：

d(i，ci)=α×dc(i，ci)+(1-α)ds(i，ci)

(17)

其中α∈(0，1)為顏色分量權(quán)重.使用顏色特征加權(quán)的距離來計(jì)算像素點(diǎn)同聚類中心點(diǎn)的距離，可以更好地捕獲圖像的語義邊緣.相比不帶加權(quán)的距離計(jì)算，給予顏色特征更高的權(quán)重，可以生成邊緣貼合度更好的超像素，更能適應(yīng)復(fù)雜的形狀，保留圖像中孤立的細(xì)節(jié).

1https://github.com/davidstutz/superpixel-benchmark/

2.4 非連通區(qū)域的啟發(fā)式合并

對(duì)非聚類中心的像素點(diǎn)進(jìn)行類別指派后，因?yàn)橄袼鼐垲惖奶匦?，?huì)出現(xiàn)超像素不連通的情況，即具有同一標(biāo)簽的像素空間上不在同一個(gè)連通域中；此外，因?yàn)閳D像中噪聲點(diǎn)和噪聲區(qū)域的存在，可能生成區(qū)域過小的超像素，而通常希望一個(gè)超像素不應(yīng)過小，超像素內(nèi)部是顏色相似度高且像素是連通的.

d(Si，Sj)=α×dc(u，v)+(1-α)×ds(u，v)

(18)

圖2展示了合并前后的超像素.由圖2可知，以基于顏色特征加權(quán)的合并方式，將過小的超像素子域歸并到與其最相似的鄰域超像素中，從而可以將在聚類過程中因?yàn)榫嚯x限制造成的同一語義部分割裂開的區(qū)域進(jìn)行合并，保證了超像素之間的像素連通性，并且盡可能保留了物體的邊緣.

圖2 超像素的合并Fig.2 Superpixel merging

2.5 算法復(fù)雜度分析

綜上，NDPCS算法總的時(shí)間復(fù)雜度為O(((2r-1)2+k)N+m2)，其中m2和N約為一個(gè)數(shù)量級(jí)，而r和k遠(yuǎn)小于N，因此，NDPCS算法的時(shí)間復(fù)雜度可以簡(jiǎn)化為O(N).NDPCS算法在計(jì)算過程中只需存儲(chǔ)大小為N的局部密度、m個(gè)局部密度最大值點(diǎn)的距離和決策值以及k個(gè)超像素的最大距離和N個(gè)像素的標(biāo)簽，因此其空間復(fù)雜度為O(N).

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

3.1 數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)以Berkeley數(shù)據(jù)集BSDS500[29]為驗(yàn)證數(shù)據(jù)集，BSDS500包含500張尺寸為321×481或481×321的自然圖片，每張圖片由至少5個(gè)不同的標(biāo)注人員進(jìn)行自然物體邊緣的標(biāo)注.

所有算法均運(yùn)行在CPU為Intel Corei7-8700(3.2GHz)、RAM為16G的計(jì)算機(jī)上，其中DPCS[20]由于沒有公開的源代碼，采用的是C++復(fù)現(xiàn)的版本，SLIC[13]、LSC[14]、ERS[23]和PB[24]使用David等[30]關(guān)于超像素的研究綜述中提供的代碼1，David 等以C++實(shí)現(xiàn)了部分超像素的算法并提供了調(diào)用接口，SEEDS[19]算法使用OpenCV的實(shí)現(xiàn)版本，該版本在不改變分割精度的情況下，運(yùn)行時(shí)間更短，所有算法參數(shù)均使用原文中最優(yōu)表現(xiàn)的參數(shù)，且沒有特別設(shè)計(jì)的GPU加速計(jì)算與并行計(jì)算.

3.2 超像素結(jié)果對(duì)比

圖3展示了NDPCS算法和其他6種算法(SLIC[13]、LSC[14]、SEEDS[19]、ERS[23]、PB[24]和DPCS[20])超像素?cái)?shù)目分別為300和800時(shí)在部分?jǐn)?shù)據(jù)集上的可視化分割結(jié)果，其中每張圖左側(cè)為原圖分割結(jié)果，右側(cè)為局部區(qū)域的細(xì)節(jié)放大圖，“NDPCS_5d”指NDPCS在5維特征空間中的超像素結(jié)果，“NDPCS_10d”指NDPCS在10維特征空間中的超像素結(jié)果.

圖3 不同超像素算法在部分圖片上的分割結(jié)果Fig.3 Segmentation results of different superpixel algorithms

從圖3中可以看出，SLIC[13]、LSC[14]以及PB[24]生成的超像素大小比較均勻，這是因?yàn)镾LIC和LSC都以均勻步長(zhǎng)初始化超像素種子.其余算法均為在全局像素中或挑選聚類中心，或調(diào)整初始邊緣，無法保證超像素的在圖像坐標(biāo)空間上的均勻性.通過比較細(xì)節(jié)發(fā)現(xiàn)，同樣使用5維CIELab信息進(jìn)行聚類，相較于使用K-means聚類的SLIC，使用密度峰值聚類的DPCS[20]和NDPCS_5d生成的超像素明顯可以更好地好貼合物體邊緣.而同樣使用10維特征信息聚類，相較于LSC[14]，NDPCS_10d生成的超像素對(duì)物體邊緣尤其是細(xì)長(zhǎng)形狀的邊緣更加敏感，更貼合自然認(rèn)知.

3.3 性能比對(duì)分析

本文采用邊緣召回率BR(Boundary Recall)[30]、欠分割誤差UE(Under-segmentation Error)[13]和可達(dá)分割精度ASA(Achievable Segmentation Accuracy)[19]這3個(gè)反映邊緣貼合能力的指標(biāo)，以及反映超像素內(nèi)部像素同一性的內(nèi)部聚類差異ICV(Intra-Cluster Variation)[30]來對(duì)超像素分割結(jié)果進(jìn)行評(píng)價(jià).

邊緣召回率BR是超像素分割最常用的指標(biāo)之一，描述了超像素邊緣S落在真實(shí)邊緣G的能力，BR越大，則分割出的超像素邊界與實(shí)際的真值標(biāo)注邊界越接近：

(19)

其中TP(S，G)為與超像素邊緣S距離不大于ε的真實(shí)邊緣G的像素個(gè)數(shù)，F(xiàn)N(S，G)為與超像素邊緣S距離大于ε的真實(shí)邊緣G的像素個(gè)數(shù).

欠分割誤差UE是測(cè)量超像素與自然物體超出重疊的標(biāo)準(zhǔn).一個(gè)好的超像素算法分割出的超像素，應(yīng)當(dāng)盡可能少地“跨越”真值標(biāo)簽中不同的區(qū)域，并鼓勵(lì)超像素更多地與自然物體重疊并減少非重疊部分.假設(shè)超像素分割的結(jié)果為S={s1，s2，…，sk}，圖片的真值標(biāo)簽為G={g1，g2，...，gl}，則欠分割誤差UE可以表示為：

(20)

可達(dá)分割精度ASA量化了超像素分割作為計(jì)算機(jī)視覺的預(yù)處理步驟，可以在后續(xù)任務(wù)(例如圖像分割)中能夠達(dá)到的最大精度，是超像素中可用于分割的部分與總像素的比值，其公式見式(21).在以超像素為基礎(chǔ)的下游任務(wù)中，希望超像素分割對(duì)下游任務(wù)的影響盡可能小，即希望可達(dá)分割精度較高.

(21)

內(nèi)部聚類差異ICV反映了超像素內(nèi)部像素點(diǎn)和超像素整體的差異.該指標(biāo)不依賴于真值標(biāo)簽，可以由超像素分割結(jié)果和原圖片計(jì)算得到.

(22)

其中I(xn)為超像素Sj內(nèi)單個(gè)像素的顏色，μ(Sj)為Sj的平均顏色.ICV越低，表示超像素內(nèi)部像素顏色越趨近于統(tǒng)一，即超像素分割質(zhì)量越高.

由于聚類生成超像素存在一定程度的不連通性，SLIC、LSC和NDPCS均需要通過超像素合并來保證每個(gè)超像素的像素彼此連通，故這幾種方法不能確定最終超像素的數(shù)目，合并后實(shí)際的超像素?cái)?shù)目相比預(yù)期設(shè)定的數(shù)目有輕微波動(dòng)，例如設(shè)定超像素?cái)?shù)目300，實(shí)際生成300±30個(gè)超像素，實(shí)驗(yàn)表明，合并造成的超像素?cái)?shù)目誤差值不影響算法之間的性能和精度對(duì)比.

圖4展示了NDPCS和6種流行算法的性能對(duì)比.NDPCS算法設(shè)置參數(shù)K=10、α=0.7.如圖4所示，NDPCS優(yōu)于在3個(gè)評(píng)價(jià)指標(biāo)上SLIC[13]、LSC[14]、ERS[23]、DPCS[20]、PB[24]等算法，這得益于最近鄰密度對(duì)邊緣檢測(cè)的貢獻(xiàn)、聚類時(shí)利用決策值對(duì)密度的選取.隨著超像素?cái)?shù)目的增加，NDPCS在邊緣召回率上的指標(biāo)仍保持領(lǐng)先，說明在使用相同數(shù)據(jù)的情況下使用局部最近鄰密度和顏色加權(quán)聚類的NDPCS可以提升像素聚類結(jié)果的性能，尤其是可以提高圖像中物體邊緣的檢測(cè)和感知能力.在反映超像素內(nèi)部顏色差異性的指標(biāo)ICV上，10維特征表示的NDPCS算法在超像素?cái)?shù)目大于200時(shí)低于所對(duì)比算法，這是由于合并時(shí)超像素之間的顏色特征加權(quán)的相似度對(duì)合并的指導(dǎo)作用，給予顏色更大的權(quán)重有利于將相似顏色的像素聚為一類.

圖4 不同超像素算法在BSDS500上的性能表現(xiàn)Fig.4 Performance of different superpixel algorithms on BSDS500

3.4 參數(shù)選擇分析

對(duì)于NDPCS算法，分別以CIELAB顏色空間的5維向量和映射到譜空間中的10維向量來表示像素特征，并選擇最近鄰居個(gè)數(shù)K和顏色分量權(quán)重α的不同取值來分析對(duì)超像素生成結(jié)果的影響.

圖5為超像素?cái)?shù)目為300時(shí)，不同參數(shù)對(duì)邊緣召回率的影響.從圖5可以得出，NDPCS在最近鄰居個(gè)數(shù)K=10時(shí)，邊緣召回率取得最大值，隨著K的增加，邊緣召回率變化較小，這是因?yàn)镵過小不足以反應(yīng)像素點(diǎn)的聚集程度，而K過大則會(huì)弱化密度對(duì)邊緣的檢測(cè)能力，實(shí)驗(yàn)中取K=10.另外隨著顏色分量權(quán)重α的變大，NDPCS在5維和10維空間分割的準(zhǔn)確度都有顯著提升，這是由于α越大，聚類時(shí)越無視空間信息，生成的超像素邊緣越貼合真實(shí)圖像的邊緣，但會(huì)導(dǎo)致超像素的形狀不規(guī)整，在未合并時(shí)孤立的超像素?cái)?shù)目變多，增加算法時(shí)間消耗，為平衡時(shí)間與精度，實(shí)驗(yàn)中取α=0.7.

圖5 不同參數(shù)下的邊緣召回率Fig.5 Boundary recall under different parameters

3.5 時(shí)間性能分析

表1對(duì)7種不同的超像素算法的時(shí)間復(fù)雜度進(jìn)行了比較，其中n為算法迭代次數(shù)，N為分割圖像中的總像素?cái)?shù).其中基于聚類的算法SLIC[13]、LSC[14]、PB[24]、DPCS[20]和NDPCS的時(shí)間復(fù)雜度都為O(N)，而基于圖的算法ERS[23]時(shí)間復(fù)雜度要高出許多，這是因?yàn)镋RS[23]將每個(gè)像素視為一個(gè)節(jié)點(diǎn)，且要計(jì)算任意兩兩像素間的距離，而SEEDS[19]算法由于顏色直方圖的劃分可以調(diào)整，尚無理論的時(shí)間復(fù)雜度.

表1 各算法時(shí)間復(fù)雜度Table 1 Time complexity of each algorithm

圖6展示了各算法在不同尺度圖像下的運(yùn)行時(shí)間，其中ERS隨著圖像大小增加時(shí)間急速上升，這是因?yàn)镋RS[23]是基于圖論的算法，考慮每?jī)蓚€(gè)節(jié)點(diǎn)之間的距離，故其運(yùn)行時(shí)間受圖像尺寸影響較大；SLIC[13]算法因?yàn)楹?jiǎn)單的合并策略，比同樣使用K-means算法的LSC[14]要快；DPCS[20]算法較NDPCS算法快，這是因?yàn)槠溆?jì)算距離時(shí)就已計(jì)算好像素點(diǎn)的歸類.NDPCS與LSC[14]時(shí)長(zhǎng)相當(dāng)，因?yàn)樵谡业骄垲愔行暮笃錃w類與合并的復(fù)雜度相同，這里的LSC[14]是使用同NDPCS相同的合并策略，故較原論文時(shí)間稍有增加，但同時(shí)也增加了邊緣召回率等精度.PB[24]采用去邊算法實(shí)現(xiàn)圖劃分，在圖像尺寸較小時(shí)近乎可以實(shí)時(shí)分割.從圖6和圖4可以看出，對(duì)比以上幾種流行的非深度學(xué)習(xí)方法，NDPCS在犧牲較少時(shí)間性能的情況下，取得了最優(yōu)的超像素分割結(jié)果.

圖6 各算法運(yùn)行時(shí)間Fig.6 Running time of each algorithm

4 結(jié) 論

本文提出的基于局部最近鄰密度和顏色特征加權(quán)的超像素生成算法NDPCS可以更好地提取圖像的局部邊緣特征.NDPCS首先在像素點(diǎn)的鄰域范圍內(nèi)用最近鄰居像素計(jì)算其局部密度，其次根據(jù)局部密度計(jì)算局部密度最大值點(diǎn)的決策值大小選擇期望數(shù)目的像素作為超像素的種子，并且為每個(gè)像素以顏色特征加權(quán)的距離最小為依據(jù)尋找聚類中心，最后通過超像素大小和顏色特征加權(quán)相似度相結(jié)合的啟發(fā)式策略合并孤立和過小超像素以保證超像素的連通性，實(shí)現(xiàn)超像素分割.NDPCS與6種經(jīng)典或最新的超像素分割算法進(jìn)行了對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明NDPCS在邊緣召回率、欠分割誤差和可達(dá)分割精度上優(yōu)于其它大多算法，運(yùn)算速度較快，在存儲(chǔ)復(fù)雜性方面也有一定優(yōu)勢(shì).但NDPCS同其他聚類方法一樣，不能精確生成超像素的數(shù)目，因此如何在不損失精度的情況下選擇新的合并策略以確保超像素的數(shù)目，以及如何使用并行計(jì)算來進(jìn)一步提高算法的運(yùn)行時(shí)間，是后續(xù)有待進(jìn)一步研究的問題.