Abstract:
A system and method for detecting an object in a high dimensional image space is disclosed. A three dimensional image of an object is received. A first classifier is trained in the marginal space of the object center location which generates a predetermined number of candidate object center locations. A second classifier is trained to identify potential object center locations and orientations from the predetermined number of candidate object center locations and maintaining a subset of the candidate object center locations. A third classifier is trained to identify potential locations, orientations and scale of the object center from the subset of the candidate object center locations. A single candidate object pose for the object is identified.

Description:
CROSS REFERENCE TO RELATED APPLICATION  
       [0001]     This application claims the benefit of U.S. Provisional Application Ser. No. 60/827,733, filed Sep. 28, 2006 which is incorporated by reference in its entirety. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The present invention is directed to a system and method for detecting an object in a high dimensional space, and more particularly, to a system and method for using marginal space learning to detect an object in a high dimensional space.  
       BACKGROUND OF THE INVENTION  
       [0003]     Many three dimensional (3D) detection and segmentation problems are confronted with searching in a high dimensional space. For example, a 3D similarity transformation is characterized by nine parameters: three position parameters, three orientation parameters and three scale parameters. It is very expensive to search the entire space for detection of an object. The search for all these parameters becomes computationally prohibitive, even if coarse-to-fine strategies are involved. Moreover, training a discriminative classifier using positive and negative examples for an object with so many parameters is challenging, because hardware limitations only allow a relatively small number of negatives at a time (on the order of 10 6 ). To handle all the possible negative examples, multiple levels of bootstrapping have to be employed, making the whole system even slower.  
         [0004]     But there are many cases when the objects to be detected are naturally aligned in some way. For example, most faces in pictures are approximately horizontal and have approximately the same skin color. Similarly, most hearts in CT scans have approximately the same size and orientation. There is a need for a method for fast detection of an object in a high dimensional space in which the search space can be greatly reduced while still retaining accurate results.  
       SUMMARY OF THE INVENTION  
       [0005]     A system and method for detecting an object in a high dimensional image space is disclosed. A three dimensional image of an object is received. A first classifier is trained in the marginal space of the object center location which generates a predetermined number of candidate object center locations. A second classifier is trained to identify potential object center locations and orientations from the predetermined number of candidate object center locations and maintaining a subset of the candidate object center locations. A third classifier is trained to identify potential locations, orientations and scale of the object center from the subset of the candidate object center locations. A single candidate object pose for the object is identified. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]     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:  
         [0007]      FIG. 1  is a block diagram of an exemplary system for implementing fast detection of an object in a high dimensional space in accordance with the present invention;  
         [0008]      FIG. 2  illustrates a projected distribution for training a classifier using marginal space learning in accordance with an aspect of the present invention;  
         [0009]      FIG. 3  is a flow chart depicting the detection of a Left Ventricle in a Computed Tomography image in accordance with an embodiment of the present invention;  
         [0010]      FIG. 4  is a functional block diagram that illustrates the steps performed to detect the left ventricle using marginal space learning in accordance with an aspect of the present invention;  
         [0011]      FIG. 5  illustrates an example of an annotated object;  
         [0012]      FIG. 6  illustrates a functional block diagram of the LV center localization method in accordance with an aspect of the present invention;  
         [0013]      FIG. 7  is a functional block diagram of the LV center and orientation detection method in accordance with an aspect of the present invention; and  
         [0014]      FIG. 8  illustrates the application of MSL to several other object detection problems in medical imaging. 
     
    
     DETAILED DESCRIPTION  
       [0015]     The present invention is directed to a system and method for detecting an object in a high dimensional image space.  FIG. 1  illustrates a system  100  for detecting an object in a high dimensional image space according to an exemplary embodiment of the present invention. The examples described herein will be directed to the detection of an anatomical structure in a three dimensional medical image. However, it is to be understood by those skilled in the art that the method and system are not limited to detection of anatomical structures and can be used to detect other objects such as faces, pedestrians, vehicles, and traffic signs, without departing from the scope and spirit of the present invention. As shown in  FIG. 1 , the system  100  includes an acquisition device  105 , a personal computer (PC)  110  and an operator&#39;s console  115  connected over a wired or wireless network  120 .  
         [0016]     The acquisition device  105  may be a computed tomography (CT) imaging device or any other three-dimensional (3D) high-resolution imaging device such as a magnetic resonance (MR) scanner or ultrasound scanner.  
         [0017]     The PC  110 , which may be a portable or laptop computer, a medical diagnostic imaging system or a picture archiving communications system (PACS) data management station, includes a central processing unit (CPU)  125  and a memory  130  connected to an input device  150  and an output device  155 . The CPU  125  includes a marginal space learning module  145  that includes one or more methods for detecting an anatomical structure in three dimensional medical images to be discussed hereinafter. Although shown inside the CPU  125 , the marginal space learning module  145  can be located outside the CPU  125 .  
         [0018]     The memory  130  includes a random access memory (RAM)  135  and a read-only memory (ROM)  140 . The memory  130  can also include a database, disk drive, tape drive, etc., or a combination thereof. The RAM  135  functions as a data memory that stores data used during execution of a program in the CPU  125  and is used as a work area. The ROM  140  functions as a program memory for storing a program executed in the CPU  125 . The input  150  is constituted by a keyboard, mouse, etc., and the output  155  is constituted by a liquid crystal display (LCD), cathode ray tube (CRT) display, printer, etc.  
         [0019]     The operation of the system  100  can be controlled from the operator&#39;s console  115 , which includes a controller  165 , e.g., a keyboard, and a display  160 . The operator&#39;s console  115  communicates with the PC  110  and the acquisition device  105  so that image data collected by the acquisition device  105  can be rendered by the PC  110  and viewed on the display  160 . The PC  110  can be configured to operate and display information provided by the acquisition device  105  absent the operator&#39;s console  115 , by using, e.g., the input  150  and output  155  devices to execute certain tasks performed by the controller  165  and display  160 .  
         [0020]     The operator&#39;s console  115  may further include any suitable image rendering system/tool/application that can process digital image data of an acquired image dataset (or portion thereof) to generate and display images on the display  160 . More specifically, the image rendering system may be an application that provides rendering and visualization of medical image data, and which executes on a general purpose or specific computer workstation. The PC  110  can also include the above-mentioned image rendering system/tool/application.  
         [0021]     Marginal Space Learning (MSL) takes advantage of the fact that most data have some mildly invariant properties (e.g., hearts in CT images have approximately the same size and orientation). As such, a large part of the space can be eliminated by detection in a marginal space where only some parameters are considered and the rest are integrated out. There are also many cases when the objects to be detected are naturally aligned in some way. This natural alignment can be exploited to train a classifier in a projected distribution as shown in  FIG. 2 , which exists over a marginal space of smaller dimension (e.g., a 3-parameter left ventricle center position space instead of a 9-parameter left ventricle similarity transformation space. Then, the search space can be restricted to candidates whose projections to the marginal space have high probability values based on the trained marginal space classifier.  
         [0022]     In MSL, a classifier is trained on a marginal space in which some of the variables are ignored. For example, a classifier trained on p(y) can quickly eliminate a large portion of the search space. Another classifier is trained on the remaining space to obtain the final classification results.  
         [0023]     An embodiment of the present invention will now be described in the context of an example in which detection of a Left Ventricle (LV) in a Computed Tomography (CT) image is performed. MSL is used to detect the LV up to a similarity transformation in 3D CT images.  FIG. 3  illustrates a flow chart that depicts an exemplary method for detecting an LV in accordance with the present invention.  FIG. 4  is a functional block diagram that illustrates the steps performed to detect the LV using marginal space learning in accordance with an aspect of the present invention.  
         [0024]     An image of an LV is received ( 402 ). A classifier is used to find the 3D location x=(x, y, z) of the LV center (step  302 ,  404 ). The classifier is trained in the marginal space of LV center locations. For each 3D input data, the best 400 locations are kept for further evaluation (step  304 ). It is to be understood by those skilled in the art that the number of locations kept for further evaluation can vary without departing from the scope and spirit of the present invention.  
         [0025]     For the 400 candidate locations, another classifier is used to keep the most promising 3D locations and orientations (x, θ)=(x, y, z, θ 1 , θ 2 , θ 3 ) of the LV (step  306 ,  406 ). Thus, this classifier is trained in the 6-dimensional marginal space of locations and orientations. The best 50 candidate locations and orientations are kept for further evaluation. It is to be understood by those skilled in the art that the number of candidate locations and orientations kept for further evaluation can vary without departing from the scope and spirit of the present invention. Finally, a trained classifier is used to detect the LV up to a 9-dimensional similarity transformation (i.e., position, orientation and scale) (step  308 ,  408 ) 
 
T=(x, θ, s)=(x, y, z, θ 1 , θ 2 , θ 3 , s 1 , s 2 , s 3 )  (1) 
 
 A single candidate is the output of this stage (step  310 ). 
 
         [0026]     The training set is comprised of a number of image volumes. The shape of each LV in the training image volumes is annotated using a 3D mesh comprising 514 points.  FIG. 5  shows an example of an LV that has been annotated with a 3D mesh  502  and a corresponding bounding box  504 . The LV apex, the A3C plane and the main axis are used to align the shapes to each other. Principal Component Analysis (PCA) is performed on the aligned shapes and the best 50 PCA bases are used to describe the shape variability.  
         [0027]     The method described in  FIGS. 3 and 4  will now be described in greater detail. To detect the LV center location  402 , a classifier is trained based on 3D Haar features. For better data alignment and performance, the LV center is detected in image volumes which are subsampled to a voxel size of 3 mm. At this resolution, a volume has a size of approximately 50×50×60 voxels. The training set comprises a number of image volumes (e.g., 100 image volumes), all resized at 3 mm voxel size.  
         [0028]     The 3D Haar filters are chosen from inside a horizontal cube of size 31×31×31 voxels centered at the sample location. A pool of about 10,000 Haar features is selected for training. The number of positives is increased by adding positives perturbed by 1-2 voxels from their true location, for robustness. This allows for about 6000 positives to be obtained from 100 training image volumes. The negatives are chosen randomly inside the image volume, at a distance of at least 5 voxels from the true center location. About 1 million negatives are used for training.  
         [0029]     A Probabilistic Boosting Tree (PBT) is used for training and detection, because it returns a probability between 0 and 1 for each sample. The PBT is described in detail in co-pending patent application Ser. No. 11/366,722, filed Mar. 2, 2006 and entitled “Probabilistic Boosting Tree Framework for Learning Discriminative Models,” which is incorporated by reference in its entirety. A PBT is trained with five levels of which the first two were enforced as cascade.  
         [0030]      FIG. 6  illustrates a functional block diagram that shows the basic LV center detection method. The input image volume  602  is resized at 3 mm voxel resolution. The LV center detection uses 3D Haar features in the image volume  604 . The Haar features are chosen from inside a box of size 31×31×31 voxels which is shown by the dotted lines centered at the sample location. The detection result is a small blob of voxels around the true center location  606 . The best 400 locations are kept for further evaluation, while the rest are discarded. An evaluation of this level indicated that all the true center locations are among the 400 candidate locations. The method reduces the search space of location from about 50×50×60=150,000 to 400, which is a reduction in magnitude of more than 300.  
         [0031]     The second classifier works in the 6-dimensional space of locations and orientations (x, θ). This space is limited to values (x, θ) for which the location x is among the 400 candidates obtained by the location detector and therefore this 6-dimensional space has already been made more than 300 times smaller.  
         [0032]      FIG. 7  is a functional block diagram of the method in which orientations for the locations are found. The locations for which the orientations are to be found are determined by the center detection method which results in a cluster of detected centers  702 . The LV orientation detection uses 3D curvature features to detect orientations  704 . Each feature is computed as a specific voxel location inside a box of size 24×24×24 voxels, translated and rotated by the sample&#39;s position and orientation. Inside this box, the locations are organized on a 9×9×9 lattice, so there are 729 different locations where a feature can be computed. At each of these locations, there are 71 different combinations (sum, product, quotient, inverse trigonometric functions, etc.) of the gradient, min and max curvatures, principal directions and volume data. This gives 729×71=51,759 features. Moreover, there are three scales at which the features are computed: 3 mm, 6 mm, and 12 mm, obtaining a total of about 150,000 features. The positives and negatives are chosen to have the location x among the 400 candidates from the first stage. The best 50 candidates (x, θ) are kept for further evaluation  706 .  
         [0033]     An important issue that appears is how to obtain a meaningful distance between the samples and the ground truth. This distance will be used to generate the positives and negatives, since samples which are really close to the ground truth should be considered positives, while samples which are further than some threshold are negatives.  
         [0034]     To compute the distance to the ground truth, each sample (x, θ) is augmented with the mean scale so which is obtained from the statistics of the training data. Using the resulting similarity transformation T=(x, θ, s 0 ), a rescaled mean shape is obtained. The mean shape was obtained when the Procrustes analysis was performed on the 98 training shapes. Thus the average point-to-point distance between the corresponding resealed mean shapes is the distance between two samples.  
         [0035]     The positives are chosen to have a distance of at most 6 mm, while the negatives are at a distance of at least 15 mm. From the output of the detector, the best 50 candidates (x, θ) are kept, the rest being discarded.  
         [0036]     The dimensionality of the search space is increased again to add the LV scale. The similarity transformation T=(x, θ, s) is in a 9-dimensional space, but the first 6 dimensions (x, θ) are restricted to take only 50 values obtained from the previous stage. The same sample pool of features is used as in the LV orientation detection stage, with the difference now that for each sample (x, θ, s), the box in which these features are computed is now (x, θ, 4/3s). A single candidate is chosen after this stage.  
         [0037]     A similar approach can be used to detect the Left Atrium (LA). To detect the LA up to a similarity transformation in 2D, a 5-dimensional space is searched: position (x,y), orientation θ and scale (s,a) (scale and aspect ratio). Using the MSL approach three classifiers are trained. A first classifier is trained to detect the LA position. Because the LA in the ultrasound data exhibits a very large degree of variability in size, a very coarse size is also estimated with three values small, medium and large. The best 1000 candidates are kept for further processing. A second classifier is trained to infer for each candidate the LA orientation and one scale parameter. Again, the best 1000 candidates are kept for further processing. A final classifier is trained to infer the aspect ratio for each of the 1000 candidates and the average of the best 20 detections are reported as the detection results.  
         [0038]     MSL is general approach and can be applied to many challenging 2D and 3D object detection and segmentation tasks in medical imaging.  FIG. 8  shows the application of MSL to detect catheter tips in X-ray images ( 802 ), ileocecal valves ( 804 ) and livers ( 806 ) in abdominal CT, heart chambers in ultrasound images ( 808 ), and heart chambers in MRI ( 810 ).  
         [0039]     Having described embodiments for a system and method for detecting an object in a high dimensional space, 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 chances 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, what is claimed and desired protected by Letters Patent is set forth in the appended claims.