In this paper, we present the learning strategies and feature extraction techniques that were applied by the IBM Research Australia team to the Medical Clustering challenge of ImageCLEF 2015. The challenge is to automatically annotate and categorize X-ray images into head-neck, body, upper-limb, lower-limb and foreign object categories. Our proposed methodology and details of experiments for each submitted run has been discussed in this paper, followed by nal results provided by the competition organizers. The key components used in our submissions are based on sparse coding of SIFT, local binary patterns and multi-scale local binary patterns with spatial pyramid, advanced sher vector, various SVM kernels, and an e ective fusion methodology, to ensure high classi cation accuracy. Comprehensive experiments demonstrate the e ectiveness of the proposed system. Six out of the ten submissions of IBM Research were among the top 10 best results, where two of our submissions outperformed all other submissions, therefore the team has achieved the rst place in the competition.
ImageCLEF medical clustering task [0] is a new category in ImageCLEF 2015 [0]. The objective of this task is to categorize digital X-ray images into four clusters: head-neck, upper-limb, body, and lower-limb [0]. X-ray is the most common medical image modality as it accounts for one third of the the radiographs taken in a typical radiology department [0]. Automatic categorization of medical images has a number of applications including e cient retrieval, archiving, and patient similarity matching. For example, for search and retrieval task, the image needs to be pre-classi ed. However, X-ray image classi cation is a challenging task due to variation in the patients location, exposure, subject motion and the presence of artifacts and foreign objects. In this work, we present a X-ray annotation and categorization system which accurately performs in presence of such artifacts.
Existing methods on X-ray image classi cation are based on local patch features such as local binary pattern (LBP) histogram, edge histogram and SIFT [0]. Recently, the choice of the local feature has gone beyond the traditional local patch descriptor, and higher dimensional representation such as pooled coding vectors and multi-resolution feature modeling have shown to improve the performance. In this paper, we investigated several feature extraction techniques based on higher level feature coding of local feature and multi-resolution analysis for X-ray image clustering challenge in ImageClef 2015. The rest of the paper is organized as follows: Section describes the methodologies applied for the medical clustering task. Section discusses the experimental setup, which has been applied for training and our internal evaluation, and the comparison of our methods before submission. Section reviews the submission runs and presents the results. Finally, Section concludes the paper. 2
Feature Extraction and Learning Methodologies 2.1
LBP describes gray-scale local texture of the image by detecting local patterns between adjacent pixels. For example, original LBP operator labels the pixels of an image by thresholding the 3 3- neighborhood of each pixel with the center value and considering the result as binary string resulting in 256 di erent patterns. In multi-scale LBP (MSLBP) [0], comparison operator between single pixels in LBP is simply replaced with comparison between average gray-values of sub-regions where each sub-region is a square block containing neighboring pixels, and the size of the square block is governed by the scale of LBP. Once the MSLBP values are computed for each pixel, a feature vector for a given image region can be computed as 256 dimensional histogram of the LBP values inside the region. However, such global histogram does not encode spatial information that may be crucial for image recognition task.
In this paper, we compute the MSLBP histogram at multiple scales of spatial resolution by partitioning the image into increasingly smaller overlapping subregions and computing the MSLBP histogram inside each region. The resulting spatial pyramid has shown improvements in the performance of image classi cation tasks. We computed LBP histogram at two levels of spatial pyramid. Let w and h denote the width and the height of the image. In the rst level, the MSLBP histogram is computed in a block where the block covers the entire image. In the second level, MSLBP histogram is computed across the 9 overlapping blocks with size of w=2 h=2 which are obtained by moving a block along x axis with increment of w=4, and along y-axis with increment of h=4. Therefore, the total number of blocks is 10. The MSLBP feature computed in all the spatial pyramid blocks are then concatenated to form a single feature vector which we name as MSLBP-SP. 2.2
Sparse coding is a popular approach for adaptively learning feature
representations. Given a set of input signals fxigiN=1, where x 2 Rm, the goal is to nd
the sparse approximation over a dictionary D in Rm k, with k columns referred
to as basis vectors, so that a linear combination of basis vectors from D
reconstructs the signal x. Rather than using pre-de ned dictionaries, sparse coding
algorithms aim to learn a dictionary of basis functions. The objective function
of sparse coding is stated as:
min
D; N i=1
(
D k22 + k k1
For any image represented by a set of M features, we can compute a single feature vector using a pooling function. For example, the pooling function de ned as average function results in a histogram feature. In this paper, we de ne the pooling function as the max-pooling function over the absolute sparse codes: zj = max fj 1;j j; ; j M;j jg where zj is the jthelement of the nal pooled vector z which is compact representation of the given image region. The max-pooling process is well established by biophysical evidence is visual cortex [0] and is empirically justi ed by many image recognition algorithms.
Given an image, we rst divide the image into 10 spatial pyramid blocks in a similar manner described in Section and compute the local features in each block. The sparse representation of the local features is then computed in each block using the method described above. In this paper, we investigate two types of local feature for sparse coding: (a) dense SIFT (b) dense MSLBP. Dense SIFT is a faster version of SIFT where the SIFT descriptors with xed scale and orientation are computed in densely sampled locations, inside a given image block. In our implementation SIFT descriptor is computed on a 100 100 patches densely sampled in a given block on a grid with step size of 30 30. Similarly, we compute the MSLBP described in Section in 100 100 patch densely sampled in a given block on a grid with step size of 30 30.
The sparse coded features computed in spatial pyramid taking dense SIFT
as local features is named SC-DenseSIFT-SP and the sparse coded features
(
Fisher Kernel [0,0] feature encoding is one of bag-of-word model [0,0] and recent evaluation [0] shows this encoding method achieved best results in many cases. Fisher Kernel encodes the distribution information of the feature points which can separate the image speci c information from the noisy local features. Fisher Kernel encoded features can be represented using a linear model which is computationally e cient.
Let X = fx1; ; xN g be the set of N local features extracted from an image I and u (x) is a probability density function which models a generative process in the feature space. The image I can be described by the gradient vector of log likelihood with respect to the model parameters :
GX = 1
N r log u (X):
Let F is the Fisher information matrix of u , a natural kernel on these gradients is
K(X; Y ) = GX0 F 1GY ; F
= Ex u [r log u (x)r log u (x)0]:
As F is symmetric and positive de nite, it can be decomposed as,
(
Linear classi ers typically consume less time than non-linear ones in training and testing phases. Learning a kernel classi er using the Fisher kernel is equivalent to learning a linear classier on the Fisher vectors GX .
The probability density function u in Fisher Vecter encoding is presented using a Gaussian Mixture Model (GMM), de ned as
F
= L0 L ; GX = L GX :
K u (x) = X k=1
kuk(x) ik =
kuk(xi) PK
k=1 k:uk(xi)
N GXk = X
i=1 GXk = XN 1 i=1 N p
1 N p k 2 k ik xi ik[
k (xi k ; 2 k k)2 Where k is the square root of the diagonal values of k. When increasing the number of Gaussian kernels, the Fisher vectors gets sparser, and the distribution of the features in a given dimension gets closer to zero. We apply a combination of power normalization and L2 normalization to each Fisher vector descriptor. In z-dimension of the Fisher vector , the power normalization is de ned as, (11) (12) (13) (14) where f ; ; g are the prior probability, mean vector and diagonal covariance matrix of the Gaussian mixture respectively. This GMM is used to describing low level features X = fx1; ; xN g extracted from an image I. The soft assignments of the descriptor xi to the kth Gaussian component ik is de ned as
Fisher vector (FV) for X is denoted as (X) = fGX1 ; GX1 ; and G k is de ned as: ; GXK ; GXK g. G k f (z) = sign(z)jzj ; where 0 1 is a parameter of the normalization and we choose = 0:5 in all the experiments. Subsequently, the Fisher vectors are L2 normalized. 2.4
This section explains four of our submissions which were based on extracting global visual features [0], and using SVM and Random Forest, two of the very common yet e ective classi cation techniques. For visual features we extracted Edge Histogram and Local Binary Patterns (LBP) using pyramid spatial granularity. The spatial pyramid refers to extracting the entire image as rst level then in the second level in 2x2 grids followed by (3x3) grids in the third level. All grid blocks are eventually concatenated.
Edge Histogram: We consider 8 edge direction bins and 8 edge magnitude bins, based on a Sobel lter (64-dimensional).
Local Binary Patterns: We also used LBP histograms of 8-bits local binary patterns, each of which is generated by comparing the gray-scale value of a pixel with those of its 8 neighbors in circular order, and setting the corresponding bit to 0 or 1, accordingly. A pattern is called uniform if it contains at most two bitwise transitions from 0 to 1. The nal histogram for each region in our granularity contains 59 bins; 58 for uniform patterns and 1 for all the non-uniform patterns.
We investigated various classi ers implemented in Weka [0], including: Decision Tree, Support Vector Machine (RBF Kernel, Poly kernel, Normalized Ploy kernel and Puk kernel), Random Forest, Logistic Model Tree (LMT) and Naive Bayesian. The validation results suggested that SMO (with normalized poly kernel) and Random forest were the best choice with respect to classi cation performance. 2.5
In an attempt to build a strong classi er by leveraging various learning methods explained previously, we have applied two fusion methods: early fusion and late fusion .
Early feature fusion: In early fusion, we concatenated three types of features to form a single feature vector before classi cation. Speci cally, we concatenated MSLBP-SP (described in Section ), SC-DenseSIFT-SP (described in Section ) and SC-DenseMSLBP-SP (described in Section ).
Late fusion: In late fusion, we combine the classi cation scores of the classication models trained on the feature described in Section - . Let a model k provides a con dence score sik;j for each image i and for each class j. We apply optimization to get the nal con dent score as the weighted sum: Si;j = Pk wk sik;j , using 10-fold cross validation. At each fold, we select the model with the highest accuracy and tune the weight to get the best combined accuracy. The nal weight parameters have been used to calculate the con dence score on the test set. 3
In this section we explain the detail of experiments and our performance evaluation methodology.
Dataset: The training set provided for the medical clustering task contains 500 images where each image belongs to one of ve categories: head-neck, upperlimb, body, lower-limb and true negative (foreign objects), and each category has 100 images. An independent test set containing 250 images without any class information was also provided.
Model Tuning: In order to tune the classi cation models and identify the best parameter values, we used 10 fold cross validation. At each fold we train on 90% of the data and evaluate the models on the remaining 10%. This process is repeated 10 times, each time using di erent train/test partition. We use average F Score among all the validation runs to select the best classi cation model for each feature representation.
Testing: The best classi cation model trained on each feature is used to evaluate on the test set. The list of submitted runs is described in Section and the performance is reported in Table .
In this paper, we described feature extraction and learning methodologies and the fusion strategy applied by the IBM Research Australia team to the medical clustering challenge of ImageCLEF 2015. We utilized advanced feature extraction methods to extract local and global features, as well as advanced feature encoding and classi cation techniques. We also applied early fusion of low-level features, and late fusion of the results of all trained classi er. Overall, six out of the ten submissions of IBM Research team were among the top 10 best results. All runs has been evaluated based on three metrics: exact match, any match and hamming distance metrics. Two of our ten submitted runs demonstrated outstanding results, and outperformed all other submissions across all teams participating in the competition. The early fusion of MSLBP-SP, SC-DenseSIFTSP and SC-DenseMSLBP-SP with homogeneous kernel map and Chi-Square kernel based SVM classi cation achieved highest exact match and any match, whereas Fisher vector resulted in highest hamming distance. 10. J Sivic and A Zisserman. Video Google: a text retrieval approach to object matching in videos. In International Conference on Computer Vision, 2003. 11. L Fei-Fei and P. Perona. A bayesian hierarchical model for learning natural scene categories. In Computer Vision and Pattern Recognition, 2005. 12. K Chat eld, V Lempitsky, and A Vedaldi. The devil is in the details: an evaluation of recent feature encoding methods. In British Machine Vision Conference, 2011. 13. Abedini, Mani and Cao, Liangliang and Codella, Noel and Connell, Jonathan H. and Garnavi, Rahil and Geva, Amir and Merler, Michele and Nguyen, QuocBao and Pankanti, Sharathchandra U. and Smith, John R. and Sun, Xingzhi and Tzadok, Asaf IBM Research at ImageCLEF 2013 Medical Tasks 14. Hall, Mark and Frank, Eibe and Holmes, Geo rey and Pfahringer, Bernhard and Reutemann, Peter and Witten , Ian H. The WEKA Data Mining Software: An Update SIGKDD Explorations (2009), Volume 11, Issue 1