Abstract
Image segmentation with depth information can be modeled as a minimization problem with Nitzberg–Mumford–Shiota functional, which can be transformed into a tractable variational level set formulation. However, such formulation leads to a series of complicated high-order nonlinear partial differential equations which are difficult to solve efficiently. In this paper, we first propose an equivalently reduced variational level set formulation without using curvatures by taking level set functions as signed distance functions. Then, an alternating direction method of multipliers (ADMM) based on this simplified variational level set formulation is designed by introducing some auxiliary variables, Lagrange multipliers via using alternating optimization strategy. With the proposed ADMM method, the minimization problem for this simplified variational level set formulation is transformed into a series of sub-problems, which can be solved easily via using the Gauss–Seidel iterations, fast Fourier transform and soft thresholding formulas. The level set functions are treated as signed distance functions during computation process via implementing a simple algebraic projection method, which avoids the traditional re-initialization process for conventional variational level set methods. Extensive experiments have been conducted on both synthetic and real images, which validate the proposed approach, and show advantages of the proposed ADMM projection over algorithms based on traditional gradient descent method in terms of computational efficiency.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The segmentation with depth information is a 2.1D sketch problem [1,2,3] in computer vision. Its goal is to reconstruct the complete shapes of occluded objects and their ordering relation in a specific scene based on only one single image via using segmentation techniques. Such segmentation plays an important role in image analysis and computer vision, such as object recognition and tracking. It is also a fundamental preprocessing step to some more complicated problems such as illusory shape recovery [4, 5].
In early 1990s, Nitzberg et al. [6] innovatively modeled the segmentation with depth as a minimization problem for an energy functional, which is called the NMS model. This model combines the classical Mumford–Shah model [7] for variational image segmentation and Euler’s elastica terms [8]. In order to optimize the NMS model in a tractable manner, authors in [6] have decomposed such problem into three successive steps: finding the edges and T-junctions in the image; hypothesizing the ordering relation of objects to be segmented and obtaining the associated minimum of energy functional; determining the objects’ ordering and the reconstructed shapes according to the minimum functional in the second step. This NMS model is a foundation for this type of segmentation problems associated with depth information, and many possible solutions have been proposed based on this model as described below.
Instead of the tedious multiple step procedure aforementioned, Esedoglu and March [9] transformed the original NMS model into an equivalent one based on \(\Gamma \)-convergence concept [10, 11] and its aim is to approximate the terms associated with length and elastica. Such derived model was claimed and demonstrated to be more tractable without requirement of T-junctions detection. For the computational efficiency, they designed a fast scheme by combing the semi-implicit discretization and fast Fourier transform (FFT) methods. But due to the over simplification of curvature-related terms in quadratic form, their model cannot preserve the corners of the recovered shapes, as they pointed out in [9].
Another rigorous approximation for the NMS model is based on variational level set method [13,14,15,16], which was proposed by Zhu et al. [12]. By making use of the standard variational method, they have derived a series of higher-order evolution equations including level set functions and then proposed the Smereka’s semi-implicit method [17] with FFT solver. However, it is difficult to discretize the fourth-order nonlinear partial differential equations (PDEs) in their approach. Additionally, they did not consider the definition of level set functions as signed distance functions during computation process as did in [12].
Recently, another similar work was conducted by Zhu et al. [18], where they proposed the Chan–Vese–Euler model by combining the Chan–Vese model and Euler elastica regularizer with an aim to recover the missed parts of contours. In order to minimize the proposed model efficiently, they designed a fast alternating direction method of multipliers (ADMM) [19, 20]. Although this model can integrate the missing parts to form a complete meaningful object, it was designed only for one foreground shape recovery problem without considering segmentation with depth information. Moreover, their work was based on binary label function method [22] or piecewise constant level set function method [21].
The curvature-related terms play crucial roles in the NMS model, but they also brought computational complexity due to the nonlinear higher-order derivatives. This issue also appears in other variational models of imaging sciences on the non-texture image inpainting [23, 24], illusory contours reconstruction [4, 5], image denoising [25,26,27,28] with feature (edge, corner, smoothness, contrast, etc.) preserving. In order to improve the computational efficiency and avoid solving nonlinear higher-order PDEs, some fast ADMM methods are systematically investigated in [27,28,29,30] for energy minimization problems associated with curvature terms.
Motivated by works in [27,28,29,30], in this paper, we focus on developing a fast ADMM method for optimizing the NMS model [6], which can be rewritten as a variational level set formulation [12]. The main difference between the variational level set formulation and the models in [23,24,25,26,27,28,29,30] is that the variational level set formulation in this paper is constrained by some nonlinear Eikonal equations of level set functions based on definition of signed distance functions. Usually, these constrained equations are guaranteed to be satisfied by solving a dynamic Hamilton–Jacobi equation using the upwind finite difference scheme [31], fast sweeping method [32], or they can be coped with penalty function method [33, 34] to get rid of these constraints.
The ADMM-projection (ADMM-P is used for abbreviation in the following parts of this paper) method proposed in this paper is based on the simplified variational level set formulation by replacing curvatures with Laplacians of level set functions on the premise that the Eikonal equations are satisfied during computation process. Another salient feature of this method is that the Eikonal equations can be satisfied indirectly by means of introducing auxiliary variables and implementing a direct projection [35, 36], which are suitable for the simplified variational level set formulation.
The paper is organized as follows: in Sect. 2, the variational level set formulation of the NMS functional along with its traditional gradient descent method (GDM is used for abbreviation in the follows) is reviewed; in Sect. 3, we derive the simplified variational level set formulation as an equivalent one of the NMS, and then design a fast ADMM-P method for the simplified variational level set formulation by transforming it into some sub-minimization problems for efficient computation in Sect. 4; in Sect. 5, extensive numerical experiments on different type images are conducted to illustrate the efficiency of the proposed model and its ADMM-P method. Concluding remarks are presented in Sect. 6.
2 The Variational Level Set Formulation for the NMS Model and its GDM Method
In this section, we will review the variational level set formulation of the NMS model first and then highlight our contributions clearly in Sects. 3 and 4. In [6], Nitzberg et al. defined the problem of segmentation with depth information as a problem of recovering occluded shapes and their ordering relations based on a 2D image. This problem is investigated with the following three assumptions: (1) there is no self-occlusion on the surface of each object; (2) the objects are not entangled with each other; (3) the pixel intensities of each object are approximately constant and different from each other. The variables defined in this problem are in three folds: the shapes of the regions \(R_1 ,R_2 ,\ldots ,R_n \) to which different objects belong; the ordering relations among objects; the pixel intensities of objects.
Without loss of generality, one can assume that the objects \(R_1 ,R_2 ,\ldots ,R_n \) in an image are in ascending order, i. e., \(R_1 \) is the nearest object to the observer while \(R_n \) is the farthest one (i. e. background). Let \(R^{\prime }_i \) be defined as the visible part of \(R_i \), i.e., \(R^{\prime }_1 =R_1 ,R^{\prime }_i =R_i -\bigcup \limits _{j<i} {R_j } ,\left( {i=2,\ldots ,n} \right) \). In addition, \(R^{\prime }_{n+1} =\Omega -\bigcup \limits _{j<n+1} {R_j } \) is defined as the visible background. Based on the above assumptions and definitions, the NMS functional is formulated as in [6]
where \(\alpha ,\beta \) are two positive penalty parameters, s is arc length, and \(c_i \in R_i \) are pixel intensities of the ith object, \(\kappa \) denotes the curvature of boundary for region \(R_i \). While one of the main difficulties in minimizing the above NMS functional is to calculate the energy term.
By making use of variational method [13,14,15] and level set method [16], Zhu and Chan proposed the variational level set formulation in [12] to replace the original NMS model. For such purpose, a level set function representing an interface \(\Gamma (t)\) (t represents time) is defined implicitly as the zero level set of a Lipchitz continuous function \(\varphi :R^{2}\rightarrow R\), which in turn can be defined in terms of time t as the following signed distance function for efficient computation,
where \(d({\Gamma (t),x})\) denotes the shortest Euclidean distance from x to \(\Gamma (t)\), and from which its Eikonal equation is derived as \(\left| {\nabla \varphi ({x,t})} \right| =1\).
For an image defined in domain \(\Omega \) with boundary \(\Gamma (t)\), according to the co-area and area formulas in [31], we will have
where \(H({\varphi (x)})\) and \(\delta ({\varphi (x)})\) are Heaviside function and Dirac delta function, respectively, with the definitions given below.
In fact, these kinds of original definitions are difficult to calculate as there exist non-differential functions. In practice, these two functions are often approximated via introducing a small positive parameter \(\varepsilon \) in (5) and (6) [10, 11] by denoting as \(H_\varepsilon ({\varphi (x)})\) and \(\delta _\varepsilon ({\varphi (x)})\). In this way, we can obtain some feasible computing forms of Heaviside function and Dirac delta function in [13,14,15,16], given by
By making use of these level set functions \(\varphi _i ( i=1,2,\ldots ,n )\), we can represent objects \(R_i \) as \(R_i =\{ x: H({\varphi _i (x)})=1 \}\), each visible part as \(R^{\prime }_i =R_i -\mathop {\bigcup }\limits _{j<i} R_j \) which is given by \(R_i^{\prime } =\{ {x:H({\varphi _i } )\prod \limits _{j=1}^{i-1} {( {1-H( {\varphi _j } )} )} =1} \}\), thus the term \(\sum \limits _{i=1}^{n+1} {\int _{R^{{\prime }}_i } {( {f(x)-c_i } )} ^{2}\mathrm{d}x} \) in (1) can be rewritten as
And more importantly, the curvature \(\kappa _i \) can be represented as \(\kappa _i =\nabla \cdot ( {\frac{\nabla \varphi _i}{|{\nabla \varphi _i } |}} )\). Now we choose \(\phi (\kappa )=|\kappa |\) as the authors of [12] did with the reason that the NMS model (1) can preserve the object corners when \(|\kappa |\) becomes large. Thus, the NMS functional (1) can be reformulated with level set functions as below and our major task is to solve the level set functions \(\varphi _i \)
Now, by using the standard variational method, one can obtain the following GDM equations of level set functions via minimization of functional (10).
where \(i=1,2,\ldots ,n\) denotes the number of objects in the image, and \(H({\varphi _{n+1} })=1\) is introduced only for consistency of description. In fact, (11) is a standard Hamilton–Jacobi equation, which can be solved iteratively using some explicit upwind-alike schemes. However, the convergence of such iteration heavily depends on selected time step size. In order to overcome this problem and improve the computational stability, the authors in [12] employed the Smereka’s semi-implicit iteration method [17] to relax the Courant–Friedrichs–Lewy condition. In order to improve the computational efficiency further, they employed the FFT method to solve the discretized equations. But discretization of the nonlinear fourth-order derivatives is tedious and is prone to errors. More seriously, they did not pay attention to the requirement of level set functions as the signed distance functions during computational iteration. In order to overcome these computational problems, we will propose a new ADMM projection approach in this paper.
3 ADMM-P Method for Simplified Variational Level Set Formulation
Instead of solving (10) directly by using the conventional variational method and solving the related GDM equations as mentioned in previous section, in this section, we first transform the original minimization problem into several sub-optimization problems by introducing some auxiliary variables and then solve them using the alternating directional optimization strategy.
First, we propose a simplified model of the original problem by considering the property of level set functions as the signed distance functions. If the level set functions are treated as the signed distance functions during computational process with property \(| {\nabla \varphi _i } |=1(i=1, 2,{\ldots }n)\), the curvatures in (10) can be replaced by Laplacians of level set functions, and in this case \(\kappa _i =\nabla \cdot ( {\frac{\nabla \varphi _i }{| {\nabla \varphi _i } |}} )=\nabla \cdot ( {\nabla \varphi _i } )=\Delta \varphi _i \) can be reduced to \(\kappa _i =\nabla \cdot ( {\nabla \varphi _i } )\). Based on this observation, the NMS functional (10) can be rewritten as the following simplified version
Note that Eqs. (12a) and (12b) are equivalent to the original problem (15). Therefore, some fast ADMM algorithms can be directly applied to (12a) and (12b). For such purpose, some auxiliary variables \(\vec {w}_i =[ {w_{i1} ,w_{i2} } ]^{T}\) and \(v_i \) with property \(\vec {w}_i \approx \nabla \varphi _i , v_i \approx \nabla \cdot \vec {w}_i \) and the Lagrangian multipliers \(\vec {\lambda }_{1i} ,\lambda _{2i} \) are introduced. In this case, the constraint \(| {\nabla \varphi _i } |=1\) will be replaced by \(| {\vec {w}_i } |=1\), and this substitution can avoid the traditional re-initialization process to satisfy \(| {\nabla \varphi _i } |=1\) by imposing the compulsory constraint for \(\vec {w}_i \). And \(| {\vec {w}_i } |=1\) then can be guaranteed by implementing a projection method easily. Based this observation, we can transform (12a) and (12b) into the following augmented Lagrangian functional with some explicit constraints.
where \(\mu _1 ,\mu _2 \) are positive penalty parameters, and \(c=\left\{ {{\begin{array}{l} {c_1 }\quad {c_2 }\quad \ldots \quad {c_{n+1} } \\ \end{array} }} \right\} , \varphi =\left\{ {{\begin{array}{l} {\varphi _1 }\quad {\varphi _2 }\quad \ldots \quad {\varphi _n } \\ \end{array} }} \right\} ,\vec {w}=\left\{ {{\begin{array}{l} {\vec {w}_1 }\quad {\vec {w}_2 }\quad \ldots \quad {\vec {w}_n } \\ \end{array} }} \right\} , v=\left\{ {{\begin{array}{l} {v_1 }\quad {v_2 }\quad \ldots \quad {v_n } \\ \end{array} }} \right\} , \vec {\lambda }_1 =\left\{ {\vec {\lambda }_{11} \hbox { }\vec {\lambda }_{12} \ldots \vec {\lambda }_{1n} } \right\} , \lambda _2 =\left\{ {\lambda _{21} \hbox { }\lambda _{22} \ldots \lambda _{2n} } \right\} \). The approximations for \(\vec {w}_i \approx \nabla \varphi _i \) and \(v_i \approx \nabla \cdot \vec {w}_i \) can be achieved by the maximization with respect to \(\vec {\lambda }_{1i} \) and \(\lambda _{2i} \) in the energy functional (13.1). Meanwhile, the constraint \(| {\nabla \varphi _i } |=1\) is replaced by \(| {\vec {w}_i } |=1\), which can be guaranteed by the projection method directly. It is noteworthy that this constraint can also be guaranteed via penalty function method, in which larger computational expense would be inevitable. Next we will propose a new approach to solve this problem.
The proposed ADMM-P method can be implemented in finite steps with stopping criteria. In each step, we can calculate a sub-problem. Also, the sub-problem of minimization is carried out with respect to one variable while keeping other variables to be fixed temporarily. For the formulations (13a) and (13b), we first initialize the unknown values \(c^{0},\varphi ^{0},\vec {w}^{0},v^{0},\vec {\lambda }_1^0 ,\lambda _2^0 \), and then, we start a procedure of optimization step by step. In each step, the minimization of (13a) and (13b) can be divided into following sub-problems
where (18) and (19) are responsible for updating of the Lagrange multipliers. These functionals of the above mentioned sub-problems are given, respectively, below.
In summary, we can present the ADMM-P approach in a pseudo-code format as follows.
Whether the above proposed ADMM method can be suitably applied for solving the non-convex and non-smooth problems in computer vision has attracted extensive attention. The authors in [39, 40] discussed this issue in detail and provided many applications in which many similar algorithms have been developed and successfully used to achieve excellent performances via solving a variety of non-convex problems. In addition, many other authors [18, 19, 26, 27, 29, 30] also have made a success of applying the ADMM method to different problems. In this paper, we adopt a similar research route to design a new algorithm to deal with the non-convex and non-smooth problem for the segmentation problem with depth.
Next we will consider each sub-problem in above algorithm individually.
4 Minimization of Each Sub-problem
4.1 Estimation of the Piecewise Constant Parameters
In the \(({k+1})\) step of the proposed ADMM, the average image intensity values \(c_i \) in different regions can be obtained by using the standard variational method based on (14) and (20), which are given by
4.2 Calculation of the Level Set Functions
For the minimization sub-problems (15) and (21) with respect to the level set functions \(\varphi _i \), the corresponding Euler–Lagrange equations are given by
where \(\vec {w}_i^k ,\vec {v}_i^k \) are fixed temporarily when \(\varphi _i^{k+1}\) is calculated by using the semi-implicit difference scheme and Gauss–Seidel iterative method. To be more specific, the Gauss–Seidel iterative method can be used for the linear terms of (25a) \(\nabla \cdot \vec {\lambda }_{1i}^k +\mu _1 \nabla \cdot ( {\vec {w}_i^k -\nabla \varphi _i } )\), while the nonlinear terms:
need to be calculated by an explicit difference scheme. According to the standard technique introduced by Zhao and Chan [13], we use \(| {\nabla \varphi _i } |\) to replace \(\delta ( {\varphi _i } )\), which facilitates accelerating the evolution process [37], and then directly utilize \(|{\nabla \varphi _i }|=1\). The final calculation result of \(\varphi _i \) is shown as follows
where \(m=1,2,\ldots ,M, l=1,2,\ldots ,N\) and \(M\times N\) denotes the size of the image.
4.3 Minimization of the Auxiliary Variable \(\vec {w}_i \)
The Euler–Lagrange equations with respect to \(\vec {w}_i \) can be derived from (16) and (22) via calculus of variation when the variables \(\varphi _i^{k+1} ,\vec {v}_i^k \) are kept constant temporarily,
The first equation of (26) can be solved by using the fast Fourier transform (FFT) [30]. We now detail the FFT implementation as follows
For clarity, we introduce \(g_{i1} =\mu _1 \partial _x \varphi _i^{k+1} -\lambda _{1i1}^k -\partial _x \lambda _{2i}^k -\mu _2 \partial _x v_i^k \) and \(g_{i2} =\mu _1 \partial _y \varphi _i^{k+1} -\lambda _{1i2}^k -\partial _y \lambda _{2i}^k -\mu _2 \partial _y v_i^k \) . Then we can rewrite (27b) as
As in [27, 29, 30], after introducing the identity operator \(If( {m,l} )=f( {m,l} )\) and shifting operators \(S_x^\pm f( {m,l} )=f( {m\pm 1,l} ), S_y^\pm f( {m,l} )=f( {m,l\pm 1} )\), (28) can be rewritten as
Based on the discrete Fourier transform, we have the following FFT properties for the shifting operators
where \(f( {y_m ,y_l })\) is the function in time domain, \(y_m \) and \(y_l \) are discrete frequencies. Let \(Z_m =\frac{2\pi }{N_1 }y_m , y_m =1,2,\ldots ,N_1 \) and \(Z_l =\frac{2\pi }{N_2 }y_l ,y_l =1,2,\ldots ,N_2 \), then (29) can be transformed into the following algebraic equations
where the coefficients are
The determinant of this coefficient matrix is shown as follows, and more details can be referred to [29].
This value is always positive for all discrete frequencies if \(\mu _1 >0\). Then, the discrete inverse Fourier transform can be used to update \(\vec {w}_i^k \) as follows
Finally, a simple projection technique can be used to guarantee the constraint \(|{\vec {w}_i }|=1\) to be satisfied if we define
4.4 Minimization of the Auxiliary Variable \(v_i \)
For the minimization problem of (17) and (23), we can derive the Euler–Lagrange equation with respect to \(v_i \) while fixing the variables \(\varphi _i^{k+1} ,\vec {w}_i^{k+1} \) temporarily,
This equation can be solved by using the analytical soft thresholding formula [19], which is given by
4.5 Updating the Lagrange Multipliers
At the end of each step, we need to update the Lagrange multipliers \(\vec {\lambda }_{1i}^k \) and \(\lambda _{2i}^k \) after all sub-minimization problems have achieved their minimum, i.e.,
In summary, all the proposed sub-problems can be solved effectively as discussed above. As in the alternating process, each sub-problem is easy to solve as other variables are kept as constants. As to the stopping criteria for each sub-problem, we will discuss them in next section.
5 Numerical Experiments
In this section, some numerical experiments on synthetic, and real images are presented to validate the performance and efficiency of proposed model and algorithm. All experiments are implemented using Matlab7.8 on a PC (Intel (R), CPU 2.60GHz). The proposed ADMM-P method will be compared with a traditional GDM [12]. For the purpose of fair comparison, the same initialization for both methods is used.
As described in [30], the iterations need to be terminated when the following criteria are satisfied:
(I) We need to monitor the following constraint errors in iterations:
where, \(\Vert \cdot \Vert _{L^{1}}\) denotes the \(L^{1}\) norm on image domain \(\Omega \). All components in (39) are calculated point by point. If \(R_i^k <\varepsilon (\varepsilon \) is a small enough parameter) for \(i=1,2,\ldots ,n\), the overall iteration will be stopped. These good numerical indicators are also used to determinate the values of \(\mu _i ({i=1,2})\), which is the basis of penalty parameter adjustment.
(II) During iteration, the relative errors of Lagrange multipliers and the solution \(\varphi _i^k \) should be monitored. They should decrease to a sufficiently small level:
Note that (40) can be quite small if the penalty parameters are large. This is due to the explicit dependency on the penalty parameters.
(III) The relative energy error can be chosen as stopping criterion:
where \(E^{k}\) is the energy value of (13a). The computation stops automatically when \(R_e^k \) is less than a predefined tolerance, which indicates that the energy approaches its steady state.
Until now, the presentation of the proposed ADMM-P is complete and we will show its effectiveness in next subsection with extensive experiments. Just keep in mind that all numerical quantities are plotted in log scale.
Next, we introduce some specific methods to tune parameters in the process of implementing the proposed approach. The two parameters in the NMS functional (1), \(\alpha \) and \(\beta \), control the length and curvature of the segmentation boundary. The ratio between \(\alpha \) and \(\beta \) is in relation to the connectivity and smoothness of the level lines. As discussed in [30], the connection of disconnected level lines and smoothness of level lines can be guaranteed by a larger parameter \(\beta \). In addition, another two parameters associated with Lagrange multipliers are in the augmented Lagrange energy functional (13): \(\mu _1 \) and \(\mu _2\), and they can be determined according to relative residuals (39), relative errors of the Lagrange multiplier (40), relative errors of \(\varphi _i^k\) (41) and the energy curve. One example is given to show such selection in Experiment 5.1.
5.1 Experiment on a Synthetic Image (Two Objects and One Background)
The first testing image is a synthetic image containing a bar and a U-sharp object (size \(128\times 128\)) as shown in Fig. 1a. In this example, two level set functions are required to describe the shapes. In order to speed up the evolution of contours, we initialize the two level set functions in Fig. 1b using the results from the piecewise constant image segmentation by using variational level set method. The final results of segmentation with depth are presented in Fig. 1c.
In this experiment, the required parameters are selected as \(\alpha =0.5, \beta =3, \mu _1 =3000, \mu _2 =3, \varepsilon =3\), respectively, for the proposed ADMM-P algorithm. In order to determine the ordering relations of the bar and the U-shape object, we minimize the energy functional based on the assumptions that the U-shape object is occluded by the bar or the bar is occluded by the U-shape object. The results are listed in Table 1, from which we can deduce that the bar, the U-shape object and the background are ordered from the nearest to farthest with respect to the observer.
As to the case that the U-shape object is occluded by the bar, we illustrate the relative residuals (39), relative errors of the Lagrange multipliers (40), relative errors of \(\varphi _i^k \)(41) and energy curve in Fig. 2. The graphs come from Fig. 1c. From these plots, one can observe that the proposed algorithm has converged before 30 iterations. They also give an important clue about how to choose penalty parameters \(\mu _i ({i=1,2} )\). In order to guarantee convergence as well as the speed of convergence, the constraint errors \(R_{\vec {w}i}^k , R_{vi}^k ,R_{\vec {\lambda }1i}^k , R_{\lambda 2i}^k \) should converge steadily with nearly the same speed. If \(R_{\vec {w}i}^k , R_{vi}^k \) go to zero faster than others, then one can decrease \(\mu _i \) and vice versa. \(R_{\vec {w}i}^k , R_{vi}^k \) will converge to zero with the same speed as the iteration proceeds and the energy will decrease to a steady constant value when \(\mu _i \) are chosen properly.
As to efficiency of the proposed algorithm, the energy curves produced by using the GDM [12] and the proposed ADMM-P are shown in Fig. 3 and the time costs are shown in Table 2. It is easy to see that the ADMM-P has faster convergence rate and higher efficiency. The parameters for the GDM method in this experiment are set as \(\alpha =0.5, \beta =3, \lambda =0.5, \varepsilon =3, \mathrm{d}t=5\times 10^{-4}\). By considering the comparisons of these two algorithms, we plot the energy functional of the original NMS model.
5.2 Experiment on synthetic image (Three Objects and a Background)
The second testing image is a synthetic one with two circles and a bar (size \(128\times 128\)) shown in Fig. 4a. There are totally four regions to be segmented including three objects and a background. In this case, three level set functions are required. In Fig. 4b, the results by piecewise constant segmentation method are used as the initialization for the level set functions. The final results obtained by the GDM and ADMM-P are presented in Fig. 4c, d, respectively.
The parameters used in the proposed ADMM-P method are chosen as \(\alpha =0.3, \beta =2, \mu _1 {=}600, \mu _2 {=}3, \varepsilon =5\). In this experiment, there are \(3!=6\) possible combinations shown in Table 3 to be considered. After minimizing the energy functional based on the six assumptions separately, the ordering relations between the small circle, the big circle and the bar can be determined. From Table 3, we know that the correct ordering from the nearest to the most further is: small circle, big circle, bar and the background.
In the case of correct ordering, we present the plots of energy decay and time costs in Fig. 5 and Table 4, respectively, by using the GDM and ADMM-P methods in order to compare their computational efficiency. The parameters for the GDM method in this experiment are \(\alpha =0.3, \beta =2, \lambda {=0.1}, \varepsilon =3, dt=1\times 10^{-4}\).
5.3 Experiment on a Noise Image (Two Objects and a Background)
The third experiment is conducted on a noise image (size \(100\times 100\)) with two circles (two objects and a background) as shown in Fig. 6a. The image is corrupted by Gaussian white noise with standard deviation 0.01. Figure 6b presents the initialization of the level set functions by using the results of piecewise constant segmentation method. The final results obtained by the GDM and ADMM-P are presented in Fig. 6c through Fig. 6d, respectively. It can be observed that the segmentation with depth is robust to noises.
In this experiment, the required parameters are selected as follows: \(\alpha =3,\beta =2,\mu _1 =4,\mu _2 =3,\varepsilon =3\) for the proposed ADMM-P method. For the ordering relations between the white circle and the gray circle, we minimize the energy functional based on the assumptions that the white circle occludes the gray circle and the gray circle occludes the white circle, respectively. From the results listed in Table 5, we can deduce that the correct ordering from the nearest to the farthest is: white circle, gray circle and the background.
In the case that white circle occludes gray circle, we further present the energy decaying trends and time costs in Fig. 7 and Table 6, respectively, obtained by using the GDM and ADMM-P methods in order to compare their computational efficiency. The parameters for the GDM method in this experiment are chosen as \(\alpha =3, \beta =2,\lambda {=0.05}, \varepsilon =3, \mathrm{d}t=5\times 10^{-4}\).
5.4 Experiment on a Color Image (Two Objects and a Background)
In the last experiment, a color image with a pencil and a hand (size \(256\times 242\)) shown in Fig. 8a is used. There is a pencil and a hand in this image, so two level set functions are required to represent the shapes. Figure 8b gives the initialization for the level set functions, and it is obtained by piecewise constant segmentation method. The final results obtained by the GDM and ADMM-P are presented in Fig. 8c, d, respectively. Figure 8e, f shows the process of evolution in details. It can be seen clearly that the pencil in the front keeps stable while fingers of the hand gradually connect behind the pencil. According to the segmentation model for vector-valued images proposed in [38], the averages of the data terms over all channels are used for coupling. In fact, the model used to solve color image segmentation with depth information can be stated as follows:
where \(l=1,2,\ldots ,m\) denotes the number of layers of a vector-valued image.
In this experiment, the parameters for the ADMM-P are selected as: \(\alpha =0.5,\beta =10,\mu _1 =85,\mu _2 =3,\varepsilon =3\). In order to determine the ordering relations of the pencil and the hand, we minimize the energy functional based on the assumptions that the pencil occludes the hand, or the hand occludes the pencil, respectively. From the results listed in Table 7, we can choose the correct ordering from the nearest to the farthest is: pencil, hand and the background.
In the case that the pencil occludes the hand, we compare the computational efficiency between the GDM and ADMM-P methods based on their energy decaying plots in Fig. 9 and the time costs in Table 8. The parameters for the GDM method in this experiment are \(\alpha =2, \beta =15, \lambda {=0.1}, \varepsilon =3, dt=8\times 10^{-5}\).
6 Conclusions
As it is known that the Nitzberg–Mumford–Shiota (NMS) model for image segmentation with depth can be described as the classical Mumford–Shah model, this model is computational expensive and time consuming. In order to solve this problem efficiently, for the variational level set formulation of the NMS, we first propose its equivalent simplified variational level set formulation by taking advantage of the property of level set functions as signed distance functions, then we develop the fast ADMM (alternating direction method of multipliers) projection method by combining the ADMM method and projection method. Thus, the original complicated problem is decomposed into a series of simple sub-problems of optimization, and each sub-problem can be easily solved accordingly. Extensive experiments have validated the effectiveness of the proposed ADMM-P approach as the ADMM-P method is much faster than the traditional algorithms based on the GDM and this may be due to the merits of the Gauss–Seidel method, soft thresholding formulas, FFT method, projection method as well as model reduction. Also, the strategies of model simplification and constraint projection can be easily extended to other variational level set models with/without curvatures.
In this paper, the number of objects in an image is known and in future, we will investigate this problem without this assumption.
References
Nitzberg, M., Mumford, D.: The 2.1D sketch. In: Proceedings of the Third IEEE International Conference on Computer Vision, pp. 138–144 (1990)
Yu, C.-C., Liu, Y.-J., Wu, M.T., Li, K.-Y., Fu, X.: A global energy optimization framework for 2.1D sketch extraction from monocular images. Graph. Models 76(5), 507–521 (2014)
Amer, M.R., Yousefi, S., Raich, R., Todorovic, S.: Monocular extraction of 2.1D sketch using constrained convex optimization. Int. J. Comput. Vis. 112(1), 23 (2015)
Zhu, W., Chan, T.F.: A variational model for capturing illusory contours using curvature. J. Math. Imaging Vis. 27(1), 29–40 (2007)
Kang, S.-H., Zhu, W., Shen, J(.J.-H).: Illusory shapes via corner fusion. SIAM J. Imaging Sci. 7(4), 1907–1936 (2014)
Nitzberg, M., Mumford, D., Shiota, T.: Filtering, Segmentation, and Depth. Lecture Notes in Computer Sciences, vol. 662. Springer-Verlag, Berlin (1993)
Mumford, D., Shah, J.: Optimal approximations by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math. 42(5), 577–685 (1989)
Mumford, D.: Elastica and computer vision. In: Bajaj, C.L. (ed.) Algebraic Geometry and Its Applications, pp. 491–506. Springer-Verlag, New York (1994)
Esedoglu, S., March, R.: Segmentation with depth but without detecting junctions. J. Math. Imaging Vis. 18(1), 7–15 (2003)
Ambrosio, L.A., Tortorelli, V.M.: Approximation of functionals depending on jumps by elliptic functionals via \(\Gamma \)-convegence. Commun. Pure Appl. Math. 43(8), 999–1036 (1990)
Loreti, P., March, R.: Propagation of fronts in a nonlinear fourth order equation. Eur. J. Appl. Math. 2, 203–213 (2000)
Zhu, W., Chan, T.F., Esedoglu, S.: Segmentation with depth: a level set approach. SIAM J. Sci. Comput. 28(5), 1957–1973 (2006)
Zhao, H.-K., Chan, T.F., Merriman, B., Osher, S.: A variational level set approach to multiphase motion. J. Comput. Phys. 127(1), 179–195 (1996)
Chan, T.F., Vese, L.A.: Active contours without edges. IEEE Trans. Image Process. 10(2), 266–277 (2001)
Vese, L.A., Chan, T.F.: A multiphase level set framework for image segmentation using the Mumford and Shah model. Int. J. Comput. Vis. 50(3), 271–293 (2002)
Osher, S., Sethian, J.A.: Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton–Jacobi formulations. J. Comput. Phys. 79(1), 12–49 (1988)
Smereka, P.: Semi-implicit level set methods for curvature and surface diffusion motion. J. Sci. Comput. 19(1–3), 439–456 (2003)
Zhu, W., Tai, X.-C., Chan, T.F.: Image segmentation using Euler’s elastica as the regularization. J. Sci. Comput. 57(2), 414–438 (2013)
Wu, C., Tai, X.-C.: Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models. SIAM J. Imaging Sci. 3(3), 300–339 (2010)
Goldstein, T., O’Donoghue, B., Setzer, S., Baraniuk, R.: Fast alternating direction optimization methods. SIAM J. Imaging Sci. 7(3), 1588–1623 (2014)
Chan, T.F., Esedoglu, S., Nikolova, M.: Algorithms for finding global minimizers of denoising and segmentation models. SIAM J. Appl. Math. 66(5), 1632–1648 (2006)
Lie, J., Lysaker, M., Tai, X.-C.: A binary level set model and some applications to Mumford–Shah image segmentation. IEEE Trans. Image Process. 15(5), 1171–1181 (2006)
Chan, T.F., Kang, S.-H., Shen, J(.J.-H).: Euler’s elastica and curvature-based inpainting. SIAM J. Appl. Math. 63(2), 564–592 (2002)
Masnou, S.: Disocclusion: a variational approach using level lines. IEEE Trans. Image Process. 11(2), 68–76 (2002)
Zhu, W., Chan, T.F.: Image denoising using mean curvature of image surface. SIAM J. Imaging Sci. 5(1), 1–32 (2012)
Yip, A., Zhu, W.: A fast modified Newton’s method for curvature based denoising of 1D signals. Inverse Probl. Imaging 7(3), 1075–1097 (2013)
Zhu, W., Tai, X.-C., Chan, T.F.: Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Probl. Imaging 7(4), 1409–1432 (2013)
Myllykoski, M., Glowinski, R., Karkkainen, T., Rossi, T.: A new augmented Lagrangian approach for L1-mean curvature image denoising. SIAM J. Imaging Sci. 8(1), 95–125 (2015)
Tai, X.-C., Hahn, J., Chung, G.J.: A fast algorithm for Euler’s elastica model using augmented Lagrangian method. SIAM J. Imaging Sci. 4(1), 313–344 (2011)
Tai, X.-C.: Fast Numerical Schemes Related to Curvature Minimization: A Brief and Elementary Review, UCLA CAM Report14-40 (May, 2014)
Osher, S., Fedkiw, R.: Level Set Methods and Dynamic Implicit Surfaces. Springer, Berlin (2003)
Zhao, H.-K.: Fast sweeping method for eikonal equations. Math. Comput. 74, 603–627 (2005)
Li, C., Xu, C., Gui, C., Fox, M. D.: Level set evolution without re-initialization: a new variational formulation. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005, vol. 1, pp. 430–436, June 20 (2005)
Liu, C., Dong, F., Zhu, S., Kong, D., Liu, K.: New variational formulations for level set evolution without re-initialization with applications to image segmentation. J. Math. Imaging Vis. 41(3), 194–209 (2011)
Duan, J., Pan, Z., Yin, X., Wei, W., Wang, G. (2014) Some fast projection methods based on Chan–Vese model for image segmentation. EURASIP J. Image Video Process. 10.1186/1687-5281-2014-7
Yashtini, M.: Alternating Direction Method of Multiplier for Euler’s Elastica-Based Denoising, Scale Space and Variational Methods in Computer Vision, pp. 690–701. Springer, Berlin (2015)
Marquina, A., Osher, S.: Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removal. SIAM J. Sci. Comput. 22(2), 387–405 (2000)
Chan, T.F., Sandberg, B.Y., Vese, L.A.: Active contours without edges for vector-valued images. J. Vis. Commun. Image Represent. 11(2), 130–141 (1970)
Wang, Y., Yin, W., Zeng, J.: Global convergence of ADMM in nonconvex nonsmooth optimization. arXiv preprint arXiv:1511.06324, (2015)
Glowinski, R., Pan, T.W., Tai, X.C.: Some facts about operator splitting and alternating direction methods. UCLA CAM Report: 16-10 (2016)
Acknowledgements
The work has been partially supported by the National Natural Science Foundation of China with Grant numbers 61305045, 61170106, 61363066 and 61303079.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tan, L., Pan, Z., Liu, W. et al. Image Segmentation with Depth Information via Simplified Variational Level Set Formulation. J Math Imaging Vis 60, 1–17 (2018). https://doi.org/10.1007/s10851-017-0735-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-017-0735-3