多种基于JavaScript 的算法与数据结构，源代码

# Content-aware image resizing in JavaScript  > There is an [interactive version of this post](https://trekhleb.dev/blog/2021/content-aware-image-resizing-in-javascript/) available where you can upload and resize your custom images. ## TL;DR There are many great articles written about the *Seam Carving algorithm* already, but I couldn'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](https://github.com/trekhleb/javascript-algorithms) repo) was the fact that *Dynamic Programming (DP)* approach might be smoothly applied to solve it. And, if you're like me and still on your "learning algorithms" journey, this algorithmic solution may enrich your personal DP arsenal. So, with this article I want to do three things: 1. Provide you with an interactive **content-aware resizer** so that you could play around with resizing your own images 2. Explain the idea behind the **Seam Carving algorithm** 3. Explain the **dynamic programming approach** to implement the algorithm (we'll be using TypeScript for it) ### Content-aware image resizing *Content-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](https://perso.crans.org/frenoy/matlab2012/seamcarving.pdf) 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.  The Seam Carving algorithm'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 removal The importance of each pixel (so-called pixel'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 demo I've created the [JS IMAGE CARVER](https://trekhleb.dev/js-image-carver/) web-app (and also [open-sourced it on GitHub](https://github.com/trekhleb/js-image-carver)) that you may use to play around with resizing of your custom images. ### More examples Here are some more examples of how the algorithm copes with more complex backgrounds. Mountains on the background are being shrunk smoothly without visible seams.  The same goes for the ocean waves. The algorithm preserved the wave structure without distorting the surfers.  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's face from the background.  ## How Seam Carving algorithms works Imagine 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'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't a part of the edge.  Assuming that the color of a pixel is represented by *4* numbers (`R` - red, `G` - green, `B` - blue, `A` - alpha) we may use the following formula to calculate the color difference (the pixel energy):  Where: - `mEnergy` - *Energy* (importance) of the *middle* pixel (`[0..626]` if rounded) - `lR` - *Red* channel value for the *left* pixel (`[0..255]`) - `mR` - *Red* channel value for the *middle* pixel (`[0..255]`) - `rR` - *Red* channel value for the *right* pixel (`[0..255]`) - `lG` - *Green* channel value for the *left* pixel (`[0..255]`) - and so on... In the formula above we're omitting the alpha (transparency) channel, for now, assuming that there are no transparent pixels in the image. Later we will use the alpha cha