Image processing, geometric modeling and data management for development of a virtual bone surgery system

Abstract

This paper describes image processing, geometric modeling and data management techniques for the development of a virtual bone surgery system. Image segmentation is used to divide CT scan data into different segments representing various regions of the bone. A region-growing algorithm is used to extract cortical bone and trabecular bone structures systematically and efficiently. Volume modeling is then used to represent the bone geometry based on the CT scan data. Material removal simulation is achieved by continuously performing Boolean subtraction of the surgical tool model from the bone model. A quadtree-based adaptive subdivision technique is developed to handle the large set of data in order to achieve the real-time simulation and visualization required for virtual bone surgery. A Marching Cubes algorithm is used to generate polygonal faces from the volumetric data. Rendering of the generated polygons is performed with the publicly available VTK (Visualization Tool Kit) software. Implementation of the developed techniques consists of developing a virtual bone-drilling software program, which allows the user to manipulate a virtual drill to make holes with the use of a PHANToM™ device on a bone model derived from real CT scan data.

• Virtual reality
• virtual bone surgery
• surgery simulation
• CT scan
• image processing
• geometric modeling
• data management

Introduction

Becoming a skillful surgeon requires rigorous training and iterative practice. For bone surgery, the student usually watches and performs many operations on cadaveric or synthetic bones under the tutelage of an experienced physician before actually performing a procedure on a patient under expert supervision. Mistakes during such procedures can lead to irreparable defects in the bone and surrounding soft tissue, which in the case of arthroplasty can in turn result in complications such as early loosening, mal-alignment, dislocation, and leg-length discrepancy [1]. Precise bone preparation is a key element for the successful long-term fixation of orthopaedic implants. The fit and fill of the implant is created by shaping and sizing a cavity within the bone to accommodate the implant. This is usually accomplished by standard material removal operations such as drilling, milling, and broaching.

The use of virtual reality (VR) for training in medicine is a growing research area. VR techniques provide the potential for a realistic, safe, and controllable environment in which medical students and novice doctors can practice surgical operations, allowing them to make mistakes without serious consequences. VR training also offers the possibility of a standardized performance evaluation for the trainees. We have taken the VR approach to develop a virtual bone surgery system by developing and implementing image processing, geometric modeling, graphic rendering, and haptic rendering techniques. The developed virtual surgery procedure is applicable to individual patients, so when the real surgery is performed, the surgeon will already be familiar with all the specific operations needed in the case. The input of bone geometry and material density to the simulator comes from real medical data such as CT scans, MRI, etc. We use the image data as the input for geometric modeling, graphic rendering, haptic rendering, and model update to perform the simulation of material removal.

Previous research on surgery simulation has covered a wide range of operations, and some simulators were developed especially to provide a virtual environment for training. For example, the VRMedLab networked facility at the University of Illinois-Chicago was designed to provide an educational resource for otolaryngology surgeons, enabling them to visualize the bone-encased structures of a temporal bone using interactive 3D visualization technology. The Ohio Supercomputer Center and the Ohio State University Hospital [2] developed an endoscopic sinus surgery simulator which provides the user with the capability for intuitive interaction with complex volume data and haptic feedback sensation.

In other virtual bone surgery research, Gibson et al. [3] presented an effort to develop an arthroscopic knee surgery simulator, using a volumetric approach to model organs, while Agus et al. [4] presented a haptic and visual implementation of a bone-cutting burr, which was developed as part of a training system for temporal bone surgery. However, few researchers have considered removal of bone material, which is an essential and integral part of a bone surgery operation [5], [6].

The simulation of material removal, such as drilling in bone surgery, can be achieved in a manner that to some extent resembles the virtual sculpting process for creating a 3D freeform object from a stock. It should be noted, however, that bone surgery simulation deals with inhomogeneous materials. Thus, in virtual bone surgery, material removal simulation is usually performed by volume modeling of the bone and continuous Boolean subtraction of the surgical tool model from the bone model [7–9].

Numerous papers have been published on visualization and rendering of medical image data [10–12]. However, they have mostly dealt only with model generation for static graphic display and have not addressed the issue of real-time model update. In the temporal bone simulation discussed in references [4] and [6], only a small portion of a temporal bone was used and the data size was not huge. Although there are papers discussing how to manage other kinds of data in real time [10], [13], the knowledge available from the literature on how to manage large medical image data for real-time simulation and visualization is still very limited.

The present paper describes the image processing, geometric modeling, and data management techniques that we have developed for simulation and rendering of bone surgery. Our main contribution concerns CT scan data management. The paper is organized as follows. First, the techniques of image processing, including feature extraction and region-based image segmentation, are presented. The paper then describes geometric modeling and graphic rendering to model the bone geometry from CT scan data and to update the model during the simulated surgical operation. This is followed by an explanation of the method of data management used to reduce computation time in order to achieve real-time visualization, considering implementation complexity, memory storage, and computational overhead. The paper then presents the results of implementing the described method with the development of a prototype virtual bone surgery system, and ends with a discussion of the implementation results and our future research plans.

Materials and methods

Image processing

Medical imaging data typically represent the values of some properties at various 3D locations [14]. CT scan data (rather than MRI data) are used in our research because they show good contrast between bones and soft tissues. An image processing procedure is used before performing the surgery simulation in order to save data processing time. The objective of image processing is to construct volumetric data represented by voxels from the images of CT scans. Due to noise in many signals and lots of irrelevant data in the CT scans, Gaussian filters and edge detection are used to process the image data slice by slice in order to remove noise in representing specific regions of a bone. Figure 1 shows an example of image data before and after processing. As shown, only a small portion of the slice is extracted to construct the bone's volumetric model and this is later used for collision detection, force generation, and model update in the bone surgery simulation.

Figure 1. Example of image data before and after processing.

After the data extraction, an image segmentation technique is used to divide the data into bony structures (femur, tibia, etc.), cartilage, tissues, and ligaments. A region-growing algorithm is then implemented for image segmentation as shown in Figure 2. The main idea behind this algorithm is to identify various regions in an image having similar features [15]. Briefly, the algorithm consists of the following steps: 1) After selecting a seed pixel within the image and comparing it with neighboring pixels, a region is grown from the seed pixel by adding those neighboring pixels that are similar; 2) Each pixel in the image receives a label from the region-growing process, and pixels are said to belong to the same region if they have the same label; 3) When the growth of one region stops, another seed pixel which does not yet belong to any previously identified regions is chosen and the region-growing process starts again; 4) This whole procedure is completed when all the pixels have been examined. During the implementation, a first-in-first-out queue, rather than a recursive stack, is used as the data structure to avoid memory/stack overflow.

Figure 2. Region-growing image segmentation algorithm.

Geometric modeling

Volume modeling is used to represent the bone geometry from the CT scan data. Compared with surface modeling, volume modeling allows representation of the internal structure of a 3D object, which is needed for virtual bone surgery because of the varying material density throughout the bone. In volume modeling, the basic elements are voxels [16]. A voxel can be represented by the coordinates of its center point plus some attributes. If the voxels have fixed dimensions, they can be represented by the vertices of a 3D lattice, which are characterized by their positions and the associated values of attributes. These attributes can represent physical properties such as density, material, stiffness, viscosity, etc., as well as display properties such as color and shading. A Hounsfield Unit (HU) value is used to represent the bone density of each voxel [17]. A sub-volume, which is a rectangular block of voxels, is used as a basis for developing techniques for efficient data management.

Voxel modeling has many advantages, such as unambiguity, heterogeneity, simplicity in Boolean operations, excellent morphological dexterity, and excellent local editability. However, algorithms based on elementary voxel modeling techniques with uniform voxel size often pose large memory storage and real-time performance issues [18]. How we address these issues will be described in the Data management section below.

Graphic rendering

Surface rendering is used as the graphic rendering technique. It is performed with a Marching Cubes algorithm [19], which extracts polygons from volumetric data. This traverses all boundary voxels of a volume model and determines the surface triangulation based on the values of the vertices of the voxels. The output of this algorithm is a triangulated surface representation of the 3D object. The memory requirement of the Marching Cubes algorithm depends on the resolution of voxels and is also related to the number of sub-volumes [20].

Data management

In developing a virtual bone surgery system, visualization quality and real-time display are essential. Challenging issues in processing the large data set include the following:

1. Memory. The volumetric data set from CT scans is commonly 128 × 128 × 128, but can be as large as 512 × 512 × 512. For the CT scan data used in our study, the size of each slice is 512 × 512 and there are more than 256 slices. If all the data is input as the source data, the set will have more than 67 × 10⁶ data points.

2. Preprocessing time. Because the data set is very large, the preprocessing of data before the surgery simulation may take a large amount of time.

3. Real-time performance. During the surgery simulation, the virtual tool will interact with the bone model when performing material removal. The data calculation and update, graphics rendering, haptic rendering, etc., will use a large amount of computational resources. If there are too many active voxels, it will influence real-time performance.

4. Resolution. The voxel size from the original CT data is 0.489 mm × 0.489 mm × 1.5 mm. This resolution may not be fine enough, but a finer resolution would demand an even larger data set.

Because a huge set of volumetric data is involved in the simulation, it is important to reduce, organize and manage the data well. Considering the volumetric modeling, graphics rendering, material removal process, complexity of implementation, storage and computational overhead, etc., we deal with the very large data set primarily by removing irrelevant input data and developing an efficient data structure. Two techniques, namely bounding volume and quadtree-based adaptive subdivision, are developed for these purposes.

Bounding volume technique

A volume buffer, or cuberille [21], is used to store volumetric data in the computer memory. After preprocessing the CT scan data, the volumetric model of a long bone is constructed with the use of a bounding box, called the object bounding box (OBB), as shown in Figure 3a. AABB (Axis Aligned Bounding Box) is chosen because of the CT scan setup in our study and the fact that this technique is easy to implement. The dimensions of the object bounding box are determined after finding the maximum and minimum values from the data processing to construct the bone model.

Figure 3. Bounding volumes of a bone: (a) object bounding box; (b) section bounding boxes. [Color version available online.]

The object bounding box of the bone may still contain many irrelevant data because a human's skeletal shape is irregular. Updating and rendering the data in the object bounding box is still time-consuming. Hence, a refined bounding volume technique is developed as shown in Figure 3b. The whole bone is divided into n sections along the Z direction. Each of these sections is bounded by a rectangular box called the section bounding box (SBB). To determine the X and Y dimensions of a section bounding box, we check the extreme X and Y values from the image data slice by slice, and then find the maximum and minimum X and Y values from these extreme values.

In order to save data loading time for the simulation, the image processing and the process of generating the section bounding boxes are carried out before the bone surgery simulation starts. The data of each section bounding box are saved into files, such as SBB1.dat, SBB2.dat,…, SBBn.dat, as shown in Figure 3b, and then reloaded as new input data before the simulation. These section bounding boxes become root sub-volumes for further subdivision using the quadtree-based adaptive subdivision method described next.

Quadtree-based adaptive subdivision

To enable simulation of bone material removal, the data needs to be updated at every time step. When the data are changed during the simulation process, the graphics need to be re-rendered for display. However, editing a whole object volume for display would be extremely time-consuming and impractical. It is desirable to update a substantially smaller volume in the display in order to achieve real-time performance. Instead of dealing with the entire volume, we deal with only the sub-volumes of interest at each time step. Thus, the data set being processed at each time step can be drastically reduced, and the system's real-time performance can significantly improve. Figure 4 shows the division of a complete model into uniform sub-volumes, with each sub-volume consisting of many voxels. The figure also shows a sub-volume designated as an active sub-volume when the tool enters its region. There is more than one active sub-volume when the tool is at the boundary of two or more sub-volumes, as illustrated on the right side of Figure 4. Only the active sub-volume(s) is updated in the display at each time instant during the simulation. This generates great time savings compared with updating the complete object model at every time instant.

Figure 4. Uniform division of a model into sub-volumes.

Despite the fact that the whole bone model has been divided into sub-volumes, the data set is often still too big to achieve real-time simulation when the uniform subdivision is used. Adaptive partitioning is used to deal with this problem. Quadtree subdivision is chosen as the adaptive partioning method, because the whole bone model has already been divided into sub-volumes with small dimensions in the Z direction.

The fundamental idea behind the quadtree subdivision technique is the divide-and-conquer power of binary subdivision [21]. A quadtree is derived by successively dividing both x and y dimensions to form quadrants from a section bounding box. Each quadrant may be full, partially full, or empty. A partially full quadrant is recursively subdivided into sub-quadrants. The subdivision continues until a predetermined resolution is reached. The successive subdivisions can be represented as a tree with the partially full quadrants as the internal nodes and the full and empty quadrants as the leaves. The subdivision of an SBB three times with the corresponding tree structure is illustrated in Figure 5. As shown in the figure, when the subdivision number is 1, all the quadrants are partially full; after it is subdivided twice, four “empty” sub-quadrants and three “full” sub-quadrants appear; during the third subdivision, we only need to consider the “partially full” quadrants resulting from the second subdivision. Usually, all the “partially full” quadrants are on the boundary of the bone model, and all the “full” quadrants are inside. The data for “empty” quadrants can be deleted during the subdivision process to further save memory.

Figure 5. An example of quadtree subdivision.

Data structure

A data structure is developed for the proposed techniques of image processing, bounding sub-volume, and quadtree subdivision. The processed image data with the bounding sub-volumes generated is treated as a new set of input data in the simulation, as shown in Figure 6. Each of the root sub-volumes (SBBs) is an object of a sub-volume class, and its data is stored in a LIST structure. Each SBB (from 1 to n) can be divided into smaller sub-volumes following the quadtree subdivision rule. These smaller sub-volumes are still objects of the sub-volume class.

Figure 6. Data structure for the proposed method.

During the bone surgery simulation, the data changes continuously when the virtual tool removes material from the bone model. The updated data is re-rendered for graphic display. Usually there is only one active sub-volume at any time instant. However, depending on the sub-volume size, the tool size, and the tool's position and orientation, multiple sub-volumes may exist at any instant. A sub-volume queue is used to manage the tool-bone intersection, using pushback and popfront to temporarily store the sub-volumes intersected by the tool.

During the process of simulating material removal, when the virtual tool intersects an active sub-volume having “partially full” or “full” quadrants at the maximal level of the tree (e.g., subdivision number = 3 is the maximum level in Figure 5), Boolean subtraction is performed on those quadrants. When the virtual tool intersects a “full” quadrant on an internal level of the tree, the “full” quadrant becomes a “partially full” quadrant because of the material removal. Boolean subtraction is performed on the full quadrant, and further subdivision is then done on the resultant quadrant till it reaches the preset level of subdivision. Boolean operations are then performed on those newly created sub-quadrants. To further reduce memory and increase efficiency, the empty sub-volumes are removed from the memory after each Boolean operation. The data structure shown in Figure 6 is then updated with deletion of some existing sub-volumes and generation of new sub-volumes.

Software implementation

The proposed techniques are implemented using C++ with VTK (Visualization Tool Kit) as the API, within the MS Visual C++ environment. The processed CT image data with sub-volumes generated by the quadtree subdivision is created before the simulation. A meta file is created to manage the data input and information such as names of data files, number of files, starting layer, divided status, etc.

Two C++ classes, CCTImageControl and CSub-volume, have been designed and developed. CCTImageControl is used to read the information from the meta file, construct the input image data files to the proposed data structure, and fulfill the search and update function. CSub-volume is a basic C++ class for the data structure. Each sub-volume shown in Figure 6 is an object of this class.

Results

The prototype virtual bone drilling system

The initial bone surgery simulation software that we have developed using the techniques described above provides the capability for both free-hand drilling and guided drilling. In guided drilling, the user can grip the virtual drill guide using the PHANToM™ device (SensAble Technologies, Inc., Woburn, MA) and position the guide to any desired location on the bone model shown on a graphic monitor. During guided drilling, the drill can move only in a certain direction constrained by the guide, thus possible damage to the bone can be avoided or minimized.

The user interface of the system is illustrated in Figure 7. The user can navigate the virtual drill and perform drilling operations on the bone model. The model is reconstructed from the CT images acquired from a real bone. Its boundary simulates the cortical bone structure, and its interior simulates the trabecular bone structure. Figure 8 provides an illustrated example of a simulated drilling operation on a femur model. The user can manipulate the virtual tool to carry out the desired hole-drilling. In the simulation, the virtual drill guide can be gripped and put in a proper drilling position using the PHANToM device. After positioning the guide, the drill can move only in the direction constrained by the guide. Figure 9 provides examples to illustrate simulation of guided drilling.

Figure 7. User interface of the virtual bone surgery system with the haptics device.

Figure 8. Illustration of material removal: the arrow indicates the direction of the drill movement. [Color version available online.]

Figure 9. Illustration of guided drilling: (a, b) gripping and positioning the guide; (c, d) drilling with the guide. [Color version available online.]

The developed prototype virtual bone drilling system offers a friendly GUI. The user can use a bone model generated from a set of patient-specific CT data to practice free drilling and guided drilling with visual and haptic feedback. There are still some limitations in the system, e.g., the PHANToM device we currently use is only capable of exerting 1.4 N of continuous force, but real bone drilling requires a force of 5–24 N [22]. A new haptic device will be needed in order to supply more realistic haptic feedback.

Effectiveness of the developed method

Several tests have been run to investigate the effectiveness of the developed method. One set of CT data (302 files with a total data size of 244 MB) from the bone shown in Figure 3 is used as the input data and the bone is divided into 14 sections for a bone drilling simulation. Table I shows that the total data files after using the bounding volume method, including first the OBB technique and then the SBB technique, are just 8.133 MB in size, which is only 3.33% of the size of the original data. The ratio of the total number of voxels of the reduced data, which is the sum of data from the 14 bone sections, over the original data is only 2.l2%. Using the reduced data, the processing time is only 1.89% of that when using the original data. Compared with the object bounding box shown in Figure 3a, the total data size and voxel number of the 14 section bounding boxes shown in Figure 3b have been reduced to 31.42% and 31.35%, respectively. These comparisons are given in Table II. Table III compares the numbers of sub-volumes resulting from the uniform division and the quadtree subdivision at different levels of subdivision for the 14 section bounding boxes of the bone model. The table also shows the ratio of sub-volumes for these two division techniques, indicating the memory savings generated by the quadtree subdivision.

Table I.  Comparisons among the original data, object bounding box (OBB) data, and sum of section bounding boxes (SBB sum) data.

File name	File size (KB)	Voxel number	Processing time (s)
Original data	243,901	72,069,396	136.24
OBB	25,883	4,869,460	5.18
SBB sum	8,133	1,526,400	2.16

Table II.  Various ratios among the original data, object bounding box (OBB) data, and sum of section bounding boxes (SBB sum) data.

	File size	Voxel number	Processing time
SBB sum/original	3.33%	2.12%	1.89%
OBB/original	10.61%	6.76%	3.81%
SBB sum/OBB	31.42%	31.35%	41.62%

Table III.  Numbers of sub-volumes and their ratio for different numbers of subdivisions resulting from uniform division and quadtree subdivision.

		Quadtree subdivision
No. of subdivisions	Uniform division	Full	Partially full	Empty	Ratio of sub-volumes
0	14	0	14	0	100%
1	56	0	56	0	100%
2	224	56	159	9	95.98%
3	896	56 + 134	334	9 + 168	58.48%

Discussion

We have described image processing, geometric modeling, and data management techniques for the development of a virtual bone surgery system. To address real-time performance and memory storage issues, a method for managing large CT scan data has been presented. In processing the CT scan data, a region-growing algorithm is implemented to remove the irrelevant data and extract different bone structures. An efficient data structure has been developed to store and organize the image data, which is processed before simulation so as to reduce the data processing and update time during the simulation.

The main contribution of this paper is the presented CT scan data management method employing bounding volume and quadtree subdivision techniques, as well as the concept of active sub-volume for graphic rendering. By using these techniques, the computer memory requirement and the data processing time are drastically reduced, enabling real-time bone surgery simulation. Compared to the more commonly used octree subdivision technique [4], [9], our method is more suitable for surgery involving long bones. Besides bone drilling, the use of other surgical tools (sawing, reaming, etc.) can also be simulated using the same data management method described in this paper.

The R&D efforts on virtual bone surgery thus far have rarely considered auditory rendering, which can play an important role in the generation of an immersive virtual environment. Sound cues can enhance visual and haptic feedback when a user is interacting with an object in a virtual environment. In bone surgery, sound can provide information about the nature of the tool-bone interface where the material removal operation occurs. Currently, we are conducting research in the area of sound modeling and rendering for bone surgery simulation. With the integration of tool-bone interaction sound and other effects such as bleeding, debris formation, fluid flow, etc., a virtual bone surgery simulation system will need more and more computation capacity. The presented data management method greatly reduces the computation and memory requirements, thereby increasing the reality level provided by the VR system.

We plan to evaluate the benefits of the multimodal simulator by conducting a user study after our virtual bone surgery system has been fully developed, and will develop metrics for the evaluation in consultation with experts in orthopaedic surgery.

Acknowledgements

The authors would like to express their sincere thanks to DePuy Orthopaedics, Inc., a Johnson & Johnson company, for funding this research. The project was also partially funded by the Intelligent Systems Center at the Missouri University of Science and Technology.