Detección y descripción de características – Lo que vemos V.S. lo que entendemos

Para una amplia variedad de aplicaciones computacionales encontrar las correspondencias visuales entre un par de imágenes dado es una de las temas de investigación actuales más importantes dentro del área de visión computacional. Tareas como la representación de imágenes, el reconocimiento de patrones y objetos, la reconstrucción de escenas 3D, o la navegación visual  no serían posibles de llevar a cabo sin la presencia de características estables y representativas en la imagen.

La descomposición de una imagen digital en regiones de interés o “características locales” es una técnica ampliamente utilizada en visión artificial que permite, tanto explotar las propiedades de apariencia local, como reducir la complejidad de los problemas de visión computacional.

La tarea de encontrar correspondencias visuales entre imágenes de una misma escena se divide en dos partes importantes: En primer lugar está la detección de los puntos clave (características locales) más sobresalientes en la imagen y, en segundo lugar, la descripción de dichos puntos de interés.


1

Figura 1. Características Locales detectadas en una imagen digital


Los detectores de características ideales encuentran regiones salientes en la imagen tales que sean posibles de detectar aun cuando estos estén sujetos a cambios de punto de vista; en forma más general, estos deben ser robustos a todas las transformaciones posibles de la imagen. Una vez que se encuentra un conjunto distintivo de puntos de interés con características contrastantes, es posible construir un descriptor de características para cada uno de dichos elementos. Un descriptor de características ideal debe ser capaz de capturar la información más importante y distintiva de una región saliente, de manera que si la misma estructura es detectada posteriormente, esta pueda ser reconocida. En este contexto, ciertas características de imagen como la intensidad de color, las formas, las texturas, o bien la respuesta de ciertos tipos de filtros espaciales pueden ser utilizados para construir descriptores.

Además de cumplir con estas características, la velocidad con que se detecta y describe a cada uno de estos puntos significativos de la imagen debe también ser optimizada para ajustarse a las restricciones de tiempo demandadas por ciertas aplicaciones particulares. Por esta razón la dificultad inherente de extraer características útiles de una imagen yace en balancear dos metas comunes de competitividad: La  calidad en la descripción de las características locales y los requerimientos de costo computacional.


2

Figura 2. Correspondencias entre los puntos característicos de un par de imágenes de una misma escena.


La década pasada fue testigo de avances clave en lo que se refiere a la extracción de puntos característicos en imágenes digitales. En el 2004 David Lowe propuso el algoritmo SIFT (Scale Invariant Feature Transform), un detector y descriptor de características locales que es invariante tanto a la rotación como al escalamiento.  Dicho algoritmo emplea una versión adaptado a la escala del método de Diferencias Gaussianas (DoG) en conjunto con el descriptor de características conocido como Histograma de Gradientes Orientados (HOG).  A pesar de que el enfoque empleado por el algoritmo SIFT implica un considerable costo computacional, este es ampliamente aceptado como uno de las opciones de más alta calidad actualmente disponibles, prometiendo distintividad y robustez a una variedad de transformaciones de imagen comunes.

Recientemente, la meta en la investigación de algoritmos de detección y descripción de características locales ha consistido en buscar un desempeño similar a SIFT, mientras que a su vez se adquiera una complejidad computacional mucho menor. El algoritmo SURF (Speeded-Up Robust Features) desarrollado y publicado por Herbert Bay en el 2006 es quizá el ejemplo más importante de ello. Dicho algoritmo de detección y descripción de características locales está basado en principios similares al algoritmo SIFT, diferenciándose principalmente en la explotación de las propiedades de la imagen integral para llevar a cabo aproximaciones eficientes de las operaciones de filtrado implicadas en la detección de los puntos clave, lo cual se traduce en una velocidad de computo notoriamente superior en comparación al algoritmo SIFT.

 

CARACTERÍSTICAS LOCALES

Una característica local puede ser definida como un patrón en una imagen digital que difiere de su vecindad inmediata.  Dichas características están usualmente asociadas con algún cambio en alguna o varias de las propiedades de la imagen, como pueden ser los cambios en el nivel de intensidad, el color o la textura.

Las características locales pueden ser puntos específicos en la imagen, aunque otras características de la imagen como los bordes o pequeñas masas (blobs) pueden ser también consideradas como tal.

Típicamente, algún tipo de información es extraída de una región centrada sobre la posición de la característica local y de esta forma dicha información puede convertirse en un descriptor de dicha característica.

El principal objetivo de la detección y descripción de características locales en una imagen es proveer una abstracción general y compacta de la información contenida en dicha imagen, de manera que esta pueda ser utilizada con mayor facilidad y eficiencia en diversas aplicaciones de visión computacional.


3

Figura 3. La detección y descripción de características locales en una imagen digital permiten obtener una representación general y compacta de la información contenida en dicha imagen.


En términos generales, una característica local ideal debe de tener las siguientes propiedades:

  • Repetibilidad: Dadas dos imágenes de un mismo objeto o escena en particular, tomadas en condiciones diferentes de punto de vista, un alto porcentaje de las características detectadas en dicho objeto o escena deben poder ser encontrados en ambas imágenes.
  • Distintividad: Los patrones de intensidad asociados con la característica detectada deben de mostrar suficiente variación, de manera que dicha característica local pueda ser distinguida apropiadamente.
  • Localidad: La característica debe ser local, con el fin de eliminar la probabilidad de oclusión y para permitir la aproximación a través de modelos simples de las deformaciones geométricas y fotométricas entre dos imágenes tomadas desde puntos de vista diferentes.
  • Cantidad: El número de características locales detectadas debe ser lo suficientemente grande, tal que un número razonable de estas sean detectadas aun en objetos muy pequeños. Además, la densidad de características detectadas debe reflejar el contenido de información de una imagen y proveer una representación compacta de la misma.
  • Precisión: Las características detectadas deben estar localizadas en forma precisa, tanto en ubicación en la imagen, así como con respecto de la escala y deformación geométrica del objeto.
  • Eficiencia: Preferentemente, el tiempo de detección de características en una nueva imagen debe ser lo suficientemente razonable para aplicaciones donde el tiempo es crítico.

 

DESCRIPTORES DE CARACTERÍSTICAS

Los detectores de características locales permiten localizar y visualizar propiedades importantes en las imágenes digitales, sin embargo la simple detección de estos puntos o regiones características usualmente no provee información suficiente que pueda ser utilizada en aplicaciones de visión artificial.

Los descriptores de características  juegan un papel importante dentro de una amplia variedad de aplicaciones de visión computacional ya que estos permiten extraer información significativa correspondiente a una amplia variedad de propiedades en la imagen.

En forma general, un descriptor de características (o simplemente descriptor) se puede definir como una abstracción de las características visuales contenidas en una imagen digital. Dichos descriptores usualmente describen características elementales como son la forma, el color, la textura, el movimiento, entre otras.

Como resultado de la descripción de características, típicamente se obtiene lo que se conoce como vector de características, el cual contiene una descripción codificada de cada uno de los puntos característicos encontrados en la imagen.

Dependiendo del contenido y la cantidad de información característica que engloban, los descriptores de características  se pueden clasificar como:

  1. Descriptores Globales: Este tipo de descriptores proporcionan una descripción general de la información de color o textura, contenida en una imagen. Un ejemplo típico de este tipo de descriptores son los histogramas de intensidad, los cuales ofrecen una descripción clara de la distribución estadística en los niveles de intensidad de los píxeles de la imagen.
  2. Descriptores Locales: Como su nombre lo sugiere, los descriptores locales proporcionan una descripción informativa de ciertos elementos u objetos específicos en la imagen digital.  Este tipo de descriptores se utilizan para sustraer información descriptiva de los puntos o regiones de interés encontradas por un detector de características locales.

 

Los descriptores de características pueden ademas clasificarse de acuerdo al tipo de información empleada pasa su construcción, como por ejemplo:

  1. Descriptores de forma: Este tipo de descriptores proporcionan información referente a la geometría de los elementos u objetos en una imagen.
  2. Descriptores de color: Los descriptores de color proveen información sobre la distribución de color en los elementos y objetos que conforman la imagen.
  3. Descriptores de textura: Estos descriptores ofrecen una descripción distintiva de propiedades estructurales de la imagen, como son el contraste, la direccionalidad, o la rugosidad, entre otras.
  4. Descriptores de movimiento: Los descriptores de movimiento tienen la función de extraer la información acerca de la relación espacio-temporal de los objetos en una imagen. El movimiento se puede relacionar con el cambio de posición de los objetos en una escena, o bien con el desplazamiento del dispositivo utilizado para la captura de imágenes.

 

Un algoritmo de descripción de características abstrae la información contenida alrededor de un punto de interés dado y la representa a través de un vector de características.

Encontrar las correspondencias entre las características locales en un par de imágenes diferentes de una misma escena u objeto es la tarea más importante derivada de la descripción de dichas características locales, y es lo que hace posible la implementación de una amplia variedad de aplicaciones de visión computacional.


4

Figura 4. Aplicación de la detección y descripción de características para la detección de objetos en una imagen.


En entradas posteriores veremos con mas detalle algunas de las técnicas mas populares para detectar y describir características en una imagen. ¡Manténganse sintonizados!

Detección y descripción de características – Lo que vemos V.S. lo que entendemos

Una clase para gobernarlos a todos.

AISearch

AISearch es una implementación propia de los algoritmos de búsqueda populares en textos de investigación, con objeto de tener un toolbox fácil de implementar, así como poder cambiar la resolución del problema con distintos algoritmos de forma sencilla. Buscando tener un punto de partida para analizarlos, compararlos o diseñar nuevas estrategias, enfocándose únicamente en los operadores del algoritmo.

Los algoritmos de búsqueda metaheurísticos que utilizan una población de soluciones, buscan mejorar esta población de soluciones mediante un proceso iterativo que hace uso de la información acumulada durante todo el proceso, o bien la disponible en cada iteración. El proceso de estos puede ser abstraído en conjunto con el siguiente diagrama de flujo.

Untitled Diagram (2)

Estos algoritmos comparten múltiples procesos en común, y aunque estos algoritmos pueden ser implementados de múltiples formas, también pueden ser organizados a manera de clases, para trabajar con ellos en un paradigma de programación orientada a objetos. De esta forma pueden compartir una gran parte de las funciones que los componen, y ser mejor comprendidos y analizados únicamente en el núcleo de los operadores que los definen.

Uno no simplemente implementa todos los algoritmos

Hacer uso de la orientación a objetos, trae consigo múltiples beneficios, entre ellos un mayor reúso del código, encapsulación, y un mejor mantenimiento y optimización del código. Aunque esta entrada no busca desarrollar el tema de programación orientada a objetos, una introducción sencilla puede encontrarse en wikipedia.

Con este objetivo en mente, el primer paso entonces es describir la clase principal, que contiene todas las propiedades y métodos que pueden ser compartidos por cada uno de los diferentes algoritmos. Por ejemplo, todos ellos tienen un arreglo donde almacenan la información de la soluciones que se encuentran actualmente en la población. Así mismo un vector con la información de asociada de desempeño por cada solución. Todos ellos comienzan con una población inicial aleatoria, por lo que tener una sola función para realizar este proceso permite que puedan ser comparados equitativamente, o bien que si esta función es mejorada, o se arregla algún error dentro de ella, haciendo cambio de esta, todos los algoritmos se beneficiaran de dicho cambio.

Las propiedades consideradas para esta clase principal son:

 properties
        sizePopulation = 30;
        noDimensions = 1;
        population = [];            %size = (sizePop, NoDim)
        fitness = [];               %size = (sizePop, 1)
        bestSolution = [];
        bestFitness = inf;
        fitnessFunction;
        numberOfFunctionCalls = 0;
        maxNoIterations = 100;
        actualIteration = 0;
 end

Los métodos que estos algoritmos comparten tienen que ver con la población, su fitness, ordenamiento, entre otras utilidades que pueden ser parte o no de los algoritmos, como la visualización gráfica de la información. A continuación citaremos cada uno de ellos.

  • Población Inicial: Usualmente estos algoritmos comienzan con un conocimiento nulo del problema que están buscando resolver de forma optima. Por lo que sus primeros intentos comienzan con soluciones totalmente aleatorias.
function initialPopulation(obj, sizePopulation, noDimensions)
   obj.population = rand(sizePopulation, noDimensions);
end
  • Evaluación de la Población: Cada solución en la población debe ser evaluada para conocer su valor de desempeño, este valor indica la superioridad de las soluciones sobre las demás. Usualmente este valor busca ser maximizado o bien minimizado.
function fit = evalPopulation(obj, population)
   fit = zeros(size(population,1),1);
   for i=1:size(population,1)
     fit(i) = obj.fitnessFunction(population(i,:));
   end
end
  • Ordenamiento de la población: Algunas veces es conveniente tener la población ordenada de acuerdo a su valor de desempeño, de forma que las mejores soluciones se encuentren primero. Aunque este proceso es conocido por ser costoso computacionalmente, por lo que su uso debe ser limitado.
function sortPopulation(obj)
   temp = sortrows([obj.fitness, obj.population], 1);
   obj.fitness = temp(:,1);
   obj.population = temp(:,2:end);
end
  • Revisar los limites de búsqueda: En ocasiones los algoritmos utilizan operadores que pueden sacar de los limites permisibles a las variables que estás siendo controladas en las soluciones. Debido a que la solución que se busca esta restringida en un área bien delimitada, soluciones fuera de esta área no deben ser aceptadas. Por lo que esta función busca entre la población soluciones que tengan variables fuera del rango permisible y las reúbica en el limite permitido.
function solutions = checkBounds(obj, solutions)
   solutions(solutions>1)=1;
   solutions(solutions<0)=0;
end

Para esta implementación consideramos que todos los problemas trabajan variables en el rango de 0 a 1, y estas son escaladas para cada problema en el rango de interés de los mismos.

  • Actualiza la mejor solución: Es común que los algoritmos utilicen la mejor solución encontrada en todo el proceso evolutivo para guiar el movimiento o evolución de la población, para ello este valor debe ser actualizado en cada iteración.
function updateBest(obj)
   [bestFitTemp, bestIndex] = min(obj.fitness);
   if bestFitTemp < obj.bestFitness
      obj.bestSolution = obj.population(bestIndex,:);
      obj.bestFitness = bestFitTemp;
   end
end
  • Ejecución del algoritmo: Este método se encarga de iniciar el proceso de búsqueda, y mantener la evolución del proceso por el número de iteraciones definidas en la clase. Es importante el orden en el que los otros métodos son llamados, así como el método llamado operadores (operators) que es la implementación del algoritmo en sí.
function start(obj)
   obj.initialPopulation();
   obj.evalPopulation();
   for i=1:obj.maxNoIterations
      obj.actualIteration = i;
      obj.operators();
      obj.updateBest();
   end
end

El metodo operators se define como abstracto, por lo que cada subclase (cada algoritmo) debe definirlo. Este método se encarga de modificar las soluciones actuales con la información recibida, y se espera que devuelva la población con las nuevas soluciones junto con el valor de desempeño de las mismas. Esto lo puede hacer internamente o bien utilizando la función definida en la clase base.

  • Otras: Existen otras funciones que son compartidas entre los algoritmos relacionadas en la forma en la que se presenta la información del proceso de evolución, o bien los resultados obtenidos. Estas funciones pueden encontrarse en el repositorio de GitHub.

Cómo un ejemplo de la implementación del algoritmo, dejó el código del método operators del algoritmo basado en enjambre de particulas (PSO), que será mejor explicado en otra ocación:

function operators(obj)
   % atraction to the best personal solution
   pbAtraction = rand(obj.sizePopulation,obj.noDimensions) .* ...
        (obj.bestPersonal(:,2:end)-obj.population);

   % atraction to the best global solution
   bestAtraction = rand(obj.sizePopulation,obj.noDimensions) .* ...
        (repmat(obj.bestSolution, obj.sizePopulation, 1) - obj.population);

   % update velocity trayectories.
   obj.velocity = obj.velocityParam * obj.velocity + ...
        obj.bestPersonalParam * pbAtraction + ...
        obj.bestParam * bestAtraction;

   % update solutions
   obj.population = obj.population + obj.velocity;
   obj.checkBounds();

   % eval fitness
   obj.evalPopulation();
end

Cada función contiene código extra que revisa las condiciones de las variables, y permite un uso mas dinámico de estos métodos. Pero el concepto clave fue expuesto en este documento. Si tienes alguna duda o comentario sobre algún código en esta implementación déjanos saber en la sección de abajo.

Una clase para gobernarlos a todos.