Seam-based reduction and expansion of images using partial solution matrix dependent on dynamic programming access pattern

• US 8,581,937 B2
• Filed: 10/14/2008
• Issued: 11/12/2013
• Est. Priority Date: 10/14/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Intwala, Chintan
• Primary Examiner(s): Sajous, Wesner
• Assistant Examiner(s): Shin, Andrew
• Application Number:
  US12/251,163
• Publication Number:
  US 20130120407A1
• Time in Patent Office: 1,855 Days
• Field of Search: 345/620, 345/621, 345/660, 345/661, 345/666, 345/606, 345/619, 345/634, 345/635, 345501-503, 345/505, 345/506, 345/520, 345/530, 345/548, 382/254, 382/276, 382/282, 382/293, 382/298, 382/300, 382303-305, 700 1- 5, 710 20- 23, 711/100, 711118-120, 711/123, 714/1, 714/5.11, 714/6.1, 714 10- 12
• US Class Current: 345/660
• 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 include generation of a partial solution matrix by at least partially isolating dependencies between sub-problems of a dynamic programming problem corresponding to its solution within different regions of an input image. The number and/or shape of the isolated (or partially isolated) sub-problems may be dependent on the access pattern used by a dynamic programming operation to identify seams in the input image. Multiple sub-problems may be processed independently and in parallel on respective processor core(s) or threads thereof to generate the partial solution matrix. The partial solution matrix may then be processed to identify one or more low-cost seams of the input image. 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

memory coupled to the one or more processors, the memory comprising instructions executable by the one or more processors to;

resize an image in one direction by seam carving along a lowest-cost seam of the image, discovery of the lowest-cost seam comprising;

identifying a first portion of the image, having a predetermined shape, for which a partial solution to a dynamic programming problem for finding the lowest energy values of the image can be solved independent of a partial solution to the dynamic programming problem for finding the lowest energy values of a second portion of the image, the second portion of the image having the predetermined shape and not overlapping the first portion of the image;

generating a partial solution to the dynamic programming problem for finding the lowest energy values of the first portion of the image and a partial solution to the dynamic programming problem for finding the lowest energy values of the second portion of the image independently and concurrently on respective ones of the one or more processors; and

determining a solution to the dynamic programming problem for the image dependent at least in part on the partial solution to the dynamic programming problem for finding the lowest energy values of the first portion of the image and the partial solution to the dynamic programming problem for finding the lowest energy values of the second portion of the image.

2. The system of claim 1, wherein the instruction are further executable to resize the image in a second direction.

3. The system of claim 1, wherein said determining the solution to the dynamic programming problem further comprises identifying a second lowest-cost seam of the image.

4. The system of claim 1, wherein said determining a solution further comprises generating a retargeting matrix comprising an indication of a cost order of each of a plurality of seams in the image, wherein the indication is associated with each of the pixels of the seam.

5. The system of claim 1, wherein cost associated with the lowest-cost seam is dependent on one or more of:

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

6. The system of claim 1, wherein instruction are further executable to resize the image further comprises:

storing the partial solution for the first portion of the image and the partial solution for the second portion of the image in a data structure in the memory; and

wherein said determining a solution comprises accessing the data structure.

7. The system of claim 1, wherein said identifying is dependent on a pattern of accesses of partial solutions employed in solving the dynamic programming problem.

8. The system of claim 1, wherein the partial solution to the dynamic programming problem for the first or second portion of the image is dependent on a partial solution to the dynamic programming problem for a third portion of the image, the third portion having the predetermined shape and not overlapping the first or second portions.

9. The system of claim 8, wherein the generating of the partial solution for the third portion of the image occurs prior to said generating a partial solution for the first or second portion of the image.

10. The system of claim 1, the instructions further executable to:

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

wherein said identifying a portion of an image, said generating, and said determining a solution are performed in response to said receiving.

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

12. One or more tangible computer-readable storage media comprising multiple instructions stored thereon that responsive to execution by one or more processors, cause the one or more processors to:

resize an image in one direction by seam carving along a lowest-cost seam of the image, discovery of the lowest-cost seam comprising;

identifying a first portion of the image, having a predetermined shape, for which a partial solution to a dynamic programming problem for finding the lowest energy values of the image can be solved independent of a partial solution to the dynamic programming problem for finding the lowest energy values of a second portion of the image, the second portion of the image having the predetermined shape and not overlapping the first portion of the image;

generating a partial solution to the dynamic programming problem for finding the lowest energy values of the first portion of the image and a partial solution to the dynamic programming problem for finding the lowest energy values of the second portion of the image independently and concurrently; and

determining a solution to the dynamic programming problem for the image dependent at least in part on the partial solution to the dynamic programming problem for finding the lowest energy values of the first portion of the image and the partial solution to the dynamic programming problem for finding the lowest energy values of the second portion of the image.

13. The one or more tangible computer-readable storage media of claim 12, the instructions being configured to resize the image in a second direction.

14. The one or more tangible computer-readable storage media of claim 12, wherein said determining the solution to the dynamic programming problem further comprises identifying a second lowest-cost seam of the image.

15. The one or more tangible computer-readable storage media of claim 12, wherein said determining a solution further comprises generating a retargeting matrix comprising an indication of a cost order of each of a plurality of seams in the image, wherein the indication is associated with each of the pixels of the seam.

16. The one or more tangible computer-readable storage media of claim 12, the instructions being configured to:

store the partial solution for the first portion of the image and the partial solution for the second portion of the image in a data structure in the memory; and

wherein said determining a solution comprises accessing the data structure.

17. The one or more tangible computer-readable storage media of claim 12, wherein said identifying is dependent on a pattern of accesses of partial solutions employed in solving the dynamic programming problem.

18. The one or more tangible computer-readable storage media of claim 12, wherein the partial solution to the dynamic programming problem for the first or second portion of the image is dependent on a partial solution to the dynamic programming problem for a third portion of the image, the third portion having the predetermined shape and not overlapping the first or second portions.

19. The one or more tangible computer-readable storage media of claim 18, the instructions being configured to, prior to said generating a partial solution for the first or second portion of the image, generating a partial solution for the third portion of the image.

20. The one or more tangible computer-readable storage media of claim 12, the instructions being configured to:

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

wherein said identifying a portion of an image, said generating, and said determining a solution are performed in response to said receiving.

21. A computer-implemented method for resizing an image in one direction by seam carving along a lowest-cost seam of the image comprising:

identifying a first portion of the image, having a predetermined shape, for which a partial solution to a dynamic programming problem for finding the lowest energy values of the image can be solved independent of a partial solution to the dynamic programming problem for finding the lowest energy values of a second portion of the image, the second portion of the image having the predetermined shape and not overlapping the first portion of the image;

generating a partial solution to the dynamic programming problem for the first portion of the image and a partial solution to the dynamic programming problem for finding the lowest energy values of the second portion of the image independently and concurrently; and

determining a solution to the dynamic programming problem for the image dependent at least in part on the partial solution to the dynamic programming problem for finding the lowest energy values of the first portion of the image and the partial solution to the dynamic programming problem for finding the lowest energy values of the second portion of the image.

22. The method of claim 21, further comprising, resizing the image in a second direction.

23. The method of claim 21, wherein said determining the solution to the dynamic programming problem further comprises identifying a second lowest-cost seam of the image.

24. The method of claim 21, wherein said determining a solution further comprises generating a retargeting matrix comprising an indication of a cost order of each of a plurality of seams in the image, wherein the indication is associated with each of the pixels of the seam.

25. The method of claim 21, further comprising:

storing the partial solution for the first portion of the image and the partial solution for the second portion of the image in a data structure in the memory;

wherein said determining a solution comprises accessing the data structure.

26. The method of claim 21, wherein said identifying is dependent on a pattern of accesses of partial solutions employed in solving the dynamic programming problem.

27. The method of claim 21, wherein the partial solution to the dynamic programming problem for the first or second portion of the image is dependent on a partial solution to the dynamic programming problem for a third portion of the image, the third portion having the predetermined shape and not overlapping the first or second portions.

28. The method of claim 27, further comprising:

prior to said generating a partial solution for the first or second portion of the image, generating a partial solution for the third portion of the image.

29. The method of claim 21, further comprising:

receiving user input indicating a request to resize the image;

wherein said identifying a portion of an image, said generating, and said determining a solution are performed in response to said receiving.