Video-based vehicle detection and tracking using spatio-temporal maps

• US 8,358,808 B2
• Filed: 01/10/2011
• Issued: 01/22/2013
• Est. Priority Date: 01/08/2010
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Malinovskiy, Yegor, Wang, Yinhai, Wu, Yao-Jan
• Primary Examiner(s): Azarian, Seyed
• Application Number:
  US12/987,854
• Publication Number:
  US 20110170744A1
• Time in Patent Office: 743 Days
• Field of Search: 382/100, 382103-107, 382/155, 382/162, 382/168, 382/173, 382/181, 382184-194, 382/209, 382/232, 382/254, 382/274, 382/276, 382285-291, 382/305, 382/312, 348/155, 340/903, 340/933, 701/301
• US Class Current: 382/103
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69
• CPC Class Codes: G06V 20/54 of traffic, e.g. cars on the road, trains or boats

Abstract

Systems and methods for detecting and tracking objects, such as motor vehicles, within video data. The systems and method analyze video data, for example, to count objects, determine object speeds, and track the path of objects without relying on the detection and identification of background data within the captured video data. The detection system uses one or more scan lines to generate a spatio-temporal map. A spatio-temporal map is a time progression of a slice of video data representing a history of pixel data corresponding to a scan line. The detection system detects objects in the video data based on intersections of lines within the spatio-temporal map. Once the detection system has detected an object, the detection system may record the detection for counting purposes, display an indication of the object in association with the video data, determine the speed of the object, etc.

Claims

1. A method, performed by a computer having a memory and a processor, for locating objects within video data, the method comprising:

receiving a selection of a set of pixels of the video data;

for each of a plurality of frames of the video data,

capturing pixel data for the selected set of pixels, and

adding the captured pixel data to image data associated with the selected set of pixels, wherein the image data comprises a spatio-temporal map representative of the selected set of pixels over a period of time;

with the processor, detecting strand lines within the image data associated with the selected set of pixels;

clustering the strand lines detected within the image data associated with the selected set of pixels; and

detecting objects based on the clustered strand lines, wherein each cluster of strand lines corresponds to a different object within the video data.

2. The method of claim 1 wherein the clustering the strand lines comprises:

detecting intersections between the strand lines detected within the image data.

3. The method of claim 2 wherein the clustering the strand lines comprises:

creating a node for each detected strand line within the image data so that each detected strand line is associated with a node;

for each detected strand line,

identifying an intersection between the detected strand line and another detected strand line, wherein the intersection occurs within the image data or when the detected strand lines are extended beyond the image data, and

creating an edge between the node associated with the detected strand line and the node associated with the other detected strand line; and

identifying groups of connected nodes, each group corresponding to a different cluster.

4. The method of claim 1, further comprising:

after detecting an object, displaying an indication of the detected object in association with the video data.

5. The method of claim 1, further comprising:

receiving a selection of at least four points in the video data; and

for each of the at least four points in the video data, mapping the point in the video data to a point on a rectangle within an image plane,

wherein the set of pixels is selected from a region defined by the at least four points in the video data and mapped to the rectangle within the image plane.

6. The method of claim 5, further comprising:

generating a transformation matrix based on the mappings between the at least four points in the video data and points on the rectangle within the image plane; and

applying the generated transformation matrix to frames of the video data.

7. The method of claim 1 wherein the set of pixels is a first set of pixels and wherein the method further comprises:

receiving a selection of a second set of pixels.

8. The method of claim 1 wherein the selected set of pixels is a line of pixels having a width of one pixel.

9. The method of claim 1 wherein the objects are vehicles and the video data is captured by a traffic surveillance camera.

10. The method of claim 9 wherein the selected set of pixels is associated with a lane of vehicular traffic.

11. The method of claim 10 wherein the selected set of pixels is a line of pixels at least approximately parallel to a vehicle'"'"'s travel direction.

12. A computer-readable storage medium storing instructions that, if executed by a computer having a memory and a processor, cause the computer to perform operations comprising:

for a first set of pixels of the video data, capturing pixel data corresponding to the first set of pixels from each of a plurality of frames of the video data;

generating a first spatio-temporal map based on the captured pixel data corresponding to the first set of pixels;

for a second set of pixels of the video data, capturing pixel data corresponding to the second set of pixels from each of the plurality of frames of the video data, wherein the first set of pixels is different from the second set of pixels and wherein the pixel data corresponding to the first set of pixels is captured concurrently with the pixel data corresponding to the second set of pixels;

generating a second spatio-temporal map based on the captured pixel data corresponding to the second set of pixels; and

for each generated spatio-temporal map,

detecting segments of strand lines within the spatio-temporal map, each segment corresponding to a different strand line, and

grouping strand lines based at least in part on intersections between the strand lines, each group of strand lines corresponding to a different object.

13. The computer-readable storage medium of claim 12 wherein the received selection of pixels is a one-pixel wide line of pixels.

14. The computer-readable storage medium of claim 12, wherein the operations further comprise:

displaying an indication of a detected object in association with the video data.

15. The computer-readable storage medium of claim 14 wherein the displayed indication represents the position of the detected object in each of a plurality of frames of the video data.

16. The computer-readable storage medium of claim 14 wherein the displayed indication includes an indication of the speed of the detected object.

17. A system, having a memory and a processor, for detecting objects in video data, the system comprising:

a component configured to, for a selected set of pixels of the video data, generate a spatio-temporal map based on pixel data captured from chronologically-ordered frames of the video data;

a component configured to detect at least portions of strand lines within the generated spatio-temporal map;

a component configured to create a node for each of the strand lines;

a component configured to, for each strand line,

identify an intersection between the strand line and another strand line, and

create an edge between the node associated with the strand line and the node associated with the other strand line;

a component configured to identify groups of connected nodes;

a component configured to identify strands based on the identified groups of connected nodes, each strand corresponding to a plurality of strand lines; and

a component configured to detect objects based on the identified strands.

18. The system of claim 17, further comprising:

a component configured to calculate a first average strand line for a first strand based on the strand lines associated with the first strand.

19. The system of claim 17, further comprising:

a component configured to calculate the position of an object associated with the first strand in each of a plurality of frames of the video data based on the first average strand line.

20. The system of claim 17, further comprising:

a component configured to increment an object counter each time a different object is detected.

21. A computer-readable storage medium storing instructions that, if executed by a computer having a memory and a processor, cause the computer to perform operations for detecting objects within image data comprising a plurality of frames, the operations comprising:

receiving a scan line;

for each of a plurality of frames of the image data,

capturing pixel data corresponding to the scan line, and

adding the captured pixel data to a spatio-temporal map associated with the scan line;

identifying strand lines within the spatio-temporal map;

extending the identified strand lines beyond the spatio-temporal map;

creating a node for each extended strand line;

identifying intersections between the extended strand lines;

identifying groups of strand lines based on the identified intersections; and

detecting objects based on the identified groups of strand lines.

22. The computer-readable storage medium of claim 21 wherein the identifying groups of strand lines comprises:

for each extended strand line,

identifying an intersection between the extended strand line and another extended strand line, and

creating an edge between the node associated with the extended strand line and the node associated with the other extended strand line; and

identifying groups of connected nodes, each group corresponding to a different strand.

23. The computer-readable storage medium of claim 21, wherein the operations further comprise:

calculating the trajectory of a first object in the video data; and

displaying an indication of the first object in association with the video data.

24. The computer-readable storage medium of claim 21, wherein identifying an intersection for a first extended strand line comprises:

traversing the first extended strand line in one direction until an intersection with another extended strand line is detected.