Iterative selection of pixel paths for content aware image resizing

• US 8,270,771 B2
• Filed: 12/09/2008
• Issued: 09/18/2012
• Est. Priority Date: 12/09/2008
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Fillion, Claude S., Monga, Vishal, Nagarajan, Ramesh
• Primary Examiner(s): Chu, Randolph I
• Application Number:
  US12/330,879
• Publication Number:
  US 20100142853A1
• Time in Patent Office: 1,379 Days
• Field of Search: None
• US Class Current: 382/298
• CPC Class Codes: G06T 3/00 Geometric image transformations in the plane of the image

Abstract

What is disclosed is a method for iterative seam selection in an image resizing system utilizing a seam carving technique. In one embodiment, an importance map is generated for a received source image. Seams are carved through the image from one edge to an opposite edge. An energy is computed for each seam based on pixel importance values. A distance is computed from each seam to a previously selected seam. A weighting for each seam is computed using a defined weighting function and the calculated seam distances. The weighting is applied to the energy of each seam produce a revised energy for each seam. A seam is selected based on the produced revised energy. The image is resized at a location of the selected seam. The process repeats until the image has been resized to a desired target output dimension. In such a manner, unnatural image resizing results are avoided.

Claims

1. A method for content aware resizing of a digital image in an image processing system, the method comprising:

receiving an image having a plurality of pixels;

defining a weighting function based on a resizing to be performed on said image, said weighting function generating a distribution as a function of distance;

determining an importance value for each pixel in said image to generate an importance map for said image; and

repeating until a target size of said image has been achieved;

carving a plurality of pixel paths through said image, each path comprising a seam traversing said image;

calculating an energy for each seam, said seam energy being based on importance values of pixels along a same path through said importance map;

calculating a distance between each seam and a previously selected seam;

calculating a weighting for each seam using said weighting function and said calculated seam distance and applying each weighting to said seam energy to produce a revised energy for each seam;

selecting a seam based on said revised energy;

revising said importance map; and

resizing said image at a location of said selected seam.

2. The method of claim 1, further comprising:

selecting at least one image operator for said image, said image operator being responsive to changes in pixels based on image content; and

using said at least one image operator to determine an importance value for each pixel, each pixel importance value being determined with respect to neighboring pixels surrounding said pixel.

3. The method of claim 1, wherein calculating said energy for each seam comprises computing a sum of importance values of pixels in said seam path.

4. The method of claim 1, wherein said defined weighting function creates a distribution which peaks at a location of a previously removed seam and which tapers off on either side of said peak, said resizing being an image reduction operation and further comprising:

selecting a seam with a minimum revised energy;

removing said selected seam from said image; and

deleting pixel importance values from said importance map along a same path as said removed seam.

5. The method of claim 1, wherein said defined weighting function creates a distribution which has a minimum at a location of a previously added seam and which increases on either side of said minimum, said resizing being an image enlargement operation and further comprising:

selecting a seam with a maximum revised energy;

creating a new seam having a same path as said selected seam;

determining a pixel value for each pixel in said new seam;

inserting said new seam in said image at a location adjacent to said path of said selected seam;

determining an importance value for each pixel in said new seam; and

adding said determined pixel importance values to said importance map along a same path as said newly inserted seam.

6. The method of claim 1, wherein calculating a distance d between a first seam S_x1 and a second seam S_x2 comprises:

7. The method of claim 1, further comprising:

determining a number of seams to be selected to resize said image to said target size; and

repeating until said determined number of seams have been selected.

8. A system for content aware resizing of a digital image in an image processing system, the system comprising:

a memory;

a storage medium for storing data; and

a processor in communication with said storage medium and said memory, said processor executing machine readable instructions performing;

receiving an image having a plurality of pixels;

defining a weighting function based on a resizing to be performed on said image, said weighting function generating a distribution as a function of distance;

determining an importance value for each pixel in said image to generate an importance map for said image; and

repeating until a target size of said image has been achieved;

carving a plurality of pixel paths through said image, each path comprising a seam traversing said image;

calculating an energy for each seam, said seam energy being based on importance values of pixels along a same path through said importance map;

calculating a distance between each seam and a previously selected seam;

calculating a weighting for each seam using said weighting function and said calculated seam distance and applying each weighting to said seam energy to produce a revised energy for each seam;

selecting a seam based on said revised energy;

revising said importance map; and

resizing said image at a location of said selected seam.

9. The system of claim 8, further comprising:

selecting at least one image operator for said image, said image operator being responsive to changes in pixels based on image content; and

using said at least one image operator to determine an importance value for each pixel, each pixel importance value being determined with respect to neighboring pixels surrounding said pixel.

10. The system of claim 8, wherein calculating said energy for each seam comprises computing a sum of importance values of pixels in said seam path.

11. The system of claim 8, wherein said defined weighting function creates a distribution which peaks at a location of a previously removed seam and which tapers off on either side of said peak, said resizing being an image reduction operation and further comprising:

selecting a seam with a minimum revised energy;

removing said selected seam from said image; and

deleting pixel importance values from said importance map along a same path as said removed seam.

12. The system of claim 8, wherein said defined weighting function creates a distribution which has a minimum at a location of a previously added seam and which increases on either side of said minimum, said resizing being an image enlargement operation and further comprising:

selecting a seam with a maximum revised energy;

creating a new seam having a same path as said selected seam;

determining a pixel value for each pixel in said new seam;

inserting said new seam in said image at a location adjacent to said path of said selected seam;

determining an importance value for each pixel in said new seam; and

adding said determined pixel importance values to said importance map along a same path as said newly inserted seam.

13. The system of claim 8, wherein calculating a distance d between a first seam S_x1 and a second seam S_x2 comprises:

14. The system of claim 8, further comprising:

determining a number of seams to be selected to resize said image to said target size; and

repeating until said determined number of seams have been selected.

15. A computer program product for content aware resizing of a digital image in an image processing system, the computer program product comprising:

a non-transitory computer-readable medium for storing instructions that, when executed on a computer, cause the computer to perform a method comprising;

receiving an image having a plurality of pixels;

defining a weighting function based on a resizing to be performed on said image, said weighting function generating a distribution as a function of distance;

determining an importance value for each pixel in said image to generate an importance map for said image; and

repeating until a target size of said image has been achieved;

carving a plurality of pixel paths through said image, each path comprising a seam traversing said image;

calculating an energy for each seam, said seam energy being based on importance values of pixels along a same path through said importance map;

calculating a distance between each seam and a previously selected seam;

calculating a weighting for each seam using said weighting function and said calculated seam distance and applying each weighting to said seam energy to produce a revised energy for each seam;

selecting a seam based on said revised energy;

revising said importance map; and

resizing said image at a location of said selected seam.

16. The computer program product of claim 15, further comprising:

selecting at least one image operator for said image, said image operator being responsive to changes in pixels based on image content; and

using said at least one image operator to determine an importance value for each pixel, each pixel importance value being determined with respect to neighboring pixels surrounding said pixel.

17. The computer program product of claim 15, wherein calculating said energy for each seam comprises computing a sum of importance values of pixels in said seam path.

18. The computer program product of claim 15, wherein said defined weighting function creates a distribution which peaks at a location of a previously removed seam and which tapers off on either side of said peak, said resizing being an image reduction operation and further comprising:

selecting a seam with a minimum revised energy;

removing said selected seam from said image; and

deleting pixel importance values from said importance map along a same path as said removed seam.

19. The computer program product of claim 15, wherein said defined weighting function creates a distribution which has a minimum at a location of a previously added seam and which increases on either side of said minimum, said resizing being an image enlargement operation and further comprising:

selecting a seam with a maximum revised energy;

creating a new seam having a same path as said selected seam;

determining a pixel value for each pixel in said new seam;

inserting said new seam in said image at a location adjacent to said path of said selected seam;

determining an importance value for each pixel in said new seam; and

adding said determined pixel importance values to said importance map along a same path as said newly inserted seam.

20. The computer program product of claim 15, wherein calculating a distance d between a first seam S_x1 and a second seam S_x2 comprises: