Normal Vector of Three Points

问题:

Hey math geeks, I've got a problem that's been stumping me for a while now. It's for a personal project.

I've got three dots: red, green, and blue. They're positioned on a cardboard slip such that the red dot is in the lower left (0,0), the blue dot is in the lower right (1,0), and the green dot is in the upper left. Imagine stepping back and taking a picture of the card from an angle. If you were to find the center of each dot in the picture (let's say the units are pixels), how would you find the normal vector of the card's face in the picture (relative to the camera)?

Now a few things I've picked up about this problem:

1. The dots (in "real life") are always at a right angle. In the picture, they're only at a right angle if the camera has been rotated around the red dot along an "axis" (axis being the line created by the red and blue or red and green dots).
2. There are dots on only one side of the card. Thus, you know you'll never be looking at the back of it.
3. The distance of the card to the camera is irrelevant. If I knew the depth of each point, this would be a whole lot easier (just a simple cross product, no?).
4. The rotation of the card is irrelevant to what I'm looking for. In the tinkering that I've been doing to try to figure this one out, the rotation can be found with the help of the normal vector in the end. Whether or not the rotation is a part of (or product of) finding the normal vector is unknown to me.

Hope there's someone out there that's either done this or is a math genius. I've got two of my friends here helping me on it and we've--so far--been unsuccessful.

回答1:

i worked it out in my old version of MathCAD:

alt text http://i47.tinypic.com/4fjhs.jpg

Edit: Wording wrong in screenshot of MathCAD: "Known: g and b are perpendicular to each other"

In MathCAD i forgot the final step of doing the cross-product, which i'll copy-paste here from my earlier answer:

Now we've solved for the X-Y-Z of the translated g and b points, your original question wanted the normal of the plane.

If cross g x b, we'll get the vector normal to both:

        | u1  u2  u3 |
g x b = | g1  g2  g3 |
        | b1  b2  b3 |  

      = (g2b3 - b2g3)u1 + (b1g3 - b3g1)u2 + (g1b2 - b1g2)u3

All the values are known, plug them in (i won't write out the version with g3 and b3 substituted in, since it's just too long and ugly to be helpful.

But in practical terms, i think you'll have to solve it numerically, adjusting g_z and b_z so as to best fit the conditions:

g · b = 0

and

|g| = |b|

Since the pixels are not algebraically perfect.

Example

Using a picture of the Apollo 13 astronauts rigging one of the command module's square Lithium Hydroxide cannister to work in the LEM, i located the corners:

alt text http://i48.tinypic.com/2heahit.jpg

Using them as my basis for an X-Y plane:

alt text http://i47.tinypic.com/wj9zsx.jpg

i recorded the pixel locations using Photoshop, with positive X to the right, and positive Y down (to keep the right-hand rule of Z going "into" the picture):

g = (79.5, -48.5, g_z)

b = (-110.8, -62.8, b_z)

Punching the two starting formulas into Excel, and using the analysis toolpack to "minimize" the error by adjusting g_z and b_z, it came up with two Z values:

g = (79.5, -48.5, 102.5)

b = (-110.8, -62.8, 56.2)

Which then lets me calcuate other interesting values.

The length of g and b in pixels:

|g| = 138.5

|b| = 139.2

The normal vector:

g x b = (3710, -15827, -10366)

The unit normal (length 1):

u_N = (0.1925, -0.8209, -0.5377)

Scaling normal to same length (in pixels) as g and b (138.9):

Normal = (26.7, -114.0, -74.7)

Now that i have the normal that is the same length as g and b, i plotted them on the same picture:

alt text http://i47.tinypic.com/2qjzp0i.jpg

i think you're going to have a new problem: distortion introduced by the camera lens. The three dots are not perfectly projected onto the 2-dimensional photographic plane. There's a spherical distortion that makes straight lines no longer straight, makes equal lengths no longer equal, and makes the normals slightly off of normal.

Microsoft research has an algorithm to figure out how to correct for the camera's distortion:

A Flexible New Technique for Camera Calibration

But it's beyond me:

We propose a flexible new technique to easily calibrate a camera. It is well suited for use without specialized knowledge of 3D geometry or computer vision. The technique only requires the camera to observe a planar pattern shown at a few (at least two) different orientations. Either the camera or the planar pattern can be freely moved. The motion need not be known. Radial lens distortion is modeled. The proposed procedure consists of a closed-form solution, followed by a nonlinear refinement based on the maximum likelihood criterion. Both computer simulation and real data have been used to test the proposed technique, and very good results have been obtained. Compared with classical techniques which use expensive equipments such as two or three orthogonal planes, the proposed technique is easy to use and flexible. It advances 3D computer vision one step from laboratory environments to real world use.

They have a sample image, where you can see the distortion:

Note

• you don't know if you're seeing the "top" of the cardboard, or the "bottom", so the normal could be mirrored vertically (i.e. z = -z)

Update

Guy found an error in the derived algebraic formulas. Fixing it leads to formulas that i, don't think, have a simple closed form. This isn't too bad, since it can't be solved exactly anyway; but numerically.

Here's a screenshot from Excel where i start with the two knowns rules:

g · b = 0

and

|g| = |b|

Writing the 2nd one as a difference (an "error" amount), you can then add both up and use that value as a number to have excel's solver minimize:

This means you'll have to write your own numeric iterative solver. i'm staring over at my Numerical Methods for Engineers textbook from university; i know it contains algorithms to solve recursive equations with no simple closed form.

回答2:

From the sounds of it, you have three points p₁, p₂, and p₃ defining a plane, and you want to find the normal vector to the plane.

Representing the points as vectors from the origin, an equation for a normal vector would be
n = (p₂ - p₁)x(p₃ - p₁)
(where x is the cross-product of the two vectors)

If you want the vector to point outwards from the front of the card, then ala the right-hand rule, set
p₁ = red (lower-left) dot
p₂ = blue (lower-right) dot
p₃ = green (upper-left) dot

回答3:

@ Ian Boyd...I liked your explanation, only I got stuck on step 2, when you said to solve for b_z. You still had b_z in your answer, and I don't think you should have b_z in your answer...

b_z should be +/- square root of g_x² + g_y² + g_z² - b_x² - b_y²

After I did this myself, I found it very difficult to substitute b_z into the first equation when you solved for g_z, because when substituting b_z, you would now get:

g_z = -(g_xb_x + g_yb_y) / sqrt( g_x² + g_y² + g_z² - b_x² - b_y² )

The part that makes this difficult is that there is g_z in the square root, so you have to separate it and combine the g_z together, and solve for g_z Which I did, only I don't think the way I solved it was correct, because when I wrote my program to calculate g_z for me, I used your g_x, and g_y values to see if my answer matched up with yours, and it did not.

So I was wondering if you could help me out, because I really need to get this to work for one of my projects. Thanks!

回答4:

Just thinking on my feet here.

Your effective inputs are the apparent ratio RB/RG [+], the apparent angle BRG, and the angle that (say) RB makes with your screen coordinate y-axis (did I miss anything). You need out the components of the normalized normal (heh!) vector, which I believe is only two independent values (though you are left with a front-back ambiguity if the card is see through).[++]

So I'm guessing that this is possible...

From here on I work on the assumption that the apparent angle of RB is always 0, and we can rotate the final solution around the z-axis later.

Start with the card positioned parallel to the viewing plane and oriented in the "natural" way (i.e. you upper vs. lower and left vs. right assignments are respected). We can reach all the interesting positions of the card by rotating by \theta around the initial x-axis (for -\pi/2 < \theta < \pi/2), then rotating by \phi around initial y-axis (for -\pi/2 < \phi < \pi/2). Note that we have preserved the apparent direction of the RB vector.

Next step compute the apparent ratio and apparent angle after in terms of \theta and \phi and invert the result.[+++]

The normal will be R_y(\phi)R_x(\theta)(0, 0, 1) for R_i the primitive rotation matrix around axis i.

[+] The absolute lengths don't count, because that just tells you the distance to card.

[++] One more assumption: that the distance from the card to view plane is much large than the size of the card.

[+++] Here the projection you use from three-d space to the viewing plane matters. This is the hard part, but not something we can do for you unless you say what projection you are using. If you are using a real camera, then this is a perspective projection and is covered in essentially any book on 3D graphics.

回答5:

right, the normal vector does not change by distance, but the projection of the cardboard on a picture does change by distance (Simple: If you have a small cardboard, nothing changes. If you have a cardboard 1 mile wide and 1 mile high and you rotate it so that one side is nearer and the other side more far away, the near side is magnified and the far side shortened on the picture. You can see that immediately that an rectangle does not remain a rectangle, but a trapeze)

The mostly accurate way for small angles and the camera centered on the middle is to measure the ratio of the width/height between "normal" image and angle image on the middle lines (because they are not warped).

We define x as left to right, y as down to up, z as from far to near.

Then
x = arcsin(measuredWidth/normWidth) red-blue
y = arcsin(measuredHeight/normHeight) red-green
z = sqrt(1.0-x^2-y^2)

I will calculate tomorrow a more exact solution, but I'm too tired now...

回答6:

You could use u,v,n co-oridnates. Set your viewpoint to the position of the "eye" or "camera", then translate your x,y,z co-ordinates to u,v,n. From there you can determine the normals, as well as perspective and visible surfaces if you want (u',v',n'). Also, bear in mind that 2D = 3D with z=0. Finally, make sure you use homogenious co-ordinates.