pc_3d.txt

3DMEDLIB - 三维医学图像开发源程序库及范例

Here d is the distance of the voxel from the origin and D is the maximum distance a voxel can be (Figure 3) from the viewing plane.

We have included here a small program in C to do depth shading (Distances.c) of an object in the X direction.  The CT data is contained in a set of files with the name CTBILD.nnn where nnn is a number.  Each file contains one CT slice and the first file is conventionally CTBILD.001 and so on.

Distance (or distance-only as it is sometimes called) shading is the fastest method of shading since the computational effort to obtain a surface approximation is minimal.  The CT data is read and processed only once and the surface shade is obtained immediately by simply saving the index values of the original slice array when a threshold transition is encountered.  However, such shading gives a very smooth appearance that is lacking in fine detail and curvature information.  Distance shading was included here primarily for comparison, although in some medical cases it can still give sufficient information.

The program (Distances.C) demonstrates the simplest type of depth shaded 3D reconstruction.  Today there are systems which can generate much more impressive images.  Nevertheless, this small program illustrates the fundamentals of 3-D reconstruction from serial slices.

The Distances.C program assumes that the original CT scans are in consecutive files named CTBILD.XXX where XXX are the slice numbers in ascending order.

The program reads and processes a slice at a time and produces a line of the image output for each.  The result is a shaded projection of the original slice along the viewing direction.  The projection is computed by examining each voxel along the viewing direction until the value passes a certain threshold and saving the distance in the corresponding element of the projection vector.

Each incoming slice is stored in a matrix in memory.  The program codes the array index of the location where the threshold is exceeded, as the grayscale value of the output image.  The result gives us the depth-coded 3-D reconstruction image of the scanned object as seen from the chosen view direction.

GRADIENT SHADING

The reconstruction program takes a set of CT files from one consecutive scan sequence and outputs a set of 3-D view images.  The set of output images consists of 9 basic views:  Front, back, right-lateral, left-lateral, left midsagittal, right midsagittal, and top intracranial.  For each view direction two images are created - one gradient shaded and the other depth coded (or distance only shaded).

The views were reconstructed first by thresholding (or level slicing) the data and then shading.  A Z-buffer algorithm was used to give the distance-only shaded images (distances.c).

The gradient of the bone surface at a point is obtained by examining the distances calculated at the surface for adjacent points along a specified viewing direction.

This is a relatively accurate approximation--the error is the size of the unit squared (which in this case is Dx or Dy, the size of a pixel).  The surface is asumed to be a continuous, smooth function of (x,y) in a local area around the point.  The gradient is computed as

腟={[Z(x+1,y)-Z(x-1,y)]/2*Dx,[Z(x,y+1)-Z(x,y-1)]/2*Dy,1}.

The gradient value computed for each pixel is Cosf where f is the angle between the surface gradient vector and the viewing direction.

Gradient shading is exceptionally good in edge rendering of surfaces because at the edges the gradient becomes perpendicular to the viewing direction and the corresponding shade becomes very dark.  The rapid changes in gradient intensity at edges amplifies these features in images.  This quality of gradient shading enables the depiction of fine anatomical details of internal body surfaces.

We interpolated between slices to overcome the problem of artifactual contour creation at slices stacked on one another.  The slices were interpolated linearly according to the zoom or magnification factor (the ratio of voxel distance in the z direction and the x direction when the scans are presumed to be parallel to the XY plane).  The zoom factor is not necessarily an integer and the number of interpolation points between two slices is not uniform, for all slices pairs.  It is important that an image has the correct dimensions to properly scale the results and allow one to make measurements from a life-size hardcopy (photograph) of the final image.  Our experiments have shown that doing interpolation on the image gray shades after 3D reconstruction has little effect on image quality.  On the other hand, interpolation before the reconstruction gives a substantial improvement in picture quality.  The pictures obtained after slice interpolation were improved in apparent surface detail, though they were not completely free of the slice-edge contour artifact.

The reconstruction program read the input data twice:  forward and backward.  The first pass created the rear, left and bottom views and the second pass created the front, right and top views.  The method for computing the gradient shade was simple:  whenever a threshold transition was encountered, the four columns surrounding the voxel were found.  The gradient value was calculated as explained above using the transition direction to be the surface direction (that is, if the transition was in the X direction the surface was assumed to be S=X(y,x)).

Flow-charts for the more complex generation of gradient shaded images in am IBM PC/AT clone are provided for a main program which first uses getdistances to obtain depth-coded images that are gradient shaded in the x, y, and z directions using doviews.

IMPLEMENTATION

An IBM PC/AT clone was used for 3-D reconstruction processing.  This unit has a built-in Ethernet connection and software support which enables the transfer of high data volume from VAX computers through a DECNET network.  The ability to manipulate high volume of data is the principal problem in medical image 3-D reconstruction processing and display.  Typically, the CT scan data set for a single patient will contain 10 MBytes of data.  A networked PC/AT is an attractive alternative for CT scan post-processing applications.

The PC/AT clone, running on a clock of 8 Mhz, was equipped with one 1Mbyte of memory, a 1.2 MB floppy disk drive and a monochrome display.  An Ethernet controller (3 COM) was installed and DECNET local area network (LAN) software was used.  This enables the PC/AT clone to transfer files back and forth from a VAX or use the VAX disks as if they were local PC/AT devices (VAX/VMS services for MS-DOS software product from DEC).

A 20 MB hard disk was installed, leaving room for two PC/AT bus 16-bit application boards.  An additional 2 MB of memory was eventually installed inside the PC/AT clone, as well as an 80287 floating point coprocessor.  We did use these options in the latest stages of our development and found that both can be used to decrease the computation time for 3D surface reconstructions.

The frame buffer system we used was an AT&T Targa24 board.  The Targa images are RGB with 8 bits for each color.  Similar results can be obtained with alternative frame buffer interface cards for the PC/AT.

The code was written in Microsoft C version 5, but with a few changes such as file handling calls and huge array declarations, it can be compiled by any C compiler.  We found the Microsoft CodeView debugger to be an extremely powerful tool in this effort which dramatically reduced our development time.

The program is organized in several modules (see flow charts):

GETDISTANCES - This is actually the first pass over the CT data.  The program travels over the CT data and extracts the distance of the first threshold transition in the X, Y, and Z directions simultaneously.  The distance of a pixel on the image plane in the X and Y directions is obtained after processing one slice.  While the distance in the Z direction is only known after processing all the slices.  The distances are saved in three files respectively as floating point data.  (Getdistances flow chart)

DOVIEWS - After the distance file exists, this procedure goes over the distance data and creates the distance-only and gradient view.  The pixels at the frame of the view are missing some neighbors, so the central difference can not be used to calculate their gradient.  Instead forward and backward difference is used.  This is why there is a separate code to handle the first and last line of the view, and the first and last pixel of each line.  (Doviews flow chart)

The patient used in the example reconstruction is a three an a half year old girl with a cleft lip and palate.  A total of 78 CT scan slices were used in the reconstruction, a total of 5,111,808 voxels.  The program which produced the 3-D views ran an hour and twenty minutes total or about one minute for each slice.  If enough RAM memory is available on the system, a RAM-disk can be defined and all the intermediate distance values can be saved in memory instead of on the hard disk.  This method can dramatically reduce processing time for surface reconstruction.

CONCLUSION

We have demonstrated the feasibility of 3-D image reconstruction on a personal computer, and our work shows that satisfactory images can be obtained in reasonable time.  The newest generation of personal computers, such as the 80386 or 68020 baed machines, can be used as the basis of a medical image workstation and perform many useful post-processing imaging functions.  We have found that a workstation will need at least 5 MB of memory and a 40 MB hard disk to enable convenient utilization.  However, for those who have an IBM PC/AT or compatible, good quality 3-D images can be obtained with modest effort.

Computer graphics have an important role in biomedical research and medical imaging.  The emergence of high performance graphics workstations and medical image transmission display and archiving systems are important new developments.

3-D reconstruction from CT and MRI scans to meet the clinical requirements for evaluating patients with complex morphologic abnormalities can be accomplished using available methods.  These methods have been applied to diagnostic and therapeutic problems in orthopedics, cardiac and craniofacial surgery, and nuclear medicine.  The basis for analysis of complex craniofacial malformations has been static surface views of the skull and facial structures in predefined projections.  More elaborate analysis, using a CAD/CAM system, has been applied to especially complex cases. 


REFERENCES

Geist D, Vannier MW, Knapp RH:  Networked personal computer software system for 3-D CT scan reconstruction imaging, National Computer Graphics Assn., Vol. III, 113-117, 1988.

Geist D, Vannier MW, Knapp RH, Marsh JL:  3-D medical imaging in an object oriented environment, SPIE Medical Imaging II, Vol. 914, 1299-1306, 1988.

Herman GT, Liu HK:  Three-dimensional display of human organs from computed tomographs, Comp. Graphics and Image Proc., 7:130-138, 1978.

Herman GT, Liu HK:  Three dimensional display of human organs from computed tomographs, Jour. Computer Assisted Tomography, 1:155-160, 1977.

Hildebolt CF, Vannier MW:  3-D measurement accuracy of skull surface landmarks, American Journal of Physical Anthropology, 76:497-503, 1988.

Hildebolt CF, Vannier MW, Knapp RH:  Validation of skull 3-D CT measurements, American Journal of Physical Anthropology, in press.

Requicha AAG:  Representations for rigid solids: Theory, methods, and systems, Comp. Surveys, 12:(4)437-464, Dec. 1980.

Srihari SN:  Representation of three-dimensional digital images, Comp. Surveys, 13:(4)399-424, 1981.

Totty WG, Vannier MW:  Analysis of complex musculoskeletal anatomy using three-dimensional surface reconstruction, Radiology, 150:173-177, 1984.

Udupa JK:  Display of 3D information in discrete 3D scenes produced by computerized tomography, Proc. IEEE, 71:(3)420-431, 1983.

Vannier MW, Marsh JL, Warren JO:  Three-dimensional computer graphics for craniofacial surgical planning and evaluation, Comput. Graphics, 17:263-274, 1983.

Vannier MW, Marsh JL, Gado MH:  Three-dimensional display of intracranial soft-tissue abnormalities, American Journal of Neuroradiology, 4:520-521, 1983.

Vannier MW, Gutierrez FR, Laschinger J, Gronemeyer S, Canter C, Knapp RH:  Three-dimensional MR imaging of congenital heart disease, Radiographics, Vol. 8, No. 5, 857-872, 1988.

Zatz LM:  Basic principles in computed tomography scanning, in T.H. Newton and D.G. Potts, Eds: Radiology of the Skull and Brain-Technical Aspects of Computed Tomography, 5:3853-3876, (1981) C.V. Mosby, St. Louis.