Функція згладжування

Для роботи алгоритму лінійного стеження нам треба мати належний спосіб згладжувати зображення. Звичайно, згладжування може виявитися потрібним і для інших цілей, аніж розпізнавання образів, наприклад для художніх. Є деяка специфіка згладжування для різних цілей.

Художня специфіка

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

$(1)\qquad {\begin{bmatrix}1&1&1\\1&2&1\\1&1&1\end{bmatrix}}$

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

Специфіка для розпізнавання образів

В алгоритмі лінійного стеження інші вимоги.

Перша специфіка — результат згладжування повинен мати добрі аналітичні властивості, щоб програма робила з нього висновки. Алгоритм згладжування повинен наближатися до формули згортки від неперервних змінних, яку у векторному вигляді записується так:

$(2)\qquad {\bar {I}}(\mathbf {r} )=\int \phi (\mathbf {r} -{\boldsymbol {\rho }})I({\boldsymbol {\rho }})d{\boldsymbol {\rho }}$

тут $I(\mathbf {r} )=I(x,y)$ — розподіл інтенсивності (величини пікселів) на оригінальному зображенні,

${\bar {I}}(\mathbf {r} )$ — результат згладжування,

$\phi (\mathbf {r} )=\phi (x,y)$ — функція згладжування.

Для того, щоб ми могли диференціювати згладжену картинку, функція згладжування повинна бути неперервною та мати перші похідні. Якщо похідні матимуть розриви першого роду (скачки), то взяття інтеграла в формулі (2) підвищує на одиницю гладкість функції, і результат ${\bar {I}}(\mathbf {r}$ матиме неперервні перші похідні і розривні (але обмежені) другі похідні.

Також бажано, щоб у випадку однакової дії в горизонтальному та вертикальгному напрямках, функція $\phi (x,y)$ діяла так само і по всіх інших напрямках, щоб уникнути подушко-подібної дисторсії. Тобто ця функція має залежати лише від відстані до центральної точки:

$(3)\qquad \phi (x,y)=f(r)=f\left({\sqrt {x^{2}+y^{2}}}\right)$

Крім того функція $f(r)$ має бути додатньою і монотонно спадною. А також перетворюватися на нуль (або ставати нехтовно малою) після деякої скінченної відстані $r_{0}$ — щоб ми могли проводити усереднення в межах одного об'єкта, не домішуючи пікселі сусіднього.

Друга специфіка — не треба застосовувати згладжування до всіх пікселів (це було б марнуванням процесорного часу), досить робити аналіз тільки поблизу контурів або характерних точок об'єкта, щоб судити про рух або форму всього об'єкта.

Вибір функції

Якщо до вимог попереднього пункту додати ще одну вимогу, щоб функція $\phi (x,y)$ була достатньо простою і легко обчислювалась, то найприроднішими кандидатами будуть такі функції:

$(4)\qquad \phi _{n}(x,y)={\begin{cases}C\cdot \left(1-{r^{2} \over a^{2}}\right)^{n}&{\mbox{if }}r<a\\0&{\mbox{if }}r\geq a\end{cases}}$

де $n$ — невелике ціле число, а параметр $a$ задає розмір області усереднення (математики цю область називають носієм функції $\phi (x,y)$), а $C$ — нормуючий множник.

Функція $\phi _{0}(x,y)$ постійна в крузі $r<a$ і має скачок (розрив першого роду) на межі круга. Функція $\phi _{1}(x,y)$ неперервна але має розривну похідну, і цілком підходить для використання в алгоритмі лінійного стеження.

Функції (4) легко узагальнюються для випадку, коли нам потрібні різні охвати усереднення по горизонталі та вертикалі:

$(5)\qquad {\tilde {\phi }}_{n}(x,y)=C\cdot \left(1-{x^{2} \over a^{2}}-{y^{2} \over b^{2}}\right)^{n}\qquad {\mbox{if }}{x^{2} \over a^{2}}+{y^{2} \over b^{2}}<1$

і область усереднення буде еліпс.

Можна навіть зробити цей еліпс нахиленим під кутом $\alpha$:

$(6)\qquad {\tilde {\phi }}_{n}(x,y)=C\cdot \left(1-{(x\cos \alpha +y\sin \alpha )^{2} \over a^{2}}-{(-x\sin \alpha +y\cos \alpha )^{2} \over b^{2}}\right)^{n}$

Деякі обчислення

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

$\qquad {\bar {I}}(x+\Delta x,y+\Delta y)-{\bar {I}}-{\bar {I}}_{x}\Delta x-{\bar {I}}_{y}\Delta y$

Ця оцінка досить складна, і буде пророблена на окремій сторінці. Тут же ми зробимо деякі простіші обчислення.

Знайдемо нормуючий множник $C$ функції $\phi _{n}(x,y)$ такий, щоб результатом усереднення рівномірної засвітки $I(x,y)=I=const$ було те саме число ${\bar {I}}=I$.

$(7)\qquad {\bar {I}}=\int \phi (\mathbf {r} -{\boldsymbol {\rho }})I({\boldsymbol {\rho }})d{\boldsymbol {\rho }}=I\int \phi ({\boldsymbol {\rho }})d{\boldsymbol {\rho }}=2\pi IC\int _{0}^{a}\left(1-{r^{2} \over a^{2}}\right)^{n}rdr={\pi a^{2} \over n+1}IC=I$

$(8)\qquad C={n+1 \over \pi a^{2}}$

В реальних зображеннях інтенсивність $I$ знаходиться в межах від нуля до деякого максимального значення $I_{\mbox{max}}$. Це є наслідком того, що датчики світла мають верхній порог. Цей факт, приводить до того, що похідна згладженої інтенсивності теж не перевищує деякого максимального числа. Знайдемо це число для випадку $n=1$. Для цього продиференціюємо (2) по координаті $x$:

$(9)\qquad \phi (x,y)={2 \over \pi a^{2}}\left(1-{x^{2}+y^{2} \over a^{2}}\right)\qquad {\mbox{if }}x^{2}+y^{2}<a^{2}$

$(10)\qquad {\bar {I}}_{x}={\partial {\bar {I}} \over \partial x}=\int \phi _{x}(\mathbf {r} -{\boldsymbol {\rho }})I({\boldsymbol {\rho }})d{\boldsymbol {\rho }}=\int _{(x-\xi )^{2}+(y-\eta )^{2}<1}\left(-4{x-\xi \over \pi a^{4}}\right)I(\xi ,\eta )d\xi d\eta$

В останньому інтегралі зробимо заміну змінних:

$\qquad \xi \rightarrow x-\xi ;\qquad \eta \rightarrow y-\eta$

тоді

$(11)\qquad {\bar {I}}_{x}=-{4 \over \pi a^{4}}\int _{\xi ^{2}+\eta ^{2}<a^{2}}\xi I(x-\xi ,y-\eta )d\xi d\eta$

Оскільки другий множник під інтегралом знаходиться в межах від нуля до $I_{\mbox{max}}$, то вираз (11) завжди менший від:

$(12)\qquad {\big |}{\bar {I}}_{x}{\big |}<{4I_{\mbox{max}} \over \pi a^{4}}\int _{\xi ^{2}+\eta ^{2}<a^{2},\;\xi >0}\xi d\xi d\eta ={8I_{\mbox{max}} \over 3\pi a}$

Із кругової симетрії функції (9) ми можемо зробити висновок, що число (12) обмежує модуль градієнта:

$(13)\qquad {\big |}\nabla {\bar {I}}{\big |}={\sqrt {{\bar {I}}_{x}^{2}+{\bar {I}}_{y}^{2}}}<{8I_{\mbox{max}} \over 3\pi a}$

Застосування до завдань розпізнавання образів

Аналітичні властивості згладженої інтенсивності дозволяють:

1. стежити за рухом об'єктів;
2. обчислювати градієнт растрового зображення, причому достатньо гладкий для потреб подальшої векторизації;
3. Робити афінний пошук на фотографії об'єкта зі внутрішньою структурою (наприклад обличчя людини).