Advanced Image & Video Databases, CS545I, Winter 1999

Friday, January 22. Computational Metrics for Color, Position, Shape, and Motion

The seminar will be in two parts:

10-11AM Room 104 Gates. Oral exam of Scott Cohen on the topic "Finding Color and Shape Patterns in Images" (see Abstract below)

3:15- 4:40 Prof. Leonard Guibas, Computer Science Department, Stanford, will start with a very brief summary of the thesis results for those who cannot make the 10AM meeting. He will then talk at a more philosophical level and suggest further ideas and open directions on the topics of summarizing, comparing, and efficiently matching general distributions.

--------------------------------------------------

This talk presents the SEL (Scale Estimation for Directed Locatin) contnet-based image retrieval (CBIR) system which finds database images that contain a region similar to a given query pattern. The SEDL framework is general enough to find both color and shape patterns. SEDL achieves excellent results for (1) the color pattern problem on a database of product advertisements with product logos as queries, and (2) the shape pattern problem on a database of Chinese characters.

As its name implies, SEDL performs a directed (as opposed to exhaustive) pattern search once it has computed an estimate for the scale at which the pattern occurs within an image. If we imagine a search rectangle moving and changing size and orientation over the image, then this rectangle will eventuially converge or settle (SEDL) on the image area where the system believes the pattern exists. A few promising initial placements of search rectangles are efficiently computed at query time without having to examine image areas that obviously do not contain the pattern. The initial size of the search rectangle is determined by the scale estimate.

An important tool that is used extensively within SEDL is the Earth Mover's Distance (EMD) between distributions of mass in some feature space. I consider the problem of finding the transformation of one distribution that minimizes its EMD to another distribution. This problem arises in the SEDL scale estimation phase with transformations that change the amounts of masses but not their locations. It is also useful in CBIR to allow transformations that change mass locations but not mass amounts. For such transformations, I present an iteration that always converges to a locally optimal transformation, and identify cases in which the iteration is guaranteed to converge to a globally optimal transformation. The proposed iteration is very general, as it can be applied for several different (feature distance, transformation set) pairs.