This paper presents EVSplitting, an efficient and visually consistent splitting algorithm for 3D Gaussian Splatting (3DGS). It is designed to make operating 3DGS as easy and effective as other 3D explicit representations, readily for industrial productions. The challenges of above target are: 1) The huge number and complex attributes of 3DGS make it tough to explicitly operate on 3DGS in a real-time and learning-free manner; 2) The visual effect of 3DGS is very difficult to maintain during explicit operations and 3) The anisotropism of Gaussian always leads to blurs and artifacts. As far as we know, no prior work can address these challenges well. In this work, we introduce a direct and efficient 3DGS splitting algorithm to solve them. Specifically, we formulate the 3DGS splitting as two minimization problems that aim to ensure visual consistency and reduce Gaussian overflow across boundary (splitting plane), respectively. Firstly, we impose conservations on the zero-, first- and second-order moments of the weighted Gaussian distribution to guarantee visual consistency. Secondly, we reduce the boundary overflow with a special constraint on the aforementioned conservations. With these conservations and constraints, we derive a closed-form solution for the 3DGS splitting problem. This yields an easy-to-implement, plug-and-play, efficient and fundamental tool, benefiting various downstream applications of 3DGS.

the Best Paper Award Committee to select the Best Paper.After careful deliberation, the following paper was chosen with the unanimous consensus as the winner, on the basis of its intellectual merit and potential impact:Visual attention network [1] Two other papers were awarded an

Deep neural networks (DNNs) have been widely used for mesh processing in recent years. However, current DNNs can not process arbitrary meshes efficiently. On the one hand, most DNNs expect 2-manifold, watertight meshes, but many meshes, whether manually designed or automatically generated, may have gaps, non-manifold geometry, or other defects. On the other hand, the irregular structure of meshes also brings challenges to building hierarchical structures and aggregating local geometric information, which is critical to conduct DNNs. In this paper, we present DGNet, an efficient, effective and generic deep neural mesh processing network based on dual graph pyramids; it can handle arbitrary meshes. First, we construct dual graph pyramids for meshes to guide feature propagation between hierarchical levels for both downsampling and upsampling. Second, we propose a novel convolution to aggregate local features on the proposed hierarchical graphs. By utilizing both geodesic neighbors and euclidean neighbors, the network enables feature aggregation both within local surface patches and between isolated mesh components. Experimental results demonstrate that DGNet can be applied to both shape analysis and large-scale scene understanding. Furthermore, it achieves superior performance on various benchmarks, including ShapeNetCore, HumanBody, ScanNet and Matterport3D. Code and models will be available at https://github.com/li-xl/DGNet.

Inspired by the success of recent vision transformers and large kernel design in convolutional neural networks (CNNs), in this paper, we analyze and explore essential reasons for their success. We claim two factors that are critical for 3D large-scale scene understanding: a larger receptive field and operations with greater non-linearity. The former is responsible for providing long range contexts and the latter can enhance the capacity of the network. To achieve the above properties, we propose a simple yet effective long range pooling (LRP) module using dilation max pooling, which provides a network with a large adaptive receptive field. LRP has few parameters, and can be readily added to current CNNs. Also, based on LRP, we present an entire network architecture, LRPNet, for 3D understanding. Ablation studies are presented to support our claims, and show that the LRP module achieves better results than large kernel convolution yet with reduced computation, due to its non-linearity. We also demonstrate the superiority of LRPNet on various benchmarks: LRPNet performs the best on ScanNet and surpasses other CNN-based methods on S3DIS and Matterport3D. Code will be avalible at https://github.com/li-xl/LRPNet.

Objects in aerial images show greater variations in scale and orientation than in other images, making them harder to detect using vanilla deep convolutional neural networks. Networks with sampling equivariance can adapt sampling from input feature maps to object transformation, allowing a convolutional kernel to extract effective object features under different transformations. However, methods such as deformable convolutional networks can only provide sampling equivariance under certain circumstances, as they sample by location. We propose sampling equivariant self-attention networks, which treat self-attention restricted to a local image patch as convolution sampling by masks instead of locations, and a transformation embedding module to improve the equivariant sampling further. We further propose a novel randomized normalization module to enhance network generalization and a quantitative evaluation metric to fairly evaluate the ability of sampling equivariance of different models. Experiments show that our model provides significantly better sampling equivariance than existing methods without additional supervision and can thus extract more effective image features. Our model achieves state-of-the-art results on the DOTA-v1.0, DOTA-v1.5, and HRSC2016 datasets without additional computations or parameters.

Our goal is to automatically generate CAD 3D models from 2D sketches as part of a design chain where models should be procedural, containing features arranged in a model tree and linked to suitable datums. Current procedural models capture much about the design intent and are easy to edit, but must be created from scratch during the detailed design state—given conceptual sketches as used by designers in the early part of the design process, current sketch-based modeling approaches only output explicit models. Thus, we describe an approach to extract high-level information directly from 2D engineering wireframe sketches and use it to complete a CSG feature tree, which serves as a model tree for a procedural 3D CAD model. Our method extracts procedural model information directly from 2D sketches in the form of a set of features, plus a set of datums and relationships between these features. We detect and analyze features of 2D sketches in isolation, and define the CSG feature tree by the parent–child relationships between features, and combine this information to obtain a complete and consistent CSG feature tree that can be transferred to a 3D modeler, which reconstructs the model. This paper focuses on how to extract the feature datums and the extrusion operation from an input 2D sketch.

Abstract Joint pose estimation of human hands and objects from a single RGB image is an important topic for AR/VR, robot manipulation, etc. It is common practice to determine both poses directly from the image; some recent methods attempt to improve the initial poses using a variety of contact‐based approaches. However, few methods take the real physical constraints conveyed by the image into consideration, leading to less realistic results than the initial estimates. To overcome this problem, we make use of a set of high‐level 2D features which can be directly extracted from the image in a new pipeline which combines contact approaches and these constraints during optimization. Our pipeline achieves better results than direct regression or contact‐based optimization: they are closer to the ground truth and provide high quality contact.

Humans can naturally and effectively find salient regions in complex scenes. Motivated by this observation, attention mechanisms were introduced into computer vision with the aim of imitating this aspect of the human visual system. Such an attention mechanism can be regarded as a dynamic weight adjustment process based on features of the input image. Attention mechanisms have achieved great success in many visual tasks, including image classification, object detection, semantic segmentation, video understanding, image generation, 3D vision, multimodal tasks, and self-supervised learning. In this survey, we provide a comprehensive review of various attention mechanisms in computer vision and categorize them according to approach, such as channel attention, spatial attention, temporal attention, and branch attention; a related repository https://github.com/MenghaoGuo/Awesome-Vision-Attentions is dedicated to collecting related work. We also suggest future directions for attention mechanism research.

Convolutionalneural networks (CNNs) have made great breakthroughs in two-dimensional (2D) computer vision. However, their irregular structure makes it hard to harness the potential of CNNs directly on meshes. A subdivision surface provides a hierarchical multi-resolution structure in which each face in a closed 2-manifold triangle mesh is exactly adjacent to three faces. Motivated by these two observations, this article presents SubdivNet , an innovative and versatile CNN framework for three-dimensional (3D) triangle meshes with Loop subdivision sequence connectivity. Making an analogy between mesh faces and pixels in a 2D image allows us to present a mesh convolution operator to aggregate local features from nearby faces. By exploiting face neighborhoods, this convolution can support standard 2D convolutional network concepts, e.g., variable kernel size, stride, and dilation. Based on the multi-resolution hierarchy, we make use of pooling layers that uniformly merge four faces into one and an upsampling method that splits one face into four. Thereby, many popular 2D CNN architectures can be easily adapted to process 3D meshes. Meshes with arbitrary connectivity can be remeshed to have Loop subdivision sequence connectivity via self-parameterization, making SubdivNet a general approach. Extensive evaluation and various applications demonstrate SubdivNet’s effectiveness and efficiency.

Accurate camera pose estimation is essential and challenging for real world dynamic 3D reconstruction and augmented reality applications. In this article, we present a novel RGB-D SLAM approach for accurate camera pose tracking in dynamic environments. Previous methods detect dynamic components only across a short time-span of consecutive frames. Instead, we provide a more accurate dynamic 3D landmark detection method, followed by the use of long-term consistency via conditional random fields, which leverages long-term observations from multiple frames. Specifically, we first introduce an efficient initial camera pose estimation method based on distinguishing dynamic from static points using graph-cut RANSAC. These static/dynamic labels are used as priors for the unary potential in the conditional random fields, which further improves the accuracy of dynamic 3D landmark detection. Evaluation using the TUM and Bonn RGB-D dynamic datasets shows that our approach significantly outperforms state-of-the-art methods, providing much more accurate camera trajectory estimation in a variety of highly dynamic environments. We also show that dynamic 3D reconstruction can benefit from the camera poses estimated by our RGB-D SLAM approach.

The irregular domain and lack of ordering make it challenging to design deep neural networks for point cloud processing. This paper presents a novel framework named Point Cloud Transformer (PCT) for point cloud learning. PCT is based on Transformer, which achieves huge success in natural language processing and displays great potential in image processing. It is inherently permutation invariant for processing a sequence of points, making it well-suited for point cloud learning. To better capture local context within the point cloud, we enhance input embedding with the support of farthest point sampling and nearest neighbor search. Extensive experiments demonstrate that the PCT achieves the state-of-the-art performance on shape classification, part segmentation, semantic segmentation, and normal estimation tasks.

In the first week of May 2021, researchers from four different institutions: Google,

In order to accurately count the number of animals grazing on grassland, we present a livestock detection algorithm using modified versions of U-net and Google Inception-v4 net. This method works well to detect dense and touching instances. We also introduce a dataset for livestock detection in aerial images, consisting of 89 aerial images collected by quadcopter. Each image has resolution of about 3000×4000 pixels, and contains livestock with varying shapes, scales, and orientations. We evaluate our method by comparison against Faster RCNN and Yolo-v3 algorithms using our aerial livestock dataset. The average precision of our method is better than Yolo-v3 and is comparable to Faster RCNN.

A quick-response code (QR code) is a two-dimensional code akin to a barcode that encodes a message of limited length. In this paper, we present a variant of QR code, a two-layer QR code. Its two-layer structure can display two alternative messages when scanned from two different directions. We propose a method to generate such two-layer QR codes encoding two given messages in a few seconds. We also demonstrate the robustness of our method on both synthetic and fabricated examples. All source code will be made publicly available (https://github.com/yuantailing/two-layer-qrcode).

Canonical forms attempt to factor out a non-rigid shape’s pose, giving a pose-neutral shape. This opens up the possibility of using methods originally designed for rigid shape retrieval for the task of non-rigid shape retrieval. We extend our recent benchmark for testing canonical form algorithms. Our new benchmark is used to evaluate a greater number of state-of-the-art canonical forms, on five recent non-rigid retrieval datasets, within two different retrieval frameworks. A total of fifteen different canonical form methods are compared. We find that the difference in retrieval accuracy between different canonical form methods is small, but varies significantly across different datasets. We also find that efficiency is the main difference between the methods.

Objective image quality metrics (IQMs) potentially benefit from the addition of visual saliency. However, challenges to optimizing the performance of saliency-based IQMs remain. A previous eye-tracking study has shown that gaze is concentrated in fewer places in images with highly salient features than in images lacking salient features. From this, it can be inferred that the former are more likely to benefit from adding a saliency term to an IQM. To understand whether these ideas still hold when using computational saliency instead of eye-tracking data, we first conducted a statistical evaluation using 15 state-of-the-art saliency models and 10 well-known IQMs. We then used the results to devise an algorithm, which adaptively incorporates saliency in IQMs for natural scenes, based on saliency dispersion. Experimental results demonstrate that this can give significant improvements.

Unlike image blending algorithms, video blending algorithms have been little studied. In this paper, we investigate 6 popular blending algorithms-feather blending, multi-band blending, modified Poisson blending, mean value coordinate blending, multi-spline blending and convolution pyramid blending. We consider their application to blending realtime panoramic videos, a key problem in various virtual reality tasks. To evaluate the performances and suitabilities of the 6 algorithms for this problem, we have created a video benchmark with several videos captured under various conditions. We analyze the time and memory needed by the above 6 algorithms, for both CPU and GPU implementations (where readily parallelizable). The visual quality provided by these algorithms is also evaluated both objectively and subjectively. The video benchmark and algorithm implementations are publicly available1.

We present the first computational tool to help ordinary users create transforming pop-up books. In each transforming pop-up, when the user pulls a tab, an initial flat two-dimensional (2D) pattern, i.e., a 2D shape with a superimposed picture, such as an airplane, turns into a new 2D pattern, such as a robot. Given the two 2D patterns, our approach automatically computes a 3D pop-up mechanism that transforms one pattern into the other; it also outputs a design blueprint, allowing the user to easily make the final model. We also present a theoretical analysis of basic transformation mechanisms; combining these basic mechanisms allows more flexibility of final designs. Using our approach, inexperienced users can create models in a short time; previously, even experienced artists often took weeks to manually create them. We demonstrate our method on a variety of real-world examples.

Though elegant in mathematical formulation, gradient-domain image blending suffers from bleeding artefacts in real world applications. We propose an image blending algorithm that avoids bleeding artefacts while preserving the good properties of gradient-domain blending, such as smooth transitions between the candidate regions. Our key idea to finesse the non-smooth boundary difference calculation that causes bleeding artefacts is to use local patch differences. While most previous gradient-domain blending algorithms change one region to fit the other, to further reduce bleeding, we perform bidirectional blending so that both regions change simultaneously. Our blending algorithm is fast: when applied to image stitching, it can achieve 20 fps at 4K resolution. Source code and test images are publicly available.

It is challenging to track a target continuously in videos with long-term occlusion, or objects which leave then re-enter a scene. Existing tracking algorithms combined with onlinetrained object detectors perform unreliably in complex conditions, and can only provide discontinuous trajectories with jumps in position when the object is occluded. This paper proposes a novel framework of tracking-by-detection using selection and completion to solve the abovementioned problems. It has two components, tracking and trajectory completion. An offline-trained object detector can localize objects in the same category as the object being tracked. The object detector is based on a highly accurate deep learning model. The object selector determines which object should be used to re-initialize a traditional tracker. As the object selector is trained online, it allows the framework to be adaptable. During completion, a predictive non-linear autoregressive neural network completes any discontinuous trajectory. The tracking component is an online real-time algorithm, and the completion part is an after-theevent mechanism. Quantitative experiments show a significant improvement in robustness over prior state-of- the-art methods.

We propose a localization refinement approach for candidate traffic signs. Previous traffic sign localization approaches, which place a bounding rectangle around the sign, do not always give a compact bounding box, making the subsequent classification task more difficult. We formulate localization as a segmentation problem, and incorporate prior knowledge concerning color and shape of traffic signs. To evaluate the effectiveness of our approach, we use it as an intermediate step between a standard traffic sign localizer and a classifier. Our experiments use the well-known German Traffic Sign Detection Benchmark (GTSDB) as well as our new Chinese Traffic Sign Detection Benchmark. This newly created benchmark is publicly available,1and goes beyond previous benchmark data sets: it has over 5000 high-resolution images containing more than 14 000 traffic signs taken in realistic driving conditions. Experimental results show that our localization approach significantly improves bounding boxes when compared with a standard localizer, thereby allowing a standard traffic sign classifier to generate more accurate classification results.1http://cg.cs.tsinghua.edu.cn/ctsdb/.

We introduce a unified particle framework which integrates the phase-field method with multi-material simulation to allow modeling of both liquids and solids, as well as phase transitions between them. A simple elasto-plastic model is used to capture the behavior of various kinds of solids, including deformable bodies, granular materials, and cohesive soils. States of matter or phases , particularly liquids and solids, are modeled using the non-conservative Allen-Cahn equation. In contrast, materials---made of different substances---are advected by the conservative Cahn-Hilliard equation. The distributions of phases and materials are represented by a phase variable and a concentration variable, respectively, allowing us to represent commonly observed fluid-solid interactions. Our multi-phase, multi-material system is governed by a unified Helmholtz free energy density. This framework provides the first method in computer graphics capable of modeling a continuous interface between phases. It is versatile and can be readily used in many scenarios that are challenging to simulate. Examples are provided to demonstrate the capabilities and effectiveness of this approach.

In this paper, we present a novel pairwise-force smoothed particle hydrodynamics (PF-SPH) model to enable simulation of various interactions at interfaces in real time. Realistic capture of interactions at interfaces is a challenging problem for SPH-based simulations, especially for scenarios involving multiple interactions at different interfaces. Our PF-SPH model can readily handle multiple types of interactions simultaneously in a single simulation; its basis is to use a larger support radius than that used in standard SPH. We adopt a novel anisotropic filtering term to further improve the performance of interaction forces. The proposed model is stable; furthermore, it avoids the particle clustering problem which commonly occurs at the free surface. We show how our model can be used to capture various interactions. We also consider the close connection between droplets and bubbles, and show how to animate bubbles rising in liquid as well as bubbles in air. Our method is versatile, physically plausible and easy-to-implement. Examples are provided to demonstrate the capabilities and effectiveness of our approach.

Shape registration is fundamental to 3D object acquisition; it is used to fuse scans from multiple views. Existing algorithms mainly utilize geometric information to determine alignment, but this typically results in noticeable misalignment of textures (i.e. surface colors) when using RGB-depth cameras. We address this problem using a novel approach to color-aware registration, which takes both color and geometry into consideration simultaneously. Color information is exploited throughout the pipeline to provide more effective sampling, correspondence and alignment, in particular for surfaces with detailed textures. Our method can furthermore tackle both rigid and non-rigid registration problems (arising, for example, due to small changes in the object during scanning, or camera distortions). We demonstrate that our approach produces significantly better results than previous methods.

The retrieval of non-rigid 3D shapes is an important task. A common technique is to simplify this problem to a rigid shape retrieval task by producing a bending-invariant canonical form for each shape in the dataset to be searched. It is common for these techniques to attempt to “unbend” a shape by applying multidimensional scaling (MDS) to the distances between points on the mesh, but this leads to unwanted local shape distortions. We instead perform the unbending on the skeleton of the mesh, and use this to drive the deformation of the mesh itself. This leads to computational speed-up, and reduced distortion of local shape detail. We compare our method against other canonical forms: our experiments show that our method achieves state-of-the-art retrieval accuracy in a recent canonical forms benchmark, and only a small drop in retrieval accuracy over the state-of-the-art in a second recent benchmark, while being significantly faster.

Pixel disparity—the offset of corresponding pixels between left and right views—is a crucial parameter in stereoscopic three-dimensional (S3D) video, as it determines the depth perceived by the human visual system (HVS). Unsuitable pixel disparity distribution throughout an S3D video may lead to visual discomfort. We present a unified and extensible stereoscopic video disparity adjustment framework which improves the viewing experience for an S3D video by keeping the perceived 3D appearance as unchanged as possible while minimizing discomfort. We first analyse disparity and motion attributes of S3D video in general, then derive a wide-ranging visual discomfort metric from existing perceptual comfort models. An objective function based on this metric is used as the basis of a hierarchical optimisation method to find a disparity mapping function for each input video frame. Warping-based disparity manipulation is then applied to the input video to generate the output video, using the desired disparity mappings as constraints. Our comfort metric takes into account disparity range, motion , and stereoscopic window violation ; the framework could easily be extended to use further visual comfort models. We demonstrate the power of our approach using both animated cartoons and real S3D videos.

We consider a face-to-face videoconferencing system that uses a Kinect camera at each end of the link for 3D modeling and an ordinary 2D display for output. The Kinect camera allows a 3D model of each participant to be transmitted; the (assumed static) background is sent separately. Furthermore, the Kinect tracks the receiver’s head, allowing our system to render a view of the sender depending on the receiver’s viewpoint. The resulting motion parallax gives the receivers a strong impression of 3D viewing as they move, yet the system only needs an ordinary 2D display. This is cheaper than a full 3D system, and avoids disadvantages such as the need to wear shutter glasses, VR headsets, or to sit in a particular position required by an autostereo display. Perceptual studies show that users experience a greater sensation of depth with our system compared to a typical 2D videoconferencing system.

3D models of humans are commonly used within computer graphics and vision, and so the ability to distinguish between body shapes is an important shape retrieval problem. We extend our recent paper which provided a benchmark for testing non-rigid 3D shape retrieval algorithms on 3D human models. This benchmark provided a far stricter challenge than previous shape benchmarks. We have added 145 new models for use as a separate training set, in order to standardise the training data used and provide a fairer comparison. We have also included experiments with the FAUST dataset of human scans. All participants of the previous benchmark study have taken part in the new tests reported here, many providing updated results using the new data. In addition, further participants have also taken part, and we provide extra analysis of the retrieval results. A total of 25 different shape retrieval methods are compared.

In this paper, we present a novel algorithm to simultaneously accomplish color quantization and dithering of images. This is achieved by minimizing a perception-based cost function, which considers pixel-wise differences between filtered versions of the quantized image and the input image. We use edge aware filters in defining the cost function to avoid mixing colors on the opposite sides of an edge. The importance of each pixel is weighted according to its saliency. To rapidly minimize the cost function, we use a modified multi-scale iterative conditional mode (ICM) algorithm, which updates one pixel a time while keeping other pixels unchanged. As ICM is a local method, careful initialization is required to prevent termination at a local minimum far from the global one. To address this problem, we initialize ICM with a palette generated by a modified median-cut method. Compared with previous approaches, our method can produce high-quality results with a fewer visual artifacts but also requires significantly less computational effort.

This work extends existing multiphase-fluid SPH frameworks to cover solid phases, including deformable bodies and granular materials. In our extended multiphase SPH framework, the distribution and shapes of all phases, both fluids and solids, are uniformly represented by their volume fraction functions. The dynamics of the multiphase system is governed by conservation of mass and momentum within different phases. The behavior of individual phases and the interactions between them are represented by corresponding constitutive laws, which are functions of the volume fraction fields and the velocity fields. Our generalized multiphase SPH framework does not require separate equations for specific phases or tedious interface tracking. As the distribution, shape and motion of each phase is represented and resolved in the same way, the proposed approach is robust, efficient and easy to implement. Various simulation results are presented to demonstrate the capabilities of our new multiphase SPH framework, including deformable bodies, granular materials, interaction between multiple fluids and deformable solids, flow in porous media, and dissolution of deformable solids.

We present a method for realtime reconstruction of an animating human body,which produces a sequence of deforming meshes representing a given performance captured by a single commodity depth camera. We achieve realtime single-view mesh completion by enhancing the parameterized SCAPE model.Our method, which we call Realtime SCAPE, performs full-body reconstruction without the use of markers.In Realtime SCAPE, estimations of body shape parameters and pose parameters, needed for reconstruction, are decoupled. Intrinsic body shape is first precomputed for a given subject, by determining shape parameters with the aid of a body shape database. Subsequently, per-frame pose parameter estimation is performed by means of linear blending skinning (LBS); the problem is decomposed into separately finding skinning weights and transformations. The skinning weights are also determined offline from the body shape database,reducing online reconstruction to simply finding the transformations in LBS. Doing so is formulated as a linear variational problem;carefully designed constraints are used to impose temporal coherence and alleviate artifacts. Experiments demonstrate that our method can produce full-body mesh sequences with high fidelity.

Automatic feature recognition aids downstream processes such as engineering analysis and manufacturing planning. Not all features can be defined in advance; a declarative approach allows engineers to specify new features without having to design algorithms to find them. Naive translation of declarations leads to executable algorithms with high time complexity. Database queries are also expressed declaratively; there is a large literature on optimizing query plans for efficient execution of database queries. Our earlier work investigated applying such technology to feature recognition, using a testbed interfacing a database system (SQLite) to a CAD modeler (CADfix). Feature declarations were translated into SQL queries which are then executed. The current paper extends this approach, using the PostgreSQL database, and provides several new insights: (i) query optimization works quite differently in these two databases, (ii) with care, an approach to query translation can be devised that works well for both databases, and (iii) when finding various simple common features, linear time performance can be achieved with respect to model size, with acceptable times for real industrial models. Further results also show how (i) lazy evaluation can be used to reduce the work performed by the CAD modeler, and (ii) estimating the time taken to compute various geometric operations can further improve the query plan. Experimental results are presented to validate our main conclusions.

This paper considers panorama images used for street views. Their viewing angle of 360° causes pixels at the top and bottom to appear stretched and warped. Although current image completion algorithms work well, they cannot be directly used in the presence of such distortions found in panoramas of street views. We thus propose a novel approach to complete such 360° panoramas using optimization-based projection to deal with distortions. Experimental results show that our approach is efficient and provides an improvement over standard image completion algorithms.

Retrieval of 3D shapes is a challenging problem, especially for non-rigid shapes. One approach giving favourable results uses multidimensional scaling (MDS) to compute a canonical form for each mesh, after which rigid shape matching can be applied. However, a drawback of this method is that it requires geodesic distances to be computed between all pairs of mesh vertices. Due to the super-quadratic computational complexity, canonical forms can only be computed for low-resolution meshes. We suggest a linear time complexity method for computing a canonical form, using Euclidean distances between pairs of a small subset of vertices. This approach has comparable retrieval accuracy but lower time complexity than using global geodesic distances, allowing it to be used on higher resolution meshes, or for more meshes to be considered within a time budget.

A major difference between amateur and professional video lies in the quality of camera paths. Previous work on video stabilization has considered how to improve amateur video by smoothing the camera path. In this paper, we show that additional changes to the camera path can further improve video aesthetics. Our new optimization method achieves multiple simultaneous goals: 1) stabilizing video content over short time scales; 2) ensuring simple and consistent camera paths over longer time scales; and 3) improving scene composition by automatically removing distractions, a common occurrence in amateur video. Our approach uses an L(1) camera path optimization framework, extended to handle multiple constraints. Two passes of optimization are used to address both low-level and high-level constraints on the camera path. The experimental and user study results show that our approach outputs video that is perceptually better than the input, or the results of using stabilization only.

Feature extraction and matching (FEM) for 3D shapes finds numerous applications in computer graphics and vision for object modeling, retrieval, morphing, and recognition. However, unavoidable incorrect matches lead to inaccurate estimation of the transformation relating different datasets. Inspired by AdaBoost, this paper proposes a novel iterative re-weighting method to tackle the challenging problem of evaluating point matches established by typical FEM methods. Weights are used to indicate the degree of belief that each point match is correct. Our method has three key steps: (i) estimation of the underlying transformation using weighted least squares, (ii) penalty parameter estimation via minimization of the weighted variance of the matching errors, and (iii) weight re-estimation taking into account both matching errors and information learnt in previous iterations. A comparative study, based on real shapes captured by two laser scanners, shows that the proposed method outperforms four other state-of-the-art methods in terms of evaluating point matches between overlapping shapes established by two typical FEM methods, resulting in more accurate estimates of the underlying transformation. This improved transformation can be used to better initialize the iterative closest point algorithm and its variants, making 3D shape registration more likely to succeed.

Abstract We present a data‐driven method for automatically recoloring a photo to enhance its appearance or change a viewer's emotional response to it. A compact representation called a RegionNet summarizes color and geometric features of image regions, and geometric relationships between them. Correlations between color property distributions and geometric features of regions are learned from a database of well‐colored photos. A probabilistic factor graph model is used to summarize distributions of color properties and generate an overall probability distribution for color suggestions. Given a new input image, we can generate multiple recolored results which unlike previous automatic results, are both natural and artistic, and compatible with their spatial arrangements.

Abstract Visual cryptography is an encryption technique that hides a secret image by distributing it between some shared images made up of seemingly random black‐and‐white pixels. Extended visual cryptography (EVC) goes further in that the shared images instead represent meaningful binary pictures. The original approach to EVC suffered from low contrast, so later papers considered how to improve the visual quality of the results by enhancing contrast of the shared images. This work further improves the appearance of the shared images by preserving edge structures within them using a framework of dithering followed by a detail recovery operation. We are also careful to suppress noise in smooth areas.

Abstract Identifying multiple deformable parts on meshes and establishing dense correspondences between them are tasks of fundamental importance to computer graphics, with applications to e.g. geometric edit propagation and texture transfer. Much research has considered establishing correspondences between non‐rigid surfaces, but little work can both identify similar multiple deformable partsandhandle partial shape correspondences. This paper addresses two related problems, treating them as a whole: (i) identifying similar deformable parts on a mesh, related by anon‐rigidtransformation to a given query part, and (ii) establishing dense point correspondences automatically between such parts. We show that simple and efficient techniques can be developed if we make the assumption that these parts locally undergo isometric deformation. Our insight is that similar deformable parts are suggested by large clusters of point correspondences that are isometrically consistent. Once such parts are identified,densepoint correspondences can be obtained by an iterative propagation process. Our techniques are applicable to models with arbitrary topology. Various examples demonstrate the effectiveness of our techniques.

We present a novel solution to automatic semantic modeling of indoor scenes from a sparse set of low-quality RGB-D images. Such data presents challenges due to noise, low resolution, occlusion and missing depth information. We exploit the knowledge in a scene database containing 100s of indoor scenes with over 10,000 manually segmented and labeled mesh models of objects. In seconds, we output a visually plausible 3D scene, adapting these models and their parts to fit the input scans. Contextual relationships learned from the database are used to constrain reconstruction, ensuring semantic compatibility between both object models and parts. Small objects and objects with incomplete depth information which are difficult to recover reliably are processed with a two-stage approach. Major objects are recognized first, providing a known scene structure. 2D contour-based model retrieval is then used to recover smaller objects. Evaluations using our own data and two public datasets show that our approach can model typical real-world indoor scenes efficiently and robustly.

We propose a novel method for detecting mesh saliency, a perceptually-based measure of the importance of a local region on a 3D surface mesh. Our method incorporates global considerations by making use of spectral attributes of the mesh, unlike most existing methods which are typically based on local geometric cues. We first consider the properties of the log-Laplacian spectrum of the mesh. Those frequencies which show differences from expected behaviour capture saliency in the frequency domain. Information about these frequencies is considered in the spatial domain at multiple spatial scales to localise the salient features and give the final salient areas. The effectiveness and robustness of our approach are demonstrated by comparisons to previous approaches on a range of test models. The benefits of the proposed method are further evaluated in applications such as mesh simplification, mesh segmentation, and scan integration, where we show how incorporating mesh saliency can provide improved results.

Finding correspondences between two surfaces is a fundamental operation in various applications in computer graphics and related fields. Candidate correspondences can be found by matching local signatures, but as they only consider local geometry, many are globally inconsistent. We provide a novel algorithm to prune a set of candidate correspondences to those most likely to be globally consistent. Our approach can handle articulated surfaces, and ones related by a deformation which is globally nonisometric, provided that the deformation is locally approximately isometric. Our approach uses an efficient diffusion framework, and only requires geodesic distance calculations in small neighbourhoods, unlike many existing techniques which require computation of global geodesic distances. We demonstrate that, for typical examples, our approach provides significant improvements in accuracy, yet also reduces time and memory costs by a factor of several hundred compared to existing pruning techniques. Our method is furthermore insensitive to holes, unlike many other methods.

Filling a small hole in an image with plausible content is well studied. Extrapolating an image to give a distinctly larger one is much more challenging---a significant amount of additional content is needed which matches the original image, especially near its boundaries. We propose a data-driven approach to this problem. Given a source image, and the amount and direction(s) in which it is to be extrapolated, our system determines visually consistent content for the extrapolated regions using library images. As well as considering low-level matching, we achieve consistency at a higher level by using graph proxies for regions of source and library images. Treating images as graphs allows us to find candidates for image extrapolation in a feasible time. Consistency of subgraphs in source and library images is used to find good candidates for the additional content; these are then further filtered. Region boundary curves are aligned to ensure consistency where image parts are joined using a photomontage method. We demonstrate the power of our method in image editing applications.

In this paper, we propose a data-driven approach for realistic deformation of articulated meshes: the wide availability of pose data makes such an approach feasible. We use multiple reference models, combined with a fast linear blending skinning (LBS) method in local spaces. By exploiting information from the reference models, realistic deformation is achieved, yet with computational efficiency comparable to traditional blending methods-our approach is suitable for real-time applications. We demonstrate the effectiveness of our algorithm using various examples.

This paper presents a novel approach to edge-aware image manipulation. Our method processes a Gaussian pyramid from coarse to fine, and at each level, applies a nonlinear filter bank to the neighborhood of each pixel. Outputs of these spatially-varying filters are merged using global optimization. The optimization problem is solved using an explicit mixed-domain (real space and DCT transform space) solution, which is efficient, accurate, and easy-to-implement. We demonstrate applications of our method to a set of problems, including detail and contrast manipulation, HDR compression, nonphotorealistic rendering, and haze removal.

We introduce PatchNets , a compact, hierarchical representation describing structural and appearance characteristics of image regions, for use in image editing. In a PatchNet, an image region with coherent appearance is summarized by a graph node, associated with a single representative patch, while geometric relationships between different regions are encoded by labelled graph edges giving contextual information. The hierarchical structure of a PatchNet allows a coarse-to-fine description of the image. We show how this PatchNet representation can be used as a basis for interactive, library-driven, image editing. The user draws rough sketches to quickly specify editing constraints for the target image. The system then automatically queries an image library to find semantically-compatible candidate regions to meet the editing goal. Contextual image matching is performed using the PatchNet representation, allowing suitable regions to be found and applied in a few seconds, even from a library containing thousands of images.

Feature matching is a challenging problem at the heart of numerous computer graphics and computer vision applications. We present the SuperMatching algorithm for finding correspondences between two sets of features. It does so by considering triples or higher order tuples of points, going beyond the pointwise and pairwise approaches typically used. SuperMatching is formulated using a supersymmetric tensor representing an affinity metric that takes into account feature similarity and geometric constraints between features: Feature matching is cast as a higher order graph matching problem. SuperMatching takes advantage of supersymmetry to devise an efficient sampling strategy to estimate the affinity tensor, as well as to store the estimated tensor compactly. Matching is performed by an efficient higher order power iteration approach that takes advantage of this compact representation. Experiments on both synthetic and real data show that SuperMatching provides more accurate feature matching than other state-of-the-art approaches for a wide range of 2D and 3D features, with competitive computational cost.

Solid textures, comprising 3D particles embedded in a matrix in a regular or semiregular pattern, are common in natural and man-made materials, such as brickwork, stone walls, plant cells in a leaf, etc. We present a novel technique for synthesizing such textures, starting from 2D image exemplars which provide cross-sections of the desired volume texture. The shapes and colors of typical particles embedded in the structure are estimated from their 2D cross-sections. Particle positions in the texture images are also used to guide spatial placement of the 3D particles during synthesis of the 3D texture. Our experiments demonstrate that our algorithm can produce higher quality structures than previous approaches; they are both compatible with the input images, and have a plausible 3D nature.

Traditional image editing techniques cannot be directly used to edit stereoscopic ("3D") media, as extra constraints are needed to ensure consistent changes are made to both left and right images. Here, we consider manipulating perspective in stereoscopic pairs. A straightforward approach based on depth recovery is unsatisfactory: Instead, we use feature correspondences between stereoscopic image pairs. Given a new, user-specified perspective, we determine correspondence constraints under this perspective and optimize a 2D warp for each image that preserves straight lines and guarantees proper stereopsis relative to the new camera. Experiments verify that our method generates new stereoscopic views that correspond well to expected projections, for a wide range of specified perspective. Various advanced camera effects, such as dolly zoom and wide angle effects, can also be readily generated for stereoscopic image pairs using our method.

We present a video editing technique based on changing the timelines of individual objects in video, which leaves them in their original places but puts them at different times. This allows the production of object-level slow motion effects, fast motion effects, or even time reversal. This is more flexible than simply applying such effects to whole frames, as new relationships between objects can be created. As we restrict object interactions to the same spatial locations as in the original video, our approach can produce highquality results using only coarse matting of video objects. Coarse matting can be done efficiently using automatic video object segmentation, avoiding tedious manual matting. To design the output, the user interactively indicates the desired new life spans of objects, and may also change the overall running time of the video. Our method rearranges the timelines of objects in the video whilst applying appropriate object interaction constraints. We demonstrate that, while this editing technique is somewhat restrictive, it still allows many interesting results.

We introduce a novel stratified sampling technique for mesh surfaces that gives the user control over sampling density and anisotropy via a tensor field. Our approach is based on sampling space-filling curves mapped onto mesh segments via parametrizations aligned with the tensor field. After a short preprocessing step, samples can be generated in real time. Along with visual examples, we provide rigorous spectral analysis and differential domain analysis of our sampling. The sample distributions are of high quality: they fulfil the blue noise criterion, so have minimal artifacts due to regularity of sampling patterns, and they accurately represent isotropic and anisotropic densities on the plane and on mesh surfaces. They also have low discrepancy, ensuring that the surface is evenly covered.

Three-dimensional surface registration transforms multiple three-dimensional data sets into the same coordinate system so as to align overlapping components of these sets. Recent surveys have covered different aspects of either rigid or nonrigid registration, but seldom discuss them as a whole. Our study serves two purposes: 1) To give a comprehensive survey of both types of registration, focusing on three-dimensional point clouds and meshes and 2) to provide a better understanding of registration from the perspective of data fitting. Registration is closely related to data fitting in which it comprises three core interwoven components: model selection, correspondences and constraints, and optimization. Study of these components 1) provides a basis for comparison of the novelties of different techniques, 2) reveals the similarity of rigid and nonrigid registration in terms of problem representations, and 3) shows how overfitting arises in nonrigid registration and the reasons for increasing interest in intrinsic techniques. We further summarize some practical issues of registration which include initializations and evaluations, and discuss some of our own observations, insights and foreseeable research trends.

We present a novel method to integrate multiple 3D scans captured from different viewpoints. Saliency information is used to guide the integration process. The multi-scale saliency of a point is specifically designed to reflect its sensitivity to registration errors. Then scans are partitioned into salient and non-salient regions through an Markov Random Field (MRF) framework where neighbourhood consistency is incorporated to increase the robustness against potential scanning errors. We then develop different schemes to discriminatively integrate points in the two regions. For the points in salient regions which are more sensitive to registration errors, we employ the Iterative Closest Point algorithm to compensate the local registration error and find the correspondences for the integration. For the points in non-salient regions which are less sensitive to registration errors, we integrate them via an efficient and effective point-shifting scheme. A comparative study shows that the proposed method delivers improved surface integration.

We propose a new method for detecting mesh saliency, a reflection of perception-based regional importance for 3D meshes. The basic idea is to incorporate the Conditional Random Field (CRF) framework with a saliency detection process. We first produce a multi-scale representation for a mesh. Then, a CRF is designed to robustly detect salient regions utilising neighbourhood consistency. By inferring the CRF via belief propagation algorithm, we actually make use of the global statistic information in the saliency detection process. Experimental results demonstrate the robustness and the effectiveness of the proposed method.

Various types of video can be captured with fisheye lenses; their wide field of view is particularly suited to surveillance video. However, fisheye lenses introduce distortion, and this changes as objects in the scene move, making fisheye video difficult to interpret. Current still fisheye image correction methods are either limited to small angles of view, or are strongly content dependent, and therefore unsuitable for processing video streams. We present an efficient and robust scheme for fisheye video correction, which minimizes time-varying distortion and preserves salient content in a coherent manner. Our optimization process is controlled by user annotation, and takes into account a wide set of measures addressing different aspects of natural scene appearance. Each is represented as a quadratic term in an energy minimization problem, leading to a closed-form solution via a sparse linear system. We illustrate our method with a range of examples, demonstrating coherent natural-looking video output. The visual quality of individual frames is comparable to those produced by state-of-the-art methods for fisheye still photograph correction.

Image segmentation is a fundamental yet challenging step during image analysis. In this paper we propose a novel method for choosing the number of labels during automatic image segmentation. It minimizes an objective function based on the number of labels, the segmentation errors, and consistency of labels between neighboring pixels. An experimental study on representative data shows encouraging results.

A fast and robust auto-sorting method for image ordering based on Markov Random Fields (MRF) is proposed. We present a specific MRF model for the ordering problem and use pairwise phase correlation for the formulation. The MRF is inferred by a modified belief propagation (BP) method. Experimental results prove that the new method can reorder a disorganised collection of images without human input, prior information or restrictions, as just the first stage of a multi stage mosaicing process, but also provides information that can be used to guide a mosaicing process in order to reduce both local mismatch and global error accumulation.

This paper gives an automatic method for online video stream abstraction, producing a temporally coherent output video stream, in a style with large regions of constant color and highlighted bold edges. Our system includes two novel components. Firstly, to provide coherent and simplified output, we segment frames, and use optical flow to propagate segmentation information from frame to frame; an error control strategy is used to help ensure that the propagated information is reliable. Secondly, to achieve coherent and attractive coloring of the output, we use a color scheme replacement algorithm specifically designed for an online video stream. We demonstrate real-time performance for CIF videos, allowing our approach to be used for live communication and other related applications.

Cellular automata (CA) with given evolution rules have been widely investigated, but the inverse problem of extracting CA rules from observed data is less studied. Current CA rule extraction approaches are both time consuming and inefficient when selecting neighborhoods. We give a novel approach to identifying CA rules from observed data and selecting CA neighborhoods based on the identified CA model. Our identification algorithm uses a model linear in its parameters and gives a unified framework for representing the identification problem for both deterministic and probabilistic CA. Parameters are estimated based on a minimum variance criterion. An incremental procedure is applied during CA identification to select an initial coarse neighborhood. Redundant cells in the neighborhood are then removed based on parameter estimates, and the neighborhood size is determined using the Bayesian information criterion. Experimental results show the effectiveness of our algorithm and that it outperforms other leading CA identification algorithms.

In region machining, neighbouring regions may be close together, but disconnected. Boundary curves may also have unwanted geometric artifacts caused by approximation and discretisation. We present a strategy to improve the topology and geometry of such boundary curves, allowing the generation of better tool paths, and in turn, improved tool wear and surface quality of the machined part. We make such improvements in three steps: firstly, disconnected regions are merged where appropriate, using a method based on morphological operations from image processing. Secondly, boundary segments with undesirable geometric properties are identified and replaced by simpler segments, using a vertex deletion operation. Finally, flaws at a smaller geometric scale are removed, using a curve shortening algorithm. Experimental results are given to illustrate our algorithm.

We present an implicit approach for pair-wise non-rigid registration of moving and deforming objects. Shapes of interest are implicitly embedded in the 3D implicit vector space. In this implicit embedding space, registration is performed using a global-to-local framework. Firstly, a non-linear optimization functional defined on the vector distance function is used to find the global alignment between shapes. Secondly, an incremental cubic B-spline free form deformation is used to recover the non-rigid transformation parameters. Local non-rigid registration is posed in terms of minimising an energy functional, for which we give a closed-form linear system and solve it using an improved iterative Gauss-Seidel method. Our approach can consistently produce smooth and continuous registration fields, and correctly establish dense one-to-one correspondences. It can naturally deal with both open partial and closed shapes, and imperfect models with gaps and noise, through its use of the implicit vector representation. Experimental results on several datasets demonstrate the robustness of the proposed method.

Abstract We present a novel image resizing method which attempts to ensure that important local regions undergo a geometric similarity transformation, and at the same time, to preserve image edge structure. To accomplish this, we define handles to describe both local regions and image edges, and assign a weight for each handle based on an importance map for the source image. Inspired by conformal energy, which is widely used in geometry processing, we construct a novel quadratic distortion energy to measure the shape distortion for each handle. The resizing result is obtained by minimizing the weighted sum of the quadratic distortion energies of all handles. Compared to previous methods, our method allows distortion to be diffused better in all directions, and important image edges are well‐preserved. The method is efficient, and offers a closed form solution.

We consider the problem of computing a parting line for a mold for a complex mesh model, given a parting direction, and the related problem of removing small undercuts, either preexisting, or resulting from the parting line. Existing parting line algorithms are unsuitable for use with complex meshes: the faceted nature of such models leads to a parting line which zig-zags or wanders across the surface undesirably. Our method computes a smooth parting line which runs through a band of triangles whose normals are approximately perpendicular to the parting direction. We generate a skeleton of this triangle band to find its distinct topological cycles, and to decompose it into simple pieces. After selecting paths making a good cycle, we generate a final smooth parting line by iteratively improving the geometry of this cycle. Compliance in the physical material, and/or modifications to eliminate minor undercuts ensure that such a parting line is practically useful.

Gradient mesh vector graphics representation, used in commercial software, is a regular grid with specified position and color, and their gradients, at each grid point. Gradient meshes can compactly represent smoothly changing data, and are typically used for single objects. This paper advances the state of the art for gradient meshes in several significant ways. Firstly, we introduce a topology-preserving gradient mesh representation which allows an arbitrary number of holes . This is important, as objects in images often have holes, either due to occlusion, or their 3D structure. Secondly, our algorithm uses the concept of image manifolds, adapting surface parameterization and fitting techniques to generate the gradient mesh in a fully automatic manner. Existing gradient-mesh algorithms require manual interaction to guide grid construction, and to cut objects with holes into disk-like regions. Our new algorithm is empirically at least 10 times faster than previous approaches. Furthermore, image segmentation can be used with our new algorithm to provide automatic gradient mesh generation for a whole image . Finally, fitting errors can be simply controlled to balance quality with storage.

An algorithm is presented to automatically generate bas-reliefs based on adaptive histogram equalization (AHE), starting from an input height field. A mesh model may alternatively be provided, in which case a height field is first created via orthogonal or perspective projection. The height field is regularly gridded and treated as an image, enabling a modified AHE method to be used to generate a bas-relief with a user-chosen height range. We modify the original image-contrast-enhancement AHE method to use gradient weights also to enhance the shape features of the bas-relief. To effectively compress the height field, we limit the height-dependent scaling factors used to compute relative height variations in the output from height variations in the input; this prevents any height differences from having too great effect. Results of AHE over different neighborhood sizes are averaged to preserve information at different scales in the resulting bas-relief. Compared to previous approaches, the proposed algorithm is simple and yet largely preserves original shape features. Experiments show that our results are, in general, comparable to and in some cases better than the best previously published methods.

We present a system for vectorizing 2D raster format cartoon animations. The output animations are visually flicker free, smaller in file size, and easy to edit. We identify decorative lines separately from colored regions. We use an accurate and semantically meaningful image decomposition algorithm, supporting an arbitrary color model for each region. To ensure temporal coherence in the output, we reconstruct a universal background for all frames and separately extract foreground regions. Simple user-assistance is required to complete the background. Each region and decorative line is vectorized and stored together with their motions from frame to frame. The contributions of this paper are: 1) the new trapped-ball segmentation method, which is fast, supports nonuniformly colored regions, and allows robust region segmentation even in the presence of imperfectly linked region edges, 2) the separate handling of decorative lines as special objects during image decomposition, avoiding results containing multiple short, thin oversegmented regions, and 3) extraction of a single patch-based background for all frames, which provides a basis for consistent, flicker-free animations.

3D mesh models are now widely available for use in various applications. The demand for automatic model analysis and understanding is ever increasing. Mesh segmentation is an important step towards model understanding, and acts as a useful tool for different mesh processing applications, e.g. reverse engineering and modeling by example. We extend a random walk method used previously for image segmentation to give algorithms for both interactive and automatic mesh segmentation. This method is extremely efficient, and scales almost linearly with increasing number of faces. For models of moderate size, interactive performance is achieved with commodity PCs. It is easy-to-implement, robust to noise in the mesh, and yields results suitable for downstream applications for both graphical and engineering models.

This paper discusses noise in range data measured by a Konica Minolta Vivid 910 scanner. Previous papers considering denoising 3D mesh data have often used artificial data comprising Gaussian noise, which is independently distributed at each mesh point. Measurements of an accurately machined, almost planar test surface indicate that real scanner data does not have such properties. An initial characterisation of real scanner noise for this test surface shows that the errors are not quite Gaussian, and more importantly, exhibit significant short range correlation. This analysis yields a simple model for generating noise with similar characteristics. We also examine the effect of two typical mesh denoising algorithms on the real noise present in the test data. The results show that new denoising algorithms are required to effectively remove real scanner noise.

Abstract A novel method is given for content‐aware video resizing, i.e. targeting video to a new resolution (which may involve aspect ratio change) from the original. We precompute a per‐pixel cumulative shrinkability map which takes into account both the importance of each pixel and the need for continuity in the resized result. (If both x and y resizing are required, two separate shrinkability maps are used, otherwise one suffices). A random walk model is used for efficient offline computation of the shrinkability maps. The latter are stored with the video to create a multi‐sized video, which permits arbitrary‐sized new versions of the video to be later very efficiently created in real‐time, e.g. by a video‐on‐demand server supplying video streams to multiple devices with different resolutions. These shrinkability maps are highly compressible, so the resulting multi‐sized videos are typically less than three times the size of the original compressed video. A scaling function operates on the multi‐sized video, to give the new pixel locations in the result, giving a high‐quality content‐aware resized video. Despite the great efficiency and low storage requirements for our method, we produce results of comparable quality to state‐of‐the‐art methods for content‐aware image and video resizing.

In this paper, we consider delayed bidirectional associative memory (BAM) neural networks (NNs) with Lipschitz continuous activation functions. By applying Young's inequality and Hoelder's inequality techniques together with the properties of monotonic continuous functions, global exponential stability criteria are established for BAM NNs with time delays. This is done through the use of a new Lyapunov functional and an M-matrix. The results obtained in this paper extend and improve previous results.

This paper presents a novel skeleton-based method for deforming meshes (using an approximate skeleton, rather than a precise medial axis). The significant difference from previous skeleton-based methods is that the latter use the skeleton to control movement of vertices whereas we use it to control the simplices defining the model. By doing so, errors that occur near joints in other methods can be spread over the whole mesh, using an optimization process, resulting in smooth transitions near joints of the skeleton. By controlling simplices, our method has the advantage that no vertex weights need to be defined on the bones, which is a tedious requirement in previous skeleton-based methods. Our method can also easily be extended to control deformation by moving a few chosen line segments or vertices embedded in the object, rather than a skeleton.

Motivated by the need to detect design intent in approximate boundary representation models, we give an algorithm to detect incomplete symmetries of discrete points, giving the models' potential local symmetries at various automatically detected tolerances. Here, incomplete symmetry is defined as a set of incomplete cycles which are constructed by, e.g., a set of consecutive vertices of an approximately regular polygon, induced by a single isometry. All seven 3D elementary isometries are considered for symmetry detection. Incomplete cycles are first found using a tolerance-controlled point expansion approach. Subsequently, these cycles are clustered for incomplete symmetry detection. The resulting clusters have welldefined, unambiguous approximate symmetries suitable for design intent detection, as demonstrated experimentally.

This paper considers the mold design problem of computing a parting line for a complex mesh model, given a parting direction. Existing parting line algorithms are unsuitable for this case, as local variations in the orientations of the facets of such models lead to a parting line which zig-zags across the surface in an undesirable way. This paper presents a method to compute a smooth parting line which runs through a triangle band composed of triangles whose normals are approximately perpendicular to the parting direction. The skeleton of the triangle band is used to generate a structure representing distinct topological cycles, and to decompose the triangle band into singly-connected surface pieces, giving candidate paths. We choose a set of paths giving a good cycle; the final smooth parting line is then constructed by iteratively improving the quality of this cycle. Compliance in the physical material, or minor modifications to the surface itself, will ensure that such a parting line is appropriate for use.

This paper considers an approach to mesh denoising based on the concept of random walks. The proposed method consists of two stages: a face normal filtering procedure, followed by a vertex position updating procedure which integrates the denoised face normals in a least-squares sense. Face normal filtering is performed by weighted averaging of normals in a neighbourhood. The weights are based on the probability of arriving at a given neighbour after a random walk of a virtual particle starting at a given face of the mesh and moving a fixed number of steps. The probability of a particle stepping from its current face to a given neighboring face is determined by the angle between the two face normals, using a Gaussian distribution whose width is adaptively adjusted to enhance the feature-preserving property of the algorithm. The vertex position updating procedure uses the conjugate gradient algorithm for speed of convergence. Analysis and experiments show that random walks of different step lengths yield similar denoising results. In particular, iterative application of a one-step random walk in a progressive manner effectively preserves detailed features while denoising the mesh very well. We observe that this approach is faster than many other feature-preserving mesh denoising algorithms.

We present a simple and fast mesh denoising method, which can remove noise effectively, while preserving mesh features such as sharp edges and corners. The method consists of two stages. Firstly, noisy face normals are filtered iteratively by weighted averaging of neighboring face normals. Secondly, vertex positions are iteratively updated to agree with the denoised face normals. The weight function used during normal filtering is much simpler than that used in previous similar approaches, being simply a trimmed quadratic. This makes the algorithm both fast and simple to implement. Vertex position updating is based on the integration of surface normals using a least-squares error criterion. Like previous algorithms, we solve the least-squares problem by gradient descent, but whereas previous methods needed user input to determine the iteration step size, we determine it automatically. In addition, we prove the convergence of the vertex position updating approach. Analysis and experiments show the advantages of our proposed method over various earlier surface denoising methods.

Segmenting meshes into natural regions is useful for model understanding and many practical applications. In this paper, we present a novel, automatic algorithm for segmenting meshes into meaningful pieces. Our approach is a clustering-based top-down hierarchical segmentation algorithm. We extend recent work on feature sensitive isotropic remeshing to generate a mesh hierarchy especially suitable for segmentation of large models with regions at multiple scales. Using integral invariants for estimation of local characteristics, our method is robust and efficient. Moreover, statistical quantities can be incorporated, allowing our approach to segment regions with different geometric characteristics or textures.

Sculptural reliefs are widely used in various industries for purposes such as applying brands to packaging and decorating porcelain. In order to easily apply reliefs to CAD models, it is often desirable to reverse-engineer previously designed and manufactured reliefs. 3D scanners can generate triangle meshes from objects with reliefs; however, previous mesh segmentation work has not considered the particular problem of separation of reliefs from background. We consider here the specific case of segmenting a simple relief delimited by a single outer contour, which lies on a smooth, slowly varying background. Generally, such reliefs meet the surrounding surface in a small step, enabling us to devise a specific method for such relief segmentation.We find the boundary between the background and the relief using an adaptive snake. It starts at a simple user-drawn contour, and is driven inwards by a collapsing force until it matches the relief's boundary. Our method is insensitive to the choice of the initial contour. The snake's limiting position is controlled by a feature energy term designed to find a step. A refinement strategy is then used to drive the snake into concavities of the relief contour.We demonstrate operation of our algorithm using real scanned models with different relief contour shapes and triangle meshes with different resolutions.

Abstract Generating soft shadows in real time is difficult. Exact methods (such as ray tracing, and multiple light source simulation) are too slow, while approximate methods often overestimate the umbra regions. In this paper, we introduce a new algorithm based on the shadow map method to quickly and highly accurately render soft shadows produced by a light source. Our method builds inner and outer translucent fins on objects to represent the penumbra area inside and outside hard shadows, respectively. The fins are traced into multilayered light space maps to store illuminance adjustment to shadows. The viewing space illuminance buffer is then calculated using those maps. Finally, by blending illuminance and shading, a scene with highly accurate soft shadow effects is produced. Our method does not suffer from umbra overestimation. Physical relations between light, objects and shadows demonstrate the soundness of our approach.

In this paper, we present an automatic method which can transfer geometric textures from one object to another, and can apply a manually designed geometric texture to a model. Our method is based on geometry images as introduced by Gu et al. The key ideas in this method involve geometric texture extraction, boundary consistent texture synthesis, discretized orientation and scaling, and reconstruction of synthesized geometry. Compared to other methods, our approach is efficient and easy-to-implement, and produces results of high quality.

This paper considers computation of visibility for two-dimensional shapes whose boundaries are C1 continuous curves. We assume we are given a one-parameter family of candidate viewpoints, which may be interior or exterior to the object, and at finite or infinite locations. We consider how to compute whether the whole boundary of the shape is visible from some finite set of viewpoints taken from this family, and if so, how to compute a minimal set of such viewpoints. The viewpoint families we handle include (i) the set of viewing directions from infinity, (ii) viewpoints on a circle located outside the object (for inspection from a turntable), and (iii) viewpoints located on the walls of the shape itself. We compute a structure called a visibility chart, which simultaneously encodes the visible part of the shape's boundary from every view in the family. Using such a visibility chart, finding a minimal set of viewpoints reduces to the set-covering problem over the reals. Practical algorithms are obtained by a discrete sampling of the visibility chart. For exterior visibility problems, a reasonable approach is to compute an almost-optimal solution (in terms of number of viewpoints), which can be done in almost-linear time. For interior visibility problems, or when a more correct solution is required, we solve the general set-covering problem, guaranteeing an optimal solution but taking exponential time.

As part of the goal of automatic creation of B-rep models of engineering objects from freehand sketches, we seek to take a single line drawing (with hidden lines removed), and from it deduce an initial 3D geometric realisation of the visible part of the drawn object. Junction and line labels, and provisional depth coordinates, are key parts of this frontal geometry. Many methods for producing frontal geometry only work correctly for drawings of trihedral objects. However, nontrihedral k-vertices commonly occur in engineering objects. We analyse the performance of a line-labelling method applied to k-vertices, and show why methods ignoring geometric considerations are inadequate. We give a new approach which produces both junction labels and provisional depth coordinates without any prior knowledge. Our results show that even a naive implementation outperforms previous methods.

Abstract Strain fields provide a method of deformation measurement based on physics. Using these as a tool, we can analyze deformation of objects in a measurable way. We have developed a new morphing technique based on strain field interpolation. Shape shaking and squeezing, which often happen when using linear interpolation for morphing, do not arise in our approach. We have also developed a new method to create isomorphic meshes from corresponding objects in two images. Meshes generated by this method have much fewer triangles than other methods, which greatly decreases calculation loads in the morphing process. Copyright © 2004 John Wiley & Sons, Ltd.

Reverse engineering allows the geometric reconstruction of simple mechanical parts. However, the resulting models suffer from inaccuracies caused by errors in measurement and reconstruction so such models do not have the exact congruence, symmetries and other regularities the original designer intended. We wish to impose such regularities in a beautification process. The paper discusses the particular problem of detecting approximate congruence between parts (e.g. a pair of handles) of a reconstructed B-rep model, so that a subsequent step can enforce them exactly. A practical detection algorithm is given for models defined using planes, spheres, cylinders, cones and tori. Analysis of the algorithm and experimental results show that expected congruence are detected reasonably quickly.

The main purpose of this research is to develop methods for automatic identification of biological specimens in digital photographs and drawings held in a database. Incorporation of taxonomic drawings into a visual indexing system has not been attempted to date. Diatoms are a single cell microscopic algae that provide a particularly suitable case study. Identification of diatoms is a challenging task due to the huge number of the species, blurred boundaries between species, and life cycle related shape changes. A novel model based on principal curves representing the life cycle related shape variation of a number of diatom species has been developed. Our model is suitable for reconstruction purposes, allowing us to produce drawings of a variety of diatom shapes, thus providing a link between the photographs and drawings. We present the classification results of photographed and drawn specimens based on the model and compare our results to another recent system for diatom identification. Finally, given a diatom specimen, we are able not only to identify the species it belongs to but also to pinpoint the stage in the life cycle it represents.

Boundary representation models reconstructed from 3D range data suffer from various inaccuracies caused by noise in the data and the model building software. The quality of such models can be improved in a beautification step, which finds geometric regularities approximately present in the model and tries to impose a consistent subset of these regularities on the model. A framework for beautification and numerical methods to select and solve a consistent set of constraints deduced from a set of regularities are presented. For the initial selection of consistent regularities likely to be part of the model's ideal design priorities, and rules indicating simple inconsistencies between the regularities are employed. By adding regularities consecutively to an equation system and trying to solve it by using quasi-Newton optimization methods, inconsistencies and redundancies are detected. The results of experiments are encouraging and show potential for an expansion of the methods based on degree of freedom analysis.

We present a new method for automatic landmark extraction from the contours of biological specimens. Our ultimate goal is to enable automatic identification of biological specimens in photographs and drawings held in a database. We propose to use active appearance models for visual indexing of both photographs and drawings. Automatic landmark extraction will assist us in building the models. We describe the results of using our method on drawings and photographs of examples of diatoms, and present an active shape model built using automatically extracted data.

Boundary representation models reconstructed from 3D range data suffer from various inaccuracies caused by noise in the data and the model building software. The quality of such models can be improved in a beautification step, which finds regular geometric patterns approximately present in the model and imposes a maximal consistent subset of constraints deduced from these patterns on the model. This paper presents analysis methods seeking geometric patterns defined by similarities. Their specific types are derived from a part survey estimating the frequencies of the patterns in simple mechanical components. The methods seek clusters of similar objects which describe properties of faces, loops, edges and vertices, try to find special values representing the clusters, and seek approximate symmetries of the model. Experiments show that the patterns detected appear to be suitable for the subsequent beautification steps.

This paper addresses a common problem in the segmentation of range images. We present methods for the least-squares fitting of spheres, cylinders, cones, and tori to 3D point data, and their application within a segmentation framework. Least-squares fitting of surfaces other than planes, even of simple geometric type, has rarely been studied. Our main application areas of this research are reverse engineering of solid models from depth-maps and automated 3D inspection where reliable extraction of these surfaces is essential. Our fitting method has the particular advantage of being robust in the presence of geometric degeneracy, i.e., as the principal curvatures of the surfaces being fitted decrease, the results returned naturally become closer and closer to those surfaces of "simpler type", i.e., planes, cylinders, cones, or spheres, which best describe the data. Many other methods diverge because, in such cases, various parameters or their combination become infinite.

This paper describes a system which converts a two-dimensional sketch with hidden lines removed of a single polyhedral object into a boundary representation solid model. The system improves on a previous system by Grimstead (1997) by analysing the sketch for symmetry elements and regularities. It uses the results of this analysis to produce a more plausible topological completion of the hidden parts of the object, and to enforce exact constraints on the geometry of the boundary-representation model.

Presents an implementation of forward-looking infrared (FLIR) and laser radar (LADAR) data simulation for use in developing a multi-sensor data-fusion automated target recognition (ATR) system. Through the use of commercial models and software, we can create a highly detailed scene model, which provides a rich data set for later processing. We embed our own modules within this software to extract data from the scene and then present it to the FLIR and LADAR sensor models. These models produce simulated range and temperature readings for objects within the scene. These data are used to create a variety of images to aid in the visualisation of the data and to test our ATR system. Frames from approach sequences show the LADAR and FLIR data in different formats. The simulated data and subsequent images are accurate and rapid to produce, and provide invaluable data resources for testing an ATR system.

We present new deterministic methods that, given two eigenspace models-each representing a set of n-dimensional observations-will: 1) merge the models to yield a representation of the union of the sets and 2) split one model from another to represent the difference between the sets. As this is done, we accurately keep track of the mean. Here, we give a theoretical derivation of the methods, empirical results relating to the efficiency and accuracy of the techniques, and three general applications, including the construction of Gaussian mixture models that are dynamically updateable.

This paper provides two algorithms; one for adding eigenspaces, another for subtracting them, thus allowing for incremental updating and downdat-ing of data models. Importantly, and unlike previous work, we keep an ac-curate track of the mean of the data, which allows our methods to be used in classification applications. The result of adding eigenspaces, each made from a set of data, is an approximation to that which would obtain were the sets of data taken together. Subtracting eigenspaces yields a result approximating that which would obtain were a subset of data used. Using our algorithms it is possible to perform “arithmetic ” on eigenspaces without reference to the orig-inal data. We illustrate the use of our algorithms in three generic applications, including the dynamic construction of Gaussian mixture models. 1

Eigenspace models are a convenientway to represent sets of observations with widespread applications, including classi#cation. In this paper we describe a new constructive method for incrementally adding observations to an eigenspace model. Our contribution is to explicitly account forachange in origin as well as a change in the number of eigenvectors needed in the basis set. No other method wehave seen considers change of origin, yet both are needed if an eigenspace model is to be used for classi#cation purposes. We empirically compare our incremental method with two alternatives from the literature and show our method is the more useful for classi#cation because it computes the smaller eigenspace model representing the observations. 1 Introduction The contribution of this paper is a method for incrementally computing eigenspace models in the context of using them for classi#cation. Eigenspace models are widely used in computer vision. Applications include: face recognition #8# where...

Djinn is an API for solid modelling which is defined in the language of point-sets and is thus independent of any particular modelling data-structure (e.g. boundary representations or CSG trees). In designing this API, several significant and interesting questions have arisen, including: the basic feasibility of the approach; deciding how to support cellular models; providing facilities for navigation without traditional data-structures; addressing the problems of 'tweaks' and blends; ensuring that labels are preserved under geometric operations; permitting regions in which changes to a model have taken place to be identified; coping with approximate models; deciding whether to support variational models; keeping sweeps and transforms within a reasonable domain; and providing facilities to handle the many types of parametric surface. These questions are not all fully answered, but progress continues towards a published interface and C++ language binding.

Abstract Designers need to transfer three‐dimensional objects from their minds via a two‐dimensional interface into a solid modelling system. We propose a system where objects are sketched interactively in two‐dimensions and incrementally line‐labelled as the drawing progresses, as the preliminary stage in constructing a solid model. Once the sketch is complete, the line‐labels are coupled with various inferred constraints to enable us to generate a solid model. In this paper we describe and evaluate a modification to existing line labelling methods to allow them to work incrementally. In this way, the labelling and region information can be built up as the user sketches, rather than all at once at the end of the sketching process, which reduces the delay before the final solid model is built.

A truncation method for computing the slant transform is presented. The slant transform truncation (STT) algorithm uses the divide and conquer principle of hierarchical data structures to factorize coherent image data into sparse subregions. In one dimension with a data array of size N=2/sup n/, the truncation method takes a time between O(N) and O(Nlog/sub 2/N), degenerating to the performance of the fast slant transform (FST) method in its worst case. In two dimensions, for a data array of size N/spl times/N, the one-dimensional truncation method is applied to each row, then to each column of the array, to compute the transform in a time between O(N/sup 2/) and O(N/sup 2/log/sub 2/N). Coherence is a fundamental characteristic of digital images and so the truncation method is superior to the FST method when computing slant transforms of digital images. Experimental results are presented to justify this assertion.>

A technique is described that allows unimodal function optimization methods to be extended to locate all optima of multimodal problems efficiently. We describe an algorithm based on a traditional genetic algorithm (GA). This technique involves iterating the GA but uses knowledge gained during one iteration to avoid re-searching, on subsequent iterations, regions of problem space where solutions have already been found. This gain is achieved by applying a fitness derating function to the raw fitness function, so that fitness values are depressed in the regions of the problem space where solutions have already been found. Consequently, the likelihood of discovering a new solution on each iteration is dramatically increased. The technique may be used with various styles of GAs or with other optimization methods, such as simulated annealing. The effectiveness of the algorithm is demonstrated on a number of multimodal test functions. The technique is at least as fast as fitness sharing methods. It provides an acceleration of between 1 and l0p on a problem with p optima, depending on the value of p and the convergence time complexity.

Transforms and quadtrees are both methods of representing information in an image in terms of the presence of information at differing length scales. This paper presents a mathematical relationship between these two approaches to describing images in the particular case when Walsh transforms are used. Furthermore, both methods have been used for the compression of images for transmission. This paper notes that under certain circumstances, quadtree compression produces identical results to Walsh transform coding, but requires less computational effort to do so. Remarks are also made about the differences between these approaches.

This paper describes a new class of surface patch for use in computational geometry, where fairness is built in at the design stage by using ideas from differential geometry. Principal patches are patches whose sides are lines of curvature, and can be created by making the boundary curves obey two conditions called the frame and position matching equations. It is shown that surface continuity is automatically achieved when composite surfaces are formed. Particular cases are discussed, especially Dupin's cyclide patches based on circular arc sides. Some advantages of Dupin's cyclides over conventional, bicubic patches are described. Finally it is shown how the use of principal patches leads to a natural, geometric need for non -four -sided patches.