Banded seam carving of images with pyramidal retargeting

• US 8,280,191 B1
• Filed: 07/31/2008
• Issued: 10/02/2012
• Est. Priority Date: 07/31/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Avidan, Shmuel, Chien, Jen-Chan, Intwala, Chintan
• Primary Examiner(s): Koziol, Stephen R
• Application Number:
  US12/184,019
• Time in Patent Office: 1,524 Days
• Field of Search: 382/100, 382/284, 382/293, 382/295, 382/298, 382/300, 345/629
• US Class Current: 382/298
• CPC Class Codes: G06T 3/04 Context-preserving transformations, e.g. by using an importance map panospheric to cylindrical image transformations G06T3/12

Abstract

A system and method for expansion and reduction of images uses pyramidal retargeting to reduce complexity in image resizing. An image pyramid may be generated dependent on a function of pixel data or energy values for each pixel of an input image. An image resizing solution may be developed by applying seam carving techniques to a lower-resolution version of the input image represented by the image pyramid, and may identify bands in the higher-resolution input image to be resized. A resizing operation may then be applied the bands based on local content. The resizing operation may include seam carving techniques, scaling techniques, and/or hybrid resizing techniques, and may be selectable by a user. Identified bands may be expanded to obtain a smoother solution. Different bands may be expanded by different amounts, based on local content. The number of bands and the expansion factors may be configurable based on user input.

Claims

1. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors and storing program instructions executable by the one or more processors to implement;

accessing data representing an image;

generating an acceleration data structure representing a lower-resolution version of the image;

determining a respective energy value for each pixel of the lower-resolution version of the image dependent on values associated with the pixels of the lower-resolution version of the image;

identifying a seam of the lower-resolution version of the image having a lowest cost, wherein the cost of the seam is dependent on the respective energy values for all pixels of the seam; and

performing a resizing operation on a portion of the image to produce a resized version of the image, wherein the portion of the image on which the resizing operation is performed is dependent on the identified seam of the lower-resolution version of the image.

2. The system of claim 1, wherein the program instructions are further executable to implement repeating said identifying and said performing for a next lowest cost seam of the lower-resolution version of the image until the resized version of the image meets a specified target size or a specified target aspect ratio.

3. The system of claim 2, wherein the program instructions are further executable to implement determining a number of seams for which to repeat said identifying and said performing, wherein said determining is dependent on user input.

4. The system of claim 2, wherein said performing comprises applying a different resizing technique to the portion of the image dependent on the identified seam having the next lowest cost than a resizing technique applied to the portion of the image dependent on the identified seam having the lowest cost.

5. The system of claim 1,

wherein the resizing operation comprises a reduction operation;

and

wherein said performing comprises removing at least some of the pixels from the portion of the image, dependent on values associated with the pixels of the portion of the image.

6. The system of claim 1,

wherein the resizing operation comprises an expansion operation;

and

wherein said performing comprises replicating at least some of the pixels of the portion of the image, dependent on values associated with the pixels of the portion of the image, and inserting the replicated pixels into the image.

7. The system of claim 1, wherein said generating comprises:

dividing the data representing the image into a plurality of blocks, wherein each block comprises respective values for a same number of pixels of the image; and

for each of the plurality of blocks;

performing an associative operation on the values of the block; and

storing a result of said performing an associative operation as a pixel value of the lower-resolution version of the image in the acceleration data structure.

8. The system of claim 7, wherein the respective energy value of each pixel of the lower-resolution version of the image is dependent on the values of a corresponding block.

9. The system of claim 7, wherein the value of each pixel of the image represents one or more of:

an absolute color value, an absolute intensity value, a difference in color values, a difference in intensity values, a derivative of two or more pixel values, an average of two or more pixel values, a maximum of two or more pixel values, or a minimum of two or more pixel values.

10. The system of claim 7, wherein the portion of the image comprises pixels of the image included in blocks associated with pixel values of the identified seam of the lower-resolution version of the image.

11. The system of claim 10, wherein the portion of the image further comprises pixels of the image adjacent to the pixels of the image included in blocks associated with pixel values of the identified seam of the lower-resolution version of the image.

12. The system of claim 1, wherein the cost of each seam is dependent on one or more of:

a sum of the respective energy values of all pixels of the seam, an average of the respective energy values of all pixels of the seam, a weighted average of the respective energy values of all pixels of the seam, or a maximum value of the respective energy values of all pixels of the seam.

13. The system of claim 1, wherein said identifying one or more seams comprises one or more of:

identifying a shortest path across the lower-resolution version of the image, or applying a dynamic programming technique.

14. The system of claim 1, wherein said performing comprises one or more of:

applying a seam-based resizing technique, or applying an image scaling technique.

15. The system of claim 1, wherein the one or more processors comprise at least one of:

a general-purpose central processing unit (CPU), or a graphics processing unit (GPU).

16. A non-transitory computer-readable storage medium, comprising program instructions computer-executable to implement:

accessing data representing an image;

generating an acceleration data structure representing a lower-resolution version of the image;

determining a respective energy value for each pixel of the lower-resolution version of the image dependent on values associated with the pixels of the lower-resolution version of the image;

identifying a seam of the lower-resolution version of the image having a lowest cost, wherein the cost of the seam is dependent on the respective energy values for all pixels of the seam; and

performing a resizing operation on a portion of the image to produce a resized version of the image, wherein the portion of the image on which the resizing operation is performed is dependent on the identified seam of the lower-resolution version of the image.

17. The storage medium of claim 16, wherein the program instructions are further executable to implement repeating said identifying and said performing for a next lowest cost seam of the lower-resolution version of the image until the resized version of the image meets a specified target size or a specified target aspect ratio.

18. The storage medium of claim 17, wherein the program instructions are further executable to implement determining a number of seams for which to repeat said identifying and said performing, wherein said determining is dependent on user input.

19. The storage medium of claim 17, wherein said performing comprises applying a different resizing technique to the portion of the image dependent on the identified seam having the next lowest cost than a resizing technique applied to the portion of the image dependent on the identified seam having the lowest cost.

20. The storage medium of claim 16,

wherein the resizing operation comprises a reduction operation;

and

wherein said performing comprises removing at least some of the pixels from the portion of the image, dependent on values associated with the pixels of the portion of the image.

21. The storage medium of claim 16,

wherein the resizing operation comprises an expansion operation;

and

wherein said performing comprises replicating at least some of the pixels of the portion of the image, and inserting the replicated pixels into the image.

22. The storage medium of claim 16, wherein said generating comprises:

dividing the data representing the image into a plurality of blocks, wherein each block comprises respective values for a same number of pixels of the image; and

for each of the plurality of blocks;

performing an associative operation on the values of the block; and

storing a result of said performing an associative operation as a pixel value of the lower-resolution version of the image in the acceleration data structure.

23. The storage medium of claim 22, wherein the value of each pixel of the image represents one or more of:

an absolute color value, an absolute intensity value, a difference in color values, a difference in intensity values, a derivative of two or more pixel values, an average of two or more pixel values, a maximum of two or more pixel values, or a minimum of two or more pixel values.

24. The storage medium of claim 22, wherein the portion of the image comprises pixels of the image included in blocks associated with pixel values of the identified seam of the lower-resolution version of the image.

25. The storage medium of claim 24, wherein the portion of the image further comprises pixels of the image adjacent to the pixels of the image included in blocks associated with pixel values of the identified seam of the lower-resolution version of the image.

26. The storage medium of claim 16, wherein the cost of each seam is dependent on one or more of:

a sum of the respective energy values of all pixels of the seam, an average of the respective energy values of all pixels of the seam, a weighted average of the respective energy values of all pixels of the seam, or a maximum value of the respective energy values of all pixels of the seam.

27. The storage medium of claim 16, wherein said performing comprises one or more of:

applying a seam-based resizing technique, or applying an image scaling technique.

28. A computer-implemented method, comprising:

accessing data representing an image;

generating an acceleration data structure representing a lower-resolution version of the image;

determining a respective energy value for each pixel of the lower-resolution version of the image dependent on values associated with the pixels of the lower-resolution version of the image;

identifying a seam of the lower-resolution version of the image having a lowest cost, wherein the cost of the seam is dependent on the respective energy values for all pixels of the seam; and

performing a resizing operation on a portion of the image to produce a resized version of the image, wherein the portion of the image on which the resizing operation is performed is dependent on the identified seam of the lower-resolution version of the image.

29. The method of claim 28, further comprising repeating said identifying and said performing for a next lowest cost seam of the lower-resolution version of the image until the resized version of the image meets a specified target size or a specified target aspect ratio.

30. The method of claim 29, further comprising determining a number of seams for which to repeat said identifying and said performing, wherein said determining is dependent on user input.

31. The method of claim 29, wherein said performing comprises applying a different resizing technique to the portion of the image dependent on the identified seam having the next lowest cost than a resizing technique applied to the portion of the image dependent on the identified seam having the lowest cost.

32. The method of claim 28,

wherein the resizing operation comprises a reduction operation;

and

wherein said performing comprises removing at least some of the pixels from the portion of the image, dependent on values associated with the pixels of the portion of the image.

33. The method of claim 28,

wherein the resizing operation comprises an expansion operation;

and

wherein said performing comprises replicating at least some of the pixels of the portion of the image, and inserting the replicated pixels into the image.

34. The method of claim 28, wherein said generating comprises:

dividing the data representing the image into a plurality of blocks, wherein each block comprises respective values for a same number of pixels of the image; and

for each of the plurality of blocks;

performing an associative operation on the values of the block; and

storing a result of said performing an associative operation as a pixel value of the lower-resolution version of the image in the acceleration data structure.

35. The method of claim 34, wherein the value of each pixel of the image represents one or more of:

an absolute color value, an absolute intensity value, a difference in color values, a difference in intensity values, a derivative of two or more pixel values, an average of two or more pixel values, a maximum of two or more pixel values, or a minimum of two or more pixel values.

36. The method of claim 34, wherein the portion of the image comprises pixels of the image included in blocks associated with pixel values of the identified seam of the lower-resolution version of the image.

37. The method of claim 36, wherein the portion of the image further comprises pixels of the image adjacent to the pixels of the image included in blocks associated with pixel values of the identified seam of the lower-resolution version of the image.

38. The method of claim 28, wherein the cost of each seam is dependent on one or more of:

a sum of the respective energy values of all pixels of the seam, an average of the respective energy values of all pixels of the seam, a weighted average of the respective energy values of all pixels of the seam, or a maximum value of the respective energy values of all pixels of the seam.

39. The method of claim 28, wherein said performing comprises one or more of:

applying a seam-based resizing technique, or applying an image scaling technique.