A comparison of filter output values between  and the proposed method for an artificial image, , up to third order.
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 real-time constraint, speed of computation and its corollary -time-saving- have also become increasingly important in the research agenda.
The importance of geometric moment (GM) invariants first received research attention when Hu  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 [2-8]. However, since GMs are non-orthogonal, a set of continuous orthogonal moments including Zernike and Legendre moments was introduced by Teague . Their desirable qualities of orthogonality, speed of computation and robustness have found a wider range of applications such as character recognition, two-dimensional (2D) direction-of-arrival estimation, and trademark segmentation and retrieval [10-13]. 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 [14-18].
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 real-time applications. A number of studies address this issue using different approaches. Hatamian  proposed a novel approach that uses 2D all-pole digital filters with separable impulse responses to implement the first 16 GMs. Wong and Siu  moved the delay element in the basic filter structure as proposed in  from the feed-forward 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 . To reduce the chip area size, they introduced an overflow counter in each of the basic filter structures . However, the plurality of large bit-width adders in the digital filter structure presents a major challenge to chip synthesis, placement and the routing process. Taking a different tack, Al-Rawi  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 - 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) , moving object reconstruction (55 orders) , and hand shape verification (60 orders) .
Two models have been proposed to deal with higher order moments. The usage of cascaded all-pole digital filters in generating higher order GMs for the formulation of orthogonal moments has been successfully explored by Kotoulas and Andreadis. In their work -, the 40th and 70th 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 image, the digital filter output values for row filtering are sampled at , where is the maximum order. The algorithm they propose, however, is undermined by a computational problem. At these time instances, the digital filter output values are much larger when compared to the earlier time instances. This is because the digital filter operates as an accumulator: their output values increase as the number of digital filters directly related to the order increases. The sample of digital filter output values obtained from the row filtering for each row are then used as inputs to the respective digital filters arranged in the column filtering. This further increases the size of the final digital filter outputs. Additionally, since the digital filter used is an approximation except for the first two orders, coefficients are then multiplied from second order onwards to make them exact. The coefficients, both positive and negative, are determined from the impulse response of the digital filter. The model proposed by Wong and Siu , though the digital filter outputs for all orders are sampled at their respective , also suffers from a similar problem. The current approaches, it is clear, thus suffer from an increase in computational complexity arising from the large increase in the digital filter output values as the order increases -.
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 where the lowest digital filter output value, sampled at is for the highest order. Meanwhile, this set of output values starts to decrease after moment orders.
Recently, another types of discrete orthogonal moments such as Krawtchouk, dual Hahn, Racah, Meixner and Hahn moments have been introduced in image analysis community –. 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 –. 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 scale-invariant 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  and . 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 all-pole digital filter design procedure using the Z-transform properties is described. It also describes the recurrence equations for the desired filter outputs. The work shows the digital filter design used in  and , and shows the implementation of the proposed architecture. Finally, the computation results of the proposed method and the method used in  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 non-orthogonal 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 . The th order two-dimensional GMs are denoted by , and can be expressed as
where is the image intensity function. GMs of low orders have an intuitive meaning,is a “mass” of the image (for binary images, is an area of the object), and define the center of gravity or centroid of the image. Second-order moments and describe the “distribution of mass” of the image with respect to the coordinate axes. In mechanics they are called the moments of inertia. Another popular mechanical quantity, the radius of gyration with respect to an axis, can also be expressed in terms of moments as and , respectively.
Another popular choice of the polynomial basis where is the imaginary unit, leads to complex moments
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 is orthogonal, i.e. if its elements satisfy the condition of orthogonality
or weighted orthogonality
for any indexes or , we speak about orthogonal (OG) moments. G is the area of orthogonality.
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, non-redundant 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 Gaussian-Hermite 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
where is the th degree Legendre polynomial (expression by the so-called Rodrigues’ formula)
and the image is mapped into the square . The Legendre polynomials of low degrees expressed in terms of are
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  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  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 is always even. The asterisk means the complex conjugate. The Zernike polynomials are defined as products
where the radial part is
can be used for conversion from geometric moments,
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 of an image intensity function with size is defined as
where is the th order orthogonal discrete Tchebichef polynomial defined by 
where is a normalization factor. The simplest choice of this factor is . The recurrence relation of Tchebichef polynomials with respect to the chosen order is:
where and the first two polynomials are and . The orthogonality property satisfies the following squared-norm:
2.4.2. Krawtchouk moments
The definition of the th order classical Krawtchouk polynomial is defined as
where and is the generalized hypergeometric function
and is the Pochhammer symbol given by
The normalized and weighted Krawtchouk polynomials are defined as 
where the weight function, and the square norm, are given as
The normalized and weighted Krawtchouk polynomials have the following three-term recurrence relation:
The 2D Krawtchouk moment of order of an image intensity function with size is defined as 
The orthogonality property leads to the following inverse moment transform
If only the moments of order up to are computed, then the reconstructed image in (2.30) can be approximated by
3. Formulation of geometric moments using digital filters
3.1. Hatamian’s model
Hatamian proposed the all-pole digital filter structure to compute GMs up to the 16th order. The one dimensional GMs of order for a -length sequence is defined in this model as
One reason for using digital filters as a moment generator is based on the convolution of the aforementioned sequence with impulse response, , where is the unit step function. Hence, the output of the digital filter evaluated at the point can be expressed:
where is the reversed sequence. Figure 1 shows the structure of a single pole digital filter with transfer function , which is equivalent to an accumulator with unity feedback. This accumulator has a delay in the feed-forward path. For cascaded filters, the corresponding transfer function is given by
The 1D cascaded filters structure is shown in Figure 2, where .
The relationship between GMs and the all-pole digital filter outputs are related by the following expression
where is the th digital filter output and is a matrix of coefficients directly obtained from the impulse responses of the all-pole digital filters as given in :
For a two dimensional image, the relationship between the GMs and digital filters outputs can be expanded to
However, the all-pole filter structure has delays in the feed-forward path; hence it causes an increase in the computation time.
3.2. Wong and Siu’s model
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 are obtained from the following recurrence formula shown in .
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 one-dimensional case, where the results can be easily extended to two-dimensional. Consider a digital filter with impulse response , where is the unit step function and is the moment order. Now, assume the input of the digital filter is given as as mentioned in (3.2). Based on the convolution theorem, the output, is therefore
Using the digital filter as shown in Figure. 3 and changing the unit step function to to accommodate the sampling of the digital filter outputs at earlier instances, we get the following
Expanding the binomial equation, and using the Stirling numbers we get
where are the Stirling numbers of the first kind , which satisfy
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 are the Stirling numbers of the second kind , and the Stirling numbers of the first and second kind can be considered to be inverses of one another:
where is the Kronecker delta.
Notice now, for the order, it can be shown that the digital filter outputs are sampled at , unlike the previous works which were sampled at or later instances of --. As the order is reached, the digital filter output values begin to decrease. This allows the use of low value digital filter outputs for the formulation of GM. The 2D moments can be obtained by expanding the 1D model for the digital filter outputs as follows:
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 ,  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  and .
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  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  as the order increases.
|Digital filter outputs||Filter structure output values||Proposed structure output values|
3.4.2. Computational complexity
The advantage of the proposed method lies in the smaller digital filter output values as compared to  and . 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,  and  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.
|Algorithm||Additions(Digital filter stages)||Additions (Digital filter outputs to GMs)||Multiplications (Digital filter outputs to GMs)|
It can be seen that even though the complexity of the linear combination stage for the proposed method is the same as , there is saving in the number of additions at the digital filters stage. This can be clearly shown in the example below. For and , the number of additions needed in the filter stage for  is 12612096 while the proposed method just requires 12090594 additions. The summary of the complexity comparison for all the three methods to compute GMs up to 45th order is shown in Table 3.
3.4.3. Speed performance and comparison studies
The computation speed of the proposed method is compared with  and . 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 ( s = p + q )||||||Proposed method|
|Moment order ( s = p + q )||||||Proposed method|
The tables clearly show that the proposed method requires less time than  and  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 ,  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 -.
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 all-pole digital filters using 1-D and 2-D Z-transforms . We believe that relevance creation manner among the real-time and Z-domain 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 1-D Z-transform to derive a 2-D digital filter structure by cascading the filters both in the rows and columns. However, we use a 2-D definition of Z-transform to obtain the impulse response of the filter which led to a reduced digital filter structure as compared with . The 2-D Z-transform for the image, is given as:
The impulse response for a 2-D image becomes:
and the transfer function , in the 2-D Z-transform domain for this filter structure is shown as
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 2-D Z- transform of (4.6) and (4.7), we get the following:
The implementation of proposed digital filter structure for generating moments up to orders is shown in Figure 9.
As compared to the digital filter structure used in  and  as shown in Figure 10, it can be seen that the difference is the prefix, and used in the rows. In the proposed model, the outputs , ,..., occur at the row filter, unlike in  and , they occur at the column filters. Hence, the difference in savings of digital filters used in the proposed method is determined by the maximum order. for example, in the design of the 40th order geometric moments, where the maximum order is 40, and thus the number of digital filters used in proposed method will be 40 digital filters less than  and .
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
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 is the geometric moment vector, is the digital filter output vector, and is a square matrix that a recurrence relationship between this matrix elements is given as
where, represents the floor function.
Following the same procedure used in obtaining the 1-D relationship digital filter outputs and geometric moments, it can also be extended for 2-D image. This is done by taking the transpose of the digital filter outputs and the transpose of the matrix, . For a 2-D image of dimensions , the geometric moments can be obtained from
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 2-D image using the proposed and existing method . Figure.3. shows the proposed digital filter structure and the structure used in . 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 order. As the number of moment orders increases the savings of the digital filters will be large. For example, the geometric moments used are forty orders, and then the number of digital filters will be reduced by forty as compared with existing methods.
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 to generate up to third order of geometric moments is considered. The intensity function of the test image is represented by the following input matrix:
Consider the dimension of the input image is , it means the endpoint of the filter outputs, is . Therefore, all generated outputs by the row filters are defined at different intervals till , where be represented by the Table 6. Table 7 shows the generated outputs by the column filters for two sampled seconds (3,6). The input image must be reversed in this method and denoted as .
The highlighted outputs can be collected as matrix in (4.12) and the coefficients matrix () as defined in (3.9), will generate the third order moments’ set of the artificial image as follows:
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 well-known that the number of the digital filter is deduced up to maximum order. Furthermore, in this method it does not need to reverse of the input sequence.
Based on (4.13) and (4.14), we can derive the digital filter outputs’ matrix (and the coefficients matrices (), respectively. Then, the set of third order moments are obtained as (4.17).
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 , where is the maximum moment order for an image. This step then paved the way to use a set of lower digital filter output values. The work demonstrates the efficacy and validity of the new algorithm in two ways: one, by comparing its complexity of computation with the complexity of two state of the art models proposed by Katoulos and Andreadis  and Wong and Siu  and two, by carrying out a set of experiments on speed of computation comparing the results obtained using the proposed method with those obtained using existing methods. A number of findings indicate the superiority of the proposed method: (1) A savings of as much as 45% is achieved for the proposed method in the number of additions as the moment order approaches when compared with the existing methods and (2) this leads to less computational time for the proposed method to derive the GMs. This work has focused on the software implications of the algorithm. If the proposed method is implemented in FPGA or ASIC based platforms, a great savings in terms of bit-widths will be realized.
Also we showed a reduced method where the number of digital filters used in the generating of geometric moments is reduced by -order when compared with the existing methods. The proposed method is modeled using the 2D Z-transform, and the theoretical framework for the proposed reduced digital filter structure is developed and the experimental results validate the performance.