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

Ответ 1

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

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

Выполните следующие действия:

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

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

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

Результат

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

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

c = [email protected][b, DiskMatrix[20]]

Результат:

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

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

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

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

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

[email protected]  
{3684, 3}   

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

3. Используйте Cluster Analysis для выбора каждого круга

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

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} .....  

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

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

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

НТН!

Изменить

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

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

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

Изменить 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}}

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

Ответ 2

"Лучшее" зависит от типа шума во входных данных. Проблема тривиальна, если в исходных точках данных нет шума: просто выберите 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 для поиска множества точек, не относящихся к outlier, а затем использовать алгоритм выше, чтобы найти точный центр для этого набора.

Ответ 3

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

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

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

Ответ 4

Посмотрите Преобразование Hough. Его можно использовать для обнаружения кругов.

Ответ 5

OpenCV 2.4.6.0 имеет findCirclesGrid функцию, чтобы найти центры кругов в сетке.