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

Довольно давно реализовывал данный алгоритм на Java для заполнения BufferedImage — столкнулся с указанной в статье проблемой и еще парой других. Впрочем результат после пары-тройки оптимизаций работает очень даже.

Возможно чуть позже, когда к самому заполнению допишу часть алгоритма для сглаживания границ заполнения (а-ля то, что делает Photoshop), стоит разместить в отдельную статью?

В любом случае данная статья будет весьма полезна для тех, кто не в курсе что и как :)

Спасибо, вспомнил как писал такое на лабораторках в универе.
Оба способа реализовывал.
На первом даже по-моему Паскаль иногда падал с Stack Overflow :), на больших картинках.

Немного оффтопик не все же. Всегда было интересно, кто быстрее Matlab иди Python. В Python реализовывал заливку и работало все довольно быстро (не надо было уходить пить чай).

О, вспомнил БК0010, там заливка форм такая же медленная была, интересно было наблюдать как заполняются сложные формы, а окажить дырочка между линиями, то весь экран заливался краской =)

Статья хорошая и присутствие видео тоже радует. Только я одного момента понять не могу:

y1 = point.y;
  
  % Находим границу слева
  while (y1 >= 1 && bim(point.x,y1) == oldColor) y1 = y1 - 1; end;
  y1 = y1 + 1;

Почему границу слева? Ведь цикл идет по вертикальной координате у. Тогда и получится должна граница сверху. Хотя на видео все правильно рисуется о_О
Ну и мелочи: рисуется в стандартном Paint а не Point и

% Бинаризуем с порогоМ 0.5

Скажите, а существуют более быстрые алгоритмы заливки? (не думая о их реализации)

Почему я выбрал такую маленькую деталь как бровь — потому что залить что-то другое, например пузо, учитывая особенности исполняемого языка Matlab, не представляется возможным за конечное время.

Вот после таких «алгоритмов» и рождаются мифы о медленности Matlab.

stack = [stack newpoint];

Этой строчкой создается новый массив, соответственно с выделением памяти, ясно, что это очень медленно, в новых версиях Matlab это давно подчеркивается как проблемный участок.

Переписав ваш первый листинг с предварительным резервированием памяти у меня получилось время выполнения 3 секунды против 140, ускорение более чем в 40 раз.

ALLOC_SIZE = 1000;
stack = struct();
stack.data(ALLOC_SIZE).x = 0;
stack.data(ALLOC_SIZE).y = 0;
%stack.data = zeros(ALLOC_SIZE , 1);
stack.data(1) = [point];

function stack = stack_push(stack, value)
if length(stack.data)>stack.pointer
stack.pointer = stack.pointer + 1;
stack.data(stack.pointer) = value;
else
stack.data = [stack.data value];
end

function [stack value] = stack_pop(stack)
if stack.pointer>=1
value = stack.data(stack.pointer);
stack.pointer = stack.pointer - 1;
else
stack.data = [stack.data value];
end



Крайне рекомендую ознакомиться со статьей Speeding Up MATLAB Applications Хотя мораль проста — выделять память заранее, и использовать векторные операции Matlab, иначе рассуждать об оптимизациях нет смысла

Спасибо, довольно полезно! Не во многих графических редакторах, например на мобильные устройства, есть такая простая на первый взгляд возможность.

Сейчас пытаюсь использовать этот алгоритм и не могу понять, где я напортачил
скриншот qblx.co/wEEIbW

Спасибо за ссылку на www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm
На мелкой задаче применял заливку через соседние 4 точки. Получилось быстро, но только в силу мизерной области. Посмотреть можно тут github.com/Lexx918/JS.Xonix
А вот на крупной картинке упёрся в производительность. В статье по ссылке построчная заливка. Не стал портировать один-в-один, но применил от части тут github.com/Lexx918/Coloring
Плюс добавил прелоадер — сразу подготовил все строки изображения и сложил в кэш. Плюс каждую замкнутую область сразу пометил своим уникальным номером и это ещё немного ускорило поиск заливаемых строк. Летает!
Ещё раз спасибо.
Кто-нить нашёл алгоритмы пошустрее?