Hough transformations

So far, we looked at how to detect edges and corners in an image. Sometimes, for image analysis apart from edges and corners, you want to detect shapes, such as lines, circles, ellipses, or any other shape for that matter. Say for example, you want to detect coins in an image, or you want to detect a box or a grid in an image. A technique that comes handy in such scenarios is Hough transformations. It is a widely used technique that detects shapes in an image using their mathematical equations in their parameterized forms.

The generalized Hough transformation is capable of detecting any shape for which we can provide an equation in the parameterized form. As the shapes start getting complex (with an increase in the number of dimensions), such as spheres or ellipsoids, it gets computationally expensive; hence, we generally look at standard Hough transformations for simple 2D shapes, such as lines and circles.

In this section, we will take a look at Hough transformations to detect lines and circles, but as mentioned earlier, it can be further extended to detect shapes, such as ellipses, and even simple 3D shapes, such as spheres.

Hough lines

Detecting lines is one of the simplest use cases of Hough transformations. In Hough lines, we select a pair of points from our image (x1, y1) and (x2, y2), and solve the following pair of equations for (a, m):

y1 = m(x1) + a

y2 = m(x2) + a

We maintain a table with two columns (a, m) and a count value. The count value keeps a record of how many times we get the (a, m) value after solving the preceding pair of equations. This is nothing but a voting procedure. After calculating the (a, m) values for all possible pairs of points, we take the (a, m) values that have count values greater than a certain threshold and these values are the desired lines in the image.

Note

For Hough transformations, we never run the algorithm directly on the image. First, we compute the edges in the image, and then apply the Hough transformation on the edges. The reason being, any prominent line in the image has to be an edge (the reverse is not true, every edge in the image will not be a line), and using only edges, we are reducing the number of points on which the algorithm runs.

OpenCV provides two implementations of Hough lines: standard Hough lines and probabilistic Hough lines. The major difference between the two is that, in probabilistic Hough lines, instead of using all edge points, we select a subset of the edge points by random sampling. This makes the algorithm run faster since there are fewer points to deal with, without compromising on its performance.

Time to write some code! First things first, add a new Hough lines menu option to our application menu. However, try to figure out the code to do this yourself this time.

Hopefully, the menu option is now in place! Let's now take a look at a code snippet that uses the probabilistic Hough transformation to detect lines in an image using OpenCV for Android:

void HoughLines()
    {

        Mat grayMat = new Mat();
        Mat cannyEdges = new Mat();
        Mat lines = new Mat();

        //Converting the image to grayscale
        Imgproc.cvtColor(originalMat,grayMat,Imgproc.COLOR_BGR2GRAY);

        Imgproc.Canny(grayMat, cannyEdges,10, 100);

        Imgproc.HoughLinesP(cannyEdges, lines, 1, Math.PI/180, 50, 20, 20);

        Mat houghLines = new Mat();
        houghLines.create(cannyEdges.rows(),cannyEdges.cols(),CvType.CV_8UC1);

        //Drawing lines on the image
        for(int i = 0 ; i < lines.cols() ; i++)
        {
            double[] points = lines.get(0,i);
            double x1, y1, x2, y2;

            x1 = points[0];
            y1 = points[1];
            x2 = points[2];
            y2 = points[3];

            Point pt1 = new Point(x1, y1);
            Point pt2 = new Point(x2, y2);

            //Drawing lines on an image
            Core.line(houghLines, pt1, pt2, new Scalar(255, 0, 0), 1);
        }

        //Converting Mat back to Bitmap
        Utils.matToBitmap(houghLines, currentBitmap);
        loadImageToImageView();

    }

As explained earlier, we first compute edges in the image using any edge detection technique (the preceding code uses Canny). The output of the Canny Edge detector is used as an input to the Imgproc.HoughLinesP() function. The first and second parameters are input and output respectively. The third and fourth parameters specify the resolution of r and theta in pixels. The next two parameters are the threshold and minimum number of points that a line should have. Lines with fewer points than this are discarded.

The For loop in the code is used to draw all the lines on the image. This is only done to visualize the lines detected by the algorithm.

Hough circles

Analogous to Hough lines, Hough circles also follow the same procedure to detect circles, only the equations change (the parameterized form of a circle is used instead).

Here is an implementation of Hough circles using OpenCV for Android:

void HoughCircles()
    {
        Mat grayMat = new Mat();
        Mat cannyEdges = new Mat();
        Mat circles = new Mat();

        //Converting the image to grayscale
        Imgproc.cvtColor(originalMat,grayMat,Imgproc.COLOR_BGR2GRAY);

        Imgproc.Canny(grayMat, cannyEdges,10, 100);

        Imgproc.HoughCircles(cannyEdges, circles, Imgproc.CV_HOUGH_GRADIENT,1, cannyEdges.rows() / 15);//, grayMat.rows() / 8);

        Mat houghCircles = new Mat();
        houghCircles.create(cannyEdges.rows(),cannyEdges.cols(),CvType.CV_8UC1);

        //Drawing lines on the image
        for(int i = 0 ; i < circles.cols() ; i++)
        {
            double[] parameters = circles.get(0,i);
            double x, y;
            int r;

            x = parameters[0];
            y = parameters[1];
            r = (int)parameters[2];

            Point center = new Point(x, y);

            //Drawing circles on an image
            Core.circle(houghCircles,center,r, new Scalar(255,0,0),1);
        }

        //Converting Mat back to Bitmap
        Utils.matToBitmap(houghCircles, currentBitmap);
        loadImageToImageView();
    }

The code is pretty much the same as Hough lines with a few changes. The output of Imgproc.HoughCircles() is a tuple of center coordinates and the radius of the circle (x, y, radius). To draw circles on the image, we use Core.circle().

Tip

A nice coding exercise would be to implement Hough lines/circles without using the predefined OpenCV functions.