COMP90086 · Computer Vision · Workshop 3

Filtering

Two ways to look at the same operation:
sliding a small window over pixels · choosing which frequencies survive

Scan to open the interactive slides on your device hesamasad.github.io/week-3-filtering-workshop

Where we're going

PART 1 — SPACE

What a filter really is
Blur · sharpen · edges
Correlation vs convolution
Derivative of Gaussian
Borders & filter size

PART 2 — FREQUENCY

Images as sums of waves
Magnitude and phase
Reading a spectrum
Convolution theorem
Low / high / band-pass

The punchline, up front: blurring in Part 1 and low-pass filtering in Part 2 are the same thing, described in two languages.

Filtering in space

A small window, slid over every pixel.

A filter is a sliding weighted sum

Put the kernel on a patch → multiply matching cells → add them up → that's one output pixel.

out[y, x] = (k * img[y:y+3, x:x+3]).sum() # ... which is all filter2D does, for every (x, y)

The same idea, written down

\[ {\color{#7fd6a8} g(x,y)} \;=\; \sum_{j=-k}^{k}\; \sum_{i=-k}^{k}\; {\color{#f2a65a} h(i,j)} \;\cdot\; {\color{#6ea8fe} f(x+i,\; y+j)} \]

a \(( 2k{+}1) \times (2k{+}1)\) kernel, one output pixel per position

f input image h kernel / filter / mask g output image


kernel = np.ones((15, 15), np.float32) / 225     # 15x15 box blur, weights sum to 1
out    = cv2.filter2D(img, -1, kernel)           # -1 = keep the input's dtype

Weights that sum to 1 preserve brightness. Weights that sum to 0 respond to change, not to level — that's every edge filter.

One kernel, grayscale and colour

OpenCV applies the same kernel to each colour channel independently. Because grayscale conversion is linear, filter then convert and convert then filter agree.

Blur: box vs Gaussian

Gaussian is the default for a reason: no hard cut-off, rotationally symmetric, and separable — a 15×15 blur costs two 1-D passes, not 225 multiplies per pixel.

Sharpening is just adding back the detail

\( d = f - G_\sigma * f \)

\( f_{\text{sharp}} = f + \alpha\, d = (1+\alpha)f - \alpha\,(G_\sigma * f) \)

Which is why [[0,−1,0],[−1,5,−1],[0,−1,0]] works: with our Laplacian sign convention, it is identity − Laplacian folded into one kernel. Weights still sum to 1.

An edge is where brightness changes fast

Edge detection = differentiation. A filter like [−1, 0, 1] is just a finite-difference derivative.

Sobel: derivative in x, derivative in y

10−1 20−2 10−1

Sobel x

121 000 −1−2−1

Sobel y

Each one is a [−1, 0, 1] derivative in one direction, combined with a [1, 2, 1] blur in the other. Smoothing first is what stops it firing on noise.

\( \nabla f = (G_x, G_y), \quad \lVert \nabla f \rVert = \sqrt{G_x^2 + G_y^2}, \quad \theta = \operatorname{atan2}(G_y, G_x) \)

Cross-correlation vs convolution

\( (h \star f)(x,y) = \textstyle\sum_{i,j} h(i,j)\, f(x{+}i,\, y{+}j) \)

\( (h * f)(x,y) = \textstyle\sum_{i,j} h(i,j)\, f(x{-}i,\, y{-}j) \)

Convolution = correlation with the kernel flipped 180°. cv2.filter2D actually does correlation; scipy.signal.convolve2d does convolution. For symmetric kernels (box, Gaussian) it makes no difference — for Sobel it flips the sign.

Derivative of Gaussian: fold two filters into one

\[ \frac{\partial}{\partial x}\bigl(G_\sigma * f\bigr) \;=\; \Bigl(\frac{\partial G_\sigma}{\partial x}\Bigr) * f \]

Because convolution is associative, you can differentiate the kernel once, offline, instead of differentiating every image at run time.

What happens at the edge of the image?

The kernel hangs off the picture — so we invent pixels.

reflect is usually the safest default: no invented dark rim (constant), no smeared streaks (replicate), no wrap-around from the opposite side.

Does a bigger kernel do more?

Take the 3×3 Sobel and pad it with zeros. Same weights, bigger support.

Identical output, much slower — cost grows with the kernel area (k²). Padding adds nothing; what matters is where the non-zero weights are.

Part 1 in one table

Kernel	Weights sum to	Responds to	Effect
Box / Gaussian	1	average level	smooths, removes detail
Sharpen	1	level + local contrast	exaggerates detail
Sobel / [−1,0,1]	0	change in one direction	edges
Laplacian	0	change in every direction	edges, no orientation

Notice the pattern: sum = 1 keeps brightness, sum = 0 discards it. That sum is the filter's response at zero frequency — \( H(0,0) = \sum_{i,j} h(i,j) \) — which is exactly what Part 2 calls the DC term.

Filtering in frequency

Same operation, different alphabet.

Any signal is a sum of sine waves

\( f(t) \;=\; \sum_{k} A_k \sin\!\bigl(2\pi k t + \phi_k\bigr) \)

The Fourier transform just answers: how much of each wave, and shifted by how much? Amount = magnitude, shift = phase.

In 2-D, one wave = two dots

\( F(u,v) \;=\; \sum_{x=0}^{M-1}\sum_{y=0}^{N-1} f(x,y)\, e^{-2\pi i\left(\frac{ux}{M} + \frac{vy}{N}\right)} \)

Drag the sliders: faster wave → dots move outward, rotate the wave → dots rotate with it. Centre of the spectrum = lowest frequency.

What does the spectrum store?

\( F(u,v) = \underbrace{|F(u,v)|}_{\text{magnitude: how much}}\; e^{\,i\,\underbrace{\phi(u,v)}_{\text{phase: where}}} \)

In natural images, phase usually carries most recognisable structure: magnitude says how strongly each frequency is present, while phase says where its waves align to form edges, contours and objects.

Reading a spectrum

Distance = scale

Centre: broad, slow changes. Outside: fine, rapid changes.

Angle = direction of change

Energy lies perpendicular to lines in the image.

Brightness = strength

Brighter points mean more magnitude at that frequency.

Convolution in space = multiplication in frequency

\[ f * h \;\;\xrightarrow{\;\mathcal{F}\;}\;\; F \cdot H \qquad\text{and}\qquad f \cdot h \;\;\xrightarrow{\;\mathcal{F}\;}\;\; F * H \]

A DFT product gives circular convolution. To reproduce linear convolution, pad sufficiently, align the kernel origin, then crop using the same boundary convention. Beyond a size-dependent crossover, the frequency route can be cheaper.

A Gaussian stays a Gaussian — but inverts

\( \mathcal{F}\bigl\{ e^{-\|x\|^2 / 2\sigma^2} \bigr\} \;\propto\; e^{-2\pi^2 \sigma^2 \|u\|^2} \qquad \text{width} \;\propto\; 1/\sigma \)

Wide blur in space ⟷ narrow window in frequency. A big blur keeps only a small disc of low frequencies — so "blur" and "low-pass" are literally the same statement.

Filtering by choosing a region of the spectrum

\( H_{\text{low}}(u,v) = e^{-\frac{u^2+v^2}{2r^2}}, \qquad H_{\text{high}} = 1 - H_{\text{low}}, \qquad g = \mathcal{F}^{-1}\{ F \cdot H \} \)

Low-pass = keep the centre → blur. High-pass = throw the centre away → edges, no brightness. Band-pass = keep a ring → one scale of detail.

The two halves, side by side

In space	In frequency
convolve with a kernel	multiply the spectrum by a mask
Gaussian blur	keep the low-frequency centre
sharpen / Laplacian	boost the outer frequencies
Sobel derivative	weight ∝ frequency, along one axis
larger smoothing scale (e.g. Gaussian σ)	narrower passband
dense direct: \(O(N^2k^2)\)	FFT: \(O(PQ\log(PQ))\), including padding

You never have to choose a domain to be "right" in — pick whichever makes the question easy to answer.

What to carry out of this room

Four habits for Assignment 1 — and for everything after it.

Take-homes for the assignment

1 · THROWING PIXELS AWAY IS A FILTERING DECISION

A coarser grid can only carry frequencies up to its own limit. Anything above that does not vanish — it reappears somewhere else in the spectrum.

So the question to ask before resampling is always: what is the new limit, and what in my image lives above it?

2 · IF TWO ROUTES MUST AGREE, PROVE IT

You saw three ways to blur today. When implementations are supposed to be equivalent, one line settles it:

np.max(np.abs(a - b)) # not "they look the same"

A tiny non-zero number is float rounding. A large one is a bug in padding, centring, or border handling. And when there is no exact match to check against, compare to a reference you trust and report an error metric rather than an impression.

3 · COST IS A CLAIM YOU CAN MEASURE

For an \(N\times N\) image: \(N^2k^2\) for direct 2-D, \(N^2k\) for separable, and \(PQ\log(PQ)\) for the FFT, where \(P,Q\) include padding. Which wins depends on the sizes you are using.

Put all the curves on one set of axes and find where the ranking changes. The crossover is the interesting part: it is where a constant factor stops mattering and the exponent takes over.

4 · IF YOU'RE LOOPING OVER PIXELS, STOP

Per-pixel Python loops are slow, but worse, they usually mean the array formulation hasn't been found yet — and that formulation is normally the clearer one.

Slicing, broadcasting, and one call to a convolution routine replace almost every double for.

EMPHASISE (in this order): 1. Point 1 is the whole conceptual spine of A1 and the one students most often skip straight past. Do NOT give them a formula for sigma — make them ask the question themselves: "after keeping every k-th pixel, what is the highest frequency the new grid can represent, and what happens to everything above it?" The marks in that question are for the reasoning, not the number. If they ask you directly for the value, turn it back into the Nyquist question. 2. Point 2 is a research habit, not an assignment trick. Students routinely present two images side by side and assert they match. Make them internalise that a max-abs-difference is cheap and decisive. Also warn them what a NON-tiny difference usually means: kernel not centred, wrong padding, or forgetting the shift before the inverse transform. 3. For point 3, remind them a timing plot needs the x-axis varied over a sensible range, repeated runs, and the same image — otherwise the curves mean nothing. 4. Point 4: "no per-pixel loops" is an explicit marking criterion in this subject, and it is also how you should write numerical code generally. Useful specifics you can mention without giving anything away: - A frequency-sweep target (concentric rings whose frequency rises with radius) is the cleanest way to SEE aliasing, because the failure appears at a particular radius. If they only test on a normal photo they may not notice anything is wrong. - Timing: take the best of several repeated runs, not a single one, and keep the image fixed while only the kernel changes. Otherwise the plot measures their laptop, not the algorithms. - Any error metric needs something to be an error AGAINST. Make them say out loud what their reference is and why it is a fair one. - For real-valued images, rfft2/irfft2 store only half the spectrum (conjugate symmetry — the same symmetry that gives the two dots on the 2-D sine slide). Deliberately NOT on this slide: any specific sigma, any specific error threshold, and the order in which to blur and subsample. Those are the assignment.

Take-homes for the rest of computer vision

WHEN AN IMAGE LOOKS WRONG, LOOK AT ITS SPECTRUM

Moiré, banding, ringing, periodic sensor noise, JPEG blocking — each has a signature in the Fourier magnitude that is obvious there and invisible in the pixels.

A DISPLAY TRANSFORM IS NOT A DATA TRANSFORM

np.log(1 + |F|) exists so your eyes can see past the DC term. Never feed the logged version back into the maths — a habit worth keeping for every colourmap, normalisation and axis scale you ever choose.

THE BUGS LIVE AT THE BOUNDARY AND AT THE CENTRE

Border mode, odd vs even kernel size, and fftshift / ifftshift account for most results that are almost right. Check corners and check the DC term.

THE KERNELS BECAME LEARNED — THE PHYSICS DIDN'T CHANGE

A CNN learns the numbers in the little matrix, but stride and pooling are still downsampling, so aliasing is still a real failure mode; and phase still carries the structure, which is why it matters for generative models and image forensics.

The core fixed-kernel theory today was linear and shift-invariant, assuming compatible boundary handling. That is what lets us describe such systems by convolution and frequency-response multiplication. Several displayed operations — such as gradient magnitude, clipping and resampling — are not themselves LSI.

EMPHASISE: - The first two cards are the ones with the longest shelf life. The spectrum-as-diagnostic habit is what separates "the output looks odd" from "the output has a periodic artefact at this orientation and spacing, so it came from here". - Card 3 is where you will spend your consultation hours. Say out loud: an even-sized kernel has no centre pixel, so "same" output is shifted by half a pixel; and ifftshift is not optional just because the image "looks fine" — it usually looks fine and is wrong by half the image. - Card 4 is the bridge to the rest of the subject. If you have 30 seconds, mention Zhang (ICML 2019), "Making Convolutional Networks Shift-Invariant Again": blurring before strided downsampling inside a network — literally Question 2 of this assignment, applied to a CNN. It lands well because they have just done it by hand. - The linear + shift-invariant point is worth a beat of silence. Everything elegant today followed from those two words.

Your turn

worksheet03.ipynb — exercises

Exercises

1 · SEPARABILITY

Do a 2-D Gaussian blur as two 1-D passes. Time it against the 2-D version.

Hint: cv2.getGaussianKernel already gives you the 1-D kernel.

2 · KERNEL SIZE

Blur with 5×5 vs 15×15. What changed — and what did not?

Watch σ as well as size; size alone doesn't set the amount of blur.

3 · DELETE MAGNITUDE OR PHASE

Replace one of them with random values and invert. Which destroys the image?

Predict first, then run it.

4 · GAUSSIAN HIGH-PASS

Build the mask in the frequency domain.

You already have the low-pass mask — think about 1 − mask.

Exercise 5 — design a kernel

Find the smallest kernel whose response peaks at the centre of this 3×3 blob and is lower everywhere else.

The response counts how much of the kernel lands on the blob — full overlap (9) only at the centre, less at every shifted position. Smaller kernels tie: 1×1 gives 1 at all nine blob pixels, 1×3 gives 3 on three of them.

Cheat sheet


# --- space -----------------------------------------------------------
k    = cv2.getGaussianKernel(15, 5); k2 = np.outer(k, k)      # separable Gaussian
out  = cv2.filter2D(img, -1, k2, borderType=cv2.BORDER_REFLECT)   # correlation!
out  = signal.convolve2d(img, k2, boundary='symm', mode='same')   # true convolution

# --- frequency -------------------------------------------------------
F    = np.fft.fftshift(np.fft.fft2(img))       # DC term to the centre
mag, ph = np.abs(F), np.angle(F)
show = np.log(1 + np.abs(F))                   # log only for DISPLAY
img2 = np.real(np.fft.ifft2(np.fft.ifftshift(F * mask)))   # shift back before inverting
F    = np.fft.rfft2(img); img2 = np.fft.irfft2(F, s=img.shape)  # real input: half the spectrum

Two things that bite everyone: filter2D is correlation, not convolution; and you must ifftshift before ifft2.

Play with these afterwards

Image Kernels, explained visually — drag a kernel over a photo, live setosa.io/ev/image-kernels/
Karl Sims — Interactive FFT tutorial — build a signal from its frequencies karlsims.com/fft.html
An Interactive Guide to the Fourier Transform — the intuition, no integrals betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/
HIPR2, University of Edinburgh — short reference pages per operator homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
MIT Vision Book — Fourier Analysis — a rigorous computer-vision treatment visionbook.mit.edu/image_processing_fourier.html
CNN Explainer — where this goes next: learned kernels poloclub.github.io/cnn-explainer/

Next week these hand-designed kernels stop being hand-designed — a CNN learns the numbers in the little matrix.

End of workshop 3

Questions?

Press S for speaker notes · O for the slide overview · F for fullscreen