Watershed, hierarchical clustering & Hough transform
This page covers three mid-level vision tools. Watershed splits an image into regions by "flooding" it. Hierarchical clustering groups pixels by similarity into a tree. The Hough transform finds lines and circles when edge points vote. After this page you can run each tool by hand on a small example. The exam asks for this.
Where these fit
Low-level vision gives pixels, edges and filters. Mid-level vision groups these into larger things: regions, clusters, lines and circles. The three topics here are three different ways to group.
| Tool | What it groups | Key idea |
|---|---|---|
| Watershed | pixels into regions | treat intensity as height, flood from the valleys, build dams where floods meet |
| Hierarchical clustering | items (pixels, features) into a tree of clusters | repeatedly merge the two closest clusters |
| Hough transform | edge pixels into lines / circles / shapes | each edge pixel votes for every shape it could belong to |
Watershed algorithm
Watershed is a region-based segmentation method. It views a grayscale image as a topographic surface. The intensity of a pixel is its height. Watershed separates touching or overlapping objects, for example coins that touch or cells in a microscope image.
Think of the image as a landscape. Dark pixels (low intensity) are valleys and bright pixels are hills. Drill a hole at the bottom of every valley and slowly raise the water level. Each valley fills with its own lake. Build a thin dam just before two lakes merge. At the end, the dams are the segmentation boundaries and each lake is one region.
Terms you must be able to define
- Low intensity is a valley (catchment basin). High intensity is a hill or mountain.
- Regional minimum: a pixel (or flat patch) with an intensity lower than all its neighbours. In the example below, the centre pixel 2 is a regional minimum.
- Catchment basin: the set of pixels that "drain" into one minimum. Example: the 3×3 patch with centre 2 is one basin, Basin A.
- Watershed line (dam): the boundary between two catchment basins. Water from two valleys is about to merge there.
Regional minimum (slide example): the 2 is lower than all 8 neighbours.
| 8 | 8 | 8 |
| 8 | 2 | 8 |
| 8 | 8 | 8 |
Catchment basin (slide example): everything drains towards the 2.
| 6 | 5 | 4 |
| 5 | 2 | 5 |
| 6 | 5 | 6 |
Watershed line: columns of A and B pixels separated by a vertical dam |.
| A | A | A | A | | | B | B | B | B |
| A | A | A | A | | | B | B | B | B |
| A | A | A | A | | | B | B | B | B |
Algorithm in words
- Find all regional minima. Give each minimum its own label (A, B, ...) as a seed.
- Raise the flood level one intensity value at a time, from lowest to highest.
- At each level, add to a basin every unlabelled pixel that touches the basin and has an intensity at or below the level.
- If two different basins reach a pixel at the same time, do not give it to either basin. Mark it as watershed line (W).
- Stop after the highest level. The W pixels are the boundaries.
Worked example from the slides (5×5 image)
Coordinates below are (row, column), counted from 1.
| 9 | 8 | 7 | 8 | 9 |
| 8 | 3 | 5 | 4 | 8 |
| 7 | 5 | 9 | 5 | 7 |
| 8 | 4 | 5 | 3 | 8 |
| 9 | 8 | 7 | 8 | 9 |
Step 1: find regional minima. The lowest values are $(2,2)=3$ and $(4,4)=3$. They are the two initial catchment basins, A and B.
Step 2: flood level = 3. Water fills only the minima. $B_1=\{(2,2)\}$, $B_2=\{(4,4)\}$. Label image (0 = unlabelled):
| 0 | 0 | 0 | 0 | 0 |
| 0 | A | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | B | 0 |
| 0 | 0 | 0 | 0 | 0 |
Step 3: flood level = 4. Pixels with intensity $\le 4$ join the nearest basin. The new pixels are $(2,4)=4$ and $(4,2)=4$. The slide gives $(2,4)$ to A and $(4,2)$ to B.
| 0 | 0 | 0 | 0 | 0 |
| 0 | A | 0 | A | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | B | 0 | B | 0 |
| 0 | 0 | 0 | 0 | 0 |
Step 4: flood level = 5. The water floods the pixels with value 5: $(2,3),(3,2),(3,4),(4,3)$. The basins start to expand. A grows to $(2,3),(3,2)$. B grows to $(3,4),(4,3)$.
| 0 | 0 | 0 | 0 | 0 |
| 0 | A | A | A | 0 |
| 0 | A | 0 | B | 0 |
| 0 | B | B | B | 0 |
| 0 | 0 | 0 | 0 | 0 |
Step 5: flood level = 7. The centre $(3,3)=9$ is not flooded yet. Pixels of intensity 7 become active and both basins grow toward the centre.
Step 6: flood level = 9. Both basins reach the centre pixel $(3,3)$ at the same time. Do not give it to either basin. Make it a watershed boundary: $W=(3,3)$. The final segmentation (as on the slide):
| 0 | 0 | 0 | 0 | 0 |
| 0 | A | A | A | 0 |
| 0 | A | W | B | 0 |
| 0 | B | B | B | 0 |
| 0 | 0 | 0 | 0 | 0 |
Write the slide's answer in the exam. Note two caveats. (1) The slide leaves the outer ring (values 7, 8, 9) as 0. A full run floods those pixels at levels 7 to 9 and gives them to the nearest basin. Mention the ring if the examiner asks. (2) Strictly, $(2,4)$ and $(4,2)$ are also regional minima (value 4, below all neighbours). The slide lets them join the nearest basin. This is what happens in marker-controlled watershed, where you pick the seeds yourself.
Examiners like these textbook facts. Plain watershed on a raw image over-segments, because every small noise minimum becomes a region. To fix this, smooth the image first, or use marker-controlled watershed (only the chosen markers are seeds). Run watershed on the gradient magnitude image, so that the edges are the ridges. Or run it on a distance transform to split touching round objects.
Extra practice. 1D row of intensities: $4,\ 1,\ 3,\ 6,\ 2,\ 5$ (positions 1 to 6). Segment it.
The regional minima are position 2 (value 1) and position 5 (value 2). Level 1: A at pos 2. Level 2: B at pos 5. Level 3: pos 3 touches A, so A. Level 4: pos 1 touches A, so A. Level 5: pos 6 touches B, so B. Level 6: pos 4 touches A (pos 3) and B (pos 5) at the same time, so it is the watershed W.
Result: A A A W B B (figure above).
Hierarchical clustering
Clustering groups similar items. Agglomerative hierarchical clustering starts with each item as its own cluster. It repeatedly merges the two closest clusters until one cluster remains. The record of the merges is a tree, the dendrogram. In the slides the items are image pixels, described by their grayscale intensity.
$d(i,j)$ is the distance between pixel $i$ and pixel $j$; $I_i$ is the grayscale intensity of pixel $i$. This is the distance between two single items. To merge clusters, you also need a rule for the distance between clusters. This rule is the "link".
The algorithm
- Compute the distance matrix between all items.
- Find the smallest off-diagonal entry. Merge those two clusters. Record the merge distance (the dendrogram height).
- Rebuild the matrix. Use the linkage rule to find the distance from the new cluster to every other cluster. All other distances stay the same.
- Repeat until one cluster is left. $n$ items give exactly $n-1$ merges.
The data (used for both examples)
| Pixel | P1 | P2 | P3 | P4 | P5 |
|---|---|---|---|---|---|
| Intensity | 10 | 12 | 18 | 25 | 40 |
Step 1: distance matrix. Use $d=|I_i-I_j|$. For example, $d(P1,P3)=|10-18|=8$ and $d(P4,P5)=|25-40|=15$.
| P1 | P2 | P3 | P4 | P5 | |
| P1 | 0 | 2 | 8 | 15 | 30 |
| P2 | 2 | 0 | 6 | 13 | 28 |
| P3 | 8 | 6 | 0 | 7 | 22 |
| P4 | 15 | 13 | 7 | 0 | 15 |
| P5 | 30 | 28 | 22 | 15 | 0 |
The smallest entry is 2, between P1 and P2, so both methods merge them first.
A. Single-link clustering (nearest neighbour)
$A,B$ are clusters and $x,y$ are individual members. The cluster distance is the distance between the closest pair, one member from each cluster.
Iteration 1. The smallest distance is 2. Merge $C_1=\{P1,P2\}$. The clusters are $\{P1,P2\},\{P3\},\{P4\},\{P5\}$. Update the matrix with min:
$D(C_1,P3)=\min(8,6)=6$, $D(C_1,P4)=\min(15,13)=13$, $D(C_1,P5)=\min(30,28)=28$. The rest are unchanged.
| C1 | P3 | P4 | P5 | |
| C1 | 0 | 6 | 13 | 28 |
| P3 | 6 | 0 | 7 | 22 |
| P4 | 13 | 7 | 0 | 15 |
| P5 | 28 | 22 | 15 | 0 |
Iteration 2. The candidates are $D(C_1,P3)=6$, $D(P3,P4)=7$ and $D(P4,P5)=15$. The minimum is 6. Merge $C_2=\{P1,P2,P3\}$. Update: $D(C_2,P4)=\min(13,7)=7$, $D(C_2,P5)=\min(28,22)=22$.
| C2 | P4 | P5 | |
| C2 | 0 | 7 | 22 |
| P4 | 7 | 0 | 15 |
| P5 | 22 | 15 | 0 |
Iteration 3. $D(C_2,P4)=\min(15,13,7)=7$ (from the original distances P1-P4, P2-P4, P3-P4). $D(P4,P5)=15$. The minimum is 7. Merge $C_3=\{P1,P2,P3,P4\}$. Update: $D(C_3,P5)=\min(30,28,22,15)=15$.
Iteration 4. Only $D(C_3,P5)=15$ remains. Merge all: $\{P1,P2,P3,P4,P5\}$.
Merge heights: 2, 6, 7, 15.
B. Complete-link clustering (farthest neighbour)
The cluster distance is the distance between the farthest pair. Two clusters are close only if every pair of members is close.
Iteration 1. The smallest distance is 2. Merge $C_1=\{P1,P2\}$. Update with max: $D(C_1,P3)=\max(8,6)=8$, $D(C_1,P4)=\max(15,13)=15$, $D(C_1,P5)=\max(30,28)=30$.
| C1 | P3 | P4 | P5 | |
| C1 | 0 | 8 | 15 | 30 |
| P3 | 8 | 0 | 7 | 22 |
| P4 | 15 | 7 | 0 | 15 |
| P5 | 30 | 22 | 15 | 0 |
Iteration 2. $D(C_1,P3)=8$, $D(P3,P4)=7$, $D(P4,P5)=15$. The minimum is 7. Merge $C_2=\{P3,P4\}$. The clusters are $\{P1,P2\},\{P3,P4\},\{P5\}$.
Update: $D(C_1,C_2)=\max(8,15,6,13)=15$
$D(C_2,P5)=\max(22,15)=22$
$D(C_1,P5)=30$.
| C1 | C2 | P5 | |
| C1 | 0 | 15 | 30 |
| C2 | 15 | 0 | 22 |
| P5 | 30 | 22 | 0 |
Iteration 3. $D(C_1,C_2)=15$, $D(C_2,P5)=22$, $D(C_1,P5)=30$. The minimum is 15. Merge $C_3=\{P1,P2,P3,P4\}$.
Iteration 4. $D(C_3,P5)=\max(30,28,22,15)=30$. Merge all.
Merge heights: 2, 7, 15, 30.
Dendrograms
To get a chosen number of clusters, cut the dendrogram with a horizontal line. With complete link, a cut at height 10 gives $\{P1,P2\},\{P3,P4\},\{P5\}$. With single link, a cut at height 10 gives $\{P1,P2,P3,P4\},\{P5\}$.
Single link vs complete link
| Aspect | Single link | Complete link |
|---|---|---|
| Cluster distance | $\min$ over pairs (closest members) | $\max$ over pairs (farthest members) |
| Merge heights in this example | 2, 6, 7, 15 | 2, 7, 15, 30 |
| Cluster shape | long, straggly "chains" (chaining effect) | compact, roughly equal-diameter clusters |
| Sensitive to | noise bridges (one stray point can join two clusters) | outliers (one far point inflates a cluster's distance) |
| Good for | elongated or irregular shapes | round, well separated groups |
| Final merge in example | P5 joins at 15 | P5 joins at 30 |
Do not update a merged row with the wrong function. This is the most common exam error. Single link uses the min of the two old entries. Complete link uses the max. Always show the new matrix after every merge and write the merge height.
Extra practice. The pixel intensities are 1, 3, 8, 12 (call them a, b, c, d). Distances: ab=2, ac=7, ad=11, bc=5, bd=9, cd=4.
Single link. Merge {a,b} at 2. In the new row, the distance to c is $\min(7,5)=5$ and to d is $\min(11,9)=9$. cd=4. The smallest is 4, so merge {c,d} at 4. Then $D(\{a,b\},\{c,d\})=\min(7,11,5,9)=5$, merge at 5. Heights: 2, 4, 5.
Complete link. Merge {a,b} at 2. In the new row, the distance to c is $\max(7,5)=7$ and to d is $\max(11,9)=11$. cd=4. Merge {c,d} at 4. Then $D=\max(7,11,5,9)=11$, merge at 11. Heights: 2, 4, 11.
The tree shape is the same, but the top heights are very different. Single link says the two groups are "5 apart". Complete link says they are "11 apart".
Hough transform
Why we need it
Edges, textons and colour are all local features. Edges carry geometric information, but a map of edge pixels is only a set of dots. The Hough transform goes from edge pixels to abstract shapes such as lines and circles.
Task. Input: the edge map $E$ of an image $I$, and the parameters that define one line or curve. Output: the locations of all instances of that line (curve), or of parts of it, in $I$.
Method 1: template matching
- Create a template (mask, mini-image) of an exemplary line or curve.
- Convolve the image with the template. An exact match gives a high response.
- Drawback: each orientation needs its own template. It is hard to make a mask that is accurate and general.
- Advantage: the idea works for arbitrary shapes. People use it in face detection.
Method 2: Hough transform (HT)
You may not have an equation for the shape, but you can measure a distinctive property of it (a line has a slope and an intercept). Measure that property at every edge pixel. A pixel that has it is a candidate. Count how many pixels agree. A high count means the object is there. HT turns a hard pattern-detection problem into simple peak detection. HT is a voting scheme.
Advantages: edges need not be connected, and the object (line, circle) can be partly visible. HT is the traditional way to detect lines and circles.
Key idea for lines. Every line in the image has an equation. A single white point can lie on infinitely many lines. In HT, each point votes for every line it can be on. The lines with the most votes win.
Step 1: measure the property (m-c parameter space)
$m$ = slope, $c$ = y-intercept. The parameter pair $(m,c)$ identifies a line uniquely. So a line in image space is a single point in parameter space (also called Hough space).
$$ c = -x_i\, m + y_i $$Now reverse the view. A fixed edge point $(x_i,y_i)$ is a point in image space. It satisfies $y_i = m x_i + c$ for many $(m,c)$ pairs. Written as $c=-x_i m + y_i$, those pairs form a line in parameter space. So a point in image space = a line in Hough space. A line in image space = a point in Hough space.
Step 2: count (the accumulator)
- Divide the parameter space $(m,c)$ into bins.
- Create an accumulator array $A(m,c)$ and set $A(m,c)=0$ for all $m,c$.
- For each edge point $(x_i,y_i)$ and each $m$ in the range, compute $c=-x_i m + y_i$. Increment $A(m,c)=A(m,c)+1$.
- Find the local maxima in $A(m,c)$. Each peak is a detected line.
Extra practice (m-c accumulator). The points are $P_1(0,1)$, $P_2(1,2)$, $P_3(2,3)$. Test the slopes $m\in\{0,1,2\}$ and use $c=-x_i m + y_i$.
| point | m=0 | m=1 | m=2 |
| P1 (0,1): c = 1 | 1 | 1 | 1 |
| P2 (1,2): c = 2 − m | 2 | 1 | 0 |
| P3 (2,3): c = 3 − 2m | 3 | 1 | −1 |
Cell $(m,c)=(1,1)$ gets 3 votes (all three points). Every other cell gets at most 1 vote (check: $(0,1),(0,2),(0,3),(2,1),(2,0),(2,-1)$ each get one). The peak $(1,1)$ gives $y=1\cdot x+1$, the line through all three points.
Remark on noise. Quantisation and noise can cause the accumulator to miss some edge points of the line. The cell still has the highest count.
The problem with y = mx + c, and the fix
The accumulator is finite, but the slope has an infinite range $-\infty\le m\le\infty$. A vertical line has $m=\infty$, which you cannot represent. Use a different line representation with a bounded parameter space.
Foot-of-the-normal (ρ-θ) representation
Draw the perpendicular from the origin to the line. $\rho$ is the length of that perpendicular (the distance of the line from the origin). $\theta$ is the angle between the perpendicular and the x-axis. The parameter space is bounded: $0\le\theta\le 2\pi$ (equivalently $0^\circ$ to $180^\circ$ if $\rho$ can be signed) and $0\le\rho\le\rho_{\max}$. $\rho_{\max}$ is about the image diagonal. For a point $(x_i,y_i)$, compute $(\rho,\theta)$.
The slide that defines this shows $\rho=-x\cos\theta+y\sin\theta$ (a different angle convention). The next slides and the Lecture 13 numerical use $\rho=x\cos\theta+y\sin\theta$. Use the plus form. It is the standard form and the numerical uses it.
Image space to Hough space
For an edge point $(x_i,y_i)$ and all $0\le\theta\le 2\pi$, compute $\rho = x_i\cos\theta + y_i\sin\theta$. A point in image space is a sinusoidal curve in $(\theta,\rho)$ space. (In m-c space it was a straight line.)
Voting examples
- Points. One point gives one sinusoid. Two points give two sinusoids. Their intersection has "two votes" and is the straight line through both points.
- Clean line. Many collinear points: all their sinusoids meet at one bright spot in the vote image. That peak is the line.
- Noisy line. The curves nearly meet. The peak is smeared and lower. The votes spread over neighbouring bins, so fewer votes reach one bin as noise increases.
- No line. Random points give curves that cross everywhere. There is no strong peak.
- Clutter. More noise points raise the maximum vote count through random coincidences. More bins then show a false peak.
Practical remarks on HT for lines
- How many lines? As many as there are peaks. Merge adjacent peaks. Use a threshold for peak detection.
- Which points belong to the line? Find the points close to the peak in Hough space, or close to the line in image space. Solve for that line and iterate.
- Accumulator cell size matters. Too small: you can miss lines, especially with noise, because the votes split across cells. Too big: you can merge distinct lines.
HT for circle detection
$(a,b)$ is the circle centre and $r$ is the radius. For a known radius, the centre identifies the circle. The Hough space is 2D, $A(a,b)$. Each edge point $(x_i,y_i)$ becomes a circle of radius $r$ in $(a,b)$ space (all possible centres at distance $r$ from the point). The circles from points on one real circle all intersect at the true centre. For an unknown radius, you need a 3D accumulator $A(a,b,r)$.
Using gradient information (faster)
A gradient-based edge detector gives each edge point $(x_i,y_i)$ an edge direction $\phi_i$. For a specific radius $r$, the centre is at distance $r$ along that direction. So you vote at only one point:
$\phi_i$ = gradient (edge) direction at the point. You add a vote to only one accumulator cell. So a point in image space becomes a point in Hough space (not a circle). This costs much less.
Coins example. Edge detection finds the coin outlines (with texture noise from the cloth). Pennies and quarters have different radii, so build a separate accumulator for each circle size. The pennies' Hough space and the quarters' Hough space each show bright dots at the matching coin centres. The final result: each coin is found and circled.
Extra practice (circle). The edge point is $(x_i,y_i)=(10,6)$, the gradient direction is $\phi_i=0^\circ$ and the known radius is $r=4$. Then $a=10-4\cos0^\circ=6$ and $b=6-4\sin0^\circ=6$. Vote for the centre $(6,6)$. (If the gradient points the other way, vote at $(14,6)$. The sign of the gradient depends on the dark-to-bright orientation.)
Generalized Hough transform (GHT)
The GHT finds arbitrary shapes. It extends the circle idea. For each border pixel, store where the shape's centre is relative to that pixel. Index this by the local edge direction.
Preprocessing (build the model):
- Run a gradient-based edge detector. Each border pixel gets an edge position and an orientation $\phi$.
- Choose an arbitrary reference point $C=(x_c,y_c)$ as the centre of the shape.
- For each border pixel, record the distance $r$ and direction $\alpha$ to $C$. Store them in the $\phi$-table (R-table), indexed by edge direction.
| Edge direction $\phi$ | Stored vectors $\bar r=(r,\alpha)$ |
|---|---|
| $\phi_1$ | $\bar r_1^1,\ \bar r_2^1,\ \bar r_3^1$ |
| $\phi_2$ | $\bar r_1^2,\ \bar r_2^2$ |
| $\vdots$ | $\vdots$ |
| $\phi_n$ | $\bar r_1^n,\ \bar r_2^n$ |
Several vectors can share one $\phi$, because different boundary points can have the same edge direction.
Detection algorithm:
- Create accumulator $A(x_c,y_c)=0$ for all $(x_c,y_c)$.
- For each edge point $(x_i,y_i,\phi_i)$ in the image, find row $\phi_i$ in the table. For each stored entry $(r_k^i,\alpha_k^i)$, compute $$ x_c = x_i + r_k^i\cos\alpha_k^i,\qquad y_c = y_i + r_k^i\sin\alpha_k^i $$ and add 1 to $A(x_c,y_c)$.
- Find the local maxima in $A(x_c,y_c)$. Each maximum is an object centre.
Add a new dimension to the accumulator for each scale $s$ or rotation $\theta$ of the object (so $A(x_c,y_c,s,\theta)$). For this reason, HT is expensive for complex shapes.
HT conclusion
- HT is fairly insensitive to occlusion and noise. It can handle discontinuities (broken edges).
- HT is very effective on simple shapes (lines, circles).
- Each extra parameter (radius, scale, rotation) adds an accumulator dimension. This increases memory and time.
These topics often come in the exam: (1) why $\rho$-$\theta$ instead of $m$-$c$ (vertical lines, bounded space); (2) steps of the HT algorithm; (3) accumulator size trade-off; (4) circle HT dimensions (2D known radius, 3D unknown); (5) single vs complete link numerical with dendrogram; (6) watershed numerical with labelled steps.
Quick self-test
1. Define regional minimum, catchment basin and watershed line.
Regional minimum: a pixel (or flat patch) lower than all its neighbours. Catchment basin: the set of pixels that drain into that minimum. Watershed line: the boundary (dam) between two catchment basins, where the floods from two valleys would merge.
2. Run watershed on the 1D row 5, 2, 4, 7, 3, 1, 6 (positions 1 to 7).
Minima: position 2 (value 2) and position 6 (value 1). Level 1: B at pos 6. Level 2: A at pos 2. Level 3: pos 5 touches B, so B. Level 4: pos 3 touches A, so A. Level 5: pos 1 touches A, so A. Level 6: pos 7 touches B, so B. Level 7: pos 4 touches A (pos 3) and B (pos 5) together, so W. Result for positions 1 to 7: A A A W B B B.
3. Single-link on pixels with intensities 5, 7, 14. Give merge order and heights.
Distances: 5-7 = 2, 5-14 = 9, 7-14 = 7. Merge {5,7} at 2. Then $D=\min(9,7)=7$; merge all at 7. Heights 2, 7. (Complete link would give 2, then $\max(9,7)=9$.)
4. Why does single link produce "chaining" while complete link does not?
Single link needs only one close pair. A chain of closely spaced points joins the cluster one at a time and makes a long, thin cluster. Complete link needs all pairs to be close. It merges only clusters whose farthest members are still near. This gives compact clusters of similar diameter.
5. Why is the $\rho$-$\theta$ form preferred over $y=mx+c$ for the Hough transform?
The slope $m$ ranges over $(-\infty,\infty)$ and cannot represent vertical lines. The accumulator cannot be finite. In $\rho=x\cos\theta+y\sin\theta$, $\theta$ has a bounded range and the image diagonal bounds $\rho$. A finite accumulator then covers every line, including vertical lines.
6. A point in image space maps to what in (a) m-c space, (b) ρ-θ space, (c) circle HT with known radius, (d) circle HT using gradient direction?
(a) a straight line $c=-x_i m+y_i$; (b) a sinusoid; (c) a circle of radius $r$ in $(a,b)$ space; (d) a single point $(x_i-r\cos\phi_i,\ y_i-r\sin\phi_i)$.
7. What happens if the accumulator cells are too small, or too large?
Too small: the votes from one real line split across several cells. The peak is weak and noise can cause missed lines. Too big: distinct nearby lines fall in the same cell and merge. The accuracy is poor.
8. What is the accumulator dimension for circles when the radius is unknown, and for the Generalized HT with unknown scale and rotation?
Circle with unknown radius: 3D, $A(a,b,r)$. GHT: the base accumulator is 2D, $A(x_c,y_c)$. Unknown scale adds one dimension and unknown rotation adds one more. The result is 4D.
9. Points (2,0), (2,1), (2,3) lie on a vertical line. Show how the ρ-θ HT detects it with θ in {0°, 90°}.
$\theta=0^\circ$: $\rho=x\cos0+y\sin0 = x = 2$ for all three points, so cell $(\theta,\rho)=(0^\circ,2)$ gets 3 votes. $\theta=90^\circ$: $\rho=y=0,1,3$, one vote each. The peak is at $(0^\circ,2)$, meaning the line $x=2$. m-c space cannot represent this line.
- Watershed: grayscale = topography; minima are seeds; flood by level; assign pixels to the touching basin; pixels reached by two basins at once become the watershed line. Plain watershed over-segments, so use markers or smoothing.
- Hierarchical (agglomerative) clustering: merge the closest two clusters repeatedly; record heights; draw a dendrogram. Single link uses min (chaining), complete link uses max (compact). Always rebuild the matrix after each merge.
- Worked data: intensities 10, 12, 18, 25, 40; single heights 2, 6, 7, 15; complete heights 2, 7, 15, 30.
- Hough transform: each edge pixel votes for all shapes it could be on; peaks in the accumulator are the shapes. Works with gaps, partial visibility and noise.
- Lines: $y=mx+c$ gives line-per-point in $(m,c)$ space but fails for vertical lines; use $\rho=x\cos\theta+y\sin\theta$ (point becomes sinusoid, bounded space).
- Circles: $(x-a)^2+(y-b)^2=r^2$; 2D accumulator for known $r$, 3D for unknown $r$; gradient direction reduces the vote to a single point $a=x-r\cos\phi,\ b=y-r\sin\phi$.
- Generalized HT: $\phi$-table stores vectors $(r,\alpha)$ to a reference point; vote $x_c=x+r\cos\alpha,\ y_c=y+r\sin\alpha$. Scale and rotation each add an accumulator dimension.