Motion tracking using image-texture templates

• US 6,529,613 B1
• Filed: 05/26/1999
• Issued: 03/04/2003
• Est. Priority Date: 11/27/1996
• Status: Expired due to Term

• Current Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Original Assignee: Princeton Video Image, Inc. (Gabriel Technologies Corporation)
• Inventors: Astle, Brian
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US09/308,949
• Time in Patent Office: 1,378 Days
• Field of Search: 382/103, 382/107, 382/218, 382/284, 382/209, 382/217, 382/199, 382/118, 382/291, 348/584, 348/585-592, 348/169, 348/135, 395/118, 395/133, 395/135, 395/127
• US Class Current: 382/103
• CPC Class Codes: G01S 17/66 Tracking systems using electromagnetic waves other than radio waves
• CPC Class Codes: G01S 3/7864 T.V. type tracking systems
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51
• CPC Class Codes: H04N 5/272 Means for inserting a foreground image in a background image, i.e. inlay, outlay
• CPC Class Codes: H04N 5/2723 Insertion of virtual advertisement; Replacing advertisements physical present in the scene by virtual advertisement data processing systems or methods specially adapted for marketing G06Q30/02

Abstract

Image templates are extracted from video images in real-time and stored in memory. Templates are selected on the basis of their ability to provide useful positional data and compared with regions of subsequent images to find the position giving the best match. From the position data a transform model is calculated. The transform model tracks the background motion in the current image to accurately determine the motion and attitude of the camera recording the current image. The transform model is confirmed by examining pre-defined image templates. Transform model data and camera sensor data are then used to insert images into the live video broadcast at the desired location in the correct perspective. Stored templates are periodically updated to purge those that no longer give valid or significant positional data. New templates extracted from recent images are used to replace the discarded templates.

Claims

1. A method for tracking motion in a stream of video images comprising the steps of:

a) obtaining a set of image templates (block) from a current video image that meet certain template capturing criteria and storing said image templates in memory;

b) determining the position of each stored image template with respect to the current image;

c) calculating a transform model using the determined template positions with respect to the current image, said transform model being a descriptor of the change of position of said set of image templates;

d) purging image templates from memory that do not meet certain template retention criteria; and

e) obtaining new image templates from said current image to replace the image templates that were purged, wherein said set of image templates comprises an array of adjacent pixels from a current video image and wherein said image templates comprise substantially less than all of the pixels in said current video image.

5. The method of claim 1 further comprising the step of:

i) confirming the accuracy of said transform model by comparing its correspondence results against a set of previously defined synthetic templates.

6. The method of claim 5 wherein determining the position of each stored image template with respect to the current image comprises the steps of:

j) performing an integer Position search in order to determine the minimum value of said error surface; and

k) upon completion of said integer position search, performing a fractional pixel interpolation in order to estimate the fractional part of the motion of a small piece of the previous image to the current image.

7. The method of claim 6 wherein performing the integer position search comprises the steps of:

l) positioning each template at several integer position locations in the image template and calculating an error surface for each location using the specified block matching criteria

m) searching a series of template regions having an initial search region centered about a predicted template position derived from an estimation of the motion of a small piece of the previous image to the current image, said searching to determine image template size and shape;

n) terminating the search successfully if a minimum is found within the predicted search region; and

o) terminating the integer position search unsuccessfully if, after several at tempts, a minimum cannot be found within the predicted search region and storing said information pertaining to the unsuccessful search so that the block may be later purged.

8. The method of claim 7 wherein said integer position search uses linear prediction techniques.

9. The method of claim 7 wherein said integer position search uses second-order polynomial prediction techniques.

10. The method of claim 7 wherein said error surface indicating mismatches between each image template and the current image in a region proximate to the determined template position is calculated according to the following block matching technique:

$M=1-N=1-\frac{\sum <br><br>I<br><br>\text{\hspace{1em}<br><br>}<br><br>T}{\sqrt{\sum <br><br>I^2<br><br>\sum <br><br>T^2}}$

where

M represents the mismatch value,

N represents a normalized correlation calculation,

I represents the pixel values in the current image, and

T represents the pixel values in the image template.

11. The method of claim 7 wherein said error surface indicating mismatches between each image template and the current image in a region proximate to the determined template position is calculated according to the following block matching technique:

$M=1-B<br><br>\text{\hspace{1em}<br><br>}<br><br>A=1-\frac{2*\sum <br><br>I<br><br>\text{\hspace{1em}<br><br>}<br><br>T}{\sum <br><br>I^2+\sum <br><br>T^2}$

where

M represents the mismatch value,

BA represents an error surface calculation,

I represents the pixel values in the current image, and

T represents the pixel values in the image template.

12. The method of claim 7 wherein said error surface indicating mismatches between each image template and the current image in a region proximate to the determined template position is calculated according to the following block matching technique:

$M=1-\mathrm{L1norm}=1-\sum <br><br>d$

where

M represents the mismatch value,

L1 norm represents an error surface calculation, and

d represents the difference in pixel values between the image template and the current image.

13. The method of claim 12 wherein the fractional pixel interpolation uses a triangular interpolation method.

14. The method of claim 7 wherein said error surface indicating mismatches between each image template and the current image in a region proximate to the determined template position is calculated according to the following block matching technique:

$M=1-\mathrm{L2norm}=1-\sum <br><br>d^2$

where

M represents the mismatch value,

L2 norm represents an error surface calculation, and

d represents the difference in pixel values between the image template and the current image.

15. The method of claim 14 wherein the fractional pixel interpolation uses a parabolic interpolation method.

16. The method of claim 7 wherein the fractional pixel interpolation uses a three-halves power interpolation method.

17. The method of claim 7 wherein said evaluating said error surface to determine its minimum value in order to determine the best match between the image templates and the current image comprises the steps of:

p) expanding the image template yielding sub-pixel position values; and

q) performing a further integer position search according to step (j) above at these sub-pixel locations.

18. The method of claim 7 wherein said evaluating said error surface to determine its minimum value in order to determine the best match between the image templates and the current image comprises the steps of:

r) obtaining error surface values proximate to the minimum value determined by the integer position search of step (j);

s) interpolating for a value at the horizontal scan line just above where the original integer position search determined a minimum, said interpolating carried out by a one dimensional method;

t) interpolating for a value at the horizontal scan line where the original integer position search determined a minimum, said interpolating carried out by a one dimensional method;

u) interpolating for a value at the horizontal scan line just below where the original integer position search determined a minimum, said interpolating carried out by a one dimensional method; and

v) interpolating the values from steps (s), (t), and (u) to determine a final minimum value for said error surface.

19. The method of claim 7 wherein said evaluating said error surface to determine its minimum value in order to determine the best match between the image templates and the current image comprises the step of:

w) interpolating the position of the minimum using a singular value decomposition method.

20. The method of claim 7 wherein calculating said transform model comprises the steps of:

x) setting horizontal and vertical weights for each block depending on the curvature of the error surface;

y) calculating a preliminary transform model using a mean square error minimization method;

z) evaluating each block for spatial error to determine how well it agrees with the preliminary transform model;

aa) modifying said weights for each block according to the spatial error; and

bb) calculating a final transform model using the modified block weights.

21. The method of claim 7 wherein said template retention criteria require that image templates, in order not to be purged, must not be in a horizontal blanking area, must not be in an active burn-in region, must agree with the current transform model with respect to position, and must have sufficient curvature of the error surface.

22. The method of claim 7 further comprising the steps of:

cc) low-pass filtering and sub-sampling said image templates obtained in step (a) in order to provide a series of lower resolution image templates;

dd) performing an integer position search on the image templates at each resolution level, starting with the lowest resolution level and working up;

ee) calculating a transform model at each resolution level in order to predict the positions of the image templates at the next highest level.

2. A method for tracking motion in a stream of video images comprising the steps of:

a) obtaining a set of image templates (block) from a current video image that meet certain template capturing criteria and storing said image templates in memory;

b) determining the position of each stored image template with respect to the current image;

c) calculating a transform model using the determined template positions with respect to the current image, said transform model being a descriptor of the change of position of said set of image templates;

d) purging image templates from memory that do not meet certain template retention criteria; and

e) obtaining new image templates from said current image to replace the image templates that were purged, wherein said purging step (d) and said obtaining step (a) are performed in either the odd video fields only or the even video fields only in order to reduce video interlace stability problems.

3. A method for tracking motion in a stream of video images comprising the steps of:

a) obtaining a set of image templates (block) from a current video image that meet certain template capturing criteria and storing said image templates in memory;

b) determining the position of each stored image template with respect to the current image;

c) calculating a transform model using the determined template positions with respect to the current image, said transform model being a descriptor of the change of position of said set of image templates;

d) purging image templates from memory that do not meet certain template retention criteria; and

e) obtaining new image templates from said current image to replace the image templates that were purged, wherein said obtaining step (a) is terminated after a preset time limit or after a sufficient number of image templates have been obtained, whichever event occurs first.

4. A method for tracking motion in a stream of video images comprising steps of:

a) obtaining a set of image templates (block) from a current video image that meet certain template capturing criteria and storing said image templates in memory;

b) determining the position of each stored image template with respect to the current image;

c) calculating a transform model using the determined template positions with respect to the current image, said transform being a descriptor of the change of position of said set of image templates;

d) purging image templates from memory that do not meet certain template retention criteria;

f) obtaining new image templates from said current image to replace the image templates that were purged;

g) determining an error surface indicating mismatches between each image template and the current image in a region proximate to the determined template position;

h) evaluating said error surface to determine its minimum value in order to determine the best match between the image templates and the current image; and

,

i) using said error surface in said transform model calculations.