Intensity Profiles in Active Shape Model

Model-based methods make use of a prior model of what is expected in the image and try to find the best match of model to the data in a new image. The first works described by Cootes et al. showed how to construct the models of a set of deformable objects, called Point Distribution Models (PDM), and how to use them to adapt them to the image [1, 2]. In this section we briefly describe the ASM model and its formal framework, as well as the matching procedure principle.

2.1 Statistical Shape Models

Statistical Shape Models are PDM which represent the shapes according to their main modes of variation independently of their poses in the reference of the image. For any set of model parameters, one can generate an instance of the model and project it into the image frame. Thereby, fitting a PDM model to a new image means find the model parameters that define both the shape and position of the target object.

Given a set of training images for a given object, each object shape is represented by a sequence of n points placed in the same location on the object in each image. The set of points forms a shape vector X such as:

$X=\left\{\left(x_{i}, y_{i}\right)\right\} i=\overline{1, n}$     (1)

If we have N training examples, we generate N shape vectors $X_{j}$. The average shape $\bar{X}$ of the training set is calculated from an iterative procedure such that all the shapes $X_{j}$ are aligned to the tangent space of the $\bar{X}$.

$\bar{X}=\frac{1}{N} \sum_{j=1}^{N} X_{j}$      (2)

Lastly, Principal Component Analysis (PCA) is applied to the set of the aligned vectors $X_{j}$. These vectors $X_{j}$ form a cloud of points in a 2n dimensional space. PCA method is applied to reduce the dimensionality of the data from 2n to something more manageable, by determining the major axes of points cloud. Each axis gives a mode of variation, a way in which the landmark points tend to move together as the shape varies. The approach is summarized as follows:

(1) For each vector X_j, we compute its deviation dX_j from the average shape $\bar{X}$:

$d X_{j}=\left|X_{j}-\bar{X}\right|$      (3)

(2) We compute the shape covariance matrix S:

$S=\frac{1}{N} \sum_{j=1}^{N} d X_{j} d X_{j}^{T}$        (4)

(3) We compute the eigenvectors $\{\varphi\}$ corresponding to the largest eigenvalues l such as:

S. $\varphi=\lambda . S$      (5)

Any shape X (See Eq. (1)) can be approximated by the nearest point (See Eq. (6) in the new space $\{\varphi\}$ of origin $\bar{X}$. A point in this subspace (See Eq. (7)) is defined by a vector b of shape parameters.

$X=\bar{X}+\varphi . b$    (6)

$b=\varphi^{T}(X-\bar{X})$    (7)

By varying b, one can vary the shape X using Eq. (6). The variance of b, across the training set is given by l. By applying limits of $\pm 3 \sqrt{\lambda}$ to the parameter b, one ensures that the shape generated is similar to those in the original training set.

2.2 ASM matching

2.png

Figure 2. Bijection (T) between image frame and model frame

Matching procedure is defined as an iterative approach that allows a reliable comparison between the PDM model and an object of interest in an image. It is based on the change of reference between the image frame and that of the model (See Figure 2), in order to calculate the best pose and model parameters of the target object. In theory, the matching corresponds to an optimization problem of a parameterized fit function between a model instance and image.

Given X_b an instance of model and its variant X_b,pof pose p, and an object Y, the formulation of the principle of the ASM matching is as follows:

Find b and p which optimizes:

$F_{b, p}=\left|Y-X_{b, p}\right|$    (8)

Under the constraints:

$X_{b}=\bar{X}+\varphi . b$     (9)

$X_{b, p}=(\bar{X}+\varphi . b)_{p}$    (10)

This formulation (See Eqns. (8-10)) depends essentially on the choice of the fit function F, the model X and the object Y, whatever the optimization method used to find the optimum. It is the fundamental principle of ASM method whose goal is both to seek a set of shape parameters and improve the fit of X to Y. In principle, the problematic of the ASM method is the same in any dimensions.

In practice, the matching procedure consists of finding all the possible and correct adjustments between the model and the object in order to identify its landmarks and delimit its outline. The standard matching algorithm uses the average shape model to approximately express the shape of target and then matches it to the target object by limiting the variable shape parameters. The basic assumption is that usually the desired landmarks points are located on the strong edges that correspond to points whose intensity gradients are maximized. Precise and strong location of shape points is a complicated and difficult issue in object localization. Improved matching algorithms based on the traditional ASM matching were proposed in the literature. Some works propose to modify the practice of the matching procedure and others propose to speed it up in order to increase its performance. Liao and Wu [4] propose a shape evaluation method and a weighted matching procedure using the evaluation information. Zhao et al. [5] add a process of searching the most similar image to the target object from the training sample set and uses the shape model of the similar image instead of the average shape model to approximately express target object model. Wang et al. [6] evoke the fine grain parallelism and applies it to the matching algorithm and reformulate it as a parallelizable algorithm. The parallel version of matching algorithm is implemented in a multi-core (CPU/GPU) environment. Naoui et al. [7] propose a theoretical framework to implement a distributed and parallel version of ASM and AAM methods.

Several works have adopted the original ASM and they adapted it to their applications.

For example, for color images, 1D-profile is computed in each component of color space. Mahoor et al. [9] devised an approach using a weighted sum of three multivariate Gaussian models for the three components of RGB (Red, Green, and Blue) color space to conceive the 1D-profil. They used a weighted sum of the three Ma-halanobis’s distances corresponding to the three channels of RGB color space as a criterion, in order to find the best matching. They validate their approach by experimenting a database composed of different subjects provided from different sources and other public databases. The approach seems to be partially automated.

For multidimensional images, Josephson et al. [10] have developed a fully automated segmentation system of the medical images in three-dimensional using ASM. 1D-gradient profile along a perpendicular at each surface is built for each landmark. During profile matching, edge detection is performed on a short distance along the normal to the surface to find the new positions of each landmark. The best positions are determined using Mahalanobis distance. The method was experimented on Magnetic Resonance (MR) images of the knee and SPECT images of the brain, without any indication on the implementation of the proposed method. The authors validated their approach that depends strongly on the quality of initial guess.

Tobon-Gomez et al. [11] proposed to build a 3D-intensity model composed of 1D- profiles directly given from real medical (cardiac) images, using medical imaging simulators. A 1D-profile is calculated for each endocardial and epicardial wall by sampling the gradient of the profile intensities along a perpendicular to each mesh of cardiac image. During matching, new positions are obtained by selecting the minimal Mahalanobis distance between sampled profiles and mean profiles of the intensity model. The proposed method was tested on two datasets, one for an automated build of 3D-intensity models and the other for evaluation of their performance. Simulation software was used to generate structures for study. Simulations were run using a computing grid of a cluster of 20 dual-processors. The feasibility of the approach was confirmed for cardiac images. However, the approach was considered difficult to manage, and many parameters were hard to determine.

Although the 1D-profile is a key method that works as well as any, it is also a sensitive technique in some situations. To Base solely on intensity gradients and searching along a perpendicular direction, can cause mapping errors during search process that misguide the estimation of the ASM parameters. In this case, the accuracy of the ASM is severely compromised, resulting in a decreased segmentation performance. Complementary approaches have been proposed to overcome the ASM drawback such as the AAM model [3] and later the CLM model (Constrained Local Model) [12] which is similar to AAM in the sense that it applies the AAM formalism inside a small area surrounding the landmark point. In the same context, Iqtait et al. [13] proposed to use jointly the ASM model and AAM model, and test their performance on one dataset of faces. ASM and AAM are presented in their standard version. One hundred (100) face images are chosen as training set, each marked with 68 points. The experiments conducted show that the number of searching positions has the most primary influence on the location result. They compared the performance between both algorithms with respect to point to point errors and execution time measurements. They conclude that the ASM algorithm locates the points more accurately and faster than the AAM algorithm. The experiments were conducted on Matlab environment without specifying the detail of the implementation.

Although ASM and its complementary approach have contributed a lot to the field of object detection, there are still shortages on real world problems. Other works adopted the ASM strategy but slightly modified in order to compensate the deficiency in the ASM search process.

Seghers et al. [14] proposed to use a spherical intensity profile collected on a sphere centered at each landmark in a 3D image. A statistical intensity model similar to 1D-profile of a 2D image is obtained by estimating the mean and the covariance of features of each landmark point. The similarity function called intensity cost is computed in 3D, similar to that of 2D of ASM. In the search process, a grid is defined around each model point to extract a set of candidate locations. For each candidate point, a search function is computed taking account both initial cost function and shape knowledge. The best candidate is selected if its search function is optimal. The search process was done in a multi-resolution framework. The proposed method was tested and validated for the liver CT (Computed Tomography) images in contrast enhanced. The different operations of the proposed approach have been implemented in Matlab. The approach has consumed a considerable calculation time estimated at twenty minutes.

Nanayakarra et al. [15] developed an automatic segmentation method of breast skin line. They have used intensity gradient information to initial boundary estimation, and morphologic operators to final boundary estimation of breast images. An 1D-gradient profile is used to extract the boundary points and estimate end points on the skin line. The method was tested and validated on many mammograms taken from a mini popular database among mammogram research community.

Labrunie et al. [16] introduced a method for predicting mid-sagittal contours of orofacial articulators from real time MR (Magnetic Resonance) images, using ASM slightly modified. A 1D-profile similar to that of original ASM is built for each point of each articulator at two resolution levels of image. The intensity profile is sampled by interpolation on the points distributed along a normal segment by step of one pixel. The obtained intensity profiles are then categorized in two classes “Contact and No contact”. These classes serve to measure and test the distance between the contour points to the nearby articulators. Each class is divided by a k-means algorithm into subclasses. Each subclass is represented by its average profile. The distances of all profiles at the average profiles were calculated. The classes serve then to determine the new positions of landmark points. The approach was evaluated from a corpus of about 26 minutes of speech of a French speaker at a rate of 55 MR images /s. The efficiency of the presented method was demonstrated by the authors.

Lee et al. [17] presented a method of extraction of facial point features that operates on mobile devices. They proposed to extend 1D-profile to a 2D-profile model. A square region is selected for each landmark. The average of gray-levels of each point within the square is computed. To locate the new locations of each model point, they proposed a similarity function based on the calculation of the difference of two profile matrices. The first matrix represents 2D-profile of a model point and the second matrix represents its sub 2D-profile. The method was implemented using Java and C with Eclipse via the android platform. It was validated on various images from JAFFE dataset, Google search and their own faces. The results obtained showed slightly higher efficiencies in terms of computational time compared to the original version of ASM.

Seghers et al. [18] presented an intensity model constructed by estimating the probability distribution functions of the intensity patterns in an image around each landmark. Thus, Gibbs function is estimated for each landmark individually. The set of intensity models is modeled as a Gaussian distribution. The Mahalanobis distance is used for the intensity models matching. The approach has been validated using hand bone and 3D liver images.

4.2 Modified ASM intensity models

Several works tried to choose better local appearance models completely different from the 1D-Gradient profile, in order to achieve high segmentation accuracy. Some works are inspired by the research work, particularly in the field of artificial intelligence and pattern recognition. Other works have resorted to the use of some robust image matching techniques known in the field of machine vision and robotics.

For example, Van Ginneken et al. [19] proposed both an intensity model composed of optimal local features along a perpendicular to the object contour instead of the normalized derivatives of 1D-profile, and a nonlinear classifier instead of the Mahalanobis distance. Multi-scale Gaussians derivatives of images are computed to describe local image structure. Around each landmark, the first and second moments of a local histogram are extracted. At each resolution, a square region is thus defined in order to extract a features vector. The optimal features are determined by using a selection technique of features and a nonlinear classifier of the k-Nearest Neighbors (KNN- classifier). During search, a considerable set of features along a normal profile is computed and fed to classifier in order to determine if the point is inside or outside the object. The method was experimented by using different types of data, in particular lung images, in order to show the course of all operations and measure the method performance. The method does not seem to be completely automated and, the implementation and its environment are not described.

Li et al. [20] have used steerable filters to extract local edge orientation features. A structure cantered at each landmark is defined by a square grid. For each grid point, a set of features is extracted varying parameters of steerable filters. The structure of local edge at each landmark is thus described by the set of features of all points of the grid. A machine learning algorithm based on AdaBoost algorithm is introduced to construct a classifier for each landmark. During search process, the classifier serves to determine the next move of the landmark point by analyzing its features along the perpendicular to the shape contour, if it is edge or non-edge. The approach was tested on brain images in which the corpus callosum was labelled manually. The approach was validated by comparing the final positions of model points to their correspondents manually labelled, by calculating the distance between them. The approach is not fully automated. The implementation in Matlab is partially described. The training process is off-line. The feature images and the classification have been done on-line. The approach used have consumed more time than the original version of ASM.

Cootes et al. [21] and later Lindner et al. [22] used the Random Forest Regression Voting approach to generate the optimal positions and locating new shape points during search process. For each landmark, a set of features of neighbouring points taken at a random distance is determined. A voting approach is thus applied in a grid over the region of interest to predict the most likely positions to the landmark point, and select thus the best position. A histogram of vote (HOV) is established to define the landmark descriptor. During search, each descriptor predicts one or more positions of the target point. Votes are accumulated in a grid to then select the best position for the landmark. The approach was validated on a range of datasets, face images and medical images.

Ebhotemhen [23] proposed to use the K-Nearest Neighbor (KNN) machine learning in the process of segmentation of medical images in order to improve segmentation accuracy. Haar filters are used as intensity model to extract features of landmarks. KNN is used to learn better positions for each landmark and to classify points around the final points of the search process of ASM. The author validates his approach by processing a set of 86 brain images annotated with 15 points each, showing that machine learning can be used to improve automatic segmentation accuracy of medical images.

Le and Vo [24] suggested to use a model combining Sobel filter and the 2D-profile in the local search process of ASM. Support Vector Machine (SVM) is used to classify and determine the new positions of landmarks. The proposed method was tested and validated on public face images from Denmark databases.

Huang and Hsu [25] proposed a facial feature location method based on active shape model and Gabor filter to reduce the intensity contrast and to enhance edge information. They use firstly 2D Gabor filter to extract the facial features and then to use a square region in the search process to decrease the location error. To locate the facial features, they proposed to use both the Gabor kernels reduction and local feature-based weighted warping method. They tested their approach using JAFFE and Yale [21] face databases under various viewing conditions of pose and illumination. To estimate the performance of their approach, a manual labeling and Viola-Jones face detector were utilized. The results obtained show that their approach is moderately robust to illumination variation. The approach seems not to be completely automated.

Spinczyk and Krasoń [26] authors proposed an automatic liver segmentation using general purpose shape modeling methods. The atlas based segmentation was used as being the simplest shape-based method. Subsequently, the ASM method was applied with optimal features as defined in the study [14]. Lastly, a generalization of classical statistical shape models, the Gaussian Process Morphable Models (GPMM), was used. The preferred method is that of GPMM which is based on the multi-dimensional Gaussian distributions of the shape deformation field. The GPMM are used as a process of generation of candidate points for the location of the model points during search process. The new locations result from the probability distribution of the shape deformation field. Mutual information and sum of square distance were used as similarity measures. 20 CT images of the abdominal cavity were used for the liver segmentation. The obtained results are compared to that dedicated for liver segmentation. The dice similarity was used as a statistical validation metric to evaluate the performance of the used methods. The best results were obtained for the GPMM method.

Zhou et al. [27] proposed to use SIFT (Scale Invariant Feature Transform) descriptors and the gray-level profiles for an automatic search of the landmarks in the face images. A Human face has been represented both by SIFT descriptor and a 1D-gradient profile. Different face data have been used for experiments, using the face detector of Viola-Jones and the STASM software. The proposed approach has shown an increased performance than the standard approach of ASM but worse than the STASM software.

Zhou et al. [28] proposed to use the Patterns of Oriented Edge Magnitudes (POEM) descriptor to represent the local appearances of the landmarks instead of pixel intensity values. A gradient image is firstly computed to determine the magnitudes matrix and directions matrix. For each pixel, a features vector is then computed composed of its magnitude and a set of magnitudes of region surrounding it. Similarity function is thus the difference of gradient magnitudes. A square region cantered at each landmark is then considered to compute finally its local appearance pattern. A set of POEM histograms is thus computed. The average histogram of each landmark acts as a local appearance model. The computing of similarity between histograms is determined using the Chi square distance. The approach was validated by using a considerable set of face images under various poses and illuminations. The implementation of the approach is not described and the approach but seems also not to be completely automated.

Milborrow et al. proposed a Histogram Array Transform (HAT) descriptor which is a simplified form of SIFT descriptor [29, 30]. HAT descriptor is unrotated SIFT descriptor with a fixed scale. Decision trees are used to generate the model for a landmark that predicts goodness-of-fit as a function of the elements of the descriptor. A Multivariate Adaptive Regression Splines (MARS) is used for descriptor matching. The descriptor has been implemented using OpenCV (Open Computer Vision) and OpenMP (Open Multi-Processing) to reduce its computational load. The approach has been experimented on facial images for validating.

Antonakos et al. [31] proposed to use the dense appearance features images for both Lucas-Kanade alignment algorithm and AAM fitting algorithm. Several descriptors have been used to extract image features mainly Histogram of Oriented Gradients (HOG), SIFT and Local Binary Patterns (LBP). Extracting features from image and warping improves significantly the approach performance and decreases its computational complexity. The optimization technique used is the gradient descent Inverse Compositional. The approach was tested on a set of face images downloaded from the web captured in totally unconstrained conditions. The presented experiments prove that HOG and SIFT are the most powerful descriptors. The implementation of the proposed approach is not described.

Medley et al. [8] proposed a methodology composed of two detection methods of the reliable observations points called ASM-FTT (ASM-Fixed Texture Templates) and ASM-VTT (ASM-Variable Texture Templates) that are used in the ASM framework. The two approaches use a rectangular region sampled around each landmark point conforming to a features template defined over training set. In ASM-FTT, the template is fixed and it is characterized by a mean texture of the region surrounding each landmark point. In ASM-VTT, the template is formulated as the CLM model [12]. It is variable and it is characterized by a linear combination of main variation modes obtained by the PCA (Principal Component Analysis) analysis of local texture surrounding each landmark point. During search process, the same templates are used to define a search region which is compared to the templates via a specific correlation function. The methodology was applied to facial images and medical images. The authors have compared the performance of their methodology against three detectors based on classical ASM edge detector, HOG detector and SIFT detector. The obtained results show that the proposed approach is better than the other three approaches. The implementation of the proposed approach is not described.

In this paper, we attempted to provide a comprehensive overview of several researches on intensity models proposed in the literature as the alternatives to ASM 1D-profile. For this purpose, the formal framework of intensity model is described, followed by an expanded formulation of the ASM matching including profile matching. We have taken a deep survey for understanding the proposed methods. The various proposals along with their advantages and disadvantages are discussed in this paper. The studies presented in this paper provide a basis for conducting our project future in this area.