טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentDubrovina Karni Anastasia
SubjectGeometric Algorithms for Image and Surface Analysis
DepartmentDepartment of Computer Science
Supervisor Professor Ron Kimmel
Full Thesis textFull thesis text - English Version


Abstract

Many problems in image and shape analysis and processing share the following common denominator: the complexity and the accuracy of the solution depend on the specific problem formulation and data representation being used. In this thesis, we studied several such problems, namely, automatic and user-assisted image segmentation, and three-dimensional shape matching. First, we used the geometric formulation of the above, which allowed us to apply tools from differential and metric geometry, as well as the variational approach. We also studied how data representation domain, sometimes different from the standard one, may be utilized to find more intuitive formulation, and faster and more accurate solutions for these well known problems.


We first considered the problem of image segmentation using the active contours approach and the level set framework. We suggested a new method for extending this classical framework for multi-region segmentation, using only a single non-negative level set function, and an evolution algorithm recently suggested for physical simulations of multi-phase interface evolution. Another problem we investigated was user-assisted image editing, such as segmentation or colorization, by means of information propagation via minimal-length paths between pixels. We suggested an efficient method for precise computation of these lengths, or distances, by re-formulating the problem in the domain of image level sets, where the distances could be computed without introducing approximation errors, unavoidable when working with the standard image representation.


In the second part of this thesis, we investigated the problem of non-rigid isometric shape correspondence. In its most general formulation, it is a combinatorial problem, which does not make use of the smooth nature of the shapes. We suggested two approaches to facilitate correspondence computation.

In the first approach, we suggested a multi-resolution matching algorithm for solving the correspondence problem, when the latter was formulated as a direct comparison of intrinsic shape properties. In our second approach, we translated the matching problem into the spectral domain of the shapes. We showed that in this new domain, the size of the matching problem could be significantly reduced, while still allowing to obtain accurate matching between the shapes.