Microcalcifications Detection in Mammograms Based on Ant Colony Optimization and Markov Random Field - Coursework Example

Microcalcifications Detection in Mammograms based on Ant Colony Optimization and Markov Random Field Affiliation: I. Literature review Breast cancer is a common cause of death among women. It is a disease where abnormal cells grow in the breast [18]. The mortality rate can be brought down if symptoms are detected and treated before full development [19]. Numerous characteristics may signify a probable clinical problem, including asymmetries between the breasts, architectural distortions and confluent densities of breast tissues, calcifications and masses [3]. These alerting signs are seen on breast X-rays. Mammogram is a medical image essential for the diagnosis of breast cancer. It is considered the most dependable technique for early detection of this type of cancer. Oncologists confirm that microcalcifications are the first sign of breast cancer that may warrant biopsy. The microcalcifications are commonly defined as a tiny deposit of minerals (calcium) that appear like localized high-intensity regions in the mammogram. Microcalcifications are minute (less than half a millimeter) spots. They occur intramammary inside and around the ducts, inside the lobules, in vascular structures, in interlobular connective tissues or fat. Microcalcification detection in mammograms is particularly challenging since abnormalities can pass unnoticed depending on the breast density [6]. Contemporarily, mammography assessments are carried out on patients to detect premature, clinically unsuspected, breast cancer. Computer-assisted schemes that work on image processing are utilized to enhance the diagnostic efficiency. These schemes improve the performances of the automatic computer-aided detections systems that are capable of serving as a pre-reader to the expert radiologist and offer him the second-opinion in the diagnosis [1]. In the literature, many Computer-Aided Detection (CAD) systems for clustered microcalcifications detection were proposed. Monmarche [2] proposed a computerized methodology for microcalcifications detection on mammograms based on three phases. First, a noise filtering is performed to decrease the normal background structure of the mammogram. Secondly, potential microcalcifications are recognized with the aid of global gray-level thresholding, morphological erosion and a local adaptive gray-level thresholding. Thirdly, the number of falsely identified microcalcifications is reduced by examining statistical and textural features of the abnormalities detected. Lau and Bischof [3] proposed a microcalcification detection algorithm based on merging morphological and mathematical processing of mammograms. A frequency assessment is, first applied to highlight any regions in the mammography image that transforms sharply in intensity. A second assessment based on textural analysis is performed: it highlights regions that are minute and textured. Areas common to both assessments are considered as Regions of Interest (ROIs) containing potential clustered microcalcifications. Cheng et al. detailed a CAD system built on fuzzy logic enhancement, irrelevant structure removal, segmentation and reconstruction [4]. Chan et al [17] examined a convolution neural network based algorithm for microcalcification detection. Chan et al presented a comparison of different algorithms used in computer-aided detection systems [17]. An efficient and optimal CAD for microcalcification detection has not yet materialized. Preprocessing, segmentation, feature extraction and classification are the common-four steps procedure upon which the CAD system is designed. The figure below presents the CAD system steps. Segmentation is seen as the major step in the chain. Therefore, we tailored this work to this step. Figure 1. Main steps involved in a computer-aided detection system.microcalcification In the literature, many researchers focused on the segmentation improvement for the detection of microcalcification clusters since it is important to distinguish the suspicious region (ROI) from its surrounding. Segmentation was carried out using a myriad of techniques. Standard segmentation techniques for image processing were tested for the mammograms. These included; Local Thresholding, K-Means Clustering, OTSU segmentation technique, among others. Other experts developed statistical and features based methods to extract ROIs on a mammogram [3, 7, 13, and 14]. However, they failed to achieve satisfactory results for microcalcification detections. Testing other approaches and techniques is still an open field of research. The entire image was examined for ROIs extractions within a mammogram. A label of appurtenance was assigned to each pixel of the considered image forming one of possible classes. In mammographic images, there are mainly three classes present: Background, Breast tissues and ROIs. Segmentation is a combinatorial optimization problem due to the large mammograms search-space. The result of this segmentation depends on the decisional function chosen. Metaheuristics suffice for combinatorial optimization in which an optimal solution is sought over a discrete search-space. The method is, therefore, plausible for the segmentation step in order to increase the ability of finding high quality solutions in a reasonable time. Popular metaheuristics for combinatorial problems were used for segmentation of images including simulated annealing by Kirkpatrick et al [18], genetic algorithms by Monmarche [2], ant colony system by Dorigo [15], and scatter search and tabu search by Glover [9, 10]. For mammogram segmentation, many cited metaheuristics were applied. In [6], Karnan et al applied the Ant Colony System (ACS) with the genetic algorithm for microcalcification identification in mammographic images. Results were encouraging in terms of the segmentation quality. An improved version of the ant-based algorithm is presented on [16]: The Ant Colony Optimization. With the ACO algorithm, ants solve combinatorial problem by exploring pheromone deposits and heuristic information. The major characteristics of the ACO are inherent parallelism, stochastic nature, adaptability and the use of positive feedback [15]. In this paper, we propose a hybrid metaheuristic approach based on Ant colony Optimization with Markov Random field to aid in the detection of microcalcifications in digital X-ray mammograms. The Markov Random Field (MRF) technique is used to model the spatial relation between the different neighboring pixels, yielding the energy function to be optimized. This paper is organized as follows: in section II, we describe the meta-heuristic based on ant colony optimization and the MRF representation of spatial constraints between pixels. In section III, we propose our ACO-MRF algorithm. We present, in section IV, the obtained results and compare them with what others have already published. On the last section, V, we conclude and offer perspective of our contribution in microcalcifications detection. II. ACO and microcalcification detection The segmentation of the microcalcification clusters is considered one of the critical steps on CAD’s for mammograms. The extremely small size of calcifications makes this problem challenging because it has to be precise and accurate. Due to the specificity of the breast tissue, the spatial relation between pixels has to be modeled. The MRF technique is used to achieve this goal and to give the energy function. This function is then optimized via the ACO algorithm to get the best labeling of the breast. This allows detection of ROI. The steps in Fig 2 below present our proposed methodology. Figure 2. Proposed methodology for the microcalcifications clusters. The first part of this section is dedicated to the description of the ACO algorithm as firstly presented by M. Dorigo, then adapted for image analysis. The second one presents the MRF modeling of images. A. Ant Colony Optimization The ACO is a metaheuristic approach that compares population densities to establish proximate values to difficult optimization problems [10]. The inspiring source of ACO is the pheromone trail laying behavior of real ants, which use the pheromone as a communication medium. The higher the pheromone amount is, the higher the probability of an ant choosing that trail. The pheromone values on lower quality trails, which are not reinforced, will often enough progressively evaporate. This form of forgetting avoids the algorithm from converging rapidly toward a suboptimal cluster. Ants, therefore, explore new areas of permanence in the broad search space [16, 2]. In this paper, ACO is introduced to tackle the microcalcification detection in digital mammograms, where we aim to locate the tiny deposits of calcification within the breast tissue. Since it is crucial to understand the image content, the proposed approach exploits a number of K-ants, moving on the image driven by local variation of the pixels intensity values. The ants establish a pheromone matrix τ representing the presence/absence of microcalcification at each pixel location of the image. ACO aims to iteratively, through N iterations, find the optimal solution of the target problem through a guided search over the solution space. The pheromone matrix is updated within and after every iteration, n. There are two fundamental issues encountered while applying an ACO algorithm (with K-ants on total number of nodes (pixels) of the mammogram) to find the optimal solution: 1) the establishment of the probabilistic transition matrix p (n), 2) the pheromone matrix update τ (n). These two issues are respectively presented in detail as follows: Figure 3. Algorithm 1. Ant Colony Optimization algorithm. First, at the nth construction step of ACO, the kth ant moves from the node i to node j according to a probabilistic action rule determined by the relationship (1): (1) Where, is the pheromone information value of the arc linking the pixel i to pixel j, Ωi is the neighborhood of the ant Ak: given its location on i. The constants α and β represent the influence of the pheromone information and the heuristic information respectively. represents the heuristic information for going from pixel i to j, which is fixed to be the same for each construction step [2]. Secondly, the pheromone matrix needs to be updated twice during the ACO procedure. The first update is performed after the movement of each ant within each construction step. Specifically, after the move of the kth ant within the nth construction step, the pheromone matrix is updated as shown in the relationship (2) below: (2) Where, ρ is the evaporation rate. Furthermore, the determination of the best tour is subject to the user-defined criterion. It could be the best scatter found in the current construction-step, the optimal algorithm state, or a combination of both. The second update is performed after the movement of all K ants within the construction-step. The pheromone matrix is updated as follows (3): (3) Where, is decay coefficient for the pheromone. The procedure of ACO is summarized in the algorithm1, where different steps of the optimizations are explicated. In this paper, we present a new ACO algorithm which subdivides a mammogram into different homogeneous texture regions. Our algorithm assigns each pixel in the mammogram membership to one of a given number of classes depending on the statistical properties of the pixel and its neighbors. The individual pixel classifications form a two-dimensional labeled matrix, which must be estimated from the observed image. This estimation is performed with the Markov Random Field approach that is described in the subsequent section. Both the mammogram and its labeled fields are modeled as discrete-parameter random fields. We estimated the pixel classes by minimizing the expected value of the number of misclassified pixels. The optimum label, which minimizes the MAP estimate, was established using the ACO algorithm. B. Markov Random Field Image segmentation requires that a decision be made about the type of each pixel. The use of the stochastic spatial process in image segmentation is widely used. Two different types of models are used in the decision making process of this approach. The first one describes the underlying image and serves as prior contextual information for making a decision. The second one describes the observation at each pixel and/or the relation between feature vectors and pattern classes [1 2]. MRF leads to a contextual model for the treated image and incorporates context by assuming that the true labeling of a pixel depends on the labels of spatially neighboring pixels. This way, the MRF model provides an excellent tool for blending the information on local spatial interaction into a global framework [6]. The image segmentation can be easily formulated as a MAP estimation problem [6]. Suppose that each pixel of the image, s, belongs to one of C different classes, and let xs in {1, ..,C} indicate the class of pixel, s. Then x = {xs, s ∈ S} is the segmentation of the image S in C classes. If x is unknown, its class, c, can be recovered from the observable data where y = {ys, s ∈ S}, and ys represents the pixel value (s) in the original mammogram. If we assume that x and y are particular realizations of two random fields X and Y, a natural way to carry out the segmentation process is to select x as the realization with the largest conditional probability given the data y, namely: Applying the Bayes theorem in the equation; Where P(X) is the apriori density of the region and P(Y/X) is the conditional density of the observed mammogram given the distribution of the region centered on pixel s. Further, we can write: (8) Where is the mean value of the intensity pixels of the neighborhood of s. We conclude then, (9) The field of the classes’ model has to keep the spatial dependencies in the image through the conditional probability that a pixel belongs to a given class given the classes of its neighbors. As a result, X has Gibbs distribution given by the system of equations (10): While the energy function is given by the relation (12): (12) the minimization of the Maximum APriori (MAP) corresponds to the maximization of the energy function. The minimization of MAP leads to the optimal labeling of the entire image. In mammograms, different tissues correspond to different intensities. Using the intensity levels, it is possible to distinguish between background, fat, tissues, and microcalcifications whose intensities generally increase in the same order. However, the mean intensity of each mammographic region may vary depending on its location and surroundings. The design of the proposed method for the extraction of suspicious areas from digital mammograms lies on two assumptions; 1) suspicious areas are brighter than their immediate surrounding tissues, and 2) pixels within a suspicious area have relatively uniform intensity. Hence, based on the pixels’ intensity of, and their relative locations, the mammographic image is segmented into three classes of regions: class 1 corresponds to background (black areas), class 2 corresponds to tissue and fat, and class 3 corresponds to microcalcifications. Class 3 is the region of interest. The MRF model is plausible for the mammographic image labeling. The process of minimization of the MAP ensures the optimal labeling of the mammogram pixels. This optimization is obtained using the ACO algorithm. The principle phases and processes of this approach is proposed in the subsequent section. III. proposed ACO-MRF algorithm Mammograms given by the mammographic machine present diverse features and noise as shown in Figure 1. A first step of basic preprocessing is, therefore, needed. The proposed microcalcification detection technique is secondly applied. These two steps are respectively explicated in this section. A. Mammogram pre-processing In this work, the mammogram images are initially enhanced by median filter to remove noise from the image. In fact, Median Filtering (MF) is powerful in removing noise from two-dimensional signals without blurring edges [1]. This makes it particularly suitable for enhancing mammogram images. In median filtering, the low-frequency image is generated by replacement of the pixel value with the median value computed over kernel centered on its location. Secondly, a delimitation of the tissue zone is done roughly within a connected component (CC) approach, to minimize the solution space. Results of this step are presented on Fig 4 below: Figure 4. Pre-processing results of a mammogram B. ACO-MRF In this section, the developed algorithm is presented. Steps are summarized in Figure 5. The main objective of the ACO-MRF algorithm is to detect microcalcification in the breast tissue, if it exists. We proceed first to achieve the best labeling to each pixel of the mammogram. The best labeling is given when minimizing the energy function U(x) of the mammogram given by equation (12). Secondly, the microcalcification label is selected. It is the class with the highest average of intensity level of pixels. The labeling process consists of assigning same label to the image pixels presenting homogeneity. The best label is the one, which minimizes the MAP estimate given by equation (9). For each ant, we assign the initial pheromone value T0 and an initial non-visited pixel randomly, constructing the first element of the tabu list relative to each ant and trying to accord each location the suitable label: maximizing the conditional probability given by equation (9). An update of the pheromone quantity is done, at first, locally. This process is repeated for all ants. At the end of tours of all ants, the best ant is chosen. The chosen ant is the one that achieved the best labeling: measured via the energy function value of the mammogram. The global update of pheromone is done in two steps:1) by enforcing the pheromone quantity of the labeling of the best ant, and 2), by evaporating a quantity of the pheromone on the track of other ants. These processes are repeated within each iteration of the ACO-MRF algorithm. Figure 5. ACO-MRF for mammogram segmentation IV. Results and interpretation The mammograms used in this experiment were obtained from Mammographic Image Analysis Society (MIAS) database. The MIAS which is an organization of UK-based research groups interested in the understanding of mammograms, has produced a digital mammography database available on the web [10]. It consists of 320 digitized mammograms at 50-micron pixel edge, resulting to a 1024x1024-pixel resolution. There are 30 mammograms containing microcalcifications. For the evaluation of the proposed method, we used all the abnormal mammograms from the MIAS database that contain microcalcifications. Figure 6. Set of MIAS database mammograms containing microcalcifications. The MIAS database provides groundtruth for each lesion in the form of circles, which indicate the approximate center and radius of each abnormality. Since circumscribed lesions are rarely perfectly circular, and since the MIAS policy was to err on the side of making the groundtruth circles completely inclusive rather than too small, these regions often contain a substantial amount of normal tissue, as well [10]. The ants explore the mammogram x-ray to localize abnormal pixels showing different characteristics than the neighborhood. A deposit of pheromone trail is made whenever a pixel of a microcalcification is detected. The evaluation of the segmentation is done by calculating the Borsotti criterion of each segmented image. This measure is based on the number N, the surface, A, and the variance, e, of the regions. It is designed to penalize the numerous small non-homogeneous regions. To determine the optimal number of ants within a colony, several tests were done. The effect of the number, n, of ants on the segmentation process is presented on Fig 7. It shows that choosing a colony of 10 ants leads to optimal criterion value within the least timing. Table 1. Plot showing influence of number of ants on the segmentation quality We tested the algorithm with 10 ants for 5 iterations. A 4-connectivity neighborhood was chosen for the determination of the optimal labeling within a kernel. Fig 8 shows the values of this criterion of some segmented mammograms. Results are promising, showing the efficiency and the adaptability for the Ant colony Optimization algorithm for the ROIs detection. Table 2. Borsotti criterion measures on selected MIAS database set In order to evaluate and situate our developed ACO-MRF algorithm in the field of microcalcification clusters detection, the average of Borsotti values within the set of mammograms was calculated. It was then compared with other averages of the same criterion applied to the same set of images. The best technique was the one giving the minimum variation in the Borsotti values. The Table 1 below shows average values of the segmentation criterion of published works as well as the average value of our method. The superior quality of ROIs detection and the accuracy of the ACO-MRF were evident. Table 3. Comparison between published average values and the average for our algorithm The figure 7 below shows the results of the detection of the microcalcification cluster of an image from MIAS database. Figure 7. Mdb218 segmentation results with the ACO-MRF algorithm; a) Mdb218 mammogram. (b) Preprocessed mammogram with MF and CC, c) Result of the segmentation, d) ROI (microcalcification cluster). V. conclusion and perspectives The importance of the segmentation phase during the analysis of x-ray breasts images led us to investigate new intelligent techniques to improve the quality of microcalcification detection. In this paper, we presented the results of the application of our novel technique based on an ant colony optimization for microcalcification detection in mammogram. When comparing the results of the conventional methods, ACO-MRF showed better ability to find best labeling and segmentation of microcalcifications. The Borsotti criterion demonstrates that the proposed algorithm has a better performance than in other published works. The proposed method proved credible for application and adaptation for the segmentation purposes and, especially, on medical images analysis. More investigations and adaptations are required to improve the running time of the proposed algorithm to obtain faster and more accurate segmentation of the mammographic images. Bibliography [1] : Cocquerez, J. P. and Philipp, S., Analyse d’images et segmentation. Masson, 1995. [2]: Monmarché, N.,  Algorithmes des fourmis artificielles: applications à la classification et à loptimisation. PhD thesis. Décembre 2000, Tours University. [3]: Lau, T.K and Bischof,W., Automated detection of breast tumors using the asymmetry approach,. Comput. Biomed. Res. 24, 273-295(1991). [4]: Sallam, M.Y., and Bowyer, K.W.: Registration and difference analysis of corresponding mammogram images. Medical Image Analysis, vol. 3, no. 2, pp: 103-118,1999. [5]: Ferrari, R.J., Rangayyan, R.M., Desautels, J.E.L., Borges, R.A., and Frere, A.F, Analysis of Asymmetry in Mammograms via Directional Filtering With Gabor Wavelets. IEEE Transactions on Medical Imaging, vol. 20, no. 9, pp: 953–964, 2001. [6]: Thangavel K.,. Karnan M,.Siva Kumar R and Kajamohideen A., Segmentation and Classification of Microcalcification in Mammograms Using the Ant Colony System. International Journal on Artificial Intelligence and Machine Learning, vol. 5, no. 3, pp: 29-40,2005. [7]: Zyout I., Abdel-Qader I., Jacobs C., Bayesian classifier with simplified learning phase for detecting microcalcifications in digital mammograms. Hindawi Publishing Corporation International Journal of Biomedical Imaging Volume 2009, Article ID 767805, 13 pages doi:10.1155/2009/767805 [8]:. Foliguet S. P, Guigues L.. Evaluation de la segmentation d’images : état de l’art, nouveaux indices et comparaison. ETIS, UMR CNRS 8051 .6 avenue du Ponceau, 95014 Cergy Cedex, CREATIS, UMR CNRS 5515, Inserm U 630 INSA, 7 rue Jean Capelle, 69621.Villeurbanne Cedex. [9] : Chau D. M. Évaluation de la segmentation dimages Superviseur Alain BOUCHER Institut de la francophonie pour linformatique (IFI) Hanoi, Vietnam janvier 2007. [10] : http://peipa.essex.ac.uk/info/mias.html. [12]: Forsyth D., Ponce J. Computer Vision: A Modern Approach. Prentice-Hall. 2003. [13]: Eddaoudi F., Regragui F., Microcalcifications Detection in Mammographic Images Using Texture Coding. Applied Mathematical Sciences, Vol. 5, 2011, no. 8, 381 – 393. [14]: Heucke L., Knaak M.,Orglmeister R., A new image segmentation method based on human brightness perception and foveal adaptation. IEEE Signal Processing Letters, 2000, 7(6),129 :131. [15]: Dorigo, M. and Blum, C., Ant colony optimization theory: A survey. Theoretical Computer Sc.. 2005, Vol. 344, pp. 243-278. [16]: Blum, C., Ant colony optimization: Introduction and recent trends. Physics of Life Reviews. 2005, Vol. 2, pp. 353-373. [17]: Chan H. P. et al, Improvement in radiologists’ detection of clustered microcalcifications on mammograms. the potential of computer-aided diagnosis, Investigative Radiology, vol. 25, no. 10, pp. 1102–1110, 1990. [18]: World Health Organization. (2008). World health statistics 2008. Geneva, World Health Organization. [19]: Morrow, M., & Jordan, V. C. (2003). Managing breast cancer risk. Hamilton, BC Decker Inc. Read More