Comments: It's my Ph.D. dissertation. ContactPerson: ys2@cse.buffalo.edu Remote host: monet.cse.buffalo.edu ### Begin Citation ### Do not delete this line ### %R 2002-12 %U /projects/azhang/papers/Song/thesis.ps %A Song, Yuqing %T MONOTONIC TREE AND ITS APPLICATION TO MULTIMEDIA INFORMATION RETRIEVAL %D August 16, 2002 %I Department of Computer Science and Engineering, SUNY Buffalo %K monotonic tree, information retrieval, image retrieval, semantics %X Contour trees have been used in geographic information systems (GIS) and computer imag-ing to display scalar data. Contours are only defined for continuous functions. For discrete data, a continuous function is first defined as an interpolation of the data. Then a con-tour tree is defined on this continuous function. In this dissertation, we first introduce a new concept termed monotonic line, which models contour lines of discrete functions. All monotonic lines in a discrete function form a tree, called monotonic tree. As compared with contour trees, monotonic trees avoid the step of interpolation, thus can be computed and manipulated more efficiently. In addition, when used in image processing, monotonic trees retrieve similar structures as contour trees do while reserving the discreteness of image data. In computer imaging, the discreteness of image data is one main factor which makes image processing and understanding so difficult. The discreteness of image data itself is a research topic. Monotonic trees are used as a hierarchical representation of image structures in content-based multimedia retrieval. Although a variety of techniques have been developed for content-based image retrieval (CBIR), automatic image retrieval by semantics still remains a challenging problem due to the difficulty in object recognition and image understand- ing. In this dissertation, we present a novel approach to support semantics-based image retrieval on the basis of monotonic trees. The structural elements of an image are modeled as branches (or subtrees) of the monotonic tree. These elements are classified and clustered on the basis of such properties as color, spatial location, coarseness, and shape. Each cluster corresponds to some semantic feature. Following these steps, images can be automatically annotated with category keywords. So high-level (semantics-based) querying and brows-ing of images can be supported. This scheme is applied to retrieve scenery features from images and locate smooth background in images. Comparisons of experimental results of this approach with conventional techniques using low-level features demonstrate the effec-tiveness of our approach. In future work, the monotonic tree model will be extended to general semantic categories on both images and videos. This dissertation has two main contributions. The first contribution is the mathematical theory of monotonic tree, which is the first theory addressing definitions, properties, and computations of contour structures directly on discrete functions. The second contribution is the application of monotonic tree model to semantics-based image retrieval. The success of this model on scenery features and smooth background implies its potential in analyzing general semantics of both images and videos.