Segmentation & clustering
Segmentation answers the question "which pixels belong together?". This page treats it as clustering. It covers Gestalt grouping, background subtraction, shot detection, agglomerative and divisive clustering, and k-means by hand. It ends with graph methods: normalized cut and spectral clustering.
What is segmentation?
Image segmentation divides a digital image into distinct regions (groups of pixels). This makes the image easier to analyse. You get a few meaningful chunks, such as sky, road and car, instead of a million pixels.
The natural view is to decide which components of a data set "belong together". This is clustering. So segmentation is clustering of pixels (or of other tokens such as frames, edges and motion vectors).
Two flavours of clustering
| Partitioning | Grouping | |
|---|---|---|
| Starting point | A large data set that you carve up | A set of distinct items you collect into sets |
| Goal | Decompose into pieces that are "good" according to a model | Collect items that "make sense" together according to a model |
| Examples | Split an image into regions of coherent colour and texture; split a video into shots; split a video into motion blobs (coherent colour, texture and motion) | Collect tokens that together form an interesting object; collect tokens that move together |
| Difficulty | Choosing a good model | Occlusion separates parts of the same object, so they are far apart in the image |
Human vision: Gestalt grouping
Gestalt psychologists (Gestalt means "whole form") noticed that humans see wholes, not isolated dots. They listed the factors that make a set of elements predisposed to be grouped. The slides first show two illusions: the triangle with a circular hole, and the vase / two-faces picture. In the vase picture you see a vase (figure) or two faces, but not both at once. The brain must decide what is figure and what is background. The Müller-Lyer lines (arrow heads in and out) look different in length, but they are equal. This shows that grouping and context change perception.
Gestalt factors (from the slides)
| Factor | Tokens tend to be grouped when... |
|---|---|
| Proximity | they are nearby |
| Similarity | they look alike (colour, size, shape) |
| Common fate | they have coherent motion |
| Common region | they lie inside the same closed region |
| Parallelism | they are parallel curves or tokens |
| Closure | grouping them leads to closed curves |
| Symmetry | the curves give symmetric groups |
| Continuity | they "join up nicely" into smooth curves (not formal continuity) |
| Familiar configuration | grouping them yields a familiar object |
Exam favourite: "List and explain the Gestalt factors". Give each factor one line and an example. The slide's picture groups them in two columns. Left: proximity, similarity (two types), common fate, common region. Right: parallelism, symmetry, continuity, closure.
Application: background subtraction
The goal is to report the moving foreground in video from a static camera. Keep an estimate of the empty background. Subtract it from each frame. Flag the pixels that differ by a large amount.
Algorithm. Form a background estimate $\mathcal B^{(0)}$. At each frame $\mathcal F$:
- Update the background: $$\mathcal B^{(n+1)}=\frac{w_a\mathcal F+\sum_i w_i\,\mathcal B^{(n-i)}}{w_c}$$
- Subtract the background from the frame. Report each pixel where $|\mathcal F-\mathcal B|>$ threshold.
$w_a$ is the weight of the current frame. $w_i$ are the weights of earlier background estimates. $w_c$ is the normalising constant (normally $w_c=w_a+\sum w_i$), so the update is a weighted average. A large $w_a$ adapts fast, but it absorbs slow movers into the background.
Numerical. Use $w_a=1$ and one previous estimate with $w_1=3$, so $w_c=4$ and $\mathcal B^{new}=(\mathcal F+3\mathcal B)/4$. The threshold is $T=20$. Background row $\mathcal B=[100,100,100,100]$, frame $\mathcal F=[102,101,160,99]$.
Differences $|\mathcal F-\mathcal B|=[2,1,60,1]$. Only pixel 3 exceeds 20, so it is foreground.
Updated background: $[(102+300)/4,\,(101+300)/4,\,(160+300)/4,\,(99+300)/4]=[100.5,\,100.25,\,115,\,99.75]$. If the object stays, pixel 3 slowly moves toward 160. Then it becomes "background".
Application: shot boundary detection
A shot is a short sub-sequence of a video that shows largely the same objects. The editing process makes it. A key frame can summarise each shot. Shot boundary detection finds the shot boundaries automatically.
Algorithm. For each frame in the sequence, compute a distance between this frame and the previous frame. If the distance is larger than a threshold, classify the frame as a shot boundary.
The slides give these ways to compute the distance:
- Frame differencing: take pixel-by-pixel differences between two frames and sum the squares of the differences.
- Histogram based: compute a colour histogram per frame and measure the distance between the histograms. Small object motion does not change it much.
- Block comparison: cut frames into a grid of boxes and compare the boxes.
- Edge differencing: compute an edge map for each frame. Count the potentially corresponding edges (nearby, similar orientation) in the next frame.
Numerical (frame differencing). Frame 1 $=\begin{bmatrix}10&10\\10&10\end{bmatrix}$, frame 2 $=\begin{bmatrix}12&10\\10&14\end{bmatrix}$. Differences: $2,0,0,4$. $D=\sum(\Delta)^2=4+0+0+16=20$. With threshold 1000, $20<1000$, so there is no cut.
Numerical (histogram distance, L1). The histograms have 4 bins. Within a shot: $h_1=[10,20,30,40]$, $h_2=[12,18,28,42]$, $d=2+2+2+2=8$ (small). Across a cut: $h_1=[90,10,0,0]$, $h_3=[0,0,10,90]$, $d=90+10+10+90=200$ (large), so the system declares a boundary.
Image segmentation by clustering
Clustering replaces a data set by clusters. A cluster is a collection of points that "belong together". In an image, each pixel becomes a point with a feature vector. The vector can hold intensity, $(R,G,B)$ colour, texture responses or position $(x,y)$. There are two simple strategies:
- Divisive (top-down): treat the whole data set as one cluster. Then split it recursively into a good clustering.
- Agglomerative (bottom-up): treat every data item as its own cluster. Then merge clusters recursively.
Agglomerative algorithm
Make each point a separate cluster.
Until the clustering is satisfactory: merge the two clusters with the smallest inter-cluster distance.
End.
Divisive algorithm (the mirror image): start with one cluster that holds everything. Until the clustering is satisfactory, split the cluster that gives the greatest improvement. (The slide's "Divisive" page repeats the agglomerative pseudo-code by mistake. The concept is top-down splitting.)
Major issues
1. What is a good inter-cluster distance? There are three ways to define the distance between two clusters:
| Linkage | Definition | Behaviour |
|---|---|---|
| Single-link | distance between the closest elements: $d(A,B)=\min_{a\in A,b\in B}d(a,b)$ | Can chain together long thin clusters; sensitive to noise bridges |
| Complete-link | the maximum distance between an element of one cluster and one of the other: $\max d(a,b)$ | Compact, roughly equal-sized clusters |
| Average-link | the average of all pairwise distances: $\frac{1}{|A||B|}\sum d(a,b)$ | Compromise between the two |
2. How many clusters are there? The agglomerative segmenter stops merging when the distance between clusters is low enough. It also stops when the number of clusters reaches a chosen value.
Dendrogram
A dendrogram is the tree that records the merge history of agglomerative clustering. The leaves are the data points. The vertical axis is the inter-cluster distance at which two clusters merged. To get a clustering, cut the tree with a horizontal line at some height. The number of vertical lines it crosses is the number of clusters. The slide shows 6 points. Points 1, 2 and 3 on the right side merge first (1 with 2, then 3). Points 4, 5 and 6 form another group. The two groups join at the top.
Worked example: single versus complete link. Four 1-D points $A=0$, $B=1$, $C=3$, $D=5.5$.
Pairwise distances: $AB=1$, $BC=2$, $CD=2.5$, $AC=3$, $BD=4.5$, $AD=5.5$.
Single link. Step 1: the smallest distance is $AB=1$. Merge $\{A,B\}$ at height 1. Step 2: $d(\{AB\},C)=\min(AC,BC)=\min(3,2)=2$ and $d(C,D)=2.5$. Merge $\{A,B\}$ with $C$ at height 2. Step 3: $d(\{ABC\},D)=\min(AD,BD,CD)=2.5$. Merge at 2.5. The chain is $((A,B),C),D)$ with heights 1, 2, 2.5.
Complete link. Step 1: $AB=1$. Merge. Step 2: $d(\{AB\},C)=\max(3,2)=3$, $d(C,D)=2.5$ and $d(\{AB\},D)=5.5$. The smallest is $CD=2.5$. Merge $\{C,D\}$ at 2.5. Step 3: $d(\{AB\},\{CD\})=\max(AC,AD,BC,BD)=5.5$. Merge at 5.5. The tree is $((A,B),(C,D))$ with heights 1, 2.5, 5.5.
Cut for 2 clusters. Single link gives $\{A,B,C\},\{D\}$. Complete link gives $\{A,B\},\{C,D\}$. The data is the same, but the clusters are different.
Remember: single link = min distance (closest pair), complete link = max (farthest pair). Students often swap them. Memory aid: complete link needs every pair to be close, so you look at the worst pair.
K-means clustering and segmentation
K-means needs the number of clusters $k$ in advance. It repeats two steps. First, assign every point to its nearest centre. Then move each centre to the mean of its points.
Algorithm (slide). Choose $k$ data points to act as cluster centres. Until the cluster centres do not change:
- Allocate each data point to the cluster whose centre is nearest.
- Make sure every cluster has at least one data point. To fix an empty cluster, give it a random point far from its centre.
- Replace the cluster centres with the mean of the elements in their clusters.
$C_j$ = cluster $j$, $\mu_j$ = its centre (mean), $J$ = total within-cluster squared distance. K-means never increases this value, so it converges (to a local minimum).
Worked example (1-D, $k=2$). Data: $2,3,4,10,11,12,20,25,30$. Initial centres $c_1=2$, $c_2=4$.
Iteration 1. Distances to $(2,4)$: $2\to c_1$. The value $3$ is 1 from each centre (tie), so give it to $c_1$. Then $4\to c_2$. Every value $\ge10$ is closer to 4. $C_1=\{2,3\}$, $C_2=\{4,10,11,12,20,25,30\}$. New centres: $2.5$ and $112/7=16$.
Iteration 2 (centres 2.5, 16). $2,3,4\to c_1$ (4 is 1.5 from the first centre and 12 from the second). For $10$: $7.5$ vs $6\to c_2$. $11,12,20,25,30\to c_2$. $C_1=\{2,3,4\}$, mean $3$. $C_2=\{10,11,12,20,25,30\}$, mean $108/6=18$.
Iteration 3 (centres 3, 18). For $10$: $7$ vs $8\to c_1$. For $11$: $8$ vs $7\to c_2$. $C_1=\{2,3,4,10\}$, mean $4.75$. $C_2=\{11,12,20,25,30\}$, mean $98/5=19.6$.
Iteration 4 (centres 4.75, 19.6). For $11$: $6.25$ vs $8.6\to c_1$. For $12$: $7.25$ vs $7.6\to c_1$. $20,25,30\to c_2$. $C_1=\{2,3,4,10,11,12\}$, mean $42/6=7$. $C_2=\{20,25,30\}$, mean $25$.
Iteration 5 (centres 7, 25). For $12$: $5$ vs $13\to c_1$. For $20$: $13$ vs $5\to c_2$. Nothing changes, so stop.
Result: clusters $\{2,3,4,10,11,12\}$ with centre 7 and $\{20,25,30\}$ with centre 25. The poor initial centres caused the extra iterations. K-means depends on initialisation.
Practice (2-D, $k=2$). Points $P_1(1,1)$, $P_2(2,1)$, $P_3(4,3)$, $P_4(5,4)$. Start with $c_1=P_1$, $c_2=P_4$. Use squared Euclidean distance.
$P_2$: to $c_1$: $1$; to $c_2$: $9+9=18\to c_1$. $P_3$: to $c_1$: $9+4=13$; to $c_2$: $1+1=2\to c_2$. New centres: $c_1=(1.5,1)$, $c_2=(4.5,3.5)$. Re-assign: $P_1$ stays with $c_1$ (0.25 vs 18.5), $P_2$ with $c_1$, $P_3$ with $c_2$ ($0.25+0.25=0.5$ vs $c_1$: $6.25+4=10.25$), $P_4$ with $c_2$. No change, so it has converged: $\{P_1,P_2\}$, $\{P_3,P_4\}$.
K-means for segmentation. Use the pixel feature vector: intensity for a grey image, $(R,G,B)$ for a colour image. You can add $(x,y)$ to make the clusters spatially coherent. Cluster all pixels. Then paint each pixel with its cluster centre. The slide shows a vegetable image reduced to a few grey levels and to a few colours. Every pixel is assigned, so the output is a quantised image. The clusters do not have to be connected regions.
| Strengths | Weaknesses |
|---|---|
| Simple, fast, easy to implement | Must choose $k$ in advance |
| Converges | Local minimum, depends on initial centres |
| Works for compact, round clusters | Sensitive to outliers; poor for elongated or non-convex clusters; ignores spatial connectivity unless $(x,y)$ is a feature |
Agglomerative versus k-means: agglomerative builds a whole hierarchy (dendrogram). It needs a linkage rule, but it does not need $k$ in advance (you choose where to cut). K-means gives one flat partition. It needs $k$ and initial centres.
Segmentation by graph-theoretic clustering
Treat the image as a graph. Then segmentation is the cutting of the graph. The slides list these terms:
- Graph $G=(V,E)$: vertices (nodes) $V$ and edges $E$ that join pairs of vertices. Here the vertices are pixels (or tokens).
- Directed graph: edges have a direction ($i\to j$). Undirected graph: edges have no direction (the usual case for similarity).
- Weighted graph: each edge has a number $w_{ij}$. Here the weight shows how strongly two pixels belong together. It is called the affinity.
- Self loop: an edge from a vertex to itself (its weight is the self-affinity, 1).
- Connected graph: a path exists between every pair of vertices. Connected component: a maximal connected subgraph. If you delete the weak edges, the connected components are the segments.
The weights are stored in a symmetric affinity matrix $W$ with $W_{ij}=\mathrm{aff}(i,j)$.
Affinity measures
All affinity measures use a Gaussian. The affinity is 1 when two items are identical. It falls toward 0 as they differ. $\sigma$ sets how fast it falls (a small $\sigma$ means that only very similar items have a high affinity).
| Affinity by | Formula | Symbols |
|---|---|---|
| Distance | $\exp\!\big\{-\dfrac{(\mathbf x-\mathbf y)^T(\mathbf x-\mathbf y)}{2\sigma_d^2}\big\}$ | $\mathbf x,\mathbf y$ pixel positions; $\sigma_d$ spatial scale |
| Intensity | $\exp\!\big\{-\dfrac{(I(\mathbf x)-I(\mathbf y))^T(I(\mathbf x)-I(\mathbf y))}{2\sigma_I^2}\big\}$ | $I(\cdot)$ intensity; $\sigma_I$ intensity scale |
| Colour | $\exp\!\big\{-\dfrac{\mathrm{dist}(\mathbf c(\mathbf x),\mathbf c(\mathbf y))^2}{2\sigma_c^2}\big\}$ | $\mathbf c(\cdot)$ colour vector; dist a colour distance |
| Texture | $\exp\!\big\{-\dfrac{(\mathbf f(\mathbf x)-\mathbf f(\mathbf y))^T(\mathbf f(\mathbf x)-\mathbf f(\mathbf y))}{2\sigma_t^2}\big\}$ | $\mathbf f(\cdot)$ filter-response (texture) vector. (The slide writes the scale as $\sigma_I$.) |
| Motion | $\exp\!\Big(-\dfrac{1}{2\sigma_m^2}\Big\{1-\sum_{\mathbf v}P(\mathbf v,\mathbf x;\sigma_d)\,P(\mathbf v,\mathbf y;\sigma_d)\Big\}\Big)$ | $P(\mathbf v,\mathbf x;\sigma_d)$ = probability that the point at $\mathbf x$ has velocity $\mathbf v$ (estimated over a neighbourhood of scale $\sigma_d$). Identical velocity distributions give the sum 1, so the affinity is 1. |
Numerical. Distance affinity with $\sigma_d=5$. Pixels $\mathbf x=(0,0)$ and $\mathbf y=(3,4)$: $d^2=25$, aff $=e^{-25/50}=e^{-0.5}=0.607$. A nearer pixel $\mathbf y'=(1,1)$: $d^2=2$, aff $=e^{-2/50}=e^{-0.04}=0.961$.
Intensity affinity with $\sigma_I=10$: $I(\mathbf x)=100$, $I(\mathbf y)=120$: $(20)^2/(2\cdot100)=2$, aff $=e^{-2}=0.135$. If $I(\mathbf y)=104$: $16/200=0.08$, aff $=0.923$. Nearby and similar pixels get a weight near 1, so they stay linked.
Eigenvectors and segmentation
Algorithm (slide). Construct an affinity matrix. Compute its eigenvalues and eigenvectors. Repeat the following steps until there are enough clusters:
- Take the eigenvector of the largest unprocessed eigenvalue.
- Set to zero all components for elements that are already in a cluster.
- Threshold the remaining components to decide which elements belong to this cluster. Fix the threshold in advance, or choose it by clustering the components.
- If all elements are in a cluster, stop.
If the data has $k$ tight groups, the affinity matrix is nearly block-diagonal. Each block gives a large eigenvalue. Its eigenvector is large on the members of that block and about 0 elsewhere. A threshold on the eigenvector picks out one group.
Worked example. Five elements. Elements 1,2,3 are mutually affine (all 1). Elements 4,5 are mutually affine (all 1). There is no affinity between the groups:
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 |
Eigenvalues: $3$ with eigenvector $\tfrac1{\sqrt3}(1,1,1,0,0)$
$2$ with $\tfrac1{\sqrt2}(0,0,0,1,1)$; the others are 0.
Take the largest eigenvalue, 3. The components are $(0.58,0.58,0.58,0,0)$. Use a threshold of, for example, 0.3. Elements 1,2,3 form cluster 1. Set them to zero. The next largest unprocessed eigenvalue is 2. The components are $(0,0,0,0.71,0.71)$, so elements 4,5 form cluster 2. All 5 elements are in a cluster, so there are 2 clusters.
Normalized cut (Ncut)
Normalized cut is a graph-partitioning criterion for spectral clustering and image segmentation (Shi and Malik). Split the graph with vertex set $V$ into two groups $A$ and $B$.
This is the total weight of the edges that the split cuts ($w_{ij}$ = edge weight = affinity).
Problem. Minimising Cut alone is biased. If one isolated pixel has a single weak edge, cutting it off gives a tiny cut value. The result is tiny, useless segments.
Association is the total connection of a cluster to the whole graph (it includes the internal edges). It measures the "size" of the cluster.
$$\mathrm{Ncut}(A,B)=\frac{\mathrm{Cut}(A,B)}{\mathrm{Assoc}(A,V)}+\frac{\mathrm{Cut}(A,B)}{\mathrm{Assoc}(B,V)}$$The division by association punishes tiny clusters. Their Assoc is small, so the ratio becomes large. A small Ncut means three things: strong connections within clusters, weak connections between clusters and balanced partition sizes.
Worked Ncut example. Edges: triangles $\{1,2,3\}$ and $\{4,5,6\}$ with all weights 4; bridge $w_{34}=2$; pendant $w_{67}=1$. Node degrees: $d_1=d_2=8$, $d_3=10$, $d_4=10$, $d_5=8$, $d_6=9$, $d_7=1$. Total $=54$.
Cut A = {7}, B = rest. Cut $=1$. Assoc$(A)=1$, Assoc$(B)=53$. Ncut $=1/1+1/53=1.019$.
Cut A = {1,2,3}, B = {4,5,6,7}. Cut $=2$. Assoc$(A)=8+8+10=26$, Assoc$(B)=54-26=28$. Ncut $=2/26+2/28=0.077+0.071=0.148$.
Min-cut picks the pendant node (cut 1 < 2). This is a useless segment. Ncut is much smaller for the bridge cut, and it gives the two natural clusters.
Matrix formulation and spectral clustering
Let $W$ = similarity (affinity) matrix and $D$ = degree matrix, diagonal with $D_{ii}=\sum_j W_{ij}$. After relaxation, the minimisation of Ncut becomes:
$$(D-W)\,\mathbf y=\lambda D\,\mathbf y\quad\Longleftrightarrow\quad L\mathbf y=\lambda D\mathbf y,\qquad L=D-W$$$L$ is the graph Laplacian. $\mathbf y$ is an indicator-like vector over the nodes. $\lambda$ is the eigenvalue. This is a generalized eigenvalue problem.
Spectral clustering using Ncut (slide steps):
- Construct the similarity matrix $W$.
- Compute the degree matrix $D$.
- Compute the Laplacian $L=D-W$.
- Solve $(D-W)\mathbf y=\lambda D\mathbf y$.
- Choose the eigenvector with the second smallest eigenvalue. (The smallest is $\lambda=0$ with the constant vector. It has no split information.)
- Partition the nodes by the sign of the entries (or by k-means on the eigenvectors).
Worked spectral example. Path graph $1-2-3-4$ with $w_{12}=2$, $w_{23}=1$, $w_{34}=2$.
$$W=\begin{bmatrix}0&2&0&0\\2&0&1&0\\0&1&0&2\\0&0&2&0\end{bmatrix},\;D=\mathrm{diag}(2,3,3,2),\;L=\begin{bmatrix}2&-2&0&0\\-2&3&-1&0\\0&-1&3&-2\\0&0&-2&2\end{bmatrix}$$By symmetry, the splitting vector is antisymmetric: $\mathbf y=(p,q,-q,-p)$. Row 1 of $L\mathbf y=\lambda D\mathbf y$: $2p-2q=2\lambda p\Rightarrow q=(1-\lambda)p$. Row 2: $-2p+3q+q=3\lambda q\Rightarrow(4-3\lambda)q=2p$. Substitute: $(4-3\lambda)(1-\lambda)=2\Rightarrow3\lambda^2-7\lambda+2=0\Rightarrow\lambda=\tfrac13$ or $2$.
The symmetric solutions give $\lambda=0$ and $\tfrac53$. So the eigenvalues are $0,\tfrac13,\tfrac53,2$. The second smallest is $\tfrac13$, with $q=\tfrac23p$, that is $\mathbf y\propto(3,2,-2,-3)$.
The signs are: $\{1,2\}$ positive and $\{3,4\}$ negative. The partition is $A=\{1,2\}$, $B=\{3,4\}$. It cuts the weak edge. Check Ncut: Cut $=1$, Assoc$(A)=2+3=5$, Assoc$(B)=5$, Ncut $=1/5+1/5=0.4$.
Do not confuse the two eigenvector methods. The plain eigenvector method (slide 27) uses the largest eigenvalues of the affinity matrix $W$. Ncut spectral clustering uses the second smallest eigenvalue of the Laplacian generalized problem $(D-W)\mathbf y=\lambda D\mathbf y$. Both methods end with a threshold or k-means on the eigenvector entries.
Quick self-test
1. List the Gestalt grouping factors with one example each.
Proximity (nearby dots form pairs), similarity (same colour/shape grouped), common fate (dots moving the same way), common region (dots inside one closed outline), parallelism (parallel curves), closure (curves that form a closed shape), symmetry (mirror-image curves), continuity (curves that join smoothly), familiar configuration (a grouping that makes a known object).
2. Describe the background subtraction algorithm. Numerically: $\mathcal B=120$, $\mathcal F=150$, $w_a=1$, $w_1=3$, $T=20$.
Estimate the background and subtract it from each frame. Report the pixels with $|\mathcal F-\mathcal B|>T$. Then update $\mathcal B^{n+1}=(w_a\mathcal F+\sum w_i\mathcal B^{n-i})/w_c$. Here $|150-120|=30>20$, so the pixel is foreground. New background $=(150+3\cdot120)/4=127.5$.
3. Explain shot boundary detection and name four ways to compute frame distance.
A shot is a sub-sequence that shows the same objects. To find its boundaries, compute a distance between consecutive frames. Flag a boundary when the distance exceeds a threshold. The four distances are frame differencing (sum of squared pixel differences), colour histogram distance, block comparison (grid of boxes) and edge differencing (matching edges in edge maps).
4. Differentiate agglomerative and divisive clustering, and single, complete and average link.
Agglomerative is bottom-up. Every point starts as a cluster, and the two closest clusters merge repeatedly. Divisive is top-down. One cluster is split recursively. Single link uses the minimum pairwise distance (chaining). Complete link uses the maximum (compact clusters). Average link uses the mean of all pairwise distances.
5. Numerical: points $1,2,6,9$ on a line. Do single-link agglomerative clustering and give merge heights.
Distances: $1\text{-}2=1$, $6\text{-}9=3$, $2\text{-}6=4$, $1\text{-}6=5$, $2\text{-}9=7$, $1\text{-}9=8$. Merge $\{1,2\}$ at 1. Then merge $\{6,9\}$ at 3 (smaller than $d(\{1,2\},6)=4$). Last, merge $\{1,2\}$ with $\{6,9\}$ at $\min(4,5,7,8)=4$. Heights: 1, 3, 4.
6. Numerical: k-means with $k=2$ on $1,2,9,10$, initial centres $1$ and $2$.
Iteration 1: $1\to c_1$; $2\to c_2$; $9,10\to c_2$. $C_1=\{1\}$ mean 1; $C_2=\{2,9,10\}$ mean 7. Iteration 2: for $2$: $1$ vs $5\to c_1$; $9,10\to c_2$. $C_1=\{1,2\}$ mean 1.5; $C_2=\{9,10\}$ mean 9.5. Iteration 3: no change. Result $\{1,2\},\{9,10\}$, centres $1.5$ and $9.5$.
7. Write the Gaussian affinity by intensity and compute it for $I(x)=50$, $I(y)=60$, $\sigma_I=5$.
$\mathrm{aff}=\exp\{-(I(x)-I(y))^2/2\sigma_I^2\}=\exp\{-100/50\}=e^{-2}=0.135$.
8. Why is minimum cut a poor segmentation criterion? How does Ncut fix it?
Min cut prefers to cut off small isolated groups. They have very few connections, so the cut value is small. Ncut divides the cut by the association of each side with the whole graph. This association is small for tiny groups, so the ratio becomes large. Balanced partitions win.
9. State the Ncut formula and the spectral algorithm.
$\mathrm{Ncut}(A,B)=\mathrm{Cut}/\mathrm{Assoc}(A,V)+\mathrm{Cut}/\mathrm{Assoc}(B,V)$. Algorithm: build $W$, $D$ and $L=D-W$. Solve $(D-W)\mathbf y=\lambda D\mathbf y$. Take the eigenvector of the second smallest eigenvalue. Split the nodes by sign or with k-means.
10. Compute Ncut for a graph with $\mathrm{Cut}(A,B)=6$, $\mathrm{Assoc}(A,V)=30$, $\mathrm{Assoc}(B,V)=20$.
$6/30+6/20=0.2+0.3=0.5$.
- Segmentation = grouping pixels that belong together = clustering (partitioning or grouping).
- Gestalt factors: proximity, similarity, common fate, common region, parallelism, closure, symmetry, continuity, familiar configuration.
- Background subtraction: weighted-average background update, flag $|\mathcal F-\mathcal B|>T$.
- Shot boundaries: a frame distance above a threshold (frame difference, histogram, block, edge).
- Agglomerative = bottom-up merge. Divisive = top-down split.
- Linkage: single = min, complete = max, average = mean. A dendrogram shows the merge history. Cut it to get the number of clusters.
- K-means: choose $k$ centres, assign points to the nearest centre, recompute the means and repeat until stable. It finds a local minimum and depends on initialisation and $k$.
- Graph clustering: pixels are nodes and Gaussian affinities (distance, intensity, colour, texture, motion) are weights. Eigenvectors of $W$ show the groups.
- $\mathrm{Ncut}=\mathrm{Cut}/\mathrm{Assoc}(A,V)+\mathrm{Cut}/\mathrm{Assoc}(B,V)$ does not isolate tiny nodes.
- Solve Ncut with $(D-W)\mathbf y=\lambda D\mathbf y$. Take the second smallest eigenvector and split by sign.