Computations that require higher than double precision for robust and exact decision making

Consider the computation of deciding relative orientations of objects undergoing multiple translations and rotations. Such an orientation test involves the computation of expressions based on arithmetic operations, square roots and trigonometric functions. The computation of signs of such expressions using double precision floating-point arithmetic in modern computers may result in errors. In this article we demonstrate the existence of examples where double precision is not sufficient to compute the correct sign of an expression. We consider (i) simple expressions involving only the four basic arithmetic operations, (ii) expressions involving the square-root function and (iii) expressions representing orientation tests in two- and three-dimensions involving objects undergoing arbitrary rotations by angles given in radians, thereby requiring the computation of trigonometric functions. We develop a system that uses requisite high precision for computing the correct sign of such expressions. The system uses our floating-point filter called L-filter and the bigfloat extended precision package in LEDA (Library of Efficient Data Types and Algorithms).     

Modular Arithmetic for Linear Algebra Computations in the Real Field

The aim of this work is to decrease the bit precision required in computations without affecting the precision of the answer, whether this is computed exactly or within some tolerance. By precision we understand the number of bits in the binary representation of the values involved in the computation, hence a smaller precision requirement leads to a smaller complexity. We achieve this by combining the customary numerical techniques of rounding the least significant bits with the algebraic technique of reduction modulo an integer, which we extend to the reduction modulo a positive number. In particular, we show that, if the sum of several numbers has small magnitude, relative to the magnitude of the summands, then the precision used in the computation of this sum can be decreased without affecting the precision of the answer. Furthermore, if the magnitude of the inner product of two vectors is small and if one of them is filled with “short” binary numbers, then again we may decrease the precision of the computation. The method is applied to the iterative improvement algorithm for a linear system of equations whose coefficients are represented by “short” binary numbers, as well as to the solution of PDEs by means of multigrid methods. Some results of numerical experiments are presented to demonstrate the power of the method.     

基于动态阈值的帧复制粘贴篡改检测

帧复制粘贴是一种常见的时域篡改方式,篡改者采用这种方式来移除视频中某段内容,如犯罪现场、犯罪证据等.针对这种篡改,已经有不少方案被提出,但是它们有两个缺点：一采用固定的阈值;二时间复杂度很高.大部分被篡改视频会经过再压缩处理,由于视频压缩基本是有损压缩,可能会导致固定阈值失去应有作用.因此,本文提出一种基于动态阈值的被动取证算法,来增强算法的鲁棒性,并且通过引入字典排序算法来缩小帧匹配时的搜索范围,成功降低了时间复杂度.文章采用精确度、召回率和平均每帧计算时间来对提出算法的性能进行评估,结果表明本算法在这三方面都优于其他算法,而且具有更好的鲁棒性.     

A convex hull approach in conjunction with Gaussian mixture model for salient object detection

The capability of humans in distinguishing salient objects from background is at par excellence. The researchers are yet to develop a model that matches the detection accuracy as well as computation time taken by the humans. In this paper we attempted to improve the detection accuracy without capitalizing much of computation time. The model utilizes the fact that maximal amount of information is present at the corners and edges of an object in the image. Firstly the keypoints are extracted from the image by using multi-scale Harris and multi-scale Gabor functions. Then the image is roughly segmented into two regions: a salient region and a background region, by constructing a convex hull over these keypoints. Finally the pixels of the two regions are considered as samples to be drawn from a multivariate kernel function whose parameters are estimated using expectation maximization algorithm, to yield a saliency map. The performance of the proposed model is evaluated in terms of precision, recall, F-measure, area under curve and computation time using six publicly available image datasets. Experimental results demonstrate that the proposed model outperformed the existing state-of-the-art methods in terms of recall, F-measure and area under curve on all the six datasets, and precision on four datasets. The proposed method also takes comparatively less computation time in comparison to many existing methods.     

自适应变尺度混沌免疫优化算法及其应用

结合混沌优化算法与免疫算法的特点,提出了一种采用折叠次数无限的自映射X=sin(2/x)产生混沌变量的自适应变尺度混沌免疫优化算法.该算法通过自适应变尺度方法不断调整优化变量的搜索空间,同时采用最大循环次数作为控制指标,既保证了寻优的准确性,又保证了算法的快速性.应用该算法对3个测试函数进行优化计算得到了比较满意的结果.将此算法应用于移动Ad Hoc网络入侵检测时的仿真实验结果表明,自适应变尺度混沌免疫优化算法能有效地减少对训练样本的依赖,同时减少噪音数据对入侵检测系统性能的影响,适用于移动自组网络对于入侵检测系统高检测率、高抗噪能力和低计算延迟的要求.     

方块脉冲函数用于线性时变系统的分析和最优控制

本文给出了方块脉冲函数的一些运算性质.利用这些性质求解线性时变系统的状态方程 和基于二次型性能指标的最优控制规律,得出了便于应用的均匀分段恒定解答.较沃尔什函 数逼近法容易导出形式简明的递推算法,且子区间的分段数可选取任意整数,因而节省计算机 内存和机时,有助于提高计算和控制的精度.     

自适应动态控制种群规模的自然计算方法

提出了一种种群规模自适应动态控制策略,实现了种群规模根据进化过程自适应的动态变化.该策略的实现不依赖于算法进化操作的具体步骤,因而适用于各种基于种群优化的自然计算方法.首先给出了动态控制策略的框架;然后,在此框架下,充分利用动态种群规模反馈的有用信息,提出了基于Logistic模型的增加/删除数目自适应变化的方法,设计了自适应地兼顾有效性和多样性的增加算子和基于多样性的删除算子.将该策略应用到两种不同的自然计算方法中,采用经典测试函数和新型CEC05测试函数验证其性能.实验结果均表明,结合了所提出的种群规模自适应动态控制策略的新算法,比原算法在求解精度和收敛速度上均有明显的提升.     

Algorithms for fast computation of Zernike moments and their numerical stability

Accuracy, speed and numerical stability are among the major factors restricting the use of Zernike moments (ZMs) in numerous commercial applications where they are a tool of significant utility. Often these factors are conflicting in nature. The direct formulation of ZMs is prone to numerical integration error while in the recent past many fast algorithms are developed for its computation. On the other hand, the relationship between geometric moments (GMs) and ZMs reduces numerical integration error but it is observed to be computation intensive. We propose fast algorithms for both the formulations. In the proposed method, the order of time complexity for GMs-to-ZMs formulation is reduced and further enhancement in speed is achieved by using quasi-symmetry property of GMs. The existing q-recursive method for direct formulation is further modified by incorporating the recursive steps for the computation of trigonometric functions. We also observe that q-recursive method provides numerical stability caused by finite precision arithmetic at high orders of moment which is hitherto not reported in the literature. Experimental results on images of different sizes support our claim.     

Computing the Matrix Mittag-Leffler Function with Applications to Fractional Calculus

The computation of the Mittag-Leffler (ML) function with matrix arguments, and some applications in fractional calculus, are discussed. In general the evaluation of a scalar function in matrix arguments may require the computation of derivatives of possible high order depending on the matrix spectrum. Regarding the ML function, the numerical computation of its derivatives of arbitrary order is a completely unexplored topic; in this paper we address this issue and three different methods are tailored and investigated. The methods are combined together with an original derivatives balancing technique in order to devise an algorithm capable of providing high accuracy. The conditioning of the evaluation of matrix ML functions is also studied. The numerical experiments presented in the paper show that the proposed algorithm provides high accuracy, very often close to the machine precision.     

低码率图象传输系统运动补偿算法及实现

普通运动矢理搜索算法并不能完全适应低码率图象传输系统的特点，运算量也较大，本文经过试验分析，改进了适用于低码率系统的图象搜索算法，并提出使用亚采样模板匹配方法减少运动矢量搜索过程的计算量。     

Tree-Based Parallel Algorithm Design

In this paper a systematic method for the design of efficient parallel algorithms for the dynamic evaluation of computation trees and/or expressions is presented. This method involves the use of uniform closure properties of certain classes of unary functions. Using this method, optimal parallel algorithms are given for many computation tree problems which are important in parallel algebraic and numerical computation, and parallel code generation on exclusive read and exclusive write parallel random access machines. Our algorithmic result is complemented by a P-complete tree problem. Received February 13, 1995; revised March 25, 1996.     

Multiple precision computation of some zeros of bessel functions by rigorous explicit formulae

In order to perform the rigorous computation of the zeros of Bessel functions, we exploit classical approximants going back to Euler and recently generalized in the light of the Trefftz-Fichera orthogonal invariants method. Working in multiple precision (up to 140 significant figures in decimal system), we compute explicit approximants obtaining more than 100 exact figures for the first positive zero. By inversion of this zero as a function of the order, we evaluate the first eigenvalue of the exponential potential Schrödinger operator with the same accuracy.     

Simultaneous self-verified computation of exp (A) and ∫ 0 1 exp (As) dsexp (As) ds

We propose a method for simultaneous computation of verified bounds for the matrix functions exp (A) and ∫ ₀ ¹ exp (As) ds where the inclusion of the integral is obtained during the computation of verified bounds for exp (A) at very little additional cost. Highly accurate results of our method are achieved by the use of advanced computer arithmetic and an implementation of dynamic precision by means of staggered correction representation.     

ARMAX 模型全结构辨识——偏倚校正递推算法

文献[1]提出了ARMAX模型控制部分结构辨识的七步递推算法,本文以此为基础,进一步提出控制部分参数及阶次辨识的偏倚校正算法,同时利用输入信号的特有性质,得到观测噪声自相关函数估计的简单公式,以此得到AR型噪声模型的阶次与参数。本算法共分十步,具有运算速度快、辨识精度高的特点。文中最后给出了仿真结果。     

工业窑炉分布式控制系统的设计

针对目前窑炉行业运行控制中普遍存在能源浪费、低效、精度差、周期长等缺点,提出了开发工业窑炉分布式控制系统;此系统建立统一窑炉控制模型,将窑炉控制整体上分割成为若干个自治系统实现对每个温区的分别单独控制;自治系统内部运行中通过严谨而又科学的数学计算与软件PID技术,实现对每一温区高效、精确的控制;系统同时具有丰富的人机对话、安全防爆警示等功能。工程实践表明,此系统为工业窑炉控制行业提供了良好的模型和方法,具有很大的实际应用价值。     

模糊熵的区域合并和图割的快速矿岩分割

目的 针对现有区域合并和图割的结合算法没有考虑矿岩图像模糊特性,导致分割精度和运行效率较低,模糊边缘无法有效分割的问题,利用快速递推计算的最大模糊2-划熵信息设置以区域为顶点的图割模型似然能来解决。方法 首先利用双边滤波器和分水岭算法对矿岩图像进行预处理,并将其划分为若干一致性较好的区域;然后利用图像在计算最大模糊2-划分熵时,目标和背景的模糊隶属度函数来设计图割能量函数似然能,使得能量函数更接近模糊图像的真实情况,期间为了提高最大模糊2-划分熵值的搜索效率,提出了时间复杂度为O（n²）的递推算法将模糊熵的计算转化为递推过程,并保留不重复的递推结果用于后续的穷举搜索;最后利用设计的图割算法对区域进行标号,以完成分割。结果 本文算法的分割精度较其他区域合并和图割结合算法提高了约23%,分割后矿岩颗粒个数的统计结果相对于人工统计结果,其误差率约为2%,运行时间较其他算法缩短了约60%。结论 本文算法确保精度同时,有效提高矿岩图像的分割效率,为自动化矿岩图像高效分割的工程实践提供重要指导依据。     

基于CAZAC序列的MIMO-OFDM定时同步算法

针对MIMO-OFDM系统定时同步中的精确度问题,提出一种基于CAZAC序列的定时同步方法。通过CAZAC序列优化帧的定时目标、准确度以及结构,使得帧和符号同步同时实现,简化定时算法。帧同步和符号同步的联合实现,降低了定时算法的计算量并能够准确定义信道的第一径,能够在时域实现整数频偏的估计,在提高同步精度的同时降低了系统的复杂度,通过仿真验证了算法在Rayleigh衰落信道中性能的明显改善。     

弹性体和带空泡体的附加质量动态数值计算

附加质量是水下航行器水动力特性中的重要参数,对于弹性体和带空泡状态下的附加质量计算还有一定的困难。采用基于动网格技术的三维非定常粘性CFD程序解决了物体在流场中刚体运动和弹性变形所引起的附加质量计算问题。通过经典的刚体、弹性体附加质量算例验证了此方法是准确可靠的,还结合多相流模型和Rayleigh Plesset空化模型对带空泡体的附加质量进行了数值计算。带空泡体附加质量的数值研究表明,尾流中的空泡是否附体对轴向(流向)的附加质量影响比较大,对于本算例而言前端的肩空泡尺寸与横向(法向)附加质量系数则存在紧密的物理关联。     

基于脉冲星的航天器定位算法

为了提高脉冲星空间定位精度和减少计算量,提出了一种新的脉冲星定位算法。该算法先用三颗脉冲星产生脉冲模糊点,再引入新的脉冲星消除脉冲模糊点直到脉冲整周数唯一。然后,采用TDOA定位技术消除航天器时钟的漂移。最后,利用最小二乘算法提高空间定位精度。实验结果表明,在半径为300 000 km的球形试探范围内,该算法处理时间小于4 ms,能较好地满足实时性的要求,并具有较高的定位精度。     

一种改进的摄像机内外参数初值计算方法

两步法是一种典型的多阶段最优化摄像机标定方法,其优点是标定精度高,容易实现。该算法的关键是第一步计算出来的外部参数和与畸变无关的内部参数的初值。由于初值的计算不是纯粹的线性问题,计算起来比较复杂。本文对此进行了改进,采用一种新的方法计算初值。另外,由于图像坐标值的精度直接影响标定精度,本文为此采用了数学形态学学的膨胀和腐蚀方法,有效地克服了噪声的影响。实验结果表明,与平面模板两步法进行比较,本文算法减少了运算量,标定的结果适用于精度较高的场合。