CODEWITHSUNDEEP
algorithmgeometrymathematical-optimizationrigid-bodies
zorgkang
zorgkang

Reputation: 55

geometric median for rigid body

I need to implement a "geometric median"-type algorithm that would apply to rigid bodies, meaning it would not only find a point minimizing the distance from a set of points, but would also take into account the orientation of the body. I haven't found a solution for this type of problem anywhere, while for the geometric median (or Weber or Fermat-Torricelli problem, or facilities location problem), there is a lot of information available, including the Weiszfeld algorithm (and modern improvements). I'm hoping someone will have references to possible solutions. I would have thought this to be a relatively common problem in registration, but maybe I just haven't found the right words to search for...

My problem could be formulated as follows: Say I have a "reference" rigid body with 3 non-colinear points (a triangle), and I measure the coordinates of the 3 points a bunch of times (with some error, or the object was moving a bit). I want to find a good "central location", that would minimize the sum of distances (not square distances) between each measured point and its corresponding centrally-located-object point. This is equivalent to the "multi-facility location problem" but with extra contstraints of fixed distances between the "facilities" and with each point pre-assigned to a facility (not necessarily the closest one).

Actually, I'm thinking instead of minimizing the sum for all the points, I'd only keep the max distance out of the 3 points for each measurement. (is that what's called "minimax"?) But I don't think that would make a big difference in the type of algorithm I'd have to use.

A possible difficulty compared to the geometric median could be that with the added freedom of rotations, the quantity to minimize is no longer convex (not 100% sure, but I think). I'm hoping I can still use a similar algorithm as Weiszfeld's (which is a subgradient method), and hopefully this has been investigated previously. Thanks for any help!

P.S. I'll be doing this in Matlab.

Upvotes: 0

Views: 423

Answers (2)

isarandi
isarandi

Reputation: 3349

You could do Weiszfeld-like iterative updates on the transformation matrices. Average the 4x4 rigid transformation matrices, project the rotation part (3x3) to SO(3) as done eg. in the Kabsch algorithm, then compute the squared deviation of each transformation from the mean, weight them by the reciprocal squared deviation and perform a weighted averaging with these weights, recompute the deviations etc, like Weiszfeld.

This would work purely with the transformations, disregarding the distribution of the points of the object.

Upvotes: 0

Eugene Smith
Eugene Smith

Reputation: 9398

I can't find any research on this subject. The first thing I would do is to use Weiszfeld's algorithm without rigidity constraints to find geometric medians of individual points, define lagrange multipliers corresponding to deviations of edges of the object from expected values, and use gradient descent to find a constrained local minimum. I can't prove that it will always work, but, intuitively, it should as long as deviations are sufficiently small.

Upvotes: 0

Related Questions