A Novel Gradient-Weighted Voting Approach for Classical and Fuzzy Circular Hough Transforms and Their Application in Medical Image Analysis—Case Study: Colonoscopy

Featured Application

The circular fuzzy Hough transform with gradient-weighted voting can be used for finding the contours of circle-like shapes, such as colorectal polyps on colonoscopy images, as well as other cases that require a given relative gradient edge around the circle-like objects.

Abstract

Classical circular Hough transform was proven to be effective for some types of colorectal polyps. However, the polyps are very rarely perfectly circular, so some tolerance is needed, that can be ensured by applying fuzzy Hough transform instead of the classical one. In addition, the edge detection method, which is used as a preprocessing step of the Hough transforms, was changed from the generally used Canny method to Prewitt that detects fewer edge points outside of the polyp contours and also a smaller number of points to be transformed based on statistical data from three colonoscopy databases. According to the statistical study we performed, in the colonoscopy images the polyp contours usually belong to gradient domain of neither too large, nor too small gradients, though they can also have stronger or weaker segments. In order to prioritize the gradient domain typical for the polyps, a relative gradient-based thresholding as well as a gradient-weighted voting was introduced in this paper. For evaluating the improvement of the shape deviation tolerance of the classical and fuzzy Hough transforms, the maximum radial displacement and the average radius were used to characterize the roundness of the objects to be detected. The gradient thresholding proved to decrease the calculation time to less than 50% of the full Hough transforms, and the number of the resulting circles outside the polyp’s environment also decreased, especially for low resolution images.

1. Introduction

As some polyps in the colon and rectal tract of the bowel can develop into extremely dangerous cancers, and they cause symptoms only rather late in their developed phase, it is recommended that even healthy individuals undergo colorectal screening after a certain age. There are multiple methods available for colon screening, with colonoscopy being the most commonly used. A colonoscope, which is an endoscope equipped with a flexible tube, camera, light source, and other tools, can navigate within the bowel, and perform various tasks like inflating the bowel, spraying liquids, and removing lesions [1,2].

Even for experienced gastrologists, detecting polyps with the naked eye can be challenging due to various factors such as inadequate intestinal preparation and visual exhaustion. A computer-aided system for localizing colorectal polyps would simplify the diagnostic process and facilitate the assessment of the examined cases severity. Thus, healthcare professionals would be able to prioritize urgent cases, promptly select appropriate treatments, and efficiently analyze clinical results. Therefore, developing reliable computer-aided diagnosis techniques that can automatically and precisely localize polyps in colonoscopy images is currently one of the most demanding needs in the healthcare sector [1,2,3].

To aid the gastroenterologists, various machine learning and deep learning architectures have been currently developed as prominent solutions to automatize polyp detection and localization tasks and enhance the accuracy of their consequences [4,5,6]. A method for real-time detection, classification, and localization of gastrointestinal tract disorders from colonoscopy images was presented in [7]. Both online available (hyper-Kvasir dataset) and private locally collected samples were utilized. The method was developed using the pre-trained transfer learning SSD, YOLOv4, and YOLOv5 object detection models, with minimal fine-tuning of the hyperparameters, and their final performance was compared, whereas the utilization of the YOLOv5 object detection algorithm and the artificial bee colony (ABC) optimization algorithm was proposed in [8]. The YOLOv5 algorithm was employed for polyp detection, while the ABC algorithm was used to enhance the performance of the model by finding the optimal activation functions and hyperparameters for the YOLOv5 algorithm. The proposed method was executed on the SUN and PICCOLO datasets and achieved good performance in real-time polyp detection.

Not only the deep learning approaches but also the polyp characterization computational methods are widespread in the literature. These methods mainly compute some shape [9,10] and texture-based [11,12] feature descriptors over the full image or a segment of it to be able to detect and localize and the polyp’s area precisely.

In pattern recognition literature, Hough transform is considered as a great mathematical tool for object detection since the first appearance of its classical version for machine analysis of bubble chamber pictures by Paul V C Hough in 1959 [13]. In 1981, it was extended by D. H. Ballard into the Generalized HT (GHT), which is a two-phase learning-detection process to detect arbitrary complex non-parametric shapes [14]. Continuously, different variations of Hough transform have been proposed by many researchers, like probabilistic Hough transform [15], randomized Hough transform [16], and Vector–Gradient Hough Transform (VGHT) [17].

In 1994, Han, Kóczy, and Poston introduced the fuzzy Hough transform [18] to detect fuzzy lines and circles in the noisy environments by roughly fitting the data points to given parametric forms.

Hough transform and all its successive versions have proven to be typical powerful techniques with promising outcomes in numerous fields of applications, for example but not limited to, object detection [19,20], lanes and roads detection [21,22], industrial automation [23], mechanical engineering [24], medical image processing [25,26,27,28,29], and robot navigation [30] fields.

Drawing from our experience and a comprehensive analysis of previous studies employing the Hough transform, we briefly outline the practical strengths and weaknesses of this method in

Table 1. The practical strengths and weaknesses of Hough transform.

Strengths	Weaknesses
✓ Not limited to specific shapes ✓ Any parametric curve can be used as basis	⊠ With more parameters the dimension of the accumulator space increases ⊠ The calculation demand grows exponentially with the number of parameters
✓ Easy to parallelize (the transformation itself is independently executed for each edge point)	⊠ Can be computationally expensive - for high-resolution images - for complex shapes - for dense line images
✓ Can identify partial and obstructed curves	⊠ Shorter curve segments with fewer points result in weaker peaks in the accumulator space
	⊠ Sensitive to noise. Noise may lead to additional peaks in the accumulator space
✓ It can detect multiple objects	⊠ Overlapping objects may lead to unphysical, ghost peaks
	⊠ Partially covered, or smaller objects can be suppressed by the larger objects with more points

.

The research community has investigated the limitations of Hough transform and suggested different approaches to make it a more plausible tool. To solve large calculation demand and to ensure integration with the Wireless Capsule Endoscopy (WCE) system, authors in [31] improved the real-time computation of the Hough transform. The design of the new approach took into consideration specific constraints of WCE such as limited space and limited energy resources. Within the same limitation direction (i.e., minimizing the Hough tansform’s computational cost), an Edge Orientation-based Fuzzy Hough Transform (EOFHT) was proposed in [32]. Instead of using all the edge-detected image points in the voting process, just those specific points whose representation is consistent with the selected gradient orientation range were eligible to vote.

Moreover, since shorter curves give fewer votes, thus, circles with smaller radii give weaker peaks in the accumulator space, a weighted vote which is inversely proportional to the radius in the parameter space was given to each entitled point in the image space by the modified voting method in [33].

Currently, automatic colorectal polyp detection and localization in colonoscopy images is a promising research area and a challenging problem because of the high variability of the colorectal polyps’ characteristics in both shape and texture. Thus, the efficiency of applying Hough transform was also studied in this field.

Classical Hough transform was applied in [34] to identify potential regions of interest (ROIs) in 300 video endoscopy pictures. A good detection of the ROIs containing a polyp was possible using classical Hough transform based on Canny edge detection approach. However, in several samples the method generated many alternative weaker circles, and raised the classification system’s False Positive Rate (FPR). To enhance the effectiveness of the proposed method, after Hough transform step, the textural characteristics from co-occurrence matrices were computed, and then used within a boosting-based technique for the final classification purpose. Hough transform was also used in other colorectal polyp localizing methods [35,36] as a ready-made preprocessing step to find ROIs. However, they concentrated on the steps determining whether a ROI contains polyp or not, and not on the Hough transform step itself. (Linear Hough transform was also used in colonoscopy for detecting folds within the bowel [37].)

In our research, instead of improving the steps after selecting the ROIs with Hough transform (like in [34,35,36]), we would like to overcome some weaknesses of the Hough transform itself. The circles arising from the fuzzy Hough transform can also serve as initial masks for active contour methods [38,39].

As a first step we introduced fuzzy Hough transform, as it provides more tolerance to the deviations from the ideal curve’s points, and colorectal polyps in real colonoscopy images are not precisely circular [40].

As a second step, we targeted the large computational demand of the Hough transform, as the low computational load is one of the most essential requirements for algorithms used in computer-aided diagnosis (CAD) systems.

Hough transform starts with an edge detection (mostly Canny edge detection), and all the edge pixels have to be transformed. However, the edge pixels can be decimated, as the Canny edge detection tends to have a dense edge map because of the necessarily high connectivity of the edge points. Colonoscopy images contain edges other than colorectal polyps’ borderlines, however, these edges often either have smaller or larger intensity steps compared to the edges of colorectal polyp contours. Based on these considerations, the possibility of removing Canny edge detected points with too small or too high gradient magnitude values was investigated in [41]. The research was performed on all the images of three colonoscopy image datasets CVC-Clinic [9], CVC-Colon [42], and ETIS-Larib [34]. The study’s goal was to eliminate edge points that do not belong to polyp contours, and at the same time, to keep as many polyp contour edge points, as it is necessary for the colorectal polyp contour to be detectable.

Setting a global gradient magnitude threshold domain that could achieve both a low total number of Canny edge pixels and at the same time a sufficiently accurate matching with the colorectal polyp contour was not possible. However, if the continuity of the Canny edges is given up, other edge detecting methods could provide a better basis for Hough transform, as there the continuity of the lines is not needed, only that the edge points are on the contours of the polyp. This is one of the ideas that were studied in this paper.

The main contributions of this article are as follows. First, the performance of four edge detection algorithms (Canny, Prewitt, Roberts, and Sobel) was compared, and the most ideal one that gave the most polyp-contour-related and least unnecessary edge points was selected. Two metrics, based on the normalized gradients of contour and non-contour edges were used to determine which algorithm is the most appropriate. Second, to further reduce the number of edges that do not belong to the polyp contours, a gradient magnitude thresholding process was applied for the results of the selected edge detection method. Finally, to make the circle detection more tolerant to shape uncertainty, the fuzzy version of the Hough transform was also tested together with the classical one using a gradient-weighted voting approach. To evaluate the results, the radial displacement and the average radius were introduced to characterize the roundness of the objects to be detected. These contributions are summarized in the following points,

• selecting the edge detection method that is the most suitable for colorectal polyp localization purposes. Developing a metric to base this selection,
• determining gradient limits for removing the unnecessary edges,
• applying fuzzy Hough transform on colonoscopy images and comparing its results with the classical Hough transform,
• introducing a gradient-weighted voting to both classical and fuzzy Hough transforms and study its effects,
• characterizing the roundness of the objects to be detected.

The paper is organized the following way. In the next section, in Section 2, the summary of the mathematical methods used in the article are given, the classical and fuzzy Hough transforms, the gradient filtering and edge detection algorithms. Section 3 contains the proposed method in detail. In Section 4 the results are given and discussed, while in the last section the conclusion is drawn.

2. Theoretical Background

2.1. Classical and Fuzzy Hough Transforms

Hough transform has been in use for detecting straight lines and circles since a rather long time. The Hough transform is meant to find a parametric curve fitting to some measured points of the curve [13], if the shape, i.e., the general parametric formula of the curve is known. One of the simplest Hough transforms uses the two-parameter equation of a straight line, i.e.,

$$y=a_0·x+b_0$$

(1)

with $x$ and $y$ being the coordinates of points in the Cartesian space, and $a_0$ and $b_0$ being the parameters from the parameter space $(a,b)$. Hough transform basically generates the curves belonging to each line point $(x_0,y_0)$ in the space of the parameters; in the case of straight lines, each point $\left(x_0,y_0\right)$ will form a straight line

$$b=\left(-x_0\right)·a+y_0$$

(2)

in the parameter space, too. If another point is on line (1) in the real space, it will have another line in the transformed space, similar to (2), but with different slope and offset. However, these lines, formed by the points on line (1) will have an intersection at $(a_0,b_0)$, i.e., at the parameter pair belonging to (1). This means, that the point $(a_0,b_0)$ will be arising from all the points $(x,y)$ of (1), thus, if we add one vote to each point of (1), then $(a_0,b_0)$ will have a high number of votes, whereas other points, that belong only to one of the lines of type (2) will have only one. This consideration was used by Hough and later by many others to develop the following method.

• Divide the space $(x,y)$ by a finite grid (if not already executed).
• Divide the transformed space $(a,b)$ by a finite grid, it gives the resolution of the result.
• For each point $\left(a,b\right)$ in the transformed space add a vote for each point $(x,y)$ in the original space, that is contained by the line.
• Search for the maximum of votes
  • If there is just one line, the global maximum $(a_{max,0},b_{max,0})$ will be the approximation of parameter $(a_0,b_0)$ of the line we were looking for.
  • If there are multiple lines, longer and shorter segments, the local maxima $(a_{max,k},b_{max,k})$ will also approximate parameter pairs of lines.
    The longer the line in the original space, the more votes it obtains. By setting up a threshold, the length of the detected line segment can be controlled.
• The lines $y=a_{max,k}·x+b_{max,k}$ with the detected approximate parameters $(a_{max,k},b_{max, k})$ can be drawn in the original space $(x,y)$.

The algorithm is given for the case of straight lines like (1), but it can be generated easily to any kind of parametric curve. In the case of colorectal polyps, the circular or elliptic Hough transform is the most plausible, with parametric equations

$$r_0^2={\left({x-a}_0\right)}^2+{\left(y-b_0\right)}^2,$$

(3)

$$1=\frac{{\left({x-h}_0\right)}^2}{a_0^2}+\frac{{\left(y-k_0\right)}^2}{b_0^2}$$

(4)

It can be seen that the circle has three parameters, the radius $r_0$, and the centre coordinates $a_0$ and $b_0$, while the ellipse has four parameters, the half axes $a_0$ and $b_0$, and the centre coordinates $h_0$ and $k_0$.

Nowadays, Hough transforms are applied to images after edge detection [14,15,16], thus, the original space already has an innate grid, i.e., step 1 is mostly not necessary. Very often this edge detection step is considered as the first step of the Hough transform.

As the focus of our paper is on circular Hough transform, here the pseudocode of the classical circular Hough transform is given in Algorithm 1.

Algorithm 1: Classical Hough transform for a circle with parameters a, b and r
Requirements:   an edge image $I[i_x,i_y]$ with size $L_x,L_y$,   a finite parameter space $V\left[j_a, j_b, j_r\right]$ with size $L_a, L_b,L_r$ with initial values of 0   a threshold for peak percentage $P_p$,   a result image $R\left[i_x,i_y\right]$, with size $L_x,L_y$, with initial values of 0
1:	for each image row $i_x$ from 1 to $L_x$
2:	for each image column $i_y$ from 1 to $L_y$
3:	for each parameter space row $j_a$ from 1 to $L_a$
4:	for each parameter space column $j_b$ from 1 to $L_b$
5:	for each parameter space 3rd dimension $j_r$ from 1 to $L_r$
6:	if $j_r^2={\left(i_x-j_a\right)}^2+{\left(i_y-j_b\right)}^2$
7:	$V\left[j_a, j_b,j_r\right]=V\left[j_a, j_b, j_r\right]+1$
8:	end if
9:	end for
10:	end for
11:	end for
12:	end for
13:	end for
14:	compute the global maximum $M_G$ in $V\left[j_a, j_b,j_r\right]$
15:	compute local maxima $M\left(k\right)=V\left[j_{a,k}{, j}_{b,k},j_{r,k}\right]$
16:	select local maxima with $M\left(k\right)>P_p\cdot M_G$
17:	calculate the number $N_M$ of the local maxima from line 16
18:	for each local maximum $k$ from 1 to $N_M$
19:	for each result image row $i_x$ from 1 to $L_x$
20:	for each result image column $i_y$ from 1 to $L_y$
21:	if $j_{r,k}^2={\left(i_x-j_{a,k}\right)}^2+{\left(i_y-j_{b,k}\right)}^2$
22:	$R\left[i_x,i_y\right]=1$
23:	end if
24:	end for
25:	end for
26:	end for

In real life, the images have noise, thus, even if the original objects had straight lines, circles or ellipses as their edges, the images will probably have distorted edges. If this distortion is not too large, then the classical Hough transform is still effective, though sometimes more lines arise instead of one. However, there is a method that can handle not only slightly distorted edges, but larger deviations from the circles. This method is the fuzzy Hough transform, introduced by Han, Kóczy and Poston [18].

The fuzzy Hough transform considers the points $(x,y)$ as fuzzy points. Fuzzy points are based on Zadeh’s original idea of fuzzy sets [43], which generalized the classical, Boolean sets to have fuzzy perimeters by introducing a so-called membership function $\mu$. In the classical, Boolean algebra, only the membership values of $\mu =0$ and $\mu =1$ are possible, i.e., something can either be a member of a set or not. In Zadeh’s approach, the objects can not only be elements or not of a set, but there is a strength of their membership. In the case of a geometrical point $(x,y)$, it can also be considered as a fuzzy set, it has membership value $\mu =1$ at the coordinate point $(x,y)$, and the membership value decreases to zero monotonously as we get further from the coordinate $(x,y)$, leaving its environment still be partially belonging to the fuzzy point $(x,y)$. Using this approach in the fuzzy transform, we can consider not only the coordinate point $(x,y)$ to give a vote 1 to the corresponding parameter space points, but also its environment can give votes proportional to their membership value.

This approach modifies the previously described classical Hough transform in the following way. (For the sake of generality, $\left(a,b, \dots \right)$ were used, instead of $(a,b)$ to express the applicability to any type of parametric curve, not only straight lines).

• Divide the space of fuzzy points $(x,y)$ by a finite grid (if not already executed).
• Divide the transformed space $(a,b, \dots )$ by a finite grid, it gives the resolution of the result.
• For each point $\left(a,b, \dots \right)$ in the transformed space, and its environment add a vote proportional to the membership function for each fuzzy point $(x,y)$ in the original space, that is part of the fuzzy curve.
• Search for the maximum of votes
  • If there is just one curve segment, the global maximum $(a_{max,0},b_{max,0}, \dots )$ will be the approximation of parameter $(a_0,b_0, \dots )$ of the curve we were looking for.
  • If there are multiple curves, with longer and shorter segments, the local maxima $(a_{max,k},b_{max,k}, \dots )$ will also approximate parameters of the curves.
    The longer the curve in the original space, the more votes it obtains. By setting up a threshold the length of the detected segment can be controlled.
• The curves with the detected approximate parameters $(a_{max,k},b_{max,k}, \dots )$ can be drawn in the original space $(x,y)$.

Practically, if all fuzzy points $(x,y)$ have the same membership distribution around them, then the 3rd step of the voting manifests in adding a vote $\mu \left(\left|\alpha -a\right|,\left|\beta -b\right|, \dots \right)$ to the neighboring points $\left(\alpha ,\beta , \dots \right)$ of the studied parameter space point $\left(a,b, \dots \right)$.

Using this approach made the Hough transform more tolerant to distortions from the original parametric curves. This made us able to use circular Hough transform for searching for contours of polyps, i.e., the three-parameter Equation (3) could be used instead of the four-parameter Equation (4).

Using these considerations, the pseudocode of the circular fuzzy Hough transform is as follows in Algorithm 2.

Algorithm 2: Fuzzy Hough transform for a circle with parameters a, b, and r
Requirements:   an edge image $I[i_x,i_y]$ with size $L_x,L_y$,   a finite parameter space $V\left[j_a, j_b,j_r\right]$ with size $L_a$, $L_b$, $L_r$, with initial values of 0   a threshold for peak percentage $P_p$,   a voting membership matrix $\mu \left[j_a, j_b,j_r\right]$ with size $2d_a+1, {2d}_b+1, 2d_r+1$   a result image $R\left[i_x,i_y\right]$, with size $L_x,L_y$, with initial values of 0
1:	for each image row $i_x$ from 1 to $L_x$
2:	for each image column $i_y$ from 1 to $L_y$
3:	for each parameter space row $j_a$ from 1 to $L_a$
4:	for each parameter space column $j_b$ from 1 to $L_b$
5:	for each parameter space 3rd dimension $j_r$ from 1 to $L_r$
6:	if $j_r^2={\left(i_x-j_a\right)}^2+{\left(i_y-j_b\right)}^2$
7:	$V\left[\left\{j_a-d_a,\dots ,j_a+d_a\right\}, \left\{j_b-d_b,\dots ,j_b+d_b\right\}, \left\{j_r-d_r,\dots ,j_r+d_r\right\}\right]=$…       $V\left[\left\{j_a-d_a,\dots ,j_a+d_a\right\}, \left\{j_b-d_b,\dots ,j_b+d_b\right\}, \left\{j_r-d_r,\dots ,j_r+d_r\right\}\right]+\mu \left[j_a, j_b,j_r\right]$
8:	end if
9:	end for
10:	end for
11:	end for
12:	end for
13:	end for
14:	compute the global maximum $M_G$ in $V\left[j_a, j_b, j_r\right]$
15:	compute local maxima $M\left(k\right)=V\left[j_{a,k}{, j}_{b,k}, j_{r, k}\right]$
16:	select local maxima with $M\left(k\right)>P_p\cdot M_G$
17:	calculate the number $N_M$ of the local maxima from line 16
18:	for each local maximum $k$ from 1 to $N_M$
19:	for each result image row $i_x$ from 1 to $L_x$
20:	for each result image column $i_y$ from 1 to $L_y$
21:	if $j_{r,k}^2={\left(i_x-j_{a,k}\right)}^2+{\left(i_y-j_{b,k}\right)}^2$
22:	$R\left[i_x,i_y\right]=1$
23:	end if
24:	end for
25:	end for
26:	end for

The applied voting membership function was a 3D-Gaussian, as it had a rather wide region around the center that is still close to 1. For a given parameter point $\left(a_0,b_0,r_0 \right)$, the votes were given to the neighboring points $\left(\left[a_0-\sigma ,a_0+\sigma \right],\left[b_0-\sigma ,b_0+\sigma \right],\left[r_0-\sigma ,r_0+\sigma \right] \right)$ according to the membership function

$$\mu \left(a,b,r\right)=\exp \left(-\frac{{\left(a-a_0\right)}^2+{\left(b-b_0\right)}^2{+\left(r-r_0\right)}^2}{2\mathsf{\sigma }}\right).$$

(5)

As an example, an image (No. 220 form database CVC-Colon), its preprocessing steps, and transformed images are shown in the following figures. Figure 1 shows the image after reflection removal, its ground truth mask and its Prewitt edge detected version. Figure 2 shows the resulting votes for classical and fuzzy Hough transforms (for one with $\sigma =5$ slight fuzziness, and another with $\sigma =15$, wide fuzziness). Each column has four images, two at the radius values belonging to the two main detected circles, and there are 2 pictures with radii slightly smaller and larger than the circle at the polyp. Figure 3 shows the detected circles for different thresholds compared to the global maximum of the votes.

2.2. Gradient Filtering

In mathematics, for a 2D continuous function, we use the partial derivatives to measure the degree of variation along each dimension. The edges in an image are segments that can be formed from the point locations where there is a rapid change in the image gray-level intensity in a small region. The connection between the previous two concepts made it possible to apply gradient filtering techniques in the field of image processing to detect edges.

The gradient of an image intensity function is a 2D vector with two components defined by the horizontal and vertical derivatives at each image point, and using these two values, we can identify the strength of the edge’s magnitude and its orientation at each pixel.

The common mathematical formulation of the gradient for 2D image is the following vector:

$$\mathbf{G}\left[f\left(x,y\right)\right]=\left[\genfrac{}{}{0pt}{}{G_x}{G_y}\right]=\left[\genfrac{}{}{0pt}{}{\frac{\partial f}{\partial x}}{\frac{\partial f}{\partial y}}\right],$$

(6)

where $f$ is the image intensity function, and $x$ and $y$ are the spatial coordinates of the image. The magnitude and direction of the gradient are consecutively given by the two equations below:

$$G\left[f\left(x,y\right)\right]=\sqrt{G_x^2+G_y^2},$$

(7)

$$\alpha \left(x,y\right)={\tan }^{-1}\left(\frac{G_y}{G_x}\right).$$

(8)

All of the aforementioned considerations are carried out in the continuous domain. In the case of a digital image, where the intensity function is sampled at image discrete points, we replace the gradient operator by a discrete operation, i.e., by a convolution between the image and a kernel, which is a matrix of smaller size. For partial differentiation the discrete counterpart is taking the difference of neighboring pixels. The following gradient kernels are often used in practice.

$${Roberts}_1=\left[\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right],\hspace{1em}{Roberts}_2=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right].$$

(9)

$${Prewitt}_x=\left[\begin{array}{ccc}-1& -1& -1\\ 0& 0& 0\\ 1& 1& 1\end{array}\right],\hspace{1em}{Prewitt}_y=\left[\begin{array}{ccc}-1& 0& 1\\ -1& 0& 1\\ -1& 0& 1\end{array}\right].$$

(10)

$${ Sobel}_x=\left[\begin{array}{ccc}1& 0& -1\\ 2& 0& -2\\ 1& 0& -1\end{array}\right],\hspace{1em}{Sobel}_y=\left[\begin{array}{ccc}1& 2& 1\\ 0& 0& 0\\ -1& -2& -1\end{array}\right].$$

(11)

2.3. The Implemented Edge Detection Algorithms

Edge detection methods can be used as mathematical techniques to identify particular locations in an image where the gray level intensities show discontinuities. The resulting edge maps serve as the basis for subsequent processing steps in numerous significant computer vision applications. In this section of the paper, a brief description of the four used edge detection methods is provided.

2.3.1. Roberts, Prewitt, and Sobel Edge Detection Algorithms

The well-known Roberts, Prewitt, and Sobel edge detection algorithms are widely used because of their simplicity and easiness of implementation. All of these algorithms have the same work mechanism, but with different kernels. Each kernel has the effect of calculating the gradient in the specified direction. However, the choice of algorithm to be used depends on the desired application and the characteristics of the image being processed.

Roberts edge detection method uses convolutional filters to detect the variations in the image gray-level intensity in the diagonal directions [44], whereas Prewitt and Sobel methods use convolutional matrices to detect the changes in both $x$ and $y$ directions [45,46].

The previously mentioned kernels, (9), (10), and (11), are used by the Roberts, Prewitt, and Sobel edge detection algorithms, consecutively.

2.3.2. Canny Edge Detection Algorithm

John Canny first presented Canny edge detection in 1986 [47] as a multistep algorithm. Canny algorithm is looking for the connectivity of the edge points as well as the high gradient image points which makes it the most popular edge detection technique in many computer vision and image processing applications. This technique produces very reliable and highly accurate edge maps that are close to the human perception of edges.

The process of Canny algorithm consists of four main steps. First, the original image is refined using a Gaussian filter to remove unwanted noise. The applied Gaussian filter is defined as follows:

$$g\left(x,y\right)=G_{\sigma }\left(x,y\right)\ast f\left(x,y\right),$$

(12)

where

$$G_{\sigma }(x,y)=\frac{1}{2\pi {\sigma }^2}\mathrm{e}\mathrm{x}\mathrm{p}(-\frac{x^2+y^2}{2{\sigma }^2})$$

(13)

The convolution operator is represented by the symbol $\ast$, and the indices $x$ and $y$ are used to identify a pixel’s location within an image. The two-dimensional function $G_{\sigma }(x,y)$ is a Gaussian function with the variance of ${\sigma }^2$.

The smoothened image’s gradient magnitude and direction are then calculated using a certain gradient operator, i.e., Roberts, Prewitt, or Sobel. The third step is implementing the Non-maximum Suppression (NMS) approach to check if the pixels are part of the local maxima, and if not, they are put down to zero. Two hysteresis high and low thresholds are computed in the final step. Every edge point with a gradient value greater than the higher threshold is identified as a strong edge, whereas the edge points whose gradient values fall below the lower threshold are eliminated. The connectivity of the residual edge points which have gradient values between the low and high thresholds is tested: the examined point is considered as an edge pixel only if at least one of the neighboring pixels is a strong edge pixel [48].

3. Practical Application of the Proposed Method

3.1. Edge Detection Methods—Application, Evaluation, and Selection

For these tasks, several processing steps were carried out. They are sequentially summarized below together with the illustrated figures and plots. Three publicly available colonoscopy image databases, CVC-Clinic [9], CVC-Colon [42], and ETIS-Larib [34] are used.

• Cutting off the black frame surrounding all original images to reduce unnecessary information.
• Removing the colonoscope’s light reflections: The colonoscope light’s reflections (and consequently their contours) were removed from all the databases’ images as a step towards reducing the number of redundant edge pixels (Figure 4b). The histogram of the image pixel intensities was used as the basis for the reflection removal step. Briefly, we cut out the histogram’s highest (and lowest) intensity peaks, and then the pixel intensities were re-normalized to the original [0 to 255] domain. A “white mask” was created using the pixels that made up the histogram’s highest peak. Similar to the procedure described in [49], the “white mask” was extended and smoothened into the neighboring pixels.
• Extracting polyp contour: For each of the ground truth masks (Figure 4c), the contour was defined (Figure 4d). The number of pixels that make up the polyp mask contour was calculated for later use in the evaluation process.
• Generating the “ring mask” for the colorectal polyp contour: In many cases of the manually drawn masks, the edges of the polyp’s contour are not completely visible, either because the polyp is located in the area of bowel folds, or it is covered with impurities. Moreover, reasons related to the human fatigue or error can also affect the drawing accuracy of the colorectal polyp mask. These are the main reasons why it was necessary to extend the contour of the manually drawn database mask to a finite width ring which is proportional to the size of the examined image. The previously extracted contour was extended into a ring (Figure 4e). To do that, we selected the first $x$ nearest pixels of the entire contour as a width of the ring mask. As the databases images are with different sizes, we used different ring mask widths based on the database images size (they are $x=3$ for CVC-Clinic database [9], $x=5$ for CVC-Colon database [42], and $x=10$ for ETIS-Larib database [34]).
• Calculating the gradient magnitude for each of the studied samples, like in (Figure 4f).
• Detecting polyp edges: Canny, Prewitt, Roberts, and Sobel techniques were applied as four different edge detection methods (Figure 5a,c,e,g respectively). By employing this edge detection operation, it becomes possible to decrease the time required for the following pre-processing steps and offers a comparatively consistent data source that tolerates geometric and environmental variations while performing the Hough transform calculations. The total number of edge pixels resulting from each filtering technique for all the images of the three databases was calculated and plotted in Figure 6.
• Finding the gradient-weighted edges: The edge filtered images (Figure 5a,c,e,g) were multiplied by the gradient magnitude output (Figure 4f). The reason for performing this multiplication step is to determine the gradient magnitude domain, where the polyp edges are most likely to be present within the whole gradient domain.
  As an example, we received images like (Figure 5b,d,f,h) for Canny, Prewitt, Roberts, and Sobel techniques. (It is visible, that in contrast with the full gradient subplot (Figure 4f), subplots (Figure 5b,d,f,h) contain the gradient values only where the edge mask value is 1, i.e., where the white pixels are located in subplots (Figure 5a,c,e,g).
• Normalizing: To make the proposed approach universally applicable, for all the pictures in all the databases, the gradient-weighted edges pixels were normalized into the interval [0, 1] for each image separately.
• Counting the number of the edge pixels located inside the ring mask, (this number serves as the reference: it is the number of the useful edge pixels).
• Calculating the final evaluation metrics: Considering our application requirements, two quantities were introduced to evaluate each of the four implemented edge detection methods. For each image of the three studied databases, the statistics calculated in the previous steps (the total number of pixels in the polyp mask contour, the total number of edge pixels resulted from each edge detection method, and the total number of edge pixels inside the ring mask) were used in composition the following two metrics.
  • The first evaluation parameter, i.e., the one referring to the calculation efficiency, is defined by the ratio between the number of edge pixels in the ring mask around the polyp contour and the total number of edge pixels in the entire image,

    $$R\_calc=\frac{(No. of edge pixels in the ring mask)}{(Total No. of edge pixels)}.$$

    (14)

    This ratio represents the quality of the edge detection method with regard to the Hough transforms and polyp detection. $R\_calc$ values’ range is between 0 and 1. The higher this ratio is, the fewer non-mask contour edges are identified, and the less unneeded calculation is required in the classical or fuzzy Hough transform. Figure 7 shows the values of this metric resulting from Canny, Prewitt, Roberts, and Sobel filtering techniques for the three databases.
  • The second evaluation parameter, i.e., the metric referring to the goodness of the edge pixels finding the ideal polyp contour (derived from the ground truth mask), is given by the ratio between the number of edge pixels in the ring mask and the number of pixels in the database polyp mask contour,

    $$R\_edge=\frac{(No. of edge pixels in the ring mask)}{(No. of pixels in mask contour)}.$$

    (15)
    In ideal case, this ratio should be as close to 1 as possible. Figure 8 displays the values of this metric resulting from all edge detection techniques for all studied databases.
    We have to note that the detected edge pixels in the ring mask may not exactly be the same as the edge pixels in the manually drawn database mask contour, but it still could be used for finding the polyp.
• Selecting the most appropriate edge detection technique: Canny method detects a wide range of fine edges and gives a dense detailed edges map. It also tends to connect edge pixels to continuous edge lines, in contrast with the other three techniques. Figure 6 clearly shows the large difference between the total number of edge pixels resulting from Canny and the other three edge detection methods. Prewitt, Roberts, and Sobel have very similar results for the majority of samples. As we are interested not only in decreasing the number of edge points scanned by the Hough transform, but also in increasing the efficiency of finding the colorectal polyp, we relied on the definition of the previous two evaluation metrics $R\_calc$ and $R\_edge$ as a basic for selecting the most appropriate edge detection technique as following.
  • Selection of the most appropriate edge detection technique using $\mathit{R}\_\mathit{c}\mathit{a}\mathit{l}\mathit{c}$: We tested two different selection strategies using metric $R\_calc$. Based on the definition of $R\_calc$, the nearest the value $R\_calc$ to 1 is, the better the filter is.
    According to the 1st strategy, we can select the filter, that has the mean of the metric $R\_calc$ values closest to 1. For each database and each type of the four edge detection methods we calculated the mean of the $R\_calc$ values.
    However, for the values of metric $R\_calc$, in all databases, for all the four edge detection techniques, there was many samples between [0, 0.1], as it is visible in Figure 7. This is the reason why another strategy has to be considered as well.
    According to the 2nd strategy, we can select the filter, which has the most samples close to the ideal value. For this purpose, a goodness interval can be defined, and the number of samples within that interval can be calculated. In our case, for every edge detection technique, we checked how many samples in each database had a $R\_calc$ value greater than 0.1 as a measure of the filter suitability. Accordingly, the higher the number of resulting samples, the better the filter is. Of course, the percentage of this number within the total number of images in each database has to be considered; database CVC-Clinic [9] has 612 images, database CVC-Colon [42] has 379 images, and database ETIS-Larib [34] has 196 images).

    Table 2. Results of selection the most appropriate edge detection technique using metric $R\_calc$.

    	Canny	Prewitt	Roberts	Sobel
    1st strategy: $R\_calc$ Mean	0.063001	0.153718	0.147087	0.152823	CVC-Clinic
    	0.04806	0.099965	0.081437	0.09925	CVC-Colon
    	0.026186	0.06001	0.049776	0.059926	ETIS-Larib
    2nd strategy: Num. of samples with $R\_calc>0.1$	70	394	360	394	CVC-Clinic
    	29	138	108	141	CVC-Colon
    	0	35	22	33	ETIS-Larib

    lists the total results of this step.
  • Selection of the most appropriate edge detection technique using $\mathit{R}\_\mathit{e}\mathit{d}\mathit{g}\mathit{e}$: We also tested two different choosing strategies based on metric $R\_edge$.
    According to the 1st strategy, similar to what we executed for $R\_calc$, we can test how similar the results to their ideal value are. However, instead of calculating the mean value, we calculated the mean absolute error (MAE) value for metric $R\_edge$ from its ideal value 1. For this criterion, the smallest MAE value nominates the better filter.
    According to the 2nd strategy, as metric $R\_edge$ should be as close to 1 as possible, we suggested finding the goodness interval around $R\_edge=1$, i.e., considering each sample that has $R\_edge$ value within [0.5, 1.5] among the good samples. Consequently, the higher the number of samples within the goodness interval, the better the filter is.

    Table 3. Results of selection the most appropriate edge detection technique using metric $R\_edge$.

    	Canny	Prewitt	Roberts	Sobel
    1st strategy: $R\_edge$ MAE	0.459919	0.447193	0.579451	0.44937	CVC-Clinic
    	0.779827	0.582246	0.683746	0.588328	CVC-Colon
    	2.609909	0.44718	0.536933	0.451125	ETIS-Larib
    2nd strategy: Num. of samples with $0.5<R\_edge<1.5$	346	353	221	349	CVC-Clinic
    	132	156	90	152	CVC-Colon
    	4	122	88	121	ETIS-Larib

    arranges the total results of this step.

The highlighted results presented in the above two tables show that the Prewitt filter is the most appropriate edge detection technique based on our proposed selection strategies using both metrics $R\_calc$ and $R\_edge$ in most cases.

It should be noted from Table 2 (2nd strategy) that the results of Sobel filter are very close to the Prewitt ones, especially for database CVC-Clinic: they are the same. Moreover, for database CVC-Colon, the number of samples that had an $R\_calc$ value greater than 0.1 is three samples more in the Sobel filter than in the Prewitt case.

The flowchart in Figure 9 summarizes the overall edge detection method selection procedure.

3.2. Gradient-Based Thresholding for Prewitt Edge Detection Results

In this part of the proposed method, the dynamic distribution of the normalized gradient-weighted edges pixels resulting from the Prewitt method of both the ring mask (i.e., the area surrounding the ground truth mask contour) and the full image was studied by generating the individual histograms of all images in all databases.

Four individual histograms of four different samples can be found in Figure 10. Please note that as in most of the cases the gradient intensities were in the first 20%, the density of the histogram bins in that domain were made to be larger. This dividing of the normalized gradient range resulted in a more detailed tendency view in the domain with dense bin distribution. Additionally, as the column height in the dense bin distribution domain became relatively smaller, thus, the visibility of the small column magnitudes in the other parts of the histogram (i.e., in the higher normalized gradient domain) became better.

In most of the cases, the distributions of the full image edges (cyan) and the ring mask edges (yellow) showed a very similar tendency with different magnitude, like in the case of the first example, subplot (a) of Figure 10. Very often beside the similar tendency in the low gradient domain, the higher gradient parts were missing in the case of the ring mask edges, like in the 2nd and 3rd example (subplots (b) and (c)). In some other cases, the distributions of the full picture and the ring mask had different tendencies, like in the case of the 4th example, in subplot (d).

To summarize the results of the individual histograms, 3D-histograms were created for the three databases with the picture number being the 3rd dimension. These total histograms are plotted in Figure 11 and Figure 12. Figure 11 shows the perspective view in linear scale, while Figure 12 gives the top view of the same histograms in logarithmic scale. It is worth mentioning that the linear and logarithmic scale plots of the same histogram are both given, because the smaller valued histogram parts at the lowest and the highest normalized gradient bins cannot be observed well in the linear scale plots of the total histograms. On the other hand, the top view of the logarithmic scale plots makes the entire set of data viewable without columns blocking the ones behind them.

Based on results in Figure 11 and Figure 12, it is visible that the edges with very high gradient values do not belong to the polyp edge, i.e., most of the ring mask edge results have 0 values over 0.3. Additionally, they have zero values below 0.06. Moreover, in many cases this lower limit can be brought up to 0.08, and the upper limit can be as low as 0.2. We decided to use this property and omit the edges with too high and too low gradient magnitudes in order to both reduce the number of pixels to be Hough transformed and to sort out those pixels that certainly do not belong to the polyp edges. Thus, in the next calculations, beside the full Hough transforms for all the edges, we performed restricted Hough transform for the edges with normalized gradient values within a wide threshold interval [0.06, 0.3] and a thin threshold interval [0.08, 0.2]. The full Hough transform results can be interpreted as a reference, to analyze how the restricted transforms influence the results.

3.3. Gradient-Weighted Voting Approach for Classical and Fuzzy Hough Transforms

In addition to excluding the edge points with too high or too low contrast (i.e., gradient thresholding), the gradient values can be used for another purpose, namely, to modify the voting process.

Even after the thresholding, polyp contours usually have segments with higher gradient magnitudes, mixed with lower gradients, whereas some of the background patterns have very low gradients. To decrease the influence of these lower gradient background edges on the Hough transform results, the following weighted voting approach was introduced.

During the original Hough transform, all edge points receive the same vote, no matter how strong these edges are. In our method, instead of 1, each point uses its normalized gradient magnitude as a vote. In the case of the fuzzy Hough transforms, the whole voting membership function is multiplied by the gradient magnitude of the given pixel. As a result, the smaller the step in the intensity at the edge is, the smaller the weight in the voting becomes for the edge point, no matter if it is a classical or a fuzzy point. To clarify better, the pseudocode of the fuzzy circular Hough transform with gradient-weighted voting approach is given in Algorithm 3.

Algorithm 3: Fuzzy Hough transform for a circle with parameters a, b, and r with gradient-weighted voting approach
Requirements:   an edge image $I[i_x,i_y]$ with size $L_x,L_y$   a gradient magnitude image $G[i_x,i_y]$ with size $L_x,L_y$   a finite parameter space $V\left[j_a, j_b,j_r\right]$ with size $L_a$, $L_b$, $L_r$ with initial values of 0   a threshold for peak percentage $P_p$,   a threshold interval for the gradient magnitudes $[g_{min}, g_{max}]$   a voting membership matrix $\mu \left[j_a, j_b,j_r\right]$ with size $2d_a+1, {2d}_b+1, 2d_r+1$   a result image $R\left[i_x,i_y\right]$, with size $L_x,L_y$, with initial values of 0
1:	for each image row $i_x$ from 1 to $L_x$
2:	for each image column $i_y$ from 1 to $L_y$
3:	for each parameter space row $j_a$ from 1 to $L_a$
4:	for each parameter space column $j_b$ from 1 to $L_b$
5:	for each parameter space 3rd dimension $j_r$ from 1 to $L_r$
6:	if $j_r^2={\left(i_x-j_a\right)}^2+{\left(i_y-j_b\right)}^2$ and $g_{min}\le G[i_x,i_y]\le g_{max}$
7:	$V\left[\left\{j_a-d_a,\dots ,j_a+d_a\right\}, \left\{j_b-d_b,\dots ,j_b+d_b\right\}, \left\{j_r-d_r,\dots ,j_r+d_r\right\}\right]=$…       $V\left[\left\{j_a-d_a,\dots ,j_a+d_a\right\}, \left\{j_b-d_b,\dots ,j_b+d_b\right\}, \left\{j_r-d_r,\dots ,j_r+d_r\right\}\right]+G\left[i_x,i_y\right]\cdot \mu \left[j_a, j_b,j_r\right]$
8:	end if
9:	end for
10:	end for
11:	end for
12:	end for
13:	end for
14:	compute the global maximum $M_G$ in $V\left[j_a, j_b, j_r\right]$
15:	compute local maxima $M\left(k\right)=V\left[j_{a,k}{, j}_{b,k}, j_{r, k}\right]$
16:	select local maxima with $M\left(k\right)>P_p\cdot M_G$
17:	calculate the number $N_M$ of the local maxima from line 16
18:	for each local maximum $k$ from 1 to $N_M$
19:	for each result image row $i_x$ from 1 to $L_x$
20:	for each result image column $i_y$ from 1 to $L_y$
21:	if $j_{r,k}^2={\left(i_x-j_{a,k}\right)}^2+{\left(i_y-j_{b,k}\right)}^2$
22:	$R\left[i_x,i_y\right]=1$
23:	end if
24:	end for
25:	end for
26:	end for

The performance of the proposed voting technique was evaluated using selected samples from each database for three main cases. The first case was the reference case where the full Hough transforms (classical and fuzzy) for all the edges without any thresholding were applied. The traditional voting technique was followed, where each edge point obtains one vote if it is eligible. The other two cases were the restricted Hough transforms for the edges with normalized gradient values within the wide threshold interval [0.06, 0.3] and the thin threshold interval [0.08, 0.2]. For these two cases, the modified, gradient-weighted voting technique was used.

In addition to the classical Hough transform, the fuzzy Hough transform was also studied in each case, with $\sigma =\mathrm{3,5},\mathrm{7,9},\mathrm{11,13} \mathrm{and} 15$ from the voting membership function (5). (In order to simplify the referring to these transform types, the classical transform may be considered as a fuzziness parameter $\sigma =0$).

When selecting the final circles, i.e., the local maxima in the transformed image, a threshold $P_p$ is to be set within the Hough transform. The arising circles (their number and location) were studied for different local maximum thresholds, namely for $P_p=50\%, 60\%, 70\%, 80\%, \mathrm{and} 90\%$ of the global maximum of the votes.

The goal of this step is to determine, how many of the final circles are around the polyp for the various $\sigma$s and local maximum thresholds $P_p$s. For this purpose, the total number of circles $N_{total}$ was counted. A circle was considered to be around the polyp by testing, if its center was inside the ground truth mask, and it had points within the ring mask around the polyp contour. The number of such circles within the ring mask $N_{ring}$ was also counted. The ratio

$$A_r=\frac{N_{ring}}{N_{total}}$$

(16)

was used as a metric for effectiveness of finding circles related to the polyp. If $A_r$ is 0, then the polyp is not found, if $A_r$ is too small, then too many other circles are found, and if $A_r$ is around 1, then the circle(s) around the polyp are found, but not many other circles can be seen in the final results.

To test the different types of Hough transforms’ tolerance degree to the deviation from the circle, it is necessary to know the size of the polyps as well as their roundness. To calculate the average radius of the polyp $r_{avg}$, the maximum and minimum coordinates of the polyp mask in $x$ and $y$ direction were used as follows,

$$r_{avg}=\frac{\left(x_{max}-x_{min}\right)+{(y}_{max}-y_{min})}{2}.$$

(17)

The center of the polyp was determined as the average of these coordinates,

$$\left(c_x,c_y\right)=\left(\frac{\left(x_{max}+x_{min}\right)}{2},\frac{{(y}_{max}+y_{min})}{2}\right).$$

(18)

This center point and the average radius were used to determine the radial displacement for each mask contour point $(m_x,m_y)$ by

$${\mathrm{\Delta }}_{radial}=\left|\sqrt{{\left(m_x-c_x\right)}^2+{\left(m_y-c_y\right)}^2}-r_{avg}\right|.$$

(19)

The roundness error can be measured by the maximum of the ratio of the radial displacements and the average radius:

$${\delta }_{roundness}=\max \left(\frac{{\mathrm{\Delta }}_{radial}}{r_{avg}}\right).$$

(20)

The larger the roundness error ${\delta }_{roundness}$, the more the shape deviates from circle. Please note, the roundness error of a circle with diameter of 30 pixels can still be as large as ${\delta }_{roundness,30}=0.04$, which decreases for a circle twice as large (i.e., of diameter 60 pixels) to ${\delta }_{roundness,60}=0.03$. Typically, an ellipse with large axis being double the size of the smaller axis have roundness error of about ${\delta }_{roundness,30}\approx 0.33$, while with axis ratio 1:3, this increases to ${\delta }_{roundness,30}\approx 0.45$, depending on the size of the ellipse in pixels.

4. Results and Discussion

4.1. Number of Circles Found by the Algorithm

In this section, the values of $A_r$ by $\sigma$s and $P_p$s are given for databases CVC-Clinic [9], CVC-Colon [42], and ETIS-Larib [34]. The total number of circles found on the images $N_{total}$ is also important, as we need as few circles, and thus, ROIs as possible for the steps after the Hough transform. For this reason, $N_{total}$ is also plotted for the three databases. In Figure 13 and Figure 14, the values $A_r$ and $N_{total}$ are given for CVC-Clinic, then in Figure 15 and Figure 16 for CVC-Colon, and finally for ETIS-Larib in Figure 17 and Figure 18. Figure 14, Figure 16 and Figure 18 together with Figure 13, Figure 15 and Figure 17, completely cover the number of circles found in the complete image and in the ring masks.

The test images were selected so that their $R\_calc$ values would be larger than 0.1. Both roundish and elongated polyps were selected from all three databases. The images with their ground truth masks are given in Appendix A. The image numbers and their respective $R\_calc$ and $R\_edge$ values together with the total number of Prewitt edge pixels for each tested sample can be found in

Table 4. The selected samples and their metrics $R\_calc$ and $R\_edge$ together with the total number of Prewitt edge pixels. The first two lines in each case are marked by gray color as they are the “bad” samples with low values of $R\_calc$, the others have $R\_calc$ larger than 0.1. The last two columns contain the metrics regarding the size and roundness of the polyp.

Database	Image	$\mathit{R}\_\mathit{c}\mathit{a}\mathit{l}\mathit{c}$	$\mathit{R}\_\mathit{e}\mathit{d}\mathit{g}\mathit{e}$	No. of Edge Pixels	${\mathit{r}}_{\mathit{a}\mathit{v}\mathit{g}}$	${\mathit{\delta }}_{\mathit{r}\mathit{o}\mathit{u}\mathit{n}\mathit{d}\mathit{n}\mathit{e}\mathit{s}\mathit{s}}$
CVC-Clinic	29	0.004918033	0.013274336	610	38.75	0.358
	201	0.008460237	0.038314176	1182	68	0.957
	111	0.247629671	0.733884298	1793	92.75	0.380
	150	0.251902588	1.054140127	1314	52	0.261
	188	0.364678899	0.424	436	66.5	0.173
	217	0.230191827	0.74393531	1199	64.5	0.409
	265	0.260652765	0.871212121	2206	110	0.775
	390	0.297808765	0.641630901	1004	75.75	0.366
	475	0.367805755	0.653354633	1112	106.5	0.757
	480	0.222554145	0.685057471	1339	72.75	0.315
	503	0.310214376	0.976190476	1586	84.75	0.151
	504	0.180173092	0.68358209	1271	56.75	0.201
CVC-Colon	51	0.004398827	0.035087719	1364	27	0.278
	255	0.002773925	0.006779661	721	52.25	0.299
	62	0.242270224	0.801120448	2361	117	0.337
	74	0.218066743	1.457692308	1738	46.25	0.694
	101	0.180649379	1.978520286	4589	71.5	0.711
	128	0.182273052	0.44973545	1399	84	0.483
	149	0.215956424	1.099510604	3121	98	0.334
	220	0.149488927	0.966942149	2348	59.5	0.202
	230	0.318594104	0.641552511	882	74.25	0.442
	283	0.194486983	0.404458599	653	52.25	0.132
ETIS-Larib	24	0.007230077	0.204545455	6224	39.75	0.135
	151	0.0010755	0.012437811	4649	70.75	0.507
	25	0.104344123	0.879186603	7044	153.25	0.549
	65	0.117593198	1.24	7645	125.25	0.249
	82	0.191721133	1.269230769	4131	113.25	0.321
	138	0.102428256	0.649859944	2265	63.5	0.449
	160	0.129833607	1.297423888	8534	151	0.430

. To make the paper more accessible to the reader, a nomenclature section of the proposed approach is also presented in

Table A1. Abbreviations and nomenclature.

$R\_calc$(14)	A ratio to represent the quality of the edge detection method regarding the calculation efficiency of Hough transforms and polyp detection
$R\_edge$ (15)	A ratio to measure the goodness of the edge pixels finding the ideal polyp contour
$\sigma$	$\sigma =\mathrm{3,5},\mathrm{7,9},\mathrm{11,13}$ and $15$ are the chosen values for the width of the voting membership function of the fuzzy Hough transforms
$P_p$	$P_p=50\%, 60\%, 70\%, 80\%,$ and $90\%$ are the peak percentage values of the selected local maximum thresholds of the global maximum of the votes
$N_{total}$	The total number of the final resulting circles
$N_{ring}$	The number of final circles within the ring mask
$A_r$ (16)	A metric to measure the effectiveness of finding polyp-related final circles
$x_{min},x_{max}$	The minimum and maximum coordinates of the ground truth mask points in $x$ direction
$y_{min},y_{max}$	The minimum and maximum coordinates of the ground truth mask points in $y$ direction
$r_{avg}$ (17)	Average radius of the polyp mask
$\left(c_x,c_y\right) \left(18\right)$	The $x$ and $y$ coordinates of the left of the polyp mask
${\mathrm{\Delta }}_{radial }\left(19\right)$	The radial displacement of mask contour point $\left(m_x,m_y\right)$
${\mathsf{\delta }}_{roundness} \left(20\right)$	The maximum of the roundness error
Original	The full Hough transforms for all the edge points
Wide	The restricted Hough transforms for the edge points with normalized gradient values within a wide threshold interval [0.06, 0.3]
Thin	The restricted Hough transforms for the edge points with normalized gradient values within a thin threshold interval [0.08, 0.2]

.

In order to check the applicability of our method, we selected some images (two from each database) that have unfavorable, very small $R\_calc$ values. These “bad” images are shown as the first two images of the figures illustrating the tests samples in Appendix A, as well as the first two lines of Table 4. These images all found zero circles in the ring mask, except for one case CVC-Colon 255, for the original, non-gradient-weighted voting method. This is why their results are not shown in Figure 13, Figure 15 and Figure 17.

In Figure 13, Figure 15 and Figure 17 the values of the ratio $A_r=N_{ring}/N_{total}$ are shown for databases CVC-Clinic [9], CVC-Colon [42], and ETIS-Larib [34], respectively.

Each plot has three segments along the vertical axis. The uppermost segment shows the original Hough transform’s $A_r$ values. These are the reference values to which the other results should be compared. The next, middle segment corresponds to the gradient-weighted voting with wider threshold, and the lowermost segment belongs to the gradient-weighted voting with a thinner threshold. Each line in each segment belongs to one image, in the order of Table 4 (except for the first two lines in each database, i.e., the “bad” images).

The plots have segments along the horizontal axes, too: the upper subplot has the results grouped by the peak percentage $P_p$ (i.e., threshold for the local maxima of the voting map $\left(a,b,r\right)$ to be considered as the circles), and each segment lists the $\sigma$s from classical (i.e., $\sigma =0$) till the widest fuzziness parameter $\sigma =15$. The lower subplot orders the values the opposite way: the segments belong to various fuzziness parameters $\sigma$, while the columns within the segments belong to the peak percentages $P_p=0.5, 0.6, 0.7, 0.8, 0.9$. The colored squares mean the number of circles found in the ring mask versus the total number of circles for a given image, for a given $\left(P_p,\sigma \right)$ pair. The darker red the little square is, the fewer circles outside of the polyp contour domain are found. If the little square is bright green, then no circle is found in the polyp contour’s ring mask.

From Figure 13 we can conclude that for database CVC-Clinic the fuzzy Hough transforms can mostly find circles belonging to polyp contours (most of the little squares in the maps are red).

The classical transform’s results are either very good (dark red) or very bad (green).

Mostly, increasing the threshold improves the results, the circles will be more in the area of the polyp contour, but the 90% threshold might be too much. It loses the circles in the ring mask for some cases. Thus, the most ideal value for $P_p$ is $70$–$80$% of the global maximum of the votes.

The fuzziness has a kind of optimal value around $\sigma =5$ (there the images have the largest number of dark red points and darkest red points), but this optimum is not very sharp, the neighboring $\sigma$ values have very similar results in the domain of $\sigma =\left\{\mathrm{3,5},7\right\}$. Even for those images that have no circle found in the ring mask for the classical case, the results can be improved by the fuzzy version of the transform.

Regarding the gradient-weighted voting, and the gradient-based thresholding, the results improve compared to the original voting scheme, but the difference is not extremely large.

There is one sample image where the circles found are not around the polyp contour for the classical transform: image No. 475. However, it can be seen that this particular polyp has barely visible circular contour segments. The results improve even for this case for the gradient-weighted voting processes (except for the classical Hough transform in the thin threshold case). Here, we have to note that in order to have the transform calculable and also to remove the very large and very small circles from the results, we limited our search for the $r$ domain between $1$% and $25$% of the longer image dimension, so the longer edges of the very elongated polyps, like the one on image No. 475 could not be detected.

From Figure 15, for database CVC-Colon, it can be seen that more circles are found outside of the polyp contour ring mask, i.e., the little squares in the plots tend towards the yellow and greenish part of the color palette.

The value of the ideal sigma seems to be a little bit higher, around $\sigma =7$ or $\sigma =9$, but there is much more variation than in the case of the previous database. For some images the higher $\sigma$ domains give better results, for others the lower $\sigma$ domains.

The thin threshold loses the circles in the ring mask for more images, so it is not a good option for this database.

For the peak percentage $P_p$ this database behaves similarly to the previous one.

Again, there is an image that does not show circles in the ring mask for most of the three cases: image No. 230, which has a brightly lighted front part and the polyp is at the background.

From Figure 17 it can be seen that for database ETIS-Larib, the ratio of circles outside the ring mask is further increased, i.e., the $A_r$ became even smaller and the plots became even less red.

Here, the higher $\sigma$ values perform slightly better, but this tendency is even less clear than in the case of CVC-Colon.

The $P_p$ value here is also similar to the previous cases, $70$–$80$%.

The thin threshold is worsening the results: even though there are pictures, where the number of circles outside the ring mask decreases, there are more images, where the circles within the ring mask at the polyp contour disappear.

For image No. 82, where the polyp contour is very sharp, the polyp’s circle gets lost due to the gradient thresholding for the thin threshold.

4.2. Roundness Metrics Evaluation

In order to test how tolerant the classical and fuzzy Hough transforms for the deviation from the circle, we used a test image of five ellipses in an image of size 200 × 200 pixels. The larger axis of the ellipse was the same for each of the objects in one image, and the ratio of the two axes were 1:1, 5:6, 4:6, 3:6, and 2:6. Three images were used, one with larger axis of 30 pixels, one with 60 pixels and one with 90 pixels. The properties of the ellipses are given in

Table 5. Properties of the ellipses of the artificial test images of size 200 × 200 pixels. The order of the ellipses is the same as the order in the vertical axis of Figure 19, except for the ghost circles.

Artificial Image	Axes (Pixels)	${\mathit{r}}_{\mathit{a}\mathit{v}\mathit{g}}$	${\mathbf{\Delta }}_{\mathit{r}\mathit{a}\mathit{d}\mathit{i}\mathit{a}\mathit{l}}$	${\mathit{\delta }}_{\mathit{r}\mathit{o}\mathit{u}\mathit{n}\mathit{d}\mathit{n}\mathit{e}\mathit{s}\mathit{s}}$
	30, 30	15.5	0.6508	0.042
	30, 25	14	1.8902	0.135
	30, 20	13	2.8758	0.221
	30, 15	11.75	4.7322	0.403
	30, 10	10.5	5.0081	0.477
	60, 60	30.5	0.7931	0.026
	60, 50	28	2.8902	0.103
	60, 40	25.5	5.2002	0.204
	60, 30	23	7.6023	0.331
	60, 20	20.5	10.0369	0.490
	90, 90	45.5	1.6081	0.035
	90, 75	41.5	4.2220	0.102
	90, 60	38	8.4958	0.224
	90, 45	34.25	12.1989	0.356
	90, 30	30.5	15.0686	0.494

. In Figure 19, the number of circles that were found by the Hough transforms are summarized for each of the ellipses separately. As the centers of the ellipses were rather close to each other especially on the largest axis case, for lower thresholds one or more unphysical “ghost” circles appeared, typically at the regions between 2 or 3, almost overlapping ellipses. The number of these ghost circles are also given under the numbers belonging to the real, physical ellipses.

It can be seen from Figure 19 that of the artificial image with objects of the smallest size, the classical Hough transform could only detect the precise circle, even the roundness error ${\delta }_{roundness}=0.135$ was not tolerable. As the fuzziness parameter increased, the peaks belonging to more and more elongated ellipses grew above the half of the global maximum of the votes, i.e., above $P_p=50$%. Already for $\sigma =5$ all the ellipses were found in the $P_p=50$% case. The corresponding radii were smaller than the larger axis of the ellipse.

As the size of the ellipses increased, the limit for finding all the ellipses went higher. Additionally, due to the closeness of the ellipses compared to the full width at half maximum of the voting matrix, overlaps arose between the individual ellipses and thus, false peaks appeared in the accumulator space, either in the area at the center of the image, which is circumvented by the ellipses, or at the two most elongated ellipses, that sometimes appeared as two twin peaks at the vote maps.

It can be seen that for the larger sized ellipse, even the classical Hough transform has a small roundness error tolerance: ${\delta }_{roundness}=0.1$ is still found, although as two circles.

If the roundness of the tested colonoscopy images is studied in the last two columns of Table 4, we can see that very much elongated polyps also exist with ${\delta }_{roundness}>0.9$ roundness error, but the typical roundness error is between 0.15 and 0.5. This is the reason we selected this domain for the ellipses to be studied in our artificial examples.

Similar to the case of the artificially generated test images, the polyps with very much elongated shapes ${\delta }_{roundness}>0.4$, the polyps were very often not found if their sizes were large, or found only for very low threshold $P_p$, like in the cases of ETIS 1st, 3rd and 4th images, or CVC-Clinic 4th.

Additionally, the smaller polyps with radii around 60 are usually detected, regardless of their roundness.

4.3. Time Evaluation

To demonstrate the effect of the running time, the ratio between the total running times of the gradient-weighted method with wide and thin thresholds to the original Hough transform is given in Figure 20. It can be seen that in the case of most of the images, the wide threshold decreases the running time of the Hough transform algorithms by about 50%, and the thin threshold decreases the runtime by another roughly 50%, but in some cases, it can go down to lower than 10% of the original transform’s running time. For database CVC-Colon, the results are a bit better than for the other databases. From the 2nd subplot of Figure 20, we can conclude that these results are almost size independent, though for a smaller number of edge pixels, the results are usually a little bit better.

It is important to note that the number of the pixels to be transformed has an almost linear effect on the transformation time, so using Prewitt edge detection is a really important step, as it can be seen from Figure 6. As the continuity of the edges is not a key point in Hough transform, and by giving it up, we can get rid of a lot of weaker edges in the background. This step has a double advantage.

5. Conclusions

A novel voting method was suggested for circular Hough transform analysis of colonoscopy images. As the colorectal polyp contours have neither too large nor very small gradients, a gradient-based thresholding was also introduced.

Based on statistical data, thresholds of $[0.06,0.3]$ and $[0.08,0.2]$ of the normalized gradient domain were suggested to improve the ratio of the circles in the surroundings of the polyp among all the circles that are found by the Hough transform. The first, wider threshold was proven to give more reliable results. Using this method, the running time of the algorithms decreased to less than $50$% compared to the full Hough transforms. The thin threshold removes so many valuable edge points from the polyp contour edges for some of the images that the circles there cannot be found by Hough transforms, so even though the threshold $[0.08,0.2]$ further improves the running time, it is safer to keep the wider threshold $[0.06,0.3]$.

The main strength of the gradient-weighted voting mechanism is that it improves the ratio of the circles near the polyp among all the circles for the Hough transforms, especially for the fuzzy Hough transform. The ideal threshold for the local maxima of the voting map $\left(a,b,r\right)$ to be considered as circles is $70$–$80$% of the global maximum for colonoscopy images.

The fuzzy Hough transforms perform better in finding circles in the polyp contour ring mask than the classical transform, but the best performing fuzziness parameter varies with the image size. For the smaller images (CVC-Clinic has image size of $384\times 288$) the small $\sigma =3$, $5$, or $7$ voting matrices are the most ideal, for the medium image size (CVC-Colon has image size of $574\times 500$) the $\sigma =7$ or $9$ is better, while for the largest images (ETIS-Larib, of size $1225\times 966$) the larger, $\sigma$ values are the most fitting for the purpose of finding polyp contours in colonoscopy images. However, this sensitivity for the values of $\sigma$ becomes less and less expressed for the larger images.

The detection success also depends on the size of the polyp and its roundness. To measure the tolerance for shape deviation of the classical and fuzzy Hough transform, the roundness error was introduced together with the average radius of the polyp. For objects larger in size, smaller tolerance is allowed in roundness, while for smaller objects, the tolerance is larger, which is rather advantageous, as in colonoscopy, mostly the smaller lesions are the ones that might be missed by humans.

The main strength of applying fuzzy Hough transform and gradient-weighted voting together is that fuzzy Hough transform has higher tolerance for shape deviations. Although fuzzy voting needs more calculations than the classical one, the introducing of the gradient threshold and the gradient-weighted voting and thus, decimating the edge points to be transformed helps to keep the calculation time lower. The weaknesses of our methods include that it is hard to determine a universal gradient threshold that is valid for all databases and image sizes. Additionally, the non-conventional angles, when the polyps are in front of dark background, need to be treated separately, though these polyps are usually hard to miss for a human expert. In addition, many polyps with extremely large, irregular shapes are not found by Hough transforms. As computer aided diagnosis is meant to aid the human expert and not to substitute them, finding the smaller polyps that are easy to miss with naked eye is the most important task in colorectal polyp localization.

It is also interesting to see that the higher resolution images with more detail tend to give more circles outside of the polyp contour domain due to the more visible background patterns, so it seems to be plausible to perform a mean or Gaussian filtering as the preprocessing step of the Hough transform for these larger images. However, to investigate this idea is out of the scope of this paper and it needs further studies. Additionally, the applying the fuzziness to 1D Hough transform or introducing parallelization can further improve the efficiency of the method by means of computational demand. Additionally, other on-line available databases [50] should be used to draw more universal conclusions in the future.