# 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, 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?