2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Аппроксимация эллипса
Сообщение17.11.2010, 20:35 
Имеется метод аппроксимации эллипса (описание на английском):
http://research.microsoft.com/en-us/um/ ... e-pami.pdf
Может кто-либо реализовывал его? Кто знаком, разъясните пожалуйста суть метода?
На английском мало-что понятно.

 
 
 
 Re: Аппроксимация эллипса
Сообщение17.11.2010, 23:10 
Аватара пользователя
h_dima в сообщении #376671 писал(а):
аппроксимации эллипса

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

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 14:00 
Я пока смог только по диагонали глянуть статью (тоже не люблю по-иностранному читать). На первый взгляд --- задачка "второго уровня" сложности. К "первому уровню" я отношу типовой чисто линейный МНК (без всяких там ограничений на коэффициенты).

Но расскажите для начала --- суть метода наименьших квадратов (вообще, безотносительно к эллипсу) Вам известна?

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 15:12 
Известна. В этой статье используется тот же критерий, как и в мнк - минимальная сумма квадратов отклонений. Так?

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 16:42 
А если не секрет, почему по-иностранному читать не любите?

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 17:26 

(Gortaur)

Не знаю... Нетренированность, наверное. Читаю, и в уме перевожу. Медленно получается.
Хотя с Сидни Шелдоном было как-то по-другому, проще. Не люблю я эту дурацкую матиматику. :D

h_dima в сообщении #376958 писал(а):
В этой статье используется тот же критерий, как и в мнк - минимальная сумма квадратов отклонений. Так?
Примерно. Только не следует думать, что эти отклонения соответствуют геометрическим расстояниям от точек до эллипса. Там где-то было употреблено слово "алгебраических" отклонений, что подчёркивает их негеометричность. Это "отклонения от нуля" значений функции-уравнения эллипса $F(x,y)=0$, где $F(x,y)\equiv ax^2+bxy+\ldots$.

Теперь представим для простоты, что мы так же хотим построить прямую $Ax+By+C=0$ (не традиционное $y=kx+b$, а именно так). Пробуем минимизировать $\sum (Ax_i+By_i+C)^2$, получаем очевидный минимум-ерунду $A=B=C=0$.
Но мы можем заранее положить, например, $A=1$. И легко-линейно найти решение (правда, для горизонтальной прямой не сработает).
Мы можем заранее положить $B=1$. И легко-линейно найти другое решение (правда, для вертикальной прямой не сработает).
Когда мы берём естественное условие $A^2+B^2=1$ (по природе --- тригонометриическое), мы находим любую прямую, и более того, "алгебраический" минимум совпадает с "геометрическим". Но лёгкость-линейность у нас пропадает.

Вот и с эллипсом, чтобы не получить $a=b=c=d=e=f=g=\ldots=0$, мы должны придумать разумный constraint на коэффициенты. Что ребята и пытаются сделать. Обсуждают другие варианты, ихний, естественно, самый лучший, да ещё и эллипсность обеспечивает. И как бы решение чем-то там облегчает. Мне по первому взгляду всё это весьма подозрительно.

(Оффтоп)

Как часто бывает в этих журналах, статья тянет на хороший курсовик хорошего советского студента.

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 19:20 
Спасибо.
А как это дело реализовать?
У меня задача такая:
Имеется набор точек на плоскости. Известно, что они расположены на эллипсе.
Необходимо оценить коэффициенты уравнения эллипса.

Реализовывал аппроксимацию по МНК: погрешность для рассматриваемой задачи получается
большой - невязка во вотором знаке после запятой. Необходимо в 12-13ом знаках.

Существуют ли другие методы аппроксимации эллипса?

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 19:42 
h_dima в сообщении #377063 писал(а):
А как это дело реализовать?
...............................................
Реализовывал аппроксимацию по МНК:
Чего-то я не понял. Вы же уже как-то реализовали, и справшиваете, как реализовать. Или Вы сделали не по статье, а хотите сделать по статье? Как Вы реализовали то, что Вы реализовали?

Цитата:
погрешность для рассматриваемой задачи получается
большой - невязка во вотором знаке после запятой. Необходимо в 12-13ом знаках.

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

Цитата:
Существуют ли другие методы аппроксимации эллипса?
Не знаю.

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 20:13 
Хочу реализовать по статье. А реализовывал чисто по мнк.

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 20:54 
Но мне реально непонятно, как это Вы "реализовывали чисто по мнк". Вот я пока не знаю, как бы я это делал, не вводя доп. условий на коэффициенты. Что Вы минимизировали?

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

Также любопытно, как они справляются со случаем, если точки расположены строго на параболе. Обсуждение этого случая напрашивается: парабола запрещена их условием нормировки, но тогда должен получаться "сколь угодно близкий" к этой параболе эллипс, "сколь угодно огромный" то есть, бесконечности выползают, какая-то ерунда должна получаться. Плохое, на мой взгляд, условие нормировки, как и исходное условие, чтобы это был непременно эллипс.

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 21:13 
a11x^2 + 2a12xy + a22y^2 + 2a13x + 2a23y + a33 = 0
Реализация по мнк
[img]E:\!!\67_1.jpg[/img]

 
 
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 21:29 
Предлагаю Вам писать по правилам форума:
Код:
$ a_{11}x^2 + 2a_{12}xy + a_{22}y^2 + 2a_{01}x + 2a_{02}y + a_{00} = 0 $
Получается $a_{11}x^2 + 2a_{12}xy + a_{22}y^2 + 2a_{01}x + 2a_{02}y + a_{00} = 0$.

Ответа я пока не увидел: "чисто по МНК" мы здесь получим $a_{11}=a_{12}= a_{22}=\ldots = 0$, о чём я уже выше писал с другими буковками.

-- 18 ноя 2010, 21:34 --

Заметтьте, если будете со статьёй разбираться, что Вы поступили правильно, записав коэффициент как ${\color{blue}2}a_{12}xy$. Ребята из статьи назвали его просто $b\,xy$, без двоечки, неканонично. Это надо будет не проглядеть при "кодировании" статьи.

 
 
 
 Re: Аппроксимация эллипса
Сообщение19.11.2010, 11:04 
Добавлю, что статья меня заинтересовала от того, что я когда-то уже думал над выбором условия нормировки коэффициентов коники $$Ax^2+2Bxy+Cy^2+2Dx+2Ey+F=0$$ (и вряд ли это было в плане МНК; не помню). В качестве такового у меня получилось $$B^2=(1-A)(1-C),\text{~~~~или~~~~}B^2-AC+A+C=1.$$ И с ним никаких особенностей не должно возникнуть.

Задачу, где важно навязать эллипсность ($AC-B^2>0$), мне придумать не удалось. Эллипсность должна обеспечиваться качеством фитируемых данных. И ежели этого нет, то и навязанная сверху эллипсность на фиг не нужна...

Качественные данные мне представляются следующих (двух) типов:
1) Достаточно большая дуга, эллипс распознаётся визуально.
2) Малая дуга (типа сечение линзы), но "отшлифованная" и, соответственно, точно оцифрованная.

 
 
 
 Re: Аппроксимация эллипса
Сообщение19.11.2010, 14:34 
$  a_{11}x^2 + 2a_{12}xy + a_{22}y^2 + 2a_{13}x + a_{23}y + a_{33} = 0$
Аппроксимация по мнк
$
{\left[
\begin{array}{c}
a_{33}\\2a_{13}\\2a_{23}\\2a_{12}\\a_{11}\\a_{22}
\end{array}
\right]=
{\left[
\begin{array}{cccccc}
N & \sum x_{i} & \sum y_{i} & \sum x_{i}y_{i} & \sum x_{i}^2 & \sum y_{i}^2 \\ 
\sum x_{i} & \sum x_{i}^2 & \sum x_{i}y_{i} & \sum x_{i}^2y_{i} & \sum x_{i}^3 &\sum x_{i}y_{i}^2 \\
\sum y_{i} & \sum x_{i}y_{i} & \sum y_{i}^2 & \sum x_{i}y_{i}^2 & \sum x_{i}^2y_{i} & \sum y_{i}^3\\
\sum x_{i}y_{i}&\sum x_{i}^2y_{i} & \sum x_{i}y_{i}^2 & \sum x_{i}^2y_{i}^2 & \sum x_{i}^3y_{i} & \sum x_{i}y_{i}^3\\
\sum x_{i}^2 & \sum x_{i}^3 & \sum x_{i}^2y_{i} & \sum x_{i}^3y_{i} & \sum x_{i}^4 & \sum x_{i}^2y_{i}^2\\
\sum y_{i}^2 & \sum x_{i}y_{i}^2 & \sum y_{i}^3 & \sum x_{i}y_{i}^3 & \sum x_{i}^2y_{i}^2 & \sum y_{i}^4    
\end{array}
\right]}^{-1}
{\left[
\begin{array}{c}
1\\1\\1\\1\\1\\1
\end{array}
\right]
$
N - количество точек

 
 
 
 Re: Аппроксимация эллипса
Сообщение19.11.2010, 16:00 
Вау!
Я пока только замечу, что индекс типа x_{i} необязательно брать в фигурные скобки: вполне можно писать x_i^2. Фигурные скобки нужны, понятно, когда индекс длиннее одного символа (то же и с показателем степени, но это Вы распознали). Про то, как попроще пишутся матрицы мне и самому не помешает вспомнить (команда \pmatrix кажется; или \begin{pmatrix}...\end{}).
А по делу постараюсь скоро отписать (я как бы на работе).

-- 19 ноя 2010, 16:14 --

Да, собственно, всё очень просто.
Этот столбец с единичками --- он откуда? Когда Вы расписали 6 производных по $a_{11}, a_{21},\ldots$, у Вас в правой части Были одни нули --- условие минимума, производная равна нулю. Вы теперь домножили на обратную матрицу, и нули подменили единичками. Это ничем не обосновано (там ведь даже величины разной размерности должны были быть).

Я не представляю себе, как можно интерпретировать Ваш результат. Неужели действительно эллипс получился, похожий на правду? (Ведь Ваша картинка со странным адресом
h_dima в сообщении #377100 писал(а):
[img]E:\!!\67_1.jpg[/img]
у нас, естественно, не нарисовалась. Карнинку надо загружать на какой-нть http://; с Вашего компа картинки не аплоадятся).

-- 19 ноя 2010, 16:30 --

Возьмём, скажем, точки на окружности $x^2+y^2-50^2=0$:
Код:
x   y
0 50
30 40
40 30
14 48
50  0
0 -50
Какие коэффициенты Вы получаете для них?

 
 
 [ Сообщений: 20 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group