Jimmy Francky Randrianasoa
email: randrianasoa@unistra.fr

Camille Kurtz

Éric Desjardin

Nicolas Passat

Binary Partition Tree Construction from Multiple Features for Image Segmentation $

Keywords: binary partition tree, morphological hierarchies, multiple features, graph-based image processing, image segmentation

In the context of image analysis, the Binary Partition Tree (BPT) is a classical data structure for the hierarchical modeling of images at different scales. BPTs belong both to the families of graph-based models and morphological hierarchies. They constitute an efficient way to define sets of nested partitions of image support, that further provide knowledge-guided reduced research spaces for optimization-based segmentation procedures. Basically, a BPT is built in a mono-feature way, i.e. for one given image, and one given metric, by merging pairs of connected image regions that are similar in the induced feature space. Our goal is to design a new family of BPTs, dealing with the need to directly manage multiple features within its building process. Then, we propose a generalization of the BPT construction framework, allowing one to embed multiple features. The cornerstone of our approach relies on a collaborative strategy used to establish a consensus between different metrics, thus enabling to obtain a unified hierarchical segmentation space. In particular, this provides alternatives to the complex issue of metric construction from several -possibly non-comparable-features. To reach that goal, we first revisit the BPT construction algorithm to describe it in a graph-based formalism. Then, we present the structural and algorithmic evolutions and impacts when embedding multiple features in BPT construction. Final experiments illustrate how this multi-feature framework can be used to build BPTs from multiple metrics computed through the (potentially multiple) image content(s).

Introduction

Context

In image processing and analysis, segmentation is a crucial task. The concept of segmentation is also quite generic from various points of views: in terms of semantics (from low-level definition of homogeneous areas to high-level extraction of specific objects), in terms of definition (object vs. background or total partition of the image support), and in terms of algorithmics (region-based or contour-based approaches).

In this context, morphological hierarchies propose a wide range of data structures for modeling images at various scales, allowing for the definition of connected operators [START_REF] Salembier | Connected operators: A review of regionbased morphological image processing techniques[END_REF]. Mainly based on the theoretical frameworks of graphs and mathematical morphology [START_REF] Najman | A graph-based mathematical morphology reader[END_REF] [3, Chapters 3, 7, 9], these approaches have already proved their efficiency in many imaging applications. (The algorithms to build and handle them are generally of linear or quasi-linear time and space complexity.) Their very principle is to embed images in a dual spatial / spectral representation space, composed of shapes (i.e. spectrally homogeneous and spatially coherent regions) together with their spatial (neighbouring) and hierarchical (inclusion) relations. These representations offer a structured space to find the best regions / scales according to the applicative objective using, e.g. high-level features to describe the image regions and their content.

Among these representations, the Binary Partition Tree (BPT) [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF] is a hierarchical representation of an image modeled as a tree structure, where each node is a connected region. Each of these nodes is either a leaf -an elementary region-or models the union of the regions of its two children nodes. The root is the node corresponding to the entire support of the image. Practically, a BPT is built from its leaves, provided by an initial partition of the image support, to its root, in a bottom-up fashion. This is done by iteratively choosing and merging two adjacent regions which minimize a merging criterion, based on a given metric, computed between them. The BPT structure allows users to explore the image at different scales. It can be used for various tasks such as segmentation, image retrieval, object recognition and visual browsing.

As other hierarchical structures, the BPT was mainly designed to process one image at a time. Furthermore, in contrast with most of them (e.g. componenttrees, trees of shapes) that are intrinsically defined from the image content, the BPT is also designed to embed an extrinsic metric that is used, together with the image, to build a mixed image / knowledge model. In other words, a BPT is generally built for one image and one metric.

Motivations and Contributions

The BPT is already known as a relevant data structure for the design of image processing and analysis tools, e.g. for video analysis, remote sensing or medical imaging. Until now, the way to build this data structure has remained mostly limited to a one image, one metric paradigm.

Indeed, on the one hand, the metric -i.e. the merging criterion for successive node merging-is a scalar function. When several kinds of information (e.g. colorimetric and geometric heterogeneity) are relevant, it is then required to find a way of fusing them as a unique metric. This complex task has a strong influence on the data structure construction. Thus, it has to be carefully carried out by the expert-user before the very construction process.

On the other hand, the BPT construction deals with one input image. This means that the handling of several images generally has to be dealt with by artificially creating a "super-image", or by fusing beforehand multiple information from various spectral bands into a single metric.

Our purpose is to provide an algorithmic process for BPT construction that goes beyond these current -image and metric-limitations, leading to a notion of multi-feature BPT (MBPT, for brief).

The main idea of our approach is to consider that k images, coupled with l metrics, lead to n = k.l features. The cornerstone of the construction of a multi-feature BPT then consists of providing a way to involve all these features into the construction process, i.e. to make them interact for the definition of a relevant node merging order, and to obtain as output a unified hierarchical segmentation space.

In other words, our main contribution is the proposal of a generalized algorithmic framework for (M)BPT construction, for handling many metrics and / or many images. This algorithmic contribution extends the standard BPT construction (retrieved by setting k = 1 and l = 1). It also encompasses a wide range of cases, e.g. various metrics on one image (k = 1 and l > 1), one metric on many images (k > 1 and l = 1), or any combination of metrics on many images. Although being algorithmic, it is important to notice that our contribution is not directly related to image processing. We aim at providing an extended way to build a data structure that describes a hierarchy of partitions of an image. In other words, this provides a reduced, knowledge-guided research space, that can be further involved in various kinds of image analysis procedures: segmentation, classification, simplification, browsing. . . Such procedures fall, however, out of the scope of this article, and indeed constitute application cases of our proposal.

To reach our goal, some secondary contributions are proposed:

• First, we revisit the standard algorithmic process of BPT construction.

In particular, we split its fundamental graph-based expression (namely a graph-collapsing procedure) from its knowledge-based layers (image topology, metric definition, merging policies, etc.) This preliminary analysis is developed in Section 3.

• Second, we describe how the basic BPT construction framework can be generalized to handle multiple features. To this end, we identify the data structure requirements (Section 4.1), and their algorithmic side effects (Section 4.2). This leads to a theoretical algorithmic framework.

• Third, we propose a practical description of this algorithmic framework. Some technical implementation details are provided in Section 5. For the sake of reproducibility, we also provide an open-source library1 for the creation of MBPTs, which constitutes a technological contribution of this work. A complexity analysis (Section 5.2) describes the induced space and time cost increases of MBPT vs. BPT construction.

This work is concluded by application examples in the domain of satellite image analysis, in Section 6. In particular, we compare the behaviour of standard BPTs to MBPTs handling several images or several metrics.

The remainder of this article -which is an extended and improved version of the conference paper [START_REF] Randrianasoa | Multi-image segmentation: A collaborative approach based on binary partition trees[END_REF]-is composed of a synthetic state of the art of graph-based, hierarchical and multi-image segmentation, in Section 2; and a conclusion that emphasizes the perspectives of this work, in Section 7.

Related works

Graph-based and Hierarchical Image Segmentation

Image analysis problems, and in particular segmentation, are often considered in a discrete way via some concepts of graph theory. Practically, image points (i.e. pixels, voxels) are considered as the vertices of a graph, whereas the spatial / neighbouring relations between them are modeled by graph edges. This paradigm, democratized since the early 1970's [START_REF] Rosenfeld | Connectivity in digital pictures[END_REF], led to the development of a wide range of segmentation approaches, based on basic graph manipulations.

In this context, image segmentation could be viewed as a partial (e.g. region growing [START_REF] Adams | Seeded region growing[END_REF]), or total partitioning problem with monotonic (e.g. watersheds [START_REF] Vincent | Watersheds in digital spaces: An efficient algorithm based on immersion simulations[END_REF]) or non-monotonic transformations (e.g. split and merge [START_REF] Horowitz | Picture segmentation by a directed split-andmerge procedure[END_REF]). Some of these approaches led to the development of optimization schemes (e.g. graph-cuts [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF], random walks [START_REF] Grady | Random walks for image segmentation[END_REF], power watersheds [START_REF] Couprie | Power watershed: A unifying graph-based optimization framework[END_REF]). In the framework of mathematical morphology, these graph-based approaches gave rise to the notion of connected operators [START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF].

Graph-based segmentation allows us to obtain one segmentation result from a given image. In order to tackle the ill-posed problem of segmentation, hierarchical approaches were developed to compute families of nested partitions, providing adapted solutions at different scales. These notions of hierarchies take their origin in image models initially dedicated to optimize the access and space cost of the carried information (e.g. octrees [START_REF] Yau | A hierarchical data structure for multidimensional digital images[END_REF]). These regular models were progressively shifted toward image / content-guided, irregular hierarchies [START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF].

From this point on, several hierarchical image models were developed, mainly in the framework of mathematical morphology. The most popular are component-trees [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF], trees of shapes [START_REF] Monasse | Scale-space from a level lines tree[END_REF][START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF], hierarchical watersheds [START_REF] Najman | Geodesic saliency of watershed contours and hierarchical segmentation[END_REF], hyperconnected component-trees [START_REF] Perret | Hyperconnections and hierarchical representations for grayscale and multiband image processing[END_REF], and binary partition trees [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF] (see Section 2.2). Since they provide a space of potential segmentations, instead of a single result, these hierarchical models were progressively involved in attributebased [START_REF] Jones | Connected filtering and segmentation using component trees[END_REF] or optimization schemes [START_REF] Guigues | Scale-sets image analysis[END_REF][START_REF] Passat | Interactive segmentation based on component-trees[END_REF] for segmentation purpose.

Based on these image models, generally designed as trees, further developments were proposed to allow for a better flexibility in image and parameter handling. The case of multiband images was considered, leading to data structures such as component-graphs [START_REF] Passat | Component-trees and multivalued images: Structural properties[END_REF], multivalued component-trees [START_REF] Kurtz | Connected filtering based on multivalued component-trees[END_REF] or multivariate trees of shapes [START_REF] Carlinet | MToS: A tree of shapes for multivariate images[END_REF]. Topological handling was also investigated, by allowing connectivity hierarchies in component-hypertrees [START_REF] Passat | Component-hypertrees for image segmentation[END_REF], or dealing with asymmetric hierarchies [START_REF] Perret | Directed connected operators: Asymmetric hierarchies for image filtering and segmentation[END_REF] allowing for non-directed graphs as image models. The way to embed semantic information as image values was also pioneered via the notion of shaping [START_REF] Xu | Connected filtering on tree-based shapespaces[END_REF].

Binary Partition Trees

Most of the hierarchical structures proposed in the literature are models intrinsically deriving from the image signal. For instance, component-trees represent the inclusion of the successive level-sets; trees of shapes represent the image level-lines; and hierarchical watersheds rely on saliency measures similar to gradients. These models strongly rely on a functional, often derived from the image intensity. Such regions may not correspond to objects of interest in image content, in particular when dealing with complex images.

The binary partition tree (BPT) [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF] relies on a mixed image / knowledge model. It can then easily embed expert-defined knowledge, in addition to imagebased information. From a structural point of view, BPTs present similar properties with binary space partition trees [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF], designed to efficiently model an image space, mainly in computer graphics. Indeed, BPTs provide hierarchies of nested total partitions of an image.

From an algorithmic point of view, a BPT is built by progressively merging elementary image segments (e.g. flat zones or superpixels), based on a given metric. In particular, the choice of this metric is crucial, as it has a direct impact on the adequacy of the built BPT with the targeted application. This gave rise to several works, ranging from theoretical contributions [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF] to experimental assessments [START_REF] Valero | Comparison of merging orders and pruning strategies for binary partition tree in hyperspectral data[END_REF]. The basic criteria used in most of segmentation approaches are generally radiometric or geometric region similarities (or their fusion into a single metric).

Except for a few contributions in the field of object recognition [START_REF] Giro | From partition trees to semantic trees[END_REF][START_REF] Vilaplana | Binary partition trees for object detection[END_REF][START_REF] Valero | Object recognition in hyperspectral images using binary partition tree representation[END_REF], BPTs were mainly used for segmentation / classification tasks, where such total partitions make sense from a semantic point of view. More precisely, the wider application field of BPTs is remote sensing [START_REF] Benediktsson | Hierarchical analysis of remote sensing data: Morphological attribute profiles and binary partition trees[END_REF]. In this context, BPTs were involved in multiresolution / multiscale image segmentation and classification [START_REF] Kurtz | Extraction of complex patterns from multiresolution remote sensing images: A hierarchical topdown methodology[END_REF][START_REF] Calderero | Multispectral cooperative partition sequence fusion for joint classification and hierarchical segmentation[END_REF]; for coupled optical / LIDAR data analysis [START_REF] Kurtz | Hierarchical extraction of landslides from multiresolution remotely sensed optical images[END_REF]; hyperspectral images [START_REF] Valero | Hyperspectral image representation and processing with binary partition trees[END_REF][START_REF] Veganzones | Hyperspectral image segmentation using a new spectral unmixing-based binary partition tree representation[END_REF]; polarimetric SAR [START_REF] Alonso-González | Filtering and segmentation of polarimetric SAR data based on binary partition trees[END_REF][START_REF] Salembier | Study of binary partition tree pruning techniques for polarimetric SAR images[END_REF]; mixed SAR / hyperspectral images [START_REF] Alonso-González | Processing multidimensional SAR and hyperspectral images with binary partition tree[END_REF]; or multi-temporal SAR image analysis [START_REF] Alonso-González | PolSAR time series processing with binary partition trees[END_REF].

Discussion -Contributions

Binary partition trees are built from one given metric. This paradigm is particularly well-fitted when the prior semantic information required for the construction of a mixed image / knowledge image model is indeed unique. (This is for instance the case when we are interested by patterns in satellite images that present a specific colorimetric property, such as agricultural crops with the vegetation index like the NDVI.) By contrast, when several kinds of prior semantic information are potentially useful for the construction of the BPT, one has to find a way to relevantly embed them into a unique metric. This may be a complex task, in particular when such information are not easily comparable. Until now, the most popular solution for dealing with that case consisted of defining a linear combination of various metrics, leading to a unified one. (This was, for instance, the case in [START_REF] Kurtz | Extraction of complex patterns from multiresolution remote sensing images: A hierarchical topdown methodology[END_REF] where a linear combination was proposed for mixing spectral homogeneity and compactness criteria, via an evolving trade-off parameter.)

In order to propose an alternative solution to the issue of handling simultaneously many metrics, we consider a new way of building BPTs. Our approach is built on the standard "mono-metric" BPT construction; in particular, it generalizes it.

We do not intend to regroup different criteria into a unique metric. By contrast, we consider each metric individually. Our purpose is then to involve consensual strategies (classically used in machine learning applications) dedicated to manage the different and possibly antagonistic information carried by each metric. By side effect, this consensual paradigm also allows us to encom-pass the case of processing several images / modalities of a same scene, with similar or specific metrics in each.

In this generalized framework, for a given set of chosen metrics and images, the user's task does no longer consist of defining a complex combination of metrics but, more generally, of choosing a consensus policy, that is the way the different features will define a common result. This paradigm provides a wide range of possibilities -including those previously offered by standard BPTsand may then improve the adequacy of the constructed BPTs with the user's needs for a particular application.

However, the construction process of such multi-feature BPTs is more complex than for standard BPTs. In particular, the intermediate data structures involved in the construction algorithmics must now allow for the representation and interactions of various features. This leads to more complex data structures, and a higher computational cost.

In the sequel, we first analyze the intrinsic properties of the standard BPT construction algorithm, in order to emphasize the parts impacted by the generalization to the multi-feature case. Then, we propose a theoretical algorithmic framework for MBPT construction, that generalizes the standard BPT algorithm. Finally, we propose a practical description and an implementation of this MBPT construction algorithm.

Structural Description of the BPT Construction

Definitions and Notations

This section provides formal definitions and notations mandatory to make this work self-contained.

An image is a function I : Ω → V that associates to each point x of the finite set Ω a value I(x) of the set V .

To model the fact that two points x and y of Ω are neighbours, let A Ω be an adjacency (i.e. irreflexive, symmetric) binary relation on Ω. In other words, G Ω = (Ω, A Ω ) is a graph that models the structure of the image space.

For any partition P of Ω, we define an adjacency inherited from that of Ω. We say that two distinct sets N 1 , N 2 ∈ P are adjacent if there exist x 1 ∈ N 1 and x 2 ∈ N 2 such that (x 1 , x 2 ) is an edge of A Ω , i.e. x 1 and x 2 are adjacent in (Ω, A Ω ). This new adjacency relation A P is also irreflexive and symmetric.

The Standard BPT Construction

A BPT is a hierarchical representation of an image. More precisely, it is a binary tree whose each node is a connected region. A node can be either a leaf representing an "elementary" region, or the union of two neighbouring regions. The root node corresponds to the whole image support.

We recall the classical way of building a standard BPT, as proposed in the pioneering article [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF]. The BPT construction is a bottom-up process. It proceeds from the determination of the leaves -provided by an initial partition of the image-to the root. This is done by choosing and merging iteratively two adjacent regions that minimize a criterion reflecting their likeness. This merging sequence is stored in a hierarchical structure, namely the BPT, that models the image at different scales. This is illustrated in the right part of Figure 1. A huge number of distinct BPTs may be obtained for a given initial partition of Ω. In order to determine a relevant BPT, it is then necessary to decide of the priority of the fusions between nodes. Let N i , N j ∈ P be two distinct and adjacent regions / nodes. A BPT generation relies on two main notions: a region model M r (N i ) which specifies how a region N i is characterized (e.g. colour, shape); and a merging criterion O r (N i , N j ) which defines the similarity of neighbouring regions N i , N j and thus the merging order.

A strategy commonly adopted for representing each region is to consider their average colour in a given space (e.g. RGB, HSV), and to merge pairs of adjacent regions either similar one to each other, or similar to the region model of the novel region built from their union. Another strategy [START_REF] Kurtz | Extraction of complex patterns from multiresolution remote sensing images: A hierarchical topdown methodology[END_REF] considers as region model a linear combination of radiometric and geometric features, with a merging criterion where the trade-off between these features evolves during the construction of the BPT. In any case, the merging criterion is a scalar function, which requires fusing various elements of expert knowledge in a single metric.

Structural Description: A Graph-based Point of View

In this section, we now revisit the BPT construction process. In particular, we focus on its algorithmic core, that essentially consists of a graph collapsing approach. We then rewrite the BPT construction process in a graph-based formalism, thus emphasizing the involved data structures mandatory to carry out the collapsing process, modeled by the output tree.

Graph and valuation function

The way to describe the construction of a BPT is generally considered from spatial (the way regions are built) and descriptive (the way regions are characterized and how they can be considered similar) points of view. Indeed, the classical description of the BPT construction considers as input: the image I (i.e. the geometrical embedding of Ω, and the value associated to each point of Ω); a region model, that "describes" the nodes; and a merging criterion, that quantifies the homogeneousness of nodes before and after fusion. These information are important from the point of view of a considered application. The red cells are removed, as the edge (N 3 , N 4 ) is suppressed (this edge had been chosen due to its highest position in the list). The scores of blue and orange cells are updated with respect to N 8 . The orange cells are merged by pairs. The positions of the blue and orange cells are updated with respect to their new scores. The scores of the green cells are not affected. Last: a new part of the BPT T is created by adding the new node N 8 , and linking it to its two children nodes N 3 and N 4 .

However, beneath these image and knowledge-based notions, the construction of a BPT is intrinsically a graph collapsing process. From an algorithmic point of view, the region models and merging criteria define a valuation on the edges that allows us to choose which nodes to fuse at any given step. In the sequel, we will then consider, without loss of generality, that a BPT is fully defined by only two input information (see left part of Figure 1):

1. a graph G L = (L, A L ) that models the initial partition of the image; 2. a valuation function W : (2 Ω ) 2 × V Ω → R for choosing the pair of nodes to be merged.

Structural description of the algorithm

We now consider an initial partition L of Ω. Each node L ⊆ Ω of L is assumed to be connected with respect to A Ω . This partition L defines the set of the BPT leaves we are going to build. For instance, L can be the set of the image flat zones. It is equipped by the adjacency A L inherited from A Ω . This leads to a graph G L = (L, A L ) modeling the structure of the partition of I.

The BPT is the data structure that describes the progressive collapse of G L onto the trivial graph (Ω, ∅). This process consists of defining a sequence

(G i = (N i , A Ni )) n i=0 (with n = |L|-1) as follows. First, we set G 0 = G L .
Then, for each i from 1 to n, we choose the two nodes

N i-1 and N i-1 of G i-1 linked by the edge (N i-1 , N i-1 ) ∈ A Ni-1 that minimizes the valuation function W . We define G i such that N i = N i-1 \ {N i-1 , N i-1 } ∪ {N i-1 ∪ N i-1 };
in other words, we replace these two nodes by their union. The adjacency A Ni is defined accordingly from A Ni-1 . We remove the edge (N i-1 , N i-1 ), and we replace each edge (N i-1 , N i-1 ) and / or (N i-1 , N i-1 ) by an edge (N i-1 ∪ N i-1 , N i-1 ). In particular, two former edges may be fused into a single one.

From a structural side, the BPT T is the Hasse diagram of the partially ordered set ( n i=0 N i , ⊆). From an algorithmic side, T is built in parallel to the progressive collapse from G 0 to G n . In particular, T stores the node fusion history. More precisely, we define a sequence (T i ) n i=0 as follows. We set T 0 = (N 0 , ∅) = (L, ∅). Then, for each i from 1 to n, we build T i from T i-1 by adding the new node N i-1 ∪ N i-1 , and the two edges

(N i-1 ∪ N i-1 , N i-1 ) and (N i-1 ∪ N i-1 , N i-1 )
. The BPT T is then defined as T n .

Remark. In [START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF], a graph-based definition of BPT construction is also proposed, that relies on a minimum spanning tree paradigm. However, this formalization is valid only if the merging order is associated to a valuation of the edges that is fixed a priori on the initial partition. This is not the case, in general.

Data structures

The above description of the BPT construction algorithm implies to define and update the following data structures:

• the graph G which stores nodes that remain to be merged, and their adjacency links; and

• the tree T that is progressively built.

In order to efficiently compute the valuation W , it is also important to associate each node of G to the corresponding part of the image I, e.g. via a mapping between G and Ω. The last required data structure is a sorted list W that gathers the scalar valuations of each remaining edge of G. This list contains the information for choosing the couple of nodes to be merged relatively to a given metric. One iteration of this algorithm is illustrated in Figure 2.

This choice is made in constant time O(1), since W is sorted. After the merging operation, W has to be updated: [START_REF] Salembier | Connected operators: A review of regionbased morphological image processing techniques[END_REF] to remove the edge between the two nodes; (2) to update the edges affected by the merging operation; and (3) to re-order these updated edges. Operation (1) is carried out in constant time O(1). Operation (2) is carried out in O(α.T W ), where T W is the cost of the computation of W for an edge, and α is the number of neighbours of the merged nodes (α is generally bounded by a low constant value). Operation (3) is carried out in O(α. log 2 |W|).

Multi-feature Generalization of the BPT Construction

In this section, we now describe our multi-feature generalization of the BPT construction algorithm. We propose a description of the algorithm and associated data structures in the same graph-based formalism used in the previous section for describing the standard BPT construction. In particular, we still consider that this construction -viewed as a graph collapsing problem-takes as input the graph G L = (L, A L ). However, we now have to use several valuation functions W : (2 Ω ) 2 × V Ω → R. We then discuss the structural and algorithmic side effects of using several such valuation functions "at the same time", instead of only one.

Our purpose is still to build one BPT from these input information. Introducing several valuation functions allows us to embed several features in a more independent way in the construction process. These features can represent several metrics associated to a same image; a same metric associated to several images of a same scene; or various metrics on various images of a same scene. The proposed generalization deals with the "feature" part of the construction. As stated in Section 3.3.1, we need a graph that models the initial partition L of the image(s). Our purpose remains to collapse this unique graph associated to a unique spatial scene. Practically, it implies that the (potentially multiple) images involved in the BPT construction are defined in the same spatial reference, i.e. the same support Ω. This spatial coherence assumption is generally a standard requirement in image processing (e.g. in medical imaging, via registration; in remote sensing via georeferencing; etc.). A graph G L , which is isomorphic to (Ω, A Ω ), can be obtained easily, either by subdividing Ω into one-point singleton sets or by considering flat zones or superpixels.

Then, the "graph" part of the BPT construction process remains unchanged. In terms of data structures, the generalized BPT construction will still handle one graph G, that will be progressively collapsed; and one tree T that will be built to provide the BPT. A unique mapping between N and Ω will still allow us to access to the values of a node for the different images.

. . . and what does

Let us now consider the "feature" part of the data structure. In the initial BPT construction approach, the valuation function W : (2 Ω ) 2 × V Ω → R was explicitly modeled by a sorted list W of the values of all graph edges. This list was updated during the progressive collapsing of G, by removing elements from the list; updating the values of some edges; and re-sorting edges with respect to their updated values.

We now consider n ≥ 1 valuation functions W : (2 Ω ) 2 × V Ω → R, which means that each edge is associated to n values, one for each function. By considering k distinct images and l distinct metrics, we may have up to n = k.l such valuation functions. This leads to define no longer one, but n sorted lists

W i (1 ≤ i ≤ n). Each list W i is associated with a specific valuation function W i : (2 Ω ) 2 × V Ω j → R,
defined with respect to a value set V i (see Figure 3). The handling of these sorted lists remains the same in terms of removal, value updating / resorting, as for one list.

Algorithmic Evolutions

Our purpose is now to build a BPT from these n lists by generalizing the algorithm described in Section 3.2, which initially depended on a unique list W.

From an algorithmic point of view, each iteration of the construction preserves the same organization. An edge is chosen and the two incident nodes of the graph are merged. This operation updates the nodes and edges of G, and adds a new node plus two edges in T. The main differences are now that: ... ... ... 1. n ≥ 1 sorted lists are updated; and 2. the choice of the optimal edge is made with respect to the information carried by these n sorted lists instead of only one.

At each iteration of the algorithm (see Figure 4), the choice of the optimal edge to remove, leading to the node fusion, depends on a decision. This decision is a consensus, made with respect to the information provided by these n lists. On the one hand, information are carried by the lists W i , that give relative information on edges, induced by their ordering with respect to W i . On the other hand, information are carried by the valuation functions W i : (2 Ω ) 2 × V Ω j → R that give an absolute value to each edge. These information are of distinct natures. We study their relevance according to various kinds of consensus policies. In particular, we identify three families of consensus strategies.

Absolute information consensus

Let us consider, for instance, that the consensus policy consists of choosing the edge of lowest mean valuation among the n lists W i , or the edge of minimal valuation among all lists. The first consensus (namely min of mean) is defined by a linear formulation: arg (N,N )∈N min n i=1 W i ((N, N )). The second (namely min of min) is defined by a non-linear formulation: arg (N,N )∈N min min n i=1 W i ((N, N )). However, in both cases, the decision is made by considering absolute information carried by the edges. More generally, when the information carried by the values of each edge is a sufficient knowledge, n sorted lists W i are not necessary. In such a case, a single sorted list W that contains the information of these, linear or non-linear, formulations is ) is suppressed (this edge had been chosen due to its "optimal" position and / or valuation in the n lists). The scores of blue and orange cells are updated with respect to N 8 . The orange cells are merged by pairs. The positions of the blue and orange cells are updated with respect to their new scores. The scores of the green cells are not affected.

indeed sufficient. The BPT construction involving n lists is then equivalent to that from one list.

The main difficulty raised by this policy derives from the potential heterogeneity of the values carried by the different W valuation functions. Indeed, when the features are not of same nature, their values should be normalized and / or weighted to allow for the definition of adequate fusion / comparison operators. This issue is mainly the same that occurs in most optimization schemes where a given metric is built from several terms of varying semantics. Although this remains tractable, at the cost of a certain expertise, it argues in favour of considering the next proposed policies as relevant alternatives.

Relative local information consensus

Let us now consider, for instance, that the consensus policy consists of choosing the edge that is the most often in first position in the n sorted lists W i , or the most frequently present in the r |W i | first positions in the n lists W i . These consensus (namely, majority vote and most frequent, potentially weighted) policies do not act on the absolute valuations of the edges, but on their relative positions in the lists. Another strategy can also consist of choosing the edge with the lowest mean of ranks, according to the position of the edges within the lists. In such cases, it is then mandatory to maintain n sorted lists, but the decision process does not require to access the whole lists. It can be restricted to the first (or the first r) element(s) of each, leading to a local decision process.

Relative global information consensus

Let us finally consider that the consensus policy consists of choosing the edge that has the best global ranking among the n sorted lists W i . As previously, such consensus (e.g. best average or best median ranking) policy, also acts on the relative positions of the edges in the lists, and does not consider the absolute values of the edges. However, in contrast with the above case, the decision process requires to explicitly access the whole content of all these lists, leading to a global decision process of higher computational cost.

Technical Discussion

In this section, we finally propose a technical description of the MBPT construction algorithm. This description is associated to a Java library implementing this algorithm and that we distribute online2 .

Details of the proposed algorithm

To build a MBPT, the main structure of the classical BPT construction remains unchanged. Indeed, the MBPT is still built from its leaves to its root, by choosing and merging adjacent regions that minimize a merging criterion. However, instead of dealing with a classical merging criterion on one image and one metric, we may now consider many images, different metrics, and a consensus strategy as input parameters. The core of the algorithm is divided as follows:

1. preparation of the lists W i based on each image and metric couple; 2. preparation of the graph G modeled as a Region Adjacency Graph (RAG); 3. creation of the MBPT T by merging pairs of nodes.

The general structure of the proposed algorithm is presented in Algorithm 1.

Preparation of the lists W i and the RAG

As already mentioned in Section 4.1, by considering k distinct images and l distinct metrics, we may have up to n = k.l valuation functions. This leads us to prepare no longer one, but n sorted lists W i . Each list W i contains all the edges of the graph G and is maintained ordered during the whole process. An object representing the metric is instantiated by the algorithm and linked to each list W i . At this stage, these n lists are still empty. When all the lists W i are prepared and linked to the right couple of image and metric, a graph G (implemented as a RAG) has to be built. The initial nodes of the graph are created from the pixels or from an initial partition of the image support. They constitute the leaves of the MBPT. Once these leaves are prepared, the edges of the graph are created and their values are computed by invoking particular methods of the corresponding metric. These edges represent the adjacencies between neighbouring regions of the image. For each edge, n computed metric values are associated. In parallel, we use these metric values to fill the n lists W i that will be further maintained sorted.

Creation of the multi-feature BPT by merging nodes

Once the lists W i and the graph G are ready, an iterative fusion of the nodes is operated to build the MBPT. This iterative process stops when the lists W i are empty. The root of the tree is then reached. Each iteration is mainly composed of:

1. the choice of the next two adjacent nodes of G to be merged, based on the consensus strategy; 2. the handling of the n lists W i by removing, in each list, the adjacency linking the two chosen nodes, and updating the values of all adjacencies that link them to their neighbours; 3. the resorting of the lists.

Complexity Analysis

In the multi-feature paradigm, choosing the edge to remove is no longer a constant time operation. Indeed, it depends on the way information are used and compared. Afterwards, operations (1-3) described in the standard BPT construction algorithm, for the sorted list maintenance, have to be duplicated for each list. These operations are then carried out in O(n), O(n.α.T W ) and O(n.α. log 2 |W |), respectively, where T Wi is the cost for computing W i for a given edge, while α is an upper bound for the nodes degree within the graph G.

This analysis can be refined with respect to the policies considered for choosing an edge, and the information carried by the valuation functions W i and / or the sorted lists W i . Besides, the choice of a consensus strategy is strongly application-dependent. It is then important to consider a trade-off between the structural and computational cost of the approach versus the benefits in terms of results accuracy. These costs are summarized in Table 1. This table provides the cost of an elementary step of the BPT construction. The number of these steps is equal to the size of the initial graph G L , namely |L|. More precisely, it is equal to the number of vertices in this initial graph (minus one). Indeed, each step merges two of these vertices, until obtaining a graph formed by exactly one node. At each step, at least one edge is removed from the graph. The number of remaining edges is then equal to the size of the list(s) |W i |. We can assume that the number of edges is bounded by the number of vertices of the graph, up to a multiplicative constant α, generally low for images defined on discrete grids. Based on these assumptions, an upper bound for the overall computational cost of the standard BPT construction [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF] is

|L| i=1 (O(1)+ O(log 2 |W|)) = |L| i=1 O(1) + |L| i=1 O(log 2 (α.i)) = O(|L|) + O(log 2 (|L|!)) = O(|L| log 2 |L|
), and so is the cost for the first consensus policy (Section 4.2.1). Following the same kind of calculation, the cost for the second consensus policy (Section 4.2.2) is O(n.|L| log 2 |L|). That of the third (Section 4.2.3) is O(n.|L| 2 ).

Experimental studies

Experimental protocol -Motivation and choices

Multi-feature BPTs do not define, by themselves, a segmentation method. Indeed, MBPTs -such as BPTs-are data structures, that provide a reduced space of partitions of the image support, hierarchically organized with respect to the (partial order) refinement relation. Such (M)BPTs can then further be involved in segmentation methods (but also in other tasks: detection, image simplification, classification, etc.).

Based on these considerations, our purpose is not to prove that MBPTs lead to better results for segmentation tasks compared to other segmentation methods. Indeed, this would require to involve subsequent segmentation processes on MBPTs, whose own quality evaluation could not be easily deconvoluted from that of the very data structure. By contrast, our purpose is to focus on the quality of the data structure itself. This is why we choose to compare the MBPTs with the standard notion of BPT (built from one feature) and with BPTs built from one feature obtained as the linear combination of many.

Other tree-based data structures exist for image modeling, for instance component-trees [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF], trees of shapes [START_REF] Monasse | Scale-space from a level lines tree[END_REF] and hierarchical watersheds [START_REF] Najman | Geodesic saliency of watershed contours and hierarchical segmentation[END_REF]. However, these trees are not built from features, and they require information provided beforehand. Indeed, component-trees and trees of shapes require the definition of a total order on the image values, whereas hierarchical watersheds require the definition of a saliency measure (namely, a gradient) on the image. By contrast, the (M)BPTs rely on relative information between nodes, that evolve while the organization and geometry of the nodes changes from the leaves up to the root. For these reasons, related to the different nature of the involved information, a direct comparison between (M)BPTs and such other tree structures would not provide relevant clues with respect to the advantages of a multi-feature paradigm in BPTs.

In the sequel, we then compare MBPTs with various kinds of BPTs. As stated above, this cannot be done by simply observing segmentation results, but by observing more generally the ability of (M)BPTs to potentially lead to good segmentations. Then, we need a specific validation framework dedicated to the evaluation of hierarchical image representations such as trees. Such a framework, recently proposed in [START_REF] Randrianasoa | Evaluating the quality of binary partition trees based on uncertain semantic ground-truth for image segmentation[END_REF], is described in Section 6.2; it is used for our experiments.

Since the BPTs have been mainly involved in remote sensing image processing and analysis over the past 20 years, we choose to consider two case studies within this application field. In Section 6.3, we show how a MBPT can be built from a single satellite image, by considering simultaneously various metrics. In Section 6.4, we show how a MBPT can be built from multiple satellite images sensed over the same area.

BPT quality evaluation

Many works have been dedicated to improve the construction of BPTs. However, only few works were dedicated to quantitatively evaluate the "quality" of these trees, (i.e. their ability to allow for a satisfactory segmentation), and then to determine if they were "correctly" constructed. In the case of supervised evaluation, the segmentation results are generally compared to a ground-truth (GT) map with standard quality indices based on spatial overlapping information. In the case of BPTs, such frameworks can not be easily considered, since several segmentations can be obtained from one single BPT.

We designed in [START_REF] Randrianasoa | Evaluating the quality of binary partition trees based on uncertain semantic ground-truth for image segmentation[END_REF] a supervised framework for BPT quality evaluation. Our approach is not to match an ideal partition of the image. We aim to evaluate the ability of a BPT to construct nodes that match at best with a subset of expertdefined segments. Then, we assume that a GT map, composed of reference segments S i ⊆ Ω (i ∈ [[1, k]]), is provided by an expert. Such GT segments can be labelled, allowing us to embed semantic criteria in the framework. We recall the three main points of this framework for BPT quality evaluation (see [START_REF] Randrianasoa | Evaluating the quality of binary partition trees based on uncertain semantic ground-truth for image segmentation[END_REF] for more details).

Node / segment matching metrics

First, we choose a local metric to evaluate the matching degree between a GT segment S and a node N of the BPT. We define a local score Λ(N, S) ∈ R + , where Λ is a metric evolving monotonically with respect to this similarity. The most common quality indices are based on a combination of the true positives (T P ), false positives (F P ) and false negatives (F N ) computed between N and S. Examples of Λ functions, considered in this work, are the Jaccard index J [START_REF] Jaccard | The distribution of the flora in the Alpine zone[END_REF]:

J (N, S) = |N ∩ S| |N ∪ S| = T P T P + F P + F N (1)
and the Dice coefficient D [START_REF] Dice | Measures of the amount of ecologic association between species[END_REF]:

D(N, S) = 2.|N ∩ S| |N | + |S| = 2.T P 2.T P + F P + F N (2)
In particular, these two classical quality functions were chosen as they are quite often considered for remote sensing image analysis evaluation, which is coherent with the context of the following two case studies.

Finding matching nodes in the BPT

Then, we determine the nodes within the BPT that maximize matching with the GT segments. Given k GT segments S i (i ∈ [[1, k]]), and a BPT T composed of n nodes N j (j ∈ [ [1, n]] with n = 2.|L| -1), we aim to solve k times the optimization problem: N i = arg max j∈[ [1,n]] Λ(N j , S i ). A brute-force approach would be to browse, for each GT segment S i , the whole BPT in a bottom-up way. This would involve useless comparisons. To reduce this cost, we consider two strategies.

We use a spatial constraint to "vertically" restrict the search space within the BPT. In particular, for finding an optimal node N it is sufficient, for a given GT segment S, to restrict the study to the BPT branches whose ending leaves intersect S. We also use a quantitative heuristic to "horizontally" restrict the BPT browsing. Indeed, to correctly match a GT segment S, a node N has to be of comparable size. Practically, it is relevant to restrict the actual computation of the Λ values to nodes N with size within a confidence interval [κ

-, κ + ] ⊆ N, with κ -< |S| < κ + .
At this stage, the scores Λ are computed. The score Λ(N , S) of the best node is then set as the quality score λ(S) of T, for each GT segment S.

Global quality score

Finally, we define a global quality measure that merges the local scores for the different GT segments. We define a weighted formulation of such global quality score Γ as

Γ = ∈L w Si∈C w i .λ(S i ) (3)
with ∈L w = 1, Si∈C w i = 1, and w ≥ 0, where L is the label set and C are the different semantic classes of GT segments. The weights w can be used to assess the relative importance of each semantic class C . In particular, w = 1/|L| if each class has the same importance. The weights w i can be used to discriminate the importance of each GT segment, i.e. the necessity to correctly segment it.

Case study 1: Multi-criteria segmentation

The analysis of very high spatial resolution (VHSR) remote sensing images is a challenging task. In this context, the segmentation of satellite images using classical mono-metric BPTs has been widely investigated [START_REF] Benediktsson | Hierarchical analysis of remote sensing data: Morphological attribute profiles and binary partition trees[END_REF][START_REF] Kurtz | Extraction of complex patterns from multiresolution remote sensing images: A hierarchical topdown methodology[END_REF][START_REF] Calderero | Multispectral cooperative partition sequence fusion for joint classification and hierarchical segmentation[END_REF][START_REF] Valero | Hyperspectral image representation and processing with binary partition trees[END_REF][START_REF] Veganzones | Hyperspectral image segmentation using a new spectral unmixing-based binary partition tree representation[END_REF]. This motivates the following experimentation on multi-criteria segmentation procedures on such images.

Data

The dataset used in this study (courtesy LIVE, UMR CNRS 7263) was sensed over the town of Strasbourg (France) by the Pléiades satellite, in 2012. The first sample is a VHSR image (2 000 × 2 000 pixels) representing a complex high-density urban area (Figure 5(a)) composed of different urban objects (e.g. individual houses, industrial buildings, parking lots, roads, shadows, water canals). The second sample is a VHSR image (2 000 × 2 000 pixels) that represents a typical low-density urban area (Figure 5(b)) composed of different geographical objects (e.g. crop fields, forests, bare soils, rivers). Both are multispectral images at a spatial resolution of 60 cm with 4 spectral bands (R, G,

B, NIR).

Ground-truth maps of different urban objects represented in the scene are also available. These maps were derived from a public crowd-sourcing campaign in the context of the COCLICO research project3 . We only retained the reference segments that led to the highest consensus between the crowders. The segments are labelled with L = 5 different semantic classes: built area, forest area, herbaceous area, roads, water. Figure 6 presents the partial GT map of the first image (Figure 5(a)).

Experiments

To reduce the patial complexity, all (M)BPTs are built from an initial partition L composed of 200 000 regions obtained from a cut on a standard BPT, thus providing superpixels composed each of 5 pixels, in average.

We consider five valuation functions W . Each models either radiometric or geometrical information related to region dissimilarities.

The first valuation function W colour is defined as the increase of the range of the pixel intensity values for each radiometric band, induced by the putative fusion of incident regions. Let N i , N j ∈ P be two adjacent regions / nodes. A multispectral image I : Ω → V associates, to each point x ∈ Ω, a s-uple of spectral intensities I(x) = s b=1 I b (x). Then, W colour is computed as The second valuation function W ndvi quantifies the difference of NDVI between two adjacent regions. The NDVI (Normalized Difference Vegetation Index) is a standard indicator for the presence of green vegetation. For each point x, it is computed from the R and NIR channels as the ratio (I N IR (x) -I R (x))/(I N IR (x) + I R (x)). Practically, the W ndvi valuation is computed for two nodes N i , N j as the absolute difference between the mean NDVI scores associated to these two regions.

1 s s b=1 max{v + b (N i ), v + b (N j )} -min{v - b (N i ), v - b (N j )},
The third valuation function W ndwi quantifies the difference of NDWI between two adjacent regions. The NDWI (Normalized Difference Water Index) The fourth valuation function W elong is defined as the change of geometrical elongation, potentially induced by the fusion of two regions. The geometrical elongation of a node N , noted elong(N ), is approximated as the ratio of the height and width of its bounding box. The W elong valuation function is then computed for two adjacent nodes N i , N j as |elong(N i ∪N j )-

elong(Ni)+elong(Nj ) 2
|. The fifth valuation function W comp is defined as the change of the geometrical compactness values, potentially induced by the fusion of two incident regions. The geometrical compactness of a node N , noted comp(N ), is approximated as the ratio of its border length and the root square of its size. The W comp valuation function is computed similarly to W elong by substituting comp to elong.

As a baseline, standard BPTs are built for each of the two satellite images of Figure 5(a-b), by using individually the 5 considered valuation functions. Some standard BPTs are also built in a mono-feature way, by considering linear combinations of several valuation functions.

For MBPTs, we consider the relative local information consensus policies mean-of-ranks and most-frequent, according to the position of the edges within the lists W (applied to the first 20% of their contents). To evaluate the impact of the different valuation functions on the segmentation results, the MBPTs are then built by considering various combinations of valuation functions.

Quantitative analysis

For quantitative analysis, we use the evaluation framework presented in Section 6.2. Our purpose is to assess the adequacy of the BPTs and MBPTs To compare nodes and GT segments, we use the Jaccard index J and the Dice coefficient D (see Equations (1-2)). As quantitative heuristics for reducing the search space (horizontal selection), we only evaluate (M)BPT nodes whose size lies within [0.5.|S|, 1. In order to highlight the efficiency of BPTs (with one metric, or one linear combination of metrics) vs. MBPTs, we first compute the scores obtained for different semantic classes. In particular, Tables 3-5 provide scores for built area, forest area, roads and water, respectively. For the sake of readability, only the most representative -and most efficient-(M)BPTs are provided.

We can observe that for 2 of the 4 tested classes, the MBPTs improve both Dice and Jaccard indices. In particular, for forest area and water, the results are better than for BPTs. In the case of roads, one of the MBPTs provides better results than BPTs, while other MBPTs provide worse results. This emphasises the fact that MBPTs do not systematically provide better results than standard BPTs, especially when a given metric is already well fitted to a given class. For instance, in the fourth case, namely for built area, a standard BPT provides better results than the MBPTs, whose scores remain however fairly close. The scores obtained by BPTs and MBPTs when considering all the GT segments finally provide index values that are slightly better for MBPTs, compared to BPTs. This study tends to prove that well-chosen metrics, involved in the construction of a MBPT can allow us to slightly improve the quality of the built tree structures for segmentation purpose.

Case study 2: Multi-image segmentation

We now illustrate the interest of MBPTs for multi-image segmentation, still in the context of satellite imaging.

Data

The dataset used here is a time series of images (1 000 × 1 000 pixels), sensed over an area located near Toulouse (France). This area is a typical agricultural From this dataset, we selected 4 images (Figure 7). They were all acquired in late August and September. This choice allows us to reduce temporal evolution effects, since we do not aim at carrying out time-based analysis. The purpose of this experiment is to assess the ability of our MBPT framework to capture timeindependent and redundant information from the content of multiple images representing a same scene.

A ground-truth map of different crop fields represented in the scene is also available (Figure 8). This map is derived from a field survey produced by the European Environment Agency (http://ec.europa.eu/agriculture). The semantic classes associated to this reference map reflect the temporal behavior of the considered crops over the 2007 cultural year. However, we only consider the delineation of the 198 segments of reference in the image for the quantitative evaluation of the quality of the produced BPTs.

Experiments

To reduce the spatial complexity, all (M)BPTs are built from an initial partition L composed of 200 000 regions obtained from a cut on a standard BPT, thus providing superpixels composed each of 5 pixels, in average. This partition was produced from Image 1 (Figure 7(a)), which is not affected by clouds.

As a baseline, a standard BPT is built for each satellite image presented in Figure 7, with the intensity value criterion W colour (denoted as W img1 colour , W img2 colour , W img3 colour , W img4 colour depending on the image where this criterion is computed). These BPTs are denoted as BPT-1, BPT-2, BPT-3 and BPT-4, respectively.

For multi-image BPTs, we consider the relative local information consensus policy mean-of-ranks, according to the position of the edges within the lists. It is applied to the first 15% of the lists W . To evaluate the impact of the different valuation functions on the segmentation results, two MBPTs are built. The first, denoted as MPBT-1, considers information extracted from the contents of the four satellite images. In other words, it is built from W img1 colour , W img2 colour , W img3 colour , W img4 colour . The second, denoted as MBPT-2, is built from only 3 of the 4 images, but 2 metrics (colour and NDVI). In other words, it is built from Best-matching nodes of the MBPTs with respect to the ground-truth map segments.

W img1 colour , W img2 colour , W img3 colour , W img1 ndvi , W img2 ndvi , W img3 ndvi . (a) Image 1 (b) Image 2 (c) Image 3 (d) Image 4 (e) GT map (f) BPT-1 (g) BPT-2 (h) BPT-3 (i) BPT-4 (j) MBPT-1 (k) MBPT-2 (l) BPT-1/GT (m) BPT- 2/GT (n) BPT- 3/GT (o) BPT- 4/GT (p) MPBPT- 1/GT (q) MPBPT- 2/GT

Quantitative analysis

For quantitative analysis, we use the evaluation framework presented in Section 6.2. Our purpose is to assess the adequacy of the BPTs and MBPTs with respect to the reference segments of the ground-truth map. Our framework is parameterized the same way as in Section 6.3.

Table 7 presents the different scores obtained for the different BPTs and MBPTs. The best scores for both Dice and Jaccard indices are obtained by MBPT-2, built from 3 images and 2 metrics (W colour , W ndvi ). The other MBPT, built from 4 images, presents lower scores than MBPT-2, which remain however slightly higher than those of standard BPTs for the 4 images.

This quantitative evaluation suggests that MBPTs are able to improve the quality of segmentation results obtained from standard BPTs. The increase of the index values is slight, but indeed sufficient to show that MBPTs constitute a fair structure for gathering and merging information collected from various images of a same scene.

Qualitative analysis

Beyond the quantitative assessment of the adequacy of (M)BPTs with ground-truth segments, it is also relevant to provide qualitative illustration of the potential of MBPTs versus standard BPTs. These qualitative analysis is indeed complementary to the above analysis.

On the one hand, the different (M)BPTs are segmented by a user-defined horizontal cut. We chose a simple segmentation paradigm, in order to avoid any bias related to the segmentation process. Such tree-cut produces a partition with a scale adapted, according to the user, to segment the geographical objects covering the sensed areas (e.g. agricultural crop fields, wide forest areas, lake).

On the other hand, we illustrate the nodes of the (M)BPTs that provide the best-matching with the segments of reference of the ground-truth map. These nodes are indeed those involved in the computation of the Dice and Jaccard indices, in the previous quantitative analysis.

For a better visualization, we focus on two image crops representing different parts of the geographical scene. Crops 1 and 2 are illustrated in Figures 9(a-d) and Figures 10(a-d), respectively.

In Crop 1, we observe that, despite of variations due to time evolutions, the global structure of the crop fields does not evolve much. Based on a visual interpretation of these images, it appears that the majority of observed geographical areas preserve the same crop field partition. However, each segmentation obtained from the standard BPTs (BPT-1 to BPT-4) presents different partitions, see Figure 9(f-i). The results obtained from the multi-image MBPT-1 and MBPT-2, see Figure 9(j-k), arise from a consensus between the results of the 4 standard BPT results.

A better observation of this phenomenon can be observed in Figure 9(pq) which gathers consensual information between the relevant segments found in the Figure 9(l-o). The best-matching nodes obtained from our multiimage/metric MBPTs are visually close to the segments of reference of the GT map presented in the Figure 9(e). Such nodes are not necessarily the same as in the arbitrary cuts of Figure 9(f-k). However, they are likely to be obtained in a segmentation result induced by a more sophisticated tree-cut process, compared to the trivial user-defined horizontal cut.

The same behaviour can be observed in Crop 2, see Figure 10. These qualitative results corroborate the previous quantitative analysis and emphasise the relevance of MBPTs, which provide different behaviour than standard BPTs, with slightly better results for relevant choices of images and metrics.

Conclusion

In this article, we proposed a generalization of the BPT construction framework. While BPTs are classically built in a mono-feature way, we considered here a multi-feature paradigm.

The induced algorithmic evolutions require the handling of more complex data structures and consensual algorithms, compared to standard BPTs. In order to tackle memory and time complexity issues, a short-term perspective of this work will be to implement distributed heuristics relying on graph-based distribution. Integrating higher-level consensus may also allow us to improve the relevance of the hierarchies and the induced segmentation.

Beyond the application examples described in this article, other relevant use-cases could be considered for the processing of different families of images. As an example, it is possible to apply MBPTs to segment hyperspectral images, by establishing a consensus between the complementary (and potentially correlated) information carried by the different spectral bands. Multi-time imaging can also be considered, by establishing a higher-level time consensus between the different image acquisitions of the same scene.

Another methodological challenge is raised by the possible divergence between the different values gathered by the metrics/images, which may lead to irrelevant consensual decisions. We plan to study how non-consensual information could be used to follow local consensus between metrics/images leading to hypertrees where the branches model local fusion decisions.

Figure 1 :

 1 Figure 1: Illustration of the construction of a BPT from one image. Left (input): (1) a graph G L = (L, A L ) models the initial partition of the image; (2) a valuation function W :(2 Ω ) 2 ×V Ω → R allows us to iteratively choose the pair of nodes to be merged (see Section 3.3). Right: progressive, bottom-up, creation of the tree from To to T 6 by iterative fusions of two neighbouring regions.

Figure 2 :

 2 Figure 2: One step of the BPT construction from one image. From the left to the right: First: the partition of Ω before and after the fusion of two nodes. Second: the associated graph G, before and after the fusion of N 3 and N 4 , forming the new node N 8 . The red edge is removed. The blue and orange edges are updated, e.g. (N 1 , N 3 ) becomes (N 1 , N 8 ). The orange edges are merged by pairs, e.g. (N 7 , N 3 ) and (N 7 , N 4 ) become (N 7 , N 8 ). The green edges are not affected. Third: the sorted list that gathers the scalar valuations of each remaining edge of G.The red cells are removed, as the edge (N 3 , N 4 ) is suppressed (this edge had been chosen due to its highest position in the list). The scores of blue and orange cells are updated with respect to N 8 . The orange cells are merged by pairs. The positions of the blue and orange cells are updated with respect to their new scores. The scores of the green cells are not affected. Last: a new part of the BPT T is created by adding the new node N 8 , and linking it to its two children nodes N 3 and N 4 .

4. 1 .

 1 Structural Evolutions 4.1.1. What does not change. . .

Figure 3 :

 3 Figure 3: General structure of a BPT construction involving n sorted lists. Each list W i gathers information about edges from one valuation function associated to a given metric on a given image. A BPT is obtained by applying a collaborative strategy between the information carried by these n lists (see Section 4.2).

Figure 4 :

 4 Figure 4: One step of a BPT construction involving n lists W i . Left: the partition of Ω before and after the fusion of two nodes. Center: the associated graph G, before and after the fusion of N 3 and N 4 , forming the new node N 8 . The red edge is removed. The blue and orange edges are updated, e.g. (N 1 , N 3 ) becomes (N 1 , N 8 ). The orange edges are merged by pairs, e.g. (N 7 , N 3 ) and (N 7 , N 4 ) become (N 7 , N 8). The green edges are not affected. Right: the n lists W i , each corresponding to a valuation function W i . The red cells are removed, as the edge (N 3 , N 4 ) is suppressed (this edge had been chosen due to its "optimal" position and / or valuation in the n lists). The scores of blue and orange cells are updated with respect to N 8 . The orange cells are merged by pairs. The positions of the blue and orange cells are updated with respect to their new scores. The scores of the green cells are not affected.

Algorithm 1 :

 1 MBPT construction Data: Image I[ ]; Metric W [ ]; Consensus strategy Consensus; Result: A Multi-feature Binary Partition Tree M BP T ; /* Variables *

Figure 5 :

 5 Figure 5: (a-b) Two VHSR satellite images (2 000 × 2 000 pixels) at a spatial resolution of 60 cm sensed by the Pléiades satellite and covering different geographical areas. (c-d) Segmentation results from standard BPTs computed from (a) and (b), respectively (23 500 and 5 000 regions, respectively). (e-f) Segmentation results from MBPTs computed from (a) and (b), respectively (23 500 and 5 000 regions, respectively), using 4 features: W colour , W elong , W ndvi , W ndwi .

Figure 6 :

 6 Figure 6: Partial ground-truth map representing urban objects of the VHSR image of Figure 5(a). This map contains 228 segments delivered by a crowd-sourcing campaign in the context of the COCLICO research project. L = 5 different semantic classes are available: built area, forest area, herbaceous area, roads, water.

  where v b provides the extremal values for the b-th spectral band in I (i.e. in I b ).

  5.|S|] for a given GT segment S. The weights involved in the computation of the global quality scores are set as w = 1/|L| and ω i = |S i |/ Sj ∈C |S j |, for a GT segment S i belonging to the semantic class C .

  (a) Image 1 (08-11-2007). (b) Image 2 (09-01-2007). (c) Image 3 (09-08-2007). (d) Image 4 (09-15-2007).

Figure 7 :

 7 Figure 7: Four satellite images (1 000 × 1 000 pixels) sensed by the Formosat-2 satellite covering the same geographical area (see Section 6.4.1). Note that the Image 2 is partially affected by the presence of clouds.

Figure 8 :

 8 Figure 8: Ground-truth map representing partial crop fields of the studied area corresponding to the 4 images of Figure 7. This map contains 198 segments of reference delivered by the European Environment Agency.

Figure 9 :

 9 Figure 9: Segmentation results from standard (i.e., mono-image) BPTs and multiimage/metric MBPTs. (a-d) Crop 1, from Figure 7. (e) Crop 1, from the ground-truth map of Figure 8. (f-i) Segmentation results from the standard BPTs (BPT-1 to BPT-4), on Images 1 to 4. (j) Segmentation result from MBPT-1 with 4-images/1-metric on Images 1-4. (k) Segmentation results from MBPT-2 with 3-images/2-metrics on Images 1-3. (l-o) Best-matching nodes of the BPTs with respect to the ground-truth map segments. (p-q) Best-matching nodes of the MBPTs with respect to the ground-truth map segments.

Figure 10 :

 10 Figure 10: Segmentation results from standard (i.e., mono-image) BPTs and multiimage/metric MBPTs. (a-d) Crop 2, from Figure 7. (e) Crop 2, from the ground-truth map of Figure 8. (f-i) Segmentation results from the standard BPTs (BPT-1 to BPT-4), on Images 1 to 4. (j) Segmentation result from MBPT-1 with 4-images/1-metric on Images 1-4. (k) Segmentation results from MBPT-2 with 3-images/2-metrics on Images 1-3. (l-o) Best-matching nodes of the BPTs with respect to the ground-truth map segments. (p-q) Best-matching nodes of the MBPTs with respect to the ground-truth map segments.

Table 1 :

 1 Cost of the BPT construction for various families of consensus. For readability purpose, α and T W , practically bounded by low constant values, have been omitted.

			Edge	Edge	Edge	Edge
		# W	choice	removal update sorting
	Stand. BPT [4]	1	O(1)	O(1)	O(1)	O(log 2 |W|)
	Absolute inf.	1	O(1)	O(1)	O(1)	O(log 2 |W|)
	Relative local inf.	n	O(n)	O(n)	O(n)	O(n. log 2 |W |)
	Relative global inf. n	O(n.|W |) O(n)	O(n)	O(n. log 2 |W |)

Table 2 :

 2 Scores of various (M)BPTs for built areas (see Section 6.3.3). BPT-1: W colour . BPT-2: Wcomp. BPT-3: W ndvi . BPT-4: linear combination of W colour , Wcomp. BPT-5: linear combination of W colour , W ndvi . MBPT-1: {W colour , Wcomp} with most-frequent. MBPT-2: {W colour , W ndvi } with most-frequent.

	Index	BPT-1 BPT-2 BPT-3 BPT-4 BPT-5 MBPT-1 MBPT-2
	Dice (D)	0.561	0.432	0.393	0.466	0.376	0.548	0.547
	Jaccard (J ) 0.417	0.283	0.276	0.313	0.266	0.403	0.409

Table 3 :

 3 Scores of various (M)BPTs for forest areas (see Section 6.3.3). BPT-1: W colour . BPT-2: W ndvi . BPT-3: linear combination of W colour , W ndvi . MBPT-1: {W colour , W ndvi } with mean-of-rank. MBPT-2: {W colour , W ndvi } with most-frequent.

	Index	BPT-1 BPT-2 BPT-3 MBPT-1 MBPT-2
	Dice (D)	0.612	0.684	0.679	0.685	0.715
	Jaccard (J )	0.464	0.553	0.541	0.548	0.573

Table 4 :

 4 Scores of various (M)BPTs for roads (see Section 6.3.3). BPT-1: W colour . BPT-2: Wcomp. BPT-3: linear combination of W colour , Wcomp. MBPT-1: {W colour , Wcomp} with mean-of-rank. MBPT-2: {W colour , Wcomp} with most-frequent. MBPT-3: {W colour , W elong , W ndvi } with most-frequent.

	Index	BPT-1 BPT-2 BPT-3 MBPT-1 MBPT-2 MBPT-3
	Dice (D)	0.633	0.443	0.466	0.509	0.697	0.515
	Jaccard (J )	0.490	0.295	0.310	0.352	0.564	0.357
	is a standard indicator for the presence of water. It is computed similarly to
	W ndvi , by substituting the G channel to the R channel.

Table 5 :

 5 Scores of various (M)BPTs for water zones (see Section 6.3.3). BPT-1: W colour . BPT-2: W ndwi . BPT-3: linear combination of W colour , W ndwi . MBPT-1: {W colour , W ndwi } with most-frequent. MBPT-2: {W colour , W elong , W ndvi } with most-frequent.

	Index	BPT-1 BPT-2 BPT-3 MBPT-1 MBPT-2
	Dice (D)	0.803	0.845	0.906	0.906	0.940
	Jaccard (J )	0.671	0.732	0.829	0.828	0.887

Table 6 :

 6 Scores of various (M)BPTs for the five thematic classes (see Section 6.3.3). BPT-1: W colour . BPT-2: W ndvi . BPT-4: W ndwi . BPT-6: Wcomp. BPT-5: linear combination of W colour , W ndwi . MBPT-1: {W colour , W ndvi } with most-frequent. MBPT-2: {W colour , W ndwi } with most-frequent. MBPT-3: {W colour , W ndvi , W ndwi } with most-frequent. MBPT-4: {W colour , W ndwi } with most-frequent. MBPT-5: {W colour , W elong , W ndvi } with most-frequent.

	Index	BPT-1 BPT-2 BPT-4 BPT-6 BPT-5 MBPT-1 MBPT-2 MBPT-3
	Dice (D)	0.630	0.559	0.580	0.446	0.568	0.658	0.656	0.656
	Jaccard (J )	0.489	0.439	0.445	0.293	0.453	0.529	0.525	0.526
	relatively to the reference segments of the GT maps. Our framework is param-
	eterized as follows.

Table 7 :

 7 Scores assessing the capacity of each (M)BPT to provide nodes similar to the 198 segments of reference of the ground-truth map of Figure8(see Section 6.4.3).

	Index	BPT-1 BPT-2 BPT-3 BPT-4 MBPT-1 MBPT-2
	Dice (D)	0.651	0.647	0.669	0.674	0.677	0.700
	Jaccard (J )	0.499	0.500	0.521	0.524	0.532	0.559
	zone, composed of different types of crop fields and vegetations. Images were
	acquired by the Formosat-2 in 2007. They were ortho-rectified and have a
	spatial resolution of 8 m, with 4 spectral bands (R, G, B, NIR) 4 .

https://bitbucket.org/agat-team/agat-v0.3

https://bitbucket.org/agat-team/agat-v0.3

http://icube-coclico.unistra.fr/index.php/Coclico

The authors thank the researchers from CESBIO for providing the geometrically and radiometrically corrected Formosat-2 images.

$ This work was supported by the French Agence Nationale de la Recherche under Grants ANR-12-MONU-0001, ANR-15-CE23-0009 and ANR-17-CE23-0015.