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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Паровая машина в цвете.
Применение оператора Собеля к изображению

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

Упрощённое описание[править | править вики-текст]

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

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

Формализация[править | править вики-текст]

Строго говоря, оператор использует ядра 3×3, с которыми сворачивают исходное изображение для вычисления приближенных значений производных по горизонтали и по вертикали. Пусть A исходное изображение, а Gx и Gy — два изображения, где каждая точка содержит приближенные производные по 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}

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


\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}

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  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

Ссылки[править | править вики-текст]