Seam-based reduction and expansion of images using parallel processing of retargeting matrix strips

• US 8,180,177 B1
• Filed: 10/13/2008
• Issued: 05/15/2012
• Est. Priority Date: 10/13/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Intwala, Chintan
• Primary Examiner(s): Zarka, David
• Application Number:
  US12/250,406
• Time in Patent Office: 1,310 Days
• Field of Search: 382/298
• 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

Systems, methods, and computer-readable storage media for resizing images using seam carving techniques may access a pre-computed retargeting matrix for an input image that associates each pixel of the input image with a cost order of a horizontal and/or vertical seam of which the pixel is a part. The retargeting matrix may be divided into sub-matrices corresponding to horizontal or vertical strips of the image, in the direction of a desired seam carving operation, for parallel processing on multiple processors or threads thereof. The retargeting matrix and/or sub-matrices may be usable in performing one or more reduction or expansion operations on the input image without re-computation of the matrices between retargeting iterations. The methods may include pre-computing the retargeting matrix and/or sub-matrices. The methods may be implemented as stand-alone applications or as program instructions implementing components of a graphics application, executable by a CPU and/or GPU configured for parallel processing.

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 a retargeting matrix for an image, wherein the retargeting matrix is a data structure comprising an indication of a cost order for each of a plurality of seams in the image, wherein a seam represents a monotonic path of pixels from one edge of the image to the opposite edge of the image, wherein the pixels included in each seam are dependent on the respective energy values of the pixels, and wherein in the retargeting matrix the indication of the cost order for each seam is associated with each of the pixels of the seam;

dividing the retargeting matrix into a plurality of sub-matrices, wherein each sub-matrix comprises the indication of the cost order for each seam of a subset of the plurality of seams in a respective portion of the image, and wherein each subset of the plurality of seams comprises two or more seams;

identifying, in each of two or more of the plurality of sub-matrices, any pixels associated with an indication of a lowest-cost seam in the image; and

removing or replicating the identified pixels in the image to produce a resized version of the image;

wherein said identifying and said removing or replicating are performed independently and concurrently on the one or more processors for each of the two or more of the plurality of sub-matrices.

2. The system of claim 1, wherein the retargeting matrix further comprises, for each pixel of the image, one or more of:

an identifier of a seam of which it is a part, and a cost of the seam of which it is a part.

3. The system of claim 1, wherein the retargeting matrix further comprises, for each of the plurality of seams in the image, one or more of:

an identifier of the seam, a cost of the seam, and an identifier of each pixel of the seam.

4. The system of claim 1,

wherein the lowest-cost seam is a lowest-cost horizontal seam in the image;

and

wherein each respective portion of the image comprises a horizontal strip of the image.

5. The system of claim 1,

wherein the lowest-cost seam is a lowest-cost vertical seam in the image;

and

wherein each respective portion of the image comprises a vertical strip of the image.

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

identifying, in another two or more of the plurality of sub-matrices, any additional pixels associated with an indication of the lowest-cost seam in the image; and

removing or replicating the additional pixels in the image to produce the resized version of the image;

wherein said identifying any additional pixels and said removing or replicating the additional pixels are performed independently and concurrently on the one or more processors for each of the other two or more of the plurality of sub-matrices.

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

identifying, in each of the two or more of the plurality of sub-matrices, any pixels associated with an indication of a next lowest-cost seam in the image; and

removing or replicating the identified pixels of a next lowest-cost seam in the image to produce a further resized version of the image.

8. The system of claim 1,

wherein the program instructions are further executable to implement:

receiving user input indicating a request to resize the image; and

wherein said accessing, said dividing, said identifying, and said removing or replicating are performed in response to said receiving.

9. The system of claim 8,

wherein in response to receiving user input indicating a request to reduce the size of the image, said removing or replicating the identified pixels in the image comprises removing the identified pixels.

10. The system of claim 8,

wherein in response to receiving user input indicating a request to expand the image, said removing or replicating the identified pixels in the image comprises replicating the identified pixels and inserting the replicated pixels into the image.

11. The system of claim 8,

wherein the program instructions are further executable to implement:

receiving user input indicating a second request to resize the image; and

repeating said identifying and said removing or replicating in response to said receiving user input indicating the second request.

12. The system of claim 1, wherein the cost order of each of the plurality of seams in the image 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, and a maximum value of the respective energy values of all pixels of the seam.

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

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

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

accessing a retargeting matrix for an image, wherein the retargeting matrix is a data structure comprising an indication of a cost order for each of a plurality of seams in the image, wherein a seam represents a monotonic path of pixels from one edge of the image to the opposite edge of the image, wherein the pixels included in each seam are dependent on the respective energy values of the pixels, and wherein in the retargeting matrix the indication of the cost order for each seam is associated with each of the pixels of the seam;

dividing the retargeting matrix into a plurality of sub-matrices, wherein each sub-matrix comprises the indication of the cost order for each seam of a subset of the plurality of seams in a respective portion of the image, and wherein each subset of the plurality of seams comprises two or more seams;

identifying, in each of two or more of the plurality of sub-matrices, any pixels associated with an indication of a lowest-cost seam in the image; and

removing or replicating the identified pixels in the image to produce a resized version of the image;

wherein said identifying and said removing or replicating are performed independently and concurrently for each of the two or more of the plurality of sub-matrices.

15. The storage medium of claim 14, wherein the retargeting matrix further comprises, for each pixel of the image, one or more of:

an identifier of a seam of which it is a part, and a cost of the seam of which it is a part.

16. The storage medium of claim 14, wherein the retargeting matrix further comprises, for each of the plurality of seams in the image, one or more of:

an identifier of the seam, a cost of the seam, and an identifier of each pixel of the seam.

17. The storage medium of claim 14,

wherein the lowest-cost seam is a lowest-cost horizontal seam in the image;

and

wherein each respective portion of the image comprises a horizontal strip of the image.

18. The storage medium of claim 14,

wherein the lowest-cost seam is a lowest-cost vertical seam in the image;

and

wherein each respective portion of the image comprises a vertical strip of the image.

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

identifying, in another two or more of the plurality of sub-matrices, any additional pixels associated with an indication of the lowest-cost seam in the image; and

removing or replicating the additional pixels in the image to produce the resized version of the image;

wherein said identifying any additional pixels and said removing or replicating the additional pixels are performed independently and concurrently for each of the other two or more of the plurality of sub-matrices.

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

identifying, in each of the two or more of the plurality of sub-matrices, any pixels associated with an indication of a next lowest-cost seam in the image; and

removing or replicating the identified pixels of a next lowest-cost seam in the image to produce a further resized version of the image.

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

receiving user input indicating a request to resize the image; and

wherein said accessing, said dividing, said identifying, and said removing or replicating are performed in response to said receiving.

22. The storage medium of claim 21,

wherein the program instructions are further executable to implement:

receiving user input indicating a second request to resize the image; and

repeating said identifying and said removing or replicating in response to said receiving user input indicating the second request.

23. The storage medium of claim 14, wherein the cost order of each of the plurality of seams in the image 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, and a maximum value of the respective energy values of all pixels of the seam.

24. A method, comprising:

performing, by one or more computers;

accessing a retargeting matrix for an image, wherein the retargeting matrix is a data structure comprising an indication of a cost order for each of a plurality of seams in the image, wherein a seam represents a monotonic path of pixels from one edge of the image to the opposite edge of the image, wherein the pixels included in each seam are dependent on the respective energy values of the pixels, and wherein in the retargeting matrix the indication of the cost order for each seam is associated with each of the pixels of the seam;

dividing the retargeting matrix into a plurality of sub-matrices, wherein each sub-matrix comprises the indication of the cost order for each seam of a subset of the plurality of seams in a respective portion of the image, and wherein each subset of the plurality of seams comprises two or more seams;

identifying, in each of two or more of the plurality of sub-matrices, any pixels associated with an indication of a lowest-cost seam in the image; and

removing or replicating the identified pixels in the image to produce a resized version of the image;

wherein said identifying and said removing or replicating are performed independently and concurrently for each of the two or more of the plurality of sub-matrices.

25. The method of claim 24, wherein the retargeting matrix further comprises, for each pixel of the image, one or more of:

an identifier of a seam of which it is a part, and a cost of the seam of which it is a part.

26. The method of claim 24, wherein the retargeting matrix further comprises, for each of the plurality of seams in the image, one or more of:

an identifier of the seam, a cost of the seam, and an identifier of each pixel of the seam.

27. The method of claim 24,

wherein the lowest-cost seam is a lowest-cost horizontal seam in the image;

and

wherein each respective portion of the image comprises a horizontal strip of the image.

28. The method of claim 24,

wherein the lowest-cost seam is a lowest-cost vertical seam in the image;

and

wherein each respective portion of the image comprises a vertical strip of the image.

29. The method of claim 24, further comprising:

identifying, in another two or more of the plurality of sub-matrices, any additional pixels associated with an indication of the lowest-cost seam in the image; and

removing or replicating the additional pixels in the image to produce the resized version of the image;

wherein said identifying any additional pixels and said removing or replicating the additional pixels are performed independently and concurrently for each of the other two or more of the plurality of sub-matrices.

30. The method of claim 24, further comprising:

identifying, in each of the two or more of the plurality of sub-matrices, any pixels associated with an indication of a next lowest-cost seam in the image; and

removing or replicating the identified pixels of a next lowest-cost seam in the image to produce a further resized version of the image.

31. The method of claim 24, further comprising:

receiving user input indicating a request to resize the image;

wherein said accessing, said dividing, said identifying, and said removing or replicating are performed in response to said receiving.

32. The method of claim 31, further comprising:

receiving user input indicating a second request to resize the image; and

repeating said identifying and said removing or replicating in response to said receiving user input indicating the second request.

33. The method of claim 24, wherein the cost order of each of the plurality of seams in the image 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, and a maximum value of the respective energy values of all pixels of the seam.