Simple registration algorithm for small sets of 2D points

Question

I am trying to find a simple algorithm to find the correspondence between two sets of 2D points (registration). One set contains the template of an object I'd like to find and the second set mostly contains points that belong to the object of interest, but it can be noisy (missing points as well as additional points that do not belong to the object). Both sets contain roughly 40 points in 2D. The second set is a homography of the first set (translation, rotation and perspective transform).

I am interested in finding an algorithm for registration in order to get the point-correspondence. I will be using this information to find the transform between the two sets (all of this in OpenCV).

Can anyone suggest an algorithm, library or small bit of code that could do the job? As I'm dealing with small sets, it does not have to be super optimized. Currently, my approach is a RANSAC-like algorithm:

1. Choose 4 random points from set 1 and from set 2.
2. Compute transform matrix H (using openCV getPerspective())
3. Warp 1st set of points using H and test how they aligned to the 2nd set of points
4. Repeat 1-3 N times and choose best transform according to some metric (e.g. sum of squares).

Any ideas? Thanks for your input.

Earing

Answer 1

With python you can use Open3D librarry, wich is very easy to install in Anaconda. To your purpose ICP should work fine, so we'll use the classical ICP, wich minimizes point-to-point distances between closest points in every iteration. Here is the code to register 2 clouds:

import numpy as np
import open3d as o3d

# Parameters:
initial_T = np.identity(4) # Initial transformation for ICP

distance = 0.1 # The threshold distance used for searching correspondences
(closest points between clouds). I'm setting it to 10 cm.

# Read your point clouds:
source = o3d.io.read_point_cloud("point_cloud_1.xyz") 
target = o3d.io.read_point_cloud("point_cloud_0.xyz")

# Define the type of registration:
type = o3d.pipelines.registration.TransformationEstimationPointToPoint(False)
# "False" means rigid transformation, scale = 1

# Define the number of iterations (I'll use 100):
iterations = o3d.pipelines.registration.ICPConvergenceCriteria(max_iteration = 100)

# Do the registration:
result = o3d.pipelines.registration.registration_icp(source, target, distance, initial_T, type, iterations)

result is a class with 4 things: the transformation T(4x4), 2 metrict (rmse and fitness) and the set of correspondences.

To acess the transformation:

I used it a lot with 3D clouds obteined from Terrestrial Laser Scanners (TLS) and from robots (Velodiny LIDAR).

With MATLAB: We'll use the point-to-point ICP again, because your data is 2D. Here is a minimum example with two point clouds random generated inside a triangle shape:

% Triangle vértices:
V1 = [-20, 0; -10, 10; 0, 0];
V2 = [-10, 0; 0, 10; 10, 0];
% Create clouds and show pair:
points = 5000
N1 = criar_nuvem_triangulo(V1,points);
N2 = criar_nuvem_triangulo(V2,points);
pcshowpair(N1,N2)

% Registrate pair N1->N2 and show:
[T,N1_tranformed,RMSE]=pcregistericp(N1,N2,'Metric','pointToPoint','MaxIterations',100);
pcshowpair(N1_tranformed,N2)

"criar_nuvem_triangulo" is a function to generate random point clouds inside a triangle:

function [cloud] = criar_nuvem_triangulo(V,N)
% Function wich creates 2D point clouds in triangle format using random
% points
% Parameters: V = Triangle vertices (3x2 Matrix)| N = Number of points
t = sqrt(rand(N, 1)); 
s = rand(N, 1);
P = (1 - t) * V(1, :) + bsxfun(@times, ((1 - s) * V(2, :) + s * V(3, :)), t);
points = [P,zeros(N,1)]; 
cloud = pointCloud(points)
end

results:

Formally

Answer 2

You may just use cv::findHomography. It is a RANSAC-based approach around cv::getPerspectiveTransform.

auto H = cv::findHomography(srcPoints, dstPoints, CV_RANSAC,3);

Where 3 is the reprojection threshold.

Bibliology

cv::findHomography requires that the two points sets (srcPoints and dstPoints here) correspond. I am interested in finding out how to find that correspondence, i.e. which points in the source point cloud correspond to which points in the destination point cloud. The RANSAC approach still needs a reasonable amount of inliers. Simply passing two uncoordinated point clouds will not work. – Earing

I thought you already had the matches but want to warp them. however, then you simply need a registration algorithm. I will try to come back later – Bibliology

@HumamHelfawi Which registration algorithm do you suggest? (In my case, I have a rotated and translated, somewhat noisy set which I wish to match with a predefined set.) – Bolick

Answer 3

One traditional approach to solve your problem is by using point-set registration method when you don't have matching pair information. Point set registration is similar to method you are talking about.You can find matlab implementation here.

Thanks

Underdone

This is indeed a possibility. Thanks. – Earing