AUTHOR:

Cédric Demonceaux 1 1 ImViA -VIBOT ERL CNRS 6000, Université Bourgogne Franche-Comté PERCEPTION FOR ROBOTICS : PART II

Some words to introduce the chapter contents:

«What is around me?»knowing how to answer to this question is essential for a robot to navigate safely in its environment. In this part, we will try to find some answers by introducing some tools for helping the robot to perceive the world. Thus, we will present different sensors (lasers, radars, cameras, RGBD sensors) which allow to build a 3D map of the scene where the robot is navigating. Then, we will mainly focus on cameras since these sensors give a rich information about the scene. We will see how we can extract features from the image in order to provide a 3D perception of the world. This chapter presents the main concepts required to start computer vision applied to robotics.

It is not an exhaustive study, thus we can only strongly recommend to read the articles and books cited to deepen the knowledge . , Y m , Z m ) , 3D point in frame m x = (u, v) , pixel E ij , Essential matrix between image i to image j X , 3D point cloud T = (R, t) , Rigid transformation with a rotation R and translation t.

ACTIVE AND PASSIVE SENSORS

An active sensor uses external projecting devices that emit light wavelength, signal or patterns to interact with the scene. The data generated by this external source are gathered by the sensor to deduce information on the environment around the robot. This conversion can be carried out in many ways depending upon the type of sensors. Based on their working principles, there are mainly 3 types of active sensors used in robotics : Lidar, Structured-Light and time-of-flight. On the opposite, passive sensors gather target data through the detection of vibrations, light, radiation, heat or other phenomena occurring in the environment without external devices. Commonly, the passive sensors used in robotics are cameras/image sensors. In the following, let us describe in few lines the different characteristics of these sensors. [START_REF] Harris | A combined corner and edge detector[END_REF] PERCEPTION FOR ROBOTICS : PART II LIDAR The LiDAR instrument emits rapid laser signals which bounce back from the obstacles. The sensor positioned on the instrument measures the amount of time it takes for each pulse to bounce back. Thus, the instrument can calculate the distance between itself and the obstacle with accuracy. It can also detect the exact size of the object. LiDAR is commonly used to make high-resolution maps (Fig. 1).

(a) (b)

Figure 1: LiDAR sensor (Velodyne) and raw data.

RADAR

The RADAR system works in much the same way as the LiDAR, with the only difference being that it uses radio waves instead of laser. In the RADAR instrument, the antenna doubles up as a radar receiver as well as a transmitter. However, radio waves have less absorption compared to the light waves when contacting objects. Thus, they can work over a relatively long distance. The most well-known use of RADAR technology is for military purposes. Airplanes and battleships are often equipped with RADAR to measure altitude and detect other transport devices and objects in the vicinity.

STRUCTURED-LIGHT

Structured-light based sensors project bi-dimensional patterns to estimate the dense depth information of the object surface points. Depending upon the application, the projected patterns can be a single or multiple frames. The main role of the projected patterns is to establish correspondences between the known pattern and camera measurements in a relatively easy manner. Note that the measurements vary according to the 3D model of the object. This variation encodes the scene depth information, which can be recovered using a triangulation tool similar to the one developed in next section for a pair of 2D cameras. Nowadays, these type of sensors are often used in robotics for many applications (localisation, 3D reconstruction, gesture recognition...) because they are light, small, low energy consuming and allow to obtain color and 3D information very quickly at each shot (Fig 2a). Nevertheless, they are really sensitive to the light conditions this is why these sensors are used for indoor application. For outdoor application, we will rather used time-of-light sensors.

TIME-OF-FLIGHT

Time-of-flight cameras consist of emitter and receiver units (Fig 2b). The emitter unit generates a laser pulse that impinges on the targeted object surface. The reflected laser pulse is then detected by the receiver unit along with the roundtrip travel time from transmitter to the receiver. This round-trip travel time provides the 3D position of the object surface point using the speed of light and the ray projection angle. Time-of-flight cameras in principle perform point-to-point reconstruction. These cameras can cover large distances and also provide accurate depth estimation though the coverage is limited by the allowed laser power. Additionally, time-of-flight cameras are rather costly and face scanning difficulties with surfaces exhibiting certain reflective, gloss or color properties. To improve the sensitivity and accuracy, both amplitude and frequency modulated strategies have been adopted for close range distance measurements. Other active sensing technologies include interferometry, laser triangulation, Moiré fringe range contours, etc. A detailed study about existing active as well passive sensors can be found in [START_REF] Sansoni | State-of-the-art and applications of 3d imaging sensors in industry, cultural heritage, medicine, and criminal investigation[END_REF].

IMAGE SENSORS

Image sensors use the ambient light source and convert it into a 2D image. 2D cameras allow capturing high-quality details (due to a combined technological progress in both optics and CCD or CMOS sensors) but require external tools and information to recover the 3D scene. Most common methods, namely stereo vision and monocular or multiple-view structure from motion, recover depth information from two or multiple such projections using the concept of image parallax.

In the case of a stereo camera pair, the image parallax is generated due to their positioning. However, monocular cameras must go under motion to generate the parallax. This approach is referred to as Structure-from-Motion (SfM). In recent days, the SfM-based techniques are very popular because they offer a simple, inexpensive, and accurate solution. Additionally, it allows us to reconstruct large scenes by moving the cameras covering the whole scene or using acquisitions from many cameras [START_REF] Agarwal | Building rome in a day[END_REF]. Nowadays, these cameras are very popular and widespread as they are affordable and reliable. It exists varieties of optics models for 2D cameras, the choice of the optics strongly depend of the application (Fig 3). For example, large field of view (panoramic, fisheye) even spherical field of view can be really useful in robotics, because they allow to have a maximum of information with only one shot.

In the following sections, we will try to answer to these questions: how to extract information in the image? How to modelize the image formation? How to localize 2D cameras in the scene and how to recover the 3D? Finally, we will focus on 3D sensors.

2D CAMERAS : SOME BASIC IMAGE PROCESSING TOOLS FEATURES EXTRACTION

To compare two images, it requires to find corresponding features across them. This problem has been studied since the 80s [START_REF] Hans P Moravec | Obstacle avoidance and navigation in the real world by a seeing robot rover[END_REF]. Most methods are based on two steps : feature detection where we identify the points or areas of interest in the images and feature description which represents the feature as a descriptor. These descriptors correspond to a signature which allow to determine correspondence between the views. A lot of methods have been developed, we will described the main ones below.

HARRIS

The idea behind the Harris method [START_REF] Harris | A combined corner and edge detector[END_REF] is to detect points based on the intensity variation in a local neighborhood: a small region W around the feature should show a large intensity change when compared with windows shifted in any direction. It PERCEPTION FOR ROBOTICS : PART II

E(p) = X (x,y)2W w(x, y)[I(x + u, y + v) I(x, y)] 2 (1)
where w(x, y) is weighted function (simplest case w = 1). For nearly constant patches, this E(p) will be near 0 whereas for very distinctive patches, E will be larger. By a Taylor expansion, E is approximated by :

E(p) ' [u, v]M [u, v] T (2)
where the matrix M corresponds to the image derivatives :

M = X (x,y)2W
w(x, y)

 I 2 x I x I y I x I y I 2 y (3)
This matrix plays an important role to characterize the homogeneity of a patch W around p thanks to the disparity of x and y derivatives. This disparity can be estimated by the eigenvalue 1 and 2 of M . Thus, Harris proposed the corner response measurement which is large for a corner :

R = det(M ) k(traceM ) 2 (4)
where k is an empirically determined constant (2 [0.04, 0.06]). This method is really efficient, invariant to image rotation but not scale invariant. In this way, Lowe [START_REF] David G Lowe | Object recognition from local scale-invariant features[END_REF] has proposed an improvement using a multiresolution scheme.

SIFT

SIFT detector [START_REF] David G Lowe | Object recognition from local scale-invariant features[END_REF] (Scale-Invariant Feature Transform) consists of four major stages: (1) Scale space extreme detection;

(2) keypoint localization; (3) orientation assignment; (4) keypoint descriptor. In the first stage, a multiresoltuion scheme is performed in order to determine potential interest points that are invariant to scale and orientation. These are the local scale-space maxima of the Difference of Gaussian (DoG) which is obtained by subtracting the different Gaussian scales: that extracts blob-like structures at locations where the determinant is maximum. Therefore, the performance of SURF can be attributed to non-maximal-suppression of the determinants M matrices. In description phase, firstly the neighborhood region of each keypoint is divided into a number of 4x4 sub-square regions. Then, it computes the response of a 2D Haar wavelet response each sub-region. Again, this procedure can be computed with aid of the integral image. Each response contributes four values to a descriptor, so each keypoint is described with a 64-dimensional (4x4x4) feature description of all sub-regions. Although the SURF method runs faster than the SIFT, but in some situations like viewpoint and intensity change it does not give good results as SIFT produced.

D(x, y, ) = (G(x, y, k ) G(x, y, )) ⇤ I(x, y) (5
FAST FAST corner detector [29] (Features from Accelerated Segment Test) is a corner detector that uses a circle of 16 pixels to classify whether a pixel p of intensity I p is actually a corner or not. Each pixel in the circle is labeled from integer number 1 to 16 as clockwise (Fig 4). If a set of N contiguous pixels in the circle are all brighter than the I p plus a threshold value t or all darker than the intensity of candidate pixel p minus threshold value t, then p is classified as corner. To make the algorithm fast, first compare the intensity of pixels 1, 5, 9 and 13 of the circle with I p . If at least three of these four pixels satisfies the threshold criterion so that p is chosen as an interest point. On the other hand, if at least three of the four pixel values (I 1 , I 5 , I 9 and I 13 ) are not above or below I P + t, then p is not an interest point (corner). Else if at least three of the pixels are above or below I p + t, then check for all 16 pixels and in this case 12 contiguous pixels should fall in given criterion. Likewise, repeat the procedure for the all others remaining pixels in the image. Because of the some limitations such as for N<12 the algorithm does not work well, the choice of pixels is not optimal and multiple features are detected adjacent to one another, a machine learning approach has been employed to the algorithm to deal with these issues.

BRISK

Although the local features obtained by vector-based descriptors such as SURF, SIFT give successful results in terms of an image representation, using the descriptors of them is not an efficient way. To address this challenge, several binary descriptors computed directly on image patches and BRISK [START_REF] Leutenegger | Brisk: Binary robust invariant scalable keypoints[END_REF] (Binariy Robust Invariant Scalable Keypoints) is one of them. BRISK is based on FAST detector and consists of three parts: a sampling pattern, orientation compensation and sampling pairs. In here, taking a sampling pattern around the keypoint refers to points spread on a set of concentric circles, which are used to determine a point is whether a corner or not in FAST detector. Then these pairs are separated two subsets, short-distance pairs and long-distance pairs. To achieve rotation invariance, the direction of each keypoint is determined by taking the sum of computed local gradient between long-distance pairs and short-distance pairs are 19 PERCEPTION FOR ROBOTICS : PART II rotated based on obtained orientations. Finally for all the pairs, the intensity values of the first and second points in the pair are compared, i.e., if the value of first point is larger than the second then output is 1, else 0. Hence, after going all 512 pairs, leading to a descriptor with 512 bits in length. In matching case, the Hamming distance is used instead of Euclidean distance due to its short execution time.

ORB

ORB detector [START_REF] Rublee | Orb: An efficient alternative to sift or surf[END_REF] (Oriented FAST rotated BRISK) is a combination of FAST and BRIEF. To extract keypoints, it modifies the FAST detector as scale invariant by constructing a scale pyramid of the image. At each scale, keypoints are detected by illustrating the FAST detector. Once the keypoints detected, the Harris corner measure is employed to sort them and only top N points are chosen based on a threshold. To obtain rotation invariant features, first-order moments is used to compute the local orientation through an intensity centroid which refers to the weighted averaging of pixel magnitudes in the local patch. This method is nowadays the most efficient approach and is used in many SLAM approaches as ORB-SLAM [START_REF] Mur | Orb-slam2: An open-source slam system for monocular, stereo, and rgb-d cameras[END_REF]. The table 3 summarizes the properties and performance of these feature detectors. For an exhaustive review, we warmly recommend to read [START_REF] Tuytelaars | Local invariant feature detectors: a survey[END_REF].

OPTICAL FLOW

Instead of finding feature points in the each images, some methods propose to estimate the motion in the video sequence when two consecutive images have been taken in a short time with few modifications. This motion, called optical flow, [START_REF] Fleet | Optical flow estimation[END_REF] is really useful in many application: obstacle avoidance [START_REF] Zingg | Mav navigation through indoor corridors using optical flow[END_REF], action recognition [START_REF] Sun | Optical flow guided feature: a fast and robust motion representation for video action recognition[END_REF], video segmentation [START_REF] Tsai | Video segmentation via object flow[END_REF]... Let us consider an image sequence I((x(t), y(t)), t), the optical flow methods compute the motion between two consecutive frames which have been taken at times t and t + 1 at every pixel position by estimating the apparent motion ! v ((x(t), y(t), t) = ( dx dt (t), dy dt (t)). If we suppose the brightness constancy constraint which means that the luminosity does not change along the time :

I((x(t), y(t)), t) = I((x(t 0 ), y(t 0 )), t 0 ) 8t. (6)
This can be rewritten: dI dt ((x(t), y(t)), t) @I @x dx dt ((x, y), t) + @I @y dy dt ((x, y), t) + @I @t ((x, y), t) = 0

(7)
Thus, ! rI((x, y), t). ! v ((x, y), t) + @I @t ((x, y), t) = 0,

where ! rI = ( @I @x , @I @y ) = (I x , I y ). This linear equation is not sufficient to compute ! v (two unknowns, one equation The fundamental principles of optical flow estimation by variational (dense) methods were proposed by Horn and Schunck in 1981 [START_REF] Berthold | Determining optical flow[END_REF]. The idea is to define a functional composed of two terms. The first term is based on the assumption of brightness constancy constraint and is defined as follows

H 1 ( ! v ) = Z Z ✓ ! rI. ! v + @I @t ◆ 2 dxdy. (9)
The second term, called regularization term, penalizes first-order variations in the vector field ! v

H 2 ( ! v ) = Z Z k ! rvk 2 dxdy. (10)
Thus, Horn and Schunck estimate ! v which minimizes:

E( ! v ) = H 1 ( ! v ) + ↵ 2 H 2 ( ! v ) (11)
where ↵ is a penalization term. The main drawbacks of this method is the introduction of the Tikhonov term (H 2 ) which induces a strong penalization of gradients. This strong penalization leads to excessive smoothing of the optical flow. Therefore, it is not possible to find the spatial discontinuities of the optical flow. Since, different authors have proposed other terms for regularization to preserve discontinuities in the flow by introducing so-called "robust" penalization term (M-estimator).

SPARSE METHOD -LUCAS AND KANADE LIKE

Lucas and Kanade [START_REF] Bruce D Lucas | An iterative image registration technique with an application to stereo vision[END_REF] were the first to propose a sparse method. To do this, they minimize an energy composed only of the brightness constancy constraint. To overcome the aperture problem, they assume the flow ! v constant on a small neighborhood of the point (x, y). This functional is defined as follows:

E( ! v (p, q)) = min ! v X (p,q)2W (p,q) w 2 (p, q)  ! rI(p, q). ! v (p, q) + @I @t (p, q) 2 (12)
where W (p,q) is a neighborhood of (x, y) and w(x, y) a gaussian. The solution is computed by: ! v (p, q) = M 1 " P (p,q)2W (p,q) w(x, y)I x I t P (p,q)2W (p,q) w(x, y)

I x I t # ( 13
)
where M is the same image derivatives matrix defined in (3). This approach is really easy to implement and fast but the optical flow is computed if and only if the neighborhood is well textured (M is well-conditioned) which leads to sparse estimation. Nevertheless, this method continues to be widely used in robotics [START_REF] Baker | Lucas-kanade 20 years on: A unifying framework[END_REF].

At this step, we are able to match points between several images or follow them on a video sequence. The study of the position of these points in 2D images can allow us to deduce the motion of the camera or the 3D structure of the scene. This is the subject of the following section. To express in pixel coordinate, this projection is described with the intrinsic camera matrix K including :f the focal length (distance between I and C, (u 0 , v 0 ) principal point, m x and m y are the scale factors relating pixels to distance, is the skew coefficient between the x and the y) :

K = 2 4 ↵ x u 0 0 ↵ y v 0 0 0 1 3 5 (14)
In order to take into account the displacements of the camera, we choose a static coordinate system called world frame.

Let us pose Y = (X w , Y w , Z w ) the coordinates of the 3D point Q in the world frame. The position of the camera in this world coordinate frame is defined by a 3-space rotation matrix R and a translation vector t and the full camera model is given in homogeneous system as :

2 4 u v 1 3 5 ⇠ KR [I| t] 2 6 6 4 X w Y w Z w 1 3 7 7 5 ⇠ P 2 6 6 4 X w Y w Z w 1 3 7 7 5 (15)
The 3 ⇥ 4 matrix P is called projection matrix and maps 3D points to 2D image points. The terms K and R [I| t] are referred to as, respectively, the intrinsic and the extrinsic parameters of the camera. In robotics, this matrix P is crucial for visual odometry or 3D reconstruction application and requires calibration step to be estimated.

CALIBRATION

Calibrating a camera means computing the P matrix. To achieve this, most methods take several images at different position and orientation of a known planar checkerboard-like pattern (Fig. 6). The intrinsic and extrinsic parameters are then estimated through an over determined system solved a least-square minimization method. Many camera calibration exist, among these, the most popular one is given in [START_REF] Bouguet | Camera calibration toolbox for matlab[END_REF].

EPIPOLAR GEOMETRY

Given point correspondences between at least two 2D cameras and their intrinsic parameters, it is possible to recover both the motion between cameras and the scene structure. This concept is described in Figure 7 between two views. Let x 1 and x 2 be corresponding image feature points given in camera coordinate frames attached to C 1 and C 2 respectively. The points e 1 and e 2 projections of C 2 on I 1 and C 1 on I 2 respectively are called epipoles.

22

PERCEPTION FOR ROBOTICS : PART II The two-view imaging model is based on the fact that, given a point in one image, its corresponding point in another image must lie in a one-dimensional space known as epipolar line. Every epipolar line intersects in the epipole as shown in Figure 7 , where x 2 (the point corresponding to x 1 ) lies on the epipolar line l 2 that also passes through the epipole e 2 . This happens because the camera centers, epipoles, image points, together with the observed 3D point X, lie on the same plane such that back-projected rays from image points intersect in 3-space. Since the line l 2 must contain e 2 and x 2 , l 2 must also lie on the epipolar plane defined by C 1 , C 2 , and X. It is straightforward to express the normal vector of the epipolar plane as [t 21 ] ⇥ R 21 x 1 where the symbol [.] ⇥ denotes a skew-symmetric. Thus, we obtain the so-called epipolar relationship between the corresponding points x 1 and x 2 as follows :

x T 2 [t 21 ] ⇥ R 21 x 1 = x T 2 E 21 x 1 (16)
The matrix E 21 is also known as the Essential matrix. By construction, the Essential matrix is of rank 2. In other words, the essential matrix has five degrees of freedom: three from the rotation matrix and two from the translation vector. Therefore, it can be estimated from at least five point correspondences, as every pair of correspondences provides one equation of the form of ( 16). Then, the rotation and translation can be recovered by direct decomposition of the Essential matrix. The reader may refer [START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF] for more information on its estimation. The entries of E 21 can be estimated only up to an unknown scale factor. This eventually prohibits us from recovering the scale of the translation and the exact scale associated with the translation vector can never be known unless extra information are fed into the problem. In this context, the extra information of scale is always necessary for its unique recovery. Therefore, the translation vector is usually computed with a unit norm hence losing the true scale of the scene.

BUNDLE ADJUSTMENT

The previous technic can easily recovered the rigid transformation between two views and thanks to a triangulation, we can also determine the depth (3D) on every points. When we deal with multiple view images, these 3D points are viewed in different positions. In this case, we use a bundle adjustment where we conjointly refine the 3D coordinates describing the scene geometry and the camera(s) position. Thus, assume that n 3D points X i are seen in m cameras 23 PERCEPTION FOR ROBOTICS : PART II with intrinsic parameters K j and let x ij be the projection of the i th point on image j. Let v ij denote the binary variables that equal 1 if point i is visible in image j and 0 otherwise and assume also that each camera j is parameterized by a rigid transformation T j = (R j , t j ). Bundle adjustment minimizes the total reprojection error with respect to all 3D point and camera parameters, specifically

min (Rj ,tj ) n X i=1 m X j=1 v ij d(K j R j [I| t j ] X i , x ij ) 2 , (17)
where d(x, y) denotes the Euclidean distance between the image points represented by vectors x and y. Thus, Bundle adjustment [START_REF] Triggs | Bundle adjustment?a modern synthesis[END_REF] minimizes the reprojection error between the image locations of observed and predicted image points (Fig 8 ), which is expressed as the sum of squares of a large number of nonlinear, real-valued functions. Thus, the minimization is achieved using nonlinear least-squares algorithms such as Levenberg Marquardt [START_REF] Moré | The levenberg-marquardt algorithm: implementation and theory[END_REF] which has proven to be one of the most successful due to its ease of implementation.

3D SENSORS : 3D -3D

In this part we suppose that we can obtain 3D data directly from the sensor (LiDAR or RGB-D cameras : Structured light, Time-of-light, Stereocamera...). These sensors have emerged as one of the most effective sensors to make robots autonomous because they become less and less expensive (LiDAR) and can give us photometric information RGB-D (color image plus depth) cameras. Thus, we consider two cases depending of the availability of the photometric information. Firstly, we will suppose that the sensor provides only 3D cloud of points at two consecutive times respectively

X = {X 1 , . . . , X m } and Y = {Y 1 , . . . , Y n }.
Here, the goal is to find the rigid transformation R and t which minimizes an error function by registering X and Y. Many methods have been developed to solve this problem and the most popular algorithm is called Iterated Closest point (ICP). In the second case, if the 3D sensor also provides RGB some methods including RGB+depth have been developed by using conjointly 2D image constraint and 3D registration.

ICP

The ICP algorithm was presented in the early 90s for registration of 3D range data to CAD models [START_REF] Paul | Method for registration of 3-d shapes[END_REF]. The key problem can be reduced to find the best transformation that minimizes the distance between two point clouds. In robotics, ICP is really useful because the transformation R and t that minimizes the error between two consecutive 3D acquisition is proportional to the motion of the robot. If the points of X and Y are matched, the problem consists in finding R and t solution of :

n X i=1 kRX i + t Y i k 2 (18)
The solution is computed by the SVD decomposition of the matrix W = UDV T = P n i=1 X 0 i ⇤ Y 0 T i where X 0 = {X 1 X , . . . , X m X } (resp.Y 0 ) are the centered data and we have :

R = UV T (19) t = X R Ȳ (
m i F indClosestP ointInY (RX i + T ) if kRX i + T Y i k 6 d max then ! i 1 else ! i 0 end if end for (R, T ) arg min P n i=1 ! i kRX i + T Y i k 2 end while
It exists many variations of this algorithm depending of outliers rejection, error measurement... a recent review can be read in [START_REF] Pomerleau | A review of point cloud registration algorithms for mobile robotics[END_REF]. Let us note that the ICP algorithm can be used to stitch consecutive 3D point clouds together. Moreover, with RGB information, it is possible to build the 3D scene with color information. In this case, RGB images can be used to match the 3D points by projective data association but also to detect a loop closure in order to reduce the inherent drift errors that we propagate by making consecutive maps created by ICP [START_REF] Izadi | Kinectfusion: real-time 3d reconstruction and interaction using a moving depth camera[END_REF], [START_REF] Han | Enhanced computer vision with microsoft kinect sensor: A review[END_REF].

DENSE RGB-D REGISTRATION

When we deal with RGB-D cameras, we can conjointly take into account 2D color information (RGB) and depth data (D).

Thus, some authors propose to compute the 3D rigid transformation T = (R, t) by minimizing an error that includes photometric : e I (p, X, t) = I(!(p, X , T ), t) I(p, t 1)

where !(p, X , T ) is a warping function which back projects a 3D point X with transformation T on I. and depth errors :

e D (p, X, t) = D(!(p, X , T ), t) D(p, t 1) (22)
where D(p, t) is the depth of pixel p in image at time t. We can note that, ( 21

With ⇢ are robust M-estimators to reduce the effects of self occlusions, moving objects, illumination and interpolations errors in the direct estimation. The value of the parameter can be fixed [START_REF] Kerl | Dense visual slam for rgb-d cameras[END_REF] or can change during the iterative minimization [START_REF] Martins | Adaptive direct rgb-d registration and mapping for large motions[END_REF].

CONCLUSION AND DISCUSSIONS

This chapter has presented the main tools used to localize a robot and reconstruct the scene from a 2D or 3D visual sensor. All approaches are based on the same steps. When only 2D information are provided, it is necessary to detect feature points, to match them, to deduce the camera motion, and to make a bundle adjustment on several acquisitions. On the other hand, if the visual sensor is able to produce 3D data, an ICP can simply be performed. We have studied here the case of a perspective camera model but the epipolar geometry is also valid in the case of a wide-angle image with a single point of view [START_REF] Geyer | A unifying theory for central panoramic systems and practical implications[END_REF] (spherical, catadioptric : parabolic mirror + spelling camera, hyperbolic mirror + perspective camera...) but also fisheye [START_REF] Courbon | A generic fisheye camera model for robotic applications[END_REF] so the approaches discussed can be easily adapted to these cameras. Nevertheless, the features 25 PERCEPTION FOR ROBOTICS : PART II extraction part must be adapted to this type of camera since traditional image processing (filtering, convolution) does not take into account the strong distortions present in these images (Fig 9). Some works dealt with these problems [START_REF] Demonceaux | Central catadioptric image processing with geodesic metric[END_REF], [START_REF] Bogdanova | Scale space analysis and active contours for omnidirectional images[END_REF] but it is still ongoing [START_REF] Aziz | Generic spatial-color metric for scalespace processing of catadioptric images[END_REF]. Concerning visual odometry, many works have been published on this topic and the estimation of the essential matrix is now well controlled. Recently, researchers have focused on reducing the number of characteristic points needed to estimate the camera motion using additional information on scene structure or camera orientation. This makes the estimation more robust to noise in the images and faster [START_REF] Fraundorfer | A minimal case solution to the calibrated relative pose problem for the case of two known orientation angles[END_REF], [START_REF] Saurer | Homography based egomotion estimation with a common direction[END_REF]. In this chapter, we focused exclusively on fixed scenes. Nevertheless, when there are few moving points in the scene, the methods remain valid by integrating a robust approach such as RANSAC or M-estimator. But if the scene has many moving objects, the approaches have to be reviewed. Recently, some works related to motion estimation and 3D reconstruction on strongly dynamic scene have been published [START_REF] Jiang | Static and dynamic objects analysis as a 3d vector field[END_REF], [START_REF] Ioan | Robust dense mapping for large-scale dynamic environments[END_REF], [START_REF] Vo | Spatiotemporal bundle adjustment for dynamic 3d reconstruction[END_REF]. Finally, when the 3D scene is composed of non rigid motion, the problem becomes more challenging and still an open problem even if some works tackle this problem [START_REF] Slavcheva | Sobolevfusion: 3d reconstruction of scenes undergoing free non-rigid motion[END_REF].

  (a) Structured-light sensor: Kinect V (b) Time-of-flight: KinectV2 (c) 3D cloud of point acquired by KinectV1 (d) 3D cloud of point acquired by KinectV2

Figure 2 :

 2 Figure 2: Structured-light and Time-of-flight sensors ([39])

Figure 3 :

 3 Figure 3: Different type of cameras

  )where G(x, y, ) is a Gaussian blur at scale . The points with low contrast are rejected based on the same idea under the Harris method where the M matrix. To obtain descriptors that invariant to rotations, an orientation histogram was formed from the gradient orientations of each local maximum of the DoG function within a region around the keypoint. The final stage of SIFT constructs a descriptor by considering the direction of a keypoint which is gradient strength is maximal. 18 PERCEPTION FOR ROBOTICS : PART II Typically, an adjacent 16x16 region is determined by put the keypoint in the center. After the region is chosen, SIFT divides this region into 4 ⇥ 4 sub-regions with 8 orientation bins in each. Since there are 4 x 4 = 16 histograms each with 8 bins the vector has 128 elements. Thus, the meaningful descriptors are extracted from the image that are compact, highly distinctive and yet robust to change in illumination and camera viewpoint. SURF SIFT are robust but really time consuming. To overcome this problem and inspired by the SIFT descriptor, Bay has proposed the SURF detector [5] (Speeded Up Robust Features). It is able to generate scale and rotation invariant interest points and descriptors. Compared to SIFT, SURF uses 2-D Haar wavelets which are an approximation of DoG but more efficient to compute thanks to integral images. For keypoint detection, it uses the sum of the 2D Haar wavelet response around the point of interest. A 2D Haar wavelet is obtained by an integer approximation to the determinant of M matrix

Figure 4 :

 4 Figure 4: Fast corner detector

  ) and we have to add another constraint. The optical flow methods differ according to this constraint. Two main approaches exit : dense technics which expect smoothness of the flow field and sparse technics which suppose a constant optical flow in the neighborhood. 20 PERCEPTION FOR ROBOTICS : PART II DENSE TECHNICS -HORN-SCHUNCK LIKE

  2D CAMERAS : FROM 2D TO 3D CAMERA MODELINGTo compute 3D structure of a scene using 2D cameras, we need a model that describes how a camera projects the 3D world onto a 2D image. The most used model in computer vision is the pinhole model, which represents a perspective projection from 3D to 2D. This model is a good compromise between simplicity and true image formation of the most cameras used in robotics : perspective cameras, fisheye cameras, some catadioptric cameras, spherical cameras...21 PERCEPTION FOR ROBOTICS : PART II

Figure 5 :

 5 Figure 5: Image modeling

Figure 6 :

 6 Figure 6: Camera Calibration: Image acquisition and results ([8]).

Figure 7 :

 7 Figure 7: Epipolar Geometry

Figure 8 :

 8 Figure 8: Bundle adjustment (Courtesy of http://www.theia-sfm.org/sfm.html)

  ) is a classical optical flow constraint equation (OFCE) term and (22) is equivalent to a flow point-to-plane ICP. The classic dense RGB-D registration consists of using jointly (21) and (22) as b T = arg min T X p ⇢ I (e I (p, X, t)) + ⇢ D (e D (p, X, t))

Figure 9 :

 9 Figure 9: Catadioptric image :d(P 1, P 2) = d(P 3, P 4) when P 1 does not have physically the same influence on P 2 than P 3 on P 4.

Table 2 :

 2 Specific notations used in this chapter

	K , Calibration Matrix P , Projection Matrix C , Camera center
	X = (X m

Table 3 :

 3 Comparison of some feature detectors

		Rotation Invariant	Scale Invariant	Repeatability	Localization accuracy	Robustness Efficiency
	HARRIS	X		+++	+++	++	++
	SIFT	X	X	+++	+++	+++	+
	SURF	X	X	++	++	++	++
	FAST	X		++	++	++	+++
	BRISK	X	X	+++	++	++	+++
	ORB	X	X	+++	++	++	+++

  Compute the rigid transformation R and t between two point clouds X and Y input : two point clouds X and Y, an initialization (R 0 , t 0 ), d max threshold. output : the rigid transformation R and t (R, t) (R 0 , t 0 )

	while not converged do
	for i	1to n do

20) 24 PERCEPTION FOR ROBOTICS : PART II In the general case, when X and Y are not matched, it's not an easy problem and it's solved iteratively by the following algorithm : Algorithm 1

PERCEPTION FOR ROBOTICS : PART II BIBLIOGRAPHY


Agniva Sengupta

Alexandre Krupa

Eric Marchand

RGB-D TRACKING OF COMPLEX SHAPES USING COARSE OBJECT MODELS

Keywords:

This paper presents a framework for accurately tracking objects of complex shapes with joint minimization of geometric and photometric parameters using a coarse 3D object model with the RGB-D cameras. Tracking with coarse 3D model is remarkably useful for industrial applications. A technique is proposed that uses a combination of point-to-plane distance minimization and photometric error minimization to track objects accurately. The concept of 'keyframes' are used in this system of object tracking for minimizing drift. The proposed approach is validated on both simulated and real data. Experimental results show that our approach is more accurate than existing state-of-the-art approaches, especially when dealing with low-textured objects with multiple coplanar faces.

I. INTRODUCTION

The research related to localizing and tracking simple geometric shapes is extensive [START_REF] Lepetit | Monocular model-based 3d tracking of rigid objects: A survey[END_REF] and is being studied since a long time [START_REF] Armstrong | Robust object tracking[END_REF]. Existing approaches for real-time, 6 degrees of freedom (DoF) object tracking can be broadly divided into three categories. The first group consists of algorithms that uses probabilistic models for tracking shapes. For example, [START_REF] Prisacariu | Pwp3d: Real-time segmentation and tracking of 3d objects[END_REF] aims to maximize the discrimination between background and foreground of a scene while simultaneously tracking the 6DoF pose of an object with known 3D model. However, this method used only RGB images as input. [START_REF] Teichman | Learning to segment and track in rgbd[END_REF] extended this method to depth cameras, adding more cues like local image appearance, depth discontinuities, optical flow, and surface normal to inform the segmentation decision in a conditional random field model. Similar approaches have been used to track articulated objects [START_REF] Cifuentes | Probabilistic articulated real-time tracking for robot manipulation[END_REF] with remarkable precision, but the tracking of articulated joints remain beyond the scope of our discussion. Particle filtering based approaches have been parallelized using GPU and implemented towards tracking rigid objects [START_REF] Choi | Rgb-d object tracking: A particle filter approach on gpu[END_REF]. A probabilistic generative model based tracker using 3D signed distance field (SDF) was proposed in [START_REF] Cy Ren | Real-time tracking of single and multiple objects from depth-colour imagery using 3d signed distance functions[END_REF], but it needs accurate object model. The second group of algorithms use learning based techniques to track objects. [START_REF] Hinterstoisser | Model based training, detection and pose estimation of texture-less 3d objects in heavily cluttered scenes[END_REF] proposes a pose estimation technique of complex objects under heavy clutter, but needs color gradient information of the model for training. However, in our approach, we assume that the accurate model of the object, as well as any color/texture based model are not available. [START_REF] Doumanoglou | Recovering 6d object pose and predicting next-best-view in the crowd[END_REF], [START_REF] Michel | Global hypothesis generation for 6d object pose estimation[END_REF] and [START_REF] Yu Xiang | Posecnn: A convolutional neural network for 6d object pose estimation in cluttered scenes[END_REF] propose increasingly accurate techniques for pose estimation, but they cannot be considered real time. [START_REF] Mccormac | Fusion++: Volumetric object-level slam[END_REF] and [START_REF] Runz | Maskfusion: Real-time recognition, tracking and reconstruction of multiple moving objects[END_REF] are both a dynamic SLAM algorithm utilizing Mask R-CNN for segmentation and performs object tracking as a byproduct. The per-object tracking accuracy is never evaluated explicitly. The third group of algorithms use well known minimization techniques to track objects using geometric and photometric constraints. Among these approaches, Iterative Closest Point (ICP) is a popular algorithm [START_REF] Pomerleau | A review of point cloud registration algorithms for mobile robotics[END_REF] that has been used extensively. Many variants of ICP have been proposed for probabilistic [START_REF] Segal | Generalized-icp[END_REF] implementation of point set registration. KinectFusion [START_REF] Izadi | Kinectfusion: real-time 3d reconstruction and interaction using a moving depth camera[END_REF] is a popular research work for tracking and reconstruction of static scene using RGB-D sensor. In this context, SLAM and object tracking have been tackled interchangeably by the same authors [START_REF] Salas-Moreno | Slam++: Simultaneous localisation and mapping at the level of objects[END_REF], while some others have used KinectFusion as a tool for benchmarking their own object tracking algorithm [START_REF] Cy Ren | Real-time tracking of single and multiple objects from depth-colour imagery using 3d signed distance functions[END_REF]. CoFusion [START_REF] Rünz | Co-fusion: Real-time segmentation, tracking and fusion of multiple objects[END_REF] is a dynamic SLAM system that uses a combination of dense ICP and photometric error minimization between the model and the current frame to track objects. The approach we propose, in terms of the framework for object tracking, is somewhat closer to CoFusion [START_REF] Rünz | Co-fusion: Real-time segmentation, tracking and fusion of multiple objects[END_REF]. However, we do not undertake explicit motion segmentation, we are not interested in reconstruction and we use the concept of keyframes. Moreover, the presence of coarse object model makes it a different problem statement altogether.

In this paper we focus on the high-accuracy tracking of rigid, complex shapes with approximately known geometry using depth cameras. We consider the coarse model to be a highly decimated, minimal representation of the object model (instead of a high-polygonal, detailed CAD model), containing very few triangular faces at best. The model does not contain any color or textural information. This is easy to generate and can also be rendered without a depth scanner (e.g: using manual measurements), making it suitable for various industrial applications. Our approach is significantly robust to measurement errors in the coarse model. We are interested in tracking all the 6 degrees of freedom [START_REF] Yilmaz | Object tracking: A survey[END_REF] of the object. The proposed approach is validated both quantitatively and qualitatively in the subsequent sections.

The key contributions of this paper are:

• Combining point-to-plane distance minimization and photometry for tracking of complex objects using coarse model • Using the concept of 'keyframe' in object tracking for increased robustness • Accurate tracking of objects with inaccurate and coarse object models

II. METHOD

The proposed approach to track rigid objects is a combination of point-to-plane distance minimization and photometric error minimization between frames.

II-A. Notation

We work with two types of data: 1) calibrated and registered depth and grayscale images provided by a depth camera, and 2) simulated data containing 3D points along with their corresponding grayscale intensity. Using conventional notations, we denote the depth data as Ω = (P 1 , c 1 ), .....(P N , c N ) , where P i = (X i , Y i , Z i ) and c i is the image intensity value of the point P i , expressed in the camera centered coordinate frame. We define a function π(•) that acts upon any 3D point and projects it to an image plane using the pinhole camera model such that p i = π(P i ). The function c i = I(p i ) provides the image intensity of the point p i . ∇I i,x and ∇I i,y gives the gradient of the image along X and Y axis.

We also consider the model of the object for tracking. We represent it as a surface 3D mesh composed of a set of planes given by M =

{n 1 , d 1 , Q 1 }, {n 2 , d 2 Q 2 }.....{n M , d M , Q M }
where

n j = (n X j , n Y j , n Z j )
is the normal to the j-th plane of the mesh which lies at a perpendicular distance of d j from the origin of the camera-centered coordinate frame. Q j denotes the set of vertices of the bounding triangle for every plane. The n-th frame from the depth sensor (or from a simulated data) is denoted by C n , while certain frames get tagged as keyframes C n ⇒ C K n . O denotes the object centered coordinate frame. These keyframes serve as the reference for photometric tracking for all subsequent frames. We use

the notation A T B = A R B A t B 0 1
to denote the rigid transformation from any arbitrary Cartesian frame A to B, where T ∈ SE [START_REF] Prisacariu | Pwp3d: Real-time segmentation and tracking of 3d objects[END_REF]. In between frames, the motion of the object with respect to its previous pose is denoted by q = ( A t B , θu), where θ and u are the angle and axis of the rotation A R B . The time derivative of q is given as n-1 v n = δq, where v ∈ se(3) is the velocity screw.

II-B. Tracking

For each frame, we minimize two cost functions that depend on a geometric term based on point-to-plane alignment and a photometric term that minimizes the intensity difference between the predicted image (based on an estimate of inter-frame transformation) and the projected image (from the point cloud).

Point-to-plane Distance Minimization: For the geometric term, we minimize the point-to-plane distance between the 3D points in the n-th frame Ω n , with respect to the set of planes registered with the point cloud in the previous frame Ω n-1 . This is given by minimizing the distance error:

e dist i ( n q n-1 ) = n R n-1 P i + n t n-1 • n k -d k (1)
where i denotes a specific point in the pointcloud and k is the index of the plane in the object model, to which it corresponds. We address the topic of this correspondence in the next subsection.

The cost function is optimized using Gauss-Newton optimization and the Jacobian is obtained by partial differentiation of eq. ( 1) with respect to n q n-1 , given by:

J dist i = n k n k × P i (2)
Photometric Minimization: The initial estimate for the transformation between the last keyframe C K p and the current data frame C n used in photometry is given by:

p T n = n T O • p T O -1 -1
where p denotes the frame number for the last keyframe. Starting with this initial estimate of the transformation between the last keyframe and current frame, the image intensity error we seek to minimize for each image point is given as:

e img i p q n = I k π P i -I n π p R n P i + p t n (3)
The Jacobian used for this minimization is:

J img i = ∇I i • A i (4)
where ∇I i = ∇I i,x ∇I i,y and

A i = f • B i , given f = f x 0 0 f y , f
x and f y being the focal lengths and:

B i = -1 Z 0 X Z 2 XY Z 2 -(1 + X 2 Z 2 ) Y Z 0 -1 Z Y Z 2 -(1 + Y 2 Z 2 ) -XY Z 2 -X Z
(5) Optimization: The pose update is given by:

v = -λ WJ + We (6)
where

J = J dist 1 , J dist 2 , • • •, J img 1 , J img 2 , • • • and e = e dist 1 , e dist 2 , • • •, γe img 1 , γe img 2 ,
• • • are the stacked Jacobian matrices and error vectors respectively. v can be interpreted as the velocity screw acting on the camera that transforms it from data frame n-1 to n. The pose update is given as

n-1 T n = n-1
Tn ∆T, where ∆T = exp(v) and n-1 Tn represents the previous estimate of the transformation. Here, γ = e dist e img is computed only once per frame, at the first iteration. γ serves as a scaling factor to ensure that the point-to-plane distance error and the photometric error are at a similar order of magnitude. W is a diagonal matrix of weights obtained from the m-estimator for being robust to outliers. We use Tukey biweight operator as the m-estimator [START_REF] Ruckstuhl | Robust fitting of parametric models based on m-estimation[END_REF]. For any given residual e i , we define the Tukey operator as:

ρ(e i , K) = e 6 i 6 + K 2 e 4 i 2 + K 4 e 2 i 2 if |e i | < K 1 6 K 6 else (7)
where K = 4.7σ and σ = 1.48 × Median(|e i -ẽj |)

II-C. Point Correspondence

As indicated in eq. ( 1), there is a need to associate every 3D point P i with one of the planes of the model, which can be represented by the tuple {n k , d k , Q k }, the k-th plane of M. At every frame, we know the value of Cn-1 T O . We project the 3D points Q k for all visible planes into the image obtained in the current frame. This gives us a set of 2D polygons in the image, each representing one of the visible faces. All the points in the image (x i , y i ) that intersects with a particular plane obtained from π Q k are considered to be associated with this plane.

II-D. Selection of Keyframe

We use keyframes to reduce drift in frame-to-frame photometric tracking. The estimate of the transformation between the last keyframe and the current frame is given by C k T Cn . We decompose this transformation matrix into the translational component (t x , t y , t z ) and the θu rotational component. We define a variable p k , such that:

p k = 1 if ||(t x , t y , t z )|| > 0.05 or θ > 0.15 0 else (8)
Here, the distance threshold is in millimetre while the angular threshold is expressed in radian.

III. RESULTS

For quantitative analysis of the tracker, we generate three short sequences of simulated RGB-D dataset, comprising of three objects: a marmalade container, a coffee machine and a simulated car. A very minimalist model is used to track these objects. We do not require the model to be continuous or topologically closed. We end up with a very rough approximation of the shape of the object, comprising of 24, 48 and 62 faces for the three objects respectively. Initialization of the tracker is done using the ViSP library [START_REF] Marchand | Visp for visual servoing: a generic software platform with a wide class of robot control skills[END_REF], by matching keypoints detected in the very first image with those extracted in the training images using an approach similar to [START_REF] Choi | Real-time 3d modelbased tracking using edge and keypoint features for robotic manipulation[END_REF]. Interested readers may look into more recent techniques, such as [START_REF] Hinterstoisser | Model based training, detection and pose estimation of texture-less 3d objects in heavily cluttered scenes[END_REF], [START_REF] Brachmann | Learning 6d object pose estimation using 3d object coordinates[END_REF] and [START_REF] Tekin | Real-time seamless single shot 6d object pose prediction[END_REF] for handling the initialization problem. Only a few model-free tracking and reconstruction algorithm are publicly available along with their open source code (e.g: [START_REF] Izadi | Kinectfusion: real-time 3d reconstruction and interaction using a moving depth camera[END_REF], [START_REF] Rünz | Co-fusion: Real-time segmentation, tracking and fusion of multiple objects[END_REF]), but none of them are directly applicable to model-based object tracking with RGB-D data. We compare the proposed method with two recent approaches: a) 'edge + keypoint + depth tracker'from [START_REF] Trinh | A modular framework for model-based visual tracking using edge, texture and depth features[END_REF] (denoted in the figures as ViSP), and b) stacked error minimization of point-to-plane distance with photometric error, without using keyframes (denoted as No KF). No KF is close to the tracking module of [START_REF] Rünz | Co-fusion: Real-time segmentation, tracking and fusion of multiple objects[END_REF]. However, we use keyframes instead of coarse-to-fine spatial pyramid. The proposed approach is denoted as PA in the figures.

The comparison of the output of the various tracking methods 1 with the ground-truth is summarized in Table I. The marmalade container sequence (Fig. 1a) shows accurate tracking with all the approaches. The proposed approach manages to outperform the other two methods, although by a small margin. In the coffee machine sequence, the proposed approach outperforms ViSP significantly. As shown in frame 275 of Fig. 1b, ViSP shows a noticeable drift while tracking a set of co-planar faces with not enough image features in it. This is the only instance where the tracking resulted in a visually noticeable drift. No KF alone, does not solve the issue of the drift completely, but the proposed approach eliminates the visible drift and the positional tracking is 83.09% better than that of ViSP. Simulated car is a bit more challenging sequence due to larger inter-frame motion towards the end. No KF shows very low accuracy in this sequence. In the rotation, ViSP outperforms the proposed approach by average of 0.51 • over the entire sequence. This drift is not noticeable visually, and happens because a combination of a large number of robust feature points and edges makes it easier for ViSP to track the overall orientation of the car, while larger inter-frame motion disadvantages the photometric minimization. However, the proposed approach is more accurate than ViSP in terms of translation.

Across the three sequences, it can be concluded that the proposed approach performs better than both No KF and ViSP. For brevity, we show the tracking error plots of only ViSP and the proposed approach in Fig. 2a and Fig. 2b. For the real dataset, all the object models were constructed using manual measurements of the object. The banana model is only a rough approximation of the shape of the real banana. Both the box and the car got accurately tracked (for visual validation, refer to Fig. 3), despite the obvious inaccuracies in the model. The proposed approach was not affected by the moderate occlusion of the objects by the hand. There were some slippage of the model from the actual object while tracking the banana. However, it never completely looses tracking.

We tested our algorithm on an Intel Core i7-6600U CPU with 16 GB RAM. Running on a single core of the system, without SSE optimization and without using any GPU, the basic C++ code written for implementing the proposed approach achieves a runtime of 100 -160 ms per frame, including data capture, tracking and display on a simple GUI. It can be envisaged that with either SSE optimization or with the use of GPU, the overall algorithm can run much faster, if required.

IV. CONCLUSION

We present an algorithm that accurately tracks the pose of a complex object. The tracking is robust to occlusion The RMSE values for translation and rotation for the three synthetic sequences, obtained by comparison with the groundtruth and partial specularity of the scene. We provide validation on both simulated and real data. The proposed approach outperforms one of the best among the open-sourced, modelbased, 6DoF object tracking methods. It also outperforms a partial re-implementation of a state-of-the-art tracking method from recent advances in the field of tracking and reconstruction. The proposed approach is an efficient method to track complex objects that a) does not require detailed object model (reducing the setup time in practical applications), b) tracks objects with better accuracy than comparable stateof-the-art approaches.

Fig. 1 :Fig. 2 :Fig. 3 :

 123 Fig. 1: Comparison of tracking results from 'ViSP Generic Tracker' [25] (ViSP -first row), 'Point-to-plane + Photometry without Keyframes' (No KF -second row) and the 'Proposed Approach' (PA -third row)

Table I :

 I Summary of RMSE values

		Marmalade Container Coffee Machine	Simulated Car
		Translation Rotation Translation Rotation Translation Rotation
	No KF 0.045	0.139	0.284	0.032	0.265	0.072
	ViSP	0.053	0.004	0.118	0.008	0.183	0.027
	PA	0.043	0.003	0.048	0.006	0.179	0.036

All results can be viewed at: vimeo.com/316228510


Léo Besanc
email: leo.besancon@liris.cnrs.fr

Catarina Ferreira
email: catarina.ferreira-da-silva@liris.cnrs.fr

Da Silva

Parisa Ghodous
email: parisa.ghodous@liris.cnrs.fr

Towards Blockchain Interoperability: Improving Video Games Data Exchange

case, control is determined by a consensus mechanism, which determines which blocks are considered valid for the network. In this paper, we mainly focus on decentralized blockchain applications (DBA).

II. RELATED WORK

A. Interoperability between blockchains

Since the creation of Bitcoin, various new BC designs have tried to improve the technology. For example, EOS [START_REF] Grigg | EOS -An Introduction[END_REF] uses Delegated Proof of Stake (DPoS) as a method for achieving consensus, which compromises decentralization in order to increase throughput. There is no unified standard between all BC designs, and this leads to the need for research regarding interoperability between BC [START_REF] Buterin | Chain Interoperability[END_REF]- [START_REF] Hardjono | Towards a Design Philosophy for Interoperable Blockchain Systems[END_REF]. Particularly, [START_REF] Jin | Towards a Novel Architecture for Enabling Interoperability amongst Multiple Blockchains[END_REF] proposes a layered architecture to improve communication between BC.

B. Interoperability in a particular field

Some research works also try to solve interoperability issues within a particular field. This is the case of [START_REF] Gordon | Blockchain Technology for Healthcare: Facilitating the Transition to Patient-Driven Interoperability[END_REF], which analyzes how to leverage BC technology to improve data sharing between patients and healthcare institutions. Standardization efforts have come from the IEEE Blockchain Initiative [START_REF]Standards -IEEE Blockchain Initiative[END_REF] and the IEEE Standards Association [START_REF]IEEE-SA -The IEEE Standards Association -Home[END_REF]. For example, a framework focused on the Internet of Things is proposed in [START_REF]Standard for the Framework of Blockchain Use in Internet of Things (IoT)[END_REF]. Concurrently, the Enterprise Ethereum Alliance (EEA) [START_REF]Enterprise Ethereum Alliance -Home[END_REF] designs specifications for BC clients, built for the Ethereum ecosystem, that could have enterprise usage. Unfortunately these proposals cannot be easily extended to other applications and applied to other BC. For example, the EEA aims to reach enterprises, so they don't take into account decentralization in their specifications [START_REF]Enterprise Ethereum Client Specification V2[END_REF]. The architecture proposed by IBM [START_REF]Blockchain reference architecture -IBM Cloud Garage Method[END_REF] has similar limitations: even though they include a public network for customers, the BC is managed by an administrator and its consensus is achieved by trusted participants.

Similarly, in the video game industry, Hoard [START_REF]Hoard -Facilitating True Ownership of Virtual Gaming Assets on the Ethereum Blockchain. Buy, Sell and Rent Downloadable Content on a Marketplace[END_REF] aims to better integrate BC in game engines for developers, as well as to abstract complexities of the BC for players. However they do not propose a generic framework for DBA. Approaching Abstract-Current solutions for designing and building decentralized blockchain applications lack interoperability. Consequently, blockchains and existing technologies do not integrate well in a unified framework. This integration is necessary to work around some of the blockchains constraints, such as scalability of transactions and ergonomics. Indeed, blockchains are not suitable for huge data storage, but there are distributed data storage solutions that can be used in a decentralized blockchain application. Regarding ergonomics, the use of blockchain technology should be in the background and transparent for users that may not know how to set up and secure a blockchain-based application.

We propose an architecture aiming to easily link existing decentralized technologies and blockchains. We then discuss the impact of this architecture for the video game industry. As a result, we propose an original data representation of blockchain gaming assets in order to improve data exchanges in this industry.

Index Terms-Blockchain, interoperability, standards, video games

I. INTRODUCTION

Blockchain (BC) is an innovative technology, which can have a high impact in numerous industries, such as healthcare [START_REF] Azaria | Medrec: Using blockchain for medical data access and permission management[END_REF], supply-chain [START_REF] Abeyratne | Blockchain ready manufacturing supply chain using distributed ledger[END_REF], finance [START_REF] Guo | Blockchain application and outlook in the banking industry[END_REF] and video games [START_REF] Xaya | The ultimate blockchain gaming platform[END_REF]. BC are append-only ledgers shared across a network of clients. Zheng et al. show in [START_REF] Zheng | Blockchain challenges and opportunities: a survey[END_REF] some of the promises of this technology: decentralization, anonymity, persistency of information and auditability. However, they also highlight some of its current challenges: each node needs to keep the history of all the transactions made in the network, so the storage space keeps increasing, and the number of transactions that can be processed by the network is quite limited, around 7 transactions per second for Bitcoin. Deshpande et al. [START_REF] Deshpande | Distributed Ledger Technologies/Blockchain: Challenges, opportunities and the prospects for standards[END_REF] also show the importance of resolving interoperability issues and developing standards in the BC field. This interoperability need can be found at multiple levels: a) between different BC, b) between different projects running on the same BC, and c) between BC and other technologies used to create decentralized applications.

BC are usually distributed, meaning the record of all transactions is replicated across multiple physical nodes. They can also be decentralized, meaning they are not controlled by a single entity (e.g. a government or company). In this the problem from a semantic perspective, like [START_REF] Grishchenko | A Semantic Framework for the Security Analysis of Ethereum Smart Contracts[END_REF] did for smart contract security, could improve interoperability.

C. Standardization of a particular blockchain

Protocols and commonly used interfaces in the BC space have mostly been standardized with a bottom-up approach. This is achieved mainly through Bitcoin Improvement Proposals (BIPs) and Ethereum Improvement Proposals (EIPs), as well as Ethereum Request for Comments (ERCs). The latter has seen several proposed standards for asset management, each built on the ERC-20 token standard [START_REF] Vogelsteller | ERC-20 Token Standard[END_REF].

In the video game industry, for non-fungible tokens, the most used token is ERC-721 [START_REF] Entriken | ERC-721 Non-Fungible Token Standard[END_REF] (e.g. collectible virtual objects such as CryptoKitties [START_REF] Cryptokitties | CryptoKitties -Collect and breed digital cats![END_REF]). More recently, the ERC-1155 [START_REF] Radomski | Multi Token Standard[END_REF] proposes a unified interface able to manage both fungible and non-fungible assets.

Currently, these standards only cover the BC side of an asset, by specifying smart contract interfaces tools need to support in order to manage the assets. However, this approach is limited as it doesn't take into account the ecosystem as a whole. For example, collectible assets such as CryptoKitties are represented by images. These images are centralized and controlled by the servers of the project's company. This design choice could be challenged if any decentralized image storage standard was associated with the ERC-721 standard.

Indeed, most decentralized applications cannot use only BC technology, as it currently has several limitations. For example, the cost of permanently storing large amounts of data (e.g. images) on the Ethereum BC is prohibitive [START_REF] Palau | Storing on Ethereum. Analyzing the costs[END_REF]. As a result, developers need to use BC only for the core processing of the application. Non-crucial processing, storage and other ancillary tasks have to be managed by other tools, such as distributed file storage solutions. Interoperability between a BC and these tools is a challenge, and it should be better taken into consideration when building standards.

D. Decentralized application example

The project Decentraland [START_REF] Ordano | Decentraland, A blockchain-based virtual world[END_REF] uses a novel approach in order to create a virtual universe where users can purchase virtual land. Users can add 3D models, videos or sounds to their land, and script their content to interact with other users. Concretely, it is possible to design games that will run inside this virtual world. However, with the current specifications, developers need to design their games around the project's ecosystem. For example, the game's logic can only be programed using the project's language. Having a more generic design could help bring support for existing game engines more easily, and attract more content creators on the platform.

To summarize, to the best of our knowledge, no welldefined and complete architecture specifications for generic DBA have been proposed yet. As a result, integrating BC into video games is difficult to do with current technology and development tools. The National Institute of Standards and Technology confirms [START_REF] Regenscheid | Blockchain and Distributed Ledger Technologies: Opportunities, Challenges and Future Work[END_REF] that the current and future work regarding BC standardization concerns BC interoperability among others. This is why our work focuses on the proposition of a generic design for DBA that could be applied in most potential application of BC technology. We propose a design pattern to help developers better integrate BC into their applications.

III. PROPOSED ARCHITECTURE

The goal of the layered architecture shown in Fig. 1 is to provide the building blocks to support a DBA. It also avoids using a BC for non-suitable tasks. For sake of genericity, it is analogous to the OSI model, and each layer needs to communicate with its neighbors.

As seen previously in [START_REF] Palau | Storing on Ethereum. Analyzing the costs[END_REF], BC technology isn't suitable for huge data storage. Fortunately, other decentralized tools can be used in addition to a BC to implement a complete application [START_REF] Kryukov | Decentralized Data Storages: Technologies of Construction[END_REF]. For example, static storage can be distributed on InterPlanetary File System [START_REF] Benet | IPFS -Content Addressed, Versioned, P2P File System[END_REF] (IPFS) for free, as any node can choose the content they host. However, in practice, if a company does not want to lose the files needed for a product, they can host a node which acts as a gateway if no one else is incentivized to host the files. Other projects try instead to give economic incentive to store data. For example, FileCoin [START_REF]Filecoin: A Decentralized Storage Network[END_REF] is a BC layer built on top of IPFS, and Swarm [START_REF] Trón | Swap, swear and swindle: incentive system for swarm[END_REF] is an Ethereum Foundation project, aiming at bringing decentralized storage in the Ethereum ecosystem. One of the main challenges faced by the file storage layer is to correctly estimate the needs of an application, in terms of data availability, decentralization and data loss prevention.

For dynamic content and queries, we cannot directly use the decentralized storage tools mentioned above, as they only support static files. But several projects (OrbitDB [START_REF]OrbitDB: A peer-to-peer database for the decentralized web[END_REF], a layer on top of IPFS, and Gun [START_REF] Nadal | amark/gun: A realtime, decentralized, offline-first, graph database engine[END_REF]) make use of conflict-free replicated data types. These databases use data types which are suitable for a distributed environment, as it is always possible to resolve incoherence between peers, even when they go offline regularly. The Brewer's theorem states that a distributed database can have at most two of the following properties: consistency, availability and partition tolerance. Using this theorem, an application-specific choice has to be made in this layer in order to have the suitable trade-off for the considered use case.

The processing layer aims to validate data integrity and to manage crucial game mechanics (ensuring financial integrity, preventing cheating, etc.). This is done by any BC which supports smart contracts, e.g. Ethereum [START_REF] Buterin | A next-generation smart contract and decentralized application platform[END_REF], EOS [START_REF] Grigg | EOS -An Introduction[END_REF], Hyperledger Fabric [START_REF] Androulaki | Hyperledger fabric: a distributed operating system for permissioned blockchains[END_REF]. The choice of the specific BC used in this layer has to be made by the developers depending on the use case. Indeed, it is sometimes preferable to prioritize throughput over decentralization or security. In these cases, it makes sense to use EOS or Hyperledger instead of Ethereum to process the application's smart contracts.

However the BC chosen in the processing layer may not have the exact properties needed. Platforms and second layer solutions can help to improve the interoperability between projects, as they can abstract the processing layer so that the application layer can interact with any of the possible BC. This abstraction is useful because it allows developers of projects built between different BC to use similar terminology, designs and mechanisms. Second layer solutions can also improve the scalability of the BC. Developers of DBA currently have two means to scale up the number of transactions. Both aim to avoid sending transaction on the public BC. There are sidechains [START_REF] Back | Enabling Blockchain Innovations with Pegged Sidechains[END_REF] and state channels, popularized by the work made on the Lightning Network [START_REF] Poon | The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments[END_REF]. If a decentralized multiplayer game must have low-latency, the developers can implement a token ring network structure through state channels for player communications, instead of having all players transact on the BC.

The application layer is related to the interface the user connects to in order to use the application. It needs to interact with the BC but also to abstract complicated concepts regarding cryptography for the user. Indeed, developers cannot expect the users to know how the BC works and the consequences regarding security of their funds. This is why the ease of use and ergonomics of the technology is crucial. For example, gamifying wallet creation is an interesting way to make sure the user has stored securely the seed words for his wallet.

To enable communication between peers and these layers, a decentralized application should use peer-to-peer networking tools. Peer discovery may be difficult to achieve without a server, but it is possible to use Distributed Hash Tables (DHTs) as Guidi et al. did in [START_REF] Guidi | Managing social contents in Decentralized Online Social Networks: A survey[END_REF].

Finally, we see that each layer of this architecture has its own challenges, both from research and engineering perspectives. Design and interface specifications would greatly help resolve these challenges.

IV. APPLICATION TO THE VIDEO GAME INDUSTRY

In the video game industry, BC can be used to improve trust between players and developers, as well as to reduce friction in the game implementation. For example:

• The founder of Ethereum, Vitalik Buterin realized the importance of decentralization when Blizzard unilaterally updated the rules regarding one of his World of Warcraft assets [START_REF] Buterin | Vitalik Buterin on about[END_REF]. The player felt cheated by the developers because he understood he didn't truly own his assets. • If players can interact with peer-to-peer technologies, game developers don't have to pay for expensive servers as all the processing can be done by the players' machines. • BC are especially suitable for ownership management.

Games like Lunar Mines [START_REF]Lunar Mines -Own your space[END_REF] take advantage of BC by letting players easily craft and trade items with other players. This type of game mechanics could be done in a non-BC game, but developers would need to recreate the asset ownership database and trading features the BC provides, so it would be harder to implement. The main drawbacks of games using BC technology compared to centralized games are the technological complexity of BC systems and the lack of control over certain aspects. For example, unwanted or illegal content could be harder to censor.

The video game industry entails various additional constraints. For example, most video games need real-time data exchange between multiple players. Moreover, graphical assets generally need a lot of storage space and bandwidth. In order to apply the proposed architecture to this industry, we show in Fig. 2 a possible life cycle of a BC game asset. Once it is created, we need to store it in the suitable format and storage solution. In order to validate the properties of the asset with the BC, hashes and the main properties should be stored in a smart contract that manages the asset. Depending on the application, the validation step can also aim to ensure the data inside the asset can be used by the application, and does not contain unwanted or illegal content. This step can be achieved by a centralized entity that stakes its reputation on the asset validity, by a community vote or by any other consensus method. Finally, whenever a player wants to use the asset (because they or another player own it in-game), the application layer should check its properties.

To correctly represent a video game asset on the BC, we've seen that ERC token standards currently do not interface well with the other layers. For example, only the ERC-721 interface allows for a reference to metadata, and it only consists of one URI that could potentially become obsolete. The approach described in [START_REF] Ordano | Decentraland, A blockchain-based virtual world[END_REF] has a similar issue. The representation of a video game asset needs to be generic and be quickly implemented with existing technologies.

We define two types of parameters: asset handling prop- erties, and asset specific properties. The first type describes required properties to identify the asset: for example its name, its hash, or its validation status. The second type contains anything else. In order to be able to represent generic assets, we focused on an archiving format similar to Java archives JAR. The content of this representation is described in Fig. 3. Most of the elements mentioned are self-explanatory. However, the following list adds precision to some of them:

• Hash (multihash [START_REF]Self describing hashes -for future proofing[END_REF] format) -can be used to quickly reference the asset. For example, if the hash is stored in a smart contract, one can retrieve the asset from the hash and then recompute it to ensure data integrity. The multihash format is self-describing, and we can implement it with any hashing function. This means that if an existing hashing function becomes obsolete because of hash collisions, we can change it with back-compatibility. However, hash collisions are less critical in our use case as we do not transfer value between users, • Properties -related to the asset (e.g. its in-game effects),

• Smart contract's Application Binary Interface (ABI)describes the prototypes of the functions of the contract, • Smart contract's and creator's address reference (string)a reference to the smart contract's address with a naming system such as the Ethereum Naming System (ENS), • Child assets hashes -can be used for crafting different assets into one. With this asset specification, game developers and BC engineers can use and agree on the same data representation. Also, it will be easier to develop tools to quickly import the assets and interact with the BC from game engines (Unity or Unreal Engine). To assess the feasibility of our proposal, we want to release a follow up research showing a prototype of a fully decentralized game implementing the architecture we propose and our proposed data representation for data transfers between players. This interoperability between game engines and the BC also allows for new game mechanisms, as shown in the next section.

V. USER GENERATED CONTENT User Generated Content (UGC) gives players the opportunity to create assets and share them with anyone in the community. Our asset data representation and architecture can help game creators and users by providing a unified distributed game design framework, which supports interoperability. Indeed, anyone can create an asset following our representation. Then, the asset is verified on the BC by a smart contract and referenced by its hash, which ensures data integrity. We can ensure the asset follows community rules by Proof of Authority, as it is easy to implement, but it compromises decentralization. A more decentralized approach could use a community vote. In this case, to avoid Sybil attacks, only players above a certain level in-game (or having played a certain time) could vote. Another possibility is to automatically filter unwanted content using machine learning in a decentralized cloud computing framework (using, for example, the products proposed by iExec [START_REF] Fedak | iExec: Blockchain-Based Decentralized Cloud Computing[END_REF] or Golem [START_REF] Golem | The Golem Project[END_REF]), but this approach brings a different set of constraints than reaching consensus within the community. For example, an artificial intelligence needs data for its training, and errors need to be handled. An advantage of using BC for UGC is that content creators can receive royalties automatically for the usage of their assets. An example of a business model would be to reserve part of the game's revenue for community content creators, based on how much content they provided and how much it is used by the community. This incentivizes content creation and involvement of players in the game.

VI. CONCLUSIONS AND PROSPECTS

Better interoperability between BC and existing technologies is needed. This interoperability can be obtained by formalizing specifications for intercommunication between layers of the architecture of DBA. In this work, we presented an architecture applied to the video game industry. We saw that existing BC data representations could not easily be used throughout the whole architecture. That is why we described a new data representation for BC assets, that contain all the necessary information to be used in a BC environment. They also take into account the scalability issues of the BC, by allowing easier data sharing of BC assets. The next steps will be to generalize what we learned from the application of our proposal to the video game industry and refine our proposed design by considering applications in other industries, e.g. the Internet of Things, banking or supply chain. For example, we can use BC assets to create diploma certifications. Assets would contain the diploma and hashes would be referenced on the BC. The advantage of BC technology here would be to timestamp the certification, and allow for revocation.

The validation of our framework will be achieved by developing a proof-of-concept of a decentralized and real-time BC game using our architecture and asset data representation. Besides the decentralization, auditability and security benefits of BC, this allows for the game's community to be more involved in the governance and content creation of the game.

Fig. 1 .

 1 Fig. 1. Decentralized blockchain application architecture

ACKNOWLEDGMENT

The PhD work of Léo Besanc ¸on is supported by B2Expand, 69100 Villeurbanne, France. We thank Éric Burgel, chairman of B2Expand, for his help and advice.