Seam carving is a content-aware image resizing technique where the image is reduced in size one vertical or horizontal “seam” of pixels 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; a horizontal seam is a path of pixels connected from the left to the right with one pixel in each column. Unlike standard content-agnostic resizing techniques (such as cropping and scaling), this content-aware technique does not distort the most interest features (aspect ratio, set of objects present, etc.) of the image. Seam carving is now a core feature in Adobe Photoshop and other computer graphics applications.
My partner and I created a data type that resizes a w-by-h image using the seam-carving technique for our Algorithms and Data Structures class using these few steps:
Energy calculation: we used the dual-gradient energy function 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 energy of pixel (x,y) is defined as the square root of the sum of the squares of x and y gradients. The x-gradient is calculated by taking the square root of the sum of the squares of R, G, and B values of horizontally neighbouring pixels, while the y-gradient does the same with vertically neighbouring pixels. To handle pixels on the borders of the image, calculate energy by defining the leftmost and rightmost columns as adjacent and the topmost and bottommost rows as adjacent. Below is an example of energy calculations done on a 3-by-4 image, courtesy of the Princeton CS Department:
Here’s a visualization of the energies on a test image using ShowEnergy.java (provided to us by course staff):
Seam identification: We used 3 2D arrays with the following information to model the picture as a digraph:
- sum of one or more energy values which can then be used as “distances” to determine the graphical importance of a pixel relative to its surrounding pixels
- x-coordinate of the previous pixel analyzed, and
- energy values for every pixel
We also created a private helper function to map indices from a 2D array to corresponding indices on a 1D array so we can use an indexed Minimum Priority Queue (MinPQ) to work with pixels of the smallest energy distance.
To start, we focused on finding vertical seams. We kept dequeuing the pixel with the smallest energy values row by row until we reached the last row. When moving row-to-row, we used Dijkstra’s algorithm with the energy “distances” to ensure we are carving a seam with both low-energy pixels and low energy distance between the pixels. Once we were done (the last row has been inspected) we traced the seam from the last pixel back up to the top using our digraph structure, storing the x-value of previous pixels as we go. Once we were back at the first row, the x-values of the entire seam is complete and in order, and the seam is returned.
To find a horizontal seam, we created a private helper method to transpose the picture, found a vertical seam on that picture, and transposed the picture back.
Seams below are visualized with ShowSeams.java (a program provided to us by course staff)
Seam removal: To remove a seam, we once again consider vertical seams first and initialized a new picture with n less pixel columns than the original, where n is the number of seams to be removed. For all pixels left of a seam, we copied the original picture exactly, but for pixels right of the seam, we set the jth pixel in any row of the new picture equal to the (jth + n) pixel in the original. This bumps all pixels right of the seam n pixels to the left, effectively closing the seam.
To remove a horizontal seam, we simply transposed the image, removed the vertical seam(s), and transposed the image back.
Below is a example of the test image alongside the same image with 150 vertical seams removed:
This assignment makes use of standard libraries from the course. All code from this assignment is currently stored on a private Github repository due to course policies and may be available upon special request.