Stefan Kinauer
email: stefan.kinauer@centralesupelec.fr

Maxim Berman
email: maxim.berman@centralesupelec.fr

Iasonas Kokkinos
email: iasonas.kokkinos@centralesupelec.fr

Monocular Surface Reconstruction using 3D Deformable Part Models

 on the PASCAL 3D+ dataset.

Both authors contributed equally.

Introduction

The advent of deep learning has led to dramatic progress in object detection [START_REF] Girshick | Deformable part models are convolutional neural networks[END_REF][START_REF] He | Deep residual learning for image recognition[END_REF] and also in tasks that can lead to 3D object perception, such as viewpoint estimation [START_REF] Tulsiani | Viewpoints and keypoints[END_REF]. Even though Convolutional Networks seem to be the method of choice for such problems, they may not be yet appropriate for structured prediction tasks that are 'beyond detection' and involve multiple, real-valued and interrelated variables that need to be estimated with high precision. The scarcity of data for many of these tasks, as well as the rich structure inherent in the problems advocate a more explicit, modelling-based method.

Our work addresses in particular the problem of estimating the three-dimensional shape of an object from a single RGB image. Apart from the inherent interest of the problem, this can lead to applications in graphics (rendering, augmented reality), robotics (grasping, navigation) and object detection (dataset augmentation, 3D-based classification). This severely ill-posed problem requires Fig. 1. Our approach models a three-dimensional object in terms of a graphical model, where the nodes correspond to 3D part positions and the edges encode geometric constraints between part positions. Given an input image and a viewpoint estimate the cost function of our energy model dictates the optimal placement of the parts in three dimensional space, obtaining a reconstruction of the object's surface from a monocular image.

somehow introducing knowledge about the 3D geometry of an object through a model-based approach.

A model-based approach to solving such a problem typically involves (a) using multiple images during training to construct a three-dimensional surface model, and (b) interpreting a single image at test time by adapting the model to it. It is clear that restricting the surface reconstruction task to a specific category simplifies the generic surface reconstruction problem [START_REF] Horn | Shape from Shading[END_REF][START_REF] Barron | Shape, illumination, and reflectance from shading[END_REF][START_REF] Kulkarni | Picture: A probabilistic programming language for scene perception[END_REF], since we now have a more specific, model-based prior knowledge about the anticipated solution. The main question is which model is best suited for this task.

Our approach builds on the recent advances of [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] where it was shown that accurate surface reconstructions can be obtained from RGB images for a wide variety of categories in the PASCAL VOC dataset. We use the same procedure for recovering the 3D geometry of categories from 2D datasets, but change entirely their modelling approach, which leads to different learning and optimization tasks. The work of [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] was using iterative optimization algorithms that can get stuck at local minima, while the cost function driving the optimization was hand-crafted, making it hard to profit from rich features or large datasets. We propose instead an approach that comes with guarantees of obtaining a globally optimal solution, and develop an associated Structured SVM training algorithm that can optimally design the cost function for the task at hand.

For this, we introduce a graphical model inspired from the Deformable Part Model paradigm [START_REF] Fischler | The Representation and Matching of Pictorial Structures[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], treating part positions as nodes of a graph and incorporating geometrical constraints within graph cliques. In particular, we lift Deformable Part Models [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] to 3D, allowing the object parts to live in a 3D pose space, reflecting the 'real-world' part coordinates. We represent prior information about the 3D shape of an object category in terms of viewpoint-conditioned pairwise terms among parts, and use rich CNN features to construct unary terms that dictate the part placement in the image. In order to make this three-dimensional model practically exploitable we develop customized optimization and learning techniques.

Regarding optimization, our method is guaranteed to deliver the optimal solution when using a loop-free graph, like a star or a tree. Even though inference would in principle be possible using generic efficient message-passing algorithms, such as Generalized Distance Transforms [START_REF] Felzenszwalb | Distance transforms of sampled functions[END_REF], the 3D nature of our task makes such techniques memory-and time-inefficient: the complexity scales linearly in the depth resolution, so one would need to trade off accuracy for speed. Instead, in Sec. 4 we extend Dual-Tree Branch-and-Bound [START_REF] Kokkinos | Rapid deformable object detection using dual-tree branch-and-bound[END_REF] to 3D, keeping the memory complexity constant and the computational complexity logarithmic in the depth resolution -this allows us to use a fine-grained depth resolution with negligible computational overhead.

Regarding learning, we use discriminative training which allows us to design the cost function so as to place the model predictions as close as possible to the ground-truth surface. In particular we use Structured SVM training with a loss function that penalizes the deviation between the estimated 3D position of the parts and the ground-truth position of the associated object landmarks. We jointly learn how to score the CNN features that are used for the construction of our unary terms and the displacement features that are used for our pairwise terms, while it would be also possible to backpropagate on the CNN that delivers the CNN features.

We demonstrate the merit of our contributions through systematic comparisons on the PASCAL 3D+ dataset, obtaining better results than the current state-of-the-art method of [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] on most categories.

Related Work

There are several problems pertaining to our task, including (i) the acquisition of 3D geometry from RGB images, (ii) the modelling of 3D deformations, and (iii) the interpretation of a test image in terms of a learned 3D deformation model. We start by presenting the techniques underlying the current state-of-the-art method of [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] and then turn to techniques that are closer to our own work.

Regarding (i), several techniques have recently tackled the problem of establishing 3D geometric models from RGB images [START_REF] Cashman | What shape are dolphins? building 3d morphable models from 2d images[END_REF][START_REF] Kanazawa | WarpNet: Weakly Supervised Matching for Single-View Reconstruction[END_REF][START_REF] Kemelmacher-Shlizerman | Internet based morphable model[END_REF], while a closely related task aims at establishing non-rigid correspondences across unstructured sets of images [START_REF] Carreira | Virtual view networks for object reconstruction[END_REF][START_REF] Zhou | Flowweb: Joint image set alignment by weaving consistent, pixel-wise correspondences[END_REF]. We follow the work of [START_REF] Vicente | Reconstructing PASCAL VOC[END_REF][START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] where a minimal annotation, in terms of a few landmarks per object instance, is combined with non-rigid structure from motion algorithms to lift the PASCAL dataset to 3D and estimate surface models for 10 categories.

Turning to (ii), the modeling of shape variability, the deformable model paradigm used in [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] relies on a linear, low-dimensional subspace to parameterize the possible surface variation that a category can have with respect to the mean, nominal surface. A particular shape instance can thus be expressed in terms of a low-dimensional coefficient vector.

Turning to (iii), adapting a deformable shape model to a novel image, the authors of [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] estimate the coefficients of the surface model so that the projection of the estimated 3D surface on the 2D camera plane is aligned with the object silhouette, while some designated mesh points project close to two-dimensional landmark positions; segmentation and landmarks are provided either by humans or by external modules [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF]. While exploiting several acceleration techniques that are particular to the cost function being used, the optimization time is in the order of seconds and the gradient descent procedure used by the authors is prone to getting stuck in local minima.

Turning to works that rely on DPMs, as we do, several works have recently aimed at coupling DPMs with three-dimensional modelling, e.g. [START_REF] Lim | Fpm: Fine pose parts-based model with 3d cad models[END_REF][START_REF] Pepik | Multi-view and 3d deformable part models[END_REF][START_REF] Yoruk | Efficient object localization and pose estimation with 3d wireframe models[END_REF][START_REF] Zhu | Single image pop-up from discriminatively learned parts[END_REF][START_REF] Zia | Are cars just 3d boxes? jointly estimating the 3d shape of multiple objects[END_REF]. However, none of the existing works treats the 3D positions of the parts as variables that are being optimized over. We note that in our case we have M = 100 landmarks in 3D while in most of these works the three-dimensional variable being optimized corresponds to the relative angle of the camera to the object [START_REF] Lim | Fpm: Fine pose parts-based model with 3d cad models[END_REF][START_REF] Pepik | Multi-view and 3d deformable part models[END_REF][START_REF] Yoruk | Efficient object localization and pose estimation with 3d wireframe models[END_REF][START_REF] Zhu | Single image pop-up from discriminatively learned parts[END_REF][START_REF] Zia | Are cars just 3d boxes? jointly estimating the 3d shape of multiple objects[END_REF][START_REF] Hejrati | Analysis by synthesis: 3d object recognition by object reconstruction[END_REF] and potentially also the visibility of points [START_REF] Zhu | Single image pop-up from discriminatively learned parts[END_REF][START_REF] Yoruk | Efficient object localization and pose estimation with 3d wireframe models[END_REF]. Several works go beyond this and search also over CAD models, typically represented as exemplars, e.g. [START_REF] Lim | Fpm: Fine pose parts-based model with 3d cad models[END_REF], while certain other works, e.g. [START_REF] Pepik | Multi-view and 3d deformable part models[END_REF][START_REF] Zhu | Single image pop-up from discriminatively learned parts[END_REF], also search over part positions in 2D.

In our case we actually consider that the viewpoint is provided by an external module or by ground-truth annotations. Our modelling part is fairly similar to that of [START_REF] Pepik | Multi-view and 3d deformable part models[END_REF], but the major difference lies in the solution space: to the best of our knowledge we are the first work that achieves efficient and guaranteed optimal placement of object parts in 3D. Our focus is on the solution of the combinatorial optimization problem obtained by trying to jointly position all 3D parts of an object in a mutually consistent configuration. For this we have built on fast techniques for inference with 2D DPMs, [START_REF] Kokkinos | Rapid deformable object detection using dual-tree branch-and-bound[END_REF][START_REF] Boussaid | Fast and exact: Admm-based discriminative shape segmentation with loopy part models[END_REF], and adapted them to operate in 3D.

3D Deformable Part Models for Category Surface Estimation

Given an image I and a viewpoint v, our task is to estimate the 3D coordinates of P mesh nodes X = {x 1 , . . . , x P }, where every node is a 3D position vector x i = (h i , v i , d i ). We will be denoting vectors with boldface letters and will alternate between the vector notation x and the horizontal/vertical/depth notation (h, v, d) based on convenience. For this we use Deformable Part Models [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] (DPMs) which provide a rigorous, energy-based approach to modelling and detecting deformable object categories. As we describe below, DPMs can also be adapted to our problem. We break the problem into three steps; firstly in Sec. 3.1 we determine the 3D model, defining the graph nodes and relationships between them. Secondly, in Sec. 3.2 we determine how the surface would look like when projected in 2D. Finally, in Sec. 3.3 we describe how to use the image so as to indicate which of the possible 3D surfaces projects in a way that matches with the image observations.

Model graph construction

We start by describing how we obtain the nodes of the DPM graph, which requires having access to 3D geometry related to an object category. As in [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF], we rely on the work of [START_REF] Vicente | Reconstructing PASCAL VOC[END_REF] to recover 3D geometry from a 2D dataset, such as the PASCAL VOC dataset; given a set of images of an object category and K category-specific keypoint annotations, Non-Rigid Structure-from-Motion (NRSfM) [START_REF] Bregler | Recovering non-rigid 3d shape from image streams[END_REF] delivers a joint estimation of (1) the 3D position of the K category-specific keypoints (including occluded keypoints) and (2) a camera viewpoint estimate for each training instance. Given the viewpoint estimates, a class-specific triangulated 3D mesh is obtained from ground-truth segmentation masks by constructing a visual hull from the training instance.

This 3D mesh and the K 3D-lifted keypoints are associated by projecting every keypoint to the 3D mesh point that is closest to it on average over the training set. This provides us with the first K nodes of our model. A denser sampling of the mesh allows our model to more thoroughly capture the object's shape; we obtain P = 100 nodes using Geodesic Surface Remeshing [START_REF] Peyré | Geodesic remeshing using front propagation[END_REF], which ensures that the K keypoints are selected, while the remaining points are roughly equidistant. In Fig. 1(a) we illustrate an example of the input and the downsampled mesh for the car category.

We obtain a Deformable Part Model by treating each of those mesh points as a graph node. Edges between nodes capture geometric constraints; each edge e i,j is associated with a 3D nominal displacement vector µ i,j equalling the average displacement between nodes i and j, and a spherical precision matrix C i,j indicating the typical inverse variance around that displacement. We note that the edges do not coincide with the ones in the mesh triangulation described above. In particular, we use edges that connect potentially opposite surface points, as these may better capture volume constraints.

Viewpoint-adapted 3D DPMs

Having defined the model's 3D geometry, we now turn to accounting for the effects of camera pose, so as to connect our model to the 2D images that will be available at test time. This includes 6 degrees of freedom, 3 for translation, and 3 for rotation.

We consider momentarily that the object is at a fixed depth, which amounts to working with images that are scale-normalized, where scale is indicated either by an object detection module, or by a ground-truth bounding box. As our experiments show, searching around this originally estimated scale can yield some improvements, but we ignore it from the following discussion. Regarding horizontal and vertical translation, our algorithm effectively does an efficient, exhaustive search.

The remaining degrees of variation include the camera's azimuth, elevation and rotation with respect to the object's canonical coordinate system in 3D. For this we introduce an additional viewpoint variable, v, which can either be provided by the output of NRSfM (which requires multiple images and landmark annotations), or by a bottom-up viewpoint estimator, as e.g. in [START_REF] Tulsiani | Viewpoints and keypoints[END_REF]. In all of our experiments we use the NRSfM-based viewpoint estimate, and compare to results of systems that use the same viewpoint estimate. One can actually search for the viewpoint through the optimization of our model's objective, but we leave this for future work.

This viewpoint variable influences the model in two ways. Firstly, the 3D nominal displacements are rotated in 3D by multiplying with R v , the rotation matrix corresponding to v; we denote this by adding a viewpoint superscript to the nominal displacement vector: µ v i,j . = R v µ i,j . The precision matrix, being spherical, is unaffected by viewpoint; dealing with elliptical matrices is equally easy, but the induced coupling of coordinates would pose challenges when we turn to optimization in Sec. 4. Secondly, the variable v is discretized into V distinct viewpoints, obtained by uniformly quantizing the 360 azimuth degrees; we denote by v the discretized value. This is used to determine in a viewpoint-dependent manner the image-to-part affinities, as detailed below.

Cost Function

Having identified the model variables and the 3D-to-2D transformation, we can now describe how we go from 2D to 3D, when presented with an image. The image provides us with 'bottom-up' evidence about the 2D positions where each visible landmark is likely to be seen. This expressed in terms of a landmark-specific unary term of the form:

U I,v,i (x i ) = u v i , f I (h i , v i ) , (1)
where

u v i
is a viewpoint-specific weight vector for node i and f I are dense image features. We use orthographic projection, assuming that the 3D landmark x i = (h i , v i , d i ) projects to the 2D image point (h i , v i ). We note also that the argument of the unary term, x i is three-dimensional, while the underlying information is two-dimensional.

The geometric arrangement between two landmarks i, j is controlled by a function of two 3D arguments that prescribes preferences for the arrangement of landmark pairs in 3D:

V i,j,v (x i , x j ) = -x j -x i -µ v i,j T C i,j x j -x i -µ v i,j , (i, j) ∈ E. (2)
In Eq. 2 µ v i,j = R v µ i,j is the viewpoint-adapted nominal displacement and C i,j is the viewpoint-invariant precision matrix described in the previous subsection. Since C i,j is a spherical precision matrix, we can write V i,j,v (x i , x j ) = γ i,j x jx i -µ v i,j 2 , showing that our model penalizes the 2 norm of the deviations of the 3D part displacements from their rotated nominal value.

Putting things together, given an image I and a viewpoint v, we score a landmark configuration X with a merit function S formed as the sum of unary and pairwise terms:

S I,v (X) = P i=1 U I, v ,i (x i ) + (i,j)∈E V i,j,v (x i , x j ), ( 3
)
where E is the set of edges on the graph. The unary terms introduce image-based evidence, and the pairwise terms enforce model-based priors. The minimization of this objective will result in an optimal placement of K landmarks in 3D while having a 2D input.

Efficient Optimization for 3D DPMs

Having developed our cost function in 3D we now turn to its optimization. We consider a star-shaped graph, where a single node ('root') is connected to all remaining nodes ('leaves'). The logarithm of the root node's max-marginals for a star-shaped graph equal:

S(x r ) = max X:Xr=xr S(X) = i max xi [U i (x i ) + V i,r (x i , x r )] , (4)
effectively scoring a candidate root position x r by optimizing over all possible part positions that may support it. In order to simplify notation we have removed the image and viewpoint dependence and introduced V i,r (x i , x r ) which is defined to be zero when x i = x r and infinity otherwise.

For the particular form of the pairwise term used here one can use the Generalized Distance Transform (GDT) of [START_REF] Felzenszwalb | Distance transforms of sampled functions[END_REF], reducing the computational complexity of message-passing from O(N 2 ) to O(N ) in the number of voxels. This can be fast in 2D, but in 3D we face a linear increase of complexity and memory in the depth resolution -so we will need to eventually tradeoff speed for accuracy.

However, we realize that the Dual-Tree Branch-and-Bound (DTBB) algorithm of [START_REF] Kokkinos | Rapid deformable object detection using dual-tree branch-and-bound[END_REF] directly applies to this problem. In particular, in DTBB rather than first exhaustively computing Eq. 4 for all values of x r and then picking the maximum, one instead performs prioritized search for the maximum -which can replace a complexity of O(N ) with one of ω(log N ), i.e. logarithmic in the best-case, which is typically orders of magnitude faster. Furthermore, since for our case the unary terms are depth-independent, one never needs to occupy memory to represent U r (x r ), as would be required by GDT -instead our algorithm's memory complexity is constant in depth resolution.

In a bit more detail, the DTBB algorithm performs prioritized search over intervals of root positions, denoted by X, using as priority an upper bound to the score in the interval. For this one bounds the right side of Eq. 4 over a root interval X, using the following series of inequalities:

max xr∈X S(x r ) ≤ i max xr∈X,xi U i (x i ) + V i,r (x i , x r ) ≤ i max xi U i (x i ) + i max xr∈X,xi V i,r (x i , x r ), (5)
where both inequalities follow from max x f (x) + g(x) ≤ max x f (x) + max x g(x). Intuitively, the first inequality opportunistically uses contributions from different nodes, even if they do not agree on the particular x r ∈ X that they support, and the second inequality opportunistically uses contributions from the unary and pairwise terms of a single node, even if they do not agree on the value of x i that lends the support.

Two facts prove useful in computing Eq. 5 efficiently: firstly, the maximization max xi U i (x i ) can be computed in 2D, since U i (x i ) is independent of the d i component of x i . As such, we never need to explicitly allocate memory to store the unary term in 3D, as would be required by GDTs. Secondly, the maximization over the combinations of x i , x r can be computed analytically, with a cost that is constant, and independent of the cardinality of the two sets; all one needs to do is extend the 2D bounding schemes of [START_REF] Kokkinos | Bounding Part Scores for Rapid Detection with Deformable Part Models[END_REF] to 3D, and the complexity increases from 4 summation and multiplication operations (in [START_REF] Kokkinos | Bounding Part Scores for Rapid Detection with Deformable Part Models[END_REF]) to 6. Other than these two observations, we use the exact same algorithm as in [START_REF] Kokkinos | Rapid deformable object detection using dual-tree branch-and-bound[END_REF][START_REF] Kokkinos | Bounding Part Scores for Rapid Detection with Deformable Part Models[END_REF]; for lack of space we refer the interested reader to those references for a more thorough presentation of DTBB.

Another substantial accelaration can be obtained by noting that the pairwise term is invariant to depth translations. Combining this with the depthindependent nature of our unary terms, means that we have a one-dimensional family of equally good solutions. Intuitively, the only constraint imposed by our model consists in properly 'unfolding' the object in 3D space, while the particular depth value around which this happens is irrelevant. As illustrated in our experimental results in 2, Branch-and-Bound would waste time on exploring evenly all those equivalent solutions; instead we fix the model's root node at a fixed depth, and use it as an anchor point for the leaf nodes.

Model learning

Having outlined our cost function and our optimization algorithm we now turn to parameter estimation. Given a candidate configuration X = (x 1 , . . . , x P ) of P parts, we treat our cost function in 3 as the inner product between an image-specific feature vector F(X) and a model-specific weight vector w, S(X) = w, F(X) .

The feature vector comprises the P D-dimensional vectors extracted from the part positions f (x p ), p = 1, . . . , P , and the model deformations with respect to the nominal displacements from the leaves to the root node (x p -x l -µ v r,p ) 2 , p = 2, . . . , P for each of the 3 dimensions. This accounts for a total size of P D+3(P -1), which is also the dimension of the learned weight vector. We do not estimate µ v r,p discriminatively, as this would impede the viewpoint-based coupling of these parameters described in Sec. 3.2. We do however estimate the relative weight of the above 2 distance and use the average displacement to define µ, which combined with the viewpoint v yields µ v r,p . The unary terms of graph nodes that do not correspond to one of the human-annotated keypoints are set to 0, meaning that the image evidence does not affect their position -while for a given viewpoint we set to zero the features of points that are not visible.

In order to learn the corresponding parameter weights, we use Structured Support Vector Machine (SSVM) training a cutting-plane optimizer [START_REF] Joachims | Cutting-plane training of structural svms[END_REF], as done in the context of Deformable Part Models e.g. in [START_REF] Pepik | Multi-view and 3d deformable part models[END_REF][START_REF] Boussaid | Fast and exact: Admm-based discriminative shape segmentation with loopy part models[END_REF]. In particular we measure the performance of a particular weight vector in terms of a loss function ∆(X * Ii , Xi ) which represents the cost incurred by labelling image i as X *

Ii when the ground truth is Xi . We choose to use the Mean Euclidean Distance, ∆( X, X) = 1 P P p=1 x p -xp 2 as a loss for our learning task, penalizing the 3D displacement of our estimated landmarks from their ground truth positions. This loss decomposes over each node of the graph. This allows us to leverage the tractability of the inference in the learning procedure, as is common in Structured SVMs.

More specifically, each iteration of the cutting plane algorithm requires the computation of the most violated constraint given the current estimate of the joint weight vector w i , finding a configuration X i cp that is consistent with the model, yet incurs a high loss. This subroutine corresponds to the optimization problem:

X i cp = arg max X S I,v ( X) + ∆( X, X) (6)
for each instance (I, X) of the labelled training set. By incorporating the loss in the expression of our model's configuration score , this problem is cast as an equivalent inference problem with modified unaries, scoring a configuration as:

SI,v ( X) = P i=1 U I, v ,i (x i ) + δ(x i , x i ) + (i,j)∈E V i,j,v (x i , x j ) (7)
where δ( xi , x i ) = 1/P xix i . The complexity of the subroutine is therefore equivalent to the complexity of our inference algorithm. This framework allows to learn the joint weight vectors in a tractable time of the order of a few hours per view and category.

Results

We use the Pascal 3D+ dataset for all of our experiments [START_REF] Xiang | Beyond pascal: A benchmark for 3d object detection in the wild[END_REF], comprising 1408 images over 10 object categories. The ground truth 3D objects are given by the dataset via rotated and positioned CAD models. We use these CAD models solely for the evaluation of our method.

For feature computation we extract dense image features using the Deeplab network of [START_REF] Chen | Semantic image segmentation with deep convolutional nets and fully connected crfs[END_REF], which is a fully convolutional neural network (FCNN) trained for semantic segmentation. We use the intermediate-level layer activations from layers 3 and 5 yielding a position-dependent feature vector of dimension D = 769. Using both lower-and mid-level features gives our unary terms the option of achieve both good localization results (low-level), and good invariance to intra-class appearance variability (high-level).

We evaluate our models in terms of inference acceleration and model performance. Firstly we benchmark the runtime of Branch-and-Bound in 3D and compare it to message-passing with Generalized Distance Transforms [START_REF] Felzenszwalb | Distance transforms of sampled functions[END_REF], commonly used in Deformable Part Models. Secondly we demonstrate that our method outperform the previous state of the art of [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] on 7 out of 10 categories using multi-scale of the Pascal 3D+ dataset. The single-scale version doesn't decisively outperform [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] (5/10), but yields comparable results in much faster runtime.

Branch-and-Bound in 3D

To benchmark the acceleration delivered by Branch-and-Bound in 3D we test our algorithm with a varying number of depth layers n d ; Our algorithm has a logarithmic best-case complexity, while inference with the Generalized Distance Transform (GDT) ( [START_REF] Felzenszwalb | Distance transforms of sampled functions[END_REF]) scales linearly in n d .

Figure 2 on the left empirically demonstrates that this is the case, showing the runtime of Branch-and-Bound on a varying number of depth layers (yellow graph). We set it against a Generalized Distance Transform (GDT) based implementation (blue graph). The timings have been obtained by averaging over the individual contributions of 100 images, 10 from each category, the average standard deviation has been annotated in the graph. The GDT-based inference is about two orders of magnitude slower than the inference with Branch-and-Bound if we set n d = 100. The red graph displays the runtime of Branch-and-Bound when the model is not anchored in depth to distinguish between otherwise equivalent solutions.We note that above a certain size of depth range the computation times increases sharply, indicating that the number of equivalent solutions increases and Branch-and- Bound explores these solutions. By contrast the anchored Branch-and-Bound only increases logarithmically in n d , being able to perform inference in less than 0.2 seconds.

Surface Estimation

Following the methodology of Kar et al. [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF], we measure the performance of our method by using the Hausdorff distance d H to compare the system's output with the ground truth, d H (X, Y ) = max{sup x∈X inf y∈Y d(x, y), sup y∈Y inf x∈X d(x, y)}, with points x ∈ X being the points on the surface of the ground truth shape X and points y ∈ Y being the points on the surface of the inferred shape Y following rigid alignment.

We display in Table 1 the average Hausdorff distance between the inferred mesh of our star-graph model, and reference CAD model associated to the object instance. In the third row of this table, we show that applying the model on different scales improves the Hausdorff error, which hints at possible future improvements of our method incorporating viewpoint estimation in the inference. Moreover, Fig. 3 shows some examples of inferred placed models. We observe that despite the simplicity of star-shaped graphical models and the speed of the inference, we are competitive to [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF], obtaining a better accuracy [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] in most categories.

Table 1. Mesh errors computed using the Hausdorff error with respect to the centered ground-truth CAD models provided in Pascal VOC 3D+ (lower is better).

plane bike boat bus car chair sofa train tv mbike mean Kar et al. [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] 2.2 4.4 6.0 3.9 3.2 2.6 8.8 6.6 4.5 2.9 4.5 1 star 2. In this work we have shown that Branch-and-Bound is suitable to infer DPMs in 3D and can preserve its logarithmic scalability. To this end we also provide a method to learn DPMs from silhouette information and viewpoint annotations. The model is simple, but outperforms the model of Kar et a. [START_REF] Kar | Category-specific object reconstruction from a single image[END_REF] in some categories by a significant margin. On average over categories we yield an 11% smaller Hausdorff error.

From our results, we see that BB can be a good option for rapid inference. This shows that future work is needed to explore the full potential of BB. Our future investigations will also aim at extending Branch-and-Bound to more general energies (for example loopy graph structures) and other types of potentials.

Using an energy-based model also leaves open the potential of coupling structured prediction techniques with CNN training [START_REF] Chen | Learning Deep Structured Models[END_REF] for the task of surface estimation. We leave this last direction for future work, but we consider it as a promising direction that is opened by our energy-based approach.

Acknowledgement

This research has been supported by the FP7-RECONFIG and H2020-I-SUPPORT projects of the European Union.

Fig. 2 .

 2 Fig. 2. Left: acceleration of branch-and-bound versus Generalized Distance Transforms as a function of depth resolution. The yellow curve shows the runtime of inference with our Branch-and-Bound algorithm in 3D. The red curve reveals the effect of not anchoring the model in depth, whereas the blue curve represents the implementation with GDTs. Branch-and-Bound is orders of magnitude faster than the GDT based implementation even on moderate depth ranges. Right: Branch-and-Bound performance on two indicative categories, car and aeroplane. The runtime of our algorithm is hardly affected when increasing the number of depth layers.

Fig. 3 .

 3 Fig. 3. Some reconstructed surfaces in 5 categories.

0 7

 0 4 4.1 6.1 4.1 3.1 3.2 5.3 6.3 3.4 3.0 4.1 1 star multiscale 2.4 4.0 5.7 3.8 3.1 3.0 5.5 6.0 3.3 3.0 4.Conclusion and Future Work


Gianluca Barbon

Michael Margolis

Filippo Palumbo

Franco Raimondi

Nick Weldin

Computer Communications

Keywords: Arduino, MQTT, IoT, Service Discovery, Communication Middleware

Micro-controllers such as Arduino are widely used by all kinds of makers worldwide. Popularity has been driven by Arduino's simplicity of use and the large number of sensors and libraries available to extend the basic capabilities of these controllers. The last decade has witnessed a surge of software engineering solutions for "the Internet of Things", but in several cases these solutions require computational resources that are more advanced than simple, resource-limited micro-controllers.

Surprisingly, in spite of being the basic ingredients of complex hardware-software systems, there does not seem to be a simple and flexible way to (1) extend the basic capabilities of micro-controllers, and (2) to coordinate inter-connected micro-controllers in "the Internet of Things". Indeed, new capabilities are added on a per-application basis and interactions are mainly limited to bespoke, point-to-point protocols that target the hardware I/O rather than the services provided by this hardware.

In this paper we present the Arduino Service Interface Programming (ASIP) model, a new model that addresses the issues above by (1) providing a "Service" abstraction to easily add new capabilities to micro-controllers, and (2) providing support for networked boards using a range of strategies, including socket connections, bridging devices, MQTT-based publish-subscribe messaging, discovery services, etc. We provide an open-source implementation of the code running on Arduino boards and client libraries in Java, Python, Racket and Erlang. We show how ASIP enables the rapid development of non-trivial applications (coordination of input/output on distributed boards and implementation of a line-following algorithm for a remote robot) and we assess the performance of ASIP in several ways, both quantitative and qualitative.

Introduction

The Internet of Things (IoT) paradigm bases its success on the pervasive presence around us of a variety of objects (such as Radio-Frequency IDentification -RFID-tags, sensors, actuators, mobile phones, etc.) which, through unique addressing schemes, are able to interact with each other and cooperate to reach common goals [START_REF] Atzori | The internet of things: A survey[END_REF].

Surprisingly, in spite of being the basic ingredients of complex hardware-software systems, there does not seem to be a simple and flexible way to [START_REF] Atzori | The internet of things: A survey[END_REF] extend the basic capabilities of micro-controllers, and (2) to coordinate inter-connected microcontrollers in IoT scenario. Indeed, new capabilities are added Email addresses: gianluca.barbon@inria.fr (Gianluca Barbon), m.margolis@mdx.ac.uk (Michael Margolis), filippo.palumbo@isti.cnr.it (Filippo Palumbo), f.raimondi@mdx.ac.uk (Franco Raimondi), n.weldin@mdx.ac.uk (Nick Weldin) on a per-application basis and interactions are mainly limited to bespoke, point-to-point protocols that target the hardware I/O rather than the services provided by this hardware.

Several commercial off-the-shelf devices are available on the market, but usually they are tightly coupled with specific vendors and require local gateways to export sensors and actuators as services on the Web. Instead, by embracing the open source and hardware principles, it is possible to offer a system easily modifiable to suit the user needs and to be used as the basis for new products in different scenarios. Micro-controllers such as Arduino are used widely by all kinds of makers worldwide. Popularity has been driven by Arduino's simplicity of use and the large number of sensors and libraries available to extend the basic capabilities of these controllers. Using such an inexpensive device makes the installation and maintenance of a system easier. In this way, it is possible to offer a system easily modifiable to suit the user needs and to be used as the basis for new products in different scenarios.

A first approach using the Internet for interacting with realworld resource-constrained devices was to incorporate smart things into standardized Web service architectures (such as SOAP, WSDL, UDDI) [START_REF] Guinard | Interacting with the soa-based internet of things: Discovery, query, selection, and ondemand provisioning of web services, Services Computing[END_REF] or embedding HTTP servers into the devices. However, in practice, this resulted to be too heavy and complex for simple objects [START_REF] Guinard | From the internet of things to the web of things: Resource-oriented architecture and best practices[END_REF]. In order to face the problem of interconnecting several resource-constrained nodes among each other and to the Internet, several communication protocols have been introduced [START_REF] Sheng | A survey on the ietf protocol suite for the internet of things: Standards, challenges, and opportunities[END_REF]. These protocols are inspired by machineto-machine (M2M) scenarios and share the same fundamentals of communication paradigms typical of standard computer networks. M2M communications occur among machines (objects or devices) with computing/communication capabilities without human intervention [START_REF] Kim | M2m service platforms: survey, issues, and enabling technologies[END_REF].

In this paper we present the Arduino Service Interface Programming (ASIP) model, a new model that addresses the issues above by [START_REF] Atzori | The internet of things: A survey[END_REF] providing a "Service" abstraction to easily add new capabilities to micro-controllers, and (2) providing support for networked boards using a range of strategies, including socket connections, bridging devices, MQTT-based publish-subscribe messaging, discovery services, etc. We provide an open-source implementation of the code running on Arduino boards and client libraries in Java, Python, Racket and Erlang. Our programming model allows to tackle the heterogeneity that is a distinguishing feature of several IoT applications; by heterogeneity we mean here hardware differences (different microcontrollers), performances/capabilities of different boards in terms of CPU power, memory, and storage, and software heterogeneity (e.g., choice of programming languages). We show how ASIP enables the rapid development of non-trivial applications (coordination of input/output on distributed boards and implementation of a line-following algorithm for a remote robot) and we assess the performance of ASIP in several ways, both quantitative and qualitative.

The rest of the paper is organized as follows. We review related work in Section 2; we introduce the ASIP model in Section 3, describing the software architecture, the communication protocol and the possible communication channels: serial, TCP, and MQTT publish/subscribe messaging. We present a detailed experimental evaluation of ASIP performance in Section 4. In Section 5, instead, we give a qualitative evaluation by providing examples of how applications can be built on top of ASIP.

Related Work

The emerging IoT scenario, exploiting the advances made in the M2M field, enables the possibility of building a huge Service Oriented Architecture (SOA) composed of several devices offering services each other [START_REF] Guinard | Interacting with the soa-based internet of things: Discovery, query, selection, and ondemand provisioning of web services, Services Computing[END_REF]. Existing application platforms use REST architecture [6,7,[START_REF]Nimbits[END_REF][START_REF] Evrythng | [END_REF][START_REF]Oneplatform by exosite[END_REF][START_REF]Axeda platform[END_REF][START_REF] Sensorcloud | [END_REF][START_REF] Neuaer | [END_REF][START_REF]idigi device cloud[END_REF] as interfaces in order to expose their services. The REST-style architecture consist of clients and servers. Clients initiate requests to servers; servers process requests and return the appropriate responses manipulating the resources. A resource can be any thing identified by URIs. REST uses the GET, PUT, POST, and DELETE operations of HTTP to access resources. However, the protocols used for RESTful architecture are not appropriate for resource constrained networks and devices [START_REF] Colitti | Rest enabled wireless sensor networks for seamless integration with web applications[END_REF]. The large overhead of HTTP causes packet fragmentation and performance degradation when dealing with M2M devices. Also, TCP flow control is not appropriate for resource-constrained devices and the overhead is too high for short transactions.

To extend the REST architecture for resource-constrained devices, a first solution presented in the literature is given by the Constrained Application Protocol (CoAP) [16]. CoAP is a protocol intended to be used in simple devices allowing them to communicate over the Internet. CoAP includes a subset of the HTTP functionalities, optimized for M2M applications. It also supports multicast, very low overhead, and asynchronous message exchanges over a user datagram protocol (UDP) [17]. However, also in CoAP, the HTTP protocol is still present. It has not been designed to support persistent communication and, even if Web Sockets have been introduced in the recent draft of HTML 5 (offering a bidirectional communication channel between client and server), they totally hide the naming scheme that makes REST so powerful: every resource having a standard unique identifier, the URI. The Web Sockets approach results in non-standard solutions for manipulating resources [START_REF] Collina | Introducing the qest broker: Scaling the iot by bridging mqtt and rest[END_REF]. In order to support collaboration between devices, there is the need to unify the naming scheme of smart objects and the URIs. For this purpose, a new communication paradigm has been presented in the literature based on the "publish-subscribe" (pub/sub) mechanism [START_REF] Eugster | The many faces of publish/subscribe[END_REF][START_REF] Sheltami | A publish/subscribe middleware cost in wireless sensor networks: A review and case study[END_REF].

Directed Diffusion [START_REF] Intanagonwiwat | Directed diffusion for wireless sensor networking[END_REF] is considered the earliest pub/sub communication paradigm for WSN. It is a data-centric protocol in which named data is described by attribute-value pairs. The subscriptions are called interests and are broadcasted throughout the whole WSN. Another early pub/sub middleware for WSN is Mires [START_REF] Souto | Mires: a publish/subscribe middleware for sensor networks[END_REF]. It is implemented on top of TinyOS [START_REF] Levis | Tinyos: An operating system for sensor networks[END_REF], an event-based operating system for WSNs. In Mires each sensor advertises its topics (e.g. temperature, pressure, luminosity, etc.) to the applications through a sink node. A slightly different programming approach is used by TinyCOPS [START_REF] Hauer | A component framework for content-based publish/subscribe in sensor networks[END_REF], a component-based middleware that also provides a contentbased pub/sub service to WSN that tries to simplify the composition of services through components (communication protocol, supported data, and service extensions). Recently, Object Management Group (OMG) has published DDS, an open standard for data-centric publish-subscribe middleware platforms with real-time capabilities [START_REF] Omg | Data distribution service for real-time systems[END_REF]. TinyDDS [START_REF] Boonma | Self-configurable publish/subscribe middleware for wireless sensor networks[END_REF] is the adopted version of OMG DDS for WSN, based on TinyOS. It is a lightweight pub/sub middleware that allows applications to interoperate across the boundary of WSNs and access networks, regardless of their programming languages and protocols.

All of these solutions are strictly coupled with the hardware platform and they usually need centralized hardware infrastructure (sink nodes or gateways) [START_REF] Castellani | Architecture and protocols for the internet of things: A case study[END_REF][START_REF] Zhu | Iot gateway: Bridgingwireless sensor networks into internet of things[END_REF]. Also the MQTT protocol introduced by IBM uses hierarchical topic based [START_REF] Hunkeler | Mqtt-sa publish/subscribe protocol for wireless sensor networks[END_REF] publishsubscribe mechanism and facilitates the constrained devices by enabling "pushing" [START_REF] Franklin | data in your face: push technology in perspective[END_REF] data from the cloud rather than polling by constrained device for the data from the server. In this case the overlay infrastructure is a software component, the broker. The broker is responsible for distributing messages to interested 2 clients based on the topic of a message. In the sensor domain, IBM has come up with yet another protocol MQTT for Sensor Networks (MQTT-SN) [START_REF] Stanford-Clark | Mqtt for sensor networks (mqtt-sn) protocol specification[END_REF] which is designed in such a way that the protocol is agnostic of the underlying networking services.

From the devices availability point of view, there are two types of hardware platforms that can be connected to IoT service platforms. One is off-the-shelf commercial products that are related to certain platforms, for example, Cosm consumer products [6], ioBridge [START_REF]iobridge -connect things[END_REF], NanoRouter [17], MicroStrain Sensors [START_REF]Lord sensing microstrain[END_REF], and Digi routers [START_REF]idigi device cloud[END_REF]. The second type is an open hardware (development/hackable) platform that users can develop themselves, such as Arduino [START_REF]Arduino[END_REF], mBed [START_REF] Armmbed | [END_REF], or Nanode [START_REF] Nanode | [END_REF]. Embracing the open source and hardware principles, it is possible to offer a system easily modifiable to suit the user needs and to be used as the basis for new products in different scenarios.

Different solutions have been proposed in order to bring the IoT paradigm on the Arduino platform. In the healthcare field, a textile version of the Arduino platform, called LilyPad [START_REF]Lilypad arduino main board[END_REF], has been used to bridge wearable medical devices to IoT enabled infrastructure using a mobile device as gateway. In [START_REF] Cerqueira Ferreira | Iot architecture to enable intercommunication through rest api and upnp using ip, zigbee and arduino[END_REF], authors propose a model to enable the event reading and the controlling of electrical devices using a master controller that acts as a gateway that is a standard PC. In the energy monitoring scenario, [START_REF] Barsocchi | Smart meter led probe for real-time appliance load monitoring[END_REF] describes a non-intrusive load monitoring system for domestic appliances where a web server is embedded on the Arduino board. These solutions embed HTTP web servers on board that make easier to fetch the exposed information in oneto-one client-server connections. Our aim is to avoid the presence of local gateways or embedded resource-consuming web servers, offering the possibility to coordinate inter-connected micro-controllers through Internet providing support for networked boards with different strategies: socket connections, bridging devices, and MQTT-based pub/sub messaging.

Pairwise evaluations and comparisons of HTTP, CoAP and MQTT protocols have been reported in the literature. For example, [START_REF] Al-Fuqaha | Internet of things: A survey on enabling technologies, protocols, and applications[END_REF][START_REF] Thangavel | Performance evaluation of mqtt and coap via a common middleware[END_REF][START_REF] Colitti | Evaluation of constrained application protocol for wireless sensor networks[END_REF] compares the performance of MQTT, CoAP, and HTTP in terms of end-to-end transmission delay and bandwidth usage [START_REF] Thangavel | Performance evaluation of mqtt and coap via a common middleware[END_REF] and in terms of energy consumption and response time [START_REF] Colitti | Evaluation of constrained application protocol for wireless sensor networks[END_REF]. Based on their results, MQTT delivers messages with lower delay than CoAP when the packet loss rate is low, while, due to its condensed header and small packet size, CoAP is more efficient than HTPP in transmission time and energy usage. Regarding the power consumption of the devices, there is a detailed experiment for power consumption comparison between HTTP and MQTT on mobile devices [START_REF] Nicholas | Power profiling: Https long polling vs. mqtt with ssl, on android[END_REF]. The result shows that the MQTT protocol wins in all tests, which include establishing, maintaining, and receiving/sending messages [START_REF] Chen | Converging mqtt resources in etsi standards based m2m platform[END_REF]. From these considerations, we choose to implement a simple text-based service discovery mechanism to let several resource-constrained microcontrollers to discover each other with their functionalities and to exchange messages among them.

From the programming model point-of-view, in order to expose sensors and actuators as services, the components connected to the micro-controller need to be programmed individ-ually to take into account both low-level implementation details and the high-level requirements of the application of which the micro-controller is part. Several solutions have been proposed in order to address the issue of abstracting low-level implementation details [START_REF] Derler | Modeling cyber-physical systems[END_REF]. Most of them are tightly targeted to particular applications [START_REF] Quigley | Ros: an open-source robot operating system[END_REF] or hardware platforms [START_REF] Levis | Tinyos: An operating system for sensor networks[END_REF]. Instead of relying on a dedicated operating system, in this paper we propose that sensors and actuators are exposed by micro-controllers as services, so that more complex software applications can be built by composing them. When restricted to the Arduino platform, the closest protocol to ASIP is the Firmata protocol [START_REF] Steiner | Firmata: Towards making microcontrollers act like extensions of the computer[END_REF], which enables a computer to discover, configure, read and write a microcontrollers general purpose IO pins. However, ASIP has a smaller footprint than Firmata (using around 20% less RAM). And uniquely, it supports high level abstractions that can be easily attached to hundreds of different services for accessing sensors or controlling actuators. These abstractions can decouple references to specific hardware, thus enabling different microcontrollers to be used without software modification. Although ASIP is currently implemented for Arduino boards, the protocol is hardware agnostic. Moreover, as shown below, ASIP supports communication over TCP and MQTT, while Firmata is limited to serial communication.

The ASIP programming model

In this section we describe the Arduino Service Interface Programming model (ASIP), which has been developed to simplify and accelerate the development of applications in the IoT. Applications for the IoT typically involve heterogeneous components, both in terms of software and hardware. Machineto-machine communications are the prevalent mechanism for coordination and execution of tasks. The ASIP programming model addresses this issue, together with a mechanism to integrate with existing protocols such as MQTT. We note that, while providing a seemingly Arduino-specific solution, our programming model is generic and can be implemented on top of microcontrollers with very limited resources. Our choice for Arduino has been motivated by the open-source nature of the project and by the availability of hardware. Specifically, ASIP builds upon the notion of "service" for micro-controllers: a service could be a temperature sensor, a servo motor, or any other input or output device connected to a micro-controller. Each micro-controller can be controlled using textual messages, and each micro-controller reports data using messages to so-called clients. The core ASIP implementation running on a microcontroller deploys one or more services: this enables the reusability of both micro-controller-specific code and of client code, and it opens the possibility of model-based development for complex applications involving multiple micro-controllers, as described below.

In summary, the ASIP model provides:

• A software architecture for code running on the microcontroller. • A textual protocol for messages exchanged between ASIP clients and micro-controllers implementing the software architecture mentioned above.

AsipClass

• A network architecture for the connection between microcontrollers and client that can be written in several highlevel programming languages.

These various components are described in the subsections below.

Basics: software architecture

As mentioned above, at the core of ASIP is the notion of service. We model it by means of the class AsipServiceClass (see right-hand side of Figure 1). Each service, e.g. a distance sensor, must have a unique ID and it can reuse existing Arduino libraries developed specifically for the given component (sensor, shield, motor, etc.) to obtain data from that component. Each service must implement the following methods:

• begin(), to set up the service appropriately, for instance by initialising the pins or by enabling interrupts.

• processRequest(), to process messages for the service dispatched by the class AsipClass, as described below.

If the service returns values, for instance in the case of a temperature or distance sensors, then the service should also implement the method reportValues(). This method converts data into ASIP messages, using the syntax of ASIP messages described below. A number of services is already provided with the ASIP implementation that we describe in this paper, but additional ones could be defined by implementing an AsipServiceClass to handle appropriate messages. It is assumed that all implementations of ASIP support at least the basic Input/Output ASIP service, which provides basic I/O operations at the pin level. On an Arduino board these operations include writing and reading values from digital and analog pins, thus permitting the control of LEDs or reading potentiometer values.

Service are put togethet in the class AsipClass (left-handside of Figure 1. The AsipClass is the core of ASIP and is responsible for managing services. The AsipClass on the microcontroller is connected to a stream, which can be a serial channel, a TCP socket or a MQTT pub/sub mechanism (please refer to the system architecture described below for additional details). The AsipClass must implement a run method that executes the main ASIP loop. Before the execution of the main loop, an initialization mechanism is called to set up the communication streams. The main loop performs the core operations to handle ASIP, acting like a dispatcher of messages to/from services. First of all, it listens for incoming messages, and redirects them to the proper service by recognizing the service identifier in the ASIP message header. A particular set of messages, called systems messages, are not handled though a service but are processed through proper methods supplied by the Asip-Class. Moreover, the loop allows services to reply continuously in case periodic status messages have been enabled, for instance to report a distance reading at regular time intervals.

The syntax of ASIP messages

Messages exchanged between micro-controllers and clients are plain text messages with a standard format. They can be divided into command messages and event messages. The first are sent by ASIP clients to micro-controllers, while the latter are sent on the opposite direction by the micro-controller. ASIP messages consist of an ASCII header, followed by ASCII character fields separated by commas, and terminated by the newline character.

Command (or request) messages to a micro-controller begin with a single character to indicate the desired service, followed by a comma and a single character tag to identify the nature of the request. Requests that contain a parameter are separated from the tag with a comma. As an example, the message I,d,13,1 invokes the service with ID I (typically, an Input/Output service), requesting an operation d (in this case it is a request to write on a digital pin) with parameters 13 and 1. These parameters indicate, respectively, pin 13 and the value 1 (high).

In the other direction, reply messages from the microcontroller begin with one of the following characters:

• "@" defines an event message responding to a request or autoevent. These messages are composed of three bytes following the "@" character: a character indicating the service, a comma, and the tag indicating the request that triggered this event respectively.

• "˜" defines an error message reporting an ill formed request or some other problems affecting the server. These messages contain the service and tag associated with the error followed by an error number and error string.

• "!" defines an informational or debug message consisting of unformatted ASCII text terminated by the newline character.

Some reply event messages have a payload with a variable number of fields with the following format:

• a numeric value that precedes the message body indicating the number of fields in the body • all numeric values are expressed as ASCII text digits and are decimal unless otherwise stated.

Figure 2 reports the syntax for a distance service.

System Architecture

Micro-controllers can be connected to clients in a number of way: directly using a serial connection (over USB), by means of TCP sockets, or using an MQTT-based publish/subscribe messaging mechanism.

Serial sockets and TCP connections are used in point-topoint connections, when a client has exclusive access to a device, for instance for controlling a robot. The MQTT-based architecture allows sending and receiving data to and from multiple devices, thus resulting useful in applications such as sensor networks (smart homes, etc.).

Serial connection

The serial connection uses the USB bus in order to connect to a micro-controller from a computer. This is the basic configuration for the ASIP architecture. The micro-controller must run an implementation of the AsipClass described above, with at least the implementation of the Input/Output Service. Theoretically, on the computer side of the connection, a simple serial monitor could send instructions and read values being reported. In practice, applications are written in a high-level language to make use of the services installed on the micro-controller. Various implementations of the serial client exist for different languages:

• Java: https://github.com/fraimondi/java-asip

TCP and MQTT bridges

Before introducing the TCP and the MQTT architecture we introduce the notion of bridge to address the issue of network connection for micro-controllers. Indeed, a micro-controller such as an Arduino board needs an additional ethernet or a wifi device to communicate on a network. This device may be an Arduino shield, or an external device. In the first case, the Arduino ASIP client sketch integrates the code needed to talk to the shield. In the latter case, instead, the Arduino sketch can be connected using a standard serial connection to the external device and it does not require modifications. Thus, it is the external device that will take care of the network communications. We call this kind of devices bridges.

The bridge logic is very simple: the bridge listens to incoming messages from the network and routes them to the serial port. In the other direction, the bridge listens to incoming messages from the micro-controller over its serial connection and it redirects them to the network interface. A bridge does not implement ASIP classes or services, because its only function is to permit the communication between different transmission medium. In order to avoid the presence of errors in the conversion between two transmission channels, error checking can be implemented.

Bridges can be implemented using different kinds of hardware platforms. For the testing phase of this paper, the Raspberry PI 2 has been used as hardware platform. However, lighter platforms can be adopted [START_REF]Particle (formerly spark) -build your internet of things[END_REF] and we have successfully employed the ESP8266 chip, a lightweight SoC that features low power consumption and includes a wi-fi antenna 1 .

Bridges can be employed both for TCP and for MQTT connections, as explained below. The Java and Python implementations of ASIP clients include bridges for TCP and for MQTT.

The adoption of bridges brings some advantages:

• a single board can be used by different clients;

• use of low cost devices instead of expensive Arduino shields (like the Ethernet and Wi-Fi shields);

• use of devices with very low power consumption;

• reduction of the workload on the Arduino board.

TCP

Connecting to an Arduino through TCP may require the adoption of a bridge, depending on how the micro-controller is connected to the network. A micro-controller implementing ASIP messaging over TCP must have an IP address and a dedicated TCP port open to connections. Once a client opens a connection to the address and port creating a socket, the exchange of messages continues identically to the serial communication. In fact, client applications developed to work over serial communication can be immediately translated into TCP-based applications just by replacing the client connection class. Code for TCP clients is provided in the Java and Python repositories mentioned above.

Even if the micro-controller is limited to single connections, nothing prevents the client from opening connections to multiple, networked devices, thus enabling the coordination of networked micro-controllers. Notice that sockets can be created even over internet, thus enabling the control of possibly very remote micro-controllers. In addition, if an appropriate DNS record can be provided for each micro-controller, standard domain naming mechanisms can be used to identify boards and bridges.

MQTT

ASIP messages can be exchanged using MQTT. The main advantage is in the implementation of clients that need to connect to multiple boards: instead of opening a socket for each micro-controller, the client can simply subscribe and publish messages to a broker. Similarly, MQTT bridges forward serial messages from the board to publish actions for appropriate topics and route subscribed messages to the serial channel. More in detail, we assume that each micro-controller is identified by a unique name and we employ the following scheme for topics:

• Messages from a specific board are published by the board (or by its bridge) to the MQTT broker with topic asip/BOARDNAME/out, where BOARDNAME is the unique identifier of the micro-controller.

• Messages to a specific board are published by clients to the MQTT broker with topic asip/BOARDNAME/in.

In practical terms, an MQTT bridge for a board should subscribe to topic asip/BOARDNAME/in and forward messages received on this topic to the serial connection. The same bridge should publish serial messages from the board to topic asip/BOARDNAME/out. Conversely, a client of a specific board should subscribe to topic asip/BOARDNAME/out to receive messages from the board, and publish messages to asip/BOARDNAME/in to send messages to the board.

Implementations of MQTT bridges and sample clients are available in the Java and Python repositories.

Service-level discovery mechanism

In order to let the devices know the presence of other devices and their embedded sensors/actuators exposed as services, we propose a service discovery overlay that exploits the MQTT protocol capabilities. We follow the approach presented in [START_REF] Palumbo | Sensor network infrastructure for a home care monitoring system[END_REF], where the service discovery functionality is realized by intelligent buses, namely the context, service and control buses. All communications between devices can happen in a round-about way, via one of them. Each of the buses handles a specific type of message/request and is realized by different kinds of MQTT topics. This approach has been proven useful in different application scenarios, spanning from ambient assisted living [START_REF] Palumbo | Aal middleware infrastructure for green bed activity monitoring[END_REF], mobile [START_REF] Palumbo | Gp-m: Mobile middleware infrastructure for ambient assisted living[END_REF], and energy monitoring [START_REF] Barsocchi | Ems@ cnr: An energy monitoring sensor network infrastructure for in-building location-based services[END_REF] infrastructures.

In particular, as soon as a micro-controller is turned on, it announces his presence publishing a message containing his unique identifier on the service bus topic (asip/servicebus) and it subscribes to the same topic in order to be notified by the MQTT broker about existing (already announced) or new services to be announced. In this way, all the devices can discover its presence and start to listen for its messages subscribing to the relative context bus topic (asip/BOARDNAME/out). Micro-controllers, if capable, can also accept commands, subscribing to their control bus (asip/BOARDNAME/in) and waiting for messages published by other micro-controllers/services on the same topic. Figure 3 shows an example of a possible interaction among different micro-controllers (B1,...,B4) and a remote service translating MQTT topics to REST resources (the description of this kind of service is out of the scope of this paper, see [START_REF] Collina | Introducing the qest broker: Scaling the iot by bridging mqtt and rest[END_REF][START_REF] Chen | Converging mqtt resources in etsi standards based m2m platform[END_REF] for possible solutions). A micro-controller can also expose different sensors/actuators as services (B4 in the figure announcing sensor S1 and actuator S2). In the example, B4 announces itself and its sensors/actuators publishing the relative identifiers on the service bus topics: PUBLISH asip/servicebus B4 PUBLISH asip/servicebus/B4 S1 PUBLISH asip/servicebus/B4 S2 then, it starts publishing data from B4/S1 on the relative context bus topic and it subscribes to the context bus topic relative to B4/S2, waiting for incoming commands:

PUBLISH asip/B4/S1/out data SUBSCRIBE asip/B4/S2/in

In the depicted example, micro-controllers B1, B2, and B3 are consumers of B4/S1 and they have already subscribed to the relative context bus topic, so they start receiving the required data. In the meantime, the REST service exposes B4/S1 and B4/S2 as web resources and can send a command to the actuator B4/S2 publishing on the relative control bus topic:

PUBLISH asip/B4/S2

Quantitative Evaluation

In this section we provide a quantitative experimental evaluation of ASIP. In particular, we to assess the throughput (how many messages per second can be sent?) and the latency (what is the delay between a request and a response?) for the possible network architectures described above: direct serial connection, TCP socket, and MQTT publish/subscribe.

Throughput

In this work we define throughput for ASIP as the number of messages per second that can be sent over a communication channel. Intuitively, this corresponds to the maximum frequency of updates that can be achieved, for instance to control a robot.

Experimental set-up

Figure 4 sketches our experimental set-up. At a high level, we use a signal generator to generate periodic impulses that are received by a micro-controller running ASIP on input pin 2. A client is connected to the Arduino using one of the possible channels (serial, TCP, MQTT) and it sets the value of output pin 13 according to the value read on pin 2. We then use an external oscilloscope to track the original signal entering pin 2 and the signal generated by the ASIP client on pin 13 to make sure that the frequencies are the same. If this is the case, then ASIP can process this number of messages per second. More in detail, in Figure 4:

• The Arduino depicted on top acts as the signal generator by emitting a signal on pin 9. The Arduino is running a simple sketch that generates a periodic signal with a specific frequency (in our sketch this value can be changed on-the-fly).

• The Arduino depicted on the lower part of the figure runs ASIP and is connected to a client through pins 0 and 1.

• The Raspberry Pi runs ASIP client code, which could be written in Java or in Python. Notice that the Raspberry Pi could be replaced by a laptop connected to the Arduino using a USB connection, or it could be replaced by a bridge for TCP or MQTT, which could in itself be a Raspberry Pi or an ESP 8266 chip.

• An external two-input oscilloscope (not depicted in the figure) compares the signal generated by the Arduino depicted on top with the signal generated on pin 13 of the Arduino depicted on the bottom.

We used an oscilloscope in order to see the difference between the wave generated by the wave generator and the resulting wave obtained after "travelling" through the ASIP network. This allowed to have a visual feedback about the throughput, in order to check the maximum rate allowed by ASIP. An example output for the oscilloscope is depicted in Figure 5. In this figure, the signal in the lower part is the signal from the signal generator, while the signal on top is the signal from the ASIP board (the drift between the two waves is the latency, assessed separately in the section below). The figure depicts a frequency for which the ASIP client can track the signal correctly, because the number of peaks is the same in both traces. When the frequency of the original signal increases above a certain threshold, the top wave fails to track the signal and misses some of the peaks.

Notice that the logic of the test is all performed in the ASIP client. The incoming signal from pin 2 is sent through an ASIP message from Arduino to the client. The client processes the message, reads the value and establishes the value of pin 13. Finally it sends a message to the Arduino with the new value for pin 13. Essentially, the aim of this set-up is to replicate the behaviour of the signal generator using ASIP. The parameters that can be varied are:

• Type of connection: serial, TCP or MQTT.

• Software for the ASIP client: Java or Python language.

• Hardware where the client is running: Raspberry Pi or other machine. We have used a Macbook Pro and a Macbook Air (see below for details).

• In the case of networked connection: hardware and software configuration of the bridge.

• In the case of MQTT: broker location. Notice that we employ MQTT QoS level 0 ("at most once").

We report detailed experimental results in the following section.

Results

We present throughput experimental results separately for Java and for Python clients. The possible hardware configurations are:

• MacBook Pro: 2.4 GHz Intel Core i7, 16 GB of RAM, running Mac OS X 10.10.

• MacBook Air: 1.7 GHz Intel Core i5, 4 GB of RAM, running Mac OS X 10.8.

• RPi 2: Raspberry Pi, 900MHz quad-core ARM CPU, 1GB RAM, running the default Raspbian Linux image.

• Micro-controller: Arduino Uno running the default ASIP code available at:

https://github.com/michaelmargolis/asip

Additionally, in terms of network architecture for the experiments, we employ the following abbreviations:

• MacBook Pro, MacBook Pro Air: the client and the TCP bridge (or MQTT broker) all run on the same machine to which the Arduino is connected using a USB cable.

• RPi 2: the client runs on a Raspberry Pi 2. In the case of TCP or MQTT connections, the bridge or the broker run on a separate Raspberry Pi. The two Raspberry Pi are connected using ethernet cables and a router.

• RPi 2 bridge + MBP client: in this configuration the software client runs on the MacBook Pro while the TCP bridge (or the MQTT broker) runs on the Raspberry Pi.

Connection is through a router and ethernet cables.

• RPi 2 bridge + MBA client: as above, but the client runs on the MacBook Air.

• RPi 2 + MB broker: the MQTT broker runs on the Mac-Book Air and the client runs on the Raspberry Pi.

Figure 6a presents the experimental for the assessment of throughput using Java clients. In this set-up we employ the code available at https://github.com/fraimondi/java-asip. The serial library is provided by JSSC (https://code. google.com/p/java-simple-serial-connector/) while the MQTT library is provided by the Paho Java client (https: //eclipse.org/paho/clients/java/). The MacBook Pro runs Oracle JVM 1.8, the MacBook Air and Raspberry Pi run Oracle JVM 1.6.

Figure 6b presents the experimental for the assessment of throughput using Python clients. In this set-up we employ the code available at https://github.com/ gbarbon/python-asip. The serial library is provided by pySerial (http://pyserial.sourceforge.net/) while the MQTT library is provided by the Paho Python client (https://eclipse.org/paho/clients/python/). All experiments have been run using Python 2.7 but notice that the code is compatible with Python 3.

Discussion: The results presented in figures 6a and 6b show that ASIP can achieve a rate of messages up to 200 messages per second when the serial connection is used. In this case the limiting factor is the CPU speed of the client. As expected, TCP and MQTT performance is inferior to direct serial communication, but it is still more than adequate even for applications that require continuous monitoring, such as controlling a robot. The reduction in throughput is associated to the multiple communication layers introduced by the network libraries. Java outperforms Python in all tests; we argue that this is caused by the better performance of the Oracle JVM and its Just-in-Time compiler with respect to the Python interpreter. Interestingly, the throughput for TCP and MQTT connections is similar, with only minor differences in some circumstances. As mentioned above, MQTT connections are run at QoS level 0, and therefore there is not guarantee of message delivery, while TCP connections have built-in retransmission and sequencing guarantees. On the other hand, MQTT messaging allows broadcasting and the easy deployment of sensor networks.

Overall, we consider these results extremely promising and, in the case of serial connections, very close to the physical capacity of the communication channel, as explained in the following sections.

Latency

Testing for latency is performed using a single board. At a very high level, the test is performed by connecting an output pin with an input pin on the board, and then writing an ASIP client that sets the first pin to high and waits for a notification for the change of value of the second pin. The time difference between setting the output pin and measuring the change in the input pin is assumed to be the latency.

Similarly to the throughput test, we perform an assessment for serial connections (see Figure 7a) and for networked architectures using either TCP or MQTT (see Figure 7b).

For each one of the configurations described above we perform 100 tests and we take the average value.

Latency results

As in the case of throughput, we perform latency measures both for Java and for Python clients. The results for Java are reported in Figure 8a, while the results for Python are reported in Figure 8b.

In nearly all case, with the exception of two configurations running on resource-limited Raspberry Pi, the latency remains below 15 ms. We consider these very positive results, as the physical limitations of the serial communication channel introduce a latency of approximately 6.7 ms. This figure is computed by considering that 32 ASCII characters are exchanged in the ASIP messages for this application, by considering the additional bits required in each serial frame, and by considering the serial speed of 57600 baud.

It is interesting to notice that latency is only minimally affected by the choice of the programming language and by the communication channel.

Qualitative Evaluation

In this section we provide examples of how ASIP can be used and extended: we present how a simple distributed application can be built in Python, how a robot can be driven using a Proportional-Integral-Derivative (PID) controller [START_REF] Ang | Pid control system analysis, design, and technology, Control Systems Technology[END_REF] using Java and, finally, we show how to add a new service, both on the micro-controller and on the client code.

Building a distributed application

In this section we build a simple distributed application to coordinate two Arduino boards connected to the network using MQTT. In particular, an input button is connected to a board, and a LED is connected to the other board. Each board employs From a practical point of view, the developer needs to install ASIP on the two Arduino boards from https://github. com/michaelmargolis/asip, set up the two Raspberry Pi using either the Python or the Java MQTT bridges and, finally, implement an ASIP client. This client can run on a machine or on one of the two Raspberry Pi depicted in the figure. Excerpts for a Python client are presented in Listing 1. This client defines a class (line 7) composed of two boards of class SimpleMQTTBoard (lines 10 and 11), whose implementation is provided by the Python library available on github. Each board needs to be connected to a Broker (specified on line 42) and is identified by an ID. After initialising environment variables (lines 13 to 17) and setting the pins to appropriate modes (lines 22 and 23), the logic of the application is implemented in the loop of the main class between lines 29 and 39. The loop simply reads the state of the input pin on board1 (line 31). If the state has changed, then the state of the LED is changed appropriately (lines 36 or 38).

Notice how the communication mechanism is abstracted in this implementation. The physical location and the connection mechanism is irrelevant for the logic of the application in the main method: the only modification required to support a serial connection (or a TCP connection) is the definition of the boards on lines 10 and 11.

The expected performance in terms of latency and throughput for this kind of applications has been discussed in Section 4.

Controlling a Robot

In this section we show how a robot can be controlled over a TCP connection. In particular, we present the code to implement a line following algorithm for the Middlesex Robotic Platform (MIRTO) [START_REF] Androutsopoulos | A Racketbased robot to teach first-year computer science[END_REF]. For the purposes of this example, we employ three infrared sensors mounted under the robot and we exploit the ability of controlling each wheel individually to the desired speed. The line to follow is a strip of black electric tape on a white table. When the infrared sensors are on the white surface they report a value close to 0, while when the sensors are perfectly on black they report values close to 1000. Any value in the 0-1000 range represent a partial overlap of the sensor with the black tape.

The robot is equipped with a bespoke PCB using an Atmel 328P chip, compatible with an Arduino Mini. The chip runs a version of ASIP including, in addition to the standard I/O service, services for infrared sensors and for wheel control. The Arduino code for this robot is available at https: //github.com/michaelmargolis/asip in the sketch called mirto.ino. The ASIP client for this service are available at https://github.com/fraimondi/java-asip in the class JMirtoRobot.

The idea of a proportional-integral-derivative controller (PID) is that an error can be computed from the reading of the infrared sensors. The greater the error, the farther away the robot from the line. We set a target speed and the correction of this speed, for each wheel, is proportional to three components:

• The current error (Proportional component)

• The rate of change of the error (the Derivative component)

• The sum of the errors so far (the Integral component). This is normally capture by the following formula:

C(t) = K p e(t) + K i t 0 e(τ)dτ + K d d dt e(t)
where C(t) is the correction at time t, e(t) is the error computed at time t and K p , K i , K d are the coefficients for the three components of the correction mentioned above.

Excerpts from the Java implementation for the PID algorithm are presented in Listing 2. The key points here are:

• Line 6 sets up a TCP connection to a bridge at IP address 192.168.0.1. This is the IP address of the Raspberry Pi running on the robot.

• The values of the infrared sensors are read at lines 10-12. The method getIR is provided by the class JMirtoRobotOverTCP that is available at https:// github.com/fraimondi/java-asip.

• The values of the infrared sensors are used at line 16 and 20-21 to compute, respectively, the current error and the correction to be applied to the motors.

• The speed of each wheel is updated at line 23 with the method setMotors, which is provided by JMirtoRobotOverTCP

Listing 2: Java ASIP implementation for a PID line following robot The Java code can be run on a client connected to the same network to which the robot is connected. A typical line following algorithm performs smoothly at a frequency of approximately 10 Hz, which can be easily achieved given the results presented in the previous section for throughput. A video of this example is available at this link: https://www.youtube. com/watch?v=KH_3766gNcM

Adding new services

We conclude this section by showing how ASIP can be extended to include new services that are not yet available in our implementation. Adding a new service typically involves building code that runs on the Arduino and client code. In this section we show how the distance service can be implemented. The first step is to implement the class AsipServiceClass reported in Figure 1. A possible implementation is reported in Listing 3.

Listing 3: C++ code for the distance service This code implements the class asipDistanceClass, extending asipServiceClass. As a result, the class inherits a number of methods required to communicate over a stream etc., and it only needs to implement the actual service to be delivered. Concretely, in Listing 3 this means defining a unique ID for the service (used in the constructor at line 4) and defining the commands that can be sent to the service in the method processRequestMsg, as exemplified at line 18 where the distance service implements a response to the command 'M' by calling method reportValues which, in turn (line 27) calls the private method getDistance. This private method (lines 31 to 47) is the method that implements the actual service and in the case of other services it may employ specific libraries for a service, such as for controlling wheels. By compiling this code and uploading it to the micro-controller it is now possible to send ASIP messages of the form D,M: these will be captured by the processRequestMsg method that, in turn, will generate a response of the form @D,e,1,{0:42} meaning that this is a message from a Distance service reporting a distance event; there is only one distance sensor attached and that its current reading is 42 cm. Additional sensors can be added without any modification of the code, see line 26 in Listing 3.

Typically, clients are extended to support the new services deployed on the micro-controller. As an example, Listing 4 shows excerpts from the Java client for the distance service described above. The full code is available in the file DistanceService.java at https://github.com/ fraimondi/java-asip. As in the case of the code running on the micro-controller, the Java class extends a superclass that provides most of the methods already. The new subclass only needs to implement the method to process responses, see line 15. This new class is then ready to be used in conjunction with ASIP applications. Notice how the developer only needs to implement the specific feature of a service and can re-use all the networking infrastructure.

Conclusion

In this paper we have introduced the Arduino Service Interface Programming model (ASIP). This is an infrastructure that comprises:

• a software architecture to manage micro-controllers as clients of higher-level languages;

• a language for messages exchanged over a range of communication channels between micro-controllers and clients;

• a communication and network architecture that can be based on direct serial (USB) links, TCP sockets, and MQTT publish/subscribe messaging.

We have provided a concrete implementation for Arduino micro-controllers and libraries for a range of programming languages. All our source code has been released as open source. We have performed an extensive assessment of the performance of the ASIP infrastructure using Java and Python clients both direct serial connections and over networked connections. The results obtained are very encouraging and show that latency and throughput are adequate for controlling precise navigation of a robot over a wireless network. Besides performance consideration, we have provided a qualitative evaluation showing how applications can be developed by exploiting the existing libraries using only a few lines of code and delegating the communication and coordination issues among microcontrollers to the underlying ASIP infrastructure.

For the future, we are currently working on the implementation of ASIP bridges based on the ESP8266 chip. While this paper has focussed on the practical implementation for Arduino micro-controllers, we remark that the service model described is independent from the actual micro-controller hardware. The only requirement is that the micro-controller should support a communication stream and support execution loops.

From a system and software engineering point of view we consider this work a first step in the direction of model-based development for complex applications involving multiple microcontrollers. Our aim is to enable automatic code generation from our service model, working in the direction of verification and certification activities for complex domains [START_REF]RTCA, DO-178C, software considerations in airborne systems and equipment certification[END_REF].

Figure 1 :

 1 Figure 1: ASIP simplified class diagram

Figure 3 :

 3 Figure 3: An application scenario exploiting the service discovery functionality.

Figure 4 :

 4 Figure 4: Serial testing set-up.

Figure 5 :

 5 Figure 5: Oscilloscope output.

Figure 6 :

 6 Figure 6: Throughput for Java (a) and Python (b) clients with various testbed network configurations.

Figure 7 :

 7 Figure 7: The hardware set-ups used for latency testing: (a) serial connection and (b) TCP and MQTT connection.

Figure 8 :Figure 9 : 15 #

 8915 Figure 8: Latency for Java (a) and Python (b) clients with various testbed network configurations.

7 // Additional code to set up pins goes here 8 / 18 /

 7818 is a method to compute the current error as 15 // described above. 16 curError = computeError(leftIR,middleIR,rightIR ); 17 / computeCorrectionLeft and Right computes the correct speed for 19 // each motor using the coefficient described above 20 speedLeft = computeCorrectionLeft(curError,Kp,Ki,Kd); 21 speedRight = computeCorrectionRight(curError,Kp,Ki,Kd); 22 23 robot.setMotors(speedLeft,speedRight); 24 } 25 } 26 }

Listing 4 :

 4 Java client for the distance service (excerpts) 1 public class DistanceService implements AsipService { 2 3 private char serviceID = 'D'; 4 // This is the last measured distance (-1 if not initialised ) 5 private int lastDistance; 6 // [...] 7 8 public void requestDistance() { 9 this.asip.getAsipWriter (). write (this.serviceID+","+'M'+"\n"); 10 } 11 // [...] 12 13 public void processResponse(String message) { 14 if (message.charAt(3) == DISTANCE EVENT) { 15 String distances = message.substring(message.indexOf("{")+1, 16 message.indexOf("}")); 17 this.lastDistance = Integer .parseInt(distances. split ( " , " )[ this.distanceID ]);

See https://github.com/michaelmargolis/mdx_prototypes/ tree/51145bd1347625df9bc4e79b7eb11726f243a401/ASIP/Lua.