A constant-space belief propagation algorithm for stereo matching

Qingxiong Yang, Liang Wang, Narendra Ahuja

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we consider the problem of stereo matching using loopy belief propagation. Unlike previous methods which focus on the original spatial resolution, we hierarchically reduce the disparity search range. By fixing the number of disparity levels on the original resolution, our method solves the message updating problem in a time linear in the number of pixels contained in the image and requires only constant memory space. Specifically, for a 800 x 600 image with 300 disparities, our message updating method is about 30 x faster (1.5 second) than standard method, and requires only about 0.6% memory (9 MB). Also, our algorithm lends itself to a parallel implementation. Our GPU implementation (NVIDIA Geforce 8800GTX) is about 10 x faster than our CPU implementation. Given the trend toward higher-resolution images, stereo matching using belief propagation with large number of disparity levels as efficient as the small ones makes our method future-proof. In addition to the computational and memory advantages, our method is straightforward to implement.

Original languageEnglish (US)
Title of host publication2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010
Pages1458-1465
Number of pages8
DOIs
StatePublished - Aug 31 2010
Event2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010 - San Francisco, CA, United States
Duration: Jun 13 2010Jun 18 2010

Publication series

NameProceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
ISSN (Print)1063-6919

Other

Other2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010
CountryUnited States
CitySan Francisco, CA
Period6/13/106/18/10

Fingerprint

Data storage equipment
Image resolution
Program processors
Pixels
Graphics processing unit

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition

Cite this

Yang, Q., Wang, L., & Ahuja, N. (2010). A constant-space belief propagation algorithm for stereo matching. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010 (pp. 1458-1465). [5539797] (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition). https://doi.org/10.1109/CVPR.2010.5539797

A constant-space belief propagation algorithm for stereo matching. / Yang, Qingxiong; Wang, Liang; Ahuja, Narendra.

2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010. 2010. p. 1458-1465 5539797 (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Yang, Q, Wang, L & Ahuja, N 2010, A constant-space belief propagation algorithm for stereo matching. in 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010., 5539797, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1458-1465, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010, San Francisco, CA, United States, 6/13/10. https://doi.org/10.1109/CVPR.2010.5539797
Yang Q, Wang L, Ahuja N. A constant-space belief propagation algorithm for stereo matching. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010. 2010. p. 1458-1465. 5539797. (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition). https://doi.org/10.1109/CVPR.2010.5539797
Yang, Qingxiong ; Wang, Liang ; Ahuja, Narendra. / A constant-space belief propagation algorithm for stereo matching. 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010. 2010. pp. 1458-1465 (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition).
@inproceedings{a0c74a018dc548a7b3b87e42af7eaf96,
title = "A constant-space belief propagation algorithm for stereo matching",
abstract = "In this paper, we consider the problem of stereo matching using loopy belief propagation. Unlike previous methods which focus on the original spatial resolution, we hierarchically reduce the disparity search range. By fixing the number of disparity levels on the original resolution, our method solves the message updating problem in a time linear in the number of pixels contained in the image and requires only constant memory space. Specifically, for a 800 x 600 image with 300 disparities, our message updating method is about 30 x faster (1.5 second) than standard method, and requires only about 0.6{\%} memory (9 MB). Also, our algorithm lends itself to a parallel implementation. Our GPU implementation (NVIDIA Geforce 8800GTX) is about 10 x faster than our CPU implementation. Given the trend toward higher-resolution images, stereo matching using belief propagation with large number of disparity levels as efficient as the small ones makes our method future-proof. In addition to the computational and memory advantages, our method is straightforward to implement.",
author = "Qingxiong Yang and Liang Wang and Narendra Ahuja",
year = "2010",
month = "8",
day = "31",
doi = "10.1109/CVPR.2010.5539797",
language = "English (US)",
isbn = "9781424469840",
series = "Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition",
pages = "1458--1465",
booktitle = "2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010",

}

TY - GEN

T1 - A constant-space belief propagation algorithm for stereo matching

AU - Yang, Qingxiong

AU - Wang, Liang

AU - Ahuja, Narendra

PY - 2010/8/31

Y1 - 2010/8/31

N2 - In this paper, we consider the problem of stereo matching using loopy belief propagation. Unlike previous methods which focus on the original spatial resolution, we hierarchically reduce the disparity search range. By fixing the number of disparity levels on the original resolution, our method solves the message updating problem in a time linear in the number of pixels contained in the image and requires only constant memory space. Specifically, for a 800 x 600 image with 300 disparities, our message updating method is about 30 x faster (1.5 second) than standard method, and requires only about 0.6% memory (9 MB). Also, our algorithm lends itself to a parallel implementation. Our GPU implementation (NVIDIA Geforce 8800GTX) is about 10 x faster than our CPU implementation. Given the trend toward higher-resolution images, stereo matching using belief propagation with large number of disparity levels as efficient as the small ones makes our method future-proof. In addition to the computational and memory advantages, our method is straightforward to implement.

AB - In this paper, we consider the problem of stereo matching using loopy belief propagation. Unlike previous methods which focus on the original spatial resolution, we hierarchically reduce the disparity search range. By fixing the number of disparity levels on the original resolution, our method solves the message updating problem in a time linear in the number of pixels contained in the image and requires only constant memory space. Specifically, for a 800 x 600 image with 300 disparities, our message updating method is about 30 x faster (1.5 second) than standard method, and requires only about 0.6% memory (9 MB). Also, our algorithm lends itself to a parallel implementation. Our GPU implementation (NVIDIA Geforce 8800GTX) is about 10 x faster than our CPU implementation. Given the trend toward higher-resolution images, stereo matching using belief propagation with large number of disparity levels as efficient as the small ones makes our method future-proof. In addition to the computational and memory advantages, our method is straightforward to implement.

UR - http://www.scopus.com/inward/record.url?scp=77955985724&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955985724&partnerID=8YFLogxK

U2 - 10.1109/CVPR.2010.5539797

DO - 10.1109/CVPR.2010.5539797

M3 - Conference contribution

AN - SCOPUS:77955985724

SN - 9781424469840

T3 - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition

SP - 1458

EP - 1465

BT - 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010

ER -