Digital Filter Implementation of Orthogonal Moments

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 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 [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 [2-8]. However, since GMs are non-orthogonal, 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, 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 [19] proposed a novel approach that uses 2D all-pole 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 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 [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 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 [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 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 [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 $N \times N$ image, the digital filter output values for row filtering are sampled at $N+2, N+3, N+4, \dots , N+p+2$ , where $p$ 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 [20], though the digital filter outputs for all orders are sampled at their respective $N$ , 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 [33]-[34].

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 $N, N-1, N-2, \dots , N-p,$ where the lowest digital filter output value, sampled at $N-p$ is for the highest order. Meanwhile, this set of output values starts to decrease after $p/2$ 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 [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 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 [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 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 [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 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 $\left\{x^p{y}^q\right\}$ . The $\left(p+q\right)$ ^th order two-dimensional GMs are denoted by $m_{pq}$ , and can be expressed as

$$m_{pq}=\underset{-\mathrm{\infty }}{\overset{+\mathrm{\infty }}{\iint }}{x}^p{y}^{q}f\left(x,y\right)dxdy\mathrm{ }$$ E1

where $f\left(x,y\right)$ is the image intensity function. GMs of low orders have an intuitive meaning, $m_{00}$ is a “mass” of the image (for binary images, $m_{00}$ is an area of the object), $m\_01/m\_00$ and $m\_10/m\_00$ define the center of gravity or centroid of the image. Second-order moments $m_{02}$ and $m_{20}$ 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 $\sqrt{m_{02}/m_{00}}$ and $\sqrt{m_{20}/m_{00}}$ , respectively.

Another popular choice of the polynomial basis ${\left(x+iy\right)}^p{\left(x-iy\right)}^q$ where $i$ is the imaginary unit, leads to complex moments

$$c_{pq}=\underset{-\mathrm{\infty }}{\overset{+\mathrm{\infty }}{\iint }}{\left(x+iy\right)}^p{\left(x-iy\right)}^{q}f\left(x,y\right)dxdy\mathrm{ }$$ E2

GMs and CMs carry the same amount of information. Each CM can be expressed in terms of GMs as

$$c_{pq}=\sum _{k=0}^p\sum _{l=0}^q\left(\genfrac{}{}{0pt}{}{p}{k}\right)\left(\genfrac{}{}{0pt}{}{q}{l}\right){\left(-1\right)}^{q-l}{i}^{p+q-k-j}{m}_{k+j,p+q-k-j}$$ E3

and vice versa

$$m_{pq}=\sum _{k=0}^p\sum _{l=0}^q\left(\genfrac{}{}{0pt}{}{p}{k}\right)\left(\genfrac{}{}{0pt}{}{q}{l}\right)\frac{{\left(-1\right)}^{q-l}}{2^{p+q}{i}^q}{c}_{k+l,p+q-k-l}$$ E4

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 $\left\{p_{kj} \left(x, y\right)\right\}$ is orthogonal, i.e. if its elements satisfy the condition of orthogonality

$$\underset{G}{\overset{}{\iint }}{P}_{pq}\left(x,y\right)P_{mn}\left(x,y\right)dxdy=0\mathrm{ }$$ E5

or weighted orthogonality

$$\underset{G}{\overset{}{\iint }}{w\left(x,y\right)P}_{pq}\left(x,y\right)P_{mn}\left(x,y\right)dxdy=0\mathrm{ }$$ E6

for any indexes $p\ne m$ or $q\ne n$ , 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

$$f\left(x,y\right)=\sum _j{\sum _{k}M}_{kj}{P}_{kj}\left(x,y\right)\mathrm{ }$$ E7

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

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

$${\lambda }_{pq}=\frac{\left(2p+1\right)\left(2q+1\right)}{4}\underset{-1}{\overset{+1}{\iint }}{P}_p\left(x\right)P_q\left(y\right)f\left(x,y\right)dxd;\mathrm{ }p,q=0,\mathrm{ }1,\mathrm{ }2,\mathrm{ }\dots \mathrm{ }$$ E8

where $P_n\left(x\right)$ is the $n$ ^th degree Legendre polynomial (expression by the so-called Rodrigues’ formula)

$$P_p\left(x\right)=\frac{1}{2^{p}p!}\frac{d^p}{{dx}^p}{\left(x^2-1\right)}^p$$ E9

and the image $f\left(x, y\right)$ is mapped into the square $\left(-1, 1\right)\times \left(-1, 1\right)$ . The Legendre polynomials of low degrees expressed in terms of $x^p$ are

$$\begin{array}{l}{P}_0\left(x\right)=1,\mathrm{ }\\ P_1\left(x\right)=x,\\ P_2\left(x\right)=\frac{1}{2}\left(3x^2-1\right),\\ P_3\left(x\right)=\frac{1}{2}\left(5x^3-3x\right),\mathrm{ }\\ P_4\left(x\right)=\frac{1}{8}\left(35x^4-30x^2+3\right).\end{array}$$ E10

The relation of orthogonality is

$$\underset{-1}{\overset{1}{\int }}{P}_p\left(x\right)P_q\left(x\right)dx=\frac{2}{2q+1}{\delta }_{pq}\mathrm{ }$$ E11

The recurrence relation, which can be used for efficient computation of the Legendre polynomials, is

$$\begin{array}{l}{P}_0\left(x\right)=1,\mathrm{ }\\ P_1\left(x\right)=x,\\ P_{p+1}\left(x\right)=\frac{2p+1}{p+1}x{P}_p\left(x\right)-\frac{p}{p+1}{P}_{p-1}\left(x\right)\mathrm{ }\end{array}$$ E12

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

$$A_{pq}=\frac{p+1}{\pi }\underset{0}{\overset{2\pi }{\int }}\underset{0}{\overset{1}{\int }}{V}_{pq}^{\mathrm{*}}\left(r,\theta \right)f\left(r,\theta \right)rdrd\theta ,\mathrm{ } p=0,\mathrm{ }1,\mathrm{ }2,\mathrm{ }\dots \mathrm{ }q=-p,\mathrm{ }-p+2,\mathrm{ }\dots ,\mathrm{ }p\mathrm{ }$$ E13

i.e. the difference $n - \left|l\right|$ is always even. The asterisk means the complex conjugate. The Zernike polynomials are defined as products

$$V_{pq}\left(r,\theta \right)=R_{pq}\left(r\right)e^{iq\theta }\mathrm{ }$$ E14

where the radial part is

$$R_{pq}\left(r\right)=\sum _{k=\left|q\right|,\left|q\right|+2,\mathrm{ } \dots }^p{B}_{pqk}{r}^k$$ E15

The coefficients

$$B_{pqk}=\frac{{\left(-1\right)}^{\frac{p-k}{2}}\left(\frac{p+k}{2}\right)!}{\left(\frac{p-k}{2}\right)!\left(\frac{k+q}{2}\right)!\left(\frac{k-q}{2}\right)!}\mathrm{ }$$ E16

can be used for conversion from geometric moments,

$$A_{pq}=\frac{p+1}{\pi }\sum _{k=\left|q\right|,\left|q\right|+2,\mathrm{ } \dots }^p{\sum _{j=0}^{\frac{k-\left|q\right|}{2}}\sum _{l=0}^{\left|q\right|}\left(\genfrac{}{}{0pt}{}{\frac{k-\left|q\right|}{2}}{j}\right)\left(\genfrac{}{}{0pt}{}{\left|q\right|}{l}\right)w^{l}B}_{pqk}{m}_{k-2j-l,2j+l}\mathrm{ }$$ E17

where

$$w=\left\{\begin{array}{c}-i ; q>0\\ i ; q\le 0\end{array}\mathrm{ } \right.$$ E18

The Zernike polynomials satisfy the relation of orthogonality

$$\underset{0}{\overset{2\pi }{\int }}\underset{0}{\overset{1}{\int }}{V}_{pq}^{\mathrm{*}}\left(r,\theta \right)V_{kl}\left(r,\theta \right)rdrd\theta =\frac{\pi }{p+1}{\delta }_{kp}{\delta }_{lq}$$ E19

The recurrence relation for the radial part is

$$R_{pq}\left(r\right)=\frac{2pr}{p+q}{R}_{p-1,q-1}\left(r\right)-\frac{p-q}{p+q}{R}_{p-2.q}\left(r\right)\mathrm{ }$$ E20

Computation of the Zernike polynomials by this formula must commence with

$R_{pp}\left(r\right)=R_{p,-p}\left(r\right)=r^p\mathrm{ } ,\mathrm{ }p=0,\mathrm{ }1,\mathrm{ }\dots \mathrm{ }$

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 $\left(p+q\right)$ of an image intensity function $f\left(n,m\right)$ with size $N\times M$ is defined as

$$T_{pq}=A\left(p,N\right)A\left(q,M\right)\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}{t}_p\left(n\right)t_q\left(m\right)f\left(n,m\right)\mathrm{ }$$ E21

where $t_p\left(n\right)$ is the $p$ ^th order orthogonal discrete Tchebichef polynomial defined by [8]

$$t_p\left(n\right)=p!\sum _{k=0}^p{\left(-1\right)}^{p-k}\left(\genfrac{}{}{0pt}{}{N-1-k}{p-k}\right)\left(\genfrac{}{}{0pt}{}{p+k}{p}\right)\left(\genfrac{}{}{0pt}{}{n}{k}\right)$$ E22

and

$A\left(p,N\right)=\frac{\beta \left(p,N\right)}{\rho \left(p,N\right)}$

where $\beta \left(p,N\right)$ is a normalization factor. The simplest choice of this factor is $N^p$ . The recurrence relation of Tchebichef polynomials with respect to the chosen order is:

$$\left(p+1\right)t_{p+1}\left(n\right)-\left(2p+1\right)\left(2n-N+1\right)t_p\left(n\right)+p\left(N^2-p^2\right)t_{p-1}\left(n\right)=0$$ E23

where $p\ge 1$ and the first two polynomials are $t_0\left(n\right)=1$ and $t_1\left(n\right)=2n-N+1$ . The orthogonality property satisfies the following squared-norm:

$$\rho \left(p,N\right)=\left(2p\right)!\left(\genfrac{}{}{0pt}{}{N+p}{2p+1}\right)$$ E24

2.4.2. Krawtchouk moments

The definition of the $n$ ^th order classical Krawtchouk polynomial is defined as

$$K_n\left(x;p,N\right)=\sum _{k=0}^n{a}_{k,n,p}{x}^k={}_2{F}_1\left(-n,-x;-N;\frac{1}{p}\right)\mathrm{ }$$ E25

where $x,n=0, 1, 2, \dots , N, N>0, p\in \left(\mathrm{0,1}\right)$ and ${}_2{F}_1\left(\bullet \right)$ is the generalized hypergeometric function

$${}_2{F}_1\left(a,b;c;z\right)=\sum _{k=0}^{\mathrm{\infty }}\frac{{\left(a\right)}_k{\left(b\right)}_k}{{\left(c\right)}_k}\frac{z^k}{k!}\mathrm{ }$$ E26

and ${\left(x\right)}_k$ is the Pochhammer symbol given by

$$\begin{array}{l}{\left(x\right)}_k=x\left(x+1\right)\left(x+2\right)\cdots \left(x+k-1\right)\\ k\ge 1\mathrm{ }\mathrm{ }\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{ }{\left(x\right)}_0=1\end{array}$$ E27

The normalized and weighted Krawtchouk polynomials $\left\{{\stackrel{-}{K}}_n\left(x;p,N\right)\right\}$ are defined as [10]

$${\stackrel{-}{K}}_n\left(x;p,N\right)=K_n\left(x;p,N\right)\sqrt{\frac{w\left(x;p,N\right)}{\rho \left(n;p,N\right)}}$$ E28

where the weight function, $w\left(\bullet \right)$ and the square norm, $\rho \left(\bullet \right)$ are given as

$$w\left(x;p,N\right)=\left(\genfrac{}{}{0pt}{}{N}{x}\right)p^x{\left(1-p\right)}^{N-x}\mathrm{ }$$ E29

and

$$\rho \left(n;p,N\right)={\left(\frac{p-1}{p}\right)}^n\frac{n!}{{\left(-N\right)}_n}\mathrm{ }$$ E30

The normalized and weighted Krawtchouk polynomials have the following three-term recurrence relation:

$$p\left(n-N\right){\stackrel{-}{K}}_{n+1}\left(x;p,N\right)=A\left[p\left(N-2n\right)+n-x\right]{\stackrel{-}{K}}_n\left(x;p,N\right)-Bn\left(1-p\right){\stackrel{-}{K}}_{n-1}\left(x;p,N\right)$$ E31

where

$A=\sqrt{\frac{\left(1-p\right)\left(n+1\right)}{p\left(N-n\right)}}$

$B=\sqrt{\frac{{\left(1-p\right)}^2\left(n+1\right)n}{p^2\left(N-n\right)\left(N-n+1\right)}}$

with

${\stackrel{-}{K}}_0\left(x;p,N\right)=\sqrt{w\left(x;p,N\right)}$

${\stackrel{-}{K}}_1\left(x;p,N\right)=\left(1-\frac{1}{Np}x\right)\sqrt{w\left(x;p,N\right)}$ .

The 2D Krawtchouk moment of order $\left(n+m\right)$ of an image intensity function $f\left(x,y\right)$ with size $N\times M$ is defined as [16]

$$Q_{nm}=\sum _{x=0}^{N-1}\sum _{y=0}^{M-1}{\stackrel{-}{K}}_n\left(x;p_1,N-1\right){\stackrel{-}{K}}_m\left(y;p_2,M-1\right)f\left(x,y\right)$$ E32

The orthogonality property leads to the following inverse moment transform

$$f\left(x,y\right)=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}{Q}_{nm}{\stackrel{-}{K}}_n\left(x;p_1,N-1\right){\stackrel{-}{K}}_m\left(y;p_2,M-1\right)$$ E33

If only the moments of order up to $\left(N_{max} ,M_{max}\right)$ are computed, then the reconstructed image in (2.30) can be approximated by

$$\tilde{f}\left(x,y\right)=\sum _{n=0}^{N_{max}}\sum _{m=0}^{M_{max}}{Q}_{nm}{\stackrel{-}{K}}_n\left(x;p_1,N-1\right){\stackrel{-}{K}}_m\left(y;p_2,M-1\right)$$ E34

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 all-pole digital filter structure to compute GMs up to the 16^th order. The one dimensional GMs of order $p$ for a $N$ -length sequence $x\left[n\right]$ is defined in this model as

$$m_p=\sum _{n=0}^{N-1}{n}^{p}x\left[n\right]$$ E35

One reason for using digital filters as a moment generator is based on the convolution of the aforementioned sequence with impulse response, $n^{p}u\left[n\right]$ , where $u\left[n\right]$ is the unit step function. Hence, the output of the digital filter $y_p$ evaluated at the point $n = N-1$ can be expressed:

$$y_p\left[N\right]=\sum _{k=0}^{N-1}x\left[k\right]{\left(N-k\right)}^p\mathrm{ }$$ E36

where $x\left[n\right]$ is the reversed sequence. Figure 1 shows the structure of a single pole digital filter with transfer function $\frac{1}{z-1}$ , which is equivalent to an accumulator with unity feedback. This accumulator has a delay in the feed-forward path. For $p$ cascaded filters, the corresponding transfer function is given by

$$H_p\left(z\right)=\frac{1}{{\left(z-1\right)}^{p+1}}\mathrm{ }$$ E37

Figure 1.

Single-pole filter structure [19] in feedforward path.

The 1D cascaded filters structure is shown in Figure 2, where $H_0\left(z\right)=\frac{1}{z-1}$ .

Figure 2.

Cascading of single-pole filters for generating of moments up to order $p$ .

The relationship between GMs and the all-pole digital filter outputs are related by the following expression

$$m_p=\sum _{r=0}^p{C}_{p,r}{y}_r\mathrm{ }$$ E38

where $y_r$ is the $r$ ^th digital filter output and $C_{p,r}$ is a matrix of coefficients directly obtained from the impulse responses of the all-pole digital filters as given in [27]:

$$C_{p,r}=\left\{\begin{array}{ccc}0& ;& r>p\\ {\left(-1\right)}^p& ;& r=0,p\ge 0\\ r{C}_{p-1,r-1}-\left(r+1\right)C_{p-1,r}& ;& r>0,p>0\end{array}\right.\mathrm{ }$$ E39

For a two dimensional image, the relationship between the GMs and digital filters outputs can be expanded to

$$m_{p,q}=\sum _{r=0}^p{C}_{p,r}\sum _{s=0}^q{C}_{q,s}{y}_{r,s}\mathrm{ }$$ E40

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

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

$$H_p\left(z\right)={\left(\frac{1}{1-z^{-1}}\right)}^{p+1}$$ E41

Figure 3.

Single-pole filter structure [20] in feedback path.

In this case, however, the GMs are obtained from the digital filter outputs and a different matrix coefficient, as shown below:

$$m_p=\sum _{r=0}^p{D}_{p,r}{y}_r$$ E42

where the coefficients of $D_{p,r}$ are obtained from the following recurrence formula shown in [23].

$$D_{p,r}=\left\{\begin{array}{ccc}0& ;& p>0,r=0\\ 1& ;& p=0,r=0\\ r\left(D_{p-1.r-1}-D_{p-1,r}\right)& ;& others\end{array}\right.$$ E43

For a two dimensional image, the relationship between the GMs and the improved digital filters structure outputs are related by

$$m_{p,q}=\sum _{r=0}^p{D}_{p,r}\sum _{s=0}^q{D}_{q,s}{y}_{r,s}\mathrm{ }$$ E44

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 $h_p\left[n\right]= n^{p}u\left[n\right]$ , where $u\left[n\right]$ is the unit step function and $p$ is the moment order. Now, assume the input of the digital filter is given as $x\left[n\right]$ as mentioned in (3.2). Based on the convolution theorem, the output, $y\left[n\right]$ is therefore

$$y_p\left[n\right]=x\left[n\right]\mathrm{*}{h}_p\left[n\right]$$ E45

Using the digital filter as shown in Figure. 3 and changing the unit step function to $u\left[n+p\right]$ to accommodate the sampling of the digital filter outputs at earlier instances, we get the following

$$y_p\left[n\right]=x\left[n\right]\mathrm{*}\left(\genfrac{}{}{0pt}{}{n+p}{p}\right)u\left[n+p\right] =\sum _{k=0}^{n+p}x\left[k\right]\left(\genfrac{}{}{0pt}{}{n-k+p}{p}\right)\mathrm{ }$$ E46

Substituting, $n=N-p$ yields

$$y_p\left[N-p\right]=\sum _{k=0}^{N}x\left[k\right]\left(\genfrac{}{}{0pt}{}{N-k}{p}\right)$$ E47

Expanding the binomial equation, and using the Stirling numbers we get

$$y_p\left[N-p\right]=\frac{1}{p!}\sum _{k=0}^N\sum _{i=0}^p{s}_1\left(p,i\right)x\left[k\right]{\left(N-k\right)}^i$$ E48

where $s_1\left(p,i\right)$ are the Stirling numbers of the first kind [28], which satisfy

$$\frac{\left(N-k\right)!}{\left(N-k-p\right)!}=\sum _{i=0}^p{s}_1\left(p,i\right){\left(N-k\right)}^i$$ E49

Using (3.2), we can rewrite (3.15) in terms of GMs as follows:

$$y_p\left[N-p\right]=\frac{1}{p!}\sum _{i=0}^p{s}_1\left(p,i\right)m_i\mathrm{ }$$ E50

Now by taking the inverse of (3.16), the GMs can be obtained in terms of the digital filter outputs thus:

$$m_p=\sum _{r=0}^{p}r!s_2\left(p,r\right)y_r\left[N-r\right]$$ E51

where $s_2\left(p,r\right)$ are the Stirling numbers of the second kind [28], and the Stirling numbers of the first and second kind can be considered to be inverses of one another:

$$\sum _{p=0}^{\max \left\{i,r\right\}}{\left(-1\right)}^{p-r}{s}_1\left(p,i\right)s_2\left(r,p\right)={\delta }_{ir}\mathrm{ }$$ E52

where ${\delta }_{ir}$ is the Kronecker delta.

Notice now, for the $p$ order, it can be shown that the digital filter outputs are sampled at $N-p$ , unlike the previous works which were sampled at $N$ or later instances of $N$ [19]-[20]-[21]. As the order $\frac{p}{2}$ 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:

$$m_{p,q}=\sum _{r=0}^p\sum _{s=0}^{q}r!s!s_2\left(p,r\right)s_2\left(q,s\right)y_{rs}\left[N-r,N-s\right]$$ E53

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:

$x\left[m,n\right]=\left[\begin{array}{cc}\begin{array}{cc}111& 114\\ 109& 101\end{array}& \begin{array}{cc}103& 116\\ 113& 108\end{array}\\ \begin{array}{cc}106& 102\\ 107& 110\end{array}& \begin{array}{cc}112& 104\\ 105& 115\end{array}\end{array}\right]$

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
${\mathit{y}}_{00}$	1736	1736
${\mathit{y}}_{01}$	4326	4326
${\mathit{y}}_{02}$	8651	4325
${\mathit{y}}_{03}$	15148	2172
${\mathit{y}}_{10}$	4358	4358
${\mathit{y}}_{11}$	10870	10870
${\mathit{y}}_{12}$	21750	10880
${\mathit{y}}_{20}$	8742	4384
${\mathit{y}}_{21}$	21811	10941
${\mathit{y}}_{30}$	15331	2205

Table 1.

A comparison of filter output values between [20] and the proposed method for an artificial image, $x\left[m,n\right]$ , up to third order.

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 $N\times N$ and GM up to order of $s$ , where $s = \left(p+q\right)$ , the number of additions and multiplications for the proposed method, [19] and [20] are shown in Table 2.

Algorithm	Additions(Digital filter stages)	Additions (Digital filter outputs to GMs)	Multiplications (Digital filter outputs to GMs)
[19]	$\left(s+1\right)\left(N+\frac{s+2}{2}\right)\left(N+1\right)$	$\frac{s\left(s+1\right)\left(s+2\right)\left(s+7\right)}{24}$	$\frac{s^4+10s^3+23s^2-34s-24}{24}$
[20]	$\left(s+1\right)\left(N+\frac{s+2}{2}\right)N$	$\frac{s\left(s-1\right)\left(s^2+3s+14\right)}{24}$	$\frac{s\left(s-1\right)\left(s^2+3s+14\right)}{24}$
Proposed method	$\left(s+1\right)\left[N\left(N+2\right)-\frac{\left(s+2\right)\left(s-3\right)}{6}\right]$	$\frac{s\left(s-1\right)\left(s^2+3s+14\right)}{24}$	$\frac{s\left(s-1\right)\left(s^2+3s+14\right)}{24}$

Table 2.

Complexity analysis of GMs computation using digital filters for image of size $N\times N$ and maximum order of $s=p+q$ .

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 $N = 512$ and $s=45$ , the number of additions needed in the filter stage for [20] 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 45^th order is shown in Table 3.

Algorithm	Additions	Multiplications
[19]	12847524	210795
[20]	12791451	179355
Proposed method	12269949	179355

Table 3.

Complexity analysis of GMs computation using digital filters for image of size $512\times 512$ and $s=45$ .

For a $128\times 128$ grayscale image, the advantage of the proposed filter structure as compared to [19] and [20] is clearly depicted in Figure 4.

Figure 4.

Number of additions for a $128\times 128$ grey-scaled image.

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 ($\mathit{s}=\mathit{p}+\mathit{q}$ )	[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

Table 4.

CPU elapsed time in milliseconds for the $128\times 128$ Pepper’s test image.

Moment order ($\mathit{s}=\mathit{p}+\mathit{q}$ )	[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

Table 5.

CPU elapsed time in milliseconds for the $512\times 512$ Lena’s test image.

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.

Figure 5.

Test images: (a) Peppers and (b) Lena.

Figure 6.

Linear scale of CPU time in seconds for the $128\times 128$ gray-scale peppers image.

Figure 7.

Linear scale of CPU time in seconds for the $512\times 512$ gray-scale Lena image.

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 all-pole digital filters using 1-D and 2-D Z-transforms [32]. 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 [19]. The 2-D Z-transform for the image, $f\left[m,n\right]$ is given as:

$$F\left(z_1,z_2\right)=\sum _{m=1}^{+\mathrm{\infty }}\sum _{n=1}^{+\mathrm{\infty }}f\left[m,n\right]z_1^{-m}{z}_2^{-n}$$ E54

The impulse response for a 2-D image becomes:

$$h_{p,q}\left[m,n\right]=\left(\genfrac{}{}{0pt}{}{m+p}{m}\right)u\left[m\right]\left(\genfrac{}{}{0pt}{}{n+q}{n}\right)u\left[n\right]$$ E55

and the transfer function $H_{p,q}\left(z_1,z_2\right)$ , in the 2-D Z-transform domain for this filter structure is shown as

$$H_{p,q}\left(z_1,z_2\right)=\frac{1}{{\left(1-z_1^{-1}\right)}^{p+1}{\left(1-z_2^{-1}\right)}^{q+1}}$$ E56

Using the above transfer function, the relationship between the input and the output of the digital filter is:

$$Y_{p,q}\left(z_1,z_2\right)=\frac{X\left(z_1,z_2\right)}{{\left(1-z_1^{-1}\right)}^{p+1}{\left(1-z_2^{-1}\right)}^{q+1}}$$ E57

Based on (4.4), the zero order of the digital filter output is derived as

$$Y_{00}\left(z_1,z_2\right)=\frac{X\left(z_1,z_2\right)}{\left(1-z_1^{-1}\right)\left(1-z_2^{-1}\right)}$$ E58

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:

$$Y_{p+1,q}\left(z_1,z_2\right)=\frac{Y_{p,q}\left(z_1,z_2\right)}{1-z_1^{-1}}\mathrm{ }$$ E59

$$Y_{p,q+1}\left(z_1,z_2\right)=\frac{Y_{p,q}\left(z_1,z_2\right)}{1-z_2^{-1}}\mathrm{ }$$ E60

Figure 8.

Recurrence relationship between the digital filter outputs of the row and column.

By taking the inverse 2-D Z- transform of (4.6) and (4.7), we get the following:

$$y_{p+1,q}\left[m,n\right]=y_{p+1,q}\left[m-1,n\right]+y_{p,q}\left[m,n\right]$$ E61

$$y_{p,q+1}\left[m,n\right]=y_{p,q+1}\left[m,n-1\right]+y_{p,q}\left[m,n\right]$$ E62

The implementation of proposed digital filter structure for generating moments up to $\left(p+q\right)$ orders is shown in Figure 9.

Figure 9.

Reduced digital filters for generating the 2-D geometric moments up to $\left(p+q\right)$ order.

Figure 10.

Digital filters for generating the 2-D geometric moments up to $\left(p+q\right)$ order used in [2] and [8].

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, $y_{pq}$ and $y_p$ used in the rows. In the proposed model, the outputs $y_{00}$ , $y_{10}$ ,..., $y_{p0}$ occur at the row filter, unlike in [19] and [20], they occur at the column filters. Hence, the difference in savings of digital filters used in the proposed method is determined by the maximum $p$ order. for example, in the design of the 40^th order geometric moments, where the maximum $p$ order is 40, and thus the number of digital filters used in proposed method will be 40 digital filters less than [19] and [20].

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

$$\begin{array}{l}{y}_0\left[N\right]=\sum _{k=1}^{N}x\left[k\right]h_0\left[N-k\right]={\mu }_0\\ y_1\left[N\right]=\sum _{k=1}^{N}x\left[k\right]h_1\left[N-k\right]=\sum _{k=1}^{N}x\left[k\right]\left(N-k+1\right)=\left(N+1\right){\mu }_0-{\mu }_1\\ y_2\left[N\right]=\sum _{k=1}^{N}x\left[k\right]h_2\left[N-k\right]=\sum _{k=1}^{N}x\left[k\right]\frac{1}{2}\left(N-k+1\right)\left(N-k+2\right)=\frac{1}{2}\left(N+1\right)\left(N+2\right){\mu }_0-{\frac{1}{2}\left(2N+3\right)\mu }_1+\frac{1}{2}{\mu }_2\end{array}$$ E63

Hence by solving them, the above geometric moments can be obtained in terms of the digital filters outputs.

$$\begin{array}{l}{\mu }_0=y_0\\ {\mu }_1={\left(N+1\right)y}_0-y_1\\ {\mu }_2={{\left(N+1\right)}^{2}y}_0-\left(2N+3\right)y_1+2y_2\end{array}$$ E64

A matrix notation showing the above relationship between the geometric moments and the digital filter outputs as expressed

$${\mathit{\mu }}_{\mathit{P}}={\mathit{C}}_{\mathit{N}}{\mathit{Y}}_{\mathit{P}}$$ E65

where ${\mathit{\mu }}_{\mathit{P}}$ is the geometric moment vector, ${\mathit{Y}}_{\mathit{P}}$ is the digital filter output vector, and ${\mathit{C}}_{\mathit{N}}$ is a square matrix that a recurrence relationship between this matrix elements is given as

$$C_{pr}=\left\{\begin{array}{c}\begin{array}{c}0 ; p<r\\ {\left(-1\right)}^{p}p! ; p=r\end{array}\\ \begin{array}{c}{\left(N+1\right)}^p ; r=0\\ -p{C}_{p-1,r-1}+p\sum _{k=r}^{p-1}\frac{C_{p-1,k}}{2^{k-r+1}\times 3^{⌊\frac{k-r+1}{2}⌋}} ; oth.\end{array}\end{array}\right.$$ E66

where, $⌊\bullet ⌋$ 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, ${\mathit{C}}_{\mathit{N}}$ . For a 2-D image of dimensions $\times N$ , the geometric moments can be obtained from

$${\mathit{\mu }}_{\mathit{p}\mathit{q}}={\mathit{C}}_{\mathit{M}}{\mathit{Y}}_{\mathit{p}\mathit{q}}^{\mathit{T}}{{\mathit{C}}_{\mathit{N}}}^{\mathit{T}}$$ E67

Also, the summation forms of (4.12) and (4.14) can be written as:

$${\mu }_p=\sum _{r=0}^p{C}_{pr}{y}_r\mathrm{ }$$ E68

$${\mu }_{pq}=\sum _{r=0}^p{\sum _{s=0}^q{C}_{pr}C}_{qs}{y}_{sr}$$ E69

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 [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 $p-$ 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.

Figure 11.

Digital filter structure for generating up to third order geometric moments for 2-D image. (a) proposed model and (b) existing model.

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 $2\times 3$ 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:

$x\left[m,n\right]=\left[\begin{array}{ccc}5& 3& 6\\ 2& 4& 1\end{array}\right]$

Consider the dimension of the input image is $2\times 3$ , it means the endpoint of the filter outputs, is $6$ . Therefore, all generated outputs by the row filters are defined at different intervals till $6$ , 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 $x^R$ .

$\mathit{n}$	0	1	2	3	4	5	6
${\mathit{x}}^{\mathit{R}}$	0	1	4	2	6	3	5
${\mathit{y}}_0$	0	1	5	7	6	9	14
${\mathit{y}}_1$	0	1	6	13	6	15	29
${\mathit{y}}_2$	0	1	7	20	6	21	50
${\mathit{y}}_3$	0	1	8	28	6	27	77

Table 6.

State table method used in [8] for obtaining row filter outputs.

$\mathit{n}$	3	6	$\mathit{n}$	3	6	$\mathit{n}$	3	6	$\mathit{n}$	3	6
${\mathit{y}}_0$	7	14	${\mathit{y}}_1$	13	29	${\mathit{y}}_2$	20	50	${\mathit{y}}_3$	28	77
${\mathit{y}}_{00}$	7	21	${\mathit{y}}_{10}$	13	42	${\mathit{y}}_{20}$	20	70	${\mathit{y}}_{30}$	28	105
${\mathit{y}}_{01}$	7	28	${\mathit{y}}_{11}$	13	55	${\mathit{y}}_{21}$	20	90
${\mathit{y}}_{02}$	7	35	${\mathit{y}}_{12}$	13	68
${\mathit{y}}_{03}$	7	42

Table 7.

State table method used in [8] for obtaining column filter outputs.

The highlighted outputs can be collected as $\mathit{Y}$ matrix in (4.12) and the coefficients matrix ( $\mathit{D}$ ) as defined in (3.9), will generate the third order moments’ set of the artificial image as follows:

$$\begin{array}{l}{\mu }_{00}=21\mathrm{ },\mathrm{ }{\mu }_{01}=42\mathrm{ },\mathrm{ }{\mu }_{02}=98\mathrm{ },\mathrm{ }{\mu }_{03}=252\\ {\mu }_{10}=28\mathrm{ },\mathrm{ }{\mu }_{11}=55\mathrm{ },\mathrm{ }{\mu }_{12}=125\\ {\mu }_{20}=42\mathrm{ },\mathrm{ }{\mu }_{21}=81\\ {\mu }_{30}=70\end{array}\mathrm{ }$$ E70

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 $p-$ order. Furthermore, in this method it does not need to reverse of the input sequence.

$\mathit{n}$	0	1	2	3	4	5	6
${\mathit{x}}^{\mathit{T}}$	0	5	2	3	4	6	1
$\mathit{y}$	0	5	7	3	7	6	7
${\mathit{y}}^{\mathit{T}}$	0	5	3	6	7	7	7
${\mathit{y}}_{00}$	0	5	8	14	7	14	21
${\mathit{y}}_{10}$	0	5	13	27	7	21	42
${\mathit{y}}_{20}$	0	5	18	45	7	28	70
${\mathit{y}}_{30}$	0	5	23	68	7	35	105

Table 8.

State table of proposed method for obtaining row filter outputs.

$\mathit{n}$	3	6	$\mathit{n}$	3	6	$\mathit{n}$	3	6	$\mathit{n}$	3	6
${\mathit{y}}_{00}$	14	21	${\mathit{y}}_{10}$	27	42	${\mathit{y}}_{20}$	45	70	${\mathit{y}}_{30}$	68	105
${\mathit{y}}_{01}$	14	35	${\mathit{y}}_{11}$	27	69	${\mathit{y}}_{21}$	45	115
${\mathit{y}}_{02}$	14	49	${\mathit{y}}_{12}$	27	96
${\mathit{y}}_{03}$	14	63

Table 9.

State table of proposed method for obtaining column filter outputs.

Based on (4.13) and (4.14), we can derive the digital filter outputs’ matrix ( $\mathit{Y})\mathit{ }$ and the coefficients matrices ( ${\mathit{C}}_{\mathit{M}}\mathit{ },\mathit{ }{\mathit{C}}_{\mathit{N}}$ ), respectively. Then, the set of third order moments are obtained as (4.17).

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.

Figure 12.

Test images (a) Pepper and (b) Lena.

Figure 13.

Comparison of the number of additions in digital filter part for [19] and proposed method for (a) Pepper image (b) Lena image.

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 $N, N-1,\dots .N+p$ , where $p$ is the maximum moment order for an $N\times N$ 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 [21] and Wong and Siu [20] 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 $N$ 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 $p$ -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.