See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/235767029

Ashraf A. Aly, Safaai Bin Deris, Nazar Zaki, “Research Review For Digital Image
Segmentation Techniques. International Journal of Computer Science &
Information Technology (IJCSI...

Article in International Journal of Computer Science and Information Technology · October 2011
DOI: 10.5121/ijcsit.2011.3509

CITATIONS READS

31 464

3 authors:

Ashraf Ahmed Aly H. Safaai deris

Universiti Teknologi Malaysia University of Malaysia, Kelantan
15 PUBLICATIONS 120 CITATIONS 120 PUBLICATIONS 797 CITATIONS

SEE PROFILE SEE PROFILE

Nazar M Zaki
United Arab Emirates University
224 PUBLICATIONS 3,536 CITATIONS

SEE PROFILE

All content following this page was uploaded by Ashraf Ahmed Aly H. on 22 May 2014.

The user has requested enhancement of the downloaded file.

 International Journal of Computer Science & Information Technology (IJCSIT) Vol 3, No 5, Oct 2011

RESEARCH REVIEW FOR DIGITAL IMAGE

SEGMENTATION TECHNIQUES

Ashraf A. Aly1, Safaai Bin Deris2, Nazar Zaki3

1, 2
Faculty of Computer Science, Universiti Teknologi Malaysia
[email protected], [email protected]
3
College of Information Technology, UAE University, UAE
[email protected]

ABSTRACT
Evaluating the previous work is an important part of developing segmentation methods for the image
analysis techniques. The aim of this paper is to give a review of digital image segmentation techniques.
The problems of digital image segmentation represent great challenges for computer vision. The wide
range of the problems of computer vision may make good use of image segmentation. This paper study
and evaluate the different methods for segmentation techniques. We discuss the main tendency of each
algorithm with their applications, advantages and disadvantages. This study is useful for determining the
appropriate use of the image segmentation methods and for improving their accuracy and performance
and also for the main objective, which designing new algorithms.

KEYWORDS
Active Contour, Segmentation Enhancement, Topological Alignments, Boundary Detection, image
Segmentation, Inversion Technique.

1. INTRODUCTION
Digital image processing is important domain for many reasons. Actually Digital image
processing is a recent subject in computer history. In 1960s; Bell Labs and University of
Maryland, and a few other places started to develop several techniques for digital image
processing. With application to satellite imagery, wire photo standards conversion, medical
imaging, videophone, character recognition, and photo enhancement. But the cost of processing
was fairly high with the computing equipment of that era. In the 1970s, image processing
proliferated, when cheaper computers and dedicated hardware became available. Images could
then be processed in real time, for some dedicated problems such as television standards
conversion. As general-purpose computers became faster, they started to take over the role of
dedicated hardware for all but the most specialized and compute-intensive operations.

In digital image processing, we use computer algorithms to perform image processing. Actually
digital image processing has several advantages over the analog image processing; first it gives
a high number of algorithms to be used with the input data, second we can avoid some
processing problems such as creating noise and signal distortion during signal processing. In
2000s, fast computers became available for signal processing and digital image processing has
become the popular form of image processing. Because of that, signal image processing became
versatile method, and also cheapest.

Image segmentation is important part in many signal processing technique and its applications.
The segmentation procedure is to find the better positions of the shape points according to the

DOI : 10.5121/ijcsit.2011.3509 99
 International Journal of Computer Science & Information Technology (IJCSIT) Vol 3, No 5, Oct 2011
appearance information. Algorithms based on classifiers have been widely applied to segment
organs in medical images like cardiac and brain images. The goal of image segmentation
process is partitioning the image into regions. Image segmentation applications identifying
objects in a scene for object-based measurements such as size and shape, identifying objects in a
moving scene for object-based video compression, identifying objects which are at different
distances from a sensor using depth measurements from a laser range finder enabling path
planning for mobile robots. The purpose of image segmentation is to cluster pixels of an image
into image regions. We can use segmentation for image compression, object recognition, and
image editing processing.

2. RELATED WORK
The problems of digital image segmentation represent great challenges for computer vision. The
wide range of the problems of computer vision may make good use of image segmentation.
Many researchers had created several methods to deal with the problem of image segmentation.
Zimmer et al. [10] created a method to detect the mobility of live cells using the active contour
(snakes) method. Mukherjee et al. [30] modified a method to handle the tracking problem using
threshold method. Coskun et al. [4] used the inverse modelling to detect the mobility of living
cells. Recently there have been a number of researchers has tried to create several image
segmentation algorithms as in (Krinidis et al., Mélange, et al., Mignotte et al.).

In this paper we managed to review and summarized the major techniques for digital image
segmentation. We categorized these techniques based on the segmentation method which the
technique is using. In Table 2.1 a comparison of the image segmentation methods.

3. DIGITAL IMAGE SEGMENTATION METHODS

In the following subsection, we will review the methods applied to segment images.
The segmentation of an image I, which represent a set of pixels is partitioning into n disjoint
sets R1,R2, . . . , Rn, called segments or regions such that their union of all regions equals I,
I =R1 U R2 U….. U Rn .

3.1 Inversion technique

The principle of the inversion is to continuously update the muscle activity to produce a face
movement following a given face trajectory (Smith et al., 1986; Terzopoulos et al., 1991; Press
et al., 1992; Waters et al., 1996). When the inversion had been carried out for all frames, the
inverted activity was used to generate an animation. A conventional nonlinear optimizer
minimizing a cost function was selected to implement the inversion. The cost function E was
the sum of the squares of the Euclidean distances between the markers and the corresponding
face model nodes:

∑
2
E= mi − ni (1)
i =1

where mi and ni are the 3-D positions of the ith marker and face model node, respectively, N is
2
the number of nodes used in the inversion, and is the vectorial magnitude square operator,
i.e., the sum of the squares of each coordinate of the vector.

The inversion could produce different activity patterns, depending on the initial conditions.
Constraints may be added to the inversion to limit the number of solutions. In all analyses, the

100
 International Journal of Computer Science & Information Technology (IJCSIT) Vol 3, No 5, Oct 2011
inversion was carried out without constraints; then with the constraint that the inverted filtered
EMG values had to be positive. The new positive constraint cost function E ' was redefined in
the second case by:

∑
2
E' = mi − ni , if all filtered EMG ≥ 0 (2)
i =1

E ' = 10 6 (1 + ∑ EMG 0 ), if at least one filtered EMG ≥ 0 (3)

Where mi and ni are the 3-D positions of the i th marker and face model node, respectively, N is
the number of nodes used in the inversion, and EMG0 is the set of negative muscle activity
levels. The constraint that all filtered EMG had to be greater than zero will be called the positive
constraint. The advantage of the method is the high quality of the animation and also the data is
very good, but the different EMG patterns can produce the same kinematic output which affects
the accuracy.

3.2. Pattern Recognition Techniques

Pattern Recognition Techniques is a non-linear modelling tools and we can be used to model the
inputs and outputs relationships (fukunaga et al., 1990; Awwal et al., 1992; Portegys et al.,
1995; Coskun et al., 2007; Baum et al., 1998). Weights in the classifier are selected through
optimizing energy functional defined by the features of structures and are updated through
processing each sample in the training set.

The extracted information from the training set provides important cues of the structures such as
intensity, position and shape, which can be valuable complementary information for the
segmentation of test images. Active appearance models (AAM) are statistical models of the
shape of structures. Training samples are used to extract the mean shape, mean appearance and
define ranges of shape parameters. Restrictions on shape parameters guarantee the similarity
between the segmentation result and the training samples. The segmentation procedure is to find
the better positions of the shape points according to the appearance information. Algorithms
based on classifiers have been widely applied to segment organs in medical images like cardiac
and brain images. If properly modelled, supervised classification algorithms can greatly enhance
the segmentation accuracy. However, supervised classification algorithms are sensitive to the
initial conditions. To guarantee the correctness of the results, the training set must contain
enough samples and the samples should be representative and segmented accurately.

3.3. Active contour models

Active contour models (snakes) goal is to apply segmentation process to an image by doing
deformation to the initial contour towards the boundary of the object of interest. We do that by
deforming an initial contour to minimizing the energy function which defined on contours (Kass
et al. 1987; Ray et al., 2002; Zimmer et al., 2002; Kruse et al., 1996; Sacan et al., 2008). There
are two components in this energy: the potential energy, which is small when the contour is
aligned to edges of the image, and the internal deformation energy, which is small when the
contour is smooth. Both components are contour integrals with respect to a parameter of the
contour.

An Active contour can be parametrically represented by v(s) = (x(s), y(s)) and its energy
functional can be written as:

101
 International Journal of Computer Science & Information Technology (IJCSIT) Vol 3, No 5, Oct 2011
1 1
E = ∫01 Eint ( v( s ))ds + 0∫ Eimage( v( s ))ds + ∫ Eext( v( s ))ds (4)
0

Where Eint represents the spline internal energy and Eimage represent the image forces and Eext
represent to the external forces. The spline energy controlled by a(s) and by B(s). Therefore, the
internal spline energy can be written as:

2 2
( a( s) vs ( s ) + B ( s ) vss ( s ) )
Eint = (5)
2

The total image energy can be represented as a combination of three weighted energy functions
and can be written as:

Eimage = wline Eline + wedge Eedge + wterm Eterm (6)

Active contour models (Snakes) can be represented by two models: region based models and
edge-based models. The characteristics of the image determine the model we should choose.
The main advantage of snakes models is the ability of snakes to give a linear description of the
object shape during the time of convergence without adding extra processing. But what
scientifically limits the use of snakes is the need of the method to have strong image gradients to
be able to drive the contour.

3.4. Threshold Method

Thresholds in these algorithms can be selected manually according to a priori knowledge or
automatically through image information. Algorithms can be further divided to edge-based
ones, region-based ones and hybrid ones (Canny, 1986; Gonzalez et al., 2002; Mukherjee et
al., 2004; Sezgin et al., 2004). Thresholds in the edge-based algorithms are related with the edge
information. Structures are depicted by edge points. Common edge detection algorithms such as
Canny edge detector and Laplacian edge detector can be classified to this type. Algorithms try
to find edge pixels while eliminate the noise influence. For example, Canny edge detector uses
the threshold of gradient magnitude to find the potential edge pixels and suppresses them
through the procedures of the non maximal suppression and hysterics shareholding. As the
operations of algorithms are based on pixels, the detected edges are consisted of discrete pixels
and therefore may be incomplete or discontinuous. Hence, it is necessary to apply post-
processing like morphological operation to connect the breaks or eliminate the holes. The
method has the ability to segment 3D image with good accuracy, but the disadvantage of this
method is the difficulty of the method to process the images of textured blob objects.

3.5. Topological Alignments Method

Topological Alignments Method depends on formalize the problem of aligning two consecutive
frames as a generalized assignment problem (Miura et al., 2005; Danuser et al., 2005; Zimmer
et al., 2006; Ersoy et al., 2007). The algorithm links the segmentation of two frames from the
video sequence. The process starts from the output of the segmentation procedure, the algorithm
work by finding the maximum weighted solutions to a generalized matching between two
segments, and derive weights from relative sets of segments.

In this method we identify the segmentation of the first image into m segments with an index set
P = {1,..., m}, and the second image segmentation into n segments with an index set Q = {1,...,
n}. Then, alignments between these sets can be introduced through partitioning P and Q into an
equal number of subsets.
102
 International Journal of Computer Science & Information Technology (IJCSIT) Vol 3, No 5, Oct 2011

Assuming that cells move moderately between two consecutive frames, we assign the relative
overlap of p and q as their weight, formally defined as

w(p, q) :=| A(p) ∪ A(q) | / | A(p) ∪ A(q) | (7)

In general, we consider the sets of segments which have overlap close to 1 as one cell, but the
sets of segments which have overlap close to 0 not to be considered as one cell. Based on these
weights, we can consider the notions of the topological alignments. We denote PL(M) for the
set of all L-partitioning`s of a finite set M; note that given a partition S ∈ PL(M), we consider S
as a family of sets and hence can identify the L subsets by writing S = (S1,..., SL). This allows
us to state our alignment as finding those partitioning`s S and T that realize the maximum in the
target function.

The topological alignments method improves the performance of segmentation of cell tracking
by explicitly taking into account the inherent problems of over (one cell is split into two
segments) and under (one segment fully covers two cells) segmentation, while still allowing the
detection of cell division. The algorithm links segments between every frame and the next one,
that will reduce the number of false trajectories and false detections. The method can deal with
low contrast images and shape cells and improves the filtration efficiency. The advantage of the
method is the ability of topological alignments to mitigate the image noise and cell deformation.

3.6. Watersheds Method

Watershed image segmentation is based on the theory of Mathematical Morphology
(Beucher et al., 1979; Najman and Schmitt, 1996; Meyer et al., 1996; Lezoray et al.,
2003; Huguet et al., 2004). Numerous techniques have been proposed to compute
watersheds. The classical idea for building the watershed is using a geographical
analogy, begin by piercing the regional minima of the surface. Then slowly immerse the
image into a lake. The water progressively floods the basins corresponding to the
various minima. To prevent the merging of two different waters originating from two
different minima, we erect a dam between both lines. Once the surface is totally
immersed, the set of the dams thus built is the watershed of the image. In one
dimension, the location of the watershed is straightforward: it corresponds to the
regional maxima of the function. In two dimensions, one can say in an informal way
that the watershed is the set of crest lines of the image, emanating from the saddle
points.

The method stick this initial contour to the maximum contained watershed contour. For
label image G = [R, E], we assume each edge eij Є E is a directing curve with the
direction the same as clockwise direction of region ri`s contour.

Watershed contour discriminate to initial contour. A watershed contour is also a closed

contour, but it is exactly along the watershed edges, i.e., it is composed of watersheds.
When we input an initial manually delineated contour, we need to push (or expend) it to
the nearby watershed edge to facilitate the later calculation. The method helps to
improve the capture range but it has disadvantage of over segmentation.

103
International Journal of Computer Science & Information Technology (IJCSIT) Vol 3, No 5, Oct 2011
Table 2.1 Comparison of the Image Segmentation Methods.

Method Advantage Disadvantage

Inverse dynamics method • Data are very good. • Many different EMG
• Animation is of high patterns can produce the
quality. same kinematic output
• Using a nonlinear
optimizer.

Active contour method • Use active contour • Should find strong image
models gradients to drive the
• Preserves global line contour.
shapes efficiently • Lacking accuracy with
weak image boundaries
and image noise

Watersheds Method • Based on Mathematical • Over segmentation

Morphology
• Helps to improve the
capture range

Novel edge-based • Algorithm based on an • depends on the

method energy minimization assumption that the
procedure. deformation and
movement of the tracked
object is small between
the frames.
Topological alignments • Improve the filtration • Complicated.
method efficiency.
Using linkage
clustering.

Pattern Recognition • Pattern recognition • Restrictions on shape

method fields used to perform parameters.
the segmentation. • Complicated
• The method used to
model relationships
between inputs and
outputs.

Threshold method • Try to find edge pixels • The detected edges are
while eliminate the consisted of discrete
noise influence. pixels and may be
• Use gradient incomplete or
magnitude to find the discontinuous.
potential edge pixels. • Computationally
expensive

104
 International Journal of Computer Science & Information Technology (IJCSIT) Vol 3, No 5, Oct 2011

4. CONCLUSIONS
From the previous review, we classify the current methods and summarize their features. Also
each method has its suitable application fields, and researchers should combine the application
background and practical requirements to design proper algorithms. Accuracy, complexity,
efficiency and interactivity of a segmentation method should all be the considered factors.

This paper makes a review on the current segmentation methods, and the main tendency of each
method with their principle ideas, application field, advantages and disadvantages are discussed.

REFERENCES
[1] S. Osher and J. Sethian, “Fronts propagating with curvature dependent speed: Algorithms
based on Hamilton - jacobi formulations,” Journal of Computationl Physics, pp. 12–49, 1988.
[2] Bouguet, J. (2000). Pyramidal implementation of the Lucas Kanade feature tracker. Intel
Corporation Microprocessor Research Labs: OpenCV Documents.
[3] Bradski, G. (2000). The Open CV Library. Dr. Dobb’s Software Tools for the Professional
Programmer.
[4] Coskun, H., Li, Y., and Mackey, M. A. (2007). Ameboid cell motility: A model and inverse
problem, with an application to live cell imaging data. Journal of Theoretical Biology, 244(2):
169–179.
[5] Kass, M., Witkin, A., and Terzopoulos, D. (1987). Snakes: Active contour models. International
Journal of Computer Vision, pages 321–331.
[6] Li, K., Miller, E., Weiss, L., Campbell, P., and Kanade, T. (2006). Online tracking of migrating
and proliferating cells imaged with phase - contrast microscopy. Proc. Of the 2006 Conf, on
Computer Vision and Pattern Recognition Workshop (CVPRW’06), pages 65–72.
[7] Mukherjee, D., Ray, N., and Acton, S. (2004). Level set analysis for leukocyte detection and
tracking. IEEE Trans Image Process, 13(4):562–72.
[8] Ray, N., Acton, S., and Ley, K. (2002). Tracking leukocytes in vivo with shape and size
constrained active contours. 21(10):1222–1235.
[9] Smart, J., Hock, K., and Csomor, S. (2005). Cross-Platform GUI Programming with wxWidgets.
Prentice Hall PTR.
[10] Zimmer, C., Labruyre, E., Meas-Yedid, V., Guilln, N., and Olivo-Marin, J. (2002). Segmentation
and tracking of migrating cells in videomicroscopy with parametric active contours: a tool for
cell-based drug testing. IEEE Trans Med Imaging, 21(10):1212–21.
[12] Shtern F. Digital mammography and related technologies: a perspective from the National
Cancer Institute. Radiology 1992; 183:629-630.
[13] Feig SA, Yaffe MJ. Current status of digital mammography. Semin Ultrasound CT MR 1996;
17:424-443.
[14] Aylward SR, Hemminger BM, Pisano ED. Mixture modeling for digital mammogram display
And analysis. In: Karssemeijer N, Thijssen M, Hendriks J, van Erning A, eds. Digital
mammography Nijmegen, 1998. Dordrecht, the Netherlands: Kluwer Academic, 1998; 305-312.
[15] Pisano ED, Zong S, Hemminger BM, et al. Contrast limited adaptive histogram equalization
image processing to improve the detection of simulated spiculations in dense mammograms. J
Digit Imaging 1998; 11:193-200.
[16] Chan HP, Vyborny CJ, MacMahon H, et al. Digital mammography ROC studies of the effects of
pixel size and unsharp - mask filtering on the detection of subtle microcalcifications. Invest
Radiol 1987; 22:581-589.

105
 International Journal of Computer Science & Information Technology (IJCSIT) Vol 3, No 5, Oct 2011
[17] Byng JW, Critten JP, Yaffe MJ. Thickness equalization processing for mammographic images.
Radiology 1997; 203:564-568.
[18] Bick U, Giger ML, Schmidt RA, Nishikawa RM, Doi K. Density correction of peripheral breast
tissue on digital mammograms. RadioGraphics 1996; 16:403-411.
[19] Nath SK, Bunyak F, Palaniappan K: Robust Tracking of Migrating ells Using Four- Color Level
Set Segmentation. ACIVS 2006:920-932.
[20] Koehler A, Schambony A, Wedlich D: Wnt Signaling in Embryonic Development Elsevier 2007
chap. Cell migration under control of Wnt signaling in the vertebrate embryo:159-201.
[21] Zimmer C, Zhang B, Dufour A, Thebaud A, Berlemont S, Meas-Yedid V, O Marin JC: On the
Digital Trail of Mobile Cells. Signal Processing Magazine 2006, 23(3):54-62.
[22] Palaniappan K, Ersoy I, Nath SK: Moving Object Segmentation Using the Flux Tensor for
Biological Video Microscopy. Lect Notes Comput Sci. 2007, 4810(LNCS):483-493.
[23] Miura K: Tracking Movement in Cell Biology. Advances in Biochemical Engineering/
Biotechnology 2005, 95:267-295.
[24] Meijering E, Smal I, Danuser G: Tracking in molecular bioimaging. Signal Processing
Magazine, IEEE 2006, 23(3):46-53.
[25] Bouguet, J. (2000). Pyramidal implementation of the Lucas Kanade feature tracker. Intel
Corporation Microprocessor Research Labs: OpenCV Documents.
[26] Bradski, G. (2000). The Open CV Library. Dr. Dobb’s Software Tools for the Professional
Programmer.
[27] Kass, M., Witkin, A., and Terzopoulos, D. (1987). Snakes: Active contour models. International
Journal of Computer Vision, pages 321–331.
[28] Li, K., Miller, E., Weiss, L., Campbell, P., and Kanade, T. (2006). Online tracking of migrating
and proliferating cells imaged with phase - contrast microscopy. Proc. of the 2006 Conf, on
Computer Vision and Pattern Recognition Workshop (CVPRW’06), pages 65–72.
[29] Mukherjee, D., Ray, N., and Acton, S. (2004). Level set a nalysis for leukocyte detection and
tracking. IEEE Trans Image Process, 13(4):562–72.
[30] Dzyubachyk O, Niessen W, Meijering E: Advanced Level - Set Based Multiple - Cell
Segmentation and Tracking in Time – Lapse Fluorescence Microscopy Images. In IEEE
International Symposium on Biomedical Imaging: From Nano to Macro Edited by: Olivo-
Marin JC, Bloch I, Laine A. IEEE, Piscataway, NJ; 2008:185-188.
[31] Li Y, Zheng Y, Doermann D, Jaeger S: Script-Independent Text Line Segmentation in Freestyle
Handwritten Documents. IEEE Trans Pattern Anal Mach Intell. 2008, 30(8):1313-1329.
[32] Ersoy I, Bunyak F, Mackey M, Palaniappan K: Cell Segmentation Using Hessian - Based
Detection and Contour Evolution with Directional Derivatives. International Conference on
Image Processing 2008:1804-1807.
[33] Tseng Y, Kole T, Wirtz D: Micromechanical Mapping of Live Cells by Multiple Particle
Tracking Microrheology. Biophysical Journal 2002, 83(6):3162-3176.
[34] Apgar J, Tseng Y, Fedorov E, Herwig M, Almo S, Wirtz D: Multipleparticle tracking
measurements of heterogeneities in solutions of actin filaments and actin bundles. Biophysical
Journal 2000, 79(2):1095-1106.
[35] Schütz GJ, Schindler H, Schmid T: Single-molecule microscopy on model membranes reveals
anomalous diffusion. Biophysical Journal 1997, 73:1073-1080.
[36] Anderson C, Georgiou G, Morrison I, Stevenson G, Cherry R: Tracking of cell surface receptors
by fluorescence digital imaging microscopy using a charge-coupled device camera. Low-density
lipoprotein and influenza virus receptor mobility at 4 degrees C. Journal of Cell Science 1992,
101(2):415-425.

106

View publication stats