Parallel Seam Carving

Aditya Bist, Vinay Palakkode

Our final project for the course 15-418: Parallel Computer Architecture and Programming

Seam Carving is a content-aware image resizing algorithm developed by Shai Avidan, of Mitsubishi Electric Research Laboratories (MERL), and Ariel Shamir, of the Interdisciplinary Center and MERL.^[1] Check out the demo here. For the final writeup of the project, click here.

The Approach

Dynamic programming is essentially sequential. The only way to parallelize such algorithms would be making approximations based on heuristics and have a balance / trade off between quality and performance.

Our proposed algorithm would not beat the quality of image generated by classical seam carving. However, we can improve the quality of our algorithm by choosing a more sophisticated energy function which is more verbose in terms of visual salience. Eg: using Histogram of Oriented Gradients instead of simple 3x3 gradients/edge detectors.

Conventional Seam Carving

The conventional seam carving algorithm can be summarized as :

1. Compute the energy map (gradient magnitude) on a per pixel basis.
2. Compute the minimum cost table
3. Use bottom up DP as mentioned here to find a seam low energy 8-connected path
4. Resize the image matrix by removing the seam calculated above and new image matrix will be 1 pixel smaller in width.
5. Repeat 1 through 4 for the resized image obtained at step 4 (till the required number of seams are removed).

Our Seam Carving

1. Compute the energy map (gradient magnitude) on a per pixel basis.
2. Sort the energies in the first row by energy values and keep track of the indices of the points in the increasing order of the energy. This will be done only once for a given image.
3. Compute the minimum cost table: based on the number of seams required to be removed, start computing seams based on the indices obtained from step 2. i.e. Start with the lowest energy pixel in the first row and pick the next lowest for the next seem and so on.
4. In over approach, we don't recompute the energy map after removing each seam. While computing the minimum seam path, if a point in a row is used by a seam that is marked as infinity in the energy map so that multiple seams don't converge.
5. The resize happens in a single go, since we have computed all the seams in one iteration.

• Step 4 is a major approximation that avoid repetitive energy map computation after removing every seam. This is a very good optimization for a CPU only implementation. On GPU’s the embarrassingly data parallel stage of the algorithm is the repetitive energy map computation which we have avoided in the new algorithm.
• This would also mean drastic reduction in memory accesses. But since the image can fit into L2, this would n’t make huge impact in terms of latency reduction.