Display of profiled sweep objects

A class of free-form solids called profiled sweep objects is defined by four parametric curves: a 2D contour (cross-section), a 3D trajectory (spine), and two profile curves, which control the scaling of the contour as it moves along the trajectory. Subclasses of this are profiled prisms, which have a linear trajectory, and profiled generalized cylinders, which have an arbitrary 3D trajectory. First an exact definition of profiled sweep object, is presented and their relation with common sweep objects is described. Then a method is given for the construction of planar approximations of these objects that can be used for fast display generation. Finally, ray-tracing algorithms are given that directly use the exact definition for high-quality display.     

Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes

We present a novel technique for the efficient boundary evaluation of sweep operations applied to objects in polygonal boundary representation. These sweep operations include Minkowski addition, offsetting, and sweeping along a discrete rigid motion trajectory. Many previous methods focus on the construction of a polygonal superset (containing self‐intersections and spurious internal geometry) of the boundary of the volumes which are swept. Only few are able to determine a clean representation of the actual boundary, most of them in a discrete volumetric setting. We unify such superset constructions into a succinct common formulation and present a technique for the robust extraction of a polygonal mesh representing the outer boundary, i.e. it makes no general position assumptions and always yields a manifold, watertight mesh. It is exact for Minkowski sums and approximates swept volumes polygonally. By using plane‐based geometry in conjunction with hierarchical arrangement computations we avoid the necessity of arbitrary precision arithmetics and extensive special case handling. By restricting operations to regions containing pieces of the boundary, we significantly enhance the performance of the algorithm.     

Classifying points for sweeping solids

Many diverse engineering problems can be modeled with solid sweeping in a conceptually simple and intuitive way, and sweeps are considered to be one of the basic representation schemes in solid modeling. However, many properties of sweeps as well as their “informational completeness” are not well understood, which is the primary reason why computational support for solid sweeping remains scarce. We propose a generic point membership classification (PMC) for sweeping solids of arbitrary complexity moving according to one parameter affine motions. The only restrictive assumption that we make in this paper is that the initial and final configurations of the moving object do not intersect during the sweep. Our PMC test is defined in terms of inverted trajectory tests against the original geometric representation of the generator object, which implies that this test can be implemented in any geometric representation that supports curve-solid intersections. Importantly, this PMC test provides complete geometric information about the set swept by 3-dimensional objects in general motions. At the same time, it establishes the foundations for developing a new generation of computational tools for sweep boundary evaluation and trimming, as well as a number of practical applications such as shape synthesis, contact analysis and path planning.     

A framework for automatic landmark identification using a newmethod of nonrigid correspondence

A framework for automatic landmark identification is presented based on an algorithm for corresponding the boundaries of two shapes. The auto-landmarking framework employs a binary tree of corresponded pairs of shapes to generate landmarks automatically on each of a set of example shapes. The landmarks are used to train statistical shape models, known as point distribution models. The correspondence algorithm locates a matching pair of sparse polygonal approximations, one for each of a pair of boundaries by minimizing a cost function, using a greedy algorithm. The cost function expresses the dissimilarity in both the shape and representation error (with respect to the defining boundary) of the sparse polygons. Results are presented for three classes of shape which exhibit various types of nonrigid deformation     

USSCD：一个基于均匀空间分割的快速碰撞检测算法

对于存在大量运动物体的虚拟环境，碰撞检测往往成为影响系统计算效率的瓶颈，为提高多体碰撞检测的效率，提出了一个基于均匀空间分割的快速多体碰撞检测算法——USSCD，该算法首先将物体空间均匀分割成一系列单元格，然后在每个单元格，通过基于AVL排序的扫描排除法进行碰撞检测，同时依据物体的分布密度，提出了一个计算单元格尺寸的优化方法，通过一系列实验，测试了USSCD算法的性能，并与I-COLLIDE算法进行比较，实验结果表明，在均匀分布条件下，当物体数量较大时，USSCD的效率高于I-COLLIDE算法，而且，USSCD算法的效率基本不受物体运动相关性的影响。     

A comparison of sampling strategies for computing general sweeps

Sweeping moving objects has become one of the basic geometric operations used in engineering design, analysis and physical simulation. Despite its relevance, computing the boundary of the set swept by a non-polyhedral moving object is largely an open problem due to well-known theoretical and computational difficulties of the envelopes.We have recently introduced a generic point membership classification (PMC) test for general solid sweeping. Importantly, this PMC test provides complete geometric information about the set swept by the moving object, including the ability to compute the self-intersections of the sweep itself. In this paper, we compare two recursive strategies for sampling points of the space in which the object moves, and show that the sampling based on a fast marching cubes algorithm possesses the best combination of features in terms of performance and accuracy for the boundary evaluation of general sweeps. Furthermore, we show that the PMC test can be used as the foundation of a generic sweep boundary evaluator in conjunction with efficient space sampling strategies for solids of arbitrary complexity undergoing affine motions.     

Radiosity redistribution for dynamic environments

The radiosity algorithm is extended to dynamic environments, providing global-illumination simulations to scenes that are modified interactively. The illumination effects introduced by a change in position, shape, or attributes of any object in the scene are computed very rapidly by redistributing the energy already exchanged between objects. Corrections are made by shooting positive and negative energy, accounting for increased illumination and the creation of shadows. Object coherence is used to minimize computation, and progressive-refinement techniques are used to accelerate convergence. The extended algorithm yields excellent approximations to the exact solutions at interactive speeds     

Polygonal space carving with geometric anti-aliasing

This paper proposes an algorithm that solves the shape recovery problem from N arbitrary images. By introducing a polygonal carving technique, the proposed algorithm can reconstruct the image-consistent polygonal shape that is patched by input images. This algorithm eliminates the invalid vertices and polygons from the initial polygonal grid space according to the color variance that represents their image consistency. The carved shape is refined by moving the outlier vertices on the boundary of each image. The final reconstructed shape faithfully accounts for the input images, and its textured appearance reflects the similar color property of the target object.     

Moving shadow detection and removal for traffic sequences

Segmentation of moving objects in a video sequence is a basic task for application of computer vision. However, shadows extracted along with the objects can result in large errors in object localization and recognition. In this paper, we propose a method of moving shadow detection based on edge information, which can effectively detect the cast shadow of a moving vehicle in a traffic scene. Having confirmed shadows existing in a figure, we execute the shadow removal algorithm proposed in this paper to segment the shadow from the foreground. The shadow eliminating algorithm removes the boundary of the cast shadow and preserves object edges firstly; secondly, it reconstructs coarse object shapes based on the edge information of objects; and finally, it extracts the cast shadow by subtracting the moving object from the change detection mask and performs further processing. The proposed method has been further tested on images taken under different shadow orientations, vehicle colors and vehicle sizes, and the results have revealed that shadows can be successfully eliminated and thus good video segmentation can be obtained.     

Shape estimation of transparent objects by using inverse polarization ray tracing

Few methods have been proposed to measure three-dimensional shapes of transparent objects such as those made of glass and acrylic. In this paper, we propose a novel method for estimating the surface shapes of transparent objects by analyzing the polarization state of the light. Existing methods do not fully consider the reflection, refraction, and transmission of the light occurring inside a transparent object. We employ a polarization raytracing method to compute both the path of the light and its polarization state. Polarization raytracing is a combination of conventional raytracing, which calculates the trajectory of light rays, and Mueller calculus, which calculates the polarization state of the light. First, we set an initial value of the shape of the transparent object. Then, by changing the shape, the method minimizes the difference between the input polarization data and the rendered polarization data calculated by polarization raytracing. Finally, after the iterative computation is converged, the shape of the object is obtained. We also evaluate the method by measuring some real transparent objects.     

基于大数据分析的移动对象轨迹预测方法

对移动对象的轨迹预测将在移动目标跟踪识别中具有较好的应用价值。移动对象轨迹预测的基础是移动目标运动参量的采集和估计,移动目标的运动参量信息特征规模较大,传统的单分量时间序列分析方法难以实现准确的参量估计和轨迹预测。提出一种基于大数据多传感信息融合跟踪的移动对象轨迹预测算法。首先进行移动目标对象进行轨迹跟踪的控制对象描述和约束参量分析,对轨迹预测的大规模运动参量信息进行信息融合和自正整定性控制,通过大数据分析方法实现对移动对象运动参量的准确估计和检测,由此指导移动对象轨迹的准确预测,提高预测精度。仿真结果表明,采用该算法进行移动对象的运动参量估计和轨迹预测的精度较高,自适应性能较强,稳健性较好,相关的指标性能优于传统方法。     

复杂障碍空间中基于移动对象运动规律的不确定轨迹预测

现有移动对象的轨迹预测大部分是针对路网空间,然而在实际地理环境中往往存在障碍物,移动对象的运动基本在障碍空间中进行。近年来,已有较多关于路网空间中移动对象轨迹预测的研究以及障碍空间中障碍范围查询、最近邻查询等的研究,但是目前尚没有障碍空间中移动对象不确定轨迹预测的相关研究。为此,提出障碍空间中基于移动对象运动规律的不确定轨迹预测方法。首先,利用障碍物之间的区域关系对障碍空间进行剪枝;其次,提出障碍空间期望距离概念,对障碍空间的轨迹数据进行轨迹聚类,从而挖掘移动对象的热点区域;然后,根据各热点区域间的障碍距离和历史访问习惯得到转移的综合概率,提出基于移动对象运动规律的轨迹预测算法;最后,通过实验验证了算法的准确性和高效性。     

Real Time Fitting of Hand-Sketched Pressure Brushstrokes

A method is described for fitting the outline of hand-sketched pressure brushstrokes with Bézier curves. It combines the brush-trajectory model, in which a stroke is generated by dragging a brush along a given trajectory, with a fast curve fitting algorithm. The method has been implemented for a vector-based drawing program in which the user draws with a cordless pressure-sensitive stylus on a digitizing tablet. From the trajectory followed by the stylus, its associated pressure data, and a specified brush, a stroke of variable width is computed and displayed in real time. First, the digitized trajectory is fitted, thus removing noise. Then, from polygonal approximations of the fitted trajectory and the brush outline, a polygonal approximation of the stroke outline is computed. Working with polygonal approximations reduces computations to simple geometric operations and greatly simplifies the treatment of dynamic, pressure-controlled brushes. Last, the polygonal approximation of the stroke outline is fitted. The result is a closed piecewise Bézier curve approximating the brushstroke outline to within an arbitrary error tolerance. Several examples of hand-sketched drawings realized with this method are presented.     

基于最小边界扇形的移动对象轨迹实时化简算法

为了对全球定位系统(GPS)设备采集到的移动对象原始轨迹数据进行简化,提高轨迹数据的使用效率,降低移动终端的通信代价和计算开销,提出了一种基于最小边界扇形(MBS)的移动对象轨迹实时化简算法。该算法不同于用一条折线来近似原始轨迹的方法,它利用扇形预测范围来估计、简化原始轨迹,在角度和距离两个层面上对简化误差进行控制。提出了新的误差度量方法--基于等极径的误差度量方法,并讨论了GPS定位误差对简化算法的影响。实验结果表明,所提算法的简化轨迹高效、稳定,所得到的简化轨迹与原始轨迹之间误差较小(不超过误差阈值的20%),对GPS定位误差有较好的容错能力。     

Qualitative Geometry for Shape Recognition

We propose an algorithm providing an abstract representation of any polygonal object O in terms of spheres. The result is a graph-based skeleton capturing the general shape of O and its inner structure (respective positions of convex parts and their thickness). We define a first-order logic language expressing in a qualitative way the needed notions (distance, size and angle). Last, we propose methods to compare shapes using this graph-based skeleton of objects.     

改进的运动目标检测算法及其实现

在智能视频运动目标检测中,带掩膜的背景差方法存在会出现鬼影目标和计算复杂度大等不足。为此,提出一种改进算法,利用相关矩阵判别法去除鬼影目标,同时增加对光照变化的处理,使算法快速适应光照变化。将耗时的浮点运算转化为整型运算。变换后的算法可同时适应浮点和定点处理器,更具有通用性。在DM642嵌入式系统上进行实现,结果表明,该算法速度快、检测准确率高,满足实时性要求。     

A new algorithm for dominant points detection and polygonization of digital curves

A new algorithm for detecting dominant points and polygonal approximation of digitized closed curves is presented. It uses an optimal criterion for determining the region-of-support of each boundary point, and a new mechanism for selecting the dominant points. The algorithm does not require an input parameter, and can handle shapes that contain features of multiple sizes efficiently. In addition, the approximating polygon preserves the symmetry of the shape.     

BSP-fields: An exact representation of polygonal objects by differentiable scalar fields based on binary space partitioning

The problem considered in this work is to find a dimension independent algorithm for the generation of signed scalar fields exactly representing polygonal objects and satisfying the following requirements: the defining real function takes zero value exactly at the polygonal object boundary; no extra zero-value isosurfaces should be generated; C¹ continuity of the function in the entire domain. The proposed algorithms are based on the binary space partitioning (BSP) of the object by the planes passing through the polygonal faces and are independent of the object genus, the number of disjoint components, and holes in the initial polygonal mesh. Several extensions to the basic algorithm are proposed to satisfy the selected optimization criteria. The generated BSP-fields allow for applying techniques of the function-based modeling to already existing legacy objects from CAD and computer animation areas, which is illustrated by several examples.     

Planar shape matching based on binary tree shape representation

In this paper we suggest a new way of representing planar two-dimensional shapes and a shape matching method which utilizes the new representation. Through merging of the neighboring boundary runs, a shape can be partitioned into a set of triangles. These triangles are inherently connected according to a binary tree structure. Here we use the binary tree with the triangles as its nodes to represent the shape. This representation is found to be insensitive to shape translation, rotation, scaling and skewing changes due to viewer's location changes (or the object's pose changes). Furthermore, the representation is of multiresolution.

In shape matching we compare the two trees representing two given shapes node by node according to the breadth-first tree traversing sequence. The comparison is done from top of the tree and moving downward, which means that we first compare the lower resolution approximations of the two shapes. If the two approximations are different, the comparison stops. Otherwise, it goes on and compares the finer details of the two shapes. Only when the two shapes are very similar, will the two corresponding trees be compared entirely. Thus, the matching algorithm utilizes the multiresolution characteristic of the tree representation and appears to be very efficient.