Method to quickly warp a 2-D image using only integer math

• US 7,379,623 B2
• Filed: 08/26/2004
• Issued: 05/27/2008
• Est. Priority Date: 04/30/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rudolph, Eric
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): CHU, RANDOLPH I
• Application Number:
  US10/927,371
• Publication Number:
  US 20050243103A1
• Time in Patent Office: 1,370 Days
• Field of Search: 382/293, 382/276, 382/277, 382295-301, 382/307, 345619-689, 348/580, 708/442
• US Class Current: 382/293
• CPC Class Codes: G06T 3/18 Image warping, e.g. rearranging pixels individually

Abstract

Systems and methods are disclosed that facilitate rapidly warping a two-dimensional image using integer math. A warping table can contain two-dimensional floating point output pixel offset values that are mapped to respective input pixel locations in a captured image. The warping table values can be pre-converted to integer offset values and integer grid values mapped to a sub-pixel grid. During warping, each output pixel can be looked up via its integer offset value, and a one-dimensional table lookup for each pixel can be performed to interpolate pixel data based at least in part on the integer grid value of the pixel. Due to the small size of the lookup tables, lookups can potentially be stored in and retrieved from a CPU cache, which stores most recent instructions to facilitate extremely rapid warping and fast table lookups.

Claims

1. A system that warps a two-dimensional image, comprising:

an input component that receives the two-dimensional image; and

a warp component that maps output pixel offset values in floating point format to input pixel coordinates and linearizes the output pixel offset values via converting the output pixel offset values for each pixel into an integer grid value and integer offset values for respective pixel(s), the warp component determines a floating point remainder for each of an x-offset value and a y-offset value for a given pixel, converts each floating point remainder to an integer remainder value by multiplying the floating point remainder by the width of a sub-pixel grid and truncates the product to obtain an x-offset integer value and a y-offset integer value and determines the integer grid value from the integer remainder values;

wherein the integer offset value is utilized to determine a location of a pixel and the integer grid value is utilized to identify a suitable warping algorithm for warping the two-dimensional image.

2. The system of claim 1, wherein the warp component partitions the pixel into the sub-pixel grid of a predetermined height and width.

3. The system of claim 1, wherein determining the floating point remainders comprises truncating each of the x-offset and the y-offset floating point values and subtracting the truncated values from their respective floating point values.

4. The system of claim 1, further comprising a one-dimensional array of structures that store integer values, wherein each of the structures comprises integer offset values that represent the position of the pixel relative to all other pixels, and the integer grid value, which represents the position of the pixel center within the sub-pixel grid.

5. The system of claim 4, wherein the warp component reads the one-dimensional array of structures to obtain the integer offset values and the integer grid values on a per-pixel basis during a warp.

6. The system of claim 1, wherein the warp component utilizes a warping algorithm to interpolate pixel information from surrounding pixels based at least in part on the integer grid value.

7. The system of claim 6, wherein the warping algorithm is a nearest neighbor interpolation algorithm.

8. The system of claim 2, wherein the height of the sub-pixel grid is equal to the width of the sub-pixel grid.

9. The system of claim 8, wherein sub-pixel regions within the sub-pixel grid are numbered from left to right in descending rows, from 0 to N, where N is an integer equal to the product of the height and width of the sub-pixel region, minus one.

10. The system of claim 9, wherein the integer grid value is within the range [0,N].

24. A computer-readable medium having stored thereon computer executable components of the system of claim 1.

11. A method for rapidly warping a two-dimensional image, comprising:

generating a table of warp coordinates that maps output pixel location in floating point format to input pixel location;

converting floating point output pixel offset values on a per-pixel basis into integer offset values and an integer grid value that represents a region of a sub-pixel grid in which a pixel'"'"'s center is positioned;

determining a floating point remainder for each of an x-offset value and a y-offset value for a given pixel;

converting each floating point remainder to an integer remainder value by multiplying the floating point remainder by the width of the sub-pixel grid and truncating the product to obtain an x-offset integer value and a y-offset integer value;

determining the integer grid value from the integer remainder values;

encoding a structure within a one-dimensional array of structures with the integer offset values and the integer grid value; and

employing the integer offset values during warping to identify an output pixel, and the integer grid value to identify surrounding pixels from which information will be interpolated.

12. The method of claim 11, wherein x- and y-integer offset values are determined via truncating the floating point warp coordinate values.

13. The method of claim 11, wherein determining the floating point remainders comprises truncating each of the x-offset and the y-offset floating point values and subtracting the truncated values from their respective floating point values.

14. The method of claim 11, wherein determining the integer grid value of a pixel from the integer remainder values comprises multiplying the y-offset integer value by the width of the sub-pixel grid and summing the product with the x-offset integer value.

15. The method of claim 11, further comprising performing a single table lookup per output pixel to find the structure associated with the output pixel during a warp.

16. The method of claim 15, further comprising performing a series of table lookups on a table that is indexed on the possible integer grid values for the output pixel to determine which of a plurality of surrounding pixels should be selected for pixel data interpolation.

17. The method of claim 16, wherein the set of possible integer grid values for the output pixel is [0,(H*W−

1)], where H and W are integers representing the height and width, respectively, of the sub-pixel grid.

18. A method for high-speed digital image warping, comprising:

generating a warp table that maps output pixel locations in floating point format to input pixel locations;

pre-converting floating-point pixel location information to integer pixel information by determining a floating point remainder for each of an x-offset value and a y-offset value for a given pixel, converting each floating point remainder to an integer remainder value by multiplying the floating point remainder by the width of the sub-pixel grid and truncating the product to obtain an x-offset integer value and a y-offset integer value, and determining an integer grid value from the integer remainder value;

generating an away of structures comprising integer information for each pixel in an image; and

warping the image based at least in part on integer information in the structures.

19. The method of claim 18, wherein the integer information further comprises an integer offset value.

20. The method of claim 18, wherein warping the image further comprises:

performing a table lookup based on offset values for a given source pixel; and

performing a series of subsequent table lookups on a table indexed on the integer grid value of the source pixel to determine appropriate percentages of information to interpolate from neighboring pixels.

21. The method of claim 20, further comprising interpolating information from neighboring pixels as determined by an interpolation algorithm that is selected based at least in part on the integer grid value.

22. A system that facilitates rapid warping of a digital image, comprising:

means for converting output pixel information from a two-dimensional floating-point format to a one-dimensional integer format;

means for determining a floating point remainder for each of an x-offset value and a y-offset value for a each pixel;

means for converting each floating point remainder to an integer remainder value by multiplying the floating point remainder by the width of the sub-pixel grid and truncating the product to obtain an x-offset integer value and a y-offset integer value;

means for determining an integer grid value for each pixel from the integer remainder values for each pixel;

means for generating an array of structures, wherein each structure comprises the integer grid value and an integer offset values for a single pixel; and

means for interpolating pixel information from neighboring pixels to warp an image based at least in part on the integer grid values.

23. The system of claim 22, further comprising means for outputting a warped image to a user.