Life is a game, take it seriously

Paper Talk: Unsupervised Learning of Probabilistic Grammar-Markov Models for Object Categories

In Computer Vision, Paper Talk on April 16, 2011 at 9:35 am

written by Gooly

“The triangle is a foundation to an offense.”
Bill Cartwright, 3 times NBA Champion

What ever that means, triangle is definitely the foundation of this paper. Combining SIFT points into a chain of triangles allows us to use dynamic programming; the DP algorithm works as follows: after finding several triangles, we add each node to one of the triangles that most fit to create a new triangle for each iteration.  See figure below.

Since for each node we store the best fit triangle that it can combine, at the next iteration when we want to add the best n5 (see above graph) , we only have to consider the best fit among all n5, all the n4 from last iteration and the n3 which each n4 pick . For a model with m nodes and an image with n nodes to match this is a drop roughly from O(n^m) to O(m*n^2).

The fitness of the triangle is a probability defined by both the surf appearance and there location plus orientation compared to the model.

The paper also provides an unsupervised way to learn the model by DP. ( which is probably the emphasis of the paper )

Some of the paper’s result are shown below.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: