A novel approach to the fast computation of Zernike moments

This paper presents a novel approach to the fast computation of Zernike moments from a digital image. Most existing fast methods for computing Zernike moments have focused on the reduction of the computational complexity of the Zernike 1-D radial polynomials by introducing their recurrence relations. Instead, in our proposed method, we focus on the reduction of the complexity of the computation of the 2-D Zernike basis functions. As Zernike basis functions have specific symmetry or anti-symmetry about the x-axis, the y-axis, the origin, and the straight line y=x, we can generate the Zernike basis functions by only computing one of their octants. As a result, the proposed method makes the computation time eight times faster than existing methods. The proposed method is applicable to the computation of an individual Zernike moment as well as a set of Zernike moments. In addition, when computing a series of Zernike moments, the proposed method can be used with one of the existing fast methods for computing Zernike radial polynomials. This paper also presents an accurate form of Zernike moments for a discrete image function. In the experiments, results show the accuracy of the form for computing discrete Zernike moments and confirm that the proposed method for the fast computation of Zernike moments is much more efficient than existing fast methods in most cases.     

Accurate and speedy computation of image Legendre moments for computer vision applications

A novel algorithm that permits the fast and accurate computation of the Legendre image moments is introduced in this paper. The proposed algorithm is based on the block representation of an image and on a new image representation scheme, the Image Slice Representation (ISR) method. The ISR method decomposes a gray-scale image as an expansion of several two-level images of different intensities (slices) and thus enables the partial application of the well-known Image Block Representation (IBR) algorithm to each image component. Moreover, using the resulted set of image blocks, the Legendre moments’ computation can be accelerated through appropriate computation schemes. Extensive experiments prove that the proposed methodology exhibits high efficiency in calculating Legendre moments on gray-scale, but furthermore on binary images. The newly introduced algorithm is suitable for the computation of the Legendre moments for pattern recognition and computer vision applications, where the images consist of objects presented in a scene.     

Efficient and accurate computation of geometric moments on gray-scale images

A novel algorithm that permits the fast and accurate computation of geometric moments on gray-scale images is presented in this paper. The proposed algorithm constitutes an extension of the IBR algorithm, introduced in the past, which was applicable only for binary images. A new image representation scheme, the ISR (intensity slice representation), which represents a gray-scale image as an expansion of several two-level images of different intensity values, enables the partially application of the IBR algorithm to each image component. Moreover, using the resulted set of image blocks, the geometric moments’ computation can be accelerated through appropriate computation schemes.     

Efficient Legendre moment computation for grey level images

Legendre orthogonal moments have been widely used in the field of image analysis. Because their computation by a direct method is very time expensive, recent efforts have been devoted to the reduction of computational complexity. Nevertheless, the existing algorithms are mainly focused on binary images. We propose here a new fast method for computing the Legendre moments, which is not only suitable for binary images but also for grey level images. We first establish a recurrence formula of one-dimensional (1D) Legendre moments by using the recursive property of Legendre polynomials. As a result, the 1D Legendre moments of order p, L_p=L_p(0), can be expressed as a linear combination of L_p-1(1) and L_p-2(0). Based on this relationship, the 1D Legendre moments L_p(0) can thus be obtained from the arrays of L₁(a) and L₀(a), where a is an integer number less than p. To further decrease the computation complexity, an algorithm, in which no multiplication is required, is used to compute these quantities. The method is then extended to the calculation of the two-dimensional Legendre moments L_pq. We show that the proposed method is more efficient than the direct method.     

Exact and fast algorithm for two-dimensional image wavelet moments via the projection transform

Wavelet moments are perfect representations of moments in multiresolution wavelet domain, which integrates the theory of moment invariants into wavelet analysis. However, the calculations of moments are very complicated in terms of computational complexity, so it is difficult to implement them in real time. An exact and fast projection-based algorithm for two-dimensional wavelet moments is presented in this paper. In our approach, the computation of a two-dimensional wavelet moment of order of r is performed in (r+1) different one-dimensional spaces. Since only additions are required to perform the projection transform, the total computational complexity can be greatly reduced.     

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

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

一种新的灰度图像Legendre矩的快速算法

Legendre正交矩在模式识别和图像分析等领域有着广泛的应用，但由于计算的复杂性，相关的快速算法尚未得到很好的解决，已有方法均局限于二值图像．文章提出了一种灰度图像的Legendre正交矩的快速算法，借助于Legendre多项式的递推公式推导出计算一维Legendre矩的递归公式．利用该关系式，一维Legendre矩Lp可以用一系列初始值L1(a)，a＜p，Lo(a)，a＜p-1来得到．而二维Legendre矩pq可以利用一维算法进行计算,为了降低算法复杂度，文中采用基于Systolic阵列的快速算法进行计算L1(a)，Lo(a),与直接方法相比，快速算法可以大幅度减少乘法的次数，从而达到了降低算法复杂度的目的。     

A comparative analysis of algorithms for fast computation of Zernike moments

This paper details a comparative analysis on time taken by the present and proposed methods to compute the Zernike moments, Z_pq. The present method comprises of Direct, Belkasim's, Prata's, Kintner's and Coefficient methods. We propose a new technique, denoted as q-recursive method, specifically for fast computation of Zernike moments. It uses radial polynomials of fixed order p with a varying index q to compute Zernike moments. Fast computation is achieved because it uses polynomials of higher index q to derive the polynomials of lower index q and it does not use any factorial terms. Individual order of moments can be calculated independently without employing lower- or higher-order moments. This is especially useful in cases where only selected orders of Zernike moments are needed as pattern features. The performance of the present and proposed methods are experimentally analyzed by calculating Zernike moments of orders 0 to p and specific order p using binary and grayscale images. In both the cases, the q-recursive method takes the shortest time to compute Zernike moments.     

Fast Recursive Computation of Krawtchouk Polynomials

Krawtchouk polynomials (KPs) and their moments are used widely in the field of signal processing for their superior discriminatory properties. This study proposes a new fast recursive algorithm to compute Krawtchouk polynomial coefficients (KPCs). This algorithm is based on the symmetry property of KPCs along the primary and secondary diagonals of the polynomial array. The \(n-x\) plane of the KP array is partitioned into four triangles, which are symmetrical across the primary and secondary diagonals. The proposed algorithm computes the KPCs for only one triangle (partition), while the coefficients of the other three triangles (partitions) can be computed using the derived symmetry properties of the KP. Therefore, only N / 4 recursion times are required. The proposed algorithm can also be used to compute polynomial coefficients for different values of the parameter p in interval (0, 1). The performance of the proposed algorithm is compared with that in previous literature in terms of image reconstruction error, polynomial size, and computation cost. Moreover, the proposed algorithm is applied in a face recognition system to determine the impact of parameter p on feature extraction ability. Simulation results show that the proposed algorithm has a remarkable advantage over other existing algorithms for a wide range of parameters p and polynomial size N, especially in reducing the computation time and the number of operations utilized.     

A new factorization of the mass matrix for optimal serial and parallel calculation of multibody dynamics

This paper describes a new factorization of the inverse of the joint-space inertia matrix M. In this factorization, M ^?1 is directly obtained as the product of a set of sparse matrices wherein, for a serial chain, only the inversion of a block-tridiagonal matrix is needed. In other words, this factorization reduces the inversion of a dense matrix to that of a block-tridiagonal one. As a result, this factorization leads to both an optimal serial and an optimal parallel algorithm, that is, a serial algorithm with a complexity of O(N) and a parallel algorithm with a time complexity of O(logN) on a computer with O(N) processors. The novel feature of this algorithm is that it first calculates the interbody forces. Once these forces are known, the accelerations are easily calculated. We discuss the extension of the algorithm to the task of calculating the forward dynamics of a kinematic tree consisting of a single main chain plus any number of short side branches. We also show that this new factorization of M ^?1 leads to a new factorization of the operational-space inverse inertia, Λ ^?1, in the form of a product involving sparse matrices. We show that this factorization can be exploited for optimal serial and parallel computation of Λ ^?1, that is, a serial algorithm with a complexity of O(N) and a parallel algorithm with a time complexity of O(logN) on a computer with O(N) processors.     

Fast algorithms for the conjugate periodic function

Two fast algorithms for the approximate computation of the conjugate periodic function are described. They are based on the fast Fourier transform and enable us to reduce the expenses toO (N logN) operations compared withO (N ²) operations for Wittich's classical method. The second algorithm, for which an ALGOL 60 procedure is listed, allows to evaluate the conjugate function on the even (or odd) numbered lattice points separately. (This feature is important for some applications.)     

A note on compressed sensing and the complexity of matrix multiplication

We consider the conjectured O(N2+?) time complexity of multiplying any two N×N matrices A and B. Our main result is a deterministic Compressed Sensing (CS) algorithm that both rapidly and accurately computes A⋅B provided that the resulting matrix product is sparse/compressible. As a consequence of our main result we increase the class of matrices A, for any given N×N matrix B, which allows the exact computation of A⋅B to be carried out using the conjectured O(N2+?) operations. Additionally, in the process of developing our matrix multiplication procedure, we present a modified version of Indyk's recently proposed extractor-based CS algorithm [P. Indyk, Explicit constructions for compressed sensing of sparse signals, in: SODA, 2008] which is resilient to noise.     

图像矩特征匹配的快速算法(英文)

针对图像匹配过程中矩特征计算量大的问题,从矩特征求解特点出发,提出了一种快速的矩特征匹配算法.该算法利用匹配过程中相邻待匹配子图间的相关性,通过设置十个和表,使得每个待匹配子图低阶矩的计算只需很少的几次加乘运算,大大降低了矩特征的计算复杂度,缩短了匹配耗时.同时,由于所提算法矩特征的计算是基于图像灰度值的精确计算,且匹配过程采用遍历搜索策略,因此其匹配精度与传统遍历搜索的匹配精度相当.仿真结果验证了所提算法的有效性.     

An agglomerative clustering algorithm using a dynamic k-nearest-neighbor list

In this paper, a new algorithm is developed to reduce the computational complexity of Ward’s method. The proposed approach uses a dynamic k-nearest-neighbor list to avoid the determination of a cluster’s nearest neighbor at some steps of the cluster merge. Double linked algorithm (DLA) can significantly reduce the computing time of the fast pairwise nearest neighbor (FPNN) algorithm by obtaining an approximate solution of hierarchical agglomerative clustering. In this paper, we propose a method to resolve the problem of a non-optimal solution for DLA while keeping the corresponding advantage of low computational complexity. The computational complexity of the proposed method DKNNA + FS (dynamic k-nearest-neighbor algorithm with a fast search) in terms of the number of distance calculations is O(N²), where N is the number of data points. Compared to FPNN with a fast search (FPNN + FS), the proposed method using the same fast search algorithm (DKNNA + FS) can reduce the computing time by a factor of 1.90-2.18 for the data set from a real image. In comparison with FPNN + FS, DKNNA + FS can reduce the computing time by a factor of 1.92-2.02 using the data set generated from three images. Compared to DLA with a fast search (DLA + FS), DKNNA + FS can decrease the average mean square error by 1.26% for the same data set.     

Fast Algorithm for Local Statistics Calculation for N -Dimensional Images

Local mean and variance measures are frequently required in multi-dimensional image analysis. These measures are needed when calculating correlation coefficients for local image matching purposes. Other measures such as skewness and autocorrelation are useful for texture analysis. This paper presents a fast algorithm for calculating these local statistics in a window of an N -dimensional image. The new algorithm, which is called the plunger method, recursively reduces the dimensions of the input N -dimensional image to achieve fast computation. The speed of the algorithm is independent of the window size. Another advantage of the algorithm is that it calculates the local statistics in one pass. Real image tests have been performed.     

Efficient computation of Zernike and Pseudo-Zernike moments for pattern classification applications

Two novel algorithms for the fast computation of the Zernike and Pseudo-Zernike moments are presented in this paper. The proposed algorithms are very useful, particularly in the case of using the computed moments, as discriminative features in pattern classification applications, where the computation of single moments of several orders is required. The derivation of the algorithms is based on the elimination of the factorial computations, by computing recursively the fractional terms of the orthogonal polynomials being used. The newly introduced algorithms are compared to the direct methods, which are the only methods that permit the computation of single moments of any order. The computational complexity of the proposed method is O(p ²) in multiplications, with p being the moment order, while the corresponding complexity of the direct method is O(p ³). Appropriate experiments justify the superiority of the proposed recursive algorithms over the direct ones, establishing them as alternative to the original algorithms, for the fast computation of the Zernike and Pseudo-Zernike moments.     

A fast algorithm for solving the first biharmonic boundary value problem

This paper presents a fast iterative algorithm for the solution of a finite difference approximation of the biharmonic boundary value problem on a rectangular region. For solving this problem, the matrix decomposition algorithm is efficiently applied to the semi-direct method which essentially treats the biharmonic equation as a coupled system of Poisson equations. Assuming anN×N grid of mesh points, the number of operations required for one iteration and for the solution terminated by 0 (N ^?2) is 0 (N ²) and 0 (N ^5/2 log₂ N), respectively. ForN ² processors, the parallel version of this algorithm would require 14 log₂ N steps per iteration. Both results are better than those known. A numerical experiment in a serial computation is also given.     

A fast fault-identification algorithm for bijective connection graphs using the PMC model

Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N^2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Möbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N = 2ⁿ, n ? 4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to Dahura–Masson’s algorithm when applied to BC graphs.     

The design and evaluation of the Simple Self-Similar Sequences Generator

This paper describes a new algorithm for the generation of pseudo random numbers with approximate self-similar structure. The Simple Self-Similar Sequences Generator (4SG) elaborates on an intuitive approach to obtain a fast and accurate procedure, capable of reproducing series of points exhibiting the property of persistence and anti-persistence. 4SG has a computational complexity of O(n) and memory requirements of the order of log₂(N), where N is the number of points to be generated. The accuracy of the algorithm is evaluated by means of computer-based simulations, recurring to several Hurst parameter estimators, namely Variance Time (VT) and the Wavelets-based estimator. The Hosking and the Wavelets-based methods for the generation of self-similar series were submitted to the same tests the 4SG was analysed with, providing for a basis for comparison of several performance aspects of the algorithm. Results show that the proposal embodies a good candidate not only for on-demand emulation of arbitrarily long self-similar sequences, but also for fast and efficient online simulations.     

Use of a double Fourier series for three-dimensional shape representation

The representation of three-dimensional star-shaped objects by the double Fourier series (DFS) coefficients of their boundary function is considered. An analogue of the convolution theorem for a DFS on a sphere is developed. It is then used to calculate the moments of an object directly from the DFS coefficients, without an intermediate reconstruction step. The complexity of computing the moments from the DFS coefficients is O(N ² log N), where N is the maximum order of coefficients retained in the expansion, while the complexity of computing the moments from the spherical harmonic representation is O(N ² log ² N). It is shown that under sufficient conditions, the moments and surface area corresponding to the truncated DFS converge to the true moments and area of an object. A new kind of DFS—the double Fourier sine series—is proposed which has better convergence properties than the previously used kinds and spherical harmonics in the case of objects with a sharp point above the pole of the spherical domain.