快速霍夫变换算法

二值图像的直线检测过程中,标准霍夫变换算法的计算量为O（N^3)。该文提出一种快速霍夫变换算法,其计算量仅为O（N^2log2N)。该快速算法可以并行实现;处理器阵列规模为O（N^2)时,计算量为O（log2N)。文中还分析得到快速算法的误差上界,并提出一种改进的快速霍夫变换算法以获得更高的计算精度。最后,给出算法的数值算例。理论分析及数值算例都表明,该文的快速霍夫变换算法在直线检测过程中有着更高的计算效率,并且具有良好的计算精度。     

Fast Reverse Jacket Transform As an Alternative Representation of the N-Point Fast Fourier Transform

The Reverse Jacket matrix (RJM) is a generalized form of the Hadamard matrix. Thus RJM is closely related to the matrix for fast Fourier transform (FFT). It also has a very interesting structure, i.e. its inverse can be easily obtained and has the reversal form of the original matrix. In this paper, we have shown that a transform based on the RJM offers a simple structure of N-point FFT in terms of the decomposition of the corresponding matrix and that it computes very fast the center weighted Hadamard transform.     

The Partial Fast Fourier Transform

An efficient algorithm for computing the one-dimensional partial fast Fourier transform \(f_j=\sum _{k=0}^{c(j)}e^{2\pi ijk/N} F_k\) is presented. Naive computation of the partial fast Fourier transform requires \({\mathcal O}(N^2)\) arithmetic operations for input data of length N. Unlike the standard fast Fourier transform, the partial fast Fourier transform imposes on the frequency variable k a cutoff function c(j) that depends on the space variable j; this prevents one from directly applying standard FFT algorithms. It is shown that the space–frequency domain can be partitioned into rectangular and trapezoidal subdomains over which efficient algorithms can be developed. As in the previous work of Ying and Fomel (Multiscale Model Simul 8(1):110–124, 2009), the contribution from rectangular regions can be reduced to a series of fractional-phase Fourier transforms over squares, each of which can be reduced to a convolution. In this work, we demonstrate that the partial Fourier transform over trapezoidal domains can also be reduced to a convolution. Since the computational complexity of a dealiased convolution of N inputs is \({\mathcal O}(N\log N)\), a fast algorithm for the partial Fourier transform is achieved, with a lower overall coefficient than obtained by Ying and Fomel.     

快速r循环分块Jacket变换

由中心权重哈达玛变换发展而来的Jacket变换,因其正交性、求逆简单和拥有快速算法等特点逐渐受到关注。Jacket变换可应用于信号与图像处理、数字移动通信、量子编码、大数据处理等领域。为了进一步丰富Jacket变换理论,提出了一种通用的循环分块Jacket变换(r-circulant block Jacket transform,r-CBJT)。同时基于基本的r循环分块矩阵的性质,给出了任意阶r循环分块Jacket变换矩阵的构造方法。随后进一步推导了任意阶r循环分块Jacket变换矩阵的快速构造与分解算法,该快速算法可表示为单位矩阵与低阶Jacket矩阵连续克罗内克积的迭代形式。相比直接计算算法,该快速算法拥有更高的计算效率,且该快速算法也可应用于具有类似结构的其他类型的r循环分块Jacket变换。     

基于GPU的快速球面距离变换

文中提出了一种基于GPU加速的精确计算球面距离变换的算法.球面距离变换在球面网格剖分、气象建模等领域有重要的应用.目前主要的球面距离变换算法是基于有序扩散的,即每个球面像素的距离变换都需要参照相邻像素的信息.因而难以通过并行计算加速.在经度-纬度参数域上,该文给出了依次沿纬线和经线独立扫描进行球面距离变换的理论证明,提...     

一种基于FFT计算离散小波变换的方法

将小波变换和快速傅里叶变换（FFT）方法相结合,分析研究了用快速傅里叶变换计算离散小波变换的方法,总结变换结果和滤波器长度之间的移位关系,并提出通过把输入信号信号循环移位,实现完全重构的方法。这种方法计算的时间复杂度和快速傅里叶变换相当。     

一种快速霍夫变换算法

霍夫变换是图像处理中的一种常用的检测算法,能够有效地在较大的噪声环境中提取图像中的特定信息。但标准的霍夫变换算法运算量大,处理速度慢,有较大的局限性。该文讨论了一种快速霍夫变换算法,该算法有效地降低了传统霍夫变换算法的时间复杂度,提高了计算效率和运算速度,对于提高图像处理的速度,增强图像处理的实时性有着显著的作用。     

Fast Fourier Transform for Hexagonal Aggregates

Hexagonal aggregates are hierarchical arrangements of hexagonal cells. These hexagonal cells may be efficiently addressed using a scheme known as generalized balanced ternary for dimension 2, or GBT₂. The objects of interest in this paper are digital images whose domains are hexagonal aggregates. We define a discrete Fourier transform (DFT) for such images. The main result of this paper is a radix-7, decimation-in-space fast Fourier transform (FFT) for images defined on hexagonal aggregates. The algorithm has complexity N log₇ N. It is expressed in terms of the p-product, a generalization of matrix multiplication. Data reordering (also known as shuffle permutations) is generally associated with FFT algorithms. However, use of the p-product makes data reordering unnecessary.     

多维离散Walsh变换快速算法设计

在分析二维离散Walsh变换形式化描述的基础上，以二维Walsh变换为例设计了一类多维离散型walsh变换的快速算法，分析了该算法的性能，指出这类算法形式多样，应用广泛。     

快速小波变换的加速算法(I)

1 自适应方法对小波变换的迫切期望图像、语音等处理技术的研究加快了小波理论的发展[1～9],今天信号处理技术随着通讯技术、计算机或机器人感知技术(实现计算机视觉、听觉、嗅觉、温度、运动等方面感知能力的技术)的飞速发展必将迎来更快发展.正如文[1]中所述:忽然间不可避免地涌现出了各种各样的非线性算法,从而也打开了信号处理通往现代数学的大门.除了传统的应用如信号传输、编码和信号恢复之外,信号处理也进入了信息分析的领域.”     

基于多项式变换的运动估计快速算法

主流的视频编码器普遍采用运动估计与补偿技术来提高压缩比,其中运动估计的计算复杂度高,需要占用大量的计算时间。因此,设计运动估计的快速算法对提高整个视频编码器的性能是至关重要的。此外,视频应用的实时性特点,也要求设计运动估计的快速算法。基于多项式变换的运动估计算法是论文新提出的一种块匹配运动估计算法,既保持了简单而易于硬件实现的特点,同时又极大地提高了计算效率。实验结果表明,基于多项式变换的运动估计算法的执行时间为全搜索算法的9～18%,优于其它快速算法。在噪声环境下,该算法比时间特性最好的WUS(WinnerUpdateSearch)算法以及Spiral算法快2～10倍。     

基于Hough变换的快速矩形检测算法

本文提出了一种基于图象Hough变换的矩形检测算法。通过对图象Hough变换空间中峰值点进行提取和组合，检测出满足角度和长度条件的直线组合，以快速定位出图象中的矩形。实验结果表明：该算法快速、准确，检测过程不需人工参与。     

一种长序列小波变换的快速实现方法

在对Mallat算法结构进行改进的同时,将长序列快速卷积算法中的重叠保留法引入Mallat算法中,提出了一种适合长序列小波变换的快速算法,给出了数学推导过程和具体实现步骤。该方法大大降低了小波变换的计算量,且并行性很好。仿真实验结果验证了算法的正确性。且运算速度较直接线性卷积实现方法有很大提高。     

Fast Fourier Transform simulation techniques for Coulomb gases

An improved approach to updating the electric field in simulations of Coulomb gases using the local lattice technique introduced by Maggs and Rossetto [A.C. Maggs, V. Rossetto, Phys. Rev. Lett. 88 (2002) 196402] is described and tested. Using the Fast Fourier Transform (FFT) an independent configuration of electric fields subject to Gauss' law constraint can be generated in a single update step. This FFT based method is shown to outperform previous approaches to updating the electric field in the simulation of a basic test problem in electrostatics of strongly correlated systems.     

M序Walsh变换的快速算法设计

讨论了Walsh函数系的一种序一逆Walsh序（M序），利用矩阵分解法设计了4种M序的快速Walsh变换算法。     

CCS上FFT运算的实现

FFT运算是数字信号处理技术的基础,DSP经常要用到FFT的运算,但FFT算法程序的编写调试费时费力。TI公司提供了以TMS320C28x系列芯片为基础的CCSFFTLibrary库函数,该库函数专门用于FFT运算,使在TMS320C28x系列芯片上实现FFT变得容易,本文就在CCS软件仿真器模式情况下对FFTLibrary库函数进行介绍并就使用方法进行说明。     

基于边界跟踪的快速欧氏距离变换算法

提出了一种基于边界跟踪、剥离的快速二维欧氏距离变换算法.从目标区域的最外层边界开始,自外向内、逐层对目标区域进行边界跟踪、剥离,直至目标区域为空.每跟踪到一个边界像素点,即根据其邻域像素所传递的最短距离信息来计算与最近背景像素间的欧氏距离,并利用一个链表结构来完成对已经过距离变换的像素点的距离更新,以解决距离传递的路径可能改变的问题.实验结果表明,该算法能够得到准确的欧氏距离,并且算法时间不到3×3倒角近似欧氏距离变换算法的2倍,比基于桶排序的欧氏距离变换算法快几十至上千倍.     

VHDL在FFT变换中的应用

控制系统的速度不但取决于控制器本身的速度,而且还在相当大程度上取决于控制算法,算法运算量的大小直接影响着对设备的控制质量。通过傅立叶变换(DFT),导出FIR实序列FFT快速简化算法;由VHDL编程,通过MAX PLUSII仿真,可以清晰地观测到,大大提高了运算速度,为实序列控制系统的设计提供了简单、方便、实用的计算机设计方法。