Обнаружение угла Харриса

В этом примере используются:

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

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

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

В этом примере модели представлен аппаратно совместимый алгоритм. Вы можете осуществить этот алгоритм на правлении, использующем справочный дизайн Xilinx™ Zynq™. См. раздел Обнаружение углов и наложение изображений с аппаратным обеспечением на основе Zynq (пакет поддержки панели инструментов Vision HDL для аппаратного обеспечения на основе Xilinx Zynq).

Введение

Ниже показана система CorureDetenseHDL.slx. Подсистема алгоритма углов HDL содержит блок детектора углов с параметром Method, равным Harris.

Первый шаг: поиск градиентов

Первым шагом в алгоритме Харриса является поиск рёбер на изображении. Блок «Детектор углов» использует два фильтра градиентного изображения с коэффициентами $\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

Результаты моделирования

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

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

Создание кода HDL

Для проверки и генерации кода HDL, на который ссылается этот пример, необходимо иметь лицензию HDL Coder™.

Для создания кода HDL используется следующая команда.

makehdl('CornerDetectionHDL/HDL Corner Algorithm')

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

makehdltb('CornerDetectionHDL/HDL Corner Algorithm')

Часть этой модели, которую можно реализовать в FPGA, является частью между блоками «От кадра до пикселей» и «От пикселей до кадра». Это подсистема под названием HDL 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)}$

Для реализации 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}}
\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$ метрикой Харриса показывает, как работает аппроксимация Харриса. Если переупорядочить члены под квадратным корнем и поменять местами знаки так, чтобы результат был больше или равен предопределенному порогу, то получится по существу метрика Харриса с некоторым масштабированием.

Ссылки

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

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