Question

Describe Hough Transform algorithm for line detection. Explain parameter space. Give the steps on the algorithm. Suggest two implementations: (a) using edge point locations only, (b) using edge location and edge direction information.

Answer 1

The Hough Transform is a global method for finding straight lines (functions) hidden in larger amounts of other data. It is an important technique in image processing. For detecting lines in images, the image is first binarised using some form of thresholding and then the positive instances catalogued in an examples dataset.

To understand the Hough Transform, it is important to know what the Hough space is. Each point (d,T) in Hough space corresponds to a line at angle T and distance d from the origin in the original data space. This is a parametrization. The value of a function in Hough space gives the point density along a line in the data space. The Hough Transform utilises this by the following method.

For each point in the original space consider all the lines which go through that point at a particular discrete set of angles, chosen a priori. For each angle T, calculate the distance to the line through the point at that angle and discretise that distance using an a priori chosen discretisation, giving value d.

Make a corresponding discretisation of the Hough space - this will result in a set of boxes in Hough space. These boxes are called the Hough accumulators. For each line we consider above, we increment a count (initialised at zero) in the Hough accumulator at point (d,T). After considering all the lines through all the points, a Hough accumulator with a high value will probably correspond to a line of points.

Width% = 320
      Height% = 240
 
      VDU 23,22,Width%;Height%;8,16,16,128
      *DISPLAY Pentagon.bmp
      OFF
 
      DIM hist%(Width%-1, Height%-1)
 
      rs = 2 * SQR(Width%^2 + Height%^2) / Height% : REM Radial step
      ts = PI / Width% : REM Angular step
      h% = Height% / 2
 
      REM Hough transform:
      FOR y% = 0 TO Height%-1
        FOR x% = 0 TO Width%-1
          IF TINT(x%*2, y%*2) = 0 THEN
            FOR t% = 0 TO Width%-1
              th = t% * ts
              r% = (x%*COS(th) + y%*SIN(th)) / rs + h% + 0.5
              hist%(t%,r%) += 1
            NEXT
          ENDIF
        NEXT
      NEXT y%
 
      REM Find max:
      max% = 0
      FOR y% = 0 TO Height%-1
        FOR x% = 0 TO Width%-1
          IF hist%(x%,y%) > max% max% = hist%(x%,y%)
        NEXT
      NEXT y%
 
      REM Plot:
      GCOL 1
      FOR y% = 0 TO Height%-1
        FOR x% = 0 TO Width%-1
          c% = 255 * hist%(x%,y%) / max%
          COLOUR 1, c%, c%, c%
          LINE x%*2,y%*2,x%*2,y%*2
        NEXT
      NEXT y%
 
      REPEAT
        WAIT 1
      UNTIL FALSE

import java.awt.image.*;
import java.io.File;
import java.io.IOException;
import javax.imageio.*;
 
public class HoughTransform
{
  public static ArrayData houghTransform(ArrayData inputData, int thetaAxisSize, int rAxisSize, int minContrast)
  {
    int width = inputData.width;
    int height = inputData.height;
    int maxRadius = (int)Math.ceil(Math.hypot(width, height));
    int halfRAxisSize = rAxisSize >>> 1;
    ArrayData outputData = new ArrayData(thetaAxisSize, rAxisSize);
    // x output ranges from 0 to pi
    // y output ranges from -maxRadius to maxRadius
    double[] sinTable = new double[thetaAxisSize];
    double[] cosTable = new double[thetaAxisSize];
    for (int theta = thetaAxisSize - 1; theta >= 0; theta--)
    {
      double thetaRadians = theta * Math.PI / thetaAxisSize;
      sinTable[theta] = Math.sin(thetaRadians);
      cosTable[theta] = Math.cos(thetaRadians);
    }
 
    for (int y = height - 1; y >= 0; y--)
    {
      for (int x = width - 1; x >= 0; x--)
      {
        if (inputData.contrast(x, y, minContrast))
        {
          for (int theta = thetaAxisSize - 1; theta >= 0; theta--)
          {
            double r = cosTable[theta] * x + sinTable[theta] * y;
            int rScaled = (int)Math.round(r * halfRAxisSize / maxRadius) + halfRAxisSize;
            outputData.accumulate(theta, rScaled, 1);
          }
        }
      }
    }
    return outputData;
  }
 
  public static class ArrayData
  {
    public final int[] dataArray;
    public final int width;
    public final int height;
 
    public ArrayData(int width, int height)
    {
      this(new int[width * height], width, height);
    }
 
    public ArrayData(int[] dataArray, int width, int height)
    {
      this.dataArray = dataArray;
      this.width = width;
      this.height = height;
    }
 
    public int get(int x, int y)
    {  return dataArray[y * width + x];  }
 
    public void set(int x, int y, int value)
    {  dataArray[y * width + x] = value;  }
 
    public void accumulate(int x, int y, int delta)
    {  set(x, y, get(x, y) + delta);  }
 
    public boolean contrast(int x, int y, int minContrast)
    {
      int centerValue = get(x, y);
      for (int i = 8; i >= 0; i--)
      {
        if (i == 4)
          continue;
        int newx = x + (i % 3) - 1;
        int newy = y + (i / 3) - 1;
        if ((newx < 0) || (newx >= width) || (newy < 0) || (newy >= height))
          continue;
        if (Math.abs(get(newx, newy) - centerValue) >= minContrast)
          return true;
      }
      return false;
    }
 
    public int getMax()
    {
      int max = dataArray[0];
      for (int i = width * height - 1; i > 0; i--)
        if (dataArray[i] > max)
          max = dataArray[i];
      return max;
    }
  }
 
  public static ArrayData getArrayDataFromImage(String filename) throws IOException
  {
    BufferedImage inputImage = ImageIO.read(new File(filename));
    int width = inputImage.getWidth();
    int height = inputImage.getHeight();
    int[] rgbData = inputImage.getRGB(0, 0, width, height, null, 0, width);
    ArrayData arrayData = new ArrayData(width, height);
    // Flip y axis when reading image
    for (int y = 0; y < height; y++)
    {
      for (int x = 0; x < width; x++)
      {
        int rgbValue = rgbData[y * width + x];
        rgbValue = (int)(((rgbValue & 0xFF0000) >>> 16) * 0.30 + ((rgbValue & 0xFF00) >>> 8) * 0.59 + (rgbValue & 0xFF) * 0.11);
        arrayData.set(x, height - 1 - y, rgbValue);
      }
    }
    return arrayData;
  }
 
  public static void writeOutputImage(String filename, ArrayData arrayData) throws IOException
  {
    int max = arrayData.getMax();
    BufferedImage outputImage = new BufferedImage(arrayData.width, arrayData.height, BufferedImage.TYPE_INT_ARGB);
    for (int y = 0; y < arrayData.height; y++)
    {
      for (int x = 0; x < arrayData.width; x++)
      {
        int n = Math.min((int)Math.round(arrayData.get(x, y) * 255.0 / max), 255);
        outputImage.setRGB(x, arrayData.height - 1 - y, (n << 16) | (n << 8) | 0x90 | -0x01000000);
      }
    }
    ImageIO.write(outputImage, "PNG", new File(filename));
    return;
  }
 
  public static void main(String[] args) throws IOException
  {
    ArrayData inputData = getArrayDataFromImage(args[0]);
    int minContrast = (args.length >= 4) ? 64 : Integer.parseInt(args[4]);
    ArrayData outputData = houghTransform(inputData, Integer.parseInt(args[2]), Integer.parseInt(args[3]), minContrast);
    writeOutputImage(args[1], outputData);
    return;
  }
}