aplicación del filtro de partículas al seguimiento de un...

ESCUELA SUPERIOR DE INGENIERÍA INFORMÁTICA

INGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMAS

Curso Académico 2008 / 2009

Proyecto de Fin de Carrera

Aplicación del filtro de partículas al seguimiento de un objeto en 2D y extracción de características.

-Autor-

Efrén Gómez del Casar.

-Tutores-

Juan José Pantrigo Fernández.

Ángel Sánchez Calle

Febrero 2009

Agradecimientos

En primer lugar, a mis tutores Ángel Sánchez Calle y Juan José Pantrigo

Fernández por su ayuda y dedicación.

A mi familia, por creer en mí siempre.

A mis amigos, por ayudarme en los malos momentos y hacerme feliz en los

buenos.

A mi compañero Javier Hernández Sánchez, por su colaboración con los videos

sintéticos.

Índice general Agradecimientos

Resumen ....................................................................................................................................... 1

1. Capitulo 1 : Introducción ....................................................................... 3

1.1 Seguimiento de objetos en movimiento ................................................................... 5

1.1.1 El problema de la visión dinámica ............................................................................. 5

1.1.2 Objetivos del seguimiento .......................................................................................... 6

1.1.3 Estudio del movimiento ............................................................................................. 6

1.1.3.1 Hipótesis de continuidad ................................................................................. 6

1.1.3.2 Inercia .............................................................................................................. 7

1.1.3.3 Hipótesis o restricciones de suavidad del movimiento .................................... 8

1.1.4 Métodos de detección de movimiento .......................................................................... 8

1.1.5 Técnicas de detección de movimiento: Sustracción de Fondo ..................................... 9

1.1.6 Aplicaciones del seguimiento visual .................................................................... 10

1.2 Filtro de Partículas ................................................................................................... 11

1.2.1 Operaciones ................................................................................................................ 12

1.2.1.1 Multiplicación por una función o cálculo de pesos ........................................ 12

1.2.1.2 Aplicación de un modelo de dinámica ........................................................... 14

1.2.1.3 Remuestreo o Resampling .............................................................................. 15

1.2.2 Descripción del algoritmo ......................................................................................... 16

2. Capítulo 2 : Objetivos ........................................................................... 19

2.1 Objetivos principales ............................................................................................. 19

2.2 Objetivos parciales ................................................................................................. 20

3. Capítulo 3: Descripción Informática .................................................. 23

3.1 Herramientas utilizadas .......................................................................................... 23

3.1.1 El lenguaje de programación MATLAB ................................................................. 23

3.1.2 VideoSyn ................................................................................................................. 24

3.1.3 Open video converter .............................................................................................. 24

3.1.4 Longitech quickcam SDK ....................................................................................... 25

3.2 Requisitos ............................................................................................................... 26

3.2.1 Requisitos funcionales .............................................................................................. 26

3.2.2 Requisitos no funcionales ......................................................................................... 27

3.3 Modelo de desarrollo software ............................................................................... 28

3.4 Diseño e implementación ....................................................................................... 30

3.4.1 Tratamiento de imágenes: Sustracción de fondo ...................................................... 30

3.4.2 Filtro de partículas para seguimiento de objetos en 2D ........................................... 31

3.4.4 Funcionalidad para extracción de características geométricas de un objeto en 2D .. 36

3.4.5 Diagrama de bloques Filtro de Partículas ................................................................ 43

4. Capítulo 4: Resultados Experimentales .............................................. 45

4.1 Experimento 1: Objeto no deformable ................................................................... 45

4.2 Experimento 2: Objeto deformable ........................................................................ 48

4.3 Experimento 2: Video sintético ............................................................................. 51

4.1.1 Análisis ..................................................................................................................... 53

5. Capítulo 5: Conclusiones ...................................................................... 55

5.1 Objetivos alcanzados ............................................................................................. 55

5.2 Mejoras y futuras líneas de trabajo ........................................................................ 56

Bibliografía ................................................................................................................................ 59

Índice figuras Figura 1.1 Etapas típicas en un sistema de Visión Artificial ............................................ 4

Figura 1.2 Fotogramas de una secuencia de imágenes a través del tiempo ..................... 5

Figura 1.3 Esquema de estimación usado por el Filtro de Partículas ............................. 12

Figura 1.4 Funcionamiento de la multiplicación sobre partículas .................................. 13

Figura 1.5 Funcionamiento del algoritmo de selección con pesos acumulados ............. 16

Figura 1.6 Pseudocódigo del algoritmo Filtro de Partículas ......................................... 17

Figura 3.1 Cámara web Longitech Quickcam 9000 Pro ................................................ 25

Figura 3.2 Modelo de desarrollo en espiral representado gráficamente ......................... 29

Figura 3.3 Ejemplo de sustracción de fondo .................................................................. 30

Figura 3.4 Ejemplo de centroide en una figura geométrica ........................................... 36

Figura 3.5 Representación del perímetro de un objeto cualquiera en 2D ...................... 37

Figura 3.6 Representación de la translación de coordenadas ......................................... 38

Figura 3.7 Ángulo formado entre vector creado y vector (0,1) ...................................... 38

Figura 3.8 Cuadrantes del eje de coordenadas ............................................................... 39

Figura 3.9 Representación cálculo área de un objeto ..................................................... 41

Figura 4.1 Captura 1 de un objeto no deformable en instante t=2s ................................ 46

Figura 4.2 Captura 2 de un objeto no deformable en instante t=5s ................................ 46

Figura 4.3 Captura 3 de un objeto no deformable en instante t=17s .............................. 47

Figura 4.4 Captura 1 de un objeto deformable en instante t=7s ..................................... 49

Figura 4.5 Captura 2 de un objeto deformable en instante t=17s ................................... 49

Figura 4.6 Captura 3 de un objeto deformable en instante t=33s ................................... 50

Figura 4.7 Captura 1 de un video sintético en instante t=20s ........................................ 52

Figura 4.8 Captura 2 de un video sintético en instante t=40s ........................................ 52

Índice Fórmulas (1.1). Hipótesis de continuidad del movimiento matemáticamente expresado ................. 6

(1.2). Consideración de la velocidad ................................................................................. 7

(1.3). Consideración de la aceleración............................................................................... 7

(1.4). Imagen diferencia..................................................................................................... 9

(1.5). Definición matemática de una partícula ................................................................ 11

(1.6). Definición matemática conjunto partículas S ....................................................... 11

(1.7). Condiciones nuevo conjunto partículas S tras aplicar un modelo de dinámica 14

(1.8). Condiciones del nuevo conjunto partículas S’ tras aplicar remuestreo .................. 15

(3.1). Ecuación pixel en imagen diferencia .................................................................... 31

(3.2). Fórmula modelo movimiento para las coordenadas (x,y) .................................... 35

(3.3). Fórmula modelo de movimiento para las velocidades en ambas coordenadas ..... 35

(3.4). Ecuaciones para el cálculo del centroide .............................................................. 36

(3.5). Fórmulas para la translación y unicidad de coordenadas ...................................... 38

(3.6). Fórmula para la conversión de radianes a grados ................................................. 39

(3.7). Fórmula de la distancia entre partículas ................................................................ 40

(3.8). Fórmula aplicada para el cálculo del perímetro del objeto ................................... 40

(3.9). Fórmula del área de un triángulo .......................................................................... 41

(4.1). Fórmula error cometido ........................................................................................ 54

Índice Tablas

Tabla 3.1 Tabla con ventajas y desventajas del programa Open Video Converter ....... 25

Tabla 3.2 Tabla con información proporcionada por la secuencia ................................ 32

Tabla 4.1 Tabla parámetros objeto no deformable ......................................................... 45

Tabla 4.2 Tabla parámetros objeto deformable .............................................................. 48

Tabla 4.3 Tabla parámetros video sintético .................................................................... 51

Tabla 4.4 Área y perímetro a través del tiempo con un video sintético ......................... 53

Tabla 4.5 Datos estadísticos obtenidos del video sintético............................................. 54


1

Resumen

Este proyecto tiene por objetivo principal realizar el seguimiento y extracción de

características geométricas de objetos en movimiento en secuencias de imágenes.

Para conseguirlo se utiliza la técnica denominada: Filtro de Partículas. La idea de

este filtro es determinar una serie de parámetros que describan un sistema que

evoluciona en el tiempo.

Se ha desarrollado un filtro capaz de seguir un objeto de dos dimensiones en una

secuencia de imágenes, aunque éste presente variaciones en su forma, tamaño, color o

modelo de movimiento. Una vez alcanzado este objetivo, se extraen características del

mismo en cada fotograma tales como: centroide, partícula estimada, coordenadas

máximas y mínimas en las dimensiones X e Y del objeto (xmax, xmin, ymax, ymin), área,

perímetro y funciones de variación del área y perímetro.

Se comprueba mediante diversos experimentos, que el sistema se comporta de

manera eficiente tanto para objetos reales deformables como no deformables, a lo largo

de una secuencia de vídeo. Igualmente se realiza un estudio estadístico de un objeto

generado sintéticamente, pudiendo evidenciar el error cometido por el sistema en el

cálculo del área y perímetro del mismo, siendo éste de: 11,71% y 13,49%

respectivamente, con respecto a la medida real.


2


3

Capítulo 1 Introducción

La visión Artificial es una disciplina que tiene como finalidad la extracción de

información del mundo físico a partir de imágenes, utilizando para ello un computador.

Se trata de un campo de conocimiento con un objetivo ambicioso y complejo que en los

últimos años ha evolucionado de manera drástica con el desarrollo de los ordenadores y

sensores de captura de imágenes [1].

La Visión Artificial, también llamada Visión Computacional, pretende con

determinadas restricciones reproducir el sentido de la vista del ser humano. En un

sistema de Visión Artificial se definen las siguientes fases, mostradas en la Figura 1.1:

La primera fase, consiste en la Captura o Adquisición de las imágenes

digitales mediante algún tipo de sensor, fundamentalmente una cámara.

Una imagen que es capturada a través de un sensor, se guarda en la memoria

de la computadora como un arreglo o matriz de puntos, llamados píxeles.

Cada pixel tiene asociados un valor numérico entre 0 y 255. Dependiendo del

tipo de imágenes que se traten, cada punto representará la intensidad o brillo

de la imagen, si se trabaja con imágenes en blanco y negro; o tres matrices de

puntos, uno para rojo, otro para verde y otro para azul si lo hacemos con

imágenes a color; su combinación representa los diferentes colores [2].

La segunda etapa tiene por objeto el tratamiento digital de imágenes para

facilitar las etapas posteriores. En esta fase, conocida como

Preprocesamiento, mediante filtros y transformaciones geométricas se tratan

de eliminar partes indeseables de la imagen y realzar los detalles de interés

para su posterior análisis.


4

CAPTURA

La Segmentación es la siguiente fase, y consiste en particionar una imagen en

regiones homogéneas con el fin de extraer características de dichas regiones

(color, textura, forma,…) para la posterior etapa de reconocimiento.

Para finalizar, se llega a la etapa denominada de Reconocimiento o

Clasificación. Valiéndose del análisis de ciertas características que se

establecen previamente para diferenciar los objetos segmentados, se pretende

discernir entre unos y otros.

Figura 1.1: Etapas típicas en un sistema de Visión Artificial (adaptado de [1]).

Diferentes aspectos han ayudado a llevar a la Visión Artificial al campo de las

aplicaciones industriales como: el aumento de las prestaciones de los ordenadores,

desarrollo de técnicas algorítmicas eficientes para el abordaje de los problemas, etc.

Estos aspectos han permitido realizar el tratamiento de imágenes en tiempo real [2].

PREPROCESAMIENTO SEGMENTACIÓN RECONOCIMIENTO


5

1.1 Seguimiento de objetos en movimiento

1.1.1 El problema de la visión dinámica

Una escena dinámica se compone de una secuencia de frames1 o fotogramas

interrelacionados, donde cada fotograma representa la escena en un determinado

instante de tiempo t.

Figura 1.2: Fotogramas de una secuencia de imágenes a través del tiempo.

Debemos entender un sistema de visión dinámica como un conjunto de coordenadas

espaciales (x,y) dentro de cada fotograma y además añadir un tercer parámetro como

sería el tiempo t, permitiéndonos su combinación la descripción de la entrada de un

sistema de visión dinámica como una función F(x,y,t). La entrada en juego del

parámetro t es fácil de entender si se tiene en cuenta los posibles cambios que pueden

darse en la escena, ya sea debido al movimiento de la escena en sí misma, de la

cámara o de ambos. En el trabajo que se trata, ese movimiento de cámara no va a

producirse, debido a que las secuencias de imágenes serán captadas mediante una

cámara estática.

Para procesar información dinámica se podrán aplicar técnicas estáticas a cada

fotograma por separado o analizar una secuencia de forma continua.

1 Imagen particular dentro de una sucesión de imágenes que componen una animación.

x

y


6

1.1.2 Objetivos del seguimiento

o Estimación del cambio temporal de los parámetros característicos de nuestro

modelo, a partir de observaciones de dichos parámetros realizadas en contextos

de incertidumbre (con ruido).

o El seguimiento espacio-temporal de un móvil a través de la estimación óptima

de su estado.

o Predicción-actualización del estado futuro del modelo a partir de una

secuencia de observaciones: típico de un filtro.

1.1.3 Estudio del movimiento

1.1.3.1 Hipótesis de Continuidad

El primer objetivo será desarrollar un algoritmo, basándose en el Filtro de

Partículas, para llevar a cabo el seguimiento visual. Para ello debemos tener muy en

cuenta la conocida hipótesis de continuidad que permitirá deducir la posición de un

objeto en movimiento en un instante de tiempo. La hipótesis de continuidad puede

enunciarse del modo siguiente:

“Suponemos que la frecuencia de muestreo del sistema es suficiente para que el

movimiento se muestre como continuo, es decir que dadas dos muestras consecutivas en

el tiempo, la posición del objeto en ambas será cercana”.

En términos matemáticos:

(1.1)

donde xti es la posición en el eje x en el instante de tiempo t, yti es la posición en el

eje y en el instante de tiempo t y ǫ es la distancia máxima entre dos mediciones para

que éstas se consideren continuas.


7

Suponiendo esto, se restringirá la búsqueda del objeto a regiones cercanas a la

posición estimada en un instante de tiempo t, permitiendo limitar el cálculo y ahorrando

coste en computación.

1.1.3.2 Inercia

La inercia se define como la dificultad o resistencia que opone un sistema físico en

ausencia de alteraciones externas, a posibles cambios [3].

La hipótesis de continuidad del movimiento, impone una restricción que hace deducir

que el movimiento conservará en parte, tanto su velocidad como su aceleración en los

instantes siguientes al actual.

Utilizando esta idea se pueden predecir comportamientos en el movimiento de un

objeto durante periodos de corta duración, si la velocidad se mantiene constante en el

tiempo y mientras no se tengan nuevas medidas, es decir:

(1.2)

donde vt+n es la velocidad en el instante de tiempo t+n y vt es la velocidad en el


Al igual que la velocidad, la aceleración también permanecerá constante hasta que no

obtengamos otro nuevo dato. En términos matemáticos:

(1.3)

Donde at+n es la aceleración en el instante de tiempo t+n y at es la aceleración en el


A medida que pase el tiempo con respecto al instante de tiempo actual t, se tendrá

una probabilidad p menor de que tanto la velocidad como la aceleración se mantengan

constantes en el tiempo, debido a la incertidumbre que sufrirá la predicción.

vt+n = vt

at+n = at


8

1.1.3.3 Hipótesis o restricciones de suavidad del movimiento.

Para continuar con el estudio del movimiento se tendrá que tener claro que:

o Una proyección de un movimiento 3D suave sigue siendo suave.

o El movimiento de un objeto en cualquier punto de la imagen en una secuencia

no cambiará abruptamente. En este sentido se tendrá en cuenta que de un

punto dado, las siguientes características, serán relativamente invariantes de un

fotograma al siguiente:

o La posición.

o La velocidad escalar.

o La dirección de movimiento.

1.1.4 Métodos de detección de movimiento

Para realizar la detección del movimiento a través del tiempo en la secuencia de

fotogramas, se tendrá en cuenta lo siguiente: un movimiento perceptible en la escena

provocará cambios (p.ej. nuevas oclusiones) en la secuencia de fotogramas de dicha

escena.

Debemos tener siempre presente, que no solo los cambios producidos en la secuencia

de fotogramas de la escena podrán ser debidos al movimiento de un objeto, sino que

también pueden ser provocados por cambios en la iluminación u otros factores.

La mayoría de las técnicas de análisis dinámicas están basadas en la detección de

cambios en una secuencia de fotogramas, ya sean: fotograma a fotograma, píxel a píxel

o región a región.


9

1.1.5 Técnica de detección de movimiento: Sustracción

de fondo

Este método requiere tener un fotograma inicial como modelo para obtener las

posteriores diferencias de los fotogramas que conforman la secuencia. Todo cambio con

respecto al fotograma inicial será considerado como no perteneciente al background 2.

En nuestro caso, aplicado al movimiento de objetos, todo cambio detectado será

interpretado como presencia del objeto a seguir [4].

El algoritmo pretende, dada una imagen B, definida como de background, obtener los

cambios que se producen a lo largo del tiempo t en la secuencia de fotogramas It,

representando éste cada uno de los fotogramas de la secuencia a través del tiempo.

En términos matemáticos:

(1.4)

donde B es la imagen tomada como background, It es el fotograma en el instante de

tiempo t , Id es la imagen diferencia en valor absoluto entre It y B, y T es el tiempo

total.

La sustracción de fondo estática es una técnica fácil de implementar pero de escasa

aplicación en entornos realistas, donde se requiere que la imagen usada como fondo

pueda variar dinámicamente teniendo en cuenta, entre otros factores, los cambios de

iluminación producidos en la escena.

2 Referido al fondo de una imagen o fotograma

Id = | It - B | ∀t=1,…,T


10

1.1.6 Aplicaciones del seguimiento visual

Existen en la literatura múltiples aplicaciones para el seguimiento visual mediante

técnicas de visión artificial. Muchas de ellas están inspiradas en lo que los seres

humanos hacen con el sistema de seguimiento biológico [5].

- Navegación: De la misma manera que las personas utilizan marcas visuales para

caminar o evitar objetos, un robot puede hacer uso de ellas para obtener su

posición y orientación relativa a ellas durante su trayecto.

- Reconocimiento de caras: El reconocimiento de caras es un problema

complicado. Existen numerosos trabajos sobre este tema, los cuales tratan de

identificar personas en entornos controlados y con vistas frontales de las caras. El

problema se hace más difícil cuando la persona a reconocer no se encuentra

inmóvil, sino que se mueve de forma natural delante de las cámaras.

- Realimentación visual para brazos de robots: Controlar los brazos de robot por

medio de seguimiento visual es una técnica útil para interactuar con entornos

dinámicos.

- Vigilancia: Ésta ha sido de las primeras aplicaciones útiles para algoritmos de

seguimiento. Normalmente, los sistemas de vigilancia típicos constan de cámaras

estáticas con módulos de detección que activan la grabación de secuencias.

- Seguimiento del movimiento de las personas: En este tipo de aplicaciones se

pretende reconocer los gestos del cuerpo. Por ejemplo, manos y dedos pueden ser

usados como ratones o teclados para interactuar con un ordenador.

- Control del tráfico: La monitorización de vehículos en carreteras y autopistas es

otra de las aplicaciones prácticas del seguimiento. La detección de colisiones y

maniobras peligrosas de los conductores pueden ser detectadas.


11

1.2 Filtro de Partículas

Un Filtro de Partículas es un método para estimar el estado de un sistema que

cambia de forma dinámica. Fue propuesto por Gordon, Salmond y Smith en 1993 [6]. El

filtro se compone de un conjunto de muestras en el espacio del problema a los cuales se

les asigna un peso de acuerdo con ciertas características medidas. Una partícula se

define como una dupla formada por un estado y un peso .

(1.5)

donde es un estado del espacio de estados , y es el peso o verosimilitud

asociada al estado y normalizado entre [0,1]. La idea es usar conjuntos de estas

partículas para aproximar distribuciones de probabilidad, por lo que se obtiene:

(1.6)

Si el conjunto de muestras es suficientemente grande, se puede demostrar que la

función de densidad de probabilidad (pdf) estimada por dichas muestras se aproxima de

forma muy fiel a la pdf real de la distribución. En concreto, para un conjunto infinito de

muestras, la pdf estimada coincidiría exactamente con la pdf real. Usando únicamente la

suposición de continuidad del movimiento la pdf esperada es una distribución uniforme,

por lo que el peso de cada partícula debe ser y estar uniformemente distribuido en el

espacio.


12

La Figura 1.3 muestra el esquema de estimación utilizado por el Filtro de

Partículas.

Figura 1.3: Esquema de estimación usado por el Filtro de Partículas

1.2.1 Operaciones

Sobre un conjunto de partículas se pueden realizar ciertas operaciones. Las que se

utilizan normalmente para implementar el Filtro de Partículas son [7]:

Multiplicación por una función

Aplicación de un modelo de dinámica

Remuestreo (resampling).

1.2.1.1 Multiplicación por una función o cálculo de pesos

La multiplicación es la más simple de las funciones utilizadas sobre un conjunto de

partículas. Consigue el efecto de mantener la situación de las partículas dentro del

espacio de estados pero modifica su peso para que sea proporcional a la función por la

que se multiplica.

pdf


13

Sea un conjunto de partículas S definido sobre el espacio de trabajo X:

y h(x) una función continua, no negativa y acotada lejos de 0.

En el nuevo conjunto, las partículas tendrán la misma posición que en el original

pero su peso habrá cambiado para ser proporcional a la función que se ha aplicado,

h(x).

Una representación gráfica del funcionamiento de la multiplicación sobre partículas

puede apreciarse en la Figura 1.4:

Figura 1.4: Funcionamiento de la multiplicación sobre partículas

Representación discreta de

la pdf a priori

Representación discreta de

la pdf a posteriori


14

1.2.1.2 Aplicación de un modelo de dinámica

Con la operación de aplicación del modelo de dinámica se busca representar el

conocimiento que tenemos acerca del movimiento. Es decir, si se conoce la posición de

un objeto en el instante t se tiene alguna información acerca de su posible posición en el

instante t+1. Esto se expresa como una distribución de probabilidades. Es decir, que

dado un conjunto de partículas y una distribución de probabilidades como la siguiente:

al aplicar la función se obtiene otro conjunto de partículas que cumple lo siguiente:

(1.7)

siendo N el número total de partículas.

La idea de aplicar esta función es que las partículas se dispersen conforme a la

función, así que ésta debe representar el conocimiento acerca del movimiento. Si se

desconoce el modelo de movimiento, la función propuesta será una distribución

uniforme. Sin embargo, si se basa en la hipótesis de continuidad, al menos se conoce

que la siguiente posición estará en las inmediaciones de la anterior. Esto se puede

representar mediante una distribución normal.


15

1.2.1.3 Remuestreo o Resampling

Una distribución de probabilidad p(x) se puede representar de muchas formas. Sin

embargo, algunas son mejores que otras según el uso que se le dé. El cálculo

computacional se hace más liviano si la mayoría de las partículas tienen pesos iguales.

Este es el propósito de la etapa de resampling.

Supóngase que se tiene un conjunto de partículas S:

Después de aplicar el resampling se obtiene otro conjunto de partículas S que

cumplirá lo siguiente:

(1.8)

donde la operación de escoger es independiente en cada paso. También existe la

posibilidad de que el resampling sea determinista, por ejemplo directamente

proporcional al peso de las antiguas partículas.


16

1.2.2 Descripción del algoritmo

El algoritmo tiene una serie de etapas en las cuales se usan las operaciones

explicadas anteriormente:

1. Inicio: Se lanzan N partículas de forma aleatoria en el espacio de

búsqueda.

2. Actualización: se define una función que sea proporcional a la porción

de la partícula que ha caído sobre el objeto que se está buscando, de modo que al

realizar la multiplicación, se obtengan partículas con pesos altos en aquellas

posiciones del espacio que tienen una situación cercana al objeto.

3. Selección: a partir del conjunto de partículas anterior, se crea uno nuevo

con el mismo número de partículas en el que éstas serán seleccionadas entre las

anteriores de forma proporcional a su peso. Así, las partículas con un peso alto se

replicarán muchas veces y aquellas que tuviesen un peso bajo se replicarán pocas.

En la Figura 1.5 se puede apreciar el funcionamiento del algoritmo de selección

con pesos acumulados.

Figura 1.5: Funcionamiento del algoritmo de selección con pesos acumulados


17

4. Predicción: las partículas sufren leves cambios de estado (posición en

nuestro caso) que representa lo que se conoce del movimiento. Por la hipótesis de

continuidad y puesto que el objeto tiene un movimiento continuo, la difusión se

hace desde el último estimado como centro y se dispersa con una distribución

normal en las proximidades dentro de un radio r.

La Figura 1.6 muestra un pseudocódigo del algoritmo:

VAR

P, P‟: conjunto de partículas;

M´: medida;

BEGIN

Inicialización (P);

t=1;

WHILE t<TMAX DO

Actualización (P,M(t));

Selección (P,P´);

Predicción (P´,P);

t=t+1;

END;

END.

Figura 1.6: Pseudocódigo del algoritmo Filtro de Partículas.


18


19

Capítulo 2 Objetivos

El objetivo principal de este proyecto puede enunciarse del siguiente modo:

“Seguimiento y extracción de características geométricas de un objeto en

movimiento a través de un Filtro de Partículas”.

Este objetivo se articula en los objetivos operativos que se enumeran a continuación.

2.1 Objetivos principales

1. Realizar un estudio del método Filtro de Partículas para obtener una visión

general del problema.

2. Implementar un Filtro de Partículas adaptándolo a la funcionalidad requerida

tras el conocimiento del filtro básico.

3. Experimentar con el Filtro de Partículas para un mejor entendimiento de sus

objetivos, ventajas y desventajas.

4. Desarrollar funcionalidad que permita la extracción de características relevantes

de un objeto basándonos siempre en la información proporcionada por las

partículas. Estas características serán:

o Centroide.

o Partícula estimada

o Perímetro.

o Área.

o Coordenadas máximas y

mínimas en las dimensiones

X e Y del objeto estimado

por el conjunto de partículas

(xmax, xmin, ymax, ymin).

5. Estudio de las características extraídas a través del tiempo, así como su

representación en los diferentes fotogramas de la secuencia de vídeo.

6. Obtener una buena respuesta, en cuanto a tiempo se refiere, del algoritmo.

7. Obtener las restricciones del sistema, es decir, casos en los que se comporta de

modo satisfactorio y en los que no lo hace.

8. Coleccionar un conjunto de datos de prueba.


20

2.2 Objetivos Parciales

Análisis

- Utilizar el Filtro de Partículas para la posterior extracción de características

geométricas de un objeto.

- Decidir los casos de prueba que serán utilizados para ejecutar el Filtro de

Partículas y extraer las características de los objetos.

- Probar el Filtro de Partículas ante diferentes situaciones: cambio de fondo,

objetos diversos en: tamaño, forma, color y modelo de movimiento.

- Obtener conclusiones acerca de las características obtenidas, así como proponer

futuras mejoras.

Diseño

- Entender y mejorar el funcionamiento del Filtro de Partículas Básico,

adaptándolo a nuestras necesidades.

- Decidir el modo de llevar a cabo el cálculo de las diferentes características,

haciendo uso únicamente de la información proporcionada por las partículas.

- Decidir cómo se va a realizar el seguimiento de objetos, es decir, cuáles serán las

directrices a seguir.

Implementación

- Familiarizarse con el entorno de programación MATLAB.

- Aprender y utilizar la TOOLBOX que ofrece MATLAB.

- Escribir un Filtro de Partículas Básico

- Modificar el Filtro de Partículas con las características necesarias para que

cumpla los objetivos.


21

- Implementar funcionalidad, que centrada en la información aportada por las

partículas, consiga extraer las características de un objeto tales como:

o Centroide.


o Perímetro.

o Área.






- Tras la extracción de características geométricas del objeto, realizar una

representación de su variación en el tiempo mediante funciones.

Pruebas

- Ejecutar el Filtro de Partículas en distintas secuencias de video, en las que se

ofrecen objetos diversos en tamaño, color, forma y modelo de movimiento.

- Estudio de las características geométricas de objetos deformables y no

deformables.

- Análisis de la eficiencia en tiempo de nuestro sistema, en el cálculo de las

características geométricas consideradas.


22


23

Capítulo 3 Descripción informática

En este capítulo se describen los diferentes aspectos que componen la especificación

del sistema desarrollado.

3.1 Herramientas utilizadas

3.1.1 El lenguaje programación MATLAB.

MATLAB (abreviatura de MATrix LABoratory, "laboratorio de matrices") es un

software matemático que ofrece un entorno de desarrollo integrado (IDE) con un

lenguaje de programación propio (lenguaje M). Está disponible para las plataformas

Unix, Windows y Apple Mac OS X.

Fue creado por The MathWorks en 1984, surgiendo la primera versión con la idea de

emplear paquetes de subrutinas escritas en Fortran en los cursos de álgebra lineal y

análisis numérico, sin necesidad de escribir programas en dicho lenguaje. El lenguaje de

programación M fue creado en 1970 para proporcionar un sencillo acceso al software de

matrices LINPACK y EISPACK sin tener que usar Fortran.

En 2004, se estimaba que MATLAB era empleado por más de un millón de personas

en ámbitos académicos y empresariales.

Entre sus prestaciones básicas se hallan:

La manipulación de matrices

La representación de datos y funciones.

La implementación de algoritmos, la creación de interfaces de usuario (GUI).

La comunicación con programas en otros lenguajes y con otros dispositivos

hardware.


24

El paquete MATLAB dispone de dos herramientas adicionales que expanden sus

prestaciones, a saber, Simulink (plataforma de simulación multidominio) y GUIDE

(editor de interfaces de usuario - GUI). Además, se pueden ampliar las capacidades de

MATLAB con las cajas de herramientas (toolboxes). Estas Toolboxes cubren las áreas

principales en el mundo de la ingeniería y la simulación, destacando entre ellas la de

proceso de imágenes, que han sido imprescindibles para este proyecto.

3.1.2 VideoSyn

VideoSyn es un generador de vídeo sintético [7]. El vídeo generado es una secuencia

simple en la que es posible generar un número variable de objetos rectangulares de

diferente tamaño que se mueven siguiendo un modelo de movimiento.

Permite añadir la funcionalidad de cambio de color. El cambio de color a uno

diferente del inicial, puede ser usado a modo de oclusión si el filtro es incapaz de

reconocer dicho color con la ventaja de que el observador humano puede supervisar el

funcionamiento y la corrección del filtro.

3.1.3 Open Video Converter

Conversor de video sencillo desarrollado por DigiByte Studio, sin grandes

pretensiones pero funcional y con los ajustes mínimos que todo conversor debe tener.

Es compatible con muchos formatos, entre otros MPEG, AVI, ASF, WMV o AVI, y

es su punto fuerte.

Puede convertir diferentes tipos de ficheros de video a AVI. Antes de proceder a la

conversión se puede fijar un punto de inicio y final al fichero convertido.

De este modo se puede fragmentar un vídeo y adquirir la escena que sea necesaria.

Entre algunos de los ajustes que permite realizar están: ajustar la resolución, escoger

el códec de vídeo, optar o no por la compresión de audio y ajustar la velocidad de salida

en función del soporte de destino.


25

Como requisitos imprescindibles para el uso de este programa ya sea en su versión

completa o de evaluación están los siguientes:

Sistema Operativo : Win98/98SE/Me/2000/NT/XP/2003.

DirectX 9.0.

Este sencillo conversor de vídeo, posee una serie de ventajas y desventajas que se

recogen en la siguiente tabla de la Figura 3.1:

VENTAJAS DESVENTAJAS

Sencillo de usar Interfaz poco intuitiva

Compatible con múltiples formatos de video Versión de prueba muy limitada

Ajustes básicos

Tabla 3.1: Ventajas y desventajas del programa Open Video Converter.

3.1.4 Longitech QuickCam SDK

Para llevar a cabo la grabación de los videos utilizados en las diferentes pruebas del

Filtro de partículas, se hará uso de una cámara web Longitech QuickCam 9000 Pro.

Esta cámara permite obtener imágenes con detalles perfectos y nítidos, gracias a sus

componentes ópticos Carl Zeiss® y enfoque automático, incluso en primeros planos. En

la Figura 3.1se puede apreciar el aspecto de esta cámara web.

Figura 3.1: Cámara web Longitech QuickCam 9000 Pro.


26

3.2 Requisitos

3.2.1 Requisitos Funcionales

Los requisitos funcionales son aquellos que proponen qué debe realizar la aplicación,

los servicios que ofrece, cómo debe reaccionar, estados que no se deben dar, etc. Estos

requisitos están enfocados a describir como se llevarían a la práctica los casos de uso.

Los requisitos funcionales de nuestra aplicación son:

Mediante un Filtro de Partículas básico, conseguir un seguimiento óptimo de

objetos en movimiento.

Modelizar el seguimiento, sin usar otras características que las de un Filtro de

Partículas básico.

Extracción de características geométricas de un objeto en movimiento para cada

fotograma de una secuencia de vídeo, haciendo uso únicamente de la

información proporcionada por las partículas:

o Centroide.


o Perímetro.

o Área.






Dar una visión completa del cambio producido en las características extraídas

del objeto en movimiento a través de los diferentes fotogramas de la secuencia

de vídeo.

Apreciar que dependiendo del número de partículas utilizado, los resultados

obtenidos acerca de la extracción de características geométricas puede variar.

Determinar el número de partículas adecuado que permita realizar una buena

extracción de las características geométricas y a la vez tenga un eficiente

comportamiento en cuanto a la complejidad.

El filtro debe ser capaz de recuperarse lo más rápidamente posible de la pérdida

de un objeto en un instante de tiempo.


27

3.2.2 Requisitos no Funcionales

Los requisitos no funcionales aseguran que se disponga de un sistema manejable y

gestionable que ofrezca la funcionalidad requerida de manera fiable, ininterrumpida o

con el tiempo mínimo de interrupción, incluso ante situaciones inusuales.

Los requisitos no funcionales de nuestro sistema serán los siguientes:

Captura de secuencias de imágenes con una webcam para seguir objetos y

extraer las características geométricas del mismo.

En un primer lugar se realizarán pruebas siguiendo un objeto de un determinado

color para comprobar el funcionamiento del Filtro de Partículas, para más tarde

capturar secuencias de diferentes objetos con diversidad de tamaños, formas,

colores, modelos de movimiento.

En la captura de vídeos no puede producirse el movimiento de la webcam. En

caso de producirse, no será válida la secuencia de video.

La captura de la secuencia de vídeo debe ofrecer las suficientes imágenes por

segundo como para poder seguir al objeto en tiempo real.

Necesitaremos hacer uso de técnicas para el tratamiento de imágenes tales como:

la sustracción de fondo, para identificar el objeto en la imagen. Para ello

tendremos como requisito disponer de una imagen denominada de background,

que represente el fondo de la escena.

Los objetos a seguir no tienen que cumplir ninguna característica especial salvo

la de distinguirse con facilidad del fondo, es decir, no tienen que tener un color,

forma, tamaño o modelo de movimiento específicos, ya que en ello radica el

objeto del estudio.

No hacer ninguna suposición del movimiento del objeto salvo de su

continuidad.

Tratar implementar un algoritmo rápido y eficiente para acercarnos a tiempo

real.


28

3.3 Modelo de desarrollo del software

El modelo de desarrollo software es una descripción simplificada de un proceso

software (actividades, productos, roles,…) [3]. Se empleará para el desarrollo de este

proyecto un modelo de desarrollo en espiral.

El modelo de desarrollo en espiral fue propuesto por Boehm, quien lo describe así:

“El modelo de desarrollo en espiral es un generador de modelo de proceso guiado

por el riesgo que se emplea para conducir sistemas intensivos de ingeniería de software

concurrente y a la vez con muchos usuarios”.

Se caracteriza principalmente por:

Un enfoque cíclico para el crecimiento incremental del grado de definición e

implementación de un sistema, mientras que disminuye su grado de riesgo.

Un conjunto de puntos de fijación para asegurar el compromiso del usuario

con soluciones de sistema que sean factibles y mutuamente satisfactorias.

Los principios básicos de esta metodología son los siguientes:

o Decidir qué problema se quiere resolver antes de proceder a

resolverlo.

o Examinar las múltiples alternativas de acción y elegir una de las más

convenientes.

o Evaluar qué se tiene hecho y qué se tiene que haber aprendido

después de hacer algo.

o No creer que el sistema que se construye será "EL" sistema que el

cliente necesita.

o Conocer (comprender) los niveles de riesgo, que tendrán que

tolerarse.


29

A continuación se ilustra un resumen gráfico del modelo de desarrollo en espiral,

mediante la Figura 3.2:

Figura 3.2: Modelo de desarrollo en espiral representado gráficamente.

El modelo de desarrollo en espiral, ilustrado en la Figura 3.2, consiste en una serie

de ciclos que se repiten en forma de espiral, comenzando desde el centro.

En cada ciclo se tiene en cuenta:

o Los Objetivos: Qué necesidad debe envolver el programa.

o Análisis: Los varios métodos de alcanzar los objetivos de manera

exitosa, a través de diferentes puntos como son:

1. Características: experiencia del personal, exigencias a efectuar.

2. Formas de gestión del programa.

3. Riesgo tomado con cada alternativa.

o Desarrollar y Verificar: Programar y probar el programa.


30

o Se planificarán los siguientes pasos y se volverá a comenzar otro ciclo.

La espiral tiene una forma de caracola y se dice que mantiene dos

dimensiones la radial y la angular:

1. Angular=Avance del proyecto Software, dentro de un ciclo.

2. Radial=Aumento del coste del proyecto, ya que con cada nueva

iteración se pasa más tiempo desarrollando.

Este sistema es muy utilizado en proyectos largos y que requieren constantes

cambios, por ejemplo la creación de un Sistema Operativo. Al ser un modelo de Ciclo

de Vida orientado al riesgo, se dice que uno de los aspectos fundamentales de su éxito

radica en que el equipo que lo aplique sea capaz de detectar y catalogar correctamente

dichos riesgos.

3.4 Diseño e implementación

3.4.1 Tratamiento imágenes: Sustracción de fondo

Las técnicas básicas consisten en el estudio de la imagen resultante de la diferencia

de una imagen con su fondo. Los objetos que se diferencian entre ambas imágenes

producen en la imagen diferencia un conjunto de píxeles con valores distintos a cero.

En la Figura 3.3 se muestra la imagen de background de la secuencia, un fotograma

con el objeto en movimiento y su posterior conversión a una imagen binaria, donde los

píxeles pertenecientes al objeto en movimiento aparecen en la imagen binaria en color

blanco (valor „1‟) y los pertenecientes al fondo, a color negro (valor „0‟).

Figura 3.3: Ejemplo de sustracción de fondo


31

Así, partiendo de dos imágenes It (imagen en el instante t) e If (imagen de fondo) los

objetos tras esta segmentación serían los píxeles a uno de la imagen Id. Siendo U un

valor umbral que depende de la variación de la iluminación entre ambas imágenes.

1, si |It (x,y) – If (x,y) |> U Id =

0, en otro caso

(3.1)

3.4.2 Filtro de Partículas para seguimiento de objetos

en 2D

Para seguir objetos en 2D en una secuencia de vídeo además de aplicar técnicas para

el tratamiento de imágenes que ayudarán a su detección, será necesaria la funcionalidad

del Filtro de Partículas básico con alguna diferencia. A continuación, procedemos a

detallar el mismo y dividiremos su explicación en dos partes: Generación de datos y

Funcionamiento del Filtro de Partículas.

Generación de datos:

Pedir parámetros

La aplicación requiere que el usuario indique una serie de parámetros para

posteriormente llevar a cabo la ejecución del Filtro de partículas y el seguimiento del

objeto en 2D. Esto parámetros son los siguientes:

1. Nombre (y ruta si procede) del archivo *.avi.

2. Número del primer fotograma del análisis. Siempre el primer fotograma será

considerado como el de background.

3. Nº último fotograma del análisis.

4. Número de partículas.


32

5. Umbral para la condición que conforma la imagen diferencia, es decir, nuevo

fotograma que recoge las diferencias entre los dos fotogramas comparados

(imagen binaria donde se recoge la diferencia del fotograma actual con

respecto al considerado de background).

6. Umbral para consideración objeto en el cálculo de las (x,y) máximas y

mínimas.

7. Umbral para consideración partículas correspondientes al perímetro. Vector

con umbral mínimo y máximo correspondientemente.

8. Umbral para consideración partículas correspondientes al área.

9. Tamaño de la ventana de la imagen que inspecciona cada partícula.

10. Rango utilizado en la etapa de difusión.

11. Rango utilizado en la etapa de predicción.

Obtener datos:

Dada una secuencia de vídeo indicada mediante la ruta anteriormente mencionada,

será necesario obtener una serie de datos de interés como la secuencia de vídeo e

información de interés de la misma, como la que se muestra en la Tabla 3.2:

Nombre Fichero Tipo compresión de la imagen.

Fecha de modificación Tipo compresión del video

Número de frames Número de entradas mapa de color

Frames por segundo Formato de audio

Ancho frame Ratio del audio

Alto frame Número de canales de audio

Tamaño del fichero

Tabla 3.2: Tabla con información proporcionada por la secuencia

Estos parámetros informativos acerca de la secuencia de vídeo serán de gran validez

en el desarrollo de funcionalidad futura.


33

Funcionamiento del Filtro de Partículas:

Generar población inicial

Lo primero que haremos será:

o Generar aleatoriamente las coordenadas (x,y) de todas las partículas dentro de

las dimensiones del fotograma de la secuencia de vídeo.

o Inicializar la velocidad de mencionadas partículas a cero (vx, vy).

Sustracción de Fondo

Dada una imagen RBG, se compara canal por canal con una imagen previa definida

como de background (imagen sin objeto) dando lugar a un nuevo tipo de imagen

denominada binaria, es decir, aquélla definida por 0 ó 1 dependiendo de si se encuentra

o no diferencia respectivamente.

Actualización

Se asigna un peso a las partículas del conjunto generado, para ello se dibuja una

pequeña ventana o región de interés asociada a la posición de la partícula y se suma el

número de píxeles a „1‟ (aquellos en los que existe diferencia con respecto a la imagen

de background) que se encuentran dentro de ella. Resultará de gran utilidad para futuros

cálculos.

Construir ruleta

Crea un vector denominado ruleta normalizado a 1. Para ello suma todos los pesos

normalizados de las partículas, creando abstractamente un gráfico de sectores,

consiguiendo así reservar en el vector ruleta un mayor espacio para aquellas partículas

de mayor peso, que dispondrán por tanto de mayor probabilidad de caer dentro de esa

región.


34

Tirar ruleta

Esta funcionalidad del Filtro de Partículas permite generar las nuevas partículas

para el instante siguiente. Para ello se tirará durante N veces (tantas como partículas

haya) la ruleta previamente construida y se guardará el índice de la partícula que se

elige en cada momento. Debemos entender que aquellas partículas con mayor peso

serán aquellas que tendrán mayor probabilidad de ser elegidas.

Elegir

Con anterioridad se obtienen los índices de las partículas tras tirar N veces la ruleta.

Ahora el conjunto partículas se generará con una posición, una velocidad y unos

pesos, pero con las partículas nuevas generadas tras tirar la ruleta y gracias a los índices

obtenidos. En resumen, generará un nuevo conjunto de partículas como el inicial, pero

ya no de modo aleatorio, sino haciendo uso de los índices obtenidos tras tirar la ruleta.

Se aprovechará igualmente para inicializar los pesos de todas las partículas a 1, porque

luego serán de nuevo actualizados.

Difundir

Debido a que se controla la generación de partículas parcialmente, es decir, no se

impone ninguna condición por la que dos partículas que ocupen las mismas

coordenadas no puedan existir, se aplicará un modelo de difusión con respecto a las

coordenadas (x,y) previas de cada partícula, para evitar la coincidencia en posición de

muchas partículas en la imagen. Esta difusión consiste en sumar a las coordenadas

(x,y) de cada partícula, un número introducido por el usuario. Cuanto mayor sea esta

función de separación entre partículas, mayor será la separación de éstas. Este

parámetro tendrá que ser tenido muy en cuenta en circunstancias en las que los objetos

aparecen muy dispersos por la imagen.


35

De nada serviría disponer de 100 partículas si 50 de ellas ocupan la misma posición

en la imagen, solo 1 me aportaría información y 49 sobrarían, con el coste en ejecución

para nuestro algoritmo que ello supondría.

Movimiento

Una vez realizada la difusión de las partículas, para evitar solapamientos entre ellas,

se aplica el modelo de movimiento de las mismas. Ahora debemos aplicar el modelo de

movimiento tanto al cálculo de las coordenadas (x,y) de las partículas :

(3.2)

como a sus correspondientes velocidades (vx, vy):

(3.3)

vx (t + Δt)= vx(t) +F

vy (t + Δt)= vy (t) +F

Δt: incremento del tiempo

F : factor incremento

velocidad

x(t + Δt)= x(t) + G

y(t + Δt)= y(t)+G

Δt: incremento del

tiempo

G : factor incremento

posición


36

3.4.3 Funcionalidad para extracción de características

geométricas de un objeto en 2D

Dividiremos este apartado en dos bloques, tratando de dar una visión más particular

de la funcionalidad implementada. Esta división se corresponde con: operaciones y

dibujar o representar.

Operaciones:

Calcular Centroide del objeto

El centroide es un punto que define el centro geométrico de un objeto.

Figura 3.4: Ejemplo de centroide en una figura geométrica.

Esta definición formal no es más, aplicada a nuestro Filtro de Partículas, que el

promedio de todas los coordenadas de las partículas que se encuentran en el objeto.

Matemáticamente se define como:

(3.4)

Debido a esta definición, al no aportar nada las partículas que no se encuentran en el

objeto en cuanto al peso, no debemos preocuparnos de ellas a la hora de calcular el

centroide.

Peso de la partícula

(xi,yi) Coordenadas de las partículas


37

Calcular las coordenadas máximas y mínimas en las dimensiones X e Y del objeto

seguido por el conjunto de partículas (xmax, xmin, ymax, ymin).

En primer lugar seleccionaremos todas aquellas partículas que se encuentren dentro

del objeto, descartando aquellas que no lo están. Sólo las partículas con peso, es decir,

las que solapan parcial o totalmente el objeto pueden competir por convertirse en las

coordenadas máximas y mínimas en las dimensiones X e Y del objeto estimado por el

conjunto de partículas (xmax, xmin, ymax, ymin). El cálculo de estos puntos de interés

proporcionará un rectángulo o cuadrado que seguirá al objeto durante la secuencia de

video.

Cálculo de las partículas que definen el perímetro

Se define el perímetro como el contorno de la superficie de una figura u objeto y

podemos apreciar un ejemplo de su representación gráfica mediante la Figura 3.5. El

objetivo será realizar el cálculo del perímetro, pero haciendo uso de la información

proporcionada por las partículas. Para ello se diferenciará entre aquellas partículas que

se encuentren en los bordes del objeto y el resto, mediante unos umbrales que

introducirá el usuario. El sistema se quedará únicamente con aquellas que se encuentren

en el contorno del objeto en movimiento y obviará el resto de partículas del conjunto

generado.

Figura 3.5: Representación del perímetro de un objeto cualquiera en 2D

Ordenar perímetro

Una vez obtenido un conjunto de partículas que pertenecen al borde del objeto a

seguir, se llevará a cabo una ordenación del mismo en orden creciente a su ángulo, para

su posterior representación. Dicho cometido se consigue en tres pasos:


38

1. Trasladar las coordenadas de las partículas que forman parte del

perímetro del objeto, con respecto al centroide del mismo y hacerlas unitarias,

como se muestra en la Figura 3.6.

Figura 3.6: Representación de la translación de coordenadas

Para ello se aplican las siguientes fórmulas:

(3.5)

2. Obtener el ángulo formado por el vector que surge de unir mediante una

recta las coordenadas ya trasladadas y hechas unitarias con el centroide del

objeto, con respecto al vector (0,1), como se muestra en la Figura 3.7:

Figura 3.7: Ángulo formado entre vector creado y vector (0,1).

Centroide del objeto

xtransladada= xcoordenada-xcentroide ytransladada= ycoordenada-ycentroide

Centroide del

objeto

Ángulo formado


39

El ángulo debe ser clasificado atendiendo al cuadrante al que pertenece. Para

una mayor claridad se muestra en la Figura 3.8 una representación gráfica de ello:

Figura 3.8: Cuadrantes del eje de coordenadas.

Por último se convierte de radianes a grados los ángulos mediante la fórmula

(3.6):

(3.6)

3. Aplicar un algoritmo de ordenación burbuja3 que ordena las

coordenadas de las partículas del perímetro en orden creciente a su ángulo,

expresado en grados.

3 Algoritmo de ordenación que funciona revisando cada elemento de la lista que va a ser ordenada con

el siguiente, intercambiándolos de posición si están en el orden equivocado

Grados = Radianes * 180 /


40

Cálcular perímetro

Para calcular el perímetro, se hará uso del conjunto de partículas pertenecientes al

perímetro y ordenadas en orden creciente a su ángulo. Se hallará la distancia entre

todas y cada una de ellas, aplicando la fórmula (3.7), y acumulando el valor resultante

de las mismas, siendo éste el valor del perímetro del objeto seguido como se expresa

matemáticamente mediante la fórmula (3.8).

(3.7)

donde serán las partículas y , las coordenadas correspondientes

a las partículas.

(3.8)

donde se corresponde con una de las partículas pertenecientes al perímetro y

con la partícula final. Np será el número de partículas del conjunto.

Se considerará que una partícula pertenece al perímetro del objeto cuando su peso

sea distinto de 0 y del máximo peso posible.

Cálculo de las partículas que definen el área

Es la extensión o superficie comprendida dentro de una figura. Con la información

proporcionada por las partículas, se generará un subconjunto de las partículas que

forman parte del objeto en su totalidad, es decir, aquéllas que tengan un peso cercano al

máximo.


41

Calcular Área

Una vez obtenido el subconjunto de partículas pertenecientes al área del objeto, se

procederá a calcular el área del mismo. Para ello no se utilizará este subconjunto de

partículas, sino el conjunto ordenado de partículas pertenecientes al perímetro. Se

desarrollará una técnica, que atendiendo a la información ofrecida por las partículas,

permitirá el cálculo del área con el menor error posible. Para ello haremos sucesivos

cálculos del área de un triángulo.

A continuación se muestra el modo de calcular el área de un triángulo:

(3.9)

La suma de todos los triángulos formados por el centroide y dos partículas

consecutivas del perímetro del objeto conformará el área de nuestro objeto a seguir,

como se describe gráficamente en la Figura 3.9:

Figura 3.9: Representación del cálculo del área de un objeto

Área triángulos que conforman

el área del objeto


42

Estimación

Calcular el estimado del sistema para el fotograma actual, consiste en el cálculo de la

partícula con mayor peso dentro del conjunto de N partículas.

Dibujar o representar:

Representaremos las siguientes características geométricas y cinemáticas del objeto:

o Centroide

o Partícula estimada (la de mayor peso).

o Coordenadas máximas y mínimas en las dimensiones X e Y del

objeto estimado por el conjunto de partículas (xmax, xmin, ymax,

ymin).

o Perímetro

o Área

o Funciones con respecto al tiempo:

o Perímetro

o Área


43

3.4.4 Diagrama de bloques del Filtro de Partículas

INICIALIZACIÓN

Pedir Parámetros.

Obtener Parámetros.

Generación población

inicial.

ACTUALIZACIÓN

Sustracción de fondo.

Actualización (cálculo

de pesos)

SELECCIÓN

Construir ruleta.

Tirar ruleta.

Elegir.

PREDICCIÓN

Difusión

Movimiento

CÁLCULO DE PARAMETROS

GEOMÉTRICOS

Calcular centroide del objeto.

Calcular las coordenadas

máximas y mínimas en las

dimensiones X e Y del objeto

seguido (xmax, xmin, ymax, ymin).

Cálculo de las partículas que

definen el perímetro.

Ordenar perímetro

Calcular perímetro

Cálculo de las partículas que

definen el área

Calcular el área

Estimación

ANÁLISIS DE

CARACTERÍSTICAS

GEOMÉTRICAS

FILTRO DE PARTÍCULAS


44


45

Capítulo 4 Resultados Experimentales

1.1 Experimento 1: Objeto no deformable

Para la realización de esta prueba se ha elegido una pelota blanca de béisbol sobre un

fondo verde. El objeto realiza un movimiento rectilíneo uniformemente decelerado. Los

parámetros empleados para el seguimiento y extracción de características son los que se

muestran en la Tabla 4.1:

Tabla 4.1: Parámetros calculados para un objeto no deformable

Al ser un objeto de escaso tamaño, el número de partículas utilizadas es pequeño:

150 partículas.

El tamaño de ventana de la partícula es reducido, ya que queremos que la ventana

para las partículas sea más pequeña que el propio cuerpo. De lo contrario, la

información dada acerca de sus características sería poco realista.

Los rangos en la etapa de difusión y en la etapa de dispersión no son muy grandes.

PARÁMETRO VALOR NUMÉRICO

Primer Frame de la secuencia 1

Último Frame de la secuencia 71

Número de partículas a generar 150

Umbral para formar imagen diferencia 0.20

Umbral partículas xmax, xmin, ymax, ymin 0.75

Umbral partículas del perímetro [0.10, 0.65]

Umbral partículas área 0.40

Tamaño ventana de las partículas [10,10]

Rango etapa difusión [15,15]

Rango etapa dispersión [20,20]


46

Figura 4.1: Captura 1 de un objeto no deformable en instante t=2s.

El sistema al detectar el objeto por primera vez, presenta una idea muy poco

aproximada del área y perímetro real del cuerpo, como se puede ver en la Figura 4.1.

Podemos apreciar con la imagen binaria, una forma indeterminada del objeto debido

al movimiento decelerado, que tendrá su mayor velocidad en estos primeros instantes de

tiempo.



47

Sobre el instante de tiempo t=5s, se produce un hecho relevante, y es que tanto el

perímetro como el área del objeto son maximizados de un modo que no se

corresponde con la realidad, como refleja la Figura 4.2. El objeto al encontrarse en

movimiento deja una estela que el sistema interpreta como perteneciente al objeto.


En la Figura 4.3 se puede apreciar como una vez asentado el movimiento del objeto,

obtenemos valores de área y perímetro constantes a lo largo del tiempo, lo que supone

que en los rangos de tiempo comprendidos entre t=10s y t=17s, la extracción de

características del objeto se realiza de manera satisfactoria otorgando valores al

perímetro, área, centroide, xmax, xmin, ymax, ymin de buena precisión.

Los valores negativos en la gráfica del perímetro o área en el transcurso del tiempo,

se deben a instantes en los que el Filtro de Partículas no tiene éxito en el seguimiento

del objeto.


48

1.2 Experimento2: Objeto deformable

En esta ocasión se tira un pañuelo rojo desde una cierta altura y es acelerado por la

acción de la gravedad. El objeto cambia de forma a lo largo del tiempo por lo que

resulta de mayor complejidad la detección de sus características. Esta vez se producirán

cambios en el área y perímetro, no únicamente por el movimiento, sino por las

deformaciones producidas en el objeto. La Tabla 4.2 muestra los parámetros empleados

para el seguimiento y extracción de características del objeto deformable.

PARÁMETRO VALOR NUMÉRICO Primer Frame de la secuencia 1










Tabla 4.2: Tabla parámetros objeto no deformable.

Los parámetros utilizados en este experimento son diferentes a los del experimento

previo. El número de partículas generado es superior al anterior, debido a que el cuerpo

a detectar posee mayor superficie. También varían medidas como el umbral para la

imagen diferencia, evitando así cualquier tipo de ruido que pudiera hacer pensar en

puntos erróneos como pertenecientes al objeto.

Igualmente la ventana del tamaño de las partículas se ha reducido para obtener una

mayor precisión en las medidas, puesto que el objeto seguido presenta mayor

irregularidad que el anterior.

Los rangos de difusión y dispersión son superiores a los empleados en la primera

prueba, puesto que el movimiento realizado por el objeto en esta ocasión presenta

mayor incertidumbre.


49

Figura 4.4: Captura 1 de un objeto deformable en instante t=7s.

En el instante t=7s la aplicación captura el objeto. Observando la Figura 4.4 se

aprecia una buena detección de área pero no de perímetro, sobre todo en cuanto a su

representación se refiere, probablemente debido al movimiento acelerado que presenta

el objeto.



50

En el instante de tiempo t=17s, vemos en la Figura 4.5 como el sistema es capaz de

detectar, a pesar de la rapidez, el cambio en la forma del cuerpo seguido, reflejándolo en

una buena extracción de las características del mismo.


Una vez el objeto deja de tener movimiento, como se muestra en la Figura 4.6, se

obtiene para los instantes de tiempo comprendidos entre t=22s y t=33s valores

homogéneos tanto del área como del perímetro, pudiendo corroborar la buena

extracción de características que realiza el sistema cuando los cambios en el objeto son

moderados.


51

1.3 Prueba 3: Video sintético

El video que a continuación se pasa a describir es generado sintéticamente por una

aplicación denominada VydeoSyn. A través del mismo pretendemos realizar una

comprobación realista de la eficiencia de nuestra aplicación. Conociendo las medidas

del objeto, podremos comparar los resultados obtenidos en la extracción del área y

perímetro por parte de nuestro sistema, con respecto a la realidad. La Tabla 4.3

muestra los parámetros empleados para extraer las características y seguir al objeto

generado sintéticamente.

Tabla 4.3: Tabla parámetros video sintético

El rango en la etapa de difusión se mantiene con respecto al utilizado anteriormente

con un objeto deformable, ya que se pretende concentrar las partículas (1500) sobre el

objeto de forma que se vea solapado por ellas. La etapa de dispersión es la de mayor

rango empleado hasta el momento, debido a que hemos eliminado fotogramas del video

sintético por resultar éste demasiado lento. Esto no debería ser así y nuestros vídeos

deberían ser capaces de procesarse en tiempo real, pero el entorno de programación

utilizado hace muy pesado todo el procesamiento.

La ventana de la partícula es lo suficientemente ajustada como para dar una

información precisa que permita comprobar la eficiencia de nuestro sistema a la hora de

calcular el área y el perímetro del cuerpo.

Igualmente se han modificado y ampliado los umbrales pertenecientes a cada una de

las características a extraer. Se pretende conseguir mayor exactitud en la información

extraída en detrimento de la eficiencia en tiempo.

PARÁMETRO VALOR NUMÉRICO

Primer Frame de la secuencia 330











52

Figura 4.7: Captura 1 video sintético en instante t=20s.

La Figura 4.7 muestra la primera detección del objeto y cálculo de área y

perímetro. Esta detección se realiza sobre el instante t=20s debido a que existirán

muchos fotogramas anteriores en los que el objeto no se detecte. Se pretende conseguir

la mínima variación posible entre los valores de área y perímetro para llevar a cabo la

comparación de las medidas obtenidas con la realidad.

Figura 4.8: Captura 2 video sintético en instante t=40s.


53

La Figura 4.8 muestra una captura final del video sintético. Como se puede apreciar

los valores obtenidos de perímetro y área se mantienen constantes a lo largo del

tiempo, pero se quiere comprobar esto estadísticamente.

4.3.1 Análisis

En la Tabla 4.4 se muestran los valores obtenidos de área y perímetro a lo largo

del tiempo:

ÁREA PERÍMETRO TIEMPO (seg) 2482,7 166,8578 16.7190

3505,6 239,8959 18.5000

3791,8 269,8049 19.4220

2999,5 202,7565 20.3910

3854,5 282,4795 24.5470

3372,3 249,4015 25.5160

3306,6 275,9958 26.4690

3546,7 245,7728 27.3910

3362,4 248,8099 28.2820

3316,7 221,6771 29.1250

3490,4 250,1135 30.0000

3896,5 279,7270 30.9070

3118,7 216,0172 32.9540

3217,6 225,2385 33.8290

3505,8 249,8963 34.7040

3524,3 261,5050 35.6100

3637,4 247,1458 36.6250

3487,7 255,2701 37.6410

3814,6 273,2881 38.5940

3457,7 253,6086 39.5160

Tabla 4.4: Área y perímetro a través del tiempo con video sintético.


54

CARACTERÍSTICAS

Media

aritmética

Valor

Máximo

Valor Mínimo Error

cometido

respecto

realidad (%)

ÁREA 3433,25263 3896,5 2482,7 13,4% PERÍMETRO 245,76309 282,4795 166,8578 11,36 %

Tabla 4.5: Datos estadísticos obtenidos del video sintético.

La Tabla 4.5 nos permite comprobar la eficiencia y aproximación a la realidad de

nuestro sistema en el cálculo del área y perímetro de un objeto.

El sistema realizó el seguimiento de un objeto cuadrado de 55x55 píxeles generado

sintéticamente sobre un fotograma de 400x400 píxeles. Con ello debiéramos obtener

valores de área y perímetro de: 3025y 220 respectivamente.

Se muestran en la Tabla 4.5 los valores obtenidos por la aplicación tras realizar el

seguimiento. Se especifica en ella la media aritmética de todas las mediciones de área

y perímetro a lo largo del tiempo, así como el valor máximo y mínimo alcanzado. En

la última columna se muestra el valor del error cometido en el cálculo del perímetro y

área utilizando la media aritmética como medida obtenida por el sistema. Las fórmulas

utilizadas para realizar este cálculo son las siguientes:

(4.1)

11,71 % 13,49 %


55

Capítulo 5 Conclusiones

Presentamos con este proyecto la implementación del método Filtro de Partículas

para el seguimiento de objetos en 2D, así como la extracción y estudio de características

relevantes del cuerpo seguido mediante la información proporcionada por las partículas,

tales como:

o Centroide.


o Perímetro.

o Área.






Para llevar a cabo el desarrollo de la aplicación, se ha hecho uso del entorno de

programación MATLAB. Previamente se ha realizado un estudio general de las áreas de

la Visión Artificial cuyo conocimiento era necesario para el buen desarrollo del

proyecto. Más tarde se desarrolló el Filtro de Partículas, alcanzando así uno de los

objetivos de este proyecto, el seguimiento de objetos en 2D.

Una vez alcanzado ese primer objetivo, dotamos a nuestro sistema de la

funcionalidad suficiente para realizar la extracción de las características relevantes para

obtener valores de las mismas eficientes y que puedan servir en futuros trabajos.

5.1 Objetivos alcanzados

Tras el desarrollo de la aplicación se ha realizado un estudio detallado que se

muestra en el Capítulo 4 de esta memoria. Se ha aplicado el sistema a diversas

secuencias de vídeo con distintos objetos en cuanto a forma, tamaño, color, modelo de

movimiento y hemos obtenido resultados satisfactorios en la extracción de sus

características. Para llevar a cabo un análisis estadístico de la eficiencia de nuestro

trabajo, sometimos al mismo al seguimiento de un cuadrado de 55x55 pixeles sobre un

frame de 400x400 pixeles, obteniendo pequeños errores de detección de perímetro y

área: 11,71% y 13,49% respectivamente, con respecto a las características geométricas

reales.


56

Es muy importante tener en cuenta para una correcta obtención de resultados, los

parámetros a introducir. Estos parámetros, al ser la primera vez que el autor del

proyecto tomaba contacto con problemas de esta índole no tenía conocimiento alguno

de las consecuencias que podría tener la modificación de sus valores sobre el

seguimiento del objeto y la extracción de sus características. Por ello se toma especial

cuidado en cada secuencia de video de detallar los mismos. De este modo se pretende

clarificar al lector la metodología del seguimiento visual a través del Filtro de

Partículas.

El único objetivo pendiente y que debe ser motivo de mejora para futuros trabajos

radica en la eficiencia del sistema, fundamentalmente provocada por el entorno de

programación MATLAB. Debemos conseguir una mayor velocidad de procesamiento

de la aplicación, para poder llevar a cabo el seguimiento de objetos en tiempo real y en

un futuro dar un uso más realista de nuestro sistema.

5.2 Mejoras y futuras líneas de trabajo

Se pretende desarrollar el siguiente trabajo futuro, relacionado con el proyecto:

o Dotar al sistema de un método de tratamiento de imágenes adaptativo para su

futura aplicación en secuencias realistas.

o Mejorar la eficiencia de la aplicación haciendo uso de otros entornos de

programación diferentes a MATLAB, que resulta fácil, intuitivo y de gran poder

didáctico pero que carece de un rendimiento óptimo en cuanto a tiempo de

ejecución se refiere.

o Obtener un conjunto adicional de medidas de forma (p.ej: forma global del objeto,

ejes menor y mayor, …).

o Generalizar el método para la extracción de medidas de un conjunto de objetos

presentes en la escena

o Mejorar la estimación de la medida del área aplicando otros métodos con menor

porcentaje de error.


57


58


59

Bibliografía

[1] J.F Vélez, A.B Moreno, Á. Sánchez y J.L Esteban, “Visión por Computador”,

Universidad Rey Juan Carlos, 2003.

[2] L. Enrique Sucar, “Vision computacional y sus aplicaciones”, Biblios:

Periodico La Jornada de Oriente [On line]. [consultado el 6.12.08]. Disponible en:

http://www.lajornadadeoriente.com.mx/2008/10/06/puebla/arroba14.php

[3] http://es.wikipedia.org

[4] D.Hall1, J. Nascimento

2, E.Andrade, et al, “Comparison of target detection

algorithms using adaptative background models”, INRIA Rhône-Alpes, France1, IST

Lisbon, Portugal2, University of Edinburgh, UK

3.

[5] L. Guerra Artal, “Seguimiento visual artificial”, Biblios. [consultado el

7.12.08]. Disponible en:

http://www.fulp.ulpgc.es/files/webfm/File/web/publicaciones/vectorplus/articulos/vp22

_05_articulo02.pdf

[6] J. MacCormick, “Stochastic Algorithms for Visual Tracking”, pringer-Verlag,

London, 2002.

[7] J.Hernández Sánchez, “Filtros de Partículas con Realimentación basada en

Memoria”, Proyecto Fin Carrera Universidad Rey Juan Carlos, Junio 2007.

aplicación del filtro de partículas al seguimiento de un...

Documents