Login Form

En este artículo, se describió un pequeño proyecto para identificar un plumón en una imagen. Para la segmentación, se hizo uso del conocimiento previo que se tenía del ambiente, en el cuál el color del fondo era conocido y contrastaba con los objetos a ser analizados por lo que bastaba con, por decirlo así, eliminar de la imagen ese color para encontrar el objeto a analizar.

Para ese pequeño proyecto, esa sencilla técnica de segmentación fue más que suficiente, pero; ¿qué pasa cuando no tenemos un control del fondo contra el que correrá nuestra aplicación?, o más aún, ¿qué pasa cuando nos enfrentamos con fondos realmente complejos como paisajes o calles donde la iluminación cambia constantemente y algunos elementos del fondo no se encuentran estáticos (como por ejemplo las hojas de un árbol que se mueve con el viento)?. Pues bien, la respuesta obvia es que necesitamos un algoritmo más robusto y complejo que nos permita modelar eficientemente este tipo de fondos.

Existen varios algoritmos que llevan a cabo dicha tarea, todos con ciertas ventajas y desventajas. En este artículo se explicará uno de ellos, bastante popular, propuesto por Chris Stauffer y W.E.L Grimson en su artículo "Adaptive background mixture models for real-time tracking" que utiliza Conjuntos de Distribuciones Gaussianas o Mezclas de Gaussianas (del inglés Mixtures of Gaussians ó MoG) para modelar el fondo y el cuál se adapta a cambios en la iluminación y en el fondo mismo.

 

 

 

A grosso modo, la idea básica de este algoritmo es modelar cada pixel de la imagen, mediante una serie de componentes gaussianas donde la media representa el valor con más probabilidades de ser observado y la desviación estándar qué tanto puede variar ese valor (realmente hay más detalles pero ese es un resumen). Cada componente representa el posible valor del pixel en un momento dado, es decir, el fondo ya no sólo puede tener un sólo valor, sino n posibles diferentes valores dependiendo nuestro número de componentes. En uno de los párrafos anteriores, poníamos el ejemplo de un árbol movido por el viento en cierta zona de la imagen. En ese caso, un sólo pixel podría tener un valor de verde cuando una hoja lo ocupa, un valor de café cuando es la rama la que lo ocupa y quiza el azul del cielo cuando ni la rama ni la hoja lo ocupan, pues bien, cada componente se encargará de modelar esas diferentes situaciones.

Teória y Supuestos

Stauffer y Grimson utilizan un enfoque probabilístico / estadistico y asumen que los objetos que forman parte del fondo de una escena son visibles por más tiempo que los objetos del primer plano y asumen también que sus colores pueden ser modelados por una distribución Gaussiana donde la media es el valor del color de la supeficie en cuestión y la varianza modela los cambios en la intensidad del color debido a ruido en la cámara, cambios en la iluminación o la propia textura del objeto.

Ahora bien, la escena está formada por una seria de superficies u objetos desconocidos y escondidos que sólo pueden ser vistos indirectamente a través del valor \(X\) asociado a un pixel dado y son representados por una serie de estados  \(k\in\{1,2,3,...,K\}\). De esos \(K\) estados, sólo se consideran como parte del fondo algunos cuantos y el resto se asume forman parte del primer plano estando cada estado ponderado con un peso \(w_k\) el cuál representa la probabilidad a priori de que la superficie \(k\) aparezca en el área visible por el pixel dado.

Estas superficies representadas por los \(k\) estados tienen una distribución\(f(X|k)\) debido a los cambios de intensidad ya mencionados por lo que el valor observado para un pixel en un momento dado \(t\) se consideran como muestra de una variable aleatoria\(X\) que incluye el comportamiento de \(k\) y  puede ser de una o varias dimensiones dependiendo el número de valores que usemos para formar el color; por ejemplo, una si usamos imágenes en escala de grises o tres en RGB donde \(X\) sería un vector de tres dimensiones,

Independientemente del número de dimensiones de nuestro vector, se utiliza un sólo valor para la varianza lo cuál quiere decir que para el caso de los colores en RGB, se asume que las tres dimensiones son independientes y que todas ellas tienen la misma varianza, es decir, se utiliza un sólo escalar para representar la varianza. 

En resumen,  el algoritmo provee un mecanismo para, dada una muestra en un tiempo \(t\), decidir cuál de los \(k\) estados es más probable que modele la variable \(X\) observada así como un procedimiento para separar aquellos estados que representan el fondo de los que representan el primer plano.

Dado el contexto anterior, podemos describir el algoritmo dando pequeñas explicaciones en las partes críticas.

 

Fases del Algoritmo

  • Inicialización
  • Estimación del Estado Actual
  • Segmentación del Fondo o Primer Plano

 

Inicialización

  • Crear el modelo inicial.

El algoritmo comienza inicializando el modelo para el video con valores predeterminados, es decir, si tenemos imágenes de ancho \(x\) y altura \(y\) con un parámetro de \(K\) gaussianas, creamos \(x*y*K\) gaussianas (media y desviación estandar) así como sus pesos iniciales. En mi implementación, he decidido usar un valor por default de cero para la media y desviación estándar y un peso por default de \(1/K\).

 

Estimación del Estado Actual

  • Para el valor \(X\) de cada pixel en un frame dado, comparar contra cada uno de sus componentes y decidir si hace match. La publicación de Stauffer y Grimson indica que se considera un match si el valor se encuentra dentro de 2.5 desviaciones estandar por lo que debemos expresar \(X\) en términos de la desviación estándar obteniendo su puntuación z (\(z=(X-\mu)/\sigma\)).
  • Para las distribuciones que hicieron match, actualizar su media y desviación estandar para que la varianza empiece a decrecer y la media se ajuste hacie el valor recién observado de acuerdo a las siguientes fórmulas:
  1. \(\mu_{k,t}=(1-\rho)*\mu_{k.t-1}+\rho X_t\)
  2. \(\sigma^2_t=(1-\rho) \sigma^2_{t-1}+\rho(X_t-\mu_t)^T(X_t-\mu_t)\)
  3. Donde \(\rho=\alpha\mathcal{N}(\mu,\sigma^2)\) y \(\alpha\) es un parámetro con el que hay que experimentar con diversos valores entre 0 y 1. \(\alpha\) es la razón de aprendizaje y define qué tan rápido se mueven los nuevos valores hacia la media observada y qué tan rápido decrece la varianza.
  • Actualizar los pesos de todos los componentes de manera que los que hicieron match se incrementen y los que no se decrementen usando la siguiente fórmula: \(w_{k,t}=(1-\alpha)w_{k,t-1}+\alpha(M_{k,t})\) donde \(M_{k,t}\) es 1 para las  distribuciones que hicieron match y 0 para las que no.
  • Normalizar los pesos (dividirlos entre la sumatoria de los mismos de manera que el total de 1).
  • Ordenar los componentes por peso.
  • Si ningún componente hizo match, reemplazar el de menos peso por una distribución nueva con media igual a \(X\) y \(\sigma^2\) alta. En mi implementación, debido a que sólo estoy trabajando con imágenes en escala de grises, decidí usar una varianza de 49 (se puede experimentar con diversos valores).
  • Si hubo un match, obtener las primeras \(B\) distribuciones cuya sumatoria de pesos sea mayor que un umbral \(T\):
  • Si la distribución que hizo match se encuentra entre las primeras \(B\), es parte del fondo y si no, del primer plano. Como se ve, este valor \(B\) se determina de manera dinámica y es el número de gaussianas ordenadas de mayor a menor por sus pesos cuya sumatoria de pesos representan el porcentaje que queremos considerar como fondo. Si usamos un porcentaje muy bajo, nuestro modelo puede llegar a ser unimodal, es decir, que sólo se acepte un componente para el fondo mientras que si \(T\) es suficientemente alto, nuestro modelo se convierte en multimodal aceptando varios componentes para la representación del fondo. De igual manera que con la varianza y la razón de aprendizaje, hay que experimentar con diferentes valores para este parámetro para un video dado.

A continuación les dejo la implementación del algoritmo en JAVA. Como lo que me interesa es el algoritmo para el modelado del fondo y no el acceso y procesamiento de bajo nivel del video, utilicé la librería BoofCV para acceder al video de manera fácil y OJO, es sólo una prueba de concepto realizada en un fin de semana por interés personal por lo que no esperen ver un algoritmo optimizado para usarse en producción y para la actualización de la media y la varianza / desviación estándar, seguí el mismo enfoque que utiliza OpenCV: no utilizar la función de distribución de probabilidad por que me alentaba mucho el programa. El programa lo pueden descargar de aquí.

Nota: Las dos ventanas (imagen sin procesar y procesada) salen en la misma posición por lo que deben mover una de ellas para ver ambas y deben ajustar la ruta del video en la clase Main.

 

For the english speakers, I'm providing a quickly implemented proof of concept in JAVA which follows OpenCV approach for updating mean and standard deviation / variance and which uses BoofCV for processing the videos.

Note: Both windows are in the same initial position. You have to drag one to see both of them and you need to adjust the location of the video in the Main class

Add comment


Security code
Refresh

contacts Contactanos

 

bugs Reportar bugs

about Acerca de www.tecnohobby.net

Go to top