До виявля́ння ко́нтурів () належать різноманітні математичні методи, спрямовані на виявляння ко́нтурів (), кривих у цифровому зображенні, на яких яскравість зображення змінюється різко, або, формальніше, має . Аналогічна задача пошуку розривів в одновимірних сигналах відома як (), а задача знаходження розривів сигналу в часі відома як (). Виявляння контурів — один з основних інструментів в обробці зображень, машинному та комп'ютерному баченні, особливо в областях виявляння та виділяння ознак.
Обґрунтування
Метою виявляння різких змін яскравості зображення є фіксування важливих подій та змін у властивостях світу. Можливо показати, що за досить загальних припущень стосовно моделі формування зображення розриви яскравості зображення, ймовірно, відповідають:H.G. Barrow and J.M. Tenenbaum (1981) "Interpreting line drawings as three-dimensional surfaces", Artificial Intelligence, vol 17, issues 1–3, pages 75–116.
розривам у глибині, розривам у спрямуванні поверхні, змінам у властивостях матеріалу та відхиленням в освітленні сцени.
В ідеальному випадку результатом застосування до зображення виявляння контурів може бути набір з'єднаних кривих, що позначують межі об'єктів, межі забарвлення поверхонь, а також усі криві, що відповідають розривам у спрямуванні поверхонь. Таким чином, застосування алгоритму виявляння контурів до зображення може значно зменшувати кількість даних, що підлягають обробці, й відтак може відфільтровувати інформацію, яку можна розцінювати як менш значущу, зберігаючи при цьому важливі структурні властивості зображення. Якщо крок виявляння контурів успішний, то подальшу задачу інтерпретування інформаційного вмісту первісного зображення може бути істотно спрощено. Проте отримувати такі ідеальні контури в картинах реального світу середньої складності можливо не завжди.
Контури, виділені з нетривіальних зображень, часто пошкоджено фрагментацією, що означає, що криві контурів не з'єднані, відсутні відрізки контурів, а також є хибні контури (), які не відповідають досліджуваному явищу в зображенні, що ускладнює подальшу задачу інтерпретування даних зображення.T. Lindeberg (1998) "Edge detection and ridge detection with automatic scale selection", International Journal of Computer Vision, 30, 2, pages 117–154.
Виявляння контурів є одним з основних кроків в обробці зображень, аналізі зображень, розпізнаванні образів у зображеннях, та в методиках комп'ютерного бачення.
Властивості контурів
Контури, виділені з двовимірного зображення тривимірної сцени, можливо класифікувати як залежні від точки огляду (), або як незалежні від неї. Незалежний від точки огляду контур зазвичай відображає притаманні властивості тривимірних об'єктів, такі як забарвлення поверхні та її форма. Залежний від точки огляду контур може змінюватися за зміни точки огляду, і зазвичай відображає геометрію сцени, таку як затуляння одного об'єкту іншим.
Типовий контур може бути, наприклад, межею між областями червоного та жовтого кольорів. З іншого боку, лінія (яку може бути виділено виявлянням хребтів) може бути невеликою кількістю пікселів відмінного кольору на в іншому незмінному тлі. Тому зазвичай для лінії може бути по одному контуру з кожного з її боків.
Проста модель контуру
Хоча в певних працях розглядали виявляння ідеальних сходинкових контурів, контури, отримувані з природних зображень, зазвичай зовсім не є ідеальними сходинковими контурами. Натомість, вони зазвичай уражені одним або кількома з наступних явищ:
фокусним розмиттям, спричинюваним скінченною глибиною різкості та скінченною функцією розсіювання точки. напівтіньовим розмиттям, викликаним тінями, створюваними джерелами світла ненульового радіусу. затіненням на гладенькому об'єкті
Як найпростіше розширення ідеальної моделі сходинкового контуру для моделювання ефектів розмиття контурів у практичних застосуваннях багато дослідників використовували гауссово згладжений сходинковий контур (функцію похибки).W. Zhang and F. Bergholm (1997) "Multi-scale blur estimation and edge type classification for scene analysis ", International Journal of Computer Vision, vol 24, issue 3, Pages: 219–250. Таким чином, одновимірне зображення , що має рівно один контур, розташований в , можна моделювати як
Ліворуч від контуру яскравість , а праворуч від контуру — . Масштабний коефіцієнт називають масштабом розмиття контуру. В ідеалі цей параметр масштабу слід налаштувати відповідно до якості зображення, щоб уникати руйнування істинних контурів у ньому.
Чому це нетривіальне завдання
Щоби проілюструвати, чому виявляння контурів не є тривіальним завданням, розгляньмо задачу виявлення контурів у наступному одновимірному сигналі. Тут ми можемо інтуїтивно сказати, що має бути контур між 4-м та 5-м пікселями.
5 7 6 4 152 148 149
Якби різниця яскравості між 4-м та 5-м пікселями була нижчою, а різниці яскравості між сусідніми прилеглими пікселями — вищими, то було би не так легко сказати, що у відповідній області має бути контур. Понад те, можливо було би стверджувати, що це випадок, у якому є декілька контурів.
5 7 6 41 113 148 149
Отже, чітко вказати певний поріг того, наскільки великою має бути зміна яскравості між двома сусідніми пікселями, щоби ми могли сказати, що між цими пікселями має бути контур, не завжди просто. Справді, це одна з причин, чому виявляння контурів може бути нетривіальною задачею, якщо тільки об'єкти в сцені не дуже прості, а умови освітлення можливо добре контролювати (див., наприклад, контури, виділені в зображенні з дівчинкою вище).
Підходи
Існує багато методів виявляння контурів, але більшість із них можливо згрупувати у дві категорії: на основі пошуку, та на основі . Методи на основі пошуку виявляють контури, спочатку обчислюючи міру вираженості контуру (), як правило, як вираження першої похідної, таке як величина градієнта, а потім шукають локальні напрямні максимуми величини градієнта з використанням обчисленої оцінки локального спрямування контуру, зазвичай, напряму градієнта. Методи на основі перетину нуля, щоби знаходити контури, шукають перетини нуля вираженням другої похідної, обчисленим із зображення, зазвичай, перетини нуля лапласіаном, або перетини нуля нелінійним диференціальним виразом. Як етап попередньої обробки для виявляння контурів майже завжди застосовують етап згладжування, як правило, гауссового (див. також знижування шуму).
Опубліковані методи виявляння контурів переважно відрізняються типами застосовуваних фільтрів згладжування та способами обчислення міри вираженості контуру. Оскільки багато методів виявляння контурів покладаються на обчислення градієнтів зображення, вони також відрізняються типами фільтрів, застосовуваних для обчислення оцінок градієнта в напрямах x та y.
Огляд низки різних методів виявляння контурів є в (Ziou and Tabbone 1998);D. Ziou and S. Tabbone (1998) "Edge detection techniques: An overview", International Journal of Pattern Recognition and Image Analysis, 8(4):537–559, 1998 див. також енциклопедичні статті про виявляння контурів в «Енциклопедії з математики» та «Енциклопедії з інформатики та інженерії».J. M. Park and Y. Lu (2008) "Edge detection in grayscale, color, and range images", in B. W. Wah (editor) Encyclopedia of Computer Science and Engineering, doi 10.1002/9780470050118.ecse603
Кенні
розглядав математичну задачу виведення оптимального згладжувального фільтра за заданого критерію виявляння, локалізації та мінімізації множинних відгуків на один контур.J. Canny (1986) "A computational approach to edge detection ", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 8, pages 679–714. Він показав, що оптимальним фільтром за цих припущень є сума чотирьох експоненційних доданків. Він також показав, що цей фільтр можливо добре наблизити першими похідними гауссіанів. Кенні також ввів поняття пригнічування немаксимумів (), яке означає, що, за заданих фільтрів попереднього згладжування, точки контурів визначаються як точки, в яких величина градієнта набуває локального максимуму в напрямі градієнта. Шукати перетин нуля другою похідною вздовж напряму градієнта вперше запропонував .R. Haralick, (1984) "Digital step edges from zero crossing of second directional derivatives ", IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(1):58–68. Знадобилося менше двох десятиліть, щоби знайти сучасне геометричне варіаційне значення для цього оператора, яке пов'язує його з алгоритмом Марра — Гілдрет виявляння контурів (перетин нуля лапласіаном). Це спостереження було представлено та .R. Kimmel and A.M. Bruckstein (2003) "On regularized Laplacian zero crossings and other optimal edge integrators", International Journal of Computer Vision, 53(3) pages 225–243.
Хоча його працю й було зроблено на початку часів комп'ютерного бачення, алгоритм Кенні виявляння контурів (включно з його різновидами) все ще перебуває на рівні останніх досягнень. & Stockman G. C. (2001) Computer Vision. London etc.: Prentice Hall, Page 326. Алгоритми виявляння контурів, які працюють краще за алгоритм Кенні, зазвичай вимагають більшого обчислювального часу, або більшої кількості параметрів.
Алгоритм Кенні — Деріша було виведено на основі подібних математичних критеріїв, що й алгоритм Кенні, але починаючи з дискретної точки зору, а потім ведучи до набору рекурсивних фільтрів для згладжування зображення замість або гауссових фільтрів.R. Deriche (1987) Using Canny's criteria to derive an optimal edge detector recursively implemented, Int. J. Computer Vision, vol 1, pages 167–187.
Описаний нижче диференціальний алгоритм виявляння контурів можливо розглядати як переформулювання методу Кенні з точки зору диференціальних інваріантів, обчислюваних з масштабопросторового подання, що дає низку переваг з погляду як теоретичного аналізу, так і субпіксельного втілення. У цьому аспекті було показано, що добрим вибором для виділяння меж у природних сценах є .Sylvain Fischer, Rafael Redondo, Laurent Perrinet, Gabriel Cristobal. Sparse approximation of images inspired from the functional architecture of the primary visual areas . EURASIP Journal on Advances in Signal Processing, special issue on Image Perception, 2007
Інші методи першого порядку
Для оцінки градієнтів зображення на основі вхідного зображення або його згладженої версії можливо застосовувати різні оператори градієнта. Найпростіший підхід — використовувати центральні різниці:
що відповідає застосуванню до даних зображення наступних фільтрових масок:
Добре відомий і більш ранній оператор Собеля ґрунтується на наступних фільтрах:
За таких оцінок перших похідних зображення величину градієнту відтак обчислюють через
а спрямування градієнта можливо оцінювати через
Інші різницеві оператори першого порядку для оцінювання градієнта зображення було запропоновано в операторі Прюітт, хресті Робертса, операторі Каялі та .
Розмір фільтрів можливо розширювати задля уникання проблеми з розпізнаванням контурів у зображеннях із низьким ССШ. Ціною цієї операції є втрати з точки зору роздільності. Прикладом є розширений оператор Прюітт 7×7.
Порогування та зв'язування
Щойно ми обчислили міру вираженості контуру (зазвичай, величину градієнта), наступним етапом є застосування порогу, щоби вирішити, чи присутні контури в якісь точці зображення. Що нижчий поріг, то більше контурів буде виявлено, й результат буде все вразливішим для шуму та виявляння контурів недоречних особливостей зображення. І навпаки, високий поріг може пропускати ледь вловимі контури, або давати в результаті фрагментовані контури.