Lispix Home | Superblobber Documentation
This paper was first published in the Journal of Computer Assisted Microscopy, 1(4):307-329, 1989. The research was sponsored by the U.S. Government and is not subject to copyright. (The Surface and Microanalysis Science Division was the Gas and Particulate Science Division when the paper was published.)
The Blob Splitting Algorithm (BSA), developed for segmenting digital images (Bright 1987a), finds simple objects in micrographs that have troublesome backgrounds and divides complex objects into reasonable parts. Locating objects can be difficult when they have a wide range of sizes, shapes, or fuzzy edges, and when they are not clearly separated or do not stand out well from the background.
More conventional means of segmentation that have been unsatisfactory
in many of these cases are to: a. use a single threshold setting
(Russ 1986), b. enhance the edges by using the gradient or derivative
of the brightness of the image, or c. use gated filters such as
the top hat filter (Bright and Steel 1987). Some other methods
for resolving brighter features while still selecting dimmer ones
include manual selection of parameters (McMillan 1987), use of
specific combinations of features or texture (Vistnes 1988), use
of a combination of large gradient and low brightness (Dahl 1986)
or use of a threshold setting for each of three planes of a color
image (Wermser 1984).
The BSA works without any preprocessing, filtering, or transforming
of the images. It is not sensitive to object width or even to
object size or shape, as is a more complex algorithm described
in the mathematical morphology literature (Skolnick 1986). Although
the general scheme of this algorithm is not new (Kirsch 1971,
Agui 1981), the implementations and specific applications to microscope
images described here are new.
Description of Blob Splitting Algorithm for finding objects.
Objects are selected from blobs, or contiguous groups of pixels,
that are formed from an image by setting an upper and a lower
intensity threshold. Only if the intensity for a pixel is within
the threshold range, is that pixel part of a blob. If a blob has
a sufficient number of pixels, then it may be selected as an object.
The sizes of the blobs and thus the number and sizes of objects
are very much dependent on the threshold settings.
The BSA can be thought of in terms of raising the water level
in hilly country. The water level represents the upper threshold
setting, and the hills represent the blobs. The lower threshold
setting includes the lowest possible water level. Hills will shrink,
sometimes subdivide or split, and disappear as the water level
rises. Objects are defined to be islands that later, with rising
water level, do not split into large pieces which are themselves
islands, but only shrink and disappear. They may perhaps shed
small clumps of land in the process, but these clumps can be ignored
by setting a minimum acceptable area for islands. In some sense,
the algorithm finds all individual hills while discounting size,
height (relative to background), steepness, altitude (or absolute
height) and shape.
The algorithm defines single objects as blobs that split from
a parent blob, but that then do not split again. The algorithm
is therefore called the "blob splitting algorithm",
or BSA. As an illustration of this, Fig. 1 shows an image where all six peaks
cannot be isolated by any single threshold setting. Fig. 2 is a mesh plot where the height
of the mesh represents intensity. Fig. 3 is a contour plot, showing isophotes
or lines of constant intensity (Meinzer 1984) taken at equal intervals.
Setting any threshold for Fig. 1, or taking a horizontal slice
through Fig. 2, or choosing a particular isophote in Fig. 3 cannot
select all six peaks a-f. For example, consider the isophote going
near peak c in Fig. 3 and encircling peak d. For this contour,
peak d is resolved, peaks a, b and c are lumped together, and
peaks e and f are not detected.
The behavior of the algorithm is better visualized by the series
of binary images in Figs. 4-1 through Figs. 4-20 which show
results of twenty different intensity threshold settings in increasing
order applied to the image in Fig. 1. The thresholds used for
these figures were chosen to show where a blob either splits from
its parent blob (see arrows in 2, 7 and 16) or where a blob disappears
altogether (arrows in 4, 5, 9, 12, 18 and 20). 'Blob' here denotes
any discrete object such as the white shapes in Fig. 4. In this
example, even that dot would be a candidate object, since Fig.
1 is computer generated and has no background noise.
The algorithm would operate on the image in Fig.1 as follows,
where the thresholds refer to Fig. 4. At threshold 1, one blob
includes all five peaks. At threshold 2, the blob with peak f (Fig.
3) has just split from the parent blob, because threshold 2 is
slightly greater than the minimum value of the ridge or watershed
between peak f and peak c.
Blobs will now be referred to by the letters that name the corresponding
peaks. From thresholds 2 to 5, blob f gradually disappears - threshold
5 is just equal to the value at the top of peak f. Blob f
never splits, so it is recorded by the algorithm as a single object.
Blob e splits from the parent blob between thresholds 2 and 3,
and then disappears as did blob f. Blob c does not split from
blob a-b until threshold 11, where it has shrunk to a size that
looks smaller than it seemingly should in order to represent the
outline of peak c (Fig. 1). This is because peak c lies on the
shoulders of peaks a and b and the threshold to resolve or separate
peak c from peak a has to be one intensity level higher than the
minimum height of the ridge between peaks a and c. The maximal
region of peak c has been found, although the visual extent of
the peak has not. This behavior is characteristic of the BSA when
it finds poorly separated peaks or smaller peaks on or near a
larger peak.
Note that the a-b blob is not considered an object, although it
is a candidate for one up to threshold 12, because it splits into two
objects at threshold 16. As with peak c, each outline is well
within the brighter area that might be considered as skirts of
each peak. This behavior can be noted in several of the examples
that follow.
Implementation of The Blob Splitting Algorithm
We implement the BSA by representing blobs as lists (using LISP,
see Bright 1987b). The algorithm uses two lists of blobs - a working
list and an object list. Initially, the object list is empty and
the working list consists of the image-filling blob resulting
from the minimum threshold setting (usually zero). The algorithm
cycles through all the following steps until the working list
is empty and then it returns the object list as the result.
The BSA is often the first step in analyzing an image. The
list of objects may be culled in a subsequent step, usually on
the basis of brightness, size, shape or position.
The algorithm has been used in this laboratory in the analysis
of several different types of images, including electron diffraction
patterns taken on an analytical electron microscope in the diffraction
mode (Bright and Steel 1988) and micrographs of particles taken
with electron and ion microscopes (Bright 1987a).
Fig.
5a is another electron diffraction pattern with a wide range
of spot and background intensities. Fig. 5b shows the spots as located by
the algorithm. Note that the BSA locates spots very close to the
beam center as well as spots near the periphery of the image.
Fig.
6a shows an electron diffraction pattern that was digitized
from a negative using a video camera and a light table. The top
hat filter (Bright and Steel 1987) can select the diffraction
spots if used twice - once for each size separately (Bright 1988).
The diameters of the larger spots are greater than the separations
of the smaller spots, so the top hat filter will not work for
both sizes at once. The BSA selects both sizes of spots at once,
as shown by the rectangles in Fig. 6b. Once the spots are selected,
the spot centers can be determined more precisely as shown in
the next example.
For the analysis of electron diffraction patterns such as Fig.
7a, the exact location of the spot centers are desired. The
BSA will isolate each spot as a blob, but more calculation is
needed to determine the spot centers. For example, Fig. 7b or Fig. 6b show the blob locations
in terms of the bounding rectangles, which are not exactly centered
on the spots. This is because the BSA selects a bounding rectangle
that includes a large portion of the skirts for these spots, and
these skirts are asymmetric. Once the spots are isolated with
one spot to a rectangle, then the centers can be located more
accurately. A good method to calculate the center location of
a diffraction spot is to select the intensity weighted average,
over the bounding rectangle, of pixels positions using only a
fraction of the brightest pixels. If this is done, the spot centers
are located as shown by the bright spots and concentric circles
in Fig. 7b.
Fig.
8a shows an electron diffraction pattern with pronounced rings.
Determining the beam center precisely is helpful for measurement
of the ring diameters (Fig. 18 in Bright 1987b), and identification
of portions of the rings is helpful in determining the beam center.
Selecting the arcs by thresholding is difficult because of interference
from the intense diffraction spots and from the bright diffuse
background. Fig.
8b shows the outlines that the BSA found for a large blob
area or Amin. Arc like parts portions of the rings have been isolated.
Other blobs are due to background noise or to patterns associated
with the beam stop. The unwanted blobs may be culled on the basis
of their location and shape.
Fig.
9a is a visible light micrograph of fluorescein spheres approximately
2 µm in diameter. The locations of the spheres as found
by the BSA are shown by the rectangles which, as in Fig. 6b and
fig. 7b, might include more area than the spheres themselves.
The locations were refined (see outlines in Fig. 9b) much as were the spot locations
in Fig. 7b. At first glance, a single threshold setting would
seem adequate to isolate the spheres in Fig. 9a; however, Figs.
10b, c and d show the results for three threshold settings,
none of which is adequate to isolate the spheres. Another simple
and less satisfactory method is to use a minimum filter to generate
a 'background' image (Bright 1987b), subtract this image from
the original, and segment the image into blobs using one choice
of threshold settings. The result of applying a minimum filter
to Fig. 9a with a kernel larger than the sphere diameter is shown
in Fig.
11a. This image has low intensity voids, rendering it unsuitable
as a background image because background images should be featureless
and smoothly varying. The reason for the voids is seen on inspection
of Fig.
11b. There are small spots of low intensity, perhaps due to
dust on the slide or camera optics. It might be possible to first
filter out the small dark dust spots and lines with a median filter
using a kernel that is larger than the width of the largest dust
particle but smaller than the smallest fluorescein sphere. The
minimum filter could then be applied to the resulting image, which
would in turn be subtracted from the original. At this point,
several image processing steps are involved, two of which require
careful selection of a size parameter. It is more convenient just
to use the BSA, retaining anything with an area 10 pixels or greater.
Fig.
12 is an aluminum image of inclusions in steel, taken with
an ion microscope and shown along with the outlines of the inclusions
found by the BSA. Integrated signal intensities for each inclusion
were desired for further analysis. Signal strength covered such
a wide dynamic range that it was useful to run the BSA on the
logarithm of the aluminum signal, which is what is actually shown
in Fig. 12. The masks of the inclusions, shown by the outlines,
designated which pixels of the original image to include in the
intensity measurements. The intense inclusions are always outlined,
although the outlines are sometimes hidden in the figure. Sometimes
skirts or nearby dim inclusions are outlined with an intense inclusion
and sometimes not, but the performance of the BSA was judged satisfactory
for the analysis desired. Since objects can be of any shape, they
can have holes. The BSA indicates that few of the two dimensional
sections of the dimmer inclusions have very small holes.
Barium particles
Fig.
13a shows a barium image of particles taken with the ion microscope.
Figure
13b shows the results of the BSA, where most of the particles
are resolved and where even the dim particles are located. The
gradient operator is often used to enhance edges if they are sufficiently
sharp. This is not the case for some of the edges in Fig. 13a,
as seen by comparing the gradient image in Fig. 13c with Fig. 13b. The BSA chose
edges differently from what one might expect from the gradient
image. This behavior of the BSA occurs often for images of objects
with diffuse edges. Which edges are correct is, of course, open
to question.
Choices for Amin illustrated with TEM of
complex particle
The value chosen for the acceptable minimum area for objects,
Amin, affects the behavior of the BSA as shown by the following
examples of subdividing the complex particle shown in Fig. 14a.
Fig.
14b shows the regions chosen by the BSA for Amin = 500 pixels,
the area equal to five of the small grid squares in Fig. 14c. A number of fractal-like or
spongy blobs that look random in nature have been selected from
the background. These blobs are due to noise fluctuations because
the background is not smooth. The BSA is sensitive to any brightness
variation because it uses no information on the absolute brightness
or shape of the desired regions. If the background were noise
free, as in Figs. 1-4, then there would be no blobs in the background.
To show that the background blobs can be explained by random noise,
the BSA was run on an image of random numbers with an intensity
distribution close to the background intensity distribution of
Fig. 14b, i.e. that for pixels in the lower left 100 x 100 pixel
square of Fig. 14a (see grid in Fig. 14c for size). The light
gray curve in Fig. 14c is the intensity distribution of these
pixels, and the white curve the corresponding distribution for
the same area of the simulated random image. The blobs chosen
from the random image by the BSA are shown in Fig. 14d, rendered in various shades of
gray to help distinguish blobs that almost touch. These blobs
look like the background blobs of Fig. 14b, which presumably are
due to instrumental noise.
For this example, the particle blobs can be distinguished from
the background blobs by the thresholds at which they were taken.
The histogram of all of the blobs vs. threshold, Fig. 15, shows that there are two distinct
groups of blobs. Group A are particle blobs and group B, background
blobs. Only the group A blobs from Fig. 14b are outlined in Fig.16a.
The blobs in Fig.
16a appear reasonable, thus 500 pixels is a workable value
for Amin. This value is not critical --
very large changes in Amin are necessary to produce significantly
different behavior of the BSA for this image. For example, Fig.
16b shows results for Amin = 5000 pixels. Because Amin is
so large, there are only three regions or blobs. Essentially the
same areas have been outlined as in Fig. 16a, but they have not
been subdivided.
Fig.
16c shows results for Amin = 50 pixels. Because Amin is so
small, some of the regions have been fragmented into very small
blobs outlining the most dense (most bright in figure) areas.
This segmentation of the image may be desirable for other types
of analysis, but was not desired here. The background has many
blobs, all smaller than the background blobs of Fig. 14b, as expected.
These background blobs can be rejected on the basis of their thresholds,
as was done to get Fig. 16a.
When images can be displayed satisfactorily using fewer than 256
gray levels (fewer than 256 steps from black to white), the BSA
will also work satisfactorily, and in considerably less time,
because processing is required on only a fraction of the original
number of gray levels. Figs. 17a - 17c are analogous to Figs.
16a-16c, except that the image was stored with 32 gray levels
rather than 256. The image with the 32 gray levels is visually
indistinguishable from the original. Fig. 17a, with Amin=500 pixels, shows
regions very similar to Fig. 16a, which were found in one sixth
the computer time. Because Amin for Fig.
16b and 17b
is 5000 pixels, the blobs are not subdivided often, and both BSA
calculations took fairly little time. The blobs in Fig. 17c, with
Amin = 50 pixels, took one fortieth the time to find as those
in Fig. 16c, due to the decrease in number both of gray levels
and of blobs.
In Fig. 17c, the particle regions are reasonable and not subdivided
as are those in Fig. 16c. Similarly the background has not been
split into so many regions. All this is because compressing the
intensity dynamic range into 32 gray levels has obliterated much
of the smaller intensity variations due to noise or to sample
thickness.
Conclusions
An algorithm is presented for locating objects in digital images.
The blob splitting algorithm or BSA uses relationships of blobs
taken at different threshold settings. The BSA is not tuned to
any particular object shape or size. Although computationally
intensive, it is robust and is used routinely in our laboratory.
Examples of its use include locating particles in TEM and ion
microscope images, locating spots in electron diffraction patterns,
and finding regions of interest in complex particles.
References
Bright, D.S., "Usefulness of Various Computer Algorithms
for Locating Spots and Arrays in Electron Diffraction Patterns",
Microbeam Analysis pp. 25-32 (1980).
Bright, D.S., "An Object Finder Based on Multiple Thresholds,
Connectivity and Internal Structure", Microbeam Analysis
(1987a), pp. 290-292.
Bright, D.S., "A Lisp-based Image Analysis System With Applications
to Microscopy", J. Microscopy 148(pt.1):51-87 (1987b).
Bright, D.S. and Steel,E.B., "Automated Extraction of Regular
Spot Arrays from Electron Diffraction Images", J. Microscopy
150(3):167-180 (1988).
Bright, D.S., and Steel, E.B., "Two Dimensional Top Hat Filter
for Extracting Spots and Spheres from Images", J. Microscopy
146:191-200 (1987).
Bright, D.S. and E. B. Steel, "Automated Method for Analyzing
Images Containing Electron Diffraction Spots", Microbeam
Analysis (1985), pp. 163-165.
Dahl, O. and Nielsen, L. "Ash Line Control", pp. 75-79
in Digital Image Processing in Industrial Applications Proceedings
of the First IFAC Workshop, Espoo, Finland, 10-12 June, 1986,
M. Ollus Ed., Permagon Press, 1987.
R. A. Kirsch, "Computer Determination of the Constituent
Structure of Biological Images," Computers and Biomedical
Research 4:315-328 (1971)
P. J. McMillan et.al., "Minima equalization: a useful strategy
in automatic processing of microscopic images", J. Microsc.
148(3):156-262 (1987)
H. P. Meinzer and U. Engelmann, "The interpreter PIC: A tool
in the field of image processing," Med. Inform. 9(2):93-102(1984)
J. C. Russ, Practical Stereology, Plenum Press, New York, 1986,
pp.80,81
M. M. Skolnick, "Application of Morphological Transformations
to the Analysis of Two-Dimensional Electrophoretic Gels of Biological
Materials,"Computer Vision, Graphics and Image Processing
35:306-332 (1986)
Vistnes, R. "Texture Models and Image Measures for Segmentation",
pp. 1005-1015 in Proceedings: Image Understanding Workshop, Vol
II, DARPA Image Understanding Workshop, Cambridge Mass. 1988.
Wang, S., Velasco, F.R.D., Wu, A. Yu. and Rosenfeld, A. "Relative
Effectiveness of Selected Texture Primitive Statistics for Texture
Discrimination", IEEE Trans. Sys., Man and Cyb. SMC-11(5):360-370
(1981)
D. Wermser, et. al., "Segmentation of blood smears by hierarchical
thresholding, "Computer vision, Graphics, and Image Processing"
25:151-168(1984)