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

    Аннотация


    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. Раскраска про Карлсона, который живет на крыше, взята отсюда — ссылка
    Поделиться публикацией

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

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

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

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

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


                Почему границу слева? Ведь цикл идет по вертикальной координате у. Тогда и получится должна граница сверху. Хотя на видео все правильно рисуется о_О
                Ну и мелочи: рисуется в стандартном Paint а не Point и
                % Бинаризуем с порогоМ 0.5
                  0
                  Упс, вы все правильно говорите, по вертикальной. Просто картинка при визуализации в MatLabe переворачивается, есть возможность это исправить, дело в команде axis image, есть аналогичная чтобы не переворачивало, но забыл совсем.
                    0
                    Спасибо за замечания, поправил.
                      0
                      Интересно работать шустрее стало или нет? Просто выбирается горизонтальное закрашивание, из-за более быстрого доступа к элементам массива в который помещается изображение(изображение в файле располагается построчно сверху-вниз).
                        0
                        Я так понял вы про второй алгоритм? Второй алгоритм шустрее первого на порядок, но по другой причине — дело в том, что минимизируется количество лишних проверок, возникает меньше коллизий.
                          +1
                          Да, я про второй алгоритм. Просто из коммента понял, что вы поменяли у на х в цикле. Вот и спросил про разницу в работе «исправленного» и «неисправленного» второго алгоритма.
                          +1
                          Сорри, не понял. Я не стал менять код — видики придется переделать если уж по честному, пусть все так и будет. А по поводу вашего вопроса про строковую индексацию: в MatLab матрица хранится по столбцам подобно Fortran, и обращаюсь к столбцам а не к строкам я получал ускорение в сотни раз. Приходилось даже специально продумывать алгоритмы для работы с транспонированной матрицей.
                      0
                      Скажите, а существуют более быстрые алгоритмы заливки? (не думая о их реализации)
                        +1
                        Да даже данную реализацию можно ускорить, вполне вероятно.
                        К тому же автор уже приводил выше ссылку на более оптимальные варианты заливки.
                        Думаю есть и другие алгоритмы и немало…
                        +2
                        Почему я выбрал такую маленькую деталь как бровь — потому что залить что-то другое, например пузо, учитывая особенности исполняемого языка 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, иначе рассуждать об оптимизациях нет смысла
                          0
                          Спасибо за дельную критику, согласен медлительность Matlab — миф. Выше уже обсуждали что эта строчка чрезвычайна неэффективна. Спасибо за ссылку. Не знаю почему так написал, наверное потому-что поленился и поскорее хотелось видик смонтировать.
                            0
                            Зато Ваши видеоролики показывают заливку в «slow-motion») Для объяснения алгоритма это более наглядно, чем 3-х секундный ролик)
                              +1
                              и еще, у Вас избавление от рекурсии не эквивалентно исходному рекурсивному алгоритму, так как на самом деле используется очередь, а не стек, так как удаление происходит из начала, а добавление в конец. Получился обход в ширину, а не в глубину. Чтобы стало стеком, надо писать stack = [newpoint stack ]
                                0
                                Ну перерабатывать статью сейчас бессмысленно, все уже обсудили. Еще раз спасибо. Буду внимательней.
                            +1
                            Спасибо, довольно полезно! Не во многих графических редакторах, например на мобильные устройства, есть такая простая на первый взгляд возможность.
                              +1
                              Кстати тоже замечал, что у мобильных устройств отсутствует банальная заливка — это весьма странно, учитывая что платформы разработки и скорости устройств более чем позволяют реализовывать куда более сложные вещи.
                              Тем более сами алгоритмы уже давно придуманы и реализованы на всех возможных языках…
                            • НЛО прилетело и опубликовало эту надпись здесь
                                0
                                Сейчас пытаюсь использовать этот алгоритм и не могу понять, где я напортачил
                                скриншот 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
                                  Плюс добавил прелоадер — сразу подготовил все строки изображения и сложил в кэш. Плюс каждую замкнутую область сразу пометил своим уникальным номером и это ещё немного ускорило поиск заливаемых строк. Летает!
                                  Ещё раз спасибо.
                                  Кто-нить нашёл алгоритмы пошустрее?

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое