Efficient Collision Detection for Moving Ellipsoids Using Separating Planes

We present a simple, accurate and efficient algorithm for collision detection among moving ellipsoids. Its efficiency is attributed to two results: (i) a simple algebraic test for the separation of two ellipsoids, and (ii) an efficient method for constructing a separating plane between two disjoint ellipsoids. Inter-frame coherence is exploited by using the separating plane to reduce collision detection to simpler subproblems of testing for collision between the plane and each of the ellipsoids. Compared with previous algorithms (such as the GJK method) which employ polygonal approximation of ellipsoids, our algorithm demonstrates comparable computing speed and much higher accuracy.     

An algebraic approach to continuous collision detection for ellipsoids

We present algebraic expressions for characterizing three configurations formed by two ellipsoids in R³ that are relevant to collision detection: separation, external touching and overlapping. These conditions are given in terms of explicit formulae expressed by the subresultant sequence of the characteristic polynomial of the two ellipsoids and its derivative. For any two ellipsoids, the signs of these formulae can easily be evaluated to classify their configuration. Furthermore, based on these algebraic conditions, an efficient method is developed for continuous collision detection of two moving ellipsoids under arbitrary motions.     

Parallel collision detection of ellipsoids with applications in large scale multibody dynamics

This contribution describes a parallel approach for determining the collision state of a large collection of ellipsoids. Collision detection is required in granular dynamics simulation where it can combine with a differential variational inequality solver or discrete element method to approximate the time evolution of a collection of rigid bodies interacting through frictional contact. The approach proposed is structured on three levels. At the lowest level, the collision information associated with two colliding ellipsoids is obtained as the solution of a two-variable unconstrained optimization problem for which first and second order sensitivity information is derived analytically. Although this optimization approach suffices to resolve the collision problem between any two arbitrary ellipsoids, a less versatile but more efficient approach precedes it to gauge whether two ellipsoids are actually in contact and require the more costly optimization approach. This intermediate level draws on the analytical solution of a 3rd order polynomial obtained from the characteristic equation of two arbitrary ellipsoids. Finally, this intermediate level is invoked by the outer level only when a 3D spatial binning algorithm indicates that two ellipsoids share the same bin (box) and therefore could potentially collide. This multi-level approach is implemented in parallel and when executed on a ubiquitous Graphics Processing Unit (GPU) card scales linearly and yields a two orders of magnitude speedup over a similar algorithm executed on the Central Processing Unit (CPU). The GPU-based ellipsoid contact detection algorithm yields a 14-fold speedup over a CPU-based sphere contact detection algorithm implemented in the third party open source Bullet Physics Library (BPL). The proposed methodology provides the efficiency demanded by granular dynamics applications, which routinely handle scenarios with millions of collision events.     

基于椭球模型的无线传感器网络的局部离群点检测

针对现有的无线传感器网络(WSNs)的局部离群点检测算法由于存在未考虑监测环境的异质性而造成邻域划分不准确、检测精度低的问题,提出适用于异质监测环境的基于椭球模型的无线传感器网络的局部离群点检测算法.算法用椭球模型刻画数据分布,节点间只传输模型参数,用椭球参数式方程计算椭球间的相异度;将数据分布的不一致性引入到邻域划分的过程中,最终利用传感数据的时空关联性来确定局部离群点.实验结果表明,提出的算法具有通信量低、检测精度高和误检率低的优点.     

基于空间分割与椭球包围盒的碰撞检测算法

为提高复杂环境下多物体碰撞检测的效率,提出了一种基于均匀网格分割与椭球包围盒的并行碰撞检测算法。该算法首先用均匀网格分割法来确定相邻物体,然后用紧密性较好的椭球包围盒层次树依次把它们包围,并利用基于线程池的多任务并行处理技术实现了并行化。为降低椭球相交测试的复杂度,先预测了椭球间的相交情况,再将三维椭球降维成二维椭圆,从而整体提高了算法的效率。通过实验数据表明,相对于其他算法,该算法具有较好的性能。     

Motion Blur for EWA Surface Splatting

This paper presents a novel framework for elliptical weighted average (EWA) surface splatting with time‐varying scenes. We extend the theoretical basis of the original framework by replacing the 2D surface reconstruction filters by 3D kernels which unify the spatial and temporal component of moving objects. Based on the newly derived mathematical framework we introduce a rendering algorithm that supports the generation of high‐quality motion blur for point‐based objects using a piecewise linear approximation of the motion. The rendering algorithm applies ellipsoids as rendering primitives which are constructed by extending planar EWA surface splats into the temporal dimension along the instantaneous motion vector. Finally, we present an implementation of the proposed rendering algorithm with approximated occlusion handling using advanced features of modern GPUs and show its capability of producing motion‐blurred result images at interactive frame rates.     

Continuous Collision Detection for Two Moving Elliptic Disks

Collision detection and avoidance are important in robotics. Compared with commonly used circular disks, elliptic disks provide a more compact shape representation for robots or other vehicles confined to move in the plane. Furthermore, elliptic disks allow a simpler analytic representation than rectangular boxes, which makes it easier to perform continuous collision detection (CCD). We shall present a fast and accurate method for CCD between two moving elliptic disks, which avoids any need to sample the time domain of the motion, thus avoiding the possibility of missing collisions between time samples. Based on some new algebraic conditions on the separation of two ellipses, we reduce collision detection for two moving ellipses to the problem of detecting real roots of a univariate equation, which is the discriminant of the characteristic polynomial of the two ellipses. Several techniques are investigated for robust and accurate processing of this univariate equation for two classes of commonly used motions: planar cycloidal motions and planar rational motions. Experimental results demonstrate the efficiency, accuracy, and robustness of our method.     

Adaptive WENO Methods Based on Radial Basis Function Reconstruction

We explore the use of radial basis functions (RBF) in the weighted essentially non-oscillatory (WENO) reconstruction process used to solve hyperbolic conservation laws, resulting in a numerical method of arbitrarily high order to solve problems with discontinuous solutions. Thanks to the mesh-less property of the RBFs, the method is suitable for non-uniform grids and mesh adaptation. We focus on multiquadric radial basis functions and propose a simple strategy to choose the shape parameter to control the balance between achievable accuracy and the numerical stability. We also develop an original smoothness indicator which is independent of the RBF for the WENO reconstruction step. Moreover, we introduce type I and type II RBF-WENO methods by computing specific linear weights. The RBF-WENO method is used to solve linear and nonlinear problems for both scalar and systems of conservation laws, including Burgers equation, the Buckley–Leverett equation, and the Euler equations. Numerical results confirm the performance of the proposed method. We finally consider an effective conservative adaptive algorithm that captures moving shocks and rapidly varying solutions well. Numerical results on moving grids are presented for both Burgers equation and the more complex Euler equations.     

基于改进高斯核度量和KPCA的数据聚类新方法

大多数超椭球聚类（hyper-ellipsoidal clustering,HEC）算法都使用马氏距离作为距离度量,已经证明在该条件下划分聚类的代价函数是常量,导致HEC无法实现椭球聚类.本文说明了使用改进高斯核的HEC算法可以解释为寻找体积和密度都紧凑的椭球分簇,并提出了一种实用HEC算法-K-HEC,该算法能够有效地处理椭球形、不同大小和不同密度的分簇.为实现更复杂形状数据集的聚类,使用定义在核特征空间的椭球来改进K-HEC算法的能力,提出了EK-HEC算法.仿真实验证明所提出算法在聚类结果和性能上均优于K-means算法、模糊C-means算法、GMM-EM算法和基于最小体积椭球（minimum-volume ellipsoids,MVE）的马氏HEC算法,从而证明了本文算法的可行性和有效性.     

A contribution to the calculation of the contact stress distribution between two elastic bodies of revolution with non-elliptical contact area

A numerical method is presented for calculating the contact area and the normal stress distribution between two elastic bodies of revolution with parallel axes. For the discretization of the Fredhom integral equation the contact area is divided into strips perpendicular to the axes of revolution. The stress distribution in each strip is assumed to be semi-elliptical in the strip direction and constant in the other direction. The contact area is calculated iteratively by satisfying the contact condition and the stress condition. In addition for a given total normal force an additional iteration is required to improve the value obtained for the rigid-body approach. The contact area and the stress distribution between two ellipsoids are compared with Hertzian solutions. To investigate the non-Hertzian contact problem a number of cases of wheel-rail contact are considered.     

改进的高效Camshift跟踪算法

Camshift是一种应用颜色信息的跟踪算法,它对做加速度的运动物体跟踪效果不够稳定和强壮,从准确预测目标位置及缩小目标搜索范围入手对Camshift算法进行了改进。该算法使用运动目标加速度运动位移方程预测下一时刻目标可能出现的位置,使用预测位置误差方程估计运动目标搜索范围,并使用IIR滤波器对目标运动速度、加速度等参数自适应地修正。实验证明,改进的Camshift有效地克服了Camshift算法自身的缺陷,即使运动目标做加速运动时,也可准确地预测运动目标的位置,缩小目标搜索范围,进而提高目标跟踪速度。     

A fast algorithm for level set-like active contours

This paper describes a fast algorithm for topology independent tracking of moving interfaces under curvature- and velocity field-dependent speed laws. This is usually done in the level set framework using the narrow-band algorithm, which accurately solves the level set equation but is too slow to use in real-time or near real-time image segmentation applications. In this paper we introduce a fast algorithm for tracking moving interfaces in a level set-like manner. The algorithm relies on two key components: First, it tracks the interface by scheduling point-wise propagation events using a heap sorted queue. Second, the local geometric properties of the interface are defined so that they can be efficiently updated in an incremental manner and so that they do not require the presence of the signed distance function. Finally examples are given that indicate that the algorithm is fast and accurate enough for near real-time segmentation applications.     

Clustering ellipses for anomaly detection

Comparing, clustering and merging ellipsoids are problems that arise in various applications, e.g., anomaly detection in wireless sensor networks and motif-based patterned fabrics. We develop a theory underlying three measures of similarity that can be used to find groups of similar ellipsoids in p-space. Clusters of ellipsoids are suggested by dark blocks along the diagonal of a reordered dissimilarity image (RDI). The RDI is built with the recursive iVAT algorithm using any of the three (dis) similarity measures as input and performs two functions: (i) it is used to visually assess and estimate the number of possible clusters in the data; and (ii) it offers a means for comparing the three similarity measures. Finally, we apply the single linkage and CLODD clustering algorithms to three two-dimensional data sets using each of the three dissimilarity matrices as input. Two data sets are synthetic, and the third is a set of real WSN data that has one known second order node anomaly. We conclude that focal distance is the best measure of elliptical similarity, iVAT images are a reliable basis for estimating cluster structures in sets of ellipsoids, and single linkage can successfully extract the indicated clusters.     

基于背景重构的运动目标检测算法研究与应用

对视频序列中的运动目标检测方法进行了研究,提出了一种基于背景重构的运动目标检测算法。通过自学习方法建立视频图像的高斯模型,构造初始背景图像;运用差分算法,得到运动目标,并对背景图像进行了重构、更新,得到实时背景图像。该方法在有运动目标存在的情况下进行实时建模,实用价值高。     

Perspective silhouette of a general swept volume

We present an efficient and robust algorithm for computing the perspective silhouette of the boundary of a general swept volume. We also construct the topology of connected components of the silhouette. At each instant t, a three-dimensional object moving along a trajectory touches the envelope surface of its swept volume along a characteristic curve K^t. The same instance of the moving object has a silhouette curve L^t on its own boundary. The intersection K^t∩L^t contributes to the silhouette of the general swept volume. We reformulate this problem as a system of two polynomial equations in three variables. The connected components of the resulting silhouette curves are constructed by detecting the instances where the two curves K^t and L^t intersect each other tangentially on the surface of the moving object. We also consider a general case where the eye position changes while moving along a predefined path. The problem is reformulated as a system of two polynomial equations in four variables, where the zero-set is a two-manifold. By analyzing the topology of the zero-set, we achieve an efficient algorithm for generating a continuous animation of perspective silhouettes of a general swept volume.     

一种基于RANSAC 框架的椭球提取算法

面向点云数据,提出一种椭球的检测和提取算法。该算法采用随机采样一 致性（RANSAC）框架,通过多次随机采样点云模型,建立多个能够生成椭球体的最小点集, 对每个最小点集计算椭球参数,经过验证后建立椭球候选集合,利用分数函数评价各候选, 筛选出最佳提取椭球。实验结果表明：对于人工合成和扫描仪获取的点云数据,该算法稳定 可靠,可有效地提取出正确的椭球。     

线性时滞系统的相对稳定性分析方法

实际控制过程中,时滞的引入常常导致系统性能的下降,也使得系统的稳定性分析变得困难。从一类具有时滞项的线性时不变( LTI) 系统的特征根求解出发,研究了系统的稳定性分析问题。复平面上系统特征根的位置不仅决定了系统的绝对稳定性,还决定系统的相对稳定性-瞬态性能。由于时滞的引入,系统特征方程变成超越方程,其解的数量为无穷。并提出一种从超越方程实部和虚部系数中提取出双向量并结合二维向量旋转的解决方法,可以准确简洁地求出超越方程在复平面上指定区域边界上的根。最后给出仿真实例表明了算法的正确性和有效性。     

Obstacle Collision Detection Using Best Ellipsoid Fit

This paper describes a method for estimating the distance between a robot and its surrounding environment using best ellipsoid fit. The method consists of the following two stages. First we approximate the detailed geometry of the robot and its environment by minimum-volume enclosing ellipsoids. The computation of these ellipsoids is a convex optimization problem, for which efficient algorithms are known. Then we compute a conservative distance estimate using an important but little known formula for the distance of a point from and n-dimensional ellipse. The computation of the distance estimate (and its gradient vector) is shown to be an eigenvalue problem, whose solution can be rapidly found using standard techniques. We also present an incremental version of the distance computation, which takes place along a continuous trajectory taken by the robot. We have implemented the proposed approach and present some preliminary results.     

Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization

Many real-life optimization problems often face an increased rank of nonsmoothness (many local minima) which could prevent a search algorithm from moving toward the global solution. Evolution-based algorithms try to deal with this issue. The algorithm proposed in this paper is called GAAPI and is a hybridization between two optimization techniques: a special class of ant colony optimization for continuous domains entitled API and a genetic algorithm (GA). The algorithm adopts the downhill behavior of API (a key characteristic of optimization algorithms) and the good spreading in the solution space of the GA. A probabilistic approach and an empirical comparison study are presented to prove the convergence of the proposed method in solving different classes of complex global continuous optimization problems. Numerical results are reported and compared to the existing results in the literature to validate the feasibility and the effectiveness of the proposed method. The proposed algorithm is shown to be effective and efficient for most of the test functions.     

基于Road R-tree的城市路网索引结构研究

在RR-tree(Road R-tree)索引结构下,基于Segment追踪技术的静态道路网里实现两种优化的方法:LSC算法和ASC算法,优化后的道路网,更新频率有一定程度的下降,更新的效率也符合RR-tree索引结构特点,达到了降低道路网中客户端(移动车辆)与服务器端(中心站)更新代价的目的.