Image Segmentation Using Nearest Neighbor Classifiers Based On Kernel Formation For Medical Images

DOI : 10.17577/IJERTV1IS3037

Download Full-Text PDF Cite this Publication

Text Only Version

Image Segmentation Using Nearest Neighbor Classifiers Based On Kernel Formation For Medical Images

Image Segmentation is one of the significant elements in the part of image processing. It becomes most essential demanding factor while typically dealing with medical image segmentation. In this paper, proposal of our work comprises of formation of kernel for the medical images by performing the deviation of mapped image data within the scope of each region from the piecewise constant model and based on the regularization term based on the function of indices value of the region. The functional objective minimization is carried out by two steps minimization in image segmentation using graph cut methods, and minimization with respect to region parameters using constant point computation. Nearest neighbor classifiers are introduced to the benchmarked image data segmented portions. Among the different methods in supervised statistical pattern recognition, the nearest neighbor rule results in achieving high performance without requirement of the prior assumptions about the distributions from which the training sets are taken.

  1. The fundamental concept relying in image processing is image segmentation and classifying. The purpose behind the processing is to formulate the image into regions. Variational formulations that result in effective algorithms include the required attributes of its region and boundaries. Works have been carried out both in continuous and discrete formulations, though discrete version of image segmentation does not approximate continuous formulation. Analysis is carried out on digitized variations of the variational formulation of the segmentation problem. Uses of graph cut algorithms have proven to be very efficient. Several works carried out shows that graph cut algorithms are of great interest in image analysis.

    Unsupervised graph cut methods proceeds without the intervention of the humans which uses the Gaussian generalization model as the data can be described in the way as is required by the graph cut algorithm model. Though useful these models are not of

    applicable as different portion of the region requires different types of models. For example SAR images are best suited for the Gamma distribution model. Even if we take into consideration within images also different regions require different models. For example Gaussian distribution is modeled for within the shadow regions in sonar energy whereas in case of reverberation regions Rayleigh distribution is more suitable. The parameters of all the models described above do not depend upon the data, as a result of it the models cannot be used.

    The objective function may be to find out the sum of all the pixels or select the pixel neighborhood data and variables. The parameters considered in Gaussian method are discrete approximation, linear combinations of the image provided. One way to modify the model is to introduce user interaction. Various interactive graph cut models have been used in contrary to the Gaussian model at any step of the segmentation process. Based on the segmented portions of the image we can diagnose the various causes based on the medical images.

  2. The majority of research in medical image segmentation pertains to its use for MR images, particularly in brain imaging. This is due to MRs ability to give a mixture of high resolution (on the order of 1mm cubic voxels), outstanding soft tissue contrast, and a high signal-to-noise ratio [1]. Furthermore, multi-channel MR images with varying contrast individuality can be acquired, providing extra information for distinguishing between dissimilar structures [7]. For common reviews on the segmentation of MR images, see [2]. Straight comparisons of dissimilar methods for segmenting MR images are also obtainable [3]. Because of its ability to get contrast from a number of tissue parameters, lots of different pulse sequences were present for acquiring MR images.

    Much of the literature on segmentation in MRI discusses particularly on the segmentation of head scans in usual subjects [4]. There are three common goals in this application: 1) discover the brain capacity, 2) segment brain tissue into gray substance, white substance, and cerebrospinal fluid, and 3) define precise brain structures such as the cerebral cortex or the hippocampus [8]. An exception to this classification is the use of atlas-guided methods [5], which are able of fully segmenting and labeling all structures

    of the brain concurrently, but also have certain shortcomings. Overviews on the segmentation of neuro anatomy are provided in [6].

    Besides head scans, segmentation has also been used to discover a diversity of other formations [9]. Segmentation in cardiac imaging has been used for delineating the cavities of the left ventricle using region growing and thresholding approaches [10], as well as deformable models [11]. Deformable models in cardiac imaging, yet, are more often proposed for tracking motion in the heart [12]. Markov random field models have been used for segmenting knee images [13] as well as magnetic resonance angiograms (MRAs) [14]. Other methods for segmenting MRAs include deformable models and thresholding. Although MRA does not require catheterization, segmentation in standard angiography is more common because of its generally superior contrast and spatial and temporal resolution.

  3. Nearest neighbor classifier is a simple method of multivariate interpolation in single or multi dimensions. The task of interpolation in nearest neighbor classifier for medical images is to approximate the value for a non-given point in some space when given some objects around that point.

    The nearest neighbor classifier (fig 1) selects the value of the nearest point and it does not take into consideration the values of neighboring point but it derives a piecewise-constant value. The neighbors are taken for a set of objects in which case the correct classification of the algorithm is known. This can be considered as the training set for the algorithm, although there is no necessity for explicit training step. Nearest neighbor classifier compute the decision boundary in an implicit manner for the given medical images as the training set. It is also possible to compute the decision boundary itself explicitly so that the computational complexity is considered as the boundary complexity.

    Piecewise constant, high contrast between regions

    Brain image

    Deviation of mapped image data

    Kernel formation

    Derives piecewise- constant value

    Time period

    Interval 1 Interval 2 Interval 3

    Objective functional minimization

    Nearest neighbor classifier

    Multivariate interpolation

    Achieving high performance

    Regions parameters via fixed point computation

    Image segmentation by graph cuts

    Approximate value for non-given point

    A piecewise constant model means that the time period during which the process takes place is observed and is split into several intervals and for each of the interval a different constant is estimated. Brain images have a number of features, to mention a few are, first, they are simple. Brain images are mainly piecewise constant with a very small number of classes. Second, they can have relatively high contrast between different

    regions for different models. Compared to other medical imaging modalities, the contrast in brain images depends upon the way the image is processed. By altering the region indices kernel formation, we can achieve high-contrast images. These two advantages facilitate segmentation. Minimization with rspect to image segmentation and region parameter for brain images using graph cut can be achieved using standard minimum cut algorithm.

    Let an image be represented as M (m1, m2, m3. mK ), where m denotes individual pixel within multi-dimensional data and K denotes the number of pixels. The method works through an optimization using graph cut procedure to reduce the functional objective which is defined as follows:






    K c

    y 1 xy y x 1

    v ||2

    ,1 c




    c represents the degree of membership of data elements my in the xth


    segment, vx is the centroid of the xth segment, s is the number of segments to be partitioned, || my – vx || is a norm (distance measures are commonly applied) representing the distance which states the similarity between measured multi-feature data and the segment centroid, and c is a real constant greater than 1 which controls the resulting partition.

    In nearest-neighbor classifier, each pixel is categorized in the similar class as the training data with the closest intensity with majority vote of the closest training data. The nearest-neighbor classifier is measured a nonparametric classifier since it makes no fundamental assumption about the statistical structure of the data. It assumes that the pixel intensities are independent samples from a mixture of probability distributions, usually Gaussian. This mixture, called a finite mixture model, is given by the probability density function.

    F (q j , , )


    k Fk ( y j , k )

    k 1

    —————-> (2)

    where qj is the intensity of pixel j, Fk is a component probability density function parameterized by k, and = [1, 2, .. k]. The variables k are mixing coefficients that

    weight the contribution of each density function and = [1, 2, k]. Training data is collected by obtaining representative samples from each component of the mixture model and then estimating each k accordingly.

    The contrast values were measured by the Bhattacharyya distance between the intensity distributions within the two regions of the actual image

    D ln

    i I

    R1(I )R2(I )

    where and denote the intensity distributions within the two regions and is the Bhattacharyya coefficient measuring the amount of overlap between these distributions. Small values of the contrast measure , correspond to images with high overlap between the intensity distributions within the regions. We carried out a comparative study by assessing the effect of the contrast on segmentation accuracy for the three segmentations methods. We evaluated the accuracy of segmentations via the percentage of misclassified pixels (PMP) defined, in the two-region segmentation case, as


    (1 | bm

    bs |

    | bm

    | fm

    fm |

    fs |) *100

    ———————> (4)

    where bm and fm denote the background and foreground of the ground truth (correct segmentation), bs and fs denote the background and foreground of the segmented image. Classification of new data is obtained by assigning each pixel to the class with the highest posterior probability. When the data truly follows a finite Gaussian mixture distribution, the ML classifier can perform well and is capable of providing a soft segmentation composed of the posterior probabilities.

  4. The performance of proposed image segmentation scheme, Nearest Neighbor Classifiers based on Kernel formation is implemented in Mathworks Matlab 7.0. Piecewise constant model is applicable because parametric kernel graph cut method (KM) provides another image modeling by implicitly mapping the image data by a kernel function. The intention of this study is to show how Nearest Neighbor Classifiers based

    on Kernel formation segment images with no prior assumption regarding image model. The medical image (brain image) is taken as training set which is segmented into three regions. Segmented regions are based upon prior medical knowledge. Segmentation at convergence and final labels are displayed in figure 2.

    1. b) c) Figure 2: a) Input Brain image, b) Segmentations at convergence, c) Final labels

      Fig. 2 gives a spot of very narrow human vessels with very small contrast within various regions. The results obtained from experiments in both cases are agreeable. The purpose of this evaluation is to express the ability of the our proposed Nearest Neighbor Classifiers based on Kernel formation scheme to adapt without human intervention to this class of images obtained with special techniques other than the common ones. These results with gray level images demonstrate that the Nearest Neighbor Classifiers is robust and flexible with various types of images.

  5. To illustrate the above advantages, we performed the tests with various sets of real medical images. The experimental results evaluated in terms of number of images used, number of segmented portions and signal to noise ratio (SNR). Proposed work computed one value for the local signal and another for the local noise at each pixel in a background-subtracted image and assigned the ratio of signal/noise for that pixel in the resulting image. This produced a new image where every pixels value was equal to its signal-to noise ratio as computed from the original, background-subtracted intensities of its local neighborhood,

    S / N


    where µ is mean of the background-subtracted intensity in the (smaller) signal window and is the standard deviation, or noise, contained by the background subtracted intensities in the (larger) background window. (The background window includes the pixels in the signal window.)












    Nearest neighbor classifier method Multiregion Graph cut method


    No. of images


    Figure 3: No. of images vs SNR

    Figure 3 depicts Comparison result of Proposed nearest neighbor classifier and existing multiregion graph cut method based on SNR. We can define the input image signal-to-noise ratio in terms of the mean greylevel value of the object pixels and background pixels and the additive noise standard deviation. As number of images increased, SNR also gets increased. SNR value of Proposed nearest neighbor classifier method is in between 17 % to 26 % which is relatively low when compared with existing multiregion graph cut method.










    20 30 40

    No. of segments




    Nearest neighbor classifier method Multiregion Graph cut method


    No. of segments

    Figure 3 illustrates the SNR based on the number of segments. In the background-subtracted image, the signal was determined by considering a certain number of pixels surrounding the pixel of interest and averaging their intensities. The mean of intensity of a small neighborhood or window around the pixel of interest became the signal value for that pixel. The standard deviation in a larger neighborhood around the pixel of interest was used to define the noise. SNR value on segments for Proposed nearest neighbor classifier method is in between 12 % to 18 % which is low as compared ith multiregion graph cut method.















    8 10




    No. of images

    Nearest neighbor classifier method Multiregion graph cut method

    Figure 5 depicts the number of segments to be generated based on the number of imges used in the experiments. Number of segments increases smoothly as number of images is increased. The performance graph shows that the Proposed nearest neighbor classifier method produce the more number of segments as compared with multiregion graph cut method.

    From the above results, it can be clearly seen that the developed method yields better results than the existing methods on Medical image segmentation.

In this paper we have investigated Image segmentation using Nearest Neighbor Classifiers based on Kernel formation for the medical images by achieving mapped image data deviation within the range of each region from piecewise constant model and based on the regularization term based on the function of indices value of the region. The method minimizing a function of original image data term which references the data transformed through a kernel function. Nearest neighbor classifiers have been introduced to image data segmented portions. It takes into consideration both the positive and negative cases. Verifiers are generated to identify the matching proportion of the test data to training data kernels. The proposal of our work gains the advantages of both simple modeling method and optimization using graph cut. Using the common kernel function effectiveness of the method can be evaluated using quantitative comparative performances over a large number of medical images especially brain images. The performance evaluation is carried out by using quality metrics which show that Compared to the existing graph cut methods, our proposed method brings different advantages with regard to accuracy in segmentation process and flexibility while diagnosing the medical images.



  1. Mohamed Ben Salah, Amar Mitiche, and Ismail Ben Ayed, Multiregion Image Segmentation by Parametric Kernel Graph Cuts, IEEE Transactions On Image Processing, vol. 20, no. 2, Feb 2011.

  2. D. Cremers, M. Rousson, and R. Deriche, A review of statistical approaches to level set segmentation: Integrating color, texture, motion and shape, Int. J. Comput. Vis., vol. 72, no. 2, pp. 195215, 2007.

  3. I. B. Ayed, A. Mitiche, and Z. Belhadj, Polarimetric image segmentation via maximum-likelihood approximation and efficient multiphase level-sets, IEEE Trans. Pattern Anal. Mach. Intell., vol. 28, no. 9, pp. 14931500, Sep. 2006.

  4. T.Logeswari and M.Karnan, An Enhanced Implementation of Brain Tumor Detection Using Segmentation Based on Soft Computing, International Journal of Computer Theory and Engineering, Vol. 2, No. 4, August, 2010.

  5. Y. Boykov and G. Funka-Lea, Graph cuts and efficient N-D image segmentation, Int. J. Comput. Vis., vol. 70, no. 2, pp. 109131, 2006.

  6. S. Vicente, V. Kolmogorov, and C. Rother, Graph cut based image segmentation with connectivity priors, in Proc. IEEE Int. Conf. Comput. Vis. Pattern Recognit., Alaska, Jun. 2008, pp. 18.

  7. N. Vu and B. S. Manjunath, Shape prior segmentation of multiple objects with graph cuts, in Proc. IEEE Int. Conf. Comput. Vis. Pattern Recognit., 2008, pp. 18.

  8. N. Y. El-Zehiry and A. Elmaghraby, A graph cut based active contour for multiphase image segmentation, in Proc. IEEE Int. Conf. Image Process., 2008, pp. 31883191.

  9. S.Zulaikha Beevi, M.Mohamed Sathik, A Robust Segmentation Approach for Noisy Medical Images Using Fuzzy Clustering With Spatial Probability, European Journal of Scientific Research, ISSN 1450-216X Vol.41 No.3 (2010), pp.437-451.

  10. A. Achim, E. E. Kuruoglu, and J. Zerubia, SAR image filtering based on the heavy- tailed Rayleigh model, IEEE Trans. Image Process., vol. 15, no. 9, pp. 26862693, Sep. 2006.

  11. I. S. Dhillon, Y. Guan, and B. Kulis, Weighted graph cuts without eigenvectors:A multilevel approach, IEEE Trans. Pattern Anal. Mach. Intell., vol. 29, no. 11, pp. 1944 1957, Nov. 2007.

  12. Rajeev Ratan A, Sanjay Sharma B, S. K. SharmaC, Brain Tumor Detection based on Multi-parameter MRI Image Analysis, ICGST-GVIP Journal, ISSN 1687-398X, Volume (9), Issue (III), June 2009.

  13. P. Kohli, J. Rihan, M. Bray, and P. H. S. Torr, Simultaneous segmentation and pose estimation of humans using dynamic graph cuts, Int. J. Comput. Vis., vol. 79, no. 3, pp. 285298, 2008.

  14. V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, and C. Rother, Probabilistic fusion of stereo with color and contrast for bilayer segmentation, IEEE Trans. Pattern Anal. Mach. Intell., vol. 28, no. 9, pp. 14801492, Sep. 2006.


Leave a Reply