Image object recognition system and method

• US 6,278,798 B1
• Filed: 08/09/1993
• Issued: 08/21/2001
• Est. Priority Date: 08/09/1993
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Rao, Kashipati G.
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/104,462
• Time in Patent Office: 2,934 Days
• Field of Search: 381/1, 381/41, 381/45-47, 381/30, 381/34, 381/36, 381/22, 381/100, 381/103, 381/154, 381/199, 381/209, 381/216, 381/224, 381/285, 381/294
• US Class Current: 382/154
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A pseudo-inverse derived model-point-to-image-point transformation hypothesis generator as could be used in a computer vision system. Preferred embodiments include generation of n-point transformations directly from n point pair sets and generation of n-point transformations from sets of n point pairs defined by a preliminary three-point transformation plus sets of (n−3) points having minimal error with respect to the three-point trnasformation. Systems include salient corner extraction and hypothesis transformation verification by further sets of point pairs.

Claims

1. A method of model-based image recognition, comprising the steps of:

(a) extracting image points from an input two-dimensional image;

(b) selecting a set of n of said image points extracted in step (a) and a set of n model points of a three-dimensional model in a class of K models, where n is a positive integer greater than or equal to 4 and K is a positive integer;

(c) computing a transformation of three dimensions to two dimensions based on said set of n model points and said set of n image points, said transformation a matrix C=JW^T(WW^T)<sup>−

1</sup> where J is a 3×

n matrix with each of the columns of J defined by a scaling factor plus the scaled two coordinates of one of said n points in said image and W is a 4×

n matrix with each of the columns of W defined by a constant plus the three coordinates of one of said n points in said model;

(d) repeating steps (b)-(c) for all sets of n of said image points and all sets of n model points of a model of said class of models;

(e) selecting a hypothesized transformation from said transformations created by steps (b)-(d) wherein said hypothesized transformation is characterized by an error measured by CW−

J of less than a predetermined threshold, but when none of said transformations has an error less than said predetermined threshold, selecting no transformation; and

(f) indicating recognition of an object in said image and corresponding to the model including the n model points of said hypothesized transformation when a hypothesized transformation is selected in step (e), else indicating no model objects recognized in said image when no transformation is selected in step (e).

2. The method of claim 1, wherein:

(a) n is in the range of 5 to 7.

3. The method of claim 1, wherein:

(a) said image points are corners; and

(b) said model points are vertices.

4. The method of claim 1, wherein:

(a) said selecting in step (c) of claim 1 includes picking said hypothesized transformation as a one of said transformations with an error not greater than the errors of others of said transformations.

5. The method of claim 1, wherein:

(a) when said set of n image points in step (b) of claim 1 are the points with coordinates (u₁,v₁), (u₂,v₂), (u₃,v₃), . . . , and (u_n,v_n), form the 3×

n matrix $J=\begin{array}{ccccc}{u}_1^{\mathrm{\prime <br><br>}}& u_2^{\mathrm{\prime <br><br>}}& u_3^{\mathrm{\prime <br><br>}}& \mathrm{\cdots <br><br>}& u_n^{\mathrm{\prime <br><br>}}\\ v_1^{\mathrm{\prime <br><br>}}& v_2^{\mathrm{\prime <br><br>}}& v_3^{\mathrm{\prime <br><br>}}& \mathrm{\cdots <br><br>}& v_n^{\mathrm{\prime <br><br>}}\\ w& w& w& \mathrm{\cdots <br><br>}& w\end{array}$

where u_j′

=u_jw with w a scale factor for weak perspective projection;

(b) when said set of n model points in step (b) of claim 1 are the points with coordinates (x₁,y₁,z₁), (x₂,y₂,z₂) . . . , and (x_n,y_n,z_n) form the 4×

n matrix $W=\begin{array}{ccccc}{x}_1& x_2& x_3& \mathrm{\cdots <br><br>}& x_n\\ y_1& y_2& y_3& \mathrm{\cdots <br><br>}& y_n\\ z_1& z_2& z_3& \mathrm{\cdots <br><br>}& z_n\\ 1& 1& 1& \mathrm{\cdots <br><br>}& 1\end{array}$

whereby the dummy row of 1s provides for translation of the image; and

(c) said computing a transformation in step (c) of claim 1 yields a 3×

4 matrix transformation matrix C by C=JW^T(WW^T)<sup>−

1</sup>.

6. The method of claim 5, wherein:

(a) said error is the sum of squares of the elements of the 3×

n matrix CW−

J.

7. The method of claim 6, further comprising the steps of:

(a) picking one of said transformations with transformation matrix C and error less than said predetermined threshold;

(b) selecting a further set of m of said model points from the model containing the n model points defining C, where m is a positive integer;

(c) computing a set of m hypothesized image points by applying C to said selected further m model points of step (b);

(d) selecting a set of m of said image points in addition to the n image points defining C;

(e) computing a preliminary verification error by the distances of said m hypothesized image points of step (c) from said corresponding m image points of step (d);

(f) repeating steps (b) through (e) for all sets of such m further model points and m further image points, and taking the smallest preliminary verification error as a verification error for C; and

(g) repeating steps (a) through (t) for all of said transformations with error less than said predetermined threshold;

(h) wherein said selecting a hypothesized transformation of step (e) of claim 1 is picking a one of said transformations from step (g) with an error plus verification error not greater than the errors of others of said transformations.

8. The method of claim 6, further comprising the steps of:

(a) picking one of said transformations with transformation matrix C;

(b) selecting a further set of m of said model points from the model containing the n model points defining C, where m is a positive integer;

(c) computing a set of m hypothesized image points by applying C to said selected further m model points of step (b);

(d) selecting a set of m of said image points in addition to the n image points defining C;

(e) computing a preliminary verification error by the distances of said m hypothesized image points of step (c) from said corresponding m image points of step (d);

(f) repeating steps (b) through (e) for all sets of such m further model points and m further image points, and taking the smallest preliminary verification error as a verification error for C; and

(g) repeating steps (a) through (f) for all of said transformations;

(h) wherein said selecting a hypothesized transformation of step (e) of claim 1 is picking a one of said transformations from step (g) with an error plus verification error not greater than the errors of others of said transformations.

9. The method of claim 6, further comprising the steps of:

(a) ranking said transformations with transformation matrix C and error according to error size with smaller error implying higher ranking;

(b) picking a highest ranking remaining transformation matrix C;

(c) selecting a further set of m of said model points from the model containing the n model points defining C, where m is a positive integer;

(d) computing a set of m hypothesized image points by applying C to said selected further m model points of step (c);

(e) selecting a set of m of said image points in addition to the n image points defining C;

(f) computing a preliminary verification error by the distances of said m hypothesized image points of step (d) from said corresponding m image points of step (e);

(g) repeating steps (c) through (f) for all sets of such m further model points and m further image points, and taking the smallest preliminary verification error as a verification error for C; and

(h) taking said selecting a hypothesized transformation of step (e) of claim 1 as the transformation of step (b) if said error plus verification error is less than a second predetermined threshold, else repeating steps (b) through (h).

10. A method of model-based image recognition, comprising the steps of:

(a) extracting image points from an input two-dimensional image;

(b) selecting a set of 3 of said image points extracted in step (a) and a set of 3 model points of a three-dimensional model in a class of K models, where K is a positive integer;

(c) computing a transformation of three dimensions to two dimensions based on mapping said set of 3 model points to said set of 3 image points, said transformation made of rotation, translation, and scaling;

(d) selecting a further set of k of said model points from the model containing the 3 model points defining said transformation, where k is a positive integer;

(e) computing a set of k hypothesized image points by applying said transformation to said selected further k model points of step (d);

(f) selecting a set of k of said image points in addition to the 3 image points defining said transformation;

(g) computing a preliminary error by the distances of said k hypothesized image points of step (e) from said corresponding k image points of step (f);

(h) repeating steps (d) through (g) for all sets of such k further model points and k further image points, and taking the smallest preliminary error as an error for said transformation;

(i) repeating steps (b) through (h) for all sets of 3 model points and 3 image points;

(j) selecting a transformation T from step (i) which has a minimal error;

(k) forming a transformation matrix C from the 3+k model points and corresponding image points defined by said transformation T from step (j) by pseudo-inverse;

(l) selecting a further set of m of said model points from the model containing the 3+k model points defining C, where m is a positive integer;

(m) computing a set of m hypothesized image points by applying C to said selected further m model points of step (l);

(n) selecting a set of m of said image points in addition to the 3+k image points defining C;

(o) computing a preliminary verification error by the distances of said m hypothesized image points of step (m) from said corresponding m image points of step (n);

(p) repeating steps (l) through (o) for all sets of such m further model points and m further image points, and taking the smallest preliminary verification error as a verification error for C; and

(q) indicating the recognition of an object in said image and corresponding to the model defining the transformation from step (p) when said verification error plus said error is less than a predetermined threshold, else repeating steps (j) through (q) for a transformation not previously selected, and when no transformation has verification error plus error less than said threshold indicating no model object recognized in said image.

11. The method of claim 10, wherein:

(a) k is in the range of 2 through 4.

12. The method of claim 10, wherein:

(a) said pseudo-inverse computation of step (k) of claim 10 is C=JW^T(WW^T)<sup>−

1</sup> when the set of 3+k image points have coordinates (u₁,v₁), (u₂,v₂), (u₃,v₃), . . . , and (u_3+k,v_3+k), to define the 3×

3+k matrix $J=\begin{array}{ccccc}{u}_1^{\mathrm{\prime <br><br>}}& u_2^{\mathrm{\prime <br><br>}}& u_3^{\mathrm{\prime <br><br>}}& \mathrm{\cdots <br><br>}& u_{3+k}^{\mathrm{\prime <br><br>}}\\ v_1^{\mathrm{\prime <br><br>}}& v_2^{\mathrm{\prime <br><br>}}& v_3^{\mathrm{\prime <br><br>}}& \mathrm{\cdots <br><br>}& v_{3+k}^{\mathrm{\prime <br><br>}}\\ w& w& w& \mathrm{\cdots <br><br>}& w\end{array}$

where u_j′

=u_jw with w a scale factor for weak perspective projection, and when the set of 3+k model points are the points with coordinates (x₁,y₁,z₁), (x₂,y₂,z₂,) . . . , and (x_3+k,y_3+k,z_3+k), to define the 4×

3+k matrix $W=\begin{array}{ccccc}{x}_1& x_2& x_3& \mathrm{\cdots <br><br>}& x_{3+k}\\ y_1& y_2& y_3& \mathrm{\cdots <br><br>}& y_{3+k}\\ z_1& z_2& z_3& \mathrm{\cdots <br><br>}& z_{3+k}\\ 1& 1& 1& \mathrm{\cdots <br><br>}& 1\end{array}$

whereby the dummy row of 1s provides for translation of the image.

13. A model-based recognition system, comprising:

(a) an imager;

(b) a corner extractor coupled to an output of said imager;

(c) a memory containing a list of vertices for each of K models;

(d) a hypothesis generator with inputs coupled to an output of said corner extractor and to said list of model vertices, wherein for each set of n of said vertices from one of said models and each set of n corners extracted from an image by said corner extractor, said hypothesis generator generates a transformation by pseudo-inverse of the form JW^T(WW^T)<sup>−

1</sup> where J is a 3×

n matrix with each of the columns of J defined by a scaling factor plus the scaled two coordinates of one of said n points in said image and W is a 4×

n matrix with each of the columns of W defined by a constant plus the three coordinates of one of said n points in said model, n is a positive integer greater than or equal to 4;

(e) a hypothesis verifier with input coupled to an output of said hypothesis generator, wherein for each set of m additional vertices from said one of said models and m additional corners said hypothesis verifier compares an error between the image points of said transformation applied to said n vertices plus said m additional vertices and said n corners plus said m additional corners; and

(f) an object recognition indicator with input coupled to an output of said hypothesis verifier and indicating recognition of an object in an image output by said imager and corresponding to the model of said n vertices plus said m additional vertices when said error is less than a predetermined threshold.

14. The system of claim 13, wherein:

(a) said pseudo-inverse of element (d) of claim 13 is JW^T(WW^T)<sup>−

1</sup> when the set of n image points have coordinates (u₁,v₁), (u₂,v₂), (u₃,v₃), . . . , and (u_n,v_n), to define the 3×

n matrix $J=\begin{array}{ccccc}{u}_1^{\mathrm{\prime <br><br>}}& u_2^{\mathrm{\prime <br><br>}}& u_3^{\mathrm{\prime <br><br>}}& \mathrm{\cdots <br><br>}& u_n^{\mathrm{\prime <br><br>}}\\ v_1^{\mathrm{\prime <br><br>}}& v_2^{\mathrm{\prime <br><br>}}& v_3^{\mathrm{\prime <br><br>}}& \mathrm{\cdots <br><br>}& v_n^{\mathrm{\prime <br><br>}}\\ w& w& w& \mathrm{\cdots <br><br>}& w\end{array}$

where u_j′

=u_jw with w a scale factor for weak perspective projection, and when the set of n vertices are the points with coordinates (x₁,y₁,z₁), (x₂,y₂,z₂,) . . . , and (x_n,y_n,z_n) to define the 4×

n matrix $W=\begin{array}{ccccc}{x}_1& x_2& x_3& \mathrm{\cdots <br><br>}& x_n\\ y_1& y_2& y_3& \mathrm{\cdots <br><br>}& y_n\\ z_1& z_2& z_3& \mathrm{\cdots <br><br>}& z_n\\ 1& 1& 1& \mathrm{\cdots <br><br>}& 1\end{array}$

whereby the dummy row of 1s provides for translation of the image.