The following problem appeared as an assignment in the Algorithm Course (COS 226) at Princeton University taught by Prof. Sedgewick. The following description of the problem is taken from the assignment itself.
The Seam Carving Problem
The first step is to calculate the energy of a pixel, which is a measure of its importance—the higher the energy, the less likely that the pixel will be included as part of a seam (as you will see in the next step).
In this assignment, we shall use the dual-gradient energy function, which is described below.
Computing the energy of a pixel. With the dual-gradient energy function, the energy of pixel (x,y) is given by the following:
The next step is to find a vertical seam of minimum total energy. (Finding a horizontal seam is analogous.) This is similar to the classic shortest path problem in an edge-weighted digraph, but there are three important differences:
The final step is remove from the image all of the pixels along the vertical or horizontal seam.
The following image is the original 507×284 pixel input image taken from the same assignment. The next few images and animations show the outputs of the seam carvingalgorithm implementation. The shape (the transpose of the image shape is reported) and size of the image (in terms of the memory taken by python np array as float, to store the image) is also reported for each iteration of the algorithm. As can be seen, the algorithm resizes the image by removing the minimum energy vertical (and horizontal seams) iteratively one at a time, by keeping the main objects as is.
Input Original Image
Removing the Vertical Seams
After Removing 200 Vertical Seams
Removing the Vertical and the Horizontal Seams in alternating manner
After Removing 100 Vertical Seams and 100 Horizontal Seams
The following is the original 1024×576 image of the Dakshineswar Temple, Kolkata along with the removed vertical seams with content-aware resizing.
Output image after removing 500 Vertical Seams
The next image is the original dolphin 239×200 image taken from the paper, along with the removed vertical seams with content-aware resizing.
After removing 112 Vertical Seams
The next image is the original 750×498 bird image taken from the paper, along with the removed vertical seams with content-aware resizing.
After Removing 297 Vertical Seams
The next image is the original 450×299 sea image taken from the paper, along with the removed vertical seams with content-aware resizing.
The next image is the original 628×413 cycle image taken from the paper, along with the removed vertical seams with content-aware resizing.
After Removing 99 Vertical Seams
The next image is the original 697×706 Fuji image again taken from the paper, along with the removed vertical seams with content-aware resizing.
After Removing 282 Vertical Seams
The same technique can be applied with mask to remove objects from an image. For example. consider the following image of the shoes taken from the same paper.
Let’s use a black mask to remove a shoe that we don’t want, as shown in the next figure.
Finally the vertical seams can be forced to go through the masked object, as shown in the next animation, in order to remove the masked object completely just by using context-aware resizing.
Output after removing the shoe with content-aware image resize algorithm
© 2019 Data Science Central ®
Powered by
Badges | Report an Issue | Privacy Policy | Terms of Service
You need to be a member of Data Science Central to add comments!
Join Data Science Central