symmetric affine transformations

A common task in computer vision problems is fitting an affine transformation to a set of point correspondences. The transformation is uniquely determined by 3 correspondences for 2D points or 4 correspondences for 3D points, and can be obtained by solving a linear system of equations.

Often, however, we have more correspondences. The usual solution is then to minimize the sum of squared distances between each point in one set and its transformed corresponding point in the other set. The problem with this approach is that you get different answers if the point sets trade roles. So, if we have point sets P and Q, the affine transformation A_PQ that transforms P to Q will in general not be the inverse of the affine transformation A_QP that transforms Q to P.

(Note that sometimes, this makes sense. If one of your point sets is a ground-truth "model" and the other is an "observation", it is reasonable to minimize the squared distances between observation points and transformed model points.)

Is there an alternative? There is, and it's based on a technique called total least squares. I'll write more about this later, but for now, here's some Matlab code that solves the problem for sets of 2D points:

function [a_pq,a_qp] = symmetric_affine(p,q)
% p and q are both 2-by-n matrices
% a_pq and a_qp will be 2-by-3 matrices

n = size(p,2);
x = [p; q];
c = mean(x,2);
x = x - c*ones(1,n);
[v d] = eigs(x*x',2,0);
a = [v; -c'*v]';

a_pq = [-a(:,[3 4])\a(:,[1 2 5])];
a_qp = [-a(:,[1 2])\a(:,[3 4 5])];

movie poster quiz

What do I hate about the following two movie posters?



It might be difficult to fix in the first one, but it would be really easy to fix in the second one.

subscription math

Ramit Sethi suggests cancelling all your subscriptions and paying for items à la carte to save money. Without considering whether or not this is a good idea in reality, my first thought was, "can we turn this into a cool math problem?".

Using movies as an example, let's assume that you will rent x_i dollars of movies during month i. Before the month, you can choose to either pay x_i (whatever it turns out to be), or pay a c dollar subscription fee to Netflix. Though this is obviously not true in reality, just for simplicity let's assume that whether or not you've subscribed doesn't affect how many movies you will watch that month. So I won't watch more movies just because I subscribed to Netflix.

Now, there is some optimal strategy that, before each month, psychically knows how many movies you're going to watch, and if their total cost is above c, subscribes for the month, otherwise pays à la carte. Of course, you can't use this strategy, because you aren't psychic.

Two questions, nonexistent readers. First, is there any other strategy that we can make any claims about? For instance, is there a strategy that will never pay more than twice what the optimal strategy pays in the long run? I'm pretty certain there is not, since an evil god could make you watch nothing every time you subscribe and $1,000,000 worth of movies every time you don't.

Second, can we add any additional elements to make the problem more interesting, where some strategy is competitive with the optimal one? What if you have to pay a fee every time you switch from subscription to nonsubscription or vice versa? What if the x_i come from a normal distribution?

excellent analogy by Marc Davis

Marc Davis of Yahoo Research gave an excellent talk at UW today on mobile phones and social media. During the talk, he gave the following analogy (paraphrased):

You are at a bar.
You get drunk.
You get even more drunk.
Someone hits you in the back of the head and you go unconscious.
While you're out cold, they take you to the airport and fly you to another country.
They drive you to an unknown location and leave you lying in the street.
You wake up and open your eyes.

That's what it's like to be a computer vision system.

The lesson, of course, is that context from our lifestream is incredibly useful for solving problems that are not easily tackled by vision alone.

using Intrade for news

I find it is enlightening to fact-check the reported news against reality, and I find that Intrade is a good surrogate for reality.

So here's my Intrade observation of the moment: although Clinton has not yet dropped out of the Democratic race, right now Obama has the same probability of being the Democratic nominee as McCain has of being the Republican one (95%).