A parallel algorithm for incremental stereo matching on SIMD machines

A parallel algorithm for stereo matching that achieves high speed by exploiting the parallel architectures of typical single-instruction multiple-data (SIMD) processors is presented. The approach is based on several existing techniques dealing with the classification and evaluation of matches, the application of ordering constraints, and relaxation-based matching. The techniques have been integrated and reformulated in terms of parallel execution on a theoretical SIMD machine. Feasibility is demonstrated by implementation on a commercially available SIMD machine. An ideal machine, operating at 60 Hz, can accomplish stereo matching in 1.5 s using 88 machine cycles. On the commercial machine, stereo matching was achieved in 13.5 s using 404 cycles