Jump to content
  • Advertisement
Sign in to follow this  
StasB

Horrific System of Equations

This topic is 3752 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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. :)

Share this post


Link to post
Share on other sites
Advertisement
Hi,

This can get solved quickly provided you do some developments and try to reduce to a manageable number of equations:

I started with your 4th equation and expressed it as:
z1 = x1/Sy1 (A1)
Then I looked at your 7th equation and expressed it as:
Sy1 = y1 * Sx1 / x1 or as x1 = y1 * Sx1 / Sy1 (B1)
Note that it can also be expressed as z1 = y1 / Sy1 (C1)
This can done for the second and third set of coordinates.

Now, plugging back these results into equation number 1, we get:
D1^2 = (A1 - A2)^2 + (C1 - C2)^2 + (B1-B2)^2
You can do this for the 2nd and third equation. You are left with three sets of equations with only three variables (y1, y2, y3).

To end, you just need to develop each of these three equations by remembering that:
(a-b)^2 = a^2 - 2ab + b^2

Then you simplify and you should be all set to solve your problem.

Hope that helps.

Ghostly yours,
Red.

Share this post


Link to post
Share on other sites
Dear god, no! Don't do this with scalar equations! Recovering position from point correspondences is a well-studied problem, with approaches that are downright pleasant. Try this book. Chapters 4, 5, and 6 will be most useful to you.

Share this post


Link to post
Share on other sites
@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.

Share this post


Link to post
Share on other sites
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 functions
fi(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,...,9

Here 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) (*)






Xn and Xn+1 being, of course, columns vectors( dimension(9x1) ). You could choose for X1 any vector( most of the time a good approximation of the solution, but if, and apparently that's the case, we don't have one, we can take anything! ). You will then compute F(X1)( you simply replace all xi with their value in F(x1,x2,...) ), J(X1), the Jacobian evaluated at X1( all xi in the matrix are replaced by their corresponding value ) and its inverse( hence the Jacobian must be inversible ). Take the difference Xn - inv(J(Xn)).F(Xn) to find a new approximation of the solution, Xn+1. Restart the process. You can stop the iterative process if Xn and Xn+1 are close enough, thats is to say, if Xn+1 - Xn < delta_X, with delta_X taken as small as wanted.


Note : you can check the correctness of the equation (*) by analysing the dimenstions of the variables involved

(9x1) = (9x1) - (9x9)x(9x1) (ixj) := i rows and j columns.

English is not my mother tongue, so sorry if I'm not clear enough...

[Edited by - johnstanp on July 11, 2008 6:55:31 AM]

Share this post


Link to post
Share on other sites
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.


Actually the method I described could be used for this reduced system.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.


I've provided the method but if you want, I can implement it. I just didn't do it because I don't have a copy of MatLab or any other scientific software at home, to do the matrix computations easily.
But I can donwload a student version or an open source software and then implement the algorithm. Or even write a C++ program that would solve that specific system of equations. If you really need it, it won't bother me to actually implement it: the equations are simple enough that doing it won't be time consuming.
If you're really interested, tell me.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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?


Well, it will give "a" solution provided there is not a unique one...The solution would depend on the first approximation given(X1(x11,y11,z11,x21,...,z31)). It's the same as finding the root of a function( that's actually what it is ): you can have multiple zeros. That's not necessarily the case( it could depends on the constants you plug in your system of equations ), but since your problem is a geometric one, it can be guessed. I guess that the presence of squares and divides will result in multiple solutions...But this is not a demonstration, just a guess: nothing proves me that I am right to do it.

[edit]If there are multiple solutions, adding constraint equations, would remove the unwanted ones. But then, things get more complicated.[/edit]

[Edited by - johnstanp on July 11, 2008 9:56:17 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!