Method for detecting polyps in a three dimensional image volume

Field of the Invention [0002] The present invention is directed to a method for detecting polyps in three dimensional image volume, and more specifically, to a method for automatically detecting polyps in three dimensional colon image volume by using a probabilistic approach.

Background of the Invention [0003] Colon cancer is one of the leading causes of death in the U.S. The number of deaths can be largely reduced if polyps can be detected and treated at their early stage of development. Virtual colonoscopy is a new technology being developed to help doctors find polyps in three dimensional (3D) computed tomography (CT) image data. However, it currently requires that the colon be physically cleansed prior to the CT scan. This is very inconvenient and prevents virtual colonoscopy from being a general screening tool for a large population. In addition, years of training are required for a doctor to successfully identify polyps in the 3D CT image.

[0004] The size of a polyp is measured by its diameter. Usually, a polyp smaller than 6mm. is not of much clinical significance. Polyps bigger than 9mm are very likely to be cancers and can be identified by doctors easily. It is most important for a polyp detection system to be able to detect polyps in the 6~9mm range since they may develop into cancers.

[0005] The task of automatic polyp detection is very challenging. First, the CT data is taken without bowel cleansing in order to minimize the inconvenience to patients. Tagged materials, such as stool, though mostly depicted as bright areas in the image, are a big distraction. Second, polyps of

2005296007 15 Jul 2009 interest are very small and don't have unique intensity patterns, nor have any special shapes. It is hard to distinguish them from the colon wall, especially when they are surrounded by tagged material. Third, the volumetric data to be processed is massive (e.g., 400 x 512 x 512), which eliminates the possibility of using any computationally expensive methods. There is a need for a method for detecting polyps in three dimensional colon image data by using a generative model to capture the underlying generation process of the polyp.

[0005a] Any discussion of the prior art throughout the specification should in no way be considered as an admission that such prior art is widely known or io forms part of common general knowledge in the field.

Summary of the Invention [0005b] It is an object of the present invention to overcome or ameliorate at least one of the disadvantages of the prior art, or to provide a useful alternative. [0006] The present invention, in its preferred form, is directed to a method for detecting target objects in a three dimensional (3D) image volume of an anatomical structure. A set of candidate locations in the image volume are obtained. For each candidate location, sub-volumes of at least two different scales are cropped out. Each sub-volume comprises a plurality of voxels. For each of the sub-volumes, each sub-volume is rotated in at least two different orientations. A shape classifier is applied to each sub-volume. If the voxels in the sub-volume pass the shape classifier, a gradient direction is computed for the voxels. If the gradient direction for the voxels is one of a predefined orientation, a probability classifier is applied to the voxels. A probability measure computed by the probability classifier as a confidence measure is used for the sub-volume. If the confidence measure is above a predetermined threshold value, the sub-volume is determined to contain the target object. [0006a] According to a first aspect of the invention there is provide a method for detecting polyps in a three dimensional (3D) image volume of an anatomical structure comprising the steps of:

receiving a three dimensional (3D) image volume of an anatomical structure:

-22005296007 15 Jul 2009 obtaining a set of candidate locations in the image volume;

for each candidate location, crop out three sub-volumes wherein each sub-volume comprises a different scale and a plurality of voxels;

for each of the three sub-volumes, obtain two additional sub-volumes (for a total of nine sub-volumes) at different orientations by rotating each sub-volume in two different directions;

for each of the nine sub-volumes, apply a shape classifier thereto; discard voxels of the sub-volume that are not identified by the shape classifier as being on the surface of a polyp, and for each voxel of the sub10 volume that is identified by the shape classifier as being on the surface of a polyp, perform the following;

(a) compute a gradient direction for the voxel;

(b) if the gradient direction for the voxel falls into one of a plurality of orientations, apply a probability classifier cascade to the voxel;

(c) if the voxel passes the probability classifier cascade, its bounding box is remembered and its corresponding probability is outputted as a confidence measure therefor; and (d) repeat (a-c) for each remaining voxel of the sub-volume; if bounding boxes exist after each of the nine sub-volumes has been analyzed, the candidate with the bounding box having the highest confidence measure is determined to be a polyp; and outputting the image volume with at least one polyp identified therein.

[0006b] According to a second aspect of the invention there is provide a system for determining if candidate locations identified in a three dimensional (3D) image volume of an anatomical structure correspond to a polyp, comprising:

a memory device for storing a program;

a processor in communication with the memory device, the processor operative with the program to:

receive a three dimensional (3D) image volume of an anatomical structure;

obtain a set of candidate locations in the image volume;

-2a2005296007 15 Jul 2009 for each candidate location, crop out three sub-volumes, wherein each sub-volume comprises a different scale and a plurality of voxels for each of the three sub-volumes, obtain two additional sub-volumes (for a total of nine sub-volumes) at different orientations by rotating each sub-volume in two different directions;

for each of the nine sub-volumes, apply a shape classifier thereto; discard voxels of the sub-volume that are not identified by the shape classifier as being on the surface of a polyp, and for each voxel of the sub10 volume that is identified by the shape classifier as being on the surface of a polyp, the processor is further operative with the program to:

(a) compute a gradient direction for the voxels;

(b) if the gradient direction for the voxels falls into one of a plurality of orientations, apply a probability classifier cascade to the voxels;

is (c) if the voxels passes the probability classifier cascade, its bounding box is remembered and its corresponding probability is output as a confidence measure therefor; and (d) repeat (a-c) for each remaining voxel of the sub-volume; if bounding boxes exist after each of the nine sub-volumes has been analyzed, the candidate with the bounding box having the highest confidence measure is determined to be a polyp; and output the image volume with at least one polyp identified therein.

[0006c] Unless the context clearly requires otherwise, throughout the description and the claims, the words “comprise”, “comprising”, and the like are to be construed in an inclusive sense as opposed to an exclusive or exhaustive sense; that is to say, in the sense of “including, but not limited to”.

Brief Description of the Drawings [0007] Preferred embodiments of the present invention will be described below in more detail, wherein like reference numerals indicate like elements, with reference to the accompanying drawings:

[0008] FIG. 1 illustrates different views of a 3D CT image of a colon;

-2b2005296007 15 Jul 2009 [0009] FIG. 2 is a schematic diagram of an exemplary Computed Tomography (CT) system in accordance with the present invention;

<img file="AU2005296007B2_D0001.tif" />

-2cWO 2006/044242

PCT/US2005/036123 [0011] FIG. 4 illustrates a snap shot of an interface used to visualize and process 3D colon data in accordance with the present invention;

[0012] FIG. 5a-5c illustrates how candidate data is aligned in accordance with the present invention;

[0013] FIG. 6 illustrates a typical polyp and its augmented data in accordance with the present invention;

[0014] FIG. 7 illustrates examples of 1D, 2D and 3D Haar wavelet filters in accordance with the present invention;

[0015] FIG. 8 illustrates a probability boosting tree in accordance with the present invention;

[0016] FIG. 9 illustrates one of the Haar wavelet filters of FIG. 7 rotated in accordance with six major orientations in accordance with the present invention;

[0017] FIG. 10 illustrates a probability boosting tree and its cascade in accordance with the present invention;

[0018] FIG. 11 illustrates trained shape classifiers in accordance with the present invention;

[0019] FIG. 12 illustrates a sub-volume shown at three different scales and three different orientations in accordance with the present invention; and [0020] FIGs. 13a and 13b are a flow chart that illustrates a method for detecting polyps in accordance with the present invention.

Detailed Description [0021] The present invention is directed to a method for detecting polyps in three dimensional (3D) colon image volume by using a learning based approach for pulmonary nodule detection in 3D volumes. A general generative model is defined to capture the underlying generation process of an object, such as a polyp. Integral volumes and 3D Haar filters are designed for fast computation of features. A cascade of Probabilistic Boosting Trees (PBT) is adopted to learn the classifiers. The present invention is capable of automatically selecting a thousand features from a pool of 50,000 candidate features. The present invention does not require pre-segmentation of the

WO 2006/044242

PCT/US2005/036123 data, which is specifically useful in detecting polyps in uncleansed data, such as an uncleansed colon.

[0022] The 3D volume image data can be obtained using different imaging modalities such as Computed Tomography (CT), X-ray or Magnetic Resonance Imaging (MRI). FIG. 1 illustrates a number of views of a colon. The first image 102 shows a complete CT volume of a section of a colon. There are two types of objects inside a colon, air and stool. Though most of them appear to be either very dark (e.g., air) or very bright if successfully tagged, there are still a large portion of residual materials which have similar intensity values as normal tissue due to poor tagging. Residual materials (e.g., stool) are tagged to make them appear bright under CT and can be removed electronically. The middle image 104 shows a CT image of a physically cleansed colon. Image 106 shows a CT image of an uncleansed colon which has been tagged.

[0023] The present invention uses a detection method based on boosting and which uses 1D, 2D and 3D features which are combined as candidate weak classifiers. Special features that directly account for the underlining regularity are incorporated. All the features have different costs and the present invention automatically takes into consideration the associated costs in determining the feature selection. The present invention pursues feature selection as multiple chains to explore ways of combining features so as to minimize overall error functions.

[0024] FIG. 2 schematically depicts an exemplary Computed Tomography (CT) system in accordance with the present invention. The CT system in conjunction with a Computed Aided Detection (CAD) system can be used to perform a non-invasive procedure on a patient to screen for various medical conditions. Examples of such procedures are virtual colonoscopies or chest screenings for the presence of lesions and possibly cancerous tissue. In addition, system can be used to detect lymph nodes and polyps in the lungs. It is to be understood by those skilled in the art that other imaging modalities can be used without departing from the scope and spirit of the present invention. For example, magnetic resonance imaging (MRI), fluoroscopy or ultrasound imaging could also be used to obtain the imagines.

WO 2006/044242

PCT/US2005/036123

For purposes of explanation, the present invention will be described in the context of use of an exemplary Computed Tomography (CT) system. CT images of a colon are obtained which may then be segmented and used to detect polyps. However, as indicated above, the method of the present invention can also be used to detect polyps in lung nodules or lymph nodes. [0025] The CT is equipped with an X-ray source 1, emitting a pyramidal X-ray beam 2, whose marginal rays are represented by the dot-dashed lines in FIG. 2 that penetrates an object 3 to be examined, for example, a patient, and that is incident on a radiation detector 4. The X-ray source 1 and the radiation detector 4 are, in the exemplary embodiment, mounted opposite to one another on an annular gantry 7.

[0026] The X-ray source 1 and the radiation detector 4 thus form a metrological system that can be rotated around the system axis 8 so that the patient 3 can be X-rayed at various projection angles relative to said system axis 8 and at various positions along the system axis 8. The resultant output signals of the individual detector elements are read out by a data acquisition system 10. The signals are sent to a signal processor 12 that computes an image of the patient 3 that, in turn, can be displayed on a monitor 13.

[0027] The images scanned by the CT system and computed by the signal processor 12 are transmitted to a CAD system 20 for further processing. The CAD system 20 tags the residual materials which may or may not be electronically removed. A learning based approach is used to detect polyps in the colon.

[0028] In accordance with the present invention, polyps are detected directly in the original data with tagged materials. FIG. 3 shows 12 polyps out of 65 positive samples. This approach is more challenging since the tagged materials provide a significant distraction. Though most polyps appear to have a bun shape, they are usually small and hard to distinguish, with folds, especially when surrounded by tagged materials. It is also feasible to use an intermediate approach in which stools that are very bright are removed and then detection procedures are employed to locate polyps.

[0029] In accordance with the present invention, an interface based on OpenGL Volumizer is used to visualize and process the 3D colon data.

WO 2006/044242

PCT/US2005/036123

However, it is to be understood by those skilled in the art that other interfaces can be used without departing from the scope and spirit of the present invention. FIG. 4 illustrates a snap shot of the interface. The window at the lower right 408 shows the 3D visualization of the whole volume. Users can rotate the volume and cut through to view different slices. The other three windows 402-406 display the slices at the XY, YZ and XZ planes.

[0030] Once the 3D image data of the colon is obtained, the images is scanned to look for objects in the image that have a high degree of curvature. These objects are collected as candidates to be analyzed to determine if the objects are polyps as will be described in more detail hereinafter. Next, classifiers are trained which are used to detect the polyps. Each 3D input image volume is assumed to be isotropic. Detection of polyps is difficult because of the large variations in shape of the polyps. For a small or medium sized polyp, it often observes a regular shape of a half hemisphere. When the polyp becomes larger, it starts to develop a variety of shapes due to interactions with the colon wall and other structures.

[0031] In addition, polyps appear in all possible orientations on the colon wall. A generative model is created to train the set of classifiers. A dictionary ψ is defined where ψ = (Δι, Δ₂, ...) and Aj is a 2D/3D template.

Each object instance x is assumed to be generated by a transformation function T on ψ. A set of typical parameters in Τ, Θ = {/, s, Θ, 0. a} can be /the number of templates used, s- scale, θ - rotation, 0 - deformation, and others which are represented by a. If y is the label of x, then y= +1 when x is an object of interest (positive) and y= -1 when x is not an object of interest (negative). The probability of x can be modeled by a generative model as

F(x|G;yi|j) = 1βχρ{-||χ-Τ(Θ,ψ)||} (1)

Where || || defines a distance measure between x and T(), and Z is the partition function Z = ^exp {-||x-T||}.

a:

[0032] In a discrimative approach, a sample x is classified based on the posterior

WO 2006/044242

PCT/US2005/036123

P(y/x) (2) [0033] In an alternative approach, parameters in Θ can be explicitly computed

P(yt*) = Σ PA I θι ’ ^χ)τ(θι I x) (3)

In accordance with eqn. (3), one objective is to reduce the complexity of the training samples. Parameters are chosen so that Θ, = {s,6,a} where s is the scale, θ is the orientation, and a is the aspect ratios of a polyp w.r.t. its depth, height, and width. A template of size 24 x 24x16 is created whose 2D view is shown in FIG. 5a. An orientation sphere is divided into 14 zones, 4 of which are along the major axes as shown in FIG. 5b. Each candidate object or polyp is aligned to the major orientation as shown in FIG. 5c.

[0034] In the orientation zone rl, the possible detailed orientations (θ_χ, 0₂) are sampled to augment the training data. As a result, specific values of (0₁₅0₂) don’t need to be searched. In addition, the training samples are augmented from 130 to about 13,000 which reduce the chance of overfitting. FIG. 6 illustrates a typical polyp sample after alignment and its three dimensional augmented data.

[0035] In accordance with the present invention, a sub-volume based on a template of 24x24x16 is classified. Positive samples are aligned and augmented to one of the major directions with its tip. The features used for polyp detection should have a number of properties. The features should be scale and aspect ratio invariant to a certain degree. In order to accomplish this, different possible scales and aspect ratios are used in the detection phase as will be described in further detail hereinafter. The features should be fast and easy to compute. The features should be informative for the objects of interest.

[0036] In accordance with the present invention, an integral volume and 3D Haar filters are used for polyp detection. FIG. 7 illustrates 1D, 2D and 3D Haar filters that are used in the present invention. At each location (x_i; y_1f z-ι),

WO 2006/044242

PCT/US2005/036123 the integral volume is computed J J JV(x, y, z)dxdydz. The computational cost xlylzl of computing Haar filters is largely reduced since only the sum of the values of the corners of the Haar filter in the integral volume need to be computed. Because the procedure of aligning data and training classifiers is time consuming, the features are preferably semi-rotation invariant. That is, once the classifier for one major direction rl is trained, the classifiers for the other orientations are automatically derived. Haar filters meet this requirement for six major orientations as shown in FIG. 9. For the other eight orientations, the 3D data in the detection stage is rotated rather than having another set of classifiers for them. This reduces the training effort and the chance of overfitting since virtually there is only one classifier trained.

[0037] In accordance with the present invention, a probabilistic boosting tree (PBT) is used to explicitly compute the discriminative model. In the training stage, a tree is recursively constructed in which each tree node is a strong classifier. The input training set is divided into two sets, left and right ones, according to the learned classifier. Each of which is then used to train the left and right sub-trees recursively. Each level of the tree is an augmented variable. Clustering is intrinsically embedded in the learning state with clusters automatically discovered and formed in a hierarchical manner. PBT does training and testing in a divide-and-conquer manner and outputs the overall discriminative model as:

raj ««·?

Zl,a:)₅..., (4) [0038] Examples of PBTs are shown in FIGs. 8 and 10. Each tree level /,· is an augmented variable. To facilitate the process of bootstrapping and

WO 2006/044242

PCT/US2005/036123 reduce the number of negatives for PBT, a cascade approach is used as shown in FIG. 10. Each stage of PBT has a probability as a threshold. Those whose p(y | x) is bigger than the probability will pass into the next stage. [0039] The following describes an example for training the polyp classifiers in accordance with the present invention. In the example, 80 volumes are used for training in which there are 130 polyps annotated and segmented by radiologists. First, an AdaBoost classifier is trained to classify whether a voxel is on the surface of a polyp or not. This classifier is used to quickly screen out a majority of the voxels that are on a flat surface. The features used are intensity, gradient, Gaussian curvatures, mean curvatures, etc. A general AdaBoost algorithm is trained to combine these features.

Some of the results are illustrated in FIG. 11.

[0040] Second, a classifier is trained which comprises a cascade of PBT classifiers. Based on the segmentation of a polyp and its annotation on the tip, the bounding box for it can be precisely located. Training samples are aligned and augmented to 13,000 positives of size24x24x16. In the 80 training volumes, those voxels whose gradient is along the major rl orientation are randomly sampled and have passed the first basic shape classifier. Also, these voxels should not be on the surface of any annotated polyps. The 3D sub-volumes are then cropped out of size 24 x 24x16aligning these voxels with the tip position in the template. There are in total 30,000 of these negative samples obtained. Using these positives and negatives, a PBT is trained with maximum 9 levels and 22 weak classifiers for each AdaBoost node.

[0041] Once a PBT is trained, it is used to run through the training volumes to perform bootstrapping to obtain more negatives. There are five PBT trained producing a cascade of five levels. Since each PBT computes the discriminative model p(y | Θ₁₅χ), the threshold can be easily adjusted to balance between detection rate and number of false positives. The first two levels are set to have nearly 100% detection rate. Each PBT comprises approximately 1,000 weak classifiers on the Haar filters. Based on the trained cascade of PBT, the other 5 cascades are obtained by rotating the Haar filters as illustrated in FIG. 9.

WO 2006/044242

PCT/US2005/036123 [0042] In accordance with the present invention, a method for detecting polyps will now be described with reference to FIGs. 12 and 13a-b. A candidate generation method is used too obtain a set of candidate locations (step 1302). An example of a candidate location is illustrated in FIG. 12. For each candidate location, 9 sub-volumes are created. The 9 sub-volumes comprise 3 volumes at different scales with each volume rotated in 3 orientations as illustrated in FIG. 12 . The top row in FIG. 12 shows the subvolumes at 3 different scales. This is done to cover the possibility of different sizes at a large scale. The bottom row shows 3 sub-volumes at different orientations. The figure to the right shows the definitions of rl, r2 and r3 and how the rotated volumes are obtained.

[0043] More specifically, for each candidate location in the volume, sub-volumes are cropped out at different scales (step 1304). For example, the sub-volume may be rescaled so that there is one sub-volume at half the original scale, one sub-volume at the original scale and a third sub-volume at one and a half times the original scale. It is to be understood by those skilled in the art that the three different scales used in the polyp detection method may differ based on clinical results and to reduce the likelihood of detecting false positives without departing from the scope and spirit of the present invention. The three sub-volumes are then resized to volumes of 60X60X60 (step 1306).

[0044] For each of the three sub-volumes, three additional sub-volumes are obtained at different orientations. Each sub-volume is rotated from direction /2 to direction rl. The sub-volumes are also rotated from direction /3 to rl (step 1308). This results in the creation of 9 sub-volumes for each candidate location.

[0045] For each of the 9 sub-volumes, the first layer shape classifier is run to rule out those voxels that are not on the surface of a polyp (step 1310). For each voxel that passes the shape classifier, its gradient direction is computed (step 1312). If the gradient direction falls into one of the six major orientations, the corresponding cascade of PBT classifier is fired (step 1314). Next, 96 possibilities of combinations of different size and aspect ratios of templates are tried by considering the current voxel being the tip of the

WO 2006/044242

PCT/US2005/036123 template (step 1316). The 96 possibilities correspond to 96 Haar filters which have been computed offline. It is to be understood that a different number of possibilities can be used to analyze the voxels without departing from the scope and spirit of the present invention.

[0046] If the voxel passes the cascade, the bounding box is remembered and its corresponding probability is outputted in the last layer of the cascade as a confidence measure (step 1318). This process is repeated for each of the 9 sub-volumes (step 1320). If bounding boxes exist after each of the sub-volumes has been analyzed, the bounding box having the highest confidence measure is used and the candidate is determined to be a polyp (step 1322).

[0047] More time is spent in the detection stage which results in the reduced complexity of the training samples. In addition, only one cascade of PBT for rl is trained and used for all other directions. This helps to improve the generality of the detector and results in greater efficiency. It can be seen that features are much easier to obtain if samples are in the upper-right position than slanted. For each voxel in the sub-volume, a shape classifier is run as well as a cascade PBT at different scales and aspect ratios. The best bounding box is outputted if it is found to be a polyp.

[0048] Having described embodiments for a method for detecting polyps in three dimensional colon image data, it is noted that modifications and variations can be made by persons skilled in the art in light of the above teachings. It is therefore to be understood that changes may be made in the particular embodiments of the invention disclosed which are within the scope and spirit of the invention as defined by the appended claims. Having thus described the invention with the details and particularity required by the patent laws,