A symmetry and bi-recursive algorithm of accurately computing Krawtchouk moments

Few scientific studies have discussed the accuracy of the Krawtchouk moments for the common case of p not equal 0.5. In the paper, a novel symmetry and bi-recursive algorithm is proposed to accurately calculate the Krawtchouk moments for the case of p is an element of (0, 1). The numerical propagation error mechanism of direct recursively calculating the Krawtchouk moments is first analyzed. It reveals that the recursion coefficients and recurrence times of the three-term recurrence relations are the key factors of reducing the propagation error in the computation of the Krawtchouk moment of high order. Based on the analysis, the x - n plane is divided into four parts by x = n and x + n = N - 1. We use the n-ascending recurrence formula to calculate the polynomials in the domain of N - 1 - n >= x >= n >= 0 and apply the n-descending recurrence relations in the domain of 0 <= N - 1 - n <= x <= n. Thus the maximum recursion times are limited to N/2. Finally, with the help of the diagonal symmetry property on x = n, the Krawtchouk polynomial values of high precision in the whole x n coordinates are obtained. The algorithm ensures that the maximum recursive numerical errors are within an acceptable range. An experiment on a large image of 400 x 400 pixels is designed to demonstrate the performance of the proposed algorithm against the classical method. (C) 2009 Elsevier B.V. All rights reserved.