Guillaume Joutel
email: guillaume.joutel@insa-lyon.fr

Véronique Eglin
email: veronique.eglin@insa-lyon.fr

Hubert Emptoz

A complete pyramidal geometrical scheme for text based image description and retrieval

Introduction

Digital Paleography and image analysis

In this work, we are interested in digitized Middle-Age (composed by copyists' texts from the 9 th to the 15 th century) and Humanistic manuscripts (essentially composed by authors' drafts from the 18 th and 19 th century) analysis. It is dedicated to palaeographers and historians to help them in their everyday work of manuscripts dating, expertise and authentication, see figure 1. One of the primary difficulties faced by palaeographers is the classification and identification of hands, and this is an area which has already received a good deal of attention in other disciplines. Specifically, the community of forensic document analysts have been working for several years now to develop computer-based systems for retrieval, identifying and classifying modern handwriting, and this begs the question whether such work can be applied to medieval writing as well. In that context, we need an original approach to answer the opposite questions raised by those two kinds of documents from the medieval and the humanistic collections. In the first case, the objective is to find writer independent and style dependent primitives for Middle-Ages manuscripts page images retrieval, while for humanistic manuscripts, the objective is to find writer dependent primitives for an identification task. The answers to those objectives are complex. We propose in this paper a contribution to this challenge that must be considered as a tool kit for historians and medievalist palaeographers to help them in their work of manuscripts dating, expertise and authentication. Due to the fact that palaeographers judge that the curvature and the orientation are two fundamental dimensions of handwritings, we have searched a way to compute them on the shapes for both collections. To compute those dimensions, we have developed a methodology that is sensitive to variations at the frontiers of shapes, that pays attention to the evolution of these criteria at different scales, that reveals the variability of shapes and their anisotropy, that is robust to disturbed environments (presence of disturbed backgrounds, of partial shapes…) and finally, that doesn't require prohibitive costs of treatment nor great storage volume for each analyzed page image. Our choice relates to a redundant multi-scale transform: the Curvelets transform that is more robust than wavelets for the representation of shapes anisotropy, of lines segments and curves in the images. The proposed solution lies for a great part on an original indexing and navigation system that contributes to different objectives: handwritten documents retrieval from the same writer, writers' identification, middle-age handwriting clustering. • The writing styles clustering that is based on the production of a cross-scale features vector for each handwritten samples and that contains a set of statistical measures from the different multiscale coefficients distributions. This clustering is based on an unsupervised classification scheme that groups palaeographical handwritten styles into visual coherent handwriting families. • The spotting and the shape retrieval by similarity that lies on the analysis of the curvature and the orientation from the finest scale of the decomposition of the image. • The CBIR that is also based on the finest scale analysis and on the production of an unique and characteristic digital signature for each handwritten samples. In this paper, we focus on the application of CBIR that is based on a direct comparison between a request image, considered by its digital signature and all off-line signatures for the rest of the database images. The similarity criterion is a weighted value of correlation between the request signature and each individual signature of the images of the database.

Content based information retrieval for handwriting images databases

The simplest scenario of content based image retrieval is the one of global example-based search: the user chooses an image example and the system determines the images of the base with the most similar visual appearance. The principle of this approach has been established by Ballard in 1991, [Ballard]. It is the fundamental principle of a lot of systems that deal with natural images, like QBic from IBM (Flickner 1995), PhotoBook from the MIT (Pentland 1994), MARS (Multimedia Analysis and Retrieval System), PicToSeek, Ikona and the KIWI system, [START_REF] Loupias | Key Points based Indexing for Pre-attentive Similarities: The KIWI System , Pattern Analysis and Applications[END_REF]. All those systems are sharing the same kinds of features for a global content based document images retrieval (colors, shapes and textures). In the specific field of CBIR dedicated to textual (printed or handwritten) document images, different specific (structural, geometrical or statistical) features and similarity measures have also been proposed, [START_REF] Journet | Ancient Printed Documents indexation: a new approach[END_REF], [START_REF] Moalla | Contribution to the Discrimination of the Medieval Manuscript Texts[END_REF]. But all of them have a common point: they are focused on the same property of images: the information is concentrated in linear shapes and their contours.

II Different ways to characterize handwritten shapes

II.1. Related works

The need for searching scanned handwritten documents are involved in application such as collections dating, works genesis, erudite study, critical edition, documents authentication… Recently Srihari et al. in [START_REF] Zhang | Binary vector dissimilarity measures for handwriting identification[END_REF][START_REF] Zhang | Word image retrieval using binary features[END_REF] have realized the importance of handwritten document retrieval and have presented their retrieval system that is dedicated to forensics applications such as writer identification. Different distances are currently used to access the best matching between different set of handwriting samples, [START_REF] Cha | Multiple Feature Integration for Writer Verification[END_REF]. Discriminability of a pair of writing samples based on similarity value can be observed by studying their distributions when the pair arises from either the same writer or from different writers. Generally, in most writers' classification approaches, authors try to produce a set of exhaustive graphical characteristics which can efficiently describe all handwritings families. In handwriting classification which is our main goal, the most closely related works are [START_REF] Crettez | A set of handwriting families: style recognition[END_REF] and [START_REF] Zhang | Word image retrieval using binary features[END_REF]. In [START_REF] Crettez | A set of handwriting families: style recognition[END_REF], authors propose an analysis of the variability of handwritings on the bases of two kinds of observations: firstly the thickness of the tracing and the spatial density of characters and secondly the successive directions of the tracing. This work has been led on contemporary documents only. The only work relative to the analysis of the Middle-ages documents referenced in [START_REF] Aiolli | SPI: a System for Palaeographic Inspections[END_REF] proposes classifications procedures which are today debatable by palaeographers. Some recent studies have tried to develop more robust approach for a non supervised classification. In [START_REF] Moalla | Contribution to the Discrimination of the Medieval Manuscript Texts[END_REF] for example, authors are interested in ancient Latin and Arabic manuscripts of the Middle-Ages before the emerging of the printing. They made the choice to analyze statistically the whole image of a manuscript and measure globally all patterns. This approach should guarantee the independency from the text content, the writer's personal style; the language used and the letters frequencies. It is difficult to pretend to be exhaustive in the description of handwritten shapes for the retrieval, so it is essential to work with expert users who are able to validate the measures that appear to be the most relevant. The signification degree that is assigned by the user could also guide the system to create a suitable distance between writing classes. In any cases, each computed measure should be evaluated in relation with all others. In this case, a Principal Component Analysis (PCA) considerably reduces the dimensionality of micro-features vectors, [13]. Within this kind of generic approach, it is possible to classify handwriting samples into visual distinct style classes. General methods are either based on the consideration of local particular graphemes [START_REF] Bensefia | Identification du scripteur par représentation graphèmes[END_REF] or on a too macroscopic and general characterization that is not always efficient for a complete writers' authentication, [START_REF] Bulacu | Writer style from oriented edge fragments[END_REF], [START_REF] Moalla | Contribution to the Discrimination of the Medieval Manuscript Texts[END_REF]. In our proposition, we lead a Curvelets based analysis for a designed decomposition in curvature and orientation which have a real sense for palaeographers. Our contribution differs from the cited works because it is dedicated to both Middle-Ages and contemporary handwritings documents. Moreover it uses a geometrical multiscale decomposition: the Curvelets, which has never been used in this context.

II.2. A new interesting way: the geometrical decompositions

In the handwriting images, the discontinuities points are essentially gathered on the shapes' outlines that contain the maximum of the visible information. It is an information that can be analyzed both globally (orientations of outlines, presences of particularly striking and redundant curvatures), and locally (the discontinuities are situated in very sensitive locations in shapes contours where experts pay generally their attention to recognize or identify a writing). A mixed approach that combines global and local shapes description seemed to be an interesting way for handwriting images analysis. But we have noticed that all decompositions can not decorrelate both local and global images properties with the ability to localize all discontinuities in the image space. Fourier Transform is a powerful tool for analysing the global regularity of a function but it does not allow recognizing discontinuities points. It doesn't allow a local shape analysis and doesn't take advantage of multiscale correlations that exist in lines based images. Orthogonal wavelets provide frames that allow sparse representation (with only few coefficients) of images but present also a lack of directional characteristics for regular curves description and geometry. We are precisely interested here in the families of redundant transforms which allow to decompose the image into directed sub-bands and to capture the geometry in the shapes contours by the agglomerates of coefficients. We can give as example, the Xlets (i.e. contourlets, bandelets, complex wavelets and oriented wavalets. Among this family, we have chosen one specific X-lets: the Curvelets that have been introduced by Candès. They offer a set of the properties of directionality and good joint location of the shapes geometry. Ridgelets and Curvelets transforms that we defend here have been imagined to bypass wavelets disadvantages.

II.3 The Curvelet Transform -from continuous to discrete

General Properties of the continuous Curvelet Transform. The Curvelet transform is a multiscale multi-orientation transform with indexed atoms in location, scale and direction. The figure 3 shows the anisotropic Curvelet transform of Candès [START_REF] Candès | Curvelets: A Surprisingly Effective Nonadaptive Representation of Objects with Edges[END_REF] of an image of our palaeographical database. On this figure, the transformation contains 4 scales with all coefficients, each one being of the same size as the original image. The combination of all images with all missing scales (not represented here) reproduces with redundancy the original image. A study of the Curvelets coefficients properties, shows that the high valued coefficients tend to gather around the objects corners and contours in the image, what seems to be natural because there is a strong dependence between Curvelets coefficients from a scale to the other and for a given neighbourhood for various given scales and orientations. These dependences have been quantitatively verified by measuring the mutual information, [START_REF] Boubchir | Bayesian Denoising Based on the MAP Estimator in Wavelet-domain Using Bessel K Form Prior[END_REF]. Conceptually, the Curvelet transform is a multi scale nonstandard pyramid because Curvelets have geometric features that set them apart from wavelets and the likes. Curvelets obey a parabolic scaling relation which says that at scale 2 -j , each element has an envelope which is aligned along a ridge of length 2 -j/2 and width 2 -j . Mathematically, if one works in R 2 , we have first to consider a radial window W(r) and then an angular window V(t) where r and t are polar coordinates in the frequency domain. These are both smooth, nonnegative and real-valued, with W taking positive real arguments and supported on r ∈[1/2,2] and V taking real arguments and supported on t∈[-1,1]. These windows will always obey the admissibility conditions:

Then, for each j≥ j 0 , a frequency window U j is defined in the Fourier domain by where |j/2| is the integer part of j/2. The support of U j is a polar wedge with the support of W and V, the radial and angular windows applied with scale-dependent window widths in each direction. In Fourier space, Curvelets are supported near a "parabolic" wedge, and the shaded area represents such a generic wedge, see figure 4. In practice, we have privileged the new wrapping-based curvelet transform proposed by (Candès, 2002) that simplifies the calculation and increases the redundancy of the coefficients

III Off-line decomposition for the CBIR application

Interest textual regions selection. In textual regions of document images, lines orientations are globally regular near to the horizontal. This orientation can be detected at a low scale : the map of textual information is revealed by high Curvelets coefficients while other coefficients have been ignored. Of course, at this resolution of image, we have lost a part of precision in this detection that has been easily compensated by the detection of the background map that has been introduced in Ramel's work in [12].

Signatures construction, evolution and comparison. The Curvelet transform gives us an analysis of pixels for several scale and several orientations. We only focus here on the highest scale of the decomposition and only cumulate information relative to shapes contours. The principle of curvature estimation is described as follows: one pixel on a curve can be potentially detected in several orientations depending of the curve. Each Curvelets coefficient corresponding to this pixel in a detected orientation is hen compared to all other detected orientations of the same pixel. We only retrieve the more significant coefficients values. Finally, the number of significant orientations gives us an evaluation of the overall curvature of a pixel, as it has been presented in [START_REF] Antoine | Measuring a curvature radius with directional wavelets[END_REF] by J-P Antoine From the orientations recovery and curvatures computation, we define a signature for each handwriting fragment. The signature is defined as the matrix of couple occurrences (curvature, orientation). Because we do not want to normalize our images before the decomposition, we have searched a way to normalize the signature. To do so, we keep in the normalized signature the ratio between every value in the original signature and the global amount of information of this signature. The only difficulty with this definition is that some coordinates in the signatures are common toalmost all handwritings (presence of high values in the horizontal and vertical directions): we compensate this phenomenon by reversing ratios in the signature, i.e. by accentuating weakly represented couples (orientation, curvature). Figure 5 presents an example of matrix plotted as a pixel image for a Middle-Ages and a 18 th author handwriting image. In our retrieval system, the distance between the queried signature and each signatures of the database is calculated using a normalized correlation similarity. The similarity measure S(X,Y) between two image X and Y is defined as follows: S(X,Y)=Cov(X,Y)/σ x σ y, where cov(X,Y) is the covariance between X and Y and σ x and σ y the standard deviations. In order to know how our signature reacts to several possible deformations in a handwriting manuscript, we have led five kinds of tests: the horizontal and vertical stretching of text, the resolution changing, the letters' dimensions zooming and the lines' spaces changing. To have significant results, we have chosen to keep the same image dimensions after each deformation. The only general conclusions are presented here. Firstly, studying (vertical or horizontal) stretching, the signature's behaviour is exactly what we were expecting: i.e. a general shifting of values of couples (curvature, orientation) towards the orientation of the stretching (0° for horizontal and 90° for vertical), a general decreasing of curvatures and a great fall of the correlation coefficients between the original image and its successive deformations. In fact, the horizontal and the vertical directions are the two main dimensions in Latin handwritings. So modifying those dimensions led to great changes in the signatures design. Concerning the resolution and the letters' dimensions changes, we can take advantage on the presence of different scales in the decomposition of the Curvelets that stabilize the signature. The Curvelet transform offers the possibility to choose the best scale for the signature design depending on the initial image resolution and characters size. Lastly, modifications of the spaces between lines entail real consequences on the signature only when the amount of information is no more comparable. In an image with about ten lines of medieval text, if one removes or adds two or three lines, the rate of recognition is maintained.

IV The CBIR application: experimentation and quantitative evaluation

In this part, the test setup and the experimental results obtained for the image retrieval task are described. The images have been divided into two groups: one group is composed by known handwriting images and the second group is composed by queried images for testing. We have tried to test our retrieval system on two databases (over 800 images): the humanistic and the Middle-Ages databases (composed by manuscripts of the database of the IRHT and of European 18th century correspondences corpus (CERPHI)). In retrieval system, the performance is subjective and its evaluation is difficult, especially for the Middle-Ages base where we do not have precise information concerning Middle-Ages European handwriting dating process. The set of known images is selected and the image retrieval process is carried out against this set of known handwritings. In each case, we compute the average precision and the recall values for each database.

As we can see on figure 6.1 (middle age) the P/R curve tends to stabilize around a precision rate of 0,6 which is not a very high value but we have proceeded by unfavourable deductions that consists in counting as false answers all images that are not surely recognized as being similar to the request. This is due to the tha lack of certain ground truth about classification of the middle age database. The classification of our base is still in progress by palaeographers of the IRHT. On the other hand, on the figure 6.2 (humanistic), we can see that our system has exactly the same behaviour that we expected. In fact those rates are certainly the best that we can have, compared to other CBIR systems. Fig. 6. Average precision and recall curves in the middle-age (6.1) and the humanistic (6.2) database.

To have a better evaluation of our system, we have used a F-measure which combines the precision and the recall values (F=2P.R/(P+R)) and provides a single measure of the retrieval accuracy: it is the Harmony mean of precision and recall value. For the humanistic base, in the top 15 ranks, the F-measure is 96,61 (P=1 and R=93). This implies that considering the top 15 results supports high precision and recall measure. For the Middle-Ages base this value is 51,43.

Conclusion

We can say with confidence that Curvelets Transforms can be used as a general technique for feature detection. In the specific case of handwritings that we study, the hypothesis that curvature and orientation are fundamental dimensions of shapes seems to be validated by our CBIR system and its recall values. The system is currently integrated to the platform of the Graphem Project dedicated to paleographer experts. The two other on-line applications that are also based on the Curvelet geometric decomposition (spotting and writing styles clustering) are currently under development.

Fig. 1 .

 1 Fig. 1. Complex handwriting documents images from different periods (13 th and 18 th century)

Fig. 2 .

 2 Fig. 2. Pyramidal architecture for the handwriting characterization and on-line applications. The first part presents an off-line Curvelet based decomposition that lies on the exploitation of the distributions of Curvelet strong coefficients through different scales: the lowest scales for the estimation of interest text areas, the middle and highest scales for the computation of digital signatures of homogeneous text fragments. The digital signatures are the 2D representations of all couples of values (curvature, orientation) obtained by the Curvelets decomposition. Three applications have then been investigated by exploiting this off-line decomposition:

Fig. 3 :

 3 Fig.3: Curvelet Transform of an image of the Palaeographical database (IRHT-Paris).

Fig. 4

 4 Fig.4 Elongated anisotropic support of the Curvelets defined by its parabolic dilation in polar frequency domain coordinates. Curvelet tiling of space and frequency. Representation of the increasing number of angular sectors with scale changing. Procedural definition and implementation of the discrete version. The proposed Curvelets decomposition uses a combination of reversible operations: a sub-bands decomposition of the original 2D signal followed by a regular and normalized partitioning of images for each subband and then the application of a local Ridgelets transform on each partition.

1 /

 1 Do the FFT of the initial image I 2/ Resample the frequential Cartesian space into recto-polar coordinates 3/ For each radial indexed • n line do the inversed Fourier Transform: so as to obtain the Radon Transform {Rad(• n , t n )} n=1..N for each • n angle and then realize the wavelet 1D transform in the spatial domain. 4/ The inverse Ridgelet transform realizes all successive inversed transforms on each step. 5/ Initialize the subband decomposition for the Curvelet transform step. 6/ Compute a local Ridgelet transform on each subband.

Fig. 5 .

 5 Fig.5. Signature of a Middle-Ages handwriting samples of the IRHT database and on a fragment extracted from the Georges Washington's digital collection.

This study has been supported by two projects: the ANR GRAPHEM

2007-2010 project between the IRHT (Institut de Recherche en Histoire des Textes), the Ecole des Chartes from Paris and the LIRIS and the regional Cluster 13 Project: "Inheritage, culture, Creation", 2005-2009 in collaboration with the CERPHI of Lyon (Centre d'Etude en Rhétorique, Philosophique et Histoire des Idées).

We now describe a strategy for realizing a digital implementation of the Curvelet transform. The proposed implementation of the Curvelets decomposition has been suggested by Candès and Starck and constitutes the most common version. The successive simplified steps of the algorithm are listed below:


Gilles Guette
email: fgilles.guette@irisa.fr

Bernard Cousin
email: bernard.cousin@irisa.fr

Fort

Algorithm for DNSSEC trusted key rollover

The Domain Name System Security Extensions (DNSSEC) architecture is based on public-key cryptography. A secure DNS zone has one or more keys and signs its resource records with these keys in order to provide two security services: data integrity and authentication. These services allow to protect DNS transactions and permit the detection of attempted attacks on DNS. The DNSSEC validation process is based on the establishment o f a c hain of trust between zones. This chain needs a secure entry point: a DNS zone whose at least one key is trusted. In this paper we study a critical problem associated to the key rollover in DNSSEC: the trusted keys rollover problem. We propose an algorithm that allows a resolver to update its trusted keys automatically and in a secure way without any d e l a y o r a n y break of the DNS service.

Introduction

During the last decade, the Internet Engineering Task Force (IETF) has developed the DNS security extensions (DNSSEC). The rst standard document designing DNSSEC is the RFC 2535 Eas99]. Many R F Cs and drafts have u pdated the RFC 2535 and according to the experience given by implementations, this protocol is today enhanced ALMR04] AAL + 04a] AAL + 04b].

The DNSSEC architecture uses public key cryptography t o p r o vide integrity and authentication of the DNS data. Each node of the DNS tree, called a zone, owns at least a key pair used to secure the zone records with digital signatures.

In order to validate DNSSEC records, a resolver builds a chain of trust Gie01] by w alking through the DNS tree from a secure entry point KSL04] ( t ypically a top level zone) to the zone queried. Each secure entry point (SEP), is statically con gured in a resolver: the resolver knows at least one key of the zone which i s taken as SEP, this key is called a trusted key. A resolver is able to build a chain of trust if it owns a secure entry point for this query and if there are only secure delegations from the secure entry point to the zone queried.

The lifespan of keys used to secure DNS zone is not in nite, because old keys become weak. Consequently, the zone keys must be renewed periodically, t h a t i s to say a new zone key is added to the zone le and an old one is deleted from the zone le. This process is called key rollover GC03].

Key rollover only updates keys on the name server, resolvers that have c o ngured the old key as trusted are not noti ed that this key has been deleted.

Consequently, the static key con guration in a resolver raises some problems of consistency between keys deployed in a zone and trusted keys con gured in a resolver for this zone.

In section 2 we present the notations use in this paper and the DNSSEC validation process. Then, in section 3 we describe the trusted key rollover problem and nally we p r e s e n t our solution to this problem in section 4.

2 The validation process in DNSSEC

Notation

In this subsection are explained the notations used in the document.

{ A DNS domain X is the entire subtree beginning at the node X. { A DNS zone is a node of the DNS tree. A zone name is the concatenation of the node's label from its node to the root of the DNS tree. A zone contains all the not delegated DNS names ended by the zone name. For example, the zone example.com. contains all the not delegated names X.example.com. where X can be composed by s e v eral labels.

{ A zone can delegate the responsability of a part of its names. For example, the zone example.com. can delegate all the name ended by { DNSKEY (key1) is the RR which describes the key named key1. { RRSIG(X) y is the RR which is the signature of the RR X generated with the private part of key y.

{ A trusted key is the public part of a zone key which has been con gured in a resolver.

{ A Secure Entry Point is a zone for which the resolver has con gured a trusted key.

The DNS entities and de nitions

Three entities with distinct role are present in the DNS architecture: the name server, the resolver and the cache server (see Moc87,AL02]).

The name server. The cache server. The cache server is not authoritative o n a n y zone. The scalability of DNS is based on the use of cache servers. These cache servers only forward queries and cache the responses when these are valids.

The DNSSEC Chain of Trust

DNS security extensions de ne new resource records in order to store keys and signatures needed to provide integrity and authentication. Each secured zone owns at least one zone key, the public part of this key is stored in a DNSKEY resource record. The private part of this public-key is kept secret and should be stored in a secure location. The private part of the key generates a digital signature for each resource record in the zone le. These signatures are stored in a RRSIG resource record. A resource record is considered valid when the veri cation of at least one of its associated RRSIG RR is complete. Figure 2 shows the signature veri cation process.

In order to verify the signature of a resource record, the resolver cyphers the RRSIG RR with the public key contained in the DNSKEY RR of the zone. If the result of this operation (Resource Record') a n d the Resource Record present in the DNS response message are the same, the signature is veri ed. The resource record is valid.

During the signature veri cation process, the zone key is needed and must be veri ed too. In order to trust a zone key, DNSSEC uses the DNS-tree model to establish a chain of trust Gie01] beginning from a secure entry point KSL04] t o the queried zone. To create this chain, a veri able relation between child zone and parent zone must exist: this is the role of the Delegation Signer resource record (DS RR) Gun03]. This record, stored in the parent zone, contains information allowing the authentication of one child zone key. F i g u r e 3 s h o ws the validation of a delegation. DNS answer message from the parent zone

DNS answer message

The chain of trust is broken

Figure3. The delegation veri cation process.

Once the signature of the DS RR provided by the parent zone and the signature of the DNSKEY provided by the child zone are veri ed, the resolver checks that information contained in one DS RR identi es one key in the child zone. If one DS RR identi es one DNSKEY RR in the child zone, one link of the chain of trust is built and the name resolution continue to secure the next link in the DNS tree. If there is no valid DS RR that identi es one valid DNSKEY RR in the child zone, the chain of trust is broken and the name resolution is unsecure.

The Delegation Signer model introduces a distinction between two t ypes of key: the Zone Signing Key (ZSK) and the Key Signing Key (KSK). A ZSK signs all types of record in the zone le and a KSK signs only the DNSKEY RRs present in the zone le. This distinction minimizes the burden produced when a key is changed in the child zone, because only KSKs have an associated DS RR in the parent zone le. Hence, a DNSKEY RR can only be considered valid by the veri cation of a signature generated by a K S K .

The trusted key rollover problem

The validation process of resource records based on the DNSSEC chain of trust needs a secure entry point to start. The RFC 2535 Eas99] speci es that a DNSSEC resolver must be con gured with at least a public key which authenticates one zone as a secure entry point. If DNSSEC is totally deployed on the whole DNS tree, only one secure entry point is su cient, i.e. the root zone. But due to deployement constraints, the current model that seems to emerge is an island of security model with DNS zones and DNSSEC zones at the same time in the DNS tree. An island of security is a subtree of the DNS tree totally secured with DNSSEC (each zone of this subtree has a signed zone le). Consequently, a resolver needs at least one secure entry point for the apex of each island of security in order to perform secure name resolution for any z o n e .

Moreover, to maintainagoodlevel of security, z o n e k eys have to be renewed at regular intervals, to prevent against key disclosure. And consequently, t r u s t e d keys must be updated in resolvers to keep consistency between the key in the zone le of a name server and the trusted key in the resolvers.

Currently, the rollover of a trusted key in the resolver's con guration le is done manually by the administrator, this implies risks of miscon guration and an interruption of the service between the moment the zone rolls its keys and the moment t h e administrator changes the resolver's con guration le. At the present time, there is no automated trusted key rollover. When a zone decides to renew one of its zone keys, there is no mechanism to notify the resolvers that this key is going to be removed from its zone le. When a key is removed from its zone le, all resolvers that have con gured this key as trusted fails all DNSSEC validation using this key.

Without an automated procedure to notify resolvers that a trusted key is going to be removed, name resolution can fail at any time even if a chain of trust exists from the root to the resource record queried.

In the next section, we propose a modi cation of the DNSKEY resource record and an algorithm to automatically update the trusted keys present i n t h e resolver con guration le. Figure4. The DNSKEY resource record wire format.

Only two bits of the Flags eld are used. These bits are the seventh bit and the fteenth bit. Bit 7 of the Flags eld is the Zone Key ag. If bit 7 is set, then the DNSKEY record holds a DNS zone key. I f b i t 7 h a s v alue 0, then the DNSKEY record holds some other type of DNS public key (such as a public key used by TKEY Eas00]). Bit 15 of the Flags eld is the Secure Entry Point ag, described in KSL04]. If bit 15 has value 1, then the DNSKEY record holds a key intended for use as a secure entry point. The other bits of the eld, bits 0-6 and 8-14 are reserved: these bits must have v alue 0.

The Protocol eld speci es the algorithm allowed to use the DNSKEY RR. Since the publication of the RFC 3445 MR02] this eld must have v alue 3.

The Algorithm eld identi es the public key's cryptographic algorithm and determines the format of the Public Key eld that holds the public key material. The format depends on the algorithm of the key being stored.

We propose to call the under changes bit, the rst of the reserved bits of the Flag eld and to give this bit the following meaning: when this bit is set the key contained in the DNSKEY RR is under changes and is going to be removed from the DNS zone le.

The automated trusted key rollover algorithm

When a zone renewed one of its keys, it sets the under changes bit in the DNSKEY RR containing this key. Piece of advice for the duration of the rollover period must be found in KG04].

During the rollover period, when a resolver asks for the DNSKEY RR, it retrieves the resource record with its under changes bit set. Three distincts periods could be de ned for each k ey: before the rollover of the key, during the rollover of the key and after the rollover of the key. Before and after the rollover, the key is not under changes so the bit is not set. During the rollover the under changes bit is set to one. When a resolver receives a DNSKEY RR with the under changes bit set, it checks if this key is con gured as trusted. If this is not the case, this key rollover will have no impact on the resolver behavior and the resolver must continue normally the current name resolution. If the received key is a trusted key for the resolver, it tries to validate another key of the zone (see section 4.3). If it succeeds, the old key is removed and the new key is added in the resolver con guration le. If the new key validation fails, the resolver raises a warning and the change in the resolver's con guration le must be made manually by the administrator.

On some resolvers, requests on a given zone could be largely spaced out, more than one month for example. Consequently, a resolver can perform no name resolution on a zone during the rollover period of a trusted key. This implies that the trusted key con gured in such resolver may h a ve been renewed and removed from the zone le during this period of resolver inactivity. Figure 6 shows the two cases that can arise: the resolver has another trusted key belonging to an ancestor's zone of the zone that has changed its zone key, o r the resolver has not such a t r u s t e d k ey. The left part of the Figure 6 is the best case resolver behavior presented in Figure 5, the right part takes into account the reception of a DNSKEY RR with the under changes bit not set.

If the under changes bit is not set the resolver performs name resolution normally. If the name resolution fails the resolver must try to update its trusted keys using another key for the name resolution. If the resolver cannot performed a DNSSEC resolution either because it has no valid trusted key or because the resolution is not secure (some data are retrieved from unsecured DNS zone) the resolver can not update its con guration le and the trusted key update must be made manually.

Algorithm presented on Figure 6 shows that in some cases a manual administrative action is needed and a totally automated solution does not exist. This is due to possible miscon guration in any DNS zone or due to the possibility f o r a resolver to not have s e n t query to a zone during its rollover period, and hence, to not have received the noti cation of key changes.

Security considerations and validation of a new trusted key

Automated update of trusted keys in a resolver is a critical mechanism for DNSSEC and must be resistant to compromised key. An attacker that owns a compromised key can try to place new fake k eys as trusted in a target resolver using the automated trusted key rollover mechanism, as describe now.

Firstly, the target resolver has a trusted key set including the compromised key. Then, the attacker sends a forged message containing the compromised key having the under changes bit set, new fake k eys and their signatures. Finally, the resolver checks the signatures of the keys, one of these keys is trusted (but compromised) and validates some signatures. The resolver discards the old key and accepts the new fake k eys sended by the attacker.

To protect the automated trusted key update from this attack, we de ne a requirement for the acceptance of a new key depending on the security l e v el that the resolver's administrator wants.

To accept a new key, the resolver checks the signatures of the DNSKEY

RRset it has received. The normal validation process succeeds if at least one signature is valid, but this is not enough to ensure security because the compromission of only one key allows the attack on the resolver to be fruitful. So to be resistant t o k ey compromission the resolver must accept a new key only if k signatures generated by the trusted key owns by the resolver for this zone are valid. If one of this signature is not correct the resolver rejects the new key.

If the resolver has n trusted keys for a given zone, our automated trusted key rollover resists to n ; k compromised keys. Because, an attacker that owns n ; k compromised key for this zone can only generate n ; k valid signatures and the resolver will accept new keys only if there are n valid signatures. Some local policy parameter may be de ned by administrators to ensure a su cient level of security. This parameter de nes the number of trusted keys an administrator wants to con gure to a given zone. If an administrator wants a low security l e v el, he sets this parameter to one and con gures only one trusted key for a zone. But, if he wants a higher security l e v el he sets this parameter to any n umber included between 2 and the numberofkeys present in this zone.

Moreover, a resolver removes or accepts keys as soon as the DNSKEY RRset is received, our method does not implies extra delays or time constraints for resolvers or servers during the rollover period.

5 Related work

Description

Recently, Mike St Johns has published an IETF draft StJ04] describing a method for automated trusted key rollover. This draft de nes a revocation bit in the Flags eld of the DNSKEY resource record. When this bit is set, it means that the key must be removed from resolver's trusted key set. This revocation is immediate. Figure 7 shows the principles of this method.

Firstly, t h e r e s o l v er sends a query about a DNS name ① and receives DNSKEY RR with the revocation bit set. The revocation is immediate and the resolver updates its trusted keys set ②. To avoid attack when a key is compromised, the resolver starts a timer of 30 days and keeps a trace of all the keys that signed the DNSKEY RRset ③. If the resolver received a response containing a DNSKEY RRset without the new keys but validly signed before the expiration of the timer, the resolver considers this information as a proof that something goes wrong (attack or miscon guration). Consequently, it stops the acceptance of the new keys and resets the timer. Figure7. Acceptation method with 30 days timer.

In the same way, if all the keys that have signed the DNSKEY RRset is revoked before the timer expiration, the resolver stops the acceptance of the new keys. Once the timer expires, the next time the resolver receives a valid DNSKEY RRset containing the new key it accepts this key as trusted ④.

Comparison

The major problem with the method described in the draft StJ04] is that it introduces extra delay (30 days) and requires a lot of management precaution for the zone administrator. Indeed this method implies a lot of constraints about the minimal numb e r o f k eys in a zone, the numb e r o f t r u s t e d k eys and the rollover frequency due to the 30 days timer.

Moreover, with this method, when a server creates a new key, this key is pending and can not be used during 30 days after its creation. This implies that if a zone owns n keys and rolls a keys every 30 n;1 days, all resolvers will be unable to update its trusted key set for this zone.

Our method does not su er from this problem because acceptance and revocation of keys are made as soon as the DNSKEY RRset is received. Our method does not imply changes or constraints for the DNS authoritative server management.

Conclusion

In this paper we h a ve presented the trusted key rollover problem and we h a ve proposed a protocol modi cation and an algorithm for resolvers to solve the trusted key rollover problem. The automation of the trusted key rollover allows to avoid break in the DNS service due to miscon gurations and allows to minimize the work overload for administrators. We h a ve exposed that in some case the trusted key rollover cannot be automated and the modi cation of the conguration le must be done manually. These cases arise seldom and are limited to machines that do not perform name resolution during the rollover period. Moreover, the algorithm described in this paper is resistant to compromised key and places the choice of security l e v el in the resolver's administrator side, which is a natural way to protect a resolver.

Figure1.

  Figure1. DNS domain and DNS zone.

  Figure2. The signature veri cation process.

4

  Figure4shows the DNSKEY resource record format.

FailureFigure5.

  Figure5. The best case resolver behavior.

Figure6.

  Figure6. The complete resolver behavior.

  test.example.com. to a new zone. This zone is named the test.example.com. zone (Fig 1).

	Delegations	.			domain	com.
	fr.	edu.	com.			zone	com.
	zone	bar.com.	foo.	bar.	example.		zone	example.com.
	zone	foo.com.		test.
			zone	test.example.com.	(delegated)


Robert Laurini

Silvia Gordillo

Françoise Raffort

Sylvie Servigne
email: sylvie.servigne@insa-lyon.fr

Gustavo Rossi

Nan Wang
email: nan.wang@insa-lyon.fr

Andrés Fortier

Francoise Raffort

A Primer of Picture-Aided Navigation in Mobile Systems

Keywords: GIS, images, explaining itineraries, Location-based Services, Physical Hypermedia

The goal of this paper is to present a new concept regarding the way of explaining itineraries based on pictures in mobile systems. Instead of presenting a map, or a list of words, an original method is proposed based on a picture database and handheld devices. Knowing the exact position of the user, the system will sent him regularly pictures of the way where to go. This system is especially targeted not for drivers but for pedestrians essentially in tourist cities.

In order to reach this objective, pictures were taken along each street both ways. Thus, a picture database was built for which the more common query is to compute the minimum path for going from one place to another. The result format is initially presented as a sequence of nodes and edges; then this sequence is transformed into a sequence of pictures. Those pictures are then sent to the user according to his position and his pace. In order to help the user, the pictures are decorated with arrows.

This presentation is based on two prototypes made within a French-Argentinean collaboration.

INTRODUCTION

Suppose you are lost in a Chinese city and you want to go to a precise place: textual or oral descriptions are not very efficient, and similarly a map is not of interest because you cannot read the names of the streets. More generally, there exist several modes of describing itineraries, each of them having their own advantages and drawbacks. The objective of this paper is to propose a new mode of describing itineraries, i.e. based on sequences of pictures.

If somebody gives you, or a computer generates a text explaining how to go from one place to another, you need first to understand the text, and second to build your own visual representation of the space in your mind in order to follow the explanations.

In the case of a vocal description, it is common to forget what has been said, especially when the itinerary is complex. In the case of maps, you can follow the itinerary easily, even if you are lost; however a lot of people have difficulties in reading maps.

We consider that giving an itinerary by a sequence of pictures can be a powerful mean to help pedestrians go from one place to another. Our vision is that for tourists or pedestrians equipped with a handheld device (PDA, smart phones, etc.) such a description mode can be useful equally outdoor and indoor provided that a lot of pictures have been taken, and that the pedestrian is correctly positioned with a mobile system, thus creating a sort of picture-aided navigational system (PANS). To do so, we assume the existence of a communication infrastructure covering the whole territory, for instance a tourist city, both indoor and outdoor. In other words, the initial goal of such a system is not oriented to car-drivers for long itineraries, but rather for short itineraries in a city.

In addition, let us mention that such a system can be used as a component for several types of Location-Based Services [START_REF] Küpper | Location-Based Services: Fundamentals and Operation[END_REF], [START_REF] Schiller | Location-Based Services[END_REF] or physical hypermedia [START_REF] Rossi | Context-Aware Services for Physical Hypermedia Applications[END_REF].

The considerations presented in this paper are based on two early prototypes made within Franco-Argentinean cooperation [START_REF] Wang | PHOTOWAY, Describing itineraries by pictures with arrows in pervasive systems[END_REF].

The paper is organized as follows. After a comparison of the various modes of describing itineraries, a comparison table based on several criteria will emphasize the advantages of picture-based itinerary descriptions. Then the main characteristics of picture-aided navigational systems will be detailed, essentially based of an ordered sequence of arrow-decorated pictures. We will conclude the paper by giving some final remarks and presenting future works.

DIFFERENT MODES FOR DESCRIBING ITINERARIES

Presently there exist several modes of describing itineraries: text-based, voice-based, map-based and picture-based. Immediately, we must notice that sometimes such modes can be used separately or in combination. In the next sections we will detail each of them.

Text-based mode

Description. In this mode a written text describes how to reach the desired place and it is up to the user to match the written indications with the existing objects in the real world. In an automatic system, the text is usually generated once at the preparation of the itinerary. Advantages. The user can keep the written indications in his mobile device and refer to it when he finds it necessary. Disadvantages. One of the main drawbacks of this mode arises when the user is lost. In this case, the user must ask somebody else in the street who usually gives him a vocal description to return the planned itinerary, which cannot be recorded as text. Another big problem arises when the user has to match the textual description with the real objects: the road names or numbers may not be written at each cross-road or they may be hidden by other obstacles, like trees or traffic lights. Finally, if the application does not support internationalization or the user's language it becomes useless.

Voice-based mode

Description. Voice-based description can be considered as the older system, and it is still very used. Advantages. In an automatic system, usually the spoken commands are not given initially, but during the navigation when necessary. Disadvantages. The main problem is that when the itinerary is complex, the user can forget or mix the indications. The classical consequence is the necessity of completing the indications by asking somebody else. Sometimes the user is not persuaded to be on the planned itinerary. Another major drawback is when the user does not understand the used spoken language.

Map-based mode

Description. With a map description, the itinerary is usually presented as a moving line showing the roads to follow.

Advantages. In automatic systems, global maps are generated initially; but only a small moving map piece is presented to the user when navigating, reduced to his nearby future, usually toward the successive node. When the user is lost, but knowing exactly where he is in the map, he can reconstruct himself the itinerary to reach the planned route. Disadvantages. One of the big drawbacks is that many persons have difficulties in reading maps and identifying exactly where they are on a map; and especially when they are lost.

Maps are essentially 2D representations. However, some systems offer the possibility of a perspective angle, so giving a sort of 3D feeling; but these are not truly 3D systems, because in our understanding, 3D visualization will imply the storing of all existing buildings with a 3D representation.

Picture-based mode

Description. Consider that practically all landmarks have not their name written in huge letters; take for instance a mountain. With only the name you can have some difficulties of identification, but not with pictures. Advantages. Pictures are independent from languages and can help easily identify places. They can be used equally outdoor and indoor. Disadvantages. The big drawback is that a database of pictures must be created and regularly updated. Another aspect is that such a system cannot be used in the case of dense fogs.

We claim that most people can understand a picture and match it easily with the real world unlike text, oral indications or maps. As far as we know, none automatic systems based on pictures exist. At the preparation of the itineraries, the sequence of pictures can be generated and then sent one-by-one when necessary.

Criticisms of existing navigation systems

The existing navigational systems are usually designed for car-drivers and based on a positioning system such as GPS. They are all map-based accompanied sometimes by textual indications or spoken commands when arriving at the vicinity of a turning place. In other words, those systems are using a combination of the previous modes only for outdoor itineraries.

In the other hand, there exist systems for desktop or laptop computers to prepare itineraries, or to make a sort of virtual visit of a city. Among those systems, we can quote:

• the French system of yellow pages with photos: http://photos.pagesjaunes.fr/, showing streets and façades for a large variety of cities in France and in Spain, • and the system "street view" of Google maps for some American cities.

From the French system, we have borrowed the idea of pictures decorated by arrows as given in Figure 1. The conclusion of this rapid analysis is that those systems are used essentially outdoor for car-drivers: they cannot be used directly for walkers and pedestrians, and as far as we know none are based on pictures.

Comparison table

Bearing all that considerations in mind, a comparison among the different modes explained earlier can be made based on several criteria. Among them, let us mention the necessity of abstracting the space, the memory burden, the local and the global vision of the itinerary, language independence, clarity and complexity of the given description and the robustness of identifying landmarks. Table 1 summarizes this comparison.

Finally, the consequence is that picture-based systems can be an interesting candidate as well outdoor as indoor for pedestrians equipped with some handheld device.

BASIC CONSIDERATIONS FOR PICTURE-BASED ITINERARY DESCRIPTION

In order to design such a system, the pre-requisites are: a) not only to model the road network as a graph, but also all places which can be walked by pedestrians, outdoor and indoor; b) to take pictures of all the required views and structure them into a picture database; c) and to model the itinerary description as an ordered sequence of pictures decorated by arrows.

From now on we will call this graph the pedestrian graph. Since there is no one-way path for mobile pedestrians, the edges become arcs in both directions. For each arc, let us speak of the origin node and the destination node.

Picture acquisition

Pictures must be taken for each arc and with a precise protocol (Figure 2). More exactly, the photographer must stand and be positioned in the origin node (N 1 ), and the picture must be directed along the arc such as the destination node (N 2 ), must be more or less in the centre of the picture. In order to position exactly the arrow, the coordinates (in pixels) of the destination node must be stored together with the picture.

If the distance between two nodes (N 1 N 2 ) is very long, it could be interesting to create additional nodes. A threshold could range between 50 and 100 meters.

The starting phase is composed of:

• the pedestrian graph in which edges in both senses are materialized,

• the outdoor paths and indoor corridors,

• and the pictures that are associated to all edges in both senses.

Two experimental databases have been made, the first one in the city of La Plata in Argentina, and the second in La Doua Campus in Lyon, France. But presently only outdoor pictures are taken and stored.

Picture DB and itinerary query answering

The minimum database will be organized as follows (Figure 3). Once the pictures have been taken according to the previous protocol, a database must be created. In essence, it is a graph network in which pictures are attached to arcs. The more important query linked to our purpose can be specified as follows: "give me the ordered sequence of pictures for going from one place to another place and set the results according to my position and my pace?" This query must use a minimum path algorithm such as Dijkstra or A* [START_REF] Zhan | Three Fastest Shortest Path Algorithms on Real Road Networks[END_REF] the result of which is an ordered sequence of nodes and arcs, which will be immediately transformed into a sequence of pictures decorated with arrows (Figures 4 and5).

Arrow decoration

This arrow must be understandable for the user without hiding important features of the pictures (Figure 4). As a consequence, two arcs and three nodes must be considered (Figure 4):

• the origin node from which the picture was taken (N 1 )

• the destination node which is approximately in the centre of the picture (N 2 ) • and the successive node of the itinerary (N 3 ). So, the current picture will correspond to the arc from N 1 to N 2 (as stored in the database), whereas the decorating arrow will correspond to the arc from N 2 to N 3 .

One first solution should be to compute those arrows at the creation of the database; but the main drawback is the multiplication of pictures to store (about three times more). Instead, we prefer compute those arrows on the fly. Three problems have to be solved (1) the position of the arrow, (2) its direction and (3) its color.

Once a solution is defined, some cognitive studies must be performed to examine user's reactions.

Arrow positioning

The arrow will be positioned as follows: its source will be located at the N 2 pixel coordinates as stored in the picture database, its length and width can be parameters of the system, for instance 20 % of the picture size for the length.

Angle computation

To determine the arrow, we need to know the coordinates of three nodes (Figure 6):

• the starting node, N 1 , in which the observer is standing to take the picture, • the shooted node, N 2 which will appear approximately in the centre of the picture, • and the successive node N 3 , knowing that the arrow will begin in N 2 and targeting N 3 . First let us suppose a linear transformation in the plane so that the new axes have their origin in N 2 , and the x axis is directed to N 1 . The observer is standing with the feet in N 1 , and his eye is located in a point H, with the elevation h.

The picture plane Im is supposed to be perpendicular to the line of sight, i.e. to the vector HN 1 . The objective is to find the projection of N 3 , named N' 3 onto the picture plane Im.

As a consequence, the main points are defined as follows:

          =           =           =           = h x H y x N x N N
And the following important angles:

• the shooting angle First let us determine the picture plane equation Im. Since it is perpendicular to HN 2 , the following dot product must be null:

. / 0 0 21 21 ε Ztg X x Zh X Zh Y X x - = ⇒ - = ⇒ = + + So the Im plane equation is X=-Ztgε.
Now, we have to determine the equation of the line L supporting the vector HN [START_REF] Itten | The Art of Color[END_REF] . We can see that it is at the intersection of two planes, the first one passing through the points: H, N 3 , N 2 , and the second one through H, N 3 , and N 1 . a/ Since the origin N 2 belongs to the plane HN 3 N 2 , its generic equation is in which a, b, and c are coefficients to be determined from the general equation: 3), we obtain:

) sin / ( ) 0 / ( ) 0 / ( 2 2 ε α ε α ε α Y tg X tg X Ytg X tg Z Ytg X - = ⇒ = + + ⇒ = - + Reporting in (2) gives: ε α ε α ε α
         - =                   - =           = ε ε α ε α ε ε α ε α
= + = + = - + - ε ε α Ztg X x y x x Y X tg Z Ytg X
Now, let us transform the N' 3 coordinates in the Im plane. We can pass to it by a rotation of angle ε along the y axis (XX, YY, ZZ being the coordinates in the plane); in the same time, we can take into consideration the focal length F and the scale (from meters to pixel width):

) cos sin ( ) sin cos ( ε ε ε ε × + × - × = × = × + × × = z x F ZZ y F YY z x F XX
But in reality, we are concerning by the angle α' in the picture. This angle can be defined from for the N' [START_REF] Itten | The Art of Color[END_REF]

ε α α ε α ε ε ε α ε ε ε α α tg tg tg tg tg YY ZZ tg = = + = + = =
We can check this result very easily in two important cases:

1 -when the photographer is vertical or in case of aerial photo, we obtain ε = 90°, and sin ε = 1 so giving α'=α; this means that the arrow is positioned along the future edge without any modification; 2 -when the photographer is lying flat on the ground, we have ε = 0° and sin ε = 0 so giving α'=0 or α'=π ; this means that the various possible directions are unrecognizable.

Color selection

According to Itten´s theory about colors [START_REF] Itten | The Art of Color[END_REF], it is convenient to select the more contrasting color for the arrow. Two solutions can be examined. The first one is a priori to select one fixed color which is used for all pictures; the second is to compute the optimal color for each picture.

The solution based on a fixed color for the arrow is that the contrast could not be sufficient enough to be understandable. Suppose green is selected for the color of all arrows it can be a good solution when the arrow is laid on tar color, but not when the itinerary is a footpath in a forest.

The variable color corresponding to second solution (Figure 7) can be computed by considering the histogram of colors in the Hue-Lightness-Saturation system, around the centre of the picture. For instance we consider the minimum value of this histogram which is used for the arrow as the most convenient color. The main drawback is that the color evolves from one picture to another, perhaps disturbing the user. For instance, a red color or a green color can be interpreted differently [START_REF] Bertin | Sémiologie graphique[END_REF]. In order not to have difficulties with color representation, only 8 buckets of colors are selected. The main steps of the algorithm are as follows:

i -consider the Itten circle of colors, and divide it into eight regular buckets, ii -make a circular histogram with those eight buckets, iii -select the maximum peak of this circular histogram (which represents the dominant color), iv -select the opposite (which is the more contrasting color, i.e. the arrow's color).

MAIN CHARACTERISTICS OF A PICTURE-AIDED NAVIGATIONAL SYSTEM

Taking all previous considerations into account, a navigational system based on pictures can be defined. This mobile system must be based on the following components:

• a server storing the pedestrian graph, the picture database, running the minimum path algorithm, and sending the sequence of pictures, • a handheld device for the user always in connection with the server , • a communication infrastructure perhaps based on WIFI systems allowing the service roaming, • and a positioning system such as GPS for outdoor, or based on beacons indoor. Remark that the arrow decoration can be made either at server or at client level.

Several of these components are outside the scope of this paper. However, we will present some more important issues to be solved.

Visual Interface

With his handheld device, the user must specify the place where to go and give his preferences. So a path query is sent to the server which runs the minimum path algorithm and returns a set of pictures (Figure 8). The decoration phase can be made either on the server or in the client (handheld device).

User Positioning

Since the system is targeted to run outdoor and indoor, two different positioning systems must be used. When outdoor, the usual GPS system will be used, whereas indoor, some other positioning systems will be used such as beacons or RFID systems. Those functionalities are yet totally operational, especially considering the continuity of service.

User Disorientation

When the user is lost, it means that the position of the user is different from a planned position. In this case, the path is recalculated from the current point to the defined target, and a new picture set is computed, and sent to the user.

CONCLUSIONS

In this paper, we have presented a new concept concerning the explanation of itineraries based on a sequence of arrow-decorated pictures, which is the basis for any pictured-aided navigation systems. We do think that in the future,

Fig 1 .

 1 Fig 1. Example of a picture decorated with an arrow to show where to go. Source: http://photos.pagesjaunes.fr/.

Fig. 2 .

 2 Fig. 2. Assigning pictures to arcs.

1 Fig. 3 .

 13 Fig. 3. Class model of the picture database.

Fig. 4 .

 4 Fig. 4. Decorating pictures with arrows. (a) aerial photo. (b) picture of the same place taken according to our protocol.

Itinerary

Fig. 5 .

 5 Fig. 5. From itinerary (a) to a sequence of pictures.

Fig. 6 .

 6 Fig. 6. Context for arrow angle computation.

-

  points H and N 3 belong to the Im plane, we have: By substituting those values in the general equation, we obtain the first equation of L: the second plane HN 3 N 1 , we need to consider a more general equation:.This line L will cross the Im plane in N' 3 the coordinates of which must be the solution of the following system of three equations: By applying (1) and (

Fig. 7 .

 7 Fig. 7. Image decorated by an arrow.

Fig. 8 .

 8 Fig. 8. Example of visual interface.

Table 1 .

 1 Comparison of different modes of describing itineraries.

	Modes/Criteria	Text-	Voice-	Map-	Picture-
		based	based	based	based
	Abstraction of	High	High	High	Low
	space
	Memory	Medium	High	Medium	Low
	burden
	Space	Difficult Difficult	Good	Excellent
	representation
	Global vision	No	No	Yes	No
	Local vision	Possible	Possible	Yes	Excellent
	Language	No	No	Generally	Yes
	independence			yes
	Clarity of	Low	Low	Medium	High
	description
	Complexity of	High	High	Medium	Low
	the description
	Landmark	No	No	By loca-	Yes
	recognition			tion
	robustness

  point in the Im plane:

		'		(sin	3	sin	cos	2	)	sin	(cos	2	sin	2	)	sin
	So,	giving	the	result	'		sin	.

such a system will be considered as the kernel as Location-Based Services and physical hypermedia.

Let's thank the anonymous referee who gives us references of the LOCUS project (http://www.locus.org.uk/) of the City University of London, the objectives of which bear some similarities with our project.

Presently, two prototypes were made in this direction, one in Argentina and one in France, and we think that the concept is now validated. However, several problems must be solved such as the design of a totally operational prototype, working outdoor and indoor, and the continuity of services.

Another important aspect is the cognitive side of the problem in order to test the reactions of the users.