Parallel CUDA implementation of a stereo matching algorithm

Authors

  • V.A. Fursov
  • E.V. Goshin
  • A.P. Kotov

Keywords:

stereo matching
3D reconstruction
projective geometry
epipolar geometry
parallel computing
graphics processors
CUDA technology

Abstract

Searching for the corresponding fragments and points on several images of the same scene is one of the central problems in many applications: autonomous navigation extended landmarks, pattern recognition, 3D-scene reconstruction, etc. To solve this problem, various correlation methods for the similarity analysis of fragments are used. Algorithms based on these methods have a high computational complexity. In this paper we consider a stereo matching algorithm for 3D-scene reconstruction. We propose a computational scheme that improves the performance of this algorithm. This computational scheme is implemented using CUDA technology. A high degree of parallelism is achieved due to a large number of the same operations for corresponding points on epipolar lines. Numerical experiments were carried out using the proposed parallel algorithm. The resulting speed-up is estimated.

New computational technologies

Downloads

Published

2014-03-14

Issue

Vol. 15 (2014): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biographies

V.A. Fursov

Samara University
• Head of Department

E.V. Goshin

Institute of Image Processing Systems of RAS
• PhD Student

A.P. Kotov

Samara University
• Head of Department

References

  1. Аншаков Г.П., Голяков А.Д., Петрищев В.Ф., Фурсов В.А. Автономная навигация космических аппаратов. Самара: ЦСКБ-Прогресс, 2011.
  2. Lowe D.G. Object recognition from local scale-invariant features // Proc. Seventh IEEE Int. Conf. on Computer Vision. Vol. 2. New York: IEEE Press, 1999. 1150-1157.
  3. Ojala T., Pietikainen M., Harwood D. Performance evaluation of texture measures with classification based on Kullback discrimination of distributions // Proc. 12th IAPR Int. Conf. on Pattern Recognition. Vol. 1. New York: IEEE Press, 1994. 582-585.
  4. Dalal N., Triggs B. Histograms of oriented gradients for human detection // IEEE Computer Society Conf. on Computer Vision and Pattern Recognition (CVPR’05). Vol. 1. New York: IEEE Press, 2005. 886-893.
  5. Ke Y., Sukthankar R. PCA-SIFT: a more distinctive representation for local image descriptors // Proc. 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol. 2. New York: IEEE Press, 2004. 506-513.
  6. Barnes C., Shechtman E., Finkelstein A., Gold’man D. PatchMatch: a randomized correspondence algorithm for structural image editing // ACM Trans. Graph. 2009. 28, N 3. Article No. 24.
  7. Klaus A., Sormann M., Karner K. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure // Proc. 18th Int. Conf. on Pattern Recognition. Vol. 3. New York: IEEE Press, 2006. 15-18.
  8. Bleyer M., Rother C., Kohli P., Scharsteinh D., Sinha S. Object stereo-joint stereo matching and object segmentation // Proc. 2011 IEEE Conf. on Computer Vision and Pattern Recognition (CVPR). New York: IEEE Press, 2011. 3081-3088.
  9. Zitnick C. L., Kang S.B. Stereo for image-based rendering using image over-segmentation // Int. J. of Computer Vision. 75, N 1. 2007. 49-65.
  10. Yang Q., Ahuja N. Stereo matching using epipolar distance transform // IEEE Trans. on Image Processing. 2012. 21, N 10. 4410-4419.
  11. Kowalczuk J., Psota E.T., Perez L.C. Real-time stereo matching on CUDA using an iterative refinement method for adaptive support-weight correspondences // IEEE Trans. on Circuits and Systems for Video Technology. 2013. 23, N 1. 94-104.
  12. Фурсов В.А., Гошин Е.В., Бибиков С.А. Реконструкция 3D-сцен на пучках эпиполярных плоскостей стереоизображений // Мехатроника, автоматизация, управление. 2013. № 9. 19-24.
  13. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход. М.: Вильямс, 2004.
  14. Грузман И.С., Киричук В.С., Косых В.П., Перетягин Г.И., Спектор А.А. Цифровая обработка изображений в информационных системах. Новосибирск: Изд-во НГТУ, 2002.
  15. Фурсов В.А., Бибиков С.А., Гошин Е.В., Жердев Д.А. Параллельная реализация модифицированного алгоритма реконструкции трехмерной сцены по стереоизображениям // Тр. Междунар. научной конференции «Параллельные вычислительные технологии», 1-5 апреля 2013 г., г. Челябинск. Челябинск: Изд-во ЮУрГУ, 2013. 624.
  16. Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. М.: ДМК Пресс, 2010.