A unified histogram-based multiresolution approach for content-based multimedia retrieval

This thesis presents a new unified method of data indexing and retrieval in order to improve retrieval time and maintain accuracy of content-based multimedia retrieval system. In particular, we have developed and demonstrated: (1) A unified, hierarchical histogram-based representation that can be used for any types of multimedia data. (2) A multiresolution search algorithm that is applicable to any data types (called the “datatype-based” approach). (3) New, multiresolution algorithms that allow searching for “parts of data” that are similar to the query (called the “sub-datatype-based” approach) and uniformly applicable to any data types. (4) Parallel and distributed algorithms that speedup search and retrieval on heterogeneous systems by taking into consideration system characteristics.; The unified, hierarchical histogram-based feature representation is based on the concept that each multimedia datatype can be represented as a k-dimensional signal in spatio-temporal domain. Characteristic features of a k-dimensional signal are extracted and stored into a hierarchical multidimensional structure, called the “k-tree.” Each node on the k-tree contains many histogram-based extracted features corresponding to the spatial and/or temporal positions in the original data.; The k-tree structure has four main benefits. First, the k-tree allows both the accuracy and the retrieval time to be dynamically adapted to the users' requirement. Second, processing on the k-tree is independent from datatypes and feature types. Third, comparisons of spatial constraints are reduced or eliminated. Fourth, the k-tree model allows different search approaches to be performed on the same databases. The k-tree is used to build a unified content-based retrieval model for all types of multimedia data in this thesis.; Proposed algorithms to search data that are similar to the input query regardless to size, scale, and aspect ratio, called “datatype-based” approach, is introduced. Using the same feature to search the data, the results using the k-tree approach are perceptually better than the results using non-k-tree algorithms, when positions of contents in the query are taken into consideration. Exploiting multiresolution processing, this algorithm can reduce retrieval time and maintain acceptable accuracy.; A new algorithm for “sub-datatype-based” approach, called “Generalized Virtual Node or GVN” algorithm, is introduced. The GVN algorithm can perform a search in time complexity O(log _k n), while that of a brute-force approach is O(nk), where n is a size of a piece of multimedia data. Using the GVN algorithm to search on the k-tree structure is datatype- and feature-independent.; To improve the retrieval time, we have investigated data-parallel approaches on the unified content-based multimedia retrieval system. Retrieval times of the systems using parallel approaches are faster than those of a single processor, without losing accuracy. To improve further, parallelism with static load balancing using the processor speeds is exploited. The results of the systems with load balancing demonstrate that the processors' efficiencies are better and the retrieval time are faster than those of the systems without load balancing. (Abstract shortened by UMI.)...