Quote:Original post by StasB
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. :)

You could use the Newton-Raphson method. You must define 9 functionsfi(x1,x2,x3,y1,y2,y3,z1,z2,z3). To derive f1(xi,yi,zi), put all the terms of the first equation in the right member:    D1^2 = (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2<=>(x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 - D1^2 = 0=>  f1(x1,x2,x3,y1,y2,y3,z1,z2,z3) := (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 - D1^2.The first equation can then be rewritten f1(x1,x2,x3,y1,y2,y3,z1,z2,z3) = 0.You should do that for all the remaining equations.You define after a vectorial function( in french "fonction vectorielle", I don't know the correct term in english ) whose components are those fi(x1,x2,...).You'll have:F(x1,x2,...)=[f1(x1,x2,...)              f2(x1,x2,...)              f3(x1,x2,...)              ...              f9(x1,x2,...)]F(x1,x2,...) is a column vector( dimensions (9x1), in this case ). Your system of equations can now be rewritten:F(x1,x2,...) = [0                0                .                .                .                0]Well, to solve your system of equations, you'll need the Jacobian of F(x1,x2,...). By definition, it is the square matrix (J)ij, i = 1,2,...,9 and j = 1,...,9 with(J)ij = partial derivative of fi(x1,x2,...,y3) with respect to xi, i = 1,2,...,9Here is how those xi are defined:        x1:=x1;        x2:=x2;        x3:=x3;        x4:=y1;        x5:=y2;        x6:=y3;        x7:=z1;        x8:=z2;        x9:=z3;Read the symbols ":=" "is defined as". Well, the derivation of that Jacobian by hand could have been time consuming since that square matrix has 81 component( 9 x 9 ), but hopefully, many terms are equal to zero( sparse Matrix ).To make the equations shorter, we'll make another definition:                  X:=(x1,x2,x3,y1,y2,y3,z1,z2,z3)The system can be rewritten as followed:        F(X) = 0 ( 0 being the null vector )Having done that, now, we will apply the following algorithm:Xn+1 = Xn - inv(J(Xn)).F(Xn) (*)

Quote:Original post by StasB
@Red Ghost:
I've tried something similar, but it still gets really nasty.
Here are the three equations I came up with:

D1^2 - (x1 - x2)^2 - (Sy1 * x1 / Sx1 - Sy2 * x2 / Sx2)^2 + (x1 / Sx1 - x2 / Sx2)^2 = 0
D2^2 - (x2 - x3)^2 - (Sy2 * x2 / Sx2 - Sy3 * x3 / Sx3)^2 + (x2 / Sx2 - x3 / Sx3)^2 = 0
D3^2 - (x3 - x1)^2 - (Sy3 * x3 / Sx3 - Sy1 * x1 / Sx1)^2 + (x3 / Sx3 - x1 / Sx1)^2 = 0

Now, if I try to work out x3 from the 3rd equation, I get two horrid possible solutions, which I then need to plug into the 2nd equation, making it un-managable. Perhaps I'm just doing something stupid...?
I've tried grouping the knowns and denoting them with simple symbols, but there's too many of them. :(

@Sneftel:
That looks quite interesting. I'll check it out.

Thank you, guys.

Quote:Original post by StasB
I'm giving up on this one.
Even if I was able to solve this system, it has too many possible solutions to be of any use.
Anyway, thanks for all your help.

Quote:Original post by StasB
Thank you very much! I'm just not sure if I should bother you with this, because I'm no longer sure if my equations would do the job. What I'm trying to do is to detect the 3D coordinates of three points given their perspective projections and the distances between them. I'm pretty sure the equations I formulated are correct, but they don't really solve my problem. Each point has a single exact location, but the equations yield many possible solutions and I don't know how I would chose the real one even if I could find all the solutions. If I understand this right, the method you suggest would return only one of the many possible solutions depending on the initial guess?