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

Этот пример использует:

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

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

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

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

Введение

Система CornerDetectionHDL.slx показана ниже. Подсистема HDL Corner Algorithm содержит блок Corner Detector с набором параметров Method, чтобы 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}$

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

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

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

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

Следующим шагом является применение кругового окна к трем компонентам с помощью трех Фильтров Изображений с Гауссовыми коэффициентами. Коэффициенты квантуются до 18-битных беззнаковых чисел, чтобы соответствовать умножителям FPGA. Чтобы найти лучшую точность дроби для коэффициентов, создайте число с фиксированной точкой с помощью функции fi (), но только задавая длину слова. В этом случае дробное масштабирование 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, является частью между блоками Frame To Pixels и Pixels To Frame. Это подсистема, называемая HDL Corner Algorithm, которая включает все элементы алгоритма обнаружения углов, увиденного выше. Остальная часть модели, включая Behavioral Corner Algorithm и источники и раковины, образует наш испытательный стенд Simulink.

Дальнейший переход

Алгоритм Харриса и Стивенса основан на аппроксимации собственных значений матрицы Харриса, как показано выше. Алгоритм Харриса использует $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)}$

Для реализации ПЛИС важно отметить повторное значение. $\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}}
\right)^2$

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

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

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

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

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

Ссылки

[1] С. Харрис и М. Стивенс (1988). Комбинированный угловой и краевой детектор. Материалы четвертой конференции «Alvey Vision». с. 147-151.

Документация