# Understanding User's Intention in Semantic Based Image Retrieval: Combining Positive and Negative Examples

Meriem Korichi, Mohamed Lamine Kherfi, Mohamed Batouche, Zineb Kaoudja, Hadjer Bencheikh

<figure><img src="image_1.png" /></figure>

## To cite this version:

Meriem Korichi, Mohamed Lamine Kherfi, Mohamed Batouche, Zineb Kaoudja, Hadjer Bencheikh. Understanding User's Intention in Semantic Based Image Retrieval: Combining Positive and Negative Examples. 6th IFIP International Conference on Computational Intelligence and Its Applications (CIIA), May 2018, Oran, Algeria. pp.66-77, 10.1007/978-3-319-89743-1_7. hal-01913900

HAL Id: hal-01913900

https://inria.hal.science/hal-01913900

Submitted on 7 Nov 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Understanding user's intention in semantic
based image retrieval: combining positive and
negative examples

Meriem KORICHI¹, Mohamed Lamine KHERFI², Mohamed
BATOUCHE¹, Zineb KAOUDJA², Hadjer BENCHEIKH²

¹ Computer Science Department, University of Constantine 2 - Abdelhamid Mehri, Constantine 25 000, ALGERIA

²Department of Computer Science and Information Technology, University of Ouargla - Kasdi Merbah, Ouargla,30000, ALGERIA.

meriemkorichi@gmail.com, Mohammedlamine.Kherfi@uqtr.ca,
mcbatouche@gmail.com, zinebkaoudja@gmail.com, bencheikh1991@gmail.com

**Abstract.** Understanding user's intention is at the core of an effective images retrieval systems. It still a significant challenge for current sys- tems, especially in situations where user's needs are ambiguous. It is in this perspective that fits our study.

In this paper, we address the challenge of grasping user's intention in semantic based images retrieval. We propose an algorithm that performs a thorough analysis of the semantic concepts presented in user's query. The proposed algorithm is based on an ontology and takes into account the combination of positive and negative examples. The positive examples are used to perform generalization and the negative examples are used to perform specialization which considerably decrease the two fam- mous problems of image retrieval: noise and miss.

Our algorithm processed in two steps: in the first step, we deal only with the positive examples where we will generalize the query from the ex- plicit concepts to infer the others hidden concepts desired by the user. whereas the second step deal with the negative examples to refine results obtained in the first step. We created an image retrieval system based on the proposed algorithm. Experimental results show that our algorithm could well capture user's intention and improve significantly precision and recall.

**Key words:** Image retrieval, Grasping user's intention, Positive examples, Negative examples, Ontology.

# 1 Introduction

Image retrieval is a growing field. Recently, it has witnessed an explosion of personal and professional image collections especially with the development of new technologies that allow users share their images via internet. There was an urgent need for automatic tools that organizing these large quantities of images.
Such tools can help users to find the desired images within a reasonable time.
These tools are called image retrieval engines.

Image retrieval systems can be classified into two main categories: the first category called Content-Based Image Retrieval (CBIR). In this category, the user is generally asked to formulate a visual query (image for example) that correspond to what he is looking for. The research is performed by measuring similarities between the low levels features of the query and the images of the collection. Various visual features, including both global features[1-3] (e.g., color, texture, and shape) and local features (e.g., SIFT keypoints [4-6]) have been studied for CBIR.

The second category which exploits the semantic concepts associated with images is called Semantic-Based Image Retrieval : SBIR. The user formulates his/her query with textual terms that express his/her needs. In this case, the search is performed by comparing between these terms and textual annotations that represent the images in the collection by the use of semantic tools. Among the tools that are often used to represent the semantics, there are "ontologies"[7]. There is another secondary category where the user formulates his/ her query with visual example like CBIR but the research is carried out on the basis of the semantics associated with those images instead of the low levels features [8]. This category try to overcome the drawbacks of the two previous categories by avoiding user to identify keywords and letting the images speak for themselves. Whatever the category of the image retrieval system, Their main objective is to understand user's needs and answer him/her accurately. However, these needs may vary from one person to another, and even from a given user at different times; therefore, the success of an image retrieval system depends on how accurate the system understands the intention of the user when he/she formulates a query[9].

Creating the query is a difficult problem. It arises two important challenges for
both the user and the retrieval system[9]: Firstly, for the user the challenge is
how to express his/her needs accurately. Secondly, for the system the challenge
is how to understand what the user wants based on the query that he/she for-
mulated.

The difficulty in dealing with these two challenges lead to many problems in im-
age retrieval, such as noise and miss. Noise can be defined as the set of retrieved
images which do not correspond to what the user wants [10] whereas, miss is
the set of images corresponding to what the user wants which have not been
retrieved.

In this paper, our objective is to improve the efficiency of image retrieval by de-
crease noise and miss via understanding user's intention. We will be interested
by the systems of the last category where the user formulates a visual query
using images and the retrieval system exploits the semantic concepts associated
with these images.

We propose an algorithm that performs a thorough analysis of the semantic
concepts presented in the user's query. Our algorithm is processed in two steps:
in the first step, we will perform a generalization from the explicit concepts to
infer the other hidden concepts that the user can't express them which decrease the miss problem. In the second step, we ask user to select negative examples to refine results obtained in the first step. In this case the images similar to those of the negative examples will be rejected, which reduces the noise. At the same time, the rejected images are replaced by others correspond to what the user wants, so miss will be decrease also.

The rest of the paper is organized as follows: section 2 briefly reviews previous related work. section 3 present the principle of our algorithm, then, we will present our data and our working hypotheses in section 4. Section 5 details our algorithm. An experimental evaluation of the performance of our algorithm is presented in section 6. Finally, section 7 presents a conclusion and suggests some possibilities for future research.

## 2 Related works

User is at the centre of any image retrieval system. One of the primary challenges for these systems is to grasp user intent given the limited amount of data from the input query [11]. In order to solve this challenge, several methods has been proposed. One way is keyword expansion where the users original query is augmented by new concepts with a similar meaning to decrease the miss problem. Keyword expansion was implemented by different techniques. Some of them [12-14] are typically based on dictionaries, thesauri, or other similar knowledge models such as ontology. It is noted by many researchers that the use of an ontology for query expansion is advantageous especially if the query words are disambiguated [11][15]. Note that query expansion is very effective, provided that initial query perfectly matches the user's need [16]. However, this is not always the case, especially in situation where the user has a difficulty to express them. In this case, the extensions of the query can lead to more inappropriate results than the initial query because of irrelevant concepts which leads to significantly increase noise [17].

Another way to grasp user's intention is relevance feedback [18-21] and pseudo relevance feedback. In Relevance feedback technique, the user choose from the returned images those that he/she finds relevants (positive examples) and those that he/she finds not relevants (negative examples) then a query-specific similarity metric was learned from the selected examples.

In pseudo relevance feedback [22-23], the query is expanding by taking the top N images visually most similar to the query image as positive examples.

For many researchers[24-26], The task of learning concepts from user's query to understand his/her intent has seen as a supervised learning problem in which the classifiers search through a hypothesis space to find an adequate hypothesis that will make good predictions. Several algorithms of supervised learning were proposed[27-30] such as: Multi-Class Support Vector Machines (SVM), Nave Bayes Classifier, Maximum Entropy (MaxEnt) classifier, Multi-Layer Perceptron (MLP).
Recent search [26], proposed an ensembling multiple classifiers for detecting users intention instead of focusing on single classifiers.

This problem has an analogue in the cognitive sciences which called human generalization behavior and inductive inference.

Bayesian models of generalization [31-34] are models from cognitive science that focus on understanding the phenomena of how to generalize from few positive examples. They has been remarkably successful at explaining human generalization behavior in a wide range of domains [34], however their success is largely depend on the reliability of the initial query.

The main contribution of our work is to propose an algorithm to perform the challenge of grasping user's intention and consequently decrease miss and noise. Our algorithm refines the initial query formulated by the user to infer the relevant concepts. It uses an ontology and exploits its semantic richness which allowed us to extract the hidden concepts that the user could not express them explicitly. Then we can improve the obtained results through the relevance feedback with negative examples.

## 3 Principle of our algorithm

In medicine, doctors apply a characteristic rule to summarize the symptoms of a specific disease, whereas, to distinguish one disease from others, they apply a discrimination rule to summarize the symptoms that discriminate this disease from others. This principle is exactly what we will use in our algorithm to understand user's intention from a given query. We perform generalization using positive examples and specialization using negative examples. This principle is applied in content-based image retrieval [18] as follows:

- For positive examples, a concentrated characteristic is important and a scattered characteristic is not important.

- For positive and negative examples, a discriminated characteristic is important and a non-discriminated characteristic is not important.

We carry out a similar work with semantic concepts as follows:

1. For positive examples: with a query that contains several images:

(a) A concept which is salient in the majority of query's images is important.

(b) A concept that appears in some images and does not appear in the others, in this case, we cannot judge immediately that it is not important. However, it can be classified into three types:

i. Either, it has concepts that reinforces it in the other images via direct or indirect relationships (for example: apple - fruit - banana), and so it is important, or at least the common concept (here it is the ancestor Fruit) is important.
ii. Either it has concepts that contradicts it in the other images, directly or indirectly, and therefore it is not important.

iii. Either there is no concept that reinforces it or a concept that contradicts it in the other images, in this case, it can either be considered with moderate importance, or neglected.

2. For positive and negative examples:

(a) The common concepts between the two sets (positive and negative) are to be neglected. common concept mean either the same concept or concepts that have a positive relations between them as it is illustrated in the case of positive example only.

(b) Discriminant concepts (directly or indirectly through relationships) between the two sets are important. If the concept is present in the positive set, it must be sought; and if it is present in the negative set, it must be dismissed.

# 4 Data and hypothesis

## 4.1 Query formulation

We ask user to select from displayed images the maximum number of images that correspond to what he/she is looking for. It is the set of concepts that annotate the selected images that will constitute our initial query.

## 4.2 Ontology creation

Our algorithm use an ontology to exploit its semantic richness and apply the principle described above. We have chosen the domain of "nature" for our ontology. The first step of the ontology creation is to choose a collection of images representative of "Nature" domain. The ontology will then be used to annotate the images in this collection. Relationships in our ontology are classified into three categories:

1. Positive relationships (reinforcement relationship): means that the presence of such concept implies the presence of such other concept, for example: presence of concept "Dune" implies the presence of concept "Desert".

2. Negative relationships (contradiction relationships): means that the presence of such concept generally implies the absence of such other concept, for example: presence of the concept "Snow" implies the absence of concept "Desert".

3. Neutral relationships: means that the relations between concepts are null (ie neither positive nor negative)

The other steps of the ontology creation are the following:
1. Identify the different concepts presents in the images collection: for example: desert, camel, dune, snow,..etc

2. Calculate the implications weights between concepts that illustrate the degree of semantic correlation between these concepts.

For each concept, the probability of having the other concepts was calculated as follows:

$$P(A|B) = \frac{P(A \cap B)}{P(B)}$$

Where $P(A | B)$ means the probability of having a concept A knowing that we are in the presence of the concept B.

Because our challenge is not the ontology creation, we have calculated this probability manually. Firstly, we started the search with the concept B using the retrieval engine "Google". The obtained images represent $P(B)$. In this collection, we calculate the number of images that represents the concept A which gives us $P(A \cap B)$.

3. Represent the ontology by a value oriented graph where concepts represent the nodes and the arcs are the semantic relationships. Our graph can be seen as a probabilistic graph.

4. Represent the relationships between concepts with a relevance matrix. This latter is a square matrix whose lines and columns are concepts and the value in box M [i, j] represents the probability of the relation between the concept i and the concept j.

A weight between two concepts models a type of semantic relationship between them.

* The weights with the value 0: mean that the two concepts can never be found in the same image so this weight models a negative relationship;

* [0,01, 0, 49]: meant that there are times when the two concepts can be found in the same image and sometimes it cannot be found. Which models a neutral relationship;

* [0.5, 1]: means that the two concepts are often found in the same image so this weight models a positive relationship.

# 5 Our algorithm

Our algorithm is processed in two steps. We called the first step: "Generalization algorithm" (see Algorithm 1)and the second step "Specialization algorithm(see Algorithm 2))

# 6 Experimental evaluation

## 6.1 Images collection

To be able to apply our algorithm, we need an ontology and an images collection annotated with the concepts of this ontology. We have chosen the domain
of "nature" for our ontology. Then, we have used Google images as an image
retrieval engine to collect images for each concept in the ontology. The top 200
returned images of each query are crawled and manually labeled to construct
the experimental data set.

6.2 Experiments

We implemented an image retrieval system that integrate our algorithm. We invited thirty users to participate in our experiments. We displayed them a set of images randomly selected from the images collection. Users can ask to see more images if the presented images do not reflect to what they wants.

To evaluate the performance of our algorithm, we carried out a comparison between: our algorithm, the Bayesian model of generalization used in [34] and the standard matching method (without generalization). As performance criteria, we use the precision and the recall measures.

**First experiment** The aim of this experiment is to evaluate the effectiveness of the first step of our algorithm (Generalization algorithm) to increase recall compared to the Bayesian model of generalization used in [34] and the standard matching method (without generalization). We asked users to make different queries, and then we calculated the recall of the three models. Fig.2 illustrate the obtained results from 16 queries.

We can see that the recall is considerably increased with our approach and

<figure><img src="image_3.png" /><figcaption>Fig. 1. The recall of the three models</figcaption></figure>

then consequently the miss problem is decreased. Compared to our algorithm,
the success of the Bayesian model of generalization is largely depend on the
reliability of the examples present in the query to good reflect the user's intention which is not always the case because sometimes the images of the query may composed of many objects, however the user is interest only with some of them. Our algorithm overcomes this problem by refining the initial query of the user.

**Second experiment** The aim of this experiment is to illustrate the effect of the negative examples to decrease noise by improving the accuracy. We asked users to formulate queries using the Generalization algorithm and we calculated the accuracy then we asked him to select negative images and restart the search. the obtained results are illustrated in Fig.3.

It is clear that the use of negative examples increase the accuracy. Indeed, after

<figure><img src="image_4.png" /><figcaption>Fig. 2. The effect of negative examples to increase accuracy.</figcaption></figure>

obtaining the results of a given query, the user can keep the positive images and enrich the query by including some undesired images as a negative examples. This implies that images similar to those of the negative example will be rejected, which reduces the noise. At the same time, the rejected images are replaced by others corresponding to what the user wants, so silence will be diminished.

# 7 Conclusion

In this paper, we proposed an algorithm that process in two steps: we called the first step "Generalization algorithm" and the second step "specialization
algorithm”. The objective of this algorithm is to improve the semantic image
retrieval quality by reducing the famous problems of image retrieval: noise and
miss via understanding user’s intention. Our algorithm is based on the use of
an ontology which allows us to exploits it’s semantic richness. We implemented
an image retrieval system that integrate the proposed algorithm. Experimental
evaluation verify the efficiency of our approach in comparison to the others
proposed in the state-of-the-art. We have shown that the combination of positive
and negative examples improve significantly precision and recall. The perspective
of our work is to automate the ontology creation.

References

1. D. G. Lowe. Object recognition from local scale-invariant features. IEEE ICCV, 1999.

2. A. Torralba, K. Murphy, W. Freeman, and M. Rubin, Context-Based Vision System for Place and Object Recognition, Proc. IntlConf. Computer Vision, 2003.

3. N. Dalal and B. Triggs, Histograms of Oriented Gradients for Human Detection, Proc. IEEE Intl Conf. Computer Vision and Pattern Recognition, 2005.

4. D. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, Intl J. Computer Vision, vol. 60, no. 2, pp. 91-110, 2004.

5. C. Celik and H. S. Bilge, Content based image retrieval with sparse representations and local feature descriptors: A comparative study, Pattern Recognit., vol. 68, pp. 113, 2017.

6. M. Guillaumin, T. Mensink, J. Verbeek, and C. Schmid. Tagprop: Discriminative metric learning in nearest neighbor models for image auto-annotation. IEEE ICCV, pages 309316, 2009

7. Liaqat, M., Khan, S.Majid, M. (2017). Image retrieval based on fuzzy ontology. Multimedia Tools and Applications.

8. N. Rasiwasia, P. J. Moreno, and N. Vasconcelos, Bridging the gap: Query by semantic example, IEEE Trans. Multimed., vol. 9, no. 5, pp. 923938, 2007

9. Mohammed Lamine Kherfi. Review of Human-Computer Interaction Issues in Image Retrieval, Advances in Human Computer Interaction, Shane Pinder (Ed.), In-Tech, DOI: 10.5772/5929 [2008].

10. Kherfi, M. L., Ziou, D.Bernardi, A. Combining positive and negative examples in relevance feedback for content-based image retrieval. Journal of Visual Communication and Image Representation, 14(4), 428457.2003

11. Xiaoou Tang, Ke Liu, Jingyu Cui, Fang Wen, Xiaogang Wang. IntentSearch:Capturing user intention for one-click internet image search, IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 34, NO. 7, JULY 2012

12. ] BILOTTI, M., KATZ, B., AND LIN, J. 2004. What works better for question answering: Stemming or morphological query expansion? In Proceedings of the Information Retrieval for Question Answering (IR4QA) Workshop at SIGIR04.

13. NAVIGLI, R. 2009. Word sense disambiguation: A survey. ACM Comput. Surv. 41, 2, 169.

14. A. Azizan, Z. A. Bakar, and S. A. Noah, Analysis of retrieval result on ontology-based query reformulation, I4CT 2014 - 1st Int. Conf. Comput. Commun. Control Technol. Proc., no. I4ct, pp. 244248, 2014.
15. Z.-J. Zha, L. Yang, T. Mei, M. Wang, and Z. Wang, Visual query suggestion, Proc. seventeen ACM Int. Conf. Multimed. - MM 09, vol. 6, no. 3, p. 15, 2009

16. R. Fergus, P. Perona, and A. Zisserman, A Visual Category Filter for Google Images, Proc. European Conf. Computer Vision, 2004.

17. G. Park, Y. Baek, and H. Lee, Majority Based Ranking Approach in Web Image Retrieval, Proc. Second Intl Conf. Image and Video Retrieval, 2003.

18. M. L. Kherfi, D. Ziou, and A. Bernardi, Combining positive and negative examples in relevance feedback for content-based image retrieval, J. Vis. Commun. Image Represent., vol. 14, no. 4, pp. 428457, 2003.

19. J. Deng, A.C. Berg, and L. Fei-Fei, Hierarchical Semantic Indexing for Large Scale Image Retrieval, Proc. IEEE Intl Conf. Computer Vision and Pattern Recognition, 2011.

20. Glowacka and J. Shawe-taylor, Image Retrieval with a Bayesian Model of Relevance Feedback. 2016

21. D. Tao, X. Tang, X. Li, and X. Wu, Asymmetric Bagging and Random Subspace for Support Vector Machines-Based Relevance.

22. M. Torjmen, K. Pinel-Sauvagnat, and M. Boughanem, Using Pseudo-relevance feedback to improve image retrieval results, Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 5152 LNCS, pp. 665673, 2008.

23. R. Yan, E. Hauptmann, and R. Jin, Multimedia Search with Pseudo-Relevance Feedback, Proc. Intl Conf. Image and Video Retrieval, 2003.

24. In-Ho Kang and GilChang Kim. Query type classification for web document retrieval. In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval, SIGIR 03, pages 6471, New York, NY, USA, 2003. ACM.

25. Uichin Lee, Zhenyu Liu, and Junhoo Cho. Automatic identification of user goals in web search. In Proceedings of the 14th International Conference on World Wide Web, WWW 05, pages 391400, New York, NY, USA, 2005. ACM.

26. A. Figueroa and J. Atkinson, Ensembling Classifiers for Detecting User Intentions behind Web Queries, IEEE Internet Comput., vol. 20, no. 2, pp. 816, 2016.

27. K Krammer and Y Singer. On the algorithmic implementation of multi-class svms. Proc. of JMLR, 2001.

28. C.-W. Hsu and C.-J. Lin, A comparison of methods for multiclass support vector machines, IEEE Trans. Neural Networks, vol. 13, no. 2, pp. 415425, 2002.

29. K. Nigam, J. Lafferty, and A. Mccallum, Using Maximum Entropy for Text Classification.

30. G. M. Foody, Hard and soft classifications by a neural network with a non-exhaustively defined set of classes, Int. J. Remote Sens., vol. 23, no. 18, pp. 38533864, 2002.

31. J. B. Tenenbaum and T. L. Griffiths, Generalization, similarity, and Bayesian inference, BEHAVIORAL AND BRAIN SCIENCES. pp. 629630, 2001.

32. J. B. Tenenbaum and F. Xu, Word learning as Bayesian inference, Proc. Twenty-Second Annu. Conf. Cogn. Sci. Soc., 2000.

33. J. Abbott, Constructing a hypothesis space from the Web for large-scale Bayesian word learning, Proc., pp. 5459, 2012.

34. Y. Jia, J. Abbott, J. L. Austerweil, T. L. Griffiths, and T. Darrell, Visual Concept Learning: Combining Machine Vision and Bayesian Generalization on Concept Hierarchies, Adv. Neural Inf. Process. Syst. 27 (NIPS 2013), vol. 1, no. 1, pp. 19, 2013.
**Algorithm 1 Generalization**

**Background:** a set of annotated images D

**Preprocess:** Extract the list of semantic concepts (LCpt) that annotate the positive examples

**Input:** list of concept LCpt =C1, C2, .Cn, relevance matrix M, ontology G

**Output:** L1 list of relevant concepts ( explicit and hidden)

**for all** C ∈ LCpt **do**

compute weight (C): the number of occurrences of C in Q

compute P(C) with

W ← weight (C)

NB ← Number of images in Q

$$P(C) = \frac{W}{NB}$$

**if** P(C) ≥ 0.5 **then**

add (C) to L1 ( the list of accepted concepts)

**else**

add (C) to L2 (the list of concepts to be verified)

**end if**

**end for**

**for all** C1 ∈ L2 **do**

**for all** C2 ∈ LCpt **and** C1 ≠ C2 **do**

Sum = Sum + M[C1,C2]

$$Avg = \frac{Sum}{length(LCpt) - 1}$$

**if** Avg ≥ 0.5 **then**

add (C1) to L1

**end if**

**end for**

**end for**

**for all** C1 ∈ LCpt **do**

**for all** C2 ∈ G **do**

**if** M[C1,C2] ≥ 0.5 **then**

add (C2) to Hid (the list of hidden concepts)

**end if**

**end for**

**end for**

**for all** C ∈ Hid **do**

compute wgt (C):the number of occurrences of C in Hid

compute Moy(C) with

Wh ← wgt (C)

Nb ← length (LCpt)

$$Moy(C) = \frac{Wh}{Nb}$$

**if** Moy(C) ≥ 0.5 **then**

add (C) to L1

**end if**

**end for**
**Algorithm 2** Specialization

**Background:** a set of an annotated images D (search results using L1 as query)

**Preprocess:** Extract the list of semantic concepts (LNE) that annotate the negative examples

**Input:** list of relevant concepts L1, list of negative concepts LNE, relevance matrix M, ontology G

**Output:** L3 list of undesired concepts.

Apply the Generalization algorithm to the list LNE, as results we obtain a an initial list of undesired concepts (L3).

**for all** C ∈ L1 **do**

**if** C ∈ L3 **then**

delete C from L3

**end if**

**end for**

**for all** Ci ∈ L3 **do**

**for all** Cj ∈ L1 **do**

Som = Som + M[Ci,Cj]

$$Moyn = \frac{Som}{length(L1)}$$

**if** Moyn ≥ 0.5 **then**

delete Ci from L3

**end if**

**end for**

**end for**

Display results by deleting all images where the concepts of l3 are appeared