max planck institut

informatik

informatik

In the last 20 years, many researchers have considered the problem of reconstructing a shape from a set of sample points. The relevance of this problem arises from its large number of possible applications. One possible application area can be found for example in industrial manufacturing. Very often, the design of a new product is first developed using a real-world model. For the production, though, a CAD model representation is required. One possibility to obtain the CAD representation from the real model is to take a set of sample points from the surface of the model and create a three-dimensional representation in the computer.

Another large application area can be found in medicine. Computertomographers scan the human body in layers, gathering valuable information about the tissue structure. But very often, it is desirable to have -- apart from the layered view -- a three-dimensional model. There are means to automatically detect boundaries between different tissue types in the layered scans. Using curve reconstruction techniques, this information can be processed to obtain collections of curves which represent the different tissue types in each layer. In a last step, curves in different layers are glued together to obtain the final three-dimensional model. For the most prominent problem of reconstructing a surface in the three-dimensional space, many solutions have been proposed, which all produce good approximations to the original surface. Until several years ago, though, none of these approaches provided a guarantee for the correctness of the produced solution. Only recently, researchers in the area of computational geometry have looked at the problem from a theoretical point of view and aimed for algorithms, which provably compute a correct solution.

Figure 1a | Figure 1b |

Figure 2a: The original curve | Figure 2b: Sample points | Figure 2c: correct reconstruction |

Probably, every child is able to connect the sample points from 2 b) correctly without knowing the original curve in 2 a), as it can guess the shape of the original curve from the set of sample points. A computer has a lot more problems with that, it lacks the necessary intuition for guessing.

Our goal is to provide a precise sequence of instructions (an algorithm) for the computer, which solves this problem (almost) as good as a human being does. In particular, we want to solve the problem provably, i.e. we want to define a condition, such that any sample set satisfying this condition is correctly reconstructed by our algorithm. Such a condition is called sampling condition.

What could be an algorithm for this problem? Well, we could for example determine for each sample point its nearest neighbor and connect all those pairs of points. Unfortunately, it turns out that the result of this procedure is not always what we are aiming for. Some pairs of points choose each other as nearest neighbors and holes appear in the reconstruction.

But with a small modification of our algorithm, we obtain the desired result: in a first phase we determine for each sample point its nearest neighbor and draw an edge (the black segments in Figure 3). If there are still sample points which have only one adjacent edge, we determine their nearest neighbor which is ''opposite'' of its first nearest neighbor (in the figure, the area is dashed, where we look for the second-nearest neighbor). The edges created in this step we have drawn in red (see Figure 3, right). What do we need to prove correctness of this simple algorithm? Well, we have to define precisely, under which conditions this algorithm computes the correct result. How should such a condition look like?

We aim for a condition which is as weak as possible, i.e. rather sparse sample sets should be allowed. Furthermore, it is desirable to have a condition, which accommodates to the local structure of the curve, i.e. in detailed areas of the curve (e.g. with high curvature) typically one needs many sample points, whereas in less detailed areas less sample points should suffice. There is a very elegant way to formally capture this condition; it is based on the so-called medial axis. The medial-axis of a curve in the plane is defined as the set of points which have two or more nearest neighbors on the curve, i.e. when growing a ball in a point of the medial axis until touching the curve, it will touch in at least two points at the same time. Figure 4 shows a curve (green) together with its medial axis (red). One property of the medial axis is that it captures somehow the local level of detail of the curve; observe that the medial axis is close to the curve in areas of high detail, whereas in areas of lower detail, the medial axis is far away from the curve.

Therefore the distance of a point p on the curve to its medial axis can be used as a measure for the level of detail of the curve at that point. A very natural condition for the sample set is to postulate that for every point p on the curve, there should be at least one sample point at distance proportional to the distance to the medial axis.

One can mathematically prove that the simple ''connect-to-your-neighbours''-algorithm presented above correctly reconstructs every sample set fulfilling this sampling condition, if the sample set comes from a collection of closed curves without corners.

Why only closed curves and why no corners? For the former, we only remark that in the case of curves with endpoints, it is not always possible to guarantee that we compute exactly the correct reconstruction; aside from the edges of the correct reconstruction, there can be additional edges in the output of the algorithm, if this is not excluded by a stronger sampling condition. But why can't we include curves with corners in our claim?

When looking at our sampling condition, one realizes, that in case of curves with corners (mathematically speaking, corners are points of the curve, where left and right tangent disagree), the medial axis actually touches the curve in the corner point, i.e. a sampling condition based on the medial axis would enforce an infinitely dense sampling near the corners (see Figure 5, left).

But the problem is not only the non-applicability of the sampling criteria based on the medial axis. In the smooth parts of the curve we indeed have that the nearest neighbors of a sample point to both sides are actually the neighbors on the curve.

In the proximity of a corner, this is no longer true -- unless we have a very, very dense sample set, as can be seen in Figure 5, right. The red edges denote pairs of points which are nearest neighbors for each other but are not adjacent along the curve.

It seems that for the regions near the corners, one has to define a different sampling condition and modify the algorithm such that it accommodates to the different setting there.

In two papers which we published recently, we have defined new sampling conditions and designed new algorithms which provably reconstruct a collection of curves, which might also include corners. The first paper is based on the so-called travelling salesman problem, i.e. the problem of finding the shortest path visiting a set of given cities. In this paper we show that for the case of a closed curve (possibly with corners), the shortest travelling salesman tour is indeed the correct reconstruction.

In general it is very difficult to solve the travelling salesman problem exactly, but we could show that in this special instance of the problem, an efficient solution is possible. The more recent paper also allows curves with endpoints.

It is beyond the scope of this article to go into the details of this algorithm, but the main idea is to relax the sampling condition around corner points; the algorithm then first reconstructs the smooth part and from there explores the corner areas.

In our current research, we consider the problem of reconstructing a surface in three dimensions, which is by far more relevant in practical applications. It turns out, that when looking at the problem from a mathematical point of view, it is not even entirely clear what is meant by the ''correct reconstruction'' of a set of sample points from a surface, as there is no notion of adjacency as in the case of curves. Nevertheless it is possible to define a canonical correct reconstruction.

For provably correct algorithms one then shows that the output of these algorithms converges towards this canonical reconstruction, if the sampling density increases. The first algorithms which guaranteed correct reconstruction in case of curves were soon adapted to the three-dimensional case of surface reconstruction. But while the running time for curve reconstruction was almost linear at around n · log n instructions to execute, where n is the number of sample points, the first algorithms which provably reconstructed a surface required about n² instructions. Remember that this means that if reconstructing 10000 points takes 2 hours, reconstructing 20000 takes 8 hours. Recently we published a paper which showed that one can provably reconstruct a surface in near-linear time using about n · log n instructions.

As many readers might have observed, the problem of reconstructing a shape is not only considered by computational geometers but also, or even mostly by researchers in the area of computer graphics and computer vision (for example the colleagues in our working group ''computer graphics'' under Prof. Seidel at our institute). Where are the differences in the approaches to solve the problem?

While computational geometers are interested in designing algorithms which allow a rather sparse sample set and have a good worst-case running time, researchers from computer graphics always assume that the sampling density is sufficient.

So the real challenge for them is to actually process this huge amount of data -- large sample sets consist of several millions of sample points. Furthermore, for real-world applications, the average running time observed in practice is much more important than the pessimistic worst-case view from us computational geometers. Nevertheless there are areas of interaction of both approaches. For surfaces with sharp ridges or corners, there are always areas in the proximity of these ridges and corners, where the sampling density is not sufficient to obtain a good solution with a simple algorithm. We hope to be able to generalize our results for the 2-dimensional case of curves with corners to the 3-dimensional case of surfaces in cooperation with the researchers of the computer graphics group. (ub)

Created by: | Uwe Brahm/MPII/DE, 12/03/2002 12:34 PM | Last modified by: | Uwe Brahm/MPII/DE, 02/10/2006 04:10 PM |

- Uwe Brahm, 03/28/2003 03:33 PM
- Uwe Brahm, 03/27/2003 07:13 PM
- Uwe Brahm, 12/05/2002 12:50 PM
- Uwe Brahm, 12/03/2002 02:58 PM
- Uwe Brahm, 12/03/2002 12:40 PM -- Created document.