畢業(yè)設計外文資料翻譯-與其他先進超像素方法相比較的SLIC超像素算法

1、畢業(yè)設計外文資料翻譯學 院： 專業(yè)班級： 學生姓名： 學 號： 指導教師： 外文出處： The IEEE Computer Society 附 件：1. HYPERLINK l _Java技術介紹 外文資料翻譯譯文； 2. HYPERLINK l _Java_Technical_Description 外文原文 指導教師評語： 該英文資料選擇合理，專業(yè)術語、詞匯翻譯準確度較高，體現(xiàn)了一定的英語應用水平。翻譯工作認真細致，嚴格按照規(guī)定，翻譯材料能與原文保持一致，能正確的表達出原文的意思，希望能夠將細節(jié)部分處理得更加得當。簽名： 2015 年 10 月 14 日 外文資料翻譯譯文 與其他先進超像素

2、方法相比較的SLIC超像素算法摘 要近年來，計算機視覺應用已經(jīng)開始越來越依靠超像素，但它并不總是很明確什么是好的超像素算法。在努力了解現(xiàn)有方法的優(yōu)點和缺點后，我們根據(jù)經(jīng)驗，從圖像邊緣的附著力、速度、存儲效率以及分割能力的影響方面對五種最先進的超像素算法進行比較。接著，我們引入一種新的，能夠自適應K-均值聚類方法來產(chǎn)生超像素的超像素算法，簡單的線性迭代聚類（SLIC）。盡管簡單，SLIC附著邊界的能力甚至超過了之前的方法。同時，SLIC更快，提高分割性能，存儲效率更高，并且直接延伸到超像素生成?！娟P鍵詞】超像素，分割，聚類，k均值1.概述超像素算法像素組成感知上有意義的微粒區(qū)可用于替換像素柵格的

3、剛性結構。他們捕捉冗余的圖像，提供從一個方便的原始計算圖像特征，并大大降低了后續(xù)的圖像處理任務的復雜性。他們已經(jīng)成為許多計算機視覺算法關鍵構建模塊，如得分最高的多類目標分割項，比如PASCAL VOC挑戰(zhàn)，深度估計，分割，人體模型估計，和對象定位。有許多方法來產(chǎn)生超像素，雖然每一個都有各自的優(yōu)點和缺點，但是也可能更適合于一個特定的應用。例如，如果遵守圖像邊界是非常重要的，對基于圖的方法8可以是一個理想的選擇。然而，如果超像素是被用來建立的曲線圖，產(chǎn)生一個更規(guī)則晶格的方法，可能是一個更好的選擇。雖然這是很難界定什么是所有應用的理想方法，我們認為以下屬性通常是需要的：1.超像素應該很好地附著圖像邊

4、界；2.當作為預處理步驟而用于降低計算復雜度時，超像素應該有高效的計算和存儲效率，并易于使用；3.當用于分割時，超像素應該增加速度并且改善的結果的質量。因此，我們進行的最先進的五種的經(jīng)驗比較超像素方法，評估他們的速度，附著圖像邊界的能力，和影響力分割性能。我們還提供了這些定性審查，以及其他超像素方法。我們的結論是，沒有現(xiàn)有的方法在各個方面都令人滿意。為了解決這個問題，我們提出了一種新的算法超像素：簡單的線性迭代算法（SLIC），它適應K-均值聚類，類似于的方式來產(chǎn)生超像素。雖然方法十分簡單，但是在使用PASCAL和MSRC數(shù)據(jù)集分割時，SLIC在保持圖像邊界方面世界領先，并優(yōu)于現(xiàn)有的方法。此外

5、，它比現(xiàn)有方法更快和更存儲器高效。除了這些可量化的好處，SLIC是易于使用，在該緊湊提供了靈活性和它產(chǎn)生的超像素的數(shù)目，是直接延伸到更高維度，并且是免費提供的。2.現(xiàn)有的超像素方法用于產(chǎn)生超像素算法可大致歸類為圖形或基于梯度上升的方法。下面，我們查看每一個類別的流行超像素方法，包括原本不是專為超像素生成一些。2.1.基于圖論的算法基于圖論的方法來產(chǎn)生超像素，就是將圖中的每個像素當成一個節(jié)點。兩個節(jié)點之間的邊緣的權重與相鄰像素之間的相似點成比例。超像素是通過最小化在圖中定義的成本函數(shù)創(chuàng)建的。NC05歸一化的削減算法遞歸分割使用輪廓和紋理的線索，全局最小化對在分區(qū)邊界處的邊緣限定的成本函數(shù)的圖像中

6、的所有像素的曲線圖。它產(chǎn)生非常有規(guī)律，視覺愉悅超像素。然而，NC05的邊界粘附相對較差，這是上述方法（特別是對大型的圖像）中最慢的，雖然存在企圖加速的算法。 NC05的復雜度是O( QUOTE ) ，其中N是像素的數(shù)量.GS04。Felzenszwalb和Huttenlocher提出一種已經(jīng)被應用到生成超像素替代基于圖形的方法。它執(zhí)行像素的凝聚聚類作為一個圖，使得每個超像素是構成像素的最小生成樹節(jié)點。 GS04能很好地粘附在圖像的邊界，但具產(chǎn)生的超像素的大小和形狀非常不規(guī)則。實際上，它的復雜度是O( QUOTE )并且夠快。然而，它不提供在超像素或它們緊湊的量的顯式控制。SL08。Moore等

7、人，提出一種以產(chǎn)生通過找到最佳路徑，或接縫符合網(wǎng)格超像素的方法，該圖像分割成更小的垂直或水平區(qū)。最佳路徑是使用圖切割方法類似煤層雕刻發(fā)現(xiàn)。雖然SL08的復雜度是 QUOTE ，根據(jù)作者，這并不占預先計算的邊界地圖，并且極大地影響輸出的質量和速度。GCa10和GCb10。Veksler等人使用類似的紋理合成工作的全局優(yōu)化方法。超像素由縫合在一起的重疊圖像塊，使得每個像素屬于只重疊區(qū)中的一個獲得的。他們建議他們的方法的兩個變體，一個用于產(chǎn)生緊湊超像素（GCA10），一個用于恒定強度超像素（GCB10）。2.2.基于梯度向上的算法從像素的粗略初始聚類開始，直到一些收斂條件得到滿足并形成超像素，都用梯

8、度上升的方法進行提煉、集群。MS02。均值漂移，用于定位的密度函數(shù)的局部最大值的迭代方式尋求過程中，被施加到找到在圖像的顏色或強度的特征空間模式，會聚到相同模式的像素來定義超像素。 MS02是一個較老的方法，生產(chǎn)非均勻大小的不規(guī)則形狀的超像素。它 QUOTE 的復雜度，使得它相當慢，而且不能準確控制數(shù)量，大小，或超像素的緊湊度。QS08?？焖僖苿右膊捎靡环N模式尋求分割方案。它使用medoid轉變程序來初始化分割。然后將其移至特征空間，增加了Parzen窗密度估計的最近的鄰居的每個點。雖然它能較好的附著圖像邊界，但是復雜度為 QUOTE 的QS08相當緩慢（d是一個很小的常數(shù)）。 QS08不允許

9、顯式控制大小或超像素的數(shù)目。以前的工作已經(jīng)使用QS08為對象定位和運動分割。WS91。分水嶺的方法，從局部極小開始生產(chǎn)流域，從而進行梯度上升，即分離集水盆地線。所得超像素往往在尺寸和形狀極不規(guī)則，并且不能顯示出良好的邊界的粘附性。相對比較快（復雜度為O( QUOTE )），但對那些超過超像素數(shù)量的或緊密度的不能控制。TP09。Turbopixel方法使用基于水平集的幾何流逐步擴張一系列的種子位置。幾何流動依賴于本地圖像梯度，瞄準到像平面上定期分發(fā)超像素。不同于WS91，TP09超像素被限制為要求具有大小均勻，致密性，和邊界粘附。 TP09依賴于復雜程度不同的算法，但在實踐中，作者聲稱，大約反應

10、為 QUOTE 。但是，在被檢查的算法中，TP09仍是最慢的并且邊界的附著性也是相對較差的。3.SLIC超像素我們提出了一種生成超像素的新方法，它比現(xiàn)有方法更快，更高效。這種方法展現(xiàn)出了最先進的邊界附著性，并且提高了圖像分割算法的效率。簡單線性迭代集群是為了使K-means能夠適應超像素產(chǎn)生，有兩個重要的區(qū)別：1.通過限制到正比于超像素尺寸的區(qū)域中的搜索空間，優(yōu)化距離計算的數(shù)量急劇減少。這降低了像素N在數(shù)量上和獨立超像素K的線性復雜度。2.加權距離量度組合顏色和空間鄰近，同時提供在超像素的尺寸和緊湊性的控制。SLIC類似于用作在中描述的深度估計，這不完全是在超像素生成的背景下探索出的預處理步驟

11、的辦法。3.1 算法SLIC易于使用，便于理解。在默認情況下，該算法的唯一參數(shù)為k，約同樣大小的超像素所需的號碼。在CIELAB顏色空間的彩色圖像，聚類程序開始于初始化步驟，其中k初始聚類中心 QUOTE 的間距為小號像素上的規(guī)則網(wǎng)格取樣。為了產(chǎn)生大致同樣大小的超像素，像素間隔為 QUOTE 。聚類中心移動到對應于最低梯度位置的33鄰域位置。這樣做是為了避免在邊緣定心一個超像素，并減少播種一個超像素與嘈雜象素的機會。接著，在分配步驟中，每個像素i與最接近的聚類中心的搜索區(qū)域重疊的位置相關聯(lián)，如在圖中描繪。 2.這是關鍵加快我們的算法，因為限制了搜索區(qū)域的大小顯著減少距離計算的數(shù)量，并導致顯著速

12、度優(yōu)于常規(guī)k均值聚類，其中每個像素必須與所有聚類中心進行比較。這通過引入一個距離量度D，其確定每個像素最接近的聚類中心，如在第3.2節(jié)中討論的是唯一可能的。由于超像素的預期空間范圍近似大小SS的一個地區(qū)，相似像素的搜索是在一個區(qū)域2S2S圍繞超像素中心完成。一旦各象素已被關聯(lián)到最近的聚類中心，所有屬于該集群的像素的載體，更新步驟調整聚類中心是平均 QUOTE 。 L2范數(shù)被用來計算新的群集中心位置和先前的聚類中心位置之間的殘余誤差E。分配和更新步驟可以反復重復，直至誤差收斂，但我們已發(fā)現(xiàn)，10次迭代足以滿足大多數(shù)圖像，所以本文中的所有結果都使用該標準。最后，一個后置處理將脫離的像素再分配到附近

13、的超像素并使其強制連接。整個算法總結在算法1中。3.2 距離測量SLIC超像素對應于在實驗室中彩色圖象平面空間群集。這顯現(xiàn)了定義測量距離D時的一個問題，當然這個問題不會立刻顯現(xiàn)。D在算法1中計算了一個像素i和聚類中心Ck之間的距離。一個像素的顏色用CIELAB顏色空間L A BT來表示，其可能值的范圍是已知的。像素位置的位置x yT，另一方面，可以采用值的范圍，根據(jù)圖像的大小而變化。簡單地定義D為在實驗室空間的歐氏距離，這將導致不同大小的超像素的群集行為不一致。對于大型超像素，空間距離超過顏色接近，給人以不是顏色空間接近更多的相對重要性。這將產(chǎn)生超像素緊湊不很好地粘附在圖像邊界。對于較小的超像

14、素，相反的是真實的。為了使兩個距離結合成一個單一的測量，有必要通過在群集內(nèi)其各自的最大距離Ns和Nc來規(guī)范化接近的顏色和鄰近的空間。這樣，D寫成 QUOTE QUOTE QUOTE ds=(xj-xi)2+(yj-yi)2 QUOTE 預期在給定集群內(nèi)的最大空間距離應該對應于采樣間隔，N_S= S=（N/k）確定最大顏色距離數(shù)控不是那么簡單，因為顏色距離可顯著變化從集群到集群和形象的形象。可以通過數(shù)控固定常數(shù)m來避免此問題，（1）變成這簡化了我們在實踐中使用距離測量：通過這種方式限定D，M也讓我們考慮了相似的顏色和鄰近的空間之間的相對重要性。當m變大的，空間的接近更重要并且所得的超像素更緊湊（

15、即，它們具有較低的面積周長比）。當m為小，所得到的超像素圖像邊界附著性更緊密，但有規(guī)則的形狀和大小也越少。當使用CIELAB顏色空間中，m可以是在范圍1,40。等式可以通過設置來適于灰度圖像它也可以擴展到處理，如圖所示。通過包括深度尺寸的空間接近性術語：3.3 后期處理和其它超像素的算法一樣，SLIC沒有明確強制連接。在聚類程序的末尾，不屬于同一連接的組件作為其聚類中心部分“孤立”像素可能仍然存在。為了校正此，這樣的像素被分配到最接近的聚類中心，使用已連接的部件算法。3.4 復雜性通過聚類程序的局部化搜索，SLIC避免執(zhí)行數(shù)千冗余的距離計算。在實踐中，一個像素落在少于8個聚類中心的附近，這意味

16、著SLIC復雜度為 QUOTE 。與此相反，瑣碎上限經(jīng)典k均值算法是 QUOTE ，和實際的時間復雜度是 QUOTE ，其中I是收斂所需的迭代次數(shù)。而計劃以減少的k均值復雜已經(jīng)使用質數(shù)長度取樣，隨機抽樣，本地群集交換提出的，通過設置上限和下限，這些方法是非常一般性質。 SLIC是專門針對超像素聚類的問題。最后，與大部分超像素的方法和上述的方法來加快k均值，在SLIC的復雜性是在像素的數(shù)目的直鏈，不考慮K值。4 與最先進算法的比較我們使用公開的源代碼對SLIC算法和五個先進的超像素算法進行比較。這些算法包括GS04,3 NC05,4 TP09,5 QS09,6和提出的算法的兩個版本，GCa10和

17、每個方法產(chǎn)生超像素分割圖。4.1 邊界的附著性可以說，一個超像素方法最重要的特性是它的邊界附著能力。邊界召回和下分割錯誤是堅持邊界標準的措施。在圖圖4a和4b，SLIC，GS04，NC05，TP09，QS09和GC10使用Berkeley數(shù)據(jù)庫在這些措施相比。此外，通過將圖像分割成均勻的正方形而獲得的基準性能被表示為“方”。伯克利數(shù)據(jù)集包含300321481的圖像，和對應于各圖象大約10人類注釋的地面實況分割。邊界召回測量了部分地面真實邊緣，包括至少兩個超像素邊緣在內(nèi)的像素。每個邊界召回的方法繪制，都是為了增加超像素的數(shù)量。高邊界召回表明，很少有真正的邊緣被漏診。由SLIC和GS04產(chǎn)生的超像

18、素顯示了最好的邊界召回性能。如果我們通過10這個默認值來減少SLIC的緊密度，SLIC將顯示出優(yōu)異于GS04的性能。欠切分錯誤，是另一種邊界附著性的測量方法。從地面真理分割gi給定一個地區(qū)和所需的超像素組覆蓋, QUOTE ,它測量了多少像素從 QUOTE “泄漏”到了 QUOTE 的邊界。如果|.|在像素切割的尺寸,M是地面實況片段的數(shù)量,B表示 QUOTE 中像素的最小數(shù)值，欠分割錯誤表示為 QUOTE - N)在我們實驗中，B被定義為 QUOTE 的5%，用來解釋地面真值的歧義。如果超像素不緊密符合地面真實情況，會導致U值偏高。4.2 計算和存儲效率超像素通常用來代替像素網(wǎng)格來幫助加速其

19、他算法。因此,在第一時間內(nèi)有效的生成超像素和你重要。在一個英特爾雙核2.26 GHz處理器2 GB RAM的同等條件下，我們比較各種超像素方法在增加分割圖片大小時所用的時間。復雜度為 QUOTE 的SLIC是最快的超像素方法,其優(yōu)勢是可以增加圖像的大小。除了復雜度為 QUOTE 的GS04能與SLIC一較高下,但其余方法在處理速度上與SLIC有很大的差距。同樣重要的是, 為了處理大型圖像，超像素算法具有較高的內(nèi)存使用效率。SLIC是存儲效率最高的方法,只需要N來存儲每個像素到其最近的聚類中心的距離。其他方法有比較高的內(nèi)存需求:GS04和GC10需要5N浮點數(shù)存儲四個結點的邊的權值和閾值（或者9

20、N來存儲八個結點）。4.3 分割性能超像素通常用作分割算法的預處理步驟。一個好的超像素算法應該提高被使用的分割算法的性能。我們比較了MSRC上SLIC、GS04 NC05,TP09,QS09,GC10分割的數(shù)據(jù)集。這些結果使用的方法,即使用超像素計算顏色,紋理,幾何形狀和位置特征。然后訓練分類器的21個對象類和學習CRF模型。表1中的結果顯示SLIC 超像素的性能最佳。SLIC也減少了計算時間，超過NC05 500倍,該方法用于。我們還測試了2010年帕斯卡VOC數(shù)據(jù)集使用的方法。在分割精確度上，SLIC比QS09更好，并且通過數(shù)量級減少了生成超像素所花費的時間。4.4 總結除了上面討論的屬性

21、, 其他因素也應該考慮到超像素算法的質量中。其中一個要考慮的因素是易于使用。有許多復雜且不和諧參數(shù)的超像素方法會導致用時長、質量差。另一個考慮是并不是所有的方法都能提供的明確超像素數(shù)量的的能力。最后,能夠控制超像素的密實度也是很重要的。緊湊且定期超像素往往是可取的,因為他們的有限的大小和幾個鄰居形成了更易于判斷的曲線,可以提取更多的局部相關特性。然而,以密實度為代價的邊界依從性和控制這種權衡的能力是有用的。下面,我們從邊界的依從性、速度、內(nèi)存效率,分割質量、參數(shù)調優(yōu)、明確超像素數(shù)量的能力、控制超像素密實度的能力來審查每個超像素方法的性能。TP09。雖然TP09能產(chǎn)生一些最緊湊且持續(xù)保持一定大小

22、的超像素,但是在邊界召回和欠分割錯誤上表現(xiàn)最差。TP09還運行緩慢并導致分割性能很差。NC05,這是最慢的超像素算法; 處理20481536的圖像時，幾乎比SLIC慢100倍,耗時800s。另外，TP09只用一個參數(shù)進行優(yōu)化并能直接控制超像素的數(shù)量。NC05。相比TP09，歸一劃割只有一個小的改進。NC05產(chǎn)生的超像素比TP09更加緊湊,基于圖論的應用程序使其吸引力。然而,邊界的附著性很差,在邊界召回方面排名第六和在欠分割錯誤方面排名第五。盡管如此,分割質量高得驚人。NC05的運行時間是非常緩慢的,該方法不能分割20481536圖片,會發(fā)出“內(nèi)存溢出”錯誤。GCa10 GCb10。這兩種方法性

23、能類似,盡管他們的設差有異計(緊湊且強度恒定的超像素)。GCb10 產(chǎn)生的“緊湊”超像素比GCa10更緊湊,盡管遠低于TP09 NC05。在邊界召回方面,GCa10 和GCb10排名中間,分別是第五和第四。他們在欠分割錯誤方面持續(xù)緩慢提高(第三和第四)。盡管GCa10和GCb10速度比NC05 TP09快,但是緩慢的運行時間限制了它的效用(要求分別是235s和315s),他們是被報道出的分割性能最差的方法之一。GC10有三個參數(shù)調優(yōu),包括很難設定的補丁的大小。從積極的一面來看,GC10允許控制超像素的數(shù)量,并能產(chǎn)生超像素。QS09。快速轉換表現(xiàn)出了良好的欠分割誤差和邊界召回能力,整體排名第二和

24、第三。然而,QS09則顯示出了相對落后的分割性能,加上其他的限制，使其成為并不理想的選擇。它運行時間緩慢 (181s),需要幾個反直觀的參數(shù)進行調優(yōu),并且不能控制超過一定數(shù)量和緊密度的超像素。最后,源代碼無法確保超像素各部分完整的連接,這可能成為后續(xù)要處理的問題。GS04。盡管超像素非常不規(guī)則，它仍然能夠很好的附著在圖像的邊界。它在邊界召回中位列第一,優(yōu)于SLIC算法。它是第二快的方法,分割20481536圖像只需在18.19 s(沒有執(zhí)行參數(shù)搜索)。然而,GS04的分割性能和欠分割錯誤相對貧窮,可能因為它的大和不規(guī)則形狀的超像素使其不適合分割方法。最后,GS04不允許超像素的數(shù)量和密實度被三

25、個輸入?yún)?shù)控制。SLIC。這里考慮的超像素方法,SLIC顯然是整體表現(xiàn)最好的。它是最快的方法,分割一張20481536的圖片只需14.94s,并且存儲效率最高。它擁有優(yōu)秀的邊界附著能力, 在欠分割錯誤方面優(yōu)于所有其他方法和在邊界召回方面以小的劣勢僅次于GS04 (通過調整m,它排名第一)。當用于分割,SLIC顯示出最佳的性能來提升MSRC和帕斯卡數(shù)據(jù)集。SLIC易于使用,其唯一參數(shù)就是被期望超像素的數(shù)量,并且是為數(shù)不多的能產(chǎn)生超立體像素的幾個方法之前已。最后,在現(xiàn)有的方法中,SLIC的獨特之處在于它能夠通過m來控制所需的超像素密度和邊界附著能力之間的平衡。4.5 更復雜的距離度量讀者可能想知道

26、, 考慮了第3節(jié)中描述的簡單方法，如果用更復雜的距離措施改善SLIC的性能會怎么樣。我們研究了這個問題，并用自適應歸一化距離測量(ASLIC)和測地線距離測量(GSLIC)替換了其距離。但令人驚訝的是，在速度、內(nèi)存和邊界附著性方面，在簡單的距離測量中使用它，優(yōu)于ASLIC和GSLIC。自適應SLIC，或稱ASLIC，適應每個集群內(nèi)的顏色和標準化的空間。這些常量值用于正常顏色和空間距離,所以他們可以組合成一個單一的聚類的距離測量。不使用常量值，而是從上一次迭代，ASLIC動態(tài)規(guī)范化接近每個集群使用的最大觀測空間和顏色距離 QUOTE 。因此,測量的距離為和之前一樣,恒定的標準化因素用于第一個迭代

27、,但后跟蹤算法記錄每個集群的最大距離。這種方法的優(yōu)點是,超級像素密實度是一致的,且不需要設置m。這是以減少邊界召回為價格的。測量距離的SLIC，或稱為GSLIC，用測量的距離來代替其距離。從第一個像素 QUOTE 到另一個 QUOTE ，為定義的測量距離為定義為將 QUOTE 到 QUOTE 之間的所有路徑設置為T， QUOTE 值與P有聯(lián)系，給出其中 QUOTE 是CIELAB顏色向量 QUOTE 和 QUOTE 之間的歐幾里得距離。這種方法的優(yōu)點是保證在 QUOTE 平面上連接,不再需要后續(xù)處理步驟。然而,計算成本太高高，并且邊界粘附性能受到損害。5 生物醫(yī)學應用許多流行的基于圖論的圖像分

28、割算法，如Graph-cuts，隨著加到圖中的點越多，價格也越貴，但是實際上圖片的大小也被限制了。對于一些應用，如從電子顯微照片（EM）看線粒體分割，圖像是大但是不能以降低分辨率為代價。在這種情況下，像素網(wǎng)格定義的曲線分割就變得棘手了。SLIC超像素顯著降低了圖形的復雜性，使分割易于處理。這種方法推廣到3D圖像棧中，它可以包含數(shù)十億的立體像素。只有最節(jié)儉的算法可以不使用某些方法減少圖的大小，并且能夠操作如此龐大的數(shù)據(jù)。SLIC超像素通過超過三個數(shù)量級來降低存儲器要求和復雜性，并通過常規(guī)立方體顯著地提高了性能。6 結束語超像素已經(jīng)成為了視覺領域的一個重要工具，在本文中，我們?yōu)樽x者提供了現(xiàn)代化的超

29、像素技術并對此進行了深入的性能分析。我們對五個最先進的算法進行了實證比較。如在預處理步驟使用分割框架時，專注于自己的邊界依從性，分割速度和性能。此外，我們提出了基于K-均值聚類的SLIC算法，這個產(chǎn)生超像素的新方法已被證明幾乎在各個方面超越已經(jīng)存在的超像素方法。雖然我們的實驗很周密，但還是有不周全的地方。某些超像素方法，具體地比如GC10和TP09，沒有考慮彩色信息，但是其它方法做到了。這可能會在其性能產(chǎn)生負面影響。致謝這項工作是由美國國家競爭力中心的研究移動信息和通信系統(tǒng)（NCCR-MICS）、歐盟項目（ERC微納下授權號碼5005-67322）支持，部分由瑞士國家科學基金會支持。2.外文原

30、文SLIC Superpixels Compared to State-of-the-Art Superpixel MethodsAbstractComputer vision applications have come to rely increasingly on superpixels in recent years, but it is not always clear what constitutes a good superpixel algorithm. In an effort to understand the benefits and drawbacks of exist

31、ing methods, we empirically compare five state-of-the-art superpixel algorithms for their ability to adhere to image boundaries, speed, memory efficiency, and their impact on segmentation performance. We then introduce a new superpixel algorithm, simple linear iterative clustering (SLIC), which adap

32、ts a k-means clustering approach to efficiently generate superpixels. Despite its simplicity, SLIC adheres to boundaries as well as or better than previous methods. At the same time, it is faster and more memory efficient, improves segmentation performance, and is straightforward to extend to superv

33、oxel generation. Index TermsSuperpixels, segmentation, clustering, k-means.1 INTRODUCTIONSUPERPIXEL algorithms group pixels into perceptually meaningful atomic regions which can be used to replace the rigid structure of the pixel grid (Fig. 1). They capture image redundancy, provide a convenient pri

34、mitive from which to compute image features, and greatly reduce the complexity of subsequent image processing tasks. They have become key building blocks of many computer vision algorithms, such as top scoring multiclass object segmentation entries to the PASCAL VOC Challenge , depth estimation, seg

35、mentation, body model estimation, and object localization.There are many approaches to generating superpixels, each with its own advantages and drawbacks that may be better suited to a particular application. For example, if adherence to image boundaries is of paramount importance, the graph-based m

36、ethod of may be an ideal choice. However, if superpixels are to be used to build a graph, a method that produces a more regular lattice, such as, is probably a better choice. While it is difficult to define what constitutes an ideal approach for all applications, we believe the following properties

37、are generally desirable:1. Superpixels should adhere well to image boundaries.2. When used to reduce computational complexity as a preprocessing step, superpixels should be fast to compute, memory efficient, and simple to use.3. When used for segmentation purposes, superpixels should both increase t

38、he speed and improve the quality of the results.We therefore performed an empirical comparison of five stateof-the-art superpixel methods, evaluating their speed, ability to adhere to image boundaries, and impact on segmentation performance. We also provide a qualitative review of these, and other,

39、superpixel methods. Our conclusion is that no existing method is satisfactory in all regards.To address this, we propose a new superpixel algorithm: simple linear iterative clustering (SLIC), which adapts k-means clustering to generate superpixels in a manner similar to it. While strikingly simple,

40、SLIC is shown to yield state-of-the-art adherence to image boundaries on the Berkeley benchmark, and outperforms existing methods when used for segmentation on the PASCAL and MSRC data sets. Furthermore, it is faster and more memory efficient than existing methods. In addition to these quantifiable

41、benefits, SLIC is easy to use, offers flexibility in the compactness and number of the superpixels it generates, is straightforward to extend to higher dimensions, and is freely available.2 EXISTING SUPERPIXEL METHODSAlgorithms for generating superpixels can be broadly categorized as either graph-ba

42、sed or gradient ascent methods. Below, we review popular superpixel methods for each of these categories, including some that were not originally designed specifically to generate superpixels. Table 1 provides a qualitative and quantitative summary of the reviewed methods, including their relative p

43、erformance.2.1 Graph-Based AlgorithmsGraph-based approaches to superpixel generation treat each pixel as a node in a graph. Edge weights between two nodes are proportional to the similarity between neighboring pixels. Superpixels are created by minimizing a cost function defined over the graph.NC05.

44、 The Normalized cuts algorithm recursively partitions a graph of all pixels in the image using contour and texture cues, globally minimizing a cost function defined on the edges at the partition boundaries. It produces very regular, visually pleasing superpixels. However, the boundary adherence of N

45、C05 is relatively poor and it is the slowest among the methods (particularly for large images), although attempts to speed up the algorithm exist it. NC05 has a complexity of O( QUOTE ), where N is the number of pixels.GS04. Felzenszwalb and Huttenlocher propose an alternative graph-based approach t

46、hat has been applied to generate superpixels. It performs an agglomerative clustering of pixels as nodes on a graph such that each superpixel is the minimum spanning tree of the constituent pixels. GS04 adheres well to image boundaries in practice, but produces superpixels with very irregular sizes

47、and shapes. It is O( QUOTE ) complex and fast in practice. However, it does not offer an explicit control over the amount of superpixels or their compactness.SL08. Moore et al. propose a method to generate superpixels that conform to a grid by finding optimal paths, or seams, that split the image in

48、to smaller vertical or horizontal regions. Optimal paths are found using a graph cuts method similar to Seam Carving1. While the complexity of SL08 is QUOTE according to the authors, this does not account for the precomputed boundary maps, which strongly influence the quality and speed of the output

49、.GCa10 and GCb10. Veksler et al. use a global optimization approach similar to the texture synthesis work of. Superpixels are obtained by stitching together overlapping image patches such that each pixel belongs to only one of the overlapping regions. They suggest two variants of their method, one f

50、or generating compact superpixels (GCa10) and one for constantintensity superpixels (GCb10).2.2 Gradient-Ascent-Based AlgorithmsStarting from a rough initial clustering of pixels, gradient ascent methods iteratively refine the clusters until some convergence criterion is met to form superpixels.MS02

51、. mean shift, an iterative mode-seeking procedure for locating local maxima of a density function, is applied to find modes in the color or intensity feature space of an image. Pixels that converge to the same mode define the superpixels. MS02 is an older approach, producing irregularly shaped super

52、pixels of nonuniform size. It is QUOTE complex, making it relatively slow,and does not offer direct control over the amount, size, or compactness of superpixels.QS08. Quick shift also uses a mode-seeking segmentation scheme. It initializes the segmentation using a medoid shift procedure. It then mov

53、es each point in the feature space to the nearest neighbor that increases the Parzen density estimate. While it has relatively good boundary adherence, QS08 is quite slow, with an QUOTE complexity (d is a small constant). QS08 does not allow for explicit control over the size or number of superpixel

54、s. Previous works have used QS08 for object localization and motion segmentation.WS91. The watershed approach performs a gradient ascent starting from local minima to produce watersheds, lines that separate catchment basins. The resulting superpixels are often highly irregular in size and shape, and

55、 do not exhibit good boundary adherence. The approach of is relatively fast (O( QUOTE ) complexity), but does not offer control over the amount of superpixels or their compactness.TP09. The Turbopixel method progressively dilates a set of seed locations using level-set-based geometric flow. The geom

56、etric flow relies on local image gradients, aiming to regularly distribute superpixels on the image plane. Unlike WS91, TP09 superpixels are constrained to have uniform size, compactness, and boundary adherence. TP09 relies on algorithms of varying complexity, but in practice, as the authors claim,

57、has approximately QUOTE behavior. However, it is among the slowest algorithms examined and exhibits relatively poor boundary adherence.3 SLIC SUPERPIXELSWe propose a new method for generating superpixels which is faster than existing methods, more memory efficient, exhibits state-of-the-art boundary

58、 adherence, and improves the performance of segmentation algorithms. Simple linear iterative clustering is an adaptation of k-means for superpixel generation, with two important distinctions:1. The number of distance calculations in the optimization is dramatically reduced by limiting the search spa

59、ce to a region proportional to the superpixel size. This reduces the complexity to be linear in the number of pixels Nand independent of the number of superpixels k.2. A weighted distance measure combines color and spatial proximity while simultaneously providing control over the size and compactnes

60、s of the superpixels.SLIC is similar to the approach used as a preprocessing step for depth estimation described in 30, which was not fully explored in the context of superpixel generation.3.1 AlgorithmSLIC is simple to use and understand. By default, the only parameter of the algorithm is k, the de