Эффективная сегментация изображений на графах


    Сегментация изображений и выделение границ объектов (edge detection) играют важную роль в системах Computer Vision и применяются для задач распознавания сцен и выделения (определения) объектов. По большому счету, это такой же инструмент, как, например, сортировка, предназначенный для решения более высокоуровневых задач. И поэтому понимание устройства данного класса алгоритмов не будет лишним при построении подобных систем с учетом предъявляемых требований (в плане качество/производительность) и специфики поставленных задач.

    В данной статье кратко описан алгоритм «Efficient Graph-Based Image Segmentation» авторов Pedro F. Felzenszwalb (MIT) и Daniel P. Huttenlocher (Cornell University), опубликованный в 2004 году. Да, алгоритм относительно старенький, но, несмотря на это, он до сих пор остается весьма популярным, демонстрируя неплохие результаты в плане производительности.

    Под катом – большая смесь картинок и текста, не требовательная к текущему уровню знаний тематики. Любопытство приветствуется.



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


    Алгоритм Краскала


    Алгоритм Краскала (wiki) строит каркас — минимальное остовное дерево данного графа. Далее будет использоваться английская аббревиатура MST (minimum spanning tree).

    Задача: на карте расположено несколько населенных пунктов (на плате расположено несколько контактов), необходимо соединить все из них друг с другом таким образом, чтобы суммарная длина дорог (проводов) была минимальной.


    * Да, задача в такой формулировке обычно называется «задачей Штейнера» (статья), решив которую, города можно соединить еще дешевле. Но нам-то, в конечном итоге, не асфальт укладывать… =)

    Для решения понадобятся:
    • Графы: Кратко о том, что это такое и как они представляются в коде уже было изложено на Хабре (статья)
    • Алгоритм Краскала (wiki): основной «движок» для решения задачи в такой формулировке. Он очень хорошо описан в библии Кормена, Лейзерсона «Алгоритмы: построение и анализ» (книга)
    • Disjoint-set data structure (wiki): дополнительная структура, необходимая для эффективного выполнения вышеупомянутого алгоритма. Как она устроена, описано в той же библии, но только немного под другим названием (если не изменяет память: Union Find-Set, как-то так)



    В текущей постановке задачи вершины графа (vi) – представляют собой города, а ребра e(vi, vj) – дороги между городами. Нам известны расстояния между парами городов (vi, vj) – это вес ребер w(e(vi, vj)). Нужно найти MST, т.е. такое дерево в графе (без циклов: зачем строить лишние дороги), чтобы сумма ребер была минимальной и при этом все вершины были достижимы.

    Изначально каждая вершина (город) сам по себе и является единственным гордым представителем соответствующего множества G1, G2, … GN (по количеству вершин). Пусть пока думает, что именно она образовала MST. В ходе алгоритма мы эффективно и дипломатично объединим все эти разрозненные множества в одно единственное G так, чтобы участвующие в нем вершины образовали MST. Для этого:
    • Сортируем все имеющиеся в графе ребра в порядке возрастания длины (дороги)
    • Пробегая по ребрам в порядке возрастания длин, смотрим на концы ребра e = (a,b):
      • Если вершины (a и b) принадлежат одному множеству:Значит, они уже участвуют в некотором образованном подмножестве микро-MST, внутри их подграфа сумма ребер уже минимальна. Такое ребро пропускается – оно нам не нужно т.к. иначе оно образует цикл в дереве, и мы зря израсходуем асфальт
      • Если вершины (a и b) принадлежат разным подмножествам микро-MST:Нужно объединять, т.к. мы нашли ребро (дорогу) минимальной длины, объединяющее (сливающее) оба подмножества в одно. Все ребра меньшей длины уже рассмотрены и дешевле, чем этим ребром, объединить не получится. Такое ребро заносится в список ребер, использованных при построении дерева MST, а множества объединяются в одно
      • Продолжаем цикл объединения до получения одного единственного множества, равного искомому MST, в котором будут присутствовать все вершины графа
    • Получаем одно единственное множество вершин (MST) и список ребер, использованных для его объединения, который представляет собой дерево минимальной суммарной длинны, объединяющее все вершины.




    Disjoint-set data structure


    Для реализации понятия «множество» в алгоритме Краскала применяется структура данных Disjoint-set data structure. Работа с ней оптимизирована на выполнение двух основных операций:
    • Узнать для некоторой вершины, какому множеству в текущий момент она принадлежит
    • Быстро объединить эти множества в одно
    Чтобы приблизиться к теме сегментации изображений, описание продолжим в терминологии пикселей изображения и их цвета. Допустим, мы сегментируем попугайчика на фоне какого-нибудь Японского синего моря. Сначала каждый пиксель (вершина графа) будет сам по себе – в собственном сегменте (множестве), но в ходе алгоритма пиксели (вершины) «схожего» цвета (одного объекта) постепенно объединяются в один сегмент.

    Допустим, на определенном шаге алгоритма попалось ребро, соединяющее два соседних пикселя: на одном конце ребра пиксель «оранжевый», а на другом «красный». Длину ребра определим как «разницу цвета» между пикселями. Все ребра меньшей длины (со схожим цветом) уже объединены: наверняка уже выделен оранжевый и красный сегмент попугайчика. Следуя алгоритму, нам нужно узнать, в одном ли сегменте лежат текущие «оранжевый» и «красный» пиксель? Если в разных, и мы считаем, что сегменты по цвету схожи, то объединяем их в один и продолжаем построение… В общем, тот же алгоритм Краскала, только с пикселями.

    Используемая для этих операций структура – очень похожа на дерево (хотя и реализуется массивом индексов). В ней для каждого пикселя указан предок, т.е. указатель (индекс) на некоторый схожий по цвету пиксель, находящийся в том же самом сегменте. Основные операции:
    • Поиск сегмента некоторого пикселя 'x': идем по предкам до самого верха. Самый верхний пиксель – это корень дерева, «представитель» данного сегмента на текущий момент.
    • Объединение сегментов. Если у пикселей разные «представители» — значит, они принадлежат различным сегментам, иначе корень был бы один. Для их объединения «представителя» сегмента меньшей высоты (от самого далекого пикселя до корня) ссылаем (из него указываем) на более длинного «представителя», чтобы не увеличивать высоту дерева. Теперь имеем объединенный сегмент с общим представителем.
    • Для того, чтобы в следующий раз не бегать далеко от пикселя к корню, после того, как «представитель» будет успешно обнаружен, устанавливаем прямую ссылку из пикселя – сразу на него. Это сокращает путь следующих поисков, и называется "path compression".



    Отлично, теперь мы можем эффективно искать сегменты по пикселям и объединять их, а так же выстраивать MST по алгоритму Краскала. Пора узнать, как принимается решение о соединении или разделении двух областей.



    Разделяй и властвуй


    Алгоритм сегментации должен четко определять, где заканчивается один сегмент и начинается другой. Как правило, границы представляют собой характерные перепады яркости и/или оттенков цвета, встречающиеся на участках объект-фон, плоскость-тень, попугайчик-море, надпись на заборе… И если «перепад» больше некоторого «порога» (threshold), то из этого должно следовать, что это разные сегменты. Но есть небольшая проблемка: перепады могут сильно варьироваться для различных объектов, и сегменты сложно «отделить» однозначно заданной (const) пороговой величиной (threshold). Для поверхности стола на фоне стены: перепады соседних пикселей вдоль поверхности стола (стены) будут относительно небольшими, а вот на границе стол-стена будет скачок, который и разделит сегменты. Это ясно. А если у нас попугайчик на фоне моря? Он же сам очень «пестрый», внутри него большие перепады интенсивности (зеленый-красный-желтый-…), чтобы его «отделить» от моря, нужен другой «порог» (threshold). И постепенно приходим к выводу, что порог, который решает, что соседним сегментам «не суждено быть вместе», должен опираться не только на локальные показатели: перепад интенсивностей вдоль одного ребра (соединяющего соседние пиксели), но и на то, насколько эти сегменты сами по себе гладкие (в плане цвета) или «пестрые».



    Серые картинки


    Прежде чем перейти к обработке полноценных цветных картинок, рассмотрим упрощенный вариант, когда изображение представлено градациями серого (grayscale), т.е. в каждой ячейке матрицы изображения хранится число в интервале [0...1], представляющее собой яркость пикселя.





    Efficient Graph-Based Image Segmentation


    Каждый пиксель изображения представляется вершиной в графе. А вес (длина) ребра, соединяющего соседние вершины, выражается формулой: w(vi,vj)=|I(pi)-I(pj)|, где I(pi) – интенсивность (яркость) пикселя pi

    В ходе выполнения алгоритма Краскала, на промежуточном этапе мы будем иметь несколько разрозненных сегментов (подмножеств пикселей), с минимальным суммарным весом ребер внутри: сегменты будут объединены ребрами минимальной длины, т.е. с минимальными «перепадами интенсивностей» между соседними пикселями. Поэтому соседние пиксели внутри одного сегмента будут схожи по цвету. Но только до некоторого значения максимального ребра (перепада интенсивности)…

    И вот… мы взяли минимальное на текущем шаге ребро. Для двух пикселей, являющихся смежными вершинами этого ребра, определяем из одного ли они (уже построенного) сегмента?
    • Да, из одного сегмента: просто продолжаем выполнение алгоритма.
    • Нет. Необходимо определить, представляют ли сегменты части одного и того же объекта на изображении и их следует объединить, или их интенсивности «существенно» различаются?
    Для определения различия между сегментами, с каждым уже построенным сегментом мы ассоциируем некоторую величину – максимальный перепад интенсивностей внутри него, т.е. самое длинное ребро в MST внутри сегмента:

    Отдельно его искать не придется – достаточно просто сохранять длину ребра, добавляемого при объединении составляющих «подсегментов». Ведь на момент объединения длина добавляемого ребра была больше, чем в уже построенных MST каждого «подсегмента», т.к. ребра обрабатываются в возрастающем порядке.

    Получаем примерное решающее правило для сегментов C1, C2:
    Признак: следует ли разграничить эти сегменты
    Текущее ребро минимальной длины, соединяющее два разрозненных сегмента
    Меньший (из больших) перепад интенсивностей внутри одного из рассматриваемых сегментов

    Получается что, для того чтобы сегменты «объединились», перепад интенсивностей на их границе должен быть меньше максимального перепада внутри каждого из объединяемых сегментов:





    Ищу тебя


    Как же построить граф по изображению? Какие пиксели являются соседними? На поверхности лежат два основных подхода:
    • 4-connected: каждый пиксель соединяем с соседними сверху / снизу / слева / справа. Такое построение привлекательно тем, что количество ребер в графе минимально.
    • 8-connected: дополнительно к предыдущему варианту каждый пиксель соединяем с соседними, находящимися по диагонали. Ребер, таким образом, в графе получается больше, алгоритм выполняется несколько медленнее. Но получаемая сегментация должна быть качественней – ведь учитывается больше связей между пикселями.


    Алгоритм должен давать более качественные результаты на 8-connected построенном графе, однако 4-connected дает весьма приемлемые результаты и при этом выполняется значительно быстрее. А в качестве «расстояния» для обработки цветных изображений можем взять вот такую простую разницу цвета пикселей, как реализовано у авторов алгоритма:

    Однако, у такой формулировки расстояния есть недостаток. Если рассматривать «перепад интенсивности» между локально соседними пикселями, то небо на следующей картинке будет разбито на 2 отдельных сегмента проходящей поперек проволокой, или получим еще худший результат, если обработаем лужайку на фоне сетки:


    Каждый фрагмент лужайки – будет отмечен как отдельный сегмент, но ведь это один объект!

    Поэтому в альтернативном варианте, авторы предлагают рассматривать не только близлежащие пиксели, а оттолкнувшись от локальных свойств изображения (пикселей, располагающихся в непосредственной близости), попробовать «перепрыгнуть через провод» (см. картинку) и дотянуться до продолжения сегмента, находящегося на некотором удалении. Для этого в качестве длины ребра они предлагают выбрать Евклидово расстояние, зависящее как от положения пикселей (x,y), так и от их цвета (r,g,b):

    Теперь пиксели будут считаться «соседями», если они расположены рядом, либо имеют схожий оттенок, хотя физически могут находиться на некотором удалении. Для построении графа авторы предлагают каждый пиксель соединять с 10 (20, 30) «ближайшими». Это дает более качественную сегментацию, но требует больше вычислительных ресурсов.


    Stick together, team!


    Возвращаясь в самое начало. Давным-давно, когда все пиксели были разрознены – между соседними мог наблюдаться существенный перепад интенсивностей, не позволяющий им объединяться (merge). Вряд ли нам предоставили микроскопическую фотографию, где каждый пиксель надо обособить — скорее всего, они являются частью какого-то большего объекта (попугайчика). Чтобы они поддавались «слиянию» (merge) в большей степени, чем уже построенные большие сегменты, для которых более важна корректность разбиения, в решающем правиле добавляют величину, зависящую от размера построенного сегмента: , где |C| – мощность рассматриваемого сегмента (количество пикселей в нем на текущий момент), а k – это уже параметр сегментации, задаваемый вручную. С подобной поправкой в решающем правиле будет использоваться формула:


    «Поправка» постепенно нивелируется с ростом сегмента (увеличением |C|)…

    На самом деле, вместо подобного задания T можно выбрать и иную функцию, учитывающую специфику обрабатываемых изображений: форму сегментов, положение на фотографии, определенные цветовые оттенки…


    Размытие по Гауссу


    Возвращаясь к очень «пестрым» картинкам:


    Ясно, что при определении расстояния между пикселями в таком определении, как «перепад интенсивностей», пиксели «пестрого», пусть даже единого объекта, будут не очень-то податливы на объединение в один объект. Чтобы сделать их более «сговорчивыми» на объединение и убрать шум/артефакты, к изображению обычно применяется размывание (smoothing) фильтром Гаусса (http://habrahabr.ru/blogs/webdev/43895/) с некоторым радиусом (среднеквадратическим отклонением) sigma. Это вызывает «взаимопроникновение» цветовых составляющих пикселей, и они более охотно идут на контакт.


    Итого


    Методов для сегментации существует много: различные подходы очень хорошо описаны в статье — «Методы сегментации изображений: автоматическая сегментация». А по большому счету, сегментация должна быть либо качественной, либо производительной, а если повезет – то все и сразу. Описанный выше метод представляет собой именно производительный вариант.

    В таком способе сегментации самым трудоемким процессом является сортировка всех ребер, выполняемая за O(elog⁡e), где e – это количество ребер в графе. Таким образом, для изображения NxM пикселей ребер будет: |e| = 4*N*M

    Исходный код алгоритма доступен по этой ссылке.


    А как же OpenCV?


    Во всеми любимой библиотеке OpenCV (wiki) есть метод "cvPyrSegmentation", т.е. пирамидальный метод сегментации изображений. Он устроен несколько иначе. Его описание заняло бы еще одну статью, поэтому — картинка. Сегменты строятся слоями (level), объединяя схожие по цвету пиксели в один (находящийся слоем выше), и далее последовательно обрабатывая слои находящиеся на следующем уровне (level) выше «до упора»:


    В 2006 в Univesity of Malaga (Spain) было проведено сравнение нескольких пирамидальных алгоритмов и результаты изложены в следующей статье:


    Авторы пришли к выводу, что из 8 методов, заслуживающими внимания являются 3, благодаря которым получаются достаточно качественные результаты разбиения изображения на объекты. Однако стоит отметить, что время выполнения пирамидальных алгоритмов колеблется от 0,5 сек. до 4,5 сек. (256x256 пикселей на Pentium 766 MHz), тогда как рассматриваемый "Efficient Graph-Based Image Segmentation" выполняется со слов авторов «in fraction of a second». У нас 1024x768 фотография отрабатывала за 0,5 сек (U9400 2 x 1.4GHz) внутри «матрешки»: VMWare – Matlab – mex (C++). В общем, пирамидальные – качество, описанные в статье графы – скорость. Оба имеют право на жизнь. =)


    Самым усидчивым читателям, раскроем тайну «волшебных пузырьков»: что за цифры изображены на картинках? Это просто параметры метода "segmentation(sigma, k, min)", с 2-мя из которых вы уже знакомы, а 3-ий "min" — это принудительно установленный минимальный размер сегмента, чтобы «маленьких» не оставалось.


    Удачи!

    P.S. Прошу сильно не пинать, это мой девятый пост на Хабре.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 48

    • UFO just landed and posted this here
        +4
        Ни пуха, ни пера! =)
          0
          Не знаю почему, но мне теория графов нравится :)
            +1
            Сочувствую. У меня в 9 утра экзамен по электротехнике…
              0
              Ну, а у меня — по основам теории управления...)
                +1
                а у меня только консультация, по «Параллельному программированию»
                  +21
                  а я закончил уже :p
                    +2
                    А у нас в квартире газ.
                      0
                      Базы данных =) экзамен… через 3 часа
                  0
                  ну что, сдали?
                    0
                    эм… с 23:51 по 6:40 (по времени комментатора 5:40) мало кто сдает/принимает экзамен =)
                    • UFO just landed and posted this here
                    0
                    Спасибо, просветился) мне кажется еще бы описание алгоритма на каком-либо языке программирования не помешало.
                      +4
                      Извинюсь… еле запостил статью в таком объеме. Чуть больше и Хабр «ни в какую». Потому и сократил статью. Пришлось урезать: практическое применение (кому интересно — сами найдут) и код.
                      Зато авторский source code прилагается: тут. Он очень сильно коррелирует с тем, что изложено в статье. Разобраться с ним — пару часов удовольствия. =)
                        +2
                        можно как вариант написать вторую часть статьи, практическую так сказать. Хотя бы самые интересные моменты.
                          0
                          Варианты, которые первыми «пришли в голову»:
                            +7
                            1. В статье уже 2009 (августа) года «An Efficient Parallel Algorithm for Graph-Based Image Segmentation» (статья) Karlsruhe University (Germany), дан вариант распараллеливания этого алгоритма, для более эффективного выполнения вычислений. Кому-то делать эффективный Computer Vision? Why not?
                            2. Благодаря тому, что алгоритм позиционируется как очень эффективный, почему бы не реализовать его на какой-нибудь мобильной платформе (КПК): тыцкнул в фото-фокусе на памятник, и камера сама навелась на памятник на весь экран или (если будет выполняться шустро на КПК) на какой-нибудь двигающийся объект – и он, оставаясь «выделенным» в квадратик, продолжает быть «отфотканным», пока не исчезнет за горизонт. Why not?
                            3. Так как сегментация (во всех алгоритмах) зависит от параметров, почему бы не научить алгоритм подстраиваться под загруженное изображение – допустим нейронной сетью. Загружена фотография автомобиля днем – выставляем для метода одни параметры, загружен ландшафт – другие, апартаменты – третьи. Это тоже сложная задача. И это сейчас стараются делать «за бугром». Наши студенты не хуже!!! Why not?
                            4. Wanna be a «bad guy»? Цифро-буквенные каптчи все еще достаточно распространенны. Можно взять цветную «зашумленную» каптчу, пройтись по ней размытием Гаусса, чтобы убрать мелкие пиксели, полосочки, потом сегментацией выделить все буквы. Применить на «толстых» буквах скелетонизацию (skeletonization: построение topological skeleton), убрать фильтрами артефакты и получить что-то примерно похожее на рукописный ввод. Далее – либо своей обученной нейронной сетью распознать буковки, или воспользоваться чем-то похожим на FineReader. Нам кажется, что так «можно грабить корованы…» (мем). Why not?
                              +1
                              3 — весьма интересно!
                        +1
                        Это бы заняло еще столько же места) Все и так отлично. Автору респект — достигнут баланс визуальной и текстовой информации + ссылки.
                        +16
                        Поздравляю с Днем Рождения! =)

                          +1
                          Большущее СПАСИБО!!! =)) Очень приятно! =))
                          +1
                          Судя по результатам сегментирования, метод может помочь создавать объёмные модели из изображений объекта, так?
                            0
                            That's right! =)
                              0
                              так же можно заметить, что можно из растра сделать вектор!!!
                              0
                              Можно ли это использовать в распознавании стерео/3D-изображений?
                                +4
                                Автор, расскажите, а Вы действительно считаете разницу между цветами как расстояние между векторами в пространстве RGB, или всё-таки привели этот пример для упрощения понимания ситуации? Ведь для цветового различия такая формула совершенно неприменима (я сам примерно тем же, что Вы, занимался когда-то, но недолго :)), и используется, как минимум, пространство XYZ.

                                  0
                                  Большое спасибо!

                                  Признаться честно, я не знал о таких подходах вычисления «разницы цвета». Обязательно ознакомлюсь. А в данной реализации (статье) авторы сделали упор на эффективность вычислений, потому и воспользовались формулами попроще.
                                    +1
                                    В оригинальной статье для цветных изображений авторы рекомендуют сперва проводить сегментацию по каждой RGB-компоненте (и получать таким образом три варианта «одноцветной» сегментации), а затем строить результат, объединяя два пикселя в один сегмент, если они были в одном сегменте более чем в двух «одноцветных» вариантах.
                                    Они утверждают, что такая реализации показала лучшие результаты, чем однократное применение алгоритма к исходному изображению с вычислением расстояний в каком-либо цветовом пространстве.
                                    В таком случае не возникает проблем с выбором цветового пространства.
                                      +1
                                      Интересно, хотя ИМХО можно попробовать использовать другие цветовые пространства, вместо RGB.
                                        +1
                                        Уже начал читать оригинал. Надо на каникулах хоть что-нибудь содержательное написать. Если удастся, можно будет попробовать Lab. Быть может авторы дальше RGB решили не углубляться. Они часто напоминают в статье, что «возможны варианты».
                                    +1
                                    Кубизм.
                                      0
                                      утреннее чтиво, ночью не могу. Обещает быть интересным
                                        +1
                                        1) пирамидальные алгоритмы — это что то очень близкое к дискретному вейвлет-преобразованию в простейшей своей форме, а там ведь еще можно и шумы отсекать очень эффективно

                                        2) с точки зрения взлома каптч сегментация изображения выглядит весьма интересной
                                          +3
                                          > P.S. Прошу сильно не пинать, это мой девятый пост на Хабре.

                                          Да ты писатель-рецидивист!!! :)
                                            +1
                                            такая сочная тема, нет он просто молодец!
                                            0
                                            Хм. Вот если с нуля думать над задачей — решение с графами кажется очевидным, первого выбора. «Как-то так бы и делал» ведь правильно? А пирамидальный — это уже ммм… глубже копать. Почему же распространение и внимание авторов популярной библиотеки досталось именно пирамидальному методу?
                                              +2
                                              «В общем, пирамидальные – качество, описанные в статье графы – скорость.»

                                              Вероятно создатели openCV предпочли качество. Ведь если не хватает мощности для выполнения алгоритма (в данном случае пирамидального), то можно попытаться улучшить вычислительную технику. А вот если не хватает качества самого алгоритма, то несмотря на его скорость и ваши вычислительные возможности, ничего уже не сделаешь (в глобальных масштабах).
                                              0
                                              Интересна реализация в коде.
                                                0
                                                Ахаха, год назад защищал дипломную вот точно по этой теме, прога даже работала, могу поискать исходники.
                                                  0
                                                  А собсна в статье есть ссылка на оригинальные исходники people.cs.uchicago.edu/~pff/segment/
                                                  0
                                                  Автор где вы были два года назад! Я бы меньше парился над запиской для дипломной =) У меня дежавю прям.
                                                    +3
                                                    Осталось придумать еще один алгоритм, который сам подбирает идеальные настройки для описанного алгоритма :)
                                                      0
                                                      Пошел искать мануалы по написанию плагинов к фотошопу.
                                                        +1
                                                        «segmentation(k, sigma, min)»
                                                        Похоже, что на изображениях параметры идут в другом порядке: sigma, k, min. Поправьте, если не затруднит. Пришлось немало времени потратить, думая, как же может сказаться на результатах величина k=0.7. Слишком уж мала она была, чтоб хоть как-то значительно изменить результаты сравнения сегментов. А оказалось, что 0.7 — это параметр для размытия по Гауссу.
                                                          0
                                                          Спасибо. Исправил.
                                                          +2
                                                          Я думаю данная статья даже спустя 5 лет остается актуальной. Особенно для тех, кто только начинает работать с алгоритмами автоматической сегментации. В связи с этим было бы очень не плохо вернуть часть «пропавших» изображений на их прежние места.
                                                            +1
                                                            Возвращаю (залил на habrastorage) =)
                                                              0
                                                              спасибо за вашу оперативность ;)

                                                          Only users with full accounts can post comments. Log in, please.