The purpose of our project was to pick out in an 2-dimensional image
a red circle of any size. To accomplish this we have decided to use
the Hough transform which can find where in an image different types of
shapes lie.
We chose to use Matlab for its excellent graphing functions, ease of
coding, and because we both have not had much experience using it.
We chose not to use C or C++, which is the language which we are very use
to, and use almost every day.
Because most data is stored internally as an intensity at a
point, we need to convert these values into useful information for the
viewer. Two functions which provide this are Colorize and Greyscale.
Colorize
The colorize function takes in a two-dimensional array of double precision
floating point numbers, scaled between zero and one, and converts them
to a full color image. In the output image, low intensity (0) corresponds
to blue, medium intensity (0.5) corresponds to green, and high intensity
(1) corresponds to red. The transition from low to medium to high is calculated
in a linear fashion, which can be seen in the file colorize.m
.
r = x * cos(a) + y * sin(a)
where r is the length of the normal from the origin to this
line and a and a is orientation of r with respect
to the x-axis. For the transform you have to test a whole series
of different a's depending on how accurate you want your transform
to be. Obviously, the more accurate you want, the slower the process
will take. When you want to use the Hough transform for a circle,
you would simply use a formula like:
r2 = (x - a)2 + (y - b)2
where a and b are the co-ordinates of the centre of the circle,
and r is the radius. The difference between applying the line
and the circle transform, is that instead of testing for different values
of a, we test for different radii r. As you can see
in the diagram below, we first test for different angles:
...and then test for different radii. For both the line and circle
transforms, the resultant image if going to have a huge spike, either where
the (a, r) point or at (a, b) respectively. So, for our resultant
images you will notice huge spikes where the centre of the circle is.
Images (two-dimensional arrays with a floating point value at each location)
are converted into three-dimensional arrays, with dimensions corresponding
to the X and Y position of the center point of the circle and the Radius
of the circle. From this data, it is simply a matter of finding the element
in the array which has the maximum value, and mapping it back into a two-dimensional
circle corresponding to that maximum value.
The first thing we do is to read the image from the file using
the command imread. This command reads in JPEG files by splitting
up the image into its red, green and blue components, and each of those
3 images is read into a separate 2-dimensional array. Now, since
we have chosen specifically to find red circles in the image, we must remove
all other colours to have a resultant 2-dimensional image of just red.
This has been solved by making a section of code to go through each pixel
of the image and apply the following equation:
img(x,y) = red - green - blue
This will basically leave the pixel which have a majority of red.
This removes a lot of the data that we don't need, and makes our transform
work much more reliably. This section of code also makes the value
at each pixel between 0 and 1, as initially the values are between 0 and
255. Therefore, the result is a 2-dimensional array which have values
between 0 and 1.
Function: Test Circle: testcirc.m
Before I go and explain the main section of code which does the Hough transform,
I will explain the other routines that make the Hough transform work.
There is a function that we have called 'testcirc', which is defined as
follows:
function [count, total] = testcirc(x, y, r, img,
func)
The main role of this function is to test how visible a circle is at a
given point on the array. The input variable, 'x' and 'y', specify
the point on the array where we want to test, and 'r' is the circles radius
we are testing for. The variable 'img' is the actual 2-dimensional
array of the image so the function can test different points on the image,
and 'func' has the circle function data store in it, which I will explain
further on.
The way this function works, is to go around the circumference of a
circle, testing points to see how intense they are and storing the results
in a variable. The way this is done is by using a formulae for a
circle to draw a circle on the screen. Instead of drawing the pixel
the screen, we add the intensity/value at that pixel to a running total.
The formulae is first generated in the main file and passed on to the
'circfunc' as an array of numbers. Originally the formulae was generated
inside 'circfunc', but since this function is called for every pixel in
the image, it was decided to move the generation part in the main file
and just pass on the resultant array to the function. Therefore the
generation only needs to happen however many different radii are to be
tested, rather than how many pixels there are in the image.
The two return values are the running total, and a count of how many
pixels tested. The count is used so that we can work out an average
number, not just a non-relative number. For example, if we have a
running total of 5.5 for two different radii, one small and one large.
The smaller radius will have only tested a smaller number of pixels and
relative to the count, the result should be high, but with a larger radius,
the result should be poor relative to the count.
The first few lines of code read:
% First we test for radii RMIN to RMAX
for r = RMIN:RMAX,
r
% These next few lines of
code are to
% calculate the circle formulae
values
maxY = fix(r*cos(pi/4));
for y = 1:(maxY),
x=round(sqrt((r^2)-(y^2)));
circfunc(y)=x;
end
...
end
This main loop has a FOR loop which tests for all radii between RMIN and
RMAX as defined earlier in the program. The reason why we test each
radii first is because we only have to calculate the formulae for the circle
once for each radius we test. Originally, for each pixel on the screen
we tested all radii, so test each radii was done last. This was found
to be very slow, especially when testing for radii past 20. Inside
this first loop, we calculated the formulae to be sent to the circfunc,
which was done by using the Pythagorean theorem. The next loop is:
for currX = r+1:(DIMX-r),
...
end
This FOR statement loops around the 'x' axis, between the values (r + 1)
and (DIMX - r), as you cannot test values which are beyond the dimensions
of the array. The next loop is:
for currY= r+1:(DIMY-r),
...
end
This loop is similar to the previous except in loops around the values
of 'y', between (r + 1) and (DIMY - r). Now, for all radii between
RMIN and RMAX, we test all the pixels on the image, using the 'circfunc',
as described previously.
Using the Results:
The result from the main loop is a whole set of images/arrays for each
radius tested. We now have to scale all the values in the array to
values between 0 and 1, so we can display them in the way we want.
We do this by executing the code below:
%scale data between 0 and 1
res = res - min(min(min(res)));
res = res / max(max(max(res)));
After this we have to reshape the images each into their own single 2-dimensional
image, so they can be output to the screen and also to a series of files.
The whole purpose of this Hough transform was to pick out a red circle
in an image, so our result should be a new image with the circle
that we have found. We have to find where the maximum value/intensity
is in the many arrays of images. To do this we use the 'find'
command which finds where a certain value is in a multi-dimensional array
of data. The maximum value in the array will be simply 1, as the
array has been scaled between the values 0 and 1. The result from
this is basically the image which has found the circle closest to the one
we are looking for, and also the 'x' and 'y' positions of where the
centre of the circle is.
We can now use these values found to create a new image which has gotten
rid of all the error and distortion in the image and is left solely with
the circle we were looking for. The next section in our documentation
will go through the results we have in detail and explain what the results
mean.
