Как найти контур рисунка

В статье представлены четыре самых распространённых алгоритма обнаружения контуров.

Первые два, а именно алгоритм трассировки квадратов и трассировка окрестностей Мура, просты в реализации, а потому часто применяются для определения контура заданного паттерна. К сожалению, у обоих алгоритмов есть несколько слабых мест, что приводит к невозможности обнаружения контура большого класса паттернов из-за их особого вида смежности.

Данные алгоритмы будут игнорировать все «дырки» в паттерне. Например, если у нас есть паттерн, подобный показанному на Рисунке 1, то обнаруженный алгоритмами контур будет похож на показанный на Рисунке 2 (синими пикселями обозначен контур). В некоторых областях применения это вполне допустимо, но в других областях, например, в распознавании символов, требуется обнаружение внутренних частей паттерна для нахождения всех пробелов, отличающих конкретный символ. (На Рисунке 3 показан «полный» контур паттерна.)

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

Что такое связность

В цифровых изображениях с двоичными значениями пиксель может иметь одно из следующих значений: 1 — когда является частью паттерна, или 0 — когда является частью фона, т.е. градации серого отсутствуют. (Мы будем считать, что пиксели со значением 1 чёрные, а со значением 0 — белые).

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

В общем случае, связная компонента — это множество чёрных пикселей P, такое, что для каждой пары пикселей p_i и p_j в P существует последовательность пикселей p_i, …, p_j, такая, что:

a) все пиксели в последовательности находятся во множестве P, т.е. являются чёрными, и

b) каждые 2 пикселя, находящиеся в последовательности рядом, являются «соседями».

Возникает важный вопрос: когда мы можем сказать, что 2 пикселя являются «соседями»? Поскольку мы используем квадратные пиксели, ответ на предыдущий вопрос нетривиален по следующей причине: в квадратной тесселяции пиксели имеют общее или ребро, или вершину, или не имеют ничего общего. У каждого пикселя есть 8 пикселей, имеющих с ним общую вершину; такие пиксели составляют «окрестность Мура» данного пикселя. Должны ли мы считать «соседями» пиксели, имеющие только одну общую вершину? Или чтобы считаться «соседями», два пикселя должны иметь общее ребро?

Так возникают два вида связности, а именно: 4-связность и 8-связность.

4-связность

Когда мы можем сказать, что заданное множество чёрных пикселей является 4-связным? Во-первых, нужно определить понятие 4-соседа (также называемого прямым соседом):

Определение 4-соседа: пиксель Q является 4-соседом заданного пикселя P, если Q и P имеют общее ребро. 4-соседи пикселя P (обозначенные как P2, P4, P6 и P8), показаны на Рисунке 2 ниже.

Определение 4-связной компоненты: множество чёрных пикселей P является 4-связной компонентой, если для каждой пары пикселей p_i и p_j в P существует последовательность пикселей p_i, …, p_j, такая, что:

a) все пиксели в последовательности находятся во множестве P, т.е. являются чёрными, и

b) каждые два пикселя, которые находятся рядом в последовательности, являются 4-соседями

Примеры 4-связных паттернов

На схемах ниже показаны примеры 4-связных паттернов:

8-связность

Когда можно сказать, что заданное множество чёрных пикселей 8-связное? Во-первых, нам нужно определить понятие 8-соседа (также называемого непрямым соседом):

Определение 8-соседа: пиксель Q является 8-соседом (или просто соседом) заданного пикселя P, если Q и P имеют общее ребро или вершину. 8-соседи заданного пикселя P составляют окрестность Мура этого пикселя.

Определение 8-связной компоненты: множество чёрных пикселей P является 8-связной компонентой (или просто связной компонентой), если для каждой пары пикселей p_i и p_j в P существует последовательность пикселей p_i, …, p_j, такая, что:

a) все пиксели в последовательности находятся во множестве P, т.е. являются чёрными, и

b) каждые два пикселя, которые находятся рядом в этой последовательности, являются 8-соседями

Примечание: все 4-связные паттерны являются 8-связными, т.е. 4-связные паттерны являются подмножеством множества 8-связных паттернов. С другой стороны, 8-связный паттерн может и не являться 4-связным.

Пример 8-связного паттерна

На схеме ниже показан паттерн, являющийся 8-связным, но не 4-связным:

Пример паттерна, не являющегося 8-связным:

На схеме ниже показан пример паттерна, не являющийся 8-связным, т.е. составленный из более чем одной связной компоненты (на схеме показаны три связные компоненты):

Алгоритм трассировки квадратов

Идея

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

Чтобы понять, как он работает, нужно немного воображения…

Допустим, у нас есть цифровой паттерн, например, группа из чёрных пикселей на фоне из белых пикселей, т.е. на сетке; находим чёрный пиксель и объявляем его нашим «начальным» пикселем. (Нахождение «начального» пикселя можно реализовать множеством разных способов; мы начнём с левого нижнего угла сетки, будем сканировать каждый столбец пикселей снизу вверх, от самого левого столбца и до самого правого, пока не натолкнёмся на чёрный пиксель. Его мы и объявим «начальным«.)

Теперь представьте, что вы — божья коровка, стоящая на начальном пикселе, как это показано на показанном ниже Рисунке 1. Чтобы получить контур паттерна, вам необходимо сделать следующее:

каждый раз, когда вы оказываетесь на чёрном пикселе, поворачивайте налево, и

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

пока снова не доберётесь до начального пикселя.

Чёрные пиксели, которые вы обошли, будут являться контуром паттерна.

Важным аспектом алгоритма трассировки квадратов является «чувство направления». Повороты влево и вправо выполняются относительно текущего расположения, которое зависит от того, каким образом вы попали на текущий пиксель. Следовательно, чтобы делать правильные ходы, необходимо отслеживать своё направление.

Алгоритм

Ниже представлено формальное описание алгоритма трассировки квадратов:

Входящие данные: квадратная тесселяция, T, содержащая связную компоненту P чёрных ячеек.

Выходные данные: ряд B (b₁, b₂ ,…, b_k) пикселей границы, т.е. контур.

Начало

• Задаём B как пустое множество.
• Сканируем снизу вверх и слева вправо ячейки T, пока не будет найден чёрный пиксель s из P.
• Вставляем s в B.
• Делаем текущий пиксель p начальным пикселем s.
• Поворачиваем влево, т.е. переходим в соседний пиксель слева от p.
• Обновляем p, т.е. он становится текущим пикселем.
• Пока p не равно s, выполняем

  Если текущий пиксель p является чёрным

  • вставляем p в B и поворачиваем влево (переходим в соседний пиксель слева от p).
  • Обновляем p, т.е. он становится текущим пикселем.

  иначе

  • поворачиваем вправо (переходим в соседний пиксель справа от p).
  • Обновляем p, т.е. он становится текущим пикселем.

  Завершение цикла «Пока»

Конец

Примечание: понятия «влево» и «вправо» следует рассматривать не относительно страницы или читателя, а относительно направления входа в «текущий» пиксель во время выполнения сканирования.

Демонстрация

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

Анализ

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

В основном это связано с тем, что повороты влево и вправо не учитывают пиксели, расположенные «по
диагонали» от текущего пикселя.

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

Критерий останова

Одна из слабостей алгоритма заключается в выборе критерия останова. Другими словами, когда алгоритм прекращает своё выполнение?

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

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

Как видите, усовершенствование критерия останова может стать хорошим началом для улучшения результативности алгоритма в целом. Существует две эффективные альтернативы для имеющегося критерия останова:

a) Останавливаться, только посетив начальный пиксель n раз, где n не меньше 2, ИЛИ

b) Останавливаться после попадания в начальный пиксель во второй раз точно так же, как мы попали в него изначально.

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

Смена критерия останова в общем случае улучшает результативность алгоритма трассировки квадратов, но не позволяет преодолеть другие слабые места, которые он имеет в случае паттернов с особыми видами связности.

Square Tracing Algorithm неспособен обнаружить контур семейства паттернов со связностью 8, которые НЕ имеют связности 4.

Ниже показана анимированная демонстрация того, как алгоритму трассировки квадратов (с критерием останова Джейкоба) не удаётся обнаружить правильный контур паттерна со связностью 8 без связности 4:

Этот алгоритм совершенно бесполезен?

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

Пусть P — множество чёрных пикселей со связностью 4 на сетке. Пусть белые пиксели сетки, т.е. фоновые пиксели W тоже имеют связность 4. Оказывается, что при таких условиях паттерна и его фона можно доказать, что алгоритм трассировки квадратов (с критерием останова Джейкоба) всегда успешно будет справляться с определением контура.

Ниже представлено доказательство, что в случае, когда и паттерн, и пиксели фона имеют связанность 4, алгоритм трассировки квадратов будет правильно определять контур при использовании критерия останова Джейкоба.

Доказательство
Дано: паттерн P такой, что все пиксели паттерна (т.е. чёрные) и пиксели фона (т.е. белые) W имеют связность 4.

Первое наблюдение

Так как множество белых пикселей W имеет связность 4, это значит, что в паттерне не может быть никаких «дыр» (выражаясь неформально, «дырами» мы называем группы белых пикселей, полностью окружённые чёрными пикселями паттерна).

Наличие любой «дыры» в паттерне приведёт к отделению группы белых пикселей от остальных белых пикселей; при этом множество белых пикселей теряет связность 4.

На Рисунке 2 и Рисунке 3 ниже показано два вида «дыр«, которые могут возникнуть в паттерне со связностью 4:

Второе наблюдение

Любые два чёрных пикселя паттерна ОБЯЗАНЫ иметь одну общую сторону.

Допустим, два чёрных пикселя имеют только одну общую вершину. Тогда, чтобы удовлетворить свойству 4-связности паттерна, должен существовать путь, соединяющий эти два пикселя так, что каждые два соседних пикселя на этом пути имеют связность 4. Но это даст нам паттерн, похожий на Рисунок 3. Другими словами, это приведёт к разделению белых пикселей. На Рисунке 4 ниже показан типичный паттерн, удовлетворяющий допущению, что пиксели паттерна и фона 4-связаны, т.е. не имеют «дыр«, а каждые два чёрных пикселя имеют одну общую сторону:

Полезно представлять такие паттерны следующим образом:

Сначала рассматриваем граничные пиксели, т.е. контур паттерна. Затем если мы рассмотрим каждый граничный пиксель как имеющий 4 ребра единичной длины, то увидим, что некоторые из этих рёбер общие с соседними белыми пикселями. Мы назовём такие рёбра граничными рёбрами.

Такие граничные рёбра можно рассматривать как рёбра многоугольника. На Рисунке
5 ниже эта мысль продемонстрирована на примере многоугольника, соответствующего паттерну с Рисунка 4 выше:

Если мы рассмотрим все возможные «конфигурации» граничных пикселей, которые могут возникать в таких паттернах, то увидим, что существует два простых случая, показанных на Рисунке 6 и Рисунке 7 ниже.

Граничные пиксели могут быть кратными этих случаев или другими расположениями, т.е. поворотами этих двух случаев. Граничные рёбра помечены синим как E1, E2, E3 и E4.

Третье наблюдение

В случае рассмотренных выше двух случаев, какой бы начальный пиксель мы не выбрали, и в каком бы направлении в него не попали, алгоритм трассировки квадратов никогда не будет «возвращаться назад» (backtrack), никогда не будет «проходить через» граничное ребро дважды (только если он не трассирует границу во второй раз) и никогда не пропустит граничное ребро. Проверьте!

Здесь нужно пояснить две концепции:

a) алгоритм «возвращается назад», когда перед трассировкой всей границы он идёт назад, чтобы посетить уже посещённый пиксель, и

b) для каждого граничного ребра существует два способа «пройти через него», а именно «внутрь» и «наружу» (где «внутрь» обозначает движение внутрь соответствующего многоугольника, а «наружу» — наружу многоугольника).

Кроме того, когда алгоритм проходит «внутрь» через одно из граничных рёбер, он пройдёт «наружу» через следующее граничное ребро, т.е. алгоритм трассировки квадратов не должен иметь возможности пройти сквозь два последовательных ребра одинаковым образом.

Последнее наблюдение

У каждого паттерна существует чётное количество граничных рёбер.

Если посмотреть на многоугольник с Рисунка 5, то можно увидеть, что:

если мы хотим начать с вершины S, отмеченной на схеме, и следовать по граничным рёбрам, пока снова не достигнем S, то заметим, что пересечём в процессе чётное количество граничных рёбер. Можно считать каждое граничное ребро «шагом» в отдельном направлении. Тогда для каждого «шага» вправо должен быть соответствующий «шаг» влево, если мы хотим вернуться в исходную позицию. То же самое относится к вертикальным «шагам». Следовательно, «шаги» должны иметь соответствующие пары и это объясняет, почему в каждом из таких паттернов будет чётное количество граничных рёбер.

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

Причина этого в том, что поскольку существует два способа прохода через граничное ребро, и алгоритм попеременно выполняет движение «внутрь» и «наружу», а граничных рёбер чётное количество, то алгоритм пройдёт через начальное граничное ребро во второй раз так же, как и в первый.

Заключение

В случае 4-связного паттерна и фона алгоритм трассировки квадратов обнаружит всю границу, т.е. контур, паттерна и прекратит работу после однократной трассировки, т.е. не будет трассировать её заново, поскольку при достижении начального граничного ребра во второй раз он войдёт в него так же, как и в первый раз. Следовательно, алгоритм трассировки квадратов с критерием останова Джейкоба будет правильно определять контру любого паттерна при условии, что и паттерн, и фон обладают 4-связностью.

Трассировка окрестностей Мура

Идея

Идея, лежащая в основе трассировки окрестностей Мура (Moore-Neighbor tracing), проста; но прежде чем объяснять её, нам нужно объяснить важное понятие: окрестности Мура пикселя.

Окрестность Мура

Окрестность Мура пикселя P — это множество из 8 пикселей, имеющих общую вершину или ребро с этим пикселем. Такие пиксели, а именно P1, P2, P3, P4, P5, P6, P7 и P8, показаны на Рисунке 1.

Окрестность Мура (Moore neighborhood, также называемая 8-соседями или indirect neighbors (непрямыми соседями)) — это важное понятие, часто упоминаемое в литературе.

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

Пусть существует цифровой паттерн, т.е. группа чёрных пикселей, на фоне из белых пикселей, т.е. на сетке; найдём чёрный пиксель и объявим его «начальным» пикселем. (Находить «начальный» пиксель можно разными способами, но мы, как и раньше, будем начинать с левого нижнего угла и сканировать все столбцы пикселей по порядку, пока не найдём первый чёрный пиксель, который и объявим «начальным«.)

Теперь снова представьте, что вы божья коровка, стоящая на начальном пикселе, как показано на Рисунке 2 ниже. Без потери обобщённости мы будем обнаруживать контур, двигаясь вокруг паттерна по часовой стрелке. (Неважно, какое направление мы выберем, главное — использовать его в алгоритме постоянно).

Общая идея заключается в следующем: каждый раз, когда мы попадаем в чёрный пиксель P, то возвращаемся назад, то есть к белому пикселю, в котором стояли ранее. Затем обходим пиксель P по часовой стрелке, посещая каждый пиксель в его окрестности Мура, пока не попадём в чёрный пиксель. Алгоритм завершает выполнение, когда начальный пиксель достигает начального пикселя во второй раз.

Те чёрные пиксели, которые посетил алгоритм, будут контуром паттерна.

Алгоритм

Ниже приведено формальное описание алгоритма трассировки окрестностей Мура:

Входящие данные: квадратная тесселяция T, содержащая связную компоненту P из чёрных ячеек.

Выходные данные: ряд B (b₁, b₂ ,…, b_k) граничных пикселей, т.е. контур.

Обозначим как M(a) окрестность Мура пикселя a.

Пусть p будет текущим граничным пикселем.

Пусть c будет текущим рассматриваемым пикселем, т.е. c находится в M(p).

Начало

• Задаём B как пустое множество.
• Снизу вверх и слева направо сканируем ячейки T, пока не найдём чёрный пиксель s из P.
• Вставим s в B.
• Зададим в качестве текущей граничной точки p точку s, т.е. p=s
• Вернёмся назад, т.е. перейдём к пикселю, из которого мы пришли в s.
• Зададим в качестве c следующий по часовой стрелке пиксель в M(p).
• Пока c не равно s, выполняем
  • если c — чёрный
    • Вставляем c в B
    • задаём p=c
    • возвращаемся назад (перемещаем текущий пиксель c в пиксель, из которого попали в p)

    иначе

    • перемещаем текущий пиксель c в следующий по часовой стрелке пиксель в M(p)

    Конец цикла «Пока»

Конец

Демонстрация

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

Анализ

Основная слабость трассировки окрестностей Мура заключается в выборе критерия останова.

В исходном описании алгоритма для трассировки окрестностей Мура критерием останова является попадание в начальный пиксель во второй раз. Аналогично алгоритму трассировки квадратов, оказывается, что трассировка окрестностей Мура при использовании такого критерия не может обнаруживать контуры большого семейства паттернов.

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

Как видите, усовершенствование критерия останова может стать хорошим началом для улучшения результативности трассировки в целом. Для критерия останова есть две эффективные альтернативы, аналогичные критерию останова Джейкоба.

Использование критерия Джейкоба значительно улучшает результативность трассировки окрестностей Мура, делая его наилучшим алгоритмом для определения контура любого паттерна, вне зависимости от его связности.

Причина этого в основном заключается в том, что для поиска следующего граничного пикселя алгоритм проверяет всю окрестность Мура граничного пикселя. В отличие от алгоритма трассировки квадратов, который делает повороты только влево и вправо и упускает пиксели «по диагонали», трассировка окрестностей Мура всегда будет способна обнаружить внешнюю границу любой связной компоненты. Причина заключается в следующем: для любого 8-связного (или просто связного) паттерна следующий граничный пиксель лежит в пределах окрестности Мура текущего граничного пикселя. Поскольку трассировка окрестностей Мура проверяет каждый из пикселей в окрестности Мура текущего граничного пикселя, она обязана обнаружить следующий граничный пиксель.

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

Радиальная развёртка

Алгоритм радиальной развёртки (Radial Sweep) — это алгоритм обнаружения контура, рассматриваемый в некоторых книгах. Несмотря на сложное название, лежащая в его основе идея очень проста. На самом деле, оказывается, что алгоритм радиальной развёртки идентичен трассировке окрестностей Мура. Можно задаться вопросом: «Зачем же вообще мы его упоминаем?».

Трассировка окрестностей Мура выполняет поиск в окрестности Мура текущего граничного пикселя в определённом направлении (мы выбрали направление по часовой стрелке), пока не найдёт чёрный пиксель. Затем она объявляет этот пиксель текущим граничным пикселем и продолжает работу.

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

Способ основан на следующей идее:

каждый раз, когда мы находим новый граничный пиксель, делаем его текущим пикселем P, и рисуем воображаемый отрезок прямой, соединяющий P с предыдущим граничным пикселем. Затем поворачиваем отрезок относительно P по часовой стрелке, пока он не натолкнётся на чёрный пиксель в окрестности Мура пикселя P. Поворот отрезка идентичен проверке каждого пикселя в окрестности Мура P.

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

А когда же останавливается алгоритм радиальной развёртки?

Давайте объясним поведение алгоритма при использовании следующих критериев останова…

Критерий останова 1

Пусть алгоритм радиальной развёртки завершает работу тогда, когда посетит начальный пиксель во второй раз.

Ниже представлена анимированная демонстрация, из которой понятно, почему правильно будет сменить критерий останова.

Стоит упомянуть также то, что при использовании этого критерия останова в обоих алгоритмах результативность алгоритма радиальной развёртки идентична трассировке окрестностей Мура.

В алгоритме трассировки квадратов и в трассировке окрестностей Мура мы выяснили, что использование критерия останова Джейкоба значительно улучшает результативность обоих алгоритмов.

Критерий останова Джейкоба требует, чтобы алгоритм прекращал выполнение при посещении начального пикселя во второй раз в том же направлении, что и в первый раз.

К сожалению, мы не можем использовать в алгоритме радиальной развёртки критерий останова Джейкоба. Причина заключается в том, что алгоритм радиальной развёртки не определяет понятия «направления», в котором он попадает в граничный пиксель. Другими словами, непонятно «направление», в котором алгоритм попал в граничный пиксель (и его определение нетривиально).

Следовательно, нам нужно предложить другой критерий останова, который не зависит от направления попадания в определённый пиксель, способный улучшить результативность алгоритма радиальной развёртки…

Критерий останова 2

Допустим, что каждый раз, когда алгоритм обнаруживает новый граничный пиксель P_i, он вставляется в ряд граничных пикселей: P₁, P₂, P₃, …, P_i; и объявляется текущим граничным пикселем. (P₁ мы будем считать начальным пикселем). Это значит, что мы знаем предыдущий граничный пиксель P_i-1 каждого текущего граничного пикселя P_i . (Что касается начального пикселя, то мы будем предполагать, что P₀ является воображаемым пикселем, неэквивалентным ни одному из пикселей на сетке, который стоит перед начальным пикселем в ряду граничных пикселей).

С учётом представленных выше допущений мы можем определить критерий останова следующим образом:

Алгоритм прекращает выполнение, когда:

a) текущий граничный пиксель P_i уже ранее встречался как пиксель P_j (где j < i ) в ряду граничных пикселей, И

b) P_i-1 =  P_j-1.

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

Если условие критерия останова удовлетворено и алгоритм не завершает работу, то алгоритм радиальной развёртки будет продолжать обнаруживать ту же границу во второй раз.

Результативность алгоритма радиальной развёртки с этим критерием останова схоже с результативностью трассировки окрестностей Мура с критерием останова Джейкоба.

Алгоритм Тео Павлидиса

Идея

Этот алгоритм — один из самых последних алгоритмов обнаружения контуров, предложенный Тео Павлидисом. Он привёл его в своей книге 1982 года Algorithms for Graphics and Image Processing (глава 7, раздел 5). Он не так прост, как алгоритм трассировки квадратов или трассировка окрестностей Мура, но не так уж и сложен (это свойственно большинству алгоритмов обнаружения контуров).

Этот алгоритм мы будем объяснять не так, как это сделано в его книге. Наш подход легче воспринимается и он даёт представление об общей идее, лежащей в основе алгоритма.

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

Теперь перейдём к идее…

Допустим, у нас есть цифровой паттерн, т.е. группа чёрных пикселей на фоне из белых пикселей, т.е. на сетке; находим чёрный пиксель и объявляем его «начальным» пикселем. Искать «начальный» пиксель можно различными способами, например, изложенным выше.

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

Важное ограничение направления, в котором мы входим в начальный пиксель

На самом деле можно выбрать ЛЮБОЙ чёрный граничный пиксель в качестве начального при таком условии: если вы изначально стоите на нём, левый соседний пиксель НЕ чёрный. Другими словами, нужно входить в начальный пиксель в таком направлении, чтобы левый соседний пиксель был белым («левый» здесь берётся относительно направления, в котором мы входим в начальный пиксель).

Теперь представим, что вы божья коровка, стоящая на начальном пикселе, как это показано на Рисунке 1 ниже. В процессе выполнения алгоритма нас будут интересовать только три пикселя, находящиеся перед вами, т.е. P1, P2 и P3, показанные на Рисунке 1. (Мы обозначим как P2 пиксель перед вами, P1 — это пиксель слева от P2, а P3 — пиксель справа от P2).

Как и в алгоритме трассировки квадратов, самое важное в алгоритме Павлидиса — это «чувство направления». Повороты влево и вправо выполняются относительно текущей позиции, которая зависит от того, как вы вошли в текущий пиксель. Следовательно, чтобы делать правильные ходы, важно отслеживать текущую ориентацию. Но как бы вы ни были расположены, пиксели P1, P2 и P3 определяются описанным выше образом.

Имея эту информацию, мы готовы к объяснению алгоритма…

Каждый раз, когда вы стоите на текущем граничном пикселе (который сначала является начальным пикселем), делаем следующее:

Во-первых, проверяем пиксель P1. Если P1 чёрный, тогда объявляем P1 текущим граничным пикселем и перемещаемся на один шаг вперёд, а затем делаем шаг влево, чтобы оказаться на P1 (порядок ходов очень важен).

На Рисунке 2 ниже показан этот случай. Путь, по которому нужно попасть в P1, показан синим.

И только если P1 белый, переходим к проверке P2…

Если P2 чёрный, то объявляем P2 текущим граничным пикселем и двигаемся на шаг вперёд, чтобы оказаться на P2. Этот случай показан на Рисунке 3 ниже. Путь, по которому нужно двигаться на P2, показан синим.

Только если и P1, и P2 белые, переходим к проверке P3…

Если P3 чёрный, то объявляем P3 текущим граничным пикселем и двигаемся на один шаг вправо, а затем на один шаг влево, как показано на Рисунке 4 ниже.

Вот и всё! Три простых правила для трёх простых случаев. Как видите, важно отслеживать своё направление при поворотах, потому что все ходы делаются относительно текущей ориентации. Но кажется, мы что-то забыли? Что если все три пикселя перед нами белые? Тогда мы поворачиваемся (стоя на текущем граничном пикселе) на 90 градусов по часовой стрелке, чтобы увидеть перед собой новый набор из трёх пикселей. Затем мы выполняем ту же проверку для этих новых пикселей. У вас может всё равно остаться вопрос: что если все эти три пикселя будут белыми?! Тогда снова поворачиваемся на 90 градусов по часовой стрелке, стоя на том же пикселе. Прежде чем проверить всю окрестность Мура пикселя, можно повернуться три раза (каждый раз на 90 градусов по часовой стрелке).

Если мы повернёмся три раза, так и не найдя чёрных пикселей, то это значит, что мы стоим на изолированном пикселе, не соединённом ни с каким другим чёрным пикселем. Именно поэтому алгоритм позволяет повернуться три раза, а потом завершает своё выполнение.

Ещё один аспект: Когда алгоритм завершает выполнение?

Алгоритм завершает работу в двух случаях:

a) как сказано выше. алгоритм позволяет повернуться три раза (каждый раз на 90 градусов по часовой стрелке), после его завершает выполнение и объявляет пиксель изолированным, ИЛИ

b) когда текущий граничный пиксель является начальным пикселем, алгоритм завершает выполнение, «объявляя», что обнаружил контур паттерна.

Алгоритм

Ниже представлено формальное описание алгоритма Павлидиса:

Входящие данные: квадратная тесселяция T, содержащая связную компоненту P чёрных ячеек.

Выходные данные: ряд B (b₁, b₂ ,…, b_k) граничных пикселей, т.е. контур.

Определения:

• Обозначим как p текущий граничный пиксель, т.е. пиксель, на котором мы стоим.
• Определим P1, P2 и P3 следующим образом: (см. также Рисунок 1 выше)
• P2 — это пиксель перед вами, соседний с тем, на котором вы стоите, т.е. с пикселем p.
• P1 — левый пиксель, соседний с P2.
• P3 — правый пиксель, соседний с P2.
• Определим «шаг» в заданном направлении как перемещение на расстояние одного пикселя в этом направлении.

Начало

• Задаём B как пустое множество.
• Сканируем ячейки T снизу вверх и слева направо, пока не будет найден чёрный начальный пиксель s из P (см. выше важное ограничение относительно направления, в котором мы попадаем в начальный пиксель)
• Вставляем s в B.
• Задаём текущий пиксель p в качестве начального пикселя s.
• Повторяем следующее:
  Если пиксель P1 чёрный
  • Вставляем P1 в B
  • Обновляем p=P1
  • Движемся на один шаг вперёд, а затем делаем шаг влево

  иначе если P2 чёрный

  • Вставляем P2 в B
  • Обновляем p=P2
  • Перемещаемся на один шаг вперёд (см. выше Рисунок 3)

  иначе если P3 чёрный

  • Вставляем P3 в B
  • Обновляем p=P3
  • Делаем один шаг вправо, обновляем позицию и перемещаемся влево (см. выше Рисунок 4)

  иначе если мы уже трижды повернулись на 90 градусов по часовой стрелке, находясь в одном пикселе p

  • завершаем выполнение программы и объявляем p изолированным пикселем

  иначе

  • поворачиваемся на 90 градусов по часовой стрелке, стоя на текущем пикселе p

  Пока p=s  (Завершаем цикл повтора)

Конец

Демонстрация

Ниже показана анимированная демонстрация того, как алгоритм Павлидиса обнаруживает контур заданного паттерна. Не забывайте, что мы ходим по пикселям; замечайте, как меняется ориентация при поворотах влево или вправо. Чтобы объяснить алгоритм как можно подробнее, мы включили в него все возможные случаи.

Анализ

Если вы считаете, что алгоритм Павлидиса идеален для обнаружения контуров паттернов, то вам стоит изменить своё мнение…

Этот алгоритм действительно немного сложнее, чем, допустим трассировка окрестностей Мура, в которой нет особых случаев, требующих отдельной обработки, однако ему не удастся определить контуры большого семейства паттернов, имеющее определённый вид связности.

Алгоритм очень хорошо работает на 4-связных паттернах. Его проблема возникает при трассировке некоторых 8-связных паттернов, не являющихся 4-связными. Ниже показана анимированная демонстрация того, как алгоритму Павлидиса не удаётся обнаружить правильный контур 8-связного паттерна (не являющегося 4-связным) — он пропускает большую часть границы.

Существует два простых способа изменения алгоритма для значительного улучшения его результативности.

a) Заменить критерий останова

Вместо того, чтобы завершать алгоритм, когда он посещает начальный пиксель во второй раз, можно завершать его, когда он посетит начальный пиксель в третий или даже четвёртый раз. Это улучшит общую результативность алгоритма.

ИЛИ

b) Добраться до источника проблемы, а именно, до выбора начального пикселя

Существует важное ограничение касательно направления, в котором выполняется вход в начальный пиксель. По сути, нужно войти в начальный пиксель так, чтобы когда ты стоишь на нём, пиксель слева от тебя является белым. Причина введения этого ограничения такова: поскольку мы всегда рассматриваем три пикселя перед нами в определённом порядке, в некоторых паттернах мы будем пропускать граничный пиксель, лежащий непосредственно слева от начального пикселя.

Мы рискуем пропустить не только левый соседний пиксель от начального пикселя, но и пиксель непосредственно под ним (как продемонстрировано в анализе). Кроме того, в некоторых паттернах будет пропущен пиксель, соответствующий пикселю R на Рисунке 5 ниже. Следовательно, мы предполагаем, что в начальный пиксель нужно попадать в таком направлении, чтобы пиксели, соответствующие пикселям L, W и R, показанным на Рисунке 5 ниже, были белыми.

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

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

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

Содержание

1. Контуры в компьютерном зрении
2. Что такое контуры?
3. Последовательность поиска и отрисовки контуров с помощью OpenCV
4. Поиск и отрисовка контуров с помощью OpenCV
   1. Отрисовка с помощью CHAIN_APPROX_NONE
   2. Отрисовка с помощью CHAIN_APPROX_SIMPLE.
5. Иерархии контуров
   1. Родительско-дочерние отношения.
   2. Контурное представление отношений
   3. Различные методы извлечения контуров
6. Резюме

Контуры в компьютерном зрении   ↑

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

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

  

• Поиск подозрительных объектов. Любой объект, оставленный без присмотра в общественных местах, обычно, считается подозрительным. Эффективным и безопасным решением может быть: (Автоматическое обнаружение объекта посредством формирования контура с использованием вычитания фона).
  

  Изображение из процитированного документа — фоновая рамка без и с оставленным без присмотра предметом — идентификация и маркировка оставленного без присмотра предмета

• Сегментация фона/переднего плана: чтобы заменить фон изображения другим, необходимо выполнить извлечение изображения переднего плана (аналогично сегментации изображения). Использование контуров — это один из подходов, который можно использовать для сегментации. Обратитесь к этому сообщению для получения более подробной информации. На следующих изображениях показаны простые примеры такого приложения:

  

Что такое контуры?   ↑

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

1. findContours()
2. drawContours()

Также, у них есть два разных алгоритма обнаружения контура:

1. CHAIN_APPROX_SIMPLE
2. CHAIN_APPROX_NONE

Рассмотрим их подробно в приведенных ниже примерах. На следующем рисунке показано, как эти алгоритмы могут обнаруживать контуры простых объектов.

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

OpenCV делает это довольно простой задачей. Просто выполните следующие действия:

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

2. Применить двоичный порог
При нахождении контуров сначала всегда применяйте двоичное пороговое значение или обнаружение границ Canny к изображению в градациях серого. Здесь мы применим двоичное пороговое значение. Такое преобразование изображения в черно-белое, выделяет интересующие объекты и упрощает алгоритм обнаружения контуров. При установке порога граница объекта на изображении становится полностью белой, при этом все пиксели имеют одинаковую интенсивность. Теперь алгоритм может определять границы объектов по этим белым пикселям.

Примечание. Черные пиксели, имеющие значение 0, воспринимаются как пиксели фона и игнорируются.

Здесь может возникнуть один вопрос. Что, если мы будем использовать отдельные каналы, такие как R (красный), G (зеленый) или B (синий), вместо изображений в градациях серого (с пороговыми значениями)? В таком случае алгоритм определения контура не сработает. Как мы обсуждали ранее, алгоритм ищет границы и пиксели аналогичной интенсивности для обнаружения контуров. Двоичное изображение предоставляет эту информацию намного лучше, чем изображение с одним цветовым каналом (RGB). Далее будет показаны результирующие изображения при использовании только одного канала R, G или B вместо изображений в оттенках серого и изображений с пороговыми значениями.

3. Найдите контуры
Используйте функцию findContours() для обнаружения контуров на изображении.

4. Нарисуйте контуры на исходном изображении RGB
После определения контуров используйте функцию drawContours(), чтобы наложить контуры на исходное изображение RGB.

Все эти шаги будут иметь гораздо больше смысла и станут понятнее, когда вы начнёте писать код.

Поиск и отрисовка контуров с помощью OpenCV   ↑

Начните с импорта OpenCV и чтения входного изображения.

import cv2

# прочитать изображение
image = cv2.imread('input/image_1.jpg')

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

# преобразовать изображение в формат оттенков серого
img_gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

Теперь используйте функцию threshold() для применения бинарного порога к изображению. Любому пикселю со значением больше 150 будет присвоено значение 255 (белый). Все оставшиеся пиксели в результирующем изображении будут установлены в 0 (черный). Пороговое значение 150 — это настраиваемый параметр, поэтому вы можете с ним поэкспериментировать.

После установления порога визуализируйте двоичное изображение, используя функцию imshow(), как показано ниже.

# apply binary thresholding
ret, thresh = cv2.threshold(img_gray, 150, 255, cv2.THRESH_BINARY)

# визуализировать двоичное изображение
cv2.imshow('Binary image', thresh)
cv2.waitKey(0)
cv2.imwrite('image_thres1.jpg', thresh)
cv2.destroyAllWindows()

Посмотрите на изображение ниже! Это двоичное представление исходного изображения RGB. Можно ясно видеть, как перо, границы планшета и телефона все белые. Алгоритм контура будет рассматривать их как объекты и находить точки контура вокруг границ этих белых объектов.

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

Отрисовка с помощью CHAIN_APPROX_NONE   ↑

Теперь давайте найдем и нарисуем контуры с помощью метода CHAIN_APPROX_NONE.

Начнем с функции findContours(). У неё, как показано ниже, есть три обязательных аргумента. Дополнительные аргументы см. На странице документации здесь.

• image: двоичное входное изображение, полученное на предыдущем шаге.
• mode: это режим поиска контура. Мы предоставили его как RETR_TREE и это означает, что алгоритм извлечет все возможные контуры из двоичного изображения. Доступны и другие режимы извлечения контуров и их обсудим тоже. Вы можете узнать больше об этих вариантах здесь.
• method: определяет метод аппроксимации контура. В этом примере мы будем использовать CHAIN_APPROX_NONE. Хотя он немного медленнее, чем CHAIN_APPROX_SIMPLE, здесь для хранения ВСЕХ точек контура будем использовать этот метод.

Здесь надо подчеркнуть, что mode относится к типу извлекаемых контуров, а method относится к тому, какие точки внутри контура сохраняются. Ниже обсудим оба более подробно.

Легко визуализировать и понять результаты различных методов на одном и том же изображении.

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

Затем используйте функцию drawContours(), чтобы наложить контуры на изображение RGB. Эта функция имеет четыре обязательных и несколько необязательных аргументов. Первые четыре аргумента ниже обязательны. Для необязательных аргументов пожалуйста, обратитесь к странице документации здесь.

• image: это входное изображение RGB, на котором вы хотите нарисовать контур.
• contours: указывает контуры, полученные с помощью функции findContours().
• contourIdx: координаты точек контура в пикселях перечислены в полученных контурах. Используя этот аргумент, вы можете указать позицию индекса из этого списка, указывая, какую именно точку контура вы хотите нарисовать. Если указать отрицательное значение, будут нарисованы все точки контура.
• color: указывает цвет точек контура, которые вы хотите нарисовать. Мы рисуем точки зеленым цветом.
• thickness: это толщина точек контура.

# обнаруживаем контуры на двоичном изображении с помощью cv2.CHAIN_APPROX_NONE
contours, hierarchy = cv2.findContours(image=thresh, mode=cv2.RETR_TREE, method=cv2.CHAIN_APPROX_NONE)
                                     
# рисуем контуры на исходном изображении
image_copy = image.copy()
cv2.drawContours(image=image_copy, contours=contours, contourIdx=-1, color=(0, 255, 0), thickness=2, lineType=cv2.LINE_AA)
               
# смотрим результаты
cv2.imshow('None approximation', image_copy)
cv2.waitKey(0)
cv2.imwrite('contours_none_image1.jpg', image_copy)
cv2.destroyAllWindows()

Выполнение приведенного выше кода приведет к созданию и отображению изображения, показанного ниже. Также сохраняем образ на диск.

На следующем рисунке показано исходное изображение (слева), а также исходное изображение с наложенными контурами (справа).

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

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

Использование одного канала: красный, зеленый или синий

Чтобы получить представление, ниже приведены некоторые результаты при раздельном использовании красного, зеленого и синего каналов при обнаружении контуров. Мы обсуждали это ранее на этапах определения контура. Ниже приведен код для того же изображения, что и выше.

import cv2

# прочитать изображение
image = cv2.imread('input/image_1.jpg')

# Разделение каналов B, G, R
blue, green, red = cv2.split(image)

# обнаруживаем контуры по синему каналу и без порога
contours1, hierarchy1 = cv2.findContours(image=blue, mode=cv2.RETR_TREE, method=cv2.CHAIN_APPROX_NONE)

# рисуем контуры на исходном изображении
image_contour_blue = image.copy()
cv2.drawContours(image=image_contour_blue, contours=contours1, contourIdx=-1, color=(0, 255, 0), thickness=2, lineType=cv2.LINE_AA)
# смотрим результат
cv2.imshow('Contour detection using blue channels only', image_contour_blue)
cv2.waitKey(0)
cv2.imwrite('blue_channel.jpg', image_contour_blue)
cv2.destroyAllWindows()

# обнаруживаем контуры с использованием зеленого канала и без порогового значения
contours2, hierarchy2 = cv2.findContours(image=green, mode=cv2.RETR_TREE, method=cv2.CHAIN_APPROX_NONE)
# рисуем контуры на исходном изображении
image_contour_green = image.copy()
cv2.drawContours(image=image_contour_green, contours=contours2, contourIdx=-1, color=(0, 255, 0), thickness=2, lineType=cv2.LINE_AA)
# смотрим результат
cv2.imshow('Contour detection using green channels only', image_contour_green)
cv2.waitKey(0)
cv2.imwrite('green_channel.jpg', image_contour_green)
cv2.destroyAllWindows()

# detect contours using red channel and without thresholding
contours3, hierarchy3 = cv2.findContours(image=red, mode=cv2.RETR_TREE, method=cv2.CHAIN_APPROX_NONE)
# рисуем контуры на исходном изображении
image_contour_red = image.copy()
cv2.drawContours(image=image_contour_red, contours=contours3, contourIdx=-1, color=(0, 255, 0), thickness=2, lineType=cv2.LINE_AA)
# смотрим результат
cv2.imshow('Contour detection using red channels only', image_contour_red)
cv2.waitKey(0)
cv2.imwrite('red_channel.jpg', image_contour_red)
cv2.destroyAllWindows() 

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

На изображении выше видно, что алгоритм обнаружения контуров не может правильно найти контуры. Это связано с тем, что он не может правильно определять границы объектов, а также нечетко определена разница в интенсивности между пикселями. По этой причине предпочительнее использовать оттенки серого и двоичное пороговое изображение для обнаружения контуров.

Отрисовка с помощью CHAIN_APPROX_SIMPLE   ↑

Теперь давайте посмотрим, как работает алгоритм CHAIN_APPROX_SIMPLE и чем он отличается от алгоритма CHAIN_APPROX_NONE.

Вот для этого код:

"""
Теперь давайте попробуем с `cv2.CHAIN_APPROX_SIMPLE`
"""
# обнаруживаем контуры на двоичном изображении с помощью cv2.ChAIN_APPROX_SIMPLE
contours1, hierarchy1 = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
# рисуем контуры на исходном изображении для `CHAIN_APPROX_SIMPLE`
image_copy1 = image.copy()
cv2.drawContours(image_copy1, contours1, -1, (0, 255, 0), 2, cv2.LINE_AA)
# смотрим результат
cv2.imshow('Simple approximation', image_copy1)
cv2.waitKey(0)
cv2.imwrite('contours_simple_image1.jpg', image_copy1)
cv2.destroyAllWindows()

Здесь единственная разница заключается в том, что method для findContours() определён, как CHAIN_APPROX_SIMPLE вместо CHAIN_APPROX_NONE.

Алгоритм CHAIN_APPROX_SIMPLE сжимает горизонтальные, вертикальные и диагональные сегменты вдоль контура и оставляет только их конечные точки. Это означает, что любая из точек на прямых путях будет отклонена и останутся только конечные точки. Например, рассмотрим контур по прямоугольнику. Все точки контура, кроме четырех угловых, будут отклонены. Этот метод быстрее, чем CHAIN_APPROX_NONE, потому что алгоритм не сохраняет все точки, использует меньше памяти и, следовательно, требует меньше времени для выполнения. Ниже показаны результаты.

Если вы внимательно присмотритесь, почти нет различий между CHAIN_APPROX_NONE и CHAIN_APPROX_SIMPLE.

Итак, почему это так?

Заслуга принадлежит функции drawContours(). Хотя метод CHAIN_APPROX_SIMPLE обычно приводит к меньшему количеству точек, функция drawContours() автоматически соединяет соседние точки, присоединение к ним, даже если их нет в списке контуров.

Итак, как можно подтвердить, что алгоритм CHAIN_APPROX_SIMPLE действительно работает?

• Самый простой способ — вручную перебрать точки контура и нарисовать круг на обнаруженных координатах контура с помощью OpenCV.
• Также, используем другое изображение, которое на самом деле поможет нам визуализировать результаты алгоритма.

В следующем коде изображение выше используется для визуализации эффекта алгоритма CHAIN_APPROX_SIMPLE. Почти все такое же, как в предыдущем примере кода, за исключением двух дополнительных циклов for и некоторых имен переменных.

• Первый цикл for проходит по каждой области контура, присутствующей в списке контуров.
• Второй проходит по каждой из координат в этой области.
• Затем мы рисуем зеленый кружок в каждой координатной точке, используя функцию circle() из OpenCV.
• Наконец, мы визуализируем результаты и сохраняем их на диск.

# чтобы визуализировать эффект `CHAIN_APPROX_SIMPLE`, нам нужно правильное изображение
image1 = cv2.imread('input/image_2.jpg')
img_gray1 = cv2.cvtColor(image1, cv2.COLOR_BGR2GRAY)

ret, thresh1 = cv2.threshold(img_gray1, 150, 255, cv2.THRESH_BINARY)
contours2, hierarchy2 = cv2.findContours(thresh1, cv2.RETR_TREE,
                                               cv2.CHAIN_APPROX_SIMPLE)
image_copy2 = image1.copy()
cv2.drawContours(image_copy2, contours2, -1, (0, 255, 0), 2, cv2.LINE_AA)
cv2.imshow('SIMPLE Approximation contours', image_copy2)
cv2.waitKey(0)
image_copy3 = image1.copy()
for i, contour in enumerate(contours2): # loop over one contour area
   for j, contour_point in enumerate(contour): # loop over the points
       # draw a circle on the current contour coordinate
       cv2.circle(image_copy3, ((contour_point[0][0], contour_point[0][1])), 2, (0, 255, 0), 2, cv2.LINE_AA)
# смотрим результат
cv2.imshow('CHAIN_APPROX_SIMPLE Point only', image_copy3)
cv2.waitKey(0)
cv2.imwrite('contour_point_simple.jpg', image_copy3)
cv2.destroyAllWindows()

Выполнение приведенного выше кода дает следующий результат:

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

Иерархии контуров

Иерархии обозначают родительско-дочерние отношения между контурами. Вы увидите, как каждый режим поиска контура влияет на обнаружение контура на изображениях и дает иерархические результаты.

Родительско-дочерние отношения   ↑

Объекты, обнаруженные алгоритмами определения контуров на изображении, могут быть:

• Отдельными объектами, разбросанными по изображению (как в первом примере), или
• Объектами и формами друг в друге

В большинстве случаев, когда фигура содержит больше фигур, мы можем с уверенностью заключить, что внешняя форма является родительской для внутренней формы.

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

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

• Все отдельные числа, то есть 1, 2, 3 и 4, являются отдельными объектами в соответствии с иерархией контуров и отношениями родитель-потомок.
• Можно сказать, что 3a — ребенок 3-го. Обратите внимание, что 3а представляет собой внутреннюю часть в контуре 3.
• Контуры 1, 2 и 4 являются родительскими фигурами без каких-либо связанных дочерних фигур, поэтому их нумерация произвольна. Другими словами, контур 2 можно было бы обозначить как 1 и наоборот.

Контурное представление отношений   ↑

Вы видели, что функция findContours() возвращает список контуров и иерархию. Теперь подробно разберемся с выводом иерархии контуров.

Иерархия контуров представлена ​​в виде массива, который, в свою очередь, содержит массивы из четырех значений. Он представлен как:

[Next, Previous, First_Child, Parent] 

Итак, что означают все эти значения?

Next: обозначает следующий контур в изображении, который находится на том же иерархическом уровне.

• Для контура 1 следующий контур на том же иерархическом уровне — 2. Здесь Next будет 2.
• Соответственно, контур 3 не имеет контура на том же иерархическом уровне, что и он сам. Итак, значение Next будет -1.

Previous: обозначает предыдущий контур на том же иерархическом уровне. Это означает, что предыдущее значение контура 1 всегда будет равно -1.

First_Child: обозначает первый дочерний контур контура, который мы сейчас рассматриваем.

• Контуры 1 и 2 вообще не имеют детей. Таким образом, значение индекса для их First_Child будет -1.
• Но у контура 3 есть ребенок. Итак, для контура 3 значение позиции First_Child будет индексной позицией 3a.

Parent: обозначает позицию индекса родительского контура для текущего контура.

• Контуры 1 и 2, как очевидно, не имеют Родительского контура.
• Для контура 3a его Родителем будет контур 3
• Для контура 4 родительский контур 3a

Приведенные выше объяснения имеют смысл, но как на самом деле визуализировать эти иерархические массивы? Лучше всего:

• использовать простое изображение с линиями и формами, как на предыдущем изображении;
• искать контуры и иерархии, используя различные режимы поиска;
• затем распечатывать значения, чтобы визуализировать их.

Различные методы извлечения контуров   ↑

До сих пор мы использовали один конкретный метод поиска, RETR_TREE, чтобы найти и нарисовать контуры, но в OpenCV есть еще три метода поиска контура, а именно RETR_LIST, RETR_EXTERNAL и RETR_CCOMP.

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

"""
Обнаружение контуров и отрисовка с использованием различных режимов извлечения для дополнения
понимание иерархий
"""
image2 = cv2.imread('input/custom_colors.jpg')
img_gray2 = cv2.cvtColor(image2, cv2.COLOR_BGR2GRAY)
ret, thresh2 = cv2.threshold(img_gray2, 150, 255, cv2.THRESH_BINARY)

RETR_LIST

Метод извлечения контуров RETR_LIST не создает никаких родительских отношений между извлеченными контурами. Таким образом, для всех обнаруженных контурных областей значения позиции индекса First_Child и Parent всегда равны -1.

Все контуры будут иметь соответствующие предыдущие и следующие контуры, как описано выше.

Посмотрите, как метод RETR_LIST реализован в коде.

contours3, hierarchy3 = cv2.findContours(thresh2, cv2.RETR_LIST, cv2.CHAIN_APPROX_NONE)
image_copy4 = image2.copy()
cv2.drawContours(image_copy4, contours3, -1, (0, 255, 0), 2, cv2.LINE_AA)
# смотрим результат
cv2.imshow('LIST', image_copy4)
print(f"LIST: {hierarchy3}")
cv2.waitKey(0)
cv2.imwrite('contours_retr_list.jpg', image_copy4)
cv2.destroyAllWindows()

Выполнение приведенного выше кода дает следующий результат:

LIST: [ [ [ 1 -1 -1 -1]
[ 2  0 -1 -1]
[ 3  1 -1 -1]
[ 4  2 -1 -1]
[-1  3 -1 -1] ] ]

Ясно видно, что позиции 3-го и 4-го индексов всех обнаруженных областей контура равны -1, как и ожидалось.

RETR_EXTERNAL

Метод извлечения контура RETR_EXTERNAL действительно интересен. Он обнаруживает только родительские контуры и игнорирует любые дочерние контуры. Таким образом, на всех внутренних контурах, таких как 3a и 4, не будет нарисовано никаких точек.

contours4, hierarchy4 = cv2.findContours(thresh2, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)
image_copy5 = image2.copy()
cv2.drawContours(image_copy5, contours4, -1, (0, 255, 0), 2, cv2.LINE_AA)
# смотрим результат
cv2.imshow('EXTERNAL', image_copy5)
print(f"EXTERNAL: {hierarchy4}")
cv2.waitKey(0)
cv2.imwrite('contours_retr_external.jpg', image_copy5)
cv2.destroyAllWindows()

В результате получим:

EXTERNAL: [ [ [ 1 -1 -1 -1]
[ 2  0 -1 -1]
[-1  1 -1 -1] ] ]

На приведенном выше изображении показаны только точки, нарисованные на контурах 1, 2 и 3. Контуры 3a и 4 опущены, поскольку они являются дочерними контурами.

RETR_CCOMP

В отличие от RETR_EXTERNAL, RETR_CCOMP извлекает все контуры изображения. Наряду с этим, он также применяет двухуровневую иерархию ко всем формам или объектам на изображении.

Это значит, что

• все внешние контуры будут иметь уровень иерархии 1, а
• все внутренние контуры будут иметь уровень иерархии 2.

Но что, если у нас есть контур внутри другого контура с уровнем иерархии 2? Точно так же, как у нас есть контур 4 после контура 3a.

В этом случае:

• контур 4, опять же, будет иметь уровень иерархии 1.
• Если внутри контура 4 есть контуры, то у них будет уровень иерархии 2.

На следующем изображении контуры пронумерованы в соответствии с их уровнем иерархии, как описано выше.

На изображении выше показан уровень иерархии как HL-1 или HL-2 для уровней 1 и 2 соответственно. Теперь давайте посмотрим на код и массив выходной иерархии.

contours5, hierarchy5 = cv2.findContours(thresh2, cv2.RETR_CCOMP, cv2.CHAIN_APPROX_NONE)
image_copy6 = image2.copy()
cv2.drawContours(image_copy6, contours5, -1, (0, 255, 0), 2, cv2.LINE_AA)

# смотрим результат
cv2.imshow('CCOMP', image_copy6)
print(f"CCOMP: {hierarchy5}")
cv2.waitKey(0)
cv2.imwrite('contours_retr_ccomp.jpg', image_copy6)
cv2.destroyAllWindows()

В результате выполнение приведенного выше кода получим:

CCOMP: [ [ [ 1 -1 -1 -1]
[ 3  0  2 -1]
[-1 -1 -1  1]
[ 4  1 -1 -1]
[-1  3 -1 -1] ] ]

Здесь мы видим, что все отношения Next, Previous, First_Child и Parent поддерживаются в соответствии с методом поиска контуров, поскольку все контуры обнаруживаются. Как и ожидалось, Предыдущее значение первой области контура равно -1. И контуры, у которых нет Родителя, также имеют значение -1.

RETR_TREE

Как и RETR_CCOMP, RETR_TREE также извлекает все контуры. Он также создает полную иерархию с уровнями, не ограниченными 1 или 2. Каждый контур может иметь свою собственную иерархию в соответствии с уровнем, на котором он находится, и соответствующими родительско-дочерними отношениями, которые у него есть.

Из рисунка выше видно, что:

• Контуры 1, 2 и 3 находятся на одном уровне, то есть на уровне 0.
• Контур 3a присутствует на уровне иерархии 1, поскольку он является дочерним элементом контура 3.
• Контур 4 — это новая область контура, поэтому его уровень иерархии равен 2.

Следующий код использует режим RETR_TREE для извлечения контуров.

contours6, hierarchy6 = cv2.findContours(thresh2, cv2.RETR_TREE, cv2.CHAIN_APPROX_NONE)
image_copy7 = image2.copy()
cv2.drawContours(image_copy7, contours6, -1, (0, 255, 0), 2, cv2.LINE_AA)
# смотрим резльтат
cv2.imshow('TREE', image_copy7)
print(f"TREE: {hierarchy6}")
cv2.waitKey(0)
cv2.imwrite('contours_retr_tree.jpg', image_copy7)
cv2.destroyAllWindows()

Выполнение приведенного выше кода дает следующий результат:

TREE: [ [ [ 3 -1  1 -1]
[-1 -1  2  0]
[-1 -1 -1  1]
[ 4  0 -1 -1]
[-1  3 -1 -1] ] ]

Наконец, давайте посмотрим на полное изображение со всеми контурами, нарисованными при использовании режима RETR_TREE.

Все контуры нарисованы так, как ожидалось, и участки контура хорошо видны. Вы также делаете вывод, что контуры 3 и 3a — это два отдельных контура, поскольку они имеют разные границы контура и площади. В то же время совершенно очевидно, что контур 3a является потомком контура 3.

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

Сравнение времени выполнения различных методов поиска контура

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

Метод получения контура	Время (в секундах)
RETR_LIST	0,000382
RETR_EXTERNAL	0,000554
RETR_CCOMP	0,001845
RETR_TREE	0,005594

Сравнение скорости вывода разных методов

Из приведенной выше таблицы следует несколько интересных выводов:

• RETR_LIST и RETR_EXTERNAL занимают наименьшее количество времени для выполнения, поскольку RETR_LIST не определяет никакой иерархии, а RETR_EXTERNAL только извлекает родительские контуры
• RETR_CCOMP занимает второе по времени выполнение. Он извлекает все контуры и определяет двухуровневую иерархию.
• RETR_TREE занимает максимальное время для выполнения, так как извлекает все контуры, а также определяет независимый уровень иерархии для каждого родительско-дочернего отношения.

Хотя приведенное выше время может показаться незначительным, важно знать о различиях для приложений, которые могут потребовать значительного объема обработки контура. Также стоит отметить, что время обработки может варьироваться в зависимости от извлекаемых контуров и определяемых ими уровней иерархии.

Ограничения

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

• Когда объекты на изображении сильно контрастируют с их фоном, вы можете четко определить контуры, связанные с каждым объектом. Но что, если у вас есть изображение, как на рисунке ниже. У него не только яркий объект (щенок), но и фон, загроможденный тем же значением (яркостью), что и объект интереса (щенок). Вы обнаружите, что контуры на правом изображении даже не завершены. Кроме того, в области фона есть несколько нежелательных контуров.

  

• Обнаружение контура также может не сработать, если фон объекта на изображении заполнен линиями.

Резюме   ↑

Мы начали с определения контуров и научились реализовывать это в OpenCV. Увидели, как приложения используют контуры для обнаружения и сегментации движения. Затем мы продемонстрировали использование четырех различных режимов восстановления и двух методов контурной аппроксимации. Мы также научились рисовать контуры, закончили обсуждением контурных иерархий и как различные режимы поиска контуров влияют на прорисовку контуров на изображении.

Основные выводы:

• Алгоритмы определения контуров в OpenCV работают очень хорошо, когда изображение имеет темный фон и четко определенный интересующий объект.
• Но когда фон входного изображения загроможден или имеет ту же интенсивность пикселей, что и объект из-Интересно, алгоритмы не так хороши.

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

Источник Contour Detection using OpenCV (Python/C++)

Множество объектов на изображении можно опознать по их форме, например, печати в сканах документов, как правило, круглые, развороты паспорта четырёхугольные и т.д. Зная простые свойства искомого объекта и отсутствие этих свойств у других объектов изображения, можно свести задачу детектирования на изображении к задаче поиска объекта, чей контур содержит в себе какое-то количество углов. Говоря проще: хочешь найти на фотографии стола книгу – найди что-то с четырьмя сторонами.

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

Однако, преобразование Хафа для окружностей хорошо применимо, очевидно, к окружностям и не найдёт печати или другие объекты, содержащие углы. Для задачи поиска изображений с «угловатым» контуром может прекрасно подойти использование детектора границ Кэнни. Примерный алгоритм:

Пронаблюдаем работу алгоритма по изложенным выше шагам, используя для обработки opencv:

Загрузим изображение и применим функцию для перевода в градации серого:

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

Далее, выделим границы объектов оператором Кэнни:

«Закроем границы»:

Найдём контуры и выделим нужные объекты:

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

Можно искать и в более сложных условиях:

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

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

Контуры — полезный инструмент для анализа формы, обнаружения и распознавания объектов.

Чтобы сохранить точность, мы должны использовать бинарные изображения. Во-первых, мы применяем обнаружение порога или края.

В OpenCV поиск контура в бинарном изображении аналогичен поиску белого объекта на черном фоне.

OpenCV предоставляет функцию findContours(), которая используется для поиска контура в бинарном изображении. Синтаксис следующий:

 
cv2. findContours(thes, cv2.RETR_TREE, cv.CHAIN_APPROX_SIMPLE) 

Функция findContours() принимает три аргумента: первый аргумент — это исходное изображение, второй — режим поиска контуров, а третий — аппроксимация контуров.

Рассмотрим следующий пример:

 
import numpy as np 
import cv2 as cv 
im = cv.imread(r'C:UsersDEVANSH SHARMAbinary.png') 
imgray = cv.cvtColor(im, cv.COLOR_BGR2GRAY) 
ret, thresh = cv.threshold(imgray, 127, 255, 0) 
contours, hierarchy = cv.findContours(thresh, cv.RETR_TREE, cv.CHAIN_APPROX_SIMPLE) 

Как рисовать контуры?

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

Чтобы нарисовать все контуры на изображении:

 
cv2.drawCounter(img, contours,-1,(0,255,0),3) 

Чтобы нарисовать индивидуальный контур, например, третий:

 
cnt = contours[3] 
cv2.drawCounter(img,[cnt],0,(0,255,0),3) 

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

Метод контурной аппроксимации

Это третий аргумент в cv2.findCounter(). Выше мы описали это, чтобы нарисовать границу фигуры с одинаковой интенсивностью. Он хранит (x, y) – координаты границы формы. Но тут возникает вопрос, хранит ли он все координаты? Это определяется методом контурной аппроксимации.

Если мы передадим cv.CHAIN_APPROX_NONE, он сохранит все граничные точки. Иногда не нужно хранить координаты всех точек, допустим, мы нашли контуры прямой линии, где не требуется хранить все точки контура, требуется хранить только две конечные точки. Поэтому для такого случая мы используем cv.CHAIN_APPROX_NONE, он удаляет все лишние точки и сжимает контуры, тем самым экономя память.

Пример 1:

На приведенном выше изображении прямоугольника первое изображение показывает точки, использующие cv.CHAIN_APPROX_NONE(734), а второе изображение показывает точку с cv2.CHAIN_APPROX_SIMPLE (всего 4 точки). Мы видим значительную разницу между двумя изображениями.

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

Контур объекта — это его видимый край, который отделяет объект от фона. В действительности, большинство методов анализа изображений работают именно с контурами, а не с пикселями как таковыми. Совокупность методов работы с контурами называется контурным анализом.

Возьмём в качестве подопытного изображения что-нибудь такое, где есть ярко выраженные вложенные контуры, какой-нибудь диск. И попробуем применить к нему стандартные функции OpenCV для поиска и визуализации контуров объектов.

1. Функция OpenCV для поиска контуров findContours

В OpenCV для поиска контуров имеется функцией findContours, которая имеет вид:

findContours( кадр, режим_группировки, метод_упаковки [, контуры[, иерархия[, сдвиг]]])

кадр — должным образом подготовленная для анализа картинка. Это должно быть 8-битное изображение. Поиск контуров использует для работы монохромное изображение, так что все пиксели картинки с ненулевым цветом будут интерпретироваться как 1, а все нулевые останутся нулями. На уроке про поиск цветных объектов была точно такая же ситуация.

режим_группировки — один из четырех режимов группировки найденных контуров:

• CV_RETR_LIST — выдаёт все контуры без группировки;
• CV_RETR_EXTERNAL — выдаёт только крайние внешние контуры. Например, если в кадре будет пончик, то функция вернет его внешнюю границу без дырки.
• CV_RETR_CCOMP — группирует контуры в двухуровневую иерархию. На верхнем уровне — внешние контуры объекта. На втором уровне — контуры отверстий, если таковые имеются. Все остальные контуры попадают на верхний уровень.
• CV_RETR_TREE — группирует контуры в многоуровневую иерархию.

метод_упаковки — один из трёх методов упаковки контуров:

• CV_CHAIN_APPROX_NONE — упаковка отсутствует и все контуры хранятся в виде отрезков, состоящих из двух пикселей.
• CV_CHAIN_APPROX_SIMPLE — склеивает все горизонтальные, вертикальные и диагональные контуры.
• CV_CHAIN_APPROX_TC89_L1,CV_CHAIN_APPROX_TC89_KCOS — применяет к контурам метод упаковки (аппроксимации) Teh-Chin.

контуры — список всех найденных контуров, представленных в виде векторов;

иерархия — информация о топологии контуров. Каждый элемент иерархии представляет собой сборку из четырех индексов, которая соответствует контуру[i]:

• иерархия[i][0] — индекс следующего контура на текущем слое;
• иерархия[i][1] — индекс предыдущего контура на текущем слое:
• иерархия[i][2] — индекс первого контура на вложенном слое;
• иерархия[i][3] — индекс родительского контура.

сдвиг — величина смещения точек контура.

2. Функция OpenCV для отображения контуров drawContours

Полученные с помощью функции findContours контуры хорошо бы каким-то образом нарисовать в кадре. Машине это не нужно, зато нам это поможет лучше понять как выглядят найденные алгоритмом контуры. Поможет в этом ещё одна полезная функция — drawContours.

drawContours( кадр, контуры, индекс, цвет[, толщина[, тип_линии[, иерархия[, макс_слой[, сдвиг]]]]])

кадр — кадр, поверх которого мы будем отрисовывать контуры;

контуры — те самые контуры, найденные функцией findContours;

индекс — индекс контура, который следует отобразить. -1 — если нужно отобразить все контуры;

цвет — цвет контура;

толщина — толщина линии контура;

тип_линии — тип соединения точек вектора;

иерархия — информация об иерархии контуров;

макс_слой — индекс слоя, который следует отображать. Если параметр равен 0, то будет отображен только выбранный контур. Если параметр равен 1, то отобразится выбранный контур и все его дочерние контуры. Если параметр равен 2, то отобразится выбранный контур, все его дочерние и дочерние дочерних! И так далее.

сдвиг — величина смещения точек контура.

3. Программа поиска и отображения контуров

Теперь напишем программу, которая будет искать контуры предметов в кадре с пончиком. Прежде всего, следует подготовить изображение. Помним, что функция findContours работает с монохромной картинкой, и нам потребуется обработать наш пончик цветовым фильтром, чтобы сам пончик стал абсолютно белым, а фон — чёрным.

import sys
import numpy as np
import cv2 as cv

# параметры цветового фильтра
hsv_min = np.array((2, 28, 65), np.uint8)
hsv_max = np.array((26, 238, 255), np.uint8)

if __name__ == '__main__':
    print(__doc__)

    fn = 'image.jpg' # путь к файлу с картинкой
    img = cv.imread(fn)

    hsv = cv.cvtColor( img, cv.COLOR_BGR2HSV ) # меняем цветовую модель с BGR на HSV 
    thresh = cv.inRange( hsv, hsv_min, hsv_max ) # применяем цветовой фильтр
    # ищем контуры и складируем их в переменную contours
    _, contours, hierarchy = cv.findContours( thresh.copy(), cv.RETR_TREE, cv.CHAIN_APPROX_SIMPLE)

    # отображаем контуры поверх изображения
    cv.drawContours( img, contours, -1, (255,0,0), 3, cv.LINE_AA, hierarchy, 1 )
    cv.imshow('contours', img) # выводим итоговое изображение в окно

    cv.waitKey()
    cv.destroyAllWindows()

В результате работы программы мы получим пончики с выделенными внешними и вложенными границами.

Теперь разберёмся как параметры кадр и макс_слой влияют на отображаемые контуры.

Алгоритм findContours нашел у пончиков четыре замкнутых контура. Если вывести иерархию в консоль с помощью обычного print, то мы увидим следующую таблицу:

[ 2 -1  1 -1] - внешний контур первого бублика
[-1 -1 -1  0] - дырка первого бублика
[-1  0  3 -1] - внешний контур второго бублика
[-1 -1 -1  2] - дырка второго бублика

На верхнем уровне иерархии имеется два контура. Эти контуры легко вычислить по значению четвертой величины = -1, которая отвечает за указатель на родительский контур. Также имеются два вложенных контура. Один вложен в первый внешний контур, а второй вложен во второй внешний контур.

В программе параметр контур = -1, следовательно drawContours должна вывести все четыре найденных контура. Но есть ещё второй параметр макс_слой, как он будет влиять на вывод? Посмотрим его поведение на анимации:

Примечание! На верхнем бегунке contour = 0, хотя мы почему-то говорим про -1. Это не ошибка! На самом деле в этом положении бегунка в функцию поступает параметр контур = -1. Это несоответствие возникло из-за особенностей бегунка в OpenCV — он не может принимать отрицательные значения, поэтому в программе из значения бегунка contour каждый раз принудительно вычитается единица.

Вернёмся к параметрам.

При макс_слой = 0 отображается первый попавшийся контур на верхнем уровне иерархии. Такая комбинация параметров вообще нетипичная  и бесполезная, она эквивалентна комбинации контур = 0, макс_слой=0.

При макс_слой = 1 отобразятся все контуры на самом верхнем уровне иерархии — это уже полезно. Так мы сможем увидеть все бублики в кадре.

Наконец, при макс_слой = 2 отобразятся контуры на верхнем уровне и все контуры на следующем уровне — то есть дырки.

Теперь наоборот, зафиксируем макс_слой = 0, и будем менять контур в диапазоне от 0 до 3.

Тут опять видна путающая всех первая комбинация: контур = -1, макс_слой = 0, игнорируем её. Но затем всё становится логично. Как и ожидалось, мы просто перебираем контуры на всех слоях, внутренних и внешних.

Чтобы самостоятельно поэкспериментировать с параметрами можно написать программу, которая добавит в окно два бегунка для изучаемых параметров. Подобное мы делали на уроке про цветовые фильтры.

import sys
import numpy as np
import cv2 as cv

hsv_min = np.array((2, 28, 65), np.uint8)
hsv_max = np.array((26, 238, 255), np.uint8)

if __name__ == '__main__':
    fn = 'donuts.jpg'
    img = cv.imread(fn)

    hsv = cv.cvtColor( img, cv.COLOR_BGR2HSV )
    thresh = cv.inRange( hsv, hsv_min, hsv_max )
    _, contours0, hierarchy = cv.findContours( thresh.copy(), cv.RETR_TREE, cv.CHAIN_APPROX_SIMPLE)

    index = 0
    layer = 0

    def update():
        vis = img.copy()
        cv.drawContours( vis, contours0, index, (255,0,0), 2, cv.LINE_AA, hierarchy, layer )
        cv.imshow('contours', vis)

    def update_index(v):
        global index
        index = v-1
        update()

    def update_layer(v):
        global layer
        layer = v
        update()

    update_index(0)
    update_layer(0)
    cv.createTrackbar( "contour", "contours", 0, 7, update_index )
    cv.createTrackbar( "layers", "contours", 0, 7, update_layer )

    cv.waitKey()
    cv.destroyAllWindows()

К размышлению

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

На следующем уроке начнем с простого — займемся поиском прямоугольников в кадре и вычислением угла их наклона.