Русская Википедия:Оператор Собеля
Оператор Собеля — дискретный дифференциальный оператор, вычисляющий приближённое значение градиента яркости изображения. Результатом применения оператора Собеля в каждой точке изображения является либо вектор градиента яркости в этой точке, либо его норма. Используется в области обработки изображений, в частности, часто применяется в алгоритмах выделения границ.
Описание
Оператор Собеля основан на свёртке изображения небольшими сепарабельными целочисленными фильтрами в вертикальном и горизонтальном направлениях, поэтому его относительно легко вычислять. С другой стороны, используемая им аппроксимация градиента достаточно грубая, особенно это сказывается на высокочастотных колебаниях изображения.
Оператор вычисляет градиент яркости изображения в каждой точке. Так находится направление наибольшего увеличения яркости и величина её изменения в этом направлении. Результат показывает, насколько «резко» или «плавно» меняется яркость изображения в каждой точке, а значит, вероятность нахождения точки на грани, а также ориентацию границы. На практике вычисление величины изменения яркости (вероятности принадлежности к грани) надёжнее и проще в интерпретации, чем расчёт направления.
Математически градиент функции двух переменных для каждой точки изображения (которой и является функция яркости) — двумерный вектор, компонентами которого являются производные яркости изображения по горизонтали и вертикали. В каждой точке изображения градиентный вектор ориентирован в направлении наибольшего увеличения яркости, а его длина соответствует величине изменения яркости. Это означает, что результатом оператора Собеля в точке, лежащей в области постоянной яркости, будет нулевой вектор, а в точке, лежащей на границе областей различной яркости, — вектор, пересекающий границу в направлении увеличения яркости.
Формализация
Строго говоря, оператор использует ядра <math>3 \times 3</math>, с которыми сворачивают исходное изображение для вычисления приближённых значений производных по горизонтали и по вертикали. Пусть <math> \mathbf{A} </math> — это исходное изображение, а <math> \mathbf{G}_x </math> и <math> \mathbf{G}_y </math> — два изображения, на которых каждая точка содержит приближённые производные по <math> x </math> и по <math> y </math>. Они вычисляются следующим образом:
- <math>
\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} </math>
где <math>*</math> обозначает двумерную операцию свертки.
Координата <math> x </math> здесь возрастает «направо», а <math> y </math> — «вниз». В каждой точке изображения приближённое значение величины градиента можно вычислить путём использования полученных приближенных значений производных:
- <math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math> (имеется в виду поэлементно).
Используя эту информацию, мы можем также вычислить направление градиента:
- <math>\mathbf{\Theta} = \operatorname{arctan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>,
где, к примеру, угол Θ равен нулю для вертикальной границы, у которой тёмная сторона слева.
Уточнение
Поскольку функция яркости известна только в дискретных точках, мы не можем определить производные до тех пор, пока не положим яркость дифференцируемой функцией, которая проходит через эти точки. С этой дополнительной предпосылкой производную дифференцируемой функции яркости можно вычислить как от функции, с которой взяты замеры — точки изображения. Оказывается, что производные в любой отдельной точке есть функции яркости от всех точек изображения. Однако приближения их производных можно определить с большей или меньшей степенью точности.
Оператор Собеля представляет собой более неточное приближение градиента изображения, но он достаточно качественен для практического применения во многих задачах. Точнее, оператор использует значения интенсивности только в окрестности <math>3 \times 3</math> каждого пикселя для получения приближения соответствующего градиента изображения, и использует только целочисленные значения весовых коэффициентов яркости для оценки градиента.
Расширение на другое количество измерений
Оператор Собеля состоит из двух отдельных операций[1]:
- Сглаживание треугольным фильтром в перпендикулярном к производной направлении: <math> h(-1) = 1; \quad h(0) = 2; \quad h(1) =1. </math>
- Нахождение простого центрального изменения в направлении производной: <math> h'(-1) = 1;\quad h'(0) = 0;\quad h'(1) = -1. </math>
Формулы фильтра Собеля для производных изображения в разных пространствах для <math>x,y,z,t \in (0,-1,1) </math>:
- одномерное пространство: <math> h_x'(x) = h'(x); </math>
- двухмерное: <math> h_x'(x,y) = h'(x)h(y); </math>
- трёхмерное: <math> h_x'(x,y,z) = h'(x)h(y)h(z);</math>
- четырёхмерное: <math> h_x'(x,y,z,t) = h'(x)h(y)h(z)h(t).</math>
Вот пример трёхмерного ядра Собеля для оси <math> z</math>:
- <math>
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}. </math>.
Технические детали
Как следует из определения, оператор Собеля можно реализовать простыми техническими и программными средствами: для приближения вектор-градиента нужны только восемь пикселей вокруг точки изображения и целочисленная арифметика. Более того, оба дискретных фильтра, описанные выше, можно разделить:
- <math>\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}, </math>
и две производные, <math> \mathbf{G}_x </math> и <math> \mathbf{G}_y </math>, теперь можно вычислить как
- <math>
\mathbf{G}_x = \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} * \left ( \begin{bmatrix} +1 & 0 & -1 \end{bmatrix} * \mathbf{A} \right )
- \quad \quad
\mathbf{G}_y = \begin{bmatrix} +1 \\ 0 \\ -1 \end{bmatrix} * \left ( \begin{bmatrix} 1 & 2 & 1 \end{bmatrix} * \mathbf{A} \right ). </math>
Раздельность этих вычислений может привести к уменьшению арифметических действий с каждым пикселем.
Применение свёртки <math> K </math> к группе пикселей <math> P </math> можно представить псевдокодом:
N(x, y) = Сумма { K(i, j).P(x-i, y-j)}, для i, j от −1 до 1.
N(x, y) представляет собой результат применения матрицы свёртки K к P.
Программная реализация оператора Собеля может эффективно использовать SIMD-расширения системы команд современных процессоров (т. н. векторизация кода), при этом выигрыш в скорости вычисления оператора может составлять до пяти раз по сравнению с высокоуровневой реализацией[2]. Ручное кодирование на языке ассемблера позволяет обогнать по скорости такие компиляторы, как Microsoft Visual C++ и Intel C++ Compiler.
Вычисление оператора Собеля элементарно распараллеливается на произвольное число потоков (в пределе каждую точку результирующего изображения можно вычислять независимо от соседних). Например, при наличии двух процессоров (ядер) верхний полукадр изображения может быть обработан одним из них, а нижний — другим.
Примеры
Результатом применения оператора Собеля является двумерная карта градиента для каждой точки. Её можно обработать и показать как картинку, на которой участки с большой величиной градиента (в основном, грани) будут видны как белые линии. Нижеприведённые изображения иллюстрируют это на примере простого изображения:
Оператор Щарра
Оператор Собеля сглаживает паразитные эффекты на изображении, вызываемые чисто центрально-дифференциальным оператором, но не обладает полной вращательной симметрией. Щарр исследовал улучшение этого свойства и пришёл к выводу, что лучшие результаты даёт следующее ядро[3][4]:
<math> \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}. </math>
См. также
- Цифровая обработка изображений
- Компьютерное зрение
- Выделение границ
- Оператор Кэнни
- Градиент
- Перекрёстный оператор Робертса (простейший оператор выделения границ)
- Дискретный оператор Лапласа
- Оператор Прюитт
Примечания
Литература
- Sobel I., Feldman G. «A 3x3 Isotropic Gradient Operator for Image Processing», 1968 (неопубл.).
- Duda R., Hart P. Pattern Classification and Scene Analysis. — John Wiley and Sons, 1973. — P. 271—272. (Дуда Р., Харт П. Распознавание образов и анализ сцен. Пер. с англ. Вайнштейна Г.Г. и Васильковского А.М. — М.: Мир, 1976.)
Ссылки
- Список отсылок на работы Ирвина Собеля Шаблон:Wayback в Digital Bibliography & Library Project
- Анализ уменьшения погрешности оператора Собеля
- Шумоустойчивые операторы выделения границ
- Оператор Собеля Шаблон:Wayback в OpenCV
- ↑ Шаблон:Citation
- ↑ Шаблон:Cite web
- ↑ Scharr, Hanno, 2000, диссертация (в Германии), Optimal Operators in Digital Image Processing.
- ↑ B. Jähne, H. Scharr, and S. Körkel. Principles of filter design. In Handbook of Computer Vision and Applications. Academic Press, 1999.
.PNG){kind=link}
.PNG){kind=link}
