CODEWITHSUNDEEP
pythonopencvcomputer-vision
nmagerko
nmagerko

Reputation: 6794

Computing the 3D Transformation between Two Sets of Points

Using a Microsoft Kinect, I am collecting depth data about an object. From these data, I create a "cloud" of points (point cloud), which, when plotted, allow me to view the object that I scanned using the Kinect.

However, I would like to be able to collect multiple point clouds from different "views" and align them. More specifically, I would like to use an algorithm such as Iterative Closest Point (ICP) to do so, transforming each point in my point cloud by calculating the rotation and translation between each cloud that I collect and the previously-collected cloud.

However, while I understand the process behind ICP, I do not understand how I would implement it in 3D. Perhaps it is my lack of mathematical experience or my lack of experience with frameworks such as OpenCV, but I cannot find a solution. I would like to avoid libraries such as the Point Cloud Library which does this sort of thing for me, since I would like to do it myself.

Any and all suggestions are appreciated (if there is a solution that involves OpenCV/python that I can work on, that would be even better!)

Upvotes: 7

Views: 14807

Answers (4)

Francesco Callari
Francesco Callari

Reputation: 11785

A very good introduction to ICP, including accelerated variants, can be found in Rusinkievicz's old paper here.

Upvotes: 4

Tolga Birdal
Tolga Birdal

Reputation: 511

A new ICP algorithm is now in OpenCV contrib (surface matching module). It also benefits from the variants of various types (including Rusinkievicz and more):

http://docs.opencv.org/3.0-beta/modules/surface_matching/doc/surface_matching.html

For MATLAB implementation: http://www.mathworks.co.jp/matlabcentral/fileexchange/47152-icp-registration-using-efficient-variants-and-multi-resolution-scheme/content/icp_mod_point_plane_pyr.m

Upvotes: 2

Arash_D_B
Arash_D_B

Reputation: 511

@tdirdal:

Ok then I may not be looking at the correct code. I am talking about this package link: The code starts with constructing a transformation matrix and then loads a *.ply which contains a mesh (faces and vertices). The rest of the code depends on the mesh that has been loaded.

I have a very simple problem and I would appreciate it if you could let me know how I can solve this using the ICP method. I have the following two point clouds. P2 is a subset of P39 and I would like to find P2 in P39. Please let me know how I can use your matlab package to solve this problem.

P2:

11.2706 -5.3392 1.1903

13.6194 -4.8500 2.6222

8.8809 -3.8407 1.1903

10.7704 -2.1800 2.6222

8.5570 -1.0346 1.1903

13.1808 -2.5632 1.1903

P39:

-1.9977 -4.1434 -1.6750

-4.3982 -3.5743 -3.1069

-6.8065 -3.0071 -1.6751

-9.2169 -2.4386 -3.1070

-11.6285 -1.8696 -1.6751

-16.4505 -0.7305 -1.6751

-14.0401 -1.3001 -3.1070

-18.8577 -0.1608 -3.1070

-25.9398 -0.8647 -3.1070

-30.1972 -4.6857 -3.1069

-28.2349 -2.5200 -3.1069

-29.5843 -0.2496 -1.6751

-31.1688 -2.0974 -3.1070

-21.2580 0.4093 -1.6751

-23.6450 0.9838 -3.1070

-26.0636 1.5073 -1.6751

-28.4357 1.9258 -3.1070

Upvotes: 0

HugoRune
HugoRune

Reputation: 13799

I am currently struggling with ICP myself. Here is what I have gathered so far:

ICP consists of three steps:

  • Given two point clouds A and B, find pairs of points between A and B that probably represent the same point in space. Often this is done simply by matching each point with its closest neighbor in the other cloud, but you can use additional features such as color, texture or surface normal to improve the matching. Optionally you can then discard the worst matches.
  • Given this list of correspondence pairs, find the optimal transformation from A to B
  • Apply this transformation to all points in A
  • repeat these three steps until you converge on an acceptable solution.

Step one is easy, although there are lots of ways to optimize its speed, since this is the major performance bottleneck of ICP; and to improve the accuracy, since this is the main source of errors. OpenCV can help you there with the FLANN library.

I assume your troubles are with step two, finding the best transformation given a list of correspondences.

One common approach works with Singular Value Decomposition (SVD). Here is a rough sketch of the algorithm. Searching for ICP & SVD will give a lot of further references.

  • Take the list of corresponding points A1..An and B1..Bn from step 1
  • calculate the centroid Ca of all points in A and the centroid Cb of all points in B
  • Calculate the 3x3 covariance matrix M
    M = (A1 - Ca)* (B1 - Cb)T + ... + (An - Ca)* (Bn - Cb)T
  • Use SVD to calculate the 3x3 Matrices U and V for M
    (OpenCV has a function to perform SVD)
  • Calculate R = U * VT.
    This is your desired optimal rotation matrix.
  • Calculate the optimal translation as Cb - R*Ca
  • The optimal transformation is the combination of R and this translation

Please note that I have not yet implemented this algorithm myself, so I am only paraphrasing what I read.

Upvotes: 11

Related Questions