# How can I reconstruct a 3D structure from a set of images?

I have a set of contours (set of line segments) grouped in the following way:

$S_i = \{I^0, I^\frac{\pi}{4}, I^\frac{2\pi}{4}, \ldots, I^\frac{7\pi}{4} \}$

where

• $S_i$ denote sequence of photos of one concrete object.
• $I^j$ denote an image, with $j^{th}$ point of view ($j=0$ means front view).

Here is example of $I^\pi$ (rear view):

How can I reconstruct 3d structure of object with given $S_i$?

Can someone point me to some papers or even give me some keywords? I know that there are a lot of articles that operate with clouds of points and so on, but those don't work as I'm operating with lines.

Actually it is quite a hard topic. Classical multi-view 3d reconstruction deals with point matching in the first place, i.e. find the same point on every image. Given the camera (view) parameters for each image, the original 3d point can be reconstructed. (Using a laser or a projector the scene can be lit so the matching can be done relatively easily.)

The bible of the field is Multiple View Geometry in Computer Vision by Hartley and Zisserman

In the book there is a section about the trifocal tensor, which is a multilinear constraint between 3 views. It contains not just point but line correspondence constraints as well. It can be used for building reconstruction very well.

So your contours should be matched at the first place, and maybe can be reconstructed knowing the camera parameters (camera calibration is also covered in the book). Then you will have contours in 3d but nothing more. For real surfaces you have to do dense point matching. Though the tensor I mentioned look good it is used for straight lines and I am sure that a modern car has curved lines all over.

I do not know how you got those contours but seeing the image you have posted I am quite sceptic about the robustness of that algorithm, so the reconstruction will be poor.

Another method it came to my mind is visual hull or space carving. The contour mathcing should also be done. Running the method on each contour you can have the model.

• I'm getting those contours by applying Canny, and then by some line simplification algorithms, which takes binary raster and then return set of edges. Actually, it is possible to involve plain images, without filters, but the reason I've formulated task in this manner is that I would need to constantly compute contours under different angles (that could have quite low delta: < $\pi/4$) of view. I thought, that if I could restore edges in 3d, all i need to do is just perform projection. Maybe, that was a mistake (if so, please, let me know). – om-nom-nom Aug 26 '11 at 12:45
• I don't see how you get an off-contour 3d point by projection. There are 3d modeling techniqes dealing with NURBS surfaces stretched between splines, but you have to provide characteristic splines for that. (Maybe a 3d artist could define the word characteristic in this context, but not me.) Again, I think the shape-from-contour (same as visual hull) can build a rough model for you. After that you can refine it based in the images. But there are no standard ways for that. – Bálint Fodor Aug 31 '11 at 10:10

While mentioned by Fodor Hartley and Zisserman book is definitely worth to read it's more for general understanding than for practical algorithms. It's quite outdated and those methods are not efficient. About your problem - the problem formulation itself is very uncommon. As it was mentioned by Fodor starting with matching feature points instead of contours is a lot more easy. In case of points the absolutely best overview of available modern methods is the paper by Triggs "Bundle Adjustment — A Modern Synthesis" But before using bundle adjustment you would have match corresponding point on the images using something like SIFT or template matching. Google for 3D reconstruction for examples of some complete methods. You can also use open source packages for it, there are several available.

If you insist on using contours the problem is a lot more difficult, though still (barely) tractable . First you will have identify and match corresponding contours in all the images, after that write the cost function - of sum of reprojection errors for each matched contours group as function from camera position&orientation of each image. After that find the set of camera position which minimize this cost function. Each step of this process is extremely difficult, and there is no good overview like Triggs. You can google some relevant papers as some combination of terms "contours" "conturs matching" "bundle adjustment" "reprojection error" "3D reconstruction" .

• While it's definetely easier to dealt with SIFT-like features there is problem that SIFT in my domain often catchs shadows/reflections on glossy cars surface, so using SIFT I'm getting enormously huge amount of noise features that doesn't rely to an actual car shape hence I have a decreasing of accuracy. – om-nom-nom Sep 8 '11 at 15:08
• You can try model-based approach if you know you are looking on the car. Parametrize generic car model and try to fit it to picture using all the image pixels. Write cost function as function of camera parameters and car model parameter and minimize it. It may work(or may not) - you seems have quite difficult problem. – mirror2image Sep 11 '11 at 13:25
• Unfortunately, I didn't understand what you have proposed to do. Please, provide some example (it could be external article, related work or something like this). – om-nom-nom Sep 11 '11 at 15:24
• I mean active shape model en.wikipedia.org/wiki/Active_shape_model or somethings imilar – mirror2image Sep 13 '11 at 6:05

Check out Model Reconstruction from Images which is a little different from what you're doing but I talk about how to go from images to a 3d model. Also check out MeshLab, it has some reconstruction algorithms that you might be able to feed your data into.