________________________________________________________________________________ Geoinformatics CTU FCE 2011 125 A SEMIAUTOMATIC LARGE-SCALE DETECTION OF SIMPLE GEOMETRIC PRIMITIVES FOR DETECTING STRUCTURAL DEFECTS FROM RANGE-BASED INFORMATION R.MARTÍNEZ1, F.J. DELGADO1, A. HURTADO2, J. MARTÍNEZ3 and J. FINAT4 1: MoBiVAP R&D Group, Scientific Park, University of Valladolid, 47011 Valladolid, Spain, {ruben.martinez.garcia, franciscojavier.delgado}@uva.es 2: MetaEmotion, Scientific Park, R&D Building, 47011 Valladolid, Spain, ahurtado@metaemotion.es 3: Lab of Architectural Photogrammetry, ETS Arquitectura, University of Valladolid, 47014 Valladolid, lfa@ega.uva.es 4: Dept. of Algebra and Geometry, ETS Ingeniería Informática, University of Valladolid, 47011 Valladolid, jfinat@agt.uva.es Keywords: Architectural surveying, semi-automatic recognition, defects detection, intervention assessment. Abstract: Buildings in Cultural Heritage environments exhibit some common structural defects in elements which can be recognized by their differences with respect to the ideal geometric model. The global approach consists of detecting misalignments between elements corresponding to sections perpendicular to an axis, e.g. The local approach consists of detecting lack of verticality or meaningful differences (facades or internal walls) in curved elements with typical components (apses or vaults, e.g.) appearing in indoor environments. Geometric aspects concern to the basic model which supports successive layers corresponding to materials analysis and mechanical structural behaviour. A common strategy for detecting simple shapes consists of constructing maps of normal which can be extracted by an appropriate sampling of unit normal vectors linked to a points cloud. The most difficult issue concerns to the sampling process. A profusion of decorative details or even the small variations corresponding to small columns which are prolonging the nerves of vaults generate a dispersion of data which can be solved in a manual way by removing not- relevant zones for structural analysis. This method can be appropriate for small churches with a low number of vaults, but it appears as tedious when we are trying to analyse a large cathedral or an urban district. To tackle this problem different strategies for sampling information are designed, where some of them involving geometric aspects have been implemented. We illustrate our approach with several examples concerning to outdoor urban districts and indoor structural elements which display different kinds of pathologies. 1. INTRODUCTION There exists a large diversity of problems in Cultural Heritage buildings which justify their maintenance or rehabilitation. They concern to unexpected behaviour of structural elements related with different kinds of mechanical efforts such as compression, traction and torsion between vertical elements, and material deterioration. The heterogeneity inside of walls, humidity or deterioration in materials can generate structural defects, but they can be detected by direct visual inspection or, alternately, by using acoustic devices for identifying irregular or heterogeneous internal composition of walls. In a similar way another affections can be identified such as geological issues (landslides, earthquakes, e.g.), fluencies or even dynamical actions (forces and moments arising from vibrations, e.g.). All of them are meaningful and involve the whole building structure but this work is restricted to quasi-static mechanical efforts, while an integral restoration must have into account the existing materials. Three-dimensional modelling is crucial for supporting all information concerning the building. In our case, a general 3D representation is created from range data which is captured by means of different kind of laser scan devices and matched with standard software tools. Alternately, 3D models can be generated from a collection of images with a good performance and less cost. A first goal concerning to Cultural Heritage Documentation is to detect any kind of displacements or deformations on the fabric w.r.t. the expected shape, without intending to explain their causes from mechanical or materials composition. A second goal concerns to the insertion of such pathologies inside an Information System which is overlaid to a 3D model of the whole building. A third goal would be focused towards the development of a Management System in charge of monitoring and assessing possible interventions focused to prevent failures or possible crashes. An intelligent agent in ________________________________________________________________________________ Geoinformatics CTU FCE 2011 126 charge of assisting Management would be on the last step of the system for supporting experts in the take of decisions. We only focus in the Documentation and Information System which are based on the common reference given by the 3D model generated from image and range information. The geometric inputs given by a dense point cloud with XYZ coordinates allow superimposing different kinds of geometric primitives such as planes, spheres, cylinders, cones, torus or wired structures. The semi-automatic identification of structural elements (columns, walls, vaults, e.g.) is performed from an interactive application which allows clipping and evaluation w.r.t. ideal shapes. The ideal character of primitives is very useful for a global understanding of the static behaviour of the whole building, but it is necessary to complement it with an analysis or evaluation of the current fabric status. This approach is related to traditional reverse engineering or surface compression methods [1] which propose clustering techniques for automatic surface extraction without measuring the distance w.r.t. ideal shapes. Due to the lack of information of occluded parts and the irregular distribution of captured data, different densities can be incompatible with traditional tools for estimating the current state of the building (based in Finite Element Method). It is necessary to work at different levels of detail (LoD) and to perform different kinds of sampling [2]. We have developed a software tool allowing the automatic extraction of meaningful elements depending on several importance criteria. Our approach for automatic sampling is based on RANSAC methodologies (Random Sample Consensus) [3] for generating and extracting valid samples for further propagating and validating hypotheses. The extension includes aspects involving IMPSAC (Importance Sampling Consensus) [4] and PROSAC (Progressive Sample Consensus) strategies [5]. IMPSAC is a natural extension of RANSAC approach which is well-known in Computer Vision [6, 7]. In this work we have developed an IMPSAC approach applied to geometry, where importance functions for selecting samples are linked to geometric properties (depth for points, relative orientation for triangles) and radiometric parameters (homogeneous colour distributions for materials). PROSAC introduces more advanced strategies for making compatible the information to different LoD for curved elements. Indeed, even after a manual selection of critical zones, the presence of columns or nerves in vaults gives a lot of outliers. Hence, a good selection of samples in a low-resolution level improves the behaviour of incidence properties of the normal vectors used for measuring model similarity. The rest of the paper is structured as follows. Section 2 introduces the traditional approach for structural analysis and a classification of the different types of structural defects. Section 3 explains how to achieve the adjustment of range data to a geometric primitive represented only by a parameterized distribution of its perfect shape. Section 4 extends the previous method for achieving a smart sampling of the points cloud, trying to get a density of points directly proportional to the complexity of the represented object shape. Finally, Section 5 concludes the paper and gives some clues for future improvements. 2. COMMON FRAMEWORK FOR STRUCTURAL ANALYSIS A global 3D geometric model of Cultural Heritage building can be obtained by merging dense clouds of points arising from laser scan devices taken from different location. UVACAD [8] is a specific software solution for merging range and radiometric information from different sources. Dense information is needed for visualization but it is not useful for a structural computation viewpoint. Since structural analysis uses a sharp simplification based in mechanisms of bars and joints, it is necessary to simplify the geometry in a collection of lines associated to longitudinal and transversal sections. Indeed, structural aspects are usually computed in terms of Finite Element Methods (FEM), whereas materials analysis requires a large set of techniques, using at most five thousand control points and bars connecting them. Despite of this fact, the bad conservation state makes sometimes very difficult to implement an effective intervention even when structural defects are obvious. Figure 1: 1) Lack of verticality in walls of Chartres of Aniago (Valladolid, Spain). 2) Dangerous vaults in Aniago. 3) External walls in a Spanish Castle (Trigueros del Valle, Valladolid) ________________________________________________________________________________ Geoinformatics CTU FCE 2011 127 We shall focus on geometric properties involving global aspects, by forgetting decorative or non-functional elements which have a very high value from the Cultural Heritage viewpoint. From the structural element viewpoint, there are some important issues concerning to identification and evaluation of parallelism and perpendicularity constraints in walls or aligned elements. For example, in [9] the superposition of clipped contours allows to identify misali gnments and irregularities in the distribution of efforts very close to the maximal tensions supported by the building. However, this paper will be focused on detecting meaningful elements for Structural Analysis in the fabrics. Multiresolution models are necessary to patch together local factors and global behaviour of the whole building. Synergistic combinations of both explain the persistence of fabrics, and inversely the local damages in some components would explain some global crash phenomena. This interrelation between local and global aspects is transversal to the above described modelling tools arising from mathematical, physical and mechanical (mpm, in the successive) aspects which provide models and technologies to be applied. Basic approaches for getting multiresolution models by sampling are based on blind sampling, i.e. decimation techniques. It removes important data relative to joints, fissures or cracks whose detection and analysis are crucial to detect structural problems and avoid a generalized crash. Hence, it is necessary to develop smart strategies for sampling which include different kinds of mpm properties and characteristics: a) Geometric modelling involves possible irregular distribution of components depending on the distance, the relative orientation and the reflectance capability of scanned materials; the last one can be corrected by superimposing high resolution views, but the other ones require automatic procedures that apply inversely proportional weight to the far or skew information w.r.t. the nearest of frontal objects with a higher density in the point cloud. b) Physical-chemical analysis concerns to different properties of materials (related to internal composition, density, porosity, absorption or thermal parameters, e.g.) with a different behaviour depending on environmental conditions. c) Mechanical properties involve different kinds of quasi-static efforts (compression, traction, torsion, e.g.), dynamical aspects (arising from vibrations or additional tensions, e.g.), the answer of the fabrics to such efforts (involving different ways of measuring elasticity, e.g.) and irregularities in the distribution of materials (masonry versus stone in walls, e.g.). The integration of these aspects requires specific experiments for evaluating structural and materials components. Furthermore, their in-situ evaluation requires a visual inspection of the state of joints (including materials decay, unsteady states) or bending effects in the elements which are supporting stairs, vaults or different kinds of roofs and/or internal coverings. 3. FITTING GEOMETRIC PRIMITIVES TO REAL DATA The traditional representations in architecture are based on drawing polylines using Computer Aided Design (CAD) software. Here, 3D points can be grouped in piecewise linear (PL) models linked to triangulations in which the detection of discontinuities up to a threshold of normal unit vectors allows edge detection. For instance, the intersection of dominant planes gives edges which very often are hidden by decorative elements. In projective geometry, sections and projections are the main inputs for a structural analysis based on 1D elements; so, deviations w.r.t. parallelism or perpendicularity constraints can be detected in a semi-automatic way. However, this approach does not solve troubles such as the detection of deviations (w.r.t. parallelism or perpendicularity) or torsion effects in superficial elements, which are not visible in planar representations. This problem requires the fitting of volumetric primitives to 3D data. Figure 2: Polylines for arcs and profiles are manually drawn over CAD files arising from points clouds. ________________________________________________________________________________ Geoinformatics CTU FCE 2011 128 The fitting of geometric primitives to a points cloud requires visual inspection to identify which kind of geometric primitive is the most appropriate: dominant planes for façades, cylinders for most columns and spheres or cylinders for vaults nerves or columns. The automation requires a volumetric segmentation able of identifying geometric primitives and fine details following a coarse-to-fine strategy. Coarse analysis corresponds to the detection of simple volumetric primitives (dominant planes, cylinders, e.g.) which are grouped in architectural objects (towers, urban blocks) according to order and adjacency constraints as in [10]. Hence, a volumetric segmentation adapted to the architectural object and its environment is obtained. Figure 3: Lack of verticality and torsional buckling of walls is one of the most common defects which can be evaluated by computing the difference with respect to ideal geometric primitives. We have developed algorithms for volumetric primitive fitting, and we are working on the automatic detection and maximal prolongation of thin 3D polylines. From the structural viewpoint both types of data are necessary. Indeed, in correspondence with joints, bars and walls, zero-, one- and two-dimensional elements must be treated in a different way according to their structural role. Deterioration at joints is transmitted to columns and nerves which must be surve yed too. The lack of symmetry in the distribution of geometric elements can generate structural defects in the fabric. For example, sometimes a wall at one side plays the same role as a collection of columns on the parallel side, with a quite different distribution of efforts. The most difficult issues concern to the behaviour of 2D elements relative to walls and vaults. The usual strategy for the adjustment consists of generating triangular meshes from points cloud and evaluating the map of unit normal vectors which plays the role of dual representation of the geometric object [11]. The most common problem for walls is the lack of verticality or bending effects, especially common in heterogeneous walls. In this case, a dense points cloud allows to compare the resulting triangulation w.r.t. an ideal vertical plane (perpendicular to ground), and to evaluate differences w.r.t. a defined threshold. Figure 4: 1) Planar segmentation for detecting plane primitives in a house suspicious of structural problems. 2) Another view of the same house showing the lack of perpendicularity at the main façade. ________________________________________________________________________________ Geoinformatics CTU FCE 2011 129 Curved vaults display some additional troubles. Deviations must be evaluated w.r.t incidence conditions for normal vectors. The affixes of the unit normal vectors can be represented as points of a sphere of unit radius. The concentration of affixes of normal vectors in the Gauss sphere around a fixed value reveals the existence of a spherical piece, whereas the concentration around a meridian is equivalent to the existence of a cylindrical piece. For a ribbed vault (intersection of two cylinders), the affixes of normal unit vectors would be located along two meridians in the Gauss sphere. Obviously, more complicated vaults can be geometrically interpreted as ruled or as translation surfaces (of a line in regard another line, e.g.) which are necessary for slabs construction. However, we shall reduce to the most common cases linked to ordinary vaults which can be found in Romanesque and Gothic styles, where we have several meaningful examples. Figure 5: Map of “almost-normal” unit vectors fitted to a sphere (1) and cylinder (2). Normal directions of sphere pass centre and normal directions of cylinder cut out the axis. Due to the discrete approach performed by a superimposed triangulation shown in figure 5 (noise is irrelevant and regularly distributed), accuracy cannot be expected in intersection properties, but only a concentration of intersections around the representation in the Gauss sphere. Two relevant remarks for structural analysis are the following ones: a) Bars of the structure (columns or vaults nerves) must be treated independently to avoid outliers in triangles connecting points of vaults with points of the other structural elements (columns and vault nerves); currently this task is manually performed by cutting out the meaningful region. b) After clipping, a treatment of surfaces corresponding to vaults is performed to LoD: coarsest for detecting defects in global shape and finest for measuring local deviations w.r.t. the ideal model. Figure 6: Low-resolution models provide a coarse approach to the original surface with the corresponding triangulations which simplifies the detection and suppression of outliers for shape estimation. Outliers are points whose difference w.r.t. "expected property" (model hypotheses to validate) is larger than a threshold. In a first stage of sampling, outliers cannot be removed according to the expected distribution. Contrarily, an important issue is to identify if the observed deviations are due to spurious facts (including noisy information) or they arise from true structural problems; they must be deleted after inspection. ________________________________________________________________________________ Geoinformatics CTU FCE 2011 130 Figure 7: 1) Normal vectors of triangles for a low-resolution sample of a spherical vault give the concentration of their intersections around a point at the centre of a sphere. 2) Two consecutive slices of a cylindrical element from a low-resolution sample of a column determine a slab. The intersection of normal vectors gives points which would lie ideally on the cylinder axis. Meaningful deviations of the line connecting them are reported 5. ADAPTATIVE SMART SAMPLIG WITH IMPORTANCE FUNCTIONS Before validating and propagating hypotheses, it is necessary to design a smart procedure to initialize the process, select appropriate thresholds and identify the samples size. Further traditional suppression of outliers, this implies a careful analysis of sampling procedures and an evaluation of the convergence rate. In this section we sketch a general strategy for smart sampling based on importance functions and progressive sampling. Traditional blind sampling follows random criteria. Hence, it ignores irregularities in distribution which can be due to the distance, relative orientation or materials reflectance, e.g. This sampling is highly efficient but it does not have into account neither irregularities in distribution nor information about proximity conditions in triangulation, such those corresponding to nerves or columns in vaults. Our strategy is performed in two steps: 1) Progressive Sampling Consensus, which selects the minimal number of points for hypotheses generation; 2) Importance Functions, which correct irregularities and hypotheses validation in robust models by propagating conditions in regularly distributed samples. The process starts with a low- resolution sample obtained from successive decimation. Hypotheses generation makes reference not only to the minimal number of points (3 for a plane, 4 for a sphere or a cylinder) in general position, but also to the adjacent ones (the nearest ones to the 3 or 4 selected following nearest neighbours search procedures). This choice is justified because it is necessary to propagate the geometric condition to the nearest points in order to verify adjustment to planarity, spherical and cylindrical conditions. For example, if the process starts with a sample of N points (around 500 for previously segmented curved surfaces, e.g.), valid subsamples must verify the appropriate incidence conditions for normal unit vectors: parallelism to dominant planes or incidence w.r.t. the centre of the ideal sphere or the axis of the ideal cylinder. If the results were appropriate, they propagate to other subsamples which are randomly chosen. For a curved object, the strategy consists of selecting a pivot point P0 and extracting three points from two levels of proximity. Then, properties are identified from the 4 tetrahedral sharing the same pivot point. More precisely, the 3 nearest points to the pivot P 0 are identified and triangulated, the normal unit vectors for each tetrahedral configuration are computed and the intersection of normal directions (up to a threshold) are stored as putative “centre”. This process is repeated for the nearest points of the above three nearest points, sharing and verifying the incidence hypothesis for normal directions supported by at most three adjacent tetrahedral which shares the pivot. A spherical shape must display a concentration of intersections around a point (the putative centre of the sphere) up to a threshold, whereas a cylindrical shape must display the alignment of intersections along a line (the putative axis of the cylinder). If the sample does not display any kind of pattern, it is rejected. Otherwise, it is accepted as a valid sample. Next, the process chooses a second sample and the previous steps are repeated. For previously segmented low-resolution clouds the convergence is very fast (8 or 10 samples). The final output of this process must be an initial estimation of geometric parameters. The second step is focused in achieving a more regular distribution, by correcting irregularities due to different factors. To avoid the suppression of meaningful information in early stages of processing, we propose three criteria involving: a) the absolute distance: higher weight to the farthest points; b) the relative orientation: points lying on skew planes must be weighted with a higher value than those on frontal planes; the relative orientation is computed from the normal unit map linked to the triangulation, and only triangles with a normal vector with angle inferior to 45º w.r.t. view line are considered; c) the light brightness: photonic answer of objects depends on object reflectance so a higher weight to darkest points must be given. This step can be performed by introducing a marginal probability for choice in terms of the difference or the ratio with respect to the local maximum; in this way, we obtain a simple reformulation of inverse proportionality arguments arising from an ideal model. The implementation of any kind of importance functions requires a previous lecture for identifying extreme points, and the generation of auxiliary tables for comparing and updating information. The detection of extreme points (a very low level description of boundary) allows to bound the valid regions, estimate the ________________________________________________________________________________ Geoinformatics CTU FCE 2011 131 global distribution of errors and focus the attention on the distribution of irregularities inside the bounded region. For regularly distributed clouds with Gaussian noise, a simple product of normal distributions would give the global distribution of errors linked to N correspondences. However, this is not the case so it is necessary to give relative non- negative weights wd, wo and wr linked to the distance, orientation and reflectance properties which verify wd + wo + wr = 1. For the collection of valid samples obtained in the first stage, a partial distribution of errors P d, Po and Pr is obtained. This distribution is weighted according to wd, wo and wr with a global distribution of errors wdPd+ woP + wrPr. Usual IMPSAC resolution follows Maximum Likelihood Optimization Criteria (in terms of gradient steepest descent, e.g.); we have adapted this approach to its formulation in the framework of Multicriteria Optimization. However, a more detailed analysis is still needed to avoid false minima. 5. CONCLUSIONS This paper introduces a methodology for the low-level recognition of planar and curved shapes presents in a large part of Cultural Heritage religious buildings which have been constructed between XI and XVI centuries. The methodology includes an adaptive and smart sampling filter of point clouds based on importance functions. The method generates uniformly distributed sampling points by removing or creating points in heterogeneous point clouds resulting from laser scans. A special attention is focused on structural defects involving mechanical efforts for detecting, evaluating and representing their influence on the whole fabric of the building. Experiments over architectural heritage scenarios show the goodness in terms of quality and accuracy of this approach and the valuable support provided to experts at the evaluation of the state of structural elements. Moreover, an adaptive sampling based on importance functions offers several possibilities which motivate further research. For example, it allows the automatic recognition and segmentation of point clouds according not only to geometric primitives, but also with the volumetric density of information. The resulting balanced segmentation in several clouds allows decomposing and distributing tasks according to different characteristics and resolution levels. Also, this helps to store and retrieve the digital artefacts which compose Cultural Heritage buildings. Besides, the established framework allows to include more complex shape estimations based in incidence properties of lines or even to perform curvature analysis for ornamental details. In presence of more complicated map of normal behaviour, it would be convenient to introduce the Willmore energy functional to evaluate the lack of sphericity. Maybe some other adjustments of importance functions are needed. 6. ACKNOWLEDGEMENTS This work has been partially supported by the ADISPA (CICYT) Project with reference BIA2009-14254-C02-01. 6. REFERENCES [1] Schnabel, R. and Wahl, R. and Klein, R. Efficient RANSAC for Point-Cloud Shape Detection. Computer Graphics Forum, 26 (2), 214--226, ACM. [2] Bao-Quan Shi, Jin Liang, Qing Liu. Adaptive simplification of point cloud using k-means clustering. Computer- Aided Design 2011. Accepted Manuscript, ISSN 0010-4485, Elsevier. [3]P.H.S. Torr and C. Davidson, IMPSAC: Synthesis of Importance Sampling and Random Sample Consensus, presented at IEEE Trans. Pattern Anal. Mach. Intell., 2003, pp.354-364. [4] M. A. Fischler and R. C. Bolles. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Comm. of the ACM 24: 381–395. 1981. [5] Bao-Quan Shi, Jin Liang, Qing Liu. Adaptive simplification of point cloud using k-means clustering. Computer- Aided Design 2011. Accepted Manuscript, Available online 9 April 2011, ISSN 0010-4485, Elsevier. [6] D. A. Forsyth and J. Ponce. Computer Vision, a modern approach. Prentice Hall. 2003. [7] R. Hartley and A. Zisserman (2003). Multiple View Geometry in Computer Vision (2nd edition). Cambridge University Press. [8] J.D. Pérez-Moneo, J. Finat, J.J. Fernández, J. I. San José and J. Martínez. UVACAD: A software platform for 3D architectural surveying. XXI CIPA International Symposium: Anticipating the Future of the Cultural. VOL. XXXVI- 5/C53 ISNN 1682-1750. Athens 2007. [9] J. I. San José, J.D. Pérez, J. Finat, J.J. Fernández and J. Martínez. Evaluation of structural damages from 3D Laser Scans. XXI CIPA International Symposium: Anticipating the Future of the Cultural, Athens, 2007 [10] Vosselman, G. and Gorte, B.G.H. and Sithole, G. and Rabbani, T. Recognising structure in laser scanner point clouds. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences 46 (8), 33—38, 2004. [11] Pauly, M. and Gross, M. and Kobbelt, L.P. Efficient simplification of point-sampled surfaces. Visualization, 2002, 163--170, IEEE.