A survey of technologies for parsing and indexing digital video
---
paper_title: Visual reasoning for information retrieval from very large databases

paper_content:

When the database grows larger and larger, the user no longer knows what is in the database and nor does the user know clearly what should be retrieved. How to get at the data becomes a central problem for very large databases. We suggest an approach based upon data visualization and visual reasoning. The idea is to transform the data objects and present sample data objects in a visual space. The user can then incrementally formulate the information retrieval request in the visual space. By combining data visualization, visual query, visual examples and visual clues, we hope to come up with better ways for formulating and modifying a user's query. A prototype system using the Visual Language Compiler and the VisualNet is then described.
---
paper_title: SELECTION AND DISSEMINATION OF DIGITAL VIDEO VIA THE VIRTUAL VIDEO BROWSER

paper_content:

The Virtual Video Browser (VVB) is a manifestation of our mechanisms for the location, identification, and delivery of digital audio and video in a distributed system which can be extended to several application domains including multimedia-based home entertainment, catalog shopping, and distance learning. In the following sections we describe the VVB software application designed to allow the interactive browsing and content-based query of a video database and to facilitate the subsequent playout of selected titles.
---
paper_title: A similarity retrieval method for image databases using simple graphics

paper_content:

A retrieval method that uses key images is proposed for image databases. The key images represent layout information of the target image. Therefore, key images can appear explicitly in the target image. The layout information presentation scheme is also discussed. The key-image-matching method used to search for the target image in the database is described. Applying the concept of ambiguity to the matching method, users' requests can be reflected more accurately and flexibly. >
---
paper_title: Indexes for user access to large video databases

paper_content:

Video-on-Demand systems have received a good deal of attention recently. Few studies, however, have addressed the problem of locating a video of interest in a large video database. This paper describes the design and implementation of a metadata database and query interface that attempts to solve this information retrieval problem.© (1994) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: A three-dimensional iconic environment for image database querying

paper_content:

Retrieval by contents of images from pictorial databases can be effectively performed through visual icon-based systems. In these systems, the representation of pictures with 2D strings, which are derived from symbolic projections, provides an efficient and natural way to construct iconic indexes for pictures and is also an ideal representation for the visual query. With this approach, retrieval is reduced to matching two symbolic strings. However, using 2D-string representations, spatial relationships between the objects represented in the image might not be exactly specified. Ambiguities arise for the retrieval of images of 3D scenes. In order to allow the unambiguous description of object spatial relationships, in this paper, following the symbolic projections approach, images are referred to by considering spatial relationships in the 3D imaged scene. A representation language is introduced that expresses positional and directional relationships between objects in three dimensions, still preserving object spatial extensions after projections. Iconic retrieval from pictorial databases with 3D interfaces is discussed and motivated. A system for querying by example with 3D icons, which supports this language, is also presented. >
---
paper_title: Video query formulation

paper_content:

For developing advanced query formulation methods for general multimedia data, we describe the issues related to video data. We distinguish between the requirements for image retrieval and video retrieval by identifying queryable attributes unique to video data, namely audio, temporal structure, motion, and events. Our approach is based on visual query methods to describe predicates interactively while providing feedback that is as similar as possible to the video data. An initial prototype of our visual query system for video data is presented.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: IconicBrowser: An iconic retrieval system for object-oriented databases

paper_content:

From the point of view of the ability to manage complex data, object-oriented database systems are superior to conventional database systems. Query languages for object-oriented databases, however, tend to be overly complicated for the casual user unfamiliar with sophisticated database manipulation. This paper describes an IconicBrowser which allows the user to retrieve objects in a database by means of icons. Icons represent classes and objects in the database. Queries are specified by overlapping one icon over another. The system then interprets them into the database operations depending on their combination, and at the same time generates predicate-based (text-base) queries which can be used in other applications of the database.
---
paper_title: PICQUERY: a high level query language for pictorial database management

paper_content:

A reasonably comprehensive set of data accessing and manipulation operations that should be supported by a generalized pictorial database management system (PDBMS) is proposed. A corresponding high-level query language, PICQUERY, is presented and illustrated through examples. PICQUERY has been designed with a flavor similar to QBE as the highly nonprocedural and conservational language for the pictorial database management system PICDMS. PICQUERY and a relational QBE-like language would form the language by which a user could access conventional relational databases and at the same time pictorial databases managed by PICDMS or other robust PDBMS. This language interface is part of an architecture aimed toward data heterogeneity transparency over pictorial and nonpictorial databases. >
---
paper_title: Media Streams: an iconic visual language for video annotation

paper_content:

In order to enable the search and retrieval of video from large archives, we need a representation of video content. Although some aspects of video can be automatically parsed, a detailed representation requires that video be annotated. We discuss the design criteria for a video annotation language with special attention to the issue of creating a global, reusable video archive. Our prototype system, Media Streams, enables users to create multi-layered, iconic annotations of streams video data. Within Media Streams, the organization and categories of the Director's Workshop allow users to browse and compound over 2200 iconic primitives by means of a cascading hierarchical structure which supports compounding icons across branches of the hierarchy. The problems of creating a representation of action for video are given special attention, as well as describing transitions in video. >
---
paper_title: PROBE Spatial Data Modeling in an Image Database and Query Processing Application

paper_content:

Abstracf-The PROBE research project has produced results in the areas of data modeling, spatial/temporal query processing, recursive query processing, and database system architecture for “nontraditional” application areas, many of which involve spatial data and data with complex structure. PROBE provides the point se? as a construct for modeling spatial data. This abstraction is compatible with notions of spatial data found in a wide variety of applications. PROBE is extensible and supports a generalization hierarchy, so it is possible to incorporate application-specific implementations of the point set abstraction. PROBE’s query processor supports point sets with the geometry filter, an optiniizer of spatial queries. Spatial queries are processed by decomposing them into 1) a set-at-a-time portion that is evaluated efficiently by the geometry filter and 2) a portion that involves detailed nianipulations of individual spatial objects by functions supplied with the application-specific representation. The output from the first step is an approximate answer, which is refined in the second step. The data model and the geometry filter are valid in all dimensions, and they are compatible with a wide variety of representations. PROBE’S spatial data model and geometry filter are described, and it is shown how these facilities can be used to support image database applications.
---
paper_title: SELECTION AND DISSEMINATION OF DIGITAL VIDEO VIA THE VIRTUAL VIDEO BROWSER

paper_content:

The Virtual Video Browser (VVB) is a manifestation of our mechanisms for the location, identification, and delivery of digital audio and video in a distributed system which can be extended to several application domains including multimedia-based home entertainment, catalog shopping, and distance learning. In the following sections we describe the VVB software application designed to allow the interactive browsing and content-based query of a video database and to facilitate the subsequent playout of selected titles.
---
paper_title: Query by image and video content: the QBIC system

paper_content:

Research on ways to extend and improve query methods for image databases is widespread. We have developed the QBIC (Query by Image Content) system to explore content-based retrieval methods. QBIC allows queries on large image and video databases based on example images, user-constructed sketches and drawings, selected color and texture patterns, camera and object motion, and other graphical information. Two key properties of QBIC are (1) its use of image and video content-computable properties of color, texture, shape and motion of images, videos and their objects-in the queries, and (2) its graphical query language, in which queries are posed by drawing, selecting and other graphical means. This article describes the QBIC system and demonstrates its query capabilities. QBIC technology is part of several IBM products. >
---
paper_title: Indexes for user access to large video databases

paper_content:

Video-on-Demand systems have received a good deal of attention recently. Few studies, however, have addressed the problem of locating a video of interest in a large video database. This paper describes the design and implementation of a metadata database and query interface that attempts to solve this information retrieval problem.© (1994) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Delivering interactive multimedia documents over networks

paper_content:

A family of applications that consists of interactive multimedia documents, such as electronic magazines and interactive TV shows, is examined and the links between application architecture, user behavior, and network performance are investigated. The kinds of application-specific information that influence the end-to-end quality of service are discussed. The architecture and dynamics of the interactive document in terms of presentation objects (P-Objects), which are the segments of information accessed by the application and which are described according to their size, media composition, and access links, are described. The same structural characteristics that may make an interactive multimedia document appealing to the end user are the characteristics that are helpful during dynamic network performance optimization. This observation is based on the hypothesis that the P-Objects' access graph, together with viewing time statistics, is the information most useful to the network delivery control mechanism for optimizing network performance. Preliminary guidelines for both network and application designers to address each other's concerns are presented. >
---
paper_title: Cinematic primitives for multimedia

paper_content:

The development of robust frameworks in interactive multimedia for representing story elements to the machine so that they can be retrieved in multiple contexts is addressed. Interactive multimedia is discussed as a user-directed form of storytelling, and the nature of cinematic storytelling is examined. It is proposed that content can be represented in layers. This model for layered information will allow programs to take advantage of the relation between cinematic sequences and the world they represent. The collection of content by the camera and microphone is considered in this context. The use of the methodology to build meaningful, context-rich sequences is discussed. >
---
paper_title: Multiresolution video indexing for subband coded video databases

paper_content:

In this paper we present a multiresolution approach for video indexing and feature matching of subband coded video databases. Subband coding refers to a coding technique where the input images are quantized after being decomposed into several narrow spatial frequency bands by filtering and decimation. Five different approaches were tested for scene change detection which is applied only on the lowest subband for computational efficiency. Two kinds of scene changes, abrupt and smoothly accumulated scene changes, mark the beginning of new scene segments. An index for each scene segment is the histogram of two representative frames, which we take to be the first and the last frame of the scene for simplicity. Using the approach of query by example, the index matching algorithm takes a multi-resolution approach by hierarchically comparing histograms at different resolutions. The search algorithm for the match between example query and its target scene segment starts from the coarsest resolution, and moves to the next finer resolution until a single match is obtained or the finest resolution is reached. Experimental results are presented, and the proposed indexing technique appears to be promising for its computational efficiency and its inherent hierarchical search procedure.
---
paper_title: Scene change detection and content-based sampling of video sequences

paper_content:

Digital images and image sequences (video) are a significant component of multimedia information systems, and by far the most demanding in terms of storage and transmission requirements. Content-based temporal sampling of video frames is proposed as an efficient method for representing the visual information contained in the video sequence by using only a small subset of the video frames. This involves the identification and retention of frames at which the contents of the scene is `significantly' different from the previously retained frames. It is argued that the criteria used to measure the significance of a change in the contents of the video frames are subjective, and performing the task of content-based sampling of image sequences, in general, requires a high level of image understanding. However, a significant subset of the points at which the contextual information in the video frames change significantly can be detected by a `scene change detection' method. The definition of a scene change is generalized to include not only the abrupt transitions between shots, but also gradual transitions between shots resulting from video editing modes, and inter-shot changes induced by camera operations. A method for detecting abrupt and gradual scene changes is discussed. The criteria for detecting camera-induced scene changes from camera operations are proposed. Scene matching is proposed as a means of achieving further reductions in the storage and transmission requirements.
---
paper_title: Automatic partitioning of full-motion video

paper_content:

Partitioning a video source into meaningful segments is an important step for video indexing. We present a comprehensive study of a partitioning system that detects segment boundaries. The system is based on a set of difference metrics and it measures the content changes between video frames. A twin-comparison approach has been developed to solve the problem of detecting transitions implemented by special effects. To eliminate the false interpretation of camera movements as transitions, a motion analysis algorithm is applied to determine whether an actual transition has occurred. A technique for determining the threshold for a difference metric and a multi-pass approach to improve the computation speed and accuracy have also been developed.
---
paper_title: Video parsing using compressed data

paper_content:

Parsing video content is an important first step in the video indexing process. This paper presents algorithms to automate the video parsing task, including video partitioning and video clip classification according to camera operations using compressed video data. We have studied and implemented two algorithms for partitioning video data compressed according to the MPEG standard. The first one is based on discrete cosine transform coefficients of video frames, and the other based on correlation of motion vectors. Algorithms to detect camera operations using motion vectors are presented.
---
paper_title: The JPEG still picture compression standard

paper_content:

For the past few years, a joint ISO/CCITT committee known as JPEG (Joint Photographic Experts Group) has been working to establish the first international compression standard for continuous-tone still images, both grayscale and color. JPEG’s proposed standard aims to be generic, to support a wide variety of applications for continuous-tone images. To meet the differing needs of many applications, the JPEG standard includes two basic compression methods, each with various modes of operation. A DCT-based method is specified for “lossy’’ compression, and a predictive method for “lossless’’ compression. JPEG features a simple lossy technique known as the Baseline method, a subset of the other DCT-based modes of operation. The Baseline method has been by far the most widely implemented JPEG method to date, and is sufficient in its own right for a large number of applications. This article provides an overview of the JPEG standard, and focuses in detail on the Baseline method.
---
paper_title: Automatic partitioning of full-motion video

paper_content:

Partitioning a video source into meaningful segments is an important step for video indexing. We present a comprehensive study of a partitioning system that detects segment boundaries. The system is based on a set of difference metrics and it measures the content changes between video frames. A twin-comparison approach has been developed to solve the problem of detecting transitions implemented by special effects. To eliminate the false interpretation of camera movements as transitions, a motion analysis algorithm is applied to determine whether an actual transition has occurred. A technique for determining the threshold for a difference metric and a multi-pass approach to improve the computation speed and accuracy have also been developed.
---
paper_title: Scene change detection and content-based sampling of video sequences

paper_content:

Digital images and image sequences (video) are a significant component of multimedia information systems, and by far the most demanding in terms of storage and transmission requirements. Content-based temporal sampling of video frames is proposed as an efficient method for representing the visual information contained in the video sequence by using only a small subset of the video frames. This involves the identification and retention of frames at which the contents of the scene is `significantly' different from the previously retained frames. It is argued that the criteria used to measure the significance of a change in the contents of the video frames are subjective, and performing the task of content-based sampling of image sequences, in general, requires a high level of image understanding. However, a significant subset of the points at which the contextual information in the video frames change significantly can be detected by a `scene change detection' method. The definition of a scene change is generalized to include not only the abrupt transitions between shots, but also gradual transitions between shots resulting from video editing modes, and inter-shot changes induced by camera operations. A method for detecting abrupt and gradual scene changes is discussed. The criteria for detecting camera-induced scene changes from camera operations are proposed. Scene matching is proposed as a means of achieving further reductions in the storage and transmission requirements.
---
paper_title: Automatic partitioning of full-motion video

paper_content:

Partitioning a video source into meaningful segments is an important step for video indexing. We present a comprehensive study of a partitioning system that detects segment boundaries. The system is based on a set of difference metrics and it measures the content changes between video frames. A twin-comparison approach has been developed to solve the problem of detecting transitions implemented by special effects. To eliminate the false interpretation of camera movements as transitions, a motion analysis algorithm is applied to determine whether an actual transition has occurred. A technique for determining the threshold for a difference metric and a multi-pass approach to improve the computation speed and accuracy have also been developed.
---
paper_title: Automatic partitioning of full-motion video

paper_content:

Partitioning a video source into meaningful segments is an important step for video indexing. We present a comprehensive study of a partitioning system that detects segment boundaries. The system is based on a set of difference metrics and it measures the content changes between video frames. A twin-comparison approach has been developed to solve the problem of detecting transitions implemented by special effects. To eliminate the false interpretation of camera movements as transitions, a motion analysis algorithm is applied to determine whether an actual transition has occurred. A technique for determining the threshold for a difference metric and a multi-pass approach to improve the computation speed and accuracy have also been developed.
---
paper_title: Automatic partitioning of full-motion video

paper_content:

Partitioning a video source into meaningful segments is an important step for video indexing. We present a comprehensive study of a partitioning system that detects segment boundaries. The system is based on a set of difference metrics and it measures the content changes between video frames. A twin-comparison approach has been developed to solve the problem of detecting transitions implemented by special effects. To eliminate the false interpretation of camera movements as transitions, a motion analysis algorithm is applied to determine whether an actual transition has occurred. A technique for determining the threshold for a difference metric and a multi-pass approach to improve the computation speed and accuracy have also been developed.
---
paper_title: Automatic partitioning of full-motion video

paper_content:

Partitioning a video source into meaningful segments is an important step for video indexing. We present a comprehensive study of a partitioning system that detects segment boundaries. The system is based on a set of difference metrics and it measures the content changes between video frames. A twin-comparison approach has been developed to solve the problem of detecting transitions implemented by special effects. To eliminate the false interpretation of camera movements as transitions, a motion analysis algorithm is applied to determine whether an actual transition has occurred. A technique for determining the threshold for a difference metric and a multi-pass approach to improve the computation speed and accuracy have also been developed.
---
paper_title: Automatic partitioning of full-motion video

paper_content:

Partitioning a video source into meaningful segments is an important step for video indexing. We present a comprehensive study of a partitioning system that detects segment boundaries. The system is based on a set of difference metrics and it measures the content changes between video frames. A twin-comparison approach has been developed to solve the problem of detecting transitions implemented by special effects. To eliminate the false interpretation of camera movements as transitions, a motion analysis algorithm is applied to determine whether an actual transition has occurred. A technique for determining the threshold for a difference metric and a multi-pass approach to improve the computation speed and accuracy have also been developed.
---
paper_title: Video parsing using compressed data

paper_content:

Parsing video content is an important first step in the video indexing process. This paper presents algorithms to automate the video parsing task, including video partitioning and video clip classification according to camera operations using compressed video data. We have studied and implemented two algorithms for partitioning video data compressed according to the MPEG standard. The first one is based on discrete cosine transform coefficients of video frames, and the other based on correlation of motion vectors. Algorithms to detect camera operations using motion vectors are presented.
---
paper_title: A Guided Tour Of Computer Vision

paper_content:

An introduction to computer vision, covering the structure and properties of the visual world. This concise guide stresses fundamental concepts, and also provides details and pointers with respect to recent developments. The author pursues the narrow view of vision covering the structure and properties of the visual world, thereby providing a lucid introduction for the novice and a fresh perspective to the expert.
---
paper_title: Segmentation of Frame Sequences Obtained by a Moving Observer

paper_content:

In many applications of computer vision, a frame sequence may be acquired using a moving camera. We propose ego-motion polar transformation for segmentation of such sequences. It is shown that segmentation and extraction of motion information become easier in the transformed domain. Our experience with a translating camera indicates that this technique can play a very important role in the analysis of moving observer dynamic scenes.
---
paper_title: Multiresolution video indexing for subband coded video databases

paper_content:

In this paper we present a multiresolution approach for video indexing and feature matching of subband coded video databases. Subband coding refers to a coding technique where the input images are quantized after being decomposed into several narrow spatial frequency bands by filtering and decimation. Five different approaches were tested for scene change detection which is applied only on the lowest subband for computational efficiency. Two kinds of scene changes, abrupt and smoothly accumulated scene changes, mark the beginning of new scene segments. An index for each scene segment is the histogram of two representative frames, which we take to be the first and the last frame of the scene for simplicity. Using the approach of query by example, the index matching algorithm takes a multi-resolution approach by hierarchically comparing histograms at different resolutions. The search algorithm for the match between example query and its target scene segment starts from the coarsest resolution, and moves to the next finer resolution until a single match is obtained or the finest resolution is reached. Experimental results are presented, and the proposed indexing technique appears to be promising for its computational efficiency and its inherent hierarchical search procedure.
---
paper_title: Digital video segmentation

paper_content:

The data driven, bottom up approach to video segmentation has ignored the inherent structure that exists in video. This work uses the model driven approach to digital video segmentation. Mathematical models of video based on video production techniques are formulated. These models are used to classify the edit effects used in video and film production. The classes and models are used to systematically design the feature detectors for detecting edit effects in digital video. Digital video segmentation is formulated as a feature based classification problem. Experimental results from segmenting cable television programming with cuts, fades, dissolves and page translate edits are presented.
---
paper_title: Projection-detecting filter for video cut detection

paper_content:

This paper discusses a video cut detection method. Cut detection is an important technique for making videos easier to handle. First, this paper analyzes the distribution of the image differenceV to clarify the characteristics that makeV suitable for cut detection. We propose a cut detection method that uses a projection (an isolated sharp peak) detecting filter. A motion sensitiveV is used to stabilizeV projections at cuts, and cuts are detected more reliably with this filter. The method can achieve high detection rates without increasing the rate of misdetection. Experimental results confirm the effectiveness of the filter.
---
paper_title: Automatic partitioning of full-motion video

paper_content:

Partitioning a video source into meaningful segments is an important step for video indexing. We present a comprehensive study of a partitioning system that detects segment boundaries. The system is based on a set of difference metrics and it measures the content changes between video frames. A twin-comparison approach has been developed to solve the problem of detecting transitions implemented by special effects. To eliminate the false interpretation of camera movements as transitions, a motion analysis algorithm is applied to determine whether an actual transition has occurred. A technique for determining the threshold for a difference metric and a multi-pass approach to improve the computation speed and accuracy have also been developed.
---
paper_title: The R*-tree: an efficient and robust access method for points and rectangles

paper_content:

The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R * -tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R * -tree clearly outperforms the existing R-tree variants. Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R * -tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R * -tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.
---
paper_title: Description and performance analysis of signature file methods for office filing

paper_content:

Signature files have attracted a lot of interest as an access method for text and specifically for messages in the office environment. Messages are stored sequentially in the message file, whereas their hash-coded abstractions (signatures) are stored sequentially in the signature file. To answer a query, the signature file is examined first, and many nonqualifying messages are immediately rejected. In this paper we examine the problem of designing signature extraction methods and studying their performance. We describe two old methods, generalize another one, and propose a new method and its variation. We provide exact and approximate formulas for the dependency between the false drop probability and the signature size for all the methods, and we show that the proposed method (VBC) achieves approximately ten times smaller false drop probability than the old methods, whereas it is well suited for collections of documents with variable document sizes.
---
paper_title: Indexes for user access to large video databases

paper_content:

Video-on-Demand systems have received a good deal of attention recently. Few studies, however, have addressed the problem of locating a video of interest in a large video database. This paper describes the design and implementation of a metadata database and query interface that attempts to solve this information retrieval problem.© (1994) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: A three-dimensional iconic environment for image database querying

paper_content:

Retrieval by contents of images from pictorial databases can be effectively performed through visual icon-based systems. In these systems, the representation of pictures with 2D strings, which are derived from symbolic projections, provides an efficient and natural way to construct iconic indexes for pictures and is also an ideal representation for the visual query. With this approach, retrieval is reduced to matching two symbolic strings. However, using 2D-string representations, spatial relationships between the objects represented in the image might not be exactly specified. Ambiguities arise for the retrieval of images of 3D scenes. In order to allow the unambiguous description of object spatial relationships, in this paper, following the symbolic projections approach, images are referred to by considering spatial relationships in the 3D imaged scene. A representation language is introduced that expresses positional and directional relationships between objects in three dimensions, still preserving object spatial extensions after projections. Iconic retrieval from pictorial databases with 3D interfaces is discussed and motivated. A system for querying by example with 3D icons, which supports this language, is also presented. >
---
paper_title: Prefix B-trees

paper_content:

Two modifications of B -trees are described, simple prefix B -trees and prefix B -trees. Both store only parts of keys, namely prefixes, in the index part of a B * -tree. In simple prefix B -trees those prefixes are selected carefully to minimize their length. In prefix B -trees the prefixes need not be fully stored, but are reconstructed as the tree is searched. Prefix B -trees are designed to combine some of the advantages of B -trees, digital search trees, and key compression techniques while reducing the processing overhead of compression techniques.
---
paper_title: ACCESS METHODS OF IMAGE DATABASE

paper_content:

The perception of spatial relationships among objects in a picture is one of the important selection criteria to discriminate and retrieve images in an image database system. The data structure called 2-D string, proposed by Chang et al., is adopted to represent the symbolic pictures. When there are a large number of images in the image database and each image contains many objects, the processing time for image retrievals is tremendous. It is essential to develop efficient access methods for these retrievals. In this paper, the efficient methods for retrieval by objects, retrieval by pairwise spatial relationships and retrieval by subpicture are proposed. All the methods are based on the superimposed coding technique.
---
paper_title: The K-D-B-tree: a search structure for large multidimensional dynamic indexes

paper_content:

The problem of retrieving multikey records via range queries from a large, dynamic index is considered. By large it is meant that most of the index must be stored on secondary memory. By dynamic it is meant that insertions and deletions are intermixed with queries, so that the index cannot be built beforehand. A new data structure, the K-D-B-tree, is presented as a solution to this problem. K-D-B-trees combine properties of K-D-trees and B-trees. It is expected that the multidimensional search effieciency of balanced K-D-trees and the I/O efficiency of B-trees should both be approximated in the K-D-B-tree. Preliminary experimental results that tend to support this are reported.
---
paper_title: Representation of multi-resolution symbolic and binary pictures using 2D H-strings

paper_content:

A type of quadtree data structure, called a 2D H-string, is proposed for representing symbolic and binary pictures. The approach has an embedding property that allows for spatial-relational operators to be easily inserted into the structure. Algorithms are presented for traversing 2D H-strings to carry out the processing needed and for intersecting two pictures directly on their 2D H-string representations. The space complexity of 2D H-strings is analyzed and compared with other quadtree data structures. It is shown to be efficient in terms of space complexity and effective in terms of cooperativeness with other spatial-relational operators. >
---
paper_title: A pictorial index mechanism for model-based matching

paper_content:

Abstract We are currently developing unified query processing strategies for image databases. To perform this task, model-based representations of images by content are being used, as well as a hierarchical generalization of a relatively new object-recognition technique called data-driven indexed hypotheses. As the name implies, it is index-based, from which its efficiency derives. Earlier approaches to data-driven model-based object recognition techniques were not capable of handling complex image data containing overlapping, partially visible, and touching objects due to the limitations of the features used for building models. Recently, a few data-driven techniques capable of handling complex image data have been proposed. In these techniques, as in traditional databases, iconic index structures are employed to store the image and shape representation in such a way that searching for a given shape or image feature can be conducted efficiently. Some of these techniques handle the insertion and deletion of shapes and/or image representations very efficiently and with very little influence on the overall system performance. However, the main disadvantage of all previous data-driven implementations is that they are main memory based. In the present paper, we describe a secondary memory implementation of data-driven indexed hypotheses along with some performance studies we have conducted.
---
paper_title: Access methods for text

paper_content:

This paper compares text retrieval methods intended for office systems. The operational requirements of the office environment are discussed, and retrieval methods from database systems and from information retrieval systems are examined. We classify these methods and examine the most interesting representatives of each class. Attempts to speed up retrieval with special purpose hardware are also presented, and issues such as approximate string matching and compression are discussed. A qualitative comparison of the examined methods is presented. The signature file method is discussed in more detail.
---
paper_title: Video parsing using compressed data

paper_content:

Parsing video content is an important first step in the video indexing process. This paper presents algorithms to automate the video parsing task, including video partitioning and video clip classification according to camera operations using compressed video data. We have studied and implemented two algorithms for partitioning video data compressed according to the MPEG standard. The first one is based on discrete cosine transform coefficients of video frames, and the other based on correlation of motion vectors. Algorithms to detect camera operations using motion vectors are presented.
---
paper_title: Multidimensional binary search trees used for associative searching

paper_content:

This paper develops the multidimensional binary search tree (or k -d tree, where k is the dimensionality of the search space) as a data structure for storage of information to be retrieved by associative searches. The k -d tree is defined and examples are given. It is shown to be quite efficient in its storage requirements. A significant advantage of this structure is that a single data structure can handle many types of queries very efficiently. Various utility algorithms are developed; their proven average running times in an n record file are: insertion, O (log n ); deletion of the root, O ( n ( k -1)/ k ); deletion of a random node, O (log n ); and optimization (guarantees logarithmic performance of searches), O ( n log n ). Search algorithms are given for partial match queries with t keys specified [proven maximum running time of O ( n ( k - t )/ k )] and for nearest neighbor queries [empirically observed average running time of O (log n ).] These performances far surpass the best currently known algorithms for these tasks. An algorithm is presented to handle any general intersection query. The main focus of this paper is theoretical. It is felt, however, that k -d trees could be quite useful in many applications, and examples of potential uses are given.
---
paper_title: The Grid File: An Adaptable, Symmetric Multikey File Structure

paper_content:

Traditional file structures that provide multikey access to records, for example, inverted files, are extensions of file structures originally designed for single-key access. They manifest various deficiencies in particular for multikey access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary and secondary keys. We start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. This leads to the notions of a grid partition of the search space and of a grid directory , which are the keys to a dynamic file structure called the grid file . This file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. We discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.
---
paper_title: Conceptual modeling of multimedia documents

paper_content:

An approach to the document-retrieval problem that aims to increase the efficiency and effectiveness of document-retrieval systems by exploiting the semantic contents of the documents is presented. The document retrieval problem is delineated, and conceptual document modeling basics and requirements are discussed. An experimental system, the Multimedia Office Server (Multos), which implements some of the document-model concepts described, is presented. >
---
paper_title: A unified approach to data modeling and retrieval for a class of image database applications

paper_content:

Recently, there has been widespread interest in various kinds of database management systems for managing information from images. Image Retrieval problem is concerned with retrieving images that are relevant to users’ requests from a large collection of images, referred to as the image database. Since the application areas are very diverse, there seems to be no consensus as to what an image database system really is. Consequently, the characteristics of the existing image database systems have essentially evolved from domain specific considerations [20]. In response to this situation, we have introduced a unified framework for retrieval in image databases in [17]. Our approach to the image retrieval problem is based on the premise that it is possible to develop a data model and an associated retrieval model that can address the needs of a class of image retrieval applications. For this class of applications, from the perspective of the end users, image processing and image retrieval are two orthogonal issues and this distinction contributes toward domain-independence. In this paper, we analyze the existing approaches to image data modeling and establish a taxonomy based on which these approaches can be systematically studied and understood. Then we investigate a class of image retrieval applications from the view point of their retrieval requirements to establish both a taxonomy for image attributes and generic retrieval types. To support the generic retrieval types, we have proposed a data model/framework referred to as AIR. AIR data model employs multiple logical representations. The logical representations can be viewed as abstractions of physical images at various levels. They are stored as persistent data in the image database. We then discuss how image database systems can be developed based on the AIR framework. Development of two image database retrieval applications based on our implementation of AIR framework are briefly described. Finally, we identify several research issues in AIR and our proposed solutions to some of them are indicated.
---
paper_title: Chabot: Retrieval from a Relational Database of Images

paper_content:

Selecting from a large, expanding collection of images requires carefully chosen search criteria. We present an approach that integrates a relational database retrieval system with a color analysis technique. The Chabot project was initiated at our university to study storage and retrieval of a vast collection of digitized images. These images are from the State of California Department of Water Resources. The goal was to integrate a relational database retrieval system with content analysis techniques that would give our querying system a better method for handling images. Our simple color analysis method, if used in conjunction with other search criteria, improves our ability to retrieve images efficiently. The best result is obtained when text-based search criteria are combined with content-based criteria and when a coarse granularity is used for content analysis. >
---
paper_title: SELECTION AND DISSEMINATION OF DIGITAL VIDEO VIA THE VIRTUAL VIDEO BROWSER

paper_content:

The Virtual Video Browser (VVB) is a manifestation of our mechanisms for the location, identification, and delivery of digital audio and video in a distributed system which can be extended to several application domains including multimedia-based home entertainment, catalog shopping, and distance learning. In the following sections we describe the VVB software application designed to allow the interactive browsing and content-based query of a video database and to facilitate the subsequent playout of selected titles.
---
paper_title: Query by image and video content: the QBIC system

paper_content:

Research on ways to extend and improve query methods for image databases is widespread. We have developed the QBIC (Query by Image Content) system to explore content-based retrieval methods. QBIC allows queries on large image and video databases based on example images, user-constructed sketches and drawings, selected color and texture patterns, camera and object motion, and other graphical information. Two key properties of QBIC are (1) its use of image and video content-computable properties of color, texture, shape and motion of images, videos and their objects-in the queries, and (2) its graphical query language, in which queries are posed by drawing, selecting and other graphical means. This article describes the QBIC system and demonstrates its query capabilities. QBIC technology is part of several IBM products. >
---

Title: A survey of technologies for parsing and indexing digital video

Section 1: Introduction
Description 1: This section introduces the background and the necessity for advanced technologies in parsing and indexing digital video.

Section 2: Video Data Indexing
Description 2: This section discusses the requirements for effectively indexing video data for easy retrieval, and mentions the primary approaches and systems used for video indexing.

Section 3: Video Data Modeling
Description 3: This section covers the methods of modeling video data, highlighting the differences between structured and unstructured data, and introduces various models for video data.

Section 4: Information Extraction
Description 4: This section describes the processes and techniques used for extracting useful information from video data, including automatic, manual, and hybrid extraction methods.

Section 5: Video Scene Dynamics
Description 5: This section explains the dynamics of video scenes, particularly focusing on the challenges of segmenting video data based on scene transitions.

Section 6: Pixel-Level Change Detection
Description 6: This section delves into the methods of detecting changes at the pixel level for video segmentation, discussing various algorithms and their robustness.

Section 7: Likelihood Ratio
Description 7: This section presents the likelihood ratio approach for detecting changes in video frames based on statistical characteristics of pixel intensities.

Section 8: Histogram Comparison
Description 8: This section explains the use of histogram comparison methods for detecting scene changes, highlighting gray-level and color histogram techniques.

Section 9: Twin-Comparison
Description 9: This section introduces the twin-comparison method for detecting gradual transitions in video scenes with special camera effects.

Section 10: Detection of Camera Motion
Description 10: This section describes the techniques used to detect camera motion, such as optical flow, for accurate video scene segmentation.

Section 11: Using DCT Coefficients in MPEG Encoded Video
Description 11: This section discusses the use of Discrete Cosine Transform (DCT) coefficients from MPEG encoded video for detecting camera breaks and segmentation.

Section 12: Segmentation Based on Object Motion
Description 12: This section covers the segmentation of video data based on the analysis of object motion within the video frames.

Section 13: Segmentation Based on Subband-Coded Video Data
Description 13: This section explains segmentation techniques for subband-coded video data, detailing various metrics used for video segmentation.

Section 14: Segmentation Based on Features
Description 14: This section outlines feature-based segmentation methods, including intensity edge analysis and chromatic scaling models.

Section 15: Data Representation and Organization
Description 15: This section reviews various data representation and organization techniques for indexing and retrieving video data, and compares different data structures and methods.

Section 16: Examples
Description 16: This section provides practical examples of video data indexing and retrieval for different types of video content, such as newscasts, distance learning, and surveillance.

Section 17: Conclusion
Description 17: This section concludes the paper, summarizing the findings and future directions in the field of video parsing and indexing technologies.