Variable seam replication in images with energy-weighted priority

• US 8,265,424 B1
• Filed: 07/31/2008
• Issued: 09/11/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/183,997
• Time in Patent Office: 1,503 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 variable seam replication to expand an image. Seam carving techniques may be used to identify one or more low-cost seams of an input image, and these low-cost seams may be replicated to produce a resized version of the image. A different replication factor may be applied to different ones of the low-cost seams, dependent on the average or total energy value of each seam. For example, the lowest cost seam may be replicated twice as many times as the next lowest cost seam. The replication factor applied to each seam may be dependent on the number of low-cost seams identified for replication, which may be configurable by users. A configurable look-up table may map seam costs to replication factors, and may be accessed to determine a respective replication factor to be applied to each of the identified low-cost seams.

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;

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; and

performing an expansion operation on the image along the identified seam to produce a resized version of the image, wherein said performing comprises replicating the identified seam a number of times, wherein the number of times that the identified seam is replicated is dependent on a respective one of a plurality of replication factors, wherein each of the plurality of replication factors indicates the number of times that one or more seams are to be replicated in response to being identified for an expansion operation.

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 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 respective replication factors for at least two identified seams are different.

4. The system of claim 3, wherein the program instructions are further executable to implement:

determining a number of seams for which to repeat said identifying and said performing; and

determining the respective replication factor for each identified seam dependent on the determined number of seams.

5. The system of claim 4, wherein said determining a number of seams is dependent on user input.

6. The system of claim 3, wherein the program instructions are further executable to implement modifying a respective replication factor dependent on user input.

7. The system of claim 3, wherein the respective replication factor of the lowest cost seam is greater than the respective replication factor of the next lowest cost seam.

8. The system of claim 3, wherein the program instructions are further executable to implement determining a respective replication factor for each seam dependent on a look-up table configured to map respective replication factors to seam costs or seam cost ranges.

9. 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.

10. The system of claim 1, wherein said identifying one or more seams comprises identifying a shortest path across the image.

11. The system of claim 1, wherein said identifying one or more seams comprises applying a dynamic programming technique.

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 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).

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

accessing data representing an 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; and

performing an expansion operation on the image along the identified seam to produce a resized version of the image, wherein said performing comprises replicating the identified seam a number of times, wherein the number of times that the identified seam is replicated is dependent on a respective one of a plurality of replication factors, wherein each of the plurality of replication factors indicates the number of times that one or more seams are to be replicated in response to being identified for an expansion operation.

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

16. The storage medium of claim 15, wherein the respective replication factors for at least two identified seams are different.

17. The storage medium of claim 16, wherein the program instructions are further executable to implement:

determining a number of seams for which to repeat said identifying and said performing; and

determining the respective replication factor for each identified seam dependent on the determined number of seams.

18. The storage medium of claim 17, wherein said determining a number of seams is dependent on user input.

19. The storage medium of claim 16, wherein the program instructions are further executable to implement modifying a respective replication factor dependent on user input.

20. The storage medium of claim 16, wherein the respective replication factor of the lowest cost seam is greater than the respective replication factor of the next lowest cost seam.

21. The storage medium of claim 16, wherein the program instructions are further executable to implement determining a respective replication factor for each seam dependent on a look-up table configured to map respective replication factors to seam costs or seam cost ranges.

22. The storage medium of claim 14, 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.

23. The storage medium of claim 14, wherein said identifying one or more seams comprises one or more of:

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

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:

accessing data representing an 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; and

performing an expansion operation on the image along the identified seam to produce a resized version of the image, wherein said performing comprises replicating the identified seam a number of times, wherein the number of times that the identified seam is replicated is dependent on a respective one of a plurality of replication factors, wherein each of the plurality of replication factors indicates the number of times that one or more seams are to be replicated in response to being identified for an expansion operation.

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

27. The method of claim 26, wherein the respective replication factors for at least two identified seams are different.

28. The method of claim 27, further comprising:

determining a number of seams for which to repeat said identifying and said performing; and

determining the respective replication factor for each identified seam dependent on the determined number of seams.

29. The method of claim 28, wherein said determining a number of seams is dependent on user input.

30. The method of claim 27, further comprising modifying a respective replication factor dependent on user input.

31. The method of claim 27, wherein the respective replication factor of the lowest cost seam is greater than the respective replication factor of the next lowest cost seam.

32. The method of claim 27, further comprising determining a respective replication factor for each seam dependent on a look-up table configured to map respective replication factors to seam costs or seam cost ranges.

33. The method of claim 25, 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.

34. The method of claim 25, wherein said identifying one or more seams comprises one or more of:

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

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.