Srikumar Ramalingam
email: srikumar@cse.ucsc.edu

Suresh K Lodha
email: lodha¡@cse.ucsc.edu

Adaptive Enhancement of 3D Scenes using Hierarchical Registration of Texture-Mapped Models

Keywords: image registration, 3D model registration, scale-sensitive algorithms, 3D Reconstruction, hierarchical registration

Adaptive fusion of new information in a 3D urban scene is an important goal to achieve in computer vision, graphics, and visualization. In this work we acquire new image pairs of a scene from closer distances and extract 3D models of successively higher resolutions. We present a new hierarchical approach to register these texture-mapped 3D models with a coarse 3D texture mapped model of an urban scene. First, we use the standard reconstruction algorithm to construct 3D models after establishing 1-1 correspondence between the feature points of two images at same resolution. Next, a subset of these feature points is used to register the higher resolution image with the lower resolution image using a scale-sensitive algorithm. Finally we register and consistently merge the 3D models at different resolutions. We present the results of our hierarchical algorithm for adaptive enhancement of a mural inside the UCSC Campus by registering data that differ in scale by a ratio of 1:15. Results indicate that the proposed hierarchical registration technique effectively utilizes the intermediate models to enable the smooth registration of the high resolution models on the coarser models.

Introduction

Construction of 3D urban models is increasingly important in a variety of applications including urban planning, environmental monitoring, emergency relief scenarios, geospatial intelligent information visualization, virtual reality, and augmented reality. Many researchers have constructed 3D urban models from two or more images taken by handheld cameras or a variety of sensors [START_REF] Bosse | Eyes of Argus: georeferenced imagery in urban environments[END_REF][START_REF] Fruh | 3D model generation for cities using aerial photographs and ground level laser scans[END_REF][START_REF] Allen | Automated site modeling in urban environments[END_REF][START_REF] Fitzgerald | Virtual reality meets GIS: Urban 3D modeling in South Carolina[END_REF][START_REF] Wasilewski | From urban terrain models to visible cities[END_REF]. Typically, these models are constructed at a fixed resolution. In some cases, researchers have also constructed a highly detailed model of interior environments where dense set of images is acquired using mobile robots from various distances [START_REF] Camillo | Videoplus: A method for capturing the structure and appearance of immersive environments. 3D Structure from Images-SMILE[END_REF][START_REF] Aliaga | Sea of images[END_REF]. A more likely scenario in outdoor 3D environment reconstruction is the acquisition of data using a variety of sensors during a short period of time to construct a model and then periodically update the model based on newly captured information using inexpensive hand-held sensors by mobile agents in outdoor environments.

In this paper we address one aspect of this adaptive fusion of new information -namely, the problem of enhancing the resolution of urban models by taking additional image sequences for specific sub-scenes. We acquire additional image sequences of a sub-scene from closer distances using a hand-held camera (see Figure 1) and extract 3D models at higher resolutions. The left diagram of Figure 2 shows that most of the existing registration approaches for 3D reconstruction of large scenes focus on collecting overlapping models at similar resolutions and mosaic them. The right diagram of Figure 2 shows our approach where the registration is needed at different scales. The challenge is to fuse the higher resolution images and models with the existing coarser level images and models. We achieve our goal through a hierarchical registration technique which utilizes the image properties of the intermediate data. We have constructed a coarse texture-mapped 3D urban model of a small region of UCSC campus using techniques similar to ones employed by other researchers [START_REF] Fitzgerald | Virtual reality meets GIS: Urban 3D modeling in South Carolina[END_REF][START_REF] Wasilewski | From urban terrain models to visible cities[END_REF] More specifically, the elevation for the terrain is obtained using Digital Elevation Models (DEMs) freely available from USGS (United States Geological Survey). Elevation of the buildings is determined using LiDAR data, which we obtained using airborne sensors. High resolution aerial imagery obtained from local sources is texture mapped on the terrain. Finally, low resolution imagery for walls is obtained using a hand-held camera and texture mapped on the side walls using standard image processing operations involving image warping and mosaicing. The bottom diagram of Figure 12 shows the results of such a coarse texture-mapped 3D model of Thimann Labs area inside the UCSC campus. We then acquired additional image pairs of a mural embedded inside this model from closer distances using a hand-held camera (see Figure 1). The focus of this work is to describe an algorithm to hierarchically register these additional images and extracted 3D models with this coarse model.

Background and previous work

In this section we review previous work on outdoor environments reconstruction, 3D reconstruction from images, registration using image and geometry features including scale-sensitive registration.

Urban scene reconstruction

Large scale urban scene reconstruction has emerged as a very important problem in recent years [START_REF] Wasilewski | From urban terrain models to visible cities[END_REF]. Faugeras et al. [START_REF] Faugeras | 3D reconstruction of urban scenes from sequence of images[END_REF] present a method of constructing 3D Euclidean models of urban scenes from a sequence of aerial images using uncalibrated cameras. Ribarsky et al. [START_REF] Wasilewski | From urban terrain models to visible cities[END_REF] describe a semi-automated urban construction approach using aerial or ground images and utilize shadow cues, counting floors and other factors. Fitzgerald et al. [START_REF] Fitzgerald | Virtual reality meets GIS: Urban 3D modeling in South Carolina[END_REF] have constructed 3D urban models using building footprints and LiDAR height data. Footprints are used to identify building locations and the LiDAR height information associated with points inside the building polygons are used to extrude buildings and assign heights to them. Images of the building walls are captured using digital camera and perspective distortions are corrected before pasting the images on the extruded building walls. As stated before, we have used a similar approach to construct the coarse level 3D model of a region inside the UCSC campus.

There are several efforts underway to construct large scale environments using a variety of sensors including GPS devices, omni-cameras, and range sensors. Bosse et al. [START_REF] Bosse | Eyes of Argus: georeferenced imagery in urban environments[END_REF] describe a system called argus which is a mobile platform fitted with high resolution digital camera, a GPS unit, orientation trackers and and is capable of capturing multiple georeferenced images of the urban scenes from various orientations and distances. Image registration and mosaicing is achieved by fusing complementary GPS, inertial sensors and odometry data through Kalman filtering. The authors also employ offline image-based registration techniques to refine pose estimates [START_REF] Mellor | Geometry and texture from thousands of images. 3D Structure from Images-SMILE[END_REF]. Allen et al. [START_REF] Allen | Automated site modeling in urban environments[END_REF] describe an urban modeling system where the data is acquired using a GPSequipped range sensor. Frueh et al. [START_REF] Fruh | 3D model generation for cities using aerial photographs and ground level laser scans[END_REF] also describe an urban modeling system where the data is acquired using a range sensor and path calibration is done using aerial imagery. Omni-directional sensors have been utilized to capture and create structure of complex indoor environments [START_REF] Camillo | Videoplus: A method for capturing the structure and appearance of immersive environments. 3D Structure from Images-SMILE[END_REF][START_REF] Aliaga | Sea of images[END_REF]. None of these projects seem to have utilized scalesensitive image or model registration in their work.

3D reconstruction from images

Extraction of depth information from images is a well known computer vision problem [START_REF] Xu | Epipolar Geometry in Stereo, Motion and Object Recognition-A Unified Approach[END_REF]. Figure 3 shows the standard pipeline for extracting 3D information from a pair of images using a calibrated camera. We have utilized this pipeline to generate 3D models from an image pair. We have used the work of Zhang [START_REF] Zhang | A flexible new technique for camera calibration[END_REF] for camera calibration using a fixed pattern. The steps in 3D reconstruction are: (i) extraction of feature points using Harris corner detection algorithm in both the images, (ii) computation of correlation score for each pair of feature points, and categorizing each pair as a possible match if the score exceeds a certain threshold (this step may yield many-to-many correspondences), (iii) computation of match strength and utilization of relaxation strategies to remove false matches, (we have used some winner take all stragety for relaxation), (iv) using epipolar geometry along with a non-linear algorithm (least-median-of-squares) to remove outliers and select a set of robust matches, and compute camera motion parameters, (v) using back projection (also known as triangulation) to determine the corresponding 3D points, and (vi) finally, bundle adjustment to refine the 3D points and the camera motion parameters (translation and rotation) and improve the accuracy of the final 3D models. In our work we perform the bundle adjustment by computing the reprojection error (the error between the 2D feature points and the reprojected feature points from 3D points) and minimiz- ing it using the Levenberg-Marquardt iteration. These 3D points are then triangulated and texture-mapped to produce texture-mapped 3D models (see Figure 4). 3D reconstruction from multiple images has also been achieved [START_REF] Pollefeys | 3D modeling from images[END_REF]. Our work focuses on registering images and models at different resolutions. We now describe the previous work related to the two main approaches to register images and models -namely using image or geometry.

Registration using image features

The problem of matching two images where the viewpoints differ by small offsets in position, orientation, and viewing parameters such as focal length has been a well-studied problem for more than two decades. Several authors have also addressed the problem of matching two images gathered from two very different viewpoints but they did not consider a large change in resolution [START_REF] Georgis | On the correspondence problem for wide angular seperation of non-coplanar points[END_REF][START_REF] Pritchett | Wide baseline stereo matching[END_REF][START_REF] Tell | Wide baseline point matching using affine invariants computed from intensity profiles[END_REF][START_REF] Tuytelaars | Matching of affinely invariant regions for visual servoing[END_REF]. The low-high resolution image matching task consists in finding a small region in the low resolution image that can be assigned to the high resolution image. Even an assumption of planar projective transformation between the two images leads to a very large search space and the associated non-linear minimization procedure has to deal with a four-parameter cost function [START_REF] Gruen | Adaptative least squares correlation: a powerful image matching technique[END_REF]. Hansen and Morse [START_REF] Hansen | Multiscale image registration using scale trace correlation[END_REF] describe a method based on point-to-point correspondences where they are able to recover the scale factor between the two images but they cannot deal with camera motions. Our scale-sensitive image-based registration work (described later in Section 3) is perhaps most closely related to the recent work by Dufournaud et al. [START_REF] Dufournaud | Matching images with different resolutions[END_REF], where they are able to match images differing in scale by a factor of up to 5. They obtain point-to-point correspondences using a scale-sensitive Harris Corner's detection algorithm. Our work differs from theirs in at least two important ways. First, we introduce a scale-sensitive image registration algorithm, the motivation for which is described further below. Second, we match both images and models at different resolutions. We achieve this by ensuring that features points in 1-1 point correspondences obtained by matching images at different resolutions (say high-res image 1 with low-res image 1) are a subset of the feature points in the 1-1 point correspondences obtained by matching images at same resolutions (say high-res image 1 and 2 and low-res image 1 and 2). Therefore, instead of applying scale-sensitive Harris Corner detection algorithm, we start with already discovered robust 1-1 point correspondences between images at same resolutions (see Figure 5) and then look for a subset of these matches using a scale-sensitive image registration to match images at different resolutions. Due to our requirement of subset of matches, we are able to match images at different resolutions that differ by a factor only up to 2, but we are able to boot-strap this method to hierarchically register several layers of both images and models. In Section 4, we present an example where we register 7 layers so that the scale ratio between the lowest and highest resolution images is approximately 1:15. We are able to carry out this hierarchical registration for several layers because the number of robust final matches after subsetting seems to be much higher at ratios of 1:2 than at higher scale ratios such as 1:5.

Registration using geometry

An alternative to image-based registration between images and models is to first register 3D models at different resolutions and then try to match images (reverse process of what we are trying to do in this work). The most popular and successful geometry-based registration approach is the ICP (iterative closest point) algorithm introduced by Besl and Mckay [START_REF] Besl | A method for registration of 3D shapes[END_REF]. Several efficient variants of this algorithm are [START_REF] Rusinkiewicz | Efficient variants of the icp algorithm[END_REF]. The variants are introduced by affecting one of the following six stages in the ICP algorithm: selection of the points in the data set, matching the points in one mesh with the points in other mesh, weighting of the corresponding pairs, rejection of certain pairs, assignment of error metric and finally the minimization of the error metric. The ICP algorithm and its variants has primarily been used in alignment of 3D information obtained directly from 3D scanners. It seems that most of the existing literature focuses on registration of 3D point clouds at similar resolution. One of the limitations of this technique is the computation of the initial state vector, which plays a major role in avoiding local minima problem. If the scale between two models is not known a-priori, it is not clear how to extend this algorithm to scale-sensitive model registration. Nevertheless, this approach has some merits and we have explored this venue to a limited extent as described in Section 3.2.

Algorithm

The proposed algorithm for hierarchical registration of texture-mapped models when data is acquired from image pairs at successively higher resolutions can be described in four major steps. The first step is the 3D model reconstruction from images at similar resolution using the standard techniques illustrated in Figure 3 and described briefly in Section 2.2. The second step is the scale-sensitive image registration algorithm described in Section 3.1 and illustrated in Figure 5. The third step is the registration of 3D models at different resolutions and mesh merging described in Section 3.2. The fourth and the final step is the hierarchical boot-strapping of the first three steps of this algorithm that allows us to register several layers of data on the initial coarse model. Results of applying the hierarchical registration are described in Section 4.

Scale-sensitive image registration algorithm

In order to register images at different resolutions, we have introduced a variation to the well known feature correspondence algorithm (presented in Figure 3 and described in Section 2.2) by introducing a scale-sensitive correlation score computation and scale-sensitive match strength computation that we describe below. As shown in Figure 5, the input to the correlation score computation algorithm is (i) feature points ¢¡ found in one (say left) image of a high resolution image, (ii) feature points ¤£ found in the same (left) image of a low resolution image. Subsequent steps are performed only on these pairs of feature points.

Correlation score computation: Rather than using the correlation windows of same size, here we introduce a scaling factor ¥ to correlate a window of size ¥ §¦ by ¥ ©c entered at © with another window of size ¦ by ¨centered at "! # $! % , as shown in the top diagram of Figure 6. Let ¦ & ' and ¦ (! 0) are the corresponding feature points located at 1 and ! 2 ! respectively. The scaling correction factor ¥ , which is a fractional value between 0.0 to 1.0, is applied to the image at higher resolution.The modified expression for computing the correlation score ¢¡ £ ¥¤ §¦ © with the scaling correction is as follows:

! #" " %$ & (' ) ¢0 !1 ) 32 ¡ 54 ¥6 7 ) 32 ¡ 98 A@ ©B & ' ) 0 !1 ) 6 7 ) @ DC $ & FE 0 !1 E 2 4 G6 7 E 2 8 A@ ©B & ©E 0 !1 E 6 7 E @ DC 0 !H §I 2 QP @ 0 !H §R 2 SP @ 9T U E 0 & ' ) @ GU E 0 & ©E @ where V

Match strength computation:

The previous step of correlation score computation may yield many-many correspondences between feature proints. The idea of match strength computation is to select a 1-1 correspondence from the set of candidate matches. In order to deal with images at different resolutions, we scale one of the neighborhoods and modify the distance formula as described below. Consider a match The remaining steps of the algorithm -relaxation strategy, use of epipolar geometry along with a least-squares-ofmedian algorithm to remove outliers, obtain a robust set of matches and compute camera motion parameters -remain the same. In order to find the optimum scale ratio, we discretized the values of from 0.5 to 1.0 with an increment of 0.1 and maximized the number of robust matches for appropriate correlation thresholds (see Figure 7). The top row of Figure 8 shows the final outcome of this stage of the algorithm.

Scale-sensitive 3D Model Registration

The end result of the previous step is a set of robust 1-1 correspondences between 2D feature points of a highresolution and a low-resolution image. Since these feature points are a subset of feature points used in 3D model construction, we use the standard back projection (also known as triangulation) to obtain the correspondences between the 3D points of high and low resolution models (see the bottom row of Figure 8).

We now need to find the scaling, rotation, and translation vectors in three dimensions to register the two models. We first compute scaling factor ( ) between the two models as follows. For every possible pair £ G¤ ¦ © , we compute the scale factor based approach. We then use the scale computation [START_REF] Berthold | Closed-form solution of absolute orientation using unit quaternions[END_REF]:

¢¡ ¤£ ¥ §¦ © ! #" %$ £ ¥ '& )( 0 # 1 ! #" %2 £ ¡ '& ( 3 (
, where 4 ¥ and 4 ¡ refer to the centroids of the 3D points in low and high resolution models. Now we use the standard quaternion approach [START_REF] Berthold | Closed-form solution of absolute orientation using unit quaternions[END_REF] to compute the rotation and translation vector to minimize the least squares error between the 3D points of the two models.

We also attempted to improve the registration of 3D models at different resolutions further by applying the ICP (iterative closest point) algorithm. However, we learned that the image based registration was already very accurate and the improvements were very marginal. However, it is possible that ICP algorithm can improve results further in additional scenarios, and we plan to investigate them in future.

Mesh Merging

We now have a high resolution mesh registered and superimposed over the low resolution mesh. We now describe a mesh merging approach in which we merge these two meshes with overlapping region to obtain a single consistent mesh. Table 1: Classification of intersections of a triangle from outer low-resolution mesh with the convex hull of the inner mesh First, the convex hull of the high resolution mesh is computed and superimposed on the outer low resolution mesh (see the top left diagram of Figure 11). Next, (i) the triangles in the low resolution mesh which are completely inside the convex hull are eliminated, (ii) the triangles in the low resolution mesh which are completely outside the convex hull are preserved, (iii) the triangles in the high resolution mesh that do not share an edge with the convex hull are also preserved. The main task lies in splitting and retriangulating the triangles belonging to both the low-res and high-res mesh in the overlapping regions (see the top right diagram of Figure 11).

Possible intersections of a low-res triangle and the convex hull are summarized in Table 1. There are three pos- The above process introduces intersections points of the newly triangulated low resolution mesh with the edges of the convex hull. At these intersection points, we change the depth values of the high resolution mesh to the depth values of the low resolution mesh to avoid any holes in the finally merged single mesh. In addition, the triangles of the high resolution mesh sharing the boundary edge are also retriangulated (Tri-4 scenario shown in the right most diagram of Figure 10.)

Results

The proposed algorithm in this paper is tested on real data sets by taking images obtained using a Sony digital camcorder. We used Zhang's easy camera calibration tool [START_REF] Zhang | A flexible new technique for camera calibration[END_REF] to calibrate the camcorder. We have used Matlab for implementing most of our algorithms. We have used OpenGL libraries and C++ programs to render and view the texture-mapped models.

We have conducted experiments with several data sets. Here we present the results for the mural data. We constructed seven models at different resolutions. The coarsest resolution model (H1), which is a part of the coarse 3D texture mapped 3D urban model, was built and registered using the techniques described in Section 1. All intermediate resolution models (H2 to H6) and the highest resolution model (H7) were built using the algorithm described in Section 2.2 (see Figure 12). Statistics are summarized in Table 2. Although the initial reprojection error was very high for H5model because the two images used in the 3D reconstruction differed by a very small rotation, which is not very good for the working of the 3D reconstruction algorithm using epipolar constraint. However there was a significant improvement after using bundle adjustment algorithm.

Statistics for registering a high resolution image and model with the next lower resolution image and model using the algorithm described in Section 3 are summarized in Table 3. In our experiments, we found that the image registration algorithm works well for scale ratios of up to .5:1. Although a more fine sampling of the scale ratio may have an improvement in the number and robustness of the matches, we found that this improvement is not critical in registration vector computation for 3D model registration. Since the texture mapping is perfomed finally on the registered 3D models, it is the accuracy of the registration of 3D models that matter and not the initial estimate of the scale ratios between the images at different resolutions. We can also adaptively enhance or simplify the scene by registering or removing the intermediate models based on the viewpoint and the resolution of the scene. The mesh merging algorithm can jump across the hierarchy so that one can merge only the required models. For example, it is possible to merge and texture map H2, H5, H6 and H2 models only (see bottom row of Figure 13).

Conclusion

We have proposed and implemented a hierarchical algorithm for registering images and models at different resolu- tions. For the case of mural, we have demonstrated that we are able to hierarchically register the data with an approximate scale ratio of 1:15. There is no inherent limitation in the proposed algorithm to carry this further with even higher scale ratios so long as the successive ratios between the two layers is approximately 1:2. We plan to investigate scale-sensitive algorithms further to remove this constraint.

Figure 1 :

 1 Figure 1: A schematic diagram showing the locations from where the images are captured. The image from location 5 is used to construct the coarsest model H-1. Images from locations 3 and 4 are used to construct the H2-Model. Additional image pairs are captured from successively closer locations.

Figure 2 :

 2 Figure 2: Left: most registration approaches use overlapping images for mosaicing. Right: adaptive registration at different scales used in this work.

Figure 3 :

 3 Figure 3: 3D reconstruction from two images of similar resolution

Figure 4 :

 4 Figure 4: 3D texture-mapped high resolution model of a part of the mural.

Figure 5 :

 5 Figure 5: One step of the hierarchical registration of low-resolution images and models with high-resolution images and models

Figure 6 :

 6 Figure 6: (top) Correlation score computation, and (bottom) match strength computation between feature point pairs in two images at different resolutions.

  correlation score between the feature points a P 4 and a wH 8 exceed a certain threshold x then match, otherwise not.

8 ,

 8 where a P 4 and a wH 8 are the feature points in first and second image respectively. We consider a neighborhood y £ a H 8 of radius around the feature point a wH 8 and a neighborhood y ¡ £ a P 4 of radius ¢ around a P 4 . Let i P A and i H A refer to the feature points belonging to the neighborhoods y is the threshold on the relative distance difference.

Figure 7 :

 7 Figure 7: Number of matches selected for different values of s using different correlation thresholds in the scalesensitive image matching algorithm. We select s=0.7 for this case because it clearly outperforms other scale factors in terms of number of robust matches for different values of thresholds.

Figure 8 :

 8 Figure 8: (top row) 73 robust matches between a high-res and a low-res image; (bottom row) feature points occurring in the scale-sensitive image registration algorithm (shown in drak) are a subset of feature points found during the 3D reconstruction of the respective models.

Figure 9 :

 9 Figure 9: Possible intersections between a low-resolution triangle and the convex hull of high-resolution mesh.

Figure 10 :

 10 Figure 10: Retriangulations (from left to right): Tri-1 scenario, Tri-2 scenario, Tri-3 scenario, and Tri-4 scenario.

Figure 11 :

 11 Figure 11: (top left): high and low resolution meshes superimposed, (top right): intersecting regions where the triangles need to be split and retriangulated, (bottom left): intersecting region after splitting and retriangulation to obtain a consistent mesh, (bottom right): consistently merged high and low resolution mesh.

Figure 12 :

 12 Figure 12: Images and corresponding 3D triangulated models at six levels of hierarchy to be registered on the coarse urban scene at the bottom.

Figure 13 :

 13 Figure 13: Registered, mesh-merged and texture-mapped models (top row) H-5, H-6, and H-7, (bottom row) H-2, H-5, H-6, H-7

Table 2 :

 2 5, H-6, H-7 Construction of 3D Models (H-2,3,4,5,6,7) using image pairs: SM=matches after match strength computation, RM=matches after relaxation strategy, EM=robust matches after applying epipolar constraint, IE=Initial reprojection error, FE=final reprojection error after bundle adjustment.

	I	FP	SM RM EM IE	FE	¡ £¢ ¥¤ §¦
	H2-1 1027 H2-2 961	879 366 252 0.8080 0.185
	H3-1 1650 3175 682 583 0.6677 0.074 H3-2 1611
	H4-1 1292 H4-2 1287	961 706 680 0.1299 0.13362
	H5-1 1098 2009 656 607 5.7771 0.14353 H5-2 1045
	H6-1 H6-2	978 2429 602 562 0.8929 0.1666 957
	H7-1 1526 2166 765 674 0.7876 0.1841 H7-2 1528

Table 3 :

 3 Scale-sensitive image and model based registration for six levels of hierarchy: I=images, FP=feature points, s=scale ratio, RM=matches after relaxation strategy, EM=robust matches after applying epipolar constraint, S=scale for 3D registration, E=Least squares registration error

	I	FP	s RM EM	S	E
	H1-1 H2-1	197 252	0.70	58	40 176.8824 0.0003
	H2-1 H3-1	252 583	0.70	89	73 109.2049 0.0010
	H3-1 H4-1	583 680	0.80	76	57	35.3214 0.0018
	H4-1 H5-1	680 607	0.50	45	45	28.5310 0.0164
	H5-1 H6-1	607 562	0.70	26	22	15.4088 0.0004
	H6-1 H7-1	562 674	0.50	12	11	7.7527 0.0025

¥6 8 k f 0 ! P 6 P @ f 0 ! %H 6 H @ . We first use this scale factor to remove the ourliers using a histogram-


Gabor Fichtinger

Anton Deguet

Ken Massamune

Emese Balogh

Gregory Fischer

Hervé Mathieu

Russell H Taylor

Laura M Fayad

James Zinreich

Ken Masamune

Herve Mathieu

S James Zinreich

Needle Insertion in CT Scanner with Image Overlay -Cadaver Studies

An image overlay system is presented to assist needle placement in conventional CT scanners. The device consisting of a flat LCD display and a half mirror is mounted on the gantry. Looking at the patient through the mirror, the CT image appears to be floating inside the patient with correct size and position, thereby providing the physician with two-dimensional "X-ray vision" to guide needle placement procedures. The physician inserts the needle following the optimal path identified in the CT image that is rendered on the LCD and thereby reflected in the mirror. The system promises to increase needle placement accuracy and also to reduce X-ray dose, patient discomfort, and procedur e time by eliminating faulty insertion attempts. We report cadaver experiments in several clinical applications with a clinically applicable device.

Introduction

Numerous studies have demonstrated the potential efficacy of CT -guided percutaneous needle-based therapy and biopsy in a wide variety of medical problems. The process of needle insertion is relatively straightforward, but there is significant variability among practitioners, in terms of accuracy and procedure time. Typically, the CT images are shown on the scanner's console outside the room, and then physician must mentally register the images with the anatomy of the actual patient and use hand-eye coordination to carry out the intervention. To address these problems, a variety of tracked navigation systems and surgical robots have been investigated; all resulting in systems that are prohibitively complex and/or expensive for routine clinical use. A variety of virtual reality methods, such as head-mounted displays [START_REF] Sauer | An Augmented Reality Navigation System with a Single-Camera Tracker: System Design and Needle Biopsy Phantom Trial[END_REF][START_REF] Birkfellner | A head-mounted operating binocular for augmented reality visualization in medicine -design and initial evaluation[END_REF], video projections [START_REF] Grimson | An Aut omatic Registration Method for Frameless Stereotaxy, Image Guided Surgery, and Enhanced Reality Visualization[END_REF] , and volumetric image overlay [START_REF] Blackwell | An Image Overlay Sy stem for Medical Data Visualization, First International Conference on Medical Image Computing and Computer-Assisted Intervention[END_REF] have been investigated. Unfortunately, all such 3D augmented reality systems, without exception, require elab orate calibration, registration, and spatial tracking of all actors and components; a rather complex and expensive engineering entourage. In the pursuit of simpler image overlay systems, our group [START_REF] Masamune | Threedimensional Slice Image Overlay System with Accurate Depth Perception for Surgery, Third International Conference on Medical Image Computing and Computer-Assisted Intervention[END_REF][START_REF] Masamune | An Image Overlay Sy stem with Enhanced Reality for Percutaneous Therapy Performed Inside CT Scanner[END_REF] and concurrently Stetten [START_REF] Stetten | Magnified Real-Time Tomographic Reflection[END_REF][START_REF] Stetten | C-Mode Real Time Tomographic Reflection for a Matrix Array Ultrasound Sonic Flashlight[END_REF] have been investigating 2D image reflection produced in a semitransparent mirror. This technique provides an optically stable 2D reflection i mage without auxiliary tracking, requiring only a simple pre-operative alignment. As the majority of needle placement procedures are executed "in-plane" (i.e. when the needle is completely contained a single CT slice), giving up 3D rendering for engineering simplicity and low cost is a most reasonable tradeoff. This paper describes a clinically deployable embodiment of the Masamune-Stetten concept, optimized for needle placement procedures in conventional CT scanners. In particular, we report new hardware, advanced display software, and the results of cadaver studies. Approval is being sought to begin human trials.

System Design

A flat LCD display a nd a semitransparent mirror are mounted on the gantry of a CT scanner (Figure 1) A CT slice is acquired and render ed on the display. The display is positioned with respect to the mirror so that the reflection of the CT image in the mirror coincides with the patient's body behind the mirror (Figure 2), as was described in [START_REF] Masamune | An Image Overlay Sy stem with Enhanced Reality for Percutaneous Therapy Performed Inside CT Scanner[END_REF]. The overlay is mounted on the gantry, so it tilts with it, if necessary. In many needle placement procedures, after the entry point is selected with using skin fiducial markers, three degrees-of-freedom (DOF) motion of the needle needs to be controlled. The physician uses the overlay image t o control the in-plane insertion angle (1 st DOF), while holding the needle in the axial plane marked by the gantry's laser light (2 nd DOF). The insertion depth (3 rd DOF) is marked on the overlay image. In our proof-of -concept prototype [START_REF] Masamune | An Image Overlay Sy stem with Enhanced Reality for Percutaneous Therapy Performed Inside CT Scanner[END_REF], the overlay image was created in the imaging plane of the scanner, which allowed for rapid imaging update, but it prohibitively constrained the workspace. The new device uses the outer laser plane of the scanner. While this arrangement provides a conveniently large workspace, it also requir es moving the table between imaging and insertion, which is altogether an acceptable trade-off.

The procedural workflow is as follows. The patient is externally marked with IZI CT Biopsy Strip (IZI Corporation, Baltimore, MD). We acquire a CT volume of i mages, with a slice thickness a ppropriate for the given application. The plane of insertion is identified and the slice of interest is transferred to the planning and display software running on a Windows-XP laptop. The entry and target points are picked in the CT image, a visual needle guide is displayed, and the scene is pushed to the overlay display as it will be seen later in the left panels of Figure 7 . The CT table is translated out by the known offset between the slice of interest and plane of the overlay. The physician places the needle tip at the entry point and lines it up with the visual insertion guide seen in the mirror, while holding the needle in the plane of the laser (Figure 1.) T he skin fiducials are visible on both the patient and in the ove rlay image and coincidence between the corresponding marks indicates correct alignment. This feature is particularly useful when the target anatomy is prone to motion due to respiration or mechanical force. (This was not found to be a limiting factor in cadaver studies , however.) Usually, a confirmation image is acquired after insertion, as we show later in Figures 6,7, and 8.

Display Software and Registration

In the current embodiment, pre-operative calibration, insertion planning, a nd display image generation are all performed on a stand-alone Windows XP laptop computer. The CT image of interest (containing the target) is transferred from the scanner's distribution server to an ordinary DICOM receiver client running on the laptop. The laptop concurrently drives the flat panel LCD display of the overlay device, for which the image is flipped horizontally so that the mirror would flip the image back to normal lateral polarity. The insertion planning component is kept simple and intuitive, in order to speed up the process. For the sake of simplicity and speed, we refrain from 3D scenes altogether, which is also reasonable for a 2D overlay device. In the interactive display, the physician can select a sub-image of interest, for which the m agnification, display, and level can be adjusted. The target and entry points are assigned by two mouse-clicks. A visual needle guide and ruler automatically appear on the screen. The com puter flips the scene, and after ensuring correct magnification and orientation, pushes the image to the overlay display. The length of the virtual needle guide is twice the depth of insertion. The physician holds the needle at the entry point behind the mirror and adjusts the height of the grip to match with the proximal end of the virtual needle guide. This posture allows the physician confidently insert the needle with a single stroke along to the marked trajectory , without the risk of overdriving (Figure 3.) Before use, the display, mirror, and scanner must be aligned. The angle of the display and mirror are fixed with respect to one another and an adjustable arm is used to set up the display-mirror unit with respect to the CT laser. For the in-plane registration a phantom made of a 10 mm thick acrylic board containing a set of 5 mm diam eter aluminum pegs is mounted in the overlay plane. A CT image of the pegs is acquired and rendered on the overlay display as seen in Figure 4. The m agn ification, in-plane rotation, and translation are adjusted until each aluminum peg coi ncides with its mark in the CT image.

Calibration has a decisive impact on the system's perform ance; thus this step must be robust to algorithmic and human errors, while still simple and fast. The marks of the aluminum pegs are auto-segmented in the phantom's CT image and then the technician leans over the mirror and selects the points where the pegs appear in the mirror. From these we calculate the in-plane translation and rotation and then cor rect the overlay image. The combined effects of human and optical errors were analyzed on synthetic data, with the objective to determine the optimal number, distribution, and selection order of registration points. We artificially misaligned the two sets of points (i.e. the pegs and their respective image coordinates) by applying a known transfo rmation on each pair and adding noise to each data point, as explained in Figure 5a. Let Q and R be the corresponding points to register in CT and real space. To simulate the error induced by the user and the physical property of the semi -transparent glass, we add some "noise" to the position of R, obtaining point P. We register P to Q getting a rigid-body transformation T reg . Using this transformation, we transform R obtaining S. Therefore, the system error is the distance bet ween points S and Q. Human error was simulated by adding a random value (±2 pixels) to the pos ition of the point to be registered. Parallax error from the mirror may induce a significantly large error. At d=4 mm thickness and α=30° view angle and using the formulas derived in Figure 5b , the parallax error is about x=1.28 mm, the effect of which fortunately can be substantially reduced by altering the view point during the calibration process. We also concluded that iterative re-registration more favorable t han collecting all registration points first and then calculating a single global registration. This observation was true across the range of practically relevant amplitudes and distributions of noise and number of registration points. The best strategy was found to be the following: (5) Repeat the pair-wise process until sufficient registration is observed between the phantom and its CT image. It is particularly important to compensate for the parallax error by altering the viewpoint. The registration error, using four pairs of registration points and assuming ±2 pixel human error was 1.23 mm (STD=0.31) at 30° view angle and 0.74 mm (STD=0.21) at perpendicular view (α=0°). This performance appears to be sufficiently accurate for most CT-guided needle placement procedures.

Experiments and Results

Body Phantoms: A male body phantom was fabricated by attaching three cm-thick tissue-equivalent bolus material (Harpell Associates Inc., Oakville, ON, Canada) on the back of a plastic male torso and placing 1.5 mm diameter metal balls in the bolus at various depths. This phantom represented a male upper body in prone position, with hard fat/muscle layer with mechanical targets in the back, spine, and shoulder. The objectives were to (1) demonstrate accurate needle placement at the pre-marked targets and (2) assess the ergonomics of the system. Experienced and novice interventionalists each executed four needle insertions with 18G diamond needles. The accuracy of needle placement was assessed in post-insertion CT, with 1 mm slice thickness. The experienced and novice users alike approached the implanted targets within 2 mm, in every attempt. The device had excellent ergonomics: there was no interfe rence in the workspace and all targets were conveniently accessible. The ergonomics of the system was also tested on a commercial interventional phantom (C IRS , Norfolk, VA) shown in Figure 2, resulting in the same excellent outcome. Also importantly, the reproduction error of the CT gantry mount was consistently below 2 mm (which is less than the width of the l aser), tested in 10 trials.

Cadaver Experiments:

The objective of human cadaver experiments was to demonstrate the ability of precise needle placement to various anatomical targets for a plurality of potential clinical applications. The accuracy of needle placement was assessed in post-insertion CT. The slice thickness was 1.0-3.0 mm, which was clinically adequate for the procedures in our study.

Spinal Nerve Blocks and Facet Joint Injections are demanding procedures primarily because of the sheer volume of cases treated regularly by the neurological pain management service at our institution. The interventional team is under strong pressure to perform these p rocedures in minimum time with clinically sufficient placement accuracy, typically about 2.0 mm. In our experiments, a cadaver was set up in prone position for nerve root and facet joint injections in the lumbar spine area in the setup seen in Figure 1 . We performed several needle insertions with standard 22G beveled needles at the L4 and L5. Contrast and therapeutic substances were not injected. All four spinal nerve block and facet joint needle placements produced clinically sufficient results. A confirmation CT image is shown in Figure 6, where the needle tip touches the correct anatomical target. The needle is completely included in the confirmation image, indicating the physician managed to keep the needle exactly in the gantry 's laser plane. Shoulder and Hip Arthograph ies are diagnostic procedures frequently applied for assessment of joint injury. Arthography typically presents a significant scheduling problem, because first an MRI contrast agent is injected percutaneously into the injured joint under CT or X-ray fluoroscopy guidance and then the patient is brought to an MRI imaging facility for diagnostic scanning. We will explore the clinical possibility of joint arthography with MRI guidance alone. In the anticipation of a forthcoming new MRI-compatible version of the image overlay sy stem, we performed preliminary cadaver studies with CT guidance. In our e xperiments, we fixed a female cadaver in supine position and performed four needle insertions to the shoulder and hip joint, using standard 22G beveled needles. The accuracy of needle placement was assessed in intermittent CT and then contrast substance was also injected in two cases. All four needle placements for joint arthography of the shoulder and hip were clinically successful, two of those shown in Figure 7. Each needle enters the body in the selected entry point, proceeds along the marked trajectory, and touches the selected anatomical target point in the joint space. Contrast material (not shown in the figures) was very hard to inject into the stiffened joint of the cadaver and it did not distribute as evenly as in live patients.

Pilot Needle for Bone Biopsy: Bone biopsies are demanding procedures because the needle must make contact with the bone in some predefined a ngle that is often very difficult to achieve freehand. One must also avoid sensitive structures (like nerves and blood vessels) in the path. As we almost always operate on dam aged bone, faulty placement and misalignment of the large needle or drill may cause structural damage to the Fig. 8: Confirmation CT of pilot needle insertion in bone biopsy already weakened bone; in fact, fracture is not an insignificant intra-operative risk. Many patients have preexist ing micro-fractures, a condition that may develop into a full fracture if the instrument is accidentally wedged in the fracture line. Altogether, unassisted freehand planning of the skin entry, trajectory, bone entry, and cortical target can become exceedingly difficult. In our experiments, we fixed a female cadaver in supine position and performed four needle insertions to the pelvis, using standard 22G beveled needles. A 1.0 mm steel ball was implanted percutan eously into the right lateral wall of the left pelvis, and then this location was targeted from several directions from diffe rent entry points. All four the pilot needle insertions for pelvic bone biopsy were clinically successful. A confirmation CT is shown in Figure 8. Unfortunately, the artifact caused by the needles suppresses the signal of the i mplanted metal target, but the needles converge in a confined area, indicating satisfactory accuracy for bone biopsy. Three of the four needles are completely included in the image slice, while the fourth one is slightly deflected from the image plane.

Discussion

In our previous prototype the i mage overlay device was mounted in the inner laser plane of the scanner, the physician's workspace was often restricted and several targets were not accessible [START_REF] Masamune | An Image Overlay Sy stem with Enhanced Reality for Percutaneous Therapy Performed Inside CT Scanner[END_REF]. Therefore, the unanimous decision of the participating physicians was to use the outer laser plane of the scanner, even though it required translation of the CT table between imaging and needle insertion. Needle insertion was more accurate in phantoms than in human cadavers, for several reasons. First, the phantom tissue was softer and more homogeneous than human cadavers. Also, in phantoms we used 18 G diamond tip needles that barely deflected during insertion, while in the human cadavers we used 22G beveled needles that had a tendency to deflect in the hard and inhomogeneous tissues. Less experienced users had difficulty in holding the needle in the plane of the laser. Although this presently does not seem to be a clinically significant impediment, we consider applying some form of mechanical constraint to aid the physician with hol ding the needle in the laser plane.

Although respiration could not be simulated in the passive phantoms and cadavers, the IZI Biopsy Strip fiducials placed on the patient around the insertion point are expected to provide robust real-time indication of any patient motion, in which case the insertion can be halted till the patient's body is correctly re-registered. Alternatively, the fiducials can be used for re-registration of the patient, the same manner as the calibration fixture is registered.

We have encountered several minor issues that could prove to be significant as our efforts are gearing up toward clinical trials. For example, i t is inconvenient to have the planning laptop in the scanner room and its wire connection may also disrupt normal traffic. (In the clinical device, the laptop will be situated next to the console and apply wireless communication to the mouse used for calibration. Also, slight change s in backlight and glare on the display frame have also caused difficulties.)

In summary, all needle placement attempts, to both phantoms and cadavers, were technically successful and clinically sufficient needle placement accuracy was co nfirmed in post-insertion CT imaging. The workflow process and instrumentation have not been optimized to yield minimum procedure time and the ergonomics of the sy stem still need to improve; these are subjects to current research. Nevertheless, the current embodiment was found to be sufficiently accurate and safe for initial human trials in a plurality of needle placement applications, in which the previously described cadaver studies are predicative of clinical performance. Presently, IRB approval is being sought to commence human trials while software and hardware refinements will continue.

Fig. 1 :

 1 Fig. 1: Spinal needle insertion in human cadaver

Fig. 2 :

 2 Fig. 2: Needle insertion in phantom. The CT image appears to be floating inside the body with correct alignment and magnification.

Fig. 4 :

 4 Fig. 4: Calibration phantom and its CT image

Fig. 3 :

 3 Fig. 3: Needle insertion with single stroke with the assistance of virtual needle guide

Fig. 5 :

 5 Fig. 5: Definition of registration error (a) and the calculation of parallax error (b)

( 1 )

 1 Pick a peg near the area of interest in the vicinity of expected target and entry. Let the computer calculate translation and readjust the overlay image. (2) Pick a peg far out from the previous one. Let the computer calculate rotation and readjust the overlay image. (3) Pick a new peg again relatively close to area of interest to adjust translation. (4) Pick another peg to adjust rotation, far out and in 90° from the previous one.

Fig. 6 :

 6 Fig. 6: CT of confirmation of needle placement for spinal pain management

Fig. 7 :

 7 Fig. 7: Target and confirmation CT for arthography of shoulder (top) and hip joint (bottom)

Acknowledgements

Funding was available from NSF ERC-9731478, Siemens Corporate Research (Princeton, NJ), and Ministry of Education, Science, Sports and Culture, Grant-in -Aid for Young Scientists #14702071. We are grateful to Beatrice Mudge, RTT for her help throughout the experiments and Frank Sauer, PhD (Siemens) for his advice.