Escala y rotación coincidencia de plantilla invariante

12

Estoy buscando un método para la coincidencia de plantillas invariantes de escala y rotación. Ya probé algunos, pero no funcionaron tan bien para mis ejemplos o tardaron en ejecutarse. La detección de funciones SIFT y SURF falló totalmente. También intenté implementar una función Log-Polar Template Matching, pero nunca terminé (no sabía exactamente cómo hacerlo).

En estos artículos (el primero está en alemán)

http://cvpr.uni-muenster.de/teaching/ss08/seminarSS08/downloads/Wentker-Vortrag.pdf

http://www.jprr.org/index.php/jprr/article/viewFile/355/148

Leí sobre ese método. El mapeo de las coordenadas polares funcionó, pero no sé si es correcto. Las imágenes se ven así.

source_log_polar.png http://www.shareimages.com/images/pics/0/0/3/62394-pZSfl5WenZysnpyVnKg-source_log_polar.png

template_log_polar.png

Y después de hacer coincidir estas 2 imágenes con la función de coincidencia de plantillas de OpenCV obtuve ese resultado

match_log_polar.png

Ahora no sé cómo seguir.

Mis plantillas son siempre símbolos simples en la construcción de planos y los planos en sí. Los símbolos pueden diferir en tamaño y orientación.

Por ejemplo, mi plan simple:

ingrese la descripción de la imagen aquí

Y mi plantilla

ingrese la descripción de la imagen aquí

En este ejemplo, solo hay una plantilla, pero en los planos debe encontrar todas las ocurrencias, incluso las que tienen tamaños y / u orientaciones.

¿Alguien tiene un enfoque de cómo podría resolver esto?

Editar:

Una adición al enfoque de Andrey. El algoritmo de captura de distancia para un perfil radial. (Usando EmguCV)

private float[] getRadialProfile( Image<Gray, byte> image, Point center, int resolution )
 {

 var roi = image.ROI;

 if ( !roi.Contains( center ) )
  {
   return null;
  }

 var steps = resolution;
 var degreeSteps = 360 / (double)resolution;
 var data = image.Data;
 var peak = 0.0f;
 var bottom = double.MaxValue;
 var bottomIndex = 0;
 var width = roi.Width;
 var height = roi.Height;
 var minX = roi.X;
 var minY = roi.Y;

 float[] distances = new float[resolution];
 for ( var i = 0; i < steps; i++ )
  {
   var degree = i * degreeSteps;
   var radial = degree * Math.PI / 180.0;
   var dy = Math.Sin( radial );
   var dx = Math.Cos( radial );

   var x = (double)center.X;
   var y = (double)center.Y;

   while ( true )
    {
    x += dx;
    y += dy;
    if ( x >= minX + width || y >= minY + height || x <= minX || y <= minY )
     {
      x = -1;
      y = -1;
      break;
     }
    var pixel = data[(int)y, (int)x, 0];
    if ( pixel == 0 )
     {
      break;
     }
    }

    float distance = 0.0f;
    if ( x != -1 && y != -1 )
    {
      distance = (float)Math.Sqrt( Math.Pow( (center.X - x), 2 ) + Math.Pow( (center.Y - y), 2 ) );
    }

    distances[i] = distance;
    if ( distance > peak )
    {
      peak = distance;
    }
    if ( distance < bottom )
    {
      bottom = distance;
      bottomIndex = i;
    }
   }

    // Scale invariance. Divide by peak
   for ( var i = 0; i < distances.Length; i++ )
   {
     distances[i] /= peak;
   }

    // rotation invariance, shift to lowest value
   for ( var i = 0; i < bottomIndex; i++ )
   {
     distances.ShiftLeft(); // Just rotates the array nothing special
   }

   return distances;
}
Arndt Bieberstein
fuente
bienvenido a dsp.SE. Intentaremos ayudarlo, pero proporcionar información más precisa sería bueno. ¿Qué quiere decir con SIFT y SURF "falló totalmente"? ¿Qué detectaron / emparejaron? Además, personalmente no sé acerca de la coincidencia de plantillas Log-Polar, pero, si lo intentó, ¿dónde estaba exactamente el problema?
penelope
Las detecciones de funciones SIFT y SURF no encontraron ninguna función en la imagen de la plantilla. Parecía que la plantilla tenía muy poca información (solo ese pequeño arco y una línea). Para la coincidencia Log-Polar encontré un documento donde se describe, pero no la matemática exacta detrás de él. Lo buscaré y lo agregaré.
Arndt Bieberstein
Hola, no mucha gente aquí puede entender alemán, creo: D Pero, para todo lo demás: puedes editar tu propia publicación para agregar cualquier información nueva en el lugar correcto, en lugar de en los comentarios. Y, además, todavía no dijiste con qué exactamente tuviste problemas.
penelope
3
El autor de "Artículo alemán" tiene un artículo en inglés: www-cs.engr.ccny.cuny.edu/~wolberg/pub/icip00.pdf (gracias a google)
SergV

Respuestas:

6

Creo que puedes resolver tu problema de una manera mucho más fácil. Teniendo en cuenta que se trata de planos, no debe preocuparse por la conectividad de borde, el ruido y muchas otras cosas para las que SIFT y SURF se construyeron para adaptarse. Su plantilla es una forma hueca con formas de borde específicas.

Por lo tanto, mi recomendación es:

  • Camine alrededor del perímetro y encuentre un perfil de distancias de los bordes alrededor del centro de la plantilla. Este es el perfil radial de la plantilla. Divida por la mayor distancia, para ser invariante de escala. Gire el vector para que la distancia más pequeña sea la primera, para que la rotación sea invariante. (Si su plantilla no tiene una distancia dominante, puede cambiar el paso 2 más adelante)

ingrese la descripción de la imagen aquí

  • Encuentra manchas en la imagen. Calcule el perfil radial descrito en la parte (1) y compare los dos vectores por correlación normalizada. Si su plantilla no tiene una distancia dominante, la correlación se convierte en una correlación cruzada normalizada y se selecciona el máximo). Los que pasan algún umbral se consideran partidos.

Aquí hay un código de Matlab para que comience: escribí la parte que encuentra el perfil de distancia para un blob específico y lo calculé para la plantilla:

function Doors
    im = imread('http://i.stack.imgur.com/Tf8EV.png');
    im = im(:,:,1);
    template = imread('http://i.stack.imgur.com/PlP4i.png');
    template = template(:,:,1);

    blobs = regionprops(template>0,'Area','Image');
    largestBlob = GetLargestBlob(blobs);
    [prof,edgeImage] = GetBlobRadialProfile(largestBlob);

    figure;
    subplot(1,2,1);plot(prof); title('Radial profile')
    subplot(1,2,2);imshow(edgeImage); title('Template');

end

function [prof,edgeImage] = GetBlobRadialProfile(blob)
    paddedImage = padarray( blob.Image,[8 8]);
    erodedImage = imerode(paddedImage,strel('disk',1));
    edgeImage = xor(erodedImage,paddedImage);

    c = regionprops(paddedImage,'Centroid');
    cx  = c.Centroid(1);
    cy  = c.Centroid(2);

    [y,x] = find(edgeImage);
    rad = (x(:)-cx).^2 + (y(:)-cy).^2;
    [~,minIndex] = min(rad);
    contour = bwtraceboundary(edgeImage, [y(minIndex), x(minIndex)],'N');
    prof = (contour(:,2)-cx).^2 + (contour(:,1)-cy).^2;
    prof = prof./max(prof);
end

function largestBlob = GetLargestBlob(blobs)    
    area = [blobs.Area];
    [~,index] = max(area);
    largestBlob = blobs(index);
end
Andrey Rubshtein
fuente
¿Supongo que esto no funciona con formas no cerradas? ¿O simplemente omito estos "agujeros" en la forma.
Arndt Bieberstein
@ArndtBieberstein, Sí, solo funciona para formas cerradas. Supongo que debería haber algún método para extenderlo.
Andrey Rubshtein
Como OpenCV no contiene la función bwtraceboundary, escribí la mía y simplemente "salté" los agujeros y los llené con ceros. Aquí hay un pequeño ejemplo de cómo se ven los resultados ahora. 5 parcelas para cada plantilla. Los puntos rojos son los puntos de partida. Parcela de muestra
Arndt Bieberstein
@ArndtBieberstein, muy bien! Tal vez podría compartir los resultados con nosotros una vez que haya terminado.
Andrey Rubshtein
Claro, el Código no es tan bueno o eficaz, pero funciona. Lo adjuntaré debajo de mi pregunta. Está escrito en C # (estoy usando EmguCV)
Arndt Bieberstein
3

Aquí está la idea básica de lo que sé que se puede hacer, basado en una charla del profesor Anurag Mittal de IIT Madras.

La idea es la detección de objetos basada en la forma, pero obviamente también se puede extender a otros lugares.

  1. Calcule los bordes utilizando el detector de bordes Berkeley.
  2. Conecte los bordes obtenidos. "Detección de límite de objeto global".
  3. Concordancia de formas usando distancia de chaflán o distancia de Houstoff.

Su artículo sobre el mismo está disponible en: Detección de objetos deformables basada en contornos de múltiples etapas.

Por otro lado, creo que SIFT debería funcionar como los algoritmos de detección de esquinas funcionarían en la función de plantilla que tiene allí.

Nota: SIFT no es completamente invariante en rotación. No puede hacer frente a rotaciones> 60 grados más o menos. Entonces, formar múltiples plantillas es una buena idea.

Al igual que en los Transfrom de Fourier-Mellin basados ​​en log-polar: Causan pérdida de información debido a cómo se realiza el muestreo de las transformadas.

Naresh
fuente
¡Este método suena realmente prometedor! No puedo abrir su enlace, pero busqué en Google su enfoque. ¡No sabía que SIFT ese SIFT no es completamente ivariante de rotación! Muy buena respuesta! +1
Arndt Bieberstein
1
Casi no encontré nada sobre Chamfer Distance y cómo funciona, para aquellos que también están buscando esto, prueba este enlace.
Arndt Bieberstein
@Naresh SIFT no es invariante en rotación para grandes rotaciones fuera del plano. No en el mismo plano.
a-Jays
1

No lo he pensado mucho, pero estoy bastante seguro de que se puede tener una solución robusta sin muchos problemas usando los descriptores clásicos de Fourier (FD). Creo que su problema podría ser un muy buen candidato para eso. No piense que necesita hacer detección de bordes porque tiene dibujos de líneas negras. Simplemente comience el escaneo de ráster hasta que toque cualquier píxel, luego haga lo siguiente:

Simplemente trate los perímetros de su habitación como si fueran una señal 1D, donde la amplitud de la señal es la distancia normal desde el centroide del objeto, muestreada a una velocidad constante. Entonces, haga un modelo FD simple para la puerta. Luego, escanee los parámetros de cada habitación con una especie de filtro convexo buscando un borde ascendente, un pico y una caída, que establece una ventana de inicio / parada de "señal" para capturar. Haga un FFT o algo similar de FD en esa "señal" capturada y compárela con la plantilla de FD. Quizás el paso de comparación de plantilla puede ser una simple correlación con un umbral para desencadenar una coincidencia. Dado que solo sus puertas tienen bordes redondos, debería ser un problema de coincidencia FD bastante fácil.

Piense en ello como usar la recuperación de imágenes o música de FD desde una base de datos. Un montón de libros blancos sobre eso.

Este es un buen tutorial sobre el uso de FD para aproximar formas: dudo que lo necesite, pero también puede transformar primero sus imágenes en un marco de coordenadas polares para lidiar con las rotaciones, como se propone en este documento: Recuperación de imágenes basadas en formas usando descriptor genérico de Fourier

¿Ves cómo FD parametriza la detección del perímetro de la manzana? La misma idea que tu puerta.

Por cierto, estoy bastante seguro de que mapear todo el esquema a coordenadas polares no ayudará a la invariancia rotacional; necesitaría hacer eso con respecto al centroide de cada puerta, que es exactamente con lo que es su problema para comenzar. Es por eso que creo que solo desea capturar candidatos para puertas, y tal vez asignarlos a coordenadas polares para que coincidan con la plantilla de puerta FD, como se hizo en ese documento vinculado anteriormente.

déjame saber cómo te va si intentas este enfoque.

Ariel Bentolila
fuente
0

Quizás encuentre útil este código de Matlab que escribí: Fractal Mosaics

Implementa el documento "Registro robusto de imágenes usando la transformación Log-Polar" ( pdf ) en una aplicación artística que requería más solidez que los métodos tradicionales que encontré.

usuario2348114
fuente