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

Паровая машина в цвете.

Применение оператора Собеля к изображению

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

Упрощённое описание

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

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

Формализация

Строго говоря, оператор использует ядра 3×3, с которыми сворачивают исходное изображение для вычисления приближенных значений производных по горизонтали и по вертикали. Пусть A исходное изображение, а G_x и G_y — два изображения, где каждая точка содержит приближенные производные по x и по y. Они вычисляются следующим образом:

$\mathbf{G}_y = \begin{bmatrix} -1 & -2 & -1 \\ 0 & 0 & 0 \\ +1 & +2 & +1 \end{bmatrix} * \mathbf{A} \quad \mbox{and} \quad \mathbf{G}_x = \begin{bmatrix} -1 & 0 & +1 \\ -2 & 0 & +2 \\ -1 & 0 & +1 \end{bmatrix} * \mathbf{A}$

где $*$ обозначает двумерную операцию свертки.

Координата x здесь возрастает «направо», а y — «вниз». В каждой точке изображения приближенное значение величины градиента можно вычислить, используя полученные приближенные значения производных:

$\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }$ (имеется в виду поэлементно)

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

$\mathbf{\Theta} = \operatorname{arctan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)$

где, к примеру, угол Θ равен нулю для вертикальной границы, у которой тёмная сторона слева.

Строго говоря..

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

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

Расширение на другое количество измерений

Оператор Собеля состоит из двух отдельный операций ^[1]:

• Сглаживание треугольным фильтром в перпендикулярном к производной направлении: $h(-1) = 1, h(0) = 2, h(1) = 1$
• Нахождение простого центрального изменения в направлении производной: $h'(-1) = 1, h'(0) = 0, h'(1) = -1$

Фильтры Собеля для производных изображения в разных пространствах для $x,y,z,t \in (0,-1,1)$ :

1D: $h_x'(x) = h'(x);$

2D: $h_x'(x,y) = h'(x)h(y)$

3D: $h_x'(x,y,z) = h'(x)h(y)h(z)$

4D: $h_x'(x,y,z,t) = h'(x)h(y)h(z)h(t)$

Вот пример трёхмерного ядра Собеля для оси z:

$h_z'(:,:,-1) = \begin{bmatrix} +1 & +2 & +1 \\ +2 & +4 & +2 \\ +1 & +2 & +1 \end{bmatrix} \quad h_z'(:,:,0) = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \quad h_z'(:,:,1) = \begin{bmatrix} -1 & -2 & -1 \\ -2 & -4 & -2 \\ -1 & -2 & -1 \end{bmatrix}$

Технические детали

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

$\begin{bmatrix} +1 & 0 & -1 \\ +2 & 0 & -2 \\ +1 & 0 & -1 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} \begin{bmatrix} +1 & 0 & -1 \end{bmatrix} \quad \quad \begin{bmatrix} +1 & +2 & +1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \end{bmatrix} = \begin{bmatrix} +1 \\ 0 \\ -1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 \end{bmatrix}$

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

$\mathbf{G}_x = \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} * \left ( \begin{bmatrix} +1 & 0 & -1 \end{bmatrix} * \mathbf{A} \right ) \quad \mbox{and} \quad \mathbf{G}_y = \begin{bmatrix} +1 \\ 0 \\ -1 \end{bmatrix} * \left ( \begin{bmatrix} 1 & 2 & 1 \end{bmatrix} * \mathbf{A} \right )$

Раздельность этих вычислений может привести к уменьшению арифметических действий с каждым пикселом.

Применение свертки K к группе пикселей P можно представить псевдокодом:

N(x, y) = Сумма { K(i, j).P(x-i, y-j)}, для i, j от −1 до 1.

N(x, y) представляет собой результат применения матрицы свёртки K к P.

Программная реализация оператора Собела может эффективно использовать SIMD-расширения системы команд современных процессоров (т. н. векторизация кода), при этом выигрыш в скорости вычисления оператора может составлять до 5 раз по сравнению с высокоуровневой реализацией ^[2]. Ручное кодирование на языке ассемблера позволяет обогнать по скорости такие компиляторы как Microsoft Visual C++ и Intel C++ Compiler. Вычисление оператора Собела элементарно распараллеливается на произвольное число потоков (в пределе каждую точку результирующего изображения можно вычислять независимо от соседних). Например, при наличии двух процессоров (ядер) верхний полукадр изображения может быть обработан одним из них, а нижний — другим.

Примеры

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

Полутоновое изображение кирпичной стены и стойки для велосипеда	Нормализованный Собелев градиент изображения кирпичной стены и стойки велосипеда
Нормализованный Собелев градиент изображения по x	Нормализованный Собелев градиент изображения по y

Оператор Щарра

Оператор Собеля сглаживает паразитные эффекты на изображении, вызываемые чисто центрально-дифференциальным оператором, но не обладает полной вращательной симметрией. Щарр исследовал улучшение этого свойства и нашёл, что лучшие результаты даёт следующее ядро^{[3] [4]}:

$\begin{bmatrix} +3 & +10 & +3 \\ 0 & 0 & 0 \\ -3 & -10 & -3 \end{bmatrix} \begin{bmatrix} +3 & 0 & -3 \\ +10 & 0 & -10 \\ +3 & 0 & -3 \end{bmatrix}$

См. также

• Цифровая обработка изображений
• Компьютерное зрение
• Выделение границ
• Оператор Canny
• Градиент
• Перекрёстный оператор Робертса (простейший оператор выделения границ)
• Дискретный оператор Лапласа
• Оператор Превитт

Примечания

1. ↑ K. Engel (2006), «Real-time volume graphics,», сс. 112-114 
2. ↑ Ватутин Э.И., Мирошниченко С.Ю., Титов В.С. Программная оптимизация оператора Собела с использованием SIMD-расширений процессоров семейства x86. Телекоммуникации. 2006. № 6. С. 12–16. (2006). Архивировано из первоисточника 13 апреля 2012.
3. ↑ Scharr, Hanno, 2000, диссертация (в Германии), Optimal Operators in Digital Image Processing.
4. ↑ B. Jähne, H. Scharr, and S. Körkel. Principles of filter design. In Handbook of Computer Vision and Applications. Academic Press, 1999.

Неопубликованное:

Sobel, I., Feldman,G., «A 3x3 Isotropic Gradient Operator for Image Processing», представлялось на Стэнфордском проекте ИИ в 1968 г., неопубликовано, но часто цитируется, опирается на «Pattern Classification and Scene Analysis», Duda,R. и Hart,P., изд. John Wiley and Sons, 1973, стр. 271—272

Ссылки

• Список отсылок на работы Ирвина Собеля в Digital Bibliography & Library Project
• Анализ уменьшения погрешности оператора Собеля
• Шумоустойчивые операторы выделения границ
• оператор Собеля в OpenCV