Math Is Fun Forum

Stas B.

Guest

Horrific System of Equations

Hi! I'm working on an interesting computer graphics project, but I'm stuck with some math and I need your help desperately. I'm trying to figure out the approximate position and orientation of a camera from a picture. I figured that if I had some cues in the picture, for example, if I had three points in the picture and knew the real distances between each pair (i.e. the 3D distances, not the distances between their projections on the picture), I could use that to get three equations and use the perspective projection formula to get six more, resulting in a system of 9 equations with 9 unknowns, with the unknows being the real coordinates of the points in 3D space. I can later use those coordinates to compute everything I need. (I don't think it would work with any less than three points, so it's 9 equations in the best case.) If non of the above makes any sense to you, it's ok. I'm just going to write the system down:

D1^2 = (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2
D2^2 = (x2 - x3)^2 + (y2 - y3)^2 + (z2 - z3)^2
D3^2 = (x3 - x1)^2 + (y3 - y1)^2 + (z3 - z1)^2
Sx1 = x1 / z1
Sx2 = x2 / z2
Sx3 = x3 / z3
Sy1 = y1 / z1
Sy2 = y2 / z2
Sy3 = y3 / z3

So the unknowns are {x1, x2, y3, y1, y2, y3, z1, z2, z3}.
D_ are the distances between the points in 3D space, S__ are the 2D coordinates of the three points after perspective projection. Those are given.
It doesn't look too complicated and technically should be solvable, but it gets really hard.
I can't solve it, neither can Maple 11.
I think the main thing that bugs me is those powers of 2. I even had this crazy idea to replace the top three lines with some linear approximations of the distances, which should make the whole thing much easier. (Too bad I just don't know of any...)
Please, help me. I need a solution to this desperately. An exact solution, a numerical solution, an approximate solution... any would do. (Maybe there's even some numeric algorithm I could implement and use to solve this?)

Thank you very much for your time. Any help would be very appreciated. Oh, and pardon my bad English.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Horrific System of Equations

So far I've got that system down into this simpler one:

D1² = az1² + bz2² - dz1z2
D2² = bz2² + cz3² - ez2z3
D3² = az1² + cz3² - fz1z3

{z1,z2,z3} are the unknowns and D1,D2,D3,a,b,c,d,e,f are given.

I've replaced them with single letters for tidiness, but a to f are also known as:

a = Sx1² + Sy1² +1
b = Sx2² + Sy2² +1
c = Sx3² + Sy3² +1
d = 2(Sx1Sx2 + Sy1Sy2 +1)
e = 2(Sx2Sx3 + Sy2Sy3 +1)
f = 2(Sx1Sx3 + Sy1Sy3 +1)

Does Maple like that system any better?

---

Why did the vector cross the road?
It wanted to be normal.

Stas B.

Guest

Re: Horrific System of Equations

Nope, Maple still doesn't like it and I can easily see why.
Try working out 'z3' from the third equation and plugging it into the 2nd.
You'll get something nasty. The next step would be to work out 'z2' from the 2nd equation, but it's just too nasty, even for Maple.
This thing is gets exponentially uglier with every step.
I think an exact solution is not an option.
Is it possible to replace the distances with some linear approximations?
I think it's those powers of 2 that make the thing so complicated.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Horrific System of Equations

May we assume that your camera is looking straight at the picture?  If this is the case, then the camera must lie along the normal of the picture.  If we are assuming that the camera is centered, then we also know that the camera lies on the centered normal.

Thus, the only thing left to figure out is the distance from the picture, which is a single number and all you need is geometry.

resulting in a system of 9 equations with 9 unknowns, with the unknows being the real coordinates of the points in 3D space.

When ever you hear yourself make such a statement, in the back of your mind should be the words, "there has got to be a better way."  On the other hand, an engineer would think, "I'm gonna get this sucker."

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Stas B.

Guest

Re: Horrific System of Equations

I think I wasn't very clear.
I have a triangle in 3D space and I have a camera that views that triangle. I know the distance between each pair of points of the triangle. The triangle is rotated and translated according to the location and orientation of the camera and gets some new 3D coordinates, but the distances remain the same.
What the camera "sees" is that transformed triangle after perspective projection.
What I want to do is to analyze what the camera sees to figure out the coordinates of the three points of the transformed triangle relatively to the camera.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Horrific System of Equations

Ok, if you want the points of the triangle, then all you must do is find the matrix that your graphics library is using, and apply that same matrix to the point.  Typically, graphic libraries have an explicit way of doing this (OpenGL does).  You shouldn't muck about with systems of equations because graphics are done by matrices, not equations.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Stas B.

Guest

Re: Horrific System of Equations

Were talking about a real camera and a real triangle here. So I'd either have to ask God for the transformation matrix, or make use of the information I have from my measurments and the input from my camera.

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Horrific System of Equations

Hopefully you have the original pictures without cropping because
the outer frame of the photo will always be at the same viewing
angle from the eye of the camera as long as their is not a zoom
lense attached.  A cropped image will produce problems in
determining distance from the camera, but you might be able
to determine some estimate of the angles from the object.
I am no expert at this; I am just trying to help a little.

---

igloo myrtilles fourmis

Stas B.

Guest

Re: Horrific System of Equations

Never mind, guys. Solving that system would be pointless.
It's funny, actually. I made an incorrect assumption that two or more identical triangles can't be positioned differently but look as the same one for a camera. This system clearly has more than one solution, proving me wrong.
I give up on this one.
Thanks for all your help.