Join select and insert ecient out-of-core algorithms for hierarchical segmentation trees Josselin Lef evre12 Jean Cousty1 Benjamin Perret1 Harold Phelippeau2

2025-05-05 0 0 477.99KB 13 页 10玖币

侵权投诉

Join, select, and insert: eﬃcient out-of-core

algorithms for hierarchical segmentation trees

Josselin Lef`evre1,2, Jean Cousty1, Benjamin Perret1, Harold Phelippeau2

1LIGM, Univ Gustave Eiﬀel, CNRS, ESIEE Paris, F-77454 Marne-la-Vall´ee, France

2Thermo Fisher Scientiﬁc, Bordeaux, France

Abstract. Binary Partition Hierarchies (BPH) and minimum spanning

trees are fundamental data structures involved in hierarchical analysis

such as quasi-ﬂat zones or watershed. However, classical BPH construc-

tion algorithms require to have the whole data in memory, which prevent

the processing of large images that cannot ﬁt entirely in the main mem-

ory of the computer. To cope with this problem, an algebraic framework

leading to a high level calculus was introduced allowing an out-of-core

computation of BPHs. This calculus relies on three operations: select,

join, and insert. In this article, we introduce three eﬃcient algorithms to

perform these operations providing pseudo-code and complexity analysis.

1 Introduction

Hierarchies of partitions are versatile representations that have proven useful in

many image analysis and processing problems. In this context, binary partition

hierarchies [14] (BPH) built from altitude ordering and associated minimum

spanning trees are key structures for several (hierarchical) segmentation

methods: in particular it has been shown [2,11] that such hierarchies can be used

to eﬃciently compute quasi-ﬂat zone (also referred as α-trees) hierarchies [10,2]

and watershed hierarchies [9,2]. Eﬃcient algorithms for building BPHs on

standard size images are well established, but, with the constant improvement

of acquisition systems comes a dramatic increase in image resolutions, which can

reach several terabytes in size. In such case, it becomes impossible to put a single

image in the main memory of a standard workstation and classical algorithms for

BPHs stop working. This creates the need for scalable algorithms to construct

BPHs in an out-of-core manner to handle images that cannot ﬁt in memory.

In [4,6,8], the authors investigate distributed memory algorithms to compute

min and max trees for terabytes images. In [5], computation of minimum

spanning trees of streaming images is considered. A parallel algorithm for the

computation of quasi-ﬂat zones hierarchies has been proposed in [7]. Finally,

the authors of [1] recently proposed massively parallel algorithms for the

computation of max-trees on GPUs. All these work rely on a common idea which

is to work independently on small pieces of the space, “join” the information

found on adjacent pieces, and “insert” this joint information into other pieces.

In a previous work [3], the authors speciﬁcally addressed the problem of

computing a BPH under the out-of-core constraint, i.e., when the objective is

arXiv:2210.02218v1 [eess.IV] 5 Oct 2022

2 J. Lef`evre et al.

to minimize the amount of memory required by the algorithms. To do so, they

introduced an algebraic framework formalizing the distribution of a hierarchy

over a partition of the space together with three algebraic operations acting on

BPHs: select,join, and insert. They showed that, when a causal partition of the

space is considered, it is possible to compute the distribution of a BPH using

these three operations by browsing the diﬀerent regions of the partition only

twice (once in a forward pass and once in a backward pass) and by requiring to

have only the information about two adjacent regions in the main memory at

any step of the algorithm. However, no eﬃcient algorithm has been proposed for

the three operations select,join, and insert.

In this work, we propose eﬃcient implementations for these operations.

The proposed algorithms rely on a particular data structure to represent local

hierarchies which is designed to eﬃciently search and browse the nodes of the

hierarchy and to store only the necessary and suﬃcient information required

locally to compute the distribution of the BPH. We give algorithms, with their

pseudo-code, for the three operations whose time complexity is either linear or

linearithmic. In order to ease the presentation, we consider the particular case

of 2d images, modelled as 4-adjacency graphs, but the method can be easily

extended to any regular graph. The implementation of the method in C++ and

Python based on the hierarchical graph processing library Higra [12] is available

online https://github.com/PerretB/Higra-distributed.

This article is organized as follows. Section 2 gives the deﬁnition of BPH.

Section 3 recalls the notion of the distribution of a hierarchy and the calculus

method that can be used to compute such distribution over a causal partition

of the space. Section 4 explains the proposed data structures. Section 5 presents

the algorithms for the three operations select,join, and insert. Finally, Section 6

concludes the work and gives some perspectives.

2 Binary partition hierarchy by altitude ordering

In this section, we ﬁrst remind the deﬁnitions of hierarchy of partitions. Then

we deﬁne the binary partition hierarchy by altitude ordering using the edge-

addition operator [3] and we recall the bijection existing between the regions of

this hierarchy and the edges of a minimum spanning tree of the graph.

Let Vbe a set. A partition of Vis a set of pairwise disjoint subsets of V.

Any element of a partition is called a region of this partition. The ground of a

partition P, denoted by gr(P), is the union of the regions of P. A partition whose

ground is Vis called a complete partition of V. Let Pand Qbe two partitions

of V. We say that Qis a reﬁnement of Pif any region of Qis included in

a region of P. A hierarchy on Vis a sequence (P0,...,P`) of partitions of V

such that, for any λin {0, . . . , ` −1}, the partition Pλis a reﬁnement of Pλ+1.

Let H= (P0,...,P`) be a hierarchy. The integer `is called the depth of H

and, for any λin {0, . . . , `}, the partition Pλis called the λ-scale of H. In the

following, if λis an integer in {0, . . . , `}, we denote by H[λ] the λ-scale of H. For

any λin {0, . . . , `}, any region of the λ-scale of His also called a region of H.

Join, select, and insert: eﬃcient out-of-core algorithms 3

The hierarchy His complete if H[0] = {{x} | x∈V}and if H[`] = {V}. We

denote by H`(V) the set of all hierarchies on Vof depth `, by P(V) the set of

all partitions on V, and by 2|V|the set of all subsets of V.

In the following, the symbol `stands for any strictly positive integer.

We deﬁne a graph as a pair G= (V, E) where Vis a ﬁnite set and Eis

composed of unordered pairs of distinct elements in V. Each element of Vis

called a vertex of G, and each element of Eis called an edge of G. The Binary

Partition Hierarchy (BPH) by altitude ordering relies on a total order on E,

denoted by ≺. Let kin {1, . . . , `}, we denote by u≺

kthe k-th element of Efor

the order ≺. Let ube an edge in E, the rank of ufor ≺, denoted by r≺(u),

is the unique integer ksuch that u=u≺

k. We then deﬁne the update of a

hierarchy Hwith respect to an edge {x, y}, denoted by H⊕{x, y}: with kthe rank

of {x, y},H ⊕ {x, y}[λ] remains unchanged for any λin{0, k −1}while, for any

λin {k, . . . , `}, we have (H ⊕ {x, y})[λ] = H[λ]\ {Rx, Ry} ∪ {Rx∪Ry}where Rx

(resp. Ry) denotes the region of H[λ] containing x(resp. y). Let E0⊆Eand let H

be a hierarchy. We set HE0=H ⊕ u1⊕. . . ⊕u|E0|where E0={u1, . . . , u|E0|}.

The binary operation is called the edge-addition. Thanks to this operation,

we can deﬁne formally the BPH for ≺. Let Xbe a set, we denote by ⊥Xthe

hierarchy deﬁned by ⊥X[λ] = {{x} | x∈X}, for any λin {0,...`}. The BPH

for ≺, denoted by B≺is the hierarchy ⊥XE.

Let B≺be a binary partition by altitude ordering, Rbe a region of B≺

and R?be the set of non-leaf regions of B≺. The rank of R, denoted by r(R),

is the lowest integer λsuch that Ris a region of B≺[λ]. We consider the map µ

from R?in Esuch that, for any non-leaf region Rof B≺, we have µ≺(R) = u≺

r(R).

We say that µ≺(R) is the building edge of R. Building edges of the binary

partitions hierarchy deﬁnes a minimum spanning tree of an edge-weighted graph.

In Figure 1, Yis the BPH built on the 4-adjacency graph B. Non-leaf nodes of Y

correspond to the edges of the minimum spanning tree of B(dashed edges).

3 Distributed hierarchies of partitions on causal partition

In this section, we recall the deﬁnition of the distribution of a BPH on a sliced

graph and the principle of its calculus in an out-of-core manner. Intuitively,

distributing a hierarchy consists in splitting it into a set of smaller trees such that:

1) each smaller tree corresponds to a selection of a sub part of whole tree that

intersects a slice of the graph and 2) the initial hierarchy can be reconstructed

by “gluing” those smaller trees.

Let Vbe a set. The operation sel is the map from 2|V|×P(V) to P(V) which

associates to any subset Xof Vand to any partition Pof Vthe subset sel(X, P)

of Pwhich contains every region of Pthat contains an element of X. The

operation select is the map from 2|V|× H`(V) in H`(V) which associates to

any subset Xof Vand to any hierarchy Hon Vthe hierarchy select (X, H) =

(sel(X, H[0]),...,sel(X, H[`])).

We are then able to deﬁne the distribution of a hierarchy thanks to select.

Let Va set, let Pbe a complete partition on Vand let Hbe a hierarchy on V.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Join,select,andinsert:ecientout-of-corealgorithmsforhierarchicalsegmentationtreesJosselinLefevre1;2,JeanCousty1,BenjaminPerret1,HaroldPhelippeau21LIGM,UnivGustaveEiel,CNRS,ESIEEParis,F-77454Marne-la-Vallee,France2ThermoFisherScientic,Bordeaux,FranceAbstract.BinaryPartitionHierarchies(BPH)andmin...

展开>> 收起<<

Join select and insert ecient out-of-core algorithms for hierarchical segmentation trees Josselin Lef evre12 Jean Cousty1 Benjamin Perret1 Harold Phelippeau2.pdf

共13页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Join select and insert ecient out-of-core algorithms for hierarchical segmentation trees Josselin Lef evre12 Jean Cousty1 Benjamin Perret1 Harold Phelippeau2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: