Canny & background subtraction
This page covers two classic low-level tools. The Canny detector finds thin, clean edges in one image. Background subtraction finds moving objects in video. After this page, you can do all five Canny steps by hand. You can also apply frame differencing and the running-average background model to numbers.
Canny edge detector: what it wants
An edge is a place where the intensity changes sharply. Simple gradient detectors give thick, noisy, broken edges. Canny's detector (a multi-stage algorithm) gives thin, connected edges and ignores noise. It has three objectives:
- Low error rate: the detector finds all real edges and gives no false responses.
- Good localisation: detected edge points are as close as possible to the true edge. The distance between a detected point and the true edge centre is minimal.
- Single response: one point for each true edge point, so the edges are thin. The number of local maxima around a true edge is minimal.
The detector finds strong and weak edges and reduces noise. It has five steps.
Step 1: noise reduction with a Gaussian filter
Differentiation amplifies noise. A single noisy pixel looks like a large gradient. To prevent this, smooth the image first with a Gaussian filter.
$(x,y)$ = offset from the kernel centre. $\sigma$ = standard deviation, which controls the blur. A bigger $\sigma$ gives more smoothing, but the edges become more blurred and less accurate. The factor $\tfrac1{2\pi\sigma^2}$ makes the weights sum to 1.
A common $3\times3$ kernel is below. The weights sum to 16, so the divisor is 16. $$\frac1{16}\begin{bmatrix}1&2&1\\2&4&2\\1&2&1\end{bmatrix}$$Step 2: gradient magnitude and direction
Apply the Sobel operators to the smoothed image $I$. $S_x$ responds to left-right intensity change (vertical edges). $S_y$ responds to up-down change (horizontal edges).
$G_x, G_y$ = horizontal and vertical gradient images. $M$ = gradient magnitude (edge strength). $\theta$ = gradient direction, which is perpendicular to the edge. In practice, use atan2 to get the full range $-180^\circ$ to $180^\circ$.
Worked example (extra). The patch is a dark-to-bright vertical step. The centre pixel is highlighted. Put the mask directly over the patch, then multiply and add. True convolution flips the kernel. This changes only the sign of $G$, not $M$.
| 10 | 10 | 50 |
| 10 | 10 | 50 |
| 10 | 10 | 50 |
$G_x = (-10+50) + 2(-10+50) + (-10+50) = 40+80+40 = 160$.
$G_y = (-10-20-50) + 0 + (10+20+50) = -80+80 = 0$.
$M=\sqrt{160^2+0^2}=160$, $\theta=\tan^{-1}(0/160)=0^\circ$. The gradient points left to right, so the edge is vertical.
Second patch with $G_x=30$, $G_y=40$: $M=\sqrt{900+1600}=50$, $\theta=\tan^{-1}(40/30)=53.13^\circ$.
Step 3: non-maximum suppression (NMS)
The Sobel output is a thick ridge, several pixels wide across the edge. NMS thins it to one pixel. Keep a pixel only if it is the local maximum along the gradient direction. Otherwise, set it to 0.
Think of the edge as a mountain ridge seen from above. Walk across the ridge (along the gradient direction). Keep only the highest point and set the points on both sides to 0.
For a target pixel $P(x,y)$, compare its gradient magnitude with the two immediate neighbours along the gradient direction. If the magnitude is greater than or equal to both, keep the pixel. If not, suppress it (set it to 0).
Discretising the direction
$\theta$ is continuous ($-180^\circ$ to $180^\circ$), but pixels are on a grid. So round $\theta$ into one of four sectors, which represent the 8-neighbour directions. In the image coordinates, $x$ is the row and $y$ is the column. The neighbours are written $P(x\pm1, y\pm1)$, as in the slides.
| Angle range $\theta$ | Rounded direction | Neighbours to compare with $P(x,y)$ |
|---|---|---|
| $[-22.5^\circ, 22.5^\circ]$ or $[157.5^\circ,180^\circ]$ or $[-180^\circ,-157.5^\circ]$ | $0^\circ$ (horizontal) | Left $P(x,y-1)$ and right $P(x,y+1)$ |
| $[22.5^\circ, 67.5^\circ]$ or $[-157.5^\circ,-112.5^\circ]$ | $45^\circ$ (diagonal) | Top-right $P(x-1,y+1)$ and bottom-left $P(x+1,y-1)$ |
| $[67.5^\circ, 112.5^\circ]$ or $[-112.5^\circ,-67.5^\circ]$ | $90^\circ$ (vertical) | Top $P(x-1,y)$ and bottom $P(x+1,y)$ |
| $[112.5^\circ, 157.5^\circ]$ or $[-67.5^\circ,-22.5^\circ]$ | $135^\circ$ (anti-diagonal) | Top-left $P(x-1,y-1)$ and bottom-right $P(x+1,y+1)$ |
This is the $3\times3$ neighbourhood around $P(x,y)$:
| P(x-1,y-1) | P(x-1,y) | P(x-1,y+1) |
| P(x,y-1) | P(x,y) | P(x,y+1) |
| P(x+1,y-1) | P(x+1,y) | P(x+1,y+1) |
$G(x,y)$ = gradient magnitude at $P$. $N_1, N_2$ = the two neighbours from the table for the rounded direction. $M$ = output after NMS.
Worked example 1 (row, $\theta=0^\circ$). These are gradient magnitudes along a row. All have $\theta=0^\circ$, so compare left and right:
| 20 | 45 | 80 | 60 | 25 |
For 20, the left neighbour is outside and the right neighbour is 45. $20\ge45$ fails, so 20 is suppressed. For 45, $45\ge20$ but $45\ge80$ fails, so 45 is suppressed. For 80, $\ge45$ and $\ge60$, so 80 is kept. For 60, $60\ge80$ fails, so 60 is suppressed. For 25, the test against 60 fails, so 25 is suppressed. The result is 0 0 80 0 0, a one-pixel-wide edge.
Worked example 2 (3x3, diagonal). These are gradient magnitudes. The centre pixel has $\theta=50^\circ$:
| 20 | 30 | 70 |
| 25 | 60 | 40 |
| 55 | 35 | 10 |
$50^\circ$ is in $[22.5^\circ,67.5^\circ]$, so the rounded direction is $45^\circ$. The neighbours are top-right $=70$ and bottom-left $=55$. $60\ge70$ fails, so the centre is suppressed (0). If $\theta$ were $90^\circ$, the neighbours would be top $=30$ and bottom $=35$. Then $60\ge30$ and $60\ge35$, so the centre would be kept.
Step 4: double thresholding
After NMS, some pixels are still noise or faint texture. Canny uses two thresholds, not one: a high threshold $T_H$ and a low threshold $T_L$.
$M$ = gradient magnitude after NMS. Strong edges are certainly real. Weak edges are "maybe" edges. Non-edges are set to 0. Canny gives a rule of thumb: $T_H : T_L$ is between 2:1 and 3:1. In OpenCV, use cv2.Canny(img, T_L, T_H).
Step 5: edge tracking by hysteresis
This step decides what happens to the weak pixels. If a weak pixel is connected (8-neighbour) to a strong pixel, keep it as an edge. If it is isolated, suppress it (set it to 0). The connections propagate. A weak pixel connected to a kept weak pixel is also kept.
Key advantage: hysteresis prevents noisy, fragmented edges. Weak edges stay only if they belong to a continuous structure that contains a strong pixel. A high threshold alone breaks edges. A low threshold alone lets in noise. The pair of thresholds is better than either one.
Worked example (steps 4 and 5 together). $T_H = 80$, $T_L = 40$. Magnitudes after NMS ($5\times5$):
| 90 | 0 | 0 | 0 | 0 |
| 0 | 60 | 0 | 0 | 50 |
| 0 | 0 | 45 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 30 | 0 | 0 | 0 | 0 |
Classify: 90 is strong ($\gt80$). 60, 45 and 50 are weak ($40$ to $80$). 30 is below $T_L$, so discard it.
Hysteresis (8-connectivity): Weak (1,1) touches strong (0,0), so keep it. Weak (2,2) touches (1,1), which is now kept, so keep it (chain propagation). Weak (1,4) has no strong or kept neighbour, so remove it. This is the final edge map:
| 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
The slides use strict inequalities. Real code usually treats $M\ge T_H$ as strong and $M\ge T_L$ as candidate. If an exam value is equal to a threshold, state your convention.
Typical questions: List the Canny steps in order. What is NMS and why is it used? What is the role of the two thresholds? What does hysteresis do? What are Canny's three criteria? Also be ready to give the Sobel masks and the $M$ and $\theta$ formulas.
Background subtraction
Background subtraction finds moving objects in a video. It separates the foreground (moving objects) from the background (static scene). Uses: video surveillance, traffic monitoring, human activity recognition, object tracking, crowd analysis, industrial automation.
Basic idea
The method has two assumptions. The background stays almost constant. Moving objects change the pixel intensities. So compare each new frame with a background model, and mark the pixels that differ by a large amount.
$I_t(x,y)$ = current frame at time $t$. $B(x,y)$ = background image. $F(x,y)$ = difference image. A large $F$ probably means foreground.
Algorithm
- Get the background image (for example, a frame with no moving objects).
- Capture the current frame.
- Compute the difference $F=\lvert I_t-B\rvert$.
- Threshold $F$ (for example, $F\gt T\to 255$, else 0) to get a binary foreground mask.
- Do morphological operations (erosion, dilation, opening, closing) to remove noise. The result is a cleaner foreground mask.
Worked example (extra). The $3\times3$ background $B$ is all 50. The current frame $I_t$ has an object that enters. The threshold is $T=30$.
| 50 | 50 | 50 |
| 50 | 50 | 50 |
| 50 | 50 | 50 |
| 50 | 52 | 50 |
| 50 | 120 | 130 |
| 50 | 118 | 50 |
Difference $F=\lvert I_t-B\rvert$:
| 0 | 2 | 0 |
| 0 | 70 | 80 |
| 0 | 68 | 0 |
Thresholding at 30 gives the mask. The threshold rejects the "2" because it is camera noise:
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 1 | 0 |
Adaptive background model
In real video, the background changes. Causes are lighting variations, shadows, rain and waving trees. A fixed background image becomes wrong after a short time. So update the background continuously.
$B_t$ = new background. $B_{t-1}$ = previous background. $I_t$ = current frame. $\alpha\in(0,1)$ = learning rate. A small $\alpha$ (for example 0.01) forgets slowly. A large $\alpha$ adapts quickly. The formula is a per-pixel exponential moving average.
Types of background subtraction
1. Frame differencing
This method uses the previous frame as the background: $D=\lvert I_t-I_{t-1}\rvert$. Advantage: it is very simple and fast. Disadvantage: it misses slow-moving objects, because there is little change between consecutive frames. A uniformly coloured moving object shows only at its leading and trailing edges (extra textbook fact).
Worked example. One row of pixels is shown over two frames, with $T=25$. A bright object (value 200) moves right on a background of 40.
| $I_1$ | 40 | 200 | 40 | 40 |
| $I_2$ | 40 | 40 | 200 | 40 |
$D=\lvert I_2-I_1\rvert = (0, 160, 160, 0)$. Thresholding at 25 gives the mask 0 1 1 0. The old position and the new position of the object both show. Now say the object moves only a little between frames (for example, 200 to 190 at the same pixel). Then $D=10\lt25$ and the method misses it. This is the "slow-moving objects" failure.
2. Running average model
This method updates the background continuously with $B_t=\alpha I_t+(1-\alpha)B_{t-1}$. Advantage: it adapts to lighting changes. Disadvantage: the adaptation is slow. A stopped object slowly becomes part of the background. Moving objects leave a faint smear in the average.
Worked example. $\alpha=0.1$ and the background pixel is $B_0=100$. A car parks, and the pixel stays at $I=140$ in every next frame. The foreground test is $\lvert I-B\rvert \gt 30$, with the background before the update.
Frame 1: $\lvert140-100\rvert=40\gt30$, foreground. Update $B_1=0.1(140)+0.9(100)=104$.
Frame 2: $\lvert140-104\rvert=36\gt30$, foreground. $B_2=0.1(140)+0.9(104)=107.6$.
Frame 3: $\lvert140-107.6\rvert=32.4\gt30$, foreground. $B_3=0.1(140)+0.9(107.6)=110.84$.
Frame 4: $\lvert140-110.84\rvert=29.16\lt30$, now background. The parked car is absorbed.
The general form is $B_n = 140 - 40(0.9)^n$. The car is absorbed when $40(0.9)^n \le 30$, that is $n\ge 2.73$, so after 3 updates. A larger $\alpha$ absorbs the car sooner. A smaller $\alpha$ absorbs it later, but it also adapts more slowly to real lighting changes.
Practice. $\alpha=0.5$, $B_{t-1}=80$, $I_t=120$. $B_t=0.5(120)+0.5(80)=100$.
3. Gaussian mixture model (GMM)
This method models each pixel with several Gaussian distributions, not one value. A pixel that matches one of the dominant Gaussians is background. A pixel that does not match is foreground. It is good for dynamic backgrounds and outdoor scenes, for example water waves and moving leaves. In these scenes, the pixel changes between a few values, and each value has its own Gaussian.
4. K-nearest neighbour (KNN) background model
This method stores the recent history of each pixel. It compares the current value with the nearest stored neighbours to decide foreground or background. Advantages: it handles dynamic scenes and is robust to noise.
| Method | Background model | Pros | Cons / suited for |
|---|---|---|---|
| Frame differencing | Previous frame $I_{t-1}$ | Very simple, fast | Misses slow-moving objects |
| Running average | $B_t=\alpha I_t+(1-\alpha)B_{t-1}$ | Adapts to lighting changes | Slow adaptation |
| GMM | Several Gaussians per pixel | Handles multimodal/dynamic backgrounds | Outdoor scenes, waves, leaves |
| KNN | Recent pixel history, nearest neighbours | Handles dynamic scenes, noise-robust | Needs to store history |
Do not confuse the three update ideas. Static background subtraction uses a fixed $B$ ($F=\lvert I_t-B\rvert$). Frame differencing uses $I_{t-1}$ as the background. The running average blends the current frame into $B$ with weight $\alpha$.
Quick self-test
1. State Canny's three design criteria.
Low error rate (find all real edges and no false ones). Good localisation (detected edges are close to the true edge). Single response (one point for each edge, so the edges are thin).
2. List the five Canny steps in order and say what each is for.
(1) Gaussian smoothing reduces noise. (2) The Sobel gradient gives the magnitude $M$ and direction $\theta$. (3) Non-maximum suppression thins edges to 1 pixel. (4) Double thresholding classifies pixels as strong, weak or non-edge. (5) Hysteresis keeps weak pixels only if they connect to strong ones.
3. For a patch with $G_x = 30$ and $G_y=-30$ find $M$, $\theta$, the rounded direction and the NMS neighbours.
$M=\sqrt{900+900}=42.4$. $\theta=\tan^{-1}(-30/30)=-45^\circ$, which is in $[-67.5^\circ,-22.5^\circ]$, so the rounded direction is $135^\circ$. Compare with top-left $P(x-1,y-1)$ and bottom-right $P(x+1,y+1)$.
4. Magnitudes along the gradient direction are 30, 70, 90, 85, 40. Apply NMS.
Only 90 is $\ge$ both neighbours (70 and 85). The output is 0, 0, 90, 0, 0. 70 and 85 lose to 90. The end values lose to their neighbours.
5. Why use two thresholds instead of one? What does hysteresis do?
One high threshold breaks real edges into fragments. One low threshold lets in noise. With two thresholds, strong pixels are sure edges. Weak pixels are kept only if they connect to a strong pixel, directly or through other kept weak pixels. The result is continuous edges without isolated noise.
6. $T_H=100$, $T_L=50$. NMS output has a chain 120 – 70 – 60 – 30 (8-connected in a line) and a separate isolated 75. Which pixels survive?
120 is strong. 70 touches 120, so it is kept. 60 touches the kept 70, so it is kept. 30 is below $T_L$, so it is discarded. The isolated 75 is weak and has no strong connection, so it is removed. The surviving pixels are 120, 70 and 60.
7. Describe the background subtraction algorithm and give the formula.
Get the background. Capture the current frame. Compute $F=\lvert I_t-B\rvert$. Threshold the difference to a binary mask. Clean the mask with morphology (opening and closing) to get a clean foreground mask.
8. Running average with $\alpha=0.2$, $B_{t-1}=50$, $I_t=100$, then next $I_{t+1}=100$. Find $B_t$ and $B_{t+1}$.
$B_t=0.2(100)+0.8(50)=60$. $B_{t+1}=0.2(100)+0.8(60)=68$.
9. Compare frame differencing, running average, GMM and KNN. When is GMM preferred?
See the comparison table. Frame differencing is fast but misses slow objects. The running average adapts to lighting, but slowly. GMM and KNN model dynamic backgrounds. Prefer GMM for dynamic outdoor scenes, such as waving leaves or water. In these scenes, one pixel can have several correct background values.
10. Frame differencing with threshold 20: $I_{t-1}=(60,60,60,60)$, $I_t=(60,90,75,62)$. Give the mask.
$D=(0,30,15,2)$. Mask: 0 1 0 0.
- Canny goals: low error rate, good localisation, single response.
- Steps: Gaussian blur, Sobel $G_x,G_y$ then $M=\sqrt{G_x^2+G_y^2}$ and $\theta=\tan^{-1}(G_y/G_x)$, NMS, double threshold, hysteresis.
- NMS: round $\theta$ to $0^\circ/45^\circ/90^\circ/135^\circ$; keep the pixel only if $\ge$ both neighbours along that direction, else 0. Gives one-pixel-wide edges.
- Double threshold: $M\gt T_H$ strong, $T_L\lt M\lt T_H$ weak, $M\lt T_L$ discarded. Hysteresis keeps weak pixels connected to strong ones, removes isolated ones.
- Background subtraction separates the moving foreground from a static background: $F=\lvert I_t-B\rvert$, threshold, then morphology to clean the mask.
- Adaptive background: $B_t=\alpha I_t+(1-\alpha)B_{t-1}$ for lighting changes, shadows, rain, waving trees.
- Types: frame differencing (simple, misses slow objects), running average (adapts, slow), GMM (dynamic outdoor backgrounds), KNN (dynamic scenes, noise-robust).