Embed Size (px)
Citation preview
Reconocimiento de Imágenes mediante Scale Invariant Feature
Transformation (SIFT)
Ing. Herigert Marilina, Bouchet Nahuel, Pianetti Iván
UTN – Facultad Regional Concepción del Uruguay
Abstract
En este trabajo de investigación desarrollamos un
Software en Java con Base de Datos en PostgreSQL,
para realizar el reconocimiento de objetos que se
pueden encontrar en diferentes imágenes, la búsqueda
de coincidencias entre los objetos a reconocer se da
sin importar las variantes que el mismo pueda llegar a
tener, ya sea por rotación, tamaño así como también
problemas de iluminación.
Para realizar este reconocimiento nos basamos en el
algoritmo SIFT (Scale Invariant Feature
Transformation), el cual se encarga de extraer
características distintivas de las imágenes en escala
de grises, es decir que puede ser utilizado para
reconocer la misma característica entre diferentes
vistas de un mismo objeto o escenas. Este algoritmo
fue trasladado a un software donde los usuarios
pueden realizar la búsqueda de las imágenes mediante
una simple interfaz para poder comprobar las tareas
que realiza el método al momento de encontrar dichos
puntos característicos y a su vez realizar la búsqueda
de coincidencias de los objetos en dos imágenes
diferentes.
Además en este informe se describe cuales serán las
tareas a realizar por el grupo para lograr aplicar en
este Software bases de datos de imágenes y distintos
mecanismos para poder realizar el reconocimiento en
tiempo real mediante cámara web.
Palabras Clave
Keypoints, Matches, Scale-Space, Best Bin First, kd-
tree
1. Introducción
Para lograr detectar objetos en una imagen, en
primer lugar es necesario encontrar los puntos clave o
de interés que identifiquen de una manera unívoca a
cada uno de los objetos de manera de poder
encontrarlos nuevamente si estos aparecen en cualquier
otra escena. Muchas metodologías se han ido
desarrollando desde el año 1981 con el trabajo de
Moravec [4], quien fue el primero en desarrollar
algoritmos de búsqueda de vértices en imágenes, con el
fin de hacer coincidir imágenes obtenidas desde
distintos ángulos. El trabajo de Moravec fue años más
tarde mejorado por Harris y Stephens (1988) [5],
creando el detector de esquinas de Harris, muy
utilizado para estos ámbitos, que no sólo busca
esquinas como dice su nombre, sino que además busca
cualquier punto dentro de la imagen con altos
gradientes en todas direcciones. Pero para detectar los
puntos de interés de una imagen, líneas rectas no sirven
debido a que los puntos en ellas son muy parecidos a
sus vecinos. Por este motivo no son aptas para una
buena descripción de las características que contiene
una imagen. Además, el detector de Harris no es
invariante para cambios de escala, que pueden ocurrir
en una cantidad muy grande de imágenes reales
tomadas con una cámara desde distancias diferentes.
Para mejorar este problema, Lowe [1] encontró en
2003 un nuevo algoritmo denominado SIFT, que
revolucionó el mundo del procesamiento de imágenes.
Su idea principal es la transformación de la imagen a
una representación compuesta de “puntos de interés”.
Esos puntos contienen la información característica de
la imagen que luego son usados para la detección de
muestras. El algoritmo se realiza mediante 4 pasos:
1- Construcción de Pirámides de Scale-Space: Se
representa la imagen en diferentes escalas y tamaños.
Se lleva a cabo de manera eficiente mediante el uso de
la función de diferencia gaussiana, para identificar los
posibles puntos de interés que son invariables a escala
y orientación.
2- Localización de puntos clave: Se buscan aquellos
puntos que se mantienen en cuanto a cambios de
escala, para ello se debe estudiar cada píxel y realizar
una comparación con los pixeles vecinos. Los puntos
clave son seleccionados en base a las medidas de su
estabilidad.
3- Asignación de orientación: en este paso se asigna a
cada punto clave una dirección de acuerdo a las
direcciones del gradiente y a la zona que rodea dicho
punto.
4- Descriptor de Puntos clave: consiste en calcular un
descriptor para la región de la imagen local que sea
fácilmente identificable, sin embargo tan invariable
como sea posible a las variaciones restantes, tales como
el cambio en la iluminación o el punto de vista 3D.
En este trabajo se ha desarrollado este método
mediante un Software en Java, que es la continuación
de una investigación y desarrollo que comenzó a
realizarse en la Technische Universität Ilmenau
Alemania en el grupo de investigación del
Departamento de “Neuroinformatik” [9], el cual se
pudo llevar a cabo durante una beca por 6 meses que la
Señorita Marilina Herigert, obtuvo en 2009. Esta
primera parte se basa en la demostración del
funcionamiento del método SIFT, sin la utilización de
bases de datos para archivar las características propias
de las imágenes para luego poder compararlas y
realizar el reconocimiento con una nueva imagen
ingresada y sin contar con la utilización de cámara web
para realizar este reconocimiento en tiempo real. Estas
tareas se están llevando a cabo en el grupo de
investigación Geinar de la Facultad Regional
Concepción del Uruguay.
2. Elementos del Trabajo y Metodología
Como ya se dijo anteriormente la metodología que
se ha utilizado para llevar a cabo este trabajo y en la
cual se basa el software desarrollado es el algoritmo
SIFT, consta de 4 pasos, que se describirán con mayor
detalle a continuación:
• Construcción de Pirámides de Scale-Space y
Detección de los extremos locales:
Para la detección de extremos locales se debe
trabajar con la imagen original filtrada. El trabajo de
Koenderink (1984) [13] y Lindeberg (1994) [7]
encontró que el único filtro apropiado para estos
efectos son los filtros Gaussianos de low pass. Se
utiliza este tipo de filtros debido a que la función
Gaussiana es invariante a escala en el espacio (Figura
1), para la detección de puntos de interés. Además,
elimina el ruido de la imagen. La imagen con la que se
trabaja es la convolución entre la imagen original y el
filtro Gaussiano. Si llamamos la imagen original I(x, y)
y al filtro G(x, y, σ), entonces la imagen con la que se
trabaja es L(x, y, σ) que resulta de la convolución entre
ambas, es decir:
( ) ( ) ( )yxIyxGyxL ,*,,,, σσ = (1)
( )
+−=
2
22
2*
2
1,,
σπσσ
yxyxG (2)
Adicionalmente, el trabajo de Lowe [1] propuso la
utilización para el filtrado de la diferencia de dos filtros
Gaussianos, con distinta desviación estándar cuya
diferencia es un factor k.
( ) ( ) ( )σσσ ,,,,,, yxGkyxGyxD −= (3)
( ) ( ) ( )yxIyxDyxL ,*,,,, σσ = (4)
Figura 1: Imagen en diferentes escalas. Fuente:[6].
Otra manera de trabajar estas imágenes es utilizando
el Laplaciano de funciones Gaussianas, sin embargo la
utilización de ésto es lenta y la diferencia de
Gaussianas es una aproximación bastante eficiente para
nuestros fines. El Laplaciano tiene la formula siguiente
con G como se ha definido anteriormente.
∂
∂+
∂
∂=∆=
2
2
2
222 *
y
G
x
GGM σσ (5)
Figura 2: Aquí se puede observar como se diferencia
la función Laplaciana de la diferencia Gaussiana
(DOG). Fuente:[3].
En la figura 2 mostramos las dos alternativas.
Además de la similitud podemos ver, qué impacto en la
imagen tiene la convolución con este filtro. La
transformada de Fourier de las funciones tiene la
misma forma, porque son funciones Gaussianas.
Entonces, podemos interpretar la figura 2 también
como la respuesta al impulso del dominio del espectro.
En una imagen real, las frecuencias que contienen la
información característica son las medias. El ruido
digital está en las frecuencias altas, que está en cada
imagen digital. Por otro lado, las frecuencias bajas,
contienen variaciones suaves por lo que no son
relevantes para la obtención de los puntos de interés.
Como se puede ver fácilmente, la aproximación del
las dos fórmulas sigue de los cálculos siguientes
usando la definición de la derivada:
( ) ( )( )1
,,,,*
−
−≈
∂
∂=∆
k
yxGkyxGGG
σ
σσ
σσ (6)
( ) ( )
( ) Gk
yxGkyxG
∆−≈
≈−⇒
**1
,,,,
2σ
σσ (7)
La convolución con la DoG (Diferencia Gaussiana)
se hace para toda la imagen y con escalas diferentes,
para detectar estructuras en todos los lugares y con
todos los tamaños. Para una implementación rápida, el
algoritmo trabaja cada octava en forma individual
(Figura 3). Investigaciones de Lowe dieron que para
cada octava un número de 3 escalas y un sigma de 1.6
eran los valores óptimos. Por eso, primero se hace la
convolución con 3 escalas de las Gaussianas, y luego
para obtener la DoG se hace con la resta de imágenes
vecinas como se puede observar en la Figura 4 donde
se ve el resultado que se obtiene tratando imágenes
reales. Para la octava siguiente, solamente hay un
nuevo muestreo con un factor 2 y la repetición de la
resta. Con este método se crean muchas imágenes
filtradas con valores extremos donde el tamaño y el
lugar de la DoG es similar a la estructura dentro de la
imagen.
Figura 3: Por cada Octava en diferentes escalas se
aplica una Diferencia Gaussiana.
Figura 4: Como se ve reflejado la DoG en imágenes
reales.
Para buscar los extremos en las imágenes
convolucionadas, cada píxel es comparado con todos
sus píxeles vecinos, ambos en el dominio del espacio y
en del dominio de la escala. Solo si todos tienen un
valor distinto, este lugar va a pasar el examen. La
Figura 5 indica este procedimiento.
Figura 5: Cada píxel de la imagen es comparado con
su píxel vecino en la Pirámide de DOG.
• Localización de puntos clave:
Entre los puntos que sobrevivieron el examen de la
búsqueda de extremos hay muchos que caracterizan
puntos con poco contraste. Ellos no son estables si por
ejemplo la iluminación cambia muy poco y producen
ruido. Para quitarlos se examina primero si el máximo
o mínimo está en un lugar entre esos píxeles, para
estimar la función D con una serie de Taylor de
grado 2.
( ) xx
Dxx
x
DDxD
2
2
2
1
∂
∂+
∂
∂+= Τ
Τ
(8)
Después de la derivación de esta aproximación e
igualando a cero queda:
x
D
x
Dx
∂
∂
∂
∂−=
−
*ˆ2
12
(9)
( ) xx
DDxD ˆ*
2
1ˆ
∂
∂+=⇒
Τ
(10)
Si el valor de D(x^) es menor a 0.03, el punto es
eliminado, suponiendo que D tiene valores de 0 a 1.
Además de quitar aquellos puntos con poco contraste,
hay que encontrar y descartar candidatos que vienen de
una línea recta y no de una esquina. Si hay una línea
recta, la curvatura de D va a ser grande en una
dirección pero pequeña en la que es perpendicular. Este
factor corresponde a un valor propio α grande y un β
más pequeño de la matriz Hessiana. Con el
conocimiento de:
( ) βα +=∂
∂+
∂
∂=
2
2
2
2
y
D
x
DHTraza (11)
( ) βαβα ry
D
x
DHDet ==
∂
∂
∂
∂= ,**
2
2
2
2
(12)
Para un r predefinido hay que examinar si se cumple
la inecuación dada por:
( )( )
( )r
r
HDet
HTraza22
1+< (13)
Lowe propone en [1] un umbral de r = 10.
• Asignación de orientación:
En este paso se asigna una dirección a cada punto de
interés, que dependerá de las muestras de los puntos
que el mismo posee en su entorno.
Para tener un buen descriptor, la localización y la
función local de aproximación que tenemos hasta ahora
no son suficientes. Hay también que examinar el valor
del gradiente y su orientación. El valor corresponde a
la escala de la Gaussiana y mediante ese tratamiento la
descripción del punto de interés es invariante con
respecto a la escala. Además con el conocimiento de la
orientación, la caracterización es independiente con
respecto a la dirección. En un espacio vectorial de
Euclides, se calcula el valor de la Longitud del
Gradiente m(x, y) y su Orientación Θ(x, y) de una
función discreta como:
( ) ( ) ( )22, yx LLyxm ∆+∆= (14)
( ) ( )( )
( ) ( )( )2
2
11
11
−−+
+−−+=
xyLxyL
yxLyxL (15)
( )
∆
∆=Θ −
x
y
L
Lyx
1tan, (16)
( ) ( )( ) ( )
−−+
−−+= −
yxLyxL
yxLyxL
,1,1
1,1,tan 1
(17)
Para tener un conocimiento más general de la
orientación en un punto de interés, el algoritmo SIFT
examina también los valores m y Θ de los píxeles que
están en su entorno. Gracias al uso de una ventana
gaussiana, los valores de píxeles más lejanos tienen un
impacto más pequeño que píxeles cercanos. Con un
histograma de orientación con ventanas de 10 grados el
algoritmo trata de buscar la dirección verdadera usando
una interpolación de los 3 valores más grandes del
histograma. El histograma de orientación es formado
por la orientación del gradiente de los puntos
muestreados en la región del punto clave. Cada pico en
el histograma corresponde a la dirección dominante del
gradiente local (un pico con el 80% es usado para crear
el punto clave con su orientación). Sólo alrededor del
15% de los puntos se les asignan múltiples
orientaciones.
En la figura 6 se ve reflejado como presenta el
Software desarrollado los puntos claves con sus
respectivas direcciones, tambien se puede observar que
no importa la rotacion de la imagen, los puntos siguen
siendo identificados correctamente.
Figura 6: Imágenes obtenidsa del Software que indica
los puntos claves (Keypoints) y las orientaciones
correspondientes.
• Descriptor de Puntos clave:
Para tener una descripción que sea lo
adecuadamente invariante a cambios en un punto de
vista en el espacio, un tratamiento relacionado a la
función de las neuronas en la visión biológica es usado.
Debido a que es necesaria la independencia de
pequeñas translaciones del punto de interés, Edelman
et al. [8] propusieron en 1997 el algoritmo siguiente.
Gradiente de la Imagen. Descriptor de los Puntos de Interés
Figura 7: Usando una ventana gaussiana, los valores
m y Θ se examinan en la vecindad del punto de interés.
Después sigue un tratamiento con histogramas para 8
orientaciones distintas.
Una ventana gaussiana representada por el círculo
en la figura7, selecciona los valores de m y Θ
prefiriendo los que están más cerca del centro. Después
sigue una distribución en sectores más grandes y otra
vez el uso de un histograma con 8 distintas
orientaciones. La ventaja de esto es que los
histogramas quedan iguales, aún cuando el centro de la
ventana gaussiana se mueve hasta 4 píxeles. Esto hace
la descripción bastante robusta con respecto a las
translaciones por cambios de puntos de vista. La
figura7 muestra un ejemplo reducido a 2x2
histogramas. Según el algoritmo SIFT se tratará con
4x4 con 8 posibles direcciones correspondiente a un
vector de 4x4x8 = 128 dimensiones para cada punto de
interés.
3. Resultados obtenidos mediante la
utilización del Software
En nuestro Software realizamos la identificación de
objetos utilizando dos imágenes estáticas que se
encuentran en un ordenador y obteniendo diferentes
resultados para las pruebas realizadas, como se puede
observar en las Figuras 8 y 9, donde en la segunda el
Software permite modificar los parámetros estándares e
ingresar nuevos, teniendo de esta forma una
visualización eficiente de cómo varía la identificación
si cambiamos la escala, la dimensión de las imágenes,
sigma y el valor mínimo de octavas.
Figura 8: Coincidencias (Matches) obtenidos mediante
el Software, con los parámetros estándares para
obtener los puntos clave.
Figura 9: Resultados obtenidos con el Software
mediante la modificación de los parámetros
estándares del método SIFT
Nuestro propósito en este grupo de investigación es
poder realizar la comparación y/o identificación de las
imágenes mediante el uso de bases de datos y cámara
web para realizar este reconocimiento en tiempo real.
Lowe propone en su trabajo del año 1999 [2] varios
métodos para obtener Matches (coincidencias)
eficientes y rápidas. El desafío es buscar en la base de
datos si hay correspondencias, para realizar esto
primero debemos almacenar en ella los vectores
descriptores de las diferentes imágenes. El problema es
la gran cantidad de dimensiones del vector de
características (128 dimensiones), debido a la cantidad
de comparaciones que debe realizar. Para tratar de
optimizar esta búsqueda aplicaremos una variación del
algoritmo “Vecino más Cercano” (nearest-neighbour
algoritm), que se denomina Best Bin First, debido a
que las búsquedas realizadas con el primer algoritmo
no son eficientes cuando las dimensiones del vector es
mayor a 10. El método Best Bin First utiliza un árbol
binario balanceado kd-tree, en el cual realiza solo las
búsquedas en las ramas del árbol que son significativas.
4. Discusión
Al realizar pruebas con diferentes valores en los
parámetros, nos hemos dado cuenta como influye en el
método el número de escalas con las que se trabaja, así
como Lowe indico que el valor óptimo para el calculo
es de 3 escalas con un sigma de 1.6, nosotros podemos
hipotetizar que si la imagen posee una alta calidad, se
debería trabajar con un número mayor de escalas para
alcanzar la cantidad de keypoint indicados para obtener
buenos resultados y a su vez si la imagen se encuentra
con gran variedad de ruido (imagen con mucha nitidez)
un valor de 3 escalas, hace que la imagen se convierta
en la ultima escala en una ventana sin distinción de
cambios y esto hace que los puntos encontrados sean
mínimos haciendo que no se pueda obtener mucha
información de la misma.
Además otro parámetro importante al momento de
trabajar con este método es el radio con el que se
maneja la información alrededor de los puntos clave,
debido a que si este radio es muy grande se obtienen
pocos puntos en la imagen, y en el caso contrario se
encuentran demasiados puntos donde quizás algunos no
sean identificativos o necesarios al momento de
realizar el reconocimiento, por este motivo el rango en
que debe moverse el valor del radio según nuestro
análisis sería entre [6 ;9].
Para poder manejar estos valores y que sea mas
flexible para el usuario al momento de realizar las
tareas de reconocimiento, hemos permitido que a través
del software se puedan ingresar estos valores de
acuerdo a la imagen que se esta tratando.
5. Conclusión
En la actualidad, el procesamiento de imágenes esta
alcanzando un desempeño significativo. Pudiéndose
mencionar el desarrollo de investigaciones en el área
de la inteligencia artificial. Tal es el caso de
aplicaciones practicas abocadas a la extracción e
interpretación de información a partir de imágenes.
El presente trabajo de investigación tiene como
objetivo el desarrollo de un software inteligente que
sea capaz de reconocer una imagen en particular
dentro de un conjunto almacenado en una base de
datos. Para esto se utiliza el algoritmo SIFT.
El algoritmo SIFT es de especial interés ya que se
encarga de extraer características distintivas que
resultan ser claves al momento de reconocer dos
imágenes. El conjunto de dichas características son los
puntos de interés que son utilizados para reconocer
unívocamente a un objeto presente en dos imágenes
con diferentes perceptivas.
El software de este trabajo se encarga de recibir una
imagen de un objeto provista por el usuario y hallarlo,
con el mejor grado de certeza posible, en una base de
datos.
El grado de bondad del reconocimiento depende de
los parámetros del algoritmo SIFT, así como también
de las características propias de la imagen. Por esta
razón el software esta predefinido en los valores
óptimos, sin embargo el usuario final tendrá la opción
de modificar los parámetros para búsquedas
adicionales.
6. Referencias [1] Lowe, D.: Distinctive Image Features from Scale-
Invariant Keypoints, Computer Science Department,
University of British Columbia, Vancuver, B.C., Canada
(2003)
[2] Lowe, D.: Object Recognition from Local Scale-Invariant
Features, Computer Science Department, University of
British Columbia, Vancuver, B.C., Canada, (1999)
[3] Frolova et. al.: Local Invariant Features, Powerpoint
Presentation,
http://cmp.felk.cvut.cz/cmp/courses/DZO/2007_dzo_features
.ppt
[4] Moravec, H.: Rover visual obstacle aviodance,
Internactional Joint Conference in Artifial Intelligence,
Vancoucer, Canada (1981)
[5] Harris, C., Stephens, M.: A combined corner and edge
detector, Fourth Alvey Vision Conference, Manchester, UK,
pp. 147-151 (1998)
[6] Silvio Heuberger, Stefan Reinhard, Image Based
Information Search, ibis (2009).
[7] Lindeberg, T.: Scale-Space theory: A basic tool for
analysing structures at different scales, Journal of Applied
Statistics, 21(2):224-270 (1994)
[8] Edelman et al.: Complex cells and object recognition.
Unpublished manuscript:
http://kybele.psych.corrnell.edu/~edelman/archive.html
(1997)
[9] Technische Universität Ilmenau - Laboratorio
Neuroinformatics and Cognitive Robotics http://www.tu-
ilmenau.de/fakia/People.2193.0.html?&L=1
Agradecimientos Al profesor Jorge Nanclares de la Facultad Concepción
del Uruguay de la Universidad Tecnológica Nacional
por su apoyo en la comprensión de diferentes temas
específicos tratados en el proyecto.
Datos de Contacto
Ing, Marilina Herigert. Facultad Regional Concepción
del Uruguay – Universidad Tecnológica Nacional.
Mariano Moreno 659 - 3260 Concepción del Uruguay
(Entre Ríos).
Nahuel Bouchet. Facultad Regional Concepción del
Uruguay – Universidad Tecnológica Nacional. Delio
Paniza 1196 - 3260 Concepción del Uruguay (Entre
Ríos).
Iván Pianetti. Facultad Regional Concepción del
Uruguay – Universidad Tecnológica Nacional. Victor
Etcheverry 532 - 3260 Concepción del Uruguay (Entre
Ríos).
