html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Алгоритм 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):
Читать дальше
Twitter
Одноклассники
Мой Мир

материал с habrahabr.ru

1

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • habrahabr.ru
          • домен habrahabr.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции