Насильственная аппроксимация дуги заданным эллипсом

[Tur]

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

[Munin]

Метод наименьших квадратов.

[worm2]

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

[Tur]

worm2 в сообщении #1367246 писал(а):

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

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

[Munin]

Tur в сообщении #1367283 писал(а):

Аппроксимировать набор точек на плоскости эллипсом (какой получится) я умею.

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

[Tur]

Munin в сообщении #1367287 писал(а):

Tur в сообщении #1367283 писал(а):

Аппроксимировать набор точек на плоскости эллипсом (какой получится) я умею.

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

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

[DeadlineX]

Tur в сообщении #1367283 писал(а):

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

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

[Munin]

Tur в сообщении #1367296 писал(а):

Я же все ясно выразил. Есть точки на плоскости (пиксели) надо их аппроксимировать не абы каким эллипсом, а эллипсом определенным, т.е. с определенными длинами полуосей a и b. Что здесь непонятно?

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

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

[Pavia]

Tur
Вам шашечки или ехать?
Если ехать, то такие задачи как поиск центра с разделением полузакрытых объектов обычно решаются при помощи НС либо вероятностных деревьев решений(каскадов).
Если шашечки, и вы хотите играться аппроксимацией.

Tur в сообщении #1367296 писал(а):

Скажем находим по данной дуге какой то эллипс с какими то a и b, затем каким то образом его деформируем так чтобы эти a и b стали равны заданным изначально, но при этом аппроксимация в каком то смысле, должна сохраняться, т.е. расстояния от точек дуги до трансформируемых (сдвигаемых) фокусов должно быть примерно равно известному изначально, наподобие a и b. Теперь понятно?

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

[Алексей К.]

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)$. Веса как-то выразятся через радиусы кривизны эллипса в окрестности измеренной точки. Но это отложим: убедиться бы сначала, что Вас такой фокус устраивает, и что оно на Ваших данных работает.

[vpb]

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

[Алексей К.]

Алексей К. в сообщении #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$ и неприменимость всей описанной кухни.

[Tur]

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

Справа нормативный эллипс. Слева синим дуга и два эллипса. С центром Мо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) получается всегда один и тот же угол.

[Алексей К.]

Хорошая иллюстрация проблемы.

Tur в сообщении #1367761 писал(а):

поэтому, Алексей, видимо нельзя полагать верным предварительную найденность центра Мо1 и направленность оси

Льзя или нельзя --- надо пробовать. Я не исключаю, что даже такое сильное расхождение, как у Вас на рисунке, всё равно может сойтись куда положено.

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

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

Tur в сообщении #1367761 писал(а):

Дано: инварианты (3) (4) (5) - это конкретные числа

Вроде нет. Они известны с точностью до нормировки.

[Tur]

Pavia в сообщении #1367359 писал(а):

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

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

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

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