Sobel Operator

Introduction

The Sobel operator is a convolution kernel used for edge detection in images. It is a good approximation of the derivatives of the image intensity function.

In this blog post, we will discuss the Sobel operator and its approximation of the derivatives of the image intensity function.

Sobel Operator

Sobel Operator Convolutions

Given a source image $A$, the Sobel operator is defined as the following two $3 \times 3$ kernels: $K_x$ and $K_y$, convolved on the image $A$.

$$
\begin{align}
K_x &=
\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 \\
+2 \\
+1 \\
\end{bmatrix}
\otimes
\begin{bmatrix}
+1 \\
0 \\
-1 \\
\end{bmatrix}
\end{align}
$$

$$
\begin{align}
K_y &=
\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 \\
0 \\
-1 \\
\end{bmatrix}
\otimes
\begin{bmatrix}
+1 \\
+2 \\
+1 \\
\end{bmatrix} \\
\end{align}
$$

where $\otimes$ denotes the outer product, indicating the kernels are low rank and separable.

The resulting matrices, $G_x$ and $G_y$, are the approximations of the derivatives of the image intensity function of $A$, along the horizontal and vertical dimensions.

$$
\begin{align}
G_x &= K_x \ast A \\
G_y &= K_y \ast A \\
\end{align}
$$

where $\ast$ denotes the convolution in signal processing.

There are variants of kernel matrices for the cross-correlation in signal processing, i.e., the convolution in deep learning. In this article, we will only focus on the convolution in signal processing.

It also turns out that the Sobel operator convolutions are separable. The Sobel operator convolutions can be computed as one $1 \times 3$ kernel and one $3 \times 1$ kernel convolved on the image $A$ in sequence and the order does not matter.

$$
\begin{align}
G_x
&= K_x \ast A \\
&= \begin{bmatrix}
+1 \\
+2 \\
+1 \\
\end{bmatrix} \ast \left(
\begin{bmatrix}
+1 & 0 & -1
\end{bmatrix} \ast A \right) \\
&= \begin{bmatrix}
+1 & 0 & -1
\end{bmatrix} \ast \left(
\begin{bmatrix}
+1 \\
+2 \\
+1 \\
\end{bmatrix} \ast A \right) \\
\end{align}
$$

$$
\begin{align}
G_y
&= K_y \ast A \\
&= \begin{bmatrix}
+1 \\
0 \\
-1 \\
\end{bmatrix} \ast \left(
\begin{bmatrix}
+1 & +2 & +1
\end{bmatrix} \ast A \right) \\
&= \begin{bmatrix}
+1 & +2 & +1
\end{bmatrix} \ast \left(
\begin{bmatrix}
+1 \\
0 \\
-1 \\
\end{bmatrix} \ast A \right) \\
\end{align}
$$

The magnitude of the gradient is defined as the L2 norm of the gradient vector $G = (G_x, G_y)$.

$$
\lvert G \rvert = \sqrt{G_x^2 + G_y^2}
$$

The direction of the gradient is defined as the angle of the gradient vector $G = (G_x, G_y)$.

$$
\theta = \arctan{\frac{G_y}{G_x}}
$$

Sobel Operator Approximation of Derivatives

Let’s take a look at why the Sobel operator is a good approximation of the derivatives of the image intensity function.

Given a $3 \times 3$ image patch $I$, the pixel values are defined as follows.

$$
\begin{align}
I &=
\begin{bmatrix}
I_{00} & I_{01} & I_{02} \\
I_{10} & I_{11} & I_{12} \\
I_{20} & I_{21} & I_{22} \\
\end{bmatrix} \\
\end{align}
$$

The image intensity function gradient along the horizontal dimension at pixel $I_{11}$ can be approximated as follows.

$$
\begin{align}
\frac{\partial I}{\partial x} \bigg\vert_{x = 1, y = 1} \approx \frac{I_{12} - I_{10}}{2}
\end{align}
$$

Similarly, the image intensity function gradient along the vertical dimension at pixel $I_{11}$ can be approximated as follows.

$$
\begin{align}
\frac{\partial I}{\partial y} \bigg\vert_{x = 1, y = 1} \approx \frac{I_{21} - I_{01}}{2}
\end{align}
$$

But why the above formulation only uses two pixels for approximating the gradient along each dimension whereas the Sobel operator uses six pixels?

This is because the Sobel operator computed the gradient smoothed using another symmetric kernel. Concretely, we have the following gradients along the horizontal dimension.

$$
\begin{align}
\frac{\partial I}{\partial x} \bigg\vert_{x = 0, y = 1} &\approx \frac{I_{02} - I_{00}}{2} \\
\frac{\partial I}{\partial x} \bigg\vert_{x = 1, y = 1} &\approx \frac{I_{12} - I_{10}}{2} \\
\frac{\partial I}{\partial x} \bigg\vert_{x = 2, y = 1} &\approx \frac{I_{22} - I_{20}}{2} \\
\end{align}
$$

The gradient along the horizontal dimension at pixel $I_{11}$ is the weighted average of the above three gradients using hard-coded smooth coefficients $2$, $4$, and $2$.

$$
\begin{align}
\frac{\partial I}{\partial x} \bigg\vert_{x = 1, y = 1} &\approx 2 \times \frac{I_{02} - I_{00}}{2} + 4 \times \frac{I_{12} - I_{10}}{2} + 2 \times \frac{I_{22} - I_{20}}{2} \\
&= I_{02} - I_{00} + 2 \times I_{12} - 2 \times I_{10} + I_{22} - I_{20} \\
&= K_x \ast I \\
\end{align}
$$

Because it does not matter whether we compute the non-smoothed gradient first and then smooth it or we smooth the image first and then compute the gradient, the Sobel operator is separable and it can be computed as one $1 \times 3$ kernel and one $3 \times 1$ kernel convolved on the image in sequence and the order does not matter.

FAQs

If the Convolution Filter is Separable, is the Convolution Separable?

Let’s create a Python script to verify a convolution whose $3 \times 3$ filter is low rank and separable to one $1 \times 3$ and one $3 \times 1$ filters.

convolution.py

import numpy as np
import scipy.signal

# Create a 3 x 1 filter.
filter_1 = np.array([[1, 2, 3]]).T
print("filter_1 = \n{}".format(filter_1))

# Create a 1 x 3 filter.
filter_2 = np.array([[4, 5, 6]])
print("filter_2 = \n{}".format(filter_2))

# Create a 3 x 3 filter by the outer product of the two filters.
filter = filter_1 @ filter_2
print("filter = \n{}".format(filter))

# The rank of filter.
print("rank of filter = {}".format(np.linalg.matrix_rank(filter)))

# Create a 6 x 6 image.
image = np.arange(1, 6 * 6 + 1).reshape(6, 6)

# Compute the convolution.
# Convolution using the 3 x 3 filter.
convolution_1 = scipy.signal.convolve2d(image, filter, mode="valid")
print("3x3 convolution = \n{}".format(convolution_1))
# Convolution using the 3 x 1 filter and then the 1 x 3 filter.
convolution_2 = scipy.signal.convolve2d(scipy.signal.convolve2d(image, filter_1, mode="valid"), filter_2, mode="valid")
print("3x1 and 1x3 convolution = \n{}".format(convolution_2))
# Convolution using the 1 x 3 filter and then the 3 x 1 filter.
convolution_3 = scipy.signal.convolve2d(scipy.signal.convolve2d(image, filter_2, mode="valid"), filter_1, mode="valid")
print("1x3 and 3x1 convolution = \n{}".format(convolution_3))

assert np.array_equal(convolution_1, convolution_2)
assert np.array_equal(convolution_1, convolution_3)

We could see that actually the convolution whose $3 \times 3$ filter is low rank and separable to one $1 \times 3$ and one $3 \times 1$ filters is also separable.

$ python3 convolution.py
filter_1 =
[[1]
 [2]
 [3]]
filter_2 =
[[4 5 6]]
filter =
[[ 4  5  6]
 [ 8 10 12]
 [12 15 18]]
image =
[[ 1  2  3  4  5]
 [ 6  7  8  9 10]
 [11 12 13 14 15]
 [16 17 18 19 20]
 [21 22 23 24 25]]
3x3 convolution =
[[ 468  558  648]
 [ 918 1008 1098]
 [1368 1458 1548]]
3x1 and 1x3 convolution =
[[ 468  558  648]
 [ 918 1008 1098]
 [1368 1458 1548]]
1x3 and 3x1 convolution =
[[ 468  558  648]
 [ 918 1008 1098]
 [1368 1458 1548]]

But this is not generally true. The convolution is separable if and only if the rank of the filter is 1.

In addition, performing the convolution using the separable filters does not save the computation. So it is not necessary to use the separable filters for computing the Sobel operator convolutions.

References

• Sobel Operator - Wikipedia
• Sobel Derivatives - OpenCV
• Convolved2D - SciPy