Abstract A parallel solution of the graphbased method is proposed to improve the segmentation speed. In this solution, the similarity computation is parallelized by means of grid partition. And a parallel Lanczos algorithm is designed to compute the eigenvalues in view of the sparseness of the similarity matrix and the inner parallelism of matrixvector multiplication. The experimental results under MPI environment show that the parallel solution effectively improves the realtime performance of the graphbased segmentation method.
[1] Shi Jianbo, Malik J. Normalized Cuts and Image Segmentation. IEEE Trans on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888905 [2] Felzenszwalb P F, Huttenlocher D P. Efficient GraphBased Image Segmentation. International Journal of Computer Vision, 2004, 59(2): 167181 [3] Odobez J M, GaticaPerez D, Guillemot M. Spectral Structuring of Home Videos // Proc of the International Conference on Image and Video Retrieval. Urbana, USA, 2003: 310320 [4] Yu S X, Shi Jianbo. Multiclass Spectral Clustering // Proc of the IEEE International Conference on Computer Vision. Nice, France, 2003: 313319 [5] Choudhary A N, Ranka S. Parallel Processing for Computer Vision and Image UnderstandingGuest Editors’ Introduction to the Special Issue. IEEE Computer, 1992, 25(2): 710 [6] Malik J, Belongie S, Shi Jianbo, et al. Textons, Contours and Regions: Cue Integration in Image Segmentation // Proc of the IEEE International Conference on Computer Vision. Corfu, Greece, 1999: 918925 [7] Fowlkes C, Martin D, Malik J. Learning Affinity Functions for Image Segmentation: Combining PatchBased and GradientBased Approaches // Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Madison, USA, 2003, Ⅱ: 5464 [8] Martin D R, Fowlkes C C, Malik J. Learning to Detect Natural Image Boundaries Using Local Brightness, Color, and Texture Cues. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004, 26(5): 530549 [9] Lanczos C. An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators. Journal of Research of the National Bureau of Standards, 1950, 45: 225282 [10] Jia Zhongxiao, Zhang Ping. Two Refined Lanczos Algorithms for Computing the Largest/Smallest Singular Values and Associated Singular Vectors of a Large Matrix. Mathematica Numerica Sinica, 2003, 25(3): 293304 (in Chinese) (贾仲孝,张 萍.计算大规模矩阵最大最小奇异值和奇异向量的两个精化Lanczos算法.计算数学, 2003, 25(3): 293304) [11] Jiang Erxiong. Symmetric Matrix Computation. Shanghai, China: Shanghai Scientific and Technological Publishers, 1984 (in Chinese) (蒋尔雄.对称矩阵计算.上海:上海科学技术出版社, 1984) [12] Wu K, Canning A, Simon H D, et al. ThickRestart Lanczos Method for Electronic Structure Calculations. Journal of Computational Physics, 1999, 154(1): 156173 [13] Wu K, Simon H D. TRLan Software Package [DB/OL]. [20050902]. http://crd.lbl.gov/~kewu/trlan.html
2007, Vol. 20 
