Угловой детектор Харриса

Детектор углов Харриса — это оператор обнаружения углов , который обычно используется в алгоритмах компьютерного зрения для извлечения углов и определения особенностей изображения. Впервые он был представлен Крисом Харрисом и Майком Стивенсом в 1988 году после усовершенствования углового детектора Моравца . ^[1] По сравнению со своим предшественником, угловой детектор Харриса учитывает разницу в угловых показателях непосредственно по направлению, вместо использования смещающихся участков для каждых 45 градусов, и было доказано, что он более точен в различении краев и углов. ^[2] С тех пор он был улучшен и принят во многих алгоритмах предварительной обработки изображений для последующих приложений.

Введение

Угол — это точка, локальная окрестность которой расположена в двух доминирующих и разных краевых направлениях. Другими словами, угол можно интерпретировать как место соединения двух краев, где край — это внезапное изменение яркости изображения. ^[3] Углы являются важными элементами изображения, и их обычно называют точками интереса, которые инвариантны к перемещению, вращению и освещению. Хотя углы составляют лишь небольшой процент изображения, они содержат наиболее важные функции восстановления информации изображения, и их можно использовать для минимизации объема обрабатываемых данных для отслеживания движения, сшивания изображений , построения 2D-мозаики, стереозрения , представления изображений. и другие смежные области компьютерного зрения.

Чтобы захватить углы изображения, исследователи предложили множество различных детекторов углов, включая оператор Канаде-Лукаса-Томази (KLT) и оператор Харриса, которые являются наиболее простыми, эффективными и надежными для использования при обнаружении углов. Эти две популярные методологии тесно связаны с матрицей локальной структуры и основаны на ней. По сравнению с угловым детектором Канаде-Лукаса-Томази, угловой детектор Харриса обеспечивает хорошую повторяемость при изменении освещенности и вращения, поэтому его чаще используют при сопоставлении стереоскопических изображений и поиске в базе данных изображений. Несмотря на то, что все еще существуют недостатки и ограничения, угловой детектор Харриса по-прежнему остается важным и фундаментальным методом для многих приложений компьютерного зрения.

Разработка алгоритма обнаружения углов Харриса ^[1]

Без ограничения общности будем считать, что в оттенках серого используется двухмерное изображение . Пусть это изображение задано $I$ . Рассмотрите возможность использования патча изображения $(x,y)\in W$ (окно) и сдвинув его на $(\Delta x,\Delta y)$ . Сумма квадратов разностей (SSD) между этими двумя патчами, обозначаемая $f$ , определяется:

f(\Delta x,\Delta y)={\underset {(x_{k},y_{k})\in W}{\sum }}\left(I(x_{k},y_{k})-I(x_{k}+\Delta x,y_{k}+\Delta y)\right)^{2}

$I(x+\Delta x,y+\Delta y)$ может быть аппроксимировано разложением Тейлора . Позволять $I_{x}$ и $I_{y}$ быть частными производными от $I$ , такой, что

I(x+\Delta x,y+\Delta y)\approx I(x,y)+I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y

Это дает приближение

f(\Delta x,\Delta y)\approx {\underset {(x,y)\in W}{\sum }}\left(I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y\right)^{2},

что можно записать в матричной форме:

f(\Delta x,\Delta y)\approx {\begin{pmatrix}\Delta x&\Delta y\end{pmatrix}}M{\begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}},

где M – структурный тензор ,

M={\underset {(x,y)\in W}{\sum }}{\begin{bmatrix}I_{x}^{2}&I_{x}I_{y}\\I_{x}I_{y}&I_{y}^{2}\end{bmatrix}}={\begin{bmatrix}{\underset {(x,y)\in W}{\sum }}I_{x}^{2}&{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}\\{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}&{\underset {(x,y)\in W}{\sum }}I_{y}^{2}\end{bmatrix}}

Процесс алгоритма обнаружения углов Харриса ^[4]^[5]^[6]

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

Цвет в оттенки серого
Расчет пространственной производной
Настройка структурного тензора
Расчет ответа Харриса
Немаксимальное подавление

Цвет в оттенки серого

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

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

\sum _{C\,\in \,\{R,G,B\}}w_{C}\cdot C

,

где, например,

w_{R}=0.299,\ w_{G}=0.587,\ w_{B}=1-(w_{R}+w_{G})=0.114.

Расчет пространственной производной

Далее мы собираемся найти производную по x и производную по y, $I_{x}(x,y)$ и $I_{y}(x,y)$ .

Настройка структурного тензора

С $I_{x}(x,y)$ , $I_{y}(x,y)$ , мы можем построить структурный тензор $M$ .

Расчет ответа Харриса

Для $x\ll y$ , у одного есть ${\tfrac {x\cdot y}{x+y}}=x{\tfrac {1}{1+x/y}}\approx x.$ На этом этапе мы вычисляем наименьшее собственное значение структурного тензора, используя это приближение:

\lambda _{\min }\approx {\frac {\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})}}={\frac {\det(M)}{\operatorname {tr} (M)}}

со следом $\mathrm {tr} (M)=m_{11}+m_{22}$ .

Другой часто используемый расчет ответа Харриса показан ниже:

$R=\lambda _{1}\lambda _{2}-k(\lambda _{1}+\lambda _{2})^{2}=\det(M)-k\operatorname {tr} (M)^{2}$

где $k$ – эмпирически определенная константа; $k\in [0.04,0.06]$ .

Немаксимальное подавление

Чтобы подобрать оптимальные значения для обозначения углов, мы находим локальные максимумы как углы в окне, которое представляет собой фильтр 3 на 3.

Улучшение ^[7]^[8]

Угловой детектор Харриса-Лапласа ^[9]
Угловой детектор на основе дифференциального морфологического разложения ^[10]
Многомасштабный угловой детектор на основе тензора двусторонней структуры ^[11]

Приложения

Выравнивание изображения, сшивание и регистрация ^[12]
Создание 2D-мозаики ^[13]
3D-моделирование и реконструкция сцены ^[14]
Обнаружение движения ^[15]
Распознавание объектов ^[16]
Индексирование изображений и поиск по содержимому ^[17]
Видео отслеживание ^[18]

См. также

Ссылки

^ Jump up to: ^а ^б Крис Харрис и Майк Стивенс (1988). «Комбинированный детектор углов и краев». Конференция Alvey Vision . Том. 15.
^ Дей, Ниланджан; и др. (2012). «Сравнительное исследование Моравека и Харриса по угловому обнаружению зашумленных изображений с использованием метода адаптивного порогового вейвлета». arXiv : 1209.1558 [ cs.CV ].
^ Константинос Г. Дерпанис (2004). Угловой детектор Харриса . Йоркский университет.
^ «Обнаружение угла оператора Харриса с использованием метода скользящего окна — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.
^ «Сравнение и применение алгоритмов обнаружения углов — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.
^ Хавьер Санчес, Нельсон Монсон и Агустин Сальгадо (2018). «Анализ и реализация углового детектора Харриса» . Обработка изображений в режиме онлайн . 8 : 305–328. дои : 10.5201/ipol.2018.229 . hdl : 10553/43499 .
^ Беллавиа, Ф.; Теголо, Д.; Валенти, К. (01 марта 2011 г.). «Улучшение стратегии выбора углового Харриса». ИЭПП Компьютерное зрение 5 (2): 87. doi : 10.1049/iet-cvi.2009.0127 .
^ Ростен, Эдвард; Драммонд, Том (7 мая 2006 г.). Леонардис, Алеш; Бишоф, Хорст; Пинц, Аксель (ред.). Машинное обучение для высокоскоростного обнаружения углов . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 430–443. CiteSeerX 10.1.1.64.8513 . дои : 10.1007/11744023_34 . ISBN 978-3-540-33832-1 . S2CID 1388140 .
^ «Сравнение детекторов аффинных областей — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.
^ Геген, Л.; Песарези, М. (2011). «Многомасштабный угловой детектор Харриса на основе дифференциального морфологического разложения» . Буквы для распознавания образов . 32 (14): 1714–1719. Бибкод : 2011PaReL..32.1714G . дои : 10.1016/j.patrec.2011.07.021 .
^ «Многомасштабный угловой детектор на основе тензора двусторонней структуры — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.
^ Канг, Хуан; Сяо, Чуанбай; Дэн, М.; Ю, Цзин; Лю, Хайфэн (01 августа 2011 г.). «Регистрация изображений на основе Харриса Корнера и взаимной информации». Материалы Международной конференции по электронике, машиностроению и информационным технологиям 2011 года . Том. 7. С. 3434–3437. дои : 10.1109/EMEIT.2011.6023066 . ISBN 978-1-61284-087-1 . S2CID 17367248 .
^ «Создание подводной мозаики с использованием видеофрагментов с разных высот — Академия Google» . ученый.google.com . Проверено 2 декабря 2015 г.
^ «Автоматическая реконструкция 3D-сцен из последовательностей изображений — Google Scholar» . ученый.google.com . Проверено 2 декабря 2015 г.
^ Лю, Мэн; У, Чэндун; Чжан, Юньчжоу (01 июля 2008 г.). «Алгоритм отслеживания оптического потока с различным разрешением, основанный на функции многомасштабных угловых точек Харриса». 2008 Китайская конференция по контролю и принятию решений . стр. 5287–5291. дои : 10.1109/CCDC.2008.4598340 . ISBN 978-1-4244-1733-9 . S2CID 8085227 .
^ «Распознавание объектов по функциям, инвариантным к локальному масштабу — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.
^ «Основные моменты поиска на основе контента – Академия Google» . ученый.google.com . Проверено 2 декабря 2015 г.
^ «Отслеживание и распознавание объектов с использованием дескриптора SURF и обнаружения углов Харриса — Google Scholar» . ученый.google.com . Проверено 2 декабря 2015 г.

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

[harris-1] Jump up to: ^а ^б Крис Харрис и Майк Стивенс (1988). «Комбинированный детектор углов и краев». Конференция Alvey Vision . Том. 15.

[dey-2] Дей, Ниланджан; и др. (2012). «Сравнительное исследование Моравека и Харриса по угловому обнаружению зашумленных изображений с использованием метода адаптивного порогового вейвлета». arXiv : 1209.1558 [ cs.CV ].

[derpanis-3] Константинос Г. Дерпанис (2004). Угловой детектор Харриса . Йоркский университет.

[4] «Обнаружение угла оператора Харриса с использованием метода скользящего окна — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.

[5] «Сравнение и применение алгоритмов обнаружения углов — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.

[sanchez-6] Хавьер Санчес, Нельсон Монсон и Агустин Сальгадо (2018). «Анализ и реализация углового детектора Харриса» . Обработка изображений в режиме онлайн . 8 : 305–328. дои : 10.5201/ipol.2018.229 . hdl : 10553/43499 .

[7] Беллавиа, Ф.; Теголо, Д.; Валенти, К. (01 марта 2011 г.). «Улучшение стратегии выбора углового Харриса». ИЭПП Компьютерное зрение 5 (2): 87. doi : 10.1049/iet-cvi.2009.0127 .

[8] Ростен, Эдвард; Драммонд, Том (7 мая 2006 г.). Леонардис, Алеш; Бишоф, Хорст; Пинц, Аксель (ред.). Машинное обучение для высокоскоростного обнаружения углов . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 430–443. CiteSeerX 10.1.1.64.8513 . дои : 10.1007/11744023_34 . ISBN 978-3-540-33832-1 . S2CID 1388140 .

[9] «Сравнение детекторов аффинных областей — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.

[10] Геген, Л.; Песарези, М. (2011). «Многомасштабный угловой детектор Харриса на основе дифференциального морфологического разложения» . Буквы для распознавания образов . 32 (14): 1714–1719. Бибкод : 2011PaReL..32.1714G . дои : 10.1016/j.patrec.2011.07.021 .

[11] «Многомасштабный угловой детектор на основе тензора двусторонней структуры — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.

[12] Канг, Хуан; Сяо, Чуанбай; Дэн, М.; Ю, Цзин; Лю, Хайфэн (01 августа 2011 г.). «Регистрация изображений на основе Харриса Корнера и взаимной информации». Материалы Международной конференции по электронике, машиностроению и информационным технологиям 2011 года . Том. 7. С. 3434–3437. дои : 10.1109/EMEIT.2011.6023066 . ISBN 978-1-61284-087-1 . S2CID 17367248 .

[13] «Создание подводной мозаики с использованием видеофрагментов с разных высот — Академия Google» . ученый.google.com . Проверено 2 декабря 2015 г.

[14] «Автоматическая реконструкция 3D-сцен из последовательностей изображений — Google Scholar» . ученый.google.com . Проверено 2 декабря 2015 г.

[15] Лю, Мэн; У, Чэндун; Чжан, Юньчжоу (01 июля 2008 г.). «Алгоритм отслеживания оптического потока с различным разрешением, основанный на функции многомасштабных угловых точек Харриса». 2008 Китайская конференция по контролю и принятию решений . стр. 5287–5291. дои : 10.1109/CCDC.2008.4598340 . ISBN 978-1-4244-1733-9 . S2CID 8085227 .

[16] «Распознавание объектов по функциям, инвариантным к локальному масштабу — Google Scholar» . ученый.google.com . Проверено 29 ноября 2015 г.

[17] «Основные моменты поиска на основе контента – Академия Google» . ученый.google.com . Проверено 2 декабря 2015 г.

[18] «Отслеживание и распознавание объектов с использованием дескриптора SURF и обнаружения углов Харриса — Google Scholar» . ученый.google.com . Проверено 2 декабря 2015 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]