Pull to refresh

Алгоритмы заливки изображений, популярно и с видео

Reading time 6 min
Views 47K

Аннотация


image
Заливка изображений — часто нужная на практике задача, суть которой — заполнить некоторую область изображения, ограниченную контуром, заданным цветом. И казалось бы все просто, однако часто медленно и криво. В данной статье рассказывается об известных алгоритмах заливки на основе стека и приводится реализация на псевдокоде MatLab. Я постарался наполнить столь скучную тему интересными видео роликами, и описал процесс их получения, опять же с использованием MatLab. В этой статье мы будем заливать Карлсона который живет на крыше, так как хабралоготипа для этих целей в нормальном разрешении я не нашел. А так же несколько строк кода о том как читать и работать с картинками в MatLab.


Предварительные сведения и предпосылки


Простым путем введем на упорядоченном наборе пар координат отношение связности или соседства. Будем различать случаи, когда точка имеет четыре соседа (Рис.1а) и случай когда у точки восемь соседей (Рис.1б).
image

Зачем это делать и что выбрать показано на рисунке 2.
image

На рисунке 2 квадратики изображают условные пиксели цифрового изображения, при этом черные пиксели описывают границу между двумя областями — верхней и нижней. Будем заливать верхнюю белую область синей краской. В случае если мы вводим только 4 соседа для точки, то синяя краска через черную границу не пройдет (Рис.2б) и нижняя область останется белой, а если использовать уже восемь соседей, то черная граница и не граница вовсе, а решето — через которое и проливается краска в нижнюю область.

Какой вид связности выбрать? На плоскости выбор небольшой — либо 4 либо 8 соседей и выбор зависит от постановки исходной задачи, однако в многомерном пространстве все сложнее, даже представить невозможно, и в статье мы рассмотрим лишь плоский случай. При этом будем рассматривать случай четырех соседей, который простым образом распространяется и на случай восьми.

image Все заметили, что картинка Карлсона, раскрашенная по моему вкусу и представлению в Paint, в аннотации статьи, залита как — то криво, на границе черный контур — цветная область — есть белые и серые, бросающиеся в глаза точки? Это произошло по той причине, что наш Карлсон совсем не в бинарном цвете а в градациях серого. Первым делом уберем этот вопиющий недостаток и бинаризуем картинку, при этом нам достаточно работать только с одним каналом — пусть будет первый — красный.
Итак:
%//Прочитаем исходную картинку
source_image = imread('karlson.bmp');
%// Взьмем из нее только первый канал
gray_image = source_image(:,:,1);
%// Бинаризуем с порогом 0.5
bim=double(im2bw(gray_image, 0.5));
%// Покажем картинку
imagesc(bim);

* This source code was highlighted with Source Code Highlighter
.

На рисунке 3 изображена нога нашего шалопая в исходном виде (Рис.3а) и после бинаризации (Рис.3б), как мы видим контур стал ожидаемо тоньше и состоит теперь только из черных точек, при этом некоторые границы пропали.
Далее мы рассмотрим два алгоритма заливки, при этом не будем программировать их рекурсивно (чтобы лишних холиваров не разводить да избежать переполнений) а развернем рекурсию в стек.
Определимся с терминологией:
  • Стартовая точка — пиксель в котором пользователь нажал подобно Point банкой с краской
  • Старый цвет — цвет заливаемой области
  • Новый цвет — цвет области после заливки.


Простой и медленный алгоритм заливки


Края изображения будем так же считать границей изображения.
Суть алгоритма проста: в текущей точке проверяем: если старый цвет — заменяем его на новый, если новый, то ничего не делаем. Затем выполняем эту же операцию для четырех соседей у которых цвет равен старому цвету.
Позволю себе один раз украсть исходный код, с рекурсивной реализацией, лишь для демонстрации сути:
//Recursive 4-way floodfill, crashes if recursion stack is full
void floodFill4(int x, int y, int newColor, int oldColor)
{
  if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
  {
    screenBuffer[x][y] = newColor; //set color before starting recursion
    
    floodFill4(x + 1, y,   newColor, oldColor);
    floodFill4(x - 1, y,   newColor, oldColor);
    floodFill4(x,   y + 1, newColor, oldColor);
    floodFill4(x,   y - 1, newColor, oldColor);
  }  
}

* This source code was highlighted with Source Code Highlighter
.

Как это будет выглядеть на Matlab да еще с имитацией стека? А вот как:
%Прочитаем исходную картинку
source_image = imread('karlson.bmp');
% Взьмем из нее только первый канал
gray_image = source_image(:,:,1);
% Бинаризуем с порогом 0.5
bim=double(im2bw(gray_image, 0.5));
% Покажем картинку
imagesc(bim);

newColor = 0.5; oldColor = 1;
point.x = 48; point.y = 234;
stack = [point];
[w h] = size(bim);
stack_size = [];
mov = avifile('karlson_fill2.avi','fps',50);
figure;
while (length(stack) ~=0)
  point = stack(1);
  stack(1) = []; % Удаляем закрашенную точку из стека  
  bim(point.x,point.y) = newColor; %Закрашиваем текущую точку
  
  if (point.x+1 <= w && bim(point.x+1,point.y) == oldColor)
    newpoint.x = point.x+1;
    newpoint.y = point.y;
    stack = [stack newpoint];
  end;
  if (point.x-1 > 0 && bim(point.x-1,point.y) == oldColor)
    newpoint.x = point.x-1;
    newpoint.y = point.y;
    stack = [stack newpoint];
  end;
  if (point.y+1 <= h && bim(point.x,point.y+1) == oldColor)
    newpoint.x = point.x;
    newpoint.y = point.y+1;
    stack = [stack newpoint];
  end;
  if (point.y-1 > 0 && bim(point.x,point.y-1) == oldColor)
    newpoint.x = point.x;
    newpoint.y = point.y-1;
    stack = [stack newpoint];
  end;
  stack_size = [stack_size length(stack)];
  imagesc(bim); colormap gray; axis image;
  F = getframe(gca); mov = addframe(mov,F); 
end;
mov = close(mov);
figure; imagesc(bim);
figure; plot(stack_size);


* This source code was highlighted with Source Code Highlighter
.

Можно сходить попить чаю, пока бровь нашего шалопая раскрашивается в серый цвет. При этом предлагаемый код нам еще и график заполненности стека на каждой итерации нарисует и мы его обсудим. А как приятный бонус кода — на выходе еще и видео ролик иллюстрирующий заполнение. Почему я выбрал такую маленькую деталь как бровь — потому что залить что-то другое, например пузо, учитывая особенности исполняемого языка Matlab, не представляется возможным за конечное время.

image
image Собственно вот какие у нас результаты получились: График заполненности стека приведен в логарифмических координатах на рисунке 5.
А голова с раскрашенной бровью изображена на рисунке 6. Видео иллюстрирующее процесс заполнения области предлагается к просмотру ниже. Все говорит нам о том, что алгоритм работает крайне медленно, посмотрите на рисунке 5 (по оси X — номер итерации, по оси Y — количество еще необработанных точек) как медленно опустошается стек (учтите логарифмические координаты), а дело все в том, что происходит слишком много лишних проверок точек. Те точки которые были залиты на предыдущем этапе все равно проверяются на следующем. Конечно же это никуда не годится. Далее мы устраним эту несправедливость! Видео файл — 50 кадров в секунду.


Алгоритм заливки — быстрый, линиями


Суть рекурсивного алгоритма:
Начинаем заполнять текущую линию от одного края до другого.
Вначале вверх из стартовой точки а затем вниз.
Возвращаемся в стартовую точку. Смотрим — если слева от стартовой точки старый цвет и нет границы, то выполняем заполнение новой линии.
Возвращаемся в стартовую точку. Смотрим — если справа от стартовой точки старый цвет и нет границы, то выполняем заполнение новой линии.

Код алгоритма:
clear all;
%Прочитаем исходную картинку
source_image = imread('karlson.bmp');
% Возьмем из нее только первый канал
gray_image = source_image(:,:,1);
% Бинаризуем с порогом 0.5
bim=double(im2bw(gray_image, 0.5));
% Покажем картинку
imagesc(bim);

newColor = 0.5; oldColor = 1;
point.x = 17; point.y = 143;
stack = [point];
[w h] = size(bim);
stack_size = []; spanLeft = 0; spanRight = 0;

mov = avifile('karlson_fill3.avi','fps',50);
figure;
while (length(stack) ~=0)
  point = stack(1);  
  stack(1) = []; % Удаляем закрашенную точку из стека
  y1 = point.y;
  
  % Находим границу слева
  while (y1 >= 1 && bim(point.x,y1) == oldColor) y1 = y1 - 1; end;
  y1 = y1 + 1;
  spanLeft = 0; spanRight = 0;
  %Топаем по строке от левой границы вправо
  while (y1 < h && bim(point.x,y1) == oldColor)
    bim(point.x,y1) = newColor; %Закрашиваем текущую точку 
    if (spanLeft == 0 && point.x > 0 && bim(point.x-1,y1) == oldColor)
      newpoint.x = point.x-1; newpoint.y = y1; stack = [stack newpoint];
      spanLeft = 1;
    elseif (spanLeft == 1 && point.x > 0 && bim(point.x-1,y1) ~= oldColor)
        spanLeft = 0;
    end;
    
    if (spanRight == 0 && point.x < w && bim(point.x+1,y1) == oldColor)
      newpoint.x = point.x+1; newpoint.y = y1; stack = [stack newpoint];
      spanRight= 1;
    elseif (spanRight == 1 && point.x < w && bim(point.x+1,y1) ~= oldColor)
      spanRight = 0;
    end;
    
    y1 = y1 + 1;
    stack_size = [stack_size length(stack)];
    imagesc(bim); colormap gray; axis image;
    F = getframe(gca); mov = addframe(mov,F); 
  end; 
end;
mov = close(mov);


* This source code was highlighted with Source Code Highlighter
.


image
На рисунке 7 у нас график заполненности стека, но уже в обычных координатах. А видео, иллюстрирующее заполнение лапы новым цветом предлагается ниже. Оно сделано так же — 50 кадров в секунду.

Как мы видим в этом случае наш стек (Рис.7) оказывается ничтожно заполненным на протяжении всей заливки, да и со скоростью мы выиграли за счет поиска с меньшей глубиной.

Заключение


В заключение хочу сказать — иллюстрируйте все, даже такие простые алгоритмы, ибо в красоте сила.
Так же прощу прощения за длинную статью и в качестве затравки для возможно следующей
статьи приведу ссылку . Там описан еще один очень интересный и очень быстрый алгоритм заливки мне незнакомый до этого. Возможно, найдется герой со свободным временем, который так же подробно и с иллюстрациями разберет этот алгоритм.
А если у кого-то ресурсы мощнее, то предлагаю все таки залить пузо Карлсону и выложить сюда ролик, а то у меня терпения не хватает пока ролик пишется. Благо для этого весь код есть.

Использованные источники


  1. Lode Vandevenne, Lode's Computer Graphics Tutorial — ссылка
  2. Раскраска про Карлсона, который живет на крыше, взята отсюда — ссылка
Tags:
Hubs:
+53
Comments 33
Comments Comments 33

Articles