🚀 go-pugleaf

THE DISSERTATION DEFENSE FOR THE DEGREE OF Ph.D. IN COMPUTER SCIENCE FOR

                       			Sameer Sheorey

Will be held:

DATE:            		Tuesday October 21, 2008 at 4:00.p. m.
LOCATION:       	Room 3450 A.V. Williams Building

TITLE:            		Recognition and Matching in the Presence of
Deformation and Lighting Change

ABSTRACT:   Natural images of objects and scenes show a fascinating amount
of variability due to different factors like lighting change, viewpoint
change, occlusion and even articulation and non-rigid deformation. In this
thesis, we develop a fast algorithm for comparing histogram descriptors, a
deformation invariant representation for images and a more accurate method
for model based recognition of specular objects.

Histograms are a powerful statistical representation for keypoint matching
and content based image retrieval. The earth mover's distance (EMD) is an
important perceptually meaningful metric for comparing histograms, but it
suffers from high (O(n^3 log n)) computational complexity. We propose a
novel linear time algorithm for approximating the EMD for low dimensional
histograms using the sum of absolute values of the weighted wavelet
coefficients of the difference histogram.  EMD computation is a special case
of the Kantorovich-Rubinstein transshipment problem, and we exploit the
H\"older continuity constraint in its dual form to convert it into a simple
optimization problem with an explicit solution in the wavelet domain.  We
prove that the resulting wavelet EMD metric is equivalent to EMD, i.e. the
ratio of the two is bounded.  We also provide estimates for the bounds. The
weighted wavelet transform can be computed in time linear in the number of
histogram bins, while comparison is about as fast as for the normal
Euclidean distance or chi^2 statistic. We experimentally show that wavelet
EMD is a good approximation to EMD, has similar performance, but requires
much less computation. We also show that the same algorithm can be used to
compare histograms with unequal mass. We also provide an algorithm that
computes the best match between a histogram and a scaled version of another
histogram. For practical evaluation of these techniques, we have a C++
implementation of the fast lifting wavelet transform algorithm for arbitrary
dimensional histograms.

An image of a non-planar object can undergo a large non-linear deformation
due to a viewpoint change. Complex deformations occur in images of non-rigid
objects, for example, in medical image sequences.  We propose using the
contour tree as a novel framework invariant to arbitrary (smooth)
deformations for representing and comparing images. The contour tree encodes
the arrangement of the iso-intensity contours of an image and is invariant
to arbitrary deformations since it does not depend on the shape of the
contours.  It represents all the deformation invariant information in an
image. Computing the edit distance between two trees gives us a measure of
the deformation invariant distance between the two corresponding images.
This distance measure can also take into account various other difficulties
of image matching, such as noise, occlusion and lighting changes.

Lighting changes greatly affect the appearance of all objects and make
recognition difficult. Recognition of specular objects is particularly
difficult because their appearance is much more sensitive to lighting
changes than that of Lambertian objects.  We consider an approach in which
we use a 3D model to deduce the lighting that best matches the model to the
image.  In this case, an important constraint is that incident lighting
should be non-negative everywhere. We propose a new method to enforce this
constraint and explore its usefulness in specular object recognition, using
the spherical harmonic representation of lighting.  The method follows from
a novel extension of  Szego's eigenvalue distribution theorem to spherical
harmonics, and uses semidefinite programming to perform a constrained
optimization.  The new method is faster as well as more accurate than
previous methods. Experiments on both synthetic and real data indicate that
the constraint can improve recognition of specular objects by better
separating the correct and incorrect models.

Examining Committee:

COMMITTEE CHAIR:       	 Dr. David Jacobs
Dean's Representative: 		 Dr. Eitan Tadmor
Committee Member(s):   	 Dr. Larry Davis
                      			 Dr. Ramani Duraiswami
                        		 Dr. David Mount

EVERYONE IS INVITED TO ATTEND THE PRESENTATION PORTION OF THIS DEFENSE