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

Оператор Собеля
Паровая машина в цвете.
Применение оператора Собеля к изображению

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

Содержание

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

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

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

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

Строго говоря, оператор использует ядра 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

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Оператор Собеля" в других словарях:

  • Оператор Айверсона — Оператор Айверсона, в дисциплине компьютерного зрения  оператор обнаружения границ в изображениях. Был разработан Ли Айверсоном[1] и Стивеном Цукером[2]. Описание метода было впервые опубликовано в журнале IEEE Transactions on Pattern… …   Википедия

  • Оператор Ротуэлла — Оператор Ротуэлла, в дисциплине компьютерного зрения  оператор для обнаружения границ, представленный Чарлзом Ротуэллом (англ. C. A. Rothwell) на Симпозиуме IEEE по компьютерному зрению[1] в 1995 году. В целом, оператор Ротуэлла… …   Википедия

  • Оператор Кэнни — (детектор границ Кэнни, алгоритм Кэнни) в дисциплине компьютерного зрения  оператор обнаружения границ изображения. Был разработан в 1986 году Джоном Кэнни (англ. John F. Canny) и использует многоступенчатый алгоритм для… …   Википедия

  • Оператор Прюитт — Оператор Прюитт, в дисциплине компьютерного зрения  метод выделения границ в обработке изображений, который вычисляет максимальный отклик на множестве ядер свёртки для нахождения локальной ориентации границы в каждом пикселе. Он был… …   Википедия

  • Оператор Canny — Canny  оператор обнаружения границ. Был разработан в 1986 году Джоном Канни и использует многоступенчатый алгоритм для обнаружения широкого спектра границ в изображениях. Канни изучил математическую проблему получения фильтра, оптимального… …   Википедия

  • Перекрёстный оператор Робертса — Изображение паровой машины Действие оператора Робертса применительно к изображению …   Википедия

  • Прюитт — Оператор Прюитт  метод выделения границ в обработке изображений, который вычисляет максимальный отклик на множестве ядер свёртки для нахождения локальной ориентации границы в каждом пикселе. Он был создан доктором Джудит Прюитт (Judith… …   Википедия

  • Выделение границ — Пример выделения границ для определения положения автомобильных номеров. Оригинальное изображение и результат. Выделение границ (выделение краёв)  термин в теории обработки изображения и компьютерного …   Википедия

  • Гистограмма направленных градиентов — (англ. Histogram of Oriented Gradients, HOG) – дескрипторы особых точек, которые используются в компьютерном зрении и обработке изображений с целью распознавания …   Википедия

  • Анализируй то — Analyze That Жанр Комедия …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»