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

Опера́тор Со́беля (англ. Sobel operator), який іноді називають опера́тором Со́беля — Фе́льдмана (англ. Sobel–Feldman operator) та фі́льтром Со́беля (англ. Sobel filter), використовують в обробці зображень та комп'ютернім баченні, зокрема в алгоритмах виявляння контурів, де він створює зображення, яке виділяє контури. Його названо на честь Ірвіна Собеля^[en] та Гері Фельдмана^[en], колег зі Стенфордської лабораторії штучного інтелекту^[en] (англ. SAIL). Собель та Фельдман запропонували ідею «ізотропного оператора градієнта зображення 3 × 3» на виступі в SAIL у 1968 році.^[1] Технічно це оператор дискретного диференціювання(інші мови), який обчислює наближення градієнта^[en] функції яскравості зображення. У кожній точці зображення результат оператора Собеля — Фельдмана — або відповідний вектор градієнта, або норма цього вектора. Оператор Собеля — Фельдмана ґрунтується на згортанні зображення з невеликим роздільним цілочисловим фільтром в горизонтальному та вертикальному напрямках, і тому відносно невитратний з погляду обчислень. З іншого боку, наближення градієнтна, яке він створює, відносно грубе, зокрема для високочастотних мінливостей на зображенні.

Формулювання

Цей оператор використовує два ядра 3×3, які згортають з первинним зображенням, щоб обчислювати наближення похідних — однієї для горизонтальних змін, та однієї для вертикальних. Якщо ми визначимо A як первинне зображення, а G_x та G_y — два зображення, що в кожній точці містять наближення горизонтальної та вертикальної похідних відповідно, то ці обчислення такі:^[2]

\mathbf {G} _{x}={\begin{bmatrix}+1&0&-1\\+2&0&-2\\+1&0&-1\end{bmatrix}}*\mathbf {A} ,\quad \mathbf {G} _{y}={\begin{bmatrix}+1&+2&+1\\0&0&0\\-1&-2&-1\end{bmatrix}}*\mathbf {A}

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

Оскільки ядра Собеля можливо розкласти як добутки усереднювального та диференціювального ядер, вони обчислюють градієнт зі згладжуванням. Наприклад, $\mathbf {G} _{x}$ можливо записати як

\mathbf {G} _{x}={\begin{bmatrix}1\\2\\1\end{bmatrix}}*\left({\begin{bmatrix}+1&0&-1\end{bmatrix}}*\mathbf {A} \right),\quad \mathbf {G} _{y}={\begin{bmatrix}+1\\0\\-1\end{bmatrix}}*\left({\begin{bmatrix}1&2&1\end{bmatrix}}*\mathbf {A} \right)

Координату x тут визначено як зростальну «праворуч», а координату y — як зростальну «донизу». У кожній точці зображення отримані наближення градієнта можливо об'єднувати, щоб отримувати величину градієнта, використовуючи

\mathbf {G} ={\sqrt {{\mathbf {G} _{x}}^{2}+{\mathbf {G} _{y}}^{2}}}

Використовуючи цю інформацію, ми також можемо обчислювати напрямок градієнта:

\mathbf {\Theta } =\operatorname {atan2} (\mathbf {G} _{y},\mathbf {G} _{x})

де, наприклад, $\mathbf {\Theta }$ дорівнює 0 для вертикального контуру, світлішого з правого боку (щодо $\operatorname {atan2}$ див. atan2^[en]).

Формальніше

Оскільки функція яскравості цифрового зображення відома лише в дискретних точках, похідні цієї функції неможливо визначити, якщо ми не припустимо, що в основі лежить диференційовна функція яскравості, з якої було зроблено вибірку в точках зображення. За деяких додаткових припущень похідну неперервної функції яскравості можливо обчислювати як функцію вибіркової функції яскравості, тобто цифрового зображення. Виявляється, що похідні в будь-якій конкретній точці є функціями значень яскравості практично в усіх точках зображення. Проте наближення цих похідних функцій можливо визначити з меншим або більшим ступенем точності.

Оператор Собеля — Фельдмана пропонує доволі неточне наближення градієнта зображення, але все ще має достатню якість для практичного використання в багатьох застосуваннях. Точніше, він використовує значення яскравості лише в області 3×3 навколо кожної точки зображення, щоби наблизити відповідний градієнт зображення, й використовує лише цілі значення для коефіцієнтів, які зважують яскравості зображення, щоб отримати наближення градієнта.

Розширення на інші виміри

Оператор Собеля — Фельдмана складається з двох роздільних дій:^[3]

Згладжування перпендикулярно напрямку похідної за допомогою трикутного фільтра: $h(-1)=1,h(0)=2,h(1)=1$
Простої центральної різниці в напрямку похідної: $h'(-1)=1,h'(0)=0,h'(1)=-1$

Фільтри Собеля — Фельдмана для похідних зображення в різних вимірностях, де $x,y,z,t\in \left\{0,-1,1\right\}$ :

1 вимір: $h_{x}'(x)=h'(x);$

2 виміри: $h_{x}'(x,y)=h'(x)h(y)$

2 виміри: $h_{y}'(x,y)=h(x)h'(y)$

3 виміри: $h_{y}'(x,y,z)=h(x)h'(y)h(z)$

3 виміри: $h_{z}'(x,y,z)=h(x)h(y)h'(z)$

4 виміри: $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}}={\begin{bmatrix}1\\1\end{bmatrix}}*{\begin{bmatrix}1\\1\end{bmatrix}}{\begin{bmatrix}1&-1\end{bmatrix}}*{\begin{bmatrix}1&1\end{bmatrix}}

{\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}}={\begin{bmatrix}1\\1\end{bmatrix}}*{\begin{bmatrix}\ \ 1\\-1\end{bmatrix}}{\begin{bmatrix}1&1\end{bmatrix}}*{\begin{bmatrix}1&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 \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, де P — піксельна матриця.

Приклад

Результат оператора Собеля — Фельдмана — це двовимірна мапа градієнта в кожній точці. Її можливо обробляти та розглядати так, ніби вона й сама є зображенням, із областями високого градієнта (імовірними контурами), видимими як білі лінії. Наступні зображення ілюструють це, показуючи обчислення оператора Собеля — Фельдмана на простому зображенні.

Перевірне зображення цегляної стіни та велостоянки у відтінках сірого	Нормована величина градієнта від оператора Собеля — Фельдмана
Нормований x-градієнт від оператора Собеля — Фельдмана	Нормований y-градієнт від оператора Собеля — Фельдмана

Наведені нижче зображення ілюструють зміну напрямку градієнта на крузі у відтінках сірого. Коли знаки $\mathbf {G_{x}}$ та $\mathbf {G_{y}}$ однакові, кут градієнта додатний, а коли різні, від'ємний. У наведеному нижче прикладі червоний і жовтий кольори на контурі кола позначують додатні кути, а синій та блакитний — від'ємні. Вертикальні контури ліворуч і праворуч кола мають кут 0, оскільки немає локальної зміни в $\mathbf {G_{y}}$ . Горизонтальні ребра вгорі та внизу кола мають кути − $π$ /2 та $π$ /2 відповідно, оскільки немає локальних змін у $\mathbf {G_{x}}$ . Від'ємний кут для верхнього контуру означає перехід від світлої області до темної, а додатний кут для нижнього контуру означає перехід від темної області до світлої. Усі інші пікселі позначено чорним через відсутність локальних змін $\mathbf {G_{x}}$ та $\mathbf {G_{y}}$ , і тому кут невизначений. Оскільки кут є функцією відношення $\mathbf {G_{y}}$ до $\mathbf {G_{x}}$ , пікселі з малими темпами зміни все ще можуть викликати велику реакцію кута. В результаті шум може викликати велику реакцію кута, що зазвичай є небажаним. Використовуючи інформацію про кут градієнта для застосувань обробки зображень, слід докладати зусиль, щоб усунути шум зображення задля зменшення цієї помилкової реакції.

Альтернативні оператори

Оператор Собеля — Фельдмана, хоч і зменшує артефакти, пов'язані з чистим оператором центральних різниць, не демонструє доброї обертової симетрії (приблизно 1° похибки). Шарр шукав можливість оптимізувати цю властивість, створивши ядра, оптимізовані для конкретної заданої числової точності (цілі числа, числа з рухомою комою…) та розмірності (1 вимір, 2 виміри, 3).^[4]^[5] Там було запропоновано оптимізовані ядра тривимірних фільтрів розміром до 5×5×5, але найчастіше використовуваними ядрами з похибкою близько 0,2° є

h_{x}'(:,:)={\begin{bmatrix}+3&0&-3\\+10&0&-10\\+3&0&-3\end{bmatrix}}\ \ \ \ \ \ \ \ \ h_{y}'(:,:)={\begin{bmatrix}+3&+10&+3\\0&0&0\\-3&-10&-3\end{bmatrix}}

Це розкладається аналогічно:

${\begin{bmatrix}3&10&3\end{bmatrix}}={\begin{bmatrix}3&1\end{bmatrix}}*{\begin{bmatrix}1&3\end{bmatrix}}$

Опера́тори Ша́рра (англ. Scharr operators) — це результат оптимізації, яка мінімізує зважену середньоквадратичну кутову похибку в області Фур'є. Ця оптимізація виконується за умови, що отримані фільтри чисельно узгоджені. Тому вони дійсно є ядрами похідних, а не просто дотримуються обмежень симетрії. Оптимальним 8-бітним цілочисловим фільтром 3x3, що випливає з теорії Шарра, є

h_{x}'(:,:)={\begin{bmatrix}47&0&-47\\162&0&-162\\47&0&-47\end{bmatrix}}\ \ \ \ \ \ \ \ \ h_{y}'(:,:)={\begin{bmatrix}47&162&47\\0&0&0\\-47&-162&-47\end{bmatrix}}

Подібну стратегію оптимізації та отримані фільтри також запропонували Фарид і Сімончеллі.^[6]^[7] Вони також досліджують схеми похідних вищого порядку. На відміну від роботи Шарра, ці фільтри не повинні бути чисельно узгодженими.

Задачу проєктування фільтрів похідних було переглянуто, наприклад, Круном.^[8]

Фільтри похідних на основі довільних кубічних сплайнів запропонував Гаст.^[9] Він показав, як можливо правильно обчислювати похідні першого та другого порядку за допомогою кубічних чи тригонометричних сплайнів за допомогою підходу подвійного фільтрування, який дає фільтри довжини 7.

Іншим подібним оператором, який спочатку було породжено з оператора Собеля, є оператор Каялі,^[10] згортковий фільтр 3x3 на основі ідеальної обертової симетрії.

Напрямково оптимальні ядра похідних значно знижують систематичні похибки в оцінюванні оптичного потоку. Більші схеми з іще більшою точністю та сімействами оптимізованих фільтрів для розширеного оцінювання оптичного потоку було запропоновано в подальшій роботі Шарра.^[11] Було досліджено набори фільтрів похідних другого порядку для прозорого оцінювання руху.^[12] Було помічено, що чим більші отримані ядра, тим краще вони наближують фільтри похідних гауссіана.

Приклад порівняння

Тут використовують чотири різні оператори градієнта для оцінювання величини градієнта перевірного зображення.

Перевірне зображення цегляної стіни та велостоянки у відтінках сірого	Величина градієнта від оператора Собеля — Фельдмана	Величина градієнта від оператора Шарра
Величина градієнта від оператора Робертса	Величина градієнта від оператора Прюітт

Втілення в MATLAB

clc
clear all
close all

test_img = imread('gantrycrane.png');
gray_img = rgb2gray(test_img);
sobel_img = sobel(gray_img);

figure
imshow(test_img)

figure
imshow(gray_img)

figure
imshow(sobel_img)

function output_image = sobel(A)
Gx = [-1 0 1; -2 0 2; -1 0 1]
Gy = [-1 -2 -1; 0 0 0; 1 2 1]

rows = size(A, 1)
columns = size(A, 2)
mag = zeros(size(A));

A = double(A);

for i=1:rows-2
    for j=1:columns-2
	    S1 = sum(sum(Gx.*A(i:i+2, j:j+2)));
	    S2 = sum(sum(Gy.*A(i:i+2, j:j+2)));

	    mag(i + 1, j + 1) = sqrt(S1.^2 + S2.^2);
    end
end

threshold = 70 % залежить віл застосування [0–255]
output_image = max(mag, threshold);
output_image(output_image == round(threshold)) = 0;
end

Наведений вище код MATLAB для демонстрування фільтра Собеля використовуватиме зображення, що йде в пакеті з самою MATLAB ('gantrycrane.png'). На виході будуть первинне зображення, версія первинного зображення у відтінках сірого, та результат фільтра Собеля.

Див. також

Примітки

↑ Irwin Sobel, 2014, History and Definition of the Sobel Operator (англ.)
↑ Feature Detectors – Sobel Edge Detector (англ.)
↑ K. Engel (2006). Real-time volume graphics. с. 112—114. (англ.)
↑ Scharr, Hanno, 2000, Dissertation (in German), 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. (англ.)
↑ H. Farid and E. P. Simoncelli, Optimally Rotation-Equivariant Directional Derivative Kernels, Int'l Conf Computer Analysis of Images and Patterns, pp. 207–214, Sep 1997. (англ.)
↑ H. Farid and E. P. Simoncelli, Differentiation of discrete multi-dimensional signals, IEEE Trans Image Processing, vol.13(4), pp. 496–508, Apr 2004. (англ.)
↑ D. Kroon, 2009, Short Paper University Twente, Numerical Optimization of Kernel-Based Image Derivatives . (англ.)
↑ A. Hast., "Simple filter design for first and second order derivatives by a double filtering approach", Pattern Recognition Letters, Vol. 42, no.1 June, pp. 65–71. 2014. (англ.)
↑ Dim, Jules R.; Takamura, Tamio (11 грудня 2013). Alternative Approach for Satellite Cloud Classification: Edge Gradient Application. Advances in Meteorology (англ.). 2013: 1—8. doi:10.1155/2013/584816. ISSN 1687-9309. (англ.)
↑ Scharr, Hanno (2007). Optimal Filters for Extended Optical Flow. Complex Motion. Lecture Notes in Computer Science. Т. 3417. Berlin, Heidelberg: Springer Berlin Heidelberg. с. 14—29. doi:10.1007/978-3-540-69866-1_2. ISBN 978-3-540-69864-7. (англ.)
↑ Scharr, Hanno, OPTIMAL SECOND ORDER DERIVATIVE FILTER FAMILIES FOR TRANSPARENT MOTION ESTIMATION 15th European Signal Processing Conference (EUSIPCO 2007), Poznan, Poland, September 3–7, 2007. (англ.)

Посилання

Вікіпідручник має книгу на тему

:en:Fractals/Computer_graphic_techniques/2D#Sobel_filter

[1] Irwin Sobel, 2014, History and Definition of the Sobel Operator (англ.)

[2] Feature Detectors – Sobel Edge Detector (англ.)

[3] K. Engel (2006). Real-time volume graphics. с. 112—114. (англ.)

[4] Scharr, Hanno, 2000, Dissertation (in German), Optimal Operators in Digital Image Processing . (нім.)

[5] B. Jähne, H. Scharr, and S. Körkel. Principles of filter design. In Handbook of Computer Vision and Applications. Academic Press, 1999. (англ.)

[6] H. Farid and E. P. Simoncelli, Optimally Rotation-Equivariant Directional Derivative Kernels, Int'l Conf Computer Analysis of Images and Patterns, pp. 207–214, Sep 1997. (англ.)

[7] H. Farid and E. P. Simoncelli, Differentiation of discrete multi-dimensional signals, IEEE Trans Image Processing, vol.13(4), pp. 496–508, Apr 2004. (англ.)

[8] D. Kroon, 2009, Short Paper University Twente, Numerical Optimization of Kernel-Based Image Derivatives . (англ.)

[9] A. Hast., "Simple filter design for first and second order derivatives by a double filtering approach", Pattern Recognition Letters, Vol. 42, no.1 June, pp. 65–71. 2014. (англ.)

[10] Dim, Jules R.; Takamura, Tamio (11 грудня 2013). Alternative Approach for Satellite Cloud Classification: Edge Gradient Application. Advances in Meteorology (англ.). 2013: 1—8. doi:10.1155/2013/584816. ISSN 1687-9309. (англ.)

[Scharr_pp._14–29-11] Scharr, Hanno (2007). Optimal Filters for Extended Optical Flow. Complex Motion. Lecture Notes in Computer Science. Т. 3417. Berlin, Heidelberg: Springer Berlin Heidelberg. с. 14—29. doi:10.1007/978-3-540-69866-1_2. ISBN 978-3-540-69864-7. (англ.)

[12] Scharr, Hanno, OPTIMAL SECOND ORDER DERIVATIVE FILTER FAMILIES FOR TRANSPARENT MOTION ESTIMATION 15th European Signal Processing Conference (EUSIPCO 2007), Poznan, Poland, September 3–7, 2007. (англ.)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

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

Зміст

Формулювання

Формальніше

Розширення на інші виміри

Технічні деталі

Приклад

Альтернативні оператори

Приклад порівняння

Втілення в MATLAB

Див. також

Примітки

Посилання

Навігаційне меню

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

Формулювання

Формальніше

Розширення на інші виміри

Технічні деталі

Приклад

Альтернативні оператори

Приклад порівняння

Втілення в MATLAB

Див. також

Примітки

Посилання

Навігаційне меню

Пошук