The SEDL Image Retrieval System

My solution to the pattern problem is the SEDL (Scale Estimation for Directed Location) image retrieval system. Although the SEDL framework is general enough to be applied to both the color and shape pattern problem, I will describe SEDL as applied in the color case.

Overview

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 may occur within an image. If we imagine a search rectangle moving and changing size and orientation over the image, then this rectangle will eventually 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 rectangles is determined by the scale estimate. An overview of the three phases in SEDL is given in the next section.

The Three Phases

[overview.jpg]

The purpose of the scale estimation phase is to compute an estimate for the scale at which the pattern may occur within the image. In the example above, the pattern is about 10% of the image. The third column of the first row shows the pattern scaled to reflect the computed estimate. One can see that the estimate in this example is very accurate. The scale estimation phase uses the amounts of colors within the image and query pattern, but not their locations.

The purpose of the initial placement phase is to identify regions in the image that have a similar color histogram to the color histogram of the query. These are promising regions for the pattern occurrence, and will be explored further in the next phase. The size of each candidate region is determined by the scale estimate from the previous phase. There is preprocessing performed so that at query time the system never examines image locations which obviously do not contain the pattern.

During the final verification and refinement phase, the system checks/verifies that the positions of the colors within a promising image region make sense. At this time it also adjusts/refines its guess as to the scale, orientation, and location of the pattern in order to improve a match distance measure that uses the positions of uniform color regions within the query pattern and image. An iterative match improvement process is directed by the region colors since these colors are unchanged by the allowed similarity transformation of pattern region positions. Eventually, the search rectangle settles (SEDLs) on the image region where the system believes that the pattern occurs.

The Importance of Scale

The pattern scale determines the amount of information in the image to match. Below is an example that illustrates the importance of having an accurate estimate of scale.
[scale-importance.jpg]
The left column shows a pattern, an image containing the pattern, and decreasing size portions of the image which are all centered on the pattern occurrence. The center column shows the color signatures for the images in the left column. For example, the query contains about 25% dark blue, 5% white, 3% light blue, etcetera. The right column shows a distance measure known as the Earth Mover's Distance (EMD) between the pattern color signature and the signatures for the various portions of the image. The distance between the pattern and image signatures is relatively large (27.7). If we remove some of the background light brown from the image, the distance between color signatures decreases (to 19.8). If we look at almost exactly the occurrence of the pattern within the image, the distance reaches a minimum (at 5.5). If the scale is slightly underestimated, the distance increases (to 9.4). Finally, if we really underestimate the scale, the distance between color signatures becomes very high again (20.8).

The point here is that a system might falsely conclude that the pattern does not occur within an image because its scale estimate is incorrect. This can happen even when the system has the correct location for the pattern (as shown above).


top Title, Table of Contents, Introduction
prev The Pattern Problem
next Image Signatures


The ideas and results contained in this document are part of my thesis, which will be published as a Stanford computer science technical report in June 1999.

S. Cohen. Finding Color and Shape Patterns in Images. Thesis Technical Report STAN-CS-TR-99-?. To be published June 1999.

Email comments to scohen@cs.stanford.edu.