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

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

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.     

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.     

Parameterized real-time moment computation on gray images using block techniques

Moments constitute a well-known tool in the field of image analysis and pattern recognition, but they suffer from the drawback of high computational cost. Efforts for the reduction of the required computational complexity have been reported, mainly focused on binary images, but recently some approaches for gray images have been also presented. In this study, we propose a simple but effective approach for the computation of gray image moments. The gray image is decomposed in a set of binary images. Some of these binary images are substituted by an ideal image, which is called “half-intensity” image. The remaining binary images are represented using the image block representation concept and their moments are computed fast using block techniques. The proposed method computes approximated moment values with an error of 2–3% from the exact values and operates in real time (i.e., video rate). The procedure is parameterized by the number m of “half-intensity” images used, which controls the approximation error and the speed gain of the method. The computational complexity is O(kL ²), where k is the number of blocks and L is the moment order.     

Recursive algorithm based on fuzzy 2-partition entropy for 2-level image thresholding

The fuzzy c-partition entropy approach for threshold selection behaves well in segmenting images. But the size of search space increases very rapidly when the number of parameters needed to determine the membership function increases. The computation complexity of the fuzzy 2-partition entropy approach is bounded by O(L³). In this paper, a recursive scheme which decreases the computation complexity of the basic algorithm to O(L²) is proposed. The approach does not need the calculation of the membership function. The processing time of each image is reduced from more than 5 min to less than 20 s.     

一种新的快速计算Legendre矩的方法

正交矩在模式识别，图像分析等领域有成功的应用，但由于正交矩的复杂性，有关正交矩的快速算法研究尚未得到很好的解决，该文提出一种 新的快速计算Ｌegendre矩的方法，该方法把基于像素点的二维Ｌegendre矩转换为线段的形式来计算，在计算出所有线段的积分后，使用扩展的Ｈatamian滤波方法来计算一维的Ｌegendre矩。结果显示新的算法有效地降低了计算的复杂度，并且，该方法能用于处理任意形状的物体。     

A fast algorithm for the computation of axial moments and its application to the orthogonal fitting of curves

This paper describes a fast algorithm to compute local axial moments used in the detection of objects of interest in images. The basic idea is the elimination of redundant operations while computing axial moments for two neighboring angles of orientation. The main result is that the complexity of the recursive computation of axial moments becomes independent of the total number of computed moments at a given point, i.e., it is of the order O(N) where N is the size of the data set. This result is of great importance in computer vision since many feature extraction methods rely on the computation of axial moments. The use of this algorithm for fast object skeletonization in images by orthogonal regression fitting is described in detail, with the experimental results confirming the theoretical computational complexity.     

Fast and low-complexity method for exact computation of 3D Legendre moments

A new method is proposed for fast and low-complexity computation of exact 3D Legendre moments. The proposed method consists of three main steps. In the first step, the symmetry property is employed where the computational complexity is reduced by 87%. In the second step, exact values of 3D Legendre moments are obtained by mathematically integrating the Legendre polynomials over digital image voxels. An algorithm is employed to significantly accelerate the computational process. In this algorithm, the equations of 3D Legendre moments are treated in a separated form. The proposed method is applied to determine translation-scale invariance of 3D Legendre moments in a very simple way. Numerical experiments are performed where the results are compared with those of the existing methods. Complexity analysis and results of the numerical experiments clearly ensure the efficiency of the proposed method.     

Connectivity-preserving transformations of binary images

A binary image I is B_a, W_b-connected, where a, b ∈ {4, 8}, if its foreground is a-connected and its background is b-connected. We consider a local modification of a B_a, w_b-connected image I in which a black pixel can be interchanged with an adjacent white pixel provided that this preserves the connectivity of both the foreground and the background of I. We have shown that for any (a, b) ∈ {(4, 8), (8, 4), (8, 8)}, any two B_a, w_b-connected images I and J each with n black pixels differ by a sequence of Θ(n²) interchanges. We have also shown that any two B₄, W₄-connected images I and J each with n black pixels differ by a sequence of O(n⁴) interchanges.     

Algorithms forn-th root approximation

Fromf(x)=x ⁿ ?r and a polynomialQ _p (y)=∑ _i=0 ^p a _i y ⁱ , we consider Newton's method to solveF _p (x)=Q _p (f(x))=0. We obtain convergent iterative methods of orderp+1 to findr ^1/n for arbitraryp.     

Computational experiences with discrete Lp-Approximation

DiscreteL _p -approximation, especially for 1≤p≤2 is useful for practical purposes. We describe the experience with an algorithm for its numerical computation.     

Linear complexity problems of level sequences of Euler quotients and their related binary sequences欧拉商的权位序列及其二元序列的线性复杂度问题

The Euler quotient modulo an odd-prime power p^r (r > 1) can be uniquely decomposed as a p-adic number of the form \(\frac{{u^{(p - 1)p^{r - 1} } - 1}}{{p^r }} \equiv a_0 (u) + a_1 (u)p + \cdots + a_{r - 1} (u)p^{r - 1} (\bmod p^r ), \gcd (u,p) = 1,\) where 0 ? a_j (u) < p for 0 ? j ? r?1 and we set all a_j (u) = 0 if gcd(u, p) > 1. We firstly study certain arithmetic properties of the level sequences (a_j (u))_u?0 over \(\mathbb{F}_p \) via introducing a new quotient. Then we determine the exact values of linear complexity of (a_j (u))_u?0 and values of k-error linear complexity for binary sequences defined by (a_j (u))_u?0.     

Optimal algorithms for the average-constrained maximum-sum segment problem

Given a real number sequence A=(a₁,a₂,…,an), an average lower bound L, and an average upper bound U, the Average-Constrained Maximum-Sum Segment problem is to locate a segment A(i,j)=(ai,ai+1,…,aj) that maximizes _∑i?k?jak subject to . In this paper, we give an O(n)-time algorithm for the case where the average upper bound is ineffective, i.e., U=∞. On the other hand, we prove that the time complexity of the problem with an effective average upper bound is Ω(nlogn) even if the average lower bound is ineffective, i.e., L=−∞.     

ARCADE: A prediction method for nominal variables

The main problem considered in this paper consists of binarizing categorical (nominal) attributes having a very large number of values (20⁴ in our application). A small number of relevant binary attributes are gathered from each initial attribute. Let us suppose that we want to binarize a categorical attribute v with L values, where L is large or very large. The total number of binary attributes that can be extracted from v is 2^L−1− 1, which in the case of a large L is prohibitive. Our idea is to select only those binary attributes that are predictive; and these shall constitute a small fraction of all possible binary attributes. In order to do this, the significant idea consists in grouping the L values of a categorical attribute by means of an hierarchical clustering method. To do so, we need to define a similarity between values, which is associated with their predictive power. By clustering the L values into a small number of clusters (J), we define a new categorical attribute with only J values. The hierarchical clustering method used by us, AVL, allows to choose a significant value for J. Now, we could consider using all the 2^L−1− 1 binary attributes associated with this new categorical attribute. Nevertheless, the J values are tree-structured, because we have used a hierarchical clustering method. We profit from this, and consider only about 2 × J binary attributes. If L is extremely large, for complexity and statistical reasons, we might not be able to apply a clustering algorithm directly. In this case, we start by “factorizing” v into a pair (v², v²), each one with about √L(v) values. For a simple example, consider an attribute v with only four values m₁,m₂, m₃,m₄. Obviously, in this example, there is no need to factorize the set of values of v, because it has a very small number of values. Nevertheless, for illustration purposes, v could be decomposed (factorized) into 2 attributes with only two values each; the correspondence between the values of v and (v², v²) would be     

15.

Exponentially weighted Legendre-Gauss Tau methods for linear second-order differential equations     

Mohamed K. El-Daou 《Computers & Mathematics with Applications》2011,62(1):51-64

We develop a method to solve a class of second-order ordinary differential equations with highly oscillatory solutions. The method consists in combining three different techniques: Legendre-Gauss spectral Tau method, exponential fitting, and coefficient perturbation methods. With our approach, the resulting approximate solutions are expressed in terms of an exponentially weighted Legendre polynomial basis {e^ω_nxL_n(x);n≥0}, where ω_n are appropriately chosen complex numbers. The accuracy and efficiency of the method are discussed and illustrated numerically.     

16.

Two new algorithms for efficient computation of Legendre moments     

J.D. ZhouAuthor VitaeH.Z. ShuAuthor Vitae  L.M. LuoAuthor VitaeW.X. YuAuthor Vitae 《Pattern recognition》2002,35(5):1143-1152

Orthogonal moments have been successfully used in the field of pattern recognition and image analysis. However, the direct computation of orthogonal moments is very expensive. In this paper, we present two new algorithms for fast computing the two-dimensional (2D) Legendre moments. The first algorithm consists of transforming the pixel-based calculation of Legendre moments into the line-segment-based calculation. After all line-segment moments have been calculated, Hatamian's filter method is extended to calculate the one-dimensional Legendre moments. The second algorithm is directly based on the double integral formulation. The 2D shape is considered as a continuous region and the contribution of the boundary points is used for fast calculation of shape moments. The numerical results show that the new algorithms can decrease the computational complexity tremendously, furthermore, they can be used to treat any complicated objects.     

17.

A Truncation Method for Computing Walsh Transforms with Applications to Image Processing     

《CVGIP: Graphical Models and Image Processing》1993,55(6):482-493

We present a method called the Truncation method for computing Walsh-Hadamard transforms of one- and two-dimensional data. In one dimension, the method uses binary trees as a basis for representing the data and computing the transform. In two dimensions, the method uses quadtrees (pyramids), adaptive quad-trees, or binary trees as a basis. We analyze the storage and time complexity of this method in worst and general cases. The results show that the Truncation method degenerates to the Fast Walsh Transform (FWT) in the worst case, while the Truncation method is faster than the Fast Walsh Transform when there is coherence in the input data, as will typically be the case for image data. In one dimension, the performance of the Truncation method for N data samples is between O(N) and O(N log₂N), and it is between O(N²) and O(N² log₂N) in two dimensions. Practical results on several images are presented to show that both the expected and actual overall times taken to compute Walsh transforms using the Truncation method are less than those required by a similar implementation of the FWT method.     

18.

On Steiner minimal trees withL p distance     

Zi -Cheng Liu  Ding -Zhu Du 《Algorithmica》1992,7(1-6):179-191

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ ?x ₂¦ ^p + ¦y₁ ?y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < ∞, each Steiner point is of degree exactly three. Define the Steiner ratio ? _p to be inf{L _s (P)/L _m (P)¦P?L _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ?₁ = 2/3. Chung and Graham proved ?₂ > 0.842. We prove in this paper that ?{∞} = 2/3 and √(√2/2)?₁?₂ ≤ ?_p ≤ √3/2 for anyp.     

19.

Multiplicity of positive solutions of a class of nonlinear fractional differential equations     

《Computers & Mathematics with Applications》2005,49(1):73-80

This paper is concerned with the nonlinear fractional differential equation L(D)u=f(x,u), u(0)=0, 0<x<1,where L(D) = Dsn − an−1Dsn−1 − … − a1Ds11 < s2 < … < sn < 1, and aj > 0, j = 1,2,…, n − 1. Some results are obtained for the existence, nonexistence, and multiplicity of positive solutions of the above equation by using Krasnoselskii's fixed-point theorem in a cone. In particular, it is proved that the above equation has N positive solutions under suitable conditions, where N is an arbitrary positive integer.     

20.

Asymptotic behavior of nonoscillatory solutions of neutral difference equations     

《Computers & Mathematics with Applications》2003,45(6-9):1461-1468

The authors consider the m^th-order neutral difference equation D_m(y(n) + p(n)y(n − k) + q(n)f(y(σ(n))) = e(n), where m ≥ 1, {p(n)}, {q(n)}, {e(n)}, and {a₁(n)}, {a₂(n)}, …, {a_m−1(n)} are real sequences, a_i(n) > 0 for i = 1,2,…, m−1, a_m(n) ≡ 1, D₀z(n) = y(n)+p(n)y(n − k), D_iz(n) = a_i(n)ΔD_i−1z(n) for i = 1,2, …, m, k is a positive integer, {σ(n)} → ∞ is a sequence of positive integers, and R → R is continuous with u f(u) > 0 for u ≠ 0. In the case where {q(n)} is allowed to oscillate, they obtain sufficient conditions for all bounded nonoscillatory solutions to converge to zero, and if {q(n)} is a nonnegative sequence, they establish sufficient conditions for all nonoscillatory solutions to converge to zero. Examples illustrating the results are included throughout the paper.     

Exponentially weighted Legendre-Gauss Tau methods for linear second-order differential equations

We develop a method to solve a class of second-order ordinary differential equations with highly oscillatory solutions. The method consists in combining three different techniques: Legendre-Gauss spectral Tau method, exponential fitting, and coefficient perturbation methods. With our approach, the resulting approximate solutions are expressed in terms of an exponentially weighted Legendre polynomial basis {e^ω_nxL_n(x);n≥0}, where ω_n are appropriately chosen complex numbers. The accuracy and efficiency of the method are discussed and illustrated numerically.     

Two new algorithms for efficient computation of Legendre moments

Orthogonal moments have been successfully used in the field of pattern recognition and image analysis. However, the direct computation of orthogonal moments is very expensive. In this paper, we present two new algorithms for fast computing the two-dimensional (2D) Legendre moments. The first algorithm consists of transforming the pixel-based calculation of Legendre moments into the line-segment-based calculation. After all line-segment moments have been calculated, Hatamian's filter method is extended to calculate the one-dimensional Legendre moments. The second algorithm is directly based on the double integral formulation. The 2D shape is considered as a continuous region and the contribution of the boundary points is used for fast calculation of shape moments. The numerical results show that the new algorithms can decrease the computational complexity tremendously, furthermore, they can be used to treat any complicated objects.     

A Truncation Method for Computing Walsh Transforms with Applications to Image Processing

We present a method called the Truncation method for computing Walsh-Hadamard transforms of one- and two-dimensional data. In one dimension, the method uses binary trees as a basis for representing the data and computing the transform. In two dimensions, the method uses quadtrees (pyramids), adaptive quad-trees, or binary trees as a basis. We analyze the storage and time complexity of this method in worst and general cases. The results show that the Truncation method degenerates to the Fast Walsh Transform (FWT) in the worst case, while the Truncation method is faster than the Fast Walsh Transform when there is coherence in the input data, as will typically be the case for image data. In one dimension, the performance of the Truncation method for N data samples is between O(N) and O(N log₂N), and it is between O(N²) and O(N² log₂N) in two dimensions. Practical results on several images are presented to show that both the expected and actual overall times taken to compute Walsh transforms using the Truncation method are less than those required by a similar implementation of the FWT method.     

On Steiner minimal trees withL p distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ ?x ₂¦ ^p + ¦y₁ ?y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < ∞, each Steiner point is of degree exactly three. Define the Steiner ratio ? _p to be inf{L _s (P)/L _m (P)¦P?L _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ?₁ = 2/3. Chung and Graham proved ?₂ > 0.842. We prove in this paper that ?{∞} = 2/3 and √(√2/2)?₁?₂ ≤ ?_p ≤ √3/2 for anyp.     

Multiplicity of positive solutions of a class of nonlinear fractional differential equations

This paper is concerned with the nonlinear fractional differential equation L(D)u=f(x,u), u(0)=0, 0<x<1,where L(D) = Dsn − an−1Dsn−1 − … − a1Ds11 < s2 < … < sn < 1, and aj > 0, j = 1,2,…, n − 1. Some results are obtained for the existence, nonexistence, and multiplicity of positive solutions of the above equation by using Krasnoselskii's fixed-point theorem in a cone. In particular, it is proved that the above equation has N positive solutions under suitable conditions, where N is an arbitrary positive integer.     

Asymptotic behavior of nonoscillatory solutions of neutral difference equations

The authors consider the m^th-order neutral difference equation D_m(y(n) + p(n)y(n − k) + q(n)f(y(σ(n))) = e(n), where m ≥ 1, {p(n)}, {q(n)}, {e(n)}, and {a₁(n)}, {a₂(n)}, …, {a_m−1(n)} are real sequences, a_i(n) > 0 for i = 1,2,…, m−1, a_m(n) ≡ 1, D₀z(n) = y(n)+p(n)y(n − k), D_iz(n) = a_i(n)ΔD_i−1z(n) for i = 1,2, …, m, k is a positive integer, {σ(n)} → ∞ is a sequence of positive integers, and R → R is continuous with u f(u) > 0 for u ≠ 0. In the case where {q(n)} is allowed to oscillate, they obtain sufficient conditions for all bounded nonoscillatory solutions to converge to zero, and if {q(n)} is a nonnegative sequence, they establish sufficient conditions for all nonoscillatory solutions to converge to zero. Examples illustrating the results are included throughout the paper.