From: rfd@po.CWRU.Edu (Richard F. Drushel)
Newsgroups: comp.graphics
Subject: SUMMARY:  3-D reconstruction techniques (LONG--26K)
Date: 8 Jan 1993 14:29:58 GMT
Organization: Case Western Reserve University, Cleveland, OH (USA)
Reply-To: rfd@po.CWRU.Edu (Richard F. Drushel)
NNTP-Posting-Host: thor.ins.cwru.edu


     SURVEY OF METHODS FOR 3-DIMENSIONAL RECONSTRUCTION 1991-1993

         compiled by Dr. Richard F. Drushel (rfd@po.cwru.edu)
                          Department of Biology
                    Case Western Reserve University
                       Cleveland, Ohio  44106  USA
                            (216) 368-3574

                Outline of Survey.

                  I.  USENET search.
                      A.  Dicer (Apple Macintosh).
                      B.  VoxelBox (80x86 family).
                      C.  AutoCAD (80x86 family).
                      D.  GVLware (SGI workstations).
                      E.  Khoros (DEC and other workstations).
                      F.  Miscellaneous software (workstations).
                      G.  Methods (platform-independent).

                 II.  Advertizement search.
                      A.  Minnesota Datametrics Corp.
                      B.  Eutectic Electronics, Inc.

                III.  Biological literature search.
                      A.  Volumetric methods.
                      B.  Rotationally-symmetric or repeating
                          structures.
                      C.  GLOM program.
                      D.  Ultrasound imaging.
                      E.  Automatic section alignment.
                      F.  Hand methods.

******************************************************************************

  I.  USENET search.  This summary is the result of the following request for
information which I posted to comp.graphics on 31 December 1992:

>From: rfd@po.CWRU.Edu (Richard F. Drushel)
>Newsgroups: comp.graphics
>Subject: 3D reconstruction from serial cross sections
>Reply-To: rfd@po.CWRU.Edu (Richard F. Drushel)
>Date: Thu Dec 31 16:07:57 1992
>
>       For my Ph.D. dissertation, I did this the good old-fashioned
>19th-century German anatomical way--by hand.  Trace sections onto paper,
>align using a light table, then reconstruct by isometric (orthogonal)
>projection.  Since I am also an illustrator, this turned out well.  But
>now that I am a postdoc, my new boss wants to use computer graphics
>methods.
>
>       The problem is, at least in the biological field, every paper
>published in the last 2 years I have seen dealing with 3D reconstructions
>uses either the 19th-century by-hand method, or else jerry-rigged hardware
>and custom, hardware-specific software (read: not commercially available).
>
>       I am prepared to admit that we biologists are not up to speed
>on the current advances in such analyses (thus the preponderance of
>jerry-rigged equipment).  What, then, are more modern means of making
>3D reconstructions from serial cross sections?  E-mail please and I
>will summarize for the net.
>
>       I would be particularly interested in any solutions based
>on the 80x86 computer family (for my owm practical needs), but please
>feel free to describe any setup you wish which does this kind of
>analysis.  Many thanks in advance.

      The following newsgroups appear to be resources for information
regarding 3-D reconstruction hardware, software, algorithms, and methods:

      alt.3d
      alt.cad
      alt.cad.autocad
      bionet.biology.computational
      bionet.neuroscience
      comp.graphics
      sci.image.processing

      My sincerest thanks to all those who responded!  Each of you is credited
after the material you submitted.  Replies are grouped according to hardware
platform; aside from minor editing for spelling and punctuation, the words are
those of the respondents.  I received responses from:

      ah395@cleveland.Freenet.Edu (Jeffrey T. Hansen)
      bridget@delphi.beckman.uiuc.edu (Bridget Carragher)
      cn09+@andrew.cmu.edu (Christopher Kalevi Nuuja)
      dona@zelda.nwra.com (Don Altman)
      dwilson@morph.EBME.CWRU.Edu (David Wilson)
      guy@trofis.tfrc.csiro.au (Guy Carpenter)
      hoberoi@limerick.cbs.umn.edu (Himanshu Oberoi)
      JKK103@PSUVM.PSU.EDU ("Mythos / Xcalbrin") {Joe Krug}
      jwp@world.std.com (john w poduska)
      martin@cs.curtin.edu.au (Martin Dougiamas)
      uselton@nas.nasa.gov (Samuel P. Uselton)

******************************************************************************
 
      A.  Dicer (Apple Macintosh).

The program Dicer, marketed by Spyglass, Inc. (217-355-6000), will do
exactly what you want (and a lot more).  It was designed specifically
for studying 3-D data.  Version 2.0 will be out in about a month.  It
will allow you to take arbitrary slices and iso-surfaces, as well as
turn selected regions transparent and produce animations.  The first
version had a multi-page writeup in "Computers in Physics".

Currently it only runs on Macintosh systems.  Windows & Unix
versions are coming.

[From dona@zelda.nwra.com (Don Altman)]

      Spyglass, Inc.
      P.O. Box 6388
      Champaign, IL  61826

Currently the program is in Version 1.12, available at $495.  On February 1st,
Version 2.0 goes on sale at $695.  If you order Version 1.12 now, *BEFORE
February 1st*, the upgrade to Version 2.0 is *FREE*.

     The program's preferred image input form is TIFF, but conversion programs
are available for "almost anything" (quoth the sales rep :)

******************************************************************************

      B.  VoxelBox (80x86 family).

One very powerful technique for this type of reconstruction is called
volume rendering. It basically takes the 2D slices and puts them
together into a 3D cube of scalar values. It then allows you to associate
colors and transparency values to the scalar values, and then the whole
thing can be drawn in 3D.

(Now for the sales push :-)) Volume renderers have traditionally only
been available on workstations in the $5K - $10K per package price range,
but my company, Jaguar Software, has recently started shipping a package
for the PC for $495, or if you order before Jan 31 $325. The following
stat sheet describes the product. If there are any other questions I can
answer, please let me know.

Product Name: VoxelBox
List Price: $495

System Requirements:
        - A 386 or higher based cpu, running Windows 3.x with at
        least 4MB of memory and a video board capable of displaying
        at least 256 colors.

Volume Rendering:
        - High quality ray-tracer.
        - Fast Rasterizer.
        - Voxel based rendering with color/alpha mapping and lighting.
        - Advanced ray-tracing features include shadows, reflections,
        antialiasing and progressive refinement.
        - Volume cropping and slice planes for removing a corner of
        the volume.

Color/Alpha Manipulation:
        - Create, save and import custom color and alpha maps.
        - Histogram Graph and orthogonal slice display aid color/alpha
        map selection.
        - Includes standard color maps such as hue circuit, heat ramp,
        gray scale, etc.

Data Import:
        - Custom compressed volume format for saving disk space.
        - Readers for HDF and AVS volume files.
        - Custom reader handles byte, word, long, float and double
        based binary data, as well as ASCII data. Byte swapping and
        signed data are also supported.

Data Export:
        - Save generated images in popular image file formats: TIFF,
        GIF, PCX, TGA, BMP, HDF.
        - Save imported volumes with custom compressed volume format,
        which also includes a comment field.

Animation:
        - Create and save animations for viewing later.
        - Key frame scripting for simple animation set up.
        - Time line editor for more advanced control of animation
        scripts.
        - Automatic in-between frame generation.
        - Create animations in bounce or loop mode for continuous
        viewing.
        - Save animations as FLI, FLC, RL0, RLE or HDF movies.
        - Includes a redistributable RL0/RLE movie viewer for
        sharing results.

Printing:
        - Prints to all Windows based color and b&w printers.
        - Output includes color/alpha mapping graphs and a set of axes.

Other Features:
        - On-line hypertext help system.
        - Bounding box manipulator.
        - Extensive 8-bit pseudo color support.
        - Multiple views of the same volume.
        - Affordably priced.

      Jaguar Software Inc.
      573 Main St., Suite 9B
      Winchester, MA 01890
      (617) 729-3659

[From: jwp@world.std.com (john w poduska)]

******************************************************************************

      C.  AutoCAD (80x86 family).

I will say yes to your question, AutoCAD can take input from
an ascii file of 3d points and create a mesh from them, but
I'm going to add a huge disclaimer ...

Right out of the box, it's kind of useless.  To do what you're
wanting to do, you're going to need to purchase an additional
hunk of software, or write it yourself, of course.  I'm assuming
that you're taking your cross sectional data from your sea-slug 
bologna, and graphing it in some fashion?  (sounds yummy, too bad
finast doesn't stock it ...)  If this is the case, you're going
to need an interface to take the data and make it useable, because
basically, autocad doesn't know what to do with it as raw x,y,z
data, altho once the data is in, it can construct all sorts of neat
3d meshes and the like from the data.

[From: ah395@cleveland.Freenet.Edu (Jeffrey T. Hansen)]

******************************************************************************

      D.  GVLware (SGI workstations).

If you can access an SGI then 

1) Bring the images over to the SGI.  You have to know the format they are in.
The best form would be a LxM file of bytes.  Each byte representing an
intensity.

2) Then do

 cat img.1 img.2 imn.n > imgLxMxN.bin

3) view the "volume" using bob.  This program is free and available from
several sites.  its home is at ftp.arc.umn.edu.  This is very useful for
viewing the whole volume.  This of course does not reconstruct the image in
the sense of extracting structural info, but by cleverly manipulating the
colormap one can "see" surprising amounts of detail.

I have helped a person who studies embryo development using confocal
microscopy.  He needed roughly 20 pictures (the N dimension) to get reasonable
info.  The more slices you have the better it is :)

<begin blurb>

The Army High Performance Computing Research Center (AHPCRC) and the
Minnesota Supercomputer Center, Inc., have been developing a set of
tools to work with large time dependent 2D and 3D data sets.  In the
Graphics and Visualization Lab (GVL) we are using these tools along
side standard packages, such as SGI Explorer and the Utah Raster
Toolkit, to render 3D volumes and create digital movies.  A couple of
the more general purpose programs have been bundled into a package
called "GVLware".

GVLware, currently consisting of Bob, Raz and Icol, is now available
via ftp.  The most interesting program is probably Bob, an interactive
volume renderer for the SGI.  Raz streams raster images from disk to
an SGI screen, enabling movies larger than memory to be played.  Icol
is a color map editor that works with Bob and Raz.  Source and
pre-built binaries for IRIX 4.0.1 are included.

To acquire GVLware, anonymous ftp to:
        machine - ftp.arc.umn.edu
        file    - /pub/gvl.tar.Z

<end blurb>

[From: hoberoi@limerick.cbs.umn.edu (Himanshu Oberoi)]

******************************************************************************

      E.  Khoros (DEC and other workstations).

Or try Khoros. This is a very very good image analysis package and recently
acquired 3D capabilities.  The package is _HUGE_ about 150Mb of disk but very
versatile and OOP based.  Khoros would be a good first bet.  The DECstation
5000/200 would just about work.  Does it have DECWindows?  You will need that
for sure.  The ftp site for khoros is

pprg.eece.unm.edu [129.24.24.10]: /pub/khoros - *Khoros image processing

the package is reallly very big.  Would take you approx 2-4 hours to ftp it
over.  Try looking in your local area, especially on a computer science
machine and get the executables :).

In any case you will need lots of memory + disk on your machine.

[From: hoberoi@limerick.cbs.umn.edu (Himanshu Oberoi)]

******************************************************************************

      F.  Miscellaneous software (workstations).

(1)   If you cannot get your hands on an SGI then if you can get a
SUN/RS6000/HP etc then get some of the image viewing programs from
ftp.ncsa.uiuc.edu (the good ones are XDataSlice and PolyView (SGI-specific). 
XDataSlice does volume rendering slicing and contouring.  I could send you
some programs that can get from the NxN byte to something XDataSlice
understands.

As for XDataSlice from (ftp.ncsa.uiuc.edu) UNIX/XDataSlice/XDS1.2 has a
DEC Ultrix executable, and XDS2.0b has a DEC 3100 executable.  Source is
also present for the 1.2 version.

And finally if you have an IBM RS6000 you can get DataExplorer from IBM which
is a OOP type program and is very powerful.  Again I could send you some
macros etc to get your data into it.  DataExplorer is available for other
platforms SGI/HP/SUN too from IBM.

There is a commercial product VoxelView.  Runs on SGI and SUN.

[From: hoberoi@limerick.cbs.umn.edu (Himanshu Oberoi)]

(2)   My first publication (while still a grad student) was "Optimal Surface
Reconstruction from Parallel Contours," in CACM Oct. 1976.  (Fuchs, Kedem &
Uselton).  I haven't worked on this problem for awhile, but I do try to keep
up on developments.  Our software was written in FORTRAN on a PDP-11 and I've
moved three jobs since then so I don't still have it.  In fact, I've re-
implemented it twice as consultingjobs for commercial outfits' internal use.

      Ken Sloan, now on faculty at U. Alabama Birmingham, had a package while
he was in Washington that went further (and was more thoroughly "developed"),
handling branching problems and fitting a smooth spline patch surface over the
initial triangulation.  His email is sloan@cis.uab.edu, and he can tell you
current status of that software.  At one point I think it was ftp-able.  (He
often reads this group and may respond himself.)

     Another possibility is a small company called Surgicad.  While still a
grad student, I helped port our software to a Data General machine in a cell
biology lab at Southwest Med in Dallas.  Two MD's (interns? post-docs? anyway
they were slave labor like me) worked as the system hackers in this lab.  One
of them, Dan Schlusselberg is now Pres and CTO of Surgicad.  They sell systems
that may do what you want.  My contact info (may be out of date):

        Surgicad Corp.                     (603) 448-4900
        Chiron Springs                     (603) 448-0179  fax
        115 Etna Rd.
        Lebanon, NH 03766

[From: uselton@nas.nasa.gov (Samuel P. Uselton)]

******************************************************************************

      G.  Methods (platform-independent).

(1)   A method we've had reasonable success with here at the Pittsburgh
Supercomputing Center is this:

      For each cross section, create a 2D grid of density values (or assign
values for each boundry you are interested in).  Values outside the cross
section are 0 (and be sure to have 0's completely surrounding the cross
section).

      Put the 2D grids togeather into a 3D volume and use standard volumetric
techniques on it.  (i.e.  isosurface at the density/boundry thresholds you
are interested in, volumetric rendering, colored slice planes, etc.).

[From: Christopher Kalevi Nuuja <cn09+@andrew.cmu.edu>]

(2)   I have seen applications in both the medical field and the geology/
mining discipline which use serial cross sections to reconstruct solid
objects.  I have in my archive (at home) a paper describing a method for
dealing with some of the tricky bits - where bodies join and divide - which I
always figured would be a good place to start if I was ever asked to implement
such a beastie.  Ref can be provided should you request it.

[From: Guy Carpenter <guy@trofis.tfrc.csiro.au>]

(3)   I don't know if this is what you meant, but I saw on Beyond 2000 on the
Discovery channel, once about people doing 3-d cut away views, etc...on the
computer for dissection in pre-med classes and such.  What they had done was
take very thin slices of the tissue, photograph it, and then load them into
the computer database.  The end result (using appropriate software of course)
was a really detailed 3-d cutaway /peel away viewing of structures.

[From: "Mythos / Xcalbrin" <JKK103@PSUVM.PSU.EDU>   {Joe Krug}]

******************************************************************************

 II.  Advertizement search.  I searched through the 12 issues of Trends in
Neurosciences (TINS) Volume 15 (1992).

      A.  Minnesota Datametrics Corporation
          1000 Ingerson Road
          St. Paul, MN 55126
          (612) 482-7938    FAX (612) 490-9717
          TINS 15: lvii (1992)

      Two systems are available:

(1)   80386/80486-based system with color VGA monitor.

      A special electronic instrument is attached to the microscope stage;
you move the stage to trace the object, and the instrument digitizes the
(x,y) coordinates (5 micron resolution).
      Software displays level curves in isometric (orthogonal)
projection--*DISTORTION*.  Uses VGA/SVGA color monitors.
      Software can perform simple rotations, translations, feature counts,
color different features.
      Cost:  stage instrument $3500, software $1450.

(2)   SGI workstation-based system.

      Input:  either greyscaled images or data in a variety of formats.
      Output:  shaded surfaces, areas, volumes.  *TRUE PERSPECTIVE*
      Cost:  software $8000, SGI workstation $18,000-$24,000.
      Also available:  a translator program to convert the software database
format into AutoCAD format.  If you have AutoCAD, you can use your 80386/80486
computer instead of the SGI workstation for output.  In this case, you just
buy the $8000 software.

******************************************************************************

      B.  Eutectic Electronics Corp.
          Department A01
          8608 Jersey Court
          Raleigh, NC  27613
          (919) 782-3000      FAX (919) 782-9913
          TINS 15:  xli (1992).

(1)   80386/80486-based system with color VGA monitor.

      Consists of a vector graphics processor, a special color vector graphics
screen, and a special digitizing tablet with mouse.  Software package contains
tracing routines, color editors, and output routines to calculate volumes and
areas.
      Input:  stack of prints *WHICH MUST BE TRACED* on the special tablet--no
provision for in-microscope scanning.
      Output:  outlines of reconstruction only (no shading).  *TRUE
PERSPECTIVE*
      Cost:  installed yourself, you provide the base computer, $8000 for the
3 special hardware pieces and the software.

******************************************************************************

III.  Literature search.  I searched Biological Abstracts Volume 93 (1992)
under keyword RECONSTRUCT* for articles with 3-DIMENSIONAL in the title or
abstract.  This is *LONG* and perhaps only of interest to biologists, so
if you wish, you may hit "n" now :)


      A.  Volumetric methods.

(1)   Takersley, R.A., and R.V. Dimock (1992).  Quantitative analysis of the
structure and function of the marsupial gills of the freshwater mussel
Anodonta cataracta.  Biol. Bull. 182:  145-154.

      Examined and quantified volumetric changes in gill water tubes.
      Serial frontal sections @ 10 microns, photograph & align every 5th
section.
      Digitize with Summagraphics digitizer (25 sections/sample) on Zenith
Z-386SX computer.
      Analyze with PC3D (Jandell Scientific) to determine volumes.
      Final reconstruction was 1.25 mm-thick slice of gill.
      Output:  *NO PICTURES SHOWN*

******************************************************************************

      B.  Rotationally-symmetric or repeating structures.

(1)   Baker, T.S., Newcomb, W.W., Olson, N.H., Cowsert, L.M., Olson, C., and
J.C. Brown (1991).  Structures of bovine and human papillomaviruses:  Analysis
by cryoelectron microscopy and three-dimensional image reconstruction. 
Biophys. J. 60:  1455-1456.

      Digitized images of whole-mount EM spreads of virus particles.
      Technique of common lines and Fourier-Bessel transformations.
      *ONLY WORKS ON ROTATIONALLY-SYMMETRIC PARTICLES*
      Used VAX/VMS 8550 with custom FORTRAN-77 programs from:

                 Fuller, S.D. (1987).  The T=4 envelope of Sindbis
           virus is organized by interactions with a complementary
           T=3 capsid.  Cell 48:  923-934.

      Output:  Grey-scaled photographs of solids.

(2)   Dokland, T., Lindqvist, B.H., and S.D. Fuller (1992).  Image
reconstruction from cryoelectron micrographs reveals the morphopoietic
mechanism in the P2-P4 bacteriophage system.  EMBO J. 11::  839-846.

      Same techniques, different virus.

(3)   Frank, J., Penczek, P., Grassucci, R., and S. Srivastava (1991). 
Three-dimensional reconstruction of the 70S Escherichia coli ribosome in ice: 
The distribution of ribosomal RNA.  J. Cell Biol. 115:  597-606.

      Digitize micrographs on flatbed microdensitometer (PDS 1010A,
Perkin-Elmer Corp., Norwalk, CT).
      Align on SGI workstation (Silicon Graphics, Mountain View, CA).
      3-D contours from SGI workstation using INSIGHT software (Biosym
Technologies, San Diego, CA).
      Same techniques, different hardware and software.

(4)   Zedzik, J., O"fverstedt, L.-G., and U. Skoglund (1992).  Three-
dimensional reconstruction of bovine intradural spinal root myelin by electron
microscope tomography.  J. Neurosci. Res. 31:  387-393.

      Micrographs scanned by Optronics P-1000 optical drum scanner.
      VAX 11/750 and Convex C210 computer analysis of repeating structures.
      Output:  Balsa wood models made from level curve printer output.

******************************************************************************

      C.  GLOM program.

(1)   Faraj, A.H., Morley, A.R., and S. Coleman (1991).  Three-dimensional
reconstruction of juxtaglomerular apparatus (JGA) in five-sixth nephrectomized
rats.  APMIS 99:  1129-1141.

      1 micron sections/toluidine blue stain/each 5th section taken for
reconstruction.
      Photograph @ 250X, enlarge to 16.5x21.5 cm, hand-trace contours in
different colored inks on the enlargements.
      GLOM program to digitize tracings with mouse, reconstruct, rotate,
translate.  Program described in:

                  Coleman, S.Y. (1986).  Statistical computer
            graphics and morphometry in 3-dimensional reconstruction
            of serial sections of glomerulus.  Ph.D. thesis, University
            of Newcastle-Upon-Tyne.

      *COMPUTER TYPE/ARCHITECTURE/MPU NOT STATED*
      Output:  Produces only level curves; no removal of hidden lines, etc. 
Different structures printed in 4 colors on dot-matrix printer.

(2)   Faraj, A.H., Lindop, G.B.M., Morley, A.R., and S. Coleman (1992). 
Three-dimensional reconstruction of human juxtaglomerular apparatus (JGA). 
APMIS 100:  29-38.

      Same techniques as above.

******************************************************************************

      D.  Ultrasound imaging.

(1)   Rosenfield, K., Losordo, D.W., Ramaswamy, K., Pastore, J.O., Langevin,
R.E., Razvi, S., Kosowsky, B.D., and J.M. Isner (1991).  Three-dimensional
reconstruction of human coronary and peripheral arteries from images recorded
during two-dimensional intravascular ultrasound examination.  Circulation 84: 
1938-1956.

      Ultrasound images of arteries recorded on VHS video tape.
      Digitized on 80386-PC/AT with D/A converter (ImageComm Systems, Santa
Clara, CA).
      Images processed with SciView workstation (ImageComm Systems) using
OMNIVIEW software (Pura Labs, Brea, CA).
      Specific for dealing with grey-scaled image analysis.
      *USED CATHETER BORE FOR ALIGNMENT*
      Output:  3-D grey-scaled images.

******************************************************************************

      E.  Automatic section alignment.

(1)   Hibbard, L.S., Arnicar-Sulze, T.L., Dovey-Hartman, B.J., and R.B. Page
(1992).  Computed alignment of dissimilar images for three-dimensional
reconstructions.  J. Neurosci. Methods 41:  133-152.

      60-80 nm EM sections, to span total distance of 100 microns.
      4 out of every 10 sections used for processing.
      Digitized on Optronics P-1000 scanning microdensitometer @ 100 micron
resolution.
      DIANA image analysis system on DEC VAX computers/workstations (J.
Neurosci. Methods 26: 55-74 (1988)).
      3-D graphics using either GRAMPS (Comput. Graphics 15:  133-141 (1981))
            or MOVIE.BYU (custom software at BYU)
            or author's (TLS) custom program for Evans & Sutherland PS390
graphics system.
      Output:  grey-scaled solid images.
      *GOOD THEORY PAPER*

******************************************************************************

      F.  Hand techniques.

(1)   Senoh, K., and J. Naito (1991).  A WGA-HRP study of the fiber
arrangement in the cat optic radiation:  A demonstration via three-dimensional
reconstruction.  Exp. Brain Res. 87:  473-483.

      Trace section outlines on clear animation cels.
      Stack cels, each separated by distance proportional to thickness.
      Hang a blank cel in front of the stack.
      Look through stack and trace outlines in perspective.

(2)   Pignot-Paintrad, I., and C. Bressac (1992).  Rapid three-dimensional
reconstruction at the light microscopic level and a technique for re-embedding
the same semithin sections for electron microscopic examination.  Biotech.
Histochem.  67:  55-57.

      Hand reconstruction of plastic sections temporarily mounted (drawing
tube on microscope).
      When you find out where you are, liberate desired sections, reembed, and
thin section.

******************************************************************************

END OF SUMMARY.
-- 
Richard F. Drushel ****** Ph.D. in Developmental Biology as of 4:45 PM 9211.20
rfd@po.cwru.edu ** Cleveland FreeNet ** Co-Sysop, Coleco ADAM Forum ** Go Z80!
.............................................................................
After 13 years of CWRU, gainfully employed making bologna slices of sea-slugs!