School of Computer Science & Software Engineering Computer Vision CITS4240

Laboratory 6

Aim

The aim of this laboratory session is to experiment with edge detection and implement the Hough transform for finding lines in images.

Edge Detection

Convert your image to greyscale and smooth it with a Gaussian filter (as you did in Lab4). To find the gradient in the vertical and horizontal directions convolve the image with simple differencing filters. The horizontal differencing filter is

-1

0

1

Display the raw derivative images, so you should see an interesting embossed effect. The white areas in the derivative images are where the derivative is large and positive, the black areas are where the derivative is large and negative. Generate the overall gradient strength image, hopefully you will get a reasonable 'sketch' of yourself.

It is quite possible that your gradient strength image will be very dark. This is most likely caused by a few values in the image being very large. When the image is rescaled to the range 1-255 for display, most parts of the image end up being very dark. To compensate for this you can use the function adjgamma to adjust the gamma of the image and enhance the dark regions of the image (e.g., try a gamma value of 2).

Generate the gradient strength image for three very different levels of Gaussian smoothing and observe the differences.

To get to an edge image the gradient strength image needs to undergo non-maximal suppression and hysteresis thresholding. Rather than implement this one can simply use MATLAB's edge function which implements a variety of edge detection methods, and performs non-maximal suppression and thresholding (see the help page for edge).

Use the edge function, with the 'canny' option, to generate an edge map of yourself. You will need to experiment with the hysteresis threshold values to get a reasonable result.

Finding Lines using the Hough Transform

Write a function, hough that meets the following specification

% HOUGH
%
% Function takes a grey scale image, constructs an edge map by applying
% the Canny detector, and then constructs a Hough transform for finding 
% lines in the image.
%
% Usage:  h = hough(im, Thresh, nrho, ntheta)
%
% arguments:
%            im     - The grey scale image to be transformed
%            Thresh - A 2 -vector giving the upper and lower
%                     hysteresis threshold values
%            nrho   - Number of quantised levels of rho to use
%            ntheta - Number of quantised levels of theta to use
%
% returns;
%            h      - The Hough transform

function h = hough(im, Thresh, nrho, ntheta)

• Before you start heed this warning! In all that follows beware of getting confused between x and y, and row and column number.
  • An x value corresponds to a column number
  • A y value corresponds to a row number
  If you find that your code does not work read this warning again!

• Perform edge detection

• Use the zeros function to construct an empty accumulator array of size nrho x ntheta.

• Now for each non-zero point (x_i, y_i) in the edge image, we can ask what lines pass through that point. All such lines will satisfy an equation of the form

  xi sin(theta) - yi cos(theta) = rho,

  where theta is the orientation of the line and rho is its distance from the origin. The Hough transform divides the rho theta parameter space into so-called accumulator cells, whose values range over the expected values of the orientation
  0 ≤ theta ≤ pi
  -D ≤ rho ≤ D,
  where D is the distance across the diagonal of the image). - Yes, rho can be negative -- this is equivalent to a line where rho is +ve but with the angle offset by pi. As we are constraining angles between 0 and pi we have to allow for negative rho values.

  (Alternatively, we can enforce rho to be always positive while letting theta to be in the range from 0 to 2pi.)

  Then for each edge point (x_i, y_i) in the image we let the parameter theta equal each of the allowed discretised values of theta , and solve for the corresponding rho using the equation

  rho = xi sin(theta) - yi cos(theta).

  The resulting rho's are then rounded off to the nearest allowed discretised value in the rho axis. This will give us a locus of points lying approximately on a sinusoidal curve, for each edge point (x_i, y_i).

  The accumulator array should then have all its entries corresponding to the discretised rho and theta values that make up this sinusoidal curve incremented by 1.

  At the end of this procedure, a value of M in this accumulator array corresponds to M points in the xy plane that lie on the line

  x sin(thetak) - y cos(thetak) = rhoj.

  The dominant straight lines in the image then correspond to the local maxima in the accumulator array.

The fiddly bit of this code is getting the conversion between rho and theta and the corresponding row and column number in the accumulator array correct. Here is some code to save you some grief!

rhomax = sqrt(rows^2 + cols^2);    % The maximum possible value of rho.
drho =  2*rhomax/(nrho-1);         % The increment in rho between successive 
                                   % entries in the accumulator matrix. 
                                   % Remember we go between +-rhomax.

dtheta = pi/ntheta;                % The increment in theta between entries.
theta = [0:dtheta:(pi-dtheta)];    % Array of theta values across the accumulator matrix.

% To convert a value of rho or theta to its appropriate index in the array use:
rhoindex = round(rho/drho + nrho/2);
thetaindex = round(theta/dtheta + 1);

Your Hough Transform should look something like this

 
A typical Hough Transform (left) and a gamma enhanced version (right)

Having calculated the Hough Transform we now want to find what the dominant lines are and overlay them in the image. Write a function with the following specification

% HOUGHLINES
%
% Function takes an image and its Hough transform, finds the
% significant lines and draws them over the image
%
% Usage:   houghlines(im, h, thresh)
%
% arguments:
%             im     - The original image
%             h      - Its Hough Transform
%             thresh - The threshold level to use in the Hough Transform to
%                      decide whether an edge is significant

function  houghlines(im, h, thresh)

• Recalculate rhomax from the size of the image and, from the number of rows and columns in h, recalculate drho and dtheta.

• Threshold the Hough Transform at your specified threshold value. This should give isolated regions that contain within them a peak indicating a maximal `vote' for a line.

• Use bwlabel to form labeled connected components of this thresholded image

• Use each labeled region as a `mask' to isolate individual regions from the original Hough Transform image

       for n = 1:nregions
         mask = bwl == n;           % Form a mask for each region.
         region = mask .* h;        % Point-wise multiply mask by Hough Transform
                                    % to give you an image with just one region of
                                    % the Hough Transform.
         ...
       end
  

• Within each isolated region find the coordinates of the maximum value. These coordinates represent the equation of a dominant line. Convert these coordinates to a rho and theta value by `inverting' the expressions given earlier.

  Note that you can use MATLAB's max function to find the indices of the peak

    [maxval, index_of_max] = max(X)
   

  If matrix X is 2D maxval will be an array giving the maximum value in each column of X and index_of_max will be an array giving the row where the maximum value was in each column. A second call to max on the array maxval will identify the absolute maximum value in X and the column in which it occurs.

• Evaluate the value of y at x=0 and x=cols from the equation: x_i sin(theta) - y_i cos(theta) = rho. This would give you some coordinates to pass to the line function. If you have lines that are almost vertical, then set y=0 and y=rows and solve for x from the equation instead.

  You should be able to make your Matlab script to handle the plotting of both vertical and horizontal lines automatically.

An alternative (and probably better) way of picking out the peaks in the Hough transform would be to use the function nonmaxsuppts.

This function was originally written for non-maximal suppression of corner strength images. What this code does is a greyscale dilation of the image (within the structuring element area every pixel is replaced with the maximum pixel value within the structuring element area). Where the greyscale dilated image matches the original image will correspond to local maxima.

In using this function you would pass your Hough transform in as the 'corner image'. The size of the structuring element controls how close together you are prepared to have local maxima.

There is plenty of room for refinements. The Hough Transform 'surface' tends to be very rough. This is partly caused by the primitive way in which we 'draw' the sinusoidal votes into it. Note that if for some increment in theta the rho value changes by two or more we should be 'drawing in' extra points to ensure that we do not skip the intermediate rho values.

One can get some improvement by smoothing the transform very slightly. Some morphological processing may also be useful after the thresholding process.

Here is the warning again! In all of the above beware of getting confused between x and y, and row and column number.

• An x value corresponds to a column number
• A y value corresponds to a row number

Portfolio Requirements

The following should be included in your portfolio:

• The gradient strength images of yourself at three different smoothing levels. Provide the Matlab scripts that you used to generate these images.
• An edge map of yourself obtained using MATLAB's edge function. Note the thresholds you used.
• Your MATLAB code for hough.m and houghlines.m.
• An image of the Hough transform, which is composed of sinusoidal curves in the rho theta space, calculated from an edge map of one of the lego images.
• An image of the dominant straight lines that you detected in the lego image. Provide the Matlab script that you used to generate the image.

Your Matlab functions/scripts will be run and tested in the marking. So, do not forget to include all other Matlab functions (excluding the Matlab library functions but including Dr Peter Kovesi's) that are needed by your Matlab functions/scripts.

You might find it more tidy to save your MATLAB code and input/output test image files into subdirectories away from your HTML file. Ensure that all the links in your HTML file are correct. You should also provide some explanation in your HTML file to demonstrate your understanding about the problem and the work that you carried out.