Linear (convolution) filters consist of a matrix with coefficients and a gain factor. When considering a linear filter of size 3x3, the 9 matrix coefficients are multiplied with 9 pixel values in the input raster map, this is summed and then multiplied with the gain factor. The result is assigned to the center pixel in the output map.
The following standard filters are known as gradient filters or derivative filters: DFDX, DFDY, DFDDN, DFDUP, D2FDX2, D2FDY2, D2FDXDY. For each group of pixel values considered, they calculate the first or second derivative in one or more directions. Derivative filters are often used in relation to slope calculations.
The standard derivative filters mentioned above have a typical size of 1x5, 5x1, or 5x5. Of course, you can also create your own linear gradient filters.
This topic is intended for people who would like to understand the mathematical background of the coefficients in the matrices of derivative filters. First, 3x3 filters will be described, then 5x5 filters.
Introduction:
The simplest mathematical situation is represented when using a 3x3 filter, however these filters may not be exact enough to calculate slopes. A 3x3 filter uses the 9 input values to calculate a value for the center pixel in the output map.
To do calculations with a 3x3 filter, a local coordinate system (x,y) is defined around the current center pixel, as:
|
(-1,1) |
(0,1) |
(1,1) |
|
|
(-1,0) |
(0,0) |
(1,0) |
|
|
(-1,-1) |
(0,-1) |
(1,-1) |
Both x and y can have the values -1, 0, and 1.
When calculating the first derivative only in the x-direction, y remains 0, and x can have value -1, 0, or 1.
To calculate derivatives, a continuous function is needed. The input pixel values are to be described by a function fx where:
f0 = input pixel value of the center pixel; x=0
f-1 = input pixel value of the pixel to the left of the center pixel; x=-1
f1 = input pixel value of the pixel to the right of the center pixel; x=1
Formulas:
As continuous function, a polynomial function is used. With 9 known values, a second order polynomial can be fitted through these points.
|
(1) |
fxy = a00 + a10 x + a20 x2 + a01 y + a11 xy + a21 x2y + a02 y2 + a12 xy2 + a22 x2y2 |
When we are only interested in the first derivative in x-direction, formula 1 can be simplified by substituting y with 0 to:
|
(2) |
fx = a0 + a1 x + a2 x2 |
The function for the first derivative equals:
|
(3) |
df/dx = f'x = a1 + 2a2 x |
The second derivative equals:
|
(4) |
d2f/dx2 = f"x = 2a2 |
Because we are interested in the derivatives at the central pixel where x=0, in formulas 3 and 4, x can be substituted with 0:
|
(5) |
df/dx = f'0 = a1 |
|
(6) |
d2f/dx2 = f"0 = 2a2 |
To find f-1, f0 and f1, in formula 2, x is substituted with values -1, 0, and 1:
|
(7) |
f-1 = a0 - a1 + a2 |
|
(8) |
f0 = a0 |
|
(9) |
f1 = a0 + a1 + a2 |
Then, by elimination, a1 and a2 are found:
|
(10) |
a1 = (f1 - f-1) / 2 |
|
(11) |
a2 = (f-1 - 2f0 + f1) / 2 |
A 3x3 first derivative filter for the x-direction will thus read:
|
0 |
0 |
0 |
|
|
-1 |
0 |
1 |
|
|
0 |
0 |
0 |
Gain factor = 1/2 = 0.5
A 3x3 second derivative filter for the x-direction will thus read:
|
0 |
0 |
0 |
|
|
1 |
-2 |
1 |
|
|
0 |
0 |
0 |
Gain factor = 1/2 = 0.5
To calculate the second derivative in both the x-direction and the y-direction, f"=d2f/dxdy, formula 1 is needed. After the substitution of all 9 coordinates in the equation, and solving them, the results are:
|
(12) |
d2f / dxdy = a11 |
|
(13) |
a11 = (f1,1 + f-1,-1) - (f-1,1 + f1,-1) / 4 |
A 3x3 second derivative filter for both the x-direction and the y-direction will thus read:
|
-1 |
0 |
1 |
|
|
0 |
0 |
0 |
|
|
1 |
0 |
-1 |
Gain factor = 1/4 = 0.25
Calculation of matrix coefficients for 5x5 filters follows the same method as for 3x3 filters. Although 5x5 filters are a little bit more complicated, they will produce more accurate results.
Again a local coordinate system is used around the current center pixel as:
|
(-2,2) |
(-1,2) |
(0,2) |
(1,2) |
(2,2) |
|
|
(-2,1) |
(-1,1) |
(0,1) |
(1,1) |
(2,1) |
|
|
(-2,0) |
(-1,0) |
(0,0) |
(1,0) |
(2,0) |
|
|
(-2,-1) |
(-1,-1) |
(0,-1) |
(1,-1) |
(2,-1) |
|
|
(-2,-2) |
(-1,-2) |
(0,-2) |
(1,-2) |
(2,-2) |
Both x and y can have the values -2, -1, 0, 1, and 2.
The polynomial function fx and its derivatives are:
|
(14) |
fx = a0 + a1 x + a2 x2 + a3 x3 + a4 x4 |
|
(15) |
df/dx= f'x = a1 + 2a2 x + 3a3 x2 + 4a4 x3 |
|
(16) |
d2f/dx2 = f"x = 2a2 + 6a3 x + 12a4 x2 |
By substituting x in formulas 15 and 16 with 0, the previous equations 5 and 6 are obtained again:
|
(5) |
df/dx = f'0 = a1 |
|
(6) |
d2f/dx2 = f"0 = 2a2 |
By substituting x in formula 14 with values -2, -1, 0, 1, and 2; f-2, f-1, f0 , f1 and f2 are found:
|
(17) |
f-2 = a0 - 2a1 + 4a2 - 8a3 + 16a4 |
|
(18) |
f-1 = a0 - a1 + a2 - a3 + a4 |
|
(19) |
f0 = a0 |
|
(20) |
f1 = a0 + a1 + a2 + a3 + a4 |
|
(21) |
f2 = a0 + 2a1 + 4a2 + 8a3 + 16a4 |
With some restructuring, the following equations are obtained:
|
(22) |
f1 + f-1 = 2a0 + 2a2 + 2a4 |
|
(23) |
f1 - f-1 = 2a1 + 2a3 |
|
(24) |
f2 + f-2 = 2a0 + 8a2 + 32a4 |
|
(25) |
f2 - f-2 = 4a1 + 16a3 |
The matrix coefficients for a 1x5 filter which calculates the first derivative in x-direction are found by the elimination of a3: subtracting equation 23 eight times from equation 25. This results in:
|
(26) |
a1 = (f-2 - 8f-1 + 8f1 - f2) / 12 |
A 1x5 first derivative filter for the x-direction will thus read:
|
1 |
-8 |
0 |
8 |
-1 |
Gain factor = 1/12 = 0.0833333
This is exactly the DFDX filter.
The matrix coefficients for a 1x5 filter which calculates the second derivative in x-direction are found by the elimination of a4: subtracting equation 22 sixteen times from equation 24 and substituting f0 for a0. This results in:
|
(27) |
a2 = (-f-2 + 16f-1 - 30f0 + 16f1 - f2) / 24 |
A 1x5 second derivative filter for the x-direction will thus read:
|
-1 |
16 |
-30 |
16 |
-1 |
Gain factor = 1/24 = 0.0416667
This is exactly the D2FDX2 filter.
See also: