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

[GUIMachine]

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

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

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

[AndreyIvanoff]

Очень интересно про сглаживание границ при заполнении, думаю обязательно стоит в отдельную статью.

[GUIMachine]

Тогда постараюсь на неделе выкроить под это время.
Тем более, что самому интересно заняться доработкой алгоритма :)

[abelov]

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

[Jenyay]

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

[AndreyIvanoff]

Оба языка являются интерпретируемыми, думаю я кривовато написал на MatLab, поэтому так долго — реализовал первую пришедшую мысль.

[bagyr]

Оба языка поддерживают исполнение нативного кода.
Тут проблема может быть в частом
stack = [stack newpoint];
выделение памяти в Matlab очень дорогое.

[AndreyIvanoff]

Да, меня тоже эта строчка смущает, постоянное расширение массива. А как бы это обойти? — ну самое очевидное — выделить заранее стек максимального размера, странно даже почему я так не сделал.

[GUIMachine]

Я так понимаю про чай — это был для наглядности сделан первый неоптимальный вариант (или же нет?)

На Java, к примеру, подобный алгоритм мгновенно заполняет такие небольшие изображения и секунду-две тратит на огромные (2000х2000+). А «пошаговая» отрисовка заливки как на видео сделана скорее для наглядности, чтобы показать как работает алгоритм, так что не думаю что там самый оптимальный вариант

[AndreyIvanoff]

Ну вроде как оптимальным является последний — построчный. А вроде бы есть еще оптимальнее — только времени нет разобраться.

[GUIMachine]

Ну про последний понятно…
А ресурс достаточно интересный, спасибо за ссылку :)

[dshster]

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

[dmtrlbdv]

но если сравнивать заливку средствами BASIC на BK-0010 и на ZX-Spectrum, то BK-0010 рвал по скорости в клочья :)

[AndreyIvanoff]

Завидую, я уже не застал этих штуковин

[BOBO]

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

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

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

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

[AndreyIvanoff]

Упс, вы все правильно говорите, по вертикальной. Просто картинка при визуализации в MatLabe переворачивается, есть возможность это исправить, дело в команде axis image, есть аналогичная чтобы не переворачивало, но забыл совсем.

[AndreyIvanoff]

Спасибо за замечания, поправил.

[BOBO]

Интересно работать шустрее стало или нет? Просто выбирается горизонтальное закрашивание, из-за более быстрого доступа к элементам массива в который помещается изображение(изображение в файле располагается построчно сверху-вниз).

[AndreyIvanoff]

Я так понял вы про второй алгоритм? Второй алгоритм шустрее первого на порядок, но по другой причине — дело в том, что минимизируется количество лишних проверок, возникает меньше коллизий.

[BOBO]

Да, я про второй алгоритм. Просто из коммента понял, что вы поменяли у на х в цикле. Вот и спросил про разницу в работе «исправленного» и «неисправленного» второго алгоритма.

[AndreyIvanoff]

Сорри, не понял. Я не стал менять код — видики придется переделать если уж по честному, пусть все так и будет. А по поводу вашего вопроса про строковую индексацию: в MatLab матрица хранится по столбцам подобно Fortran, и обращаюсь к столбцам а не к строкам я получал ускорение в сотни раз. Приходилось даже специально продумывать алгоритмы для работы с транспонированной матрицей.

[sylvio]

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

[GUIMachine]

Да даже данную реализацию можно ускорить, вполне вероятно.
К тому же автор уже приводил выше ссылку на более оптимальные варианты заливки.
Думаю есть и другие алгоритмы и немало…

[Yakhnev]

Почему я выбрал такую маленькую деталь как бровь — потому что залить что-то другое, например пузо, учитывая особенности исполняемого языка 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, иначе рассуждать об оптимизациях нет смысла

[AndreyIvanoff]

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

[vrecobra]

Зато Ваши видеоролики показывают заливку в «slow-motion») Для объяснения алгоритма это более наглядно, чем 3-х секундный ролик)

[Yakhnev]

и еще, у Вас избавление от рекурсии не эквивалентно исходному рекурсивному алгоритму, так как на самом деле используется очередь, а не стек, так как удаление происходит из начала, а добавление в конец. Получился обход в ширину, а не в глубину. Чтобы стало стеком, надо писать stack = [newpoint stack ]

[AndreyIvanoff]

Ну перерабатывать статью сейчас бессмысленно, все уже обсудили. Еще раз спасибо. Буду внимательней.

[hx0]

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

[GUIMachine]

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

[SAKrisT]

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

[Lexx918]

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