Efficient Image Segmentation using GPU Computing

Efficient Image Segmentation using GPU Computing

Ms. Swetha K. H

M.Tech student Department of computer science,

RVCE,

Bengaluru, Karnataka, India

Dr. Minal Moharir

Associate professor, Department of computer science,

RVCE,

Bengaluru, Karnataka, India

Abstract- In applications such as pattern recognition, the whole image cannot be processed directly as it is inefficient and unpractical. Hence several image segmentation algorithms were proposed to segment an image. Image segmentation is a part of image processing, which classify digital image into multiple segments according to the feature of image for example pixel values. This is useful in pattern recognition and computer vision. Pattern recognition is a process of recognition of patterns and regularities in data and is used in medical diagnosis. Computer vision is a field of understanding images to produce numerical or symbolic information. This field theme is to duplicate the abilities of human vision by understanding and electronically perceiving an image. Level Set Method (LSM) had been used widely for image segmentation. Partitioning the input image into multiple segments efficiently using LSM is the main purpose of this paper.

The paper implements an image segmentation algorithm. First it preprocess input color image (size can be upto 2MB). It deals with converting of input image into gray-scale image and then noise removal using Gaussian filter. This is followed by segmentation, which is implemented using LSM with edge, region and 2D histogram information. LSM enables to easily handle complex shapes and topological changes such as merging and splitting. But LSM is computationally expansive. This computational complexity of LSM based image segmentation approach is significantly reduced by the use of extremely parallelizable method called Lattice Boltzmann Method (LBM), with a body force to solve the Level Set Equation (LSE). Nvidia GPU (GeForce GTX) is used to take full advantage of LBM parallelism nature. CUDA C programming is used to implement algorithm on GPU.

An Image segmentation algorithm is been implemented. Testing was carried out for over 50 images and on different sizes of images (50KB to 1000KB size). The method is very effective when segmenting objects with/without edges also, independent to the position of initial contour and robust against noise. The experimental result shows that the use of GPU improved performance efficiency of level set method based segmentation when run in parallel. Segmentation speed is increased 10-times more for parallel implementation of algorithm as compared to sequential.

Keywords Segmentation, Level set method, GPU.

1. INTRODUCTION

   Image segmentation is a process, in which digital image is partitioned into multiple segments. Segmentation of images have wide applications, it is used in computer vision, pattern recognition [2]. Segmentation is required in medical

   diagnosis like to locate tumors. Segmentation is also used for face detection, iris recognition, wood quality inspection, food pack checks. So image segmentation has wide varieties of application.

   There are several methods for segmentation of images. This project implemented level set based approach for segmentation of image using GPU. The level set technique is generally used for tracking shapes and dynamic interfaces. This technique was initially developed to model fluid boundaries, for example front of flames. Now for image segmentation in pattern recognition and computer vision this level set method (LSM) had been used widely [1][3].

   The LSM main advantage is it can handle topological changes automatically, for instance merging and splitting. It has the ability to extract complex contours. The LSM is an active contour model which uses geometric representation [5].

   The LSM works by evolving the Zero-level of the level set function (LSF) in the image domain until the interested regions boundaries are reached. The level set equation (LSE) governs the active curve evolution [6]. It is a partial differential equation expressed as

   In the above equation (1) is the level set function, V is the speed function. This speed function draws and drives the active contour in the direction of the region borders. The II term in the right hand side represents the curvature. It is used for smoothing the contour. And it is non-linear, computationally expansive. and are user controlling parameters.

   There are two approaches to stop the evolving curve on the boundaries of the desired objects. The first approach practices an edge indicator depending on the gradient of the image like in active contour models [5][7]. The methods based on this approach are effective when detecting objects boundaries defined by edges. But it is ineffective when objects in image are with no edges and sensitive to noise.

   The second approach uses certain region attributes to stop the evolving curve [8]. The methods belonging to this approach are effective when detecting objects without edges, robust to noise. But have some difficulties when the boundaries between the background and object are only defined by high gradient.

   This project implemented a two phase level set method which can allow the realization of a binary segmentation, and can be easily expanded to the multi-phase case. The method uses both region information and edge information in order to effectively detect both objects defined by edges and without edges. The sensitivity to noise introduced by local information that is edge information, is handled by the 2D gray-scale histogram based constraint.

   To solve the LSE, lattice Boltzmann method (LBM) is used [9]. The LBM is simple, highly parallelizable and explicit in nature. It is second order accuracy both in space and time. It can lever the problem of time consuming better because the non-linear term in the LSE is implicitly computed. Initially to simulate equations for incompressible fluid LBM was designed [10][11]. The evolution equation of LBM is

2. DETAILS OF PREPROCESSING AND SEGMENTATION

   1. Preprocessing

      Image may contain noise, so before applying segmentation noise is removed from it. Here Gaussian blur filter is used to remove the noise. The image is converted into gray scale image.

      Gaussian blur or Gaussian smoothing is the outcome of blurring an image by Gaussian function. To decrease image noise and to decrease detail it is used in graphics software. The pictorial outcome of this blurring technique is smooth blur resembling that of viewing the image through a glowing screen. Gaussian smoothing is used as a preprocessing stage in computer vision algorithms in order to enhance image structures at different scales. The two dimension Gaussian function equation is

      (6)

      Where x is the distance from the origin (Horizontal axis), y is the distance from the origin (vertical axis), and is the standard deviation of the Gaussian distribution. The standard deviation of the Gaussian determines the amount of smoothing. The proposed idea is implemented using CUDA C to run on GPU. The output of preprocessing is a gray scale image as shown in figure 1.1

      In the above equation (2) fi is the Particle Distribution function and is the Bhatnager Gross Krook (BGK) collision model [12] with a body force F.

      In the above equation (3) represents the relaxation time and the local equilibrium Particle Distribution, it can be expressed as shown below while modeling typical diffusion phenomenon,

      In the above equation (4) is the macroscopic fluid density. By applying the Chapman Enskog expansio [12], the following diffusion equation can be recovered from LBM,

      By substituting by the signed distance function in equation (5), the LSE can be recovered. The D2Q5 LBM lattice structure model was used while solving LSE. The body force F acts as the link with image statistics for the LBM solver.

      Figure 1.1 Gray-Scale Image-Preprocessed

   2. Segmentation

      The level set method was initially proposed to track moving interfaces. It can be used to efficiently address the problem of curve or surface propagation in an implicit manner. The main idea is to represent the evolving contour using a signed function whose zero correspond to the actual contour. Then, according to the motion equation of the contour, one can easily derive a similar flow for the implicit surface that when applied to the zero level will reflect the propagation of the contour.

      The level set method has many advantages, it is implicit, it is parameter free and provides a direct way to estimate the geometric properties of the evolving structure. It can be used to define an optimization framework for addressing many applications of computer vision and medical image analysis.

   3. Lattice Boltzmann Solver

      Let consider the above defined LSE. The gradient projection method [5][6] allows to replace ) by |, and as is a signed distance function (SDF) , so | = 1. Thus this LSE can be rewritten as

      )

      which is similar to Eq. (5) with the body force expressed as

      Where is a controlling parameter used to adjust the impact of F on the active contour motion. Thus the level set equation Eq. (10) is solved using the following lattice Boltzmann evolution equation

      Without the necessity of explicitly compute the curvature since it is implicitly handled by the LBM.

   4. Level Set Method

   Level set methods are a powerful tool for performing contour evolution. Define some function (i, j, t) (the level-set function), where (i, j) are coordinates in the image plane and t is an artificial time. At any given time, the level set function simultaneously defines an edge contour and a segmentation of the image. The edge contour is taken to be the zero level set {(i, j) such that (i, j, t)= 0}, and the segmentation is given by the two regions >= 0} and < 0}. The level set function will be evolved according to some partial differential equation, and hopefully will reach a steady state that gives a useful segmentation of the image.

   The segmentation algorithms used in the proposed system Level set method algorithm. This algorithms work well for images with edges, without edges, noise images and medical images. The output of segmentation is as shown in figure 1.2.

   Figure 1.2 Segmented Image using LSM

3. EXPERIMENTAL ANALYSIS AND RESULTS The execution time for few images without using

   GPU and with using GPU is tabulated in the table below.

   Table 8.1 single Image Segmentation time for data

   Input image	Segmentation time without GPU in seconds	Segmentation time using GPU in seconds
   Test_image.jpg	0.5034	0.0499
   ss.jpg	13.416	1.0851
   mom.jpg	13.528	1.27

   The performance characteristic for a single image is plotted in figure 1.3. Performance is evaluated by taking time in Y- axis and Types of execution in X-axis.

   Figure 1.3 Image Segmentation with and without GPU

   Types of execution are Execution with GPU and execution without using GPU. The system showed good results when tested on large size images, improving segmentation speed by 85%.

4. CONCLUSION

The paper has implemented efficient image segmentation algorithm. This algorithm is implemented using an edge, region and 2D histogram information based level set model. The use of the lattice Boltzmann method to solve the level set equation enabled the algorithm to be highly parallelizable and fast when implemented using an NVIDIA (GeForce Titan GTX) graphics processing units. Experimental analysis is done on various sizes of images. The system showed good results when tested on large size images, improving segmentation speed by 85%. Future work will be to use the method for GPU cluster accelerated real-time volume images segmentation.

ACKNOWLEDGEMENT

The proposed algorithm is implemented using NVIDIA GPU (GeForce Titan GTX). The Titan GTX used for this research was donated by the NVIDIA Corporation. We gratefully acknowledge the support of NVIDIA Corporation with the donation of the Tesla K40 GPU used for this research.

REFERENCES

1. S. Balla-Arabe and X. Gao, A multiphase entrophy-based level set algorithm for MR breast image segmentation using lattice Boltzmann model, in Proc. Sino, Foreign, Interchange Workshop Intell. SciIntell. Data Eng., pp. 8-16. Oct. 2013.

2. Yuan Mei, Xinhui Wang, Jin Wang. Image Processing and Pattern Recognition, International Journal of signal processing, Vol. 6, no. 3, June 2013.

3. D. Adalsteinsson and J.A. Sethian, A fast level set method for propagating interfaces, J. Comput. Phys., vol. 118, no. 2, pp.269-277, May 1995.

4. C. Li, R. Huang, Z. Ding, J. Chris, D.N. Metaxas, and J.C. Gore, A level set method for image segmentation in the presence of intensity inhomogeneities with application to MRI, IEEE Trans. Image Process., Vol. 20, no. 7, pp. 2007-2016, Jul. 2011.

5. K. Zhang, L. Zhang, H. Song, and W. Zhou, Active contours with selective local or global segmentation: A new formulation and level set method, Image Vis. Comput., Vol. 28, no. 4, pp. 668-676, Apr. 2010.

6. C. Brun, N. Lepore, X. Pennec, Y. Chou, A. Lee, G. De Zubicaray, K.

   L. McMahon, M.J. Wright, J. C. Gee and P.M. Thompson, A nonconservative Lagrangian framework for statistical fluid registration- SAFIRA, IEEE Trans. Med. Imaging, Vol. 30, no. 2, pp. 184-202, Feb. 2011.

7. R. Malladi, J. Sethian, and B. Vemuri, A topology independent shape modeling scheme, Proc. SPIE, Vol. 2031, pp. 246-258, Jun. 1993.

8. N. Paragios and R. Deriche, Geodesic active contours for supervised texture segmentation, in Proc. IEEE Conf. Comput, Vis. Pattern Recognit., pp. 1034-1040. Nov. 1999.

9. S. Balla-Arabe and X. Gao, Image multi-thresholding by combining the lattice Boltzmann model and a localized level set algorithm, Neuro Computing, Vol. 93, pp. 106-114, Sep. 2012.

10. S. Succi, The Lattice Boltzmann Equation For Fluid Dynamics And Beyond Numerical Mathematics And Scientific Computation. New York, NY, USA: Oxford Univ. Press, Aug. 2001.

11. Y. Zhao, Lattice Boltzmann based PDE solver on the GPU, Vis. Comput., Vol. 24, no. 5, pp.323-333, May 2007.

12. S. Chapmann and T.G. Cowling, The Mathematicl Theory Of Non- Uniform Gases: An Account Of The Kinetic Theory Of Viscosity, Thermal Conduction And Diffusion In Gases. Cambridge, U.K.: Cambridge Univ. Press, 1990.

13. J. Buick and C. Greated, Gravity in a lattice Boltzmann model, Phys. Rev. E, Vol. 61, no. 5, pp. 5307-5320, May 2000.