AI for Computer Vision (AD-701) Unit 2 Notes

How unit 2 is examined

This unit covers interest points, edges, lines, and the segmentation family; every past question (all 7 marks, Dec 2024) is an "explain" on edges, active contours, mean shift, normalized cuts or energy-based methods.

Points and patches

Not asked since 2022

Definition. Interest points (keypoints) are locations such as corners whose local image patch changes strongly when shifted in any direction, so they can be found again in another image and matched.

Key points.

A flat region shows no change under a shift, an edge changes only across it, and a corner changes in every direction, so corners make the best keypoints.
The Harris detector uses the structure matrix $M=\sum w(x,y)\begin{bmatrix}I_x^2 & I_xI_y\\ I_xI_y & I_y^2\end{bmatrix}$ over a window.
The corner response is $R=\det M-k\,(\operatorname{trace} M)^2$ with $k\approx0.04$-$0.06$; a large positive $R$ means a corner, a negative $R$ an edge, and a small $|R|$ a flat area.
After detection, a descriptor of the patch (for example SIFT or a normalised pixel patch) is compared between images to match points.

Harris corners are points where both eigenvalues of the structure matrix M are large.

Edges

Definition. An edge is a boundary where image intensity changes sharply (an intensity discontinuity), found by neighbourhood operators that estimate the gradient.

Formula. Gradient $\nabla I=(G_x,G_y)$, magnitude $|\nabla I|=\sqrt{G_x^2+G_y^2}$, direction $\theta=\tan^{-1}(G_y/G_x)$; Laplacian $\nabla^2 I=\partial^2 I/\partial x^2+\partial^2 I/\partial y^2$.

Key points.

A neighbourhood operator slides a small mask over the image and replaces each pixel by the weighted sum of its neighbours (convolution).
Sobel uses rows $[-1,0,1],[-2,0,2],[-1,0,1]$ for $G_x$; its transpose gives $G_y$; the centre weight of 2 gives smoothing.
Prewitt is the same with equal weights $[-1,0,1]$ in every row, and Roberts uses two $2\times2$ diagonal masks $[1,0;0,-1]$ and $[0,1;-1,0]$.
The Laplacian mask $[0,1,0;1,-4,1;0,1,0]$ is a second-derivative operator whose zero crossings mark edges, but it is very noise-sensitive.
Steps: smooth with a Gaussian to remove noise, compute gradient magnitude and direction, apply non-maximum suppression to thin edges to one pixel, then threshold (hysteresis in Canny).

Example. Patch rows all $[10,10,50]$: Sobel $G_x=(50\cdot4)-(10\cdot4)=160$, $G_y=0$, so $|\nabla I|=160$, a strong vertical edge; the Laplacian gives $80-40=40$.

Answer frame. Open with the definition of an edge; draw the Sobel masks and the small worked patch; develop the points in order 1, 2-4, 5; close with the Canny-style pipeline.

Asked: [7 marks] (Dec 2024) Illustrate the process of edge detection using neighborhood operators.

Lines

Definition. Line detection finds straight lines from edge points, most commonly with the Hough transform.

Key points.

In the Hough transform each edge point $(x,y)$ votes for all lines through it in a parameter space using $\rho=x\cos\theta+y\sin\theta$.
Points on the same line vote for the same $(\rho,\theta)$ cell, so peaks in the accumulator are lines.
It tolerates gaps and noise, but the cost grows with the resolution of the accumulator.
Linking edges into chains (contours) is the alternative when curves rather than straight lines are wanted.

In Hough voting, each edge point votes for every $(\rho,\theta)$ line through it and the accumulator peaks are the lines.

Segmentation

Definition. Image segmentation partitions an image into regions of similar pixels (intensity, colour, texture) that correspond to objects or parts.

Key points.

Thresholding splits pixels by intensity, $g(x,y)=1$ if $f(x,y)>T$, and Otsu's method picks $T$ by maximising between-class variance.
Region growing starts from seed pixels and adds neighbours that satisfy a similarity rule.
Clustering methods such as k-means group pixels by feature vectors.
Graph-based and contour-based methods (later in this unit) handle cases where simple thresholds fail.

Segmentation divides an image into homogeneous regions that correspond to meaningful objects.

Active contours

Definition. An active contour (snake) is a deformable curve $v(s)=(x(s),y(s))$ that moves to minimise an energy so that it settles on an object boundary.

Formula. $E_{snake}=\int_0^1\left[E_{int}(v(s))+E_{ext}(v(s))\right]ds$, with $E_{int}=\tfrac12(\alpha|v'|^2+\beta|v''|^2)$ and $E_{ext}=-|\nabla I|^2$.

Key points.

The internal energy keeps the curve smooth: $\alpha$ controls stretching (elasticity) and $\beta$ controls bending (rigidity).
The external energy pulls the curve towards image features such as edges, so it is low on strong gradients.
The user initialises a curve near the object, and iterative minimisation moves it until the total energy is a local minimum on the boundary.
Snakes are used in medical image segmentation (organs, cells) and in tracking objects over video frames, but they need a good initial curve and can get stuck in local minima.

Answer frame. Open with the snake definition; write the energy equation; explain internal versus external force; describe evolution from the initial curve to the boundary; close with medical and tracking uses.

Asked: [7 marks] (Dec 2024) Explain how active contours are used in image segmentation.

Split and merge

Definition. Split and merge is a region-based method that recursively splits a non-uniform region into four quadrants and then merges adjacent similar regions.

Key points.

The image is first the root of a quadtree; any region failing a homogeneity test (for example variance above a limit) is split into four.
Splitting continues until every block is homogeneous.
Adjacent blocks that together satisfy the homogeneity test are then merged to remove artificial block boundaries.

Split and merge divides by a quadtree until regions are uniform and then merges similar neighbours.

Mean shift and mode finding

Definition. Mean shift is a non-parametric, iterative mode-seeking algorithm that moves each point uphill to the nearest maximum (mode) of the estimated data density.

Formula. $m(x)=\dfrac{\sum_i K(x_i-x)\,x_i}{\sum_i K(x_i-x)}$, and the point is updated $x\leftarrow m(x)$ until the shift $m(x)-x$ is near zero.

Key points.

The density is estimated by a kernel (Gaussian or flat) of bandwidth $h$ placed on each data point (kernel density estimation).
Each iteration moves the window centre to the kernel-weighted mean of the points inside it, which is a step along the density gradient.
Points that converge to the same mode form one cluster, so the number of clusters is not fixed in advance, unlike k-means.
Used in segmentation (clustering pixels in colour plus position space), object tracking (CamShift) and general clustering.
Its main parameter is the bandwidth: too small gives many clusters and too large merges them.

Answer frame. Open with mean shift as mode seeking; write the shift formula; show the window moving to the density peak; list applications; close with the advantage of no preset cluster count.

Asked: [7 marks] (Dec 2024) What is the mean shift algorithm and how is it applied in computer vision?

Normalized cuts

Definition. Normalized cut is a graph-based segmentation method that treats pixels as nodes and splits the graph into two groups by minimising a cut cost normalised by each group's total connection to the whole graph.

Formula. $Ncut(A,B)=\dfrac{cut(A,B)}{assoc(A,V)}+\dfrac{cut(A,B)}{assoc(B,V)}$, where $cut(A,B)=\sum_{u\in A,v\in B}w(u,v)$ and $assoc(A,V)=\sum_{u\in A,v\in V}w(u,v)$.

Key points.

Each edge weight $w$ measures the similarity of two pixels (intensity, colour, distance).
Plain minimum cut prefers to cut off tiny isolated groups because their cut value is small; normalising by association removes this bias.
Minimising Ncut exactly is NP-hard, so it is solved approximately using the eigenvectors of the generalised problem $(D-W)y=\lambda Dy$.
The second-smallest eigenvector splits the graph in two, and the process repeats to get more segments.
It gives balanced, perceptually meaningful groups and is used for perceptual grouping and image segmentation.

Answer frame. Open with the graph view of an image; give the Ncut formula; explain why min-cut fails; state the eigenvector solution; close with the advantages.

Asked: [7 marks] (Dec 2024) Explain the concept of normalized cuts and its advantages.

Graph cuts and energy-based methods

Definition. Energy-based methods define an energy function of a labelling or curve, low for good solutions, and find the answer by minimising it; graph cuts minimise such energies exactly using min-cut/max-flow.

Formula. $E(f)=\sum_p D_p(f_p)+\lambda\sum_{(p,q)}V(f_p,f_q)$, a data term plus a smoothness term (Markov random field energy).

Key points.

The data term $D_p$ measures how well label $f_p$ fits pixel $p$, and the smoothness term $V$ penalises neighbouring pixels with different labels.
In a graph cut, pixels are nodes linked to source and sink terminals, and the minimum cut gives the lowest-energy foreground/background labelling.
Energy ideas appear across feature detection: snake energy for boundaries, MRF energy for labelling, and the Harris response for corners.
Optimising an energy locates corners, edges and blobs while the smoothness or regularising term gives robustness to noise and illumination change.

Answer frame. Open with the energy functional idea; give the data-plus-smoothness formula; list snake, MRF and Harris examples; explain the min-cut optimisation; close with robustness.

Asked: [7 marks] (Dec 2024) How do energy-based methods contribute to feature detection?

Last-minute revision

Harris response $R=\det M-k(\operatorname{trace}M)^2$; large positive means corner.
Sobel $G_x$ mask is $[-1,0,1;-2,0,2;-1,0,1]$; magnitude $\sqrt{G_x^2+G_y^2}$.
Edge pipeline: smooth, gradient, non-maximum suppression, threshold.
Hough line: $\rho=x\cos\theta+y\sin\theta$; peaks in the accumulator are lines.
Otsu picks the threshold that maximises between-class variance.
Snake energy $=E_{int}+E_{ext}$; internal is smoothness, external is edge attraction.
Mean shift moves to the kernel-weighted mean until convergence; no preset cluster count.
$Ncut=cut/assoc(A,V)+cut/assoc(B,V)$, solved by eigenvectors.
Graph cut energy $=$ data term $+\ \lambda\cdot$ smoothness term.

Memory hooks

Harris: "flat, edge, corner" means 0, 1, 2 large eigenvalues.
Snake: internal holds it together, external drags it to the edge.
Mean shift: "climb the hill to the mode" with no k needed.
Ncut: normalising stops the tiny-piece cheat of min-cut.
Graph cut: data plus smoothness, solved by max-flow.

Coverage checklist

Points and patches: Harris corners and matching (no past question).
Edges: Dec 2024 edge detection using neighbourhood operators.
Lines: Hough transform (no past question).
Segmentation: thresholding, region growing, clustering (no past question).
Active contours: Dec 2024 active contours in segmentation.
Split and merge: quadtree split and merge (no past question).
Mean shift and mode finding: Dec 2024 mean shift algorithm.
Normalized cuts: Dec 2024 normalized cuts and advantages.
Graph cuts and energy-based methods: Dec 2024 energy-based methods in feature detection.

Account

AI for Computer Vision (AD-701) - Unit 2 Short Notes

How unit 2 is examined

Points and patches

Edges

Lines

Segmentation

Active contours

Split and merge

Mean shift and mode finding

Normalized cuts

Graph cuts and energy-based methods

Last-minute revision

Memory hooks

Coverage checklist