Максимально стабільні екстремумні області

У комп'ютернім баченні максима́льно стабі́льні екстре́мумні о́бласті (МСЕО, англ. maximally stable extremal regions, MSER) використовують як метод виявляння плям на зображеннях. Цю методику запропонували Матас^[cs] зі співавт.^[1] для пошуку відповідностей^[en] між елементами на двох зображеннях з різними точками огляду. Цей метод виділяння вичерпного числа відповідних елементів зображень допомагає у широкобазовому зіставлянні (англ. wide-baseline matching), що дало кращі алгоритми стереозіставляння та розпізнавання об’єктів^[en].

Зображення ${\displaystyle I}$ це відображення ${\displaystyle I:D\subset \mathbb {Z} ^{2}\to S}$. Екстремумні області на зображеннях визначені добре, якщо:

1. ${\displaystyle S}$ цілком упорядкована (має скрізь визначене, антисиметричне та транзитивне бінарне відношення ${\displaystyle \leq }$).
2. Визначено відношення суміжності ${\displaystyle A\subset D\times D}$. Позначуватимемо, що дві точки суміжні, через ${\displaystyle pAq}$.

Область ${\displaystyle Q}$ це суміжна (або зв'язна) підмножина ${\displaystyle D}$. (Для будь-яких ${\displaystyle p,q\in Q}$ існує така послідовність ${\displaystyle p,a_{1},a_{2},..,a_{n},q}$, що ${\displaystyle pAa_{1},a_{1}Aa_{2},\dots ,a_{n-1}Aa_{n},a_{n}Aq}$.) Зауважте, що за цього визначення область може містити «діри» (наприклад, кільцеподібна область зв'язна, але її внутрішній круг це не частина ${\displaystyle Q}$).

(Зовнішня) межа області ${\displaystyle \partial Q=\{q\in D\setminus Q:\exists p\in Q:qAp\}}$, що означає, що межа ${\displaystyle \partial Q}$ області ${\displaystyle Q}$ це набір пікселів, суміжних щонайменше з одним пікселем ${\displaystyle Q}$, але не належних до ${\displaystyle Q}$. Знов-таки, у випадку областей з «дірами» межа області не зобов'язана бути зв'язною підмножиною ${\displaystyle D}$ (кільце має внутрішню та зовнішню межі, що не перетинаються).

Екстремумна область ${\displaystyle Q\subset D}$ це така область, що або для будь-якого ${\displaystyle p\in Q,q\in \partial Q:I(p)>I(q)}$ (область максимальної яскравості), або для будь-якого ${\displaystyle p\in Q,q\in \partial Q:I(p)<I(q)}$ (область мінімальної яскравості). Оскільки ${\displaystyle S}$ цілком впорядкована, ми можемо переформулювати ці умови як ${\displaystyle \min(I(p))>\max(I(q))}$ для області максимальної яскравості, та ${\displaystyle \max(I(p))<\min(I(q))}$ для області мінімальної яскравості відповідно. У цьому вигляді ми можемо використовувати поняття порогового значення яскравості, яке розділює область та її межу.

Максимально стабільна екстремумна область Нехай ${\displaystyle Q_{i}}$ це така екстремумна область, що всі точки на ній мають яскравість, меншу за ${\displaystyle i\in S}$. Зауважте, що ${\displaystyle Q_{i}\subset Q_{i+\Delta }}$ для всіх додатних ${\displaystyle \Delta \in S}$. Екстремумна область ${\displaystyle Q_{i*}}$ максимально стабільна тоді й лише тоді, коли ${\displaystyle |Q_{i+\Delta }\setminus Q_{i-\Delta }|/|Q_{i}|}$ має локальний мінімум в ${\displaystyle i*}$ . (Тут ${\displaystyle |\cdot |}$ позначує потужність). ${\displaystyle \Delta \in S}$ тут параметр методу.

Це рівняння перевіряє області, які лишаються стабільними над певним числом порогів. Якщо область ${\displaystyle Q_{i+\Delta }}$ не значно більша за область ${\displaystyle Q_{i-\Delta }}$, то область ${\displaystyle Q_{i}}$ беруть за максимально стійку.

Це поняття можливо простіше пояснити порогуванням. Усі пікселі нижче певного порогу «чорні», а вище або рівні — «білі». Для заданого первинного зображення, якщо породжують таку послідовність зображень результатів порогування ${\displaystyle I_{t}}$, що кожне зображення ${\displaystyle t}$ відповідає зростальному порогу t, то спочатку буде видно біле зображення, а потім з'являтимуться й ростимуть «чорні» плями, що відповідають локальним мінімумам яскравості. Максимальну стабільну екстремумну область знайдено, коли розмір однієї з цих чорних областей виявляється таким самим (або майже таким самим), як на попередньому зображенні.

Ці «чорні» плями згодом зливатимуться, доки не почорніє все зображення. Множина всіх зв'язних складових у цій послідовності це множина всіх екстремумних областей. У цьому сенсі поняття МСЕО пов'язане з поняттям дерева складових зображення.^[2] Дерево складових справді забезпечує простий спосіб втілення МСЕО.^[3]

Екстремумні області (англ. extremal regions) в цьому контексті мають дві важливі властивості, відповідно до яких ця множина замкнена відносно…

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

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

• Інваріантність щодо афінного перетворення яскравостей зображення
• Коваріантність щодо (безперервного) перетворення зі збереженням суміжності ${\displaystyle T:D\to D}$ в області зображення
• Стабільність: обирають лише області, опора (англ. support) яких майже однакова в якомусь діапазоні порогових значень.
• Багатомасштабне виявляння без жодного згладжування, виявляється як тонка, так і велика структура.
  Зауважте, проте, що виявляння МСЕО в піраміді масштабів покращує відтворюваність та кількість відповідностей над змінами масштабу.^[4]
• Множину всіх екстремумних областей можливо злічити в гіршому випадку ${\displaystyle O(n)}$, де ${\displaystyle n}$ це число пікселів у зображенні.^[5]

Миколайчик зі співавт.^[6] дослідили шість виявлячів областей (гаррісів афінний, гессіанний афінний, МСЕО, області на основі контурів, екстремумів яскравості, та опуклісні області^[en]). Нижче наведено підсумок продуктивності МСЕО у порівнянні з іншими п'ятьма.

• Густина областей — у порівнянні з іншими, МСЕО пропонують найбільшу різноманітність, виявляючи близько 2600 областей для сцени з текстурованим розмиттям, та 230 для сцени зі зміною освітлення, і різноманітність в цілому вважають доброю. Також, у цій перевірці МСЕО мали відтворюваність 92 %.
• Розмір області — МСЕО, як правило, виявляли багато малих областей порівняно з великими, які частіше затулені, або не охоплюють пласку частину сцени. Хоча великі області може бути дещо легше зіставляти.
• Зміна точки огляду — МСЕО перевершують п'ять інших виявлячів областей як на первинних зображеннях, так і на зображеннях із повторюваними текстурними мотивами.
• Зміна масштабу — після гессіанного афінного виявляча, МСЕО посідають друге місце за змінами масштабу та обертанням у площині.
• Розмиття — МСЕО виявилися найчутливішими до такого типу змін у зображенні, єдиної області, у якій цей тип виявляння невправний.
  Проте зауважте, що в цьому оцінюванні не використовували виявляння з багатьма роздільностями, яке, як було показано, покращує відтворюваність за розмиття.
• Зміна освітлення — МСЕО показали найвищу оцінку відтворюваності для цього типу сцен, решта теж мають добру робастність.

МСЕО послідовно показували найвищий результат у багатьох перевірках, доводячи, що вони надійний виявляч областей.^[6]

Первинний алгоритм Матаса зі співавт.^[1] займає ${\displaystyle O(n\,\log(\log(n)))}$ від числа пікселів ${\displaystyle n\,}$. Він працює, спершу впорядковуючи пікселі за яскравістю. Це займає ${\displaystyle O(n)\,}$ часу, з використанням BINSORT. Після впорядкування пікселі позначують на зображенні, а перелік зростальних та об'єднуваних складових та їхніх площ підтримують за допомогою алгоритму неперетинних множин. Це займає ${\displaystyle O(n\,\log(\log(n)))}$ часу. На практиці ці кроки дуже швидкі. У процесі цього зберігають площу кожної зв'язаної складової як функцію яскравості, створюючи структуру даних. Злиття двох складових розглядають як припинення існування меншої складової й вставляння всіх її пікселів до більшої. Серед екстремумних областей «максимально стабільні» ті, що відповідають порогам, де відносна зміна площі як функція відносної зміни порогу перебуває в локальному мінімумі, тобто МСЕО це частини зображення, де локальне перетворення на бінарне зображення стабільне протягом великого діапазону порогів.^[1][6]

Дерево складових — це набір усіх зв'язаних складових порогових значень зображення, впорядкованих за включенням. Ефективні (квазілінійні незалежно від діапазону ваг) алгоритми для його обчислення існують. Таким чином, ця структура пропонує простий спосіб втілення МСЕО.^[3]

Пізніше Ністер та Стівеніус запропонували метод, справді (якщо вага це малі цілі числа) щонайгірше ${\displaystyle O(n)\,}$,^[5] також набагато швидший на практиці. Він подібний алгоритмові Ф. Салембієра зі співавт.^[7]

Мета цього алгоритму — зіставляти МСЕО, щоби встановлювати точки відповідності між зображеннями. Спершу області МСЕО обчислюють на зображенні яскравості (МСЕО+) й на інвертованому зображенні (МСЕО−). Області вимірювання обирають у кількох масштабах: розмір фактичної області, 1,5×, 2× та 3× масштабована опукла оболонка області. Зіставляння виконують робастним чином, тому краще підвищувати відмітність великих областей, не зазнаючи серйозного впливу затуляння чи непланарності попереднього зображення області. Вимірювання, зроблене з майже пласкої ділянки сцени, зі стабільним інваріантним описом, називають «добрим вимірюванням» (англ. 'good measurement'). Нестабільні вимірювання, або ті, що перебувають на непласких поверхнях або розривах, називають «зіпсованими вимірюваннями» (англ. 'corrupted measurements'). Робастну подібність обчислюють так: Для кожного ${\displaystyle M_{A}^{i}}$ в області ${\displaystyle A}$ знаходять ${\displaystyle k}$ областей ${\displaystyle B_{1},\dots ,B_{k}}$ з іншого зображення з відповідним ${\displaystyle i}$-м вимірюванням ${\displaystyle M_{B_{1}}^{i},\dots ,M_{B_{k}}^{i}}$, найближчим до ${\displaystyle M_{A}^{i}}$, і здійснюють голосування, що пропонує відповідність ${\displaystyle A}$ кожній з ${\displaystyle B_{1},\dots ,B_{k}}$. Голоси підсумовують за всіма вимірюваннями, й за допомогою аналізу ймовірностей можливо обирати «добрі вимірювання», оскільки «зіпсовані вимірювання», ймовірно, розподілять свої голоси випадковим чином. Застосовуючи RANSAC до центрів тяжіння областей, можливо обчислювати грубу епіполярну геометрію. Обчислюють афінне перетворення між парами потенційно відповідних областей, відповідності визначають його з точністю до обертання, яке потім визначають епіполярними лініями. Потім області фільтрують, й обирають ті, кореляція трансформованих зображень яких перевищує порогове значення. Знову застосовують RANSAC з вужчим порогом, й оцінюють остаточну епіполярну геометрію за восьмиточковим алгоритмом.

Цей алгоритм можливо перевіряти тут (зіставляння, обмежені епіполярною або гомографічною геометрією): WBS Image Matcher

Чень використовував алгоритм МСЕО для виявлення тексту, поєднуючи його з контурами Кенні. Контури Кенні використовують, щоби допомогти впоратися зі слабкістю МСЕО до розмиття. Спершу застосовують МСЕО до відповідного зображення, щоби визначити області символів. Щоби покращити області МСЕО, будь-які пікселі за межами, утвореними контурами Кенні, видаляють. Відділювання останніх, забезпечуване контурами, значно підвищує зручність використання МСЕО для виділяння розмитого тексту.^[8]

Альтернативним використанням МСЕО у виявлянні тексту є праця Ши з використанням графової моделі. Цей метод, знов-таки, застосовує МСЕО до зображення для створення попередніх областей. Потім їх використовують для побудови графової моделі на основі відстані положення та відстані кольору між кожними МСЕО, що розглядають як вузол. Далі вузли розділюють на передній план і тло за допомогою функцій витрат. Однією з функцій витрат є співвідношення відстані від вузла до переднього плану та тла. Інша штрафує вузли за значну відмінність від сусіда. Коли їх мінімізовано, граф розрізають^[en], щоби відокремити текстові вузли від нетекстових.^[9]

Нейман, щоб уможливити виявляння тексту в загальній сцені, використовує алгоритм МСЕО в різноманітних проєкціях. На додачу до проєкції яскравості відтінків сірого він використовує канали червоного, синього та зеленого кольорів для виявлення областей тексту, що відрізняються за кольором, але не обов'язково за яскравістю відтінків сірого. Цей метод дозволяє виявляти більше тексту, ніж за допомогою лише функцій МСЕО+ та МСЕО−, за які йшлося вище.^[10]

• Алгоритм МСЕО було пристосовано для кольорових зображень шляхом заміни порогового значення функції яскравості агломераційним кластеруванням на основі градієнтів кольорів.^[11]
• Алгоритм МСЕО можливо використовувати для виявляння областей на основі кольору, а не яскравості. Це зроблено Чавесом шляхом створення функції яскравості для червоного, зеленого та синього кольорів у просторі кольорів HSV. Потім алгоритм МСЕО виконують п'ять разів; над трьома псевдояскравостями кольорів, а відтак і над яскравостями відтінків сірого за допомогою стандартних функцій МСЕО+ та МСЕО−.^[12]
• Алгоритм МСЕО можливо використовувати для відстежування кольорових об'єктів, виконуючи виявляння МСЕО на відстані Махаланобіса до розподілу кольорів.^[3]
• Виявляючи МСЕО в різних роздільностях, можливо покращити робастність до розмиття та зміни масштабу.

• Описувачі форми для максимально стабільних екстремумних областей (англ.)
• Ефективне відстежування максимально стабільних екстремумних областей (МСЕО). (англ.)
• N-деревні неперетинномножинні ліси для максимально стабільних екстремумних областей (англ.)
• Відео Google та групування на рівні об'єктів для відеокадрів (англ.)
• Реальночасове виділяння максимально стабільних екстремумних областей на ПКВМ (англ.)
• Максимально стабільні колірні області для розпізнавання та зіставляння (англ.)

• Виявляння плям
• Виявляння ознак (комп'ютерне бачення)

• VLFeat, відкрита бібліотека комп'ютерного бачення мовою C (з інтерфейсом MEX^[en] для MATLAB), включно зі втіленням МСЕО
• OpenCV, відкрита бібліотека комп'ютерного бачення мовами C/C++, включно зі втіленням лінійночасових МСЕО
• Дослідження відтворюваності виявлячів, двійкові файли Крістіана Миколайчика (Win/Linux для обчислення МСЕО/гаррісового афінного… . Двійковий код, використаний в його дослідженні відтворюваності.
• Лінійночасове втілення МСЕО, Чарльз Дюбо, втілення МСЕО як виявляча плям, мовою C++