Omid Amini
email: omid.amini@ens.fr

Jean-Daniel Boissonnat
email: jean-daniel.boissonnat@sophia.inria.fr

Pooran Memari
email: pooran.memari@sophia.inria.fr

Geometric Tomography With Topological Guarantees

Keywords: F.2.2 [Nonnumerical Algorithms and Problems]: Geometrical problems and computations; I.3.5 [Computational Geometry and Object Modeling]: Curve, surface, solid, and object representations Algorithms, Reliability, Theory

We consider the problem of reconstructing a compact 3manifold (with boundary) embedded in R 3 from its crosssections with a given set of cutting planes having arbitrary orientations. Under appropriate sampling conditions that are satisfied when the set of cutting planes is dense enough, we prove that the algorithm presented by Liu et al. in [LBD + 08] preserves the homotopy type of the original object. Using the homotopy equivalence, we also show that the reconstructed object is homeomorphic (and isotopic) to the original object. This is the first time that shape reconstruction from cross-sections comes with such theoretical guarantees.

INTRODUCTION

Overview.

This paper deals with the reconstruction of 3-dimensional geometric shapes from unorganized planar cross-sections. The need for such reconstructions is a result of the advances in medical imaging technology, specially in ultrasound tomography. In this context, the purpose is to construct a 3D model of an organ from a collection of ultrasonic images. When the images are provided by free-hand ultrasound devices, the cross-sections of the organ belong to planes that are not necessarily parallel. However, it is only very recently that reconstruction from unorganized cross-sections has been considered: A very first work [START_REF] Payne | Surface reconstruction by multiaxial triangulation[END_REF] by Payne Reconstruction Problem.

Let O ⊂ R 3 be a compact 3-manifold with boundary (denoted by ∂O) of class C 1,1 . The manifold O is cut by a set P of so-called cutting planes that are supposed to be in general position in the sense that none of these cutting planes are tangent to ∂O. For any cutting plane P ∈ P, we are given the intersection O ∩ P . There is no assumption on the geometry or the topology of these intersections. The goal is to reconstruct O from the given intersections.

Arrangement of the Cutting Planes.

We can decompose the problem into several subproblems as follows. Consider the arrangement of the cutting planes, i.e., the subdivision of R 3 into convex polyhedral cells induced by the cutting planes. Without loss of generality, we can restrict our attention to a cell of this arrangement and reduce the reconstruction of O to the reconstruction of OC := O ∩ C for all cells C of the arrangement. Since the various reconstructed pieces will conform to the given sections, it will be easy to glue them together in the end to get the overall reconstructed object R.

Sections: Input of the Reconstruction Algorithm.

We now focus on a cell C of the arrangement and describe how the reconstructed object RC is defined in C. On each face f of C, the intersection of the object O with f is given and consists of a set of connected regions called sections. By definition, the sections of a face of C are disjoint. However, two sections (on two neighbor faces of C) may intersect along the intersection between their two corresponding faces. The boundary of a section A is denoted by ∂A and is a set of closed curves, called section-contours, that may be nested.

Let us write ∂C for the boundary of C, and FC for the set of faces of C. In the sequel, SC denotes the union of sections of all the faces of C and a point of SC is called a section-point.

Methodology.

We know that a point on the boundary of C is in O if it lies in SC. The goal is now to determine whether a point x inside C belongs to O or not. The reconstruction method that we will present here is based on the notion of distance from ∂C:

A point x ∈ C is in the reconstructed object if one of its nearest points in ∂C is in SC.

Different distance function (from the boundary of C) may be used in order to satisfy properties of interest for different applications (for example, to promote the connection between sections in the case of sparse data, or to impose a favorite direction to connect the sections, etc). A natural idea is to use the Euclidean distance as the distance function from ∂C. In this case, the reconstructed object coincides with the method introduced by Liu et al in [LBD + 08]. In this paper, we analyze this method and present appropriate sampling conditions providing topological guarantees for the resulting reconstructed object.

Organization of the paper.

After this brief introduction, in Section 2 we provide the definition of the reconstructed object R. The rest of the paper will be then devoted to prove that in the general case, under two appropriate sampling conditions, R and O are homotopy equivalent, and are more strongly homeomorphic. Indeed, the first sampling condition, called the Separation Condition, discussed in Section 2.1, ensures good connectivity between the sections, but does not necessarily imply the homotopy equivalence.

As we will see, in order to ensure the homotopy equivalence between R and O, a second so-called Intersection Condition is required, c.f., Section 3.4. To make the connection between the upcoming sections more clear, we shortly outline the general strategy employed in proving the homotopy equivalence between R and O. In Section 3.5, we provide a set of properties on the sampling of cutting planes to ensure the Separation and the Intersection Conditions. Finally, in Section 3.6 we show that the two shapes O and R are indeed homeomorphic (and even isotopic). Some preliminary notions of homotopy theory we use here are recalled in the full version of the paper [START_REF] Amini | Geometric Tomography with Topological Guarantees[END_REF].

RECONSTRUCTED OBJECT DEFINITION

Let us first give a definition of the reconstructed object in a cell C of the arrangement of the cutting planes, which is related to the Voronoi diagram of C defined as follows.

Voronoi Diagram of a Cell.

For a face f of C, the Voronoi cell of f , denoted by VorC(f ), is defined as the set of all points in C that have f as the nearest face of C, i.e.,

VorC(f ) = { x ∈ C | d(x, f ) ≤ d(x, f ′ ), ∀ face f ′ of C }.
Where d(., .) denotes the Euclidean distance. The collection of all VorC(f ) of the faces of C forms a tiling of C, called the Voronoi diagram of C. We write ∂VorC(f ) for the boundary of VorC(f ). The union of ∂VorC(f ) for all the faces f of C is called the Voronoi Skeleton of C, and is denoted by VorSkel(C). VorSkel(C) is also called the medial axis of the cell, and is the locus of points in C that are at the same distance from at least two faces of C. To simplify notation, when the cell C is understood from the context, we simply remove the index C and write Vor(f ), ∂Vor(f ), etc.

Definition 1 (Nearest Point) For any point x in C, the nearest point in ∂C to x is the orthogonal projection of x onto the nearest face f of C. This projection is denoted by np f (x). The set of all nearest points to x in ∂C is denoted by Np C (x). Note that for any x / ∈ VorSkel(C), Np C (x) is reduced to a single point. Based on this, and to simplify the presentation, sometimes we drop the index f , and by np(x) we denote a point of Np C (x).

We can now define the reconstructed object in a given cell C. We first give the formal definition, and then present a more detailed geometric characterization of the reconstructed object using the lifting procedure described below.

Definition 2 (Reconstructed Object RC in C) The reconstructed object RC is the set of all points x in C such that a nearest point np(x) lies in SC, i.e., Np C (x) ∩ SC = ∅. Note that in the case where SC is empty, RC will be the empty set as well.

Definition 3 (Lift Function) Let x ∈ C be a point in the Voronoi cell of a face f of C. The lift of x in C, denoted by liftC(x) (or simply lift(x) if C is trivially implied), is defined to be the unique point of ∂VorC(f ) such that the line defined by the segment [x, lift(x)] is orthogonal to f . In other words, lift(x) is the unique point in ∂VorC(f ) whose the orthogonal projection onto f is np(x). The lift of a set of points X ⊆ C, denoted by lift(X), is the set of all the points lift(x) for x ∈ X, i.e., lift(X) :=

{ lift(x) | x ∈ X }.
The function L : C → VorSkel(C) that maps each point x ∈ C to its lift in VorSkel(C) will be called the lift function in the sequel. For any Y ⊂ VorSkel(C), L -1 (Y ) denotes the set of points x ∈ C such that lift(x) = y for some y ∈ Y .

Characterization of the Reconstructed Object RC.

If SC = ∅, then, as we said before, for any point x ∈ C, np(x) / ∈ SC, and so RC is empty. Otherwise, let A ∈ SC be a section lying on a face of C. For each point a ∈ A, the locus of all the points x ∈ C that have a as their nearest Note that according to this characterization, if the lifts of two sections intersect in VorSkel(C), then these two sections are connected in RC. This generalizes the classical overlapping criterion for the case of parallel cutting planes. The union of all the pieces RC over all cells C will be the overall reconstructed object R.

The rest of the paper is devoted to prove that under two appropriate sampling conditions, R and O are homotopy equivalent, and are indeed homeomorphic (and isotopic).

First Sampling Condition: Separation Condition

In this section, we provide the first sampling condition, under which the connection between the sections in the reconstructed object R are the same as in the original object O. Our discussion will be essentially based on the study of the medial axis, that we define now.

Definition 4 (Medial Axis of ∂O) Consider ∂O as a 2manifold without boundary embedded in R 3 . The medial axis of ∂O, denoted by MA(∂O), contains two different parts: the so-called internal part, denoted by MAi(∂O), which lies in O and the so-called external part, denoted by MAe(∂O), which lies in R 3 \ O.

The internal retract mi : ∂O → MAi(∂O) is defined as follows: for a point x ∈ ∂O, mi(x) is the center of the maximum ball entirely included in O which passes through x. For any x ∈ ∂O, mi(x) is unique. Symmetrically, we define the external retract me : ∂O → MAe(∂O): for a point x ∈ ∂O, me(x) is the center of the maximum ball entirely included in R 3 \ O which passes through x. For any x ∈ ∂O, me(x) is unique but may be at infinity. In the sequel, we may write m(a) for a point in {mi(a), me(a)}.

The interesting point is that as discussed below if the sample of cutting planes is sufficiently dense, then the internal part of MA(∂O) lies inside the defined reconstructed object and the external part of this medial axis lies outside the reconstructed object. In other words, ∂R separates the internal and the external parts of the medial axis of ∂O. (That is where the name comes from.)

We will show that in each cell C, the Separation Condition implies that ∂RC separates the internal and the external parts of the medial axis of ∂OC.

Definition 6 (Medial Axis of ∂OC) In order to study the Separation Condition in a cell C, we will need to consider the medial axis of OC, denoted by MA(∂OC), defined as the set of points in C with at least two closest points in ∂OC. By MAi(∂OC) (resp. MAe(∂OC)) we denote the part of MA(∂OC) that lies inside (resp. outside) OC. Note that the two sets MA(∂OC) and MA(∂O) ∩ C may be different.

We also consider the internal retract mi,C : ∂OC → MAi(∂OC) defined as follows: for a point x ∈ ∂OC, mi,C(x) is the center of the maximum ball entirely included in OC which passes through x. Symmetrically, we can define the external retract me,C : ∂OC → MAe(∂OC): for a point x ∈ ∂OC, me,C(x) is the center of the maximum ball entirely included in C\OC which passes through x. It is easy to see that for any x ∈ ∂O ∩ C, the segments [x, mi,C(x)] and [x, me,C(x)] are subsegments of [x, mi(x)] and [x, me(x)] respectively, and lie on the line defined by the normal to ∂O at x. Proof. We prove the first part, MAi(∂OC) ⊂ RC. A similar proof gives the second part. Let m be a point in MAi(∂OC), and B(m) be the open medial ball centered at m. Two cases can happen:

• Either, the closest points to m in ∂OC are in ∂O, in which case m is a point in MAi(∂O). The Separation Condition states that MAi(∂O) ⊂ R, and so m ∈ RC = R ∩ C.

• Otherwise, one of the closest points to m in ∂OC is a point a in some section A ∈ SC. If a is on the boundary of A, then since along the section-contours ∂OC is non-smooth, a lies in MAi(∂OC) and coincides with m, and m = a is trivially in RC. Hence, we may assume that a lies in the interior of A. Therefore, the ball B(m) is tangent to A at a, and the line segment [a, m] is orthogonal to A. Since B(m) ∩ ∂C = ∅, m and a are in the same Voronoi cell of the Voronoi diagram of C. Thus, a ∈ SC is the nearest point in ∂C to m. By the definition of RC, we deduce that m ∈ RC.

Assume that the Separation Condition is verified. The first idea which comes to mind is to retract points of ∂O to ∂R by following the normal-directions. A point x ∈ ∂O which lies outside R can move towards mi(x) ∈ R and stop when ∂R is reached. A point x ∈ ∂O which lies inside R, can move toward me(x) and stop when ∂R is reached. Since ∂O is assumed to be of class C 1,1 , the normals form a continuous vector field. Hence, this deformation will be a continuous retraction if each normal intersects ∂R at a single point. In such a case, ∂O can be deformed to ∂R homeomorphically. But a major problem is that R may have a complex shape (with cavities), so that a normal to ∂O intersects ∂R in several points. In such a case, such a retraction is not continuous and does not provide a deformation retract of O onto R. However, we will be essentially following this intuitive idea by looking for a similar deformation retract of O onto a subshape of R (the so-called medial shape).

Guarantees on the Connections Between the Sections

We now show that if the sample of cutting planes verifies the Separation Condition, then in each cell C of the arrangement, the connection between the sections is the same in OC and RC.

Theorem 1 If the sample of cutting planes verifies the Separation Condition, RC and OC induce the same connectivity components on the sections of C.

Proof. The proof is given in two parts:

(I) If two sections are connected in RC, then they are connected in OC. Let A and A ′ be two sections connected in RC. Let γ be a path in RC that connects a point a ∈ A to a point a ′ ∈ A ′ . For the sake of a contradiction, suppose that a and a ′ are not in the same connected component of OC. In this case, as γ joins two points in two different connected components of OC, it intersects MAe(∂OC). This is a contradiction with the fact that γ ⊂ RC, since according to Lemma 1 we have MAe(∂OC) ∩ RC = ∅.

(II) If two sections are connected in OC, then they are connected in RC. Let A and A ′ be two sections in a same connected component K of OC. According to the non-smoothness of ∂OC at the boundary of the sections, ∂A and ∂A ′ are contained in MAi(∂OC). Thus, there is a path

γ in MAi(∂OC) ∩ K that con- nects a point a ∈ ∂A to a point a ′ ∈ ∂A ′ . According to Lemma 1, MAi(∂OC) ⊂ RC. Thus, γ is a path in RC that connects A to A ′ .
We proved that under the Separation condition, the connectivity between the sections of C induced by the reconstructed object RC is coherent with the original shape OC.

This will imply the homotopy equivalence between RC and OC for the 2-dimensional variant of the reconstruction problem, that consists of constructing a 2D-shape from its intersections with arbitrarily oriented cutting lines. In this case the sections are line-segments.

2D Shape Reconstruction from Line Cross-Sections

Consider the 2-dimensional variant of the reconstruction problem, that consists of constructing a 2D-shape from its intersections with arbitrarily oriented cutting lines. In this case the sections are line-segments. We can focus on a cell C of the arrangement of the plane by the cutting lines. Similar definitions for the Voronoi diagram and the Voronoi skeleton of C, the lift function and the reconstructed object RC can be considered. If for any cell C of the arrangement, hC < reachC(O) then the Separation Condition is ensured. Under the Separation Condition, there is a bijection between the connected components of RC and OC. By the definition of the reconstructed object, it is easy to see that any connected component of RC is a topological disk. On the other hand, under the Separation Condition, any connected component of ∂O is cut by at least one cutting line. We easily deduce that any connected component of OC is a topological disk.

Using the sufficient condition presented in the last section that implies the separation condition, we deduce the following theorem.

Theorem 2 (Provably Good 2D Reconstruction) If for any cell C of the arrangement of the cutting lines, hC < reachC(O) then R is homeomorphic to O.

Proof. We proved that under the separation condition, there is a bijection between the connected components of RC and OC. On the other hand, according to the previous lemma, all the connected components of OC or RC are 2-dimensional disks. Therefore, there is a homotopy equivalence between each pair of corresponding connected components of OC or RC. This provides a homotopy equivalence between RC and OC. As we will explain in detail in Section 3.4.1, the homotopy equivalences in the different cells of the arrangement can be extended to a homotopy equivalence between R and O. Finally, since R and O are two homotopy equivalent 2-dimensional topological manifolds, we conclude that there is a homeomorphism between R and O.

How to Ensure the Separation Condition?

In this section we provide a sufficient condition for ensuring the Separation Condition. For this, we need first some definitions. We now show that by upper-bounding the height of the cells by a factor related to the reach of the object, we can ensure the Separation Condition.

Lemma 2 (Sufficient Condition) If hC < reachC(O), for any cell C of the arrangement, then the Separation Condition is verified.

Proof. The proof is straightforward. Let m be a point in MA(∂O) in a cell C of the arrangement. We have

d(m, np(m)) ≤ hC < reachC(O) ≤ d(m, ∂O).
Therefore the Separation Condition is verified.

TOPOLOGICAL GUARANTEES

To clarify the connection between the upcoming sections, let us shortly outline the general strategy employed in proving the homotopy equivalence between R and O.

Proof Outline of the Homotopy Equivalence Between R and O

We will provide a homotopy equivalence between RC and OC in each cell of the arrangement. (And then glue these homotopy equivalences together to form a global homotopy equivalence between R and O.) In Section 2.2 we showed that under the first sampling condition called Separation Condition the connection between the sections in the reconstructed object RC is the same as in OC, in the sense that there is a bijection between the connected components of RC and the connected components of OC. This implies that for proving the homotopy equivalence between RC and OC, it will be enough to show that the corresponding connected components have the same homotopy type. In order to extend these homotopy equivalences to a homotopy equivalence between R and O, we will have to glue together the homotopy equivalences we obtain in the cells of the arrangement. This needs some care since the restriction to a section S of the two homotopy equivalences defined in the two adjacent cells of S may be different. To overcome this problem, we need to define an intermediate shape MC in each cell C, called the medial shape. The medial shape has the following three properties:

(i) The medial shape contains the sections of C, i.e., SC ⊆ MC.

(ii) There is a (strong) deformation retract r from OC to MC. In particular, this map is a homotopy equivalence between OC and MC. And its restriction to SC is the identity map.

(iii) Under the first sampling condition (Separation Condition), MC ⊆ RC.

The first two properties will be crucial to guarantee that the homotopy equivalences conform on each section under the Separation Condition. Indeed, the map OC → MC ֒→ RC, obtained by composing the deformation retract and the inclusion, restricts to the identity map on each section of SC. Thus, we can glue all these maps to obtain a global map from O to R.

Using a generalized version of the nerve theorem (see Section 3.4.1) and property (ii) above, we can then reduce the problem to proving that the inclusion i : MC ֒→ RC forms a homotopy equivalence in each cell. Using Whitehead's theorem, it will be enough to show that the inclusion i induces isomorphisms between the corresponding homotopy groups. Under the Separation Condition, we prove that i induces an injective map on the first homotopy groups, and that all higher homotopy groups of MC and RC are trivial. Unfortunately, the Separation Condition does not ensure in general the surjectivity of i on the first homotopy groups. To overcome this problem, we need to impose a second condition called Intersection Condition. Under the Intersection Condition, the map i will be surjective on the first homotopy groups, leading to a homotopy equivalence between O and R.

According to the guarantees on the connectivity between the sections (Theorem 1), to prove the homotopy equivalence between RC and OC under the Separation Condition, we may restrict to each of the corresponding connected components.

In the sequel, to simplify the notations and the presentation, we suppose that OC and thus RC are connected, and we show that OC and RC have the same homotopy type. It is clear that the same proofs can be applied to each corresponding connected components of OC and RC to imply the homotopy equivalence in the general case of multiple connected components.

Medial Shape

We now define an intermediate shape in each cell C of the arrangement called the medial shape. The medial shape enjoys a certain number of important properties, discussed in this section, which makes it playing an important role in obtaining the homotopy equivalence between OC and RC.

Definition 10 (Medial Shape MC) Let x be a point in SC ⊂ ∂OC. Let w(x) = [x, mi,C(x)] be the segment in the direction of the normal to ∂OC at x which connects x to the point mi,C(x) ∈ MAi(∂OC). We add to MAi(∂OC) all the segment w(x) for all the points x ∈ SC. We call the resulting shape MC, see Figure 2. More precisely,

MC := MAi(∂OC) ∪ ( [ x∈S C w(x)).
Proposition 1 The medial shape verifies the following set of properties:

(i) The medial shape contains the sections of C, i.e., SC ⊆ MC.

(ii) There is a (strong) deformation retract r from OC to MC. In particular, this map is a homotopy equivalence between OC and MC. And its restriction to SC is the identity map. We end this section with the following important remark and proposition which will be used in the next section. By replacing the shape OC with its complementary set we may define an exterior medial shape f MC. This is more precisely defined as follows. Let e O be the closure of the complementary set of O in R 3 . And let f OC be the intersection of e O with the cell C. The medial shape of f OC, denoted by f MC, is the union of the medial shapes of the connected components of f OC. Similarly, under the Separation Condition, the following proposition holds.

Topological Guarantees Implied by the Separation Condition

Throughout this section, we suppose that the Separation Condition holds. By the discussion at the end of Section 3.1, and without loss of generality, we may suppose that OC and hence RC are connected. Thus, OC and RC are connected compact topological 3-manifolds embedded in R 3 .

In Section 3.2, we defined the medial shape MC and showed that MC is homotopy equivalent to OC, by giving a (strong) deformation retract from OC onto MC. We have also shown that under the Separation Condition, MC ⊂ RC. Using these properties, the goal will be to prove that the inclusion i : MC ֒→ RC is a homotopy equivalence. As the objects we are manipulating are all CW-complexes, homotopy equivalence is equivalent to weak homotopy equivalence according to Whitehead's theorem.

Hence, it will be enough to show that i : MC ֒→ RC induces isomorphism between the corresponding homotopy groups.

Injectivity on the Level of Homotopy Groups

We will make use of the lift function in C, c.f. Section 2. We consider the restriction of the lift function to the reconstructed object RC. According to the definition of RC, RC is the union of all the segments [a, lift(a)], for a ∈ SC. On the other hand, the lift function retracts each segment [a, lift(a)] to lift(a) continuously. We infer the following simple observation.

Proposition 3 The lift function L : RC → lift(SC) is a homotopy equivalence.

According to the above proposition and the following diagram, to show that i : MC ֒→ RC is a homotopy equivalence, using Whitehead's theorem it will be sufficient to show that the restriction of the lift function to MC is a weak homotopy equivalence. Theorem 3 (Injectivity) Under the Separation Condition, the homomorphisms between the homotopy groups of MC and lift(SC), induced by the lift function L, are injective.

MC

Proof. Under the Separation Condition, we have MC ⊂ RC. Let g MC be the medial shape of the closure of the complementary set of OC in C. We refer to the discussion at the end of the previous section for more details. Recall that by Proposition 2, we have RC ⊂ C \ f MC, and there exists a deformation retract from C \ f MC to OC (in particular OC and C \ f MC are homotopy equivalent). We have now the following commutative diagram in which every map (except the lift function L) is an injection (or an isomorphism) on the level of homotopy groups.

OC MC RC C \ f MC lift(SC) w w o o o o o o o o o o o o o ≃ / / i ' ' O O O O O O O O O O O L / / ≃ g g O O O O O O O O O O O ≃
Using this diagram, the injectivity on the level of homotopy groups is clear: For any integer j ≥ 1, consider the induced homomorphism L * : πj(MC) → πj(lift(SC)). Let x ∈ πj(MC) be so that L * (x) is the zero element of πj(lift(SC)). It is sufficient to show that x is the zero element of πj(MC). Following the maps of the diagram, and using the homotopy equivalence between lift(SC) and RC, we have that i * (x) is mapped to the zero element of πj(RC). Then, by the inclusion RC ֒→ C \ f MC, it goes to the zero element of C \ f MC, and by the two retractions, it will be mapped to the zero element of MC. As this diagram is commutative, we infer that x is the zero element of MC. Thus, L * : πj(MC) → πj(lift(SC)) is injective for all j ≥ 1. The injectivity for j = 0 is already proved in Theorem 1.

We have shown that under the Separation Condition, the lift function L : MC → lift(SC) induces injective morphisms between the homotopy groups of MC and lift(SC). If these induced morphisms were surjective, then L would be a homotopy equivalence (by Whitehead's theorem). We will show in Section 3.3.2 that the Separation Condition implies the surjectivity for all the homotopy groups except for dimension one (fundamental groups). Indeed, we will show that under the Separation Condition, all the i-dimensional homotopy groups of MC and lift(SC) for i ≥ 2 are trivial. Once this is proved, it will be sufficient to study the surjectivity of L * : π1(MC) → π1(lift(SC)).

Remark 1 Note that the injectivity in the general form above remains valid for the corresponding reconstruction problems in dimensions greater than three. However, the vanishing results on higher homotopy groups of OC and RC are only valid in dimensions two and three.

The topological structures of RC and OC are determined by their fundamental groups

In this section, we show that if the Separation Condition is verified, then the topological structure of the portion of O in a cell C (i.e., OC) is simple enough, in the sense that for all i ≥ 2, the i-dimensional homotopy group of OC is trivial. We can easily show that RC has the same prop-erty.1 As a consequence, the topological structures of OC and RC are determined by their fundamental group, π1(OC) and π1(RC).

We first state the following general theorem for an arbitrary embedded 3-manifold with connected boundary.

Theorem 4 Let K be a connected 3-manifold in R 3 with a (non-empty) connected boundary. Then for all i ≥ 2, πi(K) = {0}. This theorem can be obtained from Corollary 3.9 of [START_REF] Hatcher | Algebraic topology[END_REF]. We also provide a proof of this theorem in the long version of the paper [START_REF] Amini | Geometric Tomography with Topological Guarantees[END_REF]. From this theorem, we infer the two following theorems.

Theorem 5 Under the Separation Condition, πi(OC) = {0}, for all i ≥ 2.

Proof. We only make use of the fact that under the Separation Condition, any connected component of ∂O is cut by at least one cutting plane. In this case, every connected component of OC is a 3-manifold with connected boundary. The theorem follows as a corollary of Theorem 4.

Theorem 6 πi(RC) = {0}, for all i ≥ 2.

Proof. Using Theorem 4, it will be sufficient to show that the boundary of any connected component K of RC is connected. Let x and y be two points on the boundary of K, and let S and S ′ be two sections so that x ∈ [a, lift(a)] for some a ∈ S and y ∈ [b, lift(b)] for some b ∈ S ′ . By the definition of RC, x is connected to S in ∂RC, and y is connected to S ′ in ∂RC. On the other hand, since S and S ′ are two sections in the connected component K of RC, they lie on ∂K and are connected to each other in ∂K (and so in ∂RC). Thus, x is connected to y in ∂RC.

Second Condition: Intersection Condition

In the previous section, we saw that under the Separation Condition, the topological structures of OC and RC are determined by their fundamental group π1(OC) and π1(RC), respectively. The goal of this section is to find a way to ensure an isomorphism between the fundamental groups of RC and OC. We recall that as OC and MC are homotopy equivalent, π1(OC) is isomorphic to π1(MC). On the other hand, RC and lift(SC) are homotopy equivalent, and π1(RC) is isomorphic to π1(lift(SC)) (c.f. last diagram). Thus, it will be sufficient to compare π1(MC) and π1(lift(SC)).

We consider L * : π1(MC) → π1(lift(SC)), the map induced by the lift function from MC to lift(SC) on fundamental groups . We showed that L * is injective. A natural condition to ensure that L * is an isomorphism is to imply that any connected component of lift(SC) is contractible. This is very common in practice, where the sections are contractible and sufficiently close to each other. In this case, since π1(lift(SC)) is trivial and L * is surjective. Hence, the homotopy equivalence between RC and OC can be deduced.

However, the map L * : π1(MC) → π1(lift(SC)) fails to be surjective in general (where the connected components of lift(SC) are not necessarily contractible). Figure 3 shows two shapes with different topologies, a torus and a (twisted) cylinder, that have the same (inter)sections with a set of (two) cutting planes. The lift of any curve γ connecting x1 and x2 in MC provides a non-zero element of π1(lift(SC), x). The reconstructed object (at left) is a torus and is not homotopy equivalent to the original shape (at right) which is a twisted cylinder.

Hence, whatever is the reconstructed object from these sections, it would not be topologically consistent for at least one of these objects. In particular, the proposed reconstructed object (R) is a torus which is not homotopy equivalent to the (twisted) cylinder (O). In addition, we note that the Separation Condition may be verified for such a situation. Indeed, such a situation is exactly the case when the injective morphism between the fundamental groups of O and R is not surjective. This situation can be explained as follows: let x1 and x2 be two points in the sections S1 and S2 with the same lift x in lift(SC). The lift of any curve γ connecting x1 and x2 in MC provides a non-zero element of π1(lift(SC), x) which is not in the image of L * . We may avoid this situation with the following condition. ´.

We can divide α into subcurves α1, . . . , αm such that αj joins two points xj-1 and xj, and is entirely in the lift of one of the sections Sj, for j = 1, . . . , m. We may assume y0 ∈ S1 = Sm. For each j = 1, . . . , m, let βj be the curve in Sj, joining two points zj to wj, which is mapped to αj under L. Note that wj and zj+1 (possibly) live in two different sections, but have the same image (xj) under the lift map L. Let Xj be the connected component of lift(Sj) ∩ lift(Sj+1) which contains xj, see Figure 4. According to the Intersection Condition, there is a path γj ⊂ MC connecting a point aj ∈ Sj to a point bj+1 ∈ Sj+1 such that lift(aj) = lift(bj+1) = x ′ j ∈ Xj and the image of γj under L is the zero element of π1(lift(SC), x ′ j ) (i.e., is contractible with a homotopy respecting the base point x ′ j ). Since Xj is connected, there is a path from xj to x ′ j in Xj, so lifting back this path to two paths from wj to aj in Sj and from bj+1 to zj+1 and taking the union of these two paths with γj, we infer the existence of a path γ ′ j ⊂ MC connecting wj to zj+1, such that the image of γ ′ j under L is contractible in lift(SC) with a homotopy respecting the base point xj. Putting together all the materials we have obtained, we infer the main theorem of this section.

Theorem 8 (Main Theorem-Part 0) Under the Separation and the Intersection Conditions, RC is homotopy equivalent to OC, for any cell C of the arrangement.

Generalized Nerve Theorem and Homotopy Equivalence of R and O

In this section, we extend the homotopy equivalence between RC and OC, in each cell C, to a global homotopy equivalence between R and O. To this end, we make use of a generalization of the nerve theorem. This is a folklore theorem and has been observed and used by different authors.

For a modern proof of a still more general result, we refer to Segal's paper [START_REF] Segal | Classifying spaces and spectral sequences[END_REF]. (See also [START_REF] May | Finite spaces and simplicial complexes[END_REF], for a survey of similar results.) Theorem 9 (Generalized Nerve Theorem) Let H : X → Y be a continuous map. Suppose that Y has an open cover K with the following two properties:

• Finite intersections of sets in K are in K.

• For each U ∈ K, the restriction H : H -1 (U ) → U is a weak homotopy equivalence.

Then H is a weak homotopy equivalence.

How to Ensure the Intersection Condition?

In Section 2.2, we showed that the Separation Condition can be ensured with a sufficiently dense sample of cutting planes. In this section we provide a sufficient condition that implies the Intersection Condition.

We showed that by upper-bounding the height of the cells by the reach of the object, we can ensure the Separation Condition. In order to ensure the Intersection Condition, we need a stronger condition on the height of the cells. As we will see, this condition is a transversality condition on the cutting planes that can be measured by the angle between the cutting planes and the normal to ∂O at contour-points.

Definition 12 (Angle αa) Let a be a point on the boundary of a section A ∈ SC on the plane PA. We consider mi(a), that may be outside the cell C. We define αa as the angle between PA and the normal to ∂O at a, see Figure 5: αa := angle(PA, [a, mi(a)]).

Sufficient Conditions.

We now define the sampling conditions on the cutting planes. (See 2.4 for the definitions of hC and reachC(O).) Remark on the Transversality Condition.

The transversality of the cutting planes to ∂O seems to be a reasonable condition in practice, specially for applications in 3D ultrasound. Indeed, according to [Rou03] Section 1.2.1, from a technical point of view if a cut is not sufficiently transversal to the organ, the quality of the resulting 2D ultrasonic image is not acceptable for diagnosis.

According to Lemma 2 in Section 2.2, the Density Condition implies the Separation Condition. Also we can show that under the Transversality Condition, the Intersection Condition is verified (the proof is provided in the full version [START_REF] Amini | Geometric Tomography with Topological Guarantees[END_REF]). Therefore, by increasing the density of the sections of O, with preferably transversal cutting planes, we can ensure the required sampling conditions, and consequently, provide a topologically consistent reconstruction of O.

Theorem 11 (Main Theorem-Part II) If the set of cutting planes verifies the Density and the Transversality Conditions, then the Separation and the Intersection Conditions are verified. Therefore, the proposed reconstructed object R is homotopy equivalent to the unknown original shape O.

Deforming the Homotopy Equivalence to a Homeomorphism

Using the homotopy equivalence between R and O, we can show that they are indeed isotopic.

Theorem 12 (Main Theorem-Part III) Under the Separation and the Intersection Conditions, the two topological manifolds R and O are homeomorphic (in addition, they are isotopic).

Although, this result is stronger than the homotopy equivalence, the way our proof works makes essentially use of the topological study of the previous sections.

Proof.

Again, we first argue in each cell of the arrangement and show the existence of a homeomorphism between OC and RC whose restriction to SC is the identity map. Gluing these homeomorphisms together, one obtains a global homeomorphism between R and O. Let C be a cell of the arrangement of the cutting planes. A similar method used to prove the homotopy equivalence between RC and OC shows that ∂R ∩ C and ∂O ∩ C are homotopy equivalent 2-manifolds and are therefore homeomorphic, and in addition there exists a homeomorphism βC : ∂O ∩ C → ∂R ∩ C which induces identity on the boundary of sections in SC. We showed that the topology of RC and OC is completely determined by their fundamental groups, i.e., all the higher homotopy groups of RC and OC are trivial. Moreover, there is an isomorphism between π1(OC) and π1(RC), and the induced map (βC) * : π1(∂O ∩C) → π1(∂R∩C) on first homotopy groups is consistent with this isomorphism (in the sense that there exists a commutative diagram of first homotopy groups). This shows that there is no obstruction in extending βC to a map αC : OC → RC, inducing the corresponding isomorphism between π1(OC) and π1(RC), and such that the restriction of αC to SC remains identity. Since all the higher homotopy groups of OC and RC are trivial, it follows that αC is a homotopy equivalence. We can now apply the following theorem due to Waldhausen, which shows that α can be deformed to homeomorphism between OC and RC, by a deformation which does not change the homeomorphism αC between the boundaries. A compact 3-manifold M is called irreducible if π2(M ) is trivial. We note that OC and RC are irreducible.

Theorem 13 (Waldhausen) Let f : M → M ′ be a homotopy equivalence between orientable irreducible 3-manifolds with boundaries such that f takes the boundary of M onto the boundary of M ′ homeomorphically. Then f can be deformed to a homeomorphism M → M ′ by a homotopy which is fixed all the time on the boundary of M . (See [START_REF] Matveev | Algorithmic topology and classification of 3-manifolds[END_REF], page 220, for a proof.) Applying Waldhausen's theorem, one obtains a homeomorphism αC from OC to RC which is identity on the sections in SC.

Conclusion

In this paper, we presented the first topological studies in shape reconstruction from cross-sectional data. We showed that the generalization of the classical overlapping criterion to solve the correspondence problem between unorganized cross-sections, proposed by Liu et al. in [LBD + 08], preserves the homotopy type of the shape under some appropriate sampling conditions. In addition, we proved that in this case, the homotopy equivalence between the reconstructed object and the original shape can be deformed to a homeomorphism. Even, more strongly, the two objects are isotopic.

Figure 1 :

 1 Figure 1: A 2D illustration of the partition of a cell C by the Voronoi Skeleton VorSkel(C). Left) The original shape OC. Right) The reconstructed object RC.

Definition 5 (

 5 Separation Condition) We say that the set of cutting planes verifies the Separation Condition if MAi(∂O) ⊂ R and MAe(∂O) ⊂ R 3 \ R .

Lemma 1 (

 1 Separation Condition Restricted to C) If the Separation Condition is verified then MAi(∂OC) ⊂ RC and MAe(∂OC) ⊆ C \ RC.

Definition 7 (

 7 Reach) Let O be a connected compact 3manifold with smooth boundary ∂O in R 3 . For a ∈ ∂O, we define reach(a) = min `d(a, mi(a)), d(a, me(a)) ´. The quantity reach(O) is defined as the minimum distance of ∂O from the medial axis of ∂O: reach(O) := min m∈MA(∂O) d(m, ∂O) = min a∈∂O reach(a). Note that as O is compact and ∂O is of class C 1,1 , reach(O) is strictly positive. Definition 8 (Reach restricted to a cell) Given a cell C of the arrangement, we define reachC(O) = min d(a, m(a)), where either a ∈ ∂O ∩ C or m(a) ∈ MA(∂O) ∩ C. By definition, we have reach(O) = minC (reachC(O)). Definition 9 (Height of a Cell) Let C be a cell of the arrangement of the cutting planes. The height of C, denoted by hC, is defined as the maximum distance of a point x ∈ C to its nearest point in the boundary of C. In other words, hC := maxx∈C d(x, np(x)).

Figure 2 :

 2 Figure 2: A 2D illustration of the medial shape.

Proposition 2

 2 Let f OC be the closure of the complementary set of OC in C and f MC be the medial shape of f OC. Under the Separation Condition: (i) There is a strong deformation retract from C \ f MC to OC, and (ii) We have RC ⊂ C \ f MC. Proof. The proof of Property (i) is similar to the proof of Proposition 1 by deforming along the normal vectors to the boundary of f OC. The second property (ii) is equivalent to f MC ⊂ C \ RC.

Figure 3 :

 3 Figure 3: An example of the case where the lift function from MC to lift(SC) fails to be surjective: x1 and x2 are two points with the same lift in lift(SC). The lift of any curve γ connecting x1 and x2 in MC provides a non-zero element of π1(lift(SC), x). The reconstructed object (at left) is a torus and is not homotopy equivalent to the original shape (at right) which is a twisted cylinder.

  Definition 11 (Intersection Condition) We say that the set of cutting planes verifies the Intersection Condition if for any pair of sections Si and Sj in SC, and for any connected component X of lift(Si) ∩ lift(Sj), the following holds: there is a path γ ⊂ MC from a point a ∈ Si to a point b ∈ Sj with lift(a) = lift(b) = x ∈ X so that L * (γ) is the zero element of π1(lift(SC), x), i.e., is contractible in lift(SC) with a homotopy respecting the base point x. In Section 3.5, we will show how to verify the Intersection Condition. Let us first prove the surjectivity of the map L * which is deduced directly from the Intersection Condition. Theorem 7 Under the Intersection Condition, the induced map L * : π1(MC) → π1(lift(SC)) is surjective. Proof. Let y0 be a fixed point for MC and x0 = L(y0). We show that L * : π1 `MC, y0 ´→ π1 `lift(SC), x0 ´is surjective. Let α be a closed curve in lift(SC) which represents an element of π1 `lift(SC), x0 ´. We show the existence of an element β ∈ π1 `MC, y0 ´such that L * (β) = [α], where [α] denotes the homotopy class of α in π1 `lift(SC), x0

Figure 4 :

 4 Figure 4: For the proof of Theorem 7.

Let

  HC : OC → RC be the homotopy equivalence obtained in the previous sections between OC and RC. (So HC is the composition of the retraction OC → MC and the inclusion MC ֒→ RC.) Let H : O → R be the map defined by H(x) = HC(x) if x ∈ OC for a cell C of the arrangement of the cutting planes. Note that H is well-defined since HC|S C = idS C , for all C. In addition, since for all cell C, HC is continuous, H is continuous as well. We can now apply the generalized nerve theorem by the following simple trick. Let ǫ be an infinitesimal positive value. For any cell C of the arrangement of the cutting planes, we define O ǫ C = {x ∈ R 3 , d(x, OC) < ǫ }. Let us now consider the open covering K of O by these open sets and all their finite intersections. It is straightforward to check that for ǫ small enough, the restriction of H to each element of K is a weak homotopy equivalence. Therefore, according to the generalized nerve theorem, H is a weak homotopy equivalence between R and O. And by Whitehead's theorem, H is a homotopy equivalence between R and O. Thus, we have: Theorem 10 (Main Theorem-Part I) Under the Separation and Intersection Conditions, the reconstructed object R is homotopy equivalent to the unknown original shape O.

(

  C1) Density Condition For any cell C of the arrangement, hC < reachC(O).

Figure 5 :

 5 Figure 5: Definition of αa

  Gluing αC , one obtain a global homeomorphism form O to R. Moreover, according to Chazal and Cohen-Steiner's work [CCS05] (Corollary 3.1), since R and O are homeomorphic and R contains the medial axis of O, R is isotopic to O. ✷

  RC → lift(SC) is also a homotopy equivalence and because of the commutativity of the above diagram, the inclusion i : MC ֒→ RC induces isomorphisms between the homotopy groups of MC and RC. Thus, Whitehead's theorem implies that i is a homotopy equivalence. We first show that under the Separation Condition, the restricted lift function L |M C induces injections on the level of homotopy groups.

	i	RC / /
	? ? ? ? ? ? ? ? ?
		lift(SC)

L L

More precisely, if L : MC → lift(SC) is a weak homotopy equivalence (what we will prove below), since L :

Recall that for simplifying the presentation, we assume that OC and so RC are connected. The same proof shows that in the general case, the same property holds for each connected component of OC or RC.

Acknowledgments

This work has been partially supported by the High Council for Scientific and Technological Cooperation between Israel and France (research networks program in medical and biological imaging).