Finding color and shape patterns in images

This thesis is devoted to the Earth Mover's Distance and its use within content-based image retrieval (CBIR). The major CBIR problem discussed is the pattern problem: Given an image and a query pattern, determine if the image contains a region which is visually similar to the pattern; if so, find at least one such image region.; The Earth Mover's Distance (EMD) is an edit distance between distributions that allows for partial matching, and which has many applications in CBIR. We give a couple of modifications which make the EMD more amenable to partial matching, including the partial EMD in which only a given fraction of the weight in one distribution is forced to match weight in the other.; An important issue addressed in this thesis is the use of efficient, effective lower bounds on the EMD to speed up retrieval times. We contribute lower bounds that are applicable in the partial matching case in which distributions do not have the same total weight.; Another important problem in CBIR is the EMD under transformation (EMD$G$) problem: find a transformation of one distribution which minimizes its EMD to another, where the set of allowable transformations $G$ is given. The problem of estimating the size/scale at which a pattern occurs in an image is phrased and efficiently solved as an EMD$G$ problem.; For EMD$G$ problems with transformations that modify the points of a distribution but not its weights, we present a very general, monotonically convergent iteration called the FT iteration. This iteration may, however, converge to only a locally optimal EMD value and transformation. We also present algorithms that are guaranteed to find a globally optimal transformation when matching equal-weight distributions under translation.; Our pattern problem solution is the SEDL (Scale Estimation for Directed Location) content-based image retrieval system. Three important contributions of this system are (1) a general framework for finding both color and shape patterns, (2) the previously mentioned novel scale estimation algorithm using the EMD, and (3) a directed (as opposed to exhaustive) search strategy. We show that SEDL achieves excellent results for the color pattern problem on a database of product advertisements, and the shape pattern problem on a database of Chinese characters.