MAPPING STEREO AND IMAGE MATCHING ALGORITHMS ONTO PARALLEL ARCHITECTURES

In this paper we present parallel implementations of two vision tasks; stereo matching and image matching. Linear features are used as match ing primitives. These implementations are performed on a fixed size me sh array and achieve processor-time optimal performance. For stereo ma tching, we propose O(Nn3/P2) time algorithm on a P x P processor mesh array, where N is the number of line segments in one image, n is the n umber of line segments in a window determined by the object size, and P less-than-or-equal-to n. The sequential algorithm takes O(Nn3) time. For image matching, a partitioned parallel implementation is develope d. O[((nm/P2) + P)nm] time performance is achieved on a P x P processo r mesh array, where P2 less-than-or-equal-to nm. This leads to a proce ssor-time optimal solution for P less-than-or-equal-to (nm)1/3.