Julien Subercaze
email: julien.subercaze@univ-st-etienne.fr

Christophe Gravier
email: christophe.gravier@univ-st-etienne.fr

Lifting user generated comments to SIOC

Keywords: Data extraction, Frequent subtree mining, users comments

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

The SIOC ontology [START_REF] Breslin | Towards semantically-interlinked online communities[END_REF] has been defined to represent user social interaction on the web. It aims at interconnecting online communities. Nowadays SIOC data are mostly produced by exporters 1 . These exporters are plugins to existing frameworks such as blog platforms (Wordpress, DotClear , . . .), content management systems (Drupal) and bulletin boards. Unfortunately, these exporters are not yet default installation plugins for these frameworks. Therefore few administrators enable them, as a consequence the SIOC data production remains the exception. 2 . There exists also numerous closed source platforms that supports online communities, among them are the online newspapers that allows commenting on article, Q&A systems. This subset of the user generated content on the web will never be unlocked using exporters.

In this paper we present CommentsLifter, a web-mining approach that aims at extracting users' comments directly from HTML pages, in order to circumvent the exporter issue. The comments are identified in webpages by mining frequent induced subtrees from the DOM , and using heuristics allow to discriminate the different field of the comment (username, date, . . .). This approach does not require any a priori knowledge of the webpage. We empirically evaluated our approach and obtained very good results.

The paper is structured as following. The next section presents related works on both structuring data into semantic web formats and web mining approaches. Section 3 presents a formalisation of the problem and recalls some theoretical tree mining results. Section 4 details the different steps of CommentsLifter, followed by experimental results. Finally, section 6 concludes.

Related works

Converting existing format of data into RDF is a cornerstone in the success of the semantic web. The W3C maintains a list of available RDFizer on its website 3 . Input data can be either structured or unstructured. In the former case, if the semantics of the data can be extracted, then the conversion can take place without human intervention [START_REF] Huynh | Piggy bank: Experience the semantic web inside your web browser[END_REF], otherwise the user needs to manually specifiy the semantic of the data. Sesame contains an API called SAIL (Storage And Inference Layer) that can be used to wrap existing data format into RDF. The BIO2RDF project [START_REF] Belleau | Bio2rdf: towards a mashup to build bioinformatics knowledge systems[END_REF] uses this API to build bioinformatics knowledge systems. Van Assem presented a method for converting Thesauri to RDF/OWL [START_REF] Van Assem | A method for converting thesauri to rdf/owl[END_REF] that has been succesfully applied for biological databases [START_REF] Belleau | Bio2rdf: towards a mashup to build bioinformatics knowledge systems[END_REF]. In order to convert mailing list archive into a RDF format, the authors of [START_REF] Fernández | Mailing lists meet the semantic web[END_REF] developed SWAML, a python script that reads a collection of messages in mailbox and generates a RDF description based on the SIOC ontology. Since the input data are already structured (i.e. emails follow the RFC 4155) the conversion is straightforward. On the other side, there exist several approaches that aims at automatically or semi-automatically adressing the case where user intervention is usually required. Text-To-Onto [START_REF] Maedche | Ontology learning for the semantic web[END_REF] is a framework to learn ontology from text using text mining techniques as well as its successor Text2Onto [START_REF] Cimiano | Text2onto. Natural Language Processing and Information Systems[END_REF]. However none of these papers provide a sound evaluation of the quality of learnt ontologies. This is due to the very nature of ontology modeling in which no ground truth can be assessed, there exist as many model as one could imagine for describing the same thing. In [START_REF] Berendt | Towards semantic web mining[END_REF], Berendt details relationships between web mining and semantic web mining. The different cases (ontology learning, mapping, mining the semantic web, . . .) are detailed. From this categorization, the purpose of our research falls into the category of instance mining, which focuses on populating instances for existing semantics. For this purpose, learning techniques have been proposed for web scale extraction with a few semantic concepts [START_REF] Craven | Learning to construct knowledge bases from the world wide web[END_REF] and presented promising results at the time of the publication. Textrunner [START_REF] Yates | Textrunner: open information extraction on the web[END_REF] also learns extractor to perform webscale information extraction, presenting good precision but a very low recall. Concerning non learning techniques, automatic modelling of user profiles has been performed in [START_REF] Gentile | Extracting semantic user networks from informal communication exchanges[END_REF], using term recognition and OpenCalais for named entity recognition.

Several techniques have been developed for web extraction. In [START_REF] Cai | Extracting content structure for web pages based on visual representation[END_REF], the authors simulate how a user visually understands Web layout structure. [START_REF] Lin | Discovering informative content blocks from web documents[END_REF] divided the page based on the type of tags. Many recent research works exploit text density to extract content on pages [START_REF] Kohlschütter | A densitometric approach to web page segmentation[END_REF][START_REF] Sun | Dom based content extraction via text density[END_REF][START_REF] Kohlschütter | Boilerplate detection using shallow text features[END_REF]. This approach presents good results regarding article content extraction. In order to do so, the boilerpipe library 4 , based on the work from Kohlschutter [START_REF] Kohlschütter | A densitometric approach to web page segmentation[END_REF][START_REF] Kohlschütter | Boilerplate detection using shallow text features[END_REF] is widely used. For a more detailed survey on the different Web data extraction we encourage the reader to refer to [START_REF] Chang | A survey of web information extraction systems[END_REF]. Among other techniques DEPTA [START_REF] Zhai | Web data extraction based on partial tree alignment[END_REF] (an extension of works done in [START_REF] Liu | Mining data records in web pages[END_REF]) presents an hybrid approach of visual and tree analysis. It uses a tag tree alignment algorithm combined with visual information. In a first step DEPTA processes the page using a rendering engine (Internet Explorer) to get the boundaries information of each HTML element. Then the algorithm detects rectangles that are contained in another rectangle, and thus build a tag tree in which the parent relationships indicates a containment in the rendered page. DEPTA then uses a string edit distance to cluster similar nodes into region. Since each data region in a page contains multiple data records, extracted tag trees must be aligned to produce a coherent database table. A tree edit distance (like in [START_REF] Reis | Automatic web news extraction using tree edit distance[END_REF]) is then defined and used to merge trees. However DEPTA is not able to extract nested comments. We will use a different approach, that only requires DOM parsing technique and that is suitable for analyzing huge amount of pages. Our approach is based on a theoretical tree mining background, presented in the next section.

Problem Definition

The purpose of our work is to provide a solution for the leverage of Linked Data using the SIOC schema from user generated comments on webpages, without any a priori knowledge on the webpage. Our main assumption is that comments on a given webpage (even at domain scale) are embedded in the same HTML pattern. This assumption is well fulfilled in the practice since comments are usually stored in a relational database and exposed into HTML after an automatic processing. Therefore our goal is to automatically determine the HTML pattern that is used to expose the comments and then to identify the relevant information in the content to fill SIOC instances.

Basically a comment is a sioc:Post contained in a sioc:Forum container. We identified the following subset of the core-ontology properties of sioc:Post to be relevant for the extraction (we marked with * the mandatory properties and relationships) : The sioc:Container pointed by sioc:has container can be from different types in our case. We consider extraction from user reviews (sioct:ReviewArea), posts on forum (sioc:Forum), comments from blogs (sioct:Weblog), Q&A answers (sioct:) or generally for newspaper discussion (sioc:Thread ). However, distinguishing these differents subclasses of sioc:Container would require classification from the webpages we intend to perform extraction on. This is out of the scope of our paper, we will therefore uniformally consider the container as an instance of sioc:Container. Similarly there exists subclasses of a sioc:Post for each container. As for the container, our algorithm will output sioc:Post items.

To summarize, our problem is the following : in order to generate SIOC data from raw HTML, we must identify the different items (sioc:Post) and their conversational relationships (sioc:reply to and sioc:has reply). For each item we must identify the user (sioc:UserAccount), the content of the post (sioc:content) and when possible the date and the title. Tree mining deals with the task of finding pattern of interest in single tree (FREQT or AMIOT) or in forests [START_REF] Zaki | Efficiently mining frequent trees in a forest: Algorithms and applications[END_REF]. The patterns to be extracted, as well as the trees they should be extracted from, may differ in nature. Trees are pigeonholed along three criteria: rooted/unrooted, ordered/unordered and labeled/unlabeled. A tree is called rooted if there exists a node that has been designated the root, in which case the tree may be traversed in two directions: towards and away from the root. A tree is said to be ordered if an ordering for the children of each vertex has been defined. Finally a tree is a labeled tree if each node is given a unique label. For our concern, i.e. tree mining using DOM trees, we will consider the case of rooted labeled ordered trees. The patterns to be mined are subtrees. There are different types of subtrees for there exists different types of trees. We present in the following the most common types of subtrees (from [START_REF] Chi | Frequent subtree mining-an overview[END_REF], which provides a very detailed review on frequent subtree mining). For each case, we consider a rooted tree T with vertex set V and edge set E and a subtree T with respectively V its vertex set and E its edge set. The main types of subtrees are as follows.

Theory recall : tree mining

Bottom-up subtree T is a bottom-up subtree from T iff : V ⊆ V , E ⊆ E; for a vertex v ∈ V , if v ∈ V then all descendants of v must be in V ;
the ordering of the siblings must be preserved in the subtree. Intuitively a bottom-up subtree T can be obtained by taking a vertex from V together will all its descendants and the corresponding edges. Induced subtree T is an induced subtree from T iff : V ⊆ V , E ⊆ E; for a vertex v ∈ V , the left-to-right ordering of the siblings must be preserved in the subtree, i.e. it should be subordering of the corresponding vertices in T . Intuitively a induced subtree T can be obtained by repeatedly removing leafs from T . Embedded subtree T is an embedded subtree from T iff :

E ⊆ E, (v 1 , v 2 ) ∈ E where v 1 is the parent of v 2 in T only if v 1 is ancestor of v 2 in T .
Intuitively, as an embedded subtree, T must not break the ancestor-descendant relationship among the vertices of T .

Figure 1 illustrates these three types of subtrees from a given data tree through three different examples. To better understand the difference between the subtrees, one can say that bottom-up subtrees are complete subtrees while inducted subtrees allow to remove nodes horizontally in the subtree and finally embedded subtrees allow both horizontal and vertical removals. We have the following relationship: bottom-up subtree ⊆ induced subtree ⊆ embedded subtree. Following the same order, algorithms' complexity and running time vary with the type of subtree one wants to extract. Therefore it is desirable to well identify which type of subtree we are looking for.

Frequent Subtree Mining

In the case of product listing extraction, the goal is to extract frequent subtrees that are identical in the page. For this purpose, a bottom-up subtree mining objective is sufficient. For selecting a feature among mined items, for example title and price, a filter on the leaf nodes can be applied. For the case of comments extraction, the patterns can be nested. For instance lets assume that the pattern that we are looking for is [a[p; br; p; div]]. If we encounter an answer to a comment, i.e. nested instances in the pattern, the tag tree for the comment and its answer could be as follows : [a[p; br; p; div; [a[p; br; p; div]]]]. In the case of a single comment we will encounter our pattern [a[p; br; p; div]]. We observe that nodes can be skipped horizontally along with their descendants, which eliminates the bottom-up subtree type. We observed empirically that instances are nested in the way we described previously : the direct parenting relation is preserved. Consequently induced subtree is a sufficient type of subtree for our purpose. Embedded subtree mining could also be used, however since the algorithms complexity grow with the complexity of the pattern to mine, induced subtree mining is definitely more appropriate.The major advantage of subtree mining over existing works is that it provides a mine once extract many approach. For mining a whole website, one would need to mine the pattern from only one webpage and could later extract data by simple pattern matching on other pages, thus saving large amount of computation time. In the next section, we present SIOCizer, our approach to comments extraction based on frequent subtree mining.

CommentsLifter

We now start the description of CommentsLifter. This section presents the different steps of our algorithm. The underlying idea of CommentsLifter is to use simple observations on Web pages structure to reduce the candidate set generation. This allows to minimize the error rate while selecting the winning pattern, and to contribute to the runtime performance optimization objective. To extract comments from a Web page, CommentsLifter uses seven steps: Document preprocessing, Frequent subtrees extraction, Clustering, Merging, Pattern expansion, Winner selection, Field extraction, Data extraction. In the next subsections we detail the process followed in each step of our algorithm.

Preprocessing

Recommendations issued by the W3C aim at specifying the languages of the World Wide Web, among other various versions of HTML and CSS. While pages following these recommendations produces clean DOM trees, they represent only 4.13 % of the Web pages 5 . The remaining pages are made of wrongly formatted HTML code that is often referred to as "tag soup" 6 . Due to the large portion that these pages represent, Web browser engines are able to handle malformed HTML tags, improperly nested elements, and other common mistakes. In our algorithm, the first step involves to convert any input HTML document (malformed or not) and to output a well-formed document as DOM tree. For this purpose, any dedicated library (Jsoup7 , Jtidy8 ) or browser engine can be used.

Frequent subtrees extraction

The next step of our algorithm consists in the generation of a first candidate set. For this purpose we extract frequent depth-two trees from the DOM and store them in a cardinality map (an example is given in Table 1). The basic of our approach is to select patterns with a depth of two that we will later expand into largest patterns if possible (empirical results in Section 5 show that the average depth of comment pattern is 4.58). For this purpose, a tag tree is generated from the preprocessed DOM. CommentsLifter traverses the tree in a top down fashion and stores the encountered trees of size two (each node that has children, along with its children). The results are sorted, as presented in Table 1. Candidates with less than two occurrences are discarded, since we assume that there are at least two comments. The same assumption is made for instance by [START_REF] Zhai | Web data extraction based on partial tree alignment[END_REF]. For each pattern occurrence, the encountered instance is stored in a multimap(in fact we only store the label of the parent node). At this stage our candidate set is initialized and necessarily contains the instances of comments we are looking for.

Clustering

Comments in a Web page appears in a continuous manner, it is very unlikely that comments are stored in different branches of the DOM tree. We did not encounter the case of split comments in different subtrees during our experiments. In fact, comments are organized in a tree structure, where the beginning of the comments block is the root of the tree (node with label 0, not depicted on the figure). Since comments are located in the same subtree, we process to a clustering phase of the occurrences for each pattern.

In this step, we aim at clustering co-located instances of the same pattern. In other words, the algorithm builds the couples (pattern, Instances), where each pattern is associated with a set of instances matching it that are located in the same subtree and close to each other. Consequently, one pattern can be associated multiple times with a unique set of instances, whose member is distinct from any other member of another associated set to the pattern. This means that each couple (pattern, Instances) is splitted into different (pattern, Instances) where the instances in Instances do belong to the same subtree in the DOM. The basic of our algorithm is a distance-based clustering.For each given pattern, the algorithm sorts its instances along their depth in the tree. At each depth, we check for each instance if it has a parent in the previously found (pattern, Instances). For the remaining instances, we cluster them using a classical node distance in trees : d(a, b) ∈ N is the length of the shortest path between the nodes a and b. After building the set of (pattern, Instances), we remove elements where the cardinality of instances is equal to one.

For example, running our algorithm on the tree provided by Figure 2 with the pattern ul[li; li] would produce two couples (pattern,instances) that are depicted with dotted and dashed boxes in the same figure. At the end of this step, CommentMiner holds the set of couples (pattern, Instances) that matches a pattern to a set of co-located instances in the DOM tree. In the next step, we try to identify mergeable patterns from this data structure.

Merging

HTML patterns that contains comments often have a depth greater than two (see Section 5 for more details). Consequently our candidate set may at this step contain couple of (pattern, Instances) that in fact do belong to the same global pattern, that we did not discover yet because the pattern expansion process will occur later. Instead of discovering the same pattern from different candidates, we aim at merging these candidates beforehand for optimization.

For this purpose we perform a pairwise comparison between the sets of instances and we process a merge in the case where every element s of set S 1 is topped by an element in the set S 2 . An element is topped by another if the latter is a parent of the former. If a set of instances is topped by another set, we discard this set and restart the process until no further updates to the candidate set are performed.

Algorithm 1 presents this merging process. After this step, the candidate set is again drastically pruned since we eliminated all potentially duplicate patterns for the expansion phase. This process, together with the previous clustering process, are the key phases of our algorithm since they discard both duplicate and irrelevant candidates.

Pattern expansion

Since the candidate set contains simple pattern (i.e. of depth two), we process a pattern expansion to discover the fully matching patterns. Patterns may be expanded in both direction, towards the top and the bottom of the tree.

For each candidate (pattern, Instances), we distinguish two cases. In the first case every instance is at the same depth in the tree, this is the case of product listing extraction that we call flat case. This is the case of bottom-up subtree mining (see Figure 1). The second case also called nested case is the one where instances belong to the same subtree but at different depths, this is the case of induced subtrees in Figure 1 . Top expansion is straightforward, we check if the type of the parent node (i.e. HTML markup tags) for every instance is the same, in this case we expand the pattern with the new parent node and update the instances consequently. This process is executed until all the instances do not share the same tag as parent node or if the same node (in sense of label in the tree, not HTML markup tag) is the parent of all instances. This process is the same for both nested and flat cases. Once a pattern is expanded in the top direction, the bottom expansion takes places. This bottom expansion in the flat case, similarly to the top expansion is simple since top-down subtrees are easy to extract. One just needs to traverse the instances trees in a top-down most left direction, looking for nodes that are shared by all instances. Once a node is not present in every instance the algorithm uses backtracking to select the next sibling, and then to continue its process.

However the nested case is not trivial since we look for embedded subtrees. Standard algorithms such as AMIOT and FREQT are dedicated to this task, but as we mentioned in section 3.2 they performed poorly on the full Web page, either the running was excessively long (some minutes) or the program ended with an exception. To make an efficient use of these algorithms, we take advantage of specificities of comments extraction. Apart from the aforementioned issues, the biggest problem we encountered using AMIOT or FREQT was that we were unable to adaptatively select the support (in fact, a percentage) for a Web page. However in our pattern expansion case, we know how much instances are present for each couple (pattern, Instances). Thus, we performed modification in the algorithms (see Implementation in section 5.1 for further details) to discard candidates pattern not on a minimum support base, but on a strict occurrence equality base. Finally, instead of using the complete Web page as the data tree, we construct a tree by adding all the instances in a tree. More precisely since the instances are stored using their top nodes, we build the data tree by adding the subtrees under the instances top nodes as children of the root node. Therefore, our data tree contains on ly the relevant instances. Consequently the set of candidates pattern is drastically reduced, compared with the use of the whole DOM page. To drive AMIOT in the right direction, the candidate pattern set is initialized with the current depth-two pattern, thus avoiding useless candidate generation for the first stage. Figure 3 depicts this expansion process . In this figure we present the instances as they appear in the DOM tree. Our starting pattern is ul[li; li], and its instances are represented within the dotted boxes. Both instances have a div node with a different label as parent, consequently the pattern is expanded to the top : div[ul[li; li]]. Next, both instances again have a div node as parent but in this case this is the same node. The top expansion process finishes. For the bottom expansion, we consider this subtree as the data tree. AMIOT (resp. FREQT) performs a left to right expansion that adds the node a to the pattern: div[ul[li; li]; a]. The right most div node is discarded since it does not belong the left instance (the occurrence is one whereas the algorithms expects two). Then AMIOT adds the node p to the pattern that becomes div[ul[li; li]; a[p]]. The figure does not show the part under the right most div, in this part we could find for example another instance of div[ul[li; li]; a[p]], resulting in a nested comment.

Winner selection

Recurring structures competing with the comments pattern in the candidate set are usually menu elements, links to other articles. In [START_REF] Kohlschütter | Boilerplate detection using shallow text features[END_REF][START_REF] Kohlschütter | A densitometric approach to web page segmentation[END_REF], Kohlschütter developed a densitometric approach based on simple text features that presents excellent results (F 1 -Score : 95 %) for news article boilerplate removal. User generated comments also differentiate from menu elements on their text features. Comments are from different text lengths, the link density is low since comments are not part of a link as a difference with menu items. We developed simple heuristics, based on our observations, to discard irrelevant candidates and to rank the remaining candidates.

Our experimentation showed that instances with a link density greater than 0.5 (Kohlschutter found 0.33 for news article) are always boilerplate. Short comments in very complex HTML boilerplate patterns can produce instances with a quite high link density. We empirically observed that links are on the username or on its avatar and links to a profile page. Consequently we discard candidates where the average link density is above 0.5.

For the remaining candidates their score is given by the following formula:

Score(p, I) = lgt(I) × 1 n -1 n j=1 lgt(I) -lgt(I j ) 2 (1)
The above formula computes the average text length times its standard deviation. This heuristic promotes candidates where the instances have longer text length with variable length. Finally we did not use heuristics based on a lower bound of words (as in [START_REF] Kohlschütter | Boilerplate detection using shallow text features[END_REF][START_REF] Kohlschütter | A densitometric approach to web page segmentation[END_REF]). Once again comments extraction differs from traditional boilerplate removal since some comments are sometimes just one word (e.g. lol, +1, first) or there may be longer than the article they are commenting. Therefore the standard deviation is very useful for eliminating menu items where the text length is often very close among their instances. The (pattern, Instances) couple with the highest score is promoted as the winner. At this step, the algorithm output the tree of instances, i.e. we have the structure of the conversation, but we need to further structure the conversation by identifying the different fields in the pattern.

Structuring the content

Once the HTML pattern containing comments has been selected, the next step of our algorithm consists in extracting the related SIOC fields as we described in section 3. Two fields are always present in a comment : the username and the content of the comment. From our observations on various website (online press, Q&A, blogs, reviews), two other fields appear often. Firstly the date when the comment has been posted occur in 97.95 % of the cases (See Table 2). Comments less often have a title, but the percentage we measured ( 24.48 %) remains high enough to be of interest. We voluntarily skipped the extraction of rare fields (vote on comments, account creation date) because of their few occurrences and the fact that they complicate the whole fields identification process. From our observations, we noticed that content and title are always contained into their own HTML markup tags, i.e. it is very unlikely to see the title and the content in the same div. However we noticed that username and date often occur between the same markup tag, for example we often encountered comments fields such as <div>John, May 25, 2012 at 5:00 p.m</div>. Therefore we apply the following procedures : first, identifying the date field within the pattern. We store the location of the date in the pattern and remove dates in every instances. For instance, the previous example will become<div>John</div>. At this point we are sure that the fields we are looking for will be in distinct nodes of the pattern.

Date parsing Date parsing library such as JodaTime9 and JChronic10 perform well on extracting date from messy data. These libraries takes a String as input and return a Date object. However they do not offer the feature of returning the original text without the substring containing the date. Therefore we developed our library, using features and heuristics from both of the above mentioned libraries, that offers the date string removal feature.

Fields selection Our heuristic is based again on simple observations. We know that every comment contains at least a username and a content. Date and title being optional. For each leaf of our pattern, we compute the following measures over its instances : percentage of date found, average text length, standard deviation of text length, text entropy and average word count, standard deviation on word count. Using these values, we build two candidate sets, the first one for the date the other one for title, content and username. We distinguish these fields using the fact that title, content and username are unstructured text, however dates have a particular structure (containing year, days, . . .).

A node in the pattern is a candidate for the date field if its percentage of date found is over 0.7 (to take into account the fact that date extraction is not perfect), has more than two words and has a coefficient of variation on the word count that is inferior to 0.2. This latter condition requires that the number of words is very close from one instance to another. We did not set value to zero to avoid discarding fields where the date has a variable length, for example one hour ago and yesterday. From these candidates, we pick the field with the highest entropy in order to discard constant fields that may have been recognized as a date. However if the set is empty, then no date are specified for the comments, practically this happens very rarely.

The second candidate set should contain only nodes that instances own textual data. For this purpose we discard the nodes in the pattern where the variation of text entropy is equal to zero (constant text in every instance). Since we know that the node containing the content must be present within this set, we aim at identifying this field in the first place. Luckily the content is very simple to identify since it contains the most words, has a very variable length and word count. In the practice, selecting the node having the highest word count average is sufficient. Once the content has been removed from this candidate set, we first check its size. If the size is equal to one, the remaining candidate matches the username. In the case where two candidates are present, we have to distinguish between username and title. Username are very short names, usually one or two words, and is then in average shorter than the title. If two fields are present, the shorter is identified as being the username and the longest is then the title.

Mining experiments

This section presents the evaluation protocol of CommentsLifter as well as experiment's results. We first detail the experimental setup, which is a bit particuliar for comments extraction due to the large use of AJAX. Finally we present global and detailed results for both flat and nested cases.

Setup

Many Web pages handle comments using AJAX, consequently downloading raw HTML along manual ground truth construction is not sufficient for building the dataset. To circumvent this issue we developed two components:

Firefox Extension We implemented a Firefox extension that sends the current DOM (after browser-side Javascript processing) to a Web server. Web Server The server receives the DOM from the browser through a POST request on a servlet, then runs CommentsLifter and presents an evaluation form along with the extracted comments. The user is asked to evaluate the pertinence of the extraction. We distinguish three cases for the result. We used Jena11 to generate the SIOC output.

Evaluation

The results obtained from evaluation are given in Table 2 and Table 3. Table 2 presents extraction results of the pattern mining part (steps 1 to 6 of the algorithm) whereas Table 3 presents the field identification results (step 7). The sixth first steps of the algorithm presents very good results, with a global F 1 score over 92%. Concerning field identification we first present the occurrence of the different fields over our dataset. Username and content are always present, while the date is not far from being present in every comment. However titles are to be found in one quarter of the comments. The evaluation accords to the heuristics we describe in section 4.7. Content extraction is a straightforward task since it is easy to "measure" differences with other fields, our algorithm perform perfectly at this task. Date parsing is no easy task, however our algorithm still performs well with an identification rate of 83.67 %. However it is to note that while the rest of the process is language agnostic, date parsing libraries are designed to work with western languages (english, german, french, spanish, . . .) but may fail with other languages, especially with non latin alphabet.

Conclusions and future work

In this paper, we presented CommentsLifter an algorithm that extracts users' comments and output SIOC data. Our algorithm combines mining induced subtrees from the DOM with simple yet robust heuristics to select the pattern containing the comment as well as for identifying the several fields within the pattern. The empirical evaluation presents very good results, for both extraction and field identification. We successfully extracted comments from various types of Web sites, without a priori knowledge, such as online newspapers, forum, user reviews, blogs and we were able to reconstruct the conversations. Further research will focus on refining the category of the extracted container, in order to determine wether the discussion takes into a forum, Q&A, blog, review area.

  sioc:content* : text-only representation of the content sioc:topic: title of the comment dcterms:created : creation date and relationships : sioc:has creator * : points to a sioc:UserAccount which is the resource sioc:has container * : indicates a sioc:Container object dcterms:title : text representation of the title dcterms:created : date of creation of the resource. sioc:reply to : links to a sioc:Post item sioc:has reply : links to sioc:Post items

Fig. 1 .

 1 Fig. 1. Different types of subtree from tree (a) : bottom-up subtree (b) ; induced subtree (c) ; embedded subtree (d)

Fig. 2 .

 2 Fig. 2. Example output for section 4.3 with the pattern ul[li; li]

Fig. 3 .

 3 Fig.3. Pattern expansion process, top expansion until the same node (top div node) is shared by both instances, then bottom expansion for induced subtree (the most right div is skipped)

Table 1 .

 1 Example of two depth candidates.

	Count	13	12	10	8
	Tree div[a;br;i;p] ul[li;li] div[p;p] div[p;p;p]

Table 2 .

 2 Evaluation : steps one to six

			Ground	True	False
	Pages	Truth	Positive	Positive
	Global 100	2323	2121	153
	Flat	77	1837	1674	125
	Nested 23		486	447	26
		Precision Recall	F1
	Global 93,3 % 91,3 % 92,3 %
	Flat	93.1 % 91.1 % 92.1 %
	Nested 94.5 % 91.97 % 93.22 %
				Content Username Date Title
	Occurrence (%)		100	100	97.59 24.48
	Correct extraction (%)	100	87.75	83.67 81.63

Table 3 .

 3 Evaluation, step seven : field identification

http://sioc-project.org/exporters

http://www.w3.org/wiki/SIOC/EnabledSites

http://www.w3.org/wiki/ConverterToRdf

http://code.google.com/p/boilerpipe/

http://arstechnica.com/Web/news/2008/10/opera-study-only-4-13-of-the-Web-isstandards-compliant.ars

[START_REF] Chang | A survey of web information extraction systems[END_REF] http://en.wikipedia.org/wiki/

Tag_soup 7 http://

jsoup.org/ 8 http://jtidy.sourceforge.net/

http://joda-time.sourceforge.net/

https://github.com/samtingleff/jchronic

http://jena.apache.org/


Louis Cuel

Jacques-Olivier Lachaud

Boris Thibert

Voronoi-based geometry estimator for 3D digital surfaces

We propose a robust estimator of geometric quantities such as normals, curvature directions and sharp features for 3D digital surfaces. This estimator only depends on the digitisation gridstep and is defined using a digital version of the Voronoi Covariance Measure, which exploits the robust geometric information contained in the Voronoi cells. It has been proved in [1] that the Voronoi Covariance Measure is resilient to Hausdorff noise. Our main theorem explicits the conditions under which this estimator is multigrid convergent for digital data. Moreover, we determine what are the parameters which maximise the convergence speed of this estimator, when the normal vector is sought. Numerical experiments show that the digital VCM estimator reliably estimates normals, curvature directions and sharp features of 3D noisy digital shapes.

Introduction

Differential quantities estimation, surface reconstruction and sharp feature detection are motivated by a large number of applications in computer graphics, geometry processing or digital geometry.

Digital geometry estimators. The commun way to link the estimated differential quantities to the expect Euclidean one is the multigrid convergence principle: when the shape is digitized on a grid with gridstep h tending to zero, the estimated quantity should converge to the expected one. In dimension 2, several multigrid convergent estimators have been introduced to approach normals [START_REF] De Vieilleville | Comparison and improvement of tangent estimators on digital curves[END_REF][START_REF] Provot | Estimation of the derivatives of a digital function with a convergent bounded error[END_REF] and curvatures [START_REF] Provot | Estimation of the derivatives of a digital function with a convergent bounded error[END_REF][START_REF] Kerautret | Curvature estimation along noisy digital contours by approximate global optimization[END_REF][START_REF] Roussillon | Accurate curvature estimation along digital contours with maximal digital circular arcs[END_REF]. In 3D, empirical methods for normal and curvature estimation have been introduced in [START_REF] Fourey | Normals and curvature estimation for digital surfaces based on convolutions[END_REF]. More recently, a convergent curvature estimator based on covariance matrix was presented in [START_REF] Coeurjolly | Integral based curvature estimators in digital geometry[END_REF].

Voronoi-based geometry estimation. Classical principal component analysis methods try to estimate normals by fitting a tangent plane or a higher-order polynomial (e.g. see [START_REF] Cazals | Estimating differential quantities using polynomial fitting of osculating jets[END_REF]). In contrast, Voronoi-based methods try to fit the normal cones to the underlying shape, either geometrically [START_REF] Amenta | Surface reconstruction by voronoi filtering[END_REF] or more recently using the covariance of the Voronoi cells [START_REF] Alliez | Voronoi-based variational reconstruction of unoriented point sets[END_REF][START_REF] Mérigot | Voronoi-based curvature and feature estimation from point clouds[END_REF]. Authors of [START_REF] Mérigot | Voronoi-based curvature and feature estimation from point clouds[END_REF] have improved the method of [START_REF] Alliez | Voronoi-based variational reconstruction of unoriented point sets[END_REF] by changing the domain of integration and the averaging process. The authors define the Voronoi Covariance Measure (VCM) of any compact sets, and show that this notion is stable under Hausdorff perturbation. Moreover, the VCM of a smooth surface encodes a part of its differential information, such as its normals and curvatures. With the stability result, one can therefore use the VCM to estimate differential quantities of a surface from a Hausdorff approximation such as a point cloud or a digital contour.

Voronoi Covariance measure background. The Voronoi covariance measure (VCM) has been introduced in [START_REF] Mérigot | Voronoi-based curvature and feature estimation from point clouds[END_REF] for normals and curvature estimations. Let K be a compact subset of R 3 and d K the distance function to K, i.e. the map d K (x) := min p∈K p -x . A point p where the previous minimum is reached is called a projection of x on K. Almost every point admits a single projection on K, thus definining a map p K : R 3 → K almost everywhere. The R-offset of K is the R-sublevel set of d K , i.e. the set K R := d -1

K (] -∞, R[). The VCM maps any integrable function χ : R 3 → R + to the matrix

V K,R (χ) := K R (x -p K (x))(x -p K (x)) t χ(p K (x))dx.
Remark that this definition matches the definition introduced in [1]: when χ is Fig. 1: VCM domain of integration. the indicatrix of a ball, one recovers a notion similar to the convolved VCM :

V K,R (χ) := K R ∩p -1 K (By(r)) (x -p K (x))(x -p K (x)) t dx. The domain of integration K R ∩ p -1 K (B y (r)
) is the offset of K intersected with a union of Voronoi cells (cf. Figure 1). The stability result of [START_REF] Mérigot | Voronoi-based curvature and feature estimation from point clouds[END_REF] implies that information extracted from the covariance matrix such as normals or principal directions are stable with respect to Hausdorff perturbation.

Contributions. The contributions of the paper can be sketched as follows. First, we define the estimator of the VCM in the case of digital data, for which we prove the multigrid convergence (Sect. 2, Theorem 1). We then show that the normal direction estimator, defined as the first eigenvector of the VCM estimator, is also convergent with a speed in O(h 1 8 ) (Sect. 3, Corollary 1). Furthermore, Theorem 2 specifies how to choose parameters r and R as functions of h to get the convergence. Finally, we present an experimental evaluation showing that this convergence speed is closer to O(h) in practice (Sect. 4). Moreover, experiments indicate that the VCM estimator can be used to estimate curvature information and sharp features in the case of digital data perturbated by Hausdorff noise.

VCM on digital sets

In this section, we define an estimator of the VCM in the case of 3D digital input. Theorem 1 explicits the conditions under which this estimator is multigrid convergent for digital data.

Definition

Let X be a compact domain of R 3 whose boundary is a surface of class C 2 . We denote ∂X the boundary of X, X h := Dig h (X) = X ∩ (hZ) 3 the Gauss digitisation of X, and ∂ h X ⊂ R 3 the set of boundary surfels of X h . We define a digital approximation of the VCM on a subset of the point cloud :

Z h = ∂ h X ∩ h(Z + 1 2 ) 3 . For each point x ∈ h(Z + 1 2 ) 3 with x = (x 1 , x 2 , x 3 ), we can define the voxel of center x by vox(x) = [x 1 -1 2 h, x 1 + 1 2 h] × [x 2 -1 2 h, x 2 + 1 2 h] × [x 3 -1 2 h, x 3 + 1 2 h].
We then define the digital VCM estimator as

V Z h ,R (χ) := x∈Ω R h h 3 (x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x)),
where

Ω R h = {x ∈ Z R h ∩ h(Z + 1 2 ) 3 , vox(x) ⊂ Z R h }
is the set of centers of voxels entirely contained in Z R h , the R-offset of Z h (see Fig. 2). Remark that the Hausdorff distance between ∂X and the point cloud Z h used in the definition is less than h.

Multigrid convergence of the VCM-estimator

The main theoretical result of the paper is the following theorem. Roughly speaking, it quantifies the approximation of the VCM of a smooth surface by the digital VCM of its Gauss digitisation. We denote by . op the matrix norm induced by the Euclidean metric. Given a function f : R n → R, we let f ∞ = max x∈R n |f (x)| and denote Lip(f ) = max x =y |f (x) -f (y)|/ x -y its Lipschitz constant.

Theorem 1. Let X be a compact domain of R 3 whose boundary ∂X is a C 2 surface with reach ρ > 0. Let R < ρ 2 and χ : R 3 → R + be an integrable function whose support is contained in a ball of radius r. Then for any h > 0 such that h ≤ min R, r 2 , r 2 32ρ , one has

V ∂X,R (χ) -V Z h ,R (χ) op = O Lip(χ) × [(r 3 R 5 2 + r 2 R 3 + rR 9 2 )h 1 2 ] + χ ∞ × [(r 3 R 3 2 + r 2 R 2 + rR 7
2 )h

1 2 + r 2 Rh] .
In the theorem and in the following of the text, the constant involved in the notation O(.) only depends on the reach of ∂X and on the dimension (which is three here).

For the proof of Theorem 1, we introduce the VCM of the point cloud Z h , namely V Z h ,R (χ). By the triangle inequality, one has

V ∂X,R (χ) -V Z h ,R (χ) op ≤ V ∂X,R (χ) -V Z h ,R (χ) op + V Z h ,R (χ) -V Z h ,R (χ) op .
In Proposition 1, we bound the second term and in Proposition 2, we bound the first term.

Estimation of the VCM of a point cloud. Here and in the following of this section, X is a compact domain of R 3 whose boundary ∂X is a C 2 surface with reach ρ > 0. We put R < ρ 2 and χ : R 3 → R + is an integrable function whose support is contained in a ball B y (r) of center y and radius r.

Proposition 1. For any h ≤ min R, r 2 , r 2 32ρ , one has

V Z h ,R (χ) -V Z h ,R (χ) op = O r 2 R 2 (Lip(χ)R + χ ∞ ) h 1 2 + r 2 R χ ∞ h .
Proof.

Step 1: The aim of the first step is to prove that

V Z h ,R (χ) = vox(Ω R h ) (x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x))dx + R 2 χ ∞ O(hr 2 ). Since vox(Ω R h ) ⊂ Z R h , one has V Z h ,R (χ) = vox(Ω R h ) (x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x))dx + Z R h \vox(Ω R h ) (x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x))dx
By using the facts that x -p Z h (x) ≤ R, χ is bounded by χ ∞ , and the support of χ is contained in the ball B y (r) (see Figure 2), the second term of the previous equation is bounded by

R 2 × χ ∞ × H 3 Z R h \vox(Ω R h ) ∩ p -1 Z h (B y (r)) . Now, we claim that Z R h ∩ p -1 Z h (B y (r)) ⊂ p -1 ∂X (B y (2r)). Indeed, let x ∈ Z R h ∩ p -1 Z h (B y (r)
). The fact that the Hausdorff distance between Z h and ∂X is less than

h implies that x ∈ ∂X R+h . Now, since h ≤ R, Lemma 4 implies that p ∂X (x) - p Z h (x) ≤ √ 8hρ + h, which leads to p ∂X (x) -y ≤ p ∂X (x) -p Z h (x) + p Z h (x) -y ≤ 8hρ + h + r ≤ 2r. Now, we show that Z R h \vox(Ω R h ) ⊂ ∂X R+h \∂X R-( √ 3+1)h . Indeed, as said just before, one has Z R h ⊂ ∂X R+h . Furthermore, if x ∈ ∂X R-( √ 3+1
)h , then the fact that the Hausdorff distance between Z h and ∂X is less than

h implies that x ∈ Z R- √ 3h h . Let c ∈ h(Z + 1 2 ) 3 be the center of a voxel containing x. The fact that diam(vox(c)) = √ 3h implies that vox(c) ⊂ Z R h , and thus x ∈ Z R h . We then get Z R h \vox(Ω R h ) ⊂ ∂X R+h \∂X R-( √ 3+1)h . We finally deduce that Z R h \vox(Ω R h ) ∩ p -1 Z (B y (r)) ⊂ ∂X R+3h \∂X R-3h ∩ p -1 ∂X (B y (2r)), (1)
whose volume is bounded by O(hr 2 ) by Proposition 3, which allows us to conclude.

Step 2: We then have to bound the remaining term

∆ = vox(Ω R h ) (x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x))dx -V Z h ,R (χ).
By decomposing ∆ over all the voxels of vox(Ω R h ), one has

∆ = c∈Ω R h vox(c) (x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x)) -(c -p Z h (c))(c -p Z h (c)) t χ(p Z h (c)) dx
As in Step 1, we can localise the calculation around the support of χ and we introduce the set of centers

D = Ω R h ∩ p -1 ∂X (B y (2r)). Using the relation χ(p Z h (c)) = χ(p Z h (c)) + χ(p Z h (x)) -χ(p Z h (x)), one gets ∆ = ∆ 1 + ∆ 2 ,
where

∆ 1 = c∈D vox(c) (x -p Z h (x))(x -p Z h (x)) t [χ(p Z h (x)) -χ(p Z h (c))]dx ∆ 2 = c∈D vox(c) [(x -p Z h (x))(x -p Z h (x)) t -(c -p Z h (c))(c -p Z h (c)) t ]χ(p Z h (c))
We are now going to bound ∆ 1 and ∆ 2 . One has

∆ 1 op ≤ c∈D vox(c) x -p Z h (x) x -p Z h (x) t χ(p Z h (x)) -χ(p Z h (c)) dx. For all c ∈ D and x ∈ vox(c), we have x -c ≤ √ 3 2 h. Furthermore, by definition of Ω R h , we have that x and c belong to Z R h ⊂ ∂X R+h . Then, since h ≤ R ≤ ρ 2 , Propo- sition 4 implies p Z h (x) -p Z h (c) = O(h 1 2 ) and then χ(p Z h (x)) -χ(p Z h (c)) = Lip(χ)O(h 1 2 ). Using the fact that x -p Z h (x) ≤ R, one has ∆ 1 op = Vol(vox(D)) × R 2 × Lip(χ) × O(h 1 2 ). Since vox(D) ⊂ Z R h ∩ p -1 ∂X (B y (2r)) ⊂ ∂X R+h ∩ p -1 ∂X (B y (2r)) and h ≤ R, Proposition 3 implies that Vol(vox(D)) = O(r 2 R). Finally ∆ 1 op = Lip(χ) × O(r 2 R 3 h 1 2 ). Similarly, let us bound ∆ 2 op . We put u = (x -c), v = c -p Z h (c) and w = p Z h (c) -p Z h (x)
. We can write x -p Z h (x) = u + v + w, and we get

∆ 2 = c∈D vox(c) [(u + v + w)(u + v + w) t -vv t ]χ(p Z h (c)) . From u ≤ h, v ≤ R and w = O(h 1
2 ), we bound the integrand by O( χ ∞ (R h

1 2 + h)). From Vol(vox(D)) = O(r 2 R), one has ∆ 2 op = O( χ ∞ (R 2 r 2 h 1 2 + r 2 Rh)).
Stability of the VCM. It is known that the VCM is stable. More precisely, Theorem 5.1 of [START_REF] Mérigot | Voronoi-based curvature and feature estimation from point clouds[END_REF]

states that V ∂X,R (χ r ) -V Z h ,R (χ r ) op = O(h 1 2
). However, the constant involved in O(h 1 2 ) depends on the whole surface ∂X. We provide here a more precise constant involving only local estimations, r and R. The proof is very similar to the one of [START_REF] Mérigot | Voronoi-based curvature and feature estimation from point clouds[END_REF], except that we localise the calculation of the integral. It is given in Appendix.

Proposition 2. For any

h ≤ R such that √ 8hρ + h ≤ r, one has V ∂X,R (χ r ) -V Z h ,R (χ r ) op = O Lip(χ) × [(r 3 R 5 2 + r 2 R 7 2 + rR 9 2 )h 1 2 ] + χ ∞ × [(r 3 R 3 2 + r 2 R 5 2 + rR 7 2 )h 1 2 ] . End of proof of Theorem 1. Let h ≤ min R, r 2 , r 2 32ρ . The assumption h ≤ r 2 32ρ
implies that √ 8hρ + h ≤ r. Thus we can apply Proposition 1 and Proposition 2.

Multigrid convergence of the normal estimator

Let X be a compact domain of R 3 whose boundary ∂X is a surface of class C 2 . We now want to estimate the normal, denoted by n(p 0 ), of ∂X at a point p 0 from its Gauss digitisation. We define the normal estimator by applying the digital VCM on a Lipschitz function that approaches the indicatrix of the ball B p0 (r).

Definition 1. The normal estimator n r,R (p 0 ) is the unit eigenvector associated to the largest eigenvalue of V Z h ,R (χ r ), where χ r is a Lipschitz function that is: equal to

1 on B p0 (r), equal to 1 -( x -p 0 -r)/r 3 2 on B p0 (r + r 3
2 ) \ B p0 (r), and equal to 0 elsewhere.

Remark that the normal estimator is defined only up to the sign. The following theorem gives an error estimation between ± n r,R (p 0 ) and n(p 0 ). Theorem 2. Let X be a compact domain of R 3 whose boundary ∂X is a C 2 surface with reach ρ > 0. Let R < ρ 2 . Then for any h > 0 such that h ≤ min R, r 2 , r 2 32ρ , the angle between the lines spanned by n r,R (p 0 ) and n(p 0 ) satisfies

n r,R (p 0 ), n(p 0 ) = O (rR -3 2 +R -1 +r -1 2 R -1 2 +r -3 2 +r -5 2 R 3 2 )h 1 2 +R -2 h+r 1 2 +R 2 .
The following corollary is a direct consequence. . Then for any h > 0 small enough, one has

n r,R (p 0 ), n(p 0 ) = O h 1 8 . Proof of Theorem 2. We introduce the normalized VCM N r,R (p 0 ) = 3 2πr 2 R 3 V Z h ,R (χ r ).
From Davis-Kahan sin(θ) Theorem [START_REF] Davis | The rotation of eigenvectors by a perturbation[END_REF], up to the sign of ± n r,R (p 0 ), one has

n r,R (p 0 ) -n(p 0 ) ≤ 2 N r,R (p 0 ) -n(p 0 )n(p 0 ) t op .
It is therefore sufficient to bound the right hand side. The triangle inequality gives

N r,R (p 0 ) -n(p 0 )n(p 0 ) t op ≤ 3 2πR 3 r 2 V Z h ,R (χ r ) -V ∂X,R (χ r ) op + 3 2πR 3 r 2 V ∂X,R (χ r ) -V ∂X,R (1 Bp 0 (r) ) op + 3 2πR 3 r 2 V ∂X,R (1 Bp 0 (r) ) -n(p 0 )n(p 0 ) t op .
The proof of the theorem relies on Theorem 1, that controls the first term, and on the two following lemmas. Lemma 1. Under the assumption of Theorem 2, we have

3 2πr 2 R 3 V ∂X,R (χ r ) -V ∂X,R (1 Bp 0 (r) ) op = O(r 1 2 ).
Proof. Since χ r = 1 Bp 0 (r) on the ball B p0 (r), by using similar arguments as previously, one has

V ∂X,R (χ r ) -V ∂X,R (1 Bp 0 (r) ) op ≤ Vol ∂X R ∩ p -1 ∂X (B y (r + r 3 2 )) p -1 ∂X (B y (r)) ×R 2 . Proposition 3 implies that the volume Vol ∂X R ∩ p -1 ∂X (B y (r + r 3 2 )) p -1 ∂X (B y (r)) is less than 4R × Area B y (r + r 3
2 ) B y (r) . The fact that this area is bounded by

O(r 5
2 ) allows to conclude. 7 Lemma 2. Under the assumption of Theorem 2, we have

3 2πR 3 r 2 V ∂X,R (1 Bp 0 (r) ) -n(p 0 )n(p 0 ) t op = O(r + R 2 )
Proof. We have the following relation (see Theorem 1 of [START_REF] Mérigot | Détection de structure géométrique dans les nuages de points[END_REF])

V ∂X,R (1 Bp 0 (r) ) = 2 3 R 3 1 + O(R 2 ) p∈Bp 0 (r)∩S n(p)n(p) t dp. ( 2
)
By the mean value theorem applied to the normal to ∂X, one has

n(p) -n(p 0 ) ≤ sup q∈S Dn(q) op l p,p0 ,
where l p,p0 is the length of a geodesic joining p and p 0 . Since the chord (pp 0 ) belongs to the offset ∂X R , where R < ρ, we have l p,p0 = O( p -p 0 ) (see [START_REF] Morvan | Approximation of the normal vector field and the area of a smooth surface[END_REF] for example). Therefore n(p)-n(p 0 ) = O(r) and thus n(p)n(p) t -n(p 0 )n(p 0 ) t = O(r). Consequently

p∈Bp 0 (r)∩S n(p)n(p) t dp = Area(B p0 (r) ∩ S)n(p 0 )n(p 0 ) t + Area(B p0 (r) ∩ S) O(r).
Combining with Eq. ( 2), we have

3 2R 3 Area(B p0 (r) ∩ S) V ∂X,R (1 Bp 0 (r) ) = 1 + O(R 2 ) × n(p 0 )n(p 0 ) t + O(r) .
We conclude by using the fact that Area(B p0 (r) ∩ S) is equivalent to πr 2 .

Experiments

We evaluate experimentally the multigrid convergence, the accuracy and robustness to Hausdorff noise of our normal estimator, and also its ability to detect features. The first series of experiments analyzes the convergence of the normal estimation by VCM toward the true normal of the shape boundary ∂X. The shape "torus" is a torus of great radius 6 and small radius 2, and the shape "ellipsoid" is an ellipsoid of half-axes √ 90, √ 45 and √ 45. We measure the absolute angle error with (p) = 180 π cos -1 (n(p) • n(p)) for every pointel p ∈ Z h of the digitized shape with several normalized norms:

l 1 ( ) def = 1 Card(Z h ) p∈Z h (p), l ∞ ( ) def = sup p∈Z h (p). (3)
In experiments we tried several kernel functions χ r and we display results for two of them: the "ball" kernel χ 0 p0,r (x) = 1 if x -p 0 ≤ r, 0 otherwise; the "hat" kernel χ 1 p0,r (x) = 1 -x -p 0 /r if x -p 0 ≤ r, 0 otherwise. Figure 3 displays the norms of the estimation angle error in degrees, for finer and finer digitization and R = bh 8 ). We observe the convergence of the estimator for parameters R = r = 3h

1 4 at a rate in O(h 1
1 4 , R = r = 3h 1 3 , R = r = 3h
α ∈ [ 1 3 , 1 2 ] if R = r = ah α .
Note that the kernel function has not a great impact on normal estimates, as long as it has a measure comparable to the ball kernel.

We perturbate the shape "torus" with a Kanungo noise model of parameter p = 0.25 (the number p d is the probability that a voxel at digital distance d from the boundary ∂X is flipped inside/out). This is not exactly a Hausdorff perturbation but most perturbations lie in a band of size 2h/(1 -p). Figure 4 shows that the normal is still convergent for all norms. Again convergence speed is experimentally closer to O(h 2 3 ), much better than the proved O(h 1 8 ). We then assess the visual quality of the estimators on several shapes, by rendering the digital surfels according to their estimated normals. First of all, Figure 5 displays normal estimation results on a noisy "torus" shape perturbated with a strong Kanungo noise of parameter p = 0.5. Then, Figure 6 displays the visual improvement of using normals computed by the VCM estimator. In particular, comparing Fig. 6b and Fig. 6c shows that convolving Voronoi cell geometry is much more precise than convolving only surfel geometry. Furthermore, we have tested our estimator on many classical digital geometry shapes (see Figure 7).

Our VCM estimator is a matrix and carries also curvature information along other eigendirections. Mérigot et al. [START_REF] Mérigot | Voronoi-based curvature and feature estimation from point clouds[END_REF] proposed to detect sharp features by using the three eigenvalues l 1 , l 2 , l 3 of the VCM as follows: if l 1 ≥ l 2 ≥ l 3 , compute l 2 /(l 1 + l 2 + l 3 ) and mark the point as sharp if this value exceeds a threshold T . Figure 8 shows such sharp features detection on the "bunny" dataset at many different scales, with T = 0.1 for all datasets (it corresponds to an angle of ≈ 25 • ). This shows that the VCM information is geometrically stable and essentially scaleinvariant. To conclude, we list below some information on computation times. This Fig. 4: Multigrid convergence of angle error of normal estimator (in degree) on a noisy shape. Abscissa is the gridstep h. Tests are run on "torus" shape (upper row) and on "ellipsoid" shape (lower row), perturbated by a Kanungo noise of parameter 0.25, for three kernel radii

(R = r = 3h α for α ∈ { 1 4 , 1 3 , 1 2 }), two norms (l 1 , l ∞ ): (left) kernel ball function χ 0 r , (right) kernel hat function χ 1 r .
estimator has been implemented using the DGtal library [START_REF]DGtal: Digital geometry tools and algorithms library[END_REF], and will soon be freely available in it. Image size #surfels (R, r) χ r -VCM comput. Orienting normals "Al" 150 3 48017 (30, 3) 0.73 s 0.88 s "rcruiser" 250 3 66543 (30, 3) 1.26 s 0.99 s "bunny" 516 3 933886 (30, 5) 30.1 s 15.9 s "Dig. Snow" 512 3 3035307 (30, 5) 82.1 s 53.6 s

Conclusion

We have presented new stable geometry estimators for digital data, one approaching the Voronoi Covariance Measure and the other approaching the normal vector field.

We have shown under which conditions they are multigrid convergent and provided formulas to determine their parameters R and r as a function of the gridstep h.

Experiments have confirmed both the accuracy and the stability of our estimators.

In future works, we plan to compare numerically our estimator with other discrete normal estimators (e.g. integral invariants [START_REF] Coeurjolly | Integral based curvature estimators in digital geometry[END_REF], jets [START_REF] Cazals | Estimating differential quantities using polynomial fitting of osculating jets[END_REF]) and also to perform a finer multigrid analysis to get a better theoretical bound on the error. For the last point, one has

∂[S R ∩ p -1 S (B ∩ S)] = A 1 ∪ A 2 , where A 1 = {x ∈ R 3 , x -p S (x) = R and p S (x) ∈ B ∩ S} A 2 = S R ∩ p -1 S (∂(B ∩ S))
Similarly as above, one has

Area(A 1 ) = B∩S (1 -λ 1 (x)R)(1 -λ 2 (x)R)dx ≤ 2Area(B ∩ S) 1 + R ρ 2 ≤ 5Area(B ∩ S). We put C = ∂[B ∩ S].
As for the tube formula, the set A 2 is parametrized by the map

f : C × (-R, R) -→ A 2 (x, t) -→ x + t.n(x)
The 2-jacobian of f at (x, t) is given by 1 -tλ C (x) , where λ C (x) is the curvature of S at x in the direction tangent to C. One has

Area(A 2 ) = C R -R 1 -tλ C (x) dx ≤ Length(C) R -R 1 + |t| ρ dt ≤ 3 R Length(C).
The proofs of items a, b and c follows from the fact that if B is a ball of radius r, then Area(B ∩ S) = O(r 2 ) and Length(C) = O(r).

Stability of the projection on a compact set

Proposition 4. Let S be a surface of R 3 of class C 2 whose reach is greater than ρ > 0. Let K be a compact set such that d H (S, K) = ε < 2ρ, and R < ρ a positive number. If x and x are points of S R such that d(x, x ) ≤ η, then :

p K (x) -p K (x ) ≤ 2 8ερ + 2ε + 1 1 -R ρ η
The proof of the proposition relies on Lemmas 3 and 4. Lemma 3. Let S be a surface of R 3 of class C 2 whose reach is greater than ρ > 0. Let r < ρ and x ∈ R 3 such that d(x, S) = δ < ρ. If q ∈ S satisfies q -p S (x) > r then x -q 2 > δ ρ r 2 + δ 2 . Proof. Since S has a reach greater than ρ, there exists a ball B c (ρ) of center c, that is tangent to S at the point p S (x). The interior of this ball does not intersect S and the points c, x, and p S (x) are aligned. Let q be a point of S such that q -p S (x) = r ≥ r. We denote by P the plane passing through c, x, p S (x) and p. Let y ∈ ∂B c (ρ) ∩ ∂B p S (x) (r) ∩ P. Clearly, p S (x) is at equal distance of q and y. Furthermore, since q / ∈ B c (ρ), c is closer to y than to q, hence the whole segment [c, p S (x)] is closer to y than to q, which implies that x -q ≥ x -y . Since x -y is the length of the diagonal of a regular trapezoid, we have x -y 2 ≥ δ ρ r2 + δ 2 , which allows to conclude.

Lemma 4. Let S be a surface of R 3 with a reach ρ > 0. Let K be a compact set such that d H (S, K) = ε with ε ≤ 2ρ. Let R be a number such that R < ρ. For every x ∈ S R , one has p K (x) ∈ B(p S (x), 8ερ + ε)

Proof. Let x ∈ S R . We denote δ = x -p S (x) . There exists p 0 ∈ K such that p S (x) -p 0 < ε. We then have x -p 0 ≤ x -p S (x) + p S (x) -p 0 ≤ δ + ε, which implies that x -p K (x) ≤ δ + ε. Let now p ∈ K be such that p / ∈ B(p S (x), √ 8ρε + ε). We are going to prove that p = p K (x). We first suppose that δ < ε. The assumption ε ≤ 2ρ implies that 3ε < √ 8ρε + ε and thus p -p S (x) ≥ 3ε. We have

x -p > p -p S (x) -p S (x) -x > 3ε -δ > 2ε ≥ x -p K (x) ,
which ensures that p = p K (x).

We now suppose that δ ε. There exists q ∈ S such that p -p ≤ ε and thus q -p S (x) ≥ √ 8ρε. Lemma 3 therefore implies that x -q 2 > δ ρ × 8ρε + δ 2 . The fact that δ ≥ ε implies that x -q > δ +2ε. We finally get x -p ≥ x -q -ε > δ + ε ≥ x -p K (x) , which ensures that p = p K (x).

Proof (of Proposition 4). By the triangle inequality, we have p K (x) -p K (x ) ≤ p K (x) -p S (x) + p S (x) -p S (x ) + p S (x ) -p K (x ) .

It is well-known that the projection map p S is 1 1-R ρ -Lipschitz in S R (Theorem 4.8 of [START_REF] Federer | Curvature measures[END_REF]). We then have p S (x) -p S (x ) ≤ 1 1-R ρ η. The two other terms are bounded with Lemma 4.

Proof of Proposition 2

As in the proof of the previous lemma, the hypothesis h ≤ ρ 2 and √ 8hρ + h ≤ r imply that p -1 Z h (supp(χ)) ⊂ p -1 ∂X (B y (2r)). We then introduce the common set E = ∂X R-h ∩ p -1 ∂X (B y (2r)), on which we are going to integrate. We have : Furthermore, one has ∂X R ∩ p -1 ∂X (B y (2r)) \ E = ∂X R \∂X R-h ∩ p -1 ∂X (B y (2r)), whose volume is bounded by Proposition 3 by O(r 2 h). Then

V ∂X,R (χ r ) = ∂X R
Err 1 op = χ ∞ × O(R 2 r 2 h).
Similarly, one has Adding the bounds of Err 1 op , Err 2 op and ∆ op , we find the same bound :

V ∂X,R (χ r ) = Z R h (x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x)) = Z R h ∩p -
V ∂X,R (χ r ) -V Z h ,R (χ r ) op = O Lip(χ) × [(r 3 R 5 2 + r 2 R 7 2 + rR 9
2 )h

1 2 ] + χ ∞ × [(r 3 R 3 2 + r 2 R 5 2 + rR 7
2 )h

Fig. 2 :

 2 Fig. 2: Digitisation of the offset and its localisation.

Corollary 1 . 1 4

 11 Let X be a compact domain of R 3 whose boundary ∂X is a C 2 surface with reach ρ > 0. Let a, b ∈ R + , r = ah and R = bh 1 4

Fig. 3 :

 3 Fig. 3: Multigrid convergence of angle error of normal estimator (in degree). Abscissa is the gridstep h. Tests are run on torus shape for three kernel radii (R = r = 3h α for α ∈ { 1 4 , 1 3 , 1 2 }), two norms (l 1 , l ∞ ): (left) kernel ball function χ 0 r , (right) kernel hat function χ 1 r .

1 2 ,

 2 at an almost linear rate O(h), for all norms. More experiments show that the most accurate results are obtained for

  0.25, hat kernel l1 angle error, alpha=0.25 loo angle error, alpha=0.25 l1 angle error, alpha=0.33 loo angle error, alpha=0.33 l1 angle error, alpha=0.5 loo angle error, alpha=0.5 O(h) angle error

Fig. 5 :Fig. 6 :

 56 Fig. 5: Visual result of the normal estimation on the "torus" shape perturbated with a strong Kanungo noise (p = 0.5) for gridsteps from left to right h = 0.5, 0.25, 0.125, 0.0626.

Fig. 7 :Fig. 8 :

 78 Fig. 7: Visual aspect of normal estimation on classical digital data structures: "Al" 150 3 , "Republic cruiser" 250 3 , "Digital snow" 512 3 .

(

  x -p ∂X (x))(x -p ∂X (x)) t χ(p ∂X (x)) = ∂X R ∩p -1 ∂X (By(2r)) (x -p ∂X (x))(x -p ∂X (x)) t χ(p ∂X (x)) = E (x -p ∂X (x))(x -p ∂X (x)) t χ(p ∂X (x)) + Err 1 ,where the error Err 1 satisfiesErr 1 op ≤ R 2 × χ ∞ × Vol(∂X R ∩ p -1 ∂X (B y (2r)) \ E).

Err 2 5 2 + r 2

 252 op = (R + h) 2 × χ ∞ × O(r 2 h).We now have to compare the two integrals on the common setE ∆ = E (x -p ∂X (x))(x -p ∂X (x)) t χ(p ∂X (x)) -(x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x)) .Following now the proof of Theorem 5.1 of[START_REF] Mérigot | Voronoi-based curvature and feature estimation from point clouds[END_REF], one has∆ op ≤ (R 2 Lip(χ)+2R χ ∞ )×[Vol(E)+(diam(E)+R+ √ Rh)×Area(∂E)]× √ Rh.Proposition 3 gives that Vol(E) is bounded by O(r 2 R) and Area(∂E) is bounded by O(rR + r 2 ). We then have∆ op = O Lip(χ) × [(r 3 R

  1 ∂X (By(2r))(x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x)) = E (x -p Z h (x))(x -p Z h (x)) t χ(p Z h (x)) + Err 2 ,where the error Err 2 satisfiesErr 2 op ≤ (R + h) 2 × χ ∞ × Vol(Z R h ∩ p -1 ∂X (B y (2r)) \ E). Since the set Z R h ∩p -1 ∂X (B y (2r))\E ⊂ ∂X R+h \∂X R-h ∩p -1 ∂X (B y (2r)) has a volume bounded by O(r 2 h), one has

Appendix

We give here all the proofs to be self-content. Proposition 3 is classical and follows from the well-known tube formula for smooth surfaces [START_REF] Weyl | On the volume of tubes[END_REF]. We give a complete proof in the sake of completeness. Proposition 4 states that the projection map p K onto a set K that is close to a smooth surface S behaves like the projection map p S . It relies on classical properties of the projection map onto a set with positive reach. The proof of Proposition 2 is similar to the proof of Theorem 5.1 of [START_REF] Mérigot | Voronoi-based curvature and feature estimation from point clouds[END_REF], except that the calculations are done locally.

Hausdorff measure of offsets

Then for any borelian B, one has:

, where the notation O involves a constant that only depends on the reach ρ.

Proof. The proof is based on the tube formula for surfaces of class C 2 [START_REF] Weyl | On the volume of tubes[END_REF][START_REF] Federer | Curvature measures[END_REF]. One has

where λ 1 (x) and λ 2 (x) are the principal curvatures of S at the point x. Now, since |λ 1 (x)| and |λ 2 (x)| are smaller than 1 ρ , one has

The proof of the second item is similar. The volume of (S

The result then follows from the fact that R+ε R-ε