A Review of Hough and Watershed Transform Algorithms

Table of Contents

I. Introduction

II Hough Transform

III Watershed Transform

IV Conclusions and Discussion

References

Hough and Watershed Transforms Algorithms Brief Review

Toquica Cáceres Hans Milos

Moreno Calderón Jose Luis

March 20,

Abstract —Patterns isolation is one of the bases of image processing and artificial intelligence algorithms as it is the key for image segmentation and posterior classification of objects. A brief review is performed in this document, regarding the Hough and watershed transforms algorithms, and in regards to its robustness to some conditions and implementations.

Index Terms —Hough transform, lines, circles, Hesse form, normal form, watershed transform, machine vision, segmenta- tion, polar coordinates.

I. INTRODUCTION

RECOGNITION and isolation of patterns is a very im- The Hough transform is a method used to isolate features of particular shape within an image. These features need to be in some parametric from for the transformation itself (exempli gratia lines, circles and ellipses).²

In order to perform the Hough transform, the image to be analyzed shall be filtered previously, in order to have a binary image and enhance its edges. This filtering process is usually done by means of applying a simple threshold followed by a Canny filter.

Then the parametric shape shall be defined; in general, the algorithm can be performed by only a feature at a time, id est, detecting only lines, or detecting only circles, or only R portant part of image processing and machine vision, ellipses, et cetera. it conforms the base to make a proper segmentation. Hough transformation is an algorithm used to determine parametric features in images and isolate them, whilst the watershed transform is an useful tool to isolate regions in images; both algorithms are commonly used in image segmentation.

Throughout this document, the reader will find the HOUGH TRANSFORM section in which a brief explanation of the Hough transform basic algorithm is presented, as well as some examples and the proposal to plot the accumulator space in polar coordinates as it might be useful for some applications, the WATERSHED TRANSFORM section where the algorithm is explained briefly and some examples are given, the CONCLUSIONS AND DISCUSSION and lastly, the REFERENCES, in case the reader would like to deepen in any subject.

II. HOUGH TRANSFORM

Paul Hough proposed a method and means for recognizing complex patterns, in order to recognize complex lines in photographs or other pictorial representations, particularly adaptable to the study of subatomic particle tracks passing through a viewing field (exempli gratia particles creating tracks along their path in a bubble chamber).¹ This patent, published in 1962, became what it is known now as the Hough Transform.

The choice of the parameters for the shape extraction is something that needs to be performed with care, exempli gratia, choosing the slope and intersect to parametrize a line might not be a smart choice, a better choice is to select a form of polar coordinates in order to parametrize this line. This is explained just about later.

The transformation is performed by moving from one parametric space to another (called accumulator), in this transformation the parameters are transformed in constants and vice versa. At the end, the accumulator will hold dense points which identify the desired feature in the base parametric space.

Exempli gratia, consider a line in R², this line can be represented with rectangular components with the slope and the intersect as the parameters, etiam, the line equation is unknown and the desired feature. The line equation is un- known, until a solution is found by applying the transform, but what it is important at this first stage is to establish a unique convention for this line, the convention should not be ambiguous. With the line equation convention established earlier in this paragraph, a line in R² is defined by:

illustration not visible in this excerpt

where m is the slope, b is the intersect, x is the independent component and y is the dependent component. From this representation of the line, the accumulator will be defined by the parameters of the line, as follows:

illustration not visible in this excerpt

Fig. 1: Example image space.

which defines a line in the accumulator space with parame- ters x which is the slope and the intersect is y, while m is the independent variable and b is the independent variable.

By now, there is a set of points in an image representing a feature to be isolated, in this case a line, as shown in Fig. 1 (remember than a piece of software like OpenCV takes increasing coordinates in the y axis from top to bottom, for the transform, there is no difference). Each of those points is converted to a line in the accumulator space, this conversion is made by means of selecting the coordinates of each point in the line (in the image space) and convert them in the slope and the intersect in the accumulator space, with this, the line in the accumulator shall be drawn. Note that this line represents the set of all the lines in the image space that can be traced passing through that point (because the x and y coordinates remain as constants in the accumulator space while m a b are changing).

This process is performed for several points on the line in the image, producing the same amount of lines in the accumulator space as points in the image space. Fig. 2 show the line plot for each of the points in the image space. Note that if a couple of lines cross in the accumulator space, it means that there are two points in the image space (corresponding to the lines crossing) that lie in a line in the image space with the parameters of the point in the accumulator space in which the lines are intersected. Ergo, from the accumulator space, the denser points are chosen (by means of using a value threshold). The values from the point in the accumulator space (its b and m values) are chosen and become the parameters of the line in the image space, as shown in Fig. 3.

illustration not visible in this excerpt

Fig. 2: Accumulator space with the Hough transform of the four points shown in Fig. 1; the denser point is highlighted.

illustration not visible in this excerpt

Fig. 3: Image space of Fig. 1 with the trace of the line with the parameters found in Fig. 2.

Another example is shown in Fig. 4, with points describ- ing a horizontal line, the Hough transform with rectangular coordinates performs beautifully, the accumulator space is shown in 5. The point found was b = 2, m = 0, id est a line with no slope and intersecting the y axis in 2.

By now, the Hough transform is able to perform properly with any line; Fig 6 shows a set of points that conform a vertical line, the accumulator space for such a set of points is shown in Fig. 7, note that this lines intersect in infinity, this is a problem, an equation describing the line is not possible to be obtained in a way that it does not affect the algorithm logic. It is not possible to determine vertical lines in the accumulator space by means of using the intersect and the slope.

In 1972 an article was published by Richard Duda and Peter Hart published an article (dated 1971) in which they “prefer the so-called normal parametrization” for a line in R².³ This “normal parametrization” somewhat corresponds

illustration not visible in this excerpt

Fig. 4: Example image space with horizontal line traced as a result of the accumulator space in Fig. 5.

illustration not visible in this excerpt

Fig. 5: Accumulator space with the Hough transform of the four points shown in Fig. 4; the denser point is highlighted.

illustration not visible in this excerpt

Fig. 6: Example image space with points describing a vertical.

illustration not visible in this excerpt

Fig. 7: Accumulator space with the Hough transform of the four points shown in Fig. 4; the denser point is highlighted.

illustration not visible in this excerpt

Fig. 8: A line and its normal in the image space.

to the vectorial Hesse normal form of a line.

A procedure to obtain the line equation with normal parameters can be easily deducted.⁴ Take, exempli gratia, the line in Fig. 8, its normal is traced to the origin, which corresponds to the minimum distance from the line to the origin, this distance is denoted by ρ, the angle between the horizontal and this line is denoted by θ.

For this line,

illustration not visible in this excerpt

Now remember the line equation with the slope and

illustration not visible in this excerpt

Fig. 9: Accumulator space with the Hough transform of the four points shown in Fig. 1; the denser point is highlighted. Transformation performed with normal parametrization of the line.

intersect as parameters,

illustration not visible in this excerpt

where a = OA, and b = OB, then

illustration not visible in this excerpt

The line equation with the normal parameters (id est the minimum distance from the origin to this line and the angle from the horizontal to the normal) is the Equation (2), whilst the accumulator space equation needed to perform the Hough transform is that shown in Equation (1), in this equation, the parameters are the x and y coordinates for a point in the image space.

In this order of ideas, Fig. 9 shows the accumulator space obtained for the example shown in Fig. 1 with the normal parametrization of the lines. Because what it is obtained is a series of periodic curves, a polar plot is suggested in this article, as shown in Fig. 10 and its detail in Fig. 11.

Taking the point suggested in the accumulator space, the line is plotted in Fig. 12, obtaining the line parametrized with the angle and the normal distance to the origin.

The same can be performed with a set of points describing a straight horizontal line, like those of Fig. 4, the normal parameters plot is shown in Fig. 13, its polar detail is shown in Fig. 14, and the resulting line plotted in the image space is that shown in Fig. 15.

illustration not visible in this excerpt

Fig. 10: Accumulator space with the Hough transform of the four points shown in Fig. 1; the denser point is highlighted. Transformation performed with normal parametrization of the line. Polar plot.

illustration not visible in this excerpt

Fig. 11: Fig. 10 detail.

illustration not visible in this excerpt

Fig. 12: Image space of Fig. 1 with the trace of the line with the parameters found in Fig. 9.

illustration not visible in this excerpt

Fig. 13: Accumulator space for the points in Fig. 4.

The time is now for the points describing a vertical line, note that Fig. 16 shows the accumulator space for these points with the line equation with normal parameters, whilst a detail of the polar form of this accumulator space is shown in Fig. 17, the result is plotted in Fig. 18, etiam, note that the deal of plotting this line is another task for the person using the Hough transform. Recalling the line equation with the normal parameters, it is had that

illustration not visible in this excerpt

as it is shown in Equation (2). When points describing a vertical line are transformed, the accumulator space will hold a dense point which marks a θ = 0°, when it is tried to plot the line with this parameter using the previously recalled equation, there could be problems, as the csc(0°) = ∞, as well as the cot(0°).

In the OpenCV documentation website, a clever way to deal with this kind of problem is shown in an algorithm,⁵

illustration not visible in this excerpt

Fig. 14: Accumulator space for the points in Fig. 4. Polar plot.

illustration not visible in this excerpt

Fig. 15: A line with the normal parameters found in Fig. 13 which contains all the points of Fig. 4.

as in Code 1, this brief algorithm returns a couple of points in the image by a dense point in the accumulator.

Code 1: Python implementation for obtaining line endpoints.⁵ a = np.cos(theta)

illustration not visible in this excerpt

If the feature to be identified is the circle, then it is important to recall the circle equation, which is

illustration not visible in this excerpt

Fig.16: Accumulator space for the points in Fig.6

illustration not visible in this excerpt

Fig. 17: Accumulator space for the points in Fig. 6. Polar plot.

illustration not visible in this excerpt

for a circle centered in the origin; then for a circle centered in the coordinates (h, k), a more general equation could be

illustration not visible in this excerpt

note that the parameters of this equation are h its origin x displacement, k its origin y displacement, and r its radius. This parameters lead to a three dimensional Hough trans- form accumulator space. This kind of accumulator space could lead to high computing times and the computer may be required to have a lot of processing capacity in order to perform this operation. A simpler accumulator space might

illustration not visible in this excerpt

Fig. 18: A line with the normal parameters found in Fig. 16 which contains all the points of Fig. 6.

illustration not visible in this excerpt

Fig. 19: Points in the image space poorly describing a circle

be obtained from taking the radius of the circle out of the way (assuming the r is known, ergo, r is not a parameter anymore, but a constant, instead).

Fig. 19 shows an example of points in the image space representing a circle, the circle is not evident at this stage.

Remember that the for the simpler Hough transform, the radius is known, for this example, the circle that it is tried to be found is a circle of radius r = 1. Recall that the Hough transformed is performed by means of converting the feature parameters in the image space into the variables in the accumulator space and vice versa.

Then, the transformation can be performed mathemati- cally as follows:

illustration not visible in this excerpt

Fig. 20: Hough transform accumulator space for the points shown in Fig. 19.

illustration not visible in this excerpt

from this latter expression note that the r is already known to take a value of 1, ergo, the expression for the accumulator space becomes

illustration not visible in this excerpt

From the points in the image space, the values of the parameters x and y can be replaced, and note this is an equation for a circle in the accumulator space, with x being the horizontal displacement from the origin and y being the vertical displacement from the origin; note that this circle also has r = 1.

Fig. 20 shows the accumulator space for the points in Fig. 19. The denser point setting the Fig. 19 circle parameters is highlighted. Finally, the circle is plotted in Fig. 21, note that the points selected to make the accumulator space are in the circle perimeter.

The accumulator space for a circle of unknown radius is three dimensional, and constitute the shape of a cone, as it is shown in Fig. 22.⁶

The Hough transform is, in general, robust to noise in the image, take for example the Fig. 23, note that the points in red are the points that are plotted in the accumulator space, note that although the accumulator space is somewhat affected by the noise, the denser point is selected by means of a threshold of the intensity in the accumulator image. With this information the line parameters provided by the previous to the last vignette are used to plot the line in the last vignette, which the noise didn’t affect the result at all.

illustration not visible in this excerpt

Fig. 21: Resulting circle with the parameters obtained.

illustration not visible in this excerpt

Fig. 22: Hough transform accumulator space for a circle with unknown radius. (Image edited in order to comply with this document guidelines).⁶

III. WATERSHED TRANSFORM

A. Watershed segmentation technique

The Watershed transform is a powerful morphological tool that allows the segmentation of complex structures that can not be processed by other conventional methods of digital image processing. This technique was introduced by C. Latuejoul as “watershed transformation” and later improved along with S. Beucher, and named “Watershed”.

This technique is based on segmentation procedures, based on mathematical morphology that allows to extract the borders of the regions of an image. This technique performs a partition of the image in gray levels to obtain another one formed by significant regions. It is clear then, that this technique uses other methods like borders, thresholding and regions growth.

The Watershed technique provides robust results for regions and boundaries and allows the incorporation of constraints based on the knowledge of the regions to be segmented.

illustration not visible in this excerpt

Fig. 23: Hough transform with noise. (Image edited in order to comply with this document guidelines).⁷

illustration not visible in this excerpt

Fig. 24: Likeness of the watersheed on a surface of a terrain.⁸

The gray level image can be seen as the topographic rep- resentation of a terrain, where each pixel is associated with a “height” value at its corresponding gray level (Fig. 24). Once this association is made, it begins with ”flood with water” the surfaces from the lower ”topographic” levels; It contin- ues to “flood” until the waters of continuous basins come together. The lines of union, representing the boundaries of homogeneous regions, are the result of segmentation. These pond boundaries correspond to Watersheds, which are continuous and result from segmentation. Therefore the aim of this technique is to find the Watershed lines.

The construction of Watershed lines is used in binary images by morphological dilatation, one of the simplest techniques to achieve this. One of the problems of this technique, is the excessive segmentation. This problem is characterized by the detection of an excessive number of regions, which is due to the noise that may have the original image and irregularities in the same, producing a large number of regions not desired or irrelevant to the analysis, a simple solution For this inconvenience it is to apply a filter that allows the elimination of the noise before performing the segmentation process.

In this type of algorithm it is necessary to implement a previous step to the segmentation. In the case of grayscale images, the concept of a zone contained within a contour refers to all points that, although close, there is no radical jump in the gray scale between them. Based on this starting point, the algorithm will begin with the detection of basic markers. These markers will be chosen among the local minimums of the image. From these the flooding process begins. After this step, each object that appears in the image must have a different associated marker.

Obtaining the water-splitting lines of an image is not an easy task. These types of algorithms are often slow and sometimes inaccurate. Different versions of the watershed have been researched and developed to make it more effi- cient and faster.

B. The Watershed Algorithm

There are several implementations of the Watershed algo- rithm, following the proposal of Vincent and Soille (1991), due to the efficiency in the flood process and its lower computational cost with respect to others that implement the technique.

illustration not visible in this excerpt

Fig. 25: Two examples of the watershed transform applied to a 1-dimensional signal. (A) When three markers are located at the three local minima, three segments are formed with boundaries (watershed lines) on the local maxima; (B) When only two markers are selected, segment 2 floods over a peak and into the neighboring trough, until a boundary is formed with segment 1.⁹

1) Basic Definitions: The algorithm presented in this section first sorts the pixels according to the gray level and then access them by means of a FIFO (First Input First Output) data structure to start the process of flooding the basins or basins of the picture.

Each of the local minimums is assigned a different label, which is propagated to all adjacent pixels at a given level h. We begin by analyzing the binary image with a threshold h equal to the minimum gray value of the image up to the binary image with a threshold equal to the maximum gray value. In each step the components connected between the binarization in h and h + 1 are analyzed. At the end of the flood, all pixels except Watershed lines have a label indicating which basin or region they belong to. The negative of the flooded basins forms Watershed lines separating the different regions of the image that grew from the regional minimums.

The flooding process in basins is performed by comparing the finarized image with a threshold i, denoting Z i (f), and the image at a higher level Z i +1(f), from i = 0 to i = N, where N is the maximum gray level with which the image is represented. At each level i of the image f we have regional minima m i (f). The basin or basin of the image f at the level of i, is denoted W i (f), which are initially the regional minimums. W i +1(f) is the result of basin flood W i (f).

During the flood process, there are up to three possible cases:

- Appearance of a new basin, if the pixel value of the images being compared, if Z i +1(f) is less than Z i (f), new flood regions appear, that is to say new basin.
- Appearance of a new basin, if the pixel value of the images being compared, if Z i +1(f) is less than Z i (f), new flood regions appear, that is to say new basin.
- Determination of zones of influence, if flooding of the i + 1 level joins flooded basins of level i, regions must be separated using the zones of influence of each

illustration not visible in this excerpt

Fig. 26: Prior stage for segmentation: Grayscale image, threshold- ing, aperture and distance transformation.

connected component. In this case, the baseline of i +1, that is to say W i +1 are areas of influence of the W i basin.¹⁰

C. Using the cvWatershed Function

The feature performs a marker-based segmentation using a watershed algorithm. C: void cvWatershed (const CvArr

* image, CvArr * bookmarks) Settings:

- Image: 3 channel 8 bit input image.
- Markers: Image of a single channel 32-bit input / output (map) of markers.

The function implements one of the basin variants, the non-parametric marker-based segmentation algorithm.

Before passing the image to the function, the user has roughly outline the desired regions in the image, markers with positive (¿ 0). Thus, each region is represented by one or more components connected to the values of pixels 1, 2, 3, and so on. Such markers can be retrieved from a binary mask using findContours () and drawContours (). Markers are “seeds” of future image areas. The rest of the marker pixels, whose relationship to the marked regions is not known and should be defined by the algorithm, should be set to 0. At the output of the function, each pixel of markers is set to a value of the components “Seeds ”, or -1 in the boundaries between regions.¹¹

D. Testing Watershed with OpenCV

An example of the implementation of the watershed transform was made, and distance transformation was used to segment objects that touch each other. The size of the image was reduced, then the blur filter was applied to reduce noise. A morphological opening and a morphological closure were performed to find with some degree of certainty

illustration not visible in this excerpt

Fig. 27: Final Stage: Find regions that are sure to be coins, find the unfamiliar region and then do segmentation with trashed watershed.

that the regions at the center of the objects are foreground and the region far from the center are background objects. Knowing now with certainty that region is weed and that is background, we mark the regions that we know are coins, for that we use cv2.connectedComponents() that marks the bottom of the image with 0 and then the other regions with integers from 1. Now we apply watershed as the final step to perform the final segmentation.

It is clearly observed that two coins were not identified. For this reason, the images to be worked should be properly studied and played properly with different techniques for the treatment of images before the segmentation.

IV. CONCLUSIONS AND DISCUSSION

The mathematical foundation behind the Hough transform is strong and able to be explored further, a simple change in the way the parameters of a feature are conceived may result in a great impact in the result, for example the line being taken with the slope and the intersect or the same line with normal parameters. Care must be taken into account when selecting the feature parameters.

Various features might be detected with the Hough trans- form, which is a very robust algorithm in terms of the noise it might be have to handle.

Exploration on features of several parameters shall be performed, as it may yield into accumulator spaces of several dimensions.

The use of a polar representation of the Hough transform accumulator space might be useful in some applications in which the space needs to be hardly bounded. Further research shall be performed on the algorithm employed in order to detect the denser points, as well as the case in which the line passes through the origin in the image space.

For the effective implementation of the watersheed trans- form, a work prior to its application is necessary, otherwise an inherent sobresegmentation will be obtained. Before the implementation of Watersheed can be done dilation, thresh- olding, marking, minimum imposition, gradient function, among other alternatives. This in order to come up with a suitable combination to get the best results possible.

[...]

---

¹ P. V. C. Hough, “Method and means for recognizing complex patterns,” US Patent 3,069,654, vol. 21, pp. 225-231, 1962, ISSN: 09218971. DOI: 10.1007/ s10811 - 008 - 9353 - 1. [Online]. Available: http : / / www . google . com / patents / US3069654 (visited on 03/12/2017).

² Image transforms - Hough transform, The University of Edingburgh - School of Informatics. [Online]. Available: http://homepages.inf.ed.ac.uk/rbf/HIPR2/ hough.htm (visited on 03/12/2017).

³ R. O. Duda and P. E. Hart, “Use of the hough transformation to detect lines and curves in pictures,” Communications of the ACM, vol. 15, no. 1, pp. 11- 15, Jan. 1972. DOI: 10.1145/361237.361242.

⁴ Equation of a straight line in normal form — find the equation of the line. [Online]. Available: http : //www.math-only-math.com/straight-line-in-normal- form.html (visited on 03/12/2017).

⁵ Hough line transform, OpenCV 3.0.0-dev documen- tation. [Online]. Available: http://docs.opencv.org/3. 0-beta/doc/py tutorials/py imgproc/py houghlines/ py houghlines.html (visited on 03/12/2017).

⁶ X. Chen, L. Lu, and Y. Gao, “A new concentric circle detection method based on hough transform,” 2012. DOI: 10.1109/iccse.2012.6295182.

⁷ mlai (http://stackoverflow.com/users/1985603/mlai), Answer to: Explain hough transformation, Stack Overflow. [Online]. Available: http : / / stackoverflow. com/a/20176180 (visited on 03/17/2017).

⁸ J. V. Serrano, A. Moreno, Á. Sánchez, and J. Sánchez, Visi ó n por computador. Pearson Educación, 2003, p. 268.

⁹ A. Fisher, “Cloud and cloud-shadow detection in spot5 hrg imagery with automated morphological feature extraction,” Remote Sensing, no. 1, Jan. 2014. DOI: 10.3390/rs6010776.

¹⁰ P. S. Luc Vincent, “Watersheds in digital spaces: An efficient algorithm based on immersion simula- tions,” IEEE TRANSACTIONS ON PATTERN ANAL- YSIS AND MACHINE INTELLIGENCE, vol. 13, no. 6, Jun. 1991.

¹¹ Watersheed, OpenCV 2.4.0- modules. [Online]. Available: http : / / docs . opencv . org / 2 . 4 / modules / imgproc / doc / miscellaneous transformations . html (visited on 03/17/2017).