Intelligent camera selection and object tracking

Technical Field

0001This invention relates to computer-based methods and systems for video surveillance, and more specifically to a computer-aided surveillance system capable of tracking objects across multiple cameras.

Background Information

0002The current heightened sense of security and declining cost of camera equipment have increased the use of closed-circuit television (CCTV) surveillance systems. Such systems have the potential to reduce crime, prevent accidents, and generally increase security in a wide variety of environments.

0003As the number of cameras in a surveillance system increases, the amount of information to be processed and analyzed also increases. Computer technology has helped alleviate this raw data-processing task, resulting in a new breed of monitoring device - the computer-aided surveillance (CAS) system. CAS technology has been developed for various applications. For example, the military has used computer-aided image processing to provide automated targeting and other assistance to fighter pilots and other personnel. In addition, CAS has been applied to monitor activity in environments such as swimming pools, stores, and parking lots.

0004A CAS system monitors "objects" (e.g., people, inventory, etc.) as they appear in a series of surveillance video frames. One particularly useful monitoring task is tracking the movements of objects in a monitored area. To achieve more accurate tracking information, the CAS system can utilize knowledge about the basic elements of the images depicted in the series of video frames.

0005A simple surveillance system uses a single camera connected to a display device. More complex systems can have multiple cameras and/or multiple displays. The type of security display often used in retail stores and warehouses, for example, periodically switches the video feed displayed on a single monitor to provide different views of the property. Higher-security installations such as prisons and military installations use a bank of video displays, each showing the output of an associated camera. Because most retail stores, casinos, and airports are quite large, many cameras are required to sufficiently cover the entire area of interest. In addition, even under ideal conditions, single-camera tracking systems generally lose track of monitored objects that leave the field-of-view of the camera.

0006To avoid overloading human attendants with visual information, the display consoles for many of these systems generally display only a subset of all the available video data feeds. As such, many systems rely on the attendant's knowledge of the floor plan and/or typical visitor activities to decide which of the available video data feeds to display. [0008] Unfortunately, developing a knowledge of a location's layout, typical visitor behaviour, and the spatial relationships among the various cameras imposes a training and cost barrier that can be significant. Without intimate knowledge of the store layout, camera positions and typical traffic patterns, an attendant cannot effectively anticipate which camera or cameras will provide the best view, resulting in a disjointed and often incomplete visual records. Furthermore, video data to be used as evidence of illegal or suspicious activities (e.g., intruders, potential shoplifters, etc.) must meet additional authentication, continuity and documentation criteria to be relied upon in legal proceedings. Often criminal activities can span the fields-of- view of multiple cameras, and possibly be out of view of any camera for some period of time. Video that is not properly annotated with date, time, and location information, and which includes temporal or spatial interruptions may, not be reliable as evidence of an event or crime. It is known from patent publication <patcit id="pcit0001" dnum="US20040130620A"><text>US2004/0130620</text></patcit> to use blob numbers associated with points on images identified in a video data feed to identify common objects as they move from the video data feed from one video to the video data feed from another video, and also to use of probabilities of an object observed in one video data feed appearing in a second video data feed. US patent publication <patcit id="pcit0002" dnum="US2005012817A"><text>US2005//012817</text></patcit> relates generally to multiple camera systems and discusses sensing the position of objects and then assigning cameras to the senses objects.

Summary of the Invention

0007The invention generally provides for video surveillance systems, data structures, and video compilation techniques that model and take advantage of known or inferred relationships among video camera positions to select relevant video data streams for presentation and/or video capture. Both known physical relationships - a first camera being located directly around a corner from a second camera, for example - and observed relationships (e.g., historical data indicating the travel paths that people most commonly follow) can facilitate an intelligent selection and presentation of potential "next" cameras to which a subject may travel. This intelligent camera selection can therefore reduce or eliminate the need for users of the system to have any intimate knowledge of the observed property, thus lowering training costs, minimizing lost subjects, and increasing the evidentiary value of the video.

0008Accordingly, one related aspect provides a video surveillance system including a user interface and a camera selection module. The user interface includes a primary camera pane that displays video image data captured by a primary video surveillance camera, and two or more camera panes that are proximate to the primary camera pane. Each of the proximate camera panes displays video data captured by one of a set of secondary video surveillance cameras. In response to the video data displayed in the primary camera pane, the camera selection module determines the set of secondary video surveillance cameras, and in some cases determines the placement of the video data generated by the set of secondary video surveillance cameras in the proximate camera panes, and/or with respect to each other. The determination of which cameras are included in the set of secondary video surveillance cameras can be based on spatial relationships between the primary video surveillance camera and a set of video surveillance cameras, and/or can be inferred from statistical relationships (such as a likelihood-of-transition metric) among the cameras.

0009In some embodiments, the video image data shown in the primary camera pane is divided into two or more sub-regions, and the selection of the set of secondary video surveillance cameras is based on selection of one of the sub-regions, which selection may be performed, for example, using an input device (e.g., a pointer, a mouse, or a keyboard). In some embodiments, the input device may be used to select an object of interest within the video, such as a person, an item of inventory, or a physical location, and the set of secondary video surveillance cameras can be based on the selected object. The input device may also be used to select a video data feed from a secondary camera, thus causing the camera selection module to replace the video data feed in the primary camera pane with the video feed of the selected secondary camera, and thereupon to select a new set of secondary video data feeds for display in the proximate camera panes. In cases where the selected object moves (such as a person walking through a store), the set of secondary video surveillance cameras can be based on the movement (i.e., direction, speed, etc.) of the selected object. The set of secondary video surveillance cameras can also be based on the image quality of the selected object.

0010Another related aspect provides a user interface for presenting video surveillance data feeds. The user interface includes a primary video pane for presenting a primary video data feed and a plurality of proximate video panes, each for presenting one of a subset of secondary video data feeds selected from a set of available secondary video data feeds. The subset is determined by the primary video data feed. The number of available secondary video data feeds can be greater than the number of proximate video panes. The assignment of video data feeds to adjacent video panes can be done arbitrarily, or can instead be based on a ranking of video data feeds based on historical data, observation, or operator selection.

0011The invention provides a method for selecting video data feeds for display as set out in claim 1, and includes presenting a primary video data feed from a first camera in a primary video data feed pane, receiving an indication of an object of interest, in the primary video data pane, and presenting a secondary video data feed from another camera in a secondary video data pane in response to the indication of interest. Movement of the selected object is detected, and based on the movement, the data feed from the second video data pane replaces the data feed in the primary video data pane. A new secondary video data feed is automatically selected for display in the secondary video data pane. In some instances, the primary video data feed will not change, and the new secondary video data feed will simply replace another secondary video data feed.

0012The new secondary video data feed is determined based on a statistical measure such as a likelihood-of-transition metric that represents the likelihood that an object will transition from the primary video data feed to the second. The likelihood-of transition metric can be determined, for example, by defining a set of candidate video data feeds that, in some cases, represent a subset of the available data feeds and assigning to each feed an adjacency probability. In some embodiments, the adjacency probabilities can be based on predefined rules and/or historical data. The adjacency probabilities can be stored in a multi-dimensional matrix which can comprise dimensions based on the number of available data feeds, the time the matrix is being used for analysis, or both. The matrices can be further segmented into multiple sub- matrices, based, for example, on the adjacency probabilities contained therein.

0013Another related aspect provides a method of compiling a surveillance video. The method includes creating a surveillance video using a primary video data feed as a source video data feed, changing the source video data feed from the primary video data feed to a secondary video data feed, and concatenating the surveillance video from the secondary video data feed. In some cases, an observer of the primary video data feed indicates the change from the primary video data feed to the secondary video data feed, whereas in some instances the change is initiated automatically based on movement within the primary video data feed. The surveillance video can be augmented with audio captured from an observer of the surveillance video and/or a video camera supplying the video data feed, and can also be augmented with text or other visual cues.

0014Another related aspect provides a data structure organized as an N by M matrix for describing relationships among fields-of-view of cameras in a video surveillance system, where N represents a first set of cameras having a field-of-view in which an observed object is currently located and M representing a second set of cameras having a field-of-view into which the observed object is likely move. The entries in the matrix represent transitional probabilities between the first and second set of cameras (e.g., the likelihood that the object moves from a first camera to a second camera). In some embodiments, the transitional probabilities can include a time-based parameter (e.g., probabilistic function that includes a time component such as an exponential arrival rate), and in some cases N and M can be equal.

0015In another aspect, the invention comprises an article of manufacture baying a computer-readable medium with the computer-readable instructions embodied thereon, according to claim 10. In particular, the functionality of a method of the present invention may be embedded on a computer-readable medium, such as, but not limited to, a floppy disk, a hard disk, an optical disk, a magnetic tape, a PROM, an EPROM, CD-ROM, or DVD-ROM. The functionality of the techniques may be embedded on the computer-readable medium in any number of computer-readable instructions, or languages such as, for example, FORTRAN, PASCAL, C, C++, Java, C#, TcI, BASIC and assembly language. Further, the computer-readable instructions may, for example, be written in a script, macro, or functionally embedded in commercially available software (such as, e.g., EXCEL or VISUAL BASIC). The storage of data, rules, and data structures can be stored in one or more databases for use in performing the methods described above.

0016Other aspects and advantages of the invention will become apparent from the following drawings, detailed description, and claims, all of which illustrate the principles of the invention, by way of example only.

Brief Description of the Drawings

0017In the drawings, like reference characters generally refer to the same parts throughout the different views. Also, the drawings are not necessarily to scale, emphasis instead generally being placed upon illustrating the principles of the invention. [0020] <figref idref="f0001">FIG. 1</figref> is a screen capture of a user interface for capturing video surveillance data according to one embodiment of the invention.

0018<figref idref="f0001">FIG. 1</figref> is a screen capture of a user interface for capturing video surveillance data according to one embodiment of the invention.

0019<figref idref="f0002">FIG. 2</figref> is a flow chart depicting a method for capturing video surveillance data according to one embodiment of the invention.

0020<figref idref="f0003">FIG. 3</figref> is a representation of an adjacency matrix according to one embodiment of the invention.

0021<figref idref="f0004">FIG. 4</figref> is a screen capture of a user interface for creating a video surveillance movie according to one embodiment of the invention.

0022<figref idref="f0005">FIG. 5</figref> is a screen capture of a user interface for annotating a video surveillance movie according to one embodiment of the invention.

0023<figref idref="f0006">FIG. 6</figref> is a block diagram of an embodiment of a multi-tiered surveillance system according to one embodiment of the invention.

0024<figref idref="f0007">FIG. 7</figref> is a block diagram of a surveillance system according to one embodiment of the invention.

Detailed Description

<u>Computer Aided Tracking</u>

0025Intelligent video analysis systems have many applications. In real-time applications, such a system can be used to detect a person in a restricted or hazardous area, report the theft of a high-value item, indicate the presence of a potential assailant in a parking lot, warn about liquid spillage in an aisle, locate a child separated from his or her parents, or determine if a shopper is making a fraudulent return. In forensic applications, an intelligent video analysis system can be used to search for people or events of interest or whose behavior meets certain characteristics, collect statistics about people under surveillance, detect non-compliance with corporate policies in retail establishments, retrieve images of criminals' faces, assemble a chain of evidence for prosecuting a shoplifter, or collect information about individuals' shopping habits. One important tool for accomplishing these tasks is the ability to follow a person as he traverses a surveillance area and to create a complete record of his time under surveillance.

0026Referring to <figref idref="f0001">FIG. 1</figref> and in accordance with one embodiment of the invention, an application screen <b>100</b> includes a listing <b>105</b> of camera locations, each element of the list <b>105</b> relating to a camera that generates an associated video data feed. The camera locations may be identified, for example, by number (camera #2), location (reception, GPS coordinates), subject (jewelry), or a combination thereof. In some embodiments, the listing <b>105</b> can also include sensor devices other than cameras, such as motion detectors, heat detectors, door sensors, point-of-sale terminals, radio frequency identification (RFID) sensors, proximity card sensors, biometric sensors, and the like. The screen <b>100</b> also includes a primary camera pane 110 for displaying a primary video data feed <b>115</b>, which can be selected from one of the listed camera locations <b>105</b>. The primary video data feed <b>115</b> displays video information of interest to a user at a particular time. In some cases, the primary data feed <b>115</b> can represent a live data feed (i.e., the user is viewing activities as they occur in real or near-real time), whereas other cases the primary data feed <b>115</b> represents previously recorded activities. The user can select the primary video data feed <b>115</b> from the list <b>105</b> by choosing a camera number, by noticing a person or event of interest and selecting it using a pointer or other such input apparatus, or by selecting a location (e.g., "Entrance") in the surveillance region. In some embodiments, the primary video data feed <b>115</b> is selected automatically based on data received from one or more sensor nodes, for example, by detecting activity on a particular camera, evaluating rule-based selection heuristics, changing the primary video data feed according to a pre-defined schedule (e.g., in a particular order or at random), determining that an alert condition exists, and/or according to arbitrary programmable criteria.

0027The application screen <b>100</b> also includes a set of layout icons <b>120</b> that allow the user to select a number of secondary data feeds to view, as well as their positional layouts on the screen. For example, the selection of an icon indicating six adjacency screens instructs the system to configure a proximate camera area <b>125</b> with six adjacent video panes <b>130</b> that display video data feeds from cameras identified as "adjacent to" the camera whose video data feed appears in the primary camera pane <b>110</b>. Each pane (both primary 110 and adjacent 130) can be different sizes and shapes, in some cases depending on the information being displayed. Each pane <b>110</b>, <b>130</b> can show video from any source (e.g., visible light, infrared, thermal), with possibly different frame rates, encodings, resolutions, or playback speeds. The system can also overlay information on top of the video panes <b>110</b>, <b>130</b>, such as a date/time indicator, camera identifier, camera location, visual analysis results, object indicators (e.g., price, SKU number, product name), alert messages, and/or geographic information systems (GIS) data.

0028In some embodiments, objects within the video panes <b>110</b>, <b>130</b> are classified based on one or more classification criteria. For example, in a retail setting, a certain merchandise can be assigned a shrinkage factor representing a loss rate for the merchandise prior to a point of sale, generally due to theft. Using shrinkage statistics (generally expressed as a percentage of units or dollars sold), objects with exceptionally high shrinkage rates can be highlighed in the video panes <b>110</b>, <b>130</b> using bright colors, outlines or other annotations to focus the attention of a user on such objects. In some cases, the video panes <b>110</b>, <b>130</b> presented to the user can be selected based on an unusually high concentration of such merchandise, or the gathering of one or more suspicious people near the merchandise. As an example, due to their relative small size and high cost, razor cartridges for certain shaving razors are known to be high theft items. Using the technique described above, a display rack holding such cartridges can be identified as an object of interest. When there are no store patrons near the display, the video feed from the camera monitoring the display need not be shown on any of the displays <b>110</b>, <b>130</b>. However, as patrons near the display, the system identifies a transitory object (likely a store patron) in the vicinity of the display, and replaces one of the video feeds <b>130</b> in the proximate camera area <b>125</b> with the display from that camera. If the user determines the behavior of the patron to be suspicious, she can instruct the system to place that data feed in the primary video pane <b>110</b>.

0029The video data feed from an individual adjacent camera may be placed within a video pane <b>130</b> of the proximate camera area <b>125</b> according to one or more rules governing both the selection and placement of video data feeds within the proximate camera area <b>125</b>. For example, where a total of <b>18</b> cameras are used for surveillance, but only six data feeds can be shown in the proximate camera area <b>125</b>, each of the <b>18</b> cameras can be ranked based the likelihood that a subject being followed through the video will transition from the view of the primary camera to the view of each of the other seventeen cameras. The cameras with the six (or other number depending on the selected screen layout) highest likelihoods of transition are identified, and the video data feeds from each of the identified cameras are placed in the available video data panes 130 within the proximate camera area <b>125</b>.

0030In some cases, the placement of the selected video data feeds in a video data pane <b>130</b> may be decided arbitrarily. In some embodiments the video data feeds are placed based on a likelihood ranking (e.g., the most likely "next camera" being placed in the upper left, and least likely in the lower right), the physical relationships among the cameras providing the video data feeds (e.g., the feeds of cameras placed to the left of the camera providing the primary data feed appear in the left-side panes of the proximate camera area <b>125</b>), or in some cases a user-specified placement pattern. In some embodiments, the selection of secondary video data feeds and their placement in the proximate camera area <b>125</b> is a combination of automated and manual processes. For example, each secondary video data feed can be automatically ranked based on a "likelihood-of transition" metric.

0031One example of a transition metric is a probability that a tracked object will move from the field-of-view of the camera supplying the primary data feed <b>115</b> to the field-of-view of the cameras providing each of the secondary video data feeds. The first N of these ranked video data feeds can then be selected and placed in the first N secondary video data panes <b>130</b> (in counter-clockwise order, for example). However, the user may disagree with some of the automatically determined rankings, based, for example, on her knowledge of the specific implementation, the building, or the object being monitored. In such cases, she can manually adjust the automatically determined rankings (in whole or in part) by moving video data feeds up or down in the rankings. After adjustment, the first N ranked video data feeds are selected as before, with the rankings reflecting a combination of automatically calculated and manually specified rankings. The user may also disagree with how the ranked data feeds are placed in the secondary video data panes <b>130</b> (e.g., she may prefer clockwise to counter-clockwise). In this case, she can specify how the ranked video data feeds are placed in secondary video data panes 130 by assigning a secondary feed to a particular secondary pane <b>130</b>.

0032The selection and placement of a set of secondary video data feeds to include in the proximate camera area <b>115</b> can be either statically or dynamically determined. In the static case, the selection and placement of the secondary video data feeds are predetermined (e.g., during system installation) according to automatic and/or manual initialization processes and do not change over time (unless a re-initialization process is performed). In some embodiments, the dynamic selection and placement of the secondary video data feeds can be based on one or more rules, which in some cases can evolve over time based on external factors such as time of day, scene activity and historical observations. The rules can be stored in a central analysis and storage module (described in greater detail below) or distributed to processing modules distributed throughout the system. Similarly, the rules can be applied against pre-recorded and/or live video data feeds by a central rules-processing engine (using, for example, a forward-chaining rule model) or applied by multiple distributed processing modules associated with different monitored sites or networks.

0033For example, the selection and placement rules that are used when a retail store is open may be different than the rules used when the store is closed, reflecting the traffic pattern differences between daytime shopping activity and nighttime restocking activity. During the day, cameras on the shopping floor would be ranked higher than stockroom cameras, while at night loading dock, alleyway, and/or stockroom cameras can be ranked higher. The selection and placement rules can also be dynamically adjusted when changes in traffic patterns are detected, such as when the layout of a retail store is modified to accommodate new merchandising displays, valuable merchandise is added, and/or when cameras are added or moved. Selection and placement rules can also change based on the presence of people or the detection of activity in certain video data feeds, as it is likely that a user is interested in seeing video data feeds with people or activity.

0034The data feeds included in the proximate camera area <b>115</b> can also be based on a determination of which cameras are considered "adjacencies" of the camera being viewed in the primary video pane <b>110</b>. A particular camera's adjacencies generally include other cameras (and/or in some cases other sensing devices) that are in some way related to that camera. As one example, a set of cameras may be considered "adjacent" to a primary camera if a user viewing the primary camera will most likely to want to see that set of cameras next or simultaneously, due to the movement of a subject among the fields-of-view of those cameras. Two cameras may also be considered adjacent if a person or object seen by one camera is likely to appear (or is appearing) on the other camera within a short period of time. The period of time may be instantaneous (i.e., the two cameras both view the same portion of the environment), or in some cases there may be a delay before the person or object appears on the other camera. In some cases, strong correlations among cameras are used to imply adjacencies based on the application of rules (either centrally stored or distributed) against the received video feeds, and in some cases users can manually modify or delete implied adjacencies if desired. In some embodiments, users manually specify adjacencies, thereby creating adjacencies which would otherwise seem arbitrary. For example, two cameras placed at opposite ends of an escalator may not be physically close together, but they would likely be considered "adjacent" because a person will typically pass both cameras as they use the escalator.

0035Adjacencies can also be determined based on historical data, either real, simulated, or both. In one embodiment, user activity is observed and measured, for example, determining which video data feeds the user is most likely to select next based on previous selections. In another embodiment, the camera images are directly analyzed to determine adjacencies based on scene activity. In some embodiments, the scene activity can be choreographed or constrained using training data. For example, a calibration object can be moved through various locations within a monitored site. The calibration object can be virtually any object with known characteristics, such as a brightly colored ball, a black-and-white checked cube, a dot of laser light, or any other object recognizable by the monitoring system. If the calibration object is detected at (or near) the same time on two cameras, the cameras are said to have overlapping (or nearly overlapping) fields-of-view, and thus are likely to be considered adjacent. In some cases, adjacencies may also be specified, either completely or partially, by the user. In some embodiments, adjacencies are computed by continuously correlating object activity across multiple camera views as described in commonly-owned co-pending <patcit id="pcit0003" dnum="US660955A" dnum-type="L"><text>U.S. Patent Application Serial No. 10/660,955</text></patcit>, "Computerized Method and Apparatus for Determining Field-Of-View Relationships Among Multiple Image Sensors," the entire disclosure of which is incorporated by reference herein.

0036One implementation of an "adjacency compare" function for determining secondary cameras to be displayed in the proximate camera area is described by the following pseudocode: <pre listing-type="program-listing"> bool Isoverlap(time) { // consider two cameras to overlap // if the transition time is less than 1 second return time < 1, ) bool CompareAdjacency(prob1. time1, count1. prob2, time2, count2) { if(Isoverlap(time1) -- Isoverlap(time2)) { // both overlaps or both not if(count1 -- count2) return prob1 > prob2; else return count1 > count2; ) else { // one is overlap and one is not, overlap wins return time1 < time2; } }</pre>

0037Adjacencies may also be specified at a finer granularity than an entire scene by defining sub-regions <b>140</b>,<b>145</b> within a video data pane. In some embodiments, the sub-regions can be different sizes (e.g., small regions for distant areas, and large regions for closer areas). In one embodiment, each video data pane can be subdivided into 16 sub-regions arranged in a 4×4 regular grid and adjacency calculations based on these sub-regions. Sub-regions can be any size or shape - from large areas of the video data pane down to individual pixels and, like full camera views, can be considered adjacent to other cameras or sub-regions.

0038Sub-regions can be static or change over time. For example, a camera view can start with 256 sub-regions arranged in a 16x 16 grid. Over time, the sub-region definitions can be refined based on the size and shape statistics of the objects seen on that camera. In areas where the observed objects are large, the sub-regions can be merged together into larger sub-regions until they are comparable in size to the objects within the region. Conversely, in areas where observed objects are small, the sub-regions can be further subdivided until they are small enough to represent the objects on a one-to-one (or near one-to-one) basis. For example, if multiple adjacent sub-regions routinely provide the same data (e.g., if when a first sub-region shows no activity and a second sub-region immediately adjacent to the first also shows no activity) the two sub-regions can be merged without losing any granularity. Such an approach reduces the storage and processing resources necessary. In contrast, if a single sub-region often includes more than one object that should be tracked separately, the sub-region can be divided into two smaller sub-regions. For example, if a sub-region includes the field-of-view of a camera monitoring a point-of-sale and includes both the clerk and the customer, the sub-region can be divided into two separate sub-regions, one for behind the counter and one for in front of the counter.

0039Sub-regions can also be defmed based on image content. For example, the features (e.g., edges, textures, colors) in a video image can be used to automatically infer semantically meaningful sub-regions. For example, a hallway with three doors can be segmented into four sub-regions (one segment for each door and one for the hallway) by detecting the edges of the doors and the texture of the hallway carpet. Other segmentation techniques can be used as well, as described in commonly-owned U.S. Patent Application , "Method and Apparatus for Computerized Image Background Analysis". Furthermore, the two adjacent sub-regions may be different in terms of size and/or shape, e.g., due to the imaging perspective, what appears as a sub-region in one view may include the entirety of an adjacent view from a different camera.

0040The static and dynamic selection and placement rules described above for relationships between cameras can also be applied to relationships among sub-regions. In some embodiments, segmenting a camera's field-of-view into multiple sub-regions enables more sophisticated video feed selection and placement rules within the user interface. If a primary camera pane includes multiple sub-regions, each sub-region can be associated with one or more secondary cameras (or sub-regions within secondary cameras) whose video data feeds can be displayed in the proximate panes. If, for example, a user is viewing a video feed of a hallway in the primary video pane, the majority of the secondary cameras for that primary feed are likely to be located along the hallway. However, the primary video feed can include an identified sub-region that itself includes a light switch on one of the hallway walls, located just outside a door to a rarely-used hallway. When activity is detected within the sub-region (e.g., a person activating the light switch), the likelihood that the subject will transition to the camera in the connecting hallway increases, and as a result, the camera in the rarely-used hallway is selected as a secondary camera (and in some cases may even be ranked higher than other cameras adjacent to the primary camera).

0041<figref idref="f0002">FIG. 2</figref> illustrates one exemplary set of interactions among sensor devices that monitor a property, a user module for receiving, recording and annotating data received from the sensor devices, and a central data analysis module using the techniques described above. The sensor devices capture data (such as video in the case of surveillance cameras) (STEP 210) and transmit (STEP 220) the data to the user module, and, in some cases, to the central data analysis module. The user (or, in cases where automated selection is enabled, the user module) selects (STEP 230) a video data feed for viewing in the primary viewing pane. While monitoring the primary video pane, the user identifies (STEP 235) an object of interest in the video and can track the object as it passes through the camera's field-of-view. The user then requests (STEP 240) adjacency data from the central data analysis module to allow the user module to present the list of adjacent cameras and their associated adjacency rankings. In some embodiments, the user module receives the adjacency data prior to the selection of a video feed for the primary video pane. Based on the adjacency data, the user assigns (STEP 250) secondary data feeds to one or more of the proximate data feed panes. As the object travels through the monitored area, the user tracks (STEP 255) the object and, if necessary, instructs the user module to swap (STEP 260) video feeds such that one of the video feeds from the proximate video feed pane becomes the primary data feed, and a new set of secondary data feeds are assigned (STEP 250) to the proximate video panes. In some cases, the user can send commands to the sensor devices to change (STEP 265) one or more data capture parameters such as camera angle, focus, frame rate, etc. The data can also be provided to the central data analysis module as training data for refining the adjacency probabilities.

0042Referring to <figref idref="f0003">FIG. 3</figref>, the adjacency probabilities can be represented as an <i>nxn</i> adjacency matrix <b>300</b>, where n represents the number of sensor nodes (e.g., cameras in a system consisting entirely of video devices) in the system and the entries in the matrix represent the probability that an object being tracked will transition between the two sensor nodes. In this example, both axes list each camera within a surveillance system, with the horizontal axis <b>305</b> representing the current camera and the vertical axis <b>310</b> representing possible "next" cameras. The entries <b>315</b> in each cell represent the "adjacency probability" that an object will transition from the current camera to the next camera. As a specific example, an object being viewed with camera 1 has an adjacency probability of .25 with camera 5 — i.e., there is a 25% chance that the object will move from the field-of-view of camera 1 to that of camera 5. In some cases, the sum of the probabilities for a camera will be 100% - i.e. all transitions from a camera can be accounted for and estimated. In other cases, the probabilities may not represent all possible transitions, as some cameras will be located at the boundary of a monitored environment and objects will transition into an unmonitored area.

0043In some cases, transitional probabilities can be computer for transitions among multiple (e.g., more than two) cameras. For example, one entry of the adjacency matrix can represent two cameras - i.e. the probability reflects the chance that an object moves from one camera to a second camera then on to a third, resulting in conditional probabilities based on the objects behavior and statistical correlations among each possible transition sequence. In embodiments where cameras have overlapping fields-of-view, the camera-to-camera transition probabilities can sum to greater than one, as transition probabilities would be calculated that represent a transition from more than one camera to a single camera, and/or from a single camera to two cameras (e.g., a person walks from a location covered by a field-of-view of camera A into a location covered by both camera B and C).

0044In some embodiments, one adjacency matrix <b>300</b> can be used to model an entire installation. However, in implementations with large numbers of sensing devices, the addition of sub-regions and implementations where adjacencies vary based on time or day of week, the size and number of the matrices can grow exponentially with the addition of each new sensing device and sub-region. Thus, there are numerous scenarios ― such as large installations, highly distributed systems, and systems that monitor numerous unrelated locations - in which multiple smaller matrices can be used to model object transitions.

0045For example, subsets <b>320</b> of the matrix <b>300</b> can be identified that represent a "cluster" of data that is highly independent from the rest of the matrix <b>300</b> (e.g., there are few, if any, transitions from cameras within the subset to cameras outside the subset). Subset <b>320</b> may represent all of the possible transitions among a subset of cameras, and thus a user responsible for monitoring that site may only be interested in viewing data feeds from that subset, and thus only need the matrix subset <b>320</b>. As a result, intermediate or local processing points in the system do not require the processing or storage resources to handle the entire matrix <b>300</b>. Similarly, large sections of the matrix <b>200</b> can include zero entries which can be removed to further save storage, processing resources, and/or transmission bandwidth. One example is a retail store with multiple floors, where adjacency probabilities for cameras located between floors can be limited to cameras located at escalators, stairs and elevators, thus eliminating the possibility of erroneous correlations among cameras located on different floors of the building.

0046In some embodiments, a central processing, analysis and storage device (described in greater detail below) receives information from sensing devices (and in some cases intermediate data processing and storage devices) within the system and calculates a global adjacency matrix, which can be distributed to intermediate and/or sensor devices for local use. For example, a surveillance system that monitors a shopping mall may have dozens of cameras and sensor devices deployed throughout the mall and parking lot, and because of the high number (and possibly different recording and transmission modalities) of the devices, require multiple intermediate storage devices. The centralized analysis device can receive data streams from each storage device, reformat the data if necessary, and calculate a "mall-wide" matrix that describes transition probabilities across the entire installation. This matrix can then be distributed to individual monitoring stations if to provide the functionality described above.

0047Such methods can be applied on an even larger scale, such as a city-wide adjacency matrix, incorporating thousands of cameras, while still being able to operate using commonly-available computer equipment. For example, using a city's CCTV camera network, police may wish to reconstruct the movements of terrorists before, during and possibly after a terrorist attack such as a bomb detonation in a subway station. Using the techniques described above, individual entries of the matrix can be computed in real-time using only a small amount of information stored at various distributed processing nodes within the system, in some cases at the same device that captures and/or stores the recorded video. In addition, only portions of the matrix would be needed at any one time ― cameras located far from the incident site are not likely to have captured any relevant data. For example, once the authorities know which subway stop where the perpetrators used to enter, the authorities then can limit their initial analysis to sub-networks near that stop. In some embodiments, the sub-networks can be expanded to include surrounding cameras based, for example, on known routes and an assumed speed of travel. The appropriate entries of the global adjacency matrix are computed, and tracking continues until the perpetrators reach a boundary of the sub-network, at which point, new adjacencies are computed and tracking continues.

0048Using such methods, the entire matrix does not need to be ― although in some cases it may be ― stored (or even computed) any one time. Only the identification of the appropriate sub-matrices is calculated in real time. In some embodiments, a sub-matrices exist a priori, and thus the entries would not need to be recalculated. In some embodiments, the matrix information can be compressed and/or encrypted to aid in transmission and storage and to enhance security of the system.

0049Similarly, a surveillance system that monitors numerous unrelated and/or distant locations may calculate a matrix for each location and distribute each matrix to the associated location. Expanding on the example of a shopping mall above, a security service may be hired to monitor multiple malls from a remote location ― i.e., the users monitoring the video may not be physically located at any of the monitored locations. In such a case, the transition probability of an object moving immediately from the field-of-view of a camera at a first mall that of a second camera at a second mall, perhaps thousands of miles away, is virtually zero. As a result, separate adjacency matrices can be calculated for each mall and distributed to the mall's surveillance office, where local users can view the data feeds and take any necessary action. Periodic updates to the matrices can include updated transition probabilities based on new stores or displays, installations of new cameras, or other such events. Multiple matrices (e.g., matrices containing transition probabilities for different days and/or times as described above) can be distributed to a particular location.

0050In some embodiments, an adjacency matrix can include another matrix identifier as a possible transition destination. For example, an amusement park will typically have multiple cameras monitoring the park and the parking lot. However, the transition probability from any one camera within the park to any one camera within the parking lot is likely to be low, as there are generally only one or two pathways from the parking lot to the park. While there is little need to calculate transition probabilities among all cameras, it is still necessary to be able to track individuals as they move about the entire property. Instead of listing every camera in one matrix, therefore, two separate matrices can be derived. A first matrix for the park, for example, lists each camera from the park and one entry for the parking lot matrix. Similarly, a parking lot matrix lists each camera from the parking lot and an entry for the park matrix. Because of the small number of paths linking the park and the lot, it is likely that a relatively small subset of cameras will have significant transitional probabilities between the matrices. As an individual moves into the view of a park camera that is adjacent to a lot camera, the lot matrix can then be used to track the individual through the parking lot.

<i><u>Movie Capture</u></i>

0051As events or subjects are captured by the sensing devices, video clips from the data feeds from the devices can be compiled into a multi-camera movie for storage, distribution, and later use as evidence. Referring to <figref idref="f0004">FIG. 4</figref>, an application screen <b>400</b> for capturing video surveillance data includes a video clip organizer <b>405</b>, a main video viewing pane 410, a series of control buttons <b>415</b>, and timeline object <b>420</b>. In some embodiments, the proximate video panes of <figref idref="f0001">FIG. 1</figref> can also be included.

0052The system provides a variety controls for the playback of previously recorded and/or live video and the selection of the primary video data feed during movie compilation. Much like a VCR, the system includes controls <b>415</b> for starting, pausing and stopping video playback. In some embodiments, the system may include forward and backward scan and/or skip features, allowing users to quickly navigate through the video. The video playback rate may be altered, ranging from slow motion (less than 1x playback speed) to fast-forward speed, such as 32x real-time speed. Controls are also provided for jumping forward or backward in the video, either in predefined increments (e.g., 30 seconds) by pushing a button or in arbitrary time amounts by entering a time or date. The primary video data feed can be changed at any time by selecting a new feed from one of the secondary video data feeds or by directly selecting a new video feed (e.g., by camera number or location). In some embodiments, the timeline object <b>420</b> facilitates editing the movie at specific start and end times of clips and provides fine-grained, frame-accurate control over the viewing and compilation of each video clip and the resulting movie.

0053As described above, as a tracked object <b>425</b> transitions from a primary camera to an adjacent camera (or sub-region to sub-region), the video data feed from the adjacent camera becomes the new primary video data feed (either automatically, or in some cases, in response to user selection). Upon transition to a new video feed, the recording of the first feed is stopped, and a first video clip is saved. Recording resumes using the new primary data feed, and a second clip is created using the video data feed from the new camera. The proximate video display panes are then populated with a new set of video data feeds as described above. Once the incident of interest is over or that a sufficient amount of video has been captured, the user stops the recording. Each of the various clips can then be listed in the clip organizer list <b>405</b> and concatenated into one movie. Because the system presented relevant cameras to the user for selection as the subject traveled through the camera views, the amount of time that the subject is out of view is minimized and the resulting movie provides a complete and accurate history of the event.

0054As an example of the movie creation process, consider the case of a suspicious-looking person in a retail store. The system operator first identifies the person and initiates the movie making process by clicking a "Start Movie" button, which starts compiling the first video clip. As the person walks around the store, he will transition from one surveillance camera to another. After he leaves the first camera, the system operator examines the video data feeds shown in the secondary panes, which, because of the pre-calculated adjacency probabilities, are presented such that the most likely next camera is readily available. When the suspect appears on one of the secondary feeds, the system operator selects that feed as the new primary video data feed. At this point, the first video clip is ended and stored, and the system initiates a second clip. A camera identifier, start time and end time of the first video clip are stored in the video clip organizer <b>405</b> associated with the current movie. The above process of selecting secondary video data feeds continues until the system operator has collected enough video of the suspicious person to complete his investigation. At this point, the system operator selects an "End Movie" button, and the movie clip list is saved for later use. The movie can be exported to a removable media device (e.g., CD-R or DVD-R), shared with other investigators, and/or used as training data for the current or subsequent surveillance systems.

0055Once the real-time or post-event movie is complete, the user can annotate the movie (or portions thereof) using voice, text, date, timestamp, or other data. Referring to <figref idref="f0005">FIG. 5</figref>, a movie editing screen <b>500</b> facilitates editing of the movie. Annotations such as titles <b>505</b> can be associated to the entire movie, still pictures added <b>510</b>, and annotations <b>515</b> about specific incidents (e.g., "subject placing camera in left jacket pocket") can be associated with individual clips. Camera names <b>520</b> can be included in the annotation, coupled with specific date and time windows <b>525</b> for each clip. An "edit" link 530 allows the user to edit some or all of the annotations as desired.

<u>Architecture</u>

0056Referring to <figref idref="f0006">FIG. 6</figref>, the topology of a video surveillance system using the techniques described above can be organized into multiple logical layers consisting of many edge nodes <b>605a</b> through <b>605e</b> (generally, <b>605</b>), a smaller number of intermediate nodes <b>610a</b> and <b>610b</b> (generally, <b>610</b>), and a single central node <b>615</b> for system-wide data review and analysis. Each node can be assigned one or more tasks in the surveillance system, such as sensing, processing, storage, input, user interaction, and/or display of data. In some cases, a single node may perform more than one task (e.g., a camera may include processing capabilities and data storage as well as performing image sensing).

0057The edge nodes <b>605</b> generally correspond to cameras (or other sensors) and the intermediate nodes <b>610</b> correspond to recording devices (VCRs or DVRs) that provide data to the centralized data storage and analysis node <b>615</b>. In such a scenario, the intermediate nodes <b>610</b> can perform both the processing (video encoding) and storage functions. In an IP-based surveillance system, the camera edge nodes <b>605</b> can perform both sensing functions and processing (video encoding) functions, while the intermediate nodes <b>610</b> may only perform the video storage functions. An additional layer of user nodes <b>620a</b> and <b>620b</b> (generally, <b>620</b>) may be added for user display and input, which are typically implemented using a computer terminal or web site <b>620b</b>. For bandwidth reasons, the cameras and storage devices typically communicate over a local area network (LAN), while display and input devices can communicate over either a LAN or wide area network (WAN).

0058Examples of sensing nodes <b>605</b> include analog cameras, digital cameras (e.g., IP cameras, FireWire cameras, USB cameras, high definition cameras, etc.), motion detectors, heat detectors, door sensors, point-of-sale terminals, radio frequency identification (RFID) sensors, proximity card sensors, biometric sensors, as well as other similar devices. Intermediate nodes <b>610</b> can include processing devices such as video switches, distribution amplifiers, matrix switchers, quad processors, network video encoders, VCRs, DVRs, RAID arrays, USB hard drives, optical disk recorders, flash storage devices, image analysis devices, general purpose computers, video enhancement devices, de-interlacers, scalers, and other video or data processing and storage elements. The intermediate nodes <b>610</b> can be used for both storage of video data as captured by the sensing nodes <b>605</b> as well as data derived from the sensor data using, for example, other intermediate nodes <b>610</b> having processing and analysis capabilities. The user nodes <b>620</b> facilitate the interaction with the surveillance system and may include pan-tilt-zoom (PTZ) camera controllers, security consoles, computer terminals, keyboards, mice, jog/shuttle controllers, touch screen interfaces, PDAs, as well as displays for presenting video and data to users of the system such as video monitors, CRT displays, flat panel screens, computer terminals, PDAs, and others.

0059Sensor nodes <b>605</b> such as cameras can provide signals in various analog and/or digital formats, including, as examples only, Nation Television System Committee (NTSC), Phase Alternating Line (PAL), and Sequential Color with Memory (SECAM), uncompressed digital signals using DVI or HDMI connections, and/or compressed digital signals based on a common codec format (e.g., MPEG, MPEG2, MPEG4, or H.264). The signals can be transmitted over a LAN <b>625</b> and/or a WAN <b>630</b> (e.g., T1, T3, 56kb, X.25), broadband connections (ISDN, Frame Relay, ATM), wireless links (802.11, Bluetooth, etc.), and so on. In some embodiments, the video signals may be encrypted using, for example, trusted key-pair encryption.

0060By adding computational resources to different elements (nodes) within the system (e.g., cameras, controllers, recording devices, consoles, etc.), the functions of the system can be performed in a distributed fashion, allowing more flexible system topologies. By including processing resources at each camera location (or some subset thereof), certain unwanted or redundant data facilitates the identification and filtering prior to the data being sent to intermediate or central processing locations, thus reducing bandwidth and data storage requirements. In addition, different locations may apply different rules for identifying unwanted data, and by placing processing resources capable of implementing such rules at the nodes closest to those locations (e.g., cameras monitoring a specific property having unique characteristics), any analysis done on downstream nodes includes less "noise."

0061Intelligent video analysis and computer aided-tracking systems such as those described herein provide additional functionality and flexibility to this architecture. Examples of such intelligent video surveillance system that performs processing functions (i.e., video encoding and single-camera visual analysis) and video storage on intermediate nodes are described in currently co-pending, commonly-owned <patcit id="pcit0004" dnum="US706850A" dnum-type="L"><text>U.S. Patent Application Serial No. 10/706,850</text></patcit>, entitled "Method And System For Tracking And Behavioral Monitoring Of Multiple Objects Moving Through Multiple Fields-Of-View," the entire disclosure of which is incorporated by reference herein. In such examples, a central node provides multi-camera visual analysis features as well as additional storage of raw video data and/or video meta-data and associated indices. In some embodiments, video encoding may be performed at the camera edge nodes and video storage at a central node (e.g., a large RAID array). Another alternative moves both video encoding and single-camera visual analysis to the camera edge nodes. Other configurations are also possible, including storing information on the camera itself.

0062<figref idref="f0007">FIG. 7</figref> further illustrates the user node <b>620</b> and central analysis and storage node <b>615</b> of the video surveillance system of <figref idref="f0006">FIG. 6</figref>. In some embodiments, the user node <b>620</b> is implemented as software running on a personal computer (e.g., a PC with an INTEL processor or an APPLE MACINTOSH) capable of running such operating systems as the MICROSOFT WINDOWS family of operating systems from Microsoft Corporation of Redmond, Washington, the MACINTOSH operating system from Apple Computer of Cupertino, California, and various varieties of Unix, such as SUN SOLARIS from SUN MICROSYSTEMS, and GNU/Linux from RED HAT, INC. of Durham, North Carolina (and others). The user node <b>620</b> can also be implemented on such hardware as a smart or dumb terminal, network computer, wireless device, wireless telephone, information appliance, workstation, minicomputer, mainframe computer, or other computing device that operates as a general purpose computer, or a special purpose hardware device used solely for serving as a terminal <b>620</b> in the surveillance system.

0063The user node <b>620</b> includes a client application <b>715</b> that includes a user interface module <b>720</b> for rendering and presenting the application screens, and a camera selection module <b>725</b> for implementing the identification and presentation of video data feeds and movie capture functionality as described above. The user node <b>620</b> communicates with the sensor nodes and intermediate nodes (not shown) and the central analysis and storage module <b>615</b> over the network <b>625</b> and <b>630</b>.

0064In one embodiment, the central analysis and storage node <b>615</b> includes a video storage module <b>730</b> for storing video captured at the sensor nodes, and a data analysis module <b>735</b> for determining adjacency probabilities as well as other functions such as storing and applying adjacency rules, calculating transition probabilities, and other functions. In some embodiments, the central analysis and storage node <b>615</b> determines which transition matrices (or portions thereof) are distributed to intermediate and/or sensor nodes, if, as described above, such nodes have the processing and storage capabilities described herein. The central analysis and storage node <b>615</b> is preferably implemented on one or more server class computers that have sufficient memory, data storage, and processing power and that run a server class operating system (e.g., SUN Solaris, GNU/Linux, and the MICROSOFT WINDOWS family of operating systems). Other types of system hardware and software than that described herein may also be used, depending on the capacity of the device and the number of nodes being supported by the system. For example, the server may be part of a logical group of one or more servers such as a server farm or server network. As another example, multiple servers may be associated or connected with each other, or multiple servers operating independently, but with shared data. In a further embodiment and as is typical in large-scale systems, application software for the surveillance system may be implemented in components, with different components running on different server computers, on the same server, or some combination.

0065In some embodiments, the video monitoring, object tracking and movie capture functionality of the present invention can be implemented in hardware or software, or a combination of both on a general-purpose computer. In addition, such a program may set aside portions of a computer's RAM to provide control logic that affects one or more of the data feed encoding, data filtering, data storage, adjacency calculation, and user interactions. In such an embodiment, the program may be written in any one of a number of high-level languages, such as FORTRAN, PASCAL, C, C<+>*, C<#>, Java, TcI, or BASIC. Further, the program can be written in a script, macro, or functionality embedded in commercially available software, such as EXCEL or VISUAL BASIC. Additionally, the software could be implemented in an assembly language directed to a microprocessor resident on a computer. For example, the software can be implemented in Intel 80x86 assembly language if it is configured to run on an IBM PC or PC clone. The software may be embedded on an article of manufacture including, but not limited to, "computer-readable program means" such as a floppy disk, a hard disk, an optical disk, a magnetic tape, a PROM, an EPROM, or CD-ROM.

0066While the invention has been particularly shown and described with reference to specific embodiments, it should be understood by those skilled in the area that various changes in form and detail may be made therein without departing from the scope of the invention as defined by the appended claims. The scope of the invention is thus indicated by the appended claims and all changes which come within the meaning and range of equivalency of the claims are therefore intended to be embraced.