Keywords

1 Introduction

Accounting for almost 29 % of all newly diagnosed cancers in 2015 (excluding cancers of the skin), breast cancer is the most frequent cancer among women [1]. Since surgery is performed as the most common treatment, breast deformation is taken place consequently due to tissue removal. It is clear that the imposed breast deformation is strongly dependent upon the amount of removed tissue. Normally, two types of surgeries are considered: mastectomy in which the whole breast is removed, and lumpectomy, also called as Breast Cancer Conservative Treatment (BCCT), in which the tumor together with a thin layer of healthy surrounding tissue are removed [2]. Despite differences between the amount of removed tissue, survival rate of both surgeries are almost the same; therefore, since BCCT requires less tissue to be removed, final aesthetic outcome is expected to be more satisfactory to the patients [3].

Not only the success of a surgery, but also the satisfactory aesthetic outcome is assumed to be important in a patient’s point of view. Therefore, providing a tool to increase the interaction between patients and surgeons can be an interesting framework to assist surgeons in planning surgeries with better cosmetic outcomes. As the aforementioned tool is equipped to use mathematical formulated models, it can generate different post-surgical breast shapes. Free-Form Deformation (FFD), is an example of the approaches used in parametric modeling; however, it has not generally been used for breast data. In this paper, a comparative study is presented to apply the FFD methodology in 3D breast data. Our principal contribution is focused on simplifying FFD methodology to produce better fitting results, in meaningful time. It should be noted that the original FFD designed to be used in closed objects, which is not the case of the data that we are using.

2 Related Works

Parametric modeling is the process of transforming specific data to mathematical models; however, in the mathematical scope, it is called fitting instead of modeling. The method proposed by Ruiz et al. [4] is an example that creates a fitted surface to the input data by satisfying the Nyquist-Shannon criteria. Then, the minimization problem (which is defined based on the residual distance between the surface and the input data) is solved by the Gauss-Newton iterative method to approach the surface to the data iteratively. Highlighting the application of parametric modeling of human body, Weiss et al. [5] fitted the parameters of SPACE (Shape Completion and Animation for PEople) predefined models to depth data and image silhouettes of human body. In their work, they fitted each scanned body data to the closest predefined model.

The idea of using parametric models for breast surgery planning purposes was inspired from the research carried out by Oliveira et al. [6], in which they benefited from Three-Dimensional (3D) models acquired with a low-cost device instead of the most common used Two-Dimensional (2D) HD images, to assess breast aesthetic outcome after BCCT. Now, the idea behind the presented work in this paper is to develop a parametric model to be incorporated in a planning tool based on 3D information.

In the following, more detail of the FFD approach, that is the basis of this work will be presented, using the work of Bardinet et al. [7].

2.1 Free-Form Deformation

The methodology proposed in [7] uses an algorithm to perform parametric fitting in two steps. In the first step, it fits a superquadratic to input data by changing parameters of the superellipsoid in order to minimize the Euclidean distance (also called error distance) between the input data and the superellipsoid. Since there might not be a specific set of parameters to fit the quadric model to the data completely, such a problem can be categorized as a least-square issue. The second step is proceeded by initiating a 3D parallelepipedic grid of points, called grid of control points, that surrounds the fitted superellipsoid (Fig. 1).

Fig. 1.
figure 1

Left: Superellipsoid surrounded by control grid, Right: Control grid

Full size image

The dimensions and orientation of the grid are defined by radial parameters of the superellipsoid. Containing \((l+1)(m+1)(n+1)\) points, the grid is linked to the fitted superellipsoid using a tensor product of tri-variants Bernstein’s polynomials:

$$\begin{aligned} \begin{aligned} X=\sum _{i=0}^l \sum _{j=0}^m \sum _{k=0}^n C_l^iC_m^jC_n^k (1-s)^{l-i}s^i (1-t)^{m-j}t^j .(1-u)^{n-k}u^k P_{ijk} \end{aligned} \end{aligned}$$
(1)

The parametric model is defined as X, and P is a matrix containing the points of the control grid. Besides, s, t, and u are used to denote local coordinate of each model point regarding to its corresponding control point. Compacting the summations, Eq. 1 can be rewritten, as:

$$\begin{aligned} X=BP \end{aligned}$$
(2)

where B is called the deformation matrix. Considering \(\delta X\) as the displacement field between input data and superellipsoid, Eq. 2 can be rewritten regarding to linear equation system:

$$\begin{aligned} \delta X=B\delta P \end{aligned}$$
(3)

The superellipsoid is then deformed through relocating the control points of the grid. Within iterative steps, the points on the superellipsoid are approached to the input data by solving the following minimization equation:

$$\begin{aligned} \begin{aligned} min_p ||BP-X||^2:=min_{\delta P}||B\delta P-\delta X||^2 +\alpha \sum _{j=1}^{NP}\sum _{j^{'}}||P_j-P_{j^{'}}||^2 \end{aligned} \end{aligned}$$
(4)

In the second term, \(j^{'}\) corresponds to the neighbors of P in the position of j and NP stands for the number of control points. In other words, the second term is an internal energy corresponding to the insertion of a zero-length springs between control points, that is being regularized by the weight of \(\alpha \). The equation can be solved using Singular Value Decomposition (SVD) of the matrix B.

3 Moving Towards Better and Faster Breast Fitting Using FFD

A preliminary analysis of the FFD approach (Sect. 2.1) on 3D data which contain an open side demonstrated a disadvantage. An issue called Redundant Bent Layer (RBL) affected the performance of modeling negatively by increasing distance amongst the model and input data. The misalignments of the RBL points (depicted in Fig. 2) is the main reason of the decrease in the similarity between parametric model and input data. RBL occurs when both closed sides of the initial model (both hemispheres of the fitted superellipsoid) are pulled to the closed side of breast data. Since the control points are arranged in a 3D formation, the two pulled sides of the initial model cannot be overlaid completely. Therefore, a gap is imposed between two sides of deformed model. This gap is responsible for producing wrong fitted surface which increases the distance between parametric model and input data. In order to eliminate the RBL on the parametric model, two solutions can be taken into consideration by modifying either the initial model, or the arrangement of the control points.

Fig. 2.
figure 2

Cross section view of a parametric model of a breast using algorithm of [7]: Segmentation of the cube will result in a part of breast model together RBL which is located in back of the modeled breast.

Full size image

3.1 Modifying the Initial Model

The Achilles heel of the RBL is the definition of the initial model; therefore, replacing it with an open-sided object could overcome the issue. Two initial models are proposed in this paper: a finite boundary plane and a superquadric model based on a superparaboloid similar to the one proposed in [8].

The first solution suggests in using a finite boundary plane to fulfills both the requirements of using an open-sidedness and flexibility (in any direction) whilst the second solution suggests using a superparaboloid which was previously introduced in [8]. It not only aims to satisfy the requirement of open-sidedness of the initial model, but also performs the fitting process with less iterations, since the primitive shape is similar to the objects (breast) to fit. Finally, it is recommended to set up both suggested initial models to be orthogonal to the largest principle direction of data. This assures that the model is initiated in a correct place where can overlay the input data completely. For this purpose we used a Principle Component Analysis (PCA) approach.

3.2 Modifying the Arrangement of Control Points

Previously discussed, the FFD carries out the deformation of the initial model by relocating the control points. In [7], it was suggested to use control points arranged in a 3D grid. As discussed before, referring to an open-side breast data, the control points located in the open-side of the model provide a circumstance in which RBL has emerged. Additionally, their participation in the calculating new location of model points imposes additional computation (and time) costs to the algorithm. Therefore, we propose to remove ineffective control points by reducing the dimensions of the control grid from 3D to 2D.

Dimension reduction should be carried out with regard to the presentation of input data. In other words, the dimension in which less data is presented, can be a suitable candidate to be removed. Common methodologies to perform PCA can lead to obtain the best removal candidate. Assuming the third dimension as the candidate of removal, the proposed dimension reduction of control points simplifies the nested summations used to relocate control points in Eq. 1:

$$\begin{aligned} \begin{aligned} X_{new}=\sum _{i=0}^l \sum _{j=0}^m C_l^iC_m^j (1-s)^{l-i}s^i (1-t)^{m-j}t^j .P_{ij} \end{aligned} \end{aligned}$$
(5)

\(X_{new}\) denotes the points of the parametric model. The less control points are considered in the computation, the less time is required for fitting. Figure 3 shows the difference between a 3D grid of control points (originally suggested by the authors in [7]) and proposed 2D grid.

Fig. 3.
figure 3

Left: 3D cube of control points, Right: 2D grid of control points with initial model of superellipsoid. The dimension which is removed has been identified by PCA to contain less presented data.

Full size image

4 Implementation and Results

The original methodology discussed in [7] together with proposed methodologies were implemented using C++ and Mathworks Matlab R2015a respectively, and evaluated on a 3.40 GHz machine equipped with 8 GB of memory.

The iterative modality of the studied algorithms, requires to define a stop criterion. Such criterion is defined in relation to the Euclidean distance between the models being generated in each two consecutive steps. Furthermore, as far as the average distance between two consecutive generated model exceeds \(1.50\,\mathrm{mm}\), the algorithm continues iterative fitting.

Two metrics are considered for the evaluation of the explained methodologies; distance error and computation time. Distance error stands for the average of Euclidean distance between the input data and the generated parametric model. Not only Euclidean, but also Hausdorff distance is calculated. The smaller the distance error is, the more similar the two sets will be. Besides, the computation time is also a key advantage in comparisons. Expectedly, faster methodologies are more preferable.

The evaluated dataset includes 70 breast models. Each 3D model in the dataset was obtained by scanning a patient with Microsoft Kinect, and reconstructing it via the 3D reconstruction algorithm proposed in [9]. Table 1 presents the results obtained by the different methodologies in terms of average fitting errors (Euclidean and Hausdorff) together with standard deviation. It is important to notice that bi-directional distances (from model to data and from data to model) are reported, since there might be differences in the quantity of points between the two comparing pointclouds. Also, the average number of required iterations to reach to stop criterion are reported. Inasmuch as superparaboloid methodologies have been implemented in a different compiler, time comparison cannot lead to mere deduction; however, comparison can be carried out with respect to the number of iterations, since it is compiler independent. Beside the numerical analysis, visual comparisons are depicted in Fig. 4.

Table 1. Reported results to compare proposed methodologies of FFD
Full size table

The smallest average Euclidean error from parametric model to input data was \(1.21\,\mathrm{mm}\) which is obtained by the superellipsoid and a 2D FFD. The methodology of using a plane with a 2D FFD takes the second rank with average Euclidean error of \(1.25\,\mathrm{mm}\), and finally the superellipsoid with 3D FFD stands in the third rank by obtaining an error of \(1.31\,\mathrm{mm}\). With respect to the error from input data to model, the smallest distance error was obtained by using methodology of superellipsoid deformed by a 3D FFD with an error of \(1.70\,\mathrm{mm}\). And in the following rank, superparaboloid deformed by 3D FFD, stands with the error of \(2.28\,\mathrm{mm}\). Third rank belongs to the methodology which uses a superellipsoid and a 2D FFD presenting an error of \(2.71\,\mathrm{mm}\). A brief look to the Table 1 and the requirements of the fitting stage reveals that the methodologies based on FFD superellipsoid and plane generate more precise parametric models than superparaboloid. Considering Model to Ground-truth Euclidean distance, the suggested improvement of 2D arrangement of control points surpasses other method since it eliminates the RBL phenomena. With a small gap, the methodology of using plane with 2D FFD stands in the second rank since using plane as the initial model cannot present the boundaries of breast better than superellipsoid. On the other hand, methodologies using superparaboloid generate parametric models with more distance errors. Although using predefined initial model can accelerate the convergence, the shrinkage of the parametric model in the boundaries emerges additional distance error. Such shrinkage is visible in generated models depicted in Fig. 4-e and f. Also, investigating the arrangement of the control points admits the advantage of using 2D grid instead of 3D. Eliminating increscent control points leads to both the increase of the efficiency of remained control points and decreasing time complexity of algorithm. Additionally, the proposed improvement presented in this paper demonstrated smaller error in comparison to the original methodology and also in fitting time.

Fig. 4.
figure 4

Visual comparison of performed experiments on same input data; (a) original patient breast; (b) Plane + FFD (2D); (c) Superellipsoid + FFD (2D); (d) Superellipsoid + FFD (3D); (e) Superparaboloid + FFD (2D); (f) Superparaboloid + FFD (3D)

Full size image

5 Conclusion

Put all together, parametric modeling is a technique which converts input data into a mathematical model. Mentioning the importance of a parametric modeling in a planning tool, methodologies of FFD have been studied in this paper and two improvements were proposed to enhance it; improvement of the initial model and modification of control points arrangements. Quantitative analysis indicated the proposed approach improves the performance of FFD methodology by decreasing the average distance error. Visual analysis accompanied with quantitative results indicate that the proposed methodologies suffer from model shrinkage in the boundaries. Since the mentioned shrinkage is responsible for the increase of distance between input data and model, possible future work will be concentrated to generate parametric models with less shrinkage which leads to less distance error.