`Courtney
`
`54 MOTION BASED EVENT DETECTION
`SYSTEMAND METHOD
`
`75 Inventor: Jonathan D. Courtney, Dallas, Tex.
`73 Assignee: Texas Instruments Incorporated,
`Dallas, TeX.
`
`21 Appl. No.: 08/795,432
`22 Filed:
`Feb. 5, 1997
`Related U.S. Application Data
`60 Provisional application No. 60/011,106, Feb. 5, 1996.
`(51) Int. Cl. ................................................. H04N 7/18
`52 U.S. C. ...
`348/143; 348/135; 348/155
`58 Field of Search ..................................... 348/135, 142,
`348/152, 154, 155, 143, 171, 172; 382/103,
`107, 236
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,243,418 9/1993 Kuno et al. ............................. 358/108
`5,428,774 6/1995 Takahashi et al.
`... 395/600
`5,550.965 8/1996 Gabbe et al. ...
`... 395/154
`5,666,157 9/1997 Aviv .............
`... 348/152
`5,721,692 2/1998 Nagaya et al. ...
`... 364/516
`5,734.737 3/1998 Chang et al. ........................... 382/107
`FOREIGN PATENT DOCUMENTS
`O 318 039 11/1988 Japan.
`OTHER PUBLICATIONS
`Lee, S., et al., “Video Indexing-An Approach Based on
`Moving Object and Track,” in Wayne Niblack, editor, Stor
`age and Retrieval for Image and Video Databases, Proc.
`SPIE 1908, 25-36 (1993).
`
`USOO596.9755A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,969,755
`Oct. 19, 1999
`
`Ioka, M, et al., “A Method for Retrieving Sequences of
`Images on the Basis of Motion Analysis,” in Image Storage
`and Retrieval Systems, Proc. SPIE 1662, 35-46 (1992).
`Day Y F, et al., “Object-Oriented Conceptual Modeling of
`Video Data”, Supplied by Applicant, 402-408, Mar. 6, 1995.
`Abe S, et al., “Scene Retrieval Method using Temporal
`Condition Changes', Supplied by Applicant, whole docu
`ment, Jan. 1, 1993.
`Hirotada Ueda, et al., “Automatic Structure Visualization for
`Video Editing”, Supplied by Applicant, whole document,
`Apr. 24, 1993.
`Orkisz, M., “Moving Objects Locaation in Complex Scenes
`Filmed by a Fixed Camera', Supplied by Applicant, 325,
`327–328, Jan. 1, 1992.
`Primary Examiner Tommy P. Chin
`ASSistant Examiner John Voisinet
`Attorney, Agent, or Firm-Robert L. Troike; Richard L.
`Donaldson
`ABSTRACT
`57
`A method to provide automatic content-based Video index
`ing from object motion is described. Moving objects in
`video from a Surveillance camera 11 detected in the video
`Sequence using motion Segmentation methods by motion
`Segmentor 21. Objects are tracked through Segmented data
`in an object tracker 22. A Symbolic representation of the
`Video is generated in the form of an annotated graphics
`describing the objects and their movement. A motion ana
`lyZer 23 analyzes results of object tracking and annotates the
`graph motion with indices describing several events. The
`graph is then indexed using a rule based classification
`Scheme to identify events of interest Such as appearance/
`disappearance, deposit/removal, entrance/exit, and motion/
`rest of objects. Clips of the video identified by spatio
`temporal, event, and object-based queries are recalled to
`view the desired video.
`22 Claims, 11 Drawing Sheets
`
`21
`
`
`
`22
`
`23
`
`24
`
`25
`
`
`
`MOTION
`ANALYZER
`
`RECORDERCOMPRESSOR
`
`
`
`TEMPORARY 10
`STORAGE
`
`------------
`
`27
`
`
`
`QUERY
`ENGINE
`
`DATABASE 15
`
`
`
`
`
`
`
`
`
`20
`
`
`
`S
`
`MONITOR
`
`A
`
`Canon Ex. 1021 Page 1 of 21
`
`
`
`U.S. Patent
`
`Oct. 19, 1999
`
`Sheet 1 of 11
`
`5,969,755
`
`
`
`11
`
`13
`
`VISION
`SUBSYSTEM
`
`15
`
`17
`
`19
`
`USER
`DATABASE INEc
`10
`
`MONITOR
`
`Fig. 1
`22
`
`f f
`CCAMER DiGIZATION
`
`
`
`21
`
`
`
`23
`
`
`
`MOTION
`SEGMENTOR
`
`MOTION
`OBJECT
`TRACKER ANALYZER
`
`25
`24
`RECORDERCOMPRESSOR
`
`15
`
`10
`TEMPORARY 10
`20STRAGE
`
`
`
`28
`GRAPHICAL
`USER INTERFACE
`
`30
`
`
`
`
`
`
`
`
`
`REFERENCE
`IMAGE
`
`101
`
`100
`
`29
`
`19 Fig. 5
`
`h
`
`k
`
`CONNECTED
`THRESHOLDING MORPSICAL COMPONENTS
`ANALYSIS
`
`
`
`
`
`Fig. 6
`
`103
`
`EVENT
`FOUND?
`
`105
`
`
`
`WATCHPOINTS
`Fig. 27
`
`Canon Ex. 1021 Page 2 of 21
`
`
`
`U.S. Patent
`
`Oct. 19, 1999
`
`Sheet 2 of 11
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Canon Ex. 1021 Page 3 of 21
`
`
`
`U.S. Patent
`
`Oct. 19, 1999
`
`Sheet 3 of 11
`
`5,969,755
`
`
`
`
`
`
`
`fik:33i:
`
`xition (3:38
`
`{:
`
`(i.
`
`{e
`
`:
`
`:
`
`Canon Ex. 1021 Page 4 of 21
`
`
`
`U.S. Patent
`
`
`
`Oct. 19, 1999
`
`Sheet 4 of 11
`
`5,969,755
`
`Canon Ex. 1021 Page 5 of 21
`
`
`
`US. Patent
`
`Oct. 19,1999
`
`Sheet 5 0f 11
`
`5,969,755
`
`
`
`F0
`
`F1
`
`F2
`
`F3
`
`F4
`
`F5
`
`F6
`
`F7
`
`F8
`
`F9
`
`F10
`
`F11
`
`F12
`
`F13 F14
`
`Canon Ex. 1021 Page 6 of 21
`
`Canon Ex. 1021 Page 6 of 21
`
`
`
`U.S. Patent
`
`Oct. 19, 1999
`
`Sheet 6 of 11
`
`5,969,755
`
`
`
`
`
`Fig. 13
`
`Fig. 14
`
`FO
`
`F1
`
`F2
`
`F3
`
`F4
`
`F5
`
`F6
`
`F10 F11 F12 F13 F14
`
`F7
`F8
`F9
`Fig. 15
`
`Canon Ex. 1021 Page 7 of 21
`
`
`
`U.S. Patent
`
`Oct. 19, 1999
`
`Sheet 7 of 11
`
`5,969,755
`
`ENTRANCE
`
`START
`
`EXIT
`
`APPEAR
`
`DISAPPEARANCE
`
`F9 F10/F1 F12i F13 F14
`F8
`F1 f F2 f F3 F4 F5 F6\, F7
`FO
`REMOVAL/REMOVER EXIT
`DEPOSITOR/DEPOSIT
`EXIT
`ENTRANCE
`Fig. 16
`
`
`
`
`
`FO
`
`F1
`
`F2
`
`F3
`
`F4
`
`F5
`
`F6
`
`F7
`
`F8
`
`F9
`
`F10 F11 F12 F13 F14
`
`FO
`
`F
`
`F2
`
`F3
`
`F4
`
`F5
`
`F6
`
`F7
`
`F8
`
`F9
`
`F10 F11 F12 F13 F14
`
`Canon Ex. 1021 Page 8 of 21
`
`
`
`US. Patent
`
`Oct. 19,1999
`
`Sheet 8 0f 11
`
`5,969,755
`
`F13 F14
`F12
`F11
`F10
`F9
`F8
`F7
`F6
`F5
`F4
`F3
`F2
`F1
`F0
`
`
`Fig. 79
`
`F14
`F10 F11F12 F13
`F9
`F8
`F7
`F6
`F5
`F4
`F3
`F2
`F1
`F0
`
`
`Fig. 20
`
`F0
`
`F1
`
`F2
`
`F3
`
`F4\\ F5
`EXIT
`
`
`F6
`
`F7
`
`F8
`
`F9
`
`F10 F11F12 F13
`
`F14
`
`Fig. 27
`
`Canon Ex. 1021 Page 9 of 21
`
`Canon Ex. 1021 Page 9 of 21
`
`
`
`U.S. Patent
`
`Oct. 19, 1999
`
`Sheet 9 of 11
`
`5,969,755
`
`
`
`Canon Ex. 1021 Page 10 of 21
`
`
`
`U.S. Patent
`
`Oct. 19, 1999
`
`Sheet 10 of 11
`
`5,969,755
`
`
`
`
`
`Fig. 25
`
`Canon Ex. 1021 Page 11 of 21
`
`
`
`U.S. Patent
`
`Oct. 19, 1999
`
`Sheet 11 of 11
`
`5,969,755
`
`
`
`(260
`
`Canon Ex. 1021 Page 12 of 21
`
`
`
`1
`MOTION BASED EVENT DETECTION
`SYSTEMAND METHOD
`
`5,969,755
`
`2
`Retrieving Sequences of Images on the Basis of Motion
`Analysis, in Image Storage and Retrieval Systems, Proc.
`SPIE 1662, 35-46 (1992), and S. Y. Lee and H. M. Kao,
`Video Indexing-an approach based on moving object and
`track, in Wayne Niblack, editor, Storage and Retrieval for
`Image and Video Databases, Proc. SPIE 1908, 25–36
`(1993).
`Using breakpoints found via Scene cut detection, other
`researchers have pursued hierarchical Segmentation to ana
`lyze the logical organization of Video Sequences. For more
`on this, see the following: G. Davenport, T. Smith, and N.
`Pincever, Cinematic Primitives for Multimedia, IEEE Com
`puter Graphics & Applications, 67-74 (1991); M. Shibata,
`A temporal Segmentation Method for Video Sequences, in
`PetroS Maragos, editor, Visual Communications and Image
`Processing, Proc SPIE 1818, 1194-1205 (1992); D.
`Swanberg, C-F. Shu, and R. Jain, Knowledge Guided Pars
`ing in Video Databases in Wayne Niblack, editor, Storage
`and Retrieval for Image and Video Databases, Proc. SPIE
`1908, 13–24 (1993). In the same way that text is organized
`into Sentences, paragraphs and chapters, the goal of these
`techniques is to determine a hierarchical grouping of Video
`Sub-Sequences. Combining this structural information with
`content abstractions of Segmented Sub-Sequences provides
`multimedia System users a top-down view of Video data. For
`more details see F. Arman, R. Depommier, A. Hsu, and M.
`Y. Chiu, Content-Based Browsing of Video Sequences, in
`Proceedings of ACM International Conference on
`Multimedia, (1994).
`Closed-circuit television (CCTV) systems provide secu
`rity perSonnel a wealth of information regarding activity in
`both indoor and outdoor domains. However, few tools exist
`that provide automated or assisted analysis of Video data;
`therefore, the information from most Security cameras is
`under-utilized.
`Security Systems typically proceSS Video camera output
`by either displaying the Video on monitors for Simultaneous
`Viewing by Security perSonnel and/or recording the data to
`time-lapse VCR machines for later playback. Serious limi
`tations exist in these approaches:
`Psycho-visual studies have shown that humans are limited
`in the amount of visual information they can proceSS in tasks
`like Video camera monitoring. After a time, Visual activity in
`the monitors can easily go unnoticed. Monitoring effective
`neSS is additionally taxed when output from multiple video
`cameras must be viewed.
`Time-lapse VCRs are limited in the amount of data that
`they can Store in terms of resolution, frames per Second, and
`length of recordings. Continuous use of Such devices
`requires frequent equipment maintenance and repair.
`In both cases, the Video information is unstructured and
`un-indexed. Without an efficient means to locate visual
`events of interest in the Video Stream, it is not cost-effective
`for Security perSonnel to monitor or record the output from
`all available video cameras.
`Video motion detectors are the most powerful of available
`tools to assist in Video monitoring. Such Systems detect
`Visual movement in a Video stream and can activate alarms
`or recording equipment when activity exceeds a pre-Set
`threshold. However, existing video motion detectors typi
`cally Sense only simple intensity changes in the Video data
`and cannot provide more intelligent feedback regarding the
`occurrence of complex object actions Such as inventory
`theft.
`
`65
`
`SUMMARY OF THE INVENTION
`In accordance with one embodiment of the present
`invention, a method is provided to perform Video indexing
`
`This application claims priority under 35 USC S119(e)
`(1) of provisional application No. 60/011,106, filed Feb. 5,
`1996. This application is related to co-pending application
`Ser. No. 08/795,434 (TI-22548) entitled, “Object Detection
`Method and System for Scene Change Analysis in TV and
`IR Data” of Jonathan Courtney, et al., filed Feb. 50, 1997.
`This application is incorporated herein by reference.
`TECHNICAL FIELD OF THE INVENTION
`This invention relates to motion event detection as used
`for example in Surveillance.
`BACKGROUND OF THE INVENTION
`Advances in multimedia technology, including commer
`cial prospects for Video-on-demand and digital library
`Systems, has generated recent interest in content-based video
`analysis. Video data offers users of multimedia Systems a
`wealth of information; however, it is not as readily manipu
`lated as other data Such as text. Raw Video data has no
`immediate “handles” by which the multimedia system user
`may analyze its contents. Annotating video data with Sym
`25
`bolic information describing its Semantic content facilitates
`analysis beyond Simple Serial playback.
`Video data poses unique problems for multimedia infor
`mation Systems that text does not. Textual data is a Symbolic
`abstraction of the spoken word that is usually generated and
`Structured by humans. Video, on the other hand, is a direct
`recording of visual information. In its raw and most common
`form, Video data is Subject to little human-imposed Structure,
`and thus has no immediate “handles” by which the multi
`media System user may analyze its contents.
`For example, consider an on-line movie Screenplay
`(textual data) and a digitized movie (video and audio data).
`If one were analyzing the Screenplay and interested in
`Searching for instances of the word “horse' in the text, many
`text Searching algorithms could be employed to locate every
`instance of this Symbol as desired. Such analysis is common
`in on-line text databases. If, however, one were interested in
`Searching for every Scene in the digitized movie where a
`horse appeared, the task is much more difficult. Unless a
`human performs Some Sort of pre-processing of the Video
`data, there are no Symbolic keys on which to Search. For a
`computer to assist in the Search, it must analyze the Semantic
`content of the video data itself. Without such capabilities,
`the information available to the multimedia System user is
`greatly reduced.
`Thus, much research in Video analysis focuses on Seman
`tic content-based Search and retrieval techniques. The term
`“video indexing” as used herein refers to the process of
`marking important frames or objects in the Video data for
`efficient playback. An indexed video Sequence allows a user
`not only to play the Sequence in the usual Serial fashion, but
`also to "jump” to points of interest while it playS. A common
`indexing Scheme is to employ Scene cut detection to deter
`mine breakpoints in the Video data. See H. Zang, A.
`Kankanhalli, and Stephen W. Smoliar, Automatic Partition
`ing of Full Motion Video, Multimedia Systems, 1, 10-28
`(1993). Indexing has also been performed based on camera
`(i.e., viewpoint) motion, see A. Akutsu, Y. Tonomura, H.
`Hashimoto, and Y. Ohba, Video Indexing Using Motion
`Vectors, in Petros Maragos, editor, Visual Communications
`and Image Processing SPIE 1818, 1552–1530 (1992), and
`object motion, see M. Ioka and M. Kurokawa, A Method for
`
`35
`
`15
`
`40
`
`45
`
`50
`
`55
`
`60
`
`Canon Ex. 1021 Page 13 of 21
`
`
`
`3
`from object motion. Moving objects are detected in a video
`Sequence using a motion Segmentor. Segmented Video
`objects are recorded and tracked through Successive frames.
`The path of the objects and intersection with paths of the
`other objects are determined to detect occurrence of events.
`An index mark is placed to identify these events of interest
`Such as appearance/disappearance, deposit/removal,
`entrance/exit, and motion/rest of objects.
`These and other features of the invention that will be
`apparent to those skilled in the art from the following
`detailed description of the invention, taken together with the
`accompanying drawings.
`DESCRIPTION OF THE DRAWINGS
`FIG. 1 is an Overview diagram of a System for automati
`cally indexing pre-recorded video in accordance with one
`embodiment of the present invention;
`FIG. 2 is a sequence of frames of video (test Sequence 1)
`with the frame numbers below each image;
`FIG. 3 illustrates points in the video sequence that satisfy
`the query “show all deposit events”;
`FIG. 4 illustrates the relation between video data, motion
`Segmentation and Video meta-information;
`FIG. 5 illustrates the Automatic Video Indexing system
`architecture;
`FIG. 6 illustrates the motion segmentor;
`FIG. 7 illustrates motion segmentation example where (a)
`is the reference image I, (b) Image I, (c) absolute differ
`ence D=I-I; (d) Threshold image T.; (e) result of
`morphological close operation, (f) result of connected com
`ponents analysis,
`FIG. 8 illustrates reference image from a TV camera
`modified to account for the exposed background region;
`FIG. 9 illustrates the output of the object tracking stage
`for a hypothetical Sequence of 1-D frames where vertical
`lines labeled “F” represent frame numbers n and where
`primary links are Solid lines and Secondary links are dashed;
`FIG. 10 illustrates an example motion graph for a
`Sequence of 1-D frames,
`FIG. 11 illustrates stems;
`FIG. 12 illustrates branches;
`FIG. 13 illustrates trails;
`FIG. 14 illustrates tracks;
`FIG. 15 illustrates traces;
`FIG. 16 illustrates indexing rules applied to FIG. 10;
`FIG. 17 illustrates a graphical depiction of the query
`Y=(C.T.V.R.E);
`FIG. 18 illustrateS processing of temporal constraints;
`FIG. 19 illustrates processing of object based constraints;
`FIG. 20 illustrateS processing of Spatial constraints;
`FIG. 21 illustrates processing of event-based constraints,
`FIG. 22 illustrates a picture of the “playback” portion of
`the GUI;
`FIG. 23 illustrates the query interface;
`FIG. 24 illustrates Video content analysis using advanced
`queries with Video clips a, b, c and d;
`FIG. 25 illustrates frames from test sequence 2;
`FIG. 26 illustrates frames from test sequence 3; and
`FIG. 27 illustrates video indexing in a real-time system.
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS OF THE PRESENT
`INVENTION
`FIG. 1 shows a high-level diagram of the Automatic
`Video Indexing (AVI) system 10 according to one embodi
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,969,755
`
`15
`
`25
`
`4
`ment of the present invention. In this view, a camera 11
`provides input to a vision Subsystem 13 including a pro
`grammed computer which processes the incoming video
`which has been digitized to populate a database Storage 15.
`The term camera as used herein may be a conventional
`television (TV) camera or infrared (IR) camera. A user may
`then analyze the Video information using an interface 17
`including a computer to the database 15 via Spatio-temporal,
`event-, and object-based queries. The user interface 17 playS
`Video Subsequences which Satisfy the queries to a monitor
`19.
`FIG. 2 shows frames from a video sequence with content
`Similar to that found in Security monitoring applications. In
`this sequence, a perSon enters the Scene, deposits a piece of
`paper, a briefcase, and a book, and then exits. He then
`re-enters the Scene, removes the briefcase, and exits again.
`The time duration of this example Sequence is about 1
`minute; however, the action could have been spread over a
`number of hours. By querying the AVI database 15, a user
`can jump to important events without playing the entire
`Sequence front-to-back. For example, if a user formed the
`query “show all deposit events in the Sequence', the AVI
`System 10 would respond with Sub-Sequences depicting the
`perSon depositing the paper, briefcase and book. FIG. 3
`shows the actual result given by the AVI System in response
`to this query where the System points to the placement of the
`paper, briefcase and book, and boxes highlight the objects
`contributing to the event.
`In processing the video data, the AVI vision subsystem 13
`employs motion Segmentation techniques to Segment fore
`ground objects from the Scene background in each frame.
`For motion Segmentation techniques see S. Yalamanchili, W.
`Martin, and J. Aggarwal, Extraction of Moving Object
`Descriptions via Differencing, Computer Graphics and
`Image Processing, 18, 188-201 (1982); R. Jain, Segmenta
`tion of Frame Sequences Obtained by a Moving Observer,
`IEEE Transactions on Pattern Analysis and Machine
`Intelligence, 6, 624–629 (1984); A. Shio and J. Sklansky,
`Segmentation of People in Motion, in IEEE Workshop On
`Visual Motion, 325–332 (1991); and D. Ballard and C.
`Brown, Computer Vision, Prentice-Hall, Englewood Cliffs,
`New Jersey (1982) to segment foreground objects from the
`Scene background in each frame. It then analyzes the Seg
`mented Video to create a symbolic representation of the
`foreground objects and their movement. This Symbolic
`record of video content is referred to as the video “meta
`information” (see FIG. 4). FIG. 4 shows the progression of
`the Video data frames, the corresponding motion Segmenta
`tion and the corresponding meta-information. This meta
`information is Stored in the database in the form of an
`annotated directed graph appropriate for later indexing and
`Search. The user interface 17 operates upon this information
`rather than the raw Video data to analyze Semantic content.
`The vision subsystem 13 records in the meta-information
`the size, shape, position, time-Stamp, and image of each
`object in every Video frame. It tracks each object through
`Successive Video frames, estimating the instantaneous Veloc
`ity at each frame and determining the path of the object and
`its intersection with the paths of other objects. It then
`classifies objects as moving or Stationary based upon Veloc
`ity measures on their path.
`Finally, the vision Subsystem 13 Scans through the meta
`information and places an index mark at each occurrence of
`eight events of interest: appearance/disappearance, deposit/
`removal, entrance/exit, and motion/rest of objects. This
`indexing is done using heuristics based on the motion of the
`objects recorded in the meta-information. For example, a
`
`Canon Ex. 1021 Page 14 of 21
`
`
`
`5,969,755
`
`S
`moving object that "spawns a Stationary object results in a
`“deposit” event. A moving object that intersects and then
`removes a Stationary object results in a "removal’ event.
`The system stores the output of the vision subsystem-the
`Video data, motion Segmentation, and meta-information-in
`the database 15 for retrieval through the user interface 17.
`The interface allows the user to retrieve a video Sequence of
`interest, play it forward or backward and Stop on individual
`frames. Furthermore, the user may specify queries on a
`Video Sequence based upon Spatial-temporal, event-based,
`and object-based parameters.
`For example, the user may select a region in the Scene and
`Specify the query “show me all objects that are removed
`from this region of the scene between 8am and 9 am.” In this
`case, the user interface Searches through the Video meta
`information for objects with timestamps between 8 am and
`9 am, then filters this set for objects within the specified
`region that are marked with “removal’ event tags. This
`results in a Set of objects Satisfying the user query. From this
`Set, it then assembles a Set of Video "clips' highlighting the
`query results. The user may Select a clip of interest and
`proceed with further Video analysis using playback or que
`ries as before.
`The following is a description of Some of the terms and
`notation used in the remainder of this application.
`A sequence S is an ordered set of N frames, denoted
`S={Fo, F, ..., F-1}, where F, is the frame number n in
`the Sequence.
`A clip is a 4-tuple C=(S,fs,l), where S is a sequence with
`N frames, and f, S, and l are frame numberS Such that
`0sfsssls N-1. Here, F, and F, are the first and last valid
`frames in the clip, and F is the current frame. Thus, a clip
`Specifies a Sub-Sequence with a State variable to indicate a
`"frame of interest'.
`A frame F is an image I annotated with a timestamp t.
`Thus, frame number n is denoted by the pair F=(I, t).
`An image I is an r by c array of pixels. The notation I (i,j)
`indicates the pixel at coordinates (row i, column j) in I,
`wherein i=0,....r-1 and j=0,..., c-1. For purposes of this
`discussion, a pixel is assumed to be an intensity value
`between 0 and 255.
`FIG. 5 shows the AVI system in detail. Note that the
`motion Segmentor 21, object tracker 22, motion analyzer 23,
`recorder 24, and compressor 25 comprise the vision Sub
`system 13 of FIG. 1. Likewise, the query engine, 27,
`graphical user interface 28, playback device 29 and decom
`pression modules 30 comprise the user interface 17. The
`Subsequent paragraphs describe each of these components in
`detail.
`The current implementation of the AVI system supports
`batch, rather than real-time, processing. Therefore, frames
`are digitized into a temporary Storage area 20 before further
`processing occurs. A real-time implementation would
`bypass the temporary Storage 20 and process the Video in a
`pipelined fashion.
`FIG. 6 shows the motion segmentor in more detail. For
`each frame F, in the Sequence, the motion Segmentor 21
`computes Segmented image C., as
`C=CCOmps(T.S),
`
`where T, is the binary image resulting from thresholding the
`absolute difference of images I, and I at h, Tk is the
`morphological close operation on T, with Structuring ele
`ment k, and the function ccompS() performs connected
`
`6
`components analysis resulting in a unique label for each
`connected region in image Tk. The image T, is defined as
`
`1 if D (i, j) > h
`Ti, (i,i) -
`0 otherwise
`
`for all pixels (i,j) in T, where D., is the difference image
`of I, and I Such that
`
`For noisy data (Such as from an infrared camera), the image
`D, may be Smoothed via a low-pass filter to create a more
`consistent difference image.
`Finally, the operation ak is defined as
`
`15
`
`where €D is the morphological dilation operator and 0 is the
`morphological erosion operator.
`FIG. 7 shows an example of this process. FIG. 7a is the
`reference image I, FIG. 7b is the image I, FIG. 7c is the
`absolute difference D=L-I, FIG. 7d is the thresholded
`image T, which highlights motion regions in the image;
`FIG. 7e is the result of the morophogical close operation,
`which joins together Small regions into Smoothly shaped
`objects; FIG. 7f is the result of connected components
`analysis, which assigns each detected object a unique label
`Such as regions 1-4. This result is C, the output of the
`motion Segmentor.
`Note that the technique uses a “reference image' for
`processing. This is nominally the first image from the
`Sequence, Io. For many applications, the assumption of an
`available reference image is not unreasonable, Video capture
`is simply initiated from a fixed-viewpoint camera when
`there is limited motion in the Scene. Following are Some
`reasons why this assumption may fail in other applications:
`1. Gradual lighting changes may cause the reference
`frame to grow “out of date' over long Video Sequences,
`particularly in outdoor Scenes. Here, more Sophisti
`cated techniques involving cumulative differences of
`Successive Video frames must be employed.
`2. The Viewpoint may change due to camera motion. In
`this case, camera motion compensation must be used to
`“Subtract the moving background from the Scene.
`3. A object may be present in the reference frame and
`move during the Sequence. This causes the motion
`Segmentation process to incorrectly detect the back
`ground region eXposed by the object as if it were a
`newly-appearing Stationary object in the Scene.
`A Straightforward Solution to problem 3 is to apply a test
`to non-moving regions detected by the motion Segmentation
`process to determine if a given region is the result of either
`(1) a stationary object present in the foreground or (2)
`background exposed by a foreground object present in the
`reference image.
`In the case of video data from a TV camera, this test is
`implemented based on the following observation: if the
`region detected by the Segmentation of image I, is due to the
`motion of an object present in the reference image (i.e., due
`to “exposed background”), a high probability exists that the
`boundary of the Segmented region will match intensity edges
`detected in Io. If the region is due to the presence of a object
`in the current image, a high probability exists that the region
`boundary will match intensity edges in I. The test is
`implemented by applying an edge detection operator (See D.
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Canon Ex. 1021 Page 15 of 21
`
`
`
`7
`Ballard and C. Brown, Computer Vision, Prentice-Hall,
`Englewood Cliffs, N.J., 1982) to the current and reference
`images and checking for coincident boundary pixels in the
`Segmented region of C.
`In the case of Video data from an IR camera, foreground
`objects may not have easily detectable edges due to heat
`diffusion and image blurring. In data from Some cameras,
`however, objects exhibit a contrasting halo due to opto
`mechanical image Sharpening. See A. Rosenfeld and A. Kak,
`Digital Picture Processing, 2ed., Volume 1, Academic Press,
`New York, N.Y., 1982. Thus, the test may be implemented
`by comparing the variance of pixel intensities within the
`region of interest in the two images. Since background
`regions tend to exhibit constant pixel intensities, the Vari
`ance will be highest for the image containing the foreground
`object.
`The object detection method for Scene change analysis in
`TV and IR data is described in above cited application of
`Courtney, et al. incorporated herein by reference and in
`Appendix A.
`If either test Supports the hypothesis that the region in
`question is due to exposed background, the reference image
`is modified by replacing the object with its exposed back
`ground region (see FIG. 8).
`No known motion Segmentation technique is perfect. The
`following are errors typical of many motion Segmentation
`techniques:
`1. True objects will disappear temporarily from the
`motion Segmentation record. This occurs when there is
`insufficient contrast between an object and an occluded
`background region, or if an object is partially occluded
`by a “background” structure (for instance, a tree or
`pillar present in the Scene).
`2. False objects will appear temporarily in the motion
`Segmentation record. This is caused by light fluctua
`tions or Shadows cast by moving objects.
`3. Separate objects will temporarily join together. This
`typically occurs when two or more objects are in close
`proximity or one object occludes another object.
`4. Single objects will Split into two regions and then
`rejoin. This occurs when a portion of an object has
`insufficient contrast with the background it occludes.
`Instead of applying incremental improvements to relieve
`the shortcomings of motion Segmentation, the AVI technique
`addresses these problems at a higher level where informa
`tion about the Semantic content of the Video data is more
`readily available. The object tracker and motion analyzer
`units described later employ object trajectory estimates and
`domain knowledge to compensate for motion Segmentation
`inaccuracies and thereby construct a more accurate record of
`the Video content.
`The motion Segmentor 21 output is processed by the
`object tracker 22. Given a Segmented image C, with P
`uniquely-labeled regions corresponding to foreground
`objects in the Video, the System generates a Set of features to
`represent each region. This set of features is named a
`“V-object” (video-object), denoted V., p=1, .
`.
`. .P. A
`V-object contains the label, centroid, bounding box, and
`shape mask of its corresponding region, as well as object
`Velocity and trajectory information by the tracking process.
`V-objects are then tracked through the Segmented Video
`Sequence. Given Segmented images C, and C.
`With
`V-objects V= {VP; p=1, .
`.
`. .P} and V={V;
`q=1, . . . .Q}, respectively, the motion tracking process
`“links' V-objects V, and V,
`if their position and esti
`mated Velocity indicate that they correspond to the same
`real-world object appearing in frames F, and F. This is
`
`8
`determined using linear prediction of V-object positions and
`a “mutual nearest neighbor criterion via the following
`procedure:
`1. For each V-object VPeV., predict its position in the
`next frame using
`
`where u is the predicted centroid of V, in C, u, is the
`centroid of V, measured in C, u,
`is the estimated
`(forward) velocity of V., and t
`and t are the timestamps
`of frames F and F, respectively. Initially, the Velocity
`estimate is set to us,’=(0,0).
`2. For each VeV., determine the V-object in the next
`frame with centroid nearest u?. This “nearest neighbor” is
`denoted n. Thus,
`
`3. For every pair (V, n=V, ) for which no other
`V-objects in V, have V,
`as a nearest neighbor, estimate
`u,
`; the (forward) velocity of V,
`as
`
`ri-1 ?
`
`t
`
`n+1
`in-1
`
`if
`in
`
`(1)
`
`=(0,0).
`otherwise, Set U,
`These steps are performed for each C, n=0,1,...,N-2.
`StepS 1 and 2 find nearest neighbors in the Subsequent frame
`for each V-object. Step 3 generates Velocity estimates for
`V-objects that can be unambiguously tracked; this informa
`tion is used in Step 1 to predict V-object positions for the next
`frame.
`Next, StepS 1-3 are repeated for the reverse Sequence, i.e.,
`C, n=N-1, N-2, . . . , 1. This results in a new set of
`predicted centroids, Velocity estimates, and nearest neigh
`bors for each V-object in the reverse direction. Thus, the
`V-objects are tracked both forward and backward through
`the Sequence. The remaining StepS are then performed:
`4. V-objects V, and V,
`are mutual nearest neighbors
`if n=V, and n =V... (Here, n, is the nearest neigh
`bor of V, in the forward direction, and n
`is the nearest
`neighbor of V., in the reverse direction.) For each pair of
`mutual nearest neighbors (V, V) create a primary link
`from V, to V.
`5. For each VeV, without a mutual nearest neighbor,
`create a secondary link from V to n,
`if the predicted
`centroid u,
`is within e of n, where e is Some Small
`distance.
`without a mutual nearest
`in V,
`6. For each V,
`neighbor, create a Secondary link from n', to V,
`if the
`predicted centroid it,” is within e of n,
`i.
`The object tracking procedure uses the mutual nearest
`neighbor criterion (Step 4) to estimate frame-to-frame
`V-object trajectories with a high degree of confidence. Pairs
`of mutual nearest neighbors are connected using a “primary'
`link to indicate that they are highly likely to represent the
`Same real-world object in Successive Video frames.
`Steps 5-6 associate V-objects that are tracked with less
`confidence but display evidence that they might result from
`the same real-world object. Thus, these objects are joined by
`"Secondary links. These Steps are necessary to account for
`the “split' and "join' type motion Segmentation errors as
`described above.
`The object tracking process results in a list of V-objects
`and connecting links that form a directed graph (digraph)
`
`ri-1
`
`ri--1
`
`5,969,755
`
`15
`
`25
`
`35