Алгоритм Кенні

Алгори́тм Ке́нні, виявля́ч ко́нтурів Ке́нні, опера́тор Ке́нні (англ. Canny edge detector) — це оператор виявляння контурів, який використовує багатоетапний алгоритм для виявляння широкого спектру контурів на зображеннях. Його розробив ^[en] 1986 року. Кенні також розробив обчислювальну теорію виявляння контурів (англ. computational theory of edge detection), яка пояснює, чому ця методика діє.

Виявляч контурів Кенні, застосований до кольорового фото парового двигуна.

Первинне зображення.

Розробка

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

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

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

Серед розроблених дотепер методів виявляння контурів алгоритм Кенні — один із найбільш строго визначених методів, який забезпечує добре та надійне виявляння. Завдяки своїй оптимальності для відповідності трьом критеріям виявляння контурів та простоті процесу втілення він став одним із найпопулярніших алгоритмів виявляння контурів.

Процес

Процес алгоритму виявляння контурів Кенні можливо розбити на п'ять різних етапів:

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

Гауссів фільтр

Це зображення після проходження гауссової маски 5×5 кожним пікселем.

Оскільки на всі результати виявляння контурів легко впливає шум на зображенні, важливо відфільтрувати цей шум, щоби запобігти спричиненому ним помилковому виявлянню. Щоби згладити зображення, із ним згортають ядро гауссового фільтра. Цей крок дещо згладить зображення, щоби зменшити вплив явного шуму на виявляч контурів. Рівняння для ядра гауссового фільтра розміром (2k+1)×(2k+1) задають як

${\displaystyle H_{ij}={\frac {1}{2\pi \sigma ^{2}}}\exp \left(-{\frac {(i-(k+1))^{2}+(j-(k+1))^{2}}{2\sigma ^{2}}}\right);1\leq i,j\leq (2k+1)}$

Ось приклад гауссового фільтра 5×5, використаного для створення зображення поруч, з ${\displaystyle \sigma }$ = 1. (Зірочка позначує операцію згортання.)

${\displaystyle \mathbf {B} ={\frac {1}{159}}{\begin{bmatrix}2&4&5&4&2\\4&9&12&9&4\\5&12&15&12&5\\4&9&12&9&4\\2&4&5&4&2\end{bmatrix}}*\mathbf {A} .}$

Важливо розуміти, що вибір розміру гауссового ядра впливатиме на продуктивність виявляча. Що більший розмір, то менша чутливість виявляча до шуму. Крім того, зі збільшенням розміру ядра гауссового фільтра трохи збільшуватиметься похибка розташування у виявлянні контурів. Розмір 5×5 добрий для більшості випадків, але це також різнитиметься залежно від конкретних ситуацій.

Знаходження градієнту яскравості зображення

Контур на зображенні може вказувати в різних напрямках, тож алгоритм Кенні використовує чотири фільтри для виявляння на розмитому зображенні горизонтальних, вертикальних та діагональних контурів. Оператор виявляння контурів (наприклад, Робертса, Прюітт або Собеля) повертає значення для першої похідної в горизонтальному (G_x) та вертикальному (G_y) напрямках. З цього можливо визначати градієнт та напрямок контуру:

Напрямок градієнта

${\displaystyle \mathbf {G} ={\sqrt {{\mathbf {G} _{x}}^{2}+{\mathbf {G} _{y}}^{2}}}}$

${\displaystyle \mathbf {\Theta } =\operatorname {atan2} \left(\mathbf {G} _{y},\mathbf {G} _{x}\right)}$,

де G можливо обчислювати за допомогою функції hypot, а ^[en] — функція арктангенса з двома аргументами. Кут напрямку контуру округлюється до одного з чотирьох кутів, що подають вертикаль, горизонталь та дві діагоналі (0°, 45°, 90° та 135°). Напрямок контуру в кожній кольоровій області буде встановлено на певне значення кута, наприклад, θ у [0°, 22,5°] або [157,5°, 180°] відображується в 0°.

Порогування величини градієнта або відрізне пригнічування нижньої межі

Мінімумне відрізне пригнічування величин градієнта, або порогування нижньої межі, — це одна з методик витончування контурів .

Відрізне пригнічування нижньої межі застосовують для пошуку місць із найрізкішою зміною значення яскравості. Алгоритм для кожного пікселя в градієнтному зображенні:

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

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

• якщо округлений кут градієнта дорівнює 0° (тобто контур має напрямок північ—південь), точку вважатимуть точкою контуру, якщо її величина градієнта більша за величини в пікселях у східному та західному напрямках,
• якщо округлений кут градієнта становить 90° (тобто контур має напрямок схід—захід), точку вважатимуть точкою контуру, якщо її величина градієнта більша за величини в пікселях у північному та південному напрямках,
• якщо округлений кут градієнта становить 135° (тобто контур має напрямок північний схід—південний захід), точку вважатимуть точкою контуру, якщо її величина градієнта більша за величини в пікселях у північно-західному та південно-східному напрямках,
• якщо округлений кут градієнта становить 45° (тобто контур має напрямок північний захід—південний схід), точку вважатимуть точкою контуру, якщо її величина градієнта більша за величини в пікселях у північно-східному та південно-західному напрямках.

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

Зауважте, що знак напрямку не має значення, тобто північ—південь — те саме, що південь—північ тощо.

Подвійний поріг

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

Простежування контурів за допомогою гістерезису

Виявляння контурів Кенні, застосоване до фотографії

Наразі, пікселі з сильними контурами, безумовно, повинно бути задіяно в остаточному контурному зображенні, оскільки їх виділяють зі справжніх контурів на зображенні. Проте будуть деякі дебати щодо слабких контурних пікселів, оскільки ці пікселі могло бути виділено як із справжніх контурів, так і з шуму/мінливості кольору. Для досягнення точного результату необхідно усунути слабкі контури, викликані останніми причинами. Зазвичай слабкий контурний піксель, викликаний справжніми контурами, буде з'єднано з сильним контурним пікселем, тоді як шумові відгуки не з'єднані. Для простеження з'єднання контуру використовують ^[en] шляхом розгляду слабкого контурного пікселя та пікселів його ^[en] околу. Поки в цій плямі є хоч один сильний контурний піксель, цю слабку контурну точку можливо визначити як таку, яку слід зберегти.

Покроковий прохід алгоритмом

У цьому розділі буде показано просування зображення кожним із цих п'яти кроків.

Первинне зображення

Зображення було звужено до відтінків сірого, та застосовано гауссів фільтр 5×5 з σ=1,4

Градієнт яскравості попереднього зображення. Контури зображення було оброблено шляхом повторення.

Придушення немаксимумів попереднього зображення.

Подвійне порогування попереднього зображення. Слабкі пікселі — ті, що з градієнтом між 0,1 та 0,3. Сильні пікселі мають значення градієнта понад 0,3

До попереднього зображення застосовано гістерезис

Вдосконалення

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

1. Гауссів фільтр застосовують для згладжування шуму, але він також згладжуватиме й контур, що вважається високочастотною ознакою. Це збільшує можливість пропускання слабких контурів та появи ізольованих контурів у результаті.
2. Для обчислення амплітуди градієнта старий алгоритм виявляння контурів Кенні використовує центр у маленькому вікні околу 2×2, щоб обчислювати середнє значення скінченних різниць для подавання амплітуди градієнта. Цей метод чутливий до шуму й може легко виявляти помилкові контури та губити справжні.
3. У традиційному алгоритмі виявляння контурів Кенні буде два незмінні глобальні порогові значення для відфільтровування хибних контурів. Проте, коли зображення стає складнішим, різні локальні області потребуватимуть дуже відмінних порогових значень для точного визначання справжніх контурів. Крім того, в традиційному методі глобальні порогові значення визначають вручну шляхом експериментів, що призводить до складності обчислення, коли потрібно мати справу з великою кількістю різних зображень.
4. Результат традиційного виявляння не може досягати задовільно високої точності єдиного відгуку для кожного контуру — багатоточкові відгуки матимуть місце.

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

Заміна гауссового фільтра

Оскільки як високочастотний сигнал визначатимуться і контури, і шум, простий гауссів фільтр додаватиме згладжувальний ефект до обох. Проте, щоби досягати високої точності виявляння справжнього контуру, очікується, що до шуму слід застосовувати більше згладжувального ефекту, а до контуру — менше. Бін Ван та Шаошен Фан з Університету науки й технологій Чанші розробили адаптивний фільтр, який оцінює розрив між значеннями градацій сірого кожного пікселя^[]. Що вищий розрив, то нижче значення ваги встановлюють для гладкого фільтра в цій точці. І навпаки, що менший розрив між значеннями градацій сірого, то вище значення ваги встановлюють для цього фільтра. Процес втілення цього адаптивного фільтра можливо підсумувати п'ятьма кроками:

1. K = 1, встановити кількість ітерацій n та коефіцієнт амплітуди контуру h.

2. Обчислити значення градієнта ${\displaystyle G_{x}(x,y)}$ та ${\displaystyle G_{y}(x,y)}$

3. Розрахувати вагу за наступними формулами:

${\displaystyle d(x,y)={\sqrt {G_{x}(x,y)^{2}+G_{y}(x,y)^{2}}}}$

${\displaystyle w(x,y)=\exp \left(-{\frac {\sqrt {d(x,y)}}{2h^{2}}}\right)}$

4. Визначення адаптивного фільтра:

${\displaystyle f(x,y)={\frac {1}{N}}\sum \limits _{i=-1}^{1}\sum \limits _{j=-1}^{1}f(x+i,y+j)w(x+i,y+j)}$

для згладжування зображення, де

${\displaystyle N=\sum \limits _{i=-1}^{1}\sum \limits _{j=-1}^{1}w(x+i,y+j)}$

5. Коли K = n, зупинити ітерації, інакше, k = k+1, продовжити виконанням другого кроку

Вдосконалення обчислення величини та напрямку градієнта

Величину та напрямок градієнта можливо обчислювати різноманітними операторами виявляння контурів, і вибір оператора може впливати на якість результатів. Дуже часто обирають фільтр Собеля 3×3. Проте інші фільтри можуть бути кращими, наприклад, фільтр Собеля 5×5, який знижуватиме шум, або фільтр Шарра, що має кращу обертову симетрію. Іншими поширеними варіантами є Прюітт (який використовує Чжоу) та хрест Робертса.

Надійний метод визначання подвійного порогового значення

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

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

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

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

^[en] використовували замість гауссового фільтра та оцінки градієнта для обчислення векторного поля, напрямки та величини якого приблизно відповідають напрямкам та вираженості контурів на зображенні, до якого потім застосовують кроки 3—5 алгоритму Кенні. Курвлети розкладають сигнали на окремі складові різних масштабів, а відкидання складових тонших масштабів може знижувати шум.

Диференціальне геометричне формулювання

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

Варіаційне формулювання виявляча контурів Гараліка — Кенні

Було показано, що варіаційне пояснення основної складової виявляча контурів Кенні, тобто знаходження перетинів нуля 2-ю похідною вздовж напрямку градієнта, — це результат мінімізації функціонала Кронрода — Мінковського при одночасній максимізації інтеграла над вирівнюванням контуру з градієнтним полем (Кіммел та Брукштайн 2003). Докладний опис див. у статті про регуляризовані лапласові перетини нуля та інші оптимальні інтегратори контурів.

Параметри

Алгоритм Кенні містить низку регульованих параметрів, які можуть впливати на тривалість обчислення та ефективність алгоритму.

• Розмір гауссового фільтра: фільтр згладжування, який використовують на першому етапі, безпосередньо впливає на результати алгоритму Кенні. Менші фільтри спричинюють менше розмиття та дозволяють виявляти маленькі чіткі лінії. Більший фільтр спричинює більше розмиття, розмазуючи значення певного пікселя більшою площею зображення. Більші радіуси розмиття корисніші для виявляння більших, гладкіших контурів, наприклад, контуру веселки.
• Порогові значення: використання двох порогових значень із гістерезисом забезпечує більшу гнучкість, ніж підхід з єдиним пороговим значенням, але загальні проблеми порогових підходів все ще лишаються. Занадто високий поріг може пропускати важливу інформацію. З іншого боку, занадто низьке порогове значення хибного ідентифікуватиме недоречну інформацію (наприклад, шум) як важливу. Важко дати загальний поріг, який добре працює на всіх зображеннях. Перевіреного підходу до розв'язання цієї проблеми ще не існує.

Висновок

Алгоритм Кенні можливо пристосовувати до різних середовищ. Його параметри дозволяють підганяти його для розпізнавання контурів, що мають різні характеристики, залежно від конкретних вимог заданого втілення. У первинній праці Кенні виведення оптимального фільтра давало фільтр зі скінченною імпульсною характеристикою, який може бути повільним для обчислення в просторовій області, якщо необхідна величина згладжування важлива (у цьому випадку фільтр матиме велику просторову опору). З цієї причини часто пропонують використовувати фільтр Кенні вигляду Рашида Деріша зі скінченною імпульсною характеристикою (виявляч Кенні — Деріша), який рекурсивний, і який можливо обчислювати за короткий незмінний проміжок часу для будь-якої бажаної величини згладжування. Другий вигляд підходить для втілень режиму реального часу на ПКВМ, ПЦС та дуже швидких вбудованих ПК. У цьому контексті, проте, звичайне рекурсивне втілення оператора Кенні не дає доброго наближення обертової симетрії й відтак демонструє схильність до горизонтальних та вертикальних контурів.

Див. також

• Комп'ютерне бачення
• Цифрова обробка зображень
• Виявляння ознак (комп'ютерне бачення)
• Виділяння ознак
• Виявляння хребтів
• Простір масштабів

Примітки

1. Li, Q., Wang, B., & Fan, S. (2009). Browse Conference Publications Computer Science and Engineer ... Help Working with Abstracts An Improved CANNY Edge Detection Algorithm. In 2009 Second International Workshop on Computer Science and Engineering proceedings : WCSE 2009 : 28–30 October 2009, Qingdao, China (pp. 497–500). Los Alamitos, CA: IEEE Computer Society (англ.)
2. Zhou, P., Ye, W., & Wang, Q. (2011). An Improved Canny Algorithm for Edge Detection. Journal of Computational Information Systems, 7(5), 1516-1523. (англ.)
3. Otsu N. A threshold selection method from gray-level histograms. IEEE Trans Systems, Man and Cybernetics,9(1):62-66,1979. (англ.)
4. Mallat S, Zhong S. Characterization of Signals from Multi scale Edges [J]. IEEE Trans on PAMI, 1992, 14 (7):710-732. (англ.)
5. Gebäck1, T. & Koumoutsakos, P. "Edge detection in microscopy images using curvelets" BMC Bioinformatics, 10: 75, 2009. (англ.)

 

• Canny, J., A Computational Approach To Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):679–698, 1986. (англ.)
• R. Deriche, Using Canny's criteria to derive a recursively implemented optimal edge detector, Int. J. Computer Vision, Vol. 1, pp. 167–187, April 1987. (англ.)
• Lindeberg, Tony "Edge detection and ridge detection with automatic scale selection", International Journal of Computer Vision, 30, 2, pp 117—154, 1998. (Містить диференціальний підхід до придушування немаксимумів.) (англ.)
• Kimmel, Ron and Bruckstein, Alfred M. "On regularized Laplacian zero crossings and other optimal edge integrators", International Journal of Computer Vision, 53(3):225–243, 2003. (Містить геометричну варіаційну інтерпретацію для виявляча контурів Гараліка — Кенні.) (англ.)
• (англ.)
• Thomas B. Moeslund. Image and Video Processing. August 2008 (англ.)
• Green, B. (2002, January 1). Canny Edge Detection Tutorial. Retrieved December 3, 2014; заархівовано (англ.)

Посилання

• Домашня сторінка Джона Кенні (англ.)
• Перелік публікацій Рашида Деріша (англ.)
• Журнальні публікації Рона Кіммела (англ.)
• Виявляння контурів Кенні в C++ OpenCV (англ.)
• Виявляння контурів Кенні в Python OpenCV [ 2014-04-29 у Wayback Machine.]
• Canny Edge World — приклад відео