`FOR THE DISTRICT OF MASSACHUSETTS
`
`Civil Action No. 1:19-MC-91401-NMG-
`JCB
`
`CANON,INC., CANON U.S.A., INC.
`AND AXIS COMM.AB,
`Plaintiffs,
`
`Vv.
`
`AVIGILON FORTRESS
`CORPORATION,
`Defendant.
`
`
`
`DECLARATION OF KATHERINE ZIMMERMAN
`
`I, Katherine Zimmerman,state and declare as follows:
`
`1.
`
`I am a Scholarly Communications and Licensing Librarian at the Massachusetts
`Institute of Technology (“MIT”) Libraries, 105 Broadway, Building NE36, Suite
`
`6101, Cambridge, Massachusetts 02142.
`
`2.
`
`Iam over 18 years of age and am competent to makethis Declaration. I makethis
`
`Declaration based on my own personal knowledge, based on my knowledge and
`
`review of the business records and practices of the MIT Libraries, based on
`
`conversations with other library staff, and based on the notes and records ofMarilyn
`
`McSweeneywhoprepared Declarations until her retirement in 2016.
`
`3.
`
`Ihave been employed at MIT since 2016.
`
`4. Through the actions described in paragraph 2, I have become knowledgeable about
`
`the MIT Libraries’ normal business practices with respect to how MITreceives,
`
`catalogs,
`
`indexes, shelves, and makes available to the public journals and
`
`publications.
`
`858406.v2
`
`Canon Ex. 1055 Page 1 of 45
`
`Canon Ex. 1055 Page 1 of 45
`
`
`
`5. Attached as Exhibit A to this Declaration is a true and accurate copyofthe catalog
`
`record from the MIT Libraries’ online catalog system (known as the Barton
`
`Catalog) for the publication series entitled ACM Transactions on Information
`
`Systems: a publication of the Association for Computing Machinery vols. 7 (1989)
`- 26 (2008) (“ACM Transactions on Information Systems”). This is a record that
`MIT maintainsin the ordinary course ofits regular activities.
`|
`
`6. Attached as Exhibit B to this Declaration is a true and accurate copy of the issue
`
`cover, first page, back cover, and full article text, for the article titled “Motion
`
`Recovery for Video Content Classification” by Nevenka Dimitrova and Forouzan
`
`Golshani published on pages 408-439 of Volume 13, No. 4 of the ACM
`
`Transactions on Information Systems, which was published in October 1995 (the
`
`“October 1995 Issue.”). The ACM Transactions on Information Systems is
`
`available in print format in vols: 7 (1989) - 26 (2008) from the MIT Libraries, and
`
`is a record that MIT maintains in the ordinary course ofits regular activities.
`
`7. The October 1995 Issue has an MIT Libraries date stamp of “NOV 13 1995,”
`
`indicating that the MIT Libraries received the issue on November13, 1995.
`
`8. After a serials issue receives a date stamp, it undergoes a process of being labeled
`
`and moved to a shelf of the MIT Libraries. Based on current MIT Libraries
`
`practice, this process typically takes one to two weeks. According to the MIT
`
`Libraries’ current normal business practice, the October 1995 Issue would have
`
`been displayed on a shelf of the MIT Libraries no later than November 27, 1995.
`
`858406.v2
`
`|
`
`Canon Ex. 1055 Page 2 of 45
`
`Canon Ex. 1055 Page 2 of 45
`
`
`
`9. Once a publication is on a shelf of the MIT Libraries it is available to be viewed
`
`within the MIT Libraries by any memberofthe public or requested viaInterlibrary
`
`Loan.
`
`10. To the best of my knowledge and that of current MITemployees, unless stated
`
`otherwise, the above statements are descriptions ofnormal businesspractices at the
`
`MITLibraries from at least the beginning of 1995 and through thepresent.
`
`I declare under penalty of perjury that the foregoing is true and correct. Executed on
`
`October 23, 2019, at Cambridge, Massachusetts.
`
`x
`
`KAxp—
`
`858406.v2
`
`Canon Ex. 1055 Page 3 of 45
`
`Canon Ex. 1055 Page 3 of 45
`
`
`
`Canon Ex. 1055 Page 4 of 45
`
`Canon Ex. 1055 Page 4 of 45
`
`
`
`
`
`EXHIBIT A
`EXHIBIT A
`
`Canon Ex. 1055 Page 5 of 45
`
`Canon Ex. 1055 Page 5 of 45
`
`
`
`MIT Libraries' catalog - Barton - Full Catalog - Full Record
`
`http://library.mit.edu/F/9RDNRF61C37HYS4TADPBBXPC1SYSD1L...
`
`Search Full Catalog:
` • Basic
` • Advanced
`
`Search only for:
` • Conferences
` • E-resources
`
` • Journals
` • MIT Theses
`
`• Reserves
`• more...
`
`• Your Account
`• Help with Your Account
`
`• Your Bookshelf
`• Previous Searches
`
`MIT Libraries
`
`Other Catalogs
`
`Help
`
`Full Record
`
`Permalink for this record: http://library.mit.edu/item/000395517
`
`Results List | Add to Bookshelf | Save/Email
`
`Choose
`format:
`
`Standard | Citation |
`
`MARC
`tags
`
`Record 2 out
`of 3
`
`Title ACM transactions on information systems : a publication of the Association for Computing
`Machinery.
`Continues ACM transactions on office information systems
`Online Access
` v.7:no.1 (1989:Jan.)-
`Library Holdings Library Storage Annex - Off Campus Collection | HF.A184
` v.7(1989)-v.26(2008)
`Shelf Access Find it in the library/Request item
`Shelf Location Library Storage Annex - Off Campus Collection | HF.A184
`
`Published New York, NY : The Association, c1989-
`Description v. : ill. ; 26 cm.
`Numbering Vol. 7, no. 1 (Jan. 1989)-
`Series ACM series on computing methodologies.
`Current Frequency Quarterly
`Format Serial (e.g. journals, book series, etc.)
`Note Title from cover.
`Other Format Also available via the World Wide Web.
`Subject Electronic data processing -- Periodicals.
`Information storage and retrieval systems -- Periodicals.
`Information retrieval -- Periodicals.
`Other Author Association for Computing Machinery.
`Title Abbreviation ACM trans. inf. sys.
`Other Title Transactions on information systems.
`Association for Computing Machinery transactions on information systems.
`ISSN 1046-8188
`CODEN ATISET
`Local System Number 000395517
`
`1 of 2
`
`10/10/2019, 12:45 PM
`
`Canon Ex. 1055 Page 6 of 45
`
`
`
`MIT Libraries' catalog - Barton - Full Catalog - Full Record
`
`http://library.mit.edu/F/9RDNRF61C37HYS4TADPBBXPC1SYSD1L...
`
`Basic Search of Full Catalog
`Search type:
`
`Search for:
`
`Barton Questions: Ask Us! | Contact Us
`Massachusetts Institute of Technology
`77 Massachusetts Avenue, Cambridge, MA 02139-4307 USA
`
`© 2003 Massachusetts Institute of Technology
`
`2 of 2
`
`10/10/2019, 12:45 PM
`
`Canon Ex. 1055 Page 7 of 45
`
`
`
`
`
`EXHIBIT B
`EXHIBIT B
`
`Canon Ex. 1055 Page 8 of 45
`
`Canon Ex. 1055 Page 8 of 45
`
`
`
`——|
`
`——7
`
`0 0303
`
`3 908
`
`—To
`
`—vr)
`
`——$)
`
`———$0
`
`Pea
`
`Habalsy
`ibis
`TAT
`HisLt
`
`Canon Ex. 1055 Page 9 of 45
`
`
`
`
`
`|
`
`acm Series on
`Computing
`Methodologies
`
`
`
`
`
`
`
`
` -ieee-stew
`
`nformation
`
`
`
`
`Special Issue on Video Information Retrieval
`———
`
`
`
`
`
`373 A Video Retrieval and Sequencing System
`by Tat-Seng Chua and Li-Qun Ruan
`
`
`Motion Recovery for Video Content Classification
`by Nevenka Dimitrova and Forouzan Golshani
`
`»#
`is
`440|Embedded Video in Hypermedia Documents: Supporting
`
`
`
`Integration and Adaptive Control
`by Dick C. A. Bulterman
`
`XMovie: Architecture and Implementation of a Distributed
`Movie System
`by Ralf Keller, Wolfgang Effelsberg, and Bernd Lamparter
`
` oe
`371
`Guest Editors’ Introduction
`by Scott Stevens and Thomas Little
`
`
`
`
`
`408
`
`
`
`471
`
`
`
`
`
`
`
`Canon Ex. 1055 Page 10 of 45
`
`
`
` or subscription and submissions information, see inside back cover.
`
`Department of Computer Science/Raom 150/CB 3175, Sitterson Hall/
`University of North Carolina, ChapelHill/ChapelHill, 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.com
`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/Schoolof Library and Information Studies/
`Berkeley, CA 94720 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
`CSM|UUniversity of Michigan/701 Tappan Street/Ann Arbor, MI 48109-1234
`USA/+1-313-747-4606/jso@csmil.umich.edu
`Dipartimento di Elettronica/Politecnico di Milano/Piazza Leonardo da Vinci
`32/20133 Milan, Italy/+39-2-23993520/paolini@ipmel2.elet.polimi.it
`Department of Computer Science/Cornell University/Ithaca, NY 14853 USA/
`+1-607-255-4 117/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
`
`Prasun Dewan
`
`Steven Feiner
`
`John Herring
`
`Michael N. Huhns
`
`Simon Kaplan
`
`
`
`RobKling
`
`Ray Larson
`
`John J. Leggett
`
`David D. Lewis
`;
`Judith Olson
`=
`Paolo Paolini
`
`Gerard Salton
`
`Peter Schauble
`
`Alan F. Smeaton
`
`Headquarters Quarterlies Staff
`Director of Publications
`Mark Mandelbaum
`Associate Director of Publications
`Nhora Cortes-Comerer
`Managing Editor, ACM Quarterlies
`Roma Simon
`Associate Managing Editor, ACM Quarterlies
`George Criscione
`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 changesto Trans-
`actions on Information Systems, ACM, 1515 Broadway, New York, NY 10036.
`Copyright © 1995 by the Association for Computing Machinery, Inc. (ACM). Permission to makedigital or hard copies
`of part or all of this work for personalor classroom use is granted withoutfee provided that copies are not made or
`distributed for profit or commercial advantage andthat copies bearthis notice andthe full citation onthefirst 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,orto redistribute to lists, requires prior specific permis-
`sion and/or a fee, Request permission to republish from: Publications Dept, ACM, Inc. Fax +1 (212) 869-0481 or
`email <permissions@acm.org>.
`anieieaanes that carry a code at the bottom ofthefirst or last page or screen display, coping
`wided
`that
`the per-copyfee indicated in the c
`i
`i
`Center,
`Rosewood Drive, Danvers, MA 01923,
`CanonEX!1055SPaver I Of 45
`F
`
`Canon Ex. 1055 Page 11 of 45
`
`
`
`
`
`
`
`Motion Recovery for Video Content
`Classification
`
`NEVENKA DIMITROVA and FOROUZAN GOLSHANI
`Arizona State University, Tempe
`
`information, video sequences must be classified based on the
`Like other types of digital
`semantics of their contents. A more-precise and completer extraction of semanticinformation 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 ofstill-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
`shapeorcolor, as well as their movements. By describing the movements that
`we derive from the process of motion analysis, we introduce a dual hierarchy consisting ofspatial
`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
`algorithmfor motion detection uses the motion compensation component of the MPEGvideo-en-
`coding scheme and then computes trajectories for objects of interest. The specification of a
`languagefor 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-
`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 videoanalysis, video databases, video retrieval
`
`
`1. INTRODUCTION
`Applications such as video on demand, automated surveillance systems, video
`databases, industrial monitoring, video editing, road traffic monitoring, ete.
`involve storage and processing of video data. Manyofthese 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 extensionsof 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 orall of this work for personal or classroom useis
`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,Ine. To copy otherwise, to republish, to post on
`servers, or to redistribute to lists, requires prior specific permission and/ora fee.
`© 1995 ACM 1046-8188/95/ 1000-0408 $03.50
`ACM
`Transactions on Information Systems, Vol. 13, No. 4, October 1995, Pages 408-439.
`
`Canon Ex. 1055 Page 12 of 45
`
`Canon Ex. 1055 Page 12 of 45
`
`
`
`.
`
`409
`
`Video Content Classification
`
`dealing with massive amounts ofdata. As such, classifi
`cation is an essential
`step for ensuringthe 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-
`port for the idea of classifying sequences based on the motion information
`ext racted 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 computervision can beclassified into two major
`categories based on the type of information recovered from an image se-
`quence: recognition through recovering structure from motion and recognition
`through motiondirectly. The first approach may be characterized as attempt-
`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-
`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 betweenconsecutive 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-
`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 encodingof 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-
`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 blocksof pixels and
`produces another block of 8 < 8 in the frequency domain nee poetiicien?
`are subsequently quantized and coded. The importantpoint is that most of
`the coefficients are near zero and after quantization will be unde
`zero. Run-length coding, which is an algorithm for recording the numberof
`consecutive symbols with the same value, can efficiently compress such oe
`object. The next step is coding. By using variable-length codes (an eeamiele :
`Huffman tables), smaller code words are assigned to objects occurring more
`frequently, thus further minimizingthesize.
`Our aim in the coding ofvideo signals is to reduce the temporal ae
`cies. This is based on the fact that, within a sequence et moh ae
`except for the moving objects, the background remains unchange : cat a
`reduce temporal redundancy a process known as motion compens
`s, Vol. 13, No. 4, October 1995.
`ACMTransactions on Information System
`
`Canon Ex. 1055 Page 13 of 45
`
`Canon Ex. 1055 Page 13 of 45
`
`
`
`
`
`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-
`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 = 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-
`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-
`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.
`Ourapproach to extracting object motion is based on the idea that during
`video encoding by the MPEGmethod, 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, intermediatelevel, we extract
`macroblock trajectories which are spatiotemporal representations of mac-
`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.
`frame is described by the
`Macroblock displacement
`in each individual
`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-
`spondence problem is mucheasierto 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-
`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.
`
`Canon Ex. 1055 Page 14 of 45
`
`eeSees
`
`
`
`Canon Ex. 1055 Page 14 of 45
`
`
`
`Video Content Classification
`
`:
`
`Forward prediction
`
`eeee
`2 00oogs
`"NiseCSA|ae
`
`Bidirectional prediction
`
`Fig.
`
`1.
`
`Forward andbidirectional prediction in MPEG.
`
`411
`
`Canon Ex. 1055 Page 15 of 45
`
`video-sequence), as the basis for the video information model. The basic
`retrieval operators, the OMV-languagespecification, 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 computervision 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 notonly 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, ielled
`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 -
`spatiotemporal surface flow and spatiotemporal flow curves. See
`surfaces are projections of contours over time. Thus, these surfaces are dir
`representations of object motion.
`t
`1995.
`ACMTransactions on Information Systems, Vol. 13, No. 4, October
`
`Canon Ex. 1055 Page 15 of 45
`
`
`
`
`
`
`Canon Ex. 1055 Page 16 of 45
`I
`
`412
`
`.
`
`N. Dimitrova and F. Golshani
`
`
`
`In the dynamic computervision 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-
`proach to interpretation of the movements of articulated bodies in image
`sequences is presented by Rohr [1994]. The humanbodyis represented by a
`three-dimensional model consisting of cylinders. This approach uses the
`modeling of the movement from medical motion studies. Kolleret al. [1993]
`discuss an approach to tracking vehicles in roadtraffic scenes. The motion of
`the vehicle contouris described using an affine motion model with a transla-
`tion and a changein 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 usuallyis first segmentedinto
`shots. Segmentation is an important step for detection ofcut points which can
`be used for further analysis. Each video shot can be represented by oneor
`more key frames. Features such as color, shape, and texture could be ex-
`tracted from the key frames. An approach for automatic video indexing and
`full video search is introduced by Nagasaka and Tanaka [1992]. This video-
`indexing method relies on automatic cut detection andselection offirst
`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-
`ences over a period of time. A model-driven approach to digital video segmen-
`tation is proposed by Hampapur etal. [1994]. The paperdeals with extracting
`features that correspond tocuts, spatial edits, and chromatic edits. The
`authors present an extensive formal treatment ofshot boundaryidentifica-
`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 needto 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 medianfilter 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].
`Swanberget al. [1993] introduced a method for identifying desired objects,
`shots, and episodesprior to insertion in video databases. During the insertion
`process, the data arefirst analyzed with image-processing routines to identify
`ACM Transactions on Information Systems, Vol. 13, No. 4, October 1995.
`
`Canon Ex. 1055 Page 16 of 45
`
`
`
`Video Content Classification
`:
`413
`tetanusaenee rpcsng
`cameal. Ta.
`L
`ntly well defined structure can
`be -amraer on Heide! exploits the spatial structure of the video data
`without ana yzing 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 anapriori modelof 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 fixedset ofattributes. Their system requires
`manual
`feature extraction.
`It
`then fits these features into the schema.
`Querying involves theattributes of movie, scene, and actor. Once a movie is
`selected, a user can browse fromscene to scene beginning with the initial
`selection. Weiss [1994] 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 Streamsis 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 TimeLineis 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-
`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 numberofefforts 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 bythe work of Jain andhis students [Guptaetal.
`1991a; 1991b], Grosky [Grosky and Mehrotra 1989], and the research in
`image databases. Several
`lines of research such as those in Little et al.
`[1993], Swanbergetal. [1993], Zhangetal. [1994], and Weiss [1994] 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 madeof motion vectors. Each trajectory can be thought of as ann-tuple 2
`motion vectors. This trajectory representation is a basis for various ae
`trajectory representations. At the high-level motion analysis we ae eel
`activity to a set of trajectories of an object using domain knowledgerules.
`3.1 Low-Level Motion Extraction: Single Macroblock Tracing
`In MPEG,to encode a macroblock in a predicted or a bidirectional frame, we
`:
`h
`first need to find the best matching macroblock in the reference frames, then
`stober 1995.
`ACM Transactions on Information Systems, Vol. 13, No. 4, October
`
`Canon Ex. 1055 Page 17 of 45
`
`Canon Ex. 1055 Page 17 of 45
`
`
`
`
`
`
`find the amount of x and ytranslation (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 continueuntil the endofthe video sequenceif we
`do not impose a stopping criterion. We have a choice: to stop after a certain
`numberof frames, stop after the object (macroblock) has cometo 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 ofa single macroblock through one
`frame pattern for MPEG encoding is given in Figure 2. In Dimitrova| 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-
`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-frameis computed using
`only block coordinates and forward motion vectors.
`If during the tracing
`proceduretheinitial 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 oftheinitial macroblock, In therest of this article,
`we will use 7 to indicate the set ofall possible motion vectors.
`3.1.1 Trajectory Description. Various motion retrieval procedures have
`specific requirements for retrieving desired objects. These requirements de-
`pend on the characteristics of the retrieval which maybeflexible 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,