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.

Summary

We are going to create optimized implementations of image seam-carving on both NVIDIA GPU and multi-core x86 CPU platforms. We are also trying to come up with an algorithm which can switch between content aware (seam carving) and content agnostic (bilinear interpolation) retargeting after inspecting some global statistics of the image.

Background

Standard interpolation based image scaling is oblivious to the image content and typically can be applied only uniformly. Cropping is limited since it can only remove pixels from the image periphery. More effective resizing can only be achieved by considering the image content and not only geometric constraints. Seam carving is such an image retargeting algorithm. A seam is an optimal 8-connected path of pixels on a single image from top to bottom, or left to right, where optimality is defined by an image energy function. By repeatedly carving out or inserting seams in one direction we can change the aspect ratio of an image.[2]

Comparing aspect ratio change. From left to right in the bottom: the image resized using seam removals, scaling and cropping.[2]

Seam Carving consists of two compute intense stages viz energy function computation and seam map computation.

  • Energy function is quantitative measure of visual information/content. Although seam carving can support several types of energy functions such as gradient magnitude, entropy, visual salience etc, we choose gradient magnitude. Energy function, e1(I) is defined over the image I as -

  • A vertical seam is an 8-connected path of pixels in the image from top to bottom, containing one, and only one, pixel in each row of the image. Given an energy function e,the optimal seam can be found using dynamic programming. The first step is to traverse the image from the second row to the last row and compute the cumulative minimum energy M for all possible connected seams for each entry (i, j):

Challenges

  • The default seam carving algorithm uses dynamic programming for the seam map computation, which is not GPU friendly and there is very low computation to communication ratio.
  • In order to speed up this algorithm, we definitely have to make approximations which would result in degradation of the retargeted image quality (aka. result in visual artifacts). Since there is no groundtruth for us to compare the modified algorithms ouputs to, defining an evaluation metrics for us is as challenging as optimizing the baseline algorithm itself (if not more)
  • Creating a test dataset (input images) with different energy distributions/patterns so as to see the extent of artifacts introduced by the approximations.

Resources

  • We would like to use the GHC machine with NVIDIA GTX 780 (GHC 41) and one of our personal machines with a GTX 750 for benchmarking the GPU implementation.
  • We will use a MacBook Pro "Core i7" 2.8 15-Inch (Mid-2014 Retina Display) which features a 22 nm "Haswell/Crystalwell" 2.8 GHz Intel "Core i7" processor (4980HQ), with four independent processor "cores" on a single silicon chip, a 6 MB shared level 3 cache, 16 GB of onboard 1600 MHz DDR3L SDRAM, 512 GB of PCIe-based flash storage for the CPU implementation.
  • The reference algorithm is Seam Carving for Content-Aware Image Resizing.

Goals and Deliverables

  • Implementation and analysis of the performance of the seam caving (like) algorithm on NVIDIA GTX 750 using the x86(Haswell) implementation as the baseline.
  • We will illustrate the test cases / scenarios where this algorithms performs well without sacrificing the quality of the output significantly. We will also report the negative test cases.
  • As a nice to have feature, we will propose a hybrid algorithm which would choose either content aware or content agnostic retargeting to produce a good quality retargeted image.

Here is the final writeup.