F. Dehne et K. Guimaraes, EXACT AND APPROXIMATE COMPUTATIONAL GEOMETRY SOLUTIONS OF AN UNRESTRICTED POINT SET STEREO MATCHING PROBLEM, Information processing letters, 64(3), 1997, pp. 107-114
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.