Student Member, IEEE Sampriti Soor

Senior Member, IEEE B S Daya Sagar

Watershed Arcs in Hierarchical Image Segmentation

Keywords: Watershed Transformation, Watershed Arcs, Image Segmentation, Hierarchical Segmentation, River basin Extraction. ✦

Watershed transform, formulated based on robust mathematical morphological operations, has been one of the most reliable image segmentation methods for years. However, it is constrained by the problem of over-segmentation. To encounter this limitation, region merging approaches such as waterfall and P-algorithm exist in the literature, which processes the entire image iteratively. In this paper, we introduce the concept of watershed arcs that acts as the connected partition lines between the segments on an image and explore several properties. We define the operation of removing an arc that results in merging two neighbor segments and apply it to generate hierarchical segmentation of an input image. At each level, a graph is constructed solely from the representatives of the watershed arcs in the previous level, and the set of arcs to be removed at that level is determined by applying a watershed transformation only on the graph. As the cardinality of the graph reduces drastically at each level, a hierarchy of partitions is produced in a comparatively short amount of time than that of the existing methods. The proposed method is applied to a Digital Elevation Model data to extract hierarchical river basins. We also evaluated the performance of this method in image segmentation compared with some state-of-the-art methods.

INTRODUCTION

I MAGE segmentation, a fundamental challenge in com- puter vision studies, is the process of splitting an image into disjoint regions in such a way that each region is closely similar in terms of characteristics such as intensity, color, or texture. Hierarchical image segmentation is a collection of image segmentations at various detail levels, generated by integrating regions from finer detail levels to create segmentations at coarser detail levels, such that the finer level segmentations are nested within coarser level segmentations. Studying hierarchical segmentation is important because they preserve spatial and neighboring information between split parts.

One of the numerous image segmentation algorithms available in the literature from the earliest methods (e.g., thresholding, histogram-based, region-growing, k-means, etc.) to more advanced algorithms (e.g.,active-contour, graph-cuts, random Markov fields, etc.) is the watershed transformation. Watershed transformation is a powerful tool in the field of mathematical morphology that was first introduced in the 1980s with the goal of segmenting greyscale images. The watershed transformation was explicitly defined as a new kind of region-growing approach by Beucher and Lantuejoul to obtain continuous contours from elevation models [START_REF] Beucher | Use of watersheds in contour detection. int[END_REF]. An algorithmic definition of the watershed transform by simulated immersion was given by Vincent and Soille [START_REF] Vincent | Watersheds in digital spaces: an efficient algorithm based on immersion simulations[END_REF]. Since then, numerous approaches for generating the watershed transformation have appeared in Sampriti Soor and B.S. Daya Sagar is with Systems Science and Informatics Unit, Indian Statistical Institute, Bangalore, India. e-mail: sampreetiworkid@gmail.com, bsdsagar@isibang.ac.in Sampriti Soor did most of this work during his visit to Remote Sensing Lab, University of Trento, and was funded by ITPAR-IV Programme. The work of B. S. D. Sagar was supported by the Indian Space Research Organisation (ISRO), DST-ITPAR-IV respectively, under Grant numbers ISRO/SSPO/Ch-1/2016-17, and INT/Italy/ITPAR-IV/Telecommunication/2018.

the literature [START_REF] Meyer | The dynamics of minima and contours[END_REF], [START_REF] Meijster | A disjoint set algorithm for the watershed transform[END_REF], [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF].

A general issue lies in the classical watershed transformation that yields over-segmentation. Various morphological smoothing operations have been applied to encounter this. Beucher proposed a morphological region-merging algorithm for greyscale images, called waterfall [START_REF] Beucher | Watershed, hierarchical segmentation and waterfall algorithm[END_REF], that in each level reconstructs the input image by a mask generated from its watershed transformation to fill in the depressions, resulting a hierarchically merging of neighbour segments in the image and thus eliminating the over-segmentation problem. The hierarchical algorithm and P-algorithm approached by Beucher and Marcotegui [START_REF] Beucher | P algorithm, a dramatic enhancement of the waterfall transformation[END_REF] addressed the shortsightness problem of the waterfall algorithm by prioritising certain watershed points and reintroducing maxima when reconstructing the image in each level. Apart from these there are few other studies in the literature on morphological methods for hierarchical image segmentation [START_REF] Salembier | Hierarchical morphological segmentation for image sequence coding[END_REF], [START_REF] Najman | Geodesic saliency of watershed contours and hierarchical segmentation[END_REF], [START_REF] Hanbury | Waterfall segmentation of complex scenes[END_REF], [START_REF] Meurie | Morphological hierarchical segmentation and color spaces[END_REF].

In the process of watershed transformation in a grayscale image, the higher altitude pixels that are at the same spatial distance from two neighbour regional minima, are detected as watershed points. These watershed points do not necessarily produce any partition line between the minima extensions in a discrete domain. Several properties of watershed lines, in discrete and continuous spaces are studied in [START_REF] Meyer | Topographic distance and watershed lines[END_REF], [START_REF] Najman | Watershed of a continuous function[END_REF], [START_REF] Marquez-Neila | A morphological approach to curvature-based evolution of curves and surfaces[END_REF].

In this study, we present an original method to derive the connected partition line, termed as watershed arcs, between each pair of neighbor basins that could be useful in various aspects of image analysis, such as the morphology based hierarchical image segmentation method proposed here. The novel contributions of this study are as follows:

i. we define watershed arcs for a general vertex-weighted graph, which act as a true partition between the different segments in an image.

ii. we propose the hierarchical image segmentation method, watershed arcs removal. iii. we establish different properties related to watershed arcs and the proposed method for hierarchical segmentation. Although the watershed arcs removal can be applied to generate the hierarchical clustering on any connected data set, we exclusively applied that for hierarchical image segmentation in this study. We have established that hierarchical image segmentation by watershed arcs removal can be accomplished in a linear time and have calculated an upper bound time complexity for the process. The proposed method performs better than the existing methods in terms of run-time producing comparably accurate segments. We applied this method to a large Digital Elevation Model (DEM) to extract different levels of river-basins which is helpful to understand the flood-risk of a surface.

The organization of the content that follows includes: Section 2 covers notations and terminology besides certain preliminary details related to hierarchical image segmentation and a brief review of classical watershed transformation and waterfall algorithm. Apparently, that forms the basis of the proposed concept of watershed arcs. Section 3 contains the mathematical formulations for the definitions and various properties of watershed points, watershed arcs, and watershed arcs removal, followed by the implementation of the proposed hierarchical segmentation for images with the corresponding algorithm is discussed in section 4. Section 5 covers the analysis of the computational complexity of the proposed approach and gives a comparison of run-time to that of the waterfall algorithm. Section 6 contains experimental results obtained from the implementation of watershed arcs removal on DEM data, as well as a comparison of its performance to various state-of-the-art approaches, followed by concluding remarks and scope of extension in section 7.

NOTATIONS AND TERMINOLOGIES

Graph frameworks are frequently used in image analysis. First, we will describe a few necessary concepts in graph theory that will be essential to build the foundation for our method. Later, we will explain the existing watershed transformation and waterfall algorithms, as well as how our work relates to them.

Graphs

A graph G is defined by G = (V , E ), where V and E ⊆ V × V are the vertex-set and edge-set respectively. G is called an undirected graph if E consists of unordered pairs (u, v) and a directed graph if E consists of ordered pairs (u, v) where u, v ∈ V . A neighborhood of a vertex u is defined by N u = {v : (u, v) ∈ E } and all such v is called a neighbor of u.

A path π p0,p1,...,p l-1 ,p l in G between p 0 and p l is a sequence of vertices (p 0 , p 1 , ..., p l-1 , p l ) such that (p i-1 , p i ) ∈ E , ∀i = 1, 2, ..., l. Any portion of the sequence is called a sub-path of the path π. A path is called acyclic path if no vertex is repeated in the sequence. In an acyclic path (p 0 , p 1 , ..., p l-1 , p l ), the two end-points p 0 and p l are called source and destination respectively. Π G is the set of all acyclic paths in G . Let S(V, E) ⊆ G and p 0 , p l ∈ V , then Π S p0,p l ⊆ Π G is the set of distinct acyclic paths between p 0 and p l in S. Vertex-set in the path π is denoted by V π . If there exists a path from a vertex p to a vertex q in mathscrG, then we say that q is reachable from p, and is denoted as p ⇝ q. π V1⇝V2 indicates an acyclic path from

v 1 ∈ V 1 to v 2 ∈ V 2 , V 1 , V 2 ⊂ V , V 1 ∩V 2 = ϕ; Π V1⇝V2 is the set of distinct acyclic paths between V 1 and V 2 . A sub-graph G ′ = (V ′ ⊆ V , E ′ ⊆ E ) of G is called an induced sub-graph by V ′ in G , denoted by ind G V ′ , if ∀(u, v) ∈ E , u, v ∈ V ′ , (u, v) ∈ E ′ . A connected-component (or component) in graph G is a sub-graph C ⊆ G with vertex- set V C such that ∄(u, v) or (v, u) ∈ E : u ∈ V C , v ∈ (V \V C ). C G and |C G | denotes the set of components and number of components in G respectively. The graph G is called a connected graph if |C G | = 1. V ′ ⊆ V is a vertex-cut in G if |C ind G V \V ′ | > |C G |. A vertex-cut V ′ is a maximal vertex-cut if ∄v ∈ V ′ such that |C ind G V \(V ′ \{v}) | = |C ind G V \V ′ |.

Segmentation in digital images

Let for G = (V , E ) the vertex-set V is defined on Z 2 . A 4-neighbor of vertex u ∈ V can be defined as N 4 u = {v : euc(u, v) ≤ 1, ∀v ∈ V } where euc(u, v) denotes the eucledian distance between u and v; similarly, 8-neighbor of vertex u ∈ V can be defined as [START_REF] Borgefors | Distance transformations in digital images[END_REF]. A connectivity N can be derived from the edge-set E and vice-versa. To process a digital image in graph framework, a general approach is to consider its pixels as such V on Z 2 along with such underlying connectivity, which is often termed as digital grid.

N 8 u = {v : euc(u, v) ≤ √ 2, ∀v ∈ V }. Then G is called a 4-connected graph or a 8-connected graph if E = {(u, v) : ∀u ∈ V v ∈ N 4 u } or E = {(u, v) : ∀u ∈ V v ∈ N 8 u } respectively
A digital single-band image (eg. binary image, greyscale image, Digital Elevation Model etc.) is contemplated by a triple G = (V , N , I ) where (V , N ) forms a digital grid and I : V → N (or V → R for various synthetic remote sensing images and medical images) is a function assigning a value to each pixel/vertex u ∈ V . Now on pixels and vertices will be termed invariably. Pixel-value at vertex v is denoted by I v . Path-length between two pixels p 0 and p l on path π p0,p1,...,p (l-1) ,p l ∈ Π G p0,p l is generally considered as

dist π = |I i -I i-1 |, ∀i ∈ [1, l]. The distance between p 0 and p l is d(p 0 , p l ) = min({dist π : π ∈ Π G p0,p l }).
Segmentation on a digital image is done by generating a surjective labelmap function L : V → N where each image segment is labelled with different values. We denote the labelmap of a vertex u ∈ V by L u and the labelmap of a set of vertices U ⊆ V by L (U ). The unique labels in set of vertices U is denoted by U N IQU E L (U ). A segmentation S on image G is defined by S = {S 1 , S 2 , ..., S n-1 , S n } such that, s∈S ∪s = V and S i ∩ S j = ϕ, i ̸ = j for i, j = 1, 2, ..., n; where n is the number of segments in G . Until now we have applied the proposed hierarchical segmentation method only on single-band images.

Hierarchical segmentation on image

Let H = (S (0) , S (1) , ..., S (hmax) ) be a sequence of segmentations in a image G and S j (i) is the j-th segment at i-th

) = {V } ii. ∀h < h ′ if u ∈ S k (h) , v ∈ S l (h) and u, v ∈ S m (h ′ ) then S k (h) , S l (h) ⊆ S m (h ′ )
The number of levels in this segmentation hierarchy is h max + 1.

Watershed, Waterfall and Watershed Arcs

The geodesic distance between p and q in X ⊆ G is d X (p, q) = min(dist π |π ∈ Π X p,q ). If Y ⊆ X, d X (p, Y ) = min q∈Y (d X (p, q)). The geodesic dilation of size n ≥ 0 of Y within X is the set of the pixels of X whose geodesic distance to Y is smaller or equal to n: δ

(n) X (Y ) = {p ∈ X|d X (p, Y ) ≤ n}. Let {Y i : i = 1, 2, ..., k} is a set of k connected com- ponents, such that, k i=1 Y i = Y ⊆ X ⊆ G . The geodesic influence zone of Y i within X is defined as, iz X (Y i ) = {p ∈ X : d X (p, Y i ) < d X (p, Y j ), ∀ j = {1, 2, ..., k} \ {i}}. The geodesic influence zone of Y within X is defined as, IZ X (Y ) = k i=1 iz X (Y i ) [16]
The threshold set of G at level h is the induced subgraph by T h = {p ∈ V |I p ≤ h} in G . The threshold decompositions for ∀k ∈ [h min , h max ], h min and h max respectively being the minimum and maximum pixel-value in I , obviously satisfy the inclusion relationship: T k-1 ⊆ T k .

Watershed Transform by simulated immersion (by Vincent and Soille [2])

A connected component on G = (V , N , I ) is called a regional minima (M ∈ V ) if ∀m 1 , m 2 ∈ M, I m1 = I m2
and ∀m ∈ M, I m < I n , where n ∈ N m \ M . Let M IN h denotes the union of all regional minima with pixel-value h.

The watershed transformation by simulated immersion is a region-growing approach that grows the segments towards neighbor pixels from each regional minima until convergence. The points associated with a regional minima is called its basins or catchment-basin. Let X h be the union of the computed basins till pixel-value h by following recursion:

X hmin = M IN hmin = T hmin X h+1 = M IN h+1 ∪ IZ h+1 (X h ), h ∈ [h min , h max )
The watershed points in G is given by: V \ X hmax .

In other words, the watershed points are comprising of the points which are at same geodesic distance from two neighbor-basins when convergence is reached. Note that, these watershed points not necessarily provide a boundary/partition to the basins (see Fig. 2b). X (Y ). Let X = (V, E, I X ) and Y = (V, E, I Y ) be two greyscale images defined on the same domain (V, E) and ∀v ∈ V , I X v , I Y v ∈ N ≤ N , i.e., N is the maximum possible pixelvalue for

I X v , I Y v . Let Y ≤ X (i.e., ∀v ∈ V ; I Y v ≤ I X v ). The greyscale reconstruction ρ X (Y ) of X from Y is given by [17], ∀v ∈ V, ρ X (Y )(v) = max{k ∈ [0, N ]|p ∈ ρ (T X k ) c (T Y k ) c }. Reconstruction by watershed: Let for an image X = (V, E, I), ∀v ∈ V, I v ∈ N ≤ m. Let W is the set of watershed points of X. Let a new image X ′ = (V, E, I ′ ) is constructed on the same domain by ∀v ∈ W, I ′ v = I v and ∀v ∈ V \ W, I ′ v = m. Obviously X ≤ X ′ .
The reconstructed image ρ X ′ (X) preserves the significant minima of X.

Watershed points W ′ calculated by the watershed transformaion on ρ X ′ (X) is the outcome of waterfall on X. The fact W ′ ⊂ W eshtablishes the convergence of iterative implementation of the waterfall algorithm to generate hierarchical segmentation on an image. Figure 1a,1b,1c shows an example of hierarchical segmentation on a 1-D image by waterfall algorithm.

Notion of Watershed Arcs

The initial objective we ran into was to generate a riverbasin map for a very large area from DEM data. DEM data generally comes in very high spatial resolution, thus contains numerous small depressions. To create a usable basin map, the basin map directly obtained from the DEM data is needed to be merged hierarchically. The waterfall algorithm conceptually is very appropriate strategy to apply for this objective. However, as the entire image is needed to be reconstructed at each level in the waterfall algorithm, practically it is difficult to use on such large scale data. Also the huge number of mostly unchanged levels produced by the waterfall algorithm is not very effective. The need of a faster but still accurate basin merging strategy was the motivation for this work.

In waterfall algorithm at each level the altitude of each point in the image is elevated by the reconstruction to a related watershed point, thus that watershed point becomes part of a minima extension. But the watershed points, that did not affect in reconstruction of the lower points, remain watershed points in next level too. So if a graph constructed with only the watershed points in an image connecting the neighbouring watershed points and keeping altitude of those points unchanged, a watershed transformation on that graph can detect the same watershed points if the watershed transformation is applied on the reconstructed image (see bottom row of Figure 1).

Consider background idea of watershed transformation, where a demography is thought to be immersed into water after punching holes at each local minima. The points getting water from a same minima are considered as the basin extension of it, and the points at which water from two different basins meets is considered as watershed points. The first identified watershed point between two neighbouring basins is known as the saddle points between them, and it clearly has the lowest elevation among the watershed points between them. In a 1-dimensional image, the saddle points between two basins are same as the watershed points as a pair of neighbour basins has maximum one watershed points between them. For a 2-dimensional image the before discussed graph can be constructed considering only the saddle points as the node points of the graph. A watershed transformation on the graph the points marks some of the saddle points as watershed points, and all the watershed points at previous level corresponding to each of such marked saddle points are considered watershed points of this level.

We consider the corresponding watershed points of a saddle point as a watershed arc. Hence, like saddle points, each watershed arc has a surjective mapping with each pair of neighbour basins. Note that, in higher levels some of the saddle points detected in previous level diminishes, i.e., they become part of a greater basin extension, same way, some of the existing watershed arcs at previous level also diminishes and some arcs get merged with each other. Now, by classical definition, a pair of neighbour basin may not have watershed points between them if the edgepoints of the basins neighbour to each other are equidistant from their corresponding minima. To account all the basins in the hierarchy, we enforced the presence of a watershed arc between each pair of neighbour basins by slightly changing the classical definition of watershed transformation. On a greyscale image demography the minimum set of the maximum altitude pixels needed to traverse on the different paths between two neighbour regional minima are marked as watershed points. The watershed transformation approach proposed here, thus ensures that each pair of neighbor-basins is completely isolated by the presence of watershed points in-between them 2c. At each level some of the existing watershed arcs in previous level become part of the basin points, for that, we have defined a arc removal operation, that keeps the constraint that each pair of neighbour basins are completely disconnected.

Other than hierarchical river basin extraction, we have applied the proposed method for segmentation in greyscale image too. Though we followed the same concept of constructing graphs in higher level with the saddle points of existing arcs in that level, it's worth mentioning that, instead of using the saddle points as the arc representatives, a function depending on the objective of the application can be used. The fundamental goal of this research is to demonstrate the use of the watershed arc partition, which captures the edges in an image, and to propose a hierarchical partition/segmentation method that processes the image significantly faster than previous methods by using a graph structure composed of representatives of such edges.

HIERARCHICAL SEGMENTATION USING WATER-SHED ARCS: DEFINITIONS AND PROPERTIES

This section provides the mathematical formulation of the definition and properties of watershed points, watershed arcs in hierarchical segmentation with the support of easyto-understand illustrations.

Modified Definition of Watershed Points

A path π p0,p1,...,p (l-1) ,p l in G is called a non-decreasing path (or non-increasing path

) if I pi-1 ≤ I pi (or I pi-1 ≥ I pi ) ∀i ∈ [1, l]. A non-decreasing path π 1 = (p 1 0 , p 1 1 , ..., p 1 k-1 , p 1 k
) and a non-increasing path π 2 = (p 2 0 , p 2 1 , ..., p 2 (l-1) , p 2 l ) can be concatenated to form a path with sequence of points

(p 1 0 , p 1 1 , ..., p 1 k-1 , p 1 k , p 2 0 , p 2 1 , ..., p 2 (l-1) , p 2 l ) if p 2 0 ∈ N p 1 k and is denoted by π 1 .π 2 . If π = π 1 .π 2 we will call π a non- decreasing-non-increasing path (nDnI-path).
Let, M IN is the set of all regional minima and nDnI Π =

{π M1⇝M2 } where M 1 , M 2 ∈ M IN and π M1⇝M2 is a nDnI- path. Let M = {p : p ∈ π M1⇝M2 such that ∀π M1⇝M2 ∈ nDnI Π, ∄q ∈ V π M 1 ⇝M 2 such that I q > I p }, i.e, M
is the set of pixels having maximum values on the distinct nDnIpaths between any two regional minima.

Definition 2. The smallest subset W ⊆ M are the watershed points if ∀w 1 ∈ W, ∀w 2 ∈ M \ W, I w1 ≤ I w2 and ∀π ∈ nDnI Π, ∃w ∈ V π such that w ∈ W .
For each path π p,...,q,w,r,...,s where p ∈ M 1 , s ∈ M 2 , if w is a watershed-point, then all the points in the sequence (p, ..., q) is in the basin extension from M 1 and all the points in the sequence (r, ..., s) is in the basin extension from M 2 .

Note that, in this construction there may exist some neighbor basin points having higher pixel value than the watershed points, which differs from the general idea of classical approach to watershed transformation following the water-droplet principle (see Fig. 3b). The idea of this construction is to ensure the existence of a minimal set of watershed points which if removed, different basins get disconnected.

Each regional minima is marked with different label and each basin points associated with a regional minima is marked with same label. We denote the set of watershed points by W and set of basin points by B (W ∪ B = V and W ∩ B = ϕ). The set of watershed points and basin points which are neighbor of a vertex u are denoted by

N W u and N B u respectively (N W u ∪ N B u = N u ). Property 1. If u ∈ B, then ∀v ∈ N B u , L u = L v proof: Let v ∈ N B u = N u \ N W u and L u ̸ = L v .
That means, u and v are extended from two different regional minimas M 1 and M 2 respectively, i.e., u and v belongs to different basins, say B 1 and B 2 . As for two different basins ∄p ∈ B 1 , q ∈ B 2 such that q / ∈ N p and p / ∈ N q , no such v can exist. Hence,

L u = L v . Property 2. If w ∈ W , then i. w / ∈ M IN (set of all regional minimas) ii. ∃x, y ∈ N B w such that, L (x) ̸ = L (y), i.e, | U N IQU E L (N B w )| ≥ 2 iii. |W | < |V | proof: i.
Let w is a watershed point between two basin extensions B 1 and B 2 from two regional minima M 1 and

M 2 respectively, M 1 , M 2 ∈ M IN , i.e, ∃π M1⇝M2 ∈ nDnI Π and w ∈ V π M 1 ⇝M 2 such that ∀p ∈ V π M 1 ⇝M 2 , I w ≥ I p . Let w ∈ M 1 , that means, ∀m ∈ M 1 , I w = I m . But, that constitutes a non-decreasing path from M 2 to M 1 which contradicts the existence of watershed point w. Corollarily I w > I m , ∀m ∈ M 1 , M 2 .
ii. Let for two regional minima

M 1 , M 2 ∈ M IN , ∃π M1⇝M2 ∈ nDnI Π such that w ∈ V π M 1 ⇝M 2 . From above w / ∈ M 1 , M 2 and ∀v ∈ V π M 1 ⇝M 2 , v ̸ = w, v ∈ B.
We know, for any two distinct basin B 1 and B 2 (say

M 1 ⊆ B 1 , M 2 ⊆ B 2 ) L (B 1 ) ̸ = L (B 2 ). As M 1 , M 2 ̸ = ϕ, ∃q, r ∈ N B
w on the path π p,...,q,w,r,...,s such that L q ̸ = L r . Also, w may be a watershed point on more than one such path connecting different set of regional minimas. Hence,

| U N IQU E L (N B w )| ≥ 2.
iii. From properties i. and ii. it can be concluded that

B ̸ = ϕ. As W ∪ B = V and W ∩ B = ϕ, surely |W | < |V |.
This property ensures the termination of the iterations in the proposed hierarchical segmentation algorithm.

Let B ext be the set of basin-extensions from set of regional minimas in M IN (i.e., B∈Bext ∪B = B and

∀B 1 , B 2 ∈ B ext , B 1 ̸ = B 2 , B 1 ∩ B 2 = ϕ). Two basins B 1 , B 2 ∈ B ext are called neighbor-basins if ∃w ∈ W such that ∃b 1 ∈ B 1 , b 2 ∈ B 2 where {b 1 , b 2 } ⊆ N B
w . This {B 1 , B 2 } forms an unordered neighbor-basin pair which is associated with the watershed point w. The set of all such neighborbasin pairs are denoted by B pairs and the set of neighborbasin pairs associated with w is denoted by w Bpairs . The set of basins neighbor to watershed point w ∈ W is denoted by w basins , i.e, w basins = {B : ∀{B, B ′ } ∈ w Bpairs }. Corollarily ∀B ∈ w basins , ∃b ∈ B such that w ∈ N b . For a basin B, the set of watershed points neighbor to it is denoted by B wsheds and the set of basins neighbor to it is denoted by B basins .

Property 3. In a graph G , if W ̸ = ϕ, then ∀w ∈ W , ∃W ′ ⊆ W such that, W ′ is a maximal vertex-cut in G and w ∈ W ′ proof: Let B basins = {B 1 , B 2 , .
.., B k } be the basinneighbors of a basin B. Let, B W Bi be the watershed points between B and B i for all i ∈ 1 to k. B wsheds = k i=1 ∪ B W Bi , clearly B wsheds ⊆ W . Let w is a watershed point between B and B i for some i ∈ 1 to k, i.e., w ∈ B wsheds . Now we will show that B wsheds is a vertex-cut. Suppose B wsheds is not a vertex-cut. Then G \ B wsheds must be connected, i,e., there exists a path between B and G \ B \B. Let this path be π m,...,mi where m ∈ M and m i ∈ M i , M and M i being the regional minima of basins B and B i respectively (B i ⊆ G \ B wsheds \ B). By the definition of watershed points, there exists a watershed point on such path π m,...,mi . But any watershed point w on a path between B and B i satisfies w ∈ B W Bi ∈ B wsheds . This is a contradiction. That means no path can exist between B and G \ B wsheds \ B, i.e., B wsheds is a vertex-cut. Now we will prove B wsheds is a maximal vertex-cut. suppose B wsheds is not maximal. That implies ∃B wsheds ′ ⊂ B wsheds which is a vertex-cut. Let w ∈ B wsheds \ B wsheds ′ . By definition of B wsheds , w is a watershed point. Suppose w is a watershed point between B and B i for some i ∈ 1 to k. That implies there exists a path π m,...,n,w,ni...,mi between basins B and B i where m ∈ M and m i ∈ M i , M and M i being the regional minima of basins B and B i respectively, and the points in the sequence m, ..., n is part of basin B and the points in the sequence n i , ..., m i is part of basin B i . That implies there exists a path between B and G \ B wsheds ′ \ B, which means B wsheds ′ is not a vertexcut. This is a contradiction, i.e., there cannot exist any such vertex-cut B wsheds ′ ⊂ B wsheds . So B wsheds is a maximal vertex-cut.

Corollarily it can be shown that the whole set of watershed-points W is always a maximal vertex-cut.

Watershed Arcs

In a directed graph the edges are termed arcs, not to be confused with watershed arcs which are essentially the set of watershed points having the same neighbor-basin pair. In this study, arcs and watershed arcs are used unambiguously. Definition 3. The set of watershed arcs is defined by

{{w : B 1 , B 2 ∈ w basins }∀{B 1 , B 2 } ∈ B pairs }.
The set of watershed arcs is denoted by W ARC . Each watershed-arc in W ARC is associated with a unique basinpair in B pairs . For A ∈ W ARC , that basin-pair the arc A is associated with, is denoted by A basin pair ; and for a neighbor-basin pair {B

= ϕ. As ∀w ∈ W , |w basins | ≥ 2 clearly A∈W ARC ∪A = W .
From this, similar to property 3 it can be proved that,

∀A ∈ W ARC , ∃W ARC ′ ⊆ W ARC , such that, A ′ ∈W ARC ′ ∪A ′ is a maximal vertex-cut in G and A ∈ W ARC ′ .

Removal of a Watershed Arc

Let A ∈ W ARC and A basin pair = {B 1 , B 2 }, where

B 1 , B 2 ∈ B ext . Let A ′ ⊆ A such that ∀a ∈ A ′ , a arc = {A}.
If A is removed following are the main updates to be performed.

i. A new basin

B = {B 1 ∪ B 2 ∪ A ′ } is formed if A ′ = ϕ,
} : A 1 = arc {B1,B ′ } , A 2 = arc {B2,B ′ } , ∀B ′ ∈ B ext
′ } gets merged to form single arcs between B and basins in

B ext ′ . b. Let w ∈ (N W w ′ \ A) such that w ′ ∈ A ′ .
As w ′ becomes a basin point in B, new arcs are created between B and all the basins in (w basins \ (B

1 basins ∪ B 2 basins )). c. Let w ∈ (N W w ′ \ A) such that w ′ ∈ A ′ . If ∃arc {B,B ′ } such that B ′ ∈
( rem A B ext , rem A W , rem A B pairs , rem A W ARC ).
The algorithm for the operation

REM A , A ∈ W ARC is given below. Require: B ext , W , B pairs , W ARC , A Ensure: rem {A} B ext , rem {A} W , rem {A} B pairs , rem {A} W ARC 1: A ′ ← {a : ∀a ∈ A, a arc = {A}} 2: if A ′ == ϕ then 3: rem {A} B ext ← B ext , rem {A} W ← W , rem {A} B pairs ← (B pairs \ {A basin pair }), rem {A} W ARC ← (W ARC \ {A}) 4: else 5: {B 1 , B 2 } ← A basin pair , B ← {B 1 ∪ B 2 ∪ A ′ } 6: rem {A} B ext ← (B ext \ {B 1 , B 2 }) ∪ {B}, rem {A} W ← (W \ A ′ ), rem {A} B pairs ← (B pairs \ {{B 1 , B 2 }}), rem {A} W ARC ← (W ARC \ {A}) 7: for all B ′ ∈ (B 1 basins ∩ B 2 basins ) do 8: rem {A} B pairs .remove({B ′ , B 1 }, {B ′ , B 2 }), rem {A} B pairs .append({B, B ′ }), 9: arc {B,B ′ } ← arc {B1,B ′ } ∪ arc {B2,B ′ } 10: rem {A} W ARC .remove(arc {B1,B ′ } , arc {B2,B ′ } ), rem {A} W ARC .
for all w ∈ (N W w ′ \ A), ∀w ′ ∈ A ′ do 18:
for all B ′ ∈ w basins do

19: if {B, B ′ } / ∈ rem {A} B pairs then ▷ B ′ ∈ (w basins \ (B 1 basins ∪ B 2 basins )) 20:
rem {A} B pairs .append({B, B ′ })

4. Let A ⊆ W ARC is a set of n number of arcs. Let ∀A ∈ A , ∃A ′ ⊆ A such that ∀a ∈ A ′ , a arc = {A} and A ′ ̸ = ϕ. Let REM A (B ext , W , W ARC ) is a valid operation. i. If |B ext | = k, then, | rem A B ext | = k -n ii. If | rem A W | ≥ 1, then, rem A W is a maximal vertex-cut.
proof: i. If an arc A ∈ A is removed, the two basins in A basin pair is merged to a new basin, and no other new basin is formed. So, removing each arc reduces the number of basins by 1. Hence, the statement is proved. Proof of this statement eventually ensures the convergence of proposed algorithm.

ii. If an arc A ∈ A is removed, only the watershed points which are not part of any arcs other than A gets merged into the newly formed basin, and no new watershed points are formed (though, some existing points may form new watershed arcs). From property 3 we see, W is a maximal vertexcut. Removal of only those watershed points which were only separating the basins in A basin pair ensures that the remaining watershed points (i.e., rem A W ) form a maximal vertex-cut.

Algorithm for Hierarchical Partitioning by Watershed Arc Removal

We will now introduce the notion of hierarchical segmentation by removing watershed arcs with the terminologies defined before. In proposed method, first, at initial level (l = 0), from a node-weighted graph G (0) , the set of watershed points W (0) and the set of watershed arcs W ARC (0)

and the set of saddle-points S (0) are determined. Then from S (0) the graph for next level

G 1 = (V ′ , E ′ , I ′ ) is created such that V ′ = S (0) , E ′ = {(p,
q) : p, q ∈ S (0) , p basin pair (0) ∩ q basin pair (0) ̸ = ϕ} and I ′ = {I s : s ∈ S (0) }. Note that, in this construction if a point is saddle-point for more than one arcs, duplicate points are created in G (l+1) corresponding to each of the arcs (see Fig. 3). Then watershed-points for next level (l = 1), W 1 is determined from G 1 . Clearly, W 1 ⊂ S (0) . Then, the corresponding arcs of the points from the set S (0) \ W 1 is removed to get the watershed arcs of level 1, W ARC 1 . From W ARC 1 in the same way G 2 is formed, This process goes on till some level l in which W (l) = ϕ.

A∈W ARC (l)

∪A gives the partition points between different basins at level l, which is denoted by P (l) . The partition points can be inserted to any of the neighboring basins by some particular way to generate segmentation at each level. For image segmentation a grid graph is generally considered at the initial level (l = 0).

Following is the outline of the algorithm to get the hierarchical partitions/vertex-cuts. Require: V , I , N Ensure: Set of partitions P 1: W (0) ← Get W Spoints(V , I , N ) 2: Determine W ARC (0) , S (0) , B pairs (0) 3: P.append(P (0) ) 4: l ← 1 5: while T RU E do 6: W ARC (l) , S (l) , B pairs (l) ← Remove Arcs({w arc : ∀w ∈ (S (l-1) \ W (l) )})

N (l) = Get N eighborhood(S (l-1) , B pairs (l-1) ) 7: W (l) ← Get W Spoints(S (l-1) , I (l) , N (l) ) 8: if |W (l) | == 0 then 9:

12:

P.append(P (l) )

13: l ← l + 1 14: end while By the construction of G (l+1) , s 1 is connected to only the points in (S ∪ S 1 ) \ {s 1 }, s 2 is connected to the points in (S∪S 2 )\{s 2 } and s 12 is connected to the points in (S 1 ∪S 2 )\ {s 12 }. If s 1 ∈ W (l+1) , there must exist two points, say p, q ∈ (S ∪ S 1 ) \ {s 1 }, such that, p, q / ∈ W (l+1) and ∀π p⇝q , ∃w ∈ V π p⇝q , V π p⇝q ⊆ V (l+1) , w ∈ W (l+1) . But, clearly ∃π p⇝q : V π p⇝q = {p, s 12 , s 2 , q} =⇒ V π p⇝q ∩ W (l+1) = ϕ, which is a contradiction. Hence, in G (l+1) either both s 1 and s 2 are watershed-points or both are not.

Property 5. Let B 1 , B 2 ∈ B ext(l) such that {B 1 , B 2 } ∈ B pairs (l) . If W (l+1) ̸ = ϕ, then (B ext(l+1) ) c ∩ {B 1 , B 2 } ̸ = ϕ. proof: Let (B 1basins \ B 2 ) = {B 1 1 , B

Hierarchical Segmentation from Partitions

Let B ext(l) is the set of basins and W ARC (l) is the set of watershed arcs at level l. By definition, ∀B i , B j ∈ B ext(l) , i ̸ = j, B i ∩ B j = ϕ. If B ext(l) is extended in the way B ′ = {{B ∪ w} : B ∈ w basins ∀w ∈ P (l) }}, then B∈B ′ ∪B = V and ∀B i , B j ∈ B ′ , i ̸ = j, B i ∩ B j = ϕ. Thus, B ′ becomes a segmentation at level l. We denote the segmentation at level l by S (l) .

proposed algorithm preserves definition 1 : Let, B ext(l) and B ext(l+1) are the set of basins at level l and (l + 1) respectively. Let B is a basin in B ext(l) which is not merged with any other basin at level (l + 1). So, for B there exists a basin

B ′ in B ext(l+1) such that B ⊆ B ′ (in this case B = B ′ ). Let, k number of basins B 1 , B 2 , ..., B k ∈ B ext(l) are merged at level (l + 1) to form a basin B ′ ∈ B ext(l+1) . Here, by definition, (B 1 ∪ B 2 ∪ ... ∪ B k ) ⊂ B ′ . That concludes, ∀B ∈ B ext(l) , ∃B ′ ∈ B ext(l+1) , such that, B ⊆ B ′ .
By definition P (l+1) ⊂ P (l) , and (P (l) \ P (l+1) ) ⊂ B (l+1) . Let S (l) is created by extending the basins in B ext(l) in such way that, ∀w ∈ (P (l) \ P (l+1) ), if w ∈ B ′ where B ′ ∈ B ext(l+1) , and

({w} ∪ B) ∈ S (l) where B ∈ B ext(l) , then, B ⊂ B ′ . Hence, if u ∈ S a (l) , v ∈ S b (l) and u, v ∈ S c (l+1)
then S a (l) , S b (l) ⊆ S c (l+1) . Let, S (l) and S (l+1) are two consecutive segmentation in a sequence of segmentations H . By induction, H is a hierarchical segmentation.

IMPLEMENTATION

This section includes the necessary specifics for implementing the proposed method to generate hierarchical segmentation for an image defined on a digital grid with 8connectivity. Particularly we will discuss about detecting the watershed points, generating the graphs for higher levels and the operation of removing an arc, as are defined and discussed in section 3, in the context of an image.

Generating Watershed Points

A 1) and that of push operation as O(log 2 m) where m is the current number of queues in the DHQ.

Use of DHQ (in some literature being termed as an ordered queue or ordered priority queue) to generate classical watershed transformation was first proposed by Beucher et al. [START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF]. In [START_REF] Beucher | Hierarchical Queues: general description and implementation in MAMBA Image library[END_REF] the authors provided an optimized implementation of hierarchical queues to generate watersheds. The image foresting transform (IFT), studied in [START_REF] Falcao | The image foresting transform: theory, algorithms, and applications[END_REF], is a connectivity-based method to construct various image processing operators. In [START_REF] Lotufo | The ordered queue and the optimality of the watershed approaches[END_REF] authors implemented IFT using ordered queue, and in [START_REF] Lotufo | IFT-watershed from gray-scale marker[END_REF] IFT was used to generate the watershed of an image via reconstruction from a marker image. The proposed watershed transformation method is inspired by the method proposed in [START_REF] Lotufo | IFT-watershed from gray-scale marker[END_REF]. Input: V , I , N Output: labelmap, watershed points 1: initialize empty dynamic hierarchical queue Q 2: for all v ∈ V do 3: end for 25:

W atershed.v ← F alse Shif ted.v ← F alse V isited.v ← F alse Label.v ← v DHQ P U SH(Q, v, I v +
V isited.p ← T rue 26:

end if 27: end while In the initialization step, each point is pushed into the DHQ with a priority value one greater than its pixel value. Next, the DHQ is popped in such a way that, if a popped point was assigned a greater priority than its pixel value, the point is pushed again in the DHQ with a priority value same as its pixel value; and if a popped point has the same priority as its pixel value, its neighbors are traversed. This strategy ensures the non-minima point can only be traversed from a neighbor point with a lower pixel value, and hence, the non-minima points of a pixel level will be traversed before than minima points of the same level.

When a point is traversed from one of its lower neighbors first time, it is marked as shif ted, and if the point is traversed from another lower neighbor again, it is marked as a watershed. As from a point only its higher neighbors are traversed, this ensures, that each watershed marked point must lie on atleast one nDnI-path on which no other points are marked as watershed and on each nDnI-path there exists atleast one point marked as a watershed. If a point is marked as visited once, it's neighbors are not traversed from it. If a point is marked as watershed, it is as well marked as visited. This ensures the minimality of the watershed points.

As neighbors of a watershed marked point is not traversed from it, there may exist some watershed marked point having higher neighbor basin points.

Generating Graph for Next Level

The nodes in the graph of the next level are formed by each saddle point in the current level. Each saddle point is associated with a pixel value since it has a direct mapping to the pixels of the input image. The next-level graph's neighborhood structure, i.e., the graph's edges, is defined in such a way that a saddle point is connected to all other saddle points that share a common basin. A data structure bucket is built to get the neighbor points of a point in the next level, which is effectively a list of basin-labels indexed by distinct basin-labels. Each list includes the labels of the neighbor basins of the basin, whose label the list is indexed by.

Input

x = (buckets[L (B 1 )] ∪ buckets[L (B 2 )]) \ {x} where {B 1 , B 2 } = x basin pair .

Removing a sequence of arcs

Removing an arc, as described in section 3, may delete some of the existing arcs, create new arcs, or join some existing arcs. For a general input graph, all the points on the arc being removed are to be examined. But, if the initial graph is a grid-graph 8-connectivity, only the end-points in the arc being deleted is needed to be considered, which reduces the computational time of the proposed hierarchical segmentation algorithm to a linear time (analyzed in detail in section 5.1). Lemma 1. If the G (0) is a grid-graph with 8-connectivity, then ∀A ∈ W ARC (l) , there exists a set of 4-connected paths proofs are in appendix.

Π A , such that, π∈Π A ∪V π = A and V πi ∩ V πj = ϕ and ∄u ∈ V πi , v ∈ V πj : u ∈ N v ∀π i , π j ∈ Π A , (i ̸ = j). Lemma 2. If the x and y are the end-points on π ∈ Π A , then ∀p ∈ (V π \ {x, y}) i. p arc = {A}. ii. ∄w ∈ N W p , such that, p basin pair ∩ w basin pair = ϕ Lemma 3. Let ∃p ∈ (N W x ∩ V π ), such that, p arc = {A}. Let to merge = {{A ′ , A ′′ } : A ′ , A ′′ ∈ (x arc \ {A}), such that, ∀A i , A j ∈ {A, A ′ , A ′′ }, A i ̸ = A j , A ibasin
According to these lemmas, each arc in an 8-connected grid forms a set of paths (or a single path), and the endpoints on those paths are possible junction points with another arc or neighbours to end-points of other arcs. Other arcs are extended, merged, or remain unchanged, depending on conditions. Hence, while generating the watershed arcs at a initial level, the corresponding end-points also are needed to be detected. While removing a set of arcs, removing one arc present in the set may change the structure of other arcs present in the set as stated before. To encounter this, in the following function, valid and invalid flags are assigned with the arcs being removed.

to merge ← {{A ′ , A ′′ } : A ′ , A ′′ ∈ (x arc \ {A}) such that, ∀A i , A j ∈ {A, A ′ , A ′′ }, A i ̸ = A j , A ibasin pair ∩ A j basin pair ̸ = ϕ} 7: to extend ← {{A ′ , p} : p, n ∈ N W x , A ′ ∈ n arc such that, x arc ∩ n arc = ϕ,
x basin pair ∩ n basin pair ̸ = ϕ, x basin pair ∩ p basin pair = ϕ} 8:

∀{A ′ , p} ∈ to extend, A ′ .append(p) A .append(new arc) end for 18: end function Note that, while removing an arc more than one end-points of it can be associated with a same pair of existing arcs to be merged, hence, unlike the extension of arcs, the merging is performed separately after all such arc-pairs are detected.

ANALYSIS OF THE PROPOSED ALGORITHM

In this section we examine of the run-time complexity of the proposed watershed arcs removal method for hierarchical segmentation, followed by a a comparative discussion of the working analogy of the proposed method and the waterfall algorithm, and show a comparison of run-time between watershed arcs removal and some of the other segmentation methods in literature.

Time Complexity

The run-time complexity of the proposed algorithm is highly dependent on the initial graph structure. To examine the run-time complexity in this study, owing to the implementation mainly on the images, we will consider the initial graph structure as a grid-graph. As described in 4.3 the computational time of an arc removal operation depends on the number of end-points present in the arc. As each connected part in an arc contains exactly two end-points, the computational time of removing an arc containing k number of connected parts is same as removing k number of arcs with single parts. Considering arc with k number of parts as k number of different connected arcs does not change the worst run-time complexity. For simplicity, in the illustrated example to determine the the run-time complexity of the proposed hierarchical segmentation method we consider each arc having a single part.

At the initial level the watershed arcs are determined from the watershed points, the run-time needed is directly proportional to the number of watershed points determined at the initial level, as all the points marked as 'watershed' is needed to be checked. The operation of removing a single arc having single part takes constant run-time; the number of arcs being removed at each level is proportional to the number arcs in the previous level. Generating neighborhood structure to build the graph for next level is proportional to the number of arcs at the current level. So, intuitively, the worst running time happens if most number watershed arcs are created in the initial level and most number watershed arcs are retained in the next levels, that is, the highest number of basins formed at the initial level and the least number of merging occurs at the next levels.

The highest number of basins are formed if each basin is of minimum size. Also, property 5 consider the fact that there cannot exist two basins, which are neighbor to each other, cannot remain unmerged to any of their neighbor basins. Thus, minimum merges happen if each basin gets merged with only one of its neighbors. So, in each level number of basins are reduced to at-least half of the previous level.

Consider the number of pixels/nodes in the input image is n. Now, for a grid-graph with 8-connectivity, discarding the anomaly at the perimeters of the image, the maximum number of basin points are almost n 4 (points in alternate rows of alternate columns are basin-points), each basin being of 1-pixel in size; and the number of watershed points is almost 3n 4 forming n number of arcs (a watershed-point in each of alternate rows of alternate columns is associated with 4 unique arcs, neighbor watershed-points of it are in any of these arcs) [see Fig 6a]. In the next level, to simplify the calculation, consider the merging of basins occurs like Fig. 6b; the formation provided in Fig. 6c shows the number of basins and watershed arcs formed after merging is similar to the basins and watershed arcs formed at the initial level if the input image is of size n 2 (consider from each 4 consecutive columns in 6b, 2 columns are kept in 6c). So, the number of arcs after merging becomes n 2 , i.e., n 2 number of arcs get removed. This ensures the fact that, after each level, number of remaining arc is half of previous level. The process continues until at some level number of remaining arc is 1.

To determine the watershed-points among n nodes, each point is inserted exactly twice in the hierarchical queue. The watershed transformation method presented here uses a dynamic hierarchical queue, which takes O(log 2 M ) time to insert an element, rather, with pre-knowledge of the image domain a fixed shape hierarchical queue can be used to get constant time complexity for inserting operation. It's also worth mentioning that, for the purpose of image partitioning, a graph-structure considering only the edges from lower valued pixels to higher valued pixels reduces the run-time even further. Fig. 7 shows a comparison of run-time on simulated images of different sizes between the proposed algorithm with the hierarchical clustering methods, such as Ward's method of agglomerative clustering [START_REF] Jr | Hierarchical grouping to optimize an objective function[END_REF], and weighted linkage method [START_REF] Daniel | Modern hierarchical, agglomerative clustering algorithms[END_REF] (for both run-time complexity is O(n 2 )), the proposed algorithm is the fastest among the , the fast implementation of waterfall algorithm (run-time complexity is O(n)) [START_REF] Marcotegui | Fast implementation of waterfall based on graphs[END_REF], as well as, a distance-based clustering method Iterated Watershed (IW) [START_REF] Soor | Iterated watersheds, a connected variation of k-means for clustering gis data[END_REF] which is essentially the connected variation of k-means clustering method [START_REF] Soor | Extending k-means to preserve spatial connectivity[END_REF], and morphological snake based image segmentation method, Morphological Active Contours without Edges (MorphACWE) [START_REF] Marquez-Neila | A morphological approach to curvature-based evolution of curves and surfaces[END_REF]. As can be seen in the figure, the proposed algorithm, Watershed arcs removal, works the fastest.

Comparison with Waterfall Algorithm

The waterfall algorithm is a well-known technique in the field of mathematical morphology that was developed to address the problem of over segmentation present in the classical Watershed transformation. In each level of the waterfall algorithm, the entire image is reconstructed from the watershed points detected in the previous level. Although it provides a more accurate way of basin-merging, as a downside of this technique it is possible to argue that, in a grey-scale image it takes a longer time to reconstruct all of the little depressions present in the image, hence producing numerous number of levels. Most of the levels have minor differences from one another, and determining which level provides the optimum segmentation is another existing challenge in the waterfall algorithm. On the other hand, the construction of watershed arcs as a true partition between neighbor segments automatically over-looks many small size depressions present in the image, by some points at the segmentation boundaries to be watershed points which would not be considered as the same in the classical approach. Furthermore, in each of the higher levels, rather than processing the whole image as in waterfall algorithm, only the graph constructed from the representatives of the arcs present in the previous level is processed, which reduces in size drastically in each level, resulting in a significantly shorter run-time.

Till now the proposed method is applied only on single band images, which for the purpose of object detection require a pre-processing step to generate a gradient image, similar to the waterfall algorithm.

EXPERIMENTAL RESULTS

In this section, first the application of proposed algorithm to extract hierarchical river-basins from a Digital Elevation Model (DEM) data is shown. Next the performance evaluation of the algorithm is done in the objective of image segmentation. Figure . 5 shows an example of hierarchical partitioning by the proposed method, Watershed arcs Removal. The code and results are available at [START_REF] Soor | Watershed arcs[END_REF].

Extracting Hierarchical River-basins

Uttarakhand is a state in northern India at the foot of the Himalayas that is the source of many major rivers in the Bhabar region, including the Ganga and Yamuna. In the previous decade, the state has experienced multiple disastrous floods each of which startled residents with the magnitude of their impact. To reduce the impact of natural disasters, it is necessary to identify river basins to estimate the spread of the disaster. Partitioning the DEM in a hierarchical manner via the proposed watersherd arcs provides insights to the geodynamicists and geographical information science researches. In Figure 8 the hierarchy of the river-basins in this region is provided.

Shuttle Radar Topography Mission (SRTM) available by USGS furnishes high-resolution digital topographic database of Earth provided in mosaiced 5x5 degree tiles [START_REF]Earth Explorer Interface and Product Documentation[END_REF]. The DEM is digitized and clipped with a boundary vector file, then the river and tributaries shapefiles are overlayed in QGIS software [START_REF]QGIS Geographic Information System[END_REF] to generate the image in Figure 8a, where brighter grey-scale values depict higher normalised elevations. Figure 8b-8g shows level by level river-basins mapped by employing the proposed method. The rivers and their tributaries are readily observed in different coloured basins at higher levels.

Evaluation using image Segmentation

The Wiezmann segmentation evaluation database [START_REF] Alpert | image segmentation by probabilistic bottom-up aggregation and cue integration[END_REF] contains 1-and 2-object grey-scale images (100 each) that depict the objects deferring from its surroundings by intensity, texture and other attributes, as well as the ground-truth segmentations. The performance of the proposed method , where for each method the median values for each evaluation metric is given. In Figure 9 end-results of segmentation for some images from the Wiezmann dataset are shown. The evaluation metrics considered here are (i) F-measure for Boundaries (FB), which computes the morphological boundary F-measure, (ii) F-measure for Objects and Parts (FOP), which marks each result-segment as an object or a part and calculates F-measures over the segments putting weights on the count of the marks [START_REF] Pont | Supervised evaluation of image segmentation and object proposal techniques[END_REF], (iii) Adjusted Mutual Information (AMI), that calculates the mutual information adjusted to account for the chance. (iv) Adjusted Rand Index (ARI) that computes rand index adjusted to chance, [START_REF] Fahad | A survey of clustering algorithms for big data: Taxonomy and empirical analysis[END_REF]. To calculate FOP γ o , γ p and β are set to 0.75, 0.1, 0.5 respectively; that means, if a segment in the result image has atleast 75% overlap with the corresponding segment in the ground-truth, the segment is marked as a true segment, where as, if a segment having less than 10% overlap is considered as noise segment, β regulates the importance given on the part segments (10-75% overlap). As objects in an image is appeared to be a connected segment, FB and FOP together are two appropriate metrics which lowers the score if the result segmentation is too much fragmented.

For Watershed arcs Removal and Waterfall algorithm, a gradient image is generated by applying morphologicalopening (3x3 square SE), morphological-closing (5x5 di-amond SE), morphological gradient (5x5 square SE) (SE: Structuring Element) operations successively on the input image [START_REF] Erik | Efficient 2-d grayscale morphological transformations with arbitrary flat structuring elements[END_REF]. For Watershed arcs Removal the segmentation at the last or second last level is considered, whereas in the waterfall algorithm, the segmentation with the highest clustering accuracy [START_REF] Fahad | A survey of clustering algorithms for big data: Taxonomy and empirical analysis[END_REF] with ground-truth object is For linkage methods the number of cluster is set to 2. For MorphACWE 'checkerboard' level-set is considered with a number of iterations set to 250. For Iterated Watershed the number of cluster is set to 2 for 1-Object, 3 for 2-Object.

The proposed method, watershed arcs removal, detects the edges present in the image better to locate the object boundaries, yet it is not as accurate to detect the entire object in a single segment, as indicated by its comparatively high FB and somewhat lower FOP than the others. On the other hand, presence of numerous small segments in the results of waterfall algorithm reduced its FOP. By multiple experiments with different smoothing and gradient operations as preprocessing steps, it was observed that, performance of watershed arcs removal method in object detection is slightly depending on the operations being used. The result values presented in Table-1 can be summarized as, the Watershed arcs Removal method can yield image segments that are comparable to the other methods in terms of the used evaluation metrics, albeit the main benefit is in computational time.

be in A ′ and A ′′ respectively and (i+1,j) is in B 2 and (i-1,j+1) being another basin-point. In case1.1 and case1.2, the other remaining neighbors of (i,j), being at diagonal from it, cannot be part of any arc with (i,j). With similar argument to case1.2, case-2 also the same. So, maximum one arc-pair {A ′ , A ′′ } can exist in to merge.

Let x is at (i,j), p is at (i,j-1) and point (i-1,j-1) is in basin B 1 . Let, n is at (i-1,j). To be x arc ∩ n arc = ϕ and x basin pair ∩ n basin pair ̸ = ϕ}, both (i-1,j+1) and (i,j+1) must be watershed points, which deduces the fact that, each of (i,j), (i-1,j), (i-1,j+1) and (i,j+1) must be in different arcs, more specifically, {(i-1,j),(i-2,j)}, {(i-1,j+1),(i-1,j+2)} and {(i,j+1),(i+1,j+1)} constitute the other arcs, say A ′ , A ′′ and A ′′′ respectively; and (i-2,j+1),(i,j+2) and (i+1,j) must be basin-points. No other construction is possible with such n to exist. So we see, if such n exists, there exists two arcs A ′ and A ′′ which have common basin-neighbor with A, thus, constitutes to extend. In this orientation the point at (i-1,j+1) is the extension point.

Evidently the above two constructions around x cannot exist simultanuously, hence, if |to merge| > 0, then to extend = 0 and vice-versa.

Fig. 1 .

 1 Fig. 1. A synthetic 1-dimensional input image is shown in first column (a), (d). Top row: Hierarchical segmentation by waterfall algorithm at (a) level 0 (b) level 1 (c) level 2; Thick line represents operated image in a level, watershed points are marked by dashed lines, gray-coloured area represents morphological reconstructed portion of the image in previous level. Bottom row: Hierarchical segmentation by proposed algorithm at (d) level 0 (e) level 1 (f) level 2; black marked points are watershed/saddle points generated from watershed transformation on previous level, dash-dotted lines indicate the new neighbourhood of the points

Fig. 2 .

 2 Fig. 2. (a): A grey-scale image with 4-connected neighborhood, pixels are symbolized by rings, pixel-values are written within it; (b) Watershed Transform by Vincent-Sollie Method, (c): Watershed Transform by proposed method; In (b) and (c) 'W' marked pixels are watershed points, 'A' and 'B' marked pixels are different basin points.

Definition 4 .

 4 A Saddle-point p ∈ A on a watershed-arc A ∈ W ARC is defined by p : ∄q ∈ A, I q < I p .The set of saddle-points in graph G has a bijective relation with B pairs and is denoted by S . If p is a saddle-point on arc A, p arc indicates the arc A. The saddle-point between a neighbor-basin pair {B 1 , B 2 } ∈ B pairs , is denoted by saddle {B1,B2} .

Fig. 3 .

 3 Fig. 3. (a) A simulated single-band input image (b) Watershed transformation at level = 0 on the grid-graph with 8-connectivity, watershed points are marked in red colour, different watershed-arcs are encircled by different colours (c) Image partition at level = 0 (d) Generated graph at level = 1, nodes are the saddle points of different arcs in level = 0 and given the same colour as the arcs (e) Watershed transformation on the generated graph in d, red coloured points are watershed points at level = 1 (f) Image partition at level = 1 after removing the corresponding arcs of the non-watershed points in (e) (g) Generated graph at level = 2 (h) Watershed transformation on the graph in (g) (i) Image partition at level = 2, the final level partition as no watershed point is generated in the graph of next level

Fig. 4 .

 4 Fig. 4. Three cases of arc removal operation in a 8-connected gridgraph. Top-row: before removing the arc 'A', Bottom-row: after removing the arc 'A'. (a) arcs 'B', 'C' and 'D' are unchanged, arcs 'E' and 'F' are either merged with arc 'C' and 'D' respectively or are selected to be removed along with 'A', (b) arcs 'B' and 'C' are merged to a new arc 'D', (c) arcs 'C' and 'D' are extended

  pair ∩ A j basin pair ̸ = ϕ} and to extend = {A ′ : A ′ ∈ n arc where n ∈ N W x such that, x arc ∩ n arc = ϕ and x basin pair ∩ n basin pair ̸ = ϕ}. i. |to merge| = 0 or 1. ii. |to extend| = 0 or 2. iii. At-least one of |to merge| and |to extend| is 0.

1 : 5 :

 15 function REMOVE ARCS(A ) 2: initialize arcStatus[A] ← 'valid', ∀A ∈ A 3: while A is not empty do 4: A = A .pop(0) if arcStatus[A] == 'valid' then for all x ∈ A.endpoints do 3: if ∄p ∈ (N W x ∩ A), such that, p arc = {A} then

10 :

 10 for all arc pair ∈ to merge do11: new arc ← M ERGE(arc pair) 12: if ∃A ′ ∈ arc pair such that, arcStatus[A ′ ] == 'valid' then 13: arcStatus[new arc] ← 'valid' ▷ from Property 6 14:

Fig. 5 . 16 :

 516 Fig. 5. An example of hierarchical partitioning by proposed method. (a) Original image, (b) Gradient Image, (c) to (g) hierarchical partitioning at level 0 (initial level) to 4 (final level)

Fig. 6 .

 6 Fig. 6. (a), (b) Watershed arcs at level 0 and level 1; (c) the points in merged basins and arcs in level 1 can be considered as single points. White coloured points are basin-points and dark points are watershedpoints. Each watershed-arc is encircled distinctly.

Fig. 7 .

 7 Fig. 7. Comparison of run-time between different clustering approaches. Experiments carried on a Intel E5-1650 v3 Processor with 32GB RAM. Python 3.7 is used for coding.

Fig. 8 .Fig. 9 .

 89 Fig. 8. (a) The gray-scale image constructed from the DEM of Uttarakhand state of India. Major river-streams are marked in yellow colour. (b)-(g) hierarchical river-basins. Distinct basins are coloured differently.

  1 , B 2 } ∈ B pairs , the arc between them is denoted by arc {B1,B2} . For a basin B, the set of watershed arcs neighbor to it is denoted by B ARC . A watershed-point w ∈ W can be part of more than one arcs; the set of arcs in which w belongs to, is denoted by w ARC . Clearly B ARC , w ARC ⊆ W ARC . If v is a watershed-point on arc A, v ARC = A and v basin pair is the corresponding neighbor-basin pair. If v / ∈ W then, v ARC , v basin pair

  and the new set of watershed points become W \ A ′ . ii. If the new basin B is formed, a. Let, B ext ′ = (B 1 basins ∩B 2 basins ) is the set of common basin neighbours to B 1 and B 2 . The arc-pairs in {{A 1 , A 2

  w basins and w / ∈ arc {B,B ′ } , then w is appended to the arc arc {B,B ′ } . The operation of removing an arc A, REM A works on the quadruplet (B ext , W , B pairs , W ARC ) and is a valid operation if A ∈ W ARC . Removing a set of arcs A = {A 1 , A 2 , ..., A n } is defined by REM A (B ext , W , B pairs , W ARC ) = REM An (...(REM A2 (REM A1 (B ext , W , B pairs , W ARC )))...) which produces the quadruplet, say,

  append(arc {B,B ′ } ) ′ ∈ (B ′′ basins \ (B 1 basins ∩ B 2 basins ))whereB ′′ ∈ {B 1 , B 2 } do

	11:	end for
	12: for all B 13:
	16:	end for
	17:

rem {A} B pairs .remove({B ′ , B ′′ }), rem {A} B pairs .append({B, B ′ })

14: arc {B,B ′ } ← arc {B ′ ,B ′′ } 15: rem {A} W ARC .remove(arc {B ′ ,B ′′ } ), rem {A} W ARC .append(arc {B,B ′ } )

end for 26: end for 27: end if Property

  {A} W ARC .append(arc {B,B ′ } ) arc {B,B ′ } ← arc {B,B ′ } ∪ {w}

	21:	initialize empty arc arc {B,B ′ }
	22:
	23:	end if
	24:
	25:

rem

  2 1 , ..., B m 1 } and (B 2basins \ B 1 ) = {B 1 2 , B 2 2 , ..., B n 2 }. Let s = saddle {B1,B2} and S 1 = {s i 1 : s i 1 = saddle {B1,B i 1 } where i = 1, 2, ..., m} and S 2 = {s i 2 : s i 2 = saddle {B1,B i 1 } where i = 1, 2, ..., n}. Clearly, S 1 ∩ S 2 = ϕ. As per the construction of G (l+1) stated above N s(l+1) = S 1 ∪S 2 . If s / ∈ W (l+1) , the basins B 1 and B 2 gets merged at level (l+1). If s ∈ W (l+1) , then from property 3.ii., there exists at-least two points in ∃s 1 , s 2 ∈ N s(l+1) such that s 1 , s 2 / ∈ W (l+1) . At level (l + 1), the both the neighborbasin pairs in s 1basin pair and s 2basin pair gets merged. As (s 1 ∪ s 2 ) basin pair ∩ {B 1 , B 2 } ̸ = ϕ, both B 1 and B 2 cannot be in B ext(l+1) , i.e., atmost one of two neighbor-basins B 1 and B 2 can remain unmerged to any of its neighbors in level (l + 1). This ensures |B ext(l) | < |B ext(l+1) , which in- turn ensures the convergence of the proposed hierarchical segmentation algorithm. Let B, B 1 , B 2 ∈ B ext(l) , such that, arc {B1,B2} , arc {B,B1} , arc {B,B2} ∈ W ARC (l) . Let s 12 , s 1 , s 2 are saddle-points on arc {B1,B2} , arc {B,B1} , arc {B,B2} respectively. If s 12 / ∈ W (l+1) , then, either {s 1 , s 2 } ⊆ W (l+1) or {s 1 , s 2 } ∩ W (l+1) = ϕ. Let s 1 ∈ W (l+1) and s 2 / ∈ W (l+1) . Let S, S 1 , S 2 are the set of saddle-points around basins B, B 1 , B 2 respectively.

	Property 6.

proof:

  dynamic hierarchical queue (DHQ) is a data structure that contains a collection of queues, each queue being associated with unique priority value. Any element pushed into this data structure, comes with a priority value and enters into the queue having the same priority, If the DHQ does not have any queue with the priority value of the incoming element, a new queue with that priority value is created. While popping from the DHQ, the queue with the least priority value is popped. After popping if the queue becomes empty, the queue is deleted from the DHQ. The term dynamic refers to the fact that the number of lists in the hierarchical queue is not fixed.

	end if
	Append element to L
	end function
	function DHQ POP(Q)
	Get list L with minimum priority value in Q
	Remove the first element element from L
	if L is empty then
	Remove L from Q
	end if
	return element, L.priority
	end function
	Using a min-heap data structure to store the priority values
	of the queues, gives the time complexity of pop operation
	as O(

function DHQ PUSH(Q, element, prio val) if ∄L ∈ Q such that L.priority = prio val then Create list L in Q such that L.priority = prio val else

Get list L such that L.priority = prio val

  1) 4: end for 5: while Q is not empty do Label.p and I n > I p then

	6:	p, prio ← DHQ P OP (Q)
	7:	if V isited.p is T rue then
	8:	continue
	9:	end if
	10:	if prio > I p then	▷ insert p again in Q
	11:	DHQ P U SH(Q, p, I p )
	12:	Shif ted.v ← T rue
	13:	else
	14:	for all n ∈ N p do
	15: if Label.n ̸ = 16: if Shif ted.n is T rue then
	17:	V isited.n ← T rue
	18:	W atershed.n ← T rue
	19:	else
	20:	DHQ P U SH(Q, n, I n )
	21:	Label.n ← Label.p
	22:	end if
	23:	end if
	24:

  : B pairs Output: buckets 1: Initialize empty buckets 2: for all (B 1 , B 2 ) ∈ B pairs do

	3:	if L (B 1 ) / ∈ buckets.indices then
	4:	create empty list buckets[L (B 1 )]
	5:	end if
	6:	if L (B 2 ) / ∈ buckets.indices then
	7:	create empty list buckets[L (B 2 )]
	8:	end if
	9:	buckets[L (B 1 )].append(L (B 2 ))
	10:	buckets[L (B 2 )].append(L (B 1 ))
	11: end for
	The neighborhood of a point x in next level can be generated
	by N

TABLE 1

 1 Evaluation on grey-scale images in Weizmann Data-set. For each method the median metric-scores are given. this database and compared with the results acquired by the methods mention in section 5.1. The comparison is shown in Table-1

		Method	FB	FOP AMI ARI
		Watershed arcs	0.337 0.509 0.335 0.244
		Removal
	1-Object	Waterfall Linkage Weighted	0.188 0.012 0.287 0.277 0.143 0.560 0.170 0.212
		Ward's	0.189 0.541 0.256 0.248
		Linkage
		MorphACWE	0.254 0.546 0.206 0.252
		Iterated	0.197 0.622 0.170 0.112
		Watershed
		Watershed arcs	0.462 0.545 0.433 0.399
		Removal
	2-Object	Waterfall Linkage Weighted	0.303 0.020 0.406 0.454 0.226 0.629 0.255 0.240
		Ward's	0.277 0.673 0.411 0.507
		Linkage
		MorphACWE	0.384 0.634 0.337 0.316
		Iterated	0.378 0.631 0.433 0.337
		Watershed
	is evaluated on

ACKNOWLEDGMENTS

S.S. is grateful to Indian Statistical Institute for providing the junior and senior research fellowship and to the Indo-Trento Programme for Advanced Research for the fellowship to visit RS Lab, University of Trento, Italy.

CONCLUSION AND FUTURE WORKS

In this study, as a morphological approach to hierarchical partition, we defined watershed arcs and applied it to extract hierarchical river-basins as well as for hierarchical image segmentation to generate convincing results. As the method is defined on a dataset having underlying connectivity, it is bound to produce connected segments, which is a prerequisite of shape-based object detection. The major strength of this proposed algorithm lies in reducing runtime significantly and generating more compact segments at each level. Here we shall discuss a few points regarding watershed arcs for further research.

i. Till now we generated watershed arcs in vertex weighted graphs and applied it only on single-band images. This study can be extended to generate hierarchical segmentation for multi-band images. For that, an algorithm to generate watershed arcs in an edgeweighted graph may be required. ii. We considered the initial graph structure with undirected edges, the study can be extended further to use the proposed method for the applications that requires a directed graph-structure. iii. The proposed algorithm's working base is independent of the values of the arcs' representatives (saddle-point pixel values), therefore fine-tuning it may produce better results. Also, the proposed hierarchical merging technique can be explored to incorporate with the edgedetection algorithms that do not generate disconnected segments.

APPENDIX PROOF OF LEMMA 1

Let (i,j) denotes the point at i-th row and j-th column of the grid-graph. For each watershed-point w in A there at-least exists two basin-points, say b ∈ N b2 and viceversa. Let, points at (i,j) and (i+1,j+1) are in A. As, in a 8connected grid-graph (i,j+1) and (i+1,j) are connected, they cannot be part of two different basins, i.e., at-least one of the points must be in A. Also, as every arc is part of a maximal vertex-cut, (i,j+1) and (i+1,j) together cannot be in A. Hence, points in A are connected in the grid with 4-connectivity.

Let, w is at (i,j). If (case-1) b 1 and b 2 are at (i,j-1) and (i,j+1) respectively, then both (i-1,j) and (i+1,j) are in A; here, ((i-1,j),(i,j),(i+1,j)) forms a sub-path. If (case-2) b 1 and b 2 are at (i-1,j-1) and (i,j+1) respectively, then (i-1,j) is in A; here, ((i-1,j),(i,j)) forms a sub-path. If (case-3) b 1 and b 2 are at (i-1,j+1) and (i+1,j-1) respectively and neither points at (i-1,j-1) and (i+1,j+1) are in any of B 1 and B 2 , then A comprises of singleton-point w; here (i,j) is the only point in the path. Each watershed-point in A have similar to one of these three cases with basin points from B 1 and B 2 , but may have different orientations. Hence points in A, if connected, forms a path.

PROOF OF LEMMA 2

Let p is at (i,j) and A basin pair = {B 1 , B 2 }. As p is not a end-point in arc A, excluding the other similar orientations, alongwith p either (case-1) (i-1,j) and (i+1,j) are in A, or (case-2) (i-1,j) and (i,j+1) are in A. If case-1, at-least (i,j-1) and (i,j+1) must be in different basins, say B 1 and B 2 respectively, as only these two points are neighbor to the considered arc-points and not neighbor to each other. As two neighbor basin-points must be in same basin extension, if any of (i-1,j-1) and (i+1,j-1) are basin points, that must be in B 1 and if any of (i-1,j+1) and (i+1,j+1) are basin points, that must be in B 2 . If case-2, both (i,j-1) and (i,j+1) must be part of same basin, say B 1 , and (i-1,j+1) is in B 2 . This implies, the basin points among (i-1,j-1), (i+1,j-1) and (i+ 1,j+1) are must be in B 1 . In both cases, all the neighbor basin-points of p are in either B 1 or B 2 . Hence, p arc = {A}.

In case-1, if any of (i-1,j-1) and (i+1,j-1) are watershed points, that has a neighbor-basin B 1 and if any of (i-1,j+1) and (i+1,j+1) are watershed points, that has a neighbor-basin B 2 . In case-2, if any of (i-1,j-1), (i+1,j-1) and (i+1,j+1) are watershed points, that has a neighbor-basin B 1 . Hence, all neighbor watershed-points of p shares at-least one common basin.

PROOF OF LEMMA 3

Let x is at (i,j) and p is at (i,j-1). Let the two neighborbasins of A, basin B 1 and B 2 has (case-1) points (i-1,j-1) and (i+1,j-1) respectively, or (case-2) points (i-1,j-1) and (i+ 1,j) respectively. In case-1, to exist at-least two different arcs A ′ and A ′′ in (x arc \ {A}), as two diagonal points cannot be in same arc in a 8-connected grid-graph, either (case1.1) (i-1,j) and (i+1,j) must be in A ′ and A ′′ respectively and (i,j+1) being a basin-point, or (case1.2) (i-1,j) and (i,j+1) must


Hussein Ezzeddine
email: hussein.ezzeddine@ec-lyon.fr

Julien Huillery

Arnaud Bréard

Yvan Duroc
email: yvan.duroc@univ-lyon1.fr

A Waveform Design Methodology for UHF RFID Systems: A Hybrid Simulation Approach

Keywords: UHF RFID, WPT, waveform design, multisine signals, adaptive power allocation, hybrid simulation

In this paper, we propose a waveform design methodology for ultra high frequency radio frequency identification (UHF RFID) systems based on the quantitative analysis of the backscattered signal. This latter is leveraged to probe the wireless propagation channel, allocate power accordingly to frequency components, and design channel-adaptive multisine signals. UHF RFID system performance is evaluated based on the harvested DC voltage at the output of the rectifying circuit of the RFID tag. To this end, a flexible hybrid simulation model with modular architecture is developed via the ANSYS platform to study UHF RFID system performance. Simulation results show that the designed waveforms provide an improved energetic efficiency especially in highly reflective environments.

I. INTRODUCTION

Radio frequency identification (RFID) has nowadays become an indispensable wireless technology with applications spanning numerous aspects of the industry as well as our daily lives [START_REF] Duroc | RFID: A key technology for Humanity[END_REF]. Contrary to conventional RF communications, passive ultra high frequency (UHF) RFID systems rely on wireless power transfer (WPT) and backscattering of electromagnetic waves to establish communication. However, this implies limited energy efficiency and read range, which is one of the main challenges for UHF RFID technology.

Waveform optimization for UHF RFID systems has gained significant attention in recent years as a solution to improve the read range of RFID tags. It has been widely adopted due to the different advantages it offers over other classical solutions, namely, improving the energetic efficiency of the reader-tag wireless communication link, compliance with the current EPC UHF Gen2 protocol [START_REF]EPCglobal, EPC (TM) Radio-Frequency Identity Protocols Generation-2 UHF RFID Standard, Specification for RFID Air Interface Protocol for Communications at 860 MHz -960 MHz[END_REF], and compatibility with commercial RFID tags. To that extent, there has been several approaches to design optimized waveforms for efficient WPT. In [START_REF] Trotter | Survey of range improvement of commercial RFID tags with Power Optimized Waveforms[END_REF]- [START_REF] Collado | Optimal Waveforms for Efficient Wireless Power Transmission[END_REF] the approaches relied, in principle, on designing signals having high peak-to-average power ratio (PAPR) at emission to increase the energy efficiency of the communication link. In [START_REF] Clerckx | Waveform Design for Wireless Power Transfer[END_REF]- [START_REF]Experimental platform for waveform optimization in passive UHF RFID systems[END_REF] channel-adaptive waveforms have been proposed where the exact channel state information (CSI) was assumed to be known to the transmitter. However, to be implemented in real time, the exact CSI needs to be acquired at the transmitter, which could be quite challenging due to the power and hardware limitations of passive UHF RFID tags.

In fact, the real challenge with waveform design for UHF RFID systems is to be able to probe the channel without any additional processing or modification at the tag; all processing should be done at the reader. Fortunately, the backscattered wave-highly dependent on the CSI-has the potential for both evaluation and design of RFID systems [START_REF] Fuschini | Analytical Approach to the Backscattering from UHF RFID Transponder[END_REF], [START_REF] Yang | Multi-antenna Wireless Energy Transfer for Backscatter Communication Systems[END_REF]. In addition, its analytical expressions in free space [START_REF] Fan | Signal descriptions and formulations for long range UHF RFID readers[END_REF] and multipath [START_REF] Griffin | Multipath Fading Measurements at 5.8 GHz for Backscatter Tags With Multiple Antennas[END_REF] propagation environments have been derived. Thus, in frequency diverse single-antenna UHF RFID systems, the observed backscattered signal could be leveraged to acquire some knowledge of the RF channel, adapt power allocation to frequency components, and thereby design channel-adaptive energy efficient waveforms without modifying the tag.

In this work, we propose a waveform design methodology for UHF RFID systems based on the quantitative analysis of the backscattered signal. This latter is leveraged to probe the wireless propagation environment and adapt power allocation to frequency components to improve the energy efficiency of the reader-tag link. RFID system performance is evaluated based on the harvested DC voltage at the output of the rectifying circuit of the tag. For this purpose, we develop an improved hybrid simulation model, first introduced in [START_REF] Ezzeddine | Simulation Framework for Studying UHF RFID Systems in Pulse Wave Mode[END_REF], that accounts for nonlinearities and facilitates studying UHF RFID system performance using optimized waveforms.

The rest of the paper is organized as follows. Section II presents the waveform design methodology. Section III describes the hybrid simulation model developed. Section IV provides performance analysis of the proposed waveforms. Finally, section V draws the conclusion and perspectives.

II. WAVEFORM DESIGN METHODOLOGY

A. The Backscattered Wave

Consider a typical amplitude-modulated backscattered RF signal, r(t), received by the reader. Assuming continuous wave (CW) mode transmission (a single sinewave carrier is used at emission) in a lossless, frequency-flat channel, the mathematical expression of such a signal can be written as

r(t) = [A + ∆V m(t)]cos(2πF t + θ) (1)
where A represents the constant envelope of the transmit signal received at the reader, m(t) is a binary signal that takes one of two values (0 or 1) each corresponding to a tag load impedance state, F and θ are the carrier frequency and phase of the backscattered signal respectively, and ∆V is the difference in Volts between the averages of the high and low states of backscattered baseband signal. Besides, ∆V is proportional to the magnitude of the Differential RCS (Radar Cross Section) vector as seen from the reader [START_REF] Fuschini | Analytical Approach to the Backscattering from UHF RFID Transponder[END_REF]. Thus, after demodulating and filtering r(t), ∆V m(t) would represent the tag's backscattered baseband signal received at the reader; that is, tag information.

In the presence of multipath fading and frequency-selective channels, ∆V m(t) can be written as a function of the transmitted signal, the time-varying load reflection coefficient of the RFID tag and the frequency response of the RF channel [START_REF] Griffin | Multipath Fading Measurements at 5.8 GHz for Backscatter Tags With Multiple Antennas[END_REF]. From (1), it is inferred that any attenuation induced by the channel's amplitude would influence the quantity ∆V m(t). Consequently, given its dependency on the CSI, ∆V m(t) can be utilized to probe the wireless channel. Knowing that A could be filtered out from r(t) using basic digital signal processing (DSP) techniques, ∆V could then be easily calculated and utilized to determine the best communication frequencies based on the two-way link. Therefore, channeladaptive waveforms could be designed based on the ∆V criterion.

B. Designing Adaptive Multisines Based on Backscattered Wave Analysis

Consider a general multisine signal consisting of a set of N uniformly spaced frequencies, its time-domain expression is given by

x(t) = ℜ N n=1 a n e jϕn e j2πfnt (2)
where n is a positive integer (n ∈ [1, N ]), and a n , f n and ϕ n are the amplitude, frequency and phase of the n th sinusoid, respectively. The uniformly spaced frequencies are expressed as

f n = f 1 + (n -1)∆ f (3)
where f 0 is the initial frequency and ∆ f is the frequency spacing. Let x n (t) be the n th sinusoid, i.e. a CW mode signal having a frequency f n . The waveform design methodology consists of, first, evaluating each f n according to the ∆V criterion during the channel probing phase, then, sorting these frequencies in a decreasing order of ∆V , and last, constructing x(t) by allocating power to the best f n components. During the channel probing phase, first, x n (t) is transmitted at each f n in the operating bandwidth. Then, each respective r n (t) received by the reader is processed to recover the corresponding baseband signal (at the corresponding frequency) and calculate the corresponding ∆V . This leads to obtaining a ∆V curve as a function of f n . Based on this curve, the frequencies are sorted according to their ∆V performance: the frequencies corresponding to the highest (resp. lowest) ∆V value are considered as the most (resp. least) favorable operating frequencies. The result is a set of N operating frequencies arranged from the most to the least favorable (or equivalently, from the least to the most attenuated) as seen from the reader. Finally, using (2), a total of N combinations of multisine signals could be created, ranging from 1 frequency per multisine to N frequencies per multisine.

III. HYBRID SIMULATION MODEL

To test the previously described waveform design methodology, we rely on an improved hybrid simulation model (first introduced in [START_REF] Ezzeddine | Simulation Framework for Studying UHF RFID Systems in Pulse Wave Mode[END_REF]) of a passive RFID system. The improved model, developed via the ANSYS platform, facilitates studying RFID system performance using unconventional waveforms with a high degree of flexibility and provides access to raw signals at both the reader and tag. By decoupling in time the tag's main functions, the model allows analysing the backscattered signal at the reader and evaluating the harvested energy at the tag.

In a typical passive UHF RFID system, the tag circuit performs three main functions: energy harvesting, demodulation and control logic, and backscatter modulation. Accurately modelling such a tag circuit is particularly challenging because of the design complexity, which is subject to extremely low power constraint. Fortunately, in the case of waveform design, it is sufficient to consider only two of the aforementioned functions performed by the tag: energy harvesting (to evaluate the energetic performance) and backscatter modulation (to generate and analyse the backscattered signals). For simplicity, the energy harvesting and backscatter modulation functions are modelled independently.

The hybrid simulation model is developed using ANSYS Circuit Designer and HFSS co-simulations. Fig. 1 shows a schematic depiction of the simplified UHF RFID system considered in this study. The reader is emulated by a transceiver in a monostatic configuration with a single antenna Ant R while the tag is emulated by a tag circuit and antenna Ant T . The reader circuit consists of an arbitrary waveform generator (AWG), a circulator, a DC-block capacitor C bs , a resistive load R bs , and a DSP block. The tag circuit consists of two subcircuits that are simulated separately: energy harvester (EH) and backscatter modulator (BM). When the EH is connected to Ant T , the BM does not interfere with the operation of the tag (completely disconnected), and vise versa when the BM is connected to Ant T . The first consists of a rectifying circuit and an output resistive load R L EH optimized to maximize the harvested energy, while the second consists of an RF switch, an independent DC voltage source generating a predefined square signal to drive the switch, and a resistive load R L BM matched to the tag antenna.

IV. PERFORMANCE ANALYSIS

To have a broader perspective on system performance with respect to the different UHF standards present worldwide, the study is carried out on a wide frequency span: from 800 MHz to 1000 MHz, where f 1 = 800 M Hz and ∆ f = 10 M Hz. Thus, a total of N = 21 equally spaced frequencies are considered. The average power incident to Ant R is set to the same constant value, P t , in all cases.

A. Simulated Scenarios

A typical 50-Ω half-wave dipole antenna is used for both Ant R and Ant T . Two channel scenarios are considered: nonline-of-sight (NLOS) and free space (FS). In the NLOS case, a highly reflective propagation environment composed of a rectangular aluminium box in which metallic obstacles have been arbitrarily placed is used. Fig. 2 illustrates one realization of the NLOS scenario where the total electric field lines distribution in the XZ plane at 915 MHz is shown. Fig. 3 shows the frequency response (S21 parameter) corresponding to both scenarios.

B. Channel Probing Phase

To probe the channel, after transmitting x n (t) at each f n of the N frequencies, the received r n (t) is I/Q demodulated and the corresponding ∆V value is obtained. Fig. 4 shows the ∆V values as a function of f n for both scenarios. These results indicate that the maximum ∆V values are obtained around 860 MHz for the NLOS scenario, and around 940 and 960 MHz for the FS scenario. Looking back at Fig. 3, the S21 parameter shows maximum transmission at around 860 MHz for the NLOS scenario, and around 910 and 960 MHz for the FS scenario. Although not perfectly aligned, it is clear that there exists a strong correlation between the curve profile of ∆V as a function of f n and the S21 curves as a function of frequency for both scenarios. Of course, the mismatch between both curves is certainly related to the unpredictable phase behaviour of the backward channel. However, this does not undermine the fact that ∆V is a good and reliable indicator of the channel strength.

C. Energetic Performance Evaluation

The energetic performance of the designed waveforms is evaluated based on the RMS value of the DC voltage V Load collected at the output of the rectifying circuit, i.e. at the terminals of R L EH (see Fig. 1). Note that the average transmit power is set to P t for all emitted signals x(t). For a given N , ϕ n is set to 0 and the individual sinewaves are set to have equal amplitudes (a n = constant) such that the average transmit power of x(t) is P t . Fig. 5 illustrates the harvested DC voltage of the designed waveforms as a function of N for both scenarios.

It is noticed that in FS, the harvested energy is maximum for N = 1, whereas in the NLOS case, the harvested energy reaches a maximum for N = 3. After reaching the peak, both curves then decrease gradually as a function of N .

In qualitative terms, these results show that the waveforms designed according to backscattered signal analysis improve the energetic performance of the reader-tag link. For the FS scenario, the highest energy is harvested by using a CW signal, while for the NLOS scenario, the highest energy is harvested by using a multisine waveform. This is mainly because the rectifying circuit has been optimized for CW mode operation, which is the case for commercial RFID tags. It is worth noting that using this method, the harvested energy is maximized for the same frequencies that maximize ∆V , meaning that the detection of backscattered information is also improved. Although the obtained results depend strongly on the simulated scenarios and the implemented EH circuit, they still suggest that channel-adaptive multisines that maximize the harvested energy could be designed based on backscattered signal analysis especially in highly reflective environments.

V. CONCLUSION

In this work, we studied waveform design in UHF RFID systems based on the quantitative analysis of the backscattered signal. The proposed methodology allowed acquiring knowledge on the wireless propagation channel using the backscattered RFID tag information; no additional processing at the tag was needed. Channel-adaptive multisine signals were designed and their energetic performance was evaluated using a flexible and accurate hybrid simulation model. The results showed that the proposed multisines improve the energetic efficiency of the RFID communication link especially in highly reflective environments. Finally, it is worth noting that although the study is limited to two channel scenarios, the methodology could nevertheless be generalized and applied to any possible scenario. In future work, a generalized waveform design algorithm based on backscattered signal analysis will be proposed. In such case, the designed waveforms will be applied to different channels, circuit designs and antennas.

Fig. 1 :

 1 Fig. 1: Schematic depiction of the modeled UHF RFID system.

Fig. 2 :

 2 Fig. 2: 3D electromagnetic model: Reader and tag antennas separated by an NLOS propagation environment.

Fig. 3 :

 3 Fig. 3: S21 parameters for NLOS and FS scenarios.

Fig. 4 :

 4 Fig. 4: ∆V values of the baseband signals obtained in CW mode as a function of f n for NLOS and FS scenarios.

Fig. 5 :

 5 Fig. 5: DC voltage (RMS value) of the designed waveforms collected at the output of the energy harvesting circuit as a function of N for NLOS and FS scenarios.