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

Pierre Maret
email: pierre.maret@univ-st-etienne.fr

Virtual Knowledge Communities for Semantic Agents

Keywords: H.3 [Information Storage and Retrieval]; I.2.11 [Artificial Intelligence]: Multiagent systems Semantic Agent, Virtual Knowledge Communities Semantic Agent, Virtual Knowledge Communities, Set-theoretic formalization, Ontology, OWL, SWRL

Virtual Knowledge Communities are a well suited paradigm for decentralized knowldege exchanges and they have been applied in several domains. In this paper we investigate the implementation of virtual knowledge communities with semantic agents. Using the SAM (Semantic Agent Modeling) approach, we show that agents can exchange community related concepts (in OWL) and behavior (in SWRL). Agents can then learn and adapt new community-related behavior, which is usefull when changing the role or entering into a new environment. For this purpose, we formalize Virtual Knowledge Communities in a set-theoretic way and we implement this formalization in an OWL ontology. Some examples of community representation using our formalization are presented in this paper.

INTRODUCTION

Agent mediated knowledge management (AMKM), a term coined for the first AMKM workshop in 2003 [START_REF]Agent Mediated Knowledge Management[END_REF] (followed by two editions [START_REF]Proceedings of the ECAI-2004 Workshop on Agent-mediated Knowledge Management[END_REF][START_REF]Proceedings of the AAMAS 2005 Workshop on Agent-mediated Knowledge Management[END_REF]) is a specialized research domain of distributed knowledge management. The main idea of AMKM is to take into account the decentralized nature of knowledge and its social aspects inside organizations. Nowadays, the rise of semantic technologies such as RDF,OWL and SWRL have provided a powerful frame for knowledge representation and processing, due to the expressivity of these formalisms and their underlying logic formalisms [START_REF] Damasio | Supporting open and closed world reasoning on the web[END_REF]. A first step in the integration of semantic technologies in the domain of agent-mediated knowledge management has been made in using the knowledge representation formalism. Thus, semantic technologies have been introduced to replace former knowledge representation in mainstream agent platforms like JADE [START_REF] Bellifemine | JADE-A FIPA-compliant agent framework[END_REF] and in agent programming languages like the OWL extension for JASON [START_REF] Bordini | Jason and the Golden Fleece of agent-oriented programming[END_REF]. A second step has consisted in taking advantage of the logical power of the semantic languages to replace the usual Prolog-like languages used in agent programming. By doing so, agent knowledge and agent programming can both be tackled within a unique paradigm i.e. the semantic technologies. This is known as introducing de facto the agent's reflexive abilities: the ability to change its behavior depending on its beliefs. Agents using semantic technologies in both agent knowledge representation and internal programming have been called semantic agents. Several architectures such as Nuin [START_REF] Dickinson | Towards practical reasoning agents for the semantic web[END_REF], S-APL [START_REF] Katasonov | Semantic agent programming language (S-APL): A middleware platform for the Semantic web[END_REF], JASDL [START_REF] Moreira | Agent-oriented programming with underlying ontological reasoning[END_REF] and SAM [START_REF] Subercaze | SAM : Semantic Agent Model for SWRL rule-based agents[END_REF] have been proposed.

However, while the semantic models have been introduced in these agent-oriented architectures, the duality between agent knowledge and agent behavior remains. In Nuin and in S-APL, the behaviour and the knowledge base are expressed in differents languages or paradigms. Thus, knowledge (from the knowledge base) has to be converted in order to be used by the behaviour. In Nuin and in S-APL, the behaviour and the knowledge base are expressed in different languages or paradigms. Thus, knowledge (from the knowledge base) has to be converted in order to be used by the behaviour. For Nuin and S-APL, the conversion (from RDF or from OWL) into the agent programming language implies a loss of expressivity since the logics of knowledge bases are more expressive than the ones used in the agent programming.

The aim of this paper is to propose an innovative approach that implements the combination of knowledge and behavior when considering exchanges between agents. Making agents acquire knowledge is not an innovative effort. Our proposal is to describe a model and to implement a system where agents can learn and adapt new community-related behavior (SWRL rules). This is useful when the agent changes role in a community or enters into a new environment. We will consider an existing model for agent exchanges (namely VKC [START_REF] Maret | Virtual knowledge communities for corporate knowledge issues[END_REF]) and will propose an ontology that describes and operationalizes agent knowledge and behavior in this area. This is implemented in the frame of the SAM (Semantic Agent Model) architecture.

In the next section, we will present the model of VKC and the SAM architecture. In section 3 an innovative formalization of the VKC approach using a set-theoretic model will be proposed. Based on this formalization, we will then define the OWL-based ontology that describes and operationalizes knowledge and behavior for semantic agent exchanges. Related works will be briefly described in section 4 and some concluding remarks will be given in section 5.

BACKGROUND

Two main background concepts are concerned with the present paper: Virtual Communities and the Semantic Agent Model. They are here presented for a good understanding of the proposed set-theoretic model and the OWL-based ontology.

Virtual Knowledge Communities

Research in the field of corporate knowledge management lead by Calmet and Maret introduced a distributed approach for corporate knowledge management based on the agent paradigm. The concept of Virtual Knowledge Communities (denoted VKC) was then introduced in 2004 [START_REF] Maret | Virtual knowledge communities for corporate knowledge issues[END_REF]. Since then, it has been used in several application domains.

Virtual Knowledge Communities are introduced as a means of knowledge dissemination within a society of agents. Each agent owns an internal goal to achieve which, directly or indirectly, may lead it to distribute or to acquire knowledge. Communities are the mechanism used by the agents for these knowledge exchanges. Thus communities increase the efficiency of knowledge dissemination within the society of agents. Through the dynamic processes of VKCs, agents can create, join, feed, use or leave communities, and so they can acquire new knowledge from other agents and infer new knowledge through their cognitive component.

A virtual knowledge community consists of a topic, community members and a policy for message exchanges. Members exchange messages related to the topic of the community, following the community policy (rule-based policy). Messages are exchanged through a shared board system that allows to post new messages and to access previously posted ones. This board system is called the community buffer. In the implementation provided by Hammond [START_REF] Hammond | Virtual knowledge communities for distributed knowledge management: A multi-agent-based approach using jade[END_REF], agent knowledge is represented with ontologies (i.e. concepts, links and instances). Pieces of knowledge that can be exchanged within agents are subsets of one agent ontology. A community discovery service called the "community of communities" is also provided.

Among the functionalities related to community management, one can cite the evolution of a community topic and the dissolution of a community. Topic evolution is required because communities are created dynamically and they evolve during their lifetime (i.e. participants, messages and topics can all change). The mechanism to change the community topic is provided, it is controlled by the community owner (a member with the appropriate policy) and it consists of an internal updating and sending of a message addressed to the community of communities for updating this kind of yellow pages. Similarly, the dissolution of the community can be made on the initiative of the community leader: a message is sent to the community of communities to remove the existing entry.

The ability of agents to interpret and exchange the acquired knowledge is considered as intrinsic knowledge. This ability can be different for each and every agent. We argue that this design choice takes into account the decentralized nature of knowledge and its consequences in agent-mediated knowledge management.

Community regulation is a human social necessity that is also required in virtual communities. Regulation consists of rules that apply within the community regarding its use, security and confidentiality. To handle this regulation, each agent creates a community and specifies the policy which applies to it. The policy specifies, for instance, the way agents join, leave, share messages and access messages. Also, policies are introduced to handle security issues that can be encountered with malicious agents in an open agent society. For instance, access control to the board system of the community or encryption of messages can be specified.

The VKC paradigm has been succesfully applied to several application domains, including context-aware applications [START_REF] Subercaze | Context-aware applications using personal sensors[END_REF], mobile applications [START_REF] Subercaze | A Service Oriented Framework for Mobile Business Virtual Communities[END_REF] and E-Health [START_REF] El Morr | Virtual Knowledge Network for Human Rights Monitoring[END_REF].

Semantic Agent Model

The Semantic Agent Model [START_REF] Subercaze | SAM : Semantic Agent Model for SWRL rule-based agents[END_REF][START_REF] Subercaze | Semantic Agent Systems -Foundations and Applications, chapter Programming Semantic Agent for Distributed Knowledge Management[END_REF] (noted SAM) is an architecture of semantic agent that aims at representing both static knowledge and agent behaviour using semantic models. The static knowledge is represented in SAM using ontologies expressed in OWL, which is today the most convenient modelling technique. Regarding agent behavior, while other existing semantic agent models do not support any semantic programming language, the SAM includes a standardized semantic approach, i.e. the behavior is expressed in terms of rules and it is based upon the SWRL (Semantic Web Rule Language). Doing so, the static knowledge and the behavior are expressed in a unique paradigm (semantic modeling), and this makes them fully compatible and avoids translations from one paradigm to another.

The behavior of an agent is implemented as sets of specialized SWRL rules. The antecedent of the rules consists of some conditions concerning the environment and the internal state of the agent. The consequent of the rules contains a sequence of actions that will cause the agent to act on its environment and/or to modify its internal state. Actions are of two types: SWRL built-ins and lower level actions. Lower level actions emcompass actions that are required to support an agent execution (message sending, file access), actions for knowledge manipulation that cannot be expressed with SWRL rules (such as knowledge removal), and agent framework interactions. The execution of the behavior, as well as the the maintainance of the knowledge base's coherence and the inference of new knowledge, is supported by a reasoner (Pellet).

The added value of SAM is that it increases the semantic interoperability of agents: given a limited number of lowlevel actions that must be available on each agent, any behavior expressed in terms of SWRL rules can be exchanged between agents. This means that agents can now acquire a behavior, and that they can execute this new behavior taking into account their own static knowledge.

As SWRL doesn't support rule ordering, a slightly modified version of the Extended Finite State Machine (EFSM) model [START_REF] Cheng | Automatic functional test generation using the extended finite state machine model[END_REF] has been used. This version guarantees the execution of only one rule at a time. In EFSM, transitions between states are expressed using if statements, and they are linked to some operations. A transition is fired if trigger conditions are valid. Then, the state machine is brought from the current state to the next state, and the set of specified operations is performed.

The following rule is an example of a SAM SWRL rule. It states that if the current agent is in state A (lines 1 and 2 in the rule) and the message received (3) has been sent by Bob (4) and this message is an answer [START_REF] Damasio | Supporting open and closed world reasoning on the web[END_REF], then the next state of the agent (8) will receive the value held by y (or sEnd which is the final state), a stored list of actions ActionSequence will be performed [START_REF] Katasonov | Semantic agent programming language (S-APL): A middleware platform for the Semantic web[END_REF] till the end [START_REF] Maret | Virtual knowledge communities for corporate knowledge issues[END_REF], and the content of the message (hold by w ) will be added in the knowledge base [START_REF] Moreira | Agent-oriented programming with underlying ontological reasoning[END_REF][START_REF] Subercaze | SAM : Semantic Agent Model for SWRL rule-based agents[END_REF].

CurrentState(?x) (1)
∧ StateV alue(x, A) (2)
∧hasReceived(?z)

∧hasSender(z, Bob) (3)
∧hasP erf ormative(z, Answer)

∧ N extState(?y)

∧hasContent(z, ?w)

⇒ StateV alue(y, sEnd)

∧hasContent(ActionSequence, AddInstance)

∧hasN ext(ActionSequence, endOf List)

∧hasP arameterN ame(AddInstance, name)

∧hasP arameterV alue(name, w)

The main benefit of the approach is that knowledge and behaviour are represented using compatible semantic languages. Consequently, an agent's behaviour is also a piece of knowledge, operational knowledge, upon which the agent can reason and which can be sent or received to/from other agents.

Knowledge

FORMALIZATION OF VIRTUAL KNOWL-EDGE COMMUNITIES

While Virtual Knowledge Communities have been implemented in several application domains, no formalization of the approach or the model has been given. Our aim is to implement VKC in semantic agents. So, the design of a VKC domain ontology is required. For this purpose, we will follow a two-step formalization. In a first step we will formalize the VKC in a set-theoretic way, which is the common abstraction paradigm. In a second step we will adapt this formalization as an OWL ontology, to make it compatible with SAM agents.

A set-theoretic formalization

We define several sets and relations to formalize VKCs. The first set is M the set of agents that belong to the community. Communities bring together agents around topics (one or several). The set of these elements is denoted S. As previously presented, agents do not have identical roles in communities: they can be a leader, a member or have some other predefined role. We denote R the set of the roles available in the community. A leader can shut the community down, whereas a member can only join or leave it. These actions are grouped in the set of actions called A. To link agents to roles and roles to actions, we define the relations rr and rp.

The most significant set in this formalization is P , the set of protocols. These protocols define the communication rules and acts that define interactions between agents within a community. Protocols can be designed in terms of SAM semantic rules, which then make them into executable and exchangeable knowledge for SAM agents. Doing so, agents can acquire and execute VKC protocols and thus participate in communities.

The underlying idea of this approach is to build an operational representation of VKC. In the end, agents should be able to exchange knowledge of communities that can be executed by other agents. These protocols belong to the set P that describes implementation of actions that are associated to roles by the relations rp.

We propose the following formalization for VKC: a community c belongs to the set of communities C. A community is a tuple: c ∈ C = {M, R, A, P, S, rr, ra, rp} where M, R, A, P, S are sets and rr, ra, rp are relations between these sets.

Sets.

• M is a set of agents belonging to a community. A community owns at least one agent which is the creator of the community. |M | ≥ 1.

• R is a set of possible roles within the community.

• A is a set of actions that are possible in the community. Classical actions are join, leave, post, . . . . To be meaningful, A must be non empty, otherwise no action is possible and the creator is the only member.

• P is a set of protocols. A protocol describes the rules for exchanges within the community. A protocol is related to an action. A community protocol is bound to specify the orchestration of actions for a community.

For example, a protocol can dictate that an agent cannot (or can) post a message without being a member of the community. In this example, the community protocol requires a JOIN before a POST. The cardinality of P is greater or equal to 1 (which is a consequence of A being non empty).

• S is the set of topics of the community.

Relations.

• rr ⊆ M × R is a relation between the set of agents M and the sets of roles R. This relation describes the different roles in a community an agent can be associated to. Each agent has at least one role. However some roles in a community can be unoccupied. Thus, rr is left-total 1 .

• ra ⊆ R × A is a relation between the role set R and the action set A. Each role is associated with the sets of actions permitted for this role in the community. As each role has at least one action related, ra is left-total.

• rp ⊆ R × A × P is the relation that associates each couple (role, action) to a protocol. For example the action JOIN is different if the member is a user or the host of the community. In the first case, the agent will send the request, in the second one, the host will process the request.

Zero community

The zero community c0 ∈ C is the minimal community in which knowledge exchange can happen. The term minimal is here to be understood in the sense of a minimal number of actions and roles. One may intuitively think that the minimal community is made of the 3 actions join, sendMessage, leave. However, it is possible to define a meaningful zero community with only two actions sendMessage, leave. This community is then similar to a mailing-list where the action of sending a message automatically registers the agent into the community. For the agent, leaving the community consists of sending a leave message to the community leader agent which removes it from the list of members. The figure 2 depicts this example. Bob is the creator and leader of the community, Chuck and Dave are members. Alice sends a message to Bob following the protocol specified by sendMessage for agents willing to join the community. Bob follows the protocol associated with sendMessage for the creator and thus broadcasts Alice's message to the community members. Finally, Alice is added to the list of members of the community.

Using the previous formalization, the zero community can be written as follows. Notice that '+' indicates an action initiated by an agent, and '-' indicates an action where the agent receives the action messsage.

• M = {Alice, Bob, Chuck, Dave} • R = {leader, member} • A = {sendM essage, leave} 1 A relation R ⊆ X × Y is left-total if
and only if for all x in X there is one y in Y such as (x, y) ∈ R. The association between the role leader and the leave action leads to both + and -protocols. When the leader receives a leave request from an agent (i.e. leave-), it removes the agent from the list. In the case where the leader wants to leave the community (leave+), the community is deleted.

Protocols

Protocols specify communication rules between agents.

There is a protocol for each action in the community. The communication rules described specify the content and the order of exchanged messages.

View of a community

Depending on their function and history, agents may have different information about a community they are members of. This is what is called the view of a community, and it is held by an agent. Continuing the zero-community scenario, let us take another example: Alice has just joined a community initiated by Bob. Agents Chuck and Dave already belong to this community. As Alice has just joined, she doesn't know anything about members of this community, the previous content exchanged or the topic evolutions, etc. However, Bob, who initiated the community, knows every member and it has been able to hold the history of all exchanged messages (or it has acquired the content of the messages in its knowledge base).

Let us recall that the SAM architecture handles static knowledge and behavior at the same level (and in the same semantic paradigm). Thus, the agent's view of a commmunity also encompasses the protocols an agent is able to execute related to communities. Agents can then hold different protocols relative to their respective roles in given communities. Such a mechanism is useful for security purposes to limit one's actions in a given environment. Also, since SAM makes protocols exchangeable, an agent (when changing the role) can acquire a new behavior for the related community, which changes its executable view of this community.

VKC efficiency measurement

VKCs are a means of sharing knowledge between agents. Since protocols can be exchanged, it is relevant to consider and to compare the protocol's efficiency for knowledge dissemination. We propose to measure this sharing efficiency within communities and we introduce first some basic measurement tools.

• Let At be the set of agents in the community at time t.

• Let KT,i,t be the set of knowledge received by agent i on the topic T at time t.

• Let fiK → [0, 1] be the function from the set of knowledge K to the interval [0, 1]. This function represents the interest of the agent i for a piece of knowledge. Zero means no interest and 1 means a maximum of interest.

• Let KgT,t be the set of knowledge exchanged on the topic T at the time t.

We define the efficiency of the knowledge dissemination with the formula (adapted from [START_REF] Calmet | Simulation in virtual communities[END_REF]):

EKDT (t) = i∈A t |f (K T ,i,t | |Kg T ,t | |At| ( 13
)
By definition, EKD ranges into the interval [0, 1]. EKD reaches its maximum (i.e. = 1) when all agents have received only knowledge of interest. In the case where no agent has received any knowledge worthy of interest, the function is equal to zero. The EKD measure represents the efficiency along the time. The normalized integral over time gives the instantaneous variation of the efficiency. These formulae give a frame for community benchmarking. Some benchmark results are provided in a previous study [START_REF] Calmet | Simulation in virtual communities[END_REF].

Ontology

We have presented a set-theoretic formalization of virtual knowledge communities. We have given a specific definition of community protocols, based on rules that define agent behaviour and applicable in the SAM architecture. Now, our formalization will be made available for semantic agents in defining an OWL-based ontology of virtual knowledge communities that will be integrated into each SAM agent's knowledge base.

For the design of the ontology, we translate sets and relations from the previous formalization into ontology concepts, i.e. classes and relations in OWL. This translation goes straight-forward, except for the ternary relation rp that cannot be directly expressed in OWL. Indeed OWL only supports binary relations, which then restricts our implementation. This restriction can be circumvented thanks to one of the three design methods proposed by the W3C 2 . We decided to use the solution which introduces an intermediate class (denoted AP , for ActionProtocol). Figures 3 and4

Classes.

The classes of the ontology are mostly the same as the ones defined in the set-theoretic formalization. Agent class represents an agent. LeaderAgent is a subclass of Agent and represents agents having the leader role in the community. The class Role describes the different roles available in the community. These roles are linked to actions through the classes CommunityAction and protocol. The class AP (for ActionProtocol) is the artefact used to describes the ternary relation between a role, an action and a protocol. Finally the class Topic describes the topic of the community. The classes are listed in the table 1:

Relations.

The relations in the ontology can be deduced from the ones which have been formally introduced. In OWL, relations have a name, a domain (the class of subject individual) and a range (the class of the object individual). The relation hasTopic associates a community to a topic. A community 2 http://www.w3.org/TR/swbp-n-aryRelations/

View of communities

The community ontology describes the concepts and their relations. The agent's view (composed of static knowledge and behavior) of a community is populated with instances of those concepts. Returning to our example -the zerocommunity-, agents Alice, Bob and Chuck have the following views:

Alice

• Topic: topic of the community

• Roles: member, leader It appears that the leader of the community is the only one with a complete view of the community. This is a characteristic of a centralized community like the zero-community. Notice that one could implement several types of communities (decentralized, individualistic, social, etc.) and this would influence the content of the view of the community of agents. Also, a community leader owns the protocols related to the community, but it may not necessarily know the complete set of agent members of the community. This concept of views of community appears as a keystone to maintain the decentralized approach strongly claimed in the virtual knowledge communities approach.

Application: Yahoo! Groups

In order to better illustrate our proposal, we will describe it in the frame of a real-life example: the Yahoo! Groups 3 . Yahoo! Groups are discussion-based communities, created in 1998. This service belongs to the top 5 Yahoo! services in terms of frequency of use. Yahoo! Groups offers a complete set of features to support community interactions. The following features are provided to users:

• Messages: Send an email to the group (and the possibility to delete a previous message)

• Photo album

• File storage

• Links directory: contains a link and a description for each entry

• Polls

• Database: 10 tables allowed • Options: change the welcome message. . . .

Our ontology can be used to represent Yahoo! Groups as virtual knowledge communities. We first identify the different roles: regular member, manager and creator. In addition to these three roles, the role of Yahoo! must be added. It serves as a service provider for community hosting and community searching. The number of community creators and community hosts is limited to one by Yahoo! The number of members and of managers is not limited.

The features previously described lead us to describe 29 actions for members, managers and creators: In addition, the action DeleteCommunity that definitely shut the community down is restricted to the creator and to the host. The Yahoo! Groups ontology contains 29+6+1 =36 actions. There are 101 relations roles/actions: 29 × |{M ember, creator, manager}| + 6 × |{manager, creator}| + 1 × |{creator, host}|. Each action has protocols for both sender and receiver. In this case, the host (i.e. Yahoo! Groups) is the only receiver of the actions.

This example has shown the use of VKC ontology in a real-world situation for a well-known and widely used community network. The whole implementation of this ontology in OWL+SWRL would take some time, however our approach would then make it technically possible for SAM agents to acquire some static knowledge as well as some behavior in order to participate in Yahoo! Groups, even if they were not initially programmed for this purpose.

RELATED WORK

To our knowledge, the integration of Virtual Knowledge Communities with Semantic Agents has not been addressed until now. The presented ontology is specifically designed for the Semantic Agent Model. The concept of protocol has been introduced in the ontology to allow SAM agents to execute VKCs. However the set-theoretic formalization of the VKCs and the principal components of the VKC ontology (except the specific design of protocols, dedicated to the Semantic Agent Model) are well suited to be used with other Semantic Agent architectures such as S-APL [START_REF] Katasonov | Semantic agent programming language (S-APL): A middleware platform for the Semantic web[END_REF] or NUIN [START_REF] Dickinson | Towards practical reasoning agents for the semantic web[END_REF]. The ability of agents to exchange community related concepts and behavior decribed with semantic web models (OWL+SWRL) is, to our knowledge, an original proposal.

The SIOC (Semantically-Interlinked Online Communities) ontology is an attempt to link online community sites. Also it uses Semantic Web technologies to describe the structural and content information of communities, and to find related information and new connections between content items and other community items. SIOC is based around the use of machine-readable information which is found on the online community sites4 . Whereas our formalization addresses the way a community works, SIOC provides mechanisms to interlink static data provided by different communities. The VKC formalization and the SIOC ontology can thus be seen as complementary projects of semantic communities.

CONCLUSION

In this paper we have presented an operational ontology for integrating Virtual Knowledge Communities into the world of semantic agents. Using the specificity of the SAM architecture that allows SWRL agent programming, we have formalized Virtual Knowledge Communities as an ontology that contains not only a description of VKCs, but also their related actions to be executed. The link between the descriptive part of the ontology and the implementation is made through the concept of protocols. Protocols are semantic executable code that SAM agents can execute.

In order to formalize VKCs, we first took an abstract approach using a set-theoretic formalization. The process of refining the set-theoretic formalization into an OWL ontology requires few modifications. Since both formalisms are closely coupled (logical foundation of OWL), only the ternary relation requires some modification to be implemented in the OWL ontology. The specificity of OWL, such as inverse relations and restrictions over relations allows to fully describe our formal approach of VKC in an ontology that semantic agents can handle. The decentralized aspect of the community is taken into account with the concept of views of the community. Agents share the domain ontology of VKC, but each agent owns a different view of a community. We illustrated this concept through the example of the minimal commmunity called zero-community. Finally, the Yahoo! Groups helped us to illustrate the generic nature of the ontology. Indeed our ontology is not only designed for VKC but can also be applied to real-world working examples.

Our research has shown that it is now possible for agents to exchange community related concepts and behavior. For that, we use semantic web models (OWL+SWRL). The full convergence of these two models makes the agent more flexible and powerful: it can reason and act with its knowledge without any translation effort (synonym of expressivity loss) and it can learn and adapt to new behavior, which is useful when changing the role and the environment in a community context. Further research will focus on the application of the ontology to different types of communities as well as community benchmarking using our efficiency measure.

Figure 1 :

 1 Figure 1: The SAM [12] architecture

Figure 2 :

 2 Figure 2: sendMessage execution in the community c0

  t2 t1 EKD T (dt) t2-t1 indicates the efficiency average between time t1 and t2. The derivative dEDK T (t) dt

Figure 4 :

 4 Figure Ternary relation. Not native in OWL

•

  Messages: {SendMessage, DeleteMessage} • Photo album: {CreateAlbum, DeleteAlbum, AddPicture, RemovePicture} • File Storage: {CreateFolder, DeleteFolder, AddFile, DeleteFile} • Links directory: {CreateFolderDirectory, DeleteFold-erDirectory, AddLink, DeleteLink, EditerLink} • Polls: {CreatePoll, DeletePoll, AddRéponse, FinVote} • Databases: {CreateTable, DeleteTable, AddValue, Delete-Value} • Members management: {AfficherListe, ViewProfil} • Calendar: {AddEvent, DeleteEvent, EditerEvent} • Advertising: {CreateBoîte} 6 additionnal actions restricted to manager and creator: • Invitation: {InviteMember} • Members management: {ValidateMember, DeleteMem-ber} • Messages management: {ValidateMessage, DeleteMes-sage} • Options: {SetWelcomeMessage}

Table 1 :

 1 List of the concepts of the ontology is linked to its members through the inverse relations mem-berOf and hasMember. Roles are linked to both communities (available roles) and agents (roles in the community). The relation between agent and roles is modeled by memberHas-Role and between role and the community by the relation hasRole and its inverse relation is roleOf. Roles are also linked to actions and protocols through the relations hasAP, hasAction and hasProtocol that represent the ternary relation. Relations are summarized in the table 2.

	Name	Subclass Description
	AP	Thing	Action/Protocol
	Agent	Thing	Agent
	Community	Thing	VKC
	CommunityAction Thing	Action of a community
	LeaderAgent	Agent	Leader agent
	LeaderRole	Roles	Leader role
	Protocol	Thing	Communication protocol
	Role	Thing	Roles
	Topic	Thing	Topic

Table 2 :

 2 List of the relations of the ontology

	• List of members
	• Calendar
	• Advertising: generates HTML code to promote the
	group
	Creators and managers of a group have access to a larger
	range of features in order to administer the community:
	• Invitation: invite new members
	• Members management: validate and delete accounts
	• Messages management: validation and deletion of mes-
	sages
	3 http://fr.groups.yahoo.com

http://rdfs.org/sioc/spec/


Kiran Varanasi
email: kiran.varanasi@inrialpes.fr

Edmond Boyer
email: edmond.boyer@inrialpes.fr

Temporally Coherent Segmentation of 3D Reconstructions

In this paper, we address the problem of segmenting consistently an evolving 3D scene reconstructed individually at different time-frames. The spatial reconstruction of 3D objects from multiple views has been studied extensively in the recent past. Various approaches exist to capture the performance of real actors into voxel-based or mesh-based representations. However, without any knowledge about the nature of the scene being observed, such reconstructions suffer from artifacts such as holes and topological inconsistencies. We explore the problem of segmenting such reconstructions in a temporally coherent manner, as a decomposition into rigidly moving parts. We work with mesh-based representations, though our method can be extended to other 3D representations as well. Unlike related works, our method is independent of the scene being observed, and can handle multiple actors interacting with each other. We also do not require an 'a priori' motion-estimate, which we compute simultaneously as we segment the scene. We individually segment each of the reconstructed scenes into approximately convex parts, and compute their reliability through rigid motion estimates over the sequence. We finally merge these various parts together into a holistic and consistent segmentation over the sequence. We present results on publicly available data sets.

Introduction

Segmentation of meshes is a well-studied problem in computer graphics [14][19] [START_REF] Shamir | A survey on mesh segmentation techniques[END_REF][13] [START_REF] Lien | Approximate convex decomposition of polyhedra[END_REF], because it links skeletal representations that are useful for animation with mesh representations that are useful for rendering. However, most of the proposed approaches deal with smooth meshes that are acquired from artists or from laser-scans of real actors. Computer vision provides alternative methods for obtaining 3D meshes, by multi-view stereo from synchronized and calibrated cameras [12][10] [16]. These methods aggregate silhouette and photometric information from the different views to build 3D meshes. They have a few advantages in that the captured 3D models are true to Figure 1. A temporally coherent segmentation of a sequence of visual hull reconstructions reality at every instant and that the texture information is trivially mapped to the reconstructed geometry.

However, without any knowledge of the scene being observed, these methods produce certain topological and geometric artifacts that are unique to them (figure 2). Topological inconsistencies arise when distinct objects get clubbed as they approach each other. For example, the two legs of a human actor may get clubbed together. Holes are introduced into 3D models because of problems in silhouette extraction. Finally, the obtained meshes are not usually smooth and suffer from local surface distortions due to image and silhouette noise. Please note that explicitly specifying a human model [21] can help resolve some of these ambiguities, but limits the scenes from containing more objects (either human or non-human). In this paper, we address arbitrary 3D scenes with multiple actors. Obtaining a segmentation of such meshes into body parts would be beneficial to realizing various common graphics tasks such as shape editing, animation, motion transfer etc.

Unfortunately, the segmentation approaches proposed in computer graphics are limited in their applicability towards these meshes because of their unique artifacts. For example, those approaches often use surface metrics like curvature or dihedral angles which are sensitive to noise on the meshes. Sometimes, they make restrictive assumptions such as limiting the approach to genus zero shapes [14]. Such assump- A general limitation of model-based approaches is on dealing with unknown scenes, as in the case of multiple interacting actors. We believe that these limitations can be addressed by exploiting the temporal dimension that links these individual reconstructions.

In this paper, we propose an approach to segment such visually reconstructed meshes in a temporally consistent manner. However, we don't assume that a motion estimate is available a priori that links the meshes over the sequence. A few methods already exist for performing the motion segmentation of 3D trajectories [9]. But obtaining such motion estimates is a hard problem in its own right. In a sense, 3D segmentation and motion estimation present a chicken and egg dilemma, with each of these steps depending on the other for improvement. In this paper, we attempt to solve these problems together. The crucial insight we exploit is that the convex segments of a shape usually represent the limbs of its articulation structure, and therefore exhibit rigid motions over time.

The main contributions of our work are (a) a novel algorithm to derive approximately convex segments from a single mesh (a) a method for temporally coherent segmentation of a sequence of visually reconstructed meshes (c) a method for motion estimation of these segments over such a sequence. Since we don't assume that the meshes we work with are of high quality, we don't attempt to align the segment boundaries with mesh concavities. Instead, our motivation is to discover the (possibly overlapping) set of rigid body parts which are reliably detected throughout the sequence. The paper is divided as follows. In section 2, we briefly review the related work. In section 3, we provide an overview of our approach and introduce its various steps which are elaborated in later sections. In section 4, we ex-plain the segmentation of a mesh at a seed frame. In section 5, we explain the process of arriving at a temporally coherent segmentation. In section 6, we provide results from experiments on different data sets. In section 7, we conclude and provide directions to future work.

Related Work

Various functions on the surface have been proposed that are oblivious to pose-changes and articulations. Geodesic distances on the surface of the mesh are invariant to isometry, and can be used for matching surfaces which differ by a non-rigid deformation [4]. However, they are very sensitive to topological changes (which occur often in visually reconstructed meshes). Bronstein et al.[5] use a metric based on diffusion over the surface through a heat kernel, which is less sensitive in this regard. Functions defined on the mesh-volume are more resistant to topological changes. Shapira et al.[19] use the local thickness of the mesh-volume, termed the shape-diameter function, to consistently partition different surfaces over articulations and pose changes. These and other works in the geometry processing community use surface curvature to derive the final segmentation, which is fine for smooth 3D models but is not reliable for visually reconstructed meshes.

Instead of relying on the supposed consistency of a function, a set of objects can be explicitly marked as related and can be segmented consistently. Golovinskiy and Funkhouser[11] have proposed a method that consistently segments sets of objects such as chairs and airplanes. They need point-wise correspondence between the objects, which they obtain by doing a global ICP registration and taking the closest point pairs between objects. Though this approach is powerful, it is not suited to the context of a sequence of meshes as it doesn't exploit the temporal information. In the context of a mesh sequence, de Aguilar et al. [9] use the point trajectories (computed, for example, using [START_REF] De Aguiar | Performance capture from sparse multi-view video[END_REF]) to cluster points into rigidly moving parts.

A graphical model can be used to explicitly match two surfaces differing from a non-rigid deformation [START_REF] Hernandez | Silhouette and stereo fusion for 3D object modeling[END_REF] [20], and these point correspondences can be later used to recover the articulated structure (skeleton) of the shape, as proposed by Anguelov et al. [START_REF] Anguelov | Recovering articulated object models from 3d range data[END_REF]. Chang and Zwicker [6] propose an interesting alternative in the graphical model approach; they compute a putative set of rigid transformations between surface points on two articulated shapes, and treat these transformations (instead of the points themselves) as the labels for the graphical model. These approaches are very powerful but surface matching or motion estimation is a very hard problem, and the results are often inaccurate in the presence of surface occlusions, topological noise and disjoint objects. In this paper, we propose a segmentation algorithm that does not rely on pre-computed correspondences or motion estimates.

Our work is most closely related to that of Cuzzolin et al. [START_REF] Cuzzolin | Coherent laplacian 3d protrusion segmentation[END_REF]. In this work, the authors use locally linear embedding (LLE) to represent a cloud of points and derive a segmentation in this space. The segments are then propagated across time to obtain a temporally coherent segmentation of a voxel-sequence into protrusions of the shape, such as head, hands and legs. Though very powerful, this method cannot be used directly for identifying rigid body-parts (for example, separating the upper-arm from the lower-arm) and for working on disjoint objects (for example, two interacting persons). To the best of our knowledge, nobody has attempted the segmentation of a mesh-sequence with multiple interacting persons reconstructed visually in a multi-camera environment.

Approach Outline

We consider as input a mesh sequence M t∈ [1..n] . Each of the meshes M t is an individual 3D reconstruction of a real scene composed of several actors and objects, and is composed of a set of vertices V t and a set of facets F t . We further represent the volumetric information of the mesh M t by a set of interior points X t . An individual surface point is denoted as v t i ∈ V t and an individual interior point is denoted as x t i ∈ X t . The task is to estimate a set of segments Ψ = {S j } and their rigid transformations over time T t∈ [1..n] j

. Each segment S j is detected at a specific seed-frame t = k and consists of a set of N j surface points. These points are represented by a matrix S k j of size N j × 4, with each column representing a surface point in homogeneous coordinates. The segment points at another frame t are then given by the matrix S t j = T t j * S k j (with T k j = I). An individual segment point in the segment S t j is denoted as s t ji . We say that a set of segments Ψ = {S j } is an ǫ-cover of the mesh sequence if no surface point v t i reconstructed at frame t is farther than a distance of ǫ from the corresponding set of segments {S t j }. i.e,

∀k ∀v t i ∈ V t , M in j Dist(v t i , S t j ) < ǫ (1)
An ǫ-cover yields a temporally coherent segmentation of the sequence by a margin ǫ. In practice, we achieve this by two steps.

1. Convex segmentation of a static mesh : We segment a mesh at a single frame M k into convex segments. We do this by a novel method of finding visibility clusters in the mesh volume (section 4).

Temporally coherent segmentation of a sequence :

We perform the above step at multiple randomly sampled frames in the mesh sequence. We estimate the reliability of each segment by registering it along the Algorithm 1: Convex Segmentation of the Surface Input: a surface mesh M = (V, F) Output: a set of convex segments {S j∈ [1..m] ⊂ V} Obtain a set of interior points X for the mesh M; Initialize the set of free points X F = X ; Sort X F according to a function ρ; i = 0; while X F is not empty do Select the top element of X F as the viewpoint w i ; Compute the visible volume

V V i from w i ; Remove all points x ∈ V V i from X F ; Decompose V V i into convex segments {S j }; i = i+1; end Figure 3.
Algorithm for convex segmentation of a mesh whole sequence and computing the registration error (section 5.1). We then devise an algorithm for building an ǫ-cover of the sequence from the above set of segments. (section 5.2).

Segmentation into Convex Parts

In this section, we describe our method of extracting convex segments from a 3D scene M k = (V k , F k ) reconstructed at a particular frame k. Since we deal with the static case, we eschew the superscript and denote the mesh by just M = (V, F). As mentioned in section 1, meshes reconstructed from images suffer from a huge amount of geometric and topological noise (figure 2). Surface based metrics such as point curvature or geodesic distances between points are not reliable over such meshes. In our method, we use volumetric information represented by interior points of the mesh close to the medial axis, which are more resistant to these artifacts. It is to be noted that computing the medial axis exactly is not trivial in 3D, but we aim only to estimate a cloud of interior points. We associate every surface vertex on the mesh v ∈ V with one or more interior points x ∈ X . We define the problem of convex segmentation of the surface points V as the segmentation of the interior point set X .

We consider two interior points x and y to be visible from each other if the line joining them doesn't intersect any mesh facet in F. From a selected interior point w i ∈ X (termed the viewpoint), we compute the set of visible interior points V V i ⊂ X using this definition. As illustrated in the figure 4, this visible volume constitutes one or more convex segments. Our algorithm 3 for convex segmentation rests on this observation.

We first compute the set of interior points X and spatialhash them for easy access. We initiate by marking all of them as free and sort them according to an ordering function ρ. A simple choice for ρ is the random-ordering function, another choice is mentioned later in section 4.4. We pop out the top element in the ordered free set X F as the viewpoint w i and compute its visible volume V V i . We decompose V V i into a set of convex segments {S j }, tag every point with the corresponding segment, and remove the tagged points from the free set X F . We repeat the algorithm until the free set X F is empty. In the following, we explain these steps in detail.

Estimation of interior points

Our objective is to obtain a set of uniformly sampled interior points close to the medial axis. We adopt a method similar in principle to the one described by Shapira et al. [19]. For each point on the surface v , we shoot a cone of rays opposite to the normal and identify their points of intersection with the surface. We compute the median length of these line segments as the shape diameter. We then trace a vector from v opposite to its normal with half this length, and call it the medial vector at v. After we compute medial vectors at every surface point, we perform spatial smoothing such that neighboring points have similar medial vectors. These medial vectors map the set of surface points V to a set of interior points X . We spatial-hash these interior points for easy access, and construct a k-nearest neighbor graph (termed the medial graph) on this point set. Here, we would like to note that X need not be as densely sampled as V; interior points can be constructed for only a subset of the surface points. For each interior point x, we associate a set of surface vertices (termed the surface ring) that are close to it in any direction.

Computation of a visible volume

Given a specific viewpoint w from which to compute the visible-volume, we first order the set of interior points in a medial tree based on the shortest path from w on the medial graph. As illustrated in figure 5, this tree has w at the root and captures well the underlying structure of the shape as seen from w.

We then compute the visible surface from w by checking for each surface point v if the line joining v with w intersects any mesh-facet from F. This computation may be performed rapidly by spatially hashing the mesh facets. We then descend the medial tree computed in the earlier step by accumulating interior points if their associated surface ring is entirely visible. When a non-visible surface point is encountered, we mark the corresponding interior point t as an occluding tip. We chop the medial tree at that point (figure 5-b) and don't grow any further. This way, we build a visible volume from the given viewpoint w, which is usually convex, but can be a star-shaped structure in the general case (as illustrated in figure 6). As can be seen in the figure, the boundary of the visible surface can be distinguished into a self-occluding part and a non-occluding part. While the former separates convex segments from each other, the latter is non-informative about the structure of the shape. It is the self-occluding boundary that prompts decisions in our algorithm. After the algorithm to identify the visible volume is terminated, we compute its extent δ e as the largest distance across any two points inside. If this value is very small, we reject the visible volume as For rarer and more complex shapes, this process of convex decomposition may need be performed recursively. too small to be significant. Otherwise, we proceed to the next step.

Convex decomposition of a visible volume

A visible volume is shaped as a star, and may contain multiple convex segments (as can be seen in the figure 6).

Here we describe how to decompose the visible volume into its constituent We first the tips of the visible volume by identifying the set of points which are locally maximal in their neighborhood with respect to the distance from the viewpoint w. The occluding tips discovered as explained in the earlier section are also added to this set.

We then compute a Boolean compatibility graph between the tips based on whether the surface ring associated with each tip is completely visible from the other. If all the tips are mutually compatible with each other, we mark the visible volume as convex and terminate the algorithm. Otherwise, we make each tip as a new viewpoint and recursively compute its visible volume, but this time restricted only to the star-shaped volume visible from the parent viewpoint w. If all the tips are accounted for and there still remains a stub of unassigned points, we mark this stub as an independent convex segment. At the end of this recursive procedure, the visible volume is decomposed into a unique set of convex segments.

Since we deal with noisy meshes reconstructed from images, we test only for approximate convexity and not exact convexity. In practice, this means we use certain thresholds in (1) identifying tips and (2) testing for compatibility between tips. For (1), we perform non-maximal suppression in detecting tips, and don't return a tip within a distance of δ 1 from another tip. For (2), we consider two tips as being incompatible only if there exists a pair of points v a , v b

Heuristics for choosing viewpoints

Our algorithm correctly identifies convex segments irrespective of where the viewpoints are placed. However the algorithm is faster when all the tips of the visible volume are mutually compatible, thereby returning just one convex segment. Such cases are more probable when the viewpoint is placed close to the potential tip of the visible volume. In articulated figures such as human bodies, protrusions such as hands and legs can be detected easily, by computing the average geodesic distance from a point to every other point on the mesh (figure 9-a). The protrusions of a shape come out as local maxima of this function. We use this function as the sorting function ρ algorithm 3.

Temporally Coherent Segmentation

We use the above algorithm to obtain convex segments at multiple frames in the mesh sequence. We denote the holistic set of segments obtained as P. These segments usually identify body parts, but not all of them are equally reliable. Clothing and occlusions create artifacts in the visual reconstructions, making segment-boundaries appear at places not corresponding to body parts (figure 8). Further, distinct body parts may be clubbed together into a single (a) (b) Figure 8. Limitations of static segmentation : (a) due to loose clothing, the left thigh merges with the torso (b) the upper arms get merged with the torso due to reconstruction artifacts segment either due to an articulation (the upper and lower leg joined together into a single segment) or due to an artifact in reconstruction (the hand clubbed together with the stomach as it approaches closely). Such segments are technically convex, but remain so only in one or few frames. In this section, we describe a method for rejecting such segments and identifying ones which are consistent with the entire mesh sequence. To achieve this, we estimate the motion of each segment over the entire sequence. We observe that the convex segments of a mesh usually correspond to the articulated parts of a body and thus, their motion can be approximated as rigid.

Reliability estimation

We take the surface point cloud S k j of a convex segment S j detected at frame k. We estimate the motion of this point cloud as a set of rigid transformations T t∈ [1..n] over the entire sequence. To do this, we iteratively register the segment's point cloud to the mesh points in the neighboring frames using the ICP algorithm [START_REF] Besl | A method for registration of 3-d shapes[END_REF]. As the 3D video is captured at a good frame-rate (around 10 to 20 fps), neighboring frames are sufficiently close to each other, justifying the application of the ICP algorithm.

We accelerate the ICP algorithm by using spatial kd-tree organization. When we select closest points for registration, we reject matches between points with widely discrepant surface normals. As observed by Pulli [17], this is an efficient strategy for eliminating outliers in the registration. Since the ICP algorithm is based on local search, it doesn't find good matches across large movements. Following Shapira et al.[19], we use the two mesh features introduced in the earlier section (a) the average geodesic distance, which helps in detecting surface protrusions and (b) the shape diameter which gives the thickness of the volume (figures 9-a and 9-b). We reject matches between points with discrepant values for these features, this strategy helps us find better matches than simple closest point search. We used simple geometric registration for ICP, even though more complicated methods exist that account for photometric information or scene-flow. We consider the success of registration along the sequence as an estimate of reliability for a convex segment. For each point s k ji in S k j , we compute its estimated position at frame t as s t ji = T t * s k ji . The discrepancy d(s t ji ) in this estimate is computed as the least distance to the mesh vertices reconstructed at frame t.

d(s t ji ) = M in a ||T t j * s k ji -v t a || (2)
If this value is more than ǫ, we note the point to be lost in registration at this frame. Points that are lost several times during the registration are unlikely to be part of the actual segment. We prune the segment by removing such points from the border of the segment as outliers (figure 10). In certain cases, not just a few, but a vast chunk of points in the segment suffer from discrepancies ≥ ǫ. We discard such segments altogether as incorrect. For each remaining segment S j , we compute its size as the total number of mesh vertices in {V t∈ [1..n] } that are within the margin ǫ to its estimated position at the corresponding frame S t j . We sort the various segments in P according to their size in ascending order.

Building an ǫ-cover

We construct P by performing static segmentation on multiple randomly chosen frames. It is normally sufficient to segment just 3 to 5 frames, because many segments shall be detected repeatedly in all the frames. Following equation 1, a temporally coherent segmentation is given by an ǫcover of segments chosen from P. We take a greedy approach to obtain this.

We maintain the current set of accepted segments Ψ and gradually add new segments into it from P (Ψ is started out as empty). At each stage, We pop out the top element S j in the sorted set P and check if it overlaps with any of the accepted segments S a in Ψ. We call a point s ji in S j at seed-frame t = k to be within the ǫ-margin of a segment S a , if it is within the distance of ǫ from the estimated positions of any of the points in S k a . We run this test from all accepted segments, and mark the points in S j that are within the ǫ-margin of a prior segment. Examples are shown in figure 11-a,b. We define the overlap between two segments S j and S a as the fraction of points in S j at its seed-frame t = k that are within an ǫ-margin of S k a . If this overlap is large, we detect S j as a repetition of S a and proceed to the next segment. Due to the nature of the algorithm, it is the smallest of the segment repetitions that is acknowledged, the rest are discarded. This yields tighter segments, as can be seen in figure 11-c,d.

If, on the other hand, no overlap is detected for segment S j with any of the earlier segments, then Ψ is augmented by adding S j to it. This process is terminated When every surface point in the mesh-sequence is acknowledged to be within an ǫ-margin of one or more segments of Ψ. The set of segments Ψ now defines an ǫ-cover for the sequence.

Results

We tested our approach primarily on visual hull reconstructions from multiple view silhouette data1 . These silhouettes are extracted from real images taken through a synchronized camera setup in an indoor setting. The dance and flashkick sequences (figures 1 and 13-a) present fast movements of limbs that are difficult to be tracked.The kids and juggle sequences (figures 12 and 13-b) show human-human and human-object interactions respectively. In such interactive scenarios, it is very difficult to obtain prior knowledge of the scene, and hence difficult to make assumptions on the number of actors and the topology of these shapes. Our algorithm segments these scenes without making any such assumptions.

There are certain limitations for our approach. One interesting case is detailed in figure 14. The algorithm fails to track the juggler's club properly. When the club leaves the juggler's hand, our algorithm fails to follow the club and registers its points on the hand of the juggler. Then when a new and different club approaches the hand, our algorithm registers these points onto the new club. The features that we use are not discriminative enough to handle cases like these, and the limitations of the ICP registration are manifest. In general, without a global model for tracking, it is difficult to track segments correctly for long sequences. This is especially true for small segments that are not sufficiently distinctive.

Conclusion

In this paper, we presented a novel algorithm for coherently segmenting a sequence of visually reconstructed meshes without making any assumption on the type, number or topology of the objects in the scene. Once such segments are identified, they can provide a basis for learning the spatio-temporal model of the scene. Several potential applications await here to be explored. Our algorithm for registration is currently based on the ICP algorithm, and is thus limited to small displacements. In future work, we would like to overcome this limitation through stronger and more discriminative features for matching.

Figure 2 .

 2 Figure 2. A 3D mesh of a juggler holding clubs, reconstructed from multiple view silhouettes. Visible artifacts of reconstruction (a) the clubs merged with the hands (b) the two feet merged together (c) spurious noise on the surface

Figure 4 .Figure 5 .

 45 Figure 4. Computation of visible volume, conceptualized in 2D : the viewpoints are colored green, the occluding boundary (o1,o2,o3) are colored red and the non-occluding boundary (n1,n2,n3) are colored blue. Change of viewpoint doesn't affect the occluding boundary. Interior points are shown with their surface rings indicated as line-segments traversing the volume, An interior point is considered visible if only its entire surface ring is visible. The two view points yield the same set of visible interior points.

Figure 6 .

 6 Figure 6. Convex decomposition of a visible volume : (a) The visible volume from the view point is not a convex segment, but a star shaped structure. The viewpoint is colored green, and the protruding tips of the star are colored dark blue. (b) Visible volumes are then computed from each tip of the star, which run into occluding boundaries (colored red). A convex segment is identified per each tip (colored gray), and the remaining stub of the visible volume (colored white) becomes an independent convex segment.For rarer and more complex shapes, this process of convex decomposition may need be performed recursively.

Figure 7 .

 7 Figure 7. Convex segments at a static frame : (a)(b)(c) individual segments (d) color-coded representation of all the segments found

Figure 9 .

 9 Figure 9. (a) The average geodesic distance (b) The shape diameter function. Warmer colors mean higher values in both the figures

Figure 10 .Figure 11 .

 1011 Figure 10. Reliability Estimation of Segments : (a) (c) -the segments detected at their seed-frames, (b) -outlier points with high discrepancy are pruned from the borders of (a), (d) segment is discarded after too many discrepancies in registration from (c). Points with higher discrepancy are shown in warmer colors -the red points are the outliers.

Figure 12 .

 12 Figure 12. Tracking of a rigid component in a point cloud of diverse objects

Figure 13 .

 13 Figure 13. Temporally coherent segments on sequences (a) flashkick (b) kids

http://4drepository.inrialpes.fr