Implementación Codebook Model

1-      Estructuras de datos

En primer lugar crearemos la estructura del codebook:

Existira un codebook por pixel, con tantas entradas o codewords como indiquemos en numEntries. La variable t almacena el numero de pixeles procesados desde el inicio o desde la ultima operación de borrado.

La estructura para almacenar el codeword sería la siguiente:

Como podemos observar, el uso de memoría es muy optimizado ya que estaríamos consumiendo 4 bytes por canal y dos enteros por codeword . El número de canales podría ser 1, si solo modelaramos el canal del brillo (Y), o 3, para los 3 canales YUV, como es nuestro caso.

Max y min serían las fronteras de la “caja” y los parámetros learnHigh y learnLow los umbrales que podrían causar una generación de un nuevo codeword (si un pixel no se encontrara entre los límites de min – learnLow y max + learnHigh de cada uno de los

canales )

Los parámetros t_last_update y stale se utilizaran para poder eliminar codewords creados en la fase de entrenamiento y que sean utilizados con poca frecuencia. Stale coincidiría con el valor MNRL del modelo.

      2- Lógica del proceso

Los métodos utilizados para codificar el comportamiento del método serían :

El método update_codebook() se invocará para cada pixel de la imagen durante el periodo de entrenamiento, para formar el modelo de fondo adecuado . Esta función genera los codewords necesarios o va aumentando/disminuyendo las fronteras de cada uno de ellos. Por otro lado, va actualizando los valores de t_last_update cada vez que el codeword sea accedido, y de stale, con la cantidad de tiempo durante la que el codeword no ha sido accedido.

 Esta información se usará mas tarde para eliminar codewords despreciables, a través del método clear_stale_entries().

La sustracción de fondo la procesaremos utilizando la función background_diff(), donde utilizaremos el modelo de fondo aprendido, para discernir si el valor de un pixel corresponde al foreground o el background. Para ello, además de los valores min,max de los límites de un codeword, utilizaremos los valores maxMod y minMod representaran un umbral a modo de offset, que nos permitirán decidir.

En resumen, los pasos para aplicar esta técnica serían:

1-      Aprender el modelo de fondo durante un tiempo utilizando update_codebook().

2-      Limpiar entradas residuales via clear_stale_entries().

3-      Adaptar los valores de umbral maxMod y minMod para una segmentación optimizada de los objetos del foreground.

4-      Realizar la sustracción de fondo a través de background_diff().

5-      Periodicamente actualizar el modelo de fondo.

6-      Con menos frecuencia, limpiar los codewords residuales con clear_stale_entries().

ELIGIENDO METODO NO-PARÁMETRICO ADICIONAL

Para cerrar este primer bloque del PFC, se planteaba proceder a realizar una comparativa de los métodos de sustracción de fondo estudiados hasta ahora.

Estos métodos se pueden clasificar desde dos puntos de vista:

a-       Recursivos, aquellos que mantienen un único background que se va actualizando con cada nuevo frame, y No-Recursivos, aquellos que mantienen un buffer de N frames para calcular el background.

b-       Los estimadores Paramétricos y los No-Paramétricos. Los primeros sólo pueden usarse en el caso de que la función de densidad de probabilidad a estimar se asemeje con alguna de las distribuciones conocidas (distribución Gaussiana, de Poisson,...), es decir, todo estimador paramétrico sólo es válido para una cierta distribución estadística. En cambio, los segundos estimadores son válidos independientemente de la forma que tome la función de densidad de probabilidad.

Si recopilamos los métodos implementados hasta ahora, podemos ver que, desechando el método de diferencia simple que no nos aportaría nada, tendríamos un par de métodos paramétricos  (Runnig Gaussian Average y Mezcla de Gaussianas ) y solo uno no paramétrico ( Método de la media ).

 Se me antoja necesario incluir un método no-parámetrico adicional , para equilibrar la comparativa y su posterior presentación.

 He vuelto a revisar el estado del arte en este sentido, y se me presentan dos candidatos:

1-       Kernel Densisty Estimation (KDE)

2-       Codebook Model

Expongo una pequeña presentación de cada uno de ellos.

1- Kernel Density Estimation (KDE)



El método presentado por  Elgammal en el estudio Non-parametric model for background subtraction , utiliza el valor exacto de los píxeles como característica básica de modelado de fondo,manteniendo una muestra formada por un conjunto de valores de intensidad para cada píxel de la imagen y utilizando esta muestra para estimar la función de distribución de probabilidad de la intensidad de los píxeles.

 El modelo es capaz de estimar la probabilidad de cualquier valor de la intensidad observada recientemente.


El modelo de fondo se genera a través de una muestra de N  frames  de una secuencia de los valores de cada píxel.

Tras almacenar la muestra, se obtiene una estimación de densidad del píxel P ( I s,t) aplicando una función de estimación de densidad de núcleo K . La probabilidad que posee el píxel   I s,t  de pertenecer al fondo en cada instante t se calcula como:

Donde  I s,t  es un frame de video en el tiempo t y para el pixel s, K es la función Kernel (normalmente se usa una gaussiana ), y N es el número de frames anteriores utilizados para estimar la función P(.).

Asumiéndose la independencia entre los canales de color, se puede resumir el funcionamiento del sistema como productos de Kernels de una dimension:

Utilizando esta función de probabilidad, se considera que un píxel pertenece al frente si  P( I t ) es menor que un umbral , es decir, si no está englobado por esta distribución.

El valor de sigma puede ser fijo o preestimado siguiendo el método que presenta Elgammal  en su estudio.

2- Modelo Codebook (método elegido)

Este algoritmo es presentado por Kim, Chalidabhongse, Harwood, and Davis en el estudio Real-time foreground–background segmentation using codebook model.

He elegido implementar esta propuesta porque me ha parecido original en su propuesta, y diferente al resto de algoritmos de este tipo.

También aparece en el libro Learning OpenCV, que utilizo como documento de referencia para la librería OpenCV que estamos usando en el desarrollo del PFC. De hecho , junto con el método de la media, es la única referencia  método avanzado de sustracción de fondo.

El método codebook (libro de códigos), construye de manera estadística un modelo para el fondo en una secuencia de video, en donde cada píxel del recuadro es tratado de manera independiente. Por cada píxel se genera un número variable de codewords (palabras código), creados a partir de los valores observados del píxel durante la obtención del modelo. Finalmente por medio de comparaciones entre el valor del píxel a
evaluar y los codewords que conforman el modelo de fondo se extrae el primer plano de cada cuadro del video.

El método se presenta como un algoritmo de tiempo real para la segmentación de foreground-background, basándose en la representación de un modelo de fondo comprimido, obtenido a través de una serie de valores de entrenamiento , generando para cada pixel de la imagen un codebook . La representación de este codebook resulta muy eficiente en términos de memoria y velocidad de procesado, en comparación con otras técnicas de sustracción de fondo, y se comporta bien con escenas donde existan fondos con elementos en movimiento y cambios de iluminación.

Según los autores, otro métodos utilizados para este fin, presentan algunas desventajas frente a este. Por ejemplo, si nos fijamos en el método de mezcla de Gaussianas, en los fondos en los que hay variaciones rápidas, no se modelan de una forma precisa si utilizados pocas gaussianas. Además, en función del valor de la variable learning-rate, pueden presentarse problemas, para valores bajos los cambios repentinos de background y para valores altos, los elementos con movimientos lentos pueden ser absorbidos como elementos del modelo del fondo.

En teoría este tipo de problemas, se resolverían con técnicas no paramétricas, como la descrita anteriormente (KDE), que estima la función de probabilidad de cada pixel utilizando varias muestras y se adapta rápidamente a los cambios del fondo, pero este tipo de técnicas no serían validas cuando se necesiten largos periodos de entrenamiento para modelar el fondo, debido a sus necesidades de memoria,e n este sentido el modelo codebook, presenta un algoritmo con una representación comprimida del modelo de fondo.

A continuación se muestra un ejemplo simple que serviría para ilustrar comose comporta el modelo. Un codebook está formado por cajas que van creciendo para cubrir los valores más frecuentes en el tiempo. En la imagen superior se muestra la forma de una onda en el tiempo y en la inferior pequeñas cajas que se crean para cubrir los valores y que van creciendo para englobar los valores cercanos. Si se presenta un nuevo valor muy lejano, se creará una nueva caja , que crecerá lentamente para englobar los nuevos valores.

En nuestro caso necesitaremos crear un codebook de “cajas” para cubrir 3 dimensiones, los tres canales que forman cada uno de los pixeles de la imagen.

A continuación mostramos las estructuras básicas para formar el modelo de fondo y el algoritmo utilizado.

Para cada píxel del modelo de fondo, el algoritmo crea un numero de
codewords, estos codewords se componen de un vector  vi = (R,G,B) y una séxtupla con los siguientes parámetros:

Los dos primeros representarían las cotas máxima y mínima de brillo que acepta el codeword, el siguiente la frecuencia con la que el codeword ocurre, el valor MNRL sería el intervalo más largo en el periodo de entrenamiento en el que el codeword no ha sido accedido y p ,q el primer y último acceso a ese codeword.


Durante la secuencia de entrenamiento del algoritmo las nuevas muestras se comparan con el codebook existente para determinar si hay algún codeword coincidente,si lo hay se actualiza y si no lo hay se crea uno nuevo con los valores actuales. A continuación se muestra el pseudocódigo utilizado en la secuencia de entrenamiento:

Las condiciones (a) y (b) se consideraría cumplidas cuando los colores puros de la muestra y el codeword estuvieran lo suficientemente cercanos y el brillo de la muestra se encuentre entre los limites de brillo del codeword. Los detalles para el calculo de esos valores aparecen en el documento del estudio.

Una vez creado el modelo del background en la secuencia de entrenamiento, pasaríamos a procesar la secuencia de test, donde actuaríamos deacuerdo al siguiente pseudocódigo:

Aquí entendemos E2 como el umbral de detección.  Si hay algún codeword que cumpla (a) y (b) se considera píxel fondo y se actualiza el codeword, sino se considera pixel en movimiento.


Este algoritmo básico puede ser extendido para eliminar los objetos que durante la secuencia de entrenamiento estaban en movimiento o que permanecían estáticos y han sido movidos posteriormente. Para este objetivo se utiliza un modelado por capas, teniendo en todo momento diversos modelos de fondo. Este algoritmo por capas se puede extender añadiendo más capas para una detección más refinada.

La propuesta original del método esta enfocada para espacios de color RGB. En nuestro caso, siguiendo las recomendaciones de la guía de referencia de OpenCV, vamos a innovar en este sentido, y vamos a hacer una implementación en en base al espacio de color YUV , ya que resulta más útil una representación en la que el eje de las X este relacionado con el brillo, ya que , empíricamente, la mayoría de los cambios en un modelo del fondo están relacionados con variaciones en los valores del brillo y no del color.