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

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

Не буду докучать объемной теорией, а ограничусь лишь минимальными сведениями, необходимыми для понимания сути алгоритмов.
Все указанные методы основываются на одном из базовых свойств сигнала яркости – разрывности. Наиболее общим способом поиска разрывов является обработка изображения с помощью скользящей маски, называемой также фильтром, ядром, окном или шаблоном, которая представляет собой некую квадратную матрицу, соответствующую указанной группе пикселей исходного изображения. Элементы матрицы принято называть коэффициентами. Оперирование такой матрицей в каких-либо локальных преобразованиях называется фильтрацией или пространственной фильтрацией.

Схема пространственной фильтрации иллюстрируется на рисунке ниже (см. рисунок 1).

image
Рисунок 1. Схема пространственной фильтрации

Процесс основан на простом перемещении маски фильтра от точки к точке изображения; в каждой точке (x,y) отклик фильтра вычисляется с использованием предварительно заданных связей. В случае линейной пространственной фильтрации отклик задается суммой произведения коэффициентов фильтра на соответствующие значения пикселей в области, покрытой маской фильтра. Для маски 3х3 элемента, показанной на рисунке 1, результат (отклик) R линейной фильтрации в точке (x,y) изображения составит:

image (1.1)

что, как видно, есть сумма произведений коэффициентов маски на значения пикселей непосредственно под маской. В частности заметим, что коэффициент w(0,0) стоит при значении f(x,y), указывая тем самым, что маска центрирована в точке (x,y).

При обнаружении перепадов яркости используются дискретные аналоги производных первого и второго порядка. Для простоты изложения будут рассмотрены одномерные производные.

Первая производная одномерной функции f(x) определяется как разность значений соседних элементов:

image (1.2)

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

Аналогично, вторая производная определяется как разность соседних значений первой производной:

image (1.3)

Вычисление первой производной цифрового изображения основано на различных дискретных приближениях двумерного градиента. По определению, градиент изображения f(x,y) в точке (x,y) — это вектор [2]:

image (1.4)

Как известно из курса математического анализа, направление вектора градиента совпадает с направлением максимальной скорости изменения функции f в точке (x,y) [2].
Важную роль при обнаружении контуров играет модуль этого вектора, который обозначается ∇f и равен

image (1.5)

Эта величина равна значению максимальной скорости изменения функции f в точке (x,y), причем максимум достигается в направлении вектора ∇f. Величину ∇f также часто называют градиентом.

Направление вектора градиента также является важной характеристикой. Обозначим α(x,y) угол между направлением вектора ∇f в точке (x,y) и осью x. Как известно из математического анализа [2],

image (1.6)

Отсюда легко найти направление контура в точке (x,y), которое перпендикулярно направлению вектора градиента в этой точке. А вычислить градиент изображения можно, вычислив величины частных производных ∂f/∂x и ∂f/∂y для каждой точки.

Оператор Робертса


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

image
Рисунок 2. Окрестность 3х3 внутри изображения

Один из простейших способов нахождения первых частных производных в точке image состоит в применении следующего перекрестного градиентного оператора Робертса [1]:

image (1.7)
и
image (1.8)

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

image
Рисунок 3. Маски оператора Робертса

Реализация масок размерами 2х2 не очень удобна, т.к. у них нет четко выраженного центрального элемента, что существенно отражается на результате выполнения фильтрации. Но этот «минус» порождает очень полезное свойство данного алгоритма – высокую скорость обработки изображения.

Оператор Превитта


Оператор Превитта, так же как и оператор Робертса, оперирует с областью изображения 3х3, представленной на рисунке 2, только использование такой маски задается другими выражениями:

image (1.9)
и
image (1.10)

В этих формулах разность между суммами по верхней и нижней строкам окрестности 3х3 является приближенным значением производной по оси x, а разность между суммами по первому и последнему столбцам этой окрестности – производной по оси y. Для реализации этих формул используется оператор, описываемый масками на рисунке 4, который называется оператором Превитта.

image
Рисунок 4. Маски оператора Превитта

Оператор Собеля


Оператор Собеля тоже использует область изображения 3х3, отображенную на рисунке 2. Он довольно похож на оператор Превитта, а видоизменение заключается в использовании весового коэффициента 2 для средних элементов:

image (1.11)
и
image (1.12)

Это увеличенное значение используется для уменьшения эффекта сглаживания за счет придания большего веса средним точкам.

Маски, используемые оператором Собеля, отображены на рисунке ниже (см. рис. 5).

image
Рисунок 5. Маски оператора Собеля

Рассмотренные выше маски применяются для получения составляющих градиента image. Для вычисления величины градиента эти составляющие необходимо использовать совместно:

image (1.14)
или
image (1.15)

Ну и в завершении продемонстрирую результаты обработки изображений (см. рисунки 6-8) описанными методами.

image
Рисунок 6. Исходное изображение №1

image
Рисунок 7. Исходное изображение №2

image
Рисунок 8. Исходное изображение №3

Результаты обработки методами Робертса, Превитта и Собеля продемонстрированы ниже:
image
image
image
Рисунок 9. Исходные изображения после обработки методом Робертса

image
image
image
Рисунок 10. Исходные изображения после обработки методом Превитта

image
image
image
Рисунок 11. Исходные изображения после обработки методом Собеля

Список литературы

  1. Р. Гонсалес, Р. Вудс Цифровая обработка изображений — М: Техносфера, 2005 – 1007с
  2. Кудрявцев Л.В. Краткий курс математического анализа – M.: Наука, 1989 – 736с
  3. Анисимов Б.В. Распознавание и цифровая обработка изображений – М.: Высш. школа, 1983 – 295с
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 45

    +1
    Тема хорошая, но в этом случае необходимо, мне кажется, сказать и об adaptive threshold. Потому что в противном случае эти методы не достаточно хороши для практического использования. Сами видите — у Шрека пол лица пропало, в моторе диски полустерты и т.п.

      +2
      Случайно отправилось…

      Вот, посмотрите http://library.wolfram.com/examples/edgedetection/
        0
        Спасибо за замечание. Вы безусловно правы — это довольно значительное упущение. Так же я не отметил ряд нюансов: выбор порога для сравнения с откликом R и усиление сигнала. Но это было сделано для уменьшения сложности восприятия материала статьи.
      +2
      под такими статьями нужна кнопка donate. спасибо за статью и за экономию времени. единственное, я бы выкладывал минимальные но все же исходные коды с такими алгоритмами, пусть и неоптимизированные, но позволяющие сделать первичные тесты.
        +2
        Даже не знаю как лучше поступить: выложить сюда или написать вторую часть статьи? Кода там не так уж много для отдельной статьи, но если все же браться за вторую часть, то можно проделать небольшой эксперимент по сравнению методов: скорость обработки, точность выделения контуров.
          +2
          я за второй часть, а там уж сами смотрите по возможностям и свободному времени.
            0
            Если есть время и возможность, то лучше вторую часть.
              0
              Только если будете выкладывать исходные кода — прошу вас, работайте с изображением как с матрицей — не используйте сторонних модулей для работы с картинкой — это позволит вам претендовать на универсальность записи алгоритма.
            +1
            Здорово! Хотя, мне кажется, можно было и подокучать «скучной теорией», а то как-то только во вкус при прочтении входишь, как уже и список литературы :)
              +2
              Пол года назад я занимался разработкой програмы по определению контуров. Есть несколько методов: можно исспользовать яркость соседних точек и разность между ними, можно и другие параметры, всё достаточно индивидуально для каждого применения… также достаточно важны коэфициенты допуска.

              Вот пару ссылочек по этой теме, как теоритических, так и практических… geekproit.blogspot.com/2010/10/blog-post.html здесь собраны ссылки по данной теме, для хабражителя, который занимаеться этой темой для своего диплома.
                +1
                Похоже на копипасту из курсовика.
                • UFO just landed and posted this here
                  • UFO just landed and posted this here
                      0
                      Иногда полезно освежить азы. Как со старой книгой, сколько раз читаешь ее — всегда замечаешь что-то новое, что сначала не заметил.

                      К тому же, еще несколько статей на эту тему и — глядишь — действительно сильный алгоритм появится. Или по крайней мере сводная таблица результатов (а методов определения границы действительно много). Так бывает. Я недавно наблюдал, как в совершенно случайной дискуссии родился серьезный, и насколько мне известно новый подход:
                      http://www.linkedin.com/groups/How-find-lighting-condition
                      (Разговор на английском и совсем на другую тему, но интересный)
                      • UFO just landed and posted this here
                          0
                          Я Вас плюсанул.
                          А внесите свою лепту — как Шреку лицо восстановить? Если время есть, конечно.
                            0
                            Его правая щека (освещенная) от кожи, кхм, туловища неотличима. Так что именно лицо вытянуть, кмк, нельзя…
                              0
                              Ну хоть по контуру. Мы же про границы говорим, если ее не видно, значит, и не надо ее показывать.
                              Но вот плечи, например, четко видны на рисунке. Да и нос тоже.
                                0
                                Троллиную кожу удачно получилось выделить, также можно и плечи выделить, а потом из маски уже найти контур. Кстати, тестил scilab, морфологии жалко нету.
                                  0
                                  Супер! Может, напишете подробнее? Раз все равно у нас сейчас неделя статей про поиски контуров.

                                  Пока я (имхо) считаю Ваш результат самых перспективным и лучшим, честно.

                                  PS: И как может не быть морфологии? Этого не может быть, она во всех пакетах есть, мне кажется. Примитивные операции же. Воспользуйтесь локальным поиском min/max вместо dilate/erode. Min/max же везде есть уж точно.
                                  Можно построить трехмерную картинку (каждый слайд — это маленький сдвиг исходной картинки, и все слайды склеиваются по третьей координате) и искать min/max по третьей координате. Получится прямая реализация dilate/erode.
                                  Я именно в scilab не работал, но мне кажется там это должно быть.
                                    0
                                    Ну там на самом деле мало писать. И применимо это к данной картинке — маскирование по ярко-зеленому цвету. :)

                                    Морфологии нет в базовом пакете, в сети вроде упоминается какой то дополнительный пакет, надо будет заняться.

                                    Scilab кстати на скриншотах у разработчиков очень многообещающе смотрится
                                    image
                                    но под Ubuntu у меня такой картинки получить пока не удалось…
                            • UFO just landed and posted this here
                                0
                                Ну это лучше, конечно. Теперь осталось убрать все лишнее.
                                Возможно, изображение можно разбить на регионы с точки зрения доминантого цвета, частотных характеристик текстуры, и оставить лишь линии на границах между такими областями?
                                • UFO just landed and posted this here
                                    +1
                                    Я хочу детскую раскраску (это локальная цель). Понятно же, что ребенок 3 лет спокойно обведет нужные линии, даже не задумываясь. Я видел такую программу, уже работающую, так что представляю, что разумное решение возможно.

                                    А глобальная цель — понять, увидеть как решение самых простых житейских задач достигается методами image processing. Это вовсе не протоптанная дорога. Я часто видел, как люди набрасываются на конкретную задачу и дожимают ее, в общем-то, в конце концов. Но стоит поменять чуть-чуть постановку задачи, и старые методы становятся уже негодными, и пора начинать новое исследование. Поэтому мне интересно посмотреть на классы методов, способных быстро решать те или иные задачи.

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

                                    Потом мир не стоит на месте. Когда-то сегментация посредством K-средних была супер-сложным методом. А сегодня, вон, студенты ее спокойно применяют. С такой скоростью, да при поддержке matlab, можно быстро прийти к хорошему решению, я думаю.
                      0
                      Спасибо за статью! Исправьте в формуле (1.3) опечатку в обозначении второй производной — вместо второй стоит первая.
                        +1
                        Спасибо, исправил.
                        0
                        Лучшая фотка — со Шреком!
                          +1
                          Если открыть книгу «Р. Гонсалес, Р. Вудс Цифровая обработка изображений — М: Техносфера, 2005 – 1007с», то обнаружится, то статья просто сворована оттуда за исключением картинок в конце. Но для обработки картинок с книгой «Р. Гонсалес, Р. Вудс Цифровая обработка изображений в среде MATLAB» предоставляются программы на MatLab.

                          Мнение: автор ничего полезного не сделал
                            0
                            Копипаста много, да. Но справедливости ради стоит отметить, что копипаст из 3 источников, и они указаны. А насчет использования кода для матлаба Вы сильно ошибаетесь. Свой код, как и обещал, выложу.
                              0
                              «Добейте» Шрека до конца. Так, чтобы на выходе алгоритма получилась детская раскраска. Все нужные линии на месте, и ни одной лишней линии (которые просто порождены текстурой и т.п.)
                              Эта задача вполне себе интересная. Я видел, как в Samsung на ее решение инженеры потратили 1-2 месяца. Это такой special effect, довольно популярный в телефонах.
                              На мой взгляд, несмотря на простоту, это вполне серьезная задача.

                              PS: И не переживайте. Все сложные алгоритмы являются (нетривиальной) комбинацией простых и, в общем, давно известных. Тут стыдиться нечего.
                                +1
                                Предлагаю он-лайн сервис: Родитель хочет дитяте сделать раскраску -> Заходит на сайт -> Грузит свою картинку -> Получает раскраску -> Распечатывает -> Ребенок счастлив.
                                В качестве монетизации сервиса можно предложить высылать напечатанные альбомы для раскрашивания по набору загружаемых картинок.
                                Вот такая идея, могу обеспечить алгоритмическую базу и кодинг, нет ресурсов на аренду кусочка сервака :). Хотя возможно дети уже не пользуются раскрасками?
                                  +1
                                  У меня так дети телепузиков раскрашивают :)) Я из мультфильма кадры навырезал, отредактировал и распечатал.

                                  Сервер — не проблема, могу предоставить. Только надо тогда все on-line делать. Кстати, N людей воспользуются и будут счастливы. На всяких «Мама и Малыш» форумах ссылку поставить, рейтинг сайта взлетит до небес. Потом рекламу продавать))
                                    0
                                    Отличная идея в общем, планирую найти время на ее реализацию. Спасибо за возможное решение проблемы с серваком.
                            0
                            Ох спасибо Вам) Только вчера получил задание для курсовой: реализовать программу, которая выполняет выделение контура методом Собеля, а тут такая подборка материала.
                              0
                              Статья хорошая, но кроме как для образовательных целей не нужна. Все это давно описано в литературе. Так же все это давно реализовано в бесплатной библиотеке с открытым кодом OpenCV (и еще очень много чего). Заниматься этим с нуля имеет смысл лишь как задание по курсовику. А теперь внимание вопрос: имеет ли смысл писать о каждом сколь либо интересном курсовике на Хабре?
                                0
                                В разделе «песочница», думаю стоит.
                                Надо ли было переносить ее в «Алгоритмы»? Ну, если бы в «Алгоритмах» каждый день публиковали новые алгоритмы уровня SIFT, simulated annealing или auto white balance, то, конечно, нет. Но поскольку материалов такого уровня почем-то не наблюдается, то давайте хотябы поиск границ обсудим.
                                Тем более, что если копать глубоко — это вовсе не простая задача. Очень надеюсь, что будет еще несколько более глубоких статей в продолжении.
                                  0
                                  Мне кажется, что описание широко и давно известных алгоритмов не очень уместно вообще. Так как тема мне близка, было бы гораздо интереснее увидеть либо алгоритм составленный автором (который был бы лучше уже существующих, хотя бы в каких-то частных случаях), либо какой-то малоизвестный и не тривиальный алгоритм. Просто уже не первый пост в стиле пересказа лекций/курсовиков.
                                    0
                                    Ну да, не первый. А что им еще делать? Ведь насколько я понял, единственный шанс получить «карму» — это написать пост в Песочницу?
                                    Причем рискованную тему брать нельзя, т.к. есть опасность, что будут минусить (это происходит иногда совершенно на пустом месте). Поэтому лучше всего взять что-нибудь и пересказать. Как видим, стратегия работает — все эти авторы получили по 50-60 плюсов за статью.
                                +1
                                Предлагаю перенести статью в «Обработка изображений». В статье рассматриваются операторы выделения контуров, однако не дается никаких рекомендаций — какой использовать? А я вам скажу: у все этих операторов разный коэффициент усиления шума. Коэффициент усиления шума равен сумме квадратов коэффициентов в маске. Уже маска Робертса увеличивает шум в ДВА раза.
                                  +2
                                  Перенес в «Обработка изображений». Тут этому материалу место, Вы правы.
                                  На счет рекомендаций — я планировал провести небольшой эксперимент, о котором писал чуть выше, а уже по его итогам давать какие то рекомендации и советы.
                                    +3
                                    Если хотите эксперимент — то придумайте модельную картинку — чистую, без шума. Найдите ее результат применения оператора. Но не делайте обработку по порогу! Потом зашумите картинку гауссовым шумом с дисперсией D1 и примените оператор к зашумленной картинке. Но не делайте обработку по порогу! Потом вычтите эти два результата применения операторов, и посчитайте дисперсию D2 полученной картинки. Вы получите оценку коэффициента усиления шума D2/D1.
                                      0
                                      Большое спасибо за столь ценный совет. Обязательно учту. Свободным временем еще бы разжиться в достатке
                                  +3
                                  Что-то не то с градиентом Робертса. Изображения больше похожи на просто пороговое отсечение по яркости, без применения градиента. У меня получилось вот так (после конвертации в полутона и применения Робертса):
                                  image
                                    0
                                    Возможно будет любопытно узнать, что зрение человека устроено очень похоже. Еще в глазу происходит преобразование картинки с палочек в сигналы нейронов с он и офф центром. Эти нейроны отслеживают состояние своего сенсорного поля и суммарно реагируют на границы изображения в любом направлении. По зрительному нерву передается уже контурная картинка.

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