Оператор Кенні

Оператор Кенні (детектор кордонів Кенні, алгоритм Кенні) в дисципліні комп'ютерного зору - оператор виявлення меж зображення. Був розроблений в 1986 Джоном Кенні ( англ. John F. Canny ) І використовує багатоступінчастий алгоритм для виявлення широкого спектра кордонів в зображеннях.

Кенні вивчив математичну проблему отримання фільтра, оптимального за критеріями виділення, локалізації та мінімізації декількох відгуків одного краю. Він показав, що шуканий фільтр є сумою чотирьох експонент. Він також показав, що цей фільтр може бути добре наближений першої похідної Гауссіани. Кенні ввів поняття придушення немаксімумов ( англ. Non-Maximum Suppression , Яке означає, що пікселями кордонів оголошуються пікселі, в яких досягається локальний максимум градієнта в напрямку вектора градієнта.

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


1. Розвиток алгоритму Кенні

Видалення слабких кордонів
Для чого використовуються два пороги?
1. Щоб зменшити вплив шуму для ініціалізації кривої використовуємо верхній поріг;
2. Щоб "не втратити хвіст" використовуємо нижній поріг при простежуванні.
Пошук локальних максимумів
Перевіряючи чи є піксель локальним максимумом уздовж напрямку градієнта, доводиться інтерполювати "нецілі" пікселі p і r

Метою Кенні було розробити оптимальний алгоритм виявлення меж, що задовольняє трьом критеріям:

  • гарне виявлення (Канни трактував це властивість як підвищення відносини сигнал / шум);
  • хороша локалізація (правильне визначення положення кордону);
  • єдиний відгук на одну кордон.

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

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


2. Основні етапи алгоритму

Оригінал
Зображення після застосування маски Гауса 5x5.
Детектор кордонів Canny

Згладжування. Розмиття зображення для видалення шуму. Оператор Кенні використовує фільтр який може бути добре наближений до першої похідної гауссіани. \ Sigma = 1.4:

\ 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}.

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

\ Mathbf {G} = \ sqrt {{\ mathbf {G} _x} ^ 2 + {\ mathbf {G} _y} ^ 2}
\ Mathbf {\ Theta} = \ operatorname {arctan} \ left ({\ mathbf {G} _y \ over \ mathbf {G} _x} \ right).

Кут напряму вектора градієнта заокруглюється і може приймати такі значення: 0, 45, 90, 135.

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

Придушення немаксімумов. Тільки локальні максимуми відзначаються як кордону.

Подвійна порогова фільтрація. Потенційні межі визначаються порогами.

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

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