KEYWORDS: Visualization, Algorithms, Computing systems, Raster graphics, Denoising, Image filtering, Visual process modeling, Data modeling, Digital filtering, Geographic information systems
Height fields are an important modeling and visualization tool in many applications and their exploration requires their
display at interactive frame rates. This is hard to achieve even with high performance graphics computers due to their
inherent geometric complexity. Typical solutions consist of using polygonal approximations of the height field to reduce
the number of geometric primitives that need to be rendered. Starting from a rough approximation, a refinement process
is operated until a desired level of detail is reached. In this work, we present a novel efficient algorithm that starts with
an approximation that carries enough information about the height field so that only few refinement steps are needed to
achieve any desired level of detail. Our initial approximation is a simple triangulation whose nodes are the critical points
of the height field, that is the peaks, pits, and passes of the surface which give its overall shape. The extraction of critical
points of the surface, which is a discrete structure, is done using a newly designed algorithm based on discrete Morse
theory and computational homology algorithms. 1-3
In this paper, we use concepts from digital topology for the topological filtering of reconstructed surfaces. Given a finite set
S of sample points in 3D space, we use the voronoi-based algorithm of Amenta & Bern to reconstruct a piecewise-linear
approximation surface in the form of a triangular mesh with vertex set equal to S. A typical surface obtained by means of
this algorithm often contains small holes that can be considered as noise. We propose a method to remove the unwanted
holes that works as follows. We first embed the triangulated surface in a volumetric representation. Then, we use the 3D-hole
closing algorithm of Aktouf et al. to filter the holes by their size and close the small holes that are in general irrelevant
to the surface while the larger holes often represent topological features of the surface. We present some experimental results
that show that this method allows to automatically and effectively search and suppress unwanted holes in a 3D surface.
The exploration of multidimensional scalar fields is commonly based on the knowledge of the topology of their isosurfaces.
The latter is established through the analysis of critical regions of the studied fields. A new method, based on homology
theory, for the detection and classification of critical regions in multidimensional scalar fields is proposed in this paper. The
use of computational homology provides an efficient and successful algorithm that works in all dimensions and allows to
generalize visual classification techniques based solely on the notion of connectedness which appears insufficient in higher
dimensions. We present the algorithm, discuss details of its implementation, and illustrate it by experimentations in two,
three, and four dimensional spaces.
Object recognition using the shape of objects boundaries and surface reconstruction using slice contours rely
on the identification of the correct and complete boundary information of the segmented objects in the scene.
Geometric deformable models (GDM) using the level sets method provide a very efficient framework for image
segmentation. However, the segmentation results provided by these models are dependent on the contour initialization.
Also, if there are textured objects in the scene, usually the incorrect boundaries are detected. In
most cases where the strategy is to detect the correct boundary of all the objects in the scene, the results of
the segmentation will only provide incomplete and/or inaccurate object's boundaries. In this work, we propose
a new method to detect the correct boundary information of segmented objects, in particular textured objects.
We use the average squared gradient to determine the appropriate initialization positions and by varying the size
of the test regions we create multiple images, that we will call layers, to determine the appropriate boundaries.
Topological image feature extraction is very important for many high level tasks in image processing and for topological analysis and modeling of image data. In this work, we use cubical homology theory to extract topological features as well as their geometric representations in image raw data. Furthermore, we present two algorithms that will allow us to do this extraction task very easily. The first one uses the elementary cubical representation to check the adjacency between cubes in order to localize the connected components in the image data. The second algorithm is about cycle extraction. The first step consists of finding cubical generators of the first homology classes. These generators allow to find rough locations of the holes in the image data. The second method localizes the optimal cycles from the ordinary ones. The optimal cycles represent the boundaries of the holes in the image data. A number of experiments are presented to validate these algorithms on synthetic and real binary images.
In this paper, two new approaches for the topological feature matching problem are proposed. The first one consists of estimating a combinatorial map between block structures (pixels, windows) of given binary images which is then analyzed for topological correspondence using the concept of homology of maps. The second approach establishes a matching by using a similarity measure between two sets of boundary representations of the connected components extracted from two given binary images. The similarity measure is applied on all oriented boundary components of given features. A number of experiments are carried out on both synthetic and real images to validate the two approaches.
In a recent paper, we have introduced a topological descriptor for shape representation based on classical Morse theory. More precisely, given a manifold M and a Morse function f on M, we build an invariant [Morse Shape Descriptor (MSD)] of the manifold from the ranks of relative homology groups of all pairs of lower levels of the function f. While the MSD is a robust invariant with very nice properties, its application requires time consuming computations of homology groups. We present a new and computationally efficient method to capture the essential of the information given by the MSD.
One physical process involved in many computer vision problems is the heat diffusion process. Such Partial differential equations are continuous and have to be discretized by some techniques, mostly mathematical processes like finite differences or finite elements. The continuous domain is subdivided into sub-domains in which there is only one value. The diffusion equation comes from the energy conservation then it is valid on a whole domain. We use the global equation instead of discretize the PDE obtained by a limit process on this global equation. To encode these physical global values over pixels of different dimensions, we use a computational algebraic topology (CAT)-based image model. This model has been proposed by Ziou and Allili and used for the deformation of curves and optical flow. It introduces the image support as a decomposition in terms of points, edges, surfaces, volumes, etc. Images of any dimensions can then be handled. After decomposing the physical principles of the heat transfer into basic laws, we recall the CAT-based image model and use it to encode the basic laws. We then present experimental results for nonlinear graylevel diffusion for denoising, ensuring thin features preservation.
We propose a new image model in which the image support and image quantities are modeled using algebraic topology concepts. The image support is viewed as a collection of chains encoding combination of pixels grouped by dimension and linking different dimensions with the boundary operators. Image quantities are encoded using the notion of cochain which associates values for pixels of given dimension that can be scalar, vector, or tensor depending on the problem that is considered. This allows obtaining algebraic equations directly from the physical laws. The coboundary and codual operators, which are generic operations on cochains allow to formulate the classical differential operators as applied for field functions and differential forms in both global and local forms. This image model makes the association between the image support and the image quantities explicit which results in several advantages: it allows the derivation of efficient algorithms that operate in any dimension and the unification of mathematics and physics to solve classical problems in image processing and computer vision. We show the effectiveness of this model by considering the isotropic diffusion.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.