Nicola Pellicanò
email: nicola.pellicano@u-psud.fr

Sylvie Le Hégarat-Mascle

Emanuel Aldea
email: emanuel.aldea@u-psud.fr

2CoBel: A Scalable Belief Function Representation for 2D Discernment Frames

Keywords: Belief functions, 2D discernment frame, graph-based representation, localization

This paper introduces an innovative approach for handling 2D compound hypotheses within the Belief Function framework. We propose a polygon-based generic representation which relies on polygon clipping operators, as well as on a topological ordering of the focal elements within a directed acyclic graph encoding their interconnections. This approach allows us to make the computational cost for the hypothesis representation independent of the cardinality of the discernment frame. For belief combination, canonical decomposition and decision making, we propose efficient algorithms which rely on hashes for fast lookup, and which benefit from the proposed graph representation. An implementation of the functionalities proposed in this paper is provided as an open source library. In addition to an illustrative synthetic example, quantitative experimental results on a pedestrian localization problem are reported. The experiments show that the solution is accurate and that it fully benefits from the scalability of the 2D search space granularity provided by our representation.

Introduction

Belief Function Theory (BFT) [START_REF] Dempster | A generalization of Bayesian inference[END_REF][START_REF] Shafer | A mathematical theory of evidence[END_REF] is an increasingly popular framework for the generalization of probability and possibility theory by modeling imprecision and partial ignorance of information, in addition to its uncertainty.

BFT is widely used in fundamental tasks which benefit from multi-modal information fusion, such as object detection and data association for assisted driving [START_REF] Chavez-Garcia | Multiple sensor fusion and classification for moving object detection and tracking[END_REF][START_REF] Denoeux | Optimal object association in the Dempster-Shafer framework[END_REF][START_REF] Labayrade | Obstacle detection based on fusion between stereovision and 2d laser scanner[END_REF], tracking [START_REF] Hachour | Object tracking and credal classification with kinematic data in a multi-target context[END_REF][START_REF] Tran | Evidential box particle filter using belief function theory[END_REF], object construction [START_REF] Rekik | Dynamic object construction using belief function theory[END_REF], outdoor localization [START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF], or autonomous robot mapping and tracking [START_REF] Tanzmeister | Grid-based mapping and tracking in dynamic environments using a uniform evidential environment representation[END_REF][START_REF] Kurdej | Controlling remanence in evidential grids using geodata for dynamic scene perception[END_REF], medical imaging [START_REF] Bloch | Some aspects of Dempster-Shafer evidence theory for classification of multi-modality medical images taking partial volume effect into account[END_REF], remote sensing [START_REF] Hégarat-Mascle | Automatic change detection by evidential fusion of change indices[END_REF], video surveillance [START_REF] Kumar | Addressing uncertainty in multi-modal fusion for improved object detection in dynamic environment[END_REF], aircraft classification [START_REF] Fortin | Multi-target PHD tracking and classification using imprecise likelihoods[END_REF].

The main limitation, when dealing with such theory, since it copes with compound hypotheses, is the size of the set of hypotheses to handle, which may become intractable when the size of the discernment frame increases. Such issue becomes critical especially in higher dimensions, as when dealing with twodimensional (2D) spaces. In the rest of our paper, we define a set (in our case a frame or a focal set) as being a 2D set if its elements are elements of the Cartesian product of two totally ordered sets. Accordingly, a 2D discernment frame is defined as a frame of discernment which handles 2D focal elements. Now such 2D discernment frames can be encountered for instance in information fusion in the image domain (e.g., [START_REF] Rekik | Dynamic object construction using belief function theory[END_REF]), in box particle filtering [START_REF] Tran | Evidential box particle filter using belief function theory[END_REF], or in localization applications (e.g., [START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF]).

In [START_REF] Rekik | Dynamic object construction using belief function theory[END_REF], the authors aim to reconstruct objects from fragmentary detections in the image space. The discernment frame corresponds to the 2D image lattice.

BFT is then exploited in order to perform object-detection data association, spatial extension of objects when new fragments are found, temporal conditioning for object displacement/disappear modeling and spatial conditioning for object separation modeling. Focal elements are represented as set of non-intersecting 2D-boxes.

In [START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF], 2D BFT is applied to the global navigation satellite system (GNSS) localization problem, where the information is represented by imprecise position measurements provided by several satellite sources, where complex focal elements shapes (ring sectors) are modeled as sets of boxes.

In [START_REF] Kurdej | Controlling remanence in evidential grids using geodata for dynamic scene perception[END_REF] the authors perform scene environmental mapping by making extensive use of evidential grids for spatial and temporal fusion, by converting the original 2D domain in a map of 1D BBAs.

While several public belief function theory libraries exist [START_REF] Kurdej | BFT -Belief Functions Theory library[END_REF][START_REF] Reineking | Dempster-Shafer theory library[END_REF][START_REF] Martin | Matlab toolbox for belief functions[END_REF], all of them limited to 1D representations, the use of 2D spaces for information fusion has been recently explored for various tasks. In the following of this study, we focus on 2D discrete discernment frames. An exhaustive representation of Ω discrete hypotheses usually involves a discretization of the area as a grid, where each cell of the grid represents a singleton hypothesis [START_REF] André | Evidential framework for data fusion in a multi-sensor surveillance system[END_REF][START_REF] Kurdej | Controlling remanence in evidential grids using geodata for dynamic scene perception[END_REF]. Focal elements are then expressed by using a binary word, where a bit equal to 1 means that the cell belongs to the focal set. Such straightforward binary-word representation of hypotheses allows for the definition of operators on sets through simple bitwise operations. However, such a representation suffers from major drawbacks when used in real world applications. Since there are 2 Ω potential focal elements, large discernment frames become intractable, when the discretization resolution or the size of the whole area increases (different tasks may require different levels of precision for the solution, thus calling for a 2D space discretization which would increase quadratically the representation space size).

For such reasons, some works rely on different approaches to handle the 2D case: by proposing a smart sub-sampling of the 2D space to maintain tractability [START_REF] André | Evidential framework for data fusion in a multi-sensor surveillance system[END_REF]; by proposing a sparse representation of the set of hypotheses, and by keeping in memory only the ones which are carrying non-null information [START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF].

In order to make the representation manageable, [START_REF] André | Evidential framework for data fusion in a multi-sensor surveillance system[END_REF] proposes to condition the detections acquired from one sensor in its field of view, and to perform a coarsening at a lower spatial resolution of the focal elements, depending on the physical properties of the sensor. While these workarounds help in practice, they do not make the application fully scalable with the size of the scene, and they involve approximations such as the already cited coarsening, or frequent BBA simplification, which aims at maintaining under control the number of focal elements of the BBAs. Such limitations derive from the fact that the complexity of any basic operator between focal elements (e.g., intersection, union) depends on the cardinality of the focal elements themselves. The works in [START_REF] Rekik | Dynamic object construction using belief function theory[END_REF] overcome this limitation by proposing a representation of any focal element as a set of rectangular boxes, and then by expressing the basic operators as performed on arrays of rectangles. In this setting the complexity of the basic operators will be a function of the number of boxes, but it will be independent of the cardinality of the discernment frame.

However, such representation suffers from some practical limitations. First, the representation is not unique. The same focal element may be represented by different sets of boxes, which do not allow for fast focal element comparisons and lookup. Second, the box set representation implies a non-unique approximation of the real focal element shape once edges are not parallel to the axes of reference. Geometric approximations of such focal elements may require a very large set of boxes when precision is a concern. Moreover, subsequent operations involve increasing box fragmentation which may be detrimental both for performance and for memory load. In order to avoid deep fragmentation, in [START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF] some representation simplification procedures are presented, which in turn increase the cost of BBA management.

In [START_REF] Sui | Identification of elastic properties in the belief function framework[END_REF], the authors rely on a description of multidimensional focal elements by discretizing their support as a point cloud, and by deriving an approximation of Dempster's rule by Monte Carlo simulation. They underline the fundamental issue raised by representations based on parametric functions which lead to difficult implementation of the elementary operations (intersection, union, and complementation), which are needed for Dempster-Shafer reasoning. Alternatively to this representation, in this paper we propose a novel approach, which overcomes the efficiency issues of parametric representations.

Following the idea of providing a sparse representation for 2D BFT, and motivated by the great benefit that an efficient representation would carry to high dimensional problems, we propose a new two-dimensional representation which has full scalability properties with respect to the size of the discernment frame, while allowing a theoretical infinite precision (bounded by the hardware precision limitations).

Note that our purpose is different from theoretical studies in BFT [START_REF] Cuzzolin | A geometric approach to the theory of evidence[END_REF] that propose geometric interpretations to the classical belief assignment, in order to formalize and solve problems such as probabilistic approximation and canonical decomposition. Indeed, whereas such works propose a geometrical formulation of the basic belief assignment (BBA) itself, our focus is on the geometrical representation of 2D focal elements. This paper extends our preliminary conference work [START_REF] Pellican | 2cobel: An efficient belief function extension for two-dimensional continuous spaces[END_REF] and is organized as follows. Section 2 presents the efficient BBA representation we adopt for the case of 2D discernment frames. Section 3 details the combination operators which benefit from our representation, and Section 4 discusses the decision making step. Section 5 presents the synthetic and the real data experiments, and we conclude in Section 6.

BBA representation

Let us denote by Ω the discernment frame, i.e., the set of mutually exclusive hypotheses representing the solutions. The power set 2 Ω is the set of the Ω subsets having cardinality 2 Ω . The mass function m, specifying a BBA, is

defined as m ∶ 2 Ω → [0, 1] such that ∑ A∈2 Ω m(A) = 1. A hypothesis A ∈ 2 Ω such that m(A) > 0, is a focal element of m.
The information encoded by a mass function can be represented in different equivalent formulations, most notably belief (Bel), plausibility (P l) and commonality (q):

Bel(A) = B⊆A m(B), P l(A) = B∩A≠∅ m(B), q(A) = B⊇A m(B), defined ∀A ⊆ Ω.
A BBA is said to be dogmatic if Ω is not a focal element, i.e., m(Ω) = 0.

A BBA is said to be consonant if the focal elements are nested:

∀ (A, B) ∈ 2 Ω × 2 Ω , m(A) > 0, m(B) > 0 ⇒ A ⊆ B ∨ B ⊆ A.
In the following sections, two complementary representations are proposed.

In Section 2.1, a compact polygon-based geometric focal element description, for BBAs defined in 2D spaces, is detailed. It ensures low-level scalability for primitive operators, while exhibiting fast comparison and lookup capabilities. It represents a generalization of the state-of-the-art representations [START_REF] Rekik | Dynamic object construction using belief function theory[END_REF][START_REF] André | Evidential framework for data fusion in a multi-sensor surveillance system[END_REF], which overcomes their limitations (outlined in Section 1).

In Section 2.2, a graph-based BBA description, independent from the BBA representation and from the space dimensionality, is proposed. It encodes the structural relationships between focal elements, and provides high-level scalability capabilities, e.g., for decomposition methods (Section 3.2) and for decision making algorithms (Section 4). Graph construction, optimization and traversal strategies are discussed.

Let us consider a 2D discernment frame Ω. We will refer to the illustrative example in Figure 1. Such an example, inspired by [START_REF] André | Evidential framework for data fusion in a multi-sensor surveillance system[END_REF], represents a typical localization scenario, where the discernment frame is a bounded region representing the ground plane.

Focal element geometric representation

As mentioned in the Introduction, 2D focal element representations based on an exhaustive representation of Ω and binary words become intractable once the size of one axis of the discernment frame becomes greater than a few tens of units, and the box set representation [START_REF] Rekik | Dynamic object construction using belief function theory[END_REF] suffers from geometric approximation due to the fact that the number of boxes needs to be limited to small values.

In this work, we propose to represent the focal elements as generic polygons (or sets of polygons for focal elements having multiple components, e.g., focal elements with holes or which are split after a difference operation), by exploiting the capabilities of the generic 2D polygon clipping algorithms, efficient methods for basic operator implementations (intersection, union, difference and XOR).

A focal element is represented by a set of closed paths, each of them represented by an ordered array of vertexes (counter-clockwise for positive areas, clockwise for holes). As operator implementations, we exploit an extension of Vatti's algorithm for clipping [START_REF] Vatti | A generic solution to polygon clipping[END_REF] implemented in the Clipper library [START_REF] Johnson | Clipper -an open source freeware library for clipping and offsetting lines and polygons[END_REF].

The polygons are constrained to be simple, i.e., defined by closed simple paths (no crossing), with a minimum number of vertexes (no vertex joining two co-linear edges). Figure 2 shows an example of focal element representation as two polygons (one of them representing a hole). In case of multiple polygons per focal element, an additional constraint needs to hold: Given the set of paths composing a focal element, no edge of one path can cross an edge of another path. Under these constraints, the complexity of the basic operators between two polygons having n and m number of vertexes respectively, is O(nm). Such lightweight representation presents also the advantages of uniqueness and precision. The set of (circular) vectors of vertexes of a focal element (set of polygons) provides a unique representation. The vertex coordinates use integer values for numerical robustness and correctness. This means that the continuous representation provided by polygons implies an underlining discretization. However, differently from the previous approaches, the coordinates can be rescaled at the desired level of precision (up to ≈ 10 19 ) without any impact on the speed and memory requirements of the algorithm, being bounded only by the numerical representation limits of the hardware. This implies full scalability of the focal elements with respect to their size. Example 1. Figure 1a shows an example of focal elements in the case of a localization application. The camera detection (red) is represented as a disk focal element, whereas the focal elements which have the shape of ring sectors embed the imprecision of the location and the ill-knowledge of the camera extrinsic pa-rameters; the track (green) represents the location of the target at the previous frame, whereas its dilation is used in order to model the imprecision in its position introduced by time; the gray and blue focal elements belong to two different BBAs representing scene priors, of building and road presence respectively. The disk shaped focal elements are modeled as 64 to 128 vertexes regular polygons.

Graph-based representation

In the previous section, we have highlighted that an efficient geometric representation, as the one proposed, may lead to the definition of basic operators (e.g., intersection, union) which are cardinality independent (and thus scalable).

However, such representation alone cannot guarantee full scalability properties when dealing, for example, with decision making algorithms, which work at singleton hypothesis level. Thus, claiming that a representation is spatially scalable requires some additional mechanisms which enforce scalability at an higher operational level than primitive operators on sets. Indeed, many operations on BBAs, used for BBAs combination and decision making, can be expressed as algorithms which depend only on how the focal elements intersect with each other, irregardless of the actual shape or size of such elements. Typical use cases which need an efficient data structure, serving as the foundation for the proposal of efficient algorithms, are the canonical decomposition (Section 3.2) and the BetP maximization (Section 4).

Together with an efficient geometric representation, we propose a generic representation, independent from the actual geometric representation chosen, which expresses the relationships between the focal elements of a given BBA.

In the following sections, we will propose first a straightforward representation based on graphs, then we will highlight its limitation, and, finally, we will propose some optimization techniques to improve its efficiency.

Straightforward graph definition and construction

We propose to encode the relevant topological links between the focal elements as an intersection-inclusion graph, i.e an intersection graph where an edge is augmented in the case of a (directional) inclusion relationship.

Let us define the focal elements set as A = {A 1 , A 2 , . . . , A n }. For optimization reasons explained further, the focal elements are labeled according to decreasing cardinality and the ordering follows the element label:

∀ (A i , A j ) ∈ A × A, i < j ⇒ A i ≥ A j .
In the case of different focal elements with the same cardinality, the topological order is not unique. Thus, the graph representation itself, differently from the geometric one, is not unique in general. However, non-uniqueness, given the low-level polygon representation, is not a necessary property. Moreover, graph optimizations and graph-based algorithms (detailed further) do not require uniqueness as a prerequisite.

We build a directed acyclic graph (DAG) G = (V, E) where each node v ∈ V is a focal element and each edge e ∈ E represents a non empty intersection between two focal elements, with the direction of the edge respecting the topological ordering. The inclusion relationship information is encoded into separate arrays.

Each node has a reference to its including nodes with the lowest and highest label. For example, if focal element A 5 is included into A 1 , A 3 , A 4 , then the node v 5 carries two pieces of information, namely l l 5 = 1 and l h 5 = 4, where l l j and l h j stands for lowest and highest label including focal element A j .

Let us define the k th path of length m in the intersection-inclusion graph

G = (V, E) as P (m) k = ⟨v k,1 , v k,2 , . . . , v k,m ⟩.
Such path represents the intersection between all the focal elements related to the nodes included in the path. In the following, we will refer to the intersection derived from a path as the one computed from all its nodes.

Proposition 2.1. For any non empty intersection I derived from a set  of focal elements, there exists a path P in the intersection-inclusion graph G, connecting the elements of Â.

Proof. Let us consider  = {A 1 , . . . , A m } as the target set of focal elements (I = ⋂ Ai∈ Ai A). It follows that, given the graph G = (V, E):

∀(A i , A j ) ∈ Â × Â, i < j A i ∩ A j ≠ 0 ⇒ v i , v j ∈ V, (v i , vj) ∈ E.
Since I ≠ ∅, any node at index i is connected to every node at index j, such that j > i.

The above formula implies:

∀v i ∈ V, (v i , v i+1 ) ∈ E,
a sufficient condition for the existence of the path P (m) = ⟨v .

In the following, we will refer to a path which is not redundant, equivalently, as a non-redundant path. While the graph structure can be used to explore all the possible intersections between focal elements, it shall be as efficient as possible in order to avoid exploring dead paths, while traversing only non-redundant paths, since they are by construction the paths carrying the greatest amount of structural knowledge (they gather all the focal elements which include the target intersection set).

Graph traversal and limitations

The determination of the useful paths (i.e., neither dead nor redundant) is performed through graph traversal. According to the chosen ordering (decreasing cardinality), each node is iteratively selected as the root. For each root, a depth first search strategy is used to traverse the graph. Then, given the current node v i , the intersection between all the nodes of the current path is propagated as I i ; given an edge e = (i, j), the node A j (for notation shortness a node is equivalently called by its represented focal element) is explored if

I j = I i ∩ A j > 0.
Such an operation is equivalent to performing a dynamic graph pruning which is a function of the current path, as soon as some branch leads to a dead path. Then, even if the number of node visits can be very large according to a brute force exploration, the dynamic pruning helps to cut out early dead paths, making the number of operations much lower in practice. In this form, however, the worst case for pruning happens with consonant BBAs, where every edge represents an inclusion relationship. In such case, the graph is complete, and the entire graph would need to be explored without any pruning possibility, even if most of the paths would be redundant. Such an observation, together with the fact that in practice consonant BBAs are widely used as basic representation of the initial imprecision increase with certainty, e.g., in the Dubois and Prade BBA allocation [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF], justifies the use of the inclusion information for simplifying the graph and optimizing the traversal. In the following section, some optimization mechanisms will be proposed in order to reduce the number of explored paths during the traversal, thus decreasing the average complexity of the algorithms which will be based on the graph representation. Three main sources of optimization will be presented.

Graph optimization

Proposition 2.2 (Root suppression). Given the current root node v j ∈ V , if:

∃v i ∈ V, (v i , v j ) ∈ E, i < j s.t. A j ⊊ A i ,
every path originating from root v j is redundant.

Proof. Let us consider a generic path starting at the root v j :

P (m+1) k = {v j , v k,1 , . . . , v k,m }.
By definition of a DAG, the index of the nodes v k,h , h ∈ {1 . . . m}, is higher than j, and, thus, than i. Let us consider the corresponding set of focal elements

Âk = {A j , A k,1 , . . . , A k,m }, I k = A j ∩ ⋂ h=1...m A k,h ,
and the augmented set

Â′ k = {A i , A j , A k,1 , . . . , A k,m }, I ′ k = (A i ∩ A j ) ∩ ⋂ h=1...m A k,h = A j ∩ ⋂ h=1...m A k,h = I k .
Moreover, the path P

′(m+2) k = {v i , v j , v k,1 , . . . , v k,m } is a superpath of P (m+1) k . It follows that P (m+1) k is a redundant path.
Root suppression implies that only root nodes which correspond to focal elements not included in some others preceding them in topological order, can produce paths which are non-redundant. Thus, all the other nodes are suppressed as possible roots for the traversal. Such property justifies the choice of a topological sorting in descending order of cardinality. Algorithm 1 shows where root suppression is used. After constructing the graph, each node is taken into account as candidate root for depth first search. Root suppression is used in order to filter root candidates for the following graph traversal operations.

Proposition 2.3 (Early stopping). Given the current root v r , a path containing a node v j included in a node v h , h < r is redundant.

Proof. Let us consider the generic path starting at the root v r and contain-

ing v j : P (m+n+2) a,b = {v r , v a,1 , . . . , v a,m , v j , v b,1 , . . . v b,n }. The corresponding set of focal elements is Âa,b = {A r , A a,1 , . . . , A a,m , A j , A b,1 , . . . A b,n } leading to the intersection I a,b . Since A j ⊂ A h , we can define the augmented set Â′ a,b = {A h , A r , A a1 , . . . , A a,m , A j , A b1 , . . . A b,n }, leading to the intersection: I ′ a,b = (A h ∩ A j ) ∩ A r ∩ ⋂ i=1...m A a,i ∩ ⋂ i=1...n A b,i = I a,b , since the term (A h ∩ A j ) reduces to A j .
Proposition 2.1 guarantees that the superpath

P ′(m+n+3) a,b = {v h , v r , v a,1 , . . . , v a,m , v j , v b,1 , . . . v b,n } exists. Thus, the path P (m+n+2) a,b
is redundant.

The early stopping criterion allows us to stop exploring a node if it is included in an already explored root. The constraint is equivalently expressed as the fact that early stopping is performed at v j if l l j < r (among the nodes/focal elements that included v j , indexed in l l j , l h j , there is at least one that has already been used as a root).

Early stopping is applied during graph exploration (see Algorithm 2 and Algorithm 3). It serves as a precondition for exploring or not a child of the current node.

Proposition 2.4 (Graph simplification). Given a node v j which has multiple incoming inclusion edges from v h i h=1...m , all the edges but the one from the highest indexed node in topological order, (v m i , v j ), belong to redundant paths.

Proof. First, one can demonstrate that, after removing the inclusion edges from

v h i h=1...m-1 , v j is still reachable from v 1 i . Since the edge between v m i and v j is kept, it is equivalent to demonstrate that v m i is reachable from v 1 i . ∀A k i , A s i , (k, s) ∈ {1, . . . , m} 2 , A k i ∩ A j = A j , A s i ∩ A j = A j ⇒ A k i ∩ A s i ≥ A j ≠ 0 (1)
Thus, there exists a path from any node v h i h=1...m-1 to v m i , and, consequently, to v j .

Finally, we demonstrate that, if one of the removed edges is included in a path, that path is redundant.

Let us consider the path

P (n+q+2) a,b = v a,1 , . . . , v a,n , v h i , v j , v b,1 , . . . v b,q
, where h < m, leading to the intersection I a,b . Let us consider the node v k i , h < k ≤ m, which, by topological ordering, cannot be already included into

P (n+q+2) a,b . Let us consider the superpath P ′(n+q+3) a,b = v a,1 , . . . , v a,n , v h i , v k i , v j , v b,1 , . . . v b,q , leading to the intersection I ′ a,b . Two edges have been added: (v h i , v k i ), guaran- teed to exist by Equation (1); (v k i , v j )
, that exists by definition of the problem.

I ′ a,b = A h i ∩ A k i ∩ A j ∩ ⋂ i=1...n A a,i ∩ ⋂ i=1...q A b,i = I a,b , since the term A k i ∩ A j reduces to A j . Thus, P (n+q+2) a,b is a redundant path.
Graph simplification boils down to keeping, for each v j , only the incoming inclusion connection from the node with the highest index in topological order l h j . Algorithm 4 details the graph construction steps, and shows how graph simplification is exploited. Any intersection edge between two nodes is added immediately, while addition of the inclusion edges is delayed until all the pairs of nodes are inspected (only l l j and l h j indexes are updated). At the end, for each node j, only the inclusion edge from l h j is created (if l h j is not null). Now consider the case of a consonant BBA with k focal elements. In its pure form, the representation leads to a complete DAG, with 2 k possible paths. However, after graph simplification, only the edges going from element A i to A i+1 are kept, resulting into k -1 effective edges. Moreover, due to root suppression, only the first node will be used as root, so k nodes in total will be explored, leading to k non-redundant paths, providing k different intersections, equal to the k original focal elements.

Node

l l l h Use as root Deleted edges (simplification)

1 null null yes - 2 1 1 no - 3 1 1 no - 4 1 1 no - 5 1 4 no (v 1 → v 5 ), (v 2 → v 5 ) 6 1 3 no (v 1 → v 6 ), (v 2 → v 6 ) 7 1 5 no (v 1 → v 7 ), (v 2 → v 7 ), (v 4 → v 7 )
Table 1: Graph optimization main steps for the illustrative example in Figure 1.

Example 2. We refer to the example in Figure 1. The graph on the left of

BBAs combination

Classical combination rules and hashing

Numerous combination rules exist in order to mix the information provided by two sources. When the sources m 1 and m 2 are cognitively independent, the conjunctive combination rule is the most popular among them:

∀A ∈ 2 Ω , m 1 ∩ m 2 (A) = (B,C)∈A1×A2, B∩C=A m 1 (B)m 2 (C),
where A i is the set of focal elements of m i . In computational terms, the rule involves the construction of a new BBA by performing intersection operations between all pairs of focal elements from the two BBAs. According to the sum in the previous equation, when creating a new focal element from an intersection, one has to check for its existence and to add up some elementary mass product value if it already exists. The necessity of accumulating elementary masses into already existent focal elements (maybe computed with different operators than intersection, e.g., union in the case of the disjunctive rule), and thus to do an existence check every time a new mass value is computed, is not specific of the conjunctive rule, but it is shared with several other rules (e.g., the disjunctive rule [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF], cautious rule [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] and evidential q-relaxation [START_REF] Pichon | A consistency-specificity trade-off to select source behavior in information fusion[END_REF]).

The above considerations justify the need for a BBA representation which allows for a fast lookup of a focal element in an array. The uniqueness and compactness of the proposed representation allow for an efficient and low collision prone hashing. The sparse set of focal elements of a given BBA can be stored in a hash table, where the circular vector of vertexes is used to compute the hash. For a given polygon, its hash will be unique provided that we fix a policy to decide the starting vertex (e.g., the top left). The array hashing function is equivalent to the one implemented in the Boost library's [START_REF]Boost, Boost C++ Libraries[END_REF] hash range method.

The binary-word representation, in comparison, uses the full word as a unique key. However, the key length (in number of bits) grows linearly with the cardinality of the discernment frame, requiring the use of big data structures in order to store it. On the contrary, the proposed hash exhibits collision resistance property despite a fixed length. The box set representation [START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF], being not unique, does not allow for direct hashing without the extraction of the minimal set of vertexes on the boundary. A cheap alternative could be to hash the bounding box of the focal element, but this could cause frequent collisions, since it is common to have spatially close focal elements related to the same BBA. On the contrary, polygon hashing can make direct use of the vertex data, thus not requiring any additional preprocessing step.

The hashing capability of the proposed representation may provide benefits not only in case of BBAs combination rules, but for any operator which implies mass accumulation. Let us consider the case of coarsening [START_REF] Denoeux | Approximating the combination of belief functions using the fast moebius transform in a coarsened frame[END_REF]. Given two discernment frames Ω 1 and a finer Ω 2 , let us define a refining function ρ from

2 Ω1 to 2 Ω2 , such that {ρ({o}), o ∈ Ω 1 } is a partition of Ω 2 and ∀A ⊆ Ω 1 , ρ(A) = ⋃ o∈A ρ(o).
Let us consider the coarsening function ρ -1 . According to [START_REF] Denoeux | Approximating the combination of belief functions using the fast moebius transform in a coarsened frame[END_REF],

the least committed solution for defining ρ -1 is the following outer reduction function:

∀B ⊆ Ω 2 , ρ -1 (B) = {o ∈ Ω 1 s.t. ρ(o) ∩ B ≠ ∅} .
The BBA m Ω2↓Ω1 defined on Ω 1 from a given BBA m Ω2 , defined on Ω 2 , and the coarsening function ρ -1 , is given by:

∀A ∈ 2 Ω1 , m Ω2↓Ω1 (A) = B⊆Ω2,ρ -1 (B)=A m Ω2 (B).
It follows that the derivation of m Ω2↓Ω1 can largely benefit from hashing, since a focal element mass may be the result of several fragmented masses. Similar deductions can be derived for operations such as conditioning [START_REF] Shafer | A mathematical theory of evidence[END_REF], or marginalization of discernment frames defined as Cartesian products.

Example 3. Figure 1b illustrates the result of the conjunctive combination of the sources introduced in Figure 1a. Seven focal elements are produced.

Canonical decomposition and cautious rule

Canonical decomposition of a belief function allows us to represent a complex non-dogmatic BBA1 as the result of a combination (conjunctive combination will be referred throughout the discussion) of elementary belief states, namely Simple Support Functions (SSF) if the decomposed BBA is separable or a mixture of SSF and Inverse Simple Support Functions (ISSF) otherwise. The canonical decomposition, besides being a convenient representation for some combinations, has its interest into allowing the introduction of new combination rules, as the Denoeux cautious conjunctive rule, that is the least committed rule among conjunctive ones [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF].

The decomposition of a non-dogmatic BBA, defined by Smets [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF], uses the concept of generalized Simple Support Function (GSSF), defined as:

µ ∶ 2 Ω → R, µ(A) = 1 -w, µ(Ω) = w, µ(B) = 0 ∀B ∈ 2 Ω {A, Ω} ,
where A ≠ Ω and the weight w ∈ R + . The original BBA m can be then expressed as a combination of basic GSSFs: m = ∩ A⊂Ω A w(A) . The conjunctive weight function w(⋅) is associated to any hypothesis included in discernment frame Ω:

ln w(A) = - B⊇A (-1) B -A ln q(B), ∀A ⊂ Ω
According to GSSF definition, only weights w(A) ≠ 1 are useful for representing the original BBA (i.e., not leading to a vacuous GSSF). While consonant BBAs represent a special case for weights computation, where an iterative algorithm with linear complexity in terms of the number of focal elements exists, the generic case raises computational problems.

In the 1D case, the fastest weight computation approach exploits the Fast Möbius Transform (FMT) [START_REF] Kennes | Computational aspects of the Mobius transformation[END_REF] for transforming the 2 Ω array of masses (dense representation) to a 2 Ω array of commonalities q, and finally to a 2 Ω array of weights. While this procedure is convenient for small Ω cardinalities, it is computationally infeasible for large discernment frames, like in the 2D case.

In this work, we propose to compute efficiently the canonical decomposition by constructing an ad-hoc discernment frame specific to the considered BBA.

The idea is that, even if the considered 2D discernment frame Ω is vast, for the considered BBA, the number of focal elements is limited and generally they are less than a few tens. Thus, the considered BBA can be represented on only a very restricted subpart of Ω with an effective spatial resolution that depends on the actual focal elements and will generally be much coarser than Ω resolution.

Even more, the 2D structure of the focal elements is useless provided that the interaction properties between focal elements are preserved. Thus, for a given BBA, we aim to compute the coarsest possible equivalent representation where each element can be viewed as a unitary piece of information. If one retrieves this alternative representation, then it may be transformed into a 1D equivalent (by processing each of its elements as a singleton hypothesis) where the discernment frame is small, and thus suited for the FMT computation. Thus, the canonical decomposition no longer depends on the shape and original cardinality of the focal elements, but on their ad-hoc representation.

From m Ω to coarse representation.

∀D i ∈ D, ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ D i ⊂ X , D i ∩ D j = 0, ∀D j ∈ D, i ≠ j ∀A ∈ A, D i ∩ A ≠ 0 ⇐⇒ D i ⊆ A (a)
h l = ⋂ k=1...m S l,k ,
representing the labels of all the disjoint sets included into Dl . The resulting D l will be obtained as:

D l = Dl ∖ {D h } h∈h l
If the sets are implemented as bit strings, the disjoint sets retrieval is as fast as m bitwise operations. After the difference operation, the resulting disjoint set could be empty, and so ignored. Algorithm 2 provides a detailed outline of the set of disjoint sets extraction procedure through depth first search traversal.

D = ⋂ i I i D I 1 I 2 I 3 I 4 A ✓ ✓ ✓ D A = DA B ✓ ✓ ✓ D B = DB C ✓ ✓ D C = DC ∖ {D A , D B } D ✓ ✓ D D = DD ∖ {D A } E ✓ D E = DE ∖ {D A , D B , D C , D D } F ✓ D F = DF ∖ {D A , D B , D C }
m Ω ′ ⋃ s∈S k {s} = m Ω (A k )
Given that the cardinality of the ad-hoc 1D discernment frame Ω ′ is lower than a few tens of elements in practical cases, it is then suitable for the applica- Such canonical decomposition approach is now fully scalable with the cardinality of the discernment frame, and it is especially convenient when the number of focal elements is much smaller than Ω . Since the conjunctive canonical decomposition is trivially propagated when applying the conjunctive rule to two canonically decomposed BBAs, the typical scenario of applying the decomposition (e.g., for tracking), is at the BBA construction stage and when BBA approximation is needed. At BBA construction stage, the number of focal elements is usually contained, and the consonant property of a BBA may be exploited for even faster computation. At BBA approximation stage, the number of focal elements is intentionally reduced, while the BBA is not consonant in general, making it the ideal scenario for the exploitation of the presented approach.

The canonical decomposition extraction approach allows us to use an alternative combination rule, which is particularly useful when the source cognitive independence assumption (assumed by the conjunctive rule) is not valid. The cautious rule [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] between two sources m 1 and m 2 , with w 1 and w 2 associated canonical decomposition weight functions, is defined as:

m 1 ∧ m 2 = ∩ ◯ A⊂Ω A w1(A)∧w2(A)
where ∧ denotes the minimum operator. In algorithmic terms a new canonical decomposition is built by including all the elements of the two initial decompositions with weight value lower than one. As for the case of the conjunctive rule, hashing can still be used for fast lookup of equal elements in the two decompositions.

Evidential q-relaxation

Recent work [START_REF] Pichon | A consistency-specificity trade-off to select source behavior in information fusion[END_REF] introduces a BBA combination method which is robust to unreliable sources. The evidential q-relaxation, inspired by its equivalent in interval analysis (IA), allows us to relax a given number of sources when combining several belief functions. Let us denote H N r the hypothesis that only r out of N sources are relevant, i.e., q = N -r have to be relaxed. Let us call

A = {A 1 , . . . , A N }, as an N-tuple of hypotheses, for A i ⊂ Ω, i ∈ [1, N ].
Out of the N hypotheses forming an N-tuple, only r must be kept. Such meta-knowledge can be mapped as [START_REF] Pichon | A consistency-specificity trade-off to select source behavior in information fusion[END_REF]:

Γ A (H N r ) = ⋃ A ′ ⊆{A1,...,A N }, A ′ =r ⎛ ⎝ ⋂ A∈A ′ A ⎞ ⎠
For any element B ⊆ Ω, its mass will be the sum, over all Γ A (H N r ) which are equal to B, of the products of masses of the focal elements of A:

∀B ⊆ Ω, m H N r (B) = A⊆Ω N ,Γ A (H N r )=B N i=1 m Ω i (A i )
Such a rule corresponds to a generalization of classic combination rules, since the special case of r = N (i.e., do not relax any source) corresponds to the conjunctive rule, while the case r = 1 corresponds to the disjunctive rule.

In computational terms, when considering the computation of the Γ A (H N r ) terms that appear combinatorial in terms of N and r, the algorithm has higher time complexity than classic combination approaches, depending on the value of q. However, even for small values of q, such a method can dramatically improve the fusion performance in presence of outlier sources. Moreover, the proposed representation boosts (once more) the efficiency of the method, in terms of the efficient basic operators (the method makes heavy use of intersection and union operators), as well as of the use of hashing for fast accumulation of elementary masses.

Decision making

Once the different sources have been combined, the decision is generally taken on singleton hypotheses ω by maximizing the pignistic probability, defined as:

∀ω ∈ Ω, BetP (ω) = 1 1 -m(∅) B⊇ω m(B) B .
Even if the search space size is now Ω , the decision making process is dependent on the cardinality of the discernment frame, and thus not scalable, limiting the precision level which can be set for a specific context.

In order to overcome this limitation, we propose a maximization algorithm which is independent from the cardinality of the sets, and which is only related to the number of focal elements in the BBA.

I m = ⋂ A k ∈ Ã A k , Ã ⊆ A, I m > 0 s.t. ∄A s ∈ A ∖ Ã, A s ∩ I m > 0.
The underlying idea is that, since BetP is an additive measure, its maximum value can be achieved only for elements of the discernment frame which present maximal intersections.

The set X * of hypotheses that maximize the BetP is researched within the set of maximal intersections I:

X * = arg max Im∈I BetP (I m ) I m ,
where the BetP function for compound hypotheses derives from the generalized formula:

∀A ∈ 2 Ω , BetP (A) = 1 1 -m(∅) B∈A,B∩A≠∅ A ∩ B B m(B).
Consequently to this formulation, the BetP maximization algorithm boils down to the subproblem of maximal intersection search. The solution of this subproblem may exploit of the graph-based representation presented in Section 2.2 for fast lookup of maximal intersections. Proof. Let us assume that I m is redundant. Thus, there exists a superpath leading to the same intersection. Then, I m cannot be maximal.

Let us assume that P m is a subpath of another non-redundant path P n , n > m. Thus, since non-redundant paths cannot be dead paths, P n leads to a non empty intersection. Then, I m cannot be maximal.

The graph-related definition of maximal intersection implies that any intersection not being located at a leaf of the dynamic graph cannot be a maximal intersection. The graph is said dynamic in the sense that a leaf is not only a node with no outgoing edges, but it is any node for which, given the current path, no outgoing edge can be explored further without leading to a dead path.

Then, each leaf l and the resulting I l is a candidate for maximal intersection.

However, it could be non-maximal, as its associated set à could be a subset of a maximal intersection which has already been found. So, when a maximal intersection I m is found, the list p m of focal sets involving it is stored (using a bit-set representation). Once the new candidate I l is produced, the p l list is tested for inclusion against the stored candidates (by an AND operation between the bit-sets). Algorithm 3 provides full details on the depth first search strategy for the computation of maximal intersections.

Path

Maximal intersection

⟨v 1 → v 2 → v 3 → v 6 ⟩ yes ⟨v 1 → v 2 → v 4 → v 5 → v 7 ⟩ yes ⟨v 1 → v 3 → v 6 ⟩ no ⟨v 1 → v 4 → v 5 → v 7 ⟩ no
Table 3: Maximal intersection search details for the illustrative example in Figure 1.

Example 6. Table 3 shows the intersection-inclusion graph traversal for maximal intersection search on the intersection-inclusion graph of the illustrative example of Figure 1. X * is selected as the one of the two maximal intersections at maximum BetP . For this example, raw traversal intersection graph would perform 42 node visits, while with the graph optimizations, presented in Section 2.2, 12 are executed. On the other hand, a straightforward BetP maximization by singleton hypothesis exploration would process 1100 locations (included into at least one focal element) with a factor 10 subsampling of the discernment frame.

Experiments

We present test results on a synthetic toy example, as well as on a real tracking application scenario, which make use of the proposed representation, as well as of our publicly available 2CoBel library, embedding all the described methodologies, and exploited throughout the entire testing. The library has full support for discernment frames which are cartesian products.

Case study: line estimation

As toy example for illustrating the applicability of the proposed representation to 2D domains, we tackle a fundamental problem in pattern recognition, namely the line estimation from a set of 2D points. This example allows us to compare as well the effectiveness of the different combination rules implemented by the framework. Given a set of planar points in the xy space, the objective is to infer the parameters of the line that fits at best the data. The Hough transform [START_REF] Hough | Method and means for recognizing complex patterns[END_REF] is a classical approach to this problem, and the evidential framework allows us to handle the intrinsic imprecise and uncertain sources of the problem in the Hough domain. By using the polar representation of lines:

ρ = x cos θ + y sin θ
we build an accumulation space in the (ρ; θ) domain in order to infer the values of the ρ ∈ (-∞, +∞) and θ ∈ [0, π) parameters. The discernment frame Ω is then defined as a rectangular polygon in the (ρ; θ) space. Since the ρ parameter is unbounded, theoretically also Ω is an open set. However, in order to respect closed world assumptions, we bound Ω to extremely large values of ρ. Due to the sparse nature of the representation, the size of the discernment frame has no impact on the algorithm performance, so extreme values of ρ equivalent to the max and min integer values supported by the hardware could be chosen.

Each data point P i = (x i , y i ) votes for a family of lines which pass through it in the xy plane. Each voted line l i j = (ρ j , θ j ) corresponds to a point in the accumulation space. The locus of all the points in the accumulation space corresponds to a sinusoid function. Such toy example extends the one presented in [START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF], which performs straight line estimation in the (α; β) space (where y = αx + β). However, such space does not parametrize any possible line, and, moreover, a small possible interval of values has been considered in order to have a discernment frame of small size. On the one hand, the (α; β) approach allows one to represent the constraints as straight lines rather than sinusoids, allowing for an inexpensive focal element representation. On the other hand, the proposed representation allows us to move to a more convenient space where complex shapes can be defined.

In classical Hough approaches, since there is an infinite number of lines passing through the same point, the space (ρ; θ) is quantized in such a way as to provide an acceptable precision. In the proposed representation, the resolution of the problem is given by the number of vertexes used to represent the polygons.

However, the scalability of the problem allows us to rescale more flexibly the accumulation space for high precision estimations. In this experimentation we scale the accumulation space at a resolution of 10 -2 for both ρ and θ (in degrees).

The BBA construction consists in widening the sinusoidal function derived from each point in the dataset with imprecision and uncertainty knowledge. We build a consonant BBA having two focal elements. The first focal element is a sinusoidal band with width equal to δρ 1 , centered around the real sinusoidal function drawn from the data. Such focal element codes the imprecision of the points location given by the line discretization in the xy space (typical if the space is in the image domain). The second focal element is a sinusoidal band with width equal to δρ 2 > δρ 1 , again centered around the real sinusoid. Such focal element encodes the uncertainty of the point location given by noisy data distribution.

Figure 4 shows several consonant BBAs (one for each data point) represented by polygonal approximations of sinusoidal bands in the accumulation space.

Given N points, the N BBAs are then combined following some combination rule into a single BBA. The solution (ρ * , θ * ) is finally obtained by performing BetP maximization on the output BBA. Since the result of the maximization is in general a closed area, and not a single point, the barycenter of the output polygonal result is considered as the proposed solution.

We test this evidential approach on simulated data, were T = 100 lines are randomly drawn in the xy space, and M = 10 points for each line are extracted at fixed x locations, under Gaussian noise assumption for the y coordinate y i ∼ N (-cos θ sin θ x i + ρ sin θ , σ). Moreover, in order to evaluate its robustness to unreliable sources, the system is tested for different numbers of outliers (0, 1 or 2), where an outlier is uniformly selected from the existing points and its y value is shifted by a constant value y 0 . In the proposed experiments, the BBAs parameters are set as δρ 1 = 2 and δρ 2 = 6, and the noise parameters are set as σ = 0.5 and y 0 = 5.

The following different combination rules are evaluated: conjunctive rule, cautious rule, q-relaxation (with q = 1 and q = 2). The results obtained are compared with baseline least squares (LS), which is by definition the optimal estimator in presence of Gaussian noise. Figure 5 shows some line estimation examples extracted directly from the simulated data used for the quantitative evaluation.

Figure 6 shows the line estimation error distribution of the different methods under varying conditions, in terms of ∆ρ = ρ * -ρ gt and ∆θ = θ * -θ gt , where (ρ gt , θ gt ) are the ground truth parameters for one line of the simulation dataset.

The performance of the various combination rules when the data is free from outliers are comparable with the optimal performance, in terms of the median error, achieved by standard LS. In such context, conjunctive and cautious rules give the same results, which is a desired property when the sources are independent. In the case of q-relaxation, even though the number of unreliable sources conjunctive rule, cautious rule, q-relaxation (q = 1), q-relaxation (q = 2).

is overestimated, the results are in line with the conjunctive rule case. When one outlier is introduced in the simulated data (by shifting the position of a random existing point), the advantage of a robust combination rule becomes evident. The conjunctive and cautious rules (which keep having comparable results with respect to each other), perform slightly better in terms of median error than the LS criterion, thus suffering less from the presence of an outlying source due to their resiliency to uncertain sources. Conversely, with respect to LS, the error distribution is more diffuse, reflecting a higher imprecision in the parameter estimation. The q-relaxation approaches (q ∈ {1, 2}) clearly outperform the other methods both in median and variance of the errors, being able to filter out the unreliable source and perform the estimate with the inlying ones. The q-relaxation with q = 2 offers comparable performance to the one with q = 1 (which is the optimal choice in this scenario), with a slightly more imprecise estimate, given by the fact that it considers as unreliable both the outlier (possibly) and an inlier, reducing the amount of useful information exploited for decision making. When a second outlier is added, as expected, the q-relaxation with q = 1 becomes insufficient producing results with are only slightly better with respect to classical conjunctive rule, while q-relaxation with q = 2 still outperforms the others. The proposed example demonstrates the interest of q-relaxation for any 2D problem with outliers (e.g., localization with GPS data), at the expense of a careful selection of the q hyper-parameter, as a trade-off between temporal performance and degree of robustness.

While the cautious rule is equivalent to the conjunctive rule for the proposed experiment in the case of independent data, we show its benefit when the source independence assumption fails. Figure 5d shows an example of line estimation where some data is clustered in the xy space. Some of the drawn points exhibit a partial correlation in both their x and y coordinates: they are clustered in a small subsegment of the x axis, while their y coordinate being drawn from the same distribution. Thus, the derived BBAs are not independent. Moreover, the number of points composing the cluster represents a non-negligible percentage of the total number of points (40% in the example). In this case, LS clearly fails because univariate Gaussian noise assumption is violated, q-relaxation fails because it factors out few outliers, but it is still attracted by the rest of the cluster. Conjunctive rule fails because, when aggregating all the votes in the accumulation space, the cluster masses accumulate giving a strong weight to the estimation of the line from which they are drawn. Since the conjunctive rule is sensitive to the cluster size, it behaves estimating a wrong solution which tries to average the two lines. Conversely, cautious rule estimates the correct line accurately, because it processes the cluster of dependent points as a whole, thus not being influenced by the number of points composing it. Figure 7 shows the disjoint set segmentation for efficient canonical decomposition (estimation of the ad-hoc 1D discernment frame, see Section 3.2), for a generic BBA as the one obtained by iteratively combining sinusoidal polygons. Such illustration points out that the computation of these disjoint sets is non trivial in general, while producing a segmentation of the discernment frame which is extremely convenient for canonical decomposition. In the presented scenario, since the starting BBAs are consonant, their canonical decomposition can be trivially computed as a special case at initialization time, and propagated after each cautious rule application as by definition.However, our aim here was to check the efficiency of our approach.

Case study: pedestrian tracking

We apply the proposed representation to the problem of tracking pedestrians detected by imprecise sensors, on the ground plane. The belief function framework allows for direct modeling of the imprecision associated with the detections and the tracks and provides a measure for data association between detections and tracks.

We make use of the detector proposed in [START_REF] Pellicanò | Geometry-Based Multiple Camera Head Detection in Dense Crowds[END_REF], which performs low level information fusion from multiple cameras in order to provide a dense pedestrian detection map, together with pedestrian height estimations, in a range between 1.4 m and 2 m. The output of the detector allows us to project and track the detections on the ground plane. We demonstrate the use of the 2D polygon representation provided in the 2CoBel library in order to perform joint multiple target tracking in the Sparse sequence presented in [START_REF] Pellicanò | Geometry-Based Multiple Camera Head Detection in Dense Crowds[END_REF]. We perform tracking on the provided detections for 200 frames of the Sparse sequence, and we measure the localization error of the real tracks (13 pedestrians, 4 standing and 9 moving) with respect to the ground truth. The tracker has to reconstruct lost tracks for given mis-detections occurring for up to six consecutive frames on the same pedestrian.

Discernment frame definition

The area under analysis is the ground plane region where the field of views of the cameras overlap. The area of the analysis region is 330 m 2 . The algorithm is run at a resolution of 10 -4 m, so that the cardinality of the discernment frame is Ω = 33 × 10 9 . While the desired localization precision is 10 -2 m, the chosen resolution is higher for increasing the robustness to rounding errors.

BBA construction and assignment

Given a detection d i at time t located in (x i , y i ), we build a consonant BBA with two focal elements. The first focal element is a disk centered at (x i , y i ) and with a radius of 20 cm, taking into account the person's head and shoulder occupancy on the ground plane; the second focal element is a ring sector (approximated by a trapezoidal shape), which embeds the height uncertainty (on the direction point towards the camera location) and the camera calibration imprecision. In order to break the symmetry, the two focal elements are not assigned with 0.5 mass each, but with 0.51 for the internal disk and 0.49 for the trapezoid. In the presented case the choice of the mass allocation has a negligible impact on the quantitative results.

Data association and combination

Given a set of tracks at time δ, T = {t 1 , . . . , t k } and a set of detections D = {d 1 , . . . , d h }, the data association aims to compute an optimal one-to-one association solution A l = {(t i , d j ), i ∈ {1 . . . k} , j ∈ {1 . . . h}} with respect to some defined cost. One (t i , ∅) association means that the track is into an inactive state (so it keeps propagating until it associates with a new detection or dies), while one (∅, d j ) association means a new track has to be initialized with detection d j . We make use of the criterion in [START_REF] Ristic | The TBM global distance measure for the association of uncertain combat id declarations[END_REF] to define the association cost:

C ti,dj = -log 1 -m ti ∩ m dj (∅) ,
which expresses the data association task as a conflict minimization problem, which can be solved by the use of the Hungarian algorithm [START_REF] Munkres | Algorithms for the assignment and transportation problems[END_REF][START_REF] Jonker | A shortest augmenting path algorithm for dense and sparse linear assignment problems[END_REF].

The data association task is followed by a conjunctive combination which produces for every (t i , d j ) the new track:

mti,δ = m ti,δ ∩ m dj ∩ m p ,
where m p corresponds to the prior. It performs a masking operation on the visible region of interest of the camera on the ground plane.

BBA simplification

A BBA simplification step is essential in tracking applications for two different reasons. First, we want to avoid that the number of focal elements grows without control as the time progresses, because it would mean that the real-time performance of the algorithm would degrade in time, bounding the maximum number of processed frames. Second, we want to avoid an excessive fragmentation of the belief. The BBA simplification aims at reducing the number of focal elements of a given BBA while respecting the least commitment principle. We adopt the method proposed in [START_REF] André | Evidential framework for data fusion in a multi-sensor surveillance system[END_REF], which chooses iteratively two focal elements to aggregate (by performing an union operation) as the ones which minimize the Jousselme's distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] between the original BBA and the summarized BBA, i.e., the one obtained after the aggregation.

The proposed representation allows, conversely to the one in [START_REF] André | Evidential framework for data fusion in a multi-sensor surveillance system[END_REF] (which simplifies the BBA after each conjunctive combination), to perform the simplification on a less frequent time step. In the proposed experiment a target BBA is simplified when it reaches 15 focal elements, by producing a 5 focal element BBA.

BetP maximization

At each time step, we run the BetP maximization algorithm presented in Section 4 for each active track mti,δ in order to extract the most probable location of the target. The cardinality of the resulting polygon represents the irreducible ambiguity in the target location. The target position is then estimated as the barycenter of the polygon.

Modeling the imprecision of the tracks prediction

Given the track mti,δ , which represents the result of the conjunctive combination, we need to model the prediction step imprecision. In order to model the track displacement from the current location, a random walk term is added to the track. Such term boils down to an isotropic dilation of the focal elements.

In the proposed representation, this corresponds to applying a scalable poly-

Results

Figure 9 show some qualitative results of pedestrian tracking in the Sparse sequence, highlighting the tracks estimated after the first 20 frames. In order to evaluate quantitatively the tracking accuracy, the target predicted locations are compared against an available ground truth. Such ground truth consists into coordinates in the image space where the heads are located. Since the height of such individuals is not known a priori, each location in the image space projects to a segment in the ground plane, allowing for any possible height in the interval of study. One computes the localization error as the distance between the target estimated location, and the ground truth head location, under the assumption that the height of such head corresponds to the predicted one. Such metric corresponds to computing the distance between the ground truth segment and a height uncertainty segment drawn at the target location. Target locations for inactive track states are estimated by linear regression fit of the estimated target positions at previous states. Table 4 shows the average localization error obtained by the tracking algorithm for different choices of the resolution at which the discernment frame is discretized. When a coarse resolution of 10 cm is considered, the performance drops consistently. At this resolution the size of the discernment frame is already large enough to be intractable using methods based on binary representations, as in [START_REF] André | Evidential framework for data fusion in a multi-sensor surveillance system[END_REF]. Moreover, while for the theoretically desired resolution of 1 cm the average localization error consistently drops, the proposed representation allows us to scale at finer resolutions to account for rounding errors, thus providing an additional performance boost.

For more complex tracking scenarios, the next step is to integrate the proposed representation in a more sophisticated model such as [START_REF] Tran | Evidential box particle filter using belief function theory[END_REF], which is supposed to cope with specific issues such as disambiguations or long term occlusions, and where our approach would extend box representations.

Conclusion

This paper proposed a new representation for multi-modal information fusion in bi-dimensional spaces in the BFT domain. Such representation exhibits uniqueness, compactness, space and precision scalability, which make it suitable for many settings constrained to large hypothesis spaces, where there is the need to extend the Belief Function framework with efficient multidimensional operators. In our experiments with actual data, we show the effectiveness of this formulation on multi-target tracking scenarios, where tenths of tracks have to be estimated on a wide region of interest. The main contributions can be summarized as follows:

• The proposal of a new polygon-based compound hypothesis representation, able to benefit from fast polygon clipping and hashing algorithms for scalability.

• The introduction of an intersection-inclusion directed acyclic graph to model the interaction between focal elements.

• The outline of efficient algorithms for the fundamental operators, decision making and decomposition methods which fully exploit the potential of both the geometric and graph representation proposed.

• The release of our contribution as a public library for the community, in order to ease the reproducibility of such representation for active research.

For future work, we are interested in developing a tracking algorithm for dense crowds, by performing cautious fusion of multiple detection sources provided by a smart camera network. We intend to highlight the interest of efficient 2D BFT representations for scaling such algorithms for high density crowds. In such contexts, the number of targets to track jointly can become intractable for state-of-the-art tracking frameworks, and an efficient evidential framework should fully benefit from the richer information provided by multiple cameras.

Besides multi-target tracking applications, we also aim to study the impact on our BBA representation when dealing with continuous discernment frames, since, despite some notable works, e.g., [START_REF] Ristic | Belief function theory on the continuous space with an application to model based classification[END_REF][START_REF] Ramasso | Joint prediction of continuous and discrete states in time-series based on belief functions[END_REF][START_REF] Fiche | Features modeling with an α-stable distribution: Application to pattern recognition based on contin-915 uous belief functions[END_REF], belief functions have not been widely adopted yet in real number (1D or 2D) estimation problems mainly 795 because of computational limitations.

A. Graph-based representation construction details

In the following, the construction of the intersection-inclusion graph from a given BBA is detailed. Algorithm 1 outlines the main steps for graph construction (specialized in Algorithm 4) and graph traversal (by iteratively executing 800 either Algorithm 2 or Algorithm 3 at each root node). for each v i ∈ V do if l l j is not null then continue; //root suppression end DFS((V, E), A, i, l l , v i , A i , {} , {} , {}) //either Algorithm 2 or 3 end end

Figure 1 :

 1 Figure 1: Illustrative localization example. (a) BBA definition through its focal elements: camera detection m 1 (red), track at t -1 m 2 (green), road presence prior m 3 (blue), building presence mask m 4 (gray). (b) Focal elements obtained as a result of performing a conjunctive combination over the defined BBAs. (c) Intersection-inclusion graph and the result of graph simplification. The solid lines show the inclusion relationship, while the dashed lines highlight the intersection relationship. X * is the set with maximum BetP value, retrieved as the result of the proposed BetP maximization method.

Figure 2 :

 2 Figure 2: Example of representation of the focal element P (containing a hole), as a set of polygons. The external and the internal circular paths are stored in counter-clockwise and clockwise directions respectively.

Figure

  Figure 1c illustrates the result of unoptimized graph construction. Intersection relationships are shown as dashed arrows, while inclusion relationships are depicted as solid arrows. The optimization steps are shown in Table1. First,

Definition 3 . 1 .

 31 A set of disjoint sets D is a partition of the disjunction X = ⋃ A∈A A of the set of focal elements A, where each element D i (namely, a disjoint set), satisfies:

Figure 3 :

 3 Figure 3: Illustrative example of coarse discernment frame extraction for canonical decomposition. (a) Initial BBA definition (focal elements are labeled); (b) Optimized intersectioninclusion graph for the given BBA: since I 4 is included in both I 1 and I 2 , the edge between v 1 and v 4 has been deleted by graph simplification; (c) Final set of disjoint sets extraction (disjoint sets are labeled). In order to stress that the x and y axes are generic (dependent on the application), they are not labeled.

Example 4 .

 4 Figure 3 shows the disjoint set decomposition on a 2D didactic example. Each disjoint set corresponds to a subset of one or multiple focal elements which does not span over a focal element boundary. Table 2 specifies the disjoint set computation procedure, as D elements are extracted in the order assigned by the graph traversal. Each row corresponds to a path which possibly leads to a disjoint set. The candidate disjoint set DA , for example, is the result of I 1 ∩ I 2 ∩ I 3 . Candidates are then transformed into actual disjoint sets by the difference operator. Let us specify the case of DD . Since DD is the intersection between I 1 and I 3 , we focus on the sets S 1 = {A, B, C} and S 3 = {A}. In this example, the content of S 1 means that, among all the already extracted D elements, D A , D B , D C are included into I 1 . The vector of indexes to subtract is computed as h l = S 1 ∩ S 3 = {A}. Thus, among all the already extracted D elements, DD includes the disjoint set D A , which has to be subtracted. Finally D D = DD {D A }. The intersections I 2 ∩I 3 and I 2 ∩I 4 are not explored, since both I 3 and I 4 are included in I 1 , which is an already explored root (early stopping). Moreover, for the same reason, nodes corresponding to I 3 and I 4 are not used as root (root suppression).

From the coarse representation

  to 1D BBA. As soon as the D set is fully constructed, the sets S k serve to the conversion between the original BBA and a compact 1D representation. The new 1D BBA has a new discernment frame Ω ′ of cardinality D . The indexes of the disjoint sets represent the singleton hypotheses the 1D BBA in Ω ′ . Each focal element A k is converted to a compound 1D hypothesis by using the S k , which stores the indexes of the disjoint sets in D which, when performing a union operation, form the exact original set. Thus, each A k gives rise to:

Example 5 .

 5 tion of the FMT for the weight computation. Once the weights along with the corresponding canonical decomposition sets are retrieved, the canonical decomposition of the original BBA can be obtained by mapping the 1D decomposition sets, expressed as union of singleton 1D hypotheses, to 2D sets, expressed as union of elements of D We refer to the decomposition depicted in Figure 3. The new discernment frame is Ω ′ = {A, B, C, D, E, F }. All the original focal elements translate to focal elements in Ω ′ . For example, m Ω ′ ({A, D}) = m Ω (I 3 ).

Definition 4 . 1 .

 41 Given a set of focal elements A = {A 1 , ⋯, A n } a maximal intersection I m is derived from the set of focal elements à ⊆ A, such that any different focal element added to à would lead to an empty intersection:

Corollary 4 . 1 .

 41 Given the intersection-inclusion graph G, a maximal intersection I m is represented by a non-redundant path P m which is not a subpath of any other non-redundant path.

5. 1 .

 1 The 2CoBel library2CoBel is an open source 2 evidential framework embedding essential functionalities for generic BBAs definition, combination and decision making. An Evidence object defines common operations for a BBA containing any generic type of FocalElement. The current supported methods are: mass to Belief Functions conversion (plausibility, belief, commonality), conjunctive, disjunctive, cautious (exploiting the proposed canonical decomposition) rules and qrelaxation, vacuous extension and marginalization, conditioning, discounting, (generalized) BetP computation, BetP maximization (with singleton hypothesis enumeration or maximal intersections). Different representations of FocalElement are supported, each of them defining specifically basic operators (intersection, union, equality, inclusion): unidimensional (hashable), representing the 1D focal element as a binary string; 2D bitmap, providing a bitmap representation as in[START_REF] André | Evidential framework for data fusion in a multi-sensor surveillance system[END_REF]; 2D box set, implementing the definition and focal elements simplification operations proposed in[START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF]; 2D polygon (hashable), implementing our proposed representation.

Figure 4 :

 4 Figure 4: Example of BBAs construction for line estimation in the accumulation space. Every consonant BBA (one for each color), represents the information conveyed from a data point.

Figure 5 :Figure 6 :

 56 Figure 5: Example of line estimation results for different numbers of outliers: (a) no outliers; (b) one outlier (conjunctive and cautious rule lines are identical); (c) two outliers; (d) line estimation in presence of correlated source data: cautious rule outperforms the other methods.

Figure 7 :

 7 Figure 7: Example of disjoint sets decomposition on complex BBAs (obtained by iterative cautious combination of source BBAs); (a) after one combination; (b) after 2 combinations.

Figure 8 :

 8 Figure 8: Example of pedestrian tracking steps. (a) Pedestrian detection blob. (b) Focal elements of detection BBA m d 0 on the ground plane at t = 0 (the size of the largest focal element is approximatively 1 × 2 square meters). (c) Focal elements of the conjunctive combination mt 0 ,7 between the track and the associated detection at t = 7 (16 focal elements). (d)Focal elements of the BBA simplification of mt 0 ,7 with the Jousselme's distance criterion (5 focal elements). (d) Focal elements after dilation of the track BBA m t 0 ,8 by polygon offsetting.

Figure 9 :

 9 Figure 9: Pedestrian tracking. (a) Detection blobs on the image space (t = 0) estimated by the detector in [33]. Colors refer the estimated height values from 1.4 m (red) to 2 m (green). (b) Focal elements of the detection BBAs on the ground plane (t = 0). (c)Focal elements of track and detection BBAs on the ground plane (t = 8). Associated tracks and detections share the same color. (d) Final estimated tracks on first 20 frames. Red crosses refer to target locations, while colored sets correspond to regions presenting maximum BetP value.

  gon offsetting algorithm, having O(n log n) complexity, where n is the number of vertexes. Polygon offsetting allows for a dilation which respects the inclusion relationship of the original focal elements. The result of such step is the predicted track m ti,δ+1 at time t + 1.

Figure 8

 8 Figure 8 depicts an example of the proposed tracking steps for a single

Figure 10 :

 10 Figure 10: Normalized histogram of the localization error of pedestrian tracking on the Sparse sequence.

Figure 10

 10 Figure 10 shows the results in terms of (normalized) histogram of localization error. The average localization error is = 0.2 m, which reaches the empiric

  limit set by the intrinsic uncertainty of head spatial occupation. On the other hand, the average localization error remains steady in time, meaning that the estimated tracks do not tend to drift away from the real ones. The standard deviation of the average localization error in time is σ = 2.3 cm.

Algorithm 1 :

 1 Graph construction and traversalData: Set of focal elements A ordered by decreasing cardinality; begin (V, E, l l , l h ) =BuildGraph(A);

  1 , v 2 , . . . , v m ⟩.

	Definition 2.1. A path P	(m) k	is called dead if the intersection among the m
	focal elements corresponding to its nodes is the empty set.
	Definition 2.2. Given two paths P	(m) k	and P h , P (n) k (m)	is called superpath of
	P h (n)	if m > n and:
					∀v ∈ P h (n)	⇒ v ∈ P	(m) k	.
	Conversely, P h (n)	is called subpath of P k (m)	.
	Definition 2.3. A not dead path P k (m)	, leading to the intersection I k is called
	redundant if there exists another path P h (n)	leading to the intersection I h , such
	that I h = I k , and P h (n)	(m) k is a superpath of P

Table 2 :

 2 Coarse representation computation from graph representation.

Table 4 :

 4 Average localization error on theSparse sequence using different discretization resolutions. By using a representation able to deal with finer resolutions, one may achieve a significant performance gain.

Dogmatic BBAs are transformed into non-dogmatic ones by an discounting.

Implementation available at: https://github.com/MOHICANS-project/2CoBel

for each e ij = (v i → v j ) ∈ E do if l l j < r then continue; //early stopping end for each e ij = (v i → v j ) ∈ E do if l l j < r then continue; //early stopping end