Sylvain Contassot-Vivier

Title: "Parallel computations for the treatment of satellite images"

Abstract:

The study presented in this Phd thesis puts in relation two a priori distinct scientific domains that are geology and computer science. Indeed, the context of this work is to design a complete processing line of parallel tools about satellite images, going from the three dimensional reconstruction to the visualization of the retrieved grounds. This work has then implied a strong cooperation with the department of geology at the École Normale Supérieure of Lyon.

We propose on one side, the parallelization of an algorithm for three dimensional reconstruction of the relief from a couple of satellite images, and on another side, a parallel algorithm to visualize textured grounds. These works are then related to different domains of computer science like parallelism, stereo vision and image synthesis. A methodological and more general study over geometrical image transformation algorithms is also presented.

Concerning the sequential level, we propose for each of the algorithms seen and when it is relevant, different optimizations allowing to reduce the complexity and then the computation times, and some choices for the computational tools to use for increasing the quality of the results, which is a major point in the domain of stereo vision. Concerning the parallelism, we focus on the communications and the load balancing strategies that could be used to take the most advantage of the parallel machines. By comparing our problems to those already studied in the literature, we have arrived at the conclusion that a data driven load balancing was the best suited technique. Moreover, whatever considering the vision or synthesis part, the load balancing problem can be seen exactly in the same way. We can then apply the same strategy over these different algorithms. Finally, a theoretical study of the complexity of our parallel stereo vision algorithm allows us to predict the number of processors necessary to get the best absolute performances for a given input data set.

Experimental results done on several parallel machines, Volvox, Cray T3D or Cray T3E allow us to verify the behavior of our parallel algorithms and to confirm their efficiency.

Keywords: Parallel algorithm, stereo vision, load balancing, image analysis and processing, rectilinear partitioning, image synthesis.

Manuscript (french) in PDF

Initial left image	Initial right image
Reconstructed relief
Textured visualization

An interesting extension of that work is its adaptation to a conical model of camera in order to provide the treatment of aerial images or to reconstruct any scene in robotics, for instance.
That adaptation requires the accurate determination of the epipolar geometry of an uncalibrated stereo-images.
I have personally dealt with that problem using an original approach based on genetic algorithms which gives promising results. Those works are currently idle due to my other research activities.