Resum

Utilitzant una placa de processament d’imatges que disposa d’una FPGA programable amb VHDL, s’ha implementat un algorisme que permet el seguiment de 5 microrobots i d’una pilota. S’utilitza aquesta placa per poder localitzar els jugadors 50 vegades/segon. Aquest mateix algorisme implementat per software dóna un rendiment molt baix degut al seu alt cost computacional.

La placa realitza la tasca d’etiquetar els píxels i l’algorisme s’encarrega de localitzar els robots. Quan es té un robot localitzat es centra una finestra de seguiment sobre el jugador i es calcula el seu centre de masses. Les coordenades dels jugadors són enviades a un sistema de control encarregat de prendre les decisions necessaris per cada un dels jugador.

1 Introducció

Dins el Departament d’Electrònica, Informàtica i Automàtica de la Universitat de Girona s’ha desenvolupat una placa de processament d’imatge [1], que permet la implementació d’algorismes paral·lels mitjançant un llenguatge de desenvolupament de hardware: el VHDL. Aquest llenguatge permet la programació concurrent mitjançant la creació de processos que s’executen en paral·lel. Les passes a seguir per tal de desenvolupar un algorisme són molt semblants a la programació tradicional, però diferenciant-se en que finalment, en lloc d’un codi executable, es sintetitza una lògica que queda mapejada en hardware sobre un dispositiu programable. Aquest sistema de visió s’utilitzarà per realitzar el seguiment d’un equip de microrobots cooperants que jugen a futbol [2].

És un requeriment indispensable del sistema el que funcioni en temps real, de tal manera que la única limitació del seu rendiment vingui fixada per l’estàndard de vídeo (50 imatges/segon). Aquest sistema serà utilitzat per l’equip de la Universitat de Girona que participa a la RoboCup F-180 League on competeixen 5 contra 5 robots [3].

Per arribar a aquest objectiu cal realitzar un preprocessament de la imatge, a continuació aplicar un algorisme per trobar i fer els seguiment dels jugadors i finalment enviar les coordenades al sistema que s’encarrega del control dels jugadors. En la literatura es poden trobar diferents implementacions per solucionar aquest problema [4,5]. Nosaltres hem optat per un preprocessat de la imatge consistent en etiquetar la imatge en funció del valor RGB de cada píxel. La forma d’etiquetar la imatge està lligat a l’arquitectura de la nostra placa de processament.

Les dimensions i colors del camp i dels robots estan fixats per les normes de la competició. El sistema que utilitza l’equip de la Universitat de Girona per realitzar la competició consta de:

Un camp de joc.

Una camera 3 CCD situada a sobre del camp sobre la vertical del centre del camp.

Un PC encarregat del sistema de visió per trobar la posició dels jugadors i de la pilota. Aquest PC té instal·lada la tarja de processament.

Una segon PC que llegeix les coordenades dels jugadors i de la pilota i fent servir tècniques d’intel·ligència artificial genera les consignes que s’han d’enviar a cada robot via radio.

Un transmissor de radio.

La carcassa dels jugadors té forma cilíndrica amb un diàmetre de 12,5 cm. A la tapa s’hi ha col·locat unes taques de colors per identificar els jugadors. Al centre hi ha un cercle de color amb el diàmetre equivalent de 4,1 cm que pot ser de color groc o blau.

Per determinar quina és la orientació del jugador s’utilitza un cercle de color lila que és comú a tots els jugadors del mateix equip. Per fer la identificació de cada un dels jugadors s’utilitza un tercer color, el verd, en funció del número de cercles de color verd i de la seva posició es pot conèixer quin jugador és. De la identificació de cada un dels jugadors se n’encarrega una aplicació software i es per això que el sistema de seguiment no cal que segmenti el color verd. A la Figura 1 es pot observar un robot amb la seva carcassa i els colors que l’identifiquen.

2 Definició de subsistemes

Per realitzar el seguiment dels 5 jugadors cal particionar el sistema per dividir les diverses funcions a realitzar.

Senyals de control.

Comunicació amb el PC.

Segmentació de la imatge.

Seguiment de 5 jugadors i la pilota.

2.1 Senyals de control

Aquest subsistema s’encarrega, bàsicament de generar les senyals de sincronisme horitzontal (SYNC_H), i de sincronisme vertical (SYNC_V) i les coordenades del píxel actual. La senyal SYNC_H serveix per indicar a la resta de subsistemes que ho necessitin quan s’ha processat una línia sencera de píxels. La senyal SYNC_V és l’equivalent a la senyal SYNC_H però ens indica quan s’ha processat un quadre sencer de la imatge. Aquest procés també s’encarrega d’anar comptant els píxels a mesura que van arribant per la camera per saber en tot moment quina és la coordenada del píxel actual.

2.2 Comunicació amb el PC

EL procés encarregat de la comunicació amb el PC realitza 3 funcions:

Llegir les senyals de control enviades pel PC i enviar-les al subsistema afectat.

Recollir les dades calculades pels altres subsistemes i enviar-les al PC quan aquest llegeixi de la tarja.

Emplenar la memòria de la placa (LUT) amb la taula de segmentació generada pel PC.

2.3 Segmentació de la imatge

Aquest subsistema és l’encarregat de processar la imatge d’entrada provinent de la camera. Per realitzar la segmentació s’utilitza una taula de segmentació que s’emmagatzema a una memòria (LUT) de la tarja de processament. Per a cada valor RGB s’assigna una etiqueta. Per aquesta aplicació cal utilitzar 3 etiquetes: per la posició del jugador, per l’orientació dels jugador i per posició de la pilota. Per eliminar soroll les etiquetes són filtrades. El filtre utilitzat és una operació morfològica open 2x2.

A més a més, aquest subsitema es l’encarregat de generar una imatge de sortida per poder visualitzar el resultat del seguiment. S’encarrega dibuixar les finestres de seguiment dels jugadors i de la pilota per tal de tenir una realimentació visual del funcionament del sistema.

2.4 Algorisme de seguiment

L’algorisme utilitzat per localitzar el cinc jugadors és el següent:

A mesura que arriben píxels es mira si estan etiquetats amb l’etiqueta del color de l’equip. Quan arriben un conjunt de píxels suficients per poder afirmar que s’ha localitzat un jugador es finalitza la busqueda en aquesta imatge i es guarda la coordenada del jugador.

Quan es comença la captura de la següent imatge es centra una finestra sobre la posició on s’havia localitzat el primer jugador. Per trobar el segon jugador es torna a buscar píxels etiquetats amb el color de l’equip però que quedin fora de la finestra de seguiment del primer jugador. En el moment que el nombre de píxels amb l’etiqueta de l’equip sigui superior a un llindar establert es guarden les coordenades del segon jugador.

Quan arribin els píxels de dins de la finestra del primer jugador cal calcular el centre de masses dels píxels etiquetats amb el color de la posició del jugador i el centre de masses dels píxels etiquetats amb el color de l’orientació del jugador. Amb aquest dos punts es té una mesura de la posició i de l’orientació del jugador.

Aquest procés es repeteix fins a localitzar tots els jugadors tenint en compte que per trobar un nou jugador no es tenen en compte els píxels que estan dins de les finestres dels jugadors ja localitzats.

Passades 5 imatges, si tot ha anat bé, ja s’han localitzat tots els jugadors i a la sisena imatge ja es disposa de la posició i orientació de tots els jugadors. Si en algun moment es perd la posició d’algun jugador es tornen a buscar píxels etiquetats amb la posició del jugador a dins de tot el camp i fora de les finestres dels altres jugadors.

Figura 3 Diagrama de flux de dades pel seguiment del 5 jugadors. Tots els blocs treballen en paral·lel.

(a) (b)

(c) (d)

(e) (f)

Figura 4 Evolució temporal de l’algorisme: localització inicial dels jugadors i la pilota. (a) A la primera imatge cal localitzar el primer jugador i la pilota (b) A la següent imatge ja s’ha trobat el primer jugador i la posició de la pilota (c) A la tercera imatge es troba el segon jugador (d) Després es localitza el quart jugador (e) Passades 5 imatges ja es tenen els 5 jugadors localitzats (f) A la sisena imatge ja s’està realitzant el seguiment.

3 Visualització de la imatge processada

Utilitzant la taula de segmentació de la LUT la imatge es segmentada i només ens quedem amb els píxels del color de que indiquen quina és la posició i orientació dels jugador i amb el color de la pilota. Visualitzant la imatge etiquetada s’aconsegueix que els píxels que són de color fosc quedin ressaltats i es vegi millor si la imatge té soroll. Per l’eliminació del soroll s’ha d’activar el filtratge morfològic.

Si observem una imatge de tot el camp com la Figura 5 es por observar que hi ha tota una zona on no cal realitzar el seguiment dels jugadors perquè queda fora dels límits del camp, es per això que cal indicar a la tarja de processament on està situat el camp. Els píxels que queden fora del camp són depreciats, no s’utilitzen per fer el seguiment dels jugadors.

Figura 5 Seguiment dels 5 jugadors i de la pilota per la tarja de processament

Un cop es té la imatge segmentada, etiquetada i filtrada es pot començar a aplicar l’algorisme de seguiment.

Sobre cada jugador que es realitza el seguiment es dibuixa una finestra de color blanc. Sobre la pilota es dibuixa una finestra de color vermell (veure Figura 5).

El host (ordinador on està connectada la tarja de processament) llegeix les coordenades de les posicions i orientacions dels jugadors i de la posició de la pilota. Aquestes dades es passen al sistema de control per decidir quina acció ha de prendre cada jugador. Les dades llegides pel host es representen visualment a la Figura 6.

Figura 6 Seguiment de 5 jugadors i de la pilota pel host

4 Anàlisi temporal

A la Figura 7 es pot observa quin és e diagrama de temps de l’algorisme.

Captura de la imatge: A l’instant de temps t=0 es comença de capturar la imatge, després de capturar les 287 línies amb informació de vídeo es finalitza la captura (t=18368 m s). La mitja línia que també conté informació de vídeo no es té en compte per no complicar la lògica.

Etiquetatge: L’etiquetatge de la imatge va desfasada respecte la captura 20ns aquest retard és produeix perquè cal accedir a la LUT per obtenir les etiquetes i el temps d’accés a la LUT és de 20 ns. L’etiquetatge de la imatge finalitza al mateix tems que la captura.

Filtratge: Una operació morfològica open 2x2 implica aplicar un erode a la imatge original, i a continuació un dilate a la imatge resultant. La concatenació d’aquestes dues operacions genera el mateix retard (en termes dels píxels que ens va passant la càmera) que si passéssim un únic filtre 3x3. Per poder passar un filtre 3x3 no es pot donar una valor al píxel central fins que no es coneguin els valors de tots els elements de la matriu 3x3. El fet de passar el filtre fa que es produeixi un retard d’una línia i un píxel respecte a la imatge capturada (64,1 m s). El filtratge finalitza quan acaba la captura de la imatge.

Acumulació de coordenades: a mesura que les etiquetes són filtrades, quan es troba una etiqueta que pertany algun jugador o a la pilota les seves coordenades són acumulades i s’incrementa el número de píxels

Figura 7 Diagrama de temps

• Càlcul del centre de masses: Al finalitzar l’acumulació de les coordenades ja es pot començar a calcular els centres de masses. Per calcular-lo cal dividir la coordenada acumulada per número de píxels de l’objecte corresponent. Com que es fa el seguiment de 5 jugador i de la pilota cal trobar 11 coordenades (5*posició jugador+5*orientació jugador+1*posició pilota) i com que cada coordenada està formada per 2 valors cal realitzar 22 divisions. Per seleccionar els valors a dividir i realitzar la divisió són necessaris 20 cicles del rellotge de 10 MHz, per tant per realitzar les 22 divisions calen 44 m s (22 divisions*20 cicles*100 ns).
• Comunicació amb el PC: quan ja s’han calculat els centres de masses el PC els ha de llegir. El temps que pot tardar a llegir les dades depèn completament de l’ocupació del PC i del sistema operatiu. Si el PC està completament dedicat a llegir les dades de la tarja i tenint en compte que el BUS ISA funciona a 10 MHz, la lectura del centre de masses pot tardar 3,3 m s (22 dades*100 ns+11 dades per alliberar el BUS*100ns). Donat que treballem amb un sistema operatiu multitasca però no temps real (Windows 98), és difícil estimar el temps necessari perquè el host porti a terme la lectura de les dades. Això dependrà no només de la velocitat de la CPU, sinó també de la planificació de l’execució dels threads, de la prioritat d’aquests i de la càrrega del sistema, generalment el host està realitzant altres tasques com visualitzar la imatge de vídeo, filtrar les dades obtingudes, realitzar prediccions sobre el moviment dels jugadors i de la pilota. Tot això pot retardar la lectura de les dades. El retard màxim que es pot permetre el host és de 20 ms, si tardés més es perdrien dades. Les proves realitzades han demostrat que no hi ha pèrdua rendiment a menys que es despleguin els menús de l’aplicació.


5 Experiments realitzats

Per comprovar quina és la precisió del sistema s’han realitzat tota una sèrie proves per comprovar la precisió de les dades. Primer de tot cal calcula quina és la relació entra les dades obtingudes i el món real. Les distàncies dels objectes d’una imatge es mesuren en píxels, coneixen les mides del camp en píxels i les mides del camp amb centímetres es pot trobar la següent correspondència:



Veient aquestes dades, una variació d’un píxel és de 0,617 cm en coordenades X i de 0,815 cm en coordenades Y.

Un altre aspecte a tenir es compte és el problema del càlcul d’angles. La imatge que genera la camera té una relació de 4:3, en canvi la imatge processada per la tarja i sobre la qual es realitzen les mesures té 522x287 píxels. Cal realitzar una correcció de les dades per corregir aquesta deformació.



Figura 8 Error en el càlcul dels angles

S’ha de escalar la imatge de la tarja perquè compleixi les proporcions de 4:3. Les operacions a realitzar per corregir la mesura dels angle són les següents:


(1)

S’ha realitzar una aproximació per treballar amb el mateix número de línies d’una quadre d’una imatge de l’estàndard de vídeo, se suposa que la tarja de processament mesura 288 línies.

Figura 9 Pilota en moviment: zoom sobre una imatge entrellaçada de 768´ 576 pixels.

La imatge de vídeo que està entrellaçada, cada imatge la formen dos quadres, un amb les línies imparells i l’altre amb les línies parells. Quan es captura una imatge d’un objecte en moviment i s’entrellacen els dos quadres el resultat és que s’obté un objecte deformat perquè els dos quadres s’han capturat en instant de temps diferents. A la Figura 9 es pot observar quin és el resultat de capturar una imatge amb la pilota en moviment. Si es calcula el centre de masses d’aquesta imatge en donarà un punt intermig entre el centres de masses del primer i del segon quadre. Per evitar aquest problema es calcula el centre de masses a cada quadre, d’aquesta manera s’obté una mesura més exacta de la posició de la pilota en moviment i encara que es perdi resolució vertical.

6 Resultats

Per veure com són les dades obtingudes pel seguiment s’han recollit dades sobre la posició de la pilota i dels jugadors.

Si es col·loca la pilota en una posició estàtica, en teoria, la mesura hauria de ser sempre la mateixa. A la pràctica es produeixen petites variacions. A la Taula 1 es poden observar els principals valors estadístics de les dades obtingudes. Observant aquestes dades es veu que la variància de les coordenades és molt petita.

 

	Coordenada X	Coordenada Y
Màxim	419	199
Mínim	416	195
Mitjana	416,84	196,676
Variància	0,3679	0,3002

Taula 1 Estadístics de la posició de la pilota (mesures en píxels)

Realitzant la mateixa prova amb un jugador els resultats obtinguts són mot similars (veure Taula 2 i Taula 3).
 

	Coord. X  posició	Coord. Y  posició
Màxim	415	118
Mínim	413	117
Mitjana	414,0689	117,9655
Variància	0,0785	0,03352

Taula 2 Estadístics de la posició del jugador (mesures en píxels)

	Coord. X  orientació	Coord. Y  orientació
Màxim	417	124
Mínim	415	121
Mitjana	416,2827	122,8069
Variància	0,3153	0,2124

Taula 3 Estadístics de l’orientació del jugador (mesures en píxels)

A continuació s’ha comprovat quina és la resposta del sistema de seguiment amb objectes mòbils. A la Figura 10 es representen les dades obtingudes de la pilota, inicialment està parada, un moment donat se li dona un cop, avança, realitza un doble rebot contra una cantonada del camp i surt més esmorteïda. Els resultats són molt bons ja que la pilota segueix trajectòries rectilínies i les dades obtingudes descriuen trajectòries rectilínies.



Figura 10 Coordenades d'una pilota en moviment: la línia contínua correspon a la coordenada X, la discontínua correspon a la Y

La prova realitzada amb el jugador ha consistit en fer-li donar una volta i recollir dades sobre les coordenades de la posició, de l’orientació i realitzar el càlcul de l’angle de l’orientació. La Figura 11 estan representades les dades d’un jugador realitzant una trajectòria circular, amb aquestes dades s’ha calculat l’angle de l’orientació de la Figura 12. Les coordenades tenen una variació molt petita però l’angle resultant té unes oscil·lacions molt grans, que farien difícil el control dels robots.



Figura 11 Coordenades d'un jugador realitzant una trajectòria circular: la línia contínua
correspon a les coordenades de posició, i les discontínues corresponen a l’orientació


Figura 12 Angle d'un jugador realitzant una trajectòria circular

 
Per mirar de suavitzar aquests errors en el càlcul de l’angle s’ha aplicat un filtre d’ordre 1 [6] a les mesures de la coordenades. L’equació d’aquest filtre és la següent:

L’estimació d’una coordenada en un instant temps k és funció de l’estimació anterior i de la diferencia entre la dada actual i l’estimació anterior. El paràmetre k s’utilitza per suavitzar més o menys l’efecte del filtre, per valors a prop de 1 es dona més importància a la dada actual i per valors a prop del 0 es dona més importància a l’estimació anterior. La Figura 13 s’observa quin és el resultat de l’aplicació d’aquest filtre a les coordenades d’orientació i posició amb una k=0.2.

Si es comparen les dades obtingudes del càlcul de l’angle de la Taula 4 es pot observar que la variància disminueix notablement utilitzant el filtre.

 

	Angle	Angle Filtrat K=0.2
Màxim	90	75,3767
Mínim	61,1134	66,1365
Mitjana	71,2723	71,3421
Variància	34,4243	3,5360

Taula 4 Estadístics de l'angle del jugador
(mesures en graus)


Figura 13 Angle de l'orientació filtrat

7 Conclusions

Els principals problemes que han sorgit durant la implementació són la limitació d’espai de programació de la FPGA i la necessitat de que el sistema de seguiment funcioni de 50 imatges/segon. Com a conseqüència d’aquesta limitació d’espai les seguiment dels jugadors contraris no es pot realitzar amb aquesta FPGA.

Els objectius que s’han complert són:

• Segmentar la imatge.
• Realitzar el seguiment dels 5 jugadors de l’equip propi per trobar-ne la posició i l’orientació.
• Realitzar el seguiment de la pilota.
• Enviar totes les coordenades al PC.
• Visualitzar els resultats.
• Aconseguir un temps de cicle de 20 ms per tot l’algorisme.


Agraïments

Els autors voldrien agrair la seva ajuda i col·laboració de tots els companys del laboratori, i en especial a Josep Tomàs, Lluís Magí i Tomàs Medel.

Referències
 

• Garcia, R., De La Rosa, J.Ll., Oller, A., Batlle, J., Figueras, A., Ramon, J.A. "A Fast Vision System for Tracking in Robotic Soccer" Proceedings on Micro-Robot World Cup Soccer Tournament, (MIROSOT’98), Paris, Francia,1998.
• Kitano, H., Kuniyoshi, Y., Noda, I., Asada, M., Matsubara, i Osawa, E-I. "Robocup: a challenge problem for AI," Artificial Intelligence Magazine, vol.18(1), pp.73–85, 1997.
• Sargent, R., Bailey, B., Witty, C., i Wright, A. Dynamic object capture using fast vision tracking, Artificial Intelligence Magazine, vol. 18:1, pp. 65–72, 1997.
• Hong, C.S., Chun, S.M., Lee, J.S., and Hong K.S., "A Vision-Guided Object Tracking and Prediction Algorithm for Soccer Robots", IEEE International Conference on Robotics and Automation, vol.1, pp. 346-351, 1997.
• Matsumoto,Y., Shibata, T., Sakai, K., Ibana, M., and Inoue, H., "Real-Time Color Stereo Vision System for a Mobile Robot based on Field Multiplexing", in Proceedings of the IEEE International Conference on Robotics and Automation, vol.3, pp. 1934-1939, 1997
• Isermann, R. "Digital control systems," Springer-Verlag, 1991.