Filtering images with convolution
Slide a small kernel over an image to blur it, and compute the valid output size.
On this page
Nested loops and images as arrays.
- Slide a small kernel over an image to blur it, and compute the valid output size.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Many image operations replace each pixel by a weighted sum of the pixels around it. The weights form a small grid called a kernel or filter. Sliding the kernel over the image and computing that weighted sum at every position is filtering, usually called convolution. The same operation, with learned kernels, is the core of convolutional neural networks.
A true mathematical convolution flips the kernel before sliding it. Most image libraries and deep-learning frameworks skip the flip, which is technically cross-correlation. For symmetric kernels, such as blurs, the two are identical, so the name is used loosely. The program uses the unflipped form. With 'valid' filtering the kernel must lie entirely inside the image, so an h × w image and a kh × kw kernel give an output of (h − kh + 1) × (w − kw + 1). To keep the size, pad the border first, for example with zeros, copies of the edge pixels, or a mirror image.
A 3 × 3 box blur uses nine weights of 1/9, so each output is the average of the neighbourhood. In the example, the image has a sharp step from 0 to 90 between columns 1 and 2. Blurring turns it into a gradual ramp of 30, 60, 90. The identity kernel, with a single 1 in the middle, returns the original center pixels. Gaussian kernels give a smoother, more natural blur than a box. Applying a k × k kernel costs O(H·W·k²) operations, which is why separable kernels, which split into a row and a column filter, are valued.
Code example
def convolve(image, kernel):
kh, kw = len(kernel), len(kernel[0])
output = []
for r in range(len(image) - kh + 1):
row = []
for c in range(len(image[0]) - kw + 1):
row.append(sum(image[r + i][c + j] * kernel[i][j] for i in range(kh) for j in range(kw)))
output.append(row)
return output
image = [[0, 0, 90, 90, 90] for _ in range(5)]
box = [[1 / 9] * 3 for _ in range(3)]
identity = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
blurred = convolve(image, box)
print(len(blurred), len(blurred[0]))
print([round(value, 1) for value in blurred[0]])
print(convolve(image, identity)[0])3 3 [30.0, 60.0, 90.0] [0, 90, 90]
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
def convolve(image, kernel): kh, kw = len(kernel), len(kernel[0]) output = [] for r in range(len(image) - kh + 1): row = [] for c in range(len(image[0]) - kw + 1): row.append(sum(image[r + i][c + j] * kernel[i][j] for i in range(kh) for j in range(kw))) output.append(row) return output image = [[0, 0, 90, 90, 90] for _ in range(5)]box = [[1 / 9] * 3 for _ in range(3)]identity = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]blurred = convolve(image, box)print(len(blurred), len(blurred[0]))print([round(value, 1) for value in blurred[0]])print(convolve(image, identity)[0])Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The kernel must fit inside the image, so a 5-high image and a 3-high kernel allow 3 vertical positions. | — | — | |
| At each position, multiply the kernel with the covered pixels and add up the products. | — | — | |
| A 5 × 5 image filtered with a 3 × 3 kernel gives a 3 × 3 result: (5 − 3 + 1). | — | 3 3 | |
| The sharp 0 → 90 edge becomes a ramp: the averages are 30, 60, and 90. | — | 3 3 [30.0, 60.0, 90.0] | |
| The identity kernel copies the center pixel of each window: the original values from columns 1 to 3. | — | 3 3 [30.0, 60.0, 90.0] [0, 90, 90] |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
O(H·W·kh·kw) time for an H × W image. A separable kernel reduces the work to O(H·W·(kh + kw)).
- Valid filtering shrinks the image. Pad the borders if you need the original size, and choose the padding mode deliberately.
- Library 'convolution' is usually cross-correlation. Flip asymmetric kernels yourself if you need the strict definition.
- A kernel that does not sum to 1 changes overall brightness. Normalize blur kernels so their weights total 1.
Try it yourself
What size is the output for a 100 × 80 image and a 5 × 5 kernel with valid filtering?
Reveal answer and reasoning
(100 − 5 + 1) × (80 − 5 + 1) = 96 × 76.