An optimized and improved implementation of the seam-carving algorithm (Shamir and Avidan, Mitsubishi Labs, 2007) to create faster renders and provide real-time previews.
Red lines in the image above represent the least energy pixel path in each frame that was removed/added
See what makes this implementation so efficient
A basic GUI application (JavaFX + Java, packaged as an executable) that displays real-time, interactable renders from the algorithms implemented in this project.
Click here to download the executable application
Simply run the .exe file, click the 'Load image' button, and then move the slider around once the image is loaded.
Note: Render speed varies by processing power of the computer you're using. For real-time previews, it is recommended to use an image that is no larger than 1500w x 800h
The seam carving algorithm dynamically assigns a weight to all the pixels in an image based on an 'energy' formula and then finds a vertical path of pixels with the least total weight. If the image is to be downscaled this path is removed, else if the image is to be upscaled the path is duplicated. This enables resizing of the image with the least amount of disruption to the contents of the image.
For a more detailed explanation of the original algorithm, please see this document.
This implementation uses the improved forward-energy formula as described in this paper. The forward-energy critereon is known to produce better results over the original energy formula, especially whith images that contain horizontal lines:
// TODO example
This implementation leverages Dijkstra's shortest-path algorithm to calculate vertical paths of the least energy/weight through the image. Here's a brief explanation of how this is used in this implementation:
- Assign energy/weight values to all pixels in the image using an energy critereon
- Work top-down to create a matrix of cumulative energy values for each pixel in the image. As the Cumulative Energy matrix is populated, keep track of the paths followed in a Backtracking matrix.
- Once the Cumulative Energy matrix and the Backtracking matrix are both populated, find the entry in the last row of the Cumulative Energy matrix with the least cumulative energy, and use the Backtracking matrix to find the path upwards
This version achieves significantly faster renders by caching the seams in order of least to most energy. Here is the difference in steps between this and the original algorithm:
The original algorithm iterates through all the pixels in the image after each iteration of removing pixels. This is unneccesary since most of the information within the image remains unchanged, and only a part of the pixels in the image need to be 'updated'. Here are the optimizations between the original algorithm and this implementation, specifically regarding updating the positions and energies of pixels after each iteration of pixel removal.
When the image is imported, the pixel RGB data is stored in an EnergyMatrix class with an underlying 2D ArrayList<ArrayList> object that has O(1) time complexity for adding/getting elements. This allows accessing and updating image data with O(1) time complexity. This is a powerful performance gain for this algorithm since it depends heavily on dynamically manipulating the pixel data in the image.
O(1) removal/addition of pixel from image by 'disabling/enabling' pixels rather than removing/adding
While the use of 2D ArrayLists allows for adding/updating pixels form the image in constant/O(1) time, removing pixels would still be in linear time/O(n) since ArrayLists' remove() method works in linear time.
However, this implementation still manages to remove pixels in constant time/O(1) by 'disabling' pixels in the image rather than actually removing them from the ArrayList. 'Disabling' a pixel involves setting a property on the Pixel object (by calling setActive()) which is an O(1) operation. Then, when the 2D ArrayList is to be exported as an image, we check for disabled pixels (isActive()), which is also in constant time, and ignore them when producing the BufferedImage object. This way, we can 'remove' pixels from the image in constant time.
Using the setActive() and isActive() methods of the Pixel object, we can non-desctruvtively 'remove' pixels from the 2D EnergyMatrix by disabling them. This has another advantage - it allows us to undo any pixel removals without reverse calculating.
If you try out the GUI application linked above, you will notice that if you drag the slider back and forth the pixels that were removed from the image are added back in exactly the same place (we undo the pixel removal) without data-loss. This is not easily possible with the original algorithm as pixels that are once removed cannot be 're-calculated' and 're-positioned' back in the right place. You would have to start again from the original image and crop the number of pixels that you want.
However, since this implementation never really removes the pixels from the 2D EnergyMatrix, adding them back in is simply a matter of reactivating them in the ArraList object.
// TODO Slider resizing
Updating pixel arrays is a data-parallel task that this algorithm performs for arrays that can have up to millions of elements (one pixel is one element). These kind of tasks can benefit greatly in performance by leveraging the numerous cores of a GPU. More information on GPU computation can be found here
Pull requests are more than welcome!