Reconocimiento de Objetos usando Vision artificial - Repositorio
SISTEMA DE RECONOCIMIENTO DE OBJETOS REMOVIDOS DE UNA … · 2017-02-16 · sistema de...
Transcript of SISTEMA DE RECONOCIMIENTO DE OBJETOS REMOVIDOS DE UNA … · 2017-02-16 · sistema de...
SISTEMA DE RECONOCIMIENTO DE OBJETOS REMOVIDOS DE UNA ESCENA,
UTILIZANDO VISIÓN POR COMPUTADOR
JAVIER ADOLFO PACHECO SÁNCHEZ
PONTIFICIA UNIVERSIDAD JAVERIANA
FACULTAD DE INGENIERÍA
CARRERA DE INGENIERÍA ELECTRÓNICA
BOGOTÁ D.C.
JUNIO DE 2011
2
SISTEMA DE RECONOCIMIENTO DE OBJETOS REMOVIDOS DE UNA ESCENA,
UTILIZANDO VISIÓN POR COMPUTADOR
T.G. 1114
TRABAJO DE GRADO PARA OPTAR AL TÍTULO DE INGENIERO ELECTRÓNICO
DIRECTOR
FRANCISCO CARLOS CALDERÓN B. M.Sc.
INGENIERO ELECTRÓNICO
PONTIFICIA UNIVERSIDAD JAVERIANA
FACULTAD DE INGENIERÍA
CARRERA DE INGENIERÍA ELECTRÓNICA
BOGOTÁ D.C.
JUNIO DE 2011
3
Pontificia universidad javeriana
Facultad de ingeniería
Departamento de Electrónica
Rector Magnifico PADRE JOAQUÍN EMILIO SÁNCHEZ GARCÍA S.J.
Decano Académico ING. FRANCISCO JAVIER REBOLLEDO MUÑOZ.
Decano del Medio PADRE SERGIO BERNAL RESTREPO S.J.
Director de Carrera ING. JUAN MANUEL CRUZ BOHORQUEZ.
Director de Proyecto ING. FRANCISCO CARLOS CALDERON B. M.Sc.
Asesor de Proyecto ING. ALEJANDRO FORERO GUZMÁN
4
ARTICULO 23 DE LA RESOLUCIÓN No. 13 DE JUNIO DE 1946
“La Universidad no se hace responsable de los conceptos emitidos por sus alumnos en sus
proyectos de grado.
Solo velará porque no se publique nada contrario al dogma y a la moral católica y porque los
trabajos no contengan ataques o polémicas puramente personales. Antes bien, que se vea en ellos
el anhelo de buscar la verdad y la justicia.”
5
AGRADECIMIENTOS
Primero que todo le doy gracias a Dios por haberme ayudado a llegar hasta aquí.
A mis padres y mi hermana al igual que tíos, y abuelos, por todo el apoyo, tanto moral como
económico, para que pudiera finalizar la carrera.
A mi director de trabajo de grado, el Ingeniero Francisco Carlos Calderón, por el apoyo brindado
en todos estos meses para la realización del proyecto, así como la enorme cantidad de cosas que
me enseño relacionadas al proyecto que son de gran ayuda para mi vida profesional.
Agradecer a mis compañeros de cubículo por su compañía, su amistad y las ideas para realizar
este proyecto
Sin todos ellos esto no hubiera sido posible.
¡¡Gracias a todos!!
どうも有り難う
Javier Adolfo Pacheco Sánchez.
6
CONTENIDO
INDICE DE TABLAS ................................................................................................................ 9
INDICE DE FIGURAS ............................................................................................................. 10
INTRODUCCIÓN .................................................................................................................... 11
OBJETIVOS ............................................................................................................................. 12
Objetivo General. .................................................................................................................. 12
Objetivos Específicos. ........................................................................................................... 12
MARCO TEÓRICO .................................................................................................................. 13
IMPLEMENTACIÓN. .......................................................................................................... 13
OpenCV............................................................................................................................. 13
BeagleBoard-xM................................................................................................................ 14
Angstrom. .......................................................................................................................... 16
PlayStation Eye. ................................................................................................................. 17
ALGORITMOS UTILIZADOS. ............................................................................................ 18
SURF (Speeded Up Robust Features). [8] .......................................................................... 18
FLANN (Fast Library for Approximate Nearest Neighbors). .............................................. 20
MATCH TEMPLATE. ...................................................................................................... 24
Métodos Normalizados. ..................................................................................................... 26
ESPECIFICACIONES .............................................................................................................. 27
Diagrama General ................................................................................................................. 27
Entradas y Salidas del Sistema............................................................................................... 28
Especificaciones de los Algoritmos ....................................................................................... 28
7
Herramientas de Desarrollo. .................................................................................................. 29
Descripción. .......................................................................................................................... 29
Diagrama de Bloques del Algoritmo de Diferencia Cuadrada Normalizada............................ 30
Diagrama de Bloques del Algoritmo SURF [8]. ..................................................................... 31
DESARROLLOS ...................................................................................................................... 32
Desarrollo del Algoritmo de Diferencia Cuadrática Normalizada ........................................... 32
Desarrollo del Algoritmo Usando el Método de SURF [8] ..................................................... 37
PROTOCOLO DE PRUEBAS .................................................................................................. 45
Implementación del Algoritmo de Diferencia Cuadrada Normalizada .................................... 45
Implementación del Algoritmo SURF [8] .............................................................................. 46
Implementación en la BeagleBoard-xM [3] ........................................................................... 47
ANÁLISIS DE RESULTADOS ................................................................................................ 48
Pruebas realizadas con el algoritmo de Diferencias Cuadradas Normalizadas ........................ 50
Pruebas realizadas con el algoritmo SURF [8]. ...................................................................... 50
Pruebas realizadas con detección de cambios en la homografía. ............................................. 51
Pruebas realizadas en la BeagleBoard-xM ............................................................................. 52
CONCLUSIONES .................................................................................................................... 54
TRABAJO FUTURO Y RECOMENDACIONES. .................................................................... 56
Anexo 1 .................................................................................................................................... 57
Anexo 2 .................................................................................................................................... 57
Anexo 3 .................................................................................................................................... 57
Anexo 4 .................................................................................................................................... 57
8
Anexo 5 .................................................................................................................................... 57
Anexo 6 .................................................................................................................................... 57
Anexo 7 .................................................................................................................................... 57
Anexo 8 .................................................................................................................................... 57
Anexo 9 .................................................................................................................................... 57
BIBLIOGRAFÍA ...................................................................................................................... 58
9
INDICE DE TABLAS
Tabla 1. Características de la BeagleBoard-xM. Imagen tomada de [3] ..................................... 15
Tabla 2. Parámetros de los filtros de caja para las 3 primeras escalas ......................................... 18
Tabla 3. Procedimiento de pruebas Diferencia Cuadrática Normalizada .................................... 46
Tabla 4. Procedimiento de pruebas SURF [8] ............................................................................ 46
Tabla 5. Análisis de resultados en el algoritmo de Diferencia Cuadrática Normalizada.............. 48
Tabla 6. Análisis de resultados en el algoritmo SURF [8] .......................................................... 49
Tabla 7. Homografía en algoritmo SURF [8] ............................................................................. 51
Tabla 8. Análisis de tiempos en BeagleBoard-xM con algoritmo de Diferencia Cuadrática
Normalizada ............................................................................................................................. 52
Tabla 9. Análisis de tiempos en BeagleBoard-xM con algoritmo SURF [8]. .............................. 52
10
INDICE DE FIGURAS
Imagen 1. BeagleBoard-xM ...................................................................................................... 14
Imagen 2. PlayStation Eye. ....................................................................................................... 17
Imagen 3. Filtros de caja aproximando las derivadas parciales de 2 orden del Gaussiano........... 18
Imagen 4: Proyecciones de árboles jerárquicos construidos usando 100K SIFT con factores de
ramificación: 2, 4, 8, 16, 32, 128, usando la técnica de [13]. Imagen tomada de [9]. .................. 22
Imagen 5. Diagrama en bloques ................................................................................................ 27
Imagen 6. Detalle de video de muestra. Imagen tomada de [15] ................................................ 28
Imagen 7. Diagrama de flujo de Diferencia Cuadrática Normalizada ......................................... 30
Imagen 8. Diagrama de flujo SURF [8] ..................................................................................... 31
Imagen 9. Pausa de Diferencia Cuadrada Normalizada .............................................................. 33
Imagen 10. Selección de región de interés ................................................................................. 34
Imagen 11. Comparación entre imágenes usando diferencia absoluta. ....................................... 35
Imagen 12. Objeto obstruido ..................................................................................................... 36
Imagen 13. Pausa SURF [8] ...................................................................................................... 39
Imagen 14. Selección de región de interés ................................................................................. 40
Imagen 15. Selección de puntos de máscara. ............................................................................. 41
Imagen 16. Comparación entre imágenes usando SURF [8]. ..................................................... 42
Imagen 17. Obstrucción de objeto. ............................................................................................ 43
Imagen 18. Muestra de Imágenes Tomadas para Pruebas. ......................................................... 45
11
INTRODUCCIÓN
El análisis automático de secuencias de video, es un tema que en los últimos tiempos ha tomado
mayor importancia por su creciente demanda en el mercado. Esta es una herramienta diseñada
para ayudar al personal de seguridad en su labor frente a situaciones complejas tales como
aeropuertos, estaciones de buses, centros comerciales, etcétera. El porqué de estos lugares es la
enorme cantidad de personas que frecuentan estos sitios y las implicaciones que tendría en el
funcionamiento de estas si una falla en la seguridad ocurriese.
Un problema frecuente en la seguridad es la remoción de objetos, por esta razón los sistemas de
vigilancia que usan cámaras de video están siendo usados ampliamente, al igual que el uso de
tecnologías que permitan analizar el video de estas cámaras y que puedan identificar cuando un
objeto, que está siendo vigilado, cambia de posición o cuando es removido de determinada área.
Para este trabajo de grado en concreto, se implementan algoritmos que usan visión por
computador y permiten identificar el caso en que los objetos son removidos del área de visión de
una cámara.
Actualmente en el mercado pueden adquirirse muchos sistemas de seguridad que incluyen
cámaras, las cuales se ponen a disposición de personal encargado de supervisarlas
constantemente y verificar la seguridad en tiempo real. La necesidad de estos sistemas es el de
prevenir o detener un incidente indeseable, solamente empleando la atención del personal de
seguridad. Un experimento realizado por el departamento de justicia de los Estados Unidos [1]
para probar la eficiencia de personas, el experimento consistía en el de poner una persona en
frente de uno o varios monitores de video y observar su comportamiento frente a diversos
eventos. Los eventos mostraron que no importa si la persona es dedicada y comprometida con el
trabajo, aproximadamente tras 20 minutos de supervisión de los monitores de video, la atención
de la persona decae a niveles alarmantemente bajos. Por esta razón se propone utilizar un
algoritmo que monitoree continuamente la seguridad.
12
OBJETIVOS
OBJETIVO GENERAL.
Diseñar e implementar un algoritmo de detección de objetos removidos utilizando visión por
computador.
OBJETIVOS ESPECÍFICOS.
Diseñar un algoritmo de visión por computador para la detección de objetos removidos en
una escena.
Construir una base de datos para ser usada con algoritmos de detección de objetos
removidos en escena.
Implementar el algoritmo de detección de objetos removidos en escena sobre un núcleo
OMAP3.
Especificar las condiciones mínimas de operación para un sistema que implemente el
algoritmo diseñado.
13
MARCO TEÓRICO
IMPLEMENTACIÓN.
OpenCV
OpenCV [2] es una librería de código abierto desarrollada por Intel. Está escrita en lenguaje C y
C++ y corre en los sistemas operativos Linux, Windows y Mac OS X. Se ha utilizado en
infinidad de aplicaciones. Desde sistemas de seguridad con detección de movimiento, hasta
aplicativos de control de procesos donde se requiere reconocimiento de objetos.
Uno de los objetivos de OpenCV [2] es el de proveer una infraestructura de visión artificial fácil
de usar, que ayude a la gente a realizar aplicaciones sofisticadas de visión de una manera mucho
más rápida y fácil. La librería de OpenCV [2] contiene más de 500 funciones que abarcan muchas
áreas en la visión, que incluyen inspección de productos de las fábricas, imágenes médicas,
seguridad, calibración de cámaras, visión estéreo y robótica. Visión por computador y
aprendizaje de máquina usualmente van de la mano, OpenCV [2] también contiene una gran
cantidad de librerías de aprendizaje de máquina (MLL) por sus siglas en inglés, esta sub librería
se enfoca en el reconocimiento estadístico de patrones. Las MLL son altamente útiles en las
tareas de visión que son el núcleo de la misión de OpenCV [2], pero es lo suficientemente
generalizado para ser usado para cualquier problema de aprendizaje de máquina.
14
BeagleBoard-xM.
Imagen 1. BeagleBoard-xM
La BeagleBoard-xM [3] está diseñada específicamente para la comunidad de desarrolladores que
utiliza código abierto. La BeagleBoard-xM [3] está equipada con unas características mínimas
que permiten al usuario experimentar las capacidades de cálculo del procesador.
La BeagleBoard-xM [3] contiene un procesador DM3730CBP [4] a 1GHz compatible con los
procesadores OMAP3 [5] y cuenta además con un microprocesador ARM Cortex-A8 [4] y viene
en un empaque dentro de otro empaque, que es una técnica la cual la memoria está ubicada en la
parte superior del procesador, todo esto en tan solo 0.4mm de grosor. También cuenta con
memoria de baja potencia DDR RAM de 512Mb, que permite a los aficionados, innovadores e
ingenieros ir más allá de la imaginación.
Las mejoras del diseño del hardware alcanzan rendimientos similares a dispositivos portátiles
como laptops mientras mantiene bajos niveles de consumo de potencia. Se conecta directamente
a través de sus 4 puertos USB y su puerto Ethernet 10/100, mientras mantiene el tamaño de
8.25cm x 8.25cm.
La BeagleBoard-xM [3] viene equipado con un conector digital DVI-D, el cual puede ser
visualizado en casi cualquier monitor LCD, el procesador soporta hasta 24 bits de color a la
salida, esta salida DVI-D utiliza un conector HDMI escogido por su reducido tamaño.
Estas son algunas de las características de la BeagleBoard-xM [3], el siguiente listado (Tabla 1)
nos permite conocer más de lo que la BeagleBoard-xM [3] nos ofrece.
15
Tabla 1. Características de la BeagleBoard-xM. Imagen tomada de [3]
OMAP3
La familia de procesadores OMAP3 [5] tiene aplicaciones multimedia que acercan el rendimiento
al nivel de un computador portátil, al igual que la productividad y entretenimiento avanzado para
los dispositivos móviles que soportan aplicaciones multimedia. Algunos de los beneficios del
procesador OMAP3 [5] son:
Combina entretenimiento móvil y aplicaciones de alto rendimiento.
16
Integra un avanzado núcleo SuperScalar ARM Cortex-A8 [4].
Diseñado con tecnología CMOS de 65nm para bajo consumo de potencia y rendimiento
optimizado.
Disponible también con un procesador de imágenes que permite captura de imágenes más
rápido y de alta calidad, en un sistema de bajo costo y bajo consumo.
Soporta todos los sistemas operativos de alto nivel para creación de interfaces
personalizables, algunos son Linux, Windows Mobile, Android y Symbian.
Angstrom.
Fue creado por un pequeño grupo de personas que trabajaron en proyectos para unificar sus
esfuerzos para hacer una distribución más amigable para sistemas embebidos.
Angstrom [6] es una distribución portátil con núcleo reconfigurable que corre en todos los
dispositivos Linux con un núcleo 2.6.x para dispositivos embebidos, principalmente a los
dispositivos portátiles como PDA, teléfonos inteligentes, dispositivos de mano portátiles, routers,
etc. es versátil y creado para ser amigable con el usuario. También es capaz de soportar
dispositivos estándar de computadores de escritorio. Puede ejecutarse en dispositivos con 4Mb de
memoria Flash hasta dispositivos de Terabytes de almacenamiento.
La distribución de Angstrom [6] no tiene licencia, pero todos los paquetes utilizados sí, eso
significa que deberá evaluar que paquetes usará. Con esto se tiene un manejo completo de los
paquetes, acceso a un vasto inventario de repositorios de software pre-empaquetado con la
posibilidad de instalarlo directamente sobre la red, es ágil y con actualizaciones de seguridad,
registro de errores y una interfaz flexible.
La distribución de GNU/Linux basada en Angstrom, usada en este trabajo, se desarrolló por el
grupo de investigación en Sistemas Inteligentes Robótica y Percepción (SIRP1) de la Pontificia
Universidad Javeriana.
1 www.gruposirp.org
17
PlayStation Eye.
La cámara utilizada en este proyecto es una Sony PlayStation Eye. [7]. Que se observa a
continuación.
Imagen 2. PlayStation Eye.
Una de las principales características2 que se tuvieron en cuenta para la realización del proyecto
son las siguientes:
Lente de zoom con campo visual de 6 a 75 grados
Foco fijo, de 1 pie hasta el infinito (no requiere ajuste manual)
640 x 480 a 60 secuencias por segundo
320 x 480 a 120 secuencias por segundo
Rango dinámico de 8 bits o 10 bits
Transferencias de alta velocidad por USB 2.0
Video sin comprimir o con compresión JPEG opcional
2 Características de video tomadas de [7]
18
ALGORITMOS UTILIZADOS.
SURF (Speeded Up Robust Features). [8]
Usa una aproximación del determinante de la matriz Hessiana, elegida por su estabilidad,
repetitividad y su velocidad en cómputo. Un filtro ideal podría construir el Hessiano haciendo la
circunvolución de la derivada de segundo orden del Gaussiano de una imagen con determinada
escala σ. Esto se aproxima reemplazando los filtros Gaussianos de segundo orden, con un filtro
de caja, como se muestra en la figura.
Imagen 3. Filtros de caja aproximando las derivadas parciales de 2 orden del Gaussiano
Tabla 2. Parámetros de los filtros de caja para las 3 primeras escalas
Tamaño de filtro Q1 Q2 Q3 Q4 Q5
9 3 5 3 1 1.593
15 5 9 5 1 2.700
21 7 11 7 1 3.680
Los filtros de caja se eligen porque pueden ser evaluados eficientemente usando la llamada
integral de imagen (II), definida en términos de la imagen (I):
( ) ∑ ∑ ( )
.
Para alcanzar la invariancia en la escala, los filtros son evaluados en un número diferente de
escalas „s’ y la máxima local en la escala y posición en el espacio de un conjunto de funciones
detectadas. Aquí s= σ, la escala de la Gaussiana es usada para derivar el filtro de caja. Un umbral
19
mínimo H0 en los valores límite de respuesta al número total de funciones. La ubicación x0 de
cada característica es luego refinada a una exactitud sub-pixel, usando la siguiente ecuación:
(
)
.Donde x ( ) T
son las coordenadas espacio-escalar y H es la
magnitud del determinante Hessiano. Las derivadas de H son computadas alrededor de x0 con
diferencias finitas.
La invariancia en la rotación es alcanzada detectando la orientación dominante de la imagen
alrededor de cada característica usando los coeficientes pasa altas de un filtro Haar tanto en x
como en y dentro de un circulo de radio 6s. El tamaño del filtro Haar esta escalado para que sea
de 4sx4s, y las locaciones de muestra también están escaladas por s, que fácilmente son
completadas usando la integral de imagen. Los vectores 2D resultantes son ponderados por una
Gaussiana con σ=2.5s y luego organizado por orientación. Los vectores son sumados en una
ventana deslizante de tamaño
, y la orientación es tomada de la salida de la ventana con la
magnitud más grande.
Una vez la posición, la escala y orientación son determinadas, la función descriptora es
computada, el cual es usada para igualar funciones a lo largo de las imágenes. Esta es construida
a partir de un conjunto de respuestas de Haar, calculadas en una matriz de 4x4 de subregiones de
un cuadrado de tamaño 20s alrededor de cada punto de la función, situada hacia la orientación
dominante. 25 respuestas 2D de Haar (dx, dy) son computadas usando filtros de tamaño 2s x 2s
dentro de una matriz de 5x5 dentro de cada sub región y ponderado por una Gaussiana con
σ=3.3s centrada en el punto de interés. Por todo esto se especifica que las respuestas dx y dy sean
situadas relativamente hacia la región dominante de la función, pero no como computarlas. Desde
la integral de imagen, podemos solo sumar regiones alineadas al eje, computamos respuestas
alineadas al eje y rotamos el vector 2D resultante. Cada sub región construye un vector de 4
dimensiones de estas respuestas (∑ ∑ ∑| | ∑| |).
Combinando los vectores v de cada sub región nos lleva a un solo descriptor de 64 o 128
dimensiones, dependiendo de la escogencia del usuario, el cual es normalizado a un vector
unitario que provee la invariancia del contraste. Como discriminador final, el signo de la traza de
la matriz Hessiana es usada para distinguir funciones de luz y sombra y viceversa. El algoritmo
total corre en aproximadamente 354ms en un procesador Pentium IV de 3GHz con una imagen de
800x640, desde luego el tiempo exacto varía dependiendo de los descriptores detectados.
20
FLANN (Fast Library for Approximate Nearest Neighbors).
Se puede definir el problema de la búsqueda del vecino más cercano de la siguiente manera: dado
un conjunto de puntos P=p1+p2+…+pn en un espacio X, estos puntos deben ser pre-procesados
de tal forma que dado un nuevo punto de búsqueda , encontrar el punto en P que es más
cercano a q puede ser realizado rápidamente. [9]
El problema de la búsqueda del vecino más cercano es uno de mayor importancia en una variedad
de aplicaciones tal como reconocimiento de imágenes, compresión de datos, reconocimiento de
patrones y clasificación, aprendizaje de máquina, sistemas de recuperación de documentos,
estadística y análisis de datos. Como sea, resolver este problema en un espacio multidimensional
parece ser una tarea bastante ardua y no existe ese algoritmo que realice la tarea
significativamente mejor que los buscadores por fuerza bruta. Esto ha llevado a un interés
creciente en esa clase de algoritmos que realicen búsquedas aproximadas del vecino más cercano,
el cual ha probado ser una aproximación bastante buena en la mayoría de las aplicaciones
prácticas.
FLANN [9] es una librería para realizar aproximaciones rápidas de los vecinos más cercanos.
FLANN [9] está escrito en lenguaje C++. FLANN [9] puede ser fácilmente usado en la mayoría
de los contextos que usen el lenguaje C, como MATLAB y Python.
Como encontrar rápidamente los vecinos más cercanos aproximados.
La precisión de la aproximación es medida en términos de precisión, el cual es definido en
términos de porcentaje de los puntos de búsqueda para la cual el vecino más cercano es
encontrado. En los experimentos realizados por Marius Muja y David Lowe [9] uno de dos
algoritmos obtuvo el mejor rendimiento, dependiendo de los datos y a precisión deseada. Estos
algoritmos se usan tanto para árboles k.esimos jerárquicos que de ahora en adelante se llamaran
“k-means tree” o múltiples árboles k-esimos aleatorios que de ahora en adelante se llamaran “kd-
tree”, se describirán estos algoritmos a continuación. [9]
Algoritmo de kd-tree aleatorio.
El clásico algoritmo de kd-tree [10] es eficiente en bajas dimensiones, pero en altas dimensiones
el rendimiento rápidamente decae. Para obtener un impulso sobre búsqueda lineal se hace
21
necesaria una aproximación al vecino cercano. Esto mejora la velocidad de búsqueda al costo de
que el algoritmo no estará retornando el vecino cercano exacto. El algoritmo original de kd-tree
elaborado por [11], separa los datos a la mitad en cada nivel del árbol en la dimensión en la cual
los datos muestran una gran varianza. Por comparación, los arboles aleatorios son construidos
escogiendo la dimensión a partir al azar desde la primera dimensión D en la que el dato tiene gran
varianza. Se utilizó el valor predefinido D=5 en la implementación (Pruebas realizadas por [9]),
ya que traban bien en todos los datos implementados, pero no mejora significativamente la
obtención de datos de ahí en adelante. [9]
Cuando se busca en los árboles, una prioridad en la cola es mantenida a lo largo de todo el árbol
aleatorio, así la búsqueda puede ser ordenada incrementando la distancia a cada frontera. El grado
de aproximación se determina examinando el valor predefinido en los nodos de las hojas, en los
que los puntos de búsqueda son terminados y los mejores candidatos son retornados. En la
implementación el usuario especifica la precisión de la búsqueda deseada. [9]
El algoritmo de k-means tree jerárquico.
El árbol kd-tree jerárquico es construido dividiendo los datos en cada nivel en K distintas
regiones usando agrupamiento k-ésimo y luego aplicando el mismo método recursivamente a los
puntos de cada región. Se detiene la recursión cuando el número de puntos en la región es más
pequeño que K. La Imagen 4 muestra las proyecciones realizadas sobre diversos árboles kd-tree
construidos con 100K SIFT [12] usando diferentes factores de ramificación. [9]
22
Imagen 4: Proyecciones de árboles jerárquicos construidos usando 100K SIFT con factores de ramificación: 2, 4, 8, 16, 32, 128, usando la técnica de [13]. Imagen tomada de [9].
El algoritmo inicialmente realiza un barrido transversal a través del árbol y añade una cola de
prioridades a todas las ramas no exploradas en cada nodo a lo largo del camino. A continuación
se extrae desde el primer nodo en la cola que tenga el centro más cercano al punto de búsqueda y
reinicia el árbol transversal desde esa rama. En cada transversal el algoritmo mantiene añadiendo
a la cola de prioridades las ramas no exploradas a lo largo del camino. El grado de aproximación
es especificado de la misma forma que los arboles aleatorios kd-tree, deteniendo cada búsqueda
justo antes de que el número predeterminado de nodos se hayan examinado. Este parámetro es
establecido durante el entrenamiento para lograr la precisión esperada por el usuario. [9]
Selección automática de algoritmo.
Los experimentos realizados por Marius Muja y David Lowe [9] revelaron que el algoritmo
óptimo para la aproximación rápida del vecino más cercano es altamente dependiente de distintos
factores como la estructura de los datos y le deseada precisión de la búsqueda. Adicionalmente a
eso cada algoritmo tiene su conjunto de parámetros que tienen una influencia significante en el
rendimiento de la búsqueda. Estos parámetros incluyen el número de árboles aleatorios para usar
23
en el caso de los kd-tree o el factor de ramificación y el número de iteraciones en el caso del
árbol jerárquico k-means tree. [9]
Considerando el algoritmo en si como parámetro de una búsqueda genérica del vecino más
cercano, el problema es reducido a determinar los parámetros que den la mejor solución. Este es
un problema de optimización en el parámetro de espacio. El costo es computado como una
combinación de tiempo de búsqueda, tiempo de construcción del árbol y memoria del árbol.
Dependiendo de la aplicación, cada uno de estos tres casos tiene diferente importancia, en
algunos casos no nos importa mucho el tiempo de construcción del árbol, mientras que en otros
casos ese tiempo y el tiempo de búsqueda deben ser pequeños. También hay situaciones en las
que se desean limitar las condiciones de memoria. Se controla la importancia relativa de cada uno
de los factores usando el peso del tiempo de construcción wb, y el peso de la memoria wm, para
computar el costo:
( )
Donde s representa el tiempo de búsqueda para el numero de vectores en una sola muestra de
datos, b representa el tiempo de construcción del árbol, y m=mt/md representa la relación entre la
memoria utilizada para el árbol (mt) y la memoria usada para guardar los datos (md). [9]
El peso del tiempo de construcción (wb) controla la importancia del tempo de construcción
relativo al tiempo de búsqueda. Estableciendo wb=0 significa que se quiere una búsqueda rápida,
mientras wb=1 significa que el tiempo de construcción del árbol y el tiempo de búsqueda tiene la
misma importancia. Similarmente el peso de la memoria wm controla la importancia de la
sobrecarga de memoria comparada con el tiempo de sobrecarga. El tiempo de sobrecarga es
computado relativo al óptimo costo tiempo (s+ wbb)opt , el cual es definido como búsqueda
optima y el tiempo necesario si el uso de memoria no es un factor. Si se establece wm=0 se
elegirá el algoritmo y parámetros que resultan en una búsqueda rápida y tiempo de construcción
sin importar mucho la sobrecarga de memoria, mientras se establece wm=1 le dará igual peso a
un porcentaje dado incrementando el uso de memoria al mismo porcentaje en búsqueda y tiempo
de construcción. [9]
Escogemos el mejor algoritmo de vecino cercano y el parámetro óptimo en una aproximación de
2 etapas: una exploración global del parámetro de espacio seguido por una modificación local
24
para mejor rendimiento. Inicialmente se muestrea el parámetro espacio en múltiples puntos y se
eligieron estos valores para minimizar el costo de la ecuación anterior. Para este paso se
considera utilizar [1,4,8,16,32] como numero aleatorio del kd-tree, [16,32,63,128,256] como el
factor de ramificación de los arboles k-mean y [1,5,10,15] como el número de iteraciones del
árbol k-mean. En el segundo paso se usa el método de simplificación de Nelder-Mead,
implementado en la librería, para acercarse al parámetro espacio y obtener el mejor parámetro
obtenido en el primer paso. Pero este paso no garantiza el mínimo global, los experimentos
realizados por Marius Muja y David Lowe [9] mostraban que el parámetro obtenido era cercano
al óptimo. [9]
La optimización podría correr en toda la serie de datos o en una fracción de estos. Usando toda la
serie de datos daría el resultado más acertado, pero en el caso de grandes series de datos esto
puede tomar más tiempo del deseado. Una opción es proveer el uso de una fracción de esa serie
de datos para seleccionar los parámetros. Los experimentos realizados por Marius Muja y David
Lowe [9] mostraron que solo usando un décimo de la serie de datos, los valores de los parámetros
seleccionados realizan un acercamiento a la serie de datos. El parámetro de selección necesita ser
realizado solo una vez y la librería permite usar esos valores y ser almacenados y aplicados en
todas las futuras series de datos del mismo tipo. [9]
MATCH TEMPLATE.
El algoritmo MATCH TEMPLATE (cvMatchTemplate) que de ahora en adelante se llamará
diferencia cuadrática normalizada, se encuentra presente en la librería de OpenCV [2], usa una
técnica que encuentra una muestra de la imagen y la compara sobre una imagen más grande, El
procedimiento de esta función es que la imagen más pequeña hace un barrido por la imagen de
base más grande, desde la esquina superior izquierda hasta la esquina inferior derecha, usando
uno de los métodos que se mencionan más adelante.
El algoritmo tiene varias aplicaciones, entre las cuales están el reconocimiento de rostros,
procesamiento de imágenes médicas, seguimiento de objetos, etc.
25
Esta función recibe como parámetros la imagen a buscar, la imagen de base donde se buscará una
imagen en blanco donde se guardara los resultados y el método para realizar la comparación,
estos métodos son:
METODO DE DIFERENCIAS CUADRADAS.
( ) ∑[ ( ) ( )]
Donde T es la imagen sobre la cual se va a comparar, I es la imagen de entrada y R es el resultado
[14]. Si la imagen I es de y la imagen T es de , entonces el resultado es una imagen
de ( ) ( ).
Cuando el resultado de este método es 0, indica que las dos imágenes encajan perfectamente, lo
contrario a que si el resultado es un número muy grande, las imágenes no coinciden entre sí.
MÉTODO DE CORRELACIÓN.
( ) ∑[ ( ) ( )]
Este método como es multiplicativo nos indica que, cuando las imágenes coinciden entre sí, el
resultado es un numero grande, caso contrario, si las imágenes no coinciden el resultado es muy
pequeño o cero.
MÉTODO DE COEFICIENTES DE CORRELACIÓN.
( ) ∑[ ( ) ( )]
( ) ( )
( ) ∑ ( )
( ) ( )
( ) ∑ ( )
En este método si el resultado es 1 entonces las dos imágenes coinciden perfectamente, si el
resultado es -1 las imágenes desencajan perfectamente y si el resultado es 0 entonces no existe
correlación entre las imágenes.
26
Métodos Normalizados.
Para cada uno de los tres métodos mencionados anteriormente, existen las versiones normalizadas
de las funciones, estas son bastante útiles, ya que ayudan a reducir el ruido proveniente de las
diferencias entre iluminación de la imagen de muestra y la imagen de base. Para cada función, el
coeficiente de normalización es el mismo, así:
( ) √∑ ( )
∑ ( )
Quedando los demás métodos normalizados de la siguiente forma.
MÉTODO DE DIFERENCIAS CUADRADAS NORMALIZADAS.
( ) ( )
( )
MÉTODO DE CORRELACIÓN NORMALIZADO
( ) ( )
( )
MÉTODO DE COEFICIENTES DE CORRELACIÓN NORMALIZADOS
( ) ( )
( )
En este proyecto se seleccionó el método de diferencias cuadradas normalizadas para una
comparación a bajo nivel de la secuencia de video, tomando como imagen de muestra a buscar,
un área a selección del usuario y como imagen de base, el video tomado de la cámara USB.
La razón de la elección de este algoritmo es que en la etapa de diseño del algoritmo, se observó
que el método era el que menos error tenía en la comparación entre plantillas, frente a los demás
métodos ya explicados, además también es el segundo de más rápido calculo por debajo de la
diferencia cuadrática sin normalizar. [14]
27
ESPECIFICACIONES
DIAGRAMA GENERAL
El siguiente diagrama ilustra el principio básico de funcionamiento del sistema desarrollado, se
nota a la izquierda de la figura un objeto, que es capturado por la cámara, este luego es analizado
por la plataforma OMAP3 [5] y luego de hacer su debido procesamiento de secuencia de video se
muestra la imagen a través del monitor.
Imagen 5. Diagrama en bloques
El proyecto busca que la imagen proveniente de una cámara fija conectada a través de un puerto
USB, reconozca cuando un objeto es removido del área de visión e indique en que momento fue
retirado, y luego de esto indica al personal de seguridad la ubicación donde se encontraba el
objeto junto con una señal visualizada en pantalla, como se muestra en la imagen.
28
Imagen 6. Detalle de video de muestra. Imagen tomada de [15]
Todo el sistema se compone principalmente por la cámara, la tarjeta de desarrollo y un monitor.
Las secuencias de video son procesadas por una plataforma OMAP3 [5] utilizando la tarjeta de
desarrollo BeagleBoard-xM [3]. El procesamiento de la secuencia de video utiliza un algoritmo
basado en visión artificial, que está bajo el lenguaje C y C++, usando librerías de OpenCV [2]
Luego de procesar la secuencia de video, este algoritmo identifica cuando un objeto es removido
del área de visión de la cámara y a su vez presentará el instante en que el objeto fue retirado u
obstruido totalmente por cierto intervalo de tiempo.
ENTRADAS Y SALIDAS DEL SISTEMA
La entrada del sistema descrito, es el video y el área de la región de interés seleccionada por el
usuario.
La salida del sistema será una señal visual presentada en el video que alerte al personal encargado
de revisar este.
ESPECIFICACIONES DE LOS ALGORITMOS
Desarrollando el algoritmo anteriormente descrito se busca lo siguiente:
Alto índice de robustez, en el cumplimiento de las tareas de detección y visualización,
empleando visión por computador.
Agilidad en la instalación del sistema para realizar las pruebas correspondientes.
29
HERRAMIENTAS DE DESARROLLO.
En el desarrollo del proyecto se utilizó el sistema operativo Ubuntu 10.10 (maverick meerkat)
[16] y usando el IDE3 GCC
4 [17] usando las librerías de OpenCV [2] debido a su facilidad en las
pruebas de los algoritmos.
DESCRIPCIÓN.
El proyecto se realizó enteramente en lenguaje C y C++ usando las librerías de OpenCV [2]
aplicando visión artificial. Este proyecto contiene cuatro etapas principales. Cada etapa es similar
en los dos algoritmos desarrollados la diferencia radica en la forma en que se hace la
comparación entre las imágenes presentadas por la cámara web.
La primera etapa consiste en capturar las imágenes que provienen de la cámara web y
progresivamente presentarlas en el monitor hasta que el usuario oprima la tecla para pausar el
video. En la segunda etapa el usuario procede a seleccionar con el mouse el área que se desee
realizar la vigilancia del objeto partiendo de la imagen mostrada por la pausa del video. La
tercera etapa es determinar si el objeto fue removido u obstruido totalmente por determinado
tiempo y paralelamente a esto mostrar en el monitor las imágenes de la ejecución de los
algoritmos. La última etapa es la de mostrar en el monitor el momento en que el objeto es
reportado como removido u obstruido una vez se haya comprobado por el algoritmo que el objeto
no se encuentre o se encuentre obstruido en su mayoría.
3 Integrated Development Environment
4 GNU Compiler Collection
30
DIAGRAMA DE BLOQUES DEL ALGORITMO DE DIFERENCIA CUADRADA
NORMALIZADA.
INICIO
Buscar Cámara Buscar Video Salida
CapturaImagen
AplicaciónFiltro
Gaussiano
MostrarVideo
Pausa
SI
NO NO
SI
NO
Selección de Área ROI
Comparación Entre ROI y
Video
Comparación entre imagen y plantilla usando diferencia
absoluta.
Determinación de valores mínimos y máximos
ContadorObstrucción = 20?
ContadorFin de
Programa = 0
Contador Fin de Programa = 3?
Advertencia Objeto
Obstruido
Valor mínimo >= 0.3?
Adelantar video Ta
segundos.
Hay Imagen?
Contador Objeto
Obstruido + 1
SI
SI SI
NONO NO
NO
SI
Contador Fin de Programa + 1
Mostrar Imagen de Objeto
AlmacenamientoImagen ROI
SI
Imagen 7. Diagrama de flujo de Diferencia Cuadrática Normalizada
31
DIAGRAMA DE BLOQUES DEL ALGORITMO SURF [8].
INICIO
Buscar Cámara Buscar Video Salida
CapturaImagen
AplicaciónFiltro
Gaussiano
MostrarVideo
Pausa
SI
NO NO
SI
NO
Selección de Área ROI
Selección de Puntos para
Máscara
Extraccion de puntos SURF
ContadorObstrucción = 20?
ContadorFin de
Programa = 0
Contador Fin de Programa = 3?
Advertencia Objeto
Obstruido
Valor Descriptores > 4?
Adelantar video Ta
segundos.
Hay Imagen?
Contador Objeto
Obstruido + 1
SI
SI SI
NONO NO
NO
SI
Contador Fin de Programa + 1
Mostrar Imagen de Objeto
Conversión de Imagen a escala de
grises
Almacenamiento de Imagen de Base
Comparación entre plantillas usando
SURF.
Localización de Objeto
Ubicación de puntos FLANN
Mostrar Imagen
SI
Almacenamiento Imagen ROI
Imagen 8. Diagrama de flujo SURF [8]
32
DESARROLLOS
Desarrollo del Algoritmo de Diferencia Cuadrática Normalizada
Inicio.
Este bloque es el que inicializa todas las variables globales y las funciones necesarias en la
ejecución del programa.
Buscar Cámara.
El algoritmo busca si hay una cámara conectada al equipo, si lo hay entonces pasaría a la etapa de
capturar secuencia y almacenarla en el equipo. Caso contrario pasaría a la etapa de buscar si
recibió una ruta de una secuencia de video almacenada en el equipo.
Buscar Video.
Solo entra a esta etapa si el algoritmo no encontró ningún dispositivo de video conectado al
equipo, si el algoritmo recibe una ruta de secuencia de video almacenada en el equipo pasara a la
etapa de capturar la secuencia. Caso contrario el algoritmo termina de ejecutarse.
Captura Imagen.
Dependiendo de la condición de entrada, ya sea por cámara o por video almacenado, esta etapa
extrae por cada iteración de un ciclo un cuadro y si se da el caso que no hay cuadro, es decir el
apuntador de la imagen es NULL finaliza la ejecución del programa.
Hay Imagen.
Aquí se revisa la condición de la etapa anterior de capturar imagen, si el apuntador de la imagen
no apunta a ninguna dirección de memoria finaliza la ejecución del programa, caso contrario pasa
a la etapa de aplicar un filtro para suavizar la imagen, en este algoritmo se usó el filtro gaussiano
debido a la nitidez con la que mantenía la imagen a comparación de los demás tipos de filtros.
Luego de esto se procede con la etapa de mostrar video.
33
Mostrar Video.
Esta etapa muestra en pantalla por cada iteración del ciclo, la imagen obtenida por la etapa de
capturar imagen.
Pausa video.
Durante la ejecución del algoritmo se puede oprimir la letra p ya sea minúscula o mayúscula, esto
hace que la ejecución de la secuencia de video se detenga momentáneamente y la última imagen
obtenida por la etapa de capturar imagen se muestre en una ventana distinta en la que pasaría a la
siguiente etapa.
Imagen 9. Pausa de Diferencia Cuadrada Normalizada
Selección de área ROI (Region Of Interest).
Con la imagen presentada en la ventana independiente de la de video se procede a seleccionar
con el mouse haciendo clic en la esquina del área que desea que el algoritmo analice y
arrastrando el mouse hasta la esquina contraria a la primera selección. Esto hará que esa área
seleccionada sea una nueva imagen que se visualizará en otra ventana. Esta nueva imagen se
34
tomara como imagen de base con la que se dispondrá a analizar el resto del video. Será
almacenada temporalmente y paralelamente al algoritmo.
Imagen 10. Selección de región de interés
Almacenamiento de Imagen ROI.
En la etapa anterior la imagen seleccionada por el operador a través del mouse será almacenada
en una variable global para ser usada durante el resto de la ejecución del video.
Comparación entre ROI y video.
Esta etapa se encarga de seleccionar una imagen de la secuencia de video ligeramente más grande
que la seleccionada en la etapa anterior, con el fin de garantizar que la comparación entre la
imagen y la plantilla funcione sin error alguno.
Comparación entre imagen y plantilla usando diferencia absoluta.
Esta etapa se hace una comparación entre la imagen obtenida en la etapa de selección de ROI
junto con el resto del video de ese punto en adelante, utilizando el método de diferencia absoluta.
35
Imagen 11. Comparación entre imágenes usando diferencia absoluta.
Determinación de valores mínimos y máximos.
El resultado de la ejecución del método de diferencia absoluta, nos da un resultado que es el que
se analiza y así comprobar si el objeto aún se encuentra dentro del área seleccionada por el
usuario.
Contador Obstrucción.
Esta etapa es para revisar si el objeto se encuentra presente, pero con la diferencia de que fue
obstruido parcial o totalmente por un corto periodo de tiempo, se tienen dos contadores
temporales que son los que nos indican si el objeto esta obstruido (Contador Obstrucción) o si fue
removido del área de visión de la cámara (Contador Fin de Programa). La razón de si el contador
obstrucción es igual a 20 es que si después del mismo número de ciclos no se alcanza el límite de
3 para el contador de fin de programa entonces este último se reinicializa a 0 garantizando que lo
ocurrido solo fue una obstrucción temporal del objeto.
36
Contador Fin de Programa.
Este contador temporal garantiza que el objeto aún se encuentra presente en el área de visión
seleccionada por el usuario, el valor máximo es 3, y si este contador iguala este valor se puede
asegurar que el objeto ha sido removido u obstruido por un tiempo considerable, mostrando una
advertencia cuando esto sucede. Este contador se reinicia a 0 cuando después de 20 ciclos el
objeto se encuentra aún presente en el área seleccionada.
Advertencia Objeto Obstruido.
Esta etapa detiene el video en el instante en que se confirma que el objeto se ha perdido u
obstruido por un tiempo considerable y también indica el segundo en que el algoritmo lo detecta.
Posteriormente muestra la imagen detenida del video mostrando el caso, y por último se finaliza
la ejecución del programa.
Imagen 12. Objeto obstruido
Valor Mínimo.
Este valor proviene de la etapa de determinación de valores mínimos y máximos para este
algoritmo solo se tomó el valor mínimo y si este es mayor o igual a 0.3 se podría decir que el
37
objeto se encuentra presente en el área seleccionada, en ese momento se incrementa el contador
de objeto obstruido en 1 y regresa a la etapa de capturar imagen de la secuencia de video. De ser
lo contrario se daría paso a la etapa en que se adelanta la secuencia de video en 10 cuadros y así
volver a revisar si el objeto se encuentra o no.
Adelantar el video en Ta segundos.
Esta etapa se activa cuando la etapa de valor mínimo indica que podría no estar el objeto presente
en el área de selección u obstruido por un tiempo considerable, en este caso se avanza la
secuencia de video en 10 cuadros que son aproximadamente 3.3 segundos a 30 cuadros por
segundo, además de esto se incrementa en 1 el contador fin de programa, que si este llega a 3 se
puede decir que se dieron las condiciones necesarias para indicar que el objeto no se encuentra
presente o, está obstruido por un tiempo considerable en el área de selección, luego de esto se
regresa a la etapa de capturar imagen y así iniciar el ciclo para confirmar si el objeto se encuentra
o no presente.
Desarrollo del Algoritmo Usando el Método de SURF [8]
Inicio.
Este bloque es el que inicializa todas las variables globales y las funciones necesarias en la
ejecución del programa.
Buscar Cámara.
El algoritmo busca si hay una cámara conectada al equipo, si lo hay entonces pasaría a la etapa de
capturar secuencia y almacenarla en el equipo. Caso contrario pasaría a la etapa de buscar si
recibió una ruta de una secuencia de video almacenada en el equipo.
Buscar Video.
Solo entra a esta etapa si el algoritmo no encontró ningún dispositivo de video conectado al
equipo, si el algoritmo recibe una ruta de secuencia de video almacenada en el equipo pasara a la
etapa de capturar la secuencia. Caso contrario el algoritmo termina de ejecutarse.
38
Captura Imagen.
Dependiendo de la condición de entrada, ya sea por cámara o por video almacenado, esta etapa
extrae por cada iteración de un ciclo un cuadro y si se da el caso que no hay cuadro, es decir el
apuntador de la imagen es NULL finaliza la ejecución del programa.
Hay Imagen.
Aquí se revisa la condición de la etapa anterior de capturar imagen, si el apuntador de la imagen
no apunta a ninguna dirección de memoria finaliza la ejecución del programa, caso contrario pasa
a la etapa de aplicar un filtro para suavizar la imagen, en este algoritmo se usó el filtro gaussiano
debido a la nitidez con la que mantenía la imagen a comparación de los demás tipos de filtros.
Luego de esto se procede con la etapa de mostrar video.
Mostrar Video.
Esta etapa muestra en pantalla por cada iteración del ciclo, la imagen obtenida por la etapa de
capturar imagen.
Pausa video.
Durante la ejecución del algoritmo se puede oprimir la letra p ya sea minúscula o mayúscula, esto
hace que la ejecución de la secuencia de video se detenga momentáneamente y la última imagen
obtenida por la etapa de capturar imagen se muestre en una ventana distinta en la que pasaría a la
siguiente etapa.
39
Imagen 13. Pausa SURF [8]
Selección de área ROI (Region Of Interest).
Con la imagen presentada en la ventana independiente de la de video se procede a seleccionar
con el mouse haciendo clic en la esquina del área que desea que el algoritmo analice y
arrastrando el mouse hasta la esquina contraria a la primera selección. Esto hará que esa área
seleccionada sea una nueva imagen que se visualizará en otra ventana. Esta nueva imagen se
tomara como imagen de base con la que se dispondrá a analizar el resto del video. Será
almacenada temporalmente y paralelamente al algoritmo.
40
Imagen 14. Selección de región de interés
Selección de puntos para máscara.
La máscara es una imagen que solo contiene el color negro y el blanco y se toma como imagen de
base en la búsqueda de puntos de interés que son de utilidad en el algoritmo de SURF [8] para
pasos posteriores. Estos puntos se seleccionan manualmente desde la ventana emergente de la
etapa anterior y son escogidos por el usuario, en el algoritmo únicamente se cuenta con 10 puntos
para la selección. La imagen resultante es un área cuyo interior de los puntos seleccionados
toman el color blanco y lo demás toma el color negro.
41
Imagen 15. Selección de puntos de máscara.
Conversión de Imagen a escala de grises.
Esta etapa convierte la imagen de toda la secuencia de video a escala de grises debido a que la
comparación utilizada en el algoritmo requiere como parámetro el uso de imágenes en este
formato.
Extracción de puntos SURF [8].
Esta etapa extrae los puntos de interés, llamados descriptores de imagen, de la primera imagen
seleccionada por el usuario y tomando como limite el área en blanco de la etapa de la selección
de puntos de máscara.
Almacenamiento de Imagen de Base.
Esta etapa nos almacena temporalmente las imágenes que se van a tomar para una futura
comparación con el resto de la secuencia de video, estas imágenes son: la imagen obtenida por la
etapa: Selección de área ROI, pero en escala de grises y la otra imagen es la máscara de blanco y
negro de la etapa de selección de puntos de mascara.
42
Comparación entre plantillas usando SURF [8].
Las imágenes almacenadas en la etapa anterior no se modifican y estas se comparan con la demás
secuencia de video, el algoritmo es capaz de identificar los descriptores de la imagen y los
descriptores de la secuencia de video, trazando una línea entre estos mismos. Con esto se usan los
descriptores usados en la imagen de base y la secuencia de video, y el cambio entre estos
determina si el objeto seleccionado se encuentra ya sea obstruido parcialmente o fue removido.
Imagen 16. Comparación entre imágenes usando SURF [8].
Contador Obstrucción.
Esta etapa es para revisar si el objeto se encuentra presente, pero con la diferencia de que fue
obstruido parcial o totalmente por un corto periodo de tiempo, se tienen dos contadores
temporales que son los que nos indican si el objeto esta obstruido (Contador Obstrucción) o si fue
removido del área de visión de la cámara (Contador Fin de Programa). La razón de si el contador
obstrucción es igual a 20 es que si después del mismo número de ciclos no se alcanza el límite de
3 para el contador de fin de programa entonces este último se reinicializa a 0 garantizando que lo
ocurrido solo fue una obstrucción temporal del objeto.
43
Contador Fin de Programa.
Este contador temporal garantiza que el objeto aún se encuentra presente en el área de visión
seleccionada por el usuario, el valor máximo es 3, y si este contador iguala este valor se puede
asegurar que el objeto ha sido removido u obstruido por un tiempo considerable, mostrando una
advertencia cuando esto sucede. Este contador se reinicia a 0 cuando después de 20 ciclos el
objeto se encuentra aún presente en el área seleccionada.
Advertencia Objeto Obstruido.
Esta etapa detiene el video en el instante en que se confirma que el objeto se ha perdido u
obstruido por un tiempo considerable y también indica el segundo en que el algoritmo lo detecta.
Posteriormente muestra la imagen detenida del video mostrando el caso, y por último se finaliza
la ejecución del programa.
Imagen 17. Obstrucción de objeto.
Valor Descriptores.
Este valor proviene de la etapa de extracción de puntos SURF [8], para este algoritmo se tomaron
los descriptores de la imagen, si este es mayor a un número determinado por el usuario se podría
44
decir que el objeto se encuentra presente en el área seleccionada, para esta implementación del
algoritmo se determinó en la etapa de diseño que el uso de 4 descriptores es suficiente para
caracterizar el objeto, en ese momento pasaría a la siguiente etapa. De ser lo contrario se daría
paso a la etapa en que se adelanta la secuencia de video en 10 cuadros y así volver a revisar si el
objeto se encuentra o no.
Localización de Objeto. Ubicación de puntos FLANN.
Estos bloques son los encargados de encontrar los puntos descriptores tanto en la imagen como
en la secuencia de video, y trazar una línea entre estos descriptores. Aquí también se realiza la
localización del objeto usando homografía, que es la proyección del objeto encontrado sobre la
secuencia de video. Cuando el algoritmo llega a estas etapas es debido a que el objeto se
encuentra presente en la secuencia de video actual, y así incrementando el contador de
obstrucción en 1 y regresando a la etapa inicial de captura de imagen para así empezar un ciclo
nuevo.
Adelantar el video en Ta segundos.
Esta etapa se activa cuando la etapa de valor mínimo indica que podría no estar el objeto presente
en el área de selección u obstruido por un tiempo considerable, en este caso se avanza la
secuencia de video en 10 cuadros que son aproximadamente 3.3 segundos a 30 cuadros por
segundo, además de esto se incrementa en 1 el contador fin de programa, que si este llega a 3 se
puede decir que se dieron las condiciones necesarias para indicar que el objeto no se encuentra
presente o, está obstruido por un tiempo considerable en el área de selección, luego de esto se
regresa a la etapa de capturar imagen y así iniciar el ciclo para confirmar si el objeto se encuentra
o no presente.
45
PROTOCOLO DE PRUEBAS
Para la realización de las pruebas se tomaron seis nuevos videos, dos de estos fueron con un flujo
de personas superior, dos videos con flujo de personas medio y los dos restantes con flujo de
personas bajo. Las características de los objetos que se tomaron para que el algoritmo detecte
como removidos u obstruidos varían entre objetos con textura, sin textura, con y sin forma
definida y con un color o con varios colores (Imagen 18).
Imagen 18. Muestra de Imágenes Tomadas para Pruebas.
Estos videos se ejecutan con los 2 algoritmos propuestos en este proyecto (anexo 1 y anexo 2) y
se les hacen variaciones a los parámetros que toman muestras de cada una de las imágenes (valor
minimo para el método de diferencia cuadrada normalizada, número de descriptores de la imagen
y valores de umbral Hessiano para el algoritmo de SURF [8]), de esta forma determinar por
experimentación cuál de estos parámetros obtiene los mejores resultados.
IMPLEMENTACIÓN DEL ALGORITMO DE DIFERENCIA CUADRADA
NORMALIZADA
Para el algoritmo de Diferencia Cuadrática Normalizada (anexo 1) se varía el parámetro del valor
mínimo que es el obtenido por el método de diferencia cuadrada normalizada. Este parámetro del
valor mínimo se varía 0% (valor de referencia obtenido de los parámetros de diseño), -10%, -
20%, +10% y +20%. Con estas cinco variaciones del parámetro de valor mínimo se ejecuta el
algoritmo de Diferencia Cuadrática Normalizada con los seis videos de prueba, dando un total de
30 muestras para posterior análisis. Un resumen se muestra en la siguiente tabla.
46
Tabla 3. Procedimiento de pruebas Diferencia Cuadrática Normalizada
Procedimiento de pruebas Diferencia Cuadrática
Normalizada
Valores mínimos Videos (x2)
0.30 (referencia)
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
0.33 (+10%)
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
0.36 (+20%)
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
0.27 (-10%)
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
0.24 (-20%)
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
IMPLEMENTACIÓN DEL ALGORITMO SURF [8]
Con el algoritmo SURF (anexo 2) se realizan cambios en la cantidad de descriptores de SURF
[8]. Estos pueden ser los descriptores básicos (64 elementos) o los descriptores extendidos (128
elementos), también se modificará el umbral del Hessiano cuyos valores se toman en 300 (valor
encontrado de la etapa de diseño), 400 y 500. Solo valores dentro de este umbral son tomados.
Todo lo anterior se ejecuta con el algoritmo SURF [8] y con los mismos 6 videos anteriormente
mencionados. Se muestra de manera más clara en la siguiente tabla.
De los resultados obtenidos de las pruebas realizadas con las 6 posibles variaciones de
parámetros sobre los videos de pruebas, se tomaron los parámetros con los mejores resultados (en
base a los mayores aciertos en la detección de eventos de remoción u obstrucción) como los
parámetros a ser usados en el algoritmo que une las técnicas de SURF [8] y FLANN [9].
Tabla 4. Procedimiento de pruebas SURF [8]
Procedimiento de pruebas SURF [8]
Descriptores Umbral del
Hessiano Videos (x2)
64 300 Flujo de personas Bajo.
Flujo de personas Medio.
47
Flujo de personas Alto.
128
(Referencia) 300 (Referencia)
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
64 400
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
128 400
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
64 500
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
128 500
Flujo de personas Bajo.
Flujo de personas Medio.
Flujo de personas Alto.
IMPLEMENTACIÓN EN LA BEAGLEBOARD-XM [3]
Con el fin de estimar el tiempo de procesamiento del algoritmo total, se ejecuta cada uno de los
algoritmos implementados durante un periodo de 2 minutos y se crea una serie de datos a partir
del tiempo de comparación de plantillas. Estos algoritmos también se modificaron ligeramente, es
decir, para el algoritmo de Diferencia Cuadrática Normalizada (anexo 1) se toma el parámetro del
valor mínimo que es uno de los resultados adquiridos de la comparación entre plantillas usando el
método de la diferencia cuadrada normalizada, este parámetro del valor mínimo se varía 0%
(valor de referencia obtenido de los parámetros de diseño), -10%, -20%, +10% y +20%. Estas 5
variaciones del parámetro de valor mínimo se ejecuta con un tiempo de video de 2 minutos cada
uno.
Con el algoritmo SURF [8] (anexo 2) se realizan cambios en la extracción de descriptores de
SURF [8], que pueden ser los descriptores básicos (64 elementos) o los descriptores extendidos
(128 elementos), con cada uno de estos dos tipos de descriptores, también se modificará el
umbral del Hessiano que como valor de referencia se toma 300, 400 y 500 valores de umbral.
Estas 6 variaciones de parámetros se ejecutan con un tiempo de video de 2 minutos cada uno.
48
ANÁLISIS DE RESULTADOS
Para el análisis de los datos obtenidos por los algoritmos implementados durante este proyecto se
realizaron las pruebas propuestas en el protocolo de pruebas del capítulo anterior, estas pruebas
se presentan en las siguientes tablas y se describen a continuación.
Los valores mínimos, muestra el parámetro del umbral que se modificó, este es uno de los
resultados obtenidos por el método de diferencia cuadradas normalizadas.
Los cuadros totales son el número total de cuadros que contiene el video de prueba.
Los aciertos son el número de eventos acertados por el algoritmo, en estos se encuentran los
eventos de objeto removido y obstrucción.
Los falsos positivos son los eventos detectados por el algoritmo, que no están en el video.
Los falsos negativos son los eventos que no detectó el algoritmo como aciertos, pero sí están en
el video.
Los totales generales es el número de eventos encontrados por el algoritmo
Tabla 5. Análisis de resultados en el algoritmo de Diferencia Cuadrática Normalizada
Algoritmo de Diferencia Cuadrática Normalizada
Valores
Mínimos
Video
de
prueba
Cuadros
totales Aciertos
Falsos
positivos
Falsos
Negativos
Totales
Generales
0.24
1 18060 8 11 0 19
2 18000 1 0 0 1
3 18120 1 1 0 2
4 9000 3 0 0 3
5 9060 2 0 0 2
6 90180 3 0 0 3
0.27
1 18060 10 7 0 17
2 18000 1 1 0 2
3 18120 2 0 0 2
4 9000 1 0 0 1
5 9060 1 1 0 2
6 90180 1 1 0 2
0.3
1 18060 10 8 0 18
2 18000 1 6 0 7
3 18120 2 0 0 2
49
4 9000 1 0 0 1
5 9060 1 0 0 1
6 90180 1 1 0 2
0.33
1 18060 10 7 0 17
2 18000 1 4 0 5
3 18120 1 2 0 3
4 9000 1 1 0 2
5 9060 1 0 0 1
6 90180 1 1 0 2
0.36
1 18060 8 1 0 9
2 18000 1 8 0 9
3 18120 1 1 0 2
4 9000 1 1 0 2
5 9060 1 0 0 1
6 90180 1 0 0 1
Tabla 6. Análisis de resultados en el algoritmo SURF [8]
Algoritmo SURF [8]
Descriptores
y Umbral
Video
de
Diseño
Cuadros
Totales Aciertos
Falsos
positivos
Falsos
Negativos
Totales
Generales
64-500
1 18060 4 11 1 15
2 18000 1 1 1 2
3 18120 2 1 0 3
4 9000 1 0 2 1
5 9060 1 0 0 1
6 90180 1 0 0 1
128-500
1 18060 5 16 0 21
2 18000 2 0 0 2
3 18120 2 1 0 3
4 9000 1 0 0 1
5 9060 1 0 0 1
6 90180 1 0 2 1
64-400
1 18060 1 2 42 3
2 18000 0 0 0 0
3 18120 0 0 0 0
4 9000 1 0 0 1
5 9060 1 0 0 1
6 90180 1 0 0 1
128-400
1 18060 2 1 9 12
2 18000 0 0 0 0
3 18120 0 1 0 1
4 9000 1 0 0 1
5 9060 1 0 0 1
50
6 90180 1 0 0 1
64-300
1 18060 4 14 3 18
2 18000 0 0 0 0
3 18120 0 0 0 0
4 9000 1 0 0 1
5 9060 1 11 0 12
6 90180 1 0 0 1
128-300
1 18060 2 12 0 24
2 18000 0 0 0 0
3 18120 0 0 0 0
4 9000 1 0 0 1
5 9060 0 0 0 0
6 90180 1 0 0 1
PRUEBAS REALIZADAS CON EL ALGORITMO DE DIFERENCIAS CUADRADAS
NORMALIZADAS
Los anteriores datos (Tabla 5) nos sugieren que para el caso del algoritmo de Diferencia
Cuadrática Normalizada obtiene detecciones positivas, en varios casos el porcentaje de acierto es
del 100%, ya que la detección de falsos positivos y falsos negativos era de cero.
Con las pruebas del algoritmo, el parámetro con los valores mínimos establecidos en 0.24 es el
que mejores resultados entregó, ya que con este parámetro se identificaron al menos un acierto ya
sea obstrucción o remoción y también disminuyeron los eventos de falsos positivos y negativos.
PRUEBAS REALIZADAS CON EL ALGORITMO SURF [8].
Para el caso del algoritmo SURF [8] (Tabla 6) se obtuvieron diferencias con el algoritmo de
Diferencia Cuadrática Normalizada ya que hubo casos en que el algoritmo no detecto en ningún
momento la remoción de objetos ni la obstrucción total del objeto puesto en prueba, los
parámetros que mejor resultado obtuvieron fueron aquellos que tienen el umbral de 500 con
ambos tipos de descriptores ya sea 64 o 128. Lo que es de esperarse, ya que no se está haciendo
una correspondencia espacial de los puntos de la región de interés de la imagen de plantilla con la
región de interés de la imagen del cuadro de video. Esta prueba con el algoritmo SURF [8] es una
etapa preliminar del algoritmo completo que es el uso de SURF+FLANN. Solamente se están
encontrando 4 puntos con descriptores comunes, es por eso que se toman 4 puntos, ya que es el
mínimo necesario para que el algoritmo de FLANN [9] encuentre una homografía
correspondiente.
51
Con estos valores de umbral establecido en 500 y el número de descriptores en 128, se realizaron
las pruebas usando la homografía realizada con SURF+FLANN. Estas pruebas se presentan a
continuación.
PRUEBAS REALIZADAS CON DETECCIÓN DE CAMBIOS EN LA HOMOGRAFÍA.
Esta prueba se realizó con 3 videos utilizando los parámetros que mejor resultado entregaron en
cuanto a la detección por lo menos 4 descriptores útiles en la homografía, estos son, un umbral de
500 y 128 descriptores por punto. En la siguiente tabla se muestran los datos obtenidos por
experimentación y la descripción. Esta prueba involucró el análisis cuadro a cuadro del
algoritmo.
Los cuadros totales son el número total de cuadros que contiene el video de prueba.
Los objetos obstruidos son la cantidad de aciertos que tiene al momento que se obstruyó el
objeto.
Obstrucción parcial, son la cantidad de aciertos que tiene al momento que se obstruyó
parcialmente el objeto.
Objetos removidos, son la cantidad de aciertos que tiene al momento que se removió el objeto.
Los eventos totales es la suma entre objeto obstruido, obstrucción parcial y objetos removidos.
Tabla 7. Homografía en algoritmo SURF [8]
Algoritmo SURF [8], Homografía
Video Cuadros
Totales
Objeto
Obstruido
Obstrucción
Parcial
Objeto
Removido
Eventos
Totales
Flujo de
personas alto 8940 0 10 835 858
Flujo de
personas
medio
9060 10 5 375 400
Flujo de
personas bajo 8940 0 0 1484 1484
52
PRUEBAS REALIZADAS EN LA BEAGLEBOARD-XM
Se presentan a continuación las pruebas de tiempos de ejecución obtenidas por experimentación
de los dos algoritmos realizados en este proyecto, estas pruebas fueron realizadas en la tarjeta
BeagleBoard-xM [3] durante un tiempo de ejecución de aproximadamente 2 minutos, las
condiciones de las pruebas consistieron en observar un objeto y registrar el tiempo que demoraba
la tarjeta en realizar la ejecución del algoritmo por cada ciclo.
En las siguientes tablas se muestran los datos obtenidos realizando las variaciones mencionadas
en el protocolo de pruebas. Agregando el parámetro del área seleccionada por el usuario en
píxeles para cada una de las pruebas.
Tabla 8. Análisis de tiempos en BeagleBoard-xM con algoritmo de Diferencia Cuadrática Normalizada
Algoritmo Diferencia Cuadrática Normalizada
Valores
Mínimos
Área
(píxeles)2
Promedio
(ms)
Mínimo
(ms)
Máximo
(ms)
Mediana
(ms)
Desviación
estándar
0.24 5152 26.9187 24.9328 53.4057 26.4587 2.1924
0.27 4500 27.5122 25.3601 57.1594 26.8249 2.2912
0.3 4450 27.2406 25.3295 68.9597 26.6418 2.1975
0.33 4550 27.7611 25.3601 51.7883 27.1301 2.3494
0.36 4692 27.8992 25.5432 84.0759 27.0996 2.7388
Tabla 9. Análisis de tiempos en BeagleBoard-xM con algoritmo SURF [8].
Algoritmo SURF
Descriptores
y Umbral
Área
(pixeles)2
Promedio
(ms)
Mínimo
(ms)
Máximo
(ms)
Mediana
(ms)
Desviación
estándar
64-500 4500 103.0373 71.4721 210.7849 102.3712 11.2452
128-500 5264 158.9068 113.2507 230.7739 157.3791 16.1071
64-400 5580 151.7744 122.1008 217.4987 150.2380 13.8215
128-400 4732 155.6492 102.8747 602.9052 139.4805 50.7401
64-300 5035 126.8093 91.6748 187.6220 122.5891 11.5526
128-300 5076 152.2496 110.3820 418.3654 149.9938 22.3689
Los resultados de la ejecución de los algoritmos muestran un área seleccionada bastante similar
en todos los casos y de esta forma evitar que el área seleccionada por el usuario sea algo que
interfiera en la obtención de los tiempos, se puede apreciar que el algoritmo SURF [8] toma más
tiempo en ejecutarse que el algoritmo de comparación de plantillas por diferencia cuadrática
normalizada.
53
Los datos de la mediana, que es el valor medio del conjunto de datos ordenados de menor a
mayor. Tal como se observan en las tablas obtenidas, la mediana es aproximado al valor
promedio en la mayoría de los casos, esto nos sugiere que la ejecución de los algoritmos son
estables durante el tiempo establecido en el protocolo de pruebas.
La desviación estándar es la precisión de las medidas que indican el grado de dispersión de los
datos respecto al valor medio. Como se observa en los datos obtenidos, el algoritmo de SURF [8]
tiene un grado de dispersión mucho mayor al determinado por el método de diferencias
cuadráticas normalizadas. Esto hace que el algoritmo SURF [8] sea más inestable en tiempos, y
por esta razón sea menos predecible que la comparación de plantillas.
54
CONCLUSIONES
En este proyecto se realizó un estudio sobre los algoritmos de detección de objetos removidos
usando visión artificial, se decidió entonces por implementar un algoritmo que realiza método de
diferencias cuadradas y otro algoritmo que usa descriptores de la imagen para encontrar una
imagen de muestra sobre una imagen de base.
La razón de la elección de estos algoritmos de comparación es que el método de diferencias
cuadradas es una de las técnicas más conocidas y bien documentadas de comparación entre
imágenes.
El segundo algoritmo que usa descriptores se escogió por su robustez en la localización de
imágenes identificando la proyección que tiene la imagen de muestra sobre la imagen de base
usando el método de FLANN, este algoritmo por ser más robusto que el método de diferencias
cuadradas, usa muchas más operaciones y por ende usa más recursos en la ejecución sobre la
BeagleBoard-xM.
Durante el periodo de experimentación se pudo determinar que el establecimiento de los
parámetros (valor de umbral en 500 y numero de descriptores en 128) en el algoritmo SURF
utilizando el método de FLANN arrojaba un comportamiento más favorable, por que identificaba
plenamente los eventos que se encontraban en los videos de prueba, tales como obstrucción
parcial, obstrucción total y remoción del objeto.
El algoritmo de SURF no reconoce claramente cuando en la imagen seleccionada contiene bordes
debido a que el algoritmo no se diseñó para reconocerlos, sin embargo el algoritmo es capaz de
identificar descriptores dentro de la imagen seleccionada. Caso contrario al algoritmo de
diferencias cuadradas que no utiliza descriptores ni tampoco reconoce el fondo ni el borde del
objeto seleccionado por el usuario, pero la diferencia cuadrada normalizada entre las imágenes es
el método para reconocer que el objeto no se encuentra presente.
El algoritmo de SURF presenta mayores fallas cuando el objeto que se está supervisando no
presenta una textura o bordes suficientes para extraer puntos con sus respectivos descriptores. En
ambos algoritmos, (SURF + FLANN y diferencia cuadrática), la detección de remoción funciona
mejor si mientras mayor sea la diferencia entre el objeto y el fondo de la escena.
55
Para el algoritmo de diferencia cuadrática normalizada el parámetro del valor mínimo, se variaba
dando como resultado un algoritmo que en todos los casos probados reconoce al menos una
imagen que corresponde a la remoción del objeto, el parámetro de valor mínimo en la diferencia
que resultó ser el mejor de todos es el de 0.24, que se encuentra dentro del rango de valores
entregados por el método de comparación que va desde 0 hasta 0.5. El parámetro que tiene un
mejor comportamiento en la experimentación fue el de 0.24, que es aproximadamente la mitad de
los valores máximo y mínimo.
Las pruebas realizadas por el algoritmo de SURF utilizando el método de FLANN junto con el
establecimiento de los parámetros del umbral Hessiano en 500 y el número de descriptores en
128, dio como resultado que la cantidad de aciertos que tuvo este método fue ampliamente mayor
a las realizadas por el algoritmo de Diferencia Cuadrada Normalizada, la diferencia radica en la
implementación de los algoritmos de SURF y FLANN, estos algoritmos cuentan con una mayor
cantidad de información analizada, y son más robustos, pero esto también implica más tiempo de
proceso.
El algoritmo de SURF utilizando el método de FLANN es, entre los algoritmos analizados el que
mejor se adapta a los requerimientos de ejecución en secuencias de video en tiempo real y se
recomienda para su uso y aplicación en sistemas de video seguridad para reconocimiento de
objetos removidos, ya que presenta una mejor detección de los eventos analizados.
En la implementación de los algoritmos propuestos en la tarjeta de desarrollo se probó que no es
necesario una tasa de procesamiento mayor a 5 cuadros por segundo que fue la mínima tasa
registrada por el algoritmo más lento (SURF utilizando el método de FLANN), para encontrar un
objeto removido en una escena con las características descritas en entre trabajo.
56
TRABAJO FUTURO Y RECOMENDACIONES.
La detección de objetos removidos sigue siendo un reto por encontrar el algoritmo ideal que
indique en qué momento se obstruye parcial o totalmente un objeto, y desde luego cuando es
removido, este proyecto se acerca un poco más a esa meta, por esta razón al desarrollo de
algoritmos falta mucho por desarrollar para así evitar la detección de falsos positivos que son
detectados por el algoritmo.
Un algoritmo que es ideal para partir de ahí para futuras aplicaciones es el de SURF empleando
FLANN para la detección y localización robusta de objetos, este proyecto lo usó pero por razones
de tiempo no se pudo profundizar más en el desarrollo y correcciones de este método para la
finalidad del trabajo.
Otro caso para mejorar este tipo de algoritmos es el uso de métodos para localizar el objeto sin
necesidad de utilizar áreas de selección elegidas por el usuario, y de esta forma automatizar un
poco más el algoritmo aquí realizado, desde luego sin perder la robustez y la agilidad que se le
dio en este proyecto.
57
ANEXO 1
Algoritmo de Diferencias cuadradas normalizadas. Ver DVD-ROM.
ANEXO 2
Algoritmo de SURF. Ver DVD-ROM.
ANEXO 3
Imágenes obtenidas por la ejecución del algoritmo de diferencias cuadradas normalizadas. Ver
DVD-ROM.
ANEXO 4
Imágenes obtenidas por la ejecución del algoritmo de SURF. Ver DVD-ROM.
ANEXO 5
Imágenes obtenidas por la ejecución del algoritmo de SURF+ FLANN. Ver DVD-ROM
ANEXO 6
Tablas de tiempos ejecutados por la BeagleBoard-xM para el algoritmo de Diferencias Cuadradas
Normalizadas. Ver DVD-ROM.
ANEXO 7
Tablas de tiempos ejecutados por la BeagleBoard-xM para el algoritmo SURF. Ver DVD-ROM.
ANEXO 8
Videos de diseño. Ver DVD-ROM.
ANEXO 9
Videos de pruebas. Ver DVD-ROM.
58
BIBLIOGRAFÍA
[1] U.S. Department of Justice, The Appropriate and Effective Use of Security Technologies in
U.S. Schools. Washington D.C.: Sandia National Laboratories, 1999.
[2] Gary Bradsky and Adrian Kaheler, Learning OpenCV, computer vision with the OpenCV
library. United States: O'REILLY, 2008.
[3] BeagleBoard.org, BeagleBoard-xM System Reference Manual. Richardson, TX, United
States, 2010.
[4] Texas Instruments, DM3730 Digital Media Processors, 2011, DM3730 Processor
Datasheet.
[5] Texas Instruments. (2011, Febrero) OMAP Applications Processors: OMAP 3 Processors.
[Online].
http://focus.ti.com/general/docs/wtbu/wtbuproductcontent.tsp?templateId=6123&navigatio
nId=11989&contentId=4682
[6] Angstrom. (2011, Marzo) The Angstrom Distribution. [Online]. http://www.angstrom-
distribution.org/
[7] Inc. Sony Latin America. (2011) PlayStation (R) Move Cámara- Entretenimiento en casa-
Sony Colombia. [Online].
http://www.sony.com.co/corporate/CO/productos/Entretenimiento-en-Casa/Blu-
ray/PlayStation_R_3/PlayStation_R_-Move/PLAYSTATIONEYE.html
[8] Herbert Bay, Andreas Ess, Tinne Tuytelaars, and Luc Van Gool, "Speeded-Up Robust
Features (SURF)," ETH Zurich, Katholieke Universiteit Leuven Belgium, Zurich, 2008.
[9] Marius Muja and David Lowe, "FLANN - Fast Library for Approximate Nearest
Neighbors," International Conference on Computer Vision Theory and Applications
(VISAPP'09), Febrero 2009.
59
[10] J. H., Bentley, J. L., Finkel, R. A. Freidman, "An Algorithm for Finding Best Matches in
Logarithmic Expected Time," ACM. Trans Math Softw., vol. 3, pp. 209-226, 1977.
[11] C., Hartley R. Silpa-Anan, "Optimized KD-trees for Fast Image Descriptor Matching,"
CVPR, 2008.
[12] David G Lowe, "Object RecognitionFrom Local-scale Invariant Features," Computer
Vision, 1999. The Proceedings of the Seventh IEEE International Conference on , vol. II,
no. ISBN 0-7695-0164-8 , pp. 1150-1157, Septiembre 1999.
[13] G., Brown, M., and Szeliski, R. Schindler, "Cityscale location recognition.," CVPR, pp. 1-
7, 2007.
[14] Carolina Pinzón Flórez, "Seguimiento de Objetos Móviles Usando una Cámara PTZ,"
Pontificia Universidad Javeriana, Facultad de Ingeniería, Departamento de Electrónica,
Bogotá D.C., Tesis de Grado 2010.
[15] IBM. Research, PeopleVision, real time alerts. [Online].
http://www.research.ibm.com/peoplevision/realtimealarts.html
[16] Ubuntu. (2011, Febrero) Maverick Meerkat Ubuntu. [Online].
https://wiki.ubuntu.com/MaverickMeerkat
[17] Richard M. Stallman, Using the GNU Compiler Collection. Boston, MA., United States:
GNU Press, 2010.