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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Плями відтінків сірого)
Перейти до навігації Перейти до пошуку

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

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

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

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

[ред. | ред. код]

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

у певному масштабі для отримання масштабопросторового подання . Потім обчислюють результат застосування оператора Лапласа

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

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

та виявляти масштабопросторові максимуми/мінімуми, що є точками, які є локальними максимумами/мінімумами відносно простору й масштабу одночасно (Ліндеберг 1994, 1998). Таким чином, для заданого дискретного двовимірного вхідного зображення обчислюють тривимірний дискретний масштабопросторовий об'єм , і точку розглядають як яскраву (темну) пляму, якщо значення в ній більше (менше) за значення у всіх її 26 сусідках. Таким чином, одночасне обрання особливих точок на масштабах виконується згідно з

.

Зауважте, що це поняття плями забезпечує стисле й математично точне операційне визначення поняття «пляма», яке безпосередньо веде до ефективного й надійного алгоритму виявлення плям. Деякі з основних властивості плям, визначених з масштабопросторових максимумів нормованого лапласіана, полягають у тому, що ці відгуки коваріантні з паралельними перенесеннями, поворотами та змінами масштабу в області зображення. Таким чином, якщо масштабопросторовий максимум передбачається в точці , то за масштабування зображення коефіцієнтом масштабу масштабопросторовий максимум у зміненому зображенні буде в (Ліндеберг 1998). Ця дуже корисна на практиці властивість означає, що, крім цієї конкретної теми лапласового виявляння плям, локальні максимуми/мінімуми масштабонормованого лапласіана також використовують для обирання масштабу в інших контекстах, таких як виявляння кутів, масштабопристосовне відстежування ознак (англ. scale-adaptive feature tracking, Бретцнер та Ліндеберг 1998), масштабоінваріантне ознакове перетворення (англ. SIFT, Лоу 2004), а також як інші описувачі зображення для зіставляння зображень та розпізнавання об'єктів[en].

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

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

[ред. | ред. код]

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

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

.

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

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

[ред. | ред. код]

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

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

.

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

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

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

[ред. | ред. код]

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

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

У праці Віллемса та ін. було використано простіший вираз, що відповідає та . У Ліндеберга[6] було показано, що та дають кращі масштабообиральні властивості в тому сенсі, що обирані рівні масштабу, отримувані з просторово-часової гауссової плями з просторовим протяжністю й часовою тривалістю , ідеально відповідатимуть просторовій протяжності та часовій тривалості цієї плями, з виконанням обирання масштабу шляхом виявляння просторово-часових масштабопросторових екстремумів цього диференціального виразу.

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

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

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

[ред. | ред. код]

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

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

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

[ред. | ред. код]

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

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

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

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

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

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

[ред. | ред. код]

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

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

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. а б Lindeberg, Tony (2013) "Scale Selection Properties of Generalized Scale-Space Interest Point Detectors", Journal of Mathematical Imaging and Vision, Volume 46, Issue 2, pages 177-210. (англ.)
  2. а б Lindeberg (2013) "Image Matching Using Generalized Scale-Space Interest Points", Scale Space and Variational Methods in Computer Vision, Springer Lecture Notes in Computer Science Volume 7893, 2013, pp 355-367. (англ.)
  3. а б в T. Lindeberg "Image matching using generalized scale-space interest points", Journal of Mathematical Imaging and Vision, volume 52, number 1, pages 3-36, 2015. [Архівовано 1 травня 2022 у Wayback Machine.] (англ.)
  4. T. Lindeberg "Scale invariant feature transform", Scholarpedia, 7(5):10491, 2012. [Архівовано 1 травня 2022 у Wayback Machine.] (англ.)
  5. Geert Willems, Tinne Tuytelaars and Luc van Gool (2008). An efficient dense and scale-invariant spatiotemporal-temporal interest point detector. European Conference on Computer Vision. Springer Lecture Notes in Computer Science. Т. 5303. с. 650—663. doi:10.1007/978-3-540-88688-4_48. (англ.)
  6. а б в Tony Lindeberg (2018). Spatio-temporal scale selection in video data. Journal of Mathematical Imaging and Vision. Т. 60, № 4. с. 525—562. doi:10.1007/s10851-017-0766-9. (англ.)
  7. Lindeberg, T. (1991) Discrete Scale-Space Theory and the Scale-Space Primal Sketch, PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44 Stockholm, Sweden, May 1991. (ISSN 1101-2250. ISRN KTH NA/P--91/8--SE) (The grey-level blob detection algorithm is described in section 7.1) [Архівовано 7 вересня 2019 у Wayback Machine.] (англ.)
  8. Lindeberg, Tony, Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, 1994 [Архівовано 30 листопада 2020 у Wayback Machine.] ISBN 0-7923-9418-6 (англ.)
  9. T. Lindeberg and J.-O. Eklundh, "Scale detection and region extraction from a scale-space primal sketch", in Proc. 3rd International Conference on Computer Vision, (Osaka, Japan), pp. 416--426, Dec. 1990. (See Appendix A.1 for the basic definitions for the watershed-based grey-level blob detection algorithm.) [Архівовано 1 травня 2022 у Wayback Machine.] (англ.)
  10. T. Lindeberg and J.-O. Eklundh, "On the computation of a scale-space primal sketch", Journal of Visual Communication and Image Representation, vol. 2, pp. 55--78, Mar. 1991. (англ.)
  11. Lindeberg, T.: 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, 1993. [Архівовано 1 травня 2022 у Wayback Machine.] (англ.)
  12. Lindeberg, T, Lidberg, Par and Roland, P. E..: "Analysis of Brain Activation Patterns Using a 3-D Scale-Space Primal Sketch", Human Brain Mapping, vol 7, no 3, pp 166--194, 1999. (англ.)
  13. Jean-Francois Mangin, Denis Rivière, Olivier Coulon, Cyril Poupon, Arnaud Cachia, Yann Cointepas, Jean-Baptiste Poline, Denis Le Bihan, Jean Régis, Dimitri Papadopoulos-Orfanos: "Coordinate-based versus structural approaches to brain image analysis". Artificial Intelligence in Medicine 30(2): 177-197 (2004) [Архівовано 21 липня 2011 у Wayback Machine.] (англ.)

Література

[ред. | ред. код]