Content-based image retrieval focuses on intuitive and efficient methods for retrieving images from databases based on the content of the images. A new entropy function that serves as a measure of information content in an image termed as ‘an information theoretic measure’ is devised in this paper. Among the various query paradigms, query by example (QBE) is adopted to set a query image for retrieval from a large image database. In this paper, colour and texture features are extracted using the new entropy function and the dominant colour is considered as a visual feature for a particular set of images. Thus colour and texture features constitute the two-dimensional feature vector for indexing the images. The low dimensionality of the feature vector speeds up the atomic query. Indices in a large database system help retrieve the images relevant to the query image without looking at every image in the database. The entropy values of colour and texture and the dominant colour are considered for measuring the similarity. The utility of the proposed image retrieval system based on the information theoretic measures is demonstrated on a benchmark dataset.

Keywords:    Image retrieval,   fuzzy features,   descriptors,   entropy,   indexing

The use of entropy in an image retrieval system is not as popular as compared to other methods which utilize wavelets or colour, texture, and shape descriptors. But the potentiality of entropy as a descriptor cannot be ignored and in the recent past, many researchers have started exploring the possibility of using entropy in different domains. Entropy has been found effectively useful in image indexing^4,16,11,18 and in similarity measures^12,16,20.

The term entropy as a scientific concept was first used in thermodynamics by Clausius¹⁷. Its probabilistic interpretation in the context of statistical mechanics is attributed to Boltzmann¹⁹. Shannon¹ has used this concept to describe the properties of long sequences of symbols, and applied the results to a number of basic problems in coding theory and data transmission. Later the definition of entropy was extended to the field of information theory. The entropy of a system as defined by Shannon¹ gives a measure of uncertainty about the actual structure of the image. Shannon’s definition based on the information gain from an event is inversely proportional to its probability of occurrence.

The entropy of an image is used for different applications in image processing. The interpretation of entropy in an image depends on how an event is defined and also the definition of its posterior probability. In general, gray level is considered as an event and colour histogram as its probability density function. In addition to this, it is assumed that gray levels are statistically independent. Pun⁵ and Kapur⁶, et al. have used the Shannon’s concept to define the entropy of an image assuming that an image is entirely represented by its gray level histogram only. Leung⁷, et al. have attempted to isolate an object from the background by using the Gray-scale Image Entropy. The entropy (Shannon’s) of the histogram may be taken as a measure of information content in an image; such entropy is also called global information measure of the image. A low value of entropy indicates the skewness of the distribution of gray values, while a high value may be taken as an indicator of nearly uniform distribution of gray values. Definitely the histogram and the global entropy are not dependent on the spatial distribution of gray values in the image. The co-occurrence matrix² captures the spatial details of an image to some extent. The entropy of the co-occurrence matrix gives another measure of image information known as local entropy or second order entropy. Likewise the conditional entropy of a partitioned image can also be defined.

In texture analysis, an important approach to region description is to quantify its texture content. The randomness is the basic property of texture. By exploiting this fact, entropy as a statistical descriptor of texture could measure the variability in the image.

Pal and Pal⁸ define a new entropy function based on the exponential behavior of information gain and applied co-occurrence based entropy methods for image thresholding. Zachary¹⁶ attempts to use entropy as a visual feature of an image and showed how effectively entropy can be employed for indexing and also as a similarity measure of images in an image retrieval system. In IKONA¹¹, a region-based image retrieval system, human faces are identified and preprocessed using the entropy map which assigns a saliency for each pixel in the face. This saliency is expressed as the entropy of a local gray level distribution in a region around each pixel.

A new entropy function is presented in this paper. This entropy function is so designed that it can be efficiently used for image analysis. The properties and proofs of the proposed entropy function are presented. This new function is compared with the well known entropy functions. Two entropy based features with one feature representing the colour information and the other representing the texture information are derived from an image. Apart from this, another visual descriptor of the image called the dominant colour is described. These entropy based features are further used in the multi dimensional indexing technique. An interim result set is created using the indices of images for improving the performance of the retrieval system. The results of image retrieval will be compared with those of the classical model proposed by Swain and Ballard¹⁵.

Most of the entropy functions are not suitable for representing the information in a fuzzy set. These include Shannon¹, Renyi⁹ and Pal¹⁰ et al. entropy functions. These entropy functions are generalised by introducing a polynomial in the exponential gain function. The proposed entropy function is shown to satisfy the basic properties of entropy and then Pal and Pal’s entropy function is proved to be the special case of this function.

The function involved in the entropy need not be a membership function; it could be any feature. It may be noted that when we use a membership function, the unknown parameters of this membership function will parameterize the entropy function indirectly. However, the choice of a suitable membership function is not easy. Hence, the main motivation behind development of the entropy function is our concern to represent the information/uncertainty contained in a fuzzy set.

Here, authors are mainly concerned with a single fuzzy set. However in a fuzzy rule usually many fuzzy sets are encountered, but this case will be addressed in the future work. The definition of Pal and Pal¹⁰ entropy functionis now extended considering the exponential behavior of the gain function. This will pave the way to devise a new entropy function for representing the information in a fuzzy set.

2.1 Definition and Properties

The information gain corresponding to the occurrence of the i^th event is defined as

$I(p_i)=e^{-(a{p}_i^3+b{p}_i^2+c{p}_i+d)}$ (1)

for all probabilities p_i∊[0,1], $H_{Sn}^1(P_n)=-{\displaystyle \sum _{i=1}^n{p}_i}\log p_i$ and a, b, c and d are the real-valued parameters.

The entropy is expressed by

$H=E(I(p_i))={\displaystyle \sum _{i=1}^n{p}_{i}I(p_i)}$ (2)

Note that the above entropy function is an expectation of the information gain function. Some of the important properties associated with this function are stated now.

Property 1:	$I(p_i)=e^{-(a{p}_i^3+b{p}_i^2+c{p}_i+d)}$ is a continuous function for all pi∊[0,1]
Property 2:	I(pi) is bounded
Property 3:	With the increase in pi, I(pi) decreases.
Property 4:	$H(P)={\displaystyle \sum p_i*I(p_i)}$ is a continuous function for all pi∊[0,1] real valued a, b, c and d parameters.
Property 5:	If p1 = p2 = ... = pn = 1/n then H(P) is an increasing function of n.
Property 6:	$H(P)={\displaystyle {\sum }_{i=1}^n{p}_i*e^{-(a{p}_i^3+b{p}_i^2+c{p}_i+d)}}$ where, 0 ≤ pi ≤ 1 and ${\displaystyle \sum p_i=1}$ is a concave function.
Property 7:	Consider a partition A = [A1, A2, … An] with the probabilities, pi = Pr[Ai] and assume that p1<p2. If p1 is increased and p2 is decreased by an equal amount, say δ (δ>0 and δ ≤ (p2 – p1)/2), then the entropy increases.
Property 8:	Entropy is maximum when all pi’s are equal. In other words, H(P) ≤ H(1/n, 1/n, n,...,1/n)
Property 9:	Entropy is minimum if and only if all pi’s except one are zeros and that single pi is equal to 1.
Property 10:	Consider the partition of the event space as A = [A1, A2, … An] and the probability pi = Pr(Ai). If a new partition B is formed by subdividing one of the sets of A, then H(B) ≥ H(A).

The proofs of some of the above properties are consigned to Appendix ‘A’.

2.1.1. Normalised Entropy

The normalised entropy H_N can be defined as

$H_N=(H-e^{-(a+b+c+d)})/\text{λ}$ (3)

where, The constant $\text{λ}=e^{-(\frac{a}{n^3}+\frac{b}{n^2}+\frac{c}{n}+d)}-e^{-(a+b+c+d)}$ ; a, b, c and d are real valued parameters; and n is the number of events in the probabilistic experiment (or the number of states in the system).

The normalised entropy satisfies all the properties of an entropy function.

2.1.2. Conditional Entropy

Consider two partitions A = [A₁, A₂, … A_n] and B = [B₁, B₂, … B_m] and let us define that the product of two partitions, A = [A_i] and B = [B_j] is a partition whose elements are all intersections A_iB_j and the product of partitions is denoted by A.B = [A_iB_j]. Let p_ij be the probability of the event A_iB_j, i.e., p_ij = P_r [A_iB_j] and the marginal probabilities p_i = P_r[A_i] is defined as,

$p_i={\displaystyle \sum _{j=1}^m{p}_{ij}}$

Similarly the marginal probability, q_j = P_r[B_j] can be enumerated as,

$q_j={\displaystyle \sum _{i=1}^n{p}_{ij}}$

The conditional entropy of A_i given that B_j has occurred is denoted by

$\mathrm{Pr}[A_i|B_j]=\mathrm{Pr}[A_i{B}_j]/\mathrm{Pr}[B_j]=p_{ij}/q_j=p_{i|j}$ (4)

Similarly,

$\mathrm{Pr}[B_j|A_i]=\mathrm{Pr}[A_i{B}_j]/\mathrm{Pr}[A_i]=p_{ij}/p_i=q_{j|i}$ (5)

Therefore the entropy of a partition A, given that B_j has occurred is given by H[A|B_j] as:

$H[A|B_j]={\displaystyle \sum _{i=1}^n{p}_{i|j}{e}^{-[a{p}_{i|j}{}^3+b{p}_{i|j}{}^2+c{p}_{i|j}+d]}}$

Thus the conditional entropy of A assuming B is therefore:

$H[A|B]={\displaystyle \sum _{j=1}^m{q}_{j}H[A|B_j]=}{\displaystyle \sum _{j=1}^m{\displaystyle \sum _{i=1}^n{q}_j{p}_{i|j}{e}^{-[a{p}_{i|j}{}^3+b{p}_{i|j}{}^2+c{p}_{i|j}+d]}}}$ (6)

Similarly,

$H[B|A]={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^m{p}_i{q}_{j|i}{e}^{-[a{q}_{j|i}{}^3+b{q}_{j|i}{}^2+c{q}_{j|i}+d]}}}$ (7)

Now the entropy of the product of the partitions, A.B is easily found to be

$H[A.B]={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^m{p}_{ij}{e}^{-[a{p}_{ij}{}^3+b{p}_{ij}{}^2+c{p}_{ij}+d]}}}$ (8)

2.2 Comparison with other Entropy Functions

In the last few decades treatment of uncertainty is one of the concerns in the research circles. Shannon’s entropy¹ is the pioneering work on the information measure. This entropy function is defined in the domain of probability with n-states and in that the information gain is inversely related to its probability of occurrence.

$H_{Sn}^1(P_n)=-{\displaystyle \sum _{i=1}^n{p}_i\log p_i}$ (9)

Renyi⁹ has extended the definition of Shannon’s entropy to an incomplete probability distribution. The Renyi’s entropy of order α is of the form

$H_{Rn}^1(P_n,\alpha )=\frac{1}{1-\alpha }\log {\left[\frac{{\displaystyle \sum _{i=1}^n{p}_i{}^{\alpha }}}{{\displaystyle \sum _{i=1}^n{p}_i}}\right]}_{,}{}_{\alpha >0,\alpha \ne 1}$ (10)

It is noted that as α tends to 1, Renyi’s entropy matches with Shannon’s entropy. In contrast to Shannon’s entropy, Pal and Pal’s entropy function considers the information gain as an exponential function: e^(1–p_i)

$H_{PPn}^1(P_n)={\displaystyle \sum _{i=1}^n{p}_i{e}^{(1-p_i)}}$ (11)

The normalised Pal and Pal’s Entropy is given by

$H_{Nor}^1(P_n)=\frac{H_{PPn}^1(P_n)-1}{(e^{1-\frac{1}{n}}-1)}$ (12)

Following the above entropy function, an exponential entropy function is devised with an eye on incorporating information into it. A significant feature of this entropy function is that it captures the inherent uncertainty in the fuzzy sets.

The uncertainty in a fuzzy set is non-statistical in nature and it plays an important role in fuzzy image processing. Moreover, the use of a polynomial in the exponential function yields the gain function bestowed with four tunable parameters. The parameters of the new entropy function provide controls on the information gain and proper tuning of these parameters by way of optimisation leads to the correct measure of uncertainty.

Recall the new entropy function defined above as

$H={\displaystyle \sum _{i=1}^n{p}_i{e}^{-(a{p}_i^3+b{p}_i^2+c{p}_i+d)}}$ (13)

and its corresponding normalised entropy is as follows

$H_N=(H-e^{-(a+b+c+d)})/(e^{-(\frac{a}{n^3}+\frac{b}{n^2}+\frac{c}{n}+d)}-e^{-(a+b+c+d)})$ (14)

This entropy function behaves like Pal and Pal’s entropy function for a = 0, b = 0, c = 1 and d = -1. The curves in Figs 1 and 2 show Shannon’s entropy, Normalised Pal and Pal’s entropy and Normalised new entropy for a two-state system for the two sets of parameter values. It may be observed that though the new entropy function behaves like the Shannon’s and Pal and Pal’s entropy functions yet it expands and contracts for varying values of the parameters.

2.3 Possible Applications

• Biometrics: In finger print identification, we can model the minutiae points by finding their distances with respect to a reference point which may be selected as the one with the highest curvature. In the palm print, we can model the points on the primary lines (there are mainly three such lines) and use this information for authentication.
• Medical Image processing: Breast cancer and brain tumor detection can be easily attempted by the entropy based modeling. In both these problems, issues in the affected organs undergo textural changes on the infringement of malignancy. The tumour regions can be extracted by applying the entropy function in a shifting window. The tissues in the affected portions naturally show entropy values different from those of the benign tissues for a chosen set of coefficients of the entropy function.
• Cryptography: The power of the proposed entropy can be best utilized in the encryption of secrete keys for secure transmission. In the above we have cited a few problems but one can harvest many fields should the ingenuity and imagination permit. However, in this paper its application to image retrieval will be discussed by way of indexing.

Many visual features have been explored in the literature on content-based image retrieval (CBIR) for the purpose of depicting colour, texture, shape and other properties of an image. Combining the various features usually achieves better performance in retrieval. Although a large number of features could represent the image very accurately, the inherent problem with this approach is the shortage of storage capacity for large image database. Hence an efficient multidimensional indexing technique is required for dimension reduction.

The objective of this section is to reduce the dimensionality of the feature space and to improve the performance of the retrieval process. For this, the entropy-based features are extracted from the images. The entropy of an image, by definition, is the measure of information content in the image⁸. As will be seen, the entropy function maps an n-dimensional vector to a single real number (i.e. one dimensional space) and so it can be regarded as a dimension reduction operator.

The extracted features from an image are stored to serve as an index of that image. Since the expensive management of storage and comparison time is less significant than the retrieval accuracy, only three concise and precise features are used to describe the contents of the image. These are colour entropy, texture entropy and dominant colour of the image.

3.1 Entropy-based Image Features

The entropy of a system as defined by Shannon¹ gives a measure of uncertainty about its actual structure. Shannon’s definition based on the information gain from an event is inversely proportional to its probability of occurrence. Pun⁵ and Kapur⁶, et al. have used Shannon’s concept to define entropy of an image assuming that the image is entirely represented by its gray level histogram only. Unlike the logarithmic behavior of Shannon’s entropy, the gain function in our entropy definition is of exponential nature as discussed in Section II. Two entropy based image features – colour entropy and texture entropy are now presented.

3.1.1 Colour Entropy

The RGB colour space is chosen to represent the image. Let F = {f(x, y)}M × N be an image of size M × N where f(x, y) is the colour vector (r, g, b) in the RGB space at (x, y) point and N(r, g, b) is the frequency of the colour vector (r, g, b).

Then, ${\displaystyle \sum _r{\displaystyle \sum _g{\displaystyle \sum _b{N}_{(r,g,b)}=M\times N}}}$

In a natural image, it has been observed that out of 2563 different colour levels, a small fraction of different colour levels are actually used. So instead of considering all colour levels, the colour levels of an image are quantized adaptively. To achieve this, the available colour levels are clustered into colour bins.

The number of bins is not preset; it depends on the distribution of colour in that particular image. The above algorithm adaptively clusters all the colour levels into bins. Pun⁵ and Kapur⁶, et al. use the gray-level histogram to represent the image; here the histogram is extended to the colour bins. It is generally assumed that the distribution of colours across an image follows the uniform distribution, i.e. each colour has a 1/(M × N) probability where the image size is M × N. The algorithm for forming bins is given Algorithm 1.

Let,Z = {z₁, z₂, … z_n} be the set of events that corresponds to the colour bins. Let us consider the probability of the colour bin z_i as p(z_i) = (Number of pixels in the colour bin Z_i)/ M × N. In this context, the colour entropy is taken in the normalised form, H_{N, Colour} given by

$\begin{array}{l}{H}_{N,Color}=(H_{Color}-e^{-(a+b+c+d)})/\text{λ}\\ H_{Color}={\displaystyle \sum _{i=1}^{n}p(z_i)e^{[-\{a^{*}{p}^3(z_i)+b^{*}{p}^2(z_i)+c^{*}p(z_i)+d\}]}}\end{array}$ (15)

with

where, $\text{λ}=[e^{-(\frac{a}{n^3}+\frac{b}{n^2}+\frac{c}{n}+d)}-e^{-(a+b+c+d)}]$ and n is the number of colour bins.

3.1.2 Entropy Optimisation

The entropy optimisation is resorted to estimate the four tunable parameters: a,b,c and d. The derivatives of H_N with respect to a,b,c and d are obtained from:

$\begin{array}{l}\frac{\partial H_N}{\partial a}={\mathrm{\Lambda }}_1+\frac{[-{\displaystyle \sum _{i=1}^n{p}^4(z_i)*e^{-\{a{p}^3(z_i)+b{p}^2(z_i)+cp(z_i)+d\}}]+H_1]}}{H_2-H_1}\\ \frac{\partial H_N}{\partial b}={\mathrm{\Lambda }}_2+\frac{[-{\displaystyle \sum _{i=1}^n{p}^3(z_i)*e^{-\{a{p}^3(z_i)+b{p}^2(z_i)+cp(z_i)+d\}}+H_1]}}{H_2-H_1}\\ \frac{\partial H_N}{\partial c}={\mathrm{\Lambda }}_3+\frac{[-{\displaystyle \sum _{i=1}^n{p}^2(z_i)*e^{-\{a{p}^3(z_i)+b{p}^2(z_i)+cp(z_i)+d\}}+H_1]}}{H_2-H_1}\\ \frac{\partial H_N}{\partial d}={\mathrm{\Lambda }}_4+\frac{[-{\displaystyle \sum _{i=1}^{n}p(z_i)*e^{-\{a{p}^3(z_i)+b{p}^2(z_i)+cp(z_i)+d\}}+H_1]}}{H_2-H_1}\end{array}$ (16)

where,

$\begin{array}{l}{\mathrm{\Lambda }}_1=\frac{[{\displaystyle \sum _{i=1}^{n}p(z_i)*e^{-\{a{p}^3(z_i)+b{p}^2(z_i)+cp(z_i)+d\}}-H_1]}}{{(H_2-H_1)}^2}\left[\frac{H_2}{n^3}-H_1\right]\\ {\mathrm{\Lambda }}_2=\frac{[{\displaystyle \sum _{i=1}^{n}p(z_i)*e^{-\{a{p}^3(z_i)+b{p}^2(z_i)+cp(z_i)+d\}}-H_1]}}{{(H_2-H_1)}^2}\left(\frac{H_2}{n^2}-H_1\right)\\ {\mathrm{\Lambda }}_3=\frac{[{\displaystyle \sum _{i=1}^{n}p(z_i)*e^{-\{a{p}^3(z_i)+b{p}^2(z_i)+cp(z_i)+d\}}-H_1]}}{{(H_2-H_1)}^2}\left(\frac{H_2}{n}-H_1\right)\\ {\mathrm{\Lambda }}_4=\frac{[{\displaystyle \sum _{i=1}^{n}p(z_i)*e^{-\{a{p}^3(z_i)+b{p}^2(z_i)+cp(z_i)+d\}}-H_1]}}{{(H_2-H_1)}^2}\left(\frac{H_2}{1}-H_1\right)\end{array}$

and $H_1=e^{-(a+b+c+d)},H_2=e^{-(\frac{a}{n^3}+\frac{b}{n^2}+\frac{c}{n}+d)}$

Then the parameters are updated using gradient descent learning as

$\begin{array}{l}{a}^{New}=a^{Old}-{\text{ε}}_4(i)\frac{\partial H_N}{\partial a}\\ b^{New}=b^{Old}-{\text{ε}}_4(i)\frac{\partial H_N}{\partial b}\\ c^{New}=c^{Old}-{\text{ε}}_4(i)\frac{\partial H_N}{\partial c}\\ d^{New}=d^{Old}-{\text{ε}}_4(i)\frac{\partial H_N}{\partial d}\end{array}$ (17)

where the learning rates ε(i). As this learning has convergence problems we propose reinforcement learning.

3.1.3 Reinforcement Learning

The reinforcement learning requires some re-use policy of how to use the past information.

Exploitation: In this we exploit the Reuse policy which requires integrating knowledge of the past policy into the current learning process. Here we need to bias the exploratory process of the new policy with the past one. We have used here the sigmoid function for ε in which cumulative of the past errors is biased by the term k₂ and the slope or gain of the function is changed by the term k₁.

Exploration: In the earlier work k₁ and k₂ were incremented by constant, but they are updated here by random numbers thus boosting exploration. The proposed¹¹ reinforcement learning gets stuck up in the local minima. This has been modified to incorporate evolutionary feature²⁷. In this each parameter is updated by a number of updating laws called a population each having a pair of random numbers for k₁ and k₂. The law yielding the minimum is considered as the global solution. Because of this it overcomes the drawback of local minima by taking into account both exploitation and exploration strategies.

If n is the population size, then we make use of the Reinforced learning law given by Hanmandlu and Murthy²⁷

${\text{ε}}_l(i)=e^{-(k_{1l}(i)}{\displaystyle \sum err(j,i)+k_{2l}(i))}$ (18)

where $err(j,i)=H_N(j,i)-H_N{}^{new}(j-1,i)=\Delta H_N(j,i)$ ; l=1,1,..,4, i =1 to n and j is the current iteration.

The initial values of k_1l (i) and k_2l (i) are taken both as random numbers. We use the following policy to adjust the values of k_1l (i) and k_2l (i). This consists of the following steps:

If ${\displaystyle \sum err(j,i)}$ is increasing, then ε(i) must decrease. So k_1l(i) should increase.

1. If ${\displaystyle \sum err(j,i)}$ is decreasing, then ε(i) need not change. So ^k2l (i) should increase.

2. If ${\displaystyle \sum err(j,i)}$ is constant, then ε(i) should not change. So k_1l (i) and k_2l (i) are not changed.

If H_N(j,i) is not differentiable then parameter of interest, say a, is updated as follows:

$\begin{array}{l}a(i+1)=a(i)-\text{ε}(i)\frac{H_N(a_{old}(i)+p)-H_N(a_{old}(i))}{p}\\ =x(i)+\text{ε}(i)\frac{\Delta f}{p}\end{array}$ (19)

where, p = 0.0001.

The evolution is bestowed by the following procedure: We create a population of solution processes (particles) for each parameter. Let this population be denoted as n (taken to be 10). The function values of all particles H_N(j,i) are arranged in the ascending order. After that half of the populations with high values of function are eliminated as they are unfit to propagate to new generation. Thereafter reproduction is carried out by the rest half of the population. This procedure continued until we reach the global minimum of the function.

3.1.4 Colour Entropy Results

In this sub-section, colour entropy values are computed for different natural images. The parameters a, b, c, d are initialized to one and then the entropy optimisation technique is applied to find the normalised entropy value termed as colour entropy. Table 1 shows the colour entropy values and the corresponding optimised parameter values.

3.2 Texture Entropy

The ambiguities in texture arising due to the fuzzy nature of image function allow us to devise fuzzy texture features. So rather than using the colour histogram to represent an image, the fuzzy features that capture the fuzziness in the texture property are extracted about the neighborhood of each pixel. Since texture is region based, arrangement of image functions (i.e., intensities) of pixels in a local region, say, a window is made use of in order to characterize the texture using the Gaussian type membership function. The cumulative response about the central pixel from this window replaces the pixel intensity giving rise to the texture image when taken over the entire image.

3.2.1 Extraction of Fuzzy Features

To convert the spatial domain image into the fuzzy domain, the spatial arrangement of gray levels of pixels over a window is utilised. The fuzzy property can be expressed in terms of a membership function. A membership function to this effect is represented by the Gaussian type function.

${\text{μ}}_{(k,l)}(i,j)=\exp \left[-{\{(x(i,j)-x(k,l))/\tau \}}^2\right]$ (20)

where, x (i, j) is the gray level of the pixel at the (i,j)^th position and τ is the fuzzifier which is specified to be the window size (τ is taken as 5)

We note that

${}^{{\text{μ}}_{(i,j)}(k,l)=1}\text{if}{}^{x(i,j)=x(k,l)}$ (21)

To consider the response from the neighboring pixels, the cumulative response of (i, j)^th pixel is obtained as

$y(i,j)={\displaystyle \sum _{k,l}{\text{μ}}_{(k,l)}(i,j)*x(k,l)/{\displaystyle \sum _{k,l}{\text{μ}}_{(k,l)}(i,j)}}$ (22)

This is the defuzzified response of the (i,j)^th pixel over the window of size 5. This process is repeated for all pixels in the image resulting in a texture feature image consisting of all the defuzzified values. For convenience of notation, the matrix formed by y(i,j) is designated as the response matrix, Y which in turn would represent the texture feature image.

Let Z = {z₁, z₂, … zn} be the set of distinct responses of Y. Let us consider the probability of the texture response z_i as p(z_i) = (Number of pixels having the texture response z_i)/ M × N. On the heels of the normalised colour entropy, here comes the normalised texture entropy H_N,Texture as

$\begin{array}{l}{H}_{N,Texture}=(H_{Texture}-e^{-(a+b+c+d)})/\text{λ}\\ \text{With}{H}_{Texture}={\displaystyle \sum _{i=1}^{n}p(z_i)*e^{-\{a*p^3(z_i)+b^{*}{p}^2(z_i)+c^{*}p(z_i)+d\}}}\end{array}$ (23)

where, $\text{λ}=[e^{-(\frac{a}{n^3}+\frac{b}{n^2}+\frac{c}{n}+d)}-e^{-(a+b+c+d)}]$ and n is the number of distinct responses.

In the entropy function (22, 23), a, b, c and d are four tunable parameters with 0≤H_N,Texture ≤1. Here the texture entropy is optimised to estimate these parameters using the optimisation technique described earlier.

In order to compute the texture entropy values for different natural images, the values of the parameters - a, b, c, d are initially set at 1 and then the normalised entropy value is calculated using the entropy optimisation technique. The texture entropy values and the corresponding optimised parameter values are shown in Table 2.

3.2.2 Visual Image Feature

It may be noted that the images might have the similar statistical features yet they are visually different. The choice of an appropriate visual feature plays an important role in classifying the visually similar images. There are several visual features – colour, texture, shape, contrast, coarseness, normalised area of an object etc. proposed by earlier researchers^{13, 14}. In the present work, we make use of another visual feature – dominant colour of an image.

Dominant colour of an image is the particular colour level that has the highest frequency in the image. It is a perceptual property of an image. As the CIE Lab colour space is perceptually uniform, the dominant colour is transformed to the lab colour space consisting of luminance component L and chrominance components C = {a, b}. Table 3 shows the RGB values and the CIE Lab values of the dominant colour and the percentage area covered by this colour.

The images of sea and sunset category, shown in Table 3, have distinct dominant colour, which is necessarily an important visual feature. The images of the same category will have nearly the same dominant colour, therefore in the retrieval system, CIE Lab values of the dominant colour could be used to classify similar images.

It is possible that the images of different categories have the same dominant colour, so the dominant colour is appropriate to be one of the visual features for classification.

3.2.3 Indexing through Feature Vector

As the image collection is getting larger and larger, the retrieval speed is becoming a bottleneck. Hence effective high dimensional indexing techniques need to be explored. The high dimensionality of feature vectors is normally of the order of 10². Applying the dimension reduction on the feature vectors, an embedded dimension much lower than the initial dimension though still higher for linear ordering is obtained. Therefore a multi-dimensional indexing scheme is required to index the reduced embedded dimensional feature vectors. From this discussion it follows that the multi-dimensional indexing owes its allegiance to the high dimensionality of the feature space.

As there are only three features, viz., colour entropy, texture entropy and dominant colour used in this work, the dimension of feature space is too small to apply any dimension reduction algorithm. An entropy-based two dimensional indexing is employed here using both colour and texture entropy values. In our method, the dimension of the feature vectors is not dynamic; i.e., it remains fixed as there is no need for any sophisticated tree-data structure for multidimensional indexing.

A feature vector of an image indexed by a pair of entropy values of colour and texture becomes a point in the two-dimensional feature plane whose axes are colour entropy and texture entropy.

The concept of interim result is invoked here. The interim result set is a subset of image search space containing images semantically similar to the query image. The above indexing scheme would improve the retrieval performance by creating an interim result set. For a particular query image, the colour entropy and texture entropy, say (qColourEnt, qTextureEnt) can be easily calculated. Now here is the algorithm for creating an interim result set (Algorithm 2).

In the above procedure, the choice of ε is very crucial, because the size of the interim result set is directly proportional to the value of ε. It is important to note that the value of ε should depend on the size of the feature space and also on the entropy values of colour and texture of the query image.

Let ${\text{ξ}}_{color}^2$ and ${\text{ξ}}_{Texture}^2$ represent the second order moments of entropy values of colour entropy and texture of the query image respectively. The expressions for the statistical descriptors are as follows:

${\text{ξ}}_{Color}=\sqrt{\frac{1}{n}{\displaystyle \sum _{i=1}^n{(cEn{t}_i-qColorEnt)}^2}}$ (24)

${\text{ξ}}_{Color}=\sqrt{\frac{1}{n}{\displaystyle \sum _{i=1}^n{(tEn{t}_i-qTextureEnt)}^2}}$ (25)

where, n is the size of feature space, cEnt_i and tEnt_i denote the colour entropy and texture entropy of i^th image respectively.

An expression for ε is coined by

$\text{ε}={\text{k*Max(}}^{\text{ξ}}Color{,}^{\text{ξ}}Texture)$ (26)

where, k is any positive real number.

The interim result set contains all the feature points having a distance of less than or equal to ε from the query image. One of the purposes of creating the interim result set is to reduce the search space without sacrificing the correctness of results of the retrieval process.

3.2.4 Experimental Results

A set of 9907 images from low resolution web-crawled miscellaneous database²⁶ used in WBIIS²⁵ is our benchmark dataset for generating the query results. Next the interim result set for different query images is created. The recall for the interim result set denotes the percentage of correct retrieved images out of all correct images in the image database. The ratio of the size of the interim result set to the original size of the image database gives the reduction factor. Therefore a large recall value with high reduction factor indicates the efficiency of the algorithm.

It may be observed from Table 4 that the reduction factor increases by decreasing the value of ε. For lower value of ε naturally recall also decreases. The higher recall value indicates the correctness of the system; hence the reduction factor is increased so as to keep the recall value higher. Here are the results for other query images on the same image database.

Any search engine, text-based or otherwise, is plagued by the problem of un-related matches. Often in the case of text based search engines, this hitch arises from the use of ambiguous keywords, such as bank, interest. Content-based image retrieval system allows a user to set query by an example image²¹, which ideally removes the ambiguity in setting up of queries. But the success of the image retrieval depends on the extraction of image features and measurement of similarity of query image with the images in a large data collection. In continuation of the feature extraction and the effective indexing methodology in Section 3, the distance measures between any two images in the interim result set are the necessary ingredients for comparison. Furthermore, the performance of the retrieval process will be compared with the traditional colour histogram matching¹⁵.

4.1 Image Distance Measure

To represent an image the required are the entropy based feature descriptors: colour entropy and texture entropy and a visual colour feature – dominant colour. These feature descriptors allow us to define a distance metric that closely matches the human perception. The idea is that the similarity between the two images should be measured in terms of not only the closeness of colour and texture distributions but also the closeness of the dominant colour of the image.

Consider two images, a query image I_Q and a target image I_T to measure the distance. The dominant colours of both the images are denoted by CQ(L_q, a_q, b_q) and CT(L_t, a_t, b_t) and the other two entropy based features – colour entropy and texture entropy, for query image and target image by ColourEnt_Q, ColourEnt_T and TexEnt_Q, TexEnt_T respectively. Then the distance between the images is computed as a linear combination of two L₂ distances. The first L₂ distance is measured between the two dominant colours; the lower value of this distance indicates the visual closeness in terms of colour ignoring the information in the image, which is given by the entropy. So, the distance between the dominant colours is:

$D_1=\sqrt{{(L_q-L_t)}^2+{(a_q-a_t)}^2+{(b_q-b_t)}^2}$ (27)

The second L₂ distance is measured between the entropy based feature vectors (colour entropy, texture entropy). The entropy is a real number which indicates the amount of information contained in an image in terms of colour distribution and textural pattern. The lower value of second distance indicates the similarity of images in terms of content.

$D_2=\sqrt{{(ColorEn{t}_T-ColorEn{t}_Q)}^2+{(TexEn{t}_T-TexEn{t}_Q)}^2}$ (28)

The distance between two images I_Q and I_T is defined as

$Dist(I_Q,I_T)=\alpha *D_1+(1-\alpha )*100*D_2$ (29)

where, 0 ≤ α ≤ 1

The value of D₂ lies between 0 to 1 and it is also very low in comparison to D₁. To scale both the distances at the same level, a weight of 100 is assigned to D₂. The value of α in the distance measure formula can be interpreted as the relative importance between the dominant colour and the information content. The range of α varies from 0 to 1. The higher value of α assigns more importance to the dominant colour than the information content in the retrieval of similar images. In sunset image, dominant colour has more importance, so the user could set the value of α more than 0.5 (which stands for equal importance) in forming the query for the image retrieval. It is important to note that the background colour or dominant colour might be irrelevant in many images but this would mislead the retrieval process. The value of α should be set to 0 for the queries where the dominant colour does not have any importance.

Table 8 shows that the distances between the similar images are comparatively less than the distances between the different categorical images. In this table, the distances between the query image and sample images are measured for α = 0.5.

4.2 Image Retrieval by Querying

A search engine whether text-based or otherwise is prone to unwanted matches. There are several reasons to get incorrect matches; one of them is due to the use of ambiguous keywords like interest, bank, etc., and another due to the use of inappropriate words to describe the desired images. In the proposed content-based image retrieval (CBIR) system, the user can set the query by an example from the query image set. In our system, the natural and real image databases are categorized into different classes of images, namely, animal, aircraft, architecture, landscape, sea shores, vehicles, flowers, human activities, etc. A small set of query images is presented in Table 9.

4.3 Colour Histogram Matching

The axes used for the histograms are the three opponent colour axes, assigned as follows:

$r_g=r-g$ (30)

$b_y=2\times b-r-g$ (31)

$w_b=r+g+b$ (32)

Here r, g, and b represent red, green, and blue signals, respectively. The r_g, b_y, and w_b axes are analogous to the opponent colour axes used by the human visual system²². They are used here simply to allow the intensity (w_b) axis to be more coarsely sampled than the other two, because the intensity axis is more sensitive to the variation in lighting from shadows and distance from the light source. The wb axis is divided into 8 sections while the r_g and b_y axes are each divided into 16 sections, for a total of 2048 bins. As the total intensity limits the colour differences possible, only a fraction of them can actually receive counts. To clarify this point, suppose that the camera outputs a maximum number of intensity levels, M on each channel. Letting w_b = 0(r = g = b = 0) or w_b = 3M (r = g = b =M), both axes b_y and w_b turn out to be 0. Thus the maximum intensity level restricts the available axes.

Several measures have been proposed for the dissimilarity between two histograms, H = {h_i} and K = {k_i}. The bin-by-bin dissimilarity is determined by comparing the contents of the corresponding histogram bins, i.e. h_i and k_i for all i but not h_iand k_jfor i≠j. The dissimilarity between the two histograms is determined as a sum of all pair-wise comparisons and it implies a binary ground distance with a threshold depending on the bin size.

Minkowski-Form Distance: This distance is commonly defined as:

$d_{Lr}(H,K)={\left({\displaystyle \sum _i|h_i-k_i{|}^r}\right)}^{1/r}$ (33)

The L₁ distance is often used for computing dissimilarity between colour images¹⁵.

Kullback-Leibler Divergence and Jeffrey Divergence: The Kullback-Leibler divergence appears as:

$d_{KL}(H,K)={\displaystyle \sum _i{h}_i\log \frac{h_i}{k_i}}$ (34)

From the information theory point of view, the K-L divergence measures how inefficient it could be to code one histogram using the other as the code-book²³. However, the K-L divergence is non-symmetric and is sensitive to histogram binning. The empirically derived Jeffrey divergence is a modification of the K-L divergence that is numerically stable and robust with respect to noise and the size of histogram bins²⁴. The Jeffrey divergence is determined from:

$d_J(H,K)={\displaystyle \sum _i\left(h_i\log \frac{h_i}{m_i}+k_i\log \frac{k_i}{m_i}\right)}$ (35)

χ² statistics:

$d_{{\text{χ}}^2}(H,K)={\displaystyle \sum _i\frac{{(h_i-k_i)}^2}{m_i}}$ (36)

where, $m_i=\frac{h_i+k_i}{2}$

Given a query image with histogram H, each database image with histogram K receives a measure of dissimilarity for the query image. It is then easy to rank the database images based on their dissimilarity measures and return the best matches.

The experimental configuration for a process as subjective as computing similarity between the images must be carefully set up to gauge the results with other methods and we need to remove any perceptual biases of an experimenter. To minimize the human subjectivity, the random samples of different sizes are used and also a large sample space is taken as the image database. The large image database rules out the possibility of having dominancy of any particular category of images.

Our retrieval system is tested using 9907 images from the low resolution database²⁶ as mentioned above. This image collection contains different category of images like cars, roses, mountains, patterns, animal, landscape, seaside, flowers, human activities, etc. To provide numerical results, 8 sample images are taken randomly selected from four categories prior to the manual determination of the correctness of retried images. Each category contains at least 100 relevant images. A retrieved image is considered a match if it belongs to the same category of the query image.

The query results obtained by our entropy-based matching are compared with those obtained from colour histogram matching using different dissimilarity measures – χ² statistics, Jeffrey divergence and L₁ norm. Our content based image retrieval system is developed in Visual C++ 6.0 as an offline system on Intel Celeron machine with 1.40GHz processor and 256 MB RAM. The average retrieval time is 1 second per 1000 images. The process of image retrieval involves the following steps:

1. Create the interim result set using the proposed indexing scheme.
2. Extract feature values (colour entropy, texture entropy and dominant colour) for the query image.
3. Calculate the image distance of the query image with all images in the interim result set.
4. Rank the images according to the distance measured from the query image.
5. Set the highest rank of the retrieved image which has the minimum distance with respect to the query image.

The results of retrieval by our entropy-based system are compared with those from colour histogram matching¹⁵. Testing is carried out on a set of query images from the benchmark image²⁶ database of size 9907.

It may be observed from Fig. 4 that the performance of the proposed system on the car query (car Id: 1639) outperforms Jeffrey divergence, χ² statistics and L₁ norm, but the results from Fig. 5 show that entropy based matching is comparable with others. The entropy-based method retrieves the correct images using only 3 features – colour entropy, texture entropy and dominant colour thus enhancing the processing speed of the system with a reduced number of feature values.

The performance of other query images of the categories: Rose, seaside and pattern are now discussed.

Figures 10 and 11 both show the performance of the image retrieval for query images from the pattern category. The value of α is set to 0 to rule out the dominant colour information. The entropy based method retrieves the images purely based on entropy values and it is found to perform reasonably better than other histogram matching methods for the pattern category thus demonstrating its ability to retrieve semantically similar images.

It may be noted from the results of experiments that the proposed system performs better than the histogram matching for the query images, which possess distinct features in terms of texture or colour. In the rose, seaside category images, dominant colour and colour distribution are the prominent features and in these cases the proposed system performs reasonably well, but our proposed CBIR system has stooped to the subdued performance in the face of histogram matching for some cases. If the pattern images have the distinct texture features, then our system comes out with significantly better performance as shown in Figs 10 and 11.

A new entropy function that is aimed at representing the information in a fuzzy set is presented along with some important properties. The proposed entropy function has four tunable parameters that can be estimated by optimising the entropy function itself. For obtaining the global solution reinforcement learning along with population based approaches is used.

Two types of entropy based image features – colour entropy and texture entropy are utilized in this work. The colour entropy is described in terms of randomness in the distribution of colours in an image. For this, the newly devised entropy function comes handy and resorting to the optimisation of this entropy function yields the optimised colour entropy value. The resulting entropy values uniquely classify the non textured image. But for the textured image first the fuzzy texture features of the image are extracted and then the new entropy function is applied to the features for optimising the entropy values of texture.

Both the entropy based image features are derived in such a manner that they rely only on the colour and texture distributions of an image. In the course of research, the need for visual colour information is realized, consequently the dominant colour value is considered as the third image feature. Despite the efficiency of the RGB colour space, the pixels are transformed from the RGB colour space to the CIELAB colour space because the latter one has the property of perceptual uniformity. Falling in line, the CIELAB value of the dominant colour is also used as the visual feature.

Indices permit the computer in finding the images relevant to a query without looking at every image in the database. The indexing of the colour feature vectors is investigated to speed up the atomic queries. Dimensionality is one of the major concerns in the indexing scheme. The index speed degrades as the dimensionality of the data indexed increases. In the experiments carried out, images are indexed by the entropy values of colour and texture. The uniqueness of the entropy values of an image and their lower dimensionality rule out the possibility of using any sophisticated and computationally taxing multidimensional indexing data structures. The normalised entropy values of colour and texture are found to be more suitable as a pair to index an image. This indexing scheme is found to be effective in creating an interim result set for a query image. The algorithm for the interim result set and the results obtained ensure that the size of the database is reduced considerably without affecting the correctness of the results. The objective of an image retrieval system is to identify images from the database, which are similar to the query image. Similarity or distance measurement between the two images is derived from the empirical estimates of the image features. The three image features – colour entropy, texture entropy and dominant colour in Lab colour space are selected to formulate the similarity measure. Two distances: L₂ distance between the dominant colours of two images and L₂ distance of between the two colour entropy values and also between the texture entropy values are explored. These two L₂ distances are combined in linear form to give the measure of entropy. Table 8 demonstrates that the distance between semantically similar images are significantly low in comparison to the distance between the two dissimilar images. This measure is used to rank the retrieved images by their distances from the query image.

In the proposed retrieval system, the query paradigm is employed for setting up the query as ‘Query by Example’ (QBE). In that WBIIS test image dataset of 9907 colour miscellaneous images is organized into several categories with at least 100 images per category. The features of the images are extracted off-line and the similarity measures along with their ranking are computed at the time of executing the query. The query results so obtained are compared with those from the colour histogram matching using χ² Statistics, Jeffrey Divergence and L₁ norm. The results of our system are very promising in the retrieval of the similar images from the database. Exploring the entropy function for fuzzy modeling of the image retrieval system is the next phase of this work.

1. Shannon, C.E. A mathematical theory of communication. Bell Syst. Tech. J., 1948, 27, 379-423.

2. Jain, K. Fundamental of digital image processing. Prentice Hall of India, 2000.

3. Manjunath, S. & Ma, W.Y. Texture features for browsing and retrieval of image data. IEEE Trans. Pattern Anal. Mach. Intelligence, 1996, 18(8), 837-42.

4. Koskela, M.; Laaksonen, J. & Oja, E. Entropy-based measures for clustering and SOM topology to content-based image indexing and retrieval. In the Proceedings of the 17^th International Conference on Pattern Recognition (ICPR’04), 2004, edited by J. Kittler, M. Petrou, and M.S. Nixon, IEEE CS Press, US. 2004, 2, pp. 1005-1008.

5. Pun, T. A new method for gray-level picture thresholding using the entropy of the histogram. Signal Processing, 1980, 2, 223-37.

6. Kapur, J.N.; Sahoo, P.K. & Wong, A.K.C. A new method for gray-level picture thresholding using the entropy of the histogram. Compu. Graph. Vision Image Proc., 1985, 29, 273-85.

7. Leung, K.; Lam, F.K. & To, J.T.P. Entropy-based multiscale image segmentation with edge refinement. In the Proceedings of 1^st International Conference on Information Technology and Application (ICITA 2002), 2002, Bathurst, NSW Australia, 24-28 November 2002.

8. Pal, Nikhil R. & Pal, Sankar K. Entropy: A new definition and its applications. Syst. Man Cyber., 1991, 21(5), 1260-270.

9. Renyi, A. On measure of entropy and information. In the 4^th Berkeley Symposium of Mathematics Statistics and Probability, Berkeley, California, 1961, 1, pp. 547-61.

10. Pal, N.R. & Pal, S.K. Some Properties of the Exponential Entropy. Information Sciences, 1992, 66, 113-17.

11. Boujemaa, N.; Fauqueur, J.; Ferecatu, M.; Fleuret, F.; Gouet, V.; LeSaux, B. & Sahbi, H. IKONA: interactive specific and generic image retrieval. In International Workshop on Multimedia Content-based Indexing and Retrieval (MMCBIR’2001), France, 2001.

12. Moshfeghi, M.; Saiz, C. & Yu, H. Content-based Retrieval of medical images with relative entropy. In Proceedings of SPIE, 2004, 5371, pp. 259-267.

13. Byoung, K.; Jing, P. & Hyeran, B. Region-based image retrieval using probabilistic feature relevance learning. Pattern Anal. Appl., 2001, 4(2-3), 174-84.

14. Battiato, S.; Gallo, G. & Nicotra, S. Perceptive visual texture classification and retrieval. In the 12^th International Conference on Image Analysis and Processing, 2003, Mantova, Italy, 17-19 September 2003, pp. 524-29.

15. Swain, M. & Ballard, D. Colour indexing. Inter. J. Comp. Vision, 1991, 7(1), 11-32.

16. Zachary, J. M. Jr. Louisiana State University, 2000. PhD Dissertation.

17. Yagi, E. Analytical approach to Clausius’s first memoir on mechanical theory of heat (1850). Historia Sci. 1981, 20, 77-94.

18. Wang, J. Z.; Wiederhold, G.; Firschein, O. & Wei, S.X. Content- based image indexing and searching using daubechies’ wavelets. Int. J. Digital Libr., 1997, 1(4), 311-28.

19. Boltzmann, Ludwig (1896, 1898). Lectures on gas theory. Translated by Stephen G. Brush, Berkeley: University of California Press, New York, 1995.

20. Jain, R.; Murthy, S.N.J.; Chen, P.L.J. and Chatterjee, S. Similarity measures for image databases. In Proceedings of SPIE, 1995, 2420, pp. 58-65.

21. Faloutsos, C.; Barber, R.; Flickner, M.; Hafner, J.; Niblack, W.; Petkovic, D. & Equitz, W. Efficient and effective querying by image content. J. Intell. Inform. Syst., 1994, 3(3-4), 231-62.

22. Lennie, E, & D’Zmura, M. Mechanisms of colour vision. CRC Crit. Rev. Neurobiol. 1988, 3, 333-400

23. Cover, T.M. & Thomas, J.A. Elements of information theory. Wiley Series in Telecommunications. John Wiley & Sons, New York, NY, USA. 1991.

24. Puzicha, J.; Hofmann, T. & Buhmann, J. Non-parametric similarity measures for unsupervised texture segmentation and image retrieval. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1997. San Juan, Puerto Rico, pp. 267-72.

25. Wang, WBIIS J.Z.; Wiederhold, G.; Firschein, O. & Sha, X.W. Content-Based Image Indexing and Searching Using Daubechies’ Wavelets. Int. J. Digital Libraries, 1998, 1(4), 311-28.

26. Download databases for research comparison (low resolution web-crawled misc database used in WBIIS). http://wang.ist.psu.edu/docs/related.shtml (Accessed on: September 2010)

27. Hanmandlu, M. & Murthy, O.V.R. Reinforcement learning in the entropy based recognition of handwritten hindi numerals. In the 10^th World Multi-conference on Systemics, Cybernetics and Informatics, 16-19 July 2006, Orlando, Florida, USA.

APPENDIX ‘A’