computer vision - Scale and Rotation invariant Template Matching

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 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

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('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