[Pechka 1]

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

[Xenia 36]

Возникла необходимость аппроксимировать полученые данные эллипсом с минизацией квадратов геометрических (не алгебраических!) расстояний от полученых точек до эллипса.

 

Ах как интересно! А в каком направлении вы собираетесь мерить (минимизируемые) расстояния в этой задаче? Или спрошу об этом иначе - как вы узнаете точку эллипса, которая соответствует конкретной точке данных?

 

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

 

Короче говоря, постановка задачи во многом определяется тем, как будут измеряться расстояния, которые составляют погрешность. Если эта процедура окажется слишком сложной, то у задачи может и не оказаться приемлемого решения.

 

Пока есть только такая идея - использовать статистику. Находим ценер тяжести всех экспериментальных точек. Устанавливаем в этом центре начало новых кординат, пересчитывая кородинаты всех точек в новую систему. Потом в этой системе находим собственные вектора, отвечающие положению большой и малой оси. а собстаенные значения в этой задаче будут соответствовать дисперсии по этим осям. Их-то и можно считать половинками осей эллипса. На эту тему можно почитать в интернете на тему "Факторный анализ".

[Major 0]

Что такое геометрическое расстояние (ну и алгебраическое заодно)?

В МНК минимизируют функцию правдоподобия.

Обычно правдоподобие сводят к минимизации квадрата Евклидовой нормы.

Квадрат выбирают:

1. Сильно выпуклая функция

2. Можно дифференцировать

 

Евклидова (L2) - можно дифференцировать.

Кроме того обычно именно в L2 решение существует (например в l1, l2, C и пр. его может просто не существовать для этой же задачи).

 

Норма - это длина вектора.

Метрика (расстояние между двумя точками) определяют через норму.

Все это чистая геометрия.

Дискретное представление эллипса можно представить как N_мерный вектор.

Искомое решение на этой же сетке - это другой N-мерный вектор.

Вы (с помощью МНК) минимизируете квадрат расстояния ||Zo-Zp||^2.

Что вы имеете в виду под геометрическим и алгебраическим расстоянием?

 

Про эллипс подумалось:

Если вам надо [a,b,xo,yo], то это в рамках МНК тоже вектор (размерность 4).

 

[Pechka 1]

Ах как интересно! А в каком направлении вы собираетесь мерить (минимизируемые) расстояния в этой задаче? Или спрошу об этом иначе - как вы узнаете точку эллипса, которая соответствует конкретной точке данных?

 

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

 

Я имел ввиду геометрическое расстояние в терминах аналитической геометрии, где геометрическим расстоянием от точки до кривой есть длина перпендикуляра от точки до кривой. То, что задача получается не очень простая мне и так ясно, поэтому спрашиваю о готовом её решении, а не решаю сам.

 

Что такое геометрическое расстояние (ну и алгебраическое заодно)?

В МНК минимизируют функцию правдоподобия.

Обычно правдоподобие сводят к минимизации квадрата Евклидовой нормы.

Квадрат выбирают:

1. Сильно выпуклая функция

2. Можно дифференцировать

 

Евклидова (L2) - можно дифференцировать.

Кроме того обычно именно в L2 решение существует (например в l1, l2, C и пр. его может просто не существовать для этой же задачи).

 

Норма - это длина вектора.

Метрика (расстояние между двумя точками) определяют через норму.

Все это чистая геометрия.

Дискретное представление эллипса можно представить как N_мерный вектор.

Искомое решение на этой же сетке - это другой N-мерный вектор.

Вы (с помощью МНК) минимизируете квадрат расстояния ||Zo-Zp||^2.

Что вы имеете в виду под геометрическим и алгебраическим расстоянием?

 

Про эллипс подумалось:

Если вам надо [a,b,xo,yo], то это в рамках МНК тоже вектор (размерность 4).

Спасибо за введение в аналитическую геометрию, однако это не является вопросом темы. И если уж придираться - то в МНК минимизируют квадрат некой нормы, которая может являться оптимальной либо не оптимальной в зависимости от условий задачи и выбор которой во многом определяет эффективность метода.

Что касается геометрического расстояния и алгебраического - термины взяты из зарубежной литературы на эту тему, например:

http://www.ulb.ac.be/assoc/bms/Bulletin/sup962/gander.pdf

 

Если подробнее про расстояния, то алгебраическое это когда норма, которую следует минимизировать является функцией (F(xi)-yi)^2 т.е. предполагается, что по одной из осей погрешность отсчета много меньше чем по другой. Однако, это не всегда верно. и чтобы уравнять оси в "правах" необходимо использовать целевую функцию в смысле геометрического расстояния: (xi-x0)^2+(yi-y0)^2. Для нахождения x0,y0 можно построить нормаль к эллипсу через точку xi,yi и найти её точку пересечения с кривой. Для определённости: в моих рассуждениях использую прямоугольные декартовы координаты. При первых оценках метода у меня всё свелось к уравнению 4й степени, однако, возможно, эту проблему можно обойти. Поэтому я и интересуюсь, может кто-то уже нашёл метод решения в литературе.

Заранее спасибо!

[Xenia 36]

При первых оценках метода у меня всё свелось к уравнению 4й степени, однако, возможно, эту проблему можно обойти.

 

Если вам удалось свести данную задачу к уравнению 4-й степени, то вас уже можно поздравить с решением. :) В чем вы тут видите проблему? В наше время уравнения всех степеней разрешимы и проблемы не представляют.

 

[Major 0]

Алгебраическая постановка - это линеаризованная модель для коник.

У каждой линеаризации есть область где она работает (область определения).

Авторы распространили эту область на все пространство и удивляются хреновости....

 

Потом решили сделать как я уже написал. Сделали дискретную модель эллипса (через cos(t), sin(t)).

Каждое изменение параметров искомой модели создает сове уникальное множетсво.

И после этого к этому множеству точек применяют минимизацию.

Замкнутая задача является полной и нелинейной.

Нового тут уже ничего не придумать. Все проблемы нелинейности известны. Книг море.

 

Вам надо внести априорную информацию, всю какая у вас есть, чтобы сжать область поиска.

А желательно свести эту область к компакту.

 

 

[Pechka 1]

Если вам удалось свести данную задачу к уравнению 4-й степени, то вас уже можно поздравить с решением. :) В чем вы тут видите проблему? В наше время уравнения всех степеней разрешимы и проблемы не представляют.

Только в том, что его нужно решить аналитически, затем сделать подстановку в 5 уравнений МНК(по числу неизвестных параметров) , взять соответствующие производные, а затем выразить все параметры через суммы. Если говорить проще - казалось, что задача достаточно стандартна чтобы быть решённой и не тратить на неё много времени. А ещё не ошибиться в многостраничных выкладках...

 

Статистический подход весьма распространён в такой задаче, однако требуемая точность не позволяет использовать статистические методы либо они требуют слишком много вычслительного ресурса.

 

Алгебраическая постановка - это линеаризованная модель для коник.

У каждой линеаризации есть область где она работает (область определения).

Авторы распространили эту область на все пространство и удивляются хреновости....

 

Потом решили сделать как я уже написал. Сделали дискретную модель эллипса (через cos(t), sin(t)).

Каждое изменение параметров искомой модели создает сове уникальное множетсво.

И после этого к этому множеству точек применяют минимизацию.

Замкнутая задача является полной и нелинейной.

Нового тут уже ничего не придумать. Все проблемы нелинейности известны. Книг море.

 

Вам надо внести априорную информацию, всю какая у вас есть, чтобы сжать область поиска.

А желательно свести эту область к компакту.

 

Мне казалось более правильным аналитически свести задачу к системе нелинейных уравнений и далее численными методами за несколько итераций (имея хорошую затравку) спуститься к требуемой точности.

[Major 0]

Как способ задания уравнений определяет скорость решения и точность (я не говорю про численное представление)?

Для нелинейных уравнений нельзя использовать метод Гаусса (приведение к LU виду).

 

Можно посмотреть в сторону контурного анализа. Но там при распознавании контура все равно нужна априорная информация.

Плюс в том что можно сделать фильтрацию контура, и убрать ВЧ шум.

 

Можно найти нужное конформное преобразование и перевести эллипс в линию (отрезок, область).

Дальше решить задачу для линии, и вернуться обратно.

Но преобразование будет скорее всего плохо обусловлено (но проверить надо).

Есть книга типа "конформные преобразования", она как справочник по типам отображений.

 

У коник очень много свойств на вписанные и описанные окружности, треугольники и касательные.

Можно их по изучать, возможно вы знаете о задаче больше, чем сейчас считаете.

Дома посмотрю название книги где много свойств коник.

 

 

[Tanya 4]

У коник очень много свойств на вписанные и описанные окружности, треугольники и касательные.

Перпендикуляр к касательной - биссектриса угла от точки касания к полюсам.

Легче?

[Major 0]

Акопян, Заславский "Геометрические свойства кривых второго порядка"

 

Перпендикуляр к касательной - биссектриса угла от точки касания к полюсам. Легче?

Мне все равно, поэтому и так не тяжело.

 

В статье приложенной топикстартером описан способ решения задачи в общем виде (возможны вариации на тему).

В статье не отражено как искать глобальный минимум, а это придется делать.

Я говорю о том что если что-то известно то от общей задачи можно перейти к частной или сильно снизить размер области поиска.

Возможно известно как эти точки получаются, и схема наблюдения позволяет получить доп. инфо.

 

[Pechka 1]

Как способ задания уравнений определяет скорость решения и точность (я не говорю про численное представление)?

Для нелинейных уравнений нельзя использовать метод Гаусса (приведение к LU виду).

 

Я говорил именно о численных решениях т.к. аналитических готовых я не нашёл в литературе. Система нелинейных уравнений решается методом Гаусса-Ньютона без особых проблем.

Кстати, в реальной жизни даже аналитическое решение, представленное в том или ином виде может иметь различные показатели по скорости и точности(!), поскольку, например, DSP могут иметь некоторые заложенные в них аппаратные примитивы и, опираясь на них, решение можно привести к более скоростному вычислению (тождественные преобразования, рекурсивные методы и т.д.) а ещё, в форматах чисел с плавающей запятой, может не выполняться свойство коммутативности: (a+B)+c != a+(b+c) - соответственно и точность может быть разной в зависимости от последовательности действий.

Спасибо за помощь. Буду дальше копаться, если не удастся найти - придётся самому решать.

[Alecsej 0]

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

Аналитически решаются оба случая.

[Dmitry_B 0]

Интересная задача.

Но прежде чем пытаться искать методы оптимизации, стоит осмыслить:

- случаи, когда задача не имеет решений;

- случаи, когда задача имеет более одного решения.

Нетрудно придумать простейшие примеры, которые иллюстрируют по крайней мере, последний вариант.

Что будет делать алгоритм, если решений бесконечное множество?

Очевидно, следует задачу как-то дополнительно ограничить.

[Major 0]

- случаи, когда задача не имеет решений;

- случаи, когда задача имеет более одного решения.

А какой в этом смысл?

Это оправдано тогда и только тогда, когда у вас данные без шума (шум нулевой).

Это же относится к попыткам решить задачу аналитически.

Кроме того, решая численно вы и так получите либо нулевой результат либо наиболее близкий в смысле минимизации.

 

[andrewn 0]

в форматах чисел с плавающей запятой, может не выполняться свойство коммутативности: (a+B)+c != a+(b+c)

Это ассоциативность. Не знаю, как смайлик "плавающая запятая", но смайлик "ухмылки" явно не ассоциативен...