MMVR III Spinal System

Diagramming Registration

Connectivity and Structure

    Jon T. Lea       Julio J. Santos-Munné    Michael A. Peshkin

Department of Mechanical Engineering

Northwestern University

Evanston, IL 60208

Abstract. Computer-assisted surgical systems must bring preoperative diagnostic images, surgical plans, patient anatomy, surgical tools, robots, and other components into accurate alignment with one another. Multi-step registration procedures have been devised, which are difficult to analyze, or even to describe concisely.

Here we introduce a notation for diagramming registration strategies and procedures, and apply it to a spectrum of current methods. The notation uses a graph-theoretic framework consisting of two elements: nodes, representing objects; and links, representing actions. Connectivity properties of the resulting registration graph are readily determined by inspection.

Using the registration graph one may confirm the validity of registration, check if frameless surgery is possible, list serial sources of error, determine which objects must be rigidly fixated, determine the existence and extent of redundant registration pathways, identify structurally identical registration methods, and devise and describe new registration architectures.

1. What is registration?

Computer-assisted surgical (CAS) systems involve some components that image, measure, or control position. These include robots, articulated pointers, optical tracking devices, fluoroscopes, and CT or MRI scanners. Other components cannot be so described, but are equally important. These include bones, tissues, fiducials, cutting tools, and many others.

To execute surgical procedures in accurate accord with a computer-based surgical plan, the spatial relationships between many of the components above must be determined and maintained. This is accomplished through a series of measurements and alignments of the components, a process called registration.

As an example, consider the registration strategy employed by Paul, et al. [1], in Integrated Surgical System's robotic CAS system (RoboDoc^TM) for total hip arthroplasty. A preoperative plan (in this case, a milling tool path) is created on a 3D reconstruction of the femur obtained from diagnostic CT images. The locations of three small titanium pins, implanted in the femur prior to the CT scan, are noted in the set of CT images.

Intraoperatively, the femur is immobilized with respect to the robot, and the pins are exposed. A probe on the robot's end-effector is guided to each pin. The location of each pin with reference to the robot's base is recorded by reading the robot's arm configuration when the probe is touching the pin. Since the intended milling tool path is known with respect to pins in the CT data set, that path can now be executed with the milling tool by the robot, with respect to the actual location of the pins.

2. Registration graphs

The ISS RoboDoc registration strategy is both very well known and easy to explain in text, as above. We will use it to introduce the registration graph. Figure 1 shows a registration graph of the RoboDoc system.

2.1 Nodes and links

A registration graph contains nodes interconnected by links. (The terms vertices and edges are more standard, but the geometric connotations of these terms make them confusing in our context.)

Nodes, shown as a small circles, represent objects. Examples in Figure 1 include the robot, fiducial pins, CT scanner, probe on the robot's end-effector, coordinate measuring machine (CMM), and cutting tool (a burr). A surgical plan is of course not a physical object, but it turns out to connect to other objects in a manner similar to that of a physical object, so it is also shown as a node.

An unusual and key feature of registration graphs is that measurement devices, and the objects whose positions they measure, enter into the graph in identical fashion; all are simply nodes. (Optionally, a node may be thought of as specifically representing as a coordinate frame associated with an object, as in Paul [2].)



Figure 1.  Nodes and links of the     
registration graph for the ISS RoboDoc   
system.

Links, shown as lines, connect two nodes. They represent an act of measurement which establishes a known spatial relationship between the objects represented by the two nodes.

One usually thinks of a measuring device dispassionately measuring the spatial relationship between two other objects, thus establishing a connection between them. A notation consistent with this philosophy would show a measuring device as a link, connecting the objects it measures. Here, however, a measuring device is represented as a node, and as a consequence it is more intimately involved: it reaches out to measure the relationship of its own coordinate frame to that of another object.

Note also that a link does not represent the spatial relationship itself, but rather the act of measuring it. A spatial relationship, even a fixed, permanent one, may exist between two objects, but a link will not necessarily exist between them.

Other graph conventions might seem more natural, and could equally well describe the RoboDoc registration strategy. The one described here is the only convention we have found that extends successfully to arbitrarily complex registration strategies.

The registration graph in Figure 1 shows all of the measurement operations, and all of the objects, that are involved in registration in the RoboDoc system:

A coordinate measuring machine (CMM) measures its own relation to three parts of the end-effector: the probe, the mounting flange, and the burr.
A CT scanner measures its own relation to the fiducial pins, and to the femur. A "plan" node is shown as well, with a link to the CT like that of the femur.
The robot measures its own relation to the end-effector flange. It can also command that relation, but that capability is not relevant to us yet.
A bone motion monitor (an articulated arm) measures its own relation to a "flag" on the femur. However neither the relation of this arm to the robot, nor of the flag on the femur to the fiducial pins, is ever established.
All of the links listed above connect one node that is capable of measuring, to one that is not. One link was not listed: the one that connects probe to fiducial pins. Neither a probe nor a fiducial pin is normally thought of as a measuring device. Yet they do have a very limited measuring capability; they can measure coincidence. Bringing two objects into physical contact can be thought of as a measurement operation.

One can now observe the series of links that connects plan to tool. It is just such a connected subgraph that validates registration. However, the connected subgraph in Figure 1 does not reflect several of the important aspects of registration. First, the links are valid at different times. For instance, the validity of the [probe : fiducial pins] link is broken (by moving the end-effector) before surgery is begun, so registration would seem to be lost at that point. Second, the robot appears to be uninvolved. In practice the robot is the central device, and a primary error source. These problems are resolved by the introduction of events and induced links.

2.2 Events and induced links

When objects (nodes) move relative to one another, measurement operations (links) that were previously performed become invalid. To group links that are simultaneously valid we introduce events. A link's validity during one or more events is indicated by one or more event tags on the link.

Many links are permanently valid, notably ones established between two objects on a single rigid body. As a notational convention to avoid cluttered graphs, we leave such links untagged; these are understood to belong to all events.

For instance, event [[questiondown]] includes measurements of the relation between the CMM and three components of the end-effector. The links to the CMM become invalid when the end-effector is removed from the test bay of the CMM. However, the known spatial relationship of the components to each other, which can be derived from the links to the CMM, persists. A new construct, the induced link, captures this persistence.

An induced link, shown as a dashed line connecting two nodes, may be added to the graph if there is a simultaneous connected subgraph that connects the two nodes. A simultaneous connected subgraph is simply a subset of the nodes and links, such that all of the nodes are connected to one another, directly or indirectly, via links that belong to a common event. (Recall that untagged links belong to all events.)


Figure 2.  Registration graph of      
ISS RoboDoc system, showing induced     
links and event tags.

Figure 2 shows the RoboDoc system again, now including the induced links. Induced links indicate indirect knowledge of the spatial relationship between two objects, derived via the simultaneous connected subgraph that connects them. The validity of the indirect knowledge may greatly outlast that of the subgraph which induced it. Most of the induced links in Figure 2 connect pairs of objects that belong to a single rigid body. No relative motion ever occurs between such pairs, so their validity is permanent.

However, consider the induced link [robot : fiducial pins]. The simultaneous connected subgraph that induced it is [robot : flange : probe : fiducial pins], all of which are members of event ~. (The untagged link [robot : flange] belongs to all events because the robot at all times measures the position of its end flange.) The induced link [robot : fiducial pins] is valid so long as the femur does not move relative to the robot. This is reflected in the hardware of the RoboDoc system; the femur must be rigidly fixtured with respect to the robot, from the time the fiducial pins are touched until the computer-assisted phase of surgery is complete.

2.3 Connectivity properties

We can now make some observations concerning the connectivity of a registration graph. First, the graphs provide a basic condition for registration:

Basic connectivity: Registration requires that there exist a       
simultaneous connected subgraph containing the plan, the           
involved anatomy, and the tool.

In Figure 2, the subgraph is [plan : femur : fiducial pins : robot : flange : tool].

Not all CAS systems contain an active positioning device. For those that do (in the present example, a robot) a further connectivity property is needed, in order to be able to compute the actuator velocities needed to move the tool. This capability might be called control.

Control connectivity: Control requires that the robot (or other    
active positioning device) must also be a part of the              
simultaneous connected subgraph.

If a graph has basic connectivity but not control connectivity, it is still possible to determine the actual tool position with respect to the plan. However it is not possible to predict what effect a particular commanded motion of the positioning device will have on the tool's location with respect to the plan.

2.4 Maintaining registration

It is not enough to establish registration at a single moment; we must continuously maintain registration while the tool moves. It may also be possible to maintain registration while the patient moves during surgery. If so, the patient does not need to be rigidly immobilized, an attractive feature for a surgical system. Both issues can be addressed through the connectivity properties of registration graphs.

We make a distinction between two kinds of links: transient and sustained.

A transient link between two nodes, shown as a thin line, indicates a one-shot measurement operation. Examples: a bone contour is identified in a CT image; a probe touches a fiducial marker or a bone contour; a single fluoroscopic image of an alignment artifact is acquired.

A sustained link between two nodes, shown as a bold line, indicates an ongoing measurement operation performed by one of the two objects. Also, when two objects are brought into coincidence and locked, the link is considered to be sustained. Examples: an optical tracking device monitors the location of a marker on a moving bone; a tool is held by a robot that possesses joint encoders; clips on a headframe are brought into contact with mounting brackets and fastened.

Figure 3 shows the registration graph for the RoboDoc system with the [bone motion monitor : flag] and [robot : end effector] links shown as bold lines to reflect their sustained character.

Sustained links may have event tags; they are not necessarily permanently valid. Their distinguishing characteristic is that during the events for which they are valid, they collect continuous, real-time data (or else hold objects continuously in coincidence.)

We noted above that the induced link [robot : fiducial pins] in the RoboDoc system required a femur fixator to maintain it. More generally, we make the following observation:

Fixation: Induced links require immobilization.

       

Figure 3.  Registration       
graph of ISS RoboDoc system, with       
sustained links shown as bold lines.    
The end-effector motion group is        
collapsed to single node using the      
reduction rule.

Sometimes the required immobilization is trivially present because the induced link connects objects which are both parts of a single rigid body, e.g. the end-effector. Other induced links require the explicit use of fixation devices. For instance, the [robot : fiducial pins] induced link requires a femur fixator in the RoboDoc system.

Where an explicit fixation device is needed, it may couple the objects directly, or it may couple any parts of the rigid bodies to which they belong. A motion group, indicated by a rounded rectangle, groups nodes that belong to a single rigid body. Motion groups are merely visual aids; they do not affect the connectivity properties of the graphs. However, they make the need for immobilization devices especially visible by emphasizing induced links that are not contained within a motion group.

We can now add a third connectivity property:

Sustained connectivity: Continuous registration despite tool       
motion and patient motion requires that the simultaneous           
connected subgraph consist entirely of sustained and induced       
links.

Sustained connectivity does not necessarily imply a non-fixated patient during surgery is possible. Immobilization requirements created by induced links between the patient and other motion groups still pertain.

2.5 Graph reduction

One of the benefits of the registration graph is that it makes explicit the entire chain of measurements that comprise (and contribute error to) registration. However explicitness sometimes comes at the expense of clarity and conciseness. We may prefer to represent an end-effector as a single node, as in Figure 3, rather than as a milling tool, pointer, and flange whose relationship has been established by a CMM, as in Figure 2. Also, when deciding how to represent a robot we may wish to demonstrate that it can be shown as a single node, rather than thirteen serially connected nodes representing joints and angle encoders. A reduction rule makes clear the conditions under which such collapse can be performed without affecting any connectivity properties:

Reduction rule: Nodes connected by untagged sustained or induced   
links may be collapsed into one node.

The reduction rule should be used sparingly to remove uninteresting clutter, or to help determine how new components should be represented. A good rule of thumb is not to collapse nodes unless the combined node can be given an enlightening name. For instance, thirteen robot nodes can be collapsed to a single node named "robot", and the several components of an end-effector can be collapsed to a single node named "end-effector". It is usually not a good idea to collapse a robot and its end-effector to a single node. Also, collapsing a robot and a fluoroscope can only result in a "fluorobot", and is a poor idea.

3. Graphs for other registration strategies

In the following sections, we graph other CAS systems, selected to illustrate a variety of interesting features. The graphs are detailed to the extent we can determine each system's registration procedures from the literature or from other communication.

3.1 Other systems like RoboDoc

Figure 3 showed the registration graph of the RoboDoc system. Several other CAS systems have virtually identical registration strategies to that of RoboDoc. These include a system for total knee arthroplasty developed by Kienzle, et al. at Northwestern University [3], the most recent system for total knee arthroplasty by Fadda, et al. [4] at Rizzoli Institutes, and a system for femoral osteotomies by Moctezuma, et al. [5] at the Institute for Machine Tools and Industrial Management in Münich.

3.2 Grenoble Pedicle Screw Placement System with Optotrak



Figure 4.  Registration graph     
of Grenoble pedicle screw            
placement system with Optotrak.

Lavallée et al. [6] at Grenoble University Hospital in La Tronche, France have developed a CAS system for placement of screws into the pedicle of the vertebra. In this surgery, a pilot hole must be accurately drilled along the axis of the pedicle, without breaching the walls of the pedicle or penetrating the anterior cortex of the vertebra body.

A notable feature of this system is that registration is maintained despite patient motion during surgery, and therefore no patient fixation is required. Construction of the registration graph makes this feature apparent. Referring to Figure 4,

A CT scan is used for preoperative diagnostic imaging. A computer displays a 3D reconstruction of the vertebra acquired from CT images, and a desired drill trajectory (the plan) is created through the pedicle in the image. An induced link is thus formed between plan and vertebra.
Intraoperatively, a rigid-body "flag", instrumented with six infra-red LEDs, is attached to the spinous process of the vertebra. The motion of this flag is tracked by an opto-electronic spatial digitizer (Optotrak^TM).
A pointing probe, with a similar array of LEDs, is used to digitize points from the surface of the vertebra. While the probe contacts the surface of the vertebra, a [probe : vertebra] transient link exists. This creates a [flag : vertebra] induced link. (It is worth noting that a 3D-3D matching algorithm was developed to correlate the digitized points from the Optotrak to the CT image of the vertebra. The difficulty of this matching operation is not acknowledged by the registration graph.)
A hand-held surgical drill, outfitted with six LEDs, is tracked by the Optotrak while the surgeon orients the drill to the desired trajectory, by aligning a set of cursors on a nearby computer monitor.

The subgraph [plan : vertebra : vertebral flag : Optotrak : tool] which establishes sustained connectivity does not include any induced links between motion groups (which would signal a need for fixturing.) Thus the graph shows that the patient need not be fixtured.

The graph does not have control connectivity, because there is no active positioning device. It would be possible to include the "computer-controlled surgeon" used here into the registration graph, but we have not done so here.

Nolte, et al., [7] at the University of Bern in Switzerland have developed a system for pedicle screw placement with an identical registration graph to that of Lavallée et al.

3.3 Long Beach Stereotactic Neurosurgery System

The robotic stereotactic neurosurgery system used by Kwoh, et al. [8] at the Memorial Medical Center of Long Beach was one of the first CAS systems developed. The registration graph of this system is typical of systems that use stereotactic frames, such as Glauser et al. [9], Drake et al., [10]. Referring to Figure 5,


Figure 5.  Registration graph of      
the Long Beach stereotactic             
neurosurgery system.

A CT image is obtained of the patient's head, showing also the fiducial markers on a removable headframe that the patient wears. A plan (a syringe trajectory that reaches the biopsy site in the brain safely) is created in the voxel data from the CT, and thus an induced link is shown from brain to plan.
An induced link is also formed from brain to fiducial markers. Recall that induced links require immobilization, which is provided here by fixating the headframe to the skull.
Later, mounting clips on the headframe are locked to brackets attached to the robot base. This constitutes a sustained `coincidence' link.
The induced links [fiducial markers : mounting clips] and [robot : brackets], were apparently established earlier by CMM, although one could imagine doing it differently by touching the tool to the fiducial markers (which would result in a different registration graph, of course.)

The subgraph [plan : brain : fiducial markers: clips : bracket : robot : tool] establishes sustained connectivity, but involves two fixtures: one to maintain the induced link from headframe to patient, and another corresponding to the sustained `coincidence' link between clips and bracket.



Figure 6.  Registration graph of      
the Northwestern pedicle screw           
placement system.                        


Figure 7.  Registration graph of      
the Grenoble pedicle screw placement     
system which uses a robot and a          
fluoroscope.

3.4 Northwestern Pedicle Screw Placement System

Santos-Munné et al. [11] at Northwestern University describe a system for pedicle screw placement. Its philosophy is to stay as close to conventional practice as possible, while achieving greater accuracy through the use of a robot for drill guidance. As in conventional practice, planning is done in three parts, corresponding to three orthographic projections. Referring to Figure 6,

The robot's end-effector consists of a drill guide, an array of fiducial spheres, and a mounting flange. Induced links between the components were created by CMM.
A preoperative CT image is used to create the transverse plan.
Intraoperatively an A/P fluoroscopic image of the vertebra and the array of fiducial spheres on the end-effector, which is held close to the patient. The image is used to create the A/P projection of the plan. A sagittal fluoroscopic image is used similarly.
An induced link is established between the vertebra and the robot, via the connected subgraph [vertebra : fluoroscope : fiducial spheres : flange : robot].

The subgraph [vertebra : robot : flange : tool] establishes sustained connectivity. However, the [vertebra : robot] induced link requires immobilization.

3.5 Grenoble Pedicle Screw Placement System with Robot and Fluoroscope

An earlier system developed at Grenoble by Troccaz et al. [12] for pedicle screw placement uses the same instrumentation as the Northwestern pedicle screw placement system. However, the procedures are different, and therefore the registration graph is different. Referring to Figure 7,

Drill trajectory planning is done on a 3D reconstruction of the vertebra obtained from CT. Therefore, an induced link exists between plan and vertebra.
A reference grid held by the robot is imaged by the fluoroscope, establishing an induced link [fluoroscope : robot]. This induced link must be maintained by fixturing robot to fluoroscope.
A fluoroscopic image of the vertebra is acquired. Together with the [fluoroscope : robot] induced link, a connected subgraph is created which induces a [vertebra : robot] link.
The reference grid is removed from the robot and replaced with a laser. The surgeon uses the laser beam as a guide for drilling.

The subgraph [plan : vertebra : robot : laser] establishes sustained connectivity. The [vertebra : robot] induced link requires fixation during surgery. The [fluoroscope : robot] induced link is not involved in the subgraph. It was only used to establish the [vertebra : robot] link, and may be broken thereafter.

A like registration strategy has been used in other systems developed by the Grenoble group, notably a system for stereotactic neurosurgery by Lavallée et al. [13].

3.6 Imperial College Keyhole Surgery



Figure 8.  Registration graph of     
the Imperial College keyhole surgery    
system.

A system for percutaneous biopsies (of, for example, the kidney) has been developed by Potamianos, et al. [14] at Imperial College in London. This system displays a computer-generated image of a biopsy needle superimposed on static fluoroscopic images of the patient, as the real needle is manually moved about.

The registration graph (figure 8) is notable in that there is no preoperative plan.

A fluoroscope image of the biopsy site is acquired.
A probe on the passive manipulator's end effector is placed into contact with a sterile attachment on the fluoroscope. This induces a link between the manipulator and the biopsy site.

The subgraph [biopsy site : manipulator : needle] establishes sustained connectivity. The [manipulator: biopsy site] induced link must be maintained by immobilizing the patient.

Conclusion

Connectivity properties of registration graphs are useful in the study of registration pathways and immobilization requirements of CAS systems. They can also be used as a diagrammatic technique for explaining CAS registration strategies and procedures. Several caveats should be observed:

The relative technical difficulty of operations represented by the graphs is obscured.
The graphs do not address the accuracy of individual measurement operations.
At the level of detail shown here, the graphs do not distinguish measurement operations of full rank from those of reduced rank (fewer than six degrees of freedom).
We know of at least one other way of forming an induced link, besides closing a simultaneous connected subgraph around it. This will be addressed in a subsequent report.
Systems graphed here are represented to the best of our knowledge and inference of their actual procedures. In some cases we have had to presume that, for instance, a measurement is established by CMM, when it may in fact have been established some other way.

Acknowledgments

The authors would like to acknowledge Dr. Thomas Kienzle of Mt. Sinai Hospital in Cleveland, and Dr. S. David Stulberg and Dr. Srdjan Mirkovic of Northwestern Memorial Hospital, who make up our medical contingent. This work was supported by grants from the National Science Foundation and the Whitaker Foundation.

References

[1] H. A. Paul, et al., "A Surgical Robot for Total Hip Replacement Surgery"; Proceedings, IEEE International Conference on Robotics and Automation, vol. 1, pp 606-611, Nice, France, 1992.

[2] R.P. Paul; Robot Manipulators: Mathematics, Programming and Control; MIT Press, Cambridge, MA, 1981.

[3] T.C. Kienzle, S.D. Stulberg, M. Peshkin, A. Quaid, C-H. Wu; "An Integrated CAD-Robotics System for Total Knee Replacement Surgery", Proceedings, IEEE International Conference on Robotics and Automation, vol. 1, pp. 889-894, Atlanta, GA, 1993.

[4] M. Fadda, et al.; "Computer-Assisted Knee Arthroplasty at Rizzoli Institutes"; Proceedings, First International Symposium on Medical Robotics and Computer Assisted Surgery, Vol. 1, pg. 26-30, Pittsburgh, PA, 1994.

[5] J.L. Moctezuma, F. Gosse, H.J. Schultz; "A Computer and Robotic aided Surgery System for Accomplishing Osteotomies"; Proceedings, First International Symposium on Medical Robotics and Computer Assisted Surgery, Vol. 1, pg. 31-35, Pittsburgh, PA, 1994.

[6] S. Lavallée, P. Sautot, J. Troccaz, P. Cinquin, P. Merloz; "Computer Assisted Spine Surgery: A Technique for Accurate Transpedicular Screw Fixation Using CT Data and a 3D Optical Localizer"; Proceedings, First International Symposium on Medical Robotics and Computer Assisted Surgery, Vol. 2, pg. 315-322, Pittsburgh, PA, 1994.

[7] L.P. Nolte, L.J. Zamorano, Z. Jiang, Q. Wang, F. Langlotz, E. Arm, H. Visarius; "A Novel Approach to Computer Assisted Spine Surgery"; Proceedings, First International Symposium on Medical Robotics and Computer Assisted Surgery, Vol. 2, pg. 323-328, Pittsburgh, PA, 1994.

[8] Y.S. Kwoh, I.S. Reed, J.Y. Chen, H.M. Shao, T.K. Truong, E. Jonckheere; "A new computerized tomographic-aided robotic stereotaxis system"; Robotics Age, pp. 17-22, June 1985.

[9] D. Glauser, P. Flury, N. Villotte, C.W. Burckhardt; "Conception of a Robot Dedicated to Neurosurgical Operations"; Proceedings, 5th International Conference on Advanced Robotics, pp. 899-904, Pisa, Italy, 1991.

[10] J.M. Drake, M. Joy, A. Goldenberg, D. Kreindler; "Computer and Robotic Assisted Resection of Brain Tumors"; Proceedings, 5th International Conference on Advanced Robotics, pp. 888-892, Pisa, Italy, 1991.

[11] J.J. Santos-Munné, M.A. Peshkin, S. Mirkovic, S.D. Stulberg, T.C. Kienzle; "A Stereotactic/ Robotic System for Pedicle Screw Placement"; Proceedings, Medicine Meets Virtual Reality III, San Diego, 1995.

[12] J. Troccaz, S. Lavallée, P. Sautot, P. Cinquin, B. Mazier, J.P. Chirossel; "Robot Assisted Spine Surgery"; Medi-MECHATRONICS Workshop, Málaga, Spain, October 1992.

[13] S. Lavallée; "Image Guided Operating Robot: A Clinical Application in Stereotactic Neurosurgery"; Proceedings, IEEE International Conference on Robotics and Automation, pp. 618-624, Nice, France, 1992.

[14] P. Potamianos, B.L. Davies, R.D. Hibbert; "Intra-Operative Imaging Guidance for Keyhole Surgery"; Proceedings, First International Symposium on Medical Robotics and Computer Assisted Surgery, Vol. 1, pg. 98-105, Pittsburgh, PA, 1994.