*
1
Company Confidential © by MM Solutions EAD
Проследяване на обекти в изображения - �методи и особености
Автор: Ангел Иванов
Понятия
*
2
Company Confidential © by MM Solutions EAD
Приложения
На практика, всички алгоритми, които използват множество (>1) кадри.
*
3
Company Confidential © by MM Solutions EAD
Алгоритми за откриване
FAST: поне 9 съседа трябва да са заедно по-светли или по-тъмни от центъра
Праг за достатъчен контраст
Имплементацията е множество проверки, в такъв ред, че най-бързо да бъдат отхвърлени не-точките.
Отркива точките не точно в ъглите не обектите
Средно 2.6 сравнения за пиксел
*
4
Company Confidential © by MM Solutions EAD
Алгоритми за откриване
Харис: оптимален за проследяване с SSD (по-долу)
Открива области с с голям градиент във всички посоки
Structure tensor:
Може да се разглежда като параболоид на грешката от авто-SSD (по-долу)
Собствените стойности показват стръмността на параболоида в най-стръмната и най-полегатата посока (собствените вектори)
Голяма минимална собствена стойност => добра точка за проследяване
*
5
Company Confidential © by MM Solutions EAD
Алгоритми за откриване
Вискокочестотен филтър (DOG: difference of gaussians)
abs(imboxfilt(img,3) – imboxfilt(img,15)) : опростена версия с бокс-филтри
Прост и бърз.
Устойчив на шум.
Обаче, реагира и на ръбове, а не само на характерни точки
*
6
Company Confidential © by MM Solutions EAD
Степен на различност (грешка)
Една точна в две изображения е леко различна – търсим най-добро съвпадение
Затова е необходимо да дефинираме степен на различност, т.е. грешка.
SAD : sum of absolute differences
SSD : sum of squared difference
CC: Cross-correlation: sum (image1*image2) – съвпадение при максимална стойност
Не работи при силно ротирани изображения
Когато изображенията се различават по яркост и контраст, тези методи не работят добре. Затова, нормализация:
По яркост (offset): изваждане на средната стойност
По яркост и контраст (offset and scale): изваждане на средната стойност, разделяме на стандартното откнонение
Кoлкото по-нормализирани, толкова повече риск от грешки
Може да сравняваме трицветни (RGB, YUV, HSV, etc.), едноканални (grayscale) или бинарни (1 bit per pixel) изображения спред това коя информация в изображенията се запазва между тях.
*
7
Company Confidential © by MM Solutions EAD
Проследяване на точка
Пълно търсене : изчисляваме грешката при всяка възможа позиция на точката в другия кадър
Региона на търсене се определя от:
Повърхност на грешката: по-тъмно == добро съвпадение
*
8
Company Confidential © by MM Solutions EAD
Кернел 8х8
Кадър с добавен шум и офсет -10
SAD повърхнина
Проследяване на точка
*
9
Company Confidential © by MM Solutions EAD
SAD повърхнина
SSD повърхнина
Cross-correlation
Normalized
cross-correlation
Различните функции за грешка са различно толерантни към разлики в изображенията
SAD има най-остър минимум и може да се имплемнтира с най-малко памет. Нормализирането го забавя значително
NCC също се смята бързо (използва MAC инструкции, които за бързи) и лесно се нормализира, но има повече фалшиви максимуми
Проследяване на точка
Проследяване в бинарни изображения
Когато и цвета, и офсета, и скалата, и ръбовете са различни, само геометрията има значение. Бинаризирането на изображението изхвърля информацията за цветове и яркост и оставя само геометрията.
Бинаризира се спрямо локално средно
1 бит за пиксел: проследяването е много по-бързо – сравняват се 64 пиксела с една инструкция
Появяват се фалшиви ръбове, дублиращи истинските, плоските участъци стават много шумни
*
10
Company Confidential © by MM Solutions EAD
Кернел от бинаризиран йадър
Бинаризиран кадър
SAD повърхнина
Проследяване с пирамида
По-висока резолюция =>
по-голям кернел, по-голям регион на търсене =>
Времето расте с мащаба на 4та степен
Затова: пирамида от резолюции.
Проследяването на по-ниска резолюция е с по-малък кернел и в по-малък регион.
*
11
Company Confidential © by MM Solutions EAD
Проследяване с KLT
Предполага, че изображението няма резки ръбове и се изменя линейно в рамките на региона на търсене.
Т.е. работи със силно размазани изображения и винаги в пирамида, където региона на търсене е само няколко пиксела.
Основното допускане:
v1 – v2 = (pos2-pos1) * gradient1@pos1
„Gradient1“ е производната на изображението по посоката на абцисата. v1,v2 са известни – това са стойностите на изобжражението точката в двете изображения при началното предположение за позицията й (pos1 на рисунката). Pos2 е позицията с най-доброто съвпадение в img2 – с еднаква стойност както в img1.
Тази идея се доразвива за да се проследява кернел, а не единичен пиксел.
*
12
Company Confidential © by MM Solutions EAD
Проследяване на практика
*
13
Company Confidential © by MM Solutions EAD
KLТ vs пълно търсене
KLT метода е замислен с идеята да е много бърз.
На практика греши значително по-често от пълното търсене с пирамида. Това налага проследяване на повече точки за да може по-надеждно да се откриват грешки
Пълното търсене може също да се ускори:
Може да пре-процеснат изображенията така, че повърхнината на грешката де плавна и минимумите да са широки. Тогава е по-вероятно началното предположение да попада някъде по склона на широкия минимум. Можем да „пълзим“ по склона без да изчисляваме цялата повърхнина.
Освен остротата на ръбовете в сцената, големината на кернела също определя ширината минимума.
Съвременните процесори съдържат SIMD ядра, които значително ускоряват проследяването.
Началното предположение за позицията може да се получи от :
Проследяване на практика
*
14
Company Confidential © by MM Solutions EAD
Неуспешно проследяване
Или кернелът, или позицията на най-добро съвпадение се оказва без достатъчно контраст за да се смята за надеждна
Винаги има най-добро съвпадение, дори когато то е твърде лошо.
Не търсим извън региона, но когато най-малката грешка е на границата, истинският минимум вероятно е извън него
Дрифт
Когато се движим покрай някаква точка от сцената, нейният изглед в камерата може да се променя. От там, точната позиция на проследяваната точка вече не е ясно дефинирана
Точка за проследяване може да се получи от пресичане на две линии от 2 обекта на различна далечина. Движението на тяхната пресечна точка в кадрите не съответства на движението на статичните обекти.
Точност и надеждност
Груби грешки (outliers)
Груби грешки са точки, които са проследени до грешно място – подобно изглеждащи точки, repetitive pattern, покселизация на наклонен ръб, движеши се обекти и др. Могат да бъдат открити или след напасване то на глобална трабнсформация, или ако се допусне че съседни точки би следвало да имат подобно поведение.
Геометрични трансформации
Откриваме и проследяваме точки между кадри за да съберем информация за трансформацията от кадър в кадър.
Точките в другия кадър може да са изместени спрямо очкваните им позиции:
Целия кадър може да се трасформира геометрично така че кадрите да се напаснат
Ако камерата само се завърта, напасването е идеално
Ако камера се премества и сцената е 3Д, идеално напасване не е възможно
Движещи се точки могат да бъдат открити – техните движения не съответстват на трансформацията на кадъра
Кернела за проследяване обикновено е малък и при подходяща сцена и разлики между кадрите може да пасне най-добре на грешно място.
При повтарящи се текстури (напр. ограда) проследяваната точка може прилича на много други (repetitive pattern)
*
15
Company Confidential © by MM Solutions EAD
Геометрични трансформации
Според очакваните разлики между кадрите може да се напасват различни геометрични трансформации
x’ = cos(a).x – sin(a).y +tx
y’ = sin(a).x + cos(a).y +ty
x’ = (a.x + b.y + c) / (g.x + h.y + 1)
y’ = (d.x + e.y + f) / (g.x + h.y + 1)
*
16
Company Confidential © by MM Solutions EAD
Част от 8те параметръра са взаимо-зависими, реланите степени на свобода са 6 (3 ротации и 3 транслации на камерата). Но, допълнителните степени на свобода позволяват по-добро напасване на практика, а и правят системата почти линейна – може да с регресия или собствени вектори.
Геометрични трансформации
x’ = a.x + b.y + c
y’ = d.x + e.y + f
Опростен жариант на хомографията.
Трансформира триъгълник в триъгълник. Графичните
процесори опизват геометрията на сцената с триъгълници
Лесна за регресия – две независими регресии с по 3
неизвестни
Горните трансформации за подходящи когат изображенията са без изкривявания
За повече степени на свобода, при запазване на възможността за използване на регресия, може да се ползват полиноми за x’ и y’ от някаква степен, подходяща за конкретния слючай.
При по-сложни трансфомации – напр. Между кадри с изкривявания, не е нужно трансфомацията да се представена с формула. Може да в фуннкция, съдържаща много формули, използване на таблици и др. Тогава напасването става с оптимизационна задача.
*
17
Company Confidential © by MM Solutions EAD
Геометрични трансформации
Изчисляване на линейна геометрияна трансформация
Когато имаме аналитично зададени, линейни функции, можем да намерим параметрите, които най-добре описват двойките точки с линейна регресия – система линейни уравнения по броя параметри (степени на свобода), които минимизират квадратичната грешка. За случая с афина трансформация:
xi, yi, xi”, yi” са реалните позиции на точката в двете изображения
x’ = a.x + b.y + c : очаквана позиция в другото изображение
y’ = d.x + e.y + f : очаквана позиция в другото изображение
erri = (xi“ - xi’)2 + (yi“ - xi’)2
err = SUMi ( erri )
еrri може да се разглежда като кръгъл параболоид в координатната система на грешките в позицията (xi“ - xi’), (yi“ - xi’)
Използване на точки по ръбове
В някой изображения/сцени можа да няма достатъчно добри точки, но да има ръбове (линии). Те също носят информация за общата транформация, но само в една посока – напречно на линията.
Такива точки също може да се използват в регресията. Вместо кръгъл параболоид – разтегнат такъв:
erri = pi*(xi“ - xi’)2 + qi*(yi“ - xi’)2 + ri*(xi“ - xi’) *(yi“ - xi’)
*
18
Company Confidential © by MM Solutions EAD
Геометрични трансформации
Откриване и премахване на груби грешки
Най-простия метод е да се изключат точките с най-големи грешки erri. Срерднокардратичната решка се явява стандартна девиация на точките около очакваните им позиции:
Изклюзваме всички точки с грешка >3х средата, изчисляваме нова трансформация, отново всички грешки, изключваме ... докато на новата итерация не сме изключили нищо.
Този метод работи до около 10% груби грешки, т.е. Поредполага точно проследяване на точки.
При твърде много грешки, или при клъстеризирани грешки: RANSAC
Избираме случане малък набор оит точки, намираме трансформация, проверяваме кои от останалите точки са удовлетворени от тази трансформация. Повтаряме това много пъти и в накрая избираме тази трансформация, която удовлетворява най-много точки.
Има много варианти на RANSAC – основно за подобряване на бързодействието, чрез използване наинформация специфична за конкретния случаи.
robust_erri = s2 * ( sqrt( 1 + 2.erri / s2 ) – 1 ) : Psudo-Huber – има линеен наклон (s) далече от минимума
*
19
Company Confidential © by MM Solutions EAD
Прилагане на трансформации
Геометричните трансформации обикновено се пролагат от графичен процесор
Трансформацията се представа с мрежа от точки (grid, mesh)
*
20
Company Confidential © by MM Solutions EAD
Подходяща за не-графичен проицесор�Интерполацията в рамките на една клетка може да бъде:
Подходяща предимно за графичен проицесор�Всяка клетка се разделя на два триъгълника. Интерполира се с афина трансфомация във всеки триъгълник
локални трансформации
Понякога не проследяваме точки за да определим глобална трансформация, а за да открием локалните движения в сцената. Те не могат да се представят аналитично.
Точките са разположени в мрежа, сравнително на гъсто. Част от тях попадат върху плоски участъци или върху линии – т.е. не могат да се проследят надеждно.
След проследяването, грешно- и не- проследените трябва да получат адекватни позиции в другия кадър, като се използват недеждно-проследените им съседи.
Може да се направи с филтър, или с голяма оптимизационна задача, която, обаче, използва sparse-матрица.
*
21
Company Confidential © by MM Solutions EAD
Проследяване с дескриптори
SAD,SSD и CC не се справят добре когато изображенията са завъртени, различно увеличени или силно изкривени
Самият кернел от по-горе може да се разглежда акто дескриптор – NхМ числа, представляващи стойностите на пикселите около точката.
Нормализацията на кернела вече представлява трансформация на пикселите, която ги прави инвариантни към определен тип различност – яркост и/или контраст
Може да се анализират стойностите в околността на точката и да се открие ротация, която да максимизира градиента по Х. След това пикселите от кернела може да се семплират от ротирани позиции.
Ако ротацията между кенела и мястото му в другото изображение не е известна, при всяка проба, региона около текущата трябва да се нормализира по завъртане и да се семплира ротиран – много бавно.
По-опростен вариант е да се ротира еднократно целия регион на търсене. Той, обаче, може да съдържа повече обекти извън кернела, които да променят ротацията.
*
22
Company Confidential © by MM Solutions EAD
Проследяване с дескриптори
Друг подход:
Тук дескрипторите се изчисляват бавно, но по-рядко (няма проследяване). Обаче, точките са много повече. Намирането на съответни точки изисква още повече ставнения на дескриптори - то трябва да е бързо.�Ползват се kd-дървета за намаляване на сравненията.
Инвариантен към ротация, транслация и увеличелие. 128 float числа.
Цели качество, подобно на SIFT, но със значително по-малко изчисления
BRIEF дескрипторът представлява набор от двойки пиксели около точката. Пикселите от всяка двойка се сравняват и продуцират 1 бит от дескриптора. Най-често се ползват 256 двойки (256 битов дескритор). ORB добавя ориентация: първо се намира ориентацията на изображението в околността, тогава позициите на двойките се завъртат и пикселите се прочитат от така завъртяните позиции.
*
23
Company Confidential © by MM Solutions EAD
Благодаря �за �вниманието
*
24
Company Confidential © by MM Solutions EAD