Перегляд вихідного коду сторінки Виявляння контурів

{{Виявляння ознак (комп'ютерний зір)}}

До '''виявля́ння ко́нтурів''' ({{lang-en|edge detection}}) належать різноманітні [[Математика|математичні]] методи, спрямовані на виявляння '''ко́нтурів''' ({{lang-en|edge}}), [[Крива|кривих]] у [[Цифрове зображення|цифровому зображенні]], на яких [[Сила світла|яскравість зображення]] змінюється різко, або, формальніше, має {{нп|Розрив (математика)|розриви||Discontinuity (mathematics)}}. Аналогічна задача пошуку розривів в одновимірних сигналах відома як ''{{нп|виявляння сходинок|||Step detection}}'' ({{lang-en|step detection}}), а задача знаходження розривів сигналу в часі відома як ''{{нп|виявляння змін|||Change detection}}'' ({{lang-en|change detection}}). Виявляння контурів&nbsp;— один з основних інструментів в [[Обробка зображень|обробці зображень]], [[Машинне бачення|машинному]] та [[Комп'ютерне бачення|комп'ютерному баченні]], особливо в областях [[Виявляння ознак (комп'ютерне бачення)|виявляння]] та [[виділяння ознак]].<ref>{{cite book|last=Umbaugh|first=Scott E|title=Digital image processing and analysis : human and computer vision applications with CVIPtools|year=2010|publisher=CRC Press|location=Boca Raton, FL|isbn=978-1-4398-0205-2|edition=2nd}} {{ref-en}}</ref>

== Обґрунтування ==
[[Файл:Ääretuvastuse_näide.png|міні|500x500пкс| [[Алгоритм Кенні|Виявляння контурів Кенні]], застосоване до фотографії]]

Метою виявляння різких змін яскравості зображення є фіксування важливих подій та змін у властивостях світу. Можливо показати, що за досить загальних припущень стосовно моделі формування зображення розриви яскравості зображення, ймовірно, відповідають:<ref>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. {{ref-en}}</ref><ref name="lin95">{{SpringerEOM| title=Edge detection | id=Edge_detection | oldid=17883 | first=Tony | last=Lindeberg }} {{ref-en}}</ref>

* розривам у глибині,
* розривам у спрямуванні поверхні,
* змінам у властивостях матеріалу та
* відхиленням в освітленні сцени.

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

Контури, виділені з нетривіальних зображень, часто пошкоджено ''фрагментацією'', що означає, що криві контурів не з'єднані, відсутні відрізки контурів, а також є ''хибні контури'' ({{lang-en|false edges}}), які не відповідають досліджуваному явищу в зображенні, що ускладнює подальшу задачу інтерпретування даних зображення.<ref name="lin98">[http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A452310&dswid=386 T. Lindeberg (1998) "Edge detection and ridge detection with automatic scale selection", International Journal of Computer Vision, 30, 2, pages 117–154.] {{Webarchive|url=https://web.archive.org/web/20220206233128/http://kth.diva-portal.org/smash/record.jsf?pid=diva2:452310&dswid=386 |date=6 лютого 2022 }} {{ref-en}}</ref>

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

== Властивості контурів ==

Контури, виділені з двовимірного зображення тривимірної сцени, можливо класифікувати як залежні від точки огляду ({{lang-en|viewpoint}}), або як незалежні від неї.
''Незалежний від точки огляду контур'' зазвичай відображає притаманні властивості тривимірних об'єктів, такі як забарвлення поверхні та її форма.
''Залежний від точки огляду контур'' може змінюватися за зміни точки огляду, і зазвичай відображає геометрію сцени, таку як затуляння одного об'єкту іншим.

Типовий контур може бути, наприклад, межею між областями червоного та жовтого кольорів. З іншого боку, '''[[Лінія (математика)|лінія]]''' (яку може бути виділено [[Виявляння хребтів|виявлянням хребтів]]) може бути невеликою кількістю [[Піксель|пікселів]] відмінного кольору на в іншому незмінному тлі. Тому зазвичай для лінії може бути по одному контуру з кожного з її боків.

== Проста модель контуру ==

Хоча в певних працях розглядали виявляння ідеальних сходинкових контурів, контури, отримувані з природних зображень, зазвичай зовсім не є ідеальними сходинковими контурами. Натомість, вони зазвичай уражені одним або кількома з наступних явищ:

* фокусним розмиттям, спричинюваним скінченною [[Глибина різкості|глибиною різкості]] та скінченною [[Функція розсіювання точки|функцією розсіювання точки]].
* [[Напівтінь|напівтіньовим розмиттям]], викликаним тінями, створюваними джерелами світла ненульового радіусу.
* [[Затінення (комп'ютерна графіка)|затіненням]] на гладенькому об'єкті

Як найпростіше розширення ідеальної моделі сходинкового контуру для моделювання ефектів розмиття контурів у практичних застосуваннях багато дослідників використовували гауссово згладжений сходинковий контур ([[Функція похибки|функцію похибки]]).<ref name="lin98" /><ref>W. Zhang and F. Bergholm (1997) "[https://link.springer.com/article/10.1023/A:1007923307644 Multi-scale blur estimation and edge type classification for scene analysis] {{Webarchive|url=https://web.archive.org/web/20180603081323/https://link.springer.com/article/10.1023%2FA%3A1007923307644 |date=3 червня 2018 }}", International Journal of Computer Vision, vol 24, issue 3, Pages: 219–250. {{ref-en}}</ref> Таким чином, одновимірне зображення <math>f</math>, що має рівно один контур, розташований в <math>x = 0</math>, можна моделювати як

: <math>f(x) = \frac{I_r - I_\ell}{2} \left( \operatorname{erf}\left(\frac{x}{\sqrt{2}\sigma}\right) + 1\right) + I_\ell.</math>

Ліворуч від контуру яскравість <math>I_\ell = \lim_{x \rightarrow -\infty} f(x)</math>, а праворуч від контуру&nbsp;— <math>I_r = \lim_{x \rightarrow \infty} f(x)</math>. Масштабний коефіцієнт <math>\sigma</math> називають масштабом розмиття контуру. В ідеалі цей параметр масштабу слід налаштувати відповідно до якості зображення, щоб уникати руйнування істинних контурів у ньому.{{Джерело|дата=січень 2022}}

== Чому це нетривіальне завдання ==

Щоби проілюструвати, чому виявляння контурів не є тривіальним завданням, розгляньмо задачу виявлення контурів у наступному одновимірному сигналі. Тут ми можемо інтуїтивно сказати, що має бути контур між 4-м та 5-м пікселями.

{| style="border:0; margin:0.5em auto"
| style="border:1px solid #000; padding:5px 10px;" |5
| style="border:1px solid #000; padding:5px 10px;" | 7
| style="border:1px solid #000; padding:5px 10px;" | 6
| style="border:1px solid #000; padding:5px 10px;" | 4
| style="border:1px solid #000; padding:5px" | 152
| style="border:1px solid #000; padding:5px" | 148
| style="border:1px solid #000; padding:5px" | 149
|- style="height:30px"
| style="background:#050505" |
| style="background:#070707" |
| style="background:#060606" |
| style="background:#040404" |
| style="background:#989898" |
| style="background:#949494" |
| style="background:#959595" |
|}

Якби різниця яскравості між 4-м та 5-м пікселями була нижчою, а різниці яскравості між сусідніми прилеглими пікселями&nbsp;— вищими, то було би не так легко сказати, що у відповідній області має бути контур. Понад те, можливо було би стверджувати, що це випадок, у якому є декілька контурів.

{| style="border:0; margin:0.5em auto"
| style="border:1px solid #000; padding:5px 10px;" |5
| style="border:1px solid #000; padding:5px 10px;" | 7
| style="border:1px solid #000; padding:5px 10px;" | 6
| style="border:1px solid #000; padding:5px 10px;" | 41
| style="border:1px solid #000; padding:5px" | 113
| style="border:1px solid #000; padding:5px" | 148
| style="border:1px solid #000; padding:5px" | 149
|- style="height:30px"
| style="background:#050505" |
| style="background:#070707" |
| style="background:#060606" |
| style="background:#292929" |
| style="background:#717171" |
| style="background:#949494" |
| style="background:#959595" |
|}

Отже, чітко вказати певний поріг того, наскільки великою має бути зміна яскравості між двома сусідніми пікселями, щоби ми могли сказати, що між цими пікселями має бути контур, не завжди просто.<ref name="lin98" /> Справді, це одна з причин, чому виявляння контурів може бути нетривіальною задачею, якщо тільки об'єкти в сцені не дуже прості, а умови освітлення можливо добре контролювати (див., наприклад, контури, виділені в зображенні з дівчинкою вище).

== Підходи ==

Існує багато методів виявляння контурів, але більшість із них можливо згрупувати у дві категорії: на основі пошуку, та на основі {{Не перекладено|Перетин нуля|перетину нуля|en|Zero crossing}}. Методи на основі пошуку виявляють контури, спочатку обчислюючи міру вираженості контуру ({{lang-en|edge strength}}), як правило, як [[Перша похідна|вираження першої похідної]], таке як величина градієнта, а потім шукають локальні напрямні максимуми величини градієнта з використанням обчисленої оцінки локального спрямування контуру, зазвичай, напряму градієнта. Методи на основі перетину нуля, щоби знаходити контури, шукають перетини нуля [[Друга похідна|вираженням другої похідної]], обчисленим із зображення, зазвичай, перетини нуля [[лапласіан]]ом, або перетини нуля нелінійним диференціальним виразом. Як етап попередньої обробки для виявляння контурів майже завжди застосовують етап згладжування, як правило, [[Гауссове згладжування|гауссового]] (див. також [[знижування шуму]]).

Опубліковані методи виявляння контурів переважно відрізняються типами застосовуваних фільтрів згладжування та способами обчислення міри вираженості контуру. Оскільки багато методів виявляння контурів покладаються на обчислення градієнтів зображення, вони також відрізняються типами фільтрів, застосовуваних для обчислення оцінок градієнта в напрямах ''x'' та ''y.''

Огляд низки різних методів виявляння контурів є в (Ziou and Tabbone 1998);<ref>D. Ziou and S. Tabbone (1998) "[https://web.archive.org/web/20191008173716/https://pdfs.semanticscholar.org/587a/acc01a4c33f0fe7fb172f5db785f40522b57.pdf Edge detection techniques: An overview]", International Journal of Pattern Recognition and Image Analysis, 8(4):537–559, 1998 {{ref-en}}</ref> див. також енциклопедичні статті про виявляння контурів в «Енциклопедії з математики»<ref name="lin95" /> та «Енциклопедії з інформатики та інженерії».<ref>[http://mrw.interscience.wiley.com/emrw/9780470050118/ecse/article/ecse603/current/abstract 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] {{Webarchive|url=https://web.archive.org/web/20100303141045/http://mrw.interscience.wiley.com/emrw/9780470050118/ecse/article/ecse603/current/abstract |date=3 березня 2010 }} {{ref-en}}</ref>

=== Кенні ===
{{Main|Алгоритм Кенні}}

{{нп|Джон Кенні|||John Canny}} розглядав математичну задачу виведення оптимального згладжувального фільтра за заданого критерію виявляння, локалізації та мінімізації множинних відгуків на один контур.<ref>J. Canny (1986) "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.420.3300&rep=rep1&type=pdf A computational approach to edge detection] {{Webarchive|url=https://web.archive.org/web/20210227083309/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.420.3300&rep=rep1&type=pdf |date=27 лютого 2021 }}", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 8, pages 679–714. {{ref-en}}</ref> Він показав, що оптимальним фільтром за цих припущень є сума чотирьох експоненційних доданків. Він також показав, що цей фільтр можливо добре наблизити першими похідними гауссіанів. Кенні також ввів поняття пригнічування немаксимумів ({{lang-en|non-maximum suppression}}), яке означає, що, за заданих фільтрів попереднього згладжування, точки контурів визначаються як точки, в яких величина градієнта набуває локального максимуму в напрямі градієнта. Шукати перетин нуля другою похідною вздовж напряму градієнта вперше запропонував {{нп|Роберт Гаралік|Гаралік||Robert Haralick}}.<ref>R. Haralick, (1984) "[http://haralick-org.torahcode.us/journals/04767475.pdf Digital step edges from zero crossing of second directional derivatives] {{Webarchive|url=https://web.archive.org/web/20191008173717/http://haralick-org.torahcode.us/journals/04767475.pdf |date=8 жовтня 2019 }}", IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(1):58–68. {{ref-en}}</ref>
Знадобилося менше двох десятиліть, щоби знайти сучасне геометричне варіаційне значення для цього оператора, яке пов'язує його з [[Алгоритм Марра — Гілдрет|алгоритмом Марра&nbsp;— Гілдрет]] виявляння контурів (перетин нуля лапласіаном). Це спостереження було представлено {{нп|Рон Кіммел|Роном Кіммелом||Ron Kimmel}} та {{нпні|Альфред Брукштайн|Альфредом Брукштайном||Alfred Bruckstein}}.<ref>[https://www.cs.technion.ac.il/~ron/PAPERS/laplacian_ijcv2003.pdf 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.] {{Webarchive|url=https://web.archive.org/web/20210308012954/https://www.cs.technion.ac.il/~ron/PAPERS/laplacian_ijcv2003.pdf |date=8 березня 2021 }} {{ref-en}}</ref>

Хоча його працю й було зроблено на початку часів комп'ютерного бачення, [[алгоритм Кенні]] виявляння контурів (включно з його різновидами) все ще перебуває на рівні останніх досягнень.<ref>{{нп|Лінда Шапіро|Shapiro L. G.||Linda Shapiro}} & Stockman G. C. (2001) Computer Vision. London etc.: Prentice Hall, Page 326. {{ref-en}}</ref> Алгоритми виявляння контурів, які працюють краще за алгоритм Кенні, зазвичай вимагають більшого обчислювального часу, або більшої кількості параметрів.

Алгоритм Кенні&nbsp;— Деріша було виведено на основі подібних математичних критеріїв, що й алгоритм Кенні, але починаючи з дискретної точки зору, а потім ведучи до набору рекурсивних фільтрів для згладжування зображення замість {{нпні|Експоненційний фільтр|експоненційних||Exponential filter}} або гауссових фільтрів.<ref>R. Deriche (1987) ''Using Canny's criteria to derive an optimal edge detector recursively implemented'', Int. J. Computer Vision, vol 1, pages 167–187. {{ref-en}}</ref>

Описаний нижче [[#Диференціальний|диференціальний алгоритм виявляння контурів]] можливо розглядати як переформулювання методу Кенні з точки зору диференціальних інваріантів, обчислюваних з [[Масштабопросторове подання|масштабопросторового подання]], що дає низку переваг з погляду як теоретичного аналізу, так і субпіксельного втілення. У цьому аспекті було показано, що добрим вибором для виділяння меж у природних сценах є {{нп|логарифмічний фільтр Ґабора|||Log Gabor filter}}.<ref>Sylvain Fischer, Rafael Redondo, Laurent Perrinet, Gabriel Cristobal. [https://link.springer.com/content/pdf/10.1155/2007/90727.pdf Sparse approximation of images inspired from the functional architecture of the primary visual areas] {{Webarchive|url=https://web.archive.org/web/20220206223624/https://link.springer.com/content/pdf/10.1155/2007/90727.pdf |date=6 лютого 2022 }}. EURASIP Journal on Advances in Signal Processing, special issue on Image Perception, 2007 {{ref-en}}</ref>

=== Інші методи першого порядку ===

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

: <math>
\begin{align}
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) & = -\frac1 2 L(x, y-1) + 0 \cdot L(x, y) + \frac 1 2 \cdot L(x, y+1),
\end{align}
</math>

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

: <math>
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.
</math>

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

: <math>
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.
</math>

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

: <math>|\nabla L| = \sqrt{ L_x^2 + L_y^2}</math>

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

: <math>\theta = \operatorname{atan2}(L_y, L_x).</math>

Інші різницеві оператори першого порядку для оцінювання градієнта зображення було запропоновано в [[Оператор Прюітт|операторі Прюітт]], [[Оператор Робертса|хресті Робертса]], [[Оператор Каялі|операторі Каялі]]<ref>{{Cite journal|last=Dim|first=Jules R.|last2=Takamura|first2=Tamio|date=2013-12-11|title=Alternative Approach for Satellite Cloud Classification: Edge Gradient Application|journal=Advances in Meteorology|language=en|volume=2013|pages=1–8|doi=10.1155/2013/584816|issn=1687-9309|doi-access=free}} {{ref-en}}</ref> та {{нпні|Оператор Фрая — Чена|операторі Фрая&nbsp;— Чена||Frei–Chen operator}}.

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

=== Порогування та зв'язування ===

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

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

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

=== Витончування контурів ===

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

Переваги:

# Рівні та тонкі контури сприяють кращій продуктивності {{нп|розпізнавання об'єктів|||Object recognition}}.
# Якщо застосовують [[Перетворення Гафа]] для виявляння ліній та еліпсів, то витончування може давати набагато кращі результати.
# Якщо контур виявляється межею області, то витоншування може легко, без особливої алгебри, давати параметри її зображення, як-от периметр.

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

# Обрати тип {{нп|Піксельна зв'язність#Двовимірна|зв'язності||Pixel connectivity#2-dimensional}}, як-то 8, 6 або 4.
# Перевагу віддають [[Окіл Мура|8-зв'язності]], за якої розглядають усі безпосередні пікселі, що оточують заданий.
# Вилучити точки з півночі, півдня, сходу та заходу.
# Зробити це за кілька проходів, тобто, після проходу для півночі використати те саме напівоброблене зображення в іншому проході, й так далі.
# Вилучати точку, якщо:<br/>Точка не має сусідів на півночі (у проході для півночі, й на відповідних напрямках для інших проходів).<br/>Точка не є кінцем лінії.<br/>Точка ізольована.<br/>Вилучання точок жодним чином не призведе до роз'єднання їхніх сусідів.
# Інакше лишити точку.

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

=== Підходи другого порядку ===

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

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

==== Диференціальний ====

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

Дотримуючись диференціального геометричного способу вираження вимоги придушування немаксимумів, запропонованого Ліндебергом,<ref name="lin98" /><ref name="lin93">[http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A473368&dswid=5061 T. Lindeberg (1993) "Discrete derivative approximations with scale-space properties: A basis for low-level feature extraction", J. of Mathematical Imaging and Vision, 3(4), pages 349–376.] {{Webarchive|url=https://web.archive.org/web/20210602212721/http://kth.diva-portal.org/smash/record.jsf?pid=diva2:473368&dswid=5061 |date=2 червня 2021 }} {{ref-en}}</ref> введімо в кожній точці зображення локальну систему координат <math>(u, v)</math>, {{nowrap|<math>v</math>-напрям}} якої паралельний напряму градієнта. Виходячи з припущення, що зображення було попередньо згладжено гауссовим згладжуванням, та було обчислено [[масштабопросторове подання]] <math>L(x, y; t)</math> в масштабі <math>t</math>, ми можемо вимагати, щоби величина градієнта [[Масштабопросторове подання|масштабопросторового подання]], яка дорівнює першій напрямній похідній у {{nowrap|<math>v</math>-напрямі}} <math>L_v</math>, мала у {{nowrap|<math>v</math>-напрямі}} нульову першу напрямну похідну

: <math>\partial_v(L_v) = 0</math>

тоді як друга напрямна похідна у {{nowrap|<math>v</math>-напрямі}} <math>L_v</math> повинна бути від'ємною, тобто,

: <math>\partial_{vv}(L_v) \leq 0.</math>

Записане як явний вираз у термінах локальних частинних похідних <math>L_x, L_y, \ldots, L_{yyy}</math>, це визначення контуру можливо виразити як перетин нуля кривими диференціального інваріанта

: <math>L_v^2 L_{vv} = L_x^2 \, L_{xx} + 2 \, L_x \, L_y \, L_{xy} + L_y^2 \, L_{yy} = 0,</math>

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

: <math>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</math>,

де <math>L_x, L_y, \ldots, L_{yyy}</math> позначують частинні похідні, обчислені з [[Масштабопросторове подання|масштабопросторового подання]] <math>L</math>, отриманого згладжуванням первинного зображення [[Гауссове ядро|гауссовим ядром]]. Таким чином, контури автоматично отримуватимуться як неперервні криві з субпіксельною точністю. До цих диференціальних і субпіксельних сегментів контурів також можливо застосовувати гістерезисне порогування.

На практиці наближення перших похідних можливо обчислювати за допомогою центральних різниць, як описано вище, тоді як другі похідні можливо обчислювати з [[Масштабопросторове подання|масштабопросторового подання]] <math>L</math> відповідно до:

: <math>
\begin{align}
L_{xx}(x, y) & = L(x-1, y) - 2 L(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) - 2 L(x, y) + L(x, y+1).
\end{align}
</math>

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

: <math>
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.
</math>

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

=== На основі фазової конгруентності ===

Недавній розвиток методів виявляння контурів для пошуку місць їхнього розташування використовує підхід частотної області. Методи {{нп|Фазова конгруентність|фазової конгруентності||Phase congruency}} (відомої також як фазова когерентність) намагаються знаходити місця на зображенні, де всі синусоїди в частотній області синфазні. Ці місця загалом відповідатимуть розташуванню того, що сприймається як контур, незалежно від того, чи цей контур являє собою велику зміну яскравості в просторовій області. Ключова перевага цієї методики полягає в тому, що вона добре реагує на {{нп|махові смуги|||Mach bands}} й уникає хибних спрацьовувань, які зазвичай трапляються навколо {{нпні|Даховий контур|дахових контурів||Roof edge}}. Даховий контур ({{lang-en|roof edge}})&nbsp;— це розрив у першій похідній профілю яскравості.<ref>T. Pajdla and V. Hlavac (1993) "[https://link.springer.com/chapter/10.1007/3-540-57233-3_54 Surface discontinuities in range images] {{Webarchive|url=https://web.archive.org/web/20180616062537/https://link.springer.com/chapter/10.1007%2F3-540-57233-3_54 |date=16 червня 2018 }}, " in Proc IEEE 4th Int. Conf. Comput. Vision, pp. 524–528. {{ref-en}}</ref>

=== Фазоворозтягувальне перетворення ===
[[Файл:PST_edge_detector_saint_Paul.tif|міні|500x500пкс| Посилення ознак у зображенні ([[Собор святого Павла|собору Святого Павла]] в Лондоні) за допомогою фазоворозтягувального перетворення (ФРП). Ліворуч показано первинне зображення, а праворуч&nbsp;— ознаки, виявлені за допомогою ФРП.]]

{{нп|Фазоворозтягувальне перетворення|||Phase stretch transform}}, або ФРП ({{lang-en|phase stretch transform, PST}})&nbsp;— це навіяний фізикою обчислювальний підхід до обробки сигналів та зображень. Однією з його корисних властивостей є виявляння та класифікування ознак.<ref name="original">M. H. Asghari, and B. Jalali, "Edge detection in digital images using dispersive phase stretch, " International Journal of Biomedical Imaging, Vol. 2015, Article ID 687819, pp. 1–6 (2015). {{ref-en}}</ref><ref>M. H. Asghari, and B. Jalali, "[https://ieeexplore.ieee.org/abstract/document/7032125/ Physics-inspired image edge detection] {{Webarchive|url=https://web.archive.org/web/20191008173715/https://ieeexplore.ieee.org/abstract/document/7032125/ |date=8 жовтня 2019 }}, " IEEE Global Signal and Information Processing Symposium (GlobalSIP 2014), paper: WdBD-L.1, Atlanta, December 2014. {{ref-en}}</ref> ФРП це похідний продукт дослідження {{нп|Дисперсійне перетворення Фур’є з розтягуванням у часі|дисперсійного перетворення Фур’є з розтягуванням у часі||Time stretch dispersive Fourier transform}}. ФРП перетворює зображення, моделюючи поширення дифракційним середовищем зі сконструйованою тривимірною дисперсійною властивістю (показником заломлення). Ця операція покладається на симетричність дисперсійного профілю, і її можливо розуміти в термінах дисперсійних власних функцій або режимів розтягування.<ref>B. Jalali and A. Mahjoubfar, "[https://ieeexplore.ieee.org/iel7/5/4357935/07118650.pdf Tailoring Wideband Signals With a Photonic Hardware Accelerator], " Proceedings of the IEEE, Vol. 103, No. 7, pp. 1071–1086 (2015). {{ref-en}}
</ref> ФРП виконує подібні функції, що й фазовоконтрастна мікроскопія, але на цифрових зображеннях. ФРП застосовне як до цифрових зображень, так і до часових даних, даних часових рядів.

=== Субпіксельні ===

Для підвищення точності виявляння контурів було запропоновано декілька субпіксельних методик, включно з методами допасовування кривої ({{lang-en|curve-fitting}}), на основі моменту ({{lang-en|moment-based}}),<ref>{{Cite journal|last=Ghosal|first=S.|last2=Mehrota|first2=R|date=1993-01-01|title=Orthogonal Moment Operators for Subpixel Edge Detection|journal=Pattern Recognition|volume=26|issue=2|pages=295–306|doi=10.1016/0031-3203(93)90038-X}} {{ref-en}}</ref><ref name="Christian">{{Cite journal|last=Christian|first=John|date=2017-01-01|title=Accurate Planetary Limb Localization for Image-Based Spacecraft Navigation|journal=Journal of Spacecraft and Rockets|volume=54|issue=3|pages=708–730|bibcode=2017JSpRo..54..708C|doi=10.2514/1.A33692}} {{ref-en}}</ref> відбудовними ({{lang-en|reconstructive}}) методами, та методами ефекту часткової площі ({{lang-en|partial area effect methods}}).<ref>{{Cite journal|last=Trujillo-Pino|first=Agustín|last2=Krissian|first2=Karl|last3=Alemán-Flores|first3=Miguel|last4=Santana-Cedrés|first4=Daniel|date=2013-01-01|title=Accurate subpixel edge location based on partial area effect|journal=Image and Vision Computing|volume=31|issue=1|pages=72–90|doi=10.1016/j.imavis.2012.10.005|hdl-access=free}} {{ref-en}}</ref> Ці методи мають різні характеристики. Методи допасовування кривих обчислювально прості, але на них легко впливає шум. Методи на основі моменту використовують інтегральний підхід для зменшення впливу шуму, але в деяких випадках можуть вимагати більше обчислень. Відбудовні методи використовують горизонтальні та вертикальні градієнти для побудови кривої та знаходження піку кривої як субпіксельного контуру. Методи ефекту часткової площі ґрунтуються на гіпотезі, що значення кожного пікселя залежить від площі по обидві сторони контуру всередині цього пікселя, що забезпечує точну індивідуальну оцінку для кожного пікселя контуру. Деякі варіанти методики на основі моменту виявилися найточнішими для ізольованих контурів.<ref name="Christian" />
[[Файл:Subpixel_edge_detection.png|без|міні|754x754пкс| Виявлення контурів на [[Ангіографія|ангіографічному зображенні]]. Ліворуч розпізнавання контурів зроблено на рівні пікселів. Праворуч субпіксельне виявляння контуру точно визначає контур всередині пікселів.]]

== Див. також ==

* {{Section link|Згортка (математичний аналіз)|Застосування}}
* {{нп|Фільтрування зі зберіганням контурів|||Edge-preserving filtering}}
* [[Виявляння ознак (комп'ютерне бачення)]] про інші низькорівневі виявлячі ознак
* [[Похідна зображення]]
* [[Фільтр Ґабора]]
* [[Знижування шуму в зображеннях]]
* [[Оператор Кірша]] для виявляння контурів у компасних напрямах
* [[Виявляння хребтів]] про зв'язок між виявлянням контурів та виявлянням хребтів
* {{нп|Логарифмічний фільтр Ґабора|||Log Gabor filter}}
* {{нп|Фазоворозтягувальне перетворення|||Phase stretch transform}}

== Примітки ==
{{Примітки}}

== Література ==

* {{Springer|title=Edge detection|id=Edge_detection|oldid=17883|first=Tony|last=Lindeberg}} {{ref-en}}
* [https://onlinelibrary.wiley.com/doi/10.1002/9780470050118.ecse603 Розділ про виявляння контурів в «Енциклопедії з інформатики та інженерії»] {{Webarchive|url=https://web.archive.org/web/20220206232248/https://onlinelibrary.wiley.com/doi/10.1002/9780470050118.ecse603 |date=6 лютого 2022 }} {{ref-en}}
* [http://edge.kitiyo.com/ Виявляння контурів із застосуванням ПКВМ] {{Webarchive|url=https://web.archive.org/web/20160303172119/http://edge.kitiyo.com/ |date=3 березня 2016 }} {{ref-en}}
* [[doi:10.5201/ipol.2012.gjmr-lsd|Виявляння відрізків прямих ''a-contrario'', з кодом та інтерактивною демонстрацією]] {{ref-en}}
* [https://www.mathworks.com/discovery/edge-detection.html Виявляння контурів із застосуванням ''MATLAB''] {{Webarchive|url=https://web.archive.org/web/20220206203800/https://www.mathworks.com/discovery/edge-detection.html |date=6 лютого 2022 }} {{ref-en}}
* [http://www.mathworks.com/matlabcentral/fileexchange/48908-accurate-subpixel-edge-location Субпіксельне виявляння контурів із застосуванням ''MATLAB''] {{Webarchive|url=https://web.archive.org/web/20211216123504/https://www.mathworks.com/matlabcentral/fileexchange/48908-accurate-subpixel-edge-location |date=16 грудня 2021 }} {{ref-en}}

[[Категорія:Обробка зображень]]
[[Категорія:Виділення ознак (комп'ютерний зір)|Контурів]]