Лучший алгоритм подгонки окружности

Question

Мне нужен очень точный алгоритм для подгонки круга к набору точек данных (на самом деле мне нужно определить центр).Данные поступают после бинаризации и сегментации изображения.Я попробовал простые алгоритмы центра масс и взвешенного центра масс, а также предварительно сделал функцию OpenCv :: fitEllipse.Я получил лучшие результаты от функции OpenCV, но все же точность не достаточна.Результаты значительно ухудшаются, когда центр закрепляется в подпиксельных областях.Точности, которую я получил, недостаточно, даже когда имеешь дело с смоделированными данными, что плохо, так как в конечном итоге процедура должна будет работать с данными, полученными камерами.Есть ли у вас какие-либо предложения, какой алгоритм мне искать, или у вас есть готовое решение?Я бы предпочел воздержаться от ссылок на любые внешние библиотеки.Спасибо за вашу помощь.

отредактировано: калибровочную мишень можно локализовать в любой области поля зрения.Ниже приведены лучшие результаты, которые я получил с помощью процедуры OpenCV:

169,367 748,345  
167,557 820,788  
165,690 893,158  
164,047 965,197  
162,715 1036,729  
161,575 1108,089  
160,477 1179,552  
233,297 1015,313  
232,076 1086,965  
220,359 1229,578  
268,494 1160,275  
339,544 1162,980  
362,017 1235,669  
433,390 1238,491  
482,754 1168,299  
505,233 1241,039  
554,856 1170,664  
577,302 1243,439  
627,331 1172,795  
649,507 1245,665  
713,572 588,896  
711,995 661,853  
710,440 735,034  
708,722 808,856  
707,018 882,674  
705,377 956,169  
703,609 1029,211  
701,716 1101,950  
699,760 1174,689  
721,895 1247,620  
785,829 614,754  
784,344 687,750  
782,819 761,315  
781,292 835,225  
779,389 908,975  
777,619 982,335  
775,688 1055,275  
773,672 1128,091  
771,603 1200,724  

Отредактировано: численно сгенерированная модель и реальные координаты центров:

51,1    79,8
51,1    179,8
51,1    279,8
51,1    379,8
51,1    479,8
51,1    579,8
51,1    679,8
51,1    779,8
51,1    879,8
51,1    979,8
51,1    1079,8
51,1    1179,8
51,1    1279,8
51,1    1379,8
51,1    1479,8
151,1   79,8
151,1   179,8
151,1   279,8
151,1   379,8
151,1   479,8
151,1   579,8
151,1   679,8
151,1   779,8
151,1   879,8
151,1   979,8
151,1   1079,8
151,1   1179,8
151,1   1279,8
151,1   1379,8
151,1   1479,8
251,1   79,8
251,1   179,8
251,1   279,8
251,1   379,8
251,1   479,8
251,1   579,8
251,1   679,8
251,1   779,8
251,1   879,8
251,1   979,8
251,1   1079,8
251,1   1179,8
251,1   1279,8
251,1   1379,8
251,1   1479,8
351,1   79,8
351,1   179,8
351,1   279,8
351,1   379,8
351,1   479,8
351,1   579,8
351,1   679,8
351,1   779,8
351,1   879,8
351,1   979,8
351,1   1079,8
351,1   1179,8
351,1   1279,8
351,1   1379,8
351,1   1479,8
451,1   79,8
451,1   179,8
451,1   279,8
451,1   379,8
451,1   479,8
451,1   579,8
451,1   679,8
451,1   779,8
451,1   879,8
451,1   979,8
451,1   1079,8
451,1   1179,8
451,1   1279,8
451,1   1379,8
451,1   1479,8
551,1   79,8
551,1   179,8
551,1   279,8
551,1   379,8
551,1   479,8
551,1   579,8
551,1   679,8
551,1   779,8
551,1   879,8
551,1   979,8
551,1   1079,8
551,1   1179,8
551,1   1279,8
551,1   1379,8
551,1   1479,8
651,1   79,8
651,1   179,8
651,1   279,8
651,1   379,8
651,1   479,8
651,1   579,8
651,1   679,8
651,1   779,8
651,1   879,8
651,1   979,8
651,1   1079,8
651,1   1179,8
651,1   1279,8
651,1   1379,8
651,1   1479,8
751,1   79,8
751,1   179,8
751,1   279,8
751,1   379,8
751,1   479,8
751,1   579,8
751,1   679,8
751,1   779,8
751,1   879,8
751,1   979,8
751,1   1079,8
751,1   1179,8
751,1   1279,8
751,1   1379,8
751,1   1479,8
851,1   79,8
851,1   179,8
851,1   279,8
851,1   379,8
851,1   479,8
851,1   579,8
851,1   679,8
851,1   779,8
851,1   879,8
851,1   979,8
851,1   1079,8
851,1   1179,8
851,1   1279,8
851,1   1379,8
851,1   1479,8
951,1   79,8
951,1   179,8
951,1   279,8
951,1   379,8
951,1   479,8
951,1   579,8
951,1   679,8
951,1   779,8
951,1   879,8
951,1   979,8
951,1   1079,8
951,1   1179,8
951,1   1279,8
951,1   1379,8
951,1   1479,8
1051,1  79,8
1051,1  179,8
1051,1  279,8
1051,1  379,8
1051,1  479,8
1051,1  579,8
1051,1  679,8
1051,1  779,8
1051,1  879,8
1051,1  979,8
1051,1  1079,8
1051,1  1179,8
1051,1  1279,8
1051,1  1379,8
1051,1  1479,8
1151,1  79,8
1151,1  179,8
1151,1  279,8
1151,1  379,8
1151,1  479,8
1151,1  579,8
1151,1  679,8
1151,1  779,8
1151,1  879,8
1151,1  979,8
1151,1  1079,8
1151,1  1179,8
1151,1  1279,8
1151,1  1379,8
1151,1  1479,8

Answer 1

Алгоритм, использующий преобразования изображений и кластеризацию

---

Я разработал небольшой алгоритм, использующий преобразования изображений и некоторую статистику для обнаружения ваших кругов.Давайте посмотрим, соответствует ли это вашему ожиданию ошибки.
Подойдет любая хорошая библиотека изображений и статистики, я реализовал ее с помощью Mathematica.

Выполните следующим образом:

1. Импортируйте свое изображение и выполните преобразование Bottom Hat

Мы начинаем пытаться изолировать круги.Помогает Bottom Hat Transform с ядром Box Matrix.Практически любая библиотека изображений поставляется с уже реализованным алгоритмом.

a = Import@"http://i.stack.imgur.com/hiSjj.png";   
b = BottomHatTransform[Binarize@a, BoxMatrix[30]]  

В результате получается

2. Запустите преобразование мисс попадания, чтобы выделить круги

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

c = Binarize@HitMissTransform[b, DiskMatrix[20]]

Результат:

И наши круги уже изолированы и сведены к центральному ядру.

3. Получить только белые пиксели из изображения

Это шаг, зависящий от реализации, поэтому я не буду комментировать этот.

ttflat = Flatten[Table[{i, j, ImageData[c][[i, j]]}, {i, 1232}, {j, 1624}], 1];  
ttfilter = Select[ttflat, #[[3]] == 1 &];  

Давайте посмотрим, сколько пикселейосталось

Dimensions@ttfilter  
{3684, 3}   

Так что осталось 3684 пикселя, почти 82 на круг.Достаточно сделать немного статистики.

3. Используйте кластерный анализ, чтобы выбрать каждый кружок

Кластерный анализ может быть излишним, но, как я уже реализовал, его проще использовать, чем программныйчто-то новое :).Вы можете сделать свой собственный или использовать библиотеку статистики.

ttc = FindClusters[ttfilter, 45, Method -> {"Agglomerate", "Linkage" -> "Complete"}];

Поскольку наши кластеры уже найдены, давайте найдем среднее значение для x и y в каждом кластере.Это центры окружностей:

means = N[Mean /@ ttc, 5]  

В результате получается список из 45 координат, таких как:

{{161.67, 1180.1}, {162.75, 1108.9}, 
 {164.11, 1037.6}, {165.47, 966.19} .....  

Мы почти закончили.

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

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

HTH!

Редактировать

Я сравнил результаты из вашей таблицы с моими результатами.

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

Сформируйте график ниже, вы можете увидеть, что линия "M" у подходит лучше, чем наша "Y".Но это при условии, что круги выровнены ...

Edit 2

Это расчетные координаты для первых 45 кругов вваше второе изображение.У меня систематическое смещение в 1 пиксель.Вероятно, из-за некоторых манипуляций с изображениями, которые я сделал, но это легко исправить :) ... просто вычел один пиксель по X и Y ...

{{51.135, 79.692}, {51.135, 179.69}, {51.135, 279.69},{51.135, 379.69}, {51.135, 479.69},
 {51.135, 579.69}, {51.135, 679.69}, {51.135, 779.69},{51.135, 879.69}, {51.135, 979.69}, 
 {51.135, 1079.7}, {51.135, 1179.7}, {51.135, 1279.7},{51.135, 1379.7}, {51.135, 1479.7}, 
 {151.13, 79.692}, {151.13, 179.69}, {151.13, 279.69},{151.13, 379.69}, {151.13, 479.69},
 {151.13, 579.69}, {151.13, 679.69}, {151.13, 779.69},{151.13, 879.69}, {151.13, 979.69}, 
 {151.13, 1079.7}, {151.13, 1179.7}, {151.13, 1279.7},{151.13, 1379.7}, {151.13, 1479.7}, 
 {251.13, 79.692}, {251.13, 179.69}, {251.13, 279.69},{251.13, 379.69}, {251.13, 479.69}, 
 {251.13, 579.69}, {251.13, 679.69}, {251.13, 779.69},{251.13, 879.69}, {251.13, 979.69}, 
 {251.13, 1079.7}, {251.13, 1179.7}, {251.13, 1279.7},{251.13, 1379.7}, {251.13, 1479.7}}

И это изображение:

Answer 2

Чтобы найти центры окружностей с субпиксельной точностью, если радиус окружности известен (и постоянен), я использую этот подход:

1. Сделайте снимок одним кружком (обозначается как маркер ниже). Его радиус должен совпадать с радиусом окружностей, которые вы хотите найти.
2. Обнаружение краев (величина градиента Собеля, затем некоторый порог для удаления краев низкой интенсивности) как в тестовом изображении, так и в отраженном маркерном изображении. На этой стадии я не применяю прореживание краев и не определяю точные точки на краях.
3. Перекрестные края тестового изображения с краями перевернутого маркера. Вы получаете некоторые пики, где расположены центры.
4. Найти центры пиков с субпиксельной точностью. Центр масс или примерка двумерного гауссова колокола могут хорошо работать.
5. Добавьте сдвиги, которые соответствуют известной позиции центра круга в маркере.

В противном случае, если точки на окружности известны с достаточной точностью, подгонка по методу наименьших средних квадратов должна решить проблему нахождения центра (см. Ответ @ nikie).

Answer 3

Взгляните на Преобразование Хафа . Может использоваться для обнаружения кругов .

Answer 4

«Наилучшее» зависит от вида шума во входных данных.Проблема тривиальна, если в исходных точках данных нет шума: просто выберите 3 точки и вычислите окружность.

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

(x - xm)^2 + (y - ym)^2 = r^2

, где xm, ym, r неизвестны, поэтому:

x^2 - 2*x*xm + xm^2 + y^2 - 2*y*ym + ym^2 = r^2

заменить c на r^2-xm^2-ym^2 и у вас есть переопределенная система линейных уравнений:

2*x*xm + 2*y*ym = c - x^2 - y^2

Любая хорошая библиотека линейной алгебры (например, IPP) может решить эту проблему за вас.

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

Answer 5

OpenCV 2.4.6.0 имеет функцию findCirclesGrid для поиска центров окружностей в сетке.