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

Предварительные требования

• Базовое знание Python.
• Установленные библиотеки: opencv-python, numpy, scipy.
• Понимание понятий свёртки и градиента на школьном уровне.

1. Теоретическое введение в поиск контуров. Немного математики

1.1 Механизм работы масок

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

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

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

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

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

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

Оператор Робертса — один из простейших градиентных фильтров. Он использует две матрицы 2×2, ориентированные по диагоналям.

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

1.3 Операторы Прюитта и Собеля

Операторы Прюитта и Собеля используют маски 3×3 и работают по всем направлениям, в отличие от диагонально ориентированного Робертса.

Оператор Прюитта позволяет оценить величину и ориентацию границы, но направления ограничены восемью возможными углами.

Оператор Собеля отличается увеличенным весом (коэффициент 2) у центральных элементов маски. Это снижает эффект сглаживания и повышает чувствительность к диагональным контурам. Он лучше выделяет мелкие детали по сравнению с Прюиттом.

1.4 Оператор Лапласа

Оператор Лапласа (Лапласиан) основан на производной второго порядка и относится к изотропным — он инвариантен к повороту изображения.

Дискретная форма Лапласиана представляется в виде матрицы 3×3. Для получения результата из исходного изображения вычитается свёртка с этой маской. Часто требуется нормализация результата.

1.5 Фильтр Уоллеса

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

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

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

1.6 Детектор границ Канни

Алгоритм Канни состоит из пяти этапов:

• Сглаживание — устранение шума, например, с помощью фильтра Гаусса.
• Поиск градиентов — вычисление величины и направления градиента, например, с помощью оператора Собеля.
• Подавление не-максимумов — оставляются только локальные максимумы градиента в направлении вектора градиента. Углы квантуются с шагом 45°.
• Двойная пороговая фильтрация — пиксели разделяются на три группы: сильные (выше верхнего порога), слабые (между порогами) и подавляемые (ниже нижнего).
• Трассировка по гистерезису — слабые границы сохраняются только если они связаны с сильными. Проверяется связность по 8-ми направлениям.

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

2. Практическая реализация

Все методы легко реализуются с помощью библиотек OpenCV и NumPy.

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

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

2.2 Операторы Собеля и Прюитта

Оба оператора используют маски 3×3. Прюитт выделяет больше деталей, чем Робертс. Собель за счёт усиления центральных весов лучше работает на диагоналях и мелких структурах.

2.3 Оператор Лапласа

Лапласиан реализуется одной маской, так как он изотропный. Фильтр очень чувствителен к деталям и шуму. Время выполнения собственной реализации — 150 мс, тогда как встроенный метод OpenCV работает за 8 мс.

2.4 Детектор границ Канни

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

Функция cv.findContours() использует топологический анализ бинаризованного изображения для поиска и иерархической организации контуров. cv.drawContours() визуализирует результат: контуры — синим, bounding box’ы — зелёным.

2.5 Адаптивный медианный фильтр Уоллеса

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

Выводы

• Детектор Канни показывает лучший результат по качеству и подавлению шума.
• Оператор Лапласа чувствителен к деталям, но захватывает много шума. По скорости близок к другим фильтрам.
• Операторы Собеля и Прюитта дают схожие результаты. Собель лучше на диагоналях и мелких структурах. Хорошее сочетание качества и производительности.
• Оператор Робертса даёт наименее качественный результат, но самый быстрый. Подходит для обработки больших массивов, где важна скорость.
• Фильтр Уоллеса устраняет локальные контрасты, упрощая выбор порогов и последующую обработку.

❯ Содержание

1. Теоретическое введение в поиск контуров1.1 Механизм работы масок1.2 Оператор Робертса1.3 Операторы Прюитта и Собеля1.4 Оператор Лапласа1.5 Фильтр Уоллеса1.6 Детектор границ Канни
2. Практическая реализация2.1 Оператор Робертса2.2 Оператор Собеля и Прюитта2.3 Оператор Лапласа2.4 Детектор границ Канни2.5 Адаптивный медианный фильтр Уоллеса
3. Выводы

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

❯ Предварительные требования

Для понимания материала вам понадобится:

• Базовое знание Python
• Установленные библиотеки:opencv-python,numpy,scipy.
• Понимание, что такое свёртка и градиент (на уровне школы).

1. Теоретическое введение в поиск контуров. Немного математики

❯ 1.1 Механизм работы масок

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

Яркость, а точнее говоря такое ее свойство, как разрывность, это ключевое понятие в обнаружении контуров изображения. В стандартной RGB модели значения по каждому каналу варьируются от 0 ((0, 0, 0) соответствует черный цвет) до 255 ((255, 255, 255) — белый). Яркость здесь определяется градациями серого цвета. Чтобы ее получить, нужно вычислить сумму значений по всем трем каналам и разделить на 3. В пространственных фильтрах, которые будут рассмотрены далее, будут использоваться производные первого и второго порядка, а также понятие градиента.

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

Рассмотренная формула применима для горизонтального приращения, для вертикального аналогично:

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

Градиент функции — это вектор, содержащий частные производные по всем ее переменным, он отображает направление наибольшего роста функции.

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

Источник: [1]

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

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

Рассмотрим одну из наиболее простых масок — оператор Робертса. Она представляет собой матрицы 2×2.

Рис. 2 Маски оператора Робертса

Источник: [2]

Маска естественным образом соответствует диагональным направлениями, но корректно действует на достаточно широком диапазоне углов, пусть и не всегда качественно. Из-за размерности 2×2 вызывает трудности в определении центра, но достаточно быстро действует. Оператор Робертса применяется из-за высокой скорости вычислений, но он чувствителен к шуму. Если итоговый градиент получился больше максимального значения яркости, то применяем нормализацию.

❯ 1.3 Операторы Прюитта и Собеля

Далее рассмотрим операторы размерности 3×3. Операторы Прюитта и Собеля.

Рис. 3 Оператор Прюитта

Источник: [2]

Оператор Прюитта хорошо работает уже по всем направлениям от центра, в отличии от диагонального оператора Робертса. По нему можно корректно оценить величину и ориентацию границы объекта, но направления границы ограничены 8-ю.

Оператор Собеля (см. Рис. 4) действует схожим образом, отличие в коэффициенте два у средних точек. Это увеличенное значение используется для уменьшения эффекта сглаживания за счет придания большего веса средним точкам. Более чувствителен к диагональному контуру, чем к вертикальным и горизонтальным, как оператор Прюитта.

Рис. 4 Оператор Собеля

Источник: [2]

❯ 1.4 Оператор Лапласа

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

Опираясь на формулу 2, можно вывести дискретную формулу Лапласиана:

И соответствующую ему матрицу оператора:

Рис. 5 Лапласиан в дискретной форме

Источник: [2]

Для получения итогового результата нужно вычесть из исходного изображения дискретную форму Лапласиана (зачастую требуется нормализация полученного результата).

❯ 1.5 Фильтр Уоллеса

Фильтр Уоллеса (Wallis Filter) регулирует значения яркости в локальных областях таким образом, чтобы локальное среднее значение и стандартное отклонение (СКО) соответствовали либо заданным пользователем целевым значениям, либо данным параметрам всего изображения. Это улучшение обеспечивает хороший локальный контраст по всему изображению, одновременно снижая общий контраст между светлыми и темными областями. То-есть, это локально адаптируемый фильтр, который гарантирует, что в каждом заданном пикселе среднее значение и контрастность соответствуют некоторым заданным значениям. Он отлично подходит для устранения неравномерного освещения, делая во всех локальных областях изображения одинаковое отклонение. Данный фильтр делит изображение на k равных областей, в каждой области вычисляет локальное среднее значение.

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

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

❯ 1.6 Детектор границ Канни

Далее рассмотрим алгоритм Канни, или же детектор границ Канни. Он состоит из следующих шагов:

• Сглаживание.Размытие изображения для удаления шума.
• Поиск градиентов.Границы отмечаются там, где градиент изображения приобретает максимальное значение.
• Подавление не-максимумов.Только локальные максимумы отмечаются как границы.
• Двойная пороговая фильтрация.Потенциальные границы определяются порогами.
• Трассировка области неоднозначности.Итоговые границы определяются путём подавления всех краёв, несвязанных с определенными (сильными) границами.

Для сглаживания может использоваться фильтр Гаусса:

Для поиска градиента хорошо сработает фильтр Собеля, рассмотренный ранее.

Для подавления не-максимумов пикселями границ объявляются пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента. Значение направления должно быть кратно 45°.

Рис. 6 Подавление не-максимумов

Источник: [1]

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

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

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

Время выполнения (мс)

❯ 2. Практическая реализация

Все рассмотренные методы реализуются достаточно просто через OpenCV и Numpy.Рассмотрим на примере этого изображения:

Рис. 7 Исходное изображение (любимый район)

Фотография: vadimpo

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

Метод applyRoberts()Назначение: Реализует фильтр Робертса.Алгоритм:

• Задаёт двумерные маски kernelX и kernelY для фильтра Робертса.
• Использует applyFilter, передавая обе маски.

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

❯ 2.2 Оператор Собеля и Прюитта

Методы applyPrewitt() и applySobel() используют метод applyFilter(), используя маски 3×3, представленные ранее.

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

Рассмотрим результат применения фильтра Собеля:

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

❯ 2.3 Оператор Лапласа

Назначение:Реализует лапласиан.Алгоритм:Определяет маску Лапласа kernel. Вызывает applyFilter, передавая только одну маску (так как Лаплас — изотропный оператор, т.е его маска совмещает горизонтальные и вертикальные направления).

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

❯ 2.4 Детектор границ Кенни

Метод applyCanny(double threshold1, double threshold2)Назначение: Реализует алгоритм Канни.Алгоритм: Вычисляет градиенты Собеля в горизонтальном (gradX) и вертикальном (gradY) направлениях. Использует applySobel для gradX. Вызывает applyFilter с вертикальной маской для gradY. Приводит градиенты к типу CV_32F. Вычисляет величину (magnitude) и угол (angle) градиента с помощью cv::cartToPolar. Нормализует величину градиента. Применяет пороги threshold1 и threshold2 для выделения границ.

Здесь представлены методы findContours и drawContours. Они используют библиотечные функции для отображения контуров, а также наш класс для их хранения (boundingBoxes и contours). Зеленым цветом выделяются boundingBoxes, синим — сами контуры.

В функции cv.findContours() есть три аргумента: первый — исходное изображение, второй — режим поиска контуров, третий — метод аппроксимации контура. И она выводит измененное изображение, контуры и иерархи.

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

❯ 2.5 Адаптивный медианный фильтр Уоллеса

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

По результатам применения представленных пространственных фильтров можно заключить:

• Алгоритм Канни справляется лучше пространственных фильтров по нахождению контура и фильтрации шума.
• Маска Лапласа является третьей по качеству из представленных подходов. Она очень чувствительна к деталям и захватывает много шума даже с пороговой фильтрацией. Время выполнения немногим меньше, чем у остальных фильтров.
• Маски Прюитта и Собеля дают схожие результаты, но оператор Собеля немного лучше действует для обнаружения мелких деталей контура за счет усиления веса в центре. Данные маски сочетают хорошую производительность и качество.
• Маска Робертса, как и ожидалось, показала худший итоговый результат. По времени выполнения она действует быстрее всего, рекомендуется использовать при наличии больших массивов изображений, где скорость важнее качества.
• Фильтр Уоллеса используется для удаления локальных контрастов, что облегчает подбор порогового значения и обработку.

❯ Список источников

1. Вильгейм Б. Принципы цифровой обработки изображений/Б. Вильгейм, Марк Дж. Бурдж - Лондон: Springer-Verlag, 2009 – 260 с.
2. Гонсалес Р. Мир цифровой обработки/Р. Гонсалес, Р. Вудс - Москва: Техносфера, 2012 - 1104 с.

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале↩