In 2017, the ImageCLEF benchmark proposed a task based on CT (Computed Tomography) images of patients with tuberculosis (TB). This task was divided into two subtasks: multi-drug resistance prediction, and TB type detection. In this work we present a graph-model of the lungs capable of characterizing TB patients with di erent lung problems. This graph contains a xed number of nodes with weighted edges based on distance measures between texture descriptors computed on the nodes. This model attempts to encode the texture distribution along the lungs, making it suitable for describing patients with di erent tuberculosis types. The results show the strength of the technique, leading to best results in the competition for multi-drug resistance (AUC = 0.5825) and good results in the tuberculosis type detection (Cohen's Kappa coef. = 0.1623), with many of the good runs being fairly close.
ImageCLEF (the image retrieval and analysis evaluation campaign of the
CrossLanguage Evaluation Forum, CLEF) has organized challenges on image
classication and retrieval since 2003 [
The ImageCLEF 2017 [
Following the same approach, more complex features are used in this work. The descriptors based on the HU distribution were replaced by 3D texture features. Moreover, a deep analysis of the edges of the graph are helpful to describe the tuberculosis patterns. Our hypothesis is that a holistic analysis of the relations between regional texture features is able to encode subtle di erences between patients with di erent tuberculosis type and drug resistance.
The following section contains a brief overview of the subtasks and dataset of
the ImageCLEF 2017 tuberculosis task. More detailed information on the task
can be found in the overview article [
The ImageCLEF 2017 TB task proposed two subtasks: i) Multi-drug resistance
(MDR) prediction, and ii) Tuberculosis type (TBT) detection. The MDR task
is a 2-class problem and the TBT task contains 5 classes. For both subtasks
volumetric chest CT images with di erent voxel sizes and automatic segmentations
of the lungs were provided. No other lung segmentation was attempted in this
work and the masks provided were used. These masks were obtained with the
method described in [
The competition was divided into two phases. In the rst phase, the organizers released for each subtask a set of patient CT volumes as training set with their lung masks and ground truth labels. In the second phase, the test set with its lung segmentations but no labels were provided. The evaluation on the test data was performed by the organizers after the scheduled deadline for all runs that were submitted in time. The number of CT volumes for each task and set are speci ed in Tables 1 and 2. 3
This section details the process for the feature vector extraction from the CT images provided by the ImageCLEF TB task. The same technique was applied for describing the patients of both subtasks. This technique consists of creating graph-models of the lungs, with nodes based on a geometrical atlas and weighted edges encoding dissimilarities between 3D texture descriptors of each atlas region. 3.1
The approach is based on 3D texture features. These features require having isometric voxels. The rst step of our approach is to make the 3D images and masks provided by the organizers isometric. After analyzing the multiple resolutions found in the dataset and inter-slice distances, we opted for a voxel size of 1 mm to capture a maximum of information. 3.2
To build a graph with a xed structure over the lung physiology we rst need
a localization system. In this case we chose the atlas developed by Depeursinge
et al. in [
Two state-of-the-art 3D texture features were selected to describe the texture inside the lung. The rst method is a histogram of gradients based on the Fourier transform HOG (FHOG) introduced in [10]. 28 3D directions are used for the histogram obtaining a 28-dimensional feature vector per image voxel (fH 2 R28).
The second approach is the locally-oriented 3D Riesz-wavelet transform introduced by Dicente et al. in [11]. The parameters that obtained the best results in this article were used in the approach. These are: 3rd-order Riesz transform, 4 scales and 1st-order alignment. This con guration results in 40-dimensional feature vectors for each image voxel. The feature vector for a single voxel is then 10-dimensional containing the energy of each lter along the 4 scales (fR 2 R10). Nodes Using as a base the 36-region atlas, the texture information from the 3D textural features was embedded in a 36-node graph. With this xed number of nodes, we de ned several graphs varying the number of edges and their weights. The following notation is used: given a patient p 2 P and its 36-region atlas Ap of the lungs with regions fr1; : : : ; r36g 2 Ap we let Gp be the 36-node graph of the patient p with nodes fN1; : : : ; N36g. Each node Na represents one region ra 2 Ap.
Edges Three graphs were de ned.
{ Graph Full : This is the fully connected 36-node graph. For every pair of nodes Na and Nb with a 6= b there exists an undirected edge Ea;b. The total number of edges in this case is 630 ( 36235 ). { Graph 66 : Based on the region adjacency de ned by the atlas Ap, in this case, there exists edge Ea;b between nodes Na and Nb if regions ra and rb are 3D adjacent in the atlas. This graph contains 66 edges in total. { Graph 84 : The last graph has the same 66 edges as Graph 66. Moreover, it has 18 additional edges connecting each pair of nodes representing opposite regions inside the atlas.
The three graphs are shown in Figure 2.
Graph Full
Graph 66
Graph 84
Weights The graphs were always undirected weighted graphs. The weight wa;b of an edge Ea;b was de ned in several ways based on the relations between the features of the corresponding nodes Na and Nb. Four measures were used to compute the weights. Considering fa and fb the feature vectors of regions ra and rb respectively, the measures used are: { Correlation (corr): wa;b = corr (fa; fb) { Cosine similarity (cos): wa;b = cos(fa; fb) { Euclidean distance (euc): wa;b = jjfa fbjj2 { Norm of the sum (sumNorm): wa;b = jjfa + fbjj2 Feature Vector of a Region Several feature vectors can be extracted from a region r. Section 3.3 introduced the features extracted for a single voxel, fH and fR. Given a region ra, we extracted the mean ( a) and standard deviation ( a) of the features inside the region, i.e.: a(fH ), a(fH ), a(fR), and a(fR). Feature Vector of a Patient Finally, the feature vector wp of a patient p, is de ned as the ordered concatenation of the weights wa;b 2 Gp. Depending on the graph used, this feature vector can be 630-, 66-, or 84-dimensional. Feature Normalization The last step before using the feature vectors wp with the classi er is to normalize them along the set of training patients PTRN . Each component wp;i of a vector wp corresponds to the weight of a di erent edge in the graph. Then, the components of a feature vector can not be seen independently and the normalization is required to keep these relations. Thus, the normalization was done for all components simultaneously. Several normalizations were tested: The rst is linearly resizing the min and max values among all components between 0 and 1, i.e.:
[p2mPiTnRN fwpg; p2mPaTxRN fwpg] ! [0; 1] . The second normalization aims to remove outliers. It considers the feature vector components as elements of a Gaussian distribution, and it centers the data around 0 with a standard deviation of 1, i.e.: [ p2PTRN (wp)
p2PTRN (wp); p2PTRN (wp) + p2PTRN (wp)] ! [ 1; 1] . These normalizations were also applied to the set of test patients PTST using the limits computed on the training set.
Feature Concatenation Fixing a graph structure (Graph Full, Graph 66, or Graph 84 ) and a measure between features (corr, cos, euc, or sumNorm), several sets Wd of feature vectors wd;p were de ned when varying the features used to encode the 3D texture in the regions. The possible features are a(fH ), a(fH ), a(fR), and a(fR). After normalizing each set of vectors Wd, concatenations of these descriptors were tested in order to better describe each patient. These were based on the underlying features. The combinations tested were: { FHOG using the mean and the std ( (fH ) and (fH )), { Riesz using the mean and the std ( (fR) and (fR)), { and FHOG and Riesz using the mean, the std, and both ( (fH ) and (fR), (fH ) and (fR), and (fH ) and (fR) and (fH ) and (fR)), Feature Space Reduction When using the graph Graph Full and feature concatenations, the feature space dimension was much larger than the number of patients. To avoid the known problems when using such large feature spaces, we tested two feature space reduction techniques. Both were applied in the training phase. In the rst case, we considered the ground truth labels to be an step function, with values f0; 1g for the MDR subtask, and f1; : : : ; 5g for the TB task. Then, we computed the correlation between each feature dimension and these step functions, and selected the feature dimensions that correlated best with them. The threshold was set up as the mean absolute correlation of the feature dimensions with the labels. The second technique is based on the standard deviation of each feature. Only the components with a standard deviation higher than the mean of the standard deviations were selected. Both techniques reduced the size of the feature space by 2 approximately. 3.5
Multi-class support vector machine (SVM) classi ers with RBF kernel were used for each run of both subtasks, particularly, 2-class for the MDR task and 5-class for the TBT task. Grid search over the RBF parameters cost C and gamma was applied. Since the data were normalized, both C and moved between [2 10; 2 9; : : : ; 210]. The best C and combination for a run was set as the one with highest cross-validation accuracy in the training set of each subtask. 3.6 The procedure explained in Section 3.4 resulted in 648 runs per subtask. Table 3 summarizes all possible options for each step using the same name coding as in the results tables. Submitted Runs A total of 10 runs could be submitted in the ImageCLEF 2017 TB task. 5 runs were submitted for each task. The 5 runs selected for each task were either one of the 5 best runs with respect to the cross-validation accuracy on the training set (AccTRN ), or a late fusion of a few of them. The late fusion was executed using the probabilities that the SVM classi er returned and the mean probability of belonging to each class. The same procedure was applied in both tasks. Tables 4 and 5 show the identi er and run setup of the 5 best runs for each task respectively.
Run Id. Graph Features F. measure E. weight F. norm. F. reduct. AccTRN
MDR Top1 Graph 84 FHOG and Riesz mean and std corr Gauss[
Run Id. Graph Features F. measure E. weight F. norm. F. reduct. AccTRN
TBT Top1 Graph 66 FHOG and Riesz mean and std sumNorm Gauss[
This section shows the results obtained on the training set by the submitted runs (AccTRN ), and the nal performance in the competition (AccTST ). The nal ranking was based on the Area Under the ROC Curve (AUC) for the MDR task, and on the unweighted Cohen's Kappa coe cient (Kappa) for the TBT task. Table 6 shows the results for the MDR subtask ordered by the ranking provided by the task organizers. The run identi ers MDR TopBest3 and MDR TopBest5 were obtained by doing late fusion with the 3 and 5 best runs respectively (see Section 3.6). The results for the TBT task are shown in Table 7. Again, the run identi ers TBT TopBest3 and TBT TopBest5 correspond to the late fusion of the 3 and 5 best runs respectively. The best run of the competition is shown in the same table. This work presents a new graph-model of the lung based on regional 3D texture features for describing lungs a ected by tuberculosis. The participation in the ImageCLEF 2017 tuberculosis 2017 allows for an objective comparison between methods since the ground truth for the test set was never released. For the MDR task, our method participated with 5 runs and obtained the 1st, 2nd and 3rd place in the challenge. Also in the case of the TBT subtask 5 runs were submitted but the best rank obtained was 10. The results underline the di culty of both tasks and the suitability of our approach for describing TB patients. However, the results also suggest some over tting by our method when comparing the accuracies obtained for the training and test sets.
This work was partly supported by the Swiss National Science Foundation in the project PH4D (320030{146804). 10. Liu, K., Skibbe, H., Schmidt, T., Blein, T., Palme, K., Brox, T., Ronneberger, O.: Rotation-invariant hog descriptors using fourier analysis in polar and spherical coordinates. International Journal of Computer Vision 106(3) (2014) 342{364 11. Dicente Cid, Y., Muller, H., Platon, A., Poletti, P.A., Depeursinge, A.: 3{D solid texture classi cation using locally{oriented wavelet transforms. IEEE Transactions on Image Processing 26(4) (April 2017) 1899{1910