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, используем динамическое программирование:
- Нахождение матрицы M минимальной энергии для всех возможных seams для каждого (i, j):
- Заполнить первую строку M значениями из матрицы энергии e
- Для всех строк, начиная со второй:
M[i, j] = e[i, j] + min(M[i — 1, j], M[i, j], M[i +1, j]);
- Найти минимальное значение в последней строке матрицы 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. Псевдокод продемонстрирован ниже:
- T(0, 0) = 0;
- Инициализируем значения 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);
} - Инициализируем значения TBM на границе:
for all j { T(0, j) = 1; }
for all i { T(0, i) = 0; } - Заполнить 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);
} - Находим путь из 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
Автор: Kirill_Lykov
