Преобразование Круга Хафа - Circle Hough Transform

В круг Преобразование Хафа (CHT) является основным извлечение признаков техника, используемая в цифровая обработка изображений для обнаружения кругов на несовершенных изображениях. Кандидаты в кружки создаются путем «голосования» в пространстве параметров Хафа и последующего выбора локальных максимумов в матрице аккумулятора.

Это специализация Преобразование Хафа.

Теория

В двухмерном пространстве круг можно описать следующим образом:

{ Displaystyle влево (х-а вправо) ^ {2} + влево (у-б вправо) ^ {2} = г ^ {2} (1)}

где (a, b) - центр окружности, а r - радиус. Если 2D точка (x, y) зафиксирована, то параметры можно найти согласно (1). Пространство параметров будет трехмерным (a, b, r). И все параметры, которые удовлетворяют (x, y), будут лежать на поверхности перевернутого прямоугольного конуса, вершина которого находится в (x, y, 0). В трехмерном пространстве параметры окружности можно определить по пересечению множества конических поверхностей, которые определяются точками на двумерном круге. Этот процесс можно разделить на два этапа. Первый этап - это фиксация радиуса, а затем поиск оптимального центра окружностей в двухмерном пространстве параметров. Второй этап - найти оптимальный радиус в одномерном пространстве параметров.

Найти параметры с известным радиусом R

Если радиус фиксирован, то пространство параметров будет уменьшено до 2D (положение центра круга). Для каждой точки (x, y) на исходной окружности он может определить окружность с центром в (x, y) и радиусом R согласно (1). Точка пересечения всех таких кругов в пространстве параметров будет соответствовать центральной точке исходной окружности.

Рассмотрим 4 точки на круге на исходном изображении (слева). Круговое преобразование Хафа показано справа. Обратите внимание, что радиус считается известным. Для каждой (x, y) из четырех точек (белых точек) в исходном изображении он может определять круг в пространстве параметров Хафа с центром в (x, y) с радиусом r . Матрица аккумулятора используется для отслеживания точки пересечения. В пространстве параметров количество точек голосования, через которые проходит круг, будет увеличено на единицу. Затем можно найти точку локального максимума (красная точка в центре на правом рисунке). Положение (a, b) максимумов будет центром исходного круга.

Несколько кругов с известным радиусом R

С помощью одной и той же техники можно найти несколько кругов с одинаковым радиусом.

Обратите внимание, что в аккумуляторной матрице (правый рис.) Должно быть не менее 3 точек локальных максимумов.

Матрица аккумуляторов и голосование

На практике для нахождения точки пересечения в пространстве параметров вводится аккумуляторная матрица. Во-первых, нам нужно разделить пространство параметров на «сегменты» с помощью сетки и создать матрицу аккумуляторов в соответствии с сеткой. Элемент в аккумуляторной матрице обозначает количество «кружков» в пространстве параметров, которые проходят через соответствующую ячейку сетки в пространстве параметров. Номер также называется «номером для голосования». Изначально каждый элемент в матрице нули. Затем для каждой «граничной» точки в исходном пространстве мы можем сформулировать круг в пространстве параметров и увеличить число голосов ячейки сетки, через которую проходит круг. Этот процесс называется «голосованием».

После голосования мы можем найти локальные максимумы в матрице аккумулятора. Положения локальных максимумов соответствуют центрам окружностей в исходном пространстве.

Найти параметр круга с неизвестным радиусом

Поскольку пространство параметров является трехмерным, матрица аккумулятора также будет трехмерной. Мы можем перебирать возможные радиусы; для каждого радиуса мы используем предыдущую технику. Наконец, найдите локальные максимумы в трехмерной матрице аккумулятора. Массив аккумулятора должен быть A [x, y, r] в трехмерном пространстве. Голосование должно быть за каждый пиксель, радиус и тета A [x, y, r] + = 1

Алгоритм:

Для каждого A [a, b, r] = 0;
Обработать алгоритм фильтрации изображения Gaussian Blurring, преобразовать изображение в оттенки серого (grayScaling), сделать Хитрый оператор, Оператор Кэнни дает края изображения.
Проголосуйте все возможные кружки в аккумуляторе.
Локальные круги с максимальным количеством голосов для Аккумулятора А дают кругу пространство Хафа.
Максимально проголосованный круг Аккумулятора дает круг.

Повышение квалификации лучшего кандидата:

 Для каждого A [a, b, r] = 0; // сначала заполняем нулями, создаем экземпляр 3D-матрицы Для каждой ячейки (x, y) Для каждого тета t = от 0 до 360 // возможные тета от 0 до 360 b = y - r * sin (t * PI / 180); // полярная координата центра (преобразовать в радианы) a = x - r * cos (t * PI / 180); // полярные координаты центра (преобразовать в радианы) A [a, b, r] + = 1; // голосование конец конец конец

Примеры

Найдите круги в отпечатке обуви

Исходное изображение (справа) сначала преобразуется в двоичное изображение (слева) с помощью порогового значения и фильтра Гаусса. Затем из него находятся ребра (середина), используя хитрое обнаружение края. После этого все граничные точки используются преобразованием Хафа круга для нахождения основной структуры круга.

Ограничения

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

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

Кроме того, CHT не очень устойчив к шуму.

Расширения

Адаптивное преобразование Хафа

Дж. Иллингворт и Дж. Киттлер ^[1] представил этот метод для эффективной реализации преобразования Хафа. AHT использует небольшой массив аккумуляторов и идею гибкой итеративной стратегии накопления и поиска «от грубого к точному» для выявления значимых пиков в пространствах параметров Хафа. Этот метод существенно превосходит стандартную реализацию преобразования Хафа как с точки зрения хранения, так и с точки зрения вычислительных требований.

Заявление

Подсчет людей

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

Обнаружение аневризмы головного мозга

Модифицированное преобразование круга Хафа (MHCT) используется на изображении, извлеченном из цифровой субтракционной ангиограммы (DSA), для обнаружения и классификации типа аневризмы.

^[3]