In this paper, we describe a unique new paradigm for video database management known as ViBE (video indexing and browsing environment). ViBE is a browseable/searchable paradigm for organizing video data containing a large number of sequences. The system first segments video sequences into shots by using a new feature vector known as the Generalized Trace obtained from the DC-sequence of the compressed data. Each video shot is then represented by a hierarchical structure known as the shot tree. The shots are then classified into pseudo-semantic classes that describe the shot content. Finally, the results are presented to the user in an active browsing environment using a similarity pyramid data structure. The similarity pyramid allows the user to view the video database at various levels of detail. The user can also define semantic classes and reorganize the browsing environment based on relevance feedback. We describe how ViBE performs on a database of MPEG sequences.

The advent of large image databases (>10000) has created a need for tools which can search and organize images automatically by their content. This paper focuses on the use of hierarchical tree-structures to both speed-up search-by-query and organize databases for effective browsing. The first part of this paper develops a fast search algorithm based on best-first branch and bound search. This algorithm is designed so that speed and accuracy may be continuously traded-off through the selection of a parameter lambda. We find that the algorithm is most effective when used to perform an approximate search, where it can typically reduce computation by a factor of 20-40 for accuracies ranging from 80% to 90%. We then present a method for designing a hierarchical browsing environment which we call a similarity pyramid. The similarity pyramid groups similar images together while allowing users to view the database at varying levels of resolution. We show that the similarity pyramid is best constructed using agglomerative (bottom up) clustering methods, and present a fast sparse clustering method which dramatically reduces both memory and computation over conventional methods.

We exploit the techniques of tree structured vector quantization (TSVQ), branch and bound search, and the triangle inequality to speed the search of large image databases. Our method can reduce search computation required to locate images which best match a query image provided by a user. While exact search is possible, a free parameter allows search accuracy to be reduced, thereby providing a substantially better speed-up versus accuracy tradeoff.