Unit 5

Biomedical Image Segmentation

Introduction
• In the CAD environment, one of the roles of image processing
would be to detect the region of interest (ROI) for a given,
specific, screening or diagnostic application

• Once the ROIs have been detected, the subsequent tasks

would relate to the characterization of the regions and their
classification into one of several categories
A few examples of ROIs in different biomedical imaging and
image analysis applications are listed below:

• Cells in cervical-smear test images

• Calcifications in mammograms
• Tumors and masses in mammograms
• The pectoral muscle in mammograms
• The breast outline or skin-air boundary in mammograms
• The fibroglandular disc in mammograms
• The air-way tree in lungs
• The arterial tree in lungs
• The arterial tree of the left ventricle, and constricted parts
of the same due to plaque development
Segmentation is the process that divides an image into its
constituent parts, objects, or ROIs

Segmentation is an essential step before the description,

recognition, or classification of an image or its constituents

Two major approaches to image segmentation are based on

the detection of the following characteristics

Discontinuity - Abrupt changes in gray level (corresponding

to edges) are detected
Similarity - Homogeneous parts are detected, based on
graylevel thresholding, region growing and region
splitting/merging
Depending upon the nature of the images and the ROIs, we
may attempt to detect the edges of the ROIs if distinct edges
are present OR we may attempt to grow regions to
approximate the ROIs

It should be borne in mind that, in some cases, an ROI may

be composed of several disjoint component areas
For example, a tumor that has metastasized into neighboring
regions and calcifications in a cluster

Edges that are detected may include disconnected parts that

may have to be matched and joined
Thresholding and Binarization
If the gray levels of the objects of interest in an image are known from
prior knowledge, or can be determined from the histogram of the given
image, the image may be thresholded to detect the features of interest
and reject other details

For example, if it is known that the objects of interest in the image have
gray-level values greater than L1 we could create a binary image for
display as

() if f (m, n) < Li (5.1)

g(m, n) - { 255 if f (m, n) > Li '
where f(m, n) is the original image; g(m, n) is the thresholded image to be
displayed; and the display range is [0,255]
 Example: Figure5.1 a shows a
TEM image of a ligament
sample demonstrating
collagen fibers in crosssection

~l. • ~.._ a~... •

t,t,.tf§
:. :
•• •
........._,,.....,,,. .

FICuRE 6.1
~
I

~
.
•

•. ·-~ .
-..;
~~ ~•~
•
..-.s
~ .. .fl..
( b)
•

'!. ·--

(aJ TE~J ima~ of collagen fibers in a scer-Lissuc sample from a rabbit. u,garDt'nL
aL a ma~ni ficaLiou of appro.-cimaLcly x 30. 000. Scl' also Fi~urc 1.5. Inuu;c
cow-t.e'iy of C.13. Frank. Dl'pan.mcnt of Sur~Ery. lini"crsiLy of Cal~ary. Sec
Fi~rc 2.12 for the hi<1Lo~am of the ima~c. (b) Ima~l' in (a) lhr~holrll'd aL
i he ~ay ln·el of 1-SO.
Detection of Isolated Points and Lines

Isolated points may exist in images due to noise or due to the presence of
small particles in the image

The detection of isolated points is useful in noise removal and the

analysis of particles

The following convolution mask may be used to detect isolated points

1 1 1
1 8 1 (5.2)
1 · 1 1
The operation computes the difference between the current pixel at the
center of the mask and the average of its 8 connected neighbors

The result of the mask operation could be thresholded to detect isolated

pixels where the difference computed would be large

Straight lines or line segrnents oriented at 0°, 45°, 90°, and 135° may be
detected by using the following 3 x 3 convolution rnasks l8]:

1 1 1 1 1 2
2 2 2 1 2 1
-1 -1 -1 2 1 1

1 2 -1 2 1 1
1 2 -1 1 2 1 . (5.3)
1 2 -1 1 1 2
A line may be said to exist in the direction for which the corTesponding rnask
provides the largest response.
Edge Detection
One of the approaches to the detection of an ROI is to detect its edges

The HVS is particularly sensitive to edges and gradients

Some theories and experiments indicate that the detection of edges

plays an important role in the detection of objects and analysis of
scenes

The first-order derivatives and the Laplacian relate to the edges in the
image

Furthermore, we saw that these space-domain operators have

equivalent formulations in the frequency domain as highpass filters
with gain that is proportional to frequency in a linear or quadratic
manner
Convolution mask operators for edge detection
An edge is characterized by a large change in the gray level from one side to
the other, in a particular direction dependent upon the orientation of the
edge

Gradients or derivatives measure the rate of change, and hence could serve
as the basis for the development of methods for edge detection

The first derivatives in the x and y directions, approxirnated by the first

differences, are given by (using rnatrix notation)

f yb( rn, n) ~ J('m, n) f (rn • 1, n),

I

fxb(m,n)~f(rn,n) f(rn,n -1), (5.4)

where the additional subscript b indicates a backward difference operation

Because causality is usually not a rnatter of concern in image processing, the
differences rnay also be defined as
I

!y1 (m,n) ~ f(m+ 1,n) f(m,n),

I

fx. 1 (m, n) ~ f (rn, n + 1) f(m, n), (5.5)

where the additional subscript f indicates a forward-difference operation

A limitation of the operators as above is that they are based upon the
values of only two pixels; this makes the operators susceptible to noise or
spurious pixel values

A simple approach to design robust operators and reduce the sensitivity to

noise is to incorporate averaging over multiple measurements
Averaging the t\vo definitions of the derivatives in Equations 5.4 and 5.5, \Ve
get
I

!ya (m, n) ~ 0.5 lf (m + 1, n) - f(m - 1, n)],

I

fxa (m, n) ~ 0.5 lf (m, n + 1) f (m, n 1)], (5.6)

\vhere the additional subscript a indicates the inclusion of averaging.

The Prewitt operators take these considerations into account with the
following 3X3 masks for the horizontal and vertical derivatives Gx and Gy,
respectively

-1 0 1
Gx. : 1 0 1 . (5. 7)
1 0 1

1 1 1
0 0 0 (5.8)
1 1 1
The Prewitt operators use three differences across pairs of pixels in
three rows or columns around the pixel being processed
In order to accommodate the orientation of the edge, a vectorial form of
the gTadient could be cornposed as

G1(m, n) - G1x(rn, n) +j Gty(m, n),

LG1(m, n) - tan 1 (Gty(m, n)) , (5.9)

G1x(m,n)

where
(5.10)
and
(5.11)
If the magnitude is to be scaled for display or thresholded for the detec-
tion of edges, the square-root operation may be dropped, or the magnitude
approximated as IC fx I+ IG fy I in order to save cornputation.
 The Sobel operators are sirnilar to the Pre,vitt operators, but include larger
weights for the pixels in the row or column of the pixel being processed as

1 0 1
Gx.: 2 0 2 (5.12)
-1 0 1

-1 -2 -1
Cy: 0 0 0 (5.13)
1 2 1
Edges oriented at 45° and 135° may be detected by using rotated versions
of the masks as above. The Prewitt operators for the detection of diagonal
edges are
0 1 -1
G45° : 1 0 1 (5.14)
1 1 0
and

G 135• •. Il 1
1
1
0
01
(5.15)
0 1 ~J
Similar masks rnay be derived for the Sobel operator.
Observe that the sum of all of the weights in the masks above is zero

This indicates that the operation being performed is a derivative or gradient

operation, which leads to zero output values in areas of constant gray level
and the loss of intensity information
.,

The R.oberts operator uses 2 x 2 neighborhoods to cornpute cross-differences

as
(5 .16)

The masks are positioned with the upper-left elen1ent placed on the pixel
being processed. The absolute values of the results of the t\vo operators are
added to obtain the net gradient:

g(m,n)-lf(m+l,n+l) f('m,n)l+lf('m+l,n) f(rn,n+l)I, (5.17)

with the indices in rnatrix-indexing notation. The individual differences rnay
also be squared, and the square root of their suru taken to be the net gradient.
The advantage of the Roberts operator is that it is a
forward-looking operator

Thus, the result may be written in the same array as the

input image

This was advantageous when computer memory was

expensive and in short supply
 (ul (LI

(c I ( <l I

FIGl.iRE 5. 2
(.ll SLJ.J,Jt"~ t ..... t iui.J._,;t". (L:1 G.a ...<lit"ut ui..u.;uit1YJt". di,v1..._.. I.LU-.t"
"· 'l"t,!1 . (C:1 H~11,mutJ.l <lt"! i\oiti·,t". di-.vl.i-" 1u.ui.;t"
'°· JOO .)Ut ..,f
2.,.,_ 2.,., .out of I 'l"tt!t. 'l"ti!, .
(<l·1 Yt"l ticJ.l dt"l i ....1ti,.,. di-.J.JL-" 1.1u.;t" 200. 200 -ut - f 'l"tH1. 'l"t.!1 . (t!l J!, 0
<lt-,i•,J.ti, ... di---vL.... 1.u~.;.- 2, ....,. 200 out of I 'l"t.!1. 'l"tH,. cr:i 1:i!, <lt"!h.1ti, ...
0

d.i~vld) IJ.J,J~~ l.uu. l,H, ~ul _r ( ";"t;!,. 7ti!J .

FIGwRE s.:s
(d) Clcx:k lt:"I 1u • .1:;..-. jL) G1 ..ul1t'.'ul u..1.,:,u1lU'.lt'.'. dr,l,11..t.) i.uii; • u. I )(I ulJI of
u.:tl•,. (cl Il<,11..<:~u1.::Jtlt:i1-.al1•.... <li~JJla_; ldU~.,., h J. t., .>1~1 t:.f !J~i?-. !ilY.
(di v.. ,t,c.J c1 .. ,n ..,ll\ .... d1,...,h., 1.1.u:;.- I 1... , Ill .,f JJti. 1 l!1. (t:) H, 0
dt•J IHdHt'.'. Ji~l,11.t_; la!J~t'.' l.n, ...... oul uf !1 I I. 1 Ht. Cft I J!,~ dt:J ,-.atnt'.
<l,~p I ,._.. 1 U.J\!.t' It ,. I 00 out of I J:i I . r, ,HJ .
 ( <:) (d I

(t' I (f I

FJGwRE 5.4
f.1l Kut.•t' ~JR iwa;;t'. (Ll G1.1(lst'11l u.a\:,u1tu:! ... di-.µJ.L_\ 1.uJ.;<' ~). 100 oul uf
,,.ti9.:< . lt:J Hu11.1.~u1.J c!CJ I\J.ll\C. cli-.pl.1,; 1.u,i;c luv. 1,,.. uul ~r a9t,. 191>.
f d) v..1 I ical d ..1 I\ al IVC. di-jJI.L) I LU,.,.. .!vu. :?.,., out c.f IH -:. Ml!!- . ft• J 1?1°
d!'JI', Lll',t'. w~..,h.:, I.LU>,;C 2,nl. lll\, ' I l l -f .,lil.!n,:i. ffJ 1:i!, 0 c!,•11\.LlH't'.
<11,-µla_.,, lJ.JJ'tt' .!vu. 2...u >ul ,.r t~i.!.!J.!tl.
 The Laplacian of Gaussian
Although the Laplacian is a
gradient operator, it should be
recognized that it is a second-
profile of edge order difference operator

This leads to double-edged

outputs with positive and

Lf
fin:t derivative
negative values at each edge

cecond derivative

FIGURE 6.6
Thp to bolt.om: A profile of a blurred object showin ~ two ed~es. the first
deri\'ali\'e. and the second deri\'ali\'e (see also Fi~ure 4.26).
The Laplacian has the advantage of being omnidirectional, that
is, being sensitive to edges in all directions

However, it is not possible to derive the angle of an edge from

the result

The operator is also sensitive to noise because there is no

averaging included in the operator

The gain in the frequency domain increases quadratically with

frequency causing significant amplification of high-frequency
noise components

For these reasons, the Laplacian is not directly useful in edge

detection
The double-edged output of the Laplacian indicates an
important property of the operator

The result possesses a zero-crossing in between the positive

and negative outputs across an edge

The property holds even when the edge in the original image is
significantly blurred

This property is useful in the development of robust edge

detectors

The noise sensitivity of the Laplacian may be reduced by

including a smoothing operator
A scalable smoothing operator could be defined in terms of a
2D Gaussian function, with the variance controlling the spatial
extent or width of the smoothing function

Combining the Laplacian and the Gaussian, we obtain the

popular Laplacian-of-Gaussian or LoG operator

~ .
Consider the Gaussian specified by the function

x2 + y2) (5 .18)
g(x, y) --;; • exp ( - 2 a-2 •
The usual norrnalizing scale factor has been left out. Tdking partial derivatives
with respect to x and y, \Ve obtain
a2g X
2 2
x2-y2)
- 0'4
(1
2 (12
8x 2
a2g y2 O'
2

ay2 - 0'4

(5.19)
\Vhich leads to
r2 2 a2 ( r2 )
v1 2g(x,y) - LoG(r)--= 4 exp ' 2 , (5 .20)
(J 2 (J

\vhere r -= Jx 2 + y2 . The LoG function is isotropic and has positive and

negative values. Due to its shape, it is often referred to as the lVIexican hat
or sornbrero.
 (a) (b)

(c) (d)

(e) (f)

FIGURE 6.7
I'hc Laplacian of Gaussian in (b) ima~c formaL and (cl) as a mesh plot.. I'he
related Gaussian functions are shown in (a) and (c). rhc size of the arrays
is 51 x 51 pL~els: standard de·dat.ion a 1 pL~els. rhe Fourier ma~nit.ude
spectra of the funclions are shown in (c) and (f).
Canny’s method for edge detection
Canny proposed an approach for edge detection based upon
three criteria for good edge detection, multidirectional
derivatives, multiscale analysis, and optimization procedures

The three criteria relate to

(i) Low probabilities of false edge detection and missing real
edges represented in the form of an SNR
(ii) Good localization represented by the RMS distance of the
detected edge from the true edge
(iii) The production of a single output for a single edge
represented by the distance between the adjacent maxima in
the output
A basic filter derived using the criteria mentioned above was approximated
by the first derivative of a Gaussian

Procedures were proposed to incorporate multiscale analysis and directional

filters to facilitate efficient detection of edges at all orientations and scales
including adaptive thresholding with hysteresis

The LoG filter is nondirectional, whereas Canny’s method selectively

evaluates a directional derivative across each edge

By avoiding derivatives at other angles that would not contribute to edge

detection but increase the effects of noise

Canny’s method could lead to better results than the LoG filter
Fourier-domain methods for edge detection
Highpass filters may be applied in the Fourier-domain to extract the edges in
the given image

However, the inclusion of all of the high-frequency components present in the

image could lead to noisy results

Reduction of high-frequency noise suggests the use of bandpass filters, which

may be easily implemented as a cascade of a lowpass filter with a highpass
filter

In the frequency domain, such a cascade of filters results in the multiplication

of the corresponding transfer functions

Because edges are often weak or blurred in images, some form of

enhancement of the corresponding frequency components would also be
desirable

This argument leads us to the LoG filter; a combination of the Laplacian,

which is a high-frequency emphasis filter with its gain quadratically
proportional to frequency, with a Gaussian lowpass filter
The LoG filter demonstrates the edge detection capabilities and easily
implemented in the frequency domain

Frequency-domain implementation using the FFT may be computationally

advantageous when the LoG function is specified with a large spatial array,
which would be required in the case of large values of σ

Several other line-detection and edge-detection methods such as Gabor

filters may also be implemented in the frequency domain with advantages
Segmentation and Region Growing

Dividing an image into regions that could correspond to structural units,

objects of interest, or ROIs is an important prerequisite for most techniques
for image analysis

Whereas a human observer may, by merely looking at a displayed image,

readily recognize its structural components, computer analysis of an image
requires algorithmic analysis of the array of image pixel values before arriving
at conclusions about the content of the image

Computer analysis of images usually starts with segmentation, which reduces

pixel data to region-based information about the objects and structures
present in the
image
Image segmentation techniques may be classified into four main
categories:
• Thresholding techniques
• Boundary-based methods
• Region-based methods, and
• Hybrid techniques that combine boundary and region criteria

Thresholding methods are based upon the assumption that all pixels whose
values lie within a certain range belong to the same class

The threshold may be determined based upon the valleys in the histogram
of the image
However, identifying thresholds to segment objects is not easy even with
optimal thresholding techniques

Moreover, because thresholding algorithms are solely based upon pixel

values and neglect all of the spatial information in the image, their accuracy
of segmentation is limited

Further, more thresholding algorithms do not cope well with noise or

blurring at object boundaries
Boundary-based techniques make use of the property that usually pixel
values change rapidly at the boundaries between regions

The methods start by detecting intensity discontinuities lying at the

boundaries between objects and their backgrounds, typically through a
gradient operation

High values of the output provide candidate pixels for region boundaries,
which must then be processed to produce closed curves representing the
boundaries between regions, as well as to remove the effects of noise and
discontinuities due to non-uniform illumination and other effects

Although edge-linking algorithms have been proposed to assemble edge

pixels into a meaningful set of object boundaries, such as local similarity
analysis, Hough-transform-based global analysis, and global processing via
graph-theoretic techniques, the accurate conversion of disjoint sets of edge
pixels to closed-loop boundaries of ROIs is a difficult task
Region-based methods, which are complements of the boundary-based
approach rely on the postulate that neighboring pixels within a region have
similar values

Region-based segmentation algorithms may be divided into two groups

region splitting and merging and region growing

Segmentation techniques in the region splitting and merging category

initially subdivide the given image into a set of arbitrary disjoint regions and
then merge and/or split the regions in an attempt to satisfy some pre-
specified conditions

Region growing is a procedure that groups pixels into regions

The simplest of region-growing approaches is pixel aggregation, which starts

with a seed pixel and grows a region by appending spatially connected
neighboring pixels that meet a certain homogeneity criterion
Different homogeneity criteria will lead to regions with different
characteristics, It is important, as well as difficult, to select an appropriate
homogeneity criterion in order to obtain regions that are appropriate for the
application on hand

The main difficulty with region-based segmentation schemes lies in the

selection of a homogeneity criterion

Region-based segmentation algorithms have been proposed using statistical

homogeneity criteria based on regional feature analysis, Bayesian probability
modeling of images, Markov random fields and seed-controlled homogeneity
competition
Segmentation algorithms could also rely on homogeneity criteria with respect
to gray level, color, texture or surface measures
 Optimal thresholding
Suppose it is kuowu u pr·ior•1: that the gi vcu iu1agr cousists of ouly t \VO priucipal
brightucss le vcls with the prior probabilities l '1 aud l '2. Cousidcr the situatiou
where uatural variati ous or noise 1uodify the two gray le vcls to dist,ributious
rcprcscutcd by (jaussiau PDFs p1(:e) aud JJ2(~), where :r rcprrscuts the gray
level. The PDF of the i1uagc gray levels is tbcu _8

where 111 aud 112 arc the 1uca11s of the two rcgious, aud a1 aud a2 arc their
staudard dcvi atious. Let µ1 < Jt2.
 Supposr that the dark rrgious iu thr in1agc corrrspoud to t,hr backgro1111d,
aud thr bright regious to the obj rcts of interest. Ihcu, all pixrls brlow a
threshold I 1uay br cousidcrrd to bcloug to thr backgro1111d, aud nll pixels
abovr r 1uay br cousideird as pixels bclougiug to the obj cct, of iutcrrst. The
probability of erro11rous classification is theu

l'~ (I) = 1'1 f

'1 '
oo

1J1 (i) di - 1'2 jT

-oo
p2( i) dx. (5.30)

Io fiud thr opti1ual tlu·rshold, we uiay diJlrrcutiatc l'~(T) with rcsprct to T

aud c(111atc the rrsult to ~cro, which leads to

(5.31)
Applying this result to thr (jaussia11 PDFs gives (after takiug logaritb111s and
sowc siwplitication) the quadratic equation _8_

A.T 2 HT - (1 0, (5.32)

where

.A : (J2l (J2
2'

(5.33)

The possibility of two solutious indicates that it niay require two thresholds
to obtain the optinial Uu·cshold.
 lf ai =ai =a~, n si11glc f hrrghold 111ny be u~rd, gi vc11 by
?
1' = /11 J. /12 .1. _a_-_ In 1'2
2 /11 /t2 /'1

l111rf hrnuorr, if f,hc fwo prior probabilitiirg nrr rc1ual, tihnt. iq, 1'1 =1'2, or if tihr
vnrinucr iq zrro, thnf i~, a =0, f hr. opti111al fhrr.shold i~ cc1unl to f he avrrngr
of f hr two 111rn11q,
Thresholding using boundary characteristics
The number of pixels covered by the objects of interest to be segmented
from an image is almost always a small fraction of the total number of pixels
in the image the gray-level histogram of the image is then likely to be almost
unimodal

The histogram may be made closer to being bimodal if only the pixels on or
near the boundaries of the object regions are considered
 The selrctiou aud charactcriiatiou of the edge or bouudary pixels 1uay be
achieved by usi11g gradic11t aud Laplaria11 operators as tallows _8 :

b(:e, y) = L~ if v' 1(~, y) > T a11d v'}(:e, y) .> 0, (5.35)

l L_ if Vj(:e,y) > T aud V}(:e,y) < 0,

where v' f ( :e, y) is a gradicut aud v'} (~, y) is the Laplaciau of the gi ve11 i1uage
f (~t, y); T is a Uu·cshold; a11d 0, Lt , L _ represrut tlu·ec distiucti gray le vc ls.
lt1 the rcsultiug i1uagc, the pi.xels that arc uot 011 au edge arc set to icro, the
pLxels 011 the darker sides of edges arc set to L+, a11d the pixels ou t.be lighter
sides of edges arr set to L_. This iufor1uati ou 1uay be ILScd uot ouly to detect
obj rcts aud edges, but also to idcutify the lea di ug aud traili11g edges of obj crts
(with refcreuce to the scau11iug directiou).
Region-oriented segmentation of images

Lrt ll rrprr~rut thr rrgiou ~p~u111i ug th r rutiJr ~pace of thr gi "eu i111 age.
Srg111ruf nt iou 111ay be virwrd a~ n procr~~ that part it ious 11 iut.o n ~ubrrgio11s
ll1,lf.2, ... ,l(,1 such that _8_

• U? 1JI, = ll, th at i~, thr u11io11 of all of thr rrgio11s drf rct rd spau~ t hr
rufirc i111ngc ( f hr 11, evrry pixr l 11111 ~f beloug fio a rrgio11);

• Iii i~ n co1111rct rd rrgiou, i = 1, 2, ... , 11;

• ll; n lf. j = l~ Vi, j, i 1 j (that i~, thr rrgio11~ arr di~j oi ut);
 • P(lli) = TU( I}!;, for i = l, 2, ... ,11 {for rx~uuplr, all pixrl~ withiu a
rrgio11 hnvc thr qmuc i11tr11qifiy );

• P(U, I Uj) =F.4.LSE ~'i,j, if. j {for rxn111plc, fhc iufruqifirq of the
pixrl~ i11 diffrrruti rrgiouq arr diffrrrut);

whrrr P( H,) iq a logical prrdiratr drfi11rd ovrr f hr poiufig i11 thr grfi U,, a11d
0iq thr uull sot
 A siu1ple algorithu1 for regiou growiug by pixel aggrcgatiou based 11pou thr
sin1i lari ty of a local property is as follows:

• Start with a seed pLx.rl (or a set of seed pLx.els).

• Appeud to rach pixel iu the regiou those of its 4-conuected or 8-couucctcd

urighbors that ha vr properties (gray le vcl, color, ctr.) that arr si1uilar
to those of the serd.

• Stop whcu the rcgiou cauuot be growu auy tiu-thcr.

The results of au algoritluu as above depend upou the proced,u·c used to

srlrct, the seed pixc ls aud the 111eastues of siutilarity or iuclttsi ou critrria usrd.
Thr rcsultis 111ay also drpcud 11po11 the 1urthod used to traverse the huagc;
that is, the scquPuce i11 which ueighboriug pixels arc checked for iud usiou.
 Splitting and merging of regions

Instead of using seeds to grow regions or global thresholds to separate an

image into regions, one could initially consider to divide the given image
arbitrarily into a set of disjoint regions, and then to split and/or merge the
regions using conditions or predicates P

A general split/merge procedure is as follows

Assuming the image to be square, subdivide the entire image R successively
into smaller and smaller quadrant regions such that for any region Ri, P(Ri)
=TRUE

In other words, if P(R) = FALSE, divide the image into quadrants

If P is FALSE for any quadrant, subdivide that quadrant into subquadrants
Iterate the procedure until no further changes are made or a stopping
criterion is reached

The splitting technique may be represented as a quadtree

Difficulties could exist in selecting an appropriate predicate P

Because the splitting procedure could result in adjacent regions that are
similar, a merging step would be required, which may be specified as
follows:

Merge two adjacent regions Ri and Rk, if P(Ri Ս Rk) = TRUE

Iterate until no further merging is possible

Region growing using an additive tolerance
A commonly used region-growing scheme is pixel aggregation

The method compares the properties of spatially connected neighboring pixels with
those of the seed pixel, the properties used are determined by homogeneity criteria

For intensity-based image segmentation, the simplest property is the pixel gray level

The term “additive tolerance level” stands for the permitted absolute gray-level
difference between the neighboring pixels and the seed pixel

A neighboring pixel f(m, n) is appended to the region if its absolute gray-level

difference with respect to the seed pixel is within the additive tolerance level T:

lf(rn, 'n) seed!< T.

 2 3 4 5 2 3 4 5
100 101 101 100 101 111111■■111
2 100 127 126 128 100 2 100 seed 126 128 100
3 100 124 128 127 100 3 100 124 128 127 100
4 100 124 125 126 101 4 100 124 125 126 101
5 101 100 100 101 102 5 101 ■■Ill 102
(a) (b)

2 3 4 5 2 3 4 5

111111■■111
2 100 100 2 100 127 126 128 100
100 3 100 124 128 127 100
101 4 100 124 125 126 101
5 101 102 s 101 ■■Ill.
(c) (d)

FIGURE 5.17
Exaruple of additive-tolerance region g1·owing using different. seed pixels (T -=
3). (a) Original image. (b) The 1·esult. of region g1·owing (shaded in black) with
the seed pixel at (2, 2). (c) The result of region growing with the seed pix.el at.
(3, 3). (d) The result. of region growing with the running-wean algorit.hru or
the Hew-rent. cent.er pixel" ruet.hod using any seed pixel within the highlighted
region. Figw·e cow·t.esy of L. Shen _320_.
Figure 5.17 shows a simple example of additive-tolerance region growing
using different seed pixels in a 5X5 image

The additive tolerance level used in the example is T=3

Observe that two different regions are obtained by starting with two seeds
at different locations as shown in Figure 5.17b and Figure 5.17c

In order to overcome this dependence of the region on the seed pixel

selected, the following modified criterion could be used to determine
whether a neighboring pixel should be included in a region or not

Instead of comparing the incoming pixel with the gray level of the seed, the
gray level of a neighboring pixel is compared with the mean gray level,
called the running mean µRc, of the region being grown and its current
stage Rc
This criterion may be represented as

(5.37)
where
(5 .38)

where Nc is the number of pixels in Rc

Figure 5.17d shows the result obtained with the running-mean algorithm
by using the same additive tolerance level as before (T=3)

With the running-mean criterion, no matter which pixel is selected as the

seed, the same final region is obtained in the present example, as long as
the seed pixel is within the region, which is the central highlighted area in
Figure 5.17d
 Region growing using a multiplicative tolerance

In addition to the sensitivity of the region to seed pixel selection with additive
tolerance region growing, the additive tolerance level or absolute difference
in gray level T is not a good criterion for region growing

An additive tolerance level of 3, while appropriate for a seed pixel value or

running mean of, for example, 127, may not be suitable when the seed pixel
gray level or running mean is at a different level, such as, or 230 or 10

In order to address this problem, a relative difference, based upon a

multiplicative tolerance level τ could be employed
Then, the criterion for region growing could be defined as

f_(n_i_,n_)_I-L_R_cl < 7
_I
(5.40)

or

2 lf(m, n) 1-LRci < ,, (5.41)

f(m, n) + 1-LRc -

,vhere f (rn, n) is the gTay level of the current pLxel being checked for inclusion,
and µRe could stand for the original seed pixel value, the current center pixel
value, or the running-mean gTay level. Observe that the t,vo equations above
are c.:ornparable to the definitions of sirnultaneous contrast in Equations 2. 7
and 2.8.
The additive and rnultiplic.:ati ve tolerance levels both determine the rnaxi-
mum gray-level deviation allowed within a region, and any deviation less than
this level is considered to be an intrinsic.: property of the region, or to be noise.
1\IIultiplicative tolerance is rneaningful ,vhen related to the SNR of a region (or
image), whereas additive tolerance has a direct connection with the standard
deviation of the pLxels within the region or a given image.
Analysis of region growing in the presence of noise
In order to analyze the perforrnance of region-gro,ving r11ethods in the presence
of noise, let us assur11e that the given image g n1ay be r11odeled as an ideal
ir11age f plus a noise ir11age T/, where f consists of a series of strictly uniforrn,
disjoint, or nonoverlapping regioru; Ri, i - 1, 2, ... , k, and T/ includes their
corresponding noise parts ·ryi, i - 1, 2, ... , k. 1VIather11atically, the in1age rnay
be expressed as
g - ft T/, (5 .42)
,vhere
f- LJ Ri, i --= 1, 2, ... , k, (5.4:~)
t'

and
T/ -= ui
TJi, i-1,2, ... ,k. (5 .44)
A strictly uniform region Ri is composed of a set of connected pixels f(m, n)
at positions (rn ) n) \vhose v·tlues
CJ equal a constant K.· that is
t) )

Ri - { ( rn, n) I f (rn, n) - Ki } . (5 .45)

The set of regions Ri, i - 1, 2, ... , k, is \vhat \Ve expect to obtain as the
result of segmentation. Suppose that the noise parts rJi, i - 1, 2, ... , k, are
cornposed of \Vhite noise \vith zero rnean and standard deviation ai; then, \Ve
have
g - LJ(Ri + rJi), i-= 1, 2, ... ,k, (5 .46)
t

and
f - LJ Ri - g LJ 'l'Ji, i -= 1, 2, ... , k. (5 .4 7)
t i

As a special case, \vhen all the noise cornponents have the same standard
deviation a, that is,
(5 .48)
and
(5.49)
,vhere the syrnbol ,,.,.., represents statistical similarity, the image f may be de-
scribed as
LJ
g ,,.,.., Ri + TJ, i - 1, 2, ... , k, (5.50)
i

and
f - LJ Ri ,,.,.., g - TJ; i --= 1, 2, ... , k. (5.51)
i

Additive-tolerance region gro,ving is ,veil-suited for segmentation of this spe-

cial type of irnage, and an additive tolerance level solely determined by CT may
be used globally over the image. Ho,vever, such special cases are rare in real
irnages. A given irnage generally has to be modeled, as in Equation 5.46,
,vhere multiplicative-tolerance region gro,ving may be more suitable, ,vith the
expectation that a global multiplicative tolerance level can be derived for all
of the regions in the given image. Because the multiplicative tolerance level
could be made a function of t
that is directly related to the SNR, ,vhich
2
can be defined as 10 log10 ~i dB for each individual region Ri, such a global
(1'

tolerance level can be found if

(5.52)