In this work we are going to set up a new relationship between the L-fuzzy Concept Analysis and the Fuzzy Mathematical Morphology. Specifically we prove that the problem of finding fuzzy images or signals that remain invariant under a fuzzy morphological opening or under a fuzzy morphological closing, is equal to the problem of finding the L-fuzzy concepts of some L-fuzzy context. Moreover, since the Formal Concept Analysis and the Mathematical Morphology are the particular cases of the fuzzy ones, the showed result has also an interpretation for binary images or signals.
c 2012 by the paper authors. CLA 2012, pp. 81–92. Copying permitted only for private and academic purposes. Volume published and copyrighted by its editors.
Local Proceedings in ISBN 978–84–695–5252–0,
Universidad de M´alaga (Dept. Matem´atica Aplicada), Spain. 2.1
▲-fuzzy Concept Analysis
The Formal Concept Analysis of R. Wille [
In previous works [
In our case, to work with these L-fuzzy contexts, we have defined the derivation operators 1 and 2 given by means of these expressions: ∀A ∈ LX , ∀B ∈ LY
A1(y) = inf {I(A(x), R(x, y))}
x∈X B2(x) = inf {I(B(y), R(x, y))}
y∈Y with I a fuzzy implication operator defined in the lattice (L, ≤) and where A1 represents the attributes related to the objects of A in a fuzzy way, and B2, the objects related to all the attributes of B.
In this work, we are going to use the following notation for these derivation operators to stand out their dependence to relation R: ∀A ∈ LX , ∀B ∈ LY , we define DR : LX → LY , DRop : LY → LX
DR(A)(y) = A1(y) = inf {I(A(x), R(x, y))}
x∈X DRop (B)(x) = B2(x) = inf {I(B(y), Rop(y, x))}
y∈Y where we denote by Rop the opposite relation of R, that is, ∀(x, y) ∈ X × Y, Rop(y, x) = R(x, y).
The information stored in the context is visualized by means of the L-fuzzy concepts that are some pairs (A, A1) ∈ (LX , LY ) with A ∈ fix(ϕ), set of fixed points of the operator ϕ, being defined from the derivation operators 1 and 2 as ϕ(A) = (A1)2 = A12. These pairs, whose first and second components are said to be the fuzzy extension and intension respectively, represent a set of objects that share a set of attributes in a fuzzy way.
The set L = {(A, A1)/A ∈ fix(ϕ)} with the order relation ≤ defined as:
∀(A, A1), (C, C1) ∈ L, (A, A1) ≤ (C, C1) if A ≤ C( or A1 ≥ C1)
is a complete lattice that is said to be the L-fuzzy concept lattice [
On the other hand, given A ∈ LX , (or B ∈ LY ) we can obtain the associated L-fuzzy concept. In the case of using a residuated implication, as we do in this work, the associated L-fuzzy concept is (A12, A1) (or (B2, B21)).
Other important results about this theory are in [
A very interesting particular case of L-fuzzy contexts appears trying to
analyze situations where the objects and the attribute sets are coincident [
These are the L-fuzzy contexts that we are going to use to obtain the main results of this work. Specifically, we are going to take a complete chain (L, ≤) as the valuation set, and L-fuzzy contexts as (L, Rn, Rn, R) or (L, Zn, Zn, R).
In the first case, the L-fuzzy concepts (A, B) are interpreted as signal or image pairs related by means of R. In the second case, A and B are digital versions of these signals or images. 2.2
Mathematical Morphology
The Mathematical Morphology is a theory concerned with the processing and
analysis of images or signals using filters and operators that modify them. The
fundamentals of this theory (initiated by G. Matheron [
Mathematical Morphology in binary images and grey levels images In this theory images A from X = Rn or X = Zn (digital images or signals when n=1) are analyzed.
The morphological filters are defined as operators F : ℘(X) → ℘(X) that transform, symplify, clean or extract relevant information from these images A ⊆ X, information that is encapsulated by the filtered image F (A) ⊆ X.
These morphological filters are obtained by means of two basic operators,
the dilation δS and the erosion εS, that are defined in the case of binary images
with the sum and difference of Minkowski [
δS(A) = A ⊕ S = [ As εS(A) = A ⊖ S˘ = \ As
s∈S s∈S˘ where A is an image that is treated with another S ⊆ X, that is said to be structuring element, or with its opposite S˘ = {−x/x ∈ S} and where As represents a translation of A: As = {a + s/a ∈ A}.
The structuring image S represents the effect that we want to produce over the initial image A.
These operators are not independent since they are dual transformations with
respect to the complementation [
εS(A) = (δS(Ac))c, ∀A, S ∈ ℘(X)
We can compose these operators dilation and erosion associated with the structuring element S and obtain the basic filters morphological opening γS : ℘(X) → ℘(X) and morphological closing φS : ℘(X) → ℘(X) defined by: γS = δS ◦ εS
φS = εS ◦ δS
The opening γS and the closing φS over these binary images verifies the two conditions that characterize the morphological filters: They are isotone and idempotent operators, and moreover it is verified, ∀A, S ∈ ℘(X): a) γS(A) ⊆ A ⊆ φS(A) b) γS(A) = (φS(Ac))c
These operators will characterize some special images (the S-open and the S-closed ones) that will play an important role in this work.
This theory is generalized introducing some tools to treat images with grey
levels [
The previous definitions can be immersed in a more general framework that
considers each image as a point x ∈ L of a partially ordered structure (L, ≤)
(complete lattice), and the filters as operators F : L → L with properties related
to the order in these lattices [
Now, the erosions ε : L → L are operators that preserve the infimum ε(inf M ) = inf ε(M ), ∀M ⊆ L and the dilations δ : L → L, the supremum: δ(sup M ) = sup δ(M ), ∀M ⊆ L. The opening γ : L −→ L and the closing φ : L −→ L are isotone and idempotent operators verifying γ(A) ≤ A ≤ φ(A) .
Fuzzy Mathematical Morphology In this new framework and associated
with lattices, a new fuzzy morphological image processing has been developed [
In this interpretation, the filters are operators FS : LX → LX , where L is
the chain [
In all these cases, fuzzy morphological dilations δS : LX → LX and fuzzy
morphological erosions εS : LX → LX are defined using some operators of the
fuzzy logic [
In general, there are two types of relevant operators in the Fuzzy Mathematical Morphology. One of them is formed by those obtained by using some pairs (∗, I) of adjunct operators related by:
(α ∗ β ≤ ψ) ⇐⇒ (β ≤ I(α, ψ))
The other type are the morphological operators obtained by pairs (∗, I) related by a strong negation ′ : L → L:
α ∗ β = (I(α, β′))′, ∀(α, β) ∈ L × L
An example of one of these pairs that belongs to both types is the formed by the t-norm and the implication of Lukasiewicz.
In this paper, we work taking as (X, +) the commutative group (Rn, +) or the
commutative group (Zn, +), and as (L, ≤,′ , I, ∗), the complete chain L = [
We interpret the L-fuzzy sets A : X → L and S : X → L as n-dimensional images in the space X = Rn (or n-dimensional digital images in the case of X = Zn).
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. [
∀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}
∀x ∈ X
Then we obtain fuzzy erosion and dilation operators εS, δS : LX → LX .
Moreover, it is verified: Proposition 1. (1) If ≤ represents now the usual order in LX obtained by the order extension in the chain L, then the pair (εS, δS) is an adjunction in the lattice (LX , ≤), that is:
δS(A1) ≤ A2 ⇐⇒ A1 ≤ εS(A2) (2) If A′ is the negation of A defined by A′(x) = (A(x))′, ∀x ∈ X and if S˘ represents the image associated with S such that S˘(x) = S(−x), ∀x ∈ X, then it is verified:
εS(A′) = (δS˘(A))′, δS(A′) = (εS˘(A))′, ∀A, S ∈ LX Proof. (1) Suppose that δS(A1) ≤ A2. Then δS(A1)(x) ≤ A2(x) ∀x ∈ X. That is, S(x − y) ∗ A1(y) ≤ A2(x) ∀(x, y) ∈ X × X.
From these inequalities and from the equivalence α ∗ β ≤ γ ⇔ β ≤ I(α, γ) : and interchanging x and y, we have: and consequently
A1(y) ≤ I(S(x − y), A2(x)), ∀(x, y) ∈ X × X
A1(x) ≤ I(S(y − x), A2(y)), ∀(x, y) ∈ X × X
A1(x) ≤ inf{I(S(y − x), A2(y))/y ∈ X}, ∀x ∈ X That is: A1(x) ≤ εS(A2)(x), ∀x ∈ X that shows that A1 ≤ εS(A2).
We can prove the other implication in a similar way.
(2) Let be x ∈ X.
εS(A′)(x) = inf{I(S(y − x), A′(y))/y ∈ X} = inf{I(S˘(x − y), A′(y))/y ∈ X}
= inf{(S˘(x − y) ∗ A(y))′/y ∈ X} = (sup{(S˘(x − y) ∗ (A(y))/y ∈ X})′
= (δS˘(A)(x))′ = (δS˘(A))′(x)
The second equality is proved analogously.
⊔⊓
The erosion and dilation operators given in Definition 1 are used to construct
the basic morphological filters: the opening and the closing (see [
Definition 2. The fuzzy opening of the image A ∈ LX by the structuring element S ∈ LX is the fuzzy subset γS(A) that results from the composition of the erosion εS(A) of A by S followed by its dilation:
γS(A) = δS(εS(A)) = (δS ◦ εS)(A)
The fuzzy closing of the image A ∈ LX by the structuring element S ∈ LX is the fuzzy subset φS(A) that results from the composition of the dilation δS(A) of A by S followed by its erosion:
φS(A) = εS(δS(A)) = (εS ◦ δS)(A)
It can be proved that the operators γS and φS are morphological filters, that is, they preserve the order and they are idempotent:
A1 ≤ A2 =⇒ (γS(A1) ≤ γS(A2)) and (φS(A1) ≤ φS(A2)) Moreover, these filters verify that:
γS(A) ≤ A ≤ φS(A) ∀A ∈ LX , ∀S ∈ LX
Analogous results that those obtained for the erosion and dilation operators can be proved for the opening and closing: Proposition 2. If A′ is the negation of A defined by A′(x) = (A(x))′ ∀x ∈ X, then: γS(A′) = (φS˘(A))′, φS(A′) = (γS˘(A))′
∀A, S ∈ LX Proof. γS(A′) = δS(εS(A′)) = δS((δS˘(A))′) = (εS˘(δS˘(A)))′ = (φS˘(A))′.
The other equality can be proved in an analogous way. ⊔⊓
Since the operators γS and φS are increasing in the complete lattice (LX , ≤), by Tarski’s theorem, the respective fixed points sets are not empty. These fixed points will be used in the following definition: Definition 3. An image A ∈ LX is said to be S-open if γS(A) = A and it is said to be S-closed if φS(A) = A.
These S-open and S-closed sets provide a connection between the Fuzzy Mathematical Morphology and the Fuzzy Concept Theory, as we will see next.
For that purpose, given the complete chain L that we are using, and a commutative group (X, +), we will associate with any fuzzy image S ∈ LX , the fuzzy relation RS ∈ LX×X such that:
RS(x, y) = S(x − y), ∀(x, y) ∈ X × X
It is evident that RS′ = RS′ and, if RSop represents the opposite relation of RS, then RSop = R ˘.
S
In agreement with this last point, we can redefine the erosion and dilation as follows: εS(A)(x) = inf{I(RS(y, x), A(y))/y ∈ X}
= inf{I(RSop(x, y), A(y))/y ∈ X}, ∀x ∈ X δS(A)(x) = sup{RS(x, y) ∗ A(y)/y ∈ X}, ∀x ∈ X
With this rewriting, given the structuring element S ∈ LX , we can interpret the triple (L, X, S) as an L-fuzzy context (L, X, X, RS′ ) where the sets of objects and attributes are coincident. The incidence relation RS′ ∈ LX×X is at the same time the negation of an interpretation of the fuzzy image by the structuring element S.
We will use this representation as L-fuzzy context to prove the most important results that connect both theories: Theorem 1. Let (L, X, S) be the triple associated with the structuring element S ∈ LX . Let (L, X, X, RS ) be the L-fuzzy context whose incidence relation RS′ ∈
′ LX×X is the negation of the relation RS associated with S. Then the operators erosion εS and dilation δS en (L, X, S) are related to the derivation operators
′ DRS′ and DRS′op in the L-Fuzzy context (L, X, X, RS ) by: εS(A) = DRS′ (A′)
∀A ∈ LX δS(A) = (DRS′op (A))′ ∀A ∈ LX Proof. Taking into account the properties of the Lukasiewicz implication, for any x ∈ X, it is verified that:
εS(A)(x) = inf{I(RS(y, x), A(y))/y ∈ X} = inf{I(A′(y), RS′(y, x))/y ∈ X} = DRS′ (A′)(x)
Analogously, δS(A)(x) = sup{RS(x, y) ∗ A(y)/y ∈ X} = sup{(I(RS(x, y), A′(y)))′/y ∈ X} =
′ (inf{I(RS(x, y), A′(y))/y ∈ X})′ = (inf{I(A(y), RS (x, y))/y ∈ X})′ = (inf{I(A(y), RS′op (y, x))/y ∈ X})′ = ((DRS′op (A))(x))′ = (DRS′op (A))′(x). ⊔⊓
As a consequence, we obtain the following result which proves the connection between the outstanding morphological elements and the L-fuzzy concepts: Theorem 2. Let be S ∈ LX and let be RS ∈ LX×X its associated relation. The following propositions are equivalent: 1. The pair (A, B) ∈ LX ×LX is an L-fuzzy concept of the context (L, X, X, RS′ ),
′ where RS(x, y) = S′(x − y) ∀(x, y) ∈ X × X. 2. The pair (A, B) ∈ LX × LX is such that the negation A′ of A is S-open (γS(A′) = A ) and B is the S-erosion of A′ (that is, B = εS(A′)).
′ 3. The pair (A, B) ∈ LX × LX is such that B is S-closed (φS(B) = B) and A
is the negation of the S-dilation of B (that is, A = (δS(B))′).
Proof.
1 =⇒ 2) Let be S ∈ LX and RS ∈ LX×X its associated relation. Let us ′ consider an L-fuzzy concept (A, B) of the L-fuzzy context (L, X, X, RS ) in which RS′ is the negation of RS. Then, it is verified that B = DRS′ (A) and A = DRS′op (B), and, by the previous proposition, εS(A′) = DRS′ (A) = B.
Moreover, it is fulfilled that γS(A′) = δS(εS(A′)) = δS(B) = (DRS′op (B))′ =
A′ which proves that A′ is S-open. 2 =⇒ 3) Let us suppose that the hypothesis of 2 are fulfilled. Then, φS(B) = εS(δS(B)) = εS(δS(εS(A′))) = εS(γS(A′)) = εS(A′) = B, which proves that B is S-closed. On the other hand, from the hypothesis B = εS(A′) can be deduced that δS(B) = δS(εS(A′)) = γS(A′), and consequently, taking into account that A′ is S-open, that δS(B) = A′, and finally, A = (δS(B))′. ① In the referential set X = R2, if = (x1, x2) ∈ R2, w is a positive number and if S is the structuring binary image 3 =⇒ 1) Let (A, B) be a pair fulfilling the hypothesis of 3. Let us consider the
L-fuzzy context (L, X, X, RS′ ). Then, by the previous theorem we can deduce that (DRS′op (B)) = (δS(B))′ = A. On the other hand, applying the previous theorem and the hypothesis, DRS′ (A) = εS(A′) = εS(δS(B)) = φS(B) = B, which finishes the proof. ⊔⊓ then the associated incidence relation RSc ⊂ R2 × R2 is such that:
①RSc② ⇐⇒ ((x1 − y1)2 + (x2 − y2)2 > w2) which is irreflexive and transitive. The pair (A, B) showed in Figure 1 is a concept of the context (R2, R2, RSc), because γS(Ac) = Ac and B = εS(Ac).
Example 2. Interpretation of some open digital signals as fuzzy concepts.
It is known that the erosion εS(A) of an image A by a binary structuring
element S can be rewritten in terms of infimum of the traslations of A by elements
of S [
If X ⊆ Z and L = {0, 0.1, 0.2, ..., 0.9, 1} then, the maps A : X → L can be interpret as 1-D discrete signals. In Figure 2 there are some examples of discrete signals.
The signal in Fig 2(c) is the erosion of A′ in Fig 2(b), using a line segment of three pixels as a structuring element, the middle pixel being its origin (S is a crisp set).
(a) Discrete signal A as an L-Fuzzy set (b) Negation A′ of the discrete signal A
➎➏➐➑ (c) Discrete signal B = εS (A′)
Here, we can also find the erosions in terms of intersections of image traslations: εS (A′) = V{A′−1, A′0, A′+1}.
It can be proved that A′ verifies γS (A′) = A′. So, with A in Fig 2 the pair (A, B) with B = εS (A′) is a fuzzy concept of the context (L, Z, Z, RSc ) with the crisp incidence relation xRSc y ⇔ (x − y) ∈/ S, (that is, |x − y| > 1). The main results of this work show an interesting relation between the L-fuzzy Concept Analysis and the Fuzzy Mathematical Morphology that we want to develop in future works. So, we can apply the algorithms for the calculus of L-fuzzy concepts in Fuzzy Mathematical Morphology and vice versa.
On the other hand, we are extending these results to other type of operators as other implications, t-norms, conjunctive uninorms etc... and to some L-fuzzy contexts where the objects and the attributes are not related to signal or images. This work has been partially supported by the Research Group “Intelligent Systems and Energy (SI+E)” of the Basque Government, under Grant IT519-10, and by the Research Group “Adquisicio´n de conocimiento y miner´ıa de datos, funciones especiales y m´etodos num´ericos avanzados” of the Public University of Navarra.