Line fitting Jack Elton Bresenham b. 1937 IBM / Winthrop University Bresenham's Line Algorithm (1962) Line Tracing Input: (x0,y0) & (x1,y1) Output: Approximation of Coordinates on that line

Line Tracing (x,y) (x+dx,y+dy) Line Tracing - Pseudocode (x,y) drawLineP(x,y,x+dx,y+dy) // assume dx,dy>0 a=0, b=0 while a<=dx and b<=dy drawPixel(x+a,y+b) if a/dx <= b/dy

a++ else b++ Works for positive dx and dy (x+dx,y+dy) Autonomous Mobile Robots Line Extraction Split and merge Linear regression

RANSAC Hough-Transform Zrich Autonomous Systems Lab 4b 7 4b - Perception - Features Line Extraction: Motivation

Map of the ASL hallway built using line segments R. Siegwart, D. Scaramuzza, ETH Zurich - 4b 8 4b - Perception - Features Line Extraction: Motivation Map of the ASL hallway built using orthogonal planes constructed from line segments

R. Siegwart, D. Scaramuzza, ETH Zurich - 4b 9 4b - Perception - Features Line Extraction: Motivation Why laser scanner: Dense and accurate range measurements High sampling rate, high angular resolution

Good range distance and resolution. Why line segment: The simplest geometric primitive Compact, requires less storage Provides rich and accurate information Represents most office-like environment. R. Siegwart, D. Scaramuzza, ETH Zurich -

4b 10 4b - Perception - Features Line Extraction: The Problem Scan point in polar form: (i, i) Assumptions: Gaussian noise with (0, ) for ) for Negligible angular uncertainty

Line model in polar form: x cos + y sin = r - < <= r >= 0 r R. Siegwart, D. Scaramuzza, ETH Zurich - 4b 11

4b - Perception - Features Line Extraction: The Problem (2) Three main problems: How many lines ? Which points belong to which line ? This problem is called SEGMENTATION Given points that belong to a line, how to estimate the line parameters ? This problem is called LINE FITTING The Algorithms we will see: 1.

2. 3. 4. Split and merge Linear regression RANSAC Hough-Transform R. Siegwart, D. Scaramuzza, ETH Zurich - 4b 12

4b - Perception - Features Algorithm 1: Split-and-Merge (standard) The most popular algorithm which is originated from computer vision. A recursive procedure of fitting and splitting. A slightly different version, called Iterative-End-Point-Fit, simply connects the end points for line fitting. R. Siegwart, D. Scaramuzza, ETH Zurich - 4b 13

4b - Perception - Features Algorithm 1: Split-and-Merge (Iterative-End-Point-Fit) R. Siegwart, D. Scaramuzza, ETH Zurich - 4b 14 4b - Perception - Features Algorithm 1: Split-and-Merge

R. Siegwart, D. Scaramuzza, ETH Zurich - 4d 15 4d - Perception - Features Algorithm 2: Line-Regression R. Siegwart, D. Scaramuzza, ETH Zurich - 4d

16 4d - Perception - Features Algorithm 3: RANSAC Acronym of Random Sample Consensus. It is a generic and robust fitting algorithm of models in the presence of outliers (points which do not satisfy a model) RANSAC is not restricted to line extraction from laser data but it can be generally applied to any problem where the goal is to identify the inliers which satisfy a predefined mathematical model. Typical applications in robotics are: line extraction from 2D range data

(sonar or laser); plane extraction from 3D range data, and structure from motion RANSAC is an iterative method and is non-deterministic in that the probability to find a line free of outliers increases as more iterations are used Drawback: A nondeterministic method, results are different between runs. R. Siegwart, D. Scaramuzza, ETH Zurich - Algorithm 3: RANSAC R. Siegwart, D. Scaramuzza, ETH Zurich - Algorithm 3: RANSAC

Select sample of 2 points at random R. Siegwart, D. Scaramuzza, ETH Zurich - Algorithm 3: RANSAC Select sample of 2 points at random Calculate model parameters that fit the data in the sample R. Siegwart, D. Scaramuzza, ETH Zurich -

RANSAC Select sample of 2 points at random Calculate model parameters that fit the data in the sample Calculate error function for each data point R. Siegwart, D. Scaramuzza, ETH Zurich - Algorithm 3: RANSAC

Select sample of 2 points at random Calculate model parameters that fit the data in the sample Calculate error function for each data point Select data that support current hypothesis R. Siegwart, D. Scaramuzza, ETH Zurich -

Algorithm 3: RANSAC Select sample of 2 points at random Calculate model parameters that fit the data in the sample Calculate error function for each data point Select data that support current hypothesis Repeat sampling

R. Siegwart, D. Scaramuzza, ETH Zurich - Algorithm 3: RANSAC Select sample of 2 points at random Calculate model parameters that fit the data in the sample Calculate error function for each data point Select data that support current hypothesis

Repeat sampling R. Siegwart, D. Scaramuzza, ETH Zurich - Algorithm 3: RANSAC ALL-INLIER SAMPLE R. Siegwart, D. Scaramuzza, ETH Zurich - 4b 25 4b - Perception - Uncertainty

Algorithm 3: RANSAC How many iterations does RANSAC need? Because we cannot know in advance if the observed set contains the maximum number of inliers, the ideal would be to check all possible combinations of 2 points in a dataset of N points. The number of combinations is given by N(N-1)/2, which makes it computationally unfeasible if N is too large. For example, in a laser scan of 360 points we would need to check all 360*359/2= 64,620 possibilities! Do we really need to check all possibilities or can we stop RANSAC after iterations? The answer is that indeed we do not need to check all combinations but just a subset of them if we have a rough estimate of the percentage of inliers in our dataset This can be done in a probabilistic way

R. Siegwart, D. Scaramuzza, ETH Zurich - 4b 26 4b - Perception - Uncertainty Algorithm 3: RANSAC How many iterations does RANSAC need? Let w be the fraction of inliers in the data. w = number of inliers / N where N is the total number of points. w represents also the probability of selecting an inlier Let p be the probability of finding a set of points free of outliers

If we assume that the two points needed for estimating a line are selected independently, w2 is the probability that both points are inliers and 1-w2 is the probability that at least one of these two points is an outlier Now, let k be the number of RANSAC iterations executed so far, then (1-w2) k will be the probability that RANSAC never selects two points that are both inliers. This probability must be equal to (1-p). Accordingly, 1-p = (1-w2) k and therefore log(1 p) k log(1 w 2 ) R. Siegwart, D. Scaramuzza, ETH Zurich -

4b 27 4b - Perception - Uncertainty Algorithm 3: RANSAC How many iterations does RANSAC need? The number of iterations k is log(1 p) k log(1 w2 ) This expression tells us that knowing the fraction of inliers w, after k RANSAC

iterations we will have a probability p of finding a set of points free of outliers. For example, if we want a probability of success equal to p=99% and the we know that the percentage of inliers in the dataset is w=50%, then we get k=16 iterations, which is much less than the number of all possible combinations that we had to check in the previous example! Also observe that in practice we do not need a precise knowledge of the fraction of inliers but just a rough estimate. More advanced implementations of RANSAC estimate the fraction of inliers by changing it adaptively iteration after iteration. R. Siegwart, D. Scaramuzza, ETH Zurich -