`r Machinery.
`ACM Transactions on
`Information Systems.
`
`
`
`acm I ransact1ons
`on Information
`Systems
`
`-
`
`ROIOI
`1515 Broadway
`New York, NY 10036
`Tel: (212) 869-7440
`ACM European Service Center
`Avenue Marcel Thiry 204
`1200 Brussels, Belgium
`Tel: 32 2 774 9602
`Fax: 32 2 774 9690
`Email: acm_europe@acm.org
`
`Editor-in-Chief
`Robert B. Allen
`
`Editor-in-Chief Designate
`W. Bruce Croft
`
`Associate Editors
`Alex Borgida
`
`Mic Bowman
`
`Shih-Fu Chang
`
`Prasun Dewan
`
`Steven Feiner
`
`John Herring
`
`Michael N. Huhns
`
`Simon Kaplan
`
`Rob Kling
`
`Ray Larson
`
`John J. Leggett
`
`David D. Lewis
`
`Judith Olson
`
`Paolo Paolini
`
`Gerard Salton
`
`Peter Schauble
`
`Alan F. Smeaton
`
`Bellcore/2A-367/445 South St./Morristown, NJ 07960-6438 USA/
`+ 1-201-829-4315/tois@bellcore.com
`
`University of Massachusetts/Computer Science Department/LGRC 243, Box
`34610/Amherst, MA 01003-4610 USA/+1-413-545-0463/croft@cs.umass.edu
`
`Rutgers University/Department of Computer Science/ CORE Building Room
`315/Piscataway, NJ 08854 USA/+ 1-908--932-4 7 44/
`borgida@topaz.rutgers.edu
`Transarc Corporation/The Gulf Tower/707 Grant Street/Pittsburgh, PA 15219
`USA/+ 1-412-338--6752/mic@transarc.eom
`Columbia University/Department of Electrical Engineering and Center for
`Telecommunications Research/New York, NY 10027 USA/+ 1- 212-316-9068/
`sfchang@ctr.columbia.edu
`Department of Computer Science/Room 150/CB 3175, Sitterson Hall/
`University of North Carolina, Chapel Hill/Chapel Hill, NC 27599-3175 USA/
`+ 1-919-962-1823/dewan@cs.unc.edu
`Department of Computer Science/Columbia University/500 W. 120 Street/
`New York, NY 10027 USA/+1-212-939-7083/feiner@cs.columbia.edu
`Oracle Corporation/Spatial Information Systems/3 Betheseda Metro Center/
`Suite 1400/20814 USA/+ 1-301-907-2723/jherring@us.oracle.corn
`Department of Electrical and Computer Engineering/University of South
`Carolina/Columbia, SC 29208 USA/+ 1-803-777-5921/huhns@ece.sc.edu
`Department of Computer Science/University of Queensland/Saint Lucia 4072/
`Australia/+61-733-653-168/s.kaplan@cs.uq.oz.au
`Department of Information and Computer Science/University of California at
`Irvine/Irvine, CA 92717 USA/+ 1-714-856-5955/kling@ics.uci.edu
`University of California at Berkeley/School of Library and Information Studies/
`Berkeley, CA 94 720 USA/+ 1-415-642-6046/larson@sherlock.berkeley.edu
`Department of Computer Science/Texas A&M University/College Station, TX
`77843-3112 USA/+ 1-409-845-0298/leggett@cs.tamu.edu
`AT&T Bell Laboratories/2C 408/600 Mountain Avenue/Murray Hill, NJ 07974
`USA/+ 1-908-582-3976/lewis@research.att.com
`CSMIUUniversity of Michigan/701 Tappan Street/Ann Arbor, Ml 48109-1234
`USA/+ 1-313-747-4606/jso@csmil.umich.edu
`Dipartimento di Elettronica/Politecnico di MHano/Piazza Leonardo da Vinci
`32/20133 Milan, ltaly/+39-2-23993520/paolini@ipmel2.elet.polimi.it
`Department of Computer Science/Cornell University/Ithaca, NY 14853 USA/
`+ 1-607-255-4117/gs@cs.cornell.edu
`Institute of Information Systems/Swiss Federal Institute of Technology (ETH)/
`ETH Zentrum, IFW/CH-8092, Zurich, Switzerland/+41-1-254-7222/
`schauble@inf.ethz.ch
`School of Computer Applications/Dublin City University/Glasnevin/Dublin 9,
`lreland/+353-1-7045262/asmeaton@compapp.dcu.ie
`
`Headquarters Quarterlies Staff
`Mark Mandelbaum
`Nhora Cortes-Comerer
`Roma Simon
`George Criscione
`
`Director of Publications
`Associate Director of Publications
`Managing Editor, ACM Quarterlies
`Associate Managing Editor, ACM Quarterlies
`
`ACM Transactions on Information Systems (ISSN 1046-8188) is published 4 times a year in January, April, July, and
`October by the Association for Computing Machinery, Inc., 1515 Broadway, New York, NY 10036. Second-class
`postage paid at New York, NY 10001, and at additional mailing offices. Postmaster: Send address changes to Trans(cid:173)
`actions on Information Systems, ACM, 1515 Broadway, New York, NY 10036.
`
`Copyright© 1995 by the Association for Computing Machinery, Inc. (ACM). Permission to make digital or hard copies
`of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or
`distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.
`Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is
`permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permis(cid:173)
`sion and/or a fee. Request permission to republish from: Publications Dept. ACM, Inc. Fax+ 1 (212) 869-0481 or
`email <permissions@acm.org>.
`For other copying of articles that carry a code at the bottom of the first or last page or screen display, copying is
`permitted provided that the per-copy fee indicated in the code is paid through the Copyright Clearance Center, 222
`Rosewood Drive, Danvers, MA 01923.
`
`For subscription and submissions information, see inside back cover.
`
`
`
`Motion Recovery for Video Content
`Classification
`
`NEVENKA DIMITROVA and FOROUZAN GOLSHANI
`Arizona State University, Tempe
`
`Like other types of digital information, video sequences must be classified based on the
`semantics of their contents. A more-precise and completer extraction of semantic information will
`result in a more-effective classification. The most-discernible difference between still images and
`moving pictures stems from movements and variations. Thus, to go from the realm of still-image
`repositories to video databases, we must be able to deal with motion. Particularly, we need the
`ability to classify objects appearing in a video sequence based on their characteristics and
`features such as shape or color, as well as their movements. By describing the movements that
`we derive from the process of motion analysis, we introduce a dual hierarchy consisting of spatial
`and temporal parts for video sequence representation. This gives us the flexibility to examine
`arbitrary sequences of frames at various levels of abstraction and to retrieve the associated
`temporal information (say, object trajectories) in addition to the spatial representation. Our
`algorithm for motion detection uses the motion compensation component of the MPEG video-en(cid:173)
`coding scheme and then computes trajectories for objects of interest. The specification of a
`language for retrieval of video based on the spatial as well as motion characteristics is presented.
`
`Categories and Subject Descriptors: H.3.3 [Information Storage and Retrieval]: Information
`Search and Retrieval; H.5.1 [Information Interfaces and Presentation]: Multimedia Infor(cid:173)
`mation Systems; 1.2.10 [Artificial Intelligence]: Vision and Scene Understanding- motion
`General Terms: Algorithms, Design
`Additional Key Words and Phrases: Content-based retrieval of video, motion recovery, MPEG
`compressed video analysis, video databases, video retrieval
`
`1. INTRODUCTION
`Applications such as video on demand, automated surveillance systems, video
`databases, industrial monitoring, video editing, road traffic monitoring, etc.
`involve storage and processing of video data. Many of these applications can
`benefit from retrieval of the video data based on their content. The problem is
`that, generally, any content retrieval model must have the capability of
`
`This article is a revised version with major extensions of an earlier paper which was presented at
`the ACM Multimedia '94 Conference.
`Authors' addresses: N. Dimitrova, Philips Laboratories, 345 Scarborough Road, Briarcliff Manor,
`NY 10562; email: nvd@philabs.philips.com; F. Golshani, Department of Computer Science and
`Engineering, Arizona State University, Tempe, AZ 85287-5406; email: golshani@asu.edu.
`Permission to make digital/hard copy of part or all of this work for personal or classroom use is
`granted without fee provided that copies are not made or distributed for profit or commercial
`advantage, the copyright notice, the title of the publication, and its date appear, and notice is
`given that copying is by permission of ACM, Inc. To copy otherwise, to republish, to post on
`servers, or to redistribute to lists, requires prior specific permission and/ or a fee.
`© 1995 ACM 1046-8188/ 95/ 1000-0408 $03.50
`
`ACM Transactions on Information Systems, Vol. 13 , No . 4 , October 1995 , Pages 408 - 439.
`
`
`
`Video Content Classification
`
`409
`
`dealing with massive amounts of data. As such, classification is an essential
`step for ensuring the effectiveness of these systems.
`Motion is an essential feature of video sequences. By analyzing motion of
`objects we can extract information that is unique to the video sequences. In
`human and computer vision research there are theories about extracting
`motion information independently of recognizing objects. This gives us sup(cid:173)
`port for the idea of classifying sequences based on the motion information
`extracted from video sequences regardless of the level of recognition of the
`objects. For example, using the motion information we can not only submit
`queries like "retrieve all the video sequences in which there is a moving
`pedestrian and a car" but also queries that involve the exact position and
`trajectories of the car and the pedestrian.
`Previous work in dynamic computer vision can be classified into two major
`categories based on the type of information recovered from an image se(cid:173)
`quence: recognition through recovering structure from motion and recognition
`through motion directly. The first approach may be characterized as attempt(cid:173)
`ing to recover either low-level structures or high-level structures. The low-level
`structure category is primarily concerned with recovering the structure of
`rigid objects, whereas the high-level structure category is concerned primar(cid:173)
`ily with recovering nonrigid objects from motion. Recovering objects from
`motion is divided into two subcategories: low-level motion recognition and
`high-level motion recognition. Low-level motion recognition is concerned with
`making the changes between consecutive video frames explicit (this is called
`optical flow [Horn and Schunck 1981]). High-level motion recognition is
`concerned with recovering coordinated sequences of events from the lower(cid:173)
`level motion descriptions.
`Compression is an inevitable process when dealing with large multimedia
`objects. Digital video is compressed by exploiting the inherent redundancies
`that are common in motion pictures. Compared to encoding of still images,
`video compression can result in huge reductions in size. In the compression of
`still images, we take advantage of spatial redundancies caused by the simi(cid:173)
`larity of adjacent pixels. To reduce this type of redundancy, some form of
`transform-based coding (e.g., Discrete Cosine Transform, known as DCT) is
`used. The objective is to transform the signal from one domain (in this case,
`spatial) to the frequency domain. DCT operates on 8 X 8 blocks of pixels and
`produces another block of 8 X 8 in the frequency domain whose coefficients
`are subsequently quantized and coded. The important point is that most of
`the coefficients are near zero and after quantization will be rounded off to
`zero. Run-length coding, which is an algorithm for recording the number of
`consecutive symbols with the same value, can efficiently compress such an
`object. The next step is coding. By using variable-length codes (an example is
`Huffman tables), smaller code words are assigned to objects occurring more
`frequently, thus further minimizing the size.
`Our aim in the coding of video signals is to reduce the temporal redundan(cid:173)
`cies. This is based on the fact that, within a sequence of related frames,
`except for the moving objects, the background remains unchanged. Thus to
`reduce temporal redundancy a process known as motion compensation is
`
`ACM Transactions on Information Systems, Vol. 13 , No. 4, October 1995.
`
`
`
`410
`
`N. Dimitrova and F. Golshani
`
`used. Motion compensation is based on both predictive and interpolative
`coding.
`MPEG (Moving Pictures Expert Group) is the most general of the numer(cid:173)
`ous techniques for video compression [Furht 1994; LeGall 1991; Mattison
`1994]. In fact, the phrase "video in a rainbow" is used for MPEG, implying
`that by adjusting the parameters, one can get a close approximation of any
`other proposal for video encoding. Motion compensation in MPEG consists of
`predicting the position of each 16 x 16 block of pixels (called a macroblock)
`through a sequence of predicted and interpolated frames. Thus we work with
`three types of frames-namely, those that are fully coded independently of
`others (called reference frames or I-frames), those that are constructed by
`prediction (called predicted frames or P-frames), and those that are con(cid:173)
`structed by bidirectional interpolation (known as B-frames). It begins by
`selecting a frame pattern which dictates the frequency of I-frames and the
`intermixing of other frames. For example, the frame pattern IBBPBBI indi(cid:173)
`cates (1) that every seventh frame is an I-frame, (2) that there is one
`predicted frame in the sequence, and (3) that there are two B-frames between
`each pair of reference and/ or predicted frames. Figure 1 illustrates this
`pattern.
`Our approach to extracting object motion is based on the idea that during
`video encoding by the MPEG method, a great deal of information is extracted
`from the motion vectors. Part of the low-level motion analysis is already
`performed by the video encoder. The encoder extracts the motion vectors for
`the encoding of the blocks in the predicted and bidirectional frames. A
`macroblock can be viewed as a coarse-grained representation of the optical
`flow. The difference is that the optical flow represents the displacement of
`individual pixels while the macroblock flow represents the displacement of
`macroblocks between two frames. At the next, intermediate level, we extract
`macroblock trajectories which are spatiotemporal representations of mac(cid:173)
`roblock motion. These macroblock trajectories are further used for object
`motion recovery. At the highest level, we associate the event descriptions to
`object/motion representations.
`Macroblock displacement in each individual frame is described by the
`motion vectors which form a coarse optical-flow field. We assume that our
`tracing algorithm is fixed on a moving set of macroblocks and that the
`correspondence problem is elevated to the level of macroblocks instead of
`individual points. The advantage of this elevation is that even if we lose
`individual points (due to turning, occlusion, etc.) we are still able to trace the
`object through the displacement of a macroblock. In other words, the corre(cid:173)
`spondence problem is much easier to solve and less ambiguous. Occlusion and
`tracing of objects which are continuously changing are the subject of our
`current investigations.
`In Section 2 of this article we survey some of the research projects related
`to our work. In Section 3 we present the object motion analysis starting from
`the low-level analysis through the high-level analysis. We discuss the impor(cid:173)
`tance of motion analysis and its relevance to our model which is presented in
`Section 3.4. Section 4 introduces the basic OMV structures (object, motion,
`
`ACM Transactions on Information Systems, Vol. 13, No. 4, October 1995.
`
`
`
`Video Content Classification
`
`411
`
`Forward prediction
`
`Bidirectional prediction
`
`Fig. 1. Forward and bidirectional prediction in MPEG.
`
`video-sequence), as the basis for the video information model. The basic
`retrieval operators, the OMV-language specification, and some examples are
`given. Empirical results are outlined in Section 5, and Section 6 presents
`some concluding remarks.
`
`2. RELATED WORK
`
`The research presented in this article builds on the existing results in two
`areas: dynamic computer vision and digital video modeling.
`A current trend in computational vision is influenced by the idea that
`motion analysis does not depend on complex-object descriptions. Our work
`follows this trend and is based on the recent publications that are in
`agreement with this idea in computational vision. The idea of object/event
`recognition regardless of the existence of object representations can be traced
`back to the early 70's when Johansson [1976) introduced his experiments
`with moving-light displays. The idea was to attach lights to the joints of a
`human subject dressed in dark-colored clothing and observe the motion of
`lights against a dark background. The audience not only could recognize the
`object (human being) but could also describe the motion and the events
`taking place. Goddard [ 1992) investigated the high-level representations and
`computational processes required for the recognition of human motion based
`on moving-light displays. The idea is that recognition of any motion involves
`indexing into stored models of the movement. These stored models, called
`scenarios, are represented based on coordinated sequences of discrete motion
`events. The structures and the algorithms are articulated in the language of
`structured connectionist models. Allmen [ 1991] introduced a computational
`framework for intermediate-level and high-level motion analysis based on
`spatiotemporal surface flow and spatiotemporal flow curves. Spatiotemporal
`surfaces are projections of contours over time. Thus, these surfaces are direct
`representations of object motion.
`
`ACM Transactions on Information Systems, Vol. 13, No. 4, October 1995.
`
`
`
`412
`
`N. Dimitrova and F. Golshani
`
`In the dynamic computer vision literature there are general models for
`object motion estimation and representation, as well as domain-restricted
`models. A general architecture for the analysis of moving objects is proposed
`by Kubota et al. [ 1993]. The process of motion analysis is divided into three
`stages: moving-object candidate detection, object tracking, and final motion
`analysis. The experiments are conducted using human motion. Another ap(cid:173)
`proach to interpretation of the movements of articulated bodies in image
`sequences is presented by Rohr ( 1994]. The human body is represented by a
`three-dimensional model consisting of cylinders. This approach uses the
`modeling of the movement from medical motion studies. Koller et al. [1993]
`discuss an approach to tracking vehicles in road traffic scenes. The motion of
`the vehicle contour is described using an affine motion model with a transla(cid:173)
`tion and a change in scale. A vehicle contour is represented by closed cubic
`splines. We make use of the research results in all these domain-specific
`motion analysis projects. Our model combines the general area of motion
`analysis with individual frame (image) analysis.
`In case of video modeling, the video footage usually is first segmented into
`shots. Segmentation is an important step for detection of cut points which can
`be used for further analysis. Each video shot can be represented by one or
`more key frames. Features such as color, shape, and texture could be ex(cid:173)
`tracted from the key frames. An approach for automatic video indexing and
`full video search is introduced by Nagasaka and Tanaka [1992]. This video(cid:173)
`indexing method relies on automatic cut detection and selection of first
`frames within a shot for content representation. Otsuji and Tonomura [ 1993]
`propose a video cut detection method. Their projection detection filter is
`based on finding the biggest difference in consecutive-frame histogram differ(cid:173)
`ences over a period of time. A model-driven approach to digital video segmen(cid:173)
`tation is proposed by Hampapur et al. [1994). The paper deals with extracting
`features that correspond to cuts, spatial edits, and chromatic edits. The
`authors present an extensive formal treatment of shot boundary identifica(cid:173)
`tion based on models of video edit effects. In our work, we rely on these
`methods for the initial stages of video processing, since we need to identify
`shot boundaries to be able to extract meaningful information within a shot.
`One representation scheme of segmented video footage uses key frames
`[Arman et al. 1994]. The video segments can also be processed for extraction
`of synthetic images, or layered representational images, to represent closely
`the meaning of the segments. A methodology for extracting a representative
`image, salient video stills, from a sequence of images is introduced by
`Teodosio and Bender [1993]. The method involves determining the optical
`flow between successive frames, applying affine transformations calculated
`from the flow-warping transforms, such as rotation, translation, etc., and
`applying a weighted median filter to the high-resolution image data resulting
`in the final image. A similar method for synthesizing panoramic overviews
`from a sequence of frames is implemented by Teodosio and Mills (1993].
`Swanberg et al. ( 1993] introduced a method for identifying desired objects,
`shots, and episodes prior to insertion in video databases. During the insertion
`process, the data are first analyzed with image-processing routines to identify
`ACM Transactions on Information Systems, Vol. 13 , No . 4 , October 1995.
`
`
`
`Video Content Classification
`
`413
`
`the key features of the data. In this model, episodes are represented using
`finite automata. Only video clips with inherently well defined structure can
`be represented. The model exploits the spatial structure of the video data
`without analyzing object motion. Zhang et al. [ 1994] presented an evaluation
`and a study of knowledge-guided parsing algorithms. The method has been
`implemented for parsing of television news, since video content parsing is
`possible when one has an a priori model of a video's structure.
`Another system, implemented by Little et al. [1993], supports content-based
`retrieval and playback. They define a specific schema composed of movie,
`scene, and actor relations with a fixed set of attributes. Their system requires
`manual feature extraction. It then fits these features into the schema.
`Querying involves the attributes of movie, scene, and actor. Once a movie is
`selected, a user can browse from scene to scene beginning with the initial
`selection. Weiss [1994J presented an algebraic approach to content-based
`access to video. Video presentations are composed of video segments using a
`video algebra. The algebra contains methods for temporally and spatially
`combining video segments, as well as methods for navigation and querying.
`Media Streams is a visual language that enables users to create multilayered
`iconic annotations of video content [Davis 1993]. The objects denoted by icons
`are organized into hierarchies. The icons are used to annotate the video
`streams in a Media Time Line. The Media Time Line is the core browser and
`viewer of Media Streams. It enables users to visualize video at multiple time
`scales simultaneously, in order to read and write multilayered, iconic annota(cid:173)
`tions, and it provides one consistent interface for annotation, browsing,
`query, and editing of video and audio data.
`The work presented here follows from a number of efforts listed above.
`Specifically, we use low- and intermediate-level motion analysis methods
`similar to those offered by Allmen [ 1991] and others. Our object recognition
`ideas have been influenced by the work of Jain and his students [ Gupta et al.
`1991a; 1991bJ, Grosky [Grosky and Mehrotra 19891, and the research in
`image databases. Several lines of research such as those in Little et al.
`[19931, Swanberg et al. [1993], Zhang et al. [19941, and Weiss [1994J provided
`many useful ideas for the modeling aspects of our investigations. An early
`report of our work was presented in Dimitrova and Golshani [1994].
`
`3. MOTION RECOVERY IN DIGITAL VIDEO
`In this section we describe in detail each level of the motion analysis pipeline.
`At the low-level motion analysis we start with a domain of motion vectors.
`During intermediate-level motion analysis we extract motion trajectories that
`are made of motion vectors. Each trajectory can be thought of as an n-tuple of
`motion vectors. This trajectory representation is a basis for various other
`trajectory representations. At the high-level motion analysis we associate an
`activity to a set of trajectories of an object using domain knowledge rules.
`
`3.1 Low-Level Motion Extraction: Single Macroblock Tracing
`In MPEG, to encode a macroblock in a predicted or a bidirectional frame, we
`first need to find the best matching macroblock in the reference frames, then
`
`ACM Transactions on Information Systems, Vol. 13, No. 4, October 1995.
`
`
`
`414
`
`N. Dimitrova and F. Golshani
`
`find the amount of x and y translation (i.e., the motion vector), and finally
`calculate the error component [Patel et al. 1993]. The motion vector is
`obtained by minimizing a cost function that measures the mismatch between
`a block and each predictor candidate. Each bidirectional and predicted frame
`is an abundant source of motion information. In fact, each of these frames
`might be considered a crude interpolation of the optical flow. Thus, the
`extraction of the motion vectors of a single macroblock through a sequence of
`frames is similar to low-level motion analysis.
`Tracing a macroblock can continue until the end of the video sequence if we
`do not impose a stopping criterion. We have a choice: to stop after a certain
`number of frames, stop after the object (macroblock) has come to rest, stop if
`the block comes to a certain position in the frame, stop if the macroblock gets
`out of the scene, or stop if the macroblock is occluded.
`The algorithm for tracing the motion of a single macroblock through one
`frame pattern for MPEG encoding is given in Figure 2. In Dimitrov a [ 1995],
`we describe object motion tracing for video databases in more detail. The
`algorithm takes the forward and backward motion vectors that belong to a
`particular macroblock and computes the macroblock's trajectory. The algo(cid:173)
`rithm computes the macroblock's position in a B-frame by averaging the
`positions obtained from: (1) the previous block coordinates and forward
`motion vectors and (2) next (predicted) block coordinates and the backward
`motion vector. The position of a macroblock in a P-frame is computed using
`only block coordinates and forward motion vectors. If during the tracing
`procedure the initial macroblock moves completes out of its position, then we
`have to extract motion vectors for the new macroblock position, which implies
`that we are continuing by tracing the macroblock whose position coincides
`with the (x, y) coordinates of the initial macroblock. In the rest of this article,
`we will use T to indicate the set of all possible motion vectors.
`
`3.1.1 Trajectory Description. Various motion retrieval procedures have
`specific requirements for retrieving desired objects. These requirements de(cid:173)
`pend on the characteristics of the retrieval which may be flexible to strict.
`The choice of trajectory representation may dictate the manner in which
`retrieval is conducted. Given a set of motion vectors for a macroblock, a
`number of mechanisms exist for trajectory representation. Below we present
`a sample list:
`
`(1) Point Representation: A trajectory in this case is a set of points repre(cid:173)
`sented by the absolute or relative frame coordinates of the position of the
`object, say
`
`where (xi, y) is derived by projecting (x, y, i) onto the image plane.
`(x, y, i) denotes the position of an object, i.e., (x, y), at time instant i.
`(2) Curve Representation: A parametric B-spline curve P(u) can be computed
`that passes through each of the trajectory points (xi, y) (see Farin [1990]
`for a detailed discussion). The first step involves generating a parameteri-
`
`ACM Transactions on Information Systems, Vol. 13 , No . 4, October 1995.
`
`
`
`Video Content Classification
`
`415
`
`Given: trues F = Fi i • 0, . .. ,n;
`motion vectors V • (fmx(i),fmy(i)),(bmx(i),bmy(i)) i= 1,n
`initial block coordinates bx, by
`Initialize R == 0,
`for i=l, ... , n
`if F(i) # I then
`if F(i) == P then
`if previous Type == I
`ex = bx - fmx(i)/2;
`ey = by - fmy(i)/2;
`nextbloekx = ex; nextblocky = cy;
`if previousType == P
`givenx = futurex;
`giveny = futurey;
`futurex = futurex - fmx(i)/2;
`futurey = futurey - fmy(i)/2;
`if F(i) == B then
`cx=((givenx-fmx(i)/2)+(futurex-bmx(i)/2))/2;
`cy=((giveny-fmy(i)/2)+(futurey-bmy{i)/2))/2;
`if block(bx,by) n block(cx,cy) == 0 then
`extract(mx(i),my(i)) for (cx,cy)
`R = Ru {(mx(i),my(i))}
`if F(i) is the last in a group of B ftames before a P frame
`ex = futurex;
`cy = futurey;
`if block(bx,by) n block(cx,cy) == 0 then
`extract(mx(i),my(i)) for (cx,cy)
`R = R U {(mx(i),my(i))}
`if F(i) == I then
`(bx,by) - bestMateh(bx,by) in I
`if stopping criteria == true, then
`return R;
`endfor
`
`Fig. 2. Algorithm for tracing the motion of a macroblock.
`
`zation or knot sequence u 1 s u 2 s · ·· s un. A commonly used approach
`employs cumulative chord lengths defined by the points ( xi, y). The next
`step involves setting up and solving a tridiagonal linear system of equa(cid:173)
`tions whose unknowns are the control points di of the B-splines N/u).
`The linear system depends on the xi, Yi, and ui values. This linear
`system can be efficiently solved in &'(n) time using standard techniques
`for tridiagonal matrices. The B-spline curve has the form:
`P(u) = I: d i ~(u),
`
`and it satisfies the following:
`(a) P(u) = (x i, y);
`ACM Transactions on Information System s , Vol. 13, No. 4, October 1995.
`
`
`
`416
`
`N. Dimitrova and F. Golshani
`
`(b) P(u) is a piecewise cubic polynomial, i.e., for ui ~ u ~ ui + 1 , P(u) is a
`polynomial of degree less or equal to three; and
`(c) the first and the second derivatives of P(u) are continuous.
`
`(3) Chain Code Representation: We develop a piecewise linear approximation
`to the trajectory using a set of orientation primitives. Given a set of
`discrete trajectory orientation primitives, we use a zig-zag line represen(cid:173)
`tation of the trajectory to generate the code. Another way of viewing this
`approach is derived from a neighborhood matrix with each neighbor coded
`to correspond to the primitives in the figure [Schalkoff 1989].
`(4) Differential Chain Code Representation: Each segment is coded relative to
`the next line segment using the direction (left or right) and the length.
`For example, we can have a code for: right shorter-1, right equal-2, right
`longer-3, left shorter-4, left equal-5, left longer-6 [Schalkoff 1989]. This
`scheme is useful for approximate matching of object trajectories. It is a
`rotation-, scaling-, and translation-invariant scheme.
`
`Figure 3 illustrates these methods used for the representation of an
`arbitrary movement. Figure 3(a) is an exact coordinate representation; 3(b) is
`a B-spline curve representation. Figure 3(c) represents the chain-coding
`process, and 3(d) shows the differential chain code representation of the
`trajectory.
`Note that in the coordinate representation and B-spline and chain code
`representation schemes we have a way of representing zero motion, i.e., when
`the motion vector is a null vector. If the macroblock does not move over a
`certain number of frames, the point will be repeated. In the B-spline repre(cid:173)
`sentation, the knot (i.e., the control point) will have a multiplicity greater
`than one. In the chain code representation, the zero motion is represented by
`the code "O." So, in all these representations the trajectory is not only a
`spatial representation of the object's motion (the path) but also a temporal
`characterization of the motion. By keeping track of the zero motion we are
`able to describe stationary objects as well.
`The diversity of the trajectory representations makes the querying process
`more flexible. The actual method of representation does not have a significant
`impact on the querying process as long as modeling, representation, and
`querying are all done in the same fashion.
`
`3.1.2 Trajectory-Matching Functions. Applications such as automated
`surveillance may require retrieval of either video sequences or objects con(cid:173)
`tained in these sequences based on the object trajectories. For example,
`queries of the type "retrieve objects that have a motion trajectory whose point
`of origination is the main gallery door and terminate at the Juan Miro's
`picture on the opposite wall" may help in the identificati