Statistical Density Estimation Using Threshold Dynamics for Geometric Motion

The idea to use binary segmentation techniques for density estimates arises from the need to quickly and accurately locate the regions of higher activity, as well as to calculate the local density. Instead of obtaining a complete density function estimate, such as seen in [22] and [28], our goal is to segment only one region at a time. Maximum penalized likelihood estimation models have become standard for estimating a probability density function d(x) based on point data x ₁,x ₂,…,x _N ∈ℝ ⁿ , and they take a form where R(d) is a penalty function. A wide variety of different penalty functions are proposed in the literature, and many of them are designed to impose additional smoothness on the density function. Single variable density estimation with a non-smooth density function is discussed in [27] and [18] where the authors of both works introduced the TV semi-norm as a penalty function. In their work [22], Mohler et al. construct the first two dimensional TV norm based MPLE: The authors also create an efficient computational method for minimization of (2) based on the Split Bregman algorithm [15]. Smith et al. in [28] propose a modification of the model (2), as well as the model that uses the H ¹ norm as a penalty function, and they successfully integrated geographic information of the observed region to get a more accurate density estimate. The authors use city maps, census data as well as other types of geographical data to determine the region where the events typically occur, the valid region D. Knowing that the density function is zero anywhere outside the valid region, the authors align the zero level sets of the valid region and the density function. In their modified MPLE model aligning is achieved through addition of the alignment term, and the model they propose is where 1 _D is a characteristic function of the valid region. In the case of the weighted H ¹ MPLE model, in order to allow the density function d to have sharp jumps on the border of the valid region, the H ¹ penalty functional was forced away from the boundary of the valid region. Thus, the proposed model becomes: where z _ϵ is a continuous function such that In this work we propose the variational MPLE segmentation model using the Ginzburg-Landau functional as a regularizer to segment the geography and calculate the density function: where w is a function that represents the given data, u is a segmentation function, and d(u) is a two phase density function that can be determined from u. We define w as a sum of Dirac δ functions \(w=\sum_{i}^{N}\delta(\mathbf{x}_{i})\), where x _i are data points. This function is introduced for the purpose of more compact notation. Note that in Eq. (5) the maximum likelihood term ∫wlog(d(u))dx involves the data function w, while in Eqs. (4), (3), (2) and (1) we used the sum \(\sum_{i=1}^{N} \log(d(\mathbf {x}_{i}))\). The dense region Σ is located via segmentation function u, i.e. u=χ _Σ . Using the information on the data set we obtain through function w, as well as the assumption that density d(u) is piecewise constant, we calculate the values of d(u) in Σ and Σ ^C .

This paper is organized as follows, in Sect. 2 we give some background on variational methods for image segmentation, in Sect. 3 we describe the MBO scheme, in Sect. 4 we present some background on MPLE models. In Sect. 5 we discuss the proposed model in more details, and calculate the time dependent Euler-Lagrange equation to minimize the functional (5). Section 6 explains the thresholding dynamics for minimization of our energy functional. Details on the numerical implementation are presented in Sect. 7.

Variational segmentation models are widely successful in image processing. In their pioneering work [23], Mumford and Shah propose the following segmentation model: where f is an image that should be segmented, and u is a segmentation function. One of the major results in image segmentation is Chan-Vese algorithm presented in [5], where authors, inspired by the level set method by Osher and Sethian [24], propose a method for minimizing the piecewise constant version of (6): where Σ is a segmented region. The level set version of (7) proposed in [5] is obtained by the boundary of Σ being represented as a 0-level set of the function ϕ(x):D→R. After the optimal values for constants c ₁ and c ₂ are determined, the time-dependent Euler-Lagrange equation for ϕ is found: where H _ϵ is an approximation of the Heaviside function, and a semi-implicit numerical scheme is created to solve (9). Due to the computational complexity of the numerical algorithm that solves Eq. (9), Gibou and Fedkiw created algorithms that do not explicitly solve (9). In their work [16], they designed the hybrid k-means level set method and applied it to images that were previously processed using the Perona-Malik diffusion. Another algorithm that successfully minimizes the piecewise constant Mumford-Shah functional without solving the gradient descent equation (9) is proposed in [30]. Numerous modifications of the piecewise constant Mumford-Shah model, and different ways to minimize it appeared in the literature (see [2, 4, 6, 9, 14, 17] and [29]).

The regularization based on the Total Variation semi-norm (TV) is widely used and established as a standard procedure in numerous image processing applications. It has been proven in [19] that the Ginzburg-Landau functional converges to the TV semi-norm in the sense of Γ-convergence. This property justifies the substitution of the TV norm for the Ginzburg-Landau functional. The reason one might prefer the GL functional over the TV semi-norm is the simplicity of the minimization numerical scheme that the GL functional yields. Indeed, the L ² gradient descent of the GL functional gives us the Allen-Cahn equation as opposed to having a nonlinear curvature term obtained through minimization of the TV semi-norm, although the Split Bregman technique [15] successfully resolves that issue. Models with the GL functional are typically referred to as diffuse interface models, because the double well potential causes the minimizer of the functional to have two phases with a diffuse interface between them. The diffuse interface scale is O(ϵ). The Ginzburg-Landau functional has appeared in many image processing applications, such as inpainting [3, 7] and segmentation [9, 10].

In the case of motion by mean curvature a planar curve moves with a normal velocity that is proportional to the curvature at any given point. In their work [20], Merriman, Bence and Osher introduced an intuitive and efficient level set method to approximate the motion of an interface by its mean curvature flow. The authors analyzed the motion by mean curvature of the curve C by studying the diffusion equation χ _t =Δχ, where χ is the characteristic function of the set Σ and ∂Σ=C, i.e. C represents a sharp front between two phases of the characteristic function. The appropriate change of coordinates suggested in [20] reveals that, when diffusion is applied, any point on the front moves with the normal velocity that is equal to the mean curvature at that point. Simultaneously, the front is radially blurred. However, the \(\chi=\frac{1}{2}\) level set is invariant to blurring. From there it follows that, the \(\chi=\frac{1}{2}\) level set yields motion by mean curvature. Based on the previous observation the following numerical scheme is proposed:

The reason we are interested in motion by mean curvature flow is due to is its close relation to the Allen-Cahn equation (10).

It was shown in [25] that limit of the rescaled solutions \(u_{\epsilon}(x,\frac{t}{\epsilon}), \epsilon\to0^{+}\) of the Allen-Cahn equation yields motion by mean curvature. The modification of the MBO scheme proposed in [9] by Esedoglu and Tsai particularly interesting. In their paper [9], the authors proposed a diffuse interface version of (7) for segmenting the image f. The first variation of the model (11) yields the following gradient descent equation: and the adaptation of the MBO scheme was used to solve it. Similarly to the MBO scheme where the propagation step based on the heat equation is combined with thresholding, Esedoglu and Tsai proposed the following scheme: Based on the computational experiments, the authors presented their conclusions about the choice of δt timestep in the step \(\mathbf{1.}\) of the algorithm. If δt is chosen too large comparing to the parameter λ ⁻¹, the interface tend to be overly smooth. As the advantage of choosing larger values for δt they mention faster convergence. The segmentation could also benefit from the larger values for the parameter λ, as there is less penalty on high curvature of the interface in this case. The size of the spatial resolution has to be taken into account when the value for δt is chosen, as the values much smaller than the spatial resolution could lead to the stillness of interface. These observations can also be used as guidance in parameter selection for our algorithm. The authors also show that MBO thresholding type methods for binary segmentation can easily be generalized to multi-phase segmentation methods. To accomplish that, the authors propose the four phase model based on the modified version of (11) with the sum of the two Ginzburg-Landau functionals built around two different segmentation functions, u ₁ and u ₂. In this case, the fidelity term naturally depends on both u ₁ and u ₂. After they find the gradient descent equations with respect to u ₁ and u ₂, they construct the thresholding numerical scheme to solve the obtained system of parabolic equations. We will adapt ideas by Esedoglu and Tsai to solve our MPLE problem and illustrate the usefulness of this simple method.Some extension of the MBO algorithms appeared in [11, 12, 21] An efficient algorithm for motion by mean curvature using adaptive grids was proposed in [26].

Let us assume our data consists of n points x ₁,x ₂,…,x _n and is a sample of n independent random variables with common density d ₀. Maximum likelihood estimation is a standard method for estimating a density function d ₀ based on given data. In the case the of the parametric model, we know that d ₀ belongs to the family of density functions D={d(⋅,θ):θ∈Θ}, and our goal is to find a parameter θ ₀ such that d(⋅,θ ₀)=d ₀(⋅). This class of problems are known as parametric density estimates. In 1922, According to Fisher’s model [13], an optimal parameter θ ₀∈Θ (where Θ is a set of all parameters) satisfies the following: However, in many applications, a parametric model may not be available, or information on the family of density functions d ₀ belongs to may be unknown, in which case we are dealing with a nonparametric density estimate. The analog of the model (13) is an ill-posed problem, i.e. finding a probability density function d ₀ such that has no solution, and thus can not be directly applied. To avoid “rough” density functions, with large values concentrated around data points and small values elsewhere, the roughness penalization function R(d) was introduced, and this method is known as maximum penalized likelihood estimation: Different penalty functionals appeared in literature, such as \(R(d)=\int_{\varOmega}|\nabla\sqrt{d}|^{2}\), or R(d)=∫ _Ω |∇³logd|² from [8]. These, and many other standard penalty functional enforce smoothness on density function, but do not perform well when the density function has sharp gradients, i.e. is piecewise constant. To resolve this issue, Koenker and Mizera in [18] as well as Sardy and Tseng in [27] propose the penalty functional to be the TV semi-norm. This approach was also successfully used in [28] and [22]. In our work, since we assume the density is a step function, choosing a penalty functional that can successfully handle sharp gradients is crucial. As previously mentioned , instead of the TV semi-norm, we chose the Ginzburg-Landau functional to be the penalty functional.

We use the following gradient descent equation with A(u(⋅,t)) and B(u(⋅,t)) being non-linear functions. Each of the gradient descent equations, (17), (18), (19) and (22) can be given in the form (23), where A(u(⋅,t)) and B(u(⋅,t)) take different vales in different cases. Motivated by the MBO scheme for solving the Allen-Cahn equation, we propose a thresholding scheme to approximate the solution of Eq. (23). Esedoglu and Tsai used a similar approach to minimize the Mumford-Shah segmentation functional in [9]. The first step we need to take toward generating a thresholding scheme is finding a good way to split Eq. (23) into two steps analogous to those proposed in the MBO scheme. In that regard, finding a way that successfully deals with the non-linear forcing term of Eq. (23) is critical. Inspired by the algorithm presented in [9] we propose the following dynamics:

In the propagation phase of the algorithm we solve the following PDE: with the u _n being an initial condition. To generate the numerical results we denote the timestep by δτ is a timestep, and approximate the Laplacian by its five-point stencil, which gives us the following scheme: As the linear system described above is circulant we find the Fast Fourier transform (FFT) a convenient way solve it. We are aware that other solvers with even better computational complexity than the FFT, such as multigrid algorithm, could be used. In the propagation phase our goal is not to achieve steady state, and iterations are repeated only until the total propagation time reached δt. After the propagation phase, a thresholding step is necessary to complete the iteration: where l is a total number of iterations we made in the propagation phase. The small relative change of the L ² norm between two consecutive iterations was used as a stopping criterion.

The choice of the smoothing parameter μ and the timestep can affect the performance of this algorithm. Our experiments show that in case we are segmenting the high density region the optimal value of the parameter μ is not larger than 0.2. When our goal is to estimate the valid region, we typically assign larger values to the parameter μ. To estimate the value of the smoothing parameter we implemented a version of the V-fold cross validation algorithm. In their work [27] Sardy and Tseng proposed the V-fold cross validation based on the Kullback-Leibler information. In the V-fold cross validation, the original data set is partitioned into V disjoint subsets x _v ={x _i ,i∈S _v } where S _v consists of all indexes of data points from the partition v=1,…,V. Set x _−v ={x _i ,i∉S _v } is used as a training set, i.e. the algorithm is applied on x _−v with some particular value \(\hat{\mu}\), and the density \(\hat{d}_{\hat{\mu},-v}\) is estimated. Set x _v is a validating set, which means that \(\{ \hat{d}_{\hat{\mu},-v}(x_{i})\}_{i\in S_{v}}\) is used to estimate the density on x _v . Following these observations, the authors of [27] proposed the following estimate of Kullback-Leibler information \(CV(\hat{\mu})=-\sum_{v=1}^{V}\sum_{i\in S_{v}}\hat{d}_{\hat{\mu },-v}(x_{i})\), and after the search of the set of parameters \(\hat{\mu}\) the one that minimizes this quantity is selected. However, \(CV(\hat{\mu})\) uses only the log-likelihood to predict the performance of the model for some value \(\hat{\mu}\) of the smoothing parameter, but does not take the H ¹ norm of the segmentation function of the estimated density into account. We denote the segmentation function that corresponds to the density \(\hat{d}_{\hat{\mu},-v}\) by \(\hat{u}_{\hat{\mu},-v}\). Since the segmentation function is a binary function, the discrete H ¹ and the discrete TV norm are equivalent, thus the H ¹ norm also measures the length of the front between two phases. In some applications, such as the case when the dense and the surrounding sparse region have similar densities, the values of CV(μ) for the different values of μ tend to be similar. It is useful in those cases to also measure the H ¹ norm of the obtained segmentation \(\hat{u}_{\hat{\mu},-v}\), and incorporate that information in the V-fold cross validation. Because of that, we propose a slightly different technique, where we evaluate \(CV_{H^{1}}(\hat{\mu}) =-\sum_{v=1}^{V}(\sum_{i\in S_{v}}\hat{d}_{\hat{\mu},-v}(x_{i})-\xi\int{|\nabla\hat{u}_{\hat{\mu },-v}|^{2}})\) for each value of \(\hat{\mu}\) from some proposed set of parameters, and select the value that minimizes it. The results do not appear to be very sensitive to ξ, we used small values, comparable to those of \(\hat{\mu}\). The evaluation of \(CV_{H^{1}}(\mu)\) for a single value of parameter μ requires V different density estimates, which could cause the V-fold cross validation to be very computationally intense. However, all density estimates that have to be performed are independent of each other, which makes the V-fold cross validation a perfect candidate for parallelization. In this implementation, we used 10-fold cross validation, and the process of calculating \(CV_{H^{1}}\) is parallelized using 10 threads, which reduces the computational time of one evaluation of \(CV_{H^{1}}\) down to the computational time needed for one density estimate. The computational time one density estimate takes varies from 0.2 s in the small scale examples (100×100 pixels) to around one minute in the large scale examples (600×1000 pixels). To demonstrate the performance of the proposed algorithm, Figs. 13 and 14 show some computational examples with segmentations generated using a model with the smoothing parameter obtained through 10-fold cross validation. To find the parameter μ we performed the linear search of intervals.

This work demonstrates that threshold dynamics methods for image segmentation are a powerful tool for statistical density estimation for problems involving two dimensional geographic information. The efficiency of the method, especially when combined with multi-resolution techniques makes this a practical choice for parameter estimation involving V-fold cross validation, especially when parallel platforms are available. The method is a binary segmentation method that also determines density values. However, it can be naturally generalized to multi-level segmentation. One way to achieve that may include representing the segmentation function as a linear combination of the multiple binary components, similarly to the idea used for generalizing binary to grayscale inpainting in [7]. However, this requires sufficient data to warrant a multi-level segmentation.