Лінійне стеження

Ліні́йне сте́ження — спосіб визначення зміщення об'єктів на кадрах з відеокамери.

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

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

Пояснення принципу на прикладі ідеалізованого зображення

Є другий, аналітичний підхід для обчислення зміщення об'єктів. Як модель, розглянемо спочатку бітмапу, в якій величина пікселя (інтенсивність $I$) лінійно наростає по координаті абсцис (вісь $Ox$):

$(1)\qquad I=ax+b$

Якщо на другій бітмапі це саме зображення буде зміщено на величину $\Delta x$, то інтенсивність ${\hat {I}}$ змінюється за законом:

$(2)\qquad {\hat {I}}=a(x-\Delta x)+b=(ax+b)-a\Delta x$

Маючи ці дві картинки, ми легко можемо обчислити зміщення об'єкта:

$(3)\qquad \Delta x={I-{\hat {I}} \over a}$

навіть якщо це зміщення відбулося на дробову кількість пікселів.

Коефіцієнт $a$ в формулі (1) є проєкцією градієнта інтенсивності на вісь абсцис:

$(4)\qquad \left({\mbox{grad}}I\right)_{x}=I_{x}={\partial I \over \partial x}=a$

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

$(5)\qquad I_{x}\Delta x+I_{y}\Delta y=I-{\hat {I}}$

Підготовка рельного зображення для застосування лінійного стеження

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

$(6)\qquad I(x+\Delta x)=I_{0}+\sum _{i=1}^{2}a_{i}\Delta x_{i}+\sum _{i,j=1}^{2}b_{ij}\Delta x_{i}\Delta x_{j}+\dots$

У цій формулі для простоти запису суми, координати $(x,y)$ позначено через $x_{1}=x,\;x_{2}=y$.

Розглянемо неперервну модель. Функція інтенсивності $I=I(x,y)$ змінюється неперервно всередині протяжних об'єктів, і скачком змінюється (розриви першого роду) на межі двох об'єктів. Нас цікавить згладжування саме таких скачків. Сума по сусідніх пікселях у неперервній моделі стає інтегралом згортки:

$(7)\qquad <I>=\int \phi (x-\xi ,y-\eta )I(\xi ,\eta )d\xi d\eta$

Якщо функція згладжування $\phi$ матиме неперервні перші похідні, то і результат згладжування $<I>$ буде неперервною функцією і теж матиме перші похідні (скрізь, бо розривів ми позбулись):

$(8)\qquad {\partial <I> \over \partial x}=\int {\partial \phi (x-\xi ,y-\eta ) \over \partial x}I(\xi ,\eta )d\xi d\eta$

Функція $\phi$, окрім неперервності і диференційовності, повинна бути додатньою в деякому невеликому околі нуля, і дорівнювти нулю за межами цього околу (інакше ми при усередненні можемо домішати пікселі сторонніх об'єктів, і взагалі вийти за рамки картинки). Одним із кандидатів є наступна функція, яку образно можна назвати «біквадратним капелюхом»:

$(9)\qquad \phi (x,y)={\begin{cases}\left(1-{x^{2} \over a^{2}}-{y^{2} \over b^{2}}\right)^{2},&{\mbox{if }}{x^{2} \over a^{2}}+{y^{2} \over b^{2}}<1\\0,&{\mbox{otherwise }}\end{cases}}$

Вона додатня всередині еліпса з півосями $a$, $b$, і її перші похідні неперервно перетворюються в нуль на межі. Ясно, що при згладжуванні функцією (9) чіткої вертикальної межі ми одержимо приблизно лінійну ділянку на інтервалі, що є часткою півосі $a$, на більших відстанях ми не можемо користуватися лінійним наближенням. Як показують обчислення, при $\Delta x={a/2}$ похибка при обчисленні за формулою (3) буде близько 23%.

Оптимальне використання кольору

Нехай наша відеокамера видає кольорову RGB-картинку. Тоді зміщення $\Delta x$ записується трьома формулами (по одній на кожен колір):

$(10)\qquad R_{x}\Delta x=-\Delta R;\qquad G_{x}\Delta x=-\Delta G;\qquad B_{x}\Delta x=-\Delta B$

Якщо розглядати згладжену межу між двома кольоровими об'єктами, то очевидно при зміщенні об'єктів усі три формули повинні дати один і той же результат $\Delta x$. Проте було б нераціонально обчислювати усі три формули (10), проводячи усереднення (7) за кожним із трьох кольорів (марнування процесорного часу). Краще вибрати в ролі інтенсивності деяку лінійну комбінацію кольорів:

$(11)\qquad I=\alpha R+\beta G+\gamma B$

і вже для неї проводити всі усереднення та обчислення. Але як підібрати коефіцієнти $\alpha ,\beta ,\gamma$ найкращим чином? Нехай ми маємо протяжний кольоровий об'єкт, колір якого задається числами ${\overrightarrow {Color}}_{1}=(R_{1},G_{1},B_{1})$, на кольоровому ж фоні ${\overrightarrow {Color}}_{0}=(R_{0},G_{0},B_{0})$. Кольори можна розглядати як вектори в просторі RGB. Тоді очевидно, найбільш інформативною зміною кольору на межі об'єкта буде проєкція вектора різниці:

$(12)\qquad {\overrightarrow {DC}}={\overrightarrow {Color}}_{1}-{\overrightarrow {Color}}_{0}$

В аналітичній геометрії проєкція вектора $\mathbf {r}$ на вектор $\mathbf {a}$ буде відношенням скалярного добутку до довжини вектора $\mathbf {a}$:

$(13)\qquad {\mbox{Pr}}_{\mathbf {a} }(\mathbf {r} )={(\mathbf {a} \cdot \mathbf {r} ) \over |\mathbf {a} |}$

Повертаючись до формули (11), можна за аналогією з формулою (13) обчислити коефіцієнти:

$(14)\qquad \alpha =(R_{1}-R_{0})/d$

$(14a)\qquad \beta =(G_{1}-G_{0})/d$

$(14b)\qquad \alpha =(B_{1}-B_{0})/d$

$(14d)\qquad d={\sqrt {(R_{1}-R_{0})^{2}+(G_{1}-G_{0})^{2}+(B_{1}-B_{0})^{2}}}$

Використання ітерації для підвищення точності лінійного стеження

Розглянемо застосування ітерації на прикладі задачі бінокулярного зору. Нехай ми сфотографували один вертикальний об'єкт (наприклад стовп) двома відеокамерами, які рознесені на деяку відстань по горизонталі. Ясно, що зображення цього стовпа буде зміщене по горизонталі на деяке зміщення $\Delta x$ при порівнянні двох фотографій. Зміщення по вертикалі не очікується: $\Delta y=0$, тому ця задача трохи простіша аніж стеження за рухомими об'єктами. Оскільки нам потрібний тільки градієнт по осі $Ox$, то функція згладжування (9) має бути сплюснутою. Коефіцієнт $a$ повинен щонайменше вдвічі перевищувати сподіване зміщення по іксу: $a\geq 2\Delta x$. На коефіцієнт $b$ не накладено ніяких математичних умов; але якщо ми візьмемо його поменшим, то зменшимо кількість обчислень, з другого боку, краще щоб деяке згладжування по осі $y$ відбувалося, щоб позбутися шороховатостей. Тому припустимо, що $b$ дорівнює малому цілому числу (в пікселях), наприклад $b=1$.

Тепер ми використаємо формули (3), (4) підставляючи в них згладжену інтенсивність (бажано також з врахуванням кольору за формулою 11). Одержимо результат першої ітерації:

$(15)\qquad \Delta _{1}x={I(x)-{\hat {I}}(x) \over \left({\mbox{grad}}\,I\right)_{x}}$

Тут ми явно вказали, в яких точках по іксу беруться інтенсивності. Точність цієї формули зменшується зі зростанням зміщення $\Delta _{1}x$. Але у випадку великого $\Delta _{1}x$, по модулю більшого одиниці, ми можемо провести ще одну ітерацію, змістивши другу картинку ${\hat {I}}(x)$ на ціле число пікселів що є округленням:

$(16)\qquad n={\mbox{round}}(\Delta _{1}x)$

Маємо приблизно:

$(17)\qquad {\hat {I}}(x+n)\approx {\hat {I}}(x)+({\mbox{grad}}\,I)_{x}n$

а тому наступна формула буде точнішою:

$(18)\qquad \Delta _{2}x=n+{I(x)-{\hat {I}}(x+n) \over \left({\mbox{grad}}\,I\right)_{x}}$

оскільки другий доданок в цій сумі є малою поправкою.

Інші методи стеження

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