(12) United States Patent
`Brill et al.
`
`USOO6628835B1
`(10) Patent No.:
`US 6,628,835 B1
`(45) Date of Patent:
`Sep. 30, 2003
`
`(54) METHOD AND SYSTEM FOR DEFINING
`AND RECOGNIZING COMPLEX EVENTS IN
`A VIDEO SEQUENCE
`
`(75) Inventors: Frank Z. Brill, Plano, TX (US);
`Thomas J. Olson, Plano, TX (US)
`
`(73) ASSignee:
`
`(*) Notice:
`
`lysis Incorporated,
`s
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/379,986
`(22) Filed:
`Aug. 24, 1999
`Related U.S. Application Dat
`elated U.S. Application Uata
`(60) Provisional application No. 60/098,475, filed on Aug. 31,
`1998.
`(51) Int. Cl. ............................ G06K 9/68; G06K 9/00;
`HO4N 7/18
`(52) U.S. Cl. ........................ 382/226; 382/103; 348/155
`(58) Field of Search ................................. 382,218, 219,
`382/224, 225, 226, 103; 348/142, 143,
`152, 153, 154, 155; 386/69; 340/511
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,828.809 A * 10/1998 Chang et al. ................. 386/69
`5.969,755 A 10/1999 Courtney................... 348/143
`6,107,918 A
`8/2000 Klein et al. ................. 340/511
`6.295,367 B1 * 9/2001 Crabtree et al. ............ 382/103
`* cited bw examiner
`y
`Primary Examiner Mehrdad Dastouri
`(74) Attorney, Agent, or Firm-Robert D. Marshall, Jr.; W.
`James Brady, III; Frederick J. Telecky, Jr.
`(57)
`ABSTRACT
`Given a System which detects simple events, one can define
`a complex event by constructing a list of Sub-events. In order
`to recognize a complex event, the System keeps a record of
`the sub-events that have occurred thus far and the objects
`involved in these Sub-events. Whenever the first Sub-event in
`a complex event's Sequence is recognized, an activation for
`that complex event is created. The activation contains an
`indication of the identity of the object involved in the event.
`The activation also includes an index initialized to one. If a
`newly detected event matches the next Sub-event in any of
`the currently open complex events, the indeX for that com
`plex event is incremented. If the index reaches the total
`number of Sub-events in that complex event, the complete
`complex event is recognized. Thus any desired alarm S
`generated. Since the complex event that was just recognized
`may also be a Sub-event of another complex event, the
`activation lists are consulted again to See if the indices of any
`other complex event activations can be advanced.
`
`5,666,157 A
`
`9/1997 Aviv .......................... 348/152
`
`6 Claims, 4 Drawing Sheets
`
`
`
`EVENT OF COMPLEX
`EVENT
`
`304
`
`305
`
`YES
`
`OPEN COMPLEX EVENT
`
`SET INDEX TO ONE
`
`NEXT
`EVENT OF COMPLEX
`EVENT
`
`NO
`
`306
`
`YES
`
`307
`
`NCREMENT INDEX
`
`NDEX
`EQUAL NUMBER OF
`EVENTS OF COMPLEX
`EVENT
`
`
`
`
`
`308
`
`YES
`
`DETEC COMPLEX EVENT
`
`AVIGILON EX. 2008
`IPR2019-00236
`Page 1 of 11
`
`

`

`U.S. Patent
`
`US 6,628,835 B1
`
`| Z
`
`
`
`
`
`
`
`BONWABINE 11XB
`
`Ø | No.
`
`AVIGILON EX. 2008
`IPR2019-00236
`Page 2 of 11
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 2 of 4
`
`US 6,628,835 B1
`
`300
`
`
`
`301
`
`INPUT NEW IMAGE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EVENT OF COMPLEX
`EVENT
`
`
`
`OPEN COMPLEX EVENT
`
`SET INDEX TO ONE
`
`NEXT
`EVENT OF COMPLEX
`EVENT
`
`INCREMENT INDEX
`
`INDEX
`EQUAL NUMBER OF
`EVENTS OF COMPLEX
`EVENT
`
`308
`
`YES
`
`DETECT COMPLEX EVENT
`
`FIC. 3
`
`AVIGILON EX. 2008
`IPR2019-00236
`Page 3 of 11
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 3 of 4
`
`US 6,628,835 B1
`
`400
`y
`
`FROM 502
`
`
`
`
`
`
`
`402
`
`MATCH
`NEGATED
`EVENT2
`
`CLOSE
`COMPLEX EVENT
`
`
`
`
`
`
`
`MATCH NEXT
`NON-NEGATED
`EVENT
`
`404
`
`
`
`
`
`UPDATE INDEX
`
`
`
`
`
`INDEX
`EQUAL NUMBER OF
`EVENTS OF COMPLEX
`EVENT
`
`TO 309
`FIC. 4
`
`FROM 302
`
`500
`
`
`
`
`
`
`
`
`
`
`
`MATCH
`NEGATED
`EVENT
`
`YES
`
`TRACK OBJECT
`AND EVENT
`
`502
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TO 501
`
`
`
`CLOSE
`COMPLEX
`EVENT
`
`
`
`MATCH NEXT
`NON-NEGATED
`EVENT
`
`PRIOR
`OBJECT MATCH
`ON NEGATED
`EVENT2
`
`
`
`
`
`
`
`
`
`TO 301
`
`EQUAL NUMBER OF
`EVENTS OF COMPLEX
`EVENT
`
`TO 309
`FIC. 6
`
`AVIGILON EX. 2008
`IPR2019-00236
`Page 4 of 11
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 4 of 4
`
`US 6,628,835 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Name :
`
`Events:
`
`Objects:
`
`Days of week:
`
`remove
`
`unknown
`
`
`
`Loiter by the door
`deposit
`leave
`alone
`enter
`exit Eloiter
`lightson
`lightsout
`outcar
`move
`rest
`incar
`object
`notebook
`car
`person
`box
`briefcase
`Wednesday
`Thursday
`Monday
`Tuesday
`Sunday
`Friday
`Saturday
`Time of day: from 12:00 am P. until 12:00 am
`Regions:
`PC area
`outside-the-door
`phone-area
`Duration:
`Actions:
`
`beep
`
`log
`
`flash
`
`plot Evoice
`
`popup
`
`FIG. 6
`
`
`
`Name :
`
`Theft
`
`ordered E.
`
`Enter
`Remove
`MDeposit
`Exit
`
`Loiter by the door
`Deposit/Remove
`Leave the computer
`Deposit
`Ext
`Loiter by the phone
`Enter
`Lights On/Off
`cmonitor
`Remove
`
`Actions:
`
`beep
`
`log
`
`flash
`
`plot
`
`voice
`
`popup
`
`FIC. 7
`
`AVIGILON EX. 2008
`IPR2019-00236
`Page 5 of 11
`
`

`

`US 6,628,835 B1
`
`1
`METHOD AND SYSTEM FOR DEFINING
`AND RECOGNIZING COMPLEX EVENTS IN
`A VIDEO SEQUENCE
`This application claims priority under 35 USC S119(e)
`(1) of Provisional Application No. 60/098,475, filed Aug.
`31, 1998.
`
`TECHNICAL FIELD OF THE INVENTION
`The technical field of this invention is automatic security
`Systems particularly automatic Security Systems employing
`computer image processing for detecting complex events in
`a Video Sequence.
`
`BACKGROUND OF THE INVENTION
`Commercially available video event detection Systems
`use change detection to generate alarms. Since Such Systems
`generate an alarm when any motion occurs in the monitored
`area, incidental motion or change in lighting can generate
`false alarms. Recent advances in Video monitoring technol
`ogy enable the detection of more specific events than just
`motion, Such as when a person enters a room, deposits or
`picks up an object, or loiters for a while in a given area.
`Although the events these advanced Systems detect are more
`Sophisticated than those detected via motion detection, they
`are Still unstructured events that are detected regardless of
`the context in which they occur. This can result in alarms
`being generated on events that are not of interest.
`For example, if a System is monitoring a room or Store
`with the intention of detecting theft, the system could be set
`up to generate an alarm whenever an object is picked up.
`However, no theft has occurred unless the person leaves the
`area with the object. A simple, unstructured event detection
`System would generate an alarm every time Someone picked
`up an object. This would result in many false alarms.
`Therefore there is a need in the art for a System that can
`recognize complex events an thus filter out false positive
`alarms.
`
`SUMMARY OF THE INVENTION
`Given a System which detects simple events, one can
`easily create a user interface that enables Someone to define
`a complex event by constructing a list of Sub-events. After
`one or more complex events have been defined, the Sub
`events of complex events defined later can be complex
`events themselves. AS an alternative user interface, complex
`events could be constructed in a top-down fashion, defining
`the highest-level complex event first, and then recursively
`defining the Sub-events until all of the lowest-level events
`are simple.
`Once the user has defined the complex events and the
`actions to take when they occur, the event detection System
`must recognize these events as they occur in the monitored
`area. For the purposes of this application, assume a priori
`that the simple events can be recognized and that the object
`involved in them can be tracked. The preferred embodiment
`uses the method discussed above to recognize the Simple
`events or any other Suitable prior art technique. In order to
`recognize a complex event, the System must keep a record
`of the Sub-events that have occurred thus far and the objects
`involved in these Sub-events. Whenever the first Sub-event in
`a complex event's Sequence is recognized, an activation for
`that complex event is created. The activation contains an
`indication of the identity of the object involved in the event.
`The activation also includes an index, which is the number
`
`2
`of Sub-events in the Sequence that have been recognized thus
`far. The index is initialized to 1 when the activation is
`created, since the activation is only created when the first
`sub-event of that complex event is detected. The system
`maintains a list of current activations for each defined
`complex event type. Whenever any new event is detected,
`the list of current activations is consulted to see if the newly
`detected event matches the next Sub-event in any of the
`currently open complex events. If So, the indeX for that
`complex event is incremented. If the indeX reaches the total
`number of Sub-events in the Sequence for that complex
`event, the complete complex event has been recognized.
`Thus any desired alarm is generated. Since the complex
`event that was just recognized may also be a Sub-event of
`another complex event, the activation lists are consulted
`again to see if the indices of any other complex event
`activations can be advanced.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`These and other aspects of this invention are illustrated in
`the drawings, in which:
`FIG. 1 is a diagrammatic view of a Surveillance System
`used monitor activity in a Selected region or area;
`FIG. 2 illustrates an example of one known motion
`analysis technique;
`FIG. 3 illustrates in flow chart form the process of
`detection of complex events,
`FIG. 4 illustrates in flow chart form part of the process of
`detecting complex events having negated events,
`FIG. 5 illustrates in flow chart form part of the process of
`detecting complex events having an initial negated event;
`FIG. 6 illustrates a user interface enabling the user to
`Select which events are to form the complex event via a
`dialog box interface; and
`FIG. 7 illustrates a user interface enabling a user to define
`a complex event via a dialog box interface.
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`FIG. 1 is a diagrammatic view of a Surveillance or
`monitoring system 10 which embodies the present
`invention, and which is used monitor activity in a Selected
`region or area. The monitoring System 10 also includes a
`camera unit 12, a computer WorkStation 13, which are
`operatively coupled by a network shown Schematically at
`14. The network 14 may be a local area network, the
`Internet, Some other type of network, a modem link or a
`combination of these technologies. The computer WorkSta
`tion 13 may be a personal computer including a processor
`17, a keyboard 18, a mouse 19 and a display unit 21.
`The camera unit 12 includes video camera 23. Video
`camera 23 in the disclosed embodiment is a known mono
`chrome camera that outputs gray-Scale images. However,
`the present invention may be utilized with a color video
`camera or Some other type of two-dimensional image
`detector, Such as an infrared detector. Video camera 23
`includes detector 24. Detector 24 may be a charge coupled
`device (CCD) or a CMOS image detector as known in the
`art. Video camera 23 not-illustrated includes optics of a
`known type, which focuses an image on detector 24.
`Camera unit 12 further includes an image processing
`Section 27. The image processing Section 27 includes a video
`interface circuit 28 to receive the output of image detector
`24. A network interface 29 facilitates communication acroSS
`network 14. Image processing Section 27 could also include
`
`5
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`AVIGILON EX. 2008
`IPR2019-00236
`Page 6 of 11
`
`

`

`US 6,628,835 B1
`
`1O
`
`25
`
`35
`
`40
`
`3
`a modem in addition to or in place of network interface 29.
`This would enable communications via a telephone line.
`Image processing Section 27 further includes a processor 33.
`Processor 33 preferably consists of a digital signal processor
`and its corresponding volatile memory. Image processing
`Section 27 includes a non-volatile memory Such as hard disk
`drive 34 illustrated in FIG. 1. Hard disk drive 34 could
`optionally be replaced or Supplemented by another Suitable
`type of non-volatile memory such as FLASH memory,
`EPROM memory or DRAM memory with battery backup.
`In the preferred embodiment, image processing Section 27
`is co-located in the same physical housing as camera 23.
`Thus camera unit 12 is a Stand alone device which may be
`directly coupled to network 14. However, it will be recog
`nized by those skilled in the art that image processing
`15
`section 27 could alternatively be implemented within com
`puter WorkStation 13 and physically Separate from camera
`23. In this alternative, computer workstation 13 preferably
`includes a plug-in video capture card Serving a video inter
`face and a plug-in network interface card for communication
`via network 14. Though the embodiment disclosed includes
`a single camera 23, it is possible to provide plural cameras
`With a single image processing Section.
`The basic System performs three data processing Steps for
`every image of a Video Sequence to recognize events. The
`three Steps are detecting objects, tracking objects, and ana
`lyzing the motion graph.
`Once objects are detected in a Video image, the next Step
`is to track each object through the Video Sequence. This task
`is done by linking objects in the previous frame to their
`corresponding objects in the current frame. Correspondence
`is established by matching objects with their nearest neigh
`bors. The path of links which follows a given object through
`Successive frames is called an object's track. The objects and
`their tracks create a directed graph which represents the
`history of the motion of the objects in a Video Sequence. This
`directed graph is called a motion graph. The goal of this Step
`is to create a motion graph for use by the next step in event
`recognition.
`Finally, to recognize events, the System analyzes the
`motion graph. The preferred, embodiment of the System
`recognizes the following vocabulary of events: ENTER,
`EXIT, REST, MOVE, DEPOSIT, REMOVE, LIGHTS-ON
`and LIGHTS-OUT. These events are examples of the most
`common in an office environment where the main interac
`tion is between people and Smaller Stationary objects. Other
`examples would be applicable to monitoring outdoors, Such
`as a parking lot.
`The image processing Section 27 analyzes the motion
`graph by tracking movement or non-movement of each
`identified change region through a Succession of the frames
`or images from the Video camera. For purposes of facilitat
`ing an understanding of the present invention, one known
`motion analysis technique will be briefly summarized with
`reference to FIG. 2. Although it will be recognized that
`motion analysis in the Video images is carried out in two
`dimensions, for purposes of convenience the diagram of
`FIG. 2 shows just one dimension.
`In FIG. 2, the nineteen vertical lines F0 through F18 each
`represent a respective frame or image in a Series of Succes
`sive images from the video camera 12. In FIG. 2, the
`horizontal, dimension represents time, and the vertical
`dimension represents one dimension of movement of an
`object within a two-dimensional image. When an object
`which was not previously present first appears, for example
`at 51 or 52, it is identified as an entrance or ENTER event.
`
`65
`
`45
`
`50
`
`55
`
`60
`
`4
`When an object which was previously present is found to no
`longer be present, for example at 53 or 54, it is designated
`an EXIT event. If an existing object splits into two objects,
`one of which is moving and the other of which is Stationary,
`for example as at 57, it is designated a DEPOSIT event. This
`would occur, for example, when a person who is carrying a
`briefcase Sets it down on a table, and then walks away.
`If a moving object merges with a Stationary object, and
`then continues to move while the Stationary object
`disappears, as at 58, it is designated a REMOVE event. This
`would correspond to a situation where a person walks to a
`notebook resting on a table, and then picks up the notebook
`and walks away.
`Three other types of events, which are not specifically
`illustrated in FIG. 2, are a REST event, a MOVE event, and
`a LIGHTS-OUT event. A REST event occurs when a mov
`ing object comes to a stop but continues to be present
`without moving. A practical example is a Situation where the
`objects being monitored are vehicles in a parking lot, and a
`car pulls into a parking Space and thereafter remains Sta
`tionary. AMOVE event occurs when a detected object which
`has been Stationary begins moving again, for example when
`a car that has been parked begins moving. A LIGHTS-OUT
`event occurs when the entire detected image Suddenly
`changes, for example when the lights in a monitored room
`are turned out and the room becomes dark.
`In the present invention the Surveillance System can be
`programmed to only generate an alarm upon the occurrence
`of a complex event made up of a Series of Simple events.
`Returning to the THEFT example, a better system would
`generate an alarm only when the REMOVE event is fol
`lowed by an EXIT event. The EXIT event provides context
`for the REMOVE event that enables the system to filter out
`uninteresting cases in which the perSon does not leave the
`area with the object they picked up. This application
`describes the invention of Such a complex event detection
`System.
`In the Subsequent discussion, the term Simple event means
`an unstructured atomic event. Detection of these events is
`known in the art and Such detection is described above. A
`complex event is structured, in that it is made up of one or
`more Sub-events. The Sub-events of a complex event may be
`Simple events, or they may be complex, enabling the defi
`nition of event hierarchies. Event may refer to either a
`Simple or a complex event. In our theft example above,
`REMOVE and EXIT are simple events, and THEFT is a
`complex event. A user may also define a further event, for
`example CRIME-SPREE, which may have one or more
`complex THEFT events as sub-events.
`Given a System which detects simple events, the invention
`creates a user interface that enables Someone to define a
`complex event by constructing a list of Sub-events. After one
`or more complex events have been defined, the Sub-events
`of complex events defined later can be complex events
`themselves. AS an alternative user interface, complex events
`could be constructed in a top-down fashion, defining the
`highest-level complex event first, and then recursively defin
`ing the sub-events until all of the lowest-level events are
`Simple.
`FIG. 3 illustrates the process 300 for detecting complex
`events. Once the user has defined the complex events and the
`actions to take when they occur, the event detection System
`must recognize these events as they occur in the monitored
`area. For the purposes of this disclosure, assume a priori that
`the Simple events can be recognized and that the object
`involved in them can be tracked (process blocks 301 and
`
`AVIGILON EX. 2008
`IPR2019-00236
`Page 7 of 11
`
`

`

`US 6,628,835 B1
`
`15
`
`25
`
`S
`302). The preferred embodiment uses the method any suit
`able prior art technique. In order to recognize a complex
`event, the System must keep a record of the Sub-events that
`have occurred thus far, and the objects involved in them.
`Whenever the first sub-event in a complex event's sequence
`is recognized (decision block 303), an activation for that
`complex event is created (processing block 304). The acti
`vation contains the ID of the object involved in the event,
`and an index, which is the number of Sub-events in the
`Sequence that have been recognized thus far. The indeX is
`initialized to 1 when the activation is created (processing
`block 305), since the activation is only created when the first
`Sub-event matches. The System maintains a list of current
`activations for each defined complex event type. Whenever
`any new event is detected, the list of current activations is
`consulted to see if the newly detected (or incoming) event
`matches the next Sub-event in the complex event (decision
`block 306). If so, the index is incremented (processing block
`307). If the index reaches the total number of sub-events in
`the sequence (decision block 308), the complete complex
`event has been recognized (processing block 309), and any
`desired alarm can be generated. Also, Since the complex
`event that was just recognized may also be a Sub-event of
`another complex event, the activation lists are consulted
`again (decision block 303) to see if the indices of any other
`complex event activations can be advanced. Otherwise, the
`process returns to input the next image (processing block
`301) and repeats.
`To return to our THEFT example, the complex THEFT
`event has two Sub-events, REMOVE and EXIT. When a
`REMOVE event occurs, an activation for the THEFT event
`is created, containing the identity of the perSon involved in
`the REMOVE event and an index set to 1. Later, when
`another event is recognized by the System, the activation is
`consulted to see if the event type of this newly detected
`event matches the next Sub-event in the Sequence. In this
`example the next sub-event in THEFT is EXIT. If the event
`type matches, the object identity is also checked. In this
`example, the object identity is checked to See if the perSon
`EXITing is the same as that of the person who earlier
`40
`REMOVEd the object. This prevents signaling a THEFT
`event when one person picks up an object and a different
`perSon exits the area. In a closed environment, the object
`identities used may merely be the track IDs. Each object that
`enters the monitored area is assigned a unique track ID, and
`this track ID is discarded when the object is no longer being
`tracked. If both the event type and the object ID match, the
`activations indeX is incremented to 2. Since there are only
`2 Sub-events in the complex event in this example, the entire
`complex-event has been recognized, and an alarm is gener
`ated if desired. Since the THEFT event has been recognized,
`this newly recognized THEFT event may be a sub-event of
`another complex event. When the complex THEFT event is
`recognized, the current activations are recursively checked
`to see if the theft is a part of another higher-level event, Such
`as a CRIME-SPREE
`This is the basic mechanism for defining and detecting
`complex events. There are Several variants on this basic
`mechanism, Some of which will be described next. The first
`variation is to allow unordered events. It may be desirable to
`Signal an alarm if and only if all of the Sub-events in a
`complex event are detected involving a given object, regard
`less of the order in which they occur. The complex event is
`the logical conjunction of the Sub-events. To implement this
`case, the activation consists of an object ID and a list of the
`Sub-events that have not yet been detected. AS each Sub
`event is detected, it is deleted from the activation's list. If the
`
`6
`list becomes empty, the complete unordered complex event
`has occurred. It may also be useful to define a complex event
`that is signaled if any of the complex event's Sub-events is
`detected. The complex event is the logical disjunction of its
`Sub-events. In this case, the concept of an activation is not
`needed. If any of the sub-events is detected, then the
`complex event is recognized immediately.
`Another variation is the concept of negated Sub-event.
`Considering the THEFT example, if the person pays for the
`item, then it is not a theft. If the perSon puts the item back
`down before leaving, then it is also not a theft. A more
`complete definition of THEFT is one in which a person picks
`up an item and then leaves without putting it back or paying.
`This complex event can be expressed as an ordered, complex
`event with negated Sub-events. ASSume the System can
`detect the simple events REMOVE, DEPOSIT, PAY, and
`EXIT. The complex THEFT event can now be expressed as
`the ordered list:
`1. REMOVE
`2. DEPOSIT
`3. PAY
`4. EXIT
`symbol indicates negation. Thus THEFT is
`where the
`detected if a person REMOVEs an object and EXITs without
`either DEPOSITing that object or PAYing. The user interface
`for defining complex events can easily be augmented to
`allow the users to negate Some of the Sub-events. The
`complex event recognition System may need to be enhanced
`to handle negated Sub-events.
`FIG. 4 illustrates a part of the process 400 of detecting
`complex events having negated events. The process 400
`takes place following detection of simple events (processing
`block 302). When the initial event of a complex event is
`detected, an activation for the complex event is created as
`before, and as Subsequent events are detected, they are
`checked to see if they match the next sub-event. At first the
`negation is ignored. The System checks to see if the incom
`ing event matches the non-negated version of the next
`sub-event (decision block 401). However, the action taken
`based on a match is different than for non-negated events. If
`there is a match, instead of incrementing the indeX as with
`the non-negated Sub-events, the activation is deleted
`(processing block 402).
`If the next Sub-event in the Sequence is negated, and the
`incoming event does not match, then the action to take is
`more complicated. The System now considers the next
`Sub-event and See if it is also negated. If that one also is a
`negated event, the Systems continues again to the next
`Sub-event to see if it matches. The System continues in this
`fashion as long as the next Sub-event in the Sequence is
`negated and the incoming event does not match it. If the
`System ever matches a negated Sub-event (decision block
`401), the activation is canceled (processing block 402).
`When reaching a non-negated Sub-event, the System checks
`for a match to the event (decision block 403). If a match is
`found, the System updates the activation's index (processing
`block 404). The case of reaching the end of the sub-event list
`without encountering a non-negated Sub-event will be dis
`cussed later. The updated value of the activation's index
`depends on whether the incoming event matches this non
`negated Sub-event. If the incoming event matches the non
`negated Sub-event, then the indeX is advanced past the
`negated Sub-events up to the just-matched non-negated
`Sub-event. If the incoming event does not match the non
`negated Sub-event, the indeX is left unchanged. This means
`that the System will check all of the negated Sub-events again
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`AVIGILON EX. 2008
`IPR2019-00236
`Page 8 of 11
`
`

`

`US 6,628,835 B1
`
`15
`
`25
`
`35
`
`40
`
`7
`when a new incoming event is detected. AS before, if a
`non-negated event is detected the System checks to deter
`mine if the index reaches the total number of Sub-events in
`the sequence (decision block 405). If so, this complex event
`is detected as before (processing block 309). If not the loop
`repeats.
`This is illustrated using our THEFT example again. Recall
`that our definition of the THEFT event is the 4 Sub-event
`sequence (REMOVE, DEPOSIT, PAY, EXIT). Let's say a
`person has picked up an object, so there is a THEFT
`activation with index 1. If the next event that is detected is
`LOITER, the system first checks to see if the incoming
`LOITER event matches DEPOSIT. Since it doesn’t, and
`DEPOSIT is negated in this event definition, the system
`moves to the next Sub-event and checks if the incoming
`LOITER matches PAY, which it doesn't. Since PAY is also
`negated, the System advances again to see if LOITER
`matches EXIT, which it doesn't. Since EXIT is not negated
`in this case, and doesn’t match, checking for this incoming
`event is complete. The System leaves the index unchanged at
`1. If the system recognizes another LOITER event, or any
`other event which is neither DEPOSIT, PAY, nor EXIT, the
`System will go through this entire proceSS again and the
`indeX will remain at 1.
`If the system detects a DEPOSIT or PAY event involving
`the appropriate perSon and object, the activation would be
`canceled. Intuitively, Since the perSon put the object back
`down or paid for it, no theft can occur. If the perSon pickS
`up another object, then the System will instantiate a new
`activation. So the matching of a negated Sub-event cancels
`the activation.
`If the system detects an EXIT of the appropriate person
`and the activation has not been canceled, Since the indeX is
`still 1, then the system attempts to match the incoming EXIT
`event to DEPOSIT and PAY (which do not match), and
`finally attempt to match EXIT, which succeeds. Since a
`match to the non-negated Sub-event has been detected, the
`index is set to the index of the matched Sub-event. In this
`case the indeX would be changed from 1 to 4. Since the
`complex event in this example has 4 Sub-events, and the
`indeX is now 4, the entire complex event has been matched,
`and system has recognized the THEFT event. Intuitively,
`there has been a REMOVE and an EXIT with no intervening
`DEPOSIT or PAY; this is the definition for theft.
`Another application of the complex event with negated
`Sub-events is to detect Suspicious behavior in front of a
`building. The normal behavior may be for a person to park
`the car, get out of it, and then come up into the building. If
`the person parks the vehicle and leaves the area without
`coming up into the building, this may be a car bombing
`scenario. If the system can detect the sub-events for PARK,
`OUTCAR, ENTER-BUILDING, and EXIT, the car
`bombing scenario can be defined as (PARK, OUTCAR,
`ENTER-BUILDING, EXIT).
`Consider a different car bombing scenario in which two
`cars pull up in front of the building, and a person gets out of
`one car and into the other, which drives away. One car
`remains which may contain the bomb. This Scenario may be
`defined as (PARK, OUTCAR, INCAR, EXIT), in which the
`INCAR and OUTCAR are for the same person changing
`cars. The EXIT event is for the getaway car leaving the
`Scene. However, this definition would also match the event
`in which the person gets back into the same car and drives
`away, which should not be a car bomb event. The INCAR
`and OUTCAR events must involve the same person but
`different cars. The mechanism discussed thus far has no
`provision for specifying that objects involved be different. In
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`fact, they are all assumed to be the same, and our poorly
`defined car bombing scenario will only be detected if the
`person gets in and out of the Same car, which is not the
`desired complex event.
`This problem can be resolved if the complex event
`detection System is augmented to allow the user to label the
`objects involved in the event. If the labels given to objects
`in the event definition are the same, this indicates that the
`objects involved are required to be same object, whereas if
`the labels are different, the objects are required to be
`different. The user can also indicate that it doesn’t matter
`whether the objects are the Same, perhaps by leaving the
`label blank. For events Such as OUTCAR which involve
`more than one object (the person and the car), multiple
`labels must be provided, perhaps with an ordering conven
`tion to resolve which label corresponds to the car, and which
`corresponds to the person. OUTCAR(PC) could mean that
`perSon P got out of car C. Using the labeling mechanism, the
`user could correctly define our new car bombing Scenario as
`(PARK(A), OUTCAR(P, A), INCAR(P B), EXIT(A),
`EXIT(B)). Intuitively, this says that a car parks, a person
`gets out of it, and that person then gets into a different car.
`The second car exits the Scene but the first does not. The fact
`that the label P is used in both the INCAR and OUTCAR
`events indicates that the same perSon is involved in both
`events, whereas the use of the different labels for cars
`requires that the cars be different. To make the event
`definition more clear, one might use mnemonic labels for the
`cars. Such as CAR-BOMB and GETAWAY-CAR.
`Some events may not have objects associated with them.
`For example, a LIGHTS-OUT event can be detected without
`reference to any object. Such events will always match,
`without checking any object Ids. Alternately, one could think
`of Such events as having an implicit object in which the label
`is left blank to indicate a don't-care condition.
`For yet another variant on complex event detection, return
`to the THEFT example. Imagine that a person picks