# 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://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.

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

-
welcome to dsp.SE. We'll try to help you, but providing more precise info would be nice. What do you mean by SIFT and SURF "failed totally"? What did they detect/match? Also, I personally don't know about Log-Polar Template Matching, but, if you tried, where exactly the problem was? –  penelope Dec 6 '12 at 13:50
The SIFT and SURF feature detections did't find any features in the template image. It seemd as the template has too less information (just that little bow and a line). For the Log-Polar matching I found a paper where it's described, but not the exact math behind it. I'll search it and add it. –  Arndt Bieberstein Dec 6 '12 at 13:56
Hey, not a lot of people here can understand German, I think :D But, for everything else: you can edit you own post to add any new information in the right place, instead of in the comments. And, also, you still didn't say what exactly you had problems with. –  penelope Dec 6 '12 at 14:40
The author of "german Article" has article in English - www-cs.engr.ccny.cuny.edu/~wolberg/pub/icip00.pdf (thanks to google) –  SergV Dec 7 '12 at 3:32

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 = im(:,:,1);
template = template(:,:,1);

blobs = regionprops(template>0,'Area','Image');
largestBlob = GetLargestBlob(blobs);

figure;
subplot(1,2,2);imshow(edgeImage); title('Template');

end

cx  = c.Centroid(1);
cy  = c.Centroid(2);

[y,x] = find(edgeImage);
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

-
I guess this it not working with non-closed shapes? Or do i just skip these "holes" in the shape. –  Arndt Bieberstein Dec 12 '12 at 9:10
@ArndtBieberstein, Yep it works only for closed shapes. I guess there should be some method to extend it. –  Andrey Dec 12 '12 at 14:36
Since OpenCV doesn't contain the bwtraceboundary function i wrote my own and just "skipped" the holes and filled with zeros. Here's a little example how the results now look. 5 Plots for each template. The red dot's are the Starting points. Sample Plot –  Arndt Bieberstein Dec 12 '12 at 14:54
@ArndtBieberstein, very nice! Maybe you could share the results with us once you are done. –  Andrey Dec 12 '12 at 15:35
Sure, the Code isn't that nice or performant, but it work's. I'll attach it below my Question. It's written in C# (I'm using EmguCV) –  Arndt Bieberstein Dec 12 '12 at 15:42

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.

-
This method sounds really promising! I can't open your link, but I googled your approach. I didn't know that SIFT that SIFT isn't completely rotation ivariant! Very good answer! +1 –  Arndt Bieberstein Dec 10 '12 at 8:14
I hardly found anything about Chamfer Distance and how it works, for those who are also searching for this try this link. –  Arndt Bieberstein Dec 12 '12 at 15:06

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.

-