10 Oct

first stab at an algorithm to get 3D objects from two images

Update: This post has a few errors in its methods, but describes what I was thinking at the time. Check this out for a more accurate method.

This post is myself putting into words some ideas on my present project – creating an internal 3D model from images.

First off, take two photos of the location you want to map. The photos should be taken from a few steps apart so there is some difference between near and far objects. It is not necessary for the distance to be exact. What isnecessary, is that the cameras be parallel. For that, try aiming the camera through the room, to some distant focal point.

The next step is to find the points where the two images overlap best. See the previous post for how to do this.

Here comes the fun part – we need to come up with a 3D model which somehow matches both of those photos, including their differences.

The difficulties that I forsee here mostly have to do with lighting differences and certainty. A photograph of an object may look different based on time of day or angle or a myriad of other things, so you can’t just do an exact comparison – some amount of error must be allowable. This brings up uncertainty – If two pixels next to each other look alike, they may confuse the build engine.

Anyhow – we’ll press on and build those bridges when we come to them.

The simpler items to create will be those that overlap exactly with the separate viewpoints.

  1. Load up the images, and run them through the overlapper.
  2. Assume the distance between the POVs is equal to the X offset. We don’t need to use real-world measurements for this. Assume one pixel of the original images is equal to one “unit” in the internal world model.
  3. Crop everything which does not overlap.
  4. Assume the camera’s view angle is about 45° – makes the maths simpler…
  5. Assume the average distance (Z) in the overlapped area is equal to the X offset. We can fix this later with a third photo.
  6. For each visible pixel in the overlapped area in image 1, if there is a correlation (allowing for an error of, say, 1%) in image 2 at that exact location
    1. Create a small square (two triangles) in the 3D model at that X/Y coordinate, with distance Z.
    2. The square should be large enough that it would cover the whole pixel. Mark that pixel as “done”.
  7. Optimise the created triangles, merging where possible.

The next part is more difficult – we need to find correlations with pixals that appear in one image but are not at the same point in the other.

  1. For each number (D) between 1 and half the width of the overlap
    1. For each pixel in image1 which is not marked as “done”
      1. If the pixel in image1 matches with reasonable certainty to the pixel D pixels left or right of the corresponding position in image2, then create a 3D block at the calculated distance (simple trigonometry).

There will be pixels that do not match. They can wait for further photos.

Pretty easy, when I put it like that, right? I’m sure there will be some headaches ahead.