Approximating and visualizing basins of attraction

Question

I am working on estimating the position and orientation (pose) of a model (rigid object) from its silhouette in an image. For this, I have constructed an error measure between the model in its pose and the silhouette, which looks roughly like:

$$ \epsilon ( \bar{x} ) = \sum_{\forall i} \| f(\bar{x}, m_i) - s_i \|^2 $$

where $\bar{x}$ is a six-dimensional vector describing the 3D translation and rotations as

$$ f( \bar{x}, p ) = R_{\bar{x}} \cdot p + t_{\bar{x}} $$

Ordinarily, this could be nonlinear least squares, however there is a catch: An assignment needs to be made between model-points $m_i$ and silhouette points $c_i$, which complicates the evaluation of the error measure.

I am approaching the problem as a general nonlinear optimization problem. I already know that this error measure is continous, but not continously differentiable due to the aforementioned assignment. I do have gradient information however, but this does not take the assignment into account and therefore is not completely accurate.

The question: Is there a method which can calculate/approximate and visualize the basins of attractions in this six-dimensional space?

If this is absolutely not feasible, is there a method which can calculate/approximate the number of local minima within a "bounded" region?

Answer 1

Visualizing 6 dimensional domains is simply not easy. Unless of course, your uber-dimensional monitor is back form the repairman. Getting parts from the future is never a quick thing to do however, so mine languishes in a back room with my busted Holodeck.

Kidding aside, visualizing a basin in 6-d really is not easy. Even computing the limits of a basin of attraction will be difficult. The curse of dimensionality hounds you.

Ok, even in a lower number of dimensions, identifying the boundaries of such a basin requires solving MANY optimization problems. After all, a basin of attraction need not be a convex set. It need not be connected. And, since an optimizer, starting from distinct starting values will yield results that are still distinct, you must now do some clustering, testing that the multiple solutions truly are the same.

There are other issues of course. Suppose I ask to minimize the function (x-y)^2 in the (x,y) plane? Clearly any point on the line y=x is a solution, and all are equally good. But clustering will have problems here, as they will on any such degeneracies, and identifying degeneracies in 6-d is not always trivial.

Finally, you ask about identifying the NUMBER of local minimizers in any bounded region. The is too is quite difficult for a general black box problem. The field of global optimization has been working on problems like this for many years, though I don't think they can give you any hard, easy to compute answers in general.

Answer 2

You could use a nonsmooth solver such as solvopt or ralg, run it with many random starting values and limited number of function evaluations, and make a cluster of the resulting approximate solutions.

This will give you an idea of the basins of attraction. Since randomness is involved, there are no guarantees, but I do not think that rigorous methods (branch and bound) would be efficient in your context.