Object instance recognition using feature symbol triplets Number:7,412,427 from the United States Patent and Trademark Office (PTO) owispatent A feature symbol triplets object instance recognizer and method for recognizing specific objects in a query image. Generally, the recognizer and method find repeatable features in the image, and match the repeatable features between a query image and a set of training images. More specifically, the recognizer and method finds features in the query image and then groups all possible combinations of three features in to feature triplets. Small regions or "patches" in the query image, and an affine transformation is applied to the patches to identify any similarity between patches in a query image and training images. The affine transformation is computed using position of neighboring features in each feature triplet. Next, all similar patches are found, and then pairs of images are aligned to determine if the patches agree in the position of the object. If they do, then it is said that object is found and identified.<H recognition, triplets, Object, instance, 7412427.html, Patent, pto, 7412427

Title: Object instance recognition using feature symbol triplets

Abstract: A feature symbol triplets object instance recognizer and method for recognizing specific objects in a query image. Generally, the recognizer and method find repeatable features in the image, and match the repeatable features between a query image and a set of training images. More specifically, the recognizer and method finds features in the query image and then groups all possible combinations of three features in to feature triplets. Small regions or "patches" in the query image, and an affine transformation is applied to the patches to identify any similarity between patches in a query image and training images. The affine transformation is computed using position of neighboring features in each feature triplet. Next, all similar patches are found, and then pairs of images are aligned to determine if the patches agree in the position of the object. If they do, then it is said that object is found and identified.

Patent Number: 7,412,427 Issued on 08/12/2008 to Zitnick, et al.

Inventors: Zitnick; Charles L. (Seattle, WA), Sun; Jie (Atlanta, GA), Szeliski; Richard S. (Bellevue, WA), Winder; Simon A. J. (Seattle, WA)
Assignee: Microsoft Corporation (Redmond, WA)

Appl. No.: 11/342,218

Filed: January 27, 2006

Current U.S. Class: 706/20

Current International Class: G06E 1/00 (20060101); G06E 3/00 (20060101); G06F 15/18 (20060101); G06G 7/00 (20060101)

Field of Search: 706/20

References Cited [Referenced By]

U.S. Patent Documents


6262742	July 2001	Tampieri
6975755	December 2005	Baumberg
2005/0190949	September 2005	Weber

Other References

Lee, Three Dimensional Pattern Recognition Using Feature-Based Indexing and Rule-Based Search, Graduate College University of Nevada Las Vegas, Dec. 2003. cited by examiner .
Unsalan et al., Classifying Land Development in High Resolution Satellite Images Using Straight Line Statistics, 1051-4651/02, 2002, IEEE. cited by examiner .
Brown, M., and Lowe, D.G., "Invariant Features from interest point groups" in British Machine and Vision Conference, Cardiff, Wales (2002), pp. 656-665. cited by other .
Fergus, R., Perona, P., Zisserman, A., "Object class recognition by unsupervised scale-invariant learning", in IEEE Proc. of Computer Vision and Pattern Recognition (2003), pp. 264-271. cited by other .
Lamdan, Y., and Wolfson, H. J., "Geometric hashing: A general and efficient model-based recognition scheme" in Proceedings of the International Conference of Computer Vision (1988), pp. 238-249. cited by other .
Lowe, D.G., "Distinctive image features from scale-invariant keypoints", in Int'l J. of Computer Vision 60 (2004), pp. 91-110. cited by other .
Lowe, D.G., "Local feature view clustering for 3D object recognition" in IEEE Proc. of Computer Vision and Pattern Recognition (2001), pp. 682-688. cited by other .
Lowe, D.G., "Object recognition from local scale-invariant features", in IEEE Proc. of Int'l Conf. on Computer Vision (1999), pp. 1150-1157. cited by other .
Mikolajczyk, K., Schmid, C., "An affine invariant interest point detector", in IEEE Proc. of European Conf. on Computer Vision (2002), pp. 128-142. cited by other .
Mikolajczyk, K., Schmid, C., "A performance evaluation of local descriptors", in IEEE Trans. on Pattern Recognition and Machine Intelligence, Oct. 2005 (vol. 27, No. 10), pp. 1615-1630. cited by other .
Rothganger, F., Lazebnik, S., Schmid, C., Ponce, J., "Object modeling and recognition using local affine-invariant image descriptors and multi-view spatial constraints", Int'l Journal of Computer Vision, To appear--2005, available at: http://lear.inrialpes.fr/pubs/index.php?idAuthor=108. cited by other .
Schmid, C., Mohr, R., "Local gray value invariants for image retrieval", in IEEE Trans. on Pattern Recognition and Machine Intelligence 19 (1997), pp. 530-534. cited by other .
Sivic, J., Russell, B.C., Efros, A.A., Zisserman, A., Freeman, W.T., "Discovering objects and their location in images", in IEEE Proc. of Int'l Conf. on Computer Vision, Oct. 2005. cited by other .
Viola, P., Jones, M., "Rapid object detection using a boosted cascade of simple features", in Proc. CVPR. (2001), pp. 511-518. cited by other .
Weber, M., Welling, M., Perona, P., "Unsupervised learning of models for recognition", in IEEE Proc. of European Conf. on Computer Vision (2000), pp. 18-32. cited by other.

Primary Examiner: Holmes; Michael B
Attorney, Agent or Firm: Lyon & Harr, L.L.P. Fischer; Craig S.

Claims

What is claimed is:

1. A method for recognizing an instance of a specific object in a query image, comprising: finding features in the query image; grouping three of the features into a feature triplet; computing an affine transformation with skew using neighboring feature positions to warp the feature triplet into a geometric shape in canonical space; matching each of the features in the feature triplet with training images to identify the specific object; and displaying to a user a list of training images that match the query image to recognize the specific instance of the specific object in the query image.

2. The method of claim 1, wherein the geometric shape is a non-right triangle.

3. The method of claim 2, wherein the geometric shape is an equilateral triangle, wherein each feature in the feature triplet is a vertex of the equilateral triangle.

4. The method of claim 1, further comprising finding feature descriptors for each of the features in the feature triplet such that each feature's scale, rotation, and skew are described.

5. The method of claim 4, further comprising: assigning a symbol to each feature descriptor, and using a triplet inverse lookup table to match the feature triplet with a feature triplet corresponding to a training image.

6. The method of claim 5, further comprising assigning a combination of three indices to the feature triplet and using the combination to match features using the triplet inverse lookup table.

7. The method of claim 5, further comprising verifying the matching of the features using geometric hashing.

8. The method of claim 5, further comprising: computing a second affine transformation between the query image and the training image using feature positions in the feature triplet and the training image feature triplet; projecting a center of the object on the query image; and designating the object as identified if enough triplets agree on the center of the object.

9. The method of claim 8, further comprising projecting reference points of the feature positions onto a single point, wherein the object is a planar object.

10. The method of claim 8, further comprising projecting reference points of the feature position onto a single line, wherein the object is a non-planar object.

11. A computer-implemented process for recognizing an instance of an object in a query image, comprising: finding features in the query image to obtain found features; grouping the found features into features triplets; computing an affine transformation with skew using neighboring feature positions to warp each of the feature triplets into canonical space to form an equilateral triangle; matching the feature triplets with feature triplets in a training image; and displaying to a user a list of training images that match the query image.

12. The computer-implemented process as set forth in claim 11, further comprising: defining a region of an image as a footprint of a feature; and using a group of three footprints of each of the three features in the feature triplet to compute feature descriptors the feature triplet.

13. The computer-implemented process as set forth in claim 12, wherein warping each of the feature triplets into canonical space further comprises: using an affine transformation to warp the footprints of the feature triplets into canonical space to form the equilateral triangle; and using the affine transformation to warp the warped footprints in canonical space back into an original frame.

14. The computer-implemented process as set forth in claim 11, further comprising: clustering the feature triplets into clusters; and assigning an index symbol to each of the found features, wherein the index indicates which of the clusters a feature belongs.

15. The computer-implemented process as set forth in claim 11, further comprising: defining a feature triplet combination for each of the feature triplets; generating in inverse lookup table such that each entry contains a feature triplet combination having three indices; and finding potential matches between the feature triplets and the feature triplets in the training image.

16. The computer-implemented process as set forth in claim 15, further comprising verifying the potential matches using geometric hashing to compute the affine transformation between each pair of potential matches.

17. A computer-readable storage medium having stored thereon computer-executable instructions for recognizing an instance of an object in a query image, comprising: finding features in the query image; grouping each of the features into all possible combinations of feature triplets, such that each feature triplet contains three features; computing feature descriptors for each of the feature triplets; computing a footprint for each of the features using positions of two neighboring features in feature triplets; and using an affine transformation with skew to warp the footprints of each feature triplet into canonical space, such that three footprints of the feature triplet form an equilateral triangle.

18. The computer-readable storage medium of claim 17, further comprising: clustering the feature triplets into bins, such that each bin is a representative feature and each bin has an index represented by a number; and assigning a feature combination to each feature triplet, such that each feature combination contains three indices corresponding to a bin index.

19. The computer-readable storage medium of claim 18, further comprising determining potential matches between feature triplets in the query image and feature triplets in training images using an inverse lookup table, wherein the inverse lookup table contains a feature combination of three indices in each entry.

20. The computer-readable storage medium of claim 19, further comprising: obtaining reference points in training images; projecting the reference points into the query image using the affine transformation; and verifying that a potential match is match if one of the following occurs: (a) for planar objects, the reference points project to a single point in the query image; (b) for non-planar objects, the reference points project on a line in the query image.

Description

BACKGROUND

Object instance (or known object) recognition is the task of recognizing a specific object. Object instance recognition does not recognize categories of objects, but instead a particular object from a category. By way of example, these specific objects may include specific artwork (such as the Mona Lisa), a specific photograph, the front of a restaurant, or an object on a supermarket shelf.

Object instance recognition remains a challenging problem in computer vision. Literally millions of objects exist, and finding a computationally feasible method for recognizing a particular object can be difficult. Some of the most promising approaches to object instance recognition are feature-based techniques. Feature-based techniques extract local feature descriptors from salient points in an image. Recognition is achieved by matching feature descriptors from a query image with those found from a set of training images. Ambiguous matches are eliminated in a verification stage by matching objects using a global affine transformation.

One problem, however, with feature-based techniques is the difficulty of matching found features with those in the database. The size of the feature database can be quite large. In addition, the feature database scales linearly with the number of known objects. One way commonly used to reduce the computational complexity of this search is to use an approximate nearest neighbor (ANN) technique or a hashing technique. However, the limitations of these two techniques become apparent as the number of objects in the database increases. Another problem is that as the feature space becomes more crowded it becomes increasingly difficult to find correct matches, because several good matches might exist for any feature within a query image.

In large feature databases, the ambiguity of the correctly matching feature most likely is unavoidable. If it is assumed that the feature space will be densely populated, then each feature can be assigned to a cluster instead of finding its single closest match within the database. The set of clusters can be created using a modified K-means clustering algorithm during training. The number of possible clusters can range from 1,000 to over 10,000.

This set of cluster means creates a vocabulary of features. However, one problem is that the resulting symbols can be quite generic and are rarely object dependent. Another problem with the vocabulary of features approach is ensuring that corresponding features across images are assigned to the same symbol. If the feature appearance varies due to image noise or misestimation of position, scale or rotation, differing symbols maybe assigned.

SUMMARY

This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

The feature symbol triplets object instance recognizer and method described herein includes processing and recognizing specific objects in an image. These objects can be any unique object, such as a brand name object, paintings, and landmarks. The feature symbol triplets object instance recognizer and method first finds feature in a query image. The found features then are grouped into groups of three features, called feature symbol triplets (or feature triplets). All possible combinations of three features are generated.

For each of the features a feature descriptors is computed. The feature descriptor describes a feature using, for example, position, scale, and rotation of the feature. The footprint of a feature, which is a small regions or area in the image, is used to compute the feature descriptors. An affine transformation then is computed from these feature triplets using neighboring feature positions. The affine transformation not only describes the position, scale and rotation of a feature, but also the skew of the feature. The affine transformation is used to warp the feature triplets into canonical space to form a geometric shape that is not a right triangle, such as an equilateral triangle. For the equilateral triangle, each of the three features of the feature triplet form the vertices of the equilateral triangle. The affine transformation then is used to warp the feature footprints back in to the original frame.

The features are grouped into clusters or bins using a clustering technique. Each bins is assigned a number. A feature combination is generated for each feature triplet which is a combination of three indices corresponding to bin numbers of each of the three features contained in the feature triplet. To avoid ambiguity, if two features in a feature triplet have the same index, the triplet is not used.

Potential matches between feature triplets in the query image and feature triplets in training images then are found using an inverse lookup table. The inverse lookup table contains the feature combination of three indices at each entry in the table. The potential matches are verified by examining the spatial relationship between pairs of triplets. In particular, reference points are found in the training images, and then projected into the query image using the affine transformation. If the object is a planar object, a potential match is verified if the projected reference points lie at a single point in the query image. If the object is a non-planar object, a potential match is verified if the projected reference points lie along a line in the query image.

The feature symbol triplets object instance recognizer and method uses an affine transformation based on feature triplets to warp the feature triplets into an equilateral triangle in canonical space. This warping to an equilateral triangle is symmetric, and the ordering of the triplets does not affect the result. Moreover, as compared to existing methods, there is less overlap of features. Thus, the feature symbol triplets object instance recognizer and method is faster, more efficient, and more reliable than existing techniques.

The feature symbol triplets object instance recognizer and method computes the affine transformations from the neighboring feature positions (such as feature centers) instead of using local properties. This reduces the variance of the features, which achieves greater reliability in matching as compared to existing methods. Moreover, computing affine transformations using neighboring feature positions is more repeatable than using image gradients. This means that the affine transformation as computed by the feature symbol triplets object instance recognizer and method is more repeatable across multiple images.

Computing affine transformations from neighboring feature positions also decreases the feature descriptor density. The scale and orientations of each feature are not computed locally for each feature, but instead they are computed using the three positions of the feature triplet. This means that the features look different from each other, which spreads out the feature descriptor density.

DRAWINGS DESCRIPTION

Referring now to the drawings in which like reference numbers represent corresponding parts throughout:

FIG. 1 illustrates and exemplary implementation of the feature symbol triplets object instance recognizer and method disclosed herein.

FIG. 2 illustrates an exemplary training image set.

FIG. 3 is a block diagram illustrating the details of the feature symbol triplets object instance recognizer shown in FIG. 1.

FIG. 4 is a general flow diagram illustrating the general operation of the feature symbol triplets object instance recognizer shown in FIGS. 1 and 3.

FIG. 5 is a detailed flow diagram illustrating the further details of the feature symbol triplets object instance recognizer method shown in FIG. 4.

FIG. 6A illustrates the standard features and variance for existing object instance recognition techniques.

FIG. 6B illustrates reducing the feature variance.

FIG. 6C illustrates decreasing the feature density.

FIG. 6D illustrates a combined approach of FIGS. 6B and 6C used by the feature symbol triplets object instance recognizer and method to both reduce the feature variance and decrease the feature density.

FIG. 7A illustrates that standard approaches using only a portion of the feature space.

FIG. 7B illustrates using feature triplets, as used by the feature symbol triplets object instance recognizer and method, whereby the features occupy a larger set of the feature space.

FIG. 8A illustrates an original feature triplet in an original frame.

FIG. 8B illustrates the original feature triplet shown in FIG. 8A after warping to a canonical frame with feature footprints.

FIG. 8C illustrates the results of using the affine transformation to warp the features back into the original frame.

FIG. 9A illustrates a triplet with reference point in a training image.

FIG. 9B illustrates the reference point, shown in FIG. 9A, projected to a canonical frame using the same affine transformation.

FIG. 9C illustrates the reference point projected back into the query image.

FIG. 10A illustrates a first training image used in the working example.

FIG. 10B illustrates a first query image used in the working example.

FIG. 10C illustrates a second training image used in the working example.

FIG. 10D illustrates a second query image used in the working example.

FIG. 11 illustrates that the projections of a reference point lie along a line in a query image of the working example.

FIG. 12A illustrates a first ROC curve for the single object database used in the working example.

FIG. 12B illustrates a second ROC curve for the multiple object database used in the working example.

FIG. 13A illustrates a first query image used in the working example.

FIG. 13B illustrates the training images of the objects found in the first query image of FIG. 13A.

FIG. 14A illustrates a second query image used in the working example.

FIG. 14B illustrates the training images of the objects found in the second query image of FIG. 14A.

FIG. 15A illustrates a third query image used in the working example.

FIG. 15B illustrates the training images of the objects found in the third query image of FIG. 15A.

FIG. 16A illustrates a specular object.

FIG. 16B illustrates an object with little texture.

FIG. 16C illustrates a non-planar object.

FIG. 16D illustrates a deformable object.

FIG. 17 illustrates an example of a suitable computing system environment in which the feature symbol triplets object instance recognizer and method may be implemented.

DETAILED DESCRIPTION

In the following description of the feature symbol triplets object instance recognizer and method, reference is made to the accompanying drawings, which form a part thereof, and in which is shown by way of illustration a specific example whereby the feature symbol triplets object instance recognizer and method may be practiced. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the claimed subject matter.

I. Introduction

Object recognition remains a challenging problem in computer vision. Object instance recognition is the task of recognizing specific objects, such as cereal boxes or soda cans. Billions of such unique objects occupy the world, and finding a computationally feasible method for recognition can be difficult. However, recognizing these objects in an accurate and efficient manner is an important task for many applications.

Ideally, the computational costs should scale with the complexity of the testing image, and not the size of the object database. In order to accomplish this goal, the feature symbol triplets object instance recognizer and method described herein achieves detection and recognition of objects based on triplets of feature descriptors. Each feature is given a label based on a modified K-means clustering algorithm. Object matching is then done by inverse lookup within a table of possible triplets.

The ambiguity of the matches is further reduced by having each triplet vote on its proposed object center. For planar objects, the proposed object centers should cluster at a single point. In general, assuming orthographic projection, the proposed centers will lie along a line. If enough triplets are in agreement on a specific object's center, the object is labeled as detected.

II. General Overview

The feature symbol triplets object instance recognizer and method works particularly well at finding highly-textured, non-deformable objects in an image. These highly-textured, non-deformable objects include cereal boxes and other grocery store items.

The general idea behind the feature symbol triplets object instance recognizer and method is to find repeatable features, and match the repeatable features between a query image and training images. It is desirable that the features are unique. A feature should be unique enough such that the feature is not found on another object. This allows the feature to be distinguished from other features. By way of example, a registered trademark or logo could be a repeatable feature.

More specifically, the feature symbol triplets object instance recognizer and method finds small regions or "patches" in the image, and applies a transformation to the patches in order to identify any similarity between patches in a query image and patches in training images. Next, all similar patches are found, and then pairs of images are aligned to determine if the patches agree in the position of the object. If they do, then it is said that object is found.

FIG. 1 illustrates and exemplary implementation of the feature symbol triplets object instance recognizer and method disclosed herein. It should be noted that FIG. 1 is merely one of several ways in which the feature symbol triplets object instance recognizer and method may implemented and used.

Referring to FIG. 1, the feature symbol triplets object instance recognizer 100 resides on a computing device 110. In general, the feature symbol triplets object instance recognizer 100 finds repeatable features between a query image and training images in order to identify an instance of an object in the query image. More specifically, as shown in FIG. 1, the feature symbol triplets object instance recognizer 100 inputs a query image containing at least one object 120. In addition, a training image set 130 is input to the feature symbol triplets object instance recognizer 100. The training image set 130 contains a plurality of training images, which contains objects that may be in the query image 120.

FIG. 2 illustrates an exemplary training image set 200, where the exemplary training image set 200 is an example of the training image set 130. The exemplary training image set 200 contains 24 training images. Each of these training images contains an image of an object.

Referring back to FIG. 1, the query image containing at least one object 120 and the training image set 130 are processed by the feature symbol triplets object instance recognizer 100. As described in detail below, the feature symbol triplets object instance recognizer 100 determines repeatable features in the query image 120 that matches one of the training images in the training image set 130. The output of the feature symbol triplets object instance recognizer 100 is a list of training images that match the query image 140.

III. Structural Overview

The structure of the feature symbol triplets object instance recognizer 100 now will be discussed. In order to more fully understand the structure of the feature symbol triplets object instance recognizer 100, the details of an exemplary embodiment are presented. However, it should be noted that this exemplary embodiment is only one of several ways in which the feature symbol triplets object instance recognizer 100 may be implemented and used.

FIG. 3 is a block diagram illustrating the details of the feature symbol triplets object instance recognizer 100 shown in FIG. 1. In general, the feature symbol triplets object instance recognizer 100 processes a query image 300 and compares it to a training image set 310 containing a plurality of images. A list of training images 315 that match the query image 300 then are output from the feature symbol triplets object instance recognizer 100.

The feature symbol triplets object instance recognizer 100 resides on the computing device 110. The feature symbol triplets object instance recognizer 100 includes a feature triplet module 320, which generates feature triplets 330 in the query image 300. A feature descriptor module 340 defines feature descriptors 350 for the feature triplets 330. An inverse lookup table 360 is used to find the training images in the training image set 310 that contain identical patches to the query image 300. A spatial arrangement verification module 370 further verifies that the patches are identical, based on spatial arrangement.

The output of the feature symbol triplets object instance recognizer 100 is the list of training images 315 that match the query image 300. In this example, as shown in FIG. 3, the list of training images 315 includes a first matching object 375, a second matching object 380, and a third matching object 385. It should be noted that the first 375, second 380, and third matching objects 385 are also found in the query image 300.

IV. Operational Overview

The operation of the feature symbol triplets object instance recognizer 100 and method used therein shown in FIGS. 1 and 3 now will be discussed. FIG. 4 is a general flow diagram illustrating the general operation of the feature symbol triplets object instance recognizer shown in FIGS. 1 and 3. In general, the feature symbol triplets object instance recognition method compares finds objects in a query image by comparing portions of the object to training images. If the object in the query images matches one of the training images, then a match is found and the object is identified

In particular, as shown in FIG. 4, the feature symbol triplets object instance recognition method begins by finding features in a query image, where the query object contains at least one object (box 400). Three of the features found are grouped into a feature triplet (box 410). Next, an affine transformation is computed using neighboring feature positions (box 420). In other words, for each of the three features in the feature triplet the affine transformation for that feature is computed using its neighboring other two features in the triplet.

The computed affine transformation is used to warp the feature triplet into a geometric shape in canonical space (box 430). This geometric shape takes the form of a triangle. In a one embodiment, the geometric shape is an equilateral triangle. Next, each of the features in the warped feature triplet are matched with training images (box 440). The result of this matching is an identified object that is output (box 450).

FIG. 5 is a detailed flow diagram illustrating the further details of the feature symbol triplets object instance recognizer method shown in FIG. 4. As shown in FIG. 5, the feature symbol triplets object instance recognition method begins by inputting a query image to be processed (box 500). The query image is the image that a user sends to the feature symbol triplets object instance recognizer 100. The user has a query image and wants to know what is in the image, or something about the image.

The method then finds features in the query images (box 510), and then groups the features in to feature triplets (box 520). The use of feature triplets by the feature symbol triplets object instance recognition method serves two purposes. First, the space of possible feature descriptors and their repeatability are increased. Second, by assigning features to symbols and using an inverse lookup table, possible matches can be found efficiently. The computational cost of finding features is increased over standard single feature existing methods, but the cost is independent of the training database size. Once the feature symbols are found, matching training images to the query image is very efficient, and scales to large databases of objects.

Next, the feature symbol triplets object instance recognition method computes feature descriptors of the feature triplets (box 530). To increase the reliability of each feature descriptor, the local image appearance is warped using an affine transformation computed from the triplet's feature positions. Thus, a feature location will have a different descriptor for each triplet. One advantage of this is that the repeatability of the feature descriptors is increased, while also increasing the area in feature space in which the descriptors can be contained.

Two popular techniques for finding repeatable features in an image are a scale invariant feature transform (SIFT) technique, and a Harris corner feature technique. The SIFT technique gives a rotation, scale, and orientation of a feature. In particular, an image patch of a feature has a particular size (such as 64.times.64 pixels). If the patch is scaled larger, the sampling will be larger, and if the patch is scaled smaller then the sampling is smaller. In the patch there also is rotation. The SIFT feature descriptor ensures that orientation is consistent. Thus, a SIFT feature descriptor gives position, scale, and rotation of each feature. It should be noted that with the SIFT technique, the position of a feature is found fairly accurately, while the scale and rotation are much more difficult to compute. Thus, there is much more accuracy in position than in scale and rotation.

There typically will be hundreds of these repeatable features in the query image. A standard way perform object instance recognition is to find all the features, determine which features look similar, and take those features and try to find some transformation that lines up the features. If this can be found, then it can be said the object is found.

There are two problems with this standard way. First, when scaling to large databases, it is desirable to use a feature that is repeatable and unique. The problem is that the variance is large for each feature, especially of the scale and rotation. If the scale and rotation are off even slightly, the one feature will be off from the feature trying to be matched. So the two features are matched, they will not be quite equal, especially because the scale and rotation are prone to error. Thus, it is desirable to decrease the variance.

Second, in feature space the area in which features can exist are limited. If the uniqueness of each feature is to be increased, there are two things that can be done. First, increase the feature space so that the features lie in a larger area. This is called decreasing the "feature density". Two, makes the variance smaller so that way each feature is more specific. The whole goal is to increase the reliability and uniqueness of the features to increase the speed at which objects can be matched and also increase the number of objects that are matched.

As was stated earlier, the location of the features typically is found well, but the scale and rotation are much more prone to error. Instead of looking at each feature individually, the feature symbol triplets object instance recognition method examines triplets of features, or groups of three features. These three features can then be warped to form an equilateral triangle.

One difference between the feature symbol triplets object instance recognizer and method described herein and the SIFT technique is that SIFT only describes the scale and rotation of a feature. But the affine transformation used by the feature symbol triplets object instance recognition method also describes the skew of a feature. The advantage of using an affine transformation with skew is that skew better represents a 2D representation of a 3D image than does only scale and rotation.

Another advantage of the feature symbol triplets object instance recognition method is that the affine transformation is not computed based on local image gradients. Technique that compute affine transformations using local image gradients are not as informative as using the feature positions. Using the feature positions with an affine transformation, as is done by the feature symbol triplets object instance recognition method, instead of using local image gradients with an affine transformation, yields a more reliable and repeatable transformation.

In addition, the feature symbol triplets object instance recognition method warps the feature triplets into an equilateral triangle in canonical space. One advantage of using equilateral triangles in canonical space is symmetry. The three feature triplets warped into an equilateral triangle are symmetric, and there ordering does not affect the result. Another advantage of warping feature triplets to equilateral triangles in canonical space is that the equation for computing the affine transformation is simpler. Yet another advantage of using equilateral triangles is that there is less repetition because there is less overlap of features, as compared to non-equilateral triangle techniques.

Each feature descriptor then is assigned a symbol (box 540). Each feature is assigned to a cluster instead of find its single closest match within the database. One way a set of clusters is created is by using a modified K-means clustering technique during training. By way of example, the number of clusters can range from 1,000 to more than 10,000.

This set of clusters creates a vocabulary of features. The resulting symbols can be quite generic and are rarely object dependent. To resolve ambiguity in matching symbols, the feature symbol triplets object instance recognition method matches feature triplets (or groups of three symbols). For each triplets, potential matches are found using an inverse lookup table (box 550). For each triplet, the object within which they exist are stored using the inverse lookup table. This allows the feature symbol triplets object instance recognition method to efficiently find all potentially matching objects.

Since the same triplet might appear in multiple objects, the feature symbol triplets object instance recognition method verifies matches using geometric hashing (box 560). For each pair of potential matching triplets, positions of the three features are used to compute an affine transformation between the query and training images. A center of the object then is projected on the query image. If enough triplets agree on the position of the object center, then the object is labeled as detected.

V. Operational Details

The details of the feature symbol triplets object instance recognition method now will be discussed.

Generating Feature Triplets

In current object instance recognition techniques, each object is represented as a set of training images. The images in turn are then represented as a bag of local feature descriptors, f.sub.i.epsilon.{f.sub.1, . . . , f.sub.n}. Each descriptor is based on local image statistics, such as edge magnitudes. The accuracy of these methods largely depends of the distinctiveness of each separate feature. As a result, large databases of features are needed. For example, one database of an existing technique contained 40,000 features from 32 images.

As the feature database becomes more crowded, many erroneous matches can exist within a small neighborhood of the correct match. The instant technique defines the variance of the correct corresponding feature descriptors across images as the feature variance, .sigma..sub.F. The feature variance depends on the amount of image noise and the reliability of the computed position, scale and rotation of the features.

FIGS. 6A to 6D illustrate feature density using various techniques. It should be noted that in FIGS. 6A to 6D, features are represented as black dots in feature space, a query feature 610 is shown as a red dot, and the extent of a first feature variance 610 is shown as the dotted red circle. FIG. 6A illustrates the standard features and variance for some existing object instance recognition techniques. As shown in FIG. 6A, multiple features may lie within the feature variance 610 of the query feature 600, which results in ambiguous matches.

There are two approaches to reducing the chances of a false match. In a first approach, the repeatability of the features can be increased, which reduces the feature variance. As shown in FIG. 6B, this means that the extent of a second feature variance 620 around the query feature is reduced compared to the first feature variance 610. In a second approach, the feature density is decreased. This means that the space in which features exist can be increased, so that fewer features lie close to the correct match. This effectively reduces the feature density. As shown in FIG. 6C, a third feature variance 630 around the query feature 600 has the same diameter as the first feature variance 610 shown in FIG. 6A, but the number of features within the third feature variance 630 is reduced compared to the first feature variance 610. Standard rotation and scale invariant methods attempt to find locally similar image patches. As a result, the feature descriptors are more similar, and only a fraction of the entire feature space will be occupied, as shown in FIGS. 6A and 6B.

FIGS. 7A and 7B illustrate the effects of invariant approaches. FIG. 7A illustrates that standard approaches only use a portion of the feature space. In particular, standard approaches using rotation and scale invariance attempt to find locally similar patterns. As shown in FIG. 7A, the scale and rotation invariance will lead to many features appearing similar. In contrast, invariant approaches using triplets return features based on neighboring feature positions. As a result, as shown in FIG. 7B, these same features will have differing features descriptors.

To address this problem, the feature symbol triplets object instance recognizer uses a method that improves the repeatability of the features while also increasing the space in which they exist. As shown in FIG. 6D, this method incorporates both approaches shown in FIGS. 6B and 6C. In other words, this method both reduces the variance and decreases feature density by increasing the area that features can occupy. As shown in FIG. 6D, the fourth feature variance 640 around the query feature 600 illustrates both a smaller variance and reduced feature density.

The method of the feature symbol triplets object instance recognizer relies on a novel technique for finding feature footprints. The footprint of a feature is the area, usually a rectangular region, of the image used to compute the feature descriptor. In existing techniques, the footprint is computed from the feature's position, scale and rotation. The feature symbol triplets object instance recognizer and method instead compute the footprint using groups of three features, or triplets. Using the new footprints, standard feature descriptors, such as SIFT feature descriptors, then are used.

The set of feature triplets, designated as T, consists of all groups of three features that exist within a certain distance of each other in pixel and scale space. The details of one way of creating the triplets can be found below. Any resulting triplets where the feature positions form an overly narrow triangle are discarded. More specifically, triplets in which the ratio of the longest distance between features to the sum of the two shortest distances is greater than a distance threshold, T=0.75, are removed.

The feature symbol triplets object instance recognizer and method uses the feature positions, which are typically computed more accurately than the scale and orientation, to compute an affine transformation, A.sub.i, from image space into a canonical frame. Within the canonical frame, the three points are warped to positions (0,0), (-1, sqrt(3)), (1, sqrt(3)). If the position of feature f.sub.i,j.epsilon.t.sub.i is p.sub.i,j=(x.sub.i,j, y.sub.i,j) for j.epsilon.{0,1,2}, then:

.function..function..function. ##EQU00001##

FIGS. 8A to 8C illustrate finding feature footprints using feature triplets. More specifically, FIG. 8A illustrates an original feature triplet 800 in an original frame 810 having three features, f.sub.1, f.sub.2, and f.sub.3. It should be noted that the lines on each of the features represent the orientation of the object. They are used when sampling, to align the features. The three features can be warped into a canonical frame (such as into an equilateral triangle).

Whereas existing techniques use an area that an image patch was sampled from, the feature symbol triplets object instance recognizer and method includes a novel technique for finding the box. Instead of using scale and rotation of each feature, the feature symbol triplets object instance recognizer and method uses three boxes surrounding each of the three features canonical space.

FIG. 8B illustrates the original feature triplet 800 after warping to a canonical frame 820 with feature footprints. As shown in FIG. 8B, this creates a equilateral triangle feature triplet 830. More specifically, the three points of the features are specifically chosen for the canonical frame so that they form an equilateral triangle 840, shown by the dotted line in FIG. 8B. In other words, each of the features of the equilateral triangle feature triplet 830 are vertices of the equilateral triangle 840. It should be noted that in FIG. 8B, feature f.sub.i,0 is mapped to (0,0). As shown in FIG. 8B, the orientation of each box is pointing towards the center.

After warping to the equilateral triangle 840 in the canonical frame 820, an affine transformation is used to warp the feature footprints back into the original frame 810. FIG. 8C illustrates the results of using the affine transformation to warp the features back into the original frame 810. As shown in FIG. 8C, a transformed feature triplet 850 is in the original frame 810. It should be noted that the feature symbol triplets object instance recognizer and method goes from image space to canonical space, then back to image space. The patches become the patches of the image that were actually sampled to find the feature. In other words, they become the areas of the image that was sampled to find the feature. In the working example, the size of the patches or samples were 8.times.8 (or 64) samples.

Next, A.sub.i is computed by:

.function. ##EQU00002## Within the warped frame 820 shown in FIG. 8B, the feature footprints of the three feature descriptors are placed at the corners of the equilateral triangle. In addition, the orientations of the three feature descriptors are pointing towards the center of the equilateral triangle. Within the canonical frame, the size of a footprint's side is 2, the same as the distance between feature locations.

Using A.sub.i, the feature descriptors within the triplet are invariant to affine transformations between images. As a result, the feature variance of correctly corresponding descriptors across images should decrease over simpler scale and rotation models. Affine invariant features have also been proposed for Harris corner detectors using image gradients. However, if there is not enough local gradient information, the computed affine transformations may not be robust.

Even though the triplet features are invariant to more general affine transformations, and not just scale and rotation, the space which the descriptors can occupy is larger. This is due to the affine transformations being computed using neighboring feature positions and not local image properties. For example, in FIG. 7A, both features will have the same descriptor if their scales and rotations are computed from local image gradients. On the other hand, with the triplet approach used by the feature symbol triplets object instance recognizer and method, as shown in FIG. 7B the descriptors will vary based on the location of the neighboring features. As a result, the possible area in feature space that can be occupied by the feature descriptors is larger, as shown in FIG. 6D.

Matching Feature Triplets

The previous section described how feature triplets are created and how their feature positions are used to find affine invariant descriptor footprints. The final result is a set of three SIFT feature descriptors for each triplet. In this section, the technique used by the feature symbol triplets object instance recognizer and method to efficiently matching triplets across images is described.

The number of feature triplets is typically much larger than the number of features. By way of example, for an average image of 300 features, there exists

.times..times..times..times. ##EQU00003## possible feature triplets. Since the feature symbol triplets object instance recognizer and method limits the set of possible triplets based on the relative positions and scales of features, the number of triplets is reduced to about 10,000. Given a large training set, a database of descriptors would be quite crowded. If an attempt is made to find correct corresponding features, mismatches are inevitable. This will be the case even though the space in which the triplet features can exist is larger.

Therefore, instead of storing all feature descriptors within the training data set, the feature symbol triplets object instance recognizer and method groups features of similar appearance into clusters. The cluster centers S=s.sub.1, . . . , s.sub.N form a vocabulary of symbols over the set of descriptors. Each descriptor f.sub.i,j in a query image is then mapped m(f.sub.i,j)=s.sub.k to the closet symbol. Clustering of features for generalization can be useful for object categorization. However, the quantization of the feature space reduces the distinctiveness of features, and as a result, its usefulness for object instance recognition.

While the descriptiveness of each individual feature is reduced, each feature triplet, t.sub.i, will have three symbols, s.sub.i,0, s.sub.i,1, s.sub.i,2, associated with it. Given the large number of possible triplets (on the order of 1,000.sup.3), the uniqueness of each triplet is increased over single features. As a result, the number of training images that contain a specific triplet will be much smaller than those that contain any single feature. Using an inverse lookup table that is described below, all training images that contain the same triplet can be found efficiently. However, before describing the inverse lookup table, the method for clustering feature descriptors used by the feature symbol triplets object instance recognizer and method first will be described.

Clustering Feature Descriptors

There are two goals to clustering feature descriptors. The first goal is to have as many feature clusters as possible. The sparseness and efficiency of the inverse lookup table used by the feature symbol triplets object instance recognizer and method increases as the number of symbols or clusters increases The second goal is, given two corresponding features across images, to have them both be assigned to the same symbol or cluster. These two goals must be balanced, since the more clusters that exist, the more likely corresponding features will be assigned to different clusters.

Ideally, the feature descriptors group together into easily identified clusters. Unfortunately, feature descriptors are more evenly distributed as shown in FIG. 6D. Thus, finding appropriate cluster boundaries is difficult.

Given the relatively uniform distribution of feature descriptors, the spacing between clusters is as important as their exact position. To minimize the chances of corresponding features being assigned to different symbols, the feature symbol triplets object instance recognizer and method enforces a rule that the variance of feature positions within a cluster must be greater than some multiple of the variance between corresponding features across images. Thus, the feature symbol triplets object instance recognizer and method modifies the standard K-means algorithm that iteratively groups descriptors into clusters, by enforcing a certain separation between clusters. After each iteration, any clusters whose centers are less than .beta..sigma..sub.F apart, are merged together. To maintain a constant number of clusters, any merged cluster is assigned a new center chosen randomly from the descriptor set. In a working example, .beta..rho..sub.F=0.03. This provides well-distributed features among the clusters.

In the working example, the SIFT feature descriptor had 128 values (or a 128-dimensional feature descriptor). The desire is to find all matching triplets in the set of training images that match a triplet in the query image. This is accomplished by matching the three feature descriptors within the triplets.

In order to be efficient, the features were clustered into 1200 bins, and an index was assigned to each feature. The index was assigned by defining feature symbols (or words). Thus, 1200 representative features were defined. Then, for each feature in the query image, the closest of the 1200 representative features that the feature lies closest to was found. That index was assigned to the feature.

Comparing the feature against each of the 1200 representative features can be time consuming. In order to save time, the working example used a hierarchical technique, which works by taking the 128-D vector and shrinking it down to an 8-D vector by averaging together certain indexes. It should be noted that other technique can be used, such as hashing techniques or multi-resolution techniques. It the feature was within a certain threshold, the next level was where the feature was compared to all 128 representative features. In other words, the feature was compared on a rough scale, and, if the feature was close, then it was examined on a finer scale.

Before a lookup was performed, the feature combinations were reordered from smallest to highest, to avoid looking up all the combinations of numbers. By way of example, a feature triplet combination of (987, 50, 113) was reordered as (50, 113, 987). It should be noted that if two features were assigned to the same index, the triplet was not used, since its ordering was ambiguous.

Inverse Lookup Table

At this point each feature in the query image had an index. The working example then created a large 3-D table (1200.sup.3 different entries), known as an inverse look-up table. A triplet having a combination, such as (50, 113, 987), is selected and then it was found which triplets in the training data had the same combination of features. For each entry in the inverse lookup table, the table returned a list of training images that also contained the matching feature. The working example then found the training image having the most matching feature triplets.

Given a triplet t.sub.i with symbols s.sub.i,0, s.sub.i, 1, s.sub.i,2, it is desirable to efficiently find all training images with similar triplets. In order to accomplish this goal, the feature symbol triplets object instance recognizer and method uses an inverse lookup table. For each possible combination of three symbols, an index is stored of every training image that contains a triplet with the same symbols. Thus, if there are N symbols, the lookup table will contain N.sup.3 entries. Given a large size of N (typically over 1000), most entries within the lookup table will be empty. A sparse matrix representation is used for the table to reduce memory requirements. To ensure all rotationally symmetric triplets are grouped together, the symbols are reordered in ascending order, s.sub.i,0<s.sub.i,1<s.sub.i,2, before lookup. If more than one feature is assigned the same symbol, the mapping between triplet features is ambiguous. Since a unique mapping is needed in the verification stage (which is discussed below), feature symbol triplets object instance recognizer and method discards these triplets.

One possible method for object detection is to store the probability of each triplet t.sub.i, given the object O.sub.j, P(t.sub.i|O.sub.j). Assuming the triplets are independent, the likelihood of each object can be computed as:

.function..varies..function..times..di-elect cons..times..function..function. ##EQU00004## where P(t.sub.i|O.sub.j) is equal to some small value, .epsilon., when the feature triplet has not been observed for the object.

If objects are detected based on the threshold values of equation (3), the precision and recall results would be quite poor. While the use of triplets increases the descriptiveness over the use of single symbols, this "bag of words" approach will result in many ambiguous matches. For this reason, the feature symbol triplets object instance recognizer and method does not use this approach. Instead, as described in the next section, the feature symbol triplets object instance recognizer and method uses relative feature positions as well as feature symbols to find reliable matches.

Object Verification

Since the symbols within a feature triplet are not unique to a specific object, additional constraints are needed to guarantee a correct match. One possibility is to use the spatial relationship between triplets. A global affine model could be assumed for the objects, and then sets of triplets could be found that vote for the same object and have similar affine transformations using a Hough transform or RANSAC. This approach works well for objects with a single dominant plane, such as cereal boxes or books. However, the global affine model is violated for non-planar objects or when there is significant projective distortion.

Instead of assuming a single global affine model, the feature symbol triplets object instance recognizer and method makes use of a geometric hashing technique that computes an affine transformation between each pair of matching triplets. Given a reference point, p.sub.R within a training image I.sub.j (usually assumed to be the object center), the feature symbol triplets object instance recognizer and method projects the point into the query image using the computed affine transformation. If an object is present, the set of projected points from each matching triplet pair will obey certain relationships, which is discuss in detail in the following sections.

Projecting Reference Points

As we discussed above, the feature symbol triplets object instance recognizer and method compute an affine transformation, A.sub.i, which projects a triplet t.sub.i into a canonical frame. Using the same affine transformation, the feature symbol triplets object instance recognizer and method projects a reference point, p.sub.R, into the same canonical frame. FIGS. 9A to 9C illustrate the reference point projection technique used by the feature symbol triplets object instance recognizer and method. FIG. 9A illustrates a triplet 900 with reference point, p.sub.R, in a training image 910. FIG. 9B illustrates the reference point, p.sub.R, projected to canonical frame A.sub.ip.sub.R 920, using the same affine transformation as previously used. FIG. 9C illustrates the reference point p'.sub.R=A'.sub.i.sup.-1A.sub.ip.sub.R projected into the query image 930.

Given a matching triplet t'.sub.i in another image with corresponding affine transformation A'.sub.i, The reference point p.sub.R can be projected from one image into another, as shown in FIGS. 9A to 9C, using the equation: p'.sub.R=A'.sub.i.sup.-1A.sub.ip.sub.R (4) The reference point p.sub.R is usually assumed to be the object center in training image I.sub.j. If the object is roughly centered in the image, the image center may be used.

To verify the detection of objects in a query image, the reference point needs to be projected using each triplet. Instead of storing the entire matrix A.sub.i in the inverse lookup table for each triplet in the training data set, the feature symbol triplets object instance recognizer and method stores the location of the reference point in the canonical frame, A.sub.ip.sub.R.

Planar Objects

For a planar object with an orthographic plus scale camera model, the transformation from a training image to an observed image can be modeled using a global affine transformation. In many cases, the more general projective camera model can also be well approximated locally using this affine model. Assuming an object can be modeled using a global affine transformation A*, all correctly matching triplets have an affine transformation such that A'.sub.-1A.sub.i=A*. As a result, all of the projected reference points p'.sub.R lie at a single point.

FIGS. 10A to 10D illustrate an example of projected reference points. FIG. 10A illustrates a first training image 1000, and FIG. 10B illustrates a first query image 1010. FIG. 10C illustrates a second training image 1020, and FIG. 10D illustrates a second query image 1030. In FIGS. 10A and 10C, the reference points are shown as green crosses in the first 1000 and second 1020 training images. In FIGS. 10B and 10D, the projected reference points are shown as green dots in the first 1010 and second 1030 query images.

Object detection for planar objects then can be accomplished using a simple two-dimensional (2-D) histogram binning technique called geometric hashing. An entry in the histogram is created for each 8.times.8 block of pixels within the query image. Every projected reference point is then added to the closest 2-D bin and its 8 connected neighbors. The quality of the match is measured by the number of points within the largest bin of the histogram. Even if many incorrectly matched triplets exist, it is unlikely they will vote on the same bin. Thus, most false matches can be easily eliminated.

Non-Planar Objects

Unlike planar objects, the projection of a non-planar object cannot be modeled using a single affine transformation. To understand how this affects the projection of the reference points, how this projection is accomplished will now be reexamined.

Each feature f.sub.k within a triplet t.sub.i has a corresponding unknown 3-D location x.sub.k on the object. Similarly, the three features within a triplet t.sub.i correspond to some 3-D plane, q.sub.i. Since the reference point, p.sub.R, is