Capturing Approximate Relationships 
Using Fuzzy Set Dominance Relations 

LES M. SZTANDERA
Computer Information Systems
Philadelphia University
Philadelphia, PA 19144
USA
http://Faculty.PhilaU.edu/SztanderaL

Abstract: - Land use planning, particularly in suburban areas, is a specialized spatial resource allocation problem. Spatial relationships between regions in an image play an important role in scene understanding. When the objects in a scene are represented by crisp sets, the all-or-nothing definitions of the subsets actually add to the problem of generating relational descriptions.We believe that definitions of spatial relationships based on fuzzy set theory, coupled with a fuzzy segmentation could produce realistic results. This paper introduces spatial relationships among fuzzy subsets of an image plane. The idea is to project the fuzzy subsets onto two orthogonal coordinate axes and, subsequently, utilize fuzzy set dominance relations to capture the approximate relationships. Simulation results are provided to corroborate the theory.

Key-Words: - Spatial modeling, Fuzzy sets, Fuzzy dominance relation, Scene understanding, Land use classification

1	Introduction
Land use planning, particularly in suburban areas, is a specialized spatial resource allocation problem. The challenge for land architects and their advisors is to formulate complex, spatially and temporally interdependent patterns of land use to achieve multiple, non-commensurable and frequently  conflicting goals. It is the need to be able to generate a range of alternative land use plans (with predictable characteristics) to support the land architect in the decision making process, that  has  led us  to  explore  the  potential  of  fuzzy sets and genetic  algorithms as land  use planning tools [1,2]#. The problem of specifying spatial relations between objects in a scene is a subpart of the much more general problem of picture description. Our task logically begins with a two-dimensional encoding of a scene as a picture, which is of course a basic kind of description. We desire to transform this into some "higher level" specification of what it is a picture of, with respect to the limited semantic world of spatial relations. A first step in this process would be to segment the picture into what we call objects. Those objects will hopefully correspond to what would strike an observer as the separable parts of the scene. Objects are complex entities composed of lines, edges and regions in various relations and with various properties, e.g. shape, size and texture. Our picture description will consist of objects, or the constellation of relations and properties representing objects, and the relations between them.
We delineate two types of relations between objects: those involving comparison of the properties of objects (larger, darker, smoother), and those involving their relative position (above, near, to the left of).
The latter could be considered a subset of the former if the location of an object were part of its property list, but because our concern is with spatial relations, we will find it convenient to maintain the distinction, and limit ourselves to the relative position relations. 

2   Problem Formulation
Spatial relationships between regions in an image play an important role in scene understanding. Humans are able to quickly ascertain the relationship between two objects, for example “B is to the right of A”, or “B is in front of A”, but this has turned out to be a somewhat illusive task for automation [1,2].

2.1	Projections
The idea is to project the fuzzy subsets onto two orthogonal coordinate axes and to utilize fuzzy set theoretic dominance relations to capture the approximate relationships. Similar projections were proposed by Koczy, as reported in [2].
Let A be a fuzzy subset of an image. Then A  U x V, where U is the first spatial coordinate axis and V is the second one. In our case, both U and V are subsets of real numbers (assumed to be the interval [0, 1] for convenience). Then A(x, y) is a 2D fuzzy set in U x V. The projection of A onto U, denoted AU is that fuzzy subset of U given by 
Au(x) = supy { A(x,y) }
for each x  U. 
A similar equation defines the projection of A onto V, that is 
Av(y) = supx { A(x,y) }
for each y  V. 
For a fuzzy subset C of U, the -cut C is defined by 
C= { x  U | c (x)   } 
for   [0, 1] . 
When =0, the inequality is usually considered to be strict and the C is called the support of C. 

2.1.1 Definitions of Spatial Relations for Fuzzy Objects 

Once the two fuzzy subsets A and B have been projected onto the U and V axes, methods must be defined to access their relative position. 
In this paragraph we introduce definitions for spatial relations. 

Definition 2.1.  We say that subset A is to the right of subset B if the projection of A onto the U axis dominates the projection of B, while the projections onto the V axis are (ideally) identical. In other words, A() should stay near zero for all  (especially for small ). 

Definition 2.2.  We say that subset A is to the left of subset B if the projection of B onto the U axis dominates the projection of A, while the projections onto the V axis are (ideally) identical. In other words, v () should stay near zero for all  (especially for small ). 

Definition 2.3.  We say that subset A is above subset B if the projection of A onto the V axis dominates the projection of B, while the projections onto the U axis are (ideally) identical. In other words, U() should stay near zero for all  (especially for small ) . 

Definition 2.4.  We say that subset A is below subset B if the projection of B onto the V axis dominates the projection of A, while the projections onto the U axis are (ideally) identical. In other words the grade of membership of an alpha-cut, U(), should stay near zero for all  (especially for small ). 

If we had a third coordinate axis W, that is, if we considered a three dimensional case, we could define spatial relations “in front of" and "behind". Definitions 2.5 and 2.6 are for these relations. As our concern is in two-dimensional cases we give them here just for completeness. 

Definition 2.5.  We say that subset A is in front of subset B if the projection of A onto the W axis dominates the projection of  B, while the projections onto the U axis are (ideally) identical.
In other words, U() should stay near zero for all  (especially for small ).

Definition 2.6.  We say that subset A is behind subset B if the projection of B onto the W axis dominates the projection of A, while the projections onto the U axis are (ideally) identical. In other words, U() should stay near zero for all  (especially for small ).

Definition 2.7. We say that subsets A is inside subset B if the support of A is contained in the support of B.

Definition 2.8.  We define that subset A is outside subset B if subset B is inside subset A.

Notice that we can make this assumption as outside relation is symmetric and transitive, and it has a semantic inverse defined above. Properties of spatial relations are explained next.

2.1.2 Properties of Spatial Relations for Fuzzy Objects

For the case of interest, let a set X is the set of all fuzzy objects (i.e. fuzzy subsets) of an image. Then, a fuzzy binary relation among the elements of the set X is denoted by R(X,X) or R(X2) and is a subset of X x X =X2.

Various significant types of relations R(X,X) are distinguished on the basis of three different characteristic properties: reflexivity, symmetry, and transitivity. 

First, let us consider crisp relations [7]. A crisp relation R(X,X) is reflexive if and only if (A,A)  R for every A  X, that is, if every element of X is related to itself. Otherwise, R(X,X) is called irreflexive. If (A,A)  R for every A  X, the relation is called anti-reflexive. 

A crisp relation R(X,X) is symmetric if and only if for every (A,B)  R, it is also the case that (B,A)  R, where A, B  X. Thus, whenever an element A is related to an element B through a symmetric relation, then B will also be related to A. If this is not the case for each A, B  X, then the relation is called asymmetric. If (A,B)  R and (B,A)  R implies A = B, then the relation is called anti-symmetric. If either (B,A)  R or (A,B)  R, whenever A  B, then the relation is called strictly anti-symmetric. 

A crisp relation R(X,X) is called transitive if and only if (A,C)  R whenever both (A,B) R and (B,C)  R for at least one BX. In other words, the relation of A and B to C implies the relation of A to C in a transitive relation. A relation that does not satisfy this property is called non-transitive. If (A,C) R whenever both (A,B)  R and (B,C)  R, then the relation is called anti-transitive. 

The properties of reflexivity, symmetry and transitivity can be extended for fuzzy relations R(X,X), by defining them in terms of the membership function of the relation [7]. Thus R(X,X) is reflexive if and only if
R(A, A) = 1
for all A  X. If this is not the case for some A  X, then the relation is called irreflexive; if it is not satisfied for all A  X, the relation is called anti-reflexive. A weaker form of reflexivity, referred to as -reflexivity, is sometimes defined by requiring that
R(A, A)  
where 0 <  < 1.

A fuzzy relation is symmetric if and only if
R(A, B) =R(B, A)
for all A, B  X. Whenever this equality is not satisfied for some A, B  X, the relation is called asymmetric. If the equality fails to hold for all the members of the support of the relation, then the relation is called anti-symmetric, and if it is not satisfied for all A, B  X, then the relation is called strictly anti-symmetric.

A fuzzy relation R(X,X) is transitive (or, more specifically, max-min transitive) if and only if
R(A,C)  maxyY min [R (A,B), R (B,C)]
is satisfied for each pair (A, C)  X2. A relation failing to satisfy this inequality for some members of X is called non-transitive, and if
R(A,C) < maxyY min [R (A,B), R (B,C)]
for all (A, C)  X2 , then the relation is called anti-transitive.

Transitivity of fuzzy relations can be defined in various ways alternative to the form given above. A second common form is known as the max-product transitivity and is defined by
R(A,C)  maxyY [R (A,B), R (B,C)]
for all (A,C)  X2.

Let’s consider the following example: Let R be the fuzzy relation defined on the set of all fuzzy subsets of an image and representing the concept "very near". We may assume that a subset is certainly (i.e., to a degree of 1) very near to itself. The relation is therefore reflexive. Furthermore, if subset A is very near to subset B, then B is certainly very near to A to the same degree. Therefore, the relation is also symmetric. Finally, if subset A is very near to subset B to some degree, say .7, and subset B is very near to subset C to some degree, say .8, it is possible (although not necessary) that subset A is very near to subset C to a smaller degree, say .5. Therefore, the relation is non-transitive.

The definitions 2.1-2.8 are for anti-symmetric and transitive relations, that is, TO THE LEFT (RIGHT) OF, IN FRONT OF (BEHIND), ABOVE (BELOW), INSIDE (OUTSIDE). Each of these relations has a semantic inverse.

After defining the separation measure in the next paragraph, we will be able to define symmetric relations NEAR (FAR). They have semantic inverses, as well. We will also be able to define a reflexive relation TOUCHING.

2.1.3  Separation Measure

Let AU, BU, AV, BV be the projections of A and B onto U and V respectively. Since these projections are fuzzy numbers (considering convex objects only), their -cuts are intervals, i.e.

For the projections of A and B onto the U axis, the -separation of A and B is defined by [2]:

where:

Now,  is the ratio of the square of the difference between the midpoints of the -cuts, and the square of the sum of  half-widths of these intervals. Similar equations are used for the projection of A and B onto the V axis.

Definition 2.9.  We say that A and B are -separated if  >1
Definition 2.10. We say that A and B are -just separated if  =1
Definition 2.11. We say that A and B are -overlapping if  < 1.

Theorem 2.1. 	i) AU and BU are -separated if and only if

ii) AU and BU are -just separated if and only if

iii) AU and BU are -overlapping if and only if

Proof: The proof follows easily from the geometric interpretation of the numerator of the separation measure given above.

The value of these definitions and the theorem is twofold. They incorporate the fuzziness in the description of image regions, i.e., they use fuzzy subsets of the plane. Secondly, they deal with the ambiguity of defining spatial relationships in the plane. By this we mean that it is possible that parts of the two  sets can overlap (small ) and yet be well separated for large . 

The values of  can get arbitrarily large as the widths of the level set intervals get small. In order to create a fuzzy membership function, we will map the interval [0, ) into [0, 1] by an "S-shaped function" [2] as follows. For a given , suppose  and  (Recall that we have scaled the domain of the image into the unit square), then = 16. This amount of separation (or more) will be considered complete, i.e., () = 1 if   16. Also we will require that (0) = 0, (1) = 0.5, and (16) = 0. Such a function is defined in our case by:
 
    	   0.5 S2	     for 0  S  1
(S) =	  -0.0022 S2 + 0.0711S + 0.4311			                             for 1 < S  16
	                 1	for S >16

We can now define TOUCHING relation.

Definition 2.12. We define that subset A is touching subset B if the separation measure between subsets A and B equals 1 in one projection, and equals 0 in the other one, that is () = 0 and () = 0.5 (or vice versa).

Definition 2.13. We define that subset A is near subset B if 0.5 < ()  0.75. (Similarly for the projections onto the V axis).

Definition 2.14. We define that subset B is far from subset A if () > 0.75. (Similarly for the projections onto the V axis).

It should be mentioned that a similar idea was explored by Koczy, as reported in [2], however neither separation measure nor a function of it was considered there.

3   Model for Spatial Relationships

The model for given spatial relationships can now be defined from the fuzzy subsets U and V of [0, 1]. For example, to model the relationship "A IS To THE RIGHT OF B", we would like the projection of A onto the U axis to dominate that of B; whereas the projections should (ideally) be identical on the V axis. That is, V () should stay near zero for all  (especially for small ). Similar observations can be made for "ABOVE", "BELOW".

Instead of dealing with two fuzzy subsets, U and V can be combined into a single set from which the relationship can be determined. 
"TO THE RIGHT OF" should therefore be a combination of U and the complement of V since its large values signify that the level sets of A are "above or below" those of B.

For the simulation examples described in paragraph 3.1, we chose a generalized mean

as the aggregation connective [2]. In this way, we can put higher weight on the horizontal component with decreased compensation as the level sets diverge vertically. 

Note that if P, then we have [2]:

Either the two fuzzy sets U and (l-V) or the single aggregated set m(U,V) can be used to define the relation "A IS TO RIGHT OF B". If a single value for the degree to which the two sets satisfy the relation is desired, we can construct a measure from the sets -such as the integral of the fuzzy number, or the output of an Ordered Weighted Average (OWA) [2]. An alternate approach is to use the curves directly to define a linguistic assessment of the relation. Here, it is necessary to define fuzzy sets representing terms used in the relation, such as "to the right of", "somewhat to the right of", "barely to the right of", "very to the right of", etc. These sets could be defined by the designer of the system, or perhaps, by utilizing a group of humans to give relative comparisons of a set of examples. The actual curve is then matched to the closest term available to give a linguistic assessment. This process is known as linguistic approximation [2].

3.1	Simulation Examples

All the definitions and the theorem listed above were tested using simulated data on a Sun Workstation. We worked with fuzzy subsets with two-sided drum like shaped membership functions on projections. The experiments were as follows. Let us consider an image containing two fuzzy subsets A and B whose membership functions are identical Gaussians, but with different mean locations. The set B will be fixed with mean (0.5, 0.5). Table 1 shows the fuzzy set V generated from eight choices of locations for the mean of A (assume that the V coordinate for the mean is 0.5). As can be seen, as the set A moves to the right, the fuzzy set U increases for all . Recall that the value U () = 0.5 represents the just separated condition. Three of these sets are shown graphically in Fig. 1. 

The seven -values are 0.011, 0.135, 0.258, 0.606, 0.796, 0.882, 0.923. They were chosen to get the following ranges from the mean of Gaussian functions: 0.4, 0.5, 0.6745, , 1.645, 2, 3, where  is a standard deviation.

Fig. 1

Since the projections onto V for these sets are the same as the projections onto U, these fuzzy sets in Table 1 can be used to simulate other placing of A relative to B, e.g., to the northeast or southeast. Table 2 shows four cases for the placement of the center of set A along with the aggregated fuzzy set generated from both projections. We used the generalized mean with W= 0.75 and P=2. The first case represents a set A, which is due east of B. Here the combined values are larger than those for the U projections only. In fact, even the smallest  (0.011) gives rise to a membership larger than 0.5 (the just separated crossover point). In case 2, the set A has moved to the north east of B. The movement north effectively decreases the membership in the fuzzy set "A is to the right of B". Cases 3 and 4 depict the situation where A is directly above B. As the centers move farther apart, the membership drops dramatically.

Mean of
Projections
of A	

1	

2	

3	

4	

5	

6	

7	
0.525	0.001	0.002	0.003	0.008	0.017	0.031	0.049	
0.550	0.014	0.031	0.046	0.125	0.275	0.500	0.516	
0.575	0.070	0.158	0.234	0.508	0.543	0.579	0.623	
0.600	0.222	0.500	0.514	0.564	0.622	0.680	0.731	
0.625	0.503	0.536	0.558	0.631	0.712	0.788	0.851	
0.650	0.532	0.580	0.609	0.706	0.806	0.891	0.950	
0.675	0.567	0.628	0.665	0.783	0.893	0.968	0.998	
0.700	0.604	0.680	0.724	0.857	0.962	1.00	1.00	

Table 1. Fuzzy membership functions generated from the projection of A onto U axis.

If we change either the weight W or the exponent P, we can alter the shape of the resultant fuzzy set. Tables 3 and 4 illustrate this. We used the following parameters: W= 0.8 and P= 3 to get the combined membership function in the Table 3, and W=0.9,
	1	2	3	4	5	6	7	
(0.6,0.5)
U
1-V
m(U, V)	
0.222
1.00
0.54	
0.500
1.00
0.66	
0.514
1.00
0.67	
0.564
1.00
0.70	
0.622
1.00
0.73	
0.680
1.00
0.77	
0.731
1.00
0.81	
(0.6,0.6)
U
1-V
m(U, V)	
0.222
0.778
0.43	
0.500
0.500
0.50	
0.514
0.486
0.51	
0.564
0.436
0.53	
0.622
0.378
0.57	
0.680
0.320
0.61	
0.731
0.269
0.65	
(0.5,0.6)
U
1-V
m(U, V)	
0.00
0.778
0.39	
0.00
0.500
0.25	
0.00
0.486
0.24	
0.00
0.436
0.22	
0.00
0.378
0.19	
0.00
0.320
0.16	
0.00
0.269
0.13	
(0.5,0.7)
U
1-V
m(U, V)	
0.00
0.396
0.20	
0.00
0.320
0.16	
0.00
0.276
0.14	
0.00
0.143
0.07	
0.00
0.038
0.02	
0.00
0.00
0.00	
0.00
0.00
0.00	

Table 2.  Combined membership function for the relation "A is to the right of B" (W= 0.75, P= 2).

P=4 to get the membership function in the Table 4. The shapes of the resultant fuzzy sets have been changed, but still, even for the smallest , we get memberships greater than 0.5 (the just separated crossover point).

	1	2	3	4	5	6	7	
(0.6,0.5)
U
1-V
m(U, V)	
0.222
1.00
0.59	
0.500
1.00
0.67	
0.514
1.00
0.68	
0.564
1.00
0.70	
0.622
1.00
0.73	
0.680
1.00
0.77	
0.731
1.00
0.81	
(0.6,0.6)
U
1-V
m(U, V)	
0.222
0.778
0.47	
0.500
0.500
0.50	
0.514
0.486
0.51	
0.564
0.436
0.54	
0.622
0.378
0.59	
0.680
0.320
0.64	
0.731
0.269
0.68	
(0.5,0.6)
U
1-V
m(U, V)	
0.00
0.778
0.45	
0.00
0.500
0.29	
0.00
0.486
0.28	
0.00
0.436
0.25	
0.00
0.378
0.22	
0.00
0.320
0.18	
0.00
0.269
0.15	
(0.5,0.7)
U
1-V
m(U, V)	
0.00
0.396
0.23	
0.00
0.320
0.18	
0.00
0.276
0.16	
0.00
0.143
0.08	
0.00
0.038
0.02	
0.00
0.00
0.00	
0.00
0.00
0.00	

Table 3.  Combined membership function for the relation “A is to the right of B” (W=0.8, P=3).

Also, switching to a union or intersection operator would have an even more dramatic effect on the consequent curve. This flexibility can be used to model the degree of optimism or pessimism that is desired in satisfying the relation "to the right of".

	1	2	3	4	5	6	7	
(0.6,0.5)
U
1-V
m(U, V)	
0.222
1.00
0.56	
0.500
1.00
0.63	
0.514
1.00
0.64	
0.564
1.00
0.66	
0.622
1.00
0.70	
0.680
1.00
0.74	
0.731
1.00
0.79	
(0.6,0.6)
U
1-V
m(U, V)	
0.222
0.778
0.44	
0.500
0.500
0.50	
0.514
0.486
0.51	
0.564
0.436
0.55	
0.622
0.378
0.61	
0.680
0.320
0.66	
0.731
0.269
0.71	
(0.5,0.6)
U
1-V
m(U, V)	
0.00
0.778
0.43	
0.00
0.500
0.28	
0.00
0.486
0.27	
0.00
0.436
0.24	
0.00
0.378
0.21	
0.00
0.320
0.18	
0.00
0.269
0.15	
(0.5,0.7)
U
1-V
m(U, V)	
0.00
0.396
0.22	
0.00
0.320
0.18	
0.00
0.276
0.15	
0.00
0.143
0.08	
0.00
0.038
0.02	
0.00
0.00
0.00	
0.00
0.00
0.00	

Table 4.  Combined membership function for the relation “A is to the right of B” (W=0.9, P=4).

4   Conclusions
Structural information derived from hierarchical image objects plays an important role in land use classification. Hierarchically formed image objects are useful tools for image analysis and spatial modeling. Spatial relationships between regions in an image play an important role in scene understanding. In this paper, an approach, based on the concept of dominance in fuzzy set theory, for modeling spatial relationships among fuzzy subsets of an image, has been outlined. Simulation results were presented to corroborate the theory and demonstrate the utility of the approach to the image description.

References:
[1] L. M. Sztandera, Assessing Growth Impacts of Land Use Expansion (AGILE) with Multi-Objective Genetic Algorithms, unpublished NSF grant proposal, PI: Sztandera L. M., Philadelphia, PA, 2004.
[2] L. M. Sztandera, Spatial Relations Based on Dominance of Fuzzy Sets, in Applying Soft Computing in Defining Spatial Relations, Matsakis P. and Sztandera L. M. (Eds.), Physica-Verlag, 2002.