 |
Description  |
|
|
BACKGROUND OF THE INVENTION
The present invention is generally directed to a system and method for
displaying surface information. More particularly, the present invention
incorporates non-linear interpolation to remove certain image artifacts.
The images of the surfaces displayed are typically contained within the
interior regions of solid bodies which are examined by computed axial
tomographic (CAT) x-ray systems or by nuclear magnetic resonance (NMR)
imaging systems either of which is capable of generating three dimensional
arrays of data representative of one or more physical properties at
various locations within a three dimensional volume. The present invention
is especially directed to a system and method for the display of medical
images so as to obtain images and representations of internal bodily
structures. The images generated in the practice of the present invention
provide three dimensional data for examination by physicians,
radiologists, and other medical practitioners. The present application has
been filed concurrently with application Ser. No. 741,390.
In conventional x-ray systems, a two dimensional shadow image is created
based upon the different x-ray absorption characteristics of bone and soft
tissues. A great improvement on the conventional x-ray system as a
diagnostic tool was provided by the computed axial tomographic systems
which have been developed over the last ten years or so. These so-called
CAT systems are x-ray based and initially were used to produce single two
dimensional views depicting transverse slices of a body, object, or
patient being investigated. Three dimensional information was thereafter
gleaned from CAT scan data by generating data for a number of contiguous
slices and using the inferential abilities of the radiologist to suggest a
three dimensional representation for the various internal organs. In one
embodiment of the present invention, shaded and contoured three
dimensional images are generated from the three dimensional array of data
generated by a sequence of such contiguous CAT scans. However, resolution
in the z-direction, perpendicular to each slice, is usually lower than the
resolution within a slice. This can produce undesirable artifacts which
are significantly reduced in the present invention. Similarly, the newer
NMR imaging technology is also capable of generating three dimensional
arrays of data representing physical properties of interior bodily organs.
Moreover, NMR systems have the capability to better discriminate between
various tissue types, not just bone and soft tissue. NMR imaging systems
are also capable of generating physiological data rather than just image
data. However, whether NMR or CAT systems are employed, the data has been
made available only as a sequence of slices and systems have not generally
been available which provide true three dimensional images.
In the present invention, three dimensional data generated either by a CAT
scanning system or by an NMR imaging system may be displayed and analyzed
in a plurality of ways so as to produce on a display screen or other
device a multitude of anatomical features which are selectable at the
viewer's choice. In the system and method of the present invention, the
data used to produce the three dimensional images is typically acquired
once and then used and re-used to generate medical information and display
images at the option of the viewer. The viewer is provided with the option
of selecting one or more threshhold values which determine, for example,
whether or not bone surfaces as opposed to brain surface tissue is to be
displayed. The viewer or operator of the present system can also select
the appropriate viewing angle and can, at will, selectively ignore
segments of the data generated in order to provide cross sectional views
through any desired plane. Moreover, the viewing angle is selectable and
it is possible to generate a sequence of images and display them
sequentially to provide the medical practitioner with interior views of
solid surfaces in a truly three dimensional manner from any desired
viewing angle with the further capability of being able to construct a
view through any plane or slice. Again, it is pointed out that for many
purposes, an almost infinite variety of meaningful images may be created
from only a single set of NMR or CAT scan slice data arrays. Certainly
though, if the objective of the medical investigation is the study of
internal anatomic variations as a function of time, then it is meaningful
to produce a sequence of three dimensional data arrays indexed by time.
The system and method of the present invention provide the medical
practitioner, and surgeons in particular, with the ability to plan
detailed and complicated surgical procedures using totally non-invasive
diagnostic methods. The images generated by the present invention can only
be described as truly dramatic and show every evidence of being as great
an improvement in the medical imaging arts as computed axial tomography
and nuclear magnetic resonance imaging.
While the system and method of the present invention will undoubtedly find
its greatest utilization in the analysis and display of tomographic x-ray
and nuclear magnetic resonance imaging data, the system of the present
invention is equally applicable to systems employing ultrasound, positron
emission tomography, ECT (emission computed tomography) and MMI
(multimodality imaging). Moreover, while the present invention is
particularly applicable to the construction of medical images, it is also
pointed out that the system and method of the present invention is
applicable to the display of interior three dimensional surface structures
for any system which is capable of generating three dimensional data
arrays in which signal patterns are present which represent the value of
at least one physical property associated with points in a solid body.
A particular advantage of the present invention is its ability to provide
the medical practitioner with the ability to perform interactive functions
with the machine in real time. Systems which do not permit interactive use
suffer a significant disadvantage since a real time display methodology is
required for optimal human interaction with the system, particularly in
the case of a surgeon planning a difficult procedure. For example, in
transplant surgery, it is often difficult to ascertain beforehand the
precise shape or size of a body cavity which is to receive the implant.
This is true whether or not the implant comprises human tissue or a
mechanical device. It is therefore seen that it would be very important
for a surgeon to be able to display the cavity in question on a screen in
three dimensional form and be able to rotate it and section it at will,
before any invasive procedure is undertaken. It is also important to such
medical practitioners that the images generated are sharp and exhibit
excellent contrast. The images generated should also depict surface
texture wherever this is possible.
The display of three dimensional graphic images on a cathode ray tube (CRT)
screen has principally been driven by the goals and directions of computer
aided design (CAD) and computer aided manufacture (CAM). Systems have been
developed for displaying solid bodies and for manipulating images in
desirable fashions to create solid models for manufactured parts and for
rotating and viewing these parts from a multiplicity of directions. In
particular, CAD/CAM systems have been developed which accept so called
wire-frame data. In a wire-frame display format, the display processor is
provided with a sequence or list of three dimensional points
representative of the end points of line segments. These line segments are
joined to represent various surfaces. An advantage of these wire frame
images is the ability to rapidly rotate the image about various axes to
obtain different views. This is actually a computationally burdensome task
which has only recently been satisfactorily solved through the utilization
of high speed, large scale integrated circuit devices. A wire-frame image,
even one which has been processed to eliminate hidden lines, may typically
comprise a list of 50,000 vectors which is displayed on a screen, each
"vector" being a (directed) line segment drawn between two points by a CRT
form of display device. More sophisticated graphics processing systems not
only accept wire-frame data, but also perform functions such as hidden
line removal and continuous shading in various colors and/or in various
shades of gray. In such systems, the viewing angle is selected by the
operator. In systems displaying shaded images, the normal vector to the
surface being displayed varies from point to point on the surface and the
shading is determined from this normal vector and the viewing angle. Thus,
it is seen that the information provided by the normal vector is very
important in the shading which is applied to what is in actuality a two
dimensional CRT screen image. It is the shading of this image (based
originally on wire-frame data) that creates a very effective illusion of
three dimensions. It is the providing of these three dimensional clues
(shading) to the human visual system which is achieved particularly well
in the system of the present invention. The shading data is generally
produced from wire-frame data in various graphics processing systems which
operate to convert the vector format of wireframe images to the so-called
raster scan format. It is the raster scan format that is most familiar to
the television viewer. In general, computer graphics display systems and
display methodologies are divided into vector based systems which are
particularly appropriate for line type drawings and raster format systems
which produce images which are more closely related to that which is seen
by the human eye.
Related work in the field of displaying three dimensional images has been
carried out by Gabor Herman who has employed a method in which each
adjacent volume element is analyzed and quantized to discrete zero and one
values. Surface approximations are made only by considering cube faces and
surface normal information can only be partially reconstructed because of
the quantization step that is performed. The resulting method also is
computationally long and produces low resolution images and appears be
slower than the present method for interactive use at this time.
Meagher, working for Phoenix Data Systems, has employed a method of octree
coding in which the three dimensional data array is subdivided into eight
regions and each region is subdivided until individual volume elements are
formed. Regions not containing surfaces are not subdivided. However, this
method requires special purpose hardware, while the images are crisp,
individual volume elements produce a quantized artifact that is not
observed in smooth tissues such as bone. Furthermore, octree encoding
methods are incompatible with polygonal surface descriptions which are
used in most of the advanced graphics display systems that have been
developed for CAD/CAM technology. Other methods for displaying three
dimensional data are, for example, described in U.S. Pat. No. 4,475,104
issued Oct. 2, 1984 in the name of Tsu Y. Shen. This patent appears to
disclose a three dimensional display system which incorporates a depth
buffer to provide separate 3D information as part of the mechanism for
generating appropriate shading values.
Accordingly, it is seen that it is an object of the present invention to
provide a system and method for the display of three dimensional
information.
It is a further object of the present invention to provide a display system
for use in conjunction with CAT scanners, ultrasound devices, NMR imaging
systems, and any and all other systems capable of generating three
dimensional data representative of one or more physical properties within
a body to be studied.
It is yet another object of the present invention to provide a graphics
system for medical images which is capable of interactive use and yet at
the same time produces high quality images providing textural, shading,
and other visual clues to the user.
It is yet another object of the present invention to provide a three
dimensional graphics display system which is compatible with current
CAD/CAM systems.
Another object of the present invention includes the ability to generate
and display three dimensional wire frame information.
Still another object of the present invention is to maximize the
information contained in a three dimensional data array for the purpose of
surface representation.
It is also an object of the present invention to provide a system and
method which is readily fabricatable in specialized electronic hardware
including integrated circuit chips and read only memory (ROM) devices.
It is yet another object of the present invention to provide medical
practitioners with the ability to emulate surgical procedures graphically
prior to undertaking invasive measures.
Additionally, it is an object of the present invention to provide a
plurality of three dimensional surface views from a single set of
collected data.
Lastly, but not limited hereto, it is an object of the present invention to
provide a system and method for display of three dimensional images of
internal surface structures in such a way that the specific viewing angle
and cross sectional viewing plane may be selected by the user in an
interactive manner.
SUMMARY OF THE INVENTION
In accordance with a preferred embodiment of the present invention, a
system for displaying three dimensional surface structures comprises means
for storing three dimensional signal patterns which represent the value of
at least one physical property which is associated with a three
dimensional body at rectangularly spaced grid locations within a body. The
system includes means for retrieving eight adjacent signal pattern values,
these values being located at cubically adjacent grid locations. As used
herein and in the appended claims, the term "cubically adjacent" refers to
grid locations which exist at the eight corners or vertices of a cube, or
more generally, a parallelopiped. The system also includes means for
comparing each of these eight cubically adjacent values with a
predetermined threshhold value or range of values so as to generate an
eight bit binary vector which is used herein as an addressing or
generation mechanism. The system also includes means for generating a set
of coordinate values for each of the distinct binary vectors generated.
These coordinate values represent the vertices of at least one
predetermined polygonal surface which approximates the intersection of
surfaces determined by the threshhold value with the volume defined by the
eight grid locations. In general, these coordinate values are also
selected to be dependent upon the location of the eight grid points within
the body. With particular reference to the present invention,
interpolation means are provided to adjust the coordinate values in a
non-linear fashion based on three or more data values obtained along a
grid line. A preferred embodiment of the present invention further
includes display processor means for receiving the coordinate values and
for converting these coordinate values to a particular display format. The
preferred embodiment also includes means for displaying surfaces
determined by the threshhold, the display means being driven by the
display processor.
In accordance with a preferred embodiment of the present invention, a
method for producing three dimensional surface representations on a
display device such as a CRT screen includes the steps of generating three
dimensional signal patterns in which the signal patterns represent the
values of at least one physical property associated with a three
dimensional body at regularly spaced grid points throughout the body.
These three dimensional signal patterns are employed to generate an eight
bit vector for each set of cubically adjacent locations throughout the
body. The vector is determined by comparison of data values representing
the physical property with a predetermined threshold value or range of
values. This eight bit vector is used to generate a set of coordinate
values for each of the 256 distinct eight bit vectors. The coordinate
values generated represent vertices of at least one predetermined
polygonal surface which approximates the intersection of surfaces
determined by the threshold value with the volume defined by the eight
grid locations. These coordinate values also depend upon the location of
the grid location within the body. With particular reference to the
present invention, a non-linear interpolative operation is performed to
adjust each coordinate value along a grid line based on three or more data
values obtained at adjacent grid points, that is, along a grid line. These
coordinate values are supplied to a display processor and display device
for a generation of three dimensional images of at least one surface
within the body, this surface being determined by the threshold value or
values.
In the display of three dimensional surface pictures, say for example, on a
CRT screen, it is very important to provide visual clues to the human eye
with respect to orientation of each part of the surface. These visual
clues are provided by shading the various triangular or polygonal surface
elements which are displayed. For example, the more closely the normal
direction to the surface is to the viewer's line of sight, the lighter is
the shading that is applied (at least for positive rather than negative
images). Surface segments which exhibit normal directions with components
directed away from the line of sight represent surface structures which
are not visible and therefore these normal directions provide a mechanism
for eliminating the surface element from the view for a particular viewing
angle. Surface elements having normal vectors with substantial components
in a direction orthonogal to the viewing direction are represented by more
darkly shaded surface elements. As used herein, the term "surface element"
refers to triangular, or more generally polygonal, surfaces, which are
used to tile or tesselate, the desired surface.
In the medical aspects of the present invention, a discriminating
threshhold value or range may be chosen so as to selectively view various
body structures. For example, if one wishes to view bony structures, a
particular threshhold value is chosen. However, if one wishes to view the
surface structures of softer tissue, a different threshhold value is
selected by the operator. In any event, the system for displaying such
three dimensional surface structures should include accurate means for
determining local surface normal directions, since it is these directions
which greatly enhance the ability of the viewer to recognize the shading
clues for a truly three dimensional representation.
One of the significant features of the present invention is the ability to
perform rapid generation of coordinate values representing polygonal and,
in particular, triangular surfaces. These polygonal surfaces approximate
the intersection of the desired surface with a three dimensional volume
element. The eight values defined at the eight vertices of a three
dimensional grid structure are employed to generate an eight bit vector.
This vector is employed as an address to rapidly generate the coordinate
values. In each voxel element (defined by the eight cubically adjacent
grid points), the object is to define a surface which separates included
from excluded vertices. In general, there are 256 cases which have to be
analyzed for surface intersection arrangements. However, a significant
observation of the present inventors has led to the conclusion that only
14 cases actually need to be constructed. The present inventors have
determined that by rotation about any of three mutually perpendicular axes
and by employing binary complementation methods, the 256 cases actually
reduce to a mere 14 cases which require separate manual analysis (one
additional trivial case requires no such analysis). Furthermore, the
coordinate values may be readily obtained from an eight bit vector by
means of a lookup table which is easily implemented in a read only memory
(ROM). This method provides for rapid surface tesselation and offers two
significant advantages. First, the vertices of the triangular or polygonal
structures generated in the present invention, lie on the edges of cubical
voxel grid patterns. This permits the use of interpolative methods for
adjusting the position of the polygonal vertex along the cubical edge. In
particular, non-linear interpolation is provided to produce smoother, more
accurate images. This interpolation is done in accordance with data values
occurring at three or more grid points, which values may be treated as
weights. This provides additional flexibility for more accurately
approximating the desired surface to be viewed. Secondly, since the
representational objects generated in the present invention comprise
polygons and triangles, normals to these approximating surfaces are
readily computed and may be provided directly to devices designed for
accepting display data in this form. This additional ability to accurately
portray surface and surface normal information in a rapid fashion provides
the present invention with significant advantages. Not the least of these
advantages is the fact that the polygonal format generated is compatible
with advanced graphics workstations which are used to manipulate three
dimensional surface data. It is also seen that the resolution of the
images produced by the present invention are superior to previous methods
since the signal information is interpolated, rather than quantized, to
accurately determine surface position and normal direction. As pointed out
above, it is the accurate portrayal of the surface and the surface normals
which provide the essential clues for the visual perception of displayed
images as three dimensional objects.
DESCRIPTION OF THE FIGURES
The subject matter which is regarded as the invention is particularly
pointed out and distinctly claimed in the concluding portion of the
specification. The invention, however, both as to organization and method
of practice, together with further objects and advantages thereof, may
best be understood by reference to the following description taken in
connection with the accompanying drawings in which:
FIG. 1 is a perspective drawing illustrating a vertex labelling scheme
associated with each voxel in a three dimensional array of data;
FIG. 2 is a perspective drawing illustrating an edge labelling scheme
associated with each voxel element in a three dimensional array of data;
FIGS. 3A-3N are perspective illustrations included for the purpose of
demonstrating the fact that all 256 intersection cases are reducable to
only 14 distinct cases;
FIGS. 4A-4N are perspective illustrations which show the specific polygon
or triangle employed for each one of the 14 cases;
FIGS. 4A'-4N' are plan views of the cube and surface structure shown in
FIGS. 4A-4N, respectively;
FIG. 4B" illustrates a plan view of FIG. 4B illustrating a slightly
different polygonal representation as compared with that shown in FIG.
4B';
FIG. 5 is a perspective view illustrating a linear interpolation method;
FIG. 6A is an isometric view illustrating a network of quantized binary
data points lying on the vertices of a cubical grid structure;
FIG. 6B is an isometric view similar to that shown in FIG. 6A in which the
present invention is illustrated for a set of contiguous voxel elements;
FIG. 6C is an isometric view of the three dimensional surface structure
produced in accordance with the present invention in FIG. 6B but drawn
separately from the data points so as to provide a better view of the
approximating surface for the data elements shown in FIG. 6A;
FIG. 7 is a plot of intensity as a function of pixel distance which
particularly points out the ability to distinguish internal body
structures as a function of the measurement of various physical
properties;
FIG. 8 is a flow chart illustrating data flow in the present invention;
FIG. 9 is a functional block diagram more particularly illustrating
functional components in a system constructed in accordance with the
present invention;
FIG. 10 is a photograph of a CRT image of the skull of a living human being
shown from the front;
FIG. 11 is a photograph of a CRT image of the side view of the same skull
as shown in FIG. 10, this image being generated from the same data as FIG.
10;
FIG. 12 is a photograph of a CRT display screen image of the skull shown in
FIGS. 10 and 11, viewed from a more rearward position and particularly
illustrating the presence of certain undesirable artifacts;
FIG. 13 is a photograph of a CRT display screen image similar to that shown
in FIG. 12 except that undesirable artifacts have been reduced by the
non-linear interpolation method of the present invention.
DETAILED DESCRIPTION OF THE INVENTION
An understanding of the present invention can only be had by fully
understanding the method of surface approximation employed. Likewise, this
surface approximation method cannot be properly appreciated without
analyzing the 14 cases illustrated in FIGS. 3 and 4. In order to
understand the contents of these figures, one must first appreciate the
vertex and edge labelling conventions employed. The vertex labelling
scheme is illustrated in FIG. 1, which illustrates the labelling
convention applied to eight cubical vertices, V1 through V8, as shown.
Likewise, FIG. 2 illustrates the labelling of the 12 cubical edges. In
FIG. 1, the set of vertices illustrated are, in accordance with the
definition given above, describable as being cubically adjacent. However,
since scaling in any of three distinct directions is possible, it is
understood that such points may also lie on the corners of a rectangular
parallelopiped. However, the illustrations herein have been directed to
regular cubical structures for purposes of clarity. It is pointed out that
the illustrations in FIGS. 1 and 2 have been drawn with edges E3, E4, and
E8 being shown as dotted lines to reflect their presence at the rear of
the structure, that is, they are illustrated as hidden lines. This is also
true of FIGS. 3A-3N and 4A-4N. It is noted that other vertex and edge
labelling arrangements could just as easily have been employed without
departing from the principles of the present invention. It is nonetheless
important, however, to employ consistent edge and vertex labelling
schemes.
Before a detailed discussion of FIGS. 3 and 4 is undertaken, it is
appropriate to point out several features which are common to all of these
drawings. These drawings illustrate 14 cases that are included as part of
the analysis made in the present invention. These 14 cases have been
reduced from a total of 256 possible cases. In each of the figures being
considered, vertices are shown as filled in circles. Edges are depicted by
open circles lying at the midpoints of the edges. In FIGS. 4A-4N, a
surface or set of surfaces is shown. Each of these surfaces is defined by
a sequence of edge points. Likewise, each surface is designed to isolate
one or more of the eight vertices. In one case, only a single vertex must
be isolated. In other cases, two, three, or four vertex points are to be
isolated by triangular or polygonal surface approximations. These surfaces
are approximations to the intersection of the desired surface with the
voxel element. It is of course, understood that the entire surface is to
be reconstructed from a plurality of these individual surface elements. In
FIGS. 4A'-4N' and in 4B", indications are given for a vector normal to the
approximating surfaces shown. In most cases, this normal direction is
illustrated by circulating arrow following the righthand rule convention.
In each case illustrated, the normal direction has been selected to be
directed away from the vertex which is being isolated by the surface. In
at least one case, because of the orientation of the polygons generated,
the surface normals themselves are visible (see FIG. 4J').
Attention is now directed to analyzing several examples of the polygonal
surfaces generated in accordance with the system and method of the present
invention. These polygonal surfaces are generated in response to the
production of an eight bit binary vector based upon data comparisons made
at each set of eight cubically adjacent grid locations within the body
being investigated.
Attention is now specifically directed to case 1 as illustrated in FIGS.
3A, 4A, and 4A'. FIG. 3A illustrates the case in which a single vertex is
present at one of the eight vertex points of the cube. In FIG. 3A, vertex
1, or V1, is shown as being present. This corresponds to the situation in
which data values associated with the eight vertex points have been
compared with a threshhold value with the result that only one of the
associated vertex values was found to be above (or below) a threshhold
value. It is the threshhold value or range of values which serves to
isolate the particular surface or surfaces within the three dimensional
body being considered. For ease of appreciating the geometry, FIG. 3A
shows a block in the corner associated with V1. For a proper understanding
of the present invention, it should be appreciated that case 1 actually
represents a plurality of subcases which are determined by rotation about
various axes. For example, rotations about one or more orthogonal axes
through an angle of 90.degree. , can move the small, internal block of
FIG. 3A into any desired corner of the cube. For example, rotation about a
horizontal axis extending from the middle of the front face to the middle
of the rear face of the cube shown can move the block from the V1 position
to the V5 position and then from V5 position to the V6 position, and then
from the V6 position to the V2 position, or in the corresponding opposite
direction. Likewise, rotations about other selected axes are capable of
producing a situation which differs from the case illustrated only in
specific orientation and not in geometric structure. Likewise, case 1 also
includes the complement situation in which vertices V2, V3, V4, V5, V6,
V7, and V8 are turned "on" and in which V1 is turned "off". Thus, through
rotational invariance and the use of complementary situations, it is
appreciated that case 1 actually stands for 16 subcases (8 rotational
invariances and their corresponding 8 complement cases).
One of the objects of the present invention is to generate polygonal
surfaces which represent surface approximations. Consideration then is
given to the nature of the surface which in | | |
