Decomposition of Arbitrarily Shaped Binary Morphological Structuring Elements Using Genetic Algorithms.
AbstractA number of different algorithms have been described in the literature for the decomposition of both convex binary morphological structuring elements and a specific subset of nonconvex ones. Nevertheless, up to now no deterministic solutions have been found to the problem of decomposing arbitrarily shaped structuring elements. This work presents a new stochastic approach based on Genetic Algorithms in which no constraints are imposed on the shape of the initial structuring element, nor assumptions are made on the elementary factors, which are selected within a given set.
INTRODUCTION
MATHEMATICAL morphology [1], [2], [3] concerns the study of shape
using the tools of set theory. Mathematical morphology has been
extensively used in low-level image processing and analysis appli-
cations, since it allows to filter and/or enhance only some characteristics
of objects, depending on their morphological shape. A lot of
tutorials [3], [2], [4], [1], [5], [6], [7] can be found in the literature.
Within the mathematical morphology framework, a binary image
A is defined as a subset of the two-dimensional Euclidean
space
In [3], monadic transforms acting on a generic image A
(complement, reflection, and translation) and dyadic operators between
sets (dilation, erosion, opening, and closing) are defined. In the
following only the definitions of operators used throughout this
paper are recalled, such as translation
, for some with
(2)
and dilation
for some
where A represents the image to be processed, and B is called
Structuring Element (SE), namely, another subset of E 2 whose shape
parameterizes each operation.
An SE B is said to be convex with respect to a given set of morphological
operations (e.g., dilation) with a given set of SEs (factors) {F ,
it can be expressed as a chain of dilations of the F i elements:
with for (4)
Otherwise B is said to be nonconvex with respect to the same set of SEs,
and, thus, it can only be expressed as a chain of Boolean operations
(e.g., unions and/or intersections) between convex elements
(called
. (5)
where ( represents any Boolean operation (such as unions <,
intersections >, .) and C i are convex elements that can be expressed
as chains of dilations, as shown in (4).
As discussed in the following section, the decomposition of a
binary SE into a chain of operations involving only elementary
factors is a key problem. So far, only deterministic solutions have
been analyzed and proposed in the literature [8], [9], [10], each relying
on different assumptions (such as convex SEs, specific sets of
elementary operators, etc.); on the other hand the optimal decomposition
(with respect to a given set of optimality criteria) of nonconvex
generic SEs with a deterministic approach is still an open problem.
This paper addresses this problem utilizing a stochastic ap-
proach, based on Genetic Algorithms: starting from a population
of potential solutions (individuals) determined through an exhaustive
algorithm, an iterative process modifies the existing individuals
and/or creates new ones in accordance to a set of genetic
operators applied randomly. The individuals that minimize a
given cost function tend to replace the others, and, after a sufficient
number of iterations, the algorithm tends to converge toward
the optimal solution. In particular, the main purpose of this work
is to develop a tool able to give a preliminary answer to the problem
of optimal decomposition of nonconvex SEs into concatenations
of generic elementary operations.
This work is organized as follows: Section 2 motivates the need
for SE decomposition and discusses some optimality criteria that
can drive the decomposition; Section 3 briefly summarizes the
Genetic Approach, its terminology and its notations, and describes
the implementation of the decomposition algorithm and the data
structures involved; Section 4 presents some results while Section 5
concludes the paper with some remarks and a discussion on future
developments.
2.1 Motivation
The following two subsections motivate the need for SE decomposition
on traditional serial systems, in which the use of a large SE is
not efficient, and on SIMD cellular systems that allow the execution
of only basic operations based on a neighborhood smaller than the
size of the SE; the different characteristics of general-purpose
(serial) and SIMD cellular (parallel) systems require different techniques
in order to exploit the specific hardware characteristics of
each system.
Hereinafter, a dilation between a generic image A and a complex
SE B is considered; due to the different properties of unions
and intersections discussed in [3], namely
in the following nonconvex SEs are decomposed using chains of
unions of convex SEs (using the equality expressed by relation (6),
instead of using chains of intersections or other Boolean operations
(where no equality relations hold).
2.1.1 Serial Systems
General-purpose serial systems have no upper bound to the size of
possible SEs: In fact, using a bitmapped image representation, the
value of any image pixel can be accessed within a constant time.
. The authors are with the Dipartimento di Ingegneria dell'Informazione,
Universit- di Parma, I-43100 Parma, Italy.
E-mail: broggi@ce.unipr.it.
Manuscript received 15 Apr. 1996; revised 17 Apr. 1997. Recommended for acceptance
by R. Chin.
For information on obtaining reprints of this article, please send e-mail to:
tpami@computer.org, and reference IEEECS Log Number 104926.
J:\PRODUCTION\TPAMI\2-INPROD\104926\104926_1.DOC correspondence97.dot SB 19,968 12/23/97 2:31 PM 2 8
On the other hand, the computational complexity of a serial implementation
of morphological operations depends on the number
of elements which form the operands. As an example, the computation
of A ! B requires one vector sum and one logical union for
each couple of elements a OE A and b OE B, and, thus,
where 9(#) indicates the computational complexity (the number of
vector operations) of a given operation, and #) represents the
number of elements in a set.
Using the well-known visual representation of morphological
sets [3], the number of vector sums and logical unions required by
dilation
according to (8), is given by #(A)
The structuring element B can be expressed as the dilation between
subsets
and using the chain rule property [3],
. The number of sums required to perform the
first step of the processing
is given by while the number of sums
required to complete the processing (R
Thus, the decomposition shown in (10),
while incrementing the total number of dilations from one to two,
decreases the number of operations performed from 180 to 145.
2.1.2 SIMD Cellular Systems
When a bitmapped data representation is used, mathematical
morphology operations involve repeated computations over large
data structures, thus the use of parallel systems improves the
overall performance. Both parallel architectures with spatial parallelism
(cellular systems), based on a high number of Processing Elements
(PEs) devoted to the simultaneous processing of different
image areas, and parallel architectures with operational parallelism
(pipeline systems), where the different PEs work in pipeline of the
same image area, share common constraints. The planar surface of
the silicon chip limits the hardware interconnections, thus reducing
the complexity of the elementary operations (the size of the
possible SEs) that can be performed by each single PE.
This fact is more evident in cellular systems, where the set of all
possible operations performed by each single PE (known as Instruction
Set, IS) is generally based on the use of 3 - 3 SEs. Thus,
since operations based on large SEs cannot be performed, their
decomposition into chains of simpler operations belonging to the
IS becomes mandatory. The above dilation shows the
main difference between serial and cellular systems. On serial
systems the dilation can be performed either directly (with a single
after the decomposition of B, as a chain of
more than one dilation (as shown by (11)), thus leading to a different
computational complexity. On the other hand, that dilation
cannot be performed directly on a cellular system since it is based
on a SE not belonging to the IS. Thus, while in the first case (serial
systems), the decomposition may be recommended for a number
of reasons (such as the speed-up of the processing), it becomes
mandatory in the second case (cellular systems).
Assuming a system capable of performing horizontal and vertical
dilations and translations in the eight main directions, B (as
defined in (9)) is nonconvex with respect to the IS of the system; it
may be expressed as a union of convex sets, for example
where
are convex with respect to the IS of the system and can
thus be expressed as:
Thus, according to this decomposition, the initial dilation
can be performed with six elementary dilations and one logical
union. This is a one-level solution, involving only a single level of
unions of dilations, also called sum of products (see Fig. 1a).
It is obvious that a multilevel solution may lead to a better re-
sult. For example using the chain rule property, can be
expressed in a two-levels solution:
This solution, depicted graphically in Fig. 1b, requires only five
dilations and one logical union.
2.2 Optimality Criteria
The decomposition of a SE can be aimed to many different goals,
such as:
. the minimization of the number of decomposing sets (to reduce
the number of dilations);
. the minimization of the total number of computations (for
speed-up reasons);
. the minimization of the total number of elements in the decomposing
sets (to reduce the size of the data structures and
thus also the memory requirements in serial systems);
. the possibility to implement complex morphological operations
on cellular systems whose IS is based on simple, elementary
operations (to overcome the problem caused by the
simple interconnection topology that limits the size of possible
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 20, NO. 2, FEBRUARY 1998 3
J:\PRODUCTION\TPAMI\2-
correspond
ence97.dot
. or even the determination of factors with a given shape (to
aid the recognition of 2D objects).
The optimality criterion addressed in this work can be changed
acting on the parameters of a cost function.
Genetic Algorithms (GAs), widely used in various fields [11], are
optimization algorithms based on a stochastic search [12], operating
by means of genetic operators on a population of potential solutions
of the considered problem (individuals). The main data
structure is the Genome or Chromosome, that is composed of a set of
Genes and of a Fitness value. In the population of possible solutions
the set of new individuals generated by means of genetic operators
is called Offspring.
The genetic search is driven by the fitness function: Each individual
is evaluated to give some quantitative measure of its fitness, that
is the "goodness" of the solution it represents. At each iteration
(generation) the fitness evaluation is performed on all individuals.
Then, at the following iteration, a new population is generated,
starting from the individuals with the highest fitness, and replac-
ing, completely or partially, the previous generation. The genetic
operators used to generate new individuals are subdivided into
two main categories: unary operators, creating new individuals
and replacing the existing ones with a modified version of them
(e.g., mutation, introduction of random changes of genes), and
binary operators, creating new individuals through the combination
of data coming from two individuals (e.g., crossover, exchange
of genetic material between two individuals). Each iteration step is
called generation.
The study of GAs led to the more general Evolution Programs
(EPs) [13], or Generalized GAs. In "standard" GAs an individual is
represented by a fixed-length binary string, encoding the parameters
set, which corresponds to the solution it represents; the genetic
operators act on these binary codes. In EPs, individuals are
represented by generalized data structures without the fixed-length
constraint [14], [15]. In addition, ad-hoc operators are defined
to act on these data structures.
EPs perfectly match the requirements of the SE decomposition
problem, since the varying number of elementary items forming a
solution does not allow to know a priori the size of a generic solu-
tion, that is the length of the coding of a generic individual. In fact,
for an efficient implementation, the data structure representing a
decomposition must explicitly encode both the number and the
shape of each single elementary operation composing the solution.
Moreover, this coding must also allow fast and easy processing
and evaluation phases. For these reasons it has been necessary to
develop an ad hoc EP with specific genetic rules, exploiting a
method similar to the one presented in [16] for the solution of the
bin-packing problem. Up to now, the number of iterations is chosen
by the user, but different termination criteria are under
evaluation (such as the percentage of improvement or the number
of different individuals) [11], [13].
3.1 Data Structure
As stated above, the data structure representing an individual has
to describe in a flexible and compact way the convex elements of (5),
showing its shape and decomposition into factors, but it has also
to make the evaluation phase fast and simple. This representation
has to be variable in length, since the number z of possible partitions
involved in the decomposition of a generic individual , has
no maximum bound; on the other hand, recalling (4), the number
m and the shape of factors F kj , which form element C k , depend
directly on C k .
For these reasons an individual is represented by an arbitrarily
long chain of genes, each gene representing a partition of the input SE
(see Fig. 2). The logical union of all genes produces the individual.
The simplest implementation consists in representing each
individual with a data structure whose fields contain all the
above information. Conversely, a more complex, hierarchical
data structure has been developed in order both to use a lower
amount of memory for each individual and to ease and speed-up
the determination of new better solutions. Although the handling
of this data structure is definitely complex, it allows to
detect possible overlappings among the individuals of a popula-
tion. Each level of the hierarchy encodes only the information
strictly necessary to that level. Three are the levels of the hierar-
chy, as shown in Fig. 2:
. Factor level: The basic components are the elementary morphological
operations (i.e., the instruction set elements): an
integer indicates which element of the IS is used, while a
pointer allows to follow the chain of elements.
. Gene level: A gene is composed of one or more factors and
it corresponds to a dilation chain of factors; an integer gives
the origin of the partition described by the gene, thus speci-
Fig. 1. (a) Union of dilations, also known as sum of products. (b) A two-levels solution.
Fig. 2. The data structure representing two individuals.
4 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 20, NO. 1, JANUARY 1998
J:\PRODUCTION\TPAMI\2-INPROD\104926\104926_1.DOC correspondence97.dot SB 19,968 12/23/97 2:31 PM 4 8
fying the translation required to fit the gene onto the initial
(the origin) and a pointer identifies the next gene.
. Individual level: One or more genes form the individual
that corresponds to a union of dilation chains, corresponding
to a decomposition or, more often, to a part of a decomposi-
tion. An integer gives the total number of genes forming the
individual, a pointer gives the position of the first gene of
the chain, while a double precision number contains the fitness
value of the individual.
3.2 Initialization of the Population
In order to understand this fundamental step, some definitions are
introduced.
DEFINITION 1. The IS is a set of M factors:
DEFINITION 2. Notation H (x,y) stands for H # {(x, y)}, namely, it represents
a translation, as in (2).
DEFINITION 3. For a generic image H,
. terms, 0
DEFINITION 4. For a generic image H, O H represents its origin.
In the following, B is the input SE, B i is a generic subset of B
with the same origin, and H represents any generic set, convex
with respect to the IS:
If O Fi OE F i for every F i belonging to the IS, 1 then O H OE H. The process
starts with the identification of every element of set &(B),
which is defined as

for some (19)
since every element of &(B) may represent a possible gene; this search
has to be deterministic and exhaustive. Since O F
OE , the set of possible
pairs (h, k) is given by the set of all elements of B; for a generic image H, if
(h, Therefore, the algorithm scans all the
pixels of the SE and determines which factors can form a legal chain of
dilations starting from that pixel. The gene obtained so far needs an
additional shift in order to overlap its origin with the origin of B.
Since the length of the best solution is not known a priori and
since randomly linking together some genes seldom yields a legal
solution, we have decided to use each element of &(B), which
comprises all the workable genes, as constituting an individual
with a chromosome composed of a single gene only. It is also pos-
sible, as an option, to include in the population multiple copies of
each individual so formed. In this way the set of individuals
forming the initial population is obtained.
3.3 The Fitness Function
The fitness function f(,) is used to evaluate each individual , in
order to drive the algorithm during the search. A cost function
f C (,) has been introduced, which is identical to f(,) if and only if
is the general partition forming solution , of
length N. This function must have several properties:
solutions it is equal to f(,);
it is defined also for nonlegal solutions (i.e., solutions not covering
perfectly the original SE), thus widening the search space;
it is easily implemented as a penalty function.
1. In the current implementation, each factor is limited in size to 3 - 3
and O F
F OE .
Penalty functions are used in highly constrained problems when
the need of evaluating nonlegal solutions is met by penalizing
them with respect to the legal ones. The cost function thus includes
a penalty term:
where a is equal to 1 if and only if B B
# , as stated above,
otherwise a is expressed by a term proportional to the ratio between
the number of elements present in the solution and the total
number of elements in B. The term b is related, via user-defined
parameters, to the current population size, and f P is the penalty
function, that is still related to the percentage of elements of B covered
by the decomposition contained in the considered individual.
Assuming that the goal of the process is to obtain the decomposition
that minimizes the number of operations required to compute
the dilation of a generic image with SE B, the fitness function
f(,) is mainly constituted by the sum of the cost of every partition
in addition, it takes into account also the number of logical union
operations required, weighted by an appropriate coefficient,
and the additional saving allowed by a multilevel solution. The
program, in fact, lets the user choose from among three different
optimization levels, thus leading to different final results: Level 0
does not perform any optimization; level 1 performs a first pack-
ing, based on the methods explained at the end of Section 2.1.2;
level 2 tries to pack again the solutions obtained at level 1. The use
of optimization levels 1 and 2 becomes of basic importance when
the target architecture has the capability to store temporary re-
sults, since it allows to achieve solutions with sensibly lower costs.
3.4 The Genetic Search
The structure of the algorithm is depicted in Fig. 3; a single processing
cycle is composed of four stages:
. Selection Operators: Choose two individuals among population
for reproduction purpose;
. Binary Genetic Operators: Combine, in various ways, the
parents' chromosomes in order to get offspring (i.e., one
child or two children);
. Comparison Operators: Set up a competition between parents
and offspring for inclusion in the next generation;
. Unary Genetic Operators: Mutate the chromosomes of the
individuals winning at the previous stage.
When the list containing the individuals of the current population
is exhausted, i.e., every individual has been chosen for reproduc-
tion, the population just formed undergoes the same processing:
this generation-formation process stops when the maximum number
of allowed generations is reached. 2 In the following, a brief
review of the operators is presented.
3.4.1 Selection Operators
The operator is based on the tournament selection scheme as exposed
in [17] with a tournament size of two. The scheme implemented
makes use of a slightly modified version of the genic selective
crowding technique [17] which forces individuals to compete with
those who have at least
I I
I I
pixels in common with them. In this way, a pressure is maintained
for similar to compete with similar, incrementing in this way the
significance of the tournament.
2. As mentioned, other termination criteria are currently under
evaluation.
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 20, NO. 2, FEBRUARY 1998 5
J:\PRODUCTION\TPAMI\2-
correspond
ence97.dot
3.4.2 Binary Genetic Operators
In order to obtain individuals that cover the SE in the initial phase
we need an operator which varies appreciably the length of indi-
viduals' chromosomes. Conversely, after this phase, when the
average length of individuals is roughly close to the optimal one,
we are concerned about the quality of the chromosome; for this
reason two different operators have been conceived.
. The first one is based upon the cut and splice operator [18].
Let l be the number of genes constituting a chromosome:
This operator cuts the chromosome randomly in correspondence
to one of the l possible points. If one of the l - 1
points connecting two consecutive genes is chosen, the
chromosome is broken into two parts; otherwise, with probabilityl , it is left unchanged. The two, three, or four chromosome
segments of two different individuals are pushed
in a stack; the splice stage either merges the first two top
elements of the stack, creating in this way a single child, or
promotes each element to a full individual. This shows how
the number of individuals in the following generation can
be altered. An example is shown in Fig. 4a.
. The second operator is the dual of the previous one: it attempts
to improve the fitness of the parents by mixing their
chromosomes, searching for a slight edge of improvement
by trial and error. A gene composing the first parent is
"injected" into the chromosome of the other parent, replacing
one of its genes, thus not changing the length of the
chromosome but altering only its content. The procedure is
run twice, swapping the two parents' roles. The number of
offspring generated is always two, although in some cases
they can coincide with a parent. An example is shown in
Fig. 4b.
3.4.3 Comparison Operators
At this stage the operator chooses among parents and offspring the
individuals to be inserted in the next generation. The scheme followed
is based upon the Deterministic Crowding scheme presented in [19].
3.4.4 Unary Genetic Operators
In standard GA the unary operator is the mutation, that simply
inverts randomly one or more bits of the string representing the
chromosome. On the other hand, our implementation of mutation
has the primary goal of reinserting genes previously discarded
and otherwise definitively lost; typically this is the case of little
partitions, whose contribution to the fitness improvement has
been underestimated in the previous phases of the execution. This
contribution can be essential later to achieve the covering of the
whole B. Genes are drawn from an array of genes (containing all
possible genes) and stored in memory so that every gene is chosen
cyclically. Two operators have been created:
. MUTATION 1: This operator compares each gene forming the
chromosome of the individual with the gene g coming from
the array. The gene g substitutes the most similar one in the
chain, that is the gene that maximizes the intersection between
the two genes, as in the following example:
. MUTATION 2: This operator forces gene g to be included,
along with the suppression of those which overlap with it. It
can cause a big fitness worsening but it has the advantage to
increase diversity in the chromosomes as a whole, as in the
following example:
The complete process is shown in Fig. 5 where a simple selection
(which does not use a tournament scheme) is added. It is possible
to traverse the graph following 2 3 paths and the decisions are
made according to the value of the respective probability values
These parameters are computed at the beginning of every
generation starting from parameters describing the status of the current
generation; they can be regarded as adaptive parameters [20].
4.1 Decomposition of Convex SEs
In accordance with the way the initial population is generated, the
decomposition of a convex SE by means of this approach leads to
the same results discussed in the literature (such as in [8]). This is
due to the fact that the optimal solution is a member of the initial
population, which consists of all possible (i.e., legal) decompositions
of the SE, given an arbitrary set of elementary SEs.
4.2 Decomposition of NonConvex SEs
Let us now consider the decomposition of the following nonconvex
Fig. 3. The generational cycle.
Fig. 4. Examples of the cut and splice. (a) Replacing crossover. (b) Operators.
6 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 20, NO. 1, JANUARY 1998
J:\PRODUCTION\TPAMI\2-INPROD\104926\104926_1.DOC correspondence97.dot SB 19,968 12/23/97 2:31 PM 6 8
whose optimal decomposition using the following 3 IS
is definitely nontrivial. The stochastic decomposition led to the
result shown in the following:
The dilation of a generic image A with B is then reduced to the
that, considering the IS shown in (23), takes a total of 50 elementary
dilations and eight logical unions. Had the algorithm run with
the optimization level set to one, (24) could be expressed as a sequence
of 22 elementary dilations and eight logical unions:
where I is the identity image.
In [8] the original SE needs to be convex and it is decomposed
using a given set of factors. Conversely, in [9], a wider class of SEs
is considered: The original SE can also be nonconvex but must be
simply connected and must belong to a specific class ' of decomposable
SEs. In that paper, the decomposition of a generic SE S is
defined by:
S A A A n
where A i is a 3 - 3 or less simply connected factor. This represents
an optimal decomposition when n is minimized, regardless of the
3. This IS has been chosen to reflect the set of operations available on
the PAPRICA system, a special-purpose architecture dedicated to the
execution of morphological processings.
shape of the A i elements. To compare this algorithm with ours, let
us choose a SE belonging to ' as discussed in [9]:
Hereinafter, when presenting a SE decomposition, we will use the
following
where M indicates the decomposition method used, B is the input
indicates the function giving the cost associated with each
factor belonging to the IS.
The optimal decomposition of SE H proposed by Park and Chin
in [9] is
where f is the four-connected shift cost function mentioned in [8].
Note that using this technique the morphology of the factors is not
known a priori, but only at the end. This is in contrast with our
approach that requires to specify a set of factors before running
the algorithm. To overcome this we can synthesize every factor in
(28) with factors belonging to a generic set and use the same set
within our program. Obviously, when a factor is not convex with
respect to such IS, Boolean operators must be used (in this case,
logical unions). The IS used here is a modified version of the set
specified in [8]:
The resulting decomposition is:
According to the four-connected shift cost function [8], D PC (H, f)
has cost 14. In the following, the decomposition obtained with our
Fig. 5. A schematic representation of the generational process: at each generation individuals are taken in pairs, and in accordance to the respective
probability values p1, p2 and p3, selection, binary operators and unary operators are applied.
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 20, NO. 2, FEBRUARY 1998 7
J:\PRODUCTION\TPAMI\2-
correspond
ence97.dot
(Anelli, Broggi, Destri, ABD) stochastic approach is presented, 4
where the superscript stands for the optimization level:
with the following partial results:
On the other hand, if the cost is set to one for every factor (cost
function g), the total cost of D PC (H, g) is equal to the cost of
ABD (H, g) becomes:
with the following partial results:
leading to a total cost of nine. When operating with level 2 of op-
timization, A # H can be easily computed replacing the identity
image I with the image A in (34) and (36). Table 1 summarizes the
cost of the solutions we have obtained for SE H for different optimization
levels, and for cost functions f and g, along with the solution
presented in [9].
Even though we had to rearrange the decompositions given in
[9] in order to fit our requirements (thus altering its cost), this two
examples show that the two approaches, although not directly
comparable, give solutions with similar cost. In addition, in our
approach the freedom of not knowing a priori the shape of the SEs
composing the IS is replaced with the possibility to decompose
also nonconvex SEs.
5 CONCLUSION
This paper presented a new approach to the decomposition of
arbitrarily shaped binary morphological structuring elements into
chains of elementary factors, using a stochastic technique. The
application of this technique to convex structuring elements leads
to the optimal decompositions discussed in the literature; in addi-
tion, this paper provides a way of decomposing also nonconvex SEs.
4. In these examples, the cost of the union operation has been set to
zero.
Extensive experimentations (not documented here due to space
limitations) have shown that the amount of memory required by
the system grows according to the size of the initial SE and with
the number and size of the elementary SEs. Elements up to
have been decomposed using ISs composed of eight basic operations
on a two processors HP 9000 with 128 megabytes of RAM;
the decompositions took about six hours of CPU time and computed
200 generations starting with an average of 2,000 individu-
als; the computations required about 80 megabytes of memory.
Due to the extremely high computational load required by this
iterative approach and to the large memory requirements, the
genetic engine is now being ported to the MPI parallel environ-
ment: the decomposition is managed by a "master" process, which
spawns child processes on the different nodes of a cluster of work-
stations: each child process is in charge of a specific portion of the
processing, which is executed in parallel with all others. This parallel
implementation allows to speed up the processing and to
decompose very large SEs. Moreover, a graphical interface is also
being designed to ease the definition of both the initial SE and the
IS, as well as the introduction of parameters. Being based on the
Java programming language, its integration into a Web page is
straightforward, thus allowing remote users to define and run
their own decompositions on our cluster of workstations.
In addition, the first release of the complete tool running on
many different systems (SunOS, AIX, Linux, HP-UX, DOS, and
will be shortly available as public domain software via
anonymous FTP to researchers working in the mathematical morphology
field.

ACKNOWLEDGMENTS

The authors would like to thank Prof. Aurelio Piazzi for his valuable
suggestions. This work was partially supported by the Italian
National Research Council (CNR) under the frame of the
"Progetto Finalizzato Trasporti 2."



--R

"An Evolutionary Algorithm That Constructs Recurrent Neural Networks,"
"Speeding-Up Mathematical Morphology Computations With Special-Purpose Array Processors,"
"A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems,"
"An Introduction to Simulated Evolutionary Optimiza- tion,"
Genetic Algorithms in Search
"Messy Genetic Algorithms: Motivation, Analysis, and First Results,"
"Messy Genetic Algorithms Revisited: Studies in Mixed Size and Scale,"
"Image Analysis Using Mathematical Morphology,"
Adaption Natural and Artificial Systems.
"Crossover Interactions Among Niches,"
Random Sets and Integral Geometry.
Genetic Algorithms
"Optimal Decomposition of Convex Structuring Elements for a 4-Connected Parallel Array Processor,"
"Decomposition of Arbitrarily Shaped Morphological Structuring Elements,"
Image Analysis and Mathematical Morphology.
"Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm,"

"Methods for Fast Morphological Image Transforms Using Bitmapped Binary Images,"
"Theory of Matrix Morphology,"
"Morphological Structuring Element Decomposition,"
--TR

--CTR
Ronaldo Fumio Hashimoto , Junior Barrera , Carlos Eduardo Ferreira, A Combinatorial Optimization Technique for the Sequential Decomposition of Erosions and Dilations, Journal of Mathematical Imaging and Vision, v.13 n.1, p.17-33, August 2000
Frank Y. Shih , Yi-Ta Wu, Decomposition of binary morphological structuring elements based on genetic algorithms, Computer Vision and Image Understanding, v.99 n.2, p.291-302, August 2005
Ronaldo Fumio Hashimoto , Junior Barrera, A Note on Park and Chin's Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.1, p.139-144, January 2002
genetic algorithms;arbitrarily shaped structuring element decomposition;mathematical morphology