Image Processing 2008/09 - Solution 6

Frederik Kaster (exemplary solution)

Exercise 1: Circle detection with the Hough transform (10 points)
Exercise 2: RANSAC for circle detection (10 points)
Further reading

Exercise 1: Circle detection with the Hough transform (10 points)

In this exercise we detect circles using the Circle Hough transform cht, where we assume the radii as previously known.

coins = double(imread('coins.png'))/255;
figure; imagesc(coins); axis equal tight off; colormap gray;
title('US 5ct. and 1ct. coins');

We measure a radius of 25 pixels for the 1 cent coins and 30 pixels for the 5 cent coins. In an industrial quality control setting, we could also have calculated that from the product specifications and the imaging geometry.

szImg1 = size(coins);
rad1ct = 25;         % radii to be searched (in pixels)
rad5ct = 30;
gradthr = 0.15;
opt = 'prop';
[haa1ct,grad] = cht(coins,rad1ct,gradthr,opt);
figure; imagesc(grad); axis equal tight off; colormap gray;
title('Edge strengths from Sobel filtering');
figure; imagesc(haa1ct); axis equal tight off; colormap gray;
title('Circle Hough transform with a radius of 25 pixels (proportional)');
[haa5ct] = cht(coins,rad5ct,gradthr,opt);
figure; imagesc(haa5ct); axis equal tight off; colormap gray;
title('Circle Hough transform with a radius of 30 pixels (proportional)');
opt = 'const';
[haa1ctcnst] = cht(coins,rad1ct,gradthr,opt);
figure; imagesc(haa1ctcnst); axis equal tight off; colormap gray;
title('Circle Hough transform with a radius of 25 pixels (constant)');
[haa5ctcnst] = cht(coins,rad5ct,gradthr,opt);
figure; imagesc(haa5ctcnst); axis equal tight off; colormap gray;
title('Circle Hough transform with a radius of 30 pixels (constant)');

The results of the "constant" and the "proportional" variant are roughly similar, but as can be seen below, the distribution of local maxima is considerably sparser if the constant version is chosen. Now, find local maxima (i.e. all pixels whose value exceeds those of all its neighbors in an 8-neighborhood) by the function findmaxima, impose a suitable threshold and display the results using the function draw_circles.

max1ct = findmaxima(haa1ct);
haa1ctmax = max1ct .* haa1ct;
% use a surface plot in order to choose a suitable threshold
figure; surf(haa1ctmax);
xlabel('X axis');
ylabel('Y axis');
title('Local maximum intensity of CHT (radius 25, proportional)');
haa1ctmax = haa1ctmax > 20;
% plot the results
[yhaa1ct,xhaa1ct] = find(haa1ctmax);
rhaa1ct = rad1ct*ones(size(yhaa1ct));
imgWithHaa1ct = draw_circles(coins,xhaa1ct,yhaa1ct,rhaa1ct);
figure; image(imgWithHaa1ct); axis equal tight off;
title('1 ct coins as detected by CHT with proportional edge strength');
max1ctcnst = findmaxima(haa1ctcnst);
haa1ctcnstmax = max1ctcnst .* haa1ctcnst;
% use a surface plot in order to choose a suitable threshold
figure; surf(haa1ctcnstmax);
xlabel('X axis');
ylabel('Y axis');
title('Local maximum intensity of CHT (radius 25, constant)');
haa1ctcnstmax = haa1ctcnstmax > 80;
% plot the results
[yhaa1ctcnst,xhaa1ctcnst] = find(haa1ctcnstmax);
rhaa1ctcnst = rad1ct*ones(size(yhaa1ctcnst));
imgWithHaa1ctcnst = draw_circles(coins,xhaa1ctcnst,yhaa1ctcnst,...
    rhaa1ctcnst);
figure; image(imgWithHaa1ctcnst); axis equal tight off;
title('1 ct coins as detected by CHT with constant edge strength');
max5ct = findmaxima(haa5ct);
haa5ctmax = max5ct .* haa5ct;
figure; surf(haa5ctmax);
xlabel('X axis');
ylabel('Y axis');
title('Local maximum intensity of CHT (radius 25, proportional)');
haa5ctmax = haa5ctmax > 20;
[yhaa5ct,xhaa5ct] = find(haa5ctmax);
rhaa5ct = rad5ct*ones(size(yhaa5ct));
imgWithHaa5ct = draw_circles(coins,xhaa5ct,yhaa5ct,rhaa5ct);
figure; image(imgWithHaa5ct); axis equal tight off;
title('5 ct coins as detected by CHT with proportional edge strength');
max5ctcnst = findmaxima(haa5ctcnst);
haa5ctcnstmax = max5ctcnst .* haa5ctcnst;
figure; surf(haa5ctcnstmax);
xlabel('X axis');
ylabel('Y axis');
title('Local maximum intensity of CHT (radius 25, constant)');
haa5ctcnstmax = haa5ctcnstmax > 80;
[yhaa5ctcnst,xhaa5ctcnst] = find(haa5ctcnstmax);
rhaa5ctcnst = rad5ct*ones(size(yhaa5ctcnst));
imgWithHaa5ctcnst = draw_circles(coins,xhaa5ctcnst,yhaa5ctcnst,...
    rhaa5ctcnst);
figure; image(imgWithHaa5ctcnst); axis equal tight off;
title('5 ct coins as detected by CHT with constant edge strength');

We can see that although the use of proportional edge strength accumulation leads to more spurious local maxima, the overall effects on detection accuracy are beneficial since strong edges contribute more than weak edges: hence the CHT value is in this case a better predictor if there is really an edge.

Exercise 2: RANSAC for circle detection (10 points)

We detect circles with the function ransac_circle and tune the parameters to detect the traffic sign in the test image. In contrast to the previous exercise, we introduce no knowledge at all about the circle (except for a lower bound since we do not want to find very small "circles" which are usually spurious).

trafficSign = double(rgb2gray(imread('trafficSign6.jpg')))/255;
szImg2 = size(trafficSign);
gradthr = 0.2;
eps = 1.5;          % margin widths (pixels)
ransacthr = 0.45;   % at least so many edge pixels must lie within margin,
                    % fraction of 4*pi*r*eps
nIter = 15000;      % number of iterations allowed
lowerRadius = 5;    % we are not interested in pathologically small circles
nTrials = 10;       % since this is a randomized method we should conduct
                    % several trials to make sure the traffic sign is
                    % reliably found

We have a slight perspective distortion in this image, which is the reason why the outline of the sign is not captured exactly.

for iTrial=1:nTrials,
    [xCircle,yCircle,rCircle,grad] = ransac_circle(trafficSign,gradthr,eps,...
        ransacthr,nIter,lowerRadius);
    % plot the circles found by RANSAC
    circleSign = draw_circles(trafficSign,xCircle,yCircle,rCircle);
    figure; image(circleSign); axis equal tight off;
    title(['Traffic sign detection: trial no. ' num2str(iTrial)]);
end;

In a real world setting, there are several possible improvements which ought to be added:

This image was prepicked for minimal perspective foreshortening. In real-world examples, the circular traffic signs are normally imaged as ellipses and should also be detected as such (which can be done completely analogously using RANSAC, with the only difference that five instead of three points are needed for uniquely determining an ellipse, for determining the coordinates of the two focal points and the semimajor axis).

Especially if the pictures are taken from vehicles, we encounter motion blurring which needs to be removed first.

We have thrown away all information about the gradient direction: for a circle, the gradient should only point in the direction of the circle center or opposite to it. By additionally posing this constraint, we may remove many false positives (this can also be employed for the Hough transform).

More sophisticated edge detection methods like the Canny detector are preferable to simple Sobel-type

If several circles are found very close to each other (as in our test examples), they are probably due to thick edges: then only the best fit should be kept and the rest discarded.

Image Processing 2008/09 - Solution 6

Contents

Exercise 1: Circle detection with the Hough transform (10 points)

Exercise 2: RANSAC for circle detection (10 points)

Further reading