ОБ ОПТИМАЛЬНОМ КРИТЕРИИ ДЛЯ ВОССТАНОВЛЕНИЯ ПОВЕРХНОСТЕЙ ПОСРЕДСТВОМ ПРЯМОЛИНЕЙНОЙ ГОМОТОПИИ

Берзин Д.В.

Кандидат физико-математических наук, доцент,

Финансовый университет при Правительстве Российской Федерации, Москва

ОБ ОПТИМАЛЬНОМ КРИТЕРИИ ДЛЯ ВОССТАНОВЛЕНИЯ ПОВЕРХНОСТЕЙ ПОСРЕДСТВОМ ПРЯМОЛИНЕЙНОЙ ГОМОТОПИИ

Аннотация

Восстановление (реконструирование) поверхностей из их поперечных сечений является важным для множества практических применений. И минимальная площадь здесь - это один из наиболее естественных оптимальных критериев. В работе мы рассматриваем частный случай - минимальные поверхности, восстановленые методом прямолинейной гомотопии. Мы показываем, что в таком случае данный критерий приводит к недопустимым поверхностям, а, значит, неприемлем.

Ключевые слова: геометрическое моделирование, гомотопия, оптимизация

 Berzin D.V.

PhD,  Associate Professor,

 Financial University under the Government of the Russian Federation, Moscow

ON OPTIMAL CRITERION FOR STRAIGHT-LINE HOMOTOPY SURGACE RECONSTRUCTION

Abstract

Surface reconstruction from cross-sectional data is important in a variety of applications. Minimal area is one of most natural optimal criteria for the original tiling method of surface reconstruction from cross sections. In the paper we consider a particular case - minimal surfaces for straight-line homotopy reconstruction from cross sections. We show that in this case the minimal area criterion leads to defective surfaces and thus unacceptable.

Keywords: geometric modeling, homotopy, optimization 

1. Introduction

There is often a need for reconstructing an object from its cross sections, i.e. planar contours. For example, in medicine, constructing the shape of an organ from sections is of great significance [Tam and Davis 1988]. Such surface models are advantageous for animation [Shinagawa et al. 1990], and also when modification of contour data is necessary. We want to mention some other applications of shape reconstruction from cross-sectional data: automatic construction of surfaces in computer-aided design systems; construction of geographic terrain surfaces from topographic maps; automatic generation of surfaces from CT images and MRI slices; shapes reconstruction in microscopy; volume calculations of human body components from reconstructed cross-sectional X-rays for diagnosis and therapy [Brooks and DiChiro 1975].

Of course, there are many approaches for surface generation from contours. Using the original triangular tiling method [Keppel 1975], [Fuchs et al. 1977], firstly, one should choose two adjacent contours and a finite number of points on each of the contours. Then every vertex of a corresponding toroidal graph depicts an edge of a triangle. The graph has many acceptable subgraphs. Hence, some kind of optimization criterion is necessary: one should reconstruct a triangular tiling in a natural manner avoiding invalid surfaces.

A surface of minimal area is one of most acceptable ways for such a reconstruction [Fuchs et al. 1977]. Note that the problem of searching a minimal area surface is old and famous one. It can be shown that a soap film bounded by some wire contours is a minimal surface. The connection between minimal surfaces and soap films motivated the celebrated Plateau’s problem [Dao and Fomenko 1991].

The straight-line homotopy for surface reconstruction from planar contours was proposed in [Shinagawa and Kunii 1991]. Their approach is a natural continuous generalization of the original tiling method, and it can produce smoother surfaces than the triangular one. However, no effective criteria for the surface reconstruction were proposed in the paper. Authors suggested generating shapes from cross-sections by means of minimal surfaces, but did not examine this case.

We investigate an applicability of minimal area criterion not only in the situation of straight-line homotopy, but also in the framework of arbitrary reconstruction from contours.

2. Surface reconstruction from cross sections and optimal criteria

As a start point, let us give some necessary definitions.

Let  ( x , y , z ) be standard coordinates in three-dimensional Euclidean space R³ . Consider a curve f (u) = (f ^x (u), f ^y (u), d), homeomorphic to circle, where u [0,u¹ ],  f (0) =  f (u¹) , f (u) is a continuous function, and  d  being a real number. The curve f (u)  is called a (planar) contour.

There are usually many slices of an object, and a set of contours {fⁱ =  (f ^_i x(u), f ^{_i y}(u), dⁱ ) } occurs, where numbers d are not all necessarily distinct. The goal is to reconstruct a good surface from the cross-sectional data quickly and with a minimum of user interaction. The desired surface should be satisfactory for human visual perception and aesthetic requirements, in other words, it must be smooth, a natural looking and so on. We call such a surface a reasonable. Otherwise, the surface is called invalid or defective. To generate a reasonable surface from cross-sections, some optimal criterion is usually necessary.

The problem to reconstruct a surface from planar contours can be decomposed into three main subproblems: the correspondence problem (which contours from one slice should be connected to which contours in neighboring slices?); the optimal concatenation problem (how to restore a shape from corresponding contours in some optimal way?); the branching problem (how should m contours in one slice be attached to the n corresponding contours in a consecutive slice?). For triangular tiling the second problem becomes a tiling problem (what is the optimal strip of triangles for joining contours from consecutive slices?). Excellent reviews, concerning these problems and the solutions by different authors, were presented in [Jones and Chen 1994], [Meyers et al. 1992], [Sloan and Painter 1988].

First of all, let us give a short description of the original triangular reconstruction method, based on graph representation (it is necessary for Section 3). For details, see [Keppel 1975], [Fuchs et al. 1977].

Let contours

                    (1)

where d¹≠ d² ,  be defined by a sequences of  m  distinct contour points  P⁰, P¹  ,…, P^m-1, and  n  distinct contour points  Q⁰, Q¹ ,… , Q^n-1 respectively. Note that these contours have the same orientation and  P⁰ follows P^m-1, and  Q⁰ follows Q^n-1  (Fig. 1).

The desired surface is constructed as triangular tiles. The vertices of tiles are contour points, with the vertices of each tile taken two from one sequence and one from the other. Without loss of generality we assume that all tiles belonging to the surface are triangles either of the form {Pⁱ , P^{i+1(mod m)}, Q^j} or the form {Q^j , Q^{j+1(mod n)} , Pⁱ }. We want the tiles to “fit” together; hence, restrict consideration to those sets of tiles that provide so-called acceptable surfaces, homeomorphic to cylinder. Of course, there are very many sets of tiles, which satisfy the above conditions. Hence, some criteria should be used to choose optimal surfaces from these sets.

 

Fig. 1 - Two contours with contour points

Define a directed toroidal graph G={V, E}, where the vertices correspond to a set of all possible spans between the points P⁰, P¹  ,…, P^m-1  and the points Q⁰, Q¹ ,… , Q^n-1, and the edges correspond to the set of all possible tiles (Fig. 2, left). Any set of tiles can be viewed as a subgraph S  of the graph G. Subgraphs of G, corresponding to acceptable surfaces, are called acceptable subgraphs.

Associate with each edge {v^ki , v^st} of G  a cost C({v^ki , v^st}) chosen from the set of real numbers. The cost of a trail is defined as the sum of costs of the edges traversed by it. An optimal surface is one that corresponding trail is of minimal (or maximal) cost. Instead of G, it is convenient to consider a planar graph G' obtained from toroidal graph G. Graph G'  is constructed by cutting G and gluing together two copies of the rectangle (Fig. 2, right). There exists a one-to-one correspondence between the set of acceptable trails in G that start and end at vⁱ⁰  and the set of paths from vⁱ⁰   to  v^m+i,n  in G'. Thus, the problem of finding an optimal cost acceptable trail in the toroidal graph G  is reduced to finding an optimal cost path in the corresponding planar graph G'. In Fig.2 (right) one can see subgraph S'  corresponding to subgraph S in Fig.2 (left).

Fig.2 - Toroidal graph and planar graph

 

The optimal criterion (cost metric) Keppel chooses to produce a reasonable surface is known as maximize volume. The idea is to assign a volume, which triangle adds to the surface by treating it as a face of tetrahedron, to each edge of the graph. Fuchs et al. proposed to assign to each edge of graph the area of the corresponding tile. Then the cost of a path is a sum of numbers, corresponding to each edge in the path. The problem is to find a minimal cost path. An example of human head surface reconstruction based on this minimal area criterion was shown in [Fuchs et al. 1977]. However, the methods  construct reasonable surfaces only in simple cases without branchings.

A parallel algorithm based on the graph representation was proposed in [Johnson and Livadas 1994].

In the methods [Keppel 1975], [Fuchs et al. 1977] graph representation was used to find an optimal solution mathematically. Contrary, heuristic methods use some optimal criterion locally and only as a basis for surface reconstruction. The heuristic shortest diagonal method [Christiansen and Sederberg 1978] starts the triangulation from proximate points P⁰ and Q⁰, and after vertices Pⁱ and Q^j are connected with a span, the shortest of  Pⁱ Q^j+1  and Pⁱ⁺¹ Q^j  is selected as the next span in the triangulation. This algorithm copes well only with simple branching and produces defective surfaces when two consecutive contours differ widely in shape. A simple contour branching scheme based on that of Christiansen and Sederberg was proposed in [Giersten et al. 1990]. In [Ekoule et al. 1991] a minimum edge length heuristic was considered too, but authors cope with complex branching. [Ganapathy and Dennehy 1982] use the heuristic method of normalizing the contour perimeter to unit. Heuristics for tiling are also used in [Cook et al. 1983]. Authors assume that contours change directions smoothly and slowly and use special mapping techniques. Soroka used elliptical cones for surface reconstruction [Soroka 1981], but the method can only model simple convex objects. [Meyers et al. 1992] present significant progress on the correspondence and branching problems. Their method for elliptic cones differs from that of Soroka in that complex contours are not omitted. [Shinagawa and Kunii 1991] proposed one more heuristic method. The main idea is to find a subgraph, which goes through vertices corresponding to closest pairs  (Pⁱ ,Q^j), i.e. pairs, satisfying the conditions

d(Pⁱ ,Q^j ) =^min_0≤k<n d(Pⁱ ,Q^k)  and  d(Pⁱ ,Q^j) =^min_0≤k<m d(P^k ,Q^j), where d(P ,Q ) is Euclidian distance between points P  and Q. However, the method does not solve the branching problem.

Another approach to restore a surface from cross sections is Delaunay triangulation [Boissonnat 1988]. This method for contours can be regarded as a particular case of more general problem, namely, reconstruction from a finite set of unorganized points. Despite this approach has a robust theoretical basis, often it produces unnaturally “convex” shapes.

The surface generated by a triangulation method depends heavily on the choice of the contour points for connection to each other. The problem of greatly differing contours is also a major problem for the tiling methods. Artificial wrinkles thus generated cannot be eliminated even with a usage of smooth shading. None of the above tiling algorithms correctly handle contour sets with abutting structures.

New non-triangulation approach is proposed in [Jones and Chen 1994]. The authors use a field function to convert the data into a volume numerical data, from which the surface is derived. The novel approach of first voxelizing contours and then extracting surfaces from that voxelization was also taken in [Weinstein 2000]. His method is based on scanline rendering and separating surface extraction.

An algorithm of surface reconstruction from cross sections as a particular case of shape generation from a set of unorganized points is proposed in [Savchenko et al. 1995]. It can be regarded as a continuous approach to surface reconstruction. The authors use an interpolation by particular spline functions, and minimization of corresponding variational functional as the optimal criterion. The method generates surfaces with branchings automatically, and in case when contours do not overlap produces a similar result to one in [Jones and Chen 1994]. However, the authors present only simple examples. Thus, it is unclear whether the algorithm handles with complex cases or not. Moreover, if two consecutive contours differ greatly in size the method can generate “concave” defective surfaces.

3. Minimal surfaces for straight-line homotopy reconstruction

Consider again two planar contours (1).

Definition. Continuous function F : U×I→R^ε , where F(u,0) = f(u), F(u,1)=g(u), I= [0, 1] , connects contours (1) by a homotopy that produce a surface between  f  and  g  (Fig. 3).

 

Fig.3 - Connecting contours by a homotopy

In the case of many slices surface reconstruction can be regarded as a combination of homotopies.

A continuous generalization of the “discrete” toroidal graph representation was proposed in [Shinagawa and Kunii 1991]. Consider contours f (t) = (f^x (t), f^y (t), 0) and ｇ(u) = (g^x (u), g^y (u), d), where t∈ [0,t¹], u∈ [0,u¹]. Consider two glued copies of a rectangle [0,t¹] × [0,u¹],  i.e. the rectangle [0,2t¹] × [0,u¹]. The problem is to construct a monotonically increasing continuous weight function u(t), u: [t⁰ ,t¹+t⁰] → R , Im(u)=[0,u¹] , 0 ≤t⁰<t¹  , satisfying some optimal criterion. In other words, step “function” from the discrete version (Fig.2, right) is replaced by a monotonically increasing weight function u(t) in continuous version (Fig.4).

Fig. 4 - Weight function

Every point (t,u(t)) corresponds to a straight-line segment, which connects a point from one contour with a point from the other one. We will call this approach the straight-line homotopy. As an example of optimal criteria for straight-line homotopy Shinagawa and Kunii proposed to use a piece-wise linear weight function that goes through closest pairs, but it is unclear how to determine such pairs in this continuous version. Their second suggestion is to generate minimal area surfaces in the framework of straight-line homotopy, but they have not investigated it.

Denote S(f,g) a set of all surfaces, that can be constructed by a homotopy between contours (1). Let SC(f,g)  be a set of all surfaces constructed by straight-line homotopy, which connects contours f and g, SC(f,g) ⊂  S(f,g).

Definition. We call a surface M ∈ S(f,g) minimal surface, if its area is minimal among the areas of all surfaces from the set S(f,g).

It is known, that regular surface M ∈ S(f,g) is minimal, if and only if its mean curvature vanishes everywhere (for strict mathematical definitions, see, e.g., [Fomenko and Kunii 1997]).

The problem of searching for a minimal surface M ∈ SC(f,g) appears in a natural way and was raised in [Shinagawa and Kunii 1991]. In other words: to find a monotonically increasing continuous function u(t) in the continuous toroidal graph representation, that gives a minimal area surface.

Let us start with a simple case. Consider two contours  f^c   and g^c  represented in polar coordinates:

                  (2)

In other words, consider two circles with radii R , and 2h is the distance between parallel planes, where they are situated.

Remark. It is evident, that in this case the reasonable surface is a cylinder.

Firstly, let us understand, what is a SC(f^c ,g^c ) surface, which has z as the axis of symmetry. For this end, suppose u=t+φ , and represent a surface from SC(f,g), in the form

                  (3)

where -1 ≤ v ≤ 1, A=(r,0,0), α=φ /2, A² = g^c (t+φ), A¹ = f^c (t), and vectors AA² and A¹A are equal (Fig. 5).

Fig. 5 - Hyperboloid is a straight-line homotopy surface

Obtaining the relation cos α = r/R easily, we come to the equation

                       (4)

where -h ≤ z ≤ h. It is well known, that (4) is the equation of hyperboloid, that is a surface of revolution obtained by rotating the hyperbola

about the z-axis (0 < r < R ). Here r is the radius of the minimal circle (corresponding to the level z=0 ), so-called striction line. To calculate the area of the hyperboloid, we use the formula for surfaces of rotations (see, e.g., [Carmo 1976]):

                    (5)

Calculations lead to

                   (6)

where  c = (R² - r² )(R² - r² +h² )/ h² . It is not so easy to handle (6), but computations with computer make the situation clearer (see Section 5). Hence, we come to the following statement.

Proposition 1. Surface, obtained by a straight-line homotopy (i.e. a surface contained in SC(f^c ,g^c )) and symmetric over z-axis, is a hyperboloid (4) with the area (6) and with the weight function

u(t) = t+φ , t ∈ [2^π-φ ;4^π-φ],  where φ = 2arccos(r/R).

According to the symmetry concept, we can assert, that minimal surface in the set SC(f^c ,g^c )) is a hyperboloid. Without loss of generality assume h=1 , and let h=1  be fixed. For each R  denote H(R,r)  a hyperboloid with equation (4), and let H'(R)  be a hyperboloid that gives a minimal area in SC(f^c ,g^c ): S(H'(R))=min_0<r<R S(H(R,r)), where S denotes an area of a surface. Computations support the idea, that area S(H'(R)) of the hyperboloid H'(R) is less than the area S(cyl)=4^π R  of the corresponding cylinder (see Section 5). One can see that the less the radius R, the larger the ratio  k  between the area of the cylinder and the area of the hyperboloid. If r approaches zero, hyperboloid approaches the union of two cones. If  R/h< , the area of the union is less than the area of the corresponding cylinder, and k  → 2, when    R  → 0.

References

 

1. Boissonnat JD (1988) Shape reconstruction from planar cross sections. Comput. Vision, Graphics, and Image Processing, 44(1):1-29.
2. Brooks RA, DiChiro G (1975) Theory of image reconstruction in computed tomography. Radiology 117:561-572
3. Carmo MP (1976) Differential geometry of curves and surfaces. Prentice-Hall inc., New Jersey London Sydney Toronto New Delhi Tokyo Singapore
4. Christiansen HN, Sederberg TW (1978) Conversion of complex contour line definitions into polygonal element mosaics. SIGGRAPH 12:187-192
5. Cook LT, Dwyer SJ, Batnitzky S, Lee KR (1983) A three-dimensional display system for diagnostic imaging applications. IEEE computer graphics and applications 3(5):13-19
6. Dao TT, Fomenko AT (1991) Minimal surfaces, stratified multivarifolds, and the Plateau problem. Amer. Math. Society. Translations of Math. Monographs 84
7. Ekoule AB, Peyrin FC, Odet CL (1991) A triangulation algorithm from arbitrary shaped multiple planar contour. ACM Trans. Graph. 10:182-199
8. Fomenko AT, Kunii TL (1997) Topological modeling for visualization. Springer, Tokyo Berlin Heidelberg New York
9. Fuchs H, Kedem ZM, Uselton SP (1977) Optimal surface reconstruction from planar contours. Commun ACM 20:693-702
10. Ganapathy S, Dennehy TG (1982) A new general triangulation method for planar contours. Proc ACM SIGGRAPH 16:69-75
11. Giersten C, Halvorsen A, Flood PR (1990) Graph-directed modeling from serial sections. Vis. Comput. 6:284-290
12. Jones MW, Chen M (1994) A new approach to the construction of surfaces from contour data. Proc Eurographics 75-84
13. Johnson T, Livadas PE (1994) A parallel algorithm for surface-based object reconstruction. J. Math. Imaging Vis. 4:389-400
14. Keppel E (1975) Approximating complex surfaces by triangulation of contour lines. IBM J. Res. and Development, 19(1): 2-11
15. Meyers D, Skinner S, Sloan K (1992) Surfaces from contours. ACM Trans. Graph. 11(3): 228 – 258
16. Savchenko VV, Pasko A, Okunev O, Kunii TL (1995). Function representation of solids reconstructed from scattered surface points and contours. Computer Graphics Forum 14(4):181-188
17. Shinagawa Y, Kunii TL, Nomura Y, Okuno T, Young YH (1990) Automating view function generation for walk-through animation. Proc. Comput. Animation 227-237
18. Shinagawa Y, Kunii TL (1991) The homotopy model: a generalized model for smooth surface generation from cross sectional data. Vis. Comput. 7: 72-86
19. Sloan KR, Painter J (1988) Pessimal guesses may be optimal: A counterintuitive search result. IEEE Trans. on PAMI 10(6): 949-955
20. Soroka BI (1981) Generalized cones from serial sections. Comput. Graph. and Image Processing 15(2): 154-166
21. Tam Y, Davis W (1988) Display of 3D medical images. In: Graphics Interface 78-86
22. Weinstein D (2000) Scanline Surfacing: Building Separating Surfaces from Planar Contours. Proc IEEE Visualization 2000 : 283-289.