Алгоритм seam carving для изменения размера изображения

  • Tutorial
Seam carving это алгоритм для изменения размера картинки, сохраняющий важный контент и удаляющий менее значимый. Он был описан в статье S. Avidan & A. Shamir. Он дает лучший результат, чем обычное растягивание изображения ввиду того, что не меняет пропорций значимых элементов изображения. Две фотографии ниже демонстрируют работу алгоритма – исходное изображение имеет размер 332x480, в то время как модифицированное seam carving'ом 272x400.


В данной статье я опишу работу алгоритма используя псевдокод и код Matlab. Оригинал статьи, написанный мной на английском доступен тут, исходный код на гитхабе.

Энергия изображения

В целях упрощения изложения, я буду описывать только случай уменьшения размера изображения. Увеличение картинки – схожий процесс.
Идея алгоритма в том, чтобы удалять контент который имеет меньшее значения для пользователя (содержит меньше информации). Мы назовем меру этой информации “энергией”. В качестве такой функции, мы можем использовать градиент изображения в пространстве l1:
Если картинка имеет 3 канала, то в качестве градиента всего изображения используем сумму градиентов каждого канала. Matlab код ниже демонстрирует этот подход:
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

А так выглядит результат применения функции энергии используемому изображению:


Seam

Если мы удалим пиксели с минимальной энергией, но произвольной позицией, то изображение будет испорчено. Если мы удалим колонки/столбцы с минимальной энергией, то появятся нежелательные артефакты. Здесь под колонкой я подразумеваю {(i, j)| j зафиксированно}, а под столбцом {(i, j)| i зафиксированно}. Решение дилеммы – ввести обобщение понятия колонка/столбец.
Формально, пусть I это nxm изображение, тогда назовем вертикальным seam ,
где x: [1,..,n]->[1,..,m]. То есть вертикальный seam это путь от верха изображения до низа такой, что длинна пути это ширина изображения, и для каждого элемента (i, j), принадлежащего seam, следующий элемент может быть только (i+1, j-1), (i+1, j), (i+1, j +1). Аналогично, мы можем ввести горизонтальный seam. Примеры вертикальных и горизонтальный seams показаны ниже:


Нас интересуют seams с минимальной энергией
Чтобы найти такой seam, используем динамическое программирование:
  1. Нахождение матрицы M минимальной энергии для всех возможных seams для каждого (i, j):
    • Заполнить первую строку M значениями из матрицы энергии e
    • Для всех строк, начиная со второй:
      M[i, j] = e[i, j] + min(M[i — 1, j], M[i, j], M[i +1, j]);

  2. Найти минимальное значение в последней строке матрицы M и построить путь из этого пикселя до первой строки, выбирая на каждом шаге пискель с минимальной энергией (аналогично, для (i, j) рассматривать значения M в позициях [i — 1, j], [i, j], [i + 1, j]).

В целях эффективности, в Matlab коде я представляю seam с помощью nxm битовой матрицы. Если пиксель принадлежит seam, он помечен 0, иначе 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

Для того, чтобы найти горизонтальный seam, просто передайте транспонированную матрицу энергии в функцию findOptSeam.

Нахождение оптимального порядка удаления seams

Итак, теперь мы умеем находить минимальный seam и с помощью кода ниже можем удалить его из изображения:
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

Этого набора операций уже достаточно, для того чтобы изменять размер изображения в ширину или в высоту, сохраняя важные детали – просто удаляем сколько нужно горизонтальные и вертикальные seams.
Но что если нам нужно одновременно уменьшить размер изображения по вертикали и по горизонтали? Как понять на каждой итерации что лучше в терминах минимизации энергии — удалить вертикальный seam или горизонтальный?
Эта проблема снова может быть решена с помощью динамического программирования. Пусть n' и m' — желаемый размер изображения (n’ < n, m’ < m). Введем матрицу T, которая определяет для каждого n’ x m’ стоимость оптимальной последовательности удаления вертикальный и горизонтальных seams. В целях удобства введем r = n – n’, m = m – m’, которые описывают количество вертикальных и горизонтальных удалений. В добавок к T, введем матрицу TBM размера r x c, которая для каждого T(i, j) хранит 0 или 1 в зависимости от того пришли мы в T(i, j) путем удаления вертикального (1) или горизонтального (0) seam. Псевдокод продемонстрирован ниже:
  1. T(0, 0) = 0;
  2. Инициализируем значения T на границе:
    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. Инициализируем значения TBM на границе:
    for all j { T(0, j) = 1; }
    for all i { T(0, i) = 0; }
  4. Заполнить T и 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. Находим путь из T(r, c) в T(1, 1), удаляя строку или колонку в зависимости от значения TBM(i, j).

И реализация на 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


Заключение

Алгоритм работает хорошо на ландшафтных изображениях, см. gif демонстрирующий работу алгоритма в динамике (спасибо shara):
image
Но как есть он плохо подходит для портретов или изображений насыщенных деталями. На ландшафтных изображениях небо или море — содержит мало информации, и изображение, как правило, уменьшается за счет них. Если же взять изображение содержащее много мелких деталей, то алгоритм даст не лучший результат (пример взят из статьи Avidan & A. Shamir):

Без участия пользователя не следует применять seam carving к портретным фотографиям, так как значимый для нас объект — человек — содержит меньше информации с точки зрения seam carving:

Алгоритм может быть применен для удаления помеченных объектов с изображения (пример взят из статьи Avidan & A. Shamir):
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 29

    –9
    Кажется, нет смысла приводить полотнища исходников, если есть ссылка на гитхаб.
    Статья выглядит отталкивающе из-за своих объёмов :)
    А по сути интересно, спасибо.
      +5
      Была уже хорошая статья по этому алгоритму, правда картинки к ней не сохранились.
      habrahabr.ru/post/48518/
        +12
        И с картинками есть!
          +3
          восстановил большинство картинок в исходной статьи.
        0
        Задача актуальна.
        На сколько сильно ест процессор?
        А есть что-то такое для image magick?
          +1
          Другое название liquid scaling. Для PHP php.net/manual/en/imagick.liquidrescaleimage.php, необходима liblqr для ImageMagick, другими словами решение видимо существует.
          +1
            +1
            Загружает процессор сильно, так как использовано динамическое программирование. Было бы интересно вместо него использовать какой-то вероятностный алгоритм поиска локального минимума, который бы работал при этом намного быстрее.
            +6
            Полезно показать гифку, как изменяется размер скажем от 500*500 до 300*400 пикселей.
            В динамике хорошо видно как это происходит — за счет чего изображение сжимается.
            Еще можно упомянуть, что в фотошопе это называется Content-Aware Scale. В гимпе тоже есть.
              +2
              В ImageMagick называется Liquid Scale.
                +15


                Тоже стало интересно посмотреть анимацию.
                jMas, спасибо за imagemagick, не знал что он так умеет.
                Kirill_Lykov, можете добавить мой gif в статью.

                Сделай сам [:|||:]
                #!/bin/bash
                 
                for i in {100..005..5}
                  do
                    echo "Frame width $i"
                    convert "original.jpg" -liquid-rescale "${i}x100%" "scaled/$i.png"
                    convert "scaled/$i.png" -resize "x240" "frames/$i.png"
                 done
                 
                echo "Making gif..."
                convert -delay 40 -dispose 2 "frames/*.png" \ 
                        -reverse "frames/*.png" -loop 0 "animate.gif"
                +1
                А если вместо довольно сложного «Seam» метода просто придать веса значимости пикселям как функцию от энергии, и использовать один из стандартных методов масштабирования с учётом этих весов?
                  0
                  В статье есть сравнение результатов в этим подходом.
                  +2
                  Хорошо бы для наглядности рядом две картинки: первая — обычное сжатие, второе — seam carving одного размера. А то на фото сверху — ну сжали и сжали, paint так тоже может, кажется :-)
                    +1
                    Здесь может быть и увеличение. Речь идет об изменении aspect ratio, так что части изображения сохраняют неискаженный вид.
                    Меньше неба, больше суши, рисунки на песке остались той же формы.
                    0
                    Спасибо за проделанную работу. Очень интересно.
                    Однако, у меня есть два коварных и неприятных вопроса :)

                    1. Почему у вас энергия — это мера информации? Энергия — это без сомнения информация с философской точки зрения, но ее мера — это обычно энтропия.

                    2. Почему вы называете свой критерий «энергией»? Приведенная функция пропорциональна норме вектора градиента. Я бы ее скорее назвал частотой. Во всяком случае, на частоту данный параметр похож куда больше, чем на энергию или энтропию.

                    PS: Это не попытка докопаться :) Мне действительно интересно, почему так. И я буду очень рад, если смогу разобраться в вашей логике, даже если окажусь где-то не прав :)
                    • UFO just landed and posted this here
                        0
                        Это не я. Это авторы статьи. Вообще, в computer vision часто называют вещи терминами из физики. Видимо, люди которые работают по этой теме пришли из этой области. Можете попробовать, кстати, другие варианты подсчета энергии и посмотреть что получится.
                        0
                        Возможно это не из-за алгоритма, но из достаточно четкой картинки на выходе получилось мыло
                          0
                          На самом деле не все так просто. На многих изображениях поиск минимальной энергии находит совсем не те участки. Например, человек (желательно в какой-нибудь однотонной одежде) на фоне кустов.
                            0
                            Да, я знаю. В этом случае надо помечать более важные пискели в ручную. Либо, если есть информация о глубине — например с Kinect — то можно усложнить функцию придавая более близким объектам большую энергию, нежели более удаленным.
                            +2
                            Этот алгоритм был темой одного из практических заданий в курсе Algorithms, Part II. Одно из моих любимых заданий.
                              0
                              Получается, при довольно сильном уменьшении перспектива может исказиться — картинка уменьшится, а человечки останутся прежними.
                                +8
                                Видео с примером работы (может, кому-то интересно будет):
                                  0
                                  Было интересно, спасибо. :)
                                  +1
                                  В свое время писал курсач по этой теме
                                    +1
                                    Я понимаю суть алгоритма, и знаю, что по другому не могло быть, может я не оригинален, но почему человек на последнем фото держит оторванную руку?
                                      +3
                                      Может потому что Япония?

                                    Only users with full accounts can post comments. Log in, please.