The Initial Placement Phase

During the initial placement phase, SEDL quickly identifes image regions 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 Main Ideas

The scale estimation phase returns an estimate for the scale c0 at which a pattern may occur within an image. Comparing the image signature (X,w) and the scaled pattern signature (Y,c0u) with the EMD yields both a distance d0 and an optimal flow F0=(f0ij), where the flow tells us which image colors match which pattern colors:

[d0,F0] = EMD((X,w),(Y,c0u)).

The flow variable f0ij is the amount of color j from the scaled pattern that matches color i in the image. Using the flow F0, we can compute the probability or confidence qi that an image pixel of color i is part of the pattern occurrence, assuming that the pattern does indeed occur within the image.

Assuming a good scale estimate, the sumjf0ij over all pattern colors j is a good estimate of the amount of image color i that is part of the pattern occurrence within the image. If this sum is equal to the total amount wi of color i within the image, then one is 100% confident that a random image pixel of color i is part of the pattern occurrence (assuming that the pattern is present in the image). In general, the probability qi that a random image pixel of color i is part of the pattern occurrence is

0 <= qi=sumjf0ij / wi <= 1.

The confidence qi is inversely related to the amount of backgound clutter of color i within the image. Here backgound clutter refers to all image pixels which are not part of the pattern occurence.

An example illustrating the confidence qi is given below.

[ip.mainidea.jpg]

Yellow is basically a 100% confidence color since all the yellow in the image is needed to match yellow in the scaled query. Purple is also a high confidence color. About 90% of the purple in the image is matched to purple in the scaled query. The confidence for purple is not 100% because the pattern does not include all the purple on the ziploc box, and the pattern is slightly underestimated in scale. White and black are low confidence colors. Although the white on the ziploc box within the image is needed to match white in the scaled query, there is a lot of other white in the image (the writings "I will keep my sandwich fresh" and "Ziploc has the lock on freshness", the chalk next to the ziploc box, and the white on the ziploc box that is not part of the pattern). The black in the image is not needed to match any color in the pattern.

The initial placement phase compares the local image color distribution inside of rectangular image regions to the color distribution of the pattern. The main idea here is that we only need to check image locations of high confidence colors. In the above ziploc example, we never need to examine a region in the upper part of the ziploc advertisement since there are only low confidence colors present (black and white). The search for image regions with similar color signature to the query is thus directed (the D in SEDL) by the high confidence colors. The size of the rectangular regions examined is determined by the scale estimate c0. The image signature is preprocessed in order to answer range search questions at query time : what are all the image regions inside a given rectangular area? This range search capability allows the system to compute the local image color signature inside of a rectangle.

Results

Some results from the initial placement phase are shown below. Here we asked for two promising image regions which may contain the pattern. To the right of each image is the pattern scaled according to the scale estimate.

In each of these examples, at least one of the initial placements significantly overlaps the pattern occurence. In the final tide example, where the scale is overestimated, one of the initial placements contains both occurrences of the pattern.
[ip-results.jpg]

More results from the initial placement phase are shown below.

As above, at least one of the initial placements significantly overlaps the pattern occurence in all these examples. In fact, one of the initial placements in the taco bell example is near perfect.
[ip-more-results.jpg]


top Title, Table of Contents, Introduction
prev The Scale Estimation Phase
next The Verification and Refinement Phase


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.