Enhanced shape characterization device and method

[0001] Not applicable

[0002] Not applicable

[0003] Not applicable

[0004] 1. Field of the Invention

[0005] This invention relates to the determination of the shape of rigid or nearly rigid bodies. More particularly, this invention relates to shape determination of such bodies using a computer navigation system.

[0006] 2. Description of the Background of the Invention

[0007] Computer determination of the location of bodies has been used in manufacturing and medical fields for a number of years. Computer navigation requires that the bodies to be tracked by the navigation system have a known shape, so that the orientation and position of the bodies can be properly tracked by the system. Tracking is accomplished by either attaching a tracking device to the body or embedding the tracking device into the body. There are numerous tracking technologies including active and passive optical tracking systems, magnetic systems and inertial systems.

[0008] For many applications it is necessary to field calibrate bodies so that the navigation system can thereafter track the body and realistically render the body graphically on a computer display. Typically, this is done by attaching the tracking device in a fixed relation with the body and then inserting the body into a calibration device. These devices can be as simple as a divot in a known relation to the navigation system or can be a device that constrains the body in a predetermined attitude relative to the navigation system with the tip of the body located in a predetermined position. Current tracking calibration requires some physical contact between the body and a calibration device.

[0009] For certain situations, it may be desirable to minimize contact with other devices or bodies. For instance in a surgical setting, sterility requirements require that the body to be used be sterile and that every body it contacts in any way also be sterile. This necessitates sterilizing the calibration device and maintaining the calibration device within the sterile field. With space at a premium in a surgical suite, this can be a problem.

[0010] In addition, bodies that include attachments, such as screwdrivers, drills, implant insertion devices, etc., need to be recalibrated each time a new attachment is inserted. Lastly, some devices do not have an axial shape with the result that these bodies have been difficult to field calibrate using known methods.

[0011] According to one aspect of the invention, a system determines the shape and orientation of a body relative to a tracking device. A sensing device generates a series of representation of the body. A tracking device capable of being detected by a computer navigation system is associated with the body such that the position of the body is located relative to the computer navigation system. The computer navigation system having a central processing unit processes the series of representations of the body and the relative location of the body in order to determine the shape and orientation of the body relative to the tracking device.

[0012] In accordance with another aspect of the invention, the shape and orientation of a body relative to an emitter are determined by a system. A sensing device generates a series of representation of the body. An emitter capable of being detected by a computer navigation system is associated with the body such that the position of the body is located relative to the computer navigation system. The computer navigation system having a central processing unit processes the series of representations of the body and the relative location of the body in order to determine the shape and orientation of the body relative to the emitter.

[0013] In accordance with a further aspect of the invention, a method to determine the shape and orientation of a body relative to a tracking device using a computer navigation system includes the step of generating a series of representation of the body and thereafter using these representations to determine a composite bounding volume of the body. The shape of the body is determined using the composite bounding volume. A position and an orientation of the body is determined using a tracking device associated with the body that communicates with the computer navigation system.

[0014] In yet a further aspect of the invention, a method to determine the shape and orientation of a body using a computer navigation system includes the step of generating a series of representations of the body from at least two perspectives. A composite bounding volume is determined from the series of representations and the shape of the body is determined from the composite bounding volume. The position and orientation of the body are determined from the shape of the body and the series of representations of the body.

[0031] FIG. 1 shows one embodiment of a shape characterization system 100 useful to characterize a body 102, that includes a navigation computer 104, a position tracking device 106, a plurality of cameras 108-1 through 108-M, and a plurality of backgrounds 110-1 through 110-N. The shape characterization system 100 locates the position and orientation of the body 102 in space with respect to a global coordinate system 112 established by the navigation computer 104. Specifically, the shape characterization system determines the position and orientation of body axes X_B 114, Y_B 116, and Z_B 118 that are local to the body 102 with respect to the global coordinate system 112 established by the navigation computer 104. The position and orientation of the body axes 114, 116, and 118 determined by the shape characterization system 100 can be expressed as a linear transformation matrix that maps points on the body 102 in the local coordinate space defined by the body axes 114, 116, and 118 to points in the global coordinate system 112.

[0032] The position tracking device 106 has a local coordinate system 120, and each of the cameras 108-1 through 108-M have their own local coordinate systems 122-1 through 122-M. Suitable devices for use as the cameras 108-1 through 108-M include known digital video cameras, digital still cameras, image capture devices and the like.

[0033] The position tracking device 106 has a predetermined and fixed relationship to the body 102 and is calibrated to the computer navigation system 104. Furthermore, the position tracking device 106 is capable of tracking the position of a fixed point 124 on the surface of the body 102 with respect to either the coordinate system 120 of the position tracking device 106 or with respect to the coordinate system 112 of the navigation computer 104 because the two coordinate systems are calibrated to one another. The calibration of the two coordinate systems enables any measurements of the point 124 on the body 102 with respect to the coordinate system 120 of the position tracking device 106 to be mapped to the coordinate system 112 of the navigation computer 104 through a linear transformation.

[0034] The position tracking device 106 can be physically separate from the body 102, or alternatively, the position tracking device 106 can be attached to or otherwise incorporated into the body 102 and still provide the necessary position information. The point 124 can be located in a fixed position relative to the position tracking device 106 or can be determined by a calibration method described hereinafter. The point 124 can be the location of an emitter used by the position tracking device 106, as is discussed hereinafter.

[0035] The position tracking device 106 can be one of any of a number of position sensing devices known to those familiar with the art. FIG. 2a shows the use of an example of the position tracking device 200 that uses an optical position sensor 204. Tracking a body using the optical position sensor 204 entails placing an emitter 206 on the body 102, wherein the emitter 206 is an emissive light (visible or infrared) source. Also, multiple emitters 206 can be affixed to the body 102 in known configurations. The optical position sensor 206 uses a light sensor 208 tuned to detect the light emitted by the light source and track the emissive light source 206 as it moves with the body 102. A light emitting diode (LED) is a typical emissive light source 206 and a charge coupled device (CCD) is a typical light sensor 208. The FlashPoint system of Stryker Corporation (Kalamazoo, Mich.) is an example of the optical tracking system as shown in FIG. 2a.

[0036] FIG. 2b shows the use of another type of an optical position tracking device 210 that makes use of another type of optical position sensor 212. Tracking a body with this alternate optical position tracking device 210 entails affixing a reflective body (e.g., a retro-reflector) 214 on the body 102. An emissive light source 216 is aligned with the reflective body 214 such that a beam of light 218 generated by the emissive light source 216 reflects off the reflective body 214 in such a manner that a light sensor 220 in the optical position sensor 212 may thereafter detect it and thus track the position of the reflective body 214 as it moves with the body 102. The Motus system by Peak Performance Technologies, Inc. (Englewood, Colo.) is a manufacturer of position measurement devices as shown in FIG. 2b.

[0037] FIG. 2c shows the use of a position tracking device 224 that uses magnets 226 affixed to the body 102. The changes in the direction and amplitude of magnetic flux of the magnets 226 as the magnets 226 move with the body 102 are sensed by the magnetic position sensor 228 and used to determine the position of the magnets 226. Examples of manufactures of this type of tracking technology are Polhemus Incorporated of Colchester, Vt., and Ascension Technology Corporation of Burlington, Vt.

[0038] Although only one point 124 is depicted as being tracked on the surface of the body 102 to simplify the description, it should be evident that multiple tracking points may be tracked on the same body 102, each with a separate position-tracking device. In fact, multiple tracking points may be necessary to determine the full rotational orientation of the body 102. Multiple bodies 102 can also be tracked at the same time by a single system.

[0039] Referring once again to FIG. 1, the shape characterization system identifies the orientation of the axes X_B, Y_B, and Z_B of the body 102 denoted as items numbered 114, 116, and 118, respectively, with respect to the global coordinate system 112 by estimating a bounding volume of the body 102 and determining the axes of the bounding volume. Specifically, an axis of interest 114, 116, or 118 of the body 102 can be determined through an analysis of the estimated bounding volume. It follows that the remaining axes are normal to the determined axis and to one another. If necessary, the orientation of the remaining axis may be determined more precisely by analyzing the position information provided by the tracking device and the estimated bounding volume. One point 124 of particular interest is a tip 126 of the body 102. The tip 126 can be located coaxially with the axis of interest (for example, the body axis X_B 114) or located at some other point not on the axis of interest.

[0040] The plurality of cameras 108-1 through 108-M positioned around the body capture images of the body from different perspectives. These cameras 108-1 through 108-M may be either fixed image cameras or video cameras, or some combination of the two camera technologies. If video cameras are used then individual frames of the video captured by the video camera are processed as single images. Preferably, all of the cameras capture frames nearly synchronously in time so that images from multiple view points are correlated. The positions and coordinate systems 122-1 through 122-M of the cameras 108-1 and 108-M are calibrated to one another and to the global coordinate system 112 established by the navigation computer 104. One embodiment of the method of calibration of the cameras is described herein below. In the preferred embodiment the cameras 108-1 through 108-M are standard video cameras with frame capture hardware in desktop personal computers or Firewire and USB based cameras that are well known in the art.

[0041] Fixed backgrounds 110-1 through 110-N preferably are positioned around the body opposite the cameras. These backgrounds 110-1 through 110-N provide a known surround in an image captured by the cameras 108-1 through 108-M that aids in identifying the edges of the body 102 in the image. The backgrounds 110-1 through 110-M may be neutral, black, white, or any color that would increase the contrast between the portion of the image that represents the background 110-1 through 110-M and the portion of the image that represents the body 102. Further, the backgrounds may be backlit to further increase this contrast. It is possible to perform one embodiment of the method of the present invention without fixed backgrounds. However, this is not preferred because of the increased complexity of the shape determination from having to subtract the background image from the image of the body 102.

[0042] The navigation computer 104 processes the images captured by the cameras 108-1 through 108-M. The navigation computer 104 may make use of a body database 130 populated with shape information regarding typical bodies that the navigation computer 104 may have to identify. The shape information of a body in the body database 130 is preferably coordinates of vertex points of the body as are typically be available from a computer aided design system. The navigation computer 104 develops one or more comparison metrics by comparing the bounding volume estimated from processing the images from the cameras 108-1 through 108-M to the shape information that is stored in the body database 130. If the shape information for one of the bodies in the body database 130 is found to be highly correlated with the estimated bounding volume, the navigation computer may use the shape information for the body to refine the estimated bounding volume. For example, the navigation computer may develop a comparison metric by analyzing the distances between each vertex of the estimated bounding volume and a corresponding vertex stored as part of the shape information for a body in the body database 130. An example of another comparison metric that may be developed is the result of analyzing the properties of the inertia moment axes of the estimated bounding volume with the inertia moment axes of a body in the body database 130. Additional comparison metrics are known to those familiar with the art. A preferred embodiment uses a plurality of comparison metrics to determine the degree of correlation between the estimated bounding volume and a body stored in the body database 130.

[0043] It is not necessary for the cameras 108-1 through 108-M to image the entire body. Only the portion of the body 102 that is of interest needs to be imaged by the cameras 108-1 through 108-M. Furthermore, the body 102 and the cameras 108-1 through 108-M are preferably positioned with respect to one another so that the field of view of each camera captures approximately the same parts of the body.

[0044] FIG. 3 depicts a flow chart 300 of the steps used to estimate the bounding volume from the captured images. Each image 302-1 through 302-M captured by a camera 108-1 through 108-M respectively, is first rectified by blocks 304-1 through 304-M. That is, the image is corrected for any known irregularities in the lens, normalized for the known focal length of the lens being used, adjusted for resolution of the camera, etc. Blocks 306-1 through 306-M process the rectified image generated by blocks 304-1 through 304-M to isolate the representation of the body from the representation of the background in the image. Blocks 308-1 through 308-M perform an edge detection operation on the image of the isolated body generated by blocks 306-1 through 306-M. Blocks 310-1 through 310-M use the edge information generated by blocks 308-1 through 308-M to estimate a general bounding pyramid with K_j faces for the body, where 1<=j<=M. The bounding pyramids calculated in this manner from each of the images 301-1 through 301-M captured by the cameras are normalized by a block 312 based on the time of capture of that image and the location of the camera as provided by blocks 314-1 through 314-M. Blocks 314-1 through 314-M further intersect all of the bounding pyramids with one another to a bounding volume of the body. A block 316 combines the estimated bounding volume with the location of the body from the position tracking device as provided by the block 318 to estimate the position and orientation of the body. If the body database 130 is available to the navigation computer, block 316 compares the bounding volume to the shape information for all of the bodies contained therein. If a body in the body database 130 is found that has dimensions and shape that is within a predetermined tolerance with respect to the bounding volume, then the navigation computer uses the shape information for the body in the body database to refine the estimate of the bounding volume. In the preferred embodiment, the cameras 108 capture images of the body 102 continuously (or as rapidly as the cameras can) and, as the body 102 is rotated, bounding pyramids from these additional images are intersected with a previously calculated bounding volume to refine the estimated bounding volume and the estimated orientation of the body 102.

[0045] FIG. 4 shows an example of an initial estimate of a bounding volume 400 of the body 102 generated by using three cameras 108-1, 108-2, and 108-3. The bounding volume of the body 102 can be determined by any of a number of well known methods available for making this determination. Depending on the number of cameras 108-1 through 108-M or views from a single camera 108-1, as discussed hereinafter, the intersection of the combined bounding volumes begins to approximate the shape of the body 102.

[0046] FIG. 5 shows another embodiment of the shape characterization system 500 wherein one camera 108 is used to capture a plurality of images of the body 102 as the body 102 rotates and moves through space, for example, along a path denoted by arrow R 502. The blocks 304 through 318 of FIG. 3 can process all of the images captured by the camera 108 of the body 102 as if a different camera captured each image from a different viewpoint relative to the body 102.

[0047] FIG. 6 shows yet another embodiment of the shape characterization system 600 wherein the camera 108 simultaneously captures an image of the body 102 and of the reflection of the body 102 in a mirror 602. In this embodiment, the navigation computer 104 processes the image captured by the camera 108 to divide the image into two images wherein one image contains the image of the body 102 and the other image contains the image of the reflection of the body 102 in the mirror 602. In effect, the mirror 602 acts as a second, albeit virtual, camera. As such, the blocks 302 through 318 of the flowchart 300 depicted in FIG. 3 act upon the image of the reflection of the body 102 in the mirror 602 as if the image had been captured by separate camera. In a similar manner, more than one mirror 602 could be employed.

[0048] An embodiment to calibrate the coordinate systems 122-1 through 122-M of the cameras 108-1 through 108-M of the shape characterization system 100 with respect to each other and with respect to the coordinate system 112 of the computer navigation system is through the use of a calibration body with an exactly known shape. FIG. 7 shows an example of such a calibration body 700. FIG. 7a shows a front view 702 of the calibration body 700. FIG. 7b shows a side view 704 of the calibration body 700. FIG. 7c shows a top view of the calibration body 706.

[0049] FIG. 8 depicts a flowchart 800 of the steps required to calibrate the cameras. Blocks 804-1 through 804-M rectify, isolate the body and identify edges of images 802-1 through 802-M from each of the cameras, wherein each image 802-1 through 802-M is an image of known perspective (e.g., front 702, side 704, and top 706) views of the calibration body 700. Blocks 806-1 through 806-M estimate position and orientation of each camera 108 and apply corrections based on the position and orientation estimate to the edges generated by blocks 804-1 through 804-M. A block 808 compares the edges as corrected by blocks 806-1 through 806-M with the known edge information of perspectives of the calibration body. If the corrected edges are within a predetermined tolerance of the known edges, then the cameras are said to have been calibrated and the position and orientation information generated by the block 806 is useable by the navigation computer 104. If the corrected edges are outside of the predetermined tolerance of the known edges, then the difference between the corrected edges and the known edges is calculated by a block 810 and provided to the block 806 to refine the guess of the position and orientation of each camera. The blocks 806, 808, and 810 are repeated until all of the cameras 108 are calibrated.

[0050] FIG. 9 shows another embodiment of the shape characterization system 900. Instead of using cameras 108-1 through 108-M to capture images of the body 102 against a background 110-1 through 110-N, this embodiment uses light sources 902-1 through 902-M positioned with respect to sensors 904-1 through 904-N. The positions of the light sources 902-1 through 902-M and the sensors 904-1 through 904-N are in a predetermined fixed relation to each other and known to the navigation computer 104. Alternately, the navigation computer 104 tracks the positions of all of the light sources 902-1 through 902-M and all of the sensors 904-1 through 904-N and can transform information from the sensors to be equivalent to information derived for a system wherein the position of the light sources 902-1 through 902-M is in a fixed relation to the position of the sensors 940-1 through 904-N. In addition, the navigation computer 104 tracks changes in the position of either the light sources 902-1 through 902-M or the sensors 904-1 through 904-N. Furthermore, the light sources 902-1 through 902-M and the sensors 904-1 through 904-N are positioned with respect to one another and the body 102 such that the body 102 occludes the light from each of the light sources 902-1 through 902-M and causes a shadow to be cast upon one of the sensors 904-1 through 904-N that is collinear with the light source 902-1 through 902-M and the body 102. The sensors 904-1 through 904-N are 2-dimensional sensing devices that are able to distinguish the regions that are in the shadow 906-1 through 906-N of the body 102 from those regions that are not. Each of the sensors 904-1 through 904-N provide information regarding the regions that are in shadow 906-1 through 906-N to the navigation computer 104. Only the shadows 906-1 through 906-N of the portion of the body 102 that is of interest needs to fall upon the sensors 904-1 through 904-N. A preferred sensor type is a 2-dimensional charge coupled device (CCD) array. Such a CCD array typically produces an image that is comprised of pixels wherein each pixel corresponds to one CCD element of the 2-dimensional array.

[0051] FIG. 10 depicts a flow chart 925 of the steps used to estimate the bounding volume from the images generated by the sensors 904-1 through 904-N. Each image 926-1 through 926-N from each of the sensors 904-1 through 904-N is first rectified by blocks 928-1 through 928-N. That is blocks 928-1 through 928-N correct the image for any known irregularities in the sensor, adjusts the shadow information for the resolution of the sensor, etc. Blocks 930-1 through 930-N process the rectified images generated by blocks 928-1 through 928-N to isolate the portions of the images that represent the shadow cast. Blocks 932-1 through 932-N perform an edge detection operation on the images of the isolated shadow generated by blocks 930-1 through 930-N. Blocks 934-1 through 934-N use the edge information generated by block 932-1 through 932-N to estimate a general bounding pyramid with N faces for the body. The bounding pyramids calculated in this manner from the each of the images 926-1 through 926-N generated by the sensors are normalized by a block 936 based on the time of capture of that image and the location of the camera as provided by blocks 938-1 through 938-N. The block 936 further intersects all of the bounding pyramids with one another to a estimate bounding volume of the body. A block 940 combines the estimated bounding volume with the location of the body from the position tracking device as provided by the block 942 to estimate the position and orientation of the body. Block 940 uses shape information from the body database if it is available. Specifically, if a body in the body database 130 is found that has dimensions and shape that is within a predetermined tolerance with respect to the bounding volume, then the navigation computer 104 will use the shape information for the body in the body database to refine the estimate of the bounding volume. In the preferred embodiment, the sensors 904-1 through 904-N generate representations of the shadow 906-1 through 906-N of the body 102 continuously (or as rapidly as the sensors can) and, as the body 102 is rotated, bounding pyramids from these additional representations are intersected with a previously calculated bounding volume to refine the estimated bounding volume and the estimated orientation of the body 102.

[0052] FIG. 11 shows another embodiment of the shape characterization system 950 wherein one sensor 904 is used to generate a plurality images with representations of a shadow 906 of the body 102 as the body 102 moves through space while being illuminated by one light source 902, for example, along a path denoted by arrow R 502. The blocks 928 through 940 of FIG. 10 can process all of the images generated by the sensor 904 of the body 102 as if a different sensor generated each image.

[0053] The shadow sensing devices can be calibrated using a body of known shape and dimension. A representative body 700 that can be used for calibration is depicted in FIG. 7a and the use of this body for calibrating the shadow sensing devices is the same as the process to calibrate the cameras described hereinabove except images from the shadow sensing devices 906-1 through 906-N are used instead of images from cameras 108.

[0054] The algorithms used to estimate the shape of the body 102 can be any of those well known and used in the field of computer graphics. Such algorithms are described in publications used in the field such as Computer Graphics: Principles and Practice, by James D. Foley, et al (Addison-Wesley, 1990), which is incorporated herein by reference. From the shape of the body 102 determined, the system can then determine the location of the tip 126.

[0055] If at least two sensing devices (either cameras 108 or shadow sensing devices 904) are used then the emitter 124 and the position tracking device 106 are not necessary, because the image of the body (or the shadow of the body) for one of the multiple devices provides information about the relative position of the body 102 with respect to the other devices. This information can be used to deduce the position of the body 102 with respect to the coordinate system 112 of the navigation computer 104 by, for example, stereographically determining multiple homologous point pairs in at least two camera views of the body 102. This is because the position of the sensing devices (either 108 or 904) with respect to the coordinate system 112 of the navigation computer 104 is known and tracked during the operation of the shape characterization system and linear transformation can be used to map between the coordinate systems of the sensing devices 108 or 904 and the navigation computer 104.

[0056] In addition, to further enhance the reality of the body 102 as it is displayed on a display monitor, coloration and or texture can also optionally be created by known methods. In this case, one or more light sources 128 optionally can be simulated to shade the rendered view of the body 102 on a computer graphics screen.