Image Processing and Computer Vision (CS-803 (A)) Notes

How unit 2 is examined

This unit covers how shapes are represented and described, how images are segmented, and how edges, lines and curves are found and fitted; segmentation, boundary descriptors, thresholding and the Hough transform carry the marks.

Representation schemes

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Representation schemes are ways of storing the boundary or the region of an object in a compact form that keeps its shape and suits later description and recognition.</mark>

Key points.

Boundary (external) representations describe the outline of the object and suit shape-based tasks.
Regional (internal) representations describe the pixels inside the object, such as its skeleton, and suit texture or colour tasks.
A chain code stores the boundary as a start point plus a sequence of direction numbers (4- or 8-directional).
Polygonal approximation replaces the boundary by a polygon with few vertices, fitted until the error is within a tolerance.
A signature is a 1-D function of the boundary, such as distance from the centroid against angle.
A skeleton (medial axis) reduces a region to thin lines that keep its topology.
Choose boundary schemes when shape matters and regional schemes when internal properties matter.

Asked: [7 marks] (May 2023) What are the various representation schemes of digital image processing? Explain.

Boundary descriptors

Definition. <mark>Boundary descriptors are numerical features computed from the outline of an object that describe its shape and can be compared for recognition.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 467 80" width="467" height="80" role="img" aria-label="Boundary description flow. Img = segmented object, Bnd = traced boundary points, Rep = chain code or Fourier series, Des = invariant descriptor"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah3)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah3)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah3)"/><g class="wl"><rect x="81" y="31" width="47.1" height="18" rx="9"/><text class="t" x="104.5" y="40" dy=".35em" text-anchor="middle">trace</text></g><g class="wl"><rect x="213.1" y="31" width="40.8" height="18" rx="9"/><text class="t" x="233.5" y="40" dy=".35em" text-anchor="middle">code</text></g><g class="wl"><rect x="324.6" y="31" width="75.9" height="18" rx="9"/><text class="t" x="362.5" y="40" dy=".35em" text-anchor="middle">normalise</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Img</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">Bnd</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Rep</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">Des</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Boundary description flow. Img = segmented object, Bnd = traced boundary points, Rep = chain code or Fourier series, Des = invariant descriptor</figcaption></figure>

Key points.

Chain code: the boundary is traversed clockwise from a start pixel and each step is coded 0-7 (8-connected) by direction; the first difference of the code makes it rotation invariant.
Shape number: the chain code's first difference, rotated to give the smallest integer, is unique to the shape and independent of starting point and rotation.
Fourier descriptors: boundary points are written as complex numbers $s(k)=x(k)+jy(k)$ and their DFT coefficients describe the shape, low-order terms giving the coarse shape.
Simple descriptors are length (perimeter), diameter, eccentricity and curvature; signatures and moments are also used.
Good descriptors are invariant to translation, rotation and scale, and are compact.
Fourier descriptors are made invariant by dropping $a(0)$ (translation), taking magnitudes (rotation) and dividing by $|a(1)|$ (scale).
Importance: descriptors reduce a shape to a few numbers, so classification and matching become fast and noise-tolerant.

Region descriptors (part of Q2): they describe the pixels inside the object, e.g. area, centroid, texture, moments and topology; boundary descriptors describe the outline, region descriptors describe the content, and recognition uses both.

Answer frame. Open with the definition; draw the flow diagram with a small chain-coded boundary; develop points 1-6 in order; add one line defining region descriptors when the question says "boundary and region"; close with importance in recognition.

Asked: [7 marks] (May 2023, May 2024) Discuss/explain boundary descriptors in detail with a neat diagram. Asked: [7 marks] (Jun 2025) What are boundary and region descriptors in image processing? Explain their importance in image analysis.

Region descriptors

Definition. <mark>Region descriptors describe an object by the pixels it contains rather than by its outline.</mark>

Key points.

Simple ones are area (pixel count), perimeter, centroid, and compactness $=P^2/A$.
Texture descriptors measure smoothness, coarseness and regularity, for example from the grey-level co-occurrence matrix.
Moments summarise the shape and intensity distribution; the central moments are translation invariant.
Topological descriptors, such as the number of holes and the Euler number $E=C-H$, do not change under stretching.

Thresholding

Definition. <mark>Thresholding converts a grey-scale image to a binary one by setting pixels with $f(x,y)>T$ to object (1) and the rest to background (0).</mark>

Key points.

It works because object and background form separate peaks in the histogram, and $T$ is placed in the valley between them.
Global thresholding uses one $T$ for the whole image; iterate: pick $T$, find the mean of each side, set $T$ to their average, repeat until it stops changing.
Otsu's method picks the $T$ that maximises the between-class variance $\sigma_B^2=w_0w_1(\mu_0-\mu_1)^2$.
Adaptive (local) thresholding computes a separate $T$ for each pixel from its neighbourhood mean or Gaussian-weighted mean, so it handles uneven illumination.
Uses: segmentation, binarisation of documents, and object counting.
Limitations: it fails when the histogram is not bimodal, ignores spatial information, and is sensitive to noise and uneven lighting.

Point	Global	Adaptive
Threshold	One value for the image	One per pixel or window
Illumination	Needs even lighting	Copes with uneven lighting
Speed	Fast	Slower
Example	Otsu	Local mean or Gaussian

Answer frame. Open with the definition and $g(x,y)$ rule; sketch a bimodal histogram with $T$ in the valley; develop points 2-4 and the table; close with limitations (point 6) if "limitations" is asked.

Asked: [7 marks] (May 2022) Explain global and adaptive thresholding techniques. Asked: [7 marks] (May 2023) What is Thresholding? Discuss its use and also write its limitations.

Segmentation

Definition. <mark>Image segmentation is the process of partitioning an image into meaningful, non-overlapping regions, such as objects and background, so that each region is homogeneous in some property like intensity, colour or texture.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 805 194" width="805" height="194" role="img" aria-label="Two families of segmentation"><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="316.6" y1="37" x2="120.5" y2="101"/><line class="e" x1="316.6" y1="37" x2="512.8" y2="101"/><line class="e" x1="120.5" y1="101" x2="43.5" y2="165"/><line class="e" x1="120.5" y1="101" x2="118.5" y2="165"/><line class="e" x1="120.5" y1="101" x2="197.5" y2="165"/><line class="e" x1="512.8" y1="101" x2="304" y2="165"/><line class="e" x1="512.8" y1="101" x2="442" y2="165"/><line class="e" x1="512.8" y1="101" x2="591.5" y2="165"/><line class="e" x1="512.8" y1="101" x2="721.5" y2="165"/><rect class="n" x="259.6" y="22" width="114" height="30" rx="8"/><text class="t" x="316.6" y="37" dy=".35em" text-anchor="middle">Segmentation</text><rect class="n" x="36" y="86" width="169" height="30" rx="8"/><text class="t" x="120.5" y="101" dy=".35em" text-anchor="middle">Discontinuity-based</text><rect class="n" x="14" y="150" width="59" height="30" rx="8"/><text class="t" x="43.5" y="165" dy=".35em" text-anchor="middle">Edges</text><rect class="n" x="89" y="150" width="59" height="30" rx="8"/><text class="t" x="118.5" y="165" dy=".35em" text-anchor="middle">Lines</text><rect class="n" x="164" y="150" width="67" height="30" rx="8"/><text class="t" x="197.5" y="165" dy=".35em" text-anchor="middle">Points</text><rect class="n" x="455.8" y="86" width="114" height="30" rx="8"/><text class="t" x="512.8" y="101" dy=".35em" text-anchor="middle">Region-based</text><rect class="n" x="247" y="150" width="114" height="30" rx="8"/><text class="t" x="304" y="165" dy=".35em" text-anchor="middle">Thresholding</text><rect class="n" x="377" y="150" width="130" height="30" rx="8"/><text class="t" x="442" y="165" dy=".35em" text-anchor="middle">Region growing</text><rect class="n" x="523" y="150" width="137" height="30" rx="8"/><text class="t" x="591.5" y="165" dy=".35em" text-anchor="middle">Split and merge</text><rect class="n" x="676" y="150" width="91" height="30" rx="8"/><text class="t" x="721.5" y="165" dy=".35em" text-anchor="middle">Watershed</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Two families of segmentation</figcaption></figure>

Key points.

Its goal is to simplify the image so that each object can be separated and analysed; it is the step after restoration and before description.
Discontinuity-based methods find sudden intensity changes (points, lines, edges) and link them into boundaries.
Region-based methods find the regions directly by grouping similar pixels, so they give closed regions.
Region growing starts from seed pixels and adds neighbours that satisfy a similarity test, for example intensity within a tolerance of the region mean.
Splitting and merging divides non-uniform regions on a quadtree and merges similar neighbours.
Watershed treats the gradient image as a landscape and floods it from minima; the ridges where floods meet are the boundaries.
Thresholding separates objects by intensity (see Thresholding); in binary machine vision the result is a binary image.
Connected component labeling then gives each separate object its own label so that it can be counted and measured.

Related terms (Q9). Restoration recovers an image degraded by known blur or noise; compression reduces the data needed to store it; segmentation splits it into regions; morphological processing extracts shape using structuring elements (erosion, dilation).

Example. Segmenting coins on a dark table: threshold at Otsu's $T$, label the connected components, and count the labels to get the number of coins.

Answer frame. Open with the definition; draw the two-family tree; for Q8 develop thresholding (global, adaptive, Otsu) then labeling steps and close with a comparison line; for Q10 develop points 3-6 and state the advantage that regions come closed; for Q9 give one line and one application per term.

Asked: [7 marks] (Dec 2024, Jun 2025) What is image segmentation? Discuss thresholding and connected component labeling techniques (also: segmentation in binary machine vision). Asked: [7 marks] (May 2024) Define briefly: i) Image restoration ii) Compression iii) Segmentation iv) Morphological processing Asked: [7 marks] (May 2024) Explain the segmentation techniques that are based on finding the regions directly.

Connected component labeling

Definition. <mark>Connected component labeling assigns a unique label to every group of connected foreground pixels in a binary image.</mark>

Steps.

Step 1: Scan the image row by row, left to right.
Step 2: For a foreground pixel, look at its already-scanned neighbours (left, up; plus diagonals for 8-connectivity).
Step 3: If none is labeled, give the pixel a new label.
Step 4: If some are labeled, copy the smallest label and record the labels as equivalent.
Step 5: Second pass: replace every label by the smallest label of its equivalence class.

Key points.

The result lets each object be counted and measured separately.
4-connectivity and 8-connectivity give different counts, so state which is used.
The method needs two passes because a later pixel can join two earlier labels.

Hierarchal segmentation

Definition. <mark>Hierarchical segmentation builds a multi-level description of the image, from coarse to fine regions, usually with a pyramid or quadtree.</mark>

Key points.

Coarse levels find large objects cheaply and finer levels refine them.
Top-down methods split the image, bottom-up methods merge pixels.
Split-and-merge is the standard example.

Spatial clustering

Definition. <mark>Spatial clustering groups pixels into segments by clustering feature vectors, such as intensity, colour and position.</mark>

Key points.

K-means picks $k$ centres, assigns each pixel to the nearest centre and recomputes the centres until stable.
Including the $(x,y)$ position in the feature makes clusters spatially compact.
The number of clusters must be chosen beforehand.
Mean shift avoids this by moving each pixel to a density peak.

Split & merge

Definition. <mark>Split-and-merge segments an image by recursively splitting non-homogeneous regions into four quadrants and merging adjacent regions that are similar.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-03" viewBox="0 0 332 134" width="332" height="134" role="img" aria-label="Quadtree. A homogeneous quadrant stays whole; the non-homogeneous quadrant C splits into c1 to c4"><style>#dsfig-u2-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-03 .t{fill:#16181D;font-weight:500}#dsfig-u2-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-03 .dot{fill:#16181D}#dsfig-u2-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-03 .ah{fill:#454C5A}#dsfig-u2-03 .ah.hi{fill:#2340B8}#dsfig-u2-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-03 .e{stroke:#B1B7C3}html.dark #dsfig-u2-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-03 .t{fill:#E6E8ED}html.dark #dsfig-u2-03 .t.inv{fill:#0F1115}html.dark #dsfig-u2-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-03 .dot{fill:#E6E8ED}html.dark #dsfig-u2-03 .ann{fill:#8FA3FF}html.dark #dsfig-u2-03 .lbl{fill:#858D9C}html.dark #dsfig-u2-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-03 .ah{fill:#B1B7C3}html.dark #dsfig-u2-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="154" y1="39" x2="31" y2="103"/><line class="e" x1="154" y1="39" x2="81" y2="103"/><line class="e" x1="154" y1="39" x2="179" y2="103"/><line class="e" x1="154" y1="39" x2="277" y2="103"/><rect class="n" x="124.5" y="24" width="59" height="30" rx="8"/><text class="t" x="154" y="39" dy=".35em" text-anchor="middle">Image</text><circle class="n" cx="31" cy="103" r="17"/><text class="t" x="31" y="103" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="81" cy="103" r="17"/><text class="t" x="81" y="103" dy=".35em" text-anchor="middle">B</text><rect class="n" x="114" y="88" width="130" height="30" rx="8"/><text class="t" x="179" y="103" dy=".35em" text-anchor="middle">C(c1,c2,c3,c4)</text><circle class="n" cx="277" cy="103" r="17"/><text class="t" x="277" y="103" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Quadtree. A homogeneous quadrant stays whole; the non-homogeneous quadrant C splits into c1 to c4</figcaption></figure>

Key points.

Start with the whole image as one region.
Split any region that fails the homogeneity test $P(R)$, for example intensity variance below a limit, into four equal quadrants.
After splitting, merge adjacent regions whose union satisfies $P$.
Stop when no split or merge is possible.
The quadtree makes it fast, but regions can look blocky along quadrant edges.

Answer frame. Open with the definition; draw the quadtree; give points 1-4 as steps; close with the advantage (no seed needed, handles both over- and under-segmentation) and blocky-boundary drawback.

Asked: [7 marks] (Dec 2024) Describe the split-and-merge technique used in hierarchical segmentation.

Rule-based Segmentation

Definition. <mark>Rule-based segmentation uses explicit rules about object properties (grey level, size, shape, position) to decide which pixels or regions belong together.</mark>

Key points.

Rules come from domain knowledge, for example "sky is bright, at the top and blue".
Rules are applied to regions produced by a low-level segmentation, which are then merged or relabeled.
It suits known scenes but rules must be written afresh for each application.

Motion-based segmentation

Definition. <mark>Motion-based segmentation separates moving objects from the static background using changes between frames.</mark>

Key points.

The simplest method is frame differencing: pixels where $|f_t-f_{t-1}|>T$ are moving.
Background subtraction compares each frame with a modelled background.
Optical flow groups pixels having the same motion vector.
Camera motion and noise cause false detections.

Area Extraction: Concepts

Definition. <mark>Area extraction finds the regions of interest in an image by combining edge detection, thresholding and region methods.</mark>

Key points.

It delivers the region boundaries and pixel sets from which descriptors are computed.
Edge-based extraction links edge points into closed contours.
Region-based extraction grows or merges pixels into areas.
The Hough transform helps by finding lines and curves that bound areas.

Data-structures

Definition. <mark>Data structures for area extraction are the ways of storing image regions and edges so that they can be processed efficiently.</mark>

Key points.

A label image stores a region number for each pixel.
Chain codes store a boundary compactly.
Quadtrees store regions hierarchically and save space in uniform areas.
Edge lists or linked lists store edge points for edge linking.

Edge, Line-Linking

Definition. <mark>Line detection finds thin lines in an image with masks that respond strongly to a line of a given direction, based on the second derivative.</mark>

Key points.

A thin line is a sharp intensity change on both sides, so the second derivative (Laplacian-type) mask gives a strong response.
Four $3\times3$ masks detect horizontal, $+45^\circ$, vertical and $-45^\circ$ lines.
Each mask has weight 2 along the line direction and $-1$ elsewhere; weights sum to zero.
Convolve the image with all four; a pixel belongs to the line of the mask giving the largest $|R_i|$, if it exceeds a threshold $T$.
Edge points are then linked into lines using gradient magnitude and direction similarity of near neighbours.

Horizontal	$+45^\circ$	Vertical	$-45^\circ$
-1 -1 -1<br>2 2 2<br>-1 -1 -1	-1 -1 2<br>-1 2 -1<br>2 -1 -1	-1 2 -1<br>-1 2 -1<br>-1 2 -1	2 -1 -1<br>-1 2 -1<br>-1 -1 2

Asked: [7 marks] (May 2024) Explain how the line is detected in the image and give the masks that are used to detect it?

Hough transform

Definition. <mark>The Hough transform detects lines and curves by mapping each edge point to a curve in a parameter space and finding the points where many curves intersect, using a voting accumulator.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-04" viewBox="0 0 467 80" width="467" height="80" role="img" aria-label="Hough pipeline. Edg = edge points, Map = sinusoid per point, Acc = accumulator array in (rho, theta), Pk = peaks give the lines"><style>#dsfig-u2-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-04 .t{fill:#16181D;font-weight:500}#dsfig-u2-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-04 .dot{fill:#16181D}#dsfig-u2-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-04 .ah{fill:#454C5A}#dsfig-u2-04 .ah.hi{fill:#2340B8}#dsfig-u2-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-04 .e{stroke:#B1B7C3}html.dark #dsfig-u2-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-04 .t{fill:#E6E8ED}html.dark #dsfig-u2-04 .t.inv{fill:#0F1115}html.dark #dsfig-u2-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-04 .dot{fill:#E6E8ED}html.dark #dsfig-u2-04 .ann{fill:#8FA3FF}html.dark #dsfig-u2-04 .lbl{fill:#858D9C}html.dark #dsfig-u2-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-04 .ah{fill:#B1B7C3}html.dark #dsfig-u2-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah6)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah6)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah6)"/><g class="wl"><rect x="63.4" y="31" width="82.2" height="18" rx="9"/><text class="t" x="104.5" y="40" dy=".35em" text-anchor="middle">each_point</text></g><g class="wl"><rect x="213.1" y="31" width="40.8" height="18" rx="9"/><text class="t" x="233.5" y="40" dy=".35em" text-anchor="middle">vote</text></g><g class="wl"><rect x="339" y="31" width="47.1" height="18" rx="9"/><text class="t" x="362.5" y="40" dy=".35em" text-anchor="middle">peaks</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Edg</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">Map</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Acc</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">Pk</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Hough pipeline. Edg = edge points, Map = sinusoid per point, Acc = accumulator array in (rho, theta), Pk = peaks give the lines</figcaption></figure>

Derivation. The line $y=mx+c$ has infinite slope for vertical lines, so use the normal form. Drop a perpendicular of length $\rho$ from the origin to the line, at angle $\theta$ to the x-axis. Every point $(x,y)$ on the line satisfies $$\rho = x\cos\theta + y\sin\theta$$ For a fixed $(x,y)$ this is a sinusoid in the $(\rho,\theta)$ plane; points on one line give sinusoids meeting at a common $(\rho,\theta)$.

Steps.

Step 1: Detect edge points and quantise rho and theta into an accumulator A(rho, theta), initially 0.
Step 2: For each edge point (x, y) and each theta, compute rho = x cos(theta) + y sin(theta).
Step 3: Increment A(rho, theta).
Step 4: Peaks above a threshold in A are lines; read off rho and theta.

Key points.

A peak with count $N$ means $N$ edge points lie on that line, so it tolerates gaps and noise.
Example: points $(1,1),(2,2),(3,3)$ all give $\rho=0$ at $\theta=135^\circ$, so $A(0,135^\circ)=3$ and the line is $y=x$.
For circles $(x-a)^2+(y-b)^2=r^2$ the accumulator is 3-D in $(a,b,r)$.
Role in area extraction: after edge detection (gradient or Canny operators find edge points), Hough links them into complete lines and curves that bound areas.

Answer frame. Open with the principle; draw the pipeline and one sinusoid intersection sketch; give the derivation, then steps, then the example and circle extension; for Q6 first define edge detection and its operators, and close with its role in area extraction.

Asked: [7 marks] (May 2022, May 2024) Explain Hough transform with the help of suitable derivations. Asked: [7 marks] (Dec 2024) Explain edge detection and the Hough transform in area extraction.

Line fitting

Definition. ==Line fitting finds the line $y=mx+c$ that best represents a set of points.==

Key points.

Least squares minimises the vertical distances squared; it is poor for vertical lines.
Total least squares minimises perpendicular distances and handles all orientations.
Outliers distort the fit; RANSAC or the Hough transform is robust to them.

Curve fitting (Least-square fitting)

Definition. ==Least-square fitting chooses the curve parameters that minimise the sum of squared errors $E=\sum (y_i-f(x_i))^2$ between the data and the curve.==

Key points.

For the line $y=mx+c$ set $\partial E/\partial m=0$ and $\partial E/\partial c=0$ to get the normal equations.
Solution: $m=\dfrac{n\sum xy-\sum x\sum y}{n\sum x^2-(\sum x)^2}$ and $c=\dfrac{\sum y-m\sum x}{n}$.
Example: points $(1,2),(2,3),(3,5),(4,4)$ have $n=4$, $\sum x=10$, $\sum y=14$, $\sum xy=39$, $\sum x^2=30$, so $m=16/20$ and $c=(14-8)/4$; $y=0.8x+1.5$.
Polynomials fit the same way, giving a linear system in the coefficients.
Applications: fitting lines to edges, ellipses to boundaries, camera calibration and measurement.

Answer frame. Open with the error function $E$; derive the two normal equations; state $m$ and $c$; show the four-point example; close with applications.

Asked: [7 marks] (Dec 2024) Describe the least-square fitting technique in curve fitting and its applications.

Last-minute revision

Segmentation splits an image into homogeneous regions; two families: discontinuity-based and region-based.
Global threshold: $g=1$ if $f>T$; Otsu maximises $\sigma_B^2=w_0w_1(\mu_0-\mu_1)^2$.
Adaptive thresholding uses a local window, so it copes with uneven illumination.
Thresholding fails on non-bimodal histograms and noise.
Chain code: directions 0-7; first difference gives rotation invariance; smallest rotation gives the shape number.
Fourier descriptors: DFT of $x+jy$ boundary points.
Split and merge uses a quadtree and a homogeneity predicate $P$.
Line masks: 2 on the line, $-1$ elsewhere, four directions.
Hough normal form: $\rho=x\cos\theta+y\sin\theta$; peaks in the accumulator are lines; circles need $(a,b,r)$.
Least squares: $m=\dfrac{n\sum xy-\sum x\sum y}{n\sum x^2-(\sum x)^2}$, $c=\dfrac{\sum y-m\sum x}{n}$.
Example fit: $(1,2),(2,3),(3,5),(4,4)$ gives $y=0.8x+1.5$.

Memory hooks

Boundary = outline, region = inside.
Otsu = "best split of the histogram", maximum between-class variance.
Quadtree: split into 4, merge the like.
Hough: every point votes, the crowd wins.
Line mask: 2 down the middle, $-1$ around.

Coverage checklist

Representation schemes: Q7.
Boundary descriptors: Q1, Q2.
Region descriptors: covered in Boundary descriptors and its own section.
Thresholding: Q12, Q13.
Segmentation: Q8, Q9, Q10.
Connected component labeling: Q8 (steps).
Hierarchal segmentation: linked to Q11.
Spatial clustering: section only.
Split & merge: Q11.
Rule-based Segmentation: section only.
Motion-based segmentation: section only.
Area Extraction: Concepts: Q6 (role).
Data-structures: section only.
Edge, Line-Linking: Q4.
Hough transform: Q5, Q6.
Line fitting: section only.
Curve fitting (Least-square fitting): Q3.

Account

Image Processing and Computer Vision (CS-803 (A)) - Unit 2 Short Notes

How unit 2 is examined

Representation schemes

Boundary descriptors

Region descriptors

Thresholding

Segmentation

Connected component labeling

Hierarchal segmentation

Spatial clustering

Split & merge

Rule-based Segmentation

Motion-based segmentation

Area Extraction: Concepts

Data-structures

Edge, Line-Linking

Hough transform

Line fitting

Curve fitting (Least-square fitting)

Last-minute revision

Memory hooks

Coverage checklist