1 Introduction

Statistical shape models (SSMs) have several applications including shape deformation analysis [1] and shape reconstruction [2]. Establishing correct correspondences between the points of two shapes is a crucial task in developing an SSM, and three types of methods have been proposed [3].

In the 1st group, one shape is registered to the other using a rigid/non-rigid registration scheme. Then, one assigns pairs of the nearest points as corresponding. These techniques are not suitable for non-rigid bodies. Non-rigid multimodality registration is also sensitive to intensity variations [4].

In the 2nd group, one does an exhaustive search on all landmarks which is a tedious task and sometimes impossible [3, 4].

The 3rd group uses iterative methods to estimate transformation function and to resolve point correspondences in an (expectation maximization) EM-like [5] approach. Several examples are the ICP (iterative closest point) [6] and its variants, the TPS-RPM (thin plate spline robust point matching) [3] and CPD (coherent point drift) [7]. This class of algorithms has the best performance among others. However, they do not consider morphological/anatomical characteristics of shapes. Involving shape geometry in building an SSM is important especially in cases of highly deformable bodies such as human liver.

2 Previous works

The TPS-RPM method uses the EM scheme to find fuzzy correspondences between shape points. It employs a Gaussian mixture and assigns the set of moving points as the center of the Gaussians. In the E-step, a fuzzy correspondence is assigned to the set of reference points. In the M-step, the transformation matrix is estimated to transfer the moving points to new positions. This method is sensitive to parameter setting.

The CPD method uses Gaussian mixture and the EM algorithm to iteratively register a moving shape to a reference one. In contrast to the TPS-RPM, it applies a coherency constraint on shape movement that preserves shape topology during registration. Compared to the TPS-RPM, the sensitivity of the CPD method to its parameters is less, and it is faster and more robust.

The minimum description length (MDL) algorithm maps 3D reference and moving shapes onto a sphere [8]. It registers the two shapes by displacement of their points on the sphere using minimization of the model compactness. The method has large computational cost, and its convergence is not guaranteed. Heimann et al. [9] and Xu et al. [10] proposed solutions for non-uniform distribution of points. However, the problems of runtime and convergence remained.

The above methods do not consider natural/anatomical structures of shapes. Some researchers divided a shape into semantic divisions and registered each division individually [11]. Corresponding to each division, they used a Gaussian component. Manually splitting a 3D shape is not a simple task, and employing a rigid transform function is not suitable for soft tissues too. In [12], the authors employed a sequential approach to estimate number of Gaussian components. They employed a smoother objective function and a smaller search space. The algorithm was sensitive to Gaussian parameters.

Some researchers used perception rules to split a shape into semantic parts. Some of these rules have been verified in psychological studies of human being including minima rule [13], short-cut rule [14] and convexity rule [15, 16]. The minima rule split a shape based on loci of negative minima of the curves that form a shape. The short-cut rule tries to minimize cut lengths. The convexity rule emphasizes on convexity of a shape to split it into parts. Ma et al. [17] introduced a new rule called “Part-Similarity rule” to distinguish similar parts of a body and combined it with convexity rule to split a shape. Compared with other methods, their results were closer to human perception. However, the outcomes were not acceptable with regard to curved branches and resulted in extra parts.

Three-dimensional extensions of the above methods are not straightforward. For medical objects, anatomical properties should be considered instead of structural characteristics. Okada et al. [18] divided a human liver shape into sections to improve accuracy of segmentation. Lamecker et al. [19] manually divided the surface of a liver into four patches. Due to the large shape variations, these patches are not easily distinguishable.

Anatomically, a physician divides human liver into four lobes: right, left, caudate and quadrate [20]. In this paper, we propose a new shape model which considers anatomical characteristics of liver. One used the bifurcations of portal veins to divide liver into left and right lobes. Individual models are built for each lobe and the complete hepatic model is the augmented submodels. Our main innovations are to explicitly deal with anatomical structures of the tissue, optimization and conscious choice of registration parameters, decreasing computational cost, and developing a robust algorithm. In Sect. 3, we describe the proposed method. We present the results in Sect. 4 and discuss them in Sect. 5. Section 6 concludes the paper.

3 Proposed method

The flowchart of our method has two branches (Fig. 1): The left column describes splitting a liver into anatomical divisions, and the right column explains how we build an SSM for each lobe.

Fig. 1
figure 1

The flowchart of the proposed method. The left column describes splitting a liver into anatomical divisions. The right column explains how an SSM is built for each lobe

Full size image

3.1 Splitting a liver into its left and right lobes

In an earlier research, we built a single model for a liver volume [21]. Consider a liver with a small left lobe that is to be registered on a liver with a large left lobe. In such a case, some points on the right lobe of the first liver are erroneously assigned to the left lobe points of the second liver. Therefore, considering separate models for left and right lobes increases accuracy of the model. A novelty of our method is to use anatomical landmarks to divide a liver into two parts and constructing individual models for a part. A physician divides the hepatic parenchyma into left, right, caudate, and quadrate lobes. Due to small volumes of caudate and quadrate lobes compared to left/right lobes, we do not consider them when partitioning a liver.

Since separate branches of vessels feed a lobe, we use bifurcation of portal veins that are visible in 2nd phase images to divide the gland into two parts (Fig. 2a). To enhance portal veins more, we use the multiscale filter proposed by Frangi et al. [22].

Fig. 2
figure 2

a Dividing a liver into left and right lobes. b The two lobe volumes

Full size image

We segment and extract the skeleton of the enhanced veins based on the method of Lee et al. [23]. Using the skeletons of the portal veins, we use graph analysis to distinguish left and right branches of the vessels. Based on its distance to the nearest vascular branches, each voxel is labeled as either left or right lobe (Fig. 2b). In a case where the contrast between vessels and the liver tissue was not enough, the results of vessel enhancement and skeletonization were not acceptable. A physician manually divided a liver using maximum intensity projection (MIP) of the axial view. A plane was fitted to branching place of portal veins which split the gland into left and right lobes.

3.2 Modified CPD

Since the surface of a segmented liver is not smooth, we employ a \(3 \times 3 \times 3\) smoothing filter. The liver images are zero-padded to keep the image size unchanged.

Each lobe is then represented by a mesh using the marching cube algorithm [24]. We sample liver shapes by 1000 points according to our previous work [21]. Regarding the voxel dimensions \((0.625 \times 0.625 \times 1.25 \, \hbox {mm}^{3})\), the minimum distance between mesh points cannot be less than 0.625 mm. In other words, the minimum surface of a mesh cannot be less than \(0.195\, \text{ mm }^{2}\) (\(0.625 \times 0.625/2\)). We built meshes of all training shapes with 500, 1000, and 2000 points and measured the least surface of the meshes. For the shapes sampled by 2000 points, the least mesh surface of some training shapes were less than \(0.195\, \text{ mm }^{2}\). It means that some voxels are sampled with at least two points which is not meaningful and it just increases computational time. On the other hand, the least mesh surface of some shapes sampled by 500 points was bigger than \(0.195\, \text{ mm }^{2}\) which may ignore some critical parts of a liver. However, if we sample a liver shape by 1000 points, mesh surfaces will be of the proper sizes. After splitting a liver, we represent use the larger right lobe by 601 points to and the smaller left lobe by 401. Next, we use the modified CPD algorithm to set up point correspondences.

The modified CPD is another novelty in our method to build statistical models of a shape with large variations. The CPD method simultaneously finds a non-rigid transformation matrix and point correspondences. It imposes a motion coherence constraint [25] on the velocity field of point movements which enforces the neighboring points to move coherently. This preserves shape topology during registration process. It considers registration of two point sets as a problem of estimating the probability density of one point-set using another point-set density. It achieves this goal by maximizing the posterior probability or maximizing the likelihood function equivalently. To do this, the points of the moving mesh (M points) are considered as centers of a Gaussian mixture and they are registered to the fixed mesh points (N points). Considering \(Y_0 \) as the initial position of the centers, new positions of the template mesh are obtained by Eq. 1.

$$\begin{aligned} {{\varvec{Y}}}={{\varvec{v}}}\left( {{{\varvec{Y}}}_{{\varvec{0}}}} \right) +{{\varvec{Y}}}_{{\varvec{0}}} \end{aligned}$$
(1)

In Eq. 1, v is a continuous velocity field of template point movements. Using the Bayes theorem, we calculate the posterior probability and the likelihood function of moving points Y by Eq. 2 and Eq. 3, respectively.

$$\begin{aligned} p\left( {{{\varvec{Y}}}|{{\varvec{X}}}} \right)= & {} \frac{p\left( {{{\varvec{X}}}|{{\varvec{Y}}}} \right) p\left( {{\varvec{Y}}} \right) }{p\left( {{\varvec{X}}} \right) } \end{aligned}$$
(2)
$$\begin{aligned} p\left( {{{\varvec{X}}}|{{\varvec{Y}}}} \right)= & {} \mathop \sum \limits _{m=1}^M p\left( {{{\varvec{X}}}|y_m } \right) =\mathop \prod \limits _{n=1}^N \mathop \sum \limits _{m=1}^M p(x_n |y_m )\nonumber \\= & {} \mathop \prod \limits _{n=1}^N \mathop \sum \limits _{m=1}^M e^{-\frac{1}{2}\left( {\left\| \frac{x_n -y_m }{\sigma }\right\| ^{2}} \right) } \end{aligned}$$
(3)

In Eq. 2, \(p\left( {{\varvec{X}}} \right) \) and \(p\left( {{\varvec{Y}}} \right) \) are prior probability functions of the reference and template shapes respectively. In Eq. 3, variances of the Gaussian components ( \(\sigma \)) are equal. In order to impose a smooth motion constraint, the prior probability of moving mesh is defined in Eq. 4.

$$\begin{aligned} p\left( {{\varvec{Y}}} \right) =e^{-\frac{\lambda }{2}\phi \left( {\varvec{Y}} \right) } \end{aligned}$$
(4)

In Eq. 4, \(\lambda \) is a weighting constant and \(\phi \left( {{\varvec{Y}}} \right) \) is a function which regularizes motion smoothness. Assuming linearly independence and using minus log-likelihood, Eq. 4 is rewritten as Eq. 5.

$$\begin{aligned} -\log \left( {p\left( {{{\varvec{Y}}}|{{\varvec{X}}}} \right) } \right)= & {} -\log \left( {p\left( {{{\varvec{X}}}|{{\varvec{Y}}}} \right) } \right) -\log \left( {p\left( {{\varvec{Y}}} \right) } \right) \nonumber \\&+\log \left( {p\left( {{\varvec{X}}} \right) } \right) \end{aligned}$$
(5)

By omitting independent parts from Y and substituting Eqs. 3 and 4 with Eq. 5, we write the objective function as Eq. 6.

$$\begin{aligned} E\left( {{\varvec{Y}}} \right)= & {} -\mathop \sum \limits _{n=1}^N \log \mathop \sum \limits _{m=1}^M e^{-\frac{1}{2}\left( {\left\| \frac{x_n -y_m }{\sigma }\right\| ^{2}} \right) }-\left( {-\frac{\lambda }{2}\phi \left( {{\varvec{Y}}} \right) } \right) \end{aligned}$$
(6)

Minimizing the objective function leads to minimizing the fixed and moving point distances which is equivalent to maximizing the posterior probability of the moving mesh.

We restrict the velocity field of the moving points \({{\varvec{Y}}}\) to be smooth. A smooth function has less energy in high frequencies. Thus, we obtain a smooth function through multiplying its frequency transform by a high-pass Gaussian filter or equivalently dividing by a low-pass Gaussian filter (Eq. 7).

$$\begin{aligned} \phi \left( {{\varvec{v}}} \right) = \int \frac{\left| {\tilde{{{\varvec{v}}}} \left( s \right) } \right| ^{2}}{\tilde{G}}\mathrm{d}s \end{aligned}$$
(7)

In Eq. 7, \(\tilde{{{\varvec{v}}}} \) is the Fourier transform of the velocity field and \(\tilde{G}\) is a symmetric, positive-definite and low-pass Gaussian filter that becomes smaller as \(\left| {\left| s \right| } \right| \rightarrow \infty \). By putting Eq. 7 back into Eq. 6, we write the objective function as Eq. 8.

$$\begin{aligned} E\left( \tilde{{{\varvec{v}}}}\right)= & {} -\mathop \sum \limits _{n=1}^N \log \mathop \sum \limits _{m=1}^M e^{-\frac{1}{2}\left( \left\| {\frac{x_n -y_m }{\sigma }}\right\| ^{2} \right) }\nonumber \\&+\frac{\lambda }{2}\int \frac{\left| {\tilde{{{\varvec{v}}}} \left( s \right) } \right| ^{2}}{\tilde{G}}\mathrm{d}s \end{aligned}$$
(8)

Minimizing Eq. 8 leads to minimizing the high-frequency contents of the point movement function which causes the movements to be smooth. By substituting Eq. 1 in Eq. 8 and calculating its derivation with respect to \({{\varvec{v}}}\), it can be shown that the velocity function which minimizes Eq. 8 is rewritten as Eq. 9.

$$\begin{aligned} {{\varvec{v}}}\left( z \right) =\mathop \sum \limits _{m=1}^M w_m {{\varvec{G}}}\left( {z-y_{0m} } \right) \end{aligned}$$
(9)

In Eq. 9, \(w_m \) is a weighting factor and G is a Gaussian mixture kernel which is different from the Gaussian mixture of points Y. This kernel goes to zero as \(\Vert s \Vert \rightarrow \infty \) which satisfies the velocity field smoothness. Also, the smoothness of the velocity function can be controlled by tuning parameters of the Gaussian kernel. By choosing a Gaussian kernel for the velocity field, Eq. 8 becomes similar to MCT (Motion Coherence Theory) [25] as well. The second term of Eq. 8 is equal to a weighted sum of all orders of the squared derivations of the velocity field (Eq. 10).

$$\begin{aligned} \frac{\lambda }{2}\int \frac{\left| {\tilde{{{\varvec{v}}}}\left( s \right) } \right| ^{2}}{\tilde{G}}\mathrm{d}s\rightarrow \frac{\lambda }{2}\int \mathop \sum \limits _{m=1}^\infty \frac{\beta ^{2m}}{m!2^{m}}\left( {D^{m}{{\varvec{v}}}} \right) ^{2} \end{aligned}$$
(10)

In Eq. 10, D is the derivative operator defined in Eqs. 11 and 12.

$$\begin{aligned} D^{2m}{{\varvec{v}}}= & {} \nabla ^{2m}{{\varvec{v}}}\end{aligned}$$
(11)
$$\begin{aligned} D^{2m+1}{{\varvec{v}}}= & {} \nabla \left( {\nabla ^{2m}{{\varvec{v}}}} \right) \end{aligned}$$
(12)

By substituting Eq. 10 for Eq. 8, the energy function is rewritten as Eq. 13.

$$\begin{aligned} E\left( {{\varvec{W}}} \right)= & {} -\mathop \sum \limits _{n=1}^N \log \mathop \sum \limits _{m=1}^M e^{-\frac{1}{2}\left( \left\| {\frac{x_n -y_{0m} -\mathop \sum \nolimits _{k=1}^M w_k {{\varvec{G}}}\left( {y_{0k} -y_{0m} } \right) }{\sigma }}\right\| ^{2} \right) }\nonumber \\&+\frac{\lambda }{2}tr\left( {{{\varvec{W}}}^{T}{{\varvec{G}}}{{\varvec{W}}}}\right) \end{aligned}$$
(13)

In Eq. 13, \({{\varvec{W}}}\) is the matrix of Gaussian kernel weights of velocity field and \({{\varvec{G}}}\) is a symmetric square matrix. We calculate an element of \({{\varvec{G}}}\) by Eq. 14.

$$\begin{aligned} \hbox {g}_{\mathrm{ij}} =\hbox {e}^{-\frac{1}{2}\left\| \frac{{\mathrm{y}}_{0{\mathrm{i}}} -{\mathrm{y}}_{0{\mathrm{j}}}}{\upbeta }\right\| ^{2}} \end{aligned}$$
(14)

Each element of \({{\varvec{G}}}\) has a value between 0 and 1. In Eq. 14, \(\beta \) is the effective radius of each Gaussian component with the center of \(\hbox {y}_{0\mathrm{i}} \) and it determines the number of neighboring points of \(\hbox {y}_{0\mathrm{i}} \) which are imposed to move coherently. By utilizing the EM algorithm, an upper bound for Eq. 13 can be found in the form of Eq. 15. Minimizing Eq. 15 leads to minimization of Eq. 13.

$$\begin{aligned} Q\left( {{\varvec{W}}} \right)= & {} \mathop \sum \limits _{n=1}^N \mathop \sum \limits _{m=1}^M {{\varvec{P}}}^{\mathrm{old}}\left( {m|x_n} \right) \frac{\left\| x_n -y_{0m} -{{\varvec{G}}}\left( {m,.} \right) {{\varvec{W}}}\right\| ^{2}}{2\sigma ^{2}}\nonumber \\&+\frac{\lambda }{2}tr\left( {{{\varvec{W}}}^{T}{{\varvec{G}}}{{\varvec{W}}}} \right) \end{aligned}$$
(15)

In Eq. 15, \(G\left( {m,.} \right) \) is the \(m\mathrm{th}\) row of the matrix \({{\varvec{G}}}\) and \({{\varvec{P}}}^{\mathrm{old}}\) is the posterior probability matrix which is calculated from current places of the reference points with respect to the Gaussian centers. We obtain an element of \({{\varvec{P}}}^{\mathrm{old}}\) using Eq. 16.

$$\begin{aligned} p_{mn} =e^{-\frac{1}{2}\frac{y_m^{\mathrm{old}} -x_n }{\sigma }^{2}}\Bigg /\left( {\frac{\left( {2\pi \sigma ^{2}} \right) ^{\frac{d}{2}}}{\alpha }+\mathop \sum \limits _{m=1}^M e^{-\frac{1}{2}\frac{y_m^{\mathrm{old}} -x_n }{\sigma }^{2}}} \right) \end{aligned}$$
(16)

In Eq. 16, \(\hbox {y}_{\mathrm{m}}^{\mathrm{old}} \) is the current location of a Gaussian center. A uniform distribution is included in the denominator of the \(p_{mn} \) to model noise and outliers. Regarding the uniform distribution, d is the dimension of the space and \(\alpha \) determines the effect of the uniform distribution in \(p_{mn} \).

In order to minimize the energy function, we calculate the derivation of Eq. 15 with respect to W set it to zero (Eq. 17).

$$\begin{aligned} \left\{ {\left( {diag\left( {{{\varvec{P}}1}} \right) } \right) {{\varvec{G}}}+\lambda \sigma ^{2}{{\varvec{I}}}} \right\} {{\varvec{W}}}={{\varvec{PX}}}-diag\left( {{{\varvec{P}}1}} \right) {{\varvec{Y}}}_{\varvec{0}} \end{aligned}$$
(17)

In Eq. 17, \({{\varvec{P}}1}\) is the posterior probability matrix with a column of ones and diag(.) is a diagonal matrix. Solving Eq. 17 for \({{\varvec{W}}}\) is performed in the M-step and calculating the posterior probability matrix \({{\varvec{P}}}\) is done in the E-step of the EM algorithm. If the EM algorithm is converged, the template points will be moved to new locations using Eq. 18.

$$\begin{aligned} {{\varvec{Y}}}={{\varvec{Y}}}_{{\varvec{0}}} +{{\varvec{GW}}} \end{aligned}$$
(18)

Then, we reduce the coverage of the mixture components (\(\sigma \)) by a deterministic annealing strategy [21] (Eq. 19).

$$\begin{aligned} \sigma _{\mathrm{new}} =\sigma _{\mathrm{old}} \times r \end{aligned}$$
(19)

In Eq. 19, r is the annealing factor in the 0.93–0.97 range. After reducing \(\sigma \), the EM algorithm is repeated. The annealing scheme of \(\sigma \) is continued until each Gaussian component covers a single point. This leads to a one-to-one correspondence between the reference and template point sets. The steps involved in the modified CPD method are shown using Algorithm 1.

Algorithm 1

Finding corresponding points between two shapes.

Inputs: Reference shape vector \({{\varvec{X}}}\), moving shape vector \({{\varvec{Y}}}_{\varvec{0}} \).

Step 1. Initialize parameters \(\beta =1.87,\sigma =1,\lambda =2,r=0.95\).

Step 2. Construct elements of the \({{\varvec{G}}}\) matrix using Eq. 14.

Step 3. Update correspondence matrix \({{\varvec{P}}}\) using Eq. 16.

Step 4. Solve for \({{\varvec{W}}}\) in Eq. 17.

Step 5. Update moving shape points using \({{\varvec{Y}}}={{\varvec{Y}}}_{\varvec{0}} +{{\varvec{GW}}}\).

Step 6. If \(\sigma >0.028\) then

            Update \(\sigma \) using \(\sigma =\sigma _{\mathrm{old}} \times r\).

         Goto Step 3

      End

Output: Registered shape vector \({{\varvec{Y}}}\) with points corresponding to the reference shape.

3.3 Free parameters

A novelty in our method is conscious selections of non-rigid registration parameters. The free parameters of the CPD algorithm are\(\sigma \), \(\lambda \), and \(\beta \). In Eq. 15, the parameter \(\lambda \) compromises between the point registration and the motion smoothness and we set it to 2. Thus, both parts of the Eq. 15 have the same effect on the objective function. The parameter \(\beta \) in \({{\varvec{G}}}\) (Eq. 14) regularizes interactions among the points in Y and determines that number of neighboring points in Y which are restricted to move together coherently. A small value of \(\beta \) leads to a local transformation, while a large value results in a rigid transformation. We set \(\beta \) to 1.87 so that all elements of \({{\varvec{G}}}\) are larger than 0.36. Consider the effective range of a Gaussian as (mean ± standard deviation) the standard deviation is 0.36 of its maximum value. Thus, the farthest points in \({{\varvec{Y}}}\) (Gaussian centroids) have a negligible effect on each other, and thus topology of the moving shape is preserved during the registration.

The parameter \(\sigma \) in Eq. 15 is the standard deviation of Gaussian components. It compromises between point registration accuracy and motion smoothness. We decrease this parameter by a constant factor (between 0.93 and 0.97) during registration using the Deterministic Annealing strategy. Since we normalize the shapes before registration, we set the initial value of the parameter to 1. Thus, a point in \({{\varvec{X}}}\) corresponds to any point in \({{\varvec{Y}}}\) at the start of the process. We also set the annealing factor to 0.95.

Due to the complexity of liver shapes, if we decrease the parameter \(\sigma \) less than a threshold, some points in \({{\varvec{X}}}\) may fall far from the Gaussian contours. The transformation matrix is therefore calculated incorrectly and the Gaussian centers are moved to wrong positions. We empirically found that the threshold value for sigma is 0.028. It is equivalent to 70 iterations of the algorithm according to Eqs. 20 and 21.

$$\begin{aligned} {\upsigma }_{\mathrm{final}}= & {} {\upsigma }_{\mathrm{init}} \times \hbox {r}^{\mathrm{n}}\end{aligned}$$
(20)
$$\begin{aligned} \hbox {n}= & {} \frac{\ln \frac{\upsigma _{\mathrm{final}}}{\upsigma _{\mathrm{init}}}}{\ln \hbox {r}} \end{aligned}$$
(21)

Proper selection of the final value of \(\sigma \) prevents divergence of the algorithm and helps to develop a robust technique.

3.4 Construction of the shape model

After finding corresponding points, we convert a shape in the training set to a vector and normalize it \((\left| {{\varvec{X}}} \right| =1)\) (Eq. 22).

$$\begin{aligned} \left[ {{\begin{array}{lll} {x_1 }&{} {y_1 }&{} {z_1 } \\ \vdots &{} \vdots &{} \vdots \\ {x_m }&{} {y_m }&{} {z_m } \\ \end{array} }} \right] \rightarrow {{\varvec{X}}}=\left( {x_1 ,y_1 ,z_1 ,\ldots .,x_m ,y_m ,z_m } \right) ^{T}\nonumber \\ \end{aligned}$$
(22)

In Eq. 22, m is the number of shape points. We align the normalized shapes using Generalized Procrustes Analysis and calculate the mean shape \((\bar{{{\varvec{X}}}})\) by Eq. 23.

$$\begin{aligned} \bar{{{\varvec{X}}}}=\frac{1}{S}\mathop \sum \limits _{i=1}^S {{\varvec{X}}}_i \end{aligned}$$
(23)

In Eq. 23, S is the number of shapes in the training set. Next, we calculate the covariance matrix corresponding to the training shapes \(({{\varvec{C}}})\) by Eq. 24.

$$\begin{aligned} {{\varvec{C}}}=\frac{1}{S-1}\mathop \sum \limits _{i=1}^S \left( {{{\varvec{X}}}_{\varvec{i}} -\bar{{{\varvec{X}}}}} \right) \left( {{{\varvec{X}}}_{\varvec{i}} -\bar{{{\varvec{X}}}}} \right) ^{T} \end{aligned}$$
(24)

If the eigenvalues of \({{\varvec{C}}}\) are sorted in the descending order, we reconstruct a valid shape using a linear combination of the mean shape and the eigenvalues (Eq. 25).

$$\begin{aligned} {{\varvec{X}}}\approx \bar{{{\varvec{X}}}}+{\varvec{\varPsi }} {{\varvec{b}}} \end{aligned}$$
(25)

In Eq. 25, \({\varvec{\varPsi }} \) is the eigenvector matrix corresponding to the ordered eigenvalues and b is a parameter vector.

4 Results

4.1 Dataset

We employed the second phase of 30 computed tomography images of abdominal cavity from 16 males and 14 females in the 20–75 age range. The images were stored in 12-bit DICOM format of \(512\times 512\times 159\) pixels with a pixel size of \(0.625\times 0.625\times 1.25 \hbox { mm}^{3}\). The images were captured at Osaka University Hospital, and a radiology specialist manually segmented the livers.

We implemented the codes in MATLAB environment and ran on a personal computer with windows 8.1 operating system, AMD-fx4100 3.6 GHz CPU and 8 GB of dynamic RAM.

Regarding the runtime of our method, it took approximately 16 and 31 s to find corresponding points of the left and right lobes, respectively. However, it took about 68 s to process a complete liver. Regarding computational cost, our anatomical decomposition technique is therefore superior to traditional methods. The time complexity of our algorithm is O(N) where N is the number of the input shape points.

4.2 Evaluation measures

We used Compactness, Generalization ability, and Specificity metrics [14] to evaluate the proposed shape model.

The compactness of a model is the number of modes that are required to reconstruct a valid shape (Eq. 26). A compact model uses fewer modes to reconstruct a shape.

$$\begin{aligned} C=\frac{\mathop \sum \nolimits _{i=1}^m \lambda _i }{\mathop \sum \nolimits _{i=1}^{Nd} \lambda _i } \end{aligned}$$
(26)

In Eq. 26, \(\lambda _i s\) are eigenvalues of the covariance matrix (Eq. 24) that are sorted in the descending order, M is the total number of the modes, N is the number of points and d is the shape dimension. The number of required modes (m) is selected such that C reaches a value between 0.9 and 0.98.

Generalization is the ability of a model to reconstruct training and unseen valid shapes. It evaluates over-fitting of the model with respect to the training set. The leave-one-out method is employed to calculate this metric for all training images. The mean value of reconstruction errors is considered as the generalization ability of the model (Eq. 27).

$$\begin{aligned} G\left( m \right)= & {} \frac{1}{M}\mathop \sum \limits _{i=1}^M \left\| {{\varvec{x}}}_i -{{\varvec{x}}}_i^{\prime } \left( m \right) \right\| ,\nonumber \\ {{\varvec{x}}}_i^{\prime }\left( m \right)= & {} \bar{{{\varvec{X}}}}+\mathop \sum \limits _{i=1}^m {\varvec{\varPsi }} _{i} b_{i} \end{aligned}$$
(27)

In Eq. 27, \({{\varvec{x}}}_i \) is the leftout shape, \({{\varvec{x}}}_i^{\prime }\left( m \right) \) is the reconstructed shape using m modes, \({\varvec{\varPsi }} _i \) is the ith eigenvector, \(b_i \) is the ith shape parameter, and M is the number of training shapes. The reconstructed shape (\(x_i'(m)\)) is a function of m (number of modes) and the Generalization ability is a function of m as well.

A model is specific if it represents only valid shapes. In other words, any shape that is created by the model should be similar to the training set. To compute this measure, we created 1000 random shapes using random shape vectors \((\tilde{{{\varvec{b}}}_A } ,1\le A\le 1000)\). We constrained the shape vectors in \(\left[ {-\sqrt{2}\lambda ,+\sqrt{2}\lambda } \right] \) range. The minimum distance of a random shape from the training images was calculated in the allowable shape domain (ASD) space. The mean of these distances is the specificity measure (Eq. 28).

$$\begin{aligned} S\left( m \right)= & {} \frac{1}{N}\mathop \sum \limits _{A=1}^N \mathop {\min }\limits _i \left\| {{\varvec{y}}}_A \left( m \right) -{{\varvec{x}}}_i \right\| ,\nonumber \\ \mathbf{y}_A \left( m \right)= & {} \bar{{{\varvec{X}}}}+\mathop \sum \limits _{i=1}^m \Psi _{i} b_{iA} \end{aligned}$$
(28)

In Eq. 28, \({{\varvec{y}}}_A \) is a randomly generated shape, N is the number of random shapes, and \({{\varvec{x}}}_i \) is a training shape. The Specificity is a function of m (the number of modes) as well.

4.3 Evaluation of the left and right lobes

The models of the left and right lobes were compared with the complete liver model using compactness, generalization, and specificity. We compared the results qualitatively too (Fig. 3).

The compactness of a complete liver, left lobe and right lobe models are 18, 18 and 16 respectively.

Fig. 3
figure 3

Top row A typical complete liver. Middle row Left lobe. Bottom row Right lobe. Left column Before registration. Middle and right columns After registration. The reference shape is shown in lower opacity. Warm/cold colors are larger/smaller distances respectively

Full size image
Fig. 4
figure 4

Representation of a complex shape by a single model makes the corresponding mesh to be non-uniform

Full size image
Table 1 Comparison of compactness, generalization, and specificity of left/right lobe models with the complete liver model
Full size table

We performed experiments with the MDL and the TPS-RPM algorithms using our available dataset. Regarding the run-time of the code, our method took about 1400 s to prepare a model while the MDL method took more than 3600 s to do the task. Our method is more robust compared to the MDL as well. With respect to the TPS-RPM algorithm, our method improved the mean Specificity of the right lobe by 0.09 and the Compactness of the model by two less modes.

5 Discussion

In this paper, we built individual models for left and right lobes. It prevents the surface of a liver to be represented by a non-uniform mesh. In Fig. 4, a typical shape of a liver was represented by a single model using the MDL method. As it is seen, some parts of the left lobe are not covered completely. This happens since the modes of variation corresponding to the right lobe control the left modes as well.

Based on our previous research [21], we used the modified CPD to build left and right lobe models. Regarding the results shown in Fig. 3, the moving liver shape is clearly different from the reference shape. The left lobe of the moving shape is smaller than that of the reference shape. However, the left and right lobes of the moving liver were registered to the reference liver well.

The results of the compactness reveal that the right lobe model with 16 modes is more compact compared to the left lobe and complete liver models. This means that right lobes have simpler shapes compared with the left lobe and a complete liver.

The generalization index (Table 1) shows that the complete liver model had the least reconstruction error and the reconstruction error of the right lobe model was about 0.7 mm higher. The left lobe model had the worst result due to its complex shape.

The specificity measure (Table 1) shows that the right lobe model is more specific than both the left lobe and complete liver models. Therefore generated random shapes have lower distances from the training images.

The results reveal that decomposing a shape may affect the evaluating measures and thus lead to a more accurate model. Also, taking anatomical information into account may prevent assigning wrong correspondences in biological tissues.

6 Conclusion and future works

In this paper, we presented a robust point correspondence algorithm, decomposed a complex shape into simple parts, and built individual models for each part. The proposed approach helps us to represent the surface of a complex shape with uniform meshes and to build more accurate shape models. Regarding human liver, typical applications of an accurate shape model include precise segmentation of the hepatic volume [26] and detection of liver shape deformation which is considered as a kind of disease [27].

In future, we plan to divide a liver shape into more simple parts based on anatomical landmarks and develop a hierarchical model to represent complex shapes.