Discontinuities & region growing
There are two ways to segment an image. The first looks for abrupt intensity changes (points, lines, edges) with small masks. The second grows and splits regions of similar pixels. On this page you compute mask responses by hand, run region growing on a grid, and do split-and-merge on 4×4 and 8×8 images.
Detection of discontinuities
There are three kinds of intensity discontinuity: points, lines and edges. To find them, slide a small mask (a kernel, normally 3×3) over the image. At each position, the response is the sum of products. Each product is a mask coefficient times the pixel under it:
$w_k$ = mask coefficients, $z_k$ = intensities of the 3×3 neighbourhood. The mask determines which kind of discontinuity the system detects. The coefficients of detection masks sum to 0, so a flat region gives $R=0$.
Point detection
An isolated point is very different from all eight neighbours. The mask below is "centre minus neighbours". A pixel is a point if $|R|\ge T$, where $T$ is a non-negative threshold.
| -1 | -1 | -1 |
| -1 | 8 | -1 |
| -1 | -1 | -1 |
Numerical. Threshold $T=100$. Patch with a bright isolated pixel:
| 10 | 10 | 10 |
| 10 | 50 | 10 |
| 10 | 10 | 10 |
$R=8(50)-(8\times10)=400-80=320$. $|R|=320\ge100$, so it is a point.
A flat patch of all 10s gives $R=80-80=0<T$. It is not a point. Now take a pixel on a straight edge, for example columns $10,10,50$ repeated in all rows, with centre 10. Then $R=8(10)-(10\cdot5+50\cdot3)=80-200=-120$ and $|R|=120$. This also exceeds $T=100$. So choose a high $T$, or use the mask only for truly isolated points.
Line detection
Line detection is a little more common than point detection. It finds a line one pixel wide. In a digital image, a 3-point straight line can only be horizontal, vertical or diagonal ($+45^\circ$, $-45^\circ$). So there are four masks. Each mask has a line of 2s on a background of -1s.
| -1 | -1 | -1 |
| 2 | 2 | 2 |
| -1 | -1 | -1 |
| -1 | -1 | 2 |
| -1 | 2 | -1 |
| 2 | -1 | -1 |
| -1 | 2 | -1 |
| -1 | 2 | -1 |
| -1 | 2 | -1 |
| 2 | -1 | -1 |
| -1 | 2 | -1 |
| -1 | -1 | 2 |
The masks are, from left to right: horizontal, $+45^\circ$, vertical, $-45^\circ$. Run all four masks at a pixel to get $R_1,R_2,R_3,R_4$. If $|R_k|>|R_j|$ for all $j\ne k$, the pixel is more likely on a line in direction $k$. The test $|R_k|\ge T$ confirms it.
Numerical 1 (horizontal line). Patch $\begin{bmatrix}10&10&10\\50&50&50\\10&10&10\end{bmatrix}$. Horizontal mask: row 1: $-30$; row 2: $2\cdot150=300$; row 3: $-30$. $R_H=240$. Vertical mask: each row gives $-a+2b-c$. Row 1: $-10+20-10=0$. Row 2: $-50+100-50=0$. Row 3: $0$. $R_V=0$. Both diagonal masks also give 0. The maximum is $R_H=240$, so the line is horizontal.
Numerical 2 ($+45^\circ$ line). Patch $\begin{bmatrix}10&10&50\\10&50&10\\50&10&10\end{bmatrix}$. The $+45^\circ$ mask puts 2s on the anti-diagonal: $R=2(50+50+50)-(6\times10)=300-60=240$. Horizontal: rows $-70,\,140,\,-70\to0$. Vertical: rows $-40,\,80,\,-40\to0$. $-45^\circ$: $-40,\,80,\,-40\to0$. The winner is $+45^\circ$.
Edge detection
An edge is a set of connected pixels on the boundary between two regions with different intensity. There are two models:
- Ideal (step) edge: the intensity jumps from low to high between adjacent pixels.
- Ramp edge: the intensity changes gradually over several pixels. Real images have ramp edges because of blur and noise. The edge "point" is any point on the ramp. The blur sets the thickness of the ramp.
Derivatives find edges. Look at a horizontal profile:
- The first derivative is non-zero over the ramp and zero in flat areas. Its magnitude is large at an edge.
- The second derivative is positive on the dark side and negative on the bright side. It has a zero crossing in the middle of the edge. The sign shows which side is darker.
First-order derivatives: the gradient
$G_x$ and $G_y$ are the intensity changes along $x$ and $y$. The gradient vector points in the direction of the greatest rate of change of $f$ at $(x,y)$. Its magnitude is that rate. The edge itself runs perpendicular to the gradient. The cheap form $|G_x|+|G_y|$ avoids the square root.
The slide writes the direction as $\tan^{-1}(G_x/G_y)$. The textbook (Gonzalez and Woods) angle, measured from the $x$-axis, is $\tan^{-1}(G_y/G_x)$. Know the difference. Use the form your instructor expects, and state what the angle is measured from.
Roberts, Prewitt and Sobel masks
These masks approximate $G_x$ and $G_y$ with small masks.
| Operator | Size | Masks (the two directions) | Notes |
|---|---|---|---|
| Roberts cross-gradient | 2×2 | $\begin{bmatrix}-1&0\\0&1\end{bmatrix}$ and $\begin{bmatrix}0&-1\\1&0\end{bmatrix}$ | Diagonal differences; very cheap, very noise-sensitive, edge position shifted half a pixel |
| Prewitt | 3×3 | $\begin{bmatrix}-1&-1&-1\\0&0&0\\1&1&1\end{bmatrix}$ and $\begin{bmatrix}-1&0&1\\-1&0&1\\-1&0&1\end{bmatrix}$ | Difference plus equal-weight averaging across 3 rows/columns |
| Sobel | 3×3 | $\begin{bmatrix}-1&-2&-1\\0&0&0\\1&2&1\end{bmatrix}$ and $\begin{bmatrix}-1&0&1\\-2&0&2\\-1&0&1\end{bmatrix}$ | Same, but the centre row/column has weight 2: more smoothing, better noise suppression. Most used. |
In each pair, the first mask (rows differenced, bottom minus top) responds to horizontal edges ($G_y$). The second mask responds to vertical edges ($G_x$). For Roberts, $G_1=z_4-z_1$ and $G_2=z_3-z_2$ on the 2×2 window $\begin{bmatrix}z_1&z_2\\z_3&z_4\end{bmatrix}$.
Diagonal masks (slide 9) rotate the Prewitt and Sobel masks by 45 degrees. They respond to the two diagonal edge directions:
| Prewitt, mask (a) | Prewitt, mask (b) | Sobel, mask (a) | Sobel, mask (b) |
|---|---|---|---|
| $\begin{bmatrix}0&1&1\\-1&0&1\\-1&-1&0\end{bmatrix}$ | $\begin{bmatrix}-1&-1&0\\-1&0&1\\0&1&1\end{bmatrix}$ | $\begin{bmatrix}0&1&2\\-1&0&1\\-2&-1&0\end{bmatrix}$ | $\begin{bmatrix}-2&-1&0\\-1&0&1\\0&1&2\end{bmatrix}$ |
Numerical (Sobel, vertical step edge). Patch with columns $10,10,50$:
| 10 | 10 | 50 |
| 10 | 10 | 50 |
| 10 | 10 | 50 |
$G_x$ (mask $[-1,0,1;-2,0,2;-1,0,1]$): row 1: $-10+50=40$; row 2: $2(-10+50)=80$; row 3: $40$. $G_x=160$.
$G_y$ (mask $[-1,-2,-1;0,0,0;1,2,1]$): the top row gives $-(10+20+50)=-80$ and the bottom row gives $+80$. $G_y=0$.
Magnitude $=\sqrt{160^2+0^2}=160$ (or $|G_x|+|G_y|=160$). Gradient direction $\alpha=\tan^{-1}(0/160)=0^\circ$. It points along $+x$ toward the bright side, so the edge is vertical (perpendicular). Prewitt on the same patch gives $G_x=3(50-10)=120$.
Roberts on $\begin{bmatrix}10&50\\10&50\end{bmatrix}$: $G_1=50-10=40$, $G_2=10-50=-40$. Magnitude $\sqrt{40^2+40^2}=56.6$. The approximation $|G_1|+|G_2|=80$.
Second-order derivative: the Laplacian
The Laplacian is the sum of the second derivatives. It is isotropic (rotation invariant) and it is a scalar (it has no direction). Two common 3×3 masks:
| 0 | -1 | 0 |
| -1 | 4 | -1 |
| 0 | -1 | 0 |
| -1 | -1 | -1 |
| -1 | 8 | -1 |
| -1 | -1 | -1 |
The first mask is the 4-neighbour version (from $f(x+1)+f(x-1)+f(y+1)+f(y-1)-4f$, sign flipped). The second mask is the 8-neighbour version with the diagonals. It is the same mask as the point detector.
1-D check. Profile $10,10,10,50,50,50$. Second difference $f(x+1)-2f(x)+f(x-1)$: at the last 10: $10-20+50=+40$; at the first 50: $10-100+50=-40$. The sign changes from + to - between them. The zero crossing is the edge.
2-D. Patch with a bright centre 50 on 10s: the 4-neighbour mask gives $4(50)-4(10)=160$.
The Laplacian alone has three drawbacks. It is very sensitive to noise, because second derivatives amplify noise. It gives no edge direction. It makes double edges (the + and - lobes). So use it with smoothing and zero-crossing detection. This leads to LoG.
Advanced edge detection: Laplacian of Gaussian (Marr–Hildreth)
Marr and Hildreth said that a good edge operator must first smooth the image. This suppresses noise at a chosen scale. Then the operator takes second derivatives. The operator is $\nabla^2G$: the Laplacian of a Gaussian (LoG). It is also called the Mexican hat function because of its shape. There are two ways to compute it. Convolve with the $\nabla^2G$ mask directly, or smooth with a Gaussian and then apply the Laplacian mask.
First derivatives: $\partial G/\partial x=-\frac{x}{\sigma^2}e^{-(x^2+y^2)/2\sigma^2}$, and similarly for $y$. Differentiate again:
$$\nabla^2G=\left(\frac{x^2}{\sigma^4}-\frac1{\sigma^2}\right)e^{-\frac{x^2+y^2}{2\sigma^2}}+\left(\frac{y^2}{\sigma^4}-\frac1{\sigma^2}\right)e^{-\frac{x^2+y^2}{2\sigma^2}}$$ $$\boxed{\nabla^2G(x,y)=\left(\frac{x^2+y^2-2\sigma^2}{\sigma^4}\right)e^{-\frac{x^2+y^2}{2\sigma^2}}}$$$\sigma$ = standard deviation, the scale of smoothing (a larger $\sigma$ gives a blurrier image and coarser edges). Zero crossings occur where $x^2+y^2=2\sigma^2$, that is, at radius $r=\sqrt2\,\sigma$.
The slide shows the 3-D "sombrero", its cross-section, and a 5×5 integer approximation:
| 0 | 0 | -1 | 0 | 0 |
| 0 | -1 | -2 | -1 | 0 |
| -1 | -2 | 16 | -2 | -1 |
| 0 | -1 | -2 | -1 | 0 |
| 0 | 0 | -1 | 0 | 0 |
Check the sum: the coefficients add to 0 ($-1-4+10-4-1=0$), so a flat region gives 0. This mask is the negative of the formula above, which has a negative centre. The sign flip gives a positive centre (+16) and a negative ring around it.
Numerical. $\sigma=1$. At the origin: $\nabla^2G(0,0)=\frac{-2}{1}e^0=-2$. At $(1,1)$: $x^2+y^2=2=2\sigma^2$, so $\nabla^2G=0$ (zero crossing radius $\sqrt2$). At $(2,0)$: $(4-2)/1\cdot e^{-2}=2(0.1353)=0.27$ (positive outer ring).
Marr–Hildreth steps: (1) Convolve the image with the Gaussian (or directly with the LoG). (2) Apply the Laplacian. (3) Find the zero crossings of the result (optionally, keep those with a strong slope). Zero crossings give thin, closed contours.
Gradient versus Laplacian
| Gradient (Roberts, Prewitt, Sobel) | Laplacian / LoG | |
|---|---|---|
| Derivative order | First | Second |
| Edge is at | Peak of magnitude (needs threshold) | Zero crossing |
| Gives direction | Yes ($\alpha$) | No (scalar) |
| Noise sensitivity | Moderate | High (LoG reduces it with Gaussian smoothing) |
| Edge thickness | Thick (ramp response) | Thin, closed contours |
Thresholding
Thresholding assumes that the intensity range of the objects of interest is different from that of the background. Then a single cut-off separates them.
$f$ = input intensity, $T$ = threshold, $g$ = binary output (1 = object, 0 = background). The histogram of such an image is bimodal (two humps). Put $T$ in the valley. If the histogram has three humps (for example dark background, grey objects, bright objects), use multiple thresholds $T_1<T_2$. Class 0 is $f\le T_1$, class 1 is $T_1<f\le T_2$, and class 2 is $f>T_2$ (slide: histograms with one threshold $T$ and with two, $T_1,T_2$).
Numerical. Image $\begin{bmatrix}12&200\\15&190\end{bmatrix}$, $T=100$ gives $\begin{bmatrix}0&1\\0&1\end{bmatrix}$. A simple rule to choose $T$: if the two hump means are 40 and 200, take $T=(40+200)/2=120$.
Thresholding alone still produces isolated pixels. It ignores connectivity. This motivates region-based methods.
Region-based segmentation
Edges and thresholds sometimes give poor results. Edges have gaps, and thresholds give isolated noisy pixels. Region-based segmentation uses the connectivity of similar pixels. Each region must be uniform, and its pixels must be connected. There are two main approaches: region growing and region splitting.
Basic formulation
Let $R$ be the entire image region. Segmentation partitions $R$ into subregions $R_1,\dots,R_n$ such that:
(a) $\displaystyle\bigcup_{i=1}^{n}R_i=R$ every pixel belongs to some region (complete).
(b) $R_i$ is a connected region, $i=1,\dots,n$.
(c) $R_i\cap R_j=\varnothing$ for all $i\ne j$ regions do not overlap.
(d) $P(R_i)=\text{TRUE}$ for $i=1,\dots,n$ each region satisfies the predicate.
(e) $P(R_i\cup R_j)=\text{FALSE}$ for any adjacent regions $R_i,R_j$ two different neighbours cannot be merged.
$P(R_k)$ is a logical predicate over the pixels of $R_k$. Example: $P(R_k)=\text{TRUE}$ if all pixels in $R_k$ have the same gray level.
Check (a)-(e). Image $\begin{bmatrix}1&1&9\\1&1&9\end{bmatrix}$, $P$ = "range $\le1$". Regions $R_1=\{$left four 1s$\}$, $R_2=\{$two 9s$\}$. (a) The union is the whole image. (b) Each region is connected. (c) The regions are disjoint. (d) The ranges are 0 and 0, so the predicate is TRUE. (e) $R_1\cup R_2$ has range 8, so the predicate is FALSE. This is a valid segmentation.
Region growing
Region growing uses the principle of similarity. A region is coherent if all its pixels are homogeneous in some property (colour, intensity, texture, other statistics). Pick a pixel inside the region of interest. This pixel is the seed. Compare the seed to its neighbours and merge those that match. Repeat. Region growing is a bottom-up grouping of pixels (or subregions) into a bigger region.
- Seed selection: the seeds represent the region of interest. The user normally gives them, but the system can choose them automatically. There can be one seed or many seeds.
- Growing criterion: a similarity criterion. For example, the grey-level difference from the seed (or from the average of the region) is at most a threshold. The region grows when it adds neighbours that share the properties of the seed.
- Termination: stop when no more neighbours satisfy the criterion.
Slide example. A 5×5 grid has two seeds (underlined on the slide): the 1 in row 4, column 2 and the 9 in row 2, column 4. The slide gives no threshold, so use this rule. A neighbour joins if $|\text{pixel}-\text{seed value}|\le T$ with $T=3$. Use 4-connectivity (up, down, left, right).
| 1 | 0 | 7 | 8 | 7 |
| 0 | 1 | 8 | 9 | 8 |
| 0 | 0 | 7 | 9 | 8 |
| 0 | 1 | 8 | 8 | 9 |
| 1 | 2 | 8 | 8 | 9 |
Region A (seed 1 at (4,2)). Neighbours: (3,2)=0 diff 1 ok; (5,2)=2 diff 1 ok; (4,1)=0 ok; (4,3)=8 diff 7 reject. Continue from the new pixels: (3,1)=0, (2,2)=1, (5,1)=1 ok; (3,3)=7 diff 6 reject. Then (2,1)=0, (1,2)=0 ok, then (1,1)=1 ok. Every candidate in column 3 (7, 8, 7, 8, 8) differs from 1 by at least 6. So A stops: columns 1-2, 10 pixels.
Region B (seed 9 at (2,4)). Neighbours: (1,4)=8, (3,4)=9, (2,3)=8, (2,5)=8 all ok (diff 1 or 0). Then (1,3)=7, (1,5)=7, (3,3)=7 (diff 2), (3,5)=8, (4,4)=8, (4,3)=8, (4,5)=9, (5,3)=8, (5,4)=8, (5,5)=9 all ok. The values in column 2 (0,1,0,1,2) differ from 9 by at least 7. So B stops: columns 3-5, 15 pixels.
Result (shading = region A):
| 1 | 0 | 7 | 8 | 7 |
| 0 | 1 | 8 | 9 | 8 |
| 0 | 0 | 7 | 9 | 8 |
| 0 | 1 | 8 | 8 | 9 |
| 1 | 2 | 8 | 8 | 9 |
$10+15=25$, so every pixel is assigned. Any $T$ from 2 to 5 gives the same answer. The image has two clearly separated intensity groups (about 0-2 and 7-9).
Practice. Grid $\begin{bmatrix}5&6&20\\5&7&21\\4&22&23\end{bmatrix}$, seed (1,1)=5, $T=3$, 4-connected. Neighbours: (1,2)=6 ok, (2,1)=5 ok, then (2,2)=7 (diff 2) ok, (3,1)=4 ok. The pixels (1,3)=20, (2,3)=21 and (3,2)=22 differ by at least 15, so they are rejected. Region $=\{5,6,5,7,4\}$, 5 pixels.
State your rule before you solve. The result depends on four things. They are the seed choice, the threshold, the order of visiting pixels and the comparison value (the seed value or the running region mean). Region growing is also slow and sensitive to noise.
Region splitting
Region splitting is a region-based technique. It recursively divides the image into smaller regions until each region satisfies a homogeneity criterion. The assumption: if a region is not homogeneous, split it. The method is top-down.
A predicate $P(R)$ decides homogeneity. Examples: variance $<$ threshold, intensity range $<$ threshold, texture similarity. If $P(R)=\text{TRUE}$, the region is homogeneous. If $P(R)=\text{FALSE}$, split it into four equal-sized quadrants.
Homogeneity criteria
Variance: $\sigma^2<T$. Intensity range: $\max(R)-\min(R)<T$. Standard deviation: $\sigma<T$.
$$\sigma^2=\frac1N\sum_{(x,y)\in R}\big(f(x,y)-\mu\big)^2,\qquad \mu=\frac1N\sum_{(x,y)\in R}f(x,y)$$$N$ = number of pixels in the region, $\mu$ = its mean, $T$ = threshold.
Splitting process (quadtree)
The image is stored as a quadtree. Each node is a square region with four children (the quadrants) or none. The root is the whole image.
- Take the whole image as region $R$.
- Check $P(R)$. If it is true, stop. If it is false, split $R$ into four equal quadrants $R_1,R_2,R_3,R_4$ (top-left, top-right, bottom-left, bottom-right).
- Repeat for every sub-region. For example, if $R_1$ is still not homogeneous, split it into $A,B,C,D$.
- Continue until every region satisfies $P$ or the minimum block size is reached.
- Output the segmented regions.
| Advantages | Disadvantages |
|---|---|
| Simple to implement | Produces square-shaped regions |
| No seed points needed | Boundaries may not match real object shapes |
| Suitable for large images | Sensitive to the threshold |
| Quadtree is memory efficient | Can over-segment noisy images |
Region growing versus region splitting
| Feature | Region growing | Region splitting |
|---|---|---|
| Starting point | Seed pixel required | Entire image |
| Approach | Merge pixels | Divide regions |
| Data structure | Connected region | Quadtree |
| Direction | Bottom-up | Top-down |
| Output | Irregular regions | Square regions |
Split and merge algorithm
Region growing is slow. Pure splitting leaves artificial square boundaries, and two neighbouring squares can belong to the same object. Split and merge combines both methods. It extends the seed point to a seed region. A whole region (not a single pixel) is the starting unit.
- Start with the entire image as one region $R$. Check the homogeneity criterion $P(R)$ (variance below threshold, intensity range below threshold, texture similarity). If it is true, stop. If it is false, split.
- Splitting phase: divide the region into four equal quadrants $R\to R_1,R_2,R_3,R_4$. Check each quadrant. Recurse until every region satisfies $P$ or the minimum size is reached.
- Merging phase: build the region adjacency graph (RAG) (nodes = regions, edges between neighbouring regions). Examine adjacent regions. If two neighbours satisfy $P(R_i\cup R_j)=\text{TRUE}$, merge them. Repeat until no region pair can merge.
A similarity measure, such as intensity or other image statistics, builds the homogeneity test.
Worked example 1: slide 4×4
Use the range predicate: $P(R)$ = TRUE if $\max-\min<T$ with $T=10$ (the slide gives no $T$).
| 45 | 47 | 90 | 92 |
| 46 | 48 | 91 | 93 |
| 150 | 152 | 200 | 202 |
| 151 | 153 | 201 | 203 |
Check the whole image: $\max-\min=203-45=158\ge10$, FALSE. Split it into four 2×2 quadrants.
| Quadrant | Pixels | Range | Mean | Predicate |
|---|---|---|---|---|
| Top-left | 45, 47, 46, 48 | 3 | 46.5 | TRUE |
| Top-right | 90, 92, 91, 93 | 3 | 91.5 | TRUE |
| Bottom-left | 150, 152, 151, 153 | 3 | 151.5 | TRUE |
| Bottom-right | 200, 202, 201, 203 | 3 | 201.5 | TRUE |
All four quadrants are homogeneous, so splitting stops. (Variance version: the deviations of top-left from 46.5 are $-1.5,0.5,-0.5,1.5$, so $\sigma^2=(2.25+0.25+0.25+2.25)/4=1.25$. This is very small.)
Merge: TL∪TR range $=93-45=48$; TR∪BR range $=203-90=113$; TL∪BL range $=153-45=108$; BL∪BR range $=203-150=53$. All are $\ge10$, so there is no merge. Final: 4 regions.
Worked example 2: slide 8×8 (four levels of grey)
The $8\times8$ image on the slide has a line between rows 4 and 5. Use $T=10$ with the range predicate.
| 10 | 11 | 10 | 12 | 50 | 51 | 50 | 52 |
| 11 | 12 | 11 | 13 | 51 | 52 | 51 | 53 |
| 10 | 11 | 12 | 11 | 50 | 51 | 52 | 51 |
| 12 | 13 | 11 | 12 | 52 | 53 | 51 | 52 |
| 100 | 101 | 102 | 101 | 150 | 151 | 152 | 151 |
| 101 | 102 | 101 | 103 | 151 | 152 | 151 | 153 |
| 100 | 101 | 103 | 102 | 150 | 151 | 153 | 152 |
| 102 | 103 | 101 | 102 | 152 | 153 | 151 | 154 |
Whole image: range $154-10=144$, FALSE. Split it into four 4×4 quadrants.
| Quadrant | Min | Max | Range | Mean | P |
|---|---|---|---|---|---|
| Top-left | 10 | 13 | 3 | 11.4 | TRUE |
| Top-right | 50 | 53 | 3 | 51.4 | TRUE |
| Bottom-left | 100 | 103 | 3 | 101.6 | TRUE |
| Bottom-right | 150 | 154 | 4 | 151.7 | TRUE |
There is no further splitting. Merge test on neighbours: TL∪TR spans 10 to 53 (range 43). TL∪BL spans 10 to 103. TR∪BR spans 50 to 154. BL∪BR spans 100 to 154 (range 54). All fail. Final: 4 regions with intensities about 11, 51, 102, 152.
Worked example 3: slide 8×8 (split then merge)
This image shows why merging is needed. The shaded cells are the right half, which ends up as one region. Use $T=10$.
| 10 | 11 | 10 | 12 | 50 | 51 | 49 | 50 |
| 11 | 10 | 12 | 11 | 51 | 50 | 52 | 49 |
| 10 | 12 | 11 | 10 | 49 | 52 | 50 | 51 |
| 12 | 11 | 10 | 12 | 50 | 49 | 51 | 50 |
| 30 | 31 | 29 | 30 | 50 | 51 | 49 | 52 |
| 31 | 30 | 32 | 29 | 51 | 50 | 52 | 49 |
| 29 | 32 | 30 | 31 | 49 | 52 | 50 | 51 |
| 30 | 29 | 31 | 30 | 52 | 49 | 51 | 50 |
Split. The whole image has range $52-10=42\ge10$. Split it into quadrants.
| Quadrant | Min | Max | Range | P | Approx. mean |
|---|---|---|---|---|---|
| Top-left | 10 | 12 | 2 | TRUE | 11 |
| Top-right | 49 | 52 | 3 | TRUE | 50 |
| Bottom-left | 29 | 32 | 3 | TRUE | 30 |
| Bottom-right | 49 | 52 | 3 | TRUE | 50 |
All four quadrants are already homogeneous, so splitting stops at one level.
Merge. Test the adjacent pairs (the RAG has edges TL-TR, TL-BL, TR-BR, BL-BR):
- TR∪BR: values 49-52, range $3<10$, TRUE, merge.
- TL∪TR: range $52-10=42$, FALSE. TL∪BL: range $32-10=22$, FALSE. BL∪BR: range $52-29=23$, FALSE.
Final: 3 regions: top-left (about 11), bottom-left (about 30) and the whole right half (about 50). The right half is a non-square region that the merge made. Pure splitting leaves four regions and cuts the right half in two. If $T$ is 25, TL and BL also merge (range 22). So the result depends on $T$.
Practice. $4\times4$ image $\begin{bmatrix}10&10&80&82\\10&11&81&80\\10&10&10&11\\11&10&10&10\end{bmatrix}$, $T=10$, range predicate. The whole range is 72, so split. TL (10,10,10,11) has range 1. TR (80,82,81,80) has range 2. BL (10,10,11,10) has range 1. BR (10,11,10,10) has range 1. All are homogeneous. Merge: TL∪BL has range 1, TRUE. BL∪BR has range 1, TRUE (so TL, BL and BR chain into one background region). TL∪TR has range 72, FALSE. Final: 2 regions, the background (L-shape, not a square) and the top-right square.
A typical exam asks for five things. (1) Write the five region-segmentation conditions. (2) Do region growing on a small grid with given seeds and threshold. (3) Do split-and-merge on an 8×8 image with a stated predicate. (4) Give the growing versus splitting table. (5) Explain why split-and-merge is better than pure splitting (it merges squares back across quadrant boundaries). Always state your threshold and predicate.
Quick self-test
1. Why do point-detection masks sum to zero?
A constant (flat) region must give response 0. Only intensity differences, that is discontinuities, give a non-zero response $|R|\ge T$.
2. Compute the point response: centre 90 with all eight neighbours 20, $T=300$. Is it a point?
$R=8(90)-8(20)=720-160=560$. $560\ge300$, so yes.
3. Which line mask responds most to the patch $\begin{bmatrix}10&50&10\\10&50&10\\10&50&10\end{bmatrix}$?
The vertical mask. It applies $[-1,2,-1]$ per row. Each row gives $-10+100-10=80$, so the total is $R_V=240$. Horizontal: the rows give $-1(10+50+10)=-70$, $2(70)=140$, $-70$, so the total is 0. The diagonals are 0 as well. So the line is vertical.
4. Compute the Sobel gradient magnitude for $\begin{bmatrix}10&20&30\\10&20&30\\10&20&30\end{bmatrix}$.
$G_x$: each row gives $-10+30=20$. With weights 1,2,1: $20+2(20)+20=80$. $G_y$: the top row gives $-(10+40+30)=-80$ and the bottom row gives $+80$, so the total is 0. Magnitude $=80$ (a smooth horizontal ramp is still a strong gradient).
5. Derive the LoG and state the Marr–Hildreth steps.
$G=e^{-(x^2+y^2)/2\sigma^2}$; $\partial^2G/\partial x^2=(x^2/\sigma^4-1/\sigma^2)G$, and the same for $y$. The sum gives $\nabla^2G=\frac{x^2+y^2-2\sigma^2}{\sigma^4}e^{-(x^2+y^2)/2\sigma^2}$. Steps: smooth with a Gaussian, apply the Laplacian (or convolve with LoG directly), and find the zero crossings as edges.
6. Difference between first- and second-derivative edge detectors.
First derivative (gradient): the edge is at a peak of the magnitude. It gives direction and thicker edges. Second derivative (Laplacian): the edge is at a zero crossing. It gives no direction and is very noise-sensitive. It gives thin edges, and the sign shows the dark or bright side.
7. State the five conditions of region-based segmentation.
(a) The union of the regions is the whole image. (b) Each region is connected. (c) The regions are pairwise disjoint. (d) $P(R_i)$ is TRUE for each region. (e) $P(R_i\cup R_j)$ is FALSE for adjacent regions.
8. Region growing on the slide's 5×5 grid with seeds 1 and 9: describe the outcome.
Use a threshold of 2 to 5 and 4-connectivity. The seed-1 region takes columns 1-2 (values 0, 1, 2). The seed-9 region takes columns 3-5 (values 7, 8, 9). All 25 pixels are assigned: 10 and 15 pixels respectively.
9. Do split and merge on $\begin{bmatrix}20&22&60&61\\21&23&62&63\\19&21&22&20\\20&22&21&23\end{bmatrix}$ with range $<10$.
Whole range $63-19=44$, so split. TL (20,22,21,23) has range 3, ok. TR (60,61,62,63) has range 3, ok. BL (19,21,20,22) has range 3, ok. BR (22,20,21,23) has range 3, ok. Merge: BL∪BR range $23-19=4$ TRUE. TL∪BL range $23-19=4$ TRUE. TL∪TR range $63-20=43$ FALSE. TR∪BR range $63-20=43$ FALSE. Final: TR alone, and TL+BL+BR merged. This gives 2 regions.
10. Compare region growing and region splitting. Why combine them?
Growing is seed-based and bottom-up. It merges pixels, gives irregular output and is slow. Splitting starts from the whole image and is top-down. It uses a quadtree, gives square output and needs no seeds. Splitting alone makes artificial square boundaries. A merge of adjacent homogeneous regions afterwards removes them and gives better boundaries. The start from regions instead of pixels also makes the method faster than pure growing.
- Discontinuities are points, lines and edges. Small masks find them: $R=\sum w_kz_k$. Detection masks sum to 0.
- Point mask: 8 in the centre, -1 elsewhere, $|R|\ge T$.
- Line masks: horizontal, vertical, $\pm45^\circ$ (rows or diagonals of 2 on -1). Take the mask with the largest $|R|$.
- Edges: ideal step versus ramp. The first derivative peaks at an edge. The second derivative crosses zero.
- Gradient: $\nabla f=(G_x,G_y)$, magnitude $\sqrt{G_x^2+G_y^2}\approx|G_x|+|G_y|$, direction perpendicular to the edge.
- Roberts is 2×2. Prewitt and Sobel are 3×3. Sobel has centre weight 2 and smooths more.
- Laplacian $\nabla^2f=f_{xx}+f_{yy}$ (masks with 4 or 8 centre). It is noisy and gives no direction.
- LoG (Mexican hat, Marr–Hildreth) $=\frac{x^2+y^2-2\sigma^2}{\sigma^4}e^{-(x^2+y^2)/2\sigma^2}$. Edges are at zero crossings.
- Thresholding: $g=1$ if $f>T$. A bimodal histogram needs one threshold. Several classes need multiple thresholds.
- Region-based conditions (a)-(e). Region growing: seeds, similarity criterion, stop when nothing joins. It is bottom-up and gives irregular regions.
- Region splitting: quadtree. Split into four while $P(R)$ is FALSE (variance, range or std dev below $T$). It is top-down and gives square regions.
- Split and merge: split, then merge adjacent regions whose union satisfies $P$ (RAG).