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

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

В этом примере показано, как использовать обнаружение ребра в качестве первого шага в угловом обнаружении. Алгоритм подходит для 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}}
\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). "Объединенный угол и детектор ребра". Продолжения 4-й Конференции по Видению Alvey. стр 147-151.

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