Виявляння плям

Виявляння ознак
Виявляння контурів
Кенні Деріша Диференціальне Собеля Прюітт Робертса
Виявляння кутів
Гарріса Сі та Томазі Кривина ізоліній міри вираженості гессіанових ознак SUSAN FAST
Виявляння плям
Лапласіан гауссіана (ЛГ, LoG) Різниця гауссіанів (РГ, DoG) Визначник гессіана (ВГ, DoH) МСЕО (MSER) PCBR
Виявляння хребтів
Перетворення Гафа
Перетворення Гафа Узагальнене перетворення Гафа
Структурний тензор
Структурний тензор Узагальнений структурний тензор
Афінноінваріантне виявляння ознак
Афінне пристосовування форми Афінне Гарріса Афінне гесіанне
Опис ознак
SIFT SURF GLOH HOG
Простір масштабів
Масштабопросторові аксіоми Деталі втілення Піраміди

У комп'ютернім баченні методи виявляння плям (англ. blob detection) спрямовано на виявляння областей у цифровому зображенні, які вирізняються за властивостями, такими як яскравість або колір, порівняно з навколишніми областями. Неформально пляма (англ. blob) — це область зображення, деякі властивості якої є сталими або приблизно сталими; всі точки в плямі можливо вважати в певному сенсі схожими одна на одну. Найпоширенішим методом виявляння плям є згортка.

Для деякої заданої особливої властивості, вираженої як функція від положення на зображенні, існує два основні класи виявлячів плям: (i) диференціальні методи, що ґрунтуються на похідних цієї функції від положення, та (ii) методи на основі локальних екстремумів, що ґрунтуються на пошуку локальних максимумів і мінімумів цієї функції. У сучаснішій галузевій термінології ці виявлячі також можуть називати операторами особливих точок (англ. interest point operator) або, як варіант, операторами особливих областей (англ. interest region operator, див. також виявляння особливих точок та виявляння кутів).

Мотивів для дослідження та розробки виявлячів плям декілька. Однією з основних причин є забезпечення доповняльної інформації про області, не отримуваної від виявлячів контурів та кутів. У ранній праці в цій області виявляння областей використовували для отримування особливих областей для подальшої обробки. Ці області можуть сигналізувати про наявність об'єктів або частин об'єктів в області визначення зображення із застосуванням для розпізнавання об'єктів та/або їхнього відстежування. В інших областях визначення, таких як аналіз гістограм, описувачі областей також можливо використовувати для виявляння піків із застосуванням для сегментування. Інше поширене застосуванням описувачів плям — основні примітиви для аналізу та розпізнавання текстур. У новіших працях описувачі плям знаходять все ширше застосування як особливі точки для стереозіставляння з широкою базою та для сигналізування про наявність інформативних ознак зображення для розпізнавання об'єктів за їхнім виглядом на основі локальних статистик зображень. Існує також пов'язане поняття виявляння хребтів для сигналізування про наявність видовжених об'єктів.

Лапласіан гауссіана

Один із найперших, а також найпоширеніших виявлячів плям ґрунтується на лапласіані гауссіана (ЛГ, англ. Laplacian of the Gaussian, LoG). Задане вхідне зображення $f(x,y)$ згортають гауссовим ядром

$g(x,y,t)={\frac {1}{2\pi t}}e^{-{\frac {x^{2}+y^{2}}{2t}}}$

у певному масштабі $t$ для отримання масштабопросторового подання $L(x,y;t)\ =g(x,y,t)*f(x,y)$. Потім обчислюють результат застосування оператора Лапласа

$\nabla ^{2}L=L_{xx}+L_{yy}$

що зазвичай дає сильні додатні відгуки для темних плям радіусу ${\textstyle r={\sqrt {2t}}}$ (для двовимірного зображення, ${\textstyle r={\sqrt {dt}}}$ для d-вимірного зображення) й сильні від'ємні відгуки для яскравих плям подібного розміру. Проте основна проблема при застосуванні цього оператора в єдиному масштабі полягає в сильній залежності відгуку цього оператора від співвідношення між розміром плямових структур в області зображення та розміром гауссового ядра, використаного для попереднього згладжування. Тому для автоматичного вловлювання плям різних (невідомих) розмірів в області зображення потрібен багатомасштабовий підхід.

Простий спосіб отримати багатомасштабовий виявляч плям з автоматичним обиранням масштабу (англ. multi-scale blob detector with automatic scale selection) — розглядати масштабонормований лапласіан

$\nabla _{\mathrm {norm} }^{2}L=t\,(L_{xx}+L_{yy})$

та виявляти масштабопросторові максимуми/мінімуми, що є точками, які є локальними максимумами/мінімумами $\nabla _{\mathrm {norm} }^{2}L$ відносно простору й масштабу одночасно (Ліндеберг 1994, 1998). Таким чином, для заданого дискретного двовимірного вхідного зображення $f(x,y)$ обчислюють тривимірний дискретний масштабопросторовий об'єм $L(x,y,t)$, і точку розглядають як яскраву (темну) пляму, якщо значення в ній більше (менше) за значення у всіх її 26 сусідках. Таким чином, одночасне обрання особливих точок $({\hat {x}},{\hat {y}})$ на масштабах ${\hat {t}}$ виконується згідно з

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argmaxminlocal} _{(x,y;t)}((\nabla _{\mathrm {norm} }^{2}L)(x,y;t))$.

Зауважте, що це поняття плями забезпечує стисле й математично точне операційне визначення поняття «пляма», яке безпосередньо веде до ефективного й надійного алгоритму виявлення плям. Деякі з основних властивості плям, визначених з масштабопросторових максимумів нормованого лапласіана, полягають у тому, що ці відгуки коваріантні з паралельними перенесеннями, поворотами та змінами масштабу в області зображення. Таким чином, якщо масштабопросторовий максимум передбачається в точці $(x_{0},y_{0};t_{0})$, то за масштабування зображення коефіцієнтом масштабу $s$ масштабопросторовий максимум у зміненому зображенні буде в $\left(sx_{0},sy_{0};s^{2}t_{0}\right)$ (Ліндеберг 1998). Ця дуже корисна на практиці властивість означає, що, крім цієї конкретної теми лапласового виявляння плям, локальні максимуми/мінімуми масштабонормованого лапласіана також використовують для обирання масштабу в інших контекстах, таких як виявляння кутів, масштабопристосовне відстежування ознак (англ. scale-adaptive feature tracking, Бретцнер та Ліндеберг 1998), масштабоінваріантне ознакове перетворення (англ. SIFT, Лоу 2004), а також як інші описувачі зображення для зіставляння зображень та розпізнавання об'єктів.

Масштабообиральні властивості лапласіана та інших близьких виявлячів масштабопросторових особливих точок докладно проаналізовано в (Ліндеберг 2013a). В (Ліндеберг 2013b, 2015) показано, що існують й інші виявлячі масштабопросторових особливих точок, такі як визначник гессіана, які для зіставляння на основі зображень за допомогою локальних описувачів зображення, подібних до SIFT, працюють краще за лапласіан чи його наближення різницею гауссіанів.

Підхід різниці гауссіанів

З того факту, що масштабопросторове подання $L(x,y,t)$ задовольняє рівняння дифузії

$\partial _{t}L={\frac {1}{2}}\nabla ^{2}L$

випливає, що лапласіан гауссіана $\nabla ^{2}L(x,y,t)$ також можливо обчислювати як граничний випадок різниці двох гауссово згладжених зображень (подань у просторі масштабів)

$\nabla _{\mathrm {norm} }^{2}L(x,y;t)\approx {\frac {t}{\Delta t}}\left(L(x,y;t+\Delta t)-L(x,y;t)\right)$.

В літературі з комп'ютерного бачення цей підхід називають підходом різниці гауссіанів (РГ, англ. difference of Gaussians, DoG). Проте, крім незначних технічних деталей, цей оператор по суті подібний до лапласіана, і його можливо розглядати як наближення лапласіана. Подібним до лапласіанового виявляча плям чином, плями можливо виявляти з масштабопросторових екстремумів різниць гауссіанів — щодо явного зв'язку оператора різниці гауссіанів та масштабонормованого лапласіана, див. (Ліндеберг 2012, 2015). Цей підхід, наприклад, використовують в алгоритмі масштабоінваріантного ознакового перетворення (англ. SIFT) — див. Лоу (2004).

Визначник гессіана

Розглядаючи масштабонормований визначник гессіана, який також називають оператором Монжа — Ампера,

$\det H_{\mathrm {norm} }L=t^{2}\left(L_{xx}L_{yy}-L_{xy}^{2}\right)$

де $HL$ позначує матрицю Гессе масштабопросторового подання $L$, а потім виявляючи масштабопросторові максимуми цього оператора, отримують інший простий диференціальний виявляч плям з автоматичним обиранням масштабу, що реагує також і на сідловини (Ліндеберг 1994, 1998),

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argmaxlocal} _{(x,y;t)}((\det H_{\mathrm {norm} }L)(x,y;t))$.

Точки плям $({\hat {x}},{\hat {y}})$ та масштабів ${\hat {t}}$ також визначають з операційних диференціальних геометричних визначень, що дає плямові описувачі, коваріантні з паралельними перенесеннями, поворотами та змінами масштабу в області зображення. З погляду обирання масштабу, плями, визначені через масштабопросторові екстремуми визначника гессіана (ВГ, англ. determinant of the Hessian, DoH), також мають дещо кращі масштабообиральні властивості за неевклідових афінних перетворень, ніж частіше вживаний лапласіан (Ліндеберг 1994, 1998, 2015). У спрощеному вигляді масштабонормований визначник гессіана, обчислюваний з гаарових вейвлетів, використовують як основний оператор особливих точок в описувачі SURF (Бей та ін. 2006) для зіставлення зображень та розпізнавання об'єктів.

Докладний аналіз обиральних властивостей визначника гессіана та інших близьких масштабопросторових виявлячів особливих точок, наведений в (Ліндеберг 2013a), показує, що визначник гессіана має кращі за лапласіан масштабообиральні властивості за афінних перетвореннях зображень. У (Ліндеберг 2013b, 2015) показано, що для зіставляння на основі зображень з використанням SIFT- або SURF-подібних локальних описувачів зображень визначник гессіана працює значно краще, ніж лапласіан або його наближення різницями гауссіанів, а також краще, ніж оператори Гарріса та Гарріса — Лапласа, що призводить до вищих значень ефективності (англ. efficiency) та нижчих показників 1−влучність (англ. 1−precision).

Гібридний оператор лапласіана й визначника гессіана (гессіанно-лапласіанний)

Також було запропоновано гібридний оператор описувачів плям лапласіаном і визначником гессіана, де просторове обирання здійснюється визначником гессіана, а обирання масштабу виконується за допомогою масштабонормованого лапласіана (Міколайчик та Шмід 2004):

$({\hat {x}},{\hat {y}})=\operatorname {argmaxlocal} _{(x,y)}((\det HL)(x,y;t))$

${\hat {t}}=\operatorname {argmaxminlocal} _{t}((\nabla _{\mathrm {norm} }^{2}L)({\hat {x}},{\hat {y}};t))$

Цей оператор використовували для зіставлення зображень, розпізнавання об'єктів, а також аналізу текстур.

Афіннопристосовані диференціальні виявлячі плям

Плямові описувачі, отримувані з цих виявлячів плям з автоматичним обиранням масштабу, інваріантні до паралельних перенесень, поворотів та рівномірного масштабування в просторовій області. Проте зображення, що є вхідними для систем комп'ютерного зору, зазнають також і перспективних спотворень. Щоб отримати описувачі плям, стійкіші до перспективних перетворень, природним підходом є розробка виявляча плям, інваріантного до афінних перетворень. На практиці афінноінваріантні особливі точки можливо отримувати застосовуванням до описувача плям афінного пристосовування форми, коли форма ядра згладжування ітеративно деформується, щоби зіставитися з локальною структурою зображення навколо плями, або, рівнозначно, локальний фрагмент зображення ітеративно деформується, тоді як форма ядра згладжування залишається обертово симетричною (Ліндеберг та Гардінг 1997; Баумберг 2000; Міколайчик та Шмід 2004, Ліндеберг 2008). Таким чином, ми можемо визначити афіннопристосовані версії оператора лапласіана/різниці гауссіанів, визначника гессіана та гессіанно-лапласіанного оператора (див. також гаррісів афінний та афінний гессіанний).

Виявлячі просторово-часових плям

Віллемс та ін. та Ліндеберг розширили визначник гессіана на об'єднаний простір-час, що дало наступний масштабонормований диференціальний вираз:

$\det(H_{(x,y,t),\mathrm {norm} }L)=s^{2\gamma _{s}}\tau ^{\gamma _{\tau }}\left(L_{xx}L_{yy}L_{tt}+2L_{xy}L_{xt}L_{yt}-L_{xx}L_{yt}^{2}-L_{yy}L_{xt}^{2}-L_{tt}L_{xy}^{2}\right).$

У праці Віллемса та ін. було використано простіший вираз, що відповідає $\gamma _{s}=1$ та $\gamma _{\tau }=1$. У Ліндеберга було показано, що $\gamma _{s}=5/4$ та $\gamma _{\tau }=5/4$ дають кращі масштабообиральні властивості в тому сенсі, що обирані рівні масштабу, отримувані з просторово-часової гауссової плями з просторовим протяжністю $s=s_{0}$ й часовою тривалістю $\tau =\tau _{0}$, ідеально відповідатимуть просторовій протяжності та часовій тривалості цієї плями, з виконанням обирання масштабу шляхом виявляння просторово-часових масштабопросторових екстремумів цього диференціального виразу.

Ліндеберг розширив оператор Лапласа на просторово-часові відеодані, що дало наступні два просторово-часові оператори, які також становлять моделі рецептивних полів нейронів БКЯ без запізнювання і з запізнюванням:

$\partial _{t,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\tau ^{\gamma _{\tau }/2}(L_{xxt}+L_{yyt}),$

$\partial _{tt,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\tau ^{\gamma _{\tau }}(L_{xxtt}+L_{yytt}).$

Для першого оператора потрібні властивості вибору масштабу $\gamma _{s}=1$ та $\gamma _{\tau }=1/2$, якщо ми хочемо, щоби цей оператор набував свого максимального значення над просторово-часовими масштабами на рівні просторово-часового масштабу, який відображає просторову протяжність і часову тривалість гауссової плями, яка з'являється. Для другого оператора потрібні властивості вибору масштабу $\gamma _{s}=1$ та $\gamma _{\tau }=3/4$, якщо ми хочемо, щоби цей оператор набував свого максимального значення над просторово-часовими масштабами на рівні просторово-часового масштабу, що відображає просторову протяжність і часову тривалість гауссової плями, яка зблимує.

Плями відтінків сірого, дерева плям відтінків сірого та масштабопросторові плями

Природний підхід до виявляння плям — пов'язувати яскраву (темну) пляму з кожним локальним максимумом (мінімумом) ландшафту яскравості. Проте головна проблема такого підходу полягає у високій чутливості локальних екстремумів до шуму. Щоби розв'язати цю проблему, Ліндеберг (1993, 1994) дослідив задачу виявляння локальних максимумів з обширом на кількох масштабах у просторі масштабів. З кожним локальним максимумом було пов'язувано область із просторовим обширом, який визначали за аналогією з вододілом, а також локальний контраст, який визначали з так званої розмежувальної сідлової точки. Локальний екстремум із визначеним таким чином обширом називали плямою відтінків сірого (англ. grey-level blob). Більше того, продовжуючи аналогію вододілу за межами розмежувальної сідлової точки, було визначено дерево плям відтінків сірого (англ. grey-level blob tree), щоби вловлювати вкладену топологічну структуру наборів рівнів у ландшафті яскравості чином, інваріантним до афінних деформацій в області зображення та монотонних перетворень яскравості. Через дослідження того, як ці структури розгортаються на більших масштабах, було введено поняття масштабопросторових плям (англ. scale-space blobs). Крім локального контрасту та обширу, ці масштабопросторові плями також вимірювали стійкість структур зображення у просторі масштабів, вимірюючи їхню масштабопросторову тривалість життя (англ. scale-space lifetime).

Було зроблено припущення, що отримувані таким чином описувачі особливих областей та масштабів, з відповідними рівнями масштабу, визначеними з масштабів, на яких унормовані показники вираженості плями досягали свого максимуму за масштабами, можливо використовувати для скеровування іншої первинної зорової обробки. Було розроблено ранній прототип спрощених зорових систем, де такі особливі області та описувачі масштабу було використано для спрямовування зосередження уваги активної зорової системи. І хоч завдяки нинішнім знанням у галузі комп'ютерного зору конкретну методику, використану в цих прототипах, могло би бути суттєво покращено, цей загальний підхід в цілому все ще чинний, наприклад у тому, як нині використовують локальні екстремуми масштабонормованого лапласіана над масштабами для надавання інформації про масштаб іншим зоровим процесам.

Алгоритм Ліндеберга виявляння плям відтінків сірого від на основі вододілів

З метою виявляння плям відтінків сірого (локальних екстремумів з обширом) за аналогією з вододілом, Ліндеберг розробив алгоритм, що ґрунтується на попередньому сортуванні пікселів, альтернативно з'єднаних областей, які мають однакову яскравість, у порядку зменшення значень яскравості. Потім проводили порівняння між найближчими сусідами або пікселів, або пов'язаних областей.

Для простоти розгляньмо випадок виявляння яскравих плям відтінків сірого, і нехай позначення «вищий сусід» означає «сусідній піксель, що має вищий рівень сірого». Тоді на будь-якому етапі алгоритм (що здійснюється в порядку зменшення значень яскравості) ґрунтується на наступних правилах класифікації:

1. Якщо область не має вищого сусіда, то це локальний максимум, і він буде зародком плями. Встановити прапорець, що дозволить цій плямі рости.
2. Інакше, якщо вона має хоч одного вищого сусіда, який є тлом, то вона не може бути частиною жодної плями й мусить бути тлом.
3. Інакше, якщо вона має понад одного вищого сусіда, і якщо ці вищі сусіди є частинами різних плям, то вона не може бути частиною жодної плями, й мусить бути тлом. Якщо якомусь із цих вищих сусідів все ще дозволено рости, зніміть їхній прапорець, що дозволяв їм рости.
4. Інакше вона має одного чи більше вищих сусідів, що є частинами однієї плями. Якщо цій плямі все ще дозволено рости, то поточну область слід включити як частину цієї плями. В іншому випадку цю область слід призначити тлом.

Порівняно з іншими методами вододілу, заливання в цьому алгоритмі припиняється, щойно рівень яскравості падає нижче значення так званої розмежувальної сідлової точки, пов'язаної з локальним максимумом. Проте поширити цей підхід на інші типи вододілових конструкцій досить просто. Наприклад, виходячи за межі першої точки розмежування, можливо будувати «дерево плям відтінків сірого». Більше того, метод виявляння плям відтінків сірого було вбудовано до масштабопросторового подання для виконання на всіх рівнях масштабу, що дає в результаті подання, назване масштабопросторовим первинним ескізом (англ. scale-space primal sketch).

Цей алгоритм з його застосуваннями в комп'ютерному баченні описано докладніше в дисертації Ліндеберга, а також у монографії з теорії простору масштабів, що частково ґрунтується на цій праці. Раніші подання цього алгоритму також можливо знайти в . Докладніші режими застосування виявляння плям відтінків сірого та масштабопросторового первинного ескізу до комп'ютерного бачення та аналізу медичних зображень наведено в .

Максимально стабільні екстремумні області (МСЕО)

Матас та ін. (2002) хотіли визначити описувачі зображень, що є надійними за перетворень перспективи. Вони вивчали набори рівнів у ландшафті яскравості та вимірювали, наскільки стабільними вони були за виміром яскравості. Виходячи з цієї ідеї, вони визначили поняття максимально стабільних екстремумних областей (англ. maximally stable extremal regions) і показали, як ці описувачі зображень можливо використовувати як ознаки в зображенні для стереоузгодження.

Між цим поняттям та вищезгаданим поняттям дерева плям відтінків сірого існують тісні зв'язки. Максимально стабільні екстремумні області можливо розглядати як явне створення конкретної підмножини дерева плям відтінків сірого для подальшої обробки.

Див. також

• Виділяння плям
• Виявляння кутів
• Афінне пристосовування форми
• Простір масштабів
• Виявляння хребтів
• Виявляння особливих точок
• Виявляння ознак (комп'ютерне бачення)
• Гаррісів афінний виявляч областей
• Гессіанний афінний виявляч областей
• Виявляч хребтів за головною кривиною

Література

• H. Bay; T. Tuytelaars & L. van Gool (2006). SURF: Speeded Up Robust Features. Proceedings of the 9th European Conference on Computer Vision, Springer LNCS volume 3951, part 1. с. 404—417. Архів оригіналу за 6 липня 2011. Процитовано 1 травня 2022. (англ.)
• L. Bretzner & T. Lindeberg (1998). Feature Tracking with Automatic Selection of Spatial Scales (abstract page). Computer Vision and Image Understanding. 71 (3): 385—392. doi:10.1006/cviu.1998.0650. (англ.)
• T. Lindeberg (1993). Detecting Salient Blob-Like Image Structures and Their Scales with a Scale-Space Primal Sketch: A Method for Focus-of-Attention. International Journal of Computer Vision. 11 (3): 283—318. doi:10.1007/BF01469346. S2CID 11998035. Архів оригіналу (abstract page) за 1 травня 2022. Процитовано 1 травня 2022. (англ.)
• T. Lindeberg (1994). Scale-Space Theory in Computer Vision. Springer. ISBN 978-0-7923-9418-1. Архів оригіналу за 30 листопада 2020. Процитовано 1 травня 2022. (англ.)
• T. Lindeberg (1998). Feature detection with automatic scale selection. International Journal of Computer Vision. 30 (2): 77—116. doi:10.1023/A:1008045108935. S2CID 723210. Архів оригіналу (abstract page) за 1 травня 2022. Процитовано 1 травня 2022. (англ.)
• Lindeberg, T.; Garding, J. (1997). Shape-adapted smoothing in estimation of 3-{D} depth cues from affine distortions of local 2-{D} structure. Image and Vision Computing. 15 (6): 415—434. doi:10.1016/S0262-8856(97)01144-X. (англ.)
• Lindeberg, T. (2008). Scale-space. У Wah, Benjamin (ред.). Encyclopedia of Computer Science and Engineering. Т. IV. John Wiley and Sons. с. 2495—2504. doi:10.1002/9780470050118.ecse609. ISBN 978-0-470-05011-8. (англ.)
• D. G. Lowe (2004). Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision. 60 (2): 91—110. CiteSeerX 10.1.1.73.2924. doi:10.1023/B:VISI.0000029664.99615.94. S2CID 221242327. (англ.)
• J. Matas; O. Chum; M. Urban & T. Pajdla (2002). Robust wide baseline stereo from maximally stable extremum regions (PDF). British Machine Vision Conference. с. 384—393. (англ.)
• K. Mikolajczyk; C. Schmid (2004). Scale and affine invariant interest point detectors (PDF). International Journal of Computer Vision. 60 (1): 63—86. doi:10.1023/B:VISI.0000027790.02288.f2. S2CID 1704741. (англ.)