Introduction

This is the second half of the road boundary problem you started in Lab 4.

In Lab 4 you produced an edge map: a set of candidate pixels, most of which are not road boundary. You measured recall (is the boundary in there?) and selectivity (how much junk came with it), and you could not sensibly measure precision, because an edge map is thousands of pixels and a boundary is a thin curve.

Today you fit models to those candidates. A line has two parameters, so once you have committed to a line you have made a real, falsifiable claim about where the road boundary is — and precision finally becomes a fair thing to measure.

You will build three fitting tools, in increasing order of robustness:

1. Least squares — fast, optimal when the noise is Gaussian, and destroyed by a single bad point.
2. RANSAC — slower, and does not care about outliers.
3. The Hough transform — finds several structures at once without being told how many.

You will then discover that fitting is the easy part, and deciding which lines are the road boundary is the hard part.

Reading

Computer Vision: Algorithms and Applications (2nd ed.), Szeliski — Sec. 8.1.1, 8.1.3, 8.1.4, 7.4.2, App. A.2.

2D alignment using least squares, iterative algorithms, robust least squares and RANSAC; Hough transforms; linear least squares.

Data

The KITTI Road benchmark, same as Labs 4 and 5. See Getting the KITTI data. You will reuse your edge detector and your scoring code from Lab 4.

A note on loading the data

Parsing KITTI’s calibration format and decoding its colour-coded ground truth is plumbing, not computer vision, and debugging it eats time you should be spending on the lab. A small helper module is provided: kitti.py.

import kitti

ds  = kitti.Dataset("path/to/data_road")     # point at the extracted folder
img = ds.image("um_000032")                  # left image, RGB uint8
cal = ds.calib("um_000032")                  # cal.K, cal.fx, cal.baseline, ...
pos, valid = ds.ground_truth("um_000032")    # boolean masks

It deliberately does not implement anything you are asked to write yourself — no edge detection, no region of interest, no scoring. You are free to ignore it and do your own file handling if you prefer.

Part 1: Fitting a line to points

Task 1: ordinary least squares

Fit \(y = mx + c\) to a set of points by minimising \(\sum_i (y_i - mx_i - c)^2\). Derive or state the closed-form solution and implement it.

Generate synthetic points on a known line, add Gaussian noise, and confirm you recover the parameters.

Task 2: where least squares breaks

Two failures, both of which matter for roads.

Vertical lines. Fit points on a near-vertical line. Explain what happens to \(m\) and why. This is not a numerical accident — it is built into the \(y = mx + c\) parameterisation.

Outliers. Take your synthetic line, add a single point far away, and refit. Plot the fit before and after. Report how far the estimated line moved.

Task 3: total least squares

Ordinary least squares minimises vertical distance. Total least squares minimises perpendicular distance, which removes the vertical-line problem.

Represent the line as \(ax + by + c = 0\) with \(a^2+b^2=1\). Then the perpendicular distance from \((x_i,y_i)\) is \(|ax_i + by_i + c|\).

Implement TLS: subtract the centroid, form the \(n \times 2\) matrix of centred coordinates, and take the singular vector corresponding to the smallest singular value as \((a,b)\). Then \(c = -(a\bar{x} + b\bar{y})\).

Repeat the vertical-line test from Task 2 and show TLS handles it. Then repeat the single-outlier test — does TLS help? Explain your answer.

Part 2: RANSAC

Task 4: implement it

Implement RANSAC for line fitting:

1. Sample the minimum number of points needed to define the model (2 for a line).
2. Fit the model to that sample.
3. Count inliers — points within a distance \(t\) of the model.
4. Repeat \(k\) times, keep the model with the most inliers.
5. Refit using all inliers of the winning model.

Step 5 matters and is often skipped. Show the difference it makes.

Task 5: how many iterations?

The probability of at least one all-inlier sample after \(k\) iterations is \(1-(1-w^n)^k\), where \(w\) is the inlier fraction and \(n\) the sample size. Solving for \(k\): \[ k = \frac{\log(1-p)}{\log(1-w^n)}. \]

Tabulate \(k\) for \(p = 0.99\), \(n = 2\), and \(w \in \{0.9, 0.7, 0.5, 0.3, 0.1\}\).

Then verify it empirically: generate data with a known inlier fraction, run RANSAC many times at various \(k\), and plot how often it finds the right line. Does the theory match?

Task 6: choosing the threshold

Run RANSAC on the same data with \(t\) far too small, far too large, and sensible. Describe the failure in each direction. How would you set \(t\) if you knew the standard deviation of the noise?

Part 3: The Hough transform

RANSAC finds one dominant model. A road has at least two boundaries, plus lane markings. The Hough transform finds many at once.

Task 7: build the accumulator

Implement the line Hough transform yourself, using the \((\rho, \theta)\) parameterisation: \[ \rho = x\cos\theta + y\sin\theta. \]

For each edge pixel, vote for every \((\rho,\theta)\) cell consistent with it. Then find peaks in the accumulator.

Use \(\theta\) resolution of 1 degree and \(\rho\) resolution of 1 pixel to start.

Visualise the accumulator itself, not just the detected lines. For a KITTI image, the accumulator is a picture worth looking at, and it explains the behaviour you will see next.

Task 8: resolution

Vary the \(\rho\) and \(\theta\) bin sizes. Show a case where the bins are too coarse (distinct lines merge into one peak) and one where they are too fine (votes for a single line spread across neighbouring bins and no peak stands out).

Task 9: gradient direction as a shortcut

You already computed gradient orientation in Lab 4. At an edge pixel, the line through it is (approximately) perpendicular to the gradient — so you only need to vote for \(\theta\) near that one value, not all 180.

Implement this, allowing a tolerance of a few degrees around the predicted \(\theta\). Report the speed-up and whether the detected lines changed.

Part 4: Back to the road

Now put it together on the KITTI images.

Task 10: from edges to lines

Take your Lab 4 edge map, restricted to your ROI, and extract lines with your Hough transform. Draw them on the image.

You will get a lot of them. Filter by orientation — a road boundary in this camera geometry cannot be horizontal — and report how many survive.

Task 11: selection

This is the real work of the lab.

You have many candidate lines and you want the road boundary. Design and implement a selection rule. Some ideas, none of which is the answer:

• Split candidates by slope sign into a left group and a right group, and take the strongest from each.
• Require the two chosen lines to intersect above the image, near a plausible vanishing point.
• Weight candidates by how many edge pixels actually support them, not just by accumulator height.
• Reject lines that pass through the middle of the road region.

State your rule, implement it, and show its output on several images.

Task 12: score it

Rasterise your selected lines and score them against the ground-truth road boundary using the Lab 4 procedure (\(\tau = 3\) px). Report precision, recall and selectivity for at least 10 images from each of the three categories, alongside your Lab 4 edge-map numbers for the same images.

Task 13: face the results

Compare the two stages honestly. You should find precision has improved and recall has fallen — you traded coverage for commitment.

Then look at the three categories separately. They will not behave the same. One of them will be markedly worse than the others, and quite possibly worse than the Lab 4 edge map you started from.

Work out which, and explain why the model is wrong for those images — not why your code is buggy. Think about what “the longest oblique line on the left” actually corresponds to in a multi-lane scene.

Then answer: what would you change? A different model? More lines? A curve instead of a line? A different way of choosing? You do not have to implement it, but a specific, argued proposal is what is being marked here.

Deliverables

Your notebook must contain the following.

• Ordinary least squares with its closed form, verified on synthetic data.
• The two failure demonstrations: a near-vertical line, and a single outlier with the resulting shift quantified.
• Total least squares via SVD, both failure cases retested, and an explicit answer to whether TLS fixes outliers.
• A RANSAC implementation including the refit-on-inliers step, with evidence of what that step changes.
• A table of \(k\) for \(w \in \{0.9, 0.7, 0.5, 0.3, 0.1\}\) and an empirical check that the theory holds.
• The inlier-threshold study (too small, too large, sensible).
• Your own Hough accumulator, visualised, plus the resolution study showing bins that are too coarse and too fine.
• Gradient-direction voting with a measured speed-up.
• Detected lines drawn on KITTI images, and the count surviving your orientation filter.
• Your selection rule, stated and implemented, with output on several images.
• A table of precision, recall and selectivity for all three categories, beside your Lab 4 numbers for the same images.
• The Task 13 diagnosis: which category fails, why the model is wrong for it, and a specific proposal for what to change.

Submission

Via Canvas. Please submit a single executed Jupyter notebook — one that has been run top to bottom, so that every figure and number listed above is visible in the submitted file. Code that has not been executed cannot be marked.

Parting thoughts

• Implement least squares, TLS, RANSAC and the Hough accumulator yourself. You may use cv.HoughLinesP in Part 4 to cross-check your own implementation, and should say whether they agree.
• If you do use cv.HoughLinesP, note that its output shape changed between OpenCV 4 and 5 — older tutorials index it as lines[:,0], which will fail on newer versions. lines.reshape(-1,4) works with both.
• Vectorise the Hough voting. A Python loop over every edge pixel and every \(\theta\) will be painfully slow; building an array of \(\theta\) values and using broadcasting is a few lines and hundreds of times faster.
• The failure you will hit in Task 13 is not a defect in the assignment. Classical model fitting assumes you know the shape of the thing you are looking for. When that assumption is wrong, no amount of tuning rescues it — which is a large part of why the field moved towards learned models. Lab 10 picks this up.