Minimizing Maximum Distance between 3D Point Cloud Data

I have what I'll call a "nominal point cloud" and then a "measured point cloud". My goal is that I want to minimize the maximum distance between respective points of EVERY point in the point cloud without moving points in the nominal cloud. I do not want a least-squares type fit that could sacrifice a couple points for the good of the rest of the cloud.

EDIT: Each point cloud contains the exact same amount of points and when transforming the measured point cloud, I need to move every point in relation to one another. i.e. If you move one point in a direction, every point moves in the same direction with the same magnitude.

I believe I could write a brute-force, majorly iterative, code for this process but the way I have in mind would take absolutely forever to run and that's not feasible. Looking for any advice available.

Thank you.

[José-Luis]

I don't get it. Do you have the same number of points in both clouds? Can you move either cloud? If you can move one of them, does the transform have to be affine?

[Nicholas]

Yes. Same exact number of points in each point cloud. I only want to move the measured point cloud and they have to move in relation to one another. I need to add that in there for those are very specific attributes. Please let me ammend.

[José-Luis]

Does each point move independently?

[Nicholas]

No. The points must maintain relationship with one another during the transformation. Think of the cloud as a rigid body and when moving one piece of the cloud, the rest of the cloud moves in the exact same fashion and in the same direction/magnitude.

[José-Luis]

So that means an affine transform? Translation and rotation but no shear.

[José-Luis]

Also, if the distance is pairwise (the distance between one point in one cloud to one point in another cloud, not the minimum distance between a point in one cloud and all the points in other clouds) then your problem reduces to optimizing a system of 6 unknowns:

 rotation (x, y and z)
 translation (x, y and z)

So you need to find the six values that will minimize the distance between a pairs of points. That sounds like a job for fminsearch() and similar functions.

[Nicholas]

Yes, sorry, an affine transform - like you said. Yes, the distance will be pair wise. To think of an example: I have a very thin, curved piece of metal, with holes in it. Each hole center point represents the points in my point cloud. Based off the CAD drawing, I know my center points should be at their nominal locations. However, when I fabricate the part, based on the tolerances, the holes will be in different locations when I measure the part, thus the measured point cloud. End result is I want to find a way to get the measured hole center locations to get as close to their respective nominal center locations as possible, for every hole center.

I'll look into fminsearch() like you suggested. Thank you for taking the time to consider the issue.

Answer 1

[Matt J]

My goal is that I want to minimize the maximum distance between respective points of EVERY point in the point cloud without moving points in the nominal cloud. I do not want a least-squares type fit that could sacrifice a couple points for the good of the rest of the cloud.

Well, the least squares method that you say you don't want is implemented here

http://www.mathworks.com/matlabcentral/fileexchange/26186-absolute-orientation-horn-s-method

I would do this to at least initialize a search using fminsearch, or better yet, fminimax if you have the Optimization Toolbox. This file may help to parameterize the rototranslation

http://www.mathworks.com/matlabcentral/fileexchange/30864-3d-rotation-about-shifted-axis

   reg= absor(nominal,measured);
   p0=[reg.q(2:3);0;reg.t];

   options = optimoptions('fminimax','MinAbsMax',size(nominal,2)); 
   p = fminimax(@(p) objective(p,nominal,measured),[],[],[],[],[],...
                               [],[],options);

   function F=objective(params,nominal,measured)

     x1=params(1);
     x2=params(2);
     x3=sqrt(1-x1^2-x2^2);

     theta=params(3);

     translation=params(4:6);

     Tnominal=AxelRot(nominal,theta,[x1,x2,x3],translation);

     F=Tnominal-measured;

[Nicholas]

I'm waiting on getting the Optimization Tool Box license. I will let you know ASAP if this solution worked. Thank you for taking the time to consider my issue and offer up an answer.

I do not want to use Least Squares method because of the possibility of it sacrificing x amount of points for the benefit of the cloud's average delta from nominal.

[Matt J]

I do not want to use Least Squares method because of the possibility of it sacrificing x amount of points for the benefit of the cloud's average delta from nominal.

You may have missed my point. I proposed to use least squares for initialization. You definitely want to do that.

[Nicholas]

Ah, I understand the flow of your answer better now. Thanks. I've read through both those functions and their uses and I believe they may help solve this problem. Again, awaiting licensure from my company to allow me to delve into the offered solution.

When the time comes, do you respond to e-mails? I may find it more beneficial to speak with you through that medium.

Regards.

[Matt J]

No, I don't do emails, I'm afraid. For one thing, it defeats the purpose of this forum if people move the discussion to private email exchange. The idea is to see the question resolved here so that not only you benefit as the OP, but also other people who might encounter the same problem, as well.