Least squares: fitting noisy data

A noisy camera

The overhead camera looks straight down and reports pixels $(u, v)$: column and row. For points at ball height, table position and pixel are linked by a 2×3 matrix $A$ of six unknowns, $[x, y] = A\,[u, v, 1]$, so calibrating means finding $A$ from pads whose positions you know. The camera moves every run.

This time the marker between the fingers is partly hidden, so the camera finds it only to within about 2.5 pixels (roughly 6 mm). Reading again without moving gives the same answer: it's the same picture. The balls' centres are still found exactly.

With three pads, solve_affine from step 1 (included below) fits the three noisy readings exactly, noise and all. Near those pads the map is fine; away from them the error grows. The starter calibrates on three pads: run it a few times and it misses a ball in about a third of the runs, while reporting a residual of zero. A perfect fit to noisy data is a warning sign.

More equations than unknowns

Twelve pads give 24 equations for 6 unknowns. With noise, no $A$ satisfies them all, so find the best compromise. For pad $i$, the residual $\mathbf{r}_i$ is how far the map's prediction lands from the pad:

$$\mathbf{r}_i = A \begin{bmatrix} u_i \\ v_i \\ 1 \end{bmatrix} - \begin{bmatrix} x_i \\ y_i \end{bmatrix}$$

Least squares chooses the $A$ that makes the sum of squared residuals, $\sum_i \lVert \mathbf{r}_i \rVert^2$ (each residual's squared length, summed), as small as possible. With $M$ the $N \times 3$ matrix of rows $[u_i, v_i, 1]$ and $\mathbf{x}$ the column of the pads' x-values, the best first row of $A$ is

$$\hat{\mathbf{w}} = (M^\top M)^{-1} M^\top \mathbf{x}$$

and $\mathbf{y}$ gives the second row. $M^\top$ is $M$ transposed (rows become columns). np.linalg.lstsq(M, points, rcond=None) solves both at once, more accurately than inverting $M^\top M$. Its first result is 3×2: transpose it (.T) to get $A$.

With three pads, least squares gives the exact fit again. With twelve, their errors partly cancel, and because the pads surround the balls, the map holds everywhere a ball can be.

Seeing with a Camera, step 5 fits a camera's pose to many points the same way.

Your task

1. Write fit_affine(pixels, points) for any number $N \ge 3$ of pairs (pixels and points are both $N \times 2$). Return the 2×3 matrix $A$.
2. Read the marker on all 12 pads and fit $A$ with fit_affine. The starter prints the RMS (root-mean-square) residual and draws each residual at its pad, 5 times life size.
3. Put all four balls in the cup.