Рандомизированное преобразование Хафа

Преобразования Хафа — это методы обнаружения объектов , критический шаг во многих реализациях компьютерного зрения или интеллектуального анализа данных из изображений. В частности, рандомизированное преобразование Хафа является вероятностным вариантом классического преобразования Хафа и обычно используется для обнаружения кривых (прямая линия, круг, эллипс и т. д.). Основная идея преобразования Хафа (HT) заключается в реализации процедуры голосования для всех потенциальных кривых на изображении, и по завершении работы алгоритма кривые , которые действительно существуют в изображении, будут иметь относительно высокие оценки голосования. Рандомизированное преобразование Хафа (RHT) отличается от HT тем, что оно пытается избежать проведения дорогостоящего процесса голосования для каждого ненулевого пикселя изображения, используя преимущества геометрических свойств аналитических кривых, и, таким образом, повысить эффективность использования времени и уменьшить объем памяти. Требования исходного алгоритма.

Мотивация

Хотя преобразование Хафа (HT) широко используется при обнаружении кривых , оно имеет два основных недостатка: Во-первых, для каждого ненулевого пикселя изображения в ходе процедуры голосования накапливаются параметры как существующей кривой, так и избыточных. Во-вторых, массив аккумуляторов (или пространство Хафа) предопределен эвристическим способом. Чем выше необходимая точность, тем выше должно быть разрешение параметра. Эти две потребности обычно приводят к большим требованиям к памяти и низкой скорости для реальных приложений. Поэтому для решения этой проблемы был создан RHT.

Выполнение

По сравнению с HT, RHT использует тот факт, что некоторые аналитические кривые могут быть полностью определены определенным количеством точек на кривой. Например, прямая линия может быть определена двумя точками, а эллипс (или окружность) – тремя точками. Случай обнаружения эллипса можно использовать для иллюстрации основной идеи RHT. Весь процесс обычно состоит из трех этапов:

1. Сопоставьте эллипсы со случайно выбранными точками.
2. Обновите массив аккумуляторов и соответствующие оценки.
3. Выведите эллипсы с оценками выше некоторого заранее определенного порога.

Эллипс фитинг

Одно общее уравнение для определения эллипсов : $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$

с ограничением: $ac-b^{2}>0$

Однако эллипс можно полностью определить, если знать три его точки и касательные к этим точкам.

RHT начинается со случайного выбора трех точек на эллипсе. Пусть они будут $X_{1}$, $X_{2}$ и $X_{3}$. Первый шаг — найти касательные этих трех точек. Их можно найти, проведя прямую линию методом наименьших квадратов для небольшого окна соседних пикселей.

Следующий шаг – найти точки пересечения касательных линий. Это можно легко сделать, решив линейные уравнения, найденные на предыдущем шаге. Тогда пусть точки пересечения будут $T_{12}$ и Т $T_{23}$, середины отрезков $X_{1}X_{2}$ и $X_{2}X_{3}$ быть $M_{12}$ и $M_{23}$. Тогда центр эллипса будет лежать на пересечении $T_{12}M_{12}$ и $T_{23}M_{23}$. Опять же, координаты точки пересечения могут быть определены путем решения уравнений линий, и подробный процесс здесь опущен для краткости.

Пусть координаты центра эллипса, найденные на предыдущем шаге, будут $(x_{0},y_{0})$. Тогда центр можно перевести в начало координат с помощью $x'=x-x_{0}$ и $y'=y-y_{0}$ так что уравнение эллипса можно упростить до:

$ax'^{2}+2bx'y'+cy'^{2}=1$

Теперь мы можем определить остальные параметры эллипса: $a$, $b$ и $c$ заменив координаты $X_{1}$, $X_{2}$ и $X_{3}$ в уравнение выше.

Накопление

Используя параметры эллипса, определенные на предыдущем этапе, массив аккумуляторов можно соответствующим образом обновить. В отличие от классического преобразования Хафа, RHT не сохраняет «сетку сегментов» в качестве массива аккумуляторов. Скорее, он сначала вычисляет сходство между вновь обнаруженным эллипсом и эллипсом, уже сохраненным в массиве аккумуляторов. Для расчета сходства можно использовать различные метрики. Если сходство превышает некоторый заранее определенный порог, замените значение в аккумуляторе средним значением обоих эллипсов и прибавьте 1 к его баллу. В противном случае инициализируйте этот эллипс пустой позицией в аккумуляторе и присвойте ему оценку 1.

Прекращение действия

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

Псевдокод для RHT:

while (we find ellipses AND not reached the maximum epoch) {
    for (a fixed number of iterations) {
        Find a potential ellipse.
        if (the ellipse is similar to an ellipse in the accumulator) then
            Replace the one in the accumulator with the average of two ellipses and add 1 to the score;
        else
            Insert the ellipse into an empty position in the accumulator with a score of 1;
    }
    Select the ellipse with the best score and save it in a best ellipse table;
    Eliminate the pixels of the best ellipse from the image;
    Empty the accumulator;
}