Abstract
In this paper, we present fast parallel implementations of the RANSAC algorithm on the Cell processor, a multicore SIMD architecture. We present our developed strategies for efficient parallel implementation of the RANSAC algorithm by exploiting the specific features of the Cell processor. We also discuss our new method for model generation to increase the efficiency of calculation of the Homography transformation by RANSAC. In fact, by using this new method and change of algorithm, we have been able to increase the overall performance by a factor of almost 3. We also discuss in details our approaches for further increasing the efficiency by a careful vectorization of the computation as well as by reducing the communication overhead by overlapping computation and communication. The results of our practical implementations clearly demonstrate that a very high sustained computational performance (in terms of sustained GFLOPS) can be achieved with a minimum of communication overhead, resulting in a capability of real-time generation and evaluation of a very large number of models. With a date set of size 2048 data and a number of 256 models, we have achieved the performance of over 80 sustained GFLOPS. Since the peak computing power of our target architecture is 179 GFLOPS, this represents a sustained performance of about 44% of the peak power, indicating the efficiency of our algorithms and implementations. Our results clearly demonstrate the advantages of parallel implementation of RANSAC on MIMD-SIMD architectures such as Cell processor. They also prove that, by using such a parallel implementation over the sequential one, a problem with a fixed number of iterations (hypothetical models) can be solved much faster leading to a potentially better accuracy of the model.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fischler, M.A., Bolles, R.C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. ACM Commun. 24(6), 381–395 (1981)
Chum, O., Matas, J.: Randomized RANSAC with T d,d test. In: Proc. British Machine Vision Conference, pp. 448–457 (2002)
Pritchett, P., Zisserman, A.: Wide baseline stereo matching. In: Proc. Int. Conf. on Computer Vision, pp. 754–760 (1998)
Torr, P.H.S.: Outlier detection and motion segmentation. Ph.D. dissertation, Dept. of Engineering Science, University of Oxford (1995)
McLauchlan, P., Jaenicke, A.: Image mosaicing using sequential bundle adjustment. In: Proc. British Machine Vision Conference, pp. 751–759 (2000)
Raguram, R., Frahm, J.M., Pollefeys, M.: A comparative analysis of RANSAC techniques leading to adaptive real-time random sample consensus. In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part II. LNCS, vol. 5303, pp. 500–513. Springer, Heidelberg (2008)
Chum, O., Matas, J.: Matching with PROSAC - progressive sample consensus. In: Proc. Int. Conf. on Computer Vision and Pattern Recognition, pp. 220–226 (2005)
Tordoff, B.J., Murray, D.W.: Guided-MLESAC: Faster image transform estimation by using matching priors. IEEE Trans. Pattern Anal. Mach. Intell. 27(10), 1523–1535 (2005)
Myatt, D.R., Torr, P.H.S., Nasuto, S.J., Bishop, J.M., Craddock, R.: NAPSAC: High noise, high dimensional robust estimation. In: Proc. British Machine Vision Conference, pp. 458–467 (2002)
Nistèr, D.: Preemptive RANSAC for live structure and motion estimation. Mach. Vision Appl. 16(5), 321–329 (2005)
Iser, R., Kubus, D., Wahl, F.M.: An efficient parallel approach to random sample matching (pRANSAM). In: Proc. Int. Conf. of Robotics and Automation, pp. 1199–1206 (2009)
Winkelbach, S., Molkenstruck, S., Wahl, F.M.: Low-cost laser range scanner and fast surface registration approach. In: 28th Annual Symp. of the German Association for Pattern Recognition, pp. 718–728 (2006)
Torr, P.H.S., Zisserman, A.: MLESAC:a new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding 78(1), 138–156 (2000)
Press, W.H., et al.: Numerical Recipes: The Art of Scientific Computing, 3rd edn. Cambridge University Press, Cambridge (2007)
Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision, 2nd edn. Cambridge University Press, Cambridge (2004)
Arevalo, A., et al.: Programming the Cell Broadband Engine Architecture: Examples and Best Practices. IBM Redbook (2008)
Mercury CAB2, http://www.mc.com/products/boards/accelerator_board2.aspx
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khalili, A., Fijany, A., Hosseini, F., Safari, S., Fontaine, JG. (2010). Fast Parallel Model Estimation on the Cell Broadband Engine. In: Bebis, G., et al. Advances in Visual Computing. ISVC 2010. Lecture Notes in Computer Science, vol 6454. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17274-8_46
Download citation
DOI: https://doi.org/10.1007/978-3-642-17274-8_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17273-1
Online ISBN: 978-3-642-17274-8
eBook Packages: Computer ScienceComputer Science (R0)