A symmetry and bi-recursive algorithm of accurately computing
Krawtchouk moments
Guojun Zhang
a
, Zhu Luo
b
,BoFu
b,
*
,BoLi
a
, Jiaping Liao
b
, Xiuxiang Fan
b
, Zheng Xi
b
a
School of Mechanical Science and Engineering, Huazhong University of Science and Technology, 430074 Wuhan, China
b
School of Electrical and Electronic Engineering, Hubei University of Technology, 430068 Wuhan, China
article info
Article history:
Received 14 October 2008
Received in revised form 27 November 2009
Available online 16 December 2009
Communicated by G. Borgefors
Keywords:
Krawtchouk moments
Propagation error
n-Ascending recurrence relation
n-Descending recurrence relation
Diagonal symmetry
abstract
Few scientific studies have discussed the accuracy of the Krawtchouk moments for the common case of
p – 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 2 (0, 1). The numerical propagation error mechanism of direct
recursively calculating the Krawtchouk moments is first analyzed. It reveals that the recursion coeffi-
cients 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 P x P n P 0 and apply the n-descending
recurrence relations in the domain of 0 6 N 1 n 6 x 6 n. Thus the maximum recursion times are lim-
ited 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 400 pixels is designed to demonstrate the performance of the proposed algorithm against the
classical method.
Ó 2009 Elsevier B.V. All rights reserved.
1. Introduction
Moment functions have been used as feature characteristics in
many fields of image processing, such as pattern recognition, ob-
ject classification, template matching, edge detection, pose estima-
tion, robot vision, and data compression (Hu, 1962; Teague, 1982;
Dudani et al., 1977; Pawlak, 1992; Tech and Chin, 1988; Mukundan
and Ramakrishnan, 1995; Chong et al., 2004; Zhou et al., 2002; Fu
et al., 2007; Raj and Venkataramana, 2007; Chong et al., 2003; Chao
et al., 2002; Belkasim et al., 1989; Liao and Pawlak, 1998, 1996). In
(Hu, 1962) introduced a set of moment invariants based on the
theory of algebraic invariants, which are translation, scale and
rotation independent. Regular moments, however, are not orthog-
onal. As a result, reconstructing the image from the moments is a
difficult work. Teague (1982) first introduced moments with
orthogonal basis functions, with the additional property of mini-
mal information redundancy in a moment set. In this class, Legen-
dre and Zernike moments have been widely studied in the recent
past, and several new orthogonal moment-based feature detectors
have appeared (Tech and Chin, 1988; Mukundan and Ramakrish-
nan, 1995; Chong et al., 2004; Zhou et al., 2002; Fu et al., 2007;
Raj and Venkataramana, 2007; Chong et al., 2003; Chao et al.,
2002; Belkasim et al., 1989; Liao and Pawlak, 1998, 1996).
Since the Zernike and Legendre polynomials are defined only in-
side the unit region, the calculation of those moments requires a
coordinate transformation and proper approximation of the con-
tinuous moment integrals (Pawlak, 1992; Tech and Chin, 1988;
Mukundan and Ramakrishnan, 1995; Chong et al., 2004; Liao and
Pawlak, 1996). Discrete orthogonal moments, such as Tchebichef
moments (Mukundan et al., 2001; Mukundan, 2004), Hahn mo-
ments (Liang et al., 2006), Krawtchouk moments (KMs) (Yap
et al., 2002; Yap et al., 2003), are directly defined in the image coor-
dinate space and retained the property of orthogonality in a mo-
ment set. Discrete orthogonal moments are hence expected to be
superior to continuous moments, particularly in applications that
require independent shape descriptors (Liang et al., 2006; Yap
et al., 2002; Yap et al., 2003; Mukundan et al., 2001; Mukundan,
2004).
In the classical method (so called as Yap’s method; Yap et al.,
2002), we calculate the discrete orthogonal polynomials by using
its recursive relations. When image size is large, a non-negligible
problem encountered in the computation of discrete orthogonal
moments of higher order is the propagation of numerical errors.
0167-8655/$ - see front matter Ó 2009 Elsevier B.V. All rights reserved.
doi:10.1016/j.patrec.2009.12.007
* Corresponding author. Tel.: +86 13207126527; fax: +86 027 87543992.
E-mail addresses: zgj@mail.hust.edu.cn (G. Zhang), luozhu812@yahoo.com.cn
(Z. Luo), fubofanxx@yahoo.com.cn (B. Fu), hb_lib@163.com (B. Li), jpliao@mail.
hbut.edu.cn (J. Liao), fanxxhbut@126.com (X. Fan), 596579825@qq.com (Z. Xi).
Pattern Recognition Letters 31 (2010) 548–554
Contents lists available at ScienceDirect
Pattern Recognition Letters
journal homepage: www.elsevier.com/locate/patrec
