False-positive reduction in mammography using multiscale spatial Weber law descriptor and support vector machines

The first step for WLD is the computation of the differential excitation (DE) of each pixel. To compute DE ε(x _c ) of a pixel x _c , first intensity differences of x _c with its neighbors x _i , i = 0, 1, 2, …, p − 1 (see Fig. 1a for the case p = 8) are calculated as follows [22]:

Then, the ratio of the total intensity difference \(\sum\nolimits_{i = 0}^{P - 1} {\Delta I_{i} }\) to the intensity of x _c is determined as follows:

Note that f _ratio is not robust against noise. Arctangent function is applied on f _ratio to enhance the robustness of WLD against noise, which finally gives the DE for pixel x _c :

The differential excitation ε(x _c ) may be positive or negative. If the current pixel is darker than its background, then its gray scale value I _c is less than those (I _i , i = 0, 1, 2, …, P−1) of its neighbors and each \(\Delta I_{i}\) is positive. As such, the positive value of DE means that the current pixel is darker than its background and the negative value of DE indicates that the current pixel is lighter than its background.

Next main component of WLD is gradient orientation. For a pixel x _c , the gradient orientation is calculated as follows [22]:where I ₇₃ = I ₇ – I ₃ is the intensity difference of two pixels on the left and right of the current pixel x _c , and \(I_{51} = I_{5} - I_{1}\) is the intensity difference of two pixels directly below and above the current pixel, see Fig. 1a. Note that \(\theta \in \left[ { - \frac{\pi }{2}, \frac{\pi }{2}} \right]\).

The gradient orientations are quantized into T dominant orientations as:where \(\theta^{\prime} \in [0, 2\pi ]\) and is obtained using the mapping f: θ → θ′ defined in terms of gradient orientation computed by the Eq. (4) as follows:where

In case T = 8, the dominant orientations are \(\phi_{t} = \frac{t\pi }{4} , t = 0,1, \ldots ,T - 1\); all orientations located in the interval \(\left[ { \phi_{t} - \left( {\frac{\pi }{8}} \right), \phi_{t} + \left( {\frac{\pi }{8}} \right)} \right]\) are quantized as ϕ _t .

The differential excitation and dominant orientation calculated for each pixel form a WLD feature. Using these features, WLD histogram is calculated, see Fig. 2a. First, sub-histograms H _t : t = 0, 1, 2, …, T−1 of differential excitations corresponding to each dominant orientation ϕ _t : t = 0, 1, 2, …, T−1 are calculated; all pixels having dominant direction, ϕ _t , contribute to sub-histogram H _t . Then, each sub-histogram H _t : t = 0, 1, 2, …, T−1 is further divided into M sub-histograms H _m,t : m = 0, 1, 2, …, M−1, each with S bins. These sub-histograms form a histogram matrix H _m,t : m = 0, 1, 2, …, M−1, t = 0, 1, 2, …, T−1, where each column corresponds to a dominant direction ϕ _t . Each row of this matrix is concatenated as a sub-histogram H _m  = {H _m,t : t = 0, 1, 2, …, T−1}. Subsequently, sub-histograms H _m : m = 0, 1, 2, …, M−1 are concatenated into a histogram H = {H _m : m = 0, 1, 2, …, M−1}. This histogram represents an image and is referred to as WLD. This descriptor involves three free parameters:

We represent basic WLD operator by WLD (T, M, S).

The WLD reviewed in the previous sections uses fixed size 3 × 3 neighborhood, see Fig. 1a and is unable in characterizing local salient patterns in different granularities. For representing local salient patterns at different scales, it is extended to multiscale WLD, which is computed using a symmetric square neighborhood (P, R) of side (2R + 1) centered at the current pixel and consisting of P pixels along the sides of the square. The neighborhoods (P, R)—R = 1, 2, 3 and P = 8, 16, 24—determine the scale of the descriptor [22]. For multiscale analysis, histograms obtained using WLD operators with varying (P, R) neighborhoods are concatenated. We represent multiscale WLD operator by MWLD _P,R (T, M, S).

WLD feature is a local feature but WLD histogram is a holistic descriptor that represents an image as a histogram of differential excitations. In this histogram, differential excitations are put into bins according to their values and gradient orientations, irrespective of their spatial location. In this way, locally salient patterns might be lost when an image, such as a mammogram, has different texture patterns at different locations. Spatial location is also an important factor for better description. For example, two similar structures occurring in two different patterns having different spatial locations will contribute to the same bins in the histogram and will not be discriminated by WLD. To enhance the discriminatory power of WLD, we incorporate spatial information into the descriptor. Each image is divided into a number of blocks B ₁ , B ₂ , …, B _n , WLD histogram H _Bi is computed for each block and then these histograms are concatenated to form a Spatial WLD (SWLD) H = {H _Bi : i = 1, 2, …, n}. SWLD not only encode gradient orientation information but also the spatial locality of salient micropatterns.

This descriptor has better discriminatory power because it captures the spatial locality of micropatterns in a better way, which is important for recognition purpose. This extension introduces another parameter: the number of blocks. The suitable choice of number of blocks can lead to better recognition results. We specify SWLD operator by SWLD (T, M, S, n), where n is the number of blocks.

Spatial WLD characterizes both directional and spatial information at fixed granularity. For better representation of an image, it is important to capture local micropatterns at varying scales (P, R). To achieve this end, we introduce MSWLD; in this case for each block of an image, a multiscale WLD histogram at a particular scale (P, R) is computed and then these histograms are concatenated. The final histogram is the MSWLD at scale (P, R). We represent multiscale spatial WLD operator by MSWLD _P,R (T, M, S, n).

Note that the multiscale WLD proposed in [22] is realized with MWLD _P,R (T, M, S) operator, whereas the proposed MSWLD is computed using MSWLD _P,R (T, M, S, n) operator.

The dimension of the feature space generated by MSWLD becomes excessively high. All features are not significant. The redundant features not only increase the dimension of the feature space—curse of dimensionality—but also create confusion for the classifier and result in the decrease in classification accuracy. There is the need to select the most significant features. Different methods can be used to identify irrelevant features and select only the most significant ones. We employ the method proposed by Sun et al. [23]. This method is simple, powerful, and robust; its detail is given below.

Let D = {(x _i , y _i ) : i = 1, 2, …, n} be a training dataset, where x _i ϵ R ^m and y _i ϵ {±1} are the feature descriptor and class label of ith training sample. Let w be an m-dimensional nonnegative weight vector whose components represent the relevance of the corresponding m features of x _i . The problem of feature subset selection is to compute w so that a margin-based error function in the weighted feature space parameterized by w is minimized, which is an arbitrary nonlinear problem. This problem is solved iteratively in two stages. First, by local learning, this problem is decomposed into locally linear problems of learning margins (Steps 3 and 4 in the following pseudocode). Then, w is learned within large margin framework based on logistic regression formulation (Step 5 in the following pseudocode).

The pseudocode of the algorithm is given below [23].

In this algorithm,where \(M_{i} = \{ r:1 \le r \le n, y_{r} \ne y_{i} \}\), \(H_{i} = \{ r:1 \le r \le n, y_{r} = y_{i} , r \ne i\}\), \(P\left( {\varvec{x}_{r} = NM\left( {\varvec{x}_{i} } \right) |\varvec{w}} \right) = \frac{{{ \exp }\left( {\left\| {\varvec{x}_{i} - \varvec{x}_{r} } \right\|_{w} /\sigma } \right)}}{{\mathop \sum \nolimits_{{s \in M_{i} }} { \exp }\left( {\left\| {\varvec{x}_{i} - \varvec{x}_{s} } \right\|_{w} /\sigma } \right)}}, \forall r \in M_{i}\), \(P\left( {\varvec{x}_{r} = NH\left( {\varvec{x}_{i} } \right) |\varvec{w}} \right) = \frac{{{ \exp }\left( {\left\| {\varvec{x}_{i} - \varvec{x}_{r} } \right\|_{w} /\sigma } \right)}}{{\mathop \sum \nolimits_{{s \in H_{i} }} { \exp }\left( {\left\| {\varvec{x}_{i} - \varvec{x}_{s} } \right\|_{w} /\sigma } \right)}}, \forall r \in H_{i}\), NM (x _i ) denotes the nearest neighbor of x _i belonging to the opposite class, NM(x _i ) represents the nearest neighbor of x _i belonging to its class, and the kernel width σ is a free parameter that determines the resolution at which the data are locally analyzed. The regularization parameter λ controls the sparseness of the solution and η is the learning rate. For further detail, a reader is referred to [23].

This method has two free parameters: kernel width σ and regularization parameter λ. Though the authors claim in [23] that the performance of the method does not depend on a particular choice of the values of these parameters, our experience is different, see Fig. 3; the proper choice of these parameters is imperative for the best results. To find the optimal values of σ and λ, which help to select the minimum number of the most significant features giving the best classification result, we applied grid search, as described below.

Though Sun’s method is a filter method but we employed it as a wrapper method for feature subset selection.

For classification, support vector machines (SVM) [24] are used; it is one of the most advanced classifier and outperforms other well-known classification methods in many applications involving two-class problem, especially in texture classification problem. The interesting aspect of SVM is its better generalization ability that is achieved by finding optimal hyperplane with maximum margin, see Fig. 4. The optimal hyperplane is learned from training set. More specifically, given the training samples {(x _i , y _i ): i = 1, 2, …, n}, where x _i and y _i ϵ {−1, +1} are the feature descriptor and class label of ith training sample, the optimal hyperplane is defined as follows:where w and b are obtained by solving the following optimization problem:

The solution of this problem ensures that the margin \(\frac{2}{{\left\| \varvec{w} \right\|}}\) of the hyperplane is maximum. The training samples that are on the canonical hyperplanes (w.x + b) = ±1 are known as support vectors. Note that y _i  = 1 for a normal ROI and y _i  = −1 for a mass ROI.

Support vector machines are basically a linear classifier that classifies linearly separable data, but in general, the feature vectors might not be linearly separable. To overcome this issue, kernel trick is used. Using a kernel function that satisfies Mercer’s condition, the original input space is mapped into a high-dimensional feature space where it becomes linearly separable. Using kernel trick, the general form of an SVM iswhere \(\alpha_{i}^{'} s\) are Lagrange coefficients due to Lagrange formulation of the optimization problem, Ω is the set of indices of nonzero \(\alpha_{i}^{'} s\), which corresponds to the support vectors, x is a testing sample, and K (x, x _i ) is a kernel function. Classification decision is taken based on whether f(x) as a value above or below a threshold. Different kernel functions have been employed for different classification tasks. As radial basis function (RBF) gives the best results in most of the applications, we employ RBF for false-positive reduction problem. SVM with RBF kernel involves two parameters: C, the penalty parameter of the error term and γ, the kernel parameter. For optimal classification results, these parameters must be properly tuned. We select the optimal values of these parameters using first coarse and then fine grid search. For implementation of SVM, we used LIBSVM [25].

The proposed method is evaluated using DDSM [26]; this database consists of more than 2000 cases and is commonly used as a benchmark for testing new proposals dealing with processing and analysis of mammograms for breast cancer detection. The mammograms of the DDSM database were digitized using different scanners: a DBA M2100 ImageClear (42 × 42 μm pixel resolution), a Howtek 960 (43.5 × 43.5 μm pixel resolution), a Lumisys 200 Laser (50 × 50 μm pixel resolution), and a Howtek MultiRad850 (43.5 × 43.5 μm pixel resolution). All the images are 16 bits per pixel. Finally, we rescaled the images to have the same resolution: 50 μm. Each case in this database is annotated by expert radiologists; the complete information is provided as an overlay file. The locations of masses in mammograms specified by experts are encoded as code chains; in Fig. 6, the contours drawn using code chains enclose the true masses. We randomly selected 250 mammograms of the patients, which contain proven true masses, and extracted 1024 ROIs (normal and mass) from these mammograms, see Fig. 6. We extracted 256 ROIs, which contain true masses using code chains; the sizes of these ROIs vary depending on the sizes of the mass regions from 267 × 274 to 1197 × 1301 pixels. In addition, suspicious normal ROIs, which look like masses and result in false positives, were extracted. Some sample ROIs are shown in Fig. 7. These ROIs are uvnsed for training and testing. In an automatic system, it is assumed that these ROIs are extracted by some detection and segmentation algorithm. The role of the proposed algorithm is to identify whether an ROI is a true mass or a normal tissue.

For the evaluation of classification performance, we used fivefold cross-validation. In particular, the dataset is randomly partitioned into five nonoverlapping and mutually exclusive subsets. For the experiment of fold i, subset i is selected as testing set and the remaining four subsets are used to train the classifier, i.e., 80 % of the dataset is used for training the system and the remaining 20 % samples are used to test the system. The experiments are repeated for each fold and the mean performance is reported. Using fivefold cross-validation, the performance of the method can be confirmed against any kind of bias involved in the selection of the samples for training and testing phases. It also helps in determining the robustness of the method when tested over different ratios of normal and abnormal ROIs used as training and testing sets (due to random selection, ratios will be different). To compute the best parameters (σ, λ) of the Sun’s algorithm, we used fivefold cross-validation and the wrapper approach described in Sect. 2.7.

Commonly used evaluation measures of the predictive ability of a classification method are sensitivity (a measure of true-positive rate), specificity (a measure of true-negative rate), accuracy and area under ROC curve (AUC or Az). The sensitivity is defined bywhere TN is the number of ROIs correctly classified as true masses and FN is the number of ROIs, which are wrongly classified as masses. The specificity is defined bywhere TN is the number of ROIs correctly classified as normal and FP is the number of mass ROIs, which are wrongly classified as normal ROIs. The accuracy is defined byit expresses the overall rate of correctly classified ROIs. Another performance measure to evaluate the ability of a classification system to differentiate normal ROIs from mass ROIs is the area (Az) under the ROC curve. The ROC curve describes the ability of the classifiers to correctly differentiate the set of ROIs into two classes based on the true-positive fraction (sensitivity) and false-positive fraction (1 − specificity).

Accuracy is a function of sensitivity and specificity, and it is common trend to use this measure for overall performance of a mass classification method, but a study by Huang and Ling [27] showed that Az is a better measure than accuracy. In view of this, our analysis of performance will mainly be based on Az.

The MSWLD operator—MSWLD _P,R (T, M, S, n)—involves 6 parameters: T, M, S, the number of blocks n, and the scale parameters (P, R). The recognition rate depends on the proper tuning of these parameters. In this subsection, we discuss the impact of these parameters and describe the optimal combination that yield the best recognition accuracy in terms of Az.

Finally, we give a quantitative comparison with state-of-the-art best method proposed by Lladó et al. [21] in addition to basic WLD. There are two reasons for comparison with this method. First, this method outperforms the most representative state-of-the-art methods (see the comparison given in [21]). Second, LBP histogram used in this method is a texture descriptor like WLD. Table 3 shows the comparison of three methods for false-positive reduction based on MSWLD, LBP, and WLD. Each method was implemented using the same hardware/software environment and was evaluated using the same database. Also note that LBP method was implemented precisely using LBP MATLAB code provided by Ojala et al. [28] and the specifications given in [21], i.e., LBP feature descriptor, were computed by applying \({\text{LBP}}_{8,1}^{u2}\) operator on each of 5 × 5 blocks and \({\text{LBP}}_{{8,{\text{Rsize}}}}^{u2}\) operator on each of central 3 × 3 blocks; according to Lladó et al. [21], this configuration gives the best performance. We used MSWLD_24,3 (4, 4, 5, 5 × 5) operator for MSWLD feature descriptor and WLD (12, 4, 20) operator for basic WLD feature descriptor; WLD (12, 4, 20) gives the best performance among different combinations of (T, M, S). This table indicates that MSWLD-based method outperforms in the reduction in false positives. Note that the difference between the performance of LBP-based method (0.94 ± 0.02) reported in the original work by Lladó et al., and the one (0.92 ± 0.016) shown in Table 1 may be attributed to the selection of ROIs and the evaluation technique; we have used 256 ROIs of true masses and 256 ROIs of suspicious normal tissues; Lladó et al. also used the same number but surely the ROIs are different; it is hardly possible for two different persons to choose the same 256 + 256 cases from a database consisting of more than 2000 cases. The comparison of our method with this method reveals that the proposed method is a better choice for false-positive reduction for a CAD system.

Now, the question is why MSWLD performs better. The answer to this question is that it has better potential for discrimination of texture microstructures occurring at different locations and with different orientations and scales because it considers the locality, scale, and the orientation of the texture microstructures. Though LBP descriptor encodes the locality and scale of the micropatterns, it does not take into account the orientation of micropatterns.