2014 dxdy logo

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

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


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


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



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


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

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


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

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


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

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


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

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

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


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

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

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


18/05/10
53
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
69731
Tur в сообщении #1367296 писал(а):
Я же все ясно выразил. Есть точки на плоскости (пиксели) надо их аппроксимировать не абы каким эллипсом, а эллипсом определенным, т.е. с определенными длинами полуосей a и b. Что здесь непонятно?

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

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

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


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

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

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


29/09/06
4548
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
1226
Можно еще так получить начальное приближение (если дуга дана точно, это и будет точный ответ; но если приближенно, вмешаются погрешности). Возьмем две параллельные прямые, какие угодно, так, чтобы они обе пересекали дугу в двух точках. Т.е. возьмем две параллельные хорды эллипса. Тогда, как хорошо известно, прямая, проходящая через их середины, проходит и через центр эллипса. (Действительно, если взять аффинное преобразование, переводящее эллипс в окружность, то середины параллельных хорд перейдут в середины параллельных хорд; а для окружности утверждение очевидно). Если теперь взять две другие параллельные хорды, не параллельные первым, то получится еще одна прямая через центр. Откуда центр и находится.

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


29/09/06
4548
Алексей К. в сообщении #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
53
Спасибо всем за отклики. Алексей, спасибо за содержательный ответ (правда я не все все понял, но об этом потом)
Вроде бы я решил эту задачку (ниже гротескная для ясности картинка)
Изображение
Справа нормативный эллипс. Слева синим дуга и два эллипса. С центром Мо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
4548
Хорошая иллюстрация проблемы.
Tur в сообщении #1367761 писал(а):
поэтому, Алексей, видимо нельзя полагать верным предварительную найденность центра Мо1 и направленность оси
Льзя или нельзя --- надо пробовать. Я не исключаю, что даже такое сильное расхождение, как у Вас на рисунке, всё равно может сойтись куда положено.

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

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

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

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


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

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

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

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

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



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

Сейчас этот форум просматривают: frostysh


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

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