Similarity-based image retrieval is an advanced method of searching images from image databases. Specifying required image contents as a query image, the image database system finds images having similar contents to a query image. To realize such a system, image contents have to be indexed beforehand in a form understandable by computers. To make this indexing process more clear and less complex, a six-layer hierarchical model is proposed. This model works as a framework for constructing different image databases; specific methods used in each layer may be domain dependent, but the hierarchical structure of the whole system remains the same for all kinds of images.

Among methods proposed in this thesis, five methods are explained in detail. The first method is a pixel-based image classification method particularly formulated for images with many mixels (mixed pixels). This method is used in "Pixel Layer" of the hierarchical model. By focusing on the stochastic properties of mixels, the area proportion of each class is estimated based on expectation. This expectation is calculated from the density of each class, whose parameters are obtained from mixture density estimation applied to the image histogram. However, an important hypothesis is derived from the stochastic model of mixels; if many mixels appear on an image, they form a new density on the histogram of an image. This new density called "mixel density" is characteristic in shape; it extends between pure pixel densities and has a flat region around the center of the density. Including mixel densities into mixture density estimation, each pixel is classified into either a pure pixel or a mixel based on Bayes decision rule.

Next the method of shape decomposition applicable to both binary images and gray-scale images is proposed for "Region Layer" of the hierarchical model. The purpose of this layer is to analyze properties of a set of mixels that forms a region. This method is inspired by so-called deformable models based on the energy-minimization framework. Decomposition elements used to describe natural shapes are either ellipses or superellipses in this thesis.

The purpose of the next layer, "Relation Layer," is to integrate various image properties obtained through lower layers into a single image representation model. Spatial relationship between elements is modeled as imaginary gravity, and image properties are integrated into an image representation model called "Hierarchical Attributed Relational Graph Structure." This graph structure represents regional information in its nodes, and spatial information in its arcs. Thus both types of image information are described with a single model.

After an image is represented by a graph structure, the problem of similarity-based image retrieval becomes equivalent to the problem of calculating distance between graph structures archived in image databases. Distance between graph structures is calculated by searching in the search space for a path with minimum matching cost, and the purpose of this layer, "Recognition Layer," is to speed up this exhaustive search. For this purpose, best-first search method (A* algorithm) and several speedup schemes are proposed and compared in their effectiveness.

The final layer, "Understanding Layer," aims at reflecting users' intention to image retrieval. To change the significance of each image property, parameters called weighting factors are introduced into graph matching cost. They are then optimized for retrieving user-selected (subjectively) similar images in higher orders. For optimization, Genetic algorithm (GA) is used, both conventional GA and a new GA-based method "life-cycle-based GA" tailored to "artificial selection" framework.

Three types of image databases are tested in this thesis, namely NOAA satellite image database, GMS satellite image database, and natural color image database. Experiments of image retrieval on three databases are done and results are examined from the viewpoint of accuracy, speed, and flexibility. The result shows that weighting factors are optimized so that user-selected similar images are retrieved in higher orders, which means weighting factors are effective in reflecting users' intention in a flexible way. Another result is that the hierarchical model eases the systematic construction of the different types of image databases, thus the hierarchical model can be the framework of image database systems.

      @PhdThesis{ k:phdthesis, 
      author = {Asanobu KITAMOTO},
      title = {Similarity-Based Image Retrieval Using a Graph Structure Representing Regional and Spatial Information},
      school = {Department of Electronic Engineering, Faculty of Engineering, University of Tokyo},
      year = 1997,
      month = 3,
      note = { (in Japanese)},
      }