Collision identification between convex polyhedra using neuralnetworks

Collision identification between convex polyhedra is a major research focus in computer-aided manufacturing and path planning for robots. This paper presents a collision-identification neural network (CINN) to identify possible collisions between two convex polyhedra. It consists of a modified Hamming net and a constraint subnet. The modified Hamming net is designed for point-to-polyhedron collision identification, and the constraint subnet is designed to move a point within a polyhedron and detect possible collisions with another polyhedron. A CINN has a simple canonical structure. It is very easy to program and can be implemented by a modest number of nonlinear amplifiers and three analog integrators. The working principle of the CINN is very similar to the well-known Hopfield net model. Its simple collective computing power accomplishes the relatively complicated task of collision identification between convex polyhedra, rendering a suitable device for online path planning of robots. An example is presented to demonstrate the application of CINN's to collision-free motion planning.     

Interactive continuous collision detection for non-convex polyhedra

We present a highly interactive, continuous collision detection algorithm for rigid, general polyhedra. Given initial and final configurations of a moving polyhedral model, our algorithm creates a continuous motion with constant translational and angular velocities, thereby interpolating the initial and final configurations of the model. Then, our algorithm reports whether the model under the interpolated motion collides with other rigid polyhedral models in environments, and if it does, the algorithm reports its first time of contact (TOC) with the environment as well as its associated contact features at TOC. Our algorithm is a generalization of conservative advancement [19] to general polyhedra. In this approach, we calculate the motion bound of a moving polyhedral model and estimate the TOC based on this bound, and advance the model by the current TOC estimate. We iterate this process until the inter-distance between the moving model and the other objects in the environments is below a user-defined distance threshold. We pose the problem of calculating the motion bound as a linear programming problem and provide an efficient, novel solution based on the simplex method. Moreover, we also provide a hierarchical advancement technique based on a bounding volume traversal tree to generalize the conservative advancement for non-convex models. Our algorithm is relatively simple to implement and has very small computational overhead of merely performing discrete collision detection multiple times. We extensively benchmarked our algorithm in different scenarios, and in comparison to other known continuous collision detection algorithms, the performance improvement ranges by a factor of 1.4～45.5 depending on benchmarking scenarios. Moreover, our algorithm can perform CCD at 120～15460 frames per second on a 3.6 GHz Pentium 4 PC for complex models consisting of 10K～70K triangles.     

Collision detection of a moving polygon in the presence ofpolygonal obstacles in the plane

This paper presents a new approach for the following collision detection problem in the plane: Let a simple polygon P rotate at a center &ogr; with constant angular velocity ω and translate towards a set of polygonal obstacles S with constant velocity ν. Given P and S as well as their initial positions, and given also the velocities of P, determine whether or not P will collide with any element of S and report the collided elements of S if collisions occurred. An O(mn) worst-case optimal algorithm is proposed to solve this problem, where n is the number of vertices of P and m is the number of vertices of the obstacles in S     

Collision detection for interactive graphics applications

Collision detection and response are important for interactive graphics applications such as vehicle simulators and virtual reality. Unfortunately, previous collision detection algorithms are too slow for interactive use. The paper presents a new algorithm for rigid or articulated objects that meets performance goals through a form of time critical computing. The algorithm supports progressive refinement, detecting collisions between successively tighter approximations to object surfaces as the application allows it more processing time. The algorithm uses simple four dimensional geometry to approximate motion, and hierarchies of spheres to approximate three dimensional surfaces at multiple resolutions. In a sample application, the algorithm allows interactive performance that is not possible with a good previous algorithm. In particular, the new algorithm provides acceptable accuracy while maintaining a steady and high frame rate, which in some cases improves on the previous algorithm's rate by more than two orders of magnitude     

一种改进的运动目标检测方法

为了克服传统背景差分法所存在的不足,提出了一种基于边缘特征和改进K-均值聚类相结合运动目标检测方法。运用改进的K-均值聚类方法建立背景模型,将其与前景图像相差后得到的二值化图像,通过前景边缘信息的鲁棒性来判别及去除存在的虚假目标。实验结果表明,该方法可以有效去除背景中突然有物体移入或移出引起的虚假运动目标,提高了运动目标检测的准确性。     

一种运动目标检测优化算法

提出了一种用于图像序列中检测运动目标的优化算法。针对用于室内目标检测的差分法存在着“虚影”噪声,以及用于室外目标检测的背景估计法在对短序列进行检测时,其结果中存在“残像”噪声的问题,揭示并利用两次差分之间的相关性实现了对“虚影”的检测并将其消除,将其引入背景估计法,以消除后者存在的“残像”噪声。实验表明,该方法在目标检测中不仅消除了“虚影”和“残像”噪声,而且检测结果的完整性显著提高。     

Back-face culling applied to collision detection of polyhedra

Back-face culling is a preprocessing technique used in computer graphics to speed up the rendering of polyhedra. In this paper we show how this technique can be modified to reduce unnecessary checking of boundary elements in collison detection for a physical-based simulation and animation systems. At each time step, we determine a priori which faces cannot be part of the contact between two polyhedra and thus can be culled. In the computer graphics technique, the normal vector of a polygon is compared with the view direction. Here, the normal is compared to one or possibly several relative-velocity vectors, and the face is culled when its motion is in the opposite direction of the normal vector. We also give an algorithm that takes linear time in terms of the number of faces, and on the average eliminates half of the polygons. Owing to its low computational overhead, when it is used as a front end to a collision detection system, a noticeable improvement in performance can be achieved.     

Collision detection in motion simulation

This paper describes a method of detecting collisions in motion simulation. In motion simulation, objects occasionally share a sphere in the simulated world. This would not occur in the real world, since objects would have collided before they shared a common sphere. In order to avoid such sharing and to accurately simulate collisions, a collision detection method called the Space Occupancy Method is proposed here, in which the detection of collisions between free form objects in 3-D space can be made quickly and precisely. An implementation design of the collision detection method and some results of simulations are shown.     

基于混合高斯模型的运动目标检测

提出了一种新的基于HSV颜色空间的阴影检测和误判检测的自适应背景模型运动目标检测算法,并将其应用于运动物体的分割。该算法较好地解决了背景模型的提取、更新、背景扰动、外界光照变化等问题。实验结果表明了该算法的实时性、可靠性和准确性较好。     

Dimensionality reduction for detection of moving vehicles

Automatic acoustic-based vehicle detection is a common task in security and surveillance systems. Usually, a recording device is placed in a designated area and a hardware/software system processes the sounds that are intercepted by this recording device to identify vehicles only as they pass by. An algorithm, which is suitable for online automatic detection of vehicles, which is based on their online acoustic recordings, is proposed. The scheme uses dimensionality reduction methodologies such as random projections instead of using traditional signal processing methods to extract features. It uncovers characteristic features of the recorded sounds without any assumptions about the structure of the signal. The set of features is classified by the application of PCA. The microphone is opened all the time and the algorithm filtered out many background noises such as wind, steps, speech, airplanes, etc. The introduced algorithm is generic and can be applied to various signal types for solving different detection and classification problems.     

Collision detection with relative screw motion

We introduce a framework for collision detection between a pair of rigid polyhedra. Given the initial and final positions and orientations of two objects, the algorithm determines whether they collide, and if so, when and where. All collisions, including collisions at different times, are computed at once along with properness values that measure the extent to which the collisions are between parts of the objects that properly face each other. This is useful for handling multiple (nearly) concurrent collisions and contact points.The relative motions of the rigid bodies are limited to screw motions. This limitation is not always completely accurate, but we can estimate the error introduced by the assumption.Our implementation uses rasterization to approximate the position and time of the collisions. This allows level-of-detail techniques that provide a tradeoff between accuracy and computational expense.The collision detection algorithms are only approximate, both because of the screw motion assumption and because of the rasterization. However, they can be made robust so as to give consistent information about collisions and to avoid sensitivity to roundoff errors.     

Assembly sequences for polyhedra

The problem of finding sequences of motions for the assembly of a given object consisting of polyhedral parts arises in assembly planning. We describe an algorithm to compute the set of all translations separating two polyhedra withn vertices inO(n⁴) steps and show that this is optimal. Given an assembly ofk polyhedra with a total ofn vertices, an extension of this algorithm identifies a valid translation and removable subassembly inO(k²n⁴) steps if one exists. Based on the second algorithm, a polynomial-time method for finding a complete assembly sequence consisting of single translations is derived. An implementation incorporates several changes to achieve better average-case performance; experimental results obtained for simple assemblies are described.This research was funded by DARPA Contract N00014-88-K-0620 (Office of Naval Research) and the Stanford Integrated Manufacturing Association (SIMA).     

基于ViBe改进的运动目标检测算法

运动目标检测一直是计算机视觉领域的重要研究方向,针对传统的ViBe算法容易出现鬼影、噪点和运动目标不完整等问题,提出一种基于ViBe改进算法的移动目标检测跟踪算法。通过连接区域的滤波操作,填充面积小于设定阈值的前景孔洞区域,以此限制散布在前景物体中的错误背景;通过检测图像的闪烁像素,更新存储之前的模板,并建立闪烁等级表,若某像素的闪烁等级大于等于设定的阈值,则将其从更新模版中移除,从而抑制更新模板中的闪烁区域。在动态视频中结果表明,该算法在满足实时性的前提下,可有效地改善传统ViBe算法,较好地提高运动目标检测效果。     

一种自然环境下运动物体监测算法

提出了一种自然环境下运动物体的监测算法,该算法基于时空信息融合与特征识别,主要包括背景分析、前景提取、去除阴影、背景更新。其思想是将图像序列均转换为HSV颜色模型,并分析比较各像素点参数在某一时间段内的变化规律,通过判定公式的判定,便可区分出各像素点在某一帧中是属于背景点、运动物体点还是阴影点。该算法针对风、阳光、闪电等自然条件可能带来的影响进行了改进,并能够在光照突变、运动物体静止后融入背景、背景物体转为运动等情况下智能更新背景,适用于自然环境下运动物体的监测。     

Collision detection technique for multiple access protocols on radio channels

The carrier sense multiple access with collision detection protocol (CSMA/CD) has already gained wide commercial acceptance and is used in cable and optical-fibre based local computer networks. However, its use in radio channels is inhibited by the difficulty of sensing remote carriers in the presence of local transmission. A new collision detection technique for radio channels called time-split collision detection is introduced. Collision is detected by a sequence of carrier sense, preamble transmission and carrier sense again at the beginning of a packet transmission. Throughput analysis of a new multiple access protocol using time-split collision detection is also presented. The proposed protocol has throughput performance between those of the CSMA and CSMA/CD.     

雷达微弱目标检测的有效方法

针对低信噪比条件下微弱运动目标检测问题,提出了一种基于检测前跟踪的动态规划改进算法,根据雷达图像中包含的来袭目标运动参数信息,预测来袭目标的运动轨迹,并沿着预测运动轨迹积累能量.仿真结果表明,该算法能够较准确地估计目标航迹,计算量较小,在强杂波背景下能较好地检测出低信噪比运动目标,对于威胁预警区域较大的来袭目标能更好进行实时探测.     

Entropy based region selection for moving object detection

This article addresses a problem of moving object detection by combining two kinds of segmentation schemes: temporal and spatial. It has been found that consideration of a global thresholding approach for temporal segmentation, where the threshold value is obtained by considering the histogram of the difference image corresponding to two frames, does not produce good result for moving object detection. This is due to the fact that the pixels in the lower end of the histogram are not identified as changed pixels (but they actually correspond to the changed regions). Hence there is an effect on object background classification. In this article, we propose a local histogram thresholding scheme to segment the difference image by dividing it into a number of small non-overlapping regions/windows and thresholding each window separately. The window/block size is determined by measuring the entropy content of it. The segmented regions from each window are combined to find the (entire) segmented image. This thresholded difference image is called the change detection mask (CDM) and represent the changed regions corresponding to the moving objects in the given image frame. The difference image is generated by considering the label information of the pixels from the spatially segmented output of two image frames. We have used a Markov Random Field (MRF) model for image modeling and the maximum a posteriori probability (MAP) estimation (for spatial segmentation) is done by a combination of simulated annealing (SA) and iterated conditional mode (ICM) algorithms. It has been observed that the entropy based adaptive window selection scheme yields better results for moving object detection with less effect on object background (mis) classification. The effectiveness of the proposed scheme is successfully tested over three video sequences.     

运动目标检测的ViBe算法改进

目的 目标检测在智能交通、自动驾驶以及安防监控中均有重要的地位,ViBe算法是常用的运动目标检测算法,它主要由背景模型初始化、前景检测、背景模型更新3部分组成,其思想简单,易于实现,运算效率高,但当初始帧有运动目标时,检测结果会出现“鬼影”现象,且易受噪声和光照变化影响,不能适应动态场景。同时,其逐帧逐像素进行前景检测,在计算复杂度方面有较大提升空间。为解决这些问题,提出一种改进的ViBe算法,称为ViBeImp算法。方法 在背景模型初始化时,用多帧平均法给出初始背景,采用该初始背景构建初始背景样本模型。在前景检测过程中,采用背景差分法、帧差法与OTSU算法相结合给出半径阈值的自适应计算方法。同时,根据背景差分法找出运动区域,只对运动区域进行前景判断和模型更新,降低算法的计算复杂度。结果 对25个不同场景视频分别给出ViBeImp算法在初始化背景,自适应半径阈值和计算复杂度方面改进的结果及有效性指标,实验结果表明,与ViBe、ViBeDiff2、ViBeIniR,以及Surendra等算法和高斯混合模型相比,ViBeImp算法对噪声、光照和背景动态变化有较好的鲁棒性,检测结果更完整,且实时性较好。同时,ViBeImp算法将ViBe算法的查准率、查全率以及F1值分别提高了17.98%、11.40%和15.96%。结论 ViBeImp算法采用多帧平均法构建初始背景可有效地消除“鬼影”,并给出半径阈值的自适应计算方法,使ViBe算法更快适应视频环境变化,准确且完整地检测出运动目标,具有较低的误检率和漏检率。该方法克服了ViBe算法对初始背景以及视频环境的依赖,很大程度上提高了运算速度,具有很好的鲁棒性和适用性。     

Collision detection algorithm robust to model uncertainty

With the widespread use of service robots, safety issues regarding human-robot collisions have received increasing attention. The collision detection algorithm, which allows a robot to effectively detect and react against a collision, is considered as one of the most practical solutions for ensuring collision safety. However, these algorithms are often model-based, so it cannot ensure collision safety under payload variations or model uncertainty. In this paper, a novel collision detection algorithm based on torque filtering is proposed to cope with this problem. The torque due to the motion of the robot can be effectively removed using the Butterworth 2nd-order BPF (band pass filter) so that only the torque due to a collision is used for collision detection. This improves the robustness of the algorithm against model uncertainties. The proposed algorithm does not require the use of acceleration data. The performance of the algorithm was experimentally verified.     

基于碰撞识别的优先级仲裁策略

针对单一信道下可用资源的分配问题,提出了基于碰撞识别的优先级仲裁策略,在研究了曼彻斯特编码特点的基础上,设计了一种新的编码方案,推导了优先级生成的模型,分析了仲裁的效率。仿真结果表明,在采用基于时分复用的MAC协议的前提下,同传统的逐节点询问方式相比,仲裁时间缩短为原来的四分之一。