Window-based method for approximating the Hausdorff in three-dimensional range imagery
View Patent ↗One approach to pattern recognition is to use a template from a database of objects and match it to a probe image containing the unknown. Accordingly, the Hausdorff distance can be used to measure the similarity of two sets of points. In particular, the Hausdorff can measure the goodness of a match in the presence of occlusion, clutter, and noise. However, existing 3D algorithms for calculating the Hausdorff are computationally intensive, making them impractical for pattern recognition that requires scanning of large databases. The present invention is directed to a new method that can efficiently, in time and memory, compute the Hausdorff for 3D range imagery. The method uses a window-based approach.
1. 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.
2. The method of claim 1 , wherein the closest distance is computed according to
min
q
∈
W
p
a
p
-
b
q
=
min
i
∈
W
⌊
(
A
(
p
)
-
B
(
p
+
i
-
1
-
⌊
w
/
2
⌋
)
)
2
+
k
(
i
)
⌋
where k is the distance kernel.
3. The method of claim 1 , further comprising preregistering the template data set and the probe data set.
4. The method of claim 3 , wherein the preregistering comprises finding a translation that optimally aligns the data sets.
5. The method of claim 3 , wherein the preregistering comprises finding a rotation that optimally aligns the data sets.
6. The method of claim 1 , further comprising computing the directed Hausdorff distance, according to
h
(
A
,
B
)
≈
max
a
p
∈
A
d
W
(
a
p
,
B
)
.
7. The method of claim 6 , further comprising computing a undirected Hausdorff distance H(A, B), according to max(h(A, B), h(B, A)).
8. The method of claim 1 , wherein the data sets comprise facial recognition data and the 3D object comprises a first facial image and the 3D image comprises a second facial image.