Method of tracking an object in a video stream

• US 8,224,023 B2
• Filed: 07/21/2006
• Issued: 07/17/2012
• Est. Priority Date: 10/31/2005
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Greig, Darryl
• Primary Examiner(s): Park, Chan S
• Assistant Examiner(s): YENTRAPATI, AVINASH
• Application Number:
  US11/490,156
• Publication Number:
  US 20070097112A1
• Time in Patent Office: 2,188 Days
• Field of Search: None
• US Class Current: 382/103
• CPC Class Codes: G01C 11/04 Interpretation of pictures
• CPC Class Codes: G06T 7/238 using non-full search, e.g. three-step search

Abstract

A method of tracking an object such as a face in a video stream comprises running an object detector at a plurality of locations on a first frame, defining a coarse grid. This is repeated for second and subsequent frames, with the grid slightly offset each time so that, ultimately, all of the points on a fine grid are covered but in several passes. When an object such as a face is located on one frame, positional and/or scale information is propagated to the next frame to assist in the tracking of that object onto the next frame.

Claims

1. A method of tracking an object in a video stream comprising a plurality of video frames, the method comprising:

(a) running an object detector, on a computer, at a plurality of sampling locations, the locations defining a first grid spaced across a first video frame, and recording a hit, to electronic storage, at each location where an object of interest is found; and

(b) running the object detector, on the computer, at a further plurality of sampling locations defining a second grid spaced across a succeeding second video frame, the second grid being offset from the first grid, wherein larger points, which have a size of at least 2×

2 points of a fine grained grid, cover the entire first grid and the entire second grid and wherein each of the larger points has one of the sampling locations of the first grid and one of the further sampling locations of the second grid and wherein each of the further sampling locations is offset with respect to a corresponding sampling location of the first grid for a respective larger point and simultaneously running the detector employing parallel processing, on the computer, in addition at one or more further locations on the second frame derived from each location on the first frame at which a hit was recorded.

2. A method of tracking an object in a video stream as claimed in claim 1 in which the further locations on the second frame are the same as the locations on the first frame at which the hit was recorded.

3. A method claimed as in claim 1 in which the further locations on the second frame are derived by carrying out a neighbourhood search around the locations on the first frame at which the hit was recorded.

4. A method claimed as in claim 1 in which the further locations are derived by predicting the movement of the or each object located on the first frame to one or more estimated locations in the second frame, the estimated locations being selected as the further locations.

5. A method claimed as in claim 1 in which the further locations are derived by predicting the movement of the or each object located on the first frame to one or more estimated location in the second frame, the further locations being chosen by carrying out a neighbourhood search around the estimated locations.

6. A method as claimed in claim 1 including repeating step (b) for a sequence of subsequent frames, each respective sampling grid being offset from the grid used on the preceding frame.

7. A method as claimed in claim 1 in which each time the object detector runs it attempts to find the object of interest at a plurality of different scales.

8. A method as claimed in claim 1 for operating on a real-time video stream, and in which the object detector operates in sub-real-time.

9. A method as claimed in claim 1 in which the object detector is a face detector.

10. Apparatus for tracking an object in a video stream comprising a plurality of video frames, the apparatus including an object detector comprising:

a computer that is programmed for

(a) running an object detector at a plurality of sampling locations, the locations defining a first grid spaced across a first video frame, and recording a hit, to electronic storage, at each location where an object of interest is found; and

(b) running the object detector at a further plurality of sampling locations defining a second grid spaced across a succeeding second video frame, the second grid being offset from the first grid, wherein larger points, which have a size of at least 2×

2 points of a fine grained grid, cover the entire first grid and the entire second grid and wherein each of the larger points has one of the sampling locations of the first grid and one of the further sampling locations of the second grid and wherein each of the further sampling locations is offset with respect to a corresponding sampling location of the first grid for a respective larger point and simultaneously running the detector employing parallel processing in addition at one or more further locations on the second frame derived from each location on the first frame at which a hit was recorded.

11. Apparatus as claimed in claim 10 in which the further locations on the second frame are the same as the locations on the first frame at which the hit was recorded.

12. Apparatus as claimed in claim 10 in which the further locations on the second frame are derived by carrying out a neighbourhood search around the locations on the first frame at which the hit was recorded.

13. Apparatus as claimed in claim 10 in which the further locations are derived by predicting the movement of the or each object located on the first frame to one or more estimated locations in the second frame, the estimated locations being selected as the further locations.

14. Apparatus as claimed in claim 10 in which the further locations are derived by predicting the movement of the or each object located on the first frame to one or more estimated location in the second frame, the further locations being chosen by carrying out a neighbourhood search around the said estimated locations.

15. Apparatus as claimed in claim 10 further including repeating (b) for a sequence of subsequent frames, each respective sampling grid being offset from the grid used on the preceding frame.

16. Apparatus as claimed in claim 10 in which each time the object detector runs it attempts to find the object of interest at a plurality of different scales.

17. Apparatus as claimed in claim 10 for operating on the real-time video stream, and in which the object detector operates in sub-real-time.

18. Apparatus as claimed in claim 10 in which the object detector is a face detector.

19. Apparatus as claimed in claim 10, wherein a camera includes the apparatus.