¿Cómo detectar esquinas en imágenes binarias con OpenGL?

Tengo imágenes binarias de 160x120 como:

Me gustaría detectar las esquinas de esas manchas blancas. Anteriormente están cerrados por la morfología matemática, por lo que no debería tener esquinas internas. En este caso específico, me gustaría tener 16 esquinas, como:

Mi primer intento fue usar algunas funciones de OpenCV como goodFeaturesToTrack o FAST, pero son particularmente lentas (además, FAST es muy inestable). Mi idea sería hacer tal cálculo en la GPU, ya que mi imagen de origen proviene de ella. Busqué ideas en la web sobre cómo escribir tales sombreadores (estoy usando OpenGL ES 2.0), pero no encontré nada concreto. ¿Alguna idea de cómo podría iniciar un algoritmo de este tipo?

¿En qué tamaño de imágenes estás operando? ¿A qué velocidad de cuadro? ¿En qué hardware? FAST es bonito, erm, rápido en mi experiencia.

También he visto que FAST se usa como un detector de ROI con goodFeaturesToTrack ejecutado en los ROI identificados para proporcionar una mejor estabilidad sin ejecutar la penalización de gFTT en toda la imagen.

El detector de esquina "Harris" también es potencialmente muy rápido, ya que se compone de operaciones muy simples (¡sin sqrt () por píxel, por ejemplo!), No tan estable como gFTT, pero posiblemente más que FAST.

(En términos de implementación de GPU, Google gpu cornerparece presentar una gran cantidad de enlaces, pero no tengo idea de cuán adecuados podrían ser; tiendo a implementar en FPGA).

Simplemente estaba implementando algo como esto en OpenGL ES 2.0 usando la detección de esquinas de Harris, y aunque no he terminado por completo, pensé en compartir la implementación basada en sombreadores que tengo hasta ahora. Lo hice como parte de un marco de código abierto basado en iOS , por lo que puede consultar el código si tiene curiosidad sobre cómo funciona algún paso en particular.

Para hacer esto, utilizo los siguientes pasos:

• Reduzca la imagen a sus valores de luminancia utilizando un producto de puntos de los valores RGB con el vector (0.2125, 0.7154, 0.0721).

• Calcule las derivadas X e Y restando los valores del canal rojo de los píxeles a la izquierda y a la derecha y arriba y debajo del píxel actual. Luego almaceno la derivada x al cuadrado en el canal rojo, la derivada Y al cuadrado en el canal verde y el producto de las derivadas X e Y en el canal azul. El sombreador de fragmentos para esto se ve así:

  precision highp float;
  
  varying vec2 textureCoordinate;
  varying vec2 leftTextureCoordinate;
  varying vec2 rightTextureCoordinate;
  
  varying vec2 topTextureCoordinate; 
  varying vec2 bottomTextureCoordinate;
  
  uniform sampler2D inputImageTexture;
  
  void main()
  {
   float topIntensity = texture2D(inputImageTexture, topTextureCoordinate).r;
   float bottomIntensity = texture2D(inputImageTexture, bottomTextureCoordinate).r;
   float leftIntensity = texture2D(inputImageTexture, leftTextureCoordinate).r;
   float rightIntensity = texture2D(inputImageTexture, rightTextureCoordinate).r;
  
   float verticalDerivative = abs(-topIntensity + bottomIntensity);
   float horizontalDerivative = abs(-leftIntensity + rightIntensity);
  
   gl_FragColor = vec4(horizontalDerivative * horizontalDerivative, verticalDerivative * verticalDerivative, verticalDerivative * horizontalDerivative, 1.0);
  }
  

  donde las variaciones son solo las coordenadas de textura offset en cada dirección. Precalculo esto en el sombreador de vértices para eliminar las lecturas de textura dependientes, que son notoriamente lentas en estas GPU móviles.

• Aplique un desenfoque gaussiano a esta imagen derivada. Utilicé un desenfoque horizontal y vertical separado, y aproveché el filtrado de textura de hardware para hacer un desenfoque de nueve golpes con solo cinco lecturas de textura en cada pasada. Describo este sombreador en esta respuesta de desbordamiento de pila .

• Ejecute el cálculo real de detección de esquina de Harris utilizando los valores de derivada de entrada borrosa. En este caso, en realidad estoy usando el cálculo descrito por Alison Noble en su Ph.D. disertación "Descripciones de superficies de imagen". El sombreador que maneja esto se ve así:

  varying highp vec2 textureCoordinate;
  
  uniform sampler2D inputImageTexture;
  
  const mediump float harrisConstant = 0.04;
  
  void main()
  {
   mediump vec3 derivativeElements = texture2D(inputImageTexture, textureCoordinate).rgb;
  
   mediump float derivativeSum = derivativeElements.x + derivativeElements.y;
  
   // This is the Noble variant on the Harris detector, from 
   // Alison Noble, "Descriptions of Image Surfaces", PhD thesis, Department of Engineering Science, Oxford University 1989, p45.     
   mediump float harrisIntensity = (derivativeElements.x * derivativeElements.y - (derivativeElements.z * derivativeElements.z)) / (derivativeSum);
  
   // Original Harris detector
   //     highp float harrisIntensity = derivativeElements.x * derivativeElements.y - (derivativeElements.z * derivativeElements.z) - harrisConstant * derivativeSum * derivativeSum;
  
   gl_FragColor = vec4(vec3(harrisIntensity * 10.0), 1.0);
  }
  

• Realice la supresión local no máxima y aplique un umbral para resaltar los píxeles que pasan. Utilizo el siguiente sombreador de fragmentos para muestrear los ocho píxeles en la vecindad de un píxel central e identificar si es el máximo en ese grupo:

  uniform sampler2D inputImageTexture;
  
  varying highp vec2 textureCoordinate;
  varying highp vec2 leftTextureCoordinate;
  varying highp vec2 rightTextureCoordinate;
  
  varying highp vec2 topTextureCoordinate;
  varying highp vec2 topLeftTextureCoordinate;
  varying highp vec2 topRightTextureCoordinate;
  
  varying highp vec2 bottomTextureCoordinate;
  varying highp vec2 bottomLeftTextureCoordinate;
  varying highp vec2 bottomRightTextureCoordinate;
  
  void main()
  {
      lowp float bottomColor = texture2D(inputImageTexture, bottomTextureCoordinate).r;
      lowp float bottomLeftColor = texture2D(inputImageTexture, bottomLeftTextureCoordinate).r;
      lowp float bottomRightColor = texture2D(inputImageTexture, bottomRightTextureCoordinate).r;
      lowp vec4 centerColor = texture2D(inputImageTexture, textureCoordinate);
      lowp float leftColor = texture2D(inputImageTexture, leftTextureCoordinate).r;
      lowp float rightColor = texture2D(inputImageTexture, rightTextureCoordinate).r;
      lowp float topColor = texture2D(inputImageTexture, topTextureCoordinate).r;
      lowp float topRightColor = texture2D(inputImageTexture, topRightTextureCoordinate).r;
      lowp float topLeftColor = texture2D(inputImageTexture, topLeftTextureCoordinate).r;
  
      // Use a tiebreaker for pixels to the left and immediately above this one
      lowp float multiplier = 1.0 - step(centerColor.r, topColor);
      multiplier = multiplier * 1.0 - step(centerColor.r, topLeftColor);
      multiplier = multiplier * 1.0 - step(centerColor.r, leftColor);
      multiplier = multiplier * 1.0 - step(centerColor.r, bottomLeftColor);
  
      lowp float maxValue = max(centerColor.r, bottomColor);
      maxValue = max(maxValue, bottomRightColor);
      maxValue = max(maxValue, rightColor);
      maxValue = max(maxValue, topRightColor);
  
      gl_FragColor = vec4((centerColor.rgb * step(maxValue, centerColor.r) * multiplier), 1.0);
  }
  

Este proceso genera un mapa de esquina de sus objetos que se ve así:

Los siguientes puntos se identifican como esquinas en función de la supresión y el umbral no máximos:

Con los umbrales adecuados establecidos para este filtro, puede identificar las 16 esquinas de esta imagen, aunque tiende a colocar las esquinas un píxel más o menos dentro de los bordes reales del objeto.

En un iPhone 4, esta detección de esquina se puede ejecutar a 20 FPS en 640x480 cuadros de video provenientes de la cámara, y un iPhone 4S puede procesar fácilmente videos de ese tamaño a más de 60 FPS. Esto debería ser mucho más rápido que el procesamiento vinculado a la CPU para una tarea como esta, aunque en este momento el proceso de lectura de los puntos está vinculado a la CPU y es un poco más lento de lo que debería ser.

Si desea ver esto en acción, puede tomar el código de mi marco y ejecutar el ejemplo FilterShowcase que viene con él. El ejemplo de detección de esquina de Harris se ejecuta en video en vivo desde la cámara del dispositivo, aunque como mencioné, la lectura de los puntos de esquina actualmente se produce en la CPU, lo que realmente está ralentizando esto. También me estoy moviendo a un proceso basado en GPU para esto.

Los detectores de esquina "robustos" como Shi-Tomasi y Moravec son notoriamente lentos. compruébelos aquí: http://en.wikipedia.org/wiki/Corner_detection FAST probablemente es el único detector de esquinas ligero y suficientemente bueno. Puede mejorar FAST haciendo una supresión no máxima: elija la salida FAST con el mejor puntaje de "esquina" (hay varias formas intuitivas de calcularlo, incluyendo Shi-Tomasi y Moravec como puntaje de esquina) También puede elegir entre varios detectores FAST: de FAST-5 a FAST-12 y FAST_ER (el último probablemente sea demasiado grande para dispositivos móviles) Otra forma es generar FAST: obtenga el generador de código FAST del sitio del autor y capacítelo en el conjunto de imágenes probables. http://www.edwardrosten.com/work/fast.html

No es realmente específico de GPU, pero el algoritmo SUSAN de Steve Smith es bueno para la detección de esquinas.

El algoritmo es bastante simple, como lo muestra el código fuente en C.