,
the coupling neighborhood 
,
the threshold 
,
the power n of the adaptive tolerance mapping function, and the
tolerance range variables 
and 
.
We show results of the G-LEGION image segmentation algorithm on 2D and
volume CT and MRI medical datasets of the human head. The user provides
six input parameters: the potential neighborhood ,
the coupling neighborhood ,
the threshold ,
the power n of the adaptive tolerance mapping function, and the
tolerance range variables
and .
Fig. 5a is a CT image of a
view of a horizontal section extracted at the nasal level of a human head.
The white areas are bone and grey areas are soft tissue. Fig.
5b shows results of the G-LEGION algorithm using an 8-neighborhood
,
a 24-neighborhood ,
=
7.5, n = 1,
= 3, and
= 32. In this as well as all following figures, we use a color map to indicate
the results of segmentation, where each color indicates a distinct segment.
The color map in Fig. 5b contains
105 segmented regions, and the background corresponds to black scattered
areas. Due to limited color discriminability of the printer, spatially
separate regions that appear to have the same color are in fact different
segmented regions. Whereas a global thresholding method would collect all
bony structures into a single region and would have difficulty distinguishing
the soft tissue, our algorithm is able to segment both. Furthermore, each
spatially distinct bony structure or soft tissue area is separately labeled,
as well as surrounding nasal cavities and passages.
MRI image data have the advantage of being able to display soft tissue
structures better than CT image data. They are also more difficult to segment
because objects are usually nonhomogeneous and adjacent objects may have
a low contrast. For example, see the MRI image shown in Fig.
6a, which is a mid-sagittal section of the head showing many structures,
including brain, vertebrae, oral cavity, extracranial tissue, bone marrow,
and muscle. Fig. 6b shows the
result of segmentation by G-LEGION using an 8-neighborhood ,
a 24-neighborhood ,
=
3.5, n = 3,
= 1, and
= 95. As shown in the color map of Fig.
6b, the MRI image is segmented into 70 regions, plus a background which
is again indicated by black scattered areas. The entire brain is segmented
as a single region (colored in yellow). Other significant segments include
the extracranial tissue (colored in red), the chin and the neck parts,
the vertebrae, and so on.
As discussed before, each parameter has an effect on the number and
sizes of segmented regions. An understanding of these effects is helpful
for the user to choose appropriate parameter values in order to achieve
desired segmentation. In Figs. 7-9,
we illustrate the effects of various parameter values on results of segmentation.
First, we vary the size of the coupling neighborhood. Figs.
7a-b differ from Fig. 6b
in only the size of ,
where 8-neighborhood and 4-neighborhood are used respectively, and our
algorithm segmented 309 and 599 regions, respectively. These results show
that when
is reduced, region expansion is more restrictive, and regions become smaller
and more numerous. This is because a smaller coupling neighborhood results
in more restricted pixel paths during the recruiting step of the algorithm.
This effect is clearly demonstrated, for example, in the fragmented regions
representing the brain and extracranial tissue in Figs.
7a and 7b. The size of the
potential neighborhood and the threshold
are used in the leader identification step to determine which pixels lie
in a relatively homogeneous region of an image and are thus qualified as
leaders. When the homogeneity criterion is relaxed, more leaders will be
generated. On the other hand, when the size of
decreases, a pixel more easily becomes a leader because fewer similar pixels
are needed in leader identification. Using the same parameter settings
of Fig. 6b, we show results of
changing
from an 8-neighborhood to a 24-neighborhood in Fig.
7c and 4-neighborhood in Fig.
7d. Fig. 7c contains 15 segments,
and Fig. 7d contains 318 segments,
consistent with our analysis. In Fig.
7c, the area between the brain and the extracranial tissue, which contains
fragmented bone marrows in Fig. 6b,
is collected into the background, while Fig.
7d due to the smaller
shows more fragments within the area than Fig.
6b. Changing the value of
has a similar effect. Figs. 7e-f
show results using the same parameters as for Fig.
6b, except for
= 7.5 in Fig. 7e and
= 2.5 in Fig. 7f. The color map
in Fig. 7e contains 10 segments
and in Fig. 7f contains 485 segments.
The roles of the adaptive similarity measure and its parameters are
illustrated in Figs. 8 and 9.
Fig. 8a displays an MRI image
of a horizontal section of a human head at the eye level, showing the structures
of brain, two eyeballs, the ventricle at the center, extracranial tissue,
and scattered bone marrow. To apply our adaptive similarity measure, pixel
intensities are first mapped to tolerance values, which are then applied
to the difference between a neighboring pixel pair. As the power n
increases, relatively larger tolerance values are assigned to brighter
pixels, which means that brighter pixels have relatively larger ranges
of grouping. This is desirable if brighter pixels represent more interesting
structures, as is usually the case for sampled medical images. In other
words, a brighter pixel groups with a larger range of pixels than does
a darker one. Figs. 8b-8d
show segmentation results using the cubic, square, and linear tolerance
functions, respectively, on the MRI image of Fig.
8a. In this case,
and
are both set to 8-neighborhood,
= 4.5,
= 4, and
= 18. The color maps in Figs. 8b-8d
contain 288, 239, and 173 regions, respectively. The three color maps show
that areas with bright pixels are consistently segmented, such as the white
structures behind the eyes, the brain, and the brighter parts of the extracranial
tissue. Also consistently segmented are the two eyeballs. In the leader
identification step of the G-LEGION algorithm, the tolerance function has
a similar effect in determining leaders as do
and .
In the recruiting step, the tolerance function affects region growth because
it specifies which pixels in
are on pixel paths. Region expansion depends on how fast pixel intensities
change within a region. The boundaries between regions occur where intensity
changes are too large. When the pixel intensities within a region change
substantially, a tolerance function with a higher n usually tends
to break the region apart. For example, the brain is segmented into many
parts in Fig. 8b, whereas it
remains a single region in Figs.
8c and 8d. In Fig.
8d, however, boundary details of the brain are lost. Segmentation of
the extracranial tissue shows the same effect. Thus, an appropriate choice
of the tolerance function depends upon the intensity variation characteristics
of target objects.
The user can also control the grouping for darker and brighter pixels
by selecting
and .
When either parameter is changed, the tolerance function remaps all intensities
to a new range of tolerance values. When
is increased, tolerance values will increase more quickly for darker pixels.
A similar effect holds for brighter pixels when
is increased; moreover, the effect is more dramatic. In Fig.
9, we show segmentation results using a cubic tolerance function, clamping
to 1, and varying
from 80 in Fig. 9a, to 40 in
Fig. 9b and 20 in Fig.
9c. The remaining parameters are the same as in Fig.
8. The results in Fig. 9a-c
contain 278, 375, and 459 regions, respectively. The white areas behind
the eyes, the bright areas that correspond to the brain and the extracranial
tissue (see Fig. 8a) are grouped
more fully in Fig. 9a than in
Figs. 9b and 9c.
Figs. 9 and 10
also illustrate how our algorithm handles the various types of noise artifacts
commonly found in sampled image data. Fig.
8a contains "salt and pepper" noise in the areas surrounding
the head, as well as arbitrary sized noisy areas caused by too small a
sampling rate compared with the sizes of the structures being imaged, such
as the nasal area between the two eyes. Fig.
9 shows that these noise artifacts are collected into the background
and do not affect segmentation of other regions. To further illustrate
the robustness of our algorithm to noise artifacts, we reduce the resolution
of the image of Fig. 8a by half
by throwing away every other pixel value. As shown in Fig.
10a, this magnifies the noise artifacts, especially near the boundaries
of objects. The result of segmenting Fig.
10a is shown in Fig. 10b
using a 24-neighborhood ,
an 8-neighborhood ,
=
11.5, n = 3,
= 1 and
= 150. The segmentation result contains 131 regions. The algorithm is able
to segment the brain, the areas behind the eyes, and the extracranial tissue
while placing a large number of noisy areas into the background.
Figure 11 shows segmentation results on a number of 256x256 MRI images with different sections. Parameters have been chosen in order to extract various meaningful structures. In Fig. 11b, significant regions that are segmented include the cortex, the cerebellum, and the extracranial tissue, as well as two ear segments. In Fig. 11d, the entire brain is segmented as a region, so are the extracranial tissue and the neck muscle. In Fig. 11f, the cortex and the cerebellum are well separated. Other interesting regions that are segmented include the chin part, and the extracranial tissue. In Fig. 11h, again the cortex and the cerebellum are well segmented. In addition, the brainstem and the ventricle lying at the center of the brain are correctly separated. Other structures are also well segmented as in Fig. 11f.
As discussed before, our G-LEGION algorithm easily extends to segment
volume data by expanding 2D neighborhoods to 3D. To illustrate 3D segmentation,
we show the result of segmenting an entire MRI volume dataset, from which
the image in Fig. 8a was obtained.
The volume dataset consists of 128 horizontal sections, and each section
consists of 256x256 pixels, with a total of 128x256x256 pixels. The dataset
was partitioned into four stacks along the vertical direction. From top
to bottom, stack 1 consists of sections 1-49, stack 2 sections 50-69, stack
3 sections 70-89, and stack 4 sections 90-128. We divide the entire dataset
to four stacks for the purpose of dividing total computing to different
stages, and for reflecting major anatomical shifts. The following parameters
are common for all stacks:
= 26,
is half the size of ,
a square tolerance function, and
= 1. In addition,
= 26 for stack 1, and 6 for the remaining stacks;
= 10 for stack 1, 25 for stack 2, 30 for stack 3, and 35 for stack 4. The
parameters are chosen to extract the 3D brain. Figs.
12a and 12c show two views
of the segmented 3D brain using a volume rendering software developed in
[13]. Fig.
12a displays a top view with the front of the brain facing downward.
Fig. 12c displays a side view
of the segmented 3D brain, with the front of the brain facing leftward.
To put our results in perspective, Figs.
12b and 12d show the corresponding
views of manual segmentation of the same volume dataset by a human technician
(more discussions in Sect. VI.
As shown in Fig. 12, the results
of manual segmentation fit well with the prototype of our anatomical knowledge.
On the other hand, as to be discussed in Sect.
VI, the results of our algorithm can better reflect details of a specific
dataset.
We have performed many other tasks of medical image segmentation using our algorithm, including tasks such as segmenting blood vessels in other 3D volume MRI datasets and segmenting sinus cavities from the Visible Human Dataset [1]. The segmentation results are comparable with those illustrated above. We note that our segmentation results are usually robust to considerable parameter variations, that is, major segments are not sensitive to these variations.
Determining appropriate algorithm parameters is not as difficult as
it may appear, because each parameter has an intuitive meaning and its
effect on segmentation is fairly predictable. The method we use to set
the parameters is an incremental one where each parameter is set individually
while holding the others constant. First, target structures in the dataset
are determined for segmentation. Usually these structures correspond to
bright and relatively homogeneous regions within images. To reduce the
number of extraneous regions in segmentation,
and
should both be set large initially. They essentially act as filters for
removing small and nontarget regions. A cubic tolerance function should
be used first, in order to identify bright regions. To limit expansion
into extraneous regions,
can be chosen small initially. The most tedious task is to choose
and ,
which requires some trial-and-error. Again, with some experience choosing
these parameters is not very hard.
The G-LEGION software is written in C and is compiled to run on both the SGI and HP platforms. The user is able to set each of the six algorithm parameters through a graphical user interface (GUI) written in Motif. The software displays a 3D volume with integer tags, so that the user can select one particular segmented 3D region for viewing purposes. The latter utility is also written in C and Motif for the GUI.