Image Processing

Sampling and quantization

A real scene is a continuous function $f(x,y)$ of position and intensity. To store it in a computer it must be digitised in two ways.

• Sampling digitises the coordinate values $(x,y)$. The image is measured at regular grid points, giving an $M \times N$ array of pixels. The more samples, the higher the spatial resolution; too few samples cause aliasing and a blocky look. The sampling rate must be at least twice the highest spatial frequency (Nyquist).
• Quantization digitises the amplitude (intensity) values. The continuous range of brightness at each sample is mapped to one of $L = 2^k$ discrete levels, where $k$ is the number of bits per pixel. Too few levels cause false contouring.

Image size

$512 = 2^9$ colours, so $k = 9$ bits per pixel.

$b = M \times N \times k = 1028 \times 1028 \times 9 = 9{,}511{,}056 \text{ bits}$

$= \frac{9{,}511{,}056}{8} = 1{,}188{,}882 \text{ bytes} \approx 1161 \text{ KB} \approx 1.13 \text{ MB}$

(a) Gaussian noise

It is additive noise whose values follow a normal distribution, caused by sensor electronics, poor illumination and high temperature. The noisy image is

$g(x,y) = f(x,y) + \eta(x,y), \qquad p(z) = \frac{1}{\sqrt{2\pi}\,\sigma}\, e^{-(z-\mu)^2/2\sigma^2}$

where $\mu$ is the mean and $\sigma^2$ the variance. Every pixel is disturbed by a small random amount, so the image looks grainy and uniformly noisy.

Filters: a mean (averaging) filter or Gaussian smoothing filter, adaptive Wiener filter, or a low-pass filter in the frequency domain. These reduce variance, but also blur edges. Averaging $K$ images of the same scene reduces the noise variance by a factor $K$.

(b) Salt and pepper noise

It is impulse noise in which some pixels are set to the extreme values, black (pepper, $0$) or white (salt, $L-1$), caused by faulty sensors, transmission errors and bit errors. Its probability density is

$p(z)=\begin{cases}P_s & z = L-1 \text{ (salt)}\\ P_p & z = 0 \text{ (pepper)}\\ 1-P_s-P_p & \text{otherwise}\end{cases}$

The image shows isolated white and black dots.

Filters: the median filter is the best, because the median ignores extreme values and keeps edges. Others: adaptive median filter (for high noise density), and contra-harmonic mean filter (positive order $Q$ removes pepper, negative $Q$ removes salt). Mean filters are poor because they smear the impulses.

Ideal low pass filter (ILPF)

A filter that passes without attenuation all frequencies within a circle of radius $D_0$ (the cut-off frequency) from the origin of the frequency rectangle, and completely removes all frequencies outside it:

$H(u,v)=\begin{cases}1 & D(u,v)\le D_0\\ 0 & D(u,v)> D_0\end{cases}, \qquad D(u,v)=\sqrt{u^2+v^2}$

(measured from the centre of the shifted spectrum). The sharp cut-off causes ringing in the filtered image, since its spatial counterpart is a sinc function.

Butterworth low pass filter (BLPF) of order $n$:

$H(u,v)=\frac{1}{1+\left[D(u,v)/D_0\right]^{2n}}$

It has no sharp discontinuity; at $D=D_0$, $H=0.5$. For low order $n$ (1 or 2) there is almost no ringing; ringing grows with $n$.

Condition to become ideal: as the order $n \to \infty$, the term $[D/D_0]^{2n}$ goes to $0$ for $D<D_0$ (so $H\to 1$) and to $\infty$ for $D>D_0$ (so $H\to 0$). Hence the Butterworth filter approaches the ideal low pass filter as $n\to\infty$ (with $H=0.5$ at $D=D_0$ itself).

Image compression standards

Standards ensure that images compressed by one system can be decoded by another. They are issued by ISO, IEC and ITU-T.

1. Binary (bi-level) image standards

• CCITT Group 3 (ITU-T T.4): for fax; run-length coding with modified Huffman codes, optionally 2-D (modified READ).
• CCITT Group 4 (T.6): 2-D coding only (MMR); better compression of document images.
• JBIG and JBIG2: context-based arithmetic coding of bi-level images; JBIG2 handles text and halftone regions and has lossless and lossy modes.

2. Continuous-tone still image standards

• JPEG (ISO 10918): the baseline lossy standard, based on the DCT. Steps: split into $8\times8$ blocks, DCT, quantization with a quantization table, zig-zag scan, DPCM of DC terms and run-length of AC terms, then Huffman (or arithmetic) coding. It also has a lossless predictive mode and progressive modes.
• JPEG 2000: uses the discrete wavelet transform and EBCOT coding. It has better quality at low bit rates, no blocking, lossless and lossy in one file, and region of interest and progressive transmission.
• JPEG-LS: low complexity near-lossless/lossless coding.

3. Video standards: MPEG-1, MPEG-2, MPEG-4 and H.261, H.263, H.264/AVC, H.265/HEVC. They add motion estimation and compensation to remove temporal redundancy.

4. Common file formats: GIF (LZW), PNG (DEFLATE, lossless), TIFF (multiple schemes), BMP (mostly uncompressed or RLE).

(a) Feature extraction

Feature extraction is the process of measuring the attributes of an image or region that are useful for recognising or describing it, and representing them as a compact feature vector. It follows segmentation and precedes classification. It reduces the amount of data while keeping what discriminates one object from another.

Types of features:

• Boundary/shape features: perimeter, area, compactness, eccentricity, chain codes, Fourier descriptors, moments.
• Region/texture features: mean, variance, entropy, grey level co-occurrence matrix (GLCM), statistical and spectral texture.
• Colour features: colour histograms and moments.
• Edge and point features: corners, gradients, SIFT.
• Transform features: PCA, DCT, wavelet coefficients.

A good feature is invariant to translation, rotation and scale, and robust to noise.

(b) Mach band effect

The Mach band effect is a visual illusion in which the human eye perceives bands of overshoot and undershoot of brightness at the boundary between two regions of different intensity, even though the actual intensity is constant on each side. At a boundary from a dark to a light region, the darker side appears darker still, and the lighter side appears lighter, near the edge. It is caused by lateral inhibition in the retina, where the response of a receptor is affected by its neighbours. It shows that the perceived brightness is not a simple function of intensity, and that the eye is sensitive to edges, which is important in the design of edge enhancement and displays.

Definitions

The question writes "EFT"; it is taken to mean the FFT (Fast Fourier Transform).

2-D continuous Fourier transform of $f(x,y)$:

$F(u,v)=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty} f(x,y)\, e^{-j2\pi(ux+vy)}\,dx\,dy$

2-D DFT of an $M\times N$ image:

$F(u,v)=\sum_{x=0}^{M-1}\sum_{y=0}^{N-1} f(x,y)\, e^{-j2\pi\left(\frac{ux}{M}+\frac{vy}{N}\right)},\quad u=0,\dots,M-1,\; v=0,\dots,N-1$

with the inverse $f(x,y)=\dfrac{1}{MN}\sum_u\sum_v F(u,v)\,e^{j2\pi(ux/M+vy/N)}$.

FFT: it is not a different transform but a fast algorithm to compute the DFT. By using the symmetry and periodicity of the exponential, a DFT of size $N$ is split into DFTs of size $N/2$ (divide and conquer, decimation in time/frequency). The cost falls from $O(N^2)$ to $O(N\log_2 N)$ for 1-D, and the 2-D DFT is computed as row-wise FFTs followed by column-wise FFTs (separability).

Proof of linearity

Let $\mathcal{F}$ denote the transform, and let $f_1\leftrightarrow F_1$, $f_2\leftrightarrow F_2$. We must show $\mathcal{F}\{a f_1 + b f_2\} = a F_1 + b F_2$ for constants $a,b$.

Continuous case: $\mathcal{F}\{af_1+bf_2\}=\iint \big[a f_1(x,y)+b f_2(x,y)\big]e^{-j2\pi(ux+vy)}dx\,dy$ $=a\iint f_1(x,y)e^{-j2\pi(ux+vy)}dx\,dy+b\iint f_2(x,y)e^{-j2\pi(ux+vy)}dx\,dy = aF_1(u,v)+bF_2(u,v)$ since the integral of a sum is the sum of integrals, and constants can be taken out of the integral.

Discrete case: $\mathcal{F}\{af_1+bf_2\}=\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}\big[af_1(x,y)+bf_2(x,y)\big]e^{-j2\pi(ux/M+vy/N)}$ $=a\sum_x\sum_y f_1(x,y)e^{-j2\pi(\cdot)}+b\sum_x\sum_y f_2(x,y)e^{-j2\pi(\cdot)}=aF_1(u,v)+bF_2(u,v)$ since summation is linear.

Hence both the continuous and the discrete 2-D Fourier transforms are linear operations. $\blacksquare$ (The FFT, computing the same DFT, is also linear.)

Basic relationships between pixels

Let $p$ be a pixel at $(x,y)$.

1. Neighbours

• 4-neighbours $N_4(p)$: $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$.
• Diagonal neighbours $N_D(p)$: $(x\pm1,y\pm1)$.
• 8-neighbours $N_8(p)=N_4(p)\cup N_D(p)$.

2. Adjacency (for pixels whose values lie in a set $V$ of allowed values)

• 4-adjacency: $q\in N_4(p)$.
• 8-adjacency: $q\in N_8(p)$.
• m-adjacency (mixed): $q\in N_4(p)$, or $q\in N_D(p)$ and $N_4(p)\cap N_4(q)$ has no pixel with value in $V$. It removes the ambiguity of multiple paths in 8-adjacency.

3. Path and connectivity: a path is a sequence of adjacent pixels from $p$ to $q$. Two pixels are connected if a path exists between them within a set $S$. A connected component is the set of all pixels of $S$ connected to a given pixel; $S$ is a region if it is a connected set. The boundary of a region is the set of its pixels that have a neighbour outside.

4. Distance measures: for $p=(x,y)$, $q=(s,t)$:

• Euclidean $D_e=\sqrt{(x-s)^2+(y-t)^2}$
• City block $D_4=|x-s|+|y-t|$
• Chessboard $D_8=\max(|x-s|,|y-t|)$

Functional block diagram of an image compression system

                 ENCODER
f(x,y) --> [ Mapper ] --> [ Quantizer ] --> [ Symbol encoder ] --> compressed data
                                                                        |
                 DECODER                                          channel/storage
f^(x,y) <-- [ Inverse mapper ] <-- [ Symbol decoder ] <-----------------+

Purpose of each block

• Mapper (transformer): converts the input into a form that reduces interpixel redundancy, for example run-length coding, predictive coding (differences), or a transform such as DCT/wavelet that packs energy into few coefficients. It is reversible.
• Quantizer: reduces the accuracy of the mapper's output according to a fidelity criterion, removing psychovisual redundancy. It is irreversible (lossy) and is omitted in lossless compression.
• Symbol encoder: assigns a short code to the most frequent values (Huffman, arithmetic, LZW), removing coding redundancy, and produces the bit stream. It is reversible.
• Symbol decoder: reverses the symbol encoding.
• Inverse mapper: reverses the mapping operation (inverse DCT, adding predictions) to rebuild the image $\hat f(x,y)$. There is no inverse quantizer to recover lost information.

If $\hat f=f$ the compression is lossless; otherwise it is lossy.

Segmentation divides an image into regions. Region-based methods work directly with regions, using a homogeneity predicate $P$ (for example "all pixels differ by no more than $T$").

Region growing

Starts from one or more seed pixels and grows each region by appending neighbouring pixels (4- or 8-connected) that satisfy the similarity criterion, until no more pixels can be added.

Steps: (1) choose seeds; (2) choose a criterion, e.g. $|f(x,y)-f(\text{seed})|\le T$; (3) examine the neighbours of the region and add those that satisfy it; (4) stop when none qualify.

Example. Image (4×4) with seed at the top-right pixel (value 9), $T=2$, 4-connectivity:

$\begin{matrix}1&2&8&9\\2&1&8&8\\1&1&9&9\\2&1&8&9\end{matrix}$

Pixels with values from 7 to 11 are accepted. Starting from the seed, the neighbours 8 and 8 are accepted and then all pixels in the last two columns (values 8 or 9). The pixels in the first two columns (1 and 2) differ from 9 by 7 or more, so they are rejected. The grown region is the right half (8 pixels).

Drawbacks: the result depends on the seed and the threshold, and noise can cause leaks.

Region splitting and merging

Does not need seeds.

1. Split: start with the whole image as one region. If $P(R)$ is false, split it into four quadrants (quadtree). Repeat for each quadrant until every region satisfies $P$ or is a single pixel.
2. Merge: merge adjacent regions $R_i,R_j$ if $P(R_i\cup R_j)$ is true. Repeat until no more merging is possible.

Example. Same image, with $P$: (max - min) $\le 2$.

• Whole image: max 9, min 1, so $P$ is false and it is split into four 2×2 quadrants.
• Top-left $\{1,2,2,1\}$: true. Top-right $\{8,9,8,8\}$: true. Bottom-left $\{1,1,2,1\}$: true. Bottom-right $\{9,9,8,9\}$: true. No further splitting.
• Merge: top-left with bottom-left $\{1,2,2,1,1,1,2,1\}$: range 1, merged. Top-right with bottom-right $\{8,9,8,8,9,9,8,9\}$: range 1, merged. Left with right: range 8, not merged.

Final result: two regions, the left half (dark) and the right half (bright).

Splitting and merging gives good results on images with natural region structure but blocky boundaries can appear because of quadtree splitting.

Image operations

Operations applied to digital images are classified as follows.

1. Point operations: the output at a pixel depends only on the input value at that same pixel, $s=T(r)$. Examples: negative ($s=L-1-r$), thresholding, contrast stretching, log and power-law (gamma) transforms, brightness change.

2. Neighbourhood (local) operations: the output depends on the pixels in a neighbourhood, computed with a mask by convolution or correlation. Examples: smoothing (mean, Gaussian, median), sharpening (Laplacian), edge detection (Sobel, Prewitt).

3. Global operations: each output pixel depends on the whole image, such as the Fourier transform, histogram equalisation and frequency domain filtering.

4. Geometric (spatial) operations: change the positions of pixels: translation, rotation, scaling, shear, flip, crop, with interpolation (nearest neighbour, bilinear, bicubic) to find grey values at new positions.

5. Arithmetic and logical operations between images: addition (averaging to reduce noise), subtraction (change detection), multiplication (masking, shading correction), division; AND, OR, NOT, XOR for masking and region selection.

6. Morphological operations: erosion, dilation, opening and closing using a structuring element.

7. Transform operations: DFT, DCT, wavelet, used for filtering and compression.

Image enhancement

Image enhancement is the process of processing an image so that the result is more suitable than the original for a specific application, for example by improving contrast, brightness and sharpness, or reducing noise. It does not add information and is subjective. Methods work in the spatial domain (directly on pixels: $g(x,y)=T[f(x,y)]$) or the frequency domain (modifying the Fourier transform).

Histogram modeling (processing)

The histogram of a digital image with grey levels $0,\dots,L-1$ is $h(r_k)=n_k$, the number of pixels with level $r_k$, or normalised $p(r_k)=n_k/n$. A dark image has its histogram at the low end, a bright image at the high end, and a low-contrast image in a narrow band. Histogram modeling changes the histogram to improve contrast.

Histogram equalisation makes the output histogram approximately uniform:

$s_k=T(r_k)=(L-1)\sum_{j=0}^{k}p(r_j)$

Example. 3-bit image ($L=8$), $n=64$ pixels, counts for levels 0 to 7: 8, 10, 10, 2, 12, 16, 4, 2.

Levels 2 and 3 merge into 3, and levels 6 and 7 into 7. The levels are spread over the full range, which increases contrast.

Histogram specification (matching) maps the image to a chosen target histogram instead of a uniform one, by equalising both the image and the target and combining the mappings, giving more control.

Image restoration

Image restoration is the process of recovering or estimating the original clean image from a degraded one, by using knowledge of the degradation (blur, noise) and applying the inverse of the process. The degradation model is

$g(x,y)=h(x,y)*f(x,y)+\eta(x,y)\quad\Longleftrightarrow\quad G(u,v)=H(u,v)F(u,v)+N(u,v)$

where $f$ is the original image, $h$ the degradation function (blur), $\eta$ noise and $g$ the observed image.

Wiener filtering

Inverse filtering, $\hat F=G/H$, amplifies noise strongly where $H$ is small or zero. The Wiener filter (minimum mean square error filter) finds the estimate $\hat f$ that minimises the error

$e^2=E\{(f-\hat f)^2\}$

and takes both the degradation function and the noise statistics into account:

$\hat F(u,v)=\left[\frac{H^*(u,v)}{|H(u,v)|^2+S_\eta(u,v)/S_f(u,v)}\right]G(u,v)=\left[\frac{1}{H}\,\frac{|H|^2}{|H|^2+S_\eta/S_f}\right]G$

where $H^*$ is the complex conjugate of $H$, $S_\eta=|N(u,v)|^2$ is the power spectrum of the noise, and $S_f=|F(u,v)|^2$ is that of the undegraded image.

• With no noise ($S_\eta=0$) it reduces to the inverse filter.
• Where noise dominates ($S_\eta/S_f$ large) it suppresses those frequencies.
• When the spectra are unknown, the ratio is replaced by a constant $K$: $\hat F=\dfrac{|H|^2}{H(|H|^2+K)}G$, with $K$ chosen by trial.

It gives better results than inverse filtering because it balances deblurring against noise amplification.

Morphological operations are non-linear operations that process an image according to its shape, using a small structuring element (SE) that is slid over the image. They are mostly applied to binary images, and also to grayscale images.

1. Erosion ($A \ominus B$): a pixel stays 1 only if the SE placed at that pixel fits entirely inside the foreground. $A \ominus B = \{z \mid (B)_z \subseteq A\}$ It shrinks objects, removes small noise and thin protrusions, and enlarges holes.

2. Dilation ($A \oplus B$): a pixel becomes 1 if the SE placed there overlaps the foreground at least once. $A \oplus B = \{z \mid (\hat{B})_z \cap A \neq \emptyset\}$ It expands objects, bridges small gaps and fills small holes.

3. Opening ($A \circ B = (A \ominus B) \oplus B$): erosion followed by dilation. It removes small objects and thin protrusions and smooths contours while keeping the object size roughly unchanged.

4. Closing ($A \bullet B = (A \oplus B) \ominus B$): dilation followed by erosion. It fills small holes and gaps and joins nearby objects.

5. Hit-or-miss transform: detects a specific shape or pattern using a pair of structuring elements (one for foreground, one for background).

6. Other operations: boundary extraction ($A - (A \ominus B)$), region filling, thinning, thickening, skeletonization and convex hull.

Uses include noise removal, boundary extraction, object counting, text/character recognition and shape analysis.

Image compression standards are internationally agreed formats so that images can be compressed and decompressed by any compliant system.

1. Binary (bi-level) image standards

• CCITT Group 3 (T.4) and Group 4 (T.6): used for fax and document images. They use run-length coding combined with Huffman (Modified Huffman / Modified READ) codes. Group 4 is two-dimensional and gives higher compression.
• JBIG / JBIG2: context-based arithmetic coding for bi-level images. JBIG2 supports lossless and lossy modes and text/halftone regions.

2. Continuous-tone still image standards

• JPEG: lossy DCT-based standard. Steps: split the image into $8\times8$ blocks, apply the DCT, quantize the coefficients, zig-zag scan, then apply run-length and Huffman (or arithmetic) coding. It also has a lossless predictive mode.
• JPEG 2000: uses the wavelet transform (DWT) instead of DCT, with EBCOT coding. It gives better quality at low bit rates, supports both lossy and lossless coding, region-of-interest coding and progressive transmission.
• JPEG-LS: low-complexity near-lossless/lossless compression.

3. Video compression standards

• MPEG-1, MPEG-2, MPEG-4 and H.261, H.263, H.264/AVC, H.265/HEVC: use DCT for spatial redundancy plus motion estimation and compensation (I, P, B frames) for temporal redundancy.

4. Other formats: GIF and PNG (lossless, LZW and DEFLATE based), and TIFF (container supporting several schemes).

(a) Feature reduction

Feature reduction (dimensionality reduction) reduces the number of features used to describe an object or image while keeping the information needed for classification. It lowers computation and storage, avoids the curse of dimensionality and reduces over-fitting. There are two approaches: feature selection (choose a subset of the original features) and feature extraction (build new, fewer features from the originals). A common method is Principal Component Analysis (PCA), which projects data onto the eigenvectors of the covariance matrix with the largest eigenvalues. Another is Linear Discriminant Analysis (LDA).

(b) Digital watermarking

Digital watermarking embeds hidden information (a logo, serial number or signature) into an image so that it can be used later for copyright protection, ownership proof, authentication and tamper detection. Watermarks may be visible or invisible, and robust (survive compression, cropping, noise) or fragile (break on any modification). Embedding can be done in the spatial domain (for example by modifying the least significant bits) or in a transform domain (DCT, DWT, DFT), which is more robust. Key requirements are imperceptibility, robustness and capacity.

(c) Remote sensing

Remote sensing is acquiring information about the Earth's surface without physical contact, using sensors on satellites or aircraft that record reflected or emitted electromagnetic radiation in several spectral bands. Image processing is used for correction, enhancement, classification and change detection. Applications include land-use mapping, agriculture and crop monitoring, forestry, flood and glacier monitoring, weather forecasting and urban planning.

Uses of filters in digital image processing

• Smoothing (low-pass) filters such as mean, Gaussian and median filters reduce noise and blur an image.
• Sharpening (high-pass) filters such as the Laplacian and unsharp masking enhance edges and fine detail.
• Edge detection filters (Sobel, Prewitt, Roberts) highlight boundaries.
• Band-pass/band-reject and notch filters remove periodic noise.
• Restoration filters (inverse, Wiener) remove degradation such as blur.
• They are also used in pre-processing for segmentation, feature extraction and compression.

Difference between DFT and FFT

Histogram equalization

The histogram of an image shows the number of pixels at each gray level. Histogram equalization is a contrast-enhancement technique that spreads the gray levels so that the output histogram is approximately uniform.

For an image with $n$ pixels and $L$ gray levels, with $n_k$ pixels at level $r_k$: $p(r_k)=\frac{n_k}{n},\qquad s_k = T(r_k) = (L-1)\sum_{j=0}^{k} p(r_j)$ The result $s_k$ is rounded to the nearest integer.

Steps: (1) compute the histogram, (2) compute the probabilities, (3) compute the cumulative distribution function, (4) multiply by $L-1$ and round, (5) map each old gray level to its new one.

It improves the contrast of images that are too dark or too bright, since frequently occurring levels are spread apart.

Need for image compression

Raw images need a lot of storage and bandwidth. For example, a $1024\times1024$ 24-bit colour image takes about 3 MB, and video needs many such frames per second. Compression reduces storage space, transmission time and bandwidth cost. It works by removing coding redundancy, interpixel (spatial) redundancy and psychovisual redundancy.

Run length encoding (RLE)

RLE is a lossless method that replaces a sequence of identical consecutive values (a run) by a pair (value, run length). It works well for images with large uniform regions, such as binary and document images.

Encoding example

Row of pixels: $0\,0\,0\,0\,1\,1\,0\,0\,0\,1\,1\,1\,1\,1\,1\,0$ Runs: four 0s, two 1s, three 0s, six 1s, one 0.

RLE output as (value, count): $(0,4)\,(1,2)\,(0,3)\,(1,6)\,(0,1)$.

For gray-level data, e.g. $50\,50\,50\,50\,50\,200\,200\,10$ the code is $(50,5)\,(200,2)\,(10,1)$, which stores 6 numbers instead of 8.

Decoding

The decoder reads each pair and repeats the value for the stated count: $(0,4)\to0000$, $(1,2)\to11$, $(0,3)\to000$, $(1,6)\to111111$, $(0,1)\to0$. Concatenating gives back exactly the original row, so no information is lost.

Note: RLE can expand data when there are few repeats (for example, alternating pixels), so it is best used for binary or synthetic images, and often as one stage in standards such as CCITT fax and JPEG.

Region-based segmentation

Region-based segmentation divides an image into regions of pixels that share similar properties (intensity, colour, texture), rather than looking for boundaries. The regions $R_1,\dots,R_n$ must satisfy: they cover the whole image, each is connected, they do not overlap, pixels in one region satisfy a predicate $P(R_i)=\text{TRUE}$ (e.g. similar gray level), and $P(R_i\cup R_j)=\text{FALSE}$ for adjacent regions.

Main approaches

1. Region growing: start with seed pixels; add neighbouring pixels to the region if they satisfy a similarity criterion (for example $|I(x,y)-\text{seed mean}| < T$). Repeat until no more pixels can be added. Results depend on the choice of seeds and threshold.
2. Region splitting and merging: start with the whole image. Split any region that fails the predicate into four quadrants (quadtree). Then merge adjacent regions whose union satisfies the predicate.
3. Watershed and clustering-based methods are also region-based.

Advantages: gives closed, connected regions and works well on noisy images. Disadvantages: depends on seeds and thresholds, and is computationally heavy.

Edge detection operators

Edges are sudden changes in intensity, found with gradient or second derivative operators.

• Roberts ($2\times2$ masks): simple, uses diagonal differences, sensitive to noise.
• Prewitt ($3\times3$): gradient with equal weights, $G_x=\begin{bmatrix}-1&0&1\\-1&0&1\\-1&0&1\end{bmatrix}$.
• Sobel ($3\times3$): like Prewitt but weights the centre row more, $G_x=\begin{bmatrix}-1&0&1\\-2&0&2\\-1&0&1\end{bmatrix}$, giving some smoothing. Magnitude $|G|=\sqrt{G_x^2+G_y^2}$.
• Laplacian (second derivative): isotropic, finds zero crossings, very noise sensitive.
• Laplacian of Gaussian (LoG): smooths with a Gaussian first, then applies the Laplacian.
• Canny: Gaussian smoothing, gradient, non-maximum suppression and hysteresis thresholding. It gives thin, well-connected edges and is considered the best.