IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 Comparison Between The Performance of Parametric Active Contour Models F. A.Alwan Department of Computer Science, College of Education Ibn Al-Haitham, University of Baghdad, Abstract Snakes, or active contours, are used extensively in computer vision and image processing applications, particularly to locate object boundaries. In this research, for the segmentation of anatomical structures in medical images three approaches were implemented and compared like (original snake model, distance potential force model and Gradient Vector Flow (GVF) snake model). We used Computed Tomography image (CT) for our experiments. Our experiments show that original snake model has two problems; first is the limited capture range and the second is the poor convergence. Distance potential force model solved only the first problem of original snake and failed with second problem. Gradient Vector Flow (GVF snake) provides a good capture rang and a good convergence; therefore good results are obtained where GVF snake could successfully segment the anatomical structures from CT images. Introduction Snakes are energy-minimizing curves that are defined within an image and are deformed by the effect of the internal energy of the curve itself and the external forces derived from the image. Snakes are widely used in many applications, including edge detection [1], shape modeling [2], segmentation [3] and motion tracking. There are two key difficulties with parametric active contour algorithms. First, the initial contour which in general must be close to the true boundary or else it will likely converge to the wrong result. The second problem is that active contours have difficulties progressing into boundary concavities [4]. Then, Cohen and Cohen [5] proposed a distance potential force model. The general idea behind this model is to have large external forces far away from the boundaries of the object, thus increasing the capture range of the snake. Even then, snakes based on this model fail to converge to concavities. The technique presented by IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 Xu and Prince (GVF snake) addresses these issues and presents a new formulation for active contour modeling [6,7]. In this research, we show the advantages of the GVF snake over the traditional models where we discuss and compare between it and the original model and distance potential force model. Also we discuss some results obtained by implementing and testing the algorithms of these models. Background An original snake is a curve x(s) = [x(s), y (s)] s [0,1] that moves through the spatial domain of an image to minimize the energy functional E = dssEβsα s ))(( x)(x")(x' ext 22 1 2 1 0       where α and β are weighting parameters that control the snake’s tension and rigidity, respectively, )(x' s and )(x" s denote the first and second derivatives of x(s) with respect to s. The external energy function E ext is derived from the image so that it takes on its smaller values at the features of interest, such as boundaries. Given a gray-level image I(x, y), viewed as a function of continuous position variables (x, y), typical external energies are designed to lead a snake toward step edges are: E ext (x, y) = - 2y)I(x, Eext (x, y) = -   2 y)I(x,y)(x,G * σ  where y)(x,G σ is a two-dimensional Gaussian function with standard deviation σ and  is the gradient operator. If the image is a line drawing (black on white), then appropriate external energies include [8]: E ext (x, y) = I (x, y) E ext (x, y) = y)I(x,y)(x,G * σ It is easy to see from these definitions that largerσ’s will cause the boundaries to become blurry. Such large σ’s are often necessary, however, in order to increase the capture range of the snake. ………. (1) ………. (2) ………. (3) ………. (4) ………. (5) IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 A snake that minimizes E must satisfy the Euler equation 0ext  E)('''x')(' x'α ss β This can be viewed as a force balance equation 0FF extint  where Fint = )('''x')(' x'α ss β and Fext = extE . The internal force Fint discourages stretching and bending while the external potential force Fext pulls the snake toward the desired image edges. To find a solution to (6), the snake is made dynamic by treating x as function of time t as well as S (i.e., x(s, t)). Then, the partial derivative of x with respect to t is then set equal to the left side of (6) as follows: x t (s, t) = ext E )('''x')(' x'α t s,t s, β When the solution x(s, t) stabilizes, the term x t (s, t) vanishes and we achieve a solution of (6). A solution to (8) can be found by discretizing the equation and solving the discrete system iteratively. Behavior of original Snake Model An example of the behavior of an original snake is shown in Fig.(1). Fig.(1a) shows a 256256-pixel line drawing of a V-char object (shown in black) having a boundary concavity at the top. It also shows a sequence of curves (in red) depicting. The iterative progression of an original snake ( = 0.05,  = 0, iteration no. = 100) initialized outside the object but within the capture range of the potential force field. The potential force field Fext = extE where σ= 0 pixel is shown in Fig.(1b). We note that the final solution in Fig (1a) solves the Euler equations of the snake formulation, but remains sp lit across the concave region. The reason for the poor convergence of this snake is revealed in Fig.(1c), where a close-up of the external force field within the boundary concavity is shown. Although the external forces correctly point toward the object boundary, within the boundary concavity the forces point horizontally in opposite directions. Therefore, the active contour is pulled apart ………. (6) ………. (7) ……….(8) IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 toward each of the “fingers” of the V-char, but not made to progress downward into the concavity. There is no choice of  and  that will correct this problem. Another key problem with original snake formulations, the problem of limited capture range, can be understood by examining Fig.(1b). In this figure, we see that the magnitude (5) will increase this range, but the boundary localization will become less accurate and distinct, ultimately obliterating the concavity itself when becomes too large. Behavior of Distance potential Force Model Cohen and Cohen [5] proposed an external force model that significantly increases the capture range of an original snake. These external forces are the negative gradient of a potential function that is computed using a Euclidean distance map. Fig.(2) shows the performance of a snake using distance potential forces. Fig.(2a) shows both the V-char object (in black) and a sequence of contours (in red) depicting the progression of the snake from its initialization far from the object to its final configuration. The distance potential forces shown in Fig.(2b) have vectors with large magnitudes far away from the object, explaining why the capture range is large for this external force model. As shown in Fig.(2a), this snake also fails to converge to the boundary concavity. This can be explained by inspecting the magnified portion of the distance potential forces shown in Fig.(2c). We see that, like traditional potential forces, these forces also point horizontally in opposite directions, which pulls the snake apart but not downward into the boundary concavity. We note that Cohen and Cohen’s modification to the basic distance potential forces, which applies a nonlinear transformation to the distance map (5), does not change the direction of the forces, only their magnitudes. Therefore, the problem of convergence to boundary concavities is not solved by distance potential forces. Gradient Vector Flow Field The authors Xu and Prince present a solution to the problems by replacing the standard external force Fext in the force balance equation (7) with a static external force which does not change with time or depend on the position of the snake itself. This new static external force field Fext = v (x, y) is called the Gradient Vector Field or GVF. Replacing the external potential force extE in (8) with v yields the following equation: xt (s, t) = v )('''x')(' x'α t s,t s, β The parametric curve solving the above dynamic equation is termed as a GVF snake [6]. ………. (9) IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 Steps of GVF Snake Formation The process starts by calculating the edge map of the given image, using any edge finding algorithm from the image processing literature. ),(),( ext yxyxf E i  where i = 1, 2, 3 or 4. The edge map has three important features relating to snake formation. One, the gradient of this edge map  f has vectors pointing towards the edge, which is a desirable property for snakes. Two, these vectors have large magnitude at the vicinity of the edges. Three, in homogenous regions (regions with little variation in image intensity)  f is almost zero, and therefore no information about nearby or distant edges is available. The second and third features can be problematic when constructing an active contour. To keep the first feature and nullify the effect of the latter two, the gradient map is extended farther away from the edges and into homogenous regions using a computational diffusion process. The gradient vector flow field is defined as the vector field v (x, y)= (u (x, y), v (x, y)) that minimizes the following energy functional:  ε   μ dxdyff yxyx vvuu 222222 )(  -v As can be seen, this is an example of variational formulation of regularization. The parameter μ is a regularizing parameter which adjusts the tradeoff between the first and second terms of the integrand and is set according to the level of noise present in the image. Also, when the value of the edge gradient f is small, energy is dominated by the sum of the partial derivatives of the gradient field, and yields a smooth field. On the other hand, when f is large, the second term dominates the integrand. In this case, setting v = f minimizes the energy. Overall, this formulation transforms the gradient vector flow field by keeping it equal to the edge gradient at the boundaries; it also keeps v slowly varying at the homogenous regions of the image. Using the calculus of variations, it can be shown that the GVF field can be found by solving the pair of Euler equations. 0))(( 222  yx fff-u-u x  0))(( 222  yxy fff-v-v ………. (10) ………. (11) ………. (12a) ……….(12b) IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 Here, 2 is the Laplacian operator. These equations give us another intuition behind the GVF formulation. It is noted that in homogeneous regions, the second term of both equations (12a) and (12b) is zero (because the gradient of f (x, y) is zero). Therefore, within these regions, u and v are each determined by Laplace's equation. This results in a type of “filling-in” of information taken from the boundaries of the region. Equations (12a) and (12b) can be solved numerically by treating u and v as a function of time. The resulting equations are: ),,( tyxu t )),(),,((),,(2 yxftyxutyxu x  )),(),(.( 22 yxfyxf yx  ),,( tyxv t )),(),,((),,(2 yxftyxvtyxv y  )),(),(.( 22 yxfyxf yx  The steady-state solution of equation (13a) and (13b) yields the solution to the Euler equations (12a) and (12b). An iterative solution can be set up for solving the equations above [6]. Equations in (13a) and (13b) are known as generalized diffusion equations, and are known to arise in such diverse fields as heat conduction, reactor physics, and fluid flow [9]. In GVF snake, they are used to satisfy “filling in” property. The experiments of implementation of GVF snake algorithm To see the key differences between GVF snake algorithm and the previous algorithms (the original snake and distance potential force models); it was implemented on the same line drawing V-char image, see Fig.(3). The parameters that should be given are  and no. of iteration for computing the (GVF field), and  ,  and the no. of iteration for (GVF snake); and their values are shown in the table(1). Fig.(3b) reveals these several key differences. First, the GVF field has a much larger capture range. A second observation is that the GVF vectors are pointing somewhat downward into the top of the V-char, which should cause an active contour to move farther into this concave region. Fig.(3a) shows the result of applying a GVF snake. In this case, the snake was initialized farther away from the object than the initialization in Fig.(1a), and yet it converges very well to the boundary of the V-char. ………. (13a) ………. (13b) IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 Implementation of Snakes models with Gray Level Images In this section, we show how the original snake, distance potential force, and GVF snake model, can be applied to medical image segmentation. In order to show the interests of the segmentation by these snakes, we select a CT image of 256256 pixels. The image represents abdominal CT (slice of kidneys). We implemented the mentioned above algorithms on the same CT image to show the difference in performance between them. To reveal the efficiency of these snakes in segmentation process, see the Fig.(4). In Figs.(4a, 4b) the original snake and distance potential force model could not segment the left kidney properly from CT image in concave region, in contrast with GVF snake where it could correctly evolves towards the desired boundary of left kidney, see Fig.(4c). In our experiment, the values of parameters of original snake, distance potential force, and GVF snake model are shown in table(2). Key Issues This work on the comparison between the performance of snakes models and us ing their algorithms in segmentation process of anatomical structures from CT images using active contours focuses on: Comparisons between the performance of original snake model, distance potential force model and performance of GVF snake, and the candidate values of snakes’ parameters. These phases are discussed in the following sections. Comparison of Performance The performance of the original snake model, distance potential force model and GVF snake model is compared in terms of: Convergence to a Concave Region, and Insensitivity to Initialization. With respect to convergence to concave region the comparison was explained in details in the above sections but the insensitivity to initialization we discussed only one case of initialization (outside the boundary of desired object), another example about the outside initialization is shown in Fig.(5). In this section, we discuss the initialization from inside the boundary of desired object. See Fig.(6), Fig.(6a) is the original image of thyroid gland with a cystic and capsulated lesion. See the initial curve in red color inside the cystic lesion. In Fig.(6b) the original snake model couldn’t segment the cystic lesion while in Fig.(6c, 6d) the distance potential force and GVF snake model could segment the cystic lesion properly because they have large capture range. In our experiment, the values of parameters are shown in table(3). IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 The Candidate Values of Snakes’ Parameters With respect to determine the appropriate values for tension, rigidity and the external force weightings; we found that the acceptable range for each weight is as follows: Increasing β will increase the rigidity of the model and would affect the shape even if close to start with. We found that the rigidity weighting factor can be increased from 0 to 0.03 with almost the same results. Decreasing the tension weight causes the active contour to follow the influence of the external force and lose its smoothness. The acceptable range that we found for tension was from 0.02 to 0.08. For values over α = 0.08, the active contour must be initialized close to the boundary; otherwise, the tension force tries to contract the model and prevents the contour points from easily converging to the boundary. Also we found that with parametric active contours the ratio of force weightings is more important than the values themselves. For instance, if the force weighting is increased four times, which indeed exceeds the previously recommended ranges for the force weightings (i.e., external force =2.4, α = 0.2 & β =0.06), the active contour behaves as it does for external force =0.6, α = 0.05 & β =0.01, but it requires that the initial contour be closer to the boundary. With respect to regularization parameter  , the acceptable range that we found for it was from 0 to 0.2, but if the desired object has sharp corners the value of  must be less than 0.1 else the final configuration has slightly rounder corners. Conclusion The gradient vector flow based active contour generation algorithm by Xu and Prince was compared. The algorithm, along with an original snake generation algorithm and distance potential force model were implemented on various images, both grayscale and line drawing images. It was found that the algorithm succeeds in converging the active contour to boundary concavities in both types of images. The drawback of the methods is its execution speed. Insp ite of its robustness to initialization and increased capture range, the algorithm takes a long time to converge to object contours. With respect to snakes’ parameters, it is found that, there is no way to compute or directly give the appropriate values for these parameters, but by experiments and common sense. Also the appropriate values of these parameters of our experiments were discussed in the section (The experiments With Force Weighting Factors). Reference 1. Kass, M.; Witkin, A. and Terzopoulos, D. (1986). “Snakes: Active Contour Models”, International Journal of Computer Vision, 3: 321-331. IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 2. Terzopoulos, D. and Fleischer, K. (1988). “Deformable models”, Vis. Comput., 4: 306–331. 3. Leymarie, F. and Levine, M. D. (1993). “Tracking deformable objects in the plane using an active contour model”, IEEE Trans. Pattern Anal. Machine Intell., 15: 617– 634. 4. Davatzikos, C. and Prince, J. L. (1995). “An active contour model for mapping the cortex”, IEEE Trans. M ed. Imag., 14: 65–80. 5. Cohen, L. D. and Cohen, I. (1993). “ Finite-Element Methods For Active Contour Models and Balloon For 2D and 3D Images”, IEEE Trans. On Pattern Analysis and Machine Intelligence, 15(11): 1131-1147. 6. Xu, C. and Prince, J. L. (Mar. 1998). “Snakes, Shapes, and Gradient Vector Flow”, IEEE Trans. On Image Processing, 7: 3. 7. Sattar, J. “Snakes, Shapes and Gradient Vector Flow”, School of Computer Science, McGill University, Montreal QC Canada H3A 2A7. 8. Cohen, L. D. (Mar. 1991). “On active contour models and balloons”, CVGIP: Image Understand., 53: 211–218. 9. Charles, A. H. and Porsching, T. A. (1990). “Numerical Analysis of Partial Differential Equations”, Prentice Hall, Engelwood Cliffs, NJ. Table (1) Values of GVF snake parameters with V-char image ( ) GVF iteration ( ) ( ) Iteration No. 0.1 80 0.05 0 380 Table (2) Values of snake models’ parameters with CT of kidneys Snake type ( ) ( ) GVF iteration ( ) ( ) Iteration No. Original 3 - - 0.5 0 80 Distance 2 - - 0.5 0 80 GVF 2 0.1 80 0.05 0 50 Table (3) Values of snake models’ parameters with CT of thyroid gland and with inside case of initialization. Snake type ( ) ( ) GVF iteration ( ) ( ) Iteration No. Distance potential 3 - - 0.01 0 23 GVF snake 0 0.1 80 0.01 0 23 Original snake 3 - - 0.05 0 50 IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 (a) (b) (c) Fig.(1) (a) Convergence of a snake using (b) traditional potential forces, and (c) shown close-up within the boundary concavity. (a) (b) (c) Fig.(2) (a) Convergence of a snake using (b) distance potential forces, and (c) shown close-up within the boundary concavity. (a) (b) (c) Fig.( 3) (a) Convergence of a snake using (b) GVF external forces, and (c) shown close- up within the boundary concavity. IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 (a) (b) (c) Fig.(4) Segmenting the left kidney by (a) the original snake model and (b) the distance potential force model which they failed in segmentation process in concave region of the left kidney, (c) is the final snake of GVF model which could segment the left kidney properly. (a) (b) (c) Fig (5) Outside initial curve and Segmenting the cystic lesion of liver by (a) an original snake, (b) a distance potential force snake, and (c) a GVF snake. IBN AL- HAITHAM J. FO R PURE & APPL. SC I. VOL.23 (1) 2010 (a) (b) (c) (d) Fig.(6) (a )Original image of thyroid gland with a cystic and capsulated lesion with inside case of initialization (b) an original snake, (c) a distance potential force snake, and (d) a GVF snake. 2010) 1( 23مجلة ابن الھیثم للعلوم الصرفة والتطبیقیة المجلد لمنحنیات النشیطةمقارنة بین أداِء نماذِج ا ن فائزه عبد الجبار علوا د، أبن الهیثم-كلیة التربیه ،قسم الحاسبات جامعة بغدا الخالصة من اجل یة الحاسوب ومعالجة الصور الرقمیةفي تطبیقات روؤ االفاعي او المنحنیات النشیطة تستخدم بكثرة .ایجاد حدود االجسام ة نماذج من وألجل تقطیع التراكیب التشریحیة من الصور الطبیة تم استخدام و مقارنة ثالث، في هذا البحث ًا أنموذج االفعى العاملة و، ذج القوى الكامنة للمسافةأنمو ، نموذج االفعى االصلي أو التقلیديأمثل المنحنیات النشیطة وفق ة فلنوع الصور الطبیه التي استخدمت في تجارب هذا البحث أما بالنسبة .لتدفق متجهات المیل هي الصور المقطعی ). CT(بالكومبیوتر ، یمتلك مدى التقاط محدوداالولى انه المشكلة، االصلي یعاني من مشكلتیننموذج االفعى أتجارب البحث أظهرت بأن . لالشكال التعامل مع التغیرات التوبولوجیة مثل الزوایا الحادة والمناطق المقعرة انه الیستطیع التكیف او والمشكلة الثانیة مشكله االولى ال أنموذج القوى الكامنة للمسافةكذلك ة نتمكن من حل ال موذج االفعى االصلى لكنه فشل في حل المشكل ط كبیر جدًا یمتد الى حدود الصورة مما یجعل تمتلك مدى التقاف وفقًا لتدفق متجهات المیل أما االفعى العاملة .الثانیة ت وعبر حدود الجسم المطلوب كذلك ی، من داخل ، بعیدة، یبة یمكن ان تكون قر االفعى االبتدائیة مكنها التكیف للتغیرا ب إذ، تم الحصول على نتائج جیدة لذلك، التبولوجیة تمكنت االفعى العاملة وفقا لتدفق متجهات المیل من تقطیع التراكی . التشریحیة بنجاح من الصور المقطعیة