Local bi-gram model for object recognition

1. A computer-implemented method for recognizing an object in a query image, comprising:

constructing a local bi-gram model implemented on the computer that has learned objects in a training set of images and represents each of the objects as a local relationship between neighboring matching primitives that are dependent on a single parent node in a tree structure; and

recognizing the object in the query image using tree structure and the local bi-gram model.

2. The computer-implemented method of claim 1 , wherein recognizing the object in the query image further comprises find tree structures in the query image that obey the local bi-gram model.

3. The computer-implemented method of claim 2 , further comprising computing a probability of each tree structure being one of the learned objects in the local bi-gram model.

4. A computer-readable storage medium having computer-executable instructions stored thereon for constructing a local bi-gram model, comprising:

obtaining a training set of images;

performing interest point detection on each image in the training set of images to obtain a plurality of interest points; and

clustering matching primitives obtained from the plurality of interest points to obtain the local bi-gram model.

5. The computer-readable storage medium of claim 4 , further comprising:

generating features from the plurality of interest points; and

generating matching primitives from the features.

6. The computer-readable storage medium of claim 5 , further comprising finding neighboring matching primitives using transition features.

7. The computer-readable storage medium of claim 6 , further comprising transforming the neighboring matching primitives into a canonical frame.

8. The computer-readable storage medium of claim 7 , further comprising projecting other matching primitives into the canonical frame.

9. The computer-readable storage medium of claim 8 , further comprising clustering the neighboring matching primitives and the other matching primitives using a clustering technique to obtain clusters of matching primitives.

10. The computer-readable storage medium of claim 9 , further comprising:

removing outlier matching primitives from the clusters of matching primitives to obtain updated clusters; and

outputting the local bi-gram model containing a representation of local relationships between remaining matching primitives in the updated clusters.

11. A computer-implemented process for recognizing objects in a query image using a local bi-gram model, comprising:

using the computer to find a tree structure of matching primitives in the query image that obeys the local bi-gram model such that spatial relationships between the matching primitives are modeled using local relationships represented by transitional probabilities between neighboring matching primitives;

computing a probability of the tree structure being an object learned by the local bi-gram model; and

outputting results of recognizing the objects based on the probability computation.

12. The computer-implemented process of claim 11 , wherein finding a tree structure further comprises:

randomly assigning each matching primitive in the query image as a tree node of the tree structure; and

selecting a matching primitive, a scale, and an object to determine the probability of the matching primitive being an object given the scale and the object.

13. The computer-implemented process of claim 12 , further comprising:

determining whether a probability of the matching primitive being the object is greater than a probability of the matching primitive being a background; and

if not, then not adding the matching primitive to the tree structure.

14. The computer-implemented process of claim 13 , further comprising:

if so, then adding the matching primitive to a list of matching primitives; and

selecting another matching primitive to examine and processing as above until there are no more matching primitives to examine.

15. The computer-implemented process of claim 14 , further comprising ranking each of the matching primitives in the list of matching primitives based on the probability of being an object.

16. The computer-implemented process of claim 15 , further comprising:

adding a highest-ranking matching primitive to the tree structure as a tree node; and

outputting a tree structure representing the object.

17. The computer-implemented process of claim 11 , wherein computing a probability of the tree structure further comprises computing an initial probability of a root node of the tree structure as a frequency count of each feature in a training image set divided by a total number of images in the training image set.

18. The computer-implemented process of claim 17 , further comprising computing a transitional probability of the object given the tree structure as a probability of the tree structure given the object multiplied by prior probabilities for a list of objects that includes the initial probability.

19. The computer-implemented process of claim 18 , wherein the list of objects includes a background.

20. The computer-implemented process of claim 19 , further comprising:

determining whether the transitional probability is greater than an object threshold;

if so, then classifying the tree structure as the object; and

if not, then classifying the tree structure as a background.