In place rotation of images for low memory systems

• US 7,782,341 B2
• Filed: 03/08/2006
• Issued: 08/24/2010
• Est. Priority Date: 03/08/2005
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Kothandaraman, Sreenivas
• Primary Examiner(s): Chauhan; Ulka
• Assistant Examiner(s): Chow; Jeffrey J
• Application Number:
  US11/372,452
• Publication Number:
  US 20080036791A1
• Time in Patent Office: 1,630 Days
• Field of Search: 345/649, 345/653, 345/654, 345/656, 345/658, 382/296, 382/297
• US Class Current: 345/658
• CPC Class Codes: G06T 3/606 by memory addressing or mapping

Abstract

Rotation in the storage domain is a one-one function with the domain equal to the range. This permits an image to be rotated in place. Each image size implies at least one garland of closed chains of pixels. Each image includes a spanning set of these garlands. Rotation in place moves each pixel to the next location on its garland. On completion of a garland by return to the initial pixel, pixels on the next garland are moved. Image rotation is complete after all the garlands have been traversed.

Claims

1. A method of in-place image rotation of an image stored in a memory from an original image to a rotated image comprising the steps of:

identifying a spanning set of garlands corresponding to said original image, each garland consisting of a closed path of chain links including an initial chain link from a memory location of an initial pixel in said original image to an intermediate memory location of said initial pixel in said rotated image and subsequent chain links from a prior intermediate memory location of a prior intermediate pixel in the original image to a further intermediate memory location of said prior intermediate pixel in said rotated image, until said further intermediate memory location returns to said memory location of said initial pixel, said spanning set of garlands together identifying all data movement necessary to transform said original image into said rotated image by moving each pixel only once from a memory location in said original image to a memory location in said rotated image;

identifying an initial pixel for each of the identified garlands;

said steps of identifying a spanning set of garlands corresponding to an initial image and identifying an initial pixel for each of the identified garlands include

filling an image buffer having dimensions equal to dimensions of the image with zeros,

initializing a garland count to 1, and repetitively until all pixels of the image buffer are non-zero;

searching the image buffer for a first pixel equal to zero,

storing the garland count in the first pixel,

calculating a memory location of a next pixel in a current garland,

detecting whether a next pixel at the calculated memory location in the current garland is an initial pixel in the current garland,

if the next pixel is not the initial pixel in the current garland, storing the garland count at the next pixel and repeating the steps of calculating, detecting and storing until the next pixel is the initial pixel in the current garland,

if the next pixel is the initial pixel in the current garland, incrementing the garland count and repeating the steps of searching, storing, calculating, detecting and storing until the step of searching fails to find a zero pixel, whereupon the current garland count corresponds to the number of garlands in the image and each first pixel memory location corresponds to the initial pixel for a corresponding garland;

for each pixel in each identified garland starting at the corresponding identified initial pixel;

storing a current pixel,

calculating the memory location of a next pixel in the corresponding garland,

recalling a next pixel from the calculated memory location in the memory,

storing the recalled next pixel,

saving the stored pixel into the memory at the calculated memory location, and

changing the next pixel into the current pixel and repeating for all pixels in said closed path of chain links of each garland of the spanning set of garlands.

2. The method of claim 1, wherein:

said step of detecting whether a next pixel at the calculated memory location in the current garland is an initial pixel in the current garland includes determining the next pixel is not the initial pixel in the current garland if the pixel is zero and determining the next pixel is the initial pixel in the current garland if the pixel equals the current garland count.

3. The method of claim 1, wherein:

said step of detecting whether a next pixel at the calculated memory location in the current garland is an initial pixel in the current garland includes determining the next pixel is not the initial pixel in the current garland if calculated memory location does not equal the memory location of the initial pixel and determining the next pixel is the initial pixel in the current garland if the calculate memory location equals the memory location of the initial pixel.

4. The method of claim 1, wherein:

said steps of identifying said spanning set of garlands corresponding to an initial image and identifying said initial pixel for each of said identified garlands includes recalling precalculated data indicative of said spanning set of garlands and each initial pixel from memory.

5. The method of claim 4, wherein:

said precalculated data indicative of said spanning set of garlands and each initial pixel includes data indicative of a number of garlands in said spanning set of garlands and a memory location corresponding to each initial pixel.

6. The method of claim 1, wherein:

said method operates on chain links of plural identified garlands simultaneously.

7. The method of claim 1, further comprising:

identifying at least one intermediate pixel for at least one of the identified garlands; and

said method operates on plural chain links of said at least one identified garland simultaneously, beginning at said initial pixel and each intermediate pixel of said at least one identified garland and stopping upon reaching said initial pixel or one of said at least one intermediate pixel.

8. A method of in-place image rotation of an image stored in a memory from an original image to a rotated image comprising the steps of:

identifying a set of tiles encompassing said original image;

rearranging pixels within plural data words spanning each tile, dividing rearranged pixels into plural super-pixels of contiguous pixels;

identifying a spanning set of garlands corresponding to said original image, each garland consisting of a closed path of chain links including an initial chain link from a memory location of an initial tile in said original image to an intermediate memory location of said initial tile in said rotated image and subsequent chain links from a prior intermediate memory location of a prior intermediate tile in the original image to a further intermediate memory location of said prior intermediate tile in said rotated image, until said further intermediate memory location returns to said memory location of said initial tile, said spanning set of garlands together identifying all data movement necessary to transform said original image into said rotated image by moving each tile only once from a memory location in said original image to a memory location in said rotated image;

identifying an initial super-pixel for each of the identified garlands;

said steps of identifying a spanning set of garlands corresponding to an initial image and identifying an initial super-pixel for each of the identified garlands include

filling an image buffer having dimensions equal to dimensions of the image in tiles with zeros,

initializing a garland count to 1, and repetitively until all tiles of the image buffer are non-zero;

searching the image buffer for a first tile equal to zero,

storing the garland count in the first tile,

calculating a memory location of a next tile in a current garland,

detecting whether a next tile at the calculated memory location in the current garland is an initial tile in the current garland,

if the next tile is not the initial tile in the current garland, storing the garland count at the next tile and repeating the steps of calculating, detecting and storing until the next tile is the initial tile in the current garland,

if the next tile is the initial tile in the current garland, incrementing the garland count and repeating the steps of searching, storing, calculating, detecting and storing until the step of searching fails to find a zero tile, whereupon the current garland count corresponds to the number of garlands in the image and each first tile memory location corresponds to the initial super-pixel for a corresponding garland;

for each in each identified garland starting at the corresponding identified initial super-pixel;

storing a current super-pixel,

calculating the memory location of a next super-pixel in the corresponding garland,

recalling a next super-pixel from the calculated memory location in the memory,

storing the recalled next super-pixel,

saving the stored super-pixel into the memory at the calculated memory location, and

changing the next super-pixel into the current super-pixel and repeating for all super-pixels in said closed path of chain links of each garland of the spanning set of garlands.

9. The method of claim 8, wherein:

said step of detecting whether a next tile at the calculated memory location in the current garland is an initial tile in the current garland includes determining the next tile is not the initial tile in the current garland if the tile is zero and determining the next tile is the initial tile in the current garland if the tile equals the current garland count.

10. The method of claim 8, wherein:

said step of detecting whether a next tile at the calculated memory location in the current garland is an initial tile in the current garland includes determining the next tile is not the initial tile in the current garland if calculated memory location does not equal the memory location of the initial tile and determining the next tile is the initial tile in the current garland if the calculate memory location equals the memory location of the initial tile.

11. The method of claim 8, wherein:

said steps of identifying said spanning set of garlands corresponding to an initial image and identifying said initial tile for each of said identified garlands includes recalling precalculated data indicative of said spanning set of garlands and each initial tile from memory.

12. The method of claim 11, wherein:

said precalculated data indicative of said spanning set of garlands and each initial pixel includes data indicative of a number of garlands in said spanning set of garlands and a memory location corresponding to each initial tile.

13. The method of claim 8, wherein:

said method operates on chain links of plural identified garlands simultaneously.

14. The method of claim 8, further comprising:

identifying at least one intermediate super-pixel for at least one of the identified garlands; and

said method operates on plural chain links of said at least one identified garland simultaneously, beginning at said initial super-pixel and each intermediate super-pixel of said at least one identified garland and stopping upon reaching said initial super-pixel or one of said at least one intermediate super-pixel.

15. The method of claim 8, wherein:

said method is practiced using a data processor having a first data size; and

each super-pixel has a data size equal to said first data size.

16. The method of claim 8, wherein:

said method is practiced using a synchronous dynamic random access memory having a first burst size; and

each super-pixel has a data size equal to said first burst size.