Technical Report MSC-2009-09

Title: Intrinsic regularization of inverse problems involving non-rigid shapes
Authors: Yohai Devir
Supervisors: Yuval Rabani
Abstract: In many visions problems, both human and computer, there is a need to reconstruct an unknown three dimensional object from a partial data that is derived from that object. This problem is ill-posed since in many cases, one may find a different object from which similar data can be derived. Therefore, it is common to solve a different problem in which except for the derived data there is some other prior knowledge about the nature of the unknown object. In this work we solve the problems where beside of the derived data, we are also given that the unknown object is similar to (a bending of) a known non-rigid object denoted as the prior. Many of the objects surrounding us are non-rigid in the sense that they have infinite variety of deformations preserving their topology and density. Among those, one may count the outer skin of living bodies, faces, cloths and others. Two objects that can be obtained from each other by means of non-rigid deformations are said to be intrinsically similar. Many intrinsic similarity measures are based on the geodesic distances between two points on the shape measuring the length of the minimal path contained in the shape connecting those two points. In computer vision applications, shapes are approximated by a set of samples forming a triangulated mesh. There are two common ways to approximate geodesic distances on meshes, using the Dijkstra's well known shortest paths algorithm and using the fast marching method (FMM), which lacks some of the inherent disadvantages of Dijkstra's algorithm. In this work, we propose to solve such reconstruction problems in the framework of optimization problems, where the optimization variables are the spatial locations of the shapes' vertices. In order to do so we enhance the FMM algorithm so that beside of approximating the geodetic distances, it also calculates the derivatives of those distances with respect to the spatial locations of the shape's vertices. Synthesis examples are given for a few shape reconstruction applications.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2009
To the main CS technical reports page

Computer science department, Technion