# Methods

## Keypoint

### ISS

• Input

• PointXYZ

• PointXYZRGBA model

• Output

• PointXYZ

• PointXYZRGBA model_keypoints

• Notes

• ISS + FPFH performs better than SIFT + FPFH

• However, the registration can slip on the plane; there is no constraint on the tangent plane

• `PointOutT p; p.getVector3fMap () = ...`

• Algorithm

• It computes an unnormalized covariance matrix centered at the query point (instead of the actual centroid/mean of all neighbors) and performs eigenvalue decomposition

• The original algorithm proposed by the author assigns weights to each point inversely related to the point density (i.e. higher weight for sparse points), but in PCL the current implementation does not account for this (all points weighted equally).

• The scatter matrix here is the second-order mixed moment about the origin (二阶混合原点矩).

### SIFT

• Input

• <typename PointT> return p.intensity;

• PointNormal return p.curvature;

• PointXYZRGB return (static_cast<float> (299*p.r + 587*p.g + 114*p.b) / 1000.0f);

• PointXYZRGBA return (static_cast<float> (299*p.r + 587*p.g + 114*p.b) / 1000.0f);

• Can be customized to use other types/fields (example)

• Output

• PointWithScale (save scale info if the `scale` field exists)

• PointXYZ (otherwise just provide the points)

• Notes

• This method does not populate the keypoints indices --> there is no getKeypointsIndices()

• Algorithm

• Similar to the 2D SIFT algorithm, it performs local minimum or maximum extraction in scale space for each octave (i.e. voxels of doublings of resolution), and performs the difference of Gaussian operation between each octave. If the local max/min meets the minimum contrast requirement, take it as a key point. (IMHO, it is kind of complicated, and not sure if it still makes sense in 3D space.)

### Harris3D

• Input

• PointXYZ

• PointXYZRGB

• Output

• PointXYZI (`intensity` field required)

• Notes

• Need to set the threshold for intensity response for better performance

• the function setThreshold();

• Algorithm

• It computes intensity response for each and every point in the input cloud, according to five different rules (Harris, Noble, Lowe, Tomasi, Curvature), and performs non-max suppression to select those salient ones (also checks if intensity > threshold). Therefore, it is necessary to set the threshold at this step for better performance.

## Feature

### Normal Estimation

• template <typename PointInT, typename PointOutT>

• Input

• PointXYZ

• PointXYZRGBNormal

• Output

• Normal

• PointNormal

• PointXYZRGBNormal

• Notes

• estimates local surface properties (surface normals and curvatures) at each 3D point.

• If PointOutT is specified as pcl::Normal, the normal is stored in the first 3 components (0-2), and the curvature is stored in component 3.

• RadiusSearch and KSearch cannot be used at the same time --> pick only one approach

• Algorithm

• The algorithm calls `computeCovarianceMatrix` function in centroid.h to compute normalized covariance matrix centered at its actual centroid/mean of all neighbors (not the query point).

• Then it performs eigenvalue decomposition on this covariance matrix and extracts the smallest eigenvalue and its eigenvector, and takes this eigenvector as the normal vector.

• The curvature is computed by abs(smallest eigenvalue / trace of covariance matrix).

• The covariance matrix is the second-order central mixed moment (二阶混合中心距).

• For a plane, the estimated normal could have two opposite directions. The algorithm in PCL takes into consideration the view point of the point cloud and flips the estimated normal if cos(viewpoint - point, estimated normal) < 0. (cf. the method used in SHOT descriptor: check which half plane contains more points)

### FPFH

• template <typename PointInT, typename PointNT, typename PointOutT = pcl::FPFHSignature33>

• Input

• PointXYZ/PointXYZRGB + PointNormal/Normal

• PointXYZRGBNormal + PointXYZRGBNormal

• Output

• FPFHSignature33

• Notes

• The radius used here has to be larger than the radius used to estimate the surface normals!

## Registration

• setMaxCorrespondenceDistance()

• Set the maximum distance threshold between two correspondent points in source <-> target.

If the distance is larger than this threshold, the points will be ignored in the alignment process.

### ICP

• template <typename PointSource, typename PointTarget, typename Scalar = float>

• The classic ICP registration algorithm using SVD (i.e. transformationEstimationSVD) is a wrap-up of the Eigen algorithm Eigen::umeyama.

### SAC-IA

• setMinSampleDistance()

• Set the minimum distances between samples.

• Select s sample points from P while making sure that their pairwise distances are greater than a user-defined minimum distance dmin. (from Rusu FPFH ICRA2009 paper)

### NDT

• This algorithm runs slow?

• There is an issue in the computation of covariance in the NDT source code. This issue has not been fixed until PCL 1.12.0. The correct computation should multiply the term `n/(n-1)` but the code was incorrectly multiplying `(n-1)/n`.

``````// pcl/filters/impl/voxel_grid_covariance.hpp

// line 329 and 330, in PCL 1.7, the wrong one
leaf.cov_ = (leaf.cov_ - 2 * (pt_sum * leaf.mean_.transpose ())) / leaf.nr_points + leaf.mean_ * leaf.mean_.transpose ();
leaf.cov_ *= (leaf.nr_points - 1.0) / leaf.nr_points;

// line 326 in PCL 1.12, the correct one
leaf.cov_ = (leaf.cov_ - pt_sum * leaf.mean_.transpose()) / (leaf.nr_points - 1.0);``````

Last updated