S Chambon
email: chambon@lcpc.fr

C Gourraud
email: gourraud@lcpc.fr

J.-M Moliard
email: moliard@lcpc.fr

P Nicolle
email: nicolle@lcpc.fr

ROAD CRACK EXTRACTION WITH ADAPTED FILTERING AND MARKOV MODEL-BASED SEGMENTATION Introduction and validation

Keywords: Fine structure extraction, evaluation and comparison protocol, matched filter, Markov model, segmentation

The automatic detection of road cracks is important in a lot of countries to quantify the quality of road surfaces and to determine the national roads that have to be improved. Many methods have been proposed to automatically detect the defects of road surface and, in particular, cracks: with tools of mathematical morphology, neuron networks or multiscale filter. These last methods are the most appropriate ones and our work concerns the validation of a wavelet decomposition which is used as the initialisation of a segmentation based on Markovian modelling. Nowadays, there is no tool to compare and to evaluate precisely the peformances and the advantages of all the existing methods and to qualify the efficiency of a method compared to the state of the art. In consequence, the aim of this work is to validate our method and to describe how to set the parameters.

INTRODUCTION

In many countries, the quality of roads is evaluated by taking into account numerous characteristics: adherence, texture and defects. Since 1980, many efforts have been spent for making this task more comfortable, less dangerous for employees and also, more efficient and less expensive by using an acquisition system of road images and by introducing semiautomatic defect detection, in particular crack detection. Nowadays, a lot of acquisition systems are proposed, see [START_REF] Schmidt | Automated pavement cracking assessment equipment -state of the art[END_REF], but, as far as we are concerned, even if a lot of automatic crack detections had been proposed, no method had been widely applied. In fact, this problem is difficult because road cracks represent a small part of the images (less than 1.5% of the image) and is very low contrasted (the signal of the crack is mixed with the road texture). Actually, there is no evaluation protocol to compare and to highlight methods that are well dedicated to this task and we propose to introduce such a protocol. Moreover, our second aim is to introduce and to validate our contributions about a multi-scale approach based on two steps: a binarization with adapted filtering and a refinement of the binarization by a Markov modelbased segmentation.

First, existing methods are resumed before describing our approach. Then, we introduce the evaluation protocol that enables us to validate the new approach and we give the details of the parameter settings.

DETECTION OF ROAD CRACKS

For this task, three steps can be distinguished: image acquisition, data storage and image processing. In this paper, even if the choices for the two first steps are important, we focus on the image processing step. Four different kinds of methods exist, see Table 1.

The thresholding methods are the oldest ones and also the most popular. They are based on histogram analysis [START_REF] Acosta | Low-cost video image processing system for evaluating pavement surface distress[END_REF], on adaptive thresholding [START_REF] Elbehiery | Surface defects detection for ceramic tiles using image processing and morphological techniques[END_REF], or on Gaussian modelling [START_REF] Koutsopoulos | Primitive-based classification of pavement cracking images[END_REF]. These techniques are simple but not very efficient: the results show a lot of false detections. Some methods are based on morphological tools [START_REF] Elbehiery | Surface defects detection for ceramic tiles using image processing and morphological techniques[END_REF][START_REF] Iyer | A robust approach for automatic detection and segmentation of cracks in underground pipeline images[END_REF][START_REF] Tanaka | A crack detection method in road surface images using morphology[END_REF]. The results contain less false detections but they are highly dependent on the choice of the parameters. Neuron net-works-based methods have been proposed to alleviate the problems of the two first categories (Kaseko and [START_REF] Ritchie | A neural network-based methodology for pavement crack detection and classification[END_REF]. However, they need a learning phase which is not well appropriate to the task. Filtering methods are the most recent. At the beginning, a contour detection has been used but the major drawbacks lie on using a constant scale, supposing that the width of the crack is constant and that we suppose that the background is not as noisy (or textured) as a road surface. This is not realistic and this is why, most of the filtering methods are based on a wavelet decomposition [START_REF] Delagnes | A markov random field for rectilinear structure extraction in pavement distress image analysis[END_REF][START_REF] Subirats | Automation of pavement surface crack detection with a matched filtering to define the mother wavelet function used[END_REF]Wang et al., 2007;[START_REF] Zhou | Wavelet-based pavement distress classification[END_REF] or on partial differential equations [START_REF] Augereau | A differential approach for fissures detection on road surface images[END_REF]. We can also notice an auto-correlation method [START_REF] Lee | New Crack-Imaging Procedure Using Spatial Autocorrelation Function[END_REF] (the authors estimate a similarity coefficient between patterns that represent simulated cracks and patterns inside the images). Some methods also use texture decomposition [START_REF] Petrou | Automatic surface crack detection on textured materials[END_REF][START_REF] Song | Wigner based crack detection in textured images[END_REF] (the goal is to find a noise, i.e. the crack, inside a known texture). (1992)(1993)(1994)(1995)(1996)(1997)(1998)(1999)) [START_REF] Acosta | Low-cost video image processing system for evaluating pavement surface distress[END_REF][START_REF] Cheng | Novel approach to pavement cracking detection based on fuzzy set theory[END_REF][START_REF] Koutsopoulos | Primitive-based classification of pavement cracking images[END_REF]) MORPHOLOGY (1998) [START_REF] Tanaka | A crack detection method in road surface images using morphology[END_REF] NEURAL NETWORK (1991)(1992)(1993)(1994)(1995)(1996)(1997)(1998)(1999)(2000)(2001)(2002)(2003)(2004)(2005)(2006)) [START_REF] Bray | A neural nework based technique for automatic classification of road cracks[END_REF][START_REF] Chou | Pavement distress evaluation using fuzzy logic and moment invariants[END_REF]Kaseko and Ritchie, 1993;[START_REF] Ritchie | Development of an intelligent system for automated pavement evaluation[END_REF] MULTI-SCALE (1990)(1991)(1992)(1993)(1994)(1995)(1996)(1997)(1998)(1999)(2000)(2001)(2002)(2003)(2004)(2005)(2006)(2007)(2008)(2009)) [START_REF] Chambon | Introduction of a wavelet transform based on 2d matched filter in a markov random field for fine structure extraction: Application on road crack detection[END_REF][START_REF] Delagnes | A markov random field for rectilinear structure extraction in pavement distress image analysis[END_REF][START_REF] Fukuhara | Automatic pavement-distresssurvey system[END_REF][START_REF] Subirats | Automation of pavement surface crack detection with a matched filtering to define the mother wavelet function used[END_REF][START_REF] Zhou | Wavelet-based pavement distress classification[END_REF]

THRESHOLD

AFMM Method

First, we present the general algorithm of the method: Adapted Filtering and Markov Model-based segmentation (AFMM) and, second, our contributions in each of the parts of this algorithm.

Algorithm

The goal of this algorithm, presented in Figure 1, is to obtain, steps 1 to 3, a binarization (black pixels for background and white pixels for the crack) and a refinement of this detection by using a Markovian segmentation, step 4,. In the first part, a photometric hypothesis is used: a crack is darker than the background (the rest of the road pavement) whereas, in the second part, a geometric hypothesis is exploited: a crack is composed of a set of connected segments with different orientations. The number of scales for the adapted filtering has to be chosen and depends on the resolution of the image. By supposing a resolution of 1 mm per pixel, by choosing 5 scales, a crack with a width from 2 mm to 1 cm can be detected. Moreover, the number of directions (for the filtering) also has to be chosen and, it seems natural to take these four directions: [0, π 4 , π 2 , 3π 4 ] that correspond to the four usual directions used for crack classification. Adapted filtering is applied in each scale, each directions and then all the results are merged (mean of the coefficients). The results of this filtering is used to initialize the Markov model.

Input

Adapted filtering

The ψ ∈ L 2 (IR 2 ) function is a wavelet if:

Z IR 2 |Ψ(x)| 2 x 2 dx < ∞, avec x = (i, j), ( 1
)
where Ψ is the Fourier transform of ψ. The equation (1) induces that Z IR 2 ψ(x)dx = 0. The wavelet family is defined for each scale s and for each position u, by :

ψ x, û,θ (x) = 1 2 ψ(R θ ((x -u)/s)), (2)
where ψ ∈ IR 2 and R θ is a rotation of angle θ.

h = φ -1 bb s. (3)
The crack signal depends on the definition of the crack. In this paper, like most of the papers of this domain, crack pixels correspond to black pixels surrounded by background pixels (road pixels). This is why, in [START_REF] Subirats | Automation of pavement surface crack detection with a matched filtering to define the mother wavelet function used[END_REF], a crack is a piecewise constant function:

f (x) = -a If x ∈ [-T 2 , T 2 ] 0 Elsewhere, (4)
where the factor a and the threshold T have to be determined. It does not correspond to a realistic representation of the crack. Because of sub-sampling, lights, orientation of the camera, the signal is more like a Gaussian function with zero mean:

f (x) = -a e -1 2 ( x σ ) 2 , ( 5
)
where a is the size of the crack and depends on σ, the deviation of the Gaussian law, i.e. a =

Contribution to segmentation

The goal of this part is to extract shapes, i.e. cracks, using the detection maps estimated at the first stage of the algorithm. The MRF (Markov Random Field) principle is introduced before the presentation of the improvements about the initialization of sites and the updating of the Markov Random Field.

For the first step of segmentation (initialization), in [START_REF] Subirats | Automation of pavement surface crack detection with a matched filtering to define the mother wavelet function used[END_REF], the sites are of size 3 × 3, consequently, a regular grid is considered in the image. The four configurations that are possible, are represented in Figure 2. The initialization of the sites is based on the configuration that maximizes the wavelet coefficients. More formally, if we denoted γ 2,0 , γ 2, π 4 , γ 2, π 2 andγ 2, 3π 4 , see in the bold rectangle in Figure 2, the four configurations, the best configuration γ best is:

γ best = argmax α∈[0.. 3π 4 ] m 2,α , (6)
where m 2,α is the mean of wavelet coefficients on the considered configuration γ 2,α . These four configurations do not represent all the possible and are not realistic configurations. In fact, all these four configurations are centered, whereas, it is possible to have some non-centered configurations. Consequently, we use a set of configurations that includes this aspect and we employ a set of sixteen configurations illustrated in Figure 2. By modifying the number of configurations, we need to adapt the initialization of sites, i.e. equation ( 6). The image is considered as a finite set of sites denoted S = {s 1 , . . . , s N }. For each site, the neighborhood is defined by: V s = s

γ 3, 3ψ 4 γ 0, 3π 4 γ 1, 3π 4 γ 2, 3π 4 γ 4, 3π 4 γ 1,0 γ 3,0 γ 2,0 γ 0, π 4 γ 2, π 2 γ 3, π 2 γ 1, π 2 γ 3, π 4 γ 1, π 4 γ 2, π 4 γ 4, π
′ |s / ∈ V s ′ & s ′ ∈ V s ⇒ s ∈ V s ′ .
A clique c is defined as a subset of sites in S where every pair of distinct sites are neighbors.

The random fields considered are:

1. The observation field Y = {y s } with s ∈ S. Here, y s is the mean of wavelet coefficients on the site.

2. The descriptor field L = {l s } with s ∈ S. For this work, if there is a crack l s = 1 elsewhere l s = 0.

MRF model is well suited to take into account spatial dependencies between the variables. Each iteration, a global cost, or a sum of potentials, that depends on the values of the sites and the links between neighborhoods, is updated. This global cost takes into account the site coefficients (computed from the wavelet coefficients estimated during the first part of the algorithm: adaptive filtering) and the relation between each site and the sites in its neighborhood (in this paper, it corresponds to the eight neighbors). More formally, the global cost is the sum of all the potentials of the sites and contains two terms:

u s (s) = α 1 u 1 (s) + α 2 ∑ s ′ ∈V s u 2 (s, s ′ ), (7)
where V s is the neighborhood of site s. The choice of the values α 1 and α 2 depends on the importance of each part of the equation ( 7).

The function u 1 is given by:

u 1 (y s , l s = 1) = e ξ 1 (k-y s ) 2 If y s ≥ k 1 Elsewhere and u 1 (y s , l s = 0) = e ξ 2 (y s -k) 2 If y s < k 1 Elsewhere, (8)
The parameters ξ 1 , ξ 2 and k have to be fixed 1 . For the definition of u 2 , we have to determine the number of cliques. In [START_REF] Subirats | Automation of pavement surface crack detection with a matched filtering to define the mother wavelet function used[END_REF], four cliques are possible. As there is four configurations in the previous approach, there is sixteen possibilities. A 8-neighborhood is considering but the potential function proposed in the precedent work only considers the difference of orientations between two neighborhoods and not the position between the two sites of the clique, see Table 2. Some cases are not penalized with the old configuration. For example, these two unfavorable cases are not penalized: two sites with the same orientation but with no connection between them, two sites with the same orientation but their position makes them parallel. This is why, with the sixteen possible configurations presented in Figure 2, the new variant takes into account differences of orientations between two 1 The choice of k is related to the maximal number of that belong to a crack (it depends on the resolution of images and hypothesis about the size and configuration of cracks). We have chosen k in order to consider at most 5% of the image as a crack. Moreover, our experimentations have brought us to take ξ 1 =ξ 2 =100.

γ 2,0 γ 2, π 4 γ 2, π 2 γ 2, 3π 4 γ 2,0 β 1 β 2 β 3 β 2 γ 2, π 4 β 2 β 1 β 2 β 3 γ 2, π 2 β 3 β 2 β 1 β 2 γ 2, 3π 4 β 2 β 3 β 2 β 1
Table 2: Function u 2 -This table represents the values of the function u 2 (s ′ , s) for the four initial configurations of the sites. In the experiments we have taken the values of the parameters proposed by the authors [START_REF] Subirats | Automation of pavement surface crack detection with a matched filtering to define the mother wavelet function used[END_REF] and that give the best results:

β 1 = -2, β 2 = -1 and β 3 = 2.
sites (there are 16 × 16 possibilities) and position of the two sites (there is eight possibilities because of 8connexion). Consequently, the new potential function u 2 follows these two important rules: (R 1 ) The lower the difference of orientations between two sites, the lower the potential.

(R 2 ) The lower the distance between two sites, the lower the potential (in this case, distance means the minimal distance between the extremities of the two segments). More formally, if d denotes the Euclidean distance between the two closest extremities of the sites, with

d ∈ [0, d max ] (d max = 5 √ 2)
, θ 1 and θ 2 , the orientations of respectively s = {s i } i=1..N s , and

s ′ = {s ′ j } j=1..N s ′
and θ e the angle between the two sites, the u 2 function is defined by:

u 2 (s ′ , s) = α 2 |2θ e -θ 1 -θ 2 | 2π + (1 -α 2 ) J(NbC) min i, j (d(s i ,s ′ j )) d max -NbC 3 . ( 9
)
where NbC indicates the number of elements of the two sites s and s ′ and J(x) equals 1 if NbC = 0 and 0 elsewhere. The first term is induced by the rule about the orientations, rule (R 1 ), it is zero when the sites have the same orientation and this orientation is the same as the orientation between the sites, i.e. θ e = θ 2 = θ 1 . It gives bad costs to configurations where the sites do not have the same orientation but also the particular case where they are parallel, see example (a) in Figure 3. The second and third terms express the rule (R 2 ) about the distances. Two aspects have to be distinguished: the number of connected pixels, when the sites are connected, and, on the contrary, the distance between the sites. It allows to give low influence to disconnected sites and also to increase the cost of sites that are parallel but connected, see example (b) in Figure 3. To study the influence of all these terms, the equation has been normalized and the different terms have been weighted.

s 0 s 1 s 2 s 3 s 2 s 1 s 3 s 0 θ 0 = θ 1 = θ 2 = π 4 , θ 3 = π 2 θ e1 = 0, θ e2 = π 4 and θ e3 = π 2 For s 1 : u 2 = π 2 -0 + 2 For s 2 : u 2 = 0 -1 + 0 For s 3 : u 2 = 4 -1 + 0 θ 0 = θ 1 = θ 2 = θ 3 = π 2 θ e1 = 0, θ e2 = θ e3 = π 2 For s 1 : u 2 = π -3 + 0 For s 2 : u 2 = 0 -1 + 0 For s 3 : u 2 = 0 -0 + 2
Figure 3: Illustration of function u 2 -These two examples of sites with their respective neighborhoods show the behavior of potential u 2 with the two considered aspects: orientation and distance. In example (a), with the help of the orientation term, the configuration s 1 is penalized and s 3 is penalized than s 1 . In example (b), with the help of the two terms on distance, the site s 3 is penalized, compared to s 2 . On the contrary, the particular case of s 1 is favorable and it equilibrates the penalty given by the orientations.

EVALUATION PROTOCOL

For the evaluation of automatic crack detection, there is no evaluation and comparison protocol proposed in the community. However, in all the countries, for estimating the quality of the road surface, it is important to know exactly the size and the width of the defects, i.e. to detect precisely the defect. This is why, it seems important to characterize quantitatively the performance of the methods. For building this kind of protocol, it is necessary, first, to choose the tested images, second, to choose how to build reference segmentations, and, third, to determine the criteria used for the quantitative analysis.

Tested images

The most difficult is to propose images with a reference segmentation or a "ground truth" segmentation. On the first hand, we create synthetic images with a simulated crack. As shown in figure 4, the result is not enough realistic and, on the second hand, we have taken a real image with no defect and we have added a simulated defect. The result is more realistic but the shape of the crack (which is randomly chosen) does not seem enough realistic. This is why, it appears important to propose a set of real images with manual segmentations that are enough reliable to be considered as reference segmentations or "ground truth" segmentations. To resume, the two first kinds of images allow to propose an exact evaluation and to well illustrate the behavior of the method in theoretical cases whereas the last kind of images allows to validate the work on real images with a "pseudo" ground truth.

Reference segmentation

For real images, we briefly explain how the manual segmentation is validated. Four experts manually give a segmentation of the images with the same tools and in the same conditions. Then, the four segmentations are merged, following these rules:

1. A pixel marked as a crack by more than two experts is considered as a crack pixel;

2. Every pixel marked as a crack and next to a pixel kept by step 1 or 2 is also considered as a crack.

The second rule is iterative and stops when no pixel is added. Then, the result is dilated with a structuring element of size 3 × 3.

In this part, we distinguish two datasets of real images. First, we have work with 10 images, in order to validate our manual segmentation and to determine how to fix the parameters of the proposed method. This first dataset is called initial dataset. The second one contains 32 images to complete the evaluation and we called it the complementary dataset.

Initial dataset

To evaluate the reliability of the reference segmentations, we estimate, first, the percentage of covering between each operator, and, second, the mean distance between each pixel (detected by only one expert and not kept in the reference image) and the reference segmentation. Table 3 compares the results for these 10 first images. We can notice that the first 4 images are the most reliable because the mean error is less than 2 pixels. On the contrary, the last 6 images are less reliable but they are also the most difficult to extract a segmentation.

Complementary dataset

The same technique is used for establishing the reference segmentations with 32 images. By analyzing the results for criteria D., presented in Table 3, we decided to classify the 42 tested images in 3 categories: 1. Reliable: All the images have obtained D < 2 and it means that all the operators have selected areas that are quite close to each other and the segmentation is reliable.

2. Quite reliable: All the images have obtained 2 ≤ D < 8, it that some parts of the crack are not easy to segment and there are locally big errors.

3. Ambiguous: All the images have obtained D ≥ 8. It clearly show that the images are really difficult to segment and in most of the cases, it means that some parts are detected as a crack whereas they are not a crack and reversely.

Table 3: Manual segmentation comparison for establishing the reference segmentations -For each image, we give the percentage of pixels that are preserved in the final reference segmentation compared to the size of the image (F), the percentage of covering between 2, 3 and 4 segmentations (over all the pixels marked as crack by the 4 experts) and the sum of them (S). For all the crack pixels not preserved in the final reference segmentation, the mean distance to this segmentation is given, noted D.

Images F (%) 2 (%) 3 (%) 4 (%) S (%) D (pix)

Evaluation Criteria

In this section, we introduce how the reference segmentation and the estimated segmentation are compared. In Figure 5, we present common evaluation criteria that are used for segmentation evaluation. We have added the principle of "accepted" detection that tolerates a small error on the localization of crack pixels. This criterion is needed because perfect detection seems, for the moment, difficult to reach, see the results in Table 3, that illustrate this aspect. In consequence, these "accepted" pixels have been included in the estimation of the similarity coefficient or DICE.

The threshold for accepted pixels equals 0 for synthetic images whereas it depends on the mean distances, see D. in table 3, for the real images.

Ratio between good detections and non-detections

Figure 5: Evaluation criteria -In this figure, it corresponds to two simulated segmentations of the same crack: the black one is manual (or the reference) and the red one is estimated. The goal is to evaluate the quality of the estimated segmentation, that corresponds to the Positives (P). All the non-selected pixels that do not correspond to the crack are called the True Negatives (TN). Piece of crack with the two colors (red and black) are the correct detections or True Positives (TP). In the table, the criteria are resumed and in this work, we have used the DICE because this coefficient well represents what we want to measure: the quality of the detection against the percentage of the crack that is detected, or, how to reduce false detections and to increase the density.

Experimental results

For the proposed method, we want to determine, first, how to fix the different parameters, second, the preprocessing steps that are necessary, and, finally, which variant is the most efficient. In consequence, we have tested different:

• Parameter values -The weights α 1 , equation ( 7), and α 2 , equation ( 9), are tested from 0 to 1 with a step of 0.1.

• Pre-processings -These pre-processings have been experimented to reduce noises induced by texture, to increase the contrast of the defect and, to reduce the light halo in some images (like the last six ones presented in Table 3):

1. Threshold -Each pixel over a given threshold is replaced by the local average gray levels. 2. Smoothing -A 3 × 3 mean filter is applied. 3. Erosion -An erosion with a square structuring element of size 3 × 3 is applied. 4. Restoration -It tries to combine the advantages of all the previous methods in three steps: histogram equalization, thresholding (like Threshold), and erosion (like Erosion).

• Algorithm variants -Four variants are compared:

1. Init -This is the initial method proposed in [START_REF] Subirats | Automation of pavement surface crack detection with a matched filtering to define the mother wavelet function used[END_REF]. 2. Gaus -This variant considers the crack as a Gaussian function, see section 3.2. 3. InMM -This is the initial version with an improvement of the Markov model (new definition of the sites and of the potential function), see section 3.3. 4. GaMM -This is the Gaus version with the new Markov model.

• Comparison -We have compared this method with a method based on morphological tools and that is quite similar to [START_REF] Tanaka | A crack detection method in road surface images using morphology[END_REF] noted Morph.

Parameter influence

Among the results, two conclusions can be done. For each variant and each pre-processing, the weights between the term for adapted filtering and the term for the Markovian modelling should be the same, see equation ( 7), i.e. α 1 = 0.5. However, when more weight is given to adapted filtering , the quality of the results is lower than when more weight is given to the Markovian segmentation. It means that in this kind of application, the geometric information is more reliable than the photometric one and it seems coherent with the difficulties of the acquisition.

For the new Markov model, we have noticed that the results are the best when the weights are the same between the orientation term and the distance term, see equation ( 9), i.e. α 2 = 0.5. However, better results are obtained when the weight of the orientation is greater than the distance one instead of the reverse.

Pre-processing

These tests have been done with real images, because, a priori, synthetic images do not need preprocessings. The results are given by: Init Gaus InMM GaMM Restoration Restoration Threshold Erosion However, for the four first images (acquired with lighting conditions more comfortable than the lighting conditions of the next 6 ones), the pre-processing is not significant for increasing the quality of the results. Moreover, with the new Markov model, the preprocessing step increases a little the quality.

Variants

The results are separated in two cases: with synthetic images and with real images. In Figure 6, the evolution of the similarity coefficient, or DICE, for the 11 synthetic images and the 10 real images is presented. With synthetic images, GaMM is clearly the best for most of the images. However, for one image (the fifth), the results are worse than with Gaus but they are still correct (DICE=0.72). On the contrary, for the most difficult images (the 3 first ones that contain a real road background), GaMM obtains acceptable results (DICE > 0.5) whereas the other methods are not efficient at all. An illustration is given in Figure 7: it shows how GaMM can reduce false detections. The results with real images, see graph (b) in Figure 6, are coherent with those obtained with synthetic images. The new Markov model allows the best improvements, compared to the initial method Init. The method GaMM obtains the best results, except on few images, see an example in figure 8, where InMM is the best. However, GaMM gives results that are quite similar and the differences are not significant.

Complementary dataset and comparison

Finally, we have compared the result of GaMM on each of the complementary dataset (32 images) with the results obtained with a classic method based on morphological tools, like [START_REF] Tanaka | A crack detection method in road surface images using morphology[END_REF]. The mean DICE is 0.6 with GaMM whereas it is 0.49 with the Morphology method, see Figure 9. of method. However, if we compare image per image, the results show that in 50% of the cases GaMM is the best, see illustrations of these results in Figures 10 and11. More precisely, it seems more performant with Ambiguous images, whereas the Morphology method is the best with Reliable images, see § "Complementary dataset".

It shows how this new method outperforms this kind

Image Ground truth Init

CONCLUSIONS

In a first time, we have introduced new methods for the detection of road cracks. In a second time, we have presented a new evaluation and comparison protocol for automatic detection of road cracks and the munity in order to have a larger comparison. Then, we want to increase our data set by taking into account the different qualities of road surface or road texture (because for the moment, each proposed method seems very dependent on the road texture). Finally, we want to refine our evaluation criteria by using [START_REF] Arbelaez | From contours to regions: An empirical evaluation[END_REF].

4Figure 2 :

 2 Figure 2: The sixteen configurations of the Markov model (initialization) -The sites are represented with dark gray levels.

  Figure 4: Tested images.

Figure 6 :

 6 Figure 6: Variation of the similarity coefficient, see figure 5 -The first graph shows the results for synthetic images (the 3 first ones are obtained from real images with simulated defect) and the second graph presents the results with real images. Good performances of methods InMM and GaMM can be noticed.

Figure 7 :Figure 8 :

 78 Figure 7: Segmentation results (synthetic images presented in Figure 4) -These are the results obtained with the four variants and it shows how GaMM gives the clearest result.We can also notice the good result of InMM.

Figure 9 :

 9 Figure 9: Comparison with Morph -The dotted lines illustrate the five different kinds of images tested. For the first one (that corresponds to real images with good illumination), the results are mixed whereas for the other ones, GaMM is the best.

Figure 10 :

 10 Figure 10: Differences between Morph and GaMM -Examples with synthetic and real images. Morph outperforms GaMM with simple synthetic images whereas GaMM gives detection with real images.

Figure 11 :

 11 Figure 11: Differences between Morph and GaMM -Examples with real images acquired on a vehicule. The detection with GaMM is more complete than with Morph.

Table 1 :

 1

State of the art about road crack detection -In brackets, we give the years of publication.

σ √ (2π). Consequently, the term σ allows to fix the width of the crack (like threshold T in equation (4)).


M Hirose

D Schmalstieg

C A Wingrave

Editors K Nishimura

M Hachet

A Kian

F Berthaut

J S Franco

M Desainte-Catherine

Joint Virtual Reality Conference of EGVE -ICAT -EuroVR (2009)

Keywords: Descriptors (according to ACM CCS): H.5.1 [Information interfaces and presentation]: Multimedia Information Systems-Artificial, augmented, and virtual realities J.5 [Arts and humanities]: Music, Arts, fine and performing-

While mixed reality has inspired the development of many new musical instruments, few approaches explore the potential of mobile setups. We present a new musical interaction concept, called opportunistic music. It allows musicians to recreate a hardware musical controller using any objects of their immediate environment. This approach benefits from the physical attributes of real objects for controlling music. Our prototype is based on a stereo-vision tracking system associated with FSR sensors. It allows musicians to define and to interact with opportunistic tangible widgets. Linking these widgets with sound processes allows the interactive creation of musical pieces, where musicians get inspiration from the surrounding environment.

Introduction

Musicians interact with musical applications by the way of controllers. These controllers are either based on physical devices such as mixing tables or control pads, or they lie on graphical interfaces. Physical devices allow direct and efficient control of the musical parameters. For example, a physical fader is commonly used to adjust precisely the volume of an audio track. On the other hand, the structure of the physical devices as well as the number of their functionalities is fixed. On the contrary, graphical interfaces are not limited by physical constraints and therefore offer infinite configurations. For example, a virtual fader controlled by way of a mouse can be displayed using various graphical representations. On the other hand, these interfaces suffer from a lack of haptic feedback, which decreases the efficiency of the control.

We propose a new approach called opportunistic music for interaction with musical pieces. The idea is to benefit from the physical attributes of the surrounding objects for controlling music. For example, a musician will slide his finger along the border of a table to control the volume of an audio track, or he will tap on the cover of a book to start a musical loop. This approach is inspired by the work of Henderson and Feiner [START_REF] Henderson | Opportunistic controls: leveraging natural affordances as tangible user interfaces for augmented reality[END_REF], where opportunistic controls are used for interaction with AR applications (eg. maintenance). Such an opportunistic approach opens new perspectives for musical creation. By interacting with the physical objects surrounding them, the musicians benefit from inexhaustible sources of inspiration. The way they interact with the music can evolve depending on the available surrounding objects. The musicians are no longer limited to fixed setups. They can explore new controls for interaction with their musical pieces. This approach offers extensible control, while ensuring physical interaction. Therefore, it offers opportunities to artists for a new kind of musical creation.

We have developed a first prototype to explore this concept. It is based on a stereo-vision system associated with Force Sensitive Resistors (FSR) sensors for the tracking of the musician's gestures (see Figure 1). With this system, musicians define virtual controllers directly on the physical environments surrounding them. Then, they can connect these controllers to sound parameters. Finally, the musicians play by directly interacting with the real objects they have defined as active objects.

Related Work

The past decade has seen the growth of alternative musical controllers. Furthermore, many musicians and software developers have taken advantage of research done in the mixed reality field.

The most widespread of these new controllers are tangible musical tables, which take inspiration from Fitzmaurice's graspable user interfaces [START_REF] Fitzmaurice | Laying the foundations for graspable user interfaces[END_REF]. In these applications, users manipulate real objects whose 2D position and orientation are associated to parameters of sound processes. A simple example of this category is d-touch [START_REF] Costanza | Introducing audio d-touch: a novel tangible user interface for music composition and performance[END_REF], which allows musicians to control for example a sequencer by arranging real objects representing sounds on a grid layed on a table . Other examples include The Music Table [START_REF] Berry R | The augmented composer project: The music table[END_REF], Xenakis [BCL * 08] or Scrapple [START_REF] Levin | The table is the score: An augmented-reality interface for real-time, tangible, spectrographic performance[END_REF]. The most advanced applications are the Audiopad [START_REF] Patten | Audiopad: A tag-based interface for musical performance[END_REF] and the Reactable [START_REF] Jordà | The reactable[END_REF], which both provide advanced musical control and rich visual feedback. However, these controllers rely on objects with markers and on fixed setups, i.e. large tables with fixed cameras and projectors.

Other controllers allow for more flexible setups. For example, the concept of accoustic tangible interfaces [START_REF] Crevoisier | Tangible acoustic interfaces and their applications for the design of new musical instruments[END_REF] gives the possibility of turning most surfaces and objects into accurate multitouch musical controllers, but it requires to equip them with calibrated audio sensors and thus is not mobile.

The "Augmented Groove" [PBB * 01] application relies on 3D manipulation of real LP records which are equipped with fiducial markers. Each of these records is associated with a musical loop, which is started when the user flips the record to reveal the marker. The 3D movements then control audio effects applied on the loop, such as pitch, distortion, filter, volume. It could easily be turned into a mobile setup, like the project developped by Goudeseune [START_REF] Goudeseune | Composing outdoor augmented-reality sound environments[END_REF]. This augmented reality application allows users to create virtual sound sources in a real environment. Musicians can then modify the sources' positions and navigate through them.

The "Sound of Touch" [START_REF] Raffle | The sound of touch[END_REF] is another interesting instrument. Users record sounds of the environment with a wand and play them by scratching or hitting the wand against real objects. Physical properties, i.e. resonance or texture, of the real objects alter the sound properties, making it softer or stronger. Thus this instrument allows users to explore surrounding objects, and it takes advantage of the haptic feedback from the physical textures. However, musical interaction is limited to triggering the recorded sounds.

None of these musical applications combine mobility, use of unprepared objects, haptic feedback and unrestricted control possibilities. That is why we believe that opportunistic music will bring completely new musical possibilities to musicians.

Opportunistic Widgets

The key idea of opportunistic music is to interact directly with the real objects surrounding the user. We call these interactive objects opportunistic widgets. Numerous objects of the real environment may have interesting properties when used as opportunistic widgets. We propose to take advantage of these physical characteristics to enable tangible interaction. It has been shown that tangible interaction may improve the performance of users for the completion of interactive tasks. In the case of music, we are convinced that such an approach, which provides sensitive feedback to the musician, can be very valuable. For example, furniture edges are well suited to control linear values. By sliding their hands along the edge of the furniture, the musician interact as they would do with a standard fader. Another example is the use of physical objects as pads. By tapping on the objects, the musicians can start events.

In addition to standard widgets such as pads or faders, the real environment may inspire new unconventional widgets that can have interesting properties for music. For example, a curved surface may produce valuable tangible feedback to the musician. Other examples are opportunistic widgets for which elastic feedback is intrinsically provided (e.g. a folder with rubber bands). For such widgets, the musicians benefit from an elastic sensing mode, which can be particularly interesting for the control of some sound parameters (e.g. physical modelling synthesis). Other physical properties of the real environment can be exploited. For example, musicians can exploit the texture of the objects, their viscosity or even their warmth as a haptic feedback. Figure 2 illustrates some examples of opportunistic widgets.

While facing the real environment, musicians can play with the objects without moving them, or they can rearrange their playing environment. For example, they can use some sheets of paper, on which they draw some relevant signs or text. Then, they can arrange these widgets as desired, before assigning them a function.

In the following, we describe the technical setup we have developed to define the opportunistic widgets and to interact with them. This concerns the low level tracking issues, the creation of the widgets, and their mapping to musical events. Our current implementation does not allow mobile use yet. In this paper, we present a first prototype that validates our concept. It is the first step towards a full mobile system.

Technical Environment

To build an opportunistic music system, we need to track 3D user movement and respond to user-triggered events. The system must also have desirable characteristics such as portability, on-site robustness, minimal user space cluttering, and high reactivity. The latter is a requirement for interactive systems in general, but is especially relevant to music, where typical response times cannot exceed 20ms. Vision-based tracking systems offer benefits toward portability and being minimally invasive, as they can provide the ability to rapidly process visual tracking data with minimal user instrumentation in a compact package. They also have an inherent advantage since they can easily be built with cost-efficient off-the-shelf components, as the availability of video hardware soars. However, typical camera acquisition frequencies do not exceed 30Hz for low to medium-end cameras. Also the detection of surface contact from video is fundamentally ambiguous for this type of setup as scene geometry is assumed fully unknown. Vision systems are thus desirable for identifying 3D positions and regions of movement, but not precise enough in detecting high frequency events such as surface contact. For this reason a second more responsive input source is needed. This input does not need to provide positional information, but rather a way of identifying highfrequency trigger and contact events to complement the vision system.

Current Prototype implement the desired system characteristics, we propose an opportunistic music prototype based on inputs from two cameras and an FSR sensor. The former allows for stereovision-based 3D positioning of visually salient objects, while the latter allows to detect pressure with high precision and responsiveness (<10ms). To allow absolute 3D positioning in the scene and the creation of world-basis music widgets, we need to acquire projective characteristics of cameras and their positional information. All such parameters are typically described by a single 3x4 projection matrix using the common pinhole-camera model [START_REF] Hartley R | Multiple View Geometry in Computer Vision[END_REF]. The projection matrix linearly describes where a given 3D scene point projects in camera image pixel coordinates, and can then easily be used to triangulate the 3D position of a scene point from its two identified image occurrences. In our context scene points of interest to be tracked in the scene will be the user's fingertips. simplicity, let us for now assume the camera pair is on a fixed mount (such as a tripod) observing the user interaction space with minimal occlusion. Depending on the scene, such a configuration can typically be obtained with overthe-shoulder camera positioning. Off-the-shelf methods can then be used to calibrate the camera-pair † , i.e. estimate each camera's projection matrix using a known calibration object [START_REF] Zhang | A flexible new technique for camera calibration[END_REF]. To enable user finger positioning, we still need to identify the locus of fingertip projections in camera views. To allow for robust and fast identification of fingers, we opt for a target-based approach based on infrared detection. This notably has the advantage of quasi-invariance to visible light changes and appearance-specific noise and variability, enabling detection by simple and computationally inexpensive thresholding in general situations. We thus propose minimal user instrumentation using a thimble-type device (prototype shown in Fig. 3) which hosts the FSR touch sensor and a small infrared LED. The LED could equivalently be replaced by a passive IR reflector thimble and an IR source mounted with the camera pair.

Toward a Mobile Setup

We previously assumed a fixed camera mount setup, which could be transported and used on-the-field. A drawback of this setup is that it restricts the user to a fixed tracking area observable in the common field of view of the camera pair. An idea to take this system toward a fully mobile setup is to use an instrumented headset to mount the camera pair and earphones (see Fig. 4), connected to a mobile processing unit fitted in a backpack. Head movement then allows for completely flexible interaction areas, by tracking the user's fingers in his current region of attention. A fundamental difference with the previous setup is that camera absolute positions can now be allowed to vary up to a rigid transformation, which must be estimated for each frame. We thus propose to equip the headset with a positioning device, e.g. a third camera in the visible spectrum and inertial sensor. These instruments can then be used to detect the scene's salient features and head ego-motion, thus allowing for head and camera positioning in the world coordinate frame. Music widgets can then be defined appropriately in absolute 3D coordinates in arbitrarily large interaction areas. It should be noticed that the technical solution we propose for tracking the musicians' fingers is adapted to mobile conditions, as it does not require object recognition, and it is very few dependent from the lighting conditions.

Defining and Playing the Widgets

The system we have described in the previous section allows us to know the 3D position of the users' fingers. In addition, the FSR sensors give us precise information concerning the contact between the fingers and the physical surfaces. The next step consists in defining the opportunistic widgets.

Creating the Widgets

Widget creation should be very simple and avoid tedious procedures. To this goal, we propose registration of new widgets by simply sliding fingers on surfaces intended as widgets. The musician can then define 3D curves in a straightforward manner. These curves will be used as linear valuators (faders), or they will be used as binary inputs (pads).

Technically, when a finger pressure is detected via the FSR sensor, we record the successive 3D positions P i of the LED, until the user's finger is released. In addition to these 3D points, we store the local tangent vectors given by

t i = Pi+1-Pi ||Pi+1-Pi||
We also store the local integral distance from the origin d i , which is given by

d i = d i-1 + ||P i+1 -P i ||
At the end of the record (i.e. when the finger is released), we save an id as well as the bounding box given by the min and max coordinates of the curve. We also store the total integral distance d total .

For each point of the curve, we can compute a corresponding normalized integral value c ∈ [0, 1], as described in the next section. These values are the output values of the opportunistic widgets.

One 3D position P i is stored at each frame. Hence, users can define the curves accurately by sliding their fingers slowly. They can define coarse sections by moving fast, too. Hence, the users can precisely define where they need fine control. Note that in our current implementation, we use linear interpolation based on the integral distances. By taking into account the speed of the finger movements, we could use non-linear mappings, too. These non-linear mappings could be interesting to improve music expressiveness. This direction has to be studied more in depth.

Additional widgets could be defined, too. For example, 2D surfaces could be used for the bi-dimensional control of sound parameters. We will define additional widgets in our future work.

Interacting with the Widgets

The musicians can now play with the widgets they have defined. In the following, we describe how our system manages the users' input.

When a contact is detected, we first evaluate if the 3D point F corresponding to the tracked LED is in the area of an opportunistic widget. This can be done by way of a simple inclusion test with the bounding boxes of the widgets. For the concerned widgets, we estimate the distance from F to the curve, and we return the corresponding c value.

To do so, we test if F is in a tolerance cylinder for each segment [P i P i+1 ] of the curve, as illustrated in Figure 5. We note h, the tolerance distance under which F is considered to be part of the segment

[P i P i+1 ].
We project F on (P i P i+1 ) and compute the scalar value

α = t.(F -P i ). F belongs to the tolerance cylinder if α > -h and α < ||P i+1 -P i || + h ||(F -P i ) -α t|| < h
c = di+α||di+1-di|| d total
This widget output value is then sent as an input to the musical subsystem. This is described in the next section.

The computation of the c values could be improved by managing the links between the segments of the curve. Indeed, our current implementation does not ensure the linear continuity of the widget output when the projection of the input points moves from one segment to another. This could be solved by linking the successive tolerance cylinders in order to ensure continuity, as illustrated in figure 6. We could also use generalized cylinders defined by parametric curves. However, in practice, the limited precision coming from the video tracking as well as the large number of recorded points do not require such an optimization.

Figure 6: Continuity of the output values. Regular cylinders (top) do not ensure full continuity. This can be improved by linking the cylinders (bottom).

Figure 7 illustrates the output values obtained when slidthe finger along a previously defined curved-shape widget. It can be noticed that the overall continuity of the obtained values is good. The slope modifications show the speed variation of the finger movement. It can be noticed that the output curve is not perfectly smooth. This is mainly due to tracking imprecisions. To smooth the curve, we could apply a dedicated filter.

Managing Sound Processes

Mapping the Widgets to the Sound Parameters

The musician needs to associate the opportunistic widgets sound parameters. Numerous approaches could be used to do this, such as a voice recognition or PDA interface. In the current implementation, before creating the widgets, the musician defines physical mapping buttons by touching 3D locations in the environment. For example, for a musical application where 4 parameters can be controlled, the musician should define 4 buttons, the first one corresponding to the first parameter, the second one to the second parameter, and so on. Hence, the musician associates one physical object to one parameter (e.g. a mug is associated to loudness). The musician can also use annotated sheets of paper as labels. The mapping is done by pressing a mapping button before creating a widget as we already described. The created widget is then associated to the selected sound parameter.

OpenSoundControl Messages

The values of the opportunistic widgets and the values of the FSR sensors are sent to the audio application using the OpenSoundControl [START_REF] Wright | Open sound control: A new protocol for communicating with sound synthesizers[END_REF] protocol. The messages are defined as urls, widgets and FSR values being floats between 0 and 1 : /opportun/widget1 valueWidget valueFSR They are sent when the FSR sensor's value reaches a predefined threshold. The value of the FSR sensor is also continuously sent as /opportun/sensor valueFSR, to enable other user-defined controls.

Sound Processes

The sound processes are actually defined as Pure Data patches, though every other musical application handling OpenSoundControl could be used. Pure Data (PD) is a visual programming language, written originally by Miller Puckette [START_REF] Puckette | Pure data[END_REF] and aimed at developping musical and visual interactive applications. In our case, the patch parses the OpenSoundControl messages of the opportunistic widgets, and sends the values to the associated sound process parameter. An example of application is shown in figure 8.

Practical Example

give here a practical example which summarizes an opportunistic music session from the musician point of view. We assume the musician previously defined a PD patch on his computer composed of a sine wave oscillator, a sample player, and a loop player. The user first needs to associate each sound parameter to a physical mapping button, for example the parameter's name written on a sheet of paper. Then he chooses objects of his surrounding environment (e.g. his office) he wants to play with. One possible setup may thus consist of a phone, a book, a roll of scotch-tape. The musician maps the frequency of the oscillator to the border of the phone. To do this, he starts the registration step by hitting a mapping button previously defined. Then, he slides his finger along the phone to define the widget. The widget, i.e. the 3D position composing it, is registered by the system as soon as he releases his finger. The musician can then define a new widget. For example, he can map the trigger of a drum loop to the top of the scotch tape, allowing to start/stop playing the loop when hitting its surface. He finally defines a fader controlling the read head of a sound on the border of the book, using a small box to physically keep the position of the fader. This setup allows him to start a drum loop with the scotch tape, play notes with the phone and scratch with the book. Technically, the system does not need to identify the objects by way of vision techniques. It only detects if the musician's finger belongs to a previously defined 3D area when a pressure event is detected.

Conclusion and Future Work

Opportunistic music is a new concept for on-site inspired musical pieces. It opens the way to new artistic creation possibilities. The first prototype we have developed allowed us to experiment this concept. Our work is too preliminary to conduct a formal user study. However, the feedback we had from artists encourage us to continue our developments in that direction. The next step of our work will be to make the system fully mobile, as described in section 3.2. This will allow to completely leverage the concept of opportunistic music. We also plan to develop new widgets to make interaction richer, and we will experiment the use of a pico-projector to augment the musicians environments with some visual feedbacks.

Another direction we whish explore is the integration of live-recording functionalities. By adding microphones close to the users' fingers, we could directly interact with the sounds produced by the real world. For example, the musician could interact with metallic sounds by hitting a metallic object. This live-recording concept, which as been introduced by [START_REF] Raffle | The sound of touch[END_REF], would be particularly interesting in our opportunistic setup.

The development of our system was motivated by musical needs. We think it could be used for other purposes, sharing the initial motivation of Henderson and Feiner [START_REF] Henderson | Opportunistic controls: leveraging natural affordances as tangible user interfaces for augmented reality[END_REF]. The high reactivity we obtain thanks to the combination of FSR sensors and infrared stereo-vision could benefit to many domains. Similarly, the principle of live creation of opportunistic widgets, as well as the proposed implementation, could be valuable to other AR applications. Music inspired our work. We hope that our work will inspire new developments.

Figure 1 :

 1 Figure 1: A phone used as an opportunistic fader to control a sound parameter.

Figure 2 :

 2 Figure 2: Examples of opportunistic widgets. (left) Curved and linear widgets are defined on a desktop environment. The rubber band of the folder is used to benefit from elastic feedback. The staples box slides along the book. A post-it with an annotation is also used. (right) Outside environments may be very inspiring, as well. In this example, different natural textures are used to distinguish the widgets.

Figure 3 :

 3 Figure 3: Opportunistic music prototype. (left) General setup with camera pair, finger mounted FSR+LED interaction device, FSR analog acquisition board. (right) Close-up of the thimble interaction device, with FSR sensor and infrared LED.

Figure 4 :

 4 Figure 4: Mobile setup

Figure 5 :

 5 Figure 5: Proximity test and interpolation computation

Figure 8 :

 8 Figure 8: An example of application with 3 opportunistic widgets associated to 3 sound parameters.

Figure 7 :

 7 Figure 7: Example of a widget output when sliding a tracked finger along it.

c The Eurographics Association 2009.

† Typically found in computer vision libraries such as OpenCV. c The Eurographics Association 2009.

Acknowledgment

The authors would like to thank the Studios de Création et de Recherche en Informatique et Musique Electroacoustique (SCRIME) for the material they made available for us, and particularly Joseph Larralde for his help.


Romain Picot-Clémente
email: romain.picot-clemente@u-bourgogne.fr

Christophe Cruz
email: christophe.cruz@u-bourgogne.fr

Christophe Nicolle Le2i
email: christophe.nicolle@u-bourgogne.fr

A Semantic-based Recommender System Using A Simulated Annealing Algorithm

Keywords: Semantic based recommender system, adaptive hypermedia system, simulated annealing algorithm, tourist travel. I

A recommender system based on semantic web technologies and on an adaptive hypermedia architecture is shown in this paper. The system uses a stochastic algorithm to provide recommendations to users. The paper presents the system architecture based on the semantic Web technologies and explains a simulated annealing algorithm performing the recommendations. A mobile application for the tourism domain proving the feasibility of this system is described at the end of the paper, some benchmarks are presented. In this application, the recommendations are defined as combinations of tourism products, which are linked to each other. The paper is mainly focused on the architecture and the recommendation process of the system.

INTRODUCTION

These last years, the number of customer relationship management (CRM) implementations has increased enormously. CRM systems aim at allowing organizations to provide fast and efficient user-focused services. A CRM system uses client related information or knowledge to provide relevant products or services to clients [START_REF] Levine | The rise of CRM[END_REF]. The increasing use of digital technologies by customers, and particularly the Web and mobile devices, is changing what is possible and what is expected in terms of customer management. CRM evolved from business processes such as the need to improve the client retention by the effective management of customer relationships [START_REF] Bull | Strategic issues in customer relationship management (CRM) implementation[END_REF].

Our project aims to facilitate tourists for the definition of a complete journey on the region Côte d'Or in Burgundy, France from a database composed of more than 4 thousand geo-localized tourism products. Today, searching and finding relevant tourism products related to a user profile is tedious. Consequently, a recommendation system has been defined. The use of personalized recommender systems [START_REF] Tintarev | A survey of explanations in recommender systems[END_REF] [4] [START_REF] Mcsherry | Explanation in recommender systems[END_REF] to assist customers in the selection of products is becoming more and more popular and wide-spread. Most of the recommender systems is based on algorithms computing recommendations using methods like collaborative filtering [START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF] [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF], content-based classifier [START_REF] Mooney | Content-based book recommending using learning for text categorization[END_REF] [START_REF] Pazzani | Syskill & Webert: Identifying interesting web sites[END_REF] and hybrids of these two techniques [START_REF] Basu | Recommendation as classification: Using social and content-based information in recommendation[END_REF] [START_REF] Melville | Contentboosted collaborative filtering for improved recommendations[END_REF] [START_REF] Sarwar | Using filtering agents to improve prediction quality in the grouplens research collaborative filtering system[END_REF].

Recommender systems suggest information sources and products to users based on learning from examples of their likes and dislikes [START_REF] Bilgic | Explaining recommendations: Satisfaction vs. promotion[END_REF]. A typical recommender system has three steps: 1/ Users provide examples of their tastes. These can be explicit, like demanding ratings of specific items, or implicit, like analyzing his browsing behavior. 2/ A user profile is computed using the information from the first step. It is a representation of the user's likes and dislikes; 3/The system computes recommendations using these user profiles.

Content-based (CB) and collaborative filtering (CF) methods are two of the main approaches used to form recommendations. Hybrid techniques integrating these two different approaches have also been proposed. The CB method has been based on the textual filtering model described in [START_REF] Oard | The State of the Art in Text Filtering[END_REF]. Generally, in CB systems, the user profile is inferred automatically from documents' content that the user has seen and rated. The profiles and domain documents are then used as input of a classification algorithm. The documents which are similar (in content) to the user profile are considered interesting and are recommended to the user.

CF systems [6] [7] are an alternative to CB systems. The basic idea is to go beyond the experience of an individual user profile and instead to use the experiences of a population or community of users. These systems are designed with the assumption that a good way to find interesting content is to find people with similar tastes and to propose items they like. Typically, each user is associated to a set of nearest-neighbor users, comparing profiles' information. With this method, objects recommendations are based on similarities of users rather than the similarities of objects.

Both CF and CB systems have strengths and weaknesses. In CF systems, the main problem is that the new objects with no rate cannot be recommended. CB systems suffer from deficiencies in the way of selecting items for recommendation. Indeed, the objects are recommended if the user has seen and liked similar objects in the past. Consequently, a variety of hybrid systems have recently been developed: 1/ Some use other users' ratings as additional features in a CB system [START_REF] Basu | Recommendation as classification: Using social and content-based information in recommendation[END_REF]. 2/ Some use CB methods for the creation of bots producing additional data for "pseudo-users". These data are combined with real users' data using CF methods [START_REF] Sarwar | Using filtering agents to improve prediction quality in the grouplens research collaborative filtering system[END_REF]. 3/ Others use CB predictions to "fill out" the probable user-items' ratings in order to allow CF techniques to produce more accurate recommendations [START_REF] Melville | Contentboosted collaborative filtering for improved recommendations[END_REF].

We have developed a CB system inspired by Adaptive Hypermedia systems. Adaptive hypermedia systems are hypermedia systems (websites, e-learning platforms, etc.) with adaptive behavior to provide adaptive content, presentation and navigation to users, based on their knowledge, preferences, goals, etc. The purpose of the proposed system is to find the best combination of individuals from a domain ontology that fit to the user interest and we propose the use a simulated annealing algorithm to do this. The first part explains what an adaptive hypermedia system is. It is also shown in this part how adaptive hypermedia systems are positioned relative to recommender systems. Then, a part describes the architecture, the properties and the recommendation process of the proposed recommender system applied to tourism domain. The next part shows a utilization example for a touristic journey proposition and the final one gives some benchmark of the application.

II. ADAPTIVE HYPERMEDIA SYSTEMS

The research domain of adaptive hypermedia has been very prolific these 10 last years. Some systems [START_REF] Brusilovsky | Web-based education for all: A tool for developing adaptive courseware[END_REF] [15] [START_REF] Henze | Adaptive hyperbooks: Adaptation for project-based learning resources[END_REF] have been developed, giving principally solutions for e-Learning which is considered as the first application domain. Each system brings its own architecture and methods. Moreover, few attempts have been made to define reference models [START_REF] Cristea | The Three Layers of Adaptation Granularity[END_REF] [START_REF] Hendrix | A. Meta-levels of adaptation in education[END_REF] [19] [START_REF] De Bra | AHAM: A dexter-based reference model for adaptive hypermedia[END_REF] but without success because of being not enough generic to take account of the new trends and innovations. Nevertheless, most of the systems and models are based on a set of layers, also called models, which separate clearly the different tasks. Then, we can see that there are at least three models in common, necessary and sufficient to achieve adaptive hypermedia systems according to Brusilovsky [START_REF] Brusilovsky | Adaptive hypermedia, User modeling and user-adapted interaction[END_REF]. It needs to primarily be a hypermedia system based on a domain. The domain model is a representation of the knowledge on a given subject the creator wants to deliver. It describes how the domain is organized and interconnected. The second model is called a user model which is a representation of the user within the system. It models all user information which may require the system to provide an adaptation. The last model is the adaptation model. It performs all the adaptive algorithms based on other models to provide an adaptation to the user. Beyond the use of domain, user and adaptation models, the trend is to use additional models like presentation, goals, context or other models. This allows to better identify the different performed tasks and to facilitate the construction of adaptive hypermedia systems. Nevertheless, there is no generic model integrating them for the moment.

Methods to model domain/user (adaptation principles are also described):

The keywords vectors space methods consider that each document and user profile is described by a set of weighted keywords vectors [START_REF] Moukas | Amalthaea: Information Discovery and Filtering using a Multiagent Evolving Ecosystem[END_REF] [23] [START_REF] Armstrong | WebWatcher: A Learning Apprentice for the World Wide Web[END_REF]. At the adaptation model, the weights are used to calculate the similarity degree between two vectors and then to propose relevant document to the user. The keywords representation is popular because of its simplicity and its efficiency. Nevertheless, the main drawback is that a lot of information is lost during the representation phase.

In semantic networks, each node represents a concept. Minio and Tasso [START_REF] Minio | User Modeling for Information Filtering on INTERNET Services: Exploiting an Extended Version of the UMT Shell[END_REF] present a semantic networks based approach where each node contains a particular word of a corpus and arcs are created following the co-occurrences of the words from connected nodes into the documents. Each domain document is represented like that. In simple systems using only one semantic network to model the user, each node contains only one keyword. The keywords are extracted from pages which the user gives its taste. Then, they are treated to keep only the most relevant ones and are weighted in order to remove those with a weight lesser than a predefined threshold. The selected keywords are then added to the semantic network where each node represents a keyword and each arc their co-occurrence into the documents. With this method, it is possible to evaluate the relevance of a document compared to the user profile. Indeed, it suffices to construct a semantic network of a document and compare it to the semantic network of the user to classify it to interesting, uninteresting or indifferent documents.

Ontology approach is similar to the semantic network approach in the sense that both are represented using nodes and relations between nodes. Nevertheless, in concepts based profiles, nodes represent abstract subjects and not word or set of words. Moreover, links are not only cooccurrence relations between words, they have several significations. The use of ontology can keep a maximum of information. In QuickStep [START_REF] Middleton | Exploiting synergy between ontologies and recommender systems[END_REF], the ontology is used for the research domain and has been created by domain experts. The ontology concepts are represented as vectors of article examples. The users' papers from their publication list are modeled as characteristic' vectors and are linked to concepts using the nearest neighbor algorithm. These concepts are then used to form a user profile. Each concept is weighted by the number of papers linked to it. Recommendations are then made from the correlations between the current interests of the user to topics and papers that are related to these topics. In [START_REF] Cantador | A multilayered ontology-based user profiles and semantic social networks for recommender systems[END_REF] and [START_REF] Sieg | Learning Ontology-Based User Profiles: A Semantic Approach to Personalized Web Search[END_REF], a predefined ontology is used to model the domain. User profiles are represented with a set of weighted concepts where weight represents the user's interest for a concept. Its interests are determined by analyzing its behavior.

Three types of adaptation have been highlighted in the researches on adaptive hypermedia systems: content, navigation and presentation adaptation. The content adaptation consists in hiding/showing or highlighting some information. The adaptation model makes the decision of which content has to be adapted and how to display it. The navigation adaptation consists in modifying the link structure suggesting links or forcing the user to follow a destination. There is URLs' adaptation or destinations adaptation. In the first, the adaptation model provides destination links to the presentation model; these links are displayed at the page generation. Whereas, in the second one, the adaptation model provides links without fixed destination to the presentation model; the destination is decided by the adaptation model when the link is accessed by the user. The presentation adaptation consists in insisting (or not) on the content parts or on the links. It consists also in adapting the preferences setting to the device or the page. The adaptation model process makes the decision of which content or links to insist in following the presentation context. Even if recommender systems are often differentiated from adaptive hypermedia systems, a lot of similarity between these two types of systems can be highlighted. Indeed, the recommender systems provide recommendations using different algorithms, as it is done in the adaptation model. Moreover, we can see that they model also users' tastes and domain's items, as it is done in adaptive hypermedia systems with the user model and domain model. Nevertheless, recommender systems perform only adaptation of the content whereas adaptive hypermedia systems realize two more adaptation types. Following these observations, a recommendation system appears to be a constrained adaptive hypermedia system. Thus, it seems clear that recommender systems can be defined as a subset of adaptive hypermedia systems, whatever its type (CB or CF).

The use of an adaptive hypermedia architecture for the creation of recommender systems is interesting because we can clearly define the tasks associated with each part of the application, and it gives the opportunity to evolve the system adding modules and/or other types of adaptation without difficult modifications of parts already implemented. For instance, a CB recommender system could be improved with features of CF systems, adding a group model where clusters of users can be defined. For the creation of our CB recommender system, we base on adaptive hypermedia architecture. Beyond the use of the three main ones (domain, user and adaptation model), a goal model has been added. It allows the modeling of users' goals. A description of the architecture is explained in the following part.

III. THE PROPOSED RECOMMENDER SYSTEM

This part describes, first, the architecture of the proposed recommender system. Then, the recommendation process is explained, it is based on a simulated annealing algorithm. It is followed by an overview of the implementation for the tourism application.

A. Architecture

The proposed recommendation system is based on a set of layers (models). It consists of a user model, a domain model, an adaptation model and a goal model. This modeling allows a clear separation between the tasks. The domain model defines the whole domain knowledge. It consists of sets of domain concepts and relations between concepts. Generally, the concepts index the contents or the pages in order to be provided to the user. The most appropriate structure we have chosen for this modeling is the ontology. Actually, it facilitates the creation of complex structures. It allows also the inferences and this structure is portable thanks to the standardized OWL language. The ontology concepts are populated by individuals representing instances of these concepts which can be provided to the user.

The goal model is an overlay model on the domain model. Actually, it consists of a set of goal concepts that bring together individuals of the domain model. A goal concept is a set of domain model individuals, knowing that different goal concepts can group same individuals. A goal is defined by an SWRL rule allowing the selection of the individuals which verifies the rule.

The user model aims at modeling the user into the system. In the present case, it is composed of two parts. The first part is based on the goal model which is based, by definition, on the domain model. This part is called overlay part on the domain or domain dependant part, or even dynamic part because it is very changeable. Instead, the second part is called static part; it is a domain independent part. The user model is composed of a set of goals concepts, selected using the user behavior and <attribute-value> pairs for data such as date of birth, gender, etc. With the dynamic part, we have an idea of the user interests on domain individuals. Actually, when an individual appears into more than one goal concept selected by the user, then this individual is considered more important for the user. Thus, we can induce interest weights on the domain individuals related to the selected goal concepts. Moreover, we can propagate these weights to the entire domain model using the links into the domain ontology.

The adaptation model is considered as the core of the system, the adaptive algorithms are carry out in this level. The recommendations provided to the user are formulated as a combination of individuals from the domain model, according its user model. The problem consists in finding the optimal combination of individuals from the domain model constrained by a user model. Browsing all the possible combinations to find the best one is not possible in a short time, consequently, we propose the use of a stochastic algorithm called simulated annealing in order to find a combination which is close to the best one in a short time. Simulated annealing [START_REF] Laarhoven | Simulated Annealing: Theory and Applications[END_REF] is an optimization technique particularly well suited to overcoming the multiple minima problem. Unlike gradient-descent methods, simulated annealing can cross barriers between minima and thus can explore a greater volume of the parameter space to find better models in deeper minima.

This algorithm is used to minimize an energy function defining the relevance of a combination according to a user model. This energy depends mainly on the interest weights deduced from the user dynamic part on the domain individuals. But, depending on the type of application, more parameters can be taken into account. For instance, we can use geographic parameters for an application which aims to provide a nearby restaurant corresponding to the user requirements and coordinates. Moreover, constraints can be defined in the ontology between individuals or/and concepts. For instance, a medical application which provides a combination of medicines has to indicate in the ontology when one medicine cannot be given with another one, so that the application cannot generate a bad combination.

B. Recommendation process

The recommender system aims at providing a combination of individuals from the ontology. This part presents how this recommendation is undertaken.

In order to solve the problem of providing the best combination of individuals from the domain model, we propose the use of a stochastic algorithm called simulated annealing for its resolution. Actually, this kind of algorithms allows to find a solution that approaches the best (or is the best) in a very short time. The simulated annealing is inspired from a method used in the steel industry. To obtain a metal with a perfect structure crystal type (fundamental state corresponding to the minimum internal energy), the process is as follow: after bringing the material to liquid, the temperature is lowered to solidification state. If the decrease of temperature is very sudden, a "glass" is obtained, feature of the technique of "hardening". On the contrary, if it is very gradual, allowing time for atoms to reach statistical equilibrium, it will tend toward more regular structures, to finish in the ground state: the "crystal", characterizing the system freeze. If this lower of temperature is not slow enough, defects could appear. Then, it would be necessary to correct them by heating the material again slightly to allow atoms to regain freedom of movement and facilitating a possible rearrangement toward a more stable structure.

The simulated annealing algorithm used into the adaptation model is based on this principle. At the beginning, the algorithm chooses an initial random combination of individuals following a given pattern (for instance, a combination consisting of a hotel, two restaurants and two activities). This combination has an energy E 0 , called the initial energy, which represents the quality of a combination. The lower the energy is, the better the combination is. A variable T, called temperature, decreases in increments over time. At each level of temperature is tested a number of elementary random changes on the current combination. A cost d f is associated to each modification; it is defined as the difference between the combination's energy after the modification and the one before. A negative cost signifies the current combination has a lesser energy than the previous one (thus better by definition), it is then kept. Conversely, a positive cost represents a "bad" change. Nevertheless, it can be kept according a given probability (acceptance rate a t ) depending on the temperature and the cost. The higher the temperature is, the higher the probability is. Thus, over time, the number of changes allowed decreases as the temperature decreases, until no longer accepting any changes. Finally, the system is said frozen, and the current combination becomes the final combination to be presented to the user. The acceptance rate is defined in (1) where T k is the temperature at the level k, k N. An initial temperature T 0 is computed using this formula and setting the values of the acceptance rate and the cost. The initial acceptance rate is defined arbitrarily and the cost is set calculating the average cost by performing multiple changes on random combinations. Thus, the initial temperature is presented in (2) where d fmean is the average cost of the modifications.

The temperature decrease is achieved through a geometric decay at each level:

0 1 1 ) ( T coef T coef T g T k k k k
where k is the current level and 0<coef<1.

The relevance of a combination is determined by an energy function. The quality of the final combination, given by the simulated annealing algorithm, depends a lot on the definition of this energy. This function is highly dependent on the type of application. For instance, in a tourism application, the individuals and user coordinates could be taken into account, whereas these data are useless in a medical application. Nevertheless, the energy function is based, in all cases, on the user interests deduced from its dynamic part.

The dynamic part is constituted of goals determined by the user clicks on icons which are linked to goals. Thus, each time a user clicks on an icon, the related goal is added to the dynamic part of its user model. To deduce the user's interest weights on the ontology individuals, an algorithm of weight propagation uses the fact that each goal is a set of rules including individuals from the domain model. Thus, each time an individual is selected by a rule, its weight is incremented. Therefore, this weighting allows the demarcation of some individuals, giving an idea of the user interests. With this modeling, after few user clicks on icons, the system can quickly provide a combination of domain individuals that matches its interests. According the definition, this type of recommender system is a CB system. Nevertheless, it is also possible to base on group of users to have the benefits of CF systems. It just needs to add a group model to the system. The next part shows an application of this modeling for a tourism application which is currently in development.

C. Tourism implementation

This modeling is being applied to the tourism domain in the region of Côte-d'Or in France for the company Côted'Or Tourisme. The aim is to create a tourism application that should provide a combination of tourism products from Côte-d'Or according to a user profile. At the beginning, a domain ontology has been created with all the concepts and the individuals related to the application domain. This ontology was supplied from a database composed of more than 3000 tourism products. Then, a goal model has been defined using goal concepts like "Week end", "Going out with friends", "with a baby", etc. This knowledge was generated from the specialists of the domain represented by people working for the company Côte-d'Or Tourisme.

An empirical pattern is defined to determine what kind of combination the adaptation model has to return. The energy function which gives the relevance of a combination is based on the interest weights and the coordinates of the tourism products, because it is not relevant to propose an activity in the morning and a restaurant for lunch with a distance of more than 50 kilometers. The traveling time required to reach the restaurant after the activity ending is inappropriate.

A variance threshold needs to be set in order to define the maximum preferred variance between the individuals coordinates. This variance characterized the value dispersion regarding the average, in this case the threshold. The subsets in this pattern are possible. For instance, we can define a pattern like "Accommodation, Restaurant1, Activity, Restaurant2" in which "Accomodation and Restaurant1" are the first subset, and "Activity and Restaurant2" the second subset. In addition, a variance threshold is defined for each one. Thereby, the system can use more complex patterns for the combinations.

The variance of a combination is defined as follow:

1 0 2 2 1 0 2 1 0 1 1 1 ) var( N i N i iy iy N i ix ix C N C C N C N C
where C is a combination, N the number of elements into the combination, C i the i th element of the combination, and C ix and C iy the x and y coordinates of the i th element. The weight of a combination is defined as follow: Using the variance and the weight function, the energy of a combination is:

1 0 ) var( ) var( ) ( 1 ) ( L j G Cj C Cj Threshold G E Threshold C E C weight C Energy
where E(X) is the integer part of X, Threshold C is the variance threshold of the geographic coordinates for the combination C, Cj G Threshold is the variance threshold of the geographic coordinates for the j th subset of C, and L the number avec subsets. Thus, the system performs the simulated annealing algorithm using this energy function and a user profile, so that it can provide a combination of tourism products matching its interests and close coordinates. The result of the algorithm gives a combination of close products with high weights. The next part shows an example of a touristic journey provided by this implementation. An interface has been developed for iPhone.

IV. AN UTILIZATION EXAMPLE

An interface for this tourism implementation has been developed for iPhone. This part explains briefly the utilization of this application. The user is first invited to define his profile by giving his stay duration and by clicking on goal icons in order to inform on its interests. Moreover, the geographic coordinates of the user can be used or specific geographic coordinates can be specified for a preferred area. Nevertheless, if no area is given, the area will be the entire region of Côte-d'Or. Tourism products can be also selected and a complete stay will be generated relevantly according these selections. After this step, the adaptation process is performed using the simulated annealing algorithm and the system provides a combination of tourism offers, corresponding to the user's profile, in a carousel. If the solution does not satisfy the user, he is able to demand a new generation, keeping some elements if wanted. Thus, the system takes the kept elements into account to provide a new combination. This new solution is generated by fixing the kept elements into the combination. Thus, only the others elements of the combination are modified during the process of researching the best combination. The kept elements are only considered for the energy computations. A benchmark is presented in the next part to show the relevance of the simulated annealing algorithm.

V. BENCHMARK Some tests of the algorithm for the generation of combinations have been done on a set of three thousand tourism products. We did comparisons between the energy of random combinations, the energy of the solutions found by the algorithm and the energy of the optimal combination. The solutions given by the simulated annealing algorithm are closed or equal to the optimal solution in terms of energy. In these tests, the average time required for the generation of a combination of six products was around 3 seconds. But, this time depends on the different parameters (temperature decrease rate, the number of iteration per level of temperature) necessary to perform the simulated annealing algorithm. The faster is the temperature decrease and the lower is the number of iterations, the faster is the generation, but the worse is the resulting combination. In any case, this time is better than the time required to find the best combination by browsing all the possibilities. For example, in our test, finding the best combination needed around 3 hours against 3 seconds using the simulated annealing algorithm. These times are only given to have orders of magnitude, more tests need to be performed to have exacts results and to prove the interest of our proposition. Nevertheless, given these few results, the algorithm seems to give a relevant solution according a predefined energy function with a lesser cost (in terms of time) than calculating the optimal solution.

VI. CONCLUSION

In this article, we presented a new content based recommender system in order to improve the customer relationship management in e-tourism. The idea consists to take advantages of the semantic Web technologies, the properties of adaptive hypermedia systems, and to combine them with combinatory algorithms in order to create a recommender system. The simulated annealing algorithm is used in order to solve the problem of the polynomial time search required to generate a combination of tourism products. It gives a solution which approaches the best solution in a short time. The few results seem to be good considering the time required to obtain them and comparing to the best solutions. Nevertheless, for the future, we need to make more tests and benchmarks to quantify more precisely the relevance of our system. Moreover, we could improve the quality of the propositions by taking into account some group of users as it is done in collaborative filtering recommender systems. This is possible by adding a group model into the architecture. Thus, the recommender system would become a hybrid recommender system.

  is the weight of the i th element.

ACKNOWLEDGMENT

This research is done in collaboration with Côte-d'Or Tourisme, a company which aims to promote tourism in its region. The authors would like to thank Quentin Collin and Erwan Privat for their help.