Video processing and computer vision communities usually employ shot-based or object-based structural video models and associate low-level (color, texture, shape, and motion) and semantic descriptions (textual annotations) with these structural (syntactic) elements. Database and information retrieval communities, on the other hand, employ entity-relation or object-oriented models to model the semantics of multimedia documents. This paper proposes a new generic integrated semantic-syntactic video model to include all of these elements within a single framework to enable structured video search and browsing combining textual and low-level descriptors. The proposed model includes semantic entities (video objects and events) and the relations between them. We introduce a new "actor" entity to enable grouping of object roles in specific events. This context-dependent classification of attributes of an object allows for more efficient browsing and retrieval. The model also allows for decomposition of events into elementary motion units and elementary reaction/interaction units in order to access mid-level semantics and low-level video features. The instantiations of the model are expressed as graphs. Users can formulate flexible queries that can be translated into such graphs. Alternatively, users can input query graphs by editing an abstract model (model template). Search and retrieval is accomplished by matching the query graph with those instantiated models in the database. Examples and experimental results are provided to demonstrate the effectiveness of the proposed integrated modeling and querying framework.

We propose a fully automatic and computationally efficient framework for analysis and summarization of soccer videos using cinematic and object-based features. The proposed framework includes some novel low-level processing algorithms, such as dominant color region detection, robust shot boundary detection, and shot classification, as well as some higher-level algorithms for goal detection, referee detection, and penalty-box detection. The system can output three types of summaries: i) all slow-motion segments in a game; ii) all goals in a game; iii) slow-motion segments classified according to object-based features. The first two types of summaries are based on cinematic features only for speedy processing, while the summaries of the last type contain higher-level semantics. The proposed framework is efficient, effective, and robust. It is efficient in the sense that there is no need to compute object-based features when cinematic features are sufficient for the detection of certain events, e.g., goals in soccer. It is effective in the sense that the framework can also employ object-based features when needed to increase accuracy (at the expense of more computation). The efficiency, effectiveness, and robustness of the proposed framework are demonstrated over a large data set, consisting of more than 13 hours of soccer video, captured in different countries and under different conditions.

In this paper an evolutionary algorithm (EA) is shown to be a feasible approach to solving the problem of determining the characteristics of wind gusts that result in critical loading of aircraft structures. The EA outperforms a traditional method suitable for solving linear problems, and is then extended to nonlinear problems for which there is no effective solution methodology.

In this paper, we present the tools standardized by MPEG-7 for describing the semantics of multimedia. In particular, we focus on the abstraction model, entities, attributes and relations of MPEG-7 semantic descriptions. MPEG-7 tools can describe the semantics of specific instances of multimedia such as one image or one video segment but can also generalize these descriptions either to multiple instances of multimedia or to a set of semantic descriptions. The key components of MPEG-7 semantic descriptions are semantic entities such as objects and events, attributes of these entities such as labels and properties, and, finally, relations of these entities such as an object being the patient of an event. The descriptive power and usability of these tools has been demonstrated in numerous experiments and applications, these make them key candidates to enable intelligent applications that deal with multimedia at human levels.

This paper proposes to integrate text-based database models (commonly used in the database and information retrieval literature) and low-level video features, such as object-based motion features (commonly used in image processing and computer vision), within a single framework to describe video events for fast and effective browsing and retrieval using a mixture of textual and low-level descriptors. The instantiations of the model are expressed as graphs. Users can formulate flexible queries that can be translated into such graphs. Alternatively, users can input query graphs by editing an abstract model (model template) derived either from a model database or from an example scene in the media database. Search and retrieval is accomplished by matching the query graph with those instantiated models in the database. The proposed approach allows for integrated textual and low-level, descriptor-based video search, where the integration is enabled by the model. Examples and experimental results are provided to demonstrate the effectiveness of the proposed integrated modeling and querying framework.

Robust face recognition is an important research area that has a great impact in the field of surveillance and human-computer interactions in general. This paper addresses how the concept of motion pursuit can bridge the alignment information with imagery similarities to form a joint decision for the purpose of robust face recognition. More explicitly, we perform multi-scale correspondence matching in a wavelet domain and utilize a simple motion measure in conjunction with wavelet response matching to form a discriminative face similarity measure. We demonstrate the efficacy of the proposed approach with a large consumer image database of diverse image capture conditions.

Effective and efficient representation of color features of multiple video frames or pictures is an important yet challenging task for visual information management systems. Key frame-based methods to represent the color features of a group of frames (GoF) are highly dependent on the selection criterion of the representative frame(s), and may lead to unreliable results. We present various histogram-based color descriptors to reliably capture and represent the color properties of multiple images or a GoF. One family of such descriptors, called alpha-trimmed average histograms, combine individual frame or image histograms using a specific filtering operation to generate robust color histograms that can eliminate the adverse effects of brightness/color variations, occlusion, and edit effects on the color representation. We show the efficacy of the alpha-trimmed average histograms for video segment retrieval applications, and illustrate how they consistently outperform key frame-based methods. Another color histogram descriptor that we introduce, called the intersection histogram, reflects the number of pixels of a given color that is common to all the frames in the GoF. We employ the intersection histogram to develop a fast and efficient algorithm for identification of the video segment to which a query frame belongs. The proposed color histogram descriptors have been included in the ISO standard MPEG-7 after extensive evaluation experiments.

This paper describes a hierarchical approach for object-based motion description of video in terms of object motions and object-to-object interactions. We present a temporal hierarchy for object motion description, which consists of low-level elementary motion units (EMU) and high-level action units (AU). Likewise, object-to-object interactions are decomposed into a hierarchy of low-level elementary reaction units (ERU) and high-level interaction units (IU). We then propose an algorithm for temporal segmentation of video objects into EMUs, whose dominant motion can be described by a single representative parametric model. The algorithm also computes a representative (dominant) affine model for each EMU. We also provide algorithms for identification of ERUs and for classification of the type of ERUs. Experimental results demonstrate that segmenting the life-span of video objects into EMUS and ERUs facilitates the generation of high-level visual summaries for fast browsing and navigation. At present, the formation of high-level action and interaction units is done interactively. We also provide a set of query-by-example results for low-level EMU retrieval from a database based on similarity of the representative dominant affine models.

We use Bayesian belief networks to statistically model the trends for event detection. We automatically detect non-rigid object trajectories for object motion units. Then, we use dominant and secondary trajectories of a single object in several consecutive motion units to understand semantic actions or those of more than one object to recognize semantic interactions between objects. We demonstrate sample Bayesian networks to detect events and extract the event descriptions, such as "catch the ball", "throw the ball" and "walk".

In our previous work, we developed a method to extract low-level elementary motion units (EMU) and elementary reaction units (ERU) for object-based event description, assuming perfect video object segmentation and tracking. This paper features the following contributions. (1) We propose a novel object tracking algorithm for a specific domain. (2) We evaluate the performance of our EMU and ERU extraction system with automatically-computed but imperfect video object information obtained by the proposed tracker. It is assumed that objects for which descriptors are sought for are interactively marked on the initial frame. (3) We extend the description of ERUs to enable better description of low-level reactions. Experimental results are provided to demonstrate each contribution.

Large scale deployment of digital multimedia applications requires effective and efficient image and video representations for indexing. We present a hierarchical representation of video objects based on their motion. The proposed representation enables both low and semantic level description of object motion. At the low level, we consider a parametric description of the dominant motion of video objects, and define elementary motion units (EMU) where the dominant motion of the object is coherent and does not undergo considerable change. A group of EMUs forms an action unit which carries semantic information. Interactions between objects are also considered by calculating the relative motion between objects in an object-based framework. Experimental results for retrieval of EMUs based on similarity of dominant object motion are demonstrated.

Joint representation of color-based features for multiple images or a video segment is an important task for visual information management systems. Generally, a key-frame or key-image is selected from such a group, and the color-related features of the entire collection are represented with those of the chosen sample. Such methods are highly dependent on the quality of the representative sample, and may lead to unreliable results. We present a set of histogram-based descriptors that reliably capture the color content of multiple images or video frames. These descriptors are defined for a group-of-frames (GoF) or a group-of-pictures (GoP). A single representation for the entire collection is obtained by combining individual frame or image histograms in various ways. We demonstrate the efficacy of GoF-histograms for video segment retrieval and the GoP-histograms for fast image search. This descriptor has been accepted to the Working Draft of MPEG-7, the evolving ISO standard for multimedia content description.

An algorithm for computing three-dimensional (3-D) velocity field and motion parameters from a range image sequence is presented. It is based on a new integral 3-D rigid motion invariant feature-the trace of a 3x3 "feature matrix" related to the moment of inertia tensor. This trace can be computed at every point of a moving surface and provides a quantitative measure of the local shape of the surface. Based on the feature's conservation along the trajectory of every moving point, a 3-D Flow Constraint Equation is formulated and solved for the velocity field. The robustness of the feature in presence of noise and discontinuity is analyzed.

A central step in content-based video retrieval is the temporal segmentation of video. An application independent approach to video segmentation is to detect temporally contiguous segments without significant content change between successive frames. Each such segment is termed a shot. A high-performance shot boundary detection-based video segmentation algorithm is proposed. The technique uses unsupervised clustering on a multiple feature input space, followed by a heuristic elimination process to detect, with almost perfect accuracy, shot boundaries in the video. With an extremely high accuracy coupled with a very small number of false positives, this algorithm outperforms most of the existing techniques.

In this paper, a novel model-based approach is proposed for generating a set of image feature maps (or primal sketches). For each type of feature, a piecewise smooth parametric model is developed to characterize the local intensity function in an image. Projections of the intensity profile onto a set of orthogonal Zernike-moment-generating polynomials are used to estimate model-parameters and, in turn, generate the desired feature map. A small set of moment-based detectors is identified that can extract various kinds of primal sketches from intensity as well as range images. One main advantage of using parametric model-based techniques is that it is possible to extract complete information (i.e., model parameters) about the underlying image feature, which is desirable in many high-level vision tasks. Experimental results are included to demonstrate the effectiveness of proposed feature detectors.

A new computational model for optical flow estimation is proposed. The proposed model utilizes trajectory information present in a multiframe spatio-temporal volume. Optical flow estimation is formulated as an optimization problem. The solution to this optimization problem yields a velocity field corresponding to smoothest and shortest trajectories of constant intensity points within the spatio-temporal volume. The approach is motivated by principles of inertia of motion and least action in physics and vision psychology. An analogy between a trajectory and a "thin wire" is discussed. A simple mechanism for handling trajectory discontinuities is also incorporated. The optimization problem is solved by stochastic relaxation techniques. Some experimental results and performance comparisons with two existing optical flow estimation techniques are presented to demonstrate the effectiveness of the proposed approach.>

Connected components detection and labeling is an essential step in many image analysis techniques. The efficiency of the connected components labeling algorithm is critical for many image processing and machine vision applications that require real time response. The advances in the areas of parallel processing and VLSI technology can be exploited in designing hardware algorithms of high speed and throughput. In this paper, the authors propose a systolic algorithm and architecture for finding connected components in an image. The architecture is simple and can be implemented as a special purpose VLSI chip. Although, the algorithm has a time complexity of O(N/sup 2/), this is in terms of the actual clock cycle which is estimated as 25 nano seconds. The proposed hardware can process a 128/spl times/128 image in 0.85 msec and uses 128 processors whereas the MPP requires 94.6 msec with 16384 processors. The only special purpose hardware that exists requires 300 msec to label a 512/spl times/512 image which can be accomplished in 13.5 msec using the authors' proposed hardware.>

A novel model-based unified approach is proposed for generating a set of image feature maps (or primal sketches). For each type of feature, a parametric model is developed to characterize the local intensity function in an image. Projections of intensity profile onto a set of orthogonal Zernike moment-generating polynomials are used to estimate model-parameters and in turn generate the desired feature map. A small set of moment-based detectors is identified that can extract various kinds of primal sketches from intensity as well as range images. One main advantage of using parametric model-based techniques is that it is possible to extract complete information (i.e., model parameters) about the underlying image feature, which is desirable in many high-level vision tasks. Experimental results are included to demonstrate the effectiveness of the proposed feature detectors.>

The paper presents a robust algorithm for computation of optical flow using the principle of conservation of a set of semi-invariant local features that are representatives of local gray-level properties in an image. Specifically, a set of rotation-invariant local orthogonal Zernike moments is used as features. These are inherently integral-based features, and therefore are robust against possible variations of intensity values that may occur over a sequence of images due to sensor noise, varying illumination etc. The 2D local optical flow field is obtained by the singular value decomposition of an overdetermined set of linear equations of velocity field components, resulting from the principle of conservation of features in a small neighborhood. The proposed approach is compared with Horn-Schunck (1981), and Lucas-Kanade's optical flow techniques. Experimental results with synthetic as well as real sequences are presented to demonstrate the effectiveness of the proposed approach.>

An algorithm for computing 3D motion (velocity field and motion parameters) from a sequence of range images is presented. The algorithm is based on a new integral 3D rigid motion invariant feature which can be computed locally at every point of the moving surface. This feature is the trace of a 3/spl times/3 matrix (referred to as "feature matrix" in the paper) which is closely related to the moment of inertia tenser in physics. This trace of the "feature matrix" at any point provides a quantitative measure of the local shape of the surface around that point. Since the trace feature is rigid motion invariant, it remains conserved along the trajectory of every moving point. Based on that, a 3D flow constraint equation is formulated at every point on the surface, which can be solved for the velocity at the point using optical flow techniques. Since the proposed feature is integral in nature, it is robust in terms of noise and discontinuity in the moving surface. Theoretical analysis is provided to justify these claims. Experimental results are also provided to justify the efficacy of the method.>

The paper presents a new parametric model-based approach to high-precision composite edge detection using orthogonal Zernike moment-based operators. It deals with two types of composite edges: (a) generalized step and (b) pulse/staircase edges. A 2-D generalized step edge is modeled in terms of five parameters: two gradients on two sides of the edge, the distance from the center of the candidate pixel, the orientation of the edge and the step size at the location of the edge. A 2-D pulse/staircase edge is modeled in terms of two steps located at two positions within the mask, and the edge orientation. A pulse edge is formed if the steps are of opposite polarities whereas a staircase edge results from two steps having the same polarity. Two complex and two real Zernike moment-based masks are designed to determine parameters of both the 2-D edge models. For a given edge model, estimated parameter values at a point are used to detect the presence or absence of that type of edge. Extensive noise analysis is performed to demonstrate the robustness of the proposed operators. Experimental results with intensity and range images are included to demonstrate the efficacy of the proposed edge detection technique as well as to compare its performance with the geometric moment-based step edge detection technique and Canny's (1986) edge detector.

Efficient management of non-alphanumeric data (such as images, videos, and graphs) is essential to a large number of applications.This paper discusses the issues in pictorial information modeling, examines the suitability of traditional data modeling approaches, and then proposes a new objectoriented data modeling approach, called Modeling Object- Oriented Data Semantics (MOODS).A key idea in MOODS is to integrate the image processing component of an image information management system with the data modeling technique.In addition, a user may provide additional assistance in defining semantics at various stages.We argue that the data modeling technique must capture the sequence of transformations and allow a variety of semantics to be associated with the same data to accommodate different application domains.Additional salient features of MOODS include a notion of abstract function classes and dynamic binding of functions to data.

A shape similarity-based retrieval method for image databases that supports a variety of queries is proposed. It is flexible with respect to the choice of feature and definition of similarity and is implementable using existing multidimensional point access methods. A prototype system that handles the problems of distortion and occlusion is described. Experiments with one specific point access method (PAM) are presented.>

General zero-crossing-based discontinuity detectors in two dimensions, which include Marr-Hildreth (1980), residual, difference of Gaussians, and other detectors as special cases, are discussed. Mathematical justification for this class of detectors is presented. An optimal detector that maximizes the signal-to-noise ratio is derived. Preliminary experimental results for real images are reported.

A new approach to range image segmentation is presented. The proposed approach involves two phases in which the region and edge information detected using a set of orthogonal Zernike moment-based operators are combined to provide robust segmentation of range images. In the first phase, each range image point is characterized by the surface normal vector and the depth value at that point. A surface feature-based clustering of range image points yields its initial region-based segmentation. This initial segmentation phase often produces oversegmented images. In the second phase of the proposed technique, the oversegmented image is resegmented by appropriately merging adjacent regions using the edge information to produce final segmentation. One attractive characteristic of the proposed technique is that the same set of three moment-based operators is used to extract both surface and edge features. Thus only three convolution operations are needed at an image point to compute all the desired surface and edge features associated with that point. The performances of the proposed Zernike moment-based operators in surface and edge feature detection are theoretically analyzed.>

This analysis is a panel discussion. There are many problems in the field of image database management. The object-oriented paradigm has been and continues to be a great impetus to this work. The semantics of images is essentially what they contain, and unless there is an effective method to identify their contents and index them on that basis, the database will degenerate to a collection of patterns with no semantics. This is the most challenging issue facing multimedia information systems in general, and image databases in particular. Work on query by image content has barely begun to scratch the surface. A few key query primitives will become well-understood and widely supported. To allow users to browse and search through information domains using sophisticated querying techniques that include imprecise queries, user-directed query processing, and queries that use similarity measures in order to retrieve data, new data modeling approaches are required. Key problems that arise in providing query by image content are considered.>

Presents a new approach to detect step edges with subpixel accuracy. The proposed approach is based on a set of orthogonal complex moments of the image known as Zernike moments. An ideal 2-D step edge is modeled in terms of four parameters: the background gray level, the step size, the distance of the edge from the center of the mask, and the orientation of the edge. Discrete Zernike moments are used to obtain a total of three masks to compute all the edge parameters for subpixel detection. For pixel-level edge detection only two masks (one real and one complex) are required. The theoretical analysis of the influence of noise on the location and the orientation of an edge is presented. This analysis reveals that the accuracy of the proposed approach is virtually unaffected by the additive noise. Experimental results are presented to demonstrate the efficacy of the proposed technique.>

The performance of a Gabor odd filter-based edge detector is investigated using the measures proposed by Canny. Based on this performance analysis a design criterion for 1-D Gabor filter-based edge detector is derived. It is shown that this design criterion holds good for a 2-D Gabor filter-based edge detector as well. Experimental results are presented to demonstrate the significance of the proposed design criterion.>

The authors proposed a novel Zernike moment-based generalized step edge detection method which can be used for segmenting range and intensity images. A generalized step edge detector is developed to identify different kinds of edges in range images. These edge maps are thinned and linked to provide final segmentation. A generalized edge is modeled in terms of five parameters: orientation, two slopes, one step jump at the location of the edge, and the background gray level. Two complex and two real Zernike moment-based masks are required to determine all these parameters of the edge model. Theoretical noise analysis is performed to show that these operators are quite noise tolerant. Experimental results are included to demonstrate edge-based segmentation technique.>

Gabor filters have been applied in several image processing applications such as motion analysis, texture discrimination, and image coding, etc. The authors propose a computationally efficient scheme to compute Gabor filter responses at multiple resolutions and orientations. An architecture is proposed to compute the responses of these filters in 2-D domain by utilizing the symmetric, antisymmetric, and wavelet characteristics of Gabor filters.>

Computing optical flow from a given sequence of images is computationally a very expensive task. Spatio-temporal filtering technique is one of the approaches to this task. This approach requires convolution of 3-D input with several 3-D Gabor filters. An efficient technique to compute the responses of Gabor filters by utilizing the functional characteristics of the filters is proposed. The technique significantly reduces the time complexity of computing the spatio-temporal responses. The pyramid structure of Gabor filters is discussed, and an implementation to generate the pyramid of filter responses is described. A VLSI pipelined architecture which effectively utilizes the characteristics of Gabor filters is proposed.>

An efficient parallel architecture that exploits the parallelism and pipelining possible in the difference picture-based technique (IEEE Trans. on Pattern Analysis and Machi Intelligence, vol. PAMI-3, no.5, p.489-543, (1981); Computer, p.12-18, Aug. (1981)) is presented for dynamic scene analysis. Each processor is organized as a pipeline, and the processor architecture is simple enough that the motion detection and classification system can be implemented on a single VLSI chip. The proposed VLSI architecture and the design of the various components of the basic processor are described. VLSI chip implementation issues are discussed.>

An external index mechanism for generating hypotheses in a data-driven object recognition system has been designed, implemented, and tested. The index serves to improve the speed of recognizing objects in a scene. A secondary memory implementation of this approach is discussed. The philosophy behind the present conception of image databases is quite different from that of other researchers in that image interpretation is relied on as the backbone of this approach.>

The authors develop an indexing mechanism, which is part of an overall scheme called SMITH (shape matching utilizing indexed hypothesis generation and testing) for 2-D model-based object recognition. Their approach is based on a dynamic programming implementation of attributed string matching, is computationally efficient, and works effectively for both nonoccluded as well as occluded shapes. Another advantage of this technique is that models may be inerted or deleted with relatively little cost.>

The authors focus on collision detection for planning collision-free motion of two robot arms in a common workspace. A collision-free motion is obtained by detecting collisions along the straight-line trajectories of the robots using a sphere model for the wrists and then replanning the paths and/or trajectories of one or both of the robots to avoid collisions. A novel approach to collision detection is presented and a discussion on collision avoidance is given.>