Project 2 / Image Resizing by Seam Carving / Razieh Toony

GIF-4105/7105 Photographie Algorithmique by Jean-François Lalonde

1 - Seam Carving

To reduce size of images, there are 3 methods are used commonly: cropping, scaling down and re-targeting. However, downsizing by cropping and scaling may cause some visual discomfort but what if you could alter an image's proportions with respect to its content, altering the least noticeable parts of the image rather than cropping from the edges or stretching the whole thing?
This is exactly the capacity provided by a technique called Seam Carving.Seam carving or Content-Aware Image Resizing (CAIR) is an algorithm for image resizing. It establishes the number of seams, connected paths of low energy pixels ,that are determined by magnitude of gradient in an image and automatically removes seams to reduce image size or inserts seams to extend it
Seam Carving was originally published in a 2007 paper by Shai Avidan and Ariel Shamir. .

1.2 - Algorithm

There are several methods to measure the energy of pixels, for example gradient magnitude, entropy and visual saliency.Here I used the gradient magnitude


Original image
Gradient Image


The next step of this algorithm is to take energy map and define a path of minimum energy cost either from top to bottom or from left to right. Each pixel in this path must be connected to a pixel either directly below ,left, or right. For each pixel in each row, the Min cost path to get to that pixel is that pixel's weight plus the minimum of the three pixels above it. Back tracing can then be done starting at the minimum weight pixel at the bottom, to determine what the seam path was.Once the Min seam has been found, the final step is to remove it. This requires shifting all pixels to the right of it over one to the left, and then deleting the final row.

2 - Implementation`s Result

2.1 - Seam carving vertically and horizontally

Original image
Carving vertically
Carving horizontally

Original image
Carving vertically
Carving horizontally

Original image
Carving vertically
Carving horizontally

Original image
Carving vertically
Carving horizontally

Original image
Carving vertically
Carving horizontally

Original image
Carving vertically
Carving horizontally

Original image
Carving vertically
Carving horizontally

Original image
Carving vertically
Carving horizontally

Original image
Carving vertically
Carving horizontally

Original image
Carving vertically
Carving horizontally

As we can see above, the seam carving algorithm works pretty well in most of images but sometimes it damaged the image,the reason is that, if we have high textural image especially in the unimportant sections since the gradient magnitude will be pretty high for those parts compared with less textural ones. Therefore, seam carving it, the background was not carved as we hoped, instead it removed the parts that it should not.


2.2 - Image Enlarging

I implemented image enlarging by finding the the seam with lowest energy and average it with their left and right neighbours separately (or top and bottom neighbours when inserting horizontal seams).If we just find only one optimal seam and repeat it m times ( m is the size we want to expand), the output image will be creepy because we just choose that seam every time.

Original image
Expanding vertically
Expanding horizontally

Therefore ,we need use m optimal seams to expand the image.


Original image
Expanding vertically
Expanding horizontally

2.2.1 - Result Images


Original image
Expanding vertically
Expanding horizontally

Original image
Expanding vertically
Expanding horizontally

Original image
Expanding vertically
Expanding horizontally

Original image
Expanding vertically
Expanding horizontally

Original image
Expanding vertically
Expanding horizontally

2.3 - Remove Object

Similarly, objects can be deleted from an image by negatively weighting parts of the gradient value matrix. I made a real time user-defined mask and after getting the original energy matrix, I changed the energy values under the mask to negative value and did seam carving until all pixels under the mask were removed. Then I enlarged the image to its original size by inserting seams.
Original image
Removing object
Expanded image

Original image
Removing object
Expanded image

Original image
Removing object
Expanded image

Original image
Removing object
Expanded image

Original image
Removing object
Expanded image
Object removing will be failed when the background of objects which we want to be removed , has high energy therefore the output results will be less realistic.

2.4 - Protect Object

Since the algorithm is based entirely on the gradients of pixels. To protect a specific object in the image we can define a user-controlled mask same as previous section, which can be used to manually select an object to protect just by putting high cost for their corresponding values in gradient matrix.
Original image
Conventional Carving (Vertically)
Protecting Object (Carving Vertically)

Original image
Conventional Carving (horizontally)
Protecting Object (Carving horizontally)

Conventional Carving (Vertically)
Protecting Object (Carving Vertically)