Potential Fields as an External Force and Algorithmic Improvements in Deformable Models

Correspondence to: [email protected] Recommended for acceptance by Maria Petrou ELCVIA ISSN: 1577-5097 Published by Computer Vision Center / Universitat Autonoma de Barcelona, Barcelona, Spain Electronic Letters on Computer Vision and Image Analysis 2(1):25-36, 2003 Potential Fields as an External Force and Algorithmic Improvements in Deformable Models A. Caro*, P. G. Rodríguez*, E. Cernadas+, M. L. Durán* and T. Antequera§ * Departamento de Informática, Universidad de Extremadura, Avda. Universidad s/n, Cáceres, Spain + Departamento de Informática, Universidade de Vigo, Campus As Lagoas s/n, Ourense, Spain § Tecnología de Alimentos, Universidad de Extremadura, Avda. Universidad s/n, Cáceres, Spain Received 26 June 2002; accepted 25 June 2003 Abstract Deformable Models are extensively used as a Pattern Recognition technique. They are curves defined within an image domain that can be moved under the influence of internal and external forces. Some trade-offs of standard deformable models algorithms are the selection of image energy function (external force), the location of initial snake and the attraction of contour points to local energy minima when the snake is being deformed. This paper proposes a new procedure using potential fields as external forces. In addition, standard Deformable Models algorithm has been enhanced with both this new external force and algorithmic improvements. The performance of the presented approach has been successfully proved to extract muscles from Magnetic Resonance Imaging (MRI) sequences of Iberian ham at different maturation stages in order to calculate their volume change. The main conclusions of this paper are the practical viability of potential fields used as external forces, as well as the validation of the algorithmic improvements developed. The feasibility of applying Computer Vision techniques, in conjunction with MRI, for determining automatically the optimal ripening time of the Iberian ham is a practical conclusion reached with the proposed approach. Key Words: Deformable Models, Active Contours, Snakes, Pattern Recognition, Image Analysis, Computer Vision, Magnetic Resonance Imaging (MRI). 1 Introduction Active Contours (or snakes) are a low-level processing technique widely used to extract boundaries in many pattern recognition applications [1]. In this paper, an improved snake is proposed to recognise muscles in MRI sequences of Iberian ham in different maturation stages. In the next subsections, an overview of the Active Contours is presented, and the relationship with the field of Food Technologies is exposed. In addition, the algorithm design is presented in section 2, and the obtained results are discussed in section 3. Conclusions are shown in section 4. 26 A. Caro et al. / Electronic Letters on Computer Vision and Image Analysis 2(1):25-36, 2003 1.1 Overview on Active Contours Deformable models are curves defined within an image domain that can be moved under the influence of internal forces, which are defined within the curve or surface itself, and external forces, which are computed from the image data. The internal forces are designed to keep the model smooth during deformation. The external forces are defined to move the model toward an object boundary or other desired features within an image [2]. Energy-minimising Active Contour models were proposed by Kass et al. [3]. They formulated a model using an energy function. They developed a controlled continuity spline which can be operated upon by internal contour forces, images forces, and external forces which are supplied by an interactive user, or potentially by a higher level process. The goal was to obtain a local minimum that seems most useful to that process or user. An algorithmic solution involves derivation of this objective function and optimisation of the derived equation for finding an appropriate solution. However, in general, variational approaches do not guarantee global optimality of the solution [4]. Amini et al. [4] also proposed a dynamic programming algorithm for minimising the functional energy that allows addition of hard constraints to obtain a more desirable behaviour of the snakes. However, the proposed algorithm is slow, having a great complexity O(nm3), where n is the number of points in the contour and m is the size of the neighbourhood in which a point can move during a single iteration [4, 5]. Cohen [5] proposed an additional force that made the curve behave like a balloon which is inflated by this new force. On the other hand, Williams and Shah [6] developed a greedy algorithm which has performance comparable to the dynamic programming and variational calculus approaches. They presented different formulations for the continuity term, and they examined and evaluated several approximations for the curvature term. The proposed approach was compared to the original variational calculus method of Kass et al. and the dynamic programming method developed by Amini et al. and found to be comparable in the final results, while having less computational cost than dynamic programming (lower complexity) and being more stable and flexible for including hard constraints than the variational calculus approach. Kichenassamy [7] presented a new Active Contour and surface model based on novel gradient flows, differential geometry and curve and surface evolutions. This led to a novel snake paradigm in which the feature of interest may be considered to lie at the bottom of a potential well. In addition, Radeva et al. proposed new approaches incorporating the gradient orientation of image edge points [8], and implementing a new potential field and external force in order to provide a deformation convergence, and attraction by both near and far edges [9]. McInerney and Terzopoulos [10] also developed a parametric snakes model that had the power of an implicit formulation by using a superposed simplicial grid to quickly and efficiently reparameterise the model during the deformation process. To reduce the problems caused by convergence to local minima, some authors have proposed simulated annealing as well as multiscale methods [11]. Pérez et al. [12] presented a new technique to construct Active Contours based on a multiscale representation using wavelet basis. Another approach to deal with this problem was proposed by Giraldi et al. [13]. They presented the Dual Active Contour Model, which consisted basically in comparing one contour that expands from inside the target feature, and another one which contracts from the outside. The two contours were interlinked to drive the contour out of local minima, making the solution less sensitive to the initial position. Caselles et al. [14] proposed a geodesic Active Contour model based on energy minimisation and geometric Active Contours based on the theory of curve evolution. They proved that a particular case of the classical energy snake model is equivalent to finding a geodesic or minimal distance path in a Riemannian space with a metric derived from the image content. This means that under a specific framework, boundary detection can be considered equivalent to finding a path of minimal weighted length via an Active Contour model based on geodesic or local minimal distance computation. Nevertheless, no method has been proposed for finding the minimal paths within their geodesic Active Contour model [15]. Goldenberg et al. [16] proposed a new model, using an unconditionally stable numerical scheme to implement a fast version of the geodesic Active Contour model. A. Caro et al. / Electronic Letters on Computer Vision and Image Analysis 2(1):23-34, 2003 27 Xu and Prince [17] developed a new external force for Active Contours, which they called gradient vector flow. This new force was computed as a diffusion of grey-level gradient vector of a binary edge map derived from the image. The corresponding snake was formulated directly from a force balance condition rather than a variational formulation [18]. Ballerini [19] proposed an energy minimisation procedure based on Genetic Algorithms. These Genetic Algorithms operate on the position of the snake, and their fitness function is the total snake energy. A modified version of the image energy was used, considering both the magnitude and the direction of the gradient and the Laplacian of Gaussian, though the region of interest is defined by an external user. Park and Keller [20] presented a new approach that combines dynamic programming and the watershed transformation, calling it the watersnake. The watershed transformation technique is used to decide what points are needed, in order to eliminate unnecessary curves while keeping important ones. 1.2 Scope and purpose of the research Image segmentation is a very important aspect of the Computer Vision techniques. It could be applied in the field of Food Technology to determine some features of this kind of images. Particularly, Iberian ham images were processed in this research in order to find out some characteristics and reach conclusions about this excellent product. The Iberian pig is a native animal bred from the south-western area of Spain, and drycured ham from Iberian pig is a meat product with a high sensorial quality and first-rate consumer acceptance in our country. The ripening of Iberian ham is a lengthy process (normally 18-24 months). Physical-chemical and sensorial methods are required to evaluate the different parameters in relation with quality, being generally tedious, destructive and expensive [21]. Traditionally, the maturation time is fixed, when the weight loss of the ham is approximately 30% [22]. So, other methodologies have long been awaited by the Iberian ham industries. The use of image processing to analyse Iberian products is quite recent. Some researches [23, 24, 25] have processed flat images taken by a CCD camera from Iberian ham slices for different purposes. They estimated some parameters in Iberian ham like intramuscular fat content [25] and marbling [23] or classified various types of raw Iberian ham [24]. The obtained results are very encouraging and suggestive to its application for the systematic inspection of Iberian products. However, although Computer Vision is essentially a non-destroying technique, ham pieces must be destroyed to obtain images using these techniques. MRI (Magnetic Resonance Imaging) offers great capabilities to non-invasively look inside the bodies. It is widely used in medical diagnosis and surgery. It provides multiples planes (digital images) of the body or piece. Its application to the Food Technology is still recent and it is confined for researching purposes. Cernadas et al. [26, 28] analyse MRI images of raw and cured Iberian loin to classify genetic varieties of Iberian pigs and to predict the intramuscular fat content. The results are promising to its application to ham. The loin is an uniform and simple muscle, and this is a very important advantage, comparing with the great number and complex distribution of muscles of the ham, being this one a significant drawback. In a previous work [31], classical snakes (mainly the greedy algorithm) have been applied to ham MRI sequences to extract boundaries of biceps muscle. Although the obtained results were nearly satisfactory, the method suffers from robustness for others muscles. This is one of the reasons because of the quadriceps muscle has been studied in this paper too. An enhanced Active Contour approach is proposed, based on the use of potential fields as external force and the improvements of the standard greedy algorithm for taking into account the peculiarities of the particular environment. This new method is applied over a database of specific MRI images from Food Technology, particularly Iberian ham images obtained at four different maturation stages (raw, post-salting, semi-cured and cured ham). Deformable Models are used to achieve the extraction of different muscles (biceps and quadriceps), studying their volume changes during the ripening of Iberian ham. The verification of the presented approach is shown examining these muscles, and the obtained practical results may allow us to design a methodology to optimise the ripening process. 28 A. Caro et al. / Electronic Letters on Computer Vision and Image Analysis 2(1):25-36, 2003 [ ] [ ] dssvEssvEssvEsdssvEsvEE imagecurvcontimage ∫ ∫ ++=+= ))(()())(()())(()())(())(( int γβα 2 Algorithm design A standard Active Contours overview is presented in section 2.1. In section 2.2, some particular problems and algorithmic improvements are presented. The enhanced algorithm is used in conjunction with real MRI images (section 2.3). 2.1 Standard Deformable Models Deformable Models (Active Contours, or Snakes), are curves that can be moved due to the influence of internal and external forces [1]. These forces are defined so that the snake can detect the image objects in which we are interested [29]. Active Contours are defined by an energy function. By minimising this energy function, the contour converges, and the solution is achieved. An Active Contour is represented by a vector, v, which contains all of the n points of the snake. The functional energy of this snake is given by: (1) Eint is the internal energy of the contour. It consists in continuity energy (Econt) plus curvature energy (Ecurv). Eimage represents the proper energy of the image, which is very different from one image to another. α, β and γ are values that can be chosen to control the influence of the three terms [30, 31]. For example, a large value of γ means that the energy image is more significant than the rest. When a discontinuity occurs at a point, α is zero. β is zero in corners of the image (null curvature energy). The algorithm is iterative, and during each iteration, energy of the m neighbours is computed for each one of the n points of the snake. This point is moved to the neighbour having the lowest energy of the neighbourhood. The continuity energy attempts to minimise the distance among points of the snake. The algorithm uses the difference between the average distance among points, d, and the distance between the two points under consideration: d - |vi - vi-1|. The curvature energy could be computed in many forms. We used the expression |vi-1 - 2vi + vi+1|2, which uses the distance between one point and the previous one, and so on. The image energy is a gradient magnitude [17, 18, 32]. At each point in the image, gradient magnitude has a normalised value in 0-255, in order to have the same range as the other energy terms. In our particular case, the points of the image with higher gradient values are located in edges. Therefore, points with small gradient measures are situated in the centre of some image object delimited by edges. The image energy is the only information that the algorithm has about the image on which it is working [32]. The other terms of energy (Econt and Ecurv) in the general equation to minimise are based on distances among points of the snake, but they do not use any specific information of the image. Then, it is extremely relevant to find a good image energy function [17], in order to control the correct evolution of the Active Contour. It is the only way the algorithm has to get information about the image. 2.2 The new approach for Deformable Models The internal forces of Deformable Models are designed to hold the curve together (elasticity forces, i.e. Econt) and to keep it from bending too much (bending forces, i.e. Ecurv). Typically, the external forces are defined as a gradient of a potential function. Both internal and external forces attempt to drive the curve toward the edges (object boundary) or other desired features within an image. Unfortunately, the initial snake often needs to be placed near to the searched border. Furthermore, Active Contours have difficulties A. Caro et al. / Electronic Letters on Computer Vision and Image Analysis 2(1):23-34, 2003 29 progressing into concave boundary. Then, selecting correct external forces that solve these problems is highly recommended. One of the proposed ideas in this work consists in creating potential fields, using them instead of traditional external forces. The purpose of building these potential fields is to move the points of the contours toward the object boundary, not only when they are situated close to the borders, but even when they are not located near to the edges. A traditional potential force cannot attract distant points or either moves them into concave boundary regions, being these two key difficulties with standard Active Contour algorithms. A potential field is developed for solving these problems, and it is presented in this section. Capture range for snakes has been extended, and concave regions could be explored using this new field. These are the main advantages of using this field as an external force for the Active Contour. The potential fields are computed in a two steps algorithm. The algorithm is described as follows: • As a first stage, edge map images are necessary before computing the potential field, in order to determine the object initial boundary. These primary borders will be used to increasingly grow the potential field. − A 7x7 Gausian filter has been used to smooth the images. The filter size is either 13x13 or 15x15. The goal is to smooth the images converting similar textures in homogeneous grey levels, avoiding dissimilarities. A 3x3 Sobel operator is applied, obtaining the edge images. − Although the edge images apparently seem to be almost black (except for edges, which are shown in a light white color), they contain a great variety of data. This extra information is found in dark grey levels, and needs to be equalized to obtain an adequate binary image. The equalisation proccess converts the grey levels of the edges to values close to 255. After that, the images are converted to binary using a threshold. This value is calculated considering the grey level which divides the histogram in two parts: the black color (80% of the total pixels) and the white color (the other 20%). − This bi-level image is used as an edge map to grow the potential field, so removing all the groups of isolated pixels is desirable. These groups of noisy pixels can seriously affect the potential field, producing a local convergence for the snake algorithm (global minimum would not be assure). Eliminating islands of pixels is a remarkable task in the pre-processing stage. A recursive process based on a growing seed is developed for finding islands of pixels with a size (number of pixels) lower than a given value (48 or 96 pixels, depending on the image). Therefore, the original image has been filtered, equalized, converted to binary level and processed to eliminate the undesirable noise, just before the potential field is computed (Figure 1). Figure 1: Obtaining the potential field • As a second step, the potential field is calculated as a degradation (diffusion) of the binary edge map derived from the image. Considering the bi-level image has white edges (level 255) and black background (level 0), the developed algorithm produces a color degradation (potential field) in the background points between points of boundaries, as Figure 2 shows. Filtered image Edge Detection Binary image Edge map image Sobel operator Equalising & converting to binary Removing noisy pixels Original image Gausian Filter Potential field image Computing the potential field 30 A. Caro et al. / Electronic Letters on Computer Vision and Image Analysis 2(1):25-36, 2003 Figure 2: The calculated potential field between two points of boundaries In this way, images containing potential field magnitudes have been calculated. For each point of the image, the potential field is computed, obtaining a new image, with the same dimensions as the original, which contains the potential field value for each one of the image points. Contour initialisation is one of the main problems of the Deformable Models. The snake must be developed to find the object searched for. An automatic algorithm has been developed to place an initial contour inside the images. For its realisation, the potential field image is known. Searching inside the images in order to find the points with the smallest values is required. The key is to distribute all the points of the contour surrounding all those points of the image with smallest potential field values. In this manner, it is ensured that the snake will evolve towards the edges of the object, searching for points with levels of energy smaller than the energy values of the points in the initial snake. While the contour is being deformed another difficulty could arise: some points of the contour could be attracted to the same place and cross over their trajectories (Figure 3.a). This is highly undesirable, because great amounts of nodes situated near by do not have significant information in the recognition task. Moreover, contours with dots that cross over their trajectories (Figure 3.b) would be useless. The goal is to distribute all the nodes of the snake in such a way that they determine the object contour in the best way possible. A procedure has been added to eliminate the nearest knots and aggregate new points between the most distant nodes (Figure 3.c). Figure 3 shows a 7-point contour. Points 3 and 4 cross over their trajectories during the evolution of the curve (Figure 3.a), producing a non-desirable snake (Figure 3.b). The algorithmic improvement remove one of this two points when they are getting closer (Figure 3.c), adding a new point in the middle of the largest segment (between the points 1 and 7 from the initial situation is added a new one, renaming all the points). (a) (b) (c) Figure 3: One of the developed algorithmic improvements A serious effort in the pre-processing stage is necessary to ensure successful object recognition using Deformable Models. The image processing phases (pre-processing stage) could be considered as algorithmic improvements, due to the final program deal with processed images, instead of the original ones. 255 254 253 252 251 250 251 252 253 254 255 250 249 a) Numerical Values b) Grey levels Edge Edge Background (degraded values) 2 1 7 6 5 4 3 2 1 7 6 5 4 3 2 1 7 6 5 4 3 A. Caro et al. / Electronic Letters on Computer Vision and Image Analysis 2(1):23-34, 2003 31 2.3 A practical application: Deformable Models on Iberian ham MRI The evolution study of the Iberian ham muscles during the ripening process could be one of the goals to confirm the practical viability of using the proposed approach. Muscle recognition could be used for determining the fat content and its distribution, as well as for studying how the hams evolve in their maturation process. The presented research is based on MRI sequences of Iberian ham images. One of the images of these sequences is shown in figure 4.a. A technique to recognise the main muscle structures (biceps femoris and quadriceps) is employed. Four Iberian hams have been scanned, in four stages during their ripening time. The images have been acquired using an MRI scan facilitated by the "Infanta Cristina" Hospital in Badajoz (Spain). The MRI volume data set is obtained from sequences of T1 images with a FOV (field-of view) of 120x85 mm and a slice thickness of 2 mm, i.e. a voxel resolution of 0.23x0.20x2 mm. The total number of images of the obtained database is 336 for the biceps femoris, and 448 for the quadriceps muscle. As a previous step, a pre-processing stage is introduced, in order to compute the potential field values (Figure 4.b and 4.c). Therefore, images containing potential field magnitudes have been calculated. In addition, the initial snakes for the central images of the sequence have been previously calculated too (Figure 4.d). When the final snake for this image has been achieved, this final contour is automatically modified, and a scaled version (the same contour, but smaller) of the final snake is selected as the fist contour for the immediately preceding and succeeding images. Once the complete database of images and the initial values of the snakes for these images are set, the application of Active Contours to compute the area of the muscle is needed. The greedy algorithm runs over the central image. The snake is initialised with the computed values, and next, the algorithm finishes after further iterations, and the final snake is reached for this image (Figure 4.e). This snake determines the area of the muscle over the image. The next step is based on applying this final snake for the central image as an initial snake for the following image, as it was previously mentioned. In such a manner, the final snake that could be used as initial for the next image of the sequence is obtained. Similarly, the final snake achieved in the central image could be used as an initial snake for the previous image, and so on. The final step computes areas and volumes for the extracted muscles (Figure 4.f). Calculating the surface of the final obtained snake for each image is possible to determine the volume for the muscle. 3. Practical Results and their Discussion The standard Deformable Models algorithm haven been algorithmically enhanced, and potential fields have been employed as external forces. A new approach has been successfully proved in a practical application, using these two key ideas. The obtained practical results show how the potential fields, used as external forces for Deformable Models, seem to be an acceptable solution for finding patterns (muscles in the proposed practical application). It is not necessary to place the initial snake near to the searched border, and all the difficulties in progressing into concave boundary have been solved using potential fields in conjunction with all the algorithmic improvements. Both biceps and quadriceps muscles have been satisfactorily recognised for most of the images of the database (Figure 5). Therefore, it could be considered as a good enough argument to decide the validation of the proposed algorithm. A comparison of the muscles size (obtained using the proposed technique) during the maturation stages is shown in Figures 6.a and 6.b for the biceps femoris and the quadriceps muscles, respectively. The practical application of the enhanced Deformable Models algorithm shows how the volume reduction of the Iberian ham during its ripening stages. Both new external forces and algorithmic improvements have been successfully proved, reaching suitable results equally in the two studied muscles. 32 A. Caro et al. / Electronic Letters on Computer Vision and Image Analysis 2(1):25-36, 2003 (a) (b) (c) (d) (e) (f) a) Obtaining the original images b) Preprocessing stage: converting the original images into edge map images. c) Obtaining the potential fields from the edge map images. d) Placing the initial snake into the central image of the sequence. e) Greedy algorithm f) Computing areas Figure 4: Algorithm design for the practical application A. Caro et al. / Electronic Letters on Computer Vision and Image Analysis 2(1):23-34, 2003 33 (a) (b) (c) (d) Figure 5: Initial (a) and final (b) snake for the biceps femoris muscle, and initial (c) and final (d) snake for the quadriceps muscle. The results presented in Figure 6 show a size reduction of almost 10% as an average, between the initial stage (raw) and the second one (post-salting), for both muscles. Comparing the post-salting and semi-dry stages, the average decrease is about 20%, and the size reduction produced between the semi-dry and cureddry stages is of nearly 15% as an average, for both muscles. The approximate average ratio is 45% at the end of the maturation process, 21 months after the initial stage, for both biceps femoris and quadriceps muscles. Food Technology specialists have estimated the total weight decrease in the Iberian ham during the same time at 30%. This way, a relationship between the ham weight (30%) and muscle size (45%) could be established for the maturation time, as a first approximation. Thus, a more complete study is necessary. These weight decreases could be caused by the loss of water during the maturation time. Optimal ripening time could not be the same for different Iberian pig hams. By studying the percentage rate of volume during the ripening process, it was possible to predict the optimal maturation moment. So, the new proposed approach could be considered as alternative to the traditional methods, proving not only the validation of the presented technique as another option to the conventional processes, but the appropriate use of potential fields as external forces in Deformable Models, as well as the practical efficiency of the algorithmic improvements.