Детектор аффинных областей Харриса

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

Обзор

Аффинный детектор Харриса может идентифицировать схожие области между изображениями, которые связаны аффинными преобразованиями и имеют различное освещение. Эти аффинно-инвариантные детекторы должны быть способны идентифицировать похожие области на изображениях, снятых с разных точек зрения, которые связаны простым геометрическим преобразованием: масштабированием, вращением и сдвигом. Эти обнаруженные области были названы как инвариантными , так и ковариантными . С одной стороны, области обнаруживаются инвариантно по отношению к преобразованию изображения, но области ковариантно изменяются при преобразовании изображения. Не зацикливайтесь слишком подробно на этих двух соглашениях об именах; Важно понимать, что дизайн этих точек интереса сделает их совместимыми с изображениями, снятыми с нескольких точек зрения. Другие детекторы, которые являются аффинно-инвариантными, включают детектор аффинных областей Гессе , максимально стабильные экстремальные области , детектор заметности Кадира – Брейди , области на основе краев (EBR) и области на основе экстремумов интенсивности (IBR).

Миколайчик и Шмид (2002) впервые описали аффинный детектор Харриса, который используется сегодня в «Аффинно-инвариантном детекторе точек интереса» . Более ранние работы в этом направлении включают использование Линдебергом и Гардингом адаптации аффинной формы для вычисления дескрипторов аффинных инвариантных изображений и, таким образом, уменьшения влияния перспективных деформаций изображения. использование аффинно адаптированных характерных точек для широкого сопоставления базовой линии по Баумбергу и первое использование Линдебергом характерных точек, инвариантных к масштабу; для обзора теоретической основы. Аффинный детектор Харриса основан на сочетании угловых точек, обнаруженных с помощью обнаружения углов Харриса , многомасштабного анализа с использованием пространства гауссовского масштаба и аффинной нормализации с использованием итеративного алгоритма адаптации аффинной формы . Рекурсивный и итеративный алгоритм использует итеративный подход к обнаружению этих областей:

1. Определите начальные точки области с помощью масштабно-инвариантного детектора Харриса-Лапласа .
2. Для каждой начальной точки нормализуйте область, чтобы она была аффинно-инвариантной, используя аффинную адаптацию формы .
3. Итеративно оценить аффинную область: выбрать правильный масштаб интеграции, масштаб дифференциации и пространственно локализовать точки интереса.
4. Обновите аффинную область, используя эти масштабы и пространственные локализации.
5. Повторите шаг 3, если критерий остановки не выполнен.

Описание алгоритма

Детектор Харриса – Лапласа (точки начального региона)

Аффинный детектор Харриса в значительной степени опирается как на меру Харриса, так и на представление пространства в гауссовском масштабе . Поэтому следует краткое рассмотрение обоих. Более полные выводы см. в разделе «Обнаружение углов» и «Пространство гауссовского масштаба» или в связанных с ними статьях.

Угловая мера Харриса

Алгоритм углового детектора Харриса основан на центральном принципе: в углу интенсивность изображения будет сильно меняться в нескольких направлениях. Альтернативно это можно сформулировать, исследуя изменения интенсивности из-за сдвигов в локальном окне. Вокруг угловой точки интенсивность изображения будет сильно меняться при смещении окна в произвольном направлении. Следуя этой интуиции и посредством умного разложения, детектор Харриса использует матрицу второго момента в качестве основы для принятия угловых решений. ( «Обнаружение углов» Более полный вывод см. в разделе ). Матрица $A$, также называется матрицей автокорреляции и имеет значения, тесно связанные с производными интенсивности изображения .

$A(\mathbf {x} )=\sum _{p,q}w(p,q){\begin{bmatrix}I_{x}^{2}(p,q)&I_{x}I_{y}(p,q)\\I_{x}I_{y}(p,q)&I_{y}^{2}(p,q)\\\end{bmatrix}}$

где $I_{x}$ и $I_{y}$ являются соответствующими производными (интенсивности пикселей) в $x$ и $y$ направление в точке ( $p$, $q$); $p$ и $q$ – позиционные параметры весовой функции w. Внедиагональные записи являются продуктом $I_{x}$ и $I_{y}$, а диагональные элементы представляют собой квадраты соответствующих производных . Весовая функция $w(x,y)$ может быть однородным, но чаще всего представляет собой изотропную круговую гауссову зависимость.

$w(x,y)=g(x,y,\sigma )={\frac {1}{2\pi \sigma ^{2}}}e^{\left(-{\frac {x^{2}+y^{2}}{2\sigma ^{2}}}\right)}$

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

Как оказалось, это $A$ Матрица описывает форму меры автокорреляции из-за сдвигов в расположении окна. Таким образом, если мы позволим $\lambda _{1}$ и $\lambda _{2}$ быть собственными значениями $A$, то эти значения дадут количественное описание того, как изменяется мера автокорреляции в пространстве: его основные кривизны. Как отмечают Харрис и Стивенс (1988), $A$ матрица с центром в угловых точках будет иметь два больших положительных собственных значения. Вместо извлечения этих собственных значений с использованием таких методов, как разложение по сингулярным значениям, используется мера Харриса, основанная на следе и определителе:

$R=\det(A)-\alpha \operatorname {trace} ^{2}(A)=\lambda _{1}\lambda _{2}-\alpha (\lambda _{1}+\lambda _{2})^{2}$

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

${\begin{aligned}\{x_{c}\}={\big \{}x_{c}\mid R(x_{c})>R(x_{i}),\forall x_{i}\in W(x_{c}){\big \}},\\R(x_{c})>t_{\text{threshold}}\end{aligned}}$

где $\{x_{c}\}$ являются множеством всех угловых точек, $R(x)$ – мера Харриса, рассчитанная по формуле $x$, $W(x_{c})$ представляет собой множество из 8 соседей с центром в $x_{c}$ и $t_{\text{threshold}}$ является заданным порогом.

8-точечное соседство

Гауссово масштабное пространство

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

$L(\mathbf {x} ,s)=G(s)\otimes I(\mathbf {x} )$

где $G(s)$ представляет собой изотропное круговое ядро ​​Гаусса, определенное выше. Свертка с ядром Гаусса сглаживает изображение, используя окно размером с ядро. Больший масштаб, $s$, соответствует более гладкому результирующему изображению. Миколайчик и Шмид (2001) отмечают, что производные и другие измерения должны быть нормализованы по всем шкалам. Производная порядка $m$, $D_{i_{1},...i_{m}}$, должно быть нормировано множителем $s^{m}$ следующим образом:

$D_{i_{1},\dots ,i_{m}}(\mathbf {x} ,s)=s^{m}L_{i_{1},\dots ,i_{m}}(\mathbf {x} ,s)$

Эти производные или любая произвольная мера могут быть адаптированы к представлению в масштабном пространстве путем рекурсивного вычисления этой меры с использованием набора шкал, где $n$масштаб $s_{n}=k^{n}s_{0}$. См. масштабное пространство для более полного описания.

Объединение детектора Харриса в гауссовском пространстве масштаба

Детектор Харриса-Лапласа сочетает в себе традиционный 2D угловой детектор Харриса с идеей представления пространства в гауссовском масштабе с целью создания масштабно-инвариантного детектора. Угловые точки Харриса являются хорошими отправными точками, поскольку было показано, что они обладают хорошей инвариантностью по вращению и освещению, а также позволяют идентифицировать интересные точки изображения. Однако точки не являются масштабно-инвариантными, и поэтому матрицу второго момента необходимо изменить, чтобы отразить свойство масштабной инвариантности. Обозначим, $M=\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})$ в качестве адаптированной к масштабу матрицы второго момента, используемой в детекторе Харриса – Лапласа.

$M=\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})=\sigma _{D}^{2}g(\sigma _{I})\otimes {\begin{bmatrix}L_{x}^{2}(\mathbf {x} ,\sigma _{D})&L_{x}L_{y}(\mathbf {x} ,\sigma _{D})\\L_{x}L_{y}(\mathbf {x} ,\sigma _{D})&L_{y}^{2}(\mathbf {x} ,\sigma _{D})\end{bmatrix}}$

где $g(\sigma _{I})$ это гауссово ядро ​​масштаба $\sigma _{I}$ и $\mathbf {x} =(x,y)$. Подобно пространству гауссова масштаба, $L(\mathbf {x} )$ — изображение, сглаженное по Гауссу. $\mathbf {\otimes }$ оператор обозначает свертку. $L_{x}(\mathbf {x} ,\sigma _{D})$ и $L_{y}(\mathbf {x} ,\sigma _{D})$ — это производные в соответствующем направлении, примененные к сглаженному изображению и рассчитанные с использованием ядра Гаусса со шкалой $\sigma _{D}$. С точки зрения нашей гауссовой модели масштабного пространства, $\sigma _{I}$ Параметр определяет текущий масштаб, при котором обнаруживаются угловые точки Харриса.

, основанный на этой адаптированной к масштабу матрице второго момента, Детектор Харриса-Лапласа представляет собой двойной процесс: применение углового детектора Харриса в нескольких масштабах и автоматический выбор характеристического масштаба .

Многомасштабные угловые точки Харриса

Алгоритм выполняет поиск по фиксированному числу предопределенных масштабов. Этот набор шкал определяется как:

${\sigma _{1}\dots \sigma _{n}}={k^{1}\sigma _{0}\dots k^{n}\sigma _{0}}$

Миколайчик и Шмид (2004) используют $k=1.4$. Для каждого масштаба интеграции $\sigma _{I}$, выбранного из этого множества, соответствующий масштаб дифференцирования выбирается постоянным множителем масштаба интегрирования: $\sigma _{D}=s\sigma _{I}$. Миколайчик и Шмид (2004) использовали $s=0.7$. Используя эти шкалы, точки интереса обнаруживаются с помощью меры Харриса на $\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})$ матрица. Угловость , как и типичная мера Харриса, определяется как:

${\mathit {cornerness}}=\det(\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}}))-\alpha \operatorname {trace} ^{2}(\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}}))$

Как и в традиционном детекторе Харриса, угловые точки — это те локальные (8-точечные окрестности) максимумы угла , которые превышают заданный порог.

Идентификация характеристической шкалы

Итерационный алгоритм, основанный на Линдеберге (1998), пространственно локализует угловые точки и выбирает характерный масштаб . Итеративный поиск состоит из трех ключевых шагов, которые выполняются для каждой точки. $\mathbf {x}$ которые изначально были обнаружены в масштабе $\sigma _{I}$ многомасштабным детектором Харриса ( $k$ указывает на $kth$ итерация):

• Выберите масштаб $\sigma _{I}^{(k+1)}$ это максимизирует лапласиан гауссианов (LoG) в заранее определенном диапазоне соседних масштабов. Соседние масштабы обычно выбираются из диапазона, находящегося в пределах окрестности двух масштабных пространств . То есть, если исходные точки были обнаружены с использованием коэффициента масштабирования $1.4$ между последовательными масштабами окрестность в двух масштабных пространствах - это диапазон $t\in [0.7,\dots ,1.4]$. Таким образом, рассмотренные гауссовы шкалы: $\sigma _{I}^{(k+1)}=t\sigma _{I}^{k}$. Измерение LoG определяется как:

$|\operatorname {LoG} (\mathbf {x} ,\sigma _{I})|=\sigma _{I}^{2}\left|L_{xx}(\mathbf {x} ,\sigma _{I})+L_{yy}(\mathbf {x} ,\sigma _{I})\right|$

где $L_{xx}$ и $L_{yy}$ являются вторыми производными в своих направлениях. $\sigma _{I}^{2}$ Коэффициент (как обсуждалось выше в гауссовском масштабном пространстве) используется для нормализации LoG по масштабам и обеспечения сопоставимости этих показателей, что делает максимум значимым. Миколайчик и Шмид (2001) демонстрируют, что мера LoG обеспечивает самый высокий процент правильно обнаруженных угловых точек по сравнению с другими мерами выбора шкалы. Масштаб, который максимизирует эту меру LoG в окрестности двух масштабных пространств, считается характерным масштабом , $\sigma _{I}^{(k+1)}$и используется в последующих итерациях. Если экстремумы или максимумы LoG не найдены, эта точка исключается из будущих поисков.

• Используя характерный масштаб, точки пространственно локализуются. То есть суть $\mathbf {x} ^{(k+1)}$ выбирается таким образом, чтобы максимизировать угловую меру Харриса ( угловую, как определено выше) в локальной окрестности 8×8.
• Критерий остановки : $\sigma _{I}^{(k+1)}==\sigma _{I}^{(k)}$ и $\mathbf {x} ^{(k+1)}==\mathbf {x} ^{(k)}$.

Если критерий остановки не выполняется, то алгоритм повторяется с шага 1, используя новый $k+1$ точки и масштаб. Когда критерий остановки соблюден, найденные точки представляют собой точки, которые максимизируют LoG по масштабам (выбор масштаба) и максимизируют угловую меру Харриса в локальной окрестности (пространственный выбор).

Аффинно-инвариантные точки

Математическая теория

Обнаруженные точки Харриса-Лапласа масштабно-инвариантны и хорошо работают для изотропных областей, которые просматриваются под одним и тем же углом обзора. Чтобы быть инвариантным к произвольным аффинным преобразованиям (и точкам зрения), необходимо пересмотреть математическую основу. Матрица второго момента $\mathbf {\mu }$ определяется в более общем смысле для анизотропных областей:

$\mu (\mathbf {x} ,\Sigma _{I},\Sigma _{D})=\det(\Sigma _{D})g(\Sigma _{I})*(\nabla L(\mathbf {x} ,\Sigma _{D})\nabla L(\mathbf {x} ,\Sigma _{D})^{T})$

где $\Sigma _{I}$ и $\Sigma _{D}$ являются ковариационными матрицами, определяющими масштабы гауссовского ядра дифференцирования и интегрирования. Хотя это может существенно отличаться от матрицы второго момента в детекторе Харриса – Лапласа; на самом деле это идентично. Чем раньше $\mu$ матрица представляла собой 2D-изотропную версию, в которой ковариационные матрицы $\Sigma _{I}$ и $\Sigma _{D}$ были единичные матрицы 2x2, умноженные на коэффициенты $\sigma _{I}$ и $\sigma _{D}$, соответственно. В новой формулировке гауссовы ядра можно рассматривать как многомерные гауссовы распределения, а не как однородное гауссово ядро. Однородное гауссово ядро ​​можно рассматривать как изотропную круглую область. Точно так же более общее гауссово ядро ​​определяет эллипсоид. Фактически, собственные векторы и собственные значения матрицы ковариации определяют вращение и размер эллипсоида. Таким образом, мы легко видим, что это представление позволяет нам полностью определить произвольную эллиптическую аффинную область, по которой мы хотим интегрировать или дифференцировать.

Целью аффинно-инвариантного детектора является выявление областей изображений, которые связаны посредством аффинных преобразований. Таким образом, мы рассматриваем точку $\mathbf {x} _{L}$ и преобразованная точка $\mathbf {x} _{R}=A\mathbf {x} _{L}$, где A — аффинное преобразование. В случае с изображениями оба $\mathbf {x} _{R}$ и $\mathbf {x} _{L}$ жить в $R^{2}$ космос. Матрицы второго момента связаны следующим образом:

${\begin{aligned}\mu (\mathbf {x} _{L},\Sigma _{I,L},\Sigma _{D,L})&{}=A^{T}\mu (\mathbf {x} _{R},\Sigma _{I,R},\Sigma _{D,R})A\\M_{L}&{}=\mu (\mathbf {x} _{L},\Sigma _{I,L},\Sigma _{D,L})\\M_{R}&{}=\mu (\mathbf {x} _{R},\Sigma _{I,R},\Sigma _{D,R})\\M_{L}&{}=A^{T}M_{R}A\\\Sigma _{I,R}&{}=A\Sigma _{I,L}A^{T}{\text{ and }}\Sigma _{D,R}=A\Sigma _{D,L}A^{T}\end{aligned}}$

где $\Sigma _{I,b}$ и $\Sigma _{D,b}$ являются ковариационными матрицами для $b$ эталонный кадр. Если мы продолжим придерживаться этой формулировки и будем применять это

${\begin{aligned}\Sigma _{I,L}=\sigma _{I}M_{L}^{-1}\\\Sigma _{D,L}=\sigma _{D}M_{L}^{-1}\end{aligned}}$

где $\sigma _{I}$ и $\sigma _{D}$ являются скалярными факторами, можно показать, что ковариационные матрицы для связанной точки связаны аналогичным образом:

${\begin{aligned}\Sigma _{I,R}=\sigma _{I}M_{R}^{-1}\\\Sigma _{D,R}=\sigma _{D}M_{R}^{-1}\end{aligned}}$

Требуя, чтобы ковариационные матрицы удовлетворяли этим условиям, возникает несколько замечательных свойств. Одним из этих свойств является то, что квадратный корень матрицы второго момента $M^{\tfrac {1}{2}}$ преобразует исходную анизотропную область в изотропные области, которые связаны просто через чистую матрицу вращения $R$. Эти новые изотропные области можно рассматривать как нормализованную систему отсчета. Следующие уравнения формулируют связь между нормализованными точками $x_{R}^{'}$ и $x_{L}^{'}$:

${\begin{aligned}A=M_{R}^{-{\tfrac {1}{2}}}RM_{L}^{\tfrac {1}{2}}\\x_{R}^{'}=M_{R}^{\tfrac {1}{2}}x_{R}\\x_{L}^{'}=M_{L}^{\tfrac {1}{2}}x_{L}\\x_{L}^{'}=Rx_{R}^{'}\\\end{aligned}}$

Матрицу вращения можно восстановить с помощью градиентных методов, подобных тем, которые используются в дескрипторе SIFT . Как обсуждалось с детектором Харриса, собственные значения и собственные векторы матрицы второго момента, $M=\mu (\mathbf {x} ,\Sigma _{I},\Sigma _{D})$ характеризуют кривизну и форму интенсивностей пикселей. То есть собственный вектор, связанный с наибольшим собственным значением, указывает направление наибольшего изменения, а собственный вектор, связанный с наименьшим собственным значением, определяет направление наименьшего изменения. В двумерном случае собственные векторы и собственные значения определяют эллипс. Для изотропной области эта область должна иметь круглую, а не эллиптическую форму. Это тот случай, когда собственные значения имеют одинаковую величину. Таким образом, мера изотропии вокруг локальной области определяется следующим образом:

${\mathcal {Q}}={\frac {\lambda _{\min }(M)}{\lambda _{\max }(M)}}$

где $\lambda$ обозначают собственные значения. Эта мера имеет диапазон $[0\dots 1]$. Значение $1$ соответствует идеальной изотропии.

Итерационный алгоритм

Используя эту математическую структуру, алгоритм аффинного детектора Харриса итеративно обнаруживает матрицу второго момента, которая преобразует анизотропную область в нормализованную область, в которой изотропная мера достаточно близка к единице. Алгоритм использует эту матрицу адаптации формы , $U$, чтобы преобразовать изображение в нормализованный опорный кадр. В этом нормализованном пространстве параметры точек интереса (пространственное положение, масштаб интегрирования и масштаб дифференцирования) уточняются с использованием методов, аналогичных детектору Харриса – Лапласа. Матрица второго момента вычисляется в этой нормализованной системе отсчета и должна иметь изотропную меру, близкую к единице на последней итерации. Каждый раз $k$На итерации каждая область интереса определяется несколькими параметрами, которые алгоритм должен обнаружить: $U^{(k)}$ матрица, позиция $\mathbf {x} ^{(k)}$, масштаб интегрирования $\sigma _{I}^{(k)}$ и масштаб дифференциации $\sigma _{D}^{(k)}$. Поскольку детектор вычисляет матрицу второго момента в преобразованной области, удобно обозначить эту преобразованную позицию как $\mathbf {x} _{w}^{(k)}$ где $U^{(k)}\mathbf {x} _{w}^{(k)}=\mathbf {x^{(k)}}$.

1. Детектор инициализирует пространство поиска точками, обнаруженными детектором Харриса – Лапласа.

   $U^{(0)}={\mathit {identity}}$ и $\mathbf {x} ^{(0)}$, $\sigma _{D}^{(0)}$, и $\sigma _{I}^{(0)}$ это детектор Харриса – Лапласа.

2. предыдущей итерации Примените матрицу адаптации формы , $U^{(k-1)}$ для создания нормализованной системы отсчета, $U^{(k-1)}\mathbf {x} _{w}^{(k-1)}=\mathbf {x} ^{(k-1)}$. Для первой итерации вы применяете $U^{(0)}$.
3. Выберите масштаб интеграции , $\sigma _{I}^{(k)}$, используя метод, аналогичный детектору Харриса – Лапласа. Масштаб выбирается как масштаб, который максимизирует лапласиан гауссиана (LoG). Пространство поиска шкал находится в пределах двух масштабных пространств от шкалы предыдущей итерации.

   $\sigma _{I}^{(k)}={\underset {\sigma _{I}=t\sigma _{I}^{(k-1)} \atop t\in [0.7,\dots ,1.4]}{\operatorname {argmax} }}\,\sigma _{I}^{2}\det(L_{xx}(\mathbf {x} ,\sigma _{I})+L_{yy}(\mathbf {x} ,\sigma _{I}))$

   Важно отметить, что масштаб интеграции в $U-normalized$ пространство существенно отличается от ненормализованного пространства. Поэтому необходимо искать масштаб интегрирования, а не использовать масштаб в ненормированном пространстве.
4. Выберите шкалу дифференциации , $\sigma _{D}^{(k)}$. Для уменьшения пространства поиска и степеней свободы масштаб дифференцирования считается связанным с масштабом интегрирования через постоянный коэффициент: $\sigma _{D}^{k}=s\sigma _{I}^{k}$. По понятным причинам постоянный коэффициент меньше единицы. Миколайчик и Шмид (2001) отмечают, что слишком маленький коэффициент сделает сглаживание (интеграцию) слишком значительным по сравнению с дифференцированием, а слишком большой коэффициент не позволит интегрированию усреднить ковариационную матрицу. Обычно выбирают $s\in [0.5,0.75]$. Из этого набора выбранный масштаб будет максимизировать изотропную меру ${\mathcal {Q}}={\frac {\lambda _{min}(\mu )}{\lambda _{max}(\mu )}}$.

   $\sigma _{D}^{(k)}={\underset {\sigma _{D}=s\sigma _{I}^{(k)},\;s\in [0.5,\dots ,0.75]}{\operatorname {argmax} }}\,{\frac {\lambda _{\min }(\mu (\mathbf {x} _{w}^{(k)},\sigma _{I}^{k},\sigma _{D}))}{\lambda _{\max }(\mu (\mathbf {x} _{w}^{(k)},\sigma _{I}^{k},\sigma _{D}))}}$

   где $\mu (\mathbf {x} _{w}^{(k)},\sigma _{I}^{k},\sigma _{D})$ — матрица второго момента, оцененная в нормализованной системе отсчета. Этот процесс максимизации приводит к тому, что собственные значения сходятся к одному и тому же значению.
5. Пространственная локализация: выберите точку $\mathbf {x} _{w}^{(k)}$ что максимизирует угловую меру Харриса ( ${\mathit {cornerness}}$) в пределах 8-балльной окрестности вокруг предыдущего $\mathbf {x} _{w}^{(k-1)}$ точка.

   $\mathbf {x} _{w}^{(k)}={\underset {\mathbf {x} _{w}\in W(\mathbf {x} _{w}^{(k-1)})}{\operatorname {argmax} }}\,\det(\mu (\mathbf {x} _{w},\sigma _{I}^{k},\sigma _{D}^{(k)}))-\alpha \operatorname {trace} ^{2}(\mu (\mathbf {x} _{w},\sigma _{I}^{k},\sigma _{D}^{(k)}))$

   где $\mu$ - матрица второго момента, как определено выше. Окно $W(\mathbf {x} _{w}^{(k-1)})$ — это набор 8-ми ближайших соседей точки предыдущей итерации в нормализованной системе координат. Поскольку наша пространственная локализация была выполнена в $U$-нормализованная система отсчета, вновь выбранная точка должна быть преобразована обратно в исходную систему отсчета. Это достигается путем преобразования вектора смещения и добавления его к предыдущей точке:

   $\mathbf {x} ^{(k)}=\mathbf {x} ^{(k-1)}+U^{(k-1)}\cdot (\mathbf {x} _{w}^{(k)}-\mathbf {x} _{w}^{(k-1)})$

6. Как упоминалось выше, квадратный корень матрицы второго момента определяет матрицу преобразования, которая генерирует нормализованную систему координат. Таким образом, нам нужно сохранить эту матрицу: $\mu _{i}^{(k)}=\mu ^{-{\tfrac {1}{2}}}(\mathbf {x} _{w}^{(k)},\sigma _{I}^{(k)},\sigma _{D}^{(k)})$. Матрица преобразования $U$ обновляется: $U^{(k)}=\mu _{i}^{(k)}\cdot U^{(k-1)}$. Чтобы гарантировать правильную выборку изображения и расширение изображения в направлении наименьшего изменения (наименьшее собственное значение), мы фиксируем максимальное собственное значение: $\lambda _{max}(U^{(k)})=1$. Используя этот метод обновления, можно легко увидеть, что окончательный результат $U$ матрица принимает следующий вид:

   $U=\prod _{k}\mu _{i}^{(k)}\cdot U^{(0)}=\prod _{k}(\mu ^{-{\tfrac {1}{2}}})^{(k)}\cdot U^{(0)}$

7. Если критерий остановки не соблюден, перейдите к следующей итерации на шаге 2. Поскольку алгоритм итеративно находит решение $U-normalization$ матрицу, преобразующую анизотропную область в изотропную, имеет смысл остановиться, когда изотропная мера, ${\mathcal {Q}}={\frac {\lambda _{\min }(\mu )}{\lambda _{\max }(\mu )}}$, достаточно близко к своему максимальному значению 1. Достаточно близко подразумевает следующее условие остановки :

   $1-{\frac {\lambda _{\min }(\mu _{i}^{(k)})}{\lambda _{\max }(\mu _{i}^{(k)})}}<\varepsilon _{C}$

   Миколайчик и Шмид (2004) имели хороший успех в $\epsilon _{C}=0.05$.

Расчет и реализация

Вычислительная сложность аффинного детектора Харриса разбита на две части: обнаружение начальной точки и нормализация аффинной области. Алгоритм обнаружения начальной точки Харриса – Лапласа имеет сложность. ${\mathcal {O}}(n)$ где $n$ это количество пикселей в изображении. Алгоритм нормализации аффинной области автоматически определяет масштаб и оценивает матрицу адаптации формы . $U$. Этот процесс имеет сложность ${\mathcal {O}}((m+k)p)$, где $p$ - количество начальных точек, $m$ — размер пространства поиска для автоматического выбора масштаба и $k$ — количество итераций, необходимое для вычисления $U$ матрица.

Существуют некоторые методы, позволяющие уменьшить сложность алгоритма за счет точности. Одним из методов является исключение поиска на этапе шкалы дифференцирования. Вместо того, чтобы выбирать фактор $s$ из набора факторов ускоренный алгоритм выбирает масштаб, который будет постоянным для всех итераций и точек: $\sigma _{D}=s\sigma _{I},\;s=constant$. Хотя это сокращение пространства поиска может уменьшить сложность, это изменение может серьезно повлиять на сходимость $U$ матрица.

Анализ

Конвергенция

Можно представить, что этот алгоритм может идентифицировать повторяющиеся точки интереса в нескольких масштабах. Поскольку аффинный алгоритм Харриса независимо рассматривает каждую начальную точку, заданную детектором Харриса – Лапласа, между идентичными точками нет различия. На практике было показано, что все эти точки в конечном итоге сойдутся в одной и той же точке интереса. После завершения идентификации всех точек интереса алгоритм учитывает дубликаты путем сравнения пространственных координат ( $\mathbf {x}$), масштаб интегрирования $\sigma _{I}$, изотропная мера ${\tfrac {\lambda _{\min }(U)}{\lambda _{\max }(U)}}$ и перекос. Если эти параметры точки интереса схожи в пределах указанного порога, то они помечаются как дубликаты. Алгоритм отбрасывает все эти повторяющиеся точки, за исключением точки интереса, которая ближе всего к среднему значению дубликатов. Обычно 30% аффинных точек Харриса достаточно различны и различны, чтобы их нельзя было отбросить.

Миколайчик и Шмид (2004) показали, что часто начальные точки (40%) не сходятся. Алгоритм обнаруживает это расхождение, останавливая итерационный алгоритм, если обратная изотропная мера больше заданного порога: ${\tfrac {\lambda _{\max }(U)}{\lambda _{\min }(U)}}>t_{\text{diverge}}$. Миколайчик и Шмид (2004) используют $t_{diverge}=6$. Из тех, которые сошлись, типичное количество требуемых итераций составляло 10.

Количественная мера

Количественный анализ детекторов аффинных областей учитывает как точность местоположения точек, так и перекрытие областей на двух изображениях. Mioklajcyzk и Schmid (2004) расширяют меру повторяемости Schmid et al. (1998) как отношение соответствий точек к минимуму обнаруженных точек двух изображений.

$R_{\text{score}}={\frac {C(A,B)}{\min(n_{A},n_{B})}}$

где $C(A,B)$ количество соответствующих точек на изображениях $A$ и $B$. $n_{B}$ и $n_{A}$ – количество обнаруженных точек на соответствующих изображениях. Поскольку каждое изображение представляет собой трехмерное пространство, может случиться так, что одно изображение содержит объекты, которых нет на втором изображении, и, следовательно, точки интереса которых не имеют шансов совпадать. Чтобы сделать меру повторяемости действительной, нужно удалить эти точки и рассматривать только точки, которые лежат на обоих изображениях; $n_{A}$ и $n_{B}$ считать только те точки, которые $x_{A}=H\cdot x_{B}$. Для пары из двух изображений, связанных гомографии . матрицей $H$, две точки, $\mathbf {x_{a}}$ и $\mathbf {x_{b}}$ называются соответствующими, если:

Область перекрытия двух эллиптических областей.

1. Ошибка расположения пикселей менее 1,5 пикселей: $\|\mathbf {x_{a}} -H\cdot \mathbf {x_{b}} \|<1.5$
2. Ошибка перекрытия двух аффинных точек ( $\epsilon _{S}$) должно быть меньше указанного порога (обычно 40%). Для аффинных регионов эта ошибка перекрытия следующая:

   $\epsilon _{S}=1-{\frac {\mu _{a}\cap (H^{T}\mu _{b}H)}{\mu _{a}\cup (H^{T}\mu _{b}H)}}$

   где $\mu _{a}$ и $\mu _{b}$ — восстановленные эллиптические области, точки которых удовлетворяют: $\mu ^{T}\mathbf {x} \mu =1$. По сути, эта мера принимает соотношение площадей: площади перекрытия (пересечения) и общей площади (объединения). Идеальное перекрытие будет иметь коэффициент, равный единице, и иметь $\epsilon _{S}=0$. Различные масштабы влияют на область перекрытия, и поэтому их необходимо учитывать путем нормализации площади каждой интересующей области. Области с ошибкой перекрытия до 50% являются жизнеспособными детекторами, для которых требуется сопоставление с хорошим дескриптором.

   Вторая мера, оценка соответствия , более практично оценивает способность детектора идентифицировать точки совпадения между изображениями. Миколайчик и Шмид (2005) используют дескриптор SIFT для определения точек совпадения. Помимо того, что две совпадающие точки являются ближайшими точками в SIFT-пространстве, они также должны иметь достаточно небольшую ошибку перекрытия (как определено в показателе повторяемости). Оценка соответствия представляет собой соотношение количества совпадающих точек и минимального общего количества обнаруженных точек на каждом изображении:

   $M_{score}={\frac {M(A,B)}{\min(n_{A},n_{B})}}$,

   где $M(A,B)$ количество совпадающих точек и $n_{B}$ и $n_{A}$ — количество обнаруженных областей на соответствующих изображениях.

Устойчивость к аффинным и другим преобразованиям

Миколайчик и др. (2005) провели тщательный анализ нескольких современных детекторов аффинных областей: аффинного по Харрису, аффинного по Гессе , MSER , ИБР и ЕБР и заметный детекторы. Миколайчик и др. в своей оценке проанализировали как структурированные изображения, так и текстурированные изображения. Бинарные файлы детекторов для Linux и их тестовые образы находятся в свободном доступе на их веб-странице . Краткое изложение результатов Миколайчика и соавт. (2005) следуйте; см. Сравнение детекторов аффинных областей для более количественного анализа.

• Изменение угла точки обзора: аффинный детектор Харриса имеет достаточную (среднюю) устойчивость к этим типам изменений. Детектор сохраняет показатель повторяемости выше 50% до тех пор, пока угол обзора не превысит 40 градусов. Детектор имеет тенденцию обнаруживать большое количество повторяющихся и сопоставляемых областей даже при значительном изменении точки обзора.
• Изменение масштаба: аффинный детектор Харриса остается очень стабильным при изменении масштаба. Хотя количество точек значительно снижается при крупномасштабных изменениях (выше 2,8), показатели повторяемости (50–60%) и соответствия (25–30%) остаются очень постоянными, особенно для текстурированных изображений. Это согласуется с высокой производительностью итерационного алгоритма автоматического выбора масштаба.
• Размытые изображения: Аффинный детектор Харриса остается очень стабильным при размытии изображения. Поскольку детектор не полагается на сегментацию изображения или границы областей, оценки повторяемости и соответствия остаются постоянными.
• Артефакты JPEG: аффинный детектор Харриса ухудшается так же, как и другие аффинные детекторы: показатели повторяемости и соответствия значительно падают при сжатии выше 80%.
• Изменения освещенности: аффинный детектор Харриса, как и другие аффинные детекторы, очень устойчив к изменениям освещенности: показатели повторяемости и совпадения остаются постоянными при уменьшении освещенности. Этого и следовало ожидать, поскольку детекторы в значительной степени полагаются на относительные интенсивности (производные), а не на абсолютные интенсивности.

Общие тенденции

• Точки аффинной области Харриса обычно небольшие и многочисленные. И аффинный детектор Харриса, и аффинный детектор Гессиана последовательно идентифицируют вдвое больше повторяющихся точек, чем другие аффинные детекторы: ~ 1000 областей для изображения размером 800x640. Маленькие регионы с меньшей вероятностью будут перекрыты, но имеют меньшую вероятность перекрытия соседних регионов.
• Аффинный детектор Харриса хорошо реагирует на текстурированные сцены, в которых много угловатых деталей. Однако для некоторых структурированных сцен, таких как здания, аффинный детектор Харриса работает очень хорошо. Это дополняет MSER, который лучше справляется с хорошо структурированными (сегментируемыми) сценами.
• В целом аффинный детектор Харриса работает очень хорошо, но во всех случаях все еще отстает от MSER и гессиан-аффинного, но изображения размыты.
• Аффинные детекторы Харриса и Гессиана менее точны, чем другие: их показатель повторяемости увеличивается по мере увеличения порога перекрытия.
• Обнаруженные аффинно-инвариантные области все еще могут различаться по вращению и освещенности. Любой дескриптор, использующий эти регионы, должен учитывать инвариантность при использовании регионов для сопоставления или других сравнений.

Приложения

• Поиск изображений на основе контента
• Распознавание на основе моделей
• Поиск объектов в видео
• Визуальный анализ данных: идентификация важных объектов, персонажей и сцен в видео.
• Распознавание и категоризация объектов
• Анализ изображений, полученных с помощью дистанционного зондирования: обнаружение объектов на полученных с помощью дистанционного зондирования. изображениях,

Пакеты программного обеспечения

• Аффинные ковариантные функции : К. Миколайчик поддерживает веб-страницу, которая содержит двоичные файлы Linux аффинного детектора Харриса в дополнение к другим детекторам и дескрипторам. Также доступен код Matlab, который можно использовать для иллюстрации и расчета повторяемости различных детекторов. Также доступны код и изображения для дублирования результатов, найденных в Mikolajczyk et al. (2005) статья.
• Lip-vireo — двоичный код для Linux, Windows и SunOS от исследовательской группы VIREO. Дополнительную информацию можно найти на главной странице. Архивировано 11 мая 2017 г. на Wayback Machine.

Внешние ссылки

• [1] – Слайды презентации Миколайчика и др. в своей статье 2005 года.
• [2] – Лаборатория компьютерного зрения Корделии Шмид .
• [3] - Код, тестовые изображения, библиография аффинных ковариантных функций, поддерживаемая Кристианом Миколайчиком и группой визуальной геометрии из группы робототехники Оксфордского университета.
• [4] - Библиография детекторов объектов (и капель), поддерживаемая Институтом робототехники и интеллектуальных систем Университета Южной Калифорнии.
• [5] – Цифровая реализация лапласиана гауссиана.

См. также

• гессен-аффинный
• МСЭР
• Детектор заметности Кадира – Брейди
• Масштабировать пространство
• Изотропия
• Обнаружение углов
• Обнаружение точек интереса
• Аффинная адаптация формы
• Производное изображения
• Компьютерное зрение
• ASIFT -> Affine-Sift (полностью аффинный инвариантный алгоритм сопоставления изображений)