Summary of PhD thesis Computer science: Improve the efficiency of contentbased image retrieval through weight adjustment technique of the distance function

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

19
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

The thesis proposes a number of image retrieval methods to improve image retrieval accuracy. These methods will address issues of reducing semantic gaps between low-level features and high-level concepts of images.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Summary of PhD thesis Computer science: Improve the efficiency of contentbased image retrieval through weight adjustment technique of the distance function

MINISTRY OF EDUCATION VIETNAM ACADEMY OF SCIENCE AND TRAINING AND TECHNOLOGY GRADUATE UNIVERSITY OF SCIENCE AND TECHNOLOGY ……..….***………… DAO THI THUY QUYNH IMPROVE THE EFFICIENCY OF CONTENT-BASED IMAGE RETRIEVAL THROUGH WEIGHT ADJUSTMENT TECHNIQUE OF THE DISTANCE FUNCTION Major: Computer Science Code: 9 48 01 01 SUMMARY OF PHD THESIS Ha Noi – 2019 1
The thesis has been completed: Graduate University Of Science And Technology - Vietnam Academy Of Science And Technology Supervisor 1. Assoc. Prof. Dr. Ngo Quoc Tao Supervisor 2. Assoc. Prof. Dr. Nguyen Huu Quynh Review 1: Review 2: Review 3: The thesis will be defended at the Board of Examiners of Graduate University Of Science And Technology - Vietnam Academy Of Science And Technology, at……………….on…………………………. The thesis can be explored at: - Library of Graduate University Of Science And Technology - National Library of Vietnam 2
PREFACE 1. Motivation of the thesis Image database is becoming more and more popular in various application fields such as remote sensing, crime prevention, medicine, education ... The evolution of image acquisition, transmission and storage techniques has allowed the construction of very large image databases. These factors have prompted the attention of the image retrieval community to propose ways to effectively exploit this image database. Content-based image retrieval techniques are time-consuming, costly, and depend on the subjective perception of the descriptors. Moreover, when changes are needed, this system is difficult to implement. To overcome this problem, in the early 1990s, content-based image retrieval (CBIR) was launched. The basic idea of this approach is to use automated visual feature extraction techniques to produce content descriptions from images, such as color, texture, and shape characteristics. These content descriptions are used for indexing images. There are many content based image retrieval systems that have been proposed. However, many experiments on CBIR systems indicate that low-level content often fails to describe high-level semantic concepts that appear in the user's mind. The performance of CBIR systems is still far from the users' expectations. Therefore, the thesis chooses the topic of "Improve the efficiency of content- based image retrieval through weight adjustment technique of the distance function " to contribute to solving existing problems. 2. The objective of the thesis The thesis proposes a number of image retrieval methods to improve image retrieval accuracy. These methods will address issues of reducing semantic gaps between low-level features and high-level concepts of images. 3. The major contributions of the thesis Propose SRIR method (Semantic–Related Image Retrieval method), AWEIGHT method (An efficient image retrieval method using adaptive weights). 4. Thesis organization The contents of the thesis are presented in three chapters. Chapter 1 introduces the fundamentals of content-based Image retrieval. Chapter 2 presents the semantic-related image retrieval method. Chapter 3 presents an efficient image retrieval method using adaptive weights. Final, the thesis presents conclusions and future research. 1
Chapter 1. OVERVIEW OF CONTENT-BASED IMAGE RETRIEVAL 1.1. Introduction Various types of multimedia sources are increasing rapidly, such as visual data in smartphones, 2D / 3D applications, web content, etc. Therefore, the need for image applications is more important than ever. However, visual media requires a significant amount of processing and storage. It requires efficient methods to index, store, analyzes and retrieval visual information from image databases. Therefore, retrieval images to ensure quickness, accuracy, and efficiency becomes one of the challenging tasks. 1.1.1. Text-based image retrieval The original approach for image retrieval is based on the text that describes the image, in which the images are indexed by keywords, topics or classification codes. These keywords, topics or classification codes are used in the retrieval process. However, with large image databases, the difficulties faced by the text- based retrieval approach are becoming more serious, for example: this process is labor-intensive, time-consuming and subjectivity of the description. To overcome these problems, a content-based image retrieval approach was born. In CBIR, the image contents are automatically extracted from the images themselves used for retrieving the image. 1.1.2. Content-based image retrieval In CBIR, images can be searched either using low-level features (ie colors, shapes, and textures) or using high-level semantic concepts. Figure 1.1. Illustration of semantic distance. The architecture of the image-based retrieval system is shown in Figure 1.2. Figure 1.2. The architecture of content-based image retrieval system. 2
Figure 1.3 shows the implementation mechanism of the relevant feedback in CBIR. When the initial retrieval results are available, the user selects the related images in this list of results as labeled samples (positive or negative). Based on this training set, a machine learning algorithm is implemented to adjust the parameters. Based on the parameters that have just been learned, image retrieval is performed. The process is repeated until the user is satisfied. Figure 1.3: Image retrieval diagram using machine learning with relevance feedback. 1.1.3. Related works Several CBIR methods have been proposed, which are the core of the systems, such as: VisualSeek, SIMPLicity, Blobwworld, WebSeek, Image Rover…. 1.2. Feature extraction 1.2.1. Color feature The color feature is used very effectively for retrieving color images in the image database. Color descriptions are extracted and compared effectively, so they are suitable for visual characteristics based retrieval. 1.2.2. Texture feature Image texture is an important feature of an image to describe the surface properties of an object and its relationship to surrounding areas. 1.2.3. Shape feature The shape features of images carry semantic information and can be classified into two categories: contour-based and region-based. 3
1.2.4. Spatial feature Spatial information represents the absolute spatial location and relative spatial position of the regions. Regions or objects with similar color characteristics can be better distinguished by taking advantage of spatial information. 1.3. Distance function The choice of the distance measure type, which is used to compare the similarity of each pair of images, depends on the structure of the feature vectors that describe them. Some similar measurements are commonly used: Minkowski, Mahalanobis, Cosine, Hamming, Earth Mover ... 1.4. Clustering Following the typical representation and extraction process, clustering methods perform grouping image descriptions into different clusters with different semantics. Clustering methods commonly used in image retrieval include: K-means, GMM (Gaussian mixture models) and fuzzy clustering (such as fuzzy c-means), MPCK-mean ... 1.5. Reduce the semantic gap There are many approaches to reduce the semantic gap in content-based image retrieval. The thesis chooses the approach of machine learning to propose to reduce this gap. 1.6. Evaluation To evaluate an image retrieval system, an image database and a set of queries are required. Queries are performed to obtain retrieval results. The performance evaluation method is then used to compare these retrieval results with images related to the query image in the database. 1.7. Conclusion of chapter 1 and the scope of the thesis In this chapter, the thesis has presented the low-level features of the image, the structure of the low-level features based image retrieval system and analyzed some image retrieval methods based on the low-level feature. Besides, the thesis also presented several methods to reduce semantic distance according to related feedback approach. Several image retrieval techniques with high-level semantics have also been analyzed. At present, when we propose an efficient algorithm for CBIR, some problems must be solved. The first problem is to reduce the burden on users, that is, does not require users to provide multiple image queries simultaneously. The second problem is that semantically related images, which do not belong to the same cluster, are scattered throughout the feature space. Therefore, to increase accuracy, it is necessary to have a way to get images scattered in the featured space. The third problem is that the regions that contain different good query 4
points can be very different. Therefore, to improve the accuracy, it is necessary to exploit the local information of each region. In this thesis, the author will focus on improving image retrieval accuracy in the direction of reducing semantic distance. Firstly, the thesis will propose a semantic-related image retrieval method to obtain a diverse set of result images that are scattered throughout the entire feature space without requiring users to create complex queries [CT5]. Secondly, the thesis will propose the image lookup method using an adaptive weight set. Instead of using the same set of weights for clusters that contain good query images, the method of determining weights for each specific cluster [CT6]. 5
Chapter 2. THE SEMANTIC-RELATED IMAGE RETRIEVAL METHOD 2.1. Introduction The low-level feature based image retrieval approaches assume that in a feature space, the location of the relevance images is closer to the query image than the other images. However, this assumption does not fit into the problem where it is required to find images with the same semantic concepts but low-level features may not be the same. for example: finding all roses (including red, yellow and white roses) in the image database. This chapter and the next chapter of the thesis will propose methods to solve the problem to find images that can have different low-level features but with the same high-level semantic concept (ie the same topic). The similarities between images that people perceive (the images are semantically relevant) are different from the similarities between them in the feature space. That is, semantically related images can be scattered throughout the feature space and scattered over several clusters rather than a single cluster. In this case, the traditional methods [2,29,61,74] of using the feedback approach do not work well (because these methods have used the single-point query approach). Performing feedback involves the calculation of one or more new query points in the feature space and changing the distance function. The methods presented in the feedback approach with the separate query have the advantage of obtaining semantically related images scattered throughout the feature space. However, these methods have limitations: (1) It requires users to provide multiple query images simultaneously, for example, to query for the rose theme, users must provide images of red roses, yellow roses, white roses, ... as a query. If this condition is not met, the initial retrieval result will be the images in a certain region without including relevance images in different regions. If the user only provides the system with yellow rose images, the initial retrieval results may only include yellow rose images that ignore white and red rose images. The reason for this is because, in traditional image retrieval systems, images with low-level feature vectors that are similar will lie close together (or in the same low-level feature cluster). On the list of initial results consisting of yellow roses, the user can only select yellow roses. The system will rely on the responses of the yellow roses to continue the retrieval. The next retrieval phase will move to the yellow regions. The result of the system can only get yellow roses. Therefore, red and white rose regions will be ignored, so the accuracy of the system will be limited no matter how superior the next retrieval phase will be. 6
(2) The number of queries for the next iteration depends on the number of related images provided by the user, therefore, there are two unfavorable possibilities: Firstly, the user chooses too few responses (less than the number of clusters in the featured space). In this capacity, the accuracy of the system will not be guaranteed because according to clustering theory, more queries will cover more clusters. The second possibility is that the user chooses too many feedback images. This capability will increase the burden of aggregating the result lists (each query will have a result list). In addition, too many queries do not improve the accuracy of the system (experiments in [49] have shown that accuracy increases rapidly from 1 to 8 queries and increases slowly when the number of queries is from 8 to 20). For example, in the Corel database with the theme of roses, each rose query image is only scattered in 4 clusters (each cluster corresponds to a color of rose). (3) Using the weights of different queries is equal, that is, the importance of queries is the same even though each query has different neighbors. (4) The features are equally weighted even though each feature component has a different importance. These limitations are the main reason leading to the low accuracy of the retrieval system. Based on the analysis of the limitations of the available methods, the thesis proposes a semantic image retrieval method. The proposed method has advantages: (1) Use only one query to create diverse initialized retrieval results, which include images located in different regions (reduce the burden on users). (2) Cluster the related images with low-time cost. (3) Identify the semantic importance of each query. (4) Determine importance according to each feature. These four advantages have been expressed in the method that the author has published in [CT5, CT6]. 2.2. The proposed method diagram Based on the analysis in Section 2.1, the thesis proposes the diagram of the method as shown in Figure 2.5. 7
Query Multiple representations Result Feature vectors Sort Feedback Incremental Similarity Comparison Result set Feedback set Cluster Clustes Retrieve Importance of Feature Database Calculation each query Calculation Multi-ponts Importance of query each feature Representation Figure 2.5. The structure of the proposed method. The next section of the thesis will describe in detail the proposed method. The next section needs some definitions, so the thesis gives some definitions here. Definition 2.1 (Feature set). A feature set F consists of T feature sets, each consisting of m components, each of which is a real value. (2.1) Definition 2.2 (Feature space). A feature space FS consists of m dimensions, each corresponding to a real component of the feature set t (t = 1..N) of the feature set F, Each point pt (t = 1..N) in space FS corresponds to a feature set in F. (2.2) th th Definition 2.3 (i feature space). i feature space is denoted by , is a feature space of n dimensions, Each point in this space is denoted by (t=1..N) with n coordinates. (2.3) Definition 2.4 (Measure the distance between two points in the feature space FSi). Measure the distance between two points and (k,l=1..N) with kl, denoted by ( ), is a measure of some distance. The main idea of the proposed method is not to place images (including both database and query image) in the same feature space but in different feature spaces (In the context of this chapter, the thesis maps each representation of an image into a corresponding feature space), then perform a retrieval by querying each of these feature spaces and merging the results corresponding to the feature spaces into one final result. 8
The reason that the method in the thesis can get images scattered in the original color space is that the images were converted to grayscale representation. According to this representation, the characteristics of shape and texture will not be overwhelmed by color. An image of a rose (gray representation) will be mapped into a point in the feature space. In this space, because the color is not included, images of the same subject (for example: yellow, white and red roses) will be close to each other. Therefore, the proposed method can obtain red, pink and yellow rose images corresponding to the red rose query image. At this point, the retrieval process will match the query image and the database image in each individual feature space to get a list of results. Thus, we will have four result lists. Next, the four result lists will be combined to get a final list of results. 2.3. Relevance feedback with multi-point query The original approach for content-based image retrieval is incompatible with users' perceptions of visual similarity. To fix this problem, several image retrieval methods using relevant feedback are proposed. There are two components to learning in the relevant feedback approach: distance function and new query point. The distance function is changed through learning the weights of the feature components and new query points are obtained by learning the desired points that the users need. 2.4. The proposed image retrieval algorithm Definition 2.5 (Multi-point query): A multipoint query MQ=, with nMQ denoting the number of query points in MQ, PMQ={PMQ1,…,PMQn} is the set of nMQ query points in the DB search space, WMQ={wMQ1,…,wMQn} is the set of weights associated with PMQ (the thesis assumes that the weights are normalized, ie, ∑ ), DMQ is the distance that when we give any two points pi and pj in the feature space, it will return the distance between them and k is the number of points to be retrieved in each iteration. 2.4.1. Cluster algorithm for feedback images set The algorithm below describes the initial clustering algorithm that uses k eigenvectors, named CISE (Clustering Images Set using Eigenvectors). Clustering Images Set using k Eigenvectors Input: -Image set S={s1,s2 sn} with si Rn - Number of cluster k Output: k cluster: C1, C2 Ck 1. Form the affinity maxtrix for i1 to n do for j1 to n do 9
‖ ‖ if (ij)  else  2. Construct the diagonal matrix and Laplace matrix L for i1 to n do ∑ L  D-1/2 A D-1/2 3. Compute the k largest eigenvectors x1, x2 k of the Laplace matrix L for i1 to k do  X  [x1T ,x2T kT ] 4. Construct matrix Y from X for i1 to n do for j1 to k do yij  xij/ ∑ )1/2 Y  [y1 ,y2 yk ] Step 5: Form k cluster via K-Means  for i1 to n do   K-Mean(P) Step 6: Assign the points to cluster for i1 to n do if Return C1, C2 Ck 2.4.2. The proposed incremental clustering algorithm There are many clustering algorithms such as K-means, K-medoid,…. which are used in image retrieval methods. However, when a new image is added, the methods must recluster all the images. In incremental clustering algorithms, determining the cluster for an object is the most important task. Below, we describe our proposed incremental clustering algorithm. Assume that the data has a Gauss distribution. In this algorithm, we treat each cluster as a group. When training, we will estimate the center of each group and the covariance matrix. The task of determining the cluster of an object is 10
considered as the problem of finding an estimate such that: for an input , Its cluster label will be identified by: ŷ0 y (2.8) However, is difficult to calculate, so instead of calculating , we will estimate through and . According to Bayes rule, where is the label of the group, we have the formula: (2.9) ∑ (2.10) Assume that is a multivariate normal distribution with a density: ∑ = ∑ (2.11) Where: : Mean of the inputs for group ∑ : Covariance matrix (common to all groups) Suppose that we know: (2.12) (2.13) Note: formula (2.13) is the ratio of the training samples of group i to the total number of training samples. At this point, we obtain the formula: (2.14) Since the denominator in (2.14) is independent of , we can consider it a constant C and obtain the formula: (2.15) Replacing from (2.11) into (2.15), we get: ∑ ∑ (2.16) Because 2 ∑ in (2.16) does not depend on , we set ∑ equal to the constant and we have: ∑ (2.17) and take the logarithm of both sides of (2.17), we get: ∑ (2.18) In (2.18), the value of the right side is true for all groups , so we are only interested in: ∑ (2.19) 11
= [ ∑ ∑ ] ∑ (2.20) Thus, our goal is to maximize the formula (2.20) in . In (2.20), since ∑ is independent of , we consider it a constant and (2.20) transformed into ∑ ∑ (2.21) Ignoring the constant , we have the objective function: ∑ ∑ (2.22) With an input x, we predict its label as when is the largest. 2.4.3. Improved distance function The distance from an image to multipoint query MQ = (Q1, Q2,..Qn). Formula (2.23) is the minimum of weighted distances from an image to each query Qi: ( ) (2.23)  In the formula (2.23), Dist( ,Qi ) với i=1..n, j=1..k is the distance from an image to a query Qi with feature weight (determined by the algorithm IF ), is the sematic weight combined with distance dij (see way to calculate semantic weight in formula (2.24)). 2.4.4. Calculate the semantic weight of the query The propose relies on the perception that a cluster containing multiple semantically related images is more important than remaining clusters. Therefore, the queries generated from that cluster have semantic weight higher than the remaining clusters. So the calculation of semantic weight wij combined with distance dij from image to query Qi (belongs to semantic cluster i) is the ratio of the number of semantically related images in cluster i and the total number of related images of n semantic clusters ∑  (2.24) The weights need to satisfy the condition ∑  2.4.5. Calculation algorithm for the feature importance The main idea of determining the feature importance is based on user feedback. When a user responds some images as semantically related with query image, we will cluster these semantically related images into clusters and consider each of the clusters as follows: each image in the cluster will be a point in multi-feature space and these points will be located near each other in the multi-feature space. A shape covering these points will be projected into axes corresponding to features, then we calculate the variance of these points in each axis (knowing the degree of data dispersion in an axis in a large feature space 12
means the importance in the axis low). Thus the importance of each feature in multi-feature space is the inverse of the variance of the points in that the axis. 2.4.6. The Combination algorithm performing the combination of result lists With the input of query lists Q1, Q1,…Qn and respective result lists R1, R2, ….Rn, each Ri will take first k classified images IRi1, IRi2 . . . IRik. The result lists need to be contributed to getting the combined result R. Proposition 1. [Complexity of the algorithm Combination]: The complexity of the algorithm Combination is O(nk), where n is the number of combined lists and k is the number of returned images of each list. 2.4.7. Semantic-related image retrieval (SRIR) algorithm In this section, the thesis proposes an algorithm called SRIR (Semantic – Related Image Retrieval), which does not require users to provide multiple queries. SRIR algorithm Input: Set of image database: DB Query image: Q Number of retrieved images after each iteration: k Feature space: F Number of feature: m Ouput: Set of result images: R C+Q; PMQFC+  ; WMQFC+ ; DMQFC+ (  ) s1 ; C-  ; PMQFC-  ; WMQFC- ; DMQFC- (  ) s2 ; G+  2 ; PMQFG+  ; WMQFG+ ; DMQFG+ (  ) s3 ; G-  ; PMQFG-  ; WMQFG- ; DMQFG- (  ) s4 ; ( ) US ; repeat USUS ; CL ; for i1 to n do 13
 ; ci (CiCL); PMQici for j1 to k do WMQi∑ DMQid (  ); Ri; SR until (User stops responding); return R; Proposition 2. [Complexity of the algorithm SRIR]: The Complexity of the algorithm SRIR is O(N), where N is the size of the database image set. 2.5. Experimental evaluation 2.5.1 Test environment The database used for the test is a subset of Corel. This set includes 3400 images. 2.5.3. Query implementation and evaluation To test the accuracy of the proposed method, all of 3400 images were used as queries. Average precision1 at 150 returned images are used to evaluate. In Table 2.2, f our different methods were implemented to compare including Basic C+, JF, MMRF and SRIR at 1, 4, 8, 12, 16, 20 feedback queries. Table 2.2. Result table of 4 methods according to the number of queries in one feedback. Precision according to the number of queries Method 1 query 4 query 8 query 12 query 16 query 20 query Basic C+ 0.20 0.22 0.23 0.24 0.245 0.25 JF 0.24 0.29 0.31 0.33 0.34 0.35 MMRF 0.243 0.31 0.315 0.323 0.334 0.365 SRIR 0.36490 0.39789 0.40035 0.40241 0.40360 0.40385 The experimental results are shown in Fig. 8. The horizontal axis indicates the number of clusters (can be 1, 4, 8, 12, 16, 20). The vertical axis indicates the precision. Four different methods including Basic C+ , JF, MMRF và SRIR are indicated by 4 curves We can make conclusions from Fig. 2.11. The system precision increases (the vertical axis) along with the rise of the horizontal axis (number of clusters). The more clusters we use to retrieve, the higher the system performance is. We also 14
found that the precision of SRIR method is better when the number of clusters between 1 and 8, specifically 54.73% at 1, 59.68% at 4 and 60.05% at 8. 0.45 0.4 0.35 Average accracy 0.3 0.25 Basic C+ 0.2 JF 0.15 MMRF 0.1 SRIR 0.05 0 1 4 8 12 16 20 Number of feedback queries Figure 2.11. Compare the accuracy of the four methods. In the SRIR method, the performance curve increases rapidly from 1 to 8 clusters and increase slowly in the range of 12 to 20 clusters because 8 clusters covered most of the clusters in the feature space. Although Jin & French method also increased rapidly in the range of 1 to 8 queries [49] our approach has much higher precision without increasing retrieval time. The main reason is that in our proposed method, although the number of clusters is between 1 and 8, our method takes advantage of semantic information from user feedback more than 8. 2.6. Conclusion of chapter 2 The thesis focused on proposing a method, called SRIR, to solve four main problems: (1) Use only one query to retrieve a variety of initialized results, including images in the entire feature space (reducing the burden on users in not having to select multiple query images); (2) Clustering related images with low time; (3) determine the semantic importance of each query (4) determine the importance of each feature. Our experimental results on the feature database consisting of 3400 images have shown that the proposed method SRIR offers a significantly higher precision when compared to the Basic C+, JF and MMRF method. 15
Chapter 3. AN EFFICIENT IMAGE RETRIEVAL METHOD USING ADAPTIVE WEIGHTS 3.1. Introduction Chapter 2 of the thesis presents the image retrieval method [CT5], which can retrieve semantic images spread in the entire feature space with high precision. However, this method has not solved two limitations: Firstly, it does not fully exploit feedback information (the relevance level of each image) to identify good query points. For example, Figure 3.1 is the general interface for existing systems. This interface shows us that users can only check the box at the top of the image (if the image is relevant) or uncheck it (If the image is irrelevant). While users rate the image with a higher ID pl_flower\84059 than the image with ID pl_flower\476083. Figure 3.1: Typical interface of CBIR system with relevant feedback. Second, the methods above consider the regions containing the different good query points to be equal and assign the same weight to all adjacent points of the good query. This is not appropriate because different regions often have separate attributes. Figure 3.2. Illustration of two equally well-queried regions. (a) Figure on the left: the first query point. (b) Figure on right: second query point. 16
Based on this observation, the thesis has proposed an image retrieval method through adaptive weight, named AWEIGH (An efficient image retrieval method using adaptive weights) [CT6]. In this method, instead of using the same weight vector for regions that contain different good query points, the method automatically calculates the good query points and the good weight vectors corresponding to the regions that contain the good query points based on user’s feedback. In addition, previous methods clustered all feedback images, thus the computational complexity of those methods will be high. To address this limitation, the proposed method only clustered feedback images in the first iteration (from the second iteration onwards, the method only adds feedback images to the clusters) (See section 2.3 of Chapter 2). As shown in Fig. 3.3, the main difference between our proposed method and the existing relevant feedback image retrieval methods lies in the three main components: (a) Determining the optimal query points (b) Computing the weight vectors; (c) Computing the improved distance functions. These components can be embedded in any relevant feedback image retrieval system, so we will describe each of these components separately. AWEIGHT Determining the good Initial Query query points Computing the weight Search Engine vectors Computing the improved Result set distance functions Relevant set Search Engine Result set Initial Cluster Relevant set Incremental Training set Cluster Figure 3.3. Diagram of the image retrieval system using adaptive weights. 17
3.2. The algorithm determines the good query point and the adaptive weight set of the improved distance function. In this section, the thesis presents the proposed technique for determining the optimal query point and the adaptive weights of the distance function. The technique determines the optimal query point and the adaptive weights according to a given cluster of images. In the case of multiple clusters, this technique is performed for each cluster. Given a cluster i (i=1,…,g), each image in the cluster i that is represented by with j=1… , matrix where denotes the number of images for ith cluster). Suppose the optimal query vector for cluster i is . Assume a user’s evaluation information in terms of relevancy for each (j=1,.., ) (where  2 , vector represents the user’s feedback of the relevance level of each image in cluster i . The problem of finding the optimal query point and the weight matrix is referred to the problem of minimizing penalties as follows: ∑ ( ) (3.1) Subject to: det( )=1 Where det( ) is the determinant of the matrix (to avoid the case is a zero matrix). To solve the minimization problem, we use the method of Lagrange multipliers - As a result,n an optimal query point : ∑ where (3.2) ∑ ∑ - If (C(i))-1 exists, the matrix weight matrix : C C (3.3) With C be the weighted covariance matrix of the images in the cluster i: ∑ ̅̅̅̅̅ ̅̅̅̅̅ (3.4) Since the optimal query vector and the weight matrix W, we have the distance function as: ( ) ( ) ( ) (3.5) Let Cpf ( ) be the list of points in the cluster of positive feedback samples corresponding to the optimal query point i ( i.e., the list of points in the corresponding ellipse. is the list of k points nearest to pi. C are the positive 18