Dense disparity estimation with a divide-and-conquer disparity space image technique

Chun Jen Tsai*, Aggelos K. Katsaggelos

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


A new divide-and-conquer technique for disparity estimation is proposed in this paper. This technique performs feature matching following the high confidence first principle, starting with the strongest feature point in the stereo pair of scanlines. Once the first matching pair is established, the ordering constraint in disparity estimation allows the original intra-scanline matching problem to be divided into two smaller subproblems. Each subproblem can then be solved recursively until there is no reliable feature point within the subintervals. This technique is very efficient for dense disparity map estimation for stereo images with rich features. For general scenes, this technique can be paired up with the disparity-space image (DSI) technique to compute dense disparity maps with integrated occlusion detection. In this approach, the divide-and-conquer part of the algorithm handles the matching of stronger features and the DSI-based technique handles the matching of pixels in between feature points and the detection of occlusions. An extension to the standard disparity-space technique is also presented to compliment the divide-and-conquer algorithm. Experiments demonstrate the effectiveness of the proposed divide-and-conquer DSI algorithm.

Original languageEnglish (US)
Pages (from-to)18-29
Number of pages12
JournalIEEE Transactions on Multimedia
Issue number1
StatePublished - 1999


  • Depth map
  • Disparity estimation
  • Disparity-space image
  • Divide-and-conquer stereo matching

ASJC Scopus subject areas

  • Signal Processing
  • Media Technology
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Dense disparity estimation with a divide-and-conquer disparity space image technique'. Together they form a unique fingerprint.

Cite this