Introduction

The goal of this lab is to compute image gradients and use them to find the edges that matter in a driving scene.

This is the first half of a two-part problem. Here you will produce an edge map of the road — a set of pixels that plausibly lie on a road boundary or a lane marking. In Lab 6 you will come back to these same images and fit actual lines to those pixels using the Hough transform and RANSAC. By the end of Lab 6 you will have something that genuinely detects road boundaries. Today you build the raw material.

Gradients are the workhorse of classical computer vision. Corner detection (Lab 7), local descriptors (Lab 7) and optical flow are all built on what you write here.

Reading

Computer Vision: Algorithms and Applications (2nd ed.), Szeliski — Sec. 3.2.3, 7.2.1.

Band-pass and steerable filters; edge detection.

Data

This lab uses the KITTI Road benchmark. See Getting the KITTI data — run fetch-kitti.sh --left-only; you do not need the stereo images yet.

Three sample scenes are included with the handout in ../data/kitti-samples so you can start before the download finishes. Work with all three categories:

• um_* — urban marked road
• umm_* — urban multiple marked lanes
• uu_* — urban unmarked road

A method that only works on um images is not finished.

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: Computing gradients

Start with the toy image square.png, a white square over a black background. A synthetic image makes it far easier to tell whether your gradients are correct. Once your code works, move to the KITTI images.

1. Given an image \(I\), compute \(\frac{\partial I}{\partial x}\).
2. Given an image \(I\), compute \(\frac{\partial I}{\partial y}\).
3. Compute the gradient magnitude and the edge orientation for each pixel. Recall that edge orientation is the normal to the edge through that pixel, i.e. it is perpendicular to the gradient direction.
4. Colour each pixel according to its edge orientation and display the result.
5. Construct a gradient magnitude histogram for pixels with non-zero gradient magnitude. Use 32 bins.
6. Construct a gradient orientation histogram for the same pixels. Use 360 bins, assuming orientations vary between \(-180\) and \(+180\) degrees.

Task: what does the orientation histogram tell you?

Produce the orientation histogram for a um image and for a uu image. The marked road should show structure that the unmarked one does not. Describe it, and say which orientations you would expect lane markings to occupy given where the camera sits.

Task: rotation

For an image \(I\) and its rotated version \(I_\mathrm{rot}\), show that the gradient magnitude histogram stays roughly the same while the orientation histogram changes. Implement a method that returns True if two histograms are the same and False otherwise.

Hold on to what you observe here. It is exactly the problem you will have to solve when you build a rotation-invariant descriptor in Lab 7.

Part 2: From gradients to an edge map

Raw gradient magnitude is not an edge map. Turn it into one.

Task 1: thresholding

Scale gradient magnitudes to \([0, 255]\), choose a threshold, and keep the pixels above it.

Show results for a threshold that is clearly too low, one that is clearly too high, and your chosen value. Say how you chose it. A threshold picked by staring at one image is a threshold that will fail on the next one — can you choose it from the image statistics instead?

Task 2: Canny

Implement or apply the Canny edge detector and compare its output against your simple threshold on the same image.

Canny adds two things your threshold does not have: non-maximum suppression and hysteresis. Explain, with cropped examples from a KITTI image, what each one buys you.

You may use cv.Canny here, but you must explain what it is doing.

Task 3: restricting attention to the road

Most of a KITTI image is sky, buildings and trees, and none of it is road. Define a region of interest — a polygon covering the part of the image where road can plausibly appear — and discard edges outside it.

Show your ROI and the edge map before and after masking. Roughly what fraction of your edge pixels did the ROI remove?

A fixed polygon is fine for now. Note in your write-up what would break it.

Part 3: Scoring against ground truth

This is the part that separates “it looks about right” from “it works”.

KITTI provides hand-labelled ground truth in gt_image_2. The masks are colour coded: magenta is the positive region (road, or ego lane), red is the negative region, and black marks “do not care” pixels which must be excluded from any score you compute.

Task 4: build a boundary reference

The ground truth marks the road region, not its boundary. Extract the boundary of the magenta region — its outline — and treat those pixels as the reference edge map.

How these measurements work

This is the first lab in which you evaluate your own output against a reference, so here is the machinery. You will use it again in Labs 5, 6 and 9.

Counting outcomes

Every pixel you could have flagged falls into one of four boxes. Write \(P\) for the set of pixels you marked as edge, and \(R\) for the set of reference boundary pixels:

From these, \[ \text{precision} = \frac{TP}{TP+FP}, \qquad \text{recall} = \frac{TP}{TP+FN}. \]

Precision answers “of the things I flagged, how many were right?” Recall answers “of the things I should have found, how many did I find?” They trade off: flag every pixel and recall is \(1\) while precision is terrible; flag one pixel you are certain about and precision is \(1\) while recall is nearly \(0\).

The F1 score is their harmonic mean, used when you want one number: \[ F_1 = \frac{2 \cdot \text{precision} \cdot \text{recall}}{\text{precision} + \text{recall}}. \]

Note that accuracy, \((TP+TN)/(\text{everything})\), is useless here. The boundary is under half a percent of the image, so predicting “no edge anywhere” scores over 99% accurate. Never report accuracy on a problem this unbalanced.

Why you need a tolerance

Your edge sits one pixel to the left of the reference. Counted strictly, that is both a false positive and a false negative — you are punished twice for being almost exactly right. Since the reference was traced by a human, that is unreasonable.

So we match within a tolerance \(\tau\). A detected pixel counts as a true positive if there is some reference pixel within \(\tau\) of it, and a reference pixel counts as found if there is some detected pixel within \(\tau\) of it. Note this makes precision and recall separate calculations rather than two readings of one contingency table — that is normal for boundary evaluation.

The cheap way to compute both is a distance transform. scipy.ndimage.distance_transform_edt(~mask) returns, for every pixel, the distance to the nearest True pixel of mask. So:

d_to_ref  = distance_transform_edt(~reference)   # distance to nearest reference pixel
d_to_pred = distance_transform_edt(~predicted)   # distance to nearest detected pixel

precision = (d_to_ref [predicted] <= tau).mean()
recall    = (d_to_pred[reference] <= tau).mean()

Two lines, no loops. Restrict both to the valid (non-void) pixels first.

Excluding the “do not care” pixels

KITTI marks some pixels black, meaning the annotator declined to label them. Those must be dropped from both sets before you count anything — otherwise your numbers depend on how much unlabelled area happens to be in each image and are not comparable between scenes.

Task 5: recall and selectivity

Before you measure anything, understand what you are measuring.

The reference boundary is a thin curve — roughly \(0.4\%\) of the pixels in the image. A correct edge detector will also fire on the kerb, the lane markings, other vehicles, buildings and trees, because those are all genuine edges. So the number of edge pixels you produce will exceed the number of reference pixels by an order of magnitude or more, and precision will be low no matter how good your detector is. That is a property of the task at this stage, not a bug in your code. Do not go chasing it.

What you can meaningfully measure right now is whether the boundary survives, and how much junk you carry along with it. An edge pixel a couple of pixels away from the reference should not count as a miss, so use a tolerance of \(\tau\) pixels. Report:

• recall — the fraction of reference boundary pixels lying within \(\tau\) of one of your detected edge pixels. This is your primary number. It asks: is the road boundary still in there somewhere?
• selectivity — the number of detected edge pixels divided by the number of reference boundary pixels. Lower is better; \(1.0\) would mean you produced exactly as many candidates as there are boundary pixels. This is how much work you are leaving for Lab 6.
• precision — report it as a diagnostic, but do not treat it as a score.

Use \(\tau = 3\) pixels, over at least 10 images from each of the three categories. Remember to exclude the “do not care” pixels from every count.

Task 6: the trade-off

Sweep your edge threshold and plot recall against selectivity (a log scale on the selectivity axis is easiest to read). Mark the operating point you would hand to Lab 6, and justify it: a detector that keeps \(95\%\) of the boundary but hands on \(50\times\) as many candidates may well be a worse starting point than one that keeps \(80\%\) and hands on \(5\times\).

Then answer:

• How much does the ROI mask change recall, and how much does it change selectivity? Give both as factors.
• Which category (um, umm, uu) gives the best recall? The answer is probably not the one you expected — explain what is going on in the images that accounts for it.
• Is your system failing to find boundaries, or finding too many things that are not boundaries? These are different failures with different fixes.

Keep your numbers. In Lab 6 you will fit lines to these candidates, and precision finally becomes a fair thing to measure.

Deliverables

Your notebook must contain the following.

• \(I_x\), \(I_y\), gradient magnitude and edge orientation, including the orientation-coloured image.
• Gradient magnitude (32-bin) and orientation (360-bin) histograms, and the um vs uu comparison.
• The rotation experiment and your histogram-comparison method.
• Threshold results for a value that is too low, one too high, and your chosen value, with your selection rationale.
• Canny vs simple threshold, with cropped examples showing what non-maximum suppression and hysteresis each contribute.
• Your ROI polygon, the edge map before and after masking, and the fraction of edge pixels removed.
• A table of recall, selectivity and precision at \(\tau = 3\) px for at least 10 images from each of the three categories, with void pixels excluded.
• A recall-vs-selectivity curve with your chosen operating point marked.
• Answers on the ROI trade-off (both factors), the category comparison, and which kind of failure dominates.

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 Part 1 using vanilla numpy and scipy array operations, reusing the convolution you wrote in Lab 3. You may use cv.Canny in Part 2.
• Watch your data types. Image derivatives are signed; computing them on an 8-bit unsigned image silently discards every negative value. Convert to a float type first.
• Blur before you differentiate. Differentiation amplifies noise, which is why every practical edge detector smooths first. You already have the Gaussian from Lab 3 — try \(\sigma = 1\) and \(\sigma = 3\) and see what it does to your precision/recall numbers.
• The “do not care” pixels are not optional. Scoring against them will quietly flatter or punish your results depending on the image, and your numbers will not be comparable between scenes.
• The orientation histogram in Part 1 is a simplified Histogram of Oriented Gradients (HOG) — one of the most successful hand-designed features in the history of the field, and the thing your Lab 10 CNN will be compared against.