Morphological operators that considerably improve the generalised hough transform

Hough Transform (HT) [5, 17] is one of the oldest and by far the most famous line detector. A conventional line equation can be represented as:

Where (m,b) defines the line. Instead, if we use the Hesse normal form, we can represent a line as:

where r is the distance of the closest point of the line to the origin. Using this representation, a line can be represented by (r, \(\Phi \)) in the Hough Space (HS). In this space, every (x,y) point on the line correspond to a sinusoid in the HS. It was proved that all of the sinusoids created by the pixels of a straight line intersects at a single point in the Hough Space and this intersection point gives us the line equation shown in (1). In order to find that intersection point, all of the sinusoidal curves belonging to each pixel of a line are drawn on the Hough Space. These sinusoids are accumulated or superimposed on the HS rather than being drawn. The result of this process should be sharp peaks at the intersection points. Unfortunately, the HS is implemented using two dimensional matrices, very much like a digital picture and in the discrete world of digital space, there are always 8 pixels surrounding the intersection point. Therefore, the sinusoids must pass through those 8 pixels twice, elevating their values as well. This creates a flat peak instead of a spike making it difficult to pinpoint the tip of the spike. Other factors such as discretization errors [20], noise [2], and pixels that are not connected to the line but happen to be along the path of the line also make the peaks flatter. If the line is short, then the peak will be already short to start with and it might get completely obscured by these detrimental effects.

(a) Two simple images with exactly same background but different size triangles. (b) Hough space images of the superimposed sinusoids corresponding to each pixel in (a). (c) 3-D representation of the Hough Transform demonstrating the change in the height of the peaks. Each peak correspond to one side of the triangle. The bottom picture demonstrates that the large triangle creates larger peaks

Full size image

An example that demonstrates the change in peak heights created by short and long lines is shown in Fig. 1. In the first column, (a), two simple 100\(\times \)100 pixel images are shown. These images have the same noise pixels, four small circles and five small squares at the background at exactly the same places. The only difference is the size of the triangles. The triangle in the lower picture is twice as long as the upper one. The intensity picture of the HT shown in column (b) shows that the peaks corresponding to each side of the triangle are much more intense. Three dimensional representation of the these peaks shown in column (c) demonstrates the difference between the heights of the peaks. Those three peaks obtained by Hough transforming the shorter triangle are almost obscured by the noise and small shapes while the ones belonging to the longer triangle are taller making them a lot easier to detect. Hough Transform’s use is not restricted to detection of lines. Any shape can be detected using the HT, circles being particularly popular, through the use of Generalized Hough Transform [4].

As shown in Fig. 2-a, the conventional method for using the HT is to employ an edge detector first. Usually Canny edge detector [3] is used because of its superior performance. The edge detector extracts the contours of the objects as on/off pixels and this edge data is processed by the HT line detector. However, if the image is low resolution, or if there are many short lines on the image, then the grayscale image can be stretched using the Bilinear Interpolation [22] or the Bicubic Interpolation [21]. Unfortunately when this method is used, the Canny edge detector must be applied to the stretched image resulting in a much longer processing time. For example, if the image is stretched twofold, then the edge detector must spend approximately four times longer to process the image. On the other hand, if the proposed method (shown in Fig. 2-c) is used, then the edge detector is applied to the original image. The proposed morphological operators are much faster than the edge detector therefore the overall processing time is shorter for the proposed method.

Image Stretching, magnification and up-sampling methods are old and well studied methods in the literature. The most frequently used ones being the bilinear and the bicubic interpolations. The bilinear interpolation fits a plane using four neighboring pixels and then uses that plane to up sample the image. The bicubic interpolation fits a curvy surface to 16 neighboring pixels and then uses that surface to up sample pixels. Bilinear interpolation is computationally simpler compared to the bicubic interpolation and the results are similar, therefore, throughout the experiments bilinear transformation will be used.

Another method to stretch the image is to apply morphological operators to the binary image obtained by applying the edge detector. Mathematical morphology can be defined as a theory and technique for the analysis of spatial structures, based on set theory, integral geometry and lattice algebra. This field was first introduced in 1964 by two French researchers, Serra and Matheron, while working on problems in mineralogy and petrography [12]. In order to analyze binary images, they introduced a set formalism, allowing the image objects to be processed by simple operations. These operations include as union, complementation, intersection and translation. In 1975, a seminal book entitled Random Sets and Integral Geometry was published, which have laid down the foundations of mathematical morphology [13]. After several decades of development, mathematical morphology has emerged as a popular tool for binary image processing.

Binary images consist of only black and white colors, using zeros to represent black areas and ones to represent white areas. In order to make these pictures work more efficiently with other algorithms, morphological operators are repeatedly used to improve these binary images or to manipulate them in order to make them work more efficiently with other algorithms. Three morphological operators proposed in this article are designed to enhance the line detectors. There are computationally simpler methods such as pixel replication. The simplest method is to use 4 pixels in the magnified image instead of one to achieve \(\times \)2 magnification and 9 pixels for \(\times \)3 magnification. While being very fast, this method creates jagged edges. Unfortunately, these images look very crude, because of those "jaggies".

Three different methods to perform the Hough Transform. (a) The conventional method. (b) Edge detector and HT are applied after the image is stretched using bilinear of bicubic transform. (c) Proposed method

Full size image

There are two different morphological approaches to binary image magnification in the literature. Ledda’s "mmINT" method [10] is the oldest one which uses pixel replication as the first step to enlarge the image. Naturally this creates jaggies. In order to correct them, he uses the "hit miss transform" to detect the corners created by the jaggies. His next step is to check these corners to see if they were created by jaggies. Real corners should not be smoothed therefore they are not processed. In order to remove the jaggies, he uses special masks, erosion and dilation operators, and smoothes them out in several iterations. Unfortunately these methods do not work well beyond magnification factor of \(\times \)2. For higher magnification factors, his method might yield holes in the magnified areas. Consequently, an extra iteration should be performed to remove those holes. Although this method produces quite good results, it requires several iterations on the magnified image and is computationally expensive. Wu [23] improved upon Ledda’s algorithm. Similar steps are used. First, he magnifies the image using the "pixel replication" or the "nearest neighbor" interpolation. He employs the hit and miss transform to detect corners. Then he smoothes those corners out using masks in several iterations.

None of these algorithms are suitable for line detection because they make edge pixels thicker. Feature extractor algorithms such as shape detectors or line detectors need the edge width to be single pixel. On top of that, these algorithms require multiple iterations on the upsampled image making them computationally demanding. The proposed algorithm is computationally simpler and faster, which makes it more desirable for real-time machine vision projects.

The stretch operator requires that the output of the edge detector to be thinned. The thinning, or the skeletonizing operator is a computationally exhaustive process which requires several dozen morphological operations. There are different kinds of morphological thinning algorithms and most of them use the hit and miss transform with several different masks and perform several iterations. For example the Stentiford thinning algorithm [18] uses four different masks. Each mask must be applied to the binary image one by one which makes this algorithm very slow. Unfortunately the worst part is that this process must be iteratively continued until the skeletonization is achieved. Another thinning algorithm is Zhang-Suen algorithm [26] which uses two iterations. However, every iteration requires complex decisions and calculations, and the results contain jaggies.

(a)Transformations of the special thinning operator. (b)A simple demonstration of the Stretch operator. All 8 pixels centered around an "on" pixel is copied to the stretched image. (c)A set of hit and miss transformations that define the smooth operator

Full size image

The special thinning algorithm proposed in this article is much simpler because it assumes that the input image is created by a gradient based edge detector such as the Canny edge detector. The output of such algorithms are never thicker than two pixels because the detector finds the maxima of the gradient. Under such conditions a much simpler morphological operator can be applied, and it is only performed once. Figure 3-a shows the masks used for the hit-and-miss transform. Note that the operator alters the image only if the the target pixel (the middle of the 3\(\times \)3 pattern) is on. For the off pixels, it does not waste any processing power at all. The other advantage is that it doesn’t need to create another copy of the image, it can directly modify the original copy without altering the unprocessed pixels. Figure 4-c demonstrates the results of the special thinning operator on the Canny edge detector implemented using the OpenCV library.

The stretch operator is a one-step operator that stretches the edge pixels while magnifying them by a factor of x3. Let P be the set of pixels in the original image and R be the stretched image. In that case, the stretch operator s is a function from P to R:

The interpretation of this function is quite simple: If a pixel is white, then that pixel and the surrounding 8 pixels are copied to the image R at a location three times the coordinates of that pixel. Note that if the center pixel is the tip point of an edge its x and y coordinates are simply multiplied by three. That is very important because after detecting the lines or shapes on stretched image, we need to recover their positions on the original image. The only disadventage of this operator is the small artifacts it creates around the edges that have 90 degree or less angle. This is demonstrated in Fig. 2-b. Fortunately, these artifacts have no effect on shape detectors because their size is only one pixel.

An example demonstrating all steps of the morphological stretch. (a)An image with simple geometric shapes. (b) Canny edge detector result. (c) Result of the Special Thinning operator. (d) Three times stretched using the Stretch operator. (e) Result of the Smooth operator

Full size image

(a) The "Iron Bridge." (b) The ground truth obtained by ULD (c) Standard HT applied to the image. (d) Standard HT applied to \(\times \)3 stretched image using the Bilinear Transform. (e)SHT applied to the image that was morphologically stretched using the proposed method

Full size image

The stretch operator causes jaggedness in a similar way the magnification operators do which were mentioned in Section 2. Therefore, this jaggedness must be removed. A simple hit and miss transform that detects eight 3\(\times \)3 pixel shapes is used. Once it detects one of those 8 shapes, it replaces them with a slightly different shape as shown in Fig. 3-c. This operator modifies the image only if the target pixel, the one in the middle of the 3\(\times \)3 pattern, is on. Otherwise it does not do any processing. Therefore, it is computationally much simpler compared to the smoothing operator employed by mmINT [10]. Note that the smooth operator does not alter the tip points of any of the 8 shapes it transforms. Figure 4 shows the effects of stretching and smoothing on several simple geometric shapes. Figure 4-d shows three times stretched versions of the geometric shapes shown in Fig. 4-c. Notice the jaggedness on these larger shapes. Figure 4-e demonstrates how that jaggedness is reduced by using the smooth operator.

In order to test the proposed morphological operators, The Standard Hough Transform (SHT) implementation [16] inside the OpenCV library is used. This implementation is probably the most frequently used one because of the popularity of the OpenCV platform. For the original size images, the parameters that were recommended by the OpenCV web site, (PI/180,150,0,0), were used. For both bilinear and morphological stretch methods, (PI/180,200,0,0) yields better results because all of the lines are stretched three times. Figure 5 shows the results of this algorithm on the "Iron Bridge" image that has a resolution of 400\(\times \)546 pixels. In order to obtain the ground truth, Ultrafast Line detector (ULD) [24] in mode-2 is used. In that mode, this algorithm detects lines by matching pixel patterns and therefore, it is impossible for the algorithm to detect false lines. The lines detected by ULD are printed green on top of the Canny edge detector result. Black pixels belong to edges that are ignored by the ULD and the green pixels belong to straight line segments. There are 84 lines in the ground truth image. The original method (SHT) shown in Fig. 5-c detects 21 lines. After using the Bilinear Transformation to stretch the image three times, the standard HT detects 121 lines. Figure 5-d clearly shows that although there are many more correctly detected lines, there are also many false detections due to multiple detections of the same line. This occurs because of the jagged edge lines. In this example, the number of false detections are so high that the result of this approach is unusable.

Figure 5-e shows the result of the standard HT using the morphological operators proposed in this article. Using this method, the HT detects 31 lines. It is %50 more successful than the original method. It did not detect as many lines as the bilinear transformation method (Fig. 5-d) but it did not have any false detections neither. The reader must keep in mind that the line coordinates obtained through this approach are correct for the stretched image. If they try to use those line parameters on the original image the results will be wrong. They must be converted to the geometry of the original image. Fortunately, the HT implementation in the OpenCV library outputs the line parameters in polar coordinates as (r,theta). In order to convert these parameters back to the geometry of the original image, all we have to do is divide r by three.

(a) "Office-5" image. (b) Ground truth obtained by Ultrafast Line Detector. (c) KHT applied to (a). (d) SHT applied to (a). (e) KHT on BT stretched img. (f)SHT on BT stretched img. (g)SHT on morphologically stretched img. (h)KHT on morphologically stretched img

Full size image

As shown in Fig. 5-d, the Standard HT suffers from multiple detection of the same line. The causes of that problem was explained in detail in Section 1. If the lines are too short, the peaks generated by the HT will not be tall enough to be detected. On the other hand, if they are too long, the peaks will have many secondary peaks around them which might cause multiple detections. This phenomena is explained in detail in Fernandes and Oliveira’s article [6]. In order to tackle this problem, they first segment collinear edge pixels and then apply an elliptical Gaussian envelope in the Hough domain to detect peaks. They call this method the Kernel based Hough Transform (KHT). Unlike many other Hough Transform researchers, the authors bravely published their source code as well, making it possible for other researchers to benefit from their algorithm. Experiments show that they have significantly reduced the number of multiple detections. Although not shown here, when applied to the bilinear stretched version of the "Iron Bridge" image shown in Fig. 5, there are almost no multiple detections. On the other hand, Fig. 5-d proves that the standard HT creates great number of multiple detections. Figure 6 shows the results of the KHT when applied to the Office-5 image. The Office-5 image comes with the Matlab program. The ground truth shown in Fig. 6-b is obtained with Ultrafast Line Detector (ULD) im mode-2. Note that the KHT requires an input argument from the user: Maximum number of lines to be detected in the image. For all of the images in Fig. 6, that number was kept at 30. Those 30 lines are always the longest lines in the pictures whether they were stretched or not. That explains why the results are so similar. Figure 6-d shows huge amount of multiple detections created by the Standard HT. For both the original and the proposed methods, there seems to be no multiple detections. For the one that uses bilinear stretching (Fig. 6-g), there are a couple of extra detections on the aluminum window frame. The bilinear stretch method detected the lines created by the edge of the books. However, careful inspection shows that the books on the top and bottom shelves are not aligned meaning that they do not create the longest lines in the picture. On the other hand, the bilinear stretch method (Fig. 6-h) successfully detected the edges of the computer screen. Overall, experiments with other images show that results of bilinear stretching is slightly superior to the proposed morphological streching method. That is caused most probably by the raggedness introduced by the stretch operator. If the Gaussian envelope of the KHT were adjusted to accommodate for the flatness of the peaks caused by that raggedness, the results would have been superior. Note that, as shown in Fig. 6-g, when used with the morphological stretch operator, even the Standard HT performs almost as well as the KHT. This is especially remarkable because the result of the SHT on bilinear stretched image (Fig. 6-f) is worst than Fig. 6-d.

As mentioned in the previous sections, the HT creates equations of infinitely long lines. It does not tell where the lines start and end. The algorithms that identify these end points are called Line Segment Detectors. Traditionally, line segment detectors used pixel chaining algorithms that group edge pixels and then use a line fitter such as the least squares to fit a line to as many neighboring edge pixels as possible. However, in the last ten years or so, the new HT designs also started identifying the end points of the lines they detect, blurring the distinction between a "line detector and a "line segment detector." Over the years, hundreds of different HT variants have been published. According to the latest survey [14], there are more than two hundred articles published on different HT variants, unfortunately, only several of those articles published their code or implementation. When the authors of a popular line-segment detector, the EDLines [1], compare the results of their algorithm with the PHT, they revealed that, PHT is less than %20 successful.

(a) Three natural images of 640\(\times \)480 resolution. (b) Ground truth obtained by the Ultrafast Line Detector. (c)PHT applied to the Canny edge detected images. (d) PHT applied to the Canny edge detected images that are \(\times \)3 stretched using bilinear transform. (e) Results of the PHT using the proposed method

Full size image

The HT depends on the height of the peaks produced by the sinusoids created by each pixel on a line. This means that its success rate increases with the increasing length of the lines. The stretch and the smooth operator combination introduced in the previous chapters should accomplish that purpose. By stretching the lines three times, it should drastically improve the detection rate of the HT without adding too much computating overhead. Figure 7-c demonstrates the lines detected by the Probabilistic Hough Transform (PHT) [9] on natural images. These images are downloaded from the web site of the authors of "CannyLines" [11]. CannyLines is a line segment detector and the authors of that article use these images to evaluate the performance of their algorithm against other line detectors. In order to process these images with the PHT, the edge data must be extracted using the Canny edge detector. The same input parameters were used for the Canny edge detection for all of the examples shown in this article. According to the web site of OpenCV [15], the PHT implementation needs four input arguments. Despite the fact that the OpenCV web site recommends (PI/180,50,50,10), as input parameters to the PHT, it has been observed that (PI/180,40,40,6) works better for the examples used in this work. In reality, for every individual picture, there should be a special set of optimum parameters. Unfortunately, using a distinct set of input arguments for every individual picture would kill the objectivity of the tests. For general purpose Computer Vision applications, it is impractical to change the input parameters for every different picture. In order to maintain objectivity, same input arguments are used for all of the tests. On the other hand, after the application of morphological operators, because of the increased resolution of the stretched edge image, the input arguments of the PHT are slightly increased. The parameters are elevated to (PI/180, 40\(\times \)1.25,40\(\times \)1.25,6\(\times \)3). In other words, the second and third parameters are multiplied by 1.25 and the fourth parameter is tripled to get the maximum benefit from stretching. The same parameters were also used for the images shown in Fig. 7-d which were stretched using the bilinear transformation. The PHT detection results are shown in Fig. 7-e after the images have been stretched by using the Stretch and Smooth morphological operators. The success rate of Probabilistic HT is far superior on these morphologically stretched images. Note that all of the line coordinates were divided by three before drawing them back on Figs. 7-d and 7-e, to ensure that the detected lines are converted back to the geometry of the original (unstretched) images.

Table 1 shows the number of lines detected using each method. As expected, stretched images perform much better. However, while majority of the lines detected using the bilinear transform are multiple false detections, there are almost no multiple false detections using the morpholgical stretch.

The HT was modified to detect arbitrary shapes [4] ten years after its first publication. Circles and ellipses are the second most popular use of Hough Transform to detect shapes. The OpenCV library contains an implementation of the Circular Hough Transform (CHT) called the "HoughCircles" (HC). There are different approaches for detecting circles, however, currently only Yuen’s method [25] has been implemented. The most common issues about the circular Hough Transform is its failure to detect small circles and to detect false circles when there isn’t any. The CHT implementation of the OpenCV library requires several input arguments. The first two arguments are not very important because they are the thresholds for the edge detector CHT uses. In order to apply the Stretch and Smooth operators, we need to apply our own edge detector. Other than those, there are three more input arguments that define the range of the size of the circles that can be detected. The first input argument defines how near the centers of the detected circles can be. That argument is same for all of the experiments and is half of the image height. The rest of the parameters are the range of the radius of the circles that we wish to detect. Round objects in our pictures have radiuses larger than 5 pixels and smaller than 60 pixels. Naturally for the triple stretched images, those parameters should be 15 and 180. These arguments are kept the same throughout the experiments. Figure 10 demonstrates the results of the original, bilinear stretched and morphologically stretched images. The circles detected by the CHT are drawn using the color white.

The top picture shows different kinds of screw heads. This is an example of non overlapping circular objects. Without applying the morphological operators, the original HoughCircles can detect only nine of them. If the picture is stretched using the bilinear transformation, the CHT can detect 18 of them. On the other hand, the proposed method detects all of the 21 screw heads. The middle picture in Fig. 8-a with many pills is an example of overlapping round objects. This example demonstrates the superiority of the proposed method over the other two by detecting almost three times the number of circles. The bottom picture in Fig. 8-a shows oranges that are obscured by the leaves of the tree. The proposed method not only detects more oranges, but also have less false detections, proving that these morphological operators should become a standard part of Hough Transform based detection.

(a) From top to bottom: images with non-overlapping, overlapping and obscured round objects and ground truth.(b) HC applied to the Canny edge detected images. (c) HC applied to the Canny edge detected images that are \(\times \)3 stretched using BT. (d) Results of PHT using the proposed method

Full size image

Table 2 shows success rates of these algorithms on the pictures shown in Fig. 8 and five other pictures in our dataset. In order to obtain a relative sense of the success rate, Jaccard Index is used. Conventional success measures such as accuracy, precision or loss functions can not be applied here because there are infinite number of True Negatives (TN). On the other hand the Jaccard index is defined as the ratio of True Positives (TP) to Positives (P) plus False Positives (FP), { TP/(P+FP) }.

All of the proposed operators work on binary edge images. Let us assume that there are M "off" pixels and N "on" pixels in a binary image. The pseudo code for the Special Thinning operator is:

Special Thinning.

Full size image

Therefore, this algorithm requires (M+N) conditional operations at the third line, between N\(\times \)2 and N\(\times \)8 conditional operations at the fourth line depending on which pattern it recognizes first, and then N operations at line five. Note that this algorithm assumes that it is being applied to the output of an edge detector. As a result, it does not check the off pixels. The readers must make the necessary changes to the code to should they decide to use this operator for some other purpose. The total operations performed are between M+N\(\times \)4 and M+N\(\times \)10. On the average, it should be M+N\(\times \)7. Note that there are also M+N operations for scanning the image (outside double "for loops"), which will not be mentioned for the rest of the algorithms. There are also invisible operations because of using a 2D array. Accessing an element of a 2D array requires at least one addition and one multiplication depending on the data type. However, traditionally these are usually not included in the complexity analysis because such details fall in to the realm of compiler design science. For the Stretch operator, the code is simpler:

Stretch.

Full size image

The third line of this pseudo code performs M+N operations, and the fourth line performs N\(\times \)9 copy operations. However, each copy operation accesses two 2D arrays and one of the arrays require multiplication of 3 for both coordinates and plus an addition on the average which means that the actual number of operations are at least M+N\(\times \)73.

Smooth.

Full size image

Again the third line requires M+N operations and the fourth line require between N\(\times \)2 and N\(\times \)16 operations. The last two lines require another N\(\times \)2 operations bringing the total between M+N\(\times \)5 and M+N\(\times \)19.

Success rate of algorithms when applied to the Circular Hough Transform; measured using the Jaccard Index

Full size image

The executable program that performs these experiments shown in this article has been published on Github [7]. This program has a very easy to use graphical user interface (GUI). It also has an option to test the time it takes to process the edge images using Stretch and Smooth operators. The tests were performed on a below average speed computer, an i7-9750H CPU running at 2.6 GHz using a 64 bit Windows 10 operating system. The example images were either processed 1000 times or 200 times (for CHT) and then the total processing time was converted to milliseconds per image. The results shown in Tables 3, 4, 5 and 6 prove that these morphological operators are %30 faster compared to other approaches and are very suitable for real-time image processing. The author has also publicly shared the executable, the data set, the source code and the Visual Studio project files [7] so that the reader can take adventage of these operators in their research projects.

In this article three new morphological operators have been introduced:

Special Thinning operator is a computationally efficient way of thininning the binary edge images. Not only it helps reducing false detections when used with the HT, but also can be used with many other algorithms that require thinning of an edge detector output.

Stretch and Smooth operators are computationally efficient way of improving the results of Generalised Hough Transform by stretching binary edge images three times.

When applied together, these operators increased the success rate of the SHT and PHT by both removing all of the false detections and increasing the true detection rate %50. While these operators have almost no effect on the success rate of the KHT, they have increased the True Positive (TP) rate of the Circular HT %50 and decreased False Positive (FP) rate %56 compared to the bilinear stretching. On top of those, these operators are %30 faster than bilinear stretching. Therefore, the author recommends these operators to be included inside the OpenCV library because it makes no sense not to use them. Figure 9 plots Jaccard indexes of the experiments shown in Table 2, proving that, when used with the CHT, these operators are always more successful than other approaches.

Recently a new approach has emerged for detecting lines using the HT. Convolutional Neural Networks (CNN) are being used to process Hough peaks in the Hough Domain [8]. Although the authors have published their code, because it was written in Python, the C++ code presented in this article could not be integrated to theirs for testing. This type of HT line detectors became quite popular for wiremframe parsers but unfortunately, CNN based approaches are much slower compared to the classical HT methods, therefore other authors improved upon this method [19, 27]. However, these authors either not published their code or published it in Python again. To test the performence of proposed operators on these new approaches, the C++ code will be converted to Python in the future.