ERCIM News No.44 - January 2001 [contents]

Shape Modelling and Processing: Methods and Applications

by Bianca Falcidieno and Michela Spagnuolo

Shape modelling is both a cognitive and creative process and reasoning about shape is a common way of describing and representing objects in engineering, architecture, medicine, biology, as well as in daily life. Computers have revolutionised the field of shape modelling and opened up new applications, such as Computer Aided Design, Computer Graphics and Computer Vision. The Computer Graphics Group at the Istituto per la Matematica Applicata (IMA-CNR), Genoa, has been working on different aspects of shape-based modelling since 1980. The focus of the research has been on the definition of abstraction tools for deriving high-level descriptions of complex shape models.

A key objective in research on shape-based modelling is to enhance traditional approaches to surface modelling through the definition of representations that are closer to our semantic coding of shape perception. Surface reconstruction techniques can be used to faithfully reproduce complex shape models of existing or virtual objects, which may be thought of as ëdigital mock-upsí to be visualized or analyzed using appropriate software. If, on the one hand, geometric representations are necessary for their approximation function, on the other, it is desirable to communicate with the model using higher-level abstractions, directly connected with specific properties of the shape. For example, when describing a landscape in words we would use terms such as ëmountainousí, or expressions such as ëmany ridges and ravinesí. It is thus clearly not important to communicate the number and the shape of the polygons that compose the digital model and its features, when we use abstraction and/or classification tools to group low-level geometric entities into classes with an associated meaning (conceptual model).

IMA-CNR is working in a number of projects using shape-based reasoning for shape representation and processing. Reverse engineering is a good example of an interesting application field for our approach. Digitizing machines usually perform sampling along predefined directions, sections or profiles, which induce at least a partial ordering in the data set. Shape-based techniques are especially efficient in this context since structural features of the underlying surface can be easily detected by analysing the configuration of points along the sampling directions. Reconstruction can thus be performed a posteriori with respect to the recognition of a rough shape skeleton. This is shown in Figure 1, where the approximating triangulation is fitted to the recognized structural features. IMA has also signed an important research contract with Monolith Ltd, Tokyo, within the framework of a programme funded by private and public Japanese research organizations, for the development of a terrain modelling system based on the topological and semantic structure of natural surfaces.

Our main current research efforts are in the field of computational topology, incorporating abstraction mechanisms in shape modelling. To properly represent shape information, automatic mechanisms must be developed to associate properties (eg meaning) with geometric data within the object description. To do this, properties, or shape features, are identified in order to describe objects effectively, and these properties must be defined formally so that they can be easily associated with a geometric representation.

Understood mathematically, topology is the study of shape properties that do not change under deformation; it provides a sound theoretical basis for the formalisation of a number of problems related to shape and its understanding. For example, we are currently investigating the use of a critical point configuration graph, automatically extracted from a triangulated object model, to define a sketch of the shape suitable for classification and compression purposes (see Figure 2). Another technique studied and developed at IMA concerns the extraction of morphologic features from surfaces represented by cross sections. Cross sections implicitly contain information about features like ridges, ravines, peaks, etc., which can be automatically recognized in order to improve the accuracy of the reconstructed model.

Finally, we are also studying the use of digital object models for the visualization and coding of uncertain information. Different forms of uncertainty and errors can be introduced during the modelling pipeline as data are acquired, modelled and visualized. Different approaches for coding uncertainty have been considered, eg intervals, probability distribution functions and fuzzy numbers. Graphical primitives, such as cubes and spheres, can be used to visualize sets of spatial measures affected by uncertainty, while animation and other visualization techniques such as transparency, can effectively represent the surface at various levels of presumption (see Figure 3).

Links:
http.//www.ima.ge.cnr.it

Please Contact:
Bianca Falcidieno or Michela Spagnuolo – IMA-CNR
Tel: +39 010 64751
E-mail: spagnuolo@ima.ge.cnr.it