Oleksii Trekhleb, software engineer at Uber, recently explored the use of dynamic programming to speed up a CPU-intensive content-aware image resizing algorithm. Developers may use content-aware resizing to fit images into a variety of enclosing contexts (e.g., screen form factors, responsive layout container) while preserving the image’s key features.
A paper titled Seam Carving for Content-Aware Image Resizing explained the motivation behind content-aware image resizing as follows:
The diversity and versatility of display devices today impose new demands on digital media. […] HTML supports dynamic changes of page layout and text. Nevertheless, [… images] typically remain rigid in size and cannot deform to fit different layouts automatically. […] The size or aspect ratio of an image must change, to fit into different displays such as cell phones or PDAs, or to print on a given paper size or resolution.
Standard image scaling is not sufficient since it 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.
Content-aware image resizing thus strives to preserve the important features of an image, and perform image resizing (whether shrinking or enlarging) without distortion.
| Original image | With face detection | Without face detection |
|---|---|---|
 |
 |
 |
(Example of content-aware image resizing that preserves facial features. Image source. Algorithm implementation: Caire.)
The previous image samples are provided by Caire, an open-source Go library that uses the Pigo face detection library. The library author explained a full Go solution enabled high processing speed (Go compiles to native code) without the need of installing third-party modules.
Trekhleb proposed a JavaScript implementation that strives to remain fast by applying the same seam carving algorithm with a dynamic programming approach that reduces the time complexity from O(3^h) to O(w + h) where h and w are respectively the height and width of the image. The resulting JS IMAGE CARVER web app allows currently allows users to shrink images in the browser (downscaling):
The previous animation illustrates the fundamentals of the seam carving algorithm. The white lines (the seams) are the set of pixels of the image tagged for removal. The original paper describes the algorithm as follows:
[The seam carving algorithm] changes the size of an image by gracefully carving out or inserting pixels in different parts of the image. Seam carving uses an energy function defining the importance of pixels. A seam is a connected path of low energy pixels crossing the image from top to bottom, or from left to right. By successively removing or inserting seams we can reduce, as well as enlarge, the size of an image in both directions. For image reduction, […] we remove more of the low energy pixels and fewer of the high energy ones.
The interactive web application demonstrating the JavaScript implementation of the image resizing algorithm is available online. The interested reader who seeks additional technical details is encouraged to refer to the original blog article that contains plenty of illustrations and code samples. Both the Caire Go implementation and the JavaScript implementation of the image resizing algorithm are open-source projects distributed under the MIT license.