HTML5

Juan Mellado, 12 Diciembre, 2011 - 16:25

Los defectos de convexidad son importantes en la medida que se corresponden con ciertos puntos que caracterizan un determinado contorno. El ejemplo más clásico es el de una mano. Si se calcula la envolvente convexa que engloba el contorno de una mano y sobre ella se marcan los puntos que se separan más de dicha envolvente, para cada segmento de la misma, estos puntos se corresponderán con el nacimiento de los dedos, es decir, donde dejan la palma. Estos puntos son los defectos de convexidad, y permiten determinar de una forma muy sencilla algunas características concretas, como por ejemplo el número de dedos que tiene levantados la mano.

Siguiendo la implementación de la función cvConvexityDefects de OpenCV he creado un pequeño programa en JavaScript que calcula los defectos de convexidad. Para hacerlo un poco más atractivo visualmente le he dado forma de un pequeño generador automático de constelaciones.

El programa genera varios puntos al azar asegurándose de que forman un polígono simple, o dicho de otra forma, que no se cruzan sus líneas. A continuación calcula la envolvente convexa. Y por último los defectos de convexidad.

La zona azul claro corresponde al área cubierta por la envolvente convexa. Los puntos blancos con doble círculo son los que se encuentran sobre el borde de la envolvente, el resto está dentro de ella. Los puntos amarillos son los defectos de convexidad, es decir, los puntos más alejados para cada segmento de la envolvente.

Juan Mellado, 7 Diciembre, 2011 - 15:42

Un experimento rápido y un poco tonto con js-aruco usando las sombras como marcadores de realidad aumentada.


Demo online:
www.inmensia.com/files/aruco/debug/debug.html

Juan Mellado, 5 Diciembre, 2011 - 20:15

Otra pieza del rompecabezas que estoy intentando montar. Esta vez una simple conversión de RGB a HSV en JavaScript. Hay mucha información acerca de como hacerlo en Internet, nada nuevo bajo el sol. He creado un pequeño programa que toma una imagen RGB y la convierte a HSV. Para poder ver los resultados he aplicado una pequeña transformación para devolverlos a RGB (no a los valores originales, claro).

Para los que sólo les interese el código, pongo la función de conversión. Admite como entrada los componentes RGB en el rango [0..1] y devuelve un objeto con los componentes HSV. H un ángulo dentro del rango [0..360], y S y V un porcentaje dentro del rango [0..1].

function rgb2hsv(r, g, b){
  var v = Math.max(r, g, b),
      delta = v - Math.min(r, g, b),
      s = v === 0? 0: delta / v,
      h = 0;
   
  if (0 !== delta){
 
    if (v === r){
      h = 60 * (g - b) / delta;
    }else if (v === g){
      h = 120 + (60 * (b - r) / delta);
    }else{
      h = 240 + (60 * (r - g) / delta);
    }
   
    if (h < 0){
      h += 360;
    }
  }
   
  return {h: h, s: s, v: v};
}
Juan Mellado, 1 Diciembre, 2011 - 18:26

Erosión y Dilatación son dos operadores morfológicos que se aplican dentro del campo del procesamiento de imágenes para encontrar mínimos y máximos locales. Su principio de funcionamiento consiste en recorrer todos los pixels de una imagen con una ventana deslizante de tamaño fijo, y para cada pixel calcular el mínimo (erosión) o máximo (dilatación) de entre todos los pixels cubiertos por la ventana.

He creado una sencilla implementación en JavaScript, y un pequeño programa para poder comprobar el resultado de una forma visual. El programa genera una nueva imagen de forma aleatoria cada cinco segundos, la convierte a escala de grises, y le aplica erosión y dilatación.

Como nota personal, comentar que la imagen resultante de la dilatación la encuentro bastante "festiva". El aumento del tamaño de los puntos los hace parece un montón de confeti cayendo.

Con respecto a la implementación, he utilizado un tamaño fijo de ventana de 3x3, de forma que para cada pixel de la imagen se busca el mínimo (o máximo) para los nueve pixels cubiertos por la ventana. No obstante, para ser más estrictos con la definición formal de estos operadores, tendría que haber tenido en cuenta un parámetro de entrada que se conoce como elemento estructurante. Este parámetro es una matriz con el mismo tamaño que la ventana, es decir un array de 3x3 en mi caso, con valores que pueden ser 0 ó 1. Los valores a 0 indican que los pixels vecinos correspondientes no se tienen que tener en cuenta para el cálculo, y los valores a 1 que si se tienen que tener en cuenta. En mi caso quería tener en cuenta todos los vecinos, que es lo mismo que considerar un array con todos sus valores a 1, por lo que he podido obviarlo. De igual forma que he obviado el cálculo en el borde de la imagen para simplificar la implementación.

Como se observa en las imágenes que se van generando, parece que en la erosión desaparece el ruido debido a los puntos aleatorios, mientras que en la dilatación se acentúa. Pero en realidad es un poco más complejo. Lo que se pierde son los valores altos cercanos a valores bajos en la erosión, y los valores bajos cercanos a valores altos en la dilatación. Pensando en ceros y unos se entiende más fácilmente.

Erode - Dilate

No obstante, hay que tener en cuenta que los operadores morfológicos se comportan "visualmente" de forma distinta sobre imágenes binarias (blanco y negro) que sobre imágenes en escala de grises. En las imágenes binarias la erosión "reduce" y la dilatación "aumenta". En las imágenes de escala de grises no necesariamente. La explicación es que en las imágenes binarias el valor 0 normalmente lo hacemos corresponder mentalmente con el color negro del fondo y el 1 con el blanco del frente. Al erosionar un imagen binaria se toma el mínimo que es el 0, por lo que desaparece el frente y hay más color de fondo. Pero en un imagen de escala de grises con el fondo claro mentalmente lo hacemos al revés. Esperamos que desaparezca el punto oscuro de frente y prevalezca el fondo claro, pero como el color de frente es "menor" (negro = valor 0) entonces lo que se consigue es el efecto contrario.

Si alguien está pensando que las imágenes que se están generando automáticamente en este post están invertidas con respecto a lo que debería salir teniendo en cuenta la explicación que he puesto... ¡tiene razón! Me he tomado la licencia de invertirlas para que el resultado sea más intuitivo de entender. Erosionar adegalza. Dilatar engorda. En la práctica es sólo una mera búsqueda de mínimos y máximos.

Por último, una característica a tener en cuenta de estos operadores es que se pueden aplicar varias veces seguidas, para erosionar o dilatar una imagen ya previamente erosionada o dilatada. Y que se pueden mezclar tomando la salida de uno como entrada de otro. De hecho, aplicar una dilatación después de una erosión se llama "apertura" (opening), y aplicar una erosión después de una dilatación se llama "cierre" (closing").

Juan Mellado, 29 Noviembre, 2011 - 20:13

Para un proyecto me ha surgido la necesidad de calcular la envolvente convexa (convex hull) de un polígono. Después de rebuscar un buen rato por la red me he acabado decidiendo por implementar el algoritmo propuesto originalmente por Melkman. He hecho una pequeña aplicación en JavaScript, a modo de applet, para poder hacer pruebas de una manera visual y comprobar los resultados.

El programa permite añadir puntos pulsando sobre la pantalla, creando los segmentos de rectas entre ellos, y evitando que se crucen, ya que el algoritmo sólo funciona con polígonos simples. Por lo demás, he seguido al pie de la letra el pseudo-código propuesto en el paper para calcular la envolvente, ya que es un algoritmo muy sencillo.

Convex Hull

Para los que sólo les interese el código, pongo a continuación la función que calcula la envolvente. La entrada es un array de puntos con los típicos atributos (x, y). Como mínimo debe haber tres puntos en el array para que la función devuelva un resultado.

function convexHull(points){
  var deque = [];

  if (points.length >= 3){

    if ( position(points[0], points[1], points[2]) > 0){
      deque.push(points[0]);
      deque.push(points[1]);
    }else{
      deque.push(points[1]);
      deque.push(points[0]);
    }
    deque.push(points[2]);
    deque.unshift(points[2]);

    for (var i = 3; i < points.length; ++ i){
      var point = points[i];

      if ( position(point, deque[0], deque[1]) < 0 ||
           position(deque[deque.length-2], deque[deque.length-1], point) < 0 ){
              
        while(position(deque[deque.length-2], deque[deque.length-1], point) <= 0 ){
          deque.pop();
        }
        deque.push(point);
           
        while( position(point, deque[0], deque[1]) <= 0 ){
          deque.shift();
        }
        deque.unshift(point);
      }
    }
  }

  return deque;
};