This section is devoted to the discussion on further numerical experiments computed by the semi-implicit co-volume level set method. In Section 11.2 we already discussed some examples which have been used mainly to illustrate the advection-diffusion mechanism of the segmentation equation (11.2) and the role of parameter e in closing the gaps. In the sequel we will discuss the role of additional model parameters as well as all aspects of our implementation. We also compare the method with different approaches to confirm efficiency of our numerical scheme.
For a given discrete image I0 with n1, n2, the number of pixels in the vertical and horizontal directions, respectively, we define space discretization step h = n*. It means, we embed the image into a rectangle [-0.5n^, 0.5n^] x [-0.5, 0.5]. If one wants to use h = 1 (which would correspond to pixel size equals to 1), all considerations can be changed accordingly. We prefer the above definition of spatial discretization step, because it is closer to standard approaches to numerical solution of PDEs.
First we give some CPU times overview of the method. Since we are interested in finding a "steady state" (see discussion in Section 11.2) of the evolution in order to stop the segmentation process, the important properties are the number of time steps needed to come to this "equilibrium" and a CPU time for every discrete time step. We discuss CPU times in the experiment related to segmentation of the circle with a gap given in Fig. 11.12 (left), computed using e — 10-2 (see Fig. 11.14 (top left)). The testing image has 200 x 200 pixels and the computational domain ^ corresponds to the whole image domain. Since for the boundary nodes we prescribe Dirichlet boundary conditions, we have M — 198 x 198 degrees of freedom. As the criterion to recognize the "steady state," we use a change in L2 norm of solution between subsequent time steps, i.e., we check whether
with a prescribed threshold 8. For the semi-implicit scheme and small e (then the downwards motion of the "steady state" is very slow) a good choice of threshold is 8 — 10-5.
Reasonable time steps for our semi-implicit method are of order (10h)2, e.g., for the discussed example very good results regarding CPU times and precision have been obtained for t e [0^001, 0^01]. Since by a classical criterion the precision of numerical schemes for parabolic equations is optimal for t ^ h2, we have also computed such a case. But, no significant difference due to precision has been observed, only much longer CPU time was necessary. In our example t — 5 x 10-3 and 20 time steps yield the segmentation result (using threshold 8 — 10-5). On 2.4 GHz Linux PC, the overall CPU time for this segmentation was 4.93 sec (i.e., approximately 0.25 sec for one time step including construction of coefficients and solving the linear system). This CPU time was obtained with TOL — 10-3. Since we are mainly interested in "equilibrium," one can also decide that such precision is not necessary in every discrete time step. With increasing TOL fewer numbers of SOR iterations are needed. Another way is to prescribe a fixed number (but not too small) of iterations in every time step, e.g., ten
0.0125 0.015 0.0175 0.02 0.02250.0250.0275
0.0125 0.015 0.0175 0.02 0.0225 0.025
Figure 11.19: Histogram of the segmentation result given by semi-implicit scheme after 20 time steps (top left). Histograms of the segmentation function given by the explicit scheme after 500 (top right), 1000 (bottom left), and 5000 (bottom right) time steps (color slide).
prescribed SOR iterations lead to comparable segmentation with twice faster CPU time as mentioned above.
Now, let us look at the behavior of the explicit scheme in this example. We use the explicit version of the scheme (11.23) where also the second term on the left-hand side is taken from the (n — 1)th time step. Then, due to stability reasons, we have to choose t = 5 x 10—6. Although one explicit time step takes just 0.05 sec (including construction of coefficients and explicit time update of the solution), to get a segmentation result comparable with the semi-implicit scheme we need about 10 000 time steps. In Fig. 11.19 we present histograms of the segmentation function, where the plotted range [0, 100] in the vertical direction has been chosen for visualization. We compare histograms, because one cannot use the same threshold 8 for explicit and semi-implicit schemes due to very small change in the solution between time steps in explicit scheme. In the top left, there is a histogram of the segmentation result given by semi-implicit scheme after 20 time steps. The shocks in solution (corresponding to outer and inner edges of the circle) are given by two large gaps in histogram. In the top right there is a histogram of the segmentation function given by the explicit scheme after 500 time steps, and then after 1000 (bottom left) and 5000 (bottom right) time steps. We see that, due to necessity of small time step, the formation of the piecewise flat solution is very slow for explicit scheme. Although after 1000 time steps one can see the formation of two gaps which could be already used for detection of "final" segmentation result, the CPU time for 1000 steps of explicit scheme is 49.5 sec, which is ten times longer than for semi-implicit scheme. If we would like to obtain a similar histogram as plotted in the top left using an explicit scheme, we would need 100 times longer CPU time as in the case of semi-implicit scheme.
In all computations presented above, we have usedg(s) = 1+iKsi, K = 1. In experiments without noise there is no significant difference by changing K. We get the same behavior of the method changing K from 0.1 to 10. It is understandable because the function g plays a role only along edges and its more (K > 1) or less (K < 1) quickly decreasing profile governs only speed by which level sets of solution are attracted to the edge from a small neighborhood. Everywhere else only pure mean curvature motion is considered (g = 1).
The situation is different for noisy images, e.g., depicted in Fig. 11.12 (right) and Figs. 11.16 and 11.17. The extraction of the circle in noisy environment takes a longer time (200 steps with t = 0.01and K = 1) and it is even worse for K = 10. However, decreasing the parameter K gives stronger weight to mean curvature flow in noisy regions, so we can extract the circle fast, in only 20 steps with the same t = 0.01. In the case of noisy images, also the convolution plays a role. For example, if we switch off the convolution, the process is slower. But decreasing K can again improve the speed of segmentation process. In our computations we either do not apply convolution to 10 or we use image presmoothing by m x m pixel mask with weights given by the Gauss function normalized to unit sum.
We start all computations with initial function given as a peak centered in a "focus point" inside the segmented object, as plotted, e.g., in Fig. 11.10 (top left). Such a function can be described for a circle with center s and radius R by u0(x) = x—1+, where s is the focus point and 1 gives maximum of u0. Outside the circle we take value u0 equal to . If one needs zero Dirichlet boundary data, e.g., due to some theoretical reasons (cf. [11,49]), the value r^ can be subtracted from the peak-like profile. If the computational domain ^ corresponds to image domain, we use R = 0.5. For small objects a smaller R
can be used to speed up computations. Our choice of peak-like initial function is motivated by its nearly flat profile near the boundary of computational domain. However, other choices, e.g., u0(x) = 1 — , are also possible. If we put the focus point s not too far from the center of mass of the segmented object, we get only slightly different evolution of the segmentation function and same segmentation result.
Now we will discuss some further segmentation examples. In Fig. 11.20 we present image (234 x 227 pixels) with subjective contours of the classic triangle of Kanizsa. The phenomenon of contours that appear in the absence of physical gradients has attracted considerable interest among psychologists and computer vision scientists. Psychologists suggested a number of images that strongly require image completion to detect the objects. In Fig. 11.20 (left), two solid triangles appear to have well defined contours, even in completely homogeneous areas. Kanizsa called the contours without gradient "subjective contours" , because the missed boundaries are provided by the visual system of the subject. We apply our algorithm in order to extract the solid triangle and complete the boundaries. In Figs. 11.21 and 11.22 we present evolution of the segmentation function together with plots of level lines accumulating along edges and closing subjective contours areas. In this experiment we used e = 10—5, K = 1, v = 0.5, r = 0.001, TOL = 10—3. For long time periods (from 60th to 300th time step) we can also easily detect subjective contours of the second triangle. The first one, given by closing of the solid interrupted lines, is presented in Fig. 11.22 (bottom), visualizing level line (min(u) + max(u))/2. Interestingly, for bigger e the second triangle has not been detected.
Was this article helpful?