Hough numericals, fitting, RANSAC & snakes

This page shows the Hough transform as a hand calculation. Then it asks how to fit a line or other model to noisy data. You will see least squares and why outliers spoil it. You will see how RANSAC handles outliers, with the iteration-count formula. You will also see how a deformable contour (snake) fits itself to an object.

Hough transform: ρ-θ numerical

The line representation is $\rho = x\cos\theta + y\sin\theta$. $\rho$ is the perpendicular distance from the origin to the line. $\theta$ is the angle of that perpendicular. Each edge point votes in the accumulator cell $(\theta,\rho)$ for every candidate angle.

Problem (from the slides). The image has three points $P_1=(0,1)$, $P_2=(1,2)$, $P_3=(2,3)$. Use four test angles $\theta\in\{0^\circ,45^\circ,90^\circ,135^\circ\}$. Find the line.

Useful values: $\cos0=1,\ \sin0=0$
$\cos45=\sin45=0.71$
$\cos90=0,\ \sin90=1$
$\cos135=-0.71,\ \sin135=0.71$.

Step 1: compute $\rho$ for each point at each angle.

$P_1(0,1)$:

$P_2(1,2)$:

$P_3(2,3)$:

(With the exact $\sin45=0.7071$ the values are 2.12 and 3.54. The slide rounds $\cos45$ to 0.71 first, so it gets 2.13 and 3.55. The exam accepts either.)

Step 2 (summary table of the $\rho$ values).

Point$\theta=0^\circ$$45^\circ$$90^\circ$$135^\circ$
P1 (0,1)0.000.711.000.71
P2 (1,2)1.002.132.000.71
P3 (2,3)2.003.553.000.71

Step 3: accumulate votes. Cast one vote into cell $(\theta,\rho)$ for every calculated pair. In the accumulator, rows are $\rho$ and columns are $\theta$. Each entry lists the voters:

ρ \ θ0°45°90°135°
0.001 (P1)000
0.7101 (P1)03 (P1,P2,P3)
1.001 (P2)01 (P1)0
2.001 (P3)01 (P2)0
2.1301 (P2)00
3.00001 (P3)0
3.5501 (P3)00

Check: $3\text{ points}\times4\text{ angles}=12$ votes. The table totals 12.

Step 4: detect the line. The peak bin has 3 votes at $(\theta=135^\circ,\ \rho=0.71)$. Substitute back:

$$ -0.71x + 0.71y = 0.71 \;\Rightarrow\; -x + y = 1 \;\Rightarrow\; y = x + 1 $$

The HT detects the line $y=x+1$ passing through all three points. (Check: the distance of $y=x+1$ from the origin is $1/\sqrt2=0.71$.)

Extra practice 1. The points are $(1,1),(2,2),(3,3)$ with the same four angles (exact values).

Point$0^\circ$$45^\circ$$90^\circ$$135^\circ$
(1,1)11.4110
(2,2)22.8320
(3,3)34.2430

At $135^\circ$ all three give $\rho=0$, so cell $(135^\circ,0)$ has 3 votes. Equation: $-0.71x+0.71y=0\Rightarrow y=x$.

Extra practice 2 (vertical line, impossible in m-c). The points are $(2,0),(2,1),(2,3)$. At $\theta=0^\circ$, $\rho=x=2$ for all three points. This gives 3 votes at $(0^\circ,2)$, so the line is $x=2$.

Quote this procedure in the exam. Choose the angle set. Compute $\rho$ for each point and angle. Tabulate the values. Build the accumulator. Pick the cell with the maximum. Convert back to $y=mx+c$ (divide by $\sin\theta$), or write $x\cos\theta+y\sin\theta=\rho$.

Feature matching and why we need fitting

To compare two images, match their features. These are the ways to search for the best match:

Expect many wrong matches, even when you pick the best match. These are outliers. A method that uses all the matches without checking is pulled off by the outliers. This is the reason for robust fitting.

Fitting

Fitting means to choose a parametric model that represents a set of features. Simple models are lines and circles. A car outline is a complicated model. The issues are:

Fitting techniques covered: least squares methods, RANSAC, Hough transform, EM (Expectation Maximization).

Least squares: fitting a line

$n$ points lie roughly on a line. Pick the line that makes the vertical gaps (residuals) between the points and the line as small as possible in total. Squaring the gaps gives large misses a large weight. It also gives a closed-form answer.

The data are $(x_1,y_1),\dots,(x_n,y_n)$. The line equation is $y_i - m x_i - b = 0$ ($b$ is the intercept; the slides use $c$ elsewhere). Find $(m,b)$ to minimise

$$ E = \sum_{i=1}^{n}(y_i - m x_i - b)^2 $$

$E$ = sum of squared vertical errors, $m$ = slope, $b$ = intercept.

Matrix form and the normal equation

Stack the data: $Y=[y_1,\dots,y_n]^T$, $X$ has rows $[x_i\ \ 1]$ and $B=[m\ \ b]^T$. Then

$$ E = \|Y - XB\|^2 = (Y-XB)^T(Y-XB) = Y^TY - 2(XB)^TY + (XB)^T(XB) $$

Set the derivative with respect to $B$ to zero:

$$ \frac{dE}{dB} = -2X^TY + 2X^TXB = 0 \;\Rightarrow\; X^TXB = X^TY \quad\text{(normal equation)} $$
$$ B = (X^TX)^{-1}X^TY $$

$(X^TX)^{-1}X^T$ is the pseudo-inverse of $X$. The equivalent scalar formulas are $m=\dfrac{n\sum xy-\sum x\sum y}{n\sum x^2-(\sum x)^2}$, $b=\dfrac{\sum y - m\sum x}{n}$.

Worked numerical. Fit a line to the six points of the RANSAC lecture: $(1,2),(2,4),(3,6),(4,8),(5,10),(6,15)$.

$n=6$, $\sum x=21$, $\sum y=45$, $\sum xy=2+8+18+32+50+90=200$, $\sum x^2=1+4+9+16+25+36=91$.

In normal-equation form, $X^TX=\begin{bmatrix}91&21\\21&6\end{bmatrix}$, $X^TY=\begin{bmatrix}200\\45\end{bmatrix}$. $\det=91\cdot6-21^2=546-441=105$.

$$ (X^TX)^{-1}=\frac1{105}\begin{bmatrix}6&-21\\-21&91\end{bmatrix},\quad B=\frac1{105}\begin{bmatrix}6\cdot200-21\cdot45\\-21\cdot200+91\cdot45\end{bmatrix}=\frac1{105}\begin{bmatrix}255\\-105\end{bmatrix}=\begin{bmatrix}2.43\\-1\end{bmatrix} $$

So $y\approx2.43x-1$. Residuals ($y-\hat y$): $0.57,\ 0.14,\ -0.29,\ -0.71,\ -1.14,\ 1.43$. $E\approx4.29$.

The first five points are exactly on $y=2x$, but the fit gives slope 2.43 and not 2. The single outlier $(6,15)$ pulls the line. RANSAC fixes this weakness.

Total least squares

Ordinary least squares measures the vertical error and fails for vertical lines. Total least squares uses the perpendicular distance. Write the line as $ax+by=d$ with unit normal $\mathbf w=(a,b)$ and $a^2+b^2=1$. The distance of $(x_i,y_i)$ from the line is $|ax_i+by_i-d|$. Find $(a,b,d)$ to minimise

$$ E=\sum_{i=1}^n (a x_i + b y_i - d)^2 $$

$d$ = distance of the line from the origin and $(a,b)$ = unit normal direction. Standard result: the best line passes through the centroid of the points. $(a,b)$ is the eigenvector of the scatter matrix of the data with the smallest eigenvalue.

Extra practice. The points $(2,0),(2,1),(2,3)$ are on a vertical line. Ordinary least squares has $\sum(x-\bar x)^2=0$ in its denominator, so it fails. TLS gives $a=1,b=0,d=2$ with $E=0$: the line $x=2$.

Robust estimators

With squared error, one far point dominates. A robust estimator replaces the square with a function that stops growing for large errors.

$$ E=\sum_i \rho(u_i;\sigma),\qquad u_i = a x_i + b y_i - d,\qquad \rho(u;\sigma)=\frac{u^2}{\sigma^2+u^2} $$

$u_i$ = residual (error) of point $i$ for the model parameters $h=(a,b,d)$ and $\rho$ = robust function with scale parameter $\sigma$. (This $\rho$ is not the Hough $\rho$.)

Extra practice. $\sigma=1$. Compare squared error to $\rho$:

$u$$u^2$$\rho=u^2/(1+u^2)$
0.50.250.20
110.50
390.90
101000.99

An outlier with $u=10$ costs 100 in least squares but at most about 1 here, so it does not dominate.

RANSAC

RANSAC = RANdom SAmple Consensus (Fischler and Bolles, 1981). It handles a large proportion of outliers. Context from the slides: some points are static in the world and some are not. We must find the right points to compute pose. For data with outliers, the "best fit" (least squares) line can be far from the "correct" line.

Do not let every point decide the line. Guess the line from the smallest possible sample (2 points). Count how many other points agree with the guess. Repeat with different random guesses. Keep the guess with the most supporters. A random pair sometimes contains an outlier. With enough tries, at least one pair has only inliers, and that line wins.

Algorithm

  1. Sample at random the number of points the model needs (2 for a line).
  2. Solve for the model parameters with the sample.
  3. Score the model by the fraction (or count) of inliers within a preset threshold $\delta$ of the model.

Repeat 1-3 until the best model is found with high confidence.

δ band
Green (ringed): the 2 random sample points that define the candidate line. Blue: inliers inside the $\pm\delta$ band (the consensus set). Red: outliers. The score is the number of blue points plus the sample points.

In the slide example, one random line has a consensus set of $C_i=6$ points. Another random line has $C_j=14$. RANSAC keeps the second line.

RANSAC for a general model

A model has a minimal set: the smallest number of samples that can compute it. Image transformations are also models. $s$ is the minimal number of point pairs or matches:

ModelMinimal set $s$
Line2 points
Translation1 point pair
Homography (plane)4 point pairs
Fundamental matrix8 point pairs (really 7, "let's not go there")

Algorithm (general): select $s$ points (or pairs) at random as a sample. Instantiate a model. Get the consensus set $C_i$. If $|C_i|>T$, stop and return the model. Repeat for $N$ trials. Return the model with the maximum $|C_i|$.

Distance threshold

Assume the location noise is Gaussian with variance $\sigma^2$. The distance $d$ of an inlier from the model then follows a chi distribution with $k$ degrees of freedom. $k$ is the dimension of the Gaussian. For one dimension (distance from a line), $k=1$:

$$ f(d)=\frac{\sqrt2\,e^{-d^2/(2\sigma^2)}}{\sqrt\pi\,\sigma},\quad d\ge0 $$
$$ t^2 = 3.84\,\sigma^2 \quad(\text{i.e. } t\approx1.96\sigma) $$

$t$ is the distance threshold. With $t^2=3.84\sigma^2$, an inlier has a 95% probability that $d<t$. In practice, you usually set $t$ by experiment.

Choosing the parameters

Calculating N (the iteration-count formula)

  1. $s$ = number of points that the solution needs.
  2. $p$ = desired probability of success.
  3. $e$ = proportion of outliers, so the inlier proportion is $1-e$.
  4. $P(\text{one sample is all inliers})=(1-e)^s$.
  5. $P(\text{one sample has at least one outlier})=1-(1-e)^s$.
  6. $P(\text{all }N\text{ samples have an outlier})=\big(1-(1-e)^s\big)^N$.
  7. This must be less than $1-p$: $\big(1-(1-e)^s\big)^N<1-p$.
  8. Take the log of both sides. The inequality flips because $\log(1-(1-e)^s)<0$:
$$ N > \frac{\log(1-p)}{\log\!\big(1-(1-e)^s\big)} $$

$N$ = number of random trials; $p$ = required confidence that at least one sample is outlier-free; $e$ = outlier ratio; $s$ = sample size. Round $N$ up to the next integer. You can use any log base.

Check the slide table ($p=0.99$, so $\log(1-p)=\ln0.01=-4.605$):

Full table from the slides ($p=0.99$; rows = $s$, columns = outlier proportion $e$):

$s$5%10%20%25%30%40%50%
2235671117
33479111935
435913173472
54612172657146
64716243797293
748203354163588
8592644782721177

Takeaways: $N$ increases steeply with $s$. As $e\to1$, it grows without limit.

Extra practice. Line fitting ($s=2$) with 30% outliers and $p=0.95$. $1-(0.7)^2=0.51$, $\ln0.51=-0.673$
$\ln(0.05)=-2.996$. $N>4.45$, so $N=5$. Same data with $p=0.99$ needs $N=7$ (table).

$N=f(e,s,p)$ and is not a function of the number of points (matches). A dataset of 100 points and a dataset of 100,000 points with the same outlier ratio need the same $N$. This is a common short question.

RANSAC for homography

  1. Select four feature pairs at random.
  2. Compute the exact homography $H_k$.
  3. Find the inliers where $SSD(p_i',H_kp_i)<\varepsilon$.
  4. Keep $H_k$ if $C_k$ is the largest inlier set so far.
  5. Go to step 1 for a fixed number of trials.
  6. Compute the least-squares $H$ again on all the $C_k$ inliers.

Step 6 is important. The 4-point fit is exact but noisy. A new fit on all the inliers gives the final accurate model. (In the slides, RANSAC matches the product box: the green box is the recovered homography and the lines are the remaining matches.)

Adaptively determining the number of samples

The outlier ratio is usually unknown. Start with the worst case and adapt when you find better models. If 80% of the points are inliers, $e=0.2$.

So $N$ only becomes smaller when you find a better model.

RANSAC numerical (from the slides)

Points: P1 (1,2), P2 (2,4), P3 (3,6), P4 (4,8), P5 (5,10), P6 (6,15). Distance threshold $=1.5$. The error is the vertical residual $e_i=|y_{actual}-y_{predicted}|$. A point is an inlier if $e_i\le1.5$.

Iteration 1. Select $P_1(1,2)$ and $P_4(4,8)$ at random.

Slope $m=\dfrac{8-2}{4-1}=2$; intercept $c=2-(2\times1)=0$. Line: $y=2x$.

PointActual yPredicted yErrorInlier?
P1220Yes
P2440Yes
P3660Yes
P4880Yes
P510100Yes
P615123No

Number of inliers: 5.

Iteration 2. Pick $P_2(2,4)$ and $P_6(6,15)$.

$m=\dfrac{15-4}{6-2}=\dfrac{11}{4}=2.75$
$c=4-(2.75\times2)=-1.5$. Line: $y=2.75x-1.5$.

PointActual yPredicted yErrorInlier?
P121.250.75Yes
P2440Yes
P366.750.75Yes
P489.51.5Yes (1.5 ≤ 1.5)
P51012.252.25No
P615150Yes

Inliers: P1, P2, P3, P4, P6. Total: 5.

Iteration 3. Pick $P_3(3,6)$ and $P_5(5,10)$: slope $\frac{10-6}{5-3}=2$, line $y=2x$ again, 5 inliers.

Compare all iterations.

IterationModelNo. of inliers
1$y=2x$5
2$y=2.75x-1.5$5
3$y=2x$5

The inlier counts are equal, so RANSAC picks the model with the smallest total residual error.

For $y=2x$: total error $=0+0+0+0+0+3=3$. For $y=2.75x-1.5$: $0.75+0+0.75+1.5+2.25+0=5.25$.

So RANSAC selects $y=2x$ as the final model. In a full run, you then refit least squares on the 5 inliers. Here this gives exactly $y=2x$.

Slide exercise "Solve RANSAC", worked. Points P1 (1,1), P2 (2,2), P3 (3,3), P4 (4,4), P5 (5,8), P6 (6,6). The slide gives no threshold. Use $t=1.5$ and the vertical error.

The best model is $y=x$ with 5 inliers. P5 is the outlier. Ordinary least squares on all six points gives a line tilted toward P5 ($m\approx1.26$, $b\approx-0.4$).

Least squares vs RANSAC (and Hough)

AspectLeast squaresRANSACHough transform
Usesall pointsrandom minimal samples, scores by consensusevery point votes in parameter space
Outliersvery sensitive (squared error)tolerates a large fractiontolerant (votes scatter)
Resultone exact closed-form answerprobabilistic; needs $N$ trials and threshold $t$peaks in accumulator; many shapes at once
Cost grows withnumber of points$s$ and outlier ratio (not number of points)number of model parameters (accumulator dimension)
Typical useclean data, final refinement on inliersfeature matching, homography, F matrixlines, circles, simple shapes

Deformable contours (active contours, snakes)

A deformable contour (also called an active contour or snake) is a curve that moves to approximate the perimeter of an object.

Think of a rubber band of any shape around an object. Image edges pull it inwards (or outwards). Its own stiffness keeps it smooth and tight. It deforms over time until it rests on the outline of the object.

object edgeinitial snake
Dashed amber: the initial contour with its control points. Red arrows: the pull from the strong edge (object boundary, blue). After enough iterations, the snake is on the edge.

Procedure

  1. Place a contour (open or closed) near the image contour of interest. You can place it by hand or take it from another algorithm. "Seeding" the snake is critical to success.
  2. Repeat: forces that control the shape and location of the contour pull it toward the target.
  3. Stop the deformation when the contour is stable, or after a fixed number of iterations.

The three forces and the energy functional

The 3-forces model has these terms:

  1. A continuity term $E_{cont}$: keeps the contour continuous.
  2. A smoothness (curvature) term $E_{curv}$: keeps the contour smooth.
  3. An edge attraction term $E_{img}$: pulls the contour to the closest image edge.

$E_{cont}$ and $E_{curv}$ are internal energy terms. The user defines them to set the properties of the contour: stiffness or rigidity, smoothness and uniform spread of control points. $E_{img}$ is the external energy term. It uses the image information to deform the curve.

The contour has the parametric form $c(s)=(x(s),y(s))$, with $s\in[0,1]$ the arc-length parameter. An energy functional measures how good the contour is:

$$ \mathcal E=\int\big(\alpha(s)E_{cont}+\beta(s)E_{curv}+\gamma(s)E_{img}\big)\,ds $$

$\alpha,\beta,\gamma$ set the relative weight of the three terms and can change along $c(s)$. Good solutions are minima of the functional. The goal is to minimise $\mathcal E$ over the contour.

Continuity

$$ E_{cont}=\left\|\frac{dc}{ds}\right\|^2 \;\;\Rightarrow\;\; E_{cont}=\|p_i-p_{i-1}\|^2=(x_i-x_{i-1})^2+(y_i-y_{i-1})^2,\quad i=2,\dots,N $$

It uses the 1st derivative (slope of the tangent). In the discrete case, the contour is a chain of $N$ points $p_1,\dots,p_N$ and the derivative is a finite difference. Minimising it reduces the distance between consecutive points. This gives compact contours.

Smoothness

$$ E_{curv}=\left\|\frac{d^2c}{ds^2}\right\|^2 \;\;\Rightarrow\;\; E_{curv}=\|p_{i+1}-2p_i+p_{i-1}\|^2=(x_{i+1}-2x_i+x_{i-1})^2+(y_{i+1}-2y_i+y_{i-1})^2,\quad i=2,\dots,N-1 $$

It uses the 2nd derivative, a measure of curvature. It penalises high curvature (oscillation), so minimising gives a smooth curve. For three evenly spaced collinear points it is exactly 0.

Edge attraction

$$ E_{img}=-\|\nabla I\| $$

$\nabla I$ is the spatial gradient of the intensity image $I$, computed at each contour point. Large gradients (near edges) give a very small, negative $E_{img}$. Minimising it pulls the contour onto edges. This is an external energy.

Discrete energy functional

$$ \mathcal E=\sum_{i=1}^{N}\big(\alpha_iE_{cont}+\beta_iE_{curv}+\gamma_iE_{img}\big),\qquad \alpha_i,\beta_i,\gamma_i\ge0 $$

Typical weights: $\alpha_i=\beta_i=\gamma_i=1$, or $\alpha_i=\beta_i=1$ and $\gamma_i=1.2$.

Extra practice (greedy snake step). The neighbours $p_1=(0,0)$ and $p_3=(2,0)$ are fixed. The candidate positions for the middle point $p_2$ are $A=(1,0)$ with edge strength $\|\nabla I\|=5$ and $B=(1,1)$ with $\|\nabla I\|=20$. Use $\alpha=\beta=\gamma=1$.

A=(1,0): $E_{cont}=(1-0)^2+(0-0)^2=1$
$E_{curv}$: $p_3-2p_2+p_1=(2,0)-(2,0)+(0,0)=(0,0)$, so $0$
$E_{img}=-5$. Total $=1+0-5=-4$.

B=(1,1): $E_{cont}=1+1=2$
$p_3-2p_2+p_1=(2,0)-(2,2)+(0,0)=(0,-2)$, so $E_{curv}=4$
$E_{img}=-20$. Total $=2+4-20=-14$.

B has the lower energy, so the snake moves $p_2$ to B. The strong edge outweighs the bending penalty. If $\gamma$ is small (for example 0.1), A wins (A: $1+0-0.5=0.5$; B: $2+4-2=4$), so the contour stays straight. The weights set the balance between smoothness and edge-following.

Place the snake carefully, because snakes find a local minimum. If the seed is far from the object or near a stronger wrong edge, the snake goes to the wrong contour.

Interactive segmentation

In this paradigm, a human and an algorithm work together to isolate an object or region of interest. The loop is: user input (prompt) → algorithm/model → segmentation mask → user correction/refinement.

Objectives:

Interaction typeDescriptionPrimary use case
Click-based (points)positive (foreground) clicks inside the object, negative (background) clicks outsideprecise boundary corrections and localised mask adjustments
Bounding boxtight rectangular box around the objectquick initial region-of-interest localisation (e.g. GrabCut)
Scribbles / strokesrough brush strokes across target and backgroundirregular objects, thin structures, quick multi-class annotation
Polygons / lariatcoarse boundary outlines near the target edgefine-grained edge-guided selection (e.g. Intelligent Scissors)
Text promptsnatural-language queries (e.g. "the red cat on the left")zero-shot open-vocabulary interaction paired with visual clicks

Quick self-test

1. Points (0,2), (1,3), (2,4) with $\theta\in\{0^\circ,45^\circ,90^\circ,135^\circ\}$. Find the line using the ρ-θ Hough transform.

At $135^\circ$ ($\cos=-0.71,\ \sin=0.71$): $\rho=0+2(0.71)=1.41$; $-0.71+3(0.71)=1.41$; $-1.42+4(0.71)=1.41$. All three agree: 3 votes at $(135^\circ,1.41)$. At the other angles, the three $\rho$ values differ (for example at $0^\circ$: 0, 1, 2). Equation: $-0.71x+0.71y=1.41\Rightarrow y=x+2$.

2. State the normal equation and the least-squares solution for line fitting.

$X^TXB=X^TY$, so $B=(X^TX)^{-1}X^TY$, where $B=[m\ b]^T$, $X$ has rows $[x_i\ 1]$ and $Y=[y_1\dots y_n]^T$.

3. Fit $y=mx+b$ by least squares to (0,1), (1,3), (2,5), (3,7).

$n=4,\ \sum x=6,\ \sum y=16,\ \sum xy=0+3+10+21=34,\ \sum x^2=14$. $m=\frac{4\cdot34-6\cdot16}{4\cdot14-36}=\frac{136-96}{20}=2$. $b=\frac{16-2\cdot6}{4}=1$. So $y=2x+1$ (exact fit, $E=0$).

4. Why does least squares fail with outliers, and how do robust estimators fix it?

Squared error grows without limit. One distant point adds a huge term and pulls the line. A robust function such as $\rho(u;\sigma)=u^2/(\sigma^2+u^2)$ saturates at 1 for large residuals, so outliers do not dominate. A small $\sigma$ strongly ignores large residuals. A large $\sigma$ behaves like least squares.

5. Write the RANSAC algorithm and say which parameters you must choose.

Sample the minimal set of $s$ points. Solve the model. Score it by the inliers within the threshold $t$. Repeat for $N$ trials. Keep the model with the largest consensus set (if sets are equal, keep the smallest total residual). Optionally refit on all inliers. You must choose $s$ (minimal set), $t$ (for example $t^2=3.84\sigma^2$) and $N$ (from $p$ and $e$).

6. How many RANSAC iterations to fit a line ($s=2$) with 20% outliers at $p=0.99$? Then for a homography ($s=4$) with 50% outliers.

Line: $N>\ln0.01/\ln(1-0.8^2)=-4.605/\ln0.36=-4.605/-1.0217=4.51\Rightarrow N=5$. Homography: $N>-4.605/\ln(1-0.5^4)=-4.605/-0.0645=71.4\Rightarrow N=72$.

7. Does the number of data points affect the number of RANSAC iterations?

No. $N=f(e,s,p)$ only, from $N>\log(1-p)/\log(1-(1-e)^s)$. The number of points is not in the formula.

8. A RANSAC run with threshold 1 uses the points (0,0), (1,1), (2,2), (3,3), (4,9). The sample is (0,0),(4,9). Compute the line and the inliers.

$m=9/4=2.25$, $b=0$: $y=2.25x$. Predictions at x=0..4: 0, 2.25, 4.5, 6.75, 9. Errors: 0, 1.25, 2.5, 3.75, 0. Inliers ($\le1$): only the two sample points. The score is 2, a poor model. A sample such as (0,0),(3,3) gives $y=x$ with 4 inliers.

9. Differentiate between $E_{cont}$, $E_{curv}$ and $E_{img}$ in a snake. Which are internal and external?

$E_{cont}=\|dc/ds\|^2$ (first derivative) keeps points close and the contour compact. $E_{curv}=\|d^2c/ds^2\|^2$ (second derivative) penalises bending, giving smoothness. $E_{img}=-\|\nabla I\|$ attracts the contour to edges. $E_{cont}$ and $E_{curv}$ are internal energies; $E_{img}$ is external.

10. Compare total least squares with ordinary least squares.

Ordinary LS minimises vertical distances for $y=mx+b$ and cannot handle vertical lines. TLS minimises the squared perpendicular distances $\sum(ax_i+by_i-d)^2$ with $a^2+b^2=1$. It does not depend on orientation, so it handles vertical lines.