Abstract We present an image processing method that converts a raster image to a simplical two‐complex which has only a small number of vertices (base mesh) plus a parametrization that maps each pixel in the original image to a combination of the barycentric coordinates of the triangle it is finally mapped into. Such a conversion of a raster image into a base mesh plus parametrization can be useful for many applications such as segmentation, image retargeting, multi‐resolution editing with arbitrary topologies, edge preserving smoothing, compression, etc. The goal of the algorithm is to produce a base mesh such that it has a small colour distortion as well as high shape fairness, and a parametrization that is globally continuous visually and numerically. Inspired by multi‐resolution adaptive parametrization of surfaces and quadric error metric, the algorithm converts pixels in the image to a dense triangle mesh and performs error‐bounded simplification jointly considering geometry and colour. The eliminated vertices are projected to an existing face. The implementation is iterative and stops when it reaches a prescribed error threshold. The algorithm is feature‐sensitive, i.e. salient feature edges in the images are preserved where possible and it takes colour into account thereby producing a better quality triangulation.

We present a method designed to address some limitations of typical route map displays of driving directions. The main goal of our system is to generate a printable version of a route map that shows the overview and detail views of the route within a single, consistent visual frame. Our proposed visualization provides a more intuitive spatial context than a simple list of turns. We present a novel multifocus technique to achieve this goal, where the foci are defined by points of interest (POI) along the route. A detail lens that encapsulates the POI at a finer geospatial scale is created for each focus. The lenses are laid out on the map to avoid occlusion with the route and each other, and to optimally utilize the free space around the route. We define a set of layout metrics to evaluate the quality of a lens layout for a given route map visualization. We compare standard lens layout methods to our proposed method and demonstrate the effectiveness of our method in generating aesthetically pleasing layouts. Finally, we perform a user study to evaluate the effectiveness of our layout choices.

The HSV color space is an intuitive way to reason about color, but the nonlinear relationship to RGB coordinates complicates histogram analysis of colors in HSV. We present novel Interval-HSV formulas to identify a range in HSV for each RGB interval. We show the usefulness by introducing a parameter-free and completely automatic technique to extract both colored and black ink annotations from faded backgrounds such as digitized aerial photographs, maps, or printed-text documents. We discuss the characteristics of ink mixing in the HSV color space and discover a single feature, the upper limit of the saturation-interval, to extract ink even when it is achromatic. We form robust Interval-HV histograms in order to identify the number and colors of inks in the image.

Abstract In this paper we present dart throwing algorithms to generate maximal Poisson disk point sets directly on 3D surfaces. We optimize dart throwing by efficiently excluding areas of the domain that are already covered by existing darts. In the case of triangle meshes, our algorithm shows dramatic speed improvement over comparable sampling methods. The simplicity of our basic algorithm naturally extends to the sampling of other surface types, including spheres, NURBS, subdivision surfaces, and implicits. We further extend the method to handle variable density points, and the placement of arbitrary ellipsoids without overlap. Finally, we demonstrate how to adapt our algorithm to work with geodesic instead of Euclidean distance. Applications for our method include fur modeling, the placement of mosaic tiles and polygon remeshing.

Abstract The most common form of tabular inversion used in computer graphics is to compute the cumulative distribution table of a probability distribution (PDF) and then search within it to transform points, using an O(log n) binary search. Besides the standard inversion method, however, several other discrete inversion algorithms exist that can perform the same transformation inO(1) time per point. In this paper, we examine the performance of three of these alternate methods, two of which are new.

Abstract In this paper we address the question of how to quickly model glyph‐based Geographic Information System visualizations. Our solution is based on using shape grammars to set up the different aspects of a visualization, including the geometric content of the visualization, methods for resolving layout conflicts and interaction methods. Our approach significantly increases modelling efficiency over similarly flexible systems currently in use.

In this paper, we propose a new framework to visualize hyperspectral images. We present three goals for such a visualization: 1) preservation of spectral distances; 2) discriminability of pixels with different spectral signatures; 3) and interactive visualization for analysis. The introduced method considers all three goals at the same time and produces higher quality output than existing methods. The technical contribution of our mapping is to derive a simplified convex optimization from a complex nonlinear optimization problem. During interactive visualization, we can map the spectral signature of pixels to red, green, and blue colors using a combination of principal component analysis and linear programming. In the results, we present a quantitative analysis to demonstrate the favorable attributes of our algorithm.

We describe an approach to render massive urban models. To prevent a memory transfer bottleneck we propose to render the models from a compressed representation directly. Our solution is based on rendering crude building outlines as polygons and generating details by ray-tracing displacement maps in the fragment shader. We demonstrate how to compress a displacement map so that a decompression algorithm can selectively and quickly access individual entries in a fragment shader. Our prototype implementation shows how a massive urban model can be compressed by a factor of 85 and outperform a basic geometry-based renderer by a factor of 40 to 80 in rendering speed.

This paper presents a robust extrinsic parameter estimation algorithm to calibrate field cameras which were used to observe the formation of clouds on a mountainous region. Generally, camera calibration needs accurate landmark survey and image feature identification. However, our observation area is a large scale scene in a physically inaccessible area, therefore the landmark surveys are not precise. Since clouds are distant to cameras, cloud features in the images are also difficult to accurately identify for stereo correspondences. The noise in landmark survey and cloud feature correspondence makes it challenging to obtain desired cloud observation accuracy by using traditional least squares based camera calibration approaches. Our camera calibration approach is based on a generalized total least square (GTLS) algorithm instead of a normal least square method. Experiments show that the GTLS-based camera calibration is more accurate and robust than LS-based methods for our application.

This paper presents a fully automated 3D face authentication (verification) and recognition (identification) method and recent results from our work in this area. The major contributions of our paper are: (a) the method can handle data with different facial expressions including hair, upper body, clothing, etc. and (b) development of weighted features for discrimination. The input to our system is a triangular mesh and it outputs a matching % against a gallery. Our method includes both surface and curve based features that are automatically extracted from a given face data. The test set for authentication consisted of 117 different people with 421 scans including different facial expressions. Our study shows equal error rate (EER) at 0.065% for normal faces and 1.13% in faces with expressions. We report verification rates of 100% in normal faces and 93.12% in faces with expressions at 0.1% FAR. For identification, our experiment shows 100% rate in normal faces and 95.6% in faces with expressions. From our experiment we conclude that combining feature points, profile curve, and partial face surface matching gives better authentication and recognition rate than any single matching method.

In this paper, an automatic road tracking method is presented for detecting roads from satellite images. This method is based on shape classification of a local homogeneous region around a pixel. The local homogeneous region is enclosed by a polygon, called the pixel footprint. We introduce a spoke wheel operator to obtain the pixel footprint and propose a Fourier-based approach to classify footprints for automatic seeding and growing of the road tracker. We experimentally demonstrate that our proposed road tracker can extract the centerlines of roads with sharp turns and intersections effectively, and has relatively small amount of leakage.

In this paper, a new two-step approach (detecting and pruning) for automatic extraction of road networks from aerial images is presented. The road detection step is based on shape classification of a local homogeneous region around a pixel. The local homogeneous region is enclosed by a polygon, called the footprint of the pixel. This step involves detecting road footprints, tracking roads, and growing a road tree. We use a spoke wheel operator to obtain the road footprint. We propose an automatic road seeding method based on rectangular approximations to road footprints and a toe-finding algorithm to classify footprints for growing a road tree. The road tree pruning step makes use of a Bayes decision model based on the area-to-perimeter ratio (the A/P ratio) of the footprint to prune the paths that leak into the surroundings. We introduce a lognormal distribution to characterize the conditional probability of A/P ratios of the footprints in the road tree and present an automatic method to estimate the parameters that are related to the Bayes decision model. Results are presented for various aerial images. Evaluation of the extracted road networks using representative aerial images shows that the completeness of our road tracker ranges from 84% to 94%, correctness is above 81%, and quality is from 82% to 92%.

This paper presents a shape-based approach in extracting thin structures, such as lines and sheets, from three-dimensional (3D) biomedical images. Of particular interest is the capability to recover cellular structures, such as microtubule spindle fibers and plasma membranes, from laser scanning confocal microscopic (LSCM) data. Hessian-based shape methods are reviewed. A synthesized linear structure is used to evaluate the sensitivity of the multiscale filtering approach in extracting closely positioned fibers. We find that the multiscale approach tends to fuse lines together, which makes it unsuitable for visualizing mouse egg spindle fibers. Single-scale Gaussian filters, balanced between sensitivity and noise resistance, are adopted instead. In addition, through an ellipsoidal Gaussian model, the eigenvalues of the Hessian matrix are quantitatively associated with the standard deviations of the Gaussian model. Existing shape filters are simplified and applied to LSCM data. A significant improvement in extracting closely positioned thin lines is demonstrated by the resultant images. Further, the direct association of shape models and eigenvalues makes the processed images more understandable qualitatively and quantitatively.

In this paper, we present a deformable surface geometric model for segmenting targets from volumetric data. This model deforms under external forces only, and changes its geometry and topology by using improved geometric constraints. External forces are calculated by using the sum of inflation forces, whose contributions take place on internal regions of objects, and the gradient forces, which play a key role when the surface is near the boundary of objects. A new set of geometric constraints is proposed which includes constraints on vertices, edges and faces. Once a constraint is broken, the corresponding topological transformation will occur to keep the geometric and topological integrity of the surface unaltered. We demonstrate that our model can efficiently segment complex anatomic structures from medical 3D images, and achieve the requirements of accuracy and geometry for image segmentation.

This paper presents a coarse-grain approach for segmentation of objects with gray levels appearing in volume data. The input data is on a 3D structured grid of vertices v(i. j. k), each associated with a scalar value. In this paper, we consider a voxel as a /spl kappa/ /spl times/ /spl kappa/ /spl times/ /spl kappa/ cube and each voxel is assigned two values: expectancy and standard deviation (E-SD). We use the Weibull noise index to estimate the noise in a voxel and to obtain more precise E-SD values for each voxel. We plot the frequency of voxels which have the same E-SD, then 3D segmentation based on the Weibull E-SD field is presented. Our test bed includes synthetic data as well as real volume data from a confocal laser scanning microscope (CLSM). Analysis of these data all show distinct and defining regions in their E-SD fields. Under the guide of the E-SD field, we can efficiently segment the objects embedded in real and simulated 3D data.

Our efforts in bringing the scanning probe microscope (SPM) live data available on the Web have been successful. This work is being pursued under the aegis of the IN-VSEE project targeted to bring SPM data live to community colleges, high school and other research labs/classroom. We have further advanced this to provide the capability of remote operation of the SPM via the Web. The truly remote operator can control many functions of the microscope with reasonable security and ease. The latter marks a milestone in use of the Web for truly interactive bi-directional communication involving feedback and control of an instrument. The architecture also incorporates an interactive "chat" channel among the observers and the operator(s) and compressed video delivery in separate windows. Further, since the SPM data is inherently 3-dimensional, a plug-in has also been developed to display the live data as 5-dimensional model, with support for zoom, pan, rotation, etc.