Виявляння контурів

Джон Кенні розглядав математичну задачу виведення оптимального згладжувального фільтра за заданого критерію виявляння, локалізації та мінімізації множинних відгуків на один контур.[8] Він показав, що оптимальним фільтром за цих припущень є сума чотирьох експоненційних доданків. Він також показав, що цей фільтр можливо добре наблизити першими похідними гауссіанів. Кенні також ввів поняття пригнічування немаксимумів (англ. non-maximum suppression), яке означає, що, за заданих фільтрів попереднього згладжування, точки контурів визначаються як точки, в яких величина градієнта набуває локального максимуму в напрямі градієнта. Шукати перетин нуля другою похідною вздовж напряму градієнта вперше запропонував Гаралік.[9] Знадобилося менше двох десятиліть, щоби знайти сучасне геометричне варіаційне значення для цього оператора, яке пов'язує його з алгоритмом Марра — Гілдрета виявляння контурів (перетин нуля лапласіаном). Це спостереження було представлено Роном Кіммелом та Альфредом Брукштайном.[10]

Хоча його працю й було зроблено на початку часів комп'ютерного бачення, алгоритм Кенні виявляння контурів (включно з його різновидами) все ще перебуває на рівні останніх досягнень.[11] Алгоритми виявляння контурів, які працюють краще за алгоритм Кенні, зазвичай вимагають більшого обчислювального часу, або більшої кількості параметрів.

Алгоритм Кенні — Деріша було виведено на основі подібних математичних критеріїв, що й алгоритм Кенні, але починаючи з дискретної точки зору, а потім ведучи до набору рекурсивних фільтрів для згладжування зображення замість експоненційних або гауссових фільтрів.[12]

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

Для оцінки градієнтів зображення на основі вхідного зображення або його згладженої версії можливо застосовувати різні оператори градієнта. Найпростіший підхід — використовувати центральні різниці:

${\displaystyle {\begin{aligned}L_{x}(x,y)&=-{\frac {1}{2}}L(x-1,y)+0\cdot L(x,y)+{\frac {1}{2}}\cdot L(x+1,y)\\[8pt]L_{y}(x,y)&=-{\frac {1}{2}}L(x,y-1)+0\cdot L(x,y)+{\frac {1}{2}}\cdot L(x,y+1),\end{aligned}}}$

що відповідає застосуванню до даних зображення наступних фільтрових масок:

${\displaystyle L_{y}={\begin{bmatrix}+1/2&0&-1/2\end{bmatrix}}L,\quad L_{x}={\begin{bmatrix}+1/2\\0\\-1/2\end{bmatrix}}L.}$

Добре відомий і більш ранній оператор Собеля ґрунтується на наступних фільтрах:

${\displaystyle L_{y}={\begin{bmatrix}+1&0&-1\\+2&0&-2\\+1&0&-1\end{bmatrix}}L,\quad L_{x}={\begin{bmatrix}+1&+2&+1\\0&0&0\\-1&-2&-1\end{bmatrix}}L.}$

За таких оцінок перших похідних зображення величину градієнту відтак обчислюють через

${\displaystyle |\nabla L|={\sqrt {L_{x}^{2}+L_{y}^{2}}}}$

а спрямування градієнта можливо оцінювати через

${\displaystyle \theta =\operatorname {atan2} (L_{y},L_{x}).}$

Інші різницеві оператори першого порядку для оцінювання градієнта зображення було запропоновано в операторі Прюітт, хресті Робертса, операторі Каялі[14] та операторі Фрая — Чена.

Розмір фільтрів можливо розширювати задля уникання проблеми з розпізнаванням контурів у зображеннях із низьким ССШ. Ціною цієї операції є втрати з точки зору роздільності. Прикладом є розширений оператор Прюітт 7×7.

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

Якщо контур застосовувати лише до зображення величини градієнту, то отримувані контури загалом будуть товстими, й потрібна якась подальша обробка для їхнього витоншування. Проте для контурів, виявляних із придушуванням немаксимумів, криві контурів є тонкими за визначенням, і пікселі контурів можливо зв'язувати в контурний багатокутник за допомогою процедури зв'язування контурів (англ. edge linking, простежування контурів, англ. edge tracking). На дискретній ґратці етап придушування немаксимумів можливо втілювати оцінюванням напряму градієнта за допомогою перших похідних, наступним округлюванням напряму градієнта до кратних 45 градусів, і, зрештою, порівнюванням значень величини градієнта в оціненому напрямі градієнта.

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

Витоншування контурів (англ. edge thinning) — це методика, яку використовують для усування небажаних паразитних точок на контурах у зображенні. Цю методику застосовують після відфільтровування шуму з зображення (за допомогою медіанного, гауссового фільтра тощо), застосування оператора контурів (подібного до описаних вище, Кенні або Собеля) для виявляння контурів, і після згладжування контурів із застосуванням відповідного порогового значення. Воно видаляє всі небажані точки, і, якщо застосовувати його обачно, в результаті утворюються елементи контурів товщиною в один піксель.

Переваги:

1. Рівні та тонкі контури сприяють кращій продуктивності розпізнавання об'єктів.
2. Якщо застосовують перетворення Гафа для виявляння ліній та еліпсів, то витоншування може давати набагато кращі результати.
3. Якщо контур виявляється межею області, то витоншування може легко, без особливої алгебри, давати параметри її зображення, як-от периметр.

Для цього використовують багато популярних алгоритмів, один з яких описано нижче:

1. Обрати тип зв'язності, як-то 8, 6 або 4.
2. Перевагу віддають 8-зв'язності, за якої розглядають усі безпосередні пікселі, що оточують заданий.
3. Вилучити точки з півночі, півдня, сходу та заходу.
4. Зробити це за кілька проходів, тобто, після проходу для півночі використати те саме напівоброблене зображення в іншому проході, й так далі.
5. Вилучати точку, якщо:
   Точка не має сусідів на півночі (у проході для півночі, й на відповідних напрямках для інших проходів).
   Точка не є кінцем лінії.
   Точка ізольована.
   Вилучання точок жодним чином не призведе до роз'єднання їхніх сусідів.
6. Інакше лишити точку.

Кількість проходів за напрямом слід обирати відповідно до бажаного рівня точності.

Деякі оператори виявляння контурів натомість ґрунтуються на других похідних яскравості. Це, по суті, вловлює темп зміни градієнта яскравості. Таким чином, в ідеальному неперервному випадку виявляння перетинів нуля другою похідною вловлює локальні максимуми градієнту.

Ранній оператор Марра — Гілдрета ґрунтується на виявлянні перетинів нуля оператором Лапласа, застосованого до гауссово згладженого зображення. Проте можливо показати, що цей оператор також повертатиме хибні контури, що відповідають локальним мінімумам величини градієнта. Більше того, цей оператор даватиме погану локалізацію на вигнутих контурах. Отже, цей оператор становить сьогодні переважно історичний інтерес.

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

Дотримуючись диференціального геометричного способу вираження вимоги придушування немаксимумів, запропонованого Ліндебергом,[4][15] введімо в кожній точці зображення локальну систему координат ${\displaystyle (u,v)}$, ${\displaystyle v}$-напрям якої паралельний напряму градієнта. Виходячи з припущення, що зображення було попередньо згладжено гауссовим згладжуванням, та було обчислено масштабно-просторове подання ${\displaystyle L(x,y;t)}$ в масштабі ${\displaystyle t}$, ми можемо вимагати, щоби величина градієнта масштабно-просторового подання, яка дорівнює першій напрямній похідній у ${\displaystyle v}$-напрямі ${\displaystyle L_{v}}$, мала у ${\displaystyle v}$-напрямі нульову першу напрямну похідну

${\displaystyle \partial _{v}(L_{v})=0}$

тоді як друга напрямна похідна у ${\displaystyle v}$-напрямі ${\displaystyle L_{v}}$ повинна бути від'ємною, тобто,

${\displaystyle \partial _{vv}(L_{v})\leq 0.}$

Записане як явний вираз у термінах локальних частинних похідних ${\displaystyle L_{x},L_{y},\ldots ,L_{yyy}}$, це визначення контуру можливо виразити як перетин нуля кривими диференціального інваріанта

${\displaystyle L_{v}^{2}L_{vv}=L_{x}^{2}\,L_{xx}+2\,L_{x}\,L_{y}\,L_{xy}+L_{y}^{2}\,L_{yy}=0,}$

що задовольняє умову для знаку на наступному диференціальному інваріанті

${\displaystyle L_{v}^{3}L_{vvv}=L_{x}^{3}\,L_{xxx}+3\,L_{x}^{2}\,L_{y}\,L_{xxy}+3\,L_{x}\,L_{y}^{2}\,L_{xyy}+L_{y}^{3}\,L_{yyy}\leq 0}$,

де ${\displaystyle L_{x},L_{y},\ldots ,L_{yyy}}$ позначують частинні похідні, обчислені з масштабно-просторового подання ${\displaystyle L}$, отриманого згладжуванням первинного зображення гауссовим ядром. Таким чином, контури автоматично отримуватимуться як неперервні криві з субпіксельною точністю. До цих диференціальних і субпіксельних сегментів контурів також можливо застосовувати гістерезисне порогування.

На практиці наближення перших похідних можливо обчислювати за допомогою центральних різниць, як описано вище, тоді як другі похідні можливо обчислювати з масштабно-просторового подання ${\displaystyle L}$ відповідно до:

${\displaystyle {\begin{aligned}L_{xx}(x,y)&=L(x-1,y)-2L(x,y)+L(x+1,y),\\[6pt]L_{xy}(x,y)&={\frac {1}{4}}(L(x-1,y-1)-L(x-1,y+1)-L(x+1,y-1)+L(x+1,y+1)),\\[6pt]L_{yy}(x,y)&=L(x,y-1)-2L(x,y)+L(x,y+1).\end{aligned}}}$

що відповідає таким маскам фільтрів:

${\displaystyle L_{xx}={\begin{bmatrix}1&-2&1\end{bmatrix}}L,\quad L_{xy}={\begin{bmatrix}-1/4&0&1/4\\0&0&0\\1/4&0&-1/4\end{bmatrix}}L,\quad L_{yy}={\begin{bmatrix}1\\-2\\1\end{bmatrix}}L.}$

Вищі похідні для умови третього порядку для знаку можливо отримувати аналогічно.

Недавній розвиток методів виявляння контурів для пошуку місць їхнього розташування використовує підхід частотної області. Методи фазової конгруентності (відомої також як фазова когерентність) намагаються знаходити місця на зображенні, де всі синусоїди в частотній області синфазні. Ці місця загалом відповідатимуть розташуванню того, що сприймається як контур, незалежно від того, чи цей контур являє собою велику зміну яскравості в просторовій області. Ключова перевага цієї методики полягає в тому, що вона добре реагує на махові смуги й уникає хибних спрацьовувань, які зазвичай трапляються навколо дахових контурів. Даховий контур (англ. roof edge) — це розрив у першій похідній профілю яскравості.[16]

Посилення ознак у зображенні (собору Святого Павла в Лондоні) за допомогою фазоворозтягувального перетворення (ФРП). Ліворуч показано первинне зображення, а праворуч — ознаки, виявлені за допомогою ФРП.

Фазоворозтягувальне перетворення, або ФРП (англ. phase stretch transform, PST) — це навіяний фізикою обчислювальний підхід до обробки сигналів та зображень. Однією з його корисних властивостей є виявляння та класифікування ознак.[17][18] ФРП це похідний продукт дослідження дисперсійного перетворення Фур’є з розтягуванням у часі. ФРП перетворює зображення, моделюючи поширення дифракційним середовищем зі сконструйованою тривимірною дисперсійною властивістю (показником заломлення). Ця операція покладається на симетричність дисперсійного профілю, і її можливо розуміти в термінах дисперсійних власних функцій або режимів розтягування.[19] ФРП виконує подібні функції, що й фазовоконтрастна мікроскопія, але на цифрових зображеннях. ФРП застосовне як до цифрових зображень, так і до часових даних, даних часових рядів.

Для підвищення точності виявляння контурів було запропоновано декілька субпіксельних методик, включно з методами допасовування кривої (англ. curve-fitting), на основі моменту (англ. moment-based),[20][21] відбудовними (англ. reconstructive) методами, та методами ефекту часткової площі (англ. partial area effect methods).[22] Ці методи мають різні характеристики. Методи допасовування кривих обчислювально прості, але на них легко впливає шум. Методи на основі моменту використовують інтегральний підхід для зменшення впливу шуму, але в деяких випадках можуть вимагати більше обчислень. Відбудовні методи використовують горизонтальні та вертикальні градієнти для побудови кривої та знаходження піку кривої як субпіксельного контуру. Методи ефекту часткової площі ґрунтуються на гіпотезі, що значення кожного пікселя залежить від площі по обидві сторони контуру всередині цього пікселя, що забезпечує точну індивідуальну оцінку для кожного пікселя контуру. Деякі варіанти методики на основі моменту виявилися найточнішими для ізольованих контурів.[21]

Виявлення контурів на ангіографічному зображенні. Ліворуч розпізнавання контурів зроблено на рівні пікселів. Праворуч субпіксельне виявляння контуру точно визначає контур всередині пікселів.