DeepSORT y los algoritmos de rastreo (tracking)
Rubén Rodríguez Abril
El rastreo reconstruye la trayectoria de los objetos a lo largo de una secuencia de vídeo, manteniendo su identidad entre fotogramas sucesivos. Algoritmos como DeepSORT combinan las detecciones proporcionadas por YOLO con cálculos previos de trayectoria, así como con embeddings de apareciencia para seguir la pista de los objetos, creando trayectorias coherentes y etiquetadas.
Introducción
El rastreo (tracking) es el proceso mediante el cual se reconstruye la trayectoria de uno o varios objetos a partir de observaciones sucesivas, manteniendo para cada uno de ellos una identidad estable a lo largo del tiempo. Los algoritmos de rastreo reciben las detecciones generadas por un modelo como YOLO y las enlazan entre fotogramas para producir trayectorias temporalmente coherentes y etiquetadas.
Figura 1. La labor del rastreo multiobjetos (Multi-Objet Tracking, MOT) es identificar, a lo larbo del tiempo, a cada uno de los objetos de la escena. Fuente: Wikipedia.
Entre los algoritmos de rastreo más prominentes se encuentra DeepSORT, propuesto en 2017 y convertido desde entonces en una referencia dentro del campo de la visión artificial, con aplicaciones en ámbitos como la vigilancia, los vehículos autónomos, la gestión del tráfico o el análisis de multitudes.
La arquitectura de DeepSORT se divide en dos ramas paralelas, de las cuales sólo una emplea aprendizaje profundo. Los resultados de ambas se combinan al final para realizar la asociación entre tracks y nuevos objetos.
La rama utiliza algoritmos convencionales y se articula en torno a dos componentes fundamentales: el filtro de Kalman y la distancia de Mahalanobis. Kalman estima dónde debería encontrarse cada objeto en el nuevo fotograma y determina la incertidumbre asociada a esa estimación. Cuando YOLO proporciona las nuevas detecciones, la distancia de Mahalanobis permite calcular la distancia espacial entre esa estimación y las nuevas ventanas efectivamente detectadas.
Figura 2. Los algoritmos de rastreo atribuyen a cada objeto una etiqueta, que es mantenida a lo largo de los diversos fotogramas. Fuente: DeepSORT.
Filtro de Kalman
Dentro del filtro de Kalman, dos son los elementos matemáticos fundamentales: el estado interno Xi de cada objeto rastreado -cada track, y la matriz de covarianza Pi, que cuantifica la incertidumbre que se atribuye a dicho estado. En DeepSORT, el estado interno se compone de ocho variables:
X=(x,y,a,h,x˙,y˙,a˙,h˙),
que describen a los parámetro de la ventana delimitadora -x e y indican la posición de su centro; a, la relación de aspecto; y h, su altura-, junto con sus respectivas velocidades de cambio (x˙,y˙,a˙,h˙).
Matriz de transición
La evolución temporal de este estado se calcula mediante una matriz de transición F:
Xt+1=FXt+wt,
donde wt representa las perturbaciones que el modelo de movimiento no puede anticipar exactamente. DeepSORT parte de una hipótesis de velocidad constante, de modo que la posición, altura y relación de aspecto de la ventana en el siguiente fotograma se proyectan a partir de sus valores actuales y de sus correspondientes velocidades de cambio.
Figura 3. La primera línea de la matriz dice xt+1 = xt+Δtvx.
Matriz de covarianza
Junto con el estado X y su matriz de evolución F, el filtro de Kalman mantiene una matriz de covarianza P, que representa la incertidumbre asociada a la estimación y las relaciones estadísticas entre sus diferentes variables. En lugar de considerar que el objeto se encuentra exactamente en el estado X, podemos imaginar que alrededor de éste hay una nube de probabilidad, descrita mediante una distribución gaussiana: X señala el centro de esa nube, mientras que P determina su extensión y orientación.
Figura: 4. El filtro de Kalman calcula el estado interno X de cada avión, para el siguiente fotograma, que viene representado por el punto situado en el extremo de la trayectoria. La matriz de covarianza P determina la extensión y forma de la nube. Si los elementos diaognales de la matriz fueran nulos, la nube colapsaría e un punto.
Los elementos de la diagonal de P representan la varianza asociada a cada variable: cuanto mayor sea su valor, mayor será la incertidumbre del filtro respecto a esa componente del estado. Los elementos situados fuera de la diagonal representan, por el contrario, las covarianzas entre pares de variables. Una covarianza positiva indica que sus errores tienden a desviarse conjuntamente en el mismo sentido (p.e. vibraciones diagonales de una cámara); una negativa, que tienden a hacerlo en sentidos opuestos; y una próxima a cero, que apenas existe relación lineal entre ambas incertidumbres.
Figura 5. Los elementos diagonales de p, muestran la varianza, es decir, cuánto se aleja la distribución de probabilidad de la media. Para una varianza de 0, la incertidumbre es nula y la confianza del modelo en su predicción es máxima.
Cálculo de residuos
Cuando aparece un nuevo fotograma, YOLO proporciona una nueva medición zi de las cuatro variables observables de ventana (x,y,a,h), para cada objeto detectado. Estas mediciones se comparan con las predicciones realizadas por el filtro de Kalman para los objetos que ya estaban siendo rastreados, con el fin de establecer la correspondiente asociación temporal:
r1 = z1 − HXi.
r2 = z2 − HXi.
r3 = z3 − HXi.
donde H es una matriz de proyección que extrae del estado interno Xi del objeto i las cuatro variables directamente observables (x,y,a,h), dejando fuera sus velocidades. Los vectores ri, denominados residuos, expresan así la diferencia entre la posición prevista para el objeto i y las nuevas ventanas efectivamente detectadas por YOLO.
Distancia de Mahalanobis
La operación esencial del rastreo consiste en determinar qué detección del nuevo fotograma corresponde a cada uno de los objetos que ya estaban siendo seguidos. Para ello, DeepSORT utiliza, entre otros criterios, la distancia de Mahalanobis, una métrica que compara cada nueva observación con la predicción realizada por el filtro de Kalman.
Como hemos visto, para cada pareja formada por un objeto rastreado y una nueva detección existe un residuo (r), que expresa la diferencia entre la posición y dimensiones previstas para la ventana y las observadas por YOLO. A partir de este residuo se calcula la distancia de Mahalanobis:
d2M=r⊤S−1r (distancia de Mahalanobis)
d2M=r⊤r (distancia euclídea)
donde (S) es la matriz de covarianza de la innovación, que cuantifica la incertidumbre total asociada al residuo, combinando la correspondiente al filtro de Kalman (expresada a través de P), con la del detector (representada por R). La distancia obtenida no depende, por tanto, únicamente de la separación entre predicción y observación, sino también del grado de incertidumbre existente en cada dirección. Esta característica distingue a Mahalanobis de la distancia euclídea.
DeepSORT calcula así una distancia de Mahalanobis para cada pareja potencial entre los objetos rastreados y las nuevas detecciones. Aquellas parejas cuya distancia supera un determinado umbral son descartadas como asociaciones incompatibles, mientras que las restantes continúan en el proceso de asociación, en el que interviene también la información de apariencia proporcionada por la segunda rama del algoritmo.
Comparación de embeddings
La segunda rama de DeepSORT incorpora Deep Learning. Su función consiste en analizar la apariencia visual de cada objeto detectado y representarla mediante un vector numérico o embedding. Para ello, la imagen contenida dentro de cada ventana delimitadora es procesada por una red neuronal convolucional (CNN). El resultado es un vector de 128 dimensiones que actúa como descriptor de apariencia.
DeepSORT puede comparar así la apariencia de una nueva detección con los objetos que están siendo rastreado. Para ello utiliza la distancia coseno, que mide el grado de semejanza existente entre sus respectivos embeddings. Cuanto menor sea esta distancia, mayor será la similitud visual entre ambos:
distanacia_apariencia= 1 – ej·ek,
donde ej y ek representan dos embeddings normalizados. Dos vectores orientados en una dirección semejante producen una distancia próxima a 0, mientras que valores mayores indican una menor similitud de apariencia.
Asociación de nuevos objetos con tracks
Para que una detección del nuevo fotograma pueda asociarse con un objeto rastreado, tanto la distancia de Mahalanobis como la distancia coseno deben permanecer por debajo de determinados umbrales:
d_Mahalanobis ≤ u(1)
d_apariencia ≤ u(2)
DeepSORT sólo admite, por tanto, aquellas correspondencias que resultan compatibles tanto con el movimiento previsto como con la apariencia del objeto. El problema surge cuando varias detecciones satisfacen simultáneamente ambas condiciones para varios objetos rastreados, haciendo posible más de una combinación.
Además, un objeto puede permanecer varios fotogramas sin ser detectado —por ejemplo, como consecuencia de una oclusión— sin que su rastreo sea eliminado inmediatamente. Durante ese intervalo, el filtro de Kalman continúa proyectando su estado, aunque la incertidumbre de la predicción aumenta progresivamente. Si el objeto reaparece, DeepSORT puede asociar la nueva detección con ese rastreo todavía activo y recuperar así su identidad anterior.
Para resolver las posibles ambigüedades, DeepSORT utiliza la denominada cascada de asociación (matching cascade). Los rastreos se ordenan en función del tiempo transcurrido desde su última detección, concediendo prioridad a los observados más recientemente. En cada nivel de la cascada se comparan estos rastreos con las detecciones que todavía no han sido asignadas.
Cada posible correspondencia recibe un coste de asociación, obtenido mediante una combinación ponderada de la distancia de Mahalanobis (d_Mahalanobis) y la distancia coseno entre los embeddings (d_apariencia):
ci,j = λ*d_Mahalanobis + (1-λ*)d_apariencia
donde λ determina el peso relativo de ambos criterios. Cuando λ=1, el coste depende exclusivamente del movimiento; cuando λ=0, únicamente de la apariencia; y los valores intermedios combinan ambas fuentes de información. En los experimentos originales de DeepSORT, los autores comprobaron que λ=0 resultaba adecuado cuando existía un movimiento considerable de la cámara, manteniendo en cualquier caso la distancia de Mahalanobis como criterio para descartar asociaciones espacialmente incompatibles.
Cuando existen varias correspondencias posibles —que no han sobrepasado los umbrales establecidos—, DeepSORT utiliza el llamado algoritmo húngaro, que selecciona la combinación de asociaciones (todos los objetos) con menor coste total. La asociación se realiza en cascada: se comienza con los rastreos más recientes y el procedimiento se repite sucesivamente con aquellos que llevan más tiempo sin ser observados y con las detecciones que hayan quedado disponibles.
Actualización de estado interno
Una vez emparejado el objeto rastreado con una de las detecciónes, toca corregir el estado interno del objeto. Mediante la denominada ganancia de Kalman (K), el filtro determina cuánto debe confiar en la nueva observación frente a su propia predicción y actualiza tanto las variables observables como las velocidades estimadas. K determina qué proporción del residuo debe incorporarse a la predicción:
Xt+1=Xt+1 + Kt+1rt+1.
Cuando K se aproxima a 0, el filtro concede mayor confianza a su propia predicción y apenas la modifica a partir de los datos proporcionados por YOLO. Cuando K se aproxima a 1, concede mayor confianza a la nueva observación y la corrección se aproxima al residuo completo. De este modo, el filtro actualiza tanto las variables directamente observables como las velocidades estimadas y, paralelamente, modifica la matriz de covarianza P.
La razón por la que DeepSORT no descansa exclusivamente en las mediciones proporcionadas por YOLO es que éstas pueden contener ruido, debido a múltiples causas: vibraciones mecánicas de la cámara, cambios de iluminación, oclusiones parciales o pequeñas variaciones en la ventana delimitadora estimada por el detector. El filtro de Kalman permite combinar estas observaciones imperfectas con la evolución temporal esperada del objeto, obteniendo una estimación más estable de su estado.
Conclusiones
En resumen, el funcionamiento de DeepSORT puede reducirse a una secuencia de cinco operaciones fundamentales:
Predicción: el filtro de Kalman proyecta el estado interno de cada objeto rastreado hacia el siguiente fotograma, estimando su nueva posición y la incertidumbre asociada.
Detección: YOLO identifica los objetos presentes en el nuevo fotograma y proporciona sus correspondientes ventanas delimitadoras.
Asociación: cada nueva detección se compara con los rastreos existentes. La distancia de Mahalanobis determina su compatibilidad con el movimiento previsto, mientras que la distancia coseno hace lo propio con su apariencia.
Emparejamiento: entre las asociaciones posibles, el denominado algoritmo húngaro determina la combinación de correspondencias con menor coste, siguiendo el orden establecido por la cascada de asociación.
Actualización: una vez seleccionada la detección correspondiente a cada rastreo, su residuo se incorpora al estado interno mediante la ganancia de Kalman. El filtro actualiza simultáneamente la matriz de covarianza P, incorporando así la nueva información al siguiente ciclo de predicción.
Lecturas Recomendadas
SERIES
