Метод Горна — Шунка

Метод Горна — Шунка (англ. Horn–Schunck method) оцінювання оптичного потоку — це глобальний метод, який запроваджує глобальне обмеження гладкості (англ. smoothness) для розв'язування ^[en] (додатковий опис див. у статті Оптичний потік).

Математичні деталі

Алгоритм Горна — Шунка спирається на припущення про плавність потоку над усім зображенням. Таким чином, він намагається мінімізувати спотворення потоку й віддає перевагу розв'язкам, які демонструють більшу плавність.

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

${\displaystyle E=\iint \left[(I_{x}u+I_{y}v+I_{t})^{2}+\alpha ^{2}(\lVert \nabla u\rVert ^{2}+\lVert \nabla v\rVert ^{2})\right]{{\rm {d}}x{\rm {d}}y}}$

де ${\displaystyle I_{x}}$, ${\displaystyle I_{y}}$ та ${\displaystyle I_{t}}$ це похідні значень інтенсивності зображення за вимірами x, y та часу відповідно, ${\displaystyle {\vec {V}}=[u(x,y),v(x,y)]^{\top }}$ це вектор оптичного потоку, а параметр ${\displaystyle \alpha }$ це стала регуляризації. Більші значення ${\displaystyle \alpha }$ призводять до плавнішого потоку. Цей функціонал можливо мінімізувати, розв'язуючи пов'язані (багатовимірні рівняння Ейлера — Лагранжа). Це такі

${\displaystyle {\frac {\partial L}{\partial u}}-{\frac {\partial }{\partial x}}{\frac {\partial L}{\partial u_{x}}}-{\frac {\partial }{\partial y}}{\frac {\partial L}{\partial u_{y}}}=0}$

${\displaystyle {\frac {\partial L}{\partial v}}-{\frac {\partial }{\partial x}}{\frac {\partial L}{\partial v_{x}}}-{\frac {\partial }{\partial y}}{\frac {\partial L}{\partial v_{y}}}=0}$

де ${\displaystyle L}$ є підінтегральним виразом виразу енергії, що дає

${\displaystyle I_{x}(I_{x}u+I_{y}v+I_{t})-\alpha ^{2}\Delta u=0}$

${\displaystyle I_{y}(I_{x}u+I_{y}v+I_{t})-\alpha ^{2}\Delta v=0}$

де індекси знову позначують частинне диференціювання, а ${\displaystyle \Delta ={\frac {\partial ^{2}}{\partial x^{2}}}+{\frac {\partial ^{2}}{\partial y^{2}}}}$ позначує оператор Лапласа. На практиці цей лапласіан наближують чисельно за допомогою скінченних різниць, і його може бути записано як ${\displaystyle \Delta u(x,y)=4({\overline {u}}(x,y)-u(x,y))}$ де ${\displaystyle {\overline {u}}(x,y)}$ це середньозважене усереднення ${\displaystyle u}$, обчислюване в околі пікселя в положенні ${\displaystyle (x,y)}$. Використовуючи це позначення, наведену вище систему рівнянь можна записати як

${\displaystyle (I_{x}^{2}+4\alpha ^{2})u+I_{x}I_{y}v=4\alpha ^{2}{\overline {u}}-I_{x}I_{t}}$

${\displaystyle I_{x}I_{y}u+(I_{y}^{2}+4\alpha ^{2})v=4\alpha ^{2}{\overline {v}}-I_{y}I_{t}}$

що є лінійною за ${\displaystyle u}$ та ${\displaystyle v}$, і її може бути розв'язано для кожного пікселя зображення. Проте, оскільки цей розв'язок залежить від сусідніх значень поля потоку, його потрібно повторювати, щойно було уточнено сусідів. Наступна ітераційна схема виводиться за допомогою правила Крамера:

${\displaystyle u^{k+1}={\overline {u}}^{k}-{\frac {I_{x}(I_{x}{\overline {u}}^{k}+I_{y}{\overline {v}}^{k}+I_{t})}{4\alpha ^{2}+I_{x}^{2}+I_{y}^{2}}}}$

${\displaystyle v^{k+1}={\overline {v}}^{k}-{\frac {I_{y}(I_{x}{\overline {u}}^{k}+I_{y}{\overline {v}}^{k}+I_{t})}{4\alpha ^{2}+I_{x}^{2}+I_{y}^{2}}}}$

де верхній індекс ${\displaystyle k+1}$ позначує наступну ітерацію, яку потрібно обчислити, а ${\displaystyle k}$ — останній обчислений результат. Це, по суті, метод розщеплення матриць, подібний до методу Якобі, застосованого до великої, розрідженої системи, що виникає при розв'язуванні для всіх пікселів одночасно^[].

Властивості

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

Див. також

• Метод Лукаса — Канаде

Джерела

• B.K.P. Horn and B.G. Schunck, "Determining optical flow." Artificial Intelligence, vol 17, pp 185–203, 1981. Рукопис доступний на сервері МТІ. (англ.)

Посилання

• Втілення OpenCV