Алгоритм поиска параметров 2х окружностей

[alexey007]

Привет, всем!
Помогите найти хороший алгоритм.
Даны зашумленные данные дуг 2х окружностей одинакового радиуса R в виде координат ${x_i,y_i}$ (параметры окружностей: координаты центров и радиуса неизвестны). Также, можно считать, что известно какие точки принадлежат какой из окружностей. Но, если будут идеи как разделить эти множества точек, то я буду очень рад выслушать. Пример представлен на рисунке



Нужен алгоритм, с помощью которого можно будет найти центры этих окружностей и R.
Есть очень много скриптов на матлабе, которые помогают найти параметры окружности для зашумленных данных. Я пытался их использовать. Но, очень часто они дают сильное отличие в радиусах, если я использую их последовательно для каждой из дуг окружностей. А в моей задаче заранее известно, что радиусы одинаковые.
У меня есть идея, реализовать такой алгоритм:
Пусть $\{xb_i,yb_i\}$ - точки, которые принадлежат одной окружности(черные точки) и $\{xr_j,yr_j\}$ - точки, которые принадлежат другой окружности (красные точки) (см. рис)
Центры окружностей с одинаковыми радиусами найти из минимума функции $F(a_1,b_1,a_2,b_2)=\sum{(xb_i-a_1)^2+(yb_i-b_1)^2}-\sum{(xr_j-a_2)^2+(yr_j-b_2)^2} $
А потом, после того как найдутся центры $(a_1,b_1)$ и $(a_2,b_2)$ уже искать радиус как среднее расстояние от всех точек, т.е.
$R=\frac{\sum{\sqrt{(xb_i-a_1)^2+(yb_i-b_1)^2}}+\sum{\sqrt{(xr_j-a_2)^2+(yr_j-b_2)^2}}}{N+M}$, где $N$ и $M$ количество черных и красных точек соответственно

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

[Sender]

Раз радиус один, мне кажется, было бы естественно сразу ввести его в качестве одного из искомых параметров.

-- Вт апр 13, 2021 16:00:47 --

И да, минимизируемый функционал у вас очень странно выглядит, если не сказать больше...

[ipgmvq]

Согласен, что нужно сразу минимизировать функцию пяти неизвестных.
И вначале неплохо предположить распределение шума на этой плоскости (может быть он только вдоль радиуса или только вдоль оси ординат).
В первом случае минимизируем:
$f(r, x_{n}, y_{n}, x_{m}, y_{m}) = \sum\limits_{i=1}^{n} \left( r - \sqrt{\left( y_{i} - y_n \right)^{2} + \left( x_{i} - x_n \right)^{2} } \right)^{2} + \sum\limits_{j=1}^{m} \left( r - \sqrt{\left( y_{j} - y_m \right)^{2} + \left( x_{j} - x_m \right)^{2} } \right)^{2}$

Во втором:
$f(r, x_{n}, y_{n}, x_{m}, y_{m}) = \sum\limits_{i=1}^{n} \left( y_{i} - y_n - \sqrt{ r^{2} - \left( x_{i} - x_n \right)^{2} } \right)^{2} + \sum\limits_{j=1}^{m} \left( y_{j} - y_m - \sqrt{ r^{2} - \left( x_{j} - x_m \right)^{2} } \right)^{2}$

[DeBill]

alexey007
1. Ваш функционал состоит из двух слагаемых, каждое из которых содержит лишь одну пару параметров, и минимизация суммы будет равносильна минимизации каждого по отдельности. Задача упростится.
2. Непонятно, зачем минимизировать именно сумму расстояний: лучше - сумму квадратов; это позволит найти минимум явно.
3. Минимизация суммы квадратов (да и просто суммы) даст не центр окружности; она даст центр масс системы точек. Например, если все точки - на небольшой по размеру дуге, то получим примерно середину этой дуги.

Итого: не годится Ваш функционал.
И, конечно, следует учесть рекомендациюSender про параметр - "радиус окружностей".
Т.е., что-то типа $\sum\limits_{}^{}((xb_i-f_1)^2+(yb_i-b_1)^2-\rho)^2+...$, где $\rho=R^2$. Беда будет в том, что функционал не будет квадратичным - единственность минимума не гарантируется, решать придется градиентными методами (ну хоть градиент легко считать -если нет корней), и результат не гарантируем...

-- 13.04.2021, 18:43 --

ipgmvq
Второй - нехорош: под корнем вполне может получиться отрицательность...

[Евгений Машеров]

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

[alexey007]

Спасибо всем за советы! Классный форум и тут крутые ребята. Использовал функционал

ipgmvq в сообщении #1514137 писал(а):

В первом случае минимизируем:
$f(r, x_{n}, y_{n}, x_{m}, y_{m}) = \sum\limits_{i=1}^{n} \left( r - \sqrt{\left( y_{i} - y_n \right)^{2} + \left( x_{i} - x_n \right)^{2} } \right)^{2} + \sum\limits_{j=1}^{m} \left( r - \sqrt{\left( y_{j} - y_m \right)^{2} + \left( x_{j} - x_m \right)^{2} } \right)^{2}$

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