Visualization of affinity search

Created by predoehl
Last updated: Oct 15, 2012Version comment
2 min read

Here's a picture of me stressing out a simple statistical inference engine.  I'm asking it to find an affinity to match up a triangle and square.  Of course, you and I know that a triangle and a square cannot ever be related by an affinity:  straight lines in become straight lines out (by definition), so triangles in become triangles out -- never a square.  Thus, the poor program is squirming this way and that to make the best of an impossible situation.  It's proposing all kinds of affinities, each of which projects the blue triangle (the original) into a new location (the green triangle).  The green triangle dances around as the program accepts new proposals.  Eventually it almost stops moving as the acceptance ratio drops.

To restate this:  I didn't animate the green triangle, but I wrote five components that did:

  • I made up a simple likelihood function that measures "quality of fit" by counting uncovered pixels, i.e., the red and green pixels above.  (Black and blue pixels do not count, nor do yellow pixels, which represent alignment.)
  • I chose affine transforms as the relationship between the given data (which are represented above by the red square and blue triangle).  Furthermore, I constructed a prior function that represents a-priori assumptions about the transform: it can magnify or shrink but not too much, it can rotate any amount, it can skew but only a little, etc.  In other words, some affinities are more probable than others.
  • I designed a proposer function that takes an affinity in, and tweaks it randomly.  It makes a small random change to all seven parameters.  It also can randomly flip the shape in the horizontal or vertical direction.
  • I implemented a sampling method called the Metropolis algorithm, which is one of the simplest MCMC sampling algorithms.  It can be thought of as an optimization procedure.
  • I typed in the coordinates of the square and triangle, gave them to the program, and said go.

For a little dramatic interest, I initialized the affinity so that the blue triangle maps onto itself (visible only in the first frame), but it's not really a sensible choice for compact shapes.  In practice, one would initialize so that the centroids are aligned.