Recursive computation-based stereo matching and its implementation in VLSI

Kiyoshi Miura, Masanori Hariyama, Michitaka Kameyama

Research output: Contribution to journalArticlepeer-review


An important issue in the design of stereo vision, which is a necessity for robotic perception in three dimensions, is rapid determination of corresponding points in two shifted images. In this paper, we propose a method for identifying equivalent points on such images based on the computation of sums of absolute differences (SAD). Because the use of this method to identify such equivalent points can result in a rapidly increasing number of SAD computation cycles, reducing the number of these computations becomes an important issue. In this paper we propose a recursive algorithm for SAD computations that takes into account the existence of intermediate results that are common to several SAD operations. Our algorithm not only reduces the amount of computation, but also is suitable for VLSI implementation due to its regularity and ease of parallelization. Using this algorithm, we have reduced the amount of computation to 1.2% of the amount required when recursive computation is not used. In addition, we propose an allocation architecture based on scheduling that minimizes the memory capacity required for the intermediate results by minimizing the interconnections between computers. Our analysis reveals that performance levels 5000 times higher than the levels for special-use processors are achievable.

Original languageEnglish
Pages (from-to)19-27
Number of pages9
JournalElectronics and Communications in Japan, Part II: Electronics (English translation of Denshi Tsushin Gakkai Ronbunshi)
Issue number12
Publication statusPublished - 2004 Dec 1


  • Allocation
  • Scheduling
  • Stereo vision
  • Sum of Absolute Differences (SAD)
  • VLSI processor architecture

ASJC Scopus subject areas

  • Physics and Astronomy(all)
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Recursive computation-based stereo matching and its implementation in VLSI'. Together they form a unique fingerprint.

Cite this