Method for Retargeting Images

• US 20080267528A1
• Filed: 07/10/2008
• Published: 10/30/2008
• Est. Priority Date: 03/06/2007
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Avidan, Shmuel, Shamir, Ariel
• Granted Patent: US 7,477,800 B2
• Time in Patent Office: Days
• US Class Current: 382/276
• 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 method for content-aware image retargeting generates an energy image from a source image according to an energy function. From the energy image, one or more seams are determined according to a minimizing function such that each seam has a minimal energy. Each seam is applied to the source image to obtain a target image that preserves content and a rectangular shape of the source image.

Claims

1. A computer-implemented method for content-aware image retargeting of a source image having pixels, comprising the steps of:

generating an energy image from the source image, in which each pixel in the energy image is assigned an energy of the corresponding pixel in the source image according to an energy function;

determining, from the energy image, a seam of pixels in the energy image that has a minimal energy according to a minimizing function, in which the minimal energy seam is one pixel wide and extends from one side of the energy image to an opposite side of the energy image; and

applying the minimal energy seam to the source image to obtain a target image that preserves a rectangular shape of the source image.

2. The method of claim 1, in which pixels in the source image similar to neighboring pixels have a low energy, and pixels in the source image dissimilar to neighboring pixels have a high energy.

3. The method of claim 1, in which the energy function determines a gradient magnitude for each pixel in the source image and assigns the gradient magnitude as the energy of the corresponding pixel in the energy image.

4. The method of claim 1, in which the energy function is

5. The method of claim 1, in which the energy function determines an entropy for each pixel in the source image and assigns the entropy as the energy of the corresponding pixel in the energy image.

6. The method of claim 1, in which the source image is of size n×

m pixels, the pixels in the source image are indexed in a vertical dimension by indices i=1, . . . , n, and in a horizontal dimension by indices j=1, . . . , m, and in which a vertical seam s^x is;

s^x={s_i^x}_i=1ⁿ={(x(i),i)}_i=1ⁿ,s.t.∀

i,|x(i)−

x(i−

1)≦

1,

where x is a mapping x;

[1, . . . , n]→

[1, . . . , m], and a horizontal seam s^y is;

s^y={s_j^y}_j=1^m={(j,y(j))}_j=1^m,s.t.∀

j|y(j)−

y(j−

1)≦

1,

where y is a mapping y;

[1, . . . , m]→

[1, . . . , n].

7. The method of claim 6, in which the pixels I of the vertical seams s are

I_s={I(s_i)}_i=1ⁿ={I(x(i),i)}_i=iⁿ,

and, given an energy function e, the energies E of the vertical seams are

E(s)=E(I_s)=Σ

_i=1ⁿe(I(s_i)),

and the minimal energy seam s* is

8. The method of claim 1, in which the energy function is

9. The method of claim 1, in which the minimal energy seam is determined using dynamic programming.

10. The method of claim 1, in which the applying decreases a size of the source image by removing the pixels in the source image corresponding to the pixels in the minimal energy seam.

11. The method of claim 1, in which the applying increases a size of the source image by averaging the pixels in the source image corresponding to the pixels in the minimal energy seam with neighboring pixels and duplicating the averaged pixels in the target image.

12. The method of claim 1, further comprising the steps of:

marking pixels associated with an object in the source image;

determining a minimal energy seam including pixels corresponding the marked pixels; and

removing the pixels in the source image corresponding to the pixels in the minimal energy seam.

13. The method of claim 1, in which the generating, determining, and applying is performed successively for multiple horizontal and vertical minimal energy seams according to an objective function.

14. The method of claim 13, further comprising the steps of:

storing an optimal order of the successive generating, determining, and applying.

15. The method of claim 14, in which an optimal order of successive horizontal and vertical minimal energy seam applications is determined using

16. A computer-implemented method for content-aware image retargeting of a source image having pixels, comprising the steps of:

generating an energy image from the source image, in which each pixel in the energy image is assigned an energy of the corresponding pixel in the source image according to an energy function;

determining, from the energy image, a seam of pixels in the energy image that has a minimal energy according to a minimizing function, in which the minimal energy seam is one pixel wide and extends from one side of the energy image to an opposite side of the energy image;

applying the minimal energy seam to the energy image to obtain a next energy image; and

reconstructing a target image from the next energy image that preserves a rectangular shape of the source image.

17. The method of claim 16, in which the reconstructing uses a Poisson solver.

18. A computer-implemented method for real-time content-aware image retargeting of a source image having pixels, comprising the steps of:

determining an order of minimal energy seam applications, the determining further comprising;

generating an energy image from the source image according to an energy function, in which each pixel in the energy image is assigned an energy of the corresponding pixel in the source image;

determining, from the energy image, a seam of pixels in the energy image that has a minimal energy according to a minimizing function, in which the minimal energy seam is one pixel wide and extends from one side of the energy image to an opposite side of the energy image; and

applying the minimal energy seam to the source image to obtain a next source image that preserves a rectangular shape of the source image; and

repeating the generating, determining, and applying for the next source image to determine the order of minimal energy seam applications;

enlarging the source image using minimal energy seam applications to obtain an enlarged source image;

constructing an index map having entries, each entry in the index map corresponding to a pixel in the enlarged source image and having an index number, the index number corresponding to the order of minimal energy seam applications;

selecting a particular index number corresponding to a desired size of a target image; and

producing the target image of the desired size from the enlarged source image using the index map and the particular index number.

19. The method of claim 18, further comprising the steps of:

constructing a horizontal index map and a horizontal enlarged source image to enable real-time image retargeting of the source image in the horizontal dimension;

constructing a vertical index map and a vertical enlarged source image to enable real-time image retargeting of the source image in the vertical dimension; and

associating the horizontal and vertical index maps and the horizontal and vertical enlarged source images with the source image.

20. The method of claim 18, in which the minimal energy seam applications use zero-connected minimal energy seams, and further comprising the steps of:

determining an order of minimal energy seam applications in a first dimension that produces a first plurality of target images from the source image;

determining an order of minimal energy seam applications in a second dimension, such that each zero-connected minimal energy seam in the second dimension intersects the zero-connected minimal energy seams in the first dimension only once;

enlarging the source image using minimal energy seam applications to obtain an enlarged source image;

constructing a first index map having entries, each entry in the index map corresponding to a pixel in the enlarged source image and having a first index number, the first index number corresponding to the order of minimal energy seam applications in the first dimension;

constructing a second index map having entries, each entry in the index map corresponding to a pixel in the enlarged source image and having a second index number, the second index number corresponding to the order of minimal energy seam applications in the second dimension; and

selecting a particular first index number and a particular second index number corresponding to a desired size of a target image; and

producing a target image of the desired size from the enlarged source image using the first and second index maps, the particular first index number, and the particular second index number.