Seam carving algorithm for resizing images

  • Tutorial
Seam carving is an algorithm for resizing images that saves important content and removes less significant. It was described in an article by S. Avidan & A. Shamir . It gives a better result than the usual stretching of the image because it does not change the proportions of the significant elements of the image. The two photos below demonstrate the operation of the algorithm - the original image has a size of 332x480, while the modified one by seam carving'om 272x400.


In this article, I will describe the operation of the algorithm using pseudocode and Matlab code. The original article written by me in English is available here , the source code on the github .

Image energy

In order to simplify the presentation, I will describe only the case of reducing the size of the image. Enlarging a picture is a similar process.
The idea of ​​the algorithm is to remove content that is of less importance to the user (contains less information). We will call the measure of this information “energy”. As such a function, we can use the gradient of the image in space l1:
If the picture has 3 channels, then as the gradient of the whole image we use the sum of the gradients of each channel. The matlab code below demonstrates this approach:
function res = energyRGB(I)
% returns energy of all pixelels
% e = |dI/dx| + |dI/dy|
    res = energyGrey(I(:, :, 1)) + energyGrey(I(:, :, 2)) + energyGrey(I(:, :, 3));
end
function res = energyGrey(I)
% returns energy of all pixelels
% e = |dI/dx| + |dI/dy|
    res = abs(imfilter(I, [-1,0,1], 'replicate')) + abs(imfilter(I, [-1;0;1], 'replicate'));
end

And this is how the result of applying the energy function to the image used looks like:


Seam

If we remove pixels with a minimum energy but an arbitrary position, the image will be corrupted. If we remove columns / columns with minimum energy, then unwanted artifacts will appear. Here, by column, I mean {(i, j) | j is fixed}, and under the column {(i, j) | i fixed}. The solution to the dilemma is to introduce a generalization of the concept of column / column.
Formally, let I be an nxm image, then we call it vertical seam ,
where x: [1, .., n] -> [1, .., m]. That is, vertical seam is the path from the top of the image to the bottom such that the path length is the image width, and for each element (i, j) belonging to seam, the next element can only be (i + 1, j-1), (i +1, j), (i + 1, j +1). Similarly, we can introduce horizontal seam. Examples of vertical and horizontal seams are shown below:


We are interested in seams with minimal energy.
To find such a seam, we use dynamic programming:
  1. Finding the matrix M of minimum energy for all possible seams for each (i, j):
    • Fill the first row M with values ​​from the energy matrix e
    • For all lines, starting from the second:
      M [i, j] = e [i, j] + min (M [i - 1, j], M [i, j], M [i +1, j]);

  2. Find the minimum value in the last row of the matrix M and build a path from this pixel to the first row, choosing at each step a pixel with minimal energy (similarly, for (i, j), consider the values ​​of M in the positions [i - 1, j], [i , j], [i + 1, j]).

For efficiency reasons, in Matlab code I represent seam using the nxm bit matrix. If the pixel belongs to seam, it is labeled 0, otherwise 1.
function [optSeamMask, seamEnergy] = findOptSeam(energy)
% finds optimal seam
% returns mask with 0 mean a pixel is in the seam
    % find M for vertical seams
    % for vertical - use I`
    M = padarray(energy, [0 1], realmax('double')); % to avoid handling border elements
    sz = size(M);
    for i = 2 : sz(1)
        for j = 2 : (sz(2) - 1)
            neighbors = [M(i - 1, j - 1) M(i - 1, j) M(i - 1, j + 1)];
            M(i, j) = M(i, j) + min(neighbors);
        end
    end
    % find the min element in the last raw
    [val, indJ] = min(M(sz(1), :));
    seamEnergy = val;
    optSeamMask = zeros(size(energy), 'uint8');
    %go backward and save (i, j)
    for i = sz(1) : -1 : 2
        %optSeam(i) = indJ - 1;
        optSeamMask(i, indJ - 1) = 1; % -1 because of padding on 1 element from left
        neighbors = [M(i - 1, indJ - 1) M(i - 1, indJ) M(i - 1, indJ + 1)];
        [val, indIncr] = min(neighbors);
        seamEnergy = seamEnergy + val;
        indJ = indJ + (indIncr - 2); % (x - 2): [1,2]->[-1,1]]
    end
    optSeamMask(1, indJ - 1) = 1; % -1 because of padding on 1 element from left
    optSeamMask = ~optSeamMask;
end

To find the horizontal seam, just pass the transposed energy matrix to the findOptSeam function.

Finding the best seams removal order

So, now we can find the minimum seam and using the code below we can remove it from the image:
function [optSeamMask, seamEnergy] = findOptSeam(energy)
% finds optimal seam
% returns mask with 0 mean a pixel is in the seam
    % find M for vertical seams
    % for vertical - use I`
    M = padarray(energy, [0 1], realmax('double')); % to avoid handling border elements
    sz = size(M);
    for i = 2 : sz(1)
        for j = 2 : (sz(2) - 1)
            neighbors = [M(i - 1, j - 1) M(i - 1, j) M(i - 1, j + 1)];
            M(i, j) = M(i, j) + min(neighbors);
        end
    end
    % find the min element in the last raw
    [val, indJ] = min(M(sz(1), :));
    seamEnergy = val;
    optSeamMask = zeros(size(energy), 'uint8');
    %go backward and save (i, j)
    for i = sz(1) : -1 : 2
        %optSeam(i) = indJ - 1;
        optSeamMask(i, indJ - 1) = 1; % -1 because of padding on 1 element from left
        neighbors = [M(i - 1, indJ - 1) M(i - 1, indJ) M(i - 1, indJ + 1)];
        [val, indIncr] = min(neighbors);
        seamEnergy = seamEnergy + val;
        indJ = indJ + (indIncr - 2); % (x - 2): [1,2]->[-1,1]]
    end
    optSeamMask(1, indJ - 1) = 1; % -1 because of padding on 1 element from left
    optSeamMask = ~optSeamMask;
end

This set of operations is already enough to resize the image in width or height, while maintaining important details - just delete how many horizontal and vertical seams are needed.
But what if we need to simultaneously reduce the size of the image vertically and horizontally? How to understand at each iteration what is better in terms of minimizing energy - to remove vertical seam or horizontal?
This problem can again be solved using dynamic programming. Let n 'and m' be the desired image size (n '<n, m' <m). We introduce the matrix T, which determines for each n 'x m' the cost of the optimal sequence of removal of vertical and horizontal seams. For convenience, we introduce r = n - n ', m = m - m', which describe the number of vertical and horizontal removals. In addition to T, we introduce a TBM matrix of size rxc, which for each T (i, j) stores 0 or 1, depending on whether we came to T (i, j) by removing the vertical (1) or horizontal (0) seam. The pseudocode is shown below:
  1. T (0, 0) = 0;
  2. We initialize the values ​​of T at the boundary:
    for all j {
        T (0, j) = T (0, j - 1) + E (seamVertical);
    }
    for all i {
        T (i, 0) = T (j - 1, 0) + E (seamHorizontal);
    }
  3. We initialize the TBM values ​​at the boundary:
    for all j {T (0, j) = 1; }
    for all i {T (0, i) = 0; }
  4. Fill in T and TBM:
    for i = 2 to r {
        imageWithoutRow = image;
        for j = 2 to c {
            energy = computeEnergy (imageWithoutRow);

            horizontalSeamEnergy = findHorizontalSeamEnergy (energy);
            verticalSeamEnergy = findVerticalSeamEnergy (energy);
            tVertical = T (i - 1, j) + verticalSeamEnergy;
            tHorizontal = T (i, j - 1) _ horizontalSeamEnergy;
            if (tVertical <tHorizontal) {
                T (i, j) = tVertical;
                transBitMask (i, j) = 1
            } else {
                T (i, j) = tHorizontal;
                transBitMask (i, j) = 0
            }
            // move from left to right - delete vertical seam
            imageWithoutRow = removeVerticalSeam (energy);
        }

        energy = computeEnergy (image);
        image = removeHorizontalSeam (energy);
    }
  5. We find the path from T (r, c) to T (1, 1), deleting a row or column depending on the value of TBM (i, j).

And the implementation on Matlab:
function [T, transBitMask] = findTransportMatrix(sizeReduction, image)
% find optimal order of removing raws and columns
    T = zeros(sizeReduction(1) + 1, sizeReduction(2) + 1, 'double');
    transBitMask = ones(size(T)) * -1;
    % fill in borders
    imageNoRow = image;
    for i = 2 : size(T, 1)
        energy = energyRGB(imageNoRow);
        [optSeamMask, seamEnergyRow] = findOptSeam(energy');
        imageNoRow = reduceImageByMask(imageNoRow, optSeamMask, 0);
        transBitMask(i, 1) = 0;
        T(i, 1) = T(i - 1, 1) + seamEnergyRow;
    end;
    imageNoColumn = image;
    for j = 2 : size(T, 2)
        energy = energyRGB(imageNoColumn);
        [optSeamMask, seamEnergyColumn] = findOptSeam(energy);
        imageNoColumn = reduceImageByMask(imageNoColumn, optSeamMask, 1);
        transBitMask(1, j) = 1;
        T(1, j) = T(1, j - 1) + seamEnergyColumn;
    end;
    % on the borders, just remove one column and one row before proceeding
    energy = energyRGB(image);
    [optSeamMask, seamEnergyRow] = findOptSeam(energy');
    image = reduceImageByMask(image, optSeamMask, 0);
    energy = energyRGB(image);
    [optSeamMask, seamEnergyColumn] = findOptSeam(energy);
    image = reduceImageByMask(image, optSeamMask, 1);
    % fill in internal part
    for i = 2 : size(T, 1)
        imageWithoutRow = image; % copy for deleting columns
        for j = 2 : size(T, 2)
            energy = energyRGB(imageWithoutRow);
            [optSeamMaskRow, seamEnergyRow] = findOptSeam(energy');
            imageNoRow = reduceImageByMask(imageWithoutRow, optSeamMaskRow, 0);
            [optSeamMaskColumn, seamEnergyColumn] = findOptSeam(energy);
            imageNoColumn = reduceImageByMask(imageWithoutRow, optSeamMaskColumn, 1);
            neighbors = [(T(i - 1, j) + seamEnergyRow) (T(i, j - 1) + seamEnergyColumn)];
            [val, ind] = min(neighbors);
            T(i, j) = val;
            transBitMask(i, j) = ind - 1;
            % move from left to right
            imageWithoutRow = imageNoColumn;
        end;
        energy = energyRGB(image);
        [optSeamMaskRow, seamEnergyRow] = findOptSeam(energy');
         % move from top to bottom
        image = reduceImageByMask(image, optSeamMaskRow, 0);
    end;
end


Conclusion

The algorithm works well on landscape images, see gif demonstrating the algorithm in dynamics (thanks shara ):
image
But as it is, it is not suitable for portraits or images full of details. On landscape images, the sky or the sea contains little information, and the image, as a rule, is reduced due to them. If you take an image containing a lot of small details, then the algorithm will not give the best result (an example is taken from the article by Avidan & A. Shamir):

Without the participation of the user, seam carving should not be applied to portrait photographs, since a significant object for us - a person - contains less information from the point of view of seam carving:

The algorithm can be used to remove marked objects from the image (an example is taken from Avidan & A. Shamir):

Also popular now: