Stéphane Bissol
email: bissol@imag.fr

Philippe Mulhem
email: mulhem@imag.fr

Yves Chiaramella

Towards Personalized Image Retrieval

This paper describes an approach to personalized image indexing and retrieval. To tackle the issue of subjectivity in Content-Based Image Retrieval (CBIR), users can define their own indexing vocabulary and make the system learn it. These indexing concepts may be both local (objects) and global (image categories). The system guides the user in the selection of relevant training examples. Concept learning in the system is incremental and hierarchical: global concepts are built upon local concepts as well as low-level features. Similarity measures tuning is used to emphasize relevant features for a given concept. To illustrate the potential of this approach, an implementation of this model has been developed; preliminary results are given in this paper.

Introduction

Unorganized collections of documents often lead to time consuming or deficient retrieval. Owning thousands of documents looses its purpose if those cannot be retrieved properly. This is particularly justified regarding the digital images field. Thanks to technological breakthroughs in the digitization, storage and accessibility domains, users may personally possess several thousands of digital images [START_REF] Rodden | How do People Manage Their Digital Photographs?[END_REF]. Among them, rare are those who actually organize their collection into a set of easily retrievable photographs. Each image becomes thus less reachable as the collection grows. In order to make each image retrievable, a set of images must be in some way indexed. Manual indexing is generally inappropriate, requiring too much time and effort. On the other hand (and unlike textual documents), an image semantic content cannot be accessed straightforwardly. Therefore automatic indexing implies, somehow, the decryption of the information hidden in the image pixels. Automatic indexing systems already exist that are able to associate symbolic information to images (like the objects they contain or the category they belong to). However, in those systems, symbolic terms used for indexing are arbitrarily chosen by the designers and may no suit the way users search for their images. The reason is that describing an image is known to be a highly subjective task [START_REF] John | Content-based Image Retrieval[END_REF].

This paper describes an automatic indexing system for any type of consistent image database. It allows users to define their own indexing terms progressively and in accordance to their specific needs, be they global (image categories) or local (objects present in the image). Low-level features (as colors and textures) underlying the labeling are hidden from the user when building mid-level features (objects contained in the image such as "Sky", "person" or "Foliage"). In the same fashion, low and mid-level features are implicitly manipulated when learning image categories. The system uses instance-based learning and similarity measure fitting to learn from user interactions. The advantages of the presented approach are that only a few user interactions are required to start up the system, the indexing precision increases fast with the size of the training set and that the indexing vocabulary is inherently unlimited.

The following sub-section reviews the current research into Content Based Image Retrieval (CBIR). Section 2 then introduces the general ideas, as well as the system framework. Low-level features extraction is discussed in section 3. The fourth section explains the way training sets are built. In section 5 we show how to optimize similarity measures used to compare images and regions throughout the system. The construction of classifiers is described in section 6, followed by the categories indexing scheme (section 7). Finally, experiments and results are discussed in section 8, before concluding and sketching future work in section 9.

Content-Based Image Retrieval

Content-based image retrieval (CBIR) systems [START_REF]A Review of Content-Based Image Retrieval Systems[END_REF] intend to provide solutions for browsing and retrieval of visual data. Such systems are dedicated to automatically (or semi-automatically) index images and make possible their retrieval via a search engine. Most CBIR systems are based upon the same framework [START_REF] Smeulders | Content-Based Image Retrieval at the End of Early Years[END_REF]: They usually involve a features extraction module (colors, textures, sometimes shapes), an indexing module (occasionally using machine learning techniques) and a retrieval module. However, they differ in the abstraction level of their image description and their respective query systems (which are actually limited by the abstraction level) and are not equal in terms of user's cognitive effort requirements. As the level of abstraction increases, formulating a query becomes easier.

In the earlier times, CBIR systems would involve only low-level indexes such as color and texture descriptions. In such a system, queries are intrinsically restricted to low-level queries such as sketch drawing, query by example or explicit manipulation of color, texture or shape features. These approaches are suitable in some particular cases ("I want an image which looks like this one") but are limited and should rather be available as an alternative query tool. Sketch drawing requires a lot of efforts from the user. Query by example is inherently ambiguous: an image may have been chosen as an example for multiple reasons (an object in the image, all the objects, the overall "look", the atmosphere, the location etc…). Besides, examples might not be available. QBIC [START_REF] Flickher | Query by Image and Video Content: The QBIC System[END_REF], the pioneer CBIR system, uses color, texture and shape features to describe images content. As for the queries, the user is given a choice between drawing a sketch and searching directly in terms of colors, shapes and textures. In such a system the abstraction level is low, which delegates a large part of the work to the user. This is also the case for VisualSEEk [START_REF] Smith | Querying by color regions using the VisualSEEk contentbased visual query system[END_REF] or Netra [START_REF] Ma | NETRA: A Toolbox for Navigating Large Image Databases[END_REF].

A higher level of abstraction is reached when associating the whole image with a type or a category. A higher level of indexing naturally allows a higher level query formulation. For instance in Simplicity from Stanford University [START_REF] Wang | SIMPLIcity: Semantics-sensitive Integrated Matching for Picture LIbraries[END_REF], images are automatically classified into categories such as photography, drawing etc… These categories have been learned previously from training sets and are therefore preset. In [START_REF] Vailaya | Content-Based Hierarchical Classification of Vacation Images[END_REF] vacation images are first classified into indoor/outdoor classes. Outdoor images are then further classified into city/landscape classes and landscape photographs are finally sorted into subsets such as forest, mountain or sunsets. The vacation pictures database enhanced by this system becomes much more organized and searchable. Here again, these categories are arbitrarily fixed and might not cover all of the user needs. Furthermore, only the whole image is taken into consideration, confining the queries to these predefined image categories.

Higher in the abstraction scale are the systems which attempt to describe images in terms of the entities composing them (as well as global descriptors). Not only can these systems associate signal information with symbols, they are also able of segmentation. This enables more precise and intuitive queries involving objects, their respective sizes and their spatial relationships. This level of description is, to date, the highest feasible degree of abstraction since, beyond, systems would have to deal with human emotions (atmosphere of a photograph for instance) or a deep knowledge of the world which generated the images (location, what are the people on the picture doing, etc...).

In [START_REF] Town | Content based image retrieval using semantic visual categories[END_REF], the authors describe an indexing/retrieval scheme based on high-level visual categories such as grass, sky or wood. These categories are learnt through a neural network classifier using the back-propagation algorithm. Good results are obtained with classification accuracies ranging from 86% to 98% depending on the visual category. However, the indexing terms are pre-defined and the use of neural networks makes incremental learning troublesome. An interesting fact pointed out in [START_REF] Town | Content based image retrieval using semantic visual categories[END_REF] is that results are worst when using amateur home pictures instead of a professional photograph collection such as Corel Photo Library. This should be kept in mind when confronting CBIR systems.

System Overview

In the remaining of the paper, the system will be called "Citra", the name given to its implementation. Citra is mainly an image indexing system but also includes a query and retrieval scheme. It allows a user to incrementally define his own indexing concepts, be they intra-image ("Palm tree", "Sky", "Person") or image categories ("Mountains", "Indoor", "Underwater"). After a new concept has been defined, all images in the database are updated. Citra does not need to re-compute all the indexes since each label is managed by a specialized classifier. Each label can therefore be updated separately. Figure 1 shows the principal components of the systems. Two different types of indexing are proposed. The first one is object based and requires the user to select positive and negative examples of the object he/she wishes to define through a semi-automatic segmentation tool (described in section 3). Every example is represented by a set of low-level features extracted from a rectangular, size-standardized region. Prior to building the classifier (section 5), Citra tunes the similarity measure used for each concept by giving weights to features (section 4). The system considers as good a similarity measure able to distinguish positive examples from negative ones. The classifier, a simple KNN classifier uses this similarity measure as well as the positive and negative examples to label unknown regions.

The second indexing concerns image categories (section 6). In the same fashion the user selects a few images corresponding either to positive or negative examples of an image category. A similar process then computes a suitable similarity measure (between images) and builds a classifier. This time however, the features are not only low-level (image color histogram, textures…) but also high-level features previously defined (objects or image categories). For example, when defining the global indexing concept "Beach Picture" the similarity measure tuning may set the features weights in such a way that the global colors, the presence of sky, sea and sand labels are emphasized.

Note that the underlying mechanism for global and local indexing is the same in both cases. The difference lies in the fact that category indexing uses information about objects composing images in addition to low-level features. We call that hierarchical indexing and use it to achieve higher indexing and retrieval abstraction.

Extracting Low-Level Features

There are plenty of models to choose from when it comes to extracting image features. The task is to select those which fit relevant criterions.

Extracting features usually yields several values that may or may not be correlated from each other. This characteristic is relevant in our system because (as we describe in section 5) the algorithm which associates relative weights to features assumes that the latter are not correlated.

Invariance to different geometric and lighting transformations is a property we are looking forward to, since pictures having the same content, modulo these transformations, should be considered as similar.

Driven by these considerations, we have chosen the HSV color space and the histogram representation for the characterization of image colors. The HSV color model fulfills the no-correlation property [START_REF] Bradshaw | Semantic Based Image Retrieval: A Probabilistic Approach[END_REF] as well as (to a certain extent) the invariance property.

As for texture, we have implemented a feature extractor (that we will not describe in details here) which focuses mainly on roughness and directionality. Roughness is measured under different scales and directions but expressed with disregard to them to ensure invariance. In the same way, directionality is only characterized by a quantity, intentionally omitting the orientation.

Building Training Sets

The composition of a training set is a factor influencing the learning based on this set. However in Citra, the user must constitute himself the training sets and no assumption is made concerning his ability to select the "right elements" with respect to the underlying learning mechanism. Therefore, the user has to be guided by the system.

In this section we describe how we build the training sets used to learn intra-image objects in Citra. Unlike most systems like [START_REF] Vailaya | Content-Based Hierarchical Classification of Vacation Images[END_REF][START_REF] Town | Content based image retrieval using semantic visual categories[END_REF], learning new image categories or objects may be done dynamically by the user. Choosing regions or images to build the training sets is usually performed offline by experts who, besides, know the inner working of the system. Picking up the right elements to constitute the training set is essential, especially when the latter is modest in size [START_REF] Mitchell | Machine learning[END_REF]. Besides, positive examples should be heterogeneous enough to cover all the possible appearances of an entity. As for negative examples, they ought to be close enough to the positive examples to avoid over-generalization and, at the same time, not too surrounding to prevent from over-fitting [START_REF] Mitchell | Machine learning[END_REF]. However in Citra, examples constituting the training set are not selected by an expert but by the user who picks them among a few images. Figure 2 shows the tool proposed to select positive and negative examples. This semi-automatic segmentation tool partition the image into positive and negatives regions after each user click. For instance, when defining "grass" like in figure 2, the user left-clicks in the grass area (defining an example) then in a "none grass" area (defining a negative example). The system segments the image into "grass" and "none grass" areas. In case some areas are misclassified, the user corrects the segmentation by left or right-clicking in those areas, until are no errors are left. That way, the user is imperceptibly forced to select relevant and discriminant examples. This is essential since the training set, manually constituted by the user, may be very small. In order to ensure consistency, the semiautomatic segmentation uses the same low-level features and the same classifiers as the indexing process.

Fine-Tuning Similarity Measures

In machine learning, and here more specifically, in empirical learning, one may either attempt to reach a fine level of representation and modeling of the data or concentrate on the problem of how to compare entities. The former approach fits, to a greater degree, problems in which the concepts to be learnt are well defined and formatted. Training examples and concepts chosen by an expert are more likely to be manageable by a machine learning algorithm. In Citra, those are defined by the user "None grass" "Grass" Misclassified for reasons that might not be obvious. Therefore, fine-tuning similarity measures might be more efficient than attempting to infer fine representations from the data.

Prior to building classifiers, there is a need to understand on which grounds the user based his selection of positive and negative examples. This is equivalent to finding a similarity measure between examples which emphasizes the right features. For instance, when learning the concept "Sky", features describing colors (or even blue colors) might be interesting features to focus on. While if "Car" is the target concept, a similarity measure giving more weight to textures or shapes would probably achieve better results than colors. These weights have to be discovered automatically. More precisely, the problem is to optimize the similarity measure S used to compare feature vectors. S has the following form:

) 2 , 1 ( dist . ) 2 , 1 (
1 i i N i i v v v v S ∑ = = α (1)
Where N is the number of features, v1 and v2 are the 2 features vectors corresponding to the description of two images, α i are the weights assigned to the features i. Let k be the number of values than each α i can take. The number of different weight vectors is N k , therefore optimizing S is, in the general case, an NP-hard optimization problem. Optimizing S by searching comprehensively the solution space is hence unfeasible. This is the reason why we make the assumption that features are not correlated with each other. That way, it is possible to assess the 'utility' of a given feature (for a given concept) independently, which is feasible.

Let us first define what we call utility: Utility is the ability of a given feature to discriminate positive from negative examples of a concept, that is, seeing positive examples as similar and negative examples as dissimilar from positive ones.

For this, we compute the "intra-class" similarity and "inter-class" similarity using a similarity measure which only takes into account the feature under examination. Let E + be any positive example and E -any negative example and S(E 1 , E 2 ) the similarity between two examples. Intra and inter-class similarities are defined as: Then, we combine these two values to get the utility:

(4)

Utility is computed for each feature. All these values are then normalized and constitute the weights vector for a particular concept. Note that, just like the tf/idf information retrieval classic weighting scheme, features having similar values in all the examples will not be emphasized whereas features having different values in positive and negative examples will be given more weight.

Classifiers & Indexing

Once a new concept has been defined by the user (by selecting positive and negative examples of it) and its associated similarity measure has been computed, the system classifies all the regions of all the images according to this new concept. In Citra, membership to a given class is assessed by a specific classifier. Among the multiple approaches, we have chosen to use an instance-based method: the k-Nearest Neighbor (Knn) classifier [START_REF] Mitchell | Machine learning[END_REF].

Function-fitting methods construct an explicit description of a target function from learning examples, instance-based methods store the training examples. Knn classifiers do not have a theoretical limit to the target function's complexity they learn [START_REF] Mitchell | Machine learning[END_REF]. This is required in Citra since the target function is determined by the user. Whatever the function-fitting algorithm may be, a set of training example selected by the user exists that will bewilder the classifier. Knn tackles this problem by not fitting a function at all. This makes the system flexible and adaptive to the user needs and to the images content.

One of the main issues when dealing with Knn classifiers is to cope with irrelevant attributes, which dilute relevant attributes influence. The similarity measure adapting scheme described in section 5 undertakes this difficulty by reducing the irrelevant attributes relative weights. How to select meaningful training examples is another issue in Knn learning [START_REF] Mitchell | Machine learning[END_REF], our selection scheme which handles this problem has been discussed in section 4. In Citra the user may define image categories such as "Under-water", "Cityscape", or "Indoor". In addition to our previous works [START_REF] Bissol | Dynamic Learning of Indexing Concepts for Home Image Retrieval[END_REF], an image is indexed by low-level features as well as high-level features (see figure 3). Value H1 H2 H3 … 0.73 0.12 0.0 … 0.05 0.96 Fig. 3. Feature vector for an image, containing both signal and semantic aspects.

In the feature vector, low-level features (principally histograms) are global to the image and concern color and texture. High-level features are either the area covered by a given learnt object ("Sky", "Trees") or the membership probability to an image category ("Indoor", "Portrait").

As discussed in [START_REF] Bissol | Dynamic Learning of Indexing Concepts for Home Image Retrieval[END_REF], global descriptors are useful but not sufficient to learn an image category. Introducing high-level descriptors greatly improves learning since an image category is strongly linked to the objects contained in the image as well as other image categories. For instance, the category "Mountains" would be connected with "Indoor" (there are no indoor mountains) or "Rocks" (Rocks often occur on a mountain image).

To define a new image category, the user selects a few positive and negative image examples. Similarly to intra-image object definition, the system optimizes a similarity measure used within a classifier to assign a category membership value to every image in the database.

Results

A complete implementation of our model has been realized to conduct experimentations. Images used in the following experiments are personal photographs taken by the authors. These images present a great variability in terms of quality, illumination, locations, type of scene.

Note that the following experimentations are preliminary since we are still in the process of building a large database of manually indexed images for experimentations. Step 2

Learning local concepts

Step 3

Step 4

Step 5

Step num be r

Recognition rates %

Learning Local Concepts

Figure 4 shows recognition rates for local concepts. The recognition rates are defined here as the precision value computed in the field of information retrieval, corresponding to the ratio of the number of correctly classified regions divided by the number of regions classified in that class by the system. This experimentation has been run on 40000 regions (100 images * 400 regions per image). The user starts a session with the system (from scratch) and first defines 3 concepts (step 1) using the semiautomatic segmentation tool on 1 image. The number of positive and negative examples required to segment the image varies depending on the 'complexity' of the concept. In the first step, 3, 3 and 7 examples were required for (respectively) 'Sea', 'Sky' and 'Foliage'. Noticing many mistakes in the indexing regarding the label 'Sea' the user increases the number of examples in step 2 from 3 to 12, therefore ameliorating the precision.

Then in the next steps, the user introduces new indexing terms (step 3: adding new concepts without modifying the already learnt concepts) and increases the number of examples for concepts whose precision is too low.

There are a few remarks we can make regarding this experiment. Firstly, the introduction of new concepts affects only slightly the precision of other concepts. However, the question remains opened for large number of concepts. Secondly, the accuracy of the indexing increases fast with the training set size, which is a property we were looking forward to. Indeed, the average number of examples per label is 4.3 initially and reaches 14.2 at the last step; meanwhile, the average recognition rate goes from 61% to 70%. Finally, the average precision reached by the system is satisfying, given the small size of the training samples, the large variability of the concepts appearance through the image set and the modest number of low-level features currently extracted.

Learning Image Categories

Figure 5 shows the result of an experiment in which a user wishes to define a new image category in the system (namely, "Beach pictures"). The lower precision corresponds to the case where only low-level features are used. The addition of symbolic information in the image feature vector (occupation of the image by each local concept, in percents) increases dramatically the precision. This means that global lowlevel features are not discriminant enough for this category of images, whereas symbolic information is (i.e. 60% 'Sand', 20% 'Sea'). Furthermore we can see that using a weighting scheme for the features is useful as it enhances precision. Note that, for a very small training set, weighting or not the features doesn't affect the precision. This is because finding out the 'utility' of each feature does not make sense on very small number of examples. However, as the training set size increases the weighting scheme shows its utility by emphasizing the relevant features (i.e. in this case : 'Sand', 'Sea'). Figure 6 shows a similar experiment in which the target category is "under-water". Surprisingly, the introduction here of symbolic information seems to make the preci-sion drop. The reason is that local concepts that can be found under-water (fishes, shells, etc.) are not known by the system. Therefore, these images are either indexed mostly by the term 'unknown' or by other terms which are mistakes. As a result, the relevant attributes in the feature vectors are diluted, which makes the precision fall.

However, when using the weighting scheme, the precision eventually catches up with the low-level-only precision. This is because irrelevant attributes influence is lessened by their utility value.

Conclusion

In this paper we have presented a new user-centered CBIR system. It allows users to define their own indexing terms, be they objects or image categories. Since building a training set is a sensitive task and users of this system are not expected to know how to do it, the system guides them in their selection of examples through a semiautomatic segmentation tool. Additionally, in order to understand on which grounds the user defines concepts, the system is able to characterize the 'utility' of each feature for a given concept (global or local). Users can make the system learn image categories. In this case, the system uses not only signal information but also symbolic information previously learnt: learning is hierarchical.

Our approach gives very promising results. We are currently building a large database of manually indexed images which will allow us to conduct exhaustive experiments.

Since our system performs an efficient feature selection, we plan to add more "perception" to the system via new low-level features, without fearing the dilution of relevant features influence.

Finally, we are currently trying to refine the indexing using statistical information such as location in space of local concepts and co occurrences betweens concepts.

Fig. 1 .

 1 Fig. 1. System overview. Steps requiring user intervention are marked with a symbol.

Fig. 2 .

 2 Fig. 2. Selecting relevant positive and negative examples through the semi-automatic segmentation tool.

  and P -are respectively the cardinal of the positive examples set and negative examples set.

Fig. 4 .

 4 Fig. 4. Recognition results for local concepts over a learning session

Fig. 5 .Fig. 6 .

 56 Fig. 5. Precision of the indexing according to the number of examples selected by the user (number of positive examples, number of negative examples).


Mohammed Belkhatir
email: belkhatm@imag.fr

Philippe Mulhem
email: mulhem@imag.fr

Yves Chiaramella

Integrating perceptual signal features within a bifacetted conceptual model for automatic image retrieval

The majority of the content-based image retrieval (CBIR) systems are restricted to the representation of signal aspects, e.g. color, texture… without explicitly considering the semantic content of images. According to these approaches a sun, for example, is represented by an orange or yellow circle, but not by the term "sun". The signal-oriented solutions are fully automatic, and thus easily usable on substantial amounts of data, but they do not fill the existing gap between the extracted low-level features and semantic descriptions. This obviously penalizes qualitative and quantitative performances in terms of recall and precision, and therefore users' satisfaction. Another class of methods, which were tested within the framework of the Fermi-GC project, consisted in modeling the content of images following a sharp process of human-assisted indexing. This approach, based on an elaborate model of representation (the conceptual graph formalism) provides satisfactory results during the retrieval phase but is not easily usable on large collections of images because of the necessary human intervention required for indexing. The contribution of this paper is twofold: in order to achieve more efficiency as far as user interaction is concerned, we propose to highlight a bond between these two classes of image retrieval systems and integrate signal and semantic features within a unified conceptual framework. Then, as opposed to state-of-the-art relevance feedback systems dealing with this integration, we propose a representation formalism supporting this integration which allows us to specify a rich query language combining both semantic and signal characterizations. We will validate our approach through quantitative (recall-precision curves) evaluations.

Introduction

From a user's standpoint, the democratization of digital image technology has led to the need to specify new image retrieval frameworks combining expressivity, performance and computational efficiency.

The first CBIR systems (signal-based) [START_REF] Ma | NeTra: A toolbox for navigating large image databases[END_REF][START_REF] Niblack | The QBIC project : Querying images by content using color, texture and shape[END_REF][START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF][START_REF] Smith | VisualSEEk: A fully automated content-based image query system[END_REF] propose a set of still images indexing methods based on low-level features such as colors, textures... The general approach consists in computing structures representing the image distribution such as color histograms, texture features and using this data to partition the image; thus reducing the search space during the image retrieval operation. These methods are based on the computation of discriminating features rejecting images which do not correspond to the query image and hold the advantage of being fully automatic, thus are able to quickly process queries. However, aspects related to human perception are not taken into account. Indeed, an image cannot be sufficiently described by its moments or color histograms. The problem arising from invariants or discriminating features lies on the loss of semantic information conveyed by the image. These tools are used for restricting the search space during the retrieval operation but cannot however give a sound and complete interpretation of the content. For example, can we accept that our system considers red apples or Ferraris as being the same entities simply because they present similar color histograms? Definitely not, as shown in [START_REF] Lim | Home Photo Content Modeling for Personalized Event-Based Retrieval[END_REF], taking into account aspects related to the image content is of prime importance for efficient photograph retrieval.

In order to overcome this weakness and allow the representation of the semantic richness of an image, semantic-based models such as Vimsys [START_REF] Gupta | R: Semantic queries with pictures: The VIMSYS model[END_REF] and EMIR 2 [START_REF] Mechkour | EMIR 2 : An Extended Model for Image Representation and Retrieval[END_REF][START_REF] Ounis | RELIEF: Combining expressiveness and rapidity into a single system[END_REF] rely on the specification of a set of logical representations, which are multilevel abstractions of the physical image. The originality of these models is achieved through integration of heterogeneous representations within a unique structure, collecting a maximum of information related to the image content. However these systems present many disadvantages. First, they are not fully automatic and require the user intervention during indexing, which constitutes a major drawback when dealing with reasonable corpus of images as this process is time-consuming and leads to heterogeneous and subjective interpretations of the image semantic content. Moreover, these models do not incorporate a framework for signal characterization, e.g. a user is not able to query these systems for "red roses". Therefore, these solutions do not provide a satisfying solution to bridge the gap between semantics and low-level features.

State-of-the-art systems which attempt to deal with the signal/semantics integration [START_REF] Cascia | Combining Textual and Visual Cues for Content-Based Image Retrieval on the World Wide Web[END_REF][START_REF] Lu | A unified framework for semantics and feature based relevance feedback in image retrieval systems[END_REF][START_REF] Zhou | Unifying Keywords and Visual Contents in Image Retrieval[END_REF] are based on the association of a query by example framework with textual annotation. These systems mostly rely on user feedback as they do not provide a formalism supporting the specification of a full textual querying framework combining semantics and signal descriptions and therefore exhibit poor performance in relating low-level features to high-level semantic concepts. Prototypes such as ImageRover [START_REF] Cascia | Combining Textual and Visual Cues for Content-Based Image Retrieval on the World Wide Web[END_REF] or iFind [START_REF] Lu | A unified framework for semantics and feature based relevance feedback in image retrieval systems[END_REF] present loosely-coupled solutions relying on textual annotations for characterizing semantics and a relevance feedback scheme that operates on low-level features. These approaches have two major drawbacks: first, they fail to exhibit a single framework unifying low-level and semantics, which penalizes the performances of the system in terms of retrieval effectiveness and quality. Then, as far as the querying process is concerned, the user is to query both textually in order to express high-level concepts and through several and time-consuming relevance feedback loops to complement her/his initial query. This solution for integrating semantics and low-level features, relying on a cumbersome querying process does not enforce facilitated and efficient user interaction. For instance, queries involving textually both semantics and signal features such as "Retrieve images with a purple flower" or "Retrieve images with a vegetation which is mostly green" cannot be processed. We propose a unified framework coupling semantics and signal features for automatic image retrieval that enforces expressivity, performance and computational efficiency. As opposed to stateof-the-art frameworks offering a loosely-coupled solution with a textual framework for keyword-based querying integrated in a relevance feedback framework operating on low-level features, user interaction is optimized through the specification of a unified textual querying framework that allows to query over both signal and semantics.

In the remainder of this paper, we will first present the general organization of our model and the representation formalism allowing the integration of semantics and signal features within an expressive and multi-facetted conceptual framework. We will deal in sections 3 and 4 with the descriptions of both the semantic and the signal facets, dealing thoroughly with conceptual index structures. Section 5 will specify the querying framework. We finally present the validation experiments conducted on a test collection of 2500 personal photographs.

The proposed method: Signal/Semantic integration within an expressive conceptual framework

In state-of-the-art CBIR systems, images cannot be easily or efficiently retrieved due to the lack of a comprehensive image model that captures the structured abstractions, the signal information conveyed and the semantic richness of images. To remedy such shortcomings, visual semantics and signal features are integrated within an image model which consists of a physical image level and a conceptual level. The latter is itself a multi-facetted framework supported by an expressive knowledge representation formalism: conceptual graphs.

An image model integrating signal and semantic features

The first layer of the image model (fig. 1) is the physical image level representing an image as a matrix of pixels. The second layer is the conceptual level and is itself a tri-facetted structure:

-The first facet called object facet describes an image as a set of image objects, abstract structures representing visual entities within an image. Their specification is an attempt to operate image indexing and retrieval operations beyond simple low-level processes [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF] or region-based techniques [START_REF] Carson | Blobworld: A System for Region-Based Image Indexing and Retrieval[END_REF] since image objects convey the visual semantics and the signal information at the conceptual level. Formally, this facet is described by the set I IO of image object identifiers.

-The second facet called visual semantic facet describes the image semantic content and is based on labeling image objects with a semantic concept. In the example image of fig. 1, the first image object (Io1) is tagged by the semantic concept Hut. Its formal description will be dealt with in section 3.

-It is itself partitioned in two sub-facets. The color facet describes the image color content in terms of symbolic perceptual features and consists in characterizing image objects with color concepts. In the example image of fig. 1, the second image object (Io2) is associated with symbolic colors Cyan and White and symbolic textures . The signal facet will be described in detail and formalized in section 4. It features

Representation formalism

In order to instantiate this model within a framework for image retrieval, we need a representation formalism capable to represent image objects as well as the visual semantics and signal information they convey. Moreover, this representation formalism should make it easy to visualize the information related to an image. It should therefore combine expressivity and a user-friendly representation. As a matter of fact, a graph-based representation and particularly conceptual graphs (CGs) [22] are an efficient solution to describe an image and characterize its components. The asset of this knowledge representation formalism is its flexible adaptation to the symbolic approach of image retrieval [START_REF] Mechkour | EMIR 2 : An Extended Model for Image Representation and Retrieval[END_REF][START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF][START_REF] Smith | VisualSEEk: A fully automated content-based image query system[END_REF]. It allows indeed to represent components of our CBIR architecture and to develop an expressive and efficient framework as far as indexing and querying operations.

Formally, a conceptual graph is a finite, bipartite, connex and oriented graph. It features two types of nodes: the first one graphically represented by a rectangle (fig. 2) is tagged by a concept however the second represented by a circle is tagged by a conceptual relation. The graph of fig. 2 represents a man eating in a restaurant. Concepts and relations are identified by their type, itself corresponding to a semantic class. Concept and conceptual relation types are organized within a lattice structure partially ordered by ' ' which expresses the relation 'is a specialization of'. For example, Person Man denotes that the type Man is a specialization of the type Person, and will therefore appear in the offspring of the latter within the lattice organizing these concept types. Within the scope of the model, conceptual graphs are used to represent the image content at the conceptual level. Each image (respectively user query) is represented by a conceptual graph called document index graph (respectively query graph) and evaluation of similarity between an image and a query is achieved through a correspondence function: the conceptual graph projection operator. Semantic concept types are learned and then automatically extracted given a visual thesaurus. The construction of a visual thesaurus is strongly constrained by the application domain, indeed dealing with corpus of medical images would entail the elaboration of a visual thesaurus that would be different from a thesaurus considering computer-generated images. In this paper, our experiments presented in section 6 are based on a collection of personal photographs. Let us detail the elaboration of our visual thesaurus.

Several experimental studies presented in [START_REF] Mojsilovic | Capturing image semantics with low-level descriptors[END_REF] have led to the specification of twenty categories or picture scenes describing the image content at the global level. Web-based image search engines (google, altavista) are queried by textual keywords corresponding to these picture scenes and 100 images are gathered for each query. These images are used to establish a list of concept types characterizing objects that can be encountered in these scenes. This process highlights seven major semantic concept types: people, ground, sky, water, foliage, mountain/rocks and building. We then use WordNet to produce a list of hyponyms linked with these concept types and discard terms which are not relevant as far as indexing and retrieving images from personal corpus are concerned. Therefore, we obtain a set of concept types which are specializations of the seven major semantic concept types. We repeat the process of finding hyponyms for all the specialized concept types. The last step consists in organizing all these concept types within a multi-layered lattice ordered by a specific/generic partial order. In fig. 3, the second layer of the lattice consists of concepts types which are specifications of the major semantic concept types, e.g. face and crowd are specifications of people. The third layer is the basic layer and presents the most specific concept types, e.g. man, woman, child are specifications of individual.

Fig. 3. Lattice of semantic concept types

A feed-forward neural network is used to learn these semantic concept types from a set of training and testing images. Low-level features [START_REF] Lim | Explicit query formulation with visual keywords[END_REF] are computed for each training object and organized within a vector used as the input of the neural network. The learning being completed, an image is then processed by the network and the recognition results are aggregated to highlight image objects. An image object is thus characterized by a vector of semantic concept types, each one being linked to a value of recognition certainty. For instance, in the image of fig. 1, the second image object labeled as Io2 is characterized by a vector which has a significant value for the seman- tic concept type hut and small values related to other semantic concepts. At the CG representation level, the semantic concept type with the highest recognition certainty is kept. As a matter of fact, Io2 will be represented by the semantic concept type hut. We will now specify the model organizing the visual semantics facet and deal with its representation in terms of CGs.

Model of the visual semantics facet

The model of visual semantics facet gathers semantic concept types and their lattice induced by a partial order relation: Msy = (SC, sct) -SC is the set of visual semantics concept types.

sct: I IO SC associates to each image object its semantic concept type.

Image objects are represented by Io concepts and the set SC is represented by a lattice of semantic concept types partially ordered by the relation vs . An instance of the visual semantics facet is represented by a set of CGs, each one containing an Io type linked through the conceptual relation sct to a semantic concept type. The basic graph controlling the generation of all visual semantic facet graphs is: [Io] (sct) [SC]. For instance, the following graphs are the representation of the visual semantics facet in fig. 1 and can be translated as: the first image object (Io1) is associated with the semantic concept type hut, the second image object (Io2) with the semantic concept type sky and the third image object (Io3) with the semantic concept type grass.

The integration of signal information within the conceptual level is crucial since it enriches the indexing framework and expands the query language with the possibility to query over both semantics and visual information. After presenting our formalism, we will now focus on the signal facet and deal with theoretical implications of integrating signal features within our multi-facetted conceptual model. This integration is not straightforward as we need to characterize low-level signal features at the conceptual level, and therefore specify a rich framework for conceptual signal indexing and querying. We first propose conceptual structures for the signal facet and then thoroughly specify the conceptual model for the signal facet and its representation in terms of CGs.

The signal facet: from low-level signal data to symbolic characterization

Our architecture and its supported operational model make it possible for a user to combine low-level features with visual semantics in a fully textual conceptual framework for querying. However, querying textually on low-level features requires specifying a correspondence process between color names and color stimuli. Our symbolic representation of color information is guided by the research carried out in color naming and categorization [1] stressing a step of correspondence between color names and their stimuli. We will consider the existence of a formal system S nc of color categorization and naming [START_REF] Lammens | A computational model of color perception and color naming[END_REF] which specifies a set of color categories Cat with a cardinal C cat . These color categories are the C i where variable i belongs to [1, C cat ]. Each image object is then indexed by two types of conceptual structures featuring its color distribution: boolean and quantified signal concepts.

When providing examples of the specified conceptual structures, we will consider that the color naming and categorization system highlights four color categories: cyan(c), green(gn), grey(g) and white(w) (Cat={cyan, green, grey, white}).

Index structures

Boolean signal index concept types (BSICs), gathered within the set B SI are supported by a vector structure v B with a number of elements equal to the number C cat of color categories highlighted by the naming and categorization system. Values v B [i], i∈[1,C cat ] are booleans stressing that the color category C i is present in non-zero proportion within the considered image object. The semantics conveyed by BSICs is the 'And' semantics. As a matter of fact, these concept types feature the signal distribution of image objects by a conjunction of color categories. For instance, the first image object (Io1) corresponding to the semantic concept type hut in fig. 1 is characterized by the BSIC <c:0,gn:0,g:1,w:1>, which is translated by Io1 having a signal distribution including grey and white.

We wish to extend the definition of BSICs and quantify by a variable known as color category value the integer percentage of pixels corresponding to a color category. The color category value corresponds to the standardization of the pixel percentages of each color category. Quantified signal index concept types (QSICs), gathered within the set Q SI are supported by a vector structure v Q with a number of elements equal to the number C cat of color categories highlighted by the naming and categorization system. Values v Q [i], i∈[1,C cat ] are the color category values. These concept types feature the signal distribution of image objects by a conjunction of color categories and their associated color category values. Let us note that the sum of category values is always 100, the color distribution being fully distributed between all color categories. The second image object (Io2) corresponding to the semantic concept type sky in fig. 1 is characterized by the QSIC <c:59,gn:0,g:0,w:41>, which is translated by Io2 having a signal distribution including 59% of cyan and 41% of white.

Index structures

As far as querying is concerned, our conceptual architecture is powerful enough to handle an expressive and computationally efficient language consisting of boolean and quantified queries:

-A user shall be able to associate visual semantics with a boolean conjunction of color categories through an And query, such as Q1: "Find images with a grey and white hut", a boolean disjunction of color categories through an Or query, such as Q2: "Find images with either cyan or grey sky" and a negation of color categories through a No query, such as Q3: "Find images with non-white flowers".

-As far as quantified queries, At Most queries (such as Q4: "Find images with a cloudy sky (at most 25% of cyan)") and At Least queries (such as Q5: "Find images with lake water (at least 25% of grey)") associate visual semantics with a set of color categories and a percentage of pixels belonging to each one of these categories. We specify also literally quantified queries (Mostly, Few) which can prove easier to handle by an average user, less interested in precision-oriented querying.

In the following sections we will present the conceptual structures supporting the previously defined query types.

Boolean signal query concept types.

There are three categories of concepts types supporting boolean querying: And signal concept types (ASCs), gathered within the set B And represent the color distribution of an image object by a conjunction of color categories; Or signal concept types (OSCs), gathered within the set B Or , by a disjunction of color categories and No signal concept types (NSCs), gathered within the set B No , by a negation of color categories. These concepts are respectively supported by vector structures v And , v Or and v No with a number of elements equal to the number C cat of color categories. Values v And [i], v Or [i] and v No [i], i∈[1,C cat ] are nonnull if the color category C i is mentioned respectively in the conjunction, disjunction or negation of color categories within the query. The ASC corresponding to the color distribution expressed in query Q1 is <c:0, gn:0, g:1, w:1> And . The color distribution expressed in query Q2 is translated in the OSC <c:1, gn:0, g:1, w:0> Or . Finally, the color distribution expressed in query Q3 is translated in the NSC <c:0, gn:0, g:0, w:1> No .

Signal quantified query concept types.

There are two types of numerically quantified signal concept types : At Most signal concept types (AMSCs) gathered within the set Q AM and At Least signal concept types (ALSCs) gathered within the set Q AL that are respectively supported by vector structures v AM and v AL with a number of elements equal to C cat .

If the color category C i is specified in a query, values v AM [i] and v AL [i] (i∈[1,C cat ]) are non-null and correspond respectively to the maximum pixel percentage associated with C i (translating the keyword 'At Most') and the minimum pixel percentage associated with C i (translating the keyword 'At Least'). For instance, the color distribution expressed in query Q4 is translated in the AMSC <c:25, gn:0, g:0, w:0> AMSC whereas the color distribution expressed in query Q5 is translated in the ALSC <c:0, gn:0, g:25, w:0> ALSC.

Expressing a query with numerical quantification is precision-oriented and an average user might find it cumbersome. Therefore we introduce literally quantified queries such as Mostly queries (e.g. "Find images with a bright sky (Mostly cyan)") and Few queries (e.g. "Find images with a cloudy sky (Few cyan)"). These queries are supported by sets Q Mostly and Q Few of Mostly and Few signal concept types. We set up a correspondence between the quantifier Mostly and the numeral quantification At Least 50%. Also, the quantifier Few will correspond to the numeral quantification At Most 10%.

After introducing structures for conceptual signal characterization, we propose a formal model organizing the signal facet. This model is then instantiated in the CG representation formalism within our image retrieval framework.

A conceptual model for the signal facet

The model of the signal facet M SI is given by the model MI SI of the signal index facet and the model MQ SI of the signal query facet where MI SI = (I SI , RI SI ) and MQ SI = (Qu SI , RQ SI ): Let us note that and_si and or_si are specialized relations of b_si. Also, am_si, al_si, mostly_si, few_si are specialized relations of q_si.

-I SI is
Image objects are represented by Io concepts and signal index and query structures are organized within a lattice of concept types. An instance of the signal facet is represented by a set of canonical CGs, each one containing an Io type possibly linked through signal conceptual relations to signal concept types.

There are two types of basic graphs controlling the generation of all signal facet graphs. The firsts are index signal graphs:

[Io] (b_si) [B SI ]; [Io] (q_si) [Q SI ].

The seconds are query signal graphs: [Io] (and_si) [B And ]; [Io] (or_si) [B Or ] ; [Io] (no_si) [B No ] ;

[Io] (am_si

) [Q AM ]; [Io] (al_si) [Q AL ]; [Io] (mostly_si) [Q Mostly ] and [Io] (few_si) [Q Few ].
The following index graphs are the representation of the signal facet in fig. 1: <c:0,gn:0,g:85,w:15>

Io1 q_si <c:59,gn:0,g:0,w:41>

Io2 q_si <c:0,gn:75,g:0,w:25>

Io3 q_si <c:0,gn:0,g:1,w:1>

Io1 b_si <c:1,gn:0,g:0,w:1>

Io2 b_si <c:0,gn:1,g:0,w:1> Io3 b_si

The querying module

In image retrieval systems, the typical mode of user interaction relies on the query by example process [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF]: the user provides a set of example images as an input, the system generates a query and then outputs images that are the most similar. This mode of interaction suffers from the fact that the user's need remains implicit, i.e. given the input images chosen by the user, the system has thus to use its knowledge of the image content to extract implicit information and construct a query. This process can be very complex and lead to ambiguities and poor retrieval performances when dealing with high-level characterizations of an image. Our conceptual architecture is based on a unified textual-based framework allowing a user to query over both the visual semantics and the signal facets. This obviously enhances user interaction since contrarily to query by example systems, the user becomes in 'charge' of the query process by making his needs explicit to the system through full textual querying. We will present in the following some queries involving boolean and quantified signal concepts, study their transcription within our conceptual framework and then deal with operations related to query processing. We will thus specify the organization of concept type lattices.

Query expression

A general query is defined through a combination of selection criteria over the visual semantics and the signal facets. A query image q is represented by a 3-tuple (I IO , q vs , q si ) where I IO is the set of image objects, q vs and q si are instances of the visual semantics and query signal facet models.

We propose to study the transcription in our model and then the processing of two types of queries for obvious space restrictions: the first one associates visual semantics with a boolean signal concept type (And signal concept type), the second associates visual semantics with a quantified signal concept type (At Most signal concept type).

Find images with a grey and white hut.

In our formalism, it is translated as: q=(I IO ,q vs ,q si ) with I IO ={Io1}; q vs =({Hut},{(Io1,Hut)}); q si =({<c:0,gn:0,g:1,w:1> And }, {(Io1,<c:0,gn:0,g:1,w:1> And )}). In the CG representation formalism, we have:

Find images with a cloudy sky (At Most 25% of cyan).

The transcription of this query in our conceptual framework is: q=(I IO , q vs , q si ): I IO ={Io1} ; q vs =({Sky}, {(Io1,Sky)}) ; q si =({<c:25,gn:0,g:0,w:0> AM }, {(Io1,<c:25,gn:0,g:0,w:0> AM )}). The transcription of this query in the CG representation formalism gives:

The projection operator

An operational model of image retrieval based on the CG formalism uses the graph projection operation for the comparison of a query graph and a document graph. This operator allows to identify within a graph g 1 sub-graphs with the same structure as a given graph g 2 , with nodes being possibly restricted, i.e. their types are specialization of g 2 node types. If it exists a projection of a query graph Q within a document graph D then the document indexed by D is relevant for the query Q. Formally, the projection operation℘ : q d exists if there is a sub-graph of d verifying the two following properties:

-There is a unique document concept which is a specific of a query concept, this being valid for any query concept. This property ensures that all elements describing the query are present within the image document, and their image is unique.

-For any relation linking concepts c q1 and c q2 of q, there is the same relation between the two concepts c d1 and c d2 of d, such as ℘(c q1 ) = c d1 and ℘(c q2 ) = c d2 .

At the implementation level, brute-force coding of the projection operation would result in exponential execution times. Based on the work in [START_REF] Smith | VisualSEEk: A fully automated content-based image query system[END_REF], we enforce the scalability of our framework using an adaptation of the inverted file approach for image retrieval. This technique consists in associating indexed keywords to the set of documents whose index contain it. Treatments that are part of the projection operation are performed during indexing following a specific organization of CGs which does not affect the expressiveness of the formalism.

Organizing concept type lattices for effective and computationally efficient retrieval

In the following concept type lattices (fig. 4,5), the graphical arrow corresponds to a specialization operation and we consider that Cat={cyan, green, grey, white}.

Processing an And query.

BSICs are organized within the And lattice (fig. 4) to process an And query. When a query such as "Find images with a grey and white hut" is formulated, it is first translated in a query CG with the semantic concept type hut processed by the lattice of semantic concept types (fig. 3) and the ASC <c:0,gn:0,g:1,w:1> And . This ASC is then related to its equivalent BSIC as highlighted in fig. 4. The most relevant images provided by the system have a hut with grey and white only, this symbolic color distribution is represented by the highlighted BSIC (b 1 ) in fig. 4. Other images are composed of a hut with a color distribution including grey and white and at least one secondary color category. In the lattice, BSICs representing such color distributions are sons of b 1 .

The general organization of this lattice is such that BSICs with a unique non-zero component are sons of the maximum virtual element T And . They represent the perception of a unique color category in an image object. The BSIC with all non-zero components is at the bottom of the hierarchy, it is the minimum element noted ⊥ And . This concept is a specialized concept of all BSICs presenting at least a non-zero component. Formally, we define a partial order in the And lattice of BSICs noted And by:

∀ a,b∈B SI a And b ⇔ [a = ⊥ And ∨ b = T And ] ∨ [¬∃k∈[1,C cat ] / b [k] = 1 ∧ a [k] = 0] (1)

Processing an At Most query.

When a query such as "Find images with a cloudy sky (i.e. with a color distribution that includes at most 25% of cyan)" is formulated, it is translated in a query CG with the semantic concept type sky processed by the lattice of semantic concept types (fig. 3) and the AMSC <c:25,g:0,gn:0,w:0> AM . However, the link between this AMSC and its equivalent QSIC is not straightforward. Therefore we introduce a new category of concepts types bridging the gap between AMSCs and QSICs by taking into account dominant color categories (i.e. categories mentioned in a query as they have a higher importance in the ordering process of signal concepts within the lattice, other color categories are called secondary). These concept types are QSICs with dominant d AM , where d AM is the set of dominant color categories. They are supported by a vector structure v AMd [i] with a number of elements equal to C cat +1. The v AMd [i] i∈ [1,Ccat+1] values such that C i ∈d AM are the maximum pixel percentages of dominant color categories and the v AMd [j] j∈ [1,Ccat+1] such that j ≠ i correspond to the pixel percentages of secondary color categories ranked in ascending order. A component summing pixel percentages of secondary color categories noted is introduced. By construction, this element is the maximum value among the v AMd [j] j∈ [1,Ccat+1] . QSICs with dominant d AM are therefore specializations of AMSCs and generalizations of QSICs and link AMSCs to QSICs. The AMSC <c:25,g:0,gn:0,w:0> AM is related to its equivalent QSIC with dominant {cyan}: <25,25,25,25,75> as highlighted in fig. 5a. As a matter of fact, the most relevant images provided by the system have a sky with 25% of cyan and a remaining proportion uniformly distributed between the 3 secondary color categories (25% each in our example). Others are images with a sky having a color distribution that includes less than 25% of cyan, the remaining proportion p being in the best cases uniformly distributed between the 3 secondary color categories. Formally, sub-lattices of AMSCs with dominant d AM (framed structure in fig. 5a) are partially ordered by AM :

∀ a,b QSICs with dominant d AM, a AM b ⇔ [a=⊥ AM ∨ b=T AM ] ∨ [∀j∈[1,C Cat ] / Cat j ∈d AM , 1 a [j] b [j] ] (2)
0,1,0,0 0,0,1,0 1,0,0,0 0,0,0,1

⊥ And = 1,1,1,1 TAnd 1,1,0,0 0,1,1,0 1,0,1,0 0,0,1,1(b1) 1,0,0,1 1,1,1,0 0,1,1,1 1,1,0,1 1,0,1,1 0,1,0,1 0,0,1,1And
Sub-lattices of concept types with components corresponding to dominant color categories being equal (framed structure in fig. 5b) are partially ordered by AM_eq : ∀ a,b QSICs with dominant d AM having components that correspond to dominant color categories being equal, a AM_eq b

⇔ (∀ j, k ∈ [1,C Cat + 1] / Cat j ∉ d AM ∧ Cat k ∉ d AM , j,k b [j] -b [k] j,k a [j] -a [k] ) (3)
Let us note than the At Least lattice has a symmetric organization and will not be dealt with for space restriction. Mostly and Few queries involving literal quantifiers, e.g. "Find images with a bright sky (mostly cyan)" or "Find images with a cloudy sky (few cyan)", are processed accordingly to At Most and At Least queries. Indeed, the quantifier Mostly corresponds to the numeral quantification 'At Least 50%' and the quantifier Few is linked to the numeral quantification 'At most 10%'. As a matter of fact, processing these queries will not affect the computational efficiency of our model as it is based on AMSCs and ALSCs concept type lattices.

Experimental results

We have presented a conceptual architecture in which semantic and signal features are integrated to achieve higher expressivity as far as querying is concerned and increased retrieval accuracy. We will describe here the SIAIR image retrieval system that is an implementation of the theoretical framework presented and present several experimentation results.

The SIAIR image retrieval system implements the formal framework presented in this paper, the supported mode of interaction relying on keyword-based search. When a user enters a query, it is translated in a CG query graph as developed in section 5. It is then processed and images given by the system are ranked and displayed according to their relevance with respect to the query.

Validation experiments are carried out on a corpus of 2500 personal color photographs collected over a period of five years and used as a validation corpus in worldclass publications [START_REF] Lim | Home Photo Content Modeling for Personalized Event-Based Retrieval[END_REF][START_REF] Mulhem | Symbolic photograph content-based retrieval[END_REF] (fig. 1 collection). Dealing with personal photographs instead of professional collections (e.g. Corel images) is guided by our research problematic which is the specification of an expressing framework enhancing techniques that allow a user to index and query over a collection of home photographs. Moreover, the quality of home photographs is not as good as the quality of professional images which leads to retrieval results being generally poorer than those for the Corel images. Image objects within the 2500 photographs are automatically assigned a semantic concept as presented in section 3 and are characterized with conceptual signal structures presented in section 4. Eleven color categories (red, green, blue, yellow, cyan, purple, black, skin, white, grey, orange) empirically spotlighted in [START_REF] Gong | Image Indexing and Retrieval Based on Color Histograms[END_REF] are described in the HVC perceptually uniform space by a union of brightness, tonality and saturation intervals [START_REF] Miyahara | Mathematical Transform of (R,G,B) Color Data to Munsell[END_REF].

Given an image corpus, we wish to retrieve photographs that represent elaborate scenes involving signal characterization. We specify 22 image scenes (e.g. night, swimming-pool water…) and select within the corpus for each scene all images which are relevant. The evaluation of our formalism is based on the notion of image relevance which consists in quantifying the correspondence between index and query images.

We compare our approach with both state-of-the-art signal and semantics-based approaches, namely "HSV local" and "Visual keywords". The HSV local method is based on the specification of ten key colors (red, green, blue, black, grey, white, orange, yellow, brown, pink) in the HSV color space adopted by the original PicHunter system [START_REF] Cox | The Bayesian Image Retrieval System, PicHunter: Theory, Implementation and Psychophysical Experiments[END_REF]. The similarity matching between two images is computed as the weighted average of the similarities between corresponding blocks of the images. As a matter of fact, this method is equivalent to locally weighted color histograms.

Visual keywords [START_REF] Lim | Explicit query formulation with visual keywords[END_REF][START_REF] Lim | Home Photo Content Modeling for Personalized Event-Based Retrieval[END_REF][START_REF] Mulhem | Symbolic photograph content-based retrieval[END_REF] are intuitive and flexible visual prototypes extracted or learned from a visual content domain with relevant semantic labels. A set of 26 specified visual keywords are learned using a neural network, with low-level features computed for each training region as an input for this network. An image is indexed to multi-scale, view-based recognition against these 26 visual keywords, recognition results across multiple resolutions are aggregated according to spatial tessellation. It is then represented by a set of local visual keyword histograms with each bin corresponding to the aggregation of recognition results. The similarity matching between two images is defined as the weighted average of the similarities between their corresponding local visual keywords histograms. The HSV local and Visual Keywords methods are presented here to compare the results of usual signal-based and semanticbased approaches to our framework combining both of these approaches.

For each of the 22 image scene descriptions (e.g. swimming-pool water), we construct relevant textual query terms using corresponding semantic and signal concepts as input to the SIAIR system (e.g. "Find images with mostly cyan" for swimming-pool water). Also each image scene description is translated in textual signal data as input to the HSV local approach ("Find images with cyan" for swimming-pool water) and in relevant visual keywords to be processed by the Visual keywords system ("Find images with a sky" for swimming-pool water). Curves associated with the Q_SymbColor, Q_Symb and Q_Color legends (fig. 6) illustrate respectively the results in recall and precision obtained by SIAIR, the Visual Keywords and the HSV local systems.

The average precision of SIAIR (0.5854) is approximately five times higher than the average precision of the Visual Keywords method (0.1115) and approximately 3,5 times higher than the value of average precision of the HSV local method (0.168). We notice that improvements of the precision values are significant at all recall values. This shows that when dealing with elaborate queries which combine multiple sources of information (here visual semantics and signal features) and thus require a higher level of abstraction, the use of an "intelligent" and expressive representation formalism (here the CG formalism within our framework) is crucial. As a matter of fact, SIAIR complements both state-of-the-art signal-based approaches by proposing a framework for semantic characterization and state-of-the-art semantic-based methods through signal conceptual integration, which enriches indexing languages and expands usual querying frameworks restricted to a reduced set of extracted or learned keywords (in this case the visual keywords).

Conclusion

We have proposed within the scope of this paper the formal specification of a framework combining the two existing approaches in image retrieval, i.e. signal and symbolic within a strongly-coupled architecture to achieve greater retrieval accuracy. It is instantiated by an operational model based on the CG formalism, which allows to define an image representation and a correspondence function to compare index document and query graphs. Our work has contributed both theoretically and at the experimental level to the image retrieval research topic. We have specified image objects, abstract structures representing visual entities within an image in order to operate image indexing and retrieval operations at a higher level of abstraction than state-of-the-art frameworks. We have formally described the visual semantics and the signal facets that define the conceptual information conveyed by image objects and have finally proposed a unified and rich framework for querying over both visual semantics and signal data. At the experimental level, we have implemented and evalu-ated our framework. The results obtained allowed us to validate our approach and stress the relevance of the signal/semantics integration.

Fig. 1 .

 1 Fig. 1. Image model

Fig. 2 . 3 A descriptive model for semantics: the visual semantics facet 3 . 1

 2331 Fig. 2. An example of conceptual graph

Fig. 4 .

 4 Fig. 4. Lattice processing And queries

Fig. 5 . 5 . 3 . 3

 5533 Fig. 5. (a) Sub-lattice of At Most signal concepts (b) with dominant {C1=cyan}

Fig. 6 .

 6 Fig. 6. Recall/Precision curves

  the set of signal index structures: I SI = {B SI , Q SI } -RI SI is the set of signal index conceptual relations: RI SI = {b_si, q_si} b_si : I IO B SI and q_si : I IO Q SI associate image object identifiers with boolean and quantified signal index concept types.-Qu SI is the set of signal query structures: Qu SI = {B And , B Or , B No , Q AM , Q AL , Q Mostly , Q Few } -RQ SI is the set of signal query conceptual relations: RQ SI = {and_si , or_si, no_si,

	am_si, al_si, mostly_si, few_si}
	and_si : I IO	B And ; or_si : I IO	B Or and no_si : I IO	B No associate image object
	identifiers with ASCs, OSCs and NSCs.
	am_si : I Si	Q AM and al_si : I IO	Q AL associate image object identifiers with
	AMSCs and ALSCs.
	mostly_si : I IO	Q Mostly and few_si : I

IO Q Few associate image object identifiers with Mostly and Few signal concept types.

  displays a typical photograph which belongs to this

	T AM
		....
		.
		34,32,33,1, (...)
	(...)
	(...)
	.	.
	⊥ AM


Mohammed Belkhatir
email: belkhatm@imag.fr

Philippe Mulhem
email: mulhem@imag.fr

Yves Chiaramella

THE OUTLINE OF AN 'INTELLIGENT' IMAGE RETRIEVAL ENGINE

Keywords: Multimedia, Image Retrieval, Automatic Extraction, Conceptual Graphs, Image Query Language

The first image retrieval systems hold the advantage of being fully automatic, and thus scalable to large collections of images but are restricted to the representation of low-level aspects (e.g. colors, textures…) without considering the semantic content of images. This obviously compromises interaction, making it difficult for a user to query with precision. The growing need for 'intelligent' systems, i.e. being capable of bridging this semantic gap, leads to new architectures combining multiple characterizations of the image content. This paper presents SIR 1 , a promising high-level framework featuring semantics, signal color and spatial characterizations. It features a fully-textual query module based on a language manipulating both boolean and quantification operators, therefore making it possible for a user to request elaborate image scenes such as a "covered(mostly grey) sky" or "people in front of a building".

INTRODUCTION

The democratization of digital image technology has led to the need to deal with a new generation of image retrieval frameworks combining expressivity, increased retrieval performance and computational efficiency. The first content-based image retrieval (CBIR) systems (signal-based) [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF] propose a set of image indexing methods based on low-level features such as colors, textures, geometrical forms... which are fully automatic and able to process queries quickly. However, the problem arising from low-level characterization lies on the loss of semantic information conveyed by the image. For example, can we accept that our system considers red apples or Ferraris as being the same entities simply because they present similar color histograms? Definitely not, as shown in [START_REF] Lim | Home Photo Content Modeling for Personalized Event-Based Retrieval[END_REF], taking into account aspects related to the image content is of prime importance for efficient photograph retrieval. State-of-the-art systems which attempt to deal with the semantics/signal integration [START_REF] Cascia | Combining Textual and Visual Cues for Content-Based IR on the World Wide Web[END_REF][START_REF] Lu | A unified framework for semantics and feature based RF in image retrieval systems[END_REF][START_REF] Zhou | Unifying Keywords and Visual Contents in Image Retrieval[END_REF] are based on the association of textual annotations with relevance feedback. Prototypes such as iFind [START_REF] Lu | A unified framework for semantics and feature based RF in image retrieval systems[END_REF] and ImageRover [START_REF] Cascia | Combining Textual and Visual Cues for Content-Based IR on the World Wide Web[END_REF] offer loosely-coupled solutions based on textual annotations to characterize semantics and on a relevance feedback scheme operating on low-level signal features. These approaches present two major drawbacks: first, they lack to exhibit a single framework unifying signal features and semantics, which penalizes the performance of the system in terms of retrieval efficiency and quality. Then, the user is to query both textually in order to express high-level concepts and through several and time-consuming relevance feedback loops to complement his initial query; which does not enforce a user-friendly interaction. We propose a multi-facetted image indexing and retrieval framework unifying semantics, signal color and spatial characterizations. We first specify an automated framework extracting the visual semantics. We then enrich the description of images through the specification of processes establishing a correspondence between extracted low-level features and high-level color concepts. E.g. with the visual semantics concept "sky" one might assign additional concepts such as "cyan" or "grey" characterizing its color. Also, as the specification of relations between visual entities improves retrieval performance [START_REF] Ounis | RELIEF: Combining expressiveness and rapidity into a single system[END_REF], not only do we characterize visual semantics, but also spatial relations linking them. For this, we consider an efficient operational model that allows relational indexing and is adaptable to symbolic image retrieval: conceptual graphs [START_REF] Sowa | Conceptual structures: information processing in mind and machine[END_REF]. In the remainder of this paper, we first present the general organization of our model and its representation formalism. We will deal in sections 3, 4 and 5 with the descriptions of the visual semantics, signal and spatial facets. Section 6 will finally specify the query framework.

The SIR Model And Representation Formalism

In state-of-the-art CBIR systems, images cannot be easily or efficiently retrieved due to the lack of a comprehensive image model that captures the structured abstractions, the conveyed signal information and the image semantic richness. To remedy such shortcomings, visual semantics, signal and spatial features are integrated within an image model (figure 1) which consists of a physical and a conceptual image level. The first layer of the SIR image model (figure 1) is the physical image level representing an image as a matrix of pixels. The second layer of the model is the conceptual layer and is itself a tri-facetted structure (visual semantics, signal and spatial facets). An image is characterized as a set of image objects (IOs), abstract structures representing visual entities. Their specification is an attempt to operate image indexing and retrieval operations beyond trivial low-level processes [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF] or region-based techniques [START_REF] Carson | Blobworld: A System for Region-Based Image Indexing and Retrieval[END_REF] since IOs convey the visual semantics, signal and spatial information at the conceptual level. In figure 1, the first IO (Io1) is linked to the visual semantics concept child and the signal (color) features skin, black and red. It is inside (a part of) and at the center of the visual entity represented by Io2. Visual semantics, signal and spatial facets will be thoroughly described in sections 3, 4 and 5. The conceptual level is supported by a representation formalism which allows to instantiate it within an image retrieval framework: conceptual graphs (CGs). Index and query images are represented by CGs and the matching function evaluating their similarity is based on the CG projection operator [START_REF] Sowa | Conceptual structures: information processing in mind and machine[END_REF]. The asset of this formalism is its flexible adaptation to the symbolic approach of image retrieval [START_REF] Mechkour | EMIR 2 : An Extended Model for Image Representation and Retrieval[END_REF][START_REF] Ounis | RELIEF: Combining expressiveness and rapidity into a single system[END_REF]. Formally, a CG is a finite, bipartite, connex and oriented graph. It features two types of nodes: the first one represented by a rectangle is tagged by a concept however the second represented by a circle is tagged by a conceptual relation. For example, the graph represents a man eating in a restaurant. Concept and conceptual relation are organized within a lattice structure partially ordered by ' ' which expresses the relation 'is a specialization of'. For example, person man denotes that the concept man is a specialization of the concept person, and will therefore appear in the offspring of the latter within the lattice classifying these concepts.

Modeling the Image Semantic Content through the Visual Semantics facet

Semantic concepts are learned and then automatically extracted given a visual vocabulary. The construction of the vocabulary is strongly constrained by the application domain [START_REF] Mechkour | EMIR 2 : An Extended Model for Image Representation and Retrieval[END_REF] and we deal in this paper with corpus of personal photographs. Starting from a set of 7 semantic concepts representing the main visual entities within personal photographs (people, ground, sky, water, foliage, mountain/rocks and building), we use WordNet to produce a list of hyponyms linked to these concepts and discard terms which are not relevant for our purpose. We obtain a set of concepts which are specializations of these 7 semantic concepts. We then repeat the process of finding hyponyms for all the specialized concepts. The last step consists in organizing these concepts (72) within a multi-layered lattice of semantic concepts ordered by a specific/generic partial order. In figure 2, the second layer of the lattice consists of concepts which are specific to the major semantic concepts, e.g. individual and crowd are specific concepts of people. The third layer is the basic layer and presents the most specific concepts, e.g. man, woman, child are specific concepts of individual. As a matter of fact, Io2 will be represented by the semantic concept water and an instance of the visual semantics facet is represented by a set of CGs, each one containing an Io type (representing an image object) linked through the conceptual relation sct to a semantic concept. E.g., graphs and are the representation of the visual semantics facet in figure 1 and can be translated as: the first IO (Io1) is associated with the semantic concept child and the second image object (Io2) with the concept water.

From Low-level Features to the Signal Color Facet

Integrating signal features within a high-level conceptual framework is not straightforward. The first step consists in specifying conceptual signal data which correspond to low-level features. We consider 11 color categories (cyan, white, green, grey, red, blue, yellow, purple, black, skin, orange) characterized in the HVC perceptually uniform space by a union of brightness, tonality and saturation intervals [START_REF] Gong | Image Indexing and Retrieval Based on Color Histograms[END_REF]. Each IO is then indexed by a quantified signal index concept (QSIC) which features its color distribution by a conjunction of color categories and their corresponding integer pixel percentages. Io1 and Io2 are characterized by QSICs <c:0,s:60,b:25,r:15…> and <c:85,s:0,b:15,r:0…>, which is translated by Io1 having a signal distribution including 60% of skin color, 25% of black and 15% of red; Io2, 85% of cyan and 15% of black. An instance of the signal color facet is represented by a set of CGs, each one containing an Io type linked through the conceptual signal relation q_si to a QSIC. The following CGs are the representation of the signal facet in figure 1:

Modeling Spatial Relations through the Spatial Facet

In order to model spatial data, we first consider a subset of the topological relations explicited in the RCC-8 theory An image object is therefore characterized by its centre of gravity io_g as well as two pixel sets: its interior, noted io_i and its boundary, noted io_b. To deal with the computation of topological relations [START_REF] Egenhofer | A formal definition of binary topological relationships[END_REF], two image objects Io1 and Io2 are characterized by intersections of their interior and boundary sets: io1_i io2_i, io1_i io2_b, io1_b io2_i and io1_b io2_b. Each topological relation is mapped to the results of these intersections, e.g. (DC, so1, so2) iff. io1_i io2_i =∅, io1_i io2_b =∅, io1_b io2_i =∅ and io1_b io2_b =∅. The interest of this computation method relies on the association of topological relations to the previous set of necessary and sufficient conditions involving attributes of spatial objects (i.e interior and boundary). The computation of directional relations between Io1 and Io2 relies on the relative position of their centers of gravity. An instance of the spatial facet is represented by a set of CGs, each one containing 2 Io types linked through the previously defined spatial relations. The following CGs are the representation of the spatial facet in fig. 1 and can be translated as Io1 overlaps and is at the center of Io2:

The Query Module

Our architecture is based on a unified fully textual framework allowing a user to query over the visual semantics, signal and spatial facets. This obviously enhances user interaction since contrarily to state-of-theart systems, the user becomes in 'charge' of the query process by making his needs explicit to the system through full textual querying (cf. [START_REF] Belkhatir | Integrating Perceptual Signal Features within a Multi-facetted Conceptual Model for Automatic Image Retrieval[END_REF] for further details). We propose an expressive and computationally efficient language consisting of boolean and quantified queries: -A user is able to associate visual semantics concepts and their related spatial relations with a boolean conjunction of color categories in a query such as Find images with a child with (i.e. wearing) red and black inside cyan water.

-'At Least' queries (Find images with a child inside pool water (At Least 50% of cyan)) and 'At Most' queries (Find images with a child inside lake water (At Most 25% of cyan)) associate visual semantics concepts and their related spatial relations with a set of color categories and a percentage of pixels belonging to each one of these categories. We specify also literally quantified queries (Mostly, Few), related to numeral quantifications 'At least 50%' and 'At most 10%' which are easier to handle by a user not interested in querying precisely with percentages. Each image (respectively user query) is represented by a global CG resulting from the aggregation of CGs over the visual semantics, signal and spatial facets called document index graph (respectively query graph). The evaluation of similarity between an image and a query is achieved through a correspondence function: the CG projection operator. This operator allows to identify within a graph g 1 sub-graphs with the same structure as a given graph g 2 , with nodes being possibly restricted, i.e. their types are specialization of g 2 node types. If it exists a projection of a query CG Q within a document CG D then the document indexed by D is relevant for the query Q. As far as implementation is concerned, optimizations related to the organization of index data structures have been developed allowing to process this operator in polynomial time within a given application domain [START_REF] Ounis | RELIEF: Combining expressiveness and rapidity into a single system[END_REF].

CONCLUSION

We have specified a multi-facetted architecture for image retrieval instantiated by an operational model based on the CG formalism. The latter allows to define an image representation model and a matching function to compare index and query image graphs. We have specified image objects, abstract structures representing visual entities within an image in order to operate image indexing and retrieval operations at a higher level of abstraction than state-of-the-art frameworks. We have described the visual semantics, signal and spatial facets that characterize the conceptual information conveyed by image objects and have finally proposed a unified and rich framework for querying over visual semantics, signal and spatial features.

Figure 1 .

 1 Figure 1. Image model.

Figure 2 .

 2 Figure 2. Lattice of Semantic Concepts.

[ 3 ]

 3 ; 3 relations which are exhaustive and relevant for image querying are chosen. Considering 2 IOs (Io1 and Io2), these relations are (P,Io1,Io2): 'Io1 is a part of Io2', (T,so1,so2): 'Io1 touches Io2 (externally connected or overlaps)' and (D,so1,so2): 'Io1 is disconnected with Io2'. Let us note that they are mutually exclusive and present the important property that each pair of IOs is linked by one and only one topological relation. Directional relations Right(R), Left(L), Above(A), Below(B) and the global relation Center(C) are invariant to basic geometrical transformations (translation, scaling).

Io1

Semantics/Signal integration for image retrieval