Content based image retrieval using multiple features and pareto approach

Journal of Computer Science and Cybernetics, V.32, N.2 (2016), 169–187 DOI no. 10.15625/1813-9663/32/2/8611 CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES AND PARETO APPROACH VAN-HIEU VU1, TRUONG-THANG NGUYEN2, HUU-QUYNH NGUYEN3, QUOC-TAO NGO2 1Information Technology Faculty, Haiphong University, Haiphong, Vietnam 2Institute of Information Technology, Vietnam Academy of Science and Technology 3Information Technology Faculty, Electric Power University, Hanoi, Vietnam 1hieuvv@dhhp.edu.vn; 2{ntthang, nqtao}@ioit.ac.vn; 3quynhnh@epu.edu.vn Abstract. There are two commonly used aggregation based approaches in Content Based Image Retrieval (CBIR) systems using multiple features (e.g., color, shape, texture). In the first approach, the systems usually represent each image as a unified feature vector by concatenating component feature vectors and then for a query image, compute its distance measure with images in the database. Inspite of the simplicity, this approach does not emphasize the importance of each component feature. Another approach often computes the weighted linear combination of individual distance measures and the weight assignment to each is based on Relevance Feedback (RF) from a user to determine the importance of each component. In this paper, the authors propose to use Pareto approach for candidate selection. The proposed algorithm produces a compact set of candidate images when comparing with the entire dataset and this set also contains results obtained from all aggregation operator [3]. The authors also formalize main properties of Pareto front with respect to CBIR which are mainly used to propose our two algorithms. The experiments on three image collections show that our proposed approach is very effective to improve the performance of the classification engines. Keywords. Pareto point, Pareto front, content based image retrieval (CBIR), relevance feedback (RF), classification. 1. INTRODUCTION The appearance of Internet completely changes the way we look for information. For example, when working with text, simply by typing keywords in the search engines such as Google or Bing, we can immediately get the list of most relevant websites in (generally) acceptable quality. Such an equivalent system for images, i.e. taking the image input from a user, tries to find the most similar images in its image dataset, then give them back to the user. Ideally, the similarity here is defined based on the similarity of the human concepts that images represent. Those systems are called Content Based Image Retrieval, or CBIR for short. A typical CBIR system acts as follows. First, it does feature extraction, i.e. how to associate each image with a quantitative vector. This quantitative vector is called the feature vector of this image. Features of all images in the database are calculated. Then, for a input image (often called as query image), the system computes its distance measure of features c© 2016 Vietnam Academy of Science & Technology 170 VAN HIEU, TRUONG THANG, HUU QUYNH, QUOC TAO vector with images in the database. Finally, the closest images having smallest distance measure are returned to the user. Note that the distance measure is also to be defined. Such well-known CBIR systems are given in [28, 14, 30]. CBIR systems usually represent feature of images in color, texture, shape and description layout. The combination of color, texture and shape is proposed in [25]. On the other hand, MARS [27] use components color moment, Tamura texture and co-occurrence matrices of features. Furthermore, color edge detection and discrete wavelet transform are used to represent feature in [1]. As such we see a clear trend in many CBIR systems for utilizing the combination of multiple features to retrieve images. Intuitively, the user does not easily recognize images based on low-level aspects such as color and shape. Another issue is related to the subjective perception of images, i.e. different people may have different visual perception with the same image. Different images may have different meaning or different importance level to each person. For example, given an image showing a flying bird in the sky, some people may be interested in the bird, while others may be interested in the sky. Assuming that each feature is associated with a distance measure, each image then has multiple distances with regards to a query image in the multiple dimension search space. Given a query image, according to each feature of the image, we can find some neighboring images. If considering the problem in the multi-dimension space, the candidates are often the subset of the union of previous neighboring images associated with each dimension. The ranking function is used to order the relevance among those candidates. It has to compute the aggregated distance measure for each candidate based on some pre-defined possibly weighted linear combination of individual distance measures. In the simplest case, if all candidates are ordered in the same sequence along all dimensions, the ranking function is simple as in the aggregated form, the same order is preserved [8]. However, in practice, it is often the case that an image is ranked higher compared with another candidate in one dimension but lower than that of the same counterpart in another dimension. Because we have no idea about the importance level of a particular feature, the approach often uses the weighted linear combination of individual distance measure. The weight assignment to each dimension is quite subjective. Many studies [10, 6, 5] use preference based on values of distance measure. Those researches do not use linear combination of individual distance measure to get the best candidates in their point of view (not user’s point of view). The candidate selection is based on the Pareto point [34]. A detailed example is considered as follows: Example 1. Given the query image Q and three images o1, o2, o3. The distance of the query image Q with three images in features of color and texture is shown in Table 1. Table 1: The distance between Q and o1, o2, o3 in Color and Texture features Image Color (C) Texture (T) Sum o1 0.6 0.3 0.9 o2 0.5 0.2 0.7 o3 0.45 0.35 0.8 It can easily rank the order of images o2, o3, o1 based on total distance measure. When CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES 171 not combining linear distance measure, the ranking based on individual distance measure can only deal with o1 and o2. The object o3 can not be compared with others. Besides, the ranking function is quite subjective and rather fixed with regards to weight assignment to each dimension. This way can leave out images which are more similar with the query image (i.e. their semantic may be similar with user’s image desire) in some particular dimension but their global distance is higher. Hence, to fit user’s utility function, some interactive relevance feedback with the user is essential so that we can catch more accurately his perception. The relevance feedback techniques based query refinement into three categories: query re- weighting, query point movement and query expansion. Both query re-weighting and query point movement methods use nearest neighbors. They return top ranked images for user judgement and then refine results based on user’s feedback. Intuitively, this approach suits user’s subjective perception. The limitation of those methods lies in convergence difficulty when the relevant points scatter in visual space. The query expansion method manages to overcome the issue by using multi-point query and then merges all results. However, this method can leave out images with overall high distances in all imaging dimensions but those images are semantically similar with user’s information need. The classification techniques have significantly increased performance for the CBIR sys- tems such as SVM, boosting, classification regression and tree methods etc,. Existing meth- ods are less efficient in classifying data which has not been trained and contains noises. In this paper, a Pareto-based CBIR method is proprosed. Instead of finding a query center for the selected relevant images or only applying SVM method, our algorithm PDFA delivers a set of the compact candidate images. Further, the method produces less noisy data and improves the performance of classification engine. The paper is organized as follows. Section 2 surveys related works using the Pareto method and some state-of-the-art relevance feedback techniques in CBIR. In Section 3, the propositions of the Pareto-based CBIR method which is used to minimize the search space are formalized. Section 4 shows the main experiment. Finally, the conclusion and future work are given in Section 5. 2. RELATED WORK 2.1. The Pareto approaches The Pareto approach can be found in many works related to database [22, 4], or networking [5]. Ortega et al [20] proposes a technique using the Pareto optimality to perform a pre- filtering process for eliminating less representative objects from the k-neighbours selection process while retaining the most promising ones. This work gets results of a query include all the Pareto points. The Pareto set covers space associated objects with query more than the method using combined distance measure. Arevalillo-Herr et al [2] evaluate different ways to combine two existing relevance feedback methods that place unequal emphasis on exploration and exploitation in the context of distance-based methods. Hsiao et al.,[12] proposed a multiple queries information retrieval algorithm that combines the Pareto front with efficient manifold ranking (EMR) [37]. In this paper, the learning process of the feature database (SIFT, Histogram of Oriented Gradients) is done in advance 172 VAN HIEU, TRUONG THANG, HUU QUYNH, QUOC TAO by EMR algorithm. For each query, EMR is used to produce a list of ranked results based on similarity measure. Then, the Pareto front is constructed based on these lists. However, our proposed method does not adopt pre-learning process as presented in this paper, hence it is not used in our comparisons. Advantages of the Pareto approach have not been widely researched in CBIR systems. Due to its characteristics, Pareto method can compact the candidate set, i.e. search space. Hence it potentially improves performance of CBIR systems. We propose to use the Pareto approach, particularly getting the union Pareto fronts at different depths. In addition, relevance feedback technique plays important role to comprehend user’s perception. By interacting with user, relevance feedback provides more information so that we can deduce more accurately about user preference among multiple features, i.e. which feature is more important than others in his perception. This interaction process between the system and the user helps to select relevant points while the Pareto-based method gets all Pareto fronts of those points at different depths. Therefore, the proposed method reduces much search space and covers most relevant images. 2.2. Relevance feedback in CBIR To improve performance of CBIR systems, relevance feedback (RF) techniques are ap- plied for filling the semantic gap between low-level features and high-level concepts in image descriptions by human computer interaction. The query point movement has been applied to CBIR systems such as MARS [26] and MindReader [14]. Those systems represent the query as a single point in the feature space and try to move this point toward relevant result points, as well as to move it away from irrelevant result points. This idea originated from the Rochio’s formula [24]. In this approach, the weighting technique assigns a coefficient to each dimension of query point. It associates high weights with more important dimensions and vice versa. MARS uses a weighted Euclidean distance, which handles ellipsoids whose major axis is aligned with the coordinate axis. MindReader uses a generalized Euclidean distance which permits the rotation of axis so that it works well for arbitrarily oriented ellipsoids. This approach requires many examples to calculated the covariance matrix. Other query refinement methods using the relevant multi-point were introduced. The query expansion approach in MARS [23] constructs local cluster for relevant points. In this approach, all local clusters are merged to form a single large contour that cover all query points. On the other hand, query point movement approach ignores these clusters and treats all relevant points equivalently [27, 14]. These two approaches can generate a single hyper- ellipsoid or convex shapes using local clusters in some feature space to cover all query points for simple queries. However, both approaches fail to identify appropriate regions for complex queries. FALCON [36] uses an aggregate distance function to estimate the (dis)smilarity of an object to a set of desirable images, to facilitate learning disjunctive and concave query points in the vector space as well as in arbitrary metric space. In general, MARS [28] and Mindreader [14] or FALCON [36] require a good “starting query” to work well and need several refinement step are usually needed before weights converge to the “right” values. In general, the above approaches do not guarantee to find desirable images and sometime they may be properly seeded, bootstrapped or beg the question when they do not found any new relevant images or few relevant images. To address the aforementioned limitations, we explorer multiple features in CBIR system based on the Pareto method. CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES 173 To improve retrieval performance, some effective machine learning techniques are used for sample classification [33, 39, 35]. SVM-AL [33] is an early research and make some contribution to CBIR community. In general, the classification techniques by SVM usually require certain classes known and large data set is labeled. SVM techniques are less effective in CBIR systems using RF because causes: the sample is not labeled before and the number of relevant images in a feedback round may be less or in the worst case have not relevant images. The AdaBoost technique [9, 32, 38, 15] considers meaning to boosting for weak learning algorithm, data is reweighted before running weak learning algorithm at step loops. In [32] was used AdaBoost algorithm in CBIR and used relevance feedback to learning user’s infor- mation in both negative and positive images. However, the techniques based on AdaBoost are usually slow classifiers and need many feedback loops. For efficient improvement of relevance feedback in CBIR, many machine learning tech- niques are less interested in minimizing the search space, making less density of data samples or reducing noise of data. Indeed, most of them only consider attributes (dimension) reduc- tion. We suggest to use the Pareto approach for reducing noise of data. This proposal will be presented in the next section. 3. THE PROPOSED METHOD 3.1. The Pareto approach in search space of CBIR system and formal properties of the Pareto front First, it is needed to formalize the problem as follows: Suppose {ETi ||i = 1,M} is a feature database of M images, which gets from feature extraction each image includes color, texture and shape, then it is represented by a tuple of T features, i.e. I = (I1, ..., It, ..., IT ). The queryQ is processed the same way as the images of the database, i.e., Q = (Q1, ..., Qt, ..., QT ). The distance measure corresponding with tuple of T features between Q and each I is defined by (D1Q(I), ..., D t Q(I), ..., D T Q(I)), (1) where DtQ(I) = D(Q t, It) is corresponding distance of tth feature. The search space of particular query Q which is given by: EQ = {(I,D1Q(I), ..., DtQ(I), ..., DTQ(I))/I ∈ E}, (2) There exists a map piQ, that is bijective in the search space EQ, i.e., piQ : EQ → E (I,D1Q(I), ..., D t Q(I), ..., D T Q(I)) 7→ I (3) For simplicity, when Q is fixed we put I ≡ piQ(I) ∈ E and A ≡ {piQ(I)/∀I ∈ A} ⊂ E, ∀I ∈ EQ, ∀A ⊂ EQ. Multi-objective approaches require all the objectives are simultaneously optimized (min- imum) for each criteria DtQ(I) in a solution (D 1 Q(I), D 2 Q(I), ..., D t Q(I), ..., D T Q(I)). The multi- objective problem in the search space is defined as follows:{ min DtQ(I), ∀t = 1, T s.t. I ∈ E , (4) 174 VAN HIEU, TRUONG THANG, HUU QUYNH, QUOC TAO Indeed, an ideal point Iideal simultaneously optimizing all criteria usually does not exist. The solutions of this problem turns out to find the set of tradeoff solutions that offer different compromises among criteria. A solution (D1Q(I), D 2 Q(I), ..., D t Q(I), ..., D T Q(I)) is optimal if there is no other solution in the search space that achieves distance smaller than it on every criterion DtQ(I). This implies that if we want to know which points belong to the extracted Pareto front. We should evaluate the complete set of distances for every point in the search space. Also some definitions and formal properties of the Pareto front in the search space are proposed. These definitions and formal properties are basic to form two algorithms for propose system. Definition 1. (Pareto dominance) Let I1 and I2 be two points of the search space EQ, I2 is Pareto dominated by I1 (noted I1 ≺Q I2) iff{ ∀t = 1, T ,DtQ(I1) ≤ DtQ(I2), ∃t0 ∈ [1, T ] : Dt0Q (I1) < Dt0Q (I2), (5) According to this definition, it is clear that all points I1 and I2 in the search space EQ, satisfying property I1 ≺Q I2, thus I1 is more relevant than I2 with respect to Q. Example 2. In example 1, o2 ≺Q o1 because 0.5 < 0.6 and 0.2 < 0.3. Proposition 1. Given I1, I2 and I3 in EQ. We have: (1.1) I1 ≺Q I2 ⇒ I2 ⊀Q I1. (1.2) I1 ≺Q I2, I2 ≺Q I3 ⇒ I1 ≺Q I3. (1.3) I1 ≺Q I2 ⇒ Agg(D1Q(I1), ..., DTQ(I1)) < Agg(D1Q(I2), ..., DTQ(I2)) , where Agg is an aggregation operator. Proof. (1.1) I1≺QI2 ⇒ ∃t0 ∈ [1, T ] : Dt0Q (I2) < Dt0Q (I1)⇒ I2 6≺QI1 (1.2) I1≺QI2 ⇒ (DtQ(I1) ≤ DtQ(I2), ∀t = 1, T )∧(∃t0 ∈ [1, T ] : Dt0Q (I1) < Dt0Q (I2)). I2≺QI3 ⇒ (DtQ(I2) ≤ DtQ(I3), ∀t = 1, T ) ∧ (∃t0 ∈ [1, T ] : Dt0Q (I2) < Dt0Q (I3)). Therefore (DtQ(I1) ≤ DtQ(I3),∀t = 1, T ) ∧ (Dt0Q (I1) < Dt0Q (I3))⇒ I1≺QI3. (1.3) By definition aggregation operation (see definition 1.5 in [3]), if I1 ≺Q I2 ⇒ Agg(D1Q(I1) ,..., DTQ(I1)) < Agg(D 1 Q(I2) ,..., D T Q(I2)).  Definition 2. (Pareto front) Given A ⊂ EQ, the Pareto front of A (noted PFQ(A)) is defined as: PFQ(A) def = {I ∈ A/@I ′ ∈ A : I ′ ≺Q I} ⊂ A, (6) The Pareto front or the Pareto set is the set containing all points can not compare with each other. Example 3. (3.1) From example 1, PFQ(EQ) = {o2, o3}, because they are not dominated by any point. (3.2) A ⊂ EQ, (DtQ(I1) = DtQ(I2),∀t = 1, T ), ∀I1, I2 ∈ A⇒ PFQ(A) ≡ A. CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES 175 Proposition 2. (2.1) ∀I ∈ EQ if ∃t0 ∈ [1, T ], Dt0Q (I) < Dt0Q (I ′),∀I ′ 6= I, I ∈ PFQ(EQ). (2.2) ∀A ⊂ EQ, w1, w2, ..., wT ∈ (0, 1), T∑ t=1 wt = 1, if I0 = arg min I∈A T∑ t=1 wtD t Q(I) then I0 ∈ PFQ(A). (2.3) ∀A ⊂ EQ, A 6= ∅ ⇒ PFQ(A) 6= ∅. (2.4) ∀A ⊂ EQ,∀I ∈ A\PFQ(A)⇒ ∃J ∈ PFQ(A) : J≺QI. Proof. (2.1) We prove by contradiction. Let I /∈ PFQ(EQ) ⇒ ∃I ′ ∈ EQ, DtQ(I ′) < DtQ(I) ⇒ Dt0Q (I ′) < Dt0Q (I) it is a contradiction, because D t0 Q (I) = minI′∈EQ Dt0Q (I ′). (2.2) Agg : [0, 1]T → [0, 1] (d1, d2, ..., dT ) 7→ T∑ t=1 wtdt. This is an aggregation operator, thus if I0 /∈ PFQ(A), ∃I ∈ A, I 6= I0, I≺QI0 ⇒ Agg(I) < Agg(I0) it is a contradiction, because I0 = arg min I∈A Agg(I), so that I0 ∈ PFQ(A). (2.3) Put I0 = arg min I∈A T∑ t=1 1 TD t Q(I) ⇒ I0 ∈ PFQ(A) ⇒ PFQ(A) 6= ∅. This result is a condi- tion on (2.2). (2.4)NI = {k ∈ N+/∃{I1, I2, ..., Ik} ⊂ A, Ik≺QIk−1≺Q...≺QI0 = I, Ik−1 /∈ A}, therefore I0 ∈ A\PFQ(A) ⇒ ∃I1 ∈ A : I1≺QI0 ⇒ 1 ∈ NI ⇒ NI 6= ∅, NI ⊂ {1, 2, ...,#A} ⇒ ∃k0 = maxNI . If Ik0 /∈ PFQ(A) then Ik0 ∈ A ∧ Ik0 /∈ PFQ(A) = {I ∈ A/@I ′ ∈ A ∧ I ′≺QI} ⇒ ∃I ′ ∈ A ∧ I ′≺QIk0 ⇒ {I1, I2, ..., Ik0 , I′} ⊂ A, I′≺QIk0≺QIk0−1≺Q...≺QI1 = I0 ⇒ k0 + 1 ∈ NI . This is a contradiction, because k0 = maxNI . Put J = Ik0 ∈ PFQ(A), J ≺Q I (by (1.3)).  Example 4. In example 1, DTextureQ (o2) = 0.2 = min { DTextureQ (o1), D Texture Q (o3) } ⇒ o2 ∈ PFQ(EQ). Definition 3. (Pareto depth) 3.1. The lth Pareto depth is defined as: (i) PFD0Q = ∅, (ii) PFDlQ def = PFQ(EQ\ ∪l−1j=1 PFDjQ). 3.2. Depth value: ∀I ∈ EQ, depthQ(I) def= l ∈ N+ ∧ l ≤ #EQ : I ∈ PFDlQ. Remark. PFD1Q = PFQ(EQ). Example 5. In example 1: PFD1Q = PFQ(EQ) = {o2, o2} . PFD2Q = PFQ(EQ \ PFD1Q) = PFQ(EQ \ {o2, o3}) = PFQ({o1}) = {o1}. Example 6. In example 1, EQ = {o1, o2, o3}, o2 ≺Q o1 ⇒ PFD2Q = {o1}. If EQ = {I1, I2, ..., Ik} , I1≺QI2≺QI3≺Q...≺QIk then which mean that PFDlQ = {Il}, ∀l = 1, k. There are some other important properties of the Pareto front according to different depths which are described as follows: 176 VAN HIEU, TRUONG THANG, HUU QUYNH, QUOC TAO Proposition 3. (3.1) ∀l 6= k, PFDlQ ∩ PFDkQ = ∅. (3.2) ∃l ∈ N+, l ≤ #EQ : PFDkQ = ∅ ∀k > l and l⋃ j=1 PFDjQ = EQ. (3.3) l ≥ 1, ∀I1, I2 ∈ PFDlQ ⇒ I1 6≺QI2 ∧ I2 6≺QI1. (3.4) If ∀I ∈ PFDl+1Q , l ≥ 1 then there exists J ∈ PFDlQ : J≺QI. (3.5) The definition 3.2 is valid. If I ∈ EQ then there exists a unique l, 1 ≤ l ≤ #EQ such that I ∈ PFDlQ. (3.6) I1≺QI2 ⇒ depthQ(I1) < depthQ(I2). (3.7) ∀I ∈ EQ, depthQ(I) = k ⇒ ∃I1, ..., Ik ∈ EQ : I1≺QI2≺Q...≺QIk−1≺QIk = I. (3.8) ∀I ∈ EQ, depthQ(I) = max{p ∈ /∃I1, ..., Ip ∈ EQ : I1≺Q...≺QIp = I}. Proof. (3.1) Assuming l > k, PFDlQ = PFQ(EQ\ l−1⋃ j=1 PFDjQ) ⊂ (EQ\ l−1⋃ j=1 PFDjQ) = (EQ\(PFDkQ ∪ ⋃ 1≤j≤l−1,j 6=k PFDjQ)) ⊂ (EQ\PFDkQ), which mean that PFDlQ ∩ PFDkQ = ∅. (3.2) Put M = #EQ, yields M + 1 subsets of EQ : { PFDlQ }M+1 l=1 , ∀1 ≤ l < k ≤ M + 1 meaning PFDlQ ∩ PFDkQ = ∅ (by (3.1)), therefore PFD1Q = PFQ(EQ) 6= ∅, so that ∃l : 1 ≤ l ≤ M ∧ PFDl+1Q = ∅ ∧ PFDlQ 6= ∅, PFDl+1Q = PFQ(EQ \ l⋃ j=1 PFDjQ) = ∅ ⇒ (EQ \ l⋃ j=1 PFDjQ) = ∅, by (2.3) ⇒ l⋃ j=1 PFDjQ = EQ. On the one hand ∀k > l, PFDkQ = PFQ(EQ \ k−1⋃ j=1 PFDjQ) = PFQ(EQ \ EQ) = PFQ(∅) = ∅. (3.3) Put A = EQ \ ∪l−1j=1PFDjQ therefore I1, I2 ∈ PFQ(A) = {I ∈ A/∃I ′ ∈ A : I ′ ≺Q I}, so that I1 6≺QI2 and I2 6≺QI1. (3.4) Put A = (EQ \ ∪l−1j=1PFDjQ) ⇒ PFDlQ = PFQ(A), therefore (EQ \ ∪lj=1PFDjQ) = A∩ (EQ\PFDlQ), I ∈ PFDl+1Q ⇒ (I ∈ A∧ I /∈ PFQ(A)), so that ∃J : J ∈ PFDlQ ∧ J ≺Q I. (3.5) It is to deduce from (3.1) and (3.2). (3.6) Assuming that k = depthQ(I1) ≥ l = depthQ(I2). Put A = (EQ \ ∪l−1j=1PFDjQ) ⇒ I2 ∈ PFDlQ = PFQ(A). On the other hand I1 ∈ PFQ (EQ \∪k−1j=1PFDjQ) ⊂ (EQ \∪k−1j=1PFDjQ) ⊂ (EQ \ l−1⋃ j=1 PFDjQ) = A(k ≥ l). Therefore I2 ∈ PFQ(A) ∧ (I1 ∈ A) ∧ (I1 ≺Q I2), it is a contradiction. (3.7) By proposition (3.6), ∃Ik−1 ∈ PFDk−1Q : Ik−1 ≺Q Ik = I. Applying similar process to Ik−1, ∃Ik−2 ∈ PFDk−2Q : Ik−2 ≺Q Ik−1, ...,∃I1 ∈ PFD1Q : I2 ≺Q I1, so that I1 ≺Q I2... ≺Q Ik−1 ≺Q Ik = I. (3.8) By proposition (3.4) ⇒ depthQ(I) = k ≤ max{p ∈ N+/∃{I1, ..., Ip} ⊂ EQ : I1 ≺Q I2 ≺Q... ≺Q ... ≺Q Ip = I} = p0. On the other hand ∃{I1, ..., Ip0} ⊂ EQ : I1 ≺Q I2 ≺Q .... ≺Q ... ≺Q Ip0 = I . Because of ∀l = 1, p0 − 1 , depthQ(Il) < depthQ(Il+1), so k = depthQ(I) = depthQ(I1) + p0−1∑ l=1 (depthQ(Il+1)− depthQ(Il)) ≥ 1 + p0−1∑ l=1 1 = p0. CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES 177 Conclusion k = p0.  By propositions (3.7) and (3.8), we prove all the points in the search space EQ there always exists a target point by Theorem 1. Theorem 1. (Dominant path) For all point I in the search space EQ, there are always at least depthQ(I)− 1 other points in EQ which is better relevant point I according to low-level visual features. Proof. Put k = depthQ(I) by proposition (3.7) ⇒ ∃I1, ..., Ik ∈ EQ : I1≺QI2≺Q...≺QIk−1≺QIk = I.  According to this theorem, it is clear that all the points in the search space there always exists a dominant path. Theory also is shown to depth of point I in the search space EQ which is longest dominant path start by I. Definition 4. (Pareto Union) Given EA ⊂ E and L is depth of the Pareto front, the Pareto Union of the subset EA (noted PFUL(EA)) is defined as PFUL(EA) def = ⋃ a∈EA,1≤l≤L PFDla, (7) Proposition 4. ∀EA ⊂ E,∀L ∈ N+ : EA ⊂ PFUL(EA). Proof. ∀a ∈ EA, L ∈ N+, a ∈ PFD1a ⊂ ⋃ a∈EA,1≤l≤L PFDla ⇒ EA ⊂ ⋃ a∈EA,1≤l≤L PFDla = PFUL(EA).  Definition 5. (Boundary of Pareto front) Given ∀A ⊂ EQ and  > 0, the boundary of the Pareto front (noted PFBQ,(A)) is defined as PFBQ,(A) = {I ∈ A/∃I0 ∈ PFQ(A) : DtI0(I) < , 1 ≤ t ≤ T}, (8) Proposition 5. PFQ(A) ⊂ PFBQ,(A) ⊂ A Proof. ∀I ∈ PFQ(A), put I0 = I, ⇒ { I0 ∈ PFQ(A) DtI0 = 0 < ,∀t = 1, T ⇒ I = I0 ∈ PFBQ,(A) (by definition 5). ⇒ PFQ(A) ⊂ PFBQ,(A)  3.2. Classification improvement based on the Pareto approach The Pareto set contains all the points which do not dominate each other in the search space EQ. Furthermore, it includes not only points achieving minimum measure by linear combination, but also other points which could be left out under the linear combination of distances. In this section, two algorithms are presented. The first algorithm PFDA gets a set of the Pareto points according to the Pareto front of L different depths. It is implemented based 178 VAN HIEU, TRUONG THANG, HUU QUYNH, QUOC TAO on definitions 2 and 3. A threshold aTupleMax is set up, its dimension has maximum value according to all the Pareto points which are matched. The second algorithm CUPF works on the search space returned from the algorithm PFDA. To expand the Pareto front, the union of all Pareto fronts associated with relevant points is performed. A classification engine is used on this Pareto front data. Algorithm 1 PFDA (Pareto Front Depth Algorithm) Input: {EQt/t = 1, T} . EQt is ranked and contains M points, each point has T dimensions L ; . depth of the Pareto front K ; . The number of points in the Pareto front set Output: PointSet . A set of the Pareto points is sorted according to front’s depth 1: Variables: PF = PF Next = ∅; {aTupleMaxt}Tt=1 = 0; aMax = 0; depth = 0; 2: while depth < L ∧#PointSet < K do 3: while @Ii ∈ PF that Ii ≺Q aTupleMax do 4: for t = 1 to T do 5: Get Ii in top of list ranked EQt that not marked; 6: if aMax < DtQ(Ii) then aMax = D t Q(Ii); 7: end if 8: isDominated = false; 9: while not(isDominate)∧(∃Ij ∈ PF ) unmatched with Ii do 10: if Ii ≺Q Ij then Move Ij from PF to PF Next; 11: end if 12: if Ij ≺Q Ii then 13: isDominated = true; Insert Ii into PF Next; 14: end if 15: end while 16: if not(isDominated) then Insert Ii into PF ; 17: end if 18: aTupleMaxt = aMax; . reset threshold for t th tuple 19: Select points Ii ∈ PF that aTupleMax ⊀Q Ii into PointSet and update depth; 20: end for 21: end while 22: if #PointSet < K then 23: PF = PF Next;PF Next = ∅; 24: for all Ii, Ij ∈ PF that Ii ≺Q Ij do 25: Move Ij from PF to PF Next; 26: end for 27: Select images Ii ∈ PF that aTupleMax ⊀ Ii into PointSet and update depth; 28: end if 29: end while The results of the Pareto points by algorithm 1 are called PFDLQ (choose 1 ≤ L ≤ 10), where L is depth of the Pareto front. According to definition 5, it is needed to get a set of PFUL(EA) which consists the Pareto points from the Pareto front at different depths. The set of PFUL(EA) is computed with each relevant point as query Q. The set of PFUL(EA) CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES 179 is the input test data for classification engine. This set is much smaller than the set of EA. Relevance feedback is used to improve the accuracy the set of first-round best images. After each feedback loop, we get a set of first best k images which is denoted by set of NB. We denote the set of relevant images by NB+, and set of irrelevant images by NB−based on appreciation by the users (NB = NB+ ∪NB−, and NB is subset of set PFUL(ENB+). Showing best k images, the method is normally applied by the combination of linear functions of component distance measures. This method is difficult to reach desired images which are most relevant images in NB, especially after the Pareto set PFUL(ENB+) is reconstructed from the set of relevant images. The Pareto approach also reduces noise in the training data of the classification engine. The LIBSVM1 is used as effective classification tools for Pareto point set (PFUL(ENB+)). From the set of NB+, the query expansion technique is used. Each point is considered as a query and the process is continued according to definition 5 to get more Pareto points at different depths. The algorithm CUPF is implemented to getting the set of PFUL(ENB+) and classification is performed. Algorithm 2 CUPF -Classification Union Pareto Front Input: E; . Feature database L ; . depth of the Pareto front. K ; . The number of points in the Pareto front set Output: Satisfy images; 1: Initialize: EQ ← Compute similarity measure for each image with a query image; PFDLQ ← PFDA({EQ}, L,K); . see definition 3 and algorithm 1; NB ← PFDLQ; . top k best results according to similarity measures of images in Pareto front NB+ and NB− ← NB; . Construct training set based on user’s preference 2: while User not Satisfied do 3: PFUL(NB +) = ∅; 4: for each Q′ ∈ NB+ do 5: EQ′ ← Compute similarity measure for each image with a new query image; 6: PFUL(ENB+) = PFUL(ENB+)∪PFDA({EQ′}, L,K); /* Compute union Pareto front (see algorithm 1 and definition 4) */ 7: end for 8: Training set← NB+ and NB− ; /* Construct training set based on user’s preference */ 9: Testing set ← PFUL(ENB+); 10: Construct classification function (using algorithms [33] or [32]); 11: NB ← top k results at PFUL(ENB+) according to the predicted values of classifica- tion function; 12: NB+ and NB− ← NB; /* Update training set by user */ 13: end while Our algorithms use comparison operators on T lists corresponding to the number of 1https://www.nuget.org/packages/libsvm.net 180 VAN HIEU, TRUONG THANG, HUU QUYNH, QUOC TAO features. The complexity of the algorithm PFDA is O(n×T ×K) where n, K and T are the number of images in database, Pareto points and features, respectively. For the algorithm CUPF , the complexity is O(L× n× T ×K), where L is depth of the Pareto front. 4. THE EXPERIMENTS For performance evaluation of the proposed method, some experiments are implemented and installed. The proposed method is compared with the SVM origin, i.Boost (an im- provement of AdaBoost), and the state-of-the-art relevance feedback is reimplemented in the MARS system. 4.1. Image characterization In the experiment, described images in color, texture, and shape with overall six low-level features (see Table 2). Table 2: Image characterizations used in the experiment Discription Type Dimension Distance function HSV Histogram [31] Color 32 L1 Color moments [29] Color 6 L2 Color auto correlogram [13] Color 64 L1 Gabor filters [16] Texture 48 L2 Wavelet moments [11] Texture 40 L2 Gist [19] Shape 512 L2 The performance is evaluated with three real databases which are used in many CBIR systems. The images in databases are organized according to semantic categories (The im- ages of the same category are considered relevant and opposite). The detail of the datasets are given below: Db1. This is the COREL dataset [17]. It consists of 1000 images uniformly divided into 10 categories. We use sea, Africa, rose, horse, mountain, food, bus, dinosaur, building, elephant. We get random 10% images in each category for queries. Db2. The Oxford Buildings Dataset [21] consists of 5062 images collected from Flickr by Table 3: The Pareto points set in each feedback loop with query 710.jpg. Parameters: Pareto points in set =100, depth = 20, iterations = 10 CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES 181 searching for particular Oxford landmarks. The collection has been manually annotated to generate a comprehensive ground truth for 11 different landmarks, each represented by 5 possible queries. We have a set of 55 queries over which an object retrieval system can be evaluated. Those are categories: All Souls Oxford, Ashmolean Oxford, Balliol Oxford, Bodleian Oxford, Christ Church Oxford, Cornmarket Oxford, Hertford Oxford, Keble Ox- ford, Magdalen Oxford, Pitt Rivers Oxford, Radcliffe Camera Oxford. It consists 2560 images. Db3. This is a subset of the Caltech 101 dataset [7], which obtained by randomly selecting 101 categories with a number of images per category ranging from 40 to 800. Ten categories are taken containing ant, bass, beaver, brontosaurus, cannon, ewer, mandolin, wrench, wind- sor chair, umbrella. We get random 10% images in each category for queries. After feature extraction, each dimension is normalized into scope [0, 1] by normalization method in [28]. 4.2. Baselines The proposed method is compared with three RF methods which use the same baseline: • Compare to support vector machine: Tong and Chang, 2001 [33] as classification engine for classify database images between relevant and irrelevant images. • Compare to i.Boost algorithm [32]: Tieu et al use AdaBoost technique to classify database images in relevance feedback in loop. • Compare to Relevance feedback using re-weighting in MARS [28], Rui et al, 1998. 4.3. Performance measures Two measures Precision vs. Recall and Retrieved relevant images vs. number of iterations (retrieval efficiency) [18] are used to evaluate the effectiveness of the proposed method. Precision vs. Recall curve is a general evaluation criterion for information retrieval systems. Precision Pr(q) can be defined as the number of retrieved relevant images Relevant(q) over the total number of retrieved images N(q) for a given query q, therefore: Pr(q) = Rel(q)N(q) . Recall Re(q) is the number of retrieved relevant images Rel(q) over the total number of relevant images C(q) present in the database for a given query q, therefore: Re(q) = Rel(q)C(q) . Retrieved relevant images vs. number of iterations curves are used to show the percentage of relevant images retrieved to the user given a number of RF iterations. This curve allows Table 4: The Pareto points set in each feedback loop with query 710.jpg Parameters: Pareto points in set =300, depth = 20, iterations = 10 182 VAN HIEU, TRUONG THANG, HUU QUYNH, QUOC TAO to evaluate how the number of retrieved relevant images grows over iterations. For iteration zero, the number of relevant images retrieved in the initial set is considered. The average Pr vs. Re and Rel vs. iterations curves, the results for all query images are used to compare the RF approaches. This test aims to verify if both Pr vs. Re and Rel vs. iterations curves obtained by using the proposed framework in CBIR tasks are statistically (significant) different from all the others. 4.4. Experiment results In experiments, the representation of users are simulated. All images belonging to the same class with the query image are considered relevant. Ten iterations are considered for each query (normanlly total images retrieved are 10% to 20% of the whole data set). Experiments also evaluate the effectiveness of the methods when twenty images are shown to the user on each iteration (normanlly only 2% to 5% of the whole data set is needed). 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 Recall Pr ec is io n PARETO−SVM SVM i.Boost MARS (a) (Db1) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.16 0.18 0.2 0.22 0.24 0.26 0.28 0.3 0.32 0.34 Recall Pr ec is io n PARETO−SVM SVM i.Boost MARS (b) (Db2) Figure 1: Average Precision vs. Recall Graph for Proposed model, SVM, i.Boost, and MARS in Db1 and Db2 The results in Table 3 and Table 4 show the effectiveness of the Pareto method. Table 3 sets 100 points in each Pareto front, number of relevant images retrieved is 99 and it saves average the search space up to 68.1%. Table 4 sets 300 points in each Pareto front, number of relevant images retrieved is 98 while it only saves average the search space up to 35.8%. Figure 1a, Figure 1b and Figure 2 show the average for there datasets Db1, Db1 and Db3. In Figure 1a average precision performance in the first 4 rounds of the proposed method is worse than those of three baseline methods, but from the 5th to 10th round its precision remarkedly increases. Average precision of Proposed model, SVM, i.Boost and Mars is 51.3%, 50.6%, 47.3%, 49.8% respectively. In Figure 3a, Figure 3b and Figure 4 the accuracy of proposed method is always higher than baseline methods. Figure 5 is framework of the proposed method. In this framework, top twenty images were shown to users and users selected ”-1” or ”+1” corresponding to ”irrelevant” or ”relevant” CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES 183 0 0.05 0.1 0.15 0.2 0.12 0.14 0.16 0.18 0.2 0.22 0.24 0.26 Recall Pr ec is io n PARETO−SVM SVM i.Boost MARS Figure 2: Average Precision vs. Recall Graph for Proposed model, SVM, i.Boost, and MARS in Db3 0 2 4 6 8 10 10 20 30 40 50 60 70 80 Retrieval Effciency Number of Relevance Feedback Ac cu ra cy o n Re tu rn ed Im ag es PARETO−SVM SVM i.Boost MARS (a) (Db1) 0 2 4 6 8 10 5 10 15 20 25 30 35 40 Retrieval Effciency Number of Relevance Feedback Ac cu ra cy o n Re tu rn ed Im ag es PARETO−SVM SVM i.Boost MARS (b) (Db2) Figure 3: Retrieval effciency Graph for Proposed model, SVM, i.Boost, and MARS in Db1 and Db2 by his or her subjective perception with desired output. Then system uses those labeled images for training data and processing feedback. 5. CONCLUSION AND FUTURE WORK This article formalizes properties of Pareto fronts in the search space in CBIR systems using multi features. The proposal carries out an efficiency for the classification engine. The Pareto method overcomes entanglements when CBIR systems use classification engine dealing with less 184 VAN HIEU, TRUONG THANG, HUU QUYNH, QUOC TAO 0 2 4 6 8 10 0 5 10 15 20 25 30 35 40 Retrieval Effciency Number of Relevance Feedback Ac cu ra cy o n Re tu rn ed Im ag es PARETO−SVM SVM i.Boost MARS Figure 4: Retrieval effciency Graph for Proposed model, SVM, i.Boost, and MARS in Db3 Figure 5: Framework Proposed Method labeled samples and real-time training data. It also overcomes entanglements with query movement or query expansion techniques in MARS which appears to be properly seeded, bootstrapped. For evaluating the performance of the proposed method, the authors have experimented on subsets of the following datasets: Corel, Oxford and Caltech 101 Buildings. The proposed method is compared with boosting technique (an improvement of AdaBoost), Support Vector Machine and relevant feedback technique used in MARS. The proposed method is proved for its effectiveness. In the future, the authors continue to expand the Pareto method for reducing set of the search space and applying for retrieval target image in the big data. CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES 185 ACKNOWLEDGMENT This article is partly supported by VAST01.07/15-16 project which is a grant from Viet- nam Academy of Science and Technology. REFERENCES [1] S. Agarwal, A. K. Verma, and N. Dixit, “Content based image retrieval using color edge detection and discrete wavelet transform,” in Issues and Challenges in Intelligent Computing Techniques (ICICT), 2014 International Conference on. IEEE, 2014, pp. 368–372. [2] M. Arevalillo-Herra´ez, F. J. Ferri, and S. Moreno-Picot, “Improving distance based image re- trieval using non-dominated sorting genetic algorithm,” Pattern Recognition Letters, vol. 53, pp. 109–117, 2015. [3] G. Beliakov, A. Pradera, and T. Calvo, Aggregation functions: a guide for practitioners. Springer, 2007, vol. 221. [4] J. Chomicki, “Querying with intrinsic preferences,” in Advances in Database TechnologyEDBT 2002. Springer, 2002, pp. 34–51. [5] D. Dubois, A. Hadjali, H. Prade, and F. Touazi, “Erratum to: Database preference queries- a possibilistic logic approach with symbolic priorities,” Annals of Mathematics and Artificial Intelligence, vol. 73, no. 3-4, pp. 359–363, 2015. [6] P. M. Fayers and R. D. Hays, “Should linking replace regression when mapping from profile- based measures to preference-based measures?” Value in Health, vol. 17, no. 2, pp. 261–265, 2014. [7] L. Fei-Fei, R. Fergus, and P. Perona, “Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories,” Computer Vision and Image Understanding, vol. 106, no. 1, pp. 59–70, 2007. [8] P. Fishburn, “Preference structures and their numerical representations,” Theoretical Computer Science, vol. 217, no. 2, pp. 359–383, 1999. [9] Y. Freund, R. Schapire, and N. Abe, “A short introduction to boosting,” Journal-Japanese Society For Artificial Intelligence, vol. 14, no. 771-780, p. 1612, 1999. [10] J. Fu¨rnkranz, E. Hu¨llermeier, W. Cheng, and S.-H. Park, “Preference-based reinforcement learn- ing: a formal framework and a policy iteration algorithm,” Machine learning, vol. 89, no. 1-2, pp. 123–156, 2012. [11] P. Hiremath, S. Shivashankar, and J. Pujari, “Wavelet based features for color texture classifica- tion with application to cbir,” International Journal of Computer Science and Network Security, vol. 6, no. 9A, pp. 124–133, 2006. [12] K.-J. Hsiao, J. Calder, and A. O. Hero, “Pareto-depth for multiple-query image retrieval,” Image Processing, IEEE Transactions on, vol. 24, no. 2, pp. 583–594, 2015. [13] J. Huang, S. R. Kumar, M. Mitra, W.-J. Zhu, and R. Zabih, “Image indexing using color correlograms,” in Computer Vision and Pattern Recognition, 1997. Proceedings., 1997 IEEE Computer Society Conference on. IEEE, 1997, pp. 762–768. 186 VAN HIEU, TRUONG THANG, HUU QUYNH, QUOC TAO [14] Y. Ishikawa, R. Subramanya, and C. Faloutsos, “Mindreader: Querying databases through mul- tiple examples,” Computer Science Department, p. 551, 1998. [15] M. Korytkowski, L. Rutkowski, and R. Scherer, “Fast image classification by boosting fuzzy classifiers,” Information Sciences, vol. 327, pp. 175–182, 2016. [16] T. S. Lee, “Image representation using 2d gabor wavelets,” Pattern Analysis and Machine In- telligence, IEEE Transactions on, vol. 18, no. 10, pp. 959–971, 1996. [17] J. Li and J. Z. Wang, “Automatic linguistic indexing of pictures by a statistical modeling ap- proach,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 25, no. 9, pp. 1075–1088, 2003. [18] H. Mu¨ller, W. Mu¨ller, D. M. Squire, S. Marchand-Maillet, and T. Pun, “Performance evaluation in content-based image retrieval: overview and proposals,” Pattern Recognition Letters, vol. 22, no. 5, pp. 593–601, 2001. [19] A. Oliva and A. Torralba, “Modeling the shape of the scene: A holistic representation of the spatial envelope,” International journal of computer vision, vol. 42, no. 3, pp. 145–175, 2001. [20] F. Ortega, J.-L. Sa´Nchez, J. Bobadilla, and A. Gutie´Rrez, “Improving collaborative filtering- based recommender systems results using pareto dominance,” Information Sciences, vol. 239, pp. 50–61, 2013. [21] J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, “Object retrieval with large vocabu- laries and fast spatial matching,” in Computer Vision and Pattern Recognition, 2007. CVPR’07. IEEE Conference on. IEEE, 2007, pp. 1–8. [22] O. Pivert and H. Prade, “Skyline queries in an uncertain database model based on possibilistic certainty,” in Scalable Uncertainty Management. Springer, 2014, pp. 280–285. [23] K. Porkaew and K. Chakrabarti, “Query refinement for multimedia similarity retrieval in mars,” in Proceedings of the seventh ACM international conference on Multimedia (Part 1). ACM, 1999, pp. 235–238. [24] J. J. Rocchio, “Relevance feedback in information retrieval,” pp. 313–323, 1971. [25] Y. Rui, T. S. Huang, and S.-F. Chang, “Image retrieval: Current techniques, promising di- rections, and open issues,” Journal of visual communication and image representation, vol. 10, no. 1, pp. 39–62, 1999. [26] Y. Rui, T. S. Huang, and S. Mehrotra, “Content-based image retrieval with relevance feedback in mars,” in Image Processing, 1997. Proceedings., International Conference on, vol. 2. IEEE, 1997, pp. 815–818. [27] Y. Rui, T. S. Huang, S. Mehrotra, and M. Ortega, “Automatic matching tool selection using relevance feedback in mars,” in Proc. of 2nd Int. Conf. on Visual Information Systems, 1997. [28] Y. Rui, T. S. Huang, M. Ortega, and S. Mehrotra, “Relevance feedback: a power tool for interactive content-based image retrieval,” Circuits and Systems for Video Technology, IEEE Transactions on, vol. 8, no. 5, pp. 644–655, 1998. [29] M. A. Stricker and M. Orengo, “Similarity of color images,” in IS&T/SPIE’s Symposium on Electronic Imaging: Science & Technology. International Society for Optics and Photonics, 1995, pp. 381–392. CONTENT BASED IMAGE RETRIEVAL USING MULTIPLE FEATURES 187 [30] J.-H. Su, W.-J. Huang, P. S. Yu, and V. S. Tseng, “Efficient relevance feedback for content-based image retrieval by mining user navigation patterns,” Knowledge and Data Engineering, IEEE Transactions on, vol. 23, no. 3, pp. 360–372, 2011. [31] M. J. Swain and D. H. Ballard, “Color indexing,” International journal of computer vision, vol. 7, no. 1, pp. 11–32, 1991. [32] K. Tieu and P. Viola, “Boosting image retrieval,” International Journal of Computer Vision, vol. 56, no. 1-2, pp. 17–36, 2004. [33] S. Tong and E. Chang, “Support vector machine active learning for image retrieval,” in Proceed- ings of the ninth ACM international conference on Multimedia. ACM, 2001, pp. 107–118. [34] R. Torlone, P. Ciaccia, and U. Romatre, “Which are my preferred items,” in Workshop on Recommendation and Personalization in E-Commerce, 2002. [35] X.-Y. Wang, H.-Y. Yang, Y.-W. Li, W.-Y. Li, and J.-W. Chen, “A new svm-based active feedback scheme for image retrieval,” Engineering Applications of Artificial Intelligence, vol. 37, pp. 43–53, 2015. [36] L. Wu, C. Faloutsos, K. Sycara, and T. R. Payne, “Falcon: Feedback adaptive loop for content- based retrieval,” DTIC Document, Tech. Rep., 2000. [37] B. Xu, J. Bu, C. Chen, D. Cai, X. He, W. Liu, and J. Luo, “Efficient manifold ranking for image retrieval,” in Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval. ACM, 2011, pp. 525–534. [38] J. Yu, J. Lu, Y. Xu, N. Sebe, and Q. Tian, “Integrating relevance feedback in boosting for content-based image retrieval,” in Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, vol. 1. IEEE, 2007, pp. I–965. [39] L. Zhang, F. Lin, and B. Zhang, “Support vector machine learning for image retrieval,” in Image Processing, 2001. Proceedings. 2001 International Conference on, vol. 2. IEEE, 2001, pp. 721–724. Received on August 12 - 2016 Revised on November 10 - 2016