# Line fitting - GitHub Pages

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 -

## Recently Viewed Presentations

• Virtual Instructor Led Training (Pilot) The course will be the first day of the Winter Storm Drill (Winter Storm Preparation). Format. Group Breakout (TOs, GOs) Next day hotline call. Discuss actions each company is taking. Review actions as one group....
• If nnz(A) is o(n), then need the streaming version to reduce BW asymptotically, otherwise just avoids latency. * * * "Also, data movement will cost more than flops (even on the chip). Limited amounts of memory and low memory/flop ratios...
• For example, burning 1 kg of coal releases two to three times as much energy as burning 1 kg of wood. Concentrated Energy Sources 9.1 Fossil Fuels Millions of gallons of petroleum, or crude oil, are pumped every day from...
• 42053' N: 42 degrees 53 minutes Latitude North. 78053' W: 78 degrees 53 minutes Longitude West. 2 (2) Rectangular Coordinate Systems. Also referred to as Planar, Cartesian, and Grid coordinate system. It converts Earth's curved surface onto a flat map...
• Water Chemistry B. Corrosion, C. Coagulation and flocculation Controlling corrosion: Dissolved oxygen and carbon dioxide which contribute to corrosion can be removed by de-aeration (e.g., through heating water). Chemical additives like sodium hydroxide and sodium hexametaphosphate (SHMP) may be added...
• FAT TOMâ€”Conditions for Bacteria to Grow. Acidity: pH is the measure of acidity. The pH scale ranges from 0 to 14. A value of zero is highly acidic. A value of 14 is highly alkaline. A pH of 7 is...
• Indirect-Acting Cholinomimetics Reversible Cholinesterase inhibitors. Neostigmine an ester composed of carbamic acid ([1]) and a phenol bearing a quaternary ammonium group([2]). Physostigmine A naturally occurring carbamate, is a tertiary amine. ...
• data in QEP. Reaffirmed by SACS-COC in 2010. SACS-COC Principles of Accreditation. Section I: The Principle of Integrity. ... The institution identifies college-level general education competencies and the extent to which graduates have attained them.