Repositorio Institucional de Documentos

ESTUDIO DE VIABILIDAD DE UN ALGORITMO DE SEGUIMIENTO BASADO EN EL APRENDIZAJE PREVIO DE TRAYECTORIAS “HABITUALES” PROYECTO FIN DE CARRERA INGENIERÍA DE TELECOMUNICACIONES ESPECIALIDAD DE ELECTRÓNICA Autor: Miguel Alberto Sanz Pardo Director: José Elias Herrero Jaraba Zaragoza - 15 de junio de 2011 Universidad de Zaragoza - Centro Politécnico Superior Departamento de Electrónica y Comunicaciones ESTUDIO DE VIABILIDAD DE UN ALGORITMO DE SEGUIMIENTO BASADO EN EL APRENDIZAJE PREVIO DE TRAYECTORIAS “HABITUALES” Proyecto Fin de Carrera Titulación: Ingeniería de Telecomunicaciones Autor: Miguel Alberto Sanz Pardo Director: José Elias Herrero Jaraba Zaragoza - 15 de junio de 2011 II RESUMEN En este proyecto de fin de carrera se pretende estudiar la viabilidad de un algoritmo de seguimiento basado en el aprendizaje previo de trayectorias “habituales”. Para ello nos apoyaremos en un trabajo anterior formado por distintos métodos de detección y seguimiento de objetos. Las trayectorias “habituales” o “comunes” son aquellas trayectorias asociadas a los objetos en movimiento (en nuestro caso personas, pero se podría aplicar a otros objetos usando los modelos apropiados) que aparecen con más frecuencia durante un cierto intervalo temporal en la zona espacial en la que pretendemos usar nuestro algoritmo de seguimiento. Para la obtención de trayectorias nos apoyaremos, como ya hemos mencionado antes, en un sistema de detección y seguimiento que ya ha sido desarrollado préviamente. Posteriormente a esto nos encargaremos de obtener las trayectorias medias a partir del conjunto de trayectorias obtenidas inicialmente. A estas trayectorias medias es a lo que llamaremos trayectorias “habituales” o “comunes”. Una vez calculadas, trataremos de realimentar a los algoritmos de seguimiento con dichas trayectorias con el fin de que mejore el funcionamiento de dichos algoritmos. Se pretenderá además que la introducción de esta nueva información afecte lo menos posible al sistema en cuanto a inestabilidad y practicidad, de forma que el sistema pueda ejecutarse en tiempo real o en su defecto cercano a ello. En este trabajo en concreto se va a trabajar con las posiciones y las trayectorias de los jugadores de dos equipos que se están enfrentando en un partido en un campo de futbol. En nuestro caso disponemos de 3 cámaras, las cuáles se han usado para grabar el partido (una en la zona izquierda, otra en la zona central y otra en la zona derecha del campo). De esta manera estaremos trabajando en un entorno real; el cuál a pesar de parecer estar controlado, es más caótico de lo que se pueda pensar a priori, puesto que cada jugador tiende a moverse por diferentes zonas del campo. De esta manera, si somos capaces de mejorar el sistema de seguimiento en este entorno, en teoría podremos ponerlo en práctica también en otros ámbitos fuera de lo deportivo. Palabras clave: Visión por computador, detección, seguimiento, trayectorias, kalman, UKF, MHT, homografía, tracker, mutiobjeto. III IV AGRADECIMIENTOS En primer lugar, muchas gracias a todos/as los que me habeis dado vuestro apoyo a lo largo de la carrera, en especial a: Fran, Jesús, Antonio e Isabel, ya que sin su ayuda posiblemente aún no habría empezado el P.F.C. También agradecer los buenos momentos pasados a lo largo de la carrera a: Diego, Jorge, Emilio, Diana, Julia, Manolo, Andrés, Rillo, David, Alberto, Alex, Jesús, Javi, Ángel, Loreto, Aitor, Héctor o Murfi entre otros tantos compañeros de la carrera. También agradecer el apoyo de aquellas personas que han estado en mi vida y le han dado un cierto sentido, desde amigos de la infancia (Domingo, Dani, Asier y Victor, entre otros) hasta amigos más recientes (Carlos, Tirso, Musta, Fernando, Alfredo y Rafa, entre otros). Por supuesto agradecer y dedicar este trabajo a toda mi familia: abuelos, tíos, primos, padre y en especial a mi madre que a veces parece sufrir más que yo con mi carrera y cuando la finalice estoy seguro de que se sentirá muy contenta. Y ante todo gracias a mi director Elías Herrero, por permitirme hacer este interesante proyecto y aportar buenas ideas para su desarrollo; a los profesores David Buldain y Carlos Orrite por aportar ideas interesantes para éste; y a todos mis compañeros de laboratorio por hacer más amenos los días: Miguel, Mario, Jorge y Pedro; en especial a Jorge, ya que sin su ayuda este P.F.C. igual aún no estaría finalizado. Y si por descuido se me ha olvidado mencionar a alguien en los agradecimientos, también gracias a todas esas personas por estar ahí. V VI Índice general 1. Introducción 1 1.1. Descripcióndelproyecto.................................. 2 1.2. Objetivosdelproyecto ................................... 3 1.3. Estructuradelproyecto................................... 5 2. Trayectorias “habituales” o “comunes” 7 2.1. Introducción......................................... 7 2.2. Adquisición y filtrado previo de trayectorias individuales . . . . . . . . . . . . . . . . . 7 2.3. Obtención de trayectorias medias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.1. Distancia entre dos trayectorias . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.2. Media de dos trayectorias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.3. Mediadentrayectorias............................... 19 2.4. Inclusión de las trayectorias “habituales” en los algoritmos de seguimiento . . . . . . . . 22 2.4.1. Introducción .................................... 22 2.4.2. Inclusión de trayectorias “habituales” en el algoritmo de seguimiento MSUKF . 23 2.4.3. Inclusión de trayectorias “habituales” en el algoritmo de seguimiento MHT . . . 26 3. Análisis de Resultados 29 VII 3.1. Introducción......................................... 29 3.2. Resultados obtenidos con el sistema de seguimiento MSUKF . . . . . . . . . . . . . . . 29 3.2.1. Conclusiones(MSUKF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3. Resultados obtenidos con el sistema de seguimiento MHT . . . . . . . . . . . . . . . . 43 3.3.1. Conclusiones(MHT) ................................ 48 4. Conclusiones y sugerencias para futuras investigaciones 53 4.1. Conclusiones ........................................ 53 4.2. Sugerencias para futuras investigaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 55 ANEXOS 55 A. Estado del Arte 57 A.1.Introducción......................................... 57 A.2.Detección.......................................... 57 A.2.1. Detección de movimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 A.2.2. Segmentación de la imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 A.2.3. Clasificación de figuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 A.3.Seguimiento......................................... 59 A.3.1. Algoritmos de seguimiento tipo Kalman . . . . . . . . . . . . . . . . . . . . . . 59 A.3.2. Algoritmos de seguimiento tipo Monte Carlo . . . . . . . . . . . . . . . . . . . 60 A.3.3. Algoritmos multihipótesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 A.3.4. Algoritmos multisensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 VIII Introducción campo de futbol se acerca más a un escenario real que a un entorno controlado. Por lo tanto, los algoritmos de detección y seguimiento que han sido desarrollados podrían ser usados en otros escenarios sin demasiadas dificultades si disponemos de los modelos (de los objetos a detectar y seguir) adecuados. 1.3. Estructura del proyecto El proyecto estárá dividido en 4 capítulos y 3 anexos, los cuáles estarán organizados de la siguiente manera: - Capítulo 1: Introducción. Capítulo inicial en el que se describe el proyecto en términos generales, la motivación existente para su realización y los objetivos finales de dicho proyecto. - Capítulo 2: Trayectorias “habituales” o “comunes”. En el tercer capítulo se describe el método usado para la obtención de trayectorias iniciales y el cálculo de trayectorias medias. Además se explica el método usado para la inclusión de las trayectorias medias obtenidas previamente, en los algoritmos de seguimiento. - Capítulo 3: Análisis de resultados. En el penúltimo capítulo nos encargaremos de analizar los resultados obtenidos en las distintas pruebas realizadas a partir de nuestros algoritmos de seguimiento. - Capítulo 4: Conclusiones y sugerencias para futuras investigaciones. En el cápítulo final se valorará el grado de cumplimiento de los objetivos definidos anteriormente y cuáles son los aspectos que podrían mejorarse para un futuro. - Anexo A: Estado del arte. En el primer anexo se habla de diferentes algoritmos de detección y de seguimiento los cuáles han sido desarrollados préviamente. - Anexo B: Sistema de Detección. En el segundo anexo se describe el sistema de detección utilizado para obtener las medidas(supuestos jugadores que han sido detectados) que servirán como datos de entrada para nuestro sistema de seguimiento. - Anexo C: Sistema de Seguimiento. En el último anexo se describen los sistemas de seguimiento utilizados en nuestro proyecto, los cuáles en un principio tan solo disponen como datos de entrada de las medidas obtenidas en el sistema de detección. Una vez sean obtenidas las trayectorias medias serán realimentados además 5 Capítulo 1 con la información de dichas trayectorias. Mediante dichos algoritmos de seguimiento podremos estudiar si existe mejora o no al realimentar nuestro sistema con las trayectorias medias. 6 Trayectorias “habituales” o “comunes” CAPÍTULO 2 TRAYECTORIAS “HABITUALES”O “COMUNES” 2.1. Introducción Llamaremos trayectorias “habituales” o “comunes” a aquellas trayectorias asociadas a objetos en movimiento(en nuestro caso jugadores de futbol, pero se podría aplicar a otros objetos usando los modelos adecuados), las cuáles aparecen con mayor frecuencia durante un determinado intervalo temporal en la zona espacial en la que vamos a dar uso de nuestro sistema de seguimiento. En primer lugar obtendremos las trayectorias individuales de cada jugador para un intervalo temporal determinado. A continuación, agruparemos las más similares y obtendremos las trayectorias “habituales” como la media de cada grupo de trayectorias. Finalmente realimentaremos a nuestro sistema de seguimiento con dichas trayectorias, de manera que sirvan como un parámetro de entrada junto con las medidas obtenidas en la detección. Para ver si hay mejoras en cuanto al seguimiento, calcularemos cuál es el error del sistema de seguimiento con y sin el uso de trayectorias medias y compararemos los resultados. 2.2. Adquisición y filtrado previo de trayectorias individuales Para hallar las trayectorias individuales de cada jugador, en primer lugar deberemos de obtener mediante nuestro sistema de detección y seguimiento (de forma supervisada), las posiciones de los diferentes jugadores a lo largo del intervalo temporal que deseemos. Es decir, deberemos de realizar un etiquetado previo de las posiciones reales de los jugadores de campo de ambos equipos(ni porteros, ni árbitros, ni el resto del personal que hay en los alrededores del terreno de juego). De tal forma dispondremos de 20 “trackers” (estructura de datos que contiene la posición y el estado de cada objeto en movimiento) en cada frame. Dicho etiquetado será realizado a través de un entorno gráfico como CVLAB(que funciona bajo Visual C++), el cuál se basará en nuestro sistema de detección y seguimiento, de manera que si alguna de las estimaciones de algún jugador es incorrecta, dicho error deberá ser corregido mediante la 7 Capítulo 2 Figura 2.1: Interfaz gráfica de CVLAB. supervisión de un usuario. Podemos ver un ejemplo del la interfaz gráfica de CVLAB en la Figura 2.1. En este trabajo, guardaremos las posiciones de los diferentes jugadores de campo para 5 intervalos temporales diferentes: - Del frame 1 al frame 15000. - Del frame 1 al frame 3333. - Del frame 3334 al frame 6666. - Del frame 6667 al frame 9999. - Del frame 10000 al frame 13333. 8 Trayectorias “habituales” o “comunes” Figura 2.2: Representación gráfica de la división en cuadrantes realizada sobre el campo de futbol. En nuestro caso, hay que tener en cuenta que el intervalo temporal correspondiente a 45 minutos será igual a 15000 fotogramas o frames. Una vez realizado este paso previo, nos encargaremos de obtener las trayectorias individuales de cada jugador. Para ello, mediante el software matemático “Matlab”, dividiremos el campo de fubol en 40 cuadrantes uniformemente distribuidos(tal y como podemos ver en la Figura 2.2); y a continuación almacenaremos las trayectorias individuales por cuadrante en una estructura de datos determinada. Definiremos a una trayectoria como un vector de puntos que definen la evolución temporal de un objeto en movimiento. Cada punto contendrá el mismo número de características, las cuáles pueden ser: posición, velocidad, forma, relación de aspecto, color o tamaño entre otras. En nuestro caso procesaremos las trayectorias por cuadrantes, de manera que definiremos a una trayectoria individual por cuadrante como aquella trayectoria asociada a un jugador que entra por un borde del cuadrante y sale ,después de un número de frames determinado, por otro borde de dicho cuadrante. Podemos ver un ejemplo de trayecoria individual en la Figura 2.3. 9 Capítulo 2 Figura 2.3: Ejemplo de trayectoria individual en el cuadrante 14. Una vez que disponemos de las trayectorias individuales procederemos a filtrarlas, de manera que no serán consideradas como válidas aquellas trayectorias en las que se cumpla alguna de estas dos restricciones: - Que estén formadas por un número puntos inferior a un umbral establecido (Dichas trayectorias no las consideraremos significativas). - Que la distancia entre alguno de sus pares de puntos sucesivos sea mayor que un umbral determinado (Dichas trayectorias serán consideradas como erróneas). Tras este filtrado, realizaremos un suavizado de las trayectorias, previo a la obtención de las trayectorias“habituales”. A la hora de obtener las trayectorias por cuadrante podremos plantear nuestro problema de dos formas diferentes: - Obtener las trayectorias por cuadrante de forma individual para cada jugador. - Obtener las trayectorias por cuadrante de forma global para los 20 jugadores. En ambos casos estudiaremos si hay mejora o no respecto al caso de no usar la información de las trayectorias en nuestros sistemas de seguimiento. 10 Trayectorias “habituales” o “comunes” 2.3. Obtención de trayectorias medias Una vez disponemos de las trayectorias por cuadrante, agruparemos las más similares para cada cuadrante y obtendremos las trayectorias “habituales” como la media de cada grupo de trayectorias. Para realizar dicho agrupamiento usaremos un algoritmo jerárquico([14]), el cuál se divide en 4 etapas: 1. Cálculo de una matriz de distancias, por cuadrante, que contenga la distancia dos a dos entre cada par de trayectorias de dicho cuadrante. 2. Búsqueda de la distancia más pequeña que esté fuera de la diagonal de dicha matriz. En caso de que dicha distancia supere el umbral de distancia que hayamos definido, el algoritmo se dará por finalizado. 3. Fusión de las dos trayectorias asociadas a la distancia mínima obtenida en la etapa anterior, mediante el cálculo de la media de dichas trayectorias. 4. Actualización de la matriz de distancias, teniendo en cuenta la eliminación de las trayectorias a partir de las cuales se ha realizado la fusión y la inclusión de la nueva trayectoria obtenida. Tras esto se vuelve a la fase 2. A continuación describiremos los métodos asociados al cálculo de la distancia entre dos trayectorias y los asociados al cálculo de la media de n trayectorias. 2.3.1. Distancia entre dos trayectorias Introducción En la actualidad, la distancia más conocida entre dos trayectorias es la distancia de Hausdorff([13]). Dicha distancia solo es commutativa si se calcula el máximo de aplicarlo dos veces para cada par de trayectorias: H(A, B) = m´ax {h(A, B), h(B, A)}(2.1) h(A, B) = m´ax a∈A{m´ın b∈B{d(a, b)}} (2.2) Esta distancia tan solo tiene en cuenta un punto de cada trayectoria a la hora de calcular dicha distancia, de manera que el ruido en los puntos iniciales y finales puede alterar el resultado final. Existen modificaciones de la Distancia Hausdorff como la Distancia Parcial de Hausdorff o la Distancia de Proximidad de Hausdorff, pero en ambas modificaciones a pesar de obtener mejores resultados que en la original, 11 Capítulo 2 existen otros problemas que complican el uso de dichas Distancias. De tal manera, se pretenderá diseñar un método que resuelva los problemas que sucedían con la Distancia de Hausdorff y sus modificaciones. Buscaremos que la nueva Distancia sea commutativa y que sea capaz de obtener resultados coherentes con trayectorias ruidosas. Método usado Comenzaremos clasificando cada trayectoria respecto al resto de trayectorias en dos grupos, dividiéndolas entre las que podemos medir la distancia entre ellas de una manera coherente y las que no. Al primer grupo lo llamaremos trayectorias “cercanas” mientras que al segundo grupo lo llamaremos trayectorias “lejanas”. En el caso de que dos trayecorias sean cercanas se calculará la distancia entre ellas. Consideraremos que dos trayectorias son cercanas entre sí en el caso de que cumplan estas dos condiciones a la vez: C1=d(as, bs) + d(af, bf) 2< th1(2.3) C2= m´ın Pf−1 i=sd(ai,ai+1) PnA−1 i=1 d(ai,ai+1),Pf−1 i=sd(bi,bi+1) PnB−1 i=1 d(bi,bi+1)> th2(2.4) donde: nA, nB: Número de puntos que definen las trayectorias A y B respectivamente. d(x, y): Distancia entre los puntos x e y. ci p: Punto más cercano (de la otra trayectoria) al punto p de la trayectoria i . as, bs: Puntos que definen la primera distancia mínima. af, bf: Puntos que definen la última distancia mínima. as=   a1si d(a1, cA 1)≤d(b1, cB 1) cB 1si d(a1, cA 1)> d(b1, cB 1)(2.5) af=   anAsi d(anA, cA nA)≤d(bnB, cB nB) cB nBsi d(anA, cA nA)> d(bnB, cB nB)(2.6) bs=   b1si d(b1, cB 1)≤d(a1, cA 1) cA 1si d(b1, cB 1)> d(a1, cA 1)(2.7) bf=   bnBsi d(bnB, cB nB)≤d(anA, cA nA) cA nAsi d(bnB, cB nB)> d(anA, cA nA)(2.8) Podemos ver un ejemplo de puntos que definen la primera y la última distancia mínima entre dos trayectorias, en la Figura 2.4. Las trayectorias que no cumplan las dos condiciones a la vez se considerará que 12 Trayectorias “habituales” o “comunes” Figura 2.4: Ejemplo en el que se muestran los puntos que son necesarios definir para comprobar si dos trayectorias están lo suficientemente cerca como para medir su distancia con exactitud o no(para considerarlas como “cercanas” o “lejanas”). están demasiado alejadas como para poder calcular su media de forma que podamos obtener un resultado coherente. Para calcular la distancia entre dos trayectorias “cercanas” dividiremos a ambas trayectorias en segmentos, situando el mismo número de puntos nde forma equidistante a lo largo de ambas trayectorias. A dichos puntos los llamaremos “puntos clave”. Dada una trayectoria A, sus “puntos clave” serán: a0i=a[s+i.(f−s) n−1]i= 0,1,2, ..., n −1(2.9) De la misma forma, los “puntos clave” de una trayectoria B serán: b0i=b[s+i.(f−s) n−1]i= 0,1,2, ..., n −1(2.10) donde [x] representará al entero más próximo a x. Una vez se calculen todos los “puntos clave” para ambas trayectorias, se calculará el punto más cercano a cada “punto clave” respecto de la otra trayectoria. De tal manera dispondremos de una distancia parcial para cada “punto clave” : da0i= m´ın b∈Bd(a0i, b)db0i= m´ın a∈Ad(b0i, a)i= 0,1,2...n (2.11) Finálmente, calcularemos la distancia total entre dos trayectorias “cercanas” como: D=Pn i=1 m´ın{da0i, db0i} n(2.12) Al calcular la distancia entre dos trayectorias, no tenemos por qué referirnos tan solo a la distancia posicional, sino que podemos tener en cuenta otras características como puede ser la velocidad. De tal manera, la distancia parcial entre dos puntos podrá ser calculada como una media ponderada de las distancias de cada una de estas características. Para ello habrá que definir un peso para cada característica. Si disponemos de n características, representadas como c1,c2,...,cn, con sus correpondientes pesos w1, 13 Capítulo 2 Figura 2.5: Ejemplos de distribuciones de distancias parciales entre trayectorias. w2,...,wn, definiremos la distancia parcial entre dos puntos como: d= n X i=1 wi.dfi(2.13) Mediante este método calculamos una serie de distancias parciales entre los puntos de cada trayectoria y después realizamos su media. De la manera que está planteado el cálculo de la distancia global, el algoritmo tiende a evitar calcular una distancia parcial entre los puntos en los que las trayectorias están más separadas momentáneamente. En caso de que las trayectorias permanezcan separadas durante un período largo de tiempo, el algoritmo acabará por calcular la distancia parcial entre puntos en los que las trayectorias estén más alejadas. Podemos ver algunas distribuciones de distancias parciales en la Figura 2.5. Uno de los parámetros más importantes a tener en cuenta será el número de puntos usados para realizar el cálculo de la distancia total. En caso de trayectorias bastante cercanas, el número de puntos usados no suele afectar al resultado obtenido (distancia total obtenida). En caso de trayectorias con una parte común(cercana) y otra parte divergente(lejana), el efecto de dicho extremo divergente será mayor cuantos menos “puntos clave” se usen, de forma que la distancia total se reducirá si aumentamos el número de “puntos clave”. Podemos ver un ejemplo del efecto que tiene el número de puntos usado en los dos casos comentados anteriormente en la Figura 2.6. 14 Trayectorias “habituales” o “comunes” Figura 2.13: Ejemplo del proceso de obtención de trayectorias medias. Las trayectorias iniciales se muestran en color verde y los agrupamientos de éstas - los cuáles habrá un momento en que sean considerados como trayectorias medias - en color azul. 21 Capítulo 2 Figura 2.14: En la figura de la izquierda(superior) podemos ver las trayectorias individuales que se han obtenido inicialmente para el cuadrante 14, mientras que en la figura de la derecha(superior) podemos ver las trayectorias medias que se han obtenido a partir de dichas trayectorias individuales. En las figuras inferiores podemos ver lo mismo que en las superiores pero con un zoom. Por otra parte podemos ver un ejemplo de obtención de trayectorias medias a partir de trayectorias individuales en uno de los cuadrantes en los que se divide el campo de futbol en la Figura 2.14. 2.4. Inclusión de las trayectorias “habituales” en los algoritmos de seguimiento 2.4.1. Introducción Una vez disponemos de las trayectorias “habituales” en cada cuadrante, deberemos realimentar a nuestro sistema de seguimiento con dichas trayectorias, de manera que sirvan como parámetro de entrada 22 Trayectorias “habituales” o “comunes” junto con las medidas obtenidas en la detección. NOTA: Se recomienda leer los anexos B y C de forma previa a la lectura de los próximos apartados del capítulo 2. 2.4.2. Inclusión de trayectorias “habituales” en el algoritmo de seguimiento MSUKF Tal y como se comenta en el Anexo C (Sistema de Seguimiento), Apartado 3, una vez hemos realizado las predicciones de estado, el matching de las predicciones y las medidas, y las predicciones de medida, pasaremos a calcular la estimación de estado para cada jugador. En primer lugar, una vez disponemos de las trayectorias “habituales” y de las medidas asociadas a cada cámara para cada jugador(medidas, las cuáles han sido pasadas a las coordenadas del plano del suelo), para cada medida que haya sido asociada a cada cámara(para los distintos jugadores), se calculará la ganancia de Kalman, de la cuál nos interesarán los valores asociados a las coordenadas X e Y (KX(cam), KY(cam)cam ∈(1,3)). Cuanto más cercanos a 1sean los valores de las dos componentes de K, mejor consideraremos que son las medidas tomadas por las cámaras. De tal manera para nuestras trayectorias calcularemos un valor KTRAY tal que: KTRAYX= 1 −max(KX(cam)) y KTRAYY= 1 −max(KY(cam)) si nMed 6= 0 KTRAYX= 1 y KTRAYY= 1 si nMed = 0 (2.19) KTRAY =√((KT RAYX)2+(KT RAYY)2) √2(2.20) Es decir, si el número de medidas asociadas a cada tracker(hasta un máximo de tres medidas, una por cámara) es distinto de cero entonces KTRAYX= 1 −max(KX(cam)) yKTRAYY= 1 − max(KY(cam)). En caso contrario KTRAY =KTRAYX=KTRAYY= 1 Usaremos dos métodos diferentes para trabajar con las trayectorias “habituales”: - En el primer método, de entre todas las trayectorias que aparecen en el cuadrante en el que se encuentra el jugador, usaremos la información de aquellas que se encuentren por debajo de un umbral(área de gating); el cuál estará asociado a la distancia entre el estado anterior del jugador cuyo estado queremos estimar y el punto más cercano de cada trayectoria respecto a este estado anterior. - En el segundo método calcularemos la suma de dos distancias: •Distancia entre la posición asociada al Estado anterior de un jugador y el punto más cercano de la trayectoria respecto a dicho Estado anterior. •Distancia entre la posición asociada al Estado predecido de un jugador y el punto siguiente al punto más cercano de la trayectoria respecto al estado anterior. 23 Capítulo 2 Figura 2.15: Ejemplo de como calcular el peso en el caso de una trayectoria. El peso asociado a una trayectoria será proporcional al inverso de la distancia entre el estado predecido de un jugador y el vector formado por los dos puntos más cercanos de la trayectoria respecto al estado anterior, trasladado al estado anterior. En primer lugar se creará un área de gating alrededor del estado anterior, de forma que filtremos aquellas trayectorias cuyos puntos más cercanos están dentro del área de gating. Una vez han sido seleccionadas las trayectorias, trasladaremos el vector formado por los dos puntos más cercanos de cada trayectoria al estado anterior. Calcularemos el peso asociado a cada trayectoria como el inverso de la distancia entre el estado predicho y el vector (formado por los dos puntos más cercanos) trasladado al estado anterior. De tal manera tan solo usaremos la información de la trayectoria cuya suma de distancias sea la menor de entre todas las que haya en el cuadrante para cada jugador en cada frame. A continuación procederemos a calcular los pesos para cada medida y para cada trayectoria. Para cada trayectoria que intervenga “crearemos una cámara virtual” cuyo peso será igual a: peso(cam) = KTRAY distanciatray(cam −3) cam ∈(4,4 + ntray −1) (2.21) donde : distanciatray(cam): es la distancia de mahalanobis entre el estado predecido de un jugador y el vector formado por los dos puntos más cercanos de la trayectoria respecto al estado anterior, trasladado al estado anterior. Podemos ver un ejemplo de como calcular dicha distancia en la Figura 2.15. Para cada medida su peso será igual a: peso(cam) = 1 distanciamedida(cam)cam ∈(1,3) si medida_asociada(cam)6= 0 peso(cam) = 0 cam ∈(1,3) si medida_asociada(cam)=0 (2.22) donde: distanciamedida(cam): es la distancia de mahalanobis que hay entre el estado predecido de un 24 Trayectorias “habituales” o “comunes” jugador y la medida que ha sido asociada al tracker de dicho jugador para una de las tres cámaras usadas. medida_asociada(cam): es la medida asociada a la camara cam respecto al tracker de un jugador. Una vez hayamos calculado todos los pesos, éstos se deberán normalizar de forma que la suma de todos ellos sea igual a 1. Finalmente calcularemos el estado estimado para un jugador jcomo: est_est(j)X=est_pred(j)X+ 3 X cam=1 inno_med(cam)X+ 4+ntray X cam=4 inno_tray(cam)X est_est(j)Y=est_pred(j)Y+ 3 X cam=1 inno_med(cam)Y+ 4+ntray X cam=4 inno_tray(cam)Y (2.23) inno_med(cam)X=peso(cam)·KX(cam)·(Match(j, cam)X−med_pred(j, cam)X) inno_med(cam)Y=peso(cam)·KY(cam)·(Match(j, cam)Y−med_pred(j, cam)Y)(2.24) inno_tray(cam)X=peso(cam)·KT RAYX·(MatchV ir(cam −3)X−est_pred(j)X) inno_tray(cam)Y=peso(cam)·KT RAYY·(MatchV ir(cam −3)Y−est_pred(j)Y)(2.25) donde: inno_med(cam)X: Innovación asociada a la medida obtenida en la cámara cam (coordenada X). inno_med(cam)Y: Innovación asociada a la medida obtenida en la cámara cam (coordenada Y). inno_tray(cam)X: Innovación asociada a la trayectoria obtenida en la cámara virtual cam(coord.X). inno_tray(cam)Y: Innovación asociada a la trayectoria obtenida en la cámara virtual cam(coord.Y). est_pred(j)X: Estado predecido del jugador j(coordenada X). est_pred(j)Y: Estado predecido del jugador j(coordenada Y). med_pred(j, cam)X: Medida predecida de la cámara cam para el jugador j(coordenada X). med_pred(j, cam)Y: Medida predecida de la cámara cam para el jugador j(coordenada Y). Match(j, cam)X: Medida obtenida para la cámara cam respecto al jugador j(coordenada X). Match(j, cam)Y: Medida obtenida para la cámara cam respecto al jugador j(coordenada Y). MatchV ir(cam −3)X: Vector formado por los dos puntos más cercanos de la trayectoria cam (con cam ∈(4,4+ntray)) respecto al estado anterior, trasladado al estado anterior (coordenada X). MatchV ir(cam −3)Y: Vector formado por los dos puntos más cercanos de la trayectoria cam (con cam ∈(4,4+ntray)) respecto al estado anterior, trasladado al estado anterior (coordenada Y). 25 Capítulo 2 Una vez hemos realizado distintas simulaciones, hemos podido comprobar que usando la información de las trayectorias “habituales” en todos los fotogramas(siempre y cuando estuviesen dentro del área de gating del estado anterior), el resultado no siempre era satisfactorio, en cierta medida porque el peso asociado a las medidas era distorsionado por el peso de las trayectorias. Por lo tanto hemos creado un umbral para el factor KTRAY, de modo que si nuestro KTRAY no supera dicho umbral en dicho fotograma, no se usará la información de las trayectorias en ese fotograma. Simulando para distintos umbrales, hemos podido observar que la ganancia de kalman K(la ganancia máxima entre las 3 cámaras en un frame determinado) de las cámaras como muy baja es de 0.5. Por tanto, si tomamos un umbral para nuestro KTRAY mayor que 0.5 significará que solo vamos a usar la información de las trayectorias en caso de que no haya medidas en ninguna de las tres cámaras en un frame determinado. Como se verá más adelante en el apartado de resultados, en el caso de usar la información de las trayectorias tan solo en los fotogramas en los que no haya medidas(cuando ninguna de las 3 cámaras obtengan medidas al mismo tiempo para un jugador), obtendremos mejores resultados que en el caso de no usar trayectorias. 2.4.3. Inclusión de trayectorias “habituales” en el algoritmo de seguimiento MHT Una vez se realiza la predicción de estado y de medida para cada hipótesis, pasaremos a la etapa de asociación de datos, tal y como se explica detalladamente en el Anexo C: Sistema de Seguimiento, Apartado 4. La etapa de asociación de datos se divide en 5 fases: 1. Selección de medidas 2. Obtención de la matriz de combinaciones 3. Cálculo de la probabilidad a priori de cada combinación 4. Generación de hipótesis 5. Renormalización conjunta de hipótesis En la fase de selección de medidas, una vez disponemos de las trayectorias “habituales” por cuadrante, de entre todas las trayectorias que aparecen en el cuadrante en el que se encuentra cada jugador, seleccionaremos para cada hipótesis de cada “tracker” aquellas que se encuentren por debajo del umbral umbral_tray(área de gating); el cuál estará asociado a la distancia entre el estado anterior del jugador cuyo estado queremos estimar y el punto más cercano de cada trayectoria respecto a este estado anterior. Tras esto para cada hipótesis de cada tracker seleccionaremos aquellas trayectorias(las cuáles han sido 26 Trayectorias “habituales” o “comunes” filtradas por el umbral anterior) en las las cuáles el vector formado por los dos puntos más cercanos de dicha trayectoria respecto al estado anterior, trasladado al estado anterior, se encuentren dentro del área de gating de la predicción de estado. Para ello calcularemos la distancia de Mahalanobis entre cada trayectoria(par de puntos de la trayectoria más cercanos al estado anterior, los cuáles han sido trasladados al estado anterior) y la predicción de estado de cada hipótesis. A su vez seleccionaremos para cada hipótesis de cada tracker aquellas medidas las cuáles se encuentren dentro del área de gating de la predicción de estado. Para ello calcularemos la distancia de Mahalanobis entre cada medida y la predicción de estado de cada hipótesis y si dicha distancia está por debajo del umbral umbral_medida entonces la medida asociada a dicha distancia será seleccionada. Por tanto disponemos de un umbral para seleccionar medidas y de dos umbrales para seleccionar trayectorias. De tal manera, la información obtenida de las medidas y de las trayectorias le servirá como entrada a nuestro sistema de seguimiento, de modo que tras estudiar las posibles combinaciones de medidas y trayectorias para cada tracker y tras eliminar el exceso de trackers y normalizar las probabilidades podremos pasar a estimar los estados de cada jugador. En el algoritmo de seguimiento MHT no existe un parámetro en sí el cuál indique como son de buenas las medidas de las cámaras, como la ganancia de Kalman usada en el MSUKF(en la teoría existe, pero en el algoritmo desarrollado en la práctica no existe como tal). Si realizamos simulaciones con y sin trayectorias podemos ver que no hay grandes mejoras, incluso hay empeoramiento. En caso de usar las trayectorias solo cuando las cámaras no disponen de ninguna medida podemos encontrar que hay mejoría respecto al caso de usarlas siempre (siempre que no superen ninguno de los dos umbrales). Podemos ver que si limitamos el número de hipótesis por jugador los resultados obtenidos son mejores que respecto a usar un número elevado de hipótesis. Esto se debe, posiblemente, a que al disminuir el número de hipótesis tenemos en cuenta las hipótesis más probables y eliminamos aquellas peores, de manera que el algoritmo de seguimiento no tienda a seguir las medidas y las trayectorias asociadas a las hipótesis más malas y que posiblemente sean equívocas. De igual manera, si los umbrales usados para filtrar las trayectorias son más bajos, el error tiende a disminuir. Esto se debe a que al disminuir los umbrales, permitimos tan solo la entrada de información asociada a las trayectorias más cercanas a nuestros “trackers”, de manera que evitamos introducir información de trayectorias que estén demasiado alejadas, las cuáles pueden estar introduciendo ruido y haciendo que en vez de mejorar, empeore nuestro sistema se seguimiento. Los resultados obtenidos serán comentados de una forma más detallada en el siguiente capítulo. 27 Capítulo 2 28 Análisis de Resultados CAPÍTULO 3 ANÁLISIS DE RESULTADOS 3.1. Introducción En este capítulo vamos a mostrar, analizar y comparar los resultados obtenidos con el sistema inicial de detección y seguimiento respecto al mismo sistema realimentado con las trayectorias “medias” de los distintos jugadores. Para ello compararemos el error obtenido antes y después de introducir la información de las trayectorias medias. Dicho error será calculado como la distancia euclídea entre la que sería la posición real de cada jugador en cada frame y la posición obtenida con el sistema de detección y seguimiento. Para obtener la posición real de cada jugador, etiquetaremos previamente a los distintos jugadores durante 15000 frames(que en nuestro caso equivalen a los 45 minutos de la primera parte de un partido de futbol). A continuación lanzaremos a simular un número de fotogramas determinado de dicho partido de futbol y obtendremos las posiciones estimadas de los jugadores para cada fotograma. De tal manera podremos calcular el error mencionado anteriormente. Obviamente, si el sistema que es realimentado con las trayectorias dispone de un menor error que el sistema incial, habremos obtenido una mejora; no obstante deberemos de observar los tiempos de cómputo usados por nuestro computador para realizar los cálculos con y sin trayectorias, ya que queremos obtener una mejoría en términos de error de manera que nuestro sistema funcione a una velocidad lo más cercana posible a la del sistema inicial (el cuál pretende funcionar de la forma más cercana posible al tiempo real). Por tanto, además de obtener errores deberemos de obtener tiempos de cómputo o simulación. 3.2. Resultados obtenidos con el sistema de seguimiento MSUKF En primer lugar, hemos obtenido el término de error para el sistema incial. Para ello hemos realizado varias simulaciones, modificando en cada una de ellas el umbral que está relacionado con la distancia de Mahalanobis entre las predicciones de estado y la medidas asociadas a éstas. De esta manera, aquellas medidas que estén por debajo de dicho umbral intenvendrán a la hora de realizar la asociación entre medidas y la predicción de estado, y a la hora de realizar la estimación de estado. En caso contrario esas medidas serán desechadas. Llamaremos a dicho umbral: umbral_medida. 29 Capítulo 3 Figura 3.1: Tabla que muestra el error obtenido en el sistema inicial para distintos valores de umbral_medida, para 200 y para 1000 fotogramas. En la Figura 3.1 podemos ver los errores obtenidos para distintos umbrales. Hemos calculado el error para los 200 fotogramas iniciales y para los 1000 fotogramas iniciales. Vistos los resultados obtenidos usaremos para el resto de las simulaciones con MSUKF un valor de umbral_medida igual a 12. En segundo lugar, para el sistema el cuál ya está realimentado con las trayectorias “habituales”, calcularemos el error para distintos valores de umbral_KTRAY y distintos valores de umbral_tray. Recordemos que cada medida asociada a cada cámara(una medida por cámara como mucho) dispone de una ganancia K, la cuál indica lo buena o mala que es la medida; y que hemos creado una variable KTRAY = 1 −max(K(cam)) cam ∈(1,3). De tal manera, llamaremos umbral_KTRAY a aquel umbral que permitirá el uso de la información de las trayectorias en caso de que KTRAY sea mayor que el valor de dicho umbral. Por otra parte llamaremos umbral_tray al umbral asociado a la distancia eculídea que hay entre el estado anterior de un jugador y el punto más cercano de una trayectoria que se encuentre en el mismo cuadrante en que se encuentra el jugador. De tal modo, si la distancia asociada a una trayectoria es menor a ese umbral su información será usada y en caso contrario no. Hemos podido observar que el valor de K como muy bajo es cercano a 0.5. Recordemos que el valor de K puede ir entre 0 y 1 (de peor a mejor medida). En los casos en los que no hay medidas KTRAY=1. En las Figuras 3.2 y 3.3 podemos ver que los valores de error, para distintos valores de umbral_tray, oscilan para un KTRAY ∈(0,0,5) , de manera que a veces el error es mayor y otras menor que en el caso de no usar trayectorias. Por otra parte podemos observar que para valores de KTRAY mayores de 0.5 el valor del error se estabiliza (puesto que el valor de la K de las cámaras es como muy bajo igual a 0.5, sino pasa directamente a 0; es decir, cuando no hay medidas en ninguna cámara), de manera que dicho error resulta ser menor que en el caso de no usar trayectorias. Por tanto fijaremos umbral_KTRAY a un valor superior a 0.5, por ejemplo de 0.9, de manera que solo usaremos la información de las trayectorias cuando ninguna de las 3 cámaras disponga de medidas. Finalmente, una vez hemos fijado los valores de umbral_medida(12) y de umbral_KTRAY(0.9), comenzaremos a realizar las simulaciones que realmente nos van a interesar. Realizaremos simulaciones 30 Análisis de Resultados TRAYECTORIAS INDEPENDIENTES(T.“HABITUALES”): MÉTODO 1 Figura 3.8: Tabla que muestra el error obtenido en el sistema modificado para los valores de umbral_tray: 2, 2.5, 3, 4, 5, 10, 15, 20, 25, 30 y 10000 (para 1000 fotogramas). TRAYECTORIAS INDEPENDIENTES(T.“HABITUALES”): MÉTODO 2 Figura 3.9: Tabla que muestra el error obtenido en el sistema modificado (para 1000 fotogramas). 37 Capítulo 3 TRAYECTORIAS INDEPENDIENTES(T.“HABITUALES” + T.“NO USUALES”): MÉTODO 1 Figura 3.10: Tabla que muestra el error obtenido en el sistema modificado para los valores de umbral_tray: 2, 2.5, 3, 4, 5, 10, 15, 20, 25, 30 y 10000 (para 1000 fotogramas). TRAYECTORIAS INDEPENDIENTES(T.“HABITUALES” + T.“NO USUALES”): MÉTODO 2 Figura 3.11: Tabla que muestra el error obtenido en el sistema modificado (para 1000 fotogramas). 38 Análisis de Resultados Nota aclaratoria respecto a las gráficas: En los casos en los que el error está sombreado de color verde significa que dicho error, el cuál ha sido obtenido mediante el sistema modificado(sistema realimentado con la información de las trayectorias), es menor que el obtenido mediante el sistema original(sistema en el que no se usa la información de las trayectorias). En los casos en los que el error está sombreado de color amarillo significa que dicho error, el cuál ha sido obtenido mediante el sistema modificado, es algo mayor que el obtenido mediante el sistema original, pero por una diferencia pequeña. En los casos en los que el error no está sombreado significa que dicho error, el cuál ha sido obtenido mediante el sistema modificado, es bastante mayor que el obtenido mediante el sistema original. 3.2.1. Conclusiones(MSUKF) A grandes rasgos podemos ver que para una simulación más larga obtenemos mejores resultados que para una simulación más corta, respecto a no usar la información de las trayectorias. Existe un mayor número de casos en los que el error obtenido con la información de las trayectorias es menor que el error obtenido sin la información de las trayectorias. Podemos ver esto en la Figuras 3.12 , 3.13 y 3.14. Figura 3.12: Tabla que muestra el número de casos en los que hay mejora y empeoramiento respecto a no usar la información de las trayectorias. En dicha tabla se muestra el caso de las trayectorias globales para los 200 y para los 1000 primeros frames. 39 Capítulo 3 Figura 3.13: Tabla que muestra el número de casos en los que hay mejora y empeoramiento respecto a no usar la información de las trayectorias. En dicha tabla se muestra el caso de las trayectorias independientes para los 200 y para los 1000 primeros frames. Figura 3.14: Gráfica que muestra el error para distintos valores de umbral_tray para el caso de trayectorias globales(trayectorias “habituales”) para los 200 y para los 1000 primeros frames. Se puede apreciar que para el caso de 1000 frames los errores del sistema modificado(el que usa la info. de las trayectorias) suelen estar por debajo de los errores del sistema inicial(el que no usa la info. de las trayectorias); lo cuál no ocurre en tan gran proporción para el caso de 200 frames. 40 Análisis de Resultados Figura 3.15: Tabla que muestra el número de trayectorias que intervienen para distintos valores de umbral_tray para los casos de trayectorias globales “habituales” y trayectorias independientes “habituales” (para 1000 frames). Se puede ver que al aumentar el valor de umbral_tray entran más trayectorias en juego, como es de esperar. Por otra parte para el mismo valor de umbral_tray se puede ver que interviene un número mayor de trayectorias en el caso de las trayectorias globales. Por otra parte observamos que el uso de las trayectorias globales suele ser mejor frente el uso de las trayectorias independientes. Aunque antes de realizar las simulaciones podríamos pensar que iba a suceder lo contrario, si vemos los resultados obtenidos, se puede interpretar que esto es debido a que en el caso de usar trayectorias independientes, interviene un número muy pequeño de trayectorias en comparación con el uso de trayectorias globales, tal y como podemos ver para distintos valores de umbral_tray en la Figura 3.15. Algo que puede resultar bastante interesante de ver, es que usando trayectorias “habituales” que no corresponden al intervalo inicial obtenemos mejores resultados que respecto a no usar trayectorias. De tal manera, si en un partido procesáramos durante un número determinado de fotogramas las trayectorias “habituales” y después usaramos esa información en fotogramas posteriores (en los cuáles no han intervenido esas trayectorias), deberíamos de obtener mejorías en cuanto a términos de error; que es justamente lo deseable en este sistema. A simple vista, no existe mucha diferencia en términos de errores a la hora de usar solo trayectorias “habituales” o de usar trayectorias “habituales” + trayectorias “no usuales”. Por lo tanto será preferible usar solo trayectorias “habituales”, ya que el sistema se sobrecargará menos (intenvendrá un número menor de trayectorias y el tiempo de computo será por tanto menor). No obstante si atendemos a la Figura 3.16 podemos ver que para 1000 fotogramas el error suma(error formado por la suma de los errores en los 5 intervalos usados para obtener las trayectorias para distintos valor de umbral_tray) es menor en el caso de solo usar trayectorias “habituales” 41 Capítulo 3 Figura 3.16: Gráfica que muestra el error suma(error formado por la suma de los errores en los 5 intervalos usados para obtener las trayectorias para distintos valor de umbral_tray) para los casos de trayectorias globales: trayectorias “habituales” y trayectorias “habituales”+“no usuales”. La simulación ha sido realizada para los primeros 1000 frames Figura 3.17: Gráfica que muestra el error para distintos valores de umbral_tray para el caso de trayectorias globales: trayectorias “habituales” y trayectorias “habituales”+“no usuales”. En ambos casos la simulación ha sido realizada para los primeros 1000 frames. Respecto a usar el método 1 o el método 2, parece no haber tampoco mucha diferencia en cuanto a términos de errores. En caso de usar el método 1, a priori no hay un umbral_tray óptimo para el cuál se obtengan mejores resultados que para el resto, tal y como podemos ver en la Figura 3.17 42 Análisis de Resultados 3.3. Resultados obtenidos con el sistema de seguimiento MHT En primer lugar analizaremos el error obtenido para el sistema inicial, el cuál trabaja solo con la información de las medidas y no con la de las trayectorias. Para ello hemos realizado varias simulaciones para los 200 y para los 1000 primeros fotogramas, modificando en cada una de ellas varios parámetros: - Por una parte disponemos del umbral que está relacionado con la distancia de Mahalanobis entre las predicciones de estado y la medidas asociadas a éstas; al cuál llamaremos umbral_medida. Si las medidas disponen de una distancia inferior a dicho umbral, en tal caso su información será tenida en cuenta. - Por otra parte disponemos del nohipótesis máximo por jugador a tener en cuenta en cada fotograma. - Además disponemos de otro umbral, el cuál está relacionado con la distancia euclídea entre la posición del estado anterior de un jugador y la posición del estado estimado del mismo jugador para la misma hipótesis; al cuál llamaremos umbral_antest. En caso de que esa distancia sea menor que el umbral, la posición del estado estimado del tracker se actualizará, en caso contrario la posición del estado estimado será igual a la posición estado anterior en dicho fotograma. Como primera aproximación realizaremos simulaciones cortas(de 200 fotogramas), pero en general solo vamos a mostrar las simulaciones largas(de 1000 fotogramas). No obstante en el apartado de resultados de MHT, si es necesario e interesante comentaremos algún aspecto a resaltar en las simulaciones cortas. Podemos ver el error obtenido para distintos valores de los 3 parámetros anteriores en la Figura 3.18. Se puede observar que al aumentar el node hipótesis máximo por jugador, en general, el error tiende a aumentar. Esto se debe, posiblemente, a que al disminuir el número de hipótesis tenemos en cuenta las hipótesis más probables y eliminamos aquellas peores, de modo que el algoritmo de seguimiento no tienda a seguir las medidas asociadas a las hipótesis más malas y que posiblemente sean equívocas. Por otra parte el error tiende a ser menor en las simulaciones realizadas con el umbral_antest máximo y el umbral_medida de 5.99. De tal manera, fijaremos para el resto de las simulaciones los parámetros: - NoHipótesis máxima: 2. - umbral_antest: max. - umbral_medida: 5.99. 43 Capítulo 3 Figura 3.18: Tabla que muestra el error obtenido en el sistema inicial para distintos valores de umbral_medida, nohipótesis máxima por jugador y umbral_antest, para los 1000 primeros fotogramas. Los valores que vemos a la derecha de la tabla están asoaciados a la suma total del error obtenido para los distintos valores de umbral_antest. Los valores que vemos debajo de la tabla están asoaciados a la suma total del error obtenido para los distintos valores de umbral_medida. Una vez hemos fijado los parámetros antes mencionados, pasaremos a realizar simulaciones de 1000 fotogramas para el sistema el cuál ya está realimentado con la información de las “trayectorias comunes”. Dichas simulaciones serán realizadas para distintos valores de umbral_tray (2.5, 5, 10 20). El umbral umbral_tray estará asociado a la distancia euclídea entre la posición del estado anterior del jugador cuyo estado queremos estimar y el punto más cercano de cada trayectoria (que se encuentre en el mismo cuadrante que el jugador) respecto al anterior. En caso de que esa distancia sea menor a umbral_tray, la información de la trayectoria pasará por un segundo filtrado. Dicho filtrado consistirá en otro umbral, el cuál está relacionado con la distancia de Mahalanobis entre el vector formado por los dos puntos más cercanos de cada trayectoria respecto al estado anterior (trasladado al estado anterior) y la predicción de estado. En caso de que dicha distancia sea menor al umbral mencionado, la información de dicha trayectoria será tenida en cuenta. En el caso de este umbral usaremos el mismo valor que hemos usado para umbral_medida. Podemos ver los resultados obtenidos en la Figura 3.19. En principio podemos ver que los resultados empeoran respecto a no usar la información de las trayectorias. Esto es debido a que en cada fotograma, para cada hipótesis de cada tracker, las trayectorias suelen ganarle el terreno a las medidas, debido a que normalmente para cada tracker, el número de trayectorias es mucho mayor que el número de medidas, además de que las trayectorias suelen disponer de una distancia más pequeña que en el caso de las medidas, respecto al estado predecido. 44 Análisis de Resultados Figura 3.19: Tabla que muestra el error obtenido en el sistema modificado(alimentado con la info. de las trayectorias) para distintos valores de umbral_tray, para el caso en el que siempre se usa la información de las trayectorias (siempre que no se superen umbral_tray y umbral_medida) y para el caso en que solo se usa dicha información cuando no hay medidas en ninguna de las tres cámaras (para los 1000 primeros fotogramas). Por lo tanto, igual que en el caso del algoritmo de seguimiento MSUKF, usaremos tan solo la información de las trayectorias cuando no haya medidas en ninguna de las 3 cámaras. De tal manera podemos ver como el error disminuye respecto al caso de usar trayectorias en todo momento (siempre que no superen los 2 umbrales comentados anteriormente). Además en ocasiones el error disminuye respecto al caso de no usar trayectorias. Una vez hemos fijado todos los umbrales en el sistema de seguimiento MHT, al igual que en el caso del MSUKF realizaremos simulaciones de 1000 fotogramas para distintos valores de umbral_tray. Utilizaremos dos conjuntos de trayectorias “habituales” diferentes: - Trayectorias independientes En la fase del procesamiento de trayectorias por cuadrante procesaremos las trayectorias de forma individual para cada jugador. - Trayectorias globales En la fase del procesamiento de trayectorias por cuadrante procesaremos las trayectorias de forma conjunta para todos los jugadores. Por otra parte, además de trabajar solo con trayectorias “habituales”, también analizaremos los resultados obtenidos al usar trayectorias “no usuales” junto con las trayectorias “habituales”, como hacíamos en el algoritmo MSUKF. En el caso del MHT, de los dos métodos usados en el MSUKF, solo trabajaremos con el primer método, puesto que no aporta muchas mejoras respecto al segundo método, además de que es más dificil de implementar mediante el sistema MHT. 45 Capítulo 3 TRAYECTORIAS GLOBALES(TRAYECTORIAS “HABITUALES”): MÉTODO 1 Figura 3.20: Tabla que muestra el error obtenido en el sistema modificado para los valores de umbral_tray: 2, 2.5, 3, 4, 5, 10, 15, 20, 25, 30 y 10000 (para 1000 fotogramas). TRAYECTORIAS GLOBALES(T.“HABITUALES” + T.“NO USUALES”): MÉTODO 1 Figura 3.21: Tabla que muestra el error obtenido en el sistema modificado para los valores de umbral_tray: 2, 2.5, 3, 4, 5, 10, 15, 20, 25, 30 y 10000 (para 1000 fotogramas). 46 Conclusiones y sugerencias para futuras investigaciones CAPÍTULO 4 CONCLUSIONES Y SUGERENCIAS PARA FUTURAS INVESTIGACIONES 4.1. Conclusiones Tal y como hemos podido ver en las diferentes simulaciones realizadas hemos conseguido que nuestro sistema de seguimiento consiga mejorar a base de realimentarlo con la información de las trayectorias “habituales”. En nuestras simulaciones se trabajaba con los primeros fotogramas de un partido -1000 fotogramas, teniendo en cuenta que una parte entera de un partido eran 15000- usando la información de las trayectorias “habituales” obtenida para distintos intervalos (Recordemos que habíamos obtenido las trayectorias “habituales” para 5 intervalos: 1-1333 , 3334-6666, 6667-9999, 10000-13333, 1-15000). Se tendería a pensar que si había mejoría en nuestro sistema se daría usando las trayectorias “habituales” del intervalo 1-1333 (ya que realizamos nuestras simulaciones para el intervalo 1-1000) o del intervalo 1-15000. En el caso del algoritmo de seguimiento MHT, si usamos trayectorias globales la mejora se suele producir sobre todo cuando usamos la información de las trayectorias “habituales” para el intervalo 1-15000. Sin embargo, en el sistema MSUKF, cuando se trabaja con trayectorias globales se obtiene una mejoría en casi todos los casos (hasta de un 16 por cierto en términos de error), de manera que incluso con trayectorias que no pertenecen al intervalo en el que se está realizando el seguimiento, se consiguen mejorar los resultados respecto a no usar la información de las trayectorias. Esto es bastante esperanzador, ya que podíamos aplicarlo en un partido para poder ir mejorando nuestro sistema en tiempo real. A pesar de que pudiesemos esperar lo contrario, hemos obtenido mejores resultados con el sistema MSUKF que con el sistema MHT. Esto puede ser debido a varios aspectos. Por un lado es posible que no hayamos conseguido fijar de la mejor forma posible los parámetros iniciales, puesto que el sistema MHT dispone de un amplio abanico de estos, a diferencia del MSUKF; el cuál dispone de un número 53 Capítulo 4 Figura 4.1: Tiempos de cómputo obtenidos para diferentes simulaciones para distintos conjuntos de trayectorias “habituales”. Dichas simulaciones han sido realizadas, mediante el software matemático Matlab, con un Pentium Dual Core T4400 @2.20GHz 2.20GHz con 4 gigas de memoria RAM. Si pasaramos el código a lenguage c++ se obtendrían tiempos de cómputo bastante más pequeños pero las simulaciones iniciales se realizan con Matlab. menor de parámetros. Por otro lado, cabe pensar que el sistema MHT a pesar de que puede disponer de varias hipótesis por tracker, dichas hipótesis se basan cada una en un filtro de Kalman lineal; y sin embargo, el sistema MSUKF a pesar de disponer de una sola hipótesis por tracker, se basa en un filtro de Kalman no lineal(UKF). Por otra parte, debemos atender a los tiempos de cómputo. Tal y como podemos ver en la Figura 4.1, atendiendo al sistema de seguimiento para los 1000 fotogramas de estudio, el tiempo de cómputo suele ser inferior a los 1000 segundos, eso sí, no estamos teniendo en cuenta el tiempo de cómputo del sistema de detección, el cuál desconocemos. Se puede ver que el sistema MHT es más lento que el MSUKF, en este caso no mucho, debido a que en nuestras simulaciones se han tomado como mucho dos hipótesis por jugador. A mayor número de hipótesis más lento irá el sistema. Si comparamos los tiempos de cómputo al usar trayectorias con respecto a no usarlas, se puede ver que dependiendo del intervalo de trayectorias usado los tiempos podrán llegar incluso a triplicarse (en caso de usar trayectorias globales para el intervalo 1-15000). No obstante para los intervalos de 3333 frames (que en nuestro caso son los que realmente interesarían para poder realizar mejoras en tiempo real), los tiempos se multiplican aprox. por un factor 1.5; lo cuál no es muy grave. 54 Conclusiones y sugerencias para futuras investigaciones 4.2. Sugerencias para futuras investigaciones Los algoritmos de seguimiento planteaban dos grandes problemas en un principio: - Los cruces y oclusiones que se producen entre jugadores dentro del campo de futbol. En especial en jugadas en las que hay una gran acumulación de personas en una zona del campo (como los saques de esquina o los saques de falta). - Los momentos en los que no hay medidas en las cámaras y el algoritmo de seguimiento debe de guiarse por sí mismo (por sus predicciones). Mediante el uso de la información de las trayectorias “habituales” parece que el primer problema es capaz de solucionarse en ocasiones sencillas. Pero en ocasiones complejas como pueden ser un cruce entre jugadores del mismo equipo o una aglomeración de jugadores(en especial este último caso) la cosa se complica. Por otra parte, el segundo problema parece solucionarse de manera correcta, ya que cuando no hay medidas usamos la información de las trayectorias, de manera que obtenemos un menor error que si dejamos al propio algoritmo de seguimiento que se guie por sus predicciones. Como sugerencias futuras para paliar de una forma mayor ambos problemas se podrían plantear varios aspectos: - Disponer de cámaras de una mayor resolución que entre otras cosas fuesen capaces de capturar la silueta de los números de las camisetas de los jugadores dentro de lo posible. - Disponer de cámaras cenitales o aéreas junto con las cámaras laterales. - Disponer de un mayor número de cámaras, de manera que tengamos una mayor número de puntos de vista(En el problema actual tan solo se trabajaba con 3 cámaras). - Obtener las regiones de probabilidad cada jugador (probabilidad de que se encuentre en una zona del campo u otra); y usar dicha información para realimentar nuestro sistema de seguimiento junto con la información de las medidas y de las trayectorias “habituales”. 55 Anexo 56 Estado del Arte ANEXO A ESTADO DEL ARTE A.1. Introducción En la actualidad existe un gran interés en aplicar innovaciones tecnológicas en el ámbito deportivo, con varios objetivos, como son el que pueda aumentar el rendimiento de los deportistas(como realizar mejor un movimiento para obtener mejores resultados), el estudio de tácticas por parte de los equipos o el estudio de estadísticas y/o eventos por parte de los entes televisivos(de forma que puedan aportar información extra a los telespectadores). Para ello podemos usar técnicas de Visión por Computador. En nuestro caso vamos a aplicarlas en el deporte del futbol, aunque sabemos que el uso de dichas técnicas está presente en otros deportes como: Baloncesto, Hockey hielo, béisbol, tennis, golf, billar, patinaje, etc. Actualmente se trabaja con sistemas completos de detección y seguimiento de jugadores de futbol que son capaces de detectar, clasificar y seguir a los jugadores; de manera que al final puedan obtener la trayectoria individual de cada uno. También existen sistemas completos que nos permiten analizar partidos enteros de manera que se puedan obtener estadísticas y detectar eventos de la forma más automática posible. A.2. Detección A.2.1. Detección de movimiento Una de las opciones posibles para poder detectar personas a lo largo de una sucesión de imágenes es la detección previa de movimiento en dicha imagen. Cuando se trabaja con cámaras fijas, uno de los métodos más utilizados es el de la sustracción de la imagen respecto al fondo. Sea Itla imagen en el instante actual t y Bt−1el fondo calculado en el instante anterior, serán detectados como movimiento aquellos puntos en los que su diferencia supere un umbral T: It(x, y)−Bt−1(x, y)> T (A.1) Siendo x,y: coordenadas de la imagen. 57 Anexo A Existen varias formas de modelar el fondo: - A partir de la media. - A partir de la mediana. - A partir del histograma de una serie de fotogramas de entrenamiento. Posteriormente se pueden aplicar distintos tipos de filtrados a dicha detección, de manera que se pueda incluir la información de la vecindad de los píxeles y reducir la influencia del ruido. De esta forma se puede mejorar el resultado final. La sustracción de la imagen respecto del fondo es un método con el que podemos obtener las regiones de movimiento no sólo en entornos controlados, sino también en entornos complejos como escenarios con niebla o nieve [2]. Algunos autores intentan detectar las distintas partes de las personas detectadas a partir de un análisis del contorno de la detección [3]. Otros autores proponen como mejora la creación de un doble fondo, de manera que uno actúe a corto plazo y el otro actúe a largo plazo [4]. De este modo, el fondo a corto plazo detectará los objetos/figuras que se están moviendo en ese momento, mientras que el fondo a largo plazo detectará aquellos objetos/figuras que han efectuado un movimiento previo pero que en el momento actual se encuentran estáticos. Independientemente de la forma en que hayamos calculado el fondo, los métodos de detección de movimiento suelen seguir una estructura de este tipo: 1. Modelar el fondo. 2. Inicializar el fondo (Calcular el fondo usando los fotogramas de entrenamiento que deseemos). 3. Mantener el fondo (Adaptarlo a los cambios que haya podido sufrir. Para ello se suele recalcular cada cierto tiempo). 4. Detectar figuras 5. Extraer características de las figuras A.2.2. Segmentación de la imagen Una vez se realiza la detección de movimiento puede ser conveniente realizar una segmentación de la figura que se ha detectado como movimiento. La segmentación de color de una imagen es la división de dicha imagen en regiones de colores homogéneos. Los métodos de segmentación más utilizados pueden dividirse en los siguientes grupos: 58 Estado del Arte - Umbralización de histogramas. - Agrupamiento. - Crecimiento de regiones. - Detectores de bordes. - Modelos físicos. - Redes neuronales. - Mezcla de distribuciones. - Métodos borrosos. A.2.3. Clasificación de figuras Por último se etiquetan manualmente algunos ejemplos de figuras, los cuáles serán usados como plantillas. Las nuevas figuras que detectemos serán comparadas con dichas plantillas, de manera que podamos detectar su identidad(en este caso el equipo al que pertenece dicha figura). Algunos autores usan múltiples observaciones en las que se integran varias características para aumentar la fiabilidad de este método [5]. Otros autores lo que hacen es crear un patrón a partir de varias observaciones [6]. A.3. Seguimiento Actualmente existe un gran número de algoritmos de seguimiento. En nuestro caso nos centraremos en los dos grupos más importantes: los de tipo Kalman y los de tipo Monte Carlo. A.3.1. Algoritmos de seguimiento tipo Kalman El Filtro de Kalman [9] es un algoritmo de seguimiento de tipo recursivo que se divide en dos pasos: 1. Predicción de la posición de los objetos que están en movimento. 2. Comparación de la predicción con las medidas obtenidas en la detección(si las hay) y obtención de la estimación de estado para cada tracker. En caso de no existir medidas que puedan provenir de un tracker se tomará como estimación a la posición de su predicción. 59 Anexo A El filtro de Kalman original presenta el inconveniente de que solo es capaz de estimar de forma correcta las posiciones en sistemas lineales y gaussianos. Debido a esto, se han desarrollado modificaciones de dicho filtro. Las modificaciones más conocidas son: - Extended Kalman Filter (EKF): [10] En dicho algoritmo se aproxima la distribución de estado por una variable aleatoria gaussiana, la cuál se propaga a través un sistema no lineal de primer orden. Los errores que introduce pueden hacer que el filtro diverja en caso de que el sistema no sea lo suficientemente lineal. - Unscented Kalman Filter (UKF): [11] En dicho algoritmo también se aproxima la distribución de estado por una v.a. gaussiana, solo que en este caso se representa por un conjunto de puntos determinados(los cuáles serán calculados préviamente), llamados puntos sigma. Estos puntos disponen de la media y la covarianza de la distribución gaussiana; y cuando se propagan a través de un sistema no lineal, capturan la media y la covarianza hasta el tercer orden. Si deseamos realizar el seguimiento de varios objetos a la vez(seguimiento multiobjeto), la complejidad de estos algoritmos residirá en la asociación que se debe de realizar entre las medidas obtenidas para dichos objetos y su posición estimada. A.3.2. Algoritmos de seguimiento tipo Monte Carlo El algoritmo de seguimiento tipo Montecarlo, también conocido como Filtro de Partículas(Particle Filter,PC) [12], se basa en un muestreo de las distribuciones. Tiene la ventaja de poder realizar el seguimiento con modelos no lineales y/o no gaussianos, representando la densidad de probabilidad mediante un conjunto de puntos(en el que se introduce un cierto nivel de aleatoriedad), el cuál evoluciona según lo hace la imagen de probabilidad. En lugar de usar medidas discretas como datos de entrada, usaremos imágenes de probabilidad. La complejidad de estos algoritmos reside en cómo obtener el peso de cada una de las partículas y en cómo realizar la evolución de las muestras usadas en un instante de tiempo para dar lugar a las muestras que van a ser usadas en el instante posterior. Uno de los métodos más utilizados es el Sample Importance Resampling (SIR); el cuál da lugar al algoritmo de Condensación y consiste en tres pasos: 1. Generación de partículas a partir de una función de importancia. 2. Cálculo de pesos. 3. Remuestreo eliminando las partículas con pesos bajos. 60 Estado del Arte Este algoritmo dispone de un inconveniente como es el tiempo de cómputo, ya que es mayor que con otros algoritmos de seguimiento. Por lo tanto será conveniente trabajar con arquitecturas en paralelo para poder trabajar de la forma más cercana al tiempo real. Por otra parte, si deseamos realizar un seguimiento multiobjeto mediante este tipo de algoritmos, existirán bastantes complejidades, sobre todo si las imágenes de probabilidad son ruidosas, de manera que puedan hacer que los trackers abandonen su trayectoria correcta. No obstante han sido creados diversos sistemas basados en el Filtro de Partículas, los cuáles son capaces de realizar esta tarea de una manera lo más eficiente posible. A.3.3. Algoritmos multihipótesis Además de los dos grupos de algoritmos mencionados anteriormente, los cuáles pueden ser usados para realizar un seguimiento multiobjeto, caben destacar los algoritmos de seguimiento multihipótesis(Múltiple Hypothesis Tracking, MHT). En este tipo de algoritmos, en caso de duda a la hora de asociar las medidas con los objetos a seguir, se pospone la decisión, creando de tal manera un árbol de hipótesis en el cuál se van calculando las probabilidades a posteriori. Cuando dichas probabilidades son lo suficientemente altas se toma la decisión. Cada rama del árbol se trata como si fuera un tracker distinto. De tal manera se deberían poder alcanzar buenos resultados en un entorno con medidas falsas. El mayor inconveniente de este algoritmo es que el número de hipótesis con los que se trabaja suele crecer rápidamente, de manera que es necesario usar técnicas de podado de hipótesis(prunning) que vayan eliminando las menos probables. Aun así, es bastante complejo realizar una buena poda de hipótesis, de manera que el problema pueda ser tratable computacionalmente y que a la vez no se descarten hipótesis válidas. A su vez resulta compleja la asociación entre medidas e hipótesis cuando el número de hipótesis es elevado. Algunos algoritmos multihipótesis utilizan el algoritmo de Viterbi para obtener las asociaciones de medidas. En dicho algoritmo, a partir de los diagramas de trellis, se puede calcular el camino de mayor probabilidad. Otros algoritmos multihipótesis se basan en un modelo probabilístico, como el algoritmo PMHT [19]. A.3.4. Algoritmos multisensor Para poder cubrir todo el escenario con poca distorsión y mejorar la resolución de las oclusiones y los cruces se puede trabajar con diversos sensores a la vez. En este trabajo usaremos tres sensores a la 61 Anexo A vez(en nuestro caso, serán cámaras), de manera que siempre exista una zona de solapamiento común entre las zonas de visión de dichas cámaras. Cada zona del campo de futbol al menos estará cubierta por dos cámaras. Una vez dispongamos de las medidas en la imagen de cada cámara, habrá que pasar dichas medidas a un plano común mediante una transformación proyectiva. De tal manera, podemos observar algunos trabajos en los que se logra obtener una mayor tasa de acierto en la resolución de cruces y oclusiones respecto a usar una sola cámara [7]. Algunos trabajos previos explican el método usado para trasladar las posiciones de los jugadores detectados en diferentes cámaras a un plano común [8]. Existen algoritmos que usan la información de varias cámaras los cuáles están basados en el filtro de partículas. Dichos algoritmos son capaces de obtener mejores resultados en el caso de oclusiones; pero a cambio, el dedicar un filtro de partículas a cada objeto de cada cámara resulta muy costoso. En el caso de realizar un seguimiento multiobjeto con varios sensores el problema de asociación de datos se complica aún más, debido a que existe un mayor número de interacciones entre los diferentes objetivos a seguir. Esto será más grave cuando dichos objetivos sean muy parecidos, como ocurre en el caso de jugadores de futbol del mismo equipo. A.3.5. Algoritmos de seguimiento sin detección previa Existen diversos algoritmos de seguimiento los cuáles no están basados en una detección previa, sino que realizan el seguimiento de objetos a partir de estadísticas obtenidas directamente de la imagen o a partir de los valores de los píxeles de la misma. El algoritmo mean-shift se basa en el reconocimiento de patrones en la imagen. En dicho algoritmo se pretende localizar los mínimos de diferencia de histograma entre un patrón de entrada y la imagen. Las funciones de similitud de histograma más usadas son el coeficiente de Bhattacharya o la divergencia de Kullback-Leibler. También existen otros algoritmos de seguimiento los cuáles tienen como entrada la segmentación de la imagen, ya que la segmentación no llega a ser considerada como detección en sí. En ocasiones se diseña a la vez la segmentación y el seguimiento, bien sea la segmentación basada en color y en textura o solo en color. 62 Sistema de Detección Figura B.7: Detección de movimiento tras el segundo filtrado aplicado a la imagen de la figura B.6. Figura B.8: Umbralización de la imagen para tres umbrales diferentes(de izd.a a dcha, de menor a mayor umbral. 69 Anexo B tiempo real” para compararlos con las figuras en movimiento que existan en la imagen. Deberá haber al menos tres tipos de patrones: uno por jugadores de campo de cada equipo y otro para el resto de las figuras que puedan aparecer(como el árbitro o los porteros). Si queremos distinguir a los porteros y al árbitro deberemos disponer al menos de cinco patrones. B.3.2. Agrupamiento de colores Introducción Realizaremos un agrupamiento de colores(a partir de un algoritmo de k-medias) para reducir la complejidad de la información asociada a los jugadores detectados, de manera que los modelos obtenidos sean más simples. Reduciendo el número de colores eliminaremos parte de la aleatoriedad y el ruido de color presente en las figuras, haciendo que los jugadores del mismo equipo sean más parecidos entre sí. Inicialización de los centroides En un principio deberemos de inicializar el algoritmo de k-medias, en nuestro caso situaremos los centroides iniciales en los puntos del espacio de color RGB en los que haya mayor frecuencia de color. Para ello comenzaremos calculando un histograma 3D de los píxeles de las zonas de movimiento que han sido detectadas, tal y como podemos ver en la Figura B.9 (utilizaremos los 4 ó 5 bits más significativos de cada canal de color para crear las categorías del histograma). Antes de aplicar el algoritmo de agrupamiento se deberán de definir dos parámetros: el número máximo de centroides y la distancia mínima entre ellos. En la inicialización se comenzará asignando un centroide al punto en el que se registre el máximo del histograma; es decir, el color que se repite con más frecuencia. El siguiente centroide se asignará al punto con el siguiente valor máximo(siempre y cuando esté a una distancia mayor a la distancia mínima definida del primer centroide). Este proceso se repetirá de forma iterativa hasta que no quedan más centroides por colocar ó hasta que no haya más puntos con valor positivo del histograma fuera del área de acción de cada centroide. Podemos ver gráficamente este proceso en la Figura B.10. 70 Sistema de Detección Figura B.9: Histograma 3D de los píxeles de las figuras que han sido detectadas como movimiento. Puesto que se han utilizado 5 bits para cada canal de color, se representarán los 32 histogramas 2D de las componentes R-G para cada uno de los 32 valores de B, yendo de izda. a dcha. y de arriba a abajo conforme crece su valor Figura B.10: Muestra de la evolución del algoritmo de inicialización de los centroides. La zona superior muestra la zona ocupada por cada centroide en el espacio de color RGB y la fila inferior muestra el histograma una vez que se han borrado las zonas asignadas. De izquierda a derecha vemos como va evolucionando la inicialización para la primera, la segunda y la última iteración 71 Anexo B Aplicación del algoritmo de k-medias(primer agrupamiento o clusterización) Una vez hemos incializado los centroides se aplicará el algoritmo de agrupamiento de k-medias, el cuál sigue estos pasos: - Asignación: Se asigna cada elemento al clúster cuya media esté más cercana a dicho elemento. - Actualización: Se calculan las nuevas medias a partir de los elementos asignados a cada clúster. Además se han introducido dos modificaciones: - La primera se basa en usar una distancia máxima de pertenencia al clúster, de manera que los elementos cuyo centroide más cercano esté más lejos de dicha distancia, quedarán sin asignar a ningún cluster. - La segunda se trata de una modificación en el cálculo de la actualización, en la que se hará una media ponderada de los píxeles que haya en cada categoría del histograma. La inicialización de las medias, según el método propuesto, obtiene por sí misma unos resultados bastante aceptables de clusterización, de manera que las medias de los grupos no suelen moverse mucho durante el proceso de clusterización de su posición inicial, tal y como podemos ver en la Figura B.11. Si han quedado zonas en el histograma con un valor positivo pero que no estén incluidas en ninguno de los clústeres, es posible incluir un cluster adicional. De tal modo podremos distinguir los colores que están fuera de los clústeres pero que han aparecido en la secuencia de imágenes de entrenamiento (colores minoritarios), respecto de los colores que son nuevos(probablemente ruido o distorsión). Para que la implementación de la segmentación sea rápida usaremos una Look-up table(LUT). Es recomendable que se use la misma LUT para el segundo filtrado de la detección de movimiento y para la segmentación. Aplicación de un segundo agrupamiento Mediante la clusterización por color hemos conseguido agrupar colores parecidos, de manera que si aparecen variantes de estos colores en las imágenes, seamos capaces de identificarlos. Aun así puede ocurrir que las equipaciones estén formadas por varios colores o que las variantes de un mismo color se hayan agrupado como clústeres diferentes. Por lo tanto, es interesante realizar una segunda clusterización, de manera que se unan los clústeres de colores que habitualmente aparezcan juntos; es decir, cuando exista bastante correlación entre los píxeles que hay en dos clústeres que se encuentren en el mismo blob. 72 Sistema de Detección Figura B.11: Trayectoria seguida en el espacio de color RGB por las medias desde su inicialización hasta la última iteración. Figura B.12: Representación gráfica de los clústers antes y después de la aplicación del segundo agrupamiento. De tal forma uniremos aquellos clústeres en los que su función de correlación supere un cierto umbral. Para obtener dicha función de correlación, cada clúster se considerará como una señal discreta cuyo valor en la posición i será el número de píxeles de ese clúster presentes en el blob i. De tal manera se conseguirán mejores resultados en la clasificación de jugadores y además disminuirá el tiempo de cómputo en el modo “funcionamiento en tiempo real”. Podemos ver un ejemplo de como ha funcionado esta segunda clusterización respecto a la inicial en la Figura B.12. 73 Anexo B Figura B.13: Ejemplo de división de un blob en varias capas. B.3.3. Creación del modelo Una vez las figuras en movimiento han sido detectadas deberemos de crear un modelo para cada jugador. Buscamos que dicho modelo sea representado por la menor cantidad de datos posible de forma que se disminuya el tiempo de cómputo y se aumente la efectividad de la identificación. De todos los modelos que se han probado el que mejores resultados ha dado ha sido uno que está basado en histogramas verticales. Considerando que la información horizontal de los colores de los jugadores es poco importante, este método consigue precísamente reducir la cantidad de información de forma que disminuye el tiempo de cómputo y se aumenta la fiabilidad en la identificación. En el modo “entrenamiento” el modelo de cada blob se normalizará a un tamaño estándar, de forma que se puedan comparar modelos de jugadores entre sí de una forma más rápida. La obtención del modelo de cada jugador basado en histogramas verticales se divide en 3 fases: 1. En primer lugar, el blob obtenido para cada jugador se dividirá en varias capas, una por cada clúster que contenga dicho blob. De tal forma cada capa podrá ser procesada por separado. Podemos ver un ejemplo en la Figura B.13. 2. En segundo lugar obtendremos los histogramas verticales, creando uno de ellos por cada capa de cada jugador. 3. Por último, se realizará una normalización de dichos histogramas(ver Figura B.14) . En primer lugar serán filtrados para reducir el ruido y la aleatoriedad. Finalmente se remuestrearán para obtener un número fijo de posiciones para cada histograma. De tal manera, podremos representar los modelos de los jugadores como una matriz, tal y como se puede ver en la Figura B.15. 74 Sistema de Detección Figura B.14: Obtención del histograma vertical, filtrado y remuestreo para cada una de las capas de la imagen para el blob de la figuraB.13. Figura B.15: Matriz que representa el modelo de un jugador asociado al histograma vertical de la figuraB.14. 75 Anexo B B.4. Identificación de los jugadores Una vez ha sido realizada la detección de movimiento y la segmentación y hayamos obtenido los diferentes modelos deberemos obtener los patrones que después serán usados en el modo “funcionamiento en tiempo real”. Definiremos patrón como un modelo el cuál es representativo respecto a un grupo de modelos. Para obtener los patrones usaremos un algoritmo de agupamiento jerárquico; el cuál se dividirá en 3 pasos: 1. En primer lugar calcularemos la distancia dos a dos entre cada par de modelos de jugadores. Para ello calcularemos cuál es su similitud, S: S=X iX j min(A(i, j), B(i, j)) X iX j max(A(i, j), B(i, j)) (B.2) donde: A,B: son las matrices asociadas a los modelos a comparar. i,j: son los elementos de las matrices. Cuanto más próximo a 1 sea el valor de la similitud, más parecidos serán entre sí los modelos a comparar; y cuanto más próximo a 0 sea el valor de la similitud, menos parecidos serán entre sí los modelos a comparar. Podemos ver una muestra de esta función en la Figura B.16 2. Para los dos jugadores más cercanos calcularemos su media. Si esta distancia es superior a un umbral, el algoritmo de agrupamiento habrá finalizado. Dados 2 modelos de jugadores, atendiendo a sus matrices A y B, la media de ambas matrices M, se definirá como la media elemento a elemento de ambas M = (A+B)/2. 3. Finalmente borraremos a ambos jugadores de la lista, incluiremos su media y volveremos al primer paso. La mayor complejidad de este algoritmo es saber cúando ha de terminarse el agrupamiento; es decir, establecer un límite a partir del cuál no deberían seguir fusionándose más modelos de jugadores(ver cuándo los jugadores que se están fusionando comienzan a ser demasiado diferentes entre sí). Podremos realizarlo de forma manual, según el criterio del ojo humano, o de forma automática, tal y como se explicará más adelante. No resulta sencillo conocer cuál es el valor del umbral de diferencia entre dos patrones como criterio de parada porque estas diferencias son variables y pueden depender de los colores de los uniformes, de las condiciones de iluminación o de la posición de las cámaras. De tal manera, el umbral que podría ser válido en un partido no tendría por qué serlo en otro. 76 Sistema de Detección Figura B.16: Ejemplo de una comparación entre dos modelos. Una posible solución es realizar un agrupamiento completo hasta que solo quede un clúster, habiendo guardado el número de modelos fusionados en cada clúster a lo largo de cada iteración. Con estas estadísticas es posible encontrar un punto de parada y volver a utilizar el algoritmo de agrupamiento desde el principio hasta ese punto. Tomaremos un número de patrones posibles superior al número de patrones deseado. De esta manera tendremos un cierto margen de maniobra y podremos seleccionar entre los obtenidos de forma automática, los más apropiados. La ventaja de este método es que no tenemos por qué seleccionar los grupos de modelos de jugador con más muestras, ya que los más interesantes no son siempre los que más muestras tienen. En el caso de los modelos de porteros o de árbitros éstos pueden tener una mayor importancia pero un número de muestras inferior. Una vez que se hayan seleccionado los mejores grupos de modelos, habrá que decidir como obtener el patrón a partir de dichos grupos. En un principio existen dos posibildades: Usar la media de los modelos de cada grupo para obtener los patrones que se vayan a usar. Seleccionar uno de los modelos de cada grupo el cuál sea representativo del grupo, de forma que sea tomado como patrón de dicho grupo. En la práctica no se ha podido determinar cuál de los dos modelos es más fiable, ya que cada uno de los modelos tiene ventajas o inconvenientes dependiendo de la situación. Esta fase puede hacerse de forma automática;no obstante, es recomendable que sea supervisada por un operador humano. Dicha persona se encargará de ver si los patrones elegidos han sido clasificados de forma correcta y en caso contrario corregirlos. Podemos ver un ejemplo de esta clasificación a supervisar en la Figura B.17. En dicha clasificación se puede observar como uno de los patrones obtenidos para el equipo 1 es en realidad el de un entrenador. Dicho entrenador ha sido clasificado 77 Anexo B Figura B.17: Ejemplo de obtención y clasificación automática de patrones antes de realizar la supervisión. como si perteneciese al equipo 1, debido a que viste con colores parecidos. También podemos observar que los jugadores que se han convertido en patrón parecen disponer de diferentes posiciones relativas a la cámara. Esto se debe a que es más sencillo que los jugadores que estén en las mismas posiciones tengan mayor similitud; y por lo tanto, se agrupen más fácilmente en el mismo grupo. B.5. Modo “funcionamiento en tiempo real” Una vez se ha obtenido la ROI, el fondo y los patrones en el modo “entrenamiento”, éstos serán los pasos a seguir en el modo “funcionamiento en tiempo real”: 1. Detección de movimiento basado en la resta respecto del fondo y primer filtrado. 2. Aplicación de la LUT para el segundo filtrado y la segmentación(clusterización de colores). 3. Creación de modelos para cada uno de los blobs que hayan sido detectados. 4. Comparación de los modelos con los patrones y clasificación de los mismos. Para obtener un tiempo de ejecución menor en el modo “funcionamiento en tiempo real”, un buen método (si se dispone de memoria suficiente) será el de precalcular la clusterización para cada uno de los posibles colores y anotar los resultados en una tabla a la que llamamos Look-Up table(LUT). Esto se debe a que el tiempo de acceso a memoria suele ser muy inferior al tiempo de cómputo. 78 Sistema de Seguimiento C.2.4. Pruebas realizadas Mediante las pruebas que fueron realizadas en [1](Capítulo 4.2.4) se consiguió comparar el rendimiento de un tracker en el suelo con respecto a un tracker en la imagen. Se compararon dos trackers que usaron el algoritmo de Kalman con el mismo modelo de velocidad constante, de forma que cada uno de ellos tenía un ajuste de parámetros diferente pero equivalente(ya que no podemos comparar de forma directa los parámetros en la imagen y en el plano del suelo, puesto que sus magnitudes vienen expresadas en distintas unidades). Para ello fueron realizadas tres pruebas en las que se comprobó la precisión de las predicciones de ambos trackers para una secuencia de 550 fotogramas grabada con una cámara fija a una altura de unos 2,50 metros. El objetivo era el de seguir un coche teledirigido que se movía a lo largo de un pasillo, alejándose de la cámara, a una velocidad aproximadamente constante. Una vez se obtuvo la posición del coche mediante el algoritmo de detección en cada fotograma, se aplicó un filtro de Kalman para realizar el seguimiento. La homografía; la cuál fue calculada previamente tal y como se explicó anteriormente, nos permitió obtener los puntos del plano asociados a cada punto de la imagen. De tal manera se pudo seguir al mismo objeto con trackers que trabajaban de forma independiente. Para comparar el rendimiento de ambos trackers se calculó la distancia media entre los puntos predichos por los trackers y las medidas asociadas, ya que aunque siempre habrá una diferencia, está será menor cuanto mejores sean las predicciones del tracker. En un principio se puede pensar que para medir el error cometido sería más fiable calcular la distancia entre la posición real del objeto móvil y las estimaciones de posición de los trackers; pero existen varios problemas, ya que las estimaciones calculadas a partir de las medidas y la predicción no estarán siempre disponibles; y las posiciones reales de los objetos en movimiento no se conocen. Las comparaciones entre las predicciones y las medidas actuales se realizaron en tres niveles de tiempo: Corto plazo: En este caso se fue comparando la precisión de las predicciones entre fotogramas consecutivos. Las distancias medias obtenidas entre las medidas y las predicciones se pueden ver en la Figura C.2. Tanto las distancias de los trackers en el suelo como las de los trackers en la imagen fueron medidas en el suelo, usando el milímetro como unidad de distancia para poder compararlas de forma directa. Estas distancias fueron calculadas mediante el uso de la distancia euclidea. Podremos ver las distancias obtenidas entre las predicciones y las medidas en la FiguraC.3. Tal y como se puede ver en dicha figura el seguimiento en el plano del suelo obtiene mejores resultados que el seguimiento en la imagen. Comparativamente, se puede ver que el tracker del plano del 85 Anexo C Figura C.2: Distancias medias(en milímetros) entre las predicciones y las medidas para el tracker en la imagen y el tracker en el suelo para fotogramas consecutivos. Figura C.3: Distancia obtenida entre predicciones y medidas para ambos trackers(el tracker en el suelo corresponde a la línea oscura y el tracker en la imagen corresponde a la línea clara) suelo obtiene mejores resultados que el de la imagen si el objeto está cerca de la cámara, ya que en ese intervalo temporal la variabilidad de la velocidad del objeto en la imagen suele ser mayor(es decir, el objeto se mueve en cada fotograma un número mayor de píxeles). Cuando el objeto está lejos de la cámara el tracker del plano del suelo sigue obteniendo mejores resultados que el de la imagen, pero comparativamente la diferencia es bastante menor. Medio plazo: En el segundo caso, usando la misma secuencia, se realizó una decimación del número de medidas usadas, de manera que se obtuvieron 550/f medidas (donde f es el factor de decimación). Se usaron las mismas matrices de ruido de estado y medida que en el caso de Corto plazo. Las distancias medias obtenidas entre las medidas y las predicciones se pueden ver, para distintos valores de decimación, en la Figura C.4. Podemos observar que la distancia media aumenta conforme se incrementa el valor del factor de decimación, ya que el movimiento del objeto se hace menos predecible. Además de ver que el error es menor en el caso del tracker del suelo respecto al tracker de la imagen, podemos observar que conforme aumenta el factor de decimación el aumento proporcional del error es menor en el caso del tracker del suelo. Largo plazo: Por último se realizó una simulación de oclusión o pérdida del objeto movil durante un gran 86 Sistema de Seguimiento Figura C.4: Distancias medias(en milímetros) entre las predicciones y las medidas para el tracker en la imagen y el tracker en el suelo tras aplicacr diferentes factores de decimación f. Figura C.5: Distancia obtenida entre predicciones y medidas para ambos trackers en el momento que aparece la primera medida después de eliminar un conjunto de medidas consecutivas(los ejes están representados en escala logarítmica) período de tiempo; es decir, usando la misma secuencia de fotogramas se eliminó un gran número de fotogramas consecutivos para ambos trackers. En este caso también se usó la misma configuración para ambos trackers respecto a las dos pruebas anteriores. Se realizaron diferentes test en los que el número de medidas borradas de forma consecutiva varió entre 2 y 100. Se tomó como referencia la distancia existente entre la predicción y la primera medida que hubiera a continuación del conjunto de medidas borradas(aunque no fuera emparejada de forma correcta con el tracker). Con la configuración usada se puede apreciar como el tracker del suelo no pierde el objetivo incluso después de 100 fotogramas, ya que la trayectoria seguida es bastante lineal; sin embargo, el tracker de la imagen pierde al objeto depués de oclusiones de un número de fotogramas igual o mayor a 10. Podemos ver una muestra de las distancias obtenidas en la Figura C.5 87 Anexo C C.3. Algoritmo de seguimiento MSUKF C.3.1. Introducción Nuestros algoritmos de seguimiento se van basar en el filtro de Kalman [17], un algoritmo sencillo y rápido comparado con otros algoritmos de seguimiento. Dicho algoritmo solo es capaz de funcionar con modelos lineales y gaussianos; no obstante, existen versiones de este algoritmo que sí son capaces de trabajar con modelos no lineales ni gaussianos. Actualmente existe un algoritmo, en concreto, el cuál es capaz de tratar con modelos de este tipo de manera eficiente y con un coste computacional no muy alto. Dicho algoritmo de seguimiento es el llamado Unscented Kalman Filter(UKF). En nuestro caso buscamos trabajar con sistemas multisensor(en este caso sistemas multicámara), de manera que dispongamos de varias cámaras en las que la información procesada por cada una de ellas sea tratada en conjunto con la información del resto de las camáras; ya que se obtienen mejores resultados de esta forma respecto a usar varios filtros UKF independientes(uno para las medidas de cada cámara). En nuestro caso dispondremos de 3 cámaras, de forma que cada una cubra una zona distinta del campo. Aun así podrá haber solapamientos entre las áreas de visión de las cámaras, de manera que haya momentos en los que podamos tener medidas en distintas cámaras para el mismo jugador a la vez. En primer lugar, deberemos crear una referencia común para poder integrar las medidas de las distintas cámaras, tal y como se explica en el apartado B.2.2. Para ello deberemos de calcular préviamente las matrices de homografía para cada cámara. Tras esto obtendremos las posiciones puntuales de cada jugador -a partir del sistema de detección y clasificación el cuál se ha descrito en el Anexo B -para cada cámara y pasaremos las medidas obtenidasmediante su transformación proyectivaal plano común. Una vez disponemos de las medidas en el plano común, alimentaremos con éstas a nuestro algoritmo de seguimiento. C.3.2. Unscented Kalman Filter(UKF) Comenzaremos hablando del algoritmo de seguimiento UKF, puesto que nuestro sistema de seguimiento se va ha basar en dicho algoritmo. En un principio definiremos los términos de estado y covarianza. El estado indica, en nuestro caso, la posición media en la que se detecta al jugador en el campo de futbol; y la covarianza indica la variabilidad respecto a dicha posición media, en la que el jugador se puede encontrar. Si la covarianza aumenta significa que la medida es más mala que buena; y por tanto existirá una variabilidad alta respecto a la posición media. Llamaremos estado extendido y covarianza extendida a la concatenación de dichos estados y 88 Sistema de Seguimiento covarianzas con las variables de ruido: xa k= [xT kvT knT k](C.3) Pa k=     Pk0 0 0Rv0 0 0 Rn      (C.4) siendo: Rv: matriz de ruido de estado. Rn: matriz de ruido de medida. El UKF original se divide en tres etapas: 1. Inicialización de los estados y las covarianzas. 2. Fase de predicción de estado y medida: Es similar a la fase de predicción del filtro de Kalman. ˆx− k=F(xk, uk, vk)(C.5) ˆy− k=H(xk, nk)(C.6) siendo: xk: Estado en el instante de tiempo k(no observable directamente). yk: Medida observada en el instante de tiempo k. ˆx− k: Predicción de estado en el instante de tiempo k. ˆy− k: Predicción de medida en el instante de tiempo k. uk: Datos observados externamentete en el instante de tiempo k. vk: Ruido de estado en el instante k. nk: Ruido de medida en el instante k. F: Modelo dinámico. H: Matriz de relación estado-medida. 3. Fase de estimación de estado: ˆxk= ˆx− k+Kk(yk−ˆy− k)(C.7) ˆ Pk=ˆ P− k−(KkPykykKT k)(C.8) siendo: ˆx− k: Predicción de estado en el instante de tiempo k. ˆxk: Estimación de estado en el instante de tiempo k. ˆ P− k: Predicción de covarianza en el instante de tiempo k. ˆ Pk: Estimación de covarianza en el instante de tiempo k. ˆy− k: Predicción de medida en el instante de tiempo k. Kk: Ganancia de Kalman en el instante de tiempo k. 89 Anexo C La ganancia de Kalman podrá ser calculada de esta manera: Kk=PxkykP−1 ykyk (C.9) donde: Pykyk: Covarianza de medida Pxkyk: Covarianza de medida condicionada al estado. A su vez Pykyk yPykyk son calculadas en el filtro UKF usando puntos sigma. Los puntos sigma son el menor conjunto posible de puntos cuya media y covarianza es la misma que la del estado. Para un estado con n componentes serán necesarios 2n+1 puntos sigma. Por tanto, la media y la covarianza de los puntos sigma, una vez apliquemos el modelo dinámico, representarán la media y la covarianza de estado, con la ventaja de poder usar modelos dinámicos no lineales. C.3.3. Multi Sensor Unscented Kalman Filter(MSUKF) En el sistema utilizado dispondremos de la visión de al menos dos cámaras por cada punto del campo, de manera que las medidas obtenidas en cada cámara serán combinadas para obtener una estimación por jugador. Llamaremos Multi Sensor Unscented Kalman Filter(MSUKF) a la modificación del algoritmo UKF que vamos a utilizar [18]. En este algoritmo de seguimiento dispondremos de 5 fases: 1. Inicialización de los estados y las covarianzas. 2. Fase de predicción de estado. 3. Emparejamiento de medidas con trackers. 4. Fase de predicción de medida. 5. Fase de estimación. Podemos ver un diagrama de bloques asociado a dicho algoritmo en la Figura C.6 Inicialización de los estados y las covarianzas En esta fase cada tracker se inicializa con el valor de la estimación calculada en la última iteración, o en caso de estar en el primer fotograma, con los valores asociados a las posiciones iniciales de los jugadores. 90 Sistema de Seguimiento Figura C.6: Diagrama de bloques del algoritmo MSUKF utilizado. Predicción de estado Si conocemos el estado previo ˆxk−1y su covarianza ˆ Pk−1, podremos calcular el estado extendido y la covarianza extendida concatenando la estimación previa con el ruido de estado. En esta fase tan solo se concatena el ruido de estado. El ruido de medida se concatenará posteriormente en la fase de predicción de medida, a diferencia del UKF; en el cuál se concatenan ambos a la vez. ˆxa k−1= [ˆxT k−1E[vk]]T, E[vk] = [0 . . . 0] (C.10) ˆ Pa k−1=  ˆ Pk−10 0Rv (C.11) Si disponemos de n componentes para el estado extendido, el número de puntos sigma χa k−1creados será de 2n+1. El primer punto sigma se corresponderá con la estimación del estado en el fotograma anterior. Los n puntos sigma siguientes serán la estimación del estado en el fotograma anterior más cada una de las columnas de la matriz de estimación y los últimos n puntos sigma serán la estimación del estado en el fotograma anterior menos cada una de las columnas de la matriz de estimación: ∆k=q(n+λ)ˆ Pa k−1(C.12) χa k−1= [ˆxa k−1ˆxa k−1+ ∆kˆxa k−1−∆k](C.13) Nuestra agrupación de puntos sigma puede dividirse en dos tipos: los que provienen del estado χx k−1y los que provienen del ruido de estado χv k−1. Los pesos asignados a cada punto sigma se calcularán de la misma manera que en la Unscented Transform, de manera que el peso 0 será calculado de forma diferente para las medias y las covarianzas: W(m) 0=λ/(n+λ) W(c) 0=λ/(n+λ) + (1 + α2+β) W(m) i=W(c) i= 1/[2(n+λ)] i= 1,2, . . . 2n (C.14) 91 Anexo C Figura C.7: Esquema gráfico en el que podemos ver la generación de puntos sigma a partir de la media y la covarianza del estado anterior, la predicción de los nuevos puntos sigma a partir de la matriz de transición y la recuperación de la media y la covarianza a partir de los nuevos puntos sigma Mediante la matriz de transición F podremos predecir el valor de los puntos sigma en el instante de tiempo k-ésimo: χx k|k−1=F·χx k−1+χv k−1(C.15) Dicha matriz será calculada a partir del modelo de predicción elegido. De tal forma, una vez disponemos de la predicción de los puntos sigma y de sus pesos, podremos calcular la predicción para cada estado de cada tracker (de la media y la covarianza) de esta manera: ˆxk|k−1= ˆx− k=F·ˆxk−1 ˆxk|k−1= 2n X i=0 W(m) iχx i,k|k−1 (C.16) ˆ Ex i,k =χx i,k|k−1−ˆxk|k−1(C.17) ˆ Pk|k−1= 2n X i=0 W(c) iEx i,k(Ex i,k)T(C.18) Podemos ver una representación gráfica de los pasos realizados en la predicción de estado en la Figura C.7 Emparejamiento Una vez disponemos de la la predicción de estado para cada tracker, deberemos asociar las medidas obtenidas mediante el algoritmo de detección con los trackers. Para ello nuestro sistema de asociación se basará en dos principios: - Asignar como máximo una medida a cada tracker (para cada cámara). 92 Sistema de Seguimiento - No asignar la misma medida a diferentes trackers. El método más sencillo y rápido sería el de asignar a cada tracker la medida más cercana, también conocido como Método del Vecino Más Cercano(Nearest Neighbor). Sin embargo, hemos preferido usar otro método, que aunque sea más lento obtiene mejores resultados. Dicho método consiste en minimizar la suma global de distancias entre trackers y medidas. Para que la cantidad de información a procesar sea menor (y por tanto el método no sea tan lento) utilizaremos la técnica del gating; la cuál consiste en crear una zona alrededor de cada tracker, llamada área de gating, de forma que las medidas que queden fuera de esa zona no serán tenidas en cuenta como candidatas a ese tracker. Para ello crearemos una lista con las posibles medidas para cada tracker, seleccionando aquellas cuya distancia de Mahalanobis respecto a la predicción de cada tracker sea menor que un umbral. Tras esto crearemos una tabla con todas las posibles combinaciones de asociación y escogeremos la combinación de medidas-predicciones cuya suma de distancias sea menor. Deberemos de considerar la medida nula dentro de la lista de posibles medidas para cada tracker, ya que es posible que la medida asignada a un tracker no sea ninguna de las que estén dentro de su área de gating, de manera que no sea posible hallar ninguna matriz de combinaciones que cumpla con las dos condiciones necesarias expuestas anteriormente. Como en esta fase no estamos aplicando ningún tipo de relación entre las medidas de cada cámara, el mismo proceso se aplicará de forma independiente para las medidas obtenidas en cada una de ellas. Predicción de medida Tras realizar el emparejamiento entre predicciones y medidas pasaremos a la fase de predicción de medidas. Calcularemos los estados y las covarianzas extendidas para cada par predicción-medida asociada concatenando los ruidos de medida. De esta forma, tanto los estados como las covarianzas extendidas no tendrán una dimensión fija, ya que dependerá del número de medidas que hayan quedado dentro del área de gating del tracker. ˆ x0a k= [ˆxk|k−10 0 . . .]T(C.19) ˆ P0a k=  ˆ Pk|k−10 0Rn (C.20) Rn=       Rn 10. . . 0 0Rn 2. . . 0 0 0 . . . 0 0 0 . . . Rn m        (C.21) 93 Anexo C Si disponemos de S medidas (provenientes cada una de un sensor diferente) para un tracker, dicho tracker tendrá un estado extendido con n’= 2S+4 componentes y se generarán 2n’+1 = 4S+9 puntos sigma. ∆0k=q(n0+λ0)ˆ P0a k(C.22) χ0a k−1= [ ˆ x0a kˆ x0a k+ ∆0kˆ x0a k−∆0k](C.23) cuyos pesos serán calculados de esta forma: W0(m) 0=λ0/(n0+λ0) W0(c) 0=λ0/(n0+λ0) + (1 + α02+β0) W0(m) i=W0(c) i= 1/[2(n0+λ0)] i= 1,2, . . . 2n0 (C.24) Nuestra agrupación de puntos sigma puede dividirse en dos tipos: los que provienen del estado χ0x ky los que provienen del ruido de medida χ0n k; los cuáles a su vez pueden ser diferenciados dependiendo de la medida que se ha usado para generarlos: χ0n(1) k,χ0n(2) k,...,χ0n(S) k. Mediante la matriz de relación estado-medida H, podremos obtener la predicción de medida de los puntos sigma: Y(s) k|k−1=H·χ0x k+χ0n(s) ks= 1,2, . . . , S (C.25) De esta manera, mediante estos nuevos puntos sigma, podremos hallar para cada medida la predicción de medida, la predicción de covarianza y la covarianza cruzada estado-medida: ˆyk|k−1= 2n0 X i=0 W0(m) iY(s) i,k|k−1(C.26) ˆ E0x(s) i,k =χ(s) i,k|k−1−ˆxk|k−1(C.27) ˆ Ey(s) i,k =Y(s) i,k|k−1−ˆyk|k−1(C.28) P(s) ˆykˆyk= 2n0 X i=0 W0(c) iEy(s) i,k (Ey(s) i,k )T(C.29) P(s) ˆxkˆyk= 2n0 X i=0 W0(c) iEx(s) i,k (Ey(s) i,k )T(C.30) Podemos ver una representación gráfica de los pasos realizados en la predicción de medida en la Figura C.8 Estimación Finálmente llegamos a la fase de estimación de estado. En un principio calcularemos la ganancia de Kalman para cada sensor que haya obtenido una medida asociada a alguno de los trackers: K(s) k=P(s) ˆxkˆyk/P(s) ˆykˆyk(C.31) 94 Sistema de Seguimiento combinaciones y en cada iteración se guardarán solo las mejores combinaciones. Calcularemos la suma de distancias de cada combinación, de manera que el resultado obtenido aunque no corresponda exáctamente con la probabilidad, será mucho más rápido de calcular. El resultado obtenido mediante este método, no obstante, será bastante parecido al obtenido calculando la probabilidad; sería bastante dificil que una combinación con la mejor probabilidad tuviera una suma de distancias demasiado grande. 3. Cálculo de la probabilidad a priori de cada combinación: Tras obtener la matriz de combinaciones, se realizará una selección final de las combinaciones que se van a tener en cuenta. Para ello se usará el criterio de la máxima probabilidad a priori para cada combinación Cw k,y. Dicha probabilidad se calculará como el producto de la probabilidad de cada cámara (βc,w i,k ), multiplicada por la probabilidad de la combinación de las ncmedidas de la fila rde la matriz Πw k(p(Πw k[1, ..., nc;r])); y multiplicada a la vez por la probabilidad de la hipótesis wen el instante anterior k−1 (p(Hw k−1)) desde la que se ha generado la hipótesis actual wen el instante actual k: p(Cw k,r) = p(Hw k−1)·p(Πw k[1, ..., nc;r]) ·Y b βc,w i,k (C.44) p(H1 0) = 1 (C.45) βc,w i,k =         ec,w i,k bc,w k+Pmc,w k j=1 i= 1, . . . , mc,w k bc,w i,k bc,w k+Pmc,w k j=1 i= 0 (C.46) ec,w i,k =e−1 2·(vc,w i,k )T·(Sw k)−1·vc,w i,k bc,w i,k = (2Π γ)nz 2mc,w kc−1 nz 1−Pc DPG Pc D (C.47) donde: βc,w 0,k : Probabilidad de que ninguna de las medidas dentro del área de gating sea la correcta para la hipótesis wen la cámara cen el instante temporal k. Pc D: Probabilidad de detección de la cámara c. PG: Probabilidad de gating. nz: Número de dimensiones de la medida c. cnz: Volumen de la hiperesfera unidad nz-dimensional. Habrá casos en los que un tracker no sea capaz de capturar medidas dentro de su área de gating. En tal caso se guiará por las predicciones realizadas mientras su covarianza crece, de manera que el área de búsqueda del jugador aumente en cada instante(ya que si el área de búsqueda del tracker fuera similar probablemente no volvería a encontrarlo). Al aumentar el área de gating, es posible que el tracker capture medidas de sensores distintos, de manera que estén demasiado alejadas entre sí. Para evitar este problema definiremos una función a la que denominaremos función de coherencia, la cuál será aplicada a cada combinación de medidas, de manera que 101 Anexo C Figura C.12: Ejemplo en el que tres medidas están individualmente a la misma distancia de un tracker en dos casos bien diferentes. En el caso de la izquierda las 3 medidas están alejadas entre sí; y sin embargo en el caso de la derecha están cercanas entre sí. Parece lógico pensar que en el caso de la derecha es más probable que las medidas provengan del mismo jugador, de modo que debería considerarse dicha hipótesis como más probable. multiplicará a la probabilidad calculada para cada combinación reduciendo dicha probabilidad en caso de que las medidas estén demasiado alejadas. Podemos ver un ejemplo de este tipo de problemas en la Figura C.12. 4. Generación de hipótesis: Una vez hayamos seleccionado las combinaciones de medidas que tengan una mayor probabilidad a priori(las cuáles han sido obtenidas a partir del conjunto de hipótesis Hw k−1en el instante k−1), dichas combinaciones se convertirán en las nuevas hipótesis Hw0 ken el instante k. El número de hipótesis generadas será mayor o igual al número de hipótesis de partida, ya que de cada hipótesis en el instante k−1siempre se generan una o más hipótesis en el instante k. Cada hipótesis estará representada por un vector de medidas, una de cada cámara, asociados a la r-ésima combinación de medidas: Cw k,r =zc,w i,k ≡zc,w0 k=Hw0 k(C.48) En las hipótesis generadas se mantendrán los valores de la predicción de estado, de medida, de covarianza de estado y de covarianza de medida (además de la innovación respecto de las medidas seleccionadas) respecto a las hipótesis de partida. ˆxw0 t k|k−1= ˆxwt k|k−1ˆzw0 t k|k−1= ˆzwt k|k−1 ˆ Pw0 t k|k−1=ˆ Pwt k|k−1ˆ Sw0 t k|k−1=ˆ Swt k|k−1vc,w0 t k=vc,wt k (C.49) 5. Renormalización conjunta de hipótesis: Finálmente renormalizaremos las nuevas hipótesis, ya que la que influencia mutua que ejercen unos trackers sobre otros podría hacer que varios trackers intentaran seguir al mismo objeto. Sino realizamos esta corrección es bastante probable que cada tracker acabe siguiendo a varios jugadores usando diferentes hipótesis para cada uno de ellos, de manera que permanezcan 102 Sistema de Seguimiento siguiéndolos a todos ellos por un tiempo indeterminado haciendo imposible la toma de decisión retardada. Otro caso indeseable que puede suceder, es que si se produce un cruce al final solo sobrevivan las hipótesis de ambos trackers las cuáles se dirijan al jugador con mejores medidas. Para evitar estos casos se creará un algoritmo el cuál rebaje las probabilidades de las hipótesis menos probables que siguen a medidas que otros trackers están siguiendo con hipótesis más probables. Para ello, en un principio calcularemos para cada tracker, la suma de las probabilidades de las hipótesis que usan cada una de las medidas, obteniendo para cada medida: Mj,k ={Mt j,k}=X w0 p(Hw0 k)∀zw0 k∈Hw0 k(C.50) Acto seguido, se calcularán las probabilidades para cada hipótesis, dividiéndolas por el mayor cociente, para cada una de sus medidas, entre la probabilidad de la hipótesis más probable para esa medida y su propia hipótesis. De esta manera la hipótesis de mayor probabilidad no modificará su valor y el resto disminuirán el suyo proporcionalmente a la diferencia de probabilidades. Por tanto, la nueva probabilidad de cada hipótesis será: p0(Hw0 k) = p(Hw0 k) m´ax zw0 k∈Hw0 k(m´ax t0{Mt0 j,k} Mt j,k )(C.51) Después de esto se eliminarán aquellas hipótesis cuya probabilidad esté por debajo de un umbral. En cualquier caso, la hipótesis de que ninguna de las medidas es correcta no deberá ser eliminada, aunque esté por debajo del umbral. Para seleccionar que hipótesis serán eliminadas calcularemos los coeficientes β0c,w0 k; los cuáles serán usados en la fase de estimación de estado como pesos: β0c,w0 k=ec,w0 X c ec,w0(C.52) Por último normalizaremos las probabilidades de las hipótesis de nuevo, teniendo en cuenta tan sólo las seleccionadas: p0N(Hw0 k) = p0(Hw0 k) X w0 p0(Hw0 k)(C.53) C.4.4. Estimación Una vez hayamos realizado la asociación de datos pasaremos a la fase de estimación. Para aquellas hipótesis en las que no ha sido asociada ninguna medida con el tracker, la estimación tanto de estado como de covarianza de estado, será igual a la predicción: ˆxw0 k= ˆxw0 k|k−1ˆ Pw0 k=ˆ Pw0 k|k−1(C.54) 103 Anexo C Para el resto de las hipótesis la estimación será calculada a partir de la predicción y de las medidas que hayan sido asociadas. En primer lugar se calculará la ganancia: Gw0 k=ˆ Pw0 k·HT·(Sw0 k)−1(C.55) Por otra parte, la innovación total será igual a la suma de innovaciones de cada cámara ponderadas por los pesos que hemos calculado anteriormente: ˆvw0 k=X c β0c,w0 k·ˆvc,w0 k(C.56) Finálmente, podremos calcular la estimación de estado y covarianza de esta manera: ˆxw0 k= ˆxw0 k|k−1+Gw0 k·vc,w0 k ˆ Pw0 k=ˆ Pw0 k|k−1−Gw0 k·Sw0 k·(Gw0 k)T+˜ Pw0 k (C.57) Llamaremos dispersión de las innovaciones a ˜ Pw0 k. Si nos fijamos en la distancia entre las predicciones y las medidas estaremos ignorando las distancias entre sí de las medidas seleccionadas en la combinación. Para corregir esto crearemos esta variable: ˜ Pw0 k=Gw0 k·X c β0c,w0 k·vc,w0 k·(vc,w0 k)T−vc,w0 k·(vc,w0 k)T·(Gw0 k)T(C.58) C.4.5. Probabilidad a posteriori y agrupamiento de hipótesis En nuestro caso, consideraremos que las hipótesis con menos variaciones de aceleración serán más probables. Para ello podemos obtener una probabilidad a posteriori para cada hipótesis, la cuál esté basada en el cálculo de la aceleración sufrida en los últimos fotogramas. De este modo, definiremos una función de probabilidad fAa la que llamaremos función de aceleración, la cuál representará la probabilidad de que se dé una determinada aceleración. Tras aplicar dicha función, tendremos que renormalizar las probabilidades de las hipótesis de nuevo. p00(Hw0 k) = p0N(Hw0 k)·fA(Hw0 k)(C.59) p00N(Hw0 k) = p00(Hw0 k) X w0 p00(Hw0 k)(C.60) Por otra parte, al final de cada iteración, también puede ser interesante el hecho de agrupar las hipótesis cuyos estados sean demasiado cercanos; ya que es bastante probable que dichas hipótesis obtengan resultados en paralelo, de manera que no se aproveche la ventaja de usar múltiples hipótesis. Para unir 104 Sistema de Seguimiento hipótesis cercanas se usará un agrupamiento jerárquico en cada tracker a partir del estado estimado. Al fusionar dos hipótesis se considerará como válida la trayectoria de la más probable; de manera que su probabilidad sea igual a la suma de las probabilidades de ambas hipótesis. 105 Anexo C 106 Bibliografía [1] J.R. Gómez, Detección, segmentación y seguimiento de personas en un entorno multicámara: Aplicación en el ámbito deportivo, Universidad de Zaragoza, Zaragoza (Abril 2010). [2] S.S. Cheung and C.Kamath, Robust techniques for background substraction in urban traffic video, In Proc. Video Communications and Image Processing. vol. 5308 SPIE Electronic Imaging , San Jose, CA, U.S.A., doi:10.1007/12.526886 (Jan. 2004). [3] I. Haritaoglu, D. Harwood and L.Davis, W4s: A real time system for detecting and tracking people in 2 1/2d, European Conference in Computer Vision, vol. LNCS/1406, pp.877-892, doi:10.1007/BFb0055710 (1998). [4] E.Herrero, C.Orrite and J.Senar, Detected motion classification with a double-background and a neighborhood-based difference, Patter Recognition Letters, vol.24. no.12, pp. 2079-2092 (2003). [5] T.Misu, M.Naemura, W.Zheng, Y.Izurni and K.Fukui, Robust tracking of soccer players based on data fusion, In Proc. 16th International Conference on Pattern Recognition (ICPR), vol.1, pp.556-561, doi:10.1109/ICPR.2002.1044792 (Aug. 2002). [6] M.M.Jlassi, A.Douik, T.Battikh and M.Annabi, Synthesis of classification supervised algorithms for players identification during a sports meeting, In Proc. 14th IEEE International Conference on Electronics, Circuits and Systems(ICECS) (2007). [7] M.Xu, J.Orwell and G.A. Jones, Tracking football players with multiple cameras, In Proc. International Conference on Image Processing, vol.5, pp. 2909-2912 (Oct. 2004). [8] S.Iwase and H.Saito,Tracking soccer players based on homography among multiple views, Proceedings of SPIE, vol. 5150 (Visual Communications and Image Processing), pp. 283-292, doi:10.1117/12.502967 (Jun.2003). [9] R.E.Kalman, A new approach to linear filtering and prediction problems, Transaction of the ASME-Journal of Basic Engineering - D, pp. 35-45(1960). [10] J.J. La Viola, A comparison of unscented and excented kalman filtering for estimating quaternion motion, In Proc. American Control Conference, pp. 2435-2440 (2003). 107 [11] E.A. Wan and R.Van der Merwe. The unscented kalman filter for nonlinear estimation, In Proc. IEEE Adaptative Systems for Signal Processing, Communications, and Control Symposium (AS-SPCC), pp.153-158, Lake Louise, AB, Canada, doi:10.1109/ASSPCC.2000.882463 (2000). [12] A.Doucet, On sequential simulation-based methods for bayesian filtering, Technical Report CUED/F-INFENG/TR 310, Cambridge University, Department of Engineering , Cambridge, U.K. (1998). [13] I.N.Junejo, O.Javed, and M.Shah,Multi Feature path modeling for video surveillance, In Proc. International Conference on Pattern Recognition(ICPR), vol.2, pp. 716-719(2004). [14] S.C. Jhonson, Hierarchical clustering schemes, Psychometrika, vol.32, no.3, pp.241-254, doi:10.1007/BF02289588 (Sep. 1967). [15] J.R.Gómez, J.E.Herrero, M.Montañes, F.Martínez, and C.Orrite,Detection and classification of football players with automatic generation of models, Optical Engineering, vol. 49, no. 1, pp. 017005-017005-17, doi:10.1117/1.3294885 (Jan. 2010). [16] A.Criminisi, I.Reid, and A.Zisserman, A plane measuring device, Image and Vision Computing, vol.17, no.8, pp. 625-634, doi:10.101016/S0262-8856(98)00183-8 (1999). [17] G.Welch and G.Bishop, An introduction to the Kalman filter, Technical Report TR 95-041, Computer Science, UNC Chapel Hill(1995). [18] J.R. Gómez, J.E. Herrero, C. Medrano, and C.Orrite, Multi-Sensor system based on unscented kalman filter, In.Proc Sixth IASTED international Conference on Visualization, Imaging and Image Processing (VIIP), Palma de Mallorca, Spain, pp-13-18 (Aug.2006). [19] P.Willet, Y.Ruan. and R.Streit, The pmht: Its problems and some solutions, IEEE Transactions on Aerospace and Electronic Systems, vol.38 no.3, pp.738-754(Jul.2002). 108 Índice de figuras 2.1. Interfaz gráfica de CVLAB. .................................. 8 2.2. Representación gráfica de la división en cuadrantes realizada sobre el campo de futbol. ..... 9 2.3. Ejemplo de trayectoria individual en el cuadrante 14. ...................... 10 2.4. Ejemplo en el que se muestran los puntos que son necesarios definir para comprobar si dos trayectorias están lo suficientemente cerca como para medir su distancia con exactitud o no(para considerarlas como “cercanas” o “lejanas”). .......................... 13 2.5. Ejemplos de distribuciones de distancias parciales entre trayectorias. .............. 14 2.6. Efecto del número de puntos usados para obtener la distancia total entre dos trayectorias. En la imagen de la izquierda podremos ver el efecto causado en el caso de dos trayectorias cercanas y en la imagen de la derecha podremos ver el efecto causado en el caso de dos trayectorias con una parte común y otra divergente. ................................ 15 2.7. Ejemplo de partes comunes para distintos pares de trayectorias. ................ 16 2.8. Representación gráfica del remuestreo de un número de puntos entero(imágenes de la izquierda) y de un número de puntos no entero (imágenes de la derecha) en una sección entre dos emparejamientos para dos pares de trayectorias diferentes. ...................... 17 2.9. Ejemplos de dos pares de trayectorias con sus respectivas correspondencias y su trayectoria media, en la parte común de dichas trayectorias. ......................... 18 2.10. Ejemplos de dos pares de trayectorias con sus respectivas correspondencias y su trayectoria media, en la parte divergente de dichas trayectorias. ....................... 19 109 2.11. Cálculo de la trayectoria media para un grupo de tres trayectorias. En color verde, las trayectorias originales. En colores negro, azul y morado, las trayectorias medias obtenidas de las tres formas posibles. ........................................... 20 2.12. Cálculo de la trayectoria media para un grupo de tres trayectorias. Podemos ver como la trayectoria media dispone de menos ruido que las trayecrorias iniciales a partir de las cuáles se ha obtenido dicha trayectoria. .................................. 20 2.13. Ejemplo del proceso de obtención de trayectorias medias. Las trayectorias iniciales se muestran en color verde y los agrupamientos de éstas - los cuáles habrá un momento en que sean considerados como trayectorias medias - en color azul. ........................ 21 2.14. En la figura de la izquierda(superior) podemos ver las trayectorias individuales que se han obtenido inicialmente para el cuadrante 14, mientras que en la figura de la derecha(superior) podemos ver las trayectorias medias que se han obtenido a partir de dichas trayectorias individuales. En las figuras inferiores podemos ver lo mismo que en las superiores pero con un zoom. ........ 22 2.15. Ejemplo de como calcular el peso en el caso de una trayectoria. El peso asociado a una trayectoria será proporcional al inverso de la distancia entre el estado predecido de un jugador y el vector formado por los dos puntos más cercanos de la trayectoria respecto al estado anterior, trasladado al estado anterior. En primer lugar se creará un área de gating alrededor del estado anterior, de forma que filtremos aquellas trayectorias cuyos puntos más cercanos están dentro del área de gating. Una vez han sido seleccionadas las trayectorias, trasladaremos el vector formado por los dos puntos más cercanos de cada trayectoria al estado anterior. Calcularemos el peso asociado a cada trayectoria como el inverso de la distancia entre el estado predicho y el vector (formado por los dos puntos más cercanos) trasladado al estado anterior. ................... 24 3.1. Tabla que muestra el error obtenido en el sistema inicial para distintos valores de umbral_medida, para 200 y para 1000 fotogramas. ............................... 30 3.2. Gráficas que muestran el error obtenido en el sistema modificado, para distintos valores de de umbral_KTRAY para umbral_tray: 3 y 10 (Gráficas superior e inferior respectivamente). Estos errores han sido obtenidos realizando una simulación de 200 fotogramas o frames. ....... 31 3.3. Gráficas que muestran el error obtenido en el sistema modificado para distintos valores de de umbral_KTRAY para umbral_tray: 30 y 1000 (Gráficas superior e inferior respectivamente). Estos errores han sido obtenidos realizando una simulación de 200 fotogramas o frames. ....... 32 110