LOCAL BI-GRAM MODEL FOR OBJECT RECOGNITION

[0001] Object recognition is an important area of computer vision. Object recognition includes recognizing classes of objects (object category recognition) and recognizing individual objects (object instance recognition). The goal of object category recognition is to automatically recognize unknown object instances of known categories (such as cars or faces) and assign the object to the correct category. The goal of object instance recognition is to recognize a specific instance of an object (such as a specific car or person).

[0002] Both object category recognition and object instance recognition remain challenging problems in computer vision. Some of the most promising approaches to solving these challenging problems are feature-based techniques. In general, feature-based techniques extract local features or matching primitives from descriptors from salient points in an image. This is achieved by locating “interest points”, which are points in the image having a location, a scale, and sometimes a rotation. The interest points typically have a high variance in each surrounding direction. A feature is an interest point plus interest patch of pixels around and centered on the interest point. A matching primitive can be a set of multiple features grouped together in twos (a doublet), in threes (a triplet), as well as single features (a singlet). A feature is a subset of the set of matching primitives. To be highly discriminative, a feature or matching primitive should be able to be recognized in an image repeatedly. For example, a feature could be a dark spot on a white background, or a corner of an object. Recognition is achieved by matching features from a query image with those found from a set of training images. The effectiveness of these methods relies mainly on the discriminative power of the features.

[0003] Recently techniques that additionally model the spatial relationship of features have shown improved results. This is especially true for object category recognition, where the appearance of features across intra-class objects can vary more dramatically than object instance recognition. Several types of spatial models have been developed, including the constellation model, star models, rigid 3D models, and image-centric or warping techniques. Each of these methods creates a global spatial model for an object, whether they are parts-based, image-based or full three-dimensional (3-D) model. Moreover, another feature-based technique uses a triplet approach to group features into a set of three and then looks for matches. The general idea is to verify the geometric location and the spatial relationship of triplets relative to each other using a global model.

[0004] One drawback, however, to the global spatial model is the need to assume that the object in the image is semi-rigid in space. Any deformation in the global spatial model will reduce object recognition reliability. Another drawback is that the use of a global model typically requires a model of an object for each permutation or variation of the object. For example, if the object is a human face, the global model framework requires a model of a face for each type of face, such as with a mustache, without a mustache, with glasses, without glasses, and so forth. This requires a great deal of models and training data.

[0005] 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.

[0006] The local bi-gram model object recognition system and method includes a local feature-based model for object recognition. This local bi-gram model includes spatial relationships between matching primitives that are modeled using a purely local bi-gram representation consisting of transition probabilities between neighboring primitives. Matching primitives should be both discriminative between different types of objects and predictive of the local structure in an object. To achieve highly efficient object recognition, the local bi-gram model uses both single features (or singlets) as well as sets of two neighboring features (or doublets) or three neighboring features (or triplets) as our matching primitive. By combining features into sets, the discriminative power is increased over single features. Multiple feature positions can also be used to compute robust similarity and affine transformations to better predict the local position of neighboring features. In other words, addition of doublets and triplets provides a highly discriminative matching primitive and a reference frame that is invariant to similarity or affine transformations.

[0007] The local bi-gram model is a local spatial model without any explicit global model of an object. In other words, only the relationship of neighboring features is modeled without any knowledge of their global context. An illustrative analogy can be made between the local bi-gram model and the task of language modeling. Specifically, in language modeling the goal is to model the spatial relationship of words in sentences. Most global language model methods attempt to model the entire sentence structure, such as a noun phrase, a verb phrase, and so forth. Local language models, on the other hand, only attempt to model the structure of neighboring words. One such local language model is the n-gram language model. An n-gram language model uses the previous n−1 words in a sentence to predict the probability of the next word. When n=2, the language model is known as a bi-gram language model. In the language modeling community, these simplistic local techniques have shown respectable results in comparison to the more complex global techniques. Similarly to the n-gram language model, the local bi-gram model object recognition system and method uses a bi-gram model for object recognition. This means that a “word” or matching primitive in the local bi-gram model is only dependent on a single matching primitive preceding it in the model.

[0008] Unlike the one-dimensional problem of language modeling, in which a strict ordering of words is enforced in a string, matching primitives in object recognition have no explicit order. Moreover, multiple matching primitives can be dependent on each other. In order to handle these more complex relationships that are encountered in object recognition, the local bi-gram model object recognition system and method uses a tree structure instead of a string. The tree structure provides an efficient local representation with an inherent ordering that allows for multiple matching primitives to be dependent on a single parent.

[0009] Object recognition includes comparing these tree structures of matching primitives in a query image to the local bi-gram model. Objects are recognized by finding tree structures of matching primitives in a query image that obey the local bi-gram model learned for a specific class of objects. The system and method are able to generate large tree structures of matching primitives corresponding to objects learned by the local bi-gram model across a variety of objects.

[0010] A local bi-gram model can also be found using unsupervised learning. The system and method also are capable of discovering objects unsupervised, even if the objects are deforming and rotating. In other words, the system and method can recognize objects undergoing non-rigid transformations for both object instance recognition and category recognition.

[0011] It should be noted that alternative embodiments are possible, and that steps and elements discussed herein may be changed, added, or eliminated, depending on the particular embodiment. These alternative embodiments include alternative steps and alternative elements that may be used, and structural changes that may be made, without departing from the scope of the invention.

[0036] In the following description of the local bi-gram model object recognition system 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 local bi-gram model object recognition system 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.

[0037] The general idea of the local bi-gram model object recognition system and method is to construct a local bi-gram model representing local relationships between matching primitives and to use that model to recognize an object in a query image. FIG. 1 illustrates an exemplary implementation of the local bi-gram model object recognition system and method disclosed herein. It should be noted that FIG. 1 is merely one of several ways in which the local bi-gram model object recognition system and method may implemented and used.

[0038] Referring to FIG. 1, the local bi-gram model object recognition system 100 resides on a computing device 110. In general, the local bi-gram model object recognition system 100 builds a local bi-gram model and then finds repeatable features between a query image 120 and the local bi-gram model 130. More specifically, as shown in FIG. 1, the local bi-gram model object recognition system 100 first constructs a local bi-gram model. This accomplished in part by using a training image set 140 and having a local bi-gram model module 150 learn objects as local relationships between matching primitives in the training image set 140. The output of the local bi-gram model module 150 is the local bi-gram model 130.

[0039] An object recognition module 160 is used to recognize objects give the local bi-gram model 130. In particular, the query image 120 that may or may not contain an object is input to the object recognition module 160. In addition, the local bi-gram model 130 in input to the object recognition module 160. The module 160 includes a tree structure module 170 and a probability module 180. The tree structure module 170 finds a set of neighboring primitives that obey the local bi-gram model and generates a tree structure. The probability module computes the probability or likelihood that the tree structure represents an object in the query image 120. Results of the object recognition processing regarding the query image 190 are output from the local bi-gram model object recognition system 100.

[0040] By way of example assume that it is desired to find a human face in the query image 120. The face is represented using a local representation, or, in other words, for each matching primitive only the local relationship of the primitive is stored. The local relationship means that for the face all that is done is to store a matching primitive relative to, for example, an eye on the face. Thus, for each matching primitive all the neighboring matching primitives are stored relative to a local reference frame.

[0041] These matching primitives and neighboring matching primitives are used to represent the local bi-gram model of the object. In order to recognize the object in the query image a structure of matching primitives is found that obey the model. This is done by finding tree structures of matching primitives. For example, using the tree structure a matching primitive is found and then tree is branched out to where another matching primitive should be. If another matching primitive is there, then a link between the original matching primitive and the neighboring matching primitive is found. The iterative process continues branching out to create new tree structure that branches out that obeys the model.

[0042] Once the tree structure is built for a set of matching primitives, a probability of an object being a certain object (such as a face) or being the background is computed. Initially, the tree structure has a very high likelihood of being a background. But each time a matching primitive is found that obeys the model the more nodes are found on the tree. This increases the probability of the tree structure being the object (in this case, a face). Thus, if a tree never obtains a certain size, then its probability of being a certain object will never be greater than it being part of the background. Then the results will be that the certain object was not found in the query image. It should be noted that there is no explicit penalty for not finding an object.

[0043] FIG. 2 is a flow diagram illustrating the general operation of the local bi-gram model object recognition system 100 shown in FIG. 1. In general, the local bi-gram model object recognition method generates a local bi-gram model and uses that model to recognize objects in a query image. More specifically, the local bi-gram model object recognition method initially inputs a training set of images (box 200). Next, the local bi-gram model is constructed that has learned object in the training set of images (box 210). The local bi-gram model represents each object as local relationships between neighboring primitives.

[0044] The local bi-gram model object recognition method then finds tree structures of matching primitives in a query image (box 220). The tree structures are such that they obey the local bi-gram model. The method then computes a probability of each tree structure being one of the objects represented in the local bi-gram model (box 230). The method outputs those objects found in the query image (box 240).

[0045] The local bi-gram model object recognition system and method uses a local spatial model without any explicit global model of an object. The local bi-gram model object recognition system and method only models the relationship of neighboring features without knowledge of their global context. An illustrative analogy can be made between the local bi-gram model object recognition system and method and the task of language modeling. In language modeling, the goal is to model the spatial relationship of words in sentences. Most global methods attempt to model the entire sentence structure, noun phrase, verb phrase, and so forth. Local models only attempt to model the structure of neighboring words, such as the n-gram model.

[0046] An n-gram model is a language model that is used to estimate the probability of a sequence of speech units, such as the likelihood of one word following another. An n-gram model uses the previous n−1 words in a sentence to predict the probability of the next word. In the language modeling community, these simplistic local techniques have shown respectable results in comparison to the more complex global techniques. When n=2 the language model is called a bi-gram model. The bi-gram model gives the probability of a subsequent word in a string given the preceding word. Similar to the n-gram language model, the local bi-gram model object recognition system and method uses a bi-gram model for object recognition. In other words, each “word” or matching primitive in the local bi-gram model used by the local bi-gram model object recognition system and method is dependent only on a single word preceding it in the model.

[0047] A critical design element is the choice of matching primitive. This primitive should be both discriminative between different types of objects and predictive of the local structure within an object. Existing methods typically use single features, such as SIFT, for this purpose. In addition to using single features, the local bi-gram model object recognition system and method uses sets of two or three neighboring features as matching primitives. By combining features into sets, the discriminative power is increased over single features. Multiple feature positions can also be used to compute robust similarity and affine transformations to better predict the local position of neighboring features.

[0048] Unlike the one-dimensional problem of language modeling in which a strict ordering of words is enforced in a string, words or matching primitives in object recognition have no explicit order. Moreover, multiple matching primitives can be dependent on each other. To handle this more complex relationship, the local bi-gram model object recognition system and method models the structure of objects using a tree instead of a string. This provides an efficient representation with an inherent ordering that allows for multiple matching primitives to be dependent on a single parent.

[0049] As discussed generally above, the local bi-gram model object recognition both constructs a local bi-gram model and uses that model for object recognition. This is accomplished in two general steps. In particular, a first step includes a learning phase whereby a local bi-gram model is constructed that represents objects found in a set of training images. This local bi-gram model includes a set of frequently-occurring matching primitives along with a prediction of their neighboring primitives. Only the local relationships are stored, without the global context from which they came. Moreover, a second step includes obtaining a query image and finding a set of matching primitives in the query image. These matching primitives are used to build a tree structure of matching primitives, and a search is performed to find a tree structure of matching primitives that obeys the local bi-gram model found in the learning phrase. Each of these two steps now will be discussed in more detail.

[0050] In this section, construction of the local bi-gram model is described. This model represents the local relationships between neighboring match primitives in an image. These local relationships are based on the features' descriptors, as well as their local positions and orientations. By only modeling the local interactions of features, a compact model for deformable objects with large variation of appearance can be created.

[0051] FIG. 3 is a flow diagram illustrating the detailed operation of the local bi-gram module 150 shown in FIG. 1. The operation begins by inputting a training set of images (box 300). Next, the module 150 performs interest point detection to on the training set of images to obtain a plurality of interest points (box 310). The module 150 then generates features from the plurality of interest points (box 320).

[0052] Matching primitives then are generated from the features (box 330). In addition, neighboring matching primitives are found using transition features (box 340). The module 150 then transforms neighboring matching primitives into a canonical frame (box 350). Other primitives then are projected in the canonical frame (box 360). The matching primitives then are clustered using a clustering technique, as described below (box 370), and outlier matching primitives are removed (box 380). The output is the local bi-gram model that contains a representation of local relationships between the remaining neighboring matching primitives (box 390). The local bi-gram model is used by the local bi-gram model object recognition system and method to recognize objects.

[0053] The details of the construction of the local bi-gram model now will be described in further detail in two steps. First, matching primitives and the vocabulary of words created from them are described. Second, the local spatial relationships between the words are learned. These two steps are described in the following sections.

[0054] A matching primitive should be both discriminative between different types of objects, and repeatable within a specific class of object. Existing techniques have used single features such as SIFT, corner detectors, maximally stable extremal regions, and salient regions. The use of single features provides a high level of repeatability. However, the occurrence of these features is not unique to a specific object. This is especially true when the features are discretized into a fixed number of clusters. To increase the discriminative power of matching primitives, multiple features can be used, such as doublets or triplets. While this does reduce their repeatability, their uniqueness to a single object class is increased.

[0055] In one embodiment of the local bi-gram model object recognition system and method, three approaches using either sets of one, two or three SIFT ε features called singlets, doublets and triplets are used as matching primitives. The use of single SIFT features has shown good performance for a variety of object recognition tasks. The grouping of SIFT features provides additional contextual information. By analogy, in language models, seeing “white” or “house” does not necessarily identify an article's topic as politics, but seeing “white” and “house” closely together greatly increases this probability. Similarly in object recognition, the co-occurrence of features increases their discriminative power over each individual feature. Doublets and triplets are found by grouping features that lie within a certain distance of each other both spatially and in scale space. More specifically, if a feature f_i has a scale s_i, the other features in the set must lie within distance αs_i of each other in image space and ±β in log scale space.

[0056] In order to increase matching efficiency and to reduce model complexity, the set of feature descriptors are discretized into a set of fixed size. This set is created by clustering the training feature descriptors using a K-means clustering technique. Some embodiments set K=1000, because this approximate size provides a good tradeoff between repeatability and descriptiveness.

[0057] The vocabulary is created from the n-tuple (nε{1,2,3}) of cluster indices assigned to the feature descriptors. That is, for doublet d_i, with two features f_i¹ and f_i² assigned to clusters c_i¹ and c_i², assign word w_i={c_i¹, c_i²}, w_iεC×C. It is assumed that indices of the clusters are in numerical order, in other words c_i¹<c_i². To remove matching ambiguity, all doublets with repeated cluster indices are removed. Singlet and triplet words are similar except they contain 1 or 3 distinctive cluster indices. Using this technique, singlets, doublets and triplets assigned to the same words can be grouped together.

[0058] FIG. 4 illustrates a first example of a first set of feature triplets assigned to a first word or matching primitive. The feature triplets 400, 410, 420 are shown as triangles on each of the faces. FIG. 5 illustrates a second example of a second set of feature triplets assigned to a second word or matching primitive. The feature triplets 500, 510, 520 are also shown as triangles on each of the faces. The largest theoretical size of the vocabulary is

$\underset{2}{1000}$

for doublets and

$\underset{3}{1000}$

for triplets. In practice, an object will only contain a small fraction of these sets.

[0059] The next task is to learn the local relationships of neighboring matching primitives. FIG. 6 illustrates an example of a neighboring doublet. In particular, as shown in FIG. 6, two doublets, d₁ and d₂, are said to be neighboring if they share a single feature. FIG. 7 illustrates an example of a neighboring triplet. As shown in FIG. 7, two triplets, t₁ and t₂, are said to be neighboring if they share two features. Singlets are neighboring if they lie within a certain distance in image and scale space. This is the same criterion as in the construction of doublets. In each case, there exists one feature in each set not shared by the other set. This feature is called the transition feature of its set with respect to the transition from the other set. More specifically, the transition feature of doublet d_i with respect to the transition from doublet d_j is denoted as f_i(j)≡{f_i¹, f_i²}, and similarly for pairs of singlets and triplets.

[0060] Examples of transition features can be seen in FIGS. 6 and 7. Referring again to FIG. 6, the doublet transition feature 600 is shown by the heavy dashed line. Similarly, referring to FIG. 7, the triplet transition feature 700 is shown by the heavy dashed line.

[0061] The local bi-gram model includes a set of transition probabilities between neighboring primitives, for a given object or an object category O_l. For simplicity, how to compute the doublet transition probability will be discussed first. Since neighboring doublets share all but one feature between them, the task of computing the probability of p(d_i|d_j, O_l) can be reduced to computing p(f_i(j)|d_j, O_l) for all d_iεN_j, where N_j are all neighbors of d_j. A feature f□ contains its location x, orientation θ, and cluster index c, where f□={x,θ,c}. Thus, a doublet d_j includes two features f_j¹ and f_j² with two positions x_j¹ and x_j², orientations θ_j¹ and θ_j², and cluster indices c_j¹ and c_j². In the model the doublet d_j is identified by its corresponding word w_j={c_j¹, c_j²}. Thus,

p(f_i(j)|d_j,O_l)=p({x_i(j),θ_i(j),c_i(j)}|{x_j¹,x_j²,θ_j¹,θ_j²,w_j},O_l).  (1)

[0062] Spatial relationships are modeled conditional on word assignment and are enforced in a canonical frame. FIG. 8 is an illustration of a doublet position in the canonical frame, where x_j¹ projects to (0,0) and x_j² projects to (0,1). This provides invariance up to a similarity transformation (translation, rotation and scale). Let A_j be a 3×3 matrix transforming homogeneous coordinates x_j¹ and x_j² to (0,0) and (0,1), respectively. If {circumflex over (x)}_i(j) and {circumflex over (θ)}_i(j) are feature f_i(j)'s position and orientation in the canonical frame defined by A_j,

p(f_i(j)|d_j,O_l)=p({{acute over (x)}_i(j),{acute over (θ)}_i(j),c_i(j)}|w_j,O_l)  (2)

[0063] The value of equation (2) can be understood by examining a training data set. First, a set of transition features F(w_j) is found from all neighboring doublets to doublets that are assigned to the word w_j in the training data. Next, each transition feature f_kεF(w_j) is projected into the canonical frame based on the neighboring doublets relative positions. FIG. 9 illustrates the projection of the transition features from neighbors for the doublet shown in FIG. 8. The different fill patterns or shadings in FIG. 9 represent different transition features from different clusters obtained using the K-means clustering technique.

[0064] To represent the set of possible transition features, in some embodiments several models may be used, such as a local Gaussian perturbation model or a Gaussian Mixture Model (GMM). The GMM allows the modeling of groups of transition features assigned to the same words using a Gaussian with computed means and variances. Since the number of Gaussians needed to represent the distribution is unknown and varies across doublets, in some embodiments the transition features are clustered using a mean shift clustering technique. For mean shift clustering, features are clustered based on their appearance, position and orientation. The iterative update equation for mean shift clustering as used by the local bi-gram model object recognition system and method is,

$\begin{array}{cc}\left\{{\stackrel{\prime }{x}}_k^t,{\stackrel{\prime }{\theta }}_k^t\right\}=\frac{\begin{array}{c}\sum _i{\stackrel{\prime }{x}}_i\left({\stackrel{\prime }{x}}_i;{\stackrel{\prime }{x}}_k^{t-1},{\sigma }_x^2\right)\\ \left({\stackrel{\prime }{\theta }}_i;{\stackrel{\prime }{\theta }}_k^{t-1},{\sigma }_{\theta }^2\right)\delta \left(c_i,c_k\right)\end{array}}{\begin{array}{c}\sum _i\left({\stackrel{\prime }{x}}_i;{\stackrel{\prime }{x}}_k^{t-1},{\sigma }_x^2\right)\\ \left({\stackrel{\prime }{\theta }}_i;{\stackrel{\prime }{\theta }}_k^{t-1},{\sigma }_{\theta }^2\right)\delta \left(c_i,c_k\right)\end{array}}.& \left(3\right)\end{array}$

[0065] The function N is the standard Normal distribution over the spatial coordinates in the canonical frame. In some embodiments, standard deviations of σ_x=0.4 and σ_θ=0.25^π are used for position and orientation in the canonical frame.

[0066] Features are clustered together based on their assigned cluster indices. Mathematically, this can be written as δ(c_i,c_k)=1 if c_i=c_k and 0 otherwise. Thus, only features assigned to the same cluster indices with similar positions and orientations are clustered together. FIG. 10 illustrates an example of the doublet of FIGS. 8 and 9 after this mean shift clustering. The different shadings and line dashings represent the different clusters.

[0067] To ensure the compactness of the model, only doublets that occur at least ψ times in the training data are kept. Further, clusters of transition features that have less than ω members are discarded. FIG. 11 illustrates the final model of the example of FIGS. 8, 9, and 10 after the thresholding cluster size. The different shadings and line dashings represent different clusters. In some embodiments ψ=3 and ω=3.

[0068] After mean shift clustering, the transition probabilities are represented by a set of Gaussians, each of which is factored into appearance, position and orientation components. This results in a transition probability for p(f_i(j)|d_j) being equal to the summation over all the Gaussian components index by a_i,

$\begin{array}{cc}p\text{(}f_i\left(j\right)d_j,O_l)=\sum _ap\left(a\right)\Delta \left(f_i\left(j\right),c_a\right)\left({\stackrel{\prime }{x}}_i\left(j\right);{\stackrel{\prime }{x}}_a,\sum _x\left(a\right)\right)\left({\stackrel{\prime }{\theta }}_i\left(j\right);{\stackrel{\prime }{\theta }}_a,{{\sigma }_{\theta }\left(a\right)}^2\right)& \left(4\right)\end{array}$

[0069] The similarity in appearance is computed using Δ(f_i(j),c_a), which is described in detail below. The spatial covariance matrix

$\sum _x\left(a\right)$

and orientation variance σ_θ(α)² are computed separately for each Gaussian component in the GMM based on the training data. Note that p(α)^□ is the prior probability for each component in the GMM.

[0070] The transition probabilities for neighboring feature singlets and triplets are learned in the same manner as those learned for doublets. The only exception is how the transform A_j is computed. The similarity transform for the canonical frame of singlets is computed from the feature's position, scale and orientation.

[0071] FIG. 12 is an illustration of a triplet position in the canonical frame, where the three feature positions are projected to the positions (0,0), (−0.5,√{square root over (3)}/2), (0.5,√{square root over (3)}/2) corresponding to an equilateral triangle in the canonical frame. This provides invariance to an affine transformation, and not just a similarity transformation. Once the transition features are projected into the canonical frame, the GMM is computed as described above. In particular, FIG. 13 illustrates the projection of the transition features from neighbors for the triplet shown in FIG. 12. The different fill patterns or shadings in FIG. 13 represent different transition features from different cluster obtained using the K-means clustering technique. FIG. 14 illustrates an example of the triplet of FIGS. 12 and 13 after this mean shift clustering. FIG. 15 illustrates the final model of the example of FIGS. 12, 13, and 14 after the thresholding cluster size. The different shadings and line dashings represent the different clusters.

[0072] FIGS. 16, 17, 18, and 19 illustrate a working example of a set of singlets, doublets and triplets that were found using the local bi-gram model constructed as described above on the Caltech 101 face data set. In particular, FIG. 16 illustrates the input image 1600 to the local bi-gram model object recognition system and method from the Caltech 101 face data set. This data set is well known to those having ordinary skill in the art. FIG. 17 illustrates the frequency of occurrence for singlets given the input image 1600 of FIG. 16. Note that the singlets in FIG. 17 are depicted by circles. The different grayscale shadings encodes the frequency of occurrence for each matching primitive in our model. In FIGS. 17, 18, and 19, a darker grayscale shading indicates low occurrence and a lighter grayscale shading indicates high occurrence. FIG. 18 illustrates the frequency of occurrence for doublets given the input image 1600 of FIG. 16. The doublets in FIG. 18 are represented by lines. Similarly, FIG. 19 illustrates the frequency of occurrence for triplets given the input image 1600 of FIG. 16. The triplets in FIG. 19 are illustrated by triangles. It should be noted in FIG. 19 that the triplets with high occurrence are centered on the face and absent from the background image. This means that the triplets are highly discriminative as compared to the singlets and doublets. Referring again to FIG. 17, it can be seen that singlets are less discriminative than the triplets and doublets and scattered over the face and background image.

[0073] One goal of the local bi-gram model object recognition system and method is to find objects in a new image given a set of matching primitives in the local bi-gram model. In other words, given the local bi-gram object model, this task is transformed into finding a set of neighboring primitives that obey the model. The local bi-gram model object recognition system and method accomplishes this by using an efficient and simple technique that involves using trees of matching primitives. The children in a tree permit the modeling of many possible neighbors that a primitive might have in its two-dimensional (2-D) neighborhood. As a result, the goal generally is transformed into finding a tree of matching primitives with high likelihood of belonging to a specific object.

[0074] FIG. 20 is a flow diagram illustrating the detailed operation of the object recognition module 160 shown in FIG. 1. The operation begins by inputting the local bi-gram model (box 2000) and a query image (box 2010). The module 160 then finds a tree structure of matching primitives in the query image that obey the local bi-gram model (box 2020). Next, a probability is computed of the tree structure being an object learned and represented by the local bi-gram model or being a background (box 2030). The output are results of the object recognition in the query image (box 2040).

[0075] The details of the object recognition module now will be described in further detail in two steps. The first step is finding a tree of neighboring matching primitives (singlets, doublets, or triplets) that have a high probability given the local bi-gram object models. The second step is given a set of matching primitives, determining the object to which they belong. The following discussion will first describe how to compute the probability of an object given a tree, and then describe how to find tree using a greedy technique.

[0076] FIG. 21 is a flow diagram illustrating the detailed operation of the tree structure module 170 shown in FIG. 1. The process begins by randomly assigning each matching primitive in the query image as a root node (box 2100). The module 170 then selects a matching primitive, scale, and an object to determine the probability of the matching primitive being the object given the scale and the object (box 2110).

[0077] A determination then is made as to whether the probability of matching primitive being an object is greater than the probability of the object being a background (box 2120). If the probability is greater that the matching primitive is an object, then the matching primitive is added to a list of matching primitives (box 2130). Otherwise, if the probability is greater that the matching primitive is the background, then the matching primitive is not added to the tree structure (box 2140).

[0078] Another determination then is made as to whether there are more matching primitives to examine (box 2150). If so, then another matching primitive is selected for examination, as outlined above (box 2160). If there are no more matching primitives to examine, then each of the matching primitives is ranked in the matching primitives list based on a matching primitive's probability of being an object (box 2170). The highest-ranking matching primitive in the list then is added to the tree structure as a tree node (box 2180). The output of the process is a tree structure that represents an object (box 2190).

[0079] For clarity, in this discussion assumes that the matching primitive is a doublet. However, the same techniques also apply to singlets and triplets. First, a tree is constructed using a greedy algorithm. Initially, the initial probability for each matching primitive present in the test image is computed. The initial probabilities are computed by marginalizing over all possible objects O in the database using the equation:

$\begin{array}{cc}p\text{(}d_iI)=\sum _lp(d_iO_l)p(O_lI).& \left(5\right)\end{array}$

The doublet with the highest likelihood is used as the root node in the tree. After the tree has grown to its full size, the next most likely doublet is found that was not used in a previous tree. This process is repeated until there are no remaining doublets.

[0080] After the root node is found, the tree is iteratively expanded, picking the most likely doublet to add to the tree at each time step. Given the current tree G_t, the most likely doublet d_j is computed given the current likelihood of the objects O. This is computed by marginalizing over all objects using the equation,

$\begin{array}{cc}p\text{(}d_jG_t)=\sum _lp(d_jP\left(d_j\right),O_l)p(O_lG_t).& \left(6\right)\end{array}$

[0081] The new tree G_t+1 is created by adding the doublet d_j to the tree G_t that maximizes equation (6). Once a new doublet has been added to a tree, the likelihood of the objects within O can be updated using equations (7) and (8), given below.

[0082] Once the likelihoods of the objects are updated, the likelihoods of all possible neighboring doublets to the tree also are updated. New doublets then are iteratively added to the tree until no neighboring doublets in the image have a higher likelihood of belonging to an object than to the background. Since the number of possible doublets can be quite large, empirically computing the background probability is infeasible. In practice, setting the background probability to a constant ε provides reasonable results.

[0083] If the final probability of a tree belonging to an object is greater than it belonging to the background, an object is said to be found. Since the prior probability of the background typically is much higher than that of other objects, a tree must grow to a moderate size before an object's probability is higher than the background.

[0084] FIG. 22 is a flow diagram illustrating the detailed operation of the probability module 180 shown in FIG. 1. The process begins by inputting a tree structure of matching primitives for examination (box 2200). Next, an initial probability of the root node of the tree structure is computed (box 2210). This initial probability is computed as a frequency count of each feature (singlet, doublet, or triplet) in the training image set divided by the total number of image in the training image set. A transitional probability of the object given the tree structure then is computed as a probability of the tree structure given the object times (or multiplied by) the prior probabilities for a list of objects (box 2220). The prior probabilities includes the initial probability and the probability of any preceding nodes in the tree structure. This is represented by equation (7) below. Moreover, in some embodiments one of the objects in the list of objects is the background.

[0085] A determination then is made as to whether the aggregate transitional probabilities of being the object are greater than an object threshold (box 2230). Initially, the probability of the tree structure being a background is high and the probability of the tree structure being the object is low. In this situation the object threshold is not exceeded and the tree structure is classified as a background (box 2240). As the size of the tree structure increase, the probability of the tree structure being a background decreases and the probability of the tree structure being the object increases. Eventually, the tree structure may reach a certain size such that its probability of being the object overcomes the object threshold. In this situation, the tree structure is classified as the object (box 2250). In some embodiments, the object threshold is equal to 0.2. However, in alternate embodiments the object threshold may be adjusted up or down. The object threshold can be adjusted to yield more false positives or more false negatives, whichever is desired. The process then outputs the results of whether the tree structure is a background or the object (box 2260).

[0086] Previously how to find a tree structure with matching primitives belonging to a single object was described. In this section, finding the probability that the tree structure is an object is described. Once again, for clarity it is assumed that the matching primitive is a doublet. However, the same techniques also apply to singlets and triplets.

[0087] More specifically, assume that there is a tree G of matching primitives. For clarity, assume that the matching primitive is a doublet. However, the same techniques also apply to singlets and triplets. Using Bayes Theorem it is found that,

p(O_l|G)∝p(G|O_l)p(O_l)  (7).

The prior probabilities p(O_l) for the objects O_l can be assumed to be uniform, unless addition information is known. For instance, if it is known the image was taken indoors, objects that are more likely to be found indoors can be given higher prior probabilities. Besides the objects that have been modeled, there is also a prior background probability. This background probability p(BG) typically has a value much higher than the objects' prior probabilities, since for most images the majority of doublets and triplets will lie on unknown objects.

[0088] In the tree, each doublet d_i has a parent P(d_i), with the root node of the tree having no parent being P(d_i)=0. Given its tree structure, the likelihood of G can be computed as a product of conditional probabilities,

$\begin{array}{cc}p\text{(}GO_l)=\prod _i^{}p(d_iP\left(d_i\right),O_l).& \left(8\right)\end{array}$

The probability of the root node of the tree is referred to as the initial probability, and all remaining probabilities as transition probabilities within the tree.

[0089] Since the tree provides an implicit ordering of the primitives, the above model can be viewed as a bi-gram model applied to a tree structure. In other words, each primitive depends on its preceding primitive, or its parent in the tree. The transition probabilities can be computed using equation (4) using the local bi-gram object model. The initial probability p(d_i|O_l) of the root node is the normalized frequency count of doublets assigned to the same word as d_i within the object training set.

[0090] In this section, the implementation details of the local bi-gram model object recognition system and method are discussed. For interest point detectors, some embodiments use either SIFT detection or the Harris corner detection across multiple scales. However, it was found that a feature's orientation computed using these methods often were unstable for object category recognition. Thus, in these embodiments the orientation was computed by finding the angle at which the feature's descriptor best matched that of a descriptor cluster mean. For embodiments using the K-means clustering of descriptors, the assignment to clusters also was found by matching over all orientations. For efficiency, some embodiments used only 16 orientations.

[0091] The function Δ(f_i,c) in equation (4) is computed by finding the three closest cluster centers c_i(1), c_i(2), and c_i(3) to f_i's descriptor over all orientations. If d(f_i,c) is the distance between f_i's descriptor and c^th cluster mean, then:

$\begin{array}{cc}\Delta \left(f_i,c\right)=1-\max \left(0,\frac{\left(f_i,c\right)-\left(f_i,c_i\left(1\right)\right)}{\left(f_i,c_i\left(3\right)\right)-\left(f_i,c_i\left(1\right)\right)}\right).& \left(9\right)\end{array}$

Thus, the closest cluster c_i(1) has a value of 1 while the second cluster c_i(2) varies between 0 and 1. For all other values of c, Δ(f_i,c)=0. Using this soft assignment technique, the occurrence of misclassifying feature descriptors to cluster indices is reduced.

[0092] In some embodiments, it has been determined that the probability of a transition feature belonging to the background, used to decide when a tree should stop growing, should be set to p(f_i(j)|BG=0.05 for singlets and p(f_i(j)|BG=0.2 for doublets and triplets. The value is lower for singlets since they occur in general with higher frequency.

[0093] The local bi-gram model object recognition system and method is capable off performing automatic learning. One type of automatic learning is semi-supervised learning. This is taking a collection of images containing an object (such as a face) and learning a model just from them. It is semi-supervised because the system is not actually given the location of the object in the images.

[0094] On the other hand, unsupervised learning takes the same collection of images and includes an equal or greater number of random images. The system then is expected to learn a model. If, for example, the objects are faces, the question is whether the system learns a face model, or whether the system is distracted by all the background images. When using the local bi-gram model object recognition system and method the singlets/doublets/triplets are randomly dispersed and do not co-occur so that the correct model can be learned unsupervised. Unsupervised learning has the advantage that it requires the least amount of human interaction, as compared to supervised learning and manual learning.

[0095] The local bi-gram model object recognition system and method also is capable of automatically recognizing objects. The system and method have shown the ability to build coherent trees from unstructured data. Without supervision, groups corresponding to images were found by the system and method. Moreover, every occurrence of the objects was found, even though some of the objects deformed (face and T-shirt) and pairs of specific instances of the object may not share features (rotating globe).

[0096] The local bi-gram model object recognition system and method is designed to operate in a computing environment. The following discussion is intended to provide a brief, general description of a suitable computing environment in which the local bi-gram model object recognition system and method may be implemented.

[0097] FIG. 23 illustrates an example of a suitable computing system environment in which the local bi-gram model object recognition system and method may be implemented. The computing system environment 2300 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment 2300 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment.

[0098] The local bi-gram model object recognition system and method is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with the local bi-gram model object recognition system and method include, but are not limited to, personal computers, server computers, hand-held, laptop or mobile computer or communications devices such as cell phones and PDA's, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

[0099] The local bi-gram model object recognition system and method may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. The local bi-gram model object recognition system and method may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices. With reference to FIG. 23, an exemplary system for the local bi-gram model object recognition system and method includes a general-purpose computing device in the form of a computer 2310 (the computing device 110 shown in FIG. 1 is an example of the computer 2310).

[0100] Components of the computer 2310 may include, but are not limited to, a processing unit 2320 (such as a central processing unit, CPU), a system memory 2330, and a system bus 2321 that couples various system components including the system memory to the processing unit 2320. The system bus 2321 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

[0101] The computer 2310 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by the computer 2310 and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data.

[0102] Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by the computer 2310. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media.

[0103] Note that the term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer readable media.

[0104] The system memory 2330 includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) 2331 and random access memory (RAM) 2332. A basic input/output system 2333 (BIOS), containing the basic routines that help to transfer information between elements within the computer 2310, such as during start-up, is typically stored in ROM 2331. RAM 2332 typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit 2320. By way of example, and not limitation, FIG. 23 illustrates operating system 2334, application programs 2335, other program modules 2336, and program data 2337.

[0105] The computer 2310 may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only, FIG. 23 illustrates a hard disk drive 2341 that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive 2351 that reads from or writes to a removable, nonvolatile magnetic disk 2352, and an optical disk drive 2355 that reads from or writes to a removable, nonvolatile optical disk 2356 such as a CD ROM or other optical media.

[0106] Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive 2341 is typically connected to the system bus 2321 through a non-removable memory interface such as interface 2340, and magnetic disk drive 2351 and optical disk drive 2355 are typically connected to the system bus 2321 by a removable memory interface, such as interface 2350.

[0107] The drives and their associated computer storage media discussed above and illustrated in FIG. 23, provide storage of computer readable instructions, data structures, program modules and other data for the computer 2310. In FIG. 23, for example, hard disk drive 2341 is illustrated as storing operating system 2344, application programs 2345, other program modules 2346, and program data 2347. Note that these components can either be the same as or different from operating system 2334, application programs 2335, other program modules 2336, and program data 2337. Operating system 2344, application programs 2345, other program modules 2346, and program data 2347 are given different numbers here to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer 2310 through input devices such as a keyboard 2362 and pointing device 2361, commonly referred to as a mouse, trackball or touch pad.

[0108] Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, radio receiver, or a television or broadcast video receiver, or the like. These and other input devices are often connected to the processing unit 2320 through a user input interface 2360 that is coupled to the system bus 2321, but may be connected by other interface and bus structures, such as, for example, a parallel port, game port or a universal serial bus (USB). A monitor 2391 or other type of display device is also connected to the system bus 2321 via an interface, such as a video interface 2390. In addition to the monitor, computers may also include other peripheral output devices such as speakers 2397 and printer 2396, which may be connected through an output peripheral interface 2395.

[0109] The computer 2310 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 2380. The remote computer 2380 may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer 2310, although only a memory storage device 2381 has been illustrated in FIG. 23. The logical connections depicted in FIG. 23 include a local area network (LAN) 2371 and a wide area network (WAN) 2373, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

[0110] When used in a LAN networking environment, the computer 2310 is connected to the LAN 2371 through a network interface or adapter 2370. When used in a WAN networking environment, the computer 2310 typically includes a modem 2372 or other means for establishing communications over the WAN 2373, such as the Internet. The modem 2372, which may be internal or external, may be connected to the system bus 2321 via the user input interface 2360, or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer 2310, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation, FIG. 23 illustrates remote application programs 2385 as residing on memory device 2381. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

[0111] The foregoing Detailed Description has been presented for the purposes of illustration and description. Many modifications and variations are possible in light of the above teaching. It is not intended to be exhaustive or to limit the subject matter described herein to the precise form disclosed. Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims appended hereto.