Fuziune Senzoriala la Retele Mobile de Senzori cu Aplicatii In Urmarire Si Localizare

=== Anexa ===

Anexa

A.1 Salvare date intrare

function saveMarkovLocInputs

% R1 R2 R3

l = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ;

1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ;

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ;

0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 ;

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ];

T = 7;

N = 5;

M = 5;

% R1 R2 R3

s = [1 1 1 ;

0 0 0 ;

1 1 1 ;

1 1 1 ;

1 1 1 ;

1 1 1 ;

0 0 0 ];

a = [0 0 0 ;

1 1 1 ;

0 0 0 ;

0 0 0 ;

0 0 0 ;

0 0 0 ;

1 1 0 ];

dir = [0 0 0;

0 3 3;

0 0 0;

0 0 0;

0 0 0;

0 0 0;

0 3 0];

o = [1.4142 1.4142 1.4142;

0 0 0;

1 1 1;

1 1 1;

1 1 1;

1 1 1;

0 0 0];

angl = [-pi/4 -3*pi/4 -pi/4;

0 0 0 ;

-pi/2 -pi 0 ;

-pi/2 -pi 0 ;

-pi/2 -pi 0 ;

-pi/2 -pi 0 ;

0 0 0 ];

sigma = [1 1 1 ;

1 1 1 ;

1 1 1 ;

1 1 1 ;

1 1 1 ;

1 1 1 ;

1 1 1 ];

p =[0.1068 0.8909 0.5000 ;

0.6538 0.3342 0.4799 ;

0.4942 0.6987 0.9047 ;

0.4942 0.6987 0.9047 ;

0.4942 0.6987 0.9047 ;

0.4942 0.6987 0.9047 ;

0.6538 0.3342 0.4799 ];

NR = 3;

lim = [1 1 1.5 ];

r = [1 3 2 ];

KnownObstacle = [0 0 0 0 1 ;

0 0 0 0 0 ;

0 1 0 0 0 ;

0 0 0 0 0 ;

0 0 0 0 1];

save 'saveMarkovLocInputs.mat' l T N M a dir s o p angl NR lim r sigma KnownObstacle

A.2 Algoritm de Localizare Markov. Implementare Matlab

function B = MarkovLoc(n, s, o, angl, sigma, p, a, dir, N, M, l, T, KnownObstacle, FlagKnO)

% l = locatia pt care calculez increderea robotului ca se afla in l

% n = robotul al n-lea

% s = date primite din masuratori de la senzori

% a = date primite din odometrice (numar de cate ori s-au invartit rotile)

% N, M = dimensiuni spatiu de lucru

if T > size(s,1)

T = size(s,1);

end

B = ones(N,M);

BE = zeros(N,M);

for t = 1 : T

if (s(t) ~= 0) % dk primeste s at s <> 0 si a == 0

alphaT = 0;

if (FlagKnO)

for i = 1: N

for j = 1 : M

d = estDistMinObj(B,i,j, KnownObstacle);

BE(i,j) = normpdf(d(1,1),o(t),sigma(t))* normpdf(d(2,1), angl(t),sigma(t)) * B(i,j);

alphaT = alphaT + BE(i,j);

end

end

B = BE / alphaT;

else

for i = 1: N

for j = 1 : M

BE(i,j) = geopdf(B(i,j), p(t)) * B(i,j) ;

alphaT = alphaT + BE(i,j);

B(i,j) = BE(i,j) / alphaT;

end

end

end

end

if (a(t) ~= 0) % dk primeste a at a <> 0 si s == 0

for i = 1: N

for j = 1 : M

B(i,j) = normpdf( l( transfDir(i, j, dir(t))), B(i,j), a(t)) * B(i,j);

B

end

end

end

end

A.3 Estimare distanta si unghi pana la cel mai apropiat obstacol

function dmin = estDistMinObj(B,k,l, KnownObstacle)

[N,M]= size(B);

nrO = 0;

for i = 1 : N

for j = 1 : M

if KnownObstacle(i,j) ~= 0

nrO = nrO + 1;

end

end

end

d = zeros(2, nrO);

sd = 1;

for i = 1 : N

for j = 1 : M

if ((KnownObstacle(i,j) ~= 0) && (B(k,l) ~= 0))

d(1, sd) = sqrt((k-i)^2+(l-j)^2);

if (d(1,sd) == 0 )

d(2,sd) = 0;

else

d(2, sd) = atan((k-i)/(l-j));

end

sd = sd+1;

end

end

end

v = 0;

dmin = zeros(2,1);

for i = 1: size(d)

if d(1, i) ~= 0

dmin(1,1) = min(d(1,:));

v = dmin(1,1);

end

end

for i = 1: size(d)

if d(1, i) == v

dmin(2,1) = d(2,i);

end

end

A.4 Algoritmul de localizare multi-robot

function Bel = LocalSubTeam(N, M, NR, l, lim, r, s, o, angl, sigma, p, a, dir, T, KnownObstacle, FlagKnO)

% N = nr de roboti

% NE = sub-echipa

% la mom t0 impart robotii in subechipe

R = zeros(2, NR);

[R, NrE] = repartSubTeam (NR, N, M, lim, r, s, o, angl, sigma, p, a, dir, l, T, KnownObstacle, FlagKnO);

NE = max(R(2,:));

Bel = ones(N, M * NR);

startIndex = 0;

for e = 1: NE

nrRoboPerE = NrE(2,e);

%pentru fiecare robot din echipa –> AutoLocalizare

for i = 1 : nrRoboPerE

startIndex = startIndex + 1;

n = R(1,startIndex);

Bel(:,(n-1)*N +1 : n*N) = MarkovLoc(n, s(T,n),o(T,n), angl(T,n), sigma(T,n), p(T,n), a(T,n), dir(T,n), N, M, …

l(:,(n-1)*N +1 : n*N), T, KnownObstacle, FlagKnO);

end

end

startIndex1 = 0;

Bel_Ant = zeros(N, M * NR);

Bel_Ant = Bel;

for e = 1: NE

nrRoboPerE = NrE(2,e);

% construiesc Bel robotilor din echipa in fct de Bel coechipieri

if nrRoboPerE > 1

for i = 1 : nrRoboPerE

startIndex1 = startIndex1 + 1;

n = R(1,startIndex1);

sumaProb = zeros(N,M);

for m = 1 : nrRoboPerE

if m ~= n

d = calcDistRobo(Bel_Ant(:,(n-1)*N+1 : n*N), Bel_Ant(:,(m-1)*N+1 : m*N));

if d ~= 0

Prob = normpdf(Bel_Ant(:,(n-1)*N+1 : n*N), Bel_Ant(:,(m-1)*N+1 : m*N), d);

else

Prob = 1;

end

sumaProb = sumaProb + Prob * Bel_Ant(:,(m-1)*N+1 : m*N);

end

end

Bel(:,(n-1)*N +1 : n*N) = Bel(:,(n-1)*N +1 : n*N) * sumaProb;

end

end

end

A.5 Repartizarea pe echipe

function [R,NrE] = repartSubTeam (NR, N, M, lim, r, s, o, angl, sigma, p, a, dir, l, T, KnownObstacle, FlagKnO);

% NR = nr de roboti

% lim = vector cu limitarile de comunicatie a robotului n

% r = vector cu toate razele de actiune a senzorilor plasati pe robotul n

BelGen = ones (N, NR*M);

Bel = ones(N,M);

% BelGen va fi o matrice ce va contine matricele de incredere ale tuturor

% robotilor …concatenate (Bel(1) | Bel(2)| …… | Bel(NR))

for n = 1 : NR

% localizare Markov pe baza de infos preluate de la senzori

Bel = MarkovLoc(n, s(:,n), o(:,n), angl(:,n), sigma(:,n), p(:,n), …

a(:,n), dir(:,n), N, M, l(:, (n-1)*M + 1 : n*M), T, KnownObstacle, FlagKnO);

BelGen(:,(n-1)*N+1 : n*N) = Bel;

end

BelGen

% calculez distantele intre roboti => matrice(NR, NR)

distanta = zeros(NR, NR);

for i = 1 : NR

for j = i+1 : NR

distanta(i,j) = calcDistRobo(BelGen(:,(i-1)*N+1 : i*N), BelGen(:,(j-1)*N+1 : j*N));

distanta(i,j) = distanta(i,j);

end

end

distanta

% initial asignez robotul 1 echipei 1

R = zeros(1,NR);

R(1,1) = 1;

R(2,1) = 1;

nrE = 1; % initial nr de echipe = 1

for i = 1 : NR – 1

for j = i+1 : NR

if (distanta(i,j) <= lim(i) + lim(j)) && ….

(r(i) > distanta(i,j)) && ….

(r(j) > distanta(i,j))

R(1,j) = j;

R(2,j) = R(2,i);

else

R(1,j) = j;

R(2,j) = nrE;

nrE = nrE + 1;

end

end

end

nrE

NrE = zeros(2, nrE);

for i = 1 : nrE

nrR = 0;

NrE(1,i) = i;

for j = 1 : NR

if R(2,j) == i

nrR = nrR + 1;

end

end

NrE(2, i) = nrR;

end

A.6 Calcul distanta intre roboti

function dist = calcDistRobo(BelRobo1, BelRobo2)

[N,M] = size(BelRobo1);

RoboBel1 = max(max(BelRobo1));

RoboBel2 = max(max(BelRobo2));

Robo1_i = 0 ;

Robo1_j = 0 ;

Robo2_i = 0 ;

Robo2_j = 0 ;

for i = 1 : N

for j = 1 : M

if BelRobo1(i,j) == RoboBel1

Robo1_i = i ;

Robo1_j = j ;

end

if BelRobo2(i,j) == RoboBel2

Robo2_i = i ;

Robo2_j = j ;

end

end

end

dist = sqrt((Robo1_i – Robo2_i)^2 + (Robo1_j – Robo2_j)^2);

=== Fuziune senzoriala ===

Cuprins

Introducere

2. Aspecte teoretice

2.1Terminologie

2.2 De ce fuziune senzoriala?

2.3 Cum fuzioneaza informatiile

2.4 Arhitectura unui sistem SDF

2.4.1 Definitia arhitecturii

2.4.2 Motivarea in a folosi arhitectura

2.5 Un sistem ierarhic automom general

2.6 Metode de fuziune

2.6.1 Obtinerea de valori precise

2.6.2 Privire generala asupra metodelor de fuziune

2. Prezentarea unor algoritmi inruditi

2.1 Localizarea in secvente video bazata pe o abordare legata de multirezolutie

2.1.1 Algoritmul propus

2.1.1.1 Modulul de compensare al background-ului

2.1.1.2 Modulul de updatare a backgroundului

2.1.1.2.1 Numarator de pixeli inserati pe margine (Edge pixel insertion counter)

2.1.1.2.2 Counter pentru modificarea gradientului

2.1.1.3 Extragerea marginilor tranzitorii

2.1.2 Reunirea (CLUSTERING) muchiilor tranzitorii

Obtinerea poligonului de incadrare

Implementarea

Sistem de localizare a unui obiect folosind mai multi senzori

Localizarea obiectelor bazata pe datele prelevate de la mai multi senzori

Estimarea starii sistemului monomodal

Estimarea starii multimodale

Modelul ……(Single State Model)

Modele …….. (Multiple State Models)

Estimarea starii neliniare (Nonlinear State Estimation)

Implementarea unui sistem de de localizare audio-vizuala

Localizarea audio

Localizarea video

Centrul de fuziune

Implementarea in timp real

Analiza cantitativa

Discussion and Conclusions

Bibliografie:

Imbunatatirea auto-localizarii de catre roboti folosind fuziunea senzoriala

Lucrari apropiate

Localizarea Markov

Algoritmul de localizare Markov

Algoritmul Markov de localizare multi – robot

Dezavantaje ale localizarii Markov

Algoritm de localizare cu distributia echipelor

Masurarea incertitudinii

Comunicatia

Sub-echipa

Fuziunea informatiilor intr-o subechipa

Fluxul informatiei intr-o subechipa

Fuziunea informatiilor intre doi membri ai unei subechipe

Localizarea cooperativa

Rezultatele simularii

Concluzii

Bibliografie

3. Descrierea aplicatiei

3.1 Descrierea algoritmului

3.2 Compresia Datelor pentru Supraveghere Video

3.3 Prototipul Algoritmului de Detectie a Miscarii

4. Studiu de caz. Echipa de roboti. Rezultate experimentale.

5. Concluzii

6. Bibliografie

Introducere

Putem spune ca un sistem este autonom in conditiile in care este capabil „a simti”, a primi informatii din mediul in care lucreaza si de a interactiona in acelasi timp cu acesta, in caz contrar toate taskurile trebuind sa fie bine determinate a-priori. Beneficiind de avantajul sensibilitatii, un sistem autonom isi poate astfel programa, planifica singur taskurile in conformitate cu starea actuala a mediului in care desfasoara acel task. In plus el poate decide daca totul se desfasoara conform planului de lucru, fiind asfel posibila o continua monitorizare, adaptare a comportamentului si detectare a situatiilor de exceptie.

In majoritatea situatiilor sistemele autonome actuale nu se pot baza decat pe fuziunea datelor provenite de la mai multi senzori, intrucat unul singur nu poate prelua atat de precis starea mediului incat sa si permita o functionare autonoma. Masuratorile preluate de la mai multi senzori pot fuziona pentru completarea reciproca obtinand astfel o informatie mult mai precisa, dar si pentru a coopera in vederea obtinerii unor informatii ce nu erau accesibile fara cooperarea senzorilor.

Esentiala in cadrul monitorizarii activitatii dintr-o incapere sau a unor obiecte aflate in miscare, capacitatea de urmarire a unui sistem, de a construi calea urmata de robot, se poate dovedi foarte utila in anumite situatii cum sunt ………

In acelasi timp este important ca intr-o retea de senzori, acestia sa isi stie pozitia ocupata, iar in cazul in care senzorii sunt pozitionati pe roboti mobili determinarea pozitiei si a directiei de miscare devine imperativa. Un exemplu in care apare necesitatea unui sistem de (auto)localizare este cel al aeronavelor cu pilot automat. In plus, pentru a oferi date corecte (in cazul in care reteaua de senzori este folosita pentru monitorizarea sanatatii, achizitiile de date in medii periculoase, operatiuni militare si securitate) sau pentru a-si sti cu exactitate locatia (in cazul avioanelor cu pilot automat) este nevoie ca estimarea pozitiei sa nu fie afectata de zgomot de masurare.

Aspecte teoretice

Majoritatea sistemelelor autonome au o structura ierarhizata pe mai multe niveluri. La sistemele de recunoastere cu structura ierarhica de exemplu, fuziunea senzoriala ar trebui realizata la primul nivel de abstractizare unde sunt folositi mai multi senzori.

Intrucat fuziunea senzoriala ar trebui aplicata la modul general sistemelor autonome, in prima parte a acestui capitol se prezinta un acest gen de sistem. In sectiunea a doua se prezinta termiologia adoptata, continuandu-se apoi cu o discutie detaliata privind importanta, mai corect necesitatea, fuziunii informatiilor preluate de la mai multi senzori in partea a treia. Dezavantajele cele mai intalnite ale preluarii datelor sunt prezentate in sectiunea 4 impreuna cu modalitatea de a depasi aceste deficiente prin folosirea fuziunii senzoriale. In urmatoarea sectiune (a 5-a) vo continua prin a prezenta o arhitectura pentru un sistem autonom SDF (SDF = Sensor Data Fusion) motivand in acelasi timp alegerea unei astfel de arhitecturi. In a 6-a sectiune vom da un exemplu de sistem autonom general cu arhitectura ierarhica pentru a evidentia ca un sistem SDF poate fi aplicat pe diferite nivele ale ierarhiei. Concluzionand, in sectiunea a 7-a se prezinta cateva metode de fuzionare, avantajele fiecarei metode prezentate pe diferite nivele ale ierarhiei.

In sectiunile remanente ne vom focaliza atentia asupra sistemului autonom de navigatie. In sectiunea a 8-a se va discuta despre o reprezentare interna potrivita atat Fuziunii senzoriale cat si pentru indeplinirea taskului de navigare. In sectiunea a 9-a se va defini metoda de fuzionare care se va folosi pentru reprezentarea interna. In ultima sectiune se va prezenta unde anume in aceasca arhitectura sistemul SDF va fi avantajat de folosirea teoriei retelelor neurale.

1.1 Terminologie

Intrucat cercetarile in acest domeniu sunt relativ recente si in plina desfasurare, nu s-a standardizat inca o terminologie.

In figura 1 se da o schema a unui senzor optic ilustrandu-se componentele specifice ale acesuia. Se disting urmatoarele componente:

Figura.1: Elementele constituente ale unui senzor (optic)

Traductorul este dispozitivul de masurare ce realizeaza conversia marimii fizice intr-un semnal electric.

Iesirile traductorului, de obicei constand in semnale analogice (A), sunt digitizate CNA. Rezultatul este un semnal digital (D) reprezentand masuratori asupra mediului (in aces caz, culoarea reflectata).

Masurarea propriu-zisa cu un traductor impreuna cu digitizarea acesteia este numita perceptie.

Masuratorile sunt procesate pentru a obtine informatia ce prezinta interes pentru sistemul autonom (de exemplu segmentarea imaginii in regiuni libere si regiuni ocupate). Acest proces se numeste conversie.

Obtinerea si transformarea marimilor fizice este realizata de catre un senzor virtual.

Masuratorile convertite sunt folosite pentru a constitui modelul mediului de lucru al unui robot, lucru ce se numeste reprezentare interna. Reprezentarea propriu-zisa a mediului robotului se numeste model intern. Dinstinctia intre cei doi termeni se poate face tinand cont de urmatoarea analogie: reprezentarea interna constituie un limbaj iar modelul intern este mesajul transmis. Astfel, in reprezentarea interna, marimile convertite sunt numite parametri.

Modulul de conversie al unui senzor poate face orice prelucrare de la conversie (timpul de propagare masurat cu un senzor de proximitate) pana la interpretarea modelului intern de pe un nivel inferior al ierarhiei. Astfel, la nivelele superioare ale ierarhiei senzorii nu includ traducatoare, ci mai degraba „simt” modelul intern al nivelelor inferioare.

De ce fuziune senzoriala?

De cele mai multe ori sistemul nu se poate baza pe informatia primita de la un singur senzor, astfel incat apeleaza la fuziunea masuratorilor primite de la mai multi senzori pentru a avea informatii precise. In aceasta seciune sunt prezentate primcipalele defecte ale masuratorilor efectuate cu senzori, in sensul ca rezultatele sunt incerte si/ sau incomplete.

Incertitudine masuratorilor inseamna ca senzorii pot doar estima parametrii reprezentarii interne. Aceasta incertitudine poate avea mai multe cauze si poate apare in diferite zone ale unui senzor asa cum s-a aratat in sectiunea precedenta.

O cauza a incertitudinii ar putea fi rezolutia limitata a traductorului. Spre exemplu, un sensor de ultrasunete cu raza de actiune pentru a masura distanta pana la cel mai apropiat obstacol este de obicei incert in ceea ce priveste unghiul fata de axa centrala a senzorului fata de care e masurata distanta. Sonarul emite o unde care este reflectata de un obstacol aflat undeva in zona conica. Cand unda reflectata este receptata de sonar, acesta poate estima cu acuratete distanta pana ala acest obiect bazandu-se pe timpul de propagare a undei. Totusi, nu se poate determina de la ce unghi din con se reflecta unda.

Figura 2: Datorita unghiului cu deschidere mare, senzorul nu poate determina cu precizie pozitia obstacolului pana la care e masurata distanta , in interiorul conului

Traductoarele sunt afectate de zgomotul de masura, ca e exemplu datorita fluctuatiei in capacitatile rezistantelor din curcuitul electric al traductorului.

Incertitudinea mai este provocata de conversia inadecvata a masuratorilor. Aceasta se intampla deoarece metodele de conversie pot doar aproxima comportamentul modulului de perceptie. Metodele nu iau in calcul caractersticile mediului de lucru ce pot influenta comportamentul acestui modul intrucat ar fi greu de modelat. Cateva exemple de influente ale mediului sunt urmatoarele:

Influenta fluctuatiilor de temperatura asupra comportarii senzorilor folositi pentru determinarea timpului de propagare. Aceste influente sunt greu de modelat si din aceasca cauza de cele mai multe ori nu sunt luate in considerare la constituirea metodei de conversie. Erorile generate de influentele de mediu sunt numite erori erori de masurare sistematice.

Un alt exemplu de erori de masurare nesistematice foarte des neglijate de metodele de conversie sunt citirile spontane (accidentale), la modul ca traductorul detecteaza un obstacol ce nu exista de fapt (primeste o unda de la un alt traductor si interpreteaza unda ca fiind o unda trimisa de el si care s-a reflectat intr-un obstacol).

Un alt tip de eroare de masurare nesistematica este aparitia reflexiilor, cand un traductor nu depisteaza un obstacool atunci cand acesta exista (cazul in care un obstacol reflecta o unda emisa de un traductor din afara razei de actiune a traductorului).,

Faptul ca informatiile sunt incomplete inseamna ca un singur senzor nu poate prelua toata informatia. Spre exemplu o singura camera fixa nu poate cuprinde toata zona de lucru a unui robot mobil. Pentru a obtine o imagine completa a zonei de lucru sunt necesare mai multe camere. Un alt motiv ce poate provoca obtinerea unor informatii insuficiente este prezenta unor obstacole in calea camerei. Insuficienta informatiilor poate aparea si in alte modalitati (o camera video poate oferi doar o imagine 2D). Uneori Insuficienta datelor este tratata ca o totala incertitudine insa noi vom face diferentierea indicand variatele cauze ale incertitudinii.

1.3 Cum fuzioneaza informatiile

Conform celor enuntate mai sus este necesar ca un sistem sa contopeasca informatii redundante primite de la mai multi senzori. (Redundant = mai multi senzoori care masoara acelasi lucru). Exista 3 tipuri de fuziune senzoriala:

Definitia 1 Fuziune Complementara: fuziunea masurarilor incomplete de la mai multe surse disparate.

Ca exemplu evidentiem fuziunea catorva senzori de proximitate sau senzori vizuali orientati in directii diferite. Un alt exemplu este cel al fuziunii masuratorilor unor senzori care preiau diferite aspecte ale aceluiasi obstacol (exemplu: pozitie si culoare).

Definita 2 Fuziune Competitiva: fuziune unor masuratori redundante de la surse diferite.

Spre exemplu, datele prelevate de la un senzor de apropiere cu unda laser si un senzor audio indreptate catre acelasi obstacol permit determinarea distantei si a unghiului pana la obstacol. Acest tip de fuziune este in genere folosita pentru a reduce incertitudinea masuratorilor. In plus, fuxiunea competitiva mai poate fi folosita in domeniul timp (fuziunea datelor preluate de la masuratorile succesive ale aceluiasi senzor), ceea ce reduce erorile aleatoare si nu cele sistematice.

Definitia 3 Fuziune Cooperativa: fuziunea marimilor fizice inaintea sau in timpul conversiei.

Acest tip de fuziune este folosit la senzorul tri-aural, senzor ce consta din 3 senzori audio , dintre care unul fuctioneaza ca transmitator, iar ceilalti ca receptori. Prin fuziunea celor 3 masuratori (folosind traiangularizarea si diferentele de faze) in timpul conversiei, se pot obtine date mult mai precise.

Fuziunea cooperativa este folosita indeosebi atunci cand se doreste reprezentarea interna la un innalt gran al abstractizarii, cum este cazul in care senzorii se folosesc de fuziunea cooperativa pentru a obtine un rezultat. Exemplul tipic este cel al folosirii unei reprezentari interne 3D. In acest caz are loc transformarea a 2 imagini 2D (folosind triangularizarea) in rezultatul unui singur senzor, corespunzand unei estimari a parametrilor unui model intern 3D.

Este important de remarcat faptul ca atunci cand este folosita fuziunea cooperativa, senzorii implicati depind unul de altul pentru a obtine un rezultat. Deci acest tip de fuziune nu se poate realiza daca una dintre masuratorile fizice propriu-zise nu este efectuata sau esueaza.

1.4 Arhitectura unui sistem SDF

In aceasta sectiune se prezinta arhitectura unui sistem SDF ce poate fi aplicata la oricare din nivelele unui sistem ierarjic automom.

1.4.1 Descrierea arhitecturii

Arhitectura unui sistem SDF generic trebuie sa fie capabila sa fuzioneze date preluate de la diverse tipuri de senzori. Spre exemplu in cazul unui robot mobil echipat cu dispozitive de masurare cu infrarosu, dispozitive audio, senzori tactili si camere video se poate realiza fuziunea masuratorilor prelevate de la acesti senzori doar daca ei „vorbesc aceeasi limba”, ceea ce inseamna ca datele trebuie mai intai convertite la un mod de reprezentare intern comun si abia apoi se poate realiza fuziunea propiru-zisa. Aceasta abordare este schitata in figura 3.

Figura 3: Arhitectura unui sistem SDF. Datele preluate de la senzori trebuie mai intai convertite la un mod de reprezentare intern comun iar apoi se realizeaza fuziunea propiru-zisa.

Aceasta arhitectura poate fi definita dupa cum urmeaza:

Datele preluate de la senzori sunt mai intai convertite la modul intern de reprezentare.

Aceasta reprezentare interna este comuna tuturor senzorilor.

Fuziunea datelor se realizeaza cu aceste date prelucrate.

Desi pare logica modalitatea in care se realizea fuziunea prin folosirea arhitecturii sunt multe sisteme ce realizeaza fuziunea datelor inainte de a reliza conversia lor in reprezentarea interna. De exemplu la masuratorile de distante folosind senzori audio si cu infrarosu, fuziunea este realizata inaintea obtinerii unei estimari a parametrilor. Acest lucru indica faptul ca modulele de perceptie depind unele de altele pentru a obtine o singura estimatie in reprezentarea interna. Aceasta a fst anterior denumita „fuziune cooperativa”. Diferenta intre fuziunea cooperativa si tipurile de fuziune complementara si respectiv competitiva este schitata in Figura 4.

Figura 4: Fuziunea cooperativa a masuratorilor senzorilor are loc la nivelul unui singur senzor: la nivelul senzorului 2 doua module de perceptie (in acest caz 2 camere video) coopereaza pentru obtinerea unui rezultat. Fuziunea competitiva si cea complementara se realizeaza la nivelul reprezentarii interne: senzorii 1 si 2 sunt in competitie pentru a genera o estimatie cat mai precisa a cubului, in timp ce senzorul 3 complementeaza modelul intern prin estimarea celuilalt obiect din scena.

1.4.2 Motivarea in a folosi arhitectura

Avantajele unei asemenea arhitecturi sunt:

De a demonstra importanta valorilor exacte prin care senzorul da un estimat al incertirudinii propriei sale masuratori.

In mod contrar acestei abordari, anumite metode de fuziune fac presupuneri implicite legate de asignarea valorilor certe. Spre exemplu, un filtru Kalman considera ca valorile certe au o distributie Gaussiana centrata pe rezultatul masuratorii efectuate de senzor si numai latimea acestei distributii variaza (in timp) in functie de acuratetea senzorului. Chiar daca filtrul Kalman poate fi folosit cu succes in multe aplicatii, in multe alte cazuri functia de certitudine Gaussiana este mult prea imprecisa pentru a modela incertitudinea senzorului.

Intrucat un sistem SDF presupune ca fiecare sensor sa realizeze transfomarea catre modelul intern de reprezentare, poate fi foarte usor extins prin adaugarea altor senzori. Singura restrictie constra in faptul ca pe langa „traductorul” aditional necesar, se impune si folosirea unei conversii adecvate catre modelul intern de reprezentare.

Totusi exista sisteme SDF care nu realizeaza aceasta conversie catre o reprezentare interna inainte de a face fuziunea datelor. Metoda de fuziune este aplicata direct iesirilor digitale ale traductorului, mizand pe punctele forte ale senzorului. Evident, in asemenea cazuri trebuie construit un nou algoritm de fuziune daca se vrea agaugarea de noi senzori sistemului. Deci asemenea abordari ar trebui limitate numai in cazul fuziunii cooperative.

Presupunand ca unul din senzorii din Figura 3 nu ar functiona corespunzator, acesta ar furniza estimari incorecte ale parametrilor modelului intern. Totusi, daca exista mai multi senzori (oferind astfel informatii redundante) se poate face o fuziune competitiva a datelor iar sistemul ar oferi o estimare acceptabila desi mai putin precisa a parametrilor. Sistemul per total ar fi in continuare valid, insa daca din ce in ce mai multi senzori se vor deteriora, atunci estimarea s-ar degrada si ea gradual.

Totusi multe aplicatii folosesc fuziunea cooperativa, ceea ce presupune ca fiecare senzor depinde de ceilalti pentru a genera un rezultat (virtual) valid. Evident, in acest caz este suficient ca numai un singur senzor sa nu functioneze corect pentru ca intregul sistem sa nu mai fie valid.

Arhitectura SDF permite implementarea unui sistem ce fucntioneaza in paralel, acest lucru fiind de mare folos mai ales in cazul in care sistemul trebuie sa functioneze in timp real.

Desi se impune ca datele preluate de la senzori sa fie mai intai convertite intr-un mod de reprezentare intern, aceasta conversie ridica o problema de mare importanta in aplicatiile de acest gen. Totusi desi se castiga mult prin separarea fuziunii si a conversiei, se depune un mare efort in a definii functii corecte de conversie.

1.5 Un sistem ierarhic automom general

Anterior s-a spus ca un sistem SDF este potrivit oricarui nivel intr-un sistem autonom ierarhizat general. Pentru a ilustra mai bine metodele de fuziune se va considera un astfel de sistem aplicat unui joc de Basket cu 2 roboti.

Regulile sunt:

Fiecare concurent dispune de 5 mingii si 3 gloante. Fiecaruia dintre competitori ii este asignat un cos.

Primul concurent ce reuseste sa puna toate mingiile sale in cosul adversarului castiga.

Cand unul dintre roboti isi fixeaza adversarul in tinta poate trage un glont pentru a-si paraliza pe moment inamicul.

Robotul poate fi paralizat pe moment si in cazul ciocnirii cu un obstacol, adversar sau cos.

Concurentii si cosurile au aceeasi forma (cerc), iar obstacolele au forme diferite (dreptunghiulare).

Mediul in care se desfasoara jocul este prezentat in Figura 5.

Figura 5: terenul pentru meciul de basket cu roboti.

Treaba unui sistem autonom ce controleaza unul dintre concurenti este sa:

Conduca respectivul robot in teren fara ca acesta sa se ciocneasca cu cocurentul, vreun obstacol sau cos.

Clasifice obstacolele intalnite astfel {cos, adversar, obstacol}.

Isi planifice comportamentul in functie de clasificarea obstacolelor.

1.6. Suma diferentelor absolute

Acesta reprezinta cel mai simplu algoritm folosit pentru a determina

Doua frame-uri consecutive sunt comparate pixel cu pixel iar apoi se face insumarea valorilor absolute ale diferentelor existente intre fiecare 2 pixeli corespunzatori celor doua cadre. Evident, rezultatul este un numar pozititv si este folosit ca valoare de verificare. Acest algoritm este foarte sensibil chiar si la modificari minuscule ale cadrelor: miscari rapide ale camerei video sau de exemplu aprinderea brusca a luminii in incaperea in care se afla camera video. Toate aceste pot constitui alarme false. Pe de alta parte, SAD percepe foarte greu modificarile subtile. Totusi este folosit adesea pentru a genera un set de posibile evenimente ce pot fi considerate ca alerte pentru sistem intrucat detecteaza toate modificarile esentiale cu cea mai mare probabilitate.

Detectia modificarii: (1) Hit: modificare importanta detectata. (2) Hit ratat: modificare subtila (dissolve), ce nu a fost detectata. (3) Hit Fals: o singura modificare subtila ce a fost interpretata eronat ca reprezentand de fapt doua modificari majore.

Exista mai multe modalitati de a realiza localizarea unor obiecte in miscare folosind mai multe tipuri de dispozitive gen senzor (camere video, senzori de proximitare, sonare etc). In continuare se vor prezenta cateva metode ce folosesc aceste tipuri de senzori, domeniile de folosire, avantajele si dezavantajele, punctele tari si cele slabe are acestor algoritmi.

2.1 Localizarea in secvente video bazata pe o abordare legata de multirezolutie [Gabriel Tsechpenakis, Yiannis Xirouhakis si Anastasios Delopoulos, Image, Video and Multimedia Systems Laboratory, Dept. of Electrical and Computer Eng., National Technical University of Athens, 9 Iroon Polytechniou str., 15773 Athens, Greece.]

Localizarea diferitelor obiecte mobile tine de un domeniu ce presupune “intelegerea” imaginilor, codificarea obiectelor, retragerea de continut, supravegherea si recunoasterea.

Subiectul acestei lucrari il constituie localizarea obiectelor aflate in miscare folosind diverse scheme pentru extragerea de informatii si un framework pentru MPEG-7, in cazul in care secventele de imagini sunt captate inauntru sau afara, daca este folosita o camera fixa sau una mobila. Aceasta abordare imbunatateste considerabil raportul intre acuratete si performanta in domeniul timp, lucru ce conduce la rezultate satisfacatoare fara a necesita un numar mare de calcule. In plus, poligonul de incadrare si directia miscarii sunt estimate pentru fiecare obiect mobil, dand astfel o reprezentare potrivita in sensul MPEG-7. Poligoanele rezultate pot fi folosite ca estimari initiale pentru metode ce extrag contururile obiectelor.

Detectia obiectelor aflate in miscare folosind secventele video reprezinta o parte importanta a multor tipuri de aplicatii cum sunt extragerea de continut, supravegherea remote si recunoasterea obiectelor. In prezent este folosita cu precadere pentru monitorizarea traficului si detectia intrusilor (in cadrul unui sistem de supraveghere).

In situatia in care sunt folosite camere statice abordarile propuse se pot imparti in 2 categorii: abordarea bazata pe trasaturi si cea bazata pe PIXELI. Printre altele se mai pot evidential abordarea pazata pe luminozitate , dar si ce bazata pe MARGINI.

In situatia in care este folosita o camera mobila, abordarile pot fi impartite in 2 categori:

se considera miscarea 3D a camerei cunoscuta si se deduc constrangerile pentru parametrii 2D de miscare ai obiectului.

se construieste un model parametric al miscarii 2D pentru MISCAREA DOMINANTA DE FUNDAL (BACKROUND DOMINANT MOTION).

Intrucat se folosesc algoritmi de segmentare a miscarii pentru a obtine obiectele, desi aduc rezultate adecvate, acesti algoritimi au timpi de executie nesatisfacatori.

Cel mai important lucru ce trebuie considerat in acest caz este compromisul ce trebuie facut intre acuratetea rezultatelor si eficienta in domeniul timp. In aceste conditii, in timp ce standardul MPEG-4 necesita o masca adecvata (ACCURATE) ce contine numai obiectul mobil, stadardul MPEG-7 necesita numai poligonul de incadrare (in unele cazul e vorba chiar de un dreptunghi).

Datorita acestui fapt, si prin comparatie cu tehnicile existente cu privire la detectia obiectelor mobile folosind camere mobile, algoritmul propus in aceasta lucrare acorda prioritate eficientei in timp, pastrand in acelasi timp o acuratete a rezultatelor care sa-i permita sa fie comparat cu algoritmi ce pun in discutie ideea segmentarii miscarii.

In comparatie cu o varianta mai veche, acest algoritm nu descrie obiectul (INTRUDER) ca un grup de puncte/pixeli pe baza MARGINILOR TRANZITORII ALE IMAGINII ( ON IMAGE TRANSIENT EDGES), ci defineste si extrage polinomul de incadrare si astfel obtine si conturul obiectului. In plus, estimarea directiei marginilor tranzitorii are imaginii impreuna cu folosirea unui criteriu binar de cautare permit localizarea si extragerea a mai mult de un singur obiect din secventa video, dar si a directiei de miscare.

In [14] se presupune ca intre secvente successive miscarea background-ului poate fi usor aproximata printr-o translatie. Totusi, updatarea backgroundului poate esua datorita nepotrivirilor intre frame-urile compensate, ceea ce duce la cresterea numarului de borduri tranzitorii, care pot sa apartina de fapt background-ului. De aceea este necesara folosirea unei alte metode de updatare a background-ului, o metoda ce poate determina daca o anumita frontiera poate fi considerate ca tranzitorie.

Se propune astfel o abordare multirezolutie pentru a imbunatati obtinerea obiectelor in miscare cu folosirea polinoamelor de incadrare in imaginile binare. Pixelii nedoriti ce raman in urma tuturor prelucrarilor asupra imaginilor pot fi cosiderati ca facand parte din obiectele aflate in miscare si pot fi eliminati prin descresterea rezolutiei.

Principalul avantaj al acestei abordari este acela ca din punct de vedere computational, costul este redus datorita faptului ca operatiile sunt efectuate asupra unor harti ale marginilor si nu asupra intregii imagini, lucru ce permite ca poligoanele de incadrare astfel obtinute (adica bordurile, marginile obiectului) sa fie folosite ca estimari initiale ale unor metode bazate pe ……..CURVE PROPAGATION, ca de exemplu METODE DE SETARE A NIVELULUI (LEVEL-SET METHODS).

Algoritmul propus

Modulul de compensare al background-ului

In problemele de detectie, mai ales cand este vorba ce o camera mobila ce achizitioneaza imaginile, miscarea fundalului este eliminata prin folosirea unui modul de compensare. Procesul de compensare a miscarii presupune estimarea miscarii camerei prin miscarea aparenta a background-ului, miscare ce trebuie diferentiata de miscarea obiectelor mobile aflate in cadru.

Schemele de estimare ale miscarii parametrice, desi imbunatatesc usor campul de miscare obtinut, duc la cresterea dramatica a costului de calcul. Este de asemenea notabil faptul ca intre frame-uri succesive, estimatiile miscarii obtinute sunt atat de mici incat sunt considerate nepotrivite dezvoltarii de modele parametrice, luand de asemenea in seama si inexactitatile schemelor de estimare a miscarii in 2D. In plus, schemele de segmentare a miscarii utilizate pentru a face diferentierea intre fundal si portiuni de obiect produc adesea costuri computationale mult prea ridicate pentru aplicatiile in timp real.

In acest caz se face presupunerea ca pentru frame-uri succesive, miscarea fundalului este una de translatie si astfel o metoda neparametrica si neiterativa de potrivire a blocurilor de imagine ar fi adecvata, insa chiar daca se face presupunerea ca miscarea fundalului este de translatie si ca obiectul in miscare acopera numai partial fundalul, se poate totusi totusi evita estimarea campului miscarii si miscora asftel timpul de calcul. Se utilizeaza deci o metoda de cautare exhaustiva de potrivire a portiunilor de imagine pentru un subset din pixelii fiecarui frame. Desi este adevarat ca obiectele de interes aflate in miscare populeaza partea centrala a scenei nu se poate face o limitare a pozitiei sau dimensiunii lor. Pixelii pentru care se efectueaza potrivirea sunt alesi pe un grid dreptunghiular uniform, a carui desitate este considerata ca parametru.

Fie intrarea NxM reprezentand dimensiunea frameului iar pM si pN procentul pixelilor pe fiecare linie si respectiv coloana a imaginii in care s-a produs miscare. Intrucat obiectele de interes ocupa numai o portiune a fiecarui frame se presupune ca o valoare mare (pNN)x(pMM) pentru estimarea miscarii apartine backgroundului si deci vor avea valori similare. Miscarea fundalului este aleasa AS A FREQUEND VECTOR OF SET U OF THE MOTION ESTIMATES, sau

unde m() = “majoritatea” operatiilor ,

f = indexul frame-ului curent,

δ(f) = miscarea fundalului de la frame-ul f-1 la frame-ul f.

Astfel, se poate estima orice I(f1) si I(f2) la momentele de timp f1 si respectiv f2.

Fie d(f1, f2) miscarea/variatia corespunzatoare a fundalului obtinuta prin adunarea δ(f)-urilor consecutive. Apoi miscarea frame-ului curent I(f) este compensata referitor la frame-ul I(fr) cu d(f1, f2) = [di dj] astfel:

unde I(i,j,f) reprezinta valoarea intensitatii unui pixel aflat la coordonatele (i,j) in frame-ul f, iar exponentul (c) reprezinta perechea frame-ului compensat.

Modulul de updatare a backgroundului

Conceptul ce sta la baza tehnicilor de updatare a fundalului este usoara insertie a regiunilor modificate din cadru in fundalul de referinta ce va fi acum interpretat ca fiind un frame nou detectat al scenei. Altfel orice modificari observate vor fi considerate fie zgomot, fie obiect in miscare (si deci obiect de interes). Cel mai mare avantaj al acestei metode este ca are capacitatea de a rejecta modificari ce se petrec datorita prezentei ECOURILOR PARAZITE (PRESENCE OF EXCESSIVE TEMPORAL CLUTTER).

Pentru a realiza updatarea fundalului referinta, sunt introduse 2 criterii si FRAME COUNTERS:

APARITIA (APPEARANCE) pixelilor pe margini in frame-ul curent

schimbarea directiei gradientului in pozitiile in care apar pixeli pe margine.

2.1.1.2.1 Numarator de pixeli inserati pe margine( Edge pixel insertion counter)

Fiecare pixel din margine (i, j) ce apare in frame-ul curent f duce la cresterea pixel-ului (i, j) din frame counter, in timp ce absenta unei margini de intrare duce la scaderea respectivului pixel.

unde E(i, j, f) reprezinta harta marginilor (E(i,j,f) is the edge map at pixel (i, j) at time instance f corresponding to frame pixel I(i,j,f) and Ce(i,j,f) is the respective frame counter value) . Deci marginile ce nu sunt afectate de modificare, de miscarea obiectului mobil au valori mari, in timp ce marginile tranzitorii dau valori mici pentru FRAME COUNTER.

Imaginea fundalului referinta este obtinuta prin limitarea counterului (impunem un prag)

unde reprezinta timpul de adaptare sau intarzierea inserata de modulul de updatare a background-ului. Acest parametru depinde de durata dorita/asteptata/predictata pentru schimbarile bruste de luminozitate (de exemplu, in cazul in care camerele sunt plasate pe teren, fulgerul poate provoca schimbari puternice a intensitatii luminii, iar in cazul in care camerele sunt platate in interiorul unei incinte, asemenea modificari pot si datorate schimbarii pozitiei sau a intensitatii sursei luminoase). Daca se presupune ca asemenea fenomene pot dura t secunde, timpul de adaptare ar trebui sa dureze mai mult de frame-uri, unde r este frame-rate-ul secventei.

2.1.1.2.2 Counter pentru modificarea gradientului

Daca apare o modificare puternica in directia gradientului pentru fiecare dintre pozitiile specificate anterior, atunci pixelii respectivi sunt considerati ca facand parte din marginile tranzitorii.

unde reprezinta un unghi, iar este modificarea directiei gradientului in pixelul (i, j) , unde G(i, j) este definita ca:

unde este gradientul at the specific image pixel.

Imaginea fundalului referinta este obtinuta prin limitarea counterului:

unde este timpul de adaptare corespunzator.

Parametrul depinde de frame-rate-ul secventei dar si de respectiva secventa, adica depinde de cat de brusc se modifica scena intre 2 frame-uri succesive.

Conditiile (4) si (7) sunt incluse intr-un modul de decizie, folosind unul dintre parametrii de limitare, sau

2.1.1.3 Extragerea marginilor tranzitorii

Intrucat si frame-ul curent si background-ul considerat ca referinta sunt imagini binare in care s-au evidentiat muchiile (BINARY EDGE IMAGE), extragerea muchiilor veriabile la nivelul pixelului (i, j) se realizeaza prin folosirea unul operator logic ce izoleaza muchiile condiserate ca intrari si care lipsesc in background-ul referinta updatat:

unde si reprezinta operatiile logice SI, respectiv NOT. Ecuatia (8) infica faptul ca muchiile tranzitorii sunt obtinute ca muchiile din frame-ul curent dupa ce s-au extras muchiile statice din background considerate la acelasi moment de timp.

Folosind operatorii logici SI/NOT se obtine o imagine cu 2 niveluri a muchiilor (T), continant atat muchiile variabile, cat si ceea ce ramane din muchiile fundalului datorita zgomotului. Astfel, filtrul median poate fi folosit pentru a reduce/rejecteaza zgomotul, intrucat muchiile obiectelor mobile sunt continue din punct de vedere spatial, in timp ce portiunile din background ce s-au adaugat imaginii rezultate sunt raspandite aleator. Totusi folosirea filtrului median pentru imagini BILEVEL este echivalenta cu filtrarea…… (BINARY MAJORITY FILTERING) si duce la rezultate nesatisfacatoare in cazul zgomotului (EXCESSIVE TEMPORAL CLUTTER). On the other hand unlike temporal clutter, mobile objects’ boundaries consist of thick transient edges. In this context, convolution with a thinning kernel is most appropriate.

Reunirea (CLUSTERING) muchiilor tranzitorii

Pana acum s-a realizat gruparea pixelilor la nivelul muchiilor tranzitorii pentru determinarea pozitiei si dimensiunii obiectului mobil. Totusi in majoritatea cazurilor in cadru pot fi prezente mai multe obiecte mobile destul de apropiate unele de altele, iar buneori chiar suprapunandu-se si astfel devine foarte importanta gruparea pixelilor. In plus estimarea directiei de deplasare a fiecarui obiect poate fi folosite in supravegherea remote cu camere vidoe ce fac si urmarirea obiectului aflat in miscare si in sisteme de extragere de continut (ALLOWING QUERIES).

In acest scop se foloseste algoritmul de estimare a miscarii prin potrivirea blocurilor de imagine. Complexitatea este neglijabila intrucat estimarea miscarii se face doar pentru pixelii ce apartin muchiilor tranzitorii. In aceasta lucrare s-a preferat numararea pixelilor ce apartin muchiilor si care sunt alocati unui anumit bloc pentru a decide care este cel mai „potrivit” bloc de imagine, in locul calculului diferentei absolute intre imagini(MEAN ABSOLUTE DIFFERENCE). Aceste informatii impreuna cu schema de grupare a miscarii (exemplu fuzzy c-mean clustering) determina clasificarea lor in obiecte mobile sau nu. In plus acest proces permite rejectarea pixelilor ce formeaza un obiect insignifiant.

Obtinerea poligonului de incadrare

Pentru fiecare obiect mobil, in ultimul modul, i se extrage polinomul de incadrare. Intrucat se pot construi mai mult poligoane care sa contina fiecare obiect mobil, se estimeaza infasuratoarea convexa (cel mai mic polinom convex ce contine setul de puncte). Se foloseste metoda Graham Scan, ce necesita un efort de calcul redus, mai ales cand coordonatele punctelor sunt numere intregi, cum e cazul acestei metode.

Criteriul pentru a decide daca unul dintre frame-urile verificate contine cel putin un obiect mobil este suma pixelolor ce s-au modificat in frame-ul respectiv:

Totusi gruparea punctelor extrase nu constituie un criteriu prea sigur pentru a decide daca exista sau nu un obiect mobil in cadru datorita faptului ca numarul de pixeli detectati pe conturul obiectului in miscare nu releva mereu marimea obiectului. Intrucat, in aceasta metoda se construieste polinomul de incadrare Pm pentru fiecare obiect mobil m, se poate folosi in locul numarului de pixeli perimetrul ariei ocupate de fiecare obiect mobil pentru a determina daca este destul de mare pentru a reprezenta un obiect mobil de interes. In aces sens ecuatia (9) se poate rescrie:

unde a este o functie ce calculeaza aria infasurarii convexe iar maxf este valoarea maxima a estimatiillor ariilor din frame-ul f. Acest proces poate fi sensibil la zgomot in cazul in care gruparea muchiilor tranzitorii esueaza.

Implementarea

Principala sursa a impreciziei in sistemul prezentat este prezenta zgomotului, adica prezenta pixelilor tranzitorii ce nu apartim obiectelor mobile si totusi raman in setul muchiilor tranzitorii extras si astfel apar probleme la extragerea poligonului de incadrare si in procedura de estimare a infasurarii convexe. In plus problemele se agraveaza in cazul in care in cadru sunt prezente mai multe obiecte mobile intrucat procedura de grupare a muchiilor tranzitorii esueaza din cauza faptului ca exista multi pixeli ramasi. Acesti pixeli persista deoarece:

schema de updatare a background-ului este „sabotata” de miscarea rapida a camerei video

significant local temporal clutter forcing random pixels to existence.

Pana acum in afara de criteriul impus asupra schemei de updatare a background-ului pentru a elimina muchiile ce nu sunt dorite se foloseste un THINNING KERNEL in timpul extragerii muchiilor tranzitorii.

Se poate face o verificare daca muchii nedorite ale obiectelor raman in setul pixelilor tranzitorii. Aproape in toate cazurile acestea pot fi inlaturate folosing abordarea MULTIREZOLUTIE. Daca se reduce dimensiunea imaginii, vor ramane muchiile obiectului in timp ce pixelii care reprezinta zgomot vor disparea. De fapt, desi la ambele rezolutii pixelii aleatori apar din cauzele mentionate mai sus, ei nu corespund IN THE RESPECTIVE EDGE MAP asa cum corespund pixelii tranzitorii, pentru ca aparitia acestora din urma nu depinde de cauze sistematice.

Practic schema de multirezolutie se construieste in felul urmator: dimensiunea perechii fiecarui frame ce intra la procesare se micsoreaza (downsampling by 2). Apoi se trece prin toti pasii algoritmului pana se obtin gruparile de puncte cu exceptia pasului in care se face estimarea miscarea background-ului. Dupa ce se extrag muchiile tranzitorii atat ale frame-ului original cat si ale perechii downsampled, hartii muchiilor frameului downsampled i se modifica iar dimensiunea (upsampling) si este comparata cu harta muchiilor imaginii originale. Intrucat muchiile neproeminente apar ca zgomot in ambele frame-uri, in arta combinata vor ramane numai muchiile tranzitorii. Astfel este imbunatatita cu mult performanta schemei de grupare.

Metoda cu multirezolutie poate fi aplicata pe o gama larga a rezolutiilor imaginilor, fara a impune un cost computational ridicat.

Figurile de la 3 la 4 contin 9 imagini. Pe prima linie din fiecare figura sunt prezentate perechile compensate a 3 frame-uri. Pe a 2-a linie apar hartile muchiilor frame-urilor din prima linie. Exceptie face Figura 3 unde pe linia a 2-a este afisat background-ul updatat. Pe a 3-a linie sunt afisate muchiile tranzitorii impreuna cu polinomul de incadrare.

In Figura 3 se prezinta detectia unui corp. In acest caz algoritmul s-a dovedit a fi robust in ciuda conditiilor variabile de iluminare intalnite in timpul filmarii prin schimbarea sursei luminoase.

Figura3 Detectia unui obiect mobil realizata de o camera statica intr-o incapere.

In figurile 4 si 5 sunt prezentate rezultatele obtinute pentru o secventa filmata afara cu o camera video de mana (ce este rotita usor si vibreaza). Princilapa sursa de eroare este prezenta semnificativa a zgomotului.

Figura 4 Detectia unui obiect mobil realizata de o camera de mana.

Figura 5 Detectia unui obiect mobil realizata de o camera de mana.

Figura 6 ilustreaza cazul in care in cadru sunt prezenate mai multe obiecte mobile (delfini). Aici algoritmul de grupare localizeaza cu succes cei 3 delfini, cunoscand referinta si vectorii de miscare ai muchiilor tranzitorii.

Figura 6 Detectia a 3 obiecte mobile intr-o secventa preluata din programul TV.

Figura 7 prezinta o extensie a algoritmului propus: dandu-se 2 frame-uri (aproximative) succesive si poligoanele de incadrare ale obiectelor principale aflate in cadru, se extrag contururile obiectelor.

Figura 7 Estimarea conturului unor obiecte mobile: a) miscarea aleatoare a unei cani de cafea, b) miscarea capului unei femei C) un delfin intr-o secventa dintr-un film d) scena din trafic

2.2 Sistem de localizare a unui obiect folosind mai multi senzori [S. Spors, R. Rabenstein and N. Strobel, Telecommunications Laboratory, University of Erlangen-Nuremberg, Cauerstrasse 7, 91058 Erlangen, Germany, E-mail: {spors, rabe, strobel}@LNT.de].

In aceasta lucrare este prezentat un sistem de localizare si urmarire ce integreaza mai multi senzori. Aici localizarea obiectelor se face prin fuzionarea datelor de la mai multe sisteme locale de senzori folosind un filtru Kalman descentralizat. Se evalueaza un sistem de urmarire cu difuzor audiovizual, sistem ce consta dintr-un sistem de urmarire a fetei si un MICROPHONE ARRAY. O analiza cantitativa arata ca acest sistem de urmarire are rezultate mult mai accurate si mai robuste decat oricare din cele 2 modalitati de urmarire luate separate.

In prezent exista diversi algoritmi ce folosesc MICROPHONE ARRAY, camere video, senzori de proximitate, fiecare dintre acesti senzori avand si puncte slabe si puncte tari. Este deci mult mai avantajos sa se combine aceste modalitati, pentru a obtine estimari ale pozitiilor mult mai robuste. In aceasta lucrare este prezentat un framework pentru localizare bazat pe fuzionarea estimatiilor starilor primite de la sisteme descentralizate folosind un filtru Kalman.

2.2.1 Localizarea obiectelor bazata pe datele prelevate de la mai multi senzori

Urmarirea obiectelor si fuziunea datelor pot fi privinte din perspectiva estimarii parametrice. In cadrul acestei aplicatii vor fuziona date ce reprezinta estimarile pozitiilor, estimari generate de algoritmii de localizare ce utilizeaza date primite de la un singur tip de senzor. In general algoritmii de localizare intorc masuratori afectate de zgomot yi[k] datorita THE RAW SENSOR DATA OF THE LOCAL SENSORS. In cazul nostru starea sistemului x[k] este formata din pozitia obiectului si inca alte cateva variabile de stare. Integrand estimarea parametrica in procesul de fuziune al datelor se creeaza un algoritm de localizare multimodal ce are la baza un filtru Kalman.

Estimarea starii sistemului monomodal

In situatiile in care dinamica sistemului poate fi descrisa printr-un model de stare, algoritmul bazat pe filtrul Kalman ofera o solutie de estimare a starii sistemului satisfacatoare din punct de vedere computational. Filtrul Kalman poate fi caracterizat ca un PREDICTOR BAZAT PE MODEL (MODEL-BASED PREDICTOR) urmat de un (inseriat cu un) corector (compensator, regulator) dependent de observatiile facute ( compensator…zic eu). Filtrul Kalman linear discret este caracterizat de urmatorul model de stare liniar,

unde xi reprezinta starea sistemului iar u[k] reprezinta intrarea in proces. Variabilele aleatoare vi si ni reprezinta zgomotul la iesirea din proces si cel de masurare. Aceste variabile se presupune ca sunt independente si una fata de celalata si fata de starea sistemului. In plus, se mai presupune ca distributia de probabilitate normala e de medie zero, iar matricele de covarianta sunt si. Intrarea filtrului Kalman discret reprezinta estimarea pozitiei celui de-al i-lea senzor obtinut din vectorul de masura yi[k], unde Ci[k] reprezinta matricea de observabilitate. Trebuie tinut cont de faptul ca s-a presupus ca nodurile retelei de senzori (1a) si canalele de comunicatie (1b) au acelasi model de stare, desi acestea pot diferi. Algoritmul de implementare a filtrului Kalman depinde de urmatorul set de ecuatii:

(gasibile in [3, 12])

Estimarea starii multimodale

In sectiunea precedenta s-a vorbit despre filtrul Kalman in situatia unei localizari monomodale. Estimarile pozitiilor calculate de filtrele Kalman locale corespondente fiecarui sistem de senzori se bazeaza doar pe observatiile/masuratorile sezorilor din respectivul sistem. Toate aceste estimatii se combina si se obtine o estimare globala a pozitiilor, mult mai robusta.

Estimatiile locale ale pozitiilor calculate de catre filtrele Kalman pentru fiecare sistem de senzori bazate pe observatiile facute. Apoi se combina aceste estimatii pentru a obtine o estimatie globala mult mai robusta. Pentru inceput fuziunea senzoriala se poate face prin maparea tuturor vectorilor obtinuti in urma masuratorilor locale intr-un vector global de masurare:

si prin folosirea filtrului Kalman pentru a estima starea sistemului. Aceasta metoda face fuziunea masuratorilor si are anumite avantaje fata de fuziunea vectorilor de stare prezentata in [4]. Singurul dezavantaj il constituie structura centralizata prin folosirea unui filtru Kalman centralizat pentru estimarea starii multimodale. Totusi o structura descentralizata a sistemului de urmarire este mai utila in aplicatii practice. In aceasta sectiune este prezentata modalitatea de a ajunge la aceasta estimatie a pozitiei folosind un filtru Kalman descentralizat (implementarea descentralizata a unui filtru Kalman standard [5,16,17].)

Modelul ……(Single State Model)

Filtrul Kalman descentralizat (Descentraliized Kalman Filter – DKF) este un filtru Kalman multi-senzor ce a fost divizat in mai multe module asociate sistemelor locale de senzori. Fiecare nod calculeaza o estimare a posteriori a pozitiei obiectului bazata pe masurarea pozitieide catre senzorul i. Aceste estimatii partiale sunt in final asimilate pentru a genera estimatia a posteriori globala obtinuta in centrul de fuziune.

Figura 8: Structura unui algoritm multimodal de localizare folosing un filtru kalman descentralizat. Se realizeaza fuziunea a 2 tipuri de date: rezultatele localizarii bazate pe achizitionarea de date de tip audio si rezultatele localizarii bazate pe achizitionarea de date de tip video. Starile estimate de catre filtrul Kalman local sunt supuse fuziunii in cantrul de fuziune obtinandu-se astfel estimatul global al starii .

In figura 8 este prezentata structura unui filtru Kalman descentralizat. The time-update equations and measurement-update equations of a DKF with M sensors can, e.g. be found in [3]. In cazul in care componenteve zgomotului de masura sunt independente atunci se poate face decentralizarea estimarii starii. Se presupune ca ecuatia globala a starii este aceeasi pentru toate filtrele Kalman. Atunci se poate descrie ecuatia globala de stare in aceeasi maniera in care se descrie dinamica sistemului local

Estimatul global al starii poate fi scris astfel:

unde si reprezinta covariantele estimate ale erorilor a priori si respectiv a posteriori, in timp ce si sunt componentele lor locale. Vectorul reprezinta estimattul starii a priori, iar si reprezinta estimatele locale ale starilor a priori si respectiv a posteriori.

Matricea globala a posteriori de covarianta a erorii se poate scrie:

Ecuatiile (4) si (5) dau algoritmul pentru implementarea filtrului Kalman descentralizat. Nu este nevoie comunicare intre centrul de fuziune si filtrele Kalman locale. Centrul de fuziune trebuie doar sa acceseze estimatiile de stare a priori si a posteriori ale filtrelor Kalman si matricele corespunzatoare de covarianta a erorii si . De asemenea, metodei de fuziune i se pot adauga date de siguranta (RELIABILITY DATA) generate de algoritmii locali de localizare. Acest lucru poate fi realizat prin folosirea matricei de covarianta a erorii de masurare ale carei valori pot fi ajustate in functie de starea sistemului de localizare. Daca spre exemplu sistemul de localizare a „pierdut” obiectul de interes la momentul curent, se vor alege valori mari pentru elementele de pe diagonala matricei de covarianta a erorii de masurare corespunzand respectivului senzor ceea ce inseamna ca centrul de fuziune nu v-a lua in considerare aceste masuratori.

Teoretic nu este vorba de o performanta mai mica a sistemului descentralizat fata ce cel ce foloseste un filtru Kalman centralizat – aduce aceleasi rezultate. Avantajele folosirii unui filtru Kalman descentralizat constau un conceptul modular, permitand adaugarea de senzori sistemului pe parcurs, si usurinta in implementarea paralela.

Modele …….. (Multiple State Models)

In situatiile in care obiectele excuta miscari complexe folosinfmai multe tipuri de msicari este dificil a construi un singur model de stare care sa poate fi folosit pentru orice tip de miscare se folosesc estimatori interactivi pentru modele multiple (INTERACTIG MULTIPLE MODEL ESTIMATORS). Presupunand ca se pot obtine modele de stare potrivite diferitor parti din traiectoria obiectului in miscare, se poate folosi in filtru Kalman adaptiv ce va invata din datele masurate care dintre aceste modele este potrivit a fi folosit la momentul respectiv.

Estimarea starii neliniare (Nonlinear State Estimation)

Pana acum s-a presupus ca dinamica sistemului si canalul de comunicatoe pot fi descrise printr-un model se stare liniar. Insa in unele cazuri este necesar a se folosi un model de stare neliniar. Spre exemplu se foloseste o ecuatie neliniara de masurare cand trebuie fuzionate date reprezentand estimatii ale pozitiilor ce au fost calculate in sisteme de coordonate diferite sau in cazul in care sistemele locale de senzori au offset-uri si orientari diferite fata de sistemul de coordonate global. Modelul de stare al unui sistem neliniar este dat de :

unde si reprezinta relatii neliniare cunoscute ce depind in general de indexul de timp k. Urmarind aceeasi modalitate de constructie a filtrului Kalman liniar descentralizat, se presupune ca ecuatiile neliniare sunt identice pentru fiecare subsistem. Totusi modelele de masurare ale retelei distribuite de senzori nu trebuie sa fie identice, caz in care se obtine:

unde componentele zgomotului de masurare sunt presupuse a fi independente. In cazul ideal estimarea marimii de stare obtinuta dupa fuzionarea tuturor estimatiilor neliniare este identica cu estimarea starii sistemului centralizat. Din cauza ecuatiilor neliniare este dificil de obtinut o solutie generala pentru aceasta problema.

Totusi o solutie este folosirea unui filtru Kalman extins (Extended Kalman Filter EKF) pentru a realiza estimarea starii neliniare intr-o maniera centralizata. Acest tip de filtru Kalman realizeaza liniarizarea neliniaritatilor ecuatiei de stare (6). In acest scop se foloseste o varianta a ecuatiei neliniare de stare:

unde A[k] si C[k] reprezinta matricele Jacobian ale derivatelor partiale ale si .

In cazurile in care dinamica sistemului poate fi descrisa printr-un model de stare liniar (1a) si o ecuatie de masurare neliniara (6b), fitrul Kalman extins poate fi combinat cu un filtru Kalman descentralizat. DKF prezentat in Figura 1 contine componente autonome ceea ce face posibila inlocuirea filtrelor Kalmen locale, initiale cu filtre Kalman extinse, atunci cand e necesar.

…….Derivarea (STRAIGHTFORWARD DERIVATION) filtrului Kalman extins induce probleme legate de stabilitatea numerica a sistemului in timpul implementarii. For practical implementation the unscented Kalman filter (UKF) [18, 8] provides a solution to overcome these problems.

Implementarea unui sistem de de localizare audio-vizuala

In continuare este prezentata implementarea unui sistem audio-vizual. Sunt mai multe posibilitati de a implementa estimatorul de stare descentralizat, posibilitati ce depind de obiectele urmarite, de tipurile de senzori disponibile si de cerintele (REQUIREMENTS) pentru localizare si urmarire. In continuare este prezentat un sistem destinat urmaririi unei singure persoane dintr-un anumit mediu. Sistemul consta dintr-un MICROPHONE ARRAY pentru a realiza localizarea audio si o camera video pentru urmarirea fetelor. Masuratorile preluate de la ambele tipuri de senzori sunt combinate folosing metoda recursiva prezentata anterior. In continuare se discuta numai cazul localizarii 2D a unui obiect.

Localizarea audio

In general matricele de sunet sunt folosite pentru localizarea audio. Strategiile de localizare audio existente pot fi impartite in 3 clase:

• maximizarea puterii de iesire a unui steered beamformer (beamformer de conducere..)

• estimarea intarzierilor la timpul de ….(time delays of arrival) intre microfoane confiderand un anumit wavefront

• concepte …………high-resolution spectral estimation concepts

Se investigheaza 2 algoritmi diferiti cu privire la localizarea unei surese audio. Primul algoritm este bazat pe estimarea adaptive a respunsurilor unei camere la impulsuri intre sursa si microfoane. Calculand intarzierea pe calea directa intre microfoane se poate obtine timpul de transmisie (time delay of arrival). Cel de-al doilea algoritm utilizeaza in mod eficient implementarea unui filtru de conducere (steered filter…?) si insumeaza un BEAMFORMER (BEAMFORMING = tehnica ce procesare de semnal folosita la matrice de senzori (retele de senzori) pentru a transmite/receptiona selmnalul intr-o/dintr-o directie) pentru a evalua iesirea beamformerului asociata fiecarei presupuse estimatii a pozitiilor. Pozitia sursei semnalului audio este gasita prim maximizarea puterii de la iesirea STEERED BEAMFORMER. Pentru a reduce estimatiile eronate atunci cand nu exista semnal audio, pentru ambii algoritmi este implementat un detector de lipsa de semnal audio.

Algoritmii de localizare audio dau estimatii ale unghiului θ[k] (azimut coordonate polare) si razei r[k]. Datorita relatiilor neliniare intre valorile masurate pentru θ[k] si r[k] componentele vectorului de stare x[k].

Trebuie folosit filtrul Kalman extins pentru estimarea locala a starii. In acest caz matricea Jacobienilor C[k] are urmatoarea forma:

Localizarea video

Sistemul de localizare video efectueaza urmarirea un timp real a urmatoarelor elemente: raport fundal-imagine prim-plan (foreground – background segmentation), detectia regiunilor de culoarea pielii, detectia regiunilor ce au forma ochilor.

Raportul prim plan-fundal este obtinut prin compararea frame-ului curent cu o imagine a fundalului ce a fost retinuta la momentul inceperii urmaririi. Segmentarea in functie de culoarea pielii este obtinuta din pixelii detectati din prim plan. In acest scop se foloseste un model statistic al culorii pielii. Pe baza rezultatelor obtinute din detectia culorii pielii se foloseste un algoritm robust bazat pe statistica (robust statistic based algorithm) pentru a estima centrul si dimensiunea fetei din frame-ul curent. Pentru a depasi ambiguitatile legate de culoarea pielii se mai cauta si forma ochilor in zona in care s-a detectat fata. Acest lucru este realizat folosind un algoritm de detectie a ochilor unde caracteristicile sunt invatate in prealabil dintr-un set de imagini.

Centrul de fuziune

Centrul de fuziune combina estimatiile locale ale starii preluate de la filtrele Kalman locale intr-o estimatie globala bazat pe algoritmul prezentat anterior. Pentru a face urmarirea obiectelor folosind un filtru Kalman este nevoie de un model potrivit al miscarii. Intrucat este destul de complicat a descrie manevre complexe miscarea va fi aproximata de un model liniar, iar obiectele se presupune ca se deplaseaza cu viteza constanta.

Implementarea in timp real

Aceasta sectiune adreseaza problemele de timp real legate de algoritmii descrisi. Cerintele legate de costul de calcul ale estimatiei starii si ale algoritmilor descentralizati sunt destul de reduse. Estimatiile starilor trebuie sa fie updatate de fiecare data cand se efectueaza masuratori noi de catre algoritmul de localizare. Atunci estimatia globala a pozitiei este calculata in centrul de fuziune de fiecare data cand se primesc estimatii locale ale starii. Totusi, intregul sistem trebuie sa fie sincronizat corespunzator. La filtrul Kalman prezentat se face presupunerea ca subsistemele locale de localizare sunt sincronizare din punct de vedere temporal. Aceasta constrangere poate fi depasita daca se foloseste o formulare asincrona a filtrului Kalman descentralizat.

Analiza cantitativa

Urmarirea unei persoane ce vorbeste intr-un mediu dotat cu camere video si sensori audio este o aplicatie interesanta insa nu inlesneste analiza cantitativa intrucat pozitia vorbitorului nu poate fi determinata cu precizie. Pentru a demonstra robustetea si acuratetea urmaririi folosind atat mijloace video cat si audio, se va efectua urmarirea modelului unei cai ferate de forma ovala.

Figura 9: Vedere asupra machetei de cale ferata

Figura 10: Rezultatele experimentelor asupra machetei

Linia intrerupta reprezinta calea ferata. Secventa estimatiilor pozitiilor obtinute din beamformer este indicata cu (+) si reprezinta intrarea in filtrul Kalman local KF1. Iesirea estimata de catre filtul Kalman este indicata cu o linie continua. Intrucat procesul de estimare a inceput in partea de jos a caii ferate se poate observa eroarea ce apare la

Intrucat procesul de estimare a starii a inceput in partea de jos a machetei, este vizibila eroarea initiala ce apare dupa primii pasi ai algoritmului ce implementeaza filtrul Kalman. In plus,

Furthermore, there are two instances in the sequence of position estimates where the raw position estimates (observations) were dropped to mimic a silent acoustic source. In both cases, the Kalman filter extrapolated the position estimates based on the linear motion model of the local Kalman filter. When new input data became available, the position estimates resumed their proper course. The situation is similar for video localization shown in the lower plot of Figure 4(a). Since the camera usually has a much higher spatial resolution than the microphone array, the video position estimates are significantly more accurate in general. Again, two instances with missing video observations were simulated. As in the case of the audio localizer, the associated video position estimates were linearly extrapolated since the associated video Kalman filter, KF2, uses the same motion model as the audio Kalman filter, KF1. The fusion result is shown in the upper plot of Figure 4(b). It may be seen that the joint estimation algorithm successfully removes deviations due to unreliable audio or video observations. Finally, the lower plot in Figure 4(b) shows how the audio, video, and joint audio-video position estimates differ from the true object positions. The absolute position errors of the audio and video position estimates peak at the startup of the audio estimator and when there are failures related to missing mono-modal sensor observations.

Since these deviations do not coincide in time, the joint estimate relies on the more accurate single localizer estimate in these cases. This example shows that joint audio-video object localization provides more robust results than either of the two mono-modal methods employed independently.

Discussion and Conclusions

This paper presented a localization and tracking system integrating multiple sensor systems. The decentralized Kalman filter recursively combines local audio and video state estimates into a more reliable global state and, thus, position estimate. To this end, a common model of the system dynamics and a common coordinate system is needed. Although audio position estimates are often less accurate than the results obtained with a video localizer, they can still provide useful input for a joint audiovideo object localization system. Nevertheless, by introducing a joint audio-video processor, a localizer that yields more reliable results than either one of the single-sensor systems is obtained.

The principles of multimodal object tracking are not limited to the use of decentralized Kalman filters. More advanced state estimation techniques like the CONDENSATION algorithm [6] were also proposed for state estimation in our context. These algorithms overcome the limitations of the Kalman filter, mainly the assumption of a unimodal density to model the system state. Due to our observations, the decentralized adaptive Kalman filter does not seem to limit the performance of our multimodal tracking algorithm. The underlying assumptions were shown to be valid in our scenarios.

2.2.5 Bibliografie:

[1] J. Benesty. Adaptive eigenvalue decomposition algorithm for passive acoustic source localization. Journal of the Acoustical Society of America, 107(1):384–391, 2000.

[2] M. Brandstein and D. Ward, editors. Microphone Arrays. Springer, 2001.

[3] Robert Grover Brown and Patrick Y.C. Hwang. Introduction to random signals and applied Kalman filtering. Wiley, 1997.

[4] Q. Gan and C.J. Harris. Comparison of two measurement fusion methods for Kalman-filter-based multisensor data fusion. IEEE Transactions on Aerospace and Electronic Systems, 37(1):273–280, Jan 2001.

[5] H. R. Hashemipour, S. Roy, and A. J. Laub. Decentralized structures for parallel Kalman filtering. IEEE Transactions on Automatic Control, 33(1):88–93, 1988.

[6] M. Isard and A. Blake. Condensation – conditional density propagation for visual tracking. International Journal of Computer Vision, 29(2):5–28, 1998.

[7] M. J. Jones and J. M. Rehg. Statistical color models with application to skin detection. In IEEE Conference on Computer Vision and Pattern Recognition, volume 1, pages 274– 280, 1998.

[8] S.J. Julier and J.K. Uhlmann. A new extension of the Kalman filter to nonlinear systems. In Proceedings of AeroSense: The 11th International Symposium on Aerospace/Defense Sensing, Simulation and Controls, Orlando, Florida.

[9] M. Kirby and L. Sirovich. Application of the Karhuenen – Lo`eve procedure for the characterization of human faces. In IEEE Transactions on Pattern analysis and Machine intelligence, volume 12, pages 103–108, 1990.

[10] E. Mazor, A. Averbuch, Y. Bar-Shalom, and J. Dayan. Interacting multiple model methods in target tracking: A survey. IEEE Transactions on Aerospace and Electronic Systems, 34(1):103–123, Jan 1998.

[11] B. S. Rao, H. F. Durrant-Whyte, and J. A. Sheen. A fully decentralized multi-sensor system for tracking and surveillance. International Journal of Robotics Research, 12(1):20–44, 1993.

[12] L. L. Scharf. Statistical Signal Processing – Detection, Estimation, and Time Series Analysis. Addison-Wesley, 1991.

[13] S.Spors and R.Rabenstein. A real-time face tracker for color video. In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), USA, Salt Lake City, May 2001.

[14] N. Strobel, T. Meier, and R. Rabenstein. Speaker localization using steered filteredand-sum beamformers. In B. Girod, H. Niemann, and H.-P. Seidel, editors, Proceedings Vision, Modeling, and Visualization ’99, pages 195–202, Erlangen, 1999.

[15] N. Strobel and R. Rabenstein. Robust speaker localization using a microphone array. In Proceedings of the X European Signal Processing Conference, volume III, pages 1409–1412. EURASIP, 2000.

[16] N. Strobel, S. Spors, and R. Rabenstein. Joint audio-video signal processing for object localization and tracking. In M. Brandstein and D. Ward, editors, Microphone Arrays, chapter 10, pages 203–225. Spinger, 2001.

[17] N. Strobel, S. Spors, and R. Rabenstein. Joint audio-video object localization and tracking. IEEE Signal Processing Magazine, 18(1):22– 31, Jan 2001.

[18] Eric A. Wan and Rudolph van der Merwe. The unscented Kalman filter for nonlinear estimation. In Proceedings of Symposium 2000 on Adaptive Systems for Signal Processing, Communication and Control (AS-SPCC), Lake Louise, Alberta, Canada, Oct. 2000.

2.3 Imbunatatirea auto-localizarii de catre roboti folosind fuziunea senzoriala

Localizarea (procesul prin care un robot isi estimeaza pozitia din date preluate de la senzori) reprezinta o problema fundamentala in cadrul roboticii.

In prezent robotii mobili sunt implicati in activitati ce necesita mai multa acuratete, sau sunt dificil de realizat sau pot fi periculoase omului. In majoritatea situatiilor acesti roboti necesita ajutorul unor agenti pentru a duce la bun sfarsit taskurile asignate. Alternativa la folosirea unui singur robot pentru realizatea unei activitati complexe este folosirea unui grup de roboti, fiecaruia dandu-i-se spre realizare o parte din task. Procesul de localizare prin care robotii isi determina pozitia folosind si informatii primite de la alti roboti se numeste localizare cooperativa. Acest tip de localizare este folosit mai ales in situatiile in care unul dintre robotii dintr-o echipa nu poate vedea un obiect sau este echipat cu sezori de calitate scazuta.

Problema localizarii poate fi impartita in 3 subprobleme:

localizare globala

localizare relativa

„robot kidnapping”

Localizarea globala

In comparatie cu localizarea relativa, cea globala este mai greu de realizat, intrucat se presupune ca robotul nu dispune de informatii despre pozitia sa initiala si incearca sa estimeze pozitia in care se afla relativ la un cadru extern global. In marea majoritate a cazurilor incercarile de localizare a robotului se soldeaza cu esecuri sau rezultatele nu sunt destul de precise. In plus aceasta metoda necesita un mare efort de calcul si memorie suplimentara comparativ cu localizarea relativa.

Localizarea relativa

Localizarea relativa presupune faptul ca robotul isi cunoaste pozitia actuala in comparatie cu alt obiect si isi updateaza pozitia.

Robot kidnapping

Problema „robot kidnapping” presupune estimarea de catre un robot a noii sale pozitii dupa ce a fost „ametit”. Aceasta problema este asemanatoare localizarii globale, dar mai dificila intrucat robotul trebuie sa realizaze faptul ca pozitia i-a fost schimbata. Acesta constituie un milestone intrucat mai intai robotul trebuie sa-si dea seama ca a fost mutat si apoi sa isi estimeze noua pozitie.

2.3.4 Localizarea Markov

Localizarea Markov este un cadru de lucru probabilistic capabil sa coopereze cu localizarea globala si poate fi adaptata localizarii cooperative.

In cadrul localizarii Markov functia densitate de probabilitate se metine constanta in toate zonele in care exista posibilitatea sa se gaseasa robotul respectiv. Nu se presupune vreo anumita forma asupra acestie functii, asa cum se face la alte metode, de exemplu cea bazata pe filtrul Kalman in care se presupune ca functia este functia de densitate probabilistica gaussiana.

Folosind algoritmul de localizare Markov pentru un singur robot se poate dezvolta un algoritm de localizare Multi-Robot ce presupune localizarea cooperativa a propriei pozitii a unui robot si a determinarii locatiei unor obiecte bazata pe propagarea perspectivelor de estimare a locatiei intr-o echipa de roboti, lucru ce poate fi vazut ca o extensie a algoritmului de Localizare Markov.

Un singur robot poate avea propria estimatie asupra locatiei sale curente sau a unui alt obiect, dar o echipa de roboti este capabila sa rezolve situatii in care unul dintre coechipieri nu poate observa obiectul sau se poate face o estimatie mai buna a pozitiei obiectului prin intermediul comunicarii.

Localizarea Markov

Localizarea Markov este una dintre cele mai bune si mai eficiente abordari in localizarea globala ce a fost aplicata cu succes unei mari varietati de probleme de localizare. Contrar altor algoritmi de localizare cum sunt cei bazati pe filtrarea Kalman, aceasta metoda nu face nici o presupunere privind distributiile de incertitudine. In loc sa faca mentina o singura ipoteza cu privire la cea mai buna estimatie a pozitiei unui robot, aceasta abordare pastreaza o densitate de probabilitate peste toate poziitiile si orientarile posibile ale robotilor, lucru numit Incredere (Belief). La inceput, cand nu sunt informatii legate de pozitia initiala, functia desitate de probabilitate (PDF) este o distributie uniforma. In cativa pasi, robotul combina informatiile primite de la senzori si datele odometrice si functia densitate de probabilitate evolueaza catre o functie densitate de probabilitate multimodala. In final , cand robotul determina pozitia lui exacta, functia desitate de probabilitate este transformata intr-o distributie unimodala. Dezavantajul este ca localizarea Markov presupune efort de calcul ridicat si necesita memorie.

2.3.6 Ideea de baza a algoritmului

Presupunand pentru simplitate ca pozitia robotulului este unidimensionala, adica acesta se poate misca numai pe orizontala si ca el este plasat in acest mediu insa nu isi cunoaste pozitia, localizarea Markov reprezinta starea de incertitudine printr-o distributie uniforma asupra tuturor pozitiilor.

Daca robotul primeste date de la senzorii sai cum ca s-ar afla langa o usa, increderea robotului se modifica prin cresterea probabilitatii ca robotul sa fie pozitionat langa o usa si in acelasi timp prin scaderea probabilitatii ca el sa se afle in alte locatii. Acest lucru este figurat in a doua diagrama.

Se poate remarca faptul ca increderera robotului este multi-modala si ca informatiile disponibile sunt insuficiente pentru a realiza o localizare globala si ca zonele ce nu se afla in apropierea unei usi inca poseda probabilitate non-zero. Acest lucru datoreaza faptului ca datele preluate de la senzori sunt afectate de zgomot si simpla detectare a unei usi este insuficienta pentru a exclude posibilitatea de a nu se afla langa o usa.

Presupunand ca robotul se misca se poate observa cum algoritmul shifteaza distributia indrederii corespunzator directiei de deplasare (diagrama 3). Tinand cont si de zgomotul propagat prin miscare, noua incredere este nedeta (si mai putin certa) decat cea anterioara.

Daca robotul mai preia o data date de la senzori si din nou se gaseste langa o usa, aceasta observatie este adaugata increderii anterioare (ce era neuniforma) obtinand increderea finala, prezentata in ultima diagrama. In acest moment robotul stie in mod cert care este locatia sa.

2.3.7 Concepte teoretice

2.3.7.1 Notatia

Se noteaza pozitia (locatia) unui robot mobil printr-o variabila tridimensionala , reprezentand coordonatele Carteziene x si y si directia de deplasare .

reprezinta adevarata locatie a robotului la momentul t, iar reprezinta valiabila aleatoare corespunzatoare.

Robotul nu-si cunoaste pozitia exacta, ci dispune numai de o incredere asupra pozitiei unde s-ar putea afla. Increderea robotului la momentul t se noteaza cu si reprezinta distributia de probabilitate peste spatiun pozitiilor. De exemplu este probabilitatea ca robotul sa creada ca locatia sa la momentul t este l.

Increderea este updatata ca urmare a producerii a doua tipure de evenimente:

Primirea de date de masurare de la senzorii de care dispune robotul (camera video, sonar)

Primirea de date preluate din odometrie.

Se noteaza cu s datele preluate de la senzori, cu a datele provenite din odometrie si cu S, respectiv A variabilele aleatoare corespunzatoare.

Se noteaza cu setul de date primite fie din odometrie, fie de la senzori, unde fiecare , cu reprezinta fie data preluata de la senzori, fie din odometrie. Variabila t indexeaza datele, iar T reprezinta cea mai recenta informatie preluata.

2.3.7.2 Localizare recursiva

Localizarea Markov estimeaza distributia posteriori asupra lui in functie de toate informatiile disponibile. Acest lucru se scrie

Inainte de a avansa in descrierea algoritmului, trebuie prezentat un element cheie in implementarea ulterioara a algoritmului de localizare, si anume ipoteza Markov. Denumita uneori ipoteza unei lumi statice, aceasta releva faptul ca daca se cunoasta locatia robotului , masuratorile ulterioare nu depind de cele trecute (si reciproc):

Aceasta ipoteza ese inutila in situatia in care mediul contine alte obiecte in miscare in afara robotului si care pot oferi date senzorilor.

Calculand se disting doua cazuri, in functie de originea celei mai recente informatii primate de robot

Cea mai recenta informatie provine de la un senzor

unde regula lui Bayes spune ca acest termen poate fi transformat

 care conform ipotezei Markov se poate simplifica in:

In plus numitorul de poate inlocui cu o constanta , intrucat nu depinde de . Rezulta:

Se poate observa natura recursiva a acestei ecuatii. Daca se scrie , ecuatia anterioara devine

In aceasta ecuatie s-a inlocuit  cu intrucat nu depinde de timp.

Cea mai recenta informatie provine din odometrie

Calculand cu Teorema Probabilitatii Totale

Conform ipotezei Markov

Si cel de-al doilea termen poate fi simplificat intrucat nu detine informatii legate de pozitia :

Inlocuind in ecuatia oferita de Teorema Probabilitatii Totale, se obtine:

Si aici se poate observa forma recursiva a ecuatiei. Rezulta:

S-a folosit in locul intrucat se presupune ca este invariant in timp.

Algoritmul de localizare

Se considera ca reprezinta modelul miscarii intrucat modeleaza efectul miscarii asupra pozitiei robotului, iar este numit modelul perceptual intrucat modeleaza informatiile preluate de robot de la senzori.

In cadrul algoritmului Markov ce initializeaza increderea reprezinta informatia cunoscuta apriori despre pozitia robotului. Aceasta distributie poate fi aleasa arbitrar insa in practica doua cazuri sunt predominante:

Daca pozitia robotului ii este total necunoscuta se doloseste distributia uniforma

Daca pozitia initiala a robotului este aproximativ cunoscuta ce foloseste distributia Gaussiana centrata pe pozitia robotului.

2.3.7.4 Implementarea algoritmului Markov

Se poate observa ca nu s-a facut nici o specificatie despre modul in care sunt determinate probabilitatile si .

Pentru updatarea increderii atunci cand robotul se afla in miscare se foloseste modelul de miscare . Bazandu-ne pe faptul ca erorile ce apar la translatie si rotatie au o disributie normala, se foloseste o combinatie de doua distributii Gaussiene independente si centrate in zero. Varianta acestor distributii este proportionala cu lungimea miscarii masurate.

Probabilitatea ca informatia s citita de senzor sa fie prelevata atunci cand robotul de afla in pozitia l trebuie sa fie calculata pentru toate pozitiile l la fiecare updatare a algoritmului Markov. Aceasta probabilitate se poate calcula considerand distanta pana la cel mai apropiat obstacol detectat se senzor. Fie probabilitatea de a masura distanta daca robotul se afla in pozitia l . Sunt doua cazuri importante:

Obstacolul este cunoscut: daca senzorul detecteaza un obstacol distributia poate fi modelata ca o distributie Gaussiana centrata pe distanta pana la acest obstacol. Fie probabilitatea ca senzorul sa masoare distanta d daca robotul se afla in pozitia l , presupunand ca raza senzorului este reflectata de cel mai apropiat obstacol. Deci distanta pana la acest obstacol este . Probabilitatea este data de o distributie Gaussiana centrata in :

Deviata standard modeleaza incertitudinea distantei masurate.

Obstacolul este necunoscut: in cadrul localizarii Markov s-a presupus ca modelul mediului inconjurator este unul static. In realitate in mediul in care isi desfasoara activitatea robotii isi pot face aparitia obiecte necunoscute lor si astfel unda senzorului poate fi reflectata de un obstacol necunoscut. Presupunand ca acestea au o distributie uniforma, probabilitatea de a detecta un obiect necunoscut la o distanta este independenta de pozitia robotului si deci poate fi modelata printr-o distributie geometrica intrucat distanta este masurata daca senzorul nu este reflectat de vreun obstacol la o distanta si este reflectat la distanta . Deci probabilitatea se poate scrie:

unde este probabilitatea ca senzorul sa fie reflectat de un obstacol necunoscut.

Algoritmul Markov de localizare multi – robot

Localizarea Markov se poate extinde la o localizarea colaborativa in care o echipa de N roboti utilizeaza informatia primita de la coechipieri pentru a imbunatati incertitudinea, atunci cand un robot „observatorul” descopera un alt robot „observatul”. In acest caz datele de la observator trec catre robotul observat, iar acest lucru creste numarul de constrangeri pentru robotul observat de a-si imbunatati perspectiva.

Dezavantaje ale localizarii Markov

Unul din marile dezavantaje ale acestui algoritm este ca presupune calcule numeroase si complicate, deci un efort mare de calcul si necesita memorie. In plus, transmiterea unei cantitati mari de informatie in timp real reprezinta in sine o constrangere.

De exemplu, poate fi destul de costisitor daca o echipa de N roboti are nevoie sa faca schimb de date si pastreaza perspective ale pozitiilor celor N roboti. In acest caz chiar si schimbul de informatii cu un singur robot poate cauza neplaceri.

Un alt dezavantaj al algoritmului de Localizare Markov il constituie faptul ca nu exista o strategie anume pentru a face fuziunea intre datele pe care le primeste un robot. In unele situatii combinarea a mai multor increderi poate fi benefica, in timp ce in altele nu se reuseste sa imbunatateasca increderea intr-o informatie deja detinuta.

De asemenea pentru a putea aplica acest tip de abordare este necesar ca robotii sa fie agenti activi, capabili sa observe alti agenti, sa transmita si sa receptioneze informatii. Totusi, cand se face localizarea unor obiecte, acesti roboti sunt agenti pasivi si nu sunt capabili sa masoare distanta parcursa, sa observe propria locatie sau sa comunice cu agentul observator.

Algoritm de localizare cu distributia echipelor

Acest algoritm imbunatateste probabilitatea determinarii de catre un robot a propriei locatii, dar si a localizarii unui obiect de catre un robot. Dar mai intai se vor defini unele concepte.

Masurarea incertitudinii

Entropia este o masura pentru cantitatea de informatie trimisa referitor la un element al mesajului transmis (masura a incertitudinii). Introdusa mai intai de Boltzmann in contextul Termodinamicii, a fost folosita si in alte domenii, cum sunt Fizica Cuantica si Teoria Informatiei. Shannon a fost cel care a definit entropia in Teoria Informatiei ca:

unde pi este probabilitatea ca variabila aleatoare L sa ia valoarea li. Entropia este un numar pozitiv: . Cand H = 0 suntem pe deplin singuri ca ceea ce s-a receptionat este ceea ce s-a transmis. Pe masura ce H creste, plauzabilitatea informatiei detinute / primite scade.

In cazul localizarii probabilistice, ne confruntam cu problema incertitudinii, lucru masurat prin intermediul entropiei. Presupunand ca doi roboti n si m observa un obiect Obj, increderea este definita ca perceptia robotului n asupra locatiei obiectului Obj. Entropia obiectului Obj asupra lui insusi poate fi definita ca:

Acum primul robot primeste informatii despre locatia obiectului de la cel de-al doilea robot. Robotul n, pentru a-si imbunatati increderea asupra localitiei lui Obj, preia informatia de la robotul m si:

Putem astfel defini entropia cooperativa:

Entropia increderii Bel poate fi considerata cantitatea de incertitutine continuta in Bel. Incertitudinea poate fi redusa prin imbinarea mai multor observatii. Asfel, entropia este folosita pentru a conditiona fuziunea increderilolr pe criteriul ca doua entropii ale unor increderi sunt combinate daca entropia observatiilor combinate descreste.

Comunicatia

Datorita restrictiilor de comunicatie si a altor limitari fizice, un robot nu poate face schimb de informatii cu toti robotii din echipa. In plus ar fi foarte costisitor din punctual de vedere al efortului de calcul daca fiecare robot ar vrea sa foloseasca observatiile tuturor celorlalti roboti. De aceea s-a definit raza optimala r in interiorul careia este utila fuziunea informatiilor. Evident, valoarea maxima a lui r este limitata de raza de actiune a dispozitivelor de comunicatie.

Sub-echipa

Desi o cooperare deplina intre toti robotii unei echipe ar imbunatati esential estimarea locatiei obiectelor, necesita un efort substantial de calcul si cateodata este imposibil de realizat din punct de vedere tehnic. Din aceasta cauza echipa de roboti se imparte in doua subechipe. In fiecare subechipa, membrii echipei sunt in contact si fac schimb de informatii. In plus subechipele pot avea membri comuni. In Fig.1 se arata cum membrii unei echipe sunt impartiti in doua subechipe, ce pot comunica prin intermediul unui membru comun.

Figura 10

Fuziunea informatiilor intr-o subechipa

Presupunand ca observatiile efectuate de fiecare echipa sunt independente, se poate solosi urmatoarea ecuatie pentru a combina informatia intr-o subechipa de K roboti:

unde di este observatia celui de-al i-lea robot.

Fluxul informatiei intr-o subechipa

In cazul localizarii mutuale fluxul informational este bidirectional asa cum se arata in Figura 11. Pentru localizarea unui obiect, directia fluxului informational depinde de pozitia relativa a respectivului membru de echipa. Informatia este trimisa din aproape in aproape, un membru trimitand informatia celui mai apropiat sub-coechipier si de aici catre restul membrilor. Un exemplu de flux informational este prezentat in Figura 10. Sub-echipele pot face schimb de informatii bidirectional si, in cazul localizarii unui obiect, directia de propagare a informatiei este de la cel mai apropiat membru catre cel mai indepartat (a se vedea in Figura 12).

Figura11

Figura 12

Fuziunea informatiilor intre doi membri ai unei subechipe

Presupunem ca robotul m il observa pe robotul n. Plecand de la acest lucru, robotul observat n isi poate imbunatati localizarea prin:

(***)

unde este distanta dintre cei doi roboti la momentul t de timp. In cazul localizarii unui obiect, unde obiectul Obj este observat de robotul n :

si se calculeaza conform relatiei anterioare (***).

Localizarea cooperativa

Localizarea unui obiect de catre o echipa de roboti implica diferite ….incercari. Sunt multe situatiile in care datorita unor restrictii cum sunt raza de actiune a senzorilor sau obstacolele fizice robotii nu-si pot observa coechipierii sau alte obiecte. Un alt motiv pentru a folosi localizarea colaborativa este acela ca poate imbunatati acuratetea localizarii. Pentru a realiza acest lucru s-a folosit algoritmul de Localizare Markov la care s-au facut anumite modificari pentru a evita dezvantajele acestuia.

Algoritmul poate fi impartit in 4 pasi:

1 – impartirea pe subechipe (Sub-team registration)

2 – auto localizarea

3 – localizarea unui obiect

4 – comunicarea intre subechipe

Se imparte echipa in doua subechipe presupunand ca membrii echipei sunt distincti. La inceput robotii vor incerca sa se alature unei subechipe, dimensiunea fiecarei subechipe depinzand de limitarile de comunicatie, de numarul de observatii ce trebuie fuzionate. Dupa ce s-au incadrat intr-o subechipa, robotii trebuie sa isi determine locatiile folosing algoritmul de Localizare Markov. Apoi trimit perceptiile / observatiile unui monitor de subechipa, astfel incat toti membri au acces la observatiile celorlalti membri. Fuziunea datelor observate are sens numai atunci cand cele doua observatii se potrivesc, iar pentru a verifica acest lucru se foloseste entropia. Un robot va fuziona informatia pe care o detine cu a altui robot daca entropia rezultatului scade dupa fuziune. Presupunand ca robotul m observa robotul n, el va trimite informatia despre n catre monitor. Robotul n foloseste ecuatia (3) si ii certifica lui m persectiva propriei pozitii. Robotul n foloseste acea informatie daca urmatoarea conditie este satisfacuta:

Ecuatia (2) este folosita pentru a fuziona informatiile, iar mai apoi robotii isi formeaza perspective relative la obiectele din jur folosindu-se de diferiti sensori pentru a aduna date din mediu si apoi folosesc algoritmul de localizare Markov. Urmatorul pas este de a trimite din nou informatii monitorului. Fiecare robot foloseste ecuatia (4) pentru a afla observatii de la coechipieri despre obiectele din campurile vizuale ale acestora. Conditia de fuziune este aceeasi ca si la auto-localizare insa este aplicata obiectului Obj si se folosesc de ecuatia (2) pentru a combina observatiile. Subechipele au nevoie sa comunice unele cu altele doar in cazul unor situatii ambigue (unul dintre roboti nu poate vedea un obiect).

Rezultatele simularii

S-a studiat efectul cooperarii atunci cand un robot doreste sa-si imbunatateasca perspectiva observatiilor pentru auto-localizare sau localizarea unui obiect si de asemenea daca, din vreun motiv anume, nu poate localiza respectivul obiect. Mediul a fost impartit in arii egale de forma patrata. Se considera diferite rezolutii de la 50×50 la 200×200. Simularile s-au facut cu zece roboti echipati cu doua tipuri de senzori: senzori vizuali si senzori auditivi. Modelul vederii este stochastic si s-a fixat numai raza campului vizual al senzorilor.

Fig. 13

In Fig. 13 este prezentata variatia incertitudinii senzorului visual data de distanta. Raza de acoperire a vectorului este limitata intre celulele 1 si 13 aflate pe directia senzorului. Cele mai precise observatii sunt preluate intre 6 si 8, atunci cand entropia este minima. Crescand sau micsorand distanta, incertitudinea observatiilor creste. Similar se considera si modelul stocastic al senzorului ce preia datele odometrice. In Fig. 14 se prezinta variatia incertitudinii senzorului.

Fig. 14

In cadrul experimentului s-a studiat mai intai efectul cooperarii in cazul localizarii mutuale si apoi in cazul localizarii unui obiect. La fiecare pas, robotii din fiecare sub-echipa isi updateaza perspectiva folosind mai intai datele primite de la senzori si apoi considerand si datele odometrice. Apoi fac schimb de informatii cu coechipierii, in sensul ca fiecare robot primeste date despre perspectiva fiecarui robot despre el insusi. In cazul acestui experiment, intrucat robotii erau pozitionati aleator pe teren si datorita restrictiilor senzorilor vizuali, doar un singur robot a putut fi observat de unii dintre roboti. Dimensiunea subechipelor a variat intre 2 si 6 membri, in functie de situatie. Inainte de a folosii datele primite de la coechipieri, robotul a filtrat entropiile si le-a ales pe cele optime astfel incat in urma fuziunii entropia finala sa scada.

In cazul localizarii unui obiect, dupa ce isi determina propria pozitie, fiecare dintre robotii ce a observat acel obiect, trimite informatia coechipierilor si astfel se propaga incertitudinea in subechipa si in retea. Folosint aceasta metoda, nu numai ca se micsoreaza entropia in cazul localizarii unui obiect, dar in situatiile in care robotii nu pot vedea respectivele obiecte, ei isi pot forma o perspectiva asupra pozitiei obiectului respectiv prin intermediul vecinilor. In plus efortul de calcul este mult mai mic, la fel si memoria necesara si comunicarea intre coechipieri decat in cazul metodei Markov sau a Localizarii Multi-Robot. In Fig. 15 este prezentat graficul entropiei perspectivei initiale functie de entropia perspectivei obtinute prin cooperare. Pe masura ce numarul de roboti ce coopereaza creste se observa o scadere a entropiei.

Fig.15

In Fig. 16 se poate vedea scaderea entropiei medii in functie de numarul robotilor cooperanti. Pe masura ce numarul de roboti ce coopereaza creste, entropia perspectivei rezultata din fuziunea datelor obtinute prin cooperarea robotilor scade.

Fig. 16

Concluzii

Obiectivul acestei lucrari a fost de a investiga cum influenteaza cooperarea robotilor dintr-o echipa perspectiva fiecarui robot legat de auto-localizare sau de localizarea unui obiect. Prin acest experiment s-a justificat a alegerea acestui algoritm. Incertitudinile senzorilor si cele de odometrie au avut distributii geneate stocastic. S-a aratat ca localizarea cooperativa este utilza si in cazul in care robotii sunt sau nu capabili sa vada obiectul propus.

Bibliografie

[1] D. Foxy, W. Burgardz, H. Kruppayy, S. Thruny, A Probabilistic Approach to Collaborative Multi-Robot Localization, Autonomous Robots, 8(3), 2000.

[2] W. Burgard, D. Fox, D. Hennig, T. Schmidt, Estimating the absolute position of a mobile robot using position probability grids. In Proc. of the National Conference on Artificial Intelligence (AAAI),1996.

[3] W. Burgard, D. Fox, S. Thrun, Active mobile robot localization. In Proc. of the International Joint Conference on Artificial Intelligence (IJCAI),1997.

[4] D. Fox,W. Burgard and S. Thrun, Active Markov localization for mobile robots. Robotics and Autonomous Systems, 25:195-207.

[5] D. Fox,W. Burgard, F. Dellaert, S. Thrun, Monte Carlo localization: Efficient position estimation for mobile robots. In Proc. of the National Conference on Artificial Intelligence (AAAI)1999.

[6] D. Fox,W. Burgard, S. Thrun, Markov localization for mobile robots in dynamic environments. Journal of Artificial Intelligence Research, 11,1999.

[7] D. Fox, W. Burgard, S. Thrun, A.B. Cremers, Position estimation for mobile robots in dynamic environments. In Proc. of the National Conference on Artificial Intelligence (AAAI) 1998.

[8] W. Burgard, A. Derr, D. Fox, A.B. Cremers, Integrating global position estimation and position tracking for mobile robots: The Dynamic Markov Localization approach. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 1998

[9] S. I. Roumeliotis and G. A. Bekey. Collective localization, A distributed kalman filter approach to localization of groups of mobile robots. In IEEE Int. Conf. on Robotics and Automation, pg. 2958-2965, Apr. 2000.

[10] S. Thrun. A probabilistic online mapping algorithm for teams of mobile robots, International Journal of Robotics Research, 20(5):335-363, 2001.

[11] S.Thrun, D. Fox, and W. Burgard, A probabilistic approach to concurrent mapping and localisation for mobile robots. Machine Learning, 31(5):29-55, 1998. Joint issue with Autonomous Robots.

[12] A. Howard, M. J Mataric, G. S. Sukhatme, Localization for Mobile Robot Teams: A Distributed MLE Approach. Experimental Robotics VIII, Bruno Siciliano and Paulo Dario (eds), Springer-Verlag, 2003, pp.146 – 155.

[13] A. Howard, M. Mataric, G. Sukhatme, Putting the ’i’ in team: an ego-centric approach to cooperative localization, in Proceeding of the IEEE Int. Conference on Robotics and Automation, to appear, Taipei, Taiwan, May 2003.

[14] I. M. Rekleitis, G. Dudek, E. E. Milios, Multi-Robot Cooperative Localization: A Study of Trade-offs Between Efficiency and Accuracy. In Proceedings of Intelligent Robots and Systems, pages 2690-2695, Lausanne, Switzerland, September-October 2002.

[15] P. Marcelino, P. Nunes, P. Lima, M.I. Ribeiro, Improving object localization through sensor fusion applied to soccer robots, Proceedings do Encontro Cientfico do 3 Festival Nacional de Robtica, ROBOTICA 2003, Lisboa, 2003.

[16] C.C.F. Penedo, J.P.G.N. Pavo, P.Lima, M.I.Ribeiro,Localization in the Robocup Simulation

League, Robotica, 4 trimestre, pp. 16-21, 2003.

[17] C. C. F. Penedo, J. P. G. N. Pavo, P. Lima, M.I.Ribeiro, Markov Localization in the RoboCup

Simulation League,Proceedings do Encontro Cientfico do 3 Festival Nacional de Robtica, ROBOTICA 2003, Lisboa, 2003

[18] P. Pinheiro, P. Lima,Sensor Fusion for Cooperative Object Localization and World Modeling,Proc. 8th Conference on Intelligent Autonomous Systems, IAS- 8, Amsterdam, The Netherlands, 2004.

[19] H.F. Durrant-Whyte, ”Sensor Models and Multisensor Integration,” Int. J. Robot. Res., vol. 7, no. 6, pp. 97-113, 1988.

[20] S. Martens, G.A. Carpenter, P. Gaudiano,Neural sensor fusion for spatial visualization on a mobile robot. Proceedings of the SPIE International Symposium on Intelligent Systems and Advanced Manufacturing (Boston, 11/98). Technical Report CAS/CNS TR-98- 028, Boston, MA: Boston University.

[21] H.J.C. Pasika, ’Weural Network Sensor Fusion Engines for Remote Sensing”, PhD thesis, McMaster University, 1999.

[22] H. Joseph, Neural Network Sensor Fusion: Creation OF A Virtual Sensor For Cloud-Base Height Estimation PhD thesis, McMaster University, 1999.

[23] A. Mahajan, K. Wang, Multisensor Integration and Fusion Model that Uses a Fuzzy Inference, System and Probir,IEEE/ASME TRANSACTIONS ON MECHATRONICS, VOL. 6, NO. 2, JUNE 2001

[24] S. Shekhar, O. Khatib, M. Shimojo, Object localization with multiple sensors, Int. J. Robot. Res., vol. 7, no. 6, pp. 34-44, Dec. 1988.

[25] A. Stroupe, M.C. Martin, T. Balch, Merging gaussian distributions for object localization in multirobot systems, Proc. of the ISER ’00 Seventh International Symposium on Experimental Robotics, Springer-Verlag.

3. Descrierea aplicatiei

3.1 detectia Miscarii cu SAD

Se dezvolta o aplicatie video in Simulink folosind capacitatile de procesare de semnale in DSP Blockset.

Pentru inceput se examineaza compresia datelor, apoi se face o descriere a modului de a crea si simula algoritmul de detectie pentru aplicatia de supraveghere video folosing Simulink si DEP Blockset. Apoi se discuta acordarea (calibrarea) simularii, generarea automata a codului pentru rularea in timp real. La final de masoara performanta sistemului.

Descrierea algoritmului

Suma diferentelor absolute (Sum of Absolute Differences SAD) este o metoda simpla si des utilizata pentru potrivirea blocurilor de imagini folosite la estimarea miscarii. Aceasta metoda se bazeaza pe determinarea valorii absolute a diferentei intre fiecare pixel din blocul initial si pixelul coresponent din blocul cu care se face comparatia. Aceste diferente sunt insumate petru a masura similaritatile intre cele 2 blocuri (se caluleaza norma L1 a imagini diferenta).

SAD este o metoda foarte rapida intrucat este foarte simpla. Este des utilizata pentru estimarea miscarii, detectia reperelor si are multe implementari hardware intrucat este un algoritm robust. Este cea mai simpla metoda ce ia in considerare fiecare pixel dintr-un bloc ceea ce o face foarte eficienta pentru detectia miscarii. Suporta de asemenea paralelizare intrucat analizeaza fiecare pixel separat.

Pe scurt se analizeaza pozitiile dintr-o secventa de imagini in care o imagine este inlocuita cu o alta cu alt continut vizual.

Se genereaza masura unicitatii locale prin calculul distorsiunii de la imaginea initiala. Pentru fiecare pixel se calculeaza valoarea de corelatie folosind formula

unde template-ul T de dimensiune MxN pixeli este corelat cu imaginea I (avand aceeasi dimensiune) extrasa din imaginea din care se face cautarea.

Compresia Datelor pentru Supraveghere Video

Intrucat sistemele de supraveghere video presupun inregistrarea, arhivarea si refolosirea (review) unor calupuri mari de date apare necesitatea compresiei acestor tipuri de date. Ca exemplu, pana si un sistem digital de supraveghere monocrom cu 8 biti/pixel si rezolutie CIF (352×240 pixeli) functionand la 30 frameuri/secunda va trimite unitatilor de stocare aproximativ 2.4MB/secunda. Exista 2 modalitati principale prin care se poate reduce necesarul de spatiu de stocare a datelor video: salvarea (stocarea) numai a acelor frameuri ce prezinta anumite caracteristici, de exemplu detectia miscarii; sau stocarea unor variante arhivate ale frameurilor. Aici se foloseste ca tehnica, alegerea automata a frameurilor spre stocare intrucat se reduce astfel rata de inregistrare.

Algoritmul de Detectie a Miscarii

Stocarea frameurilor este declansata de detectarea miscarii in campul vizual al camerei video. In Figura 17 este prezentata situatia in care o camera video achizitioneaza date la o frecventa de 30 frameuri/ secunda in conditiile in care subiectul sta nemiscat. In Figura 18 subiectul este in miscare. Toate secventele ce nu contin miscare sunt supuse compresiei, reducand astfel semnificativ frame rate-ul (rata de achizitie…?) . Unul dintre cei mai simpli algoritmi pentru a estima miscarea presupune calculul diferentelor intre secventele succesive. Cu cat diferenta intre secvente este mai mare, cu atat este mai mare posibilitatea ca in repectivul cadru sa fi avut loc schimbari ca urmare a miscarii diferitelor obiecte…etc. Diagrama bloc prezentata in Figura 19 calculeaza suma diferentelor absolute intre secventele succesive si intoarce la iesire o estimare a miscarii produse.

Figura 19: Modelul Simulink infatisand diagrama bloc corespunzatoare algoritmului SAD.

In Figura 19, semnalul scos pe portul de iesire 1 constituie estimarea miscarii .

Caracteristici precum autoscalarea si raportarea situatiilor de overflow, precum si parametrii in virgula fixa sunt folositoare in situatii de genul detectarea conditiilor de depasire a dynamic range sau aprecierea impactului modalitatilor de rotunjire asupra calculelor intermediare.

O problema ce trebuie luata in considerare in momentul conceperii unui sistem fixed-point este efectul pe care il are limitarea dynamic range-ului si scalarea asupra calculelor intermediare. In cazul acestui sistem, un rezultat intermediar il constituie imaginea „diferenta absoluta” (AD) ce este creata chiar inaintea obtinerii iesirii SAD. Secventa video ce reprezinta rezultatul AD poate fi obtinuta in diagrama bloc anterioara din portul de iesire no.1, etichetat „AD”. Un exemplu de imagine ce contine diferentele intre 2 secvente succesive este prezentata in Figura 20.

Figure 20: Imaginea diferentelor absolute

Algoritmul de Localizare Markov