Gabor Fichtinger

Anton Deguet

Ken Masamune

Emese Balogh

Gregory Fischer

Herve Mathieu

Russell H Taylor

S James Zinreich

Laura M Fayad

Image Overlay Guidance for Needle Insertion in CT Scanner

We present an image overlay system to aid needle insertion procedures in CT scanners. The device consists of a display and a semitransparent mirror that 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 insertions. The physician inserts the needle following the optimal path identified in the CT image rendered on the display and thus reflected in the mirror. The system promises to reduce X-ray dose, patient discomfort, and procedure time by significantly reducing faulty insertion attempts. It may also increase needle placement accuracy. We report the design and implementation of the image overlay system followed by the results of phantom and cadaver experiments in several clinical applications.

I. INTRODUCTION AND BACKGROUND

N UMEROUS STUDIES have demonstrated the potential efficacy of computed tomography (CT) guided percutaneous needle-based interventions in a wide variety of medical problems. Contemporary practice, however, is limited by the freehand nature of needle placement, which requires mental registration of the patient's anatomy to the CT image in targeting and precise hand-eye coordination in inserting the needle. This frequently results in faulty needle placement attempts, especially in the case of a deep lesion adjacent to vital structures, which in turn increases the discomfort and radiation exposure of the patient, and lengthens the procedure. The recent appearance of real-time CT fluoroscopy has brought significant improvement to needle insertion procedures, but CT fluoroscopy is not without significant risks and shortcomings, it exposes patient and physician to real-time X-ray dose and the physician's hand-eye coordination still remains a dominant factor. Presently no technological solution exists to assist freehand CT-guided needle placement in a simple, accurate, and inexpensive manner, without imparting additional radiation.

Practitioners generally agree that, given enough time and opportunity for intermittent CT imaging and adjustments, the target usually can be reached with appropriate accuracy. The important question is, however, whether the same objective could be achieved with just one attempt, because each correction requires taking an extra CT image (or even series of images) and reinsertion of the needle, which in turn increases the risk of post-procedure complication, discomfort, and radiation exposure to the patient. Therefore, eliminating faulty needle placement attempts is a prime objective of our research.

A variety of tracked navigation systems and surgical robots [START_REF] Cleary | State of the art in surgical robotics: clinical applications and technology challenges[END_REF], [START_REF] Taylor | Medical robotics in computer-integrated surgery[END_REF] have been investigated to assist image guided freehand insertions; all resulting in systems that are prohibitively complex and/or expensive for routine clinical use. Birkfellner et al. integrated computer graphics into the optical path of a head-mounted stereo binocular [START_REF] Birkfellner | A head-mounted operating binocular for augmented reality visualization in medicine -design and initial evaluation[END_REF]. Sauer et al. reported another variant of head-mounted display (HMD) technology [START_REF] Sauer | An augmented reality navigation system with a single-camera tracker: System design and needle biopsy phantom trial[END_REF], in which two head-mounted cameras captured the real scene and a stereo HMD visualized the augmented scene. DiGioia et al. developed a volumetric image overlay system by projecting three-dimensional virtual image on a semitransparent mirror in which the physician simultaneously can observe the actual patient and computer-generated images [START_REF] Blackwell | An image overlay system for medical data visualization[END_REF], [START_REF] Digioia | Computer aided surgery[END_REF]. A similar device using this concept is commercially available under the brand name of Dexteroscope [START_REF] Kockro | Planning and simulation of neurosurgery in a virtual reality environment[END_REF], which also involves elaborate preoperative calibration and requires realtime spatial tracking of all components, including the patient, physician's head, overlay display, mirror, and surgical tools. Grimson et al. graphically overlaid segmented 3D preoperative images onto video images of the patient [START_REF] Grimson | An auto-matic registration method for frameless stereotaxy, image guided surgery, and enhanced reality visualization[END_REF]. This approach presented largely the same calibration and tracking problems as DiGioia's system, and in addition, the projected image also had to be warped to conform to the surface of the patient. Iseki et al. created a volumetric overlay display, and off-line registered to the patient in intracranial neurosurgery cases with the use of fiducials implanted into the skull [START_REF] Iseki | Volumegraph (overlaid three-dimensional image-guided navigation). clinical application of augmented reality in neurosurgery[END_REF], [START_REF] Nakajima | Three-dimensional medical imaging display with computer-generated integral photography[END_REF]. Current volumetric augmented reality devices require painstaking calibration and real-time spatial tracking. Tracked navigation systems have also known to have a plethora of problems and risk factors extensively characterized in the computer-aided surgery literature. Most current systems depend on complex and expensive hardware.

In the pursuit of simpler image overlay systems, our group [START_REF] Masamune | An image overlay system with enhanced reality for percutaneous therapy performed inside ct scanner[END_REF], [START_REF] Masamune | Three-dimensional slice image overlay system with accurate depth perception for surgery[END_REF] and concurrently Stetten et al. [START_REF] Stetten | Overlaying ultrasonographic images on direct vision[END_REF] investigated 2D image reflection produced in a semitransparent mirror. This technique provides an optically stable 2D reflection image without auxiliary tracking, requiring only a simple preoperative alignment. As the majority of needle placement procedures are executed "in-plane" (i.e. when the needle is completely contained in a single CT slice), giving up 3D rendering for engineering simplicity and low cost appears to be a reasonable tradeoff.

This paper describes an embodiment of the 2D image overlay concept optimized for needle placement procedures in conventional CT scanners. In particular, we report new hard- The structure of this paper is the following. After this introduction, Section 2 describes the concept of the system, and Section 3 presents the image overlay display and Section 4 the system integration. Section 5 is devoted to experiments and results, and the last section discusses the results.

II. SYSTEM CONCEPT

The basic concept of the two-dimensional CT image overlay is shown in Figure 1. A flat-panel display and transparent mirror are mounted on the gantry of a CT scanner. We acquire a CT slice, flip it horizontally, adjust its magnification, and then render it on the display. The scanner, display, and mirror are aligned so that the reflection of the CT image appearing in the mirror coincides with the patient's body behind the mirror as shown in Figure 2. The system creates the impression as if the CT image that was floating inside the body in the correct pose and magnification, giving the physician a planar X-ray vision. This technique can also be characterized as an in-situ visualization tool, where the medical image is rendered right in the context of the procedure, spatially registered with the physical body. Perhaps the most promising aspect of image overlay is that the physician can execute the procedure without turning his/her attention away from the patient, while executing the same series of motions and actions as in conventional freehand procedures. In most needle placement procedures, after the entry point is selected, three degrees-of-freedom (DOF) motion of the needle needs to be controlled. In this case, the physician uses the overlay image to control the in-plane insertion angle (1st DOF), while holding the needle in the axial plane marked by the gantry's inner laser light (2nd DOF). (Most modern CT scanners are equipped with two parallel laser planes: the inner plane coincides with the scanner's plane of imaging, while the outer laser plane emanates from a source mounted on the housing of the gantry over the table. The offset between the two laser planes is known from the manufacturer's specification and can also be measured by moving a marker with the encoded table between the two laser planes.) The insertion depth (3rd DOF) is controlled with a ruler and virtual depth gauge drawn on the overlay image. In addition, we may use stripes on the needle to indicate depth and a spring-loaded sterile clamp to prevent overdriving the needle (Figure 2). The use of 2D image overlay does not alter the traditional unassisted procedure to which physicians are accustomed, while increasing the amount of visual information in the field of action. The advantages of 2D image overlay are numerous in comparison to other virtual reality or display augmentation methods reviewed in the previous section. Most significantly, 2D image overlay provides optically stable image without auxiliary tracking instrumentation and it requires only a simple alignment that does not need to be repeated for each patient. The system is simple and inexpensive; the replication of the prototype system shown in (Figure 4) costs only about $3,500. As the majority of needle placement procedures are executed "inplane" (i.e. when the needle is completely contained in a single image slice), giving up full 3D rendering for engineering simplicity and low cost appears to be acceptable. The main added benefit of the image overlay is making pre-insertion CT images available for intra-procedural guidance, without exposing the patient and physician to additional radiation. Although CT does not provide real-time imaging, the image overlay system assists the physician in detecting target motion and allows for gating the needle insertion by the respiratory cycle with the use of skin fiducials, as we explain later.

III. CT IMAGE OVERLAY DEVICE

We have built two basic prototypes of the CT image overlay device for pre-clinical evaluation on phantoms and human cadavers. Both prototypes are mounted on the CT gantry and rotate with the gantry if a tilted CT plane is needed to guide the needle placement. The first prototype, shown in Figure 3, produced the tomographic overlay image in the imaging plane of the scanner, inside the gantry of a singleslice CT scanner (GE Medical Systems, Waukesha, WI). The mounting mechanism was made of 2"x4" pinewood beams, providing great deal of freedom in design. To fit any position and direction of the image slice, we built a 7-DOF passive arm. The adjustable joints enabled us to adjust the angle and distance between the mirror, display, and CT gantry. As the overlay image was created in the actual imaging plane of the scanner, we achieved rapid update of the overlay image.

The second-generation prototype, shown in Figure 4, produces the reflection image in the outer axial laser plane of a Somatom-4 Siemens scanner. This arrangement provides ample room for both patient and physician. The patient must be translated in and out between imaging and intervention, which is the case in most unassisted traditional interventions anyway. No time is lost with this action, because the operator can move the table while the physician is entering the room after acquiring the targeting image. The patient is secured to the table with foam wedges and wide velcro bands, which efficiently prevent involuntary motion of the body. In all modern CT scanners the table translation is digitally encoded, the linear drive mechanism is highly accurate and repeatable. Altogether, target offset due to table translation stays safely within the error margin of these procedures.

The gantry mount was built from extruded aluminum. This structure offers structural integrity, easy machining, light weight, and is aesthetically pleasing. Two average-size technicians are able to mount the basic hardware in a few minutes. The repeatability of the mount, with respect to the gantry's laser planes, is more accurate than the width of the laser (about 1.5 mm), tested in ten experiments. The angle of the display and mirror are fixed with respect to one another and adjustable joints are used to set up the display-mirror unit with respect to the plane of the outer laser on the CT. As the mount is very reliable, the passive arm holding the display/mirror unit has only three adjustable joints, in contrast to the 7-DOF arm in the first prototype. The weight of the display/mirror unit and the mount is 4.0 kg and 20.5 kg, respectively. This is an insignificant extra weight on the gantry and creates virtually no torque on its joints. We also verified that the overlay device did not interfere with the laser lights of the scanner.

IV. SYSTEM INTEGRATION

A. Workflow

We position the subject under the overlay on the table and we acquire a small stack of CT slices with a slice thickness appropriate for the given clinical application. IZI CT Biopsy Strip (IZI Corporation, Baltimore, MD) external fiducials are placed on the skin in the plane of interest. A single CT slice is acquired with the fiducials in place and transferred in DICOM format to the planning and control software implemented on a stand-alone computer (Dell laptop, MS Windows-XP). The laptop concurrently drives the flat panel 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. We kept the insertion planning software simple and intuitive, in order to speed up the process. We refrain from 3D scenes altogether, which is also reasonable for a 2D overlay device. The CT window/level parameters can be interactively adjusted. The entry and target points are picked in the CT image by two mouse-clicks. The computer marks the target and entry points, draws a visual guide along the trajectory of insertion, and marks the depth of insertion. If the overlay system is configured in the outer laser plane of the scanner, then the table is translated out by the known offset between the slice of interest and the overlay plane. The physician holds the needle at the entry point behind the mirror and adjusts the angle to the virtual needle guide while holding the needle in the plane of the laser (Figures 2 and4). This posture allows the physician to insert the needle with a single stroke along the marked trajectory. The IZI skin fiducials are visible on both the patient and in the overlay image. The coincidence between the corresponding marks indicates correct alignment. This feature is particularly important for quality assurance, especially in applications when the target anatomy is prone to motion due to respiration or mechanical force. The skin fiducials can be used to gate or synchronize the needle insertion to the respiratory cycle. After the needle is inserted, a confirmation image is acquired.

B. Calibration

After mounting the system, the display-mirror unit must be aligned with the scanner's plane of imaging. As we mentioned earlier, the physicians' choice was to set up the system in the outer laser plane of the scanner. (Note that the outer laser plane is parallel to the plane of imaging, the offset between the two is a priori known, and the encoded table provides precise translation between the two planes.) Calibration is accomplished in two steps: (1) make the overlay image coincide with the plane of the scanner's outer laser plane, and (2) determine the inplane transformation between the overlaid CT image and the view of the physical object in the mirror.

We fabricated a calibration phantom containing a base board and a perpendicular fiducial board, the latter with with an asymmetric set of 5 mm diameter and 10 mm long aluminum pegs, shown in Figure 5. The boards are made of 10 mm thick clear acrylic and they are practically radiolucent. We manually adjust the calibration phantom on the CT table until the scanner's axial laser plane sweeps the front face of the fiducial board. We render an arbitrary test image on the overlay. We adjust the joints on the mirror-display unit to make the overlay image appear on the front face of the fiducial board. This adjustment usually does not need to be performed every time the overlay device is set up, because the gantry mount is highly accurate and reproducible. (In fact, we took the mount off and then put it back ten times, and the mirrordisplay unit was correctly positioned every time and did not need any adjustment.)

The first step of the in-plane registration process is image scaling. The overlay image must appear in correct size in the mirror, but there is variable linear scaling between the CT image and displayed image. Let

u c v c and u d v d be a
vector in the CT image and display image, respectively, in pixel unit. Also, let (p cx , p cy ) and (p dx , p dy ) be the pixel size in the CT image and display image, respectively, in mm/pixel unit, in x and y directions. The pixel size of the display is constant and it is either known from the manufacturer's specification or its measurement is trivial. The pixel size of the CT image is calculated as the ratio between the field of view (in mm) and image size (in pixel), both are known from the scanning protocol that is encoded in the header of the DICOM image. Then the scale factors in x and y directions are calculated as s x =p cx /p dx and s y =p cy /p dy , respectively. The in-plane scaling between the CT and display image vectors is described by the following equation:

u d v d = s x 0 0 s y * u c v c (1)
If the pixel size is identical in x and y directions in both the CT and display, then the scale factors are equal (s x =s and s y =s) and the equation above reduces to:

u d v d = u c v c * s (2)
Having dealt with scaling, the second step of in-plane registration is to determine a 3-DOF rigid body transformation. We acquire a CT image of the fiducial board and render it on the overlay display, as seen in Figure 5. We adjust the in-plane rotation and translation of the phantom's CT image until each aluminum peg coincides with its mark in the CT image. We auto-segment the marks of the aluminum pegs in the phantom's CT image. Then a technician leans over the mirror and with the mouse clicks on the points where the actual pegs appear through the mirror. From the two planar sets of corresponding points, we calculate the in-plane translation and rotation. Finally, we apply the resulting 3-DOF transformation on the CT image, and then redisplay the image on the overlay. There are two possible approaches to this point-based rigid body registration: (1) Optimize the registration for minimum error in one step after collecting all corresponding pairs of points. (2) Progress gradually in an iterative cycle, where in each iteration pick only one corresponding pair and recover the translation or rotation alternately until correct registration is achieved. From our perspective, the one-step method is less practical, because using all points is usually superfluous, but using less than all of them is a gamble: if the registration needs only a tiny bit of adjustment at the end, then we still must repeat the entire registration process from the beginning. We must add, however, that the iterative registration relies on accurate point pairs, and the translation estimation in particular may be sensitive to noise (i.e. human error) and is less robust than least-squares minimization over all pairs. A severe outlier may throw off the registration, which the operator must detected visually and compensate by either undoing the outlier or adding more registration points. All facts considered, we chose the iterative rigid body registration approach, for its inherent practicality and convenience. The mathematical formulation is described next. In the equations below We iterate in the following cycle until the exit criteria are met:

u i v i is a point in the CT image, u i v i is its corresponding point in
• Choose a point in the CT image, and then choose the corresponding point as seen through the mirror. (To start, pick a point near the center of the image.) • Calculate the required translation p to align the selected point, as shown in Figure 6 (a). • Translate all CT image points by the following equation:

u i v i = p x p y + u i v i ( 3
)
• Display the adjusted image.

• Choose another point in the CT image, and then choose the corresponding point as seen through the mirror.

• Calculate the angle θ representing the angular misalignment in the axis normal to the imaging plane. The center of rotation is the point selected previously for translation, as explained in Figure 6 (b). • Rotate all CT points by the calculated amount about the chosen center of rotation, by the following equation:

u i v i = cosθ sinθ -sinθ cosθ * u i -u v i -v + u v ( 4
)
• Display the adjusted image. (Note that the pixels in the adjusted image are interpolated, as it is always the case in rotated images.) • Make a quick visual assessment of the registration. Continue the cycle if necessary, otherwise exit. (Note that one could also apply quantitative exit criteria on the amount translation and rotation, but we found the quick visual check to be sufficient for our clinical applications.)

We also analyzed the combined effects of human and optical errors 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 transformation on each pair and adding noise to each data point, as explained in Figure 7(a). 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 added some "noise" to the position of R, obtaining point P . We registered P to Q getting a rigid-body transformation T reg . Using this transformation, we transformed R obtaining S. Therefore, the system error was the distance between points S and Q. Human error was simulated by adding a random value (2 pixels) to the position of the point to be registered. Parallax error from the mirror may induce a significantly large error. At d=4 mm thickness and α = 30 o view angle and using the formulas derived in Figure 7(b), the parallax error was about x=1.28 mm, the effect of which fortunately can be substantially reduced by altering the view points during the calibration process. We also concluded that iterative re-registration was more favorable than 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. We found the following to be the best strategy: view (α = 0 o ). This performance appears to be adequate for most CT-guided needle placement procedures.

V. EXPERIMENTS AND RESULTS

A. Head Phantom

In this experiment we used the prototype presented in Figure 3. The overlay device was set up in the plane of imaging, so the subject was not moved between imaging and needle placement. We implanted a honeydew melon with multiple 1.5 mm diameter metal pellets serving as targets. The melon simulated the locations of head, neck, and intracranial targets, as seen in Figure 2. We used standard brain imaging protocol with 1 mm slice thickness, and standard 20 G diamond-head stainless steel needles. The needles came with a sterilized spring loaded clamp that was adjusted to the depth of insertion. An experienced interventionalist executed three interventions. We assessed the accuracy in post-insertion CT, with 1 mm slice thickness. The needle tip approached the implanted metal ball target within 2 mm distance in every attempt. Although the metal ball was not distinguishable from the needle in the confirmation CT slice, the lateral scout view clearly showed the target and needle tip. The needle was fully visible in CT slice, indicating that the physician succeeded in holding the needle exactly in the laser plane.

B. Body Phantoms

The overlay device, mounted in the inner laser plane of the scanner, demonstrated several ergonomic shortcomings: (1) the physician's workspace was often restricted, (2) in some situations the target was inaccessible, (3) the subject could not be translated in and out the scanner without moving the mirror out of the way, (4) the gantry could not be tilted beyond a few degrees without collision between the subject and mirror, (5) in some cases there was not enough room for the needle between the subject and mirror. Due to the limitations identified during the head phantom experiments, the unanimous decision of the participating clinicians was to configure the device in the outer laser plane of the scanner. In all subsequent experiments, this system configuration was used. Although the subject needs to be moved between imaging and needle insertion, that was not considered as a significant risk in addition to the standard procedure. There is some time delay after taking the targeting image, because the interventionalist must return to the room. Furthermore, the IZI Biopsy Strip fiducials provide sensitive external indication of body motion, thereby mitigating the risk of target dislocation substantially.

We constructed a male body phantom 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 demonstrate accurate needle placement at the pre-marked targets and assess the ergonomics of the system. An experienced interventionalist executed four needle insertions with 18 G diamond needles. We assessed the accuracy of needle placement in post-insertion CT, with 1 mm slice thickness. The needle approached the implanted target within 2 mm in every attempt. There was no interference in the workspace and all targets were conveniently accessible. The ergonomics of the system was also tested on a commercial interventional phantom (CIRS, Norfolk, VA), resulting in the same outcome. Also importantly, the reproduction error of the CT gantry mount relative to the CT laser was consistently below 2 mm (which is less than the width of the laser), tested in 10 trials.

C. Cadaver Experiments

The objective of human cadaver experiments was to demonstrate the ability of clinically successful needle placement to various anatomical targets in several 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.

1) 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 Fig. 8. CT of confirmation of needle placement for spinal pain management service at our institution. The interventional team is under strong pressure to perform these procedures; namely bilateral injections under 10 minutes and with clinically sufficient placement accuracy of 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. We performed several needle insertions with 22 G beveled needles at the L4 and L5. Contrast and therapeutic substances were not injected. All four spinal nerve block and facet joint needle placements were clinically successful. A confirmation CT image is shown in Figure 8, where the needle tip touches the correct anatomical target. Here needle is completely included in the confirmation image, indicating the physician managed to keep the needle exactly in the gantry's laser plane.

2) Shoulder and Hip Arthrographies: are diagnostic procedures frequently applied for assessment of joint injury. An Magnetic Resonance Imaging (MRI) contrast agent is injected percutaneously into the injured joint under CT or Xray fluoroscopy guidance and then the patient is brought to an MRI imaging facility for diagnostic scanning.

In our experiments, we fixed a female cadaver in supine position and performed four needle insertions to the shoulder and hip joint, using 22 G beveled needles. The accuracy of needle placement was assessed in CT and then contrast substance was also injected in two cases. All four needle placements for joint arthrography of the shoulder and hip were clinically successful as the injection needle safely entered the joint space, two of those cases are shown in Figure 9. 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 it does in live patients.

3) Pilot Needle Insertion for Musculoskeletal Biopsy:

Typically, performance of a CT guided percutaneous musculoskeletal (MSK) biopsy requires careful attention to target and path planning, followed by insertion of a 22 G pilot needle to the bone surface through the pre-selected entry point and path. After correct placement of the pilot needle is ascertained with a confirmatory CT image, a large (12-16 G) or smaller (14-18 G) core needle can be passed down along the pilot needle to collect the sample from a skeletal or soft tissue lesion respectively. Bone biopsies are especially demanding procedures because the needle must make contact with the bone in some predefined angle 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 damaged bone, faulty placement and misalignment of the large needle or drill may cause structural damage to the already weakened bone; in fact, fracture is not an insignificant intra-operative risk. Many patients have preexisting 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 22 G beveled needles. A 1.0 mm steel ball was implanted percutaneously into the right lateral wall of the left pelvis, and then this location was targeted from several directions from different entry points. All four pilot needle insertions for pelvic bone biopsy were clinically successful, the confirmation CT is shown in Figure 10. Unfortunately, the artifact caused by the needles suppresses the signal of the implanted metal target, but the needles converge in a confined area, indicating appropriate 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.

VI. DISCUSSION

We have reviewed alternative augmented realty solutions earlier in Section 1. Here we provide a critical analysis of our results with the CT image overlay device. Overall, phantom and cadaver experiments were successful toward proving the hypothesis: the CT image overlay device allowed for clinically adequate and safe needle placement without the need for reinsertion and re-imaging. As our efforts now are gearing up for clinical trials, several ergonomic and technical issues need to be dealt with.

In our first prototype (see Figure 3) the image 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. Therefore, the decision of the participating physicians was to use the outer laser plane of the scanner (see Figure 4), even though it required translation of the CT table between imaging and needle insertion. (This does not cause time delay, because the physician needs time to enter the scanner room anyway.)

Initially, optical parallax used to cause problems during needle insertion. Our current workflow, however, eliminates that effect: We identify the needle insertion point on the patient's skin with the use of the IZI biosy strip markers, rather than picking the point in the overlay image. Once the needle tip is committed, we keep the needle parallel to the virtual needle guide drawn on the overlay image. Parallax can make the needle appear shifted with respect to the virtual guide. We know, however, that this is just an optical illusion, because the needle is firmly lodged in its entry point. We simply disregard the parallax shift and concentrate on keeping the needle parallel to the virtual guide.

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 22 G beveled needles that had a stronger tendency to deflect in the hard and inhomogeneous tissues. There are several methods to mitigate deflection during free-hand needle insertion, such as spinning or various combinations of jackhammering, spinning, and insertion. It must also be noted that thin needles are mostly used in relatively superficial targets, so the off-axis dislocation of the needle tip usually remains under the clinical margin of error. One must keep in mind that needle bending is not always unwanted. For example, beveled needles are often purposely deflected off some bony structures to access narrow passages, as often is the case in facet joint and epidural space injections. Furthermore, needle bending does not necessarily cause the needle tip to land outside the clinical margin of error, however, pinpoint accuracy is always more desirable. Finally, we reiterate that the main goal of our project is not pinpoint accuracy, but the prevention of clinically faulty needle insertions.

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. The IZI fiducials can be used for reregistration of the patient in the same manner as the calibration fixture is registered. Importantly, this can be accomplished without re-imaging the patient.

Despite continuous improvement, calibration of the system still is a significant issue. Optical parallax and human perception errors need to be eliminated from the process. Note that the prototype in Figure 4 uses the outer laser plane on the CT gantry. Aligning the display/mirror unit with this laser plane is a difficult and also somewhat unsafe practice, because the laser source is mounted on the cover of the gantry rather than on its steel frame and thus the accuracy of the beam cannot be guaranteed. A more appealing solution is to construct a rigid display/mirror unit that carries its own laser reference plane, similarly to Stetten [START_REF] Stetten | Overlaying ultrasonographic images on direct vision[END_REF] and calibrate the system to the scanner as described in [START_REF] Lee | Novel algorithms for robust registration of fiducials in CT and MRI[END_REF]. This device will be aligned to the CT scan plane with two rotational joints, while the remaining four degrees of freedom will be compensated by software. The calibration of this system will be fully automated and free of human perception errors. These modifications are currently underway in our laboratory.

We have also encountered several other minor problems. The physician sometimes had difficulty in holding the needle in the axial laser plane. Although this presently does not seem to be a clinically significant impediment, we consider applying some form of soft mechanical constraint to aid the physician with holding the needle in plane. We have found it somewhat inconvenient to have the planning laptop in the scanner room, especially because its wire connection occasionally disrupted normal traffic. In the forthcoming clinical version, we will place the laptop next to the console and apply wireless communication to the device in the scanner room. Changes in room light conditions have also caused difficulties. Although we draped the distal opening of the gantry, foreground light still often interfered with the overlay image. We consider mounting a controlled light source on the frame and reduce occasional glare from the display frame by applying dark satin coating.

In summary, needle placement experiments with both phantoms and cadavers were clinically successful and confirmed in post-insertion CT imaging. The workflow process and instrumentation have not been optimized to yield minimum procedure time and the ergonomics of the system still need to improve; these are subjects to current research. Nevertheless, the current embodiment was found to be adequate and safe for initial human trials in several of needle placement applications, in which the previously described cadaver studies are predictive of good clinical performance. Presently, Institutional Review Board (IRB) approval is being sought to commence human trials in MSK biopsy and arthrography while software and hardware refinements will continue.

Fig. 1 .

 1 Fig. 1. System Concept

Fig. 2 .

 2 Fig. 2. Needle insertion in a head-phantom. The CT image of the water melon is floating inside the phantom.

Fig. 3 .

 3 Fig.3. First prototype of the image overlay system, the reflection image is in the inner axial laser plane of the scanner. A magnification of the system is shown in Figure2.

Fig. 4 .

 4 Fig. 4. Current prototype of the image overlay system, the reflection image is in the outer axial laser plane of the scanner. (The laser source is in coverage behind the mount.) Spinal needle insertion in human cadaver

Fig. 5 .

 5 Fig. 5. Calibration phantom and its CT image at the lower left corner.

Fig. 6 .

 6 Fig. 6. In-plane rigid translation (a) and rotation (b). The aluminum pegs segmented in CT are represented by solid black dots, while the actual pegs seen in the mirror are represented by hollow circles.

( 1 )Fig. 7 .

 17 Fig. 7. Definition of registration error (a) and the calculation of parallax error (b).

Fig. 9 .

 9 Fig. 9. Target and confirmation CT for arthrography of shoulder (top) and hip joint (bottom)

Fig. 10 .

 10 Fig. 10. Confirmation CT of pilot needle insertion in bone biopsy.

Gabor

  Fichtinger (M04) received the BS and MS degrees in Electrical Engineering, and the PhD degree Computer Science from the Technical University of Budapest, Hungary, in 1986, 1988, and 1990, respectively. He completed a post-doctoral training in high performance computing at the University of Texas at Austin, with a specialization in biomedical visualization and computing. From 1993 to 1999, he lead the development of radiosurgery, radiotherapy, and neurosurgery treatment planning systems at the George Washington University and Precision Mathematics, Inc. Currently, Dr. Fichtinger is an Associate Research Professor of Computer Science, Mechanical Engineering and Radiology at the Johns Hopkins University. His research focuses on image-guided surgical interventions, surgical planning, medical robotics, surgical navigation, therapy monitoring, and systems integration. Anton Deguet received the BS in Mathematics in 1991 from the University of Tours and the MS in computer science in 1994 from the University of Grenoble, France. Since 2000, he has been a research systems engineer at the Center for Computer Integrated Surgery at the Johns Hopkins University. Emese Balogh received the BS/MS combined degree in computer science in 1995 from the Babes-Bolyai University in Cluj, Romania and completed doctoral requirements in computer science in the University of Szeged, Hungary. Since 2003, she has been at the Johns Hopkins University as a predoctoral research fellow. Emese Balogh's research interest is in the area of medical image processing, computer graphics, discrete tomography, and image guided needle insertions.

Johns Hopkins University, Baltimore, MD, USA

Tokyo Denki University, Japan

ACKNOWLEDGMENT

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


Fabio Cuzzolin
email: cuzzolin@cs.ucla.edu

On the properties of relative plausibilities

Keywords: Belief functions, belief space, relative plausibilities, probabilistic approximation, Dempster's rule

In this paper we investigate the properties of the relative plausibility function, the probability built by normalizing the plausibilities of singletons associated with a belief function. On one side, we stress how this probability is a perfect representative of the original belief function when combined with any arbitrary probability through Dempster's rule. This leads to conjecture that this function should also be the solution of the probabilistic approximation problem, formulated naturally in terms of Dempster's rule. On the other side, the geometric properties of relative plausibilities are studied in the context of the geometric approach to the theory of evidence, yielding a description of the representation property which suggests a sketch for the general proof of our conjecture.

Introduction

The problem of finding the correct probabilistic approximation of belief functions has been widely studied in the last years. A number of papers have been published on this issue [START_REF] Haenni | Resource bounded and anytime approximation of belief function computations[END_REF][START_REF] Denoeux | Approximating the combination of belief functions using the fast Moebius transform in a coarsened frame[END_REF][START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF] (see [START_REF] Bauer | Approximation algorithms and decision making in the Dempster-Shafer theory of evidence-an empirical study[END_REF] for a review), mainly in order to find efficient implementations of the rule of combination aiming to reduce the number of focal elements in coarsened frames [START_REF] Denoeux | Approximating the combination of belief functions using the fast Moebius transform in a coarsened frame[END_REF] or using hierarchical clustering [START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF]. Tessem [START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF], for instance, incorporated only the highest-valued focal elements in his m klx approximation; a similar approach inspired the summarization technique formulated by Lowrance et al. [START_REF] Lowrance | A framework for evidential-reasoning systems[END_REF]. The connection between belief functions and probabilities is as well the basement of a popular approach to the theory of evidence, Smets' pignistic model [START_REF] Ph | Belief functions versus probability functions[END_REF]. On his side, F. Voorbraak [START_REF] Voorbraak | A computationally efficient approximation of Dempster-Shafer theory[END_REF] proposed as solution the relative plausibility function * ~s P , i.e. the unique probability that, given a belief function s with plausibility P * s , assigns to each singleton its normalized plausibility. Afterwards, Cobb and Shenoy [START_REF] Cobb | A comparison of methods for transforming belief function models to probability models[END_REF] described some properties of the relative plausibility of singletons and discussed its nature of probability function that is equivalent to the original belief function.

In this paper we will actually study some properties of this Bayesian function. Considering the central role of Dempster's rule of combination in the theory of evidence, we will formulate an approximation criterion based on similarity between combinations. We will show how the relative plausibility function solves a "reduced" version of the problem, as a consequence of * ~s P being a "perfect" representative of s in the probabilistic region P, meaning that s ⊕ t = * ~s P ⊕ t for each probability t where ⊕ denotes their Dempster's sum.

In the search for a general solution of this Dempster-based approximation problem, we will study the geometry of the relative plausibility function in the context of the geometric interpretation of the theory of evidence. The geometric behavior of the representation property, in particular, will suggest us a possible sketch for the general proof. The geometric analysis of belief and plausibility functions is due to the author. Black has also dedicated its doctoral thesis to the study of belief functions [START_REF] Black | An examination of belief functions and other monotone capacities[END_REF]. Another close reference could be a recent paper of Ha and Haddawy [START_REF] Ha | Theoretical foundations for abstraction-based probabilistic planning[END_REF] in which they exploit methods of convex geometry to represent probability intervals.

The theory of evidence

Belief and plausibility functions

In the theory of evidence [START_REF] Dempster | Upper and lower probabilities generated by a random closed interval[END_REF] [9] a basic probability assignment (b.p.a.) over a finite set

Θ (called frame of discernment) is a function m:2 Θ → [0,1] such that Θ ⊆ ∀ ≥ = = ∅ ∑ Θ ⊆ A A m A m m A 0 ) ( , 1 ) ( , 0 ) ( (1)
Subsets of Θ associated with non-zero values of m are called focal elements and their union core. The belief function s : 2 Θ → [0,1] associated with the basic probability assignment m is defined as:

∑ ⊆ = A B B m A s ) ( ) ( . (2)
Conversely, the basic probability assignment m of a belief function s can be uniquely recovered by means of the Moebius inversion formula [START_REF] Shafer | A mathematical theory of evidence[END_REF] so that there is a 1-1 correspondence between the two set functions m ↔ s. In particular, a probability function is a peculiar belief function which satisfies the additivity rule for disjoint sets (Bayesian b.f.).

Belief functions representing distinct bodies of evidence can be combined by means of Dempster's rule [START_REF] Dempster | Upper and lower probabilities generated by a random closed interval[END_REF].

) ( ) ( ) ( ) ( ) ( 2 1 2 1 ∑ ∑ ∅ ≠ ∩ = ∩ ⋅ ⋅ = B A C B A B m A m B m A m C m (3)
When all the intersections between focal elements of the two functions are empty, the denominator of Equation ( 3) goes to zero and we say that s 1 and s 2 are non-combinable. The definition easily extends to the combination of several belief functions. A dual representation of the evidence encoded by a belief function s is called plausibility function. Its value expresses the amount of evidence not against a proposition

∑ ∅ ≠ ∩ = - = A B c s B m A s A P ) ( ) ( 1 ) ( * (4)
where A c is the complement of the set A in Θ.

Belief and plausibility space

Motivated by the approximation problem, we recently introduced the language of convex geometry in the theory of evidence to study the geometry of belief functions [START_REF] Cuzzolin | Geometry of Dempster's rule of combination[END_REF][START_REF] Cuzzolin | Geometry of upper probabilities[END_REF][START_REF] Cuzzolin | Geometric analysis of belief space and conditional subspaces[END_REF]. Consider a frame of discernment Θ and introduce in the Euclidean space

ℜ N , N = |2 Θ | -1, an orthonormal reference frame {x A }, A ⊂ Θ, A ≠ ∅, in which each coordinate function x A measures the belief value s(A) of A.
Definition 1. The belief space associated with Θ is the set of points S Θ of ℜ N corresponding to a belief function.

We assume the domain Θ fixed, and use the notation S to refer to the belief space. To determine which points of ℜ N "are" belief functions we can exploit the Moebius inversion lemma, by computing the corresponding b.p.a. and checking the axioms m must obey. It is not difficult to prove [START_REF] Cuzzolin | Geometry of Dempster's rule of combination[END_REF][START_REF] Cuzzolin | Geometric analysis of belief space and conditional subspaces[END_REF]

that S is convex. More precisely, if call A B B m A m S s P A ≠ ∀ = = ∈ = 0 ) ( , 1
) ( : [START_REF] Dempster | Upper and lower probabilities generated by a random closed interval[END_REF] the unique belief function assigning all the mass to a single subset A of Θ, it can be proved that the belief space S coincides with the convex closure Cl of all the basis belief functions P A , (see Figure 1) Furthermore, any belief function s ∈ S can be written as a convex sum as follows:

∑ Θ ⊂ = A A P A m s ) ( . ( 8
)
Since a probability is a belief function assigning non zero masses to singletons only, the set P of all the Bayesian belief functions is a subset of the boundary of S, precisely the simplex determined by all the basis functions associated with singletons:

). , (

Θ ∈ = x P Cl P x (9)
Analogously, we can call plausibility space the region Π of ℜ N whose points correspond to admissible plausibility functions. It can be proved [START_REF] Cuzzolin | Geometry of upper probabilities[END_REF] that Π is also a simplex, [START_REF] Ph | Belief functions versus probability functions[END_REF] whose vertices Π A are exactly the plausibility functions associated with the basis belief functions P A.

) , ( Θ ⊂ Π = Π A Cl A

Dempster-based approximation

The rule of combination is central in the theory of evidence: belief functions are meaningful when combined with other b.f. in an inference process. We believe this should be taken into account when approaching the approximation problem. This led us to formulate a constraint on the ``external" behavior of the desired approximation. A good approximation, when combined with any other belief function, must produce results similar to what obtained by combining the original function. Analytically, this can expressed as

∫ ∈ ∈ ⊕ ⊕ = S t C s dt t s t s dist s ) ' , ( min arg ˆ' (11)
where t ∈ S is an arbitrary belief function on the same frame, "dist" is a distance function in the Euclidean space (being the belief space a subset of ℜ N ), and C is the class of belief functions the approximation belongs to. Here we consider the class P of the Bayesian belief functions, and show how the relative plausibility function possess a peculiar property which candidates it to be the solution of the probabilistic approximation problem as posed in [START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF].

Representation

Let us compute the general form of the difference s ⊕ t -p ⊕ t, where both p and t are Bayesian belief functions. To this extent we exploit the general commutativity property we have recently proved in [START_REF] Cuzzolin | Geometry of Dempster's rule of combination[END_REF]. We just saw that any belief function s can expressed as a convex sum of simple b.f. (Equation ( 8)). As Dempster's rule is commutative with respect to convex combinations (see [START_REF] Cuzzolin | Geometry of Dempster's rule of combination[END_REF]

P A m t s ⊕ ⋅ = ⊕ ∑ ∑ Θ ⊂ Θ ⊂ ) ( ) ( ) ( ) ( * * (12)
Immediately then, if t in particular is a Bayesian b.f.

x x y s s P y P y t x P x t t s ⋅ = ⊕ ∑ ∑ Θ ∈ Θ ∈ ) ( ) ( ) ( ) ( * * (13) x x y P y p y t x p x t t p ⋅ = ⊕ ∑ ∑ Θ ∈ Θ ∈ ) ( ) ( ) ( ) ( (14)
where P x is the basis belief function for the event {x}, since P p * (x) = p(x) as p is a probability. The difference s ⊕ t -p ⊕ t can hence be expressed as i.e. * ~s P is the intersection of the line joining the vacuous belief function P Θ and the plausibility of singletons * s P with the probabilistic subspace (see Figure 2 again). The geometry of * ~s P is then naturally related to the geometry of * s P . This function has a quite interesting interpretation in terms of distances in the belief space. Theorem 3. The L ∞ distance between any arbitrary b.f. s on a frame Θ and the corresponding plausibility of singletons measures exactly the difference between the cumulative plausibility of the elements of Θ and its own plausibility value,

[ ] ∑ ∑ Θ ∈ Θ ∈ ∆ - ∆ ⋅ ∆ ∆ = =         ∆ - ∆ ⋅ x
∑ Θ ∈ = = y s s s y P x P x P x p ) ( / ) ( ) ( ) ( * * * ∑ ∑ ∑ ∑ ∑ Θ ∈ Θ ∈ ∆ = = = = ∆
x P x t ) ( ) ( ) ( ) ( 1 ) ( ) ( ) ( *

Reduced approximation criterion

Geometry of relative plausibilities 4.1 Plausibility of singletons

∑ Θ ∈ Θ ⊂ ∞ - = - = - x s s A s x P A s A P s P 1 ) ( ) ( ) ( max * * * (24) Proof. Namely, if |A| = n -k, with A = Θ -{x 1 ,…, x k }, then ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∑ = ⊃ ∅ ≠ ∩ ∅ ≠ ∩ Θ ⊂ = ⊃ Θ ⊂ - Θ ⊂ = Θ ⊂ ⊃ = - Θ ⊂ - Θ ⊂ = = - + - = = + - + - = - + - -         - = = - - - = = - Θ - - - - Θ = - Θ - - = - k i x X x x X x x X X k i x X X x x X k i X x X k i x X x x X k i k i k i k i s s i k k i k i i k X m X m c X m X m X m X m c X m c k X m X m X m c k X m x x s c k x s x x s x P c A s A P 1 } ,..., { } ,..., { 1 } ,..., { 1 1 } { } ,..., { 1 1 1 1 * * ) ( ) ( ) 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( }) ,..., { ( ) ( }) { ( }) ,..., { ( ) ( ) ( ) (

∑ ∑ ∑

= ⊃ ∅ ≠ ∩ - = Σ k i x X x x X k i k X m X m 1 } ,..., { ) ( ) ( 1 (26) we can then write . ) 1 ( ) ( ) ( * k s c A s A P Σ + - = - (27) Now, ) ( ) ( * A s A P s ≥ for all A, since [ ] ⋅ + - + ∩ - ⋅ ⋅ = ∩ - ⋅ ⋅ + - = Σ + - ∑ ∑ ∑ ∑ ∅ = ∩ ∅ ≠ ∩ Θ ⊂ ∅ ≠ ∩ } ,..., { 1 } ,..., { 1 } ,..., { 1 1 1 ) ( 1 } ,..., { 1 ) ( ] } ,..., { 1 [ ) ( ) 1 | )(| ( ) 1 ( k k k x x X k x x X k X x x X k X m X x x X X m x x X X m X X m c (28) [ ] 0 ] 1 )[ ( } ,..., { ) ( ] 1 [ . } ,..., { } ,..., { 1 1 1 ≥ - + + ∩ - = - ⋅ ∑ ∑ ∅ = ∩ ∅ ≠ ∩ k k x x X x x X k X X m x x X X X m X (28) Also, for any chain of subsets {x 1 }⊂ … ⊂ {x 1 ,…, x k } ⊂ … ⊂ Θ the sequence {Σ k } is decreasing, as ∑ ∑ ∑ ∑ ∑ ∑ ⊃ ∈ ∃ ⊃ ⊄ ⊃ ∅ ≠ ∩ ⊃ ∈ ∅ ≠ ∩ + + + + + + ≤ - = + + - = - + + - = Σ - Σ i k k k k k k k x X k i x X X x x x X x x X x X X x x x X k k X m X m X m X m X m X m : ] ,.., 1 [ , } ,..., { , } ,..., { } ,..., { 1 1 1 1 1 1 1 1 1 . 0 ) ( ) ( ) ( ) ( ) ( ) ( (29)
In the binary case * * s s P P = and the relative plausibility function lays on the line ) , ( * s P P Θ as in Figure 2.

5 Towards a general solution

Probabilistic approximation in S 2

Let us see how the general criterion [START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF] works for the binary frame. The representation property allows us to rewrite the integral [START_REF] Tessem | Approximations for efficient computation in the theory of evidence[END_REF]

λ β β (35) since s ⊕ s' = s ⊕ [λt + (1-λ)c] = β s ⊕ t + (1-β) s ⊕ c
where β = λ∆ st /(λ∆ st + (1-λ)∆ sc ) for (30) again. After observing that s ⊕ (1,1) = (1,1) (a trivial consequence of its definition), and remembering that Dempster's rule maps a line passing through a pair of points into another line through the images of these points [START_REF] Cuzzolin | Geometry of Dempster's rule of combination[END_REF] we get that the images s ⊕ c and s ⊕ t also lay on a line passing through ( are parallel to the line (s ⊕ c, s ⊕ t). This property is characteristic of the relative plausibility function, since for any other probability p, p ⊕ t does not lay in the intersection of this line with P. We can reasonably consider this elegant symmetry as an evidence of the correctness of our conjecture.

Conclusions

The picture depicted here is far from being complete, as the general case will not be a copycat of the bidimensional one. However, in this paper we have shown how the geometric approach can provide useful insights about the solution of the approximation problem. The commutativity results [START_REF] Cuzzolin | Geometry of Dempster's rule of combination[END_REF], in particular, are powerful tools which allow us to describe Dempster's combination in a straightforward manner, eventually leading us to the solution of complex optimization problems and bringing more light on the properties of relative plausibilities. ) to lines still passing through the same point. In other words, s ⊕ t is the relative plausibility of s ⊕ s' whatever s' ∈ (c,t). When p = P * s then p ⊕ t = s ⊕ t and all the vectors s ⊕ s' -p ⊕ t are parallel.

  From P * s we can derive a Bayesian belief function called relative plausibility of singletons by simply normalizing the plausibility values of all the elements of Θ:

Figure 1 .

 1 Figure 1. The belief space is a simplex whose vertices are the basis belief functions P A .

Figure 2 .

 2 Figure 2. The bi-dimensional case Θ={x,y}. In this case * * s s P P = .

Figure 2

 2 Figure 2 illustrates the geometry of the belief space for a simple binary frame Θ = {x,y}. As s(Θ) = 1 for all s we can neglect the coordinate Θ, and represent a belief function s as a point of the plane, with coordinates )). ( ) ( ), ( ) ( ( y m y s x m x s s = = =

  c = ∑ x P s * (x) is the total plausibility of singletons. If we define

Figure 3 .

 3 Figure 3. Probabilistic approximation in S 2 . Dempster's rule maps lines passing through (1,1) to lines still passing through the same point. In other words, s ⊕ t is the relative plausibility of s ⊕ s' whatever s' ∈ (c,t). When p = P * s then p ⊕ t = s ⊕ t and all the vectors s ⊕ s' -p ⊕ t are parallel.

5.1 The geometry of representation

																		µ	=	λ	∆	sp	+	sp -∆ 1 ( λ λ	∆	p ) P s *	(33)
																		where the denominators of p ⊕ s and p ⊕ * ~s P are
																		∆	sp	=	x ∑ ∑ x A ⊃ x p ) (	m	(	A )	=	∑ x	p	(	x	)	s P	(	x	)
																		∆	∑ x ~* * ∑ ∆ = = s sp s p P x P x P x p s ) ( ) ( ) ( * *	(34)
																		x
																		so that, since s ⊕ p = * ~s P ⊕ p for Theorem 1, p ⊕ t = p ⊕ [λs
																		+ (1-λ) * ~s P ] = µ s ⊕ p + (1-µ) s ⊕ p = s ⊕ p. In other
																		words, the representatives of s in P are located on the line passing through s and * ~s P .
	Figure 2 makes clear that	(	P Θ	,	* s P	)	corresponds to a dual
	line	(	Π	Θ	,	s	)	, joining the belief function s with the vacuous
	plausibility Θ Π . The results of Section 4 can now be given
	a geometric interpretation in terms of this line, possibly
	enlightening our search for a solution of the general
	approximation problem (11).
	Theorem 4. All the points t of the line	(	s	, P s *	)	are perfect
	representatives of s when combined with arbitrary Bayesian
	functions, t ⊕ p = s ⊕ p ∀p∈P.
	Proof. We can again exploit the results on Dempster's rule
	of affine combinations. If ∑ i α i = 1, [3]
											s	⊕	∑	α	i	i s	=	∑	β	i	s	⊕	i s	(30)
																i		i
	where	β	i	=	α	i	∆	i	/	∑ ∆ j α	j	and i ∆ is the denominator of
	the b.p.a. of s ⊕ s i as in Section 3.1. Now, each point t on the line ) , ( * s P s can be written as
														t	=		λ	s	+	1 (	-	λ	* s P )	(31)
	for some λ ∈ [0,1]. But then its combination with p is
												µ	p		⊕	s	+	1 (	-	µ	p	⊕	* ) s P	(32)
	where the new line coordinate µ is, according to (30),

  1,1)! In other words,

												s	⊕	t	=	* ~c s P ⊕	. Now, if	p =	* ~s P
	expression (35) becomes
	∈ ∈ P t [ λ ∫ ∫ 0	] 1 ,	-	β	d	λ	⋅	s	⊕	c	-	⊕ 1 s dt t P * (36)
	since again	s	⊕	t	=	t ~. Geometrically, all the P s ⊕ *
	difference vectors	s	⊕	s	-	P s ⊕	t

* '


Fabio Cuzzolin
email: cuzzolin@cs.ucla.edu

Ruggero Frezza
email: frezza@dei.unipd.it

Evidential modeling for pose estimation

Keywords: Pose estimation, training set, featurepose maps, belief functions, evidential model

Pose estimation involves reconstructing the configuration of a moving body from images sequences. In this paper we present a general framework for pose estimation of unknown objects based on Shafer's evidential reasoning. During learning an evidential model of the object is built, integrating different image features to improve both estimation robustness and precision. All the measurements coming from one or more views are expressed as belief functions, and combined through Dempster's rule. The best pose estimate at each time step is then extracted from the resulting belief function by probabilistic approximation. The choice of a sufficiently dense training set is a critical problem. Experimental results concerning a human tracking system are shown.

Introduction

Object tracking [START_REF] Moeslund | A survey of computer vision-based human motion capture[END_REF] is one of the most active field of computer vision, concerning the reconstruction of the actual pose of a moving object by processing the sequence of images taken during its motion. Most of the literature concerns model-based approaches [START_REF] Gavrila | 3D model-based tracking of humans in action: A multi-view approach[END_REF]. In case of articulated objects composed by a number of rigid parts [START_REF] Bregler | Tracking people with twists and exponential maps[END_REF], a popular choice is to use a kinematic model, while when tracking general non-rigid objects one has to recur to flexible models whose parameters are no more in relation with the relative positions of rigid subsets of the body. Statistical estimation methods have been recently introduced, ranging from maximum a-posteriori (MAP) estimation, to applications of particle filtering or multiple hypothesis techniques. All those methods however contemplate the introduction of some kind of model of the moving body, in terms of observation likelihoods, volumetric models, or other. Consider instead a scenario in which the configuration of an unknown object is desired, having no a-priori information about the nature itself of the body (i.e. rigid, articulated, deformable, etc.). As we show in this paper, the only way of doing inference on the object pose is then building a map between some salient image measurements (features) and poses through a learning procedure. In a training session the object describes an exciting enough trajectory approximating the actual parameter space Q: a finite approximation Q of the parameter space is hence acquired as a collection of poses assumed by the object. These ground truth configuration values can be produced for instance by a motion capture system, as in [START_REF] Rosales | Learning and synthesizing human body motion and posture[END_REF]. At the same time, a number of features are extracted from one or more image sequences. Their ranges (features spaces) are discretized by feeding a hidden Markov model (HMM) with the acquired measurements, and the maps from the approximate feature spaces to the approximate configuration space Q are learned. These maps, together with discrete feature and parameter spaces form the learned evidential model of the object: when the object evolves freely, the evidential model can be used to estimate its pose. We propose a cue integration approach based on the theory of evidence [START_REF] Shafer | A mathematical theory of evidence[END_REF] in which the uncertainty on the measurements is described through belief functions (b.f.), as they have no need for prior distributions (an attractive feature in a model-free estimation process). New features are transformed into belief functions, combined, and then a pointwise estimate of the body pose is computed by probabilistic approximation. Experimental results concerning human body tracking in a challenging situation are presented.

Pose estimation

Given an object moving in front of one or more cameras, the pose estimation problem consists on estimating at each time instant its configuration or pose from the available images. We assume that the pose of the moving object can be expressed as a point in some region Q of R D , called parameter space. In the case of a rigid body (for example, an airplane flying in the field of view of the cameras) the pose is simply the position and orientation of the object with respect to some fixed reference frame (for the plane, 3 coordinates giving its location and other 3 coordinates expressing its motion direction, D = 6). If the body is articulated (composed by several rigid bodies) like a human arm or hand, its pose also describes its internal configuration. A common choice is to assume a kinematic model describing the angles between the rigid parts or links forming the object. For instance, Rehg and Kanade [START_REF] Rehg | Model-based tracking of self-occluding articulated objects[END_REF] used a kinematic model of the hand with D = 27 degrees of freedom (see Figure 1) representing the angles between each pair of links of the fingers. As the object evolution is observed through one or more cameras, its pose must then be estimated from the available images. However, as images themselves are too large and redundant too be useful, usually a number of salient measurements (features) are extracted from them to be used in the estimation process. Rehg, for instance, measured the projected locations of the fingertips of the hand on the image plane.

Pose estimation of unknown objects

Consider now a situation in which we want to estimate the configuration of an unknown object, having no model or a-priori information about the nature of the body itself (i.e. rigid, articulated, deformable, etc.). The only way of estimating the object pose is then building a map between features and poses, which would allow us to make inference on the pose q ∈ Q given the evidence extracted from the images. As we have no knowledge of the analytic relations between image features and body configurations, this has to be done directly from the data by means of a learning strategy. In a training session the object evolves, exploring its range of possible configurations, and a set of its poses is collected to form a finite approximation Q of the parameter space

Q . = {q k , k = 1, ..., T }. (1)
At the same time a number N of features

{y i (k), k = 1, ..., T }, i = 1, ..., N (2)
are extracted from the images at each time instant k.

As they are collected by cameras at a finite, constant pace, the number of feature measurements is finite.

To collect Q we need a source of "ground truth" telling us what the object pose is at each instant k of the training session. One possibility is using a motion capture system as done in [START_REF] Rosales | Learning and synthesizing human body motion and posture[END_REF] or [START_REF] Howe | Bayesian reconstruction of 3D human motion from single-camera video[END_REF] for the human body tracking problem. In particular, if we apply a number of reflective markers in fixed positions of the body, the system is able to provide (through some triangulation algorithm) the 3D locations of the markers during the motion in the training stage. Since we do not know the parameter space of the object, it is reasonable to adopt the markers' locations as body configuration. This way the motion capture system generates the desired sequence of poses [START_REF] Bauer | Approximation algorithms and decision making in the Dempster-Shafer theory of evidence-an empirical study[END_REF].

Ideally, Q should be somehow "dense" in Q: ∀q ∈ Q there should be a sample q k such that qq k < ǫ for some ǫ small enough. Clearly as the actual shape of the parameter space is unknown such a condition is hard to impose.

Given the training data (1), (2), hidden Markov models provide a method to automatically build featurepose maps that can eventually be used for model-free pose estimation. We can associate the elements of the finite state space X = {1, ..., n} to coordinate versors e i = (0, .., 0, 1, 0, .., 0) ∈ R n and write the model as [9]

X k+1 = AX k + V k+1 Y k+1 = CX k + diag(W k+1 )ΣX k
where {V k+1 } is a sequence of martingale increments and {W k+1 } is a sequence of i.i.d. Gaussian noises N (0, 1). The HMM parameters are the transition matrix A = (a ij ) = P (X k+1 = e i |X k = e j ), the matrix C collecting the means of the state-output distributions (as the j-th column C j of C is equal to

E[p(Y k+1 |X k = e j )]
), and the matrix Σ of the variances of the output distributions.

Approximate feature spaces

A, C and Σ can be estimated, given a sequence of observations (the feature sequence in our case) through the Expectation-Maximization (EM) algorithm. Also, when applied to a sequence of feature values {y i (k), k = 1, ..., T } acquired in the training session, the EM algorithm provides a multi-modal Gaussian approximation of the original feature space (the range Y i ⊂ R di of the unknown feature function y i : I → Y i on the set of all images I). More precisely, a set of n i Gaussian densities (one for each state) {Γ j i , j = 1, ..., n i } on the i-th feature space is set up: their means and variances are collected in C and Σ, respectively. This is equivalent to an implicit partition

Π Yi = {Y 1 i , ..., Y ni i } (3)
of the feature range (see Figure 2), where 3) is a finite representation of the range of the i-th feature function: we call it approximate feature space.

Y j i = {y ∈ Y i s.t. Γ j i (y) > Γ l i (y) ∀ l = j}}. The collection (

Learning feature-parameter maps

As a consequence, for each feature i each sample pose

q k in the training set Q = {q k , k = 1, ..., T } is mapped to the element Y j i of the implicit partition (3) such that y i (k) ∈ Y j i ∀i, k q k → Y j i : y i (k) ∈ Y j i .
On the other hand, each element Y j i of the discrete feature space is mapped to the set of training poses whose feature value fall in Y j i ,

ω i : Y j i → Qj i . = {q k ∈ Q : y i (k) ∈ Y j i }. (4)
The application of the EM algorithm to all the feature sequences (2) then yields N maps (4) from each approximate feature space (3) to the approximate parameter space Q.

Evidential modeling

Once feature-pose maps are learnt from the training data they can be used to design a method for estimating the pose of the object of interest. As single features cannot guarantee of stability and invariance to nuisance factors, extracting multiple cues can be useful to solve ambiguities and increase the robustness of the overall system. Some researchers have actually posed the cue integration issue in a rigorous probabilistic setup [START_REF] Sminchisescu | Covariance scaled sampling for monocular 3D body tracking[END_REF]. However, in a Bayesian setting it is hard to design a model-independent feature extraction process, and a number of independence or incorrelation assumptions are needed to make the formulas tractable [START_REF] Sidenbladh | Learning the statistics of people in images and video[END_REF].

The theory of evidence

We propose an uncertainty description based on theory of evidence as, in contrast to the Bayesian formalism, no a-priori distributions are needed [START_REF] Shafer | A mathematical theory of evidence[END_REF] as required in the model-free estimation problem introduced in Section 2.

Definition 1. A basic probability assignment (b.p.a.) on a finite set (FOD) Θ is a function m : 2 Θ → [0, 1] such that m(∅) = 0, m(A) ≥ 0 ∀A ⊂ Θ, A⊂Θ m(A) = 1.
2 Θ denotes the power set of Θ. The elements of 2 Θ associated with non-zero values of m are called focal elements (f.e.) and their union C core.

Definition 2. The belief function s associated with a basic probability assignment m is the unique function

s : 2 Θ → [0, 1] such that s(A) = B⊂A m(B).
In the theory of evidence finite probability functions are just peculiar belief functions such that m(A) = 0 ∀ A s.t. |A| > 1 (Bayesian b.f.). Belief functions can be combined by means of Dempster's rule.

m(A) = i,j:Ai∩Bj =A m 1 (A i ) • m 2 (B j ) 1 -i,j:Ai∩Bj =∅ m 1 (A i ) • m 2 (B j ) . (5)
The theory's major restriction (at least in its original formulation 1 ) is the fact that belief functions are defined on finite domains. However, as the training set Q is finite, the use of belief functions is not problematic.

Evidential model

Dense training sets (as defined in Section 2.1) are good formal approximations of the unknown parameter space of the moving object. On their side, HMMs provide a method for finding multi-modal approximations of the involved feature spaces, and a way of building maps from each feature space to the approximate parameter space. A unifying framework in which to arrange training sets, approximate feature spaces and feature-pose maps would be desirable. The theory of evidence is such a framework, as both approximate feature spaces (3) and training sets (1) can be thought of as FODs. We will denote with Θ i = {θ 1 i , ..., θ ni i } the FOD corresponding to the implicit partition Π Yi .

For each feature i, the collection π Q i . = { Qj i , j = 1, ..., n i } forms a partition of the approximate parameter space Q. In the evidential language the EM algorithm builds a refining ω i (4) between each approximate feature space (3) and the training set Q. Definition 4. Given two FODs Θ and Ω, a map ω : 2 Θ → 2 Ω is called refining if it satisfies the following conditions: 1)

ω({θ}) = ∅ ∀θ ∈ Θ; 2) ω({θ}) ∩ ω({θ ′ }) = ∅ if θ = θ ′ ; 3) θ∈Θ ω({θ}) = Ω.
A refining ω maps Θ to a disjoint partition of Ω. Ω is called a refinement of Θ, while Θ is said a coarsening of Ω (see Figure 3

-top)).
As a map between features and configurations, a refining ω i allows us to make inferences in Q on the pose of the moving object, based on the evidence provided by a feature measurement living in Θ i . However, as inferences based on a single feature are often inaccurate and unreliable, we select in the training stage a number of different features and build a refining for each of them. Q then becomes the common refinement [START_REF] Shafer | A mathematical theory of evidence[END_REF] of the collection of approximate feature spaces Θ 1 , ..., Θ N (Figure 3-bottom), and is the place where all the evidence provided by the different image measurements 1 In fact Shafer extended the theory to infinite frames of discernment in [START_REF] Shafer | Allocations of probability[END_REF]. The collection of FODs Q, Θ 1 , ..., Θ N along with their refining maps is characteristic of both the unknown object to track and the chosen feature functions y 1 , ..., y N : we call it evidential model.

Q W w q w(q) A ( ) A w ( ) A w Q Q Q Q Q 1 Q 2 n

Pose estimation

Measurement functions

The evidential model of the object is built in the training stage, when an adequate training set of the object's motion is acquired (see Section 2.1). After that, it can be used to estimate the pose of the moving object, as new evidence becomes available.

When a new image is acquired, new visual features are extracted. Those continuous features can be transformed into belief functions on the approximate feature spaces:

y i → s i : 2 Θi → [0, 1].
We call these b.f. measurement functions (m.f.).

This can be done in two steps. Given as input a feature value y i ∈ Y i the Markov model H i produces as output the set of likelihoods {Γ j i (y i ), j = 1, ..., n i } of this measurement with respect to each state e j of the model (see Figure 2). Computing the measurement function s i then reduces to building a belief function from this set of likelihoods. These in turn detect a consonant belief function (i.e. a b.f. whose focal elements are nested, [START_REF] Shafer | A mathematical theory of evidence[END_REF]) through the following expression, due to Shafer:

s i (A) = 1 - max θ j i ∈ Ā Γ j i (y i ) max θ j i ∈Θi Γ j i (y i )
.

The consonant measurement functions s 1 , ..., s N have then to be projected to the common refinement Q to be combined, in order to infer the current pose q of the object.

Projections of measurement functions

In model-free estimation it is hard to formulate analytic relations between distinct features as they may concern completely unrelated aspects of the images. The evidential model, instead, provides a formal description of these relations in terms of refinings. Roughly speaking, ω(A) is the largest subset of Θ that implies A, while ω(A) is the smallest subset of Θ implied by A (see Figure 3-top again).

If Ω is a refinement of Θ with refining ω then a b.f. Every m.f. then generates a collection of "sister" functions defined on the other FODs, called projections.

s ′ : 2 Ω → [0, 1] on Ω is called the vacuous extension of a b.f. s : 2 Θ → [0, 1] on Θ iff s(A) = s ′ (ω(A)) for all A ⊂ Θ,
Theorem 1. The projection of a m.f. s i defined on Θ i onto another discrete feature space Θ j has the following expression:

π j [s i ] : 2 Θj → [0, 1], π j [s i ] = s i • ω i • ω j . Its basic probability assign- ment can be computed from m i as π j [m i ](A) = B⊂Θi:ωj (ωi(B))=A m i (B).
Proof. The vacuous extension s ′ of a belief function

s : 2 Θ → [0, 1] to a refinement Ω, ω : 2 Θ → 2 Ω has a b.p.a. m such that m(A) = m ′ (ω(A)) = m ′
• ω and can be expressed as s ′ = s•ω ([12], Theorem 7.4). The projection π j [s i ] of a b.f. s i : 2 Θi → [0, 1] onto another discrete feature space Θ j is then the restriction to Θ j of the vacuous extension of

s i to Q, so that π j [s i ] = s ′ j • ω j = s i • ω i • ω j . Its basic probability assignment is π j [m i ](A) = C⊂ Q:ωj (C)=A m ′ i (C) which is equal to B⊂Θi:ωj (ωi(B))=A m ′ i (ω i (B)) = B⊂Θi:ωj (ωi(B))=A m i (B) for m ′ i (C) = 0 iff C is the image of a f.e. B of s i .
As a consequence, the set of focal elements of

π j [s i ] is E πj [si] = {A ⊂ Θ j |A = ωj (ω i (B)), B ∈ E si } and its core C πj [si] = ωj (ω i (C si )).
Theorem 2. The projection of a consonant belief function is still consonant, even if it has not in general the same number of focal elements.

Proof. Let us call A 1 ⊆ • • • ⊆ A K the nested focal elements of s: obviously its extension s ′ to Q has as focal elements ω i (A 1 ), ..., ω i (A K ). They are all distinct subsets of Q for ω is a refining. They are also nested so that s ′ is still a consonant b.f. over Q. Now, the focal elements of π j [s i ] are the restrictions of those subsets to Θ j :

ωj (ω i (A k )) = {θ ∈ Θ j |ω j ({θ}) ∩ ω i (A k ) = ∅}.
Since they are nested, if

ω j ({θ}) ∩ ω i (A k ) = ∅ then ω j ({θ}) ∩ ω i (A l ) = ∅, l ≥ k so that ωj (ω i (A k )) ⊂ ωj (ω i (A l )), l ≥ k i.e. π j [s i ] is consonant.
However, it is not generally true that ∀k, l ∃θ ∈ Θ j s.t. θ ∈ ωj (ω i (A l )) and θ ∈ ωj (ω i (A k )): it is actually easy to find a counterexample. Hence in the chain ωj (ω i (A 1 )) ⊂ • • • ⊂ ωj (ω i (A K )) some equalities may appear.

Theorem 2 shows how consonant belief functions are then invariant under projection, and hence a formally correct representation of feature measurements.

Pointwise estimation

Once the measurement functions s 1 , ..., s N are projected onto Q, they can be combined using Dempster's rule. In absence of conflict the orthogonal sum of the m.f. finally yields a belief function ŝ on Q. The easier way to extract a single pose estimate q from the belief estimate is then approximating ŝ with a finite probability p on Q, and then compute its mean value

q = T k=1 p(q k ) • q k .
The problem of approximating a belief function with a finite probability has been widely studied [START_REF] Cobb | A comparison of methods for transforming belief function models to probability models[END_REF][START_REF] Ben Yaghlane | Coarsening approximations of belief functions[END_REF].

Natural approximations of a belief function s are the relative plausibility of singletons p = P * s [START_REF] Voorbraak | A computationally efficient approximation of Dempster-Shafer theory[END_REF] P * s (θ) =

P * s ({θ)} θ ′ ∈Θ P * s ({θ ′ })
where P * s : 2 Θ → [0, 1] is the associated plausibility function, or the pignistic function [START_REF] Smets | Belief functions, Non-Standard Logics for Automated Reasoning[END_REF]. Under weak local linearity assumptions on the parameter space, this approximation produces good results. Several fast implementation of Dempster's rule exist for restricted situations (see [START_REF] Bauer | Approximation algorithms and decision making in the Dempster-Shafer theory of evidence-an empirical study[END_REF][START_REF] Denoeux | Approximating the combination of belief functions using the fast Moebius transform in a coarsened frame[END_REF] among the others). However, consonant b.f. can only have n focal elements (being nested, Section 5.1). This reduces the computational complexity of their sum to O(n 2 ) instead of O(2 2n ).

6 Analysis of the evidential model

Quantization and ambiguities

We have seen that learning a model directly from the data necessarily implies some sort of approximation of the involved spaces in terms of samples. However, this has non-trivial consequences on the performance of the resulting estimation. In particular, the degree of discretization of feature spaces and training set have a direct influence on the presence of ambiguities during estimation. Again, the evidential formalism is powerful enough to give a formal picture of the ambiguity issue, and help the assessment of the adequate level of quantization. We have seen how Q is a common refinement of the approximate feature spaces. However, a collection of compatible FODs has many common refinements. One of these is particularly simple.

Definition 6. Consider a collection of compatible FODs

Θ 1 , ..., Θ N . If another FOD Θ is such that: 1) ∀i ∃ω i : 2 Θi → 2 Θ refining; 2) ∀θ ∈ Θ ∃ θ i ∈ Θ i for all i = 1, ..., N such that {θ} = ω 1 ({θ 1 }) ∩ ... ∩ ω N ({θ N }), then this unique [12] FOD Θ . = Θ 1 ⊗• • •⊗Θ N is called minimal refinement of the collection Θ 1 , ..., Θ N . Θ 1 , ..., Θ N are said to be independent if ω 1 (A 1 ) ∩ • • • ∩ ω N (A N ) = ∅ whenever ∅ = A i ⊂ Θ i ∀i.
Now, imagine that the N feature functions assume the discrete values θ 1 , ..., θ N respectively. Each piece of evidence implies an object pose inside the subset ω i (θ i ) of the training set, so that from θ 1 , ..., θ N it can be inferred that the estimated pose falls inside the set

ω 1 (θ 1 ) ∩ ... ∩ ω N (θ N ). (6)
In other words, configurations in the same intersection of the form (6) are indistinguishable. But now, those subsets are the elements of the minimal refinement, so that Theorem 3. Each pair of poses of the training set can be distinguished under the evidential model iff Q is the minimal refinement of the feature spaces.

In this case, for each training pose q k there exists a combination of feature values θ 1 , ..., θ N s.t. q k is perfectly resolved:

q k = ω 1 (θ 1 ) ∩ ... ∩ ω N (θ N ).
Given a training set it is hence desirable to choose the number of states of the N HMMs associated with each feature space in order to bring the minimal refinement Θ 1 ⊗ • • • ⊗ Θ N as close as possible to Q. As the "natural" number of states is determined by the clusters actually formed by the feature data acquired in the training session, sometimes the addition of new features becomes necessary to resolve the ambiguities.

Conflict management

Dempster's combinations of generic belief functions defined on different frames Θ 1 , ..., Θ N are always guaranteed to exist only if Θ 1 , ..., Θ N are independent [START_REF] Cuzzolin | Algebraic structure of the families of compatible frames of discernment[END_REF]. This could seem a serious obstacle to evidence combination in the evidential model. However, measurement functions are not generic b.f., as they are peculiar b.f. built by means of a HMM (see Section 5.1).

Let us first suppose one of the sample poses q k is presented to the model, with feature values y 1 (k), ..., y N (k). In the worst case, for each feature i there will be a single state j i with Γ ji i (y i ) >> Γ j i (y i ) ∀l = j i . The algorithm of Section 5.1 will then yield a set of N Bayesian b.f. with m i (θ ji i ) = 1, m i (A) = 0 for A = {θ ji i }. Now, as q k ∈ ω i (θ ji i ) for all i (by definition of ω i ), ω 1 (θ j1 1 ) ∩ • • • ∩ ω N (θ jN N ) ⊃ q k = ∅ and their Dempster's sum always exists. Hence, a conflict is possible only if q ∈ Q. Consider then two scalar features as in Figure 4, with ranges partitioned in 2 clusters delimited by the horizontal lines and a training set formed by the 6 points marked on the absciss. The refining maps are

y 1 2 3 4 5 6 1 1 2 4 5 6 2 3 1 y 1 2 y 2 1 y 2 2 q q Q 1 Q 2 Q 3 Q 1 Q 2 Q 3
ω 1 (Y 1 1 ) = {4, 5, 6}, ω 1 (Y 2 1 ) = {1, 2, 3} and ω 2 (Y 1 2 ) = {4, 5, 6}, ω 2 (Y 2
2 ) = {1, 2, 3} respectively. But now, for each of the poses q in the highlighted region Q 2 , ω 1 (y 1 (q)) = {1, 2, 3} while ω 2 (y 2 (q)) = {4, 5, 6} so that ω 1 (y 1 (q)) ∩ ω 2 (y 2 (q)) = ∅ and there is no combination. Formally, each implicit partition of a feature range Y i is naturally associated with a partition of the parameter space Q through the inverse feature map

{Y 1 i , ..., Y ni i } y -1 i → Π i Q = {y -1 i (Y 1 i ), ..., y -1 i (Y ni i )}. ( 7
)
On the other side, there exists a refining ω ′ i between Θ i and Y i , namely ω ′ i (θ j i ) = Y j i , so that each feature value y i can be mapped to a set of training poses in Q,

y i → ω i (ω ′ i (y i )) = {q k ∈ Q : y i (q k ) ∈ Y jy i i } where ω′ i is the reduction of ω ′ i and Y jy i i is the region of Y i containing y i . Hence, each object configuration q ∈ Q has a set of representatives in Q, ω 1 (ω ′ 1 (y 1 (q))) ∩ • • • ∩ ω N (ω ′ N (y N (q))). (8)
As the above example explains, Proposition 1. There is conflict between measurement functions iff the underlying object pose q has no representatives [START_REF] Moeslund | A survey of computer vision-based human motion capture[END_REF] in the training set.

The intersection of the partitions Π i Q of the parameter space associated with the quantized feature ranges (Equation ( 7)) finally detects another partition of Q,

Π Q = {y -1 1 (Y j1 1 ) ∩ • • • ∩ y -1 N (Y jN N )} ∀ j 1 = 1, ..., n 1 , • • • , j N = 1, ..., n N .
The nonrepresented region of Q is then the set of the elements of Π Q which do not contain any sample pose (as the marked region Q 2 in Figure 4). This suggests that Proposition 2. Conflict is impossible in the evidential model iff

Π Q ∼ Θ 1 ⊗ • • • ⊗ Θ N .
Adding new samples in each of the non-represented elements of Π Q (like q ∈ Q 2 in Figure 4) would ideally solve the problem. Unfortunately, as we have no apriori knowledge about the parameter space, the best we can do is updating the evidential model each time a conflict takes place, progressively reducing the chance of this happening again.

Algorithms

It is time to summarize the learning and estimation algorithms we introduced in Sections 3, 4 and 5.

Model learning

In the training stage an evidential model of the object is built. The body moves in front of the camera(s), exploring its parameter space, while a sequence of training poses Q = {q k , k = 1, ..., T } is provided by a source of ground truth (for instance a motion capture system, Section 2.1). At the same time:

1. we compute a number of feature measurements y i , i = 1, ..., N from all the images; 2. we process every feature sequence {y i (k), k = 1, ..., T } by means of a HMM H i with n i states, obtaining 2.a the N approximate feature spaces Θ i , i.e. the implicit partitions of the ranges associated with the states of the corresponding HMMs (Section 3.1); 2.b the N refinings ω i (4) between each feature space Θ i and the approximate parameter space Q.

Even after choosing the desired feature functions, the resulting evidential model still depends on the dimensions {n i , i = 1, ..., N } of the approximate feature spaces (the number of states of the HMMs). The "best" value of n i can be estimated by analyzing the clusters formed by the training data, or alternatively learned by measuring the estimation error as n i increases.

Pose estimation

Given an evidential model of the moving body with N features, estimating the object's pose reduces to the following steps: Given one or more images at time t 1. the N feature values are extracted from the acquired image(s); 2. the likelihoods {Γ j i (y i (t)), j = 1, ..., n i } of each feature value y i (t) associated with the corresponding HMM H i are computed (Section 3.1); 3. for each feature i a measurement belief function s i (t) is built from these likelihoods (Section 5.1); 4. all the m.f. {s i (t), i = 1, ..., N } are projected onto the approximate parameter space Q by vacuous extension (Section 5.2);

in absence of conflict their orthogonal sum ŝ(t)

. = s 1 (t)⊕...⊕s N (t) is obtained through Dempster's rule; otherwise the new pose is added to Q, and the model is updated; 6. the pointwise estimate q(t) of the object configuration is obtained from ŝ(t) after Bayesian approximation (Section 5.3).

Experimental results

We tested our evidential modeling technique in a challenging setup, involving the pose estimation of hu-man arms and legs from two well separated views. To collect the necessary ground truth we used a marker-based motion capture system [START_REF] Rosales | Learning and synthesizing human body motion and posture[END_REF][START_REF] Howe | Bayesian reconstruction of 3D human motion from single-camera video[END_REF] built by E-motion. The person was filmed by two DV cameras (Figure 5). In the first experiment we asked him to make his arm follow a trajectory which could hopefully cover the configuration space of the arm itself, keeping his wrist blocked and standing on a fixed spot on the floor to reduce the dimensionality of the space (2 d.o.f.s for the shoulder and 2 for the elbow). In the second experiment we tracked the legs, assuming that the person was walking normally on the floor, and collected the training set by sampling a random walk on a small part of the floor. We adopted color segmentation to separate the moving object from a non-static background through a colorimetric analysis of the body of interest (Figure 6). We then found the bounding box around the the silhouette of the segmented upper torso or legs, building a feature vector as the collection max(row), min(row), max(col), min(col) of the row and column indexes defining the box. For the arm experiment we placed four markers on shoulder, elbow, wrist and hand, and used the resulting 12-component vector of their 3D positions as body pose. For the leg experiment we placed 6 markers on hips, knees and feet. The length of the training sequences was 1726 frames for the arm and 1952 frames for the legs. We then built for the arm experiment three different evidential models: one using the left view only, with N = 2 feature spaces and n i = 5 states for both features; a second model for the right view only, with N = 3 acquired a testing sequence for each experiment and compared the results with the ground truth provided by the E-motion system. The single-view estimates were rather mediocre. Accordingly, the minimal refinements Θ i for the left and right models were of size 22 and 80 respectively (the larger the size, the finer the resolution of the model).

As Figure 7 shows, the estimates obtained exploiting both views were clearly better than a simple selection of the best partial estimate at each instant, as the ambiguity analysis confirms. Θ i for the overall model had size 372 and the sizes of the five largest undistinguished regions of Q were 69,53,43,38,28 respectively, with 139 samples perfectly resolved! We also computed the estimation error by measuring the Euclidean distance between the real and estimated 3D location of each marker over the whole testing sequence. The average estimation errors were 17.3, 7.95, 13.03, and 2.7 centimeters respectively for the four markers. Figure 9 shows instead the performance of the estimation algorithm in the leg experiment, for a 200frame-long test sequence. The results were a bit less impressive but still good, mainly due to the difficulty of segmenting a pair of black pants against a dark background (see Figure 5c). This is confirmed by the numerical results. The average estimation errors were 25.41, 19.29, 21.84, 19.88, 23.00, and 22.71 centimeters respectively. Consider that the cameras were located at a distance of about three meters. No significant conflict problem was reported.

Other learning-based approaches

A comparison with the performance of other methods only makes sense for data-driven model building methods. In fact, a small number of other researchers have proposed an estimation framework based a learning process. Howe et al. [START_REF] Howe | Bayesian reconstruction of 3D human motion from single-camera video[END_REF] proposed to use some a-priori knowledge about human motion learned from training data to resolve the ambiguities of monocular tracking. They modeled the probabilities of short motions called snippets as a mixture of Gaussian density, and adopted EM to find the weight of each cluster. However, the system was tested on short clips only, as the authors admitted it would not be reliable for significantly long sequences. Here instead we have tested our algorithms over rather long sequences. Rosales and Sclaroff [START_REF] Rosales | Learning and synthesizing human body motion and posture[END_REF] proposed instead a pose estimation technique in which the object pose was expressed as a 2D marker configuration. In the training stage, a motion capture system provided the 3D marker positions of the given object in the motion sequences, whose 2D projections formed the ground truth of the learning process. A 3D model of the object was then used to generate synthetic silhouette views, from which some visual features were extracted. The training set of projected 2D markers was clustered using the EM algorithm, and for each cluster a multi-layer perceptron was trained to map features to 2D marker positions, analogously to what we have shown is Section 3.2.

The training data was more extensive, consisting on 5 sequences of some 200 frames each. The method was applied to synthetic silhouettes obtained through a 3D model, while the results seemed to degrade a little when real video data were considered.

Conclusions

In this paper we presented a bottom-up technique for pose estimation of arbitrary unknown objects (artic-ulated, flexible, etc.) based on learning a direct mapping between features and poses in a learning stage, and combining the available data in the framework of the evidential reasoning. We showed how to use the EM algorithm for HMMs to build multi-Gaussian approximations of the feature spaces and direct featurepose maps. We adopted the evidential language to formalize and implement the information fusion, as the ToE makes no use of a-priori distributions, a very attractive feature in the context of model-free estimation. The ToE also provides tools to represent feature-pose maps through the notion of refining, and analyze incorrect inferences due to coarse approximations or ambiguities in the learnt model. We chose to represent features as belief functions, also because of their relative simplicity. However, the use of Dempster's rule as fusion mechanism is implicitly based on the assumption that the pieces of evidence carried by the features are independent. This is reasonable in a model-free situation in which no a-priori knowledge of their relationships is available, and is often assumed in the literature. The approach has been tested in a challenging setup, concerning real video sequences with realistic non-static backgrounds. The experimental results support this assumption. It would be interesting to understand what happens when we represent the uncertainty by means of some other class of imprecise probabilities, such as credal sets, coherent previsions, or the imprecise Dirichlet model. However, this well deserves a paper of its own, and will be the object of further research in the near future.

Figure 1 :

 1 Figure 1: Rehg's kinematic model of the hand.

  the feature function y (feature space) Gaussian densities associated with the states of a Markov model Gaussian probability densities

Figure 2 :

 2 Figure 2: Implicit partition associated with a Markov model with three states. To each state corresponds a Gaussian density on the range Y of the feature function (abscissa). Together they detect a partition of the range into three regions Y 1 , Y 2 , Y 3 (separated by the vertical lines).

Definition 3 .

 3 The orthogonal sum or Dempster's sum of two belief functions s 1 , s 2 is a new belief function s 1 ⊕ s 2 whose focal elements are all the possible non-empty intersections between focal elements A i , B j of s 1 and s 2 respectively, and whose b.p.a. is given by

Figure 3 :

 3 Figure 3: (top) A refining ω between two FODs Θ and Ω. Each element θ ∈ Θ is associated with an element of a disjoint partition of Ω. Each subset A ⊂ Ω can be mapped to its inner ω(A) or ω(A) outer reduction as in figure. (bottom) Evidential model architecture.

Definition 5 .

 5 The maps ω : 2 Ω → 2 Θ , ω(A) = {θ ∈ Θ|ω({θ}) ⊂ A} and ω : 2 Ω → 2 Θ , ω(A) = {θ ∈ Θ|ω({θ}) ∩ A = ∅} are called inner and outer reduction associated with the refining ω.

  and its focal elements are exactly the images of focal elements of s: m ′ (B) = 0 iff B = ω(A) for some A s.t. m(A) = 0.

Figure 4 :

 4 Figure 4: Conflict in the evidential model.

Figure 5 :

 5 Figure 5: Human bodypart tracking. a),b) Training images of a person moving his right arm. c),d) Training images of the person walking inside a rectangle drawn on the floor.

Figure 6 :Figure 7 :

 67 Figure 6: Feature extraction process. Left: original image. Right: the object of interest is color segmented, and the bounding box around it is detected.

Figure 8 :

 8 Figure 8: Estimation errors for markers 4 in the arm experiment. The horizontal line indicates the average value.

Figure 9 :

 9 Figure 9: Performance of the two-view pose estimation for the leg experiment on a testing sequence of length 200 with N = 6 and n i = n = 5. The estimates for some significative components of the pose vector (components 4,7,9, and 12) are shown in red, against the ground truth values (in blue).