Функція згладжування
Для роботи алгоритму лінійного стеження нам треба мати належний спосіб згладжувати зображення. Звичайно, згладжування може виявитися потрібним і для інших цілей, аніж розпізнавання образів, наприклад для художніх. Є деяка специфіка згладжування для різних цілей.
Художня специфіка[ред. | ред. код]
Наприклад в художніх цілях ми можемо використати згладжування для зміни слайдів у презентації. Перший слайд розпливається (зменшується наводка на різкість), а по тому наступний слайд починає з'являтися, збільшуючи різкість. Тут особливих вимог до диференційовності функції зглажування не пред'являється. Неістотним є також відсутність подушко-подібної дисторсії, наприклад ми можемо взяти функцію, що задається матрицею:
в цій процедурі згладжування ми беремо центральний піксель з коефіцієнтом 2, а сусідні з ним — з коефіцієнтом 1. В цій функції по діагоналях згладжування проявляється сильніше, ніж в горизонтальному чи вертикальному напрямках.
Перша специфіка художнього згладжування — що його результат не аналізується комп'ютером, а призначений для показування людині. Друга специфіка — ми повинні обов'язково обробляти всю картинку (або деяку область), і не можемо обмежуватися окремими вибірковими пікселями.
Специфіка для розпізнавання образів[ред. | ред. код]
В алгоритмі лінійного стеження інші вимоги.
Перша специфіка — результат згладжування повинен мати добрі аналітичні властивості, щоб програма робила з нього висновки. Алгоритм згладжування повинен наближатися до формули згортки від неперервних змінних, яку у векторному вигляді записується так:
тут — розподіл інтенсивності (величини пікселів) на оригінальному зображенні,
- — результат згладжування,
- — функція згладжування.
Для того, щоб ми могли диференціювати згладжену картинку, функція згладжування повинна бути неперервною та мати перші похідні. Якщо похідні матимуть розриви першого роду (скачки), то взяття інтеграла в формулі (2) підвищує на одиницю гладкість функції, і результат матиме неперервні перші похідні і розривні (але обмежені) другі похідні.
Також бажано, щоб у випадку однакової дії в горизонтальному та вертикальгному напрямках, функція діяла так само і по всіх інших напрямках, щоб уникнути подушко-подібної дисторсії. Тобто ця функція має залежати лише від відстані до центральної точки:
Крім того функція має бути додатньою і монотонно спадною. А також перетворюватися на нуль (або ставати нехтовно малою) після деякої скінченної відстані — щоб ми могли проводити усереднення в межах одного об'єкта, не домішуючи пікселі сусіднього.
Друга специфіка — не треба застосовувати згладжування до всіх пікселів (це було б марнуванням процесорного часу), досить робити аналіз тільки поблизу контурів або характерних точок об'єкта, щоб судити про рух або форму всього об'єкта.
Вибір функції[ред. | ред. код]
Якщо до вимог попереднього пункту додати ще одну вимогу, щоб функція була достатньо простою і легко обчислювалась, то найприроднішими кандидатами будуть такі функції:
де — невелике ціле число, а параметр задає розмір області усереднення (математики цю область називають носієм функції ), а — нормуючий множник.
Функція постійна в крузі і має скачок (розрив першого роду) на межі круга. Функція неперервна але має розривну похідну, і цілком підходить для використання в алгоритмі лінійного стеження.
Функції (4) легко узагальнюються для випадку, коли нам потрібні різні охвати усереднення по горизонталі та вертикалі:
і область усереднення буде еліпс.
Можна навіть зробити цей еліпс нахиленим під кутом :
Деякі обчислення[ред. | ред. код]
Для впевненого застосування алгоритму лінійного стеження нам треба зробити оцінку зверху різниці:
Ця оцінка досить складна, і буде пророблена на окремій сторінці. Тут же ми зробимо деякі простіші обчислення.
Знайдемо нормуючий множник функції такий, щоб результатом усереднення рівномірної засвітки було те саме число .
В реальних зображеннях інтенсивність знаходиться в межах від нуля до деякого максимального значення . Це є наслідком того, що датчики світла мають верхній порог. Цей факт, приводить до того, що похідна згладженої інтенсивності теж не перевищує деякого максимального числа. Знайдемо це число для випадку . Для цього продиференціюємо (2) по координаті :
В останньому інтегралі зробимо заміну змінних:
тоді
Оскільки другий множник під інтегралом знаходиться в межах від нуля до , то вираз (11) завжди менший від:
Із кругової симетрії функції (9) ми можемо зробити висновок, що число (12) обмежує модуль градієнта:
Застосування до завдань розпізнавання образів[ред. | ред. код]
Аналітичні властивості згладженої інтенсивності дозволяють:
- стежити за рухом об'єктів;
- обчислювати градієнт растрового зображення, причому достатньо гладкий для потреб подальшої векторизації;
- Робити афінний пошук на фотографії об'єкта зі внутрішньою структурою (наприклад обличчя людини).