M.Sc Thesis

M.Sc StudentLanda Zoya
Subject2D Object Description and Classification Based on Contour
Matching by Implicit Polynomials
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROFESSOR EMERITUS David Malah
DR. Meir Bar-Zohar


In this work we present several techniques for improving 2D object  description and classification based on coefficients of implicit  polynomials (IP), fitted to the object boundary. We first improve the description abilities of the Min-Max and Min-Var algorithms (A. Helzer, M. Barzohar, D. Malah, 2004) by replacing algebraic distances by geometric ones in a cost function used by these algorithms. We show that a polynomial of a predetermined degree would have a difficulty to distinguish among objects which are too complicated to be modeled by a polynomial of this degree. On the other hand, fitting of much simpler objects, which can be successfully modeled by a polynomial of a lower degree, would result in a polynomial whose coefficients are sensitive to even small perturbations of the data-set. Therefore, a classifier based on fitting of a polynomial of a single predetermined degree would have a low classification rate if applied to a database that contains both simple and complicated shapes. We propose a classification approach that is based on fitting several polynomials to the object shape, each having a different degree, and on their fitting errors, which improves considerably the classification. This Multi-Order (degree) and Fitting Errors Technique (MOFET) approach is shown to be much more efficient for classification than previously used IP-based classification techniques.

A major issue in classifying 2D objects is that they may have undergone an Affine transform, relative to the corresponding object in the data-base. We first apply linear rotation invariants that are based on the polynomial coefficients (Tarel et. Al. 1998) and modify accordingly the Min-Max and Min-Var fitting algorithms.

We then propose a Shape Transform, based on the Scatter Matrix of a shape, which transforms each object to its "Mother Shape". The Mother Shape is unique, up to rotation, for all the objects which are linearly related to the original shape. This way, by carrying out the fitting and classification on mother-shapes, using the above rotation invariants, extends the invariance to Affine transforms as well. Simulation results show the advantage of this approach over the standard Curvature Scale Space (CSS) classification technique, which is part of MPEG-7.