EXACT AND APPROXIMATE COMPUTATIONAL GEOMETRY SOLUTIONS OF AN UNRESTRICTED POINT SET STEREO MATCHING PROBLEM

In this paper we study the problem of computing an exact, or arbitrari ly close to exact, solution of an unrestricted point set stereo matchi ng problem. Within the context of classical approaches like the Marr-P oggio algorithm, this means that we study how to solve the unrestricte d basic subproblems created within such approaches, possibly yielding an improved overall performance of such methods. We present an O(n(2+4 k)) time and O(n(4)) space algorithm for exact unrestricted stereo mat ching, where n represents the number of points in each set and k the n umber of depth levels considered, We generalize the notion of a delta- approximate solution for point set congruence to the stereo matching p roblem and present an O((epsilon/delta)(k)n(2+2k)) time and O((epsilon /delta)n(2)) space delta-approximate algorithm for unrestricted stereo matching (epsilon represents measurement inaccuracies in the image). We introduce new computational geometry tools for stereo matching: the translation square arrangement, approximate translation square arrang ement and approximate stereo matching tree. (C) 1997 Published by Else vier Science B.V.