220
IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 19, NO. 1, JANUARY 2010
Effective Level Set Image Segmentation With a Kernel Induced Data Term
cumcmMohamed Ben Salah, Amar Mitiche, Member, IEEE, and Ismail Ben Ayed, Member, IEEE
Abstract—This study investigates level t multipha image gmentation by kernel mapping and piecewi constant modeling of the image data thereof. A kernel function maps implicitly the original data into data of a higher dimension so that the piecewi constant model becomes applicable. This leads to a flexible and effective alternative to complex modeling of the image data. The method us an active curve objective functional with two terms: an original term which evaluates the deviation of the mapped image data within each gmentation region from the piecewi constant model and a classic length regularization term for smooth region boundaries. Functional minimization is carried out by iterations of two concutive steps: 1) minimization with respect to the gmentation by curve evolution via Euler-Lagrange descent equations and 2) minimization with respect to the regions parameters via fixed point iterations. Using a common kernel function, this step amounts to a mean shift parameter update. We verified the effectiveness of the method by a quantitative and comparative
performance evaluation over a large number of experiments on synthetic images, as well as experiments with a variety of real images such as medical, satellite, and natural images, as well as motion maps. Index Terms—Kernel mapping, level t image gmentation, mean shift, multipha, piecewi constant model.
托福写作机经
I. INTRODUCTION
A
central problem in computer vision, image gmentation has been the subject of a considerable number of studies [6]–[8], [10]–[13], [16]. Variational formulations [17], which express image gmentation as the minimization of a functional, have resulted in the most effective algorithms. This is mainly becau they are amenable to the introduction of constraints on the solution. Conformity of region data to statistical models and smoothness of region boundaries are typical constraints. The Mumford–Shah variational model [17] is fundamental. Most variational gmentation algorithms minimize a variant of the piecewi constant Mumford–Shah functional (1)
Manuscript received January 07, 2009; revid August 26, 2009. First published September 22, 2009; current version published December 16, 2009. The associate editor coordinating the review of
this manuscript and approving it for publication was Dr. Jenq-Neng Hwang. M. B. Salah and A. Mitiche are with the Institut National de la Recherche Scientifique (INRS-EMT), Montréal, QC, H5A 1K6, Canada (e-mail: mitiche@emt.inrs.ca; bensalah@emt.inrs.ca). I. B. Ayed is with General Electric (GE) Canada, 268 Grosvenor, E5-137, London, N6A 4V2, ON, Canada (e-mail: ismail.). Color versions of one or more of the figures in this paper are available online at ieeexplore.ieee. Digital Object Identifier 10.1109/TIP.2009.2032940
is a piecewi constant approximation of where the obrved data , and is the t of boundary points of . The piecewi constant image model [6]–[9], [17], [18], and its piecewi Gaussian generalization [3], [19], [20], have been the focus of most studies and applications becau the ensuing algorithms reduce to iterations of computationally simple updates of gmentation regions and their model parameters. The more general Weibull model has also been investigated [21]. Although they can be uful, the models are not generally applicable. For instance, synthetic aperture radar (SAR) images, of great importance in remote nsing, require the Rayleigh distribution model [22]–[24] and polarimetric images, common in remote nsing and medical imaging, the Wishart or the complex Gaussian model [25], [26]. The u of accurate models in image gmentation is problematic for veral reasons. First, modeling is notoriously difficult and tim
e consuming [27]. Second, models are learned using a sample from a class of images and, therefore, are generally not applicable to the images of a different class. Finally, accurate models are generally complex and, as such, are computationally onerous, more so when the number of gmentation regions is large [25]. An alternative approach, which would not be prone to such problems, would be to transform the image data so that the piecewi constant model becomes applicable. This is typically what kernel functions can do, as veral pattern classification studies have shown [28]–[31]. A kernel function maps implicitly the original data into data of a higher dimension so that linear paration algorithms can be applied [39]. This is illustrated in Fig. 1 with a 2-D data example. The mapping is implicit becau the dot product, the Euclidean norm thereof, in the higher dimensional space of the transformed data can be expresd via the kernel function without explicit evaluation of the transform. Several studies [28], [29], [32], [33] have shown evidence that the prevalent kernels in pattern classification are capable of properly clustering data of complex structure. In the view that image gmentation is spatially constrained clustering of image data [34], kernel mapping should be quite effective in gmentation of various types of images. This study investigates level t multipha image gmentation by kernel mapping and piecewi constant modeling of the image data thereof. The method us an active curve objective functional containing two terms: an original term which evaluates the deviation of the mapped image data within each g
mentation region from the piecewi constant model and a classic length regularization term for smooth region boundaries. Functional minimization is carried out by iterations of two concutive steps: 1) minimization with respect to the partition by curve evolution via the Euler-Lagrange descent equations and 2) minimization with respect to the regions parameters via fixed
1057-7149/$26.00 © 2009 IEEE
SALAH et al.: EFFECTIVE LEVEL SET IMAGE SEGMENTATION WITH A KERNEL INDUCED DATA TERM
221
Fig. 1. Illustration of nonlinear 2-D data paration with mapping: The data is non linearly parable in the data space. Mapping the data to a feature (kernel) space and, then, parating it in the induced space with linear methods is possible. For the purpo of display, the feature space in this example is of the same dimension as the original data space. In general, however, the feature space is of higher dimension.
point iteration. The latter leads, interestingly, to a mean shift update of the regions parameters. Using
a common kernel function, we verified the effectiveness of the method by a quantitative and comparative performance evaluation over a large number of experiments on synthetic images. In comparison to existing level t methods, the propod method brings advantages with regard to gmentation accuracy and flexibility. To illustrate the flexibility of the method, we also show a reprentative sample of the tests we ran with various class of real images including natural images from the Berkeley databa, medical and satellite data, as well as motion maps. The remainder of this paper is organized as follows. The next ction reviews the Bayesian framework commonly ud in level t gmentation. Section III contains the theoretical contribution. It describes an original kernel-bad functional and derives the equations of its minimization in both two-region and multiregion cas. Section IV describes the validation experiments, and Section V contains a conclusion. II. MULTIPHASE IMAGE SEGMENTATION Let be an image function. regions consists of finding a partition Segmenting into of the image domain so that each region is homogeneous with respect to some image characteristics commonly given in terms of statistical parametric models. In this ca, it is convenient to cast gmentation in a Bayesian framework [12], [13], [25], [35]. The problem would then consist of finding a which maximizes the a posteriori probability partition over all possible -region partitions of
is independent of Assuming that of (2), we have
for
and taking
(3) where
(4) The first term, referred to as the data term, measures the con, to a formity of image data within each region , . The Gaussian distribution parametric distribution has been the focus of most studies becau the ensuing algorithms are computationally simple [13]. The well known piecewi constant gmentation model [2], [6], [8], [34], [35] corresponds to a particular ca of the Gaussian distribution. In this ca, the data term is expresd as follows: (5)
(2)
where , and is . Although ud most often, the mean intensity of region the Gaussian model is not generally applicable. For instance, natural images require more general models [21], and the specific, yet important, SAR and polarimetric images require the Rayleigh and Wishart models [22], [23], [25].
222
IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 19, NO. 1, JANUARY 2010
The cond term in (4) embeds prior information on the gmentation [13]. The length prior, also called regularization term, is commonly ud for smooth gmentation boundaries
eyequous, symmetric, positive mi-definite kernel function can be expresd as a dot product in a high-dimensional space, we do not have to know explicitly the mapping . Instead, we can u a kernel function, , verifying (8) where “ ” is the dot product in the feature space. Substitution of the kernel functions in the data term yields the following non-Euclidean distance measure in the original data space:
(6) where is the boundary of the region and is a positive factor. In the next ction, we will propo a data term which references the image data transformed via a kernel function, and explain the purpo and advantage of doing so. III. LEVEL SET SEGMENTATION IN A KERNEL-INDUCED SPACE To explain the role of the kernel function in the propod gmentation functional, and describe clearly the ensuing algorithm, we first treat the ca of a gmentation into two regions (Sections III-A and III-B). In Section III-C, a multiregion extension is described. A. Two-Region Segmentation The image data is generally non linearly parable. The basic idea in using a kernel fu
nction to transform the image data for image gmentation is as follows: rather than eking accurate image models and addressing a non linear problem, we transform the image data implicitly via a kernel function so that the piecewi constant model becomes applicable and, therefore, solve a (simpler) linear problem. be a nonlinear mapping from the obrvation space Let to a higher (possibly infinite) dimensional feature space . be a clod planar parametric curve. Let divides the image domain into two regions: the interior of designated by , and its exterior . Solving the problem of gmentation in the kernel-induced space with curve evolution consists of evolving in order to minimize a functional corresponding to the mapped data. The functional , measures a kernel-induced non Euclidean we minimize, distance between the obrvations and the regions parameters and [e (7), shown at the bottom of the page]. In machine learning, the kernel trick [30], [31] consists of using a linear classifier to solve a nonlinear problem by mapping the original nonlinear data into a higher dimensional space. Following the Mercer’s theorem [30], which states that any contin-
(9) , which depends both on and on the reTo minimize gions parameters and , we adopt an iterative two-step algorithm. The first step consists of fixing the curve and optimizing with respect to the parameters. As the regularization term does not depend on regions parameters, this is equivalent to
op. The cond step contimizing the data term, referred to as sists of evolving the curve with the parameters fixed. 1) Step 1: For a fixed partition of the image domain, the with respect to , yield the folderivatives of lowing equations:
(10) Table I lists some common kernel functions. In all our experiments we ud the radial basis function (RBF) kernel, a kernel which has been prevalent in pattern data clustering [28], [42], [43]. With an RBF kernel, the necessary conditions for a minwith respect to region parameters are imum of (11)
(7)
SALAH et al.: EFFECTIVE LEVEL SET IMAGE SEGMENTATION WITH A KERNEL INDUCED DATA TERM
2012年12月四级223
TABLE I EXAMPLES OF PREVALENT KERNEL FUNCTIONS
where
江南逢李龟年翻译Fig. 2. Reprentation of a 4-region partition.
(12) The solution of (11) can be obtained by fixed point iterations. This consists of iterating (13) , quence converges. A detailed For proof is given in Appendix A. Let be its limit. Thus, is a fixed point of function and, conquently, is a solution of (11). The update of the region parameters obtained in (13) is a mean-shift update. Mean-shift corrections have traditionally appeared in data clustering and have been quite efficient [36], [37]. It is a mode arch procedure which eks the stationary points of the data distribution. It is quite interesting that a mean-shift correction appears in this context of active curve gmentation. This correction occurs in the minimization with respect to the region parameters due to the kernel induced data term, via the RBF kernel. The effectiveness and flexibility of this kernel formulation and the ensuing mean-shift update will be confirmed by an extensive experimentation in Section IV. 2) Step 2: With the region parameters fixed, this step conwith respect to . The Euler-Lagrange sists of minimizing descent equation corresponding to is derived by embedding the curve into a family of one-parameter curves and solving the following partial differential equation: (14)bless是什么意思
limi
where is the mean curvature function of . The final evolution equation for a two-region gmentation in the kernel-induced space is (17) In the ca of an RBF kernel, the expression (9) of simplifies to , , 2. B. Level Set Implementation To implement the curve evolution in (17), we u the wellis implickno
wn level t method [38]. The evolving curve itly reprented by the zero level t of a function at time , i.e., . This reprentation is numerically stable and handles automatically topological changes of the evolving curve. is evolving following [38]: When the curve (18) , the corresponding level t function where evolves according to (19) Using this result, the level t function evolution corresponding to (17) is given by
(20) where the curvature function is given by
is the functional derivative of with respect where and are obtained from curve to . Segmentation regions at convergence, i.e., when time . Using the result in [12] which shows that, for a scalar function , the functional derivative with respect to the curve of is equal to , where is the outward unit normal to , we have
(15) The derivative of the length prior with respect to is [12]
(21) It should be mentioned that (20) applies only for points on the curve . We extend this evolution equation to the whole image domain [35]. The function evolves also for points outside its zero level according to (20) without affecting the process of gmentation and, us such, is more stable numerically. More details on the level t partial differential equation discretization schemes and fast
介绍一本书的作文resolution algorithms are available in [38]. C. Multiregion Segmentation
(16)
Multiregion gmentation using veral active curves can lead to ambiguity when two or more curves interct. The
224
IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 19, NO. 1, JANUARY 2010
满分Fig. 3. Image intensity distributions: (a) small overlap; (b) significant overlap.
main issue is to guarantee that the curves converge to define a partition of the image domain. There are veral ways of generalizing a two-region gmentation functional to a multiregion functional to guarantee such a partition. For instance, the generalization is done [3] via a term in the functional which draws the solution toward a partition, an explicit correspondence between the regions of gmentation and the interior of curves and their interctions in [8] and [35], and a partition constraint to u directly in the equations of minimization of the functional in [2]. The and other methods are reviewed in [35]. Here, we u the implementation of our generalization described in [3
5] and ud in other applications [21], [22]. This generalization is bad on the following definition of a partition. For a gmentation into regions, let be simple clod plane curves and the regions they enclo. Then, the following regions form a partition: and , is the complementary of in . This is illustrated where in Fig. 2 for four regions. The curve evolution equations and the corresponding level-t equations, using this definition of a partition, are given in Appendix B. IV. EXPERIMENTAL RESULTS To illustrate the effectiveness of the propod method, we first give a quantitative and comparative performance evaluation over a large number of experiments on synthetic images with various noi models and contrast parameters. The percentage of misclassified pixels (PMP) was ud as a measure of gmentation accuracy. To illustrate the flexibility of the method, we also show a reprentative sample of the tests with various class of real images including natural images from the Berkeley databa, medical and satellite data, as well as motion maps. A. Quantitative and Comparative Performance Evaluation The piecewi constant gmentation method and the piecewi Gaussian generalization have been the focus of most studies and applications [6], [9] becau of their tractability. In the following, evaluation of the propod method, referred to as Kernelized Method (KM), is systematically supported by comparisons with the Piecewi Gaussian Method (PGM) [3], [19], [20]. The PGM method us a Gaussian model in the data
Fig. 4. Segmentation of two exponentially noisy images with different contrasts: (a), (b) noisy images with different contrasts; (a ) (b ) gmentation results with PGM; (a ) (b ) gmentation results with KM. Image size: 128 128. = 1.
fireflies2
0
0
term of (5). In all our experiments, the KM method us the RBF kernel (refer to Table I) with the same parameter . We first show two typical examples of our extensive testing with synthetic images and define the measures we ud for performance analysis: the contrast and the percentage of misclassified pixels (PMP). Fig. 4(a) and (b) depicts two versions of a two-region synthetic image, each perturbed with an exponential noi. Different noi parameters result in different amounts of overlap between the intensity distributions within the regions (Fig. 3). The larger the overlap, the more difficult the gmentation [4]. depict the gmentation results with the Figs. 4 PGM. Becau the actual noi model is exponential, gmentation quality obtained with the PGM was significantly affected . However, the KM yielded with the cond image in Fig. 4 ), approximately the same result
for both images (Fig. 4 although the cond image undergoes a relatively significant
