摘 要: 過分割是計算機視覺領域流行的圖像預處理方法。針對其運行速度慢的缺點，對廣泛采用的Turbopix算法提出CUDA并行優化的方法。通過每個線程執行一個超像素擴張的任務分配，實現了水平集函數的并行演化；利用紋理存儲空間和常數存儲空間的優化策略,改善了數據訪存的效率。實驗結果表明，在GT 240M平臺上，平均加速比達到了15以上。
關鍵詞: 過分割； 超像素； Turbopix； CUDA
超像素是圖像中局部區域內連通、亮度相近、邊緣描述性較好的像素集合。將圖像劃分成超像素后，其圖像單元更加符合人們期望的結構粒度[1]。由于能夠更有效地表示圖像結構， 超像素被廣泛應用于圖像內容標記[1]、虛擬漫游[2]、圖像分割[3-6]等領域。將圖像表示由像素轉換成超像素的過程稱為過分割(Over Segmentation)。常用的過分割算法有均值漂移[7]、分水嶺[8]、N-Cuts[9]和Turbopix算法[10]。均值漂移和分水嶺算法的優點是計算復雜度較低，缺點是平滑區域存在著嚴重的欠分割(Under Segmentation)現象。N-Cuts和Turbopix算法通過緊致性約束(Compactness Constraint)有效解決了該問題。N-Cuts綜合考慮全局和局部信息，利用圖論算法對圖像內容進行劃分。圖像中的像素對應圖的節點，像素間的鄰域關系對應圖的邊，邊的權重反映了相鄰像素間的相似性。但是N-Cuts算法是NP難題。SHI J等人提出的譜估計算法[9]復雜度為O(N3/2)，其中N為像素數目。FEZENSZWALB P等人基于圖節點聚類準則將N-Cuts算法的復雜度降為O(NlogN)[11]，但該方法不能控制生成的超像素數目。VEDALDI A等人在Mean-Shift的基礎上提出了計算速度更快的Quick-Shift算法[12]; LUCCHI A等人提出了計算復雜度為O(N)的簡單線性迭代聚類算法SILC(Simple Linear Iterative Clustering)[13]，但這兩種方法在平滑區域都存在欠分割現象。在計算機視覺領域曲線演化算法[14-15]的啟發下， LEVINSHEIN A等人提出的Turbopix算法[10]具有與N-Cuts算法同等或更優的性能，但顯著降低了計算時間，其計算復雜度和像素數目近似成線性關系。Turbopix算法通過自適應局部結構的種子膨脹實現超像素的分割,其核心思路是將復雜的超像素分割難題簡化為易解的幾何流(Geometry Flow)問題。
雖然Turbopix算法與N-Cuts算法相比計算速度有顯著提高，但對于中等分辨率的圖像，其計算時間仍需要十幾秒。為了進一步提高過分割的計算速度，本文在分析Turbopix算法并行性的基礎上，提出在GPU上CUDA并行實現的方法。
1 Turbopix算法分析
Turbopix算法的基本思路是設計一個幾何流,使得曲
算法的具體計算步驟如下。
(1)計算像素的局部相似性函數φ(x,y)及其梯度。
(2)在圖像I上均勻放置K個種子。
(3)擾動種子位置，使其偏離梯度較大的區域，以避免初始階段超像素邊界擴張過慢。
(4)有符號歐幾里得距離函數ψ和分配值圖A的初始化。A(x,y)若為非負值，則表示像素I(x,y)所屬超像素的序號；否則表示未分配到任何超像素中。
(5)統計演化前已分配的像素個數C1。
(6)將演化時刻n初始為0。
(7)超像素擴張：計算速度圖SI和SB，根據式(2)更新ψ,并由ψ更新分配值圖A。
(8)統計演化后已分配的像素個數C2。
(9)演化時刻n遞增1。
(10)判斷終止條件：如果(C1-C2)／圖像總的像素數>某個常數，將C2值賦給C1并跳到步驟(7)，否則跳到步驟(11)。
(11)后處理：將未分配的像素劃分到最鄰近的超像素中。
(12)從ψ中提取零水平集，作為超像素的邊界。
2.6 后處理的CUDA優化
當超像素邊界擴張終止時，還有部分像素處于未分配狀態。后處理就是將這些未分配的像素劃分到距離其最近的超像素中。
2.7 超像素邊界提取的CUDA優化
超像素的邊界為距離函數ψ的零水平集，1表示邊界，0表示非邊界。這實際上就是分配值圖中非負值和負值之間的邊界。
3 實驗與結果討論
本文實驗的硬件配置為Intel Core2 Duo 2.20 GHz CPU，2 GB內存；GeForce GT 240 M 1.21 GHz GPU，16 KB共享內存，436 MB全局內存。軟件配置為Windows 7+Visual Studio 2008+CUDA SDK 4.0+NVIDIA Driver for Windows7(275.33)。
將Turbopix算法的CPU實現[10]與本文的CUDA實現進行對比，測試圖像為參考文獻[10]提供的lizard。圖1給出了在不同超像素個數下，本文CUDA優化實現的平均加速比。在該實驗中，測試圖像lizard的分辨率為518×344。從圖1可以看出，經過CUDA優化后平均加速比達到了15以上。
圖2給出了超像素個數為500時，原始算法[10]和本文CUDA優化得出的過分割結果。從圖2可以看出，本文CUDA優化輸出的結果與原始算法結果存在差異。原始算法過分割的結果更接近目標的邊界，而本文優化的結果則在各超像素大小上更趨于一致。這種差異存在的主要原因是這兩種實現的SB速度計算方法不一樣。原始算法將位于未分配區域骨架處的所有像素點對應的SB設為0，其他區域處則設為1。本文為便于CUDA實現，根據分配值圖確定SB的值。
通過研究Turbopix算法的原理，本文提出了在GPU上高速并行實現的方法。該方法利用超像素邊界擴張的數據獨立性，提出了原始算法關鍵步驟CUDA并行優化的思路，并通過紋理存儲器和常數存儲器優化了內存訪問的效率。未來工作是改進速度分量的計算方法，使本文實現結果與原始算法結果更加一致；進一步優化CUDA實現方式，使加速比能有更大的提高。
參考文獻
[1] 劉靖，李翠華，楊敦旭. 一種基于超像素的戶外建筑圖像布局標定方法[J]. 廈門大學學報(自然科學版)，2010,49(2):175-180.
[2] 袁淑娟，高秀芬. 基于圖像精確過分割的虛擬現實場景構建[J]. 計算機工程與設計，2009,30(17):4044-4046.
[3] 韓守東,趙勇，陶文兵,等. 基于高斯超像素的快速Graph Cuts圖像分割方法[J]. 自動化學報，2011,37(1):11-20.
[4] 劉陳，李鳳霞，張艷. 基于圖割與泛形信息的對象分割方法[J]. 計算機輔助設計與圖形學學報，2009,21(12):1753-1760.
[5] 方浩，仇麗英，盧嘉鵬. 基于區域劃分和再融合的全幅視覺圖像分割[J]. 北京理工大學學報，2009,29(9):799-802.
[6] 劉陳，王欣欣，李鳳霞,等. 一種快速保邊的圖像對象分割方法[J]. 北京理工大學學報，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高性能計算之CUDA[M].北京：中國水利水電出版社, 2009.