Normal Vector of Three Points

mattbasta picture mattbasta · Jan 10, 2010 · Viewed 11.2k times · Source

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.

Answer

Ian Boyd picture Ian Boyd · Jan 14, 2010

i worked it out in my old version of MathCAD:

alt text

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 gz and bz 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

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

alt text

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, gz)

b = (-110.8, -62.8, bz)

Punching the two starting formulas into Excel, and using the analysis toolpack to "minimize" the error by adjusting gz and bz, 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):

uN = (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

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:

alt text
(source: microsoft.com)

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:

alt text

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.