max planck institut
informatik
informatik
Investigators: Yutaka Ohtake, Shin Yoshizawa, and Alexander Belyaev
Ridge-valley lines, curves on a surface along which the surface bends sharply, are powerful shape descriptors. Their robust detection is important for medical image analysis, shape quality control, reverse engineering, face recognition, and many other applications. However a reliable detection of ridge-valley structures on surfaces approximated by polygonal meshes is extremely difficult because it requires an accurate estimation of curvature derivatives.
In [OBS04] we propose to use an implicit surface fitting procedure for detecting view- and scale-independent ridge-valley structures (the so-called crest lines) on surfaces approximated by dense triangle meshes. We demonstrate that the ridges and valleys are perceptually salient surface features that can be used for shape compression, recognition, and quality evaluation purposes.
In [YBS05], we develop a fast and robust method for detecting the ridge-valley lines on surfaces approximated by dense triangle meshes. The method is based on estimating the curvature tensor and curvature derivatives via local polynomial fitting. A finite difference scheme/test proposed in [OBS04] is used for curvature maxima/minima identification. Our new thresholding scheme exploits interesting relationships between curvature extrema, variational functionals, and Dupin cyclides. Fig.0.1 shows patterns of ridges and valleys found on simple and complex geometrical models.
Investigators: Rhaleb Zayer, Zachi Karni, Christian Rössl, and Shin Yoshizawa
Surface parametrization is a fundamental problem in computer graphics. Its relevance to a wide range of applications such as texture mapping, mesh morphing and medical imaging makes it an active area of research. Given a surface mesh with disk topology, the aim is to establish a planar parametric representation of the surface. Linear parameterization methods are of particular interest; their simplicity, efficiency, and robustness enables the processing of detailed, large meshes, given well defined boundary conditions. In practice, however, the current linear schemes are limited to producing discrete conformal parameterizations [DMA02,Flo03] and hence may suffer from considerable distortion e.g. in length and area, see Figure 0.2. We introduce new linear operators for surface parameterization [ZRS05]. In contrast to most linear methods mainly relying on the Laplace equation, our work is based on the crucial observation that the general quasi-harmonic equation can account for area distortion as well as angle distortion. This construction is driven by a tensor field, which captures the mapping of each triangle, and the resulting parameterization provides control over distortion while maintaining smoothness of the solution, see Figure 0.2.
|
In [YBS04] we propose a fast and simple method for generating a low-stretch mesh parameterization. Given a triangle mesh topologically equivalent to a disk, we start from the Floater shape preserving parameterization [Flo97] and then improve the parameterization gradually. At each improvement step, we optimize the parameterization generated at the previous step by minimizing a weighted quadratic energy
|
where the weights are chosen in order to minimize the parameterization stretch. We redistribute the local stretches by assigning
|
where
|
are local stretches estimated from the previous step at the inner mesh vertices. Our method is much faster than that of [SSGH01] and its extensions and generates higher quality mesh parameterizations.
|
Angle Based Flattening [SdS01] is a robust parameterization technique allowing a free boundary. The numerical optimization associated with the approach rises a challenging problem. We discuss several approaches to effectively reduce the computational effort involved and propose appropriate numerical solvers [ZRS03,ZRS04b]. A simple but effective transformation of the problem which reduces the computational cost and simplifies the implementation is proposed. We also show that fast convergence can be achieved by finding approximate solutions which yield a low angular distortion. Further investigation of this topic convinced us that it is possible to improve these results [ZRS04a]. We propose two iterative approaches to overcome the numerical challenges arising in this problem. The first approach is based on the fact that decoupling the system yields a much easier matrix equation. This enables an iterative approach for carrying out the computations. The second approach is based on the analysis of saddle point problems and introduces a modified Uzawa algorithm for efficiently addressing the numerical optimization problem.
In collaboration with Craig Gotsman and Steven Gortler.
Linear parameterization of 3D meshes with disk topology is usually performed using the method of barycentric coordinates pioneered by Tutte and Floater [Flo97,Tut63]. This imposes a convex boundary on the parameterization which can significantly distort the result. Recently, several methods showed how to relax the convex boundary requirement while still using the barycentric coordinates formulation [DMA02,LKL02]. However, this relaxation can result in other artifacts in the parameterization.
For many applications, in particular those involving texture mapping and remeshing, it is desirable that the parameterization satisfy hard constraints on the embedded positions of some of the mesh vertices. This makes the parameterization problem much more difficult. It renders the linear systems used in the method of barycentric coordinates overdetermined, no matter whether the boundary is fixed or free. Hence, satisfying the constraints usually comes at the expense of the injectivity of the parameterization, and it will typically contained flipped triangles.
In [KGG05] we explore linear free-boundary methods and give a general recipe for natural boundary conditions for the family of so-called three point barycentric coordinates. We introduce two methods to generate injective free-boundary parameterizations. Both methods are 2D reproducing. One method is iterative capable also of satisfying a set of given constraints, if this may be done without introducing Steiner vertices. Figure 0.4 demonstrates two constraints facial texture mapping examples.
 |
Investigators: Holger Theisel, Christian Rössl, and Rhaleb Zayer
In [TRZS04], we introduce a new technique for estimating the curvature tensor of a triangular mesh. The input of the algorithm is only a single triangle equipped with its (exact or estimated) vertex normals. The basic idea for doing so comes from the well-known concept of Phong-shading: given a triangle of a mesh together with its vertex normals, two linear interpolations are applied. The linear interpolation for the vertices gives the current location, while the linear interpolation of the vertex normals gives the normal for the illumination model. Although a certain error is taken to account (the normal from the piecewise linear surface generally differs from the interpolated normal), this approach has been proven to produce smooth-looking representations of meshes.
Bearing in mind that the curvature tensor of a smooth surface is completely defined by its first order partials and the first order partials of its normals, we can use the idea of Phong shading to get an estimation of the curvature tensor on a single triangle: we use the linear interpolation of the vertices to get the surface and its first order partials, while the normals and its first order partials are obtained from the linearly interpolated vertex normals. Similar to Phong shading, this introduces a certain error which is due to the application of two different linear interpolations. However, we show that this error can compete with the errors of other estimation schemes of the curvature tensor. If the exact normals of the underlying surface are available at the vertices, the error drops significantly.
Investigators: Torsten Langer and Alexander Belyaev
 |
Given a dense triangle mesh approximating a smooth surface, one of the most fundamental problems consists of accurate estimating the curvature tensor. The mean curvature vector is related to the Laplacian and core of many smoothing and fairing algorithms, Gaussian curvature is a measure of deviation from flatness, and the principal directions can be used for ``geometrically meaningful'' remeshing. Mean curvature, Gaussian curvature and principal directions together are often referred to as curvature tensor. It is essential for many more tasks, like mesh segmentation, feature detection and non-photorealistic rendering.
In [LBS05] we presented a novel approach that makes use of the formulation of the curvature tensor as an integral. We introduced a quadrature formula to compute this integral exactly from the directional curvatures. We demonstrated the usefulness in practice and showed that our algorithm combines short running times and accurate results. Furthermore, we proved that our estimated curvature tensor converges towards the correct curvature tensor if denser and denser meshes are used. Our method combines a solid mathematical foundation with a high practical value.
Investigators: Hitoshi Yamauchi, Seungyong Lee, Yunjin Lee, Yutaka Ohtake, and Alexander Belyaev
Feature sensitive mesh segmentation is important for many computer graphics and geometric modeling applications. In [YLL+05], we develop a mesh segmentation method which is capable of producing high-quality shape partitioning. It respects fine shape features and works well on various types of shapes, including natural shapes and mechanical parts. The method combines a procedure for clustering mesh normals with a modification of the mesh chartification technique [SWG+03]. For clustering of mesh normals, we adapt Mean Shift, a powerful general purpose technique for clustering scattered data. We demonstrate advantages of our method by comparing it with two state-of-the-art mesh segmentation techniques.
Investigators: Hitoshi Yamauchi and Jörg Haber
In [YHS03], we introduce an image restoration method which consider both large structure and small details of an image. The algorithm is based on two common techniques: image inpainting and texture synthesis.
Image inpainting is a reconstruction method which solves a partial differential function (PDE) to fit a smooth function. This method can construct large structure of an image, but fitting a smooth function can hardly reconstruct small details. Texture synthesis searches portions of image in the input image, and transfer the most plausible pixel to fill in the missing part of an image. This method can reconstruct small details of input image, however, the large structure part could not be reconstructed since this method does not consider the continuity of the input.
The function of the both methods are compliment, however, the mathematical basics are totally different, PDE and search. Then, how to combine both method is not trivial.
To break this problem, we employ the view point of signal processing. Solving PDE reconstructs low frequency part of an image and texture synthesis reconstructs high frequency part of an image. Therefore, we analyze an input image through DCT and reconstruct the low frequency part by PDE based reconstruction and high frequency part is reconstructed by texture synthesis method.
|
|
|
|
|
|
|
|
Investigators: Stefan Gumhold and Zachi Karni
Investigator: Stefan Gumhold
The development of customized compression techniques for polygonal meshes has been stimulated by the pioneer work of Deering [Dee95]. On the one hand stand methods with reasonably good compression rates which are very fast [GS98] and allow for compression of huge polygonal meshes [IG03]. On the other hand rises the question how optimal the methods are and whether we can come up with a compression technique that is optimal in the information theoretic sense. Here we followed the latter question for the compression of connectivity and geometry of triangular meshes.
|
The connectivity of a triangular mesh is a discrete, graph-like, combinatoric entity describing in which way the vertices are connected together with triangles. An early work of Tutte [Tut62] showed that the asymptotic information theoretic lower bound for the encoding of a planar triangular connectivity graph is
|
bits per vertex, where it is assumed that it is allowed to permute the indices of vertices and triangles. But only recently this lower bound has been matched with an optimal compression technique also from above by Poulalhon and Schaeffer [PS03]. In [Gum05] we developed a coding back-end based on a Markov Probability Model for the well-known edge-breaker encoding scheme [Ros99]. A Markov Model is a finite state automaton with transition probabilities and it can be mapped directly to an arithmetic coder. In an early work [Gum00] we proposed a method for the design of such probability models resulting in an upper bound of 3.5 bits per vertex, where the result not only holds for planar connectivity graphs but for connectivities of triangular meshes with arbitrary topology. In the latest work [Gum05] the transition probabilities of the Markov Models have been optimized in order to achieve a lowest upper bound. Figure 0.8 shows the resulting bit rates in dependence on the number of states in the used Markov Models. The more states used the more constraints on the edge-breaker symbols can be exploited. The diagram shows that one can come very close to the information theoretic lower bound of planar triangular connectivities also for the non planar case. Furthermore is the resulting coding back-end very efficient and can be attached to the easy to implement edge-breaker coding scheme.
The encoding of mesh geometry, i.e. the 3D vertex locations, cannot be captured as well in terms of information theoretic upper and lower bounds. Similar to the settings for image compression do we seek for optimal coding schemes in the rate-distortion sense, i.e. we want to minimize the bit-rate for a given bound on the distortion. The result is then not anymore a simple number but a rate-distortion curve plotting the achieved bit-rates over the distortion bound. The comparison between two rate-distortion curves is typically not easy. For the case of 2D geometry Ben-Chen and Gotsman [BCG04] showed that the transformation into the eigenbasis of the adjacency matrix of the connectivity graph orders the geometry components optimally in a rate-distortion sense, i.e. if we assume that each vertex coordinate costs b bits, skipping from all n coordinates the first k transformed coordinates results in the bit-rate bk/n, which is optimal for the distortion of the inverse transformation of the reduced set of transformed coordinates. This is a lower bound for a quite general class of 2D mesh geometries. For the case of 3D coordinates no bounds are known and it is not clear if the geometries encountered in practice are not from a more specific class of geometries, where for example a strong correlation exists between the different coordinate directions. Furthermore, are all these bounds related to mesh geometry and not to the geometry of the underlying shape.
In the work [Gum04] we investigated a coding scheme that allows to exploit redundancy in the mesh that is not necessary to describe the shape. The scheme is based on predictive coding and uses a different quantization step. Most methods pre-quantize the vertex coordinates to b bits on an evenly spaced 3D grid in a global or local coordinate system. We allow on the other hand that the position of a vertex is quantized into a region which does not alter the underlying shape. These regions are called validity regions and defined for each vertex as the points in space to which we can move the vertex without introducing a Hausdorff distance larger than a distortion bound E. In this way we switch from a vertex-to-vertex distortion measure to shape distortion measure. Figure 0.9 illustrates the proposed shape-adaptive quantization approach. It shows the original mesh in light gray. The validity region around the original vertex is the ellipse shaded in very light gray. The predicted location is shown in red. A hierarchical quantization grid is built around the predicted location in the local coordinate system. In uniform quantization the quantized location would be the small red ball on the dashed red grid lines. In the adaptive quantization approach one can choose from all valid grid locations (inside the validity region) the one with the smallest coding cost. To minimize the coding cost we assign for each possible quantized coordinate a cost depending on the level in the hierarchical quantization grid and choose as quantization location the one with the minimal cost - in the example the blue grid location. This favors indices on higher quantization levels increasing their number in a way that a standard adaptive arithmetic coder can exploit automatically. Between two and three bits can be saved per vertex with the new shape adaptive quantization approach. Although the compression tasks of the proposed scheme becomes more time consuming, the decompression is as fast as with any other predictive coding scheme.
Investigator: Zachi Karni
In collaboration with Craig Gotsman.
3D animation appears in two forms: rigid-body and soft-body motion. In rigid-body motion, the relative position of each two vertices of the mesh stays fixed and the body moves as one entity. Soft-body motion does not impose any restrictions on the relation between an object's vertices (as long as they form a valid mesh). It consists of a separate trajectory for each mesh vertex, which allows capturing of smooth and realistic motion. However, the size of files storing this data is usually very large because each frame is actually a complete 3D object. This is a major factor preventing soft-body motions from becoming popular or suitable for real-time rendering. They are mostly used in offline rendering scenarios, such as high-quality rendered animation clips for the movie industry.
In [KG04] we describe a compression scheme for the geometry component of 3D animation sequences. This scheme is based on the Principle Component Analysis (PCA) method, which represents the animation sequence using a small number of basis functions. Second order Linear Prediction Coding (LPC) is applied to the PCA coefficients in order to further reduce the code size by exploiting the temporal coherence present in the sequence. Our results show that applying LPC to the PCA scheme results in significant performance improvements relative to other coding methods. Use of these codes will make animated 3D data more accessible for graphics and visualization applications.
 |
