Image filtering

To filter an image, each output pixel becomes a weighted sum of the pixels around it. Watch the 3 × 3 window below slide over a square of ones: the edges and corners drop, and a faint ring grows outside.

A weighted sum of neighbours

In Images as signals (28.1), “A frequency with a direction” wrote an image as $x[n_1,n_2]$: the brightness of the pixel in column $n_1$ (across) and row $n_2$ (down). An image is a signal with two indices. So what does filtering it mean?

Think of a rumour in a village laid out as a grid of houses. Each house hears something, but what it believes is the average of what it and its eight neighbours heard. One loud house gets toned down, and a quiet house next to it picks up a little.

That is image filtering. Each output pixel is a weighted sum of the pixels around it, and the same weights are used wherever you are in the image. The grid of weights is the kernel, $h[n_1,n_2]$. It plays the part the impulse response $h[n]$ played for a 1-D filter.

Let’s start with the simplest kernel, the 3 × 3 average: nine weights, each 1/9. The output at a pixel is the mean of that pixel and its eight neighbours.

My image is 12 × 12 pixels. It is 0 everywhere except a 6 × 6 square of 1s, in rows 3 to 8 and columns 3 to 8, counting from 0.

One question comes first: what does a window see at the border? Some of its nine pixels fall outside the image. On this page, a pixel beyond the border repeats the nearest edge pixel. This is called edge padding. Near the corner of my image, the outside pixels are copies of zeros.

The picture at the top of the page slides this window over my image.

Notice the corner of the square in the output. Four of the nine pixels under the window are 1, so the output is 4/9, or 0.444. Count the others the same way: along an edge six of the nine are inside, 0.667, and deep inside all nine are, 1.

Every output value is a whole number of ninths. The count of 1s is the number of the window’s rows inside the square times the number of its columns inside, each 0 to 3. So only 0, 0.111, 0.222, 0.333, 0.444, 0.667 and 1.000 occur.

The 2-D convolution sum

In “Flip and slide: a mechanical way to compute it” of Discrete convolution (5.2), the output was $y[n]=\sum_k x[k]\,h[n-k]$. Its next section showed that it does not matter which one you flip, so the same sum is $\sum_k h[k]\,x[n-k]$, with $k$ the distance from the output sample. An image needs one such distance across and one down:

Here $k_1$ runs across and $k_2$ down, over every place where the kernel has a weight. This is 2-D convolution, and I write it with the same star, $y=x*h$. For the 3 × 3 average, $h[k_1,k_2]=1/9$ for $k_1$ and $k_2$ from −1 to 1, and 0 elsewhere.

The minus signs in $x[n_1-k_1,n_2-k_2]$ flip the kernel, as in 5.2: across, and also down. That is a half turn of the grid. The average looks the same after a half turn, so for it the flip changes nothing. The window just slides, multiplies and adds, as in “Slide, multiply, add: no flip” of Correlation (24.3).

What the weights add up to

The 3 × 3 average is one kernel among many. Before trying others, let’s ask what any kernel does to a flat area, where every pixel has the same value $c$. Every product is a weight times $c$, so the output is $c$ times the sum of the weights.

That one number sorts kernels into two families. If the weights add up to 1, a flat area comes out unchanged, and only detail is reshaped. If they add up to 0, a flat area comes out 0, and only changes remain. It is like asking your neighbours’ opinions: averaging them keeps the general mood, while subtracting them leaves only the disagreements.

To compare kernels I need a richer image than a square. Here is my test card, 128 × 128 pixels, with values between 0 and 1, built from a formula:

• a gentle gradient across, $0.25+0.35\,n_1/127$, from 0.25 at column 0 to 0.60 at column 127;
• a disc of 0.9 with radius 24, centred at column 40, row 40;
• a square of 0.1 over columns 72 to 111 and rows 64 to 103;
• fine diagonal stripes, $0.5+0.3\cos\big(2\pi(n_1+n_2)/6\big)$, over columns 8 to 55 and rows 92 to 123.

The stripes are a grating of 28.1, with $1/6$ cycle per pixel across and $1/6$ down. They are the finest detail on the card.

I put four kernels through the card. Each is a small grid, with $k_1$ from left to right and $k_2$ from top to bottom.

Blur. The 3 × 3 average is a box blur: every weight the same. A smoother blur lets the weights fall off with distance. Mine is 5 × 5, built from the row 1, 4, 6, 4, 1, divided by 16. That row is four copies of 1, 1 convolved together, and it traces a bell close to the Gaussian of Random variables for signals (24.1), with a standard deviation of 1 pixel.

Each weight of the kernel is the row’s value for its column times the row’s value for its row, divided by $16\times16=256$. This is the Gaussian blur (also called the binomial blur):

The 25 weights add up to $256/256=1$.

Sharpen. The weight 5 in the centre and −1 at the four sides:

The weights add up to $5-4=1$. Written another way, the output is $x$ plus 4 times the difference between $x$ and the mean of its four sides. It adds back four times the difference from the neighbours’ average.

Sobel. In “A slope from samples” of Special FIR filters (19.4), the simplest slope was the difference of neighbouring samples. A slope across an image is a difference across. The Sobel kernel takes the difference between the pixels on either side, −1, 0, 1, and averages three rows of it with weights 1, 2, 1:

The same grid with rows and columns swapped measures the slope down. I call the two outputs $g_1$ (across) and $g_2$ (down). Together they are the gradient, the slope in both directions, and its size is

Each Sobel kernel’s weights add up to 0.

Laplacian. The weight −4 in the centre and 1 at the four sides, adding up to 0:

Read across, its middle row takes the pixel before, minus twice the pixel, plus the pixel after. That is the difference of two neighbouring differences. It measures how fast the slope changes, the bend or curvature, and its middle column does the same down. Compare it with sharpen: the sharpen kernel is the 1 in the centre minus the Laplacian. So sharpening subtracts the curvature.

Watch the flat areas as the clip cuts from kernel to kernel. Blur and sharpen keep them; Sobel and the Laplacian wipe them out and leave only the edges.

Notice what the blur does to the stripes. On the card they swing 0.3 each side of 0.5. After the blur they swing only 0.095, while the disc’s middle stays at 0.900 and the square’s at 0.100. The finest detail suffers most; flat areas do not change at all.

Sharpen does the opposite. Take row 84, across the square’s left edge: the card reads 0.446 just outside the edge and 0.100 just inside. Sharpened, the two pixels read 0.794 and −0.246. The bright side gets brighter and the dark side darker, so the edge stands out.

The two extremes of the sharpened card, −0.915 and 2.720, sit at the disc’s left edge. There, on row 40, a single pixel of the disc pokes out at column 16, with outside pixels above, below and to its left. Sharpen adds up the pixel’s differences from its four sides, and here three of them are large.

A slope that is not a bend

The difference between the two zero-sum kernels shows up on the gentle gradient. Take the 9 × 9 patch at rows 10 to 18, columns 100 to 108, far from any shape. There the card rises by $0.35/127=0.0028$ per pixel across.

On that patch, blur and sharpen change nothing (to 3 decimals): a steady slope has no detail to reshape. The Laplacian gives 0.000: a steady slope does not bend. But Sobel gives 0.022: a steady slope is a change. That is 8 times the step of 0.0028, since the kernel takes a difference across 2 pixels with weights adding up to 4.

The one place the flip matters

The Sobel kernel is the one kernel here that changes under a half turn: every weight changes sign. That matters for the sign of the result. Slide the grid as written across a step from 0 to 1, without the flip of 24.3, and the step’s right column meets the weights 1, 2, 1. The output is $1+2+1=4$.

Convolution flips the kernel first, so it gives −4. The size $\lvert\nabla x\rvert$ is 4 either way, and that size is what the instrument draws.

Median against salt and pepper

Some noise is not gentle. A camera with a few dead pixels, or a scanned page with dust on it, has scattered pixels that are fully dark or fully bright. This is called salt-and-pepper noise: specks of 0 and 1 sprinkled over the image.

I made some with seeded random draws (seed 282). For each pixel I drew a number between 0 and 1. Below 0.025 the pixel was set to 0, and above 0.975 it was set to 1. That hit 825 of the 16 384 pixels, 5.04 %: 395 pepper and 430 salt.

In “A median ignores spikes” of Simple smoothing filters (18.2), the median beat the average on glitches. The same works in two dimensions. The 3 × 3 median sorts the nine pixels under the window and keeps the middle one, the fifth. One or two specks sort to an end of the list and never reach the middle.

The median is not a weighted sum. No kernel computes it, and it is not linear, as 18.2 showed. It still slides a window over the image, with the same edge padding.

Compare the last two cards: the average smears each speck into a grey blotch, and the median drops it.

The mean-square error is the average, over all pixels, of the squared difference from the clean card. The average spreads each speck over a 3 × 3 block, at a ninth of its height above the card. The median cuts the error to less than a quarter of the average’s. Of the 825 specks, the median brings 786 back to within 0.01 of the clean card.

The median has a cost of its own, small but not zero. Put the clean card through it and the error is 0.0009. Most of that, 88 %, is in the fine stripes, where a window covers five neighbouring diagonals and its middle value is often not the centre’s. The rest is at the square’s four corners and the disc’s four outermost pixels: a corner pixel has only four of its nine on its own side, so the median rounds it off.

Two short passes instead of one big kernel

The 5 × 5 blur costs 25 multiplications for every output pixel. But each of its weights is a value of 1, 4, 6, 4, 1 for its column times a value for its row. So the blur can be done in two steps: blur every column with the 1-D kernel 1, 4, 6, 4, 1 (÷ 16), then blur every row of the result with the same kernel.

That costs 5 multiplications down and 5 across, 10 per pixel instead of 25. On the 16 384 pixels of the card, that is 163 840 multiplications instead of 409 600. A kernel that splits like this, into a column times a row, is separable.

Do the two ways agree? On the card they differ by at most $4.4\times10^{-16}$, rounding error, and the exact size depends on the order of the additions.

For a $K\times K$ kernel the saving is $2K$ multiplications instead of $K^2$, and it grows with the kernel. The Sobel kernel is separable too: the column 1, 2, 1 times the row −1, 0, 1. The Laplacian and sharpen are not.

Worked example

1. One output by hand. In the 12 × 12 image, take the output at row 2, column 4. In my notation that is $y[4,2]$, column first. The window covers rows 1 to 3 and columns 3 to 5. Only row 3’s three pixels are inside the square, so the output is $3/9=0.333$.

2. A corner by hand. At row 3, column 3, the window covers rows 2 to 4 and columns 2 to 4. The square starts at row 3 and column 3, so four pixels are inside: $4/9=0.444$.

3. Sobel on a step. Take a step from 0 to 1 across, at any row. Slid without the flip, the kernel’s left column sits on 0s and its right column on 1s, so the output is $1+2+1=4$. As a convolution it is −4. Either way $\lvert\nabla x\rvert=4$.

4. Sobel on the gradient. The card’s gradient rises 0.0028 per pixel. The difference across two pixels is twice that, and the weights 1, 2, 1 add up to 4. So $\lvert\nabla x\rvert=8\times0.35/127=0.022$.

5. The cost of a separable blur. A 5 × 5 kernel costs 25 multiplications per pixel. Split into two 1-D passes, it costs $5+5=10$.

Where you’ll meet this

Every photo editor has a Gaussian blur and a sharpen. The usual sharpen is “unsharp masking”: subtract a blurred copy to find the detail, then add some of that detail back, as $h_\text{sharp}$ did with the four sides.

In computer vision, Sobel’s gradients are an early step of edge and corner detectors, which pick out points to match between two photographs. The first layer of an image-recognition network is a set of kernels too. Their weights are learned from examples, and many of them come out looking like slope and stripe detectors.

Median filters clean up scanned documents and images with dead or stuck pixels. Software libraries give you all of this page: scipy.ndimage has convolve and median_filter, and its mode='nearest' is this page’s edge padding. Other libraries choose other borders. OpenCV, for one, reflects the image at its edge by default.

I left out colour, which repeats everything for each colour channel, and edge detectors that are not a single kernel, such as Canny’s. A blur is a low-pass filter, and The 2-D DFT (28.3) shows each of these kernels as a pattern of gains on the plane of spatial frequencies. For more, see Gonzalez and Woods, Digital Image Processing (4th ed., 2018), chapter 3, and Szeliski, Computer Vision (2nd ed., 2022), chapter 3.

Reference card