Search tips
Search criteria 


Logo of nihpaAbout Author manuscriptsSubmit a manuscriptHHS Public Access; Author Manuscript; Accepted for publication in peer reviewed journal;
Conf Proc IEEE Eng Med Biol Soc. Author manuscript; available in PMC 2010 August 31.
Published in final edited form as:
PMCID: PMC2930183

Linear Measurement of Polyps in CT Colonography Using Level Sets on 3D Surfaces


CT colonography has emerged as a minimally invasive alternative to optical colonoscopy for the screening of polyps which are the precursors to colon cancer. Accurate polyp measurement is crucial as the size of a polyp is considered an indication of its potential for malignancy. We present a novel method for the automatic measurement of polyps. It is based on a level set algorithm capable of evolving on the surface of a 3D object represented by a triangular mesh. It is guided by curvature features and is capable of segmenting the polyp neck, that is, the ridgeline/crestline formed around the polyp by its merging to the colon wall. Our method was validated on 40 polyp surfaces obtained from real clinical data. A 3D manual measurement was used as the reference standard. A correlation of 0.825 was found between polyp measurements from our new method and the reference standard.

I. Introduction

Although colon cancer is the second leading cause of cancer mortality in the United States [1], screening is not as widespread as could be wished because of the perceived discomfort associated with optical colonoscopy. Computed tomographic colonography (CTC) has been intensively investigated as a minimally invasive, more acceptable alternative for the screening of polyps, which are the precursors of colon cancer. Computer aided detection (CAD) of polyps has been actively pursued in order to reduce radiologists’ reading time and increase sensitivity and consistency [2]–[4]. A CTC CAD system must detect and measure polyps. Detection is a classifying task that results in a binary decision (a portion of the colon surface is either a polyp or not) while measurement is a quantitation problem. Both tasks require a polyp segmenter. In theory the same segmenter could be used for both although the priorities are not exactly identical. In the case of detection a partially segmented polyp might be good enough while for measurement an accurate segmentation is necessary. A possible strategy would use two different segmenters with the measurement segmenter refining the detection segmenter. Measuring polyps is important because the diameter of a polyp is considered an indication of its potential malignancy. Ideally a CTC CAD system would ignore polyps under 0.5 cm and call the radiologist’s attention to polyps approaching 1.0 cm. Under current guidelines, polyps 1.0 cm or larger should be immediately removed.

So far, in the published literature, the detection task has received the most attention. Results are usually presented in terms of the rates of true and false positives. However, recent times have seen a growing interest for the automated measurement of polyps. Dijkers et al. [5] and Fletcher et al. [6] presented work on polyp measurement with validation on a colon phantom while Taylor et al. used a human specimen obtained from colectomy [7]. In vivo studies were presented by Yeshwant et al. [8] and Burling et al. [9]. The automated methods in [8] and [9] both segment polyps in the CT volume, using respectively an active contour method and a fuzzy region growing. In the present paper we present a novel algorithm that works on the surface of a colon rather than in its volume. Our polyp segmentation uses a level set algorithm capable of evolving on a 3D surface mesh. It is guided by curvature features and is capable of segmenting the polyp neck, that is, the ridgeline/crestline formed around the polyp by its merging to the colon wall. The level set we implemented, the geodesic active contour (GAC), was chosen for its robustness to boundary inhomogeneities, which, in the present case, means inhomogeneities in the curvature properties of the polyp neck. The validation involves 40 polyp surfaces obtained from in vivo clinical data.

II. Methods

The inputs to our algorithm are colonic surfaces obtained using the marching cubes algorithm after colon segmentation. The algorithm is a level set designed to evolve on 3D surfaces represented by triangular meshes. Level sets are evolving contours that can expand, contract and even split or merge [10]. For the purpose of segmentation, they are designed to deform so as to match an object of interest and stop at its boundaries. The level set we chose to implement, the GAC, evolves according to [11]:


The evolving contour is encoded as the zero level set of the distance function ψ(x,t). In other words, points that verify ψ(x,t) = 0 form the contour. By convention, the distance is negative for points inside the contour and positive for the ones outside:


where d is the distance from point x to the zero level set contour. The first term on the right-hand side of Equation 1 is the propagation term that makes the contour move with velocity c. The second is the curvature term which controls the smoothness of the contour using the mean curvature κ. The third term, the advection term, was introduced by Caselles et al. [11] to lock the contour to the boundary. The parameters α, β and γ weight the importance of each term. The spatial function g, derived from the image or surface to be segmented, encodes the information about the objects’ boundaries and is called the speed function. This function is crucial as it guides the contour.

Level sets have mainly been implemented on rectangular grids. How to implement the GAC on a triangular mesh representing the surface of a 3D object was detailed in [12]. A narrow band strategy was used. In [12] the mesh level set was used to extract the ridgelines of vertebral bodies. In order to adapt it to the problem of segmenting polyps from colonic walls we introduced important innovations.

A. Speed function

A novel speed function was designed. While in rectangular grids guiding features are mainly grey level edges, on 3D surfaces, features are based on curvature properties. Shape Index (SI) and Curvedness (CV) are two meaningful ways of quantifying curvature properties [13]. At a local level on a surface, SI quantifies the nature of the shape (cap, ridge, saddle, rut, cup) while CV quantifies the degree of curvature. In [12] only CV was used. Here we only use SI because CV is not a distinguishing feature. Flat polyps have low CV like most of the colon surface. On the other hand SI is independent of the degree of curvature. Flat or non-flat polyps all have the SI of a cap while polyp necks are mostly made of vertices with SI ranging from saddle to rut. Our speed function must therefore assign high speed values to cap vertices and low speed to saddle and rut shapes. This can be done using the following sigmoid:


Where gSI (V) and SI are respectively the values of the speed function and shape index at vertex V. The two parameters ξ and η are defined as follows [14]:


Such a choice for η and ξ ensures that gSI (V) assigns (i) a speed value increasingly lower than 0.05 to SI values increasingly larger than SI1 and (ii) a speed value increasingly larger than 0.95 to SI values increasingly smaller than SI2. SI values fall in the range of 0 to 1, with the following correspondences between shapes and values: [cap, ridge, saddle, rut, cup] = [0, 0.25, 0.5, 0.75, 1.0] It can be seen that selecting 0.2 and 0.3 for respectively SI2 and SI1 will ensure high speed for caps and low speed for saddle/rut.

B. Seeding and initial contour

For the present study seeds were placed manually in the CT volume. To find the seed on the corresponding mesh we cluster cap vertices (defined as having SI value between 0 and 0.2) using a simple blob-labeling technique on the mesh. Two cap vertices belong to the same blob if they are connected by an edge. Let Nc be the total number of cap vertices in the vicinity of the volume seed. Nc can be taken as an indication of the size of the polyp. We consider the 2 largest cap clusters. If Nc is less than 100 the centroid of the largest cluster is our seed. If it is larger we use the centroids of both clusters as seeds.

In [12] the initial contour was a circle of a fixed size centered on the seed. Such a method worked well for the extraction of vertebral ridgelines. In the present work we used a more adaptive method because polyps have a wide range of sizes. Our new method for placing the initial contour is an iterative region growing algorithm. At each new iteration the neighbors of the vertices added during the previous iteration are examined. If they verify certain conditions based on the speed function they are added to the region. A vertex V is added if gSI (V) as defined by Equation 3 is larger than 0.25. The number of iterations depends on the number of cap vertices Nc. If Nc is larger than 50, the number of iterations is 10, otherwise it is 4. At the end of the iteration process, the boundary between the grown region and the background constitutes the initial contour.

C. Adaptive time step

During the Runge-Kutta discretization of Equation 1, a timestep Δt must be chosen. In [12], the timestep was a fixed quantity. However on a mesh where the length of edges is variable, such a choice is questionable. In the present work we make the timestep adaptive. A specific timestep is now computed for each vertex on the contour. The level set locally advances in the direction normal to the contour. As can be seen from Equation 1 the gradient of the distance function [nabla]ψ has to be computed. For each vertex V on the contour we take the normalized gradient to be the local normal to the contour. We consider the set {Vi} of immediate neighbors of V. Let Vn be the neighbor that lies in the direction closest to the normal at V. We take the timestep V at to be:


where λ is a proportionality constant. We found 0.8 to be a suitable value.

Once the segmentation of a polyp is obtained, we can extract its largest diameter. We go through all the vertices belonging to the polyp. For each of these vertices we find the vertex most remote from it and record the distance between them. The largest of all recorded distances is taken as the polyp’s largest diameter.

To conclude this section we must add that the maximum number of iterations is 50 and that the narrow band is a 2-ring neighborhood around the contour. The values we used for the parameters α, β and γ in Equation 1 are respectively 1, 1.5 and 2, which are the same as in [12].

III. Experimental Results

The dataset used to validate the algorithm consists of 40 polyp surfaces, a prone and a supine surface for 20 polyps. CT was performed using either a four-detector row or eight- detector row CT scanner (GE LightSpeed or Light Speed Ultra, General Electric Medical Systems, Waukesha, Wis.). Scanning parameters were 120 kVp, 100 mAs, 1.25-to-2.5 mm collimation, table speed of 15 mm per second, and reconstruction interval of 1 mm. Standard bowel preparation was performed including faecal tagging and air insufflation.

As the reference standard we used a manual 3D CT reading performed with a commercial colonography software (Viatronix). This software reconstructs a 3D view of the interior of the colon. A built-in caliper is used to trace the polyp’s largest diameter. The sizes of the polyps thus measured ranged from 4.2 to 19.6 mm. Fig. 1 shows the measurements obtained using our novel level set method (LS) versus those of the manual 3D diameter tracing (LM3D). The correlation between the two measures was R=0.825 (p<6×10−11). The intra-class correlation, a measure of agreement between the two readings, was also computed. The intraclass correlation is 0.794 (95% confidence interval 0.707 – 0.87).

Fig. 1
Correlation between level set and manual measures.

We also evaluated the consistency between prone and supine measures. For the 20 polyps, the fractional difference, defined as the absolute difference between prone and supine sizes divided by the mean of those sizes, was computed. For LS and LM3D the means (standard deviations) were respectively 0.12 (0.17) and 1.6 (1.4). The automated method has a lower mean fractional difference. Fig. 2 shows an example of contour evolution on a polyp on a haustral fold and Fig. 3 shows examples of final segmentation for a wide variety of polyps.

Fig. 2
Level set evolution on a polyp on haustral fold. The total number of iterations was 30. Every 6 other frame is shown.
Fig. 3
Nine examples of level set polyp segmentation and measurement. The diameter is measured between the two black dots. LS and LM3D are respectively the level set and manual measures. All measures are in cm. The second and third column respectively shows ...

IV. Conclusion

We have presented a novel algorithm for the linear measurement of polyp sizes. The method consists of a level set that evolves on a triangular mesh representing the 3D surface of the colon. It is guided by curvature features and can extract the ridgeline/crestline formed around the polyp by its merging to the colon wall (polyp neck). The method was validated on 40 polyp surfaces against a manual 3D CT reading. The correlation between manual and automated measures was 0.825.


The authors would like to thank Drs. Perry Pickhardt, J. Richard Choi and William Schindler for providing the CTC data and Viatronix.

This research was supported by the Intramural Research Program of the NIH, NIAMS and CC.

Contributor Information

Sovira Tan, National Institute of Arthritis and Musculoskeletal and Skin diseases, National Institutes of Health, Clinical Center, 10 Center Drive MSC 1182, Bethesda, MD 20892 USA.

Jianhua Yao, Department of Diagnostic Radiology, National Institutes of Health, Clinical Center, Bethesda, MD 20892 USA.

Michael M. Ward, National Institute of Arthritis and Musculoskeletal and Skin diseases, National Institutes of Health, Clinical Center, 10 Center Drive MSC 1182, Bethesda, MD 20892 USA.

Ronald M. Summers, Department of Diagnostic Radiology, National Institutes of Health, Clinical Center, Bethesda, MD 20892 USA.


1. Jemal A, Tiwari RC, Murray T, et al. Cancer statistics, 2004. CA Cancer J Clin. 2004;54:8–29. [PubMed]
2. Gokturk SB, Tomasi C, Acar B, et al. A statistical 3D pattern processing method for computer aided detection of polyps in CT colonography. IEEE Trans on Medical Imaging. 2001;20:1251–1260. [PubMed]
3. Yoshida H, Nappi J. Three-dimensional computer aided diagnosis scheme for detection of colonic polyps. IEEE Trans on Medical Imaging. 2001;20:1261–1274. [PubMed]
4. Summers RM, Yao J, Pickhardt PJ, et al. Computed tomographic virtual colonoscopy computer aided polyp detection in a screening population. Gastroenterology. 2005;129:1832–1844. [PMC free article] [PubMed]
5. Dijkers JJ, van Wijk C, Vos FM, et al. Segmentation and size measurement of polyps in CT Colonography. MICCAI. 2005:712–719. [PubMed]
6. Fletcher JG, Booya F, Melton Z, et al. Automated polyp measurement with CT colonography: preliminary observations in a phantom colon model. AJR. 2007;188:945–952. [PubMed]
7. Taylor SA, Slater A, Halligan S, et al. CT colonography: automated measurement of colonic polyps compared with manual techniques - human in vitro study. Radiology. 2007;242:120–128. [PubMed]
8. Yeshwant SC, Summers RM, Yao J, et al. Polyps: Linear and Volumetric measurement at CT colonography. Radiology. 2006;241:802–811. [PubMed]
9. Burling D, Halligan S, Taylor SA, et al. CT colonography: automatic measurement of polyp diameter compared with manual assessment – an in vivo study. Clinical Radiology. 2007;62:145–151. [PubMed]
10. Sethian JA. Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision and materials science. Cambridge University Press; 1999.
11. Caselles V, Kimmel R, Sapiro G. Geodesic Active Contours. IJCV. 1997;22:61–79.
12. Tan S, Yao J, Ward MM, et al. Computer aided evaluation of Ankylosing Spondylitis using high resolution CT. IEEE Trans on Medical Imaging. 2008;27:1252–1267. [PMC free article] [PubMed]
13. Koenderink JJ. Solid Shape. The MIT Press; 1990.
14. Ibanez L, Schroeder W, Ng L, et al. The ITK software guide. Kitware Inc; 2003.