Image analysis – Applications – 3-d or stereo imaging analysis
Reexamination Certificate
1993-08-09
2001-08-21
Chang, Jon (Department: 2623)
Image analysis
Applications
3-d or stereo imaging analysis
C382S216000
Reexamination Certificate
active
06278798
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to digital image processing, and, more particularly, to a system for recognition of three-dimensional objects in a two-dimensional image and the method of recognition.
Computer vision includes the automatic machine recognition and localization of three-dimensional objects from two-dimensional images.
FIG. 1
shows a computer vision system
100
with passive sensor
102
, digitizer
104
, recognition processor
106
, and output
108
. Passive sensor
102
may include a TV camera or an infrared imager for night vision; digitizer
104
may be a sampling analog-to-digital converter or may be partially incorporated into sensor
102
in the case of a CCD sensor. Recognition processor
106
analyzes the image from sensor
102
to determine the presence of certain target objects in the scene. Output
108
may be a display of recognized targets or may feed a controller for flight as in automatic target recogntion in a smart missle. Recognition processor
106
may use various target recognition systems.
Known target recognition systems include recognition by global features such as Fourier transform descriptors, moments, silhouette-based features, and so forth. These systems presume an open target. However, for images of target objects which may be partially occluded or with low signal-to-noise ratios the extraction of such global features may not be possible.
Alternative to global feature recognition is local feature recognition. Huttenlocher and Ullman, Recognizing Solid Objects by Alignment with an Image, 5 Int'l. J. Comp. Vision 195 (1990) and Lowe, Three-Dimensional Object Recognition from Single Two-Dimensional Images, 31 Artif. Intell. 355 (1987) describe model-based recognition approaches using vertices and edges. The model-based approach matches stored geometric models against features extracted from an image. Recognition of an object within an image entails finding a transformation (rotation, translation, perspective projection) from a set of features of a model of the object to a set of corresponding features extracted from the image. The larger the sets of model and image features, the better the match. Note that Huttenlocher and Ullman use a weak perspective projection in which the depth of objects is presumed small so the perspective is orthgraphic projection plus a common scale factor for all objects to account for distance. They compute hypothesized transformations from sets of three pairs of model and image points (corners) and verify the transformations with edge contour matches as follows. Given three pairs of points (a
m
, a
i
), (b
m
, b
i
), and (c
m
, c
i
), where the image points (subscript “i”) are in two-dimensional sensor coordinates and the model points (subscript “m”) are in three-dimensional object coordinates. First, rotate and translate the model so that the new a, is at the origin (0,0,0) and the new b
m
and c
m
are in the x-y plane. This operation is poerformed offline for each triple of model points.
Next, define the translation vector b=−a
i
, and translate the image points by b so that the new a
i
is at the origin (0,0), the new b
i
is at old b
i
-a
i
and the new c
i
is at old c
i
-a
i
.
Then, solve for the 2 by 2 linear transformation L with matrix elements L
ij
so that Lb
m
=b
i
and Lc
m
=c
i
. The translation b and linear transformation L define a unique affine transformation A as long as the three model points are not collinear.
Further, compute c
1
and c
2
as:
c
1
=±[w
+(
w
2
+4
q
2
)
½
]
½
/2
½
c
2
=−q/c
1
where w=L
12
2
+L
22
2
−(L
11
2
+L
21
2
) and q=L
11
L
12
+L
21
L
22
.
Lastly, form the 3 by 3 matrix sR as:
L
11
L
12
(
c
2
L
21
-
c
1
L
22
)
/
s
L
21
L
22
(
c
1
L
12
-
c
2
L
11
)
/
s
c
1
c
2
(
L
11
L
22
-
L
21
L
12
)
/
s
where s=[L
11
2
+L
21
2
+c
1
2
]
½
. This yields the complete transformation with translation vector b and scale and rotation sR. The image coordinates of a transformed model point, p′=sRp+b, are then given by the x and y coordinates of p′.
In constrast, Lowe uses a full perspective and feature groupings (parallelism, collinearity, and end point proximity) of edges to trigger Newton-Rapheson method computation of hypothesized transformations.
U.S. Pat. No. 5,173,946 (K. Rao) discloses a corner matching and distance array method of image matching.
The foregoing items are hereby incorporated by reference.
SUMMARY OF THE INVENTION
The present invention provides a model-based recognition system which uses pseudo-inverse generated hypothesized transformations based on sets of four or more pairs of model and image points. Various preferred embodiments employ further pairs of points for transformation verification and also incorporate a preliminary three-point transformation as part of the hypothesized transformation generation.
REFERENCES:
patent: 5123057 (1992-06-01), Verly et al.
patent: 5210799 (1993-05-01), Rao
patent: 5214721 (1993-05-01), Fukuhara et al.
Strang, “Linear Algebra and its Applications”, 1988, pp. 444-449.*
Huttenlocher, “Recognizing Solid Objects by Alignment with an Image” Intl. J. Comp. Vision, 5:2, 195-212 (1990).*
Lowe “Fitting Parameterizod 3D Models to Images” IEEE PAMI vol. 13, No. 5 1991 pp 441-450.*
Jacobs, “Optimal Matching of Planes models in 3D Scenes”, IEEE, pp 269-274 (1991).*
Yamamoto, “A Segmentation Method Based on Motion From Image Sequence and Depth.” Proc. of 10thInt. Conf. on Pattern Recognition, vol. 1, pp. 230-232, Jun. 1990.*
Chien et al. “Interative Autoassociative Memory Models for Image Recalls and Pattern Classification.” IEEE Joint Conf. on Neural Networks, vol. 1, pp. 30-35, Nov. 1991.*
Chao et al. “Pseudo-Inverse with Increasing Threshold: an Error-Recovery Pattern Recognition Algorithm.” RNNS/IEEE Symposium on Neuroinformatics and Neurocomputers, vol. 2, pp. 888-894, Oct. 1992.*
Chao et al. “Combined Orthogonal Vector and Pseudo-Inverse Approach for Robust Pattern Recognition.” RNNS/IEEE Symposium on Neuroinformtics and Neurocomputers, vol. 2, pp. 881-887, Oct. 1992.*
“An Anglytical Solution for the Perspective 4-Point Problem”, Horaud et al. IEEE Computer Vision and Pattern Recognition, 1989.
Brady W. James
Chang Jon
Hoel Carlton H.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Image object recognition system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image object recognition system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image object recognition system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2520097