Logistic Regression Models for a Fast CBIR Method Based on Feature Selection

1 Introduction

The rapid expansion of the Internet and the wide use of digital data in many real world applications in the field of medecine, security, communications, commerce and academia, increased the need for both efficient image database creation and retrieval procedures. For this reason, contentbased image retrieval (CBIR) approach was proposed. In this approach, each image from the database is associated with a feature vector capturing certain visual features of the image such as color, texture and shape. Then, a similarity measure is used to compare these feature vectors and to find similarities between images with the assumption that images that are close to each other in the feature space are also visually similar. Distance measures like the Euclidean distance have been the most widely used for feature vector comparison in the CBIR systems. However, these similarity measures are only based on the distances between feature vectors in the feature space. Therefore, because of the lack of information about the relative relevances of the featurebase feature vectors and because of the noise in these vectors, distance measures can fail and irrelevant features might hurt retrieval performance. Probabilistic approaches are a promising solution to this CBIR problem, that when compared to the standard CBIR methods based on the distance measures, can lead to a significant gain in retrieval accuracy. In fact, these approaches are capable of generating probabilistic similarity measures and highly customized metrics for computing image similarity based on the consideration and distinction of the relative feature vector relevances. As to previous works based on these probabilistic approaches, [Peng et al., 2004] used a binary classification to classify the database color image feature vectors as relevant or irrelevant, [Caenen and Pauwels, 2002] used the classical quadratic logistic regression model, in order to classify database image feature vectors as relevant or irrelevant, [Aksoy et al., 2000] used weighted L1 and L2 distances, in order to measure the similarity degree between two images and [Aksoy and Haralick, 2001] measure the similarity degree between a query image and a database image using a likelihood ratio derived from a Bayesian classifier.

In this paper, we investigate the effectiveness of a Bayesian logistic regression model based on a variational method, in order to adjust the weights of a pseudo-metric used in [Ksantini et al., 2006], and then to improve its discriminatory capacity and to increase image retrieval accuracy. This pseudometric makes use of the compressed and quantized versions of the Daubechies-8 wavelet decomposed feature vectors, and its weights were adjusted by the classical logistic regression. We will show that thanks to the variational method, the used Bayesian logistic regression model is a significantly better tool than the classical logistic regression model to compute the pseudo-metric weights and to improve the querying results. The retrieval method is fast, efficient and based on feature selection. The evaluation of the retrieval method using both models, separately, is performed using precision and scope curves as defined in [Kherfi and Ziou, 2006].

In the next section, we briefly define the pseudo-metric. In section 3, we briefly describe the pseudo-metric weight computation using the classical logistic regression model, while showing the limitations of this latter and that the Bayesian logistic regression model is more appropriate for the pseudometric weight computation. Then, we detail the Bayesian logistic regression model. Moreover, we will describe the data training performed for both models. The feature selection based image retrieval method and the feature vectors used to represent the database images are presented in section 4. Finally, in section 5, we will perform some experiments to validate the Bayesian logistic regression model and we will use the precision and scope, in order to show the advantage of the Bayesian logistic regression model over the classical logistic regression one, in terms of querying results.

2 The pseudo-metric

Given a query feature vector Q and a featurebase of |DB| feature vectors Tk (k = 1, ..., |DB|) having 2J components each, our aim is to retrieve in the featurebase the most similar feature vectors to Q. To achieve this, Q and the |DB| feature vectors are Daubechies-8 wavelets decomposed, compressed to m coefficients each and quantized. Then, to measure the similarity degree between Q and a target feature vector Tk of the featurebase, we use the one-dimensional version of the pseudo-metric used in [Ksantini et al., 2006] and given by the following expression

where

˜Q[0] and ˜ Tk[0] are the scaling factors of Q and Tk, ˜Qcq [i] and ˜ T c kq [i] represent the i-th coefficients of their Daubechies8 wavelets decomposed, compressed to m coefficients and quantized versions, ˜w0 and the wbin(i)'s are the weights to compute, and the bucketing function bin() groups these latters according to the J resolution levels, such as

3 The weight computation

In order to improve the discriminatory power of the pseudometric, we compute its weights ˜w0 and {wk}J-1 k=0 using a classical logistic regression model and a Bayesian logistic regression model, separately. We define two classes, the relevance class denoted by Ω0 and the irrelevance class denoted by Ω1, in order to classify the feature vector pairs as similar or dissimilar. The basic principle of using the Bayesian logistic regression model and the classical logistic regression one is to allow a good linear separation between Ω0 and Ω1, and then to compute the weights which represent the local relevances of the pseudo-metric components.

3.1 The classical logistic regression model

In this model, each feature vector pair is represented by an explanatory vector and a binary target variable. Specifically, for the i-th feature vector pair, we associate an explanatory vector Xi = ( ˜X0,i, X0,i, ..., XJ-1,i, 1) ∈ RJ ×{1} and a binary target Si which is either 0 or 1, depending on whether or not the two feature vectors are intended to be similar. ˜X0,i is the absolute value of the difference between the scaling factors of the Daubechies-8 wavelets decomposed, compressed and quantized versions of the two feature vectors and {Xk,i}J-1 k=0 are the numbers of mismatches between the J resolution level coefficients of these latter. We suppose that we have n0 pairs of similar feature vectors and n1 pairs of dissimilar ones. Thus, the class Ω0 contains n0 explanatory vectors and their associated binary target variables {X r i , Sr i = 0}n0 i=1 to represent the pairs of the similar feature vectors, and the class Ω1 contains n1 explanatory vectors and their associated binary target variables {X ir j , Sir j = 1}n1 j=1 to represent the pairs of the dissimilar feature vectors. The pseudo-metric weights ˜w0 and {wk}J-1 k=0 and an intercept v are chosen to optimize the following conditional log-likelihood.

where pri and pir j are the relevance and irrelevance probabilities, respectively, and given by

where F(x) = ex 1+ex is the logistic function. For this reason, standard optimization algorithms such as Fisher scoring and gradient ascent algorithms [Clogg et al., 1991], can be invoked. However, in several cases, especially because of the exponential in the likelihood function or because of the existence of many zero explanatory vectors, the maximum likelihood can fail and estimates of the parameters of interest (weights and intercept) may not be optimal or may not exist or may be on the boundary of the parameter space. Also, as there is complete or quasicomplete separation between Ω0 and Ω1, the function L is made arbitrarily large and standard optimization algorithms diverge [Krishnapuramet al., 2005]. Moreover, as Ω0 and Ω1 are large and high-dimensional, these standard optimization algorithms have high computational complexity and take long time to converge. The first two problems can be solved by smoothing the parameter of interest estimates, assuming a certain prior distribution for the parameters, thereby reducing the parameter space, and the third problem can be solved by using variational transformations which simplify the computation of the parameter of interest estimates [Jaakkola and Jordan, 2000]. This motivates the adoption of a Bayesian logistic regression model based on variational methods.

3.2 The Bayesian logistic regression model

In the Bayesian logistic regression framework, there are three main components which are a chosen prior distribution over the parameters of interest, the likelihood function and the posterior distribution. These three components are formally combined by Bayes' rule. The posterior distribution contains all the available knowledge about the parameters of interest in the model. Among many priors having different distributional forms, gaussian prior has the advantage of having low computational intensity and of smoothing the parameter estimates toward a fixed mean and away from unreasonable extremes. However, when the likelihood function is not conjugate of the gaussian prior, the posterior distribution has no tractable form and its mean computation involves high-dimensional integration which has high computational cost. According to [Jaakkola and Jordan, 2000], it's possible to use accurate variational transformations in order to approximate the likelihood function with a simpler tractable exponential form. In this case, thanks to the conjugacy, with a gaussian prior distribution over the parameters of interest combined with the likelihood approximation, we obtain a closed gaussian form approximation to the posterior distribution. However, as the number of observations is large, the number of variational parameters updated to optimize the posterior distribution approximation is also large, thereby the computational cost is high. In the Bayesian logistic regression model that we propose, we use variational transformations and the Jensen's inequality in order to approximate the likelihood function with tractable exponential form. The explanatory vectors are not observed but instead are distributed according to two specific distributions. The posterior distribution is also approximated with a gaussian which depends only on two variational parameters. The computation of the posterior distribution approximation mean is fast and has low computational complexity. In this model, we denote the random vectors whose realizations represent the explanatory vectors {X r i }n0 i=1 of the relevance class Ω0 and the explanatory vectors {X ir j }n1 j=1 of the irrelevance class Ω1, by X0 = ( ˜X0,0 , X0,0 , ..., XJ-1,0 , 1) and X1 = ( ˜X0,1 , X0,1 , ..., XJ-1,1 , 1), respectively. We suppose that X0 ∼ q0(X0 ) and X1 ∼ q1(X1 ), where q0 and q1 are two chosen distributions. For X0 we associate a binary random variable S0 whose realizations are the target variables {S r i = 0}n0 i=1, and for X1 we associate a binary random variable S1 whose realizations are the target variables {S ir j = 1}n1 j=1 . We set S0 equal to 0 for similarity and we set S1 equal to 1 for dissimilarity. Parameters of interest (weights and intercept) are considered as random variables and are denoted by the random vector W = ( ˜ w0 , w0 , ..., wJ-1 , v). We assume that W ∼ π(W), where π is a gaussian prior with prior mean μ and covariance matrix Σ. Using Bayes' rule, the posterior distribution over W is given by

where P(Si = i|Xi = xi,W) = F ((2i - 1)Wtxi) for each i ∈ {0, 1}. Using a variational approximation [Jaakkola and Jordan, 2000] and the Jensen's inequality, the posterior distribution is approximated as follows

where Eq0 and Eq1 are the expectations with respect to the distributions q0 and q1, respectively, ϕ(ϵi) = tanh( ϵi 2 ) 4ϵi and {ϵi}1i=0 are the variational parameters. Therefore, the approximation of the posterior distribution is considered as an adjustable lower bound and as a proper Gaussian distribution with a posterior mean μpost and covariance matrix Σpost which are estimated by the following Bayesian update equations

The weight and intercept computation algorithm is in two phases. The first phase is the initialization of q0, q1 and the gaussian prior π(W), and the second phase is iterative and allows the computation of Σpost and μpost through the Bayesian update equations (5) and (6), respectively, while using an EM type algorithm [Jaakkola and Jordan, 2000], in order to find the variational parameters {ϵi}1i=0 at each iteration to have an optimal approximation to the posterior distribution. In the initialization phase, q0 and q1 are chosen to model Ω0 and Ω1, respectively, and because of the absence of prior knowledge about the weights and the intercept, π(W) is chosen univariate with zero mean and large variances [Congdon, 2001]. The values of μpost components are the desired estimates of the pseudo-metric weights ˜w0 and {wk}J-1 k=0 and the intercept v. Once the parameters of the posterior distribution approximation are computed, its magnitude is given by the term ∏1i=0 F(ϵi). This latter becomes very close to 1 as Ω0 and Ω1 are linearly separated or quasi separated and tends towards 0 as Ω0 and Ω1 become more and more overlapped. Analogically, in the classical logistic regression model, the term e2L has almost the same characteristics as ∏1i=0 F(ϵi) [Caenen and Pauwels, 2002]. These two terms will be used to perform feature selection in the retrieval method.

3.3 Training

Let us consider a color image database which consists of several color image sets such that each set contains color images which are perceptually close to each other in terms of object shapes and colors. In order to compute the pseudo-metric weights and the intercept by the classical logistic regression model, we have to create the relevance class Ω0 and the irrelevance class Ω1. To create Ω0, we draw all possible pairs of feature vectors representing color images belonging to the same database color image sets, and for each pair we compute an explanatory vector and we associate to this latter a binary target variable equal to 0. Similarly, to create Ω1, we draw all possible pairs of feature vectors representing color images belonging to different database color image sets, and for each pair we compute an explanatory vector and we associate to this latter a binary target variable equal to 1. For the Bayesian logistic regression model, we create the Ω0 and Ω1 with the same way, but instead of associating a binary target variable value to each explanatory vector of Ω0 and Ω1, we associate a binary target variable S0 equal to 0 to all Ω0 explanatory vectors and we associate a binary target variable S1 equal to 1 to all Ω1 explanatory vectors.

4 Color image retrieval method

The querying method is in two phases. The first phase is a preprocessing phase done once for the entire database containing |DB| color images. The second phase is the querying phase.

4.1 Color image database preprocessing

We detail the preprocessing phase done once for all the database color images before the querying in a general case by the following steps.

1. Choose N feature vectors for comparison.
2. Compute the N feature vectors Tli (l ∈ {1, ...,N}) for each i-th color image of the database, where i ∈ {1, ..., |DB|}.
3. The feature vectors representing the database color images are Daubechies-8 wavelets decomposed, compressed to m coefficients each and quantized.
4. Organize the decomposed, compressed and quantized feature vectors into search arrays Θl+ and Θl- (l = 1, ...,N ) which are used to optimize the pseud-metric computation process [Ksantini et al., 2006].
5. Adjustment of the metric weights ˜wl0 and {wlk }J-1 k=0 for each featurebase Tli (i = 1, ..., |DB|) representing the database color images, where l ∈ {1, ..., N}.

4.2 The querying algorithm

We detail the querying algorithm in a general case by the following steps.

1. Given a query color image, we denote the feature vectors representing the query image by Ql (l = 1, ..., N ).
2. The feature vectors representing the query image are Daubechies-8 wavelets decomposed, compressed to m coefficients each and quantized.
3. The similarity degrees between Ql (l = 1, ...,N ) and the database color image feature vectors Tli (l = 1, ..., N ) (i = 1, ..., |DB|) are represented by the arrays Scorel (l = 1, ...,N ) such that Scorel[i] =‖ Ql, Tli ‖ for each i ∈ {1, ..., |DB|}. These arrays are returned by the procedure Retrieval(Ql, m, Θl+, Θl-) (l = 1, ..., N ), respectively. The procedure Retrieval is used to optimize the querying process [Ksantini et al., 2006].
4. The similarity degrees between the query color image and the database color images are represented by a resulted array TotalScore, such as, TotalScore[i] = ∑Nl=1 γlScorel[i] for each i ∈ {1, ..., |DB|}, where {γl}Nl=1 are weightfactors used to down-weight the feature which has low discriminatory power. γl = e2Ll when the weights are computed by the classical logistic regression model, and γl = ∏1i=0 F(ϵli ) when the weights are computed by the Bayesian logistic regression model.
5. Organize the database color images in order of increasing resulted similarity degrees of the array TotalScore. The most negative resulted similarity degrees correspond to the closest target images to the query image. Finally, return to the user the closest target color images to the query color image and whose number is denoted by RI and chosen by the user.

4.3 Used feature vectors

In order to describe the luminance, colors and the edges of a color image, we use luminance histogram and weighted histograms. The image texture description is performed by kurtosis and skewness histograms. Given an M × N pixel LAB color image, its luminance histogram hL contains the number of pixels of the luminance L, and can be written as follows

for each c ∈ {0, ..., 255}, where IL is the luminance image and δ is the Kronecker symbol at 0. The weighted histograms are the color histogram constructed after edge region elimination and the multispectral gradient module mean histogram. The former is given by

and the latter is given by

where Np,k(c) is the number of the edge region pixels and is defined as

and

for each c ∈ {0, ..., 255} and k = a, b, where λmax represents the multispectral gradient module [Ksantini et al., 2006], η is a threshold defined by the mean of the multispectral gradient modules computed over all image pixels, Ia and Ib are the images of the chrominances a red/green and b yellow/blue, respectively, and χ is the characteristic function. The multispectral gradient module mean histogram provides information about the overall contrast in the chrominance and the edge region elimination allows the avoidance of overlappings or noises between the color histogram populations caused by the edge pixels. The LAB color image kurtosis and skewness histograms are given by

and

respectively, for each c ∈ {0, ..., 255} and k = L, a, b, where I κ L, I κ a and I κ b are the kurtosis images of the luminance L and the chrominances a and b, respectively, and I sL, I s a and I s b are the skewness images of these latter. They are obtained by local computations of the kurtosis and skewness values at the luminance and chrominance image pixels. Then, a linear interpolation is used to represent the kurtosis and skewness values between 0 and 255. Since each used feature vector is a histogram having 256 components, we set J equal to 8 in the following section.

5 Experimental results

In this section, we will discuss the choices of the distributions q0 and q1, in order to validate the Bayesian logistic regression model in the image retrieval context. Finally, we will use the precision and scope as defined in [Kherfi and Ziou, 2006], to evaluate the querying method using both models separately. The choices of the distributions q0 and q1 and the querying evaluation will be conducted on the WANG and Zubud color image databases proposed by [Deselaers et al., 2004]. The WANG database contains |DB| = 1000 color images which were selected manually to form 10 sets (e.g. Africa, beach, ruins, food) of 100 images each. The Zurich Building Image Database (ZuBuD) contains a training part of |DB| = 1005 color images and query part of 115 color images. The training part consists of 201 building image sets, where each set contains 5 color images of the same building taken from different positions. Before the feature vector extractions, we represent the WANG and Zubud database color images in the perceptually uniform LAB color space. Since from each color image of the Zubud and WANG databases we extract N = 11 histograms which are given by (7), (8), (9), (12) and (13) respectively, each database is represented by eleven featurebases. The choices of q0 and q1 will be separately performed for each featurebase. For each featurebase, we assume that ˜X0,0 and (X0,0 , ...,XJ-1,0 ) are independent. We make the same assumption for ˜X0,1 and (X0,1 , ...,XJ-1,1 ). Moreover, we suppose that the random vector (X0,0, ...,XJ-1,0) random variables whose realizations are positive integers, are independent and each one of them follows a truncated poisson distribution at its greatest realization, to have a best fit. Analogically, we make the same choice for (X0,1, ..., XJ-1,1). Also, we assume that the random variable ˜X0,0 whose realizations are positive reals, follows a gaussian mixture distribution, which is the same choice for ˜X0,1 . Generally, to carry out an evaluation in the image retrieval field, two principal issues are required: the acquisition of ground truth and the definition of performance criteria. For ground truth, we use human observations. In fact, three external persons participate in the below evaluation. Concerning performance criteria, we represent the evaluation results by the precision-scope curve Pr = f (RI ), where the scope RI is the number of images returned to the user. In each querying performed in the evaluation experiment, each human subject is asked to give a goodness score to each retrieved image. The goodness score is 2 if the retrieved image is almost similar to the query, 1 if the retrieved image is fairly similar to the query and 0 if there is no similarity between the retrieved image and the query. The precision is computed as follows: Pr = the sum of goodness scores for retrieved images/RI. Therefore, the curve Pr = f (RI ) gives the precision for different values of RI which lie between 1 and 20 when we perform the querying evaluation on the WANG database, and lie between 1 and 5 when we perform the querying evaluation on the ZuBuD database. When the human subjects perform different queryings in the evaluation experiment, we compute an average precision for each value of RI, and then we construct the precision-scope curve. In our evaluation experiment, each color image of the WANG and Zubud databases is represented by N = 11 histograms which are hL, hha , hhb , ¯hea , ¯heb , hκL, hκa , hκb , hsL, hsa and hsb . In order to evaluate the querying in the WANG database, each human subject is asked to formulate a query from the database and to execute a querying, using weights computed by the classical logistic regression model, and to give a goodness score to each retrieved image, then to reformulate a query from the database and to execute the querying, using weights computed by the Bayesian logistic regression model, and to give a goodness score to each retrieved image. Each human subject performs the querying fifty times by choosing a new query from the database each time. We repeat this experience for different orders of compression m ∈ {30, 20, 10}. To evaluate the querying in the ZuBuD database, each human subject is asked to follow the preceding steps, while formulating the queries from the database query part. For the WANG and Zubud databases, the resulted precision-scope curves are given in Figure 1 for compression orders m ∈ {30, 20, 10}. The Figure 2 illustrates two retrieval examples in the Zubud database comparing the performances of the regression models for m = 30. In each example the query is located at the top-left of the dialog box.

(a)

6 Conclusion

We presented a simple, fast and effective color image querying method based on feature selection. In order to measure the similarity degree between two color images both quickly and effectively, we used a weighted pseudo-metric which makes use of the one-dimensional Daubechies decomposition and compression of the extracted feature vectors. A Bayesian logistic regression model and a classical logistic regression one were used to improve the discriminatory capacity of the pseudo-metric and to allow feature selection. Evaluations of the querying method showed that the Bayesian logistic regression model is a better tool than the classical logistic regression one to compute the pseudo-metric weights and to improve the querying results.