DONG Yuxuan @ Aug 21, 2019
Seam carving is an algorithm for content-aware image resizing. It functions by establishing a number of seams (paths of least importance) in an image and automatically removes seams to reduce image size. Most papers about seam carving consider only finding seams, not removing them, and consider only one direction (usually finding vertical seams). If there're only vertical or horizontal seams, removing them from an image is easy. However, to fastly reduce the size of the image, we need to remove both vertical and horizontal seams simultaneously after finding them. Supposing some vertical and horizontal seams are found and two seams don't intersect if they are of the same direction, removing them is not as easy as we intuitively think. The article explains the reason and presents a simple solution.
Seam carving is an algorithm for content-aware image resizing. It functions by establishing a number of seams (paths of least importance) in an image and automatically removes seams to reduce image size. The basic idea can be demonstrated with the following image from Wikipedia^{1}:
Seam carving will find seams which are indicated by red lines:
After removing seams, we get the resulting image:
Most papers about seam carving consider only finding seams, not removing them, and consider only one direction (usually finding vertical seams). To fastly reduce the size of the image, we need to remove both vertical and horizontal seams simultaneously after finding them. This problem is not as easy as we intuitively think.
The original algorithm of seam carving^{2}^{3} can find only one seam each time but there is an improvement^{4} which can find multiple seams at one time and ensures two seams of the same direction doesn’t intersect. This article is based on the improved algorithm, discussing how to simultaneously remove these seams.
If there are only vertical or horizontal seams, removing them is simple. Taking the vertical case as an example, for any pixel (i, j)
in the input image, where i
is the row index, j
is the column index, it will be mapped to the pixel (i, j - co(i, j))
in the resulting image, where co(i, j)
is the number of vertical seams on the left of the pixel (i, j)
in the input image. Denoting the input image as x
, the resulting image as y
, and indexes starting from 0, we have:
y[i][j - co(i, j)] = x[i][j]
, for i
in [0, x.height)
, j
in [0, x.width)
, and x[i][j]
is not passed through by any seam.
Similarly, if there are only horizontal seams, we have:
y[i - ro(i, j)][j] = x[i][j]
, for i
in [0, x.height)
, j
in [0, x.width)
, and x[i][j]
is not passed through by any seam. Here ro(i, j)
is the number of horizontal seams above the pixel (i, j)
in x
.
Combining two cases, for both vertical and horizontal seams, we have:
y[i - ro(i, j)][j - co(i, j)] = x[i][j]
, for i
in [0, x.height)
, j
in [0, x.width)
, and x[i][j]
is not passed through by any seam.
However, this algorithm is not correct for two reasons. The first reason is that multiple pixels in x
may be mapped to the same pixel in y
. The second reason is that some positions in y
may not be mapped by any pixel in x
. In another word, the mapping from remained pixels in x
to pixels in y
, is neither injective nor surjective. These two reasons are not easy to see, we will show by examples below.
The example is a 4x4 image. To very microscopically observe it, we draw it as the following grids. Each grid represents a pixel of the image, and we draw seams on it, blue for the vertical, red for the horizontal. As the grids show, two pixels of the input image can be mapped to the same position. For pixel M(3, 0), there’re 2 horizontal seams above it and no vertical seams on the left of it, so we have ro[3][0] = 2
and co[3][0] = 0
, thus it will be mapped to (1, 0) in the resulting image. For pixel K(2, 2), we have co[2][2] = 2
and ro[2][2] = 1
, thus it will also be mapped to (1, 0).
Again, we take a 4x4 image presented in the following grids as an example. We label every pixel with letters and draw seams on it, blue for the vertical, red for the horizontal. Observe that every pixels right to or below F(1, 1) is removed by seams, so no pixel will be mapped to (1, 1).
Drawing the resulting image will make this more clear:
We can see that the result can not even form a rectangle.
As the mapping is neither injective nor surjective, we can modify it to make it be.
To make the mapping injective, we can randomly choose a pixel to map when we found multiple pixels are mapped to the same position. A simple strategy is to choose the most bottom-right pixel. To make this happen, we need to do nothing on the intuitive algorithm. Just run the intuitive algorithm on the input image from top to bottom, left to right.
To make the mapping surjective, we run a blank-fill algorithm after the intuitive algorithm. For position (i, j)
in y
, if it’s not mapped, we use y[i - 1][j]
or y[i][j - 1]
to fill it. Here we assume the position (0, 0) was mapped in the intuitive algorithm. The assumption is obviously true if seams don’t pass through all pixels in the input image.
This solution may not be the best one, but it’s simple and usable and works fine in a real-world web application Resize.Fun. Resize.Fun is an implementation of browser-side computing seam carving with very high performance. On my machine (1.2 GHz Intel Core m5, MacOS 10.14.6, Chrome 76), Resize.Fun can even do real-time resizing of a 1024x768 image with a slider UI.
Image: Tower – https://en.wikipedia.org/wiki/Seam_carving#/media/File:Broadway_tower_edit.jpg ↩
Shai Avidan and Ariel Shamir. 2007. Seam carving for content-aware image resizing. ACM Trans. Graph. 26, 3, Article 10 (July 2007). DOI: https://doi.org/10.1145/1276377.1276390 ↩
Avik Das. 2019. Real-world Dynamic Programming: Seam Carving ↩
Huang, H., Fu, T., Rosin, P.L. et al. Sci. China Ser. F-Inf. Sci. (2009) 52: 172. https://doi.org/10.1007/s11432-009-0041-9 ↩