Shape representation and classification using the poisson equation

We present a novel approach that allows us to reliably compute many useful properties of a silhouette. Our approach assigns, for every internal point of the silhouette, a value reflecting the mean time required for a random walk beginning at the point to hit the boundaries. This function can be computed by solving Poisson's equation, with the silhouette contours providing boundary conditions. We show how this function can be used to reliably extract various shape properties including part structure and rough skeleton, local orientation and aspect ratio of different parts, and convex and concave sections of the boundaries. In addition to this, we discuss properties of the solution and show how to efficiently compute this solution using multigrid algorithms. We demonstrate the utility of the extracted properties by using them for shape classification and retrieval     

Shape representation using a generalized potential field model

This paper is concerned with efficient derivation of the medial axis transform of a 2D polygonal region. Instead of using the shortest distance to the region border, a potential field model is used for computational efficiency. The region border is assumed to be charged and the valleys of the resulting potential field are used to estimate the axes for the medial axis transform. The potential valleys are found by following the force field, thus, avoiding 2D search. The potential field is computed in closed form using equations of the border segments. The simple Newtonian potential is shown to be inadequate for this purpose. A higher order potential is defined which decays faster with distance than the inverse of distance. It is shown that as the potential order becomes arbitrarily large, the axes approach those computed using the shortest distance to the border. Algorithms are given for the computation of axes, which can run in linear parallel time for part of the axes having initial guesses. Experimental results are presented for a number of examples     

Shape retrieval using triangle-area representation and dynamic space warping

In this paper, we present a shape retrieval method using triangle-area representation for nonrigid shapes with closed contours. The representation utilizes the areas of the triangles formed by the boundary points to measure the convexity/concavity of each point at different scales (or triangle side lengths). This representation is effective in capturing both local and global characteristics of a shape, invariant to translation, rotation, and scaling, and robust against noise and moderate amounts of occlusion. In the matching stage, a dynamic space warping (DSW) algorithm is employed to search efficiently for the optimal (least cost) correspondence between the points of two shapes. Then, a distance is derived based on the optimal correspondence. The performance of our method is demonstrated using four standard tests on two well-known shape databases. The results show the superiority of our method over other recent methods in the literature.     

使用形状变化描述三维模型

针对三维模型检索中的形状特征提取问题,提出利用三维模型自身形状变化信息构造形状特征描述符的方法.首先选择一组等间距互相平行的平面切割三维模型,得到三维模型的切片集合;然后定义相邻切片的 差来描述切片间的形状变化,并通过所有相邻切片间的差值来反映三维模型自身的形状变化,以此作为三维模型的形状特征描述符.该方法与三维模型的旋转、平移无关,同时不依赖于模型的点云分布,并且精简模型三角面片对算法的影响较小.实验结果验证了该方法的有效性.     

Local shape blending using coherent weighted regions

We present a novel local shape blending method that maps a sparse configuration of facial markers captured from an actor onto target models. The advantage of local shape blending methods is that, given a small set of key shapes for each local region, their combination can generate various facial expressions. However, they have the common problem that they use the pre-determined (fixed) regions and compute the combination of local key shapes for each region independently of each other. So, they have a risk of breaking natural correlations between the regions. We present a stochastic method of computing the regions and the blending weight vectors simultaneously. To do so, we formulate local shape blending as a problem of finding an optimal distribution of blending weight vectors of all control points in MAP?CMRF framework.     

Shape approximation using quadtrees

The quadtree representation encodes a 2″ by 2″ binary image as a set of maximal blocks of 1's or 0's whose sizes and positions are powers of 2. With the aid of the quadtree, a hierarchy of approximations to the image can be defined. Several ways of doing this are described. The accuracy of these approximations is empirically evaluated by studying how fast estimates of the first few moments of the image, computed from the approximations, converge to the true values, using a database of 112 airplane silhouettes. Approaches to the problem of fast shape matching using these approximations are also discussed.     

Shape segmentation using relaxation

Relaxation is applied to the segmentation of closed boundary curves of shapes. The ambiguous segmentation of the boundary is represented by a directed graph structure whose nodes represent segments, where two nodes are joined by an arc if the segments are consecutive along the boundary. A probability vector is associated with each node; each component of this vector provides an estimate of the probability that the corresponding segment is a particular part of the object. Relaxation is used to eliminate impossible sequences of parts, or reduce the probabilities of unlikely ones. In experiments involving airplane shapes, this almost always results in a drastic simplification of the graph with only good interpretations surviving. The approach is also extended to include curve linking and gap filling. A chain coded input image is broken into segments based on a measure of local curvature. Gap completions linking pairs of segments are then proposed and represented in a graph structure. A second graph, whose nodes consist of paths in the above graph, is constructed, and the nodes of the second graph are probabilistically classified as various object parts. Relaxation is then applied to increase the probability of mutually supporting classifications, and decrease the probability of unsupported decisions. A modified relaxation process using information about the size, spatial position, and orientation of the object parts yielded a high degree of disambiguation.     

Shape from shading using the facet model

In this paper, the facet model is used in the recovery of surface orientation from single and multiple images. Two methods for determining surface orientation from image shading are presented. The first method works in the single image domain and is formulated as a non-linear optimization problem. Since three-dimensional scene information available in a single image is usually ambiguous, the optimization procedure can result in multiple solutions. The possibility of adding boundary constraints to the optimization process is also investigated. In the second method, additional images are obtained from the same viewing position, but with changing illumination direction. With these additional images, local surface orientation is determined uniquely by a linear optimization procedure. Experimental results of the shape-from-shading methods are also described.     

Solving polynomial systems using no-root elimination blending schemes

Searching for the roots of (piecewise) polynomial systems of equations is a crucial problem in computer-aided design (CAD), and an efficient solution is in strong demand. Subdivision solvers are frequently used to achieve this goal; however, the subdivision process is expensive, and a vast number of subdivisions is to be expected, especially for higher-dimensional systems. Two blending schemes that efficiently reveal domains that cannot contribute by any root, and therefore significantly reduce the number of subdivisions, are proposed. Using a simple linear blend of functions of the given polynomial system, a function is sought after to be no-root contributing, with all control points of its Bernstein–Bézier representation of the same sign. If such a function exists, the domain is purged away from the subdivision process. The applicability is demonstrated on several CAD benchmark problems, namely surface–surface–surface intersection (SSSI) and surface–curve intersection (SCI) problems, computation of the Hausdorff distance of two planar curves, or some kinematic-inspired tasks.     

An interactive data-driven driving simulator using motion blending

Compared to the motion equations the data-driven method can simulate reality from sampling of real motions but real-time interaction between a user and the simulator is problematic. Existing data-driven motion generation methods simply record and replay the motion of the vehicle. Character animation technology enables a user to control motions that are generated by a motion capture database and an appropriate motion control algorithm. We propose a data-driven motion generation method and implement a driving simulator by adapting the method of motion capture. The motion data sampled from a real vehicle are transformed into appropriate data structures called motion blocks, and then a series of motion blocks are saved into the motion database. During simulation, the driving simulator searches for and synthesizes optimal motion blocks from the motion database and generates motion streams that reflect the current simulation conditions and parameterized user demands. We demonstrate the proposed method through experiments with the driving simulator.     

Uncertainty representation using fuzzy measures

We introduce the fuzzy measure and discuss its use as a unifying structure for modeling knowledge about an uncertain variable. We show that a large class of well-established types of uncertainty representations can be modeled within this framework. A view of the Dempster-Shafer (D-S) belief structure as an uncertainty representation corresponding to a set of possible fuzzy measures is discussed. A methodology for generating this set of fuzzy measures from a belief structure is described. A measure of entropy associated with a fuzzy measure is introduced and its manifestation for different fuzzy measures is described. The problem of uncertain decision making for the case in which the uncertainty represented by a fuzzy measure is considered. The Choquet integral is introduced as providing a generalization of the expected value to this environment.     

Odor classification using similarity-based representation

In this paper a new approach to odor classification is presented, founded on the similarity-based representation paradigm. The proposed approach builds a new representation space, called similarity space, in which each object is not represented by features, but by its similarities with respect to other objects in the data set. The classification step is performed using support vector machines, a technique introduced in the statistical learning theory context. One of the major drawbacks of the similarity-based representation paradigm is the dimensionality of the similarity space: a method for addressing this problem has been introduced in this paper, based on a notion of the unsupervised classification (clustering) theory, namely the medoid concept. The approach outperforms standard features-based representations on tests regarding data gathered from a chemical sensors array electronic nose.     

基于结式的曲面拼接与三维造型

针对很多几何造型是带有约束条件的曲面拼接问题,在线性连续同伦的基础上提出了利用非线性同伦连续计算拼接曲面以进行三维造型的方法。首先,根据得到的截面(切片)的位置及其曲线方程确定插值点并得到插值多项式;其次,将此插值多项式作为非线性连续同伦映射函数并分别代入主曲面和辅助曲面的多项式方程得到过渡曲面的方程;然后,仅将插值变元作为变元而主、辅助曲面方程的变元作为参数,利用Sylvester结式消去过渡方程中的变元得到关于主曲面的拼接方程即造型曲面。利用该方法能实现带有控制点的曲面造型以及多曲面约束的几何造型,而且它可以确定造型过程中的中间形状及中间形状的位置,从而更加具有实用性。     

Rendering hair using pixel blending and shadow buffers

A technique is described for adding natural-looking hair to standard rendering algorithms. Using an explicit hair model, in which each individual hair is represented by a three-dimensional curve, the technique uses pixel blending combined with Z-buffer and shadow buffer information from the scene to yield a final anti-aliased image with soft shadows. Although developed for rendering human hair, this technique can also be used to render any model consisting of long filaments of sub-pixel width. The technique can be adapted to any rendering method that outputs Z-buffer and shadow buffer information and is amenable to hardware implementation.     

Shape indexing using self-organizing maps

In this paper, we propose a novel approach to generate the topology-preserving mapping of structural shapes using self-organizing maps (SOMs). The structural information of the geometrical shapes is captured by relational attribute vectors. These vectors are quantised using an SOM. Using this SOM, a histogram is generated for every shape. These histograms are treated as inputs to train another SOM which yields a topology-preserving mapping of the geometric shapes. By appropriately choosing the relational vectors, it is possible to generate a mapping that is invariant to some chosen transformations, such as rotation, translation, scale, affine, or perspective transformations. Experimental results using trademark objects are presented to demonstrate the performance of the proposed methodology.     

压缩感知形状检测

压缩感知以随机投影的形式利用较少的非传统采样,重构稀疏的或可压缩的信号。Hough变换通常用于检测图像中的直线和其他参数化形状。提出利用Hough变换域的稀疏性,用CS寻找图像中的参数化形状的方法。进行了用基于CS的方法检测噪声图像中的直线和圆的实验。     

Shape recognition using fractal geometry

Within this paper fractal transformations are presented as a powerful new shape recognition technique. The motivation behind using fractal transformations is to develop a high speed shape recognition technique which will be scale invariant. A review is given of the most popular existing shape recognition techniques. There then follows a full mathematical analysis of the new technique together with a proof of the authors Fractal Invariance Theorem, the new theorem at the centre of the recognition technique. Through the mathematical analysis it becomes apparent that the fractal recognition technique possesses the remarkable property that it is able to distinguish between similar objects. Details are then given of the practical implementation of the technique together with an algorithm for making the technique rotationally invariant. The technique is then applied to a selection of real world objects and a comparison made with the popular moment invariants technique. This shows that the fractal technique is faster than the technique of moment invariants, and also requires less initial information to be effective. Finally conclusions are drawn and further work detailed.     

Shape matching using relaxation techniques

The problem of finding approximate matches of pieces of shapes to parts of larger shapes is investigated. The shapes are represented by polygonal approximations. Initially, figures of merit are assigned to the matches between pairs of angles on the two shapes. Relaxation methods are then used to find acceptable combinations of these matches. This approach was tested on a data base consisting of digitized coastlines in various map projections. In nearly all cases, all matches except the correct one were eliminated by the relaxation processes.