Метод наименьших квадратов для аппроксимации эллипсом в геометрическом смысле., Ищутся сам алгоритм и его реализация. Опции

[Pechka]

Возникла необходимость аппроксимировать полученые данные эллипсом с минизацией квадратов геометрических (не алгебраических!) рсстояний от полученых точек до эллипса. Нашёл много быстрых реализаций для алгебраических расстояний, но нужно именно геометрические минимизировать (поскольку вектора X и Y имеют равную погрешность). В качестве затравки к алгоритму можно использовать результат минимизации алгебраических расстояний так что использование метода Ньютона-Гауса (или других, чувствительных к начальному приближению) вполне пригодно. Может кто-либо встречался с какой-нибудь статьёй на эту тему? или есть готовые библиотеки для таких манипуляций?

[Pechka]

К чему такие споры? И так всем ясно, что раз уж эллипс имеет 5 параметров - значит необходимым условием является наличие как минимум 5 точек, чтобы решение было единственным, иначе по определению система уравнений будет иметь бесконечное множество решений. Что касается глобального минимума - нужно проверять, в численных методах обычно ищется как раз локальный минимум, а дальше, используется дополнительная информация чтобы доказать глобальность этого минмума.

В моей задаче имеются точки на плоскости. часть из них хорошо описываются эллипсом, а другая часть (их может быть достаточно много, но меньше 30% от полезных) - шумовая, которые могут в свою очередь образовывать контуры, а могут быть хаотично рассыпаны.

Если по теме, то нашёл 2 метода:
1. пересчитывать точки в канонический базис текущего эллипса и в нём всё решать
http://www.geometrictools.com/Documentatio...aresFitting.pdf
2. Проводить из точки кратчайшее расстояние до эллипса и минимизировать квадрат этих расстояний.
http://ieeexplore.ieee.org/xpl/login.jsp?t...number%3D813057

К сожалениею, не имею полного доступа к материалам ссылки 2. Если у кого-нибудь есть - поделитесь плз. полным pdf.

Задача для случая когда оси симметрии эллипса параллельны осям или расположены произвольно?
Аналитически решаются оба случая.

Оси произвольно расположены.
Можно ссылочку на статью или книгу с аналитическим решением такого случая?

[AndrewN]

К чему такие споры? И так всем ясно, что раз уж эллипс имеет 5 параметров - значит необходимым условием является наличие как минимум 5 точек, чтобы решение было единственным, иначе по определению система уравнений будет иметь бесконечное множество решений. Что касается глобального минимума - нужно проверять, в численных методах обычно ищется как раз локальный минимум, а дальше, используется дополнительная информация чтобы доказать глобальность этого минмума.

Я даже не буду оспаривать математическую "ценность" подобных измышлений...

Упростите для начала задачу. Представьте, что данные раньше измерялись с погрешностями sigma_1 и sigma_2 для координат x_1 и x_2, а после того, как в измерительную систему вселился гремлин, x_1 измеряется с погрешностью 0, а x_2 с погрешностью sigma_1 + sigma_2. Задайте аналитически произвольный эллипс. Внесите погрешности (исказите) в случайный набор точек на эллипсе. Найдите параметры "измеренного" эллипса по МНК, считая, что измерительная система населена гремлином.

Если полученное решение не слишком далеко от истинного (задайте метрику), то пользуйтесь упрощённой моделью.

Если решение "далеко", увеличьте количество измерений. Если и это не помогает, то пересмотрите модель - считайте честно овал ошибки.