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.

• Понимание, что такое свёртка и градиент (на уровне школы).

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

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

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

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

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

Рис. 1 Схема применения маски

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Сглаживание. Размытие изображения для удаления шума.

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

• Подавление не-максимумов. Только локальные максимумы отмечаются как границы.

• Двойная пороговая фильтрация. Потенциальные границы определяются порогами.

• Трассировка области неоднозначности. Итоговые границы определяются путём подавления всех краёв, несвязанных с определенными (сильными) границами.

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

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

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

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

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

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

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

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

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

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

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

Любимый район :>

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

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

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

• Использует applyFilter, передавая обе маски.

import cv2
import numpy as np
from scipy import ndimage

THRESHOLD = 50

img = cv2.imread("input.jpg", 0).astype('float64')
roberts_cross_v = np.array([[1, 0], [0, -1]])
roberts_cross_h = np.array([[0, 1], [-1, 0]])
vertical = ndimage.convolve(img, roberts_cross_v)
horizontal = ndimage.convolve(img, roberts_cross_h)
edged = np.sqrt(np.square(horizontal) + np.square(vertical))
edged = np.clip(edged, 0, 255).astype(np.uint8)
_, edged = cv2.threshold(edged, THRESHOLD, 255, cv2.THRESH_BINARY)
cv2.imwrite("output.jpg", edged)

Рис. 7. Оператор Роббертса

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

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

import cv2
import numpy as np
from scipy import ndimage

THRESHOLD = 50

img = cv2.imread("input.jpg", 0).astype('float64')
sobel_x = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]])
sobel_y = np.array([[-1, -2, -1], [0, 0, 0], [1, 2, 1]])
grad_x = ndimage.convolve(img, sobel_x)
grad_y = ndimage.convolve(img, sobel_y)
edged = np.sqrt(np.square(grad_x) + np.square(grad_y))
edged = np.clip(edged, 0, 255).astype(np.uint8)
_, edged = cv2.threshold(edged, THRESHOLD, 255, cv2.THRESH_BINARY)
cv2.imwrite("output.jpg", edged)

import cv2
import numpy as np
from scipy import ndimage

THRESHOLD = 50

img = cv2.imread("input.jpg", 0).astype('float64')
prewitt_x = np.array([[-1, 0, 1], [-1, 0, 1], [-1, 0, 1]])
prewitt_y = np.array([[-1, -1, -1], [0, 0, 0], [1, 1, 1]])
grad_x = ndimage.convolve(img, prewitt_x)
grad_y = ndimage.convolve(img, prewitt_y)
edged = np.sqrt(np.square(grad_x) + np.square(grad_y))
edged = np.clip(edged, 0, 255).astype(np.uint8)
_, edged = cv2.threshold(edged, THRESHOLD, 255, cv2.THRESH_BINARY)
cv2.imwrite("output.jpg", edged)

Рис. 8. Оператор Прюитта, результат

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

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

Рис. 9 Оператор Собеля, результат

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

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

import cv2
import numpy as np
from scipy import ndimage

THRESHOLD = 50

img = cv2.imread("input.jpg", 0).astype('float64')
laplacian = np.array([[0, 1, 0], [1, -4, 1], [0, 1, 0]])
filtered = ndimage.convolve(img, laplacian)
edged = np.abs(filtered)
edged = np.clip(edged, 0, 255).astype(np.uint8)
_, edged = cv2.threshold(edged, THRESHOLD, 255, cv2.THRESH_BINARY)
cv2.imwrite("output.jpg", edged)

Рис. 10 Оператор Лапласа, результат

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

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

import cv2

THRESHOLD = 50

img = cv2.imread("input.jpg", 0)
edged = cv2.Canny(img, threshold1=THRESHOLD, threshold2=THRESHOLD * 3)
cv2.imwrite("output.jpg", edged)

Рис 11. Найденные контуры алгоритма Канни

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

import cv2

img = cv2.imread("canny_output.jpg", 0)
color_img = cv2.cvtColor(img, cv2.COLOR_GRAY2BGR)
contours, _ = cv2.findContours(img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
for cnt in contours:
    x, y, w, h = cv2.boundingRect(cnt)
    cv2.rectangle(color_img, (x, y), (x + w, y + h), (0, 255, 0), 2)
cv2.drawContours(color_img, contours, -1, (255, 0, 0), 1)
cv2.imwrite("output.jpg", color_img)

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

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

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

import cv2
import numpy as np

def wallis_filter(img, W=15, Amax=1.0, Dd=1.0, p=0.5, Md=128.0):
    img = img.astype(np.float64)
    if W % 2 == 0:
        W += 1
    kernel = np.ones((W, W), np.float64) / (W * W)
    local_mean = cv2.filter2D(img, -1, kernel)
    local_var = cv2.filter2D((img - local_mean) ** 2, -1, kernel)
    local_std = np.sqrt(local_var + 1e-10)
    numerator = (img - local_mean) * (Amax * Dd)
    denominator = Amax * local_std + Dd
    result = numerator / denominator + p * Md + (1 - p) * local_mean
    result = np.clip(result, 0, 255).astype(np.uint8)
    return result

img = cv2.imread("input.jpg", 0)
filtered = wallis_filter(img)
cv2.imwrite("output.jpg", filtered)

Рис 12. Фильтр Уоллеса

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

• Алгоритм Канни справляется лучше пространственных фильтров по нахождению контура и фильтрации шума.

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

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

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

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

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

2. Гонсалес Р. Мир цифровой обработки/Р. Гонсалес, Р. Вудс - Москва: Техносфера, 2012 - 1104 с.

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