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