2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Насильственная аппроксимация дуги заданным эллипсом
Сообщение09.01.2019, 18:53 


18/05/10
36
На работе у меня есть такая проблемка:
Камера снимает движущиеся таблетки. Есть последовательность фреймов с контурами таблеток. Предварительно таблетка сфотографирована и ее нормативный контур известен. Он близок к эллипсу и аппроксимирован им. Параметры эллипса известны. На фреймах есть куски дуг таблеток. По этим небольшим дугам требуется найти центр таблетки. Но если небольшую дугу аппроксимировать эллипсом, то часто получаются эллипсы совсем с другими параметрами, нежели нормативные. А требуется по дуге находить центр таблетки.
Если круглая таблетка, то зная ее истинный радиус легко найти приблизительно ее центр, т.е. по точкам дуги и известному радиусу найти координаты ее центра. А как найти центр таблетки если известны точки ее небольшой дуги и параметры ее нормативного эллипса a и b? Т.е. как заданную дугу аппроксимировать эллипсом с известными длинами его полуосей? Достаточно приблизительно найти центр таблетки.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение09.01.2019, 19:48 
Заслуженный участник
Аватара пользователя


30/01/06
67295
Метод наименьших квадратов.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение09.01.2019, 19:54 
Заслуженный участник
Аватара пользователя


01/08/06
2490
Уфа
1) Таблетка, какой бы формы она ни была — всё-таки не эллипс (плоская фигура), а имеет какую-то трёхмерную форму — эллипсоид, цилиндр или что-то ещё.
2) Возможно, таблетка имеет форму круглого цилиндра (как это чаще всего и бывает), но из-за поворота круги превращаются в эллипсы. Но это два разных эллипса, а не один (плюс две прямые перемычки между ними). Или ещё может быть, что таблетка имеет форму эллипсоида, проекция которого на плоскость — эллипс (на этот раз один и тот же). Две разные задачи.
3) В любом случае, чем меньше дуга, тем хуже получится результат (из-за погрешностей картинки).

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение09.01.2019, 21:38 


18/05/10
36
worm2 в сообщении #1367246 писал(а):
1) Таблетка, какой бы формы она ни была — всё-таки не эллипс (плоская фигура), а имеет какую-то трёхмерную форму — эллипсоид, цилиндр или что-то ещё.
2) Возможно, таблетка имеет форму круглого цилиндра (как это чаще всего и бывает), но из-за поворота круги превращаются в эллипсы. Но это два разных эллипса, а не один (плюс две прямые перемычки между ними). Или ещё может быть, что таблетка имеет форму эллипсоида, проекция которого на плоскость — эллипс (на этот раз один и тот же). Две разные задачи.
3) В любом случае, чем меньше дуга, тем хуже получится результат (из-за погрешностей картинки).

Да, все верно вы пишите, но как же решать мою задачу: аппроксимировать дугу на плоскости заданным эллипсом? Как в аппроксимации навязать конкретные величины осей a и b?
Аппроксимировать набор точек на плоскости эллипсом (какой получится) я умею.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение09.01.2019, 21:53 
Заслуженный участник
Аватара пользователя


30/01/06
67295
Tur в сообщении #1367283 писал(а):
Аппроксимировать набор точек на плоскости эллипсом (какой получится) я умею.

Тогда в чём состоит ваш вопрос?

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение09.01.2019, 22:37 


18/05/10
36
Munin в сообщении #1367287 писал(а):
Tur в сообщении #1367283 писал(а):
Аппроксимировать набор точек на плоскости эллипсом (какой получится) я умею.

Тогда в чём состоит ваш вопрос?

Я же все ясно выразил. Есть точки на плоскости (пиксели) надо их аппроксимировать не абы каким эллипсом, а эллипсом определенным, т.е. с определенными длинами полуосей a и b. Что здесь непонятно?
Подобно тому как если бы надо было аппроксимировать точки окружностью не вообще, а заданного радиуса. В таком случае можно было бы взять две точки дуги А и B разнесенные между собой скажем на величину заданного радиуса, соединить их прямой и восставить в ее середине перпендикуляр к линии АB на котором должен находиться центр окружности. Далее на этом перпендикуляре можно было бы найти точку (центр окружности) удаленную от исходных двух выбранных А и B на расстояние заданного радиуса R. Таких точек будет две, выбираем нужную и все. Это самый простой, грубый вариант. Может быть с эллипсом можно проделать подобную процедуру, но более изящную и найти для конкретной дуги конкретный эллипс с полуосями a и b? Скажем находим по данной дуге какой то эллипс с какими то a и b, затем каким то образом его деформируем так чтобы эти a и b стали равны заданным изначально, но при этом аппроксимация в каком то смысле, должна сохраняться, т.е. расстояния от точек дуги до трансформируемых (сдвигаемых) фокусов должно быть примерно равно известному изначально, наподобие a и b. Теперь понятно?

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение09.01.2019, 22:38 


09/01/19
9
Tur в сообщении #1367283 писал(а):
Да, все верно вы пишите, но как же решать мою задачу: аппроксимировать дугу на плоскости заданным эллипсом? Как в аппроксимации навязать конкретные величины осей a и b?
Аппроксимировать набор точек на плоскости эллипсом (какой получится) я умею.
Первое, что пришло в голову... У Вас есть несколько дуг, априорно принадлежащих одному эллипсу с осями $a$ и $b$. Выбираете по три точки на каждой из дуг (2 крайние и середину) и вычисляете сумму расстояний от каждой из них до образующей эллипса. Эллипс (кроме осей) задан еще тремя параметрами: координатой $(x,y)$ на плоскости и углом поворота $\alpha$. Т.е. Ваша целевая функция (которую минимизируете) имеет вот эти три аргумента.
Так пойдет?

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


30/01/06
67295
Tur в сообщении #1367296 писал(а):
Я же все ясно выразил. Есть точки на плоскости (пиксели) надо их аппроксимировать не абы каким эллипсом, а эллипсом определенным, т.е. с определенными длинами полуосей a и b. Что здесь непонятно?

Непонятно было, что вы называли "определённым эллипсом" - такого термина нет в математике.

Ну что ж, аппроксимируйте точно так же, как и раньше, только с определёнными $a$ и $b.$ Получится даже проще: меньше параметров аппроксимации.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение10.01.2019, 06:05 
Аватара пользователя


31/10/08
977
Tur
Вам шашечки или ехать?
Если ехать, то такие задачи как поиск центра с разделением полузакрытых объектов обычно решаются при помощи НС либо вероятностных деревьев решений(каскадов).
Если шашечки, и вы хотите играться аппроксимацией.
Tur в сообщении #1367296 писал(а):
Скажем находим по данной дуге какой то эллипс с какими то a и b, затем каким то образом его деформируем так чтобы эти a и b стали равны заданным изначально, но при этом аппроксимация в каком то смысле, должна сохраняться, т.е. расстояния от точек дуги до трансформируемых (сдвигаемых) фокусов должно быть примерно равно известному изначально, наподобие a и b. Теперь понятно?

Выпишите формулу деформации к примеру формулу вращающегося эллипса. Будет 1 неизвестная константа и её будет легко найти.
Ах чуть не забыл что центр неизвестен тогда +2 константы.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение10.01.2019, 13:04 


29/09/06
4542
Tur в сообщении #1367296 писал(а):
Может быть с эллипсом можно проделать подобную процедуру, но более изящную и найти для конкретной дуги конкретный эллипс с полуосями a и b? Скажем находим по данной дуге какой то эллипс с какими то a и b, затем каким то образом его деформируем так чтобы эти a и b стали равны заданным изначально, но при этом аппроксимация в каком то смысле, должна сохраняться, т.е. расстояния от точек дуги до трансформируемых (сдвигаемых) фокусов должно быть примерно равно известному изначально, наподобие a и b.

Примерно так я бы и поступил, не особо рассчитывая на "изящность", но довольно надёжно. Из Вашего сообщения делаю вывод, что точек достаточно, чтобы получить хоть какой-то эллипс; дуга -- хотя бы четвертинка эллипса. Далее предлагаю нелинейный (линеаризуемый) МНК с итерациями.

0. Нашли хоть какой-то эллипс, допустим по пяти точкам, включая самые крайние. Его центр -- $(U_0,V_0)$, наклон большой оси -- $\xi_0$.
Соответственно, измеренные точки $(X_i,Y_i)$ переводим в "каноническое положение" переносом и поворотом; получаем $(x_i,y_i)$.

1. По этим точкам будем искать искомый эллипс, полагая теперь, что его центр $(u,v)$ и наклон оси $\xi$ малы. Его уравнение имеет вид
$$F(x,y)\equiv A[(x-u)\cos\xi+(y-v)\sin\xi]^2+B[-(x-u)\sin\xi+(y-v)\cos\xi]^2-1=0\eqno(1)$$($A=\frac1{a^2}$, $B=\frac1{b^2}$). Положив в (1) $$u^2=0,\quad v^2=0,\quad uv=0,\quad \sin^2\xi=0,\quad\sin\xi=\xi,$$ решаем линейную задачу МНК для$$\Phi(u,v,\xi)=\sum \left[w_i\,F(x_i,y_i)\right]^2,\eqno(2)$$ в которой пока полагаем $w_i=1$.

2. Тем самым уточняем $U_0\to U_0+u,\;\ldots$ и повторяем процедуру. Если исходные данные достаточно надёжны, получим быструю сходимость $u_j\to 0,\;\ldots$, ($j$ -- номер итерации).

3. Окончательное уточнение проделаем, определив для каждой точки вес $w_i$ так, чтобы слагаемые в (2) были приблизительно пропорциональны расстояниям от точек до эллипса, т.е. чтобы миниизировать сумму квадратов именно отклонений, а не абстрактных значений неявной функции $F(x,y)$. Веса как-то выразятся через радиусы кривизны эллипса в окрестности измеренной точки. Но это отложим: убедиться бы сначала, что Вас такой фокус устраивает, и что оно на Ваших данных работает.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение10.01.2019, 19:56 
Заслуженный участник


18/01/15
937
Можно еще так получить начальное приближение (если дуга дана точно, это и будет точный ответ; но если приближенно, вмешаются погрешности). Возьмем две параллельные прямые, какие угодно, так, чтобы они обе пересекали дугу в двух точках. Т.е. возьмем две параллельные хорды эллипса. Тогда, как хорошо известно, прямая, проходящая через их середины, проходит и через центр эллипса. (Действительно, если взять аффинное преобразование, переводящее эллипс в окружность, то середины параллельных хорд перейдут в середины параллельных хорд; а для окружности утверждение очевидно). Если теперь взять две другие параллельные хорды, не параллельные первым, то получится еще одна прямая через центр. Откуда центр и находится.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение11.01.2019, 15:15 


29/09/06
4542
Алексей К. в сообщении #1367406 писал(а):
Но это отложим: убедиться бы сначала, что...
Закончу, однако, не дожидаясь... Ибо оно работало при Брежневе; сработает, полагаю, и сейчас.

Для точки $(x_i,y_i)$, на расстоянии $d_i$ от эллипса (1), $F(x,y)\equiv\dfrac{x^2}{a^2}+\dfrac{y^2}{b^2}-1=0$, ($d_i<0$ --- внутри оного) выполнено $$ |d_i|\ll\min(a,b)\quad\Longrightarrow\quad d_i\approx\frac{abF(x_i,y_i)}{2\sqrt{(a^2+b^2)-(x_i^2+y_i^2)}}\,.$$ Поэтому в (2) полагаем $$w_i=\frac{1}{\sqrt{(a^2+b^2)-(x_i^2+y_i^2)}}.$$Малость или отрицательность выражения под радикалом означает довольно огромные значения $d_i$ и неприменимость всей описанной кухни.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение11.01.2019, 16:26 


18/05/10
36
Спасибо всем за отклики. Алексей, спасибо за содержательный ответ (правда я не все все понял, но об этом потом)
Вроде бы я решил эту задачку (ниже гротескная для ясности картинка)
Изображение
Справа нормативный эллипс. Слева синим дуга и два эллипса. С центром Мо1 - тот, который получаем так:
коэф-ты а11 а22... из (1) находятся из переопределенной системы в которую подставляем точки x y дуги.
По ним рассчитываются инварианты (3) (4) (5), затем центр (6) и оси (7)
А правильный (т.е. с осями a и b) мог был бы быть с центрм Мо. (поэтому, Алексей, видимо нельзя полагать верным предварительную найденность центра Мо1 и направленность оси, я вообще поначалу думал почти так же: отложить по найденной оси от ближайшего фокуса отрезок с из нормативного эллипса и все)
Мой тупик был в том, что сначала находятся а11 а22... и только по ним a и b. Причем если а11 а22... определены, то и a и b определены. Т.е. я думал как же изменить эти уже найденные а11 а22... чтобы получились верные a и b. А затем пришла простая мысль - что надо каким то образом включить в исходное ур-е (1) величины осей a и b. Но как это сделать - понять не мог. И вот еще простая мысль: поскольку нормативный эллипс определен, то определены и его инварианты, т.е. имеем
Дано: инварианты (3) (4) (5) - это конкретные числа
1. полагаем а11 = 1
2. из (5) находим а22
3. из (4) находим а12
(а12 и а22 это уже конкретные числа)
4. все эти а11 а22 а12 подставляем в (1) и т.о. получаем новую переопределенную систему ур-ний относительно а13 а23 а33.
5. находим их и по (6) находим центр

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

Что то не то. Ведь если положить а11 = 1 и найти а22 и а12 из (5) и (4), то по (2) получается всегда один и тот же угол.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение11.01.2019, 16:51 


29/09/06
4542
Хорошая иллюстрация проблемы.
Tur в сообщении #1367761 писал(а):
поэтому, Алексей, видимо нельзя полагать верным предварительную найденность центра Мо1 и направленность оси
Льзя или нельзя --- надо пробовать. Я не исключаю, что даже такое сильное расхождение, как у Вас на рисунке, всё равно может сойтись куда положено.

Качество первого приближения и способы его отыскания --- это вопросы, требующие думания, в т.ч. с привлечением конкрентых (типичных) данных.
Ну и надо посмотреть --- не строится ли эллипс с заданными полуосями по трём точкам легко. Или с заданным эксцентриситетом --- по 4-м точкам.
Простые, должно быть, задачки, особенно если утром решать (да и может кто-то умный и/или неленивый сразу сообразит и напишет).

-- 11 янв 2019, 17:00:03 --

Tur в сообщении #1367761 писал(а):
Дано: инварианты (3) (4) (5) - это конкретные числа
Вроде нет. Они известны с точностью до нормировки.

 Профиль  
                  
 
 Re: Насильственная аппроксимация дуги заданным эллипсом
Сообщение11.01.2019, 17:19 


18/05/10
36
Pavia в сообщении #1367359 писал(а):
Tur... такие задачи как поиск центра с разделением полузакрытых объектов обычно решаются при помощи НС либо вероятностных деревьев решений(каскадов).
Выпишите формулу деформации к примеру формулу вращающегося эллипса. Будет 1 неизвестная константа и её будет легко найти.
Ах чуть не забыл что центр неизвестен тогда +2 константы.
НС я занимался чуть-чуть и давно, так что пока нет сил все это поднимать, тем более что аналогия с геометрическим нахождением центра окружности по известному радиусу не выходит из поля зрения. Вращающийся эллипс это следующий шаг. С первым бы разобраться.

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

Алексей К., так что скажете по моему заходу? Нельзя полагать равным единице ни один из коэф-тов: а11 а22 а12?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group