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

How unit 4 is examined

This unit covers line labeling and consistent labeling with back-tracking, the 3D geometry of cameras (perspective and inverse perspective), photogrammetry, and image matching. Back-tracking and perspective geometry carry the marks.

Labeling lines

<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">Not asked since 2022</span>

Definition. Line labeling assigns each edge of a line drawing of a polyhedron a symbol that tells what 3D edge it is.

Key points.

A convex edge, where two visible faces meet with the solid on the inside, is labeled +.
A concave edge, where two visible faces meet with the solid outside, is labeled -.
An occluding (boundary) edge is labeled with an arrow, keeping the visible surface on its right.
Labels are chosen for every line of the drawing so that the whole picture stays physically possible.

Understanding line drawings

Definition. Understanding a line drawing means recovering the 3D structure of the object from its 2D edges and junctions.

Key points.

Junctions are classified by shape as L, Y (fork), T and arrow (W), and each type allows only a few label combinations.
Huffman-Clowes catalogues list the legal labelings, so an illegal drawing (an impossible object) has no consistent labeling.
Once the labels are found, each face and its depth relation to neighbours can be read from them.

Classification of shapes by labeling of edges

Definition. Shapes are classified by the pattern of edge labels: the mix of +, - and arrows on their edges decides the class of the object.

Key points.

A convex object has only + interior edges and arrow outlines, so it is easy to separate.
Concave edges (-) show a notch, a groove or an object resting on another.
The label pattern gives a description that does not depend on the viewpoint much, which is why it helps recognition.

Recognition of shapes

Definition. Shape recognition is identifying an object from its geometric form (outline, surface) and assigning it to a known class.

Key points.

It matters for object detection, OCR and character reading, medical imaging (organ or tumour shape), and industrial inspection.
It supports classification and image retrieval, because shape is stable when colour or lighting changes.
The facet model recognition method fits small planar facets (patches) to the image or range data, measures attributes such as orientation and curvature per facet, and labels the region as flat, ridge, valley or peak.
Classifying the facet attributes gives a shape description that is good for 3D and range images.

Asked: [7 marks] (May 2023) Explain the importance of shape recognition in image processing. Asked: [7 marks] (Jun 2025) Describe the facet model recognition method. How is it applied to shape classification in images?

Consisting labeling problem

Definition. In the consistent labeling problem, each unit (a line or region) must be given one label from a set so that every constraint between related units is satisfied.

Key points.

The problem has units, a label set for each, and constraints on pairs of units.
Line labeling of a drawing is the classic example: junction rules are the constraints.
It is solved by back-tracking search or by relaxation, which prunes inconsistent labels.

Back-tracking Algorithm

Definition. <mark>Back-tracking is a depth-first search that assigns labels one at a time, tests each partial assignment against the constraints, and returns to the previous choice when no label fits.</mark>

Key points.

It is used for the consistent labeling problem: find a label for every unit so that all constraints hold.
It builds a partial solution step by step and never extends one that already violates a constraint, so whole branches are pruned.
When a unit has no consistent label left, the algorithm backs up to the last unit and tries its next label.
If every label of the first unit fails, no solution exists.
Worst-case time is exponential, $O(k^n)$ for $n$ units with $k$ labels, but pruning makes it fast in practice.
In shape recognition it labels the lines of a drawing so that every junction has a legal label set.

Steps.

Step 1: Order the units; set i = 1.
Step 2: Pick the next untried label for unit i.
Step 3: If it is consistent with units 1..i-1, set i = i + 1; if i is past n, output the solution.
Step 4: If no label is left for unit i, set i = i - 1 (back-track) and go to Step 2; if i = 0, there is no solution.

Example. 4-queens, one queen per row, column chosen per row:

Try	Result
Q1 = col 1, Q2 = col 3	Row 3 has no safe column, so back-track
Q2 = col 4, Q3 = col 2	Row 4 has no safe column, so back-track
Q3 has no more choices, Q2 has none	Back-track to Q1
Q1 = col 2, Q2 = 4, Q3 = 1, Q4 = 3	Solution: (1,2), (2,4), (3,1), (4,3)

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 1075 322" width="1075" height="322" role="img" aria-label="4-queens search tree; failed nodes are back-tracked"><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" 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="ahh8" 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="618.5" y1="37" x2="246.5" y2="101"/><line class="e" x1="618.5" y1="37" x2="990.5" y2="101"/><line class="e" x1="246.5" y1="101" x2="153.5" y2="165"/><line class="e" x1="246.5" y1="101" x2="525.5" y2="165"/><line class="e" x1="153.5" y1="165" x2="60.5" y2="229"/><line class="e" x1="525.5" y1="165" x2="432.5" y2="229"/><line class="e" x1="432.5" y1="229" x2="339.5" y2="293"/><line class="e" x1="990.5" y1="101" x2="897.5" y2="165"/><line class="e" x1="897.5" y1="165" x2="804.5" y2="229"/><line class="e" x1="804.5" y1="229" x2="711.5" y2="293"/><rect class="n" x="592.5" y="22" width="52" height="30" rx="8"/><text class="t" x="618.5" y="37" dy=".35em" text-anchor="middle">Root</text><rect class="n" x="220.5" y="86" width="52" height="30" rx="8"/><text class="t" x="246.5" y="101" dy=".35em" text-anchor="middle">Q1=1</text><rect class="n" x="127.5" y="150" width="52" height="30" rx="8"/><text class="t" x="153.5" y="165" dy=".35em" text-anchor="middle">Q2=3</text><rect class="n" x="19" y="214" width="83" height="30" rx="8"/><text class="t" x="60.5" y="229" dy=".35em" text-anchor="middle">Q3 fails</text><rect class="n" x="499.5" y="150" width="52" height="30" rx="8"/><text class="t" x="525.5" y="165" dy=".35em" text-anchor="middle">Q2=4</text><rect class="n" x="406.5" y="214" width="52" height="30" rx="8"/><text class="t" x="432.5" y="229" dy=".35em" text-anchor="middle">Q3=2</text><rect class="n" x="298" y="278" width="83" height="30" rx="8"/><text class="t" x="339.5" y="293" dy=".35em" text-anchor="middle">Q4 fails</text><rect class="n" x="964.5" y="86" width="52" height="30" rx="8"/><text class="t" x="990.5" y="101" dy=".35em" text-anchor="middle">Q1=2</text><rect class="n" x="871.5" y="150" width="52" height="30" rx="8"/><text class="t" x="897.5" y="165" dy=".35em" text-anchor="middle">Q2=4</text><rect class="n" x="778.5" y="214" width="52" height="30" rx="8"/><text class="t" x="804.5" y="229" dy=".35em" text-anchor="middle">Q3=1</text><rect class="n hi" x="685.5" y="278" width="52" height="30" rx="8"/><text class="t" x="711.5" y="293" dy=".35em" text-anchor="middle">Q4=3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">4-queens search tree; failed nodes are back-tracked</figcaption></figure>

Answer frame. Open with the definition; draw the search tree above or a small junction-labeling tree; state steps 1-4 in order; solve the example, showing two back-tracks; close with the exponential worst case and pruning.

Asked: [7 marks] (May 2022, Dec 2024, Jun 2025) Discuss back tracking algorithm by an example. What is the backtracking algorithm? Explain its application in solving consistency labelling problems. Illustrate the back-tracking algorithm used in shape recognition. Provide a scenario where this algorithm is applied.

Perspective Projective geometry

Definition. ==Perspective projection maps a 3D point $(X,Y,Z)$ to the image plane through the centre of projection, so $x = fX/Z$ and $y = fY/Z$, where $f$ is the focal length.==

Key points.

Projective geometry studies properties preserved under projection, such as points, lines, incidence and cross-ratio, while lengths and angles change.
Depth is lost: many 3D points on one ray through the centre give the same image point.
Parallel lines in 3D that are not parallel to the image plane meet at a vanishing point, and the vanishing points of a plane lie on its horizon line.
Homogeneous coordinates $(x,y,w)$ write the projection as a matrix product, which makes it linear: $\begin{bmatrix}x\\y\\w\end{bmatrix}=\begin{bmatrix}f&0&0&0\\0&f&0&0\\0&0&1&0\end{bmatrix}\begin{bmatrix}X\\Y\\Z\\1\end{bmatrix}$, with image point $(x/w, y/w)$.
It models the pinhole camera, and is used to interpret 3D from 2D, for pose and calibration.

Comparison. Affine models approximate perspective when the object is far.

Point	Orthographic	Weak perspective
Equations	$x = X,\ y = Y$	$x = fX/Z_0,\ y = fY/Z_0$
Scale	Unit, no depth scaling	Constant scale $f/Z_0$ for all points
Assumption	Rays parallel to axis	Depth variation small against $Z_0$ (average depth)
Distance dependence	None	Whole object shrinks with $Z_0$
Accuracy	Rough	Better, scaled orthographic

Answer frame. Open by defining perspective projection with $x=fX/Z$; draw the pinhole diagram with a vanishing point; develop points 1-5; for the comparison, define affine models, then give the table; close with its role in 3D reconstruction.

Asked: [7 marks] (May 2022) Compare weak perspective projection and orthographic projection in affine projection models. Asked: [7 marks] (Dec 2024, Jun 2025) Describe perspective projective geometry and inverse perspective projection. Explain projective geometry and its role in interpreting 3D objects from 2D images.

Inverse perspective Projection

Definition. <mark>Inverse perspective projection recovers the 3D position of a point from its image point, using extra knowledge such as its depth or the plane it lies on.</mark>

Key points.

A single image point corresponds to a whole ray, so the depth $Z$ must come from a known plane (for example the ground), a second image, or a size cue.
It is needed to get real-world position from an image, for example in bird's-eye view for robots and lane detection.
With known $Z$, the inverse of $x=fX/Z$ is $X = xZ/f$ and $Y = yZ/f$.
It is used in 3D vision, mapping and measurement.

Steps.

Step 1: Calibrate the camera to get f and the pose.
Step 2: Form the ray through the image point (x, y) and the centre of projection.
Step 3: Intersect the ray with the known plane, or with the ray from a second view.
Step 4: Read off (X, Y, Z) as the 3D point.

Shape numbers. The shape number of a boundary is the smallest-magnitude circular first difference of its chain code; its order is the number of digits, and it stays the same when the shape is rotated.

Answer frame. Open with the definition; draw the ray through the image point meeting the ground plane; write the need, then the steps; close with an application. In the definition question, give both parts.

Asked: [7 marks] (May 2024) Explain inverse perspective projection algorithm. Asked: [7 marks] (Jun 2025) Define: (i) Inverse perspective projection (ii) Shape numbers used in boundary analysis.

Photogrammetric -from 2D to 3D

Definition. Photogrammetry measures the 3D shape and position of objects from two or more 2D photographs.

Key points.

First the camera is calibrated to find focal length and pose.
Corresponding points are matched between the images (stereo correspondence).
Triangulation of each matched pair gives depth: $Z = fB/d$, with baseline $B$ and disparity $d$.
The depth values form a 3D reconstruction, used in mapping, surveying and modelling; it is limited by noise, occlusion and poor matches.

Asked: [7 marks] (May 2023) Explain in brief how photogrammetric processing is done from 2D to 3D?

Image matching: Intensity matching of ID signals

Definition. Image intensity is the gray level (brightness value) at a pixel; intensity matching of 1D signals finds the shift at which two intensity profiles agree best.

Key points.

Slide one profile $g$ over the other $f$ and score each shift $s$ by $SSD(s)=\sum_x (f(x)-g(x-s))^2$, lowest is best.
Or use correlation $\sum_x f(x)\,g(x-s)$, highest is best; normalised correlation removes gain changes.
The best shift gives position or disparity.
Illumination change and noise hurt matching, which is why normalisation is used.

Asked: [7 marks] (May 2023) What is image intensity in image processing? Discuss in brief the Intensity matching of ID signals in an image.

Matching of 2D image

Definition. 2D image matching finds where a template or a second image aligns best with an image.

Key points.

The template is moved over the image and scored by SSD or normalised cross-correlation at each position.
The peak (or minimum) score locates the object.
It is costly for large images and not robust to rotation and scale.

Hierarchical image matching

Definition. Hierarchical matching matches first at a coarse level of an image pyramid, then refines at finer levels.

Key points.

A pyramid of reduced-resolution images is built by smoothing and sub-sampling.
The coarse match is cheap and gives an approximate position.
Each finer level searches only near that position, which saves time.

Object Models And Matching: 2D representation

Definition. A 2D object model stores an object by its 2D view: outline, regions or features, for matching against the image.

Key points.

Models are shapes such as contours, chain codes, or sets of features with relations.
Matching compares the image description with each stored model and picks the best score.
One 2D model covers one view, so several views are stored for 3D objects.

Global vs. Local features

Definition. Global features describe the whole image or object; local features describe small neighbourhoods around interest points.

Key points.

Global features (area, moments, histograms) are simple but fail with occlusion or clutter.
Local features (corners, edges, patches) survive occlusion and partial views.
Local features need more matching effort but recognise objects better.

Last-minute revision

Line labels: + convex, - concave, arrow for occluding edge.
Back-tracking is depth-first with constraint tests; undo the last choice on failure.
Back-tracking worst case is $O(k^n)$.
Perspective: $x=fX/Z$, $y=fY/Z$; depth is lost.
Parallel 3D lines meet at a vanishing point.
Weak perspective: $x=fX/Z_0$; orthographic: $x=X$.
Inverse projection needs depth or a known plane: $X=xZ/f$.
Stereo depth: $Z=fB/d$.
SSD is minimised, correlation is maximised, for 1D matching.
Shape number: minimum circular first difference of chain code; order is its length.
Hierarchical matching goes coarse to fine.

Memory hooks

Plus is Peak (convex), minus is Mine (concave).
Back-tracking is a maze: hit a wall, step back.
Far away means weak perspective: everything gets the same scale.
Forward loses depth, inverse must borrow it.
Coarse to fine: a map first, then the street.

Coverage checklist

Labeling lines: definition, +, - and arrow labels.
Understanding line drawings: junctions and legal labelings.
Classification of shapes by labeling of edges: label patterns.
Recognition of shapes: May 2023 importance of shape recognition; Jun 2025 facet model recognition.
Consisting labeling problem: constraints and labels.
Back-tracking Algorithm: May 2022, Dec 2024, Jun 2025.
Perspective Projective geometry: May 2022 comparison; Dec 2024, Jun 2025.
Inverse perspective Projection: May 2024; Jun 2025 (also shape numbers).
Photogrammetric -from 2D to 3D: May 2023.
Image matching: Intensity matching of ID signals: May 2023.
Matching of 2D image: template matching.
Hierarchical image matching: pyramids.
Object Models And Matching: 2D representation: 2D models.
Global vs. Local features: comparison.

Account

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

How unit 4 is examined

Labeling lines

Understanding line drawings

Classification of shapes by labeling of edges

Recognition of shapes

Consisting labeling problem

Back-tracking Algorithm

Perspective Projective geometry

Inverse perspective Projection

Photogrammetric -from 2D to 3D

Image matching: Intensity matching of ID signals

Matching of 2D image

Hierarchical image matching

Object Models And Matching: 2D representation

Global vs. Local features

Last-minute revision

Memory hooks

Coverage checklist