Image Analysis and Computer Vision

Contents

• Introduction and overview
• 0. Review: linear algebra, convolution, probability
• 1. Image formation: camera and sampling
• 2. Filtering and convolution
• 3. Edges: gradient and Canny
• 4. Interest points: Harris and SIFT
• 5. Projective geometry and homographies
• 6. Stereo vision and epipolar geometry
• 7. Optical flow: Lucas-Kanade
• 8. Segmentation: k-means and graph cuts
• 9. CNNs for vision: detection and segmentation
• 10. 3D point clouds: ICP and urban analysis
• 11. Research at IGN (Brédif): urban LiDAR
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an engineer who has already opened an image in NumPy / OpenCV and applied a blur; no projective geometry is assumed on page 1. Empirical first: each topic starts from a failure you can observe — Canny over-sensitive to noise, a homography that breaks on a panorama, a CNN that detects better than SIFT until labels run out — and only then names the model behind it (pinhole camera, epipolar geometry, ICP).

This course is about making a machine see. It goes from optics to detection CNNs, through filtering, multi-view geometry and 3D point clouds, and it tells classical and learned vision as one story: the convolution of ch. 2 is the same operator as the one inside the CNNs of ch. 9. It ends with urban LiDAR, the research field of the instructor at IGN, and the skills it builds serve both industrial perception and the multimodal models of the program.

What you will be able to do

• Explain how an image forms — camera, projection, sampling — and deduce the limits of the system.
• Design and apply filters and convolutions, and connect classical filtering with the first layers of CNNs.
• Detect edges and interest points (Canny, Harris, SIFT) and know what they are used for in practice.
• Handle projective geometry: homographies, calibration, image rectification.
• State the stereo problem and use epipolar geometry to reconstruct in 3D.
• Estimate motion by optical flow (Lucas-Kanade) and know its assumptions of validity.
• Segment an image by k-means or by graph cuts — the latter framing vision as a graph problem.
• Implement vision CNNs for detection and segmentation, and process 3D point clouds with ICP.

Official objectives and syllabus (2026-2027 catalog)

The official sheet (X3A ME1) sets the frame: “the objective of computer vision is to compute properties of the world from digital images”, with problems such as 3D shape recovery, motion estimation, or object recognition, and an introduction that “covers themes such as feature detection, motion estimation, image mosaics, and 3D vision”.

The themes are discussed “in terms of algorithms and mathematical tools”, and the applications can be developed “in Python or C++” — the algorithmic orientation of these materials.

Official prerequisites: not displayed; assessment: 5 small classes + 1 project; volume: 36 h in person. The table follows the “Programme détaillé” of the sheet, then the themes of its description.

All the themes of the official program are covered. Structure from motion (Def. 6.5) was added earlier; against the 2026-2027 sheet, light (Def. 1.6), dense correlation and plane-sweep stereo (Def. 6.6–6.8) and image-based rendering (Def. 6.9–Example 6.10) were added, as they were previously only named in passing. The truncated item “Image basée sur…” is our reading (image-based rendering). Our additions, beyond the official program: the review chapter 0, chapter 10 (LiDAR point clouds, ICP, and urban analysis), and chapter 11 (the instructor’s work at IGN), which extend vision toward 3D geospatial data.

Where this course fits in the program

One of the “Choose 3” electives of Year 1 · Period 1 (36 h, 4.5 ECTS), preselected by the AI-systems route of the home page: the “vision” choice of the period. Official prerequisites: not stated on the sheet.

These materials assume two internal prerequisites. The first is Signal Processing, whose filtering, convolution, and sampling it consumes (the review chapter takes up linear algebra, convolution, and probability). The second, for the CNN chapter, is neural-network training and convolutional layers: Deep Learning, ch. 1–4, taken in the same period. The AI-systems route takes Deep Learning only in its P2 variant, after this course, so its students read ch. 1–5 of the Refresher Neural Nets before session 10; the box “CNN in one page” that opens ch. 9 adds the convolutional parts.

Downstream, three modules directly extend this one: Computer Vision: From Fundamentals to Applications (Period 2; announced in the MSc&T brochure but not in the 2026–27 LLGA lists, notes kept for reference) is its declared sequel, from fundamentals to applications; Multimodal Generative AI mobilizes visual encoders and diffusion over images; Advanced Deep Learning deepens vision architectures among advanced models. Note: the graph-cut segmentation of chapter 8 also connects vision to the “graphs” side of the master’s program, up to Graph ML.

The course is the perception front end of two end-of-year projects: the scene-graph question answering of Y1.5 (detection, ch. 9; camera and projective geometry, ch. 1 and 5) and the 3D product search of Y2.3 (point clouds, ch. 10).

Course outline

• Review: linear algebra, convolution, probability: the three pillars taken up from Signal Processing and the refreshers, at the level required in vision.
• Image formation: camera and sampling: from the 3D world to the pixel — the camera model and its artifacts.
• Filtering and convolution: smoothing, detecting, combining — the founding operation of everything that follows.
• Edges: gradient and Canny: extracting the significant boundaries of an image.
• Interest points: Harris and SIFT: anchoring correspondences between images, before deep learning.
• Projective geometry and homographies: computing across views — crop, rectify, stitch.
• Stereo vision and epipolar geometry: two views, one constraint — reconstructing depth.
• Optical flow: Lucas-Kanade: measuring apparent motion, with its assumptions and its failures.
• Segmentation: k-means and graph cuts: partitioning the image — and framing vision as a graph problem.
• CNNs for vision: detection and segmentation: the learned successor to manual filtering, up to dense tasks.
• 3D point clouds: ICP and urban analysis: aligning and analyzing LiDAR clouds — vision beyond images.
• Research at IGN (Brédif): urban LiDAR: Mathieu Brédif’s research, from the 3D city to massive geospatial data.

Session plan

36 h in class = 12 sessions of 3 h. The volume is the one of the SynapseS 2026–2027 sheet (36 h in person; the lecture / small-class split is not displayed); the sheet lists its programme topics but publishes no session-by-session programme, so the split below is our proposal for covering these notes in that time. Level 1 = foundations (reviews, definitions, first worked examples), 2 = core methods, 3 = advanced material (3D registration, learning on point clouds); the level never goes down from one session to the next.

Self-study, outside the 36 h (about 2 h in total): ch. 11 Research at IGN (Brédif): urban LiDAR — the benchmark, LU-Net and disocclusion papers, read as project preparation (≈ 2 h).

How to study this module

• Visualize everything: each chapter benefits from being validated on real images (display the gradients, the Harris maps, the segmentations) — a vision error can be seen.
• Implement convolution, Canny, and Lucas-Kanade in NumPy/OpenCV on your own photos before moving to CNNs: the convolutional layers will be all the more readable.
• Write the projective geometry matrices by hand on a small numerical example (homogeneous points, homography): the formalism only settles in by being practiced.
• If convolution or sampling is fuzzy, go back to the Signal Processing module; if CNNs are, read the box that opens ch. 9, then the Deep Learning module (ch. 4) or, on the AI-systems route, the Refresher Neural Nets (ch. 1–5).
• Remember the guiding thread: the same operator — convolution — runs through classical filtering and the learned networks of chapter 9.
• Finish with the 3D chapters: ICP and urban LiDAR are a direct gateway to geospatial internships and to Computer Vision: From Fundamentals to Applications, announced for Period 2 (notes kept for reference).

0. Review: linear algebra, convolution, probability

This chapter gathers the tools from linear algebra, calculus and probability that the rest of the course uses constantly. Two results deserve to be known by heart: the singular value decomposition, which solves almost every estimation problem of the geometric chapters, and the behaviour of Gaussians under convolution, which makes the Gaussian the default smoothing kernel.

1. Image formation: camera and sampling

Concrete scene: a 12 MP smartphone photo, you downsample ×4 with no anti-aliasing filter — moiré on grids, aliasing on text. This is not “the image looks ugly”: it is the formation model (projection + sampling) setting hard limits. This chapter links pixels to geometry before Canny, SIFT and CNNs.

A digital image is the discretization of a projection of the 3D world onto a plane. Understanding the formation model is indispensable: it is what connects the pixels to geometry (ch. 5-6), and what imposes the limits of sampling (aliasing).

Light: from scene radiance to pixel value

The official programme opens with “light, colour and images”. Geometry (Definition 1.1) says where a point lands in the image; radiometry says how bright it is, which every intensity-based method of the course — edges, correlation, flow — silently depends on.

2. Filtering and convolution

Filtering an image means replacing each pixel with a combination of its neighborhood: smoothing noise, sharpening details, detecting variations. The universal tool is convolution, already met in 1D in the Signal Processing module (ch. 1): everything that follows is its 2D translation.

3. Edges: gradient and Canny

An edge is a rapid variation of intensity: the first order (gradient) locates it by its maxima, the second order (Laplacian) by its zero crossings. The Canny detector (1986) combines these ideas into a pipeline still present in industrial chains.

4. Interest points: Harris and SIFT

Matching two images amounts to finding points that are distinctive and stable there: corners, blobs, local structures. Two classics organize the chapter: Harris (1988) to detect, SIFT (2004) to describe — and the CNNs of ch. 9 are their learned heirs.

import cv2, numpy as np

img  = cv2.imread("scene.jpg", cv2.IMREAD_GRAYSCALE)
imgf = img.astype(np.float32)

# --- 1. manual Harris: structure tensor, response, thresholding
Ix = cv2.Sobel(imgf, cv2.CV_32F, 1, 0, ksize=3)
Iy = cv2.Sobel(imgf, cv2.CV_32F, 0, 1, ksize=3)
A  = cv2.GaussianBlur(Ix*Ix, (5, 5), 1.5)     # weighted local sum
B  = cv2.GaussianBlur(Ix*Iy, (5, 5), 1.5)
C  = cv2.GaussianBlur(Iy*Iy, (5, 5), 1.5)
R  = (A*C - B*B) - 0.04*(A + C)**2
corners = np.argwhere(R > 0.01 * R.max())        # relative thresholding

# --- 2. OpenCV versions
Rc = cv2.cornerHarris(imgf, 2, 3, 0.04)
sift = cv2.SIFT_create(nfeatures=2000)
kps, desc = sift.detectAndCompute(img, None)   # 128-D per keypoint
img2 = cv2.drawKeypoints(img, kps, None,
                         flags=cv2.DRAW_RICH_KEYPOINTS)

# --- 3. matching two views with Lowe's ratio test
kps2, desc2 = sift.detectAndCompute(cv2.imread("scene2.jpg", 0), None)
bf  = cv2.BFMatcher()
mch = [m for m, n in bf.knnMatch(desc, desc2, k=2) if m.distance < 0.8*n.distance]
print(len(mch), "matches kept out of", len(desc))
# and for the rest of the course: Canny + quick Hough transform
edges = cv2.Canny(img, 80, 200)

Nearest-neighbour search: kd-trees and hashing

Matching descriptors (Proposition 4.5), pairing points in ICP and estimating normals (ch. 10) all ask one question: which stored vector is closest to a query? This section is the reference of these notes for the two classical answers, trees and hashing.

5. Projective geometry and homographies

Two views of the same plane (facade, document, whiteboard), or one camera that only rotates about itself: in both cases, the relation between pixels is a homography. It is the basic tool of registration, panoramas, and augmented reality.

6. Stereo vision and epipolar geometry

Two views of a 3D scene, taken from different points: the epipolar constraint says that the correspondent of a pixel lies on a known line in the second image. All of stereo vision — from reconstruction to robotics — follows from this geometric observation.

Dense correlation and multi-view stereo

Feature matching (ch. 4) gives a few thousand correspondences; dense stereo needs one per pixel. The official programme names the tool: matching by dense correlation, then its generalization to many views (MultiView Stereo).

Image-based rendering

The programme item truncated on the sheet as “Image basée sur…” is read here as image-based rendering (together with the mosaics of chapter 5): producing new views of a scene directly from photographs.

7. Optical flow: Lucas-Kanade

The apparent motion of luminances between two images — optical flow — is the ingredient of tracking, video compression, and navigation. Lucas-Kanade (1981) remains the reference formulation, and its mathematics is a condensed version of the course.

8. Segmentation: k-means and graph cuts

Segmenting means partitioning the image into coherent regions: objects of interest, surfaces, backgrounds. Two families: the clustering approach (pixels are points in a feature space) and the energy-based approach (look for a partition that minimizes a global cost).

9. CNNs for vision: detection and segmentation

Convolutional networks, introduced in ch. 4 of the Deep Learning module, have absorbed a large part of the classical pipeline: learned filters replace Sobel and SIFT. This chapter focuses on vision tasks: classifying, detecting (where are the objects?), segmenting (which pixels belong to them?).

Lab sheet: fine-tuning a pretrained detector (session 10)

About 90 minutes on a free GPU tier, in PyTorch and torchvision. On a laptop CPU, train for 2 epochs at a reduced image size and keep only the NMS ablation.

1. Data. The Penn-Fudan pedestrian database (Wang, Shi, Song and Shen, ACCV 2007): 170 street images with 345 pedestrians, annotated with boxes and masks. Keep 120 images for training and 50 for testing, with a fixed seed.
2. Model. torchvision’s Faster R-CNN with a ResNet-50 FPN backbone pretrained on COCO (fasterrcnn_resnet50_fpn); replace its box predictor by a two-class head (background, pedestrian).
3. Training. First freeze the backbone and train the heads only, then unfreeze it. Use SGD with \eta = 0.005, momentum \beta = 0.9, weight decay 5\cdot10^{-4}, batches of 2 images, horizontal flips, 5 to 10 epochs. The model returns the losses of Definition 9.6 (classification and smooth-L1, for the proposal network and for the head): plot each one.
4. Evaluation. AP@0.5 and mAP@[0.5:0.95] on the test images with torchmetrics.detection.MeanAveragePrecision; check the AP of one test image by hand with Definition 9.4 and Example 9.5.
5. Ablations. NMS threshold 0.3, 0.5 and 0.7 (Definition 9.2); frozen against unfrozen backbone; 30 against 120 training images.
6. Report, one page: the AP table, the loss curves, and three failure cases explained (occlusion, small or truncated pedestrians, duplicate boxes).

10. 3D point clouds: ICP and urban analysis

Mobile or airborne LiDAR, photogrammetry, RGB-D depth: the world also arrives as point clouds — millions of 3D points, possibly colored, with no topology. The questions become geometric: register two clouds, estimate normals, segment, classify.

import numpy as np
from scipy.spatial import cKDTree

def best_rigid_transform(P, Q):            # theorem 10.3 (Kabsch)
    cp, cq = P.mean(0), Q.mean(0)
    H = (P - cp).T @ (Q - cq)              # 3x3
    U, S, Vt = np.linalg.svd(H)
    d = np.sign(np.linalg.det(Vt.T @ U.T))
    R = Vt.T @ np.diag([1, 1, d]) @ U.T
    return R, cq - R @ cp

def icp(P, Q, iters=50, tol=1e-7):
    tree = cKDTree(Q); R = np.eye(3); t = np.zeros(3); prev = np.inf
    for _ in range(iters):
        Pk = P @ R.T + t                          # current position of P
        d, idx = tree.query(Pk)                   # (1) matching
        Rk, tk = best_rigid_transform(Pk, Q[idx]) # (2) Kabsch increment
        R, t = Rk @ R, Rk @ t + tk                # (3) accumulation
        err = np.mean(d**2)
        if prev - err < tol: break
        prev = err
    return R, t, np.sqrt(err)

# synthetic test: 25-degree rotation + 1 cm noise
rng = np.random.default_rng(0)
src = rng.normal(size=(3000, 3)) * [10, 3, 1]     # elongated noisy "ground"
a = np.deg2rad(25)
Rt = np.array([[np.cos(a), -np.sin(a), 0],
               [np.sin(a),  np.cos(a), 0],
               [0, 0, 1]])
dst = src @ Rt.T + [2, -1, 0] + rng.normal(scale=.01, size=src.shape)
R, t, rms = icp(src, dst)
print("angle error (deg):", np.rad2deg(np.arccos((np.trace(R.T @ Rt)-1)/2)))
# ~0.002 deg here; on an isotropic blob ([10, 10, 1]) the same 25 deg start
# ends in a local minimum (Prop. 10.4): the shape gives ICP nothing to grip

11. Research at IGN (Brédif): urban LiDAR

The module is taught by Mathieu Brédif, researcher at IGN (MATIS laboratory, ENSG) and professor at Université Gustave Eiffel. His work traverses exactly the program of the semester: mobile acquisition, registration, semantic analysis of urban clouds, and the handling of LiDAR sampling defects. Verified selection:

• TerraMobilita/iQmulus urban benchmark. B. Vallet, M. Brédif, A. Serna, B. Marcotegui, N. Paparoditis, “TerraMobilita/iQmulus urban point cloud analysis benchmark”, Computers & Graphics 49, 2015 — an annotated dataset acquired by Stéréopolis (IGN’s mobile mapping vehicle) in Paris and Rueil-Malmaison, with two evaluation tasks: facade segmentation and urban object classification (see data.ign.fr). The international reference for comparing mobile cloud analysis methods — the “test bench” of ch. 8-10.

• Semantic segmentation by range images: LU-Net. P. Biasutti, V. Lepetit, M. Brédif, J.-F. Aujol, A. Bugeau, “LU-Net: An Efficient Network for 3D LiDAR Point Cloud Semantic Segmentation Based on End-to-End-Learned 3D Features and U-Net”, ICCV Workshops 2019 — the architecture of ch. 9 (U-Net) applied to the range images of ch. 10, with 3D features learned end to end: the “signs, lampposts, facades” class at a fraction of the cost of 3D convolutions.

• LiDAR disocclusion and visibility. Mobile LiDARs see streets from the street: everything occluded (behind a car, a tree) is missing from the cloud.

  The series of works “Disocclusion of 3D LiDAR point clouds using range images” (ISPRS Hannover Workshop 2017), “Visibility estimation in point clouds with variable density” (VISAPP 2019), and “Diffusion and inpainting of reflectance and height LiDAR orthoimages” (Computer Vision and Image Understanding 179, 2019), with P. Biasutti, J.-F. Aujol, A. Bugeau — extended as early as ICIP 2016 with M. Bevilacqua (“Visibility estimation and joint inpainting of Lidar depth maps”) —, addresses these holes: estimating visibility, inpainting range and ortho-reflectance images — LiDAR processed as an image (ch. 2), with geometry as a constraint.

• 3D models and historical textures. His recent work projects very many photographs (heritage ones included) onto current urban 3D models — projective “multitexturing” of cities and clouds (with M. S. Gomes de Castro) — an exercise in homographies (ch. 5) and visibility (ch. 10) at the scale of a city. See his full CV on HAL.

Exercises

1. ★ Camera (solved). Sensor 3000×2000 of 2.2 µm, focal length 24 mm. (a) Horizontal field of view? (b) Focal length in pixels? (c) How many point pairs for a homography, and why 4? (d) Does a pure rotation of the camera give a homography between views (justify)? Solution. (a) w = 6.6 mm, \mathrm{FOV} = 2\arctan(3.3/24) \approx 15.6^\circ. (b) f_x = 0.024/2.2\,\text{µm} \approx 10\,900 px. (c) 4 pairs: H has 8 dof (9 coefficients − 1 scale), each pair provides 2 independent equations (Prop. 5.3). (d) Yes: Theorem 5.2, case (ii) — it is even the only non-planar case that qualifies.

2. ★ Convolution (solved). (a) Convolve [10, 12, 11, 40, 42] with the kernel [0.25,\,0.5,\,0.25] (replicated borders). (b) How many multiplications per pixel for a 5×5 Gaussian, direct then separable? (c) Why is a 3×3 box filter not an ideal smoother? Solution. (a) [10.5,\,11.25,\,18.5,\,33.25,\,41.5] — the jump 11→40 is smoothed over two samples. (b) 25 direct, 2\times5 = 10 separated (Prop. 2.2), ratio 2.5×. (c) its frequency response is a sinc (Def. 2.1 and the Signal Processing module, ch. 3): negative lobes create contrast reversals at high frequencies — the Gaussian has no rebound.

3. ★ Lucas-Kanade (solved). Window of 4 pixels, measurements (I_x, I_y\,;\,I_t): (2, 1; 6), (4, 2; 10), (3, 1; 7), (5, 2; 12). Solve for the flow; compute the eigenvalues of the tensor; is the flow reliable? Propose two remedies.

   Solution. M = \begin{pmatrix}54 & 23\\ 23 & 10\end{pmatrix}, right-hand side -(133, 57)^\top. \det M = 11 — nearly singular: \lambda_1 \approx 63.8, \lambda_2 \approx 0.17. Cramer: u = v = -19/11 \approx -1.73.

   Reliability: no — \lambda_2 \ll \lambda_1 signals an edge (aperture problem, Thm 7.2); the uncertainty ellipse is very elongated: the flow component along the edge is poorly observed. Remedies: pyramid (large → small motion) and Gaussian weighting of the window; failing that, reject the pixel (\lambda_2 < \tau).

4. ★ Stereo (solved). f = 721 px, B = 0.54 m. (a) Disparity of an object at 25 m, at 5 m? (b) Depth if d = 25 px? (c) Depth uncertainty at 25 m if the disparity is known to ±0.25 px? (d) Why double the baseline?

   Solution. (a) d = fB/Z: 15.6 px at 25 m; 77.9 px at 5 m. (b) Z = fB/d = 721\times0.54/25 \approx 15.6 m. (c) \Delta Z/Z = \Delta d/d = 0.25/15.6 \approx 1.6\,\% → ±0.4 m (Thm 6.3). (d) Z = fB/d: doubling B doubles d at equal depth, hence halves the relative error — at the price of a wider separation and increased occlusion areas between views.

5. ★★ Harris in practice. Implement the structure tensor (Example 4.6), threshold R > 0.01\,R_{max}, display the corners on a photo; compare with cv2.cornerMinEigenVal. Rotate the image by 30° and measure the stability of the detection (Prop. 4.3). Hint: smoothing with \sigma \approx 1{-}2 before the Sobels; measure stability by the number of corners rematched within ±2 px.

6. ★★ RANSAC. (a) Derive the formula for the number of draws N \geq \ln(1-p)/\ln(1-w^s) for an s-point estimator (independence of the draws).

   (b) Compute N for s = 4, w = 0.3, p = 0.999. (c) Adaptive RANSAC: how to stop before N draws?

   Hint: (a) failure probability 1-w^s per draw, independent ⇒ (1-w^s)^N \leq 1-p. (b) w^4 = 0.0081, N = 6.908/0.00813 \approx 850. (c) update w with the current best consensus and recompute N on the fly.

7. ★★ ICP. Generate a noisy planar cloud, transform it (30° rotation), run the ICP of Example 10.5 from increasingly bad initializations; measure the basin of convergence. Test the point-to-plane variant on planes. Hint: plot the RMS error per iteration (log); the basin closes when matches cross the edges of the cloud — hence the value of rejecting distant pairs and of initial RANSAC.

8. ★★ Segmentation, up close. On a photo, compare k-means on (a) RGB, (b) RGB + (x, y)/10, (c) Lab; choose k by the elbow method. Where do SLIC superpixels fit in a modern vision pipeline (ch. 8-9)? Hint: (b) forces spatial compactness — connected regions; (c) separates hue from luminance (Def. 1.5); connect to the Machine Learning module, ch. 7.

9. ★★ Graph cut by hand (solved). Three pixels in a row, a – b – c. As in Example 8.5, the edge from s to a pixel carries the cost of the background label, and the edge to t the cost of the foreground label: 6 and 1 for pixel a, 3 and 2 for b, 1 and 5 for c. Both neighbour edges have \lambda B = 2.

   (a) Find a maximum flow by augmenting paths, and the minimum cut (Algorithm 8.4). (b) Check the result by listing the energies of Definition 8.3. (c) From which value of \lambda B does the whole row become foreground?

   Solution. (a) The paths s \to a \to t, s \to b \to t and s \to c \to t carry 1, 2 and 1; then s \to a \to b \to c \to t carries 2: the flow is 6.

   Then S = \{s, a, b\}: pixels a and b are foreground, c is background, and the cut 1 + 1 + 2 + 2 = 6 equals the flow.

   (b) The labelling (F, F, B) costs 1 + 2 + 1 + 2 = 6; (F, B, B) costs 7, (F, F, F) 8, (B, B, B) 10, and the four others more. (c) (F, F, F) costs 8 and (F, F, B) costs 4 + \lambda B: the whole row is foreground once \lambda B > 4.

Projects and assessment

The official assessment is “5 small classes (TD) + 1 project”, stated in the description of the 2026–2027 SynapseS sheet and in its section for the engineering degree; the LLGA section of the sheet displays no assessment of its own. The subjects below are proposals of these notes, not official rules. The exercises and the labs of the session plan match the five small classes, and one solo or group subject stands for the project; the sheet announces no written exam, so the exam below is only a proposal, for instance for a resit.

The projects exercise mainly O6 (vision, the visual side of the multimodal objective), O7 (complete pipelines on real benchmarks, checked against OpenCV, COLMAP or torchvision) and O1 (SVD, least squares and CNN training), with O4 and O5 in the graph-cut, LiDAR-graph and scene-graph subjects.

Solo projects

1. [Solo · ≈ 20 h] Panorama stitcher from scratch. When does a handheld panorama break the homography model of Theorem 5.2, and how many RANSAC draws does matching really need?
   • Work: Harris and SIFT matching with Lowe’s ratio test, Hartley-normalized DLT, adaptive RANSAC whose number of draws is measured against Proposition 5.4, inverse warping with bilinear interpolation, and feathered blending; the method of Brown and Lowe (“Automatic Panoramic Image Stitching using Invariant Features”, IJCV 2007).
   • Data: the 59 viewpoint sequences of HPatches (Balntas, Lenc, Vedaldi and Mikolajczyk, CVPR 2017), which come with ground-truth homographies; then your own sequences, on a tripod (pure rotation), of a planar facade, and handheld with parallax — the two cases of Theorem 5.2 and one failure.
   • Success criterion: mean corner error of the estimated homographies under 3 px on most HPatches viewpoint pairs; measured draws compared with Proposition 5.4; seams and ghosting compared with cv2.Stitcher and explained.
   • Deliverables: code, a 4–6 page report, a 10-minute talk; chapters 2, 4 and 5.
2. [Solo · ≈ 20 h] Paper study: how robust is ICP, and does optimal transport help? (Besl and McKay, 1992; Shen, Feydy et al., NeurIPS 2021). How wide is the basin of convergence of point-to-point, point-to-plane and trimmed ICP, and does a soft transport matching widen it?
   • Work: starting from Example 10.5, map the success rate against the initial rotation, the noise, the overlap and density changes; add an entropic-OT (Sinkhorn) soft matching in the spirit of the RobOT paper, computed with the POT or GeomLoss library, and a RANSAC initialization on Open3D’s FPFH features.
   • Data: the Stanford Bunny scans bun000 and bun045 of the Stanford 3D Scanning Repository (partial overlap), and the synthetic clouds of Example 10.5.
   • Success criterion: success-rate curves (final rotation error under 2°) against the initial angle for each method, with the RMS per iteration and the time per run; the OT variant compared at equal time budget.
   • Deliverables: code, report, talk; chapters 0 and 10. It leads to Computational Optimal Transport, ch. 3 (Sinkhorn) and to the ICP of Shapes, ch. 4.
3. [Solo · ≈ 20 h] Graph cuts against learned segmentation. With the same user input, how close does an interactive graph cut get to a pretrained promptable segmenter?
   • Work: Boykov-Jolly segmentation (Definition 8.3) with Gaussian B_{pq} and colour-histogram terminal costs, solved with the PyMaxflow library (Boykov-Kolmogorov); a sweep of the Potts weight \lambda; k-means and SLIC baselines; a normalized cut of the same pixel graph on downsampled images; Segment Anything (Kirillov et al., ICCV 2023) prompted with the same box.
   • Data: the GrabCut dataset (Rother, Kolmogorov and Blake, SIGGRAPH 2004): 50 images with ground-truth masks and the user trimaps of the paper.
   • Success criterion: mean IoU over the 50 images for each method with identical user input; the effect of \lambda explained with Example 8.5.
   • Deliverables: code, report, talk; chapters 8 and 9. The normalized cut is the spectral clustering of Graph ML, ch. 4.

Group projects

1. [Group of 3 · ≈ 30 h each] From two views to multi-view stereo and novel views. How close can a pipeline written from the chapters get to COLMAP, and where does it break?
   • Work: calibrate a phone camera (Zhang’s checkerboard, ch. 1); normalized 8-point algorithm with RANSAC, decomposition of E and the chirality test (Proposition 6.2); triangulation and incremental SfM with bundle adjustment by scipy.optimize.least_squares (Definition 6.5); plane-sweep NCC on 5–10 views (Definition 6.8); interpolated views (Example 6.10) and, as a stretch, a 3D Gaussian splatting fit from the recovered poses.
   • Data: your own captures, then one scene of the ETH3D high-resolution multi-view benchmark (Schöps et al., CVPR 2017), which provides laser-scan ground truth.
   • Split: calibration and two-view geometry; SfM and bundle adjustment; multi-view stereo and rendering.
   • Success criterion: camera rotations within 2° of COLMAP’s; accuracy and completeness of the fused cloud against the ETH3D scan at a 5 cm tolerance; disocclusion holes shown and explained.
   • Deliverables: code, an 8–10 page joint report, a 20-minute talk; chapters 1, 5 and 6.
2. [Group of 3 · ≈ 30 h each] Urban LiDAR segmentation: range image, points or graph? Which representation of Proposition 10.6 gives the best accuracy per unit of memory and time on street scans?
   • Work: three pipelines under the same budget — (i) a range image and a U-Net in the style of LU-Net (ch. 11); (ii) PointNet on raw points; (iii) a GNN over the k-nearest-neighbour graph, with PCA normals as node features (Proposition 10.2).
   • Data: a subset of SemanticKITTI (Behley et al., ICCV 2019), two training sequences and the validation sequence 08; as a stretch, the TerraMobilita/iQmulus benchmark (Vallet et al., 2015) of ch. 11.
   • Split: one pipeline per member, with shared data loading and evaluation.
   • Success criterion: mIoU on the held-out sequence, memory and latency per scan for the three pipelines; an analysis of the errors in occluded areas (ch. 11).
   • Deliverables: code, joint report, talk; chapters 9–11. Pipeline (iii) is the message passing of Graph ML, ch. 5.
3. [Group of 3 · ≈ 30 h each] Scene graphs from detections, the perception front end of Y1.5. How much does detection error degrade the scene graph, and the answers computed on it?
   • Work: fine-tune a detector with attribute heads (colour, shape, material, size) as in the lab sheet of ch. 9; build the scene graph of the Note in ch. 9, with left of and behind from the box positions; answer a few CLEVR question families with a symbolic program executor, on gold and on predicted graphs.
   • Data: CLEVR (Johnson et al., CVPR 2017), a subset of about 10,000 training and 2,000 validation renders (of 70,000 and 15,000), with full scene annotations and question programs.
   • Split: detector and attributes; scene-graph builder and its metrics; question executor and evaluation.
   • Success criterion: AP@0.5 per attribute class; edge precision and recall of the predicted scene graphs against the annotations; question accuracy on gold against predicted graphs, as a function of the detection threshold.
   • Deliverables: code, joint report, talk; chapters 1, 5 and 9. It is the first milestone of the Year 1 project Y1.5 and feeds the relational GNNs of Graph ML, ch. 5.

Written exam (proposal)

Two hours, one handwritten A4 sheet allowed, a simple calculator allowed; four exercises.

1. Question (5 points). Explain why the Harris response is invariant to a rotation of the image but not to a change of scale. List the steps by which SIFT obtains scale and rotation invariance, then state Lowe’s edge-rejection test and say what it rejects.
   • Expected: M averages \nabla I\,\nabla I^\top, and a rotation maps it to RMR^\top: same eigenvalues, same response (Proposition 4.3). A zoom changes which pixels fall in the window, so a corner at one scale looks like an edge or a flat area at another.
   • SIFT: extrema of the DoG in (x, y, \sigma) for scale; the dominant gradient orientation for rotation; a 4\times4\times8 histogram, normalized and clipped at 0.2, for illumination.
   • Edge test: keep a point only if \det H > 0 and \mathrm{tr}(H)^2/\det H < (r+1)^2/r, with r = 10; it rejects edge-like points, whose principal curvatures differ by a factor above 10.
2. Question (5 points). A rectified stereo rig has f = 700 px and B = 0.5 m. (a) Give the depth of a point with disparity 14 px, and its uncertainty if the disparity is known to ±0.5 px. (b) F is estimated by RANSAC on 8-point samples with 50% inliers: how many draws give 99% confidence? And with the 7-point algorithm?
   • Expected: Z = fB/d = 350/14 = 25 m, and \Delta Z \approx Z^2\Delta d/(fB) \approx 0.89 m, that is 3.6% (Example 6.4).
   • By Proposition 5.4, N \geq \frac{\ln(0.01)}{\ln(1 - 0.5^8)} = \frac{4.605}{0.00391} \approx 1177 draws; with 7 points, 4.605/0.00784 \approx 588: one point fewer per sample halves the number of draws at this inlier rate.
3. Question (5 points). Let p_i, q_i (i = 1, \dots, n) be paired points of \mathbb{R}^3, with centred versions \tilde p_i = p_i - \bar p and \tilde q_i = q_i - \bar q, and consider \min_{R \in SO(3),\ t \in \mathbb{R}^3} \ \sum_i \|R p_i + t - q_i\|^2, \qquad H = \sum_i \tilde p_i \tilde q_i^\top = U\Lambda V^\top . Prove that the optimal translation is t = \bar q - R\bar p, that the best rotation then maximizes \mathrm{tr}(RH), and that it is R = VU^\top when \det(VU^\top) = 1.
   • Expected: the gradient in t, 2\sum_i (R p_i + t - q_i), vanishes at t = \bar q - R\bar p.
   • Substituting, the cost becomes \sum_i\|\tilde p_i\|^2 + \sum_i\|\tilde q_i\|^2 - 2\sum_i \tilde q_i^\top R\,\tilde p_i , \qquad \sum_i \tilde q_i^\top R\,\tilde p_i = \mathrm{tr}(RH) .
   • With Z = V^\top R U, which is orthogonal, \mathrm{tr}(RU\Lambda V^\top) = \mathrm{tr}(Z\Lambda) = \sum_i Z_{ii}\lambda_i \leq \sum_i \lambda_i , since Z_{ii} \leq 1 and \lambda_i \geq 0. Equality holds at Z = I, that is R = VU^\top, a rotation since its determinant is 1 (Theorem 10.3).
4. Question (5 points). One class, boxes written (x_1, y_1, x_2, y_2). Two ground truths and four detections, sorted by decreasing score: G_1 = (0, 0, 4, 4),\ G_2 = (10, 0, 14, 4); \qquad D_1 = (0, 0, 4, 4),\ D_2 = (1, 0, 5, 4),\ D_3 = (10, 2, 14, 6),\ D_4 = (11, 0, 15, 4).
   1. Compute the IoU of D_2 with G_1 and of D_3, D_4 with G_2. (b) Which detections survive NMS at 0.5? (c) Give the AP at \tau = 0.5, without and with NMS.
   • Expected: (a) 12/20 = 0.6; 8/24 \approx 0.33; 12/20 = 0.6.
   • (b) \mathrm{IoU}(D_1, D_2) = 0.6 > 0.5 removes D_2; \mathrm{IoU}(D_3, D_4) = 6/26 \approx 0.23 keeps both. D_1, D_3 and D_4 survive.
   • (c) Without NMS the verdicts are TP, FP (duplicate), FP, TP: precision 1 up to recall 0.5, then 0.5 at recall 1, so \mathrm{AP} = 0.5 + 0.25 = 0.75. With NMS they are TP, FP, TP and \mathrm{AP} = 0.5 + 0.5 \times 0.67 \approx 0.83 (Example 9.5).

Grading rubric (proposal)

References

• R. Szeliski, Computer Vision: Algorithms and Applications, 2nd ed., Springer, 2022 — free online edition; the reference textbook of the course, all the classic sections (formation, filtering, geometry, stereo, motion).
• R. Hartley, A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, 2004 — the bible of ch. 5-6: homographies, DLT, epipolar, autocalibration.
• C. Harris, M. Stephens, “A Combined Corner and Edge Detector”, Alvey Vision Conference, 1988 — the paper of ch. 4.
• D. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints”, IJCV 60(2), 2004 — SIFT.
• J. Beis, D. Lowe, “Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces”, CVPR, 1997; M. Muja, D. Lowe, “Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration” (FLANN), VISAPP, 2009; M. Charikar, “Similarity Estimation Techniques from Rounding Algorithms”, STOC, 2002 — nearest-neighbour search and hashing in ch. 4.
• J. Canny, “A Computational Approach to Edge Detection”, IEEE TPAMI 8(6), 1986 — the detector of ch. 3.
• B. Lucas, T. Kanade, “An Iterative Image Registration Technique with an Application to Stereo Vision”, IJCAI, 1981; B. Horn, B. Schunck, “Determining Optical Flow”, Artificial Intelligence 17, 1981 — the two pillars of ch. 7.
• Z. Zhang, “A Flexible New Technique for Camera Calibration”, IEEE TPAMI 22(11), 2000 — the checkerboard calibration of ch. 1.
• H. Hirschmüller, “Stereo Processing by Semiglobal Matching and Mutual Information”, CVPR, 2008 — the SGM of ch. 6.
• P. Felzenszwalb, D. Huttenlocher, “Efficient Graph-Based Image Segmentation”, IJCV 59(2), 2004 — nearly linear segmentation; Y. Boykov, M.-P. Jolly, “Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images”, ICCV, 2001 — the interactive cuts of ch. 8; Y. Boykov, V. Kolmogorov, “An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision”, IEEE TPAMI 26(9), 2004 — the max-flow algorithm of vision; J. Shi, J. Malik, “Normalized Cuts and Image Segmentation”, IEEE TPAMI 22(8), 2000.
• O. Ronneberger, P. Fischer, T. Brox, U-Net: Convolutional Networks for Biomedical Image Segmentation, MICCAI 2015 (arXiv 1505.04597); K. He et al., Deep Residual Learning, CVPR 2016 (arXiv 1512.03385).
• S. Ren, K. He, R. Girshick, J. Sun, Faster R-CNN, NeurIPS 2015 (arXiv 1506.01497); J. Redmon et al., You Only Look Once, CVPR 2016 (arXiv 1506.02640); N. Carion et al., DETR, ECCV 2020 (arXiv 2005.12872); A. Radford et al., CLIP, ICML 2021 (arXiv 2103.00020); H. Rezatofighi et al., Generalized Intersection over Union, CVPR 2019 (arXiv 1902.09630) — the GIoU loss of ch. 9; L. Wang, J. Shi, G. Song, I. Shen, “Object Detection Combining Recognition and Segmentation”, ACCV, 2007 — the Penn-Fudan pedestrian database of the ch. 9 lab.
• P. Besl, N. McKay, “A Method for Registration of 3-D Shapes”, IEEE TPAMI 14(2), 1992 — ICP; Z. Zhang, “Iterative Point Matching for Registration of Free-Form Curves and Surfaces”, IJCV 13(2), 1994 — the robust variant; C. R. Qi et al., PointNet, CVPR 2017 (arXiv 1612.00593).
• Z. Shen, J. Feydy, P. Liu, A. H. Curiale, R. San José Estépar, R. San José Estépar, M. Niethammer, “Accurate Point Cloud Registration with Robust Optimal Transport”, NeurIPS 2021 — RobOT: the ICP/optimal-transport bridge of ch. 10 (and of the Computational Optimal Transport module).
• B. Vallet, M. Brédif, A. Serna, B. Marcotegui, N. Paparoditis, TerraMobilita/iQmulus urban point cloud analysis benchmark, Computers & Graphics 49, 2015; P. Biasutti, V. Lepetit, M. Brédif, J.-F. Aujol, A. Bugeau, LU-Net, ICCV Workshops 2019; P. Biasutti, J.-F. Aujol, M. Brédif, A. Bugeau, Disocclusion of 3D LiDAR point clouds using range images, ISPRS Hannover Workshop 2017 — the instructor’s publications (ch. 10-11), complete on HAL.
• M. Levoy, P. Hanrahan, “Light Field Rendering”, SIGGRAPH, 1996; S. Gortler, R. Grzeszczuk, R. Szeliski, M. Cohen, “The Lumigraph”, SIGGRAPH, 1996; B. Mildenhall et al., “NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis”, ECCV, 2020; B. Kerbl et al., “3D Gaussian Splatting for Real-Time Radiance Field Rendering”, ACM TOG (SIGGRAPH), 2023 — image-based rendering (ch. 6).
• G. Bradski, “The OpenCV Library”, Dr. Dobb’s Journal, 2000 — opencv.org: the lab tool (Sobel, Harris, SIFT, Canny, stereo, calibration).