1. Introduction
Accuracy in detection, robustness in performance and the ability to perform accurately and robustly are all integral considerations in image related research. However, since applications of such research often have a realtime constraint, speed of computation and its corollary timesaving have also become increasingly important in the research agenda.
The importance of geometric moment (GM) invariants first received research attention when Hu [1] introduced them in his study. As they capture global features have been widely used in applications such as object classification, image and shape analysis and edge detection [28]. However, since GMs are nonorthogonal, a set of continuous orthogonal moments including Zernike and Legendre moments was introduced by Teague [9]. Their desirable qualities of orthogonality, speed of computation and robustness have found a wider range of applications such as character recognition, twodimensional (2D) directionofarrival estimation, and trademark segmentation and retrieval [1013]. However, these continuous moments pose certain problems in computation: they require coordinate transformation and suitable approximation of the continuous moment integrals. The transformation and approximation they require create additional opportunities for the occurrence of error in the computation of the feature descriptors. This recognition of the error potential in continuous orthogonal moments led to a new set of discrete orthogonal moments such as Tchebichef, Krawtchouk and Hahn moments as these do not require coordinate transformation and the discretization step in the moment computation [1418].
The computation of both continuous and discrete orthogonal moments can be realized directly or via the GMs. The complexity in deriving higher order GMs using a direct calculation approach raises a significant challenge for realtime applications. A number of studies address this issue using different approaches. Hatamian [19] proposed a novel approach that uses 2D allpole digital filters with separable impulse responses to implement the first 16 GMs. Wong and Siu [20] moved the delay element in the basic filter structure as proposed in [19] from the feedforward to the feedback path. Their method considered moment computation of up to the third order. Using a similar structure of cascaded digital filters, Kotoulas and Andreadis showed orthogonal moments can be generated from their outputs [21]. To reduce the chip area size, they introduced an overflow counter in each of the basic filter structures [22]. However, the plurality of large bitwidth adders in the digital filter structure presents a major challenge to chip synthesis, placement and the routing process. Taking a different tack, AlRawi [23] generalized the relationship between the moments and the digital filter outputs using a recurrence formula.
Two facts demand our attention at this point. One, in all the aforementioned literature, the basic concept involved in the computation of moments using the digital filter structure has remained unchanged over the past three decades [19][20] even though this digital filter structure was formulated when only low orders of moments were used. Two, many recent works have involved increasingly higher moment orders. They include, among others, invariant image watermarking (30 orders) [24], moving object reconstruction (55 orders) [25], and hand shape verification (60 orders) [26].
Two models have been proposed to deal with higher order moments. The usage of cascaded allpole digital filters in generating higher order GMs for the formulation of orthogonal moments has been successfully explored by Kotoulas and Andreadis. In their work [21][22], the 40^{th} and 70^{th} high order Zernike and Tchebichef moments, respectively were obtained from the digital filter outputs and their transform coefficients. Their digital filter was based on the feedforward model, and for a
The method of computation we propose in this work attempts to reduce computational complexity – and save time through a reduction in the number of additions – by addressing the problems arising from: 1) The increase in digital filter output values as the order of moment’s increases and 2) the consequent use of positive and negative coefficient multipliers to make them exact. To circumvent the problems arising from these two facts, we are proposing the use of only positive coefficient multipliers which then makes it possible to use lower digital filter outputs as the order of the moment increases in generation of GMs. As will be discussed in greater detail in Section 3, the proposed method is based on the formulation and understanding of the impulse response of the digital filters, the unit step function to be used and their relationship with GMs. This formulation makes it possible for the digital filter outputs to be evaluated at earlier instances at
Recently, another types of discrete orthogonal moments such as Krawtchouk, dual Hahn, Racah, Meixner and Hahn moments have been introduced in image analysis community [16]–[17]. It was shown that they have better image representation capability than the continuous orthogonal moments.
One main difficulty concerning the use of moments as feature descriptors is their high computational complexity. To solve this problem, a number of fast algorithms have been reported in the literature [14]–[19]. Most of them concentrated on the fast computation of geometric moments and continuous orthogonal moments. This work examines various aspects; both theory and applications of image moment implementation using digital filter structures. Since these aspects can be discussed rather independently, we devote each chapter to the discussion of one particular aspect of moment structures. The following is a summary of contents of the sections.
Section 2: Orthogonal Moments. Numerous types of orthogonal polynomial, both in 1D and 2D, have been described in traditional mathematical literature. In this chapter we present a survey of orthogonal moments that are of importance in image analysis. The literature on orthogonal moments is very broad, namely in the area of practical applications, and our survey has no claim on completeness. We divide orthogonal polynomials and orthogonal moments into two basic groups. The polynomials orthogonal on a rectangle originate from 1D orthogonal polynomials whose 2D versions were created as products of 1D polynomials in x and y. The main advantage of the moments orthogonal on a rectangle is that they preserve the orthogonality even on the sampled image. They can be made scaleinvariant but creating rotation invariants from them is very complicated. The polynomials orthogonal on a disk are intrinsically 2D functions. They are constructed as products of a radial factor (usually a 1D orthogonal polynomial) and angular factor which is usually a kind of harmonic function. When implementing these moments, an image must be mapped into a disk of orthogonality which creates certain resampling problems. On the other hand, moments orthogonal on a disk can easily be used for construction of rotation invariants because they change under rotation in a simple way.
Section 3: A New Formulation of Geometric Moments from Lower Output Values of Digital Filters. In this chapter we propose a new method to accelerate geometric moment’s computation using digital filters based on the lower output values. It is shown in this chapter a brief reviews of the digital filter methods employed in [19] and [20]. First, a description of the proposed method that includes the theoretical formulation of the relationship between the digital filter outputs and GMs is provided. Second, we discuss the computational complexity with both an artificial and two real images, and the computational time. Finally, this study with some suggestions for future research is concluded.
Section 4: A Reduced 2D digital Filter Structure for Fast Computation of Geometric Moments. It is shown in this chapter how to design a reduced 2D digital filter grid for fast computation of geometric moments. For this design, the 1D and 2D allpole digital filter design procedure using the Ztransform properties is described. It also describes the recurrence equations for the desired filter outputs. The work shows the digital filter design used in [3] and [4], and shows the implementation of the proposed architecture. Finally, the computation results of the proposed method and the method used in [3] is illustrated.
Section 5: Conclusions. The presentation is concluded, summarizing the contents of the work and discussing possibilities which may be open for the future research.
2. Moment functions
Geometric Moments (GMs) and complex moments (CMs) are the simplest among moment functions, with the kernel function defined as a product of the pixel power coordinates. These type of moments are nonorthogonal and because of this problem, the inverse GMs or CMs formulation are not possible. On the other hand, the orthogonal moment functions have been used widley for image analysis. The orthogonal moment functions are based on the orthogonal polynomials such as Legendre, Zernike, Tchebichef, Krawtchouk and so on. All these moment functions play an important role in continuous or discrete domains of polynomials range.
2.1. Geometric and complex moments
GMs are defined with the basis kernel
where
Another popular choice of the polynomial basis
GMs and CMs carry the same amount of information. Each CM can be expressed in terms of GMs as
and vice versa
CMs are introduced because they behave favorably under image rotation. This property can be advantageously employed when constructing invariants with respect to rotation.
2.2. Orthogonal moments
If the polynomial basis
or weighted orthogonality
for any indexes
In theory, all polynomial bases of the same degree are equivalent because they generate the same space of functions. Any moment with respect to a certain basis can be expressed in terms of moments with respect to any other basis. From this point of view, OG moments of any type are equivalent to geometric moments.
However, a significant difference appears when considering stability and computational issues in a discrete domain. Standard powers are nearly dependent both for small and large values of the exponent and increase rapidly in range as the order increases. This leads to correlated geometric moments and to the need for high computational precision. Using lower precision results in unreliable computation of geometric moments. OG moments can capture the image features in an improved, nonredundant way. They also have the advantage of requiring lower computing precision because we can evaluate them using recurrent relations, without expressing them in terms of standard powers.
Unlike geometric moments, OG moments are coordinates of f in the polynomial basis in the common sense used in linear algebra. Thanks to this, the image reconstruction from OG moments can be performed easily as
2.3. Continuous moments
Some of orthogonal moments are in terms of a continuous variable such as Legendre, Zernike and GaussianHermite moments. All of these continuous moments depend on the same continuous polynomials. Here, we will discuss about such these polynomial functions and moments.
2.3.1. Legendre moments
There have been many works describing the use of the Legendre moments in image processing, e.g. references [29] and [30], among many others. The Legendre moments are defined as
where
and the image
The relation of orthogonality is
The recurrence relation, which can be used for efficient computation of the Legendre polynomials, is
2.3.2. Zernike moments
Zernike moments (ZMs) were introduced into image analysis about 30 years ago by Teague [9] who used ZMs to construct rotation invariants. He used the fact that the ZMs keep their magnitude under arbitrary rotation. He also showed that the Zernike invariants of the second and third orders are equivalent to the Hu invariants when expressed in terms of geometric moments. He presented the invariants up to the eighth order in explicit form but no general rule about how to derive them was given. Later, Wallin [31] described an algorithm for the formation of rotation invariants of any order. Numerical properties and possible applications of ZMs in image processing among others. ZMs of the nth order with repetition l are defined as
i.e. the difference
where the radial part is
The coefficients
can be used for conversion from geometric moments,
where
The Zernike polynomials satisfy the relation of orthogonality
The recurrence relation for the radial part is
Computation of the Zernike polynomials by this formula must commence with
2.4. Discrete moments
There is a group of orthogonal polynomials defined directly on a series of points and therefore they are especially suitable for digital images. Some of these polynomials such as Tchebichef, Krawtchouk, Hahn, dual Hahn and Meixner polynomials.
2.4.1. Tchebichef moments
The 2D TMs of order
where
and
where
where
2.4.2. Krawtchouk moments
The definition of the
where
and
The normalized and weighted Krawtchouk polynomials
where the weight function,
and
The normalized and weighted Krawtchouk polynomials have the following threeterm recurrence relation:
where
with
The 2D Krawtchouk moment of order
The orthogonality property leads to the following inverse moment transform
If only the moments of order up to
3. Formulation of geometric moments using digital filters
This section first reviews the generation of GMs using digital filter structure as proposed by Hatamian [19]. This is then followed by a review of the improved version used by Wong and Siu [20].
3.1. Hatamian’s model
Hatamian proposed the allpole digital filter structure to compute GMs up to the 16^{th} order. The one dimensional GMs of order
One reason for using digital filters as a moment generator is based on the convolution of the aforementioned sequence with impulse response,
where
The 1D cascaded filters structure is shown in Figure 2, where
The relationship between GMs and the allpole digital filter outputs are related by the following expression
where
For a two dimensional image, the relationship between the GMs and digital filters outputs can be expanded to
However, the allpole filter structure has delays in the feedforward path; hence it causes an increase in the computation time.
3.2. Wong and Siu’s model
To overcome this problem, Wong and Siu [20] moved the delay unit to the feedback path of the filter, as shown in Figure 3. The transfer function is given as
In this case, however, the GMs are obtained from the digital filter outputs and a different matrix coefficient, as shown below:
where the coefficients of
For a two dimensional image, the relationship between the GMs and the improved digital filters structure outputs are related by
3.3. Proposed method based on the lower output values of digital filters
We begin with the onedimensional case, where the results can be easily extended to twodimensional. Consider a digital filter with impulse response
Using the digital filter as shown in Figure. 3 and changing the unit step function to
Substituting,
Expanding the binomial equation, and using the Stirling numbers we get
where
Using (3.2), we can rewrite (3.15) in terms of GMs as follows:
Now by taking the inverse of (3.16), the GMs can be obtained in terms of the digital filter outputs thus:
where
where
Notice now, for the
3.4. Experimental studies
A set of experiments were carried out to validate the theoretical framework developed in the previous sections and to evaluate the performance of the proposed structure. This section is divided into 3 parts. In the first subsection, an artificial image of size 4×4 is used to generate GMs up to third order. The computational complexity of three algorithms – the algorithms of [19], [20] and the proposed method – is then analyzed and discussed in the second subsection. In the third subsection, the speed of the proposed method is compared with the speed achieved using [19] and [20].
3.4.1. Artificial test image
rtificial test image of size 4×4 was used to prove the validity of the proposed approach. In this case, the digital filter outputs up to third order were generated. The intensity function of the test image is given in the following matrix:
The difference between the digital filter output values for [20] and proposed structure is shown in Table 1. It is clear that for orders higher than one, the proposed output values are much lower than [20] as the order increases.
Digital filter outputs 
Filter structure output values [20]  Proposed structure output values 
 1736  1736 
 4326  4326 
 8651  4325 
 15148  2172 
 4358  4358 
 10870  10870 
 21750  10880 
 8742  4384 
 21811  10941 
 15331  2205 
3.4.2. Computational complexity
The advantage of the proposed method lies in the smaller digital filter output values as compared to [19] and [20]. However, it would still be useful to study the computational complexity of these three methods and the direct method in term of the number of additions and multiplications. The proposed method, [19] and [20] consist of two main steps. Digital filter outputs are obtained from the respective digital filter structure. Then, these outputs are linearly combined to compute GMs.
For a grayscale image of size
Algorithm 
Additions (Digital filter stages)  Additions (Digital filter outputs to GMs)  Multiplications (Digital filter outputs to GMs) 
[19] 



[20] 



Proposed method 



It can be seen that even though the complexity of the linear combination stage for the proposed method is the same as [20], there is saving in the number of additions at the digital filters stage. This can be clearly shown in the example below. For
Algorithm  Additions  Multiplications 
[19]  12847524  210795 
[20]  12791451  179355 
Proposed method  12269949  179355 
For a
3.4.3. Speed performance and comparison studies
The computation speed of the proposed method is compared with [19] and [20]. CPU elapsed time is used in the evaluation process in all the performed numerical experiments. The codes were all written in MATLAB7 and simulations were run with a 3GHz Intel Core2 with 2GB RAM and the average time is used in the discussion. The images used for the experiments were the Pepper and Lena images, as shown in Figure 5.
Table 4 shows the simulation time for GMs computation on the Pepper image of size 128×128 for orders of 5 to 55, in a step of 10. The same experiment was repeated on the Lena image of size 512×512. The simulation times are shown in Table 5.
Moment order (  [19]  [20]  Proposed method 
5  0.4  0.39  0.388 
15  1.12  1.104  1.05 
25  2.03  1.97  1.81 
35  3.28  3.14  2.82 
45  5.15  4.87  4.32 
55  7.96  7.48  6.63 
Moment order (  [19]  [20]  Proposed method 
5  6.03  6.02  6.00 
15  16.264  16.222  16.018 
25  26.817  26.722  26.13 
35  37.866  37.677  36.494 
45  49.663  49.325  47.343 
55  62.542  61.982  58.99 
The tables clearly show that the proposed method requires less time than [19] and [20] to compute GMs of the same order. They also show that the time saving increases as the order of moments increases. In Figure 6 and Figure 7 we provide a comparison of required CPU time between [19], [20] and the proposed method.
4. A Reduced 2D digital filter structures for fast computation of geometric moments
In the previous works, the linear transformation is performed using an external PC to relate the outputs of the digital filter structure to generate the moments. However, finding of a relationship between the geometric or orthogonal moments and the digital filters outputs has been stood as the main meaning of similar works [19][20].
In all the above aforementioned literatures, the basic concept involved the computation of geometric and other types of moments using the accumulator grid structure has remain unchanged over the past decades.
First we summarize the designing modality of allpole digital filters using 1D and 2D Ztransforms [32]. We believe that relevance creation manner among the realtime and Zdomain is one of the most essential issues in studying of digital image moments. This section presents the results of a study aimed at the formulation of a new method to reduce the filter resources used in the digital filter structure. This study, though not exhaustive, serves to provide a suitable classification framework that underlies a new approach in digital filter design for the computation of moments.
4.1. Reduced digital filter structure
Unlike the previous researchers who used a 1D Ztransform to derive a 2D digital filter structure by cascading the filters both in the rows and columns. However, we use a 2D definition of Ztransform to obtain the impulse response of the filter which led to a reduced digital filter structure as compared with [19]. The 2D Ztransform for the image,
The impulse response for a 2D image becomes:
and the transfer function
Using the above transfer function, the relationship between the input and the output of the digital filter is:
Based on (4.4), the zero order of the digital filter output is derived as
Thereafter, a recurrence relationship between the previous and the next outputs of each digital filter for the row and columns as shown in Figure 8 can be obtained:
By taking the inverse 2D Z transform of (4.6) and (4.7), we get the following:
The implementation of proposed digital filter structure for generating moments up to
As compared to the digital filter structure used in [19] and [20] as shown in Figure 10, it can be seen that the difference is the prefix,
In our proposed method, we begin by showing the relationship between the digital filter outputs and the geometric moments by considering a 1D image. So, the first few outputs of the digital filter are
(63) 
Hence by solving them, the above geometric moments can be obtained in terms of the digital filters outputs.
A matrix notation showing the above relationship between the geometric moments and the digital filter outputs as expressed
where
where,
Following the same procedure used in obtaining the 1D relationship digital filter outputs and geometric moments, it can also be extended for 2D image. This is done by taking the transpose of the digital filter outputs and the transpose of the matrix,
Also, the summation forms of (4.12) and (4.14) can be written as:
4.2. Experimental results
In this subsection, we will begin with an example to determine the geometric moments up to third order for 2D image using the proposed and existing method [19]. Figure.3. shows the proposed digital filter structure and the structure used in [19]. As can be seen from Figure 11(a) and (b), the proposed filter structure used three less digital filters. The difference between them is maximum
4.2.1. Artifical test image
Artificial test images of small size are used to prove validity of the proposed architecture. To illustrate the workings, an artificial image with size of
Consider the dimension of the input image is
 3  6 
 3  6 
 3  6 
 3  6 
 7  14 
 13  29 
 20  50 
 28  77 
 7  21 
 13  42 
 20  70 
 28  105 
 7  28 
 13  55 
 20  90  
 7  35 
 13  68  
 7  42 
The highlighted outputs can be collected as
If we derive the moments of the same example with the proposed method, the endpoint of the procedure is also 6. However, the results of the digital filter outputs are listed in Tables 8 and 9. In this case, according to Figure 11(a), it is wellknown that the number of the digital filter is deduced up to maximum
 0  1  2  3  4  5  6 
 0  5  2  3  4  6  1 
 0  5  7  3  7  6  7 
 0  5  3  6  7  7  7 
 0  5  8  14  7  14  21 
 0  5  13  27  7  21  42 
 0  5  18  45  7  28  70 
 0  5  23  68  7  35  105 
 3  6 
 3  6 
 3  6 
 3  6 
 14  21 
 27  42 
 45  70 
 68  105 
 14  35 
 27  69 
 45  115  
 14  49 
 27  96  
 14  63 
Based on (4.13) and (4.14), we can derive the digital filter outputs’ matrix (
4.2.2. Real test image
The images used for the experiments were the Pepper (128×128) and Lena (512×512) images as shown in Figure 12(a) and (b). As shown in Figure 13(a) and (b) the number of additions for digital filter processes are compared in [19] and the proposed method.
5. Conclusions
Orthogonal moments are widely used in image analysis and as pattern features in pattern classification. The computation of orthogonal moments can be achieved via geometric moments. Hatamian introduced cascaded digital filters, where each filter operates as an accumulator to generate geometric moments.
One of the weaknesses in using the outputs of the cascaded digital filters to generate the GMs is that the filter outputs increase exponentially as the orders of the moments increase. This work proposes a new formulation to solve this problem by sampling at earlier instances of
Also we showed a reduced method where the number of digital filters used in the generating of geometric moments is reduced by