1 Introduction

Cranioplasty is a procedure performed by neurosurgeons to graft the autograft, allograft, xenograft, or synthetic material into defective skull regions [17]. Although the optimal choice involves using a fresh frozen autograft bone flap removed at the craniotomy [27], it is unfeasible for patients with head trauma in emergency. A custom-made pre-fabricated prosthesis using a computer-aided design is a favorable alternative [18]. To ensure the protection of intracranial tissues and recover the pre-operative head shape for aesthetic purposes, bone substitutes must fit the cranial defects. Several methods have emerged in relevant literature for reconstructing the cranial implant, such as the mirroring technique [25, 37], surface interpolation [5, 6], and a deformed template [8, 36], to match the incision as closely as possible. However, the mirroring method is limited by unilateral defects, the surface interpolation approach does not duplicate actual anatomical shapes, and the template-based method requires labor-intensive manual selection of landmarks. In our previous study [20], we proposed an algorithm consisting of the 2D snake and image registration using the patient’s own diagnostic low-resolution and defective high-resolution computed tomography (CT) images to repair the impaired skull for preserving the original appearance. Although our previous approach effectively created a customized skull implant, the computational efficiency can be further improved from within 3 h to within half an hour using the 3D multigrid snake and multiresolution image registration.

Multigrid methods involve using a pyramid of grids to suppress the error components at each level for solving partial differential equations [3, 35]. Numerous multigrid applications are involved in image processing, computer graphics, and computer vision research, including shape from shading [34], image denoising [10], image classification [29], isometric embedding [4], mesh deformation [32], and nonlinear image registration [14]. Multigrid approaches are intrinsically suitable to the snake model (also known as active contour model), because minimizing the energy function can be converted into a partial differential equation [16]. However, most of the previous snake-related applications have considered only 2D images. For example, Papandreou and Maragos [28] applied properly designed multigrid methods for the rapid evolution of level-set-based geometric active contours. Cremers et al. [7] implemented a multigrid scheme to solve the steady-state equation of a diffusion snake, which incorporated a statistical shape prior. Cremers et al. mainly used a knowledge-driven approach to contend with the occlusion problem in computer vision. However, this was not applicable to our case, because prior information was absent. Han et al. [15] efficiently computed the gradient vector flow by introducing a multigrid scheme and served as the external force to increase the capture range of classic snake models in both 2D and 3D images; however, they did not use the multigrid methods in updating the snake coordinates.

The multiresolution scheme optimizes the estimate in coarser-resolution images, and the resulting estimate is propagated to the next finer-resolution image as initial for accelerating the optimization [24, 30]. We refined the previous image registration algorithm with an additional multiresolution image pyramid to accelerate the computation with comparable precision and robustness. Furthermore, we designed an image-trimming procedure to remove the irregular inner margins of the skull implant so that the trimmed implant can more effectively fit the borders of the cranial incision. This allows us to facilitate the placement of skull implants without requiring manual trimming during surgery.

To assess the performance of the proposed algorithm, we manufactured a set of skull phantoms to simulate six different conditions of cranial defects; namely, unilateral, bilateral, and cross-midline defects with 20 or 40 % skull defects. After applying the 3D multigrid snake, multiresolution image registration, and image trimming to reconstruct the defective skull portions, the skull implants were manufactured to observe whether the reconstruction algorithm can recover the original cranial appearance.

2 Materials and methods

In this study, we aimed to reconstruct the cranial defect by image-based and mesh-based processing using a low-resolution diagnostic CT image with an intact skull and a high-resolution CT image with a defective skull. We previously proposed a reconstruction algorithm [20], which was computationally intensive and required approximately 3 h of computation time. The reconstruction algorithm was redesigned to improve the computation efficiency (Fig. 1). The reconstruction steps are as follows. First, the low-resolution CT image is resampled using trilinear interpolation to match the resolution of the high-resolution image. Second, the skull is extracted by image thresholding with a value close to the lower bound of the CT number for the bone. Third, we adopt multigrid techniques on a 3D snake model to accelerate the convergence. The 3D multigrid snake alleviates slice-by-slice computations and matrix inversion of the 2D snake model. Fourth, the multiresolution scheme is employed to reduce computation time in registering the diagnostic and defective images. Fifth, the difference between the two aligned images can be extracted as the defective area. Sixth, we added an image-trimming process to modify the inner margin of the skull implant to facilitate cranioplasty. Finally, the repaired skull images were translated into a stereolithographic (STL) format, and the skull implant was manufactured using a rapid prototyping (RP) machine.

Fig. 1
figure 1

A flow chart of the reconstruction algorithm. Compared with our previous study [20], procedures in the boxes with solid lines are redesigned

Full size image

2.1 Phantom design and image acquisition

We designed a set of skull phantoms based on real cranial CT data to validate the proposed algorithm. A 19-year-old male with an intact skull was informed of radiation concerns, and completed a consent form before participating in this study. The cranial CT data of the subject were acquired as contiguous axial images, covering only areas above the orbitomeatal plane, with in-plane resolution of 0.49 mm × 0.49 mm, and 0.6-mm slice thickness. The acquired CT images were translated into a STL format using computer-aided design software [13]. Seven skull phantoms were duplicated using an RP machine (Dimension SST 768, Stratasys, Inc.) based on the translated STL (Fig. 2). For six of the seven phantoms, a portion of the skull was removed using a clinical-use power twist drill (1.5-mm diameter, Aesculap, Inc.) in different locations and sizes to simulate six conditions of skull defect. Specifically, the six simulated conditions are 20 and 40 % skull defects in the right hemisphere (Fig. 3a, b), cross-midline area (Fig. 3c, d), and bilateral sides (Fig. 3e, f), respectively. The various conditions of skull defects were designed based on the clinical suggestions of neurosurgeons (co-authors C.T. Wu and S.T. Lee). The unilateral side of skull defects is common in patients who receive a craniotomy to control the elevated intracranial pressure. The frontal skull defect is usually caused by trauma from car accidents in which the frontal cranium is subjected to a heavy impact. The bilateral sides of skull defects can result from a second craniotomy or bilateral brain surgery. According to neurosurgeons’ experience, the 20 and 40 % circular skull defects were common in clinics.

Fig. 2
figure 2

A skull phantom manufactured by the RP machine based on the STL of CT skull data

Full size image
Fig. 3
figure 3

The phantom simulations with a 20 % and b 40 % skull defects in the right hemisphere, c 20 % and d 40 % skull defects in the cross-midline area, and e 20 % and f 40 % skull defects in the bilateral sides. The black arrows indicate the removed portions of the phantoms

Full size image

For the subsequent image processing, axial CT images were acquired for one intact and all six defective skull phantoms using a Sensation 16 CT scanner (Siemens, Inc.) at Chang Gung Memorial Hospital, Taoyuan, Taiwan. The field of view was 250 × 250 mm2, with a 512 × 512 matrix and 0.6-mm-thick contiguous slices. Supplemental CT data were reconstructed for the intact skull phantoms with the same in-plane resolution and 5.0-mm slice thickness (Table 1) to simulate the partial volume artifacts in the diagnostic low-resolution CT images.

Table 1 The voxel size of acquired data sets
Full size table

2.2 3D multigrid snake

Active contour models, also known as snakes, are evolving curves driven by minimizing the internal and external energies [16]. The internal energy makes the contour tense and stiff. The external energy derived from image features guides the contour toward the region of interest. The calculus of variations is used to minimize the internal and external energies for deriving the Euler–Lagrange equation:

$$ \alpha {\mathbf{v}}^{\prime \prime } + \beta {\mathbf{v}}^{\prime \prime } \,^{\prime\prime} + \frac{{\partial E_{\text{ext}} }}{{\partial {\mathbf{v}}}} = 0 $$

where v denotes the coordinate vector of the contour with entities v i , for i = 1, 2,…, N (the number of vertex on the contour), the leading two terms were derived from the internal energy with the α and β weights of tension and stiffness, and the final term from the external energy E ext. After a further expansion using a finite difference to approximate derivatives, the equation becomes

$$ \begin{aligned} &\alpha_{i} (v_{i} - v_{i - 1} ) - \alpha_{i + 1} (v_{i + 1} - v_{i} ) + \beta_{i - 1} (v_{i - 2} - 2v_{i - 1} + v_{i} ) \\ &\quad - 2\beta_{i} (v_{i - 1} - 2v_{i} + v_{i + 1} ) + \beta_{i + 1} (v_{i} - 2v_{i + 1} + v_{i + 2} ) + f_{v} (i) = 0 \\ \end{aligned} $$

that can be rewritten into matrix form: \( {\mathbf{A}}v + {\mathbf{f}}_{v} = 0, \) where A is a matrix consisting of α and β, and f v is associated with external energy. Traditionally, A is solved using matrix inversion.

The 2D snake has been applied slice-by-slice to eliminate the superfluous ripple artifacts, which were introduced when images were resampled from low resolution to high resolution [20]. Because skull reconstruction using the 2D snake to iteratively process hundreds of slices can be time consuming, we proposed using the 3D snake with a multigrid algorithm to accelerate the computation and ensure the whole-volume congruency. As described in the previous study [20], we firstly replaced the lower half volume by flipping the upper volume to form a closed skull surface for initializing the 3D snake. We hereafter term the skull/dura interface as the “inner surface” and the skull/scalp interface as the “outer surface”. To encapsulate the recessed surface, rather than the bumped surface (the artifacts) of the skull, image erosion was executed [12]. The inner and outer surface meshes were then constructed using the marching cubes algorithm [22], and were separately used as the initials for the subsequent 3D inner and outer snakes.

In this study, the 3D snake consisted of more than 250,000 vertices, and matrix A was not banded diagonal because of the irregular arrangement of vertices, which limited the use of lower-upper triangular matrix decomposition for matrix inversion [16]. To solve this problem, the basic iterative methods, such as the Jacobi and Gauss–Seidel smoothers, were employed to estimate the solution without inverting matrix A. However, the smoothers can only effectively eliminate the high-frequency errors but are incapable of suppressing the low-frequency ones. We adopted a multigrid approach to accelerate the convergence by damping the low-frequency error components at coarser resolution levels [3, 35].

In multigrid methods, a V-cycle multigrid algorithm traverses the grid hierarchy from the finest level to the coarsest level; at each level, the pre-smoothing is executed. We then return to the finest level step-by-step to perform the post-smoothing. The traversal constitutes a V-shaped path, and this algorithm is referred to as a V-cycle multigrid. In this paper, we implemented the two-level V-cycle multigrid to iteratively update the coordinates of the 3D snake. The mesh at the coarser level was firstly constructed by applying a polygonal simplification algorithm on the original full-resolution mesh [23]. The shortest edge was successively selected and collapsed to merge the two vertices on the same edge. Once the coarse grid was constructed, multigrid methods could be applied with nested iterations and coarse-grid correction. A schematic diagram of the two-level multigrid algorithm is presented in Fig. 4a, and the notations are tabulated in Fig. 4b. The detailed algorithm of a two-level multigrid is presented in [3].

Fig. 4
figure 4

A two-level V-cycle multigrid algorithm. a The schematic diagram. b A list of notations

Full size image

The inner and outer surfaces at the finer level consisted of 268,528 and 348,618 vertices, respectively. The huge amount of data not only consumed the storage space but also hampered the speedup of computation. We used a sparse matrix to store A. We set the stopping criteria for Steps 1, 4, and 7 to be either a pre-defined iteration number (less than 500 in our experiments) or a tolerance

$$ {\text{tol}} = \frac{\left\| r \right\|}{{\varepsilon \cdot \left( {\left\| A \right\| \cdot \left\| v \right\| + \left\| f \right\|} \right)}} $$

that was less than a threshold, where ε is set to 10−8 and 10−3 at fine and coarse levels, respectively [2]. The threshold was 1 in all relaxations, except for the relaxation of z coordinates in pre-smoothing and post-smoothing, where the thresholds were set to be 3.0 and 1.5, respectively, because the residuals reduced extremely slowly.

2.3 Multiresolution image registration

A multiresolution image registration scheme was adopted to avoid local minima and provide better initialization from the coarse images, whilst reducing computation time [21]. Subsampling was used to reduce the full-resolution images with a dimension of 512 × 512 × 228 into two coarser-level images with dimensions of 256 × 256 × 114 and 128 × 128 × 57, respectively. The 3D rigid-body image registration started from the coarsest-level image. The translation parameters were initialized as the difference of two volume centroids and the rotation parameters were initialized as zeros. The convergent parameters were used as initials in the registration of finer-level images. The sum of squared differences was used as the cost function, and Powell’s method was used in optimizing the parameters [21, 31].

2.4 Trimming of repaired skull images

After aligning the intact and defective images, the defective area was extracted using a designed difference operation, which consists of image subtraction, morphological opening, 3D region growing, and manual revision [20]. The resulting image was used to construct the skull implant. The trimming of the skull implants is usually required during cranioplasty surgery so that the implants can match the boundary of defects. The manual trimming of implants may increase the operating time, resulting in additional intra-operative blood loss for patients. The mismatch between implants and the patient’s skull is mainly because of the bumped inner margin of the implants (white arrows in Figs. 5a, 6a). To facilitate the surgery, we trimmed the border of the repaired skull images by shaping the inner margins. The incised margins created during the craniotomy are commonly perpendicular to the skull surface, allowing us to cut the incised margins of the implants at 45° to remove the bumped inner margins (Fig. 5b).

Fig. 5
figure 5

A coronal slice for demonstrating the mismatch between skull defect and implant. a The image displays the mismatch between a skull implant (gray regions) and defective skull (white regions) due to the bumped inner margin (white arrow) of the implant. b The skull implant with 45° inner margin trimming can be placed in the proper position

Full size image
Fig. 6
figure 6

The trimming on the inner margin of a repaired skull image. a A repaired skull image (for the right-hemisphere 20 % defect case) is with bumped inner margins (labeled by white arrows). b The central normal vector (the white line with the outward direction) is defined by the connection of the center point on the outer surface and the centroid of skull image. The outer surface (green surface) possesses normal vectors parallel with the central normal vector (i.e. 0.8 < cross-correlation < 1.0), and the side surface (red surface) possesses normal vectors perpendicular to the central normal vector (i.e. −0.3 < cross-correlation < 0.3). The outer margin (blue curve) is defined as the border between the outer and side surfaces. c The point A on the central normal line is connected with the voxels on the outer margin to define the lines with 45° included angles. The yellow regions are the cut-out inner margins that locate outside the 45° lines. d The trimmed repaired skull image (colour figure online)

Full size image

Specifically, the trimming of the repaired skull images was achieved by performing the following steps. First, we defined the normal vector in the center of the repaired skull images (the white line in Fig. 6b in the outward direction) by connecting the centre point of the outer surface and the centroid of the skull image. Second, we smoothed the images using convolution with a 3 × 3 × 3 kernel composed of the six-neighborhood voxels to reduce the noisy normals. The normals for each surface voxel were estimated according to their image gradients using the central difference approximation. Third, the surface voxels, whose normal vectors were parallel with the central normal vector (0.8 < cross correlation < 1.0), were identified as the outer surface (the green surface in Fig. 6b). The surface voxels, whose normal vectors were perpendicular to the central normal vector (0.3 < cross correlation < 0.3), were defined as the side surface (the red surface in Fig. 6b). The outer margin (the blue curve in Fig. 6b) was defined as the border between the outer and side surfaces. Fourth, we searched for the point on the central normal line (A in Fig. 6c) and connected it with the voxels on the outer margin to define the lines at 45° included angles (magenta lines in Fig. 6c). Finally, the inner margins located outside the 45° lines were removed (yellow regions in Fig. 6c) to result in the trimmed skull images (Fig. 6d). The trimmed skull image can be readily constructed as a mesh and translated into the STL format using Autodesk® 3ds Max®. We manufactured the skull implant using the STL file in an RP machine.

2.5 Assessment of skull reconstruction

We evaluated the performance of the snake and repaired skull implants to assess the skull reconstruction using the phantom CT data sets. The performance of the snake in eliminating the ripple artifacts was assessed using the low-resolution (5.0-mm slice thickness) and high-resolution images (0.6-mm slice thickness) of the intact skull data. The low-resolution images were first resampled to obtain identical resolutions of the resampled image and high-resolution images. The 2D snake and 3D multigrid snake were then employed on the resampled images to eliminate the ripple artifacts on both the inner and outer surfaces. Because the low- and high-resolution images were reconstructed from the same intact skull phantom, the high-resolution images served as the ground truth. The surface errors were estimated for three conditions: resampled, resampled with the 2D snake, and resampled with the 3D multigrid snake.

The surface error was calculated as the distance from every reconstructed inner- or outer-surface vertex to the closest intersection point on the ground truth mesh. Specifically, the estimated coordinate of the ith vertex for each reconstructed mesh, \( v_{i}^{r} \), can be denoted as \( \left( {x_{i}^{r} ,y_{i}^{r} ,z_{i}^{r} } \right) \), for i = 1, 2, …, \( N^{r} \), and \( N^{r} \) is the total number of the vertices for the reconstructed mesh. For each \( v_{i}^{r} \), the three vertices of the nearest plane, \( v_{i1}^{g} \), \( v_{i2}^{g} \), and \( v_{i3}^{g} \), on the ground truth mesh were identified (Fig. 7). The normal of this triangular plane, denoted as \( n_{i}^{g} = (a,b,c) \), can be obtained using the cross-product on vectors \( \overrightarrow {{v_{i2}^{g} v_{i1}^{g} }} \) and \( \overrightarrow {{v_{i3}^{g} v_{i1}^{g} }} \). The plane equation of the nearest plane can be presented as \( ax + by + cz + d = 0 \), where d is a constant determined according to any point on the plane. Finally, the surface error for \( v_{i}^{r} \), can be calculated as \( {\text{SE}}(v_{i}^{r} ) = \frac{{\left| {ax_{i}^{r} + by_{i}^{r} + cz_{i}^{r} + d} \right|}}{{\sqrt {a^{2} + b^{2} + c^{2} } }} \).

Fig. 7
figure 7

The surface error between the reconstructed mesh and the ground truth mesh on v i

Full size image

We evaluated whether the manufactured skull implants could recover the original cranial appearance by two means. First, the skull implants with or without inner margin trimming (Sect. 2.4) were placed on the defective skull phantoms, and the fitness was confirmed by visual inspection. Second, we calculated the errors of the outer surface, which is the main concern of clinics, on each repaired skull portion by comparing the locations of the outer-surface voxels with those on the high-resolution intact skull images.

3 Results

3.1 Speed improvement

Our program was implemented by Microsoft® Visual C++® 6.0, and the experiments were carried out on a personal computer with an Intel® Core™2 Duo CPU 2.33 GHz and 2 GB of RAM on Microsoft® Windows® XP Professional Edition. The time cost of registering diagnostic and defective skull binary images using the full-resolution images is 1,884 ± 309 (mean ± SD) s. Applying the multiresolution scheme in image registration can reduce the computation time to a maximal 1,358 s (right, 40 % defect) and a minimal 330 s (cross-midline, 20 % defect), obtaining an average 732 ± 370 s. The average gain in computational speed was 3; that is, 67 % of computations were saved. In comparing the 2D snake with the 3D multigrid snake, the computation time was shortened from 6,880 s to 245 s—a speed gain of 28. This demonstrated that the 3D multigrid snake significantly improved the computational efficiency.

3.2 Accuracy comparison between 2D snake and 3D multigrid snake

The results of the 2D snake and 3D multigrid snake in eliminating the ripple artifacts compared with the resampled intact skull images (Fig. 8a) are illustrated in Fig. 8b and c, respectively. The ripple artifacts on the outer and inner surfaces in the resampled skull image were efficiently removed by both the 2D snake and 3D multigrid snake. The outer and inner surface errors, which were calculated as the distances to the closest intersection points on the ground truth images for the estimated vertices, were separately assessed.

Fig. 8
figure 8

The processed results from the 2D snake and 3D multigrid snake for the intact skull data. a A sagittal resampled skull image, b the skull image after the 2D snake, c the skull image after the 3D multigrid snake, d the outer surface error for the resampled skull images, e the outer surface error for the images after 2D snake, f the outer surface error for the images after 3D multigrid snake, g the inner surface error for the resampled skull images, h the inner surface error for the images after 2D snake (white arrows indicate the location of local spots), i the inner surface error for the images after 3D multigrid snake. Red arrows indicate the locations of maximal errors for each condition (colour figure online)

Full size image

Regarding the outer surfaces, the surface errors for the resampled images exhibited evident ripple artifacts (Fig. 8d). After applying the 2D snake (Fig. 8e) or the 3D multigrid snake (Fig. 8f), the ripple artifacts on the outer surface were greatly suppressed. Large surface errors (~3.67 mm for the resampled surfaces and ~2.50 mm for the resampled surfaces with either the 2D or 3D multigrid snake) were observed at the posterior upper portions of the skull outer surface under all three conditions (the red arrows in Fig. 8d, e, f). These large surface errors may originate from the insufficient number of image points at the top of the skull because of the larger slice thickness of diagnostic skull images; hence, few points were available that limited the snake algorithms to approximate the curved shape at the top of the skull.

The ripple artifacts of the inner surface were also greatly suppressed by the 2D snake (Fig. 8h) and 3D multigrid snake (Fig. 8i), especially on the convex portions in the resampled surfaces (Fig. 8g). For both snake algorithms, large surface errors of 2.40 mm for the 2D snake and 3.10 mm for the 3D multigrid snake were observed at the frontal crest (the red arrows in Fig. 8h, i). The frontal crest was an anatomical structure with a locally inward bump, as compared with neighboring surfaces, and was similar to the ripple artifacts removed using the snake. Moreover, three other local areas near the parietal portions with inner surface errors of ~2.20 mm were observed in the 2D snake results (white arrows in Fig. 8h), which did not appear in the 3D multigrid snake results.

In comparing the surface errors that resulted from using the 2D snake with those from using the 3D multigrid snake, Fig. 9 displays the distribution of surface errors indicated by box plots. For both the outer and inner surfaces, the 3D multigrid snake presented a lower median, lower 75 % percentile, and a smaller upper adjacent, although fewer outliers were observed at the outer posterior portion and inner frontal crest regions for the 2D snake. Our results suggested that the 3D multigrid snake is more effective in removing the ripple artifacts, as shown in the resampled skull images. In addition, the 3D multigrid snake is more efficient than the 2D snake (a speed gain of 28).

Fig. 9
figure 9

The surface errors result from the 2D snake and 3D multigrid snake for the intact skull data. On each box, the red horizontal line is the median, and the lower and upper edges of the box are the 25th and 75th percentile, respectively. The upper adjacent (upper end of whiskers) represents the minimum error larger than 1.5 times interquartile range of the 75th percentile, and the lower adjacent (lower end of whiskers) represents the maximum error smaller 1.5 times interquartile range of the 25th percentile. Outliers (red crosses) are identified as those beyond the upper adjacent (colour figure online)

Full size image

3.3 Assessment of skull reconstruction

We manufactured the repaired skull implants using RP based on the skull images with or without the inner margin trimming (see Sect. 2.4 and Fig. 6). Figure 10a is the original skull implant manufactured based on the Fig. 6a, and Fig. 10b is the implant based on the Fig. 6d with a 45° inner margin trimming. The original skull implant exhibits bumped inner margin and, therefore, cannot be placed back to the defect portion of phantom properly (black arrows in Fig. 10c, e). In contrast, the skull implant with a 45° trimming can be fitted appropriately to the defective phantom, and the borders of the trimmed skull implant are satisfactorily matched with those in the defect portion (Fig. 10d, f).

Fig. 10
figure 10

The repaired skull implants manufactured by RP. a The original skull implant based on the skull images in Fig. 6a, b the skull implant with 45° inner-margin trimming based on the skull images in Fig. 6d, c the placement of the original skull implant on the defect portion of phantom, d the placement of the trimmed skull implant on the defect portion of phantom, e the placement of the original skull implant from a frontal view, f the placement of the trimmed skull implant from a frontal view. The black arrows indicate the mismatch between the skull implants and defect portion

Full size image

The reconstructed outer surface errors of the repaired skull portions for six conditions of skull defects (Sect. 2.1 and Fig. 3) resulting from using the 2D snake and 3D multigrid snake are displayed in Fig. 11. The results for the right, cross-midline, and bilateral 20 % skull defects exhibit a lower median (for the 2D snake), lower 75th percentile (for the 3D multigrid snake), and a smaller upper adjacent of surface errors, as compared with those for the 40 % skull defects. For all right and bilateral defect conditions, the repaired results obtained using 3D multigrid snake present smaller median outer surface errors, lower 75th percentile, and a smaller upper adjacent than those from using the 2D snake. Moreover, for all four conditions of right and bilateral defects using the 3D snake, the median and 25th percentile are equal to zero, indicating that most reconstructed outer surfaces of defects are close to the ground truth. However, under the condition of the cross-midline 40 % defect, the median and maximum of surface errors are 0.6 and 2.05 mm for the 2D snake, and 0.30 and 2.32 mm for the 3D snake, which are larger than other defect conditions. The larger surface errors and outliers in the 40 % cross-midline defect are caused by the coverage over the posterior upper skull portions (Fig. 8d), which are ~2.50 mm for both the 2D and 3D snakes (red arrows in Fig. 8e, f).

Fig. 11
figure 11

The reconstructed outer surface errors of repaired results for six conditions of skull defects (see Fig. 3) using either the a 2D snake or b 3D multigrid snake. On each box, the red horizontal line is the median, and the lower and upper edges of the box are the 25th and 75th percentile, respectively. The upper adjacent (upper end of whiskers) represents the minimum error larger than 1.5 times interquartile range of the 75th percentile, and the lower adjacent (lower end of whiskers) represents the maximum error smaller 1.5 times interquartile range of the 25th percentile. Outliers (red crosses) are identified as those beyond the upper adjacent (colour figure online)

Full size image

4 Discussion

In this study, we redesigned a reconstruction algorithm to improve the computation efficiency. For the artifact elimination, a 3D multigrid snake was employed to alleviate the iterative process involving hundreds of slices using the 2D snake. The results showed that ~96 % of computation time can be saved using the 3D multigrid snake (reduced from 6,880 to 245 s), and higher accuracy can be achieved in artifact elimination (Fig. 9) and defective skull reconstruction (Fig. 11). For the image registration, a coarse-to-fine multiresolution scheme was adopted to reduce 67 % of computation time (the average speed gain was 3), as compared with the full-resolution image registration with the same accuracy. After the extraction of the defect portion images, we added an image-trimming step to remove the bumped inner margin outside the 45° lines (Fig. 6). This image-trimming procedure can replace the manual trimming of skull implants during surgery and, therefore, reduce the operating time. Using this redesigned reconstruction algorithm, the overall image processing time in reconstructing the repaired skull images can be reduced from 3 h to 20 min, saving ~90 % of computation time.

We noticed that the construction of the coarse mesh influenced the convergence of multigrid methods, because a different edge-collapsing order changed the errors prolonged to the finer mesh. Error restriction and prolongation were two critical steps in the multigrid methods. If the residual error did not accurately downsample into the coarse level, the low-frequency error cannot be properly resolved. However, if the correction obtained from the coarse level did not faithfully prolong to the fine grid, the multigrid scheme became inefficient in the updating of estimation. In addition to the shortest-edge-first algorithm (SHORTEST), we evaluated three other edge-collapsing methods, namely, the Garland and Heckbert simplification algorithm with and without weighting according to the area of the triangles in the mesh (QUADRICTRI and QUADRIC, respectively) [11] and Melax’s polygon reduction algorithm (MELAX) [26]. As presented in Table 2, using the 3D multigrid snake by applying the shortest-edge-first algorithm was the most computationally efficient.

Table 2 A comparison of four simplification algorithms used in the 3D multigrid snake
Full size table

We demonstrated the effectiveness of using the 2D snake and 3D multigrid snake in eliminating ripple artifacts on the outer and inner surfaces (Fig. 8). The results showed that both the snake algorithms can successfully suppress the ripple artifacts to recover the smooth surfaces. However, the 3D multigrid snake was superior to the 2D snake in reducing the inner surface errors at local areas (white arrows in Fig. 8h), because the 3D snake updated the 3D surface mesh and ensured the overall congruency. The distribution of the surface errors resulting from the 3D multigrid snake also exhibited a lower median, lower 75 % percentile, and a smaller upper adjacent compared with the results of 2D snake (Fig. 9). Along with the computational efficiency of the 3D multigrid snake, we suggest that the 3D multigrid snake provides a superior alternative for eliminating ripple artifacts. We estimated the outer surface errors in the repaired skull portions using box plots to evaluate the recovered cranial appearances (Fig. 11). The results showed that the defective portion with the coverage over the posterior upper skull portions (e.g. the condition of the cross-midline 40 % skull loss in this study) may produce large outer surface errors because of insufficient image points at the top border of the skull. However, the other five skull defect conditions can be reconstructed using the proposed algorithm with the 3D multigrid snake to achieve maximal surface errors of ~1.15 mm (with a median lower than 0.30 mm). In summary, the redesigned reconstruction algorithm significantly reduced the computation time for cranioplasty, and the overall reconstruction was satisfactory for clinical use.

In our implementation of the 3D snake, the beta was not used, because the skull was a smooth surface without pits and, thus, only the alpha was used. We set the alpha to 20 after testing several orders of magnitude: 0.2, 2, 20, 30, 40, 50, 100, 200, and 2000. If the alpha was very large, the snake converged to an irregular shape. In contrast, when the alpha was very small, the snake converged slowly and remained close to the initial surface. However, the alpha values ranging from 2 to 50 produced comparable results.

Six skull phantoms with defects in different locations and sizes were repaired to assess the accuracy of skull reconstruction algorithm. The results showed that the skull implant models with inner-margin trimming can more effectively match the boundary of the defect portions on the phantoms (Fig. 10). Previous studies have reported that the pre-fabricated skull implants usually require manual trimming (in the order of several millimeters) costing a few minutes before or during surgery [1, 9, 33, 38]. The proposed image-trimming procedure provides a solution for facilitating cranioplasty and alleviating manual intervention. The phantom used in this study was created using a cranial CT volume acquired from a 19-year-old male subject. In addition, we chose the material for the phantom so that the density of the phantom was similar to real skulls. The phantoms were drilled using the same surgical devices as in the surgical operation. Accordingly, the scanned skull images on phantoms were comparable with real cases. Different from our skull phantoms, the heterogeneous surrounding tissues composed of cartilage, fluids, and brain tissues in real cases may result in regionally different sizes of bumped artifacts. However, the size of the bumped artifacts caused by partial volume effects has little effect on the recovered skull surfaces using the snake algorithm. Therefore, the reconstructed procedure proposed in this study is applicable to clinical data.

Using a snake model to recover the skull surface has its limitations. A diagnostic image with a resolution that is very low makes using the snake model difficult for the removal of ripple artifacts. Our experiments indicated that an axial resolution of at least 10 mm is necessary. We also noticed the effects of different image resolutions and proportions of incomplete contents on the performance of image registration. In our previous study [19], we designed a series of experiments for evaluating intra-subject head CT image registration using the skull as the matching feature; different image resolutions and volumes with incomplete contents were considered. Brain CT images with different axial resolutions from the same subject were acquired at 0.3, 1, 2, 3, 5, and 10 mm. Then, 25 to 75 % of the skull parts were artificially removed from the images of both subjects to simulate incomplete volume contents. We found that a successful registration can be achieved under two conditions: (1) more than half of the skull content is preserved; (2) the difference in image resolution between the two images is less than 16 times.

In applying the proposed algorithm, we used low-resolution diagnostic images to extract the patient’s own anatomical structure of the cranial defect for skull reconstruction. This method can prevent patients from having to receive two high-resolution CT scans within a short period (immediately before and after craniotomy), which may increase their risk of induced cancers caused by radiation exposure. For patients with elevated intracranial pressure caused by brain tumors or intracranial trauma, medical doctors suggest having brain CT scans for the purpose of surgical planning or diagnosis. However, the proposed method may not be applicable to patients without brain CT scans before the craniotomy.