Oriane Siméoni

Ahmet Iscen

Giorgos Tolias

Yannis Avrithis
email: ioannis.avrithis@inria.frahmet.iscen

Ondřej Chum
email: chum@cmp.felk.cvut.cz

Unsupervised object discovery for instance recognition

Severe background clutter is challenging in many computer vision tasks, including large-scale image retrieval. Global descriptors, that are popular due to their memory and search efficiency, are especially prone to corruption by such a clutter. Eliminating the impact of the clutter on the image descriptor increases the chance of retrieving relevant images and prevents topic drift due to actually retrieving the clutter in the case of query expansion. In this work, we propose a novel salient region detection method. It captures, in an unsupervised manner, patterns that are both discriminative and common in the dataset. Saliency is based on a centrality measure of a nearest neighbor graph constructed from regional CNN representations of dataset images. The descriptors derived from the salient regions improve particular object retrieval, most noticeably in a large collections containing small objects.

Introduction

Particular object retrieval becomes very challenging when the object of interest is covering a small part of the image. In this case, the amount of relevant information is significantly reduced. Large objects might be partially occluded, while small objects are on a background that covers most of the image. A combination of both, occlusion and cluttered background, is not rare either. These conditions naturally arise from image acquisition and make naive approaches fail, including global template matching or semirobust template matching [START_REF] Oliva | Building the gist of a scene: The role of global image features in recognition[END_REF].

Ideally, image descriptors should be extracted only from the relevant part of the image, suppressing the irrelevant clutter and occlusions. In this paper, we attempt to determine the regions containing the relevant information, as shown in Figure 1, in a fully unsupervised manner.

Methods based on robust matching of hand-crafted local features are naturally insensitive to occlusion and background clutter. The locality of the features allows to match small parts of images in regions containing the object of in- terest, while the incorrect matches are typically removed by robust geometric consistency check [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. Methods based on efficient matching of vector-quantized local-feature descriptors were introduced in context of image retrieval by Sivic and Zisserman [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF].

Retrieval methods based on descriptors extracted by convolutional neural networks (CNNs) have become popular because they combine good precision and recall, efficiency of the search, and reasonable memory footprint [START_REF] Babenko | Neural codes for image retrieval[END_REF][START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF]. Deep neural networks are capable of learning, to some extent, what information in the image is relevant, which results in a good performance even with global descriptors [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF][START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF][START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF]. However, if the signal to noise ratio is low, e.g. the object is relatively small, multiple objects are present, etc., the global CNN descriptors fail [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF][START_REF] Iscen | Fast spectral ranking for similarity search[END_REF].

A class of methods inspired by object detection have recently emerged. Instead of attempting to match the whole image to the query, the problem is changed to finding a rectangular region in the image that best matches the query [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF][START_REF] Salvador | Faster r-cnn features for instance search[END_REF]. An inefficient search by sliding window is intractable for large collections of images. The exhaustive enumeration is approximated by similarity evaluation on a number of pre-selected regions. The regions are either selected geometrically to cover the whole image at different scales, as in R-MAC [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF], or by considering the content by object or region proposal methods [START_REF] Salvador | Faster r-cnn features for instance search[END_REF][START_REF] Song | Deep region hashing for efficient large-scale instance search from images[END_REF][START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF].

Another direction of suppressing irrelevant content is saliency detection [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF][START_REF] Noh | Largescale image retrieval with attentive deep local features[END_REF]. For each image, a saliency map, that captures more general region shapes compared to (a small set of) rectangles, is first estimated. The contribution of each pixel (or region) is then proportional to the saliency of that location.

In this work we introduce a very simple pooling scheme that inherits the properties of both saliency detection and region based pooling and that, like all previous approaches, is applied to each image in the database independently. In addition, we investigate the use of the resulting regional representation for automatic, offline object discovery and suppression of background clutter, which considers the image collection as a whole. Unlike previous approaches, we do this in an unsupervised way. As a consequence, our representation takes two saliency detection steps into account. One that acts per image and depends solely on its content and another that considers the image collection as a whole and captures frequently appearing objects.

In both cases, we derive a global representation that outperforms comparable state-of-the-art methods in retrieving small objects on standard benchmarks, while the memory footprint and online cost is only a fraction compared to more powerful regional representations [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF][START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF]. Moreover, we show that our representation benefits significantly from query expansion methods.

Section 2 discusses our contributions against related work. Section 3 describes our methodology including our pooling scheme in Section 3.3 and our object discovery approach in Section 3.8. We present experimental results in Section 4 and draw conclusions in Section 5.

Related work

Local features and geometric matching offer an attractive way for retrieval systems to handle occlusions, clutter, and small objects [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Jégou | Improving bag-offeatures for large scale image search[END_REF]. One of their drawbacks is high query complexity and large storage cost; an image is typically represented by several thousands features. Many methods attempt to decrease the amount of indexed features by removing background clutter while maintaining the relevant information. The selection procedure is either applied independently per image or considers an image collection as a whole. Common examples of the former case are bursty feature detection [34], symmetry detection [START_REF] Tolias | Symcity: Feature selection by symmetry for large scale image retrieval[END_REF] or use of semantic segmentation [START_REF] Arandjelović | Visual vocabulary with a semantic twist[END_REF]27]. The methods of the second category, are scalable enough to jointly process the whole collection and perform feature selection by the following assumption. A feature that repeats over multiple instances of the same object in the dataset is likely to appear in novel views of the object too. Representative cases are common object discovery [START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problems[END_REF][START_REF] Tolias | Image search with selective match kernels: aggregation across single and multiple images[END_REF], co-occurrence detection [6], or methods using GPS information [START_REF] Gammeter | I know what you did last summer: Object-level auto-annotation of holiday snaps[END_REF]20].

The work by Turcot and Lowe [START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problems[END_REF] performs pairwise spatial verification on hand-crafted local features across all images and only indexes verified features. With an additional off-line cost, the on-line stage is sped up and the memory footprint is reduced. However, unique views of objects are not verified and thus discarded. In this work, we address a similar selection problem based on more powerful CNN-based representation rather than local features.

Recent advances on deep learning [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF][START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF][START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF][START_REF] Gordo | End-to-end learning of deep visual representations for image retrieval[END_REF][START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF]] dispense with the large memory footprint by using global descriptors and cast the problem of instance search as Euclidean nearest neighbor search. Nevertheless, background clutter and occlusion are better handled by regional representation. Regional descriptors significantly increase the performance when they are indexed independently [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF][START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF] but this comes at a prohibited memory and computational cost for large scale scenarios. Region Proposal Networks (RPN) are applied either off-the-shelf [START_REF] Salvador | Faster r-cnn features for instance search[END_REF] or after finetuning [START_REF] Song | Deep region hashing for efficient large-scale instance search from images[END_REF] for instance search. The RPNs reduce the number of regions per image only to the order of tens. Our work focuses on aggregating regional representation that keeps the complexity low but we rather detect regions around salient objects and objects that frequently appear in the dataset. Jimenez et al. [16] construct saliency maps and perform region detection to construct global image vectors, as we also do. However, they employ generic object detectors trained on ImageNet and this makes the method not applicable with fine-tuned networks which provide the best performance. The Hessian-affine detector is used on CNN activations to detect repeatable regions [START_REF] Jeong | Regional deep feature aggregation for image retrieval[END_REF]. The major benefit in this work, though, comes from second order pooling and higher dimensional descriptors.

Saliency maps are another way to handle clutter and occlusions. Once more, there exist both examples of computation in an unsupervised manner [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF][START_REF] Laskar | Context aware query image representation for particular object retrieval[END_REF] or learned [START_REF] Noh | Largescale image retrieval with attentive deep local features[END_REF][START_REF] Kim | Learned contextual feature reweighting for image geo-localization[END_REF] and applied per image afterwards. Our approach generates saliency maps in a fully unsupervised way that capture both salient objects on single images but also repeating objects appearing in a particular image collection.

Method

Like [START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problems[END_REF], our objective is to remove transient and nondistinctive objects as in Figure 1 and rather focus on objects appearing frequently in a dataset. Beginning with the activation map of a convolutional layer in a CNN, one would need access to a local representation to automatically discover such objects. On the other hand, knowing what these objects are would help forming a local representation by selecting regions depicting them, which appears to be a chicken-and-egg problem. Without an initial region selection, we risk "discovering" uninformative but frequently appearing "stuff"-like patches, for instance sky. Figure 2. Overview of our offline unsupervised process. On the top row, CNN activations of dataset images are used to extract a feature saliency map, on which a set of regions is detected. On the bottom row, a centrality measure is obtained per region from a region k-NN graph. Using this measure, a dense object saliency map is formed from the original CNN activations and the feature saliency. This map is focusing on objects automatically discovered in the dataset, with background clutter removed. Finally, another set of regions is detected on the object saliency map to extract descriptors and represent the dataset for retrieval.

Overview

Fortunately, it is possible to make an initial selection based on CNN activations alone, without any training and without bounding box annotations. As described in Section 3.3, the mechanism is inspired by CroW [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF] and Grad-CAM [START_REF] Selvaraju | Grad-CAM: Why did you say that? visual explanations from deep networks via gradient-based localization[END_REF] and generates a feature saliency map. This initiates our offline analysis illustrated in Figure 2. A small set of rectangular regions is detected per image from this map as discussed in Section 3.4. This first round of detection is applied independently per image and depends only on its content.

Each region in the dataset is associated to a feature saliency score and a visual descriptor, pooled from the activation map of the corresponding image, as discussed in Section 3.5. It is now possible to compute a centrality score per region, representing the "significance" of each region in the dataset. This is based on a region k-NN graph and is discussed in Sections 3.6 and 3.7. Now, given a new image, we can infer the "significance" of every region from its nearest neighbors in the graph, yielding a dense object saliency map as discussed in Section 3.8. This is a regression problem and we suggest a non-parametric k-NN solution. Finally, we detect a small set of rectangular regions on this saliency map and extract a global descriptor to represent dataset images for retrieval, as discussed in Section 3.9. This second detection procedure takes into account all salient and repeating objects appearing in the dataset.

The entire process is fully unsupervised and only assumes on the-shelf networks trained on a classification or retrieval task without bounding box annotations.

Representation

We represent the activation map of a convolutional layer as a non-negative 3d tensor A ∈ R h×w×c where h, w are the spatial resolution (height, width) and c is the number of feature channels. The set of valid spatial positions is P : =

[h] × [w]

Feature saliency

Inspired by cross-dimensional weighting and pooling (CroW) [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF] and class activation mapping (CAM) [45], we construct a 2d saliency map of an image based on a convolution activation of that image alone. Following CroW, we compute an idf-like weight per channel b ∈ R c with elements

b j = log (a + ) 1 a j + (1)
for j ∈ [c], where a : =

1 wh p∈P 1[A p• ] ∈ R c
is the average number of nonzero elements per channel. We then compute a weighted sum over channels

F : = j∈[c] b j A• j (2)
Finally, we obtain the 2d feature saliency (FS) map F ∈ R h×w by normalizing F according to [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF]. Contrary to CroW, we use the feature channel weights when computing the 2d spatial weights, amplifying channels with sparse activation. This order of summation is the same as in CAM. However, we are working with channel weights obtained by a sparsity property on any convolutional layer, without any assumption on the network topology. CAM on the other hand, assumes global average pooling followed by a fully connected layer mapping channels to classes and uses the parameters of this layer to obtain a saliency map per class.

Region detection

We are given a 2d saliency map S, which can be either the feature saliency described in section 3.3 or the object saliency described in Section 3.8. We use an expanding Gaussian mixture (EGM) model [START_REF] Avrithis | Approximate gaussian mixtures for large scale vocabularies[END_REF] to detect a number of salient rectangular regions. This is a variant of expectationmaximization (EM) that iteratively performs local averaging (E-and M-steps) interleaved with a selection process (P-step) similar to non-maximum suppression (NMS). In doing so, it dynamically estimates the number of regions.

The original algorithm applies to point sets and isotropic Gaussian components. Here we extend it to functions, considering that a saliency map is a function S : P → R. We use it to fit a number of components, each modeling a rectangular region in 2d coordinate space. We also extend it to a diagonal covariance model, so that a rectangle is modeled by an axis-aligned ellipse.

In particular, given 2d saliency map S ∈ R h×w , we represent it as a set of Gaussian functions s i : R 2 → R with

s i (x) : = S pi N (x|p i , σI 2 ) (3) for i ∈ [ ], x ∈ R 2
where N is the normal density, = |P | is the number of positions and we represent P as {p 1 , . . . , p }. Here, σ is a scale parameter that determines how coarse or fine the region representation will be for the given saliency map. Similarly, we represent components as Gaussian functions q k : R 2 → R with

q k (x) : = π k N (x|µ k , Σ k ) (4) for k ∈ [m], x ∈ R 2
, where m is the number of components and

π k ∈ R, µ k ∈ R 2 and Σ k ∈ R 2×2
are the mixing coefficient, mean and diagonal covariance matrix respectively of component k. Means represent region centers, while the (inverse) eigenvalues of covariance matrices represent heights and widths. We initialize components as q k ← s k for k ∈ [m], with m ← . In the expectation (E)-step, we compute the responsibility

γ ik ← s i , q k j∈[m] s i , q j (5) of component k ∈ [m] for sample i ∈ [ ],
where f, g is the L 2 inner product of square-integrable functions f, g : R d → R, computed in closed form for Gaussian functions [START_REF] Avrithis | Approximate gaussian mixtures for large scale vocabularies[END_REF]. In the maximization (M)-step, we update parameters as

π k ← k (6) µ k ← 1 k n i=1 γ ik p i (7)
Σ k ← 1 k n i=1 γ ik diag(p i -µ k ) •2 (8)
where k : = n i=1 γ ik is the effective number of points assigned to component k and X •2 : = X • X is the Hadamard product power for a vector or matrix X.

Finally, in the purge (P)-step, similarly to NMS, we process components in descending order of mixing coefficient and we decide whether to keep a component or not depending on its overlap with the collection of previously kept components. Overlap is measured by a generalized responsibility function similar to [START_REF] Babenko | Neural codes for image retrieval[END_REF], and again inner products are given in closed form [START_REF] Avrithis | Approximate gaussian mixtures for large scale vocabularies[END_REF]. This means that the number of components m is potentially reducing at each iteration.

Figure 3 shows how regions are formed during EGM iterations, starting from one small region centered on each spatial position. We get 4 clean regions on the ground truth building, as well as 6 regions on background objects, which, although less salient, cannot be removed based on the feature saliency alone.

Region pooling

Given a rectangular region R ∈ R of an image with feature saliency map F ∈ R h×w , we associate to it feature saliency f : = µ F (R) ∈ R, where

µ F (R) : = 1 |R| p∈R Fp (9)
is the average of 2d map F over R.

In addition, given the activation map A ∈ R h×w×c of the same image, it is standard practice that a descriptor is obtained by pooling over R, for instance sum [START_REF] Babenko | Aggregating deep convolutional features for image retrieval[END_REF], weighted sum [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF] or max [START_REF] Azizpour | From generic to specific deep representations for visual recognition[END_REF][START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF] pooling. We adopt the latter choice to extract descriptor z : = m A (R) ∈ R c , where

m A (R) : = max q∈R A q• (10)
is the maximum of 3d tensor A over R along the spatial dimensions. This has been the basis of fine-tuning in [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF][START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF].

A particular set of regions, uniformly sampled on a grid at different scales, is referred to as regional maximum activation of convolutions (R-MAC) [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF]. Global description, referred to as MAC, is a special case where there is a single region R = P . In contrast, we detect a set of regions based on saliency maps in this work.

Finally, we follow [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF] in performing supervised whitening of the descriptors by simultaneous diagonalization [START_REF] Mikolajczyk | Improving descriptors for fast tree matching by optimal linear projection[END_REF]. In particular, given vector z ∈ R c , we 2 -normalize, center, whiten, PCA-project and renormalize to generate the region descriptor v : = w(z) ∈ R d for region R. Function w : R c → R d represents this pipeline entirely.

Graph construction

Given an image dataset, we assume here a set of regions {R 1 , . . . , R n } are detected from the saliency maps (Section 3.4), a feature saliency vector f : = (f 1 , . . . , f n ) ∈ R n is computed with the corresponding average saliency per region in [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF], and a set of descriptors V : = {v 1 , . . . , v n } ⊂ R d are extracted from the activation maps, whitened and normalized per region (Section 3.5).

Based on the above information, we construct a k-NN graph on those regions in order to compute a global centrality score per region as discussed in Section 3.7, which enables us to form an object saliency map on a new image, described in Section 3.8. Approximate techniques for k-NN graph construction [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] can be used to handle largescale databases.

We construct a weighted undirected graph having the set of descriptors V as vertices. Following [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF], the edge weights are defined according to mutual k-nearest neighbors (NN) in the descriptor space. In particular, given descriptors v, u ∈ R d , we measure their similarity by s(v, u) = (v u) β , where exponent β > 0 is a parameter. We define the sparse symmetric nonnegative adjacency matrix W ∈ R n×n with elements w ij being s(v i , v j ) if v i , v j are mutual k-NN in V and zero otherwise.

We define the n × n degree matrix D : = diag(W 1) where 1 ∈ R n is the all-ones vector, and the symmetrically normalized adjacency matrix

W : = D -1/2 W D -1/2 , ( 11
)
with the convention 0/0 = 0. Following [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF][START_REF] Iscen | Fast spectral ranking for similarity search[END_REF], we define the n × n matrices L α : = (D -αW )/(1α) and

L α : = D -1/2 L α D -1/2 = (I -αW)/(1 -α), (12)
where α ∈ [0, 1). Both are positive-definite [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF][START_REF] Iscen | Fast spectral ranking for similarity search[END_REF].

Graph centrality

With the above definitions in place, the objective is to compute a vector g ∈ R n where each element g i represents the significance of vertex v i in the graph, for i ∈ [n]. We define this centrality vector as the solution g * ∈ R n of the linear system

L α g = 1. (13)
As in [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF], we solve this system by the conjugate gradients (CG) [START_REF] Nocedal | Numerical optimization[END_REF] method. Any method would be equally appropriate because this is computed just once offline. The solution g * is a graph centrality measure [START_REF] Mej | Networks: an introduction[END_REF], and in particular, Katz centrality [START_REF] Katz | A new status index derived from sociometric analysis[END_REF]. Centrality is a global measure of significance of vertices in a graph, and PageRank [START_REF] Page | The PageRank citation ranking: bringing order to the web[END_REF] is maybe the most well-known. In fact, Katz centrality was introduced as such a global measure before being adapted by boundary condition y to measure relevance to individual vertices by Hubbell [11]. This work has a long history before being rediscovered e.g. by [START_REF] Page | The PageRank citation ranking: bringing order to the web[END_REF][START_REF] Zhou | Ranking on data manifolds[END_REF], as summarized in the study of spectral ranking [START_REF] Vigna | Spectral ranking[END_REF].

Saliency map construction

Given the region descriptor set V , the region saliency vector f and the associated centrality vector g * of an entire dataset, the problem is to construct a new saliency map S ∈ R h×w for an image in the dataset. The image is represented by its activation map A ∈ R h×w×c . Since this saliency is based on regions or patterns appearing frequently in the dataset, which are commonly associated to repeating objects, we call it object saliency (OS).

We compute S by a sliding window iteration over each position p ∈ P . The saliency value S p at p is found as a linear combination of the centrality values of the nearest neighbors in V of a patch centered at p. In particular, we consider a square patch R p of side a centered at p. We compute the vector u p : = w(m A (R p )) ∈ R d by max-pooling over R p , whitening and normalizing as discussed in Section 3.5. If N p is the set of indices of the k-NN of u p in V , we compute S p as

S p : = F Θ p i∈Np s(v i , u p )f θ i g * i . (14)
That is, each neighboring region descriptor v i is weighted by its similarity to patch descriptor u p , its feature saliency f i and its centrality g * i , while the entire sum is scaled by the feature saliency Fp at the current position p of the image being considered. Exponents Θ and θ control the relative importance of feature saliency of the current image and neighbors, respectively, compared to centrality. The object saliency computation is illustrated in Figure 4. Looking at the input image and is feature saliency map F alone, it is not evident which is the object of interest and which is clutter. This is only found by discovering other instances of the same object in the dataset, as represented by the graph.

Representation

The object saliency map S highlights patterns that appear frequently in the dataset, with the background clutter removed. It is only natural then to apply the same method described in Section 3.4 to this map in order to detect a small number of regions per image. Unlike the regions detected from the feature saliency map F , these new regions are more likely to appear in a new image. For the purpose of evaluation, we investigate both saliency maps.

For each region R detected from a saliency map ( F or S) in a dataset image with activation map A, we apply max pooling and 2 -normalization. All descriptors are then summed and the resulting descriptor is whitened with w : R c → R d as described in Section 3.5. The difference here is that we apply whitening on the aggregated vector and not separately per region. This is the same representation as R-MAC evaluated in [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF] and both yield a global image representation in R d , but here the regions are detected in the saliency map rather than being uniformly distributed.

Pooling based on saliency is in fact the idea explored in CroW [START_REF] Kalantidis | Crossdimensional weighting for aggregated deep convolutional features[END_REF], but here we follow the nonlinear two-level pooling of R-MAC (max followed by sum) rather than the one-level sum of CroW. This is more powerful and has also been the basis of fine-tuning in [START_REF] Gordo | Deep image retrieval: Learning global representations for image search[END_REF].

Experiments

We apply the proposed representation on image retrieval. In particular, we have two variants of our method that both use the region detection described in Section 3.4. The saliency map which the detection is performed on is different in each case. FS.EGM uses the feature saliency map described in Section 3.3, and OS.EGM uses the object saliency map described in Section 3.4. The former is image specific, while the latter both image and database specific.

Experimental setup

Test sets. We evaluate on Oxford Buildings [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and the more recently introduced Instre [43] dataset. Instre contains around 27k images of small objects in cluttered scenes while objects appear with different variations, such as rotation, occlusion and scale changes, making it a challenging case. We use the evaluation protocol introduced in [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF] for Instre. We add 100k distractors from Flickr [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] to Ox-ford5k to perform experiments at larger scale. We refer to it as Oxford105k. Search performance in all datasets is measured with mAP.

Image Representation. We represent each image by global image representation as described in Section 3.9. This reduces image similarity to cosine, which is common practice [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF]. Feature extraction is performed with the VGG network [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] that is fine-tuned specifically for image retrieval [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF]. Supervised whitening [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF] is used for postprocessing. The same network is additionally used to compare against two baselines. First, MAC global descriptor, which is obtained by global max pooling and the descriptor that the network is directly optimized for [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF]. Second, the baseline approach (Uniform), which refers to regional max pooling for regions that are uniformly sampled at 3 scales, as in R-MAC [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF]. Our variants are different in that regions are detected from salient and repeating objects, while aggregation and whitening is identical. Detection is applied to dataset images only, while we use the provided bounding boxes on the query side.

Implementation Details. To simplify region detection, each saliency map is masked above threshold τ and element-wise raised to exponent ρ before detection, which removes the weakest regions and increases the contrast between foreground and background objects. We set ρ = 1, τ = 0.2 and scale parameter σ = 1 before any parameter tuning is performed. We determine OS parameters Θ, θ in ( 14) by visual inspection of OS and set Θ = 2, θ = 3 throughout our experiments. We perform our experiments on a 16-core Intel Xeon 2.00GHz CPU. It takes 36s to create the graph on Instre, while centrality computation takes negligible amount of time. It takes 0.02s for FS computation and detection per image, while 0.23s in the case of OS.

Parameter tuning

In this section, we show the impact of FS.EGM and OS.EGM detection parameters on the retrieval performance. We tune the parameters on Oxford5k when using diffusion [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF]. The remaining experiments evaluate the proposed representation with the chosen parameters on Instre and Ox-ford105k as well.

Feature saliency detection is evaluated first by FS.EGM, while we do not compute object saliency and OS.EGM yet. Figure 5 shows the effect of ρ, which controls the contrast of the the saliency map. We observe that large ρ is needed to remove as much clutter as possible from the noisy FS activations. We set ρ = 5 for the rest of our experiments. Figure 6 shows the effect of threshold τ , which is another selectivity parameter. We set τ = 0.4. Scale σ is used during EGM sampling as explained in Section 3.4. Its impact in performance is shown in Figure 7. Setting σ = 2.5 results in good performance and regions that are large enough for FS.EGM.

Object saliency detection is then evaluated once the feature saliency parameters are fixed, and EGM detection is applied on the new saliency map. We observe that OS behaves quite differently to FS, because foreground objects are much cleaner. The impact of parameters σ and ρ is shown in Figures 5 and7 respectively. It is remarkable that a much lower exponent is needed in this case. We choose ρ = 2 and σ = 2. Finally, we fix τ = 0 for OS, as the saliency maps obtained with OS are exactly zero at background regions. The effect is shown in Figure 6.

Evaluation of saliency maps

We exploit the fact that Instre dataset comes with bounding box annotation for all database images. We use the ground truth information to quantitatively evaluate the saliency maps. We define precision as the sum of saliency over ground truth regions, normalized by the sum over the entire image, and we measure it for FS and OS as shown in Figure 8. High precision means that a saliency map is well aligned to the ground truth bounding boxes. Given that these bounding boxes are not used anywhere, the improvement that OS offers is impressive. Visual examples for saliency maps and detections for FS.EGM and OS.EGM are shown in Figure 9. In all cases, OS is cleaner and focuses on objects that FS cannot discriminate.

Comparison to other methods

We compare our methods to the standard practice of uniform region sampling (Uniform) as in R-MAC and global max pooling (MAC). We additionally propose a variant of OS.EGM, where further uniform region sampling at 2 scales 1. mAP comparison of our methods marked with against baselines on all tested datasets. QE refers to query expansion by diffusion [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF].

is performed within each detected region. We refer to this as OS.EGM-. All methods are tested with k-NN search and global diffusion [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF], which is a method for query expansion or manifold search and is known to significantly improve performance. Results are given in Table 1.

FS.EGM improves performance compared to uniform sampling by focusing on salient objects. However, salient objects are not necessarily relevant for the particular dataset. This is what OS.EGM captures and boosts the search performance, especially on Instre. On all datasets, MAC is better than uniform sampling (R-MAC). This is because the network used [START_REF] Radenović | CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples[END_REF] is directly fine-tuned to optimize MAC. However, when using diffusion, we outperform it on all datasets. This can be explained by the fact that diffusion boosts any items that are similar to the top-ranking ones according to the original similarity [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF], so it is essential that these items are reliable. A global descriptor is affected by clutter in general. By contrast, our representation is global yet clutter-free. Our improvements are larger on Instre, which is more challenging due to small objects and severe background clutter. This is exactly where our detection is essential. Most Instre images are also quite different than the building images which the network is fine-tuned on. This is probably why our representations outperform MAC even without diffusion on this dataset.

There are several other previous approaches that deal with region detection or saliency masks, which are not directly comparable, so they are not included in Table 1. Nevertheless, we outperform their reported results. Salvador et al. [START_REF] Salvador | Faster r-cnn features for instance search[END_REF] use the off-the-shelf VGG and fine-tune RPN in the test set. Without using query expansion, they obtain 71.0 in Oxford5k. Similarly, Jimenez et al. [16] learn class weights and apply them on the activation maps of off-the-shelf VGG and achieve 73.6 in Oxford5k. Song et al. [START_REF] Song | Deep region hashing for efficient large-scale instance search from images[END_REF] train on different datasets, and achieve 78.3 in Oxford5k. The results obtained by learning a saliency mask are not comparable since spatial verification with local features is always applied in the end [START_REF] Noh | Largescale image retrieval with attentive deep local features[END_REF]. Finally, Zheng et al. [START_REF] Zheng | Accurate image search with multi-scale contextual evidences[END_REF] achieve 83.4 . mAP comparison of our global OS.EGM ( ) to R-Match with uniformly sampled regional descriptors, with and without diffusion on Oxford5k. Text labels refer to query time.

with regional representation on Oxford5k. They employ both CNN and local features, while we only rely on CNN and much more compact representation. Finally, no work other than [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF] evaluates on Instre which is rather challenging due to small objects.

Region cross-matching methods [START_REF] Razavian | Visual instance retrieval with deep convolutional networks[END_REF] represent an image with multiple vectors, sacrificing memory footprint and complexity for accuracy. In particular, the memory is linear in the number of regions, while the complexity is quadratic. We compare our global representation with region crossmatching (R-Match) and regional diffusion [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF] in Figure 10. Different numbers of regions are obtained by GMM reduction, exactly as in [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF]. Compared to regional descriptors, we require about 4 times less memory to achieve the same performance. The runtime complexity gain is in the order of 4 2 , which holds for the case of R-Match and also for the first part of diffusion where Euclidean nearest neighbors are found. The diffusion complexity is O(m), where m is the number of non-zero entries of the graph. We found that m is 3.7 times smaller in our case and our measurements of actual query timings agree with this ratio.

Conclusions

We propose a region detection approach that is dataset specific but requires no supervision. It captures not only salient objects by considering each image individually but also frequently appearing ones by considering the dataset as a whole. As a result, we avoid separate indexing of regional descriptors and construct a global descriptor by pooling over data-dependent regions, which performs well under background clutter and severe occlusions. We demonstrate that this approach is effective in particular object retrieval where background clutter is a common problem.

Figure 1 .

 1 Figure 1. The saliency map (right) computed for an input image (left) based on common-structure analysis on Instre dataset. Background clutter and objects not relevant for this dataset are automatically removed. The image is represented only by the region detected on the saliency map.

  1 and the set of all rectangles with vertices in P is denoted by R. By A pj we represent an element of A at position p ∈ P and channel j ∈ [c]. By A• j ∈ R h×w we denote the 2d feature map of A corresponding to channel j ∈ [c]. By A p• ∈ R c we denote the vector containing all feature channels at position p ∈ P .

  image i = 0, m = 272 i = 2, m = 29 i = 3, m = 22 i = 5, m = 17 i = 7, m = 11 i = 14, m = 9

Figure 3 .

 3 Figure 3. Evolution of regions during EGM iterations on the feature saliency map of an image of Magdalen tower from Oxford buildings dataset, shown on the left. Below each image we display the iteration i and the number of regions m.

Figure 4 .

 4 Figure 4. Computing the object saliency map S of an image from Instre dataset (top), as defined in (14). For each patch, its neighbors in the graph (right) are found. Common patterns with high centrality in green outline, outliers with low centrality in red. S (bottom) then focuses on patches similar to common patterns and combines with feature saliency F (left).

Figure 5 .Figure 6 .Figure 7 .

 567 Figure 5. mAP on Oxford5k versus saliency exponent ρ for FS.EGM and OS.EGM.

Figure 8 .Figure 9 .

 89 Figure 8. Histogram of saliency precision for FS and OS maps measured on all images of Instre.

  Figure 10. mAP comparison of our global OS.EGM ( ) to R-Match with uniformly sampled regional descriptors, with and without diffusion on Oxford5k. Text labels refer to query time.

Here, [i] is the set {1, . . . , i} for i ∈ N.

Acknowledgments The authors were supported by the MSMT LL1303 ERC-CZ grant. The Tesla K40 used for this research was donated by the NVIDIA Corporation.


Cesar Vargas

Nadège Varsier

Jean Schwoerer

Xavier Lagrange

Modeling of MTC Energy Consumption for D2D communications with Chase Combining HARQ Scheme

  L'archive ouverte pluridisciplinaire

Modeling of MTC Energy Consumption for D2D communications with Chase Combining HARQ Scheme

Cesar Vargas Anamuro * † , Nadège Varsier * , Jean Schwoerer * and Xavier Lagrange † * Orange Labs, Meylan, France Email: {cesaraugusto.vargasanamuro, nadege.varsier, jean.schwoerer}@orange.com † IMT Atlantique/IRISA, Rennes, France Email: xavier.lagrange@imt-atlantique.fr

Abstract-Device-to-Device (D2D) communication for Massive Machine-Type Communication (mMTC) applications is a promising approach to reduce the energy consumption of the battery-limited Machine-Type Devices (MTDs) located in poor coverage areas. In this paper, we analyze the energy consumption of the MTDs when Automatic Repeat reQuest (ARQ) and Hybrid ARQ with Chase Combining (CC-HARQ) mechanisms are used to improve the reliability of D2D communication. By using the tools of stochastic geometry, we derive analytical expressions for the system success probability, the average number of transmissions, and the average MTD energy consumption. Numerical results show that CC-HARQ mechanism outperforms ARQ mechanism in terms of energy consumption, especially when the distance between an MTD and its relay increases (at low relay density) or when the density of MTDs sharing the same sub-channel increases.

Index Terms-Energy consumption, Device-to-Device, mMTC, HARQ with Chase Combining, Stochastic Geometry

I. INTRODUCTION

Reducing the energy consumption of Machine-Type Devices (MTDs) is one of the main challenges of Massive Machine-Type Communication (mMTC) applications since MTDs typically operate using a battery, which is not recharged or replaced for several years. In addition, MTDs are lowcomplexity devices and have relaxed requirements in terms of data rate.

Device-to-Device (D2D) communication is considered as one of the technical enablers for future 5G networks. D2D refers to the direct communication between two devices, without going through the base station. Recently, D2D technology has been studied as an alternative for mMTC applications. In that case, the User Equipments (UEs) act as relays establishing D2D links with nearby MTDs [START_REF] Pratas | Underlay of low-rate machine-type D2D links on downlink cellular links[END_REF] [2] [START_REF] Rigazzi | Aggregation and trunking of M2M traffic via D2D connections[END_REF]. This configuration allows reducing the energy consumption of the MTDs since the MTD-UE path-loss is less than the MTD-BS path-loss.

In D2D communications, there are two modes for resource allocation [START_REF] Gpp | Study on LTE Device to Device Proximity Services; Radio Aspects[END_REF]. In mode 1 or Scheduled mode, the base station schedules and assigns resources. All MTDs inside the cell then use dedicated resources to transmit as in traditional cellular communications, avoiding intra-cell interference but not intercell interference. In mode 2 or Autonomous mode, MTDs autonomously select resources from pools that are preconfigured or given by the base station if they are in coverage. In this mode, depending on the traffic expectations, the mobile operators dimension the resource pools. In autonomous mode, two or more devices could select the same resource causing interference between them. In this paper we focus our analysis on the Autonomous mode, and we leave the Scheduled mode for future work.

Retransmission schemes increase the transmission reliability exploiting the temporal diversity of the channel. The most common schemes are Automatic repeat request (ARQ) and hybrid ARQ (HARQ) that combines ARQ and forward error correction (FEC) mechanisms.

In our analysis, we are considering only the transmission of messages from the MTDs to the network since mMTC traffic is usually uplink-dominated. An MTD uses a UE as a relay to send its messages to the base station. Both devices are connected through a D2D link. ARQ is the simplest retransmission scheme, in which the same packet is retransmitted if requested by the receiver. In HARQ with Chase combining (CC-HARQ) [START_REF] Chase | Code combining: A maximum-likelihood decoding approach for combining an arbitrary number of noisy packets[END_REF], the same operations are done as for ARQ at the transmitter side. Nevertheless, the operations are slightly more complex at the receiver side. In this paper, the MTDs are the transmitters while the relays (UEs) are the receivers. Therefore, ARQ and CC-HARQ would be suitable for mMTC applications since they allow to improve the transmission reliability without increasing the complexity of the MTDs.

Most of the existing studies related to retransmission mechanisms for mMTC do not consider interference [START_REF] Centenaro | A comparison of energyefficient HARQ protocols for M2M communication in the finite blocklength regime[END_REF] [7] [START_REF] Manhas | Energy efficiency analysis of HARQ with chase combining in multihop wireless sensor networks[END_REF]. In [START_REF] Manhas | Energy efficiency analysis of HARQ with chase combining in multihop wireless sensor networks[END_REF], the authors consider HARQ with Chase Combining for wireless sensor networks due to the simplicity of this protocol. In [START_REF] Bagaa | An efficient D2D-based strategies for machine type communications in 5G mobile systems[END_REF] the authors propose one solution allowing reducing the energy consumption of the MTDs. They consider a model of energy consumption taking into account the cumulative interference, but the analysis was only carried out for the ARQ mechanism.

In this paper, we compare the performance of ARQ and CC-HARQ mechanisms in terms of energy consumption, considering the D2D autonomous resource allocation scheme. We take into account the impact of Rayleigh fading, log-normal shadowing, and interference caused by other MTDs. Analytical expressions for the success probability, the average number of transmissions, and the MTD energy consumption are derived using a stochastic geometry approach.

The remainder of this paper is organized as follows. Section II presents the system model. The system success probability and the number of transmissions are derived in section III.

In Section IV, we analyze the energy consumption and we compare with some numerical results in Section V. Finally conclusions are given in Section VI.

II. SYSTEM MODEL

A. Network Model

We consider a cellular network where the locations of UEs form a homogeneous Poisson point processes (PPP) Φ U with density λ U in R 2 . An active MTD transmits its reports using a UE as a relay via a D2D link. D2D links and cellular links are orthogonal. Hence, there is no interference between these systems. We assume that the locations of MTDs form an independent homogeneous PPP Φ M with density λ M in R 2 . An MTD shares resources with other ones that use the same sub-channel. Hence, a UE acting as a relay suffers interference from other MTD-UE links as shown in Fig. 1.

B. Communication Model

During the discovery phase, an MTD searches and selects a UE which will be used as a relay until the transmission is successful. In this study, we only analyze the MTD energy consumption in the data transmission phase, i.e. after the MTD has selected a relay. All the MTDs transmit at fixed power P tx and at fixed rate R m as in [START_REF] Pratas | Underlay of low-rate machine-type D2D links on downlink cellular links[END_REF].

Without loss of generality, we consider a reference receiver (UE-0) located at the origin of coordinates (0, 0) and its transmitter peer (MTD-0) located at a distance r g from UE-0. We model the communication channel considering path loss attenuation r -α g , Rayleigh fading H, and log-normal shadowing effect exp(χ). Then, the reception power P rx at UE-0 can be derived as

P rx = P tx H(r g /r 0 ) -α exp(χ), (1)
where P tx is the MTD transmission power, H is an exponentially distributed random variable (RV) with unit mean, r 0 is a constant propagation parameter, α is the path loss exponent, and χ is zero-mean Gaussian RV with variance σ 2 .

Log-normal shadowing is also characterized in terms of its dB-spread σ dB = 10σ/ ln [START_REF] Dhillon | Downlink Rate Distribution in Heterogeneous Cellular Networks under Generalized Cell Selection[END_REF].

Let K be the number of available sub-channels for D2D links, which is dimensioned by the operator depending on the density of devices sharing resources. We assume that an MTD in D2D mode randomly selects a sub-channel with the same probability 1/K (Autonomous mode). Then, the MTDs that have selected the same sub-channel as MTD-0 form a thinning PPP Φ m = {x i } from Φ M , with density λ m = λ M /K. The cumulative interference at UE-0 can be expressed as

I = ∑ xi∈Φm P tx H xi (r g,xi /r 0 ) -α exp(χ xi ), (2)
where all H xi are i.i.d. exponential RVs with unit mean, all χ xi are i.i.d. Gaussian RVs with zero mean and variance σ 2 , and r g,xi represents the distance from the origin of coordinates to x i .

Let θ be the signal-to-interference and noise ratio (SINR) at UE-0. Combining and simplifying ( 1) and ( 2), we obtain

θ = P rx N 0 + I ≈ P rx I = Hr -α g exp(χ) ∑ xi∈Φm H xi r -α g,xi exp(χ xi ) , ( 3
)
where N 0 represents the noise power, usually negligible compared to cumulative interference.

In order to simplify our analysis, we use the displacement theorem [10, lemma 1]. Then, we can re-write (3) as

θ = Hr -α ∑ x ′ i ∈Φ ′ m H x ′ i r -α x ′ i , ( 4
)
where

Φ ′ m = {x ′ i } is a homogeneous PPP with density λ m E[e -2χ/α ] = λ m e 2σ 2 /α 2
and r = e -χ/α r g is the modified distance between MTD-0 and UE-0. In order to ensure analytical tractability, in the rest of this paper, our analysis is based on the modified distance r.

The transmission success probability of a single transmission is given by

P s = P(θ ≥ θ th ) = P ( Hr -α ∑ x ′ i ∈Φ ′ m H x ′ i r -α x ′ i ≥ θ th ) , (5)
where θ th is the SINR threshold. Since H ∼ exp(1), and Φ ′ m forms a PPP with density λ m e 2σ 2 /α 2 , we can use the tools of stochastic geometry. Then, (5) can be derived as in [START_REF] Haenggi | Interference in large wireless networks[END_REF]:

P s (r) = exp(-πλ m e 2σ 2 /α 2 r 2 θ 2/α th Γ(1 + 2/α)Γ(1 -2/α)), (6)
where Γ(x) = ∫ ∞ 0 t x-1 e -t dt denotes the gamma function. The cumulative distribution function (CDF) of the SINR is

F θ (θ) = 1-exp(-πλ m e 2σ 2 /α 2 r 2 θ 2/α Γ(1+2/α)Γ(1-2/α)). (7)
Then, the probability density function (PDF) of the SINR can be derived as where Ω = (πλ m e 2σ 2 /α 2 r 2 Γ(1 + 2/α)Γ(1 -2/α)) -α/2 , and β = 2/α. Note that (8) follows a Weibull distribution of shape parameter β and scale parameter Ω.

f θ (θ) = dF θ (θ) dθ = β Ω ( θ Ω ) β-1 e -(θ/Ω) β , ( 8)

III. SYSTEM SUCCESS PROBABILITY AND AVERAGE NUMBER OF TRANSMISSIONS

In this section, we calculate the system success probability and the average number of transmissions for ARQ and CC-HARQ schemes. In both schemes, MTD-0 resends a packet until it is successfully received or until a maximum number of transmissions N is reached. UE-0 answers with an acknowledgment (ACK) if the packet is received correctly or a negative acknowledgment (NACK) if the packet is received with errors as shown in Fig. 2.

A. Performance of ARQ scheme

In ARQ, when a packet is received with errors the receiver discards it and asks for a retransmission of the same packet.

a) System success probability: The probability of failure in each transmission is independent of the other transmissions [START_REF] Bagaa | An efficient D2D-based strategies for machine type communications in 5G mobile systems[END_REF]. We can derive an expression of the system success probability after N transmissions for ARQ scheme:

P s,arq (r) = 1 -(1 -P s ) N , ( 9
)
where P s is the success probability in a single transmission, which is defined in [START_REF] Centenaro | A comparison of energyefficient HARQ protocols for M2M communication in the finite blocklength regime[END_REF]. b) Average number of transmissions: Considering the ARQ scheme, the number of transmissions T arq needed to correctly receive a packet varies randomly according the channel conditions. The average number of transmissions can be obtained as in [START_REF] Bagaa | An efficient D2D-based strategies for machine type communications in 5G mobile systems[END_REF]:

T arq (r) = 1 -(1 -P s ) N P s . ( 10
)
From ( 9), we can also deduce the z-th percentile number of transmissions for ARQ:

T z-th,arq (r) = ⌈ln(1 -z%)/ ln(1 -P s )⌉, (11)
where ⌈•⌉ is the ceiling operator.

B. Performance of HARQ with Chase Combining scheme

In CC-HARQ, a packet received with errors is not discarded anymore. The receiver stores this packet in a buffer, and then combines it with the next transmitted packet. The transmitted packet is an identical copy of the original packet.

Thanks to the maximal ratio combining (MRC) technique, the energy is accumulated in each transmission. Hence, the global SINR after n transmissions can be written as:

Θ n = n ∑ i=1 θ i , ( 12
)
where θ i is the SINR at the receiver in round i. a) System success probability: Unlike the ARQ scheme, in CC-HARQ the success probability in each new transmission depends on the previous transmissions. Let φ n be the probability that first n transmissions fail in a CC-HARQ scheme:

φ n = P(Θ n < θ th ) = P( n ∑ i=1 θ i < θ th ). ( 13
)
We have shown in ( 8) that θ i follows a Weibull distribution. Then φ n is the CDF of the sum of n i.i.d. Weibull RVs of shape β and scale Ω parameters. An approximation for the CDF of the sum of n i.i.d. Weibull RVs is presented in [START_REF] Bessate | A very tight approximate results of MRC receivers over independent Weibull fading channels[END_REF]. Using this approximation we have

φ n = 1 -exp(-U n ) n-1 ∑ i=0 (U n ) i i! , ( 14
)
where

U n = πλ m e 2σ 2 /α 2 r 2 Γ(1 + 2 α )Γ(1 -2 α ) ( Γ(n+2/α) n!Γ(1+2/α) θ th
) 2/α . We can re-write [START_REF] Liu | Cross-Layer combining of adaptive Modulation and coding with truncated ARQ over wireless links[END_REF] as

φ n = 1 - Γ(n, U n ) (n -1)! , ( 15
)
where Γ(a, x) = ∫ ∞ x t a-1 e -t dt is the upper incomplete gamma function.

Then, the system success probability after N transmissions for CC-HARQ can be expressed as

P s,harq (r) = 1 -φ N = Γ(N, U N ) (N -1)! . ( 16
)
b) Average number of transmissions: The average number of transmissions of CC-HARQ can be derived as in [START_REF] Lagrange | Throughput of HARQ protocols on a block fading channel[END_REF]:

T harq (r) = 1 + N -1 ∑ n=1 φ n . ( 17
)
Combining ( 15) and ( 17), we obtain

T harq (r) = N - N -1 ∑ n=1 Γ(n, U n ) (n -1)! , ( 18
)
where N is the maximum number of transmissions, and U n is defined in [START_REF] Liu | Cross-Layer combining of adaptive Modulation and coding with truncated ARQ over wireless links[END_REF]. The z-th percentile number of transmissions for CC-HARQ T z-th,harq can be derived from (16). We have

T z-th,harq (r) = n * , ( 19
)
where n * is the smallest integer value which satisfy the inequality Γ(n * ,U n * ) (n * -1)! ≥ z%. We can use numerical computation to find n * .

IV. ENERGY CONSUMPTION MODELING

The MTD energy consumption in a single transmission can be derived as

E m,1 = P m,T t m,T + P m,R t m,R + P m,I t m,I , ( 20
)
where P m,T , P m,R , and P m,I are the MTD power consumption in Tx state, Rx state, and Idle state respectively; t m,T , t m,R , and t m,I are the duration of Tx state, Rx state, and Idle state respectively (see Fig. 2). We assume that an MTD transmits at a fixed power (no power control) and at a fixed data rate (no link adaptation) due to its low complexity and low cost. Then, we have t m,T = L/R m , where L is the packet size and R m is the MTD bit rate.

The back-off time t m,I is a random time that allows the independence of transmissions in case two or more devices transmit at the same time. In this work, we consider t m,I = ηt m,T , where η is a random integer following an exponential distribution with a mean η = 5. It should be noted that the back-off time does not increase significantly the energy consumption since the MTD during this time is in Idle state. On the other hand, the delay could increase significantly as a function of η. However, mMTC applications are delay-tolerant.

We assume that t m,R = t m,T , thereby the ACKs will have enough redundancy in order to ensure that they will be received correctly by the MTD.

Then, the average MTD energy consumption in a single transmission can be expressed as

E m,1 = (P m,T + P m,R + ηP m,I ) L R m . ( 21
)
The average of the global energy consumed by the MTD E m,G can be derived as

E m,G (r) = E m,1 T , ( 22
)
where T denotes the average number of transmissions defined in [START_REF] Dhillon | Downlink Rate Distribution in Heterogeneous Cellular Networks under Generalized Cell Selection[END_REF] and (18) for ARQ and CC-HARQ respectively.

V. NUMERICAL RESULTS

In this section, the analytical and simulation results are presented to validate the accuracy of our analytical models. The simulation parameters are specified in Table I. We consider the same modulation and coding schemes (MCS) as in [START_REF] Liu | Cross-Layer combining of adaptive Modulation and coding with truncated ARQ over wireless links[END_REF], as well as the same SINR thresholds (see Table II). All the simulations are performed using MATLAB.

The system success probability as a function of the modified distance MTD-UE is shown in Fig. 3. In this figure, NARQ represents a single transmission. We can see that the analytical and the simulation results fit well. We can also notice that as N increases CC-HARQ scheme becomes more advantageous than ARQ scheme.

We compare the performance of ARQ and CC-HARQ in terms of the number of transmissions as well as the average energy consumption. In this regard, we assume N large enough (e.g. N = 128) such that the success probability is similar in both retransmission schemes up to a certain MTD-UE distance (see Fig. 3 ). As shown in Fig. 3, for N = 128 and MCS-3, the maximum distance MTD-UE where the success probability is greater than 95% in both retransmission schemes is approximately 140 meters. Therefore, in the rest of this paper, we compare the performance of both ARQ and CC-HARQ for distances MTD-UE less than 140 meters. The average and the 95th percentile number of transmissions for ARQ and CC-HARQ schemes are presented in Fig. 4. We can see that the analytical and the simulation results fit well. In addition, this figure shows the advantage of CC-HARQ over ARQ in terms of the number of transmissions. This advantage increases when the distance MTD-UE increases. For example, at a distance MTD-UE of 100 meters, 95% of the MTDs transmit successfully in less than 9 and 6 transmissions using ARQ and CC-HARQ respectively. Fig. 5 shows the average MTD energy consumption for different modulation and coding schemes. Note that the energy consumption could be reduced if the MTD would be able to dynamically adapt its modulation and coding scheme.

One of the main characteristics of the mMTC applications is the high connection density (devices/km 2 ) while one of the advantages of D2D relaying is the reuse of resources. As we mentioned above, λ m represents the density of MTDs sharing the same sub-channel. So far, we have considered that all the MTDs share a single sub-channel (K = 1). However, due to the interference the number of transmissions and the MTD energy consumption increase exponentially, especially for distances MTD-UE greater than 100 meters. A solution would be to increase the number of sub-channels, which reduce the density of devices sharing a sub-channel. Fig. 6 shows the average MTD energy consumption considering 1, 2, 4 and 8 sub-channels. From this figure, we observe that CC-HARQ outperforms ARQ in terms of energy consumption especially at a high density of devices sharing a sub-channel.

As shown in Fig. 6, the difference between CC-HARQ and ARQ in terms of energy consumption is more evident as the modified distance MTD-UE r increase. This distance is a random variable since the locations of the MTDs and UEs form two independent PPPs. Assuming that during the discovery phase an MTD selects the nearest UE as its relay. Hence, the CDF of r can be derived as in [START_REF] Andrews | A Tractable Approach to Coverage and Rate in Cellular Networks[END_REF] P(r ≤ R) = 1 -exp(-λ U πR 2 ). It is worthwhile noting that the distance MTD-UE depends only on the density of UEs λ U . For example, for λ U = {16 × 10 -6 , 32 × 10 -6 , 64 × 10 -6 } in 90% of cases the MTD-UE distances are less than 214, 151, 107 meters respectively. The MTD density and the UE density are two important parameters when comparing the ARQ and CC-HARQ schemes.

VI. CONCLUSION AND FUTURE WORKS

In this paper, we compared the performance of ARQ and CC-HARQ mechanisms in terms of the average energy consumption for D2D communications. Using stochastic geome- try, we derived analytical expressions for the system success probability, the average number of transmissions, and the average MTD energy consumption of ARQ and CC-HARQ. Our analysis takes into account Rayleigh fading, shadowing and the interference among D2D links when they share the same sub-channel. The accuracy of these analytical expressions is confirmed by simulations.

For future work, we will investigate the energy consumption of the MTDs using D2D relaying mechanisms where the resources allocation is performed in scheduled mode. Moreover, the model of the energy consumption will be extended considering the discovery phase.

Fig. 1 .

 1 Fig. 1. Network model.

Fig. 2 .

 2 Fig. 2. Retransmission scheme.

Fig. 3 .

 3 Fig. 3. System success probability of ARQ and CC-HARQ as a function of the modified distance MTD-UE, considering MCS-3, maximum number of transmissions N = {2, 8, 128}, and one sub-channel (K = 1).

Fig. 4 .

 4 Fig. 4. Number of transmissions of ARQ and CC-HARQ as a function of the modified distance MTD-UE, considering MCS-3, maximum number of transmissions N = 128, and one sub-channel (K = 1).

Fig. 5 .

 5 Fig. 5. Average MTD energy consumption of ARQ and CC-HARQ as a function of the modified distance MTD-UE, considering maximum number of transmissions N = 128, and one sub-channel (K = 1).

Fig. 6 .

 6 Fig. 6. Average energy consumption of ARQ and CC-HARQ as a function of the modified distance MTD-UE, considering MCS-3, maximum number of transmissions N=128, and number of sub-channels K = {1, 2, 4, 8}.