Open access peer-reviewed chapter

Digital Filter Implementation of Orthogonal Moments

By Barmak Honarvar Shakibaei Asli and Raveendran Paramesran

Submitted: March 24th 2012Reviewed: August 8th 2012Published: January 16th 2013

DOI: 10.5772/52191

Downloaded: 1594

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 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 N × Nimage, the digital filter output values for row filtering are sampled at N+2, N+3, N+4, , N+p+2, where pis 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, , N-p,where the lowest digital filter output value, sampled at N-pis for the highest order. Meanwhile, this set of output values starts to decrease after p/2moment 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 xpyq. The p+qth order two-dimensional GMs are denoted by mpq, and can be expressed as

mpq=-+xpyqfx,ydxdy E1

where fx,yis the image intensity function. GMs of low orders have an intuitive meaning,m00is a “mass” of the image (for binary images, m00is 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 m02and m20describe 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 m02/m00and m20/m00, respectively.

Another popular choice of the polynomial basis x+iypx-iyqwhere iis the imaginary unit, leads to complex moments

cpq=-+x+iypx-iyqfx,ydxdy E2

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

cpq=k=0pl=0qpkql-1q-lip+q-k-jmk+j,p+q-k-jE3

and vice versa

mpq=k=0pl=0qpkql-1q-l2p+qiqck+l,p+q-k-lE4

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 pkj x, yis orthogonal, i.e. if its elements satisfy the condition of orthogonality

GPpqx,yPmnx,ydxdy=0 E5

or weighted orthogonality

Gwx,yPpqx,yPmnx,ydxdy=0 E6

for any indexes pmor qn, 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

fx,y=jkMkjPkjx,y 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

λpq=2p+12q+14-1+1PpxPqyfx,ydxd; p,q=0, 1, 2,  E8

where Pnxis the nth degree Legendre polynomial (expression by the so-called Rodrigues’ formula)

Ppx=12pp!dpdxpx2-1pE9

and the image fx, yis mapped into the square -1, 1×-1, 1. The Legendre polynomials of low degrees expressed in terms of xpare

P0x=1, P1x=x,P2x=123x2-1,P3x=125x3-3x, P4x=1835x4-30x2+3.E10

The relation of orthogonality is

-11PpxPqxdx=22q+1δpq E11

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

P0x=1, P1x=x,Pp+1x=2p+1p+1xPpx-pp+1Pp-1x 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

Apq=p+1π02π01Vpq*r,θfr,θrdrdθ,   p=0, 1, 2,  q=-p, -p+2, , p  E13

i.e. the difference n - lis always even. The asterisk means the complex conjugate. The Zernike polynomials are defined as products

Vpqr,θ=Rpqreiqθ  E14

where the radial part is

Rpqr=k=q,q+2,  pBpqkrkE15

The coefficients

Bpqk=-1p-k2p+k2!p-k2!k+q2!k-q2!  E16

can be used for conversion from geometric moments,

Apq=p+1πk=q,q+2,  pj=0k-q2l=0qk-q2jqlwlBpqkmk-2j-l,2j+l E17

where

w=-i  ;  q>0i     ;   q0  E18

The Zernike polynomials satisfy the relation of orthogonality

02π01Vpq*r,θVklr,θrdrdθ=πp+1δkpδlqE19

The recurrence relation for the radial part is

Rpqr=2prp+qRp-1,q-1r-p-qp+qRp-2.qr E20

Computation of the Zernike polynomials by this formula must commence with

Rppr=Rp,-pr=rp  , p=0, 1,   

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 p+qof an image intensity function fn,mwith size N×Mis defined as

Tpq=Ap,NAq,Mn=0N-1m=0M-1tpntqmfn,m E21

where tpnis the pth order orthogonal discrete Tchebichef polynomial defined by [8]

tpn=p!k=0p-1p-kN-1-kp-kp+kpnkE22

and

Ap,N=βp,Nρp,N

where βp,Nis a normalization factor. The simplest choice of this factor is Np. The recurrence relation of Tchebichef polynomials with respect to the chosen order is:

p+1tp+1n-2p+12n-N+1tpn+pN2-p2tp-1n=0E23

where p1and the first two polynomials are t0n=1and t1n=2n-N+1. The orthogonality property satisfies the following squared-norm:

ρp,N=2p!N+p2p+1E24

2.4.2. Krawtchouk moments

The definition of the nth order classical Krawtchouk polynomial is defined as

Knx;p,N=k=0nak,n,pxk=F1-n,-x;-N;1p2 E25

where x,n=0, 1, 2, , N, N>0, p0,1and F12is the generalized hypergeometric function

F1a,b;c;z2=k=0akbkckzkk!  E26

and xkis the Pochhammer symbol given by

xk=xx+1x+2x+k-1k1  and x0=1E27

The normalized and weighted Krawtchouk polynomials K-nx;p,Nare defined as [10]

K-nx;p,N=Knx;p,Nwx;p,Nρn;p,NE28

where the weight function, wand the square norm, ρare given as

wx;p,N=Nxpx1-pN-x E29

and

ρn;p,N=p-1pnn!-Nn E30

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

pn-NK-n+1x;p,N=ApN-2n+n-xK-nx;p,N-Bn1-pK-n-1x;p,NE31

where

A=1-pn+1pN-n

B=1-p2n+1np2N-nN-n+1

with

K-0x;p,N=wx;p,N

K-1x;p,N=1-1Npxwx;p,N.

The 2D Krawtchouk moment of order n+mof an image intensity function fx,ywith size N×Mis defined as [16]

Qnm=x=0N-1y=0M-1K-nx;p1,N-1K-my;p2,M-1fx,yE32

The orthogonality property leads to the following inverse moment transform

fx,y=n=0N-1m=0M-1QnmK-nx;p1,N-1K-my;p2,M-1E33

If only the moments of order up to Nmax ,Mmaxare computed, then the reconstructed image in (2.30) can be approximated by

f~x,y=n=0Nmaxm=0MmaxQnmK-nx;p1,N-1K-my;p2,M-1E34

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 16th order. The one dimensional GMs of order pfor a N-length sequence xnis defined in this model as

mp=n=0N-1npxnE35

One reason for using digital filters as a moment generator is based on the convolution of the aforementioned sequence with impulse response, npun, where unis the unit step function. Hence, the output of the digital filter ypevaluated at the point n = N-1can be expressed:

ypN=k=0N-1xkN-kp  E36

where xnis the reversed sequence. Figure 1 shows the structure of a single pole digital filter with transfer function 1z-1, which is equivalent to an accumulator with unity feedback. This accumulator has a delay in the feed-forward path. For pcascaded filters, the corresponding transfer function is given by

Hpz=1z-1p+1 E37

Figure 1.

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

The 1D cascaded filters structure is shown in Figure 2, where H0z=1z-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

mp=r=0pCp,ryr  E38

where yris the rth digital filter output and Cp,ris a matrix of coefficients directly obtained from the impulse responses of the all-pole digital filters as given in [27]:

Cp,r=0;r>p-1p;r=0,p0rCp-1,r-1-r+1Cp-1,r;r>0,p>0 E39

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

mp,q=r=0pCp,rs=0qCq,syr,s  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

Hpz=11-z-1p+1E41

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:

mp=r=0pDp,ryrE42

where the coefficients of Dp,rare obtained from the following recurrence formula shown in [23].

Dp,r=0;p>0,r=01;p=0,r=0rDp-1.r-1-Dp-1,r;othersE43

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

mp,q=r=0pDp,rs=0qDq,syr,s 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 hpn= npun, where unis the unit step function and pis the moment order. Now, assume the input of the digital filter is given as xnas mentioned in (3.2). Based on the convolution theorem, the output, ynis therefore

ypn=xn*hpnE45

Using the digital filter as shown in Figure. 3 and changing the unit step function to un+pto accommodate the sampling of the digital filter outputs at earlier instances, we get the following

ypn=xn*n+ppun+p =k=0n+pxkn-k+pp   E46

Substituting, n=N-pyields

ypN-p=k=0NxkN-kpE47

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

ypN-p=1p!k=0Ni=0ps1p,ixkN-kiE48

where s1p,iare the Stirling numbers of the first kind [28], which satisfy

N-k!N-k-p!=i=0ps1p,iN-kiE49

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

ypN-p=1p!i=0ps1p,imi E50

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

mp=r=0pr!s2p,ryrN-rE51

where s2p,rare 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:

p=0maxi,r-1p-rs1p,is2r,p=δir E52

where δiris the Kronecker delta.

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

mp,q=r=0ps=0qr!s!s2p,rs2q,syrsN-r,N-sE53

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:

xm,n=111114109101103116113108106102107110112104105115 

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 outputsFilter structure output values[20]Proposed structure output values
y0017361736
y0143264326
y0286514325
y03151482172
y1043584358
y111087010870
y122175010880
y2087424384
y212181110941
y30153312205

Table 1.

A comparison of filter output values between [20] and the proposed method for an artificial image, xm,n, 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×Nand GM up to order of s, where s = p+q, the number of additions and multiplications for the proposed method, [19] and [20] are shown in Table 2.

AlgorithmAdditions(Digital filter stages)Additions (Digital filter outputs to GMs)Multiplications (Digital filter outputs to GMs)
[19]s+1N+s+22N+1ss+1s+2s+724s4+10s3+23s2-34s-2424
[20]s+1N+s+22N
ss-1s2+3s+1424ss-1s2+3s+1424
Proposed methods+1NN+2-s+2s-36ss-1s2+3s+1424ss-1s2+3s+1424

Table 2.

Complexity analysis of GMs computation using digital filters for image of size N×Nand 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 = 512and 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 45th order is shown in Table 3.

AlgorithmAdditionsMultiplications
[19]12847524210795
[20]12791451179355
Proposed method12269949179355

Table 3.

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

For a 128×128grayscale 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 × 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 ( s = p + q )[19][20]Proposed method
50.40.390.388
151.121.1041.05
252.031.971.81
353.283.142.82
455.154.874.32
557.967.486.63

Table 4.

CPU elapsed time in milliseconds for the 128×128Pepper’s test image.

Moment order ( s = p + q )[19][20]Proposed method
56.036.026.00
1516.26416.22216.018
2526.81726.72226.13
3537.86637.67736.494
4549.66349.32547.343
5562.54261.98258.99

Table 5.

CPU elapsed time in milliseconds for the 512×512Lena’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 × 128 gray-scale peppers image.

Figure 7.

Linear scale of CPU time in seconds for the 512 × 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, fm,nis given as:

Fz1,z2=m=1+n=1+fm,nz1-mz2-nE54

The impulse response for a 2-D image becomes:

hp,qm,n=m+pmumn+qnunE55

and the transfer function Hp,qz1,z2, in the 2-D Z-transform domain for this filter structure is shown as

Hp,qz1,z2=11-z1-1p+11-z2-1q+1E56

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

Yp,qz1,z2=Xz1,z21-z1-1p+11-z2-1q+1E57

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

Y00z1,z2=Xz1,z21-z1-11-z2-1E58

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:

Yp+1,qz1,z2=Yp,qz1,z21-z1-1 E59
Yp,q+1z1,z2=Yp,qz1,z21-z2-1 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:

yp+1,qm,n=yp+1,qm-1,n+yp,qm,n E61
yp,q+1m,n=yp,q+1m,n-1+yp,qm,nE62

The implementation of proposed digital filter structure for generating moments up to p+qorders is shown in Figure 9.

Figure 9.

Reduced digital filters for generating the 2-D geometric moments up to p + q order.

Figure 10.

Digital filters for generating the 2-D geometric moments up to p + q 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, ypqand ypused in the rows. In the proposed model, the outputs y00, y10,..., yp0occur 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 porder. for example, in the design of the 40th order geometric moments, where the maximum porder 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

y0N=k=1Nxkh0N-k=μ0y1N=k=1Nxkh1N-k=k=1NxkN-k+1=N+1μ0-μ1y2N=k=1Nxkh2N-k=k=1Nxk12N-k+1N-k+2=12N+1N+2μ0-122N+3μ1+12μ2E63

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

μ0=y0μ1=N+1y0-y1μ2=N+12y0-2N+3y1+2y2E64

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

μP=CNYPE65

where μPis the geometric moment vector, YPis the digital filter output vector, and CNis a square matrix that a recurrence relationship between this matrix elements is given as

Cpr=0                                                                           ;      p<r-1pp!                                                              ;       p=rN+1p                                                             ;       r=0-pCp-1,r-1+pk=rp-1Cp-1,k2k-r+1×3k-r+12   ;    oth.E66

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, CN. For a 2-D image of dimensions ×N, the geometric moments can be obtained from

μpq=CMYpqTCNTE67

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

μp=r=0pCpryr E68
μpq=r=0ps=0qCprCqsysrE69

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×3to generate up to third order of geometric moments is considered. The intensity function of the test image is represented by the following input matrix:

xm,n=536241 

Consider the dimension of the input image is 2×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 xR.

n0123456
x R0142635
y 001576914
y 10161361529
y 20172062150
y 30182862777

Table 6.

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

n36n36n36n36
y 0714y11329y22050y32877
y 00721y101342y202070y3028105
y 01728y111355y212090
y 02735y121368
y 03742

Table 7.

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

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

μ00=21 , μ01=42 , μ02=98 , μ03=252μ10=28 , μ11=55 , μ12=125μ20=42 , μ21=81μ30=70 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.

n0123456
x T0523461
y0573767
y T0536777
y 000581471421
y 1005132772142
y 2005184572870
y 30052368735105

Table 8.

State table of proposed method for obtaining row filter outputs.

n36n36n36n36
y 001421y102742y204570y3068105
y 011435y112769y2145115
y 021449y122796
y 031463

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 (Y) and the coefficients matrices (CM , CN), 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,.N+p, where pis the maximum moment order for an N×Nimage. 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 Nwhen 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.

© 2013 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Barmak Honarvar Shakibaei Asli and Raveendran Paramesran (January 16th 2013). Digital Filter Implementation of Orthogonal Moments, Digital Filters and Signal Processing, Fausto Pedro García Márquez and Noor Zaman, IntechOpen, DOI: 10.5772/52191. Available from:

chapter statistics

1594total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Two-Rate Based Structures for Computationally Efficient Wide- Band FIR Systems

By Håkan Johansson and Oscar Gustafsson

Related Book

First chapter

Digital Filters for Maintenance Management

By Fausto Pedro García Márquez and Diego José Pedregal Tercero

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us