Edges, corners, contours
This lecture shows how to find the distinctive places in an image. These are corners (Harris, Hessian), blobs (LoG, DoG) and contours (Suzuki-Abe border following). After this page, you can compute a Harris response by hand. You can explain why corners are better than edges and flat regions for matching. You can also trace the hierarchy that contour detection builds.
Feature extraction: the big picture
Feature extraction finds and describes distinctive structures in an image. It turns raw pixels into numbers that you can compare or give to a classifier. It keeps the essential information. The slides list eight families: edge detection, shape-based features, texture analysis, colour and intensity features, transform-based features, blob detection, local feature descriptors and corner detection.
Imagine you describe a friend in a crowd. You do not give every pixel of their photo. You say "tall, red jacket, round glasses". Features are that short, distinctive description. A good feature is one you can find again in another photo.
This lecture covers corners, blobs and contours. The lecture outline also names edge detection. The slides assume that you know it from the filtering lectures. Harris and contour detection both use gradients, so the next section is a short refresher.
Refresher: edges and gradients
An edge is a place where intensity changes sharply. The image gradient measures this change: $\nabla I = (I_x, I_y)$, where $I_x = \partial I/\partial x$ and $I_y = \partial I/\partial y$.
$m$ is edge strength (gradient magnitude). $\theta$ is the gradient direction. It points across the edge (perpendicular to the edge line). In code, use atan2(Iy, Ix) to get the correct quadrant.
The Sobel kernels estimate $I_x$ and $I_y$ and include smoothing:
| -1 | 0 | 1 |
| -2 | 0 | 2 |
| -1 | 0 | 1 |
| -1 | -2 | -1 |
| 0 | 0 | 0 |
| 1 | 2 | 1 |
The left kernel is $S_x$ (it detects vertical edges). The right kernel is $S_y$ (it detects horizontal edges).
Practice numerical: Sobel gradient. Patch:
| 10 | 20 | 30 |
| 20 | 30 | 40 |
| 30 | 40 | 50 |
$G_x$ = (right column weighted) $-$ (left column weighted) $= (30 + 2\cdot 40 + 50) - (10 + 2\cdot 20 + 30) = 160 - 80 = 80$.
$G_y$ = (bottom row weighted) $-$ (top row weighted) $= (30 + 2\cdot 40 + 50) - (10 + 2\cdot 20 + 30) = 160 - 80 = 80$.
$m = \sqrt{80^2 + 80^2} = 80\sqrt2 \approx 113.1$. $\theta = \tan^{-1}(80/80) = 45^\circ$.
Canny is the standard full edge detector. It has five steps:
- Smooth with a Gaussian.
- Compute the gradient magnitude and direction.
- Do non-maximum suppression: keep only the local maximum along the gradient direction. This thins edges to 1 pixel.
- Apply a double threshold to get strong edges, weak edges and non-edges.
- Do hysteresis: keep a weak edge only if it connects to a strong edge.
The Laplacian $\nabla^2 I = I_{xx} + I_{yy}$ finds edges at its zero crossings.
Corner detection: the idea
A corner is a point where two edges meet. Intensity changes rapidly in two directions in a small region. The slides use the "small window" test:
- You can recognise the point when you look through a small window.
- A shift of the window in any direction gives a large change in intensity.
Harris corner detector: the maths
Shift a small window $W$ by $(u,v)$. Measure how much the pixels inside change with the sum of squared differences:
$E$ is the "error" or change energy. $I$ is intensity. $(u,v)$ is the shift. $W$ is the window. At a corner, $E$ is large for every $(u,v)$.
Small-motion assumption. Expand with a first-order Taylor series. If $(u,v)$ is small, the higher-order terms are negligible:
$$ I(x+u,y+v) \approx I(x,y) + I_x u + I_y v = I(x,y) + [I_x\;\;I_y]\begin{bmatrix}u\\v\end{bmatrix} $$Put this into $E$. The $I(x,y)$ terms cancel:
$$ E(u,v) \approx \sum_{W}\left([I_x\;\;I_y]\begin{bmatrix}u\\v\end{bmatrix}\right)^2 = \sum_W [u\;\;v]\begin{bmatrix} I_x^2 & I_xI_y\\ I_yI_x & I_y^2\end{bmatrix}\begin{bmatrix}u\\v\end{bmatrix} $$Move $[u\;v]$ and the column out of the sum. The result is:
The slides call this matrix $H$. It is also called the structure tensor, second moment matrix or Harris matrix. It is a symmetric $2\times2$ matrix. It uses only first derivatives.
Why eigenvalues matter
Take shifts $(u,v)$ on the unit circle. The eigenvectors of $M$ give the directions of the biggest and smallest $E$.
- $x_+$ is the direction of the largest increase in $E$. $\lambda_+$ is the size of that increase.
- $x_-$ is the direction of the smallest increase. $\lambda_-$ is the size of that increase.
Eigenvalue refresher: an eigenvector $x$ of $A$ satisfies $Ax = \lambda x$. Solve $\det(A-\lambda I)=0$ to get the eigenvalues. For a $2\times2$ matrix with entries $h_{11},h_{12},h_{21},h_{22}$:
$$ \lambda_\pm = \tfrac12\Big[(h_{11}+h_{22}) \pm \sqrt{4h_{12}h_{21} + (h_{11}-h_{22})^2}\Big] $$When you know $\lambda$, solve $(A-\lambda I)x=0$ to get the eigenvector.
$M$ describes an ellipse of "how much the window changes". The long axis is the direction of fastest change. The short axis is the direction of slowest change. A flat patch gives a tiny ellipse. An edge gives a long thin ellipse. A corner gives a fat ellipse.
The three cases
| Region | Eigenvalues | Meaning |
|---|---|---|
| Flat | $\lambda_1\approx0,\ \lambda_2\approx0$ | No significant intensity change |
| Edge | $\lambda_1\gg\lambda_2$ or $\lambda_2\gg\lambda_1$ | Change in only one direction |
| Corner | $\lambda_1\gg0,\ \lambda_2\gg0$ (both large, similar) | Large change in all directions |
Harris response R
To compute eigenvalues for every pixel, you need square roots. Harris avoids this. His score uses the determinant and the trace. These equal the product and the sum of the eigenvalues:
$k$ is an empirical constant, typically $0.04$ to $0.06$. For $M=\begin{bmatrix}a&b\\b&c\end{bmatrix}$: $\det = ac-b^2$ and trace $=a+c$.
| Region | R |
|---|---|
| Flat | $R\approx0$ (small magnitude) |
| Edge | $R<0$ |
| Corner | $R>0$ and large |
Reason: for an edge, one eigenvalue is tiny. So $\lambda_1\lambda_2$ is small, but $(\lambda_1+\lambda_2)^2$ is big. This makes $R$ negative. For a corner, both eigenvalues are large and similar, so the product is larger.
Algorithm
- Compute gradients $I_x, I_y$ (Sobel).
- Compute the products $I_x^2,\ I_y^2,\ I_xI_y$ at every pixel.
- Smooth each product with a Gaussian $G$: $S_{xx}=G*I_x^2$, $S_{yy}=G*I_y^2$, $S_{xy}=G*(I_xI_y)$. This gives the weighted window sum.
- Form $M=\begin{bmatrix}S_{xx}&S_{xy}\\S_{xy}&S_{yy}\end{bmatrix}$ at each pixel.
- Compute $R=\det(M)-k\,\operatorname{trace}(M)^2$.
- Threshold: keep pixels with $R>T$.
- Do non-maximum suppression: keep only the local maxima of $R$ as the final corners.
Do not skip step 3. Without the smoothing, $M$ for a single pixel has rank 1 ($\det=0$), and every pixel looks like an edge. The window sum makes two directions possible.
Worked numerical (practice): Harris response from a window. A $2\times2$ window has these gradient pairs $(I_x, I_y)$: $(2,1),\ (1,2),\ (0,1),\ (1,0)$. Use uniform weights and $k=0.04$.
$S_{xx}=\sum I_x^2 = 4+1+0+1 = 6$. $S_{yy}=\sum I_y^2 = 1+4+1+0 = 6$. $S_{xy}=\sum I_xI_y = 2+2+0+0 = 4$.
| 6 | 4 |
| 4 | 6 |
$\det = 36-16 = 20$, trace $=12$. $R = 20 - 0.04\cdot144 = 20-5.76 = 14.24 > 0$. This is large, so the window is a corner.
Check with eigenvalues: $\lambda_\pm = \tfrac12[12 \pm \sqrt{4\cdot16+0}] = \tfrac12[12\pm8]$, so $\lambda=10,\,2$. Both are positive, the product is $20$ and the sum is $12$. The results agree.
Edge case. $M=\begin{bmatrix}10&0\\0&0.1\end{bmatrix}$: $\det=1$, trace$^2=102.01$, $R=1-4.08=-3.08<0$, an edge. Flat case. $M=0.1I$: $\det=0.01$, trace$^2=0.04$, $R=0.01-0.0016\approx0.008\approx0$, flat.
Advantages and limitations
| Advantages | Limitations |
|---|---|
| Rotation invariant (eigenvalues do not change when the image rotates) | Not scale invariant: a corner at one scale looks like an edge or curve when zoomed |
| Computationally efficient | Sensitive to the threshold $T$ |
| Good localisation of corners | May miss corners at other scales |
| Robust to noise after Gaussian smoothing |
A typical exam has four tasks: (1) derive $M$ from $E(u,v)$ with a Taylor series, (2) classify a given $M$ with $R$, (3) explain why $R<0$ for edges, (4) explain why Harris is rotation invariant but not scale invariant. Remember that Harris is only partly illumination invariant. Additive intensity changes are fine (derivatives). Multiplicative contrast changes scale $R$.
Hessian corner detector
The Hessian detector uses second-order derivatives (curvature) instead of first derivatives. The Hessian matrix at a pixel is:
Smooth with a Gaussian first, then compute the derivatives. This suppresses noise.
Algorithm
- Smooth: $L(x,y)=G(x,y,\sigma)*I(x,y)$.
- Compute second derivatives $L_{xx},L_{yy},L_{xy}$.
- Form $H=\begin{bmatrix}L_{xx}&L_{xy}\\L_{xy}&L_{yy}\end{bmatrix}$.
- Response $R=\det(H)=L_{xx}L_{yy}-L_{xy}^2$.
- Threshold: keep $R>T$.
- Do non-maximum suppression: keep the local maxima.
Practice numerical. At a pixel $L_{xx}=4,\ L_{yy}=3,\ L_{xy}=1$. $R=4\cdot3-1^2=11$. A large positive value means curvature in both directions (corner or blob-like). Now take $L_{xx}=4,\ L_{yy}=-3,\ L_{xy}=1$. Then $R=-12-1=-13<0$. This is a saddle (it curves in opposite ways), and the detector rejects it.
Harris vs Hessian: Harris uses the first derivatives summed over a window (structure tensor, 7 steps, needs $k$). Hessian uses the second derivatives at a point. It uses only $\det(H)$ and needs no $k$.
Blob detection
A blob is a region that differs from its surroundings in brightness, colour or texture. An example is a sunflower head against dark leaves. A blob has a size, but a corner does not. So blob detectors must search over scale. The 1-D pictures on the slide show typical blob profiles. These are a bright plateau, a dark plateau, a bump, a dip, a triangle and a skewed bump.
Why a second derivative of Gaussian works
Convolve a 1-D blob $f(x)$ with $\partial^2 n_\sigma/\partial x^2$. Here $n_\sigma$ is a Gaussian with spread $\sigma$. This kernel looks like an upside-down Mexican hat. The response has strong extrema when the kernel width matches the blob width. The slides show three blobs: A (narrow), B and C (wide).
- With a small fixed $\sigma$, the narrow blob A gives a clean single dip. The wide blobs B and C give two separate side responses, because the kernel sees only their edges.
- With a larger $\sigma$, the raw response gets smaller, because more blur gives weaker derivatives. To compare scales fairly, multiply by $\sigma^2$. This is scale normalisation: $\sigma^2\,\dfrac{\partial^2 n_\sigma}{\partial x^2}*f(x)$.
- As $\sigma$ grows, the normalised response of each blob becomes a single deep minimum at its centre when $\sigma$ matches its size. The narrow blob A peaks at a small $\sigma$. The wide blob C needs a larger $\sigma$.
Scan over $\sigma$ and pick the $\sigma$ where the normalised response is extreme. The location gives the blob centre. The $\sigma$ gives the blob size. In 2-D, a blob of radius $r$ responds best at $\sigma = r/\sqrt2$.
Techniques
| Method | How it works |
|---|---|
| Laplacian of Gaussian (LoG) | Convolve with a Gaussian. Apply the Laplacian $\nabla^2$ to highlight rapid intensity change. Find the extrema or zero crossings to locate blobs. Scale-normalised: $\sigma^2\nabla^2 G$. |
| Difference of Gaussians (DoG) | Subtract two blurred copies (different $\sigma$). This is a cheap approximation of LoG: $G(k\sigma)-G(\sigma)\approx(k-1)\sigma^2\nabla^2G$. |
| Determinant of Hessian | A blob is where $\det(H)$ is large: intensity changes strongly in several directions. |
Search for local extrema in $(x,y,\sigma)$. SIFT (next lecture) uses this.
Contour detection
A contour is a continuous boundary of a shape or object whose pixels share colour, brightness or intensity. Contour detection groups edge pixels into continuous paths (lists of $(x,y)$ coordinates). These paths define shapes and hierarchies.
Edge detection gives loose ink dots along boundaries. Contour detection connects the dots into closed outlines. It also shows which outline is inside which outline (a doughnut has an outer contour and an inner contour).
Pipeline
- Convert to grayscale.
- Reduce noise (Gaussian blur).
- Binarise or extract edges (threshold or Canny) to get a 0/1 image.
- Trace boundaries: scan the binary image, follow contiguous non-zero pixels and store their $(x,y)$ coordinate sets.
Border types
- Outer border: the boundary of a connected component.
- Hole border: the boundary around a hole inside an object.
Slide examples (1 = foreground). Left: a hollow rectangle. It is one connected component with an outer border and a hole inside. Right: a ring with a single pixel in its hole.
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
In the right image, the ring has an outer border and a hole border. The highlighted centre pixel is its own object (an outer border) inside that hole.
Connectivity
The algorithm generally uses 8-connectivity: all eight surrounding pixels are neighbours. The neighbours of $P$ are numbered counter-clockwise, starting from the east:
| P4 | P3 | P2 |
| P5 | P | P1 |
| P6 | P7 | P8 |
4-connectivity uses only P1, P3, P5 and P7 (right, up, left, down).
Suzuki-Abe border following
This is the algorithm in OpenCV findContours. It extracts outer and hole borders. It builds a parent-child tree of regions in one raster scan. The image is a matrix $F=\{f(i,j)\}$. Row $i$ goes from top to bottom. Column $j$ goes from left to right. Pixel values: $0$ = background, $1$ (or $>0$) = foreground.
Variables
- $NBD$ (Number of Border): counter of the borders found so far. It starts at $1$, which stands for the image frame.
- $LNBD$ (Last encountered Border): the $NBD$ of the most recent border crossed on the current row. Reset to $1$ at the start of every row.
Step 1: raster scan, decide whether a new border starts at $(i,j)$ with $f(i,j)\ge1$
Outer border start: $f(i,j)=1$ and $f(i,j-1)=0$. Then $NBD\leftarrow NBD+1$, $(i_2,j_2)\leftarrow(i,j-1)$, type = outer.
Hole border start: $f(i,j)\ge1$ and $f(i,j+1)=0$. Then $NBD\leftarrow NBD+1$, $(i_2,j_2)\leftarrow(i,j+1)$, type = hole; and if $f(i,j)>1$, $LNBD\leftarrow f(i,j)$.
If neither holds, skip tracing and go to Step 4.
$(i_2,j_2)$ is a background neighbour. The neighbourhood search starts from it.
Step 2: parent assignment
The parent of the new border depends on its type and on the type of the $LNBD$ border:
| Current border | LNBD border | Relationship | Parent of new border |
|---|---|---|---|
| Outer | Outer | Siblings (same parent container) | parent(NBD) = parent(LNBD) |
| Outer | Hole | Enclosed inside that hole | parent(NBD) = LNBD |
| Hole | Hole | Siblings (same parent object) | parent(NBD) = parent(LNBD) |
| Hole | Outer | Enclosed inside that object | parent(NBD) = LNBD |
Step 3: tracing loop
3.1 first neighbour. Let $(i_3,j_3)=(i,j)$. Start from $(i_2,j_2)$ and search clockwise around $(i,j)$ among its 8 neighbours. Find the first non-zero pixel $(i_1,j_1)$.
- Isolated pixel (all 8 neighbours are 0): set $f(i,j)\leftarrow-NBD$ and finish this border (go to Step 4).
- Otherwise set $(i_2,j_2)\leftarrow(i_1,j_1)$ and enter the loop.
3.2 traversal loop. $(i_3,j_3)$ is the current pixel, $(i_2,j_2)$ its previously visited neighbour.
- Start from $(i_2,j_2)$ and go counter-clockwise around $(i_3,j_3)$. Find the first non-zero pixel $(i_4,j_4)$.
- Mark the current pixel:
- If $(i_3,j_3+1)$ is a 0-pixel (background on the right), set $f(i_3,j_3)\leftarrow-NBD$.
- Else if $(i_3,j_3+1)$ is not 0 and $f(i_3,j_3)=1$, set $f(i_3,j_3)\leftarrow NBD$.
- Otherwise leave it unchanged.
- Check for termination. If $(i_4,j_4)=(i,j)$ and $(i_3,j_3)=(i_1,j_1)$ (back at the start, heading the same way), the border is complete. Otherwise set $(i_2,j_2)\leftarrow(i_3,j_3)$ and $(i_3,j_3)\leftarrow(i_4,j_4)$, and repeat.
Step 4: resume the scan
If $f(i,j)\ne1$, set $LNBD\leftarrow|f(i,j)|$. The slide writes $\ne1$. The original algorithm also excludes $0$, because background does not change $LNBD$. Move to $(i,j+1)$. Stop after the bottom-right pixel.
Marking rule: a border pixel gets $-NBD$ when background is on its right, and $+NBD$ otherwise. Later scans use this mark to know that a border "ended" there, and they update $LNBD$. These labels tell the scan, row by row, which region it is in.
Worked example (the matrix on the last slide).
| 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 |
This is a rectangular ring (a $4\times4$ square of ones with a $2\times2$ hole). Start: $NBD=1$ (the frame), $LNBD=1$.
- Row 0. $(0,0)=0$: nothing. At $(0,1)$: $f=1$ and $f(0,0)=0$, so an outer border starts. $NBD=2$, $(i_2,j_2)=(0,0)$. Parent: $LNBD=1$ is the frame (treated as outer). By the outer/outer rule, the border is a sibling at top level, and its parent is the frame. Trace clockwise: $(0,1)\to(0,2)\to(0,3)\to(0,4)\to(1,4)\to(2,4)\to(3,4)\to(3,3)\to(3,2)\to(3,1)\to(2,1)\to(1,1)\to(0,1)$, then stop (back at the start). Pixels with background on the right get $-2$: the whole column 4. Other border pixels with a 1 on the right get $+2$.
- Remaining row 0. $(0,4)$ has value $-2$, so $LNBD\leftarrow2$. Then $(0,5)=0$.
- Row 1. $LNBD$ resets to $1$. At $(1,1)$ value is $2\ge1$ and $f(1,2)=0$: a hole border starts. $NBD=3$, $(i_2,j_2)=(1,2)$. Because $f(1,1)=2>1$, $LNBD\leftarrow2$. Rule hole / outer: the hole is inside object 2, so parent(3) $=2$. Trace around the 8 pixels that surround the hole. Pixels whose right neighbour is a hole zero, $(1,1)$ and $(2,1)$, become $-3$.
- Rest of scan. No other border starts. $(1,4)$ and $(2,4)$ are $-2$ (not $\ge1$). Row 3 has no new border start. Its pixels already have labels. No unvisited $1$ has background on its left or right in a new way. The scan ends at $(3,5)$.
Resulting labels:
| 0 | 2 | 2 | 2 | -2 | 0 |
| 0 | -3 | 0 | 0 | -2 | 0 |
| 0 | -3 | 0 | 0 | -2 | 0 |
| 0 | 2 | 2 | 2 | -2 | 0 |
Hierarchy: frame (1) $\to$ outer border (2) $\to$ hole border (3). There are two contours: one outer and one inner. OpenCV returns this with RETR_TREE or RETR_CCOMP.
In an exam, the key points are the increments of $NBD$, the border types and the parent tree. The exact $\pm$ labels depend on the details of the tracing direction, so state your convention.
Common slips: Do not forget that the frame is border number 1. Do not use 4-connectivity (the algorithm uses 8). Do not mix the scan directions: the initial search is clockwise and the traversal is counter-clockwise, as in the slides. Do not forget to reset $LNBD$ at the start of each row.
Detectors compared
| Detector | Looks for | Derivatives | Scale handling | Key formula |
|---|---|---|---|---|
| Harris | Corners | First (structure tensor) | Single scale (not scale invariant) | $\det(M)-k\,\mathrm{tr}(M)^2$ |
| Hessian | Corners / blobs | Second | Single scale (extendable) | $\det(H)$ |
| LoG | Blobs | Second (Laplacian) | Multi-scale with $\sigma^2$ normalisation | $\sigma^2\nabla^2G*I$ |
| DoG | Blobs | Approximates LoG | Multi-scale pyramid | $G_{k\sigma}-G_\sigma$ |
Quick self-test
1. Why are corners better features to match than edge points or flat points?
A flat patch looks the same everywhere, so it has no unique position. An edge point can slide along the edge without a change in the window (aperture problem: the position is ambiguous in one direction). A corner changes in every shift direction, so it has a unique, repeatable location.
2. Derive the Harris matrix from $E(u,v)$.
Start from $E=\sum[I(x+u,y+v)-I(x,y)]^2$. Use $I(x+u,y+v)\approx I+I_xu+I_yv$. The bracket becomes $I_xu+I_yv$. Square and sum: $E\approx\sum(I_x^2u^2+2I_xI_yuv+I_y^2v^2)=[u\ v]M[u\ v]^T$ with $M=\sum\begin{bmatrix}I_x^2&I_xI_y\\I_xI_y&I_y^2\end{bmatrix}$.
3. Classify the pixel with $S_{xx}=9,\ S_{yy}=1,\ S_{xy}=0$, $k=0.05$.
The pixel is edge-like. $\det=9$ and trace $=10$. $R=9-0.05\cdot100=4$. The eigenvalues are $9$ and $1$. $R$ is positive but only modest. The eigenvalue ratio is 9:1, so one direction dominates. In practice, a threshold $T$ larger than $4$ rejects it. Compare with $S_{xx}=S_{yy}=9$: $R=81-0.05\cdot324=64.8$, a clear corner. Lesson: $R>0$ is not enough. The value must also be large.
4. Why is Harris rotation invariant but not scale invariant?
Rotation rotates the eigenvectors of $M$ but does not change the eigenvalues, so $R$ does not change. Scaling changes the geometry that the window sees. A corner at a coarse scale in a fixed window looks like a curved edge, so $R$ changes. Multi-scale methods (LoG/DoG, SIFT) fix this.
5. Compare Harris and Hessian detectors in two or three lines.
Harris builds a window-summed matrix of products of first derivatives. It scores the matrix with $\det-k\,\mathrm{tr}^2$. Hessian uses the matrix of second derivatives of the smoothed image. It scores the matrix with $\det(H)$. Both detectors apply a threshold and then non-maximum suppression.
6. Why multiply by $\sigma^2$ in blob detection?
The derivative responses of a Gaussian shrink as $\sigma$ grows, so you cannot compare raw responses at different scales. The $\sigma^2$ factor (scale normalisation) makes the response at the matching scale a comparable maximum. The best $\sigma$ then gives the blob size.
7. A blob has radius $r=7$ pixels. Roughly what $\sigma$ should LoG use?
$\sigma=r/\sqrt2=7/1.414\approx4.95$.
8. Define NBD and LNBD in Suzuki-Abe, and state what happens on finding an isolated pixel.
$NBD$ counts the borders found (it starts at 1 for the frame). $LNBD$ is the number of the last border crossed on the current row (reset to 1 each row). An isolated pixel (all 8 neighbours zero) gets the mark $-NBD$, and its tracing ends immediately.
9. Give the parent for a new hole border when the LNBD border is an outer border.
The parent is the LNBD border: parent(NBD) $=$ LNBD, because the hole is inside that object. If LNBD is a hole border, the new hole is its sibling: parent(NBD) = parent(LNBD).
10. List the contour detection pipeline.
Grayscale conversion, noise reduction, binarisation or edge extraction, and boundary tracing (for example Suzuki-Abe). Boundary tracing produces coordinate lists and the hierarchy.
- Corner: intensity changes strongly in two directions in a small window. Flat: no change. Edge: change only across the edge.
- $E(u,v)=\sum[I(x+u,y+v)-I(x,y)]^2\approx[u\ v]M[u\ v]^T$ with $M=\sum\begin{bmatrix}I_x^2&I_xI_y\\I_xI_y&I_y^2\end{bmatrix}$ (structure tensor).
- Eigenvalues of $M$: both small = flat, one large = edge, both large = corner.
- $R=\det(M)-k\,\mathrm{tr}(M)^2$, $k\approx0.04$ to $0.06$: $R<0$ edge, $R\approx0$ flat, $R>0$ large corner.
- Harris steps: Sobel gradients, products, Gaussian smoothing, matrix, response, threshold, non-maximum suppression.
- Harris: rotation invariant, efficient, localises well; not scale invariant, threshold sensitive.
- Hessian: second derivatives of smoothed image; $R=\det(H)=L_{xx}L_{yy}-L_{xy}^2$.
- Blobs: LoG, DoG, determinant of Hessian; multiply by $\sigma^2$ to compare scales; extremum over $(x,y,\sigma)$ gives centre and size.
- Contours: grayscale, denoise, binarise, trace boundaries; outer border vs hole border; 8-connectivity.
- Suzuki-Abe: raster scan with $NBD$ and $LNBD$; outer start $f(i,j)=1,\ f(i,j-1)=0$; hole start $f(i,j)\ge1,\ f(i,j+1)=0$; builds a parent-child tree.