вход по аккаунту


A microcomputer-based graphical reconstruction technique for serial sectioned objects with hidden line removal.

код для вставкиСкачать
A Microcomputer-Based Graphical Reconstruction
Technique for Serial Sectioned Objects, With
Hidden Line Removal
Institute for Zoology, State University of Ghent, Belgium
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
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
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
Address reprint requests to Peter Aerts, Laboratorium voor Morfologie en Systematiek der Dieren, Ledeganckstraat 35, B 9000 Gent,
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).
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.
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.
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:
sinasinb cosa
- sina
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
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.
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:
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.
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
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-
played, and deletion only proceeds after confirmation of
the instruction.
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
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.
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).
The scheme of Figure 5 shows how to put into practice
the most important routines of the package. The whole
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
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
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.
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.
Fig. 5. Scheme of the software. For explanation, see text.
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
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.
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 .
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.
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.,
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.
Без категории
Размер файла
725 Кб
base, removal, graphical, microcomputer, serial, objects, line, hidden, techniques, reconstruction, sectioned
Пожаловаться на содержимое документа