Pull to refresh

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

Reading time 7 min
Views 29K
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):
Tags:
Hubs:
+80
Comments 29
Comments Comments 29

Articles