Constraining a least squares minimization to fit a single root? - MathOverflow

Constraining a least squares minimization to fit a single root?

2010-03-10T22:35:10Z

I have an algorithm that segments depth images using surface fitting. At the moment the algothim uses least squares polymonial fitting, but polynomials are not powerful enough to fit the shapes that are in these images. I replaced the explicit polynomial $z = f(x,y)$, with the implicit fitting problem $f(x,y,z) = 0$. Where $x$ and $y$ are the pixels location and $z$ is the value of the pixel and $f$ is a polynomial. A classic problem with many nice linear solutions. This did make the fitting much more powerful, but this left me with a problem I have been unable to solve for a while now. Once I had the least squares solution to the implicit poly, I had to solve for z, not easy at all, but I could search for the minimum (there are only 256 possible pixel values to search through after all). THE problem is that there was more than one solution for z! Where a pixel can only have one value. That is, once the implicit poly was solved for z there were several roots.

So my question is;

How do I formulate a least squares minimization problem for a single root? What contraints must I add?

This might not be completely clear so here is an example: You have a set of noisy data points ${x,y}$ that form a semi-circle about the origin in the positive y only. I want to fit $f(x,y) = 0$ to the data points, or to be pricise, a circle. $f == x^2 + y^2 + c = 0$.

The least squares minimization problem is a nice simple linear $\min_c \sum_{i=0}^n (x_i^2 + y_i^2 + c)^2$ but I am only interested minimizing the datapoints distance to the positive half of the circle. Solving for $y$ and taking the positive root gives us $y_i = \sqrt{-c-x_i^2}$. Giving us the acutal minimization problem as $\min_c \sum_{i=0}^n (y_i - \sqrt{-c-x_i^2})^2$ NOT a nice linear problem at all. These two minimisation problems will give differnt results since the negative half of the circle should not try to fit itself to any data points. How can i constrain the linear problem so that it is an equivelent to minimizing to a single root?

Or in general constrin $\min_{ijk} (\sum_{i,j,k}a_{ijk}x^iy^jz^k)^2$ to a minimization to a single root in $z$?

I hope this makes sence and sorry for the length but this has been annoying me for weeks.

Answer by fedja for Constraining a least squares minimization to fit a single root?

2010-03-11T05:23:58Z

Asuming that your surfaces are not too wild, it seems logical to try to combine the implicit approximation with the explicit one, i.e., to solve 2 least square problems simultaneously: one for the implicit function and one for the explicit one. The explicit solution will give you a crude approximation for the root and then you just choose the root of the implicit function that is closest to this crude approximation as the "true" position of your pixel. It certainly works with your half-circle example but whether it'll work in your real case depends on the actual surfaces you are dealing with.

If you could give us some idea of what they look like, what precision you are getting with the explicit approximation, what precision you are getting with the implicit one, and how close the "parasitic" roots can come to the "true" ones, we might be able to say more.

OK, let's try one more idea. Minimize the sum of $f(x,y,z)^2+A(\partial_z f(x,y,z)-1)^2$ with some positive $A$ (you'll have to play with its choice to see what works best). The advantage is two-fold: first, now you have the true root separated (the $z$ derivative is not small) and second, you have two approximate equations for it ($f=0$ and $\partial_z f=1$), which should give you extra advantage, the hope being that the parasitic roots of $f$ won't be able to match the derivative too. Also, keep the power in $z$ well below that in $x$ and $y$. Note that you are still better off than with $z-f(x,y)$ because this explicit formula satisfies all the extra conditions we are trying to impose automatically.

And yes, it'll help to see the data, though, if possible, I'd prefer the one-dimensional case (the $x$ slice of your real data should have all the same problems already). Just post something reasonable (like $S(1),\dots, S(50)$) that we want to approximate by $f(x,z)=0$ with $f$ of some reasonable degree with which you currently have a problem. I'll try to play with it a bit when I have free time.

Answer by David Bar Moshe for Constraining a least squares minimization to fit a single root?

2010-03-11T14:30:11Z

I think that it is better to use rational approximation for the fitting z = P(x,y)/Q(x,y), where P and Q are polynomials. This type of fitting is more flexible in general than polynomial fitting and doesn't have the multiple solution problem. There are many algorithms to establish this type of fitting, one possibility is the Nelder-Mead simplex algorithm.

Answer by Tategami for Constraining a least squares minimization to fit a single root?

2010-03-13T16:25:03Z

I finally have an example ready...

So we have an image of a sphere, and we take data points on it.

Since this is a sphere it is reasonable to assume that we can fit a sphere to this part of the image. Here are the reults:

Blue is low error, we can see that most points fit well, the other are the `parasitic' roots, interpolations look as follows:

The correct root fits the image well, the other root is just getting in the way (at the moment) but here is the fitted function:

Now this is a nice result since the 'edge' of the fitted sphere corresponds to the edge of the sphere in the image. Something I imagine the suggested rational fitting can't do any why I WANT several roots in the solution, but I only want to fit one to the data!!

So whats the problem, well, this is a nice result but a 3rd order polynomial might fit it better (the data is technically not a simple sphere), or i might have other data that would need even higher order fitting (toruses for exmaple are 4th order). So I fit a 3rd order poly and here is the resulting function:

Not nice, the roots are all over each other, fighting against each other to fit the data.

Now I want the re-iterate my question. One can always solve for z and fit a single root to the data using non-linear regression, but my feeling is that we should be able to do the same using constrained linear fitting. And HOW is my question! Here is an example that constraining the fit does at least help. Here the $z$ and $z^2$ parameters are fixed to $1$: Fitting the same 3rd order poly to the same data:

A much friendlier 3rd order poly, but this restriction is too much it turns out, and i have lost the nice results.

So the question in terms of my original example:

How can I linearise the following minimization problem without reintroducing multiple roots?

$\min_c \sum_{i=0}^n (y_i - \sqrt{-c-x_i^2})^2$

and then we can see if this can be done in general to all implicit polys....

Thanks.