5 ms·

At some point, I'm hoping to get enough of this to solve this problem: you've taken a picture of, say, the Mona Lisa in its rectangular frame, but because of cr

by thyrsus 11y ago

At some point, I'm hoping to get enough of this to solve this problem: you've taken a picture of, say, the Mona Lisa in its rectangular frame, but because of crowds you weren't in line with dead center, instead you were 5 meters back, 1 meter high, and 2 meters to the side, and not even pointed at the center. Your photo now contains some quadrangle that is a projection of the rectangle. I'd like to tag the four corners and have an algorithm map the photo to its original rectangle - I intuit there's enough information in the photo and the four tagged points, given that the original is actually a rectangle.

tiglionabbit 11y ago
This exact application appears in the Coding the Matrix class on Coursera. http://codingthematrix.com/ http://codingthematrix.com/
mcintyre1994 11y ago
Definitely doable - see the various scanner apps in your app store of choice. They work really well.
gjm11 11y ago
A word of warning about solutions to this problem. The "easy" version states it this way: the mapping you want takes (x,y) to ((ax+by+c)/(gx+hy+i),(dx+ey+f)/(gx+hy+i)) for some a,b,c,d,e,f,g,h,i -- a general "projective transformation". If you decide ahead of time exactly what rectangle you want to map to, you have 8 constraints on a..i (two coordinates for each of four corners) and one irrelevant degree of freedom (if you multiply all of a..i by the same constant, nothing changes) so you have "exactly enough" information to find those parameters. So you solve the equations and you're done. This works, provided your measured positions are perfectly accurate, but it isn't the best you can do. The reason is that a single projection actually has one degree of freedom less than a general projective transformation. (Three parameters to say where your camera is located. Three to say how it's rotated. One scaling factor. Total is 7 rather than 8.) This means that there's an extra (slightly hairy) constraint on the parameters a..i, which turns out to mean that the aspect ratio of the rectangle you're mapping to is determined for you. Imposing that constraint will give you (1) more information -- you won't have to know ahead of time what aspect ratio you have -- and (2) a more accurately estimated transformation. You can find more details of this stuff in, e.g., this PDF document: http://people.csail.mit.edu/bkph/articles/Harmful.pdf http://people.csail.mit.edu/bkph/articles/Harmful.pdf .
jamessb 11y ago
HN previously had some discussion on an article that used IamgeMagick to do this correction on a video: https://news.ycombinator.com/item?id=8713070 https://news.ycombinator.com/item?id=8713070

by thyrsus 11y ago

tiglionabbit 11y ago

This exact application appears in the Coding the Matrix class on Coursera. http://codingthematrix.com/ http://codingthematrix.com/

mcintyre1994 11y ago

Definitely doable - see the various scanner apps in your app store of choice. They work really well.

gjm11 11y ago

A word of warning about solutions to this problem. The "easy" version states it this way: the mapping you want takes (x,y) to ((ax+by+c)/(gx+hy+i),(dx+ey+f)/(gx+hy+i)) for some a,b,c,d,e,f,g,h,i -- a general "projective transformation". If you decide ahead of time exactly what rectangle you want to map to, you have 8 constraints on a..i (two coordinates for each of four corners) and one irrelevant degree of freedom (if you multiply all of a..i by the same constant, nothing changes) so you have "exactly enough" information to find those parameters. So you solve the equations and you're done. This works, provided your measured positions are perfectly accurate, but it isn't the best you can do. The reason is that a single projection actually has one degree of freedom less than a general projective transformation. (Three parameters to say where your camera is located. Three to say how it's rotated. One scaling factor. Total is 7 rather than 8.) This means that there's an extra (slightly hairy) constraint on the parameters a..i, which turns out to mean that the aspect ratio of the rectangle you're mapping to is determined for you. Imposing that constraint will give you (1) more information -- you won't have to know ahead of time what aspect ratio you have -- and (2) a more accurately estimated transformation. You can find more details of this stuff in, e.g., this PDF document: http://people.csail.mit.edu/bkph/articles/Harmful.pdf http://people.csail.mit.edu/bkph/articles/Harmful.pdf .

jamessb 11y ago

HN previously had some discussion on an article that used IamgeMagick to do this correction on a video: https://news.ycombinator.com/item?id=8713070 https://news.ycombinator.com/item?id=8713070