Детектор аффинной области Харриса - Википедия - Harris affine region detector

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

Обзор

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

Миколайчик и Шмид (2002) впервые описали аффинный детектор Харриса в том виде, в котором он используется сегодня в Детектор аффинно-инвариантных точек интереса.^[2] Более ранние работы в этом направлении включают использование адаптация аффинной формы Линдеберга и Гардинга для вычисления дескрипторов аффинно-инвариантных изображений и, таким образом, уменьшения влияния деформаций перспективных изображений,^[3] использование аффинно адаптированных точек характеристик для широкого базового сопоставления по Баумбергу^[4] и первое использование масштабно-инвариантных характерных точек Линдебергом;^[5]^[6]^[7] для обзора теоретических основ. Аффинный детектор Харриса полагается на комбинацию угловых точек, обнаруженных через Обнаружение угла Харриса, многомасштабный анализ через Гауссово масштабное пространство и аффинная нормализация с использованием итеративного адаптация аффинной формы алгоритм. Рекурсивный и итерационный алгоритм следует итеративному подходу к обнаружению этих областей:

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

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

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

Аффинный детектор Харриса в значительной степени полагается как на меру Харриса, так и на гауссову формулу. представление масштабного пространства. Поэтому следует краткое рассмотрение обоих. Для более полных выводов см. обнаружение угла и Гауссово масштабное пространство или связанные с ними документы.^[6]^[8]

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

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

{ displaystyle 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) конец {bmatrix}}}

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

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

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

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

{ displaystyle R = det (A) - alpha operatorname {trace} ^ {2} (A) = lambda _ {1} lambda _ {2} - alpha ( lambda _ {1} + лямбда _ {2}) ^ {2}}

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

{ displaystyle { begin {align} {x_ {c} } = { big {} x_ {c} | R (x_ {c})> R (x_ {i}), forall x_ {i } in W (x_ {c}) { big }}, R (x_ {c})> t_ {threshold} end {align}}}

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

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

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

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

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

куда ${ Displaystyle G (s)}$ является изотропным круговым гауссовым ядром, как определено выше. Свертка с гауссовым ядром сглаживает изображение, используя окно размером с ядро. В большем масштабе, ${ displaystyle s}$ , соответствует более гладкому результирующему изображению. Миколайчик и Шмид (2001) отмечают, что производные и другие измерения должны быть нормализованы по шкалам.^[9] Производная порядка ${ displaystyle m}$ , ${ displaystyle D_ {i_ {1}, ... i_ {m}}}$ , должны быть нормированы коэффициентом ${ displaystyle s ^ {m}}$ следующим образом:

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

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

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

В Харрис-Лаплас детектор сочетает в себе традиционный двухмерный угловой детектор Харриса с идеей гауссова представление масштабного пространства для создания масштабно-инвариантного детектора. Угловые точки Харриса являются хорошей отправной точкой, потому что, как было показано, они обладают хорошей инвариантностью к вращению и освещению в дополнение к идентификации интересных точек изображения.^[10] Однако точки не являются масштабно-инвариантными, и поэтому матрица второго момента должна быть изменена, чтобы отразить свойство масштабной инвариантности. Обозначим, ${ Displaystyle М = му ( mathbf {х}, sigma _ { mathit {I}}, sigma _ { mathit {D}})}$ как масштабно адаптированная матрица второго момента, используемая в детекторе Харриса-Лапласа.

{ displaystyle 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}}}

^[11]

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

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

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

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

{ displaystyle { sigma _ {1} dots sigma _ {n}} = {k ^ {1} sigma _ {0} dots k ^ {n} sigma _ {0}}}

Миколайчик и Шмид (2004) используют ${ displaystyle k = 1,4}$ . Для каждого масштаба интеграции ${ displaystyle sigma _ {I}}$ , выбранный из этого набора, соответствующий масштаб дифференциации выбирается как постоянный коэффициент шкалы интегрирования: ${ displaystyle sigma _ {D} = s sigma _ {I}}$ . Миколайчик и Шмид (2004) использовали ${ displaystyle s = 0,7}$ .^[11] Используя эти шкалы, точки интереса обнаруживаются с помощью меры Харриса на ${ displaystyle mu ( mathbf {x}, sigma _ { mathit {I}}, sigma _ { mathit {D}})}$ матрица. В угловатость, как и типичная мера Харриса, определяется как:

{ displaystyle { mathit {angness}} = det ( mu ( mathbf {x}, sigma _ { mathit {I}}, sigma _ { mathit {D}})) - alpha имя оператора {след} ^ {2} ( mu ( mathbf {x}, sigma _ { mathit {I}}, sigma _ { mathit {D}}))}

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

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

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

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

{ displaystyle | LoG ( mathbf {x}, sigma _ {I}) | = sigma _ {I} ^ {2} | L_ {xx} ( mathbf {x}, sigma _ {I}) + L_ {yy} ( mathbf {x}, sigma _ {I}) |}

куда

{ displaystyle L_ {xx}}

и

{ displaystyle L_ {yy}}

- вторые производные в соответствующих направлениях.^[12] В

{ displaystyle sigma _ {I} ^ {2}}

Фактор (как обсуждалось выше в гауссовском масштабном пространстве) используется для нормализации LoG по масштабам и делает эти измерения сопоставимыми, таким образом делая максимум актуальным. Миколайчик и Шмид (2001) демонстрируют, что показатель LoG достигает наивысшего процента правильно обнаруженных угловых точек по сравнению с другими критериями выбора шкалы.^[9] Масштаб, который максимизирует эту меру LoG в два масштабных пространства район считается характерный масштаб,

{ Displaystyle sigma _ {I} ^ {(к + 1)}}

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

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

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

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

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

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

{ displaystyle 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})}

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

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

{ displaystyle { begin {align} 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 {выровнено}}}

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

{ displaystyle { begin {align} Sigma _ {I, L} = sigma _ {I} M_ {L} ^ {- 1} Sigma _ {D, L} = sigma _ {D} M_ {L} ^ {- 1} end {выровнено}}}

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

{ displaystyle { begin {align} Sigma _ {I, R} = sigma _ {I} M_ {R} ^ {- 1} Sigma _ {D, R} = sigma _ {D} M_ {R} ^ {- 1} end {выравнивается}}}

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

{ displaystyle { begin {align} 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} ^ {'} конец {выровнено}}}

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

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

куда ${ displaystyle lambda}$ обозначают собственные значения. Эта мера имеет диапазон ${ Displaystyle [0 точки 1]}$ . Ценность ${ displaystyle 1}$ соответствует идеальной изотропии.

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

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

Детектор инициализирует пространство поиска точками, обнаруженными детектором Харриса-Лапласа.
${ Displaystyle U ^ {(0)} = { mathit {идентичность}}}$ и ${ Displaystyle mathbf {х} ^ {(0)}}$ , ${ displaystyle sigma _ {D} ^ {(0)}}$ , и ${ displaystyle sigma _ {I} ^ {(0)}}$ взяты из детектора Харриса-Лапласа.
Применить предыдущую итерацию матрица адаптации формы, ${ Displaystyle U ^ {(к-1)}}$ для создания нормализованной системы отсчета, ${ Displaystyle U ^ {(k-1)} mathbf {x} _ {w} ^ {(k-1)} = mathbf {x} ^ {(k-1)}}$ . Для первой итерации вы применяете ${ displaystyle U ^ {(0)}}$ .
Выберите масштаб интеграции, ${ displaystyle sigma _ {I} ^ {(k)}}$ , используя метод, аналогичный детектору Харриса-Лапласа. Масштаб выбран как масштаб, который максимизирует лапласиан гауссова (LoG). Пространство поиска шкал - это те, которые находятся в пределах двух пространств шкалы предыдущих итераций.
${ displaystyle sigma _ {I} ^ {(k)} = { underset { sigma _ {I} = t sigma _ {I} ^ {(k-1)} на вершине 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}))}$
Важно отметить, что шкала интеграции в ${ displaystyle U-normalized}$ пространство значительно отличается от ненормализованного пространства. Следовательно, необходимо искать масштаб интегрирования, а не использовать масштаб в ненормализованном пространстве.
Выберите шкалу дифференциации, ${ displaystyle sigma _ {D} ^ {(k)}}$ . Чтобы уменьшить пространство поиска и степени свободы, масштаб дифференцирования считается связанным со масштабом интегрирования через постоянный коэффициент: ${ Displaystyle sigma _ {D} ^ {k} = s sigma _ {I} ^ {k}}$ . По понятным причинам постоянный коэффициент меньше единицы. Миколайчик и Шмид (2001) отмечают, что слишком маленький коэффициент сделает сглаживание (интегрирование) слишком значительным по сравнению с дифференцированием, а слишком большой коэффициент не позволит интегрированию усреднить ковариационную матрицу.^[9] Обычно выбирают ${ displaystyle s in [0,5,0,75]}$ . Из этого набора выбранный масштаб максимизирует изотропную меру ${ displaystyle { mathcal {Q}} = { frac { lambda _ {min} ( mu)} { lambda _ {max} ( mu)}}}$ .
${ Displaystyle sigma _ {D} ^ {(k)} = { underset { sigma _ {D} = s sigma _ {I} ^ {(k)}, ; s in [0,5, точки, 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}))}}}$
куда ${ displaystyle mu ( mathbf {x} _ {w} ^ {(k)}, sigma _ {I} ^ {k}, sigma _ {D})}$ - матрица второго момента, вычисленная в нормализованной системе отсчета. Этот процесс максимизации приводит к тому, что собственные значения сходятся к одному и тому же значению.
Пространственная локализация: Выберите точку ${ Displaystyle mathbf {х} _ {ш} ^ {(к)}}$ который максимизирует угловую меру Харриса ( ${ displaystyle { mathit {угловость}}}$ ) в 8-балльной окрестности вокруг предыдущего ${ Displaystyle mathbf {х} _ {ш} ^ {(к-1)}}$ точка.
${ displaystyle 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)}))}$
куда ${ displaystyle mu}$ матрица второго момента, как определено выше. Окно ${ Displaystyle W ( mathbf {x} _ {w} ^ {(k-1)})}$ - это набор из 8 ближайших соседей точки предыдущей итерации в нормализованной системе отсчета, поскольку наша пространственная локализация была выполнена в ${ displaystyle U}$ -нормализованный опорный кадр, вновь выбранная точка должна быть преобразована обратно в исходный опорный кадр. Это достигается путем преобразования вектора смещения и добавления его к предыдущей точке:
${ Displaystyle mathbf {x} ^ {(k)} = mathbf {x} ^ {(k-1)} + U ^ {(k-1)} cdot ( mathbf {x} _ {w} ^ {(k)} - mathbf {x} _ {w} ^ {(k-1)})}$
Как упоминалось выше, квадратный корень из матрицы второго момента определяет матрицу преобразования, которая генерирует нормализованный опорный кадр. Таким образом, нам нужно сохранить эту матрицу: ${ displaystyle mu _ {i} ^ {(k)} = mu ^ {- { tfrac {1} {2}}} ( mathbf {x} _ {w} ^ {(k)}, сигма _ {I} ^ {(k)}, sigma _ {D} ^ {(k)})}$ . Матрица преобразования ${ displaystyle U}$ обновлено: ${ Displaystyle U ^ {(к)} = му _ {я} ^ {(к)} cdot U ^ {(k-1)}}$ . Чтобы гарантировать, что изображение выбрано правильно и мы расширяем изображение в направлении наименьшего изменения (наименьшее собственное значение), мы фиксируем максимальное собственное значение: ${ Displaystyle лямбда _ {макс} (U ^ {(k)}) = 1}$ . Используя этот метод обновления, легко увидеть, что окончательный ${ displaystyle U}$ Матрица принимает следующий вид:
${ Displaystyle U = prod _ {k} mu _ {i} ^ {(k)} cdot U ^ {(0)} = prod _ {k} ( mu ^ {- { tfrac {1 } {2}}}) ^ {(k)} cdot U ^ {(0)}}$
Если критерий остановки не выполняется, переходите к следующей итерации на шаге 2. Поскольку алгоритм итеративно решает для ${ Displaystyle U-нормализация}$ матрица, которая преобразует анизотропную область в изотропную область, имеет смысл остановиться, когда изотропная мера, ${ Displaystyle { mathcal {Q}} = { гидроразрыва { lambda _ { min} ( mu)} { lambda _ { max} ( mu)}}}$ , достаточно близко к своему максимальному значению 1. Достаточно близко подразумевает следующее условие остановки:
${ displaystyle 1 - { frac { lambda _ { min} ( mu _ {i} ^ {(k)})} { lambda _ { max} ( mu _ {i} ^ {(k )})}} < varepsilon _ {C}}$
Миколайчик и Шмид (2004) добились хороших результатов с ${ displaystyle epsilon _ {C} = 0,05}$ .

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

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

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

Анализ

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

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

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

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

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

{ displaystyle R _ { text {score}} = { frac {C (A, B)} { min (n_ {A}, n_ {B})}}}

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

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

Ошибка в расположении пикселя менее 1,5 пикселя: ${ Displaystyle | mathbf {x_ {a}} -H cdot mathbf {x_ {b}} | <1.5}$
В ошибка перекрытия двух аффинных точек ( ${ displaystyle epsilon _ {S}}$ ) должно быть меньше указанного порога (обычно 40%).^[1] Для аффинных регионов эта ошибка перекрытия следующая:
${ displaystyle epsilon _ {S} = 1 - { frac { mu _ {a} cap (H ^ {T} mu _ {b} H)} { mu _ {a} cup (H ^ {T} mu _ {b} H)}}}$
куда ${ Displaystyle mu _ {а}}$ и ${ displaystyle mu _ {b}}$ восстановленные эллиптические области, точки которых удовлетворяют: ${ Displaystyle mu ^ {T} mathbf {x} mu = 1}$ . По сути, эта мера принимает соотношение площадей: площади перекрытия (пересечения) и общей площади (объединения). Идеальное перекрытие будет иметь коэффициент, равный единице, и иметь ${ displaystyle epsilon _ {S} = 0}$ . Различные масштабы влияют на область перекрытия и, следовательно, должны приниматься во внимание путем нормализации области каждой интересующей области. Области с ошибкой перекрытия до 50% являются жизнеспособными детекторами, которые должны быть сопоставлены с хорошим дескриптором.^[1]
Вторая мера, оценка соответствия, более практично оценивает способность детектора определять точки совпадения между изображениями. Миколайчик и Шмид (2005) используют ПРОСЕЯТЬ дескриптор для определения совпадающих точек. Помимо того, что две совпадающие точки являются ближайшими точками в пространстве SIFT, они также должны иметь достаточно небольшую ошибку перекрытия (как определено в измерении повторяемости). В оценка соответствия - это отношение количества совпавших точек к минимуму общего количества обнаруженных точек на каждом изображении:
${ displaystyle M_ {score} = { frac {M (A, B)} { min (n_ {A}, n_ {B})}}}$ ,^[1]
куда ${ Displaystyle М (А, В)}$ количество совпадающих точек и ${ displaystyle n_ {B}}$ и ${ displaystyle n_ {A}}$ - количество обнаруженных областей на соответствующих изображениях.

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

Mikolajczyk et al. (2005) провели тщательный анализ нескольких современных детекторов аффинных областей: аффинных Харриса, Гессенское аффинное, MSER,^[14] IBR и EBR^[15] и выдающийся^[16] детекторы.^[1] Mikolajczyk et al. проанализировали как структурированные изображения, так и текстурированные изображения в своей оценке. Бинарные файлы для Linux детекторов и их тестовые изображения находятся в свободном доступе по адресу страница в Интернете. Краткое изложение результатов Mikolajczyk et al. (2005) следовать; видеть Сравнение детекторов аффинной области для более количественного анализа.

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

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

Точки аффинной области Харриса обычно малы и многочисленны. И детектор Харриса-Аффина, и Гессен-Аффинный последовательно идентифицируйте удвоенное количество повторяемых точек по сравнению с другими аффинными детекторами: ~ 1000 областей для изображения 800x640.^[1] Небольшие области с меньшей вероятностью будут закрыты, но имеют меньшую вероятность перекрытия соседних областей.
Аффинный детектор Харриса хорошо реагирует на текстурированные сцены, в которых много угловых частей. Однако для некоторых структурированных сцен, таких как здания, детектор Харриса-Аффина работает очень хорошо. Это дополняет MSER, который лучше работает с хорошо структурированными (сегментированными) сценами.
В целом аффинный детектор Харриса работает очень хорошо, но все еще уступает MSER и Hessian-Affine во всех случаях, кроме размытых изображений.
Harris-Affine and Hessian-Affine detectors are less accurate than others: their repeatability score increases as the overlap threshold is increased.
The detected affine-invariant regions may still differ in their rotation and illumination. Any descriptor that uses these regions must account for the invariance when using the regions for matching or other comparisons.

Приложения

Поиск изображений на основе содержимого^[17]^[18]
Model-based recognition
Object retrieval in video^[19]
Visual data mining: identifying important objects, characters and scenes in videos^[20]
Object recognition and categorization^[21]
Remotely sensed image analysis: Обнаружение объекта из дистанционно ощущаемый изображений^[22]

Программные пакеты

Аффинные ковариантные особенности: K. Mikolajczyk maintains a web page that contains Linux binaries of the Harris-Affine detector in addition to other detectors and descriptors. Также доступен код Matlab, который можно использовать для иллюстрации и вычисления повторяемости различных детекторов. Также доступны код и изображения для дублирования результатов, найденных в Mikolajczyk et al. (2005) бумага.
Lip-vireo - binary code for Linux, Windows and SunOS from VIREO research group. See more from the домашняя страница

внешняя ссылка

[1] - Презентационные слайды Mikolajczyk et al. на их бумаге 2005 года.
[2] - Лаборатория компьютерного зрения Корделии Шмид
[3] - Код, тестовые изображения, библиография аффинных ковариантных функций, поддерживаемая Кристианом Миколайчиком и Группа визуальной геометрии из группы робототехники Оксфордского университета.
[4] - Библиография детекторов функций (и blob), поддерживаемая Институтом робототехники и интеллектуальных систем USC
[5] - Digital implementation of Laplacian of Gaussian