Как стать автором
Обновить

Комментарии 33

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

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

В любом случае данная статья будет весьма полезна для тех, кто не в курсе что и как :)
Очень интересно про сглаживание границ при заполнении, думаю обязательно стоит в отдельную статью.
Тогда постараюсь на неделе выкроить под это время.
Тем более, что самому интересно заняться доработкой алгоритма :)
Спасибо, вспомнил как писал такое на лабораторках в универе.
Оба способа реализовывал.
На первом даже по-моему Паскаль иногда падал с Stack Overflow :), на больших картинках.
Немного оффтопик не все же. Всегда было интересно, кто быстрее Matlab иди Python. В Python реализовывал заливку и работало все довольно быстро (не надо было уходить пить чай).
Оба языка являются интерпретируемыми, думаю я кривовато написал на MatLab, поэтому так долго — реализовал первую пришедшую мысль.
Оба языка поддерживают исполнение нативного кода.
Тут проблема может быть в частом
stack = [stack newpoint];
выделение памяти в Matlab очень дорогое.
Да, меня тоже эта строчка смущает, постоянное расширение массива. А как бы это обойти? — ну самое очевидное — выделить заранее стек максимального размера, странно даже почему я так не сделал.
Я так понимаю про чай — это был для наглядности сделан первый неоптимальный вариант (или же нет?)

На Java, к примеру, подобный алгоритм мгновенно заполняет такие небольшие изображения и секунду-две тратит на огромные (2000х2000+). А «пошаговая» отрисовка заливки как на видео сделана скорее для наглядности, чтобы показать как работает алгоритм, так что не думаю что там самый оптимальный вариант
Ну вроде как оптимальным является последний — построчный. А вроде бы есть еще оптимальнее — только времени нет разобраться.
Ну про последний понятно…
А ресурс достаточно интересный, спасибо за ссылку :)
О, вспомнил БК0010, там заливка форм такая же медленная была, интересно было наблюдать как заполняются сложные формы, а окажить дырочка между линиями, то весь экран заливался краской =)
но если сравнивать заливку средствами BASIC на BK-0010 и на ZX-Spectrum, то BK-0010 рвал по скорости в клочья :)
Завидую, я уже не застал этих штуковин
Статья хорошая и присутствие видео тоже радует. Только я одного момента понять не могу:
y1 = point.y;
  
  % Находим границу слева
  while (y1 >= 1 && bim(point.x,y1) == oldColor) y1 = y1 - 1; end;
  y1 = y1 + 1;


Почему границу слева? Ведь цикл идет по вертикальной координате у. Тогда и получится должна граница сверху. Хотя на видео все правильно рисуется о_О
Ну и мелочи: рисуется в стандартном Paint а не Point и
% Бинаризуем с порогоМ 0.5
Упс, вы все правильно говорите, по вертикальной. Просто картинка при визуализации в MatLabe переворачивается, есть возможность это исправить, дело в команде axis image, есть аналогичная чтобы не переворачивало, но забыл совсем.
Спасибо за замечания, поправил.
Интересно работать шустрее стало или нет? Просто выбирается горизонтальное закрашивание, из-за более быстрого доступа к элементам массива в который помещается изображение(изображение в файле располагается построчно сверху-вниз).
Я так понял вы про второй алгоритм? Второй алгоритм шустрее первого на порядок, но по другой причине — дело в том, что минимизируется количество лишних проверок, возникает меньше коллизий.
Да, я про второй алгоритм. Просто из коммента понял, что вы поменяли у на х в цикле. Вот и спросил про разницу в работе «исправленного» и «неисправленного» второго алгоритма.
Сорри, не понял. Я не стал менять код — видики придется переделать если уж по честному, пусть все так и будет. А по поводу вашего вопроса про строковую индексацию: в MatLab матрица хранится по столбцам подобно Fortran, и обращаюсь к столбцам а не к строкам я получал ускорение в сотни раз. Приходилось даже специально продумывать алгоритмы для работы с транспонированной матрицей.
Скажите, а существуют более быстрые алгоритмы заливки? (не думая о их реализации)
Да даже данную реализацию можно ускорить, вполне вероятно.
К тому же автор уже приводил выше ссылку на более оптимальные варианты заливки.
Думаю есть и другие алгоритмы и немало…
Почему я выбрал такую маленькую деталь как бровь — потому что залить что-то другое, например пузо, учитывая особенности исполняемого языка 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, иначе рассуждать об оптимизациях нет смысла
Спасибо за дельную критику, согласен медлительность Matlab — миф. Выше уже обсуждали что эта строчка чрезвычайна неэффективна. Спасибо за ссылку. Не знаю почему так написал, наверное потому-что поленился и поскорее хотелось видик смонтировать.
Зато Ваши видеоролики показывают заливку в «slow-motion») Для объяснения алгоритма это более наглядно, чем 3-х секундный ролик)
и еще, у Вас избавление от рекурсии не эквивалентно исходному рекурсивному алгоритму, так как на самом деле используется очередь, а не стек, так как удаление происходит из начала, а добавление в конец. Получился обход в ширину, а не в глубину. Чтобы стало стеком, надо писать stack = [newpoint stack ]
Ну перерабатывать статью сейчас бессмысленно, все уже обсудили. Еще раз спасибо. Буду внимательней.
Спасибо, довольно полезно! Не во многих графических редакторах, например на мобильные устройства, есть такая простая на первый взгляд возможность.
Кстати тоже замечал, что у мобильных устройств отсутствует банальная заливка — это весьма странно, учитывая что платформы разработки и скорости устройств более чем позволяют реализовывать куда более сложные вещи.
Тем более сами алгоритмы уже давно придуманы и реализованы на всех возможных языках…
НЛО прилетело и опубликовало эту надпись здесь
Сейчас пытаюсь использовать этот алгоритм и не могу понять, где я напортачил
скриншот qblx.co/wEEIbW
Спасибо за ссылку на www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm
На мелкой задаче применял заливку через соседние 4 точки. Получилось быстро, но только в силу мизерной области. Посмотреть можно тут github.com/Lexx918/JS.Xonix
А вот на крупной картинке упёрся в производительность. В статье по ссылке построчная заливка. Не стал портировать один-в-один, но применил от части тут github.com/Lexx918/Coloring
Плюс добавил прелоадер — сразу подготовил все строки изображения и сложил в кэш. Плюс каждую замкнутую область сразу пометил своим уникальным номером и это ещё немного ускорило поиск заливаемых строк. Летает!
Ещё раз спасибо.
Кто-нить нашёл алгоритмы пошустрее?
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.