Anomalous pattern discovery

• US 8,660,368 B2
• Filed: 03/16/2011
• Issued: 02/25/2014
• Est. Priority Date: 03/16/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Datta, Ankur, Paluri, Balamanohar, Pankanti, Sharathchandra U., Zhai, Yun
• Primary Examiner(s): Bali, Vikkram
• Assistant Examiner(s): CHEN, XUEMEI G
• Application Number:
  US13/049,032
• Publication Number:
  US 20120237081A1
• Time in Patent Office: 1,077 Days
• Field of Search: 345/690, 345/723, 348/77, 381/98, 382/103, 382/104, 382/155, 382/159, 382/160, 382/173
• US Class Current: 382/218
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 20/53 Recognition of crowd images, e.g. recognition of crowd congestion
• CPC Class Codes: G06V 20/54 of traffic, e.g. cars on the road, trains or boats

Abstract

A trajectory of movement of an object is tracked in a video data image field that is partitioned into a plurality of different grids. Global image features from video data relative to the trajectory are extracted and compared to a learned trajectory model to generate a global anomaly detection confidence decision value as a function of fitting to the learned trajectory model. Local image features are also extracted for each of the image field grids that include object trajectory, which are compared to learned feature models for the grids to generate local anomaly detection confidence decisions for each grid as a function of fitting to the learned feature models for the grids. The global anomaly detection confidence decision value and the local anomaly detection confidence decision values for the grids are into a fused anomaly decision with respect to the tracked object.

Claims

1. A method for anomalous pattern discovery, the method comprising:

tracking movement of an input object in an image field of input video data to determine a trajectory of the input object, wherein the input video data image field is partitioned into a plurality of different grids defining a matrix and the input object trajectory passes through a plurality of input object trajectory grids;

extracting global image features relative to the trajectory and local image features from each of the input object trajectory grids of the image field of the input video data;

generating an anomaly distribution detection confidence decision value for each of the input object trajectory grids as a function of fitting the extracted local image features to a learned feature model representing normal pattern distributions or abnormal pattern distributions that are defined for the grids;

generating a trajectory similarity value for the input object trajectory as a function of similarity of a parameterized representation of the extracted global image features to a learned trajectory model representing a normal trajectory or an abnormal trajectory;

finding a normalized sum of the generated anomaly distribution detection confidence decision values for the grids that include the tracked object trajectory; and

determining a fused anomaly decision value for the tracked object as a dynamic weighted combination of a product of the normalized sum and a local coefficient and a product of the trajectory similarity value and a global coefficient, wherein the local and global coefficients are dynamically determined from values that are inversely correlated to variances of the learned feature model and the learned trajectory model, and wherein the local and global coefficients sum to one.

2. The method of claim 1, further comprising:

segmenting an image field of training video data into a plurality of grids defining a matrix;

tracking a training object within the training video image field through a plurality of the grids over time to determine a training object trajectory;

extracting global training video image features relative to the training object trajectory and local training video image features from each grid of the segmented training video data image field over time;

defining dominant distributions of the extracted local training video image features over time within each of the grids as the learned feature model representing the normal pattern distributions, or rare distributions of the extracted local training video image features over time within each of the grids as the learned feature model representing the abnormal pattern distributions; and

building the learned trajectory model representing the normal trajectory or the abnormal trajectory.

3. The method of claim 1, wherein at least one of the anomaly distribution detection confidence decision values and the trajectory similarity value is binary values indicating normal or anomaly.

4. The method of claim 1, wherein the plurality of different grids is a segmentation of the image field into a matrix of grids in a spatiotemporal domain.

5. The method of claim 1, wherein the step of generating the trajectory similarity value for the input object trajectory as the function of the similarity of the parameterized representation of the extracted global image features to the learned trajectory model representing the normal trajectory or the abnormal trajectory comprises:

separating the tracked object trajectory into a plurality of tracked object trajectory tracks of uniform lengths; and

modeling the tracked object trajectory tracks with second-order polynomial coefficients.

6. The method of claim 2, wherein the step of building the learned trajectory model comprises:

separating the training object trajectory in the training video input into a plurality of training video tracks of uniform lengths;

modeling the training video tracks with second-order polynomial coefficients; and

building the learned trajectory model as a clustered grouping of the second-order polynomial coefficients modeled from the training video tracks.

7. The method of claim 2, further comprising:

building the learned trajectory model from an ordered polynomial coefficient set representing an entirety of the training object trajectory tracked in the training video input; and

wherein the extracting the global training video image features relative to the training object trajectory comprises representing an entirety of the tracked training object trajectory with another ordered polynomial coefficient set.

8. The method of claim 2, further comprising:

building the learned trajectory model from spatiotemporal interest points on the training object trajectory tracked in the training video input; and

wherein the extracting the global training video image features relative to the training object trajectory comprises representing the tracked training object trajectory with spatiotemporal interest points on the tracked training object trajectory.

9. The method of claim 2, further comprising:

updating at least one of the learned feature model representing the normal pattern distributions or the abnormal pattern distributions, and the learned trajectory model representing the normal trajectory or the abnormal trajectory as a function of the fused anomaly decision value.

10. The method of claim 1, further comprising:

integrating computer readable program code into a computer system comprising a processor, a computer readable memory and a computer readable storage medium, wherein the computer readable program code is embodied on the computer readable storage medium and comprises instructions that, when executed by the processor via the computer readable memory, cause the processor to perform the steps of;

tracking the movement of the input object in the image field of input video data to determine the trajectory of the input object;

extracting the global image features relative to the trajectory and local image features from each of the input object trajectory grids of the image field of the input video data;

generating the anomaly distribution detection confidence decision values for each of the input object trajectory grids as the function of fitting the extracted local image features to the learned feature model representing the normal pattern distributions or the abnormal pattern distributions defined for the grids;

generating the trajectory similarity value for the input object trajectory as the function of similarity of the parameterized representation of the extracted global image features to the learned trajectory model representing the normal trajectory or the abnormal trajectory;

finding the normalized sum of the generated anomaly distribution detection confidence decision values for the grids that include the tracked object trajectory; and

determining the fused anomaly decision value for the tracked object as the dynamic weighted combination of the product of the normalized sum and the local coefficient and the product of the trajectory similarity value and the global coefficient.

11. A system, comprising:

a processor, a computer readable memory and a computer readable storage medium;

wherein the processor, when executing program instructions stored on the computer-readable storage medium via the computer readable memory;

tracks movement of an input object in an image field of input video data to determine a trajectory of the input object, wherein the input video data image field is partitioned into a plurality of different grids defining a matrix and the input object trajectory passes through a plurality of input object trajectory grids;

extracts global image features relative to the trajectory and local image features from each of the input object trajectory grids of the image field of the input video data;

generates an anomaly distribution detection confidence decision values for each of the input object trajectory grids as a function of fitting the extracted local image features to a learned feature model representing normal pattern distributions or abnormal pattern distributions that are defined for the grids;

generates a trajectory similarity value for the input object trajectory as a function of similarity of a parameterized representation of the extracted global image features to a learned trajectory model representing a normal trajectory or an abnormal trajectory;

finds a normalized sum of the generated anomaly distribution detection confidence decision values for the grids that include the tracked object trajectory; and

determines a fused anomaly decision value for the tracked object as a dynamic weighted combination of a product of the normalized sum and a local coefficient and a product of the trajectory similarity value and a global coefficient; and

wherein the local and global coefficients are dynamically determined from values that are inversely correlated to variances of the learned feature model and the learned trajectory model, and wherein the local and global coefficients sum to one.

12. The system of claim 11, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further:

generates the trajectory similarity value for the input object trajectory as the function of similarity of the parameterized representation of the extracted global image features to a learned trajectory model representing the normal trajectory or the abnormal trajectory by;

separating the tracked object trajectory into a plurality of tracked object trajectory tracks of uniform lengths; and

modeling the tracked object trajectory tracks with second-order polynomial coefficients.

13. The system of claim 11, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further:

segments an image field of training video data into a plurality of grids defining a matrix;

tracks a training object within the training video image field through a plurality of the grids over time to determine a training object trajectory;

extracts global training video image features relative to the training object trajectory and local training video image features from each grid of the segmented training video data image field over time;

defines dominant distributions of the extracted local training video image features over time within each of the grids as the learned feature model representing the normal pattern distributions, or rare distributions of the extracted local training video image features over time within each of the grids as the learned feature model representing the abnormal pattern distributions; and

builds the learned trajectory model representing the normal trajectory or the abnormal trajectory.

14. The system of claim 13, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further builds the learned trajectory model by:

separating the training object trajectory in the training video input into a plurality of training video tracks of uniform lengths;

modeling the training video tracks with second-order polynomial coefficients; and

building the learned trajectory model as a clustered grouping of the second-order polynomial coefficients modeled from the training video tracks.

15. The system of claim 13, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further:

builds the learned normal trajectory model from an ordered polynomial coefficient set representing an entirety of the training object trajectory tracked in the training video input; and

wherein the extracting the global training video features relative to the training object trajectory comprises representing an entirety of the tracked training object trajectory with another ordered polynomial coefficient set.

16. The system of claim 13, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further updates at least one of the learned feature model representing the normal pattern distributions or the abnormal pattern distributions, and the learned trajectory model representing the normal trajectory or the abnormal trajectory, as a function of the fused anomaly decision value.

17. An article of manufacture for anomalous pattern discovery, the article of manufacture comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising instructions that, when executed by a processor, cause the processor to;

track movement of an input object in an image field of input video data to determine a trajectory of the input object, wherein the input video data image field is partitioned into a plurality of different grids defining a matrix and the input object trajectory passes through a plurality of input object trajectory grids;

extract global image features relative to the trajectory and local image features from each of the input object trajectory grids of the image field of the input video data;

generate an anomaly distribution detection confidence decision value for each of the input object trajectory grids as a function of fitting the extracted local image features to a learned feature model representing normal pattern distributions or abnormal pattern distributions that are defined for the grids;

generate a trajectory similarity value for the input object trajectory as a function of similarity of a parameterized representation of the extracted global image features to a learned trajectory model representing a normal trajectory or an abnormal trajectory;

find a normalized sum of the generated anomaly distribution detection confidence decision values for the grids that include the tracked object trajectory; and

determine a fused anomaly decision value for the tracked object as a dynamic weighted combination of a product of the normalized sum and a local coefficient and a product of the trajectory similarity value and a global coefficient; and

wherein the local and global coefficients are dynamically determined from values that are inversely correlated to variances of the learned feature model and the learned trajectory model, and wherein the local and global coefficients sum to one.

18. The article of manufacture of claim 17, wherein the computer readable program code instructions, when executed by the processor, further cause the processor to:

generate the trajectory similarity value for the input object trajectory as the function of the similarity of the parameterized representation of the extracted global image features to the learned trajectory model representing the normal trajectory or the abnormal trajectory by;

separating the tracked object trajectory into a plurality of tracked object trajectory tracks of uniform lengths; and

modeling the tracked object trajectory tracks with second-order polynomial coefficients.

19. The article of manufacture of claim 17, wherein the computer readable program code instructions, when executed by the processor, further cause the processor to:

segment an image field of training video data into a plurality of grids defining a matrix;

track a training object within the training video image field through a plurality of the grids over time to determine a training object trajectory;

extract global training video image features relative to the training object trajectory and local training video image features from each grid of the segmented training video data image field over time;

define dominant distributions of the extracted local training video image features over time within each of the grids as the learned feature model representing the normal pattern distributions, or rare distributions of the extracted local training video image features over time within each of the grids as the learned feature model representing the abnormal pattern distributions; and

build the learned trajectory model representing the normal trajectory or the abnormal trajectory.

20. The article of manufacture of claim 19, wherein the computer readable program code instructions, when executed by the processor, further cause the processor to build the learned trajectory model by:

separating the training object trajectory in the training video input into a plurality of training video tracks of uniform lengths;

modeling the training video tracks with second-order polynomial coefficients; and

building the learned trajectory model as a clustered grouping of the second-order polynomial coefficients modeled from the training video tracks.

21. The article of manufacture of claim 19, wherein the computer readable program code instructions, when executed by the processor, further cause the processor to build the learned trajectory model from an ordered polynomial coefficient set representing an entirety of the training object trajectory tracked in the training video input;

and

wherein the extracting the global training video image features relative to the training object trajectory comprises representing an entirety of the tracked training object trajectory with another ordered polynomial coefficient set.

22. The article of manufacture of claim 19, wherein the computer readable program code instructions, when executed by the processor, further cause the processor to update at least one of the learned feature model representing the normal pattern distributions or the abnormal pattern distributions, and the learned trajectory model representing the normal trajectory or the abnormal trajectory, as a function of the fused anomaly decision value.