2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Аппроксимация эллипса
Сообщение17.11.2010, 20:35 


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

 Профиль  
                  
 
 Re: Аппроксимация эллипса
Сообщение17.11.2010, 23:10 
Заслуженный участник
Аватара пользователя


15/10/08
11581
h_dima в сообщении #376671 писал(а):
аппроксимации эллипса

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

 Профиль  
                  
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 14:00 


29/09/06
4552
Я пока смог только по диагонали глянуть статью (тоже не люблю по-иностранному читать). На первый взгляд --- задачка "второго уровня" сложности. К "первому уровню" я отношу типовой чисто линейный МНК (без всяких там ограничений на коэффициенты).

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

 Профиль  
                  
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 15:12 


17/11/10
8
Известна. В этой статье используется тот же критерий, как и в мнк - минимальная сумма квадратов отклонений. Так?

 Профиль  
                  
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 16:42 


26/12/08
1813
Лейден
А если не секрет, почему по-иностранному читать не любите?

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


29/09/06
4552

(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 


17/11/10
8
Спасибо.
А как это дело реализовать?
У меня задача такая:
Имеется набор точек на плоскости. Известно, что они расположены на эллипсе.
Необходимо оценить коэффициенты уравнения эллипса.

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

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

 Профиль  
                  
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 19:42 


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

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

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

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

 Профиль  
                  
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 20:13 


17/11/10
8
Хочу реализовать по статье. А реализовывал чисто по мнк.

 Профиль  
                  
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 20:54 


29/09/06
4552
Но мне реально непонятно, как это Вы "реализовывали чисто по мнк". Вот я пока не знаю, как бы я это делал, не вводя доп. условий на коэффициенты. Что Вы минимизировали?

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

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

 Профиль  
                  
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 21:13 


17/11/10
8
a11x^2 + 2a12xy + a22y^2 + 2a13x + 2a23y + a33 = 0
Реализация по мнк
[img]E:\!!\67_1.jpg[/img]

 Профиль  
                  
 
 Re: Аппроксимация эллипса
Сообщение18.11.2010, 21:29 


29/09/06
4552
Предлагаю Вам писать по правилам форума:
Код:
$ 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 


29/09/06
4552
Добавлю, что статья меня заинтересовала от того, что я когда-то уже думал над выбором условия нормировки коэффициентов коники $$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 


17/11/10
8
$  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 


29/09/06
4552
Вау!
Я пока только замечу, что индекс типа 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