Image Processing

Fundamental steps in digital image processing

1. Image acquisition: capturing the image with a sensor (camera, scanner) and converting it to digital form; includes preprocessing such as scaling.
2. Image enhancement: improving the image for a specific purpose, e.g. contrast stretching, histogram equalisation, sharpening.
3. Image restoration: removing degradation (blur, noise) using a model of how the image was degraded.
4. Colour image processing: colour models (RGB, HSI, CMY) and processing of colour images.
5. Wavelets and multiresolution processing: representing the image at several resolutions.
6. Compression: reducing the storage or bandwidth needed (JPEG, run-length, Huffman).
7. Morphological processing: extracting shape components using erosion, dilation, opening, closing.
8. Segmentation: partitioning the image into objects or regions.
9. Representation and description: converting segmented regions to boundary or region form and computing descriptors (area, perimeter, shape numbers).
10. Recognition: labelling an object from its descriptors.

All steps interact with a knowledge base about the problem domain.

Neighbours of a pixel

For a pixel $p$ at $(x,y)$:

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

Pixels on the image border have fewer neighbours.

Distance between pixels

For $p=(x,y)$ and $q=(s,t)$, a distance function $D$ satisfies $D(p,q)\ge0$ (zero iff $p=q$), $D(p,q)=D(q,p)$, and $D(p,z)\le D(p,q)+D(q,z)$. Common measures:

• Euclidean: $D_e(p,q) = \sqrt{(x-s)^2 + (y-t)^2}$
• City-block ($D_4$): $D_4(p,q) = |x-s| + |y-t|$ (pixels with $D_4\le1$ are the 4-neighbours)
• Chessboard ($D_8$): $D_8(p,q) = \max(|x-s|, |y-t|)$ (pixels with $D_8\le1$ are the 8-neighbours)

Example: for $p=(2,3)$, $q=(5,7)$: $D_e = \sqrt{9+16}=5$, $D_4 = 3+4=7$, $D_8 = \max(3,4)=4$.

Why enhance an image?

Raw images often have poor contrast, noise, blur or uneven illumination. Enhancement processes an image so that the result is more suitable than the original for a specific application, by making details clearer to a human viewer or easier for later processing (segmentation, recognition). It does not add information; it emphasises existing features.

Histogram in image enhancement

The histogram of an image with $L$ grey levels is $h(r_k) = n_k$, the number of pixels with level $r_k$; the normalised histogram $p(r_k) = n_k/MN$ estimates the probability of that level. A dark image has a histogram concentrated at low levels, a bright one at high levels, and a low-contrast one is narrow.

• Histogram equalisation: apply the transformation $s_k = T(r_k) = (L-1)\sum_{j=0}^{k} p(r_j)$ which spreads the levels to a roughly uniform histogram and increases contrast automatically.
• Histogram specification (matching): transform the image so its histogram matches a chosen shape.
• Local histogram processing: equalise inside a sliding neighbourhood to enhance local detail.
• Histogram statistics (mean, variance) are also used to judge brightness and contrast.

Log vs power-law (gamma) transformation

The log transform is effectively a special case of the power-law family with a fixed curve shape.

Properties of the Fourier transform

For the 2-D DFT pair $f(x,y) \leftrightarrow F(u,v)$ of an $M\times N$ image:

1. Separability: the 2-D DFT is computed as two 1-D transforms, first along rows then along columns.
2. Linearity: $af_1 + bf_2 \leftrightarrow aF_1 + bF_2$.
3. Translation: $f(x-x_0,y-y_0) \leftrightarrow F(u,v)\,e^{-j2\pi(ux_0/M + vy_0/N)}$; a shift changes only the phase, not the magnitude. Also $f(x,y)(-1)^{x+y} \leftrightarrow F(u-M/2, v-N/2)$, which centres the spectrum.
4. Periodicity: $F(u,v) = F(u+M,v) = F(u,v+N)$, and likewise in space.
5. Conjugate symmetry: for real $f$, $F(u,v) = F^*(-u,-v)$, so $|F(u,v)| = |F(-u,-v)|$.
6. Rotation: rotating $f$ by $\theta$ rotates $F$ by the same angle.
7. Scaling: $f(ax,by) \leftrightarrow \frac{1}{|ab|}F(u/a, v/b)$.
8. Convolution theorem: $f * h \leftrightarrow F\cdot H$ and $f\cdot h \leftrightarrow F * H$.
9. Average value: $F(0,0) = MN\bar f$ (the DC term is proportional to the mean).
10. Parseval's (energy) relation: the total energy in space and frequency is equal.

Derivation of the 1-D fast Fourier transform (decimation in time)

The DFT of $N$ samples is

$F(u) = \sum_{x=0}^{N-1} f(x)\,W_N^{ux},\qquad W_N = e^{-j2\pi/N},\quad u=0,\dots,N-1.$

Direct evaluation needs $N^2$ complex multiplications. Take $N = 2^n$ and split $f$ into even and odd samples, $x = 2r$ and $x = 2r+1$, $r=0,\dots,N/2-1$:

$F(u) = \sum_{r=0}^{N/2-1} f(2r)\,W_N^{2ur} + \sum_{r=0}^{N/2-1} f(2r+1)\,W_N^{u(2r+1)}.$

Since $W_N^{2} = W_{N/2}$,

$F(u) = \underbrace{\sum_{r=0}^{N/2-1} f(2r)\,W_{N/2}^{ur}}_{F_e(u)} + W_N^{u}\underbrace{\sum_{r=0}^{N/2-1} f(2r+1)\,W_{N/2}^{ur}}_{F_o(u)}.$

$F_e$ and $F_o$ are $N/2$-point DFTs of the even and odd samples. They are periodic with period $N/2$, so for $u = 0,\dots,N/2-1$, using $W_N^{u+N/2} = -W_N^{u}$:

$F(u) = F_e(u) + W_N^{u}F_o(u),$ $F\!\left(u+\tfrac N2\right) = F_e(u) - W_N^{u}F_o(u).$

These two equations are the "butterfly". Applying the split recursively down to 2-point (then 1-point) transforms gives $\log_2 N$ stages, each with $N/2$ butterflies and one multiplication each:

$\text{multiplications} = \frac{N}{2}\log_2 N \quad\text{versus}\quad N^2.$

For $N=1024$ this is 5120 versus about a million, a speed-up of about 200. The 2-D FFT applies the 1-D FFT to all rows and then to all columns.

Image degradation and restoration

Image restoration recovers an original image from a degraded version, using knowledge of the degradation process. Unlike enhancement (subjective), restoration is objective and model-based.

Degradation model

The input image $f(x,y)$ is acted on by a degradation function $h(x,y)$ (e.g. blur from motion, defocus or atmospheric turbulence) and then corrupted by additive noise $\eta(x,y)$:

$g(x,y) = h(x,y) * f(x,y) + \eta(x,y).$

In the frequency domain:

$G(u,v) = H(u,v)F(u,v) + N(u,v).$

Restoration estimates $\hat f(x,y)$ from $g$, knowledge of $H$ and the statistics of $\eta$.

Restoration methods

• Noise only ($H=1$): spatial filters (mean, median, order-statistics) and frequency-domain filters (band reject, notch) for periodic noise.
• Inverse filtering: $\hat F(u,v) = G(u,v)/H(u,v)$. It is simple but fails where $H$ is small or zero, because noise is greatly amplified.
• Wiener (minimum mean-square-error) filtering: $\hat F(u,v) = \frac{H^*(u,v)}{|H(u,v)|^2 + S_\eta(u,v)/S_f(u,v)}\,G(u,v)$ which balances deblurring and noise suppression.
• Constrained least squares filtering: needs only the noise variance and a smoothness constraint.
• Estimating $H$: by observation of the image, by experiment (imaging a point source to get the impulse response) or by mathematical modelling.

Process summary: model the degradation, estimate $H$ and the noise, apply a suitable inverse-type filter, and evaluate the result.

Why remove noise?

Noise is unwanted random variation in pixel values introduced during acquisition (sensor, low light, electronics) or transmission. It hides detail, degrades visual quality, produces false edges and errors in segmentation, feature extraction and recognition, and lowers compression efficiency. Removing it improves both appearance and the accuracy of later processing.

Order-statistics filters

These replace the centre pixel of a window $S_{xy}$ by a value chosen from the ranked (sorted) pixel values in the window. They are non-linear.

• Median filter: $\hat f(x,y) = \underset{(s,t)\in S_{xy}}{\text{median}}\{g(s,t)\}$. It removes salt-and-pepper (impulse) noise very well while blurring edges much less than a mean filter of the same size. Example: window $\{10, 12, 255, 11, 13, 12, 10, 0, 14\}$ sorted is $0,10,10,11,12,12,13,14,255$ and the median is 12.
• Max filter: $\hat f(x,y) = \max_{(s,t)\in S_{xy}}\{g(s,t)\}$. It finds the brightest points and reduces pepper (dark) noise, but brightens the image and enlarges bright objects.
• Min filter: $\hat f(x,y) = \min_{(s,t)\in S_{xy}}\{g(s,t)\}$. It finds the darkest points and reduces salt (white) noise, but darkens the image and enlarges dark objects.

Median is the best general choice for impulse noise; max and min are used when only one polarity of impulse is present.

Image segmentation

Segmentation partitions an image $R$ into regions $R_1,\dots,R_n$ so that the regions cover the image, are connected, do not overlap, each region satisfies a predicate (e.g. similar intensity), and adjacent regions differ. It subdivides an image into its objects and is the key step before representation and recognition. Segmentation methods are based on discontinuity (edges, points, lines) or similarity (thresholding, region growing).

Three basic grey-level discontinuities

All are detected by running a mask over the image and computing the response $R = \sum_{i=1}^{9} w_iz_i$, a weighted sum of the 3x3 neighbourhood. A pixel is marked if $|R| \ge T$.

1. Point detection: an isolated point differs sharply from its neighbours. Mask (Laplacian-type): $\begin{bmatrix}-1&-1&-1\\-1&8&-1\\-1&-1&-1\end{bmatrix}$ The response is near zero in flat regions and large at an isolated point.

2. Line detection: four masks detect lines at different orientations: $\text{Horizontal }\begin{bmatrix}-1&-1&-1\\2&2&2\\-1&-1&-1\end{bmatrix},\ \ +45^\circ\begin{bmatrix}-1&-1&2\\-1&2&-1\\2&-1&-1\end{bmatrix},$ $\text{Vertical }\begin{bmatrix}-1&2&-1\\-1&2&-1\\-1&2&-1\end{bmatrix},\ \ -45^\circ\begin{bmatrix}2&-1&-1\\-1&2&-1\\-1&-1&2\end{bmatrix}$ The mask with the largest response gives the line direction.

3. Edge detection: an edge is a set of connected pixels on the boundary between two regions with different grey levels. It is found using derivatives. The first derivative (gradient) $\nabla f = [G_x, G_y]^T$ has magnitude $\sqrt{G_x^2+G_y^2}\approx |G_x|+|G_y|$, computed with Prewitt or Sobel masks; edges are where the magnitude is high. The second derivative (Laplacian, Laplacian of Gaussian) has a zero crossing at an edge.

Periodic noise

Periodic noise comes from electrical or electromechanical interference during acquisition. It appears as a regular sinusoidal pattern added to the image. In the Fourier spectrum it shows up as concentrated bright spikes (impulses) at the noise frequencies, which makes it easy to remove in the frequency domain.

Band reject filter

A band reject filter attenuates (or removes) frequencies inside a band around a radius $D_0$ from the origin of the (centred) spectrum, with width $W$, and passes everything else. Since periodic noise spikes lie in a ring at radius about $D_0$, the filter suppresses them while leaving the rest of the image content.

Ideal band reject filter:

$H(u,v) = \begin{cases}1 & D(u,v) < D_0 - W/2\\ 0 & D_0 - W/2 \le D(u,v) \le D_0 + W/2\\ 1 & D(u,v) > D_0 + W/2\end{cases}$

Butterworth (order $n$):

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

Gaussian:

$H(u,v) = 1 - e^{-\frac12\left[\frac{D^2(u,v) - D_0^2}{D(u,v)W}\right]^2}$

where $D(u,v) = \sqrt{(u-M/2)^2 + (v-N/2)^2}$.

Procedure

1. Compute the DFT $G(u,v)$ of the noisy image and centre it.
2. Inspect the spectrum to find the radius $D_0$ and the width $W$ covering the noise spikes.
3. Multiply by $H(u,v)$: $\hat F(u,v) = H(u,v)G(u,v)$.
4. Take the inverse DFT (and undo the centring) to get the restored image.

Ideal filters cause ringing, so Butterworth or Gaussian types are preferred. If the noise is at only a few points, notch reject filters (a narrow band reject at single locations) lose less image information.

Region splitting and merging

Region growing starts from seed points; splitting and merging instead starts from the whole image, subdivides it, and then merges similar neighbours, and so needs no seeds.

Let $R$ be the entire image and $Q(R)$ a predicate that is TRUE when a region is homogeneous (e.g. $|z_{max} - z_{min}| \le T$, or all pixels within a given variance).

Algorithm

1. Initial split: if $Q(R)$ is FALSE, split the image into four disjoint quadrants.
2. Recursive splitting: for every region $R_i$ with $Q(R_i)$ FALSE, split it into four quadrants again. Continue until every region is homogeneous or reaches the minimum size (single pixel). The result is a quadtree.
3. Merging: examine adjacent regions $R_j$ and $R_k$; if $Q(R_j \cup R_k)$ is TRUE, merge them into one region.
4. Stop when no further merging is possible.

Splitting and merging can be done together (merge only when the union satisfies $Q$).

Example. An 8x8 image with a bright object on a dark background fails $Q$ as a whole and is split into four 4x4 quadrants. Quadrants that contain only background pass $Q$ and are kept; the quadrant containing the object edge is split again into 2x2 blocks. Finally adjacent homogeneous background blocks are merged into one background region and object blocks into one object region.

Properties: it is a top-down then bottom-up method, gives regions whose boundaries are aligned with quadtree blocks (hence blocky boundaries) and depends on the choice of predicate $Q$.

Interpixel redundancy

Interpixel (spatial or temporal) redundancy exists because the value of a pixel can be predicted fairly well from its neighbours: adjacent pixels are correlated, so each pixel carries little new information. Coding each pixel independently, as in a fixed-length code, wastes bits.

Identification

• Autocorrelation: compute the normalised autocorrelation along a row, for example $\gamma(\Delta n) = \frac{A(\Delta n)}{A(0)},\qquad A(\Delta n) = \frac{1}{N-\Delta n}\sum_{y=0}^{N-1-\Delta n} f(x,y)\,f(x,y+\Delta n).$ High values of $\gamma$ for small shifts $\Delta n$ (decaying slowly) show strong correlation, i.e. interpixel redundancy.
• The grey-level histogram may be identical for two images, yet their autocorrelation differs, showing redundancy that the histogram (coding redundancy) cannot reveal.

Exploitation (removal)

The 2-D pixel array is transformed into a more efficient representation, a mapping, which is usually reversible:

• Run-length coding: a run of identical pixels is stored as (value, length). E.g. 0000 1111 1100 becomes $(0,4),(1,6),(0,2)$. Effective for binary and graphic images.
• Predictive (differential) coding: store the difference $e_n = f_n - \hat f_n$ from the predicted value (e.g. the previous pixel); the differences are small and concentrated near zero, which a variable-length code such as Huffman codes in fewer bits.
• Transform coding: transform blocks (DCT as in JPEG) so that energy is packed into a few coefficients.
• Bit-plane coding: code each bit plane separately, since higher planes are highly correlated.

The mapped data are then coded with a variable-length code to achieve compression.

Erosion

Erosion is a morphological operation that shrinks or thins objects in a binary image. For an image $A$ and a structuring element $B$, both sets in $\mathbb{Z}^2$:

$A \ominus B = \{\,z \mid (B)_z \subseteq A\,\}$

The result is the set of all positions $z$ of the origin of $B$ such that $B$, translated to $z$, lies completely inside $A$. In practice, slide $B$ over the image; the output pixel is 1 only if every 1-pixel of $B$ lies over a 1-pixel of $A$.

Effects: objects get smaller, small objects and thin protrusions (noise) disappear, holes get larger, and objects joined by thin bridges are separated. It is the dual of dilation: $(A\ominus B)^c = A^c \oplus \hat B$.

Example. Let $B$ be a 3x3 square of ones (origin at the centre) and let $A$ contain a 4x5 block of ones (rows 1-4, columns 1-5 below) plus a single stray pixel:

0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0
0 1 1 1 1 1 0 0
0 1 1 1 1 1 0 1
0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0

A pixel survives only if its whole 3x3 neighbourhood is 1. Only the interior pixels of the block satisfy this: rows 2-3 and columns 2-4. The isolated pixel at the right has no full neighbourhood and vanishes.

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

The 4x5 block is reduced to 2x3, i.e. shrunk by one pixel on every side, and the noise pixel is removed. Erosion is used for noise removal, and with dilation forms opening, $A\circ B = (A\ominus B)\oplus B$.

Signature. A signature is a 1-D functional representation of a 2-D boundary. The boundary is converted into a function of one variable, which is easier to describe than the original curve. The most common signature plots the distance $r(\theta)$ from the centroid to the boundary points against the angle $\theta$.

• A circle gives a constant $r(\theta)=R$.
• A square gives a periodic function that repeats four times with peaks at the corners.
• Properties are then read from the 1-D plot, such as the number of peaks, the maximum and minimum, and the variance.
• The signature is invariant to translation. It is made invariant to scale by normalising $r$ to the range $[0,1]$. It is made invariant to rotation by always starting at the farthest point from the centroid.

Shape number. The shape number is a descriptor derived from the chain code of the boundary.

1. Write the 4- or 8-directional chain code of the boundary.
2. Take the first difference: the number of counter-clockwise direction changes between consecutive code elements (circular, mod 4 or mod 8). This makes the code rotation invariant.
3. Circularly rotate the difference sequence so that it forms the integer of minimum magnitude. This integer is the shape number.

Example: for the 4-directional chain code $0\,0\,3\,0\,3\,2\,2\,1\,2\,1$ the first difference is found element by element as $(c_i-c_{i-1})\bmod 4$ (the first element uses the last), and the sequence is then rotated to its minimum value. The first difference is $3\,0\,3\,1\,3\,3\,0\,3\,1\,3$ and the minimum circular rotation, the shape number, is $0\,3\,1\,3\,3\,0\,3\,1\,3\,3$ (order 10).

The number of digits is the order $n$ of the shape. Two shapes with the same order and the same shape number are the same shape irrespective of orientation. The order also measures how closely the shape matches a given rectangle.

Pattern. A pattern is an arrangement of descriptors (features) that represents an object, for example a vector $\mathbf{x}=(x_1,x_2,\dots,x_n)^T$ of measurements such as area, perimeter and mean intensity.

Pattern class. A pattern class is a family of patterns that share common properties. Classes are denoted $\omega_1,\omega_2,\dots,\omega_W$, for example the classes of digits 0 to 9 or of letters. Pattern recognition assigns an unknown pattern to one of these classes.

Detecting foreground and background. The usual approach is thresholding-based segmentation:

1. Compute the histogram of the grey levels. An image with a bright object on a dark background (or the reverse) has a bimodal histogram, with one mode for the background and one for the object.
2. Choose a threshold $T$ in the valley between the modes. $T$ can be chosen manually, by the iterative global method, or automatically by Otsu's method, which maximises the between-class variance.
3. Apply the threshold:

$g(x,y)=\begin{cases}1 & f(x,y)>T\\ 0 & f(x,y)\le T\end{cases}$

Pixels with $g=1$ form the foreground (object) and pixels with $g=0$ form the background. When illumination is uneven, a local or adaptive threshold is used instead, computing $T$ in each small neighbourhood. The binary result can be cleaned with morphological opening and closing, and connected-component labelling then separates individual objects.

Linear filter. A spatial filter is linear if its output is a weighted sum of the pixels in the neighbourhood, so that it obeys superposition: $T[af_1+bf_2]=aT[f_1]+bT[f_2]$. For a $3\times3$ mask,

$g(x,y)=\sum_{s=-1}^{1}\sum_{t=-1}^{1} w(s,t)\,f(x+s,y+t)$

Examples are the averaging (mean) filter, the Gaussian filter and the Laplacian. Median and max filters are non-linear.

Histogram equalisation. Here $L=8$ (grey levels 0 to 7) and the total number of pixels is $n=25+10+35+50=120$. The mapping is

$s_k=\text{round}\big((L-1)\,\text{CDF}(r_k)\big)=\text{round}\Big(7\sum_{j\le k}\frac{n_j}{n}\Big)$

Equalised histogram:

The original levels $\{1,3,4,5\}$ are spread to $\{1,2,4,7\}$, so the occupied grey levels now reach the top of the dynamic range (7). The total count is still $25+10+35+50=120$. A discrete histogram cannot become perfectly flat, but the contrast is clearly stretched.

Forward 2-D DFT. For an $M\times N$ image $f(x,y)$:

$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$

Inverse 2-D DFT.

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

(The $\frac1{MN}$ factor may instead be placed in the forward transform, or $\frac1{\sqrt{MN}}$ in both.)

Properties of the DFT.

1. Separability. The 2-D DFT is computed as two 1-D DFTs: first along rows, then along columns. This reduces the cost and allows the FFT to be used.
2. Linearity. $af_1+bf_2 \leftrightarrow aF_1+bF_2$.
3. Translation. $f(x-x_0,y-y_0)\leftrightarrow F(u,v)e^{-j2\pi(ux_0/M+vy_0/N)}$. Only the phase changes, so the magnitude spectrum is unchanged. Also $f(x,y)e^{j2\pi(u_0x/M+v_0y/N)}\leftrightarrow F(u-u_0,v-v_0)$. Multiplying by $(-1)^{x+y}$ shifts the origin to the centre $(M/2,N/2)$.
4. Periodicity. $F(u,v)=F(u+M,v)=F(u,v+N)$, and likewise in the spatial domain.
5. Conjugate symmetry. For real $f$, $F(u,v)=F^*(-u,-v)$, so $|F(u,v)|=|F(-u,-v)|$. The spectrum is symmetric about the origin.
6. Rotation. Rotating $f$ by $\theta_0$ rotates $F$ by the same angle.
7. Scaling. $f(ax,by)\leftrightarrow \frac{1}{|ab|}F(u/a,v/b)$. Compressing in space expands the spectrum.
8. Average value. $F(0,0)=MN\bar f$, the DC term.
9. Convolution theorem. $f*h\leftrightarrow F\cdot H$ and $f\cdot h\leftrightarrow \frac{1}{MN}F*H$. This is the basis of frequency-domain filtering.
10. Parseval (energy conservation). $\sum|f|^2=\frac1{MN}\sum|F|^2$.
11. Distributivity. The DFT distributes over addition but not over multiplication.

Noise models. Two common noise models are the following.

1. Gaussian noise. The noise intensity $z$ has the PDF $p(z)=\frac{1}{\sqrt{2\pi}\sigma}e^{-(z-\mu)^2/2\sigma^2}$. It models electronic circuit noise and sensor noise at low light.
2. Salt-and-pepper (impulse) noise. Pixels randomly take the minimum value (pepper, probability $P_a$) or the maximum value (salt, probability $P_b$). It is caused by faulty switching or transmission errors and is removed well by a median filter.

Others are Rayleigh, gamma (Erlang), exponential and uniform noise.

Huffman coding. The value $0.7$ for $r_4$ is taken as $0.07$. Huffman coding depends only on the relative weights, so the construction is the same either way.

Sorted weights: $r_0=0.40$, $r_3=0.25$, $r_1=0.18$, $r_2=0.10$, $r_4=0.07$, $r_5=0.05$.

Source reduction:

Assigning 0/1 back along the tree gives:

Average length with the given weights (total 1.05):

$L=\frac{0.40(1)+0.25(2)+0.18(3)+0.10(4)+0.07(5)+0.05(5)}{1.05}=\frac{2.44}{1.05}\approx 2.32\ \text{bits/symbol}$

A fixed-length code needs 3 bits/symbol, so the Huffman code saves about 23%. The code is prefix-free, so it is uniquely decodable.

Region. A region is a connected subset $R$ of the image's pixels, all of which satisfy a common property such as similar intensity, colour or texture. It is a connected set of pixels in which every pixel can be reached from any other through neighbouring pixels of the set. Regions are the result of region-based segmentation.

Boundary (border). The boundary of a region $R$ is the set of pixels in $R$ that have at least one neighbour outside $R$. It is the contour that separates the region from its background or from adjacent regions. Boundaries are found by edge detection or by contour tracing, and are described with chain codes, signatures and so on.

Elements of visual perception.

• Structure of the human eye. The cornea, lens, iris and pupil focus light onto the retina. The retina contains cones (photopic, colour, fine detail) and rods (scotopic, low light).
• Image formation in the eye. The lens changes its focal length to focus objects on the retina.
• Brightness adaptation. The eye adapts over a very large range of intensities, but only a small range can be discriminated at one time.
• Brightness discrimination (Weber ratio). The just-noticeable change in intensity relative to the background intensity.
• Simultaneous contrast. The perceived brightness of a region depends on its surroundings.
• Mach bands. Overshoot or undershoot is perceived near sharp intensity edges.
• Optical illusions.

Implications of periodicity and symmetry (Fourier transform).

• Periodicity. The DFT is periodic: $F(u,v)=F(u+M,v)=F(u,v+N)$. The transform of the image therefore repeats, and the image itself is implicitly treated as periodic. As a result:
  • One period of $M\times N$ values is enough to describe the transform.
  • The DC (low-frequency) terms sit at the corners of the array. Multiplying $f(x,y)$ by $(-1)^{x+y}$ moves the origin to the centre so that the spectrum is displayed as one complete period.
  • Convolution through the DFT is circular, so the images must be zero-padded to avoid wrap-around error.
  • The sharp discontinuity between opposite image borders causes leakage, which appears as streaks along the axes.
• Symmetry. For a real image, $F(u,v)=F^*(-u,-v)$, so the magnitude is even and the phase is odd. Consequently:
  • Only about half of the spectrum needs to be computed or stored, because the other half is its conjugate.
  • The spectrum is symmetric about the origin.
  • Filter transfer functions are made symmetric so that the filtered image remains real.

Lossless predictive coding. This removes interpixel redundancy by coding only the new information in each pixel. It needs no quantiser, so the reconstruction is exact.

• The predictor estimates the current pixel from previous pixels: $\hat f_n=\text{round}\big[\sum_{i=1}^{m}\alpha_i f_{n-i}\big]$. For example, $\hat f_n=f_{n-1}$ (previous pixel).
• The prediction error is $e_n=f_n-\hat f_n$.
• The encoder sends $e_n$ with a variable-length code such as Huffman. Because errors are concentrated near zero, the error histogram has low entropy and needs fewer bits than the raw pixels.
• The decoder uses the same predictor and rebuilds $f_n=e_n+\hat f_n$ exactly.

Example: for the row 100, 102, 103, 103, 101 the errors are 100 (first pixel), 2, 1, 0, $-2$.

Chain codes. A chain code represents a boundary as a connected sequence of straight-line segments of fixed length and direction. Starting from a chosen point, the boundary is traced (usually clockwise) and each step is coded by its direction number.

• 4-directional code: 0 = right, 1 = up, 2 = left, 3 = down.
• 8-directional code: 0 = east, 1 = north-east, 2 = north, 3 = north-west, 4 = west, 5 = south-west, 6 = south, 7 = south-east.

Example: a square traced anticlockwise from its lower-left corner (right, up, left, down) has the 4-directional chain code $0\,1\,2\,3$. A $2\times2$ square traced the same way gives $0\,0\,1\,1\,2\,2\,3\,3$.

Chain codes are compact, but they have three drawbacks. The code depends on the starting point, on the orientation (rotation), and on the scale (sampling grid).

Making the code invariant.

• Starting point. Treat the code as a circular sequence and rotate it so that it forms the integer of minimum magnitude.
• Rotation. Use the first difference. Count the number of counter-clockwise direction changes between consecutive elements (mod 4 or mod 8). For the code $1\,0\,3\,3$ (4-directional) the first difference is $3\,3\,3\,0$ (taking the last element as the predecessor of the first). It does not change when the boundary is rotated by multiples of 90 degrees (45 degrees for the 8-directional code).
• Scaling. Resample the boundary onto a coarser or finer grid of a fixed size (for example, the same number of boundary points or the same grid spacing) before coding, so that objects of different size give the same code.
• Combining the minimum-magnitude rotation with the first difference gives the shape number, which is invariant to both starting point and rotation.

Lines are detected by convolving the image with a mask that responds most strongly to a thin line of one orientation. The mask coefficients sum to zero, so flat regions give zero response.

Masks.

Horizontal line:

$\begin{bmatrix}-1&-1&-1\\ 2&2&2\\ -1&-1&-1\end{bmatrix}$

Vertical line:

$\begin{bmatrix}-1&2&-1\\ -1&2&-1\\ -1&2&-1\end{bmatrix}$

(The $\pm45^\circ$ masks are similar.) The response at a point is $R=\sum_{i=1}^{9} w_iz_i$. A point belongs to a line if $|R|\ge T$ for a chosen threshold $T$. When all four masks are applied, the line orientation is that of the mask giving the largest $|R|$.

Example. Take a $3\times3$ region containing a vertical one-pixel-wide line of intensity 10 on a background of 0:

$\begin{bmatrix}0&10&0\\ 0&10&0\\ 0&10&0\end{bmatrix}$

• Vertical mask: $R=3(2\cdot10)+0=60$. This is a strong response.
• Horizontal mask: the first and last rows give $-10$ each and the middle row gives $+20$, so $R=-10+20-10=0$.

Only the vertical mask responds, so the line is detected as vertical. Thresholding $|R|$ then marks the line pixels.

Basic global thresholding picks one threshold $T$ for the whole image, found iteratively from the histogram.

Algorithm.

1. Select an initial estimate of $T$, for example the mean intensity of the image, or the average of its minimum and maximum grey levels.
2. Segment the image with $T$. This divides the pixels into two groups: $G_1$ (pixels with intensity $>T$) and $G_2$ (pixels with intensity $\le T$).
3. Compute the mean intensities $m_1$ of $G_1$ and $m_2$ of $G_2$.
4. Compute the new threshold $T=\tfrac12(m_1+m_2)$.
5. Repeat steps 2 to 4 until the difference between successive values of $T$ is smaller than a predefined parameter $\Delta T$.
6. Segment the image with the final $T$:

$g(x,y)=\begin{cases}1&f(x,y)>T\\0&f(x,y)\le T\end{cases}$

The method works well when the histogram is clearly bimodal and illumination is uniform. With uneven illumination, adaptive or Otsu's thresholding is used instead.

Spatial-domain representation. A digital image is a 2-D function $f(x,y)$ sampled on a grid, represented as an $M\times N$ matrix:

$f(x,y)=\begin{bmatrix}f(0,0)&\cdots&f(0,N-1)\\ \vdots&&\vdots\\ f(M-1,0)&\cdots&f(M-1,N-1)\end{bmatrix}$

Here $(x,y)$ are the spatial coordinates (row, column) and $f$ is the intensity (grey level), an integer from $0$ to $2^k-1$ for a $k$-bit image. Spatial-domain processing works directly on the pixels: $g(x,y)=T[f(x,y)]$.

Intensity level slicing and bit-plane slicing.

Pattern recognition. Pattern recognition is the automatic assignment of an unknown pattern (a feature vector extracted from an image or signal) to one of a set of known pattern classes. The steps are image acquisition and pre-processing, segmentation, feature extraction, and classification (decision theoretic or structural). Examples are character recognition, face recognition and fingerprint identification.

Mexican hat filter. The Mexican hat is the Laplacian of Gaussian (LoG) filter. Its name comes from the shape of its 2-D profile, which looks like a sombrero.

$h(x,y)=\nabla^2 G(x,y)=\frac{x^2+y^2-2\sigma^2}{\sigma^4}\,e^{-\frac{x^2+y^2}{2\sigma^2}}$

(sometimes defined with a negative sign, which gives the "hat" shape facing upward). It has a positive centre and a negative surrounding ring, and its coefficients sum to zero.

• It first smooths the image with a Gaussian (the scale $\sigma$ controls the amount of smoothing and the size of the features detected), then applies the Laplacian. This reduces the Laplacian's noise sensitivity.
• Edges are located at the zero crossings of the output.
• In pattern recognition it is used for blob detection, edge detection and as a matched filter for feature detection at a given scale. It is also close to the way the human retina's receptive fields respond (centre-surround).
• A typical $5\times5$ approximation is

$\begin{bmatrix}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\end{bmatrix}$

Usage of derivative-based filters. Derivative filters respond to changes in intensity, so they are used for:

• Image sharpening and enhancement of fine detail (Laplacian, unsharp masking).
• Edge detection (first derivative: Sobel, Prewitt, Roberts; second derivative: Laplacian, LoG).
• Detecting isolated points and thin lines.
• Feature extraction for segmentation and recognition.

The first derivative is non-zero along ramps and at steps and gives thick edges. The second derivative responds strongly to fine detail, gives a double response at edges, and is zero in flat areas and along ramps.

Laplacian mask. The Laplacian is isotropic: $\nabla^2 f=\dfrac{\partial^2 f}{\partial x^2}+\dfrac{\partial^2 f}{\partial y^2}$.

The discrete second derivative in each direction is

$\frac{\partial^2 f}{\partial x^2}=f(x+1,y)+f(x-1,y)-2f(x,y)$

$\frac{\partial^2 f}{\partial y^2}=f(x,y+1)+f(x,y-1)-2f(x,y)$

Adding them:

$\nabla^2 f=f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y)$

The mask is therefore

$\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}$

Including the diagonal terms gives the 8-neighbour version with centre $-8$ and all eight neighbours $1$. The sign-reversed versions have centre $+4$ (or $+8$) and neighbours $-1$. For sharpening, $g=f-\nabla^2 f$ is used with the negative-centre mask and $g=f+\nabla^2 f$ with the positive-centre mask.

Hough transform (slope-intercept form). A point $(x_i,y_i)$ lies on the line $y=mx+c$ if $c=y_i-mx_i$. Each image point becomes a line in the $(m,c)$ parameter space. Points that are collinear in the image give lines in parameter space that all intersect at one point $(m,c)$, which gives the line they share.

The third point is $(3,-3)$. With $(3,3)$ as printed, the three points are not collinear (the line through $(1,1)$ and $(-2,7)$ gives $y=-3$ at $x=3$), so the question's third point is read as $(3,-3)$.

Parameter-space lines.

• $(1,1)$: $c=1-m$
• $(-2,7)$: $c=7+2m$
• $(3,-3)$: $c=-3-3m$

Intersection of the first two:

$1-m=7+2m\Rightarrow 3m=-6\Rightarrow m=-2,\quad c=1-(-2)=3$

Check with the third: $c=-3-3(-2)=-3+6=3$. The third line also passes through $(m,c)=(-2,3)$.

All three lines in parameter space meet at the single point $(-2,3)$, so the three image points are collinear.

Equation of the line:

$y=-2x+3\quad\text{or}\quad 2x+y-3=0$

Check: $(1,1)$: $-2+3=1$ yes. $(-2,7)$: $4+3=7$ yes. $(3,-3)$: $-6+3=-3$ yes.

Because the vertical lines cannot be represented by $m$, the normal form $\rho=x\cos\theta+y\sin\theta$ is used in practice, and the accumulator cell with the most votes gives the line.

High frequency emphasis filter versus Laplacian filter.

Histogram equalisation. The image has 25 pixels with $L=8$ levels.

Counts: level 2 occurs 6 times, level 3 occurs 14 times, level 4 occurs 5 times (6 + 14 + 5 = 25).

Levels 0, 1, 5, 6, 7 do not occur. The mapping is $2\to2$, $3\to6$, $4\to7$.

Output image:

The grey levels 2, 3 and 4 are spread out to 2, 6 and 7, so the contrast of the image increases.

Noise. Noise is an unwanted random variation of pixel intensity that is not part of the true scene. It is introduced during acquisition (sensor noise, low light, temperature), transmission (channel errors) or digitisation. Common types are Gaussian, salt-and-pepper (impulse), Rayleigh, gamma, exponential and uniform noise, and periodic noise caused by electrical interference.

Degradation model. Image degradation is modelled as a degradation function $h$ followed by additive noise $\eta$:

$g(x,y)=h(x,y)*f(x,y)+\eta(x,y)$

where $f$ is the original image, $g$ is the observed (degraded) image, $h$ is the point spread function, such as motion blur or defocus, and $*$ is spatial convolution. In the frequency domain:

$G(u,v)=H(u,v)F(u,v)+N(u,v)$

Restoration model. Restoration finds an estimate $\hat f$ of the original image, using knowledge of $h$ and of the noise statistics, by applying a restoration filter:

$f(x,y)\xrightarrow{\;h\;}\xrightarrow{\;+\eta\;}g(x,y)\xrightarrow{\;\text{restoration filter}\;}\hat f(x,y)$

• Only noise present ($H=1$): $g=f+\eta$. Spatial filters are used: mean (arithmetic, geometric, harmonic, contraharmonic), median, max, min, midpoint and alpha-trimmed mean filters. Periodic noise is removed in the frequency domain with band-reject, band-pass and notch filters.
• Inverse filtering: $\hat F(u,v)=\dfrac{G(u,v)}{H(u,v)}=F+\dfrac{N}{H}$. It fails where $H$ is small or zero because the noise is amplified.
• Wiener (minimum mean square error) filtering:

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

where $S_\eta$ and $S_f$ are the power spectra of the noise and the original image. It balances de-blurring against noise suppression and, when the noise-to-signal ratio is replaced by a constant $K$, it is the parametric Wiener filter.

• Constrained least squares filtering uses only the noise mean and variance, and gives a smoothness-constrained estimate.
• The degradation function $h$ is obtained by observation, by experiment or by mathematical modelling (for example, uniform linear motion or atmospheric turbulence).

Spatial domain versus frequency domain.

2-D DFT of the $4\times4$ all-ones image. With $M=N=4$,

$F(u,v)=\sum_{x=0}^{3}\sum_{y=0}^{3} f(x,y)\,e^{-j2\pi(ux+vy)/4}$

Since $f(x,y)=1$ for all pixels, this factors into two 1-D sums:

$F(u,v)=\Big(\sum_{x=0}^{3}e^{-j2\pi ux/4}\Big)\Big(\sum_{y=0}^{3}e^{-j2\pi vy/4}\Big)$

For $u=0$ the sum is $4$. For $u=1,2,3$ it is a sum of the fourth roots of unity, and equals $0$ (for $u=1$: $1+(-j)+(-1)+j=0$). So $F(u,v)\ne0$ only when $u=v=0$:

$F(0,0)=4\times4=16$

$F(u,v)=\begin{bmatrix}16&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&0\end{bmatrix}$

(With the $\frac{1}{MN}$ factor placed in the forward transform, $F(0,0)=1$.) The image is a constant, so all its energy is in the DC term (the average intensity times $MN$), and there are no higher frequencies.