Decomposition of Gray-Scale Morphological Templates Using the Rank Method.
AbstractConvolutions are a fundamental tool in image processing. Classical examples of two dimensional linear convolutions include image correlation, the mean filter, the discrete Fourier transform, and a multitude of edge mask filters. Nonlinear convolutions are used in such operations as the median filter, the medial axis transform, and erosion and dilation as defined in mathematical morphology. For large convolution masks or structuring elements, the computation cost resulting from implementation can be prohibitive. However, in many instances, this cost can be significantly reduced by decomposing the templates representing the masks or structuring elements into a sequence of smaller templates. In addition, such decomposition can often be made architecture specific and, thus, resulting in optimal transform performance. In this paper we provide methods for decomposing morphological templates which are analogous to decomposition methods used in the linear domain. Specifically, we define the notion of the rank of a morphological template which categorizes separable morphological templates as templates of rank one. We establish a necessary and sufficient condition for the decomposability of rank one templates into 3  3 templates. We then use the invariance of the template rank under certain transformations in order to develop template decomposition techniques for templates of rank two.
INTRODUCTION
OTH linear convolution and morphological methods are
widely used in image processing. One of the common
characteristics among them is that they both require applying
a template to a given image, pixel by pixel, to yield a
new image. In the case of convolution, the template is usually
called convolution window or mask; while in mathematical
morphology, it is referred to as structuring element.
Templates used in realizing linear convolutions are often
referred to as linear templates. Templates can vary greatly in
their weights, sizes, and shapes, depending on the specific
applications.
Intuitively, the problem of template decomposition is
that given a template t, find a sequence of smaller templates
K n such that applying t to an image is equivalent to
applying t t
sequentially to the image. In other
words, t can be algebraically expressed in terms of
One purpose of template decomposition is to fit the support
of the template (i.e., the convolution kernel) optimally
into an existing machine constrained by its hardware con-
figuration. For example, ERIM's CytoComputer [1] cannot
deal with templates of size larger than 3 - 3 on each pipe-line
stage. Thus, a large template, intended for image processing
on a CytoComputer, has to be decomposed into a
sequence of 3 - 3 or smaller templates.
A more important motivation for template decomposition
is to speed up template operations. For large convolution
masks, the computation cost resulting from implementation
can be prohibitive. However, in many instances,
this cost can be significantly reduced by decomposing the
masks or templates into a sequence of smaller templates.
For instance, the linear convolution of an image with a
gray-valued multiplications and
- additions to compute a new image pixel value; while
the same convolution computed with an 1 - n row template
followed by an n - 1 column template takes only 2n multiplications
a f additions for each new image pixel
value. This cost saving may still hold for parallel architectures
such as mesh connected array processors [2], where
the cost is proportional to the size of the template.
The problem of decomposing morphological templates has
been investigated by a host of researchers. Zhuang and
Haralick [3] gave a heuristic algorithm based on tree search
that can find an optimal two-point decomposition of a
morphological template if such a decomposition exits. A
two-point decomposition consists of a sequence of templates
each consisting of at most two points. A two-point
decomposition may be best suited for parallel architectures
with a limited number of local connections since each two-point
template can be applied to an entire image in a multi-
ply-shift-accumulate cycle [2]. Xu [4] has developed an al-
gorithm, using chain code information, for the decomposition
of convex morphological templates for two-point system
configurations. Again using chain-code information,
Park and Chin [5] provide an optimal decomposition of
convex morphological templates for four-connected
meshes. However, all the above decomposition methods
work only on binary morphological templates and do not
extend to gray-scale morphological templates.
A very successful general theory for the decomposition
. The authors are with the University of Florida, Gainesville, FL 32611.
E-mail: {ps0; ritter}@cis.ufl.edu.
Manuscript received Nov. 9, 1995; revised Mar. 14, 1997. Recommended for acceptance
by V. Nalwa.
For information on obtaining reprints of this article, please send e-mail to:
transpami@computer.org, and reference IEEECS Log Number 104798.
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 6, JUNE 1997
J:\PRODUCTION\TPAMI\2-INPROD\104798\104798_1.DOC regularpaper97.dot AG 19,968 04/24/97 1:49 PM 2 11
of templates, in both the linear and morphological domain,
evolved from the theory of image algebra [6], [7], [8], [9],
[10] which provides an algebraic foundation for image
processing and computer vision tasks. In this setting, Ritter
and Gader [11], [9] presented efficient methods for decomposing
discrete Fourier transform templates. Zhu and Ritter
[12] employ the general matrix product to provide novel
computational methods for computing the fast Fourier
transform, the fast Walsh transform, the generalized fast
Walsh transform, as well as a fast wavelet transform.
In image algebra, template decomposition problems, for
both linear and morphological template operations, can be
reformulated in terms of corresponding matrix or polynomial
factorization. Manseur and Wilson [13] used matrix as
well as polynomial factorization techniques to decompose
two-dimensional linear templates of size m - n into sums
and products of 3 - 3 templates. Li [14] was the first to investigate
polynomial factorization methods for morphological
templates. He provides a uniform representation of
morphological templates in terms of polynomials, thus reducing
the problem of decomposing a morphological template
to the problem of factoring the corresponding poly-
nomials. His approach provides for the decomposition of
one-dimensional morphological templates into factors of
two-point templates. Crosby [15] extends Li's method to
two-dimensional morphological templates.
Davidson [16] proved that any morphological template
has a weak local decomposition for mesh-connected array
processors. Davidson s existence theorem provides a theoretical
foundation for morphological template decomposi-
tion, yet the algorithm conceived in its constructive proof is
not very efficient. Takriti and Gader formulate the general
problem of template decomposition as optimization problems
[17], [18]. Sussner, Pardalos, and Ritter [19] use a
similar approach to solve the even more general problem of
morphological template approximation. However, since
these problems are inherently NP-complete, researchers try
to exploit the special structure of certain morphological
templates in order to find decomposition algorithms. For
example, Li and Ritter [20] provide very simple matrix
techniques for decomposing binary as well as gray-scale
linear and morphological convex templates. A separable
template is a template that can be expressed in terms of two
one-dimensional templates consisting of a row and a column
template. Gader [21] uses matrix methods for decomposing
any gray-scale morphological template into a sum of
a separable template and a totally nonseparable template. If
the original template is separable, then Gader s decomposition
yields a separable decomposition. If the original template
is not separable, then his method yields the closest
separable template to the original in the mean square sense.
Separable templates are particularly easy to decompose
and the decomposition of separable templates into a product
of vertical and horizontal strip templates can be used as
a first step for the decomposition into a form which
matches the neighborhood configuration of a particular
parallel architecture. In the linear case, separable templates
are also called rank one templates since their corresponding
matrices are rank one matrices. O Leary [22] showed that
any linear template of rank one can be factored exactly into
a product of 3 - 3 linear templates. Templates of higher
rank are usually not as efficiently decomposable. However,
the rank of a template determines upper bounds of worst-case
scenarios. For example, a linear template of rank two
always decomposes into a sum of two separable templates.
In the linear domain, the notion of template rank stems
from the well known concept of matrix rank in linear alge-
bra. The purpose of this paper is to develop the notion of a
morphological matrix rank similar to the linear matrix rank.
By way of bijection, matrices correspond to certain rectangular
templates. In analogy to the linear case, we define the
rank of a morphological template as the rank of the corresponding
matrix. We demonstrate that this notion allows
for an elegant and concise formulation of some new results
concerning the decomposition of gray-scale morphological
templates into separable morphological templates.
The paper is organized as follows. In Section 2, we introduce
the image algebra notation used throughout this
paper and in most of the aforementioned algebraic template
decomposition methods. In Section 3, we develop the notions
of linear dependence, linear independence and rank
pertinent to morphological image processing. In Section 4,
we establish general theorems for the separability of matrices
in the morphological domain. Finally, in Section 5, we
apply the result of the previous sections and establish decomposition
criteria, methods, and algorithms for the decomposition
of gray-scale morphological templates. Proofs
of theorems are given in [23] so as not to obscure the main
ideas and results of this paper.
Image algebra is a heterogeneous or many-valued algebra in
the sense of Birkhoff and Lipson [24], [6], with multiple sets
of operands and operators. In a broad sense, image algebra
is a mathematical theory concerned with the transformation
and analysis of images. Although much emphasis is focused
on the analysis and transformation of digital images,
the main goal is the establishment of a comprehensive and
unifying theory of image transformations, image analysis,
and image understanding in the discrete as well as the continuous
domain [6], [8], [7]. In this paper, however, we restrict
our attention only to the notations and operations that
are necessary for establishing the results mentioned in the
introduction. Hence, our focus is on morphological image
algebra operations.
Henceforth, let X be a subset of the digital plane
Z Z
c h
denotes the set of integers. For
any set F, we denote the set of all functions from X into F by
F X . We use the symbols / and Y- to denote the binary operations
of maximum and minimum, respectively.
2.1 Images and Templates
From the image algebra viewpoint, images are considered
to be functions and templates are viewed as functions
whose values are images. In particular, an F-valued image a
over the point set X is a function a X a X
i. e. ,
while an F-valued template t on X is a function
SUSSNER AND RITTER: DECOMPOSITION OF GRAY-SCALE MORPHOLOGICAL TEMPLATES USING THE RANK METHOD 3
J:\PRODUCTION\TPAMI\2-INPROD\104798\104798_1.DOC regularpaper97.dot AG 19,968 04/24/97 1:49 PM 3 11
i. e. , e j . For notational convenience, we
define t y as t(y) for all y OE X. Note that the image t y has
representation
y y
a f
{ } (1)
where the pixel values t x
y
a f at location x of this image are
called template weights at point y.
Since we are concerned with optimizing morphological
convolutions, the set F of interest will be the real numbers
with the symbol -. appended. More precisely,
F R R
-.
denotes the set of real num-
bers. The algebraic system associated with R -. will be the
semi-lattice-ordered group R -.
c h with the extended
arithmetic and logic operations defined as follows:
a a a
a a a a
-.
-.
a f a f
a f a f
R
R (2)
Note that the element -. acts as a null element in the system
R -.
c h if we view the operation + as multiplication
and the operation / as addition. The dual of this system is
the lattice ordered group R +. Y-
c h . The algebraic system
R -.
c h provides the mathematical environment for the
morphological operation of gray scale dilation, while
R +. Y-
c h provides the environment for the dual operation
of gray scale erosion.
Our focus will be on translation invariant R -valued
templates over X since gray-scale structuring elements can
be realized by these templates. A template t X X
OE -.
R
e j is
called translation invariant if and only if
y z y
a f a f , , Z 2 (3)
are elements of X. The support of a
template
OE -.
R
e j at a point y is denoted by S(t y ) and defined
as follows:
y y
A translation invariant template t is called rectangular, if
rectangular discrete array.
EXAMPLE. Let r X X
OE -.
R
e j be the translation invariant template
which is determined at each point y OE X by the
following function values of x OE X:
r x
x y
x y
x y
y
a f
-.
R
| |
| |
l l
l l for some l
l l
if
if
if
else
we can visualize the rectangular template
r as shown in Fig. 1.
Fig. 1. The support of the template r at point y. The hashed cell indicates
the location of the target point
2.2 Basic Operations
The basic operations of addition and maximum on R -. induce
pixelwise operations on R -valued images and tem-
plates. For any a b X
, OE -.
R and any s t X X
, OE -.
R
a b x a x b x x X
a b x a x b x x X
y y
y y
a fa f a f a f
a fa f a f a f
a f
a f
y
y
If c X
OE -.
R denotes the constant image
a f
c h a f
for some c OE -.
R , then scalar operations on images and
templates can be obtained by defining
c c
c c
c c
c c
a a a c
a a a c
y y y
y y y
a f a f
a f a f
2.3 Additive Maximum Operations
Forming the additive maximum (*) of an image a X
OE -.
R and
a template t X X
OE -.
R
results in the image a t X
* OE -.
R , which
is determined by the following function values.
a t y a x t x
OE
a fb g a f a f (8)
Clearly, each template t X X
OE -.
R
defines a function
4 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 6, JUNE 1997
J:\PRODUCTION\TPAMI\2-INPROD\104798\104798_1.DOC regularpaper97.dot AG 19,968 04/24/97 1:49 PM 4 11
a a t
-.

a
The additive maximum of a template t X X
OE -.
R
e j and a template
OE -.
R
e j is defined as the template r X X
OE -.
R
e j which
determines f f
, the composition of f t followed by f s .
Specifically,
OE
a f a f a f a f
These relationships induce the associative and distributive
laws given later. Note that for any constant c OE -.
R

a f a f a f
EXAMPLE. The following column templates r s t X X
R
t.
Fig. 2. The template r constitutes the additive maximum of the templates
s and the template t.
2.4 Some Properties of Image
and Template Operations
The following associative and distributive laws hold for an
arbitrary image a X
OE -.
R and arbitrary templates t X X
OE -.
R
and s X X
OE -.
R
a s t a s t
a s t a s a t

a f a f
a f a f a f (12)
These results establish the importance of template decomposition

2.5 Strong Decompositions of Templates
A sequence of templates t t
e j in R -.
e j is called a
(strong) decomposition (with respect to the operation "*") of a
template
OE -.
R
OE -.
R
e j can be written in the form
In the special case where we speak of a separable template
if the support of t 1 is a one dimensional vertical array
and the support of t 2 is a one dimensional horizontal array.
EXAMPLE. The template r X X
OE -.
R
e j given in Fig. 1 represents
a separable template since this template decomposes
into a vertical strip template s X X
OE -.
R
e j and a horizontal
strip template t X X
OE -.
R
Fig. 3. Pictorial representation of a column template s and a row template
t.
2.6 Weak Decompositions of Templates
A sequence of templates t t
e j in R -.
with a strictly increasing sequence of natural numbers
K is called a (weak) decomposition (with respect to the
operation "*") of a template t X X
OE -.
R
if the template t can
be represented as follows:
We say s s
e j is a weak decomposition of a rectangular
template
OE -.
R
separable templates if each s i ,
is separable and t s s
2.7 Correspondence Between Rectangular
Templates and Matrices
Note that there is a natural bijection f from the space of all
matrices over R -. into the space of all rectangular
templates in R -.
be arbitrary and x X
c h be
such that
min , ,
min ,
The image of a matrix A OE -.
R
is defined to be
SUSSNER AND RITTER: DECOMPOSITION OF GRAY-SCALE MORPHOLOGICAL TEMPLATES USING THE RANK METHOD 5
J:\PRODUCTION\TPAMI\2-INPROD\104798\104798_1.DOC regularpaper97.dot AG 19,968 04/24/97 1:49 PM 5 11
the template t X X
OE -.
R
e j which satisfies
y
y
y y
c h
c h
K K
Henceforth, we restrict our attention to rectangular templates
whose target pixel is centered, i.e., rectangular templates
of the above form.
The theory of minimax algebra [25] examines the algebraic
structures arising from the lattice operations
"maximum," "minimum," and "addition," including the
space of all matrices over R -. together with the operation
additive maximum. The natural correspondence between
rectangular templates in t X X
OE -.
R
e j and matrices over R -.
allows us to use a minimax algebra approach in order to
study the weak decomposability of rectangular templates
into separable templates.
EXAMPLE. Let A OE R 3-3 be the matrix and u, v the vectors
given below.
A u v
F
I
F
I
c h (17)
The function f maps A to the square template
OE -.
R
e j in Fig. 1, and it maps the column vector u
to the column template s X X
OE -.
R
e j and the row vector
v to the row template t X X
OE -.
R
e j in Fig. 3.
In this section, we develop a new notion of matrix rank
within the mathematical framework of minimax algebra.
We relate this concept of matrix rank to the one given by
Cuninghame-Green [25] and derive the notion of the rank
of a morphological template.
3.1 Algebraic Structures and Operations
in Minimax Algebra
The mathematical theory of minimax algebra deals with
algebraic structures such as bands, belts, and blogs. For
example, R -. together with the operations of maximum
("/") and addition forms a belt. Cuninghame-Green defines
the matrix rank for matrices over certain subsets of the blog
R -. For our purposes it suffices to consider R, the finite
elements of R -.
Operations such as the maximum ("/"), the minimum
("Y-"), and the addition on R induce entrywise operations
- , the set of all m - n matrices over R. Minimax algebra
also defines compound operations such as "*"-
pronounced "additive maximum"-from R R
- into
- , an operation similar to the regular matrix product
known from linear algebra. (An obvious dual of this operation
is provided by the "additive minimum" operation.)
Given matrices A OE R m-k and B OE R k-n , the additive maximum
R m n is determined by
c a
ik kj
If A is a matrix in R m n
- and if u i are column vectors in R m-1
and v are row vectors in R 1-n for then the following
equivalence holds for the corresponding rectangular
template f(A), the vertical strip templates f u i
and the
horizontal strip templates f v i
A u v A u v
3.2 Linear Dependence of Vectors
A vector v OE R n is said to be linearly dependent on the vectors
OE R if and only if there exist scalars c OE R,
ce
Otherwise, the vector v OE R n is called linearly independent
from the vectors v 1 , -, v k OE R n . The vectors v 1 , -, v k OE R n
are linearly independent if each one of them is linearly independent
from the others.
EXAMPLE. Consider the following elements of R 3
F
F
F
a f , the vector v is linearly
dependent on v 1 and v 2 .
3.3 Strong Linear Independence
Vectors v v
OE R are called strongly linearly independent
(SLI) if and only if there exists a vector v OE R n such that
v has a unique representation
Since this definition does not provide a suitable criterion
for testing a collection of vectors in R n for strong linear in-
dependence, we choose to provide an alternative equivalent
definition based on the following theorem.
THEOREM 1. Vectors v v
OE R are SLI if and only if the
following inequalities hold.
where ~ v v
vfor any vector
6 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 6, JUNE 1997
J:\PRODUCTION\TPAMI\2-INPROD\104798\104798_1.DOC regularpaper97.dot AG 19,968 04/24/97 1:49 PM 6 11
c h R
COROLLARY. There are k vectors v 1 , -, v k OE R n which are SLI if
and only if k OE {1, -, n}.
3.4 Rank of a Matrix
Cuninghame-Green defines the rank of a matrix A OE R m-n as
the maximal number of SLI row vectors or, equivalently,
the maximum number of SLI column vectors. The rank of a
finite matrix A OE R m-n is less than or equal to min {m, n}.
3.5 Remarks on the Rank of a Matrix
in Minimax Algebra
The notion of (regular) linear independence is not suited to
define a rank in minimax algebra because certain dimensional
abnormalities would occur. For example, it is possible
to find k linearly independent vectors in R n for any
number k OE N. The notion of strong linear independence
gives rise to a satisfactory theory of rank and dimension
(although certain equivalences known from linear algebra
do not hold).
3.6 The Separable Rank of a Matrix
The separable rank of a matrix A OE R m-n is denoted by
defined as the minimal number r of column
vectors row vectors { v 1 , - v r } OE { R} 1 -
which permit a representation of A in the following form:
A u v
A representation of this form is called a (weak) separable decomposition
of A. We say A is a separable matrix (with respect
to the operation *) if rank sep
3.7 The Rank of a Rectangular Template
real valued matrix A, then we define
the rank of the template t X X
OE -.
R
e j as the separable rank of A.
Our interest in the rank of a morphological template is
motivated by the problem of morphological template decomposition
since the rank of a morphological template
OE -.
R
represents the minimal number of separable
templates whose maximum is t or, equivalently, the minimal
number r of column templates r X X
R
e j and row
templates s X X
R
e j such that t r s
r ie j .
In this section, we derive some theorems concerning the
separable rank of matrices which translate directly into results
about the rank of rectangular templates. These theorems
greatly simplify the proofs of the decomposition results
which we will present in the next section.
THEOREM 2. If a matrix A OE R m-n has a representation
A u v
l
le j in terms of column vectors u m
R 1 and
row vectors v l n
then A can be
expressed in the following form:
A
l
l
R 1 is given by
w a
l
, . , (26)
REMARK. Theorem 2 implies that, for any matrix A OE R m-n of
separable rank k, it suffices to know the row vectors
, , . , which permit a weak decomposition
of A into k separable matrices in order to determine
a representation of A in the form:
A w v
l
l l
R , . , (27)
Like most of the theorems established in this paper,
Theorem 2 has an obvious dual in terms of column
vectors which we choose to omit.
We now are going to introduce certain transforms which
preserve the separable matrix rank. These transforms are
suited to simplify the task of determining the separable
rank of a given matrix.
4.1 Column Permutations of Matrices
Let A OE R m-n and r be a permutation of {1, -, n}. The associated
column permuted matrix r c (A) of A with respect to r is
defined as follows:
r
c
a a a
a a a
a a a
A
a f
a f a f a f
a f a f a f
a f a f a f
F
I
4.2 Row Permutations
If r is a permutation of {1, -, m}, then we define the associated
row permuted matrix r r (A) of A OE R m-n with respect to r
as follows:
r
r
a a a
a a a
a a a
A
a f
a f a f a f
a f a f a f
a f a f a f
F
I
The multiplication of a matrix A OE R m-n by a scalar c OE R is
defined as usual. In this case, -A stands for (-1) # A.
THEOREM 3. The following transformations preserve the separable
rank of a matrix A OE R m-n :
SUSSNER AND RITTER: DECOMPOSITION OF GRAY-SCALE MORPHOLOGICAL TEMPLATES USING THE RANK METHOD 7
J:\PRODUCTION\TPAMI\2-INPROD\104798\104798_1.DOC regularpaper97.dot AG 19,968 04/24/97 1:49 PM 7 11
. column and row permutations;
. additions of separable matrices;
. scalar multiplications.
REMARK. Column and row permutations as well as additions
of separable matrices also preserve the rank of a
matrix, as defined by Cuninghame-Green. This invariance
property follows directly from the definition
of this matrix rank as the minimal number of SLI row
vectors or column vectors.
THEOREM 4. The separable rank of a finite matrix A OE R m-n is
bounded from below by the rank of A and bounded from
above by the minimal number l of linearly independent row
vectors or column vectors of A.
At this point, we are finally ready to tackle the problem of
determining weak decompositions of matrices in view of
their separable ranks. The reader should bear in mind the
consequences for the corresponding rectangular templates.
For any matrix A OE R m-n , we use the notation a(i),
-, m to denote the ith row vector of A and we use the notation
the jth column vector of A.
THEOREM 5 [20]. Let A OE R m-n be a separable matrix and {a(i) :
be the collection of row vectors of A. For each
arbitrary row vector a(i 0 ), there exist
scalars l i OE R, m, such that the following equations
are satisfied:
l
In other words, given an arbitrary index 1 - i 0 - m, each
row vector a(i) is linearly dependent on the i 0 th row vector
A.
Clearly, Li and Ritter's theorem gives rise to the following
straightforward algorithm which tests if a given matrix
over R is separable. In the separable case, the algorithm
computes a vector pair into which the given matrix can be
decomposed.
ALGORITHM 1. Let A OE R m-n be given and let a(i) denote the
ith row vector of A. The algorithm proceeds as follows
for all
Subtract a 1j from a ij .
Compare c i with a ij - a 1j . If a 1j , the matrix
A is not separable and the algorithm stops. If step
has been successfully completed, then A
is separable and A is given by c*a(1).
Note that this algorithm only involves (m - 1)n subtractions
and (m - 1)(n - 1) comparisons. Hence, the number of operations
adds up to 2(m - 1)n which implies that
the algorithm has order O(2mn).
REMARK. As mentioned earlier, the given image processing
hardware often calls for the decomposition of a given
template into 3 - 3 templates. The theorem below
shows that, in the case of a separable square template,
this problem reduces to the problem of decomposing
a column template into 3 - 1 templates as well as decomposing
a row template into 1 - 3 templates. Suppose
that the original template is of size (2n
operations per pixel are
needed when applying this template to an image. If
the template decomposes into n 3 - 3 templates, this
number of operations reduces to 9n. However, the
simple strong decomposition of the original separable
template into a row and a column template of length
especially when using
a sequential machine since only 4n operations
per pixel are required when taking advantage of this
decomposition.
THEOREM 6. Let t be a square morphological template of rank 1,
given by r is a column template and s is a
row template. The template t is decomposable into
templates if and only if r is decomposable into m - 1 templates
and s is decomposable into templates.
EXAMPLE. Let A be the real valued 5 - 5 matrix given below.
A u v
F
I
where
F
I
The template is not decomposable into two
templates since the template r = f(u) is not decomposable
into two 3 - 1 templates.
REMARK. Of course, Theorem 6 does not preclude the existence
of templates t of rank # 2 which are strongly decomposable
into 3 - 3 templates.
EXAMPLE. The following template t of rank > 1 can be written
as a *-product of two 3 - 3 templates t 1 and t 2 . See
Fig. 4 and Fig. 5.
COROLLARY. Let t be a square morphological template of rank k,
given by
-, r k are column templates and s 1 , -, s k are row tem-
plates. If the templates r 1 , -, r k are decomposable into
templates and the templates s 1 , -, s k are decomposable
then t has representation
in terms of templates t 1 , -, t k which are
strongly decomposable into templates.
8 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 6, JUNE 1997
J:\PRODUCTION\TPAMI\2-INPROD\104798\104798_1.DOC regularpaper97.dot AG 19,968 04/24/97 1:49 PM 8 11
Fig. 4. Example of a 5 - 5 template t of rank > 1 which is decomposable
into 3 - 3 templates t 1 and t 2 .
Fig. 5. Templates t 1
and t 2
which
LEMMA 1. If a matrix A OE R m-n has separable rank two, then
there exits a transform T-consisting of only row permuta-
tions, column permutations, and additions of row or column
vectors-as well as vectors u OE R m-1 and v OE R 1-n
such that T(A) can be written in the following form:
where
and 0 m-n denotes the m - n zero matrix.
LEMMA 2. Let T be a (separable) rank preserving transform as in
Theorem 3 and A OE R m-n The transform T maps row vectors
of A to row vectors of T(A), and column vectors of A
to column vectors of T(A).
THEOREM 7. A matrix A OE R m-n has separable rank two if and
only there are two row vectors of A on which all other row
vectors depend (linearly).
A similar theorem does not hold for matrices of separable
3. This fact is expressed by Theorem 8.
THEOREM 8. For every natural number k # 3, there are matrices
over R -. which are weakly *-decomposable into a product of
vector pairs, but not all of whose row vectors are linearly
dependent on a single k tuple of their row vectors.
REMARK. By Theorem 6, a matrix A OE R m-n has separable
rank two if and only if there exist two row vectors of
A-a(o), a(p) where o, p OE {1, -, m}-which allow for
a weak decomposition of A. In this case, an application
of Theorem 2 yields the following representation
of A:
A
u a v a
a f b g (35)
where
u a a i m
v a a i m
, . ,
, . ,
OE
R 111
Hence, in order to test an arbitrary matrix A OE R m-n
for weak decomposability into two vector pairs, it is
enough to compare A with (b[i] * a(i)) / (b[j] * a(j))
for all indices i, j OE {1, -, m}. Here B OE R m-n is computed
as follows:
b a a
is js
, . , (37)
ALGORITHM 2. Assume a matrix A OE R m-n needs to be decomposed
into a weak *-product of two vector pairs if
such a decomposition is possible. Considering the
preceding remarks, we are able to give a polynomial
time algorithm for solving this problem. For each
step, we include the number of operations involved in
square brackets.
Compute
2:
3:
and compare the
result with A. If C
m, then the algorithm stops yielding the following
result:
does not
have a weak decomposition into two vector pairs.
[At most 2 2
I K a f comparisons].
This algorithm involves at most a total number of m 2 (3n - 1
operations which amounts to order O(m 3 n).
EXAMPLE. Let us apply Algorithm 2 to the following matrix
A OE R 4-5 .
SUSSNER AND RITTER: DECOMPOSITION OF GRAY-SCALE MORPHOLOGICAL TEMPLATES USING THE RANK METHOD 9
J:\PRODUCTION\TPAMI\2-INPROD\104798\104798_1.DOC regularpaper97.dot AG 19,968 04/24/97 1:49 PM 9 11
F
I
We compute matrices B OE R 4-4 and C i OE R 4-5 for all
C b a
C b a
C b a
C b a
F
I
F
I
F
I
F
I
a f
a f
a f
a f
F
I
Comparing the matrices C i / C j with A for all
EXAMPLE. Let A OE R 9-9 be the following matrix, which constitutes
the maximum of a matrix in pyramid form
and a matrix in paraboloid form.
F
G G G G G G G G
I
Since matrices in paraboloid and in pyramid form are
separable, Algorithm 2 should yield a weak decomposition
of A in the form [u * a(o)] / [v * a(p)] for some vectors
u, v OE R 9 and some indices o, p OE {1, -, 9}. Indeed, if
B OE R 9-9 denotes the matrix computed by Algorithm 2,
where
a
F
G G G G G G G G
I
F
G G G G G G G G
I
a f c h
a f c h (44)
This weak decomposition of A can be used to further decompose
the square templates f(b[1] * a(1)) and f(b[3] *
templates. By Theorem 6, the templates
are decomposable into 3 - 3
templates if and only if the column templates f(b[1]) and
are decomposable into 3 - 1 templates and the row
templates f(a[1]) and f(a[3]) are decomposable into 1 - 3
templates. It is fairly easy to choose 3 - 1 templates
R
R
4, such
that
s 4 . For more complicated examples, we recommend using
one of the integer programming approaches suggested in
[17], [18], [19]. See Fig. 6 and Fig. 7. Hence, we obtain a representation
of f(b[1] * a(1)) in the form of (45).
By rearranging the templates r and s i for 4, we can
achieve a decomposition of f(b[1] * a(1)) into four 3 - 3
templates
Fig. 6. Templates of size 3 - 1 and size 1 - 3 providing a decomposition
of the template f(b[1] * a(1)).
Fig. 7. The 3 - 3 templates, providing a decomposition of the template
In a similar fashion, we are able to decompose the tem-
J:\PRODUCTION\TPAMI\2-INPROD\104798\104798_1.DOC regularpaper97.dot AG 19,968 04/24/97
plate f(b[3] * a(3)) into four 3 - 3 templates.
REMARK. The methods for decomposing rectangular morphological
templates presented in this paper can be
easily generalized to include arbitrary invariant morphological
templates which correspond to matrices
over R -.
6 CONCLUSIONS
We introduced the new theory of the separable matrix rank
within minimax algebra, which we compared to the theory
of matrix rank provided by Cuninghame-Green. The definition
of the separable rank of a matrix leads to the concept
of the rank of a rectangular morphological template, a notion
which has significance for the problem of morphological
template decomposition.
Using this terminology, the class of separable templates
represents the class of templates of rank one. A separable
templates can be strongly decomposed into a product of a
column template and a row template. Generalizing this
decomposition of separable templates, we developed a
polynomial time algorithm for the weak decomposition of a
rectangular template of rank two into horizontal and vertical
strip templates. We are currently working on an improved
version of this algorithm.
In an upcoming paper, we will show that determining
the rank of an arbitrary rectangular template is an NP complete
problem, and we will discuss the consequences for
morphological template decomposition problems in gen-
eral. Moreover, we will present a heuristic algorithm for
solving the rank problem and for finding an optimal weak
decomposition into strip templates.

ACKNOWLEDGMENT

This research was partially supported by U.S. Air Force
Contract F08635 89 C-0134.



--R

"Biomedical Image Processing,"
"Parallel 2-D Convolution on a Mesh Connected Array Processor,"
"Morphological Structuring Element Decomposition,"
"Decomposition of Convex Polygonal Morphological Structuring Elements Into Neighborhood Subsets,"
"Optimal Decomposition of Convex Morphological Structuring Elements for 4-Connected Parallel Array Processors,"
available via anonymous ftp from ftp.

"Recent Developments in
"Necessary and Sufficient Conditions for the Existence of Local Matrix Decompositions,"
"Classification of Lattice Transformations in Image Processing,"

"The P-Product and Its Applications in Signal Processing,"
"Decomposition Methods for Convolution Operators,"
"Morphological Template Decomposition With Max- Polynomials,"
Maxpolynomials and Morphological Template Decomposition
"Nonlinear Matrix Decompositions and an Application to Parallel Processing,"
"Decomposition Techniques for Gray-Scale Morphological Templates,"
"Local Decomposition of Gray-Scale Morphological Templates,"
"Global Optimization Problems in Computer Vision,"
"Decomposition of Separable and Symmetric Convex Templates,"
"Separable Decompositions and Approximations for Gray-Scale Morphological Templates,"
"Some Algorithms for Approximating Convolu- tions,"
"Proofs of Decomposition Results of Gray-Scale Morphological Templates Using the Rank Method,"
"Heterogeneous Algebras,"
Lecture Notes in Economics and Mathematical Systems
--TR

--CTR
A. Engbers , R. Van Den Boomgaard , A. W. M. Smeulders, Decomposition of Separable Concave Structuring Functions, Journal of Mathematical Imaging and Vision, v.15 n.3, p.181-195, November 2001
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
structuring element;morphology;morphological template;template rank;convolution;template decomposition