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).