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

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

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

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

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

Один із найперших, а також найпоширеніших виявлячів плям ґрунтується на лапласіані гауссіана (ЛГ, Шаблон:Lang-en). Задане вхідне зображення $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)$. Потім обчислюють результат застосування оператора Лапласа

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

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

Простий спосіб отримати багатомасштабовий виявляч плям з автоматичним обиранням масштабу (Шаблон:Lang-en) — розглядати масштабонормований лапласіан

$\underset{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}{\overset{2}{\mathrm{\nabla }}}L=t(L_{xx}+L_{yy})$

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

$(\hat{x},\hat{y};\hat{t})={\mathrm{argmaxminlocal}}_{(x,y;t)}((\underset{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}{\overset{2}{\mathrm{\nabla }}}L)(x,y;t))$.

Зауважте, що це поняття плями забезпечує стисле й математично точне операційне визначення поняття «пляма», яке безпосередньо веде до ефективного й надійного алгоритму виявлення плям. Деякі з основних властивості плям, визначених з масштабопросторових максимумів нормованого лапласіана, полягають у тому, що ці відгуки коваріантні з паралельними перенесеннями, поворотами та змінами масштабу в області зображення. Таким чином, якщо масштабопросторовий максимум передбачається в точці $(x_0,y_0;t_0)$, то за масштабування зображення коефіцієнтом масштабу $s$ масштабопросторовий максимум у зміненому зображенні буде в $(s{x}_0,s{y}_0;s^2{t}_0)$ (Ліндеберг 1998). Ця дуже корисна на практиці властивість означає, що, крім цієї конкретної теми лапласового виявляння плям, локальні максимуми/мінімуми масштабонормованого лапласіана також використовують для обирання масштабу в інших контекстах, таких як виявляння кутів, масштабопристосовне відстежування ознак (Шаблон:Lang-en, Бретцнер та Ліндеберг 1998), масштабоінваріантне ознакове перетворення (Шаблон:Lang-en, Лоу 2004), а також як інші описувачі зображення для зіставляння зображень та Шаблон:Нп.

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

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

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

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

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

$\underset{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}{\overset{2}{\mathrm{\nabla }}}L(x,y;t)\approx \frac{t}{\mathrm{\Delta }t}(L(x,y;t+\mathrm{\Delta }t)-L(x,y;t))$.

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

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

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

$\det H_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}L=t^2(L_{xx}{L}_{yy}-L_{xy}^2)$

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

$(\hat{x},\hat{y};\hat{t})={\mathrm{argmaxlocal}}_{(x,y;t)}((\det H_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}L)(x,y;t))$.

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

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

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

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

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

$\hat{t}={\mathrm{argmaxminlocal}}_t((\underset{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}{\overset{2}{\mathrm{\nabla }}}L)(\hat{x},\hat{y};t))$

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

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

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

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

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

$\det (H_{(x,y,t),\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}L)=s^{2{\gamma }_s}{\tau }^{{\gamma }_{\tau }}(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).$

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

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

${\partial }_{t,\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}(\underset{(x,y),\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}{\overset{2}{\mathrm{\nabla }}}L)=s^{{\gamma }_s}{\tau }^{{\gamma }_{\tau }/2}(L_{xxt}+L_{yyt}),$

${\partial }_{tt,\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}(\underset{(x,y),\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}{\overset{2}{\mathrm{\nabla }}}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) дослідив задачу виявляння локальних максимумів з обширом на кількох масштабах у просторі масштабів. З кожним локальним максимумом було пов'язувано область із просторовим обширом, який визначали за аналогією з вододілом, а також локальний контраст, який визначали з так званої розмежувальної сідлової точки. Локальний екстремум із визначеним таким чином обширом називали плямою відтінків сірого (Шаблон:Lang-en). Більше того, продовжуючи аналогію вододілу за межами розмежувальної сідлової точки, було визначено дерево плям відтінків сірого (Шаблон:Lang-en), щоби вловлювати вкладену топологічну структуру наборів рівнів у ландшафті яскравості чином, інваріантним до афінних деформацій в області зображення та монотонних перетворень яскравості. Через дослідження того, як ці структури розгортаються на більших масштабах, було введено поняття масштабопросторових плям (Шаблон:Lang-en). Крім локального контрасту та обширу, ці масштабопросторові плями також вимірювали стійкість структур зображення у просторі масштабів, вимірюючи їхню масштабопросторову тривалість життя (Шаблон:Lang-en).

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

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

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

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

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

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

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

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

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

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

Див. також

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

Література

• Шаблон:Cite conference Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite conference Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en