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.
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.
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.
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)