Tej Dallej
email: tdallej@yahoo.fr

Nicolas Andre

Philippe Martinet

Contribution to generic modeling and vision-based control of a broad class of fully parallel robots

Keywords: Visual Servoing, Control, Modeling, Parallel Robots, Kinematics

This paper deals with a generic modeling and vision-based control approach for a broad class of parallel mechanisms. First, a generic architecture representing several families is proposed. Second, inspired by the geometry of lines, a generic dierential inverse kinematic model according to the proposed generic structure is introduced. Finally, based on the image projection of cylindrical legs, a kinematic vision-based control using legs observation is presented. The approach is illustrated and validated on the Gough-Stewart and Par4 parallel robots.

Introduction

The coupling between visual servoing techniques [START_REF] Dallej | 3D pose visual servoing relieves parallel robot control from joint sensing[END_REF] and parallel robots is becoming increasingly important and has been the subject of several studies. Essentially, kinematic vision-based control generates a Cartesian desired velocity, which is converted into joint velocities by the dierential inverse kinematic model. The latter is usually an analytical model in the case of parallel robots. The dierential inverse kinematic model also depends on the Cartesian pose, [START_REF] Angeles | Fundamentals of Robotic Mechanical Systems: Theory, Methods, and Algorithms[END_REF][START_REF] Merlet | Parallel robots[END_REF] which needs to be estimated.

Authors in refs. [6, 7] have been among the rst to introduce vision-based control for parallel robots. The interesting point of the aforementioned approaches is the use of vision in the feedback control for regulation. [START_REF] Corke | Robotics, Vision and Control[END_REF] However, the used parallel robots are designed with particular mechanical structures to have an analytical forward kinematic model. Consequently, the dierential inverse kinematic model turns out to be dependent on the end-eector pose estimated using the forward kinematic model and joint values.

In actuality, the formulation of the parallel robot forward kinematic model [START_REF] Husty | An algorithm for solving the direct kinematics of general Gough-Stewart platforms[END_REF] is generally dicult to solve and gives several possible poses for the end-eector. [START_REF] Merlet | An algorithm for the forward kinematics of general 6 d.o.f parallel manipulators[END_REF] To make the control robust with respect to modeling errors, vision replaces the forward kinematic model in the feedback with a camera measurement. This method can also be used to simplify dierent models of the control scheme. [START_REF] Corke | Robotics, Vision and Control[END_REF] Amongst the various visual servoing techniques, 3D pose visual servoing [START_REF] Wilson | Relative end-eector control using cartesian position-based visual servoing[END_REF][START_REF] Thuilot | Position based visual servoing: keeping the object in the eld of vision[END_REF] can be applied to parallel robots. In ref. [13], a generic 3D pose visual servoing of six degrees of freedom (DOF) Gough-Stewart platform (Fig. 1) was proposed. In this kinematic control, the end-eector pose, indirectly measured, was used in the feedback control and in the dierential inverse kinematic model.

Image Based Visual Servoing (IBVS) was also applied to parallel robots [START_REF] Qi | Improved image based visual servoing with parallel robot[END_REF][START_REF] Palmieri | A comparison between position-based and image-based dynamic visual servoings in the control of a translating parallel manipulator[END_REF] using endeector observation. This method does not require the model of the visual target or the end-eector pose. However, the method has diculties with large rotational motion. [START_REF] Chaumette | Potential problems of stability and convergence in image-based and position-based visual servoing[END_REF] The main limitation of visual servoing of parallel robots focused on the observation of a visual target is that it requires the estimation of the end-eector to tool transformation, the world to base transformation and the entire kinematic parameter set. Moreover, it is not wise to consider observing the end-eector of a machining tool. It may be incompatible with various applications.

It is noticeable that the state of a parallel robot is any representation of the end-eector pose. A new way to use vision which gathers the advantages of redundant metrology [START_REF] Barron | The on-line directs kinematics of parallel manipulators under joint-sensor redundancy[END_REF][START_REF] Tancredi | Forward kinematics of a parallel manipulator with additional rotary sensors measuring the position of platform joints[END_REF] and visual servoing was presented in ref. [19]. This method was proposed to control the well-known six degrees of freedom (DOF) Gough-Stewart platform using legs observation. This proposed approach has a reduced set of kinematic parameters and does not require any visual target. The orientation of the robot's legs was chosen as visual primitives. The control law was based on their reconstruction from the image which might not be very accurate for intrinsic reasons. To improve the practical robustness by servoing the legs in the image, it was proposed in ref. [20] to servo leg edge rather than leg orientation. The proposed method was extended to Par4 [START_REF] Dallej | Visual servoing of par4 using leg observation[END_REF] and I4L 22 robots (Fig. 1 and Fig. 2). In ref. [23], the authors suggested a dynamic control via leg edges of a parallel robot taking into account all relevant aspects of leg edges observation.

The notion that the legs can contain the state of a parallel robot leads the way towards an innovative approach in which modeling, calibration [START_REF] Renaud | Kinematic calibration of parallel mechanisms: a novel approach using legs observation[END_REF] and control are interlaced. In addition, it can permit a better representation of a parallel robot. References [25, 26], show that observing the direction of the parallel robot's legs involves controlling the displacement of a hidden robot. The latter has up to eight assembly modes that are dierent from those of the real live robot. First, the method shown in ref. [19] was used for control. Afterwards, based on the kinematic modeling of the hidden robot, the singularity problem of the controller was studied and controllability information of the parallel robot was given.

In our opinion, a generic solution for controlling any parallel robot should take into account the specic kinematic properties of parallel robots and the observable kinematic elements. This solution does not require any additional visual target. The terminology of a kinematic element was rst introduced in ref. [27] in order to nd geometric and kinematic properties which can be applied to many parallel robots. The indicated representative Generic modeling and vision-based control of parallel robots 3 kinematic chain is made up of at least one kinematic element which is composed of two rigid bodies linked by a Prismatic joint (xed or moving joint).

The notion of a kinematic element is then fully formalized in ref. [28] and an interesting mathematical model of a kinematic element was given. The proposed method gives a linear dynamic modeling of parallel robot from observable kinematic elements. It relies on a body-oriented representation of observable rectilinear kinematic structures. However, the modeling and control of parallel robots on a kinematic level were not clearly and fully studied. In addition, the proposed modeling method in ref. [28] was illustrated on a simple 2 degrees of freedom (DOF) ve-bar mechanism which is an RRR-RR structure planar parallel robot. Some discussion about the extension to a broad class of parallel mechanisms would have been more interesting, complete and generic.

Condent that one can fuse kinematics and projective geometry into a projective kinematic model for control and inspired by the geometry of lines and the image projection of cylindrical legs, this paper has three main goals: r to propose a generic structure of the kinematic chains and the nacelle 2931 (an articulated set of elements having xed length and containing the moving platform). It is a general way to nd generic parallel robot structure corresponding to a broad class of fully parallel robots, e.g. the Gough-Stewart Platform, the H4, [START_REF] Pierrot | H4: A new family of 4-dof parallel robots[END_REF] the I4R, [START_REF] Krut | A high-speed parallel robot for scara motions[END_REF] the Par4 31 (Fig. 1) and the I4L [START_REF] Krut | I4: A new parallel mechanism for scara motions[END_REF] (Fig. 2). r to provide a thorough study of modeling and kinematic vision-based control derived according to a generic methodology taking into account the proposed generic parallel robot structure. The edges of the last elements (referent elements) attached to the nacelle are used in the servo loop and in the kinematic visual servoing law. We will conrm that, measuring by vision the referent elements edges, one can easily measure a projective kinematic model for control without proprioceptive sensors, which might simplify the robot design. r to present a coherent representation of a broad class of fully parallel robots, in which one can fuse a generic architecture, the kinematic modeling and referent elements observation.

The paper is organised as follows: Section 2 presents a comparative study of some existing parallel robots. The aim is to nd similar points and to introduce a generic architecture. Based on some assumptions and the structures of dierent parallel robot families, section 3 presents a generic architecture of a broad class of fully parallel robots with one actuated joint. It is composed of the kinematic chains architectures and the nacelle including the moving platform. Section 4 introduces the concept of the observable referent kinematic elements. The projection of cylindrical elements in the image gives the visual primitives used for the edge-based control. Section 5 explains the generic dierential inverse kinematic model according to the proposed generic structure. A kinematic visionbased control using referent elements observation is then presented in section 6. Section 7 presents experimental validations on the Gough-Stewart platform and the Par4 robot. A discussion and conclusions are presented in sections 8 and 9, respectively.

Structure of some parallel robot families

As we plan to propose a generic architecture which unies several families of parallel robots, specic kinematic properties of a broad class of parallel robots must be found. The generic unied method must be able to be used for more than one type of parallel robot to prove the validity of the proposed approaches. Consequently, this section deals with a comparative study of some existing parallel robots. The main objective is to nd a common representation and to introduce a generic architecture for a broad class of parallel robots. This classication is based on the presence or absence of a Prismatic joint in each kinematic chain. [START_REF] Renaud | Kinematic calibration of parallel mechanisms: a novel approach using legs observation[END_REF][START_REF] Gaoa | New kinematic structures for 2-, 3-, 4-, and 5-DOF parallel manipulator designs[END_REF] Throughout the paper, the notations given in Table I will be used.

Generic modeling and vision-based control of parallel robots

First family

The rst family includes robots whose actuated Prismatic joint is located between two rigid bodies of the kinematic chain. For example, the Gough-Stewart platform (Fig. 3) is a six degrees of freedom parallel mechanism. It has 6 kinematic chains [A 1i A 2i ] with varying lengths L(r 1i ) = r 1i , i ∈ 1..6 due to the actuated Prismatic joints located at P 1i .

The kinematic chains of a standard Gough-Stewart platform are attached to the base by Universal joints (located at points A 1i ) and to the moving platform by Ball joints located at points A 2i . The moving platform of the Gough-Stewart robot is made up of a single element S attached to each kinematic chain at point A 2i .

A 1i A 2i P 1i r 1i .
. E S Fig. 3. A real Gough-Stewart platform and its representative Sketch.

Table I . Notations.

r Boldface characters denote vectors or matrices. Unit vectors are underlined.

r i T j = i R j i t j 0 1
is the homogeneous matrix associated to the rigid transformation from frame F i to frame F j . r i v is vector v expressed in frame F i . r K is the matrix of the camera's intrinsic parameters. r q 0i denes the rst actuated joint of kinematic chain i. r q denes the vector of all actuated joints. r j τ i = j V i j Ω i T is the Cartesian velocity (linear and angular velocities) of F i expressed in and with respect to F j . It can be minimally represented by i V j when the components of the Cartesian velocity are less than 6. r M + is the pseudo-inverse of M. r M is the estimation of M based on measurements. r [a] × is the cross-product matrix of vector a. r An element with constant length of a kinematic chain is equivalent to two rigid bodies linked by a xed Prismatic joint (Fixed joint).

r A kinematic element is considered as two rigid bodies linked by a Prismatic joint (xed or moving joint).

r Each kinematic chain can be composed of one or more kinematic elements. r i = 1..n denotes the kinematic chains (legs), m = 0..1 denotes the kinematic elements which form the kinematic chain and j = 1..2 denotes the edges of each observable cylindrical kinematic element. r The camera frame is xed with respect to the base frame. r A nacelle 2931 is made of an articulated set of kinematic elements (with a xed length). Only one of these elements is considered as the moving platform of the robot.

r In some cases, a nacelle can be composed of one element (with a xed length) which is the moving platform.

r The associated variables for each joint are r ki for Prismatic joint , α ki for Revolute joint, (α ki , β ki )

for Universal joint and (α ki , β ki , γ ki ) for Ball joint, with k = 0..2.

Generic modeling and vision-based control of parallel robots 5

Second family

The second family includes robots which have one or two kinematic elements with a xed length and an actuated Prismatic joint between these elements and the base. It includes, for instance, the Orthoglide robot, [START_REF] Wenger | Kinematic analysis of a new parallel machine tool: The orthoglide[END_REF] the Isoglide-4 T3R1 [START_REF] Gogu | Fully-isotropic T3R1-type parallel manipulator[END_REF] and the I4L [START_REF] Krut | I4: A new parallel mechanism for scara motions[END_REF] (Fig. 2).

2.2.1. The Orthoglide robot. The Orthoglide is a 3-DOF translational parallel manipulator. It consists of three identical kinematic chains attached to the base at points P 0i by three actuated and orthogonal Prismatic joints. Upon analyzing in more detail the architecture of the Orthoglide (Fig. 4), one can consider a rst kinematic element [A 0i A 1 1i ] with variable length l(r 0i ), i ∈ 1..3. It is connected to the articulated parallelogram composed of two elements

[A 1 1i A 1 2i ] and [A 2 1i A 2 2i
] with a xed length L(r 1i ) = L (Fig. 4). 2.2.2. The I4L robot. The I4L robot is composed of 4 actuated Prismatic joints. Each linear motor located at P 0i moves the kinematic element

[P 0i A 1 1i ]. One can consider a rst element [A 0i A 1 1i ] with variable length l(r 0i ), i ∈ 1..4.
Each kinematic element is connected to an articulated parallelogram (forearm) equipped with ball joints

(A 1 1i , A 1 2i )
and

(A 2 1i , A 2
2i ) (Fig. 5). The state of the forearm can be dened using points

A 1 1i or A 2 1i
and A 1 2i or A 2 2i , respectively. The rotation of moving platform S is due to the relative displacement of the two nacelle parts S 01 = S 02 and S 03 = S 04 (Fig. 5), using two rack-and-pinion systems. The relative translation T is transformed into a proportional end-eector rotation θ = T/K, with K as the transmission ratio. It should be observed that each kinematic chain i is attached to a nacelle element S 0i which is directly attached to moving platform S at D 0 or D 1 .

Third family

In the third family, there is no actuated Prismatic joint in the kinematic chains. It includes the H4, the I4R and the Par4 (Fig. 1). All these robots have only actuated Revolute joints. H4, I4R and Par4 robots are based on four identical kinematic chains (Fig. 6, Fig. 7, Fig. 8 and Fig. 9). Each revolute motor located at A 0i moves arm i with a xed length l(r 0i ) = l, i ∈ 1..4. Each arm is connected to a forearm (parallelogram) made up of two structures equipped with ball joints

(A 1 1i , A 1 2i ) and (A 2 1i , A 2 2i
). The axis passing through the two upper ends (or the lower extremities) of this parallelogram keeps the same direction. The state of the forearm can be dened using points A Each forearm is connected at each end to the articulated nacelle. The end-eector frame located at E can be translated in three directions and rotated around a xed axis c z e .

A 0i P 1i L P 0i l A 2i 2 A 1i 2 A 1i 1 A 2i 1

Contribution to a generic architecture of a broad class of fully parallel robots

To join together a broad class of fully parallel mechanisms in the same generic architecture, a contribution to a generic structure of the kinematic chains and a generic representation of an articulated nacelle will be discussed in this section. Only the manipulators having the following characteristics will be considered:

Generic modeling and vision-based control of parallel robots r Fully parallel robot: the number of controlled degrees of freedom of the end-eector is strictly equal to the number of kinematic chains and just one actuator exists in each kinematic chain. 5, 36 r There are only two elements in each kinematic chain. Each element is composed of two rigid bodies linked by a Prismatic joint (xed or actuated moving joint).

The majority of existing parallel mechanisms are designed with a reduced number of kinematic chain elements compared to serial structures. Since each kinematic chain is usually short and based on the comparative study of some existing parallel robots shown in Section 2, we will restrict the proposed generic architecture to four serial rigid bodies (two serial kinematic elements as dened in Table I) in each kinematic chain. It is suce from our point of view to describe a broad class of fully parallel robots. r The joint between two kinematic elements of the kinematic chain must be a Ball, Revolute or Universal joint.

The main reason for this assumption is due to the fact that each kinematic element can be composed of two rigid bodies linked by a Prismatic joint. Consequently, the standard joints (Ball, Revolute, Universal and Prismatic joint) are therefore represented in each kinematic chain. r The joint between the last element and the nacelle including the moving platform can be a Ball, Revolute or Universal joint. This is motivated by the fact that a Prismatic joint directly attached to the nacelle is, generally, excluded. An actuated Prismatic joint mounted at or near the xed base (and not the moving platform) is more interesting for rigidity and high-speed. Additionally, a passive Prismatic joint attached to the nacelle is dicult to control. r The joint between the rst element and the base can be a Revolute or a Fixed joint.

Either joint can ensure rigidity and good kinematic behaviour of the robot because we have introduced enough degrees of freedom between the two kinematic elements (Ball, Revolute or Universal joint), between the last element and the nacelle (Ball, Revolute or Universal joint) and between rigid bodies of each element (Prismatic joint). r Each kinematic chain of a parallel robot has at least one Prismatic joint which must be a xed or actuated joint.

A passive Prismatic joint should not be used because it is dicult to control. In addition, a fully parallel robot does not include a kinematic chain with two actuated joints (in some cases, two actuated Prismatic joints).

Contribution to generic architecture of the kinematic chains

Based on the previous assumptions and structures of parallel robots presented in section 2, a representative architecture of a broad class of fully parallel robots is shown in Fig. 10. The articulated nacelle is connected to the base by n kinematic chains. Each chain

[A 0i A 2i ] is composed of 2 serial kinematics elements [A mi A (m+1)i ],
(m = 0..1 and i = 1..n). In such conditions, this architecture is composed of: The generic architecture in Fig. 10 unies several families of parallel robots. As shown in Table II, one can easily nd the Gough-Stewart platform by taking l(r 0i ) = 0 (the length of the rst element of each kinematic chain) and an Universal joint at A 1i = A 0i . The Prismatic joint with an axis passing through P 1i provides the variation of the length L(r 1i ).

r 4 rigid bodies, in each kinematic chain, [A 0i P 0i ], [P 0i A 1i ], [A 1i P 1i ] and [P 1i A 2i ]. r 5
Based in the characteristics of several families of parallel robots, following constraints must be satised: r The actuator of each kinematic chain is located at A 0i or P 0i or P 1i . The two other passive joints are xed. This is due to the fact that the actuated joint mounted at or near the xed base (and not the moving platform) is more interesting for two reasons. First, this conguration reduces the moving platform mass associated with the actuation. Second, it is also a more convenient way to design a parallel robot with low inertia, high load and high speed. r For each kinematic chain, the actuated joint at A 0i or P 0i or P 1i will be denoted q 0i . It may be a Prismatic or a Revolute joint.

Fully parallel robots are designed with only one actuated joint in each kinematic chain.

The conventional actuators are revolute or linear joint mechanisms.

Table II . Illustration of the generic structure.

Generic Architecture Gough-Stewart platform

A 0i
Revolute or Fixed joint Fixed joint

P 0i
Prismatic or Fixed joint Fixed Prismatic (Fixed) joint

A 1i
Ball or Revolute or Universal joint Universal joint

P 1i
Prismatic or Fixed joint Prismatic joint

A 2i
Ball or Revolute or Universal joint Ball joint

l(r 0i ) l(r 0i ) or constant constant L(r 1i ) L(r 1i ) or constant = 0 L(r 1i ) Par4/I4R/H4 Orthoglide/I4L A 0i
Revolute joint Fixed joint

P 0i
Fixed Prismatic (Fixed) joint Prismatic joint

A 1i
Ball joint Ball joint

P 1i
Fixed Prismatic (Fixed) joint Fixed Prismatic (Fixed) joint

A 2i
Ball joint Ball joint

l(r 0i ) constant l(r 0i ) L(r 1i ) constant constant
Therefore, one can write the actuated joint q 0i as:

q 0i = λ i α 0i + λ i (µ i r 0i + µ i r 1i ) (1)
where

r µ i = 1 -µ i and λ i = 1 -λ i . r µ i = 1 if joint at P 0i is actuated . r µ i = 0 if joint at P 1i is actuated .
Generic modeling and vision-based control of parallel robots r λ i = 1 if joint at A 0i is actuated . r λ i = 0 if joint at P 0i or at P 1i is actuated .

In the case of an unactuated joint at P 0i and P 1i , µ i can take the value 0 or 1. This conguration is denoted by . It denotes an indeterminate value.

Contribution to a generic representation of a nacelle

The majority of existing parallel robots are designed with a nacelle composed of one rigid body, which is a compact solid containing the end-eector E and the moving platform S (Fig. 11). It is linked to each kinematic chain at A 2i (e.g. the case of the Gough-Stewart and the Orthoglide robot). The nacelle can be also composed of several elements 29 S 0i and S (Fig. 11). Several research studies have proven that combining a parallel robot and an articulated nacelle (e.g. H4, 29 I4L, [START_REF] Krut | I4: A new parallel mechanism for scara motions[END_REF] the I4R [START_REF] Krut | A high-speed parallel robot for scara motions[END_REF] and the Par4 [START_REF] Nabat | Par4: Very high speed parallel robot for pick-and-place[END_REF] ) is a good alternative for high-speed pick and place operations and obtaining unlimited rotation of the tool around one xed axis.

In order to propose generic representation of a fully parallel robot nacelle, let us consider the following classications: r First family:

This family includes nacelles composed of one rigid body (e.g. Gough-Stewart, Orthoglide [START_REF] Wenger | Kinematic analysis of a new parallel machine tool: The orthoglide[END_REF] , Agile Eye, [START_REF] Gosselin | The agile eye: A high performance three-degree-of-freedom cameraorienting device[END_REF] the Hexapteron [START_REF] Seward | A new 6-dof parallel robot with simple kinematic model[END_REF] ). This family also contains the nacelle of the fully-isotropic parallel robot. 35 r Second family:

In this family one can nd articulated nacelles of parallel robots with Schoenies motions [START_REF] Schoenies | Geometrie der Bewegung in Synthetischer Darstellung[END_REF][START_REF] Hervé | The lie group of rigid body displacements, a fundamental tool for mechanism design[END_REF] (also called 3T1R parallel robots or SCARA motions). The used nacelle is made up of at least 2 articulated bodies (e.g. H4, 29 I4L, [START_REF] Krut | I4: A new parallel mechanism for scara motions[END_REF] the I4R [START_REF] Krut | A high-speed parallel robot for scara motions[END_REF] and the Par4 31 ).

In general cases, articulated elements of the nacelle are restricted to be coplanar. The nacelle has only translational motion. However, the relative motion of the articulated elements of the nacelle turns the moving platform around an axis of xed direction, using an amplication system. The proposed study is limited to a nacelle made up of n bodies S 0i (i = 1..n) and one central rigid body S. For each kinematic chain i, the rst element S 0i contains A 2i and the second one S contains the end-eector E. Table III presents nacelles of a broad class of parallel robots according to the generic representation in Fig. 11.

As shown in Fig. 11, one can write: The I4R robot Kinematic chain i

S 0i S D 0i 1 [A 21 D 0 ] [D 0 E] D 0 2 [A 22 D 0 ] [D 0 E] D 0 3 [A 23 E] [ED 0 ] E 4 [A 24 E] [ED 0 ] E The I4L robot Kinematic chain i S 0i S D 0i 1 [A 21 D 0 ] [D 0 E] D 0 2 [A 22 D 0 ] [D 0 E] D 0 3 [A 23 D 1 ] [D 1 E] D 1 4 [A 24 D 1 ] [D 1 E] D 1
The choice of an appropriate joint between S 0i and S centered at D 0i can be made taking into account the rigidity and a good kinematic behaviour of the parallel mechanism. Thus, a movement of the solid S 0i must generate a movement of S, at least according to a well-dened axis (the rotation based on the Schoenies motions). A Prismatic joint has to be avoided, since a movement of S 0i along the axis of the joint does not move S. Consequently, the rotational movement of S 0i may only be linear depending on the rotation of the moving platform S (case of gears, pulley and belt, chain and gears or side by side movement transmissions).

Taking into account the characteristics of the nacelle, one can write in the xed camera frame F c :

   c V D0i∈S = c V D0i∈S0i c Ω 0i = c Ω e (3)
where is the transmission ratio between the two rotational velocities of S and S 0i .

It should be noted that: r = 1 if the nacelle is representing a single and compact solid ( c Ω 0i = c Ω e ). r = 0 if there is no rotational movement of S 0i with respect to xed camera frame F c ( c Ω 0i = 0 3X1 ).

Applying the velocity composition law expressed in F c , one can formulate:

dA2i dt = c V A2i = c V D0i∈S0i + c Ω 0i × c ----→ D 0i A 2i dD0i dt = c V D0i∈S = c V e + c Ω e × c ---→ ED 0i (4)
Generic modeling and vision-based control of parallel robots From ( 3) and ( 4), one can compute:

c V A2i = c V e + c Ω e × c ---→ ED 0i + c Ω 0i × c ----→ D 0i A 2i (5)
Consequently, using (3) and ( 5), one can write the following generic relation:

c V A2i = I 3 -[ c ---→ ED 0i + c ----→ D 0i A 2i ] × c τ e = G 1 2i c τ e (6)
where:

G 1 2i = I 3 -[ c ---→ ED 0i + c ----→ D 0i A 2i ] × (7)
Two signicant cases can be deduced: r The kinematic elements of nacelle S and S 0i are rigidly xed to a single and compact solid (the case of Gough-Stewart platform and the Orthoglide robot), which is the moving platform ( = 1). One can write:

c V A2i = I 3 -[ c ---→ EA 2i ] × c τ e (8)
r There is no rotational movement of S 0i with respect to xed camera frame F c ( = 0). However, S has a rotational movement with respect to xed camera frame F c (in the case of the nacelle of H4, Par4, I4R and I4L robots). Consequently, one can write:

c V A2i = I 3 -[ c ---→ ED 0i ] × c τ e (9)

Vision-based kinematic using referent edges observation

The majority of existing parallel mechanisms are designed with slim and cylindrical legs between their base and their moving platform. Thus, one can consider these legs as straight lines for kinematic analysis. [START_REF] Merlet | Parallel robots[END_REF] In this section, we will show that referent elements can be observed to extract, directly from the image, the edges used as visual primitives.

According to the nature of visual primitives, we will also show that one can have an optimal representation of the state of a parallel robot.

Line representation

Let L be a 3D line (Fig. 12). A point-independent representation of this line is the Plücker coordinates (u, n) 41 (also known as normalized Plücker coordinates since us u is a unit vector), where u is the direction of the line and n encodes its position. However, noticing that n is orthogonal to the so-called interpretation plane dened by L and the origin, one can split it into two parts: the unit vector n dening the interpretation plane and its norm n which is the orthogonal distance of L to the origin.

Projection of the cylindrical referent element in the image

The closest element i to the nacelle is chosen as the referent element of each kinematic chain. By observing each referent cylindrical element, one can extract the edges n j i with j = 1, 2 associated to the lines' projections in the image plane (Fig. 12). The line's image projection could be represented by the normal vector n j i (j = 1, 2) to the so-called interpretation plane associated to each edge j.

Such a projected line in the image plane, expressed in the camera frame F c , has the following equation: With the intrinsic camera matrix K, (10) can also be expressed in the image frame as:

im n j i T im p j i = im n j i T K c p j i = 0 (11)
Using ( 10) and ( 11), one can easily obtain the conversion from the line equation in the camera frame c n j i to the same conversion in the pixel coordinates im n j i :

   im n j i = K -T c n j i K -T c n j i c n j i = K T im n j i K T im n j i (12)
Consequently, one can deduce the direction c u i of each cylinder 42 from (12):

c u i = c n 1 i × c n 2 i c n 1 i × c n 2 i ( 13
)
Moreover, consider point P i lying on the cylinder axis i (Fig. 12), the edge j of each cylinder is dened by the following constraints, expressed in the camera frame:

       c n j i T c u i = 0 c n j i T c n j i = 1 c n j i T c P i = c n j i T ( c p j i + c ---→ p j i P i ) = c n j i T ( c p j i + λ j R c n j i ) = λ j R (14)
where λ 1 = λ 2 = ±1 and R is the radius of cylinder i.

The last constraint means that the edges are located at a distance R from the cylinder's axis (Fig. 12).

The observation of the referent element and the state of a parallel robot

Two edges can be extracted using cylindrical referent element observation. These edges are directly used in the control loop and in a dierential kinematic model. This reference element is characterized by the reference direction u i and a length L(r 1i ) which can be either variable L(r 1i ) or constant L(r 1i ) = L, but never zero. A 1i and A 2i are the lower and upper extremities of this element. The lower extremity can be dened using all joint positions of the kinematic chain A 1i (α 0i , r 0i , ξ geom ), where ξ geom is a kinematic parameter. The upper extremity depends on the pose X of the end-eector A 2i (X, ξ geom ).

Generic modeling and vision-based control of parallel robots

The referent element [A 1i A 2i ] of the kinematic chain i can eectively represents the state of parallel robot. Thus, using the constraints ( 14) applied to point A 2i , one can write the following formula:

c n j i T c A 2i (X, ξ geom ) = λ i R c A 2i = c A 21 (X, ξ geom ) + c ----→ A 21 A 2i (X, ξ geom ) (15)
The end-eector X can be represented by the axis-angle representation ( c u e , c θ e ) of a rotation c R e and the translation vector c t e . Consequently, one can solve a system with 7 unknown variables represented by c u e , c θ e and c t e components.

A unique solution of the following system can be computed using constraints in ( 15) applied to at least 4 kinematic chains:

                               c n 1 1 T c A 21 (X, ξ geom ) = λ 1 R c n 2 1 T c A 21 (X, ξ geom ) = λ 1 R c n 1 2 T ( c A 21 (X, ξ geom ) + c -----→ A 21 A 22 (X, ξ geom )) = λ 2 R c n 2 2 T ( c A 21 (X, ξ geom ) + c -----→ A 21 A 22 (X, ξ geom )) = λ 2 R c n 1 3 T ( c A 21 (X, ξ geom ) + c -----→ A 21 A 23 (X, ξ geom )) = λ 3 R c n 2 3 T ( c A 21 (X, ξ geom ) + c -----→ A 21 A 23 (X, ξ geom )) = λ 3 R c n 1 4 T ( c A 21 (X, ξ geom ) + c -----→ A 21 A 24 (X, ξ geom )) = λ 4 R c n 2 4 T ( c A 21 (X, ξ geom ) + c -----→ A 21 A 24 (X, ξ geom )) = λ 4 R (16)

Generic dierential inverse kinematic model

According to the generic architecture presented in section 3, the main objective of this section is to fuse kinematics and projective geometry into a generic projective dierential kinematic model for control, which can have the following form:

  q u ṅ   =   D inv e M inv e L inv e   τ (17)
where D inv e , M inv e and L inv e are the joint kinematic matrix, the Cartesian kinematic matrix associated to the directions and the Cartesian kinematic matrix associated to the edges, respectively.

The kinematic chains' closure around the reference element [A 1i A 2i ] (Fig. 10) yields, for each kinematic chain i, the following kinematic model in generic vector form:

L(r 1i )u i = ----→ A 1i A 2i = A 2i (X, ξ geom ) -A 1i (α 0i , r 0i , ξ geom ) (18)
where X is a representation of the end-eector pose.

Assuming that the kinematic parameters ξ geom are constants, time dierentiating of the kinematic model (18) gives:

L(r 1i )u i + L(r 1i ) ui = (19)
d dt (A 2i (X, ξ geom )) - d dt (A 1i (α 0i , r 0i , ξ geom ))
Time dierentiating of L(r 1i ), A 2i and A 1i provides:

             d dt (L(r 1i )) = ∂L(r1i) ∂r1i ṙ1i d dt (A 2i ) = ∂A2i ∂X L X τ d dt (A 1i ) = ∂A1i ∂α0i α0i + ∂A1i ∂r0i ṙ0i (20)
where L X is the matrix relating time dierentiating of the Cartesian pose to the Cartesian velocity. [START_REF] Angeles | Fundamentals of Robotic Mechanical Systems: Theory, Methods, and Algorithms[END_REF] One can rewrite (19) as:

L(r 1i ) ui = G 1 2i τ + G 0 1i α0i + G 1 1i ṙ0i + G 2 1i ṙ1i (21)
where

r G 1 2i = ∂A2i
∂X L X is the interaction matrix associated to the 3D point A 2i expressed in (7) (see Section. 3.2 for more details).

r G 0 1i = -∂A1i ∂α0i , G 1 1i = -∂A1i ∂r0i and G 2 1i = -∂L(r1i)
∂r1i u i are joint kinematic matrices.

Dierential inverse kinematic model associated to the actuated joints

In the case of a parallel robot with one actuated joint q 0i in each kinematic chain, the vector of the joint velocities q is obtained from the individual joint velocity q0i . The dierential inverse kinematic model associated to all actuated joints expressed in the camera frame F c can have the following formula:

q = D inv e c τ e (22)
Assuming that only one joint variable (α 0i , r 0i or r 1i ) is used in (21), one can write:

L(r 1i ) c ui = (23)
G 1 2i c τ e + G 0 1i α0i + G 1 1i ṙ0i + G 2 1i ṙ1i ≡ G 1 2i c τ e + G 1i q0i
where G 1i depends on q 0i (see section 3.1 and ( 1)) and has the following generic equation:

G 1i = λ i G 0 1i + λ i (µ i G 1 1i + µ i G 2 1i ) (24)
Since c u T i c ui = 0, (23) gives the dierential inverse kinematic model associated to

q 0i : q0i = - c u T i G 1 2i c u T i G 1i c τ e = D inv ei c τ e (25)
where D inv ei is the individual matrix (row vector) of D inv e . 5.2. Dierential inverse kinematic model associated to directions Using (23) and (25), the dierential inverse kinematic model associated to directions u i can be written as:

c ui = 1 L(r 1i ) (I 3 - G 1i c u T i c u T i G 1i )G 1 2i c τ e = M i c τ e (26)
where

M i = 1 L(r1i) (I 3 - G1i c u T i c u T i G1i )G 1 2i is the individual matrix of M inv e .
Generic modeling and vision-based control of parallel robots

Dierential inverse kinematic model associated to edges

The time derivative of constraints in ( 14) applied to point A 2i induces a rst dierential inverse kinematic model associated to the edges expressed in the camera frame and has the following equation: 20

c ṅj i = (R j 1i G 1 2i + R j 2i M i )τ = c L j i c τ e (27)
where

                 R j 1i = - ( c u i × c n j i ) c n j i T c A T 2i ( c u i × c n j i ) R j 2i = -(I 3 - ( c u i × c n j i ) c A T 2i c A T 2i ( c u i × c n j i ) ) c u i c n j i T c L j i = R j 1i G 1 2i + R j 2i M i (28)
where M i is dened in (26) and G 1 2i is dened in (7). This proves that the movement of the platform depends linearly on the variation of the movement of A 2i represented by G 1 2i and on the dierential inverse kinematic model associated to directions M i .

A second dierential inverse kinematic model associated to edges expressed in the image frame can also be computed. As a results one needs to present the interaction matrix im L j i relating the Cartesian velocity c τ e to the time dierentiating of the edge vector of each referent element im ṅj i expressed in the image frame:

im ṅj i = im L j i c τ e (29)
where im L j i is the individual matrix of L inv e .

im L j i can be written as a product of two matrices:

im L j i = im J c c L j i ( 30
)
where im J c is associated to the camera-to-pixel change of frame:

im ṅj i = im J c c ṅj i (31)
According to ref. [20], im J c can be written as:

im J c = K T im n j i (I 3 -im n j i im n j i T )K -T (32)
6. Visual servoing using referent elements observation

Error to servo

The generic control law is based on the observation of referent elements and the extraction of the visual primitives s j i = im n j i used for regulation. We choose to minimize the error e j i between the edge in the current position im n j i and the edge in a desired position im n j i * . First, the control law gives the Cartesian velocity according to the error. The dierential inverse kinematic model associated to the joints will then provide the joint velocities.

The error to servo [START_REF] Andre | Image-based visual servoing of Gough-Stewart parallel manipulators using legs observation[END_REF][START_REF] Dallej | Visual servoing of par4 using leg observation[END_REF] is:

e j i = im n j i × im n j i * (

Generic control law

Time derivative of (33) gives:

ėj i = im ṅj i × im n j i * = -[ im n j i * ] × im ṅj i (34)
Using (29), one can compute:

ėj i = N j i c τ e (35)
where

N j i = -[ im n j i * ] × im L j i ( 36
) Taking into account an exponential behaviour of the error ( ė = -λ p e), (35) gives:

c τ e = -λ p N + e (37) where N is a compound matrix from the associated individual interaction matrices N j i and λ p is a constant parameter.

Inserting (37) into ( 22) delivers the nal generic control law:

q = -λ p c D inv e N + e (38)
7. Experimental validations

Experimental context

The proposed approaches are validated on the Gough-Stewart Platform and the Par4 robot. By providing an interface with Linux-RTAI, the kinematic control of the Gough-Stewart platform and the Par4 robot is ensured using ViSP library [START_REF] Marchand | Visp for visual servoing: a generic software platform with a wide class of robot control skills[END_REF] for extracting edges, tracking and matrix computation. Each robot is observed by a perspective camera (1024x780 pixels, IEEE1394) xed with respect to the base reference frame. The camera is placed in front of the robot legs so that it can cover the robot workspace (Fig. 13 and Fig. 14). The direction c x p0i of each arm is a unit vector. Each arm has a rotational movement around c z p0i , with angle q 0i = α 0i .

It should be noted that:

r c A 0i and c ----→ A 2 1i A 1 1i = -H c z p0i are constants. r l(r 0i ) = l. r c A 1 1i = c A 0i + l c x p0i + 1 2 c ----→ A 2 1i A 1 1i . One can compute: d( c A 1 1i ) dt = l d dt ( c x p0i ) = q0i l c y p0i (41)
where c y p0i = c z p0i × c x p0i Table V presents the Par4 models according to the generic model (see section 3 and section 5). 7.3.2. Experimental results. The par4 robot is asked to reach the desired pose (Fig. 14) obtained from the initial conguration by a translation along the three axes and a rotation around the c z axis. Fig. 16 shows that the edge errors and the Cartesian velocities converge to 0. An experimental test was performed using approximately 15-20 FPS, IEEE1394 camera. This is largely sucient to prove the validity of the proposed approaches. As shown in Fig. 16, one can see that the maximum speed is approximately equal to 0.012 m/s in translation and 0.042 rad/s in orientation. Notice that one can use a high speed camera (e.g. Rolling Shutter Camera) to achieve a high-speed vision-based control [START_REF] Ozgür | High Speed Parallel Kinematic Manipulator State Estimation from Legs Observation[END_REF] and to improve speed and acceleration values. Recently, the real-time vision-based control, the analysis and the real-time trajectory tracking control validated on a real parallel robots, e.g. 4547 , have attracted more interests. Actuators in each kinematic chain 1 In the kinematic modeling of the Par4 robot shown in Table V, one needs to estimate points A 1 1i . The rst option is to use redundant sensors to measure q 0i = α 0i and to compute

µ i 0 or 1 λ i 1 q 0i α 0i A 1i A 1 1i 0 Nacelle Articulated elements and c Ω 0i = 0 G 0 1i -l c y p0i G 1 1i 0 G 2 1i 0 G 1i -l c y p0i G 1 2i ( I 3 -[ c ----→ D 24 D 0i ] × ) 0
c A 1 1i = c A 0i + l c x p0i + 1 2 c ----→ A 2 1i A 1
1i . This method is not always technically feasible. It has been shown in ref. [48] that these parameters can be measured using only vision in the case of the I4R robot. Moreover, it was shown that one can get rid of the joint values in the same movement. In this paper, the same method is used in the case of Par4 robot. The edges and constraints (14) deriving from the image projection of the cylindrical referent elements are used to measure c u i and A 1 2i . Finally, c A 1 1i can then be deduced from (40) without proprioceptive sensors.

Discussion

It should be noted that the observation of the cylindrical referent kinematic elements by a single perspective camera causes a self-occlusion problem since the legs in the background of the image may be hidden by those in the foreground (Fig. 13). Moreover, the perspective projection of some referent elements appears nearly parallel in the image, which is a noise sensitive conguration for the direction extraction. In ref. [44], a way to solve the occlusion problem is to turn to an observable portion of the line representing the cylindrical leg edge which can be enough for visual tracking. Omnidirectional camera can also overcome these problems since it provides a 360 degree eld of view of the surroundings. Placed between the legs, it provides a more convenient observation of the lines. [START_REF] Dallej | Kinematic calibration of a gough-stewart platform using an omnidirectional camera[END_REF][START_REF] Tahri | Visual servoing of gough-stewart platform using omnidirectional camera[END_REF] An alternative solution is to observe only the m n observable legs among the n legs of the parallel robot (m n <n). [START_REF] Andre | Vision-based control of a Gough-Stewart parallel mechanism using legs observation[END_REF] As shown in ref. [26], the minimal number of observed legs (m n ) should be, for 3D unit orientations vectors, an integer greater than n/2.

Let us now consider the case of a referent kinematic element having another shape such as a parallelepiped, a portion of a cone, square pyramid or cuboid. Dierent points can be discussed here. The rst step is to choose the visual primitives (edges, lines, faces) and the vision system (perspective, omnidirectional or stereo camera) to use in the control. Afterwards, the constraints in Section 4 (Eqs. ( 10), ( 13) and ( 14)) should be modied and adjusted to t each shape and can then be used to compute the direction and the dierential inverse kinematic model associated to visual primitives. In some cases, dierent edges and faces of shapes are not observable. Dierent techniques like shape detection or tracking using contours can be used to avoid this problem.

The previously mentioned issues can be the subject of several future studies. Once these points are studied, they can improve our approach and make it even more generic.

Conclusion

This paper presented a generic modeling and vision-based control of a broad class of parallel robots designed with cylindrical legs and one actuated joint. A generic architecture composed of a generic representation of the kinematic chains and the nacelle was rst introduced.

Based on the geometric specications of each kinematic chain and the nacelle, a generic projective kinematic model was examined. Inspired by the geometry of lines, this model relies on the kinematic specicity of the last kinematic elements (referent kinematic elements) attached to the nacelle. This modeling method turns out to be dependent on the mobile platform position and the orientation of referent elements. According to the same generic methodology which is applied to the geometric and kinematic model, a vision-based control was introduced. The image projection of the referent element of the robot was used as feedback signal.

The main advantage of the proposed approaches is that modeling and control are unied according to a coherent representation of parallel robots, in which one can fuse a generic architecture, the kinematic modeling, referent kinematic elements observation and control, for several types of parallel robots. Furthermore, we do not require the use of an additional visual pattern to calibrate the relative pose of the latter with respect to the end-eector.

The proposed generic architecture is based on the characteristics of dierent parallel robot families and some assumptions, such as an actuated or passive joint, the number of actuators and the number of kinematic elements in each kinematic chain. Despite these assumptions, we proved that a broad class of parallel robots (section II) can be included in this architecture. The modeling and control proved to be well founded in experimental validations on two dierent families of parallel robots (Gough-Stewart platform and a Par4 robot) presented in this paper.

The proposed generic control is based on the referent kinematic elements observation. Three Cartesian kinematic matrices are computed in generic form: the joint kinematic matrix, the Cartesian kinematic matrix associated to the referent kinematic elements' direction and the Cartesian kinematic matrix associated to the edges (see section V Generic modeling and vision-based control of parallel robots for more details). We do agree that studying the convergence properties of this control algorithm could be very signicant. The goal is to nd the region of attraction of the controller (global or local), since this is a pure pseudoinverse control law. Authors in ref. [26] studied the controllability of parallel robots using only the visual servoing of leg orientation in Cartesian space. In this case, the Cartesian kinematic matrix associated to the edges shown in Section 5.3, was not considered in the control law. Based on the Hidden robot concept, authors proved that a global dieomorphism between the Cartesian space and the leg direction space does not always exist. They also certied that the robot did not converge to the local minima, through the application of tools developed for the singularity analysis of robots.

However, research studies in ref. [20] have proven that servo edges might be very accurate than servo orientation for intrinsically geometrical reasons. In this paper, a generic representation of the approach in ref. [20] was proposed. The mapping between the edges and the observed elements' directions (the Cartesian kinematic matrix associated to the edges) is shown in Section 5.3. Hence, part of our future studies will be dedicated to the extension of the approach to other classes of parallel robots and to the study of the controllability of parallel robots using edge-based visual servoing in image space.

Fig. 1 .

 1 Fig. 1. From left to right: the Gough-Stewart platform (Institut Pascal), the H4 and the Par4 robots (LIRMM).

Fig. 2 .

 2 Fig. 2. From left to right: the Orthoglide (IRCCyN), the Isoglide-4 T3R1 (IFMA) and the I4L (LIRMM) robots.

r

  F b = (O, x b , y b , z b ), Fe = (E, x e , y e , z e ), Fc = (Oc, x c , y c , z c ) and F pmi = (P mi , x pmi , y pmi , z pmi ) denote the base, end-eector, camera and i th kinematic element reference frames, respectively.

Fig. 4 .

 4 Fig. 4. Sketch of the Orthoglide.

Fig. 5 .

 5 Fig. 5. Top view of the I4L robot (left) and its nacelle (right).

Fig. 6 .

 6 Fig. 6. H4, I4R and Par4 kinematic chain parameters.

Fig. 7 .

 7 Fig. 7. Top view of the H4 robot (left) and its nacelle (right).

Fig. 8 .

 8 Fig. 8. Top view of the I4R robot (left) and its nacelle (right).

Fig. 9 .

 9 Fig. 9. Top view of the Par4 robot (left) and its nacelle (right).

Fig. 10 .

 10 Fig. 10. A generic kinematic chain architecture of a broad class of parallel robots.

=Fig. 11 .

 11 Fig. 11. Generic representation of the articulated nacelle (left) and the nacelle composed of one rigid body (right).

Fig. 12 .

 12 Fig. 12. Projection of a cylinder in the image (Left) and a projection of a 3D line representation.

33 ) 1 T e 2 1 T 1 n

 33111 Taking into account that the proposed generic architecture is composed of n kinematic chains, the vector of all errors is e = e 1 ... e

Fig. 13 .

 13 Fig. 13. A photograph of a Gough-Stewart platform (left) and a current conguration seen from the camera (the desired conguration is in the background).

7. 2 .

 2 Experimental validation on a Gough-Stewart Platform 7.2.1. The Gough-Stewart platform model according to the generic structure model. In the case of the Gough-Stewart platform, the two extremities of the referent element are A 1i and A 2i (see Fig.3and Fig.10). Notice that A 1i is a constant parameter ( d( c A1i) dt = 0).

Fig. 15 .

 15 Fig. 15. Visual servoing of the Gough-Stewart platform: edge errors and Cartesian velocity.

Fig. 16 .

 16 Fig. 16. Visual servoing of Par4 robot: edges errors and Cartesian velocity.

  groups of joints shown in TableII: two joints (Prismatic or Fixed joint) at P mi , two joints (Ball, Universal or Revolute joint) at A 1i and A 2i and one joint (Revolute or Fixed joint) at A 0i .

Table III .

 III Illustration of the generic architecture of the nacelle.

	The Gough-Stewart platform Kinematic chain i 1 2 3 4 5 6 The H4 or the Par4 robot Kinematic chain i 1 2 3 4	S 0i [A 21 A 21 ] [A 22 A 22 ] [A 23 A 23 ] [A 24 A 24 ] [A 25 A 25 ] [A 26 A 26 ] S 0i [A 21 D 21 ] [A 22 D 21 ] [A 23 D 24 ] [A 24 D 24 ]	S [A 21 E] [A 22 E] [A 23 E] [A 24 E] [A 25 E] [A 26 E] S [D 21 D 24 ] [D 21 D 24 ] [D 24 D 21 ] [D 24 D 21 ]	D 0i A 21 A 22 A 23 A 24 A 25 A 26 D 0i D 21 D 21 D 24 D 24

Table V .

 V The Par4 models.

c A 2i = c E + c ---→ ED 0i + c ----→ D 0i A 2i(2)

Generic modeling and vision-based control of parallel robots

The length of the referent element

. The kinematic model in vector form (18) can be written as:

Table IV gives the characteristics of the Gough-Stewart platform models deduced from the proposed generic model (see section 3 and section 5). Actuators in each kinematic chain 1

7.2.2. Image-based visual servoing results. To evaluate the control approach, the Gough-Stewart platform is asked to reach a desired pose (Fig. 13) obtained from an initial conguration. Therefore, Fig. 15 presents the evolution of the unit-less errors in the image and the Cartesian velocities. The errors converge exponentially to 0 with a perfect decoupling from an initial position to the desired one. The convergence errors are essentially due to the accuracy level of the edges' extraction. The position of the vision sensor (Fig. 13) does not allow the same precision on all referent kinematic elements, which generates measurement sensitivity. ] with length L(r 1i ) = L (see Fig. 6 and Fig. 10). The kinematic model ( 18) can be written as: (40)


Julien Roussel

François Labarthe

Jérôme Thireau

Fabio Ferro

Charlotte Farah

Jérôme Roy

Masahisa Horiuchi

Martine Tardieu

Bruno Lefort

Jean François Benoist

Carnitine deficiency induces a short QT syndrome

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche


Harry Sevi

Gabriel Rilling

Pierre Borgnat

MODELING SIGNALS OVER DIRECTED GRAPHS THROUGH FILTERING

Keywords: Graph signal processing, random walks, filtering

published or not. The documents may come

INTRODUCTION

The interest in the analysis and exploitation of data represented by graphs is becoming increasingly significant, partly due to the affluence of such data in various fields such as neurosciences, biology or social networks. To better process, analyze and exploit these graph data, developing relevant and efficient mathematical and computational methods is helpful.

In recent years, a new mathematical framework has been developed called graph signal processing [START_REF] David I Shuman | The emerging field of signal processing on graphs: Extending highdimensional data analysis to networks and other irregular domains[END_REF][START_REF] Sandryhaila | Discrete signal processing on graphs[END_REF][START_REF] Ortega | Graph signal processing[END_REF]. The aim of this framework is to generalize the fundamental concepts of classical signal processing, such as filtering, Fourier transform or wavelets, and it considers graph data as a signal on graph.

A main challenge of graph signal processing is the determination of a suitable Fourier basis for signals on a directed graph. A few approaches have emerged, either based on Jordan's decomposition of the adjacency matrix [START_REF] Sandryhaila | Discrete signal processing on graphs: Frequency analysis[END_REF] or recently constructed through non-convex optimization problems [START_REF] Shafipour | A digraph fourier transform with spread frequency components[END_REF][START_REF] Sardellitti | On the graph fourier transform for directed graphs[END_REF]. Recently, we have proposed an appropriate frequency analysis based on the eigenvectors of the random walk operator, showing that they constitute a new Fourier-type basis for signals defined on directed graphs [START_REF] Sevi | Multiresolution analysis of functions on directed networks[END_REF].

We focus on a problem of signal modeling, where we learn a model that allows the reconstruction of a signal's miss-This work was supported by the ANR-14-CE27-0001 GRAPHSIP grant and the ACADEMICS Grant in the Scientific Breakthrough Program of the IDEXLYON.

ing values given a small number of known values. This problem is related to the semi-supervised learning framework [START_REF] Zhu | Semi-supervised learning literature survey[END_REF], except we assume the whole signal known to learn the model. Hence, our model would be better suited for instance for a lossy compression application. Here, the focus is rather on the comparison of different models based on different graph signal processing frameworks. The problem can be studied using the graph Laplacian [START_REF] Zhu | Semi-supervised learning with graphs[END_REF] whose main limitation is to apply only to undirected graphs with real and non-negative edges, or a graph signal processing framework based on the adjacency matrix [START_REF] Sandryhaila | Discrete signal processing on graphs[END_REF].

We develop signal modeling on directed graphs, leveraging directed graph signal processing using random walks [START_REF] Sevi | Multiresolution analysis of functions on directed networks[END_REF]. We show how to learn the parameters of a polynomial filter based on the random walk operator to model a signal, then how it allows us to recover it when it is only partially known, on a small number of vertices. We also consider other reference operators combining the random walk and its reversed version. We study numerically, on an example based on the political blogs dataset [START_REF] Lada | The political blogosphere and the 2004 us election: divided they blog[END_REF], the efficiency and advantage of the proposed approaches, and compare them to existing works.

RANDOM WALKS ON DIRECTED GRAPHS

Let G " pV, Eq be a weighted directed graph with cardinality |V| " N . The graph G is represented by its weighted adjacency matrix A " ta ij u 1ďi,jďN P R N ˆN `. We assume that G is strongly connected.

A random walk [START_REF] Brémaud | Markov chains: Gibbs fields[END_REF] on G is a (possibly non-reversible) Markov chain X " pX n q ně0 on the finite state space V. From a graph theory point of view, the random walk operator P P R N ˆN `is defined as P " D ´1A, where D " diagtd 1 , ¨¨¨, d N u, the diagonal matrix of the out-degrees of the vertices and A the adjacency matrix, with d i " ř N j"1 a ij , for all i " 1, ¨¨¨, N .

We assume throughout this paper that the random walk X is ergodic, that is irreducible and aperiodic [START_REF] Brémaud | Markov chains: Gibbs fields[END_REF]. Consequently, the random walk X admits a unique stationary distribution π [START_REF] Brémaud | Markov chains: Gibbs fields[END_REF]. We define the time reversed ergodic random walk X ˚with stationary distribution π [START_REF] Montenegro | Mathematical aspects of mixing times in markov chains[END_REF] characterized by the following operator

P ˚" Π ´1P J Π,
where Π " diagtπ 1 , ¨¨¨, π N u is the diagonal matrix of the stationary distribution.

From the non-reversible X , with transition matrix P and unique stationary measure π, it is known how to construct the additive reversibilization [START_REF] Allen | Eigenvalue bounds on convergence to stationarity for nonreversible markov chains, with an application to the exclusion process[END_REF] of X , whose transition matrix is the average between P and its time reversed P ˚. It is expressed as

P " P `P2 . (1)
P is reversible with unique stationary distribution π.

A novelty here is to define and consider the more general class P of convex combinations between P and P ˚:

P "

"

Pα : Pα " p1 ´αqP `αP

˚ˇα P r0, 1s * . (2)
The elements Pα P P are non-reversible except for α " 1{2, namely P1{2 " P. Still, they share the same stationary distribution π, and we will show that it can be useful to consider them as reference to defined filters on directed graphs.

PARAMETRIC MODELING OF GRAPHS SIGNALS

In this section, we consider a way of modeling the relationships between values of a graph signal using a graph filter. The model is expressed as a graph filter that takes a few values of the graph signal and reconstructs the other values. A possible application of such a model could be the lossy compression of the signal, where knowing only the graph, the coefficients of the graph filter and a few signal values enable the reconstruction of the whole signal.

Problem formulation

A graph filter H is expressed as a polynomial finite sum of a reference operator R, that is

H " K ÿ k"0 θ k R k , θ k P R, @k " 0, ¨¨¨, K. (3)
The coefficients of the graph filter are learned by solving the following optimization problem:

p θ " argmin θ"tθ k u K k"0 PR K`1 E " }f 0 ´K ÿ k"0 θ k R k Y } 2 µ  , (4)
where f 0 is the original graph signal, Y " rY 1 , ¨¨¨, Y N s J P 2 pV, µq is a multivariate random variable indexed on the vertex set V. The random variables Y k , k " 1, ¨¨¨, N can be expressed as Y k " ε k f 0k , where the ε k are assumed independent and Bernoulli distributed with parameters δ k : ε k " Berpδ k q. The random variable ε defined as

ε " 1 N N ÿ i"1 ε i , (5)
is the proportion of known values of f 0 in Y . Y can be viewed as a random sampling of the graph signal f 0 and HY as a reconstruction of f 0 from these samples. The optimization problem (4) corresponds to the minimization of the reconstruction error given such a set of random samples.

Solution of the problem

The solution of ( 4) can be expressed as

p θ " Z ´1MQ J f 0 ,
with M " diagtµ 1 , ¨¨¨, µ N u, Z the matrix where each entry Z k is expressed as

Z k " Tr `rR k s J MR EpY Y J q ˘, @tk, u P v0, Kw 2 ,
and Q " rq 0 , ¨¨¨, q K s P R N ˆpK`1q where each vector q j is q j " R j EpY q, @j P v0, Kw.

The resulting estimation of the filter is

p H " K ÿ k"0 p θ k R k , p θ k P R, @k " 0, ¨¨¨, K. (6)

AN EXPLORATION OF MODELING ACCURACY WITH DIFFERENT GRAPH OPERATORS

The reconstruction quality using the previous approach depends on several factors: the choice of reference operator R, the order of the filter K and the random sampling strategy defined by the Bernoulli parameters δ k . Here, we evaluate primarily the influence of R and compare two possible sampling strategies.

As an example, we consider the dataset of the political blogs of the 2004 US presidential campaign [START_REF] Lada | The political blogosphere and the 2004 us election: divided they blog[END_REF]. The dataset consists of 1224 political blogs where each political blog has a political orientation, either republican or democrat. This dataset is modeled as a directed graph G " pV, Eq where each vertex v P V corresponds to a blog and an edge between two vertices tv i , v j u indicates the presence of hyperlinks from the blog associated to the vertex v i to the vertex v j . This graph is unweighted. The political orientations of blogs are modeled by a graph signal f 0 " tf 0 pv 1 q, ¨¨¨, f 0 pv N qu where each vertex v i has a label f 0 pv i q P t´1, 1u characterizing its political orientation.

Reconstruction accuracy

Graph signal reconstruction symmetrized version of G'

A sym P sym The directed graph G associated to the political blogs is not strongly connected. In our theoretical framework, we only consider strongly connected graphs. Hence, we will first consider the largest strongly connected subgraph of G, denoted by G 1 " pV 1 , E 1 q which is made up of |V 1 | " N 1 " 793 vertices (roughly 65% of the vertex set V) and its associated graph signal f 1 0 . In 4.3, we will extend the method to G. As the chosen signal takes values only in t´1, 1u, we will compare the reconstruction accuracy using a proportion of correctly reconstructed labels obtained via f " signp p HY q.

Signal modeling on G 1

In this section, we solve the problem (4) by learning a polynomial graph filter with K " 10 on G 1 . We consider various possible reference operators: those for directed graphs, in the set C " tA norm , P, Pu where A norm is a normalized version of the the adjacency matrix whose spectral norm is equal to one, P the random walk operator and P its additive reversibilization; and those for undirected (or symmetrized) graphs, in the set C " tA sym , P sym u where A sym is the normalized version of the symmetrized adjacency matrix pA ÀJ q{2 and P sym the random walk operator based on A sym . The random variables Y j , j " 1, ¨¨¨, N 1 are distributed in one of the two following cases: Case 1: Random variables Y j " ε j f 1 0 pv j q where ε j " Berppq with p the proportion of known labels.

Case 2: Random variables Y j " ε j f 1 0 pv j q where ε j " Berpαπ j q, such that ř j Epε j q " pN 1 with p the proportion of known labels.

The proportions of correctly reconstructed labels are measured for various p values using 500 realizations of Y .

Numerical simulations: Case 1

We evaluate the reconstruction performance of the graph signal f 1 0 in figure 1. For all proportions p of known labels, the average rate of correctly reconstructed labels in the graph signal f 1 0 from a learned polynomial graph filter of P or P is significantly better than the one based on a learned polynomial graph filter of A norm in the case where we consider either the subgraph G 1 or its symmetrized version. Furthermore, the reconstruction performance using a filter based on P is slightly better than using a filter based on P.

Numerical simulations: Case 2

The reconstruction performance is shown in figure 2. We observe a significantly better performance using a filter based on P or P than based on A norm in the case where we consider either the subgraph G 1 or its symmetrized version and a slightly better performance using P rather than P. We notice the reconstruction performance based on A norm has a large variability and even decreases for larger p.

Case 1 vs. Case 2

The reconstruction performance using a filter based on P or P is slightly better when the samples in Y are selected according to a distribution proportional to the stationary distribution π (case 2) than when the distribution is uniform (case 1). This is expected as vertices with larger π k values correspond to better-connected blogs, which are likely to have an influence on a larger number of other blogs. Although the reconstruction performance using a filter based on A norm is better in case 2 than in case 1, the large variability and the poorer performance at large p in case 2 suggest that these filters provide generally poorer models of the signal.

Signal modeling on G 1 with Pα P P

Here we consider the same problem as in the previous section but now compare the performance using reference operators Pα P P. The random variables Y j , j " 1 ¨¨¨, N 1 are distributed as Y j " ε j f 1 0 pv j q where ε j " Berpαπ j q, such that ř j Epε j q " pN 1 .

Numerical simulations

We evaluate the reconstruction performance of f 0 as a function of α in figure 3. We notice that the reconstruction performances using a filter based on Pα , α » 0.3 are the best except for the rates p " t0.01, 0.02u. We notice poorer performance overall when α increases from α " 0.5 to α " 1. This suggests that, for this signal, graph filters based on Pα perform better when the convex combination of P and P ˚involves more the forward random walk, i.e. α P p0, 0.5q, than the backward one, i.e. α P p0.5, 1q.

Signal modeling on G

We now consider the same problem on the whole graph G. The random variables Y j , j " 1 ¨¨¨, N are distributed as Y j " ε j f 0 pv j q, ε j " Berppq.

As some vertices in G have an out-degree equal to zero, we cannot create a transition matrix directly from the adjacency matrix. To overcome this problem, we propose two approaches that make the graph strongly connected and the associated random walk ergodic:

1. Rank-one perturbation: from the original adjacency matrix A, we construct a new adjacency matrix A as follows A " A ` J, where J " 11 J {N is a rank-one matrix and is small. The weak perturbation of the adjacency matrix A by the matrix J ensures that the random walk on G is ergodic with stationary measure π and its associated transition matrix P is well-defined. For our experiments, we choose " 10 ´4. For each proportion of known labels p, the good reconstruction rates are derived by averaging 500 graph signals realizations of Y . We consider the set of reference operators F " tA norm , P , P G , P , PG u.

Construction of the

Graph signal reconstruction G

Numerical simulations

The reconstruction performance is shown in the figure 4. For all p values, the reconstruction performance using filters based on A norm is significantly worse than with all other reference operators. Compared to the other reference operators, A norm is the only one that can be used without modifying the graph to make it strongly connected. Still, its performance is always worse.

Among the other reference operators, we notice a clearly better performance generally when using the reversibilizations P and PG compared to the non-reversible random walks P and P G . This differs from the results on G 1 where both would perform similarly.

Finally, the reconstruction performance does not depend as much on the approach we use to make the graph strongly connected. It seems though that the Google approach slightly outperforms the rank-one approach, both for the non-reversible random walks and their reversibilizations.

CONCLUSION

We studied parametric modeling on directed graphs using graph filters. Our approach based on the random walk operator is suitable on directed as well as undirected graphs. We formulated the problem and derived a closed-form solution. Experiments on a dataset of political blogs showed that the signal modeling based on the random walks operators outperforms the one based on the adjacency matrix. In addition, the parameter α in the convex combination between the random walk operator and its adjoint is seen as a tunable parameter that can improve the modeling. The set P might be an alluring set of reference operators for convolutional neural networks [START_REF] Michael M Bronstein | Geometric deep learning: going beyond euclidean data[END_REF][START_REF] Atwood | Diffusionconvolutional neural networks[END_REF] on directed graphs.

Fig. 1 . 1 0

 11 Fig. 1. (Case 1) Left: Reconstruction of the graph signal f 1 0 on the subgraph G 1 . Right: Reconstruction of the graph signal f 1 0 on the symmetrized version of G 1 .

Fig. 2 . 1 0

 21 Fig. 2. (Case 2) Left: Reconstruction of the graph signal f 1 0 on the subgraph G 1 . Right: Reconstruction of the graph signal f 1 0 on the symmetrized version of G 1 .

Fig. 3 .

 3 Fig. 3. Reconstruction of the graph signal f 1 0 on the subgraph G 1 .

Fig. 4 .

 4 Fig. 4. Reconstruction of the graph signal f 0 on G.

  Google matrix of G[START_REF] Amy | Google's PageRank and beyond: The science of search engine rankings[END_REF]. The construction is in two steps. Firstly, we construct an adjacency matrix à from A by adding one for all dangling nodes, that is nodes with no out-edges. From à we can construct the transition matrix S. Secondly, we define the Google matrix P G as P

		0.95
		0.9
		0.85
	Reconstruction accuracy	0.7 0.75 0.8
		0.65
		0.6
		0	0.02	0.04	0.06	0.08	0.1	0.12	0.14	0.16
					Rate of known labels

G " p1 ´γqS `γJ.

with γ " 0.85 r14s and stationary measure π G .