I'm not sure you couldn't solve this as an optical character recognition problem, with something like Isomap, which is invariant under orientation and scale cha

I'm not sure you couldn't solve this as an optical character recognition problem, with something like Isomap, which is invariant under orientation and scale changes. Break your image up into patches, reduce dimensionality on all of them, and find the location that way. I would predict that this is faster, at some cost in accuracy.