2014 dxdy logo

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

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


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


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



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


18/05/10
46
Алексей К. в сообщении #1374850 писал(а):
У меня не грипп :-( , но я тоже вынужден отложить эту развлекуху на некоторое время.
Для меня это не развлекуха, а работа и вы в ней мне здорово помогли, большое бремя сняли с плеч. Спасибо!
Опишу как это работает.
Дана дуга (синие 111 точек) и ее первоначальная аппроксимация эллипсом (на рисунке изображен черным и белым его центр и фокусы). Получившиеся параметры эллипса а = 187 и b = 58
Изображение
Задача состоит в том чтобы эту дугу аппроксимировать эллипсом с параметрами а = 79 и b = 37.5
Вот код исходной аппроксимации:

(Оффтоп)

Код:
function [x y Mo MT] = move_zero(x, y)
ell = old_param_ell(x, y);
drawell_by_aa(ell.aa);
mm(ell.F1,'w'); mm(ell.F2,'w');
MT = ell.MT; Mo = ell.Mo; mm(Mo,'w')
[x y] = movearr(x, y, MT);
end

function ell = old_param_ell(x, y)
% ell - aa MT fi a b Mo F1 F2
mx = mean(x); my = mean(y);
xn = x - mx; yn = y - my;
[a11 a12 a13 a22 a23] = aquadric(xn, yn);
[D I d] = invariant(a11, a12, a13, a22, a23);
type = type_quadric(D, I, d); % ell.type = 1;
if type == 1 || type == 2
  [a b fi s c] = a_b_fi(a11, a22, a12, d);
  Mo = first_Mo_d(a11, a12, a13, a22, a23);
  [Mo MT] = Mo_ell(Mo, mx, my, s, c);
  [F1 F2] = foci(Mo, s, c, a, b);
else
  if type == -1 return; end
  if type == 3 disp('parabola'); return; end
end
ell.type = type;
% ell.faa = [a11 a12 a13 a22 a23 1];
ell.aa = complete_equation(a, b, Mo, fi);
ell.MT = MT;
ell.ab = [a b];
ell.fi = fi;
ell.Mo = Mo;
ell.F1 = F1;
ell.F2 = F2;
end
function type = type_quadric(D, I, d)
if d == 0
  type = -1; return
end
if 0 < D && d*I < 0
  type = 1; return % ellipse
end
if D < 0
  type = 2; return % hyperbola
end
if D == 0
  type = 3; return % parabola
end
type = -1;
end
function Mo = first_Mo_d(a11, a12, a13, a22, a23)
D = a11*a22 - a12*a12;
Mo.X = (a12*a23 - a13*a22)/D;
Mo.Y = (a13*a12 - a11*a23)/D;
end
function [a b fi s c] = a_b_fi(a11, a22, a12, d)
tg = 2*a12/(a11-a22); fi = 0.5*atan(tg);
s = sin(fi); c = cos(fi); s2 = s*s; c2 = c*c;
lambda1 = a11*c2 + 2*a12*s*c + a22*s2;
lambda2 = a11*s2 - 2*a12*s*c + a22*c2;
a2 = -d/(lambda1*lambda1*lambda2);
b2 = -d/(lambda1*lambda2*lambda2);
if a2 < 0 a2 = -a2; end
if b2 < 0 b2 = -b2; end
if a2 < b2
  tmp = b2; b2 = a2; a2 = tmp;
  % s = sin(fi+pi/2); c = cos(fi+pi/2);
  fi = fi + pi/2;
  s = sin(fi); c = cos(fi);
end
a = sqrt(a2); b = sqrt(b2);
end
function [Mo MT] = Mo_ell(Mo, mx, my, s, c)
MT1 = [1 0 -mx; 0 1 -my; 0 0 1];
Mper = [1 0 -Mo.X; 0 1 -Mo.Y; 0 0 1];
Mpov = [c s 0; -s c 0; 0 0 1];
MT2 = Mpov*Mper;
MT = MT2*MT1; invM = inv(MT);
P.X = 0; P.Y = 0; Mo = mp(invM, P);
end
function [F1 F2] = foci(Mo, s, c, a, b)
tg = s/c; p = sqrt(a*a-b*b)/sqrt(1+tg*tg);
F1.X = Mo.X - p; F1.Y = Mo.Y - tg*p;
F2.X = Mo.X + p; F2.Y = Mo.Y + tg*p;
end

function aa = complete_equation(a, b, Mo, fi)
s = sin(fi); c = cos(fi);
s2 = s*s; c2 = c*c;
xo = Mo.X; yo = Mo.Y;
xo2 = xo*xo; yo2 = yo*yo;
a2 = a*a; b2 = b*b;
a11 = c2/a2 + s2/b2;
a22 = s2/a2 + c2/b2;
a12 = s*c*(1/a2 - 1/b2);
a13 = -xo*a11 - yo*a12;
a23 = -xo*a12 - yo*a22;
a33 = a11*xo2 + a22*yo2 + 2*a12*xo*yo - 1;
aa = [a11 a12 a13 a22 a23 a33]';
end

Нулевое приближение это центр найденного эллипса Mo.X = 195 Mo.Y = -105 и угол наклона эллипса fi = 0.7442
При аппроксимации получена также матрица поворота и переноса МТ. С ее помощью преобразуем исходную дугу так чтобы центр найденного эллипса совпал с началом координат, а главная ось эллипса с осью Х, см рис ниже.
Изображение
Обозначим новую полученную дугу xn, yn. Теперь задача состоит в том чтобы аппроксимировать ее заданным эллипсом.

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


18/05/10
46
Эту аппроксимацию осуществим с помощью алгоритма предложенного Алексеем (немного преобразую его)
$L(x,y;u,v,\xi)=\frac{x}{a^2}u+\frac{y}{b^2}v+\left(\frac1{a^2}-\frac1{b^2}\right)xy\,\xi-0.5\cdot(\frac{x^2}{a^2}+ \frac{y^2}{b^2}-1) = 0

Изображение
Параметры голубого эллипса аппроксимирующего синюю дугу xn, yn
a = 79 b = 37.5 Mo.X = 76 Mo.Y = -4.6 fi = 0.0135
Вот ф-ция, осуществляющая эту аппроксимацию

(Оффтоп)

Код:
function [Mo fi MT] = get_vell(a,b,x,y)
a2 = a*a; b2 = b*b; A = x/a2; B = y/b2;
C = (1/a2 - 1/b2)*x.*y;
D = -(x.*x/a2 + y.*y/b2 - 1)/2;
M = [A B C D]; X = pere_slau(M);
Mo.X = -X(1); Mo.Y = -X(2); fi = X(3);

Mper = [1 0 -Mo.X; 0 1 -Mo.Y; 0 0 1];
s = sin(fi); c = cos(fi);
Mpov = [c s 0; -s c 0; 0 0 1];
MT = Mpov*Mper;
end

function X = pere_slau(M)
% решение переопределенной
% системы уравнений
% A1*x + B1*y = C1    M = [A1 B1 -C1;
% A2*x + B2*y = C2         A2 B2 -C2;
% A3*x + B3*y = C3         A3 B3 -C3;
% A4*x + B4*y = C4         A4 B4 -C4];
[~, c] = size(M);
A = M(:,1:c-1);
B = M(:,c);
C = A'*A;
D = A'*B;
X = C\D;
end

Эта функция дает и соответствующую матрицу МТ. С ее помощью можно перенести новый полученный эллипс в координаты исходной дуги
Изображение
Как видим аппроксимация еще далека от завершения.
Подобно тому как мы перенесли с помощью первичной аппроксимации исходную дугу в координаты где центр найденного эллипса попадал в начало координат - так и сейчас перенесем координаты дуги xn yn с помощью только что полученной МТ и получим (белые точки - обозначим их xn2 yn2):
Изображение
На следующем шаге будем аппроксимировать уже эти точки

-- Пн фев 11, 2019 15:38:22 --

Ниже приведен зеленый эллипс с параметрами a = 79 b = 37.5 аппроскимирующий белые точки дуги
Изображение
Новый зеленый эллипс в координатах исходной дуги
Изображение
Как видим эта аппроксимация уже ближе к истинной.
Сделаем еще одну итерацию: с помощью новой "зеленой" МТ получим новую дугу xn3 yn3 (желтую)
Изображение
новая аппроксимация желтой дуги (красная линия). Уже по рис видно на сколько ее центр близок с началу координат
Изображение
Новая, красная итерация в исходных координатах
Изображение

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


18/05/10
46
Нулевым приближением полагались два параметра найденных при первичной аппроксимации дуги произвольным эллипсом: угол наклона его главной оси и его центр Мо1. Я изменил это условие и нашел точку пересечения (Р) оси эллипса с его дугой или с ним самим и затем по оси эллипса отложит отрезок равный а = 79. Т.о. получил новый центр Мо.
Изображение
В этом случае требуются всего одна-две итерации. Вот первая:
Изображение
А вот вторая желтая, почти совпадающая с предыдущей
Изображение

А вот случай когда дуга гипербола (так показывает первичная ее аппроксимация кривой второго порядка)
Изображение
Находим ось гиперболы, ее пересечение либо с дугой либо с самой гиперболой в ее вершине (Р). От этой точки Р откладываем отрезок а = 79 и находим Мо - начальное приближение эллипса. Затем первая итерация:
Изображение
и вторая:
Изображение
Т.о. аппроксимировали гиперболу эллипсом с заданными осями.

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


05/09/16
5365
Кажись, полезное чтение для ТС:

Grbić, R., Grahovac, D., & Scitovski, R. (2016). A method for solving the multiple ellipses detection problem. Pattern Recognition, 60, 824–834.
https://doi.org/10.1016/j.patcog.2016.06.031

(Abstract)

In this paper, the multiple ellipses detection problem on the basis of a data points set coming from a number of ellipses in the plane not known in advance is considered. An ellipse is considered as a Mahalanobis circle with some positive definite matrix. A very efficient method for solving this problem is proposed. This method very successfully combines the well-known direct least squares method and the RANSAC algorithm with a realistic statistical model of multiple ellipses in the plane. The method is illustrated and tested on numerous synthetic and real-world applications. The method was also compared with other similar methods. In the case when a data points set comes from a number of ellipses with clear edges, the proposed method gives results similar to other known methods. However, when a data points set comes from a number of ellipses with noisy edges, the proposed method performs significantly better than the other methods. We should emphasize the advantage and utility of the proposed methods in a variety of applications such as: medical image analysis and ultrasound image segmentation.


Там они детектируют эллипсы без предварительно заданных параметров (полуосей). И вродь получается хорошо.
Изображение
Ну и библиография там есть.
Например:
[16] Y. Qiao, S. H. Ong, Arc-based evaluation and detection of ellipses, Pattern Recognition 40 (2007) 1990–2003 ( DOI: 10.1016/j.patcog.2006.10.009 )
картинка оттуда:
Изображение
[17] C. Akinlar, C. Topal, Edcircles: A real-time circle detector with a false detection control, Pattern Recognition 46 (2013) 725–740. ( https://doi.org/10.1016/j.patcog.2012.09.020 )

Насчет как почитать. Идете на sci hub (напр. sci-hub.se ) и туда вводите doi (всю строку, т.е. напр. https://doi.org/10.1016/j.patcog.2016.06.031 )

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


18/05/10
46
wrest, вы эту тему не смотрели. С детектированием эллипса уже много лет нет никаких проблем. Грубо говоря в этой теме речь шла об аппроксимации гиперболы эллипсом. Даны точки, дуга и мы даже не выясняем эти точки эллипса или гиперболы или еще чего-то. Это безразлично. Эти точки теперь можно аппроксимировать эллипсом причем длины его осей мы можем выбирать какие нам заблагорассудится.

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

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



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

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


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

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