[SOLVED] CS algorithm CS 4610/5335 Point-cloud perception

CS 4610/5335 Point-cloud perception
Robert Platt Northeastern University
Material adapted from:
1. Lawson Wong, CS 4610/5335
2. Peter Corke, Robotics, Vision and Control

Depth sensors
Creating point clouds / maps
Voxelizing, calculating surface normals, denoising
ICP
RANSAC
Hough transform
Topics

Fake perception
https://april.eecs.umich.edu/software/apriltag
Incredibly useful and reliable!

3-D vs. 2-D perception
Main object: point clouds
Point clouds contain more information: 3-D shape perception is critical Point clouds have little information: points are sparse, volume is inferred Instance detection is the main objective
We want SE3 poses, not just bounding boxes

Laser range scanners
Hokuyo UTM-30LX-EW Scanning Laser Range Finder

Laser range scanners
Scan geometry
2D map created using laser range scanner

Laser range scanners
Slide from Course INF 555 slides, Ecole Polytechnique, Paris

Laser range scanners

Structured light sensors

Slide: John MacCormick, Dickinson University

Kinect uses speckled light pattern in IR spectrum

Slide: John MacCormick, Dickinson University

Slide: John MacCormick, Dickinson University

Slide: John MacCormick, Dickinson University

Slide: John MacCormick, Dickinson University

Point cloud created using a depth sensor Depth image Point cloud
RGB image

Calculating surface normals
Point cloud Point cloud w/ surface normals (normals are subsampled)

Calculating surface normals
Question: How do we calculate the surface normal given only points?
Answer:
1. Calculate the sample covariance matrix of the points within a local neighborhood of the surface normal
2. Take Eigenvalues/Eigenvectors of that covariance matrix

Calculating surface normals
Let C denote the set of points in the point cloud Suppose we want to calculate the surface normal at
Let denote the r-ball about x
is the set of points in the cloud within r of x

Calculating surface normals
Calculate the sample covariance matrix of the points in

Calculating surface normals
Length =
Eigenvalues of
Length =
Principle axes of ellipse point in directions of corresponding eigenvectors

Calculating surface normals
So: surface normal is in the direction of the Eigenvector corresponding to the smallest Eigenvalue of
There should be two large eigenvalues and one small eigenvalue.

Calculating surface normals: Summary
1. calculate points within r-ball about x:
2. calculate covariance matrix:
3. calculate Eigenvectors:
and Eigenvalues: (lambda_3 is smallest)
4. v_3 is parallel or antiparallel to surface normal

Question
What if there are two small eigenvalues and one large eigenvalue?

Calculating surface normals
Important note: the points alone do not tell us the sign of the surface normal

Calculating surface normals
Important note: the points alone do not tell us the sign of the surface normal

Question
Important note: the points alone do not tell us the sign of the surface normal
Any ideas about how we might estimate sign given a set of points generated by one or more depth sensors?

Calculating surface normals
How large a point neighborhood to use when calculating ?
Because points can be uneven, dont use k-nearest neighbor. its important to select a radius r and stick w/ it.
which what value of r to use?

Calculating surface normals
Images from Course INF 555 slides, Ecole Polytechnique, Paris

Calculating surface normals
Images from Course INF 555 slides, Ecole Polytechnique, Paris

Outlier removal
Similar approach as in normal estimation: 1. calculate local covariance matrix
2. estimate Eigenvectors/Eigenvalues
3. use that information somehow Images from Course INF 555 slides, Ecole Polytechnique, Paris

Outlier removal
If points lie on a plane or line, then small
is
If points are uniformly random, then
is close to 1
Outlier removal: delete all points for which
Images from Course INF 555 slides, Ecole Polytechnique, Paris
is above a threshold

Point cloud registration: ICP
Find an affine transformation that aligns two partially overlapping point clouds
Images from Course INF 555 slides, Ecole Polytechnique, Paris

ICP Problem Statement
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

ICP: key idea
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Step 1: center the two point clouds
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Step 2: use SVD to get min t and R
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Step 2: use SVD to get min t and R
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

ICP data association problem
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

ICP Algorithm
Input: two point sets, X and P
Output: translation t and rotation R that best aligns pt sets
1. 2. 3. 4. 5. 6.
Start with a good alignment Repeat until t and R are small:
for every point in X, find its closest neighbor in P find min t and R for that correspondence assignment translate and rotate P by t and R
Figure out net translation and rotation, t and R
Converges if the point sets are initially well aligned Besl and McKay, 1992

ICP example
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Question
Where does ICP converge for this initial configuration?

Question
How does ICP align these two point sets?

ICP Variants
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Selecting points to align
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Normal-space sampling
Idea:
estimate surface normals of all points
bucket points in surface normal space (i.e. discretize in normal space) select buckets uniformly randomly. Then select a point uniformly
randomly from within the bucket.
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Comparison: normal space sampling vs random
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Comparison: normal space sampling vs random

Feature based sampling
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

ICP: data association
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

ICP: data association
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Closest point matching
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Normal shooting
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Closest compatible point
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Question
How might one use feature based sampling to improve data association?

Data association comparison: fractal scene
Normal shooting Closest point

Data association comparison: incised plane
Normal shooting Closest point

Point-to-plane distances
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

ICP: summary
This slide from: Burgard, Stachniss, Bennewitz, Arras, U. Freiburg

Another approach to alignment: RANSAC
This slide from: Kavita Bala, Cornell U.

RANSAC
This slide from: Kavita Bala, Cornell U.

How does regression work here?

RANSAC key idea
This slide from: Kavita Bala, Cornell U.

Counting inliers
This slide from: Kavita Bala, Cornell U.

Counting inliers
This slide from: Kavita Bala, Cornell U.

How do we find the best line?
This slide from: Kavita Bala, Cornell U.

RANSAC
This slide from: Kavita Bala, Cornell U.

This slide from: Kavita Bala, Cornell U.

This slide from: Kavita Bala, Cornell U.

This slide from: Kavita Bala, Cornell U.

Question
How would you use this approach to fit a plane in 3 dimensions?

Question
Suppose we want to find the best fit line in the plane (as above)
m: number of points on line
n: total number of points in the plane
What is the expected number of samples required to find the line using the procedure outlined above?
What is the prob of NOT finding the line after k iterations?

Using RANSAC to Fit a Sphere

Using RANSAC to Fit a Sphere

Using RANSAC to Fit a Sphere Radius?
Center?

Using RANSAC to Fit a Sphere
How generate candidate spheres? How score spheres?

Using RANSAC to Fit a Sphere
How generate candidate spheres? How score spheres? 1. sample a point

Using RANSAC to Fit a Sphere
How generate candidate spheres? How score spheres? 1. sample a point
2. estimate surface normal

Using RANSAC to Fit a Sphere
radius
How generate candidate spheres? 1. sample a point
2. estimate surface normal
3. sample radius
How score spheres?

Using RANSAC to Fit a Sphere
radius
How generate candidate spheres?
1. sample a point
2. estimate surface normal
3. sample radius
How score spheres?
4. estimate center to be radius distance from sampled point along surface normal

Using RANSAC to Fit a Sphere
radius
How generate candidate spheres?
1. sample a point
2. estimate surface normal
3. sample radius
How score spheres?
1. count num pts within epsilon of
candidate sphere surface
4. estimate center to be radius distance from sampled point along surface normal

Using RANSAC to Fit a square
Think of strategies for using RANSAC-like technologies for fitting a square in the plane
square of known side length and orientation?
square of known side length and unknown orientation?
square of unknown side length and orientation?
arbitrary rectangle?
What assumptions are you making with your sample strategies?

Using RANSAC to Fit a Cylinder
How generate candidate cylinders?

Using RANSAC to Fit a Cylinder
How generate candidate cylinders? 1. sample two pts

Using RANSAC to Fit a Cylinder
How generate candidate cylinders?
1. sample two pts
2. estimate surface normal at both pts

Using RANSAC to Fit a Cylinder
How generate candidate cylinders?
1. sample two pts
2. estimate surface normal at both pts
3. get sample axis by taking cross product between two normals

Using RANSAC to Fit a Cylinder
How generate candidate cylinders?
1. sample two pts
2. estimate surface normal at both pts
3. get sample axis by taking cross product between two normals
4. project points onto plane orthogonal to axis 5. fit a circle using a method similar to what we did for the sphere.
6. project center of circle back into 3d space

Using RANSAC to Fit a Cylinder
3xn matrix of pts projected onto plane
32 basis for plane. (two column vectors side by side)
3xn matrix of pts in 3d space
How generate candidate cylinders?
1. sample two pts
2. estimate surface normal at both pts
3. get sample axis by taking cross product between two normals
4. project points onto plane orthogonal to axis 5. fit a circle using a method similar to what we did for the sphere.
6. project center of circle back into 3d space

RANSAC: the parameters
This slide from: Kavita Bala, Cornell U.

RANSAC: how many parameters to sample?
This slide from: Kavita Bala, Cornell U.

RANSAC Summary
This slide from: Kavita Bala, Cornell U.

Hough transform
This slide from: Kavita Bala, Cornell U.

Hough transform
This slide from: Kavita Bala, Cornell U.

Hough transform
This slide from: Kavita Bala, Cornell U.

Hough transform
This slide from: Kavita Bala, Cornell U.

Hough transform

Hough transform
This slide from: Kavita Bala, Cornell U.

Hough transform
Why arent there eight intersections instead of seven? This slide from: Kavita Bala, Cornell U.

Hough transform for circles
What is the parameter space for the circle Hough transform? What about 2-D ellipses?