Определение количества кругов в двоичном входном изображении
В этом посте я хотел бы упомянуть о том, как определять круги, а также об общем количестве кругов во входном изображении. Мой алгоритм принимает двоичное изображение в качестве входных данных, но довольно легко преобразовать любое входное изображение в двоичный формат, используя существующие библиотеки. Так что я просто пропускаю эту часть. И в качестве этапа предварительной обработки я конвертирую двоичное изображение в изображение края. Края - это фактически необходимые данные для меня, чтобы обнаружить наличие круглых форм. Вот почему я реализую простую операцию фильтрации по осям x и y, чтобы получить изображение края.
Обнаружение круга широко изучается в литературе как часть области обработки изображений, и к настоящему времени были предложены некоторые полезные методы. Один из этих методов, называемый Hough Circle Transform, широко применяется в сообществе обработки изображений, и мы можем видеть множество различных реализаций с использованием имеющихся библиотек обработки изображений.
Вместо того, чтобы использовать любой доступный инструмент, я хотел бы рассказать, как алгоритм работает под капотом, и простой код Python, который может решить эту задачу за нас.
Логика, лежащая в основе алгоритма Hough Circle Transform, основана на математическом выражении круга в полярной системе координат как:
где,
Нам нужно преобразовать наше двумерное входное изображение края E (x, y) в трехмерную матрицу накопителя (x0, y0, r).
Анализируя матрицу аккумуляторов, мы можем выяснить координаты потенциальных центров окружностей и их соответствующие радиусы. Здесь мы используем простую технику голосования. Основная идея состоит в том, чтобы записывать голоса для каждой возможной координаты круга и искать индексы, которые набирают много голосов.
Для достижения этой задачи мы можем использовать псевдокод ниже:
Apply filtering operation to detect edges PSEUDOCODE for HOUGH CIRCLES METHOD Input a binary edge image E(x,y) Initialize accumulator array A(x0,y0,r) to zeros Dimensions of A : x0 --> rows of E matrix y0 --> columns of E matrix r --> sqrt( power(rows of E matrix,2) + power(columns of E matrix,2) ) for all x: for all y: if E(x,y): for all x0: for all y0: r = sqrt( power((x-x0),2) + power((y-y0),2) ) increment A at (x0,y0,r) end end end end end end Search for the peaks in A(x0,y0,r) - the corresponding indices of A are the parameter of the detected circles.
Чтобы проверить свой алгоритм, я использовал входное изображение с именем binary_circles.tif. Вот входное изображение:
После этапа предварительной обработки нахождения краев я получаю изображение ниже:
Когда мы изучаем входное изображение, мы видим, что средняя длина радиуса кругов составляет около 10 пикселей.
Таким образом, в матрице накопления мы рассматриваем только возможные координаты окружностей (x0, y0) с r = 10
В приведенном выше псевдокоде вместо «для всех x0:» и «для всех y0:» я использовал диапазон «x-15, x + 15» и «y-15, y + 15», где x и y - крайние точки. Поскольку целевой радиус, который я ищу, равен 10, мне не нужно искать радиус, который больше. Таким образом, я добился отличной производительности кода.
Полученный аккумулятор можно использовать для определения количества кругов.
Я закодировал простую функцию find_number_of_circles (Accumulator_Matrix, ratioparameter), которая принимает аргумент как матрицу накопителя и порог и выводит количество кругов.
Наконец, вот результат моего кода:
Как видите, мой код правильно определил количество кругов на входном изображении :)
Я надеюсь, что этот пост будет полезен для вас, чтобы понять теорию, лежащую в основе преобразования Круга Хафа. Код, использованный в этом посте, можно найти в этом репозитории на github: