Lecture 7
Department of Intelligent Systems, University of Lahore
Lab 7 builds a feature-matching + shape-detection application from everything here.
Sobel/Laplacian (Lecture 4) give a gradient magnitude image — every pixel near an edge lights up, producing thick, noisy edge bands. An edge detector must turn that into a clean, one-pixel-wide, thresholded edge map. Canny (1986) is still the reference algorithm because it explicitly optimises three criteria:
1. Noise suppression: convolve with a Gaussian \(G_\sigma\) first — Canny is a gradient method, and gradients amplify noise.
2. Gradient computation: Sobel (or similar) gives \(g_x, g_y\), from which:
\[ M(x,y) = \sqrt{g_x^2 + g_y^2}, \qquad \theta(x,y) = \operatorname{atan2}(g_y, g_x) \]
The direction \(\theta\) is quantised to one of 4 discrete directions (0°, 45°, 90°, 135°) for the next step.
At every pixel, compare the gradient magnitude \(M\) against its two neighbours along the gradient direction \(\theta\) (i.e. perpendicular to the edge). Keep the pixel only if it is a local maximum in that direction; otherwise suppress it to 0.
A single threshold is fragile: too low → noise passes as edges; too high → weak-but-real edges break into gaps. Canny uses two thresholds \(T_{low} < T_{high}\):
edges = cv2.Canny(gray, threshold1=50, threshold2=150, apertureSize=3, L2gradient=True)Practitioner rule of thumb: start with \(T_{high}:T_{low} \approx 2\)–\(3 : 1\), and always tune on your own footage with a trackbar (Lab 6’s UI pattern) — there is no universal setting.
Given a noisy, broken edge map, how do we find the lines or circles hiding in it? The Hough transform reframes shape detection as voting: every edge pixel votes for every shape it could be part of, and peaks in the vote accumulator are the detected shapes.
Key idea: a line through image point \((x,y)\) in the usual \(y=mx+c\) form has an unbounded slope. Instead use the normal form:
\[ \rho = x\cos\theta + y\sin\theta \]
Every edge point \((x,y)\) traces a sinusoid in \((\rho,\theta)\) space; points that are collinear in the image produce sinusoids that all cross at one \((\rho,\theta)\) — that intersection is a peak in the accumulator, i.e. a detected line.
lines = cv2.HoughLinesP(edges, rho=1, theta=np.pi/180,
threshold=80, minLineLength=40, maxLineGap=10)
for x1, y1, x2, y2 in lines[:, 0]:
cv2.line(out, (x1, y1), (x2, y2), (0, 255, 0), 2)HoughLines) returns infinite lines \((\rho,\theta)\); Probabilistic Hough (HoughLinesP) returns finite segments and is faster — the practical default.threshold = minimum votes to accept a line; minLineLength/maxLineGap merge nearby broken segments.A circle needs 3 parameters — centre \((a,b)\) and radius \(r\): \((x-a)^2+(y-b)^2=r^2\). A brute-force 3D accumulator is expensive, so OpenCV’s HOUGH_GRADIENT uses the edge gradient direction to vote only along the likely radius direction from each edge pixel, then searches candidate radii — much faster.
circles = cv2.HoughCircles(gray, cv2.HOUGH_GRADIENT, dp=1.5, minDist=30,
param1=100, param2=40, minRadius=5, maxRadius=60)Common use: coin/pupil/bolt-hole counting on a fixed camera rig where circles are the dominant shape.
A contour is an ordered list of boundary points around a connected region in a binary mask — the natural output of thresholding + morphology (Lecture 6).
contours, hierarchy = cv2.findContours(mask, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)RETR_EXTERNAL, RETR_LIST, RETR_TREE, …) controls whether holes/nested contours are returned and how the parent–child hierarchy is built.CHAIN_APPROX_NONE stores every boundary pixel; CHAIN_APPROX_SIMPLE compresses straight segments to their endpoints — far fewer points, same shape.cv2.contourArea, cv2.arcLength, cv2.boundingRect, cv2.minAreaRect give geometric measurements directly (Lab 5, Lab 9).The Ramer–Douglas–Peucker algorithm simplifies a contour to a polygon with fewer vertices while staying within a tolerance \(\varepsilon\) of the original curve:
eps = 0.02 * cv2.arcLength(cnt, True)
approx = cv2.approxPolyDP(cnt, eps, True)
n_sides = len(approx) # 3=triangle, 4=quad, ... , circle-ish otherwiseThis is the classical way to tell “is this a rectangle, a triangle, or a blob?” from a contour — and the geometric core of the Lab 8 document-scanner homography (find the 4-corner quad, then warp).
Image moments summarise a shape’s mass distribution:
\[ m_{pq} = \sum_{x,y} x^p y^q\, I(x,y) \]
Hu moment invariants (7 values, Hu 1962) are non-linear combinations of \(\eta_{pq}\) up to 3rd order that are invariant to translation, scale, and rotation — a compact shape fingerprint.
M = cv2.moments(cnt)
hu = cv2.HuMoments(M).flatten()
score = cv2.matchShapes(cnt1, cnt2, cv2.CONTOURS_MATCH_I1, 0) # smaller = more similarEdges localise well in one direction but not along themselves. For matching two images of the same scene, we need points that are localised in both directions — corners and blobs.
A corner is a point where the image intensity changes sharply in two directions (an edge changes in only one). Harris (1988) formalises this with the structure tensor over a window \(w\):
\[ M = \sum_{w} \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix}, \qquad R = \det(M) - k\,(\operatorname{trace}(M))^2 \]
harris = cv2.cornerHarris(gray_f32, blockSize=2, ksize=3, k=0.04)
corners = harris > 0.01 * harris.max()Shi & Tomasi (1994) showed that a more direct and more stable corner score is simply the smaller eigenvalue of the same structure tensor:
\[ R_{ST} = \min(\lambda_1, \lambda_2) \]
goodFeaturesToTrack, the standard seed-point detector for KLT optical-flow tracking (Lecture 11).pts = cv2.goodFeaturesToTrack(gray, maxCorners=200, qualityLevel=0.01,
minDistance=8, blockSize=7)Harris/Shi–Tomasi detect corners at a single, fixed scale (the window size). A real corner can appear at many scales (a building corner vs. a whole building), and the “right” scale depends on the object — unknown in advance.
Scale space repeatedly Gaussian-blurs the image with increasing \(\sigma\), building a stack \(L(x,y,\sigma) = G_\sigma * I(x,y)\). Features are then detected as extrema across both space and scale, giving each keypoint a characteristic scale — this is what makes a detector scale-invariant.
The Laplacian-of-Gaussian (LoG) is the ideal blob detector (responds maximally when the blob size matches \(\sigma\)), but is expensive. The Difference of Gaussians is a cheap, close approximation:
\[ D(x,y,\sigma) = L(x,y,k\sigma) - L(x,y,\sigma) \;\approx\; (k-1)\,\sigma^2 \nabla^2 G * I \]
Harris/DoG are accurate but too slow for real-time embedded use. FAST (Rosten & Drummond, 2006) trades some accuracy for a huge speed-up:
fast = cv2.FastFeatureDetector_create(threshold=20, nonmaxSuppression=True)
kps = fast.detect(gray, None)FAST alone has no scale or orientation information — that is exactly the gap ORB fills by pairing FAST detection with an orientation estimate and the BRIEF descriptor (next lecture).
| Detector | Rotation-invariant | Scale-invariant | Speed | Typical use |
|---|---|---|---|---|
| Harris | Yes | No | Medium | Calibration targets, planar scenes |
| Shi–Tomasi | Yes | No | Medium | KLT tracking seed points |
| DoG (SIFT detector) | Yes | Yes | Slow | Wide-baseline matching, panoramas |
| FAST | No | No | Very fast | Real-time / embedded (paired with a descriptor) |
Repeatability is normally reported as the fraction of keypoints detected in image A that reappear (within a small pixel tolerance, after applying the known transform) in image B — the standard benchmark protocol is Mikolajczyk & Schmid (2005).
approxPolyDP’s \(\varepsilon\) should scale with contour perimeter (e.g. 0.02 * arcLength), not be a fixed pixel count, or it will misbehave across resolutions.Lab 7 — Features & Matching.
Intelligent Vision Systems; University of Lahore | Dr. Muhammad Kazim