Scale and Rotation invariant Template Matching

Question

I'm looking for a method for scale and rotation invariant Template matching. I already tried some, but they didn't work so good for my examples or took for ever to execute . SIFT and SURF Feature detection failed totally. I also tried to implement a Log-Polar Template Matching function, but I never finished (didn't know exactly how to).

In these Articles (the first is in german)

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

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

I read about that method. Mapping the polar coordinates worked, but I don't know if it's right. The Images look like this.

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

And after matching these 2 images with OpenCV's Template Matching function i got that result

Now I don't how to go on.

My templates are always simple symbols in building blueprints and the blueprints itself. The symbols can differ in size and orientation.

For example my simple blueprint:

And my template

In this example there is only one template, but in the blueprints it should find all occurrences, even the ones with sizes and/or orientations.

Does anyone have an approach how I could solve this?

Edit:

An addition to Andrey's approach. The distance capturing algorithm for a radial profile. (Using 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;
}

Answer 1

I think that you can solve you problem in a much easier way. Considering that you are dealing with blueprints, you should not worry about edge connectivity, noise, and many other things that SIFT and SURF were built to accommodate for. Your template is a hollow shape with specific edge shapes.

Thus, My recommendation is:

• Walk around the perimeter and find a profile of distances of the edges around the center of the template. This is the radial profile of the template. Divide by largest distance, to be scale invariant. Rotate the vector so that the smallest distance is the first, to be rotation invariant. (If your template has no dominant distance, you can change step 2 later)

• Find blobs in the image. Compute the radial profile described at part (1), and compare the two vectors by normalized correlation. If your template has no dominant distance, correlation becomes normalized cross-correlation, and selecting maximum). Those who pass some threshold are considered matches.

Here is some Matlab code for you to start with - I wrote the part that finds distance profile for a specific blob and calculated it for the template:

function Doors
    im = imread('https://i.sstatic.net/Tf8EV.png');
    im = im(:,:,1);
    template = imread('https://i.sstatic.net/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

Answer 2

Here's the basic idea of what I know can be done, based on a talk by Professor Anurag Mittal of IIT Madras.

The idea is of shape based object detection, but can obviously be extended elsewhere as well.

1. Compute edgels using Berkeley edge detector.
2. Connect edges obtained. "Global Object Boundary Detection".
3. Shape matching using Chamfer distance or Houstoff Distance.

His paper on the same is available at: Multi-Stage Contour based Detection of Deformable Objects.

On the other hand I think SIFT should work as corner detection algorithms would work on the template feature that you have over there.

Note: SIFT isn't completely rotation invariant. It is not able to cope with rotations > 60 degrees or so. So forming multiple templates is a good idea.

As on log-polar based Fourier-Mellin Transfroms: They cause loss of information due to how sampling takes place for the transforms.

Answer 3

I have not given it much thought, but I'm pretty sure a robust solution can be had without much trouble using classic Fourier Descriptors (FD). I think your problem might be a very good candidate for that. Don't think you need to do edge detection b/c you have black line drawings. Just start raster scanning until you hit any pixels, then do the following:

Just treat your room perimeters as if they were a 1D signal, where the signal amplitude is the normal distance from the centroid of the object, sampled at some steady rate. So, do a simple FD model for the door. Then, scan each room's parameter with a sort of convex filter looking for a rising edge, a peak, and fall, which sets a start/stop window of "signal" to capture. Do a FFT or similar FD algo on that captured "signal" and compare against the FD template. Maybe the template compare step can be a simple correlation with a threshold to trigger a match. Since only your doors have round edges that should be a pretty easy FD matching problem.

Think of it like using FD's doing image or music retrieval from a database. Lots of white papers on that.

This is a good tutorial on using FDs to approximate shapes: I doubt you'll need it, but you can also first transform your images to a polar coordinate framework to deal with rotations, like proposed in this paper: Shape-based image retrieval using generic Fourier descriptor

see how they FD parameterize the apple perimeter detection? Same idea like your door.

BTW, I'm pretty sure mapping the whole schematic to polar coordinates won't help rotational invariance- you would need to do that about the centroid of each door, which is exactly what your problem is to begin with. That is why I think you want to just capture door candidates, and maybe map those to polar coordinates to match with the FD door template, like done in that paper linked above.

let me know how it goes if you try this approach.

Answer 4

Perhaps you'll find this Matlab code I wrote useful: Fractal Mosaics

It implements the paper "Robust Image Registration Using Log-Polar Transform" (pdf) in an artistic application that required more robustness than the traditional methods I found.