The background<\/h2>\n
Let\u2019s consider the image below (Fig.1). It\u2019s a nice and clean picture with a wide open background. Now suppose that we want to make it smaller. We have two options: either to crop it, or to scale it. Cropping is limited since it can only remove pixels from the image periphery. Also advanced cropping features like smart cropping cannot resolve our issue, since it will remove the person from the left margin or will crop a small part from the castle. Certainly we do not want this to happen. Scaling also is not sufficient since it is not aware of the image content and typically can be applied only uniformly.<\/p>\n
![\"\"](\"https:\/\/esimov.com\/blog\/wp-content\/uploads\/2019\/05\/Broadway_tower_edit-1024x694.jpg\")
<\/p>\n
Fig.1: Sample image<\/p>\n
Seam carving was developed typically for this kind of use cases. It works by establishing a number of seams (a connected path of low energy pixels) crossing the image from top to down or from left to right defining the importance of pixels. By successively removing or inserting seams we can reduce or enlarge the size of the image in both directions. Fig.2. Illustrates the process.<\/p>\n
![\"\"](\"https:\/\/esimov.com\/blog\/wp-content\/uploads\/2019\/05\/carving-steps.png\")
<\/p>\n
Fig.2: The seam carving method illustrated<\/p>\n
First let\u2019s skim through the details and summarize the important steps.<\/p>\n
- \n
- An energy map (edge detection) is generated from the provided image.<\/li>\n
- The algorithm tries to find the least important parts of the image taking into account the lowest energy values.<\/li>\n
- Using a dynamic programming approach the algorithm will generate individual seams crossing the image from top to down, or from left to right (depending on the horizontal or vertical resizing) and will allocate for each seam a custom value, the least important pixels having the lowest energy cost and the most important ones having the highest cost.<\/li>\n
- Traverse the image from the second row to the last row and compute the cumulative minimum energy for all possible connected seams for each entry.<\/li>\n
- The minimum energy level is calculated by summing up the current pixel value with the lowest value of the neighboring pixels from the previous row.<\/li>\n
- Traverse the image from top to bottom (or from left to right in case of vertical resizing) and compute the minimum energy level. For each pixel in a row we compute the energy of the current pixel plus the energy of one of the three possible pixels above it.<\/li>\n
- Find the lowest cost seam from the energy matrix starting from the last row and remove it.<\/li>\n
- Repeat the process.<\/li>\n<\/ul>\n
<\/p>\n
Implementation<\/h2>\n
Seam carving can support several types of energy functions such as gradient magnitude, entropy, sobel filter, each of them having something in common: it values a pixel by measuring its contrast with its neighboring pixels. We will use the Sobel filter operator in our case. Typically in image processing the Sobel operator is used to detect image edges. It\u2019s working with an energy distribution matrix to differentiate the sensitive image information from the less sensitive ones. (Fig. 3)<\/p>\n
![\"\"](\"https:\/\/esimov.com\/blog\/wp-content\/uploads\/2019\/05\/carving-sobel-threshold.png\")
<\/p>\nFig.3: Sobel threshold applied to the original image<\/p>\n
Once we obtained the energy distribution matrix we can advance to the next step to generate individual seams of one pixel wide. We\u2019ll use a dynamic programming approach to store the results of sub-calculations in order to simplify calculating the more complex ones. For this purpose we define some setter and getter methods whose role are to set and get the pixel energy value.<\/p>\n
\n<\/iframe><\/p>\nAfter generating the energy map there are two important steps we need to follow: <\/p>\n
Traverse the image from the second row to the last one and compute the cumulative minimum energy M<\/strong><\/em> for all possible connected seams for each entry (i, j)<\/strong><\/em>. M<\/strong><\/em> is the two dimensional array of cumulative energies we are building up. The minimum energy level is calculated by summing up the current pixel value with the minimum pixel value of the neighboring pixels obtained from the previous row. This can be done via Dijkstra’s algorithm<\/a>. Suppose that we have a matrix with the following values:<\/p>\n
![\"\"](\"https:\/\/esimov.com\/blog\/wp-content\/uploads\/2019\/05\/original-matrix.png\")
<\/p>\nOriginal matrix<\/p>\n
To compute the minimum cumulative energies of the second row we start with the columns from the first row and sum up with the minimum value of the neighboring cells from the second row. After the above operation is carried out for every pixel in the second row, we go to the third row and so on.<\/p>\n
![\"\"](\"https:\/\/esimov.com\/blog\/wp-content\/uploads\/2019\/05\/Dijkstra-matrix.png\")
<\/p>\nUsing Dijkstra\u2019s algorithm to calculate the minimum energy values.<\/p>\n
\n<\/iframe><\/p>\nOnce we calculated the minimum energy values for each row, we select the last row as starting position and search for the pixel with the smallest cumulative energy value. Then we traverse up on the matrix table one row at once and again search for the minimum cumulative energy value up until the first row. The obtained values (pixels) make up the seam which should be removed.<\/p>\n
\n<\/iframe><\/p>\nTo remove the seam is only a matter of obtaining the pixel coordinates of the seam values and checking on each iteration if the processed pixel coordinates corresponds with the seams pixel values position. We can check the accuracy of our logic by drawing the removable seams on top of the image. (Fig.4)<\/p>\n
![\"\"](\"https:\/\/esimov.com\/blog\/wp-content\/uploads\/2019\/05\/red-seams.png\")
<\/p>\nFig.4: Low energy seams crossing the image<\/p>\n
\n<\/iframe><\/p>\nThe same logic can be applied to enlarge images, only this time we compute the optimal vertical or horizontal seam (s<\/strong><\/em>) and duplicate the pixels of s<\/strong><\/em> by averaging them with their left and right neighbors (top and bottom in the horizontal case).<\/p>\n
![\"\"](\"https:\/\/esimov.com\/blog\/wp-content\/uploads\/2019\/05\/final-image-resized.png\")
<\/p>\nFig.5: The final resized image<\/p>\n
Prevent face deformation with face detection<\/h2>\n
For certain content such as faces when relations between features are important, automatic face detection can be used to identify the areas that needs protection. This is an important requirement since in certain situations when sensible image regions like faces (detected by the sobel filter operator) are compressed in a small area it might happen to get distorted (see Fig.6). To prevent this, once these regions are detected we can increase the pixel intensity to a very high level before running the edge detector. This way we can assure that the sobel detector will consider these regions as important ones, which also means that they will receive high energy values.<\/p>\n
![\"\"](\"https:\/\/esimov.com\/blog\/wp-content\/uploads\/2019\/05\/face-detection.jpg\")
<\/p>\nFig.6: Resizing image with and without face detection<\/p>\n
Below you can see the seam carving algorithm in action, first checking for human faces prior resizing the image. It’s visible from the image that the seams are trying to avoid the face zone normally marked with a rectangle. And this is done with a simple trick: if face zone is detected that rectangle is marked with a white background which makes the detector to believe that it’s an area with high energy map. For face detection it was used Pigo<\/a>, another Go library developed by me.<\/p>\n
![\"\"](\"https:\/\/esimov.com\/blog\/wp-content\/uploads\/2019\/05\/seam-carving-in-action.gif\")
<\/p>\nConclusion<\/h2>\n
Seam carving is a technique which can be used on a variety of image manipulations including aspect ratio change, image retargeting, object removal or even content amplification. Also it can be seamlessly integrated with a Convolutional Neural Network which can be trained for specific object recognition, making the perfect toolset for every content delivery solution. There are other numerous possible domains this technique could be applied or even extended like video resizing or the ability for continuous resizing in real time.<\/p>\n
Of course as every technology has its limitations, like the case when the processed image is very condensed, in the sense that it does not contain \u201cless\u201d important areas, ugly artifacts might appear. Also the algorithm does not perform very well when the image albeit being not very condensed, the content is laid out in a manner that it does not permit the seams from bypassing some important parts. In certain situations by tweaking the parameters, like using a higher sobel threshold or applying a blur filter these kind of limitations could be surpassed.<\/p>\n
Source code<\/h2>\n
The code is open sourced and can be found on my Github page:<\/p>\n