Abiel -Aguilar-González

Miguel Arias-Estrada

François Berry

Dense Feature Matching Core for FPGA-based Smart Cameras

Keywords: Feature matching, Feature tracking, Smart camera; FPGA

Smart cameras are image/video acquisition devices that integrate image processing algorithms close to the image sensor, so they can deliver high-level information to a host computer or high-level decision process. In this context, a central issue is the implementation of complex and computationally intensive computer vision algorithms inside the camera fabric. For low-level processing, FPGA devices are excellent candidates because they support data parallelism with high data throughput. One computer vision algorithm highly promising for FPGA-based smart cameras is feature matching. Unfortunately, most previous feature matching formulations have inefficient FPGA implementations or deliver relatively poor information about the observed scene. In this work, we introduce a new feature-matching algorithm that aims for dense feature matching and at the same time straightforward FPGA implementation. We propose a new mathematical formulation that addressed the feature matching task as a feature tracking problem. We demonstrate that our algorithmic formulation delivers robust feature matching with low mathematical complexity and obtains accuracy superior to previous algorithmic formulations. An FPGA architecture is lay down and, hardware acceleration strategies are discussed. Finally, we applied our feature matching algorithm in a monocular-SLAM system. We show that our algorithmic formulation provides promising results under real world applications.

INTRODUCTION

Smart cameras are image/video acquisition devices with selfcontained image processing algorithms that simplify the formulation of a particular application. i.e., algorithms for video surveillance could detect and track pedestrians, but for a robotic application, algorithms could be edge and feature detection. In recent years, progress in microprocessor power and FPGA technology allowed the creation of compact smart cameras with low cost and, this increased the smart camera applications performance, so in current embedded vision applications, smart cameras represent a ACM ISBN .

DOI:

promising on-board solution under different application domains: motion detection, object detection/tracking, inspection and surveillance, human behavior recognition [START_REF] Fularz | The architecture of an embedded smart camera for intelligent inspection and surveillance[END_REF][START_REF] Haritaoglu | Real-time surveillance of people and their activilies[END_REF], etc. In any case, flexibility of application domain relies on the large variety of image processing algorithms that can be implemented inside the camera. One task highly used by computer vision applications is feature matching between different camera views. In computer vision, feature matching aims for pixel/point correspondences across different viewpoints from the same scene/object (Fig. 1) and it is the basis of several computer vision applications such as, augmented reality, object recognition [START_REF] Anderson | Real-time feature tracking on an embedded vision sensor for small vision-guided unmanned vehicles[END_REF], etc. The most common formulation consists in detecting a set of feature points and associate each point with a visual descriptor. Once feature points and their descriptors have been extracted from at least two images, it is possible to match features across the images. In this context, feature-tracking seems to be a simple point matching problem, nevertheless, in practice it is a complex task since matching performance depends on the feature extractor/visual descriptor properties. Specific detectors and descriptors, appropriate for the input images content have to be used in specific applications. i.e., if input images are a microscopic view of bacteria or cells, a blob detector should be used. On the other hand, if the images are a city view, a corner detector is more suitable to find building structures. In addition, if input images have high degradation (rotation, orientation or scale changes), complex and intensive visual descriptors considering the image degradation are required in order to guarantee stability.

RELATED WORK

In current computer vision systems, several applications use feature matching as keystone of their mathematical formulations, so a smart camera that contains feature matching in their self-contained algorithms is highly desirable. In recent work, there are several approaches that aim for an embedded feature matching core; several FPGA architectures have been developed and several solutions have been proposed. [START_REF] Wang | A fpga-based architecture for real-time image matching[END_REF][START_REF] Sinha | Gpu-based video feature tracking and matching[END_REF]. In [START_REF] Fularz | A high-performance fpga-based image feature detector and matcher based on the fast and brief algorithms[END_REF] an embedded system architecture for feature detection and matching was presented. The proposed FPGA architecture implements the FAST [START_REF] Rosten | Machine learning for high-speed corner detection[END_REF] (Features from Accelerated Segment Test) feature detector and the BRIEF [START_REF] Calonder | Brief: Binary robust independent elementary features[END_REF] (Binary Robust Independent Elementary Features) feature descriptor in a customizable FPGA block. The developed blocks were designed to use hardware interfaces based on the AMBA AXI4 interface protocol and were connected using a DMA (Direct Memory Access) architecture. The proposed architecture computes feature matching over two consecutive HD frames coming from an external memory at 48 frames per second. In [START_REF] Yao | An architecture of optimised sift feature detection for an fpga implementation of an image matcher[END_REF] a FPGA architecture of SIFT (Scale Invariant Feature Transform) visual descriptor associated to an image matching algorithm was presented. For an efficient FPGA-SIFT image matching implementation (in terms of speed and hardware resources usage), the original SIFT algorithm was optimized as follows: 1) Upsampling operations were replaced with downsampling, in order to avoid interpolation operations. 2) Only four scales with two octaves were used. 3) Dimension of the visual descriptor was reduced to 72 instead of 128 in the original SIFT formulation. This implementation is able to detect and match features in 640×480 image resolution at 33 frames per second. More recently, Weberruss [START_REF] Weberruss | Orb feature extraction and matching in hardware[END_REF] have proposed a FPGA architecture for ORB [START_REF] Rublee | Orb: An efficient alternative to sift or surf[END_REF] (Oriented FAST) descriptor associated to a feature matching algorithm. An "harris corner" detection [START_REF] Harris | A combined corner and edge detector[END_REF] was the feature extractor and ORB visual descriptors were computed at each "corner". Finally, the previous features (stored in a 2D Shift Register) and the current features were matched using the hamming distances as discrimination metric. In 2017, Vourvoulakis [START_REF] Vourvoulakis | Fpga accelerator for real-time sift matching with ransac support[END_REF] presented an FPGA-SIFT architecture for feature matching. In order to achieve high hardware parallelism, procedures of SIFT detection and description were reformulated. At every clock cycle, the current pixel in the pipeline is tested and if it is a SIFT feature, its descriptor is extracted. Furthermore, every detected feature in the current frame is matched with one among the stored features of the previous frame, using a moving window, without breaking the "pixel pipeline". False matches are rejected using RANSAC (Random Sample Consensus) algorithm. The architecture was implemented on Cyclone IV. Maximum supported clock frequency was set as 25 MHz and the architecture was capable to process 81 frames per second, considering 640×480 image resolution.

In most of cases, previous FPGA-based feature matching formulations, [START_REF] Wang | A fpga-based architecture for real-time image matching[END_REF][START_REF] Sinha | Gpu-based video feature tracking and matching[END_REF][START_REF] Fularz | A high-performance fpga-based image feature detector and matcher based on the fast and brief algorithms[END_REF][START_REF] Rosten | Machine learning for high-speed corner detection[END_REF][START_REF] Calonder | Brief: Binary robust independent elementary features[END_REF][START_REF] Yao | An architecture of optimised sift feature detection for an fpga implementation of an image matcher[END_REF][START_REF] Weberruss | Orb feature extraction and matching in hardware[END_REF][START_REF] Rublee | Orb: An efficient alternative to sift or surf[END_REF][START_REF] Vourvoulakis | Fpga accelerator for real-time sift matching with ransac support[END_REF] provide relatively good performance under real world scenarios. Unfortunately, in several applications and in particular smart cameras applications, these algorithms are not compliant due to their relatively high hardware requirements and their algorithmic formulation. We can mention three important limitations affecting the current feature matching algorithms:

1. Low performance for embedded applications: nowadays computers can process several feature matching algorithms in real-time. Unfortunately, in embedded applications such as, smart cameras, mobile applications, autonomous robotics or compact smart vision systems, the use of computers is difficult due to their high power consumption and size. The use of FPGA technology is an alternative, but there are hard challenges due to previous visual descriptors (SIFT, BIERF, ORB) and matching techniques were designed for software implementation, and often, there are several iterative operations that could not be parallelized. As result, most previous FPGA architectures have high hardware requirements and relatively low processing rate.

2. Sparse matching: in order to maintaining high discrimination between descriptors only features with high thresholding response are matching (since it is assumed that these features have to be associated with high responsive visual descriptor that has low probability to be similar in other features). In practice, this assumption ensures consistency in the matching process, however, there is an important limitation because only a few image points are matched, then, scene/object information are available only at certain sparse points of the image, as shown in Fig. 2.

3. Outliers: In certain cases, the image ambiguities around features (color/texture repeatability, occlusion, etc.) generate similar visual descriptors for two or more different features, in such scenario the matching techniques deliver wrong results that can affect the global performance of several computer vision applications (camera calibration, structure from motion, visual odometry, etc.), see Fig. 2. To solve this problem, statistically robust methods like RANSAC have to be applied as outlier filter. In this case, statistical methods remove wrong matches, but they increment the matching cost.

THE PROPOSED ALGORITHM

Most previous FPGA-based feature matching formulations provide relatively good performance under real world scenarios, however, there are several important limitations (low performance for embedded applications, sparse matching and outliers) that affect performance. In this work, we assume that a more efficient solution consists in addressing the feature matching task as a feature tracking problem. In this way, we consider that a feature tracking approach will provide more data parallelism than previous formulations based on SIFT/ORB visual descriptors. In current state of the art, there are some FPGA architectures for feature tracking [START_REF] Tomasi | Fpga-dsp co-processing for feature tracking in smart video sensors[END_REF][START_REF] Tippetts | Fpga implementation of a feature detection and tracking algorithm for real-time applications[END_REF]. Unfortunately, most previous work addressed the problem via the KLT (Kanade-Lucas-Tomasi) tracking algorithm, that is highly exhaustive and has high hardware requirements for the case of FPGA implementation.

3.1 Feature matching and Feature tracking.

The basis of feature matching is to extract visual features from two or more different viewpoints from the same scene/object and then, match these visual features by comparing visual descriptors computed around each feature, as shown in Fig. 3. On the other hand, feature tracking consists in extracting visual features from an image and then, try to find the same features back in a similar image (commonly the next frame from a video sequence), as illustrated in Fig. 4. Since there are several image ambiguities around features (color/texture repeatability, occlusion, etc.), complex and intensive pixel similarity metrics are required in order to guarantee accurate tracking.

In our case, we propose a new feature tracking formulation that can be extended for feature matching. Our contributions are twofold: first, we propose a tracking/matching framework that improves most of the current limitations of the previous feature matching algorithms and that is fully compliant with FPGA architectures. Second, we lay down an FPGA architecture, suitable for smart cameras implementation. In Fig. 6 an overview of our algorithmic formulation is shown. In general, our algorithm first, stores two consecutive frames from an input video sequence. Visual features are extracted from the both frames. In addition, curl of the intensity gradient is computed over both frames. In this case, curl of the intensity gradient aims to remove image ambiguities around features (color/texture repeatability, pixel similarity, etc.). Then, a fully parallelized feature tracking algorithm computes preliminary matches between features in first frame and pixel points in second frame. For that, curls of the intensity gradient are considered as input since it is assumed that it guarantees consistent tracking around features. Finally, considering feature points in second frame, a feature matching steep refines the tracking result by comparing tracked points in second frame with visual feature coordinates computed at the same frame.

Image storage

Considering that in most cases the image sensor provides data as a stream, a storage is required to get two consecutive frames at the same t time. More information/details about the storage architecture will be presented in Section 4.1. For mathematical formulation, first frame (frame at t time) is noted I1(x, y) while the second frame (frame at t + 1 time) is I2(x, y).

Feature extractor

In this work, the Shi-Tomasi feature extractor is used. it provides a good trade-off between accuracy/robustness, speed processing and hardware requirements. This extractor is based on spatial gradients such as:

A(x, y) = ∂I ∂x • ∂I ∂x B(x, y) = ∂I ∂y • ∂I ∂y C(x, y) = ∂I ∂x • ∂I ∂y
A gaussian filtering is applied over the A, B, C matrices in order to reduce noise and to remove fine-scale structures that affect the performance of the corner response. Smoothed matrices are defined by A , B , C . Original Shi-Tomasi corner metric Eq. 1, provides a high response value for corners and low response otherwise, as illustrated in Fig. 5b.

D(x, y) = (A (x, y)+B (x, y))-(A (x, y) -B (x, y)) 2 + 4C (x, y) 2 (1)
In order to determine if a pixel P is a corner or not, maximum value of the corner response is retained. However, many pixels around each corner are detected in spite of filtering with a threshold α. These pixels are false feature candidates and are difficult to match/track. A way to remove these false feature candidates consists in applying a non-maxima suppression step. An appropriate FPGA-based non-maxima suppression step could be defined as follows: Considering D(x, y) as the corner response image and Ω(x, y) as fixed neighborhood size of 3×3 around D(x, y), a "good features" is computed as :

β(x, y) = max   Ω(x, y) *   1 1 1 1 0 1 1 1 1    
Finally, a thresholding (α) have to be applied over D(x, y) in order to select the "good features/corners", see Eq. 2.

corners(x, y) = 1 if β(x, y) > α 0 if otherwise (2)

Improvement feature discrimination

Previous work [START_REF] Suominen | Transform-based methods for stereo matching and dense depth estimation[END_REF] demonstrated that simple pixel similarity metrics such as SAD (Sum of Absolute Differences), Hamming distances or NCC (Normalized Cross-Correlation) deliver poor results over real world scenarios. This is due to several image ambiguities around features. i.e., due to color/texture repetition, different features could have low difference between similarity metrics (close to zero). To solve these problems, previous feature tracking formulations [START_REF] Tomasi | Fpga-dsp co-processing for feature tracking in smart video sensors[END_REF][START_REF] Tippetts | Fpga implementation of a feature detection and tracking algorithm for real-time applications[END_REF] used more complex approaches such as Eigenvalues of the Gradient matrix or Jacobian matrix as similarity metric. Unfortunately, they require high hardware resources for FPGA implementation.

In this work, we propose to improve the feature discrimination by using the curl of the intensity gradient dI(x,y) dx in each point. Let curl as a vector operator that describes the infinitesimal rotation, then, at every point the curl of that point is represented by a vector where attributes (length and direction) characterize the rotation at that point. In our case, we use only the norm of Curl I(x, y) given by:

CurlI(x, y) = ∇ × dI(x, y) dx ( 3
)
where ∇ is the Del operator.

CurlI(x, y) = ∂ ∂y ∂I ∂x - ∂ ∂x ∂I ∂y 2 = | ∂ ∂y ∂I ∂x - ∂ ∂x ∂I ∂y | (4)

Feature tracking

Tracking process assumes that features displacements between frames is such as it exists an overlap on two successive "search regions". A search region is defined as a patch around a feature to track. This process is illustrated in Fig. 7. Considering that between I1 and I2, the illumination is stable, a similarity-based metric provides a good accuracy. This similarity is calculated by a SAD (Sum of Absolute Difference). This process is defined in Eq. 5, where r is the search region size, CurlI1(x, y), CurlI2(x, y) are the norm curl images on two consecutive frames from a video sequence (I1, I2 respectively), x, y are the spatial coordinates of features extracted in I1 and, a, b are the spatial coordinates for all points within the search region constructed in I2. Thus, considering a video sequence, first, the feature extractor (Section 3.3) obtains g feature points from I1(x, y), defined as corners1(x, y). Let x1(g), y1(g) as the x, y are the spatial position for all extracted features in I1. Then, tracking of extracted features is performed by applying Eq. 6 and 7; where x2(h), y2(h) are the tracked positions in I2.

Feature matching

Our feature tracking algorithm do not consider the occlusion problem i.e., it tracks any feature extracted from I1, then, some outliers could be present because some features extracted in reference image I1 could have occlusion at I2. To solve this problem, a matching technique is used as outlier filtering. Considering x2(h), y2(h) as reference spatial coordinates for the feature matching (Eq. 6 and 7) and given corners2(x, y) the feature extraction from I2 (Eq. 2), a pixel tracking is correct only if there is one unique feature in I2 that is located in the region that surrounds the previously computed tracking localization (see Eq. 8 -10).

f ilter h (x, y) = u=1 u=-1 v=1 v=-1 corners2(x + u, y + v) (8) x f (h) = x2(h) if f ilter h (x, y) == 1 0 otherwise (9) y f (h) = y2(h) if f ilter h (x, y) == 1 0 otherwise (10)

FPGA ARCHITECTURE

In Fig. 8, an overview of the FPGA architecture for the featurematching algorithm is presented. The architecture is centered on an FPGA implementation where all recursive/parallelizable algorithms are accelerated in the FPGA fabric. In general, the basis of the proposed architecture is the frame storage unit. In this block, frames captured by the imager are feed to/from an external SDRAM memory using a DMA. Two consecutive frames are read out into the buffers used to hold local sections of the frames that are being tracked and allow for local parallel access that facilitates parallel processing.

Frame storage unit

Images from the image sensor are stored in an external SDRAM that holds at least 2 frames from the sequence, and later the SDRAM is read by the FPGA to cache parts of the frames into buffers. The frame storage unit is responsible for data transfers in segments of the image (usually several rows of pixels) to/from the SDRAM. The core of the FPGA architecture are the buffers attached to the local processors that can hold temporarily as cache, for image sections from two frames, and that can deliver parallel data to the processors. For the SDRAM controller, both Xilinx and Altera have IPs for this proposes. For the buffers, we use a circular buffer schema in which input data from the previous N rows can be stored using memory buffers till the moment when a n×n neighborhood is scanned along subsequent rows. This approach has high hardware reutilization and high flexibility for computer vision applications. For more details, see [START_REF] Aguilar-González | An fpga 2d-convolution unit based on the caph language[END_REF].

Feature extraction unit

Fig. 9a gives an overview of the feature extractor unit. First, the architecture computes the vertical/horizontal gradients, ∂I 1 ∂x , ∂I 1 ∂y , respectively. Then it computes the A(x, y), B(x, y), C(x, y) variables. After that, a buffer delivers parallel data for the Gaussian filtering. Then, the reconfigurable convolution units (see [START_REF] Aguilar-González | An fpga 2d-convolution unit based on the caph language[END_REF]) compute the smoothing operation. Finally, the FPGA architecture computes the corner response metric and the non-maxima suppression step. In order to simplify the square root operation implementation in the feature extraction step, we adapted the architecture developed by Yamin Li and Wanming Chu [START_REF] Li | A new non-restoring square root algorithm and its vlsi implementations[END_REF]. This architecture uses a shift register mechanism and compares the more significant/less significant bits to compute square root from Eq. 1 with relatively high accuracy and low hardware resources.

Feature discrimination unit

Feature tracking unit

For the feature tracking unit, we consider that the tracking problem can be seen as a generalization of the dense stereo matching problem. i.e., stereo matching algorithms track (searching on the horizontal axis around points in the reference image), all points/pixels within a stereo pair. Feature tracking aims to track features points between two consecutive frames from a video sequence (searching around spatial coordinates of the features in the reference frame). Then, it is possible to adapt previous stereo matching FPGA architectures to fulfill with our application domain. In this work, we adapted the FPGA architecture presented in [START_REF] Pérez-Patricio | An fpga stereo matching unit based on fuzzy logic[END_REF], which has low hardware requirements and high parallelism. In Fig. 10, the developed architecture is shown. Considering that feature points for I1 are known, these are obtained by the feature extraction unit. Then, the search region modules (see Fig. 7), construct n search regions, where search regions are constructed via logical pointers under the input buffer for I2. For each feature point in the reference image (I1), search region centers correspond to all patches within the search region on frame I2. Once the search regions are constructed, similarity SAD modules compute the correlation response (applying the sum of absolute differences as similarity metric response). i.e., it compares all search regions with the reference region. Finally, a multiplexer tree can determine the a, b indices that minimize the correlation function, and therefore, the tentative position in I2 of the feature points extracted in the reference image (I1).

Feature matching unit

The feature matching unit consists in a unique module that compares the feature tracking results with visual features extracted in I2. Then, the feature matching x f {h}, y f {h} (final result) is the result obtained after comparisons between tracking positions x2{h}, y2{h} and visual features corners2 in frame I2.

RESULTS

In order to validate our mathematical formulation, we implemented our feature-matching algorithm in a MatLab R2016b code that captures video sequences from a web camera. Then, feature points (corners) are tracked along the video sequence. In all experiments, feature points are obtained by applying the algorithm presented in Section 3.3. Video sequences of 1920×1080 pixel resolution and 800 frames were used. In Fig. 11, results by applying our algorithm over an outdoor scenario are shown.

Performance for dataset scenes

For performance comparisons we compared our feature matching algorithm with previous feature matching/tracking algorithms. For feature tracking, we applied the KLT, KL and Mean-shift algorithms. For feature matching we used three classic feature matching frameworks, based on ORB, SIFT and SUFR visual descriptors, respectively. We we evaluate the algorithms with several video sequences, all videos were obtained from [START_REF] Sturm | A benchmark for the evaluation of rgb-d slam systems[END_REF]. Two performance tests were conducted. In Table 1, accuracy comparisons are shown.

To validate the accuracy in numerical form, RMS error is computed as: = x 2 + y 2 ; where x is the error in x axis, defined as the average difference between the ground truth x position in each frame of the video sequence and the position in same frame computed by the testing algorithm (visual features ground truth were computed using the camera localization ground truth provided by the dataset). y is the error in y axis, it is computed similar to x. In all cases, our algorithm outperforms the KL and the MS tracking algorithms, and outperforms feature matching algorithms based on visual descriptors like ORB, SIFT and SURF. This is because the KL algorithm does not consider the occlusion problem. In addition, the KL algorithm uses simple similarity metrics, that introduces erroneous measurements under image ambiguities. On the other hand, MS algorithm was formulated for object-tracking in dynamic scenes, therefore, performance under rigid scenes is low. For algorithms that use robust visual descriptors (ORB, SIFT, SURF), occlusions, ambiguities and perspective changes between frames introduce outliers, therefore, accuracy is lower than tracking approaches. Although KLT algorithm outperforms our algorithmic formulation, KLT is highly exhaustive, processing speed is low, and implementation in real-time/embedded applications is highly limited.

For density comparisons: traditional feature matching algorithms extract and match visual features via visual descriptor comparisons. Unfortunately, in all cases, the maximal number of features that can be matched varies between 0.5% and 1.0% of all pixels in the image, depending on the selected descriptor and its particular configuration. In practice, computer vision systems work with configurations that allow extracting near 1% of the pixels from an image. This is illustrated in Table 2, where feature matching based on visual descriptors reach less than 200 matches per frame. This limits the real-world applications performance since less than 1% of the image points are available, thus, the visual environmental understanding, high-level descriptors application and objects/structures recognition in the scene could have low stability under real-world scenarios. Even the most current and popular feature matching approaches, for example such based on the ORB descriptor, are limited to sparse matching. On the other hand, tracking algorithms such as KLT and KL deliver high density compared with matching approaches, as shown in Table 2. Both, KL and KLT can track near 2% of all points in the scene (×44 more than the matching algorithms). In the case of our feature matching algorithm, it can track/match near 5% of the points within the scene (×2 more than previous feature tracking approaches and ×85 more than previous feature matching approaches). This was achieved by applying low threshold values for the feature extraction process and, due to vectors transformations whose formulation guarantee consistence between low responsive features. For KL and KLT these low thresholds generate outliers that affect the tracking accuracy. Since the MS algorithm was formulated for object-tracking, density is low since this algorithm only track shape features (that are a few of pixels compared with all the points in the analyzed scenes).

Performance for real world applications

We implement our feature-matching algorithm in a monocular-SLAM system. We applied our algorithm to obtain point correspondences across the video sequence. In this case, point correspondences allow fundamental matrix estimation. Finally, using the fundamental matrix, is it possible to estimate a 3D reconstruction and camera pose along the video sequence. In this case our feature matching algorithm is capable to increase the point cloud density, as shown in Fig. 12. We consider that this could be highly useful under several computer vision applications that use feature matching in their mathematical formulations (SLAM, SfM, 3D reconstruction), since more information (×85 more than previous feature matching approaches and ×2 more than previous feature tracking formulations) are available. Thus, visual environmental understanding, high-level descriptors application and objects/structures recognition performance could be improved. For our FPGA architecture, we consider that our architectural formulation could be implemented within a smart camera fabric. In this scenario, our feature matching algorithm could be an important contribution for smart cameras, this because several computer vision applications uses point correspondences between frames/camera views as keystone of their mathematical formulation. For more details about the performance of the proposed algorithm see the material adjoint to this manuscript, all material can found from https://1drv.ms/f/s!AqkoNeNXKa6ijF10rKB5LFp30_CP.

CONCLUSIONS

In this work, we have introduced a new feature matching algorithm that deliver accurate/dense feature matching under indoor/ outdoor scenarios. We proposed a new mathematical formulation that addressed the feature matching task as a feature tracking problem, and we have used the curl of the intensity gradient as feature discrimination technique. An FPGA architecture was lay down and, hardware acceleration strategies were discussed. Since several computer vision applications use feature matching a keystone of their mathematical formulations, we consider that feature matching within a smart camera fabric could be promising under current computer vision applications. We have applied our feature matching algorithm in a monocular-SLAM system. We have shown that our algorithmic formulation improves the performance under SLAM applications. As work in progress we are implementing our feature matching algorithm inside the DREAMCAM [START_REF] Birem | Dreamcam: A modular fpga-based smart camera architecture[END_REF], a robust/flexible smart camera.

Figure 1 :

 1 Figure 1: The feature matching problem: visual features (circles) have to be matched (lines) across different viewpoints from the same scene/object (squares).

Figure 2 :

 2 Figure 2: Feature matching algorithms limitations: most previous formulations work with few image points. Therefore, scene information is limited to a certain sparse points in the image. On the other hand, most previous work deliver outliers that effect performance in real world applications. (Figure modified from [25])

Figure 3 :

 3 Figure 3: The feature matching problem: for two or more different viewpoints visual features and visual descriptors around each feature are computed. Then, feature matching is computed based on visual descriptors comparison. Since some features could appear only at one unique view, high discriminant visual descriptors are desirable in order to avoid outliers.

Figure 4 :

 4 Figure 4: The feature tracking problem: considering two consecutive frames from a video sequence, visual features are extracted within the first frame. Then, it is tried to find the same features back in the next frame.Since there are several image ambiguities around features (color/texture repeatability, occlusion, etc.), complex and intensive pixel similarity metrics are required in order to guarantee accurate tracking.

Figure 5 :

 5 Figure 5: The Shi-Tomasi feature extractor: (a) Input image. (b) Corner metric response, Eq. 1. (c) Corner response after our non-maxima suppression step, β(x, y). (d) Output image considering α = 0.08, Eq. 2

Figure 6 :

 6 Figure 6: Block diagram of the proposed algorithm.

  + u, y + v)| -|CurlI2 = (x + u + a, y + v + b)| (5) x2(h) = h=g h=1 x1(h) + minaSAD(a, b) ) + min b SAD(a, b)

Figure 7 :

 7 Figure 7: The proposed feature-tracking algorithm formulation. For each feature point, n overlapped regions are constructed in I 2 , n region centers are all points within the search region created in I 1 . n region center that minimizes SAD is the tracked position of the feature point (x, y) in I 2 .

Fig. 9b ,

 9b Fig. 9b, an overview of the feature discrimination unit is shown. It resuses the gradient computation carried out in the feature extraction unit. Then, curl of the intensity gradient is computed as illustrated in Section 3.4. Two logical processes compute the curl of the intensity gradient for I1 and I2 in parallel.

Figure 9 :

 9 Figure 9: (a) FPGA architecture for the feature extractor unit. (b) FPGA architecture for the feature discrimination unit.

Figure 10 :

 10 Figure 10: FPGA architecture for the feature tracking unit

Figure 8 :

 8 Figure 8: FPGA architecture for dense/robust feature matching

Figure 11 :

 11 Figure 11: Feature matching under outdoor scenarios. Our mathematical formulation reach: accurate matching (without outliers) and dense matching (more than 14000 pixels are matched).

Figure 12 :

 12 Figure 12: The proposed algorithm applied in a monocular-SLAM system. (a) Feature matching via the BIREF visual descriptor. (b) Feature matching via the proposed algorithm. For our algorithm, 3D density is increased, then, visual environmental understanding, high-level descriptors application and objects/structures recognition performance can be highly improved.

Table 1 :

 1 The proposed algorithm compared with previous feature matching/tracking algorithms (accuracy). Error is measured in pixels

	Dataset	SIFT[12]	SURF[3]	ORB[25]	KLT[21]	KL[13]	MS[6]	Proposed
	fr1/room	67.22	79.38	76.24	0.21	4.81	9.62	1.87
	fr2/desk	69.83	81.12	73.63	0.45	4.9	9.81	1.55
	fr1/plant	59.29	77.74	75.24	0.39	4.12	8.25	1.7
	fr1/teddy	75.38	83.53	76.73	0.47	4.91	9.82	1.71

Table 2 :

 2 The proposed algorithm compared with previous feature matching/tracking algorithms (density). Density is measures as the feature matches number per frame

	Dataset	SIFT[12]	SURF[3]	ORB[25]	KLT[21]	KL[13]	MS[6]	Proposed
	fr1/room	167	174	79	7469	7546	85	14286
	fr2/desk	183	188	77	7942	7252	77	14598
	fr1/plant	124	158	78	6264	6576	74	13547
	fr1/teddy	172	183	75	7722	7112	92	14968

ACKNOWLEDGMENTS

This work has been sponsored by the French government research program "Investissements d'avenir" through the IMobS3 Laboratory of Excellence (ANR-10-LABX-16-01), by the European Union through the program Regional competitiveness and employment 2007-2013 (ERDF Auvergne region), and by the Auvergne region. This work has been sponsored by the National Council for Science and Technology (CONACyT), Mexico, through the scholarship No. 567804.


Abiel -Aguilar-González

Miguel Arias-Estrada

François Berry

PhD Forum: Camera Pose Estimation Suitable for Smart Cameras

Keywords: Camera pose, embedded systems, FPGA

Camera pose estimation across video sequences is an important issue under several computer vision applications. In previous work, the most popular approach consists on optimization techniques applied over 2D/3D point correspondences for two consecutive frames from a video sequence. Unfortunately, these optimization techniques are iterative and depend on nonlinear optimizations applied over some geometric constraint. For real-time embedded applications, another approach, more efficient in terms of computational size and cost, could be a linear or closed-form solution for the camera pose estimation problem. In this work, we introduce a new approach for camera pose estimation, this approach uses 2D visual features displacements as linear/dependent parameters for the camera pose estimation so, camera pose can be estimated without iterative behavior and without geometric constraints. As result, the proposed algorithm could be implemented inside a small FPGA device, suitable for smart cameras. Preliminary results are encourageous and show the viability of the proposed approach.

INTRODUCTION

In the last few years, camera pose estimation across unknown video sequences appears repeatedly under several computer vision contexts: visual servoing [START_REF] Chaumette | Visual servoing[END_REF], Simultaneous Localization and Mapping (SLAM) [START_REF] Mur-Artal | Orb-slam: a versatile and accurate monocular slam system[END_REF], augmented reality [START_REF] Hong | A 27 mw reconfigurable marker-less logarithmic camera pose estimation engine for mobile augmented reality processor[END_REF], etc. In previous work, primary interest was for an accurate/generalized solution for the camera pose problem [START_REF] Hartley | In defense of the eight-point algorithm[END_REF][START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF]. Unfortunately, these solutions have iterative behavior and requires relatively high computational resources. As result, several SLAM algorithms or augmented reality systems have limitations for embedded applications and, even with the use of relatively powerful PCs, camera pose often is limited between 15-25 estimations per second.

ACM ISBN .

DOI:

In this work, we believe that a smart camera that delivers camera pose at video cadence could be an important contribution for current embedded computer vision applications. In general, several applications such as robotics, SLAM or augmented reality could reach onboard camera pose processing. Furthermore, given the camera pose algorithm would be inside the camera fabric and close to the image sensor, higher processing speed and lower size/cost could be achieved (compared with previous work).

CAMERA POSE ESTIMATION SUITABLE FOR SMART CAMERAS

In smart camera context, one central issue is the implementation of complex/intensive computer vision algorithms inside the camera fabric. For processing purposes, FPGA devices are excellent candidates since they support data parallelism with low power consumption. Furthermore, FPGA devices are smaller and cheaper compared with other devices such as GPU processors or Intel processors. Under this premise, it is possible to assume that the more promising solution for the camera pose estimation is for an FPGA architecture. However, there are several challenges because previous background addressed the camera pose estimation problem via optimization techniques (these are difficult to be implemented inside FPGA fabric). In previous work, some approaches have studied the viability of solutions with small iterative number [START_REF] Shi | Estimation of camera pose using 2d to 3d corner correspondence[END_REF][START_REF] Romano | 3d pose estimation using convolutional neural networks[END_REF][START_REF] Nakajima | Robust camera pose estimation by viewpoint classification using deep learning[END_REF]. Nevertheless, in all cases, mathematical formulation limits its FPGA implementation.

CAMERA POSE ESTIMATION BASED ON PARALLEL CLASSIFIERS

As early formulation, we consider an autonomous vehicle scenario in which all possible camera movements are linear dependent of the x, y pixel displacements whiting the scene. i.e., given the input image divided in four quadrants (as shown in Fig. 1) and, consider four different cases: turn left, turn right, forward and backward; for the turn left case: all pixels within all the quadrants must have right displacement under the horizontal axe and similar displacement for the vertical axe, see Fig. 1a. For the turn right case: all pixels for all the quadrants must have left displacement under the horizontal axe and similar displacement for the vertical axe, as shown in Fig. 1b. For the forward case: pixels displacement are to outside the image, see Fig. 1c. Finally, for the backward case: pixels displacement are to the image center, as illustrated in Fig. 1d.

The proposed approach

Given pi{x, y} spatial locations for i feature points (obtained via FAST, SIFT, Harris, etc.) from frame t of a video sequence, Q that represents the horizontal, vertical displacements for the pi feature points at frame t + 1 is computed as shown in Eq. 1; where n represents each one of the quadrants from the input image (see Fig. 1), g are the feature points number within the n quadrant and ki are the spatial locations of the pi feature points at frame t + 1, these can be obtained via feature tracking algorithms. Considering the Q parameter is linearly/dependent to the camera movement, j known camera displacements (obtained from datasets) can be correlated with its corresponding Qj parameters, see Eq. 2; where Cj{x, y, z, α, θ, β} is the camera movement with six degree of freedom. Finally, given each Qj parameter and its corresponding camera displacement (Cj) as a unique class for a camera movement classifier, and considering that each possible camera movement (taken at some known viewpoints from a known scene) is included in the classifier definition, any camera movement for an unknown viewpoint can be estimated as shown in Eq. 3 and4; where Q is the Q parameter for the pose being computed and C k is the camera pose of the class that minimizes the absolute difference between the Q parameter and the Qj parameters.

Q{xn, yn} = 1/g i=g i=1 (pi{x, y} -ki{x, y}) (1)
Qj{xn, yn} = Cj{x, y, z, α, θ, β}

k = arg min j (H), H(j) = |Qj -Q | (3) pose{x, y, z, α, θ, β} = C k (4) (2)

FPGA architecture

For the FPGA implementation, the proposed approach could be implemented as a multiplexer tree. In this case, definitions for the movement classifier can be saved into logical registers, then, given an input Q parameter for an unknown camera movement, the multiplexer tree computes the camera position by parallel comparisons between Q and the stored Qj parameters.

PRELIMINARY RESULTS

We implemented our algorithm in a MatLab R2016b code that uses the KITTI dataset [START_REF] Geiger | Vision meets robotics: The kitti dataset[END_REF] as input sequences. First, feature points (Harris corners) are tracked along the video sequence. Then, several Qj parameters and its corresponding (Cj) camera displacements are saved. Finally, unknown camera movements can be estimated by comparing the Q parameter of the input frame with previous stored Qj parameters and (Cj) camera displacements. In Fig. 2, results by applying our algorithm over two different KITTI sequences are shown. In both cases 400 random frames from the first video sequence were used in the classifier definition, then, camera pose for the remaining frames in the first sequence (4171 frames) and for all the frames for the second sequence were computed by the proposed algorithm.

CONCLUSIONS AND FUTURE WORK

In this work, we have introduced a new camera pose estimation approach in which pixel displacements are used as linear/dependent parameters for the camera pose estimation. Different to previous work, our approach can estimate camera poses without iterative behavior and without geometric constraints. As result, the proposed algorithm could be implemented inside a small FPGA device, suitable for smart cameras. As work in progress, we are generalizing our algorithmic approach and implementing it inside the Dream-Cam, [START_REF] Birem | Dreamcam: A modular fpga-based smart camera architecture[END_REF], a robust/flexible smart camera.

Figure 1 :

 1 Figure 1: Given an autonomous vehicle scenario. Four different cases: turn left, turn right, forward and backward have to fulfill with all possible movements from a single moving camera installed over the vehicle. In such scenario, pixel displacements inside the images (red arrows) have different directions for each case.

Figure 2 :

 2 Figure 2: Camera pose estimation for the first two video sequences of the KITTI dataset [3]. In both cases, the proposed algorithm achieves accurate results (similar with the ground truth).


Antonio Brogi

Andrea Canciani

Jacopo Soldani

Modelling the Dynamic Reconfiguration of Application Topologies, Faults Included

Fault-aware management protocols permit modelling the management of application components (including potential faults) and analysing the management behaviour of a multi-component application. The analysis is driven by the application topology, and it assumes manyto-1 dependencies among application components, i.e. each requirement of a component can be satisfied by exactly one other component.

In this paper we extend fault-aware management protocols to account for many-to-many dependencies among components, i.e. different application components can be used to satisfy a requirement of another component. The extensions also accounts for dynamic changes in the topology, hence enabling the analysis of the management behaviour of dynamically reconfigurable multi-component applications.

, which is composed by a JavaScript-based microservice acting as web-based frontend of the application, two alternative and interchangeable implementations of a backend microservice, and a microservice hosting a Mongo database. The frontend microservice exposes

Introduction

How to automatically manage composite applications is currently one of the major concerns in enterprise IT [START_REF] Binz | TOSCA: Portable Automated Deployment and Management of Cloud Applications[END_REF][START_REF] Leymann | Cloud computing[END_REF]. Composite applications typically integrate various heterogeneous components, like in microservice-based applications [START_REF] Fowler | Microservices. ThoughtWorks[END_REF], and the deployment, configuration, enactment, and termination of the components forming a composite application must be suitably coordinated, by taking into account all dependencies occurring among application components.

It is worth noting that, while coordinating the management of a composite application, we must "enable failure" [START_REF] Killalea | The hidden dividends of microservices[END_REF]. Namely, we must be aware that the components forming a composite application may fail, and we should be able to react to such failures by restoring the desired application configuration.

A convenient way to represent the structure of a composite application is a topology graph [START_REF] Binz | Formalizing the Cloud through Enterprise Topology Graphs[END_REF], whose nodes represent the application components, and whose arcs represent the dependencies occurring among such components. Each topology node can be associated with the requirements of a component, the capabilities it features, and the operations to manage it. Inter-node dependencies associate the requirements of a node with capabilities featured by other nodes.

In [START_REF] Brogi | Fault-aware application management protocols[END_REF] we showed how the management behaviour of topology nodes can be modelled by fault-aware management protocols, specified as finite state machines whose states and transitions are associated with conditions defining the consistency of a node's states and constraining the executability of its management operations. Such conditions are defined on the requirements of a node, and each requirement of a node has to be fulfilled by a capability of another node. Faultaware management protocols also permit modelling how a node behaves when a fault occurs (viz., when a node is assuming a requirement to be satisfied by a capability, and such capability stops being provided by the corresponding node). The management behaviour of a composite application can then be easily derived by composing the management protocols of its nodes according to the dependencies defined in its topology.

Fault-aware management protocols (as per their definition in [START_REF] Brogi | Fault-aware application management protocols[END_REF]) assume manyto-1 dependencies among components. Namely, while a capability can be used to satisfy multiple requirements, a requirement can be satisfied only by one capability. This is a quite strict assumption, which impedes modelling and analysing applications where a requirement of a node can be satisfied by different capabilities offered by different nodes (e.g., a microservice-based application where a microservice requires a certain API, and alternative implementations of such an API are offered by different microservices).

In this paper we present a proper extension of fault-aware management protocols that relaxes the above mentioned assumption, allowing application topologies to have many-to-many dependencies among components. More precisely, we not only allow a capability to be connected to multiple requirements (viz., the set of requirements it can satisfy), but also a requirement to be connected to multiple capabilities (viz., the set of capabilities that can be used to satisfy such requirement). Whenever a node needs one of its requirements, any capability connected to such requirement can be used to satisfy it, and faults are raised whenever a node stops providing a capability actually satisfying a requirement. The extension also permits indicating whether the actual binding of a requirement can be dynamically changed while executing a management operation or while handling a pending fault, hence allowing to dynamically reconfigure the topology of an application.

We then illustrate how the management behaviour of a composite application can be derived by composing the management protocols of its nodes according to the static dependencies defined in its topology. We also show how this permits automating various useful analyses, like determining whether a plan orchestrating the management of a composite application is "valid", which are its effects (e.g., which capabilities are available after executing it, or whether it can dynamically reconfigure an application), and finding management plans achieving specific goals (e.g., reaching a desired application configuration, or dynamically reconfiguring an application to recover it from a fault).

The rest of the paper is organised as follows. Sect. 2 illustrates a scenario motivating the need for extending fault-aware management protocols to account for many-to-many dependencies in application topologies. Such extension is then formalised in Sect. 3. Sect. 4 shows how to automatically compose management protocols to analyse and automate the management of a composite application in presence of faults. Finally, Sects. 5 and 6 discuss related work and draw some concluding remarks, respectively. a requirement endp, as it needs to know which is the endpoint where to invoke the RESTful api offered by the backend microservices. These in turn expose a requirement db, as they need to set up a persistent connection to the microservice hosting a Mongo database.

Suppose that we wish to orchestrate the deployment of the whole application with a dedicated management plan. Since the represented application topology does not include any management protocol, one may produce invalid management plans. For instance, while Fig. 2 illustrates three seemingly valid plans, only (a) is a valid plan. Plan (b) is not valid since the operation config of backend 1 must be executed before actually starting the node (to provide backend 1 with the necessary information to set up the connection with the Mongo database). Plan (c) is not valid either, since database must be running before backend 1 and backend 2 can start (as this also results in connecting them to the database).

Suppose now that all microservices have been deployed, started, and properly connected (e.g., by executing plan (a) in Fig. 2), with frontend being configured to invoke the api offered by backend 2 . What happens if the operation stop of backend 2 is executed? The microservice backend 2 is stopped, and this may generate a fault in frontend, as it becomes unable to serve its clients simply because the api that it remotely invokes is not offered anymore by backend 2 . A simple yet effective solution would be to dynamically reconfigure the microservice frontend to invoke the api offered by backend 1 . Even worse is the case when database is stopped, as this causes a fault in backend 1 and backend 2 , which become unable to serve their clients, and this in turn causes a fault also in frontend. Both the above mentioned cases fail because a microservice stops providing its capabilities while other microservices are relying on them to continue to work. In both cases we would like to recover our microservice-based application, by automatically determining a valid reconfiguration plan capable of restoring the desired application configuration.

In summary, while the validity of management plans can be manually verified, this is a time-consuming and error-prone process, especially in microservicebased applications [START_REF] Killalea | The hidden dividends of microservices[END_REF]. In order to enable the automated verification of the validity of plans, as well as the automated generation of valid plans reaching desired application configurations, we need an explicit representation of the management protocols of the nodes appearing in the topology of a composite application. Such management protocols have to take into account the possibility of faults to occur, and should permit reacting to them to recover the desired configuration of an application, e.g., by dynamically reconfiguring the inter-connections among the components of an application.

Most of the available languages for modelling composite applications permit describing the states, requirements, capabilities, and management operations of the nodes building the topology of a composite application (e.g., enterprise topology graphs [START_REF] Binz | Formalizing the Cloud through Enterprise Topology Graphs[END_REF], TOSCA [START_REF]OASIS: Topology and Orchestration Specification for Cloud Applications[END_REF]). Fault-aware management protocols [START_REF] Brogi | Fault-aware application management protocols[END_REF] permit specifying the management behaviour of the nodes composing an application, i.e. the behaviour of a node's management operations, their relations with states, requirements, and capabilities, and how a node reacts to the occurrence of a fault.

However, fault-aware management protocols assume many-to-1 dependencies among the nodes forming a topology (i.e., each requirement of a node is connected to exactly one capability of another node, while each capability of a node can be connected to multiple requirements of other nodes). We hereby present an extension of fault-aware management protocols that relaxes such assumption, by also allowing to specify whether the capability used to satisfy a requirement may be dynamically changed (by choosing another capability connected to it in the application topology).

Let N be a node modelling an application component, whose finite sets of its states, requirements, capabilities, and management operations are denoted by S N , R N , C N , and O N , respectively. Fault-aware management protocols permit modelling the management behaviour of N by describing (i) the order in which the management operations of N can be executed, (ii-iii) whether and how N depends on other nodes providing the capabilities that satisfy its requirements, and (iv) how N reacts when a fault occurs. More precisely:

(i) The order in which the operations of N can be executed is described by a transition relation τ N specifying whether an operation o ∈ O N can be executed in a state s ∈ S N , and which state is reached by executing o in s. (ii) The states and transitions of N can be associated with (possibly empty) sets of requirements to indicate that the capabilities satisfying them are assumed to be provided by the corresponding nodes.

-The requirements associated with a state s ∈ S N specify that the capabilities satisfying them must (continue to) be offered by the corresponding nodes in order for N to (continue to) work properly. -The requirements associated with a transition t ∈ τ N specify that the capabilities satisfying them must be provided by the corresponding nodes to enable the execution of t. (iii) Each state s ∈ S N is also associated with the (possibly empty) set of capabilities provided by N in s. (iv) N is affected by a fault whenever it is in a state assuming some requirement(s) to be satisfied, and some other node stops providing the capabilities satisfying such requirement(s). The explicit fault handling of N is described by a transition relation ϕ N specifying how N changes its state from s to s (with s, s ∈ S N ) when some of the requirements it assumes in s stop being satisfied.

Definition 1 (Fault-aware management protocols). Let N = S N , R N , C N , O N , M N be a node, where S N , R N , C N , and O N are the finite sets of its states, requirements, capabilities, and management operations. M N = s N , ρ N , χ N , τ N , ϕ N is a finite state machine defining the fault-aware management protocol of N , where:

-s N ∈ S N is the initial state, -ρ N : S N → 2 R N is a function indicating which requirements must hold in each state s ∈ S N , -χ N : S N → 2 C N is a function indicating which capabilities of N are offered in each state s ∈ S N , -τ N ⊆ S N × 2 R N × 2 R N × O N × S N is
-ϕ N ⊆ S N × 2 R N × S N
is a set of triples modelling the explicit fault handling for a node, i.e. s, ∆, s ∈ ϕ N denotes that the node will change its state from s to s if a subset of the requirements in (ρ(s) -ρ(s )) ∪ ∆ stops being satisfied (with the requirements in ∆ potentially being satisfied by a different capability after the transition) 1 .

Remark. Note that we permit specifying which requirements may be satisfied by different capabilities after a transition to enable dynamic reconfiguration (as we will see in Sect. 4). Intuitively, for each requirement r that is assumed to hold in a given application configuration, only one among the capabilities connected to r is actually used to satisfy r (provided that the corresponding node is actually offering such capability). A transition s, P, ∆, o, s ∈ τ N ensures that the capabilities used to satisfy the requirements in P -∆ continue to be the same after the transition, while the capabilities used to satisfy the requirements in ∆ may be dynamically changed. Similarly, a transition s, ∆, s ∈ ϕ N permits dynamically changing the capabilities used to satisfy the requirements in ∆.

Example 1. Fig. 3 shows the management protocols of the nodes composing our motivating scenario (thick arrows represent τ , dashed arrows represent ϕ). Consider, for instance, the management protocol M frontend , which describes the management behaviour of the microservice frontend. In states uninstalled (initial) and installed it does not require nor provide anything. The same does not hold in the running state, where frontend assumes the requirement endp to (continue to) be satisfied. If the requirement endp is faulted, and there exists a different capability (with respect to that currently bound to endp) that can satisfy it, it is possible to remain in state running by executing the fault-handling transition dynamically changing the actual binding of endp. If instead there is no capability capable of satisfying endp, then the microservice frontend goes back to its state installed. Finally, the protocol specifies that operations install, and uninstall do not need any requirement to be performed, while start and stop require endp to be satisfied. M backend1 is another example of management protocol worth looking at. It indeed includes a state offering a capability (viz., backend 1 is offering its capability api only in the state running), and a transition to dynamically reconfigure the actual binding of a requirement (viz., backend 1 can change the actual binding of the requirement db by executing the operation config in state configured).

M backend 1 M backend 2 M frontend
In the following, we assume fault-aware management protocols to be wellformed, deterministic, and race-free [START_REF] Brogi | Modelling and analysing cloud application management[END_REF][START_REF] Brogi | Fault-aware application management protocols[END_REF]. Also, as the management protocol of a node may leave unspecified how it will behave in case some requirements stop being fulfilled in some states, we assume that management protocols have been automatically completed by adding transitions for all unhandled faults2 .

Analysing the management of composite applications

In this section we illustrate how to analyse and automate the management of composite applications in a fault-resilient manner, by also taking that the application topology may be dynamically reconfigured while the application is managed. More precisely, we show how to automatically determine the management behaviour of an application by composing the protocols of its nodes according to the application topology (Sect. 4.1). We then describe how this permits automating various useful analyses, like checking the validity of a management plan, which are its effects, or how to automatically determine a valid management plan reaching a desired application configuration (Sect. 4.2).

Management behaviour of an application

We hereby show how to determine the fault-aware management behaviour of an application by composing the fault-aware management protocols of its components. In doing so, we exploit some shorthand notations to denote generic composite applications, the nodes in their topology, and the connections among the requirements and capabilities of such nodes.

Definition 2 (Composite application). We denote with A = T, B a generic composite application, where T is the finite set of nodes in the application topol-ogy 3 , and where inter-node connections are described by a binding relation

B ⊆ R T × C T , with R T = N ∈T R N and C T = N ∈T C N ,
which associates each requirement of each node with the capabilities that can be used to satisfy it.

Formally, the semantics of the management protocols of a composite application A = T, B can be defined by a labelled transition system over configurations that denote the states of the nodes in T and the association between each requirement assumed by a node in T and the capability of another node in T that is actually used to satisfy such requirement. Intuitively, G, b o -→ A G , b is a transition denoting that operation o can be executed (on a node) in A when the "global state" of A is G and the "actual binding" among requirements and capabilities is b, making A evolve into a new global state G with a new actual binding b . We next formally define the notions of global state and actual binding for a composite application.

The global state G of an application A stores the current state of each of its nodes, while the actual binding b of an application A stores the current association between the requirements assumed by the nodes in A and the capabilities used to satisfy them.

Definition 3 (Global state).

Let A = T, B be a composite application, and let

N = S N , R N , C N , O N , M N . A global state G of A is a set of states such that: G ⊆ N ∈T S N ∧ ∀N ∈ T.∃!s ∈ G : s ∈ S N .
Notation 1. Let G be a global state of a composite application A = T, B . We denote with ρ(G) the set of requirements that are assumed to hold by the nodes in T when A is in G, and with χ(G) the set of capabilities that are provided by such nodes in G. Formally:

ρ(G) = N ∈T {ρ N (s) | s ∈ G ∧ s ∈ S N }, and
χ(G) = N ∈T {χ N (s) | s ∈ G ∧ s ∈ S N }.
An actual binding is a partial function from the requirements R T to the capabilities C T of an application A = T, B which, informally speaking, defines a "subset" of the binding relation B.

Definition 4 (Actual binding). Let A = T, B be a composite application.

An actual binding b of A is a partial function from the requirements in T to the capabilities in T , which is defined as follows:

b : R T → C T ∧ ∀r ∈ R T : (b(r) = ⊥ ∨ r, b(r) ∈ B).
We now define a function f to denote the set of pending faults in an application A when its global state is G and when its actual binding is b. Intuitively, the faults that are pending in A are the requirements assumed in G that (according to b) are bound to capabilities that are not provided in G or not bound at all. Definition 5 (Pending faults). Let A = T, B be a composite application. The function f denotes the set of pending faults in A:

f (G, b) = {r ∈ ρ(G) | b(r) / ∈ χ(G) ∨ b(r) = ⊥}
where G is a global state of A, and b is an actual binding of A.

We also define a function h N to denote the set of settling handlers for handling all the faulted requirements of a node N that are pending in f (G, b). Such handlers are all fault handling transitions s, ∆, s ∈ ϕ N such that:

-s ∈ G, i.e. s, ∆, s is executable from the current state s of N in G, -ρ N (s ) -∆ ⊆ ρ N (s) -f (G, b), i.e.
s, ∆, s handles all faulted requirements of N (as its target state s is not assuming any of the requirements faulted in f (G, b) but those that can be dynamically rebound), and -∀r ∈ ∆.∃c ∈ χ(G) : r, c ∈ B, i.e. for each requirement r that can be dynamically rebound by s, ∆, s , there exists a capability c that is actually offered in G and that is capable of satisfying r.

h N (G, b) = { s, ∆, s ∈ ϕ N | s ∈ G ∧ ρ N (s ) -∆ ⊆ ρ N (s) -f (G, b) ∧ ∀r ∈ ∆.∃c ∈ χ(G) : r, c ∈ B }
The management behaviour of a composite application A = T, B is defined by a labelled transition system over pairs denoting the global state and actual binding of A. The transition system is characterised by two inference rules, (op) for operation execution and (fault) for fault propagation. The former permits executing a management operation o on a node N ∈ T only if there are no pending faults and all the requirements needed by N to perform o are satisfied (by the capabilities provided by other nodes in T ). The latter defines how to execute settling handlers when there are pending faults.

f (G, b) = ∅ s ∈ G s, P, ∆, o, s ∈ τ N G = G -{s} ∪ {s } ∀r ∈ ρ(G) : r / ∈ ∆ ⇒ b (r) = b(r) ∀r ∈ ρ(G ) : r, b (r) ∈ B ∀r ∈ P : b (r) ∈ χ(G) ∧ r, b (r) ∈ B G, b o -→ G , b (op) f (G, b) = ∅ s ∈ G s, ∆, s ∈ h N (G, b) G = G -{s} ∪ {s } ∀r ∈ ρ(G) : r / ∈ ∆ ⇒ b (r) = b(r) ∀r ∈ ρ(G ) : r, b (r) ∈ B ∀r ∈ ∆ : b (r) ∈ χ(G) ∧ r, b (r) ∈ B ∀ s, , s ∈ h N (G, b) : ρ(s ) ⊆ ρ(s ) G, b ⊥ -→ G , b (fault)
The (op) rule defines how the global state of a composite application is updated when a node N performs a transition s, P, ∆, o, s ∈ τ N . Such transition can be performed if there are no pending faults (viz.

Analysing the management behaviour of applications

The management behaviour defined in Def. 7 permits analysing and automating the management of a composite application. For instance, we can easily determine which sequences (or, more in general, which workflows) of management operations can be considered valid in a given application configuration. To simplify definitions, we introduce some shorthand notations to observe only the (transitions corresponding to) management operations executed while managing a composite application. Notation 2. Let A = T, B be a composite application. The observable behaviour of A is denoted by a labelled transition system whose configurations are pairs G, b (where G is a global state of A and b is an actual binding for A), and whose transition relation is defined by the following inference rules: The introduced modelling can be exploited for various other purposes besides checking plan validity. For instance, since different sequential traces of a valid plan may lead to different global states, it is interesting to characterise deterministic plans.

G, b o -→ G , b G, b o -→ G , b G, b ⊥ -→ G , b G , b o -→ G , b G, b o -→ G , b Intuitively, a sequence of operations o 1 o 2 . . . o n is valid in a given application configuration G, b if (i) o 1 is executable in G,

Definition 9 (Deterministic plan).

Let A = T, B be a composite application. Let also G and b be a global state and an actual binding of A, respectively. A sequence of management operations o

1 . . . o n in G, b is deterministic iff o 1 . . . o n is valid in G, b ∧ ∃!G . G, b o1 -→ . . . on -→ G , .
A workflow W orchestrating the management operations in A is a deterministic plan in G, b iff all its sequential traces are deterministic in G, b and reach the same global state G . Example 3. One can readily check that plan (a) in Fig. 2 is valid and deterministic. Indeed, all its sequential traces are valid in the initial application configuration (i.e., when database is unavailable, backend 1 , backend 2 and frontend are uninstalled, and the actual binding is empty), and they all bring the application to the global state where all microservices are running. Note that the above holds independently from the fact that the requirement endp of frontend will be bound to the capability api offered by backend 1 or to that offered by backend 2 .

Plan (b) is instead not valid in the initial application configuration. This is because all sequential traces starting with database.run • backend 1 .install • backend 1 .start are not valid (because the management protocol of backend 1 does not allow to execute start before config -see M backend2 in Fig. 3).

Plan (c) is not valid either in the initial application configuration, because all the sequential traces starting with backend 1 .install • backend 1 .config are not valid. This is because the management protocol of backend 1 constrains the executability of config to the satisfaction the requirement endp of backend 2 (see M backend2 in Fig. 3). The latter can only be satisfied by the capability db of database, which is however not provided by database in its starting state unavailable (see M database in Fig. 3).

Checking whether a given plan is valid or deterministic corresponds to visiting the graph generated by the transition system of an application's management behaviour (Def. 7), which also models the non-determinism due to the choice of the new actual binding b . It is worth noting that, thanks to the constraints on management protocols and to the way they are combined, both the possible global states and the possible actual bindings are finite, hence guaranteeing that the above mentioned visit of the graph eventually terminates.

It is also worth noting that the effects of a deterministic workflow W on the states of an application's components, as well as on the requirements and capabilities that are available, can be directly determined from the global state reached by performing any of the sequential traces of W .

Moreover, the problem of finding whether there is a deterministic plan that starts from an application configuration and achieves a specific goal (e.g., bringing some components of an application to specific states, or making some capabilities available) can also be solved with a visit of the graph associated with the transition system of an application's management behaviour. This is especially useful to automatically determine plans dynamically reconfiguring the topology of an application, or to restore a desired application configuration after some application components got stuck because of a fault5 (as we discussed in our motivating scenario -Sect. 2).

Finally, it is worth characterising a weaker notion of validity, to denote those plans whose sequential traces may fail depending on the actual bindings chosen while executing them. Intuitively, a sequence of operations is weakly valid if there exists an application configuration G , b reached by executing o 1 in G, b such that o 2 . . . o n can all be performed. Weak validity of plans follows from that of their sequential traces. A weakly valid plan warns that it may fail. By observing its sequential traces, it is possible to understand whether such a warning can be ignored when deploying and managing a concrete instance of the application (e.g., since a problematic actual binding will never be chosen because of security policies), or whether they can cause real issues at runtime. Notably, such issues can be avoided by exploiting the above explained planning techniques to find a deterministic plan (if any) reaching the same global state reached by the successful traces of a weakly valid plan.

Related work

The problem of automating composite application management is one of the major trends in today's IT [START_REF] Leymann | Cloud computing[END_REF]. Management protocols [START_REF] Brogi | Modelling and analysing cloud application management[END_REF][START_REF] Brogi | A petri net-based approach to model and analyze the management of cloud applications[END_REF], as well as Aeolus [START_REF] Di Cosmo | Aeolus: a Component Model for the Cloud[END_REF], permit automatically deploying and managing multi-component cloud applications. The underlying idea of both approaches is quite simple: Developers describe the behaviour of their components through finite-state machines, and such descriptions can be composed to model the management behaviour of a composite application. Engage [START_REF] Fischer | Engage: A deployment management system[END_REF] is another approach for processing application descriptions to automatically deploy applications. Fault-aware management protocols [START_REF] Brogi | Fault-aware application management protocols[END_REF] extend management protocols [START_REF] Brogi | Modelling and analysing cloud application management[END_REF], and differ from Aeolus [START_REF] Di Cosmo | Aeolus: a Component Model for the Cloud[END_REF] and Engage [START_REF] Fischer | Engage: A deployment management system[END_REF], since they permit explicitly modelling possible faults of components, as well as how to react when such faults occurs.

However, the fault-aware management protocols in [START_REF] Brogi | Fault-aware application management protocols[END_REF] assume many-to-1 dependencies among the nodes forming a topology. The approach presented in this paper properly extends fault-aware management protocols by relaxing this assumption, and by also allowing to specify whether the capability used to satisfy a requirement may be dynamically changed (by choosing among the many available and connected to it in the application topology).

Other approaches worth mentioning are Rapide [START_REF] Luckham | Specification and analysis of system architecture using rapide[END_REF], Darwin [START_REF] Magee | Dynamic structure in software architectures[END_REF] and π-ADL [START_REF] Oquendo | π-adl: An architecture description language based on the higherorder typed π-calculus for specifying dynamic and mobile software architectures[END_REF]. Rapide, Darwin and π-ADL are very close in the spirit to our approach, as they are languages for describing composite systems, whose components expose require and provide ports (corresponding to our notions of requirements and capabilities, respectively). The structure of a system is given by interconnecting such ports, and it can dynamically be changed while execution progresses. Rapide, Darwin and π-ADL however differ from our approach as they only permit many-to-1 interconnections among components, since they assume application components to be stateless (viz., once instantiated, a component assumes all its require ports to be satisfied, and it offers all its provide ports), and since they do not permit explicitly specifying how to handle the faults affecting a component (when one of the requirements it assumes stop being satisfied).

The rigorous engineering of fault-tolerant systems is a well-known problem in computer science [START_REF] Butler | Rigorous Development of Complex Fault-Tolerant Systems[END_REF], with many existing approaches targeting the design and analysis of such systems. For instance, [START_REF] Johnsen | Incremental fault-tolerant design in an object-oriented setting[END_REF] proposes a way to design objectoriented systems by starting from fault-free systems, and by subsequently refining such design by handling different types of faults. [START_REF] Qiang | Automatic fault localization for BIP[END_REF] and [START_REF] Betin Can | Eliminating synchronization faults in air traffic control software via design for verification with concurrency controllers[END_REF] instead focus on fault-localisation, thus permitting to redesign a system to avoid the occurrence of such a fault. These approaches differ from ours because they aim at obtaining applications that "never fail", since all potential faults have been identified and properly handled. Our approach is instead more recovery-oriented [START_REF] Candea | Recovery-oriented computing: Building multitier dependability[END_REF], since we focus on applications where faults possibly occur, and we permit designing applications capable of being recovered.

Similar considerations apply to [START_REF] Grunske | Model-driven safety evaluation with state-event-based component failure annotations[END_REF], [START_REF] Kaiser | A new component concept for fault trees[END_REF], and [START_REF] Alhosban | Bottom-up fault management in service-based systems[END_REF], which however share with our approach the basic idea of modelling faults in single components and of composing the obtained models according to the dependencies between such components (i.e., according to the application topology).

[13] proposes a decentralised approach to deploy and reconfigure cloud applications in presence of failures. It models a composite application as a set of interconnected virtual machines, each equipped with a configurator managing its instantiation and destruction. The deployment and reconfiguration of the whole application is then orchestrated by a manager interacting with virtual machine configurators. [START_REF] Durán | Robust and reliable reconfiguration of cloud applications[END_REF] shares with our approach the objective of providing a decentralised and fault-aware management of a composite application, by specifying the management of each component separately. However, it differs from our approach since it focuses on recovering virtual machines that have been terminated only because of environment faults, while we also permit describing how components react to application-specific faults.

[21] proposes an approach to identify failures in a system whose components' behaviour is described by finite state machines. Even though the analyses are quite different, the modelling in [START_REF] Liggesmeyer | Improving system reliability with automatic fault tree generation[END_REF] is quite similar to ours. It indeed relies on a sort of requirements and capabilities to model the interaction among components, and it permits "implicitly" modelling how components behave in presence of single/multiple faults. Our modelling is a strict generalisation of that in [START_REF] Liggesmeyer | Improving system reliability with automatic fault tree generation[END_REF], since a component's state can evolve not only because of requirement unsatisfaction but also because of invoked operations, and since we permit "explicitly" handling faults (i.e., fault handling transitions are distinct from those modelling the normal behaviour of a component). Similar considerations apply to [START_REF] Chen | Fault propagation formal modeling based on stateflow[END_REF], whose modelling is also based on finite state machines with input and output channels (which permit fault communication and propagation by components).

In summary, to the best of our knowledge, the approach we propose in this paper is the first that permits automatically orchestrating the management of composite applications (i) accounting for many-to-many dependencies among application components, (ii) allowing to dynamically change/reconfigure application topologies, and (iii) assuming that faults possibly occur while managing composite applications.

Conclusions

Fault-aware management protocols [START_REF] Brogi | Fault-aware application management protocols[END_REF] are a modular and reusable way to model the management behaviour of application components (including how they react to potential faults), and to analyse and automate the management of a complex application composed by multiple components. However, the fault-aware management protocols in [START_REF] Brogi | Fault-aware application management protocols[END_REF] assume many-to-1 dependencies among the nodes in an application topology (viz., a capability can be used to satisfy multiple requirements, while a requirement can be satisfied only by a given capability), and this does not permit dealing with composite applications having multiple nodes that can satisfy a given requirement of another node (such as the microservice-based application in our motivating scenario -Sect. 2).

In this paper we have presented an extension of fault-aware management protocols, which permits modelling and analysing composite applications whose topologies have many-to-many dependencies among components. The proposed extension is such that any capability connected to a requirement can be used to satisfy such requirement when the latter is needed by the corresponding node. The proposed extension also permits specifying whether the capability used to satisfy a requirement of a node can be dynamically changed (when executing a management operation or handling a fault), hence allowing to dynamically reconfigure the topology of an application.

The proposed extension of fault-aware management protocols paves the way for their exploitation for modelling and analysing elasticity and live updates of the components forming a composite application. Both cases require to add/remove replicas of nodes, as well as of their ingoing and outgoing dependencies, to/from the topology of a composite application, hence requiring to support many-tomany dependencies and dynamic reconfiguration. The proposed extension of fault-aware management protocols includes such support, and it can hence be exploited to model the evolution of the states of node replicas. The formalisation of the above is in the scope of our immediate future work.

We believe that the proposed modelling and analysing techniques can also pave the way towards the development of self-adaptive composite applications. Self-adaptive applications are controlled by the so-called MAPE (Monitor, Analyse, Plan and Execute) loop [START_REF] Salehie | Self-adaptive software: Landscape and research challenges[END_REF]. Indeed, our techniques can be exploited during the Analyse and Plan steps of the MAPE loop controlling a composite application. The Monitor and Execute instead require to adapt and integrate existing approaches to work with fault-aware management protocols. Such adaptation and integration are left for future work.

It is also worth noting that, even if some of the analyses we presented in Sect. 4 have exponential time complexity in the worst case, they still constitute a significant improvement with respect to state-of-the-art, as currently the management of composite applications is coordinated manually (e.g., by developing ad-hoc scripts), and it is hardly reusable since it is tightly coupled to the application. We plan to further improve the support for the analyses in Sect. 4, by offering a tool capable of validating management plans and of automatically determining valid plans reaching desired goals (by extending the prototype 6 for the fault-aware management protocols of [START_REF] Brogi | Fault-aware application management protocols[END_REF]).

Finally, it is worth noting that fault-aware management protocols do not take into account costs nor QoS, since their focus is on automatically coordinating the management of the components forming a composite application. Cost and QoS are however important factors [START_REF] Armbrust | A view of cloud computing[END_REF], and they should be taken into account when modelling and analysing the management of composite applications. This could be solved by further extending management protocols by allowing to specify the amount of resources actually offered by a capability, and "how many" of such resources are needed to satisfy a requirement connected to such capability. The extension of fault-aware management protocols to include cost and QoS is in the scope of our future work.

Fig. 1 .

 1 Fig. 1. Motivating example.

Fig. 2 .

 2 Fig. 2. Example of deployment plans. Empty circles denote the start of plans, boxes represent the execution of management operations, "plus" operators are used to start and terminate parallel flows, and filled circles denote the end of plans.

Fig. 3 .

 3 Fig. 3. Example of fault-aware management protocols.

Definition 6 (

 6 Settling handlers). Let A = T, B be a composite application, and let G and b be a global state and an actual binding of A, respectively. Let N = S N , R N , C N , O N , M N be a node in T , with M N = s N , ρ N , χ N , τ N , ϕ N . The function h N denotes the set of settling handlers for the faults pending in f (G, b) and affecting N :

Example 2 .

 2 Consider again the application in our motivating scenario (Sect. 2), and suppose that it is in the following global state G (Def. 3): frontend.running backend 1 .configured backend 2 .running database.running Suppose also that the actual binding b of the application (Def. 4) is the following: b(frontend.endp) = backend 1 .api b(backend 1 .db) = database.db b(backend 2 .db) = database.db In the above situation, the set of pending faults f (G, b) (Def. 5) is the following: frontend.endp The set of settling handlers h frontend (G, b) (Def. 6) for the above pending fault is the following: frontend.running, {frontend.endp}, frontend.running frontend.running, {}, frontend.installed Definition 7 (Management behaviour of a composite application). Let A = T, B be a composite application, and let N = S N , R N , C N , O N , M N with M N = s N , ρ N , χ N , τ N , ϕ N . The management behaviour of A is modelled by a labelled transition system whose configurations are pairs G, b , where G is a global state of A and b is an actual binding for A, and whose transition relation is defined by the following inference rules:

  , f (G, b) = ∅), and if there exists a new actual binding b such that: -∀r ∈ ρ(G) : r / ∈ ∆ ⇒ b (r) = b(r), i.e. b preserves the actual binding of the requirements that are assumed in G and that cannot be dynamically changed by the transition, -∀r ∈ ρ(G ) : r, b (r) ∈ B, i.e. all requirements assumed after the transition are bound to capabilities that can satisfy them (according to B), and -∀r ∈ P : b (r) ∈ χ(G) ∧ r, b (r) ∈ B, i.e. all requirements needed to perform the transition are bound to capabilities actually provided in the global state G and that can satisfy them (according to B). As a result, the application configuration G, b is changed to G , b , where G is obtained from G by updating the state of N (viz., G = G -{s} ∪ {s }), and where b is a new actual binding satisfying the above explained conditions. The (fault) rule instead models fault propagation. It defines how the global state G of a composite application A is updated when executing a settling handler s, ∆, s for a node N . A settling handler s, ∆, s ∈ h N can be executed if there are pending faults (viz., f (G, b) = ∅), and if there exists a new actual binding b satisfying conditions analogous to those imposed by the (op) rule. Also, among all settling handlers, s, ∆, s is the handler whose target state s assumes the biggest set of requirements 4 (viz., ∀ s, , s ∈ h N (G, b).ρ(s ) ⊆ ρ(s )). As a result, the application configuration G, b is changed to G , b , where G is obtained from G by updating the state of N (viz., G = G -{s} ∪ {s }), and where b is a new actual binding satisfying the above explained conditions.

Definition 8 (

 8 b , and (ii) whatever is the application configuration G , b reached by executing o 1 in G, b , the sequence o 2 . . . o n can always be performed in G , b . Validity of plans follows from that of their sequential traces. Valid plan). Let A = T, B be a composite application. Let also G and b be a global state and an actual binding of A, respectively. A sequence of management operations o 1 o 2 . . . o n is valid in G, b iff it is empty or (i) ∃ G , b : G, b o1 -→ G , b , and (ii) ∀ G , b : G, b o1 -→ G , b ⇒ o 2 . . . o n is valid in G , b . A workflow W orchestrating the management operations in A is a valid plan in G, b iff all the sequential traces of W are valid in G, b .

Definition 10 (

 10 Weakly valid plan). Let A = T, B be a composite application. Let also G and b be a global state and an actual binding of A, respectively. The sequence o 1 o 2 . . . o n of management operations in A is weakly valid in G, b iff it is empty or ∃ G , b : G, b o1 -→ G , b ∧ o 2 . . . o n is weakly valid in G , b A workflow W orchestrating the management operations in A is a weakly valid plan in G, b iff one of its sequential traces is weakly valid in G, b .

  a set of quintuples modelling the transition relation, i.e. s, P, ∆, o, s ∈ τ N denotes that in state s, and if the requirements in P are satisfied (with those in ∆ ⊆ P potentially being satisfied by a different capability after the transition), o is executable and leads to state s , and

A transition s, ∆, s ∈ ϕN permits handling the fault of a requirement r either by leading to a state s not assuming r any more (when r ∈ ρ(s)-ρ(s )), or by changing its actual binding (when r ∈ ∆).

The procedure to automatically complete management protocols is discussed in[START_REF] Brogi | Fault-aware application management protocols[END_REF]. Essentially, they are completed by adding transitions for all unhandled faults, all leading to a "sink" state that requires and provides nothing.

For simplicity, and without loss of generality, we assume that the names of states, requirements, capabilities, and operations of a node are all disjoint. We also assume that, given two different nodes in a topology, the names of their states, requirements, capabilities, and operations are disjoint.

In this way, fault-handling transitions are guaranteed (to handle all the faults on a node and) to minimise the amount of requirements that stop being assumed.

In[START_REF] Brogi | Fault-aware application management protocols[END_REF] we illustrate how to recover application that are stuck because a fault was not properly handled, or because of unforeseen faults (e.g., due to non-deterministic application bugs). The approach is based on the idea of automatically determining valid plans restoring a desired application configuration, and (despite[START_REF] Brogi | Fault-aware application management protocols[END_REF] assumes many-to-1 dependencies among application components) it can be easily adapted to cope with the notion of validity presented in this paper.

https://github.com/di-unipi-socc/barrel.