Repositorio Institucional de Documentos

Repositorio de la Universidad de Zaragoza– Zaguan http://zaguan.unizar.es Trabajo Fin de Máster Seguimiento de Múltiples Objetos Basado en el Algoritmo de Viterbi Autor/es Ramón A. Suárez Fernández Director/es Carlos Orrite Uruñuela Máster Oficial en Ingeniería Electrónica Escuela de Ingeniería y Arquitectura 2011-2012 I II Seguimiento de Múltiples Objetos Basado en el Algoritmo de Viterbi Resumen El seguimiento de objetos en secuencias de imágenes es actualmente un tema de investigación importante debido a que tiene un amplio rango de aplicaciones tales como video vigilancia, análisis deportivo, etc. Un ejemplo común es el análisis de jugadores en un partido de fútbol. Mediante el procesamiento de las imágenes se puede establecer la trayectoria de cada jugador durante el partido y así proveer información importante sobre su actividad. El problema del seguimiento de objetos tiene dos grandes pasos principales, el primero es detectar y localizar los objetos dentro de los fotogramas del video y el segundo es la parte de seguimiento, esto implica implementar un método que obtenga las trayectorias de los objetos detectados resolviendo las oclusiones que pueden establecer entre ellos. En este trabajo se propone un método para el seguimiento de múltiples objetos. Se parte de un trabajo previo donde se detectó a los jugadores en la imagen y se estableció la localización de todos ellos en el terreno de juego, afrontando el segundo problema explicado, es decir, la asignación de una etiqueta inequívoca para cada jugador a lo largo de todo el partido. Para llevar a cabo esta tarea previamente se ha procedido a un etiquetado manual de todos los jugadores para posteriormente verificar la fiabilidad del método propuesto. El método planteado sigue un análisis de probabilidades de presencia de cada jugador en una posición determinada del campo y un método robusto de asignación temporal de todas las posiciones de los jugadores mediante el algoritmo de Viterbi. Palabras Clave Seguimiento de Objetos, Algoritmo de Viterbi, Análisis Deportivo, Análisis de Probabilidades. III IV Quiero dar las gracias en primer lugar a mi tutor Carlos Orrite Uruñuela por haberme ofrecido la oportunidad de realizar este Trabajo Fin de Master y agradecerle toda la ayuda y el apoyo que he recibido durante todos estos meses. Finalmente, me gustaría dedicarle este trabajo a mi familia y amistades, los cuales siempre han estado conmigo brindándome apoyo y consejos en los momentos buenos y malos. A vosotros, Gracias. V VI Índice Introducción ............................................................................................... 1 1.1 Motivación ......................................................................................... 1 1.2 Objetivos y Enfoque ............................................................................ 2 1.3 Organización de la Memoria ............................................................... 3 Estado del Arte ........................................................................................... 4 Seguimiento de Múltiples Objetos.............................................................. 10 3.1 Problemática .................................................................................... 10 3.2 Modelo de Red .................................................................................. 11 3.3 Metodología ...................................................................................... 12 3.3.1 Procesos Discretos de Markov ..................................................... 12 3.3.2 Elementos de un HMM ............................................................... 12 3.3.3 Problemas Básicos de los HMM .................................................. 14 3.3.4 Solución al Problema 2 ............................................................... 14 3.3.5 Algoritmo de Viterbi .................................................................... 16 Aplicación al Análisis Deportivo................................................................. 18 4.1 Secuencias (Datos) de Vídeo ............................................................. 18 4.2 Etiquetado Manual de los Jugadores ................................................ 20 4.3 Transformación con la Matriz de Homografía .................................... 22 4.4 Elaboración de Mapas Probabilísticos ............................................... 23 4.5 Detalles de Implementación ............................................................. 24 4.5.1 Número de Estados del Modelo N ................................................ 25 4.5.2 Probabilidad de Transición , ................................................... 25 4.5.3 Probabilidad de Observación () .............................................. 26 4.5.4 Etiquetado de la Posición Mediante Viterbi ................................. 27 Análisis de Resultados .............................................................................. 28 VII 5.1 Cálculo del Umbral  ....................................................................... 28 5.2 Simulación del Sistema Inicial ......................................................... 31 5.3 Método de Corrección de Etiquetas .................................................. 33 5.4 Simulación del Sistema Final .......................................................... 36 Conclusiones ............................................................................................ 40 6.1 Propuestas de Desarrollo Futuro ..................................................... 42 Anexo I: Cálculo de la matriz de Homografía .............................................. 43 Bibliografía ............................................................................................... 46 VIII Tabla de Figuras Figura 1 - Histograma de la fecha de publicación de los trabajos citados a lo largo del trabajo. ............................................................................................................. 4 Figura 2. Modelo de la red para seguimiento de un jugador. ................................. 11 Figura 3. Esquema del campo de visión del terreno de juego. ............................... 19 Figura 4. Vistas de las cámaras 1-3 del terreno de juego. ..................................... 19 Figura 5. Asignación de etiquetas a los jugadores en el terreno. Disposición 4-4-220 Figura 6. Ejemplo del programa de etiquetado manual de jugadores..................... 21 Figura 7 - Ejemplo gráfico del cambio de coordenadas del plano de la imagen al plano del campo ................................................................................................... 22 Figura 8 - Histogramas de las posiciones de los jugadores 1 (arriba) y 9 (abajo) .... 23 Figura 9 - Ejemplo de las trayectorias obtenidas por el algoritmo de Viterbi ......... 24 Figura 10 - Demonstración Grafica del Cálculo de Distancia Euclidea .................. 26 Figura 11 - Curva de Error al cambiar el Umbral (λ) ............................................. 30 Figura 12 - Resultado de Etiquetado Inicial para el fotograma 64 ......................... 32 Figura 13 - Resultado de Etiquetado Inicial para el fotograma 383 ....................... 32 Figura 14 - Resultado del Etiquetado Inicial para el fotograma 477 ...................... 33 Figura 15 - Resultado de Etiquetado Final para el fotograma 64 ........................... 38 Figura 16 - Resultado de Etiquetado Final para el fotograma 383 ......................... 38 Figura 17 - Resultado de Etiquetado Final para el fotograma 477 ......................... 39 Figura 18 - Ejemplo gráfico de la transformación de coordenadas de la imagen al plano .................................................................................................................... 43 Listado de Tablas Tabla 1 - Matriz de Confusión para λ = 0,1 ........................................................... 28 Tabla 2 - Matriz de Confusión para λ=0,3 ............................................................. 29 Tabla 3 - Matriz de Confusión para λ=0,5 ............................................................. 29 Tabla 4 - Porciento de Error Dependiendo del Umbral λ ........................................ 30 Tabla 5 - Resultados detallados del Etiquetado inicial .......................................... 31 Tabla 6 - Tabla de Valores de δ t (j) para el fotograma 383 ..................................... 34 Tabla 7 - δ t (j) del Jugador A en los fotogramas 382 - 384 ..................................... 35 Tabla 8 - δt (j) del Jugador B en los fotogramas 382 - 384 .................................... 35 Tabla 9 - Matriz de confusión de la simulación del sistema final ........................... 36 Tabla 10 - Resultados detallados del Etiquetado Final .......................................... 37 7 Por otra parte, si se pretende realizar un seguimiento de múltiples objetos 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 la posición de los objetos abandone 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. Esta técnica se ha utilizado para seguir a varios jugadores de hockey en [13]. Además de los dos grupos de algoritmos mencionados anteriormente, los cuáles pueden ser usados para realizar un seguimiento de múltiples objetos, caben destacar los algoritmos de seguimiento “Multiple Hypothesis Tracking”. En este tipo de algoritmos, en caso de duda a la hora de asociar las medidas a 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 una posición distinta. 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 un buen podado 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 multi-hipó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 multi-hipótesis se basan en un modelo probabilístico, como el algoritmo PMHT [14]. 8 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. En un intento de aumentar su fiabilidad, algunos métodos tienen enfoques híbridos. Las detecciones en las imágenes se conectan en trayectorias cortas, que luego son unidas entre sí. Por ejemplo, [15] se basa en el filtro de Kalman para obtener trayectorias básicas, y luego trata de unir o separarlas usando el “Hungarian Algorithm”. Wu y Nevatia en [16] define una medida de la afinidad basada en la posición, tamaño y color luego utiliza el “Hungarian Algorithm” para asociar las hipótesis y las respuestas de detección de objetos en fotogramas vecinos. [17] explora la versión jerárquica del mismo concepto. Por el contrario en [18], Los autores asumen que una gráfica de trayectorias ya se ha producido y se centran en la vinculación de las etiquetas en el gráfico. Ellos formulan el seguimiento de varios objetos como un problema de Inferencia de Red Bayesiana y aplican este método para el seguimiento de varios jugadores de fútbol. Esta clase de métodos es un buen compromiso: La arquitectura de dos etapas les permite escalar de manera eficiente, mientras que al mismo tiempo, tienen en cuenta una ventana de observación más amplia. Sin embargo, mientras que exhiben buenos resultados en algunas situaciones, los métodos no garantizan la convergencia a un óptimo global. Por consiguiente, son propensas a errores tales como cambios de etiquetas. 9 Para mejorar la robustez, la investigación se ha centrado recientemente en la vinculación de las detecciones en una ventana de tiempo más grande utilizando varios esquemas de optimización. Programación Dinámica [19] se puede utilizar para unir las múltiples detecciones atreves del tiempo, y por lo tanto, resolver el problema de seguimiento múltiple. Además, se puede ampliar para permitir la optimización de varias trayectorias simultáneamente [20]. La Programación Lineal es un método de optimización que se ha aplicado para encontrar óptimos globales y resolver el problema del seguimiento de varias personas [21]. Empezando desde la salida de detectores de objetos, este último enfoque construye un gráfico de la red en la que cada nodo es una observación y está completamente conectado a observaciones futuras y pasadas. Oclusiones entre los objetos se modelan mediante la especificación de los conflictos espaciales entre los nodos. Nodos adicionales se crean específicamente para manejar los objetos ocluidos. Finalmente, los pesos de los arcos se eligen de acuerdo a las apariencias de objetos y un modelo de este. Un modelo gráfico similar, con nodos que representan las detecciones, se construye por [22] para seguimiento de múltiples personas. El óptimo global se busca utilizando un algoritmo de flujo de costo mínimo, que se aprovecha de la estructura específica de la gráfica para alcanzar el óptimo más rápido. 10 Seguimiento de Múltiples Objetos 3 En este capítulo se describe el método utilizado para resolver el problema de seguimiento de múltiples objetos en fotogramas de video. Para esto, se comienza por representar todas las posibles posiciones de un objeto dentro de la imagen como nodos. Luego de varios fotogramas, estos nodos interconectados forman un gráfico o “trellis”, donde un camino de nodos conectados representa una posible trayectoria de un objeto a través del tiempo en un video. 3.1 Problemática Para poder hacer el seguimiento de los objetos, es necesario localizar sus posiciones a través de una secuencia de fotogramas de vídeo. Como se mencionó anteriormente, este trabajo parte de un trabajo previo donde se detectó a los jugadores en las imágenes y se estableció la localización de todos ellos en el terreno de juego. No obstante, ya teniendo esto, se ha procedido a hacer un etiquetado manual de todos los jugadores en el terreno de juego utilizando el programa explicado en la sección 4.2. El etiquetado manual se utilizará como las observaciones para poder verificar el desempeño del método implementado posteriormente. Partiendo de la detección de los objetos en las imágenes nos centraremos en un método que nos permita asignar una etiqueta inequívoca a cada jugador a lo largo de todo el partido. 11 3.2 Modelo de Red A continuación se estudia el seguimiento de múltiples objetos basado en un modelo de la red en el cual todos los sub-modelos interactúan entre ellos. La Figura 2 representa la red en la cual se basa el algoritmo. Las posibles posiciones de un jugador son representados como nodos circulares. En cualquier fotograma, las posibles posiciones (es decir, las observaciones) para cada objeto pueden ser diferentes. Los nodos de inicio y final, mostrados como cuadrados en la Figura 2, también son incluidos en cada sub-modelo para representar el inicio y el final de la trayectoria del jugador, sin embargo, los nodos del final no corresponden a ningún estado de los jugadores. Las flechas en negro entre los nodos representan las posibles transiciones de estado. Un conjunto de nodos conectados entre los nodos de inicio y final representan la trayectoria espacial de un objeto. Una vez un nodo es seleccionado como la posición de un objeto, todos los otros objetos deben estar en una posición diferente dentro del fotograma. Figura 2. Modelo de la red para seguimiento de un jugador. S 1 S2 S3 Sn S 1 S2 S3 Sn S 1 S2 S3 Sn S 1 S2 S3 Sn q 1 12 3.3 Metodología La teoría del Modelo Oculto de Markov (HMM) esta descrita en detalle en los artículos [23 y 24]. 3.3.1 Procesos Discretos de Markov Se considera un sistema que puede ser descrito en cualquier instante de tiempo, como que está en uno de  estados distintos   ,  ,⋯,  . En instantes discretos de tiempo, el sistema sufre un cambio de estado conforme con un conjunto de probabilidades asociadas a este estado. Se conocen los instantes de tiempo asociados con los cambios de estado como =1,2,⋯, y llamamos al estado en el tiempo t como   . Una descripción probabilística completa del sistema mencionado, generalmente, requiere la especificación tanto del estado actual (en el tiempo ) como de los estados anteriores. 3.3.2 Elementos de un HMM Un HMM se caracteriza por lo siguiente: 1) , el número de estados en el modelo. A pesar de que los estados están ocultos, para muchas aplicaciones prácticas hay algún significado físico adherido a los estados o a conjuntos de estados del modelo. Generalmente los estados están interconectados entre ellos de tal manera que se puede alcanzar un estado desde cualquier otro. Se denominan los estados individuales como =  ,  ,⋯,  . 2) , el número de símbolos de observaciones distintas por estado, i.e., el tamaño discreto del alfabeto. Los símbolos de las 13 observaciones corresponden a la salida física del sistema siendo modelado. Se denominan los símbolos individuales como =   ,  ,⋯,  . 3) La distribución de las probabilidades de transición de estado = ,! " donde,  , !  = P $   %  =   !  ǀ    =    ' ,      1 ≤ ) , * ≤  . (1) Para el caso especial donde cualquier estado puede llegar a cualquier otro en un paso, tenemos que  ,! >0 para todo ),*. Para otros tipos de HMM, podría ser que  ,! =0 para uno o más de un par ),*. 4) La distribución de las probabilidades de los símbolos de observaciones en el estado * , .=/ ! (0)", donde / ! ( 0 )  = P $   1     |    =   ! ' ,     1 ≤ * ≤  1 ≤ 0 ≤  . (2) 5) La distribución del estado inicial 3=3  donde 3  = P 4    =  5 ,      1 ≤ ) ≤  . (3) Dados los apropiados valores de ,,,.y 3, el HMM puede ser utilizado para proveer una secuencia de observaciones, 6 = 6  , 6  , ⋯ , 6  . (4) Donde cada observación 6  es uno de los símbolos de , y 7 es el número de observaciones en la secuencia. 14 3.3.3 Problemas Básicos de los HMM Dado el modelo del HMM anterior, hay tres problemas básicos de interés que deben ser resueltos para que el modelo pueda ser útil en aplicaciones reales. Los problemas son los siguientes: Problema 1: Dada la secuencia de observaciones 6=6  ,6  ,⋯,6  , y un modelo 8=, ., 3, ¿Cómo calculamos la probabilidad de la secuencia de las observaciones P(6|8), dado el modelo? Problema 2: Dada la secuencia de observaciones 6=6  ,6  ,⋯,6  , y el modelo 8=, ., 3, ¿Cómo escogemos la correspondiente secuencia de estados 9=  ,  ,⋯,  optima? Problema 3: ¿Cómo ajustamos los parámetros del modelo 8=, ., 3 para maximizar P(6|8)? Tal como se explica, el Problema 2 es el caso donde intentamos descubrir la parte oculta del modelo, mejor dicho, encontrar la secuencia de estados correcta. Debido a que la problemática de este trabajo se asimila más al Problema 2 de los HMM, solo se presentara a continuación la solución matemática a este. 3.3.4 Solución al Problema 2 A diferencia del Problema 1 para el cual una solución exacta puede ser encontrada, hay varias maneras de resolver el Problema 2, es decir, encontrar la secuencia de estados óptima asociada con la secuencia de observaciones dada. Por ejemplo, una posible solución es escoger como criterio de optimalidad los estados   que son individualmente más probables. Este criterio de optimización maximiza el número esperado de estados correctos. Para implementar esta solución al Problema 2, se define la variable, 15 :  ( ) ) = ; (    =   | 6 , 8 ) , (5) i.e., la probabilidad de estar en el estado  en el tiempo  dada la secuencia de observaciones 6, y el modelo 8. La ecuación (5) se puede expresar solo en términos de las variables <  ()) y =  ()), :  ( ) ) = <  ( ) )  =  ( ) ) ; ( 6 | 8 ) = <  ( ) )  =  ( ) ) ∑ <  ( ) )  =  ( ) )  ?  . (6) Donde, <  ( ) ) = P ( 6   6   ⋯  6  ,    =   |  8 ) , (7) es la probabilidad de la secuencia de observaciones parcial, 6  6  ⋯6  (hasta el tiempo ) y el estado  en el tiempo  dado el modelo 8. Y =  ( ) ) = P ( 6  %   6  %   ⋯  6 @ |    =    , 8 ) , (8) es la probabilidad de la secuencia de observaciones parcial desde t+1 hasta el final dado el estado  en el tiempo  y el modelo 8. El factor de normalización ;(6|8)=∑<  ())=  ())  ? hace a :  ()) una medida de probabilidad para que C :  ( ) )  ?  = 1 . (9) Utilizando :  ()) se puede resolver para el estado individual más probable   en el tiempo  de la siguiente manera   = argmax  I I  4 :  ( ) ) 5 ,      1 ≤  ≤ 7 . (10) 16 Aunque (10) maximiza el número de estados correctos, podría haber problemas con la secuencia de estados resultante. Un ejemplo es cuando el HMM tiene valores de transición de estado con probabilidad de cero ( ,! =0 para algún ),*), la secuencia de estado optima puede ser que no sea una secuencia de estado valida. Esto es debido a que la solución de (10) simplemente resuelve por el estado más probable en cada instante sin tomar en cuenta la probabilidad de la secuencias de estados. Una posible solución al problema anterior es modificar el criterio de optimización. Por ejemplo, se podría resolver por la secuencia de estados que maximizara el número esperado de pares correctos de estados (  , % ) o tríos de estados (  , % , % ), etc. Aunque este criterio puede ser razonable para algunas aplicaciones, el criterio más utilizado es encontrar la mejor secuencia de estados (trayectoria), o sea, maximizar ;(9|6,8) lo cual es equivalente a maximizar ;(9,6|8). Una estrategia formal para encontrar la mejor secuencia de estados existe basada en Programación Dinámica y se llama el Algoritmo de Viterbi [25], [26]. 3.3.5 Algoritmo de Viterbi Para encontrar la mejor y única secuencia de estados 9=   ,  ,⋯, @ , para la secuencia de observaciones dada 6=6  ,6  ,⋯,6  , necesitamos definir J  ( ) ) = max K L , K M , ⋯ , K N O L P 4       ⋯     =  )  , 6  , 6  , ⋯ , 6  |  8 5 (11) i.e., J  ()) es la mayor probabilidad a través de una trayectoria, en el tiempo , que toma en cuenta las primeras  observaciones y acaba en el estado  . Por lo que tenemos, J  ( ) ) = $ max J  ( ) )   , ! '  ∙  / ! ( 6  %  ) . (12) 23 4.4 Elaboración de Mapas Probabilísticos Luego de haber transformado las posiciones de los jugadores en el campo de la imagen a sus respectivas posiciones en el terreno de juego, se procedió crear un mapa probabilístico de los jugadores en el terreno de juego. Este mapa probabilístico se creó contando el número de ocasiones en que un jugador =1,2,…,10 se encuentra en la posición (U,V), donde U∈40,1005,V∈40,605 en cada uno de los fotogramas. Con estos valores se elabora un histograma de las posiciones que ocupa el jugador . En la Figura 8 se demuestran dos ejemplos de los histogramas creados para los jugadores 1 y 9. La obtención de un mapa probabilístico es un paso útil ya que esto nos proporciona las probabilidades de que un jugador esté en un punto del campo en cualquier instante de tiempo y se utilizara en la implementación del método planteado. 10 20 30 40 50 60 70 80 90 100 10 20 30 40 50 60 HISTOGRAMA DE POSICIONES DEL JUGADOR 1 EN EL TERRENO DE JUEGO 10 20 30 40 50 60 70 80 90 100 10 20 30 40 50 60 HISTOGRAMA DE POSICIONES DEL JUGADOR 9 EN EL TERRENO DE JUEGO Figura 8 - Histogramas de las posiciones de los jugadores 1 (arriba) y 9 (abajo) 24 4.5 Detalles de Implementación La Figura 9 muestra un ejemplo gráfico del resultado que se espera del algoritmo implementado. El algoritmo de Viterbi obtiene la mejor trayectoria de un solo jugador a través de una secuencia, debido a esto, se ejecutará un algoritmo de Viterbi para cada jugador y así obtener su recorrido individual. El algoritmo se implementará en Matlab ya que éste cuenta con herramientas útiles para el procesamiento de imágenes que pueden manejar los costos computacionales. A continuación se explican detalles de la asignación de variables del algoritmo. Figura 9 - Ejemplo de las trayectorias obtenidas por el algoritmo de Viterbi 25 4.5.1 Número de Estados del Modelo N Como se ha explicado anteriormente, hay 10 etiquetas posibles para los jugadores de cada equipo. Estas se representan como círculos en el ejemplo de la Figura 9 y dan referencia a su posición física dentro del campo como lo ilustra la Figura 5. Debido a esto, el número de estados posibles en cualquier fotograma del video es de 10. Donde, =1,2,3,4,5,6,7,8,9,10 4.5.2 Probabilidad de Transición , La probabilidad de transición se define como la probabilidad de estar en la posición * del terreno de juego en un instante de tiempo, dado que te hayas encontrado en la posición ) en el tiempo anterior. Un ejemplo del significado de la probabilidad de transición se puede observar en la Figura 9, donde  , representa la probabilidad de pasar de la posición 1 en el tiempo =1, a la posición 1 en el tiempo =2. De la misma manera,  a, denota la probabilidad de pasar de la posición 10 a la posición 1. Para obtener esta probabilidad se comienza por calcular la distancia Euclidea entre la posición de un objeto en el fotograma actual y la posición de todos los objetos detectados en el fotograma siguiente. La representación gráfica del cálculo de esta distancia se encuentra en la Figura 10. En el ejemplo de la Figura 10, se calcula la distancia de la posición actual de un objeto a las posiciones de todos los objetos detectados en el siguiente fotograma. De esta manera, mientras menor sea la distancia recorrida de un fotograma al siguiente, mayor será la probabilidad de que sea esta la transición del estado. 26 Seguido de obtener las distancias se procede a calcular la probabilidad utilizando la siguiente ecuación:  , !   P $   %     !  ǀ        '  b R c d e N L → N M d (20) Donde 8 es un umbral que nos permite afinar el cálculo de la probabilidad de transición, y g L→M es la distancia calculada. 4.5.3 Probabilidad de Observación  Para definir la probabilidad de observación / ! 0, primero se debe detallar el significado de las observaciones. Se tomarán como observaciones las posiciones de los jugadores en el terreno de juego para cada fotograma. Con esta definición de observación se puede resumir la probabilidad de observación como la probabilidad de que un objeto detectado corresponda a un estado u otro dada su posición la imagen. En la Figura 9, la probabilidad de transición en el tiempo   2 se representa como $/  h6 M i,… ,/ a h6 M i', donde, 6 M es la posición en el terreno de juego del jugador en el tiempo   2 y /  h6 M i es la probabilidad de que el jugador esté en esta posición. Para esta probabilidad se utilizaran los resultados de los mapas probabilísticos y los Figura 10 - Demonstración Grafica del Cálculo de Distancia Euclidea 2 3 6 7 Posición en t=1 Posición en t=2 1 4 5 8 dt=1→t=2 9 10 27 histogramas mencionados anteriormente ya que precisamente estos mapas proporcionan la probabilidad de un jugador dada la posición en el terreno de juego. 4.5.4 Etiquetado de la Posición Mediante Viterbi En la Figura 9 se presenta un simple ejemplo de cómo funciona el etiquetado mediante el algoritmo de Viterbi. En dicha figura se ve representado el resultado de la ecuación (19):  ∗ =Q % ( % ∗ ),=7−1,7−2,⋯,1 Esta ecuación obtiene las etiquetas de los jugadores,  ∗ , desde = 1hasta =7. En el ejemplo de la Figura 19 se pueden observar los cambios de etiqueta de los jugadores j1 y j10 desde =1 hasta =7 y se representa la trayectoria como la conexión de las flechas negras. De acuerdo con este ejemplo el resultado del etiquetado del jugador j1 es la secuencia, (j1)=41,1,…,2,25. Este resultado supondría un error en el etiquetado, ya que, el jugador j1 comienza con la etiqueta 1 en el tiempo =1 y a lo largo del tiempo cambia su etiqueta a 2. Sin embargo, el etiquetado del jugador j10 es, (j10)=410,10,…,10,105. En este caso las etiquetas se mantienen iguales durante toda la trayectoria por lo que el etiquetado sería correcto. El error en el etiquetado del jugador j1 es uno muy común donde los sistemas de seguimiento cambian las etiquetas en algún instante, este error es precisamente uno de los problemas que se desea corregir asignando una etiqueta inequívoca a lo largo de todo el tiempo para evitar coincidencias. 28 Análisis de Resultados 5 En este capítulo vamos a mostrar, analizar y comparar los resultados obtenidos con el sistema de seguimiento respecto al mismo sistema con un método de verificación de coincidencias en los etiquetados de los jugadores. Para poder evaluar el sistema utilizaremos los datos del etiquetado manual y se calculará el error obtenido antes y después de utilizar el método mencionado. Dicho error será calculado como el número de veces en que se le asigna una etiqueta equivocada a algún jugador en cada fotograma. 5.1 Cálculo del Umbral  El primer paso antes de la simulación del algoritmo implementado es el cálculo del umbral relacionado con la probabilidad de transición que se presenta en la sección 4.5.2. Para escoger este umbral se simuló el sistema con 1200 fotogramas variando el umbral desde 0,1 hasta 1,0 en intervalos de 0,1. A continuación se presenta la Matriz de confusión para 8=0,1, 8=0,3 y 8=0,5. Resultado del Etiquetado Mediante el Algoritmo de Viterbi 1 2 3 4 5 6 7 8 9 10 Etiqueta Real del Jugador 1 1194 3 0 0 1 0 1 0 1 0 2 279 911 5 2 0 0 0 0 1 2 3 1 2 11 90 4 0 1 1 0 1 0 4 147 1 6 10 38 3 1 1 1 1 1 5 443 0 1 3 746 4 1 0 1 1 6 509 2 1 5 3 6 75 4 0 1 0 7 561 1 0 0 0 8 6 26 4 0 0 8 0 0 1 0 0 0 6 11 86 7 0 9 346 0 0 0 0 0 0 5 8 43 6 10 686 0 2 0 0 1 4 1 11 4 95 Tabla 1 - Matriz de Confusión para λ = 0,1 29 Resultado del Etiquetado Mediante el Algoritmo de Viterbi 1 2 3 4 5 6 7 8 9 10 Etiqueta Real del Jugador 1 1192 5 0 0 1 0 1 0 1 0 2 4 1185 5 2 0 1 0 0 1 2 3 1 2 1190 4 0 1 1 0 1 0 4 2 1 5 1184 3 1 1 1 1 1 5 4 0 1 4 1181 5 2 0 1 2 6 0 2 1 7 4 1180 5 0 1 0 7 104 2 2 1 0 9 1076 5 0 1 8 0 0 1 0 0 0 6 1186 7 0 9 0 1 0 0 1 0 0 7 1181 10 10 0 2 2 0 3 22 4 2 14 1171 Tabla 2 - Matriz de Confusión para λ=0,3 Resultado del Etiquetado Mediante el Algoritmo de Viterbi 1 2 3 4 5 6 7 8 9 10 Etiqueta Real del Jugador 1 1192 5 0 0 1 0 1 0 1 0 2 4 1185 5 2 0 1 0 0 1 2 3 1 2 1190 4 0 1 1 0 1 0 4 2 1 5 1184 3 1 1 1 1 1 5 4 0 1 4 1181 5 2 0 1 2 6 0 2 1 7 4 1180 5 0 1 0 7 0 2 2 1 0 9 1179 6 0 1 8 0 0 1 0 0 0 6 1186 7 0 9 0 1 0 0 1 0 0 7 1181 10 10 0 2 2 0 3 2 4 2 14 1171 Tabla 3 - Matriz de Confusión para λ=0,5 La matriz de confusión es una herramienta de visualización donde cada columna de la matriz representa el número de predicciones de cada clase, mientras que cada fila representa a las instancias en la clase real. Se representan los resultados de esta manera ya que estas facilitan ver si el sistema se está confundiendo entre clases. Como se puede apreciar en las Tablas 1-3, a medida que se aumenta el umbral, las equivocaciones en el etiquetado de los jugadores disminuyen. Por ejemplo, si comparamos en las tres tablas la fila 7 de la columna 1, veremos que con el umbral en8=0,1 el 30 número de veces que le asigna al jugador 7 la etiqueta de jugador 1 es de 561. Mientras que con el umbral en 8=0,3 es de 104 y con 8  0,5 es de 0 veces. Para calcular el error de etiquetado simplemente se suman los elementos en la matriz que no están en la diagonal (Errores) y se divide entre la suma de todos los elementos de la matriz (12000). Los valores de error de esta simulación se encuentran en la Tabla 1 y gráficamente en la Figura 11. Fotogramas: 1 - 1200 Umbral de la Probabilidad de Transición (  ) 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 Error de Etiquetado 25,8% 4,40% 2,28% 1,90% 1,42% 1,42% 1,42% 1,42% 1,42% 1,42% Tabla 4 - Porciento de Error Dependiendo del Umbral λ Como se puede ver en los datos de la Tabla 4 y la Figura 11, El error comienza en un 25,8% con un umbral de 8  0,1 y disminuye hasta un error de 1,42% con un umbral de 0,5 en adelante. Con estas pruebas se puede decidir de una manera experimental el valor del umbral que nos proporcionara el menor error de etiquetado. De este punto en adelante se utilizara un umbral de 8  0,5 para simular el sistema. Figura 11 - Curva de Error al cambiar el Umbral (λ) 0 5 10 15 20 25 30 0 0,2 0,4 0,6 0,8 1 % Error de Etiquetado Umbral (λ) Curva de Error de Etiquetado vs. Umbral Umbral Seleccionado λ = 0,5 31 5.2 Simulación del Sistema Inicial Luego de obtener el valor del umbral, se procedió a simular el sistema para analizar detalladamente los resultados obtenidos. Como se mencionó en la sección anterior, al simular el algoritmo con un umbral de 8=0,5 se obtuvo un error de 1,42%. Este porciento de error supone un fallo de un total de 171 etiquetas para todos los jugadores en 1200 fotogramas. Además de los resultados globales, podemos analizar los resultados para cada jugador individualmente. En la Tabla 5 se presentan los fallos encontrados particularmente por cada jugador. Fotogramas: 1 - 1200 Jugador 1 2 3 4 5 6 7 8 9 10 Fallos en etiquetado 8 15 10 16 19 20 21 14 19 29 Porciento de Error 0,67% 1,25% 0,83% 1,33% 1,58% 1,67% 1,75% 1,16% 1,58% 2,42% Tabla 5 - Resultados detallados del Etiquetado inicial Como se puede observar, el jugador que más dificultad tuvo el algoritmo de etiquetar fue el numero 10 ya que lo etiqueto incorrectamente 29 veces en una secuencia de 1200 fotogramas, esto se puede deber a que el jugador número 10 está constantemente moviéndose alrededor del terreno de juego y en alguna ocasión su probabilidad puede ser parecida a la de otro jugador. Sin embargo, si se toma en cuenta que el error en el etiquetado es de solo un 2,42% individual y de un 0,242% global, se puede decir que el Algoritmo de Viterbi, con el valor del umbral escogido, realiza la labor del etiquetado de forma eficiente y ha sido un método acertado para resolver el problema planteado. Para poder apreciar los resultados visualmente, se creó un código en Matlab que obtiene las imágenes reales del partido y les superpone la localización del jugador con un cuadro rojo alrededor de este punto. Además, muestra las etiquetas de los jugadores obtenidas por el algoritmo en cada fotograma y nos permite evaluar los resultados de una manera 32 diferente. A continuación, en las Figuras 12 – 14 se pueden apreciar las imágenes de varios instantes del partido de fútbol que representan los resultados del algoritmo. Figura 12 - Resultado de Etiquetado Inic ial para el fotograma 64 Figura 13 - Resultado de Etiquetado Inicial para el fotograma 383 39 Figura 17 - Resultado de Etiquetado Final para el fotograma 477 40 Conclusiones 6 En este Trabajo Fin de Master se ha presentado un método para solucionar el problema del seguimiento de múltiples objetos mediante técnicas de visión por computador y análisis de probabilidades. Para validar el sistema se ha aplicado el método a las imágenes de un partido de futbol, ya que por la naturaleza del deporte, existen muchos instantes donde los objetos en la imagen se ocluyen parcial o totalmente y presentaría un entorno útil para verificar la fiabilidad del sistema. En el capítulo 5 se pueden observar los resultados de las simulaciones del algoritmo. El sistema inicial, con la implementación del Algoritmo de Viterbi, se simuló para un total de 1200 fotogramas aproximadamente 10 min. En esta simulación se obtuvieron 171 etiquetas incorrectas de las 12000 etiquetas que se asignan, lo que corresponde a un error de 1,425%. Aun teniendo un error tan bajo, se exploró una manera de hacer que el sistema sea más robusto y resolviera mejor las oclusiones. Para esto se alteró el Algoritmo de Viterbi añadiendo un método de corrección de coincidencias demostrado en la sección 5.3. El cambio en el algoritmo supuso una disminución en el error total del 1,42% al 0,0167% lo que equivale a solo 2 errores en las etiquetas. Con estos resultados se demuestra que el Algoritmo de Viterbi, con algunas alteraciones, es un método idóneo para resolver problemas complicados de oclusiones parciales y totales para obtener las trayectorias de los jugadores a través de la secuencia de imágenes. El porcentaje de error resultante muestra que el sistema es robusto y fiable para la situación dada 41 y deja la puerta abierta para aplicarlo a otras situaciones de seguimiento de objetos. El sistema propuesto ha logrado el objetivo principal planteado en este trabajo, encontrar un método capaz de seguir objetos en una secuencia de imágenes asignándole a cada uno una etiqueta inequívoca durante toda una secuencia. De la misma manera se han alcanzado los objetivos intermedios: • Encontrar o desarrollar un algoritmo de seguimiento de múltiples objetos. • Minimizar la tasa de error en el seguimiento, teniendo en cuenta situaciones como cruces y oclusiones. Un objetivo no mencionado, pero aun así muy importante, es obtener los menores tiempos de ejecución del sistema posibles. Este parámetro es significativo ya que te asegura que has implementado el método de la manera más eficiente posible y permite posibilidad de ejecutar el sistema en tiempo real. El sistema, ejecutado en el entorno de Matlab con un procesador AMD E-350 @ 1.60 GHz y 4,00 GB de memoria RAM, tiene un tiempo de ejecución de 3.825s, un valor normal debido a la complejidad de los cálculos. 42 6.1 Propuestas de Desarrollo Futuro El algoritmo de seguimiento planteaba un gran problema principal, 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. Un posible trabajo futuro seria intentar aumentar la eficacia del algoritmo implementado utilizando más puntos de vista que los disponibles en las imágenes utilizadas en este trabajo, esto significaría utilizar un mayor número de cámaras. Además, sería interesante poder hacer el seguimiento mediante visión por computador, no por la posición de los jugadores en el campo, sino por la silueta de los números de las camisetas lo que necesitaría instalar cámaras de una mayor resolución en muchos puntos del campo. Otra propuesta para un trabajo futuro podría ser la implementación del sistema en tiempo real, recibiendo las imágenes del campo mientras el partido se está disputando y poder analizar las trayectorias de los jugadores. Esta propuesta tendría la posibilidad de convertirse en un producto comercial ya que los equipos deportivos utilizan dispositivos tecnológicos para mejorar su juego. Sin embargo, esto significaría que el método hay que pasarlo del lenguaje de Matlab a otro lenguaje capaz de hacer los cómputos más rápido. . 43 Anexo I: Cálculo de la matriz de Homografía Existen dos razones por la que es recomendable realizar un seguimiento sobre el plano del suelo en vez de sobre la imagen: - Mejorar la precisión de seguimiento de los jugadores, ya que se reduce el efecto del error perspectivo en la imagen. - Poder realizar un seguimiento de objetos a partir de los datos obtenidos de forma simultánea por varios sensores a la vez, uniendo a continuación las diferentes observaciones en un plano común. Para trasladar la información obtenida en la imagen al plano aplicaremos una transformación proyectiva. Como aproximación asumiremos que no existe ninguna distorsión creada por la lente de la cámara. Un punto en el plano proyectivo representará un rayo que pasa por el origen en el espacio 3D, tal y como podemos ver en la Figura 18. Figura 18 - Ejemplo gráfico de la transformación de coordenadas de la imagen al plano La transformación proyectiva entre dos planos puede ser representada como una transformación lineal donde, m  =7  m  . Si queremos volver al sistema de referencia anterior podremos usar como matriz de transformación 7  R , de manera que la transformación también sea lineal. 44 Si dicha transformación es representada en coordenadas cartesianas, los resultados no serán lineales. Sean: m n =(U ,V ,1) @ : Las coordenadas del punto i en el sistema de referencia de la cámara. m o =(U o ,V o ,1): Las coordenadas homogéneas asociadas a las coordenadas del punto i en el sistema de referencia del plano del suelo(U o ,V o ). 7 on : La transformación proyectiva para las coordenadas m n y m o . Para obtener dicha transformación proyectiva, para cada par i de puntos se tomará está ecuación: h8 U o ,8 V o ,8 i @ =p7 on (U ,V ,1)q @ Si la desarrollamos: rU V 1 0 0 0 −U o U −U o V −U o 0 0 0 U V 1 −V o U −V o V −V o s=p0 0q Donde =(     t      t  t  t  tt ) @ es un vector formado por los elementos de la matriz de homografía 7 on . Si usamos cuatro pares de puntos (En nuestro caso, por ejemplo, podríamos tomar los cuatro puntos asociados a los extremos del campo que se pueden ver cada cámara - por cada cámara tendremos una homografía), de forma que tres de ellos no sean colineales, podremos construir una matriz M de 8x9 elementos, donde Mt = 0. De esta manera, la solución t corresponde al vector propio asociado con el menor valor propio (en este caso el valor propio nulo) de la matriz MTM; el cuál puede ser calculado mediante una descomposición en valores singulares de la matriz M. Una vez hallemos la matriz de homografía Tgc, podremos realizar su transformación inversa para obtener la homografía en el sistema de referencia deseado. 45 46 Bibliografía [1] J. Black, T. Ellis, and P. Rosin, “Multi-View Image Surveillance and Tracking,” in IEEE Workshop on Motion and Video Computing, 2002. [2] A. Mittal and L. Davis, “M2tracker: a Multi-View Approach to Segmenting and Tracking People in a Cluttered Scene,” Computer Vision and Image Understanding, vol. 51(3), pp. 189–203, 2003. [3] S. Iwase and H. Saito, “Parallel Tracking of All Soccer Players by Integrating Detected Positions in Multiple View Images,” in International Conference on Pattern Recognition, August 2004, pp. 751–754. [4] M. Xu, J. Orwell, and G. Jones, “Tracking Football Players With Multiple Cameras,” in International Conference on Image Processing, October 2004, pp. 2909–2912. [5] D. R. Magee, “Tracking multiple vehicles using foreground, background and motion models,” Image and Vision Computing, vol. 22, no. 2, pp. 143–155, February 2004. [6] J.J. La Viola, “A comparison of unscented and scented Kalman filtering for estimating quaternion motion,” In Proc. American Control Conference, pp. 2435-2440 (2003). [7] E.A. Wan and R.Van der Merwe. “The unscented Kalman filter for nonlinear estimation,” In Proc. IEEE Adaptive Systems for Signal Processing, Communications, and Control Symposium (AS-SPCC), pp.153-158, Lake Louise, AB, Canada, (2000). [8] J. Vermaak, A. Doucet, and P. Perez, “Maintaining Multimodality Through Mixture Tracking,” in International Conference on Computer Vision, October 2003, pp. 1110–1116. [9] K. Smith, D. Gatica-Perez, and J.-M. Odobez, “Using Particles to Track Varying Numbers of Interacting People,” in Conference on Computer Vision and Pattern Recognition, 2005. [10] Z. Khan, T. Balch, and F. Dellaert, “Mcmc-Based Particle Filtering for Tracking a Variable Number of Interacting Targets,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 11, pp. 1805–1918, 2005. [11] C. Yang, R. Duraiswami, and L. Davis, “Fast multiple object tracking via a hierarchical particle filter,” in International Conference on Computer Vision, 2005. [12] T. Mauthner, M. Donoser, and H. Bischof, “Robust Tracking of Spatial Related Components,” in International Conference on Pattern Recognition, 2008. [13] K. Okuma, A. Taleghani, N. de Freitas, J. Little, and D. Lowe, “A Boosted Particle Filter: Multitarget Detection and Tracking,” in European Conference on Computer Vision, May 2004. [14] P.Willet, Y.Ruan. and R.Streit, “The PMHT: Its problems and some solutions,” in IEEE Transactions on Aerospace and Electronic Systems, vol.38 no.3, pp.738-754 (Jul.2002). [15] A. Perera, C. Srinivas, A. Hoogs, G. Brooksby, and H. Wensheng, “Multi-Object Tracking Through Simultaneous Long Occlusions and Split-Merge Conditions,” in Conference on Computer Vision and Pattern Recognition, June 2006, pp. 666–673. [16] Wu, B., Nevatia, R., “Detection and Tracking of Multiple, Partially Occluded Humans by Bayesian Combination of Edgelet based Part Detectors,” in International Journal of Computer Vision (2007) 47 [17] C. Huang, B. Wu, and R. Nevatia, “Robust Object Tracking by Hierarchical Association of Detection Responses,” in European Conference on Computer Vision, 2008, pp. 788–801. [18] P. Nillius, J. Sullivan, and S. Carlsson, “Multi-Target Tracking - Linking Identities Using Bayesian Network Inference,” in Conference on Computer Vision and Pattern Recognition, 2006, pp. 2187– 2194. [19] R. E. Bellman, Dynamic Programming. Princeton University Press, 1957. [20] J. Wolf, A. Viterbi, and G. Dixon, “Finding the Best Set of K Paths Through a Trellis With Application to Multitarget Tracking,” in Aerospace and Electronic Systems, IEEE Transactions on, vol. 25, no. 2, pp. 287–296, March 1989. [21] H. Jiang, S. Fels, and J. Little, “A Linear Programming Approach for Multiple Object Tracking,” in Conference on Computer Vision and Pattern Recognition, 2007, pp. 744–750. [22] L. Zhang, Y. Li, and R. Nevatia, “Global Data Association for Multi-Object Tracking Using Network Flows,” in Conference on Computer Vision and Pattern Recognition, 2008. [23] L. R. Rabiner and B. H. Juang, “An introduction to hidden Markov models,” in IEEEASSP Mag., pp. 4-16, Jan. 1986. [24] L. R. Rabiner. “A tutorial on hidden Markov models and selected applications in speech recognition,”in Proc. IEEE, vol. 77, no. 2, pp. 257-286, Feb. 1989. [25] A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimal decoding algorithm,” in IEEE Trans. Information Theory, vol. IT-13, pp. 260-269, Apr. 1967. [26] G.D. Forney, “The Viterbi algorithm,” in Proc. IEEE, vol. 61, pp. 268-278, Mar. 1973. [27] J. Martínez-del-Rincón, E. Herrero, J. Raúl, C. Orrite, C. Medrano, M. Montañés, “Multicamera sport player tracking with Bayesian estimation of measurements,” in Optical Engineering, Apr. 2009