Hybrid seam carving and scaling of images with configurable carving tolerance

• US 8,270,766 B1
• Filed: 07/31/2008
• Issued: 09/18/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, Ǐntwala, Chintan
• Primary Examiner(s): Koziol, Stephen R
• Application Number:
  US12/183,960
• Time in Patent Office: 1,510 Days
• Field of Search: 382/100, 382/284, 382/293, 382/295, 382/300, 345/629
• US Class Current: 382/284
• 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 a hybrid resizing technique combining seam carving and image scaling techniques to reduce or expand an input image. Seam carving techniques may be used to remove or add seams of the image to perform a portion of an overall resizing operation, according to a configurable seam carving tolerance. For example, the technique may only remove and/or replicate a predetermined number or percentage of the lowest-cost seams of the image, or may only remove or replicate the number of low-cost seams needed to achieve a specified percentage of the target resizing operation. The hybrid technique may apply scaling techniques to further resize the image to achieve a target size and/or ratio for the resized image. The hybrid technique may be implemented by program instructions of an image editing application, and the seam carving tolerance may be configurable by a user.

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;

in response to initiation of a single hybrid resizing operation to be performed on an image;

accessing data representing the image;

determining a respective energy value for each pixel of the image dependent on a value associated with each pixel;

identifying a seam of the image having a lowest cost, wherein the cost of the seam is dependent on the respective energy values of pixels of the seam;

performing a resizing operation on the image along the identified seam to produce a resized version of the image, wherein said performing comprises applying a seam carving technique;

repeating said identifying and said performing for a next lowest cost seam until a specified portion of the single hybrid resizing operation for the image is achieved by the resized version of the image; and

applying a scaling technique to at least a portion of the resized version of the image to produce a further resized version of the image.

2. The system of claim 1, wherein the specified portion is dependent on one of:

a specified percentage of the single hybrid resizing operation, a specified percentage of seams of the image, or a specified number of seams of the image.

3. The system of claim 1, wherein the further resized version of the image meets a specified target size or a specified target aspect ratio.

4. The system of claim 1,

wherein the single hybrid resizing operation comprises a reduction operation;

and

wherein said performing comprises removing the pixels of the seam.

5. The system of claim 1,

wherein the single hybrid resizing operation comprises an expansion operation;

and

wherein said performing comprises replicating the pixels of the seam and inserting the replicated pixels into the image.

6. The system of claim 1, wherein the cost of the 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.

7. The system of claim 1, wherein said identifying a seam of the image having a lowest cost comprises identifying a shortest path across the image.

8. The system of claim 1, wherein said identifying a seam of the image having a lowest cost comprises applying a dynamic programming technique.

9. The system of claim 1, wherein the program instructions are further executable to implement modifying the specified portion dependent on user input.

10. The system of claim 1, wherein the scaling technique is applied uniformly across the resized version of the image.

11. The system of claim 1, wherein the scaling technique is applied to a portion of the resized version of the image comprising pixels of low priority.

12. The system of claim 1, wherein the value associated with each pixel 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.

13. The system as recited in 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).

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

in response to initiation of a single hybrid resizing operation to be performed on an image;

accessing data representing the image;

determining a respective energy value for each pixel of the image dependent on a value associated with each pixel;

identifying a seam of the image having a lowest cost, wherein the cost of the seam is dependent on the respective energy values of pixels of the seam;

performing a resizing operation on the image along the identified seam to produce a resized version of the image, wherein said performing comprises applying a seam carving technique;

repeating said identifying and said performing for a next lowest cost seam until a specified portion of the single hybrid resizing operation for the image is achieved by the resized version of the image; and

applying a scaling technique to at least a portion of the resized version of the image to produce a further resized version of the image.

15. The storage medium of claim 14, wherein the specified portion is dependent on one of:

a specified percentage of the single hybrid resizing operation, a specified percentage of seams of the image, or a specified number of seams of the image.

16. The storage medium of claim 14, wherein the further resized version of the image meets a specified target size or a specified target aspect ratio.

17. The storage medium of claim 14,

wherein the single hybrid resizing operation comprises a reduction operation;

and

wherein said performing comprises removing the pixels of the seam.

18. The storage medium of claim 14,

wherein the single hybrid resizing operation comprises an expansion operation;

and

wherein said performing comprises replicating the pixels of the seam and inserting the replicated pixels into the image.

19. The storage medium of claim 14, wherein the cost of the 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.

20. The storage medium of claim 14, wherein said identifying a seam of the image having a lowest cost comprises one or more of:

identifying a shortest path across the image, or applying a dynamic programming technique.

21. The system storage medium of claim 14, wherein the program instructions are further executable to implement modifying the specified portion dependent on user input.

22. The storage medium of claim 14, wherein the scaling technique is applied uniformly across the resized version of the image.

23. The storage medium of claim 14, wherein the scaling technique is applied to a portion of the resized version of the image comprising pixels of low priority.

24. The storage medium of claim 14, wherein the value associated with each pixel 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.

25. A computer-implemented method, comprising:

in response to initiation of a single hybrid resizing operation to be performed on an image;

accessing data representing the image;

determining a respective energy value for each pixel of the image dependent on a value associated with each pixel;

identifying a seam of the image having a lowest cost, wherein the cost of the seam is dependent on the respective energy values of pixels of the seam;

performing a resizing operation on the image along the identified seam to produce a resized version of the image, wherein said performing comprises applying a seam carving technique;

repeating said identifying and said performing for a next lowest cost seam until a specified portion of the single hybrid resizing operation for the image is achieved by the resized version of the image; and

applying a scaling technique to at least a portion of the resized version of the image to produce a further resized version of the image.

26. The method of claim 25, wherein the specified portion is dependent on one of:

a specified percentage of the single hybrid resizing operation, a specified percentage of seams of the image, or a specified number of seams of the image.

27. The method of claim 25, wherein the further resized version of the image meets a specified target size or a specified target aspect ratio.

28. The method of claim 25,

wherein the single hybrid resizing operation comprises a reduction operation;

and

wherein said performing comprises removing the pixels of the seam.

29. The method of claim 25,

wherein the single hybrid resizing operation comprises an expansion operation;

and

wherein said performing comprises replicating the pixels of the seam and inserting the replicated pixels into the image.

30. The method of claim 25, wherein the cost of the 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.

31. The method of claim 25, wherein said identifying a seam of the image having a lowest cost comprises one or more of:

identifying a shortest path across the image, or applying a dynamic programming technique.

32. The method of claim 25, further comprising modifying the specified portion dependent on user input.

33. The method of claim 25, wherein the scaling technique is applied uniformly across the resized version of the image.

34. The method of claim 25, wherein the scaling technique is applied to a portion of the resized version of the image comprising pixels of low priority.

35. The method of claim 25, wherein the value associated with each pixel 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.