Детектирование углов методом Харриса

В этом примере показано, как использовать обнаружение ребра в качестве первого шага в угловом обнаружении. Алгоритм подходит для FPGAs.

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

Угол интуитивно задан как пересечение двух ребер. Этот пример использует алгоритм Harris & Stephens [1], в котором расчет упрощен с помощью приближения собственных значений матрицы Харриса. Для другого углового алгоритма обнаружения для FPGAs смотрите пример Детектирования углов методом FAST.

Эта модель в качестве примера предоставляет аппаратно-совместимый алгоритм. Можно реализовать этот алгоритм на плате с помощью исходного проекта Xilinx™ Zynq™. Смотрите Угловое Наложение Обнаружения и Изображения с Находящимся в Zynq Оборудованием (Пакет поддержки Vision HDL Toolbox для Xilinx Находящееся в Zynq Оборудование).

Введение

Систему CornerDetectionHDL.slx показывают ниже. Угловая подсистема Алгоритма HDL содержит блок Corner Detector с набором параметров Метода к Harris.

Первый шаг: найдите градиенты

Первый шаг в алгоритме Харриса должен найти ребра в изображении. Блок Corner Detector использует два фильтра градиента изображений с коэффициентами$\left[ \begin{array}{ccc} {1}&{0}&{- 1} \end{array} \right]$ и$\left[ \begin{array}{c} {1}\\{0}\\{- 1} \end{array} \right]$ произвести градиенты$G_x$ и$G_y$. Квадрат и перекрестный умножается, чтобы сформироваться$G_x^2$,$G_y^2$ и$G_{xy}$.

Второй шаг: круговая фильтрация

Второй шаг алгоритма должен выполнить Гауссову фильтрацию к среднему значению$G_x^2$,$G_y^2$ и$G_{xy}$ по круговому окну. Размер кругового окна определяет шкалу обнаруженного угла. Блок использует 5x5 окно. Для трех компонентов блок использует три фильтра с теми же коэффициентами фильтра.

Последний шаг: сформируйте матрицу Харриса

Последний шаг алгоритма должен оценить собственное значение матрицы Харриса. Матрица Харриса является симметрической матрицей, похожей на ковариационную матрицу. Основная диагональ состоит из двух средних значений градиентов, в квадрате$\langle G_x^2 \rangle$ и$\langle G_y^2 \rangle$. От диагональных элементов средние значения векторного произведения градиента$\langle G_{xy} \rangle$. Матрица Харриса:

$$A_{Harris} = \left[ {\begin{array}{*{20}{c}}{\langle G_x^2
\rangle}&{\langle G_{xy} \rangle}\\{\langle G_{xy} \rangle}&{\langle
G_y^2 \rangle}\end{array}} \right]$$

Вычислите ответ из матрицы Харриса

Ключевое упрощение алгоритма Харриса оценивает собственные значения матрицы Харриса, когда определитель минус масштабированная трассировка придал квадратную форму.

$R = det(A_{Harris}) - k \cdot Tr^2(A_{Harris})$ где$k$ обычно константа 0.04.

Угловой метрический ответ$R$, описанное использование градиентов:

$$ R = \left( {\langle G_x^2 \rangle} \cdot {\langle G_y^2 \rangle} -
{\langle G_{xy} \rangle}^2 \right) - k \cdot \left( {\langle G_x^2
\rangle} + {\langle G_y^2 \rangle} \right)^2 $$

Когда ответ больше, чем предопределенный порог, угол обнаруживается:

$$ R \quad > \quad k_{thresh} $$

$$ \left( {\langle G_x^2 \rangle} \cdot {\langle G_y^2 \rangle} -
{\langle G_{xy} \rangle}^2 \right) - k \cdot \left( {\langle G_x^2
\rangle} + {\langle G_y^2 \rangle} \right)^2 \quad > \quad k_{thresh} $$

Настройки фиксированной точки

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

Поток входного пикселя является 8-битными полутоновыми пиксельными данными. Вычисление градиентов не добавляет много роста разрядности, поскольку ядро фильтра имеет только +1 и-1 коэффициент. Результатом является полная точность 9-битная фиксированная точка со знаком.

Обработка на квадрат и перекрестное умножение градиентов приводят к подписанным 18-битным результатам, все еще в полной точности. Много общих множителей FPGA имеют 18-битный или 20-битный вход wordlengths, таким образом, необходимо будет квантовать на следующем шаге.

Следующий шаг должен применить круговое окно к этим трем компонентам с помощью трех Фильтров Изображений с Гауссовыми коэффициентами. Коэффициенты квантуются к 18-битным числам без знака, чтобы соответствовать множителям FPGA. Чтобы найти лучшую дробную точность для коэффициентов, создайте номер фиксированной точки с помощью fi () функция, но только задав wordlength. В этом случае дробное масштабирование 21 бита является лучшим, поскольку самое большое значение в матрице коэффициентов между 1/8 и 1/16.

coeffs = fi(fspecial('gaussian',[5,5],1.5),0,18)
coeffs = 

    0.0144    0.0281    0.0351    0.0281    0.0144
    0.0281    0.0547    0.0683    0.0547    0.0281
    0.0351    0.0683    0.0853    0.0683    0.0351
    0.0281    0.0547    0.0683    0.0547    0.0281
    0.0144    0.0281    0.0351    0.0281    0.0144

          DataTypeMode: Fixed-point: binary point scaling
            Signedness: Unsigned
            WordLength: 18
        FractionLength: 21

Результаты симуляции

Вы видите, что получившиеся изображения от симуляции очень похожи, но не точно то же самое. Небольшие различия в результатах симуляции - то, потому что поведенческая модель использует целочисленные арифметические правила C, и квантование отличается от готового к HDL углового блока обнаружения.

Используя Simulink, можно изучить эти различия и решить, допустимы ли ошибки для приложения. Если они не приемлемы, можно увеличить битные ширины операторов, несмотря на то, что это увеличивает область, используемую в FPGA.

Генерация HDL-кода

Проверять и сгенерировать HDL-код сослались в этом примере, у вас должна быть лицензия HDL Coder™.

Чтобы сгенерировать HDL-код, используйте следующую команду.

makehdl('CornerDetectionHDL/HDL Corner Algorithm')

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

makehdltb('CornerDetectionHDL/HDL Corner Algorithm')

Часть этой модели, которую можно реализовать на FPGA, является частью между Системой координат К Пикселям и Пикселями, Чтобы Структурировать блоки. Это - названный Угловой Алгоритм HDL подсистемы, который включает все элементы углового алгоритма обнаружения, замеченного выше. Остальная часть модели, включая Поведенческий Угловой Алгоритм и источники и приемники, формирует наш испытательный стенд Simulink.

Движение далее

Алгоритм Harris & Stephens основан на аппроксимации собственных значений матрицы Харриса как показано выше. Алгоритм Харриса использует$R = det(A_{Harris}) - k \cdot Tr^2(A_{Harris})$ в качестве метрики, избегая любого деления или операций квадратного корня. Другой способ сделать угловое обнаружение состоит в том, чтобы вычислить фактические собственные значения.

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

$$ \lambda_1 = \frac{Tr(A)}{2} + \sqrt{\frac{Tr^2(A)}{4}-det(A)} $$

$$ \lambda_2 = \frac{Tr(A)}{2} - \sqrt{\frac{Tr^2(A)}{4}-det(A)} $$

При замене в наших$A_Harris$ значениях мы добираемся:

$$ \lambda_1 = \left( \frac{{\langle G_x^2 \rangle} + {\langle G_y^2
\rangle}}{2} \right) + \sqrt{ \left( {\frac{{\langle G_x^2 \rangle} +
{\langle G_y^2 \rangle}}{2}} \right)^2 - \left( {\langle G_x^2
\rangle} \cdot {\langle G_y^2 \rangle} - {\langle G_{xy} \rangle}^2
\right)} $$

$$ \lambda_2 = \left( \frac{{\langle G_x^2 \rangle} + {\langle G_y^2
\rangle}}{2} \right) - \sqrt{ \left( {\frac{{\langle G_x^2 \rangle} +
{\langle G_y^2 \rangle}}{2}} \right)^2 - \left( {\langle G_x^2
\rangle} \cdot {\langle G_y^2 \rangle} - {\langle G_{xy} \rangle}^2
\right)} $$

Для реализации FPGA важно заметить повторное значение$\frac{Tr(A)}{2}$. Мы можем вычислить это значение однажды и затем квадрат, чтобы объединиться с$det(A)$. Это означает, что алгоритм собственного значения требует только двух множителей, но за счет большего количества сумматоров и вычитающих устройств и функции квадратного корня, которая требует нескольких множителей самостоятельно.

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

$$ \lambda_1, \lambda_2 \quad > \quad k_{minimum} $$

$$ \lambda_1 - \lambda_2 \quad < \quad k_{thresh} $$

$$ 2 \sqrt{\frac{Tr^2(A)}{4}-det(A)} \quad < \quad k_{thresh} $$

$$ \frac{Tr^2(A)}{4}-det(A) \quad < \quad \left( {\frac{k_{thresh}}{2}}&#xA;\right)^2 $$

Можно перестроить это так, чтобы это было очень похоже на метрику Харриса$R$ выше:

$$ det(A) - \frac{Tr^2(A)}{4} \quad \geq \quad \left( {\frac{k_{thresh}}{2}}&#xA;\right)^2 $$

Расширение матрицы дает:

$$ \left( {\langle G_x^2 \rangle} \cdot {\langle G_y^2 \rangle} - {\langle&#xA;G_{xy} \rangle}^2 \right) - \left( {\frac{{\langle G_x^2 \rangle} + {\langle&#xA;G_y^2 \rangle}}{2}} \right)^2 \quad \geq \quad \left( {\frac{k_{thresh}}{2}}&#xA;\right)^2 $$

Подобие между различием собственных значений и$R$ метрикой Харриса показывает, как приближение Харриса работает. Если вы перестраиваете термины под квадратным корнем и подкачиваете знаки, таким образом, результат должен быть больше или равен предопределенному порогу, вы прибываете в по существу метрику Харриса с некоторым масштабированием.

Ссылки

[1] К. Харрис и М. Стивенс (1988). "Объединенный угол и детектор ребра". Продолжения 4-й Конференции по Видению Alvey. стр 147-151.

Для просмотра документации необходимо авторизоваться на сайте