Случай 1: Преобразование Хафа
В решении проблем компьютерного зрения мы часто ищем круги среди новейшей информации. Эта проблема характеризуется наличием множества точек данных, возможно, происходящих из разных кругов в присутствии большого количества шума.
Обычный подход к решению этой проблемы - Преобразование Хафа https://en.wikipedia.org/wiki/Circle_Hough_Transform. Основная идея состоит в суммировании доказательств для кругов, которые могут проходить через каждую точку (x, y).
Мы создаем целочисленный массив с именем Hough [a, b, r], который параметризует все возможные круги, которые могут проходить через вашу точку (x, y). Это эквивалентно рисованию круга радиуса 1 в плоскости r = 1 с центром в (x, y); окружность радиуса 2 в плоскости r = 2 с центром в (x, y) и т. д.
Каждый раз, когда круг проходит через точку в [a, b, r], мы добавляем 1 к соответствующему значению. Некоторые очки накапливают много доказательств. Эти точки соответствуют кругам интересов.
Изображение с cis.rit.edu иллюстрирует, что происходит на одной из r-плоскостей.
Выполнение этого для каждой точки (x, y) будет генерировать свидетельство в отношении каждой из точек в [a, b, r], соответствующих кругу, который вы ищете. Так что просто просканируйте этот массив, чтобы найти точку с максимальным доказательством. Это твой круг.
Пример преобразования Хафа
Знание радиуса круга сводит это от задачи O (n ^ 3) к задаче O (n ^ 2), так как нужно построить и отсканировать только одну плоскость. У меня также были хорошие результаты при построении радиусов в лог-пространстве, чтобы получить (менее точный) алгоритм O (n ^ 2 log n).
Случай 2: Круглый фитинг
Если известно, что точки лежат вблизи границы одного круга, и / или если точки не очень многочисленны и / или иначе мы очень уверены, что шума очень мало, то преобразование Хафа является плохим решением поскольку он требует значительных вычислительных ресурсов, требует много памяти и из-за растровой природы массива аккумуляторов, возможно, не очень точен.
В этом случае мы можем захотеть подогнать окружность по аналогии с методами подгонки линии, в которых используется линейная регрессия. Обсуждение техники подгонки окружности можно найти в https://pdfs.semanticscholar.org/faac/44067f04abf10af7dd583fca0c35c5937f95.pdf.
(довольно простая) реализация этого алгоритма представлена ниже.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
float x;
float y;
} point;
/*
* Function using a modified least squares approach to circle fitting.
*
* Reference :
*
* Umbach, D. and Jones, K. N. "A few methods for fitting circles to data",
* IEEE Trans Instrumentation and Measurement
* vol XX(Y) 2000
*
* https://pdfs.semanticscholar.org/faac/44067f04abf10af7dd583fca0c35c5937f95.pdf
*
* NOTES
*
* The code below has not been checked for numerical stability or conditioning.
*/
int circle_fit_MLS (point P[], int n, double *x_pos, double *y_pos, double *radius)
{
int i;
double sum_x=0.0, sum_y=0.0, sum_xx=0.0, sum_xy=0.0, sum_yy=0.0, sum_xyy=0.0, sum_yxx=0.0, sum_xxx=0.0, sum_yyy=0.0;
double A, B, C, D, E;
double x2, y2, xy, F, xdif, ydif;
for (i=0; i<n; i++)
{
sum_x += P[i].x;
sum_y += P[i].y;
x2 = P[i].x * P[i].x;
y2 = P[i].y * P[i].y;
xy = P[i].x * P[i].y;
sum_xx += x2;
sum_yy += y2;
sum_xy += xy;
sum_xyy += xy*P[i].y;
sum_yxx += P[i].y*x2;
sum_xxx += x2*P[i].x;
sum_yyy += y2*P[i].y;
}
A = n * sum_xx - sum_x * sum_x;
B = n * sum_xy - sum_x * sum_y;
C = n * sum_yy - sum_y * sum_y;
D = 0.5 * ( n * (sum_xyy + sum_xxx) - sum_x * sum_yy - sum_x * sum_xx);
E = 0.5 * ( n * (sum_yxx + sum_yyy) - sum_y * sum_xx - sum_y * sum_yy);
F = A*C - B*B;
*x_pos = (D*C - B*E) / F;
*y_pos = (A*E - B*D) / F;
*radius = 0;
for (i=0; i<n; i++)
{
xdif = P[i].x - *x_pos;
ydif = P[i].y - *y_pos;
*radius += sqrt(xdif * xdif + ydif * ydif);
}
*radius /= n;
return 0;
}
Основная программа, представленная ниже, может использоваться для тестирования кода. Пожалуйста, оставляйте в комментариях любые результаты / наблюдения / предложения по улучшению.
int main()
{
point *P;
int n, i;
double xpos, ypos, radius;
printf ("Please enter the number of points \n> ");
scanf ("%d", &n);
P = malloc (n * sizeof(point));
for (i=0; i<n; i++)
{
printf ("x%d = ", i);
scanf ("%f", &P[i].x);
printf ("y%d = ", i);
scanf ("%f", &P[i].y);
}
circle_fit_MLS (P, n, &xpos, &ypos, &radius);
printf (" a = %f\n", xpos);
printf (" b = %f\n", ypos);
printf (" r = %f\n", radius);
}