Mathematical Morphology is a theory concerned with the processing and analysis of images or signals using filters and other operators 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. ? 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.
The fundamentals of mathematical morphology (initiated by G. Matheron [
The generalization of this theory, in order to consider fuzzy subsets as objects,
was given in [
On the other hand, the fuzzy property-oriented concept lattice framework [
Recently, both theories, fuzzy mathematical morphology and fuzzy
propertyoriented concept lattice, have been related [
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 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. 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 mathematical morphology. It is usual that there is noise in the transmission of information 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 [
This section recalls the fuzzy property-oriented concept lattice framework [
L-fuzzy property-oriented concept lattice In this framework a complete residuated lattice (L, ∨, ∧, ∗, I, 0, 1, ≤?) is considered 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 → LX can be defined as:
R∃(A)(y) = sup{A(x) ∗ R(x, y) | x ∈ X}
R∀(B)(x) = inf{I(R(x, y), B(y)) | y ∈ Y }
(1)
(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 [
As a first result, the pair (R∃, R∀) forms an isotone Galois connection [
The set of all property-oriented concepts of (X, Y, R) is denoted by P(X, Y, R)
and it is a complete lattice [
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 [
Fuzzy morphological dilations δS : LX → LX and fuzzy morphological
erosions εS : LX → LX are defined using some operators of the fuzzy logic. In
the literature (see [
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. [
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 [
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 element 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 .
This relation provides that the dilation and erosion have the properties of the isotone Galois connection (R∃, R∀). The following result shows the connection between the outstanding morphological elements and the L-fuzzy propertyoriented 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 [
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} u∈U (3) 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,
Aj∗ 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 A1∗, . . . , 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
... ... ... ... an1 ∗ x1 ∨ · · · ∨ anm ∗ xm = bn (5)
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 subsets A1∗, . . . , A∗m ∈ LV , D1, . . . , Dm ∈ LU are assumed, such that Aj∗(vi) = aij for i ∈ {1, . . . , n}, j ∈ {1, . . . , m}, R(u, vi) = yi and Dj(u) = dj. Therefore, System (4) can be written as (6) (7) (8) I(a11, y1) ∧ · · · ∧ I(an1, yn) = d1
... ... ... ...
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.
This section introduces an application of fuzzy relation equation to objects
retrieval in the fuzzy mathematical morphology setting. From the relationship
between fuzzy mathematical morphology and fuzzy property-oriented concept
lattice, recalled in Section 2.3, and the relationship between fuzzy property-oriented
concept lattice and fuzzy relation equations [
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
... ... ... ...
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
... ... ... ...
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 [
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 defined 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 defined by A(xi) = ai, for all i ∈ {1, . . . , n}.
Example 1. Let us assume the set X = {0, 1, 2, . . . , 21, 22} ⊆ Z, the linear structure 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.
From this environment a system of fuzzy relation equations similar to System (7) is considered, in order to obtain a signal A with dilation B.
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
RS(x, y) = S(y − x) = 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 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, B0) lower neighbour of (εS(B), B) in P(X0, X0, RS); or A < εS(B) and A is incomparable with A0, for all (A0, B0) 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 object, such that εS(B) = A, then either δS(A) ≤ B < B0 for some upper neighbour (A0, B0) of (A, δS(A)) in P(X0, X0, RS); or δS(A) < B and B is incomparable with B0, for all (A0, B0) upper neighbour of (A, δS(A)) in P(X0, X0, RS).
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.
S = {(x1, x2) ∈ Z × Z | x1 + x2 ≤ 1} given in Figure 4.
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),
RS (x, y) = S(y − x) = (1 0 if (y1 − x1) + (y2 − x2) ≤ 1 otherwise
Therefore, by the previous results, the greatest solution Ag : Z2 → L, associated 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: 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
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 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 [
In the future, more properties and applications will be studied, for instance in object recognition.