# What algorithms can automatically determine a 3D scene from one or a few 2D images?

For a project I'm doing, I'm trying to model a scene based on a phone camera's video input, and then insert arrows into it that indicate direction in three dimensions.

I've looked around, and the paper Rendering synthetic objects into legacy photographs (The presentation in SIGGRAPH Asia 2011) looks quite interesting, and I suppose I could try to adapt its methods.

However, it has the problem that users must input some reasonable spatial constraints into it beforehand, whereas doing this for every frame of a live and constantly changing video is unreasonable.

Another thing that I found allows reconstruction of a 3D object from a few photos of it in various directions, but I can't seem to find the original source anymore.

Any ideas?

• note that phones often have gyroscope/compass/accelerometer which can give you good information about which way the camera is pointing, too. bitbucket.org/apacha/sensor-fusion-demo Nov 14, 2016 at 15:30

SLAM(Simultaneous Localization and Mapping) algorithms can be used to for 3D reconstruction. They offer solutions for both monocular as well as stereo cameras. With single camera they estimate depth with few images and reconstruct the scene. You can find some of the open source solutions here.

Real time 3D reconstruction can done using ORBSLAM and it is also opensource.Here is the related paper for monocular SLAM.

• Oh I've heard of SLAM!! I think that was the reconstruction thing I had forgotten. ORBSLAM looks awesome though.
– oink
Nov 14, 2016 at 20:54

Let us first assume you can produce estimates of the camera state (position and attitude) via sensors, a filter like a Kalman Filter, and a (simple) model for the camera itself. Using this information, you could then match features between a sequence of images and use those matches and camera state estimates to estimate relative 3D coordinates of those features in space.

Using these features and their locations in 3D, you could then use interpolation schemes to build textured 3D models based on the sequences of images.

Obviously one of the tough points with this is noisiness in state estimates for the camera each frame/image in the sequence. But as you match features between multiple images, noise can be smoothed out and allow you to produce more stable results.

• Yeah, there's certainly enough input information to reconstruct the scene with good accuracy (phone sensors are actually amazing), but the matching-features process itself seems to be the hard part.
– oink
Nov 14, 2016 at 20:58
• @cchan3141 Yeah it can be tough to find what feature matching approach is a good balance of robustness and efficiency for a given problem. Not to mention the ability to make good matches is dependent on using a sufficiently detailed descriptor for your problem. Nov 14, 2016 at 22:49

Since you are having a sequence of images from a scene or an object on your phone, I suggest to use a fairly simple method called Structure from Motion1.

Basically, you need to:

1. Determine matrices describing things like camera orientation and scale, so that you can map points from 3d space to image space, for each camera position.

2. Determine equivalent pairs of points in both images that correspond to the same point in 3d space.

3. Compute intersection of 2 rays that pass from the camera centers through the image points, to determine the location in 3d space. Repeat for each pair of corresponding points.

It's a bit involved and hard to get good results, as there are many ambiguities. There's a free PDF book which I found to be quite useful regarding camera calibration and multi-view 3d reconstruction:

http://www.r-5.org/files/books/computers/algo-list/image-processing/vision/Richard_Hartley_Andrew_Zisserman-Multiple_View_Geometry_in_Computer_Vision-EN.pdf