Emb Fuzzy Ret
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Emb Fuzzy Ret as PDF for free.
More details
- Words: 4,072
- Pages: 5
Embedding Fuzzy Logic in Content Based Image Retrieval Constantin Vertan, Nozha Boujemaa INRIA Rocquancourt – Projet IMEDIA Domaine de Voluceau BP105 Rocquancourt, 78153 Le Chesnay Cedex, France Constantin.Vertan, [email protected]
Abstract
of fuzzy theory used for their definition. Four classes of fuzzy processing algorithms were identified in [15]: This paper focuses on the possible embedding of the un- crude fuzzy, fuzzy paradigm-based, fuzzy aggregational certainty regarding the colors of an image into histogram- and fuzzy inferential. The crude fuzzy techniques (as sugtype descriptors. The uncertainty naturally arises from gested by their name) are characterized by the use of num both the quantization of the color components and the bers in the interval (typically being weights attached human perception of colors. Fuzzy histograms measure to the objects of the problem universe), that are compatthe typicality of each color within the image. We define ible with a semantical description. The fuzzy paradigmvarious fuzzy color histograms following a taxonomy that based techniques use (implicitly or not) a fuzzy model of classifies fuzzy techniques as crude fuzzy, fuzzy paradigm the objects of the problem universe. The fuzzy aggregabased, fuzzy aggregational and fuzzy inferential. For tional techniques use a fuzzy model for the combination these fuzzy sets we must develop appropriate similarity (aggregation) of the individual objects in order to derive measures and distances. We propose a class of such dis- the outcome. Finally, the fuzzy inferential techniques are tances, derived from the fuzzy set equality and which we based on the inference mechanism that is applied with reparticularize according to various T-norms(fuzzy logical spect to a set of fuzzy rules that describe both the object ”or” operators). We also prove that the metric nat- model and the object aggregation. This is the most comurally arises as a distance for fuzzy sets, considering the plex model, that can be viewed as an instance of a rulefuzzy set symmetric difference. based expert system. In this contribution we will revisit the use of color histograms from a fuzzy-logic perspective: the value of each 1 Introduction bin must represent the typicality of the color within the Content-based image retrieval (CBIR) became a must in image rather than its probability. Thus, in section 2, we the last decade. Powered by the explosive development will define new type of histograms as membership funcof the Internet and the Web and the continuously cheaper tions of the colors within the image (and thus as fuzzy digital imagining devices and technologies, applications sets) and some new resemblance measures and distances such as digital libraries, image archives, video-on-demand for fuzzy sets will be introduced in section 3. Finally, secand specific image databases emerge as a real-life fact. tion 4 will present some experiments and conclusions. The basic idea of the CBIR process is to compactly describe an image by a digital signature and then match query images to the most resemblant image within the database according to the similarity of their signatures. 2 Fuzzy image histograms Traditionally, the content description is done (for either global or partial queries) according to the notions of color and texture. Thus the signatures are color distributions As already mentioned in the introduction, the histogram (histograms [13], color moments [9], color coherence vec- (probability density function) of the values within an imtors [10]), second-order, spatially constrained color distri- age (either color or gray-scale) is largely used for the butions (color correlograms [4], edge correlograms [3]) content-based image retrieval. The retrieval means that or classical textural descriptors (Fourier or wavelet coeffi- the images within the databases are selected according to cients, Markov random field models, etc.). the resemblance of their histogram to the histogram of the The search for new, fuzzy color distributions will fol- query image. Given a color image , of size by low the taxonomy proposed in [15] for the classification pixels, characterized by the color at location , i.e. of fuzzy processing techniques according to the amount , the color distribution (histogram) of the color
set. That means that we will associate to any color a Lukasiewicz function, M ?ON 9PQ R and for any color # ! % " $ , + * " $ &' & D of the color universe, M ? D is the resemblance degree
1 2 0 * 4 5 3 7 8 6 (1) of the color D to the color . Further assuming a fuzzy
(*) - (*)/. model that is not machiavelic (as discussed in [1]), we The values are normalized in order to sum to (as re- must logically admit a relation between the color resemquired by the definition of a probability density function) blance degree and the distance that separates the colors and is the Dirac impulse function. The value of each and D , and, more particularly, that the resemblance degree bin is. thus the number of image pixels having the color , decreases as the inter-color distance increases. The natural choice (according to the image processing or, after normalization, is the probability that the color set
is given by
traditions) is to impose a smooth decay of the resemblance function with respect to the inter-color distance. Still, we TSU color space was supposed to may remember that the 2.1 Crude fuzzy histograms offer the equivalence between the perceptual inter-color In order to construct such a function we must provide a distance and the Euclidean distance between their tristimsemantical description of the significance of the numbers ulus representations. Even more, the notion of JND asattached to each color in the color space 9 and a method sures visual equivalence for colors that are closer than 2.3 [12]. Practical considerations and the analytical simplifithat assures that the numbers are well within the range. The immediate approach is to slightly modify the cation of the computational expressions impose the use of construction of the normal color histogram. We may de- an unified formula for the resemblance degree. A linear fine the concept of typicality of a color within the given descent would require little computation but could conimage as the importance of the given color with respect tradict the smooth descent principle. A Gaussian operator to its relative presence. In fact, this description relates the (3) could be a more appropriate choice. \ typicality of the colors to the area that they occupy, and D ? = < ^ _ (3) M D V W XZY%[*\] 0#` XE [*a\ b H thus to their probability of occurrence. But the most typical color must have a typicality degree of 1, regardless its occurrence probability and thus we define this fuzzy This fuzzy color model enables to enlarge the influence of a given color to its neighboring colors, according to histogram as (2): the uncertainty principle (of not being certain that a quan $ tized color has not erroneous changed the original color) (2) :<;>=?A@BC EDF *35 76G9IH and the perceptual similarity. This means that each time a color is found in the image, it will influence all the This is in fact the usual color histogram (1) but with a dif- quantized colors from 9 (and thus all the histogram bins) ferent normalization condition; instead of the probability according to their resemblance to the color . Numeri density function normalization condition ( J ?A@BLK D ), cally, this could be expressed as: we normalize by the mode ( :<;>= ? @ BC D ) of the color !d"*$ +"%$ \ c & & & M ? D ghji102 V distribution. The new normalization does not change much the intrinsic properties of the histogram, since it ? @ BLK e (*) f (*) . preserves its shape (including the “holes” or empty bins & ? (4) ?A@BLK D M D H that appeared mainly as quantization effect). We may use this approach as a transitional step in changing the probabilistic description of the color description by a fuzzy The expression in (4) is the linear convolution between description. Also, such a histogram can be useful if fuzzy the usual color histogram and the fuzzy color model (supdistances are to be embedded in the retrieval system, since posing that the model is color-independent, that is M ? the fuzzy distances are defined on fuzzy sets and the nor- M ?@ %35 Ra D 6k9 ). Thus we can compactly write: \ l M ? H mal histogram cannot be viewed as one. (5) appears in the image.
2.2 Fuzzy paradigm-based histograms As ennounced in the description of the taxonomic categories, the fuzzy paradigm-based techniques are constructed according to a fuzzy model of the objects of the universe. In the case of color images, the objects are the colors within the image or the possible colors within the set 9 . The model assumes that any color is a fuzzy
The convolution expresses the histogram smoothing, provided that the color model is indeed a smoothing, lowpass filtering kernel; such an approach was proposed in [7] for gray scale images, but the grays model was a triangular function. The use of the Gaussian shape from (3) as color model produces the smoothed histogram, proposed by many authors (that can be traced back to [8]) as a mean for the reduction of quantization errors.
fuzzy sets defined over the same problem universe , that means {A N P R . We will also denote by The colors are already described by a fuzzy model. As MV {A< the resemblance measure between sets and expressed in (4), the contribution of each individual pixel and by {A< their corresponding distance. As sugof the image is added in order to produce the global con` gested in [2], if MV {a7 is a resemblance measure, than tribution of the image at each possible color. Thus, the between the fuzzy
a7I 0MV {A< is a distance interaction between the colors (as result of a specific im- ` sets and , with a7 . age appearance) is modeled as a ”stockpile” and described ` We propose to investigate two approaches, derived by a sum operation. from a fuzzy set equality formulation and the fuzzy symIn order to produce a fuzzy interaction model that metric difference. groups together the individual pixel contributions, we must re-define the fuzzy histogram. We will again use the typicality approach (already used for the crude fuzzy his- 3.1 Distances between fuzzy sets from fuzzy equality togram), but we consider the image as the reunion of the colors that are present within. Thus, the typicality of the As known, the set equality relation can be expressed as color is the measure of resemblance of the given color a double inclusion, which can be further translated into with respect to the reunion of all the colors in the image. fuzzy logic operators. We may note that the approach was Since the [reunion (logical or operator) is modeled by a briefly mentioned in [2] as an extension of a previous disT-conorm [16] we have: similarity indicator introduced in [5], [6]. Still the au Rm T n Msr o e/p fEq [ o e/p fEq Msr o e/p fEq (6) thors did not investigated neither if the expressions meet o e/p fEq the mathematical conditions (reflexivity in particular) nor the generation of a complete class of such fuzzy distances The T-conorm models the aggregation of the individual (or resemblance measures). The set equality relation can be classically expressed as entities.[ Several T-conorms have been [ proposed [16]: S U S U S U Svu a double . For Zadeh O :7[ ;Z= , algebraic t U 0 SU , Lukasiewicz S U w :<xzy S{u|U , Hamacher fuzzy sets,inclusion: the inclusion relation can be evaluated [11] by \ [ S U [ " the number M%5 xzy>B ¡¢ { £5a¤R¥¦# £5a , where
V~}%$ " } , Einstein S U VQ$ }s . } that the relaxation of%}the fuzzy con- ¡ is a fuzzy negation operator (we will use the classical We may notice S 0 S ). Thus, we can evaluate the straint (that any number should be within ) in the Zadeh negation, ¡* definitions of the fuzzy T-conorms that impose it in an equality relation of the fuzzy sets and by the number explicit manner (such as the Lukasiewicz operator) will M§|M * {M * . Since any fuzzy logic conjunction is a [ T-norm ¨ and simply replace the reunion operator by a simple addition of the resemblance degrees. Thus we obtain the paradigm- any fuzzy logic disjunction is a T-conorm , dual to each operator ¡ [11], based fuzzy histogram from (4). In fact, we can view other with respect to the given negation x©yAEB [ ¡I £5a*A# £5j the fuzzy aggregational histogram as a thresholding of the [16], we can rewrite M%[ 5 x©y>B ª¡I # £5a5a £*j . Thus, the gensmoothed, paradigm-based, fuzzy histogram; more colors and MsV5 that are actually present in the image (but are close to the eral expression of the fuzzy resemblance degree of the two real colors) have good chances to receive a typicality of 1. sets can be thus expressed as (7). Using m the Zadeh operators, the fuzzy histograms be(7) MV {A< «¨ M%5jMs ¬ ¬H comes :7;Z= Msr o e/p fEq , which implies that any color that appears in the image will exhibit a typicality of m %3* #6 ) and the other colors (those within We expect that any useful resemblance measure ex1 ( hibits some common-sense properties, such as the value 90 ) will have typicalities depending on the distance it should take for the case of the comparison of two idento the closest existing color. Since all the colors from , tical objects (histograms or fuzzy sets), i.e the reflexivity regardless their relative proportions, have the same typi- property. This value must be 1, according to the usual norcality, this kind of fuzzy histogram is less discriminant. malizations and mathematical conditions [2]. That means we should impose:
2.3 Fuzzy aggregational histogram
3 Fuzzy-based resemblance measures and distances In this section we will focus on the introduction of some new resemblance measures (and subsequently distances) between fuzzy sets. Let us denote by and two
if { £5 # £5®3¬£v68 then MV {a7
H
(8)
Replacing the condition (8) in the general expression of the resemblance measure (7) we obtain:
[ [ ¨ ¯ >zx yB h 0 £5a £5as ExzyB { £5 02{ £*j°, H (9)
S S
For any T-norm ¨ , ¨* if and only if and thus the condition from (9) becomes:
> xzyB
[
2 0 { £5a{ £5a± [
02{ £5a{ £5a±
S
³] ² ´ x¶µZ;>· ] y ¸¸a¹ 35£v6vwH
[16],
In the case of crisp sets, the symmetrical difference is defined as:
Í
(10)
Í
(11)
OÎ#70t tÏ»< or
«0h7%Îv Ð02IH [
(19) (20)
Since any T-conorm can be used as a logical ”or” [ In fact, the condition (11) states that the T-conorm that operator (and thus as a reunion) and any T-norm ¨ can be is to be used in the expression (7) must necessarily respect used as a logical ”and” operator (and thus as a intersecthe excluded middle principle [16], [11]. The only such T- tion) [16], we can express (19) and (20) as: conorm is the ”or” operator, [ [ Lukasiewicz (bounded u º .sum) ͧ £5T|¨ ¯ £5ad £5a* 0¨¢ { £5A# £5j°EH (21) defined as £saº» :<xzy j£ Thus, the general expression of the fuzzy resemblance measure becomes: [
MV a7c S U
¨* S Ex©yB Ex©yB
U ¼ x¶¸A½ :<x©y 02{ £5 u # £5a :<x©y ¾u { £502# £5a*H
Ív £*
(12)
¯¨ { £* 02# £*j*j¨ 02{ £5a# £5aR°EH
(22) The dissimilarity set used in [5], [6] for the Restle indicator is the fuzzy symmetrical[ difference (22) according to the Zadeh fuzzy operators ( :7;>= , ¨d :<x©y ). Other distances could be potentially obtained from (21) and (22) by using other fuzzy operators. The following proposition [14] will, however, limit their choice. [ Proposition: For any fuzzy operators and ¨ , the fuzzy distance (18) constructed according to the symmet distance. rical set difference (21) or (22) is the Using the proper combination of T-norms and Tconorms [16] in the general expression from (22), after some simple arithmetics we obtain that the distance be distween the fuzzy sets and is, in all cases, the tance between the two sets:
Equation (12) represents in fact a class of resemblance measures, provided that we use different T-norms ¨ . We S U can use the following T-conorms [16]: Zadeh ¨* 7 S U S U S U :<x©y , algebraic ¨* , Lukasiewicz ¨* S U S U T SU¿ Su2U 0 SU , :7;Z= R Su2U 0 , Hamacher X S ¨* UVuÀ S U S U ¿ SU . Einstein ¨* T
0 0 Using the above mentioned T-norms and the general expression from (12), after some simple arithmetics we obtain the following distances between fuzzy sets: (13) when using the Zadeh operator, (14) when using the alge& braic operator, (15) when using the Lukasiewicz operator,
` a<T EB Ç £5V0hd £* (16) when using the Hamacher operator and (17) when using the Einstein operator. In all the equations, we denote Á Ã Â ´ ^ >B ¯{ £5 0|# £5®° and ÄÅ xzy EB ¯ £* 0 The complete proof can be found in [14]. # £5j° .
` Æ `È `Ê ` Ë
a7c
a7c
a7c
a7c
`Ì a7c
EÂ ´ B^ Ç { £*02# £* Ç Á 0hÄ u ÁÉ Ä Á 0hÄ Á 0hÄ u X Á8É Ä ¾u Á8É Á 0hÄ Ä 0 Á8É Ä H
(13) (14) (15) (16) (17)
3.2 Distances between fuzzy sets from symmetric difference According to a more general definition [2], a fuzzy distance between the fuzzy sets and (defined over the discrete set ) is the fuzzy cardinality of the set Í , called dissimilarity set.:
&
` {A< EB ͧ £5H
(18)
ÇH
(23)
4 Experiments and conclusions The experiments performed in order to establish the retrieval capabilities of the proposed fuzzy histograms were conducted using the Surfimage software platform developed at IMEDIA. We investigated both the objective and the subjective retrieval quality, on two different, heterogeneous, generalist image databases. The subjective retrieval quality was studied by visual inspection and similarity estimation of the images retrieved from a large (1500) heterogeneous database of “natural” images (Comstock). All fuzzy histograms perform well, providing perceptually appealing results. The objective retrieval quality is measured by the precision of retrieval for a small, labeled database, consisting of 21 image classes (key frames from a television broadcast). The images were described by their color distribution, expressed as a fuzzy histogram. Table 1 presents the maximal (at recall 1) and average precision of the retrieval by the $ histogram and various fuzzy set equality-issued
distances. Apparently, the Hamacher-operators induces distance performs somehow better, but the difference with respect to the other distances is not significant. In the distance (obtained as fuzzy set symsame time, the metrical difference distance) provides significantly better performance. The same type of results is obtained for the other fuzzy histograms. Table 1: Maximal and average precision rates for the retrieval by the crude fuzzy normalized color histogram (2) with various proposed fuzzy set distances Maximal Average precision precision Zadeh (13) 72.38 % 57.11 % Algebraic (14) 74.76 % 58.07 % Lukasiewicz (15) 75.71 % 57.27 % Hamacher (16) 75.71 % 57.92 % Einstein (17) 75.24 % 58.06 % L1 23) 80.95 % 64.33 % Table 2 presents the average precision and the precision for 10 retrieved images, for the retrieval by the usual color histogram and the crude-fuzzy (mode normalized) color histogram, according to various fuzzy distances. It is clear that the use of the fuzzy histogram increases the retrieval performance. Table 2: Average precision and precision at recall 10 for the retrieval by the usual color histogram and the crude fuzzy color histogram $ (2) Distance class and Average Recall 10 histogram type precision precision Zadeh, with (1) 55.67 % 45.74 % $ Zadeh, with (2) 57.11 % 47.42 % Lukasiewicz, with (1) 54.18 % 45.45 % Lukasiewicz, with $ (2) 57.27 % 47.03 % Hamacher, with (1) 54.58 % 45.41 % Hamacher, with $ (2) 57.92 % 47.94 % The various proposed color histograms may be not allways quantitatively better than the usual color histogram, but the actual retrieval results are visually appealing and correct. However, we could not expect to obtain more rigorous results (and thus improved objective measured performance) by relaxing (through fuzzy modeling) the histogram image description. The new introduced fuzzy distances are not specifically designed for content based image retrieval, but are general. Their use may prove effective in other application areas also. As a final conclusion, we suggest that the retrieval results are very encouraging and prove that the use
of uncertainty in content based image retrieval is natural and desirable as long as human perception remains the key factor in judging and using the results.
References [1] J. C. Bezdek. Fuzzy models - what are they and why ? IEEE Trans. on Fuzzy Systems, 1(1):1–5, Feb. 1993. [2] I. Bloch. On fuzzy distances and their use in image processing under imprecision. Pattern Recognition, 32(11):1873–1895, Nov. 1999. [3] J. Huang, S. R. Kumar, M. Mitra, and Z. W.-J. Spatial color indexing and applications. In IEEE International Conference on Computer Vision ICCV ‘98, Bombay, India, 4-7 Jan. 1998. [4] J. Huang, S. R. Kumar, M. Mitra, Z. W.-J., and R. Zabih. Image indexing using correlograms. In Computer Vision and Pattern Recognition CVPR ‘97, San Juan, Puerto Rico, 17-19 Jun. 1997. [5] R. C. Jain, S. N. Murthy, L. Tran, and S. Chatterjee. Similarity measures for image databases. In W. Niblack and R. C. Jain, editors, Storage and Retrieval for Still Image and Video Databases III, volume SPIE 2420, pages 58– 67, 1995. [6] R. C. Jain, S. N. Murthy, L. Tran, and S. Chatterjee. Similarity measures for image databases. In Proc. of IEEE Conference on Fuzzy Systems, volume 3, pages 1247– 1254, Yokohama, Japan, 1995. [7] C. V. Jawahar and A. K. Ray. Fuzzy statistics of digital images. IEEE Signal Processing Letters, 3(8):225–227, Aug. 1996. [8] J. Kautsky, N. K. Nichols, and D. L. B. Jupp. Smoothed histogram modification for image processing. CVGIP, 26(3):271–291, Jun. 1984. [9] B. M. Mehtre, M. S. Kankanhalli, A. D. Narasimhalu, and G. C. Man. Color matching for image retrieval. Pattern Recognition Letters, 16:325–331, Mar. 1995. [10] G. Pass and R. Zabih. Histogram refinement for content based image retrieval. In IEEE Workshop on Applications of Computer Vision, pages 96–102, 1996. [11] B. Reusch. Mathematics of fuzzy logic. In H. J. Zimmermann, D. Dasc˘alu, and M. G. Negoit¸a˘ , editors, Real World Applications of Intelligent Technologies, pages 15– 52, Bucures¸ti, Romania, 1996. Romanian Academy Publ. House. [12] G. Sharma and H. J. Trusell. Digital color imaging. IEEE Trans. on Image Processing, 6(7):901–932, Jul. 1997. [13] M. J. Swain and D. H. Ballard. Color indexing. International Journal of Computer Vision, 7(1):11–32, 1991. [14] C. Vertan and N. Boujemaa. Using fuzzy histograms and distances for color image retrieval. In Proc. of CIR’2000, Brighton, United Kingdom, 4-5 May 2000. [15] C. Vertan and V. Buzuloiu. Fuzzy nonlinear filtering of color images: A survey. In E. Kerre and M. Nachtegael, editors, Fuzzy Techniques in Image Processing, Heidelberg, Germany, 2000. Physica Verlag. [16] H. J. Zimmermann. Fuzzy Sets, Decision Making and Expert Systems. Kluwer Academic Publ., Boston MA, 1987.
Abstract
of fuzzy theory used for their definition. Four classes of fuzzy processing algorithms were identified in [15]: This paper focuses on the possible embedding of the un- crude fuzzy, fuzzy paradigm-based, fuzzy aggregational certainty regarding the colors of an image into histogram- and fuzzy inferential. The crude fuzzy techniques (as sugtype descriptors. The uncertainty naturally arises from gested by their name) are characterized by the use of num both the quantization of the color components and the bers in the interval (typically being weights attached human perception of colors. Fuzzy histograms measure to the objects of the problem universe), that are compatthe typicality of each color within the image. We define ible with a semantical description. The fuzzy paradigmvarious fuzzy color histograms following a taxonomy that based techniques use (implicitly or not) a fuzzy model of classifies fuzzy techniques as crude fuzzy, fuzzy paradigm the objects of the problem universe. The fuzzy aggregabased, fuzzy aggregational and fuzzy inferential. For tional techniques use a fuzzy model for the combination these fuzzy sets we must develop appropriate similarity (aggregation) of the individual objects in order to derive measures and distances. We propose a class of such dis- the outcome. Finally, the fuzzy inferential techniques are tances, derived from the fuzzy set equality and which we based on the inference mechanism that is applied with reparticularize according to various T-norms(fuzzy logical spect to a set of fuzzy rules that describe both the object ”or” operators). We also prove that the metric nat- model and the object aggregation. This is the most comurally arises as a distance for fuzzy sets, considering the plex model, that can be viewed as an instance of a rulefuzzy set symmetric difference. based expert system. In this contribution we will revisit the use of color histograms from a fuzzy-logic perspective: the value of each 1 Introduction bin must represent the typicality of the color within the Content-based image retrieval (CBIR) became a must in image rather than its probability. Thus, in section 2, we the last decade. Powered by the explosive development will define new type of histograms as membership funcof the Internet and the Web and the continuously cheaper tions of the colors within the image (and thus as fuzzy digital imagining devices and technologies, applications sets) and some new resemblance measures and distances such as digital libraries, image archives, video-on-demand for fuzzy sets will be introduced in section 3. Finally, secand specific image databases emerge as a real-life fact. tion 4 will present some experiments and conclusions. The basic idea of the CBIR process is to compactly describe an image by a digital signature and then match query images to the most resemblant image within the database according to the similarity of their signatures. 2 Fuzzy image histograms Traditionally, the content description is done (for either global or partial queries) according to the notions of color and texture. Thus the signatures are color distributions As already mentioned in the introduction, the histogram (histograms [13], color moments [9], color coherence vec- (probability density function) of the values within an imtors [10]), second-order, spatially constrained color distri- age (either color or gray-scale) is largely used for the butions (color correlograms [4], edge correlograms [3]) content-based image retrieval. The retrieval means that or classical textural descriptors (Fourier or wavelet coeffi- the images within the databases are selected according to cients, Markov random field models, etc.). the resemblance of their histogram to the histogram of the The search for new, fuzzy color distributions will fol- query image. Given a color image , of size by low the taxonomy proposed in [15] for the classification pixels, characterized by the color at location , i.e. of fuzzy processing techniques according to the amount , the color distribution (histogram) of the color
set. That means that we will associate to any color a Lukasiewicz function, M ?ON 9PQ R and for any color # ! % " $ , + * " $ &' & D of the color universe, M ? D is the resemblance degree
1 2 0 * 4 5 3 7 8 6 (1) of the color D to the color . Further assuming a fuzzy
(*) - (*)/. model that is not machiavelic (as discussed in [1]), we The values are normalized in order to sum to (as re- must logically admit a relation between the color resemquired by the definition of a probability density function) blance degree and the distance that separates the colors and is the Dirac impulse function. The value of each and D , and, more particularly, that the resemblance degree bin is. thus the number of image pixels having the color , decreases as the inter-color distance increases. The natural choice (according to the image processing or, after normalization, is the probability that the color set
is given by
traditions) is to impose a smooth decay of the resemblance function with respect to the inter-color distance. Still, we TSU color space was supposed to may remember that the 2.1 Crude fuzzy histograms offer the equivalence between the perceptual inter-color In order to construct such a function we must provide a distance and the Euclidean distance between their tristimsemantical description of the significance of the numbers ulus representations. Even more, the notion of JND asattached to each color in the color space 9 and a method sures visual equivalence for colors that are closer than 2.3 [12]. Practical considerations and the analytical simplifithat assures that the numbers are well within the range. The immediate approach is to slightly modify the cation of the computational expressions impose the use of construction of the normal color histogram. We may de- an unified formula for the resemblance degree. A linear fine the concept of typicality of a color within the given descent would require little computation but could conimage as the importance of the given color with respect tradict the smooth descent principle. A Gaussian operator to its relative presence. In fact, this description relates the (3) could be a more appropriate choice. \ typicality of the colors to the area that they occupy, and D ? = < ^ _ (3) M D V W XZY%[*\] 0#` XE [*a\ b H thus to their probability of occurrence. But the most typical color must have a typicality degree of 1, regardless its occurrence probability and thus we define this fuzzy This fuzzy color model enables to enlarge the influence of a given color to its neighboring colors, according to histogram as (2): the uncertainty principle (of not being certain that a quan $ tized color has not erroneous changed the original color) (2) :<;>=?A@BC EDF *35 76G9IH and the perceptual similarity. This means that each time a color is found in the image, it will influence all the This is in fact the usual color histogram (1) but with a dif- quantized colors from 9 (and thus all the histogram bins) ferent normalization condition; instead of the probability according to their resemblance to the color . Numeri density function normalization condition ( J ?A@BLK D ), cally, this could be expressed as: we normalize by the mode ( :<;>= ? @ BC D ) of the color !d"*$ +"%$ \ c & & & M ? D ghji102 V distribution. The new normalization does not change much the intrinsic properties of the histogram, since it ? @ BLK e (*) f (*) . preserves its shape (including the “holes” or empty bins & ? (4) ?A@BLK D M D H that appeared mainly as quantization effect). We may use this approach as a transitional step in changing the probabilistic description of the color description by a fuzzy The expression in (4) is the linear convolution between description. Also, such a histogram can be useful if fuzzy the usual color histogram and the fuzzy color model (supdistances are to be embedded in the retrieval system, since posing that the model is color-independent, that is M ? the fuzzy distances are defined on fuzzy sets and the nor- M ?@ %35 Ra D 6k9 ). Thus we can compactly write: \ l M ? H mal histogram cannot be viewed as one. (5) appears in the image.
2.2 Fuzzy paradigm-based histograms As ennounced in the description of the taxonomic categories, the fuzzy paradigm-based techniques are constructed according to a fuzzy model of the objects of the universe. In the case of color images, the objects are the colors within the image or the possible colors within the set 9 . The model assumes that any color is a fuzzy
The convolution expresses the histogram smoothing, provided that the color model is indeed a smoothing, lowpass filtering kernel; such an approach was proposed in [7] for gray scale images, but the grays model was a triangular function. The use of the Gaussian shape from (3) as color model produces the smoothed histogram, proposed by many authors (that can be traced back to [8]) as a mean for the reduction of quantization errors.
fuzzy sets defined over the same problem universe , that means {A N P R . We will also denote by The colors are already described by a fuzzy model. As MV {A< the resemblance measure between sets and expressed in (4), the contribution of each individual pixel and by {A< their corresponding distance. As sugof the image is added in order to produce the global con` gested in [2], if MV {a7 is a resemblance measure, than tribution of the image at each possible color. Thus, the between the fuzzy
a7I 0MV {A< is a distance interaction between the colors (as result of a specific im- ` sets and , with a7 . age appearance) is modeled as a ”stockpile” and described ` We propose to investigate two approaches, derived by a sum operation. from a fuzzy set equality formulation and the fuzzy symIn order to produce a fuzzy interaction model that metric difference. groups together the individual pixel contributions, we must re-define the fuzzy histogram. We will again use the typicality approach (already used for the crude fuzzy his- 3.1 Distances between fuzzy sets from fuzzy equality togram), but we consider the image as the reunion of the colors that are present within. Thus, the typicality of the As known, the set equality relation can be expressed as color is the measure of resemblance of the given color a double inclusion, which can be further translated into with respect to the reunion of all the colors in the image. fuzzy logic operators. We may note that the approach was Since the [reunion (logical or operator) is modeled by a briefly mentioned in [2] as an extension of a previous disT-conorm [16] we have: similarity indicator introduced in [5], [6]. Still the au Rm T n Msr o e/p fEq [ o e/p fEq Msr o e/p fEq (6) thors did not investigated neither if the expressions meet o e/p fEq the mathematical conditions (reflexivity in particular) nor the generation of a complete class of such fuzzy distances The T-conorm models the aggregation of the individual (or resemblance measures). The set equality relation can be classically expressed as entities.[ Several T-conorms have been [ proposed [16]: S U S U S U Svu a double . For Zadeh O :7[ ;Z= , algebraic t U 0 SU , Lukasiewicz S U w :<xzy S{u|U , Hamacher fuzzy sets,inclusion: the inclusion relation can be evaluated [11] by \ [ S U [ " the number M%5 xzy>B ¡¢ { £5a¤R¥¦# £5a , where
V~}%$ " } , Einstein S U VQ$ }s . } that the relaxation of%}the fuzzy con- ¡ is a fuzzy negation operator (we will use the classical We may notice S 0 S ). Thus, we can evaluate the straint (that any number should be within ) in the Zadeh negation, ¡* definitions of the fuzzy T-conorms that impose it in an equality relation of the fuzzy sets and by the number explicit manner (such as the Lukasiewicz operator) will M§|M * {M * . Since any fuzzy logic conjunction is a [ T-norm ¨ and simply replace the reunion operator by a simple addition of the resemblance degrees. Thus we obtain the paradigm- any fuzzy logic disjunction is a T-conorm , dual to each operator ¡ [11], based fuzzy histogram from (4). In fact, we can view other with respect to the given negation x©yAEB [ ¡I £5a*A# £5j the fuzzy aggregational histogram as a thresholding of the [16], we can rewrite M%[ 5 x©y>B ª¡I # £5a5a £*j . Thus, the gensmoothed, paradigm-based, fuzzy histogram; more colors and MsV5 that are actually present in the image (but are close to the eral expression of the fuzzy resemblance degree of the two real colors) have good chances to receive a typicality of 1. sets can be thus expressed as (7). Using m the Zadeh operators, the fuzzy histograms be(7) MV {A< «¨ M%5jMs ¬ ¬H comes :7;Z= Msr o e/p fEq , which implies that any color that appears in the image will exhibit a typicality of m %3* #6 ) and the other colors (those within We expect that any useful resemblance measure ex1 ( hibits some common-sense properties, such as the value 90 ) will have typicalities depending on the distance it should take for the case of the comparison of two idento the closest existing color. Since all the colors from , tical objects (histograms or fuzzy sets), i.e the reflexivity regardless their relative proportions, have the same typi- property. This value must be 1, according to the usual norcality, this kind of fuzzy histogram is less discriminant. malizations and mathematical conditions [2]. That means we should impose:
2.3 Fuzzy aggregational histogram
3 Fuzzy-based resemblance measures and distances In this section we will focus on the introduction of some new resemblance measures (and subsequently distances) between fuzzy sets. Let us denote by and two
if { £5 # £5®3¬£v68 then MV {a7
H
(8)
Replacing the condition (8) in the general expression of the resemblance measure (7) we obtain:
[ [ ¨ ¯ >zx yB h 0 £5a £5as ExzyB { £5 02{ £*j°, H (9)
S S
For any T-norm ¨ , ¨* if and only if and thus the condition from (9) becomes:
> xzyB
[
2 0 { £5a{ £5a± [
02{ £5a{ £5a±
S
³] ² ´ x¶µZ;>· ] y ¸¸a¹ 35£v6vwH
[16],
In the case of crisp sets, the symmetrical difference is defined as:
Í
(10)
Í
(11)
OÎ#70t tÏ»< or
«0h7%Îv Ð02IH [
(19) (20)
Since any T-conorm can be used as a logical ”or” [ In fact, the condition (11) states that the T-conorm that operator (and thus as a reunion) and any T-norm ¨ can be is to be used in the expression (7) must necessarily respect used as a logical ”and” operator (and thus as a intersecthe excluded middle principle [16], [11]. The only such T- tion) [16], we can express (19) and (20) as: conorm is the ”or” operator, [ [ Lukasiewicz (bounded u º .sum) ͧ £5T|¨ ¯ £5ad £5a* 0¨¢ { £5A# £5j°EH (21) defined as £saº» :<xzy j£ Thus, the general expression of the fuzzy resemblance measure becomes: [
MV a7c S U
¨* S Ex©yB Ex©yB
U ¼ x¶¸A½ :<x©y 02{ £5 u # £5a :<x©y ¾u { £502# £5a*H
Ív £*
(12)
¯¨ { £* 02# £*j*j¨ 02{ £5a# £5aR°EH
(22) The dissimilarity set used in [5], [6] for the Restle indicator is the fuzzy symmetrical[ difference (22) according to the Zadeh fuzzy operators ( :7;>= , ¨d :<x©y ). Other distances could be potentially obtained from (21) and (22) by using other fuzzy operators. The following proposition [14] will, however, limit their choice. [ Proposition: For any fuzzy operators and ¨ , the fuzzy distance (18) constructed according to the symmet distance. rical set difference (21) or (22) is the Using the proper combination of T-norms and Tconorms [16] in the general expression from (22), after some simple arithmetics we obtain that the distance be distween the fuzzy sets and is, in all cases, the tance between the two sets:
Equation (12) represents in fact a class of resemblance measures, provided that we use different T-norms ¨ . We S U can use the following T-conorms [16]: Zadeh ¨* 7 S U S U S U :<x©y , algebraic ¨* , Lukasiewicz ¨* S U S U T SU¿ Su2U 0 SU , :7;Z= R Su2U 0 , Hamacher X S ¨* UVuÀ S U S U ¿ SU . Einstein ¨* T
0 0 Using the above mentioned T-norms and the general expression from (12), after some simple arithmetics we obtain the following distances between fuzzy sets: (13) when using the Zadeh operator, (14) when using the alge& braic operator, (15) when using the Lukasiewicz operator,
` a<T EB Ç £5V0hd £* (16) when using the Hamacher operator and (17) when using the Einstein operator. In all the equations, we denote Á Ã Â ´ ^ >B ¯{ £5 0|# £5®° and ÄÅ xzy EB ¯ £* 0 The complete proof can be found in [14]. # £5j° .
` Æ `È `Ê ` Ë
a7c
a7c
a7c
a7c
`Ì a7c
EÂ ´ B^ Ç { £*02# £* Ç Á 0hÄ u ÁÉ Ä Á 0hÄ Á 0hÄ u X Á8É Ä ¾u Á8É Á 0hÄ Ä 0 Á8É Ä H
(13) (14) (15) (16) (17)
3.2 Distances between fuzzy sets from symmetric difference According to a more general definition [2], a fuzzy distance between the fuzzy sets and (defined over the discrete set ) is the fuzzy cardinality of the set Í , called dissimilarity set.:
&
` {A< EB ͧ £5H
(18)
ÇH
(23)
4 Experiments and conclusions The experiments performed in order to establish the retrieval capabilities of the proposed fuzzy histograms were conducted using the Surfimage software platform developed at IMEDIA. We investigated both the objective and the subjective retrieval quality, on two different, heterogeneous, generalist image databases. The subjective retrieval quality was studied by visual inspection and similarity estimation of the images retrieved from a large (1500) heterogeneous database of “natural” images (Comstock). All fuzzy histograms perform well, providing perceptually appealing results. The objective retrieval quality is measured by the precision of retrieval for a small, labeled database, consisting of 21 image classes (key frames from a television broadcast). The images were described by their color distribution, expressed as a fuzzy histogram. Table 1 presents the maximal (at recall 1) and average precision of the retrieval by the $ histogram and various fuzzy set equality-issued
distances. Apparently, the Hamacher-operators induces distance performs somehow better, but the difference with respect to the other distances is not significant. In the distance (obtained as fuzzy set symsame time, the metrical difference distance) provides significantly better performance. The same type of results is obtained for the other fuzzy histograms. Table 1: Maximal and average precision rates for the retrieval by the crude fuzzy normalized color histogram (2) with various proposed fuzzy set distances Maximal Average precision precision Zadeh (13) 72.38 % 57.11 % Algebraic (14) 74.76 % 58.07 % Lukasiewicz (15) 75.71 % 57.27 % Hamacher (16) 75.71 % 57.92 % Einstein (17) 75.24 % 58.06 % L1 23) 80.95 % 64.33 % Table 2 presents the average precision and the precision for 10 retrieved images, for the retrieval by the usual color histogram and the crude-fuzzy (mode normalized) color histogram, according to various fuzzy distances. It is clear that the use of the fuzzy histogram increases the retrieval performance. Table 2: Average precision and precision at recall 10 for the retrieval by the usual color histogram and the crude fuzzy color histogram $ (2) Distance class and Average Recall 10 histogram type precision precision Zadeh, with (1) 55.67 % 45.74 % $ Zadeh, with (2) 57.11 % 47.42 % Lukasiewicz, with (1) 54.18 % 45.45 % Lukasiewicz, with $ (2) 57.27 % 47.03 % Hamacher, with (1) 54.58 % 45.41 % Hamacher, with $ (2) 57.92 % 47.94 % The various proposed color histograms may be not allways quantitatively better than the usual color histogram, but the actual retrieval results are visually appealing and correct. However, we could not expect to obtain more rigorous results (and thus improved objective measured performance) by relaxing (through fuzzy modeling) the histogram image description. The new introduced fuzzy distances are not specifically designed for content based image retrieval, but are general. Their use may prove effective in other application areas also. As a final conclusion, we suggest that the retrieval results are very encouraging and prove that the use
of uncertainty in content based image retrieval is natural and desirable as long as human perception remains the key factor in judging and using the results.
References [1] J. C. Bezdek. Fuzzy models - what are they and why ? IEEE Trans. on Fuzzy Systems, 1(1):1–5, Feb. 1993. [2] I. Bloch. On fuzzy distances and their use in image processing under imprecision. Pattern Recognition, 32(11):1873–1895, Nov. 1999. [3] J. Huang, S. R. Kumar, M. Mitra, and Z. W.-J. Spatial color indexing and applications. In IEEE International Conference on Computer Vision ICCV ‘98, Bombay, India, 4-7 Jan. 1998. [4] J. Huang, S. R. Kumar, M. Mitra, Z. W.-J., and R. Zabih. Image indexing using correlograms. In Computer Vision and Pattern Recognition CVPR ‘97, San Juan, Puerto Rico, 17-19 Jun. 1997. [5] R. C. Jain, S. N. Murthy, L. Tran, and S. Chatterjee. Similarity measures for image databases. In W. Niblack and R. C. Jain, editors, Storage and Retrieval for Still Image and Video Databases III, volume SPIE 2420, pages 58– 67, 1995. [6] R. C. Jain, S. N. Murthy, L. Tran, and S. Chatterjee. Similarity measures for image databases. In Proc. of IEEE Conference on Fuzzy Systems, volume 3, pages 1247– 1254, Yokohama, Japan, 1995. [7] C. V. Jawahar and A. K. Ray. Fuzzy statistics of digital images. IEEE Signal Processing Letters, 3(8):225–227, Aug. 1996. [8] J. Kautsky, N. K. Nichols, and D. L. B. Jupp. Smoothed histogram modification for image processing. CVGIP, 26(3):271–291, Jun. 1984. [9] B. M. Mehtre, M. S. Kankanhalli, A. D. Narasimhalu, and G. C. Man. Color matching for image retrieval. Pattern Recognition Letters, 16:325–331, Mar. 1995. [10] G. Pass and R. Zabih. Histogram refinement for content based image retrieval. In IEEE Workshop on Applications of Computer Vision, pages 96–102, 1996. [11] B. Reusch. Mathematics of fuzzy logic. In H. J. Zimmermann, D. Dasc˘alu, and M. G. Negoit¸a˘ , editors, Real World Applications of Intelligent Technologies, pages 15– 52, Bucures¸ti, Romania, 1996. Romanian Academy Publ. House. [12] G. Sharma and H. J. Trusell. Digital color imaging. IEEE Trans. on Image Processing, 6(7):901–932, Jul. 1997. [13] M. J. Swain and D. H. Ballard. Color indexing. International Journal of Computer Vision, 7(1):11–32, 1991. [14] C. Vertan and N. Boujemaa. Using fuzzy histograms and distances for color image retrieval. In Proc. of CIR’2000, Brighton, United Kingdom, 4-5 May 2000. [15] C. Vertan and V. Buzuloiu. Fuzzy nonlinear filtering of color images: A survey. In E. Kerre and M. Nachtegael, editors, Fuzzy Techniques in Image Processing, Heidelberg, Germany, 2000. Physica Verlag. [16] H. J. Zimmermann. Fuzzy Sets, Decision Making and Expert Systems. Kluwer Academic Publ., Boston MA, 1987.
