=Paper=
{{Paper
|id=None
|storemode=property
|title=On Information Retrieval in Morphological Image and Signal Processing
|pdfUrl=https://ceur-ws.org/Vol-1062/paper19.pdf
|volume=Vol-1062
|dblpUrl=https://dblp.org/rec/conf/cla/AlcaldeBDFM13
}}
==On Information Retrieval in Morphological Image and Signal Processing==
https://ceur-ws.org/Vol-1062/paper19.pdf
On information retrieval in morphological image
and signal processing
C. Alcalde1 , A. Burusco2 , J.C. Dı́az3 , R. Fuentes-González2 , and J. Medina3?
1
Dpt. Matemática Aplicada. Universidad del Paı́s Vasco UPV/EHU. Spain
Email: c.alcalde@ehu.es
2
Dpt. Automática y Computación, Univ. Pública de Navarra. Spain
Email: {burusco,rfuentes}@unavarra.es
3
Dpt. of Mathematics, University of Cádiz. Spain†
Email: {juancarlos.diaz,jesus.medina}@uca.es
Abstract. Mathematical Morphology is a theory concerned with the
processing and analysis of images or signals using filters and other oper-
ators that modify them. This paper studies how the original images and
signals can be retrieved using fuzzy property-oriented concept lattices
and fuzzy relation equations.
1 Introduction
The fundamentals of mathematical morphology (initiated by G. Matheron [18]
and J. Serra [22]), are in the set theory, the integral geometry and the lattice
algebra. This methodology is used in the recent years in general contexts related
to activities as the information extraction in digital images, the noise elimination
or the pattern recognition.
The generalization of this theory, in order to consider fuzzy subsets as objects,
was given in [5–9, 16, 17] using L-fuzzy sets as images and structuring elements,
which was called fuzzy morphological image processing.
On the other hand, the fuzzy property-oriented concept lattice framework [15]
arises as a fuzzy generalization of Rough Set Theory and in which a set of objects
and a set of attributes are assumed, following the view point of Formal Concept
Analysis. This theory has been considered to solve fuzzy relation equations [12]
and important results, in order to obtain the whole set of solutions, are given.
Recently, both theories, fuzzy mathematical morphology and fuzzy property-
oriented concept lattice, have been related [1], extending the initial relation given
in [2].
In mathematical morphology, the usual procedure is, given a structuring
image, to obtain the dilation and the erosion from an initial image. But what
happen if we lose the original image or, simply, we have not got it because we
?
Corresponding author.
†
Partially supported by the Spanish Science Ministry projects TIN2009-14562-C05
and TIN2012-39353-C04, and by Junta de Andalucı́a project P09-FQM-5233.
c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA
2013, pp. 225–235, ISBN 978–2–7466–6566–8, Laboratory L3i, University of La
Rochelle, 2013. Copying permitted only for private and academic purposes.
226 Cristina Alcalde et al.
only know its corresponding dilation or erosion, how can the original image be
obtained?
This paper studies the problem of objects retrieval in the framework of math-
ematical morphology. It is usual that there is noise in the transmission of infor-
mation or, in several cases, it is easier to send a kind of image than another
one. Hence, the received object is not equal to the original one. Note that this
problem is also related to other settings, such as object recognition.
Specifically, we focus on solving the problem of obtaining the original object
A from another one received B, assuming a structuring image and that B is the
dilation or the erosion of the original image A. For that, this problem will be
written as a fuzzy relation equation and the relationship introduced in [1] and
the results given in [12] will be used to solve it.
2 Preliminaries
This section recalls the fuzzy property-oriented concept lattice framework [15],
fuzzy mathematical morphology [5–9, 16, 17], the relationship beetween them,
introduced in [1], and fuzzy relation equations [21].
2.1 L-fuzzy property-oriented concept lattice
In this framework a complete residuated lattice (L, ∨, ∧, ∗, I, 0, 1, ≤? ) is con-
sidered as algebraic structure. Moreover, a fuzzy (formal) context is assumed,
(X, Y, R), where R : X × Y → L is a fuzzy relation between the sets X and
Y , where X can be interpreted as a set of objects and Y as a set of properties
(attributes).
Given a fuzzy context (X, Y, R), two mappings R∃ : LX → LY and R∀ : LY →
X
L can be defined as:
R∃ (A)(y) = sup{A(x) ∗ R(x, y) | x ∈ X} (1)
∀
R (B)(x) = inf{I(R(x, y), B(y)) | y ∈ Y } (2)
for all A : X → L, B : Y → L, x ∈ X and y ∈ Y , where I is the residuated
implication associated with the conjunctor ∗. Examples of these operators are
given in [3, 19].
As a first result, the pair (R∃ , R∀ ) forms an isotone Galois connection [13].
Therefore, a property-oriented concept (or, a concept based on rough set theory)
of (X, Y, R) is a pair (A, B) ∈ LX × LY such that B = R∃ (A) and A = R∀ (B).
The set of all property-oriented concepts of (X, Y, R) is denoted by P(X, Y, R)
and it is a complete lattice [15], which is called the property-oriented concept
lattice of (X, Y, R) (or, the concept lattice of (X, Y, R) based on rough set the-
ory) [15]. For that isotone Galois connection (R∃ , R∀ ) and lattice P(X, Y, R)
interesting properties have been proven, e.g., in [3, 4, 13, 15].
On information retrieval in morphological image and signal processing 227
2.2 Fuzzy mathematical morphology
Fuzzy morphological image processing has been developed using L-fuzzy sets A
and S (with X = R2 or X = Z2 ) as images and structuring elements in [5–9, 16,
17]. The structuring image S represents the effect that we want to produce over
the initial image A.
Fuzzy morphological dilations δS : LX → LX and fuzzy morphological ero-
sions εS : LX → LX are defined using some operators of the fuzzy logic. In
the literature (see [6, 9, 14, 17]) erosion and dilation operators are introduced
associated with the residuated pair (∗, I) as follows:
If S : X → L is an image that we take as structuring element, then we consider
the following definitions associated with (L, X, S)
Definition 1. [6] The fuzzy erosion of the image A ∈ LX by the structuring
element S is the L-fuzzy set εS (A) ∈ LX defined as:
εS (A)(x) = inf{I(S(y − x), A(y)) | y ∈ X} for all x ∈ X
The fuzzy dilation of the image A by the structuring element S is the L-fuzzy
set δS (A) defined as:
δS (A)(x) = sup{S(x − y) ∗ A(y) | y ∈ X} for all x ∈ X
From these definitions arise two mappings which will be called the fuzzy
erosion and dilation operators εS , δS : LX → LX .
2.3 Relationship between both theories
In [1] these previous theories were related. For that, first of all, any fuzzy image
S ∈ LX was associated with the fuzzy relation RS ∈ LX×X , defined as:
RS (x, y) = S(y − x)
for all x, y ∈ X. Hence, the fuzzy erosion and dilation of an L-fuzzy subset A of
X are written as follows:
εS (A)(x) = inf{I(RS (x, y), A(y)) | y ∈ X}
δS (A)(x) = sup{RS (y, x) ∗ A(y) | y ∈ X}
and the following results were proved.
Proposition 1. Let (L, X, S) be the triple associated with the structuring ele-
ment S ∈ LX . Let (L, X, X, RS ) be the L-fuzzy property-oriented context whose
incidence relation is the relation RS associated with S. Then the erosion εS and
dilation δS operators in (L, X, S) are related to the derivation operators (RS )∀
and (RS )∃ in the L-fuzzy property-oriented context (L, X, X, RS ) by:
εS (A) = (RS )∀ (A)
δS (A) = (RS )∃ (A)
for all A ∈ LX .
228 Cristina Alcalde et al.
This relation provides that the dilation and erosion have the properties of
the isotone Galois connection (R∃ , R∀ ). The following result shows the connec-
tion between the outstanding morphological elements and the L-fuzzy property-
oriented concepts.
Theorem 1. Let S ∈ LX and its associated relation RS ∈ LX×X , the following
statements are equivalent:
1. The pair (A, B) ∈ LX × LX is an L-fuzzy property-oriented concept of the
context (L, X, X, RS ).
2. A is S-closed (i.e. εS ◦ δS (A) = A) and B is the S-dilation of A.
3. B is S-open (i.e. δS ◦ εS (B) = B) and A is the S-erosion of B.
2.4 Systems of fuzzy relation equations
Systems of fuzzy relation equations have been widely studied, for instance in [10,
11, 20]. This section recalls these kind of systems for which a residuated lattice
(L, ∨, ∧, ∗, I, 0, 1, ≤) is fixed.
A system of fuzzy relation equations with sup-∗-composition (SFRE∗), is the
following system of equations
_
Ai ◦ R = Bi , or (Ai (u) ∗ R(u, v)) = Bi (v), i ∈ {1, . . . , n} (3)
u∈U
where R ∈ LU ×V is an unknown fuzzy relation, A1 , . . . , An ∈ LU and B1 , . . . , Bn ∈
LV . Its counterpart is a system of fuzzy relation equations with inf-I-composition
(SFREI), that is,
^
A∗j C R = Dj or I(Aj (v), R(u, v)) = Dj (u), j ∈ {1, . . . , m} (4)
v∈V
considered with respect to an unknown fuzzy relation R ∈ LU ×V and the fuzzy
subsets A∗1 , . . . , A∗m ∈ LV and D1 , . . . , Dm ∈ LU .
Given the universes U = {u1 , . . . , um } and V = {v1 , . . . , vn }, an unknown
fuzzy relation R ∈ LU ×V and two arbitrarily chosen fuzzy subsets of respective
universes A1 . . . , An ∈ LU , B1 , . . . , Bn ∈ LV . If an element of V is fixed, v ∈ V ,
Ai (uj ) = aij for i ∈ {1, . . . , n}, j ∈ {1, . . . , m}, R(uj , v) = xj , Bi (v) = bi , then
System (3) can be written as
a11 ∗ x1 ∨ · · · ∨ a1m ∗ xm = b1
.. .. .. .. (5)
. . . .
an1 ∗ x1 ∨ · · · ∨ anm ∗ xm = bn
Consequently, for each v ∈ V , we obtain a column of R, thus, solving n
SFRE∗ systems, we will obtain the unknown relation. In order to obtain a SFREI
system where the considered universes U , V and the unknown fuzzy relation
R ∈ LU ×V are as in the previous system, an element of U is fixed, u ∈ U , fuzzy
On information retrieval in morphological image and signal processing 229
subsets A∗1 , . . . , A∗m ∈ LV , D1 , . . . , Dm ∈ LU are assumed, such that A∗j (vi ) = aij
for i ∈ {1, . . . , n}, j ∈ {1, . . . , m}, R(u, vi ) = yi and Dj (u) = dj . Therefore,
System (4) can be written as
I(a11 , y1 ) ∧ · · · ∧ I(an1 , yn ) = d1
.. .. .. .. (6)
. . . .
I(a1m , y1 ) ∧ · · · ∧ I(anm , yn ) = dm
Therefore, for each u ∈ U , we obtain a row of R, thus, solving m SFRE→
systems, the unknown relation will be obtained.
3 Images and signals retrieval
This section introduces an application of fuzzy relation equation to objects re-
trieval in the fuzzy mathematical morphology setting. From the relationship be-
tween fuzzy mathematical morphology and fuzzy property-oriented concept lat-
tice, recalled in Section 2.3, and the relationship between fuzzy property-oriented
concept lattice and fuzzy relation equations [12], we will solve the problem of
obtaining the original object A : X → L from another one received B : X → L
and a fixed structuring image S : X → L.
Specifically, given an image B : X → L, we can consider a structuring image
S : X → L and ask if there exists A : X → L such that δS (A) = B and, if there
exists, how to obtain it. Analogously, for each image A : X → L, we can ask if
there exists B : X → L such that εS (B) = A, for a structured image S, and, if
there exists, how to obtain it.
First of all, we will write this mathematical morphology problem in terms of
fuzzy relation equations.
Given a finite subset X0 = {x1 , . . . , xn } of X, an image B : X0 → L and a
structuring image S : X0 → L, if we want to obtain an image A : X0 → L such
that δS (A) = B, then we need to solve the following system:
RS (x1 , x1 ) ∗ A(x1 ) ∨ · · · ∨ RS (xn , x1 ) ∗ A(xn ) = b1
.. .. .. .. (7)
. . . .
RS (x1 , xn ) ∗ A(x1 ) ∨ · · · ∨ RS (xn , xn ) ∗ A(xn ) = bn
in which B(xi ) = bi , for all i ∈ {1, . . . , n}.
Analogously, given an image A : X0 → L and a structuring image S : X0 → L,
obtaining an image B : X0 → L, such that εS (B) = A, is equivalent to solve the
system:
I(RS (x1 , x1 ), B(x1 )) ∧ · · · ∧ I(RS (x1 , xn ), B(xn )) = a1
.. .. .. .. (8)
. . . .
I(RS (xn , x1 ), B(x1 )) ∧ · · · ∧ I(RS (xn , xn ), B(xn )) = an
Next, several results will be presented in the fuzzy mathematical morphology
framework, based on the properties introduced in [12]. The first one is about the
solvability of Systems (7) and (8).
230 Cristina Alcalde et al.
Theorem 2. Given a finite subset X0 ⊆ X and B ∈ LX0 , defined by B(xi ) = bi ,
for each i ∈ {1, . . . , n}. System (7) can be solved if and only if B is S-open in
X0 . In that case, εS (B) ∈ LX0 is the greatest solution.
Analogously, given A ∈ LX0 , defined by A(xi ) = ai , for each i ∈ {1, . . . , n}.
System (8) can be solved if and only if A is S-closed in X0 . In that case, δS (A) ∈
LX0 is the least solution.
As a consequence, if the values bi satisfy that δS (A)(xi ) = bi ∈ L, for all i ∈
{1, . . . , n}, then we can find a solution A ∈ LX0 of System (7). Analogously, if
εS (B)(xi ) = ai ∈ L is known for all i ∈ {1, . . . , n}, then we can find B ∈ LX0
solving System (8).
The second result relates the independent term and greatest solution to a
property-oriented concept.
Theorem 3. System (7) can be solved if and only if (εS (B), B) is an L-fuzzy
property-oriented concept of the context (L, X0 , X0 , RS ), where B ∈ LX0 is de-
fined by B(xi ) = bi , for all i ∈ {1, . . . , n}.
Similarly, System (8) can be solved if and only if (A, δS (A)) is an L-fuzzy
property-oriented concept of the context (L, X0 , X0 , RS ), where A ∈ LX0 is de-
fined by A(xi ) = ai , for all i ∈ {1, . . . , n}.
Now, we present an application to digital signals.
Example 1. Let us assume the set X = {0, 1, 2, . . . , 21, 22} ⊆ Z, the linear struc-
ture L = {0, 0.1, 0.2, . . . , 0.9, 1}, the mapping B : X → L, which is represented in
Figure 1, and the structuring set S = {−1, 0, 1}. Note that B can be interpreted
as a 1-D discrete signal.
L 1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0 2 4 6 8 10 12 14 16 18 20 22
X
Fig. 1. Discrete signal received
From this environment a system of fuzzy relation equations similar to Sys-
tem (7) is considered, in order to obtain a signal A with dilation B.
On information retrieval in morphological image and signal processing 231
First of all, we need to check if this system has a solution. Hence, we consider
the context (L, X, X, RS ), where the fuzzy relation RS ⊆ X × X is defined, for
each (x, y) ∈ X × X, as
(
1 if |y − x| ≤ 1
RS (x, y) = S(y − x) =
0 otherwise
Since the signal B is S-open in X, that is (δS ◦ εS )(B) = B, by Theorems 2
and 3, we have that the considered system has, at least, one solution and the
greatest solution Ag is εS (B), which is given in Figure 2 and defined as
εS (B)(x) = inf{I(RS (x, y), B(y)) | y ∈ X} = inf{B(y) | |y − x| ≤ 1}
for all x ∈ X. Moreover, (Ag , B) is a fuzzy property-oriented concept.
S =
−1 1
L 1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0 2 4 6 8 10 12 14 16 18 20 22
X
Fig. 2. Greatest solution
It is clear, in Example 1, that the original signals A may not be the greatest
solution, but another one of the proposed system. In order to obtain the whole
set of solutions the following result is introduced and can be proven from [12].
Theorem 4. Given an S-open object B ∈ LX0 , if A ∈ LX0 is the original object,
such that δS (A) = B, then either A0 < A ≤ εS (B) for some (A0 , B 0 ) lower
neighbour of (εS (B), B) in P(X0 , X0 , RS ); or A < εS (B) and A is incomparable
with A0 , for all (A0 , B 0 ) lower neighbour of (εS (B), B) in P(X0 , X0 , RS ).
Analogously, given an S-closed object A ∈ LX0 , if B ∈ LX0 is the original ob-
ject, such that εS (B) = A, then either δS (A) ≤ B < B 0 for some upper neighbour
(A0 , B 0 ) of (A, δS (A)) in P(X0 , X0 , RS ); or δS (A) < B and B is incomparable
with B 0 , for all (A0 , B 0 ) upper neighbour of (A, δS (A)) in P(X0 , X0 , RS ).
232 Cristina Alcalde et al.
Therefore, Theorem 4 can be applied in order to obtain the whole set of
solutions of the system given in Example 1. However, we need to remark that,
since straightforward εS (B) ≤ B, we have that Ag is the solution closest to B.
Hence, considering the greatest solution can be a good election.
The following example focus on images retrieval.
Example 2. We consider a two dimensional pixelated image. Hence, X = Z2 ,
L = {0, 1} and the mappings A : Z2 → L are interpreted as two dimensional
images. The elements of X are denoted as x = (x1 , x2 ) ∈ R2 .
In this case, the image B : Z2 → L, given in Figure 3, is obtained and we
want to retrieve the original image or a good approximation.
Fig. 3. Initial image
The structuring binary image S is the unit ball:
S = {(x1 , x2 ) ∈ Z × Z | x1 + x2 ≤ 1}
given in Figure 4.
Fig. 4. Structuring set
Now, we consider a System (7) and a context ({0, 1}, Z2 , Z2 , RS ), where the
associated incidence relation RS ⊆ Z2 × Z2 is defined, for each x = (x1 , x2 ),
On information retrieval in morphological image and signal processing 233
y = (y1 , y2 ), as
(
1 if (y1 − x1 ) + (y2 − x2 ) ≤ 1
RS (x, y) = S(y − x) =
0 otherwise
Therefore, by the previous results, the greatest solution Ag : Z2 → L, asso-
ciated with B and the structuring image, is the best approximation of B. That
is, the image closer to B. This image is given in Figure 5 and it is defined as:
Fig. 5. Greatest solution
εS (B)(x) = (RS )∀ (B)(x)
= inf{I(RS (x, y), B(y) | y ∈ X}
= inf{B((y1 , y2 )) | (y1 − x1 ) + (y2 − x2 ) ≤ 1}
0 if there exists (y1 , y2 ) ∈ Z2 such that B((y1 , y2 )) = 0
= and (y1 − x1 ) + (y2 − x2 ) ≤ 1
1 otherwise
By Theorem 3, the pair (A, B) is a property-oriented concept of the context
({0, 1}, Z2 , Z2 , RS ). However, in this case, the considered original image is not
the greatest solution Ag but a solution less than it. This is given in Figure 6.
This is not a problem, but it shows that it is also interesting to compute the
whole set of solutions. Theorem 4 provides an interesting mechanism to get all
the solutions of Systems (7) and (8), although another more operative results
will be studied in the future.
4 Conclusions and future work
In mathematical morphology, the usual procedure is, given a structuring image,
to obtain the dilation and the erosion of an original image. This paper have
234 Cristina Alcalde et al.
Fig. 6. Original image
studied the opposite problem, that is, given a fuzzy object B : X → L and a
structuring object S : X → L, find out the original object A : X → L such that
B is the dilation of A, δS (A) = B, or the erosion of A, εS (A) = B, and, if there
exists, how to obtain it.
We have shown that this problem is associated with solving systems of fuzzy
relation equations. Therefore, the results given in [12] and the relationship intro-
duced in [1] have been used to obtain the original image or a good approximation.
Moreover, we have introduced some results focus on searching the whole set of
possible original images.
In the future, more properties and applications will be studied, for instance
in object recognition.
References
1. C. Alcalde, A. Burusco, J. C. Dı́az, R. Fuentes-González, and J. Medina-Moreno.
Fuzzy property-oriented concept lattices in morphological image and signal pro-
cessing. Lecture Notes in Computer Science, 7903:246–253, 2013.
2. C. Alcalde, A. Burusco, and R. Fuentes-González. An interpretation of the l-fuzzy
concept analysis as a tool for the morphological image and signal processing. In
Proc. of CLA 2012, pages 81–92, 2012.
3. E. Bartl, R. Bělohlávek, J. Konecny, and V. Vychodil. Isotone galois connections
and concept lattices with hedges. In 4th International IEEE Conference “Intelli-
gent Systems”, pages 15.24–15.28, 2008.
4. R. Bělohlávek. Concept lattices and order in fuzzy logic. Annals of Pure and
Applied Logic, 128:277–298, 2004.
5. I. Bloch. Duality vs. adjunction for fuzzy mathematical morphology and general
form of fuzzy erosions and dilations. Fuzzy Sets and Systems, 160(0):1858–1867,
2009.
6. I. Bloch and H. Maı̂tre. Fuzzy mathematical morphologies: a comparative study.
Télécom Paris 94D001, 1994.
On information retrieval in morphological image and signal processing 235
7. P. Burillo, N. Frago, and R. Fuentes-González. Inclusion grade and fuzzy implica-
tion operators. Mathware & Soft Computing, VIII(0):31–46, 2001.
8. P. Burillo, R. Fuentes-González, and N. Frago. Inclusion grade and fuzzy implica-
tion operators. Fuzzy Sets and Systems, 114(0):417–429, 2000.
9. B. De Baets. Fuzzy morphology: a logical approach. In B. Ayyub and M. Gupta,
editors, Uncertainty Analysis, Engineering and Science: Fuzzy Logic, Statistics and
neural network Approach, pages 53–67. Kluwer Academic Publishers, 1997.
10. B. De Baets. Analytical solution methods for fuzzy relation equations. In D. Dubois
and H. Prade, editors, The Handbooks of Fuzzy Sets Series, volume 1, pages 291–
340. Kluwer, Dordrecht, 1999.
11. A. Di Nola, E. Sanchez, W. Pedrycz, and S. Sessa. Fuzzy Relation Equations
and Their Applications to Knowledge Engineering. Kluwer Academic Publishers,
Norwell, MA, USA, 1989.
12. J. C. Dı́az and J. Medina. Solving systems of fuzzy relation equations by fuzzy
property-oriented concepts. Information Sciences, 222:405–412, 2013.
13. G. Georgescu and A. Popescu. Non-dual fuzzy connections. Arch. Math. Log.,
43(8):1009–1039, 2004.
14. J. Goutsias and H. Heijmans. Fundamenta morphologicae mathematicae. Funda-
menta Informaticae, 41(0):1–31, 2000.
15. H. Lai and D. Zhang. Concept lattices of fuzzy contexts: Formal concept analysis
vs. rough set theory. International Journal of Approximate Reasoning, 50(5):695–
707, 2009.
16. P. Maragos. Lattice image precessing: A unification of morphological and fuzzy
algebric systems. Journal of Mathematical Imaging and Vision, 22(0):333–353,
2005.
17. M. Mas, M. Monserrat, and J. Torrens. S-implications and r-implications on a
finite chain. Kybernetika, 40(1):3–20, 2004.
18. G. Matheron. Random Sets and Integral Geometry. Wiley, 1975.
19. J. Medina. Multi-adjoint property-oriented and object-oriented concept lattices.
Information Sciences, 190:95–106, 2012.
20. I. Perfilieva and L. Nosková. System of fuzzy relation equations with inf-→ com-
position: Complete set of solutions. Fuzzy Sets and Systems, 159(17):2256–2271,
2008.
21. E. Sanchez. Resolution of composite fuzzy relation equations. Information and
Control, 30(1):38–48, 1976.
22. J. Serra. Image Analysis and Mathematical Morphology. Academic Press, I (fourth
printing 1990) and II (second printing 1992).