Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 46 ยท Filtering and Edges

Convolution and Correlation

Learn how image kernels slide over pixels. Write correlation from scratch, see how it differs from convolution, and cover padding, stride and separable kernels.

Almost every classical filter (blur, sharpen, edge detection) and every layer of a convolutional neural network does the same basic thing: take a small grid of numbers called a kernel, slide it over the image, and at each position replace the pixel with a weighted sum of its neighbours. The kernel is the recipe, and changing its numbers turns the same machinery into a blur, a sharpener or an edge finder.

In this lesson you will write that sliding window yourself, learn the small but important difference between correlation and convolution, and then handle the practical questions that every real implementation must answer: what happens at the image border (padding), how large is the output (and what is stride), and how to make a big kernel cheap (separable kernels). At the end you will meet the library versions in scipy.signal and scipy.ndimage. You should know array slicing from Indexing and Slicing and the idea of an image as an array from Images as Arrays.

The sliding window

Take a 3x3 kernel. Place it so that it covers a 3x3 patch of the image, multiply the nine kernel values by the nine pixels under them, add the products, and write the sum to one pixel of the output. Move one pixel to the right and repeat. When you reach the end of the row, go down one row. That is the whole algorithm.

flowchart LR
    A["image patch<br/>3x3 pixels"] --> C["multiply element<br/>by element"]
    B["kernel<br/>3x3 weights"] --> C
    C --> D["sum the 9 products"]
    D --> E["one output pixel"]
    E --> F["slide window<br/>one step, repeat"]

Each output pixel is a weighted sum of a small patch. The kernel stays fixed while the window moves.

The first TryIt does this with two plain loops on a tiny image: a bright 3x3 square on a dark background. The kernel is a box blur, nine weights of 1/9, so every output pixel is the average of its patch. A second version replaces the loops with sliding_window_view, which creates all patches at once as a view without copying data.

Python Sliding a box blur over an image

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each output value is the mean of nine neighbours. The value 9.0 at position (1, 1) appears because that patch lies completely inside the bright square, while a corner patch that covers only one bright pixel gives 1.0. The edges of the square became a gentle ramp, which is exactly what blurring means.

Notice the size: a 6x6 image and a 3x3 kernel give a 4x4 output. The window never hangs over the border, so the result shrinks by kernel size - 1 in each direction. We will fix that with padding in a moment.

Correlation versus convolution

What we just computed is technically cross-correlation: the kernel is laid on the patch as it is. Convolution is the same operation with the kernel rotated by 180 degrees (flipped both vertically and horizontally) first. The two give identical results whenever the kernel is symmetric, like a box or Gaussian blur, and mirror-image results when it is not.

Why do both exist? In signal processing, convolution has nicer algebra: it is commutative and associative, and it matches how a system responds to an input. Deep-learning libraries compute correlation and still call it "convolution", which is harmless because the kernels are learned, so the flip is simply absorbed into the weights. For image filtering by hand, the difference only matters for asymmetric kernels such as Sobel.

A clean way to see the flip is the impulse test: feed in an image that is all zeros except for a single 1. The convolution of an impulse with a kernel gives the kernel back, as an image. The correlation gives the kernel rotated by 180 degrees.

Python The kernel flip, seen with an impulse

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The convolution prints the kernel 1 2 3 / 4 5 6 / 7 8 9 in the middle of the output; the correlation prints it as 9 8 7 / 6 5 4 / 3 2 1. Remember the impulse test whenever you wonder which direction a filter works in.

Note: In this course, "filtering with a kernel" means correlation unless a lesson says otherwise, because that is what the code does and what deep-learning libraries do. When a result depends on direction (like an edge filter), the lesson will show the kernel and the output so there is no doubt.

Padding: what happens at the border

At the edge of the image, part of the window hangs outside the picture. There are two ways to deal with it. The first is to accept a smaller output, called valid mode. The second is to pad the image with extra pixels so the output keeps the input size, called same mode. A third choice, full, lets the kernel overlap by even a single pixel, and so the output is larger than the input (H + kh - 1 rows).

What values should the padding hold? Several conventions are common:

Mode Padding rule Typical use
zeros (constant) fill with 0 the CNN default; darkens borders
edge (nearest) repeat the border pixel natural-looking blur at borders
reflect mirror the image at the border smooth filtering, avoids dark rims
wrap continue from the opposite side periodic textures, FFT-based filters
Python Padding modes and output sizes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the first and last numbers of each filtered row. With zero padding the first output is (0 + 1 + 2) / 3 = 1.0, pulled down by the invented zero. With nearest it is (1 + 1 + 2) / 3 = 1.33, because the edge value is repeated. With reflect it is also 1.33. With mirror the neighbour beyond the edge is the pixel one step inside, giving (2 + 1 + 2) / 3 = 1.67, and wrap borrows the value from the opposite end.

Warning: Mode names are not consistent between libraries. NumPy's np.pad(mode="reflect") mirrors without repeating the edge pixel, which SciPy calls mirror. NumPy's "symmetric" repeats the edge pixel, which SciPy calls reflect. When results look off by one pixel near the border, check the mode names.

Output size and stride

So far the window moved one pixel at a time. The stride is the step between window positions. A stride of 2 evaluates every second position in each direction and so produces an output about half as wide and half as tall. It is a cheap way to downsample, and CNN layers use it constantly. The output size follows one formula, for input size n, kernel size k, padding p on each side and stride s:

TEXT
output size = floor((n + 2p - k) / s) + 1
Python Stride and the output-size formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A 7-pixel row with a 3-pixel kernel, one pixel of padding on each side and stride 2 gives (7 + 2 - 3) // 2 + 1 = 4 outputs. Keep the formula handy; shape mistakes are the most common bug when you build convolutional networks later in the course.

Separable kernels

A 2D kernel is separable if it is the outer product of a column and a row. The Gaussian is the classic example. Instead of sliding a 5x5 kernel (25 multiplications per pixel), you can slide the 5-element column kernel down the image and then the 5-element row kernel across it (10 multiplications per pixel). The result is identical. For a kernel of width k, the cost drops from k * k to 2 * k multiplications per pixel, which matters a lot for large blurs.

flowchart LR
    A["5x5 kernel<br/>25 multiplies per pixel"] -->|"is separable"| B["column kernel 5x1<br/>5 multiplies"]
    B --> C["row kernel 1x5<br/>5 multiplies"]
    C --> D["same result,<br/>10 multiplies"]

A separable kernel is applied as two 1D passes.

Python Separable Gaussian and the Sobel kernel

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A kernel is separable exactly when its matrix rank is 1. The Gaussian and the Sobel kernel qualify (the Sobel kernel is a smoothing column [1, 2, 1] times a difference row [1, 0, -1]), while the Laplacian has rank 2 and cannot be split into a single pair of 1D passes. You will see why Sobel works so well in Gradients and Edge Detection.

Kernels at work, and the library versions

Different weights give different filters. Normalised weights that sum to 1 (box, Gaussian) preserve overall brightness; weights that sum to 0 (edge kernels) give zero on flat regions; the sharpen kernel [[0, -1, 0], [-1, 5, -1], [0, -1, 0]] sums to 1 and boosts differences from the neighbours. Applying a kernel to a soft step edge shows both the blur and the sharpening effect on one image row:

Python Blur and sharpen a soft edge

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sharpened row dips below 0 on the dark side and climbs above 100 on the bright side. These overshoots make an edge look crisper (a halo effect), but they leave the valid pixel range. Clip them before saving, and never let the arithmetic wrap around in uint8 (see Brightness, Contrast and Gamma).

In practice you rarely write the loop. SciPy offers two families:

  • scipy.signal.convolve2d and correlate2d follow the valid, same and full vocabulary and are fine for small arrays. For large kernels scipy.signal.fftconvolve is faster.
  • scipy.ndimage.correlate and ndimage.convolve keep the output the same size as the input and take a mode for the border ('reflect', 'nearest', 'constant', 'wrap', 'mirror'). correlate1d and convolve1d filter along one axis, which is how separable passes are done. Most image work uses the ndimage family.

Lessons that follow rely on these tools. Blurring and Denoising builds Gaussian and median filters, and the convolutional layer in The Convolutional Layer is this same sliding window with learned weights.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A 10x10 image is filtered with a 3x3 kernel in valid mode, with stride 1. What is the output size?

    Valid mode never lets the window hang over the border: 10 - 3 + 1 = 8 in each direction.
  2. 2. What is the difference between convolution and (cross-)correlation?

    The kernel is rotated 180 degrees in convolution. For symmetric kernels, such as a box or Gaussian, the two operations give identical results.
  3. 3. You pad a 28-pixel-wide row with 1 pixel on each side and use a 3-wide kernel with stride 2. How many output pixels do you get?

    floor((28 + 2 - 3) / 2) + 1 = floor(13.5) + 1 = 14.
  4. 4. Why is a separable 5x5 Gaussian cheaper than a general 5x5 kernel?

    The 2D kernel is the outer product of two 1D kernels, so filtering the columns and then the rows gives the same result with 2k instead of k*k multiplications per pixel.
  5. 5. Which padding mode makes a blur darken the image borders?

    Zero padding averages real pixels with invented zeros, so the border pixels drift toward black. Reflect and nearest reuse real pixel values.

Summary

  • A kernel is a small grid of weights. Sliding it over an image and summing the products at each position is correlation; convolution is the same with the kernel rotated by 180 degrees.
  • The impulse test (a single bright pixel) shows which one you are doing: convolution returns the kernel, correlation returns it flipped.
  • valid, same and full modes give output sizes n - k + 1, n and n + k - 1. Padding (zeros, edge, reflect, wrap) decides what the border pixels see; the names differ between NumPy and SciPy.
  • With padding p and stride s, the output size is floor((n + 2p - k) / s) + 1.
  • Separable kernels (rank 1, such as the Gaussian and Sobel) are applied as two 1D passes, which costs 2k instead of k*k multiplications.
  • Sharpening and edge kernels overshoot the pixel range, so clip the result. In practice use scipy.ndimage.correlate or scipy.signal.

Next up: put these kernels to work in Blurring and Denoising.