SEAM CARVING FOR IMAGE RESIZING

• US 20110085745A1
• Filed: 10/09/2009
• Published: 04/14/2011
• Est. Priority Date: 10/09/2009
• Status: Active Grant

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Luo, Jiebo, Miller, Rodney L., Conger, David D., Kumar, Mrityunjay
• Granted Patent: US 8,213,745 B2
• Time in Patent Office: Days
• 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

A method for modifying an input digital image having input dimensions defined by a number of input rows and input columns to form an output digital image where the number of rows or columns is reduced by one, comprising an image energy map determined from the input image; determining a seam path responsive to the image energy map; imposing constraints on the seam path; and removing pixels along the seam path to modify the input digital image.

Claims

1. A method for modifying an input digital image having input dimensions defined by a number of input rows and input columns to form an output digital image where the number of rows or columns is reduced by one, comprising using a processor to perform the steps of:

a) selecting either a horizontal seam direction to remove a row or a vertical seam direction to remove a column;

b) determining an image energy map for the input image;

c) defining a gradient threshold;

d) determining a seam path responsive to the image energy map, where the seam path is constrained such that a directional image gradient computed in a direction perpendicular to either the seam path or the seam direction is less than the gradient threshold for each pixel in the seam path; and

e) determining an output digital image by removing pixels along the seam path.

4. The method of claim 1 wherein the image energy map is computed by:

5. The method of claim 1 wherein the gradient threshold is determined responsive to a distribution of directional image gradient values.

6. The method of claim 5 wherein the gradient threshold is determined such that a specified fraction of the directional image gradients in the distribution of directional image gradient values fall below the gradient threshold.

7. The method of claim 1 wherein the directional image gradient is computed in a direction perpendicular to the seam direction and step d) further includes:

i) determining an image gradient map where the gradient is a directional image gradient computed in a direction perpendicular to the seam direction;

ii) thresholding the image gradient map with the gradient threshold to determine illegal pixel locations; and

iii) determining a seam path responsive to the image energy map, where the seam path does not pass through any illegal pixel locations.

8. The method of claim 1 wherein the input digital image is a color input digital image and the seam path is determined using a luminance image determined from the color input image.

9. A method for resizing an input digital image with an input aspect ratio to form an output digital image with an output aspect ratio where the method of claim 1 is applied repeatedly to reduce the number of input rows or input columns until the output aspect ratio is reached.

2. The method of claim I where step e) includes modifying the output digital image pixels in a neighborhood near the seam path using the values of the removed pixels.

3. The method of claim 2 where the values of output digital image pixels adjacent to the seam path are replaced by the average of the original image pixel values and the adjacent removed image pixel values.

10. A system comprising:

a data processing system; and

a memory system communicatively connected to the data processing system and storing instructions configured to cause the data processing system to implement a method for modifying an input digital image having input dimensions defined by a number of input rows and input columns to form an output digital image where the number of rows or columns is reduced by one, wherein the instructions comprise;

a) selecting either a horizontal seam direction to remove a row or a vertical seam direction to remove a column;

b) determining an image energy map for the input image;

c) defining a gradient threshold;

d) determining a seam path responsive to the image energy map, where the seam path is constrained such that a directional image gradient computed in a direction perpendicular to either the seam path or the seam direction is less than the gradient threshold for each pixel in the seam path; and

e) determining an output digital image by removing pixels along the seam path.