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 and viewpoint change, occlusion, articulation and non-rigid deformation. There are certain cases like recognition of specular objects and images with arbitrary deformations where existing techniques do not perform well. For image deformation, we

propose a method for faster keypoint matching with histogram descriptors and a completely deformation invariant representation. We also propose a method for improving specular object recognition.

Histograms are a powerful statistical representation for keypoint matching and content based image retrieval. The <EM>earth mover's distance</EM> (EMD) is an important perceptually meaningful metric for comparing histograms, but it suffers from high (O(n<SUP>3</SUP> log n)) computational complexity. We propose a novel <em>linear time</em> algorithm for approximating EMD with the weighted L<SUB>1</SUB> norm of the wavelet transform of the difference histogram. We prove that the resulting wavelet EMD metric is equivalent to EMD. We experimentally show that wavelet EMD is a good approximation to EMD, has similar performance, but requires much less computation. We also give a fast algorithm for the best partial EMD match between two histograms.

Images of 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 <EM>contour tree</EM> as a novel framework invariant to arbitrary deformations for representing and comparing images. It represents all the deformation invariant information in an image.

Lighting changes greatly affect the appearance of <EM>specular</EM> objects and make recognition difficult much more than for Lambertian objects. In model based recognition of specular objects, an important constraint is that the estimated 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 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.