Algorithm for weighted elliptic curve fit

Question

Background: I was trying to detect a face solely on the bases of features and the confidence of the features found. I am using a method to identify the features along with the response (confidence). Stronger features have higher responses. I was trying to identify rotations of face. So, I was thinking about using ellipse bound to identify single face from image.

Question: Is there any standard algorithm/standard library that does weighted elliptic curve fit for all the points?

(Mostly, the points would be in and around the ellipse with weights. However, there may be outliers. All points will have to be considered. The outliers will have less weight though.)

Inputs to the algorithm: coordinates of the points and the weights of the points.

Expected output from the algorithm: Minor axis, major axis, 2D orientation angle and the centre of the ellipse (using weighted curve fitting).

If there are 'n' number of features, I could calculate the centre of ellipse using the weighted average of features. But, how would I determine minor axis, major axis and the rotation of the ellipse?

Attempts: I tried with circle and it works very well. But, it does not have rotational information (it just draws a circle when face is rotated). I found literature survey about elliptical curve fits using iterative methods. I also ideated that rectangular curve fit would also do (as length of the rectangle can be major axis of ellipse and breadth of rectangle can be minor axis of ellipse).

But, I have been unable to observe any 'universal' solution. (For example, if the face is far from the camera, ellipse should be smaller accordingly. Many curve fitting algorithms use parameters which are translation variant)

Images for unweighted and weighted curve fitting:

Unweighted elliptical curve fitting would be as shown in left. It would probably just use least mean square fitting (with iterations for angles). But, this method is not desired as it would not account for the importance of features (for example, a feature of a shirt in an image would be "less important" than the one on face. Hard thresholding or binarising destroys information). Desired weighted elliptic curve fitting is as shown in right.

Answer 1

Fitting an ellipse to a set of points is sometimes known as elliptical regression. Doing a Google search on that phrase will find you many resources on the subject (e.g., 1, 2, etc.; I can't vouch for any of these).

Let's focus first on the case where you ignore outliers. Then, there are two methods. One way is to use least-squares fitting and directly compute a best fit (e.g., the method of Fitzgibbon et al). An alternative method is to use iterative methods, where you write an objective function $\Phi(p)$ that captures how well the ellipse parameters $p$ fit the data and then use gradient descent, the Gauss-Newton method, or some other method of optimization. See, e.g., the Levenberg-Marquardt algorithm.

You'll also need to decide on objective function, or equivalently, on the error model. Standard methods typically measure the "goodness of fit" by measuring the vertical error: for each point, you measure the length of the vertical line from that point to the fitted ellipse, and that is the error associated with that point; then, you sum up the squares of those errors. This is the right model if you think that your measurement of the $x$-coordinate is perfect and your measurement of the $y$-coordinate is corrupted by random errors. However, in practice that's probably often not the case; rather, we probably think that the location of the point has been shifted from the ellipse in a random direction. In that case, a better measure of "goodness of fit" would be to measure the distance from the point to the ellipse (in whatever direction makes that distance minimized; not restricting only to a vertical distance), and then take the sum of those squared distances. This does require you to use iterative methods to minimize this objective function. A similar issue arises in linear regression (see here) and it might be easier to understand in that scenario first.

OK, that should handle the case where you have no outliers. What if you do have outliers? Then there are multiple reasonable approaches. One is to use an objective function that is robust to outliers: for instance, use the median of the squared distances rather than the sum of squared distances, or use the Huber loss function instead of the square. The downside of these methods is that they make it harder to compute the gradient and thus harder to apply iterative methods (and the non-iterative methods probably can't be used at all).

An alternative way to deal with outliers is to use RANSAC, which is a general procedure for dealing with outliers. An overview is that you pick a small random sample of the points, hope that the random sample has no outliers, tentatively fit an ellipse to the sample, use the tentative ellipse to classify the points into inliers vs outliers based on how far they are from the tentative ellipse, then fit a new ellipse to all the inliers; and repeat 1000 times with 1000 different random samples, taking the best solution found. This is a generic method for dealing with outliers that has the advantage of being usable with existing non-robust methods for elliptical regression. You don't need to modify the loss function, objective function, or algorithm at all, since you are only applying elliptical regression to inliers, so you can use any method for elliptical regression without needing it to be robust to outliers.