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, don’t use k-nearest neighbor. – it’s 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
3×2 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 aren’t 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?