《外文翻译-- A Novel and Multi-Scale Unsupervised Algorithm for Image Segmentation》由会员分享，可在线阅读，更多相关《外文翻译-- A Novel and Multi-Scale Unsupervised Algorithm for Image Segmentation（5页珍藏版）》请在金锄头文库上搜索。
1、A Novel and Multi-Scale Unsupervised Algorithm for Image Segmentation Luo Minmin, Jiang Guiping, Lin Ya-zhong School of Biomedical Engineering Southern Medical University Guangzhou China Abstract: Gibbs Random Fields (GRF) is a popular prior model widely used in Bayesian segmentation due to its exc
2、ellent property in describing the spatial information of image. But until now, the classical approaches, describing the Markovian property of single-scale instead that of multi-scale, may come across some difficulties such as expensive computation and unsupervised parameter estimation of GRF. Thus,
3、in this paper, a novel and unsupervised algorithm named multi-scale GRF that addresses these problems perfectly is proposed by extending the classical single-scale model of GRF to a multi-scale one at the first time. Experiments have shown that our algorithm presented in the paper has excellent robu
4、stness and easy to be used in unsupervised and precise segmentation. Keywords: MRF; GRF; multi-scale segmentation; segmentation approach I. INTRODUCTION Segmentation technology is not only the basis of pattern recognition and image understanding, but also one of the important goals of image processi
5、ng. Labelling every pixel correctly is a key to image segmentation. The successful application of GRF model to describe spatial correlation of image pixel makes Bayesian segmentation popular. The parameter of the traditional single-scaled GRF model used to describe this correlation is very complicat
6、ed4, 3 (the parameter number is the number of shape 1in the clique) and the cost required is huge. In traditional multi-scale algorithm, there will be different GRF parameters on different scales, namely a problem of parameter selection. Thus, while lelbellging pixels on a certain scale, we do not s
7、imply carry out quadtree partitioning, but also adopt graph structure to reflect Markov characteristics on different scales. This can transmit the correlation between low-resolution pixels to a high-resolution zone, and fundamentally solve the problem of correlation description that can only be sett
8、led by means of high-order neighborhood on a single scale. Meanwhile, the MAP estimation is only for pixels on the highest scale and recusion rather than iterative process is used on other layers, which accordingly settles the problem of algorithm speed. In short, the application of multi-scale GRF
9、model (Multi-scale GRF, MGRF) is beneficial to: 1) preventing complicated parameter estimation of partition function; 2) preventing complicated iterative computations and saving a lot of cost; 3) realizing extension and application of GRF model on different scales; and 4) describing images more prec
10、isely and making segmentation more accurate and reliable. This paper is organized as follows: Part II is about the establishment of multi-scale GRF, namely MGRF; Part III is a detailed introduction of MGRF unsupervised segmentation approach; 978-1-4244-4713-8/10/$25.00 2010 IEEEPart IV is about expe
11、riments conducted in different noises. A conclusion is made according to the results of brain MR segmentation by mean of SGRF and MGRF algorithms respectively. II. MGRF MODEL Similar to other model1, the MGRF also adopts second-order Gibbs neighborhood, and only its unitary and dualistic cliques are
12、 considered. But, the Gibbs model discussed here is conducted between graph structures. These nodes are distributed at different scales rather than traditionally at the same scale. Besides, as the number of pyramid layer rises from the bottom up, the resolution of image will descend gradually. Repre
13、senting original image input, the resolution on layer 0 (bottom) is the highest and the resolution on layer L (top) is the lowest, and a parent-child relationship is tied up between adjacent layers. For example, layer 1 is the parent of layer 0 and layer 0 is the child of layer 1, and so on and so f
14、orth. In MGRF model, the labeling of pixels at a certain scale is realized by means of two decomposition processes and maximum posteriori estimation of structural model,.Namely, quadtree decomposition of child layer and graph structure decomposition of parent layer. For the convenience of understand
15、ing, Figure 1 is a schematic diagram of one-dimensional structural model (n=2). In this model, it is assumed that, the random field represented by each layer is only related to its parent layer (satisfying local correlation) and each pixel at the same scale is mutually independently (satisfying the
16、independence) under the neighborhood of parent layer given. If )(nX and )(nS respectively indicate the random field at Scale n and pixel set at the scale, there will form a multi-scale Markov Chain3from higher scales to lower scales. ),|()()()()(nlxXxXPllnn= )|()1()1()()(+=nnnnxXxXP )|()1()(|)1()(+=
17、nnxxxxpnn ( 1 ) Therefore, the joint distribution of random field X and Y can be represented by the following product formula: ),(xXdyYP= ( 2 ) )().|()|()()1()(|10)0(|)()1()()0(LxnnxxLnxyxpxxpxyPLnn+=+= Figure 1: One-Dimensional Structural Model (Scale Level n=2) (n2: graph structure; n2: quadtree s
18、tructure) In MAP segmentation, the MGRF model utilizes graph structure to get prior probability of pixel points and acquire likelihood probability by means of quadtree structure. In Figure 2, we can see the coincidence relation between Node) 1 , 1 ()0(x and its second-order neighborhood node of pare
19、nt layer on Scale 0:) 1 , 1 (),0 , 1 (),1 , 0(),0 , 0()1()1()1()1(xxxx. The node correlation at other scales can be figured out by analogy. Figure 2: Coincidence Relation between Node (1, 1) and Neighborhood Nodes of Parent Layer on Scale 0 With this model, we can conduct MAP estimation for pixels a
20、t the highest scale (Layer L) and label pixels at lower scales by means of a recurrence formula. Namely: When the observed image Y and )1( +nxestimated on this layer is given, the following recursion formula can be used to tag pixels on the child layer: )|(logmaxarg)(|)()()(yxpxLyxxLLL= (3) ),|(logm
21、axarg)1()(,|)()1()()(yxxpxnnyxxxnnnn+=, Ln (4) According to the Bayes formula and provided that )(LX is distributed uniformly, the above recurrence formula can be changed into: )|(logmaxarg)(|)()()(LxyxLxypxLL= (5) +=)|(logmaxarg)()(|)(nxyxnxypxnn )|(log)1()(|)1()(+nnxxxxpnn Ln (6) Formula (6) shows
22、 that: this kind of segmentation approach is realized by means of likelihood logarithm of quadtree structure and prior logarithm of graph structure. III. REALIZATION OF MGRF SEGMENTATION Unlike the traditional multi-scale segmentation practices6, 5, this algorithm is executed at coarse and fine stag
23、es twice respectively. The first execution is to get parameters of the model and the second one is to realize accurate segmentation. In formula (6), the first item to be maximized on the right is likelihood. For the convenience of calculation and on the premise that its maximization is not affected,
24、 its logarithm is adopted in this paper. Provided that:)()(sdnrepresents the parent-layer neighborhood of pixels in quadtree structure at Scale n and )()(sdnrepresents Node s along the tree structure at scale n; 1 , 0nrepresents the transmission probability of labels from nodes on parent layer to th
25、e nodes on this layer; and provided that the type of neighborhood on parent layer is k, the density function of interlayer transmission of pixels in Type m will be as follows: Mkmpnkmnxxnsns+=+1.)|(,|)1()( (7) Thereinto: km, is the function of Dirac and M is the type number of image. Based on assume
26、d independence of the model, the conditional density function on this layer will be: )|()|()()(|)(|)()()()(nsnsxySsnxyxypxypnsnsnn=(8) Its logarithmic formula will be: )|(log)()(|)()()(kypklnsxynsnsns= (9) According to assumed local correlation of the model, the following iterative formula can be us
27、ed to complete likelihood computation of logarithm from lower scales to higher scales: )|(log)()0(|)0(kypklsxysss= (10) +=+)(exp.log)()()()1()1(klklnrnsdrns )(exp1)(1mlMnrMmn= (11) In formula (6), the second item to be maximized on the right is a prior logarithm. Provided that 1 , 0nindicates coinci
28、dent probability remained between nodes in graph structure and nodes on parent layer, and s1,s2,s3, and s4 represent the second-order Gibbs neighborhood of node s (i,j), the coincidence function will be as follows: ),|()1()(|okjimpnsnsxx+),|()1(4)1(3)1(2)1(1)(oXkXjXiXmXPnsnsnsnsns=+Mnomkmjmimn+=1)(4
29、, (12) By means of acquisition of likelihood function and prior function respectively, the following recursion formulas can replace formula (5) and formula (6). This accordingly realizes layered segmentation of an image through MGRF algorithm: )(maxarg)(1)(klxLsMkLs= (13) )|(log)(maxarg)1(|)(1)()1()
30、(+=nsxxnsMknsxkpklxnsns Ln (14) In the process of segmentation, the parameter ,nn=needs to be estimated. The parameter is estimated at the first coarse stage by means of EM algorithm. The common cost function of estimated parameter n is as follows. After estimation ofn, we can figure out ndirectly:
31、).|(log(),()(|/)(nxynnXypEQn= |),|()1()(|)1()(nnnxxxXpnn+ ,/)1()1(nnnxXyY+= (15) In short, the detailed steps of unsupervised MGRF segmentation approach are: 1 Initialization of parameters: 5 . 0, 11=Ln; the number of cluster is specified as: M=4; 2 Acquire various kinds of mean value and variance b
32、y means of K-Means and use them as initial values for each type; 3 Use formula (10) and (11) to complete likelihood computation of logarithm from lower scales to higher scales; 4 Use formula (13) to tax each pixel at the highest scale; 5 Conduct the following treatment from scale n=L-1 to scale n=0:
33、 (a) Use EM algorithm to estimate the value of parameternn,; (b) Use formula (14) to tag pixels on different scales; (c) Use)101 (21=nnto update parameters. Here, 2is the positive minimum; 6 Repeat from step 3 to step 5 to complete image segmentation. IV. EXPERINENT AND CONCLUSION In this experiment
34、, we compare segmentation of a 128*128 brain MR image by means of MGRF, ICM and SA under different noise interference. The original image is of 4 types, respectively: background, cerebrospinal fluid, gray matter, and white matter. The mean valueand variance2acquired by means of K-Means are: (0.85, 8
35、.56), (72.47, 534.30), (128.73, 416.3), and (172.37, 254.66) respectively. Line 1, Line 2 and Line 3 in Figure 3 represent the segmentation results acquired by means of MGRF, ICM and SA with 0%, 10% and 20% noise interference respectively. The experiment was made on a P4 computer with 1.7G CPU, 512M
36、, VC6.0. And the time used is 0-1 second in MGRF, 21-23 seconds in ICM and 179-186 seconds in SA. The experiment shows that, the MGRF model mentioned in this paper can be used to realize rapid and accurate image segmentation. From the results, we can see that: in case of no noise interference, the s
37、egmentation results by means of three kinds of algorithm are nearly the same; as more noises come, the segmentation results under different algorithms are damaged to a certain degree, but the deterioration of MGRF is the slowest. Especially with 20% of noise interference, only MGRF can distinguish w
38、hite matter and gray matter, and the other two algorithms do not work. The main reason is that, through the interlayer transmission of Markov characteristics, MGRF algorithm can help to overcome the limitation of large-sized pixel correlation that cant be described by the other two SGRF algorithms u
39、nless high-order neighborhood is introduced. Compared to SGRF, MGRF is of higher robustness. Besides, with the use of “partitioning” technology, no high-order neighborhood needs to be introduced for MGRF. Thus, it is faster than SGRF. Figure 3: Segmentation Results by Means of Different Algorithms R
40、EFERENCES 1 H. Derin and H. Elliott, “Modeling and Segmentation of Noisy and Textured Images Using Gibbs Random Fields J”, IEEE. TPAMI, 1987, 9(1): 39-55 2 John Ashburner, and Karl J. Friston, “Unified segmentation J”, NeuroImage, vol. 25, No. 3, pp. 839-851, 2005. 3 P. F. Felzenszwalb and Daniel P.
41、 Huttenlocher, “Efficient Graph-Based Image Segmentation J”, International Journal of Computer Vision, vol. 59, No. 2, pp. 167-181, 2004. 4 Hui Cheng, “Document Image Segmentation and Compression D”, PHD thesis, Purdue University Aug. 1999 5 R. Wilson and C. Tsun-Li, “Multiresolution Random Fields and Their Application to Image Analysis R” Research Report CS-RR-361, Department of Computer Science, University of Warwick, Coventry, UK, Aug. 1999 With 0% Noise With 10% Noise With 20% Noise Original
