Navigation Pattern Based Relevance Feedback Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Now a day textual based image search become old fashion. So image search has gained an intense popularity. Searching or retrieving image based on its content is called content based image retrieval. There are various methods so far implemented and all of these methods are also support by feedback system from the user to fine tune the search results. But previous methods have some limitation so these methods are impractical away for real applications. Thus this work proposes a new user navigation pattern based feedback system to support content based image retrieval.

Keywords: Content-based image retrieval, relevance feedback, query point movement, query expansion, navigation pattern mining

1 Introduction

In content-based image search, the goal is to retrieve the most similar images to a query image introduced to the system. Due to the complexity of multimedia contents, understanding of image is difficult. Extracting valuable knowledge from a large-scale multimedia repository, so-called multimedia mining is also difficult. Typically, in the development of an image requisition system, semantic image retrieval relies heavily on the related captions, e.g., file-names, categories, annotated keywords, and other manual descriptions. Unfortunately, this kind of textual-based image retrieval always suffers from two problems: high-priced manual annotation and inappropriate automated annotation. On one hand, high-priced manual annotation cost is prohibitive in coping with a large-scale dataset. On the other hand, inappropriate automated annotation yields the distorted results for semantic image retrieval. As a result, a number of powerful image retrieval algorithms have been proposed to deal with such problems over the past few years. Content-Based Image0Retrieval (CBIR) is the mainstay of current image retrieval systems. In general, the purpose of CBIR is to present an image conceptually, with a set of low-level visual features such as color, texture, and shape. These conventional approaches for image retrieval are based on the computation of the similarity between the user's query and images via a query by example (QBE) system [5]. Despite the power of the search strategies, it is very difficult to optimize the retrieval quality of CBIR within only one query process. To solve such problems, in the QBE system, the users can pick up some preferred images to refine the image explorations iteratively. The feedback procedure,

Called Relevance Feedback (RF), repeats until the user is satisfied with the retrieval results. Although a number of RF studies [5] have been made on interactive CBIR. These approaches also have some common problems, namely redundant browsing and exploration convergence. First, in terms of redundant browsing, most existing RF methods focus on how to earn the user's satisfaction in one query process. That is, existing methods refine the query again and again by analyzing the specific relevant images picked up by the users. Especially for the compound and complex images, the users might go through a long series of feedbacks to obtain the desired images using current RF approaches. In fact, it is not practical in real applications like online image retrieval in a large-scale image database. Fig. 1 illustrates the problem of exploration convergence. In Fig. 1, suppose that two users query with the same image whose concept consists of ―"car and ―sunset". In this example, however, the aimed concept for Query 1 and Query 2 is ―"car" and ―"sunset", respectively. After a set of feedbacks for Query 1 and Query 2, two different moving paths will be produced since they will lead to images of aimed concepts, respectively. This problem is called as visual diversity. In this case, if the compound concept to aim at consists of car, sunset, and sunset and car, it is not easy for traditional CBIR methods to capture the user's intention. For query point movement, this problem will result in that the features would converge toward the specific point in the feature space during the query session.

Figure 1: Example for the Problem of Exploration Convergence

Hence, it is still hard to cover the concepts of car, sunset, and sunset car even by performing the weighted K-Nearest Neighbors search To resolve the problems, a novel method named based Navigation Patterns for efficient Relevance Feedback is used to achieve the high retrieval quality of CBIR with RF by using the discovered based navigation patterns. According to the discovered patterns, the users can obtain a set of relevant images in an online query refinement process. Thus, the problem of redundant browsing is successfully solved. In terms of effectiveness, navigation-pattern-based search algorithm (NPRF Search) merges three query refinement strategies, including Query Point Movement (QPM), Query Reweighting (QR), and Query Expansion (QEX), to deal with the problem of exploration convergence.


To avoid the problem of redundant browsing and problem exploration following strategic are given.

2.1 Query Reweighting

The notion behind QR is that, if the ith feature fi exists in positive examples frequently, the system assigns the higher degree to fi. QR allow to user to submit image query to refine his/her search through set of relevance feedback. In this work, the feature weights are dynamically updated to connect low-level visual features and high-level human concepts. NNEW learns the user's query from positive and negative examples by weighting the important features. For this kind of approach, no matter how the weighted or generalized distance function is adapted, the diverse visual features extremely limit the effort of image retrieval.

2.2 Query Point Movement

Another solution for enhancing the accuracy of image retrieval is moving the query point toward the contour of the user's preference in feature space. QPM regards multiple positive examples as a new query point at each feedback. After several forceful changes of location and contour, the query point should be close to a convex region of the user's interest. One of the QPM approaches is the modified version of MARS [4

2.3 Query Expansion

The technique QR and QPM cannot overcome the drawback in traditional CBIR method so QEX is used. For this reason, the modified version of MARS [4] groups the similar relevant points into several 62 clusters, and selects good representative points from these clusters to construct the multipoint query. Q cluster [2] intends to handle the disjunctive queries by employing adaptive classification and cluster merging methods. The effectiveness of QEX is better than those of QPM and QR. QEX brings out higher computation cost and more feedbacks in RF.

2.4 Hybrid RF

Another type of RF approach emphasizes the integration of various search strategies. One of the hybrid RF strategies is IRRL. IRRL [5] addresses the important empirical question of how to precisely capture the user's interest at each feedback. In IRRL, exploiting knowledge from the long-term experience of users can facilitate the selection of multiple RF techniques to get the best results. The derived problems from IRRL are: the selection of optimal RF technique cannot avoid the overhead of long iterations of feedback. Also, the visual diversity existing in the global feature space cannot be resolved with an optimal RF technique alone.


3.1 Problem Definition

Extracting multimedia data from the large multimedia repository suffer from problem such as redundant browsing and exploration convergence. Whenever the user query the database the resultant data is irrelevant with the user's query and it takes long iterations of feedback to produce the result. The goal is to assist the search strategy in efficiently hunting the desired images.

3.2Overview of NPRF NPRF integrates the discovered navigation patterns and three RF techniques to achieve efficient and effective exploration of images as shown in Fig.2. The task is divided into two major operations, offline knowledge discovery and online image retrieval.

3.2.1 Online image retrieval Initial Query Processing Phase: Without considering the feature weight, this phase extracts the visual features from the original query image to find the similar images. Afterward, the good examples (also called positive examples) picked up by the user are further analyzed at the first feedback (also called iteration 0).

Image Search Phase: Behind the search phase, extend the one search point to multiple search points by integrating the navigation patterns and the proposed search algorithm NPRF Search. In this phase, a new query point at each feedback is generated by the preceding positive examples. Then, the nearest images to the new query point can be found by expanding the weighted query. The search procedure does not stop unless the user is satisfied with the retrieval result.

3.2.2 Offline Knowledge Discovery: Knowledge Discovery Phase : Learning from users' behaviors in image retrieval can be viewed as one type of knowledge discovery. Consequently, this phase primarily concerns the construction of the navigation model by discovering the implicit navigation patterns from users' browsing behaviors. This navigation model can provide image search with a good support to predict optimal image browsing paths.

Data Storage Phase: The databases in this phase can be regarded as the knowledge marts of a knowledge warehouse, which store integrated, time variant, and nonvolatile collection of useful data including images, navigation patterns, log files, and image features. The knowledge warehouse is very helpful to improve the quality of image retrieva

3.3.1 Offline Knowledge Discovery: Web image retrieval, the user has to submit a query term to the search engine, so-called textual-based image search. Then the user can obtain a set of most relevant web images according to the metadata or the browsing log. However, if the result does not satisfy the user, the query refinement can be easily incorporated into the query procedure. The usage log of CBIR suffers mainly on how to generate and utilize the discovered patterns. The data structure can be viewed as a hierarchy, including positive images, query points, and clusters. A query session contains a set of iterative feedbacks (iterations), which is referred to a navigation path. At each feedback, the positive examples, which indicate the results picked up by the user, are used to derive a referred visual query point by averaging the positive visual features. Finally, the query sessions, iterations, positive examples, and visual query points are stored .If the original log data are ready; the next task is to discover navigation patterns from the original log data. For navigation patterns mining, the frequent item sets are mined from navigation-transaction table. The transformed log table is also divided into several sub tables.

3.3.1 Data Transformation Data Transformation simplifies both the description of visual query points and the discovery of navigation patterns. Without data transformation, all positive images of each query session in the database are considered. If all positive images The aim of data transformation is to generate Query Point Dictionary (QPD) to reduce the kinds of items on the transaction list. In this phase, the transformed log are considered for navigation pattern mining, too many items make the frequent item sets hard to find. Also, the mining cost is expensive. table is first generated by the logged query sessions containing query session id, iteration number, positive images, and visual query point number. Once a query point is projected onto the QPD, the referred item number is stored into the transform log table. The transformed log table has to be partitioned into three tables for various needs, including QP table, Navigation-transaction table, and Partitioned Log table. Navigation-transaction table is used for navigation patterns mining.

Fig.2. Example of navigation pattern trees.

3.3.2 Navigation Pattern Mining

This stage focuses on the discovery of relations among the users' browsing behaviors on RF. In this SVM Based NPRF approach, the users' common interests can be represented by the discovered frequent patterns (also called frequent item sets). Through these navigation patterns, the user's intention can be precisely captured .The task is decomposed into two steps:

Step 1: Construction of the navigation transaction table. To exploit valuable navigation patterns, all query sessions in the transformed log table are collected as the navigation transaction table.

Step 2: Generation of navigation patterns. This operation concentrates on mining valuable navigation patterns to facilitate online image retrieval.


Fig. 3. Procedure for offline knowledge discovery.

3.3.3 Pattern Indexing

In this stage, build the navigation pattern tree with the discovered navigation patterns. As shown in Fig.3, the navigation patterns can be regarded as the branches of the navigation pattern tree. Once the navigation patterns are generated, the query item in each navigation pattern is used as a seed (called query seed) to plant the navigation pattern tree. A tree contains a number of navigation paths, and each node of the paths stands for an item consisting of several visual query points. A visual query point indicates a set of positive images. Based on the navigation pattern tree, the desired images can be captured without repeating the scan of the

The iterative search procedure can be decomposed into several steps as follows:

1. Generate a new query point by averaging the visual-features of positive examples.

2. Find the matching navigation pattern trees by determining the nearest query seeds (root).

3. Find the nearest leaf nodes (terminations of a path) from the matching navigation pattern trees.

4. Find the top s relevant visual query points from the set of the nearest leaf nodes.

5. Finally, the top k relevant images are returned to the user.


After implementing the project the query logs can be obtained by performing query point movement. Navigation patterns are obtained by using the pattern discovery mechanism. The knowledge discovered from the navigation patterns can be enhanced once the query is submitted to NPRF. To analyze the effectiveness of the proposed approach, two major criteria, namely precision and coverage, are used to measure the related experimental evaluations. They are defined as


where correct is the positive image set to the query image at each feedback, retrieved is the resulting image set exploited by the proposed approach at each feedback, ac_correct is the union set of all correct during a query session, and relevant is the ground truth. The criterion precision delivers the ability for hunting the desired images in user's mind and the coverage represents the ability for finding the accumulated positive images in a query session.

TABLE 1 : The Experimental Parameter Settings

In fig.3 the first parameter we concerned is the number of clusters cl .fig reveals that the precision slightly degrades as the number of clusters increases

In fig 4 ,The second parameter we tested is the number of logs and Fig. depicts that, the larger the number of logs, the higher the average precision and the higher the retrieval cost

Fig.4 The average precisions of different clusters for data set

Fig.5 The average precisions of different numbers of log-transaction for data set


In this dissertation , proposed a relevance feedback technique based on NPRF (navigation-pattern based relevance feedback) approach for Speedup the ordinal correlation measure. On one hand, the navigation patterns derived from the users' long- term browsing behaviors are used as a good support for minimizing the number of user feedbacks. Within a very short term of relevance feedback, the navigation patterns can assist the users in obtaining the global optimal results and bring out more accurate results than other well-known approaches. As a result, traditional problems such as visual diversity and exploration convergence are solved. In addition, the involved methods for special data partition and pattern pruning also speed up the image exploration. The experimental results reveal that the proposed approach NPRF is very effective in terms of precision and coverage. Within a very short term of relevance feedback, the navigation patterns can assist the users in obtaining the global optimal results.