摘  要: 過分割是計(jì)算機(jī)視覺領(lǐng)域流行的圖像預(yù)處理方法。針對(duì)其運(yùn)行速度慢的缺點(diǎn)，對(duì)廣泛采用的Turbopix算法提出CUDA并行優(yōu)化的方法。通過每個(gè)線程執(zhí)行一個(gè)超像素擴(kuò)張的任務(wù)分配，實(shí)現(xiàn)了水平集函數(shù)的并行演化；利用紋理存儲(chǔ)空間和常數(shù)存儲(chǔ)空間的優(yōu)化策略,改善了數(shù)據(jù)訪存的效率。實(shí)驗(yàn)結(jié)果表明，在GT 240M平臺(tái)上，平均加速比達(dá)到了15以上。
關(guān)鍵詞: 過分割； 超像素； Turbopix； CUDA

     超像素是圖像中局部區(qū)域內(nèi)連通、亮度相近、邊緣描述性較好的像素集合。將圖像劃分成超像素后，其圖像單元更加符合人們期望的結(jié)構(gòu)粒度[1]。由于能夠更有效地表示圖像結(jié)構(gòu)， 超像素被廣泛應(yīng)用于圖像內(nèi)容標(biāo)記[1]、虛擬漫游[2]、圖像分割[3-6]等領(lǐng)域。將圖像表示由像素轉(zhuǎn)換成超像素的過程稱為過分割(Over Segmentation)。常用的過分割算法有均值漂移[7]、分水嶺[8]、N-Cuts[9]和Turbopix算法[10]。均值漂移和分水嶺算法的優(yōu)點(diǎn)是計(jì)算復(fù)雜度較低，缺點(diǎn)是平滑區(qū)域存在著嚴(yán)重的欠分割(Under Segmentation)現(xiàn)象。N-Cuts和Turbopix算法通過緊致性約束(Compactness Constraint)有效解決了該問題。N-Cuts綜合考慮全局和局部信息，利用圖論算法對(duì)圖像內(nèi)容進(jìn)行劃分。圖像中的像素對(duì)應(yīng)圖的節(jié)點(diǎn)，像素間的鄰域關(guān)系對(duì)應(yīng)圖的邊，邊的權(quán)重反映了相鄰像素間的相似性。但是N-Cuts算法是NP難題。SHI J等人提出的譜估計(jì)算法[9]復(fù)雜度為O(N3/2)，其中N為像素?cái)?shù)目。FEZENSZWALB P等人基于圖節(jié)點(diǎn)聚類準(zhǔn)則將N-Cuts算法的復(fù)雜度降為O(NlogN)[11]，但該方法不能控制生成的超像素?cái)?shù)目。VEDALDI A等人在Mean-Shift的基礎(chǔ)上提出了計(jì)算速度更快的Quick-Shift算法[12]; LUCCHI A等人提出了計(jì)算復(fù)雜度為O(N)的簡(jiǎn)單線性迭代聚類算法SILC(Simple Linear Iterative Clustering)[13]，但這兩種方法在平滑區(qū)域都存在欠分割現(xiàn)象。在計(jì)算機(jī)視覺領(lǐng)域曲線演化算法[14-15]的啟發(fā)下， LEVINSHEIN A等人提出的Turbopix算法[10]具有與N-Cuts算法同等或更優(yōu)的性能，但顯著降低了計(jì)算時(shí)間，其計(jì)算復(fù)雜度和像素?cái)?shù)目近似成線性關(guān)系。Turbopix算法通過自適應(yīng)局部結(jié)構(gòu)的種子膨脹實(shí)現(xiàn)超像素的分割,其核心思路是將復(fù)雜的超像素分割難題簡(jiǎn)化為易解的幾何流(Geometry Flow)問題。
    雖然Turbopix算法與N-Cuts算法相比計(jì)算速度有顯著提高，但對(duì)于中等分辨率的圖像，其計(jì)算時(shí)間仍需要十幾秒。為了進(jìn)一步提高過分割的計(jì)算速度，本文在分析Turbopix算法并行性的基礎(chǔ)上，提出在GPU上CUDA并行實(shí)現(xiàn)的方法。
1 Turbopix算法分析
    Turbopix算法的基本思路是設(shè)計(jì)一個(gè)幾何流,使得曲

　算法的具體計(jì)算步驟如下。
　(1)計(jì)算像素的局部相似性函數(shù)φ(x,y)及其梯度。
    (2)在圖像I上均勻放置K個(gè)種子。
　(3)擾動(dòng)種子位置，使其偏離梯度較大的區(qū)域，以避免初始階段超像素邊界擴(kuò)張過慢。
　(4)有符號(hào)歐幾里得距離函數(shù)ψ和分配值圖A的初始化。A(x,y)若為非負(fù)值，則表示像素I(x,y)所屬超像素的序號(hào)；否則表示未分配到任何超像素中。
   (5)統(tǒng)計(jì)演化前已分配的像素個(gè)數(shù)C1。
　(6)將演化時(shí)刻n初始為0。
　(7)超像素?cái)U(kuò)張：計(jì)算速度圖SI和SB，根據(jù)式(2)更新ψ,并由ψ更新分配值圖A。
　(8)統(tǒng)計(jì)演化后已分配的像素個(gè)數(shù)C2。
　(9)演化時(shí)刻n遞增1。
　(10)判斷終止條件：如果(C1-C2)／圖像總的像素?cái)?shù)>某個(gè)常數(shù)，將C2值賦給C1并跳到步驟(7)，否則跳到步驟(11)。
    (11)后處理：將未分配的像素劃分到最鄰近的超像素中。
    (12)從ψ中提取零水平集，作為超像素的邊界。

2.6 后處理的CUDA優(yōu)化
    當(dāng)超像素邊界擴(kuò)張終止時(shí)，還有部分像素處于未分配狀態(tài)。后處理就是將這些未分配的像素劃分到距離其最近的超像素中。
2.7 超像素邊界提取的CUDA優(yōu)化
    超像素的邊界為距離函數(shù)ψ的零水平集，1表示邊界，0表示非邊界。這實(shí)際上就是分配值圖中非負(fù)值和負(fù)值之間的邊界。
3 實(shí)驗(yàn)與結(jié)果討論
    本文實(shí)驗(yàn)的硬件配置為Intel Core2 Duo 2.20 GHz CPU，2 GB內(nèi)存；GeForce GT 240 M 1.21 GHz GPU，16 KB共享內(nèi)存，436 MB全局內(nèi)存。軟件配置為Windows 7+Visual Studio 2008+CUDA SDK 4.0+NVIDIA Driver for Windows7(275.33)。
    將Turbopix算法的CPU實(shí)現(xiàn)[10]與本文的CUDA實(shí)現(xiàn)進(jìn)行對(duì)比，測(cè)試圖像為參考文獻(xiàn)[10]提供的lizard。圖1給出了在不同超像素個(gè)數(shù)下，本文CUDA優(yōu)化實(shí)現(xiàn)的平均加速比。在該實(shí)驗(yàn)中，測(cè)試圖像lizard的分辨率為518×344。從圖1可以看出，經(jīng)過CUDA優(yōu)化后平均加速比達(dá)到了15以上。

    圖2給出了超像素個(gè)數(shù)為500時(shí)，原始算法[10]和本文CUDA優(yōu)化得出的過分割結(jié)果。從圖2可以看出，本文CUDA優(yōu)化輸出的結(jié)果與原始算法結(jié)果存在差異。原始算法過分割的結(jié)果更接近目標(biāo)的邊界，而本文優(yōu)化的結(jié)果則在各超像素大小上更趨于一致。這種差異存在的主要原因是這兩種實(shí)現(xiàn)的SB速度計(jì)算方法不一樣。原始算法將位于未分配區(qū)域骨架處的所有像素點(diǎn)對(duì)應(yīng)的SB設(shè)為0，其他區(qū)域處則設(shè)為1。本文為便于CUDA實(shí)現(xiàn)，根據(jù)分配值圖確定SB的值。

    通過研究Turbopix算法的原理，本文提出了在GPU上高速并行實(shí)現(xiàn)的方法。該方法利用超像素邊界擴(kuò)張的數(shù)據(jù)獨(dú)立性，提出了原始算法關(guān)鍵步驟CUDA并行優(yōu)化的思路，并通過紋理存儲(chǔ)器和常數(shù)存儲(chǔ)器優(yōu)化了內(nèi)存訪問的效率。未來工作是改進(jìn)速度分量的計(jì)算方法，使本文實(shí)現(xiàn)結(jié)果與原始算法結(jié)果更加一致；進(jìn)一步優(yōu)化CUDA實(shí)現(xiàn)方式，使加速比能有更大的提高。
參考文獻(xiàn)
[1] 劉靖，李翠華，楊敦旭. 一種基于超像素的戶外建筑圖像布局標(biāo)定方法[J]. 廈門大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010,49(2):175-180.
[2] 袁淑娟，高秀芬. 基于圖像精確過分割的虛擬現(xiàn)實(shí)場(chǎng)景構(gòu)建[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2009,30(17):4044-4046.
[3] 韓守東,趙勇，陶文兵,等. 基于高斯超像素的快速Graph Cuts圖像分割方法[J]. 自動(dòng)化學(xué)報(bào)，2011,37(1):11-20.
[4] 劉陳，李鳳霞，張艷. 基于圖割與泛形信息的對(duì)象分割方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2009,21(12):1753-1760.
[5] 方浩，仇麗英，盧嘉鵬. 基于區(qū)域劃分和再融合的全幅視覺圖像分割[J]. 北京理工大學(xué)學(xué)報(bào)，2009,29(9):799-802.
[6] 劉陳，王欣欣，李鳳霞,等. 一種快速保邊的圖像對(duì)象分割方法[J]. 北京理工大學(xué)學(xué)報(bào)，2010,30(2):183-187.
[7] COMANICIU D, MEER P. Mean shift: a robust approach  toward feature space analysis[J]. IEEE Transactions on Pattern  Analysis and Machine Intelligence, 2002,24(5): 603-619.
[8] VINCENT L, SOILLE P. Watersheds in digital spaces: an efficient algorithm based on immersion simulations[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1991,13(6):583-598.
[9] SHI J,MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000,22(8):888-905.
[10] LEVINSHTEIN A, STERE A, KUTULAKOS K N, et al. TurboPixels: fast superpixels using geometric flows[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009,31(12):2290-2297.
[11] FELZENSZWALB P,HUTTENLOCHER D. Efficient graphbased image segmentation[J].International Journal of Computer Vision, 2004(1):167-181.
[12] VEDALDI A, SOATTO S. Quick shift and kernel methods for mode seeking[C]. Proceedings of the 10th European Conference on Computer Vision, Marseille, France, 2008:705-718.
[13] LUCCHI A, SMITH K, ACHANTA R. A fully automated approach to segmentation of irregularly shaped cellular  structures in EM images[C]. Proceedings of the International Conference on Medical Image Computing and Computer Assisted Intervention, Beijing, China, 2010:20-24.
[14] CASELLES V, CATTE F, COLL T, et al. A geometric model for active contours in image processing[J]. Numerische Mathematik, 1993,66(1):1-31.
[15] MALLADI R, SETHIAN J, VEMURI B. Shape modeling with front propagation:a level set approach[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17(2): 158-175.
[16] 張舒,禇艷利,趙開勇,等.GPU高性能計(jì)算之CUDA[M].北京：中國(guó)水利水電出版社, 2009.