# Algorithm for weighted elliptic curve fit

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.

• Elliptical Hough transform? Maybe some kind of RANSAC algorithm? – Pseudonym Mar 14 '18 at 6:34
• Can you edit the question to clarify what you mean by "weighted elliptic curve fit"? I don't understand what you're trying to accomplish, so you're probably going to have to explain that in more detail. What are the inputs to the algorithm, and what is the desired output? For instance, maybe we are given a set of points and we want to find an ellipse that goes near most of those points? – D.W. Mar 14 '18 at 6:49
• Thank you for letting my question get better. In curve fitting methods (like least mean square fit), we usually take all points without considering the "importance" of points. If some points have higher weights, the curve fitting should be "inclined" towards the points with higher weights. Please see the attached images. – Akshay Rathod Mar 14 '18 at 14:58
• So my description was correct: you are given some points, and want to find an ellipse that goes near those points? I don't see that stated in the question. It would help to include that in the question, I think. Do we have to deal with outliers (a few points that are far away from the ellipse and should be mostly ignored), or will all points be near the ellipse? – D.W. Mar 14 '18 at 16:31
• @D.W. Thank you so much for making the question better. I have added this in the question: "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" – Akshay Rathod Mar 15 '18 at 3:40

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.