Seeded segmentation methods have gained a lot of attention due to their good performance in fragmenting complex images, easy usability and synergism with graph-based representations. These methods usually rely on sophisticated computational tools whose performance strongly depends on how good the training data reflect a sought image pattern. Moreover, poor adherence to the image contours, lack of unique solution, and high computational cost are other common issues present in most seeded segmentation methods. In this work we introduce Laplacian Coordinates, a quadratic energy minimization framework that tackles the issues above in an effective and mathematically sound manner. The proposed formulation builds upon graph Laplacian operators, quadratic energy functions, and fast minimization schemes to produce highly accurate segmentations. Moreover, the presented energy functions are not prone to local minima, i.e., the solution is guaranteed to be globally optimal, a trait not present in most image segmentation methods. Another key property is that the minimization procedure leads to a constrained sparse linear system of equations, enabling the segmentation of high-resolution images at interactive rates. The effectiveness of Laplacian Coordinates is attested by a comprehensive set of comparisons involving nine state-of-the-art methods and several benchmarks extensively used in the image segmentation literature.

3D surface reconstruction usually begins with a point cloud and aims to build a representation of the object producing that point cloud. There are several algorithms to solve this problem, each with different priors over the point cloud, such as the type of object represented, or the method by which it was obtained. In this work, we focus on an algorithm called Non-Convex Hull (NCH), which reconstructs surfaces through a concept similar to the Medial Axis Transform. A new algorithm called Shrinking Planes is proposed to compute the NCH, based on the Shrinking Ball method with a few improvements. We prove that the new method can approximate surfaces to arbitrarily small error, and evaluate its performance on the surface reconstruction task. The new method maintains the same reconstruction quality as the Naïve Non-Convex Hull method, while achieving a large performance improvement.

We propose a method that helps an unskilled user to carve a physical replica of a 3D CAD model while only using manual cutting tools. The method starts by analyzing the input CAD model and generates a set of carving instructions. Then using a projector, we project the instructions sequentially one at a time to a block of material to guide the user in performing each of them. After each cutting step, we use the projector-camera setup to 3D scan the object after cutting. And automatically align the scanned point cloud to the CAD model, to prepare the position for the next instruction. We demonstrate a complete system to support this operation and show several examples manually carved while using the system.

Several 3D imaging methods based on active illumina- tion, such as silhouette-based 3D reconstruction and struc- tured light 3D scanning with binary patterns, require light sources capable of generating shadows with sharp bound- aries when they are used to illuminate opaque occluders. Supported by empirical evidence suggesting that a low cost Uncollimated Laser Diode (ULD) produces shadows with sharp boundaries not requiring focusing in a wide range of depths, this paper proposes the use of ULDs as light sources in the target applications. Since due to astigmatism the Point Light Source (PLS) is not an accurate mathemati- cal model of light propagation for the ULD, the Two Lines Light Source (TLLS) model is introduced to explain the ob- served behavior of the ULD. This novel geometric model of light propagation is defined by two 3D line segments, rather than a single 3D point, and guarantees that for each illu- minated 3D point there exists a unique ray, which simul- taneously passes through the point and intersects the two line segments. Furthermore, the equation of this ray can be computed in closed form at very low computational cost, and the TLLS model reduces to the PLS model when the two line segments intersect. Finally, the paper introduces a calibration method to estimate the model parameters, and describes the experiments performed to validate the model.

In this article we present the first effective method based on global optimization for the reconstruction of image puzzles comprising rectangle pieces-Puzzle Solving by Quadratic Programming (PSQP). The proposed novel mathematical formulation reduces the problem to the maximization of a constrained quadratic function, which is solved via a gradient ascent approach. The proposed method is deterministic and can deal with arbitrary identical rectangular pieces. We provide experimental results showing its effectiveness when compared to state-of-the-art approaches. Although the method was developed to solve image puzzles, we also show how to apply it to the reconstruction of simulated strip-shredded documents, broadening its applicability.

Human hand motion and shape sensing is an area of high interest in medical communities and for human interaction researchers. Measurement of small hand movements could help professionals to quantize the stage of conditions like Parkinson's Disease (PD) and Essential Tremor (ET). Similar data is also useful for designers of human interaction algorithms to infer information about hand pose and gesture recognition. In this paper we present a structured light sensor capable of measuring hand shape and color at 121 FPS. Our algorithm uses a novel structured light method developed by us, called Chebyshev Phase Shifting (CPS). This method uses a digital projector and a camera to create high-resolution color 3D models from sequences of color images. We show how to encode CPS patterns in three RGB images for a reduced acquisition time, enabling high speed capture. We have built a prototype to measure rapid trembling hands. Our results show our prototype accurately captures fast tremors similar to those of PD patients. Color 3D model sequences recorded at high speed with our sensor will be used to study hand kinematic properties in a future.

Existing algorithms for building layouts from geometric primitives are typically designed to cope with requirements such as orthogonal alignment, overlap removal, optimal area usage, hierarchical organization, among others. However, most techniques are able to tackle just a few of those requirements simultaneously, impairing their use and flexibility. In this work we propose a novel methodology for building layouts from geometric primitives that concurrently addresses a wider range of requirements. Relying on multidimensional projection and mixed integer optimization, our approach arranges geometric objects in the visual space so as to generate well structured layouts that preserve the semantic relation among objects while still making an efficient use of display area. Moreover, scalability is handled through a hierarchical representation scheme combined with navigation tools. A comprehensive set of quantitative comparisons against existing geometry-based layouts and applications on text, image, and video data set visualization prove the effectiveness of our approach.

We introduce Embedded PS, a new robust and accurate phase shifting algorithm for 3D scanning. The method projects only high frequency sinusoidal patterns in order to reduce errors due to global illumination effects, such as subsurface scattering and interreflections. The frequency set for the projected patterns is specially designed so that our algorithm can extract a set of embedded low frequency sinusoidals with simple math. All the signals, patterns high and embedded low frequencies, are used with temporal phase unwrapping to compute absolute phase values in closed-form, without quantization or approximation via LUT, resulting in fast computation. The absolute phases provide correspondences from projector to camera pixels which enable to recover 3D points using optical triangulation. The algorithm estimates multiple absolute phase values per pixel which are combined to reduce measurement noise while preserving fine details. We prove that embedded periodic signals can be recovered from any periodic signal, not just sinusoidal signals, which may result in further improvements for other 3D imaging methods. Several experiments are presented showing that our algorithm produces more robust and accurate 3D scanning results than state-of-the-art methods for challenging surface materials, with an equal or smaller number of projected patterns and at lower computational cost.

Image inpainting is a challenging topic in computer vision that seeks to recover the natural aspect of an image where data has been partially damaged or occluded by undesired objects. A common drawback not addressed by most inpainting methodologies is that the user must manually provide the inpainting mask as input data to the method. Selecting the inpainting mask is tedious, time consuming and it often requires artistic skills to precisely determine the mask. In this work we design a new tool that allows users to easily select the desirable mask. The proposed framework combines the high-adherence on image contours of the Laplacian Coordinates segmentation approach with the efficiency of a recent inpainting technique that unifies anisotropic diffusion, inner product-based filling order mechanism and exemplar-based completion. The user can interact with the object that he/she intends to edit by stroking small parts of the object so as to proceed with the segmentation and inpainting task. Our comparisons show that the proposed framework has good performance in terms of applicability and effectiveness when compared against other existing techniques in the literature.

Various Structured Light (SL) methods are used to capture 3D range images, where a number of binary or continuous light patterns are sequentially projected onto a scene of interest, while a digital camera captures images of the illuminated scene. All existing SL methods require the projector and camera to be hardware or software synchronized, with one image captured per projected pattern. A 3D range image is computed from the captured images. The two synchronization methods have disadvantages, which limit the use of SL methods to niche industrial and low quality consumer applications. Unsynchronized Structured Light (USL) is a novel SL method which does not require synchronization of pattern projection and image capture. The light patterns are projected and the images are captured independently, at constant, but possibly different, frame rates. USL synthesizes new binary images as would be decoded from the images captured by a camera synchronized to the projector, reducing the subsequent computation to standard SL. USL works both with global and rolling shutter cameras. USL enables most burst-mode-capable cameras, such as modern smartphones, tablets, DSLRs, and point-and-shoots, to function as high quality 3D snapshot cameras. Beyond the software, which can run in the devices, a separate SL Flash, able to project the sequence of patterns cyclically, during the acquisition time, is needed to enable the functionality.

Seed-based image segmentation methods have gained much attention lately, mainly due to their good performance in segmenting complex images with little user interaction. Such popularity leveraged the development of many new variations of seed-based image segmentation techniques, which vary greatly regarding mathematical formulation and complexity. Most existing methods in fact rely on complex mathematical formulations that typically do not guarantee unique solution for the segmentation problem while still being prone to be trapped in local minima. In this work we present a novel framework for seed-based image segmentation that is mathematically simple, easy to implement, and guaranteed to produce a unique solution. Moreover, the formulation holds an anisotropic behavior, that is, pixels sharing similar attributes are kept closer to each other while big jumps are naturally imposed on the boundary between image regions, thus ensuring better fitting on object boundaries. We show that the proposed framework outperform state-of-the-art techniques in terms of quantitative quality metrics as well as qualitative visual results.

We present a near real-time algorithm for interactively exploring a collectively captured moment without explicit 3D reconstruction. Our system favors immediacy and local coherency to global consistency. It is common to represent photos as vertices of a weighted graph, where edge weights measure similarity or distance between pairs of photos. We introduce Angled Graphs as a new data structure to organize collections of photos in a way that enables the construction of visually smooth paths. Weighted angled graphs extend weighted graphs with angles and angle weights which penalize turning along paths. As a result, locally straight paths can be computed by specifying a photo and a direction. The weighted angled graphs of photos used in this paper can be regarded as the result of discretizing the Riemannian geometry of the high dimensional manifold of all possible photos. Ultimately, our system enables everyday people to take advantage of each others' perspectives in order to create on-the-spot spatiotemporal visual experiences similar to the popular bullet-time sequence. We believe that this type of application will greatly enhance shared human experiences spanning from events as personal as parents watching their children's football game to highly publicized red carpet galas.

We present a benchmark for the evaluation and comparison of algorithms which reconstruct a surface from point cloud data. Although a substantial amount of effort has been dedicated to the problem of surface reconstruction, a comprehensive means of evaluating this class of algorithms is noticeably absent. We propose a simple pipeline for measuring surface reconstruction algorithms, consisting of three main phases: surface modeling, sampling, and evaluation. We use implicit surfaces for modeling shapes which are capable of representing details of varying size and sharp features. From these implicit surfaces, we produce point clouds by synthetically generating range scans which resemble realistic scan data produced by an optical triangulation scanner. We validate our synthetic sampling scheme by comparing against scan data produced by a commercial optical laser scanner, where we scan a 3D-printed version of the original surface. Last, we perform evaluation by comparing the output reconstructed surface to a dense uniformly distributed sampling of the implicit surface. We decompose our benchmark into two distinct sets of experiments. The first set of experiments measures reconstruction against point clouds of complex shapes sampled under a wide variety of conditions. Although these experiments are quite useful for comparison, they lack a fine-grain analysis. To complement this, the second set of experiments measures specific properties of surface reconstruction, in terms of sampling characteristics and surface features. Together, these experiments depict a detailed examination of the state of surface reconstruction algorithms.

Given a set of high-resolution images of a scene, it is often desirable to predict the scene's appearance from viewpoints not present in the original data for purposes of change detection. When significant 3-D relief is present, a model of the scene geometry is necessary for accurate prediction to determine surface visibility relationships. In the absence of an a priori high-resolution model (such as those provided by LIDAR), scene geometry can be estimated from the imagery itself. These estimates, however, cannot, in general, be exact due to uncertainties and ambiguities present in image data. For this reason, probabilistic scene models and reconstruction algorithms are ideal due to their inherent ability to predict scene appearance while taking into account such uncertainties and ambiguities. Unfortunately, existing data structures used for probabilistic reconstruction do not scale well to large and complex scenes, primarily due to their dependence on large 3-D voxel arrays. The work presented in this paper generalizes previous probabilistic 3-D models in such a way that multiple orders of magnitude savings in storage are possible, making high-resolution change detection of large-scale scenes from high-resolution aerial and satellite imagery possible. Specifically, the inherent dependence on a discrete array of uniformly sized voxels is removed through the derivation of a probabilistic model which represents uncertain geometry as a density field, allowing implementations to efficiently sample the volume in a nonuniform fashion.

Abstract We introduce a new variational formulation for the problem of reconstructing a watertight surface defined by an implicit equation, from a finite set of oriented points; a problem which has attracted a lot of attention for more than two decades. As in the Poisson Surface Reconstruction approach, discretizations of the continuous formulation reduce to the solution of sparse linear systems of equations. But rather than forcing the implicit function to approximate the indicator function of the volume bounded by the implicit surface, in our formulation the implicit function is forced to be a smooth approximation of the signed distance function to the surface. Since an indicator function is discontinuous, its gradient does not exist exactly where it needs to be compared with the normal vector data. The smooth signed distance has approximate unit slope in the neighborhood of the data points. As a result, the normal vector data can be incorporated directly into the energy function without implicit function smoothing. In addition, rather than first extending the oriented points to a vector field within the bounding volume, and then approximating the vector field by a gradient field in the least squares sense, here the vector field is constrained to be the gradient of the implicit function, and a single variational problem is solved directly in one step. The formulation allows for a number of different efficient discretizations, reduces to a finite least squares problem for all linearly parameterized families of functions, and does not require boundary conditions. The resulting algorithms are significantly simpler and easier to implement, and produce results of quality comparable with state‐of‐the‐art algorithms. An efficient implementation based on a primal‐graph octree‐based hybrid finite element‐finite difference discretization, and the Dual Marching Cubes isosurface extraction algorithm, is shown to produce high quality crack‐free adaptive manifold polygon meshes.

We formulate the problem of surface deformations as the integration in the least square sense of a discrete vector-valued 1-forms obtained as the result of applying smooth stretching and rotation fields to the discrete differential of the 0-form defined by the vertex coordinates of a polygon mesh graph. Simple algorithms result from this formulation, which reduces to the solution of sparse linear systems. The method handles large angle rotations in one step and is invariant to rotations, translations, and scaling. We also introduce the integration of 1-forms along spanning trees as a heuristic to speed up the convergence of iterative solvers.

Aerial video registration is traditionally performed using 2-d transforms in the image space. For scenes with large 3-d relief, this approach causes parallax motions which may be detrimental to image processing and vision algorithms further down the pipeline. A novel, automatic, and online video registration system is proposed which renders the scene from a fixed viewpoint, eliminating motion parallax from the registered video. The 3-d scene is represented with a probabilistic voxel model, and camera pose at each frame is estimated using an Extended Kalman Filter and a refinement procedure based on a popular visual servoing technique. 1

Abstract We present a planarity constraint and a novel three‐dimensional (3D) point reconstruction algorithm for a multiview laser range slit scanner. The constraint is based on the fact that all observed points on a projected laser line lie on the same plane of laser light in 3D. The parameters of the plane of laser light linearly parametrize a homography between a pair of images of the laser points. This homography can be recovered from point correspondences derived from epipolar geometry. The use of the planar constraint reduces outliers in the reconstruction and allows for the reconstruction of points seen in only one view. We derive an optimal reconstruction of points subject to the planar constraint and compare the accuracy to the suboptimal approach in prior work. We also construct a catadioptric stereo rig with high quality optical components to remove error due to camera synchronization and non‐uniform laser projection. The reconstruction results are compared to prior work that uses inexpensive optics and two cameras.

We describe a unified representation of occluders in light transport and photography using shield fields: the 4D attenuation function which acts on any light field incident on an occluder. Our key theoretical result is that shield fields can be used to decouple the effects of occluders and incident illumination. We first describe the properties of shield fields in the frequency-domain and briefly analyze the "forward" problem of efficiently computing cast shadows. Afterwards, we apply the shield field signal-processing framework to make several new observations regarding the "inverse" problem of reconstructing 3D occluders from cast shadows -- extending previous work on shape-from-silhouette and visual hull methods. From this analysis we develop the first single-camera, single-shot approach to capture visual hulls without requiring moving or programmable illumination. We analyze several competing camera designs, ultimately leading to the development of a new large-format, mask-based light field camera that exploits optimal tiled-broadband codes for light-efficient shield field capture. We conclude by presenting a detailed experimental analysis of shield field capture and 3D occluder reconstruction.

This paper describes a new median filter algorithm optimized for real-time performance in smart cameras with embedded processors. As in the JPEG and MPEG compression algorithms, each frame of the video stream is first partitioned into a regular array of non-overlapping square blocks. The median value for each block is then computed and compared with corresponding values of neighboring blocks. If the magnitude of the difference does not exceed a threshold, the output value for all the pixels in the block is set to the median value. Otherwise, the output value for each pixel in the block is computed as the median value within a window of the same size centered at this pixel. We describe variations for binary and grayscale images. The algorithm has been implemented and tested in an embedded single-board-computer (SBC) with no hardware acceleration, as a component of a Visual Sensor Network (VSN) system for real-time indoor person detection and tracking. In this system, where the SBCs have the additional overhead of decoding JPEG frames from IP cameras, our new algorithm is 5 to 20 times faster than the traditional algorithms for typical window sizes. We expect further speedups to frame-rate performance on smart cameras with embedded image sensors and reconfigurable hardware.

Figure 1: (a) A 256 × 256 texture map with chart boundaries of the mesh shown in orange. (b) A charted horse model with 97K faces. (c) Close up of the original textured model. (d) 125 iterations of atlas-aware Laplacian smoothing with λ = 0.75. (e) 125 iterations of standard Laplacian smoothing. Notice the boundary artifacts along the seams. 1

Polygon meshes, which are used in most graphics applications, require considerable amounts of storage, even when they only approximate precise shapes with limited accuracy. To support Internet access to 3D models of complex virtual environments or assemblies for electronic shopping, collaborative CAD, multi-player video games, and scientific visualization, representations of 3D shapes must be compressed by several orders of magnitude. Furthermore, several closely related methods have been proposed in recent years to smooth, de-noise, edit, compress, transmit, and animate very large polygon meshes, based on topological and combinatorial methods, signal processing techniques, constrained energy minimization, and the solution of diffusion differential equations. This is an overview of some of my recent results in this area: linear anisotropic mesh filtering, bi-level isosurface compression, space-optimized texture maps, and volume warping for adaptive isosurface extraction.

In this paper we introduce a new and simple algorithm to compress isosurface data. This is the data extracted by isosurface algorithms from scalar functions defined on volume grids, and used to generate polygon meshes or alternative representations. In this algorithm the mesh connectivity and a substantial proportion of the geometric information are encoded to a fraction of a bit per marching cubes vertex with a context based arithmetic coder closely related to the JBIG binary image compression standard. The remaining optional geometric information that specifies the location of each marching cubes vertex more precisely along its supporting intersecting grid edge, is efficiently encoded in scan-order with the same mechanism. Vertex normals can optionally be computed as normalized gradient vectors by the encoder and included in the bitstream after quantization and entropy encoding, or computed by the decoder in a postprocessing smoothing step. These choices are determined by trade-offs associated with an in-core vs. out-of-core decoder structure. The main features of our algorithm are its extreme simplicity and high compression rates.

Polyhedral models, which are used in most graphics applications, require considerable amounts of storage, even when they only approximate precise shapes with limited accuracy. To support internet access to 30 models of complex virtual environments or assemblies for electronic shopping, collaborative CAD, multi-player video games, scientific visualization, representations of 30 shapes must be compressed by several orders of magnitude. In this talk I will describe the state of the art in schemes for lossy and loss-less compression of triangle and polygonal meshes, including progressive approaches. In additions to single-resolution compression schemes for triangle and polygonal meshes, which result in compressed formats of less than a byte per triangle, multiresolution progressive rejinement approaches have advanced to the point of challenging the best single resolution schemes in compression eficiency. Along with surface simplijication or decimation methods, these approaches, which change the surj5ace topology while approximating the geometry, can be regarded as lossy compression schemes. Finaly, I will describe the status of standardization efforts and open problems.

The dual of a 2-manifold polygonal mesh without boundary is commonly defined as another mesh with the same topology (genus) but different connectivity (vertex-face incidence), in which faces and vertices occupy complementary locations and the position of each dual vertex is computed as the center of mass (barycenter or centroid) of the vertices that support the corresponding face. This barycenter dual mesh operator is connectivity idempotent but not geometrically idempotent for any choice of vertex positions, other than constants. In this paper we construct a new resampling dual mesh operator that is geometrically idempotent for the largest possible linear subspace of vertex positions. We look at the primal and dual mesh connectivities as irregular sampling spaces, and at the rules to determine dual vertex positions as the result of a resampling process that minimizes signal loss. Our formulation, motivated by the duality of Platonic solids, requires the solution of a simple least-squares problem. We introduce a simple and efficient iterative algorithm closely related to Laplacian smoothing, and with the same computational cost. We also characterize the configurations of vertex positions where signal loss does and does not occur during dual mesh resampling, and the asymptotic behavior of iterative dual mesh resampling in the general case. Finally, we describe the close relation existing with discrete fairing and variational subdivision, and define a new primal-dual interpolatory recursive subdivision scheme.

Many real-world polygonal surfaces contain topological singularities that represent a challenge for processes such as simplification, compression, and smoothing. We present an algorithm that removes singularities from nonmanifold sets of polygons to create manifold (optionally oriented) polygonal surfaces. We identify singular vertices and edges, multiply singular vertices, and cut through singular edges. In an optional stitching operation, we maintain the surface as a manifold while joining boundary edges. We present two different edge stitching strategies, called pinching and snapping. Our algorithm manipulates the surface topology and ignores physical coordinates. Except for the optional stitching, the algorithm has a linear complexity and requires no floating point operations. In addition to introducing new algorithms, we expose the complexity (and pitfalls) associated with stitching. Finally, several real-world examples are studied.

We present a method for compressing non-manifold polygonal meshes, i.e. polygonal meshes with singularities, which occur very frequently in the real-world. Most efficient polygonal compression methods currently available are restricted to a manifold mesh: they require a conversion process, and fail to retrieve the original model connectivity after decompression. The present method works by converting the original model to a manifold model, encoding the manifold model using an existing mesh compression technique, and clustering, or stitching together during the decompression process vertices that were duplicated earlier to faithfully recover the original connectivity. This paper focuses on efficiently encoding and decoding the stitching information. By separating connectivity from geometry and properties, the method avoids encoding vertices (and properties bound to vertices) multiple times; thus a reduction of the size of the bit-stream of about 10% is obtained compared with encoding the model as a manifold.

The Ball-Pivoting Algorithm (BPA) computes a triangle mesh interpolating a given point cloud. Typically, the points are surface samples acquired with multiple range scans of an object. The principle of the BPA is very simple: Three points form a triangle if a ball of a user-specified radius p touches them without containing any other point. Starting with a seed triangle, the ball pivots around an edge (i.e., it revolves around the edge while keeping in contact with the edge's endpoints) until it touches another point, forming another triangle. The process continues until all reachable edges have been tried, and then starts from another seed triangle, until all points have been considered. The process can then be repeated with a ball of larger radius to handle uneven sampling densities. We applied the BPA to datasets of millions of points representing actual scans of complex 3D objects. The relatively small amount of memory required by the BPA, its time efficiency, and the quality of the results obtained compare favorably with existing techniques.

In this paper we introduce the Progressive Forest Split (PFS) representation, a new adaptive refinement scheme for storing and transmitting manifold triangular meshes in progressive and highly compressed form. As in the Progressive Mesh (PM) method of Hoppe, a triangular mesh is represented as a low resolution polygonal model followed by a sequence of refinement operations, each one specifying how to add triangles and vertices to the previous level of detail to obtain a new level. The PFS format shares with PM and other refinement schemes the ability to smoothly interpolate between consecutive levels of detail. However, it achieves much higher compression ratios than PM by using a more complex refinement operation which can, at the expense of reduced granularity, be encoded more efficiently. A forest split operation doubling the number n of triangles of a mesh requires a maximum of approximately 3:5n bits to represent the connectivity changes, as opposed to approximately #5 + log 2 #n## n bits in PM. We describe

Many real world polygonal surfaces contain topological singularities that represent a challenge for processes such as simplification, compression, smoothing, etc. We present an algorithm for removing such singularities, thus converting non manifold sets of polygons to manifold polygonal surfaces (orientable if necessary). We identify singular vertices and edges, multiply singular vertices, and cut through singular edges. In an optional stitching phase, we join surface boundary edges that were cut, or whose endpoints are sufficiently close, while guaranteeing that the surface is a manifold. We study two different stitching strategies called "edge pinching" and "edge snapping"; when snapping, special care is required to avoid re-creating singularities. The algorithm manipulates the polygon vertex indices (surface topology) and essentially ignores vertex coordinates (surface geometry). Except for the optional stitching, the algorithm has a linear complexity in the number of vertices edges and faces, and require no floating point operation.

The virtual-reality modeling language (VRML) is rapidly becoming the standard file format for transmitting three-dimensional (3-D) virtual worlds across the Internet. Static and dynamic descriptions of 3-D objects, multimedia content, and a variety of hyperlinks can be represented in VRML files. Both VRML browsers and authoring tools for the creations of VRML files are widely available for several different platforms. In this paper, we describe the topologically assisted geometric compression technology included in our proposal for the VRML compressed binary format. This technology produces significant reduction of file sizes and, subsequently, of the time required for transmission of such filed across the Internet. Compression ratios of 50:1 or more are achieved for large models. The proposal also includes a binary encoding to create compact, rapidly parsable binary VRML files. The proposal is currently being evaluated by the Compressed Binary Format Working Group of the VRML consortium as a possible extension of the VRML standard. In the topologically assisted compression scheme, a polyhedron is represented using two interlocking trees: a spanning tree of vertices and a spanning tree of triangles. The connectivity information represented in other compact schemes, such as triangular strips and generalized triangular meshes, can be directly derived from this representation. Connectivity information for large models is compressed with storage requirements approaching one bit per triangle. A variable-length, optionally lossy compression technique is used for vertex positions, normals, colors, and texture coordinates. The format supports all VRML property binding conventions.

The abundance and importance of complex 3-D data bases in major industry segments, the affordability of interactive 3-D rendering for office and consumer use, and the exploitation of the Internet to distribute and share 3-D data have intensified the need for an effective 3-D geometric compression technique that would significantly reduce the time required to transmit 3-D models over digital communication channels, and the amount of memory or disk space required to store the models. Because the prevalent representation of 3-D models for graphics purposes is polyhedral and because polyhedral models are in general triangulated for rendering, this article introduces a new compressed representation for complex triangulated models and simple, yet efficient, compression and decompression algorithms. In this scheme, vertex positions are quantized within the desired accuracy, a vertex spanning tree is used to predict the position of each vertex from 2,3, or 4 of its ancestors in the tree, and the correction vectors are entropy encoded. Properties, such as normals, colors, and texture coordinates, are compressed in a similar manner. The connectivity is encoded with no loss of information to an average of less than two bits per triangle. The vertex spanning tree and a small set of jump edges are used to split the model into a simple polygon. A triangle spanning tree and a sequence of marching bits are used to encode the triangulation of the polygon. Our approach improves on Michael Deering's pioneering results by exploiting the geometric coherence of several ancestors in the vertex spanning tree, preserving the connectivity with no loss of information, avoiding vertex repetitions, and using about three fewer bits for the connectivity. However, since decompression requires random access to all vertices, this method must be modified for hardware rendering with limited onboard memory. Finally, we demonstrate implementation results for a variety of VRML models with up to two orders of magnitude compression.

The authors present an automatic product 1D system ("VeggieVision"), intended to ease the produce checkout process. The system consists of an integrated scale and imaging system with a user-friendly interface. When a produce item is placed on the scale, an image is taken. A variety of features, color, texture (shape, density), are then extracted. These features are compared to stored "signatures" which were obtained by prior system training (either on-line or off-line). Depending on the certainty of the classification, the final decision is made either by the system or by a human from a number of choices selected by the system. Over 95% of the time, the correct produce classification is in the top four choices.

Parametric deformable models have been extensively and very successfully used for reconstructing free-form curves and surfaces, and for tracking nonrigid deformations, but they require previous knowledge of the topological type of the data, and good initial curve or surface estimates. With deformable models, it is also computationally expensive to check for and to prevent self-intersections while tracking deformations. The implicit simplicial models that we introduce in this paper are implicit curves and surfaces defined by piecewise linear functions. This representation allows for local deformations, control of the topological type, and prevention of self-intersections during deformations. As a first application, we also describe an algorithm for 2D curve reconstruction from unorganized sets of data points. The topology, the number of connected components, and the geometry of the data are all estimated using an adaptive space subdivision approach. The main four components of the algorithm are topology estimation, curve fitting, adaptive space subdivision, and mesh relaxation.

For a number of computational purposes, including visualization of scientific data and registration of multimodal medical data, smooth curves must be approximated by polygonal curves, and surfaces by polyhedral surfaces. An inherent problem of these approximation algorithms is that the resulting curves and surfaces appear faceted. Boundary-following and iso-surface construction algorithms are typical examples. To reduce the apparent faceting, smoothing methods are used. In this paper, we introduce a new method for smoothing piecewise linear shapes of arbitrary dimension and topology. This new method is in fact a linear low-pass filter that removes high-curvature variations, and does not produce shrinkage. Its computational complexity is linear in the number of edges or faces of the shape, and the required storage is linear in the number of vertices.>

Estimating principal curvatures and principal directions of a surface from a polyhedral approximation with a large number of small faces, such as those produced by iso-surface construction algorithms, has become a basic step in many computer vision algorithms, particularly in those targeted at medical applications. We describe a method to estimate the tensor of curvature of a surface at the vertices of a polyhedral approximation. Principal curvatures and principal directions are obtained by computing in closed form the eigenvalues and eigenvectors of certain 3/spl times/3 symmetric matrices defined by integral formulas, and closely related to the matrix representation of the tensor of curvature. The resulting algorithm is linear, both in time and in space, as a function of the number of vertices and faces of the polyhedral surface.>

In this paper we describe a new tool for interactive free-form fair surface design. By generalizing classical discrete Fourier analysis to two-dimensional discrete surface signals -- functions defined on polyhedral surfaces of arbitrary topology --, we reduce the problem of surface smoothing, or fairing, to low-pass filtering. We describe a very simple surface signal low-pass filter algorithm that applies to surfaces of arbitrary topology. As opposed to other existing optimization-based fairing methods, which are computationally more expensive, this is a linear time and space complexity algorithm. With this algorithm, fairing very large surfaces, such as those obtained from volumetric medical data, becomes affordable. By combining this algorithm with surface subdivision methods we obtain a very effective fair surface design technique. We then extend the analysis, and modify the algorithm accordingly, to accommodate different types of constraints. Some constraints can be imposed without any modification of the algorithm, while others require the solution of a small associated linear system of equations. In particular, vertex location constraints, vertex normal constraints, and surface normal discontinuities across curves embedded in the surface, can be imposed with this technique. CR Categories and Subject Descriptors: I.3.3 [Computer Graphics]: Picture/image generation - display algorithms; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling - curve, surface, solid, and object representations;J.6[Com- puter Applications]: Computer-Aided Engineering - computeraided design General Terms: Algorithms, Graphics. 1

Interest in algebraic curves and surfaces of high degree as geometric models or shape descriptors for different model-based computer vision tasks has increased in recent years, and although their properties make them a natural choice for object recognition and positioning applications, algebraic curve and surface fitting algorithms often suffer from instability problems. One of the main reasons for these problems is that, while the data sets are always bounded, the resulting algebraic curves or surfaces are, in most cases, unbounded. In this paper, the authors propose to constrain the polynomials to a family with bounded zero sets, and use only members of this family in the fitting process. For every even number d the authors introduce a new parameterized family of polynomials of degree d whose level sets are always bounded, in particular, its zero sets. This family has the same number of degrees of freedom as a general polynomial of the same degree. Three methods for fitting members of this polynomial family to measured data points are introduced. Experimental results of fitting curves to sets of points in R/sup 2/ and surfaces to sets of points in R/sup 3/ are presented.>

In this article we present new algorithms for rasterizing implicit curves, i.e., curves represented as level sets of functions of two variables. Considering the pixels as square regions of the plane, a “correct” algorithm should paint those pixels whose centers lie at less than half the desired line width from the curve. A straightforward implementation, scanning the display array evaluating the Euclidean distance from the center of each pixel to the curve, is impractical, and a standard quad-tree-like recursive subdivision scheme is used instead. Then we attack the problem of testing whether or not the Euclidean distance from a point to an implicit curve is less than a given threshold. For the most general case, when the implicit function is only required to have continuous first-order derivatives, we show how to reformulate the test as an unconstrained global root-finding problem in a circular domain. For implicit functions with continuous derivatives up to orderkwe introduce an approximate distance of orderk. The approximate distance of orderkfrom a point to an implicit curve is asymptotically equivalent to the Euclidean distance and provides a sufficient test for a polynomial of degreeknot to have roots inside a circle. This is the main contribution of the article. By replacing the Euclidean distance test with one of these approximate distance tests, we obtain a practical rendering algorithm, proven to be correct for algebraic curves. To speed up the computation we also introduce heuristics, which used in conjunction with low-order approximate distances almost always produce equivalent results. The behavior of the algorithms is analyzed, both near regular and singular points, and several possible extensions and applications are discussed.

The author describes a new method to improve the algebraic surface fitting process by better approximating the Euclidean distance from a point to the surface. In the past they have used a simple first order approximation of the Euclidean distance from a point to an implicit curve or surface which yielded good results in the case of unconstrained algebraic curves or surfaces, and reasonable results in the case of bounded algebraic curves and surfaces. However, experiments with the exact Euclidean distance have shown the limitations of this simple approximation. Here, a more complex, and better, approximation to the Euclidean distance is introduced from a point to an alegbraic curve or surface. It is shown that this new approximate distance produces results of the same quality as those based on the exact Euclidean distance, and much better than those obtained using other available methods.>

An approach to fitting of implicit algebraic curves and surfaces to point data is introduced. Two families of polynomials with bounded zero sets are presented. Members of these families have the same number of degrees of freedom as general polynomials of the same degree. Methods for fitting members of these families of polynomials to measured data points are described. Experimental results for sets of points in R/sup 2/ and R/sup 3/ for curves and surfaces, respectively, are presented.>

Describes techniques for stabilizing the implicit function fitting process. The key drawback of implicit function fitting methods described in literature thus far has been the stability with respect to outliners in the data. In this paper methods for stabilizing the implicit function fitting using additional constraints in the form of surface (curve) normals are described. These constraints eliminate the problem of sensitivity of the implicit function fitting method to outliners in the data. The authors demonstrate that in certain cases the fitting process can be reduced to a generalized eigenvalue problem that can be efficiently solved by standard numerical procedures. Preliminary experimental results with 2D curves consisting of point location and curve normal constraints as data are encouraging.>

The author addresses the problem of parametric representation and estimation of complex planar curves in 2-D surfaces in 3-D, and nonplanar space curves in 3-D. Curves and surfaces can be defined either parametrically or implicitly, with the latter representation used here. A planar curve is the set of zeros of a smooth function of two variables x-y, a surface is the set of zeros of a smooth function of three variables x-y-z, and a space curve is the intersection of two surfaces, which are the set of zeros of two linearly independent smooth functions of three variables x-y-z For example, the surface of a complex object in 3-D can be represented as a subset of a single implicit surface, with similar results for planar and space curves. It is shown how this unified representation can be used for object recognition, object position estimation, and segmentation of objects into meaningful subobjects, that is, the detection of 'interest regions' that are more complex than high curvature regions and, hence, more useful as features for object recognition.>

The problem of multiresolution 2-D and 3-D shape representation is addressed. Shape is defined as a probability measure with compact support. Both object representations, typically sets of curves and/or surface patches, and observations, sets of scattered data, can be represented in this way. Global properties of shapes are defined as expectations (statistical averages) of certain functions. In particular, the moments of the shapes are global properties. To any shape S and every integer d>0 is associated a shape polynomial of degree 2d, whose coefficients are functions of the moments of S. These polynomials are related to the shape S in an affine-invariant way. They yield small values near S and large values far away, and their level sets approximate S. The shape polynomials define two distances between shapes. As asymmetric measures how well one shape fits as a subset of another one; a symmetric version indicates how equal two shapes are. The evaluation of these distance measures is determined by a sequence of computationally very fast matrix operations. The distance measures are used for recognition and positioning of objects in occluded environments.>

The problem of minimal parameter representation and estimation for complex planar and nonplanar curves, and surfaces is considered. The representation is based on concepts from algebraic geometry: a surface is the set of roots of a polynomial of three variables, and a curve is the intersection of two different surfaces. It is shown that the surfaces of an interesting complex of objects in three-space can be represented by single high degree-polynomials, and a similar statement applies to complex curves in three-space. An approximate expression for the mean-square distance from a set of points to a curve or surface is developed, not only for quadratic surfaces, but also for surfaces and curves defined by polynomials of higher degree. A computationally efficient algorithm is presented to carry out the minimization without using nonlinear optimization techniques.>