Відстежувач ознак Канаде — Лукаса — Томазі

У комп'ютернім баченні відсте́жувач озна́к Кана́де — Лу́каса — Тома́зі (КЛТ, англ. Kanade–Lucas–Tomasi feature tracker, KLT) — це один з підходів до виділяння ознак. Його пропонують головно для розв'язування тієї проблеми, що традиційні методи зіставляння зображень, як правило, витратні. КЛТ використовує інформацію про просторову яскравість, щоби спрямовувати пошук положення, яке дає найкращий збіг. Він швидший за традиційні методики за рахунок дослідження набагато меншої кількості потенційних збігів між зображеннями.

Задача зіставляння

Традиційну задачу зіставляння зображень можливо охарактеризувати наступним чином: Дано дві функції ${\displaystyle F(x)}$ та ${\displaystyle G(x)}$, що подають значення пікселів у кожному положенні ${\displaystyle x}$ на двох зображеннях відповідно, де ${\displaystyle x}$ — вектор. Ми хочемо знайти вектор розузгодженості (англ. disparity) ${\displaystyle h}$, який мінімізує певну міру відмінності між ${\displaystyle F(x+h)}$ та ${\displaystyle G(x)}$ для ${\displaystyle x}$ у якійсь розглядуваній області ${\displaystyle R}$.

Деякі міри відмінності між ${\displaystyle F(x+h)}$ та ${\displaystyle G(x)}$:

• Норма L₁ = ${\displaystyle \sum _{x\in R}\left\vert F(x+h)-G(x)\right\vert }$
• Норма L₂ = ${\displaystyle {\sqrt {\sum _{x\in R}\left[F(x+h)-G(x)\right]^{2}}}}$
• Нормована кореляція з протилежним знаком
  = ${\displaystyle {\dfrac {-\sum _{x\in R}F(x+h)G(x)}{{\sqrt {\sum _{x\in R}F(x+h)^{2}}}{\sqrt {\sum _{x\in R}G(x)^{2}}}}}}$

Базовий опис алгоритму зіставляння

Відстежувач ознак КЛТ ґрунтується на двох працях:

У першій праці Лукас та Канаде^[1] розвинули ідею локального пошуку з використанням градієнтів, зважених наближенням до другої похідної зображення.

Одновимірний випадок

Якщо ${\displaystyle h}$ це зміщення між двома зображеннями ${\displaystyle F(x)}$ та ${\displaystyle G(x)=F(x+h)}$, то роблять наближення, що

${\displaystyle F'(x)\approx {\dfrac {F(x+h)-F(x)}{h}}={\dfrac {G(x)-F(x)}{h}}\,}$

так, що

${\displaystyle h\approx {\dfrac {G(x)-F(x)}{F'(x)}}\,}$

Це наближення до градієнта зображення точне лише якщо зміщення локальної області між двома зображеннями для зіставляння не надто велике. Це наближення ${\displaystyle h}$ залежить від ${\displaystyle x}$. Для поєднання різних оцінок ${\displaystyle h}$ за різних значень ${\displaystyle x}$ їх природно усереднювати:

${\displaystyle h\approx {\dfrac {\sum _{x}{\dfrac {G(x)-F(x)}{F'(x)}}}{\sum _{x}1}}.}$

Це усереднення можливо додатково покращити зважуванням внеску кожного з членів до нього, обернено пропорційного оцінці ${\displaystyle \left\vert F''(x)\right\vert }$, де

${\displaystyle F''(x)\approx {\dfrac {G'(x)-F'(x)}{h}}.}$

З метою полегшення виразу вагову функцію визначають як

${\displaystyle w(x)={\dfrac {1}{\left\vert G'(x)-F'(x)\right\vert }}.}$

Відтак, усередненням зі зважуванням є

${\displaystyle h={\dfrac {\sum _{x}{\dfrac {w(x)\left[G(x)-F(x)\right]}{F'(x)}}}{\sum _{x}w(x)}}.}$

Після отримання цієї оцінки ${\displaystyle F(x)}$ можливо перемістити на цю оцінку ${\displaystyle h}$. Цю процедуру застосовують багаторазово, що дає ітерування на зразок Ньютона — Рафсона. Ця послідовність оцінок в ідеалі сходитиметься до найкращої ${\displaystyle h}$. Це ітерування можливо виразити через

${\displaystyle {\begin{cases}h_{0}=0\\h_{k+1}=h_{k}+{\dfrac {\sum _{x}{\dfrac {w(x)\left[G(x)-F(x+h_{k})\right]}{F'(x+h_{k})}}}{\sum _{x}w(x)}}\end{cases}}}$

Альтернативне виведення

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

${\displaystyle F(x+h)\approx F(x)+hF'(x),}$

щоби знаходити ${\displaystyle h}$, яка мінімізує міру норми L₂ різниці між кривими (або похибку), де цю похибку можливо виразити як

${\displaystyle E=\sum _{x}\left[F(x+h)-G(x)\right]^{2}.}$

Щоби мінімізувати цю похибку за ${\displaystyle h}$, візьмімо частинну похідну ${\displaystyle E}$, й встановімо її в нуль:

${\displaystyle {\begin{aligned}0&={\dfrac {\partial E}{\partial h}}\\&\approx {\dfrac {\partial }{\partial h}}\sum _{x}\left[F(x)+hF'(x)-G(x)\right]^{2}\\&=\sum _{x}2F'(x)\left[F(x)+hF'(x)-G(x)\right]\end{aligned}}}$ ,

${\displaystyle \Rightarrow h\approx {\dfrac {\sum _{x}F'(x)[G(x)-F(x)]}{\sum _{x}F'(x)^{2}}}\,}$

Це в принципі те саме, що й в одновимірному випадку, за винятком того, що ваговою функцією є ${\displaystyle w(x)=F'(x)^{2}.}$ А ітерування зі зважуванням можливо виразити так:

${\displaystyle {\begin{cases}h_{0}=0\\h_{k+1}=h_{k}+{\dfrac {\sum _{x}w(x)F'(x+h_{k})\left[G(x)-F(x+h_{k})\right]}{\sum _{x}w(x)F'(x+h_{k})^{2}}}\end{cases}}}$

Продуктивність

Щоб оцінити продуктивність цього алгоритму, нам, природно, цікаво дізнатися, за яких умов і як швидко послідовність ${\displaystyle h_{k}}$ збігатиметься до справжньої ${\displaystyle h}$.

Розгляньмо випадок:

${\displaystyle F(x)=\sin x,}$

${\displaystyle G(x)=F(x+h)=\sin(x+h).}$

Обидва варіанти алгоритму зіставляння збіжаться до правильної ${\displaystyle h}$ за ${\displaystyle \left\vert h\right\vert <\pi }$, тобто для первинних помилкових зіставлянь розміром до половини довжини хвилі. Проміжок збіжності можливо покращувати пригнічуванням високих просторових частот у зображенні, чого можливо досягати його згладжуванням^[en], яке також небажано пригнічуватиме його дрібні деталі. Якщо вікно згладжування набагато більше за розмір допасовуваного об'єкта, то цей об'єкт може бути пригнічено повністю, так, що зіставляння стане неможливим.

Оскільки зображення, профільтровані до низьких частот, можливо дискретизувати з нижчою роздільністю без втрати інформації, використовують грубо—точну (англ. coarse-to-fine) стратегію. Для отримання приблизного допасування можливо використовувати згладжену версію зображення з низькою роздільністю. Застосування цього алгоритму до зображень із вищою роздільністю покращуватиме допасування, отримане за нижчої роздільності.

Оскільки згладжування розширює проміжок збіжності, функція зважування покращує точність наближення, прискорюючи збігання. Без зважування розрахована розузгодженість ${\displaystyle h_{1}}$ першої ітерації з ${\displaystyle F(x)=\sin x}$ падає до нуля, коли розузгодженість наближається до половини довжини хвилі.

Втілення

Це втілення вимагає обчислювання зважених сум величин ${\displaystyle F'G,}$ ${\displaystyle F'F}$ та ${\displaystyle (F')^{2}}$ над розглядуваною областю ${\displaystyle R.}$ Хоч ${\displaystyle F'(x)}$ і неможливо обчислити точно, її можливо оцінювати через

${\displaystyle F'(x)\approx {\dfrac {F(x+\Delta x)-F(x)}{\Delta x}},}$

де ${\displaystyle \Delta x}$ обирають доречно невеликою.

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

Узагальнення на численні виміри

Алгоритм зіставляння для одного та двох вимірів можливо узагальнити на більшу кількість вимірів. Щоби зробити це, ми намагаємося мінімізувати норму L₂ міри похибки:

${\displaystyle E=\sum _{\mathbf {x} \in R}\left[F(\mathbf {x} +\mathbf {h} )-G(\mathbf {x} )\right]^{2},}$

де ${\displaystyle \mathbf {x} }$ та ${\displaystyle \mathbf {h} }$ — n-вимірні рядкові вектори.

Лінійне наближення аналогічне:

${\displaystyle F(\mathbf {x} +\mathbf {h} )\approx F(\mathbf {x} )+\mathbf {h} \left({\dfrac {\partial }{\partial \mathbf {x} }}F(\mathbf {x} )\right)^{T}.}$

І частинно диференціюємо ${\displaystyle E}$ за ${\displaystyle \mathbf {h} }$:

${\displaystyle {\begin{aligned}0&={\dfrac {\partial E}{\partial \mathbf {h} }}\\&\approx {\dfrac {\partial }{\partial \mathbf {h} }}\sum _{\mathbf {x} }\left[F(\mathbf {x} )+\mathbf {h} \left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)^{T}-G(\mathbf {x} )\right]^{2}\\&=\sum _{\mathbf {x} }2\left[F(\mathbf {x} )+\mathbf {h} \left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)^{T}-G(\mathbf {x} )\right]\left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)\end{aligned}}}$ ,

${\displaystyle \Rightarrow \mathbf {h} \approx \left[\sum _{\mathbf {x} }\left[G(\mathbf {x} )-F(\mathbf {x} )\right]\left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)\right]\left[\sum _{\mathbf {x} }\left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)^{T}\left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)\right]^{-1},}$

що має майже такий же вигляд, як й одновимірний варіант.

Подальші узагальнення

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

${\displaystyle G(x)=F(Ax+h),}$

де ${\displaystyle A}$ — лінійне просторове перетворення. Похибкою для мінімізування тоді є

${\displaystyle E=\sum _{x}\left[F(Ax+h)-G(x)\right]^{2}.}$

Щоби визначити величину ${\displaystyle \Delta A}$ для підлаштовування ${\displaystyle A}$ та ${\displaystyle \Delta h}$ для підлаштовування ${\displaystyle h}$, знову скористаймося лінійним наближенням:

${\displaystyle F(x(A+\Delta A)+(h+\Delta h))}$

${\displaystyle \approx F(Ax+h)+(\Delta Ax+\Delta h){\dfrac {\partial }{\partial x}}F(x).}$

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

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

${\displaystyle F(x)=\alpha G(x)+\beta ,}$

де ${\displaystyle \alpha }$ подає підлаштування контрастності, а ${\displaystyle \beta }$ — яскравості.

Поєднуючи цей вираз із загальною задачею зіставляння лінійним перетворенням, отримуємо

${\displaystyle E=\sum _{x}\left[F(Ax+h)-(\alpha G(x)+\beta )\right]^{2}}$

як величину для мінімізування за ${\displaystyle \alpha ,}$ ${\displaystyle \beta ,}$ ${\displaystyle A}$ та ${\displaystyle h.}$

Виявляння та відстежування точкових ознак

У другій праці Томазі та Канаде^[2] використали той же базовий метод для пошуку зіставляння через паралельне перенесення, але вдосконалили цю методику шляхом відстежування ознак, які підходять для алгоритму відстежування. Запропоновані ознаки обиратимуться, якщо обидва власні значення градієнтної матриці перевищуватимуть деякий поріг.

За допомогою дуже подібного виведення цю задачу формулюють як

${\displaystyle \nabla d=e\,}$

де ${\displaystyle \nabla }$ — градієнт. Це те саме, що й остання формула Лукаса — Канаде вище. Локальний фрагмент вважають доброю ознакою для відстежування, якщо обидва з двох власних значень (${\displaystyle \lambda _{1}}$ та ${\displaystyle \lambda _{2}}$) градієнта ${\displaystyle \nabla }$ перевищують якийсь поріг.

Метод відстежування на основі цих двох праць зазвичай вважають відстежувачем КЛТ.

Вдосконалення та варіації

У третій праці Сі та Томазі^[3] запропонували додатковий етап перевірки правильності відстежування ознак.

Між зображенням поточно відстежуваної ознаки та її зображенням у несуміжному попередньому кадрі допасовують афінне перетворення. Якщо це афінно компенсоване зображення занадто відмінне, цю ознаку відкидають.

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

Використовуючи подібне виведення, як і для КЛТ, Сі та Томазі показали, що цей пошук можливо виконувати за формулою

${\displaystyle Tz=a\,}$

де ${\displaystyle T}$ — матриця градієнтів, ${\displaystyle z}$ — вектор афінних коефіцієнтів, а ${\displaystyle a}$ — вектор похибки. Порівняйте це з ${\displaystyle \nabla d=e}$.

Примітки

1. Bruce D. Lucas and Takeo Kanade. An Iterative Image Registration Technique with an Application to Stereo Vision. International Joint Conference on Artificial Intelligence, pages 674–679, 1981. (англ.)
2. Carlo Tomasi and Takeo Kanade. Detection and Tracking of Point Features. Carnegie Mellon University Technical Report CMU-CS-91-132, April 1991. (англ.)
3. Jianbo Shi and Carlo Tomasi. Good Features to Track. IEEE Conference on Computer Vision and Pattern Recognition, pages 593–600, 1994. (англ.)

Див. також

• Ознаки Канаде — Томазі в контексті виявляння ознак
• Метод Лукаса — Канаде, алгоритм оптичного потоку, отриманий із посилання 1.