טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentRosman Guy
SubjectEfficient Flattening in Manifold Learning and Image
Processing
DepartmentDepartment of Computer Science
Supervisor Professor Ron Kimmel
Full Thesis textFull thesis text - English Version


Abstract

Multidimensional scaling is a family of computational methods that map the coordinates of a set of points given their pairwise distances into a simple low dimensional space.

It is used in various applications, ranging from dimensionality reduction of image manifolds to psychology and statistics.

MDS attempts to flatten the  data manifold, while preserving its geometric structure.


Images can be considered as two  dimensional manifolds.

For example, the Beltrami framework considers images as surfaces embedded in the 3-color plus 2-spatial coordinates hybrid domain.

The Beltrami flow, resulting from this outlook, is an effective filter in color image processing.

This flow gradually flattens the image manifold while maintaining its visual meaning.

It is closely related to the median, total variation, and bilateral filters.

Its computation is, however, costly, which is problematic for some applications.


In the first part we focus on accelerating these flattening processes.

We use vector extrapolation techniques in order to speed up the numerical solution of MDS problems, and in order to efficiently implement the Beltrami filter.

Vector extrapolation methods are often used to accelerate the convergence of fixed-point iterative algorithms.

We first review these techniques, detailing the theory in the case of linear iterative processes, and in the proximity of the fixed point for nonlinear processes.

We then review the MDS problem and the Beltrami framework and present examples of our accelerated solver for these applications. 


Next, in the context of manifold learning we introduce a new framework for considering non-local dissimilarities within the flat embedding procedure.

Unlike existing algorithms that use global distances, we use the topology of the manifold in order to avoid distances that could distort the embedding.

The idea is to filter out potentially problematic distances between feature points based on the geodesic connecting the points and its distance to the boundary of the feature manifold.

Since the proposed algorithm matches non-local structures, it is robust to noise.

Using our accelerated MDS solver we show experimental results demonstrating the advantages of the proposed approach over state-of-the-art methods.