<p>16 April, 202111 min to read </p> <p> Background image byIan DooleyTL;DRThere are many great articles written about the Seam Carving algorithm already, but I couldn&#8217;t resist the temptation to explore this elegant, powerful, and yet simple algorithm on my own, and to write about my personal experience with it. Another point that drew my attention (as a creator of javascript-algorithms repo) was the fact that Dynamic Programming (DP) approach might be smoothly applied to solve it. And, if you&#8217;re like me and still on your &#8220;learning algorithms&#8221; journey, this algorithmic solution may enrich your personal DP arsenal.So, with this article I want to do three things:Provide you with an interactive content-aware resizer so that you could play around with resizing your own imagesExplain the idea behind the Seam Carving algorithmExplain the dynamic programming approach to implement the algorithm (we&#8217;ll be using TypeScript for it)Content-aware image resizingContent-aware image resizing might be applied when it comes to changing the image proportions (i.e. reducing the width while keeping the height) and when losing some parts of the image is not desirable. Doing the straightforward image scaling in this case would distort the objects in it. To preserve the proportions of the objects while changing the image proportions we may use the Seam Carving algorithm that was introduced by Shai Avidan and Ariel Shamir.The example below shows how the original image width was reduced by 50% using content-aware resizing (left image) and straightforward scaling (right image). In this particular case, the left image looks more natural since the proportions of the balloons were preserved. </p> <p> The Seam Carving algorithm&#8217;s idea is to find the seam (continuous sequence of pixels) with the lowest contribution to the image content and then carve (remove) it. This process repeats over and over again until we get the required image width or height. In the example below you may see that the hot air balloon pixels contribute more to the content of the image than the sky pixels. Thus, the sky pixels are being removed first.Finding the seam with the lowest energy is a computationally expensive task (especially for large images). To make the seam search faster the dynamic programming approach might be applied (we will go through the implementation details below).Objects removalThe importance of each pixel (so-called pixel&#8217;s energy) is being calculated based on its color (R, G, B, A) difference between two neighbor pixels. Now, if we set the pixel energy to some really low level artificially (i.e. by drawing a mask on top of them), the Seam Carving algorithm would perform an object removal for us for free.JS IMAGE CARVER demoI&#8217;ve created the JS IMAGE CARVER web-app (and also open-sourced it on GitHub) that you may use to play around with resizing of your custom images. You may also try its embed version below right away! This widget uses the Seam Carving algorithm that we&#8217;re going to explore in this article.Content Aware Image ResizerWidth%Height%Resized image Original image Mask to removeMore examplesHere are some more examples of how the algorithm copes with more complex backgrounds.Mountains on the background are being shrunk smoothly without visible seams. </p> <p> The same goes for the ocean waves. The algorithm preserved the wave structure without distorting the surfers. </p> <p> We need to keep in mind that the Seam Carving algorithm is not a silver bullet, and it may fail to resize the images where most of the pixels are edges (look important to the algorithm). In this case, it starts distorting even the important parts of the image. In the example below the content-aware image resizing looks pretty similar to a straightforward scaling since for the algorithm all the pixels look important, and it is hard for it to distinguish Van Gogh&#8217;s face from the background. </p> <p> How Seam Carving algorithms worksImagine we have a 1000 x 500 px picture, and we want to change its size to 500 x 500 px to make it square (let&#8217;s say the square ratio would better fit the Instagram feed). We might want to set up several requirements to the resizing process in this case:Preserve the important parts of the image (i.e. if there were 5 trees before the resizing we want to have 5 trees after resizing as well).Preserve the proportions of the important parts of the image (i.e. circle car wheels should not be squeezed to the ellipse wheels)To avoid changing the important parts of the image we may find the continuous sequence of pixels (the seam), that goes from top to bottom and has the lowest contribution to the content of the image (avoids important parts) and then remove it. The seam removal will shrink the image by 1 pixel. We will then repeat this step until the image will get the desired width.The question is how to define the importance of the pixel and its contribution to the content (in the original paper the authors are using the term energy of the pixel). One of the ways to do it is to treat all the pixels that form the edges as important ones. In case if a pixel is a part of the edge its color would have a greater difference between the neighbors (left and right pixels) than the pixel that isn&#8217;t a part of the edge. </p> <p> Assuming that the color of a pixel is represented by 4 numbers (R &#8211; red, G &#8211; green, B &#8211; blue, A &#8211; alpha) we may use the following formula to calculate the color difference (the pixel energy): </p> <p> Where:mEnergy &#8211; Energy (importance) of the middle pixel ([0..626] if rounded)lR &#8211; Red channel value for the left pixel ([0..255])mR &#8211; Red channel value for the middle pixel ([0..255])rR &#8211; Red channel value for the right pixel ([0..255])lG &#8211; Green channel value for the left pixel ([0..255])and so on&#8230;In the formula above we&#8217;re omitting the alpha (transparency) channel, for now, assuming that there are no transparent pixels in the image. Later we will use the alpha channel for masking and for object removal. </p> <p> Now, since we know how to find the energy of one pixel, we can calculate, so-called, energy map which will contain the energies of each pixel of the image. On each resizing step the energy map should be re-calculated (at least partially, more about it below) and would have the same size as the image.For example, on the 1st resizing step we will have a 1000 x 500 image and a 1000 x 500 energy map. On the 2nd resizing step we will remove the seam from the image and re-calculate the energy map based on the new shrunk image. Thus, we will get a 999 x 500 image and a 999 x 500 energy map.The higher the energy of the pixel the more likely it is a part of an edge, and it is important for the image content and the less likely that we need to remove it.To visualize the energy map we may assign a brighter color to the pixels with the higher energy and darker colors to the pixels with the lower energy. Here is an artificial example of how the random part of the energy map might look like. You may see the bright line which represents the edge and which we want to preserve during the resizing. </p> <p> Here is a real example of the energy map for the demo image you saw above (with hot air balloons). </p> <p> The widget below renders the energy map during resizing. You may play around with your custom images and see how the energy map would look like.Content Aware Image Resizer with Energy MapWidth%Height%Resized image Original image Mask to removeWe may use the energy map to find the seams (one after another) with the lowest energy and by doing this to decide which pixels should be ultimately deleted. </p> <p> Finding the seam with the lowest energy is not a trivial task and requires exploring many possible pixel combinations before making the decision. We will apply the dynamic programming approach to speed it up.In the example below, you may see the energy map with the first lowest energy seam that was found for it. </p> <p> In the examples above we were reducing the width of the image. A similar approach may be taken to reduce the image height. We need to &#8220;rotate&#8221; the approach though:start using top and bottom pixel neighbors (instead of left and right ones) to calculate the pixel energywhen searching for a seam we need to move from left to right (instead of from up to bottom)Implementation in TypeScriptYou may find the source code, and the functions mentioned below in the js-image-carver repository.To implement the algorithm we will be using TypeScript. If you want a JavaScript version, you may ignore (remove) type definitions and their usages.For simplicity reasons let&#8217;s implement the seam carving algorithm only for the image width reduction.Content-aware width resizing (the entry function)First, let&#8217;s define some common types that we&#8217;re going to use while implementing the algorithm.<br /> type ImageSize = { w: number, h: number }; </p> <p>type Coordinate = { x: number, y: number }; </p> <p>type Seam = Coordinate[]; </p> <p>type EnergyMap = number[][]; </p> <p>type Color = [<br /> r: number,<br /> g: number,<br /> b: number,<br /> a: number,<br /> ] | Uint8ClampedArray;On the high level the algorithm consists of the following steps:Calculate the energy map for the current version of the image.Find the seam with the lowest energy based on the energy map (this is where we will apply Dynamic Programming).Delete the seam with the lowest energy seam from the image.Repeat until the image width is reduced to the desired value.type ResizeImageWidthArgs = {<br /> img: ImageData,<br /> toWidth: number,<br /> }; </p> <p>type ResizeImageWidthResult = {<br /> img: ImageData,<br /> size: ImageSize,<br /> }; </p> <p>export const resizeImageWidth = (<br /> { img, toWidth }: ResizeImageWidthArgs,<br /> ): ResizeImageWidthResult = > { </p> <p> const size: ImageSize = { w: img.width, h: img.height }; </p> <p> const pxToRemove = img.width &#8211; toWidth;<br /> if (pxToRemove { </p> <p> const seamsEnergies: (SeamPixelMeta | null)[][] = matrix(w, h, null); </p> <p> for (let x = 0; x</p>