## Improving region-bound seam carving

I found this small research paper (PDF, 11.7 MB) that I wrote last year about seam carving, colloquially known as ‘content-aware image resizing’, lingering on my laptop. Last year, I did some research on how to improve the original seam carving method devised by Shai Avidan and Ariel Shamir. If you’re not familiar with seam carving, you should definitely watch this video.

One way to improve seam carving is by partitioning an image into separate regions, or ‘region-bound seam carving’ as we dubbed it. Seams can then be bound to horizontal or vertical regions to make sure that they follow a relatively straight path. Region-bound seam carving performed quite well, but left room for improvement as well. That’s why I came up with 2-dimensional region-bound seam carving.

In regular region-based seam carving, an image with width $n$ and height $m$, each pixel $p_{x,y}$ can be assigned a horizontal and vertical region class $R_{x}$ and $R_{y}$ using the following formulae:

$R_{x}(p_{x,y}) = \frac{1}{r} \lfloor \frac{r}{n} \displaystyle\sum\limits_{i=0}^{n-1} e_{local}(p_{i,y}) \rfloor$
$R_{y}(p_{x,y}) = \frac{1}{r} \lfloor \frac{r}{m} \displaystyle\sum\limits_{i=0}^{m-1} e_{local}(p_{x,i}) \rfloor$.

($e_{local}$ is a simple energy function that is further explained in my paper, and $r$ is the number of different region classes that you want to assign.)

To improve this method, I decided to introduce 2-dimensional regions. With this method, the region class of any pixel of an image with the same dimensions as above can be calculated using $R'$ using the following formula:

$R'(p_{x,y}) = \frac{1}{r} \lfloor r \cdot e_{local}(p_{x,y}) \rfloor$.

Such regions will look like this (original image above, 2-dimensional regions below):

The concept is even easier than it looks! If you’re interested, my paper will show you that the results are better and that it’s computationally cheaper so go read it. 😉