In this article by Amgad Muhammad, the author of OpenCV Android Programming By Example, we will see a famous shape analysis technique called the Hough Transform. You will learn about the basic idea behind this technique, which made it very popular and widely used.

Detecting shapes

We have seen how to detect edges; however, this process is a pixel-by-pixel process that answers the question whether this pixel is an edge or not. Moving forward in shape analysis, we would need more concrete information than just the edge test; we will need better representation.

For example, if we have a picture of a box and we did the edge detection, we will end up with thousands and thousands of edge pixels; however, if we tried to fit a line to these edge pixels, we will get a rectangle that is more symbolic and is a useful representation.

Understanding the Hough line transform

There are many ways to fit a line through a number of points and Hough transform is considered the underconstrained method where we use only one point to find all the possible lines that can go through this point. We use another point to also find all the lines that can go through it and we keep doing this for all the points that we have.

We end up with a voting system where each point is voting for a line and the more points laying on the same line, the higher the votes given to this line. In a nutshell, the Hough transform can be described as mapping a point in space to the parameter space of the shape of interest.

With the equation of a line in the x and y space, , we transform it to the slope (a) and intercept space (b) and with this transformation, a point in the x and yspace is actually a line in the slope and intercept space with the equation :

Insert image_4584_03_07.png

Here we have five points in the x and y space (left). When converted to the slope and intercept space, we get five lines (right):

Insert image_4584_03_08.png

Now, every point in the x and y space will vote for a slope and intercept in the slope and intercept space, so all we have to do is find the maxima in the parameter space and this will be the line to fit our points:

Insert image_4584_03_09.png

In the right image, you can find the maxima value based on the votes of the points in the left image, and in the left image you can see that maxima is the slope and intercept of the line fitting the points.

In the case of vertical lines, the slope is infinity; that's why it is more practical to use the polar equation of a line instead of the slope and intercept form. In this case, the equation that we will work with is and again, we have two parameters, and , and we will follow the same idea except that now the space is and instead of the slope and intercept:

Insert image_4584_03_10.png

We will follow the voting system to find the maxima, which represents the and of the line fitting our points. However, this time, a point in the and space will be sinusoid, and if two or more sinusoids intersect at the same and , this means that they belong to the same line:

Insert image_4584_03_11.png

You can see the Hough transform in action using the applets at http://www.rob.cs.tu-bs.de/teaching/interactive/.

Detecting lines using Hough transform

In OpenCV, we have two implementations of the Hough line transform:

The standard Hough transform: The process is pretty much following the preceding process; however, it is considered the slower option as the algorithm has to examine all the edge points in a given image.
The probabilistic Hough line transform: This option is the one that we will use in our example. In the probabilistic version, the algorithm attempts to minimize the amount of computation needed to detect lines by exploiting the difference in the fraction of votes needed to detect the lines. Intuitively, for strong/long lines, we only need a small fraction of its supporting points to vote before deciding if the accumulator bin reaches a count that is non-accidental; however, for shorter lines, a higher portion is needed to decide this. In conclusion, the algorithm tries to minimize the number of edge points that are needed to decide on the fitting line.

UI definitions

We will add a new item menu to start the Hough transform algorithm. Go to the res/menu/soft_scanner.xml file and open it to include the following item menu:

<item android_id="@+id/action_HTL"

android_enabled="true"

android_visible="true"

android_title="@string/action_HL">

</item>

Detecting and drawing lines

The process to use the Hough line transform is divided in four steps:

Load the image of interest.
Detect image edges using Canny; the output will be a binary image.
Call either the standard or probabilistic Hough line transform on the binary image.
Draw the detected lines.

In SoftScanner Activity, we need to edit the onOptionesItemSelected method and add the following case:

else if(id==R.id.action_HTL)

{

if(sampledImage==null)

{

Context context = getApplicationContext();

CharSequence text = "You need to load an image first!";

int duration = Toast.LENGTH_SHORT;

Toast toast = Toast.makeText(context, text, duration);

toast.show();

return true;

}

Mat binaryImage=new Mat();

Imgproc.cvtColor(sampledImage,
binaryImage,Imgproc.COLOR_RGB2GRAY);

Imgproc.Canny(binaryImage, binaryImage, 80, 100);

Mat lines = new Mat();

int threshold = 50;

Imgproc.HoughLinesP(binaryImage, lines, 1, Math.PI/180,
threshold);

Imgproc.cvtColor(binaryImage, binaryImage,
Imgproc.COLOR_GRAY2RGB);

for (int i = 0; i < lines.cols(); i++)

{

double[] line = lines.get(0, i);

double xStart = line[0],

yStart = line[1],

xEnd = line[2],

yEnd = line[3];

org.opencv.core.Point lineStart = new
org.opencv.core.Point(xStart, yStart);

org.opencv.core.Point lineEnd = new
org.opencv.core.Point(xEnd, yEnd);

Core.line(binaryImage, lineStart, lineEnd, new
Scalar(0,0,255), 3);

}

displayImage(binaryImage);

return true;

}

The code is actually straightforward, as follows:

if(sampledImage==null)

{

Context context = getApplicationContext();

CharSequence text = "You need to load an image first!";

int duration = Toast.LENGTH_SHORT;

Toast toast = Toast.makeText(context, text, duration);

toast.show();

return true;

}

We first handle the case if the user clicks the item menu and didn't load an image:

Mat binaryImage=new Mat();

Imgproc.cvtColor(sampledImage, binaryImage,
Imgproc.COLOR_RGB2GRAY);

Imgproc.Canny(binaryImage, binaryImage, 80, 100);

Then, we initialize a new Mat object and convert the loaded image from the full color space to the grayscale space. Finally, we call Imgproc.Canny to convert the grayscale image to a binary image with only the edges displayed:

Mat lines = new Mat();

int threshold = 50;

Imgproc.HoughLinesP(binaryImage, lines, 1, Math.PI/180, threshold);

The next step is to call Imgproc.HoughLinesP, which is the probabilistic version of the original Hough transform method, passing in the following parameters:

A Mat object representing the binary image version of the loaded image
A Mat object to hold the detected lines as the parameters
A double for the resolution, in pixels, of the parameter, ; in our case, we set it to one pixel
A double for the resolution, in radians, of the parameter, ; in our case, we set to it to one degree,
An integer for the accumulator threshold to return only the lines with enough votes

Usually, when using the probabilistic version of the Hough transform, you would use a smaller threshold because the algorithm is used to minimize the number of points used to vote. However, in the standard Hough transform, you should use a larger threshold.

Imgproc.cvtColor(binaryImage, binaryImage, Imgproc.COLOR_GRAY2RGB);

for (int i = 0; i < lines.cols(); i++)

{

double[] line = lines.get(0, i);

double xStart = line[0],

yStart = line[1],

xEnd = line[2],

yEnd = line[3];

org.opencv.core.Point lineStart = new
org.opencv.core.Point(xStart, yStart);

org.opencv.core.Point lineEnd = new
org.opencv.core.Point(xEnd, yEnd);

Core.line(binaryImage, lineStart, lineEnd, new Scalar(0,0,255), 3);

}

displayImage(binaryImage);

Finally, we convert the binary image to a full color space to display the detected lines and then we loop on the detected lines' Mat object columns and draw them one by one using the parameters, :

Insert image_4584_03_15.png

Hough lines (in blue) detected from the edge image

Detecting circles using Hough transform

OpenCV provides another implementation of the Hough transform, but this time, instead of detecting lines, we will detect circles following the same idea of transforming the space to the parameters space.

With an equation of a circle, ,we have three parameters, ; where a and b are the centers of the circle in the x and y direction, respectively, and r is the radius.

Now, the parameter space is three-dimensional and every edge point belonging to a circle will vote in this three-dimensional space; then we search for the maxima in the parameter space to detect the circle center and radius.

This procedure is very memory- and computation-intensive and the three-dimensional space will be very sparse. The good news is that OpenCV implements the circle Hough transform using a method called Hough gradient method.

The Hough gradient method works as follows: in step one, we will apply an edge detector, for example, the Canny edge detector. In step two, we will increment the accumulator cells (two-dimensional space) in the direction of the gradient for every edge pixel. Intuitively, if we are encountering a circle, the accumulator cell with higher votes is actually that circle's center. Now, we have built a list of potential centers and we need to find the circle's radius so we will—for every center—consider the edge pixels by sorting them according to their distance from the center and keep a single radius that is supported (voted for) by the highest number of edge pixels:

Insert image_4584_03_14.jpg

UI definitions

To trigger the circle Hough transform, we will add one item to our existing menu. Go to the res/menu/soft_scanner.xml file and open it to include the following item menu:

<item android_id="@+id/action_CHT"

android_enabled="true"

android_visible="true"

android_title="@string/action_CHT">

</item>

Detecting and drawing circles

The process of detecting circles is similar to the process of detecting lines:

Load the image of interest.
Convert it from a full color space to a grayscale space.
Call the Hough circle transform method on the grayscale image.
Draw the detected circles.

We will again edit onOptionsItemSelected to handle the circle Hough transform case:

else if(id==R.id.action_CHT)

{

if(sampledImage==null)

{

Context context = getApplicationContext();

CharSequence text = "You need to load an image first!";

int duration = Toast.LENGTH_SHORT;

Toast toast = Toast.makeText(context, text, duration);

toast.show();

return true;

}

Mat grayImage=new Mat();

Imgproc.cvtColor(sampledImage, grayImage, Imgproc.COLOR_RGB2GRAY);

double minDist=20;

int thickness=5;

double cannyHighThreshold=150;

double accumlatorThreshold=50;

Mat circles = new Mat();

Imgproc.HoughCircles(grayImage, circles,
Imgproc.CV_HOUGH_GRADIENT, 1,
minDist,cannyHighThreshold,accumlatorThreshold,0,0);

Imgproc.cvtColor(grayImage, grayImage, Imgproc.COLOR_GRAY2RGB);

for (int i = 0; i < circles.cols(); i++)

{

double[] circle = circles.get(0, i);

double centerX = circle[0],

centerY = circle[1],

radius = circle[2];

org.opencv.core.Point center = new
org.opencv.core.Point(centerX, centerY);

Core.circle(grayImage, center, (int) radius, new
Scalar(0,0,255),thickness);

}

displayImage(grayImage);

return true;

}

The code for the circle Hough transform is just as the one to detect lines except for the following part:

double minDist=20;

int thickness=5;

double cannyHighThreshold=150;

double accumlatorThreshold=50;

Mat circles = new Mat();

Imgproc.HoughCircles(grayImage, circles,
Imgproc.CV_HOUGH_GRADIENT, 1,
minDist,cannyHighThreshold,accumlatorThreshold,0,0);

Imgproc.cvtColor(grayImage, grayImage, Imgproc.COLOR_GRAY2RGB);

for (int i = 0; i < circles.cols(); i++)

{

double[] circle = circles.get(0, i);

double centerX = circle[0],

centerY = circle[1],

radius = circle[2];

org.opencv.core.Point center = new
org.opencv.core.Point(centerX, centerY);

Core.circle(grayImage, center, (int) radius, new
Scalar(0,0,255),thickness);

}

We detect circles by calling Imgproc.HoughCircles and passing to it the following parameters:

A Mat object representing the 8-bit, single-channel grayscale input image.
A Mat object that will hold the detected circles. Every column of the matrix will hold a circle represented by these parameters, .
An integer for the detection method and currently, OpenCV only implements the Hough gradient algorithm.
A double used as an inverse ratio of the accumulator resolution to the image resolution. For example, if we passed one, the accumulator has the same resolution as the input image. If we passed two, the accumulator is half the resolution of the input image.
A double for the minimum distance between the centers of the detected circles. If the parameter is too small, multiple neighbor circles may be falsely detected in addition to a true one. If it is too large, some circles may be missed.
A double used for the upper threshold for the internal Canny edge detector; as it will be half the upper one for the lower threshold.
A double for the accumulator threshold for the circle centers at the detection stage. The smaller it is, the more false circles may be detected.
An integer for the minimum radius to be detected; if unknown, pass zero.
An integer for the maximum radius to be detected; if unknown, pass zero.