A surprising approach to solve the surface estimation problem is to transform it into a well known problem in graph theory. In [22] V. Kolmogorov shows that a certain group of energy functions can be minimized by solving a maximumgraph cutproblem. This problem can be shown to be the same as solving theminimum flow problem of a graph, which is a well research method in graph theory. To use this approach in surface estimation, the problem must be formulated as a special energy function. The basic idea is to assign vertices to a cartesian grid in a volume of interest in the space. Locally a cost is assigned to every composition of triangles defining the connectivity of the local vertices. This cost is calculated using the input images together with a smoothness term. The edge in the graph going from one vertex to another is set to be some cost of letting that cut be a part of the surface. This defines a large graph over the grid of vertices, in which the minimum cut is sought. Vogiatzis showed the use of this in practice in [29].
One interesting property of using a graph algorithm solving such a problem is that it is deterministic. Thus the result of the algorithm is the global minima of the energy function. The downside is that setting up and solving the graph problem can be relatively slow.
C h a p t e r 6
Discussion
The last chapters have shown a part of the huge field of surface estimation.
Most of this research has been done in the last decade or so, and the field shows no sign of stopping now. We are getting closer to methods that can be used for practically purposes in real life.
One of the more promising method is using deformable models. The deforma-tions of the model can be performed and controlled in many ways, which makes the method very generic. The fact that graphics hardware offer an superior and ever increasing performance, when projecting and evaluating images and meshes, only makes the choice even more attracting. Therefore this method has been chosen as the main focus of the rest of this thesis. In particular one very interesting method by George Vogiatzis is considered [57].
Part II
Basic Algorithm
C h a p t e r 7
The Algorithm
As denoted in the last part, the rest of this thesis will concentrate on a specific approach to do surface estimation, i.e. using deformable models on rigid bodies under constant lighting conditions. This part will describe, document and test the algorithm presented by Vogiatzis in [57], denoted as the basic algorithm.
The algorithm will be reflected upon and used as the base for a discussion on surface estimation using deformable models. This is used to propose deviations to the basic algorithm of which some will evaluated using the basic algorithm as a foundation.
This chapter will introduce the algorithm in its most simple form, and then gradually add deeper insight, up until the next chapter that will describe it all in a Bayes framework using simulated annealing. Next the design of a mesh representing the surface will be described in Chapter 9, followed by a docu-mentation of the impledocu-mentation of the algorithm in Chapter 10. At this point Chapter 11 introduces the datasets used in this thesis, which is used to test and evaluate the basic algorithm and some deviation to it in Chapter 12. Finally the results are discussed and a conclusion on the basic algorithm is made in Chapter 13.
34 The Algorithm
7.1 Foundation
The basic idea that makes the foundation for the algorithm is the general ob-servation that:
Having the correct surface of some object, and a set of input images and the corresponding cameras thereof.
Then projecting an arbitrary input image onto the surface and back into an arbitrary (possibly the associated) camera, will match the image of that camera in the domain of the image being visible from the viewpoints of both cameras.
If on the other hand, the projection does not result in a perfect match, then the surface is not correct. Thus a measure of the
’correctness’ of a surface, with respect to a set of input images, can be defined as the how well, the surface reprojects the images into each other.
This is an idealistic presentation of the fundamental idea, since it assumes a number of idealistic assumptions of the world. These assumptions and a short explanation is listed in the following.
1. The object is Lambertian. Thus every point on the surface radiates light of the same color and intensity in all directions, and is thus perceived as having the same color in the input images in which it is visible.
2. The input images must be of infinite resolution. If the images were a quantification of the captured light rays, then the match may fail due to the pixels not being projected perfectly into each other.
3. The images are noiseless and thus resembles the scene correctly as seen from their viewpoint.
4. The projection1 of images onto the surface and the reprojection into a camera are assumed to be perfect.
5. Lighting conditions are constant.
6. The space outside the object are completely transparent and space inside the object is completely opaque.
7. The images are taken at the same time, or the scene is static.
1It should be noted that the termproject is used in a mathematical sense, and not as light would normally be projected as from a projector. In other words the perceived color and intensity of a surface point is invariant to the normal to the surface at that point.