Find points on a line

Question

I have a camera that searches for an edge. It returns a list of $10$ points along the detected edge.

The result is ideally a list of $10$ points all on the same line. In reality it happens that some edges are misdetected by a lot. It is difficult to say how many are misdetected. It could be $1$ or $5$.

I need to find the most probable line that represents the edge, that goes through as many points as possible, but excludes the points that deviate a lot.

How can this be done mathematically?

This is a sample of how the points could be scattered:

EDIT:

I have a list of real points now: (The ones marked with an arrow are those that contain a outlier in the X values and need to be removed.)

  X  /  Y
-----------
570,5/693,5 <---
585,5/683,5
591,5/673,5
586,5/663,5 <---
631,5/653,5 <---
611,5/633,5
617,5/623,5
622,5/613,5
622,5/603,5 <---

Answer 1

It sounds like you are looking for a regression line with a systematic way to identify highly influential points (outliers and high leverage points).

In R this would work a follows:

x <- c(570, 585, 591, 586, 631, 611, 617, 622, 622)
y <- c(693, 683, 673, 663, 653, 633, 623, 613, 603)
plot(x,y, pch=19)
mod <- lm(y ~ x)
abline(mod, col = 'firebrick')
summary(mod)
plot(mod)

Call:
lm(formula = y ~ x)

Residuals:
    Min      1Q  Median      3Q     Max 
-22.825  -9.100  -6.631   8.268  38.471 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 1406.4879   191.8358   7.332 0.000158 ***
x             -1.2551     0.3175  -3.953 0.005510 ** 
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 19.06 on 7 degrees of freedom
Multiple R-squared:  0.6906,    Adjusted R-squared:  0.6464 
F-statistic: 15.63 on 1 and 7 DF,  p-value: 0.00551

Can you see the high-leverage points? Like point $5,$ corresponding to (631, 653)? I marked it in red on the first plot - it is out of sync with the response $y$ in the rest of the data (outlier), and being positioned towards the end, it is pulling on the fitted line relatively more than the others (high leverage).

The second diagnostic plot (standardized residuals), tests the model for heteroskadisticity. The points should be distributed randomly above and below the line. Their individual influence is detected by calculating the ratio of the model residuals to the product of the standard deviation times the square root of 1 - "hat values" (measurement of leverage / values along the diagonal of the projection matrix). You can see that point $5$ is clearly above the others. Similarly Cook's distance identifies the same point as highly influential.

If we remove it from the dataset, we end up with a better fit (notice, for instance the change in R-squared from $69$ percent to $95$ percent.

new.x <- x[-5]
new.y <- y[-5]
plot(new.x,new.y, pch=19)
mod2 <- lm(new.y ~ new.x)
abline(mod2, col = 'firebrick')
summary(mod2)
par(mfrow=c(2,2))
plot(mod2)
Call:
lm(formula = new.y ~ new.x)

Residuals:
   Min     1Q Median     3Q    Max 
-9.323 -6.856  1.839  4.258  9.064 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 1655.3182    91.0720   18.18 1.79e-06 ***
new.x         -1.6775     0.1516  -11.07 3.24e-05 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 7.99 on 6 degrees of freedom
Multiple R-squared:  0.9533,    Adjusted R-squared:  0.9455 
F-statistic: 122.5 on 1 and 6 DF,  p-value: 3.242e-05

Notice how the regression line (below) is reflecting a better fit (minimizing residuals) as it is no longer leveraged by that pesky point $5,$ which was an outlier, as well as a point of high leverage on the fitted line. Now it travels under three of the last four points, whereas it ran above them previously.