Patent ID: 7542624

Claim:
A method for three-dimensional (3D) range imagery, comprising: a) providing a template data set A={a l , . . . , a P } wherein a i comprises a 3×1 column vector representing the (x i , y i , z i ) coordinate of the i th point of P points located on a 3D object; b) providing a probe data set B={b l , . . . , b Q } wherein b i comprises a 3×1 column vector representing the (x i , y i , z i ) coordinate of the i th point of Q points located on a 3D image; c) computing a template range image A(p)=z p by quantization mapping [x p , y p ]′ of the set A into an index represented by column vector p=[i p , j p ]′ wherein i p and i p are positive integers and z p is the range value (z-coordinate) for p; d) computing a probe range image B(q)=z q by quantization mapping [x q , y q ]′ of the set B into an index represented by column vector q=[i q , j q ]′ wherein i q and i q are positive integers and z q is the range value (z-coordinate) for q; e) representing a set of coordinates of points in a window of size w, according to W={(u, v)|=1, . . . w, v=1 . . . w} for a distance kernel k wherein u and v determine the entries for k that are the square norm to that entry's position from the center of the distance kernel; f) centering the window W at p of the probe range image B, thereby providing a set of coordinates of centered points according to W p W+p−(1+└w/2┘) for each point p of the template range image A(p) and wherein W p is the window W centered at p; g) for each point p in A, finding the distance d W of the closest corresponding point q in B, according to d W ⁢ ⁢ ( a p , B ) = min q ∈ W p ⁢  a p - b q  wherein d W is the approximate Hausdorff distance using the window W; h) computing a Hausdorff fraction, according to ϕ ⁢ ⁢ ( A , B ) ≈ ∑ a p ∈ A ⁢ ⁢ χ D ⁢ ⁢ ( d W ⁢ ⁢ ( a p , B ) ) ⁢  A  . where function χ D (x) is an indicator function given by χ D ⁢ ⁢ ( x ) = { 1 if ⁢ ⁢ x ≤ D 0 otherwise and D is a largest threshold Hausdorff distance; and i) determining if the Hausdorff fraction exceeds a threshold, thereby determining if the 3D image matches the 3D object.