Marcello Leida

Basim Majeed

Maurizio Colombo

Andrej Chu

A Lightweight RDF Data Model for Business Process Analysis

Keywords: business process, ontology, RDF, SPARQL, linked data, real time processing

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Business Process Management (BPM) is increasingly taking a place as a critical area of information technology, helping businesses to leverage their resources for maximum benefit. It has been successfully applied at improving the performance of business processes:

-by automatically extracting process models from existing systems logs, event logs, database transactions, audit trail events or other sources of information [START_REF] Van Der Aalst | Workflow mining: Discovering process models from event logs[END_REF][START_REF] Van Der Aalst | Workflow mining: a survey of issues and approaches[END_REF]; -by allowing instant analysis of the business processes using interactive visual displays of the process workflow; -by identifying specific case characteristics or trends that influence processing times [START_REF] Taylor | Case study in process mining in a multinational enterprise[END_REF].

However, existing BPM systems tend to limit the kind of data they can analyse and rigid on the data model itself. Moreover, most systems offer very limited real-time analysis capabilities. Furthermore, the kind of analysis that can be performed is normally restricted to an inextensible and inflexible set of functions tied to the underlying model, besides others challenges identified by the IEEE Task Force on Process Mining [START_REF] Van Der Aalst | Process mining manifesto[END_REF].

The current technology typically requires the translation or import of data into the system before it can be analysed [START_REF] Van Der Aalst | Workflow mining: Discovering process models from event logs[END_REF][START_REF] Van Der Aalst | Workflow mining: a survey of issues and approaches[END_REF][START_REF] Taylor | Case study in process mining in a multinational enterprise[END_REF]. This imposes severe constraints on the way the data is represented and collected. The main limitation is however imposed by schemas that are neither flexible, nor easily extensible, meaning that new information cannot be easily captured by the system without off line modifications; moreover the high complexity of the model used makes such modification expensive. The scope for analysis and information extraction is hence severely limited.

In order to address these issues, in this article we present a lightweight and flexible business process representation model. Lightweight in the sense that the model presented is a very simple conceptualisation of a business process, that can be extended by domain specific conceptualisations. The model we present in this paper is an extremely reduced set of concepts allowing third party client to perform independent process analysis.

The approach is based on the Resource Description Framework (RDF) [START_REF] Hayes | Resource description framework (rdf)[END_REF] standard that allows independence between the applications generating business process data and those consuming it. The approach is validated by a proof of concept prototype based on a set of SPARQL [START_REF] Prud'hommeaux | Sparql query language for rdf[END_REF] queries that demonstrates that the applications can independently work without the need for exchanging domain specific information about the business process monitored.

The article is structured as follows: Section 2 introduces the actual state of the art; Section 3, the main section of the article, describes the basic data model used in our system and a use case scenario where the basic data model is extended by a process monitoring application with domain specific information. Then, Section 4 demonstrates how an analytical tool can perform specific analysis without previous knowledge of the process by using a set of SPARQL queries. Section 5 focuses on how the schema can be used for real time monitoring applications. Section 6 outlines open challenges that the use of such model can introduce. Finally, Section 7 presents final consideration and future work on this area.

Related Work

There is a very broad literature and commercial production related to business processes and their representation. However, in this section we will limit the scope to the data models that have been defined starting from requirements such as flexibility, extensibility and suitability for real-time analysis.

There are well known languages, such as BPMN 1 and BPEL 2 that are used to explicitly define a process and capture execution information for fully automated 1 http://www.omg.org/spec/BPMN/2.0/ 2 http://docs.oasis-open.org/wsbpel/2.0/OS/wsbpel-v2.0-OS.html systems (e.g. web service orchestration). However in most cases integration of BPEL engines in existing and on-going processes is a non-trivial undertaking and it is often an effort that enterprises prefer to avoid unless a minimum Return of Investment (ROI) is guaranteed. This effort might also be undesirable when the process is not formally captured and exists only in an idealized sense in the mind of the people involved; this is particularly the case for many SMEs.

Therefore, there are many situations where a process model is of very limited use or simply not available: in this case, the process model needs to be inferred from the information generated during its execution, following a bottom-up approach to build the process model from execution data. This is the case of many business process mining tools, such as Aperture [START_REF] Taylor | Case study in process mining in a multinational enterprise[END_REF], ProM [START_REF] Van Der Aalst | Workflow mining: Discovering process models from event logs[END_REF] and Aris [START_REF] Fischer | Aris process performance manager[END_REF].

The data model underpinning Aperture is based on a flexible database model based on the concept ofprocess and task instances, with arbitrary number and type of attributes.

The MXML data format [START_REF] Van Der Aalst | Workflow mining: a survey of issues and approaches[END_REF] and the Extensible Event Stream (XES) standard3 used by ProM and Aris are, as for the Aperture model, general purpose, flexible and extensible business process representations.

However, the main issue with this approach is that they are strongly oriented toward a task-based representation, thus it is extremely difficult to analyse the flow from a different point of view. Moreover these models are based on a tree representation, while our model is based on a graph, which is expressively more powerful.

Ontology-based business process representation has also been defined: in [START_REF] Weber | Semantic business process validation[END_REF], the authors define an ontology for semantically annotate business processes: the work focuses on the web service domain and the outcome is a set of ontologies and tools used to analyse the processes. The ontologies clearly describes the processes, the actors (also as organizations) involved, and all the tasks and constraints composing the processes. The target of this work is to use these ontologies to validate process executions by consistency checking on the processes represented as instances of the ontology.

Another example of business process models defined as ontologies is Web Service Modeling Ontology (WSMO) [START_REF] Roman | Wsmo -web service modeling ontology[END_REF], which has been applied in the field of Web Service composition and execution. The approach is very similar to [START_REF] Weber | Semantic business process validation[END_REF] and provides a set of ontologies to be used for business process validation.

The major issue with both approaches is that the process model is already defined by the ontology and the data is usually related to the concept by a mapping. This is an approach that is valid in case of fully automated processes (such as in a Web Service scenario), processes that can be easily deployed and that generate clean data, because these approaches require the data to be translated into the ontological format (if not generated already in the ontological format).

In our approach we do not define a process-specific ontology, rather the ontology is created dynamically starting from the data generated by process executions. Hence we can potentially represent any process without having to make any change to the data model. This particular situation is the one we plan to challenge with the solution presented in this article: the data model presented is based on the Resource Description Framework (RDF) and is more naturally suited to represent continuously evolving and unpredictable knowledge associated with business processes.

An extensible business process data model

As already reported in Section 2, the main limitation in actual business process analysis tools is the tight connection between the applications that capture the information about the process and the ones that analyse it, mainly due to the rigid data model used. Nowadays we face the need to deal with increasingly complex systems and monitoring tools; that have to be flexible and robust enough to process also information that is not present or unknown at the moment of deployment or system initialization. Next generation Business Intelligence (BI) systems will need to react to real-time events and predict the process behaviour in order to take corrective actions [START_REF] Azvine | Real time business intelligence for the adaptive enterprise[END_REF]. Moreover it is necessary to separate the data creation step from the analytical one in terms of meta-data dependency: departments that execute the processes are mostly unaware of the type of analysis that will be performed and they tend not to communicate small changes in the way and quantity of data they capture [START_REF] Taylor | Case study in process mining in a multinational enterprise[END_REF]. On the other side, also the analytical applications do not need to know how the information is captured, as long as it is made available on time and is compliant to a standard representation. Therefore, the need for a less constraining and less rigid model is arising. To this aim, it is important to use an extensible, flexible and publicly available data model. We identified the Resource Description Framework (RDF) [START_REF] Hayes | Resource description framework (rdf)[END_REF] and RDF Schema (RDFS) [START_REF] Brickley | Rdf vocabulary description language 1.0: Rdf schema[END_REF] as a very elegant way to solve this issue.

RDF is a standard vocabulary definition which is at the basis of the Semantic Web vision, it is composed of three elements: concepts, relations between concepts and attributes of concepts. These elements are modelled as a labelled oriented graph [START_REF] Carroll | Named graphs[END_REF], defined by a set of triples <s,p,o> where s is subject, p is predicate and o is object. Formally a graph G can be defined as:

G ≡ (U ∪ B ∪ L) × U × (U ∪ B ∪ L)
where:

-U is an infinite set of constant values (called URI references) these have their well-defined semantics provided as an example by the RDF and RDFS vocabularies; -B is an infinite set of identifiers (called Blank nodes) which identify instantiation of concepts. Elements in this set do not have a defined semantic; -L is an infinite set of values (called Literals). Elements in this set do not have a defined semantic.

The elements of a triple <s,p,o> are respectively: s ∈ (U ∪ B ∪ L), p ∈ U , and o ∈ (U ∪ B ∪ L). The elements in U represents elements of the schema as in Figure 1, while the elements in B and L are used to represent instances.

An RDF graph is defined by a list of triples and adding new information reduces to append new triples to the list. It is therefore easy to understand why such representation can provide big benefits for real time business process analysis: data can be appended on the fly to the existing one and it will become part of the graph, available for any analytical application, without need for reconfiguration or any other data preparation steps as we will see in Section 5.

RDF is an extremely generic data representation model and it can be used in any domain. The level of flexibility and extensibility offered by the RDF model however requires high computational power in order to query the information in the graph. A system which is able to store and query an RDF graph is called a triple store. It is out of the scope of this article to go in details of the features of a triple store; in order to get a detailed overview the reader should refer to [START_REF] Rohloff | An evaluation of triple-store technologies for large data stores[END_REF] [14] for some comparative surveys. In order to get some comparative measures for query answering times of the main triples stores please refer to [START_REF] Bizer | Berlin sparql benchmark (bsbm). Benchmark[END_REF].

RDF and RDFS standard vocabularies allow external application to query data through SPARQL query language [START_REF] Prud'hommeaux | Sparql query language for rdf[END_REF]. SPARQL is a standard query language for RDF graphs based on conjunctive queries on triple patterns, which identify paths in the RDF graph. SPARQL is supported by most of the triples stores available.

RDF and RDFS provide a basic set of semantics that is used to define concepts, sub-concepts, relations, attributes, and can be extended easily with any domain-specific information. In the specific case of this article, the application domain is related to Business Processes analysis and in order to provide a point of contact for the data generation and analytical applications, it is important to agree on a common vocabulary defining the set of semantics of this domain: a simple representation allowing a high level of flexibility and at the same time providing a set of elements (concepts, relations and attributes) that are meaningful in the business process analysis domain. We identified as the most generic business process the conceptual model represented in Figure 1. The main elements are the concepts: ebtic-bpm:Process that represents the business process and ebtic-bpm:Task, representing the activity that composes the processthe process. They both have a basic set of attributes representing the beginning and termination of an activity: ebtic-bpm:startTime and ebticbpm:endTime. A relation between these two basic concepts defines the simplest way to represent the workflow of a business process execution: ebtic-bpm:hasTask is defined from the ebtic-bpm:Process to the ebtic-bpm:Task concepts and represents the set of tasks belonging to a process. Finally, a set of recursive relations are defined on the ebtic-bpm:Task concept: ebtic-bpm:followedBy, ebticbpm:precededBy and ebtic-bpm:hasSubTask. They respectively indicate which tasks precede and follow a given one and which tasks are subtasks of a given one. The ebtic-bpm:followedBy and ebtic-bpm:precededBy relations are used to build the process workflow while the ebtic-bpm:hasSubTask is useful in order to define stages of execution and to ease the analysis and structural organisation of complex processes. It is important also to underline the fact that the representation of Figure 1 does not contain any data, it provides only a conceptual schema that the process monitoring applications will extend and instantiate as described in Section 3.1.

The conceptual model of Figure 1 can be formalised by a graph G defined by the set of triples in Table 1 4 . The elements in the conceptual model of Figure 1 are defined as a vocabulary EBTIC-BPM that extends the set U which already contains the vocabularies RDF and RDFS. The RDF graph resulting by these triples is displayed in Figure 2: the nodes represents the elements from the (U ∪ B ∪ L), the number of the connections represents the triple identifiers, and the label of connection identifies the triple part: the label SP is the part of the triple connecting subject to object and the PO is the part of the triple connecting predicate to object.

According to Linked Data [START_REF] Bizer | How to publish Linked Data on the Web[END_REF] principles the ebtic-bpm RDF graph will be made available on-line and advertised as a publicly available schema. So that business process data can be published and shared using this representation. This will allow consumer application to be able to process any business process defined according to this extensible schema, as described in Section 4. Fig. 2. The RDF graph resulting by the triples in Table 1.

Extending the EBTIC-BPM vocabulary

The conceptual model defined by the triples in Table 1 is generic and does not provide any domain specific information that can be used for a meaningful business process analysis; this information needs to be provided independently by the applications that monitor the process execution and defined as an extension of the EBTIC-BPM vocabulary. We will not go into the details of this application since it depends on the specific deployment configuration, as an example this application could be deployed on a SOA environment and monitor the message exchange on an Enterprise Service Bus (ESB), it could monitor a set of log files, it could be defined as a trigger in a database and so on. What is relevant is that the information captured by this application has to be interpreted and translated into triples.

The process monitor will act as a bridge between the specific execution environment of the process to monitor and the triple store where the triples will be directed to; in order to make accessible the information to other applications through the SPARQL interface of the triples store as described more in detail in section 3.2.

As an example let us consider the process of building a product A; this product is composed by a set of components that need to be assembled. Once the product is assembled, its correct behaviour is verified by a testing activity. It is possible to capture the semantic of this process by defining a vocabulary Product-A (PA) that enriches the basic process model EBTIC-BPM as represented by the conceptual model in Figure 3. This vocabulary is not a rigid process model definition such as BPML but just the list of attributes, relations and tasks that may appear during the execution of the process.

Modelling the information as an RDF graph allows monitoring applications to provide also an incomplete vocabulary or even not to provide any vocabulary at all during start time, and update it when a new concept, task or an attribute appears during the execution of the process; hence also the process definition is provided on-line. This is an important assumption that allows our approach to adapt to situations where the process is not known a priori and where its behaviour is not predictable or cannot be bounded. Updating the vocabulary in this model is equivalent to appending the related triples to the graph and there is no constraint of any type on when these triples should appear in the graph. As it is also possible to notice from Figure 4, this action is transalted in adding nodes and relations to the graph.

The domain specific vocabulary is composed by a set of concepts, relations and attributes:

-pa:CreateProductA: this concept extends the concept ebtic-bpm:Process using the rdfs:subClassOf relation and its semantic indicates the type of process (creation of a product of type A). This concept has a domain specific attribute pa:department which represents the identifier of the department that executed the process. -pa:Employee: this concept represents the employee which performs the test of the final product. This concept has an attribute pa:EIN which represents the identification number of the employee. 2.

This domain specific information is used to extend the basic process model by appending the triples in Table 2 to the ones present in the triple store (the triples in Table 1 that will be present after the bootstrap procedure). Figure 4 shows the complete RDF graph resulting by the union of the triples in Table 1 and in Table 2.

Architecture of a sample deployment

A typical deployment of a system based on the data model described so far is represented in Figure 5. One or more process monitor is deployed as a non invasive application and used to monitor the process activity; non invasive means that the deployment of the process monitor will require none or very limited change in the existing system. The process monitor creates and maintains the extension of the EBTIC-BPM vocabulary while capturing process execution data: this extension need to be present in the triple store as well as the EBTIC-BPM vocabulary: it can be provided during system bootstrap procedure or created on the fly, by the process monitor itself by analysing the process execution data, and submitted gradually to the triple store. When the process monitor intercept process activity information, it creates the triples representing such activity and continuously sends the triples to a message queue (for example Apache ActiveMQ5 ). A message listener continuously receives the triples sent to the message queue by the various process monitors and inserts the triples into the triple store. The triple store exposes a SPARQL query service allowing external applications to query the continuously updated process execution graph.

As discussed, the monitoring application is responsible of creating the extensions of the EBTIC-BPM vocabulary and once a process instance is executing, the process monitor captures this information and creates the corresponding triples to be sent to the triple store.

For the sake of simplicity we will not consider in this paper named graphs or contexts of a triple. We assume the triples created by the process monitors will contribute to compose the same RDF graph. We will demonstrate that even without the use of contexts we can distinguish between different process models in the same graph. Introducing named graphs or contexts will add separation between RDF graphs, but the approach described is still valid.

In this deployment, the process monitoring application generates a flow of triples representing the process activity. The logic used to translate process activity into triples is contained in the Process Monitor and it varies depending on the process. Imagine a log file continuously updated by a workflow management system containing process activity as the on in Table 3.

Every line in the log represent a process activity; every time a line is added to the log, the process monitor will analyse the line and crate the respective triples. The final list of triples representing the log execution of Table 3 is reported in Table 4. Figure 6 shows the complete RDF graph containing all the nodes and connections representing the execution of a process; as it is possible to notice, already with only one process execution the graph starts to become complex.

Once the triples are present in the triple store, it will be possible for other applications such as business process mining or monitoring applications to extract and analyse business process information through the SPARQL interface.

The EBTIC-BPM vocabulary introduced in section 3 provides a generic business process domain vocabulary that allows to define SPARQL queries to be used for data discovery process, but it is necessary to ensure that the concepts, relations and attributes in Figure 1 are always present in the graph when the process monitors become operative. Therefore we assume that the system will be initialised by a bootstrap procedure that will insert the triples of Table 1 in the triple store.

A SPARQL-based discovery process

As a proof of concept application we developed a business process visualisation tool, which is based on a set of predefined SPARQL queries defined with the assumption that the EBTIC-BPM vocabulary is present in the graph. Hence the queries are independent with respect to the domain specific information of the process to analyse. This application connects to a SPARQL endpoint and is used to display business process flows under different point of views. It has been developed from a set of recurrent requirements gathered with the experience our team developed from down-streaming of the business process mining tool [START_REF] Taylor | Case study in process mining in a multinational enterprise[END_REF]. These requirements were focused on a more flexible visualisation of the process workflow and the possibility to monitor real time process executions. The use of the data model described in this article allows to fulfil both requirements successfully. This tool will initially display the list of domain specific processes that are available in the triple store, which the user can select and obtain the instances of that process, inspect their attributes, and list of tasks with their attributes, related concepts, and subtasks. Also by clicking on a process instance the application will display the workflow diagram of the selected instance of execution. All the interactions of the user with the application are translated into SPARQL queries that are submitted to the triple store. This application processes the results and presents them to the user according to the selected action. These SPARQL queries are defined only with knowledge of EBTIC-BPM vocabulary, but we will now demonstrate that the tool can visualise and make use of domain specific information without prior knowledge of it.

Once the application is started, a set of SPARQL queries is executed in order to obtain some information about the processes that are present in the store; the following query:

SELECT ?process (1)
WHERE { ?process rdfs:subClassOf ebtic-bpm:Process.} returns the concepts that extend the ebtic-bpm:Process concept. Each of these concepts represents a different process type that is present in the RDF graph, in case of the current example the results in the variable ?process will contain pa:CreateProductA. The results of this query will be displayed in a list (area 1 in Figure 7) and the user will be able to select which type of processes to analyse. Once the user selects an entry in the process list, a second query will be executed:

SELECT ?processID ?startTime ?endTime

WHERE { ?processID rdf:type pa:CreateProductA.

?processID ebtic-bpm:startTime ?startTime.

OPTIONAL { ?processID ebtic-bpm:endTime ?endTime.}} this query returns information (?processID ?startTime ?endTime) about the instances of the process pa:CreateProductA, in case the user selected such process from the list populated with the results of the previous query. In case the user did not select any specific process type then the query that will be submitted will be slightly different:

SELECT ?processID ?startTime ?endTime

WHERE { ?processID rdf:type ?process.

?process rdfs:subClassOf ebtic-bpm:Process.

?processID ebtic-bpm:startTime ?startTime.

OPTIONAL { ?processID ebtic-bpm:endTime ?endTime.}} this modified version combines the query 1, used to retrieve the concepts extending the basic process concept and the query 2 which is used to retrieve the instances of a specific process concept, thus the query will return information about all the process instances that are present in the graph; the query 3 can be slightly simplified in case the triple store supports RDFS inference. The results of this second query will be used to populate a table in the graphical interface of the application (area 2 in Figure 7), where the user will be able to see the list of instances of the selected process (pa:CreateProductA in this case). The OPTIONAL keyword indicates that the ending time of a process may not be present, in case the process is still executing (as it is possible to notice in the last row of the table in area 2 in Figure 7). In case OPTIONAL is not present the results will contain only process instances that have terminated.

At this point the user, by interacting with this list can select one process instance, as an example pa:01; this action will fire another query:

SELECT ?attribute ?value (4)
WHERE { pa:01 ?attribute ?value.

FILTER (?attribute != rdf:type)} which will populate another table with the names and values of all the attributes of the selected process and the list of its tasks (area 3 in Figure 7).

It is important to stress on the fact that also in this case the query will return all the process attributes and tasks of that specific process execution, without any knowledge of the process meta-data. The FILTER keyword is used to remove the attributes of type rdf:type from the results if they are not meaningful for the final user. The use of pa:01 in the first triple pattern is used to ensure that the results returned are relevant to the selected process instance.

The user can now select a row in the resulting table, this action will execute the query 4 modified by replacing the pa:01 element with the value of the row selected by the user. In case the value represents a task instance, the results of this query will populate a table with the names and the values of all the attributes of the selected task (area 4 in Figure 7)

A more interesting behaviour occurs when the user double clicks on one process instance to obtain the process workflow. This action will be converted by the application into the following SPARQL query: SELECT ?PID ?startTime ?endTime ?taskID

?taskType ?follBy ?precBy WHERE { ?PID ebtic-bpm:hasTask ?taskID.

?taskID rdf:type ?taskType.

?PID ebtic-bpm:startTime ?startTime.

OPTIONAL {?PID ebtic-bpm:endTime ?endTime.}.

OPTIONAL { ?taskID ebtic-bpm:followedBy ?follBy.}.

OPTIONAL { ?taskID ebtic-bpm:precededBy ?precBy.}.

FILTER (?PID = pa:01)}

where pa:01 is the selected process instance. The output of query 5, in case the RDF graph contains the triples of Table 1, 2 and 4 is reported in Table 5 Table 5. A sample result set from the execution of query 5. The result of this query is processed by a method that returns a graphical representation of the process built using the information in the ?followedBy and ?precededBy variables. The method generates a standard GraphML [START_REF] Brandes | Graphml progress report, structural layer proposal[END_REF] document that can be consumed by any graphical library supporting such standard (Jung6 , yFiles7 , jsPlumb8 , D39 just to cite few of them). The output will be returned to the user in a new window as in the example of Figure 8. Our tool makes use of the yFiles library to display the GraphML document. All the workflow diagrams presented in this paper has been generated by our tool; in the figures the window frame has been cropped out.

The process workflow in Figure 8 is an interactive object that the user can manipulate: as an example switching the task-based view by selecting alternative ways to present the process. This can be done at process or task level.

Process level view interaction

This aspect refers to the interaction of the user with the graphical representation of the global process workflow. The right click of the user on any point of the window (which is not a task), is translated in a query that is used to retrieve all the attributes and objects related to all the tasks present in the workflow. This is an important feature of this approach because it ensures that the user will only be able to choose between task attributes that are present in the process instance the user is interacting with. This is encoded in the following query:

SELECT DISTINCT ?attribute (6)
WHERE { pa:01 ebtic-bpm:hasTask ?taskID.

?taskID rdf:type ?Task.

?Task rdfs:subClassOf ebtic-bpm:Task.

?Task rdfs:domain ?attribute.}

The results of this query will populate a box where the user can select an element that will be used to switch the process workflow from a task-based representation to an attribute-based representation, according to the attribute selected. In case of process level view interaction, if the selected attribute is not present in a task the usual task-based representation will be used for that task.

This behaviour is automatically encoded in the query that will be fired once the user selects an attribute from the pop-up list. The query is similar to the pre-vious one, with one additional variable ?alternativeName that will be used to replace the task name in case the attribute used to switch the workflow is present in the task. For example, if the user selects the element pa:createComponent from the pop up list; the SPARQL query that will be execute will be:

SELECT ?PID ?startTime ?endTime ?taskID

?taskType ?follBy ?precBy ?altName WHERE { ?PID ebtic-bpm:hasTask ?taskID.

?taskID rdf:type ?taskType.

?PID ebtic-bpm:startTime ?startTime.

OPTIONAL {?PID ebtic-bpm:endTime ?endTime.}.

OPTIONAL { ?taskID ebtic-bpm:followedBy ?follBy.}.

OPTIONAL { ?taskID ebtic-bpm:precededBy ?precBy.}.

OPTIONAL { ?taskID pa:createComponent ?altName.}.

FILTER (?PID = pa:01)}

The difference with query 5 is that there is an additional optional triple pattern created using the attribute selected by the user (pa:createComponent in this case) linked to the task instance (by the ?taskID variable). This additional pattern will bind the results to the ?alternativeName variable in case the path in the RDF graph exists.

The output of query 7, in case the RDF graph contains the triples of Table 1, 2 and 4 is reported in Table 6. Table 6. A sample result set from the execution of query 5.

PID startTime endTime taskID taskType follBy precBy altName pa:01 2012-03-14T07:... 2012-03-14T07:... pa:0045 pa:Assemble pa:0046 pa:0098 pa:01 2012-03-14T07:... 2012-03-14T07:... pa:0046 pa:Assemble pa:0047 pa:0045 pa:0099 pa:01 2012-03-14T07:... 2012-03-14T07:... pa:0047 pa:Assemble pa:0048 pa:0046 pa:0099 pa:01 2012-03-14T07:... 2012-03-14T07:... pa:0048 pa:Test pa:0049 pa:0047 pa:01 2012-03-14T07:... 2012-03-14T07:... pa:0049 pa:Assemble pa:0056 pa:0048 pa:0099 pa:01 2012-03-14T07:... 2012-03-14T07:... pa:0056 pa:Test pa:0049

The results will be processed to create the GraphML document representing the workflow in Figure 9. The algorithm used to generate the GraphML document will use the value in ?alternativeName, if present, to represents the task name, using also a different colour to fill the element in the workflow.

Task level view interaction

This second aspect refers to the recursive interaction of the user with single task type attributes in order to modify the graphical representation of the process workflow.

Imagine a situation for which the user is interested in a certain attribute of a specific task type and another attribute of another task type. The user, by right clicking on a task, will fire a query very similar to query 6 which will be used to retrieve all the attributes and objects related to that specific task. This is done by replacing the variable ?Task in the query with the specific task (pa:createComponent), consequently narrowing the set of results.

These results are used to populate a pop-up box as, described above, and the user can select an attribute that will be used to replace the traditional task-based representation for that specific task.

The action of clicking on an attribute will be translated to a query conceptually similar to query 7, with the difference that this time we need to make wide use of the UNION construct in order to compose the results of different queries: one query that will be focused on the alternative value referred to the task selected by the user, while a second query that will take care of the tasks that are not of the type selected by the user, which will be displayed with the traditional task-based view. This behaviour is defined by the following query:

SELECT ?PID ?startTime ?endTime ?taskID

?taskType ?follBy ?precBy ?altName WHERE {{ ?PID ebtic-bpm:hasTask ?taskID.

?taskID rdf:type ?taskType.

?PID ebtic-bpm:startTime ?startTime.

OPTIONAL {?PID ebtic-bpm:endTime ?endTime.}.

OPTIONAL { ?taskID ebtic-bpm:followedBy ?follBy.}.

OPTIONAL { ?taskID ebtic-bpm:precededBy ?precBy.}.

OPTIONAL { ?taskID pa:createComponent ?altName.}.

FILTER (?PID = pa:01 && ?taskType = pa:Assemble)} UNION { ?PID ebtic-bpm:hasTask ?taskID.

?taskID rdf:type ?taskType.

?PID ebtic-bpm:startTime ?startTime.

OPTIONAL {?PID ebtic-bpm:endTime ?endTime.}.

OPTIONAL { ?taskID ebtic-bpm:followedBy ?follBy.}.

OPTIONAL { ?taskID ebtic-bpm:precededBy ?precBy.}.

FILTER (?PID = pa:01 && ?taskType != pa:Assemble)}}

This action can be iteratively repeated by the user for every task type present in the workflow diagram, so that each different task type can be represented using a different attribute.

The actions of the user are translated into additional queries that are connected to the one defined so far by the UNION keyword as shown in query 9.

SELECT ?PID ?startTime ?endTime ?taskID

?taskType ?follBy ?precBy ?altName WHERE {{ ?PID ebtic-bpm:hasTask ?taskID.

?taskID rdf:type ?taskType.

?PID ebtic-bpm:startTime ?startTime.

OPTIONAL {?PID ebtic-bpm:endTime ?endTime.}.

OPTIONAL { ?taskID ebtic-bpm:followedBy ?follBy.}.

OPTIONAL { ?taskID ebtic-bpm:precededBy ?precBy.}.

OPTIONAL { ?taskID pa:createComponent ?altName.}.

FILTER (?PID = pa:01 && ?taskType = pa:Assemble)} UNION { ?PID ebtic-bpm:hasTask ?taskID.

?taskID rdf:type ?taskType.

?PID ebtic-bpm:startTime ?startTime.

OPTIONAL {?PID ebtic-bpm:endTime ?endTime.}.

OPTIONAL { ?taskID ebtic-bpm:followedBy ?follBy.}.

OPTIONAL { ?taskID ebtic-bpm:precededBy ?precBy.}.

OPTIONAL { ?taskID pa:executedBy ?altName.}.

FILTER (?PID = pa:01 && ?taskType = pa:Test)} UNION { ?PID ebtic-bpm:hasTask ?taskID.

?taskID rdf:type ?taskType.

?PID ebtic-bpm:startTime ?startTime.

OPTIONAL {?PID ebtic-bpm:endTime ?endTime.}.

OPTIONAL { ?taskID ebtic-bpm:followedBy ?follBy.}.

OPTIONAL { ?taskID ebtic-bpm:precededBy ?precBy.}.

FILTER (?PID = pa:01 && ?taskType != pa:Assemble && ?taskType != pa:Test)}}

The output of query 9, in case the RDF graph contains the triples of Table 1, 2 and 4 is reported in Table 7.

The results will be processed to create the GraphML document representing the workflow in Figure 10.

Table 7. A sample result set from the execution of query 6.

PID startTime endTime taskID taskType follBy precBy altName pa:01 2012-03-14T03:... 2012-03-14T07:... pa:0045 pa:Assemble pa:0046 pa:0098 pa:01 2012-03-14T03:... 2012-03-14T07:... pa:0046 pa:Assemble pa:0047 pa:0045 pa:0099 pa:01 2012-03-14T03:... 2012-03-14T07:... pa:0047 pa:Assemble pa:0048 pa:0046 pa:0099 pa:01 2012-03-14T03:... 2012-03-14T07:... pa:0049 pa:Assemble pa:0056 pa:0048 pa:0099 pa:01 2012-03-14T03:... 2012-03-14T07:... pa:0048 pa:Test pa:0049 pa:0047 pa:00129 pa:01 2012-03-14T03:... 2012-03-14T07:... pa:0056 pa:Test pa:0049 pa:00129

This set of queries demonstrates how the visualiser application is able to extract and make use of domain specific information to create useful user in- terfaces and rich process workflows, by automatically creating SPARQL queries with only the initial knowledge of the EBTIC-BPM vocabulary. As previously pointed out this vocabulary is the basic set of information shared between applications that monitor business process execution and submit the triples to the triple store, and the applications that make use of such information.

Real time aspects

Another important aspect of the business process model presented in this article is the possibility to continuously add information to the graph. This is an important feature of RDF representation, enabled by the fact that every triple is a valid RDF piece of information that identify nodes and connections in the RDf graph. Another important feature of RDF is that both schema and instance-level information is stored in the same graph and that a SPARQL query can return any point in the graph.

Answering queries in SPARQL can be simply translated into identifying all the paths in the graph that satisfy the query pattern. Hence, continuously adding nodes and connection to the graph generates new paths in the graph that can match queries previously executed.

EBTIC 10 developed a triple store that allows client applications to register queries, so that the client is notified with a new result whenever there is data inserted in the system closing a path that satisfies the registered query. In case the triple store does not support such a feature, a timer can be defined and the queries to monitor can be executed continuously providing the difference between the results at time t and t-1 to the client.

The queries that have been presented in the previous section can be registered in the triple store as continuous queries and the application will be notified with every new result. Assuming that the process monitor will continuously intercept process execution data and translate it into triples, the visualisation application is able to monitor the processes in real-time.

Open Problems

One of the major issues that at the moment prevents us from obtaining a fully flexible solution to business process discovery with absolute transparency between process monitors and the graph, is the assumption that all the process monitors operating on the same extended process model (for example the one defined in Section 3.1) need to agree on the process model specific vocabulary and they are not allowed to modify it without mutual agreement with all the other process monitors. This is a requirement we have to impose at the moment, but in future the idea is that every process model is independent and that they can freely modify the process model vocabulary. The RDF graph ideally will automatically adapt and modify the incoming triples in order to adapt to the evolved model. However this is an open problem that will require further research in the field of collaborative ontology evolution.

Conclusions

In this article we presented an extremely extensible and flexible data representation model oriented towards real time business process monitoring and discovering; the model is based on Resource Description Framework (RDF) standard that allows independence between applications that generate business process data and applications that consume it. The process is represented as a labelled oriented graph defined by a set of triples as defined in Section 3.

Applications that monitor business processes will extend this basic set of information with their domain specific one at run-time by entering the corresponding triples in the triple store.

We finally demonstrated that this approach allows process discovery and analysis of domain specific extensions that may also be created at run time by third party applications just with the use of SPARQL queries. Future work on this direction will be to develop a set of non-invasive monitoring and analytical applications that will allow us to deploy and test this approach within an enterprise-scale environment.

Fig. 1 .

 1 Fig. 1. The conceptual model representing the basic business process representation.

  :hasTask rdfs:range ebtic-bpm:Task ebtic-bpm:hasTask rdfs:domain ebtic-bpm:Process ebtic-bpm:precededBy rdfs:domain ebtic-bpm:Task ebtic-bpm:precededBy rdfs:range ebtic-bpm:Task ebtic-bpm:followedBy rdfs:domain ebtic-bpm:Task ebtic-bpm:followedBy rdfs:range ebtic-bpm:Task ebtic-bpm:hasSubTask rdfs:domain ebtic-bpm:Task ebtic-bpm:hasSubTask rdfs:range ebtic-bpm:Task ebtic-bpm:endTime rdfs:range xs:dateTime ebtic-bpm:endTime rdfs:domain ebtic-bpm:Process ebtic-bpm:endTime rdfs:domain ebtic-bpm:Task ebtic-bpm:startTime rdfs:range xs:dateTime ebtic-bpm:startTime rdfs:domain ebtic-bpm:Task ebtic-bpm:startTime rdfs:domain ebtic-bpm:Process

Fig. 3 .

 3 Fig. 3. The EBTIC-BPM conceptual model extended with domain specific concepts.

  -pa:Assemble: this concept extends the concept ebtic-bpm:Task (with the rdfs:subClassOf relation) and represents the activity of assembling a set of components (indicated by the relation pa:useComponent) into a new component (represented by the relation pa:createComponent). -pa:Component: this concept represents the component that is used/created by the assembling task. This concept has an attribute pa:serialNumber which indicates the serial number of the component. -pa:Test: this concept extends the concept ebtic-bpm:Task and represents the activity of testing the final component (indicated by the pa:testedComponent relation). As represented by the pa:executedBy relation, this activity is carried out by an employee.

Fig. 4 .

 4 Fig. 4. The RDF graph resulting by adding to the existing graph the the triples in Table2.

Fig. 5 .Table 3 .

 53 Fig. 5. A typical deployment of the system.

Fig. 7 .

 7 Fig. 7. The main interface of the business process visualisation tool.

  PID startTime endTime taskID taskType follBy precBy pa:01 2012-03-14T03:18:56+04:00 2012-03-14T07:15:26+04:00 pa:0045 pa:Assemble pa:0046 pa:01 2012-03-14T03:18:56+04:00 2012-03-14T07:15:26+04:00 pa:0046 pa:Assemble pa:0047 pa:0045 pa:01 2012-03-14T03:18:56+04:00 2012-03-14T07:15:26+04:00 pa:0047 pa:Assemble pa:0048 pa:0046 pa:01 2012-03-14T03:18:56+04:00 2012-03-14T07:15:26+04:00 pa:0048 pa:Test pa:0049 pa:0047 pa:01 2012-03-14T03:18:56+04:00 2012-03-14T07:15:26+04:00 pa:0049 pa:Assemble pa:0056 pa:0048 pa:01 2012-03-14T03:18:56+04:00 2012-03-14T07:15:26+04:00 pa:0056 pa:Test pa:0049

Fig. 8 .

 8 Fig. 8. The process workflow of a process instance.

Fig. 9 .

 9 Fig. 9. The process workflow using switched view by the id of the component created by the task.

Fig. 10 .

 10 Fig. 10. The process workflow using switched view by used component.

Table 1 .

 1 The list of triples that defines the basic Business process representation with elements from EBTIC-BPM vocabulary.

Table 2 .

 2 The list of triples that extends the EBTIC-BPM vocabulary with domain specific information.

	s	p	o
	pa:CreateProductA rdfs:subClassOf ebtic-bpm:Process
	pa:Assemble	rdfs:subClassOf ebtic-bpm:Task
	pa:Test	rdfs:subClassOf ebtic-bpm:Task
	pa:Assemble	rdfs:domain	pa:useComponent
	pa:useComponent	rdfs:range	pa:Component
	pa:Assemble	rdfs:domain pa:createComponent
	pa:createComponent	rdfs:range	pa:Component
	pa:Test	rdfs:domain pa:testedComponent
	pa:testedComponent	rdfs:range	pa:Component
	pa:Test	rdfs:domain	pa:executedBy
	pa:executedBy	rdfs:range	pa:Employee
	pa:CreateProductA	rdfs:domain	pa:department
	pa:department	rdfs:range	xs:String
	pa:Component	rdfs:domain	pa:serialNumber
	pa:serialNumber	rdfs:range	xs:Integer
	pa:Employee	rdfs:domain	pa:EIN
	pa:EIN	rdfs:range	xs:Integer

Table 4 .

 4 The triples defining one instance of execution of a process, as created by a monitoring application.

	s	p	o
	pa:01	rdf:type	pa:CreateProductA
	pa:01	pa:department

Fig.

6

. The RDF graph resulting by the union of the triples of Table

1

, 2 and 4.

http://www.xes-standard.org/

The elements with xs: preamble are part of the XML Schema vocabulary (http: //www.w3.org/XML/Schema).

http://activemq.apache.org/

http://jung.sourceforge.net/

http://www.yworks.com/en/products_yfiles_about.html

http://jsplumb.org

http://d3js.org/

http://www.ebtic.org

DBX"^^xsd:string pa:01 ebtic-bpm:startTime 2012-03-14T03:18:56+04:00"^^xsd:date pa:0045 rdf:type pa:Assemble pa:0045 ebtic-bpm:startTime 2012-03-14T03:18:56+04:00"^^xsd:date pa:0098 rdf:type pa:Component pa:0098 pa:serialNumber 23442"^^xsd:integer pa:0045 pa:createComponent pa:0098 pa:0045 2012-03-14T03:55:46+04:00"^^xsd:date pa:01 ebtic-bpm:hasTask pa:0045 pa:0045 ebtic-bpm:followedBy pa:0046 pa:0046 ebtic-bpm:followedBy pa:0047 pa:0047 ebtic-bpm:precededBy pa:0046 pa:0056 ebtic-bpm:precededBy pa:0049 pa:0046 rdf:type pa:Assemble pa:0046 ebtic-bpm:startTime 2012-03-14T04:01:56+04:00"^^xsd:date pa:0099 rdf:type pa:Component pa:0099 pa:serialNumber 21232"^^xsd:integer pa:0046 pa:useComponent pa:0098 pa:0046 pa:createComponent pa:0099 pa:0046 ebtic-bpm:endTime 2012-03-14T04:15:06+04:00"^^xsd:date pa:0047 rdf:type pa:Assemble pa:01 ebtic-bpm:hasTask pa:0046 pa:0047 ebtic-bpm:startTime 2012-03-14T04:18:56+04:00"^^xsd:date pa:0047 pa:useComponent pa:0099 pa:0048 ebtic-bpm:precededBy pa:0047 pa:0047 ebtic-bpm:followedBy pa:0048 pa:0048 ebtic-bpm:followedBy pa:0049 pa:0049 ebtic-bpm:followedBy pa:0056 pa:0046 ebtic-bpm:precededBy pa:0045 pa:0049 ebtic-bpm:precededBy pa:0048 pa:0047 pa:createComponent pa:0099 pa:0047 ebtic-bpm:endTime 2012-03-14T04:55:26+04:00"^^xsd:date pa:0048 rdf:type pa:Test pa:01 ebtic-bpm:hasTask pa:0049 pa:0048 ebtic-bpm:startTime 2012-03-14T04:56:58+04:00"^^xsd:date pa:0048 pa:testedComponent pa:0099 pa:00129 rdf:type pa:Employee pa:00129 pa:EIN 760506653"^^xsd:integer pa:0048 pa:executedBy pa:00129 pa:0048 ebtic-bpm:endTime 2012-03-14T05:15:16+04:00"^^xsd:date pa:0049 rdf:type pa:Assemble pa:01 ebtic-bpm:hasTask pa:0047 pa:0049 ebtic-bpm:startTime 2012-03-14T06:18:56+04:00"^^xsd:date pa:0049 pa:useComponent pa:0099 pa:0049 pa:createComponent pa:0099 pa:0049 ebtic-bpm:endTime 2012-03-14T06:55:26+04:00"^^xsd:date pa:0056 rdf:type pa:Test pa:01 ebtic-bpm:hasTask pa:0048 pa:0056 ebtic-bpm:startTime 2012-03-14T06:58:25+04:00"^^xsd:date pa:0056 pa:testedComponent pa:0099 pa:0056 pa:executedBy pa:00129 pa:01 ebtic-bpm:hasTask pa:0056 pa:0056 ebtic-bpm:endTime 2012-03-14T07:15:26+04:00"^^xsd:date pa:01 ebtic-bpm:endTime 2012-03-14T07:15:26+04:00"^^xsd:date


A Milliez

† M Guay

M.-P Cani

M Gross

R W Sumner

Programmable Animation Texturing using Motion Stamps

: Our system provides a modular framework for authoring stylistic enhancements on complex animations such as fluids (left) or cloth (right). All or parts of the animation can be selected for stylization. The selected points are clustered and tracked over time. A stylization engine instantiates parameterized animations for each cluster, such as the fish and butterflies shown here that spawn when water is lifted off or when wrinkles form.

Introduction

The appearance of 3D surfaces can be controlled with 2D images through the well-known process of texture mapping. Local 2D parametrizations of a three dimensional object are packed in a UV map and exposed to artists, who can use digital painting tools to give a flat description of the appearance of the 3D model. Texture † e-mail:antoine@disneyresearch.com images can encode information such as color, normal perturbations, or material parameters. At render time, programmable shaders let users define the fragment colors of the rendered image as a function of the surface geometry and of its texture-mapped parameters. Texture mapping is especially powerful for locally repetitive surface appearance, where a pattern element can be defined once in texture space, and replicated over a surface through a carefully crafted UV map.

In the context of 3D animation, a wide range of tools of various complexity give artists fine control over the shape of a character, its animation and its appearance, letting them craft complex animations. However, stylizing animations with locally repetitive animated elements remains a tedious task. In particular, while modern simulation systems for fluids and cloth achieve a high degree of physical realism and deliver results that are often indistinguishable from reality, the creative vision for a computer animated film may call for a more stylized look. While some variations, such as the degree of turbulence in a fluid simulation or the apparent weight of a garment's fabric, are easily achieved through simulation parameter tuning, more dramatic art direction cannot be accommodated by changing simulation parameters. For example, the creative vision for an animated film may call for portions of a fluid simulation to be enhanced with an animated mesh that evolves over time as the fluid moves, or for the wrinkles in a cloth simulation to exhibit life of their own by spawning individual animated elements that are coherent with the evolving wrinkle patterns.

These highly art-directed effects call for animated elements that move and deform in a particular way based on the desired look, and existing tools are not designed to incorporate such animations into complex animations in a coherent and unified way. The complexity of the rich motion created by simulation systems makes this coherent stylistic adjustment a highly cumbersome task. As a result, animators must either abandon desired art-directed enhancements or, when budget allows, invest the laborious effort needed for specialized one-off effects.

Inspired by texture mapping, our work targets art-directed stylistic enhancements to complex animations using a novel algorithm for spatio-temporal clustering, and a programmable framework for animation instancing. Since complex animations such as simulations often deliver unstructured data that is independent from frame to frame, we apply our clustering algorithm to impose structure and temporal coherence on the selected points. Clusters are tracked over time and dynamically added and removed as the animation evolves. They provide information about the local behavior of the underlying animation, in analogy to UV maps that provide information about the local geometry of the underlying surface.

Finally, each cluster is used as input to a stylization engine that instantiates parameterized animation components called motion stamps. Each motion stamp represents a parameterized animated scene that can have geometry, motion, and other parametric variations. Our system connects parameter values associated with the clusters, such as position, size, velocity, or other feature values, to the motion stamp parameters so that the stamp animations are directly parameterized by the animation that should be textured. This concept is analogous to fragment shaders, that let users define fragment colors depending on the input geometry parameters. Taken together, this framework provides a flexible procedure for animators to texture animations with custom, art-directed content. Examples of our method used to enhance a fluid and a cloth simulations are shown in Figure 1.

Our main contribution is a modular framework for authoring stylistic enhancements of complex animations such as fluids and cloth. On a technical level, we contribute an artistically motivated spatio-temporal clustering method to establish coherence over time, and a parameterized instancing component based on the feature val-ues. We demonstrate our system with several examples, including a water simulation that is represented by swimming fish and erupts into a flock of birds when different components of the fluid splash together and a wrinkle pattern on cloth whose high curvature values lead to butterflies that spawn and fly away.

Related work

Adding realistic details to simulations. A large body of work has focused on adding realistic details to existing simulations. A strategy in fluid simulations is to enhance a coarse velocity field with higher resolution sub-scale turbulence. Different sub-grid models of turbulence were introduced to computer graphics [KTJG08, SB08, PTC * 10, NSCL08], modeling the transfer from coarse fluid velocity to fine scale turbulence. Other methods focus on specialized procedural techniques for generating spray, droplets and foam on height-field [MY97, CM10] and 3D particle-based simulations [OCv13,IAAT12]. These methods have succeeded at increasing the realistic details of a fluid simulation, but do not accommodate expressive and artistic styles of motion. Similarly, in cloth simulation, many works seek to upscale a coarse simulation with detailed wrinkles either procedurally [HBVMT99,KWH04,RPC * 10], using data-driven techniques [dASTH10, WHRO10, KGBS11, ZBO13], or through explicit user direction [BMWG07] . These methods are compatible with our work, as we can offer animated stylistic enhancements on top of the simulation output to achieve particular artistic effects.

Gross control of simulation shape. Other work enhances the art-directability of simulations by focusing on gross control over the shape of the simulation itself. Research in this area allows artists to direct simulations of smoke [TMPS03, SY05], liquids [TKPR06, RTWT12], clouds [START_REF] Dobashi | Feedback control of cumuliform cloud formation based on computational fluid dynamics[END_REF], cloth [START_REF] Wojtan | Keyframe control of complex particle systems using the adjoint method[END_REF], or elastic solids [MTGG11, STC * 12] to take on particular shapes, such as a cow made of smoke or a horse made of water. Rather than enforcing these large modifications of the shape of the simulation, our work aims to enhance simulations with animations that target specific art-directed effects. By focusing on a modular pipeline based on feature detection, our system can support a variety of enhancements that connect fluid features to animation instances.

Stylizing fluids with 2D exemplars. One technique to enhance fluids is to use 2D texture patches along the velocity field [Ney03, SMC04, BBRF14, JFA * 15]. Texture advection [Ney03] consists in transporting the UV coordinates the texture, while limiting the distortion of the UVs over time as much as possible. An alternative is to consider small individual stencils as particles and splat them to produce the final look-as is done for cartoon smoke in [SMC04]. Similar in spirit to our work, they improve the coherence over time of the stylization by modulating the stencils based on particle properties. Recent techniques reduce the distortion with a synthesis process based on self-similarity when blending between textures [BBRF14, JFA * 15]. While these methods allow creating impressive looks, they are focused on 2D texture exemplars while we target 3D stylistic enhancements and provide a general framework that supports both fluids and cloth. Additionally, the internal motion of the texture example is entirely guided by the texture synthesis optimization routine and the fluid velocity. In contrast, our programmable framework allows our motion stamps to vary according to other features such as the radius of the cluster. Dynamic texture synthesis. One way of facilitating the process of stylizing an animation with potentially non-realistic animations is to extend texture synthesis to the dynamic case. The basic idea is to repeat a pattern over a domain following principles of coherence and causality. Traditional 2D texture synthesis methods have been extended to the 3D domain with 3D mesh texture elements [START_REF] Ma | Discrete element textures[END_REF] and then to the temporal domain [START_REF] Ma | Dynamic element textures[END_REF]. Given a user-provided exemplar and an animated domain to texture (a 2D surface or a set of 1D strands), their goal is to automatically cover the domain with the exemplar while ensuring coherence in both the spatial and temporal dimensions. It is unclear how to adapt their example-based structural similarity to topologically varying domains such as liquids. In contrast, our method can synthesize coherent trajectories over topologically varying domains and provides artistic control over the instantiation in time. One of the core differences with our work is that these techniques are designed to track grouped points over time, while we support more general feature-based space-time clustering where the sets of points constituting the features being clustered are allowed to change over time.

Overview

Our method enables artists to texture complex animations by extracting temporally coherent structures that locally describe these animations. The artists can then specify a correspondence between the characteristics of the extracted structures and parameters of user-defined animation elements called motion stamps. Our method allows one to specify the size of the structures that locally describe the underlying animation, and is applicable even when the set of animated points change over time.

When analyzing artistic stylization in hand-drawn animations, we observe that animators often stylize visually salient areas of an animation in order to emphasize or exaggerate their qualities. Based on this observation, we let artists choose to texture a whole animation or only parts of it. We provide a UI letting artists specify relevant areas based on features such as vertex curvature, position, or velocity. Texturing salient parts of an animation such as waves rolling over an ocean or cloth wrinkles sliding along the surface of a garment is made possible thanks to our structure extraction that is independent of the topology of the underlying animation.

Our solution includes two main components:

• Space-time clustering. Since the points that define a simulation are often unstructured without temporal consistency, we propose a novel spatio-temporal clustering method to establish coherence in the simulation data. Clusters may appear or disappear, split or merge over time, triggering the appearance or disappearance of motion stamps when and where needed, based on the evolution of the animation. • Motion stamp control. For each cluster, a stylization engine instances a motion stamp whose parameters are connected to the detected feature values. Our method allows one to control time cycles of motion stamps, temporal warping, changes in scale and orientation, as well as deformation parameters such as the amount of stretch or twist of an animated shape.

The parts of our work are respectively described in the next two sections.

Dynamically Coherent Clustering

Given a set of 3D points Ps defining all or parts of an animation, our goal is to create a uniform distribution of clusters that meet the desired radius of the animated stamps. While many methods targeting spatial clustering exist (see Section 2), they do not allow directly specifying the radius of the computed clusters. Since the clusters will be used as support to instantiate motion stamps, it is crucial that our method provides control over the size of those clusters. We let users specify a radius and a tolerance threshold, defining the range of acceptable cluster sizes. This enables the detection of clusters whose size varies over time. The second challenge is to create a dynamically coherent clustering, i.e. the ability to have clusters that move over time without temporal discontinuities.

To allow the user to specify a range of acceptable cluster radii, we employ a hierarchical clustering strategy (described below), and track the clusters over time by mixing advection and dynamic reclustering. In other words, we initialize a clustering at the beginning of the animation, and then advect the clusters over time by sampling the velocities of the clustered points, and re-clustering areas that hold new features that appeared over time.

Spatial Clustering

Our spatial clustering routine is a hierarchical clustering which results in a tree graph with bottom leafs holding a cluster with a single 3D point, and the root node a single cluster containing all the points. Each node describes a set of points and its radius, a node's parent always has a larger radius, while a node's child always has a smaller one. Given a range of acceptable cluster radii, we can parse the tree and select clusters at the appropriate hierarchical level.

To create the hierarchical clustering structure, we start by creating a cluster for each 3D point, setting its radius to 0. Then we iteratively merge the two nearest clusters into a larger one until all clusters have been merged into a root node containing all 3D points (see Figure 3). In practice, building the whole hierarchy is not necessary since the root cluster will often be larger than the maximum desired radius. Instead, we keep track of the radius of each cluster at each iteration. If two clusters get merged and the new cluster's radius is above the maximum allowed value, we stop this iteration and look at the two clusters getting merged. If a cluster has its radius larger than the minimum authorized radius, then it is tagged as a valid cluster and will be propagated further down our pipeline.

Note that this algorithm computes clusters only if their radii are within the acceptable range and therefore does not necessarly provide a partition of the selected 3D points. For instance, water droplets smaller than the prescribed radius and too far apart will merge into a cluster with an undesirable large clusters, and they will be discarded since they are too small, which complies to the user-specified cluster size.

Space-time clustering

Given two clusterings of the animation at two different moments in time, the correspondence between the two sets of clusters can be ambiguous; it can be hard to know which cluster at a time step corresponds to which cluster at the next step. One possible strategy to overcome this ambiguity is to perform a hierarchical space-time clustering of the animated points. Such an algorithm would be similar to the spatial clustering described in Section 4.1. Each particle at each time frame would be assigned to one cluster, and the two closest clusters in both time and space would be iteratively merged. While our experiments have shown that this method provides satisfying results, the cluster hierarchy computed over a complex animation is very memory and time consuming, which is not desirable when interactively manipulating animations.

Our strategy is instead to create a first spatial clustering at time t k , and to then advect the clusters, predicting their positions at time t k+1 . We can use the predicted cluster positions to efficiently compute a clustering at t k+1 as shown in Figure 4, and iterating this step results in a fast algorithm producing temporally coherent cluster data.

Advecting clusters requires the definition of cluster velocity. Two velocities can be defined for a specific cluster: the average of its element (vertex or particle) velocities, or the velocity obtained by fi-nite differences over the cluster's successive positions. We found in our experiments that both definitions can be appropriate depending on the application. When clustering wrinkles moving over a shirt, the vertices constituting the wrinkles follow a trajectory mostly along the normal direction to the shirt, while the wrinkles slide tangentially to the cloth. When clustering particles in a flowing river simulation however, a cluster should move along the water and follow the particle velocities. Ignoring the particle velocities could result in static clusters, that would be surrounded by particles at each time step while having a null velocity.

This observation lead us to offer the user the choice to compute clustering based on point velocities or on cluster velocity. When choosing to use cluster velocities, we initialize the cluster velocities after the initial spatial clustering to be zero, they are then updated as the spatio-temporal clustering progresses.

During spatio-temporal clustering, after any time step t k , we estimate each cluster's position at time t k+1 by advecting its previous position using the velocity type chosen by the user. We use a priority queue to store all the pairs (estimated cluster position, 3D point) at time t k+1 and use it to successively assign 3D points to their closest estimated cluster center. Each assignment is discarded if it conflicts with the user specifications: if the assignment would bring the cluster radius over the maximum authorized one, or if the displacement of the cluster would increase the cluster velocity over the maximum authorized value.

Once the assignment step done, the remaining points (features appearing in the animation, or points that would have enlarged existing clusters beyond user specifications) are clustered using our spatial clustering method and added to the set of computed clusters. Note that since this spatial hierarchical clustering is only computed when and where needed, the computation time of our method does not suffer much from rebuilding a cluster hierarchy.

Finally, we detect splits and merges between clusters. Using the initial velocity of a cluster, we backtrack its first position one frame in time, and look at the backtracked position's neighborhood. If the existing cluster closest to that position is within δt * max vel , with max vel the maximum authorized cluster velocity, we mark this as a split event: the already existing cluster has its own trajectory, but splits to spawn the new one. We apply a similar process to detect merges at the end of a cluster's life. Later in the pipeline, the user can chose to use that split/merge knowledge for stylization.

Programmable motion stamps parameterization

Our goal is to texture animations with animated motion. In the previous section, we described how to obtain dynamic clusters of preselected size moving along the animation. Each cluster provides local spatio-temporal information about local parts of the animation.

Figure 3: Each 3D point is assigned to an individual cluster of radius 0 (blue). We iteratively merge the two closest clusters until we reach one cluster covering all the data (orange). The cluster hierarchy (right) can then be used to get clusters with a desired radius.

Figure 4: The cluster velocities at time t k (left) are used to predict the cluster positions at t k+1 (center). Assigning 3D points to the closest predicted centers (right) yields a partial clustering at t k+1 . The non-clustered points (black) are then clustered in an independent step.

We build an analogy with traditional texture mapping. To render a textured surface, it is discretized into faces, bounded by vertices and edges. Each vertex can carry information such as its position, color, normal, or texture coordinate, the latter helping to define local 2D parameterizations of the 3D surface. By writing a vertex shader, the user defines how 3D vertices are projected onto the screen. Then by writing a fragment shader, the user can specify an output color, defined by four parameters (red, green, blue, alpha), depending on the information carried by the vertices that are projected onto the screen.

In our framework, the base animation is discretized into clusters, that carry information sampled from their components: their cluster velocity and component velocity, their position, radius, normal, etc. The user can write scripts that we call motion shaders to parameterize animation instances. We use the formalism introduced by Milliez et al. [MNB * 14] and define elementary animations as motion brushes. A motion brush can be as flexible as a procedurally defined shape and as rigid as a baked 3D animation. A motion brush is analogous to a 2D texture. Instances of motion brushes in a scene are called motion stamps, and carry a set of parameters such as position, scale, orientation, opacity multiplier, animation speed, etc. When writing motion shaders, users define the values of a single motion stamp's parameters based on a single input cluster, the same way fragment shader programs define the color of a single fragment at a time (Figure 5).

As described in 4.2, our space-time clustering detects if a cluster has splitted from or is merging into another cluster. That information is available in our motion shader framework and the user can read the parameters of the clusters splitted from or merged into. The motion shader can ignore it, or can adapt the instantiated motion stamp's parameters accordingly. For example in the provided supplemental videos, the butterly motion shader ignores those events and every butterfly appears with a rising animation, and disappears by flying away. The fish motion shader however takes note of the split information. When a cluster appears splitting from another one, the motion shader aligns the motion stamp parameters with the older cluster for a few frames. The result animation does not result in a popping fish animation, but shows fish splitting in two.

Our motion stamp engine then runs the user-specified motion shader on each computed cluster and automatically instantiates motion stamps within the scene. The attached video shows various examples of textured animations including changes between different motion stamps during the life of a cluster.

Cluster Motion Stamp

Figure 5: Users can choose how the cluster data is used to parameterize the motion stamps.

Results

We implemented our pipeline as a plugin for Autodesk Maya ( [May16]), in order to take advantage of the production pipeline professional artists are acquainted with. Both cloth and liquid animations seen in this paper were simulated using technology natively available in Maya.

The user can open a scene, select a simulation object, and load our plugin. When desired, we provide a visualisation of the selected parts of an animation by coloring the selected particles or the mesh vertices. Our plugin provides UI controls to adjust thresholds for a variety of vertex and particle parameters, letting users select parts of the animation depending on that information. In the case of complex feature selection, the user can even script the value of the score for each 3D point.

The user starts the clustering procedure by first using UI elements to specify the desirable cluster radius and the tolerance for admissible cluster radii, as well as the maximum authorized cluster velocity. Our clustering algorithm is fast and if the user is not satisfied with the result, he or she can change the parameters and run the clustering algorithm again. We present some performance results in Table 1.

Finally, the user can edit motion shaders that parametrize motion stamps depending on the cluster data. The collection of already implemented shaders is exposed to the user, who can decide to reuse previous shaders, or to write a new one.

Figure 6 shows a simple toy example: a simulated cloth rectangle is held by two handles that exerce a vertical motion. The cloth simulation produces a wave motion. The goal here was to cover the cloth with butterflies, that take off as the wave motion propagates along the cloth.

The user could define the selection based on the y position of vertices, as well as the animation time. The desired cluster radius was defined as the desired butterfly radius, and the maximum authorized velocity for each cluster was set relatively high (3 times the cluster radius) to ensure proper tracking during the fast cloth movement. Once the clustering was performed, the user could use two motion brushes describing butterfly animations: idle and take off, and script the motion stamp instantiation through the following script (presented here as pseudo code).

while (cluster is alive) { stamp.position ← cluster.center stamp.scale ← cluster.radius / stamp.radius stamp.upDirection ← (0,1,0) loop play idle animation } for (frame = cluster.end +1 to cluster.end + take off duration) { keep the same position, scale, orientation play take off animation once } For the wrinkle stylization seen in Figure 1, the wrinkles on the T-shirt were selected based on the vertex curvatures (wrinkles exhibit a high curvature) and positions (so as to ignore the wrinkles on the arms). Butterfly motion stamps were then scripted to follow the cluster centers, first playing a spawning animation once, followed by a looped idle animation. When clusters disappear, the stamps were scripted to keep the same position and play a take off animation once.

We also created different liquid simulation scenarios. First, as shown in Figure 7, water is thrown with a high initial horizontal velocity, and is projected in the air by a bump on the ground. The user could select various parts of the animation to cluster them, and use the clusters to texture the liquid with animated fish. In a similar fashion to previous results, the fish radii are dictated by the cluster sizes, while the fish positions and orientations are parametrized by the cluster positions and velocities respectively. Replacing the fish by another type of motion stamps like the birds seen in Figure 7 is simply done by changing the type of motion stamp used in the motion shader.

Motion stamp parameters are not limited to the ones used in our results so far. We demonstrate the flexibility of our method by parametrizing the deformation of spring-like shapes. Each spring's stretch factor is parametrized by the underlying cluster's velocity, its bending by the curvature of the cluster's trajectory, and its revolution angle is scripted to increase over time. Considering the spring shape as a 1-frame animation, this example fits in the formal definition of motion stamps described in [MNB * 14]. However, we are essentially producing the shape animation on the fly depending on the cluster data, instead of reusing animated examples. Finally, we show more complex examples of animation texturing. In the first, two liquids collide and create a splash, as shown in Figure 8. Selecting particles based on their position and velocity, the user could successively stylize the two sets of fast moving particles aiming at the collision area. By setting the same desired cluster properties on the two sets, and texturing them using the fish parametrization described above, the user could easily instantiate two crowds of fish with similar radii aiming at a frontal collision. Then, selecting particles based on their position and time of existence, the user could isolate the particles that constitute the splash. After clustering them, a bird parameterization similar to the previously described one was used, thus texturing the splashing drops with flying birds. We show a composition of the fish and birds, rendered along with the meshed particles.

The last example seen in Figure 1 shows a hand lifting water from a pond. After selecting particles based on their vertical position, the user textured the water lifted off by the hand, turning the water into fish as it is being manipulated.

Conclusion

In this work, we have devised an animation texturing framework that allows animators to author stylizations on top of complex animations. Our programmable approach allows artists to select salient areas of basic animations, as well as to link the stylization behavior and motion of the instantiated motion stamps to the attributes of the underlying animation. Our clustering algorithm can be efficiently implemented without copying any point data, and we have shown results of its performance. However, its sequential design makes a performance improvement through parallelization challenging. We have implemented our work within Autodesk Maya for artistic convenience: it provides all the necessary tools for animation authoring, and our method integrates well within that workflow. However, while motion shaders are simple programs and our motion shader processor can be straightforwardly parallelized, the time spent processing the shaders is negligible compared to the processing time required by the Maya API to read motion brush files from disk and to set motion stamp parameters and keyframes.

While our method lets artists semi-automatically create complex arrangements of animations that would otherwise be very challenging to produce by hand, we could already identify interesting areas for future work. While we have demonstrated our implementation on cloth and particle simulations, we believe that our method can easily extend to other types of animated data. Eulerian simulations for example, are typically used to represent smoke or fire. Each cell in a Eulerian simulation grid provides a velocity vector that we could rely on in our spatio-temporal clustering algorithm, and scalar data such as density or temperature could be used to parameterize motion stamps.

While our method instantiates and tracks clusters based on the underlying animation, there is so far no interaction between the clusters. Using the detected splits and merge informations, the user can decide to temporarily align rigidly new appearing clusters to existing ones, giving the impression that instantiated stamps are splitting, as is seen in the accompanying video. However, one could imagine designing, in addition to a motion stamp animation, a motion stamp merging animation, that would be played when two clusters merge. While our current method rigidly transforms a motion stamp to instantiate it, instantiating merging motions would require a non-rigid deformation of the motion stamps' trajectories, which we do not currently support.

Our clustering is based solely on point positions, which is an acceptable limitation for the results targeted in this paper. However, one could envision use-cases where more metrics would be relevant. For example in the complex case of particles moving in different directions while being in the same vicinity, one might want to cluster them based on velocity. It is unclear whether exposing several metrics to the user would result in an intuitive and predictable interface, which would be an interesting question to explore when extending this work.

Another feature that could contribute to interesting results would be a remeshing step to merge the animation mesh and the instantiated motion stamps. While our method is already satisfying for instantiating fish in water for example, it is not well suited to changing the shape of the water. If a user wants to select every wave in an ocean to change their shape, the current approach would be limited to instantiating new wave shapes on top of the existing ones. Computing a smooth mesh over the animation and the instantiated geometry would provide more appealing results.

Finally, we feel like our clustering algorithm could be used for level of detail stylization of 3D scenes. Indeed, by incorporating a camera model into our clustering, one could imagine seeing more clusters appear on a scene as the camera zooms in. The radius occupied by each cluster on the screen could also be used to parameterize the motion stamp animations.

  Motion stamps. Dynamic stylization can be time consuming when performed manually. Hence previous works have investigated the idea of linking parametric motions to larger scale movements designed by the animator [CHG14, MNB * 14]. In these works, 2D or 3D animated stamps are controlled by sketching their positions or trajectories. Chevalier et al. propose an interface for designing 2D flows and controlling the parameters of overlaid 2D texture elements moving along the flow [CHG14]. Milliez et al. allow the user to sketch the position of 3D animated meshes and control additional parameters such orientation using gesturing strokes [MNB * 14]. We adopt the same "motion stamp" concept proposed by Milliez et al. and extend it to work in the context of simulation enhancement. Neither method addresses the problem of feature selection or trajectory extraction in the context of complex fluid or cloth simulations. Clustering. A core component of our system addresses temporally coherent clustering of 3D points respecting a user-specified size. Data clustering is a research field in itself, and Xu and Wunsch provide a survey of clustering algorithms [XW05]. We are in particular inspired by spatial hierarchical clustering techniques, of which a detailed review is available in [HKT01]. In order to support an artist-inspired workflow, we favor an application-oriented clustering and tracking algorithm. Related techniques for spatiotemporal clustering target data such as moving pedestrians or vehicles [LHY04,HP04,NP06,AAR * 09,JLO07,JYZ * 08,KMNR10].

Figure 2 :

 2 Figure 2: Overview of our pipeline.

Figure 6 :

 6 Figure 6: From left to right: original animation with colored selection of vertices, clustering over the selected vertices, motion stamp, textured animation.

Figure 7 :

 7 Figure 7: From top to bottom: the original animation and a clustering obtained using our algorithm. The motion stamps used to create the present results. Textured results of our algorithm.

Figure 8 :

 8 Figure 8: Original, clustered data and textured animation.

Table 1 :

 1 c 2016 The Author(s) Computer Graphics Forum c 2016 The Eurographics Association and John Wiley & Sons Ltd.A. Milliez, M. Guay, M.-P. Cani, M. Gross, R. W. Sumner / Programmable Animation Texturing using Motion Stamps For each result, the number nPoints of 3D points clustered in the animation, over nFrames frames, into nClust clusters. Computation time reported in the last column.

		nPoints	nFrames nClust. time
	Water Fish	134,651 127	238	6s
	Water Bird Drops 132,120 130	435	8s
	Butterfly Shirt	457,748 215	2578	38s

c 2016 The Author(s) Computer Graphics Forum c 2016 The Eurographics Association and John Wiley & Sons Ltd.