A microcomputer-based graphical reconstruction technique for serial sectioned objects with hidden line removal.код для вставкиСкачать
THE ANATOMICAL RECORD 215:84-91(1986) A Microcomputer-Based Graphical Reconstruction Technique for Serial Sectioned Objects, With Hidden Line Removal W. VANDEN BERGHE, P. AERTS, H. CLAEYS, A N D W. VERRAES Institute for Zoology, State University of Ghent, Belgium ABSTRACT The presented software package fulfills the need for processing serial sections with a microcomputer configuration, enabling three-dimensional reconstruction with hidden line removal. The language used is a n interpreted BASICdialect (HPL). The input is performed via a n interactive program. The object can be rotated in space. The Hidden Line algorithm does not depend upon a raster technique. Points of intersection of successive contours are calculated and inserted, thus providing drawings of high resolution and quality. The handling time can be said to be short, especially when considering the capacities of the microcomputer configuration used. With the increased availability of computers, systems for automatic three-dimensional reconstruction have become more and more popular in morphological and histological research. Digitizing, storing, and drawing after rotation offer no problem for even a home computer. Difficulties arise, however, when hidden lines have to be removed from the drawings. In engineering applications, 3D graphics, with or without hidden line removal, have been run on larger computer systems for several years. However, the constraints there are totally different: 1) Data are not bound to parallel planes, unlike in serially sectioned material. This necessitates elaborated depth-search algorithms, which take up a large part of programming effort. 2) Shapes are usually regular, which implies that their boundaries can be described by less points than in the case of sections through biological structures. In the past few years, there have been some publications on 3D reconstructions for biologists. Katz and Levintal (1972) have published a paper on interactive computer graphics. Since then, a number of authors have given data on computer-aided reconstruction techniques. Huijsmans et al. (1984)have given a brief survey of contour-oriented computer-aided reconstructions from serial sections. Most authors worked on EM serial sections, using minicomputers, or even larger computer systems to elaborate the reconstructions (among others, Willey et al., 1973; Cahan and Trombka, 1975; Shantz and McCann, 1978; Macagno et al., 1979; Marino et al., 1980; Sobel et al., 1980; Stevens et al., 1980). As far as we know, only Street and Mize (1983)have used a microcomputer setup. Many of these publications concern an automatic microprocessor-controlled image analysis (Macagno et al., 1979; Sobel et al., 1980; Stevens et ab, 1980; Huijsmans et al., 1984). Other investigators used LM sections (Dursteler et al., 1977; Afshar and Dykes, 1982; Perkins and Green, 1982; Johnson and Capowski, 1983; Steigman et al., 1983 Thompson et al., 1983; Wong et al., 1983). Prothero and Prothero (1982) mentioned a A 1986 ALAN R. LISS. INC. microcomputer-based software package, without revealing the actual algorithms. Overall, algorithms are rarely mentioned. Cahan and Trombka (1975)gave some information on a rotation array for the coordinate system, but they did not use a hidden line removal routine. Shantz and McCann (1978)described an optimal surfacemapping technique and a n algorithm to compute realistically shaded surfaces. Marino et al. (1980) used a triangulation technique to compute coordinate transformation, light reflections, and shaded surfaces. Finally, Huijsmans et al. (1984) published a concatenated view transformation matrix, which can be used to rotate the reconstructed object. They noted that the generation of hidden line views is still too time-consuming for a microcomputer. None of the mentioned papers fully satisfied the need for a low-budget, fast-processing, and high-quality application. Therefore, we have developed a 3D reconstruction method for PC-like configurations. Minimal hardware for our system consists, besides the central unit, of two floppy drives, a digitizer, and a plotter. In our configuration a graphics screen is used to follow gradually the buildup of the reconstructions. A hard disk used instead of the external floppy drives should still considerably reduce the reconstruction time. The developed software uses 192K bytes of internal memory, and allows processing of contours of up to 1,000 points each. The highest possible resolution is determined by the resolution of the digitizer, i.e. 0.1 mm in our configuration. If one is satisfied with a lower resolution, the same contours take less points, so less memory is required. Received May 22, 1985; accepted October 30, 1985. P. Aerts is a research assistant a t the National Fund for Scientific Research. Address reprint requests to Peter Aerts, Laboratorium voor Morfologie en Systematiek der Dieren, Ledeganckstraat 35, B 9000 Gent, Belgium. 85 COMPUTER RECONSTRUCTIONS The program does not use a bit-mapping technique, but calculates points of intersections between the projections of successive contours. This has the advantage that lines of the hidden contour can be prolonged to the hiding contour, thus giving a neater picture by the absence of gaps. Notwithstanding the fact that the system is written in a n interpreted language, even complicated reconstructions are completed within a reasonable time span (see legend of Fig. 6). Y '---- CONFIGURATION This software package has been developed to run on a Hewlett Packard 9826A microcomputer with one internal Ei1/4'' flexible disk drive (270K) and a total of 192K RAM. The H P 82901111 dual 5l14" flexible disk drive has a capacity of 2 x 270K bytes. Contours are digitized with a Summagraphics tablet. The resolution of the tablet is 0.1 mm; the digitizing area is 0.5 x 0.5 m. Images of the reconstructions are displayed on a n HP 1311B vector screen, via a n HP 1351A graphics generator. The resulting reconstructions are plotted by a n H P 7470A plotter. The programming language used at this stage is HPL. It is a fast-interpreted, BASIC-like language with extended graphical and arithmetical capabilities. The program will run only on H P machines, equipped with a n HPL interpreter. HPL can easily be translated in standard BASIC. However, one has to take into account that (although the HPL routines are very compact) the totality of all routines takes about 80K bytes. A faster and more portable PASCAL version of the program is planned. Details on the algorithm of the hidden line program will be published elsewhere. OBJECT REFERENCES The present method allows processing of each parallelplane-sectioned (biological) object, on the condition that these sections can be defined in a 3D reference grid which has one of its reference planes oriented parallel to the plane of the sections. This can be done by sectioning a reference system together with the object. Another possibility is to use each section as a relative reference for the following one. This can be realized by calculating the relative positions with regard to its predecessor of the sections from, e.g., orthogonal photographs of the entire object. For our purposes, the former method is used. Entire heads of fishes (adults and larvae) are embedded in transparent plastic (e.g., Epon). The specimen is then trimmed with a plane parallel to (what has been defined as) either the horizontal or the transversal plane of the object. A layer of stained plastic is then poured onto this plane. So, respectively transversal or frontal sections will be defined in a grid determined by the axis of bilateral symmetry and the axis presented by the layer of stained plastic (Fig. 1).The third dimension can be computed from the thickness of the sections, the magnification used, and the number of preceding sections. The plane of reference parallel to the sectioning plane will be referred to further on as the XY plane. The point of intersection of the XY axes in all sections is situated on the Z axis (Fig. 1). Fig. 1. Successive sections of a series through an object. The stippled areas are the external reference defining the X-axis. The intersection of the mediosagittal line (Y-axis)with the X-axis in each section determines the Z-axis. Rotations a s indicated around the X- and Y-axis are preposed to be positive. ROTATION To simulate the projection of a 3D image, Claeys and Aerts (1984) illustrate that it suffices to rotate the object around two axes (a rotation a around the X axis and a successive rotation b around the Y axis, the latter being inclined as a result of the first rotation a). Except for rotations a and/or b equal to go", the restrictions imposed by the handmade procedure (see Claeys and Aerts, 1984) no longer exist, as coordinate transformation by computer application has become possible. After digitization (see further on), each contour represents a set of 2D coordinates. The third dimension, or Z axis, is given by the number of preceding sections and the thickness of a section. Rotations a and b require a transformation in a new set representing the coordinates of the rotated contour in the original XYZ reference grid. The coordinates of a point after rotation can simply be calculated by using the following multiplication of matrices: cosb 0 sinb sinasinb cosa - sina cosbsina - with Xn, Yn, Zn being the original coordinates of a contour point, and Xt, Yt, and Zt being the coordinates after rotation. The first matrix is the transformation matrix (see Claeys and Aerts, 1984: notice that, when this transformation matrix will be used, rotations as 86 W. VANDEN BERGHE, P. AERTS, H. CLAEYS, AND W. VERRAES indicated on Fig. 1must be called positive). As the final graphical reconstruction will be, in fact, projections of the rotated 3D object on either the XY or the YZ or the XZ plane, the new set of transformed 3D coordinates also allows reconstructions on each of these planes. OBJECT ORGANIZATION A biological object consists of structures, which appear in the sections as closed contours, describing outer andi or inner boundaries of the structure in cross section. Further on, these will respectively be referred to as outer and inner contours. So, contours may enclose each other (e.g., section through the brains and the neurocranium; see Fig. 2). The order in which the points of a n outer contour are stored on disk is clockwise, contrary to inner contours, which are stored counterclockwise. One structure can be built up by several contours per section. These will always be reconstructed together, as the structure level is the lowest level which can be read from disk: per structure and per section one data file is used. This is a 1D array of integers. Its first datum represents the number of contours of the considered structure in the concerned section, the second, the number of points in the first contour (=n) followed by n coordinates stored as one integer per pair, the value in position n + 3 represents the number of points in the second contour, and so on. . . . The organization of the data files of a structure throughout a series of sections is stored in the structure reference file. This file contains, besides the name of the structure, the serial number of the sections in which a t least one contour of the structure has been recorded, and the identification number of the disk on which the concerning data files are stored. The information on all structure reference files of an object resides in the object reference file. It contains a (expandable) list of the structures defined in the object. All object reference files are grouped in one system reference file, which gives general information concerning the data available on disk: species, age, thickness of the sections, magnification, staining, and an 80-character space free for comments. The following scheme represents the manner in which the management of the data is done: SYSTEM REFERENCE FILE structure n- 2 n 2 -n DATA FILES STRUCTURE REFERENCE FILES OBJECT REFERENCE FILES a NCR IC Fig. 2. Schematic representation of a transverse section through the neurocranium and the brain (two structures) of a teleost fish. The neurocranium (NCR) is defined by a n inner (IC) and outer (OC)contour. The brain (BR; stippled) consists in this section of two outer contours. INPUT For magnifications up to ~ O O X sections , are directly projected onto the digitizer by means of a modified slide projector. Higher magnifications require drawings (or photographs) made with a microscope as a n intermediate step. Coordinate points of the contours are fed in the computer by tracing them with a cursor or a pencil. The recording resolution is 0.1 mm. The digitizer is set to stream mode, so as to give the maximal data flow to the central unit, but if the distance from a point to its predecessor is less than 0.5 mm it is rejected by the program. The result is a series of points (i. e., coordinate pairs) more or less evenly spaced along the traced contour. The coordinates then are recalculated to the object reference. These newly defined points are transformed in a 1 byte code: they are defined respective to their predecessor by storing the distance in both X and Y direction in two times 4 bits. Therefore, these orthogonal distances may not exceed 0.7 mm. If this is the case, a point is automatically inserted. There are several options a t the operator’s disposal to help control the input. Any contour can be called from the library and drawn on the graphics screen. This allows one to control the recorded data. If necessary, minor corrections can be made (such as insertion or deletion of one point or a series of points). The reference of a section can be reconsidered. The position of contours in a section can be altered (one by one, or all in one operation) by redefining the coordinate pairs of the points of the concerning contours. The position of the contours in a section can be referenced with respect to other sections by drawing them on the same screen. Relocation of the reference is then accomplished by incrementing X or Y values of the points, or by rotation around the origin of the new reference coordinate system. A group of data of any hierarchical level (like contour, section, . . .) can be deleted from the library in one operation. Before deletion, the data in question are dis- COMPUTER RECONSTRUCTIONS played, and deletion only proceeds after confirmation of the instruction. 87 A THE HIDDEN LINE ALGORITHM The principle of the presented method is to calculate the points of intersection between contours. From these, and from the visibility of one point on the hindmost contour, it is possible to determine which parts of this hindmost contour are visible with respect to the other contour, i. e., the parts that are to be drawn. In order to save memory space and working time, this operation is not performed on each forelying contour separately, but on their “envelope(s).” An envelope is defined as a continuous closed curve, enclosing a partial reconstruction. As with contours, inner and outer envelopes can exist (see Fig. 3). If the reconstruction consists of several nonoverlapping parts, each of these parts is enclosed by a separate envelope. The coordinate points of the contours to be reconstructed are read from disk and recalculated to the demanded rotation and projection (see above). The points of intersection of a contour with the envelope (or envelopes) of the forelying contours are then calculated. As the visibility of any contour will only change after a n intersection, it sufficies to determine the visibility of only one point of this contour. Successive segments between points of intersection will have alternating visibility. The new envelope ( i e . , the combination of the envelope of all forelying contours, together with the last contour) is determined by taking in turn a visible part of the last contour and the connecting part of the former envelope. Between each two parts of the resulting new envelope, the appropriate point of intersection between the former envelope and the last contour is inserted. This process is repeated until a continuous closed curve is formed. If empty areas remain between the last contour and the envelope, separate inner envelopes around these areas are defined in the same way. Once all points of intersection have been used in the construction of the new boundaries, the process is finished. The following contour is then read from disk and compared with the newly constructed envelopes. If there exist inner envelopes, these will be the first to be considered. Parts of the last contour passing through these inner boundaries are drawn, and the new inner envelope (which must necessarily be smaller) is determined. Once all inner boundaries are handled, the visibility with regard to the outer envelope is checked (Fig. 3). THE VISIBILITY The visibility of a point respective to a contour (or envelope) is determined by counting the number of crossings of this contour with the right part of the horizontal line through the point under consideration. In case of a contour around a filled area, a n even (or zero) number of crossings determines a visible point. For a contour around a n empty area, the point will be visible in the opposite case (Fig. 4). A PP LICATI0N The scheme of Figure 5 shows how to put into practice the most important routines of the package. The whole B NS Fig. 3. Schematic representation of the reconstruction routine. A) Partly finished reconstruction (solid line). The envelope (E) of this reconstruction is represented by the dashed line. B) A new section (NS) is added (dotted line) and will be compared with the envelope. C) Visible parts of t h e new section with respect to the envelope are determined. D) New envelope(s) is constructed. In this case also a n inner envelope (IE) must be considered. The following section must be compared with both envelopes. software is menu-driven. To illustrate, three sections of a bony element (paraspenoid of a fish) are used. The cavities within this bone are treated as a separate (hollow) structure (see Object Organization). Once the program is started the operator has the choice to record 88 W. VANDEN BERGHE, P. AERTS, H. CLAEYS, AND W. VERRAES A B Fig. 4. Illustration of the visibility determination of a point with respect to a contour. A) An outer contour; the right part of a horizontal line through a visible point has a n even number or zero intersections (nij with the contour; a n odd number refers to an invisible point. B) An inner contour (solid line); in case of a visible point, the number of intersections will be odd. For invisible points, t h e number will be even or zero. (The arrows on the contours refer to the direction in which the contour defining points a r e stored: clockwise for outer, counterclockwise for inner contours.) new data or to reconstruct (part of) an object stored on disk. In the data recording phase, one may digitize sections or edit previously recorded sections. In both cases, keyboard input is required to specify what data are to be treated. After digitization, coordinate points are converted to a string array and stored on disk. Depending on the operator’s choice, there can be back-looping at different levels. Starting the reconstruction phase, keyboard input, specifying what data are selected, is also required. After that, the further procedure runs automatically until the program is ready for output. Reconstructions can be made with or without hidden line removal. if desired, morphometric data can be printed. For graphical output, data can be sent to the plotter or to the graphics screen. Again, back-looping is possible. EVALUATION OF THE PRESENTED RECONSTRUCTION METHOD Some results of the program are presented in Figure 6. As one can see, even complicated structures can be handled by the Hidden Line algorithm. In Figure 6B, the number of points in several contours is as high as 500; the total number of points in the distinct inner and outer envelopes is up to 2,000. The highest number of intersections between a contour and a n envelope encountered during this reconstruction is over 100. The time needed to make a reconstruction like this one remains, however, acceptable. This handling time is a function of the complexity of the component contours, which is mainly reflected in the number of intersections, rather than in the number of coordinate pairs. Another factor which may dramatically influence the speed of reconstruction is the number of generated envelopes. This is the main reason for the relative long handling time as indicated in the legend of Figure 6B: during this reconstruction, a t a certain instant, up to 130 inner envelopes are taken into consideration. As the visibility has only to be checked for one point per contour, the handling time does not increase proportionally with the number of contour defining points. This makes it possible to work with a very high resolution without increasing considerably the handling time. Claeys and Aerts (1984) present a manual method for 3D reconstructions. With this method, the same frontal view as the present Figure 6C has been completed in about 300 minutes. The reconstruction time for Figure 6C equals 151 minutes. A similar amount of time is used for the digitization of the contours. However, there are three arguments in favor of the computerized method: 1) The restrictions on the range of rotations no longer exist. 2) The reconstruction itself is totally automatic. Thus, it does not require a n operator’s attention. 3) Tracing has to be done only once. With the manual method, tracing must be repeated each time the angle of view is altered. Moreover, the processing time for more complex reconstructions will be relatively shorter for the presented automatic method. With the increase of the complexity of (biological) structures, the handling time for the manual method will also increase considerably since superpositions, requiring repeated counterchecks, will become unavoidable. A major drawback of this method is its sensitivity to errors. If one intersection between two boundaries is not found, or the visibility of one point is determined incorrectly, the whole process collapses. Such situations can occur, e.g.,by a self-crossing contour. On the other hand, this drawback can equally well be explained as a n advantage: as we know that a minor error will have catastrophic consequences, we can be confident that a drawing with no apparent mistakes is totally correct. By calculating and inserting the intersections between contours, one gets a very clear and neat image. This is especially of importance when contours are reconstructed which are close to one another. Starting the reconstruction at the front end, one sooner gets a n impression of the global appearance. Two advantages of this method over raster techniques are that this program consumes a lot less memory and the resolution of the reconstruction does not depend upon hardware limitations. COMPUTER RECONSTRUCTIONS OBJECT 89 n SECTIONS SECTION I SECTION 1-1 SECTION 1+1 START PROGRAM t -OR I DATA RECORDI NG I DEJECT NR SECTION NR FOR DIGITIZING M Y STRUCTURE 1 NEXT STRUCTURE NEXT SECTION -RECONSTRUCT I ON KEYBOAR0 INPUT DEJECT NR STRUCTURE NR(S)F I R S T SECTIONLAST SECTION- PLANE OF PROJECTION HlDOEN LINE REMOVAL PR' NTER -YORPHOMETR NEXT SECTION IC RECONSTRUCTION v SCREEN PLOTTER*' v NEXT ROTATION i NEXT RECONSTRUCTION rid n tNU Fig. 5. Scheme of the software. For explanation, see text. 90 W. VANDEN BERGHE, P. AERTS, H. CLAEYS, AND W. VERRAES B C Fig. 6. Some results of the presented program. A) A stereopair of the snout region of a juvenile Salmo gairdneri. Total number of points: 3,526. Visible points: 2,187. Reconstruction time: 11 minutes. B) Part of the parasphenoid of Astatotilapia elegans juvenile. Total number of points: 11,392. Visible points: 5,726. Reconstruction time: 72 minutes. C) Cartilaginous parts of the brachial basket of a trout larva, rostrodorsal and caudoventral view. The rostrodorsal view can be compared with Figure 4B of Claeys and Aerts, (1984). Total number of points in one view: 12,420. Visible points: 8,190. Reconstruction time:151 minutes. COMPUTER RECONSTRUCTIONS The time required for the present algorithm is long compared to raster techniques. In the legend of Figure 6, handling times of our reconstructions are mentioned. However, we consider this time span reasonable, especially when the following facts are taken into account: "1 The language used (HPL) is interpreted. A compiled version should run several times faster. Moreover, some features are not implemented in HPL, such as, e.g.,the use of integers, definition of user functions, etc. "1 Notwithstanding the advanced CPU (MC 68000), our system can still be regarded as a small configuration: the internal memory is limited, a hard disk is not available, and the capacity of the used floppy disks is very small. At this moment, a modern PC-like configuration amply satisfies the requirements of the program. AC KNOWLEDGMENT We are very grateful to Drs. G. Elshoud of the Leiden University (The Netherlands) for the provided information and discussions on this topic. We wish to thank Dr. P. Herman of the State University of Ghent for his review, and Mrs. A. Huysseune and Mr. K. Roche (State University of Ghent) for their comments on the English. We thank Miss M. Strobbe for her help in finishing Figure 5 . LITERATURE CITED Afshar, F., and E. Dykes (1982) A three-dimensional reconstruction of the human brain stem. J. Neurosurg., 57:491-495. Cahan, L., and B. Trombka (1975) Computer graphics. Three dimensional reconstruction of thalamic anatomy from serial sections. Comp. Prog. Biomed., 5:91-98. Claeys, H., and P. Aerts (1984) A simplified method for hand-made oblique graphical reconstructions. Anat. Rec., 210683-692. Dursteler, M., C. Blakemore, and L. Garey (1977) Uptake of horseradish peroxydase by geniculo-cortical axons in the golden hamster: Analysis by computer reconstruction. Exp. Brain Res., 29:487-500. 91 Huijsmans, D., W. Lamers, J. Los, J. Smith, and J. Strackee (1984) Computer-aided three-dimensional reconstruction from serial sections: A software package for reconstruction and selective image generation for complex topologies. In: Eurographics, '84; Bo and Tuckers, eds. Elsevier Scientic Publishing, pp. 3-13. Johnson, E., and J. Capowski (1983) A system for the three-dimensional reconstruction of biological structures. Comp. Biomed. Res., 16:79-87. Katz, L., and C. Levintal (1972) Interactive computer graphics and representation of complex biological structures. Ann. Rev. Biophys. Bioeng., 1:465-504. Macagno, E., C. Levintal, and I. Sobel (1979) Three-dimensional computer reconstruction of neurons and neuronal assemblies. Ann. Rev. Biophys. Bioeng., 8:323-351. Marino, T., P. Cook, L. Cook, and S. Dwyer 111 (1980) The use of computer imaging techniques to visualise cardiac muscle cells in three dimensions. Anat. Rec., 198:537-546. Perkins, W., and R. Green (1982) Three dimensional reconstruction of biological sections. J. Biomed. Eng., 4:37-43. Prothero, J., and J. Prothero (1982) Three dimensional reconstruction from serial sections. I. A portable microcomputer based software package in Fortran. Comp. Biom. Res., 15:598-604. Shantz, M., and G. McCann (1978) Computational morphology: Threedimensional computer graphics for electron microscopy. IEEE Trans. Biomed. Eng., 25U1:99-103. Sobel, I., C. Levintal, and E. Macagno (1980) Special techniques for the automatic computer reconstruction of neuronal structures. Ann. Rev. Biophys. Bioeng., 9:347-362. Steigman, S., and Y. Michaeli, M. Weinreb Jr., and G. Zajicek (1983) Three-dimensional reconstruction of the rat incisor by means of computerised histomorphometry. Anat. Rec., 205:455-464. Stevens, J., T. Davis, N. Friedman, and P. Sterling (1980)A systematic approach to reconstructing microcircuitry by electron microscopy of serial sections. Brain Res. Rev., 22655293. Street, C.H., and R.R. Mize (1983) A simple microcomputer based three-dimensional serial section reconstruction system (Micros). J. Neurosci. Methods, 7:359-375. Tompson, R., Y.M. Wong, and T. Fitzharris (1983) A computer graphic study of cardiac truncal septation. Anat. Rec., 206:207-214. Willey, T., R. Shultz, and A. Gott (1973) Computer graphics in three dimensions for perspective reconstructions of brain ultrastructure. IEEE Trans. Biomed. Eng., 20(4):288-291. Wong, Y.M., R. Thompson, L. Cobb, and T. Fitzharris (1983) Computer reconstructions of serial sections. Comp. Biomed. Res., 16:580-586.