CARACTERÍSTICAS DE NIVEL MEDIO

CAMPO DE APLICACIÓN

La presente invención se enfoca en una nueva tecnología de búsqueda de imágenes usando como consulta un dibujo confeccionado a mano (sketch). La presente invención se relaciona con un sistema que utiliza un método de representación de sketches mediante histogramas de orientaciones de gradientes calculados por celdas en las que un sketch es dividido. Los sketches caracterizan lo que los usuarios desean encontrar. Considerando que las imágenes regulares no siguen la naturaleza de un sketch, en la presente invención se propone una etapa para obtener un sketch a partir de una imagen regular. Para este fin se propone utilizar características de nivel-medio que son obtenidas mediante algoritmos de aprendizaje de máquina. El sistema propuesto puede ser aplicado en diversos contextos en los que es factible definir como consulta un dibujo hecho a mano (sketch). Por ejemplo: búsqueda de productos en catálogos, búsqueda de fotos en la web, búsqueda de piezas en para manufactura, búsqueda de patrones en estructuras biológicas, etc.

ANTECEDENTES DE LA INVENCIÓN

En los últimos años, la búsqueda o recuperación de imágenes se ha convertido en una de las áreas más relevantes en Ciencias de la Computación debido, principalmente, a los avances con respecto a la tecnología de captura y almacenamiento de imágenes así como al uso masivo de redes sociales que fomentan el intercambio de contenido visual. En este sentido, cada vez se hace más necesario contar con mecanismos capaces de administrar y organizar automáticamente el contenido visual que los usuarios puedan almacenar. Por ejemplo, es de gran interés contar con métodos automáticos que puedan agrupar imágenes por similitud, buscar imágenes similares a una de referencia, reconocer objetos que hay en las imágenes o, en general, interpretar de algún modo imágenes en una pluralidad de colecciones.

La recuperación automática de imágenes es uno de los problemas que se ha venido estudiando desde hace algunas décadas. El objetivo es recuperar un conjunto de imágenes relevantes desde una o más colecciones con respecto a un criterio de búsqueda determinado. Estas colecciones pueden contener miles, millones o billones de imágenes. Tradicionalmente, la búsqueda por imágenes se ha basado en comparar descripciones textuales previamente asignadas. Sin embargo, describir textualmente una imagen es poco práctico. Además, tales descripciones pueden reducir la riqueza descriptiva que una imagen pueda contener por sí misma. Por este motivo, los esfuerzos durante la última década han estado enfocados en explotar el propio contenido de las imágenes a través de lo que se conoce como Búsqueda de Imágenes por Contenido (CBIR por sus siglas en inglés), cuyo objetivo es desarrollar métodos eficientes que, aprovechando completamente el contenido visual de las imágenes (e.g. patrones de color, textura, forma), produzcan mayor efectividad en el proceso de búsqueda por similitud.

Un método clásico para realizar búsquedas de imágenes por contenido debe recibir como entrada una imagen regular (e.g. una foto), que represente lo que uno desea encontrar. Sin embargo, en muchos casos uno no dispone de una imagen de ejemplo para realizar una búsqueda. De hecho, alguien puede querer realizar una búsqueda de imágenes porque justamente no cuenta con la imagen que desea. Para esquematizar el caso en que una imagen de ejemplo estaría ausente presentamos el siguiente escenario: Supongamos que estamos en un contexto de búsqueda de productos por imágenes; alguien puede estar interesado en comprar una pieza de arte con alguna forma especial; tal persona puede tener en mente lo que quisiera encontrar pero no tiene alguna imagen que represente su intención de búsqueda; aquí, las modalidades de búsqueda que hemos venido discutiendo no son aplicables.

Una alternativa para realizar consultas en un sistema de recuperación de imágenes es dibujando lo que deseamos encontrar. Un dibujo es un medio intuitivo y natural de comunicación entre los seres humanos, que puede proveer suficiente información acerca nuestra intención de búsqueda. De hecho, los dibujos fueron una de las primeras formas de comunicación entre humanos. Un dibujo puede ser muy detallado o muy simple; incluso, un dibujo puede representar color y textura. Sin embargo, un dibujo detallado que contenga color y textura demanda tiempo adicional que puede hacer la búsqueda impráctica. Además, un dibujo detallado requiere ciertas habilidades que no todo usuario posee. En este sentido, definiremos como "dibujo de consulta" o sketch a un dibujo hecho a mano basado en simples trazos, con poca o nula información de color y textura. El objetivo de tratar con este tipo de dibujo, es que pueda ser realizado por cualquier persona rápidamente, sin requerir habilidades especiales. Este tipo de búsqueda es conocido como Búsqueda de Imágenes basada en Sketches (SBIR por sus siglas en inglés). Para mantener coherencia con el uso técnico en esta área, de aquí en adelante, usaremos el término sketch para referirnos al dibujos definido anteriormente.

A diferencia de la búsqueda de imágenes por contenido, el número de trabajos de investigación orientados a la recuperación de imágenes por sketches es mucho menor. Sin embargo, en los últimos cinco años este número se ha visto incrementado. Ejemplos de la proliferación de investigación en el área se plasman en los trabajos de Mathias Eitz usando SIFT descriptors y Bag of Features; Rui Hu con una propuesta basada en HOG y José Saavedra usando Keyshapes e Histogramas de Orientaciones Locales.

Considerando que un sketch es un dibujo basado en trazos, una de sus características más relevantes es la orientación del trazo. La orientación es una característica de las imágenes que ha sido explotada ampliamente en la comunidad de visión por computador, que ha mostrado resultados sobresalientes en tareas de reconocimiento y caracterización de objetos. En el caso de la búsqueda por sketches esta característica también ha sido explotada por Rui Hu, a través del método HOG (Histogram of Oriented Gradients), y José Saavedra, mediante el cálculo de un histograma de orientaciones locales (HELO).

Aunque se han propuesto métodos novedosos en el área, los resultados aún muestran bajo desempeño. Por esa razón, sistemas de búsqueda de imágenes por sketches basados en métodos más efectivos son requeridos. Por lo tanto, la presente innovación divulga un sistema de búsqueda de imágenes o fotos que utiliza un nuevo método que comprende las siguientes características.

• Estimación de gradientes por celdas.

• Estimación de histogramas por bloques.

• Estimación de gradientes e histogramas de orientaciones mediante interpolación.

• Votación de gradientes en forma ponderada con respecto a su magnitud.

• Conversión de una imagen a una forma de sketch mediante operaciones de nivel medio. Las técnicas tradicionales, usan operaciones de bajo nivel (e.g. Canny).

• Normalización del histograma mediante normalización potencia (pow normalizatioh).

PROBLEMA TÉCNICO

Los métodos clásicos en el campo de recuperación de imágenes por sketches se basan en construir vectores de características en forma de histogramas que representan la distribución de puntos u orientaciones de los trazos que componen un sketch. Algunas otras aproximaciones se basan en contornos activos, pero no han demostrado alta efectividad en grandes colecciones. Otra alternativa, pero más costosa aún, es convertir un sketch a una imagen regular y luego proseguir con una clásica búsqueda por contenido. Lamentablemente, las tareas involucradas en este método representan costo computacional adicional que lo hace impráctico para búsquedas en tiempo real.

Otros métodos extraen características locales como SIFT, SURF, HOG o algunas variaciones de SIFT, que luego son agregados usando la metodología Bag of Features (BoF). Ejemplo de estos métodos son los propuestos por Eitz, basados en características SIFT y variaciones de Shape Context, así como el método de Rui Hu, basado en características HOG. Aunque estos métodos han mostrado avances en el área de recuperación de imágenes por sketches, aún mantienen una efectividad baja que los hacen poco prácticos en ambientes reales.

Es también importante mencionar el documento US20120054177 que divulga un método de representación y búsqueda de sketches. Este método se basa en detectar "salient curves" tanto en la consulta como en las imágenes de la base de datos. La similitud entre una sketch y una imagen se basa en medir la similitud entre "salient curves" mediante una variación de la distancia de Chamfer que usa información de posición y orientación de los puntos de las curvas. Esta propuesta es completamente diferente a la nuestra ya que nuestra innovación se basa en calcular gradientes representativos por celdas utilizando técnicas de interpolación y representación de contornos de las fotos con las que un sketch debe ser comparado.

El bajo rendimiento mostrado por los métodos clásicos se puede deber a que estos métodos están basados en representaciones que explotan la riqueza de información que otorgan las imágenes, descuidando la naturaleza de los sketches. Los sketches son representaciones dispersas carentes de color y, en muchos casos, también de textura, que distan ampliamente de la naturaleza de una imagen regular. Por ejemplo, HOG se compone de una gran cantidad de vectores de orientaciones calculados sobre cada uno de los puntos de la imagen. Sin embargo, considerando que un sketch es disperso, el vector HOG puede contener muchos valores nulos que puede afectar negativamente el desempeño de los métodos.

Para afrontar los problemas anteriores, Saavedra propuso un método que construye un histograma de orientaciones de gradientes representativos en una localidad (HELO por sus siglas en inglés). Así, un gradiente no representa a un solo punto de la imagen sino a un conjunto de ellos en cierta localidad. La propuesta de Saavedra, aunque logra mejorar los métodos clásicos, aún presenta una baja efectividad. Sin embargo, un punto fuerte con esta propuesta es que deja de representar gradientes por punto y aprovecha el hecho de que los sketches comparten gradientes similares en una zona para centrarse en la representación de gradientes locales.

Otro aspecto relevante que afecta la efectividad de un método es que se comparan sketches contra imágenes regulares, que son representaciones de naturaleza diferente. Un sketch es un dibujo hecho a mano que no tiene riqueza visual como color o textura, mientras que una imagen regular es una fuente rica de información en donde el color o la textura pueden ser características altamente discriminativas. Este hecho, además, sienta un gran desafío por conseguir alta efectividad a partir de reducida información que los sketches proveen.

Para resolver el problema anterior, un sistema de búsqueda por sketches intenta convertir una imagen regular en una representación tipo sketch. Para este fin, los métodos existentes se basan en obtener una imagen de bordes o contornos de la imágenes mediante métodos que detectan variaciones de intensidad en la imágen. Estos métodos son conocidos como métodos de bajo nivel y, frecuentemente, otorgan imágenes de contornos ruidosas, ya que al estar basados en medir diferencias de intensidades, cualquier cambio de intensidad, posiblemente causada por pequeñas distorsiones en la imagen, puede causar la aparición de un punto de borde erróneo. Consecuentemente, comparar un sketch contra contornos ruidosos produce una degradación en la efectividad de un método.

SOLUCIÓN TÉCNICA

La presente invención se relaciona con un sistema para realizar búsquedas de imágenes mediante un dibujo hecho a mano (sketch). El sistema propuesto se basa en un método que calcula gradientes que representan a un conjunto de puntos agrupados en celdas, en lugar de representar solamente un punto en la imagen. A diferencia de HELO que también calcula gradientes locales, aquí se propone usar interpolación tanto para el cálculo de gradientes como para el cálculo de los histogramas. Además, la presente innovación propone nuevas etapas con el objetivo de aumentar la efectividad en recuperación de imágenes. La innovación propuesta puede ser aplicada en diversos contextos como la búsqueda de productos en catálogos o la recuperación de contenido visual en la web.

Una imagen regular o un sketch se compone de RxC puntos dispuestos en forma matricial. Así, una imagen consta de F¡ filas y C columnas. En el caso de información de color, cada punto tiene asociado una terna (R,G,B) que representa la intensidad de color en tres canales Rojo (R), Verde (G) y Azul (B). El rango de variación de cada canal depende de diferentes contextos. Una implementación usa el esquema tradicional, en el que el rango en cada canal varía de 0 a 255; así el valor de cada canal puede ser representado por 1 Byte y cada pixel contendrá 3 Bytes. Una imagen en escala de grises representa cada uno de sus puntos solamente por 1 Byte, siendo 0 el color negro (mínima intensidad) y 255 el color blanco (máxima intensidad).

VENTAJAS TÉCNICAS

La presente invención permite realizar búsquedas de imágenes sin la necesidad de contar con una imagen de ejemplo, requerida en los clásicos sistemas de búsqueda de imágenes por contenido. En contraste, aquí se propone un sistema basado en un método que permite a un usuario buscar imágenes a través de un dibujo (sketch). Así, con simplemente dibujar lo que el usuario desea desea, el sistema es capaz devolver imágenes similares. Esta tecnología se puede aplicar a diferentes contexto en donde una consulta pueda ser plasmada en forma de un dibujo tipo sketch.

La presente invención mejora la efectividad de los métodos conocidos a través de una pluralidad de características como: cálculo de gradientes por celdas usando interpolación, cálculo de histogramas por bloques usando interpolación, y generación de sketches desde imágenes regulares a través de características de nivel medio. La estrategia basada en interpolación, además, le da mayor robustez al método propuesto ante variaciones de posición de los objetos.

El componente de normalización potencia permite minimizar el efecto negativo generado por la eventual alta votación en una parte muy reducida del histograma. Finalmente la baja complejidad del método la hace fácil de escalar a grandes colecciones.

DESCRIPCIÓN DE LAS FIGURAS

Figura 1 : Esquema General.

Figura 2: Procesador de Imágenes (200).

Figura 3: Extractor de Características para Sketches(300).

Figura 4: Esquema de la división de un imagen en celdas.

Figura 5: Interpolación en el cálculo del gradiente por celda (320).

Figura 6: Interpolación en el cálculo de histogramas por bloque (340). DESCRIPCIÓN DETALLADA DE LA INVENCIÓN

La presente invención se relaciona con un sistema para realizar búsquedas de imágenes mediante un dibujo hecho a mano (sketch). El sistema (Figura 1) involucra a usuarios (001); un dispositivo (100) con conexión a una red de comunicación que tiene una aplicación que permite realizar consultas (140) y a su vez muestra resultados (150); y una unidad de procesamiento (120), la cual comprende un procesador de imágenes (200), un motor de búsqueda de sketches (130) y un medio de almacenamiento que contiene las imágenes sobre las que se realizarán búsquedas junto a un conjunto de características asociadas a cada una de ellas. Así, un usuario (001) dibuja en dicho dispositivo (100) lo que desea encontrar. Luego, envía el dibujo (140), llamado también sketch, hacia el motor de búsqueda (130) de la unidad de procesamiento (120) que procesa la consulta (140) y devuelve la respuesta (150) al dispositivo (100), que se encargará finalmente de mostrar el resultado al usuario (001).

El procesador de imágenes (200) se encarga de pre-procesar el conjunto de imágenes sobre el que se desea realizar una búsqueda (Figura 2). Este es un proceso que se desarrolla en forma off-line. Cada una de las imágenes (600 ) se procesa bajo los siguientes pasos: (1) Se aplica una operación de suavizamiento (210) con el objetivo de reducir el ruido presente en la imagen (600). Una implementación puede hacer uso de filtros de suavizamiento isotrópicos como por ejemplo, filtros Gaussianos, o puede aplicar filtros anisotrópicos, como el filtro de Malik para producir una imagen suavizada (610). (2) Un detector de contornos (220) genera una imagen de contornos (620) con respecto a la imagen procesada (610) en la etapa anterior. Es importante que la imagen de contornos (620) sea lo más fiel posible a cómo un ser humano generaría un contorno sobre una imagen. Para este fin, se aplica un método basado en características de nivel medio, el cual requiere utilizar algoritmos de aprendizaje de máquina durante un proceso de entrenamiento, con el objetivo de poder determinar si un punto de la imagen debe ser etiquetado como parte del contorno o no. Una implementación utiliza el método de Lim et al. basado en Sketch Tokens como detector de contornos. (3) Un extractor de características para sketches (300) extrae un vector de características (630) de la imagen de contornos (620). El vector de características (630) es almacenado en el dispositivo de almacenamiento (500) junto a la imagen original correspondiente.

Sketch Token es un método para detectar contornos en imágenes basado en un proceso de entrenamiento en el que se genera un modelo de clasificación que permite determinar si un punto en la imagen de entrada corresponde o no a un contorno. Para este fin, es necesario contar con un conjunto de datos de entrenamiento que debe estar compuesto de imágenes regulares, cada una asociada a su correspondiente imagen de contorno. Generalmente, la imagen de contorno es elaborada por un humano. En el proceso de entrenamiento se extraen regiones, generalmente de 31x31 pixels, de las imágenes y se etiquetan como contorno si el centro de la región coincide con un punto de borde en la correspondiente imagen de contorno y como no-contorno en otro caso. Un algoritmo de aprendizaje de máquina genera un modelo de clasificación usando las regiones extraídas. El modelo permite etiquetar a cada punto de una imagen nueva como punto de contorno o no.

La etapa de extracción de características (300) recibe un sketch que puede ser la representación (620) obtenida en la etapa de extracción de contornos de una imagen regular (220) o un sketch de consulta (140) que dibuja un usuario (001). En esta etapa un sketch se divide en MxN celdas, el tamaño final de cada celda dependerá del tamaño de una imagen. Para cada celda se estima un gradiente representativo en base a los gradientes de punto cercanos. Para evitar los problemas generados por la discretización de una imagen en celdas, los gradientes representativos se calculan por interpolación. Así, cada gradiente de un punto P colabora en el cálculo del gradiente representativo de las cuatro celdas más cercanas a P (ver Figura 5). Sea una imagen / de R filas y C columnas la cual se divide en x/V celdas, en donde cada celda se enumera por (p,q), siendo p=0..M- 1 y q=0..N-1. La Figura 4 esquematiza la división de una imagen en celdas con M=N=6. Para determinar el gradiente representativo de cada celda, todos los puntos (i,j) se procesan como sigue:

1. Determinar las cuatro celdas más cercanas a (i,j) como se muestra en la Figura 5. Podemos especificar cada celda cercana a (i,j) por los siguientes cuatro pares de índices (Lpos, n pos), (r jpos, n pos), (I jpos, s_pos), y (r_pos, s_pos), en donde los prefijos /, r, s, n indican left, right, south and north, respectivamente. Los índices de las celdas son calculados con las siguientes fórmulas. , ** {jfC) * N. q = (i¡R) * M

l_post ~ (p --- DJS)J. n__pm ~ £q 0.5) j

r_pos - {p ~ !)J5)j. x_pm ^~ £q™- B.¾ j

2. Calcular un peso para cada celda afectada por (i,j). Este peso es calculado en forma inversa a la distancia entre (i,j) y el centro de la celda subyacente. La distancia es calculada tanto para el eje-x (columnas) como para el eje-y (filas). Para el eje-x, se usa el valor de p de la fórmula anterior, y para el eje-y se usará el valor de q. A continuación se describe el proceso usando p.

2.1. Calcular la distancia de p al lado más izquierdo de la celda en donde el punto (i,j) cae: iñat _p ^:::: p ···· j?j

2.2. Si {dist _p <0.5) 2.3. Si {dist _p >=0.5)

Siguiendo los pasos anteriores, pero usando el valor de q, se obtendrán los pesos s_weight y n weight que completan los pesos con respecto a las cuatro celdas cercana al punto

3. Calcular el gradiente representativo para cada celda en términos de su orientación y magnitud. Para este caso, usaremos la estrategia de Gradiente Cuadrado. Para ello, definiremos dos matrices Ax y Ay, ambas de tamaño MxN, que almacenan las componentes del gradiente representativo para cada celda.

3.1 Inicializar Ax y Ay con todos sus valores en cero.

3.2. Para cada punto (i,j) aplicar los siguientes pasos:

- sea [Gi, Gj] e\ gradiente calculado en el punto Una implementación usa

Sobel.

- definir theta(i,j)=atan2(Gi, Gj)

- definir n(i,j)=sqrt(Gi ^* Gi+Gj ^* Gj)

- Para cada uno de los cuatro celdas (a, b) afectadas por (i,j) actualizar el correspondiente valor en Ax y Ay.

* sean w_a, w_b los pesos correspondientes para a, b, respectivamente con respecto al punto

* definir alpha(a,b)=w_a ^* w_b * definir cx=cos(theta(i )) ^* cos(theta(i ))-sin(theta(i )) ^* sin(theta(i,j))

* definir cy=2 ^* sin(theta(i,j)) ^* cos(theta(i,j))

* Actualizar Ax(a,b)=Ax(a,b)+alpha(a,b) ^* n(i,j) ^* cx

* Actualizar Ax(a,b)=Ax(a,b)+alpha(a,b) ^* n(i,j) ^* cy

4. La orientación beta(a,b) del gradiente representativo en la celda (a,b) se calcula como: beta(a,b)= 0.5 ^* atan2(Ay(a,b), Ax(a,b))

5. La magnitud del gradiente representativo se obtiene como la suma ponderada de todos los gradientes que participaron en la celda correspondiente.

Habiendo calculado el gradiente representativo por cada celda se procede a formar histogramas por bloques. Para ello se divide la imagen en H1xH2 bloques (340). Para cada bloque se calcula un histograma de orientaciones de los gradientes de celdas cercanos al bloque. Al igual al caso anterior, el histograma es calculado mediante interpolación tri-lineal que se compone de una interpolación bi-lineal con respecto a la posición de cada bloque y un interpolación simple con respecto a la orientación de cada celda. Los pesos de la interpolación son estimados en forma similar a lo descrito anteriormente. Además, cada celda votará en forma ponderada por el histograma de bloque correspondiente. La ponderación se realiza mediante la magnitud estimada en cada celda. Un ejemplo de este proceso se presenta en la Figura 6.

Los histogramas por bloques son normalizados (350) independientemente. Una implementación puede usar normalización L2. El histograma del sketch se obtiene agregando los histogramas por bloque (360). Una implementación usa concatenación de histogramas por bloque como método de agregación. Finalmente, el histograma agregado sigue una normalización de potencia, en donde cada valor del histograma se eleva a la potencia t (0<t<1). Una implementación utiliza normalización de raíz cuadrada en donde t=0.5. El resultado final es un histograma agregado normalizado (640) que es el vector de características de un sketch.

Con el método descrito, implementado en el componente de extractor de características para sketches (300), se pueden calcular los vectores de características en forma de histogramas de orientaciones por celda para contornos de imágenes (620) o para sketches de consultas (140).

Antes de que el sistema quedo listo a responder consulta por sketches una unidad de procesamiento (120) carga a memoria los vectores de características del conjunto de imágenes sobre el que se realizarán las búsquedas, mediante un método de indexamiento. Una implementación puede usar Kd-Tree exacto o aproximado como método de indexamiento. El indexamiento permite organizar apropiadamente los vectores de modo que una búsqueda se resuelva eficientemente.

Cuando un usuario realiza una consulta, él dibuja lo que desea encontrar produciendo así el sketch de consulta (140). Luego, el motor de búsqueda (130) extrae las características aplicando el método descrito anteriormente (300) para luego proceder a buscar las K imágenes más parecidas según la similitud entre sus correspondientes vectores de características representados en forma de histogramas de orientaciones. Considerando que los histogramas siguen una representación vectorial, estos se comparan mediante alguna función de distancia vectorial. Una implementación usa una función de Minkowski (e.g Euclidiana o de Manhattan) como función de distancia vectorial.

El resultado (150) con las K fotos más parecidas son enviadas por la red de comunicación (110) para finalmente ser presentadas al usuario (001) a través del dispositivo (100). Una implementación puede asociar el conjunto de imágenes a buscar con un catálogo de productos. Así, estaríamos en una aplicación de búsqueda de productos usando sketches.