M.Sc Thesis

M.Sc StudentLeifman George
SubjectDetermining the Similarity of Three-Dimensional Objects
using Relevance Feedback
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Ayellet Tal
PROF. Ron Meir


This study addresses the problem of retrieving from a database of three-dimensional objects, represented by their polyhedral surfaces, the most similar objects to a given object. Shape-based retrieval is usually done in two steps. First, each object in the database is compactly represented by a signature. Second, a retrieval algorithm compares signatures and ranks objects according to the similarity of their signatures.

In the last few years, several papers dealing with three-dimensional object retrieval appeared. Most of the proposed signatures cannot handle objects represented by polyhedral surfaces having degenerated polygons or disconnected components. Those methods that work with such objects, usually describe only local properties of the objects using some statistical measures.

In this work we propose two novel signatures to capture the geometric structure of three-dimensional objects: Sphere Projection and Octrees. The Sphere Projection signature attempts to capture the global characteristics of the object by computing the amount of  “energy” required to deform it into a predefined three-dimensional shape. The idea of the Octrees signature is to represent an object hierarchically, so that a coarse-to-fine comparison can be applied to determine similarity. Finally, we show how to enrich the above geometric signatures with topological properties. We show that our method, in addition to tolerating degenerated surfaces and disconnected components, compares three-dimensional objects by capturing their global geometry and topology. Moreover, the object representation technique that we use can be naturally augmented with a relevance feedback scheme.

Object similarity is not only a geometric objective problem, but also a subjective matter, which is dependent on the human viewer. Our goal is to give the user an added ability of influencing the search as it is being conducted. In other words, we let the user mark results as relevant or irrelevant and consider this relevance feedback in order to update a distance measure between objects. We show how providing the user the ability to influence the search can be stated as a classification or as a learning problem.

Finally, we describe an experimental study comparing the quality of various signatures using several estimation measures. We also show the results of retrieval with relevance feedback and compare different relevance feedback methods.