Computer Science ›› 2014, Vol. 41 ›› Issue (1): 64-68.

Previous Articles     Next Articles

Realization of Graph Guts Based on Improved Push-relabel Algorithm on GPU

LI Ye,YU Shuang-yuan and LUO Si-wei   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Graph Cuts has been an important method of computer vision,which can apply to the field of image processing.In recent years,the graphics processing unit (GPU) has progressively and rapidly become a kind of higher parallel computing processing unit with launching the Compute Unified Device Architecture (CUDA) from Nvidia.The parallel implementing of push-relabel algorithm on high-end parallel computing platform has a high level of parallelism to improve the computational efficiency.This technology has an important value of theoretical study and widely actual application background,which expands the range of applications of graph cuts in the field of computer vision.It firstly presents a basic parallel implementation of the push-relabel algorithm for graph cuts on the GPU,which introduces texture memory of GPU to improve the speedup.At last,the experiments test the times of foreground-background segmentation and compare speedup of different groups,which show optimizations can enhance the performance of the implementation.

Key words: Graph cuts,Push-relabel algorithm,CUDA,GPU

[1] Shiloach Y,Vishkin U.An o(nlogn) parallel max-flow algorithm[J].Journal of Algorithms,1982,3:128-146
[2] Goldberg A.Efficient graph algorithms for sequential and parallel computers[D].Cambridge:MIT,1987
[3] Anderson R J,Setubal J.On the parallel implementation of goldbergs maximum flow algorithm[C]∥Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures.1992:168-177
[4] Hussein M,Varshney A,Davis L.On implementing graph cuts on cuda[C]∥First Workshop on General Purpose Processing on Graphics Processing Units.2007
[5] Vineet V,Narayanan P J.CudaCuts:Fast Graph Cuts on the GPU[C]∥CVPR Workshop on Visual Computer Vision on GPUs.2008
[6] 张舒,褚艳利.GPU高性能运算之CUDA[M].北京:中国水利水电出版社,2009:15-20
[7] Cormen T H.Introduction to algorithms(第二版)[M].潘金贵,译.北京:机械工业出版社,2009:411-415
[8] Boykov Y,Jolly M P.Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images[C]∥International Conference on Computer Vision (ICCV).2001
[9] Wu Zhen-yu,Leahy R.An Optimal Graph Theoretic Approach to Data Clustering:Theory and Its Application to Image Segmentation [J].IEEE Trans.on Pattern Analysis and Machine Intelligence,1993,15(11):1101-1113
[10] Shi Jian-bo,Malik J.Normalized Cuts and Image Segmentation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905
[11] 卢风顺,宋君强,银福康,等.CPU/GPU协同并行计算研究综述[J].计算机科学,2011,8(3):5-9
[12] Grady L,Schwartz E L.Isoperimetric Graph Partitioning for Ima-ge Segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(3):469-475
[13] 杨帆,廖庆敏.基于图论的图像分割算法的分析与研究[J].视频技术应用与工程,2006(7):80-83
[14] 许新征,丁世飞,史忠植,等.图像分割的新理论和新方法[J].电子学报,2010(2A):18-82
[15] 刘丙涛,田铮,李小斌,等.基于图论Gomory-Hu算法的SAR图像多尺度分割[J].宇航学报,2008,9(3):1002-1007
[16] Feng Wen-juan,Xiang Hui,Zhu Yan.An Improved Graph-based Image Segmentation Algorithm and Its GPU Acceleration [C]∥Workshop on Digital Media and Digital Content Management.2011
[17] Bader D A,Sachdeva V.A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic [C]∥ISCA PDCS.2005:41-48
[18] 张庆科,杨波,王琳,等.基于GPU的现代并行优化算法[J].计算机科学,2012,9(4):304-311
[19] 陶文兵,金海.一种新的基于图谱理论的图像阈值分割方法[J].计算机学报,2007,0(1):110-119
[20] Boykov Y,Veksler O,Zabih R.Fast approximate energyminimization via graph cuts [J].IEEE Trans.Pattern Anal.Mach.Intell.,2001,23(11):1222-1239

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!