Interactive Image Segmentation Based On Multiple Linear Reconstruction

Interactive Image Segmentation Based On Multiple Linear Reconstruction

Alisha Abraham

Calicut University

Abstract

The task is formulated as a problem of graph-based transductive classification. Specifically, given an image window, the colour of each pixel in it will be reconstructed linearly with those of the remaining pixels in this window. The optimal reconstruction weights will be kept unchanged to linearly reconstruct their class labels. The label reconstruction errors are estimated in each window. These errors are further collected together to develop a learning model. Then, the class information about the user specified foreground and background pixels are integrated into a regularization framework.

1. Introduction

   Image segmentation has often been defined as the problem of localizing regions of an image relative to content. Recent image segmentation approaches have provided interactive methods that implicitly define the segmentation problem relative to a particular task of content localization. Image segmentation requires user guidance of the segmentation algorithm to define the desired content to be extracted. The goal of interactive image segmentation is to cut out a foreground object from its background with modest user interaction In some case reconstruction is based on unlabelled pixels and some may be based on spatial window Here consider different reconstruction based on foreground and background pixels. .The difficulties lie in two aspects. On the low level it is difficult to model visual elements. On the high level it is difficult to group truthfully the visual patterns into then needed object regions. In the absence of prior knowledge about the image, none of these two aspects can be easily solved. In practice, such difficulties encourages the development of interactive image segmentation with human computer interface, the user can label the foreground and background. In view of the

   pattern classification, such a labelling is fundamentally important. In this let us discuss interactive image segmentation approaches and methods used for implementations. In this paper compare several techniques of interactive image segmentation and compare the differences in different techniques.

2. Different Techniques

   In early methods several techniques such as random walk, spline regression and so on and in recently multiple linear reconstruction is used. Let us discuss several techniques:

   1. Random Walker

      In random walk each seed specifies a location with a user- defined label. A random walker starting at this location, the probability that it first reaches each of the K seed points. Calculation may be performed exactly without the simulation of a random walk. By performing the calculation, we assign a K-tuple vector to each pixel that specifies the probability that a random walker starting from each unseeded pixel will first reach each of the K seed points. A final segmentation may be derived from these K-tuples by selecting for each pixel the most probable seed destination for a random walker. By biasing the random walker to avoid crossing sharp intensity gradients, quality segmentation is obtained that respects object boundaries.

   2. Spline Regression

      Spline is a combination of linear and Greens functions developed in Sobolev functional space. It is suitable for the task of scattered data interpolation and thus popularly used in geometrical design. There are two main advantages it is smooth and able to approximate the interpolation values at the scattered data points .

      The user-specified foreground and background pixels, and used as a prediction function for those unlabeled pixels. SR is fast and can generate satisfactory segmentations for most natural images with adequate user specified strokes. The spline on the user specified foreground and background pixels, and solves its parameters (the combination coefficients of functions) from a group of linear equations. To speed up spline construction, K-means clustering algorithm is employed to cluster the user specified pixels.

      1. Intelligent Scissors

         The intelligent scissors algorithm treats the image as a graph where each pixel is associated with a node and a connectivity structure is imposed. This technique requires the user to place points along the boundary of the desired object. Dijkstras algorithm is then used to compute the shortest path between the user-defined points and this path is treated as the object boundary. The algorithm is simple to implement, very fast and may be used to obtain an arbitrary boundary with enough points. A low-contrast or noisy boundary may require the specification of many points and the algorithm is inapplicable to 3D boundaries.

      2. Adaptive GMMRF model

         The operation of adaptive segmentation model, termed a Gaussian Mixture Markov Random Field(GMMRF). The desired object has been cleanly separated from its background with a modest amount of user interaction. Stripping away details of user interaction, the basic problem input consists of an image and its trimap. The trimap defines training regions for foreground and background, and the segmentation algorithm is then applied to the unclassified region in which all pixels must be classified foreground or background. Error rates for GMMRF segmentation are calculated throughout using a new image database, available on the web, with ground truth provided by a human segmented.

      3. Supervised Segmentation

         Supervised segmentation algorithms typically operate under two paradigms for guidance: ) Specification of pieces of the boundary of the desired object or a nearby complete boundary that evolves to the desired boundary, 2) Specification of a small set of pixels belonging to the desired object and a set of pixels belonging to the background. The automatic segmentation algorithms might be considered by the

         supervised by subsequent user selection. of the desired segment. However, if the desired object is not a complete segment, a secondary clustering/segmentation algorithm must be employed to split or merge the automatic segments.

      4. Learn with Local and Global Consistency The general problem of learning from labelled and unlabeled data, which is often called semi-supervised learning. A principled approach to semi-supervised learning is to design a classifying function which is sufficiently smooth with respect to the intrinsic structure collectively revealed by known labelled and unlabeled points. The goal is to predict the labels of the unlabeled points. The performance of an algorithm is measured by the error rate on these unlabeled points only. The basic idea of method is to construct a smooth function. It is natural to consider using this method to improve a supervised classier by smoothing its classifying result.The classifying result given by a supervised classier as the input.

      5. Adaptive Weighted Distances

         An interactive algorithm for soft segmentation of natural images. The user first roughly scribbles different regions of interest, and from them, the whole image is automatically segmented. This soft segmentation is obtained via fast, linear complexity computation of weighted distances to the user-provided scribbles. The adaptive weights are obtained from a series of Gabor filters, and are automatically computed according to the ability of each single filter to discriminate between the selected regions of interest. The underlying framework and examples showing the capability of the algorithm to segment diverse images.

      6. Interactive Gaph Cuts

         The user marks certain pixels as object to provide hard constraints for segmentation. Additional constraints incorporate both boundary and region information. Cuts are used to find the globally optimal segmentation of the N-dimensional image. It provides a globally optimal solution for an N-dimensional segmentation when the cost function is clearly defined. A globally optimal segmentation can be very efficiently recomputed when the user adds or removes any hard constraints .This allows the user to get any desired segmentation results quickly via very intuitive interactions. The segmentation boundary can be anywhere to separate the object seeds from the background seeds.

      7. Multiple Linear Reconstructions

      This method uses graph-based algorithm for interactive image segmentation. Specifically, give a 3 X 3 local window; the colour of each pixel in it will be linearly reconstructed with those of the remaining eight pixels. The optimal weights will be transferred to linearly reconstruct its class label. To develop a graph- based algorithm of transductive classification, the key is to properly represent the pixels in each window. To this end, we consider to linearly reconstruct their colours. This treatment is reasonable as in general the colours of the neighbouring pixels are similar to each other.

3. Algorithm:

   The steps of the algorithm, multiple linear reconstructions in windows (MLRW) .There are no complex computations in MLRW. In addition, is a highly sparse matrix. The size of each is 9X9 and the 3x 3 windows are overlapped with each other

4. Algorithm of MLRW:

   Input: Image with pixels to be segmented; the set of the user-specified foreground pixels and the set of the user- specified background pixels two parameters r and l

   Output: The segmentation of F 1: Construct X where x=[r,g,b] ,

   2: Allocate a sparse matrix .

   3: for each pixel , pi=1,2,3, ,n do n

   4: Allocate a zero matrix . 5: for j=1,2,3,.9 , do 6: Calculate ,Mij.

   7: .Mij=Mi+Mj

   8: end for

   9: M=M+SMiSj, according to (13).

   10: end for

   11: Construct diagonal matrix , according to (16). 12: Construct vector , according to (17).

   13: Solve ,f, according to (15). 14: for ,i=1,2,..n do

   15: Label as pi , if ; , otherwise. 16: end for

   Figure 1: Flowchart of the algorithm

5. Comparison

   MLRW with the commonly-used algorithms of graph cut (GC) and RW in interactive image segmentation. We also compare it with the classical transductive algorithms of GRF and LLGC. In addition, SLRW will be also compared to illustrate the effectiveness of algorithm. In GC, the algorithm is implemented. The label likelihoods of pixels are calculated via the approach used. To speed up the calculation, Kmeans clustering algorithm with 20 clusters is run to cluster, respectively, the colours of the user-specified foreground and background pixels.

   GC can generate satisfactory segmentations where the foreground and background pixels have different colours. If the foreground and background have similar colours and those colours are not labelled by the user, GC may generate unsatisfactory segmentations.

   RW is a powerful algorithm. However, it may also generate unsatisfactory results for complex natural images. More user-specified strokes are needed to guarantee that the random walk starting from an unlabeled pixel meets first the labelled pixel belonging to its own class.

   GRF and LLGC generate unsatisfactory results. More user-specified strokes are needed to block the leaking of label propagation into the unwanted regions. In addition, the segmentations also indicate that MLRW significantly outperforms SLRW. The segmentation accuracy is calculated as the ratio of correct segmented pixels with respect to the ground truth segmented by gaussian stochastic process. When the stochastic process concerns an entire region of space we talk about a Gaussian random field.

   In a homogeneous Gaussian random field the one-point Gaussian distribution the probability at any one

   location within that volume for having a value Yc = [y; y + dy] is given by the one-point Gaussian distribution. image window with the same pixel colour, the Laplacian matrix deduced by LSR will equal to a unique constant Laplacian matrix. MLRW can speed up LSR.The Laplacian matrix in LSR will be replaced by a constant Laplacian matrix.

   SR is developed in view of discriminative learning. SR need not solve a large group of linear equations. Thus, it is fast and can run with low memory. However, SR may generate segmentations with noises .The reason is that the pixels are segmented one-by-one by the learned spline, without considering their spatial relations on the image grid.

   LSR is developed SR from discriminative learning to transductive learning. Differently, SR learns a unique spline for all of the pixels to be segmented, while LSR employs a group of splines, each of which is used to only map the pixels in a 3x 3 window. As a graph- based learning algorithm, LSR explicitly utilizes the spatial relations between pixels when it is applied to image segmentation.

   LSR needs to construct the Laplacian matrices in image windows and solve large-scale linear equations. More time will be taken and large memory will be required to fulfilled the segmentation.MLRW is also a transductive learning algorithm. Differently, LSR uses spline to map the pixels in each window, nonlinearly, into their classes labels, while MLRW linearly reconstructs them.. Based on SR, LSR, and MLRW, can focus on developing a segmentation system for very large images.

   The large-scale sparse linear equations in LSR and MLRW can be solved iteratively by combining conjugate gradient, image pyramid, and multi-grid methods. In this process, SR can be used to provide an initial solution.

6. Advantages

   Both of them have their own explicit meanings, which are all independent of data .Need not be tuned well from image to image. The most complex computation is to solve sparse symmetrical linear equations. The main computation time will be taken to fulfill the linear reconstructions in the windows of 3.3 pixels.

7. Conclusion

   The key idea is to linearly reconstruct the colour vector of each pixel with those of the remaining pixels also in the window. The estimated optimal reconstruction weights are transferred to linearly reconstruct the class label of each pixel. In this way, the label reconstruction errors are estimated and minimized to obtain the finally segmentation. . It is used in different areas of medical imaging MRI flooding & machine versions. In the existing top-down methods is that they significantly depend upon the accuracy of image segmentation, and the performance of these methods may be degraded by inaccurate image segmentation. In this all images are all independent of data .It need not be tuned well from image to image. The most complex computation is to solve sparse symmetrical linear equations. More time will be taken and large memory will be required to fulfil the segmentation.

8. Reference

1. L. Gray, Random walks for image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., vol. 28, no. 11, pp. 17681783, Nov. 2006 .

2. S. Xiang, F. Nie, C. Zhang, and C. Zhang, Interactive natural image segmentation via spline regression, IEEE Trans. Image Process., vol 18, no. 7, pp. 16231632, Jul. 2009.

3. E. Mortensen and W. Barrett, Intelligent scissors for image composition, in Proc. SIGGRAPH, Los Angeles, CA, 1995, pp. 191 198.

4. A. Blake, C. Rother, M. Brown, P. Perez, and P. Torr, Interactive image segmentation using an adaptive GMMRF model, in Pr Eur.Conf. Computer Vision, Prague, Czech Republic, 2004, pp. 428441.

5. X. J. Zhu, Z. Ghahramani, and J. Lafferty, Semi-supervised learning using gaussian fields and harmonic functions, in Proc. Int. Conf. Machie Learning, Washington, DC, 2003, pp. 912919.

6. A. Protiere and G. Sapiro, Interactive image segmentation via adaptive weighted distances, IEEE Trans. Image Process., vol. 16, no. 4, pp.10461052, Apr. 2008.

7. D. Hoiem, A. A. Efros, and M. Hebert. Automatic photo pop- up. ACM Trans Graph., 24(3):577584, 2005.

8. D. Zhou, O. Bousquet, T. Lal, J.Weston, and B. Scholkopf, Learning with local and global consistency, in Proc. Advances in Neural Information Processing Systems 16, Vancouver, BC, Canada, 2003, pp. 321328.

9. W. A. Barrett and A. S. Cheney, Object-based image editing, in

Proc. SIGGRAPH, San Antonio, TX, 2002, pp. 777784

[10]Y. Boykov and M. Jolly, Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images, in Proc. Int. Conf. Computer Vision, Vancouver, BC, Canada, 2001, pp. 105 112.