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

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


В данной статье я опишу работу алгоритма используя псевдокод и код 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