Introduction

In the last decades, advances in medicine have seen the emergence of minimally-invasive surgery. In this surgical approach, the surgeon manipulates the organs with instruments inserted through trocars placed in small abdominal incisions. The view of the operating field is provided by a laparoscopic camera, inserted also through a trocar, allowing the surgeon to perform the surgery by watching a high-definition monitor placed above the patient. Minimally-invasive surgery provides real benefits to the patient, by reducing pain, bleeding and risks of infection and therefore shortening recovery time. However, since the manipulation of instruments is indirect and the visual feedback is limited, it remains quite challenging from a surgical standpoint. Improved navigation, planning, and visualization of internal structures are among the main requirements. The use of a laparoscopic camera in the clinical routine has naturally led the research community to investigate registration techniques in order to overlay the pre-operative anatomical models directly onto the intra-operative view. In the context of hepatic surgery, the objective is to locate tumors with greater accuracy and preserve vessels which are needed for the post-operative regeneration of the liver tissue. For this reason, and also due to the important deformations underwent by the liver during the procedure, minimally-invasive hepatic surgery is a challenge for intra-operative guidance methods.

Registration between intra-operative data and pre-operative data is a cross-disciplinary research domain combining disciplines such as computer vision, image processing, computer graphics and computational mechanics methods. Indeed, where surgical vision methods36 help process the endoscopic images in order to recover organs shapes, perform instruments tracking, or estimate camera position, computer graphics techniques aim at providing three-dimensional virtual representations of real organs using advanced geometrical modeling and rendering algorithms. These three-dimensional representations are often considered as purely geometric, since most existing surgical navigation systems assume rigid organ motion.24 Nevertheless, in real clinical routines, this assumption no longer holds, given the elastic characteristics of soft tissues. In addition, in minimally-invasive surgery, the abdomen is inflated with CO2, creating large deformations of the organs to which respiratory and cardiac motions are added, as well as interactions with surgical instruments. As a consequence, more advanced modeling methods need to be envisioned, such that elastic deformations linking pre- and intra-operative data can be simulated in real-time.

The benefits of surgery navigation are particularly clear in laparoscopic hepatectomy where it can enable the visualization of pre-operative data directly fused with endoscopic images. Generally, a geometrical model constructed from pre-operative data is used during the navigation,24,31,37 Although such approaches offer the possibility to achieve real-time registration and give visually coherent augmentation, they are limited to surface overlay, as neither the vessels nor the tumors are considered. They also rarely account for soft tissue deformation.

To provide in-depth structures overlay, elastic registration and volume computation has to be considered.14,16,38 Physically-based elastic models have proven to be relevant for volume deformation tracking since they permit to estimate the in-depth motion from surface deformation. In,30 a 4D scan of the heart is coupled with a biomechanical model. It is controlled by surface constraints created by features extracted from a stereo-vision camera stream and allows for a quite accurate estimation of the position of internal structures. This approach is, however, dedicated to cyclic movements and cannot be translated to liver surgery where large and unpredictable deformations may occur. Based on a dynamic model, Schaerer et al. 32 proposed to use forces measured in the image to drive the model towards the boundaries of the object. The main limitation of this method is that it assumes the organ to be homogeneous, and that the entire organ is visible in the MRI data. A Neo-hookean elastic model is employed in35 in order to perform intra-operative registration between stereo-endoscopic images and pre-operative model of the liver. The accuracy of registration is assessed on a phantom and shows the suitability of the model for an accurate registration, nevertheless not suitable for a real time simulation. In our previous work,14 we used a deformable biomechanical model accounting for heterogeneity and anisotropy for hepatic surgery guidance. Convincing results are reported on both in vivo and phantom data under well-defined conditions. Nevertheless, the boundary conditions, which are essential to yield good results, were defined in an ad-hoc manner during the initialization phase. In,38 shape-matching is used for the registration of a physically-based model derived from pre-operative mesh and intra-operative surface computed from camera. The intra-operative organ shape is modeled as an electrostatic-elastic problem. The elastic model is electrically charged to slide into an oppositely charged organ shape representation. Nonetheless, the method uses a simplified homogeneous model of the liver and it is assumed that at least 50% of the organ surface is captured by the camera, which is generally not possible. A pose-independent matching of intra-operative data acquired by a camera was proposed in.8 The method is automatic and takes into account data noise and tissue deformations. However, the approach requires to have access to an advanced camera hardware providing depth information, which facilitates the reconstruction of the surface, but is not usable in clinical (minimally-invasive) conditions.

Based on the work of,2 Oktay et al. 25 proposed to combine the intra-operative data acquired from CT-scans with a biomechanical simulation of gas insufflation to accurately perform the registration. Although this method provides accurate registration, it relies on intra-operative scans, which are currently not available during clinical routines. Clements et al. 6 introduced an approach that exploits salient anatomical features, identifiable in both the pre-operative images and intra-operative liver surface. Based on an iterative closest point (ICP) the method performs well, but is limited to rigid transformations. In28 an automatic registration of the liver using only the endoscopic images is proposed. It relies on an approach similar to6 but using a deformable model. Nonetheless, the method performs the registration only with a static point cloud, thus not handling liver motion due to respiratory and cardiac motions.

While the above approaches are often based on a biomechanical model to describe the behavior of the deformable body, the modeling of the organ remains relatively simple and usually not compatible with the real-time simulation. For instance, in the case of the liver, it has been demonstrated experimentally that this organ has a complex anatomy with a significant level of patient-specificity.20,43 In our context, using a more accurate model will improve the accuracy of the internal structure position estimation.16 Such an improvement in the model can be obtained by accounting for the three different constituents (parenchyma, vessels, Glisson’s capsule) of the liver, each having its characteristic mechanical properties.40 Another element influencing the behavior of the liver is the pathology, which in certain cases can stiffen the organ significantly. Among the important body of work that exists regarding the biomechanical properties of the liver parenchyma, only few studies focused on the role of vascularization inside the tissue. In,18 a visco-elastic model of the liver is proposed as well as material parameters experimentally measured ex vivo on perfused liver. In,23 a patient specific model of hepatic vasculature is proposed. The material properties of vessels are modelled by non-linear constitutive law. Nevertheless, the model does not allow for real-time performance as the vessel walls are modelled with large number of finite elements.

This article is an extension of our previous works,16,28 where we improve upon16 by adding anatomically correct boundary conditions, and extend the work presented in28 by considering a non-static point cloud in the registration process. In this paper we mainly focus on the usability and assessment of the framework depicted in Fig. 1. In particular we emphasize the patient-specific model of the liver, which takes into account the vascular network as the main source of heterogeneity and anisotropy, yet allows for real-time augmentation and is directly derived from medical images routinely acquired in the case of liver cancer. The details about the model reconstruction are presented in "Patient-specific Composite Model of Human Liver" section. The biomechanical model is constrained by anatomically correct boundary conditions, which are transferred from a statistical atlas. These boundary conditions permit to obtain a well-constrained system during the registration process which is based on a two-step approach. First, an iterative algorithm brings the pre-operative model in the camera reference frame and deforms it according to the point cloud shape. Then, a tracking algorithm guarantees the real-time registration of the biomechanical model with the liver view of the endoscopic video flow. The method of both the initial and the real-time registrations are described in  "Image-Guided Non-rigid Registration" section. Further, the "Results" section  provides an assessment of the method using the synthetic and in vivo experimental data. The limitations of the method as well as its applicability are finally discussed in  "Conclusion" section.

Materials and Methods

Patient-Specific Composite Model of Human Liver

The biomechanical model used for the initial registration and intra-operative positional prediction of the internal structures (such as vessels and lesions) has two aspects: the reconstruction of the geometry and the physical formulation of the problem. It has been demonstrated via rheological experiments presented in40 that the biomechanical behaviour of the liver is determined by three constituents: parenchyma, Glisson’s capsule and vascularization. Therefore, our framework relies on the composite model presented in26, 27 which combines the mechanical response of the three constituents while allows for real-time employment of the resulting virtual object.

In this section, the semi-automatic pipeline which creates the geometrical representation from the input images (such as pre-operative CT or MRI) is first described. Further, the mechanical aspects of the composite model are presented together with an efficient solution method.

Reconstruction of the Model Geometry

The geometry of the model is obtained by a semi-automatic pipeline presented in Fig. 2. Starting from the pre-operative images, the pipeline has two branches: the geometrical reconstruction of the parenchyma and the capsule and the reconstruction of the vascular model. While the former consists of segmentation and meshing, the latter requires skeletonization of the vascular tree and construction of the geometrical representation suitable for the finite-element formulation based on beam elements. Below we present details for each phase of the geometrical reconstruction.

Geometrical Reconstruction of Parenchyma and Capsule

To perform the liver segmentation, we employ the field level set algorithm presented in.44 The quality of the segmented map is improved by several filtering methods, namely by Laplacian smoothing, hole-filling and detection of the continuous components. Afterwards, it is used to generate the finite element mesh for both the parenchyma and the capsule. In our pipeline, we employ the method presented in4 which generates the 3D tetrahedral mesh of the parenchyma directly from the segmented map and reduces the number of degenerated elements and slivers using mesh optimizations such as Lloyd and ODT smoothers. The surface triangulation of the mesh is extracted from the tetrahedral mesh, resulting in the geometrical domain of the capsule.

Geometrical Reconstruction of the Vascularization

Blood vessels are segmented from the same image modality as the parenchyma by a semi-automatic method.44 Then a skeletonization is computed using an algorithm based on Voronoi diagram1 which as the input takes the surface of the segmented map. This surface is usually constructed using a marching cubes algorithm, however the resulting skeleton often suffers from incompleteness as the method is very sensitive to the quality of the segmentation. Therefore, we adapted the method based on iterative Dijkstra minimum cost spanning tree presented in.41 The method works directly with the segmented map which is converted into a weighted 3D graph where each voxel belonging to the segmented volume is prepresented by a weighted node.

The method constructs the skeleton in two steps: first, the spanning tree is constructed iteratively starting from the root voxel. The edges between voxels are constructed recursively using a sorted heap: in each step, the head of the heap having the minimal weight is marked and all its unmarked neighbors are inserted into the heap. The node weight used to sort the heap is defined as \(\frac{1}{r_{\rm{b}}}\) where \(r_{\rm{b}}\) is a distance from boundary which is obtained from distance map pre-computed from the binary image of the vascular tree. The weight thus prioritizes the voxels with higher probability to lie on the centerline, i.e., further from the vessel boundary. Moreover, for each visited voxel, its distance from the root (\(d_{\rm{r}}\)) is stored, being the geometrical distance along the edges contructed so far from the root.

Second, the centerlines are extracted recursively from the tree:

  • Path \({\mathscr{P}}_0\) of order 0 is constructed as the shortest path connecting the root and the voxel with the highest value of \(d_{\rm{r}}\) in the graph.

  • Path \({\mathscr{P}}_n\) of order n is constructed in two steps:

    • voxel expansion: for each voxel \({\mathbf{v}}\) of the path \({\mathscr{P}}_{n-1}\) of order \((n-1)\), a set \({\mathcal{V}}_{\mathbf{v}}\) of all voxels accessible from \({\mathbf{v}}\) is constructed.

    • path extraction: the shortest path \(({\mathbf{v}},{\mathbf{w}})\) is constructed: \({\mathbf{v}}\) is the parent voxel (on path of order \((n-1)\)) and \({\mathbf{w}}\) is the voxel from \({\mathcal{V}}_{\mathbf{v}}\) having the highest value of \(d_{\rm{r}}\).

We introduce several modifications w.r.t.  the original method:41 first of all, in order to increase the smoothness of the resulting centerline, we evaluated the extraction for different exponents \(e\in \{1,2,3,4,5,6\}\) in the definition of the node weight \(\frac{1}{r_{\rm{b}}^e}\). We obtained the best results in terms of centerline smoothness and continuity using \(e=4\). Further, we added two heuristics in order to improve the quality of the skeleton. The first heuristic attempts to shorten the new path \({\mathscr{P}}_n({\mathbf{v}},{\mathbf{w}})\) by finding a parent voxel \({\mathbf{u}}\) which is closer to the terminal voxel \({\mathbf{w}}\). Mathematically, we look for a voxel \({\mathbf{u}}\in {\mathscr{P}}_{n-1}\) such that: \({\mathbf{u}}\) is adjacent to a voxel from \({\mathscr{P}}_n\) and for the lengths of the paths, it holds: \(|({\mathbf{u}},{\mathbf{w}})| < |({\mathbf{v}},{\mathbf{w}})|\). If such voxel exists, path \(({\mathbf{v}},{\mathbf{w}})\) is replaced by path \(({\mathbf{u}},{\mathbf{w}})\).

The second heuristic detects the false paths which lie inside a tube in which a path already exists. Before testing the new path \({\mathscr{P}}_n({\mathbf{v}},{\mathbf{w}})\), we find a voxel \({\mathbf{u}}\in {\mathscr{P}}_{n-1}\) which lies in the parent path and minimizes the Euclidean distance \(|({\mathbf{u}},{\mathbf{w}})|\). This distance is not measured along the path but it is simply the length of a straight line connecting \({\mathbf{u}}\) and \({\mathbf{w}}\). A new path \({\mathscr{P}}_n({\mathbf{v}},{\mathbf{w}})\) is removed if:

  • the angle \(({\mathbf{v}},{\mathbf{u}}), ({\mathbf{v}},{\mathbf{w}})\) does not lie inside the interval \((\pi /2-\epsilon ,\pi /2+\epsilon )\); experimentally, we determined \(\epsilon = 0.05\,\text {rad}\);

  • the line \({\mathbf{u}},{\mathbf{w}}\) lies completely inside the segmented volume.

The second condition detects the paths which lie inside the same tube as the parent path, however, the detection is applied only to paths which are not almost perpendicular to the parent path.

The skeleton constructed by the graph-based method presented above cannot be used directly as the domain for the finite element method based on the beam formulation, which requires smooth geometrical representation where every node is equipped with both positional and rotational degrees of freedom (DoF).

Therefore, the next step in the reconstruction process is based on Bézier curve fitting: a set of cubic Bézier curves is fit to each segment of the skeleton using the recursive algorithm presented in.33 Then, the 6 DoF nodes are sampled along the Bézier curves adaptively: the density of sampling increases along the segmented with higher curvature in order to improve the quality of the discretization.

Patient-Specific Composite Model

Similarly as in,38 we consider the registration as a dynamic process. This avoids having to set Dirichlet boundary conditions such that the stiffness matrix is invertible. Such boundary conditions would not make sense in an ICP-based approach. The dynamic system of equations is given by

$${\mathbf{M}}{\ddot{\vec{u}}} + {\mathbf{B}}{\dot{\vec{u}}} + {\mathbf{K}}({\vec{u}}) = {\vec{f}},$$
(1)

where \({\mathbf{M}}\) is the mass matrix, \({\mathbf{B}}\) is the damping matrix, \({\mathbf{K}}\) is the stiffness matrix, \({\vec{u}}\) is the vector of nodal displacements and \({\vec{f}}\) is the vector of external forces applied to the deformable object.

In this paper, the liver is modeled using a composite approach which takes into account the mechanical behavior of the three components of the liver: parenchyma, vessels and Glisson’s capsule. Since the mass of both the vessel walls and the capsule is negligible w.r.t.  the entire body, the mass matrix \({\mathbf{M}}\) is based only on the mass of the parenchyma. In our approach, the damping matrix \({\mathbf{B}}\) is obtained by an approximation

$${\mathbf{B}} = r_M{\mathbf{M}} + r_K{\mathbf{K}},$$
(2)

where \(r_M\) and \(r_K\) are Rayleigh mass and damping, respectively. Finally, the mass matrix \({\mathbf{K}}\) is the part of the equation which is composed from three different contributions corresponding to the three components of the liver as explained in the following section.

FE Formulation of the Liver Parenchyma

While time-dependent phenomena related to viscosity are not considered in this work, we employ co-rotational finite elements to model the parenchyma relying on the geometrical co-rotational method proposed in.22 Although the technique relies on linear stress-strain relationship, large displacements including rotations can be considered as correctly approximated. Denoting p a generic P1 tetrahedral element of the parenchyma, the 12 × 12 element stiffness matrix is then computed as

$$ {\mathbf{K}}_{\rm{p}} = {\mathbf{R}}^{\top }_{\rm{p}} \left\{ \int _{V_{\rm{p}}} {\mathbf{B}}_{\rm{p}}^\top {\mathbf{D}}_{\rm{p}} {\mathbf{B}}_{\rm{p}} dV \right\} {\mathbf{R}}_{\rm{p}}$$
(3)

where \({\mathbf{B}}_{\rm{p}}\) is the strain-displacement matrix, \({\mathbf{D}}_{\rm{p}}\) is the stress-strain matrix and \({\mathbf{R}}_{\rm{p}}\) is a rotation matrix derived in the co-rotational formulation. The details related the matrices in Eq. (3) can be found in.22 While both \({\mathbf{B}}_{\rm{p}}\) and \({\mathbf{D}}_{\rm{p}}\) are constant during the simulation, \({\mathbf{R}}_{\rm{p}}\) must be updated in each step of the simulation.

In the case when lesions (such as tumors) are present inside the parenchyma, these can be taken into account also from the mechanical point of view as they usually introduce significant heterogeneity. This heterogeneity can be straightforwardly included in the model since the employed meshing technique4 allows for creating heterogeneous meshes according to different labels in the input segmented map. Then, various constitutive parameters can be assigned to the elements that belong to the area representing the lesion.

FE Formulation of the Vascular Structures

Similarly, the co-rotational approach is used to model the vascular structures. The serially-linked beam elements based on Tymoshenko formulation are employed, taking into account the hollow structure of the vessels via moments of inertia. As the beam formulation considers both positional and rotational degrees of freedom (allowing for modeling the twists and torques), each beam element v is modeled with a 12 × 12 elements stiffness matrix \({\mathbf{K}}_{\rm{v}}\). Although the size of the local system is the same as in the case of parenchyma, the matrix has a completely different structure, as it describes an element given by two nodes each having six degrees of freedom. Thus, it relates angular and spatial positions of each end of a beam element to the forces and torques applied to them. The exact definition of the matrix \({\mathbf{K}}_{\rm{v}}\) can be found in.9

FE Formulation of the Glisson’s Capsule

Due to the thickness of the Glisson’s capsule (<20 μm), it is not possible to model such a thin structure with classical tetrahedral elements in real-time as the model would require an extremely dense mesh. Instead, modeling the capsule with two-dimensional elements that abstract from the thickness in the third dimension seems to be a natural choice. In the elasticity theory, this functionality is usually provided by membrane elements. To maintain simplicity of the composite model we choose constant strain triangular (CST) elements based on co-rotational formulation. For each CST element c, the 9 × 9 stiffness matrix \({\mathbf{K}}_c\) is given as

$$\begin{aligned}{\mathbf{K}}_{\rm{c}} = & {} \int _V {\mathbf{B}}^\top _{\rm{c}} {\mathbf{D}}_{\rm{c}} {\mathbf{B}}_{\rm{c}} dV \end{aligned}$$
(4)
$$\begin{aligned}= & {} h \int _A {\mathbf{B}}^\top _{\rm{c}} {\mathbf{D}}_{\rm{c}} {\mathbf{B}}_{\rm{c}} dA, \end{aligned}$$
(5)
$$\begin{aligned}= & {} h A {\mathbf{B}}^\top _{\rm{c}} {\mathbf{D}}_{\rm{c}} {\mathbf{B}}_{\rm{c}} , \end{aligned}$$
(6)

where \({\mathbf{B}}_{\rm{c}},\) is the strain-displacement matrix, \({\mathbf{D}}_{\rm{c}}\) the material matrix, h is the thickness and A the area of the element. In the previous Eq. (5) follows from the fact that we assume constant thickness of the element and Eq. (6) follows from the fact that the strain-displacement matrix is constant in our case. The strain-displacement matrix for the CST element can be expressed as:

$$\begin{aligned} {\mathbf{B}}_{\rm{c}} = \frac{1}{2A} \left[\begin{array}{lllllll} {\vec{y}}_{23}&\quad{\vec{0}}&\quad{\vec{y}}_{31}&\quad{\vec{0}}&\quad{\vec{y}}_{12}&\quad{\vec{0}} \\ {\vec{0}}&\quad{\vec{x}}_{32}&\quad{\vec{0}}&\quad{\vec{x}}_{13}&\quad{\vec{0}}&\quad{\vec{x}}_{21} \\ {\vec{x}}_{32}&\quad{\vec{y}}_{23}&\quad{\vec{x}}_{13}&\quad{\vec{y}}_{31}&\quad{\vec{x}}_{21}&\quad{\vec{y}}_{12} \end{array}\right] \end{aligned}$$
(7)

The values \(x_{ij} = x_i - x_j\) and \(y_{ij} = y_i - y_j\) are computed from the x or y coordinates of the nodes i, j of the triangular element. The reader can refer to the respective literature11 for more thorough description.

Complete Liver Model

The complete model of the liver takes into account all three components described above by combining the contributions of parenchyma, vessels and capsule. The coupling between the vessel elements (beams) and parenchyma elements (tetrahedra) is described in detail in.26 Briefly, each vessel node (having 6 degrees of freedom to account for torques in vessels) is coupled with a tetrahedra in which it is located via barycentric coordinates. This coupling remains constant during the simulation and can be described via matrix \({\mathbf{J}}_{v\rightarrow p}\) which is the Jacobian matrix of the coupling.

The coupling between the parenchyma and capsule is straightforward, since the triangles used as the domain for the CST formulations are the surface faces of the volume mesh. Therefore, for a given triangle with vertices \(v_1\), \(v_2\) and \(v_3\), the corresponding tetrahedron (sharing the same three vertices) is found and a 9 × 12 permutation matrix \({\mathbf{P}}_{c\rightarrow p}\) mapping the triangle vertices to tetrahedra vertices is computed.

Without loss of generality, let us suppose a tetrahedral element e which receives a mechanical contribution from both the capsule and vessels. The composite element stiffness matrix \({\mathbf{K}}_{\rm{e}}\) is then computed as

$$\begin{aligned} {\mathbf{K}}_{e} = {\mathbf{K}}_{p} + {\mathbf{J}}_{v\rightarrow p}^\top {\mathbf{K}}_v {\mathbf{J}}_{v\rightarrow p} + {\mathbf{P}}_{c\rightarrow p}^\top {\mathbf{K}}_c {\mathbf{P}}_{c\rightarrow p}. \end{aligned}$$
(8)

The beam and triangular elements together with the areas of the parenchyma having different Young’s modulus introduce heterogeneity and anisotropy into the simulation of the organ. Therefore, either direct solver or preconditioners must be used to solve the system in each step of the simulation.

Numerical Solution

The dynamic system given by Eq. (1) is integrated using implicit backward Euler scheme presented in.3 The scheme requires to compute the inversion of the system matrix in each time step. Since the system matrix consists of the contributions from the vessels and capsule which introduce heterogeneity and anisotropy, the convergence of iterative solvers such as the conjugate gradient (CG) is jeopardized.34 In our case, due to the heterogeneity and anisotropy introduced by the vessels, the CG requires an important number of iteration or might not converge. Therefore, the system matrix is factorized using the LDL decomposition. In the future, we will use the technique based on the asynchronous preconditioning7 in order to improve the computational time.

Image-Guided Non-rigid Registration

To register the pre-operative liver model onto the intra-operative laparoscopic video stream, we rely on (1) a reconstruction of a three-dimensional point cloud from the stereo-endoscopic camera view, and (2) a multi-step registration process. The main requirements and constraints of this problem can be summarized as follows. First, the stereo-endoscope is capable of capturing only a part of the liver (about 30 to 40% of the whole surface), and we must rely on this partial information to drive the registration process. Second, the liver sustains significant deformations due to the inflation of the abdomen with CO2, and the reference frames from the pre-operative CT scan is completely different from the reference frame of the stereoscopic image, leading to a very poorly initialized registration problem. Third, the liver is continuously moving, under the influence of both breathing and cardiac motions. The following sections describe the approach we propose to address these different points.

Atlas-based Transfer of Anatomical Features

In order to improve the accuracy and robustness of the registration process, we augment the pre-operative liver model with anatomical features. The first step consists of labeling corresponding areas on both the pre-operative mesh and the point cloud to ensure that this point cloud, corresponding to the visible part of the liver, is accurately matched on the pre-operative surface mesh. Three anatomical features are used as landmarks: the umbilical notch where the right margin of falciform ligament is attached to the liver, the anterior margin of the liver (see Fig. 3), and the vena cava which is tightly connected to the posterior part of the liver. The second step consists in assigning different roles to these landmarks. Some of them are used to drive the initial registration, others are used as boundary conditions during the real-time registration process. The anterior margin and umbilical notch are used in the registration process, and the vena cava as a boundary condition of the biomechanical liver model.

Since the anterior margin of the liver can be easily identified in most human liver, it is automatically detected as follows: the edges separating two triangles with sufficiently different directions of normals are selected as seeds. Then, the ridge line is extended from the seed edges; if no extension is found, the seeds are removed. The definition of the two thresholds, one for the seeds and one for the extensions, is based on statistics on the normals for the whole mesh. Iteratively, the ridge line is reconstructed.

Depending on the image modality, the two other anatomical features are either difficult or simply impossible to segment from the pre-operative data. To solve this issue, these features are transferred onto the three dimensional mesh via a statistical atlas hand-built by experts. Details regarding the construction of the atlas are described in.29 For each liver used to create the atlas the segmentation and the landmarks labelling require anatomical expertise and can take several hours. A set of pre-operative medical images of the organ of interest is segmented manually by an expert to obtain segmented map of the organ and anatomical landmarks. From each segmented maps, surface meshes, one for the whole surface and one for each structure of interest, are generated using the method described in  "Reconstruction of the Model Geometry" section. First, a number of points is sampled onto the surface of each mesh. The same number of points and numbering is used for each point cloud corresponding to the same structure. Then, all the point clouds are aligned in a common reference frame using a generalized Procrustes analysis (GPA).13 The GPA determines for each point cloud the similarity transformation \({\mathbf{SIM}}_i\) providing an optimal alignments of all the models in the database:

$$\begin{aligned} {\mathbf{SIM}}_i: &{\mathscr{S}}_i\rightarrow {\mathscr{C}}\qquad {\mathbf{SIM}}_i=s_i{\mathbf{R}}_i{\mathbf{T}}_i, \end{aligned} $$
(9)
$$\begin{aligned} &{\mathbf{P}}_i\mapsto {\mathbf{P}}'_i, \end{aligned}$$
(10)

where \({\mathscr{S}}_i\) is the space of the ith segmented model, \({\mathscr{C}}\) the common reference frame, \({\mathbf{P}}_i\) the initial point cloud, \({\mathbf{P}}'_i\) the aligned point cloud, \({\mathbf{T}}_i\) the translation which align the center of mass of the ith point cloud and the origin, \({\mathbf{R}}_i\) a rotation, and \(s_i\) a scale factor. Both \({\mathbf{R}}_i\) and \(s_i\) are computed iteratively using the matrix \({\mathbf{P}}_i{\bar{\textbf{P}}}^\top \), where \({\bar{\textbf{P}}}\) is the mean shape recomputed at each iteration. We have:

$$\begin{aligned} \text {SVD}(\mathbf{P}_i{\bar{\textbf P}}^\top )&={\mathbf{U}}_i\Sigma _i{\mathbf{V}}_i^\top, \end{aligned}$$
(11)
$$\begin{aligned} {\mathbf{R}}_i&={\mathbf{U}}_i{\mathbf{V}}_i^\top, \end{aligned}$$
(12)
$$ \begin{aligned} s_i&=\sqrt{\frac{\text {tr}({\mathbf{P}}_i {\bar{\textbf{P}}}^\top )}{n||{\mathbf{P}}_i||_F|| {\bar{\textbf{P}}}^\top ||_F}}, \end{aligned}$$
(13)

where SVD(.) denotes the singular value decomposition, tr(.) the trace of a matrix, and \(||.||_F\) the Frobenius norm of a matrix. Then, the principal component analysis (PCA) is performed on each structure of interest to compute the principal modes of deformation across the database. We keep only the most significant modes, i.e. the modes responsible for more than 90% of deformations. Assuming the Gaussian distribution of the modes, we can determine the mean position and the standard deviation associated with each structure. The atlas is finally registered on a three-dimensional patient-specific liver model using the physically-based registration method described in "Elastic Registration" section.

Intra-operative 3D Reconstruction

The estimation of the three-dimensional shape of the liver from intra-operative images can be performed in different ways depending on the image modality.19 In this work, we make no assumption about specific acquisition technologies available in the operating room (such as intra-operative MR or CT scanner, or depth camera), but we rely only on images provided by the stereoscopic camera for the estimation of the three-dimensional shape of the liver. Although this technology is not currently widespread in operating theaters its usage is rapidly growing. The only requirement is that the camera be calibrated at the beginning of the intervention which takes only few seconds.

Let us assume the stereoscopic pair of images \({\mathscr{I}}_l\) and \({\mathscr{I}}_r\). We extract from this stereo pair points of interest (i.e., features) that are sufficiently reliable for the 3D reconstruction. Several detectors have been reported in the literature (e.g.,12), we employ the Speeded-up Robust Features (SURF); our choice is motivated by its particular suitability for robotic-guided endoscopy applications.10

When using this detector on the image pair \(({\mathscr{I}}_l, {\mathscr{I}}_r)\) with an appropriate threshold, we obtain two sets of features \({\mathbf{E_l}} = (x_{1_l},\ldots , x_{n_l})\) and \({\mathbf{E_r}} = (x_{1_r},\ldots , x_{m_r})\) where it is necessary to estimate for each feature \(x_i = (u_i,v_i)\) the 3D point \(X_i = (U_i,V_i,W_i)\). This is done by establishing a correspondence between image points \(x_l \longleftrightarrow x_r\), using a descriptor-based matching method.21 Once a correspondence is found, a sparse set of m 3D points, denoted \({\mathbf{T}} = (X_{1},\ldots , X_{m})\), is reconstructed using triangulation algorithm17 and a surface mesh S is interpolated using Moving Least-Square surface approximation.14,16

The point cloud has to be labelled with the anatomical landmarks described in  "Atlas-Based Transfer of Anatomical Features" section. An operator selects (e.g., by clicking) on one of the stereoscopic images some points on the border of the three regions of interest, the umbilical notch, the anterior margin, and the liver surface, to form closed areas. This selection takes only few seconds. Once the targeted regions are selected, we build for each of them a three-dimensional point cloud using the method described above. These point clouds are labelled according to their corresponding regions as illustrated in Fig. 3a.

Elastic Registration

At the beginning of the registration process, the biomechanical model (source) is in its pre-operative configuration and needs to be deformed to match the intra-operative point cloud (target). This match is only partial since the target represents only about 30% to 40% of the total surface of the liver. The biomechanical model described in "Patient-Specific Composite Model" section is used to simulate the behaviour of the tissue while the registration constraints imposed to the deformable object are modelled with penalty forces \({\mathbf{f}}_{\rm{ext}}\). Theses penalty forces can be seen as a mean of imposing a displacement with a tolerance. Therefore, the result of the registration does not depend on the absolute values of the stress parameters but rather on their relative ratio, as already shown in,42 and on the relative intensity of external forces vs. internal forces. The goal of the registration process is to minimize the energy function associate to theses forces. At each time step, \({\mathbf{f}}_{\rm{ext}}\) is recomputed as follows.

First, we define a set of corresponding pairs \(\{p_i, q_i\}\) where \(p_i\) is a point of the point cloud and \(q_i\) is a point of the biomechanical model surface. To compute these pairs, we project each point of the point cloud with label j onto its closest neighbour on the part of the surface mesh with the same label using the method described in.28 Then, for each pair we define an external force:

$$ {\mathbf{f}}_{\rm{ext}_i}=k(1-\arctan (s|| \overrightarrow{p_iq_i}||))\frac{\overrightarrow{p_iq_i}}{|| \overrightarrow{p_iq_i}||} $$
(14)

where k is a scalar stiffness coefficient [in (N/m)] and the term \(1-\arctan (s|| \overrightarrow{p_iq_i}||)\) is an asymptotic penalty function of the distance [in (m)] which includes also the scale factor s. The stiffness coefficient k is defined in three different ways depending on the type of the corresponding feature: thus, k is one of \(k_{\text{un}}\), \(k_{\text{am}}\) and \(k_{\text{surf}}\) where the identifiers stand for the umbilical notch, anterior margin and surface, respectively. At the beginning of the registration, the reliability of matching associated to each type of feature is reflected in the corresponding values of the stiffness coefficients: \(k_{\text{un}}>k_{\text{am}}>k_{\text{surf}}\). As the registration proceeds, \(k_{\text{un}}\) remains constant, whereas both \(k_{\text {am}}\) and \(k_{\text{surf}}\) evolve in order to prevent the energy minimization process from falling into a local minimum. Therefore, during the registration, it is detected when the mechanical system has reached a plateau, and the stiffness coefficients \(k_j\) for \(j\in \{\text{am},\text{surf}\}\) are updated as

$$ \begin{aligned} k_{j_{\min }}+\frac{2(k_{j_{\max }}-k_{j_{\min }})(\frac{n}{r_j})^2}{(\frac{n}{r_j})^2+1}\text { for } n<r_j \quad \text {and} \quad k_{j_{\max }}\text { for } n\ge r_j \end{aligned}$$
(15)

where \(n\ge 0\) is the plateau index (which is incremented each time a new plateau is detected) and \(r_j> 0\) an integer which controls the increase rate of \(k_j\). The registration is stopped as soon as \(n = \max (r_j) + 1\).

After attaining convergence, the temporal registration step is performed. The temporal registration permits to register the biomechanical model at each frame acquired from the endoscopic camera, following the motion of the liver (which moves due to the heart beating and/or respiratory motion). As a good initialization of the three dimensional model configuration is available, the point cloud is down-sampled and the labels (umbilical notch and anterior margin) are no longer used. The motion of the liver is captured using an optical flow algorithm5 that tracks image-points from the liver surface based on a brightness consistency constraint 4. The combination of optical flow and SURF features has proven to be robust to track heart motion in laparoscopic images, where real-time is needed10 and was successfully translated to liver motion estimation.15 Indeed, at this stage, a real-time simulation is mandatory since video frames are acquired at least at 30 Hz and the registration w.r.t.  the n-th frame must to be performed before the frame \(n+1\) is available. Furthermore, if the boundary conditions were not used during the initial registration because of the rigid transformation between the pre and intra-operative liver model, we activate them during the temporal registration. However, some of the liver boundary conditions are mobile, such as the ligaments that attach the liver to the diaphragm. For this reason, we only use the vena cava and the entrance points of the liver vascular tree as boundary conditions to allow the model to move with the diaphragm.

Results

Throughout the various stages of the pipeline, different sources of errors may degrade the quality of the final result. First, the segmentation of the liver and its vascular network is operator-dependant and sensitive to the quality of the medical images. The error arising from the segmentation is not easy to evaluate but a lower bound is given by the voxel size which in our case is 0.85 mm × 0.85 mm × 0.70 mm. Second, the quality of the three-dimensional mesh generated from the segmented maps depends notably on the number of its vertices. We generated a high-quality mesh and computed the Hausdorff distance between this mesh and the mesh that we use for computation. We found a mean Hausdorff distance of 0.2 mm and a maximal error of 4.9 mm. Third, the point cloud quality is subject to errors arising from the calibration of the camera, the image quality (sharpness, texture...) and from the triangulation method (features detection, matching...). As we do not have any ground truth for the laparoscopic data, it is really difficult to estimate the error in millimetres between the point cloud and the real position of the organ. Fourth, the use of an atlas to transfer some landmarks onto the three dimensional model may lead to some error in their location. We tried to evaluate this error and its influence in "Transfer of Boundary Condition" section. Finally, we evaluate the quality of the registration using our complete biomechanical model of the liver in "Patient-Specific Modeling and Registration" section.

Transfer of Boundary Condition

In this section we assess the quality of the boundary condition transfer and its influence on the biomechanical model behaviour. The atlas was created using ten liver models and their respective anatomical features obtained from segmented abdominal CT scans. To ensure the quality of the atlas, we evaluated the standard deviation of the umbilical notch and vena cava positions over the samples; we obtained \(\sigma _{\text{un}}=\)11.12 mm and \(\sigma _{\text{vc}}=\)16.56 mm respectively. The average variability represents less than 9.7% of the size of the organ showing a strong consistency among the feature positions. We registered the atlas onto several livers: ten from the atlas following the left-one-out principle and two livers not included in the atlas (sample #11 and #12). The registration errors are presented in Fig. 5.

The results show that the surface registration is very accurate and all the boundary condition location errors are under 10 mm except for one sample. This value is less than the standard deviations in the atlas.

To evaluate the influence of errors in boundary condition location, we altered the position of the boundary conditions compared to the reference: the falciform ligament attached to the umbilical notch and the vena cava. We used a liver segmented in the supine position to set up a simulation where gravity is re-oriented in order to simulate a deformation of the organ in the flank position. This simulation was performed using both the reference boundary conditions location and the altered ones. Then, we compared the final shape of the liver simulated with altered boundary condition to the final shape of the reference liver. The results are presented in Fig. 6a. They show that small displacement (below 3 mm) lead to an error below 1 mm, however, the relation between the displacement and the error seems to be quadratic. Nevertheless, a deeper analysis is needed to confirm this tendency. The same kind of experiments was conducted to evaluate the influence of errors in the boundary condition stiffness, the results are shown in Fig. 6b. The values of the reference stiffness were set according to the ligament and vena cava Young’s modulus found in the literature39 (20 MPa for both) and their geometry. The results show that the influence of the stiffness is very small when compared to the influence of the location of the boundary conditions. This can be justified since the ratio between the liver internal forces and the external forces imposed by the boundary condition is very low. Therefore using twice or half the reference stiffness does not change this ratio significantly.

Patient-Specific Modeling and Registration

The aim of the method is to estimate the location of internal structures of the organ which undergoes important intra-operative deformations when compared to its initial pre-operative configuration. Validating the registration in this context is very challenging, since the optimal ground truth would be a 3D reconstruction of the organ at the intra-operative stage, which requires the intra-operative CT or MR scan of the patient. Access to these techniques is very limited and almost impossible to use on human subjects. Consequently, we decompose the validation process in two parts: first, we present quantitative results on in silico data (we decided not to use a phantom for an intermediate validation because of the low complexity of such model and non-realistic conditions for surface patch reconstruction). Second, we report qualitative results using real endoscopic data.

Patient-Specific Modeling

A heterogeneous anisotropic biomechanical model was generated from the patient image data using the method described in "Patient-specific Composite Model of Human Liver" section. In order to obtain the ground truth for the registration and to measure the influence of the biomechanical model used for the deformation, we applied a pressure on the model surface to simulate the effect of the pneumoperitoneum. We used two parameter sets; one representing a healthy liver (parameter values are set as reported in40):

$$\begin{aligned}\begin{array}{lll}&E_{\rm{parenchyma}}=\text {3.5 kPa, }&\nu _{\rm{parenchyma}}=\text {0.45, }\\&E_{\rm{vessels}}=\text {620 kPa, }&\nu _{\rm{vessels}}=\text {0.4, }\\&E_{\rm{capsule}}=\text {8000 kPa, }&\nu _{\rm{capsule}}=\text {0.45,} \end{array}\end{aligned}$$

and the other a cirrhotic liver: \(E_{\rm{parenchyma}}\)= 30 kPa. All the other parameters are identical for both cases. We also deformed two homogeneous models of the parenchyma using the Young’s modulus and the Poisson’s ratio of the healthy and cirrhotic liver. Then, we measured the distance between the final states obtained after deformation. We compared the healthy liver to the cirrhotic one and the homogeneous models to their heterogeneous counterparts.

Results presented in Fig. 7 show that the vessels and the capsule influence the deformations, particularly in the case of the healthy liver where the mean Target Registration Error (TRE) between the final configuration of the heterogeneous and homogeneous model is 10.1 mm. This error represent 43% of the homogeneous healthy liver deformation. The same analysis performed for the cirrhotic liver quantifies the influence of the vessels being 18% w.r.t.  the entire deformation.

Registration

As only a part of the liver surface is visible to the endoscopic camera during a surgical intervention, we extracted a portion of the deformed surface from the deformed configuration, obtained with the healthy and cirrhotic heterogeneous liver model. We kept two deformed configurations having an area ranging from 50% to 10% of the whole surface and evaluated the registration robustness w.r.t.  the amount of visible surface.

The undeformed healthy and cirrhotic biomechanical models were subsequently registered onto these partial surfaces. Then, we compared the shape of the models after registration with the deformed configurations of the whole meshes. We used a tetrahedral mesh composed of 2193 tetrahedra and 547 vertices. The Rayleigh mass and the Rayleigh damping coefficients were set to 0.1. For all registrations we adjusted the parameters according to the Young’s modulus value. In this manner, we ensured that the ratio between the external and the internal forces remains the same independently of the actual value of the Young’s modulus. We use a factor \(10^{-3}\) for \(k_{\text{un}}\), \(k_{\text{am}_{\max }}\), and \(k_{\text{surf}_{\max }}\), a factor \(10^{-4}\) for \(k_{\text{am}_{\min }}\) and we set \(k_{\text{surf}_{\min }}=0\), \(r_{\text{am}} =2\), and \(r_{\text{surf}} =10\). The computational time needed for the initial registration remains below 30 s which is acceptable for the given scenario.

We computed the TRE on the mesh surface and in the mesh volume to measure the accuracy of the registration. The results are presented in Fig. 8. We obtained a mean error below 3 mm in all cases except when the visible surface represent less than 20% of the liver surface, which would correspond to a very limited surface reconstruction.

We also tested the influence of our heterogeneous liver model vs. a simplified homogeneous liver model on the registration. In the case of a cirrhotic liver the registrations of the simplified model leads to similar TRE showing that the vessels have a low influence on the model. However, in the case of a healthy liver the volume TRE increase when the registration is performed with a simplified biomechanical model.

Additionally, we studied the influence of the point cloud size on the registration results. Provided that the density of points remains above 0.7 points per square centimetre, the mean TRE between the registration result using the complete point cloud (3.9 points per square centimetre) and the down sampled one does not exceed 1 mm.

Moreover, as the umbilical notch position is transferred to the patient liver via an atlas, we conducted a preliminary study to evaluate the influence of the umbilical notch position on the registration results. We moved the umbilical notch around its real position on the liver surface. The TRE between the registered source mesh using the reference umbilical notch position vs. the altered position highly depends on the displacement direction. The worst scenarios occurs when the umbilical notch is displaced along the anterior margin towards the right lobe. In this case the mean TRE is increased by 3.5 mm for a position shift of 17.5 mm (mean hausdorf distance of 4.8 mm). However, for all tested scenarios, the TRE remains below 2 mm as long as the displacement of the ligament does not exceed 10 mm (mean hausdorf distance of 1.0 mm). Nevertheless, additional experiments would be necessary to conduct a proper analysis of the impact of position error of the umbilical notch on the registration result.

Finally, we tested our method on in-vivo human data using two sets of patient images. As in-vivo a direct quantitative evaluation is not possible, we perform only a visual qualitative assessment presented in Fig. 9. Nonetheless, even in this case, it is challenging to provide comprehensible visualization of the registration results. However, the point cloud was accurately matched to its corresponding part onto the three dimensional mesh and the mean Hausdorff distance between the surface mesh and the point cloud was below 1.1 mm.

Conclusion

We presented a complete pipeline to register a pre-operative patient-specific three-dimensional model of the liver to sparse and incomplete intra-operative data extracted from stereo-endoscopic images. This pipeline includes a semi-automatic segmentation of the liver and its vascular system, an automatic generation of the biomechanical model from the segmented maps, a real-time simulation of the complete liver model. It also involves the automatic adaptation of boundary conditions using a statistical atlas, and an ICP-based non-rigid registration process.

We performed a quantitative assessment of the registration accuracy using the synthetic data for which the ground truth is known. The evaluation was done for two different sets of parameters corresponding to healthy and cirrhotic liver. In the case of the healthy liver, the influence of the vascular network on the overall deformable behavior was more significant than in the case of the cirrhotic liver which is much stiffer. In both cases, the elastic registration was capable of providing a good estimation of the actual position of the internal structures from the surface data: we showed that only 30% of the organ surface captured by the camera is sufficient to reduce the mean TRE measured both on the surface and in the volume below 3 mm. This value is smaller than the current laparoscopic procedure safety margins which are usually between 10 and 25 mm around the possible location of a tumor. We have also performed a qualitative assessment using real patient data. Both the evaluation using the synthetic and the real data demonstrated that using a biomechanical model results in good accuracy and robustness of the method.

We are currently developing a prototype of our system that can be deployed in the operating room. This requires to further automate the pipeline described in this work, and to reduce the number of parameters involved in the process. We are also working on a more thorough validation protocol based on an intra-operative CT scan in which the position of the camera could be determined as well as the location of the tumor(s). This will allow for a direct comparison of the estimated and actual target locations.

In the future, we plan to improve the definitions of the boundary conditions for the temporal registration phase which is an important and challenging problem. We will also try to design an in vivo validation setup to obtain quantitative errors on real data. In addition, we plan to improve the visualization of the vascular network superimposed on the laparoscopic view to ensure better depth perception.

Figure 1
figure 1

Overall concept of our approach illustrating the non-rigid registration process using a patient-specific biomechanical model derived from pre-operative data. The registration with the endoscopic image permits the visualization of internal structures during the operation in order to provide surgeons with decision support.

Full size image
Figure 2
figure 2

Scheme showing the pipeline used for the model reconstruction: (a) input CT or MRI data, (b) segmented vascularization, (c) segmented parenchyma, (d) skeletonization of vascular trees, (e) meshing of segmented volume and (f) composite model composed of the parenchyma mesh and beam elements sampled from Bézier curves fitted to the vascular skeleton.

Full size image
Figure 3
figure 3

Anatomical landmarks. On the laparoscopic image: the liver surface (in green), the anterior margin (in orange) and the umbilical notch (in yellow).

Full size image
Figure 4
figure 4

A SURF feature being tracked over time (600 frames) using LK optical flow. (top) tracking performed in both a forward and a backward time direction. Graph shows X and Y coordinates as a function of video frames. (middle) The selected feature located in the endoscopic images at selected frames. (bottom) 50 \(\times \) 50 pixel window centred around the feature location at every 100 frames.

Full size image
Figure 5
figure 5

Mean Hausdorff distances between the segmented liver surface and the registered mean shape (in red) between the manually segmented umbilical notch and the umbilical notch transferred from the atlas (in green) and between the manually segmented vena cava and the vena cava transferred from the atlas (in blue).

Full size image
Figure 6
figure 6

Sensitivity study. Mean Hausdorff distance between the final configurations of a reference model and a biomechanical model with altered boundary conditions position (a) and stiffness (b).

Full size image
Figure 7
figure 7

Surface and volume TRE between deformed configurations. (a) heterogeneous liver model: healthy vs. cirrhotic, (b) healthy liver: homogeneous vs. heterogeneous model, (c) cirrhotic liver: homogeneous vs. heterogeneous model.

Full size image
Figure 8
figure 8

Surface error distributions w.r.t.  the percentage of visible surface. The boxes with solid lines represent the results for the healthy liver and the dashed boxes correspond to the cirrhotic liver (the bar-and-whisker graph shows the mean, upper and lower quartiles, and the maximal and minimal error). For the partial surface representing 10% of the liver surface we also measured the errors on a sub-part corresponding only to the volume under the visible surface from the camera viewpoint (10p).

Full size image
Figure 9
figure 9

Non-rigid registration between intra-operative and pre-operative data using in-vivo human data. The overlay of the liver surface and the vascular network permits to guide surgeon during the operation.

Full size image