Multiresolution modeling provides an abstraction for representing, manipulating, and visualizing large volumes of spatial data at multiple levels of detail and accuracy. In terrain modeling, for instance, a coarse representation can be used to describe less relevant areas of a terrain, while high resolution can be focused on specific parts of interest.
An improved method for adaptively constructing a sequence of triangular meshes from a set of data points is developed. Alternate refinement and decimation steps are repeatedly applied to triangular meshes, incrementally determining a better distribution of the data points, while a specified error tolerance is preserved. Even though not asymptotically optimal or monotonically convergent, it produces approximations that are, experimentally, significantly better than those generated by straightforward greedy insertion algorithms. The method uses a Delaunay triangulation to maintain the topology of the data points, whose vertices lie at a subset of the input data. A local error metric is used to select points to be inserted into the triangulation, based on the maximum vertical error weighted by the standard deviation calculated in a neighborhood of the candidate point. Conversely, a measure of angle between surface normals is used to determine whether a vertex should be removed from the triangulation.
The technique provides an effective compromise between fidelity and time requirements, producing high quality approximations with great flexibility.
One of the most critical research problems encountered in the analysis and visualization of large volumes of data is the development of methods for storing, manipulating, and rendering massive data sets efficiently. Unless data reduction or compression methods are used, extremely large data sets cannot be analyzed or visualized in real time.
Examples of applications involving large volumes of data and complex domain knowledge include remote sensing, satellite imaging, planetary exploration, computer vision, computer-aided design, and medical image analysis.
This project investigates a method for approximating dense range images by integrating triangular meshes and curvature information. First, an adaptive filtering technique is applied to the original range image based on estimations of the surface curvature. This produces a collection of 3D points, which are triangulated to produce an initial mesh. The mesh is then refined through a Delaunay triangulation algorithm until a predefined error tolerance is achieved. New local error measures are used to select points to be inserted into the triangulation. Points tend to scatter in planar areas and to concentrate in high variation areas.
The technique is effective for modeling dense range images, producing approximations with high quality and high data reduction rates. The method can be used as an efficient preprocessing tool for segmentation and recognition of objects in computer vision applications.
This project investigates the use of triangular meshes for approximating digital images, allowing substantial reduction in the cost of storing, manipulating, and rendering surfaces.
As an alternative to regular grid models, in which a set of sampled points representing measures of intensity or elevation are stored at regular intervals, the proposed method constructs a set of nonoverlapping contiguous triangular faces which adaptively approximates the data, while preserving relevant features.
The data points need not lie in any particular pattern and the density may vary over space. There are many advantages associated with triangular meshes. First, data points (such as elevation points in a terrain) are commonly not regularly distributed in space, therefore, the structure of the mesh can be adjusted to reflect the density of the data. Consequently, cells become larger where data are sparse, and smaller where data are dense. Second, relevant features can be incorporated into the model. For instance, vertices in a triangulation can describe nodal terrain features such as peaks, pits or passes, while edges can represent linear terrain features such as break, ridge or channel lines. Third, triangular meshes can be organized into a hierarchical model such that they can represent a terrain in various levels of detail. Finally, triangles are simple geometric objects which can be easily manipulated and rendered.
The approximation of surfaces to scattered data is an important problem encountered in a variety of scientific applications, such as reverse engineering, computer vision, computer graphics, and terrain modeling.
Modeling certain regions as piecewise linear surfaces (C0-continuity surfaces) may require a large number of triangles, whereas a curved surface can provide a more accurate and compact model of the true surface. Smooth surfaces can also produce superior results for rendering purposes, reducing certain perceptual problems such as the appearance of Mach Bands along element boundaries.
This project proposes an automatic method for constructing smooth surfaces defined as a network of curved triangular patches. The method starts with a coarse mesh approximating the surface through triangular elements covering the boundary of the domain, then iteratively adds new points from the data set until a specified error tolerance is achieved. Once this initial triangulation has been generated, smooth surfaces are constructed over the triangular mesh. The resulting surface over the triangular mesh is represented by piecewise polynomial patches possessing C1 continuity.
The extraction of topographic features in digital images is a primary problem encountered in several computer vision systems. Several computer-based recognition tasks such as navigation of autonomous vehicles, planetary exploration, reverse engineering, rapid prototyping, and medical image analysis require the construction of accurate models based on shape descriptors in order to represent surface information in an efficient and consistent way.
This project proposes a method for extracting topographic features from images approximated by triangular meshes. Peaks, pits, passes, ridges, valleys, and flat regions are defined by considering the topological and geometric relationship between the triangular elements. The approach is suitable for image analysis tasks, simplifying object recognition and scene interpretation.
The development of methods for storing, manipulating, and rendering large volumes of data efficiently is a crucial task in several scientific applications, such as medical image analysis, remote sensing, computer vision, and computer-aided design. Unless data reduction or compression methods are used, extremely large data sets cannot be analyzed or visualized in real time. Polygonal surfaces, typically defined by a set of triangles, are one of the most widely used representations for geometric models.
The purpose of this project is to develop a fast algorithm for generating triangle strips from triangulated meshes, providing a compact representation suitable for transmission and rendering of the models. A data structure that allows efficient triangle strip generation is proposed. The method is based on simple heuristics, significantly reducing the number of vertices used to describe the triangulated models. Two heuristics are considerated. The first aims to minimize the number of strips, generating output to a hardware and a graphics library that support swap without resending a vertex. The second heuristic minimizes the number of vertices for models that simulate swap resending a vertex. In the first approach, less strips mean less vertices, while in the second approach there is a tradeoff between few strips and few swaps.
The primary purpose of a classification system is to extract information from the images to allow the discrimination among different objects of interest. The classification process is usually based on gray level intensity, color, shape, or texture. Image classification is of great interest in a variety of applications, for instance, analysis of aerial, satellite, multispectral, medical images, and content-based image retrieval systems.
Texture analysis forms the basis of object recognition and classification in several knowledge domains. Texture can be characterized by local variations of pixel values that repeat in a regular or random pattern on the object or image. It can also be defined as a repetitive arrangement of patterns over a region. Several methods for unsupervised and supervised texture segmentation and classification have been proposed in the literature. However, neither generic methods nor formal approaches exist that are useful for a great variety of images.
This project proposes a segmentation technique based on the combination of measures for pixel feature description and of spatial dependence, modeled by a Markov random field. Such association is obtained through Bayesian formulation and the use of relaxation techniques for maximizing the probability of finding a proper segmentation. Two steps are performed to classify the images. Initially, the method recognizes the homogeneous regions (object interior) in the image. Regions consisting of dissimilar elements (transition between objects) are then properly identified and classified.
The task of partitioning an image into homogeneous regions remains a challenge, especially when the image contains complex textures. Texture is a fundamental feature and plays an important role in several applications involving image analysis, such as medical imaging, remote sensing, industrial inspection, and content-based image retrieval.
Many different techniques have been developed to characterize texture information, including statistical, geometrical, model and spectral based methods. Due to the versatility of the multi-scale transforms, such that important features from images can be characterized more efficiently in spatial-frequency domain, wavelet transforms offer a powerful representation for texture description.
The purpose of this project is to develop image segmentation techniques based on texture using wavelet transforms. Features derived from wavelet coefficients are investigated for texture characterization in several image segmentation problems.
Image classification methods based on textural characteristics have been greatly used in scientific and industrial area, with applications in medicine, microscopy, remote sensing, control of quality, retrieval of information in graphic databases, among others. The characteristic of texture is an important source of information for the process of image analysis and interpretation.
This project proposes a supervised method for classifying remote sensed images based on characteristics of texture. Textural information is described in terms of estatistical features indicating the spatial distribution of color or intensity variation of objects in the images. Such features are calculated using co-occurrence matrices, which are computationally fast and simple.
Several image supervised classification methods based on textural information are evaluated, such as minimum distance classifier, nearest neighbor classifier, maximum likelihood classifier, neural networks. Relevant details on dimensionality reduction, feature extraction and selection that affect the precision and performance of the classifier are also considered.
This project integrates three-dimensional reconstruction methods and rapid prototyping techniques, providing a more efficient design of accurate medical models from tomographic images (scan data) using cost-effective manufacturing techniques. The similarity between the Computed Tomography (CT) and Magnetic Resonance Imaging (MRI) cross-sectional images and the 2D data used in rapid prototyping encourages the integration of these two technologies.
Rapid Prototyping is a technique to rapidly produce 3D objects of complex shapes directly from 3D computer data. These solid models are constructed by the addition of layers of materials, one layer at a time, with each successive layer formed in place and adhered to the stack of previously formed layers. Several manufacturing processes are commercially available today, some of the most commonly used are Fused Deposition Modeling (FDM), Stereolithography (STL), and Selective Laser Sintering (SLS).
The generation of such models provides valuable aid in several medical applications such as surgical planning, implant design, prosthesis fabrication, diagnosis, and treatment planning. Physical models derived from CT or MRI data can offer physicians a direct, intuitive understanding of complex anatomical details which cannot be obtained from imaging on the screen.
A fast reconstruction method is proposed to approximate the external surfaces of three-dimensional objects from a set of 2D cross-sectional tomographic images. Surface representations are obtained by connecting the object boundaries through triangular elements. The triangulation process generates a collection of triangular patches between consecutive pairs of contours, forming a precise approximation to the original object surface. The triangulation algorithm is able to handle cases where there may be several contours in each slice, known as multiple branching problem. Once the surface has been constructed, the resulting data are converted into a file in STL format, which is processed by the prototyping machine to generate the physical models. The developed software works as an interface between the medical imaging system and the prototyping machine.
Connected component identification in images is crucial to several image analysis applications, such as image segmentation, document analysis, automatic inspection, and medical image analysis.
A connected component is a set of pixels in an image which are all connected to each other and share common properties, for instance, intensity values, color or texture. Once all groups have been determined, a unique label is assigned to each identified component.
This project aims to develop efficient methods for identifying connected components in bidimensional and tridimensional binary images. In a 2D image, adjacency relationships can either be based on 4- or 8-connectivity. In a 3D image, adjacency relationships can be based on 6-, 18- or 26-connectivity. Detection of connected components in gray-level and color images is also considered.
The problem of computing visibility information derived from terrain data has a variety of applications. Examples include civil engineering, navigation, landscape architecture, military surveillance, and extraction of topographic features. A common problem is to determine the optimal location of a limited number of resources in order to cover a certain region. Examples of resources include television, radio, and cellular telephone transmitters and receivers, observation towers for monitoring forest fires, radar systems, and other monitoring equipments.
Visibility analysis uses elevation data to determine the regions that are visible (viewshed) from a particular location in the terrain. The choice of the terrain representation in general affects the visibility computation. Tipically, elevation data are represented by means of contour maps, regular grid structures, or triangulated irregular networks. Computing visibility information from terrain data is usually very time-consuming, particularly when the size and density of data increase. Due to the improved capabilities for collecting and distributing data and due to the need for higher accuracy, careful design of models and algorithms is necessary in order to make tasks more computationally tractable.
The purpose of this project is to develop efficient methods for determining visibility information, producing a map containing the number of data points that are visible from each point of the terrain.
Drainage network provides important information on several applications, such as determination of flood areas and erosion, determination of watershed, transportation of sediments, and geomorphology. The calculation of water flow is, in general, dependent on the terrain model used to represent the surface. Typically, terrain data are represented through a regular grid of points, a triangular irregular mesh, or a map of contours. The implementation of a drainage network extraction algorithm is affected by the occurrence of errors in the elevation data, as a result of digitization techniques used to generate the data.
This project aims to develop an automatic method for extracting the drainage network from digital elevation models, allowing a good balance between capacity of processing great volumes of data and time efficiency.