This paper handles with two main challenges: retrieving the best matching images to a given query and improving diversity in ranking using fuzzy logic. The proposed scheme proceeds as follows: First, an off line module is performed before starting the image retrieval process in order to reduce both, the execution time and the algorithm complexity. This module contains an inter-images semantic similarity graph and an inter-images visual similarity graph. Second, an on-line part implies the relevance-based ranking, the diversity-based ranking and their combination. We deal with the redundancy problem using fuzzy logic. Moreover, the vector of the relevance scores and the vector of the diversity scores are joined in order to have final scores of each image according to a given query. The experiments are conducted on ImageCLEF12 benchmark for the Personal Photo Retrieval task and show satisfying results.
Our group REGIMvid within REGIM laboratory research participates in the
Personal Photo Retrieval task [
cess and to better organize the images in. The on-line part of the algorithm implies the following steps: First, the relevance-based ranking is the basic part of the process, in which we fix the image semantic similarity scores according to a given query. Second, the diversity-based ranking is a refinement’s process, in which we attribute a diversity score for each image according to its relations with other images from the collection while respecting its position in the rank list. Finally, both of these scores are combined.
The rest of the paper is organized as follows. Section 2 details our proposed relevance and diversity-based approach. Section 3 discusses the experimental results. 2
Relevance computing in our approach implies three phases. First, a matching process is performed basing on concepts from the query and the image data. Second, we compute the diversity scores. Finally, we establish the combination.
The following notations will be used. Given a set of query concepts = { , ,.., }, we denote by = { , ,.., } the collection of images that are associated with the set of query concepts . This collection is a part of the large collection .
Giving an image , we denote by = { , ,.., } the set of its associated
concepts [
, where denotes the relevance with respect to the set of query concepts . (1) Relevance score reflects the degree of the existence of a given concept in the image . This score is normalized that we range it from 0 to 1. 2.1
Based on experimental semantic similarity measures study, we decide to adopt an approach for semantic similarity between a given query and an image that is analogous in term of Cosine similarity measure. The semantic similarity between and , which are respectively the sets of query concepts and image concepts, is defined as:
This semantic similarity is computed between the query set of concepts and each concept sets of images that belong to the sub-collection relative to this query. For other images belonging to , their similarity scores are evidently equal to zero.
We denote by the vector of semantic similarity between a query and the collection . It is defined as follows: This vector supposed be used as an input for refinement phase is provided thanks to an inter-images semantic similarity based random walk with restart. However, we note that when we use random walk with the collections, which present redundant images, we risk decreasing the diversity. In fact, it supposes that images, which are similar, have generally the same relevance scores. As consequence, in a first step, we use inter-images relationship to get closer the similar images and in a second, we want to separate them. Therefore, we have ignored the random walk. 2.2
To satisfy more the user, results should be not only relevant but also diverse. Therefore, the final scores are the combination of relevance scores and diversity scores. In fact, relevance scores, which are computed as mentioned in the previous section, serve not only for the combination but they are the input for the diversity-based algorithm that when we have two related images, we should put the most relevant and neglect the other. So if we verify the diversity characteristic while considering the order, the most relevant will be selected the first and after, when we come to verify the other, we discover that they are similar and we class it at the end without doubt that it can be more relevant than the other.
Indeed, we attempt to give higher scores to diverse images. Thanks to the
greedy [
The greedy algorithm works in phases. At each phase, we take the best we can get right now, without regard for future consequences. Moreover, we hope that by choosing a local optimum at each step, we will end up at a global optimum. This strategy incrementally builds a more diverse set of results from the existing result set.
The greedy algorithm seeks to provide a more efficient approach to improve diversity by using a specific condition to guide the construction of a result set in an incremental fashion. During each iteration, the remaining images are ordered according to their diversity degree. The images are chosen according to the order in relevance based ranking list. In other words, the first image to be selected is always the one with the highest similarity to the query. Moreover, we will verify if this selected image is the one with the highest diversity degree with respect to the set of images selected during the previous iteration.
The following figure shows the greedy search algorithm procedure for image ranking: Hence, greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most evident and immediate benefit. Indeed, we just rank all images and keep the diverse ones in the top of the list. Therefore, it is a permutation problem, in which users will not miss information.
Diversity can have more than unique definition. In fact it can be solution for ambiguity, uncertainty, redundancy and vagueness which are usually present in the image content, the user query and the similarity measures. Indeed, it is a source of novelty and optimal understanding of the query that results will be different from each other.
To model these constraints, we make appeal to the fuzzy logic [
correct image retrieval, extracting the information with fuzzy logic would be
more natural [
We search to be more practical in dealing with diversity intention. For giving high score to an image for a given query, it must be not redundant comparing to others ranked before it.
Diversity refers to no redundancy. Therefore, we define diversity score of an image as its minimal difference with the images appearing before it for a given query. It must be visually far from each image ranked before it. In other words, there are no images having higher relevance scores, similar to this image. In fact, scores reflecting the redundancy of an image are computed tanks to the inter-images visual similarity graph representing the collection. Another factor can have an impact on the quality of the diversity-based ranking that the collection contains an image, which has low relevance score but which is highly semantically dissimilar from all other images in this collection.
As a consequent, it will necessarily have a high diversity score that will make wrong the final score. Therefore, we must include another intermediary score. Based on the inter-images semantic similarity graph, this score should reflect the degree of homogeneity of this image with all images in the collection.
The following graph illustrates an example of semantic similarities
between some images extracted from a collection from ImageCLEF 2012.
For optimal diversity, scores take into account these two factors, which are
redundancy and prevalence. In fact, we verify the situation of this image not
only according to images ranked before it but also in relation with the whole
collection. The used connective to combine rules is the logical disjunction
taken from the Lukasiewicz logic [
In order to balance between the relevance and the diversity user’s needs, the final ranking list is obtained after combining the relevance score and diversity score of an image for given query. As a final stage, the combination between relevance-based ranking scores and diversity-based ranking scores is a decisive phase. In fact, we have thinking a lot about the balancing manner especially about the importance that we should give to one factor at the
expense of the other. We consider that diversity requirement has the same degree of importance that has relevance necessity. As a result, global score not only reflects the similarity between the query and the image collection but also respects some specificity in queries like image redundancy constraint. 3
We describe the experimental study conducted to evaluate the proposed approach within the relevance computing and the diversity enhancement. The relevance and diversity-based approach for image retrieval is evaluated with the Personal photo task1, in which the challenge is to overcome the redundancy problem.
The submitted runs are inspired from our proposed approach described above that for a run, we use only the redundancy factor (run1), for another we add the prevalence factor (run 4) and a baseline run using only relevance constraint (run5). Moreover, we try our two proposed graphs, the semantic graph and the visual one, in calculating these two factors previously mentioned.
We notice that the forth run, which represents the complete proposed
approach has the best result but with restricted difference. In fact, the used
diversity strategy, which is proposed by [
In addition, our results concerning this task revel better in P_5, P_10, P_15 and P_20 than in P_30 and P_100, which is explained by the use of the greedy search algorithm. In fact, we think that user need diversity in the top 1 http://www.imageclef.org/2012/personal
of the list and prefer to keep the other images judged no diverse in the rest of the list. Diversity-based ranking proved its necessity in eliminating redundancy within the Retrieval of visual concepts task with our five submitted runs. Furthermore, the proposed approach shows acceptable results with the Retrieval of events task. Comparing with the results achieved for the Retrieval of visual concepts task, we notice a notable degradation, which can be explained that our proposed approach is designed for image retrieval whereas event retrieval is closer to shot detection. 4
In this interesting participation in ImageCLEF, we propose an approach, which improves diversity in ranking using fuzzy logic. The proposed scheme proceeds as follow: First, an off line module was performed before starting the image retrieval process in order to reduce both, the execution time and the algorithm complexity. This module contains an inter-images semantic similarity graph and inter-images visual similarity graph. Second, an on-line part implies the relevance-based ranking, the diversity-based ranking and their combination. Thanks to fuzzy logic, we deal with the redundancy problem. Moreover, the vector of the relevance scores and the vector of the diversity scores are joined in order to have final scores of each image according to a given query. The experiments are conducted on ImageCLEF12 benchmark for the Personal Photo Retrieval task and show good results.