Statistically comparing and matching plural sets of digital data

• US 7,302,084 B2
• Filed: 12/07/2005
• Issued: 11/27/2007
• Est. Priority Date: 02/18/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Szeliski, Richard, Wilt, Nicholas
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): GORADIA, SHEFALI DINESH
• Application Number:
  US11/297,627
• Publication Number:
  US 20060088189A1
• Time in Patent Office: 720 Days
• Field of Search: 382/103, 382/107, 382/228, 382/299, 382/209, 348/169
• US Class Current: 382/103
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 10/94 Hardware or software architectures specially adapted for image or video understanding

Abstract

The present invention is embodied in a system and method for statistically comparing a first set of digital data to at least a second set of digital data and matching the first set of digital data to appropriately corresponding portions of the second set of digital data. The first or the second set of digital data can be transformed during statistical analysis to enhance statistical analysis of the digital data.

Claims

1. A computer readable medium having computer executable instructions for tracking digital templates of a digital scene defined by plural images, said computer executable instructions comprising:

causing a computer graphics card including a raster processor to transform at least one of the templates, said transforms including combinations of rotations, scales, perspective transforms, and translations;

controlling a statistics enable switch included in the computer graphics card, wherein accumulation of information for each digital template is enabled when said statistics enable switch is enabled, and wherein said computer graphics card provides the at least one transformed template to a frame buffer included in the computer graphics card when said statistics enable switch is disabled by the computer executable instructions;

controlling a statistical compare processor included in the computer graphics card that accumulates information for each digital template and statistically compares and matches images associated with the templates for tracking the templates based on the accumulated information when said statistics enable switch is enabled by the computer executable instructions; and

providing pixel alpha values to the statistical compare processor for weighting statistical information used by the statistical compare processor for simultaneously and statistically comparing and matching images associated with the templates for tracking the templates.

2. The computer readable medium of claim 1, wherein the computer graphics card further comprises an address generator that generates addresses for the template and the image that are to be compared in response to the computer executable instructions.

3. The computer readable medium of claim 2, wherein the addresses serve as input to filtering functions that read from the images to be compared and generate color values.

4. The computer readable medium of claim 1, wherein the template comprises a group of pixels of the image and wherein the computer graphics card further includes an acceptance tester preprogrammed to decide whether to allow a pixel of the template to contribute to the statistics.

5. The computer readable medium of claim 4, wherein if the pixel is permitted to contribute, the color values are sent to the statistical compare processor for statistical analyses and comparison processing.

6. The computer readable medium of claim 5, wherein the statistical compare processor contains variables that are updated for each pixel based on the input color values of each pixel.

7. The computer readable medium of claim 6, wherein the statistical analyses compares and matches the template to the image by initially defining a function that estimates the similarity between the template and the image.

8. The computer readable medium of claim 7, wherein the template is located in the image by computing the function at various locations in the image and determining where the function is maximized.

9. The computer readable medium of claim 1, wherein the raster processor renders the template at a plurality of offsets for allowing the raster processor to at least one of determining a desired position for the template and accumulate information to analytically compute a desired update.

10. The computer readable medium of claim 9, wherein the offsets are fractional perturbations to vertices of the templates.

11. A method for tracking digital templates of a digital scene defined by plural images, comprising steps for:

using a computer graphics card including a raster processor to transform at least one of the templates, said transforms including combinations of rotations, scales, perspective transforms, and translations;

controlling a statistics enable switch included in the computer graphics card, wherein accumulation of information for each digital template is enabled when said statistics enable switch is enabled, and wherein said computer graphics card provides the at least one transformed template to a frame buffer included in the computer graphics card when said statistics enable switch is disabled;

controlling a statistical compare processor included in the computer graphics card that accumulates information for each digital template and statistically compares and matches images associated with the templates for tracking the templates based on the accumulated information when said statistics enable switch is enabled; and

providing pixel alpha values to the statistical compare processor for weighting statistical information used by the statistical compare processor for simultaneously and statistically comparing and matching images associated with the templates for tracking the templates.

12. The method of claim 11 wherein the computer graphics card further comprises an address generator that generates addresses for the template and the image that are to be compared.

13. The method of claim 12 wherein the addresses serve as input to filtering functions that read from the images to be compared and generate color values.

14. The method of claim 11 wherein the template comprises a group of pixels of the image and wherein the computer graphics card further includes an acceptance tester preprogrammed to decide whether to allow a pixel of the template to contribute to the statistics.

15. The method of claim 14 wherein if the pixel is permitted to contribute, the color values are sent to the statistical compare processor for statistical analyses and comparison processing.

16. The method of claim 15 wherein the statistical compare processor contains variables that are updated for each pixel based on the input color values of each pixel.

17. The method of claim 16 wherein the statistical analyses compares and matches the template to the image by initially defining a function that estimates the similarity between the template and the image.

18. The method of claim 17 wherein the template is located in the image by computing the function at various locations in the image and determining where the function is maximized.

19. The method of claim 11 wherein the raster processor renders the template at a plurality of offsets for allowing the raster processor to at least one of determining a desired position for the template and accumulate information to analytically compute a desired update.

20. The method of claim 19 wherein the offsets are fractional perturbations to vertices of the templates.