Hideaki Uchiyama
email: hideaki.uchiyama@inria.fr

Eric Marchand
email: eric.marchand@irisa.fr

Toward Augmenting Everything: Detecting and Tracking Geometrical Features on Planar Objects

Keywords: H.5.1 [INFORMATION INTERFACES AND PRESENTATION (e.g., HCI)]: Multimedia Information Systems-Artificial, augmented, and virtual realities; I.4.8 [IMAGE PROCESSING AND COMPUTER VISION]: Scene Analysis-Tracking

 for geometrical feature based keypoint matching. Because the stability of keypoint extraction affects the accuracy of the keypoint matching, we set the criteria of keypoint selection on keypoint response and the distance between keypoints. In order to produce robustness to scale changes, we build a non-uniform image pyramid according to keypoint distribution at each scale. In the experiments, we evaluate the applicability of traditional keypoint detectors with LLAH for the detection. We also compare our approach with SURF and finally demonstrate that it is possible to detect and track different types of textures including colorful pictures, binary fiducial markers and handwritings.

INTRODUCTION

6DoF object detection and tracking are basically two important technologies for vision based augmented reality. Object retrieval (also known as recognition or identification) is recently incorporated in the detection such that an object is captured in an image, retrieved from a database and its initial pose is simultaneously computed [START_REF] Pilet | Virtually augmenting hundreds of real pictures: An approach based on learning, retrieval, and tracking[END_REF]. Once an object is detected, it is tracked from the next frame by tracking keypoints [START_REF] Wagner | Pose tracking from natural features on mobile phones[END_REF] or minimizing the difference between two consecutive images under blurring [START_REF] Park | ESM-Blur: Handling & rendering blur in 3D tracking and augmentation[END_REF] and non-linear illumination change [START_REF] Dame | Accurate real-time tracking using mutual information[END_REF]. This type of tracking is named tracking by tracking. Detecting an object at every frame is another type of tracking named tracking by matching [START_REF] Ozuysal | Fast keypoint recognition using random ferns[END_REF].

Generally, object detection is based on local texture descriptors such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Because the orientation histogram based keypoint descriptor in SIFT is considered as discriminative enough for large-scale keypoint matching, several attempts to approximate and simplify SIFT have been actively investigated in recent years [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF][START_REF] Wagner | Pose tracking from natural features on mobile phones[END_REF][START_REF] Chandrasekhar | CHoG: Compressed histogram of gradients a low bitrate feature descriptor[END_REF][START_REF] Takacs | Unified real-time tracking and recognition with rotationinvariant fast features[END_REF]. Normally, keypoint matching with those methods works well for rich textures that have the variety of intensity in a local patch such as Figure 1(a). However, binary textures such as Figure 1(b), (c) and (d) do not have enough variety of intensity and are hardly detected by those methods. Especially, it is almost impossible to detect random dot markers in Figure 1(e) because local texture at each dot is exactly same. This means that a wide variety of textures cannot be detected with only local texture based descriptors. To address this issue and develop an all-in-one solution, we Figure 1: Our objective is to detect and track various types of textures such as (a) graffiti [START_REF] Mikolajczyk | Scale & affine invariant interest point detectors[END_REF], (b) handwriting, (c) poster for ISMAR 2011, (d) ARToolKit marker [START_REF] Kato | Marker tracking and HMD calibration for a video-based augmented reality conferencing system[END_REF] and (e) random dot marker [START_REF] Uchiyama | Random dot markers[END_REF] with only one method.

need to drastically shift the approach for keypoint matching.

In this paper, we propose an approach for detecting and tracking various types of planar objects with geometrical features. Compared with traditional methods, we do not use local texture based descriptors. Instead, we employ geometrical relationship between keypoints as a descriptor. Whereas this type of method was not much discussed in the community of computer vision and augmented reality, similar methods were proposed for document image retrieval [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF][START_REF] Moraleda | Toward massive scalability in image matching[END_REF]. Because those methods were dedicated to retrieving only text document images, we generalize them for common object retrieval.

In our approach, keypoints are first extracted with a traditional keypoint detector. Next, we select stable keypoints by considering keypoint response and the distance between keypoints. After selecting keypoints, we compute geometrical descriptors for each keypoint and find correspondences between an input image and a database with LLAH [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF]. From the next frame, we perform keypoint matching between two consecutive frames to track objects with LLAH. To improve the robustness for scale changes, we build a non-uniform image pyramid according to the change of keypoint distribution at each scale.

To the present, geometrical feature based keypoint matching has not been much discussed yet. By investigating and evaluating such approach, we contribute to various kinds of researches based on keypoint matching. Especially, the approach has a possibility to relax the limitation of target objects for augmented reality applications toward "augmenting everything".

The remain of the paper is organized as follows. In the next section, we review traditional keypoint detectors and local descriptors. Section 3 briefly describes LLAH based keypoint matching and tracking for text documents because it is a key technique in our approach. Section 4 explains the detailed parts of detecting and tracking geometrical features. In Section 5, we quantitatively evaluate the robustness of our approach by comparing with SURF [START_REF] Bay | Speeded-up robust features (SURF)[END_REF]. In Section 7, we show augmentation results for various types of textures.

RELATED WORKS

Detecting keypoints is an initial step in various researches and has been investigated for a long time. Harris corner detector is one of the most popular methods that computes a corner score from the determinant and trace of autocorrelation matrix [START_REF] Harris | A combined corner and edge detector[END_REF]. FAST corner detector selects a pixel that has higher or lower value than neighbors with a machine learning technique [START_REF] Rosten | Faster and better: A machine learning approach to corner detection[END_REF]. Mair, et al. improved FAST by building an optimal decision tree [START_REF] Mair | Adaptive and generic corner detection based on the accelerated segment test[END_REF]. These detectors can be incorporated onto an image pyramid such that keypoints are detected in a scale invariant manner. The keypoint detector in SIFT is based on building a scale space with Differences of Gaussians (DoG) computed by subtracting blurred images [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. In this method, a point with a local extrema on the space is selected as a keypoint. Another type of scale space is constructed by resizing a filter on a single scale in the following methods. In SURF, Hessian is approximated by box filters and its response is efficiently computed from integral images [START_REF] Bay | Speeded-up robust features (SURF)[END_REF]. In CenSurE, Laplacian filters with the different sizes of octagons and boxes are computed from integral images as well [START_REF] Agrawal | CenSurE: Center surround extremas for realtime feature detection and matching[END_REF]. In CSDD, a central foreground region is compared with its surrounding by computing Laplacian of Gaussian (LoG) with IIR filters [START_REF] Collins | CSDD features: Center-surround distribution distance for feature extraction and matching[END_REF].

For keypoint description, the recent major approach is the approximation and simplification of SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Mikolajczyk and Schmid [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF] proposed spatial sampling of gradient using a log-polar location grid named GLOH compared with a Cartesian grid in SIFT. For mobile devices, Wagner, et al. used smaller size of a sampling grid and fewer quantization level of orientations to simplify SIFT as Phony SIFT [START_REF] Wagner | Pose tracking from natural features on mobile phones[END_REF]. In CHoG, a tree coding technique is used to quantize and compress a histogram of gradient into a low bit rate feature [START_REF] Chandrasekhar | CHoG: Compressed histogram of gradients a low bitrate feature descriptor[END_REF]. For an orientation invariant descriptor, Takacs, et al. developed RIFF that performed radial gradient transform for gradient binning [START_REF] Takacs | Unified real-time tracking and recognition with rotationinvariant fast features[END_REF]. For other types of descriptors, hundreds of binary features in a local patch are computed for a random fern based classification [START_REF] Ozuysal | Fast keypoint recognition using random ferns[END_REF] and BRIFF [START_REF] Calonder | BRIEF: Binary robust independent elementary features[END_REF].

Due to the development of various keypoint detectors and descriptors, their stability has quantitatively been evaluated from various aspects such as rotation and illumination changes. In 2000, Schmid, et al. reported that Harris was better than other detectors in various cases [START_REF] Schmid | Evaluation of interest point detectors[END_REF]. For keypoint matching on 3D objects, Hessianaffine and Harris-affine detectors with the descriptor in SIFT outperformed other combinations [START_REF] Moreels | Evaluation of features detectors and descriptors based on 3D objects[END_REF]. Gauglitz, et al. evaluated all combinations of state-of-the-art keypoint detectors and descriptors with several parameters for visual tracking [START_REF] Gauglitz | Evaluation of interest point detectors and feature descriptors for visual tracking[END_REF]. They stated that it was difficult to select a single best method in all cases because each detector has advantages and disadvantages in a situation. Some of approaches incorporated geometrical features into local texture based descriptors. Chum and Matas proposed normalization of a local region computed from local affine frames on the outer boundaries of MSER with the scheme of geometric hashing [START_REF] Chum | Geometric hashing with local affine frames[END_REF].

Forssén and Lowe simply constructed pair descriptors with nearest neighbor keypoints [START_REF] Forssén | Shape descriptors for maximally stable extremal regions[END_REF].

DETECTING AND TRACKING DOCUMENTS USING LLAH

LLAH is a method for retrieving document images using geometrical features [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF]. It was extended to a method for tracking documents for augmented reality applications [START_REF] Uchiyama | Camera tracking by online learning of keypoint arrangements using LLAH in augmented reality applications[END_REF]. Also, this technique was applied to the development of random dot markers [START_REF] Uchiyama | Random dot markers[END_REF]. Because our approach in this paper is crucially related with these works, we briefly review the procedure to assist the understanding of overall parts of our method.

Descriptors

We explain the procedure to compute descriptors with Figure 2. For each keypoint, x ′ y ′ coordinate system is set and n nearest neighbor points are selected in anti-clockwise direction on the coordinate system (n = 7 in the figure). The order of the selection is pre-defined such that we start from a (the point closest to x ′ at the first quadrant). Second, m points are selected from n points to compute one descriptor. This means that the number of descriptors for a keypoint is n C m . For m points, 4 points are selected to compute the ratio of two triangles. By computing all combinations, m C 4 dimensional descriptor is constructed. The descriptor is finally quantized into one dimension as index by a hash scheme. Note that these descriptors are not rotation-invariant because the starting point a varies when capturing these points from different viewpoints.

Detection

First, the descriptors (indices) are computed for each keypoint on a reference and stored into an inverted file as (index, keypoint IDs). To achieve rotation-invariant matching, the starting point a is set at all n neighbor points for computing the descriptors. Thus, the total number of computed descriptors for a keypoint is n • n C m .

In the keypoint matching, n C m descriptors are computed and keypoint IDs are retrieved from the inverted file to make a histogram of keypoint IDs versus its retrieval frequency. A keypoint ID that got the maximum frequency is selected as matched. To remove outliers, geometrical verification is performed such that RANSAC based homography is computed for planar objects.

Tracking

LLAH based keypoint matching is also applied to matching between two consecutive frame for keypoint tracking [START_REF] Uchiyama | Camera tracking by online learning of keypoint arrangements using LLAH in augmented reality applications[END_REF][START_REF] Uchiyama | Random dot markers[END_REF]. This means that the detection and tracking of keypoints are performed with the same computation.

After geometrical verification in the detection, each keypoint on the reference is projected onto the input image to find the closest keypoint in the image. This process can increase correspondences, refine the homography and effectively work because the number of tracked keypoints decreases during moving a camera. To track keypoints, we perform keypoint matching between the keypoints obtained from the projection and those in the next frame.

DETECTING AND TRACKING GEOMETRICAL FEATURES

In this section, we explain the details of detecting and tracking geometrical features that work well for various types of textures.

Keypoint Extraction

We first tried applying document image retrieval using LLAH [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF] to typical image retrieval. However, it was far from working well because of the instability of keypoint extraction on normal textured patterns. In that method, binarization by adaptive thresholding is used as a word region detector. From a text document image, it can extract word regions and then the center of each region is computed as a keypoint. When we applied it to other textured patterns, it could not stably segment the patterns into comprehensible regions as illustrated in Figure 3. It turned out that the binarization by adaptive thresholding only worked well for extracting word regions in text documents.

As described in Section 2, various keypoint detectors have already been developed in the literature. Therefore, we decided to use them and select stable keypoints from the extracted keypoints because the same neighbors of a keypoint should be extracted from different views for keypoint matching. In the next section, we will explain how to select stable keypoints.

Keypoint Selection

Traditional keypoint detectors return the image coordinate of each keypoint with several parameters such as size, scale, angle and response. Some of these parameters might be useful as selection criteria. Size and scale are not meaningful because many keypoints have the same value. Though angle is variant for each keypoint, it is unlikely that a specific angle is better than others. Therefore, we select keypoint response to represent the quality of a keypoint as in [START_REF] Shi | Good features to track[END_REF] and assume that a keypoint with higher response can have higher repeatability. However, it is difficult to set a threshold for keypoint response because the response value depends on textured patterns. Instead, we set a threshold for the maximum number of extracted keypoints selected from the strongest response as first criterion. In traditional keypoint detectors, Harris [START_REF] Harris | A combined corner and edge detector[END_REF], FAST [START_REF] Rosten | Faster and better: A machine learning approach to corner detection[END_REF], Fast-Hessian in SURF [START_REF] Bay | Speeded-up robust features (SURF)[END_REF] and CenSurE [START_REF] Agrawal | CenSurE: Center surround extremas for realtime feature detection and matching[END_REF] provide keypoint response. In the evaluations, we compared the accuracy of the detection by all keypoint detectors with LLAH.

The distance between keypoints is also important criterion. When the neighbor points are too close, the ratio of two triangles cannot correctly be computed because the points are almost on a line or the triangles are small as illustrated in Figure 4(a). To compute geometrical features, keypoints should sparsely be distributed. Thus, we set a threshold for the minimum distance between keypoints as second criterion.

The overall procedure for selecting keypoints is as follows. We first sort all keypoints in the descending order of keypoint response. When we select one keypoint from the sorted keypoints, we compute the distance with the nearest neighbor in already-selected keypoints. If the distance is less than a threshold, it is discarded. When the total number of selected keypoints is over than a threshold, the selection is finished. An example of the selection is illustrated in Figure 4. Because these two thresholds affect the result of object detection, we investigate the influence in the evaluations.

Building Image Pyramid

To produce the robustness for scale changes, we take an image pyramid based approach. Usually, an image pyramid is built by resizing images with a fixed scaling such that the image of each pyramid level is generated by scaling down with a factor of 1/ √ 2 from the previous level as in [START_REF] Wagner | Pose tracking from natural features on mobile phones[END_REF]. However, such image pyramid was not efficient for our approach because keypoint distribution in two consecutive scales were quite different depending on textures. In this case, it is better to check the middle scale between two scales. Therefore, we develop a method for building an image pyramid with adaptively selected levels.

We first build an image pyramid with small scale changes, and then select appropriate level as illustrated in Figure 5. Full resolution corresponds to level 0 on the pyramid. From the next level, keypoint matching is performed with the previously selected level. Because the transformation is known, we can consider that a correspondence is an inlier when the reprojection error is less than a threshold (set as 3 pixels). Then, we simply compute an inlier rate from the matching result as Inlier rate = Number of inliers Number of retrieved keypoints .

(1)

Note that the denominator of this equation is not the number of extracted keypoints because a keypoint does not alway have a corresponding point with LLAH [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF]. We remove such keypoints from the extracted keypoints and use only the remaining as retrieved keypoints.

When an inlier rate is lower than a threshold, the level is selected for our image pyramid. For example, we set a threshold for acceptable inlier rate as 20% in Figure 5. We perform keypoint matching between level 1 and level 0, and skip level 1 from the matching result because the inlier rate is higher than the threshold. When level 3 is matched with level 0, level 3 is selected for our pyramid because of its inlier rate. Then, level 4 is matched with level 3 to judge whether level 4 is put into our pyramid or not. Image size x 0.9 x 0.8 x 0.7 x 0.6 x 0.5

Figure 5: Building a non-uniform image pyramid. The image is first resized with a factor of 1/10 compared with a full resolution. A pyramid level is selected for our image pyramid in the case that the inlier rate of keypoint matching with the previously selected pyramid level is lower than a threshold. When we set the threshold for the inlier rate as 20%, the selected pyramid levels were 0, 3 and 5 in this figure . The selected levels vary depending on keypoint detectors, two thresholds in the keypoint selection and target textures.

The result of selected levels depends on target textures, keypoint detectors and two thresholds in the keypoint selection. For example, Figure 1(a) with 600 × 480 pixels had there levels at 600 × 480, 480 × 384 and 360 × 288 whereas Figure 1(e) with 400 × 400 pixels had one level at 400 × 400 under the same condition as described in Section 7. This means that the image pyramid using a fixed scaling is not efficient.

Detection and Tracking

Detecting and tracking planar objects are based on a method described in Section 3. We incorporate the procedure for extracting and selecting stable keypoints on an image pyramid into the method.

At the beginning, we build our image pyramid of reference images to reduce computational cost in the on-line detection and tracking. We label each selected level on the pyramid as an individual reference and compute descriptors in the rotation invariant manner for a keypoint database.

For an input image in the detection, we compute the descriptors only on full resolution and find correspondences on the references. From the result of keypoint matching, we have the candidates of detected references with their pyramid level. This means that a reference image can be detected on different levels. By computing RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] based homography for each candidate, we finally select a reference at a level.

Once a reference is detected, it is tracked using the reference with a detected level. The keypoints on the reference are projected onto the input image to increase correspondences. In the next frame, keypoints extracted in the image were matched with the keypoints obtained from the projection. When tracking fails, we detect a reference in the database again.

EVALUATIONS WITH OUR DATASET

We first focused on the evaluations of object detection to clarify the applicability of traditional keypoint detectors with LLAH. As described in Section 3, the geometrical descriptors in LLAH should theoretically be rotation invariant. To evaluate the invariance, we prepared our dataset images captured under large rotations.

Overview

In order to capture the whole part of each texture with a rotating camera, we used a camera mounted on a robot arm to precisely control the rotation angle. We initially set the arm perpendicular to textured patterns in Figure 1 on a table and rotated it at 5 degrees increments through 90 degrees with centering around a principal point of the camera as illustrated in Figure 6. The resolution of captured grayscale images was 640 × 480.

We performed keypoint matching between the first frame and others, and counted inliers by computing a reprojection error with the ground truth of a rotation matrix obtained from the robot odometry. A keypoint is an inlier when the error is less than 3 pixels. The evaluation criterion was the inlier rate defined in Equation 1. Note that we did not build our image pyramid because the distance between a camera and a texture was fixed. We discussed the influence in a single scale in this section. Regarding the parameters in LLAH [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF], we set n = 7 and m = 5 for all experiments.

Comparison between Keypoint Detectors

We first compared the inlier rates computed with each traditional keypoint detector under large rotations. For all texture images in Figure 1, we tested our approach with Harris [START_REF] Harris | A combined corner and edge detector[END_REF], FAST [START_REF] Rosten | Faster and better: A machine learning approach to corner detection[END_REF], Fast-Hessian in SURF [START_REF] Bay | Speeded-up robust features (SURF)[END_REF] and STAR that was improved version of Cen-SurE [START_REF] Agrawal | CenSurE: Center surround extremas for realtime feature detection and matching[END_REF] implemented in OpenCV [1]. We used default parameters in OpenCV for all detectors. For two thresholds in the keypoint selection, we set the maximum number of keypoints as 200 and the minimum distance between keypoints as 10 pixels. As a comparison with a traditional local texture descriptor, we selected SURF [START_REF] Bay | Speeded-up robust features (SURF)[END_REF] for keypoint extraction and description and FLANN [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF] for keypoint matching implemented in OpenCV. We limited the maximum number of extracted keypoints to 200 by selecting from the strongest response to set up the same condition as in our approach. The inlier rate for SURF was computed by dividing the number of inliers by the number of extracted keypoints because FLANN always returned the nearest point for each keypoint.

In Figure 7, we showed the results of the inlier rates at each angle for all texture images. Harris outperformed others in most of the cases including rich texture and binary texture. This means that keypoint extraction with rotation invariance in Harris provided better performance than others in terms of stability. Especially, the keypoints on the handwriting were stably extracted as illustrated in Figure 7(b). Because the inlier rates are around 50%, RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] or other robust estimators can remove outliers when computing homography.

For the ISMAR 2011 pattern in Figure 1(c), the inlier rate of Harris was lower than the rate of Harris in other textures as illustrated in Figure 7(c). This is because there were a lot of similar corners extracted from squares in the lower part of this texture. When we limited the number of extracted keypoints, all corners could not always be extracted and some of them were unstably extracted. From Figure 7(e), it was obviously proved that a local texture based approach could not detect random dot markers because the local texture was exactly same. Therefore, an geometrical feature based approach is definitely required to detect various kinds of textures with only one method.

Thresholds in Keypoint Selection

In this section, we investigated the influence of two thresholds for inlier rates with Harris corner detector for Figure 1(a) and (b).

Minimum Distance between Keypoints

In this experiment, we fixed the threshold for the maximum number of extracted keypoints as 200. As illustrated in Figure 8, we tested the minimum distance between keypoints from 0 pixels to 30 pixels. From Figure 8(a) and (b), the result at 10 pixels commonly outperformed others. For other cases, the results were not stable. The influence of the threshold clearly appeared in Figure 8(b). When the threshold was 0 pixels, the inlier rates were around 0 at many angles because many keypoints densely appeared together. As a result, geometrical features for such keypoints were not discriminative. To avoid detecting dense keypoints, it is necessary to set up a threshold for the minimum distance between keypoints.

Maximum Number of Extracted Keypoints

In this experiment, we fixed the threshold for the minimum distance between keypoints as 10 pixels. As illustrated in Figure 9, we tested the maximum number of extracted keypoints from 50 to 300. In Figure 9(b), the line charts of 200 and 300 were overlapped because extracted keypoints in both cases were same. In Figure 9(a), the worst result appeared at 300. In contrast, the best result appeared at 300 in Figure 9(b). Similarly, fairly good result appeared at 50 in Figure 9(a) whereas the same threshold was worst in Figure 9(b).

From this result, it is hard to state that more or fewer number of keypoints is better or not. From various experiments, we confirmed that setting 200 on the threshold had provided better performance.

EVALUATIONS WITH MIKOLAJCZYK'S DATASET

In this section, we evaluated the influence of viewpoint changes for the detection with two datasets in Mikolajczyk framework [START_REF] Mikolajczyk | Scale & affine invariant interest point detectors[END_REF][START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF] as illustrated in Figure 10 and 11.

Overview

As in Section 5.3, we investigated the influence of two thresholds. In Figure 10(e) and Figure 11(e), the inlier rate with several thresholds for the maximum number of extracted keypoints was computed by fixing the minimum distance between keypoints as 10 pixels. In Figure 10(f) and Figure 11(f), the inlier rate with several thresholds for the minimum distance between keypoints was computed by fixing the maximum number of extracted keypoints as 400. In each image set in Figure 10 and 11, (a) was used as a reference with an image pyramid and compared with other three images from (b) to (d). We compared our approach using Harris corner detector with SURF.

Evaluation

Figure 10 included view angle changes in perspective views. In Figure 10(e) that illustrated the inlier rates with different thresholds for the minimum distance between keypoints, the result at 10 pixels was quite better than others for the pair (a,b). For other pairs, our approach did not achieve enough inlier rate for camera pose estimation. In Figure 10(f) that illustrated the inlier rates with different thresholds for the maximum number of extracted keypoints, there were few differences among the results of four thresholds. Compared with SURF, our approach with Harris corner detector was not invariant to viewpoint changes such that the inlier rates computed from our approach were not sufficient in the pair (a,c) while SURF still achieved around 20%. Figure 11 included zoom and rotation changes in a 3D outdoor scene. Compared with the previous experiment, the results for the pair (a,c) were better because the viewpoint change in this experiment was limited to zoom and rotation. For other pairs, the result was almost same as that in the previous experiment.

Discussion

In order to establish correct correspondences in our approach, we need to extract both same keypoints and same neighbor keypoints. As illustrated in Figure 11(e), the inlier rate decreased when the maximum number of extracted keypoints increased. Because different keypoints might be included in the neighbor keypoints in differ- ent views if there are too many keypoints, the number of extracted keypoints should be limited. Also, the matching result was sensitively influenced by the minimum distance between keypoints. From both experiments in Figure 10 and 11, it is hard to find the best threshold because the best threshold depended on texture patterns. Because the density of extracted keypoints varies depending on an image size and content, it is necessary to set up the threshold considering such elements.

Let us finally note that we only evaluated the detection part of our method in this section. Such detection process has only to be considered for the initialization and when the tracking process failed. It has also to be noted that, the complexity of the detection does not increase dramatically with the number of reference image in the database. Therefore, in a real application process, various reference images are considered. They can also be synthesized (as in [START_REF] Ozuysal | Fast keypoint recognition using random ferns[END_REF] to take into account affine or perspective transformation). Such a process greatly improves the detection process.

AUGMENTATION RESULTS

Figure 12 represented the results of the detection on different scales and the tracking under perspective views. We first stored the references from all texture images, and then captured one of the textures for the augmentation. For two thresholds in the keypoint selection, we set the minimum distance between keypoints as 10 pixels and the maximum number of extracted keypoints as 200. The first row in Figure 12 represented the result of keypoint extraction for the reference images. The resolution of the texture images and that of their pyramid are described in Table 1.

Table 1: Image resolution of the textures in Figure 1 and their pyramid (pixel). The selected levels for the pyramid varied according to textures. As illustrated in Figure 12, the movement of a camera included scale changes and perspective views. Object detection was done with difference scales. The robustness of random dot markers to scale changes was apparently higher than others even when one level on the image pyramid was generated because the dots were stably extracted from several viewpoints. For others, the range of camera movement during the tracking was almost same. Regarding computational costs, a frame rate was around 30 frames per second on a typical laptop (Intel i7 CPU 2.67GHz with 4GB RAM) for 640 × 480 pixels as described in Table 2. By using our approach, it is possible to detect and track rich texture, handwriting, ARToolKit markers and random dot markers.

CONCLUSION

We proposed an approach for detecting and tracking various types of textures using geometrical feature based keypoint matching. We combined traditional keypoint detectors with LLAH originally designed for retrieving text documents. Because the stability of keypoint extraction was required, we selected stable keypoints according to keypoint response and the distance between keypoints. We also built a non-uniform image pyramid by matching between neighboring scales to adaptively select the representative scales.

In the evaluations, we investigated the inlier rates in the detection for several image sets. Because the result was influenced by both the minimum distance between keypoints and the maximum number of extracted keypoints, we need to set up two thresholds considering an image size and content. To be invariant to viewpoint changes, one possible approach is to prepare synthetic images of various different viewpoints such as [START_REF] Ozuysal | Fast keypoint recognition using random ferns[END_REF] and compute descriptors on them because the number of registered images did not much influence the retrieval costs due to a hashing scheme as reported in [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF].

In the further works, we need to improve object tracking because traditional trackers are more robust to illumination and scale change [START_REF] Dame | Accurate real-time tracking using mutual information[END_REF]. One solution is to merge such trackers into our approach such that object detection is performed by our method and the tracker is selected depending on the detected object. The integration of a local texture descriptor with geometrical descriptors in LLAH will be also an interesting topic. This means that the stability of keypoint extraction with rotation invariance in Harris was more superior than others. For random dot markers, it was obviously proved that keypoint matching with local texture descriptors failed. To deal with various types of textures, a geometrical feature based approach should be integrated.

Figure 2 :

 2 Figure 2: Descriptors in LLAH. A descriptor is the set of the ratios of two triangles. For each keypoint, several descriptors are computed from neighbor points.

Figure 3 :

 3 Figure 3: Applying word region detector [21] to Figure 1(a). Binarization by adaptive thresholding was applied to (a) an input image. (b) Few keypoints were extracted from segmented regions because most of the extracted regions were connected.

Figure 4 :

 4 Figure 4: Keypoint selection. FAST was applied to Figure 3(a). (a) 427 keypoints were extracted in total. (b) 100 keypoints were extracted by setting the minimum distance as 10 pixels and the maximum number of keypoints as 100.

Figure 6 :

 6 Figure 6: Example of images. A camera equipped on an arm robot was used to control the rotaiton angles precisely. Grayscale images were captured at 5 degrees increments through 90 degrees. The resolution of the captured images was 640 × 480.

Figure 8 :

 8 Figure 8: Thresholds for the minimum distance between keypoints (pixel). (a) and (b) correspond to (a) and (b) in Figure1. We tested the threshold from 0 pixels to 30 pixels. In both cases, 10 pixels got fairly good results.

Figure 9 :

 9 Figure 9: Thresholds for the maximum number of extracted keypoints. (a) and (b) correspond to (a) and (b) in Figure1. We set the threshold from 50 to 300. In (b), the lines of 200 and 300 were overlapped. It is difficult to state that more or fewer number is better.

Figure 10 :

 10 Figure 10: View angle change. (e) The thresholds for the minimum distance between keypoints from 5 to 30 pixels were tested with three image pairs: (a,b), (a,c) and (a,d). (f) The thresholds for the maximum number of extracted keypoints from 200 to 500 were tested with the same image pairs as (e).

Figure 11 :

 11 Figure 11: Zoom and rotation change. The experimental condition of (e) and (f) was the same as that of Figure 10 (e) and (f).

Figure 7 :

 7 Figure 7: Comparison between keypoint detectors. (a)-(e) correspond to (a)-(e) in Figure 1. In most of the cases, Harris outperformed others.This means that the stability of keypoint extraction with rotation invariance in Harris was more superior than others. For random dot markers, it was obviously proved that keypoint matching with local texture descriptors failed. To deal with various types of textures, a geometrical feature based approach should be integrated.

Figure 12 :

 12 Figure 12: Augmentation results from detecting and tracking planar images. (a)-(e) correspond to (a)-(e) in Figure 1. Images at the first row are the results of keypoint extraction with Harris on the reference images. As a result of detection and tracking, we overlaid a paper ID and a pyramid level on the images. The range of camera movement for random dot markers was widest.

Table 2 :

 2 Average computational costs (msec).

	Texture Resolution	Pyramid
	(a)	640 × 480 640 × 480, 480 × 384, 360 × 288
	(b)	640 × 480	640 × 480, 448 × 336
	(c)	353 × 500 353 × 500, 282 × 400, 247 × 350
	(d)	400 × 400	400 × 400, 240 × 240
	(e)	400 × 400	400 × 400
	Extraction Description Detection Tracking
	15	10	5	2


F Chatelain

A Costard

O J J Michel

A BAYESIAN MARKED POINT PROCESS FOR OBJECT DETECTION. APPLICATION TO MUSE HYPERSPECTRAL DATA

Keywords: Point Processes, Hierarchical Bayesian Models, Hyperspectral Data, Galaxy Detection

Marked point processes have received a great attention in the recent years, for their ability to extract objects in large data sets as those obtained in biological studies or hyperspectral remote sensing frameworks. This paper focuses on an original Bayesian point process estimation for the detection of galaxies from the hyperspectral data 'cubes' provided by the Multi Unit Spectroscopic Explorer (MUSE) instrument. It is shown that this approach allows to obtain a synthetic representation of the detection problem and circumvent the computational complexity inherent to high dimensional pixel based approaches. The reversible jump Monte Carlo Markov Chain implemented to sample the parameters is detailed, and the results obtained on benchmark data mimicking the real instrument are provided.

INTRODUCTION, DATA DESCRIPTION

The overwhelming growth in size and complexity of experimental data from research fields such as biology, remote sensing and astrophysics requires to develop new approaches to warrant optimal scientific exploitation of the instrument. This paper focuses on the automated object detection task, formulated in a Bayesian marked point process detection framework. A marked point process is a stochastic process whose realizations are random configurations of objects. Thus an object is modeled as a point, associated with some marks that accounts for geometrical or spectral features. These processes yield a natural sparse representation for a configuration of a random number of objects in an image. The number of parameters actually depends on the effective number of objects in the current configuration, allowing one to obtain a synthetic representation of the problem. It appears to be a useful tool to circumvent the computational complexity due to high dimensional space problems inherent to pixel-wise approaches. These processes have received a great attention during the last several years for object extraction from biological [START_REF] Rue | Bayesian object recognition with Baddeley's delta loss[END_REF] or remotely sensed images (see e.g. [START_REF] Descamps | Automatic flamingo detection using a multiple birth and death process[END_REF][START_REF] Ortner | A marked point process of rectangles and segments for automatic analysis of digital elevation models[END_REF]). A known drawback of previously developed approaches resides in their high sensitivity to some hyper-parameters that controls the prior and data energy of the process. Consequently, these latter parameters are customary tuned by hand, to some data specific value. The Bayesian approach proposed in this paper overcomes this difficulty by introducing non-informative priors, possibly

The first author would like to thank Xavier Descombes and Josiane Zerubia for fruitful discussion about point processes during his post-doctoral fellowship at INRIA Sophia Antipolis. This work was supported by ANR DAHLIA, and P.P.F. ISSO, University of Nice Sophia Antipolis, France.

with a second level of hierarchy within the Bayesian model. It results in a so-called hierarchical Bayesian model. Finally, the posterior distribution is sampled using a Reversible Jump Markov chain Monte Carlo (RJMCMC) method. This hierarchical Bayesian model leads to a general and robust algorithm where the hyperparameters are estimated due to a full data-driven criterion [START_REF] Dobigeon | Bayesian orthogonal component analysis for sparse representation[END_REF]. This is, to our knowledge, the first time that a fully Bayesian marked point process is developed for object recognition. Moreover, for the purpose of galaxy detection in the MUSE data cube, the proposed model is designed to handle the large number of monochromatic images (data cube slices). The Multi Unit Spectroscopic Explorer (MUSE) project (see [START_REF]Official website of the MUSE project[END_REF]) aims to provide astronomers with a new generation of optical instrument, capable of simultaneously imaging the sky (in 2D) and measuring the optical spectra of the light received at a given position on the sky. MUSE is planned to be installed on the VLT and to be operational in 2012, and its performances are expected to allow observation of far galaxies up to 100 times fainter than those presently detectable. MUSE will deliver a 3D 'data-cube' made of a stack of images recorded at 3578 different wavelengths over the range 465-930 nm. Each 'monochromatic' image represents a field of view of 60X60 arcsec, recorded with a spatial sampling of 0.2 arcsec 0.2 arcsec. Each record results in a data cube of size 1570 MB encoding 3578 images of 300X300 pixels, possibly containing thousands of objects (galaxies) existing over different subsets of wavelengths! In the literature [START_REF] Simard | The deep groth strip survey. ii. hubble space telescope structural parameters of galaxies in the groth strip[END_REF][START_REF] Peng | Detailed Structural Decomposition of Galaxy Images[END_REF], the galaxy morphology is classically assumed to result from elliptical components. Following this assumption, in this paper, a galaxy is approximated by an elliptic object. The marks correspond to the ellipse parameters and to the intensity vector of the galaxy. Galaxy detection is then performed jointly on the different slices of the hyperspectral cube. Throughout this study, we analyze simulation data mimicking the expected hyperspectral record (in terms of SNR, density of objects, spectral content,...), as provided by CRAL [START_REF]Official website of the CRAL laboratory[END_REF] within the ANR Dahlia [START_REF]Official website of the Dahlia project[END_REF] collaborative project. This paper is organized as follows. The Bayesian model is described in section 2. The RJMCMC sampler is derived in section 3. Simulations conducted on the MUSE cube are reported in section 4. Conclusions are drawn in section 5.

BAYESIAN MODEL

Let y be a M × 1 vector corresponding to a vectorized image (at a given wavelength λ) counting M pixels, while u = {u1, u2, . . .} denotes a configuration of objects. Finally, n(u) denotes the number of objects ui in the configuration u.

Monochromatic Observation model

y = s + 1m + n,
where m > 0 is the mean of the astrophysical background intensity, 1 = (1 . . . 1) T is the M × 1 matrix with unit elements, n is a M × 1 centered white noise Gaussian vector with component variance σ 2 , and s is a M × 1 vector that models the device response to a galaxy configuration u in the observed scene. The signal s is expressed as:

s = n(u) X i=1 wixi,
where xi stands for the the response of imaging device to an ellipse ui with unitary intensity ; wi is the intensity associated with ui. An equivalent matrix formulation yields:

s = X w, where X = ˆx1 . . . x n(u) ˜∈ R M ×n(u) and w = (w1, . . . , w n(u) ) T ∈ R n(u) .

Hyperspectral Likelihood

From the observation and noise models above, under the assumption that different spectral bands or slices yield independent observations, the hyperspectral likelihood is obtained as the product of the monochromatic (at λ) likelihoods

f (y λ |u, m λ , σ 2 λ ) = " 1 2πσ 2 λ « M 2 exp " - Z T λ Z λ 2σ 2 λ « , (1)
where Z λ = y λ -1m λ -X λ w λ , and all parameters but u depend on λ. This stresses on the fact that a configuration is shared by all slices (wavelengths) in a given data cube. In the remainder of the paper, λ will be omitted for sake of simplicity. Although the independence of the observations from different slices may seem oversimplified, this holds for sufficiently separated (in the wavelength domain) slices. Note that the model can be extented to possible spectral correlations due to the spectral point spread function. However this point is not tackled in this paper.

Parameter and Hyperparameter Priors

A noninformative improper prior is chosen for the pair of parameters (m, σ 2 ):

p(m, σ 2 ) = 1 σ 2 1 (0,+∞) 2 (m, σ 2 ).
A Gaussian prior is introduced for the intensity vector:

w|u, σ 2 , η 2 ∼ N " 0, η 2 σ 2 (X T X ) -1 " ,
Note that all these priors satisfy a principle of invariance. Any affine transformation of the measurements y, or of the signal basis X , will transform the posterior distribution, and thus our inferences, in the same way. Moreover, the hyperparameter η 2 represents the signalto-noise ratio (SNR) of the observed scene since it is straightforward to show that

η 2 = E[s T s] E[n T n] .
Finally, a Bayesian hierarchical structure is proposed, by introducing a hyperprior distribution for the hyperparameter η 2 . This hyperparameter is modeled as a conjugate inverse-Gamma distribution IG(α0, α1/2):

p(η 2 ) ∝ " 1 η 2 « α 0 +1 e - " α 1 2η 2 « .
The parameters α0 and α1 are chosen sufficiently small to obtain a vague prior (basically, α0 = α1 = 10 -3 ).

Posterior distribution conditionally on a galaxy configuration u

The resulting posterior distribution, conditionally on a configuration u, is obtained as:

p(w, m, σ 2 , η 2 |u, y) ∝ " 1 2πσ 2 « M +n(u) 2 +1 1 η 2 n(u) 2 × exp - Z T Z + 1 η 2 w T X T X w 2σ 2 ! × exp(-α 1 2η 2 ) (η 2 ) α 0 +1 1 (0,+∞) 2 (m, σ 2 ) (2)
Based on (2), one can see that the conditional posterior distribution of the intensity vector w given m, σ 2 , η 2 , u, y is Gaussian with mean and covariance matrix respectively:

µ = " 1 + 1 η 2 « -1 (X T X ) -1 h X T (y -1m) i , Σ = σ 2 η 2 1 + η 2 " X T X " -1 .
It allows one to integrate out the parameter vector w to obtain the following marginalized posterior distribution:

p(m, σ 2 , η 2 |y, u) ∝ " 1 σ 2 « M 2 +1 " 1 1 + η 2 « n(u) 2 × e - (y-1m) T " I- " η 2 1+η 2 « X(X T X) -1 X T « (y-1m) 2σ 2 × exp(-α 1 2η 2 ) (η 2 ) α 0 +1 1 (0,+∞) 2 (m, σ 2 ).
(3)

Priors on the configuration

The galaxy configuration u = {u1, u2, . . .} is modeled as a marked point process (see [START_REF] Stoyan | Stochastic Geometry and Its Applications[END_REF] for more details about point processes). Each marked point ui corresponds to an ellipse ui = (pi, ai, bi, ωi), where pi is the center, ai, bi denotes respectively the first and second axis values and ωi is the orientation of the first axis. This process is defined by its density with respect to the measure µ(•) of a unitary Poisson process defined on W × K, where W ⊂ R 2 is the coordinate space of the observed scene and K = [rmin, rmax]×[rmin, rmax]× [0, π[ is the mark space. In order to regularize the solution and to avoid multiple detections, a hard core penalization is introduced to prevent overlapping. Let r(ui, uj) = max

P s∈u i ∩u j xi,s P s∈u i xi,s , P s∈u i ∩u j xi,s P s∈u j xi,s ! ∈ [0, 1]
be the overlapping ratio between the responses of two objects ui and uj, where xi,s stands for the object response xi evaluated at location s. It yields the following hard core density

h(u) = ( 0 if it exists i = j such that r(ui, uj) > t, 1 otherwise,
where the threshold t is set to the deterministic value t = 1/2. Finally, the number of galaxy n(u) is governed a priori by a Poisson distribution with mean β. A second level of hierarchy is introduced with the choice of a Jeffreys noninformative hyperprior on this hyperparameter: p(β) = 1/ √ β. The resulting prior on the configuration is obtained as:

p(u, β) ∝ β n(u)-1/2 e -β h(u)µ(u).
Integrating out β, it yields the following marginalized prior:

p(u) ∝ Γ (n(u) + 1/2) h(u)µ(u), (4)
Γ(a) = R +∞ 0 t a-1 e -t dt being the classical Gamma function.

Posterior distribution

The joint posterior distribution on both the configuration u and the parameter vector θ = (m, σ 2 , η) expresses now as:

p(u, θ|y) ∝ p(θ|u, y)p(u) (5)
where p(θ|u, y) and p(u) are defined respectively in ( 3) and (4).

RJMCMC SAMPLER

Several kinds of movements are considered in the RJMCMC dynamics [START_REF] Peter | Reversible Jump Markov chain Monte Carlo computation and Bayesian model determination[END_REF]. Simple moves just update some model parameters, or object features (location, marks). More complex moves allow for dimensional changes in the model, such that the birth of the death of an object in the current configuration. The different moves defined below are finally randomly selected in the RJMCMC dynamic.

Sampling the parameters

One can deduce from (3) the conditional posterior distributions for each parameter given the other ones. These posterior distributions can be used as proposals, leading to an acceptance ratio equal to 1. These moves reduce to classical Gibbs moves. Note that the different moves to update the parameters are performed sequentially in the RJMCMC dynamic. Let ν = M -1, and

W = I - " η 2 1 + η 2 « X (X T X ) -1 X T , δ 2 = (1 T W 1) -1 , m = δ 2 1 T W y, s 2 = ν -1 δ 2 h y T W y -δ 2 (1 T W y) 2 i . (6)
Based on ( 3) and ( 6), straightforward computations lead to the following Inverse-Gamma density for the variance parameter:

σ 2 |(m, λ 2 , y, u) ∼ IG `M 2 , 1 2δ 2 (νs 2 + (m -m) 2 )
´. By integrating out σ 2 , the marginal posterior for m becomes:

p(m|λ 2 , y, u) ∝ ν + " m - m s « 2 ! -ν+1 2 1 (0,+∞) (m).
Thus the marginal posterior for m is a positive truncated Student distribution with degree of freedom ν, location parameter m, and scale parameter s: m|(λ 2 , y, u) ∼ T + (ν, m, s).

Finally, sampling from the bivariate posterior for (m, σ 2 ), given λ 2 , y and u, is performed in two-steps:

1. draw m|(λ 2 , y, u) ∼ T + (ν, m, s),

2. draw σ 2 |(m, λ 2 , y, u) ∼ IG( M 2 , 1 2δ 2 [νs 2 + (m -m) 2 ]).

Sampling the SNR parameter η 2

From (3), the posterior of η 2 is

p(η 2 |m, σ 2 , y, u) ∝ " 1 1 + η 2 « n(u) 2 e » - " 1 1+η 2 « β 2σ 2 - e - α 1 2η 2 (η 2 ) α 0 +1 ,
where β = (y -1m) T X (X T X )X T (y -1m). This distribution is not standard and it is not possible to sample according to this distribution directly. However, the generation of η 2 |(m, σ 2 , y, u) can be achieved using a standard Metropolis-Hasting step, by introducing an adequate proposal distribution. It leads to a "so-called" Metropolis-within-Gibbs sampler.

Birth and Death moves

For a given configuration u, pB(u) denotes the probability to select the birth move, while pD(u) = 1 -pB(u) is the probability to choose the reversible move, i.e. the death move (basically, pB(u) = pD(u) = 1/2).

For a birth move, a new object v is drawn independently from the configuration u, according to the reference Poisson process. In the death case, the object ui ∈ u that is proposed to be removed is uniformly selected, thus with probability pS(ui|u) = 1/n(u).

Finally, in the birth case, the proposed configuration is v = u ∪ {v} and the following Metropolis-Hastings-Green ratio is obtained:

r(u, v) = pD(v) pB(u)
p(v, θ|y) p(u, θ|y) pS(v|v).

In the death case, the proposed configuration is v = u\{ui} and the Metropolis-Hastings-Green ratio is:

r(u, v) = pB(v) pD(u) p(v, θ|y) p(u, θ|y) 1 pS(ui|u)
.

Finally, each one of this moves is accepted with probability α = min (1, r(u, v)).

Updating an object of the configuration

This move can be viewed as the composition of a death and a birth move. In fact, an object ui ∈ u is uniformly selected with probability pS(ui|u) = 1/n(u). A new object v is drawn according to the reference Poisson process. We propose to replace the object ui by the new one v leading to the new configuration v = u\{ui} ∪ {v}.

The following Metropolis-Hasting ratio is obtained:

r(u, v) = pS(v|v) pS(ui|u) p(v, θ|y) p(u, θ|y) ,
and the acceptance rate is α = min (1, r(u, v)).

RESULTS

The algorithm was applied to a partially integrated (over λ) MUSE data cube: instead of considering all the 3578 wavelengths, 'thick' slices integrating 8 consecutive wavelengths are considered. This lead to a new data set of size 300 × 300 × 448, where images at some average λ are assumed independent. The intensity shape xi associated with the ellipsis ui is modeled as a bivariate Gaussian density f2D for which ui is a α iso-probability contour defined by R (x,y)∈u i f2D(x, y)dxdy = 1α. Probabilities to select the parameter update PParameter (see section 3.1), the birth/death PB/D (see 3.2), the object update move PObject (see 3.3) are set to arbitrary values. Note that a fusion/split move (not discussed in this paper) was added for the computation whose results are shown below. The number of MCMC iterations that has been done is 1.1 × 10 7 . It takes about 250 minutes on a 2.40GHz (single core) CPU. Figure 1 shows the obtained parameters vs the wavelengths. These parameters are estimated by taking the MMSE estimate over the last 50000 samples provided by the MCMC. The problem which appears around λ = 850nm was already noticed by the astronomers who prepared the data. It is noteworthy that the shape of the variance receives some physical interpretation, as it matches the expected behavior of the spectrum when water is present in the atmosphere. This was not given as a prior. A projection (integrated over λ) of the detected galaxy configuration is shown on figure 2.

CONCLUSIONS

A fully Bayesian marked point process has been studied to automatically extract the galaxies in the MUSE data cube. Future works include the definition of new moves in the RJMCMC dynamic in order to improve the mixing properties of the Markov Chain. The Fig. 2. Projection of the MUSE data cube (in negative grayscale colors) and contours (in red) of the 384 detected galaxies extension to more complex intensity shape models, taking into account the point spread function of the imaging device must be investigated. Some improvements are also necessary in order to account for very large dynamical variations of the intensity detected for different classes of astrophysical objects.

3. 1 . 1 .

 11 Sampling the background parameters (m, σ 2 )

Fig. 1 .

 1 Fig. 1. Estimated background mean m (a), logarithm of the estimated background variance σ 2 (b), estimated SNR η (c), as functions of the central wavelength (in nm) for each slice of the data cube. (d): log-posterior density at the current parameter values vs the MCMC iteration.


Rabie Saidi

Sabeur Aridhi

Mondher Maddouri

Engelbert Mephu Nguifo

Novel metrics for feature extraction stability in protein sequence classication

Keywords: Motif / feature extraction, classification of protein sequences, motif stability, sensibility, stable motif interest

Feature extraction is an unavoidable task, especially in the critical step of preprocessing biological sequences. This step consists for example in transforming the biological sequences into vectors of motifs where each motif is a subsequence that can be seen as a property (or attribute) characterizing the sequence. Hence, we obtain an objectproperty table where objects are sequences and properties are motif extracted from sequences. This output can be used to apply standard machine learning tools to perform data mining tasks such as classification. Several previous works have described feature extraction methods for bio-sequence classification, but none of them discussed the robustness of these methods when perturbing the input data. In this work, we introduce the notion of stability of the generated motifs in order to study the robustness of motif extraction methods. We express this robustness in terms of the ability of the method to reveal any change occurring in the input data and also its ability to target the interesting motifs. We use these criteria to evaluate and experimentally compare four existing extraction methods for biological sequences.

Introduction.

Classification of biological sequences is a fundamental task in bioinformatics [START_REF] Bhaskar | Machine learning in bioinformatics: A brief survey and recommendations for practitioners[END_REF]. In fact, biologists are continuously interested in identifying the family to which a novel sequenced protein belongs [START_REF] Bernardes | Structural descriptor database: a new tool for sequence based functional site prediction[END_REF]. This makes it possible to study the evolution of this protein and to discover its biological functions. Generally, biologists use alignment to classify new biological sequences into already known families/classes by searching similarity and homology among sequences. However, this approach is often inefficient. For instance, in metagenomics, one of the major problems encountered during the application of such approach is that between 25% and 65% of the sequences have no homologous (orphan sequences) in the databases, making these sequences unusable [START_REF] Debroas | Metagenomic approach studying the taxonomic and functional diversity of the bacterial community in a mesotrophic lake (lac du bourget -france)[END_REF].

Machine learning techniques are one way to deal with such a problem. But, with the format of biological sequences where characteristics are encoded into the sequence itself, it is not possible to use the wellknown classification algorithms which have proved to be very efficient in real data mining tasks [START_REF] Maddouri | Encoding of primary structures of biological macromolecules within a data mining perspective[END_REF] with data described in a relational data format. Consequently, a preprocessing step is necessary in order to parse the biological data into a new format suitable for different data mining tools [START_REF] Al-Ani | A dependency-based search strategy for feature selection[END_REF].

For protein sequences, motif extraction represents a widely used solution to perform this preprocessing phase. The protein sequences are chains of amino acids residues where each residue is represented by a character within an alphabet of size 20. Discovering motifs from these sequences is a delicate task aiming to find substrings or words that can serve as descriptors. These descriptors form the feature space that allows transforming the biological sequences into vectors of values, thus facilitating the processing of such data by machine learning and data mining tools. This preprocessing phase is the key step towards a reliable process of knowledge discovery because it directly affects the quality of obtained results [START_REF] Saidi | Comparing graph-based representations of protein for mining purposes[END_REF]. Each protein sequence is described by a set of motifs to achieve a vector of values where the values depend on the nature of the description function that binds the sequence and the motif such as:

-Presence / absence of the motif in the sequence, -Number of occurrences of the motif in the sequence, -First position of the motif in the sequence... These motifs, which will serve as descriptors, are extracted from biological sequences according to predefined parameters such as frequency, length, composition. However, designing and developing a suitable method for finding motifs that may reduce any loss of information due to the format change and help solve problems of data mining, remains a nontrivial task [START_REF] Xu | Nonmonotonic feature selection[END_REF] [START_REF] Zhang | EXMOTIF: efficient structured motif extraction[END_REF].

Several motif extraction methods have been proposed [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF]. Meanwhile, various studies have made assessments and comparisons between these methods and have tried to study the impact of one method or another on the quality of the learning task to be performed (classification, prediction, shape recognition ...). So, the best methods are those that allow having the best values of quality metrics such as accuracy rate in the case of supervised classification.

In this paper we introduce the concept of stability to compare motif extraction methods. We call stability of a motif extraction method from a dataset, the nonvariability in its set of motifs, when applying a technique of variation on the input data. The robustness of a method is the coupling of the non-stability and the ability to retain or improve the quality of the associated data mining task. In our case we will use the supervised classification accuracy as quality measure.

Concrete motivations behind the above-mentioned stability can be found within distributed systems and grid computing environments that are mining huge amount of data. In such environments, the variation of data is a common fact. This variation can be due to various events such as failed transfer of data portions, loss of communication between nodes of the distributed system, data updating... Another motivating application is information retrieval from biological databases (such as GenBank [5], EMBL [START_REF] Stoesser | The embl nucleotide sequence database[END_REF], UniProt [START_REF] Bairoch | The universal protein resource (uniprot)[END_REF]). The problem here lies in the fact that every database has its own terminology and procedures which sometimes yield related but not identical data [START_REF] Zhao | Identifying biologically relevant genes via multiple heterogeneous data sources[END_REF]. Since the retrieved data are the main materials of several delicate processes in both industry and research like disease management and drug development, it is crucial for database researcher, bioscience user and bioinformatics practitioner to be aware of any change in the preparation data samples [START_REF] Topaloglou | Biological data management: research, practice and opportunities[END_REF]. In addition, with the exploding amounts of data submitted to the biological databases, there is an increasing possibility of finding erroneous data. In such conditions, it is important to make sure that the motif extraction methods, which are the start point of any mining process, are robust enough to detect even slight variations in input data like does any good sensor when describing its context environment.

The goal of this study is to propose new metrics to measure the robustness of motif extraction methods in terms of their ability to reveal any change occurring in the input data and also its ability to target the interesting motifs. We experiment these measures on protein data. This paper is organized as follows. In the next section, we present an overview on some works that dealt with the concept of stability and present the motivation behind our work. In section 3 we define the various terms used in this paper. Section 4 describes our experimental protocol then we discuss the obtained results in section 4. A conclusion and some prospects are presented in section 5.

Background.

The topic of stability with respect to motif extraction methods has not been studied in the literature. However, this aspect was slightly studied in a very close field to motif extraction which is the feature selection [20] [35] [10] [START_REF] Kalousis | Stability of feature selection algorithms: a study on highdimensional spaces[END_REF] [28] [START_REF] Yu | Stable feature selection via dense feature groups[END_REF].

In [START_REF] Pavel | Improving stability of feature selection methods[END_REF], authors propose a measure which assesses the stability of feature selection algorithms with respect to random perturbation in data. In this work, the stability of feature selection algorithms can be assessed through the properties of the generated probability distributions of the selected feature subsets. The interest is, of course, in feature selection algorithms that produce probability distributions far from the uniform and close to the peak one. Given a set of features, all possible feature combinations of size k are considered achieving n feature subsets. The frequencies F of selected feature subsets are recorded during data perturbation in a histogram. For a size k, the stability S k is measured based on the Shannon entropy:

S k = - n ∑ i=1 F i log F i . (2.1)
In [START_REF] Yvan | Robust feature selection using ensemble feature selection techniques[END_REF], authors perform an instance sub-sampling to simulate data perturbation. Feature selection is performed on each of the n sub-samples, and a measure of stability is calculated. The output f of the feature selection applied on each sub-sample is compared to the outputs of the other sub-samples using Pearson correlation coefficient, the Spearman rank correlation coefficient and the Jaccard index as similarity measure noted S. The more similar all outputs are, the higher the stability measure will be. The overall stability can then be defined as the average over all pairwise similarity comparisons:

S total = 2 × ∑ n-1 i=1 ∑ n j=i+1 S(f i , f j ) n(n -1) . (2.2)
In [START_REF] Dunne | Solutions to Instability Problems with Sequential Wrapper-Based Approaches To Feature Selection[END_REF], different sub-samples (or training sets) are created using the same generating distribution. Stability quantifies how different training sets affect the feature selection output. Authors take into account three types of representations for feature subsets. In the first type a weight or score is assigned to each feature indicating its importance. The second type of representation, ranks are assigned to features. The third type consists only of sets of features in which no weighting or ranking is considered. Measuring stability requires a similarity measure for feature representations. This obviously depends on the representation used by a given feature selection algorithm to describe its feature subset. The authors used three similarity measures: the Pearson's correlation coefficient, the Spearman rank correlation coefficient and the Tanimoto distance.

Robustness of motif extraction methods.

3.1 Motivations. The application of the abovepresented measures of stability is not convenient in our case (motif extraction). This comes from the nature of input data used by feature selection methods [START_REF] Ma | Penalized feature selection and classification in bioinformatics[END_REF] [21] [16] [25].

In fact, these methods use an original set of features (motifs) as input and try to merely select a subset of relevant features. The perturbation of data is applied to the original set of features. In the case of motif extraction, the input data are still in rough state and the data perturbation step is applied directly to row data (before motif extraction step)(figure 1).

There are different kinds of data perturbation (introducing noise in data) [START_REF] Sloan | Four types of noise in data for PAC learning[END_REF] [START_REF] Sloan | Types of Noise in Data for Concept Learning (Extended Abstract)[END_REF], especially in the context of biological data where it is possible to consider also deletion, mutation and insertion of nucleotides or amino acids into the sequences. In what follows, we will consider only one kind of noise consisting of removing a subset of sequences from the initial set. This case is the one that often happens in the context of distributed environment as described in section 1.

In our work, the motivation behind exploring the motif extraction method stability is to provide evidence that even slight changes in the data must also be followed by changes in the output results (extracted motifs). These changes must concern the motifs that are no longer significant for the perturbed input data; which means that the motifs that have been conserved must prove to be interesting i.e. help with better classification. Since the set of features are not known a priori we can not apply the measures quoted in the feature selection related works. For our purposes let be the two following assumptions: Assumption 1. We suppose that a motif extraction method allows a reliable description of input data if any variation within these data affects the set of the generated motifs. That is to say that it reveals any change occurring in the input data.

Assumption 2. After changes in the set of generated motifs, the motifs that are conserved, are interesting i.e., help to better classify unknown sequences.

In the next subsection we define and describe the terms we use to formally express our assumptions and to evaluate the robustness of motif extraction methods.

Terminology.

Based on assumption 1, we introduce the concept of sensibility . This concept reflects the ability to produce a different set of motifs i.e., a different data description, whenever we make a variation within the input data. The sensitivity criterion can be studied by means of the conserved motifs called stable motifs. It is also interesting to test the assumption 2, that is to say the quality of the stable motifs, by assessing their benefits in an artificial learning task.

Below we formally define the terms used in this paper. Consider the following: Thus, the sensibility S of a method is complementary to its rate of stable motifs. It may be noted: the original dataset D. However, it is noteworthy that we can not judge that conservation unless the method is already sensible. Indeed, an insensible method tends to generate the same motifs even after perturbations in the input data indicating that its extraction approach is rigid and does not adopt a concept of "choice". This conservation C can be measured by:

-A dataset D, divided into n subsets D 1 , D 2 ,.., D n . -A motif
S = 1 -RSM . (3.5) Definition 3.

(Conservation) A motif extraction method M conserves the quality metric value of a datamining task T if the use of the set of stable motifs SSM in T preserves the quality metric values for this task as when we use the set of motifs SM generated from

C = 1 -|M tr T (SM ) -M tr T (SSM )| . ( 3
I = 2 × S × C S + C . (3.7)
This measure is inspired from the F1-Score which is a statistical measure of a test's accuracy that combines Precision and Recall. The F1-score can be interpreted as a weighted average of the precision and recall, where an F1-score reaches its best value at 1 and worst score at 0. In our case, we combine conservation and sensibility to quantify the interest of stable motifs. Using τ such that τ = 65%, the motifs m1 and m6 are considered stable since they appear in more than 65% of the motifs subsets. We can easily calculate the rate of stable motifs RSM = 0.25, which is two over the set of eight motifs. We consider that m9 and m10 are noise, and thus are not relevant for the classification task.

The sensibility S of M is equal to 0.75. In this case, the set of stable motifs SSM 1 is equal to {m1, m6}.

Using τ > 66%, only the motif m1 are considered stable since it appears in more than τ % of the motifs subsets. We can easily calculate the rate of stable motifs RSM as equal to 0.125. The sensibility S of M is equal to 0.875, and SSM 2 = {m1}.

Suppose we use sets of motifs SM and SSM 1 as variables space to measure the accuracy rate (M tr T ) of the supervised classification task T . Let consider the following obtained values with M tr T : M tr(SM ) = 0.85 and M tr(SSM ) = 0.80

The set of stable motifs SSM 1 enables a conservation of the quality metric value C = 0.95 Finally, we can measure the interest of stable motifs by I = 0.83.

Experiments.

In this section, we describe an experimental study conducted on four motif selection methods quoted in [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF]. Calculations were run on a duo CPU 1.46GHz PC with 2GB memory, operating on Linux. The following is a presentation of the input datasets and the used tools.

Experimental data.

We used four datasets containing 1327 protein sequences extracted from Swiss-Prot [START_REF] Bairoch | The SWISS-PROT protein sequence database and its supplement TrEMBL in 2000[END_REF] and described in table 1. These datasets differ from one another in terms of size, number of class, class distribution, complexity and sequence identity percentage (IdP ). The change in the nature of the datasets allows us to avoid specific outcomes to data and to have better interpretations. [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF], i.e., n-grams NG [START_REF] Leslie | The spectrum kernel: a string kernel for SVM protein classification[END_REF], active motifs AM [START_REF] Wang | Discovering Active Motifs in Sets of Related Protein Sequences and Using Them for Classification[END_REF], discriminative descriptors DD [START_REF] Maddouri | Encoding of primary structures of biological macromolecules within a data mining perspective[END_REF] and discriminative descriptors with substitution matrix DDSM [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF]. In our experiments we use the same default settings as in [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF]. NG is a simple method that generate the distinct words of fixed length by sliding a window of N characters on the whole sequences i.e., at every character i the word [i, i + N ] is extracted.

The AM method allows generating the commonly occurring motifs whose lengths are longer than a specified value in a set of biological sequences. The activity of a motif is the number of matching sequences given an allowed number of mutations [START_REF] Wang | Discovering Active Motifs in Sets of Related Protein Sequences and Using Them for Classification[END_REF]. The motif generation is based on the construction of a generalized suffix tree (GST) which is an extension of the suffix tree [START_REF]Combinatorial Pattern Matching, Third Annual Symposium, CPM 92[END_REF] and is dedicated to represent a set of n sequences indexed each one by i = 1..n.

The DD method allows building sub-strings that can discriminate a family of proteins from other ones [START_REF] Maddouri | Encoding of primary structures of biological macromolecules within a data mining perspective[END_REF]. This method is based on an adaptation of the Karp, Miller and Rosenberg (KMR) algorithm [START_REF] Karp | Rapid Identification of Repeated Patterns in Strings, Trees and Arrays[END_REF]. This algorithm identifies the repeats in character strings. The extracted repeats are then filtered in order to keep only the discriminative and minimal ones. A substring is considered to be discriminative between the family F and the other families if it appears in F significantly more than in the other families.

The DDSM method is an extension of the DD method that takes into account the phenomenon of mutation within proteins. It uses the substitution matrices [START_REF] Dayhoff | A model of evolutionary change in proteins[END_REF] [START_REF] Henikoff | Amino acid substitution matrices from protein blocks[END_REF] to achieve a sort of clustering of motifs and keep, for each cluster, the most mutable motif. It is therefore a more concise representation than DD since it reduces significantly the number of generated motifs [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF].

Comparisons made in [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF] between these methods revealed that DDSM performs the best to help in problems of protein sequences classification even in difficult cases where other methods fail to produce reliable descriptors for an accurate classification. In this work, we try to find a relationship between this performance and the concepts introduced in section 3.

Experimental process.

In our experiments, we perturb each input dataset in a systematic way and we observe the impact of this perturbation on the set of generated motifs. To do this, we use the 10-crossvalidation (10CV) and leave-one-out techniques (LOO) [START_REF] Han | Data Mining: Concepts and Techniques, Second Edition[END_REF]. Therefore, the variation of a dataset containing n sequences consists in removing a partition (one tenth with 10-cross-validation and a single sequence with leave-one-out) from the dataset and the rest is used to generate a set of motifs. This is done several times (ten times with 10-cross-validation and n times with leaveone-out). At each iteration, the number of occurrences of generated motifs is updated. Otherwise, a sequences-Figure 2: Experimental process based perturbation can be applied here, As already defined in Section 2, the technique we adopt to measure the sensibility of motif extraction methods from protein sequences is based on the rate of stable motifs. Whereas the sensibility is related to the amount of stable motifs, the interest of stable motifs is related to their quality. In other words, if these motifs are generated by the extraction method to appear often enough then they should be "interesting". We measure the interest in our experiments by their usefulness in a supervised classification task. Once the stable motifs are generated, they are used to convert protein sequences into binary vectors where the value '1' denotes the presence of motif in the sequence and '0' its absence, all these binary vectors compose what is called a learning context.

Thus the classification of proteins in this new format is now possible with different classifiers. To do this, we use the support vector machine classifier SVM of WEKA workbench [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF]. The effect of this choice should be insignificant in the process of measuring the robustness of motif extraction methods. However we put our focus on a well-known and efficient classifier for our experiments. In addition SVM classifier has shown its efficiency in a previous study [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF].

The classification is performed based on 10-crossvalidation (10CV) and leave-one-out (LOO) techniques Hence, our experiments are conducted using the following four combinations for data variation and classification: (LOO; LOO), (LOO; 10CV), (10CV; LOO) and (10CV; 10CV).

Results and discussion.

We show in table 2 the classification results of our datasets using the motif extraction methods quoted in section 4.2.

The classification is performed without making any perturbation on our datasets using the SVM classifier of WEKA [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF] based on 10-cross-validation (10CV) and leave-one-out (LOO). Comparing these results with those obtained using the stable motifs allow us to better evaluate the studied methods and test assumptions 1 and 2.

The experimental results are presented in tables 3 and 4. Table 3 contains the results obtained with a LOO based variation and table 4 with 10CV based variation. For each dataset and for each value of τ , we note the rate of stable motifs and their corresponding accuracy if we use these motifs to classify protein sequences of that dataset based on 10-cross-validation and leave-one-out tests. As shown in figure 3 and4, we can notice that the classification test technique i.e., 10CV or LOO does not affect the obtained results (the classification accuracy rates are almost the same). Using results from tables 2, 3 and 4, we draw the interest of stable motifs histogram corresponding to dataset (figure 5 and6). tions in data. Indeed its rate of stable motifs is often equal or very close to 100%. Therefore, the variation of input data has no bearing on the generated motifs.

In other words, we often obtain the same motifs even in the presence of variations in input data. In this case, we can not evoke the interest of stable motifs (see figures 5 and 6).

The AM method follows almost the same fluctuating behavior for all datasets (except for DS4 where we could not conduct our experiments due to lack of memory). In fact, below τ = 0.7, AM is insensible (RSM is equal or close to 100%). Beyond this value, AM becomes sensible. This sensibility varies depending on dataset and the variation technique (10CV or LOO). It is very significant for DS1, average for DS2 and slight for DS3. For example in table 3, for τ = 0.7, the rate of stable motifs are 32.5, 83.6 and 98.3% respectively for DS1, DS2 and DS3. Similarly, the interest of stable AM motifs is very fluctuating and varies as well depending on the dataset (see figures 5 and 6). This method is sometimes completive to DD and DDSM. But, we note that it is greedy in memory and can not handle large datasets as it is the case with the dataset DS4 (see tables 3 and4).

The approach adopted by the DD method offers it a sensible nature. In fact, according to this method, each motif must satisfy the conditions of discrimination and minimality (see section 4.2). Therefore, it is likely that a disruption of input yields not meeting these conditions and thus the elimination of some existing motifs and/or addition of new ones. At the same time, this method generates sets of interesting stable motifs with all the data samples and different values of τ . Indeed, it generally allows better interest rates than NG and AM (see figures 5 and6).

The DDSM method is an extension of DD, which adopts a competitive approach among the motifs to generate. Indeed, to be chosen, a motif must be the most mutable among other ones of equal size. This constraint remarkably increases the sensibility of the method vis-a-vis the changes in the input data. This can be noticed by the decreasing rates of stable motifs compared to the DD method. In addition, this high sensibility is always accompanied by a set of very interesting stable motifs manifested by generally allowing the highest interest rates. However we note that for τ = 1, DDSM does not often have the best rates of interest especially with 10CV based variation (we recall that this value of τ means that the stable motifs are those that appear in all variations of data). This is because that the substitution, which is a fundamental criterion in the process of DDSM, is not taken into account in the construction of the set of stable motifs. Hence, similar forms of a given motif may be ignored. But by relaxing the condition of τ = 1 and moving to smaller values of τ we see that the interest rates get improved considerably. This method reveals both the property of sensibility and interest of its stable motifs (see figures 5 and 6), which allows it to redescribe well the input data, which is in accordance with results quoted in [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF] showing the efficiency of this method for feature extraction in protein sequences.

Conclusion.

In this paper, we introduced the notions of stability and sensibility as new criteria to compare motif extraction methods from biological sequences. The sensibility of a method is its ability to produce a different set of motifs, so a different description, whenever a perturbation is made in the dataset. This criterion must be accompanied by a set of interesting stable motifs. This concept of interest arises when a method eliminates certain motif and conserves others following a change in the input data and that the conserved motifs are useful if used in a data mining task.

The experimental study shows that the DDSM method is more sensible compared to the other methods. This sensibility is usually accompanied by sets of stable interesting motifs. This confirms the results found by [START_REF] Saidi | Protein sequences classification by means of feature extraction with substitution matrices[END_REF] that show the contribution of the DDSM method in supervised classification tasks.

As future works, the proposed feature extraction approach is announced to be generic since it can be coupled with any data mining task T . Hence, we plan to apply it to other types of tasks such as clustering [17] [37]. We will also explore its extension to text mining supervised classification tasks [START_REF] Sebastiani | Machine learning in automated text categorization[END_REF].

Figure 1 :

 1 Figure 1: Data perturbation in feature selection and motif extraction

3. 3

 3 Illustrative example. Considering a dataset D in a supervised classification task T . The data pertur-bation of D generates three subsets D 1 , D 2 and D 3 . The application of a motif extraction method M to D on one side and to D 1 , D 2 and D 3 on another side generates the sets of motifs SM from D and SM 1 , SM 2 and SM 3 from D 1 , D 2 and D 3 respectively : SM ={m1, m2, m3, m4, m5, m6, m7, m8, m9, m10} SM 1 ={m1, m4, m5, m6} SM 2 ={m1, m2, m3} SM 3 ={m1, m6, m7, m8}

Figure 3 :

 3 Figure 3: Effect of classification test technique (LOO and 10CV) to the classification accuracy rates using LOO-based variation

Figure 4 :

 4 Figure 4: Effect of classification test technique (LOO and 10CV) to the classification accuracy rates using 10CV-based variationWe notice that NG is virtually insensible to varia-

Figure 5 :

 5 Figure 5: Interest of stable motifs using LOO-based variation

Figure 6 :Table 4 :

 64 Figure 6: Interest of stable motifs using 10CV-based variation

  extraction method M applied to D on one side and to D 1 , D 2 ,.., D n on the other side and respectively generating the sets of motifs SM from D and SM 1 , SM 2 , .., SM n from D 1 , D 2 ,.., D n . Definition 3.3. (Method sensibility) A method M 1 is more sensible than another method M 2 if and only if for the same changes within the same dataset, the rate of stable motifs of M 1 is lower than that of M 2 .

	(3.3)
	Definition 3.2. (Rate of stable motifs) The rate
	of stable motifs (RSM ) of a method M is the ratio of
	the number of stable motifs to the number of distinct
	motifs of all SM i , i = 1..n. Formally:
	(3.4)	RSM =	N umber of stable motif s | ∪ n i=1 SM i |	.

-An artificial learning task T and a quality metric M tr of T . Let M tr T (SM ) denote the value of the metric obtained if T is performed using the set SM as a feature space.

We define the following: Definition 3.1. (Motif Stability) A motif x is said to be stable if and only if its occurrence rate in all SM i , i = 1..n, exceeds a threshold . The occurrence rate is simply the ratio of the number of SM i , i = 1..n, where x appears to n. Formally: N umber of SM i /x ∈ SM i n ≥ τ, with i = 1..n .

  .6)

	Definition 3.5. (Interest) A set of stable motifs
	SSM is considered to be interesting if it allows inter-
	esting values of conservation and sensibility. Formally,
	we can measure this interest I by:

Table 1 :

 1 Experimental data

	Dataset IdP Family / class	#sequences
			High-potential	19
			Iron-	Sulfur
			Protein
	DS1	48% Hydrogenase	20
			Nickel	Incorpo-
			ration	Protein
			HypA
			Glycine Dehydro-	21
			genase
	DS2	28%	Human TLR Non-human TLR	14 26
	DS3	48%	Chemokine Melanocortin	255 255
			Monomer		208
			Homodimer	335
			Homotrimer	40
	DS4	25% Homotetramer	95
			Homopentamer	11
			Homohexamer	23
			Homooctamer	5
	4.2 Motif extraction methods. We compare the
	motif extraction methods quoted in

Table 2 :

 2 Accuracy rate of the studied methods using datasets without modification

	Method	DS1 10CV LOO 10CV LOO 10CV LOO 10CV LOO DS2 DS3 DS4
	NG	96.7	96.7	67.5	67.5	100	100	44.9	45.5
	AM	100	100	72.5	65	100	100	-	-
	DD	96.7	96.7	82.5	80	100	100	43.5	43.5
	DDSM 96.7	96.7	95	95	100	100	82.5	87.5