结合区间算术和退火遗传算法的曲面求交

§1.引言 曲面求交问题,由于在几何实体建模中的重要性,而得到广泛地重视和讨论.目前,已有文献中记载的方法大致可分为:解析法、隐函数法、离散网格法、自适应分割法、局部跟踪法等,其中解析法、隐函数法虽然求解精确、可靠,但依赖于曲面的解析性质及曲面方程,故只能适用于特定类型的曲面求交.离散网格法、自适应分割法虽然对曲面类型没有限制,但存在离散精度与运算效率的矛盾,并普遍存在病态情况.局部跟踪法由于不限定曲面类型且相对高效和精确,而应用得较为广泛,但仍存在如何有效地寻找初始交点问题.     

Efficient and accurate B-rep generation of low degree sculptured solids using exact arithmetic: I—representations

We present efficient representations and algorithms for exact boundary computation on low degree sculptured CSG solids using exact arithmetic. Most of the previous work using exact arithmetic has been restricted to polyhedral models. In this paper, we generalize it to higher order objects, whose boundaries are composed of rational parametric surfaces. We present the underlying representations necessary in our approach, and provide an overview of the boundary computation algorithm, which is described in more detail in a followup paper.     

柔性神经网络训练算法的研究

针对经典BP网络训练速度慢、易陷入局部最小值而无法收敛的弱点,提出用具有高度柔性的柔性神经网络代替经典网络,并以矩阵作为基本运算单位导出了柔性神经网络训练的最速下降法和LM(Levenberg Marquard)算法。矩阵作为基本运算单位的优点是可以用高效矩阵库LAPACK来编写程序,提高了数值计算的精度和速度。仿真结果表明了算法的有效性。     

Voxelized Minkowski sum computation on the GPU with robust culling

We present a new approach for computing the voxelized Minkowski sum (excluding any enclosed voids) of two polyhedral objects using programmable Graphics Processing Units (GPUs). We first cull out surface primitives that will not contribute to the final boundary of the Minkowski sum, analyzing and adaptively bounding the rounding errors of the culling algorithm to solve the floating point error problem. The remaining surface primitives are then rendered to depth textures along six orthogonal directions to generate an initial solid voxelization of the Minkowski sum. Finally we employ fast flood fill to find all the outside voxels. We generate both solid and surface voxelizations of Minkowski sums without enclosed voids and support high volumetric resolution of 1024³ with low video memory cost. The whole algorithm runs on the GPU and is at least one order of magnitude faster than existing boundary representation (B-rep) based algorithms. It avoids the large number of 3D Boolean operations needed in most existing algorithms and is easy to implement. The voxelized Minkowski sums can be used in a variety of applications including motion planning and penetration depth computation.     

Parallel VLSI architectures for real-time kinematics of redundant robots

We describe new architectures for the efficient computation of redundant manipulator kinematics (direct and inverse). By calculating the core of the problem in hardware, we can make full use of the redundancy by implementing more complex self-motion algorithms. A key component of our architecture is the calculation in the VLSI hardware of the Singular Value Decomposition of the manipulator Jacobian. Recent advances in VLSI have allowed the mapping of complex algorithms to hardware using systolic arrays with advanced computer arithmetic algorithms, such as the coordinate rotation (CORDIC) algorithms. We use CORDIC arithmetic in the novel design of our special-purpose VLSI array, which is used in computation of the Direct Kinematics Solution (DKS), the manipulator Jacobian, as well as the Jacobian Pseudoinverse. Application-specific (subtask-dependent) portions of the inverse kinematics are handled in parallel by a DSP processor which interfaces with the custom hardware and the host machine. The architecture and algorithm development is valid for general redundant manipulators and a wide range of processors currently available and under development commercially.     

Continuous penetration depth computation for rigid models using dynamic Minkowski sums

We present a novel, real-time algorithm for computing the continuous penetration depth (CPD) between two interpenetrating rigid models bounded by triangle meshes. Our algorithm guarantees gradient continuity for the penetration depth (PD) results, unlike conventional penetration depth (PD) algorithms that may have directional discontinuity due to the Euclidean projection operator involved with PD computation. Moreover, unlike prior CPD algorithms, our algorithm is able to handle an orientation change in the underlying model and deal with a topologically-complicated model with holes. Given two intersecting models, we interpolate tangent planes continuously on the boundary of the Minkowski sums between the models and find the closest point on the boundary using Phong projection. Given the high complexity of computing the Minkowski sums for polygonal models in 3D, our algorithm estimates a solution subspace for CPD and dynamically constructs and updates the Minkowski sums only locally in the subspace. We implemented our algorithm on a standard PC platform and tested its performance in terms of speed and continuity using various benchmarks of complicated rigid models, and demonstrated that our algorithm can compute CPD for general polygonal models consisting of tens of thousands of triangles with a hole in a few milli-seconds while guaranteeing the continuity of PD gradient. Moreover, our algorithm can compute more optimal PD values than a state-of-the-art PD algorithm due to the dynamic Minkowski sum computation.     

Design of a Fixed‐Order RST Controller for Interval Systems: Application to the Control of Piezoelectric Actuators

This paper presents a technique for designing a robust polynomial RST controller for parametric uncertain systems. The uncertain parameters are assumed to be bounded by intervals. The computation of the controller is addressed by introducing the interval arithmetic. The controller synthesis is formulated as a set inversion problem that can be solved using the SIVIA algorithm. The proposed method is afterwards applied to design a robust controller for a piezoelectric microactuator. The experimental results show the efficiency of the proposed method. Finally, a fine stability analysis is performed to analytically prove the robustness of the designed controller.     

Standard forms for rational linear arithmetic in constraint logic programming

Rational (resp. real) linear arithmetic is a computation domain included in several constraint logic programming languages. The decision procedure for this computation domain is usually based on a standard form for the representation of constraints. In this paper we show that the standard form used by the simplex algorithm for the representation of equations is not appropriate for deciding systems of linear constraints including disequations. We propose a new standard form, derived from it which overcomes the difficulty. We then show that the simplex algorithm can be extended to preserve this standard form through pivoting. These results provide the basis for an efficient and incremental procedure for rational linear arithmetic inside constraint logic programming languages.This paper is a revised and extended version of [19]. Part of this work was done while the authors were at ECRC, Munich (Germany).     

Design and analysis of evolutionary bit-length optimization algorithms for floating to fixed-point conversion

Hardware designs need to obey constraints of resource utilization, minimum clock frequency, power consumption, computation precision and data range, which are all affected by the data type representation. Floating and fixed-point representations are the most common data types to work with real numbers where arithmetic hardware units for fixed-point format can improve performance and reduce energy consumption when compared to floating point solution. However, the right bit-lengths estimation for fixed-point is a time-consuming task since it is a combinatorial optimization problem of minimizing the accumulative arithmetic computation error. This work proposes two evolutionary approaches to accelerate the process of converting algorithms from floating to fixed-point format. The first is based on a classic evolutionary algorithm and the second one introduces a compact genetic algorithm, with theoretical evidence that a near-optimal performance, to find a solution, has been reached. To validate the proposed approaches, they are applied to three computing intensive algorithms from the mobile robotic scenario, where data error accumulated during execution is influenced by sensor noise and navigation environment characteristics. The proposed compact genetic algorithm accelerates the conversion process up to 10.2× against the state of art methods reaching similar bit precision and robustness.     

基于PC的不变矩实时计算算法

矩和不变矩是工业部件识别和检测的重要特征.几何矩的值必须实时计算.介绍了灰度图像二维几何矩的高效计算.尽管存在许多矩快速计算算法,但不能在没有特殊硬件工具的微机上实时计算.原因是这些快速算法虽减少了计算复杂性,但在计算过程中仍需要大量浮点运算.为了实现在微机上的实时计算,提出的算法将图像分成相同大小的块,每图像块运用定点运算计算各自矩,然后运用浮点运算计算整个图像的矩.这种计算模式不需要近似而是精确计算,然而对于每个图像块不采用变换不容易克服溢出问题,在高效计算各图像块矩过程中使用了改进的Hatamian滤波器.实验结果表明,提出的算法大大减少了浮点运算次数,大大提高了图像矩计算速度.该算法可有效应用于复杂工业部件的实时识别和检测.     

Determining the directional contact range of two convex polyhedra

The directional contact range of two convex polyhedra is the range of positions that one of the polyhedra may locate in along a given straight line so that the two polyhedra are in collision. Using the contact range, one can quickly classify the positions along a line for a polyhedron as “safe” for free of collision with another polyhedron, or “unsafe” otherwise. This kind of contact detection between two objects is important in CAD, computer graphics and robotics applications. In this paper we propose a robust and efficient computation scheme to determine the directional contact range of two polyhedra. We consider the problem in its dual equivalence by studying the Minkowski difference of the two polyhedra under a duality transformation. The algorithm requires the construction of only a subset of the faces of the Minkowski difference, and resolves the directional range efficiently. It also computes the contact configurations when the boundaries of the polyhedra are in contact.     

Large Margin Classification Using the Perceptron Algorithm

We introduce and analyze a new algorithm for linear classification which combines Rosenblatt's perceptron algorithm with Helmbold and Warmuth's leave-one-out method. Like Vapnik's maximal-margin classifier, our algorithm takes advantage of data that are linearly separable with large margins. Compared to Vapnik's algorithm, however, ours is much simpler to implement, and much more efficient in terms of computation time. We also show that our algorithm can be efficiently used in very high dimensional spaces using kernel functions. We performed some experiments using our algorithm, and some variants of it, for classifying images of handwritten digits. The performance of our algorithm is close to, but not as good as, the performance of maximal-margin classifiers on the same problem, while saving significantly on computation time and programming effort.     

Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation

Mixed polynomial matrices are polynomial matrices with two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. The computation of their maximum degrees of minors is known to be reducible to valuated independent assignment problems, which can be solved by polynomial numbers of additions, subtractions, and multiplications of rational functions. However, these arithmetic operations on rational functions are much more expensive than those on constants. In this paper, we present a new algorithm of combinatorial relaxation type. The algorithm finds a combinatorial estimate of the maximum degree by solving a weighted bipartite matching problem, and checks if the estimate is equal to the true value by solving independent matching problems. The algorithm mainly relies on fast combinatorial algorithms and performs numerical computation only when necessary. In addition, it requires no arithmetic operations on rational functions. As a byproduct, this method yields a new algorithm for solving a linear valuated independent assignment problem.     

Contributing vertices-based Minkowski sum computation of convex polyhedra

Minkowski sum is an important operation. It is used in many domains such as: computer-aided design, robotics, spatial planning, mathematical morphology, and image processing. We propose a novel algorithm, named the Contributing Vertices-based Minkowski Sum (CVMS) algorithm for the computation of the Minkowski sum of convex polyhedra. The CVMS algorithm allows to easily obtain all the facets of the Minkowski sum polyhedron only by examining the contributing vertices—a concept we introduce in this work, for each input facet. We exploit the concept of contributing vertices to propose the Enhanced and Simplified Slope Diagram-based Minkowski Sum (ESSDMS) algorithm, a slope diagram-based Minkowski sum algorithm sharing some common points with the approach proposed by Wu et al. [Wu Y, Shah J, Davidson J. Improvements to algorithms for computing the Minkowski sum of 3-polytopes. Comput Aided Des. 2003; 35(13): 1181-92]. The ESSDMS algorithm does not embed input polyhedra on the unit sphere and does not need to perform stereographic projections. Moreover, the use of contributing vertices brings up more simplifications and improves the overall performance. The implementations for the mentioned algorithms are straightforward, use exact number types, produce exact results, and are based on CGAL, the Computational Geometry Algorithms Library. More examples and results of the CVMS algorithm for several convex polyhedra can be found at http://liris.cnrs.fr/hichem.barki/mksum/CVMS-convex.     

基于数学形态学的图像分形维数实时提取方法研究

图像的分形维数是图像的重要定量特征，可广泛应用于图像分析中。但一般计算图像分形维数的算法存在计算量大，不能实时计算的缺点。为了实时计算图像的分形维数，本文根据Ｍｉｎｋｏｗｓｋｉ－Ｂｏｕｌｉｇａｎｄ维数定义，采用数学形态学覆盖的方法设计了一种算法，并同Ｂｏｘ Ｃｏｕｎｔｉｎｇ方法进行了比较，实验计算结果表明该算法计算准确度高且稳健性好。同时本文还给出了实时并行实现结构。     

Evaluating signs of determinants using single-precision arithmetic

We propose a method of evaluating signs of 2×2 and 3×3 determinants withb-bit integer entries using onlyb and (b+1)-bit arithmetic, respectively. This algorithm has numerous applications in geometric computation and provides a general and practical approach to robustness. The algorithm has been implemented and compared with other exact computation methods. This work was partially supported by the ESPRIT Basic Research Action 7141 (AL-COMII) and by NSF Grant CCR 91-96176. Part of this work was done while J.-D. Boissonnat was visiting Brown University.     

Improvements to algorithms for computing the Minkowski sum of 3-polytopes

A Minkowski sum is a geometric operation that is equivalent either to the vector additions of all points in two operands or to the sweeping of one operand around the profile of the other without changing the relative orientation. Applications of Minkowski sums are found in computer graphics, robotics, spatial planning, and CAD. This paper presents two algorithms for computing Minkowski sum of convex polyhedron in three space (3-polytopes). Both algorithms are improvements on current ones found in the literature. One is based on convex hulls and the other on slope diagrams. The original convex hull based Minkowski algorithm is costly, while the original slope diagram based algorithms require the operation of stereographic projection from 3D to 2D for merging the slope diagrams of the two operands. Implementation of stereographic projection is complicated which increases the computation time and reduces the accuracy of the geometric information that is needed for constructing the resultant solid. This paper reports on improvements that have been made to these two algorithms and their implementation. These improvements include using vector operations to find the interrelations between points, arcs and regions on a unit sphere for the slope diagram algorithm, and addition of a pre-sorting procedure before constructing convex hull for convex hull based Minkowski sum algorithm. With these improvements, the computation time and complexity for both algorithms have been reduced significantly, and the computational accuracy of the slope diagram algorithm has been improved. This paper also compares these two algorithms to each other and to their original counterparts. The potential for extending these algorithms to higher dimensions is briefly discussed.     

Computing the Isolated Roots by Matrix Methods

Two main approaches are used, nowadays, to compute the roots of a zero-dimensional polynomial system. The first one involves Gröbner basis computation, and applies to any zero-dimensional system. But, it is performed withexact arithmetic and, usually, large numbers appear during the computation. The other approach is based on resultant formulations and can be performed with floating point arithmetic. However, it applies only to generic situations, leading to singular problems in several systems coming from robotics and computational vision, for instance.In this paper, reinvestigating the resultant approach from the linear algebra point of view, we handle the problem of genericity and present a new algorithm for computing the isolated roots of an algebraic variety, not necessarily of dimension zero. We analyse two types of resultant formulations, transform them into eigenvector problems, and describe special linear algebra operations on the matrix pencils in order to reduce the root computation to a non-singular eigenvector problem. This new algorithm, based on pencil decompositions, has a good complexity even in the non-generic situations and can be executed with floating point arithmetic.     

Foveated active tracking with redundant 2D motion parameters

This work presents a real-time active vision tracking system based on log-polar image motion estimation with 2D geometric deformation models. We present a very efficient parametric motion estimation method, where most computation can be done offline. We propose a redundant parameterization for the geometric deformations, which improve the convergence range of the algorithm. A foveated image representation provides extra computational savings and attenuation of background effects. A proper choice of motion models and a hierarchical organization of the iterations provide additional robustness. We present a fully integrated system with real-time performance and robustness to moderate deviations from the assumed deformation models.