Feature extraction by shape matching - Feature Extraction and Image Processing - page 182

%Hough Transform for Circles

function HTCircle(inputimage,r)

%image size
[rows,columns]=size(inputimage);

%accumulator
acc=zeros(rows,columns);

%image
for x=1:columns
for y=1:rows
if(inputimage(y,x)==0)
for ang=0:360
t=(ang*pi)/180;
x0=round(x-r*cos(t));
y0=round(y-r*sin(t));
if(x0<columns & x0>0 & y0<rows & y0>0)
acc(y0,x0)=acc(y0,x0)+1;
end
end
end
end
end

Code 5.5 Implementation of the Hough transform for circles

to (i). We can see that the HT has the ability to tolerate occlusion and noise. Note that we
do not have the earlier problem with the start and the end of the lines since the circle is a
closed shape. In Figure 5.11 (c), there are many edge points which implies that the amount
of processing time increases. The HT will detect the circle (provide the right result) as long
as more points are in a circular locus described by the parameters of the target circle than
there are on any other circle. This is exactly the same performance as for the HT for lines,
as expected, and is consistent with the result of template matching.
In application code, Bresenham's algorithm for discrete circles (Bresenham, 1977) can
be used to draw the circle of votes, rather than use the polar implementation of Equation
5.32. This ensures that the complete locus of points is drawn and avoids the need to choose
a value for increase in the angle used to trace the circle. Bresenham's algorithm can be used
to generate the points in one octant, since the remaining points can be obtained by reflection.
Again, backmapping can be used to determine which points contributed to the extracted
circle.
An additional example of the circle HT extraction is shown in Figure 5.12 . Figure
5.12 (a) is again a real image (albeit, one with low resolution) which was processed by
Sobel edge detection and thresholded to give the points in Figure 5.12 (b). The circle
detected by application of HTCircle with radius 5 pixels is shown in Figure 5.12 (c)
superimposed on the edge data. The extracted circle can be seen to match the edge data
well. This highlights the two major advantages of the HT (and of template matching): its
ability to handle noise and occlusion . Note that the HT merely finds the circle with the