Target tracking

• US 8,121,346 B2
• Filed: 06/08/2007
• Issued: 02/21/2012
• Est. Priority Date: 06/16/2006
• Status: Active Grant

• Current Assignee: BAE Systems Plc
• Original Assignee: BAE Systems Plc
• Inventors: Williams, Mark Lawrence
• Primary Examiner(s): BHATNAGAR, ANAND P
• Application Number:
  US11/910,582
• Publication Number:
  US 20090310820A1
• Time in Patent Office: 1,719 Days
• Field of Search: 382/100, 382/103, 382/106, 382/107, 382/209, 382/215, 382/217, 348169-175
• US Class Current: 382/103
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/772 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries

Abstract

A method and system are disclosed for tracking a target imaged in video footage. The target may, for example, be a person moving through a crowd The method comprises the steps of: identifying a target in a first frame; generating a population of sub-templates by sampling from a template area defined around the target position; and searching for instances of the sub-templates in a second frame so as to locate the target in the second frame. Sub-templates whose instances are not consistent with the new target position are removed from the population and replaced by newly sampled sub-templates. The method can then be repeated so as to find the target in further frames. It can be implemented in a system comprising video imaging means, such as a CCTV camera, and processing means operable to carry out the method.

Claims

1. A method of tracking a target imaged in video footage, the method comprising the steps of:

(i) identifying the target to be tracked in a first image frame, the target being located at a first position;

(ii) defining a first template area around the first position;

(iii) generating a first population of sub-templates by sampling from the first template area;

(iv) searching for an instance of each of the first population of sub-templates in a second image frame, and determining the location of each instance in the second image frame;

(v) determining a second position of the target in the second image frame in dependence on the locations of the instances;

(vi) selecting a selection of the first population of sub-templates in dependence on the locations of the instances of each of the sub-templates in the second frame;

(vii) defining a second template area defined around the second position;

(viii) generating a second population of sub-templates comprising the selection of the first population of sub-templates, and a set of new sub-templates generated by sampling from the second template area; and

(ix) iterating steps (iv) to (viii) above in respect of further image frames, using the second population of sub-templates and the second position from a preceding iteration in place of the first population of sub-templates and the first position, thereby determining a series of target positions, and inferring the target track therefrom,

wherein the step of identifying a second position of the target comprises the step of determining a permitted area, and constraining the second position to lie within the permitted area, and

wherein the step of searching for an instance of each of the first population of sub-templates in a second image frame includes searching areas of the second image frame outside the permitted area.

2. The method as claimed in claim 1 wherein the step (iii) comprises determining the location of a best match for each of the first population of sub-templates in the second image frame.

3. The method as claimed in claim 1 wherein the step of generating the second population of sub-templates comprises associating a weight with each of the first population of sub-templates, the weight being related to the location of the instance of said each sub-template in the second frame relative to the second position.

4. The method as claimed in claim 3 wherein each weight is given one of two values in dependence on whether the instance of its associated sub-template is located within or without the second template area.

5. The method as claimed in claim 4 wherein the selection of the first population of sub-templates comprises sub-templates having instances within the second template area.

6. The method as claimed in claim 1 wherein an upper limit is set for the number of sub-templates in the set of new sub-templates.

7. The method as claimed in claim 6, wherein the upper limit is in the range between 5% and 50% of the number of sub-templates in the first population of sub-templates.

8. The method as claimed in claim 7, wherein the upper limit is in the range between 15% and 25% of the number of sub-templates in the first population of sub-templates.

9. The method as claimed in claim 8 wherein the upper limit is 20% of the number of sub-templates in the first population of sub-templates.

10. The method as claimed in claim 1, wherein the step of determining a permitted area comprises providing a maximum target speed, and determining the permitted area in dependence on the maximum target speed, the first position, and the time elapsed between the first and second image frames.

11. The method as claimed in claim 10 wherein the area of the first and second image frames is much larger than the area of the first and second template areas.

12. The method as claimed in claim 1, wherein the step of identifying a second position comprises applying a clustering process to the locations of the instances of the first population of sub-templates in the second image frame.

13. The method as claimed in claim 12 wherein the clustering process comprises the step of convolving a cluster function with the population of instances of the first population of sub-templates, and the second position is the position having the highest value of the resulting convolution.

14. The method as claimed in claim 13 wherein the cluster function has a shape approximately equal to the target template.

15. A tracking system comprising imaging means operable to generate video footage, and processing means operable to carry out a method of tracking a target imaged in video footage, the method comprising the steps of:

(i) identifying the target to be tracked in a first image frame, the target being located at a first position;

(ii) defining a first template area around the first position;

(iii) generating a first population of sub-templates by sampling from the first template area;

(iv) searching for an instance of each of the first population of sub-templates in a second image frame, and determining the location of each instance in the second image frame;

(v) determining a second position of the target in the second image frame in dependence on the locations of the instances;

(vi) selecting a selection of the first population of sub-templates in dependence on the locations of the instances of each of the sub-templates in the second frame;

(vii) defining a second template area defined around the second position;

(viii) generating a second population of sub-templates comprising the selection of the first population of sub-templates, and a set of new sub-templates generated by sampling from the second template area; and

(ix) iterating steps (iv) to (viii) above in respect of further image frames, using the second population of sub-templates and the second position from a preceding iteration in place of the first population of sub-templates and the first position, thereby determining a series of target positions, and inferring the target track therefrom,

wherein the step of identifying a second position of the target comprises the step of determining a permitted area, and constraining the second position to lie within the permitted area, and

wherein the step of searching for an instance of each of the first population of sub-templates in a second image frame includes searching areas of the second image frame outside the permitted area.

16. A non-transitory computer readable medium having recorded thereon a computer program product operable, when the computer readable medium is inserted into a computer, to cause the computer to execute a method of tracking a target imaged in video footage, the method comprising the steps of:

(i) identifying the target to be tracked in a first image frame, the target being located at a first position;

(ii) defining a first template area around the first position;

(iii) generating a first population of sub-templates by sampling from the first template area;

(iv) searching for an instance of each of the first population of sub-templates in a second image frame, and determining the location of each instance in the second image frame;

(v) determining a second position of the target in the second image frame in dependence on the locations of the instances;

(vi) selecting a selection of the first population of sub-templates in dependence on the locations of the instances of each of the sub-templates in the second frame;

(vii) defining a second template area defined around the second position;

(viii) generating a second population of sub-templates comprising the selection of the first population of sub-templates, and a set of new sub-templates generated by sampling from the second template area; and

(ix) (iv) to (viii) above in respect of further image frames, using the second population of sub-templates and the second position from a preceding iteration in place of the first population of sub-templates and the first position, thereby determining a series of target positions, and inferring the target track therefrom,

wherein the step of identifying a second position of the target comprises the step of determining a permitted area, and constraining the second position to lie within the permitted area, and

wherein the step of searching for an instance of each of the first population of sub-templates in a second image frame includes searching areas of the second image frame outside the permitted area.