TLDR: In class, I learned the most basic version of seam carving. Then I read about the improved seam carving algorithm by the same author. I implemented both methods using numpy and hope to add them to scikit-image.
Update: PR was rejected due to patent issues: scikit-image/scikit-image#3643
But you can pip install my fork here: https://github.com/axu2/scikit-image/tree/forward-energy2
Was No. 1 on Show | Hacker News for a day.
Implementation:
Seam-carving is a content-aware image resizing technique where the image is reduced in size by one pixel of height (or width) at a time. A vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row. Unlike standard content-agnostic resizing techniques (such as cropping and scaling), seam carving preserves the most interesting features (aspect ratio, set of objects present, etc.) of the image.
Above left is the original 714-by-186 pixel image; above middle are the vertical seams; above right is the result after removing 554 vertical seams.
This technique is taught in many Data Structures courses such as:
- CS 61B at UC Berkeley
- CIS 121 at UPenn
- COS 226 at Princeton.
But these classes neglect to mention the improved seam carving algorithm, published the year after the original.
The difference between the original and the improved can be seen below after carving 200 seams on a 512-by-342 bench image.
The left is the original seam carving algorithm and the right is the improved algorithm:
It took 3 seconds using the original seam carving method and 8 seconds using the improved method, tested on a cheap Windows laptop using Anaconda Python 3.6.
The improved method preserves the gradient of the water and the bench supports much better, and the result is similar to what happens in Adobe Photoshop.
In this notebook, I will be implementing both methods using numpy and scikit-image.
I believe my implementation of the second method is more optimal than any other Python implementation I've seen on Google or GitHub, though I note more potential optimizations in the notebook that could potentially make forward energy just as fast or even faster than backwards energy as its implemented right now in scikit-image.
For more details, read the original seam carving paper and the Improved Seam Carving paper, where the above photo is from.
Both papers introduce different ways 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."
The first paper determined the energy of a pixel by looking at its 4 surrounding neighbors. (e.g. dual gradient.)
The second paper determined the energy of a pixel by looking
forward at the resulting image instead of backward at the image before removing the seam. At each step, we search for the seam whose removal inserts the minimal amount of energy into the image. These are seams that are not necessarily minimal in their energy, but will leave less artifacts in the resulting image, after removal. This coincides with the assumption that natural images are piece-wise smooth intensity surfaces, which is a popular assumption in the literature.
Calculating the three possible vertical seam step costs for pixel pi,j using forward energy. After removing the seam, new neighbors (in gray) and new pixel edges (in red) are created. In each case the cost is defined by the forward difference in the newly created pixel edges. Note that the new edges created in row i − 1 were accounted for in the cost of the previous row pixel.
The two resulting energy maps of the bench image using the two methods look like this, where higher energy pixels are brighter:
As you can see, seams will not want to pass through the bench using backwards energy, which causes severe artifacts.
Here is an image of the resulting seams and accumulated energy matrices from the paper:
