Algoritmo de condensación

El algoritmo de condensación ( propagación de densidad condicional ) es un algoritmo de visión artificial . Su principal aplicación consiste en detectar y rastrear el contorno de objetos que se mueven en un entorno complejo. El seguimiento de objetos es uno de los aspectos más básicos y difíciles de la visión artificial y, por lo general, un requisito previo para el reconocimiento de objetos . Identificar qué píxeles de una imagen conforman el contorno de un objeto es un problema complejo. La condensación es un algoritmo probabilístico que intenta resolver este problema.

El algoritmo en sí es descrito en detalle por Isard y Blake en una publicación en el International Journal of Computer Vision en 1998. ^{[ 1 ]} Una de las facetas más interesantes del algoritmo es que no realiza cálculos en cada píxel de la imagen. En cambio, los píxeles a procesar se eligen aleatoriamente, y solo se procesa un subconjunto de ellos. La naturaleza probabilística del enfoque permite plantear múltiples hipótesis sobre lo que se mueve. Las funciones de evaluación provienen en gran medida de trabajos previos en el área e incluyen muchos enfoques estadísticos estándar. La parte original de este trabajo es la aplicación de técnicas de estimación de filtros de partículas.

La creación del algoritmo se inspiró en la incapacidad del filtro de Kalman para realizar un seguimiento de objetos eficaz en presencia de un ruido de fondo significativo. La presencia de ruido tiende a generar distribuciones de probabilidad para el estado del objeto que son multimodales y, por lo tanto, el filtro de Kalman no las modela adecuadamente. El algoritmo de condensación, en su forma más general, no requiere suposiciones sobre las distribuciones de probabilidad del objeto ni de las mediciones.

El algoritmo de condensación busca resolver el problema de estimar la conformación de un objeto descrito por un vector.${\displaystyle \mathbf {x_{t}} }$en ese momento${\displaystyle t}$, dadas las observaciones${\displaystyle \mathbf {z_{1},...,z_{t}} }$de las características detectadas en las imágenes hasta el momento actual inclusive. El algoritmo genera una estimación de la densidad de probabilidad condicional del estado.${\displaystyle p(\mathbf {x_ {t}} |\mathbf {z_ {1},...,z_ {t}} )}$ mediante la aplicación de un filtro no lineal basado en el muestreo factorizado y puede considerarse como un desarrollo de un método de Montecarlo . ^{[ 1 ]}${\displaystyle p(\mathbf {x_ {t}} |\mathbf {z_ {1},...,z_ {t}} )}$es una representación de la probabilidad de posibles conformaciones para los objetos basada en conformaciones y mediciones previas. El algoritmo de condensación es un modelo generativo ^{[ 2 ]} ya que modela la distribución conjunta del objeto y el observador.

La densidad condicional del objeto en el momento actual${\displaystyle p(\mathbf {x_ {t}} |\mathbf {z_ {1},...,z_ {t}} )}$se estima como un conjunto de muestras ponderadas e indexadas en el tiempo.${\displaystyle \{s_{t}^{(n)},n=1,...,N\}}$con pesas${\displaystyle \pi _{t}^{(n)}}$. N es un parámetro que determina el número de conjuntos de muestras elegidos. Una realización de${\displaystyle p(\mathbf {x_ {t}} |\mathbf {z_ {1},...,z_ {t}} )}$se obtiene mediante muestreo con reemplazo del conjunto${\displaystyle s_{t}}$con probabilidad igual al elemento correspondiente de${\displaystyle \pi _{t}}$. ^{[ 1 ]}

Las suposiciones de que la dinámica del objeto forma una cadena de Markov temporal y que las observaciones son independientes entre sí y de la dinámica facilitan la implementación del algoritmo de condensación. La primera suposición permite que la dinámica del objeto esté completamente determinada por la densidad condicional.${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )}$. El modelo de la dinámica del sistema determinado por${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )}$También debe seleccionarse para el algoritmo, y generalmente incluye dinámicas tanto deterministas como estocásticas .

El algoritmo se puede resumir mediante la inicialización en el tiempo${\displaystyle t=0}$y tres pasos en cada instante t :

Dado que el seguimiento de objetos puede ser un objetivo en tiempo real, la consideración de la eficiencia del algoritmo se vuelve importante. El algoritmo de condensación es relativamente simple en comparación con la intensidad computacional de la ecuación de Ricatti requerida para el filtrado de Kalman. El parámetro${\displaystyle N}$, que determina el número de muestras en el conjunto de muestras, implicará claramente una compensación entre eficiencia y rendimiento.

Una forma de aumentar la eficiencia del algoritmo es seleccionar un modelo con pocos grados de libertad para representar la forma del objeto. El modelo utilizado por Isard (1998) es una parametrización lineal de B-splines, donde las splines se limitan a ciertas configuraciones. Se encontraron configuraciones adecuadas determinando analíticamente combinaciones de contornos a partir de múltiples vistas del objeto en diferentes poses, y mediante análisis de componentes principales (ACP) sobre el objeto en deformación.

Isard y Blake modelan la dinámica del objeto.${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )}$como una ecuación de diferencias de segundo orden con componentes deterministas y estocásticas:${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )\propto e^{-{\frac {1}{2}}||B^{-1}((\mathbf {x_{t}} -\mathbf {\bar {x}} )-A(\mathbf {x_{t-1}} -\mathbf {\bar {x}} ))||^{2})}}$

dónde${\displaystyle \mathbf {\bar {x}} }$es el valor medio del estado, y${\displaystyle A}$,${\displaystyle B}$son matrices que representan los componentes deterministas y estocásticos del modelo dinámico, respectivamente.${\displaystyle A}$,${\displaystyle B}$, y${\displaystyle \mathbf {\bar {x}} }$se estiman mediante la estimación de máxima verosimilitud mientras el objeto realiza movimientos típicos. ^{[ 1 ] [ 3 ]}

El modelo de observación${\displaystyle p(\mathbf {z} |\mathbf {x} )}$no se puede estimar directamente a partir de los datos, lo que requiere hacer suposiciones para poder estimarlo. Isard (1998) supone que el desorden que puede hacer que el objeto no sea visible es un proceso aleatorio de Poisson con densidad espacial.${\displaystyle \lambda }$y que cualquier medición objetivo verdadera es insesgada y se distribuye normalmente con desviación estándar${\displaystyle \sigma }$.

El algoritmo de condensación básico se utiliza para rastrear un solo objeto en el tiempo. Es posible extender el algoritmo de condensación utilizando una única distribución de probabilidad para describir los estados probables de múltiples objetos y así rastrear varios objetos en una escena simultáneamente. ^{[ 4 ]}

Dado que el desorden puede provocar que la distribución de probabilidad del objeto se divida en múltiples picos, cada pico representa una hipótesis sobre la configuración del objeto. El suavizado es una técnica estadística que condiciona la distribución basándose en mediciones pasadas y futuras una vez completado el seguimiento, con el fin de reducir los efectos de los múltiples picos. ^{[ 5 ]} El suavizado no se puede realizar directamente en tiempo real, ya que requiere información de mediciones futuras.

El algoritmo puede utilizarse para la localización de robots móviles mediante visión artificial. ^{[ 6 ]} Sin embargo, en lugar de rastrear la posición de un objeto en la escena, se rastrea la posición de la plataforma de la cámara. Esto permite localizar globalmente la plataforma de la cámara a partir de un mapa visual del entorno.

También se han utilizado extensiones del algoritmo de condensación para reconocer gestos humanos en secuencias de imágenes. Esta aplicación del algoritmo de condensación influye en el rango de interacciones posibles entre humanos y computadoras. Se ha utilizado para reconocer gestos simples de un usuario en una pizarra blanca para controlar acciones como seleccionar regiones de la pizarra para imprimirlas o guardarlas. ^{[ 7 ]} Otras extensiones también se han utilizado para el seguimiento de varios automóviles en la misma escena. ^{[ 8 ]}

El algoritmo de condensación también se ha utilizado para el reconocimiento facial en una secuencia de vídeo. ^{[ 9 ]}

En el sitio web de Michael Isard se puede encontrar una implementación del algoritmo de condensación en C.

Se puede encontrar una implementación en MATLAB en Mathworks File Exchange .

En los foros de OpenCV se puede encontrar un ejemplo de implementación utilizando la biblioteca OpenCV .

• Filtro de partículas : la condensación es la aplicación de la estimación de remuestreo por importancia de muestreo (SIR) al seguimiento de contornos.