A Semi-Supervised Automatic Optimization Model for Segmentation of Multiple Images

A Semi-Supervised Automatic Optimization Model for Segmentation of Multiple Images

R. Arul Renista, *R. Eveline Pregitha

PG Student, Department of Electronics and Communication Engineering, James college of Engineering and Technology, Navalcaud.

*Department of Electronics and Communication Engineering, James college of Engineering and Technology, Navalcaud.

Abstract

A semi-supervised optimization model for determining an efficient segmentation of many input images is proposed. The advantage of optimization model is twofold. Firstly, the segmentation is highly controllable as the portion chosen for segmentation can be specified by providing the labeled pixels in images for the model either offline or interactively. Secondly, the optimization model requires only minute tuning of model parameters during the beginning stage. Once initial tuning is done, it can be used to automatically segment a large collection of images that are distinct but, share similar features. It is proposed to conduct extensive experiments on various collections of biological images, it will be established that the model proposed is quite computationally efficient and effective for segmentation.

Keyword- Biological image segmentation, Interactive Image segmentation, Microscopic images, multiple images

I.INTRODUCTION

Image segmentation is the process of partitioning a digital image into multiple segments and used to locate objects and boundaries (lines, curves) in images. It is used in many areas, including computer vision, computer graphics, and medical imaging. Types of image segmentation are fully automatic image segmentation and Semi- automatic image segmentation. Completely

automatic image segmentation has many intrinsic difficulties is still a very rigorous problem. For example, it is very often that an image can have much segmentation that is meaningful. Various Fields like medical or biomedical imaging, objects of interest (OOIs) are often badly defined and even sophisticated automatic segmentation algorithms often fail. Moreover, in cell segmentation in microscopy images and organ segmentation in medical images, the kind of object and segmentation of interest are known in advance. It is, therefore, enticing to design segmentation methods that allow the user to specify what the user wants.

For these situations, the only possibility until recently was to replace automatic methods by interactive ones, where a lot of interaction between the user and the image is necessary, either to draw the contours of OOIs. It is always very tiresome. So, it is replaced by semi-automatic image segmentation, with a very limited amount of user interaction. Many types of semi-automatic methods have been suggested: intelligent scissors, methods based on user steered image segmentation paradigms and methods based on the concept of fuzzy connectedness.

The segmented objects are clustered to retrieve the original image. In clustering there are three types of clustering. They are supervised, unsupervised and semi-supervised. Semi- supervised clustering is introduced to cover some drawbacks of clustering (unsupervised learning) and classification (supervised learning), such as production of non acceptable clusters or sometimes finding multiple grouping of data in the clustering process. In this situation semi-supervised clustering could be a good choice. Semi-supervised clustering uses some side-information to cover the

categorization goal. The side-information could be the similar pairs from input data or information that indicates membership of the data items to specific clusters. This side-information usually has the pairs-wise (must-link and cannot-link constraints) form in most studies. Must-link constraints impose data on the same cluster but, cannot-link constraints impose them on different clusters.

In semi-automatic segmentation, the user marks some sample pixels from each class of objects. Then computational algorithm computes a classification of other pixels from each class of objects. This way, the resulting segmentation is highly controllable by the user and thereby eliminates much ambiguity in defining a partition. Because of this property it is used in medical field [2] & [3].

Initially optimization model is available for single class only. Later an optimization-based two-class segmentation model [4] is developed, in which an optimal class membership function is computed through the minimization of a quadratic cost function with user supplied samples as linear constraints. The basic idea is that two pixels should have similar membership if they are either geometrically similar or photo metrically similar or both. The results are quite impressive. The model was later extended [5] in to handle the multiple class problem. A few effective numerical optimization methods and fundamental theoretical properties of the model were studied [6], [7] & [8].

Single-image optimization models were

are discussed. In Section III, the experimental result of the proposed model is shown. In Section IV, some concluding remarks are given.

1. PROPOSED SYSTEM

   In this section, the formulation of the proposed model is stated. The two image-multiple class case is illustrated. This two image model can be used to segment collection of images one at a time. The generalization to multiple-image multiple class case is clear.

   2.1 Optimization Model

   ,

   ,

   Let us for s=1, 2 be two given multi channel images. The sizes are not necessarily the same. Let s be the set of all pixels in image us. Let s be the set of whole unlabeled pixels in image. Let s be the set of pixels in image us labeled to one of the M classes by the user. Thus s = s s which allowing both labeled and unlabeled pixels contained in the image. The set of labeled pixels s is divided into s/1,, s/M, where s/m is the set of pixels that are labeled with class m, for m=1,, M. s is an index referring to an image different from the image indexed by s. For each pixel I s and each pixel j t , let , 0 be a similarity between

   ,

   ,

   the pair of pixels, for s, t=1,2. When t=s, the similarity , is computed within image us; when

   t=s, the similarity is computed across two images. For each i s, the similarity scores and normalized as shown in (1)

   extended to the multiple-image for image retrieval.

   , ,

   + = 1

   (1)

   The various clustering techniques are K-means and

   ,

   s

   ,

   support vector machine. K-means is an unsupervised method used to group the objects based on attributes/features into K number of

   For each pixel I s , let , t be a set of pixels in image, which is called the neighbor of I in ut .

   For each I s, let / [0 1] be the degree of

   group. The grouping is performed by minimizing the sum of squares of distances between data and

   membership of pixel i s

   to class m. It is required

   the corresponding cluster centroid. The drawback is user has to specify the number of clusters in advance, not able to handle noisy data and it is not suitable to discover clusters with non-convex shapes. Support Vector Machines is a supervised method, which is well suited for aspect based recognition images and color-based classification.

   that = 1 . It is also denote by the

   =1

   vector / . The basic idea is that the

   membership of similar pixels should be similar. For eah unlabeled pixel i s, membership to class m inferred from its neighbors is weighted average as shown in (2)

   SVM is widely used in object detection and

   s,s + s,s

   (2)

   recognition, Text recognition, etc the drawback is

   ,

   ,

   ,

   ,

   its sensitive to noise, it considers only two classes and image classification problem exist.

   The outline of this paper is as follows. In

   Subject to the constraints,

   0 s/m 1 and

   =1

   / =1 (3)

   Section II, the proposed model and the properties

   For s=1,2 and m=1,,M and the

   boundary condition / = 1, for i s/m and /

   = 0, for i s\s/m. The objective function in (2) can be compactly written in matrix form as shown in

   Where, c is a normalization constant such that

   s,s 1, and 2 is computed as the sample

   2

   2

   (4)

   ,

   J(1,,M) =

   =1

   2

   (4)

   variance of the photometric features withins,s .

   The within image neighbor and the across

   1. Similarity Measures

      Two kinds of similarity measures are, geometric and photometric are. The former is based on pixel locations, whereas the latter is based on color features.

      For each pixel is, its geometric neighbor

      s,s s is defined in (5)

      image neighbor are defined in (9) and (10) as

      s,s Gs,s s,s (9)

      Ns,s s,s (10)

      The combined within image similarity and combined across image similarity is defined in (11) and (12)

      s,s :=(gs,s/(1+) + s,s/(1+))/(1+) (11)

      s,s := {js : 0<i-j rg } (5)

      Where rg>0 is a constant controlling the size of the

      ,

      ,

      s,s

      ,

      ,

      = ,

      = ,

      /(1+) (12)

      window, and . is the vector maximum norm. We often set rg=1 so that a 3*3 window around pixel I is used.

      ,

      ,

      The geometric similarity g, is defined

      Where, > 0 is a tuning parameter controlling the weight between geometric and photometric similarities, and >0 is a tuning parameter controlling the weight between within and across

      image similarities.

      in (6)

      s,s 2/ 2

      s,s

      g, := c

      2 i , if j G

      (6)

   2. Optimality Conditions

      0 , otherwise

      Where e is a normalization constant such that,

      ,

      ,

      = 1, and 2 is computed as the sample

      The objective function in (4) is differentiated and Lagrange multipliers for the constraints is introduced in (3), to shown that the

      , i

      optimality conditions are given in the linear

      variance of the geometric locations withinGs,s . For

      each pixel is, let Fi be its feature vector.

      The within image photometric neighbor

      systems as shown in (13),

      Ãm=bm for m=1,M (13)

      Ã=I-DTDW

      s,s s is defined to be the top 4 pixels within the

      1 1

      2

      2

      2

      2

      =

      1,1

      1 1

      1,2

      17*17 window around pixel whose feature vectors are nearest to Fi . Using a larger window size

      2 2,1

      2 2,2

      allows us to reduce error. The within image

      photometric similarity is defined in (7)

      bm = b

      1

      s,s

      2

      2

      2

      s,s

      2

      ,

      : = c

      2

      , if j

      (7)

      Each unlabeled pixel is connected to a

      0 otherwise

      Where, 2 is computed as the sample variance of the photometric features withinPs,s .

      For efficient computation of the across image photometric neighbor , the top 4 labeled pixels in pixels in S is considered, whose feature vectors are nearest to Fi. Here,S is a

      random sample of such that it contains an equal

      number of pixels from s 1 and 2 . The across image photometric similarity is defined in (8)

      labeled pixel through a sequence of directed edges, each of which connects a pixel to one of its neighbors in the same image or a different image. It shows that the solution is non singular and unique. If the matrix size is small, then linear systems can be efficiently solved by Gaussian elimination. However, if the image size is larger, preconditioned interactive methods [5] are used.

   3. Applications to a Collection of Images

      Suppose u1 contains some manually labeled pixels while other images are unlabeled. To

      2

      2

      2

      5.5

      s,s

      ,

      := c

      2

      , if j

      (8)

      segment a large collection of images, we apply the optimization model to u1 and other image (called u2) at a time. That implies 1 0 and 2=0.

      A simple way to apply the model is to let

      1,2 =0 for all i 1, so that W1,2=0, and let w1,1=G1,1/(1+) + P1,1/(1+).

      In this case, the matrix is a block upper triangular as shown in (15)

      The nuclei cell test image is taken to segment one at a time using the proposed semi- supervised optimization model. The original image is a color image. It is having multiple levels of optimization model segmentation.

      1

      1 1,1 0

      original image second level pso

      Ã=

      2 2 2,1 2 2 2,2

      (14)

      The parameters and are manually tuned to solve 1/m and the first unlabeled image. Then, these values are used to segment all other images. Thus the tuning is quite comportable for the collection that is used.

      If there K>1 in images that contain labeled pixels, then we can simply apply the model for k+1 images to segment one unlabeled image at a time. The proposed model is easy to be extended. For the single image case, it show that m satisfies the strong maximum principle, which guarantees the strict in equalities 0< m <1 and the uniqueness of m [5]. For the multiple image, if W1,2=0, then the feeble maximum principle, which implies 0 m 1 only. However, the more important uniqueness of m still holds.

   4. Computational Complexity

   In optimization model, the computational costs is discussed in the following steps

   Step1) Compute P1, 1(independent and )

   Step2) Compute 1, 1 (dependent on ) and solve the

   third level pso fourth level pso

   Figure 1: Segmentation of nuclei cell image obtained by pso optimization model

   original image second level dpso

   third level dpso fourth level dpso

   linear system [I- 1 1 W

   2… M-1.

   1, 1

   ] 1/m

   =b1/m

   for m=1,

   Figure 2: Segmentation of nuclei cell image obtained by dpso optimization model

   Step3) Compute P2, 2 and P2, 1 (independent of and ).

   Step4) Compute W2,1 and W2,2(dependent on and

   original image second level fodpso

   ) and solve the linear system [I-2

   2 W

   2,2

   ]2/m

   = 2 2 W

   2,1

   1/m

   for m=1,.,M-1.

   During the initial tuning stage the parameters are tuned based on the labeled image and the first unlabeled image, steps 1 and 3 are needed to be performed only once, whereas steps 2 and 4 have to be repeated. In this experiment, steps 1 and 3 are often more time consuming than steps 2 and 4. If u1 is fully labeled, then {1/1,, 1/m} are known, and steps 1 and 2 can be skipped. Beginning from the second unlabeled image, only steps 3 and 4 are performed and no further tning of parameters is done.

2. EXPERIMENTAL RESULTS

   third level fodpso fourth level fodpso

   Figure 3: Segmentation of nuclei cell image obtained by fodpso optimization model

3. CONCLUSION

A Semiautomatic optimization model for segmentation of multiple images is developed. The model has a quadratic objective function and linear constraints. Owing to the discrete maximum/

minimum principles, the optimality conditions simply boil down to solve the linear order. In our applications, the two parameters can be easily tuned. Once initial tuning is performed, the setup can be used to segment all other images within the collection automatically. The quality of the results is high. However, it relies on the logical supposition that the different classes can be separated in the feature space and that the user supplied samples can represent each class well.

REFERENCES

1. Michael K. Ng, and M. Yip, A Semi- supervised Segmentation Model for Collections of Images, IEEE transactions on image processing, vol.21, no.6, June 2012.

2. Y.Boykov and V. Kolmogorov, An Experimental Comparison of Min-cut/Max- flow Algorithms for Energy Minimization in Vision, IEEE Trans. Pattern Anal. Mach. Intell., vol.26, no.9, pp.1124-113, sep.2004.

3. A. Protiere and G. Sapiro, Interactive Image Segmentation via Adaptive Weighted Distances, IEEE Trans. Image Process., vol.16, no. 4, pp.1046-1057, Apr. 2007.

4. J. Guan and G. Qiu, Interactive Image Segmentation using Optimization with Statistical Priors, in proc. ECCV, Grav, Austria, 2006.

5. M.K. Ng, G. Qiu, and A.M. Yip, Numerical Methods for Interactive Multiple-class Image Segmentation Problems, Int. J. Imag. Syst. Technol., vol.20, no. 3, pp, 191-201, sep.2010.

6. F. Wang, C. Zhang, H. Shen, and J. Wang, Semi-supervised Classification using Linear Neighborhood Propagation, in Proc. CVPR , 2006,pp.160-167.

7. O. Delzlleau, Y. Bengio, and N. Le Roux, Efficient Non-parametric Function Induction in Semi-supervised Learning, in Proc. 10th Int. Workshop AI Stat., 2005, pp. 96-103.

8. J. Guan and G. Qiu, Modeling User Feedback using a hierarchical Graphical Model for Interactive Image Retrieval, in Advances in Multimedia Information Processing , Ser. Lecture Notes in Computer Science, H.H.-S. Ip, H. Leung, O.C Au, M.-T. Sun, W.-Y. Ma, and S.-M.Hu, Eds. Berlin, Germany: Springer-Verlag, 2007, pp.18-29.

9. J.Guan and G. Qiu, Interactive image matting using optimization, Sch. Comput. Sci. Inf. Technol., Univ. Nottingham, University Park, U.K., Tech. Rep. 01- 2006,2006.

10. C. Rother, V. Kolmogorov, and A. Blake, Grabcut: Interactive foreground extraction using iterated graph cuts, ACM Trans.

    Graph., vol.23, no. 3, pp. 309-314, Aug.2004.

11. J. Wang and M. Cohen, An iterative optimization approach for unified image segmentation and matting, in Proc. IEEE Int. Conf. Comput. Vis., 2005, pp. 936-943.

12. S.Yu and J. Shi, Segmentation given partial grouping constraints, IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no.2, pp.173-183, Feb. 2004.

13. G. Gilboa and S. Osher, Nonlocal linear image regularization and supervised segmentation, Multiscale Model. Simul., vol. 6,no.2,pp. 595 -630, 2007.

14. Y. Boykov and M. P. Jolly, Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images, in Proc. IEEE Int Conf. Comput. Vis., 2001, pp. 105-112.

15. A. Blake, C. Rother, M. Brown, P. Perez, and

P. Torr, Interactive image segmentation using an adaptive GMMRF model, in Proc. ECCV, 2004, pp. 428-441.