Introduction

Colorectal cancer (CRC) is one of the most common forms of cancer worldwide and the third leading cause of cancer deaths in the United States (US) [1]. Colonic polyps are known to be a precursor to CRC, and in western countries it has been shown that over 95.0% of CRCs arise from colonic polyps [2]. Early detection and treatment provide a higher cure rate, and the timely removal of a precancerous polyp can prevent up to 90.0% of deaths [3].

To reduce the inspection time and detect the overlooked lesions in computed tomography (CT) images, computer-aided detection (CAD) methods have been reported by several research groups. In most cases, fully automatic polyp detection is described in terms of three consecutive steps: Colon lumen segmentation, polyp candidate detection and false-positive elimination and classification. Previous algorithms for segmenting the colonic lumen generally focused on the level-set methods [4,5,6], region-growing-based techniques [7,8,9], gray-level thresholding [10,11,12], knowledge-guided techniques [13, 14] and fuzzy clustering [15]. Since polyp candidate detection is a complex task, different detection methods and features such as curvature shape assumptions [16, 17], shape index and curvedness [18, 19], thickness of the colonic wall [19, 20], surface topology [21, 22], spherical fitting [23, 24] and surface normal vector via Hough transform [8, 10, 12, 23] were proposed. Also, the curvature information (orientation and global shape index) in geodesic-ring neighborhoods that incorporate the shape of a local neighborhood was determined as a polyp candidate detection method [25]. For the reduction in FPs, various methods have been employed to extract the two- or three-dimensional features considering geometrical differences, [21, 22, 26] and statistical texture information [8, 9, 14]. Besides, several mutual information methods for feature selection were proposed in order to increase specificity while preserving the sensitivity [27]. Classifiers such as support vector machines [26, 28], neural network (NN) classifiers [8, 13, 29, 30], nearest-neighbor classifiers [8] and linear and quadratic discriminant classifiers [31, 32] were applied to obtain the polyp regions.

Fig. 1
figure 1

Overview of the developed CAD system

Full size image

Polyps larger than 9 mm are very likely to be cancers and can be identified by radiologists easily. For a CAD system, it is important to be able to detect polyps in the range of 6–10 mm since they may develop into cancers. The main problems for the detection of the small polyps are the low accuracy of the segmentation process and the high number of false positives. The aim of this paper is to present a full implementation of a CAD system specially focused on the detection of the smaller polyps. “Materials and methods” section describes the structure of the developed CAD system and discusses the automatic segmentation process. Also, the polyp candidate extraction techniques and false-positive reduction and classification are described in “Materials and methods” section. “Experiments and results” section presents the experimental results. “Discussion” section discusses the performance of our CAD system. Finally, “Conclusion” section concludes this paper.

Materials and methods

Overview of the developed CAD system

The overview of our proposed CAD system is illustrated in Fig. 1. The algorithm involves colon segmentation, polyp candidate extraction, feature selection and classification. Depending on the usage of oral-contrast agent, segmentation converts from two-class problem (air–tissue) to three-class problem (air–fluid–tissue). Therefore, the first main element of the algorithm includes an adaptive threshold calculation and discrete segmentation for both air and possible fluid regions. Since the polyps are convex and have elliptical peak curvature, our system is secondly focused on extracting the 3D elliptical structures as potential polyp candidates based on the Laplacian of Gaussian filter. The final component of the CAD system is the classification of polyp candidates. First, 2D projection image for each candidate was generated, and the shape-based discriminative features were extracted from projection images. Finally, these features were used as the inputs of an artificial neural network classifier.

Automatic colon segmentation

Threshold calculation

Despite the well-defined intensity range between air and tissue, CT attenuation of the oral contrast may vary between 100 and 400 HU [33]. Due to the usage of oral-contrast agents, it is clear that there is no universal set of fixed threshold values to be used in colonic segmentations. For this purpose, we firstly designed a two-level thresholding technique, which is an extended version of Otsu’s method. The essence of this procedure is that there are two optimal thresholds \(\{{T}_{1},{T}_{2}\}\), which divide the dataset into three classes (air–tissue–fluid). In order to determine the optimal thresholds, we maximized the inter-class variances by using the discriminant analysis.

Colon-air region segmentation

The first stage of the colon-air region segmentation was the removal of the air around the body. To eliminate this outer region, the top left voxel of the first slice was selected as a seed and a standard region-growing algorithm was applied to the CT data. Next, the segmentation algorithm labeled the remaining air regions using a three-dimensional flood-fill algorithm. One of the significant characteristics of the CT data the lungs always has the biggest air areas in the first slice. After the detection of the lungs by area calculation, labels of these areas were defined as background.

After the complete removal of the outer regions and lung, the only remaining air-filled regions are the small intestines and the colon. In order to determine the colonic structures, the volume and the number of air regions in each label, which express the length of the label, were calculated as the volume/length (V/L) ratio. The normalized V/L ratios for eight cases are given in Fig. 2. It was observed that fully distended colon (CT2, CT4, CT5 and CT7) has one major segment at the V/L ratio of 1. Also collapsed colon structures (CT1, CT3, CT6 and CT8) have multiple segments, and V/L ratio of one of its segments is 1, while for others ratios are close to 1. Furthermore, V/L ratios for segments of small bowel have low values, and there is a high degree of tolerance between colon and non-colon segments approximately in a range of 0.4 and 0.7 as shown in Fig. 2. For total colon-air region segmentation, we have experimentally determined that air regions should have at least a 0.5 normalized V/L ratio.

Fig. 2
figure 2

Normalized V/L ratios for eight different CT cases

Full size image

Contrast-opacified region segmentation

Following the reconstruction of the colon-air region, the only missing part of the colon, depending on the usage of contrast agents, was the fluid pockets. In order to determine these regions, value of the \(T_2 \) was selected as a lower threshold for fluid voxels and 6-connected flood-fill algorithm was constructed to label fluid regions. The fluid regions were not the only related regions for this lower threshold. But also the voxel intensities of bone structure were above \(T_2 \). The bone structure was always present between the first and the last slice of the CT and has a biggest bounding box. The algorithm eliminated the corresponding label that met this condition.

Between the air and fluid regions, due to the thresholds \(T_1\) and \(T_2\) there was always a thin air–fluid boundary which separates both regions. This boundary, caused by gravitational force, may occur only when air-filled regions are located above the fluid-filled regions. Therefore, the upper adjacent voxels of the fluid pockets must have a connection with the lower adjacent voxels of the colon-air-filled regions. In this stage, the segmentation algorithm determined the upper boundary voxels of each fluid label and checked the connectivity between air and fluid regions. At least one connection between air–fluid regions denotes the fluid region as a part of the colon.

In this stage, the morphological dilation operation was performed to combine the air and fluid regions of the colon lumen. Thus, possible missing fragments that may be present outside of the segmented colon could be defined as a part of the colon surface in fuzzy clusters.

Fuzzy C-means clustering

In fuzzy C-means (FCM), each voxel of the dilated colon lumen belongs to one of the three clusters (air–tissue–fluid), specified by the membership grade of each voxel. For each voxel value, the membership grades and the cluster centers were updated iteratively until minimizing the objective function.

Fig. 3
figure 3

Automated segmentation of four colons a and b are the segmentation results of the well-distended colons. c and d are the segmentation results of the collapsed colons

Full size image
Fig. 4
figure 4

Polyp candidate regions in various slices. Red circles define the colon boundaries, and the green circles are the polyp candidate regions

Full size image
Fig. 5
figure 5

Demonstration of the fitting process: a the polyp candidate, b the surface of the region, c line fit and d the circle fit results

Full size image
Fig. 6
figure 6

Surface characteristics of the polyps and the folds

Full size image

After the clustering process, the ratio of the volumes of the fluid and the tissue clusters, \(V_\mathrm{F}{/}V_\mathrm{T}\), was assumed as an important feature for designating the presence of contrast agents. We experimentally determined that the CT data, which include contrast agents, have a \(V_\mathrm{F}{/}V_\mathrm{T}\) value of \({>}\)1. The colon with a lower ratio according to \(V_\mathrm{F}/V_\mathrm{T}\) is formed only from the air region. When the presence of the fluid region was determined, vertical neighborhoods of each tissue voxels were considered. For any given tissue voxel, if upper vertical neighbors were labeled as an air and lower vertical neighbors were labeled as a fluid, the related voxel was kept as a part of the colon lumen as well as the air and fluid labels. Figure 3 illustrates the performance of our automated colon segmentation algorithm for four colons.

Polyp candidate detection

Determination of ROI

A majority of the polyp candidate detection method is based on the scale-space representations of the segmented colon mask. It is a formal approach for handling structures in an image at different scales. The main purpose of using the scale space is to detect suspicious structures at any size. Scale-space representations of the colon mask were obtained by applying a Gaussian kernel with a scale parameter sigma depending on the kernel size. The Laplacian operator as a polyp candidate detector was defined as the trace (the sum of its diagonal terms) of the Hessian matrix of each voxel. By multiplying this trace with a scale parameter, Laplacian operator was used to detect scale-space maxima.

At a certain scale \({\sigma }\), scale-space representation \(L\big (x,y,z|_\sigma \big )\) was a convolution of the segmented colon \(C\left( {x,y,z} \right) \) with the Gaussian kernel defined as

$$\begin{aligned} L\left( {x,y,z|_\sigma } \right)= & {} G\left( {x,y,z,\sigma } \right) *C\left( {x,y,z} \right) \end{aligned}$$
(1)
$$\begin{aligned} G\left( {x,y,z,\sigma } \right)= & {} \left( {\frac{1}{2\pi \sigma ^{2}}} \right) ^{3/2}\mathrm{e}^{\left( {-\frac{x^{2}+y^{2}+z^{2}}{2\sigma ^{2}}} \right) } \end{aligned}$$
(2)

where \({\sigma }\) determines the width of the kernel as a full width at half maximum. Also, the Laplacian of the scale-space representation was computed as

$$\begin{aligned} \nabla ^{2}L=\frac{\partial ^{2}L}{dx^{2}}+\frac{\partial ^{2}L}{dy^{2}}+\frac{\partial ^{2}L}{dz^{2}}=L_{xx} +L_{yy} +L_{zz} \end{aligned}$$
(3)

where \(L_{xx} \), \(L_{yy} \) and \(L_{zz} \) are the diagonal terms of the Hessian matrix.

Laplacian operator gives strong positive responses to the elliptical structures. However, the Laplacian response is dependent on the relation between the Gaussian kernel and the size of the suspicious structures. In order to detect polyps of various sizes, four different Gaussian convolution kernels (\(5\times 5\times 5\), \(7\times 7\times 7\), \(9\times 9\times 9\), \(11\times 11\times 11\)) were applied to the segmented colon. For each kernel, the standard deviation (scale parameter) was determined as full width at half maximum as given, \(\sigma =\hbox {size\,of\,the\,kernel}/\left( {4\sqrt{2\log \left( 2 \right) }} \right) \). For four different kernels, the responses of each scale space might be comparable across the scales. Thus, the multi-scale polyp detector was constructed as \(\nabla ^{2}_{\mathrm{norm}} {L}_{{k}} ={\sigma }_{{k}} \nabla ^{2}{L}_{{k}} \) with the normalizing factor \({\sigma }_{{k}} \), where k is the indices of the four different scale spaces.

Since the polyps and folds may have irregular shapes, the response of the scale-normalized space contains multiple detections with different interest points. To eliminate the weak interest points, a \(3\times 3\) non-maxima suppression operator with eight neighbors was applied to the normalized polyp detector responses. The final interest points that have equal or more than four connections through the scanning direction denoted as center of the polyp candidates. Figure 4 depicts the polyp candidate regions for several slices. Red circles define the colon boundaries, and the green circles are the polyp candidate regions.

False-positive reduction

Once we found the polyp candidate regions, we fit line and circle to each slice of polyp candidates and sphere to the surface of volumetric polyp candidates as detailed in Göktürk et al. [26]. To calculate the best fit results, least-square solution of three shapes was obtained from candidate surface voxels. For a random slice of any candidate, the polyps and the folds have an ellipsoidal nature and satisfy the circle fit solution considering the line fit with minimum error (Fig. 5). Also, if the candidate is formed from the residual materials or part of the colon wall, line fit solution has a better error rate.

Generally, in 3D volumetric candidate surfaces, folds appear as elongated and ridge-like structures, while polyps are bulbous or hemispherical (Fig. 6). In order to distinguish the polyps from colonic walls and especially from folds, the spherical nature of each candidate was measured by fitting a sphere. The surface fit errors and the ratio of the voxels that intersect within the sphere were calculated to identify the differences between polyps and FPs. Here, the intersection ratio was calculated as

$$\begin{aligned} \mathrm{Intersection\,ratio} =\frac{V_\mathrm{C} \cap V_\mathrm{S} }{V_\mathrm{C} -\left( {V_\mathrm{C} \cap V_\mathrm{S} } \right) } \end{aligned}$$
(4)

where \(V_\mathrm{C}\) is the candidate tissue volume and \(V_\mathrm{S}\) denotes the best-fitting sphere volume.

Feature extraction and classification

Generating 2D projections for candidate polyps

In the literature, previous attempts to generate a 2D projection image of polyp candidates were focused on gathering the endoluminal projection of the suspicious regions through the inside of the colon and tried to mimic the radiologists 3D fly-through polyp detection process. Despite the fact that these approaches are visually realistic, such methods have several limitations. In order to obtain the 2D projection image of polyp candidates, these approaches try to optimize several parameters such as viewpoint of the camera [34, 35], the location and the direction of the projection plane [36,37,38].

Fig. 7
figure 7

Flowchart of the optimal projection image calculation scheme

Full size image
Fig. 8
figure 8

Rotation process of the polyp candidate structure

Full size image
Fig. 9
figure 9

Various projection images of a sample synthetic polyp: a and b unsuitable projections, c correct projection angles

Full size image
Fig. 10
figure 10

Optimal 2D projection of different colon structures

Full size image
Fig. 11
figure 11

Graphical descriptions of the features

Full size image

In order to overcome these limitations, we proposed a novel approach of generating a 2D projection image of polyp candidates based on affine transform. The flowchart of the projection calculation is given in Fig. 7.

As illustrated in Fig. 8, the developed method rotates each candidate around the principle axes x and y with respect to its own center, independently from the colon surface. Also, it generates 2D projection images and calculates the evaluation criterion for each rotation. \(\theta \) and \(\varphi \) are the angles of rotation that orientate each candidate around x and y axes, respectively, and for these angles, the proposed method performs 169 rotations with 15 degree intervals between \({-}\pi \le \theta , \varphi \le \pi \). The rotation matrix R is obtained from multiplication of two rotation matrices as given below.

$$\begin{aligned}&R=R_X \left( \theta \right) R_Y \left( \varphi \right) \end{aligned}$$
(5)
$$\begin{aligned}&R_X \left( \theta \right) =\left[ {{\begin{array}{llll} 1&{} \quad 0&{} \quad 0&{} \quad 0 \\ 0&{} \quad {\hbox {cos}\left( \theta \right) }&{}\quad {-\hbox {sin}\left( \theta \right) }&{}\quad 0 \\ 0&{}\quad {\hbox {sin}\left( \theta \right) }&{}\quad {\hbox {cos}\left( \theta \right) }&{}\quad 0 \\ 0&{}\quad 0&{}\quad 0&{}\quad 1 \\ \end{array} }} \right] \end{aligned}$$
(6)
$$\begin{aligned}&R_Y \left( \varphi \right) =\left[ {{\begin{array}{llll} {\hbox {cos}\left( \varphi \right) }&{}\quad 0&{}\quad {\hbox {sin}\left( \varphi \right) }&{}\quad 0 \\ 0&{}\quad 1&{} \quad 0&{} \quad 0 \\ {-\hbox {sin}\left( \varphi \right) }&{} \quad 0&{} \quad {\hbox {cos}\left( \theta \right) }&{}\quad 0 \\ 0&{} \quad 0&{} \quad 0&{} \quad 1 \\ \end{array} }} \right] \end{aligned}$$
(7)

Due to the numerous rotations, the calculation of 2D projection images and the determination of the optimal projection image must be simple, effective and time efficient. Therefore, for each rotation we obtained 2D projection images on \(x-z\) plane by summing the samples along the direction of y-axis. The criterion for optimal projection image was determined as choosing the widest area among the projection images.

Various projection images of a sample synthetic polyp are shown in Fig. 9. In Fig. 9a and b, the projection areas take up small spaces for unsuitable angles of rotation. Figure 9c shows the widest area, and therefore, it is decided as an optimal 2D projection image.

Feature extraction

The projection of each 3D candidate surface was obtained to retrieve 2D features. When the optimal projection of the polyp candidate was obtained, it was seen that the significant information of 3D candidates such as geometrical shape, height, spread and slope was still preserved in the 2D projection plane. If the structure is a polyp, a round-shaped concentric pattern appears in the projection image where the brighter pixels are near the center (Fig. 10a). If the structure is fold, an elongated shape pattern is seen in the optimal projection image. Also, since the folds appear as ridge-like structures in the 3D volumetric surface, the elongated shape pattern has continuity between the borders of the projection image (Fig. 10b). In the colon surface structure, random pattern occurs but the slopes are small in all directions (Fig. 10c).

Instead of extracting features from the 3D volume of polyp candidates, we extracted features from the 2D projection images to reduce the computational complexity. Besides, the 2D projection information of candidates also enabled the extraction of distinctive features of the polyp pattern, which cannot be easily computed from the 3D data directly.

In order to extract distinctive features from the optimal projection, hysteresis thresholding was applied to obtain the region of interest (ROI). For this purpose, the pixel values higher than 0.9 were selected as seed regions, and values between 0.9 and 0.7 were selected as growable regions.

After the binarization procedure, we extracted optimal features, namely eccentricity, circularity ratio, solidity, equivalent radius ratio, distance ratio and the surface pixel continuity test.

The first feature, eccentricity (E), is the ratio of the distance between the foci and the major axis length of the ellipse that has the same second moments as the ROI. We illustrated this relationship in Fig. 11a. In order to determine eccentricity, we firstly constructed the co-variance matrix of the ROI and then did eigen-value decomposition. Here eigen values were defined as the major and minor axis length of the ellipse, and the eigen vectors were defined as the directions of the minor/major axis. Then, we calculated the eccentricity as given below

$$\begin{aligned}&\left( {D_\mathrm{f} } \right) ^{2}=\left( {L_\mathrm{major} } \right) ^{2}-\left( {L_\mathrm{minor} } \right) ^{2} \end{aligned}$$
(8)
$$\begin{aligned}&E=\frac{D_\mathrm{f} }{L_\mathrm{major} }=\sqrt{1-\left( {\frac{L_\mathrm{minor} }{L_\mathrm{major} }} \right) ^{2}} \end{aligned}$$
(9)

where \(D_\mathrm{f}\) is the distance between the foci, \(L_\mathrm{major} \) is the length of the major axis and \(L_\mathrm{minor} \) is the length of minor axis. Eccentricity was extracted to distinguish polyp and fold structures with respect to their 2-D geometrical behaviors in their projection images. For this feature, the ROI with eccentricity ratio close to 1 is referred as fold (a line segment) and the ROI with eccentricity ratio close to 0 is referred as polyp.

Circularity ratio (\(R_\mathrm{C})\) is the proportion of the area of the ROI to distance around the boundary of the ROI [39].

$$\begin{aligned} R_\mathrm{C} =\frac{4\pi A}{P^{2}}=\frac{4\pi \left( {\pi r_\mathrm{A} ^{2}} \right) }{\left( {2\pi r_\mathrm{P} } \right) ^{2}} \end{aligned}$$
(10)

where A is the area and P is the perimeter of ROI, respectively. \(r_\mathrm{A}\) is the radius of a circle with a same area as ROI and \(r_\mathrm{P}\) is the radius of a circle with a same perimeter as ROI. For a region whose shape is similar to a circle, the ratio gets close to 1.

Since the shape of a polyp in optimal projection image was convex (Fig. 10a), we extracted the solidity feature to identify suspicious convex regions. In this regard, we calculated convex hull of each region and determined the proportion between the area of the ROI and the area of the convex hull as illustrated in Fig. 11b.

The feature called the equivalent radius ratio (\(E_\mathrm{R})\) is the ratio between the radius of circle with the same area as the region and the radius of a circle with the same perimeter as the region.

$$\begin{aligned} E_\mathrm{R} =\frac{\sqrt{4A/\pi }}{P}=\frac{\sqrt{4r_\mathrm{A} ^{2}}}{2\pi r_\mathrm{P} } \end{aligned}$$
(11)

For a circular region, due to the similar values of \(r_\mathrm{A}\) and \(r_\mathrm{P}, E_\mathrm{R}\) gets close to \(1/\pi \). In Fig. 11c, the circle that has a same perimeter as the region is illustrated with blue color and the circle that has a same area as the region is illustrated with red color.

In the case of a polyp, a round-shaped concentric pattern appeared at the center of the optimal 2-D projection plane. Therefore, the center coordinates of the projection plane (\(x_{c}, y_{c})\) and the ROI (\(x_{w},y_{w})\) should be quite close to each other. This relation is illustrated in Fig. 11d. In this regard, we defined the distance ratio (\(R_{D})\), as the Euclidean distance between the centroid of the projection plane and the weighted centroid of the ROI is given as

$$\begin{aligned} R_D =\frac{\sqrt{\left( {x_c -x_w } \right) ^{2}+\left( {y_c -y_w } \right) ^{2}}}{\sqrt{d_x^2 +d_y^2 }} \end{aligned}$$
(12)

here \(d_{x}\) and \(d_{y }\) are the dimensions of the projection plane.

In an optimal projection image of a polyp, ROI area appeared near the center and was not connected to the borders of the plane. Therefore, the boundary pixels of the region were in the form of a closed loop. In this respect, we randomly selected a boundary pixel of a ROI as a seed point and moved it along the boundary in both directions until the whole border was completed. If that pixel had a connection to a border of the plane, the process was stopped in that direction. Finally, we calculated the Euclidean distance between the final pixels and defined this feature as the surface pixel continuity test (SPCT). For SPCT, two different scenarios are illustrated in Fig. 11e and f, respectively. In Fig.11e, boundary of the region has a connection to border of the plane. So the process is stopped in both directions. In Fig. 11f, boundary of the region is in the form of a closed loop and Euclidean distance is 0.

Classification

Even though the feature vectors were quite effective for distinguishing polyps from FPs, the discrimination offered by our feature space was not linearly separable. Therefore, we used a committee of multi-layer perceptron (MLP) neural network and support vector machine (SVM) as classifiers to develop a suitable classification scheme. MLP is feedforward artificial neural network technique, which maps sets of a feature onto a set of different classes and has the capacity to distinguish feature data which are not linearly separable. MLP employs a supervised learning method, backpropagation, for training. The output of the jth hidden neuron in MLP is calculated as

$$\begin{aligned} O_j =f\left( {\mathop \sum \limits _{i=1}^N \left[ {w_{ij} } \right] \left[ {x_i } \right] +b} \right) \end{aligned}$$
(13)

where \(w_{ij} \) is the weight of connection, \(x_i \) is the input pattern, b is the bias weight and f is the activation function.

The reason for utilizing a committee of classifiers was that it often achieves better performance than a single classifier due to the diverse configuration of the members of the committee. The committee was constructed of five members, and the configuration of each classifier was determined experimentally. MLP members had three hidden layers with different configurations (number of neurons differs for the first hidden layer between 12 and 14, for the second hidden layer 7 and 9 and for the third hidden layers 4 and 6), and Levenberg–Marquardt-based backpropagation algorithm was used for training [41]. Hyperbolic tangent-sigmoid function was selected as the activation function.

$$\begin{aligned} \mathrm{tanh}\left( x \right) =\frac{1-\mathrm{e}^{-2x}}{1+\mathrm{e}^{-2x}} \end{aligned}$$
(14)

We used a majority vote rule to reach the committee decision. In this assumption, the class that receives the largest number of votes is selected as the consensus decision.

Fig. 12
figure 12

FROC curve of the CAD system

Full size image

SVM is also supervised learning method, which maps linearly non-separable sets of feature in a higher-dimensional space and designates optimal discriminating hyperplane to classify two different classes. So, linearly non-separable features become linearly separable in higher dimensions. Given a set of Mdata points \(\left( {x_i ,y_i } \right) ,i=1, \ldots ,M\) where \(x_i \in R^{n}\) (feature vector), n is the number of attributes of \(x_i \) and \(y_i \in \left\{ {-1,1} \right\} \) (class label), the optimal form of the SVM classifier is

$$\begin{aligned} f\left( x \right) =\mathop \sum \limits _{i=1}^M \alpha _i y_i K\left( {x_i ,x} \right) +b \end{aligned}$$
(15)

where \(\alpha _i \) is the Lagrange multipliers and b is the constant, which are optimized as the solution of quadratic programming, \(f\left( x \right) \) is the decision of the core function and \(K\left( {x_i ,x} \right) \) is the kernel, which maps linearly non-separable features in a higher dimension. We constructed SVM classifier with Gaussian radial basis function kernel with scaling factor, sigma, of 1

$$\begin{aligned} K\left( {x_i ,x_j } \right) =\hbox {exp}\left( -\Vert x_i -x_j\Vert ^{2}/2\sigma ^{2}\right) \end{aligned}$$
(16)

When the size of the training dataset is small, cross-validation is a popular approach to reduce bias and avoid over-fitting [14]. Due to the small sample size of our database, we evaluated our classification performance with threefold cross-validation method. We randomly divided the polyp candidates (37 polyps and 1506 non-polyps) into three uniformly distributed sets without any repetitions. In each of the three experiments, one set was used for validation (12 or 13 polyps and 502 non-polyps) and the remaining sets were used for the training (25 or 24 polyps and 1004 non-polyps). Every polyp candidate occurred in the validation set exactly once and occurred in the training set two times.

Experiments and results

Data specification

For some cases, patient preparation procedure includes the administration of contrast agent for fecal tagging. Colonic insufflation was obtained with an automated \(\hbox {CO}_{2}\) insufflator. Room air with manual insufflation was utilized if adequate colon distention could not be obtained using the mechanical insufflator. Before examination, unless contraindicated or rejected by the study participant, one milligram of subcutaneous glucagon was administered for 7–15 min. All examinations were performed using at least a 16-slice CT scanner. Images were acquired using 0.5–1.0 mm collimation, pitch of 0.98–1.5, matrix \(512\times 512\), field-of-view to fit, tube currents of 100–275 mA with 140 kVp, and standard reconstruction algorithm. Images were reconstructed to slice thicknesses of 0.5–1 mm. Our CAD system was applied to supine position scans with respect to slice thicknesses of 0.5, 0.625 and 1 mm.

The locations of the polyps were confirmed by two experienced radiologists who were blinded to interpretation of the CTC and colonoscopy results. Radiologists independently determined the size and the location of the polyp structures on CT supine scans based on the colonoscopy reports. If interpretations of the radiologists (polyp size range or location of the polyp) did not to match, they viewed the CT data together and confirmed the size and the location of the polyp structures with a high degree of agreement. In cases where a tissue was reported as a polyp on colonoscopy results but not identified on CT data, it was excluded from the study. Only two significant polyps (measured as a small polyps on colonoscopy results, \({<}\)6 mm) were unable to be determined in the CT scans. These manually confirmed polyp locations and sizes were used as a gold standard. In this study, 37 polyps of various sizes (7 polyps \({<}\)6 mm, 24 polyps between 6 and 10 mm and 6 polyps \(\ge \)10 mm) were obtained from 30 patients supine scans.

Table 1 Performance of the CAD system for operating points 1
Full size table
Table 2 Performance of the CAD system for operating points 2
Full size table

Overall performance of the CAD system

The FROC curves as given in Fig. 12 show the overall performance of our CAD system in all polyp size range. In Fig. 12, the black line depicts the performance of the MLP, and the dotted blue line represents the performance of the SVM. The operating points 1 given on the plot indicate 94.59% sensitivity with 5.3FP/dataset for MLP and 7.9FP/dataset for SVM (Table 1). For the operating points 2, the sensitivities for MLP and SVM classifier were 91.89% with FP per dataset of 1.3 and 4.16, respectively (Table 2). The sensitivities for the detection of the polyps between 6 and 10 mm were 95.83% for both MLP and SVM (operating points 1) and 91.67% for MLP and 95.83% for SVM (operating points 2). The operating points were selected in a manner that detected low false-positive rates with high sensitivities.

In order to determine the performance of our CAD system for polyps in different size ranges, the patient dataset was separated into three classes according to polyp sizes (\(\ge \)10, 6–10 and \({<}\)6 mm). In Fig. 13, the black line shows the MLP performance for polyps \(\ge \)10 mm, the red line indicates the MLP performance for polyps between 6 and 10 mm and the blue line denotes the MLP performance for polyps \({<}\)6 mm. The dotted lines also show the performance of the SVM classifier, respectively. From the operating points that were given on the FROC curves, the sensitivities and the FP/dataset are given in Table 3. The sensitivity of 87.5% for polyps between 6 and 10 mm was achieved at FP rates of 5.57 for MLP and 7.81 for SVM. For polyps \(\ge \)10 mm, sensitivity of 100% was obtained for the MLP and SVM at 1.83 FP/dataset and at 5 FP/dataset, respectively.

The FROC curves of the CAD system for polyps \(\ge \)6 mm are given in Fig. 14. For these 27 patient datasets featuring 30 polyps, the operating points indicated that the CAD system yielded 96.67% sensitivity at 1.12 FP/dataset for MLP and 96.67% sensitivity at 5.48 FP/dataset for SVM.

Fig. 13
figure 13

FROC curves of CAD system for polyps in different size ranges

Full size image

Discussion

Although most of the polyps come in various shapes, they still have some spherical local surface fragments and may appear roughly as hemi-spherical, blob-like structures. Therefore, our polyp candidate detection method extracts polyp candidates based on LoG filters. While previous approaches in polyp candidate recognition were focused on the shape index and curvedness [18, 19] or surface normal vector via Hough transform [8, 10, 23], we proposed a novel approach that serves a different point of view and extracts all true polyps with 7927 FPs (264.3 FP/dataset). In addition to shape fitting techniques as given in Göktürk et al. [26], we introduced a new feature called intersection ratio and calculated the SSE of each least-square solution. The application of shape fitting technique reduced FPs by 80.6% and approximately 50.2 FP per dataset was obtained.

Polyps could arise at different locations of the inner surface of the colon at any size and any orientation. Therefore, the proposed algorithm identified the locations of candidates in scale space, invariant to orientation, size and location. Also, candidate detection algorithm did not need any preprocessing stages such as Hough transform [8, 10, 23], surface normal overlap [12] or intensity adjustment [15]. This reduced the computational complexity of the detection method. In the literature, previous attempts either extracted constant sub-masks [10, 13, 15, 26] or experimentally determined constant thresholds or several control parameters [8, 10, 15, 29, 40] to identify polyp candidates. Due to the various sizes of the polyps, there is no global sub-volume or sub-image extraction scheme. The sensitivity of constant sub-masks approaches is depending on the size of the sub-masks, and there is always a possibility to miss polyp structures. On the other hand, determination of the control parameters or thresholds for the geometrical features [15, 29, 40] (shape index, curvedness, etc.) limits the detection boundaries and enable to miss polyp region. Our polyp detection system investigated the possible polyp regions without any sub-mask and eliminated the weak interest points, with non-maxima suppression instead of constant threshold. The only control parameter was scale parameter \({\sigma }\).

Table 3 Performance of the CAD system when applied to polyps for different size ranges
Full size table
Fig. 14
figure 14

FROC curve of CAD system for the polyps larger than or equal to 6 mm

Full size image

We proposed a novel technique to determine optimal projection image of the polyp candidates. The developed method rotates each candidate around the principle axes independently from the colon surface and generates 2D projection images. Li et al. [34, 35] proposed the endoluminal projection method using 2D projection image technique based on taking graphical snapshots of polyp candidates through an optimized viewpoint which depend on the camera position and lightning direction. Also, Yao et al. [36,37,38] proposed a ray casting technique for generating 2D projection images, and they computed the distance from the camera to the surface based on height map approach. To generate a height map, an orthogonal projection plane was defined and placed over polyp candidates. However, these methods have several limitations such as camera position, lightning direction and location of the orthogonal projection planes. If the plane is too close or too far to the suspicious detection, it may cut across the polyp or may fall behind the opposite colon wall. Our novel projection approach overcomes these limitations and calculates optimal projection by choosing the widest area among the projection images. Shape-based features such as circularity ratio, solidity and the eccentricity were used in polyp detection for the first time.

In the training process, we evaluated two different classifiers polyp detection performances. The performance of MLP classifier is dependent on the choice of the number and the size of the hidden layers. Similarly, the performance of SVM is also dependent on the choice of the kernel function [26]. We constructed committee of MLP with five MLP members, and each member has three hidden layers with different configurations (number of neurons differs for the first hidden layer between 12 and 14, for the second hidden layer 7 and 9 and for the third hidden layer 4 and 6). We also evaluated the performance of SVM with different kernel functions (linear, polynomial, quadratic, exponential and Gaussian radial basis functions) and determined that Gaussian radial basis function kernel with scaling factor, sigma, of 1 provided better sensitivity with low FP ratios. Although MLP and SVM had the capacity to distinguish features, which are not linearly separable, the output performances of classifiers indicated that MLP provided better FP ratios than SVM at the same sensitivity values. Thus, we had determined the overall performance of proposed CAD system by selecting the MLP as a classifier (Table 4).

The performance comparison of the proposed CAD system to the related methods reported in the literature is given in Table 5. It can be observed that the performance of our CAD system has significant sensitivity ratios at low number of FPs. The CAD system proposed by Summers et al. [22] detected convex surfaces as polyp candidates and extracted shape-based features such as the principle, mean and Gaussian curvatures. In order to reduce the false positives, they derived shape-based filters and achieved 71% sensitivity for large polyps (\(\ge \)10 mm) with 3.4 FP/dataset. Additionally, Paik et al. [12] used the number of intersection points of the normal vectors to identify suspicious convex structures and achieved 100% sensitivity with 7 FP/dataset for polyps \(\ge \)10 mm. Our polyp detection algorithm is able to identify large polyps with sensitivity of 100% at 1.83 FP/dataset, which are the best ratios among the studies.

Table 4 Performance of the CAD system for the polyps larger than or equal to 6 mm
Full size table
Table 5 Summary performance of the selected CAD systems
Full size table

Kiss et al. [23] analyzed the surface normal intersections and determined the center points of convex surfaces based on Hough transform and 3D region-growing algorithm. Their CAD system achieved 60% sensitivity with 3.17 FP for polyps \(\ge \)6 mm. Yoshida and Nappi [40] utilized shape index and curvedness to determine candidate surfaces, and their systems showed 95% sensitivity at 3.4 FP for 12 polyps between 6 and 30 mm. For similar sized polyps, Suzuki et al. [13] and Xu et al. [14] achieved 95% sensitivity at 3.6 FP/dataset and 96% sensitivity at 4.1 FP/dataset, respectively. With our method, sensitivity of 96.67% with 1.12 FP per dataset is obtained for polyps \(\ge \)6 mm. While our algorithm has comparable sensitivity ratios with [13, 14, 40], it has better sensitivity ratio than the one developed by Kiss et al. [23]. Besides, our FP/dataset is superior to those four studies.

When performances of the three different projection calculation methods were inspected, Li et al. [35] obtained 71.11% sensitivity with 5.38 FP/dataset and Yao et al. [38] obtained 76.9% sensitivity with 3.09 FP per dataset for medium-sized polyps (6–10 mm). In our method, we achieved 87.5% sensitivity at 5.57 FP/dataset in this size range. Although the FP ratio of our system is higher for operating point as given in Fig. 13, we achieved better sensitivity. For another operating point in FROC curve of the CAD system for medium-sized polyps, we achieve 78.3% sensitivity at 2.58 FP/dataset, which is superior to the two studies. Additionally, we obtain better sensitivity with respect to Yao et al. [38] for large polyps.

In our tests, we used only the supine scans of the CT images. We believe that an improvement for system performance is still possible if the prone scans of the CT images are added to dataset.

Conclusion

In this paper, we developed a fully integrated CAD system for the automated detection of polyps that yields a high polyp detection rate with a reasonable number of false positives. The proposed CAD system detects polyp structures with 94.59% sensitivity at 5.3 FP/dataset. Our CAD system also identifies clinically relevant polyps (\(\ge \)6 mm) with 96.67% sensitivity at 1.12 FP/dataset. A novel polyp candidate detection system with LoG filters is one of the main contributions of this paper. We also propose a new 2D projection image calculation scheme. We believe that our CAD system is highly effective for assisting radiologist interpreting CT scans.