A comparison of filter output values between [20] and the proposed method for an artificial image,

## 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

The method of computation we propose in this work attempts to reduce computational complexity – and save time through a reduction in the number of additions – by addressing the problems arising from: 1) The increase in digital filter output values as the order of moment’s increases and 2) the consequent use of positive and negative coefficient multipliers to make them exact. To circumvent the problems arising from these two facts, we are proposing the use of only positive coefficient multipliers which then makes it possible to use lower digital filter outputs as the order of the moment increases in generation of GMs. As will be discussed in greater detail in Section 3, the proposed method is based on the formulation and understanding of the impulse response of the digital filters, the unit step function to be used and their relationship with GMs. This formulation makes it possible for the digital filter outputs to be evaluated at earlier instances at

Recently, another types of discrete orthogonal moments such as Krawtchouk, dual Hahn, Racah, Meixner and Hahn moments have been introduced in image analysis community [16]–[17]. It was shown that they have better image representation capability than the continuous orthogonal moments.

One main difficulty concerning the use of moments as feature descriptors is their high computational complexity. To solve this problem, a number of fast algorithms have been reported in the literature [14]–[19]. Most of them concentrated on the fast computation of geometric moments and continuous orthogonal moments. This work examines various aspects; both theory and applications of image moment implementation using digital filter structures. Since these aspects can be discussed rather independently, we devote each chapter to the discussion of one particular aspect of moment structures. The following is a summary of contents of the sections.

**Section 2: Orthogonal Moments.**Numerous types of orthogonal polynomial, both in 1D and 2D, have been described in traditional mathematical literature. In this chapter we present a survey of orthogonal moments that are of importance in image analysis. The literature on orthogonal moments is very broad, namely in the area of practical applications, and our survey has no claim on completeness. We divide orthogonal polynomials and orthogonal moments into two basic groups. The polynomials*orthogonal on a rectangle*originate from 1D orthogonal polynomials whose 2D versions were created as products of 1D polynomials in*x*and*y*. The main advantage of the moments orthogonal on a rectangle is that they preserve the orthogonality even on the sampled image. They can be made 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 ^{th} order two-dimensional GMs are denoted by

where *center of gravity* or *centroid* of the image. Second-order moments *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

Another popular choice of the polynomial basis *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

or weighted orthogonality

for any indexes *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

There have been many works describing the use of the Legendre moments in image processing, e.g. references [29] and [30], among many others. The *Legendre moments* are defined as

where ^{th} degree *Legendre polynomial* (expression by the so-called Rodrigues’ formula)

and the image

The relation of orthogonality is

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

#### 2.3.2. Zernike moments

*Zernike moments* (ZMs) were introduced into image analysis about 30 years ago by Teague [9] who used ZMs to construct rotation invariants. He used the fact that the ZMs keep their magnitude under arbitrary rotation. He also showed that the Zernike invariants of the second and third orders are equivalent to the Hu invariants when expressed in terms of geometric moments. He presented the invariants up to the eighth order in explicit form but no general rule about how to derive them was given. Later, Wallin [31] described an algorithm for the formation of rotation invariants of any order. Numerical properties and possible applications of ZMs in image processing among others. ZMs of the *n*th order with repetition *l* are defined as

i.e. the difference *Zernike polynomials* are defined as products

where the radial part is

The coefficients

can be used for conversion from geometric moments,

where

The Zernike polynomials satisfy the relation of orthogonality

The recurrence relation for the radial part is

Computation of the Zernike polynomials by this formula must commence with

### 2.4. Discrete moments

There is a group of orthogonal polynomials defined directly on a series of points and therefore they are especially suitable for digital images. Some of these polynomials such as Tchebichef, Krawtchouk, Hahn, dual Hahn and Meixner polynomials.

#### 2.4.1. Tchebichef moments

The 2D TMs of order

where ^{th} order orthogonal discrete Tchebichef polynomial defined by [8]

and

where

where

#### 2.4.2. Krawtchouk moments

The definition of the ^{th} order classical Krawtchouk polynomial is defined as

where

and

The normalized and weighted Krawtchouk polynomials

where the weight function,

and

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

where

with

The 2D Krawtchouk moment of order

The orthogonality property leads to the following inverse moment transform

If only the moments of order up to

## 3. Formulation of geometric moments using digital filters

This section first reviews the generation of GMs using digital filter structure as proposed by Hatamian [19]. This is then followed by a review of the improved version used by Wong and Siu [20].

### 3.1. Hatamian’s model

Hatamian proposed the all-pole digital filter structure to compute GMs up to the 16^{th} order. The one dimensional GMs of order

One reason for using digital filters as a moment generator is based on the convolution of the aforementioned sequence with impulse response,

where

The 1D cascaded filters structure is shown in Figure 2, where

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

where ^{th }digital filter output and

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

To overcome this problem, Wong and Siu [20] moved the delay unit to the feedback path of the filter, as shown in Figure 3. The transfer function is given as

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

where the coefficients of

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

### 3.3. Proposed method based on the lower output values of digital filters

We begin with the one-dimensional case, where the results can be easily extended to two-dimensional. Consider a digital filter with impulse response

Using the digital filter as shown in Figure. 3 and changing the unit step function to

Substituting,

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

where

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

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

where

where

Notice now, for the

### 3.4. Experimental studies

A set of experiments were carried out to validate the theoretical framework developed in the previous sections and to evaluate the performance of the proposed structure. This section is divided into 3 parts. In the first subsection, an artificial image of size 4×4 is used to generate GMs up to third order. The computational complexity of three algorithms – the algorithms of [19], [20] and the proposed method – is then analyzed and discussed in the second subsection. In the third subsection, the speed of the proposed method is compared with the speed achieved using [19] and [20].

#### 3.4.1. Artificial test image

rtificial test image of size 4×4 was used to prove the validity of the proposed approach. In this case, the digital filter outputs up to third order were generated. The intensity function of the test image is given in the following matrix:

The difference between the digital filter output values for [20] and proposed structure is shown in Table 1. It is clear that for orders higher than one, the proposed output values are much lower than [20] as the order increases.

Digital filter outputs | Filter structure output values[20] | Proposed structure output values |

1736 | 1736 | |

4326 | 4326 | |

8651 | 4325 | |

15148 | 2172 | |

4358 | 4358 | |

10870 | 10870 | |

21750 | 10880 | |

8742 | 4384 | |

21811 | 10941 | |

15331 | 2205 |

#### 3.4.2. Computational complexity

The advantage of the proposed method lies in the smaller digital filter output values as compared to [19] and [20]. However, it would still be useful to study the computational complexity of these three methods and the direct method in term of the number of additions and multiplications. The proposed method, [19] and [20] consist of two main steps. Digital filter outputs are obtained from the respective digital filter structure. Then, these outputs are linearly combined to compute GMs.

For a grayscale image of size

Algorithm | Additions(Digital filter stages) | Additions (Digital filter outputs to GMs) | Multiplications (Digital filter outputs to GMs) |

[19] | |||

[20] | |||

Proposed method |

It can be seen that even though the complexity of the linear combination stage for the proposed method is the same as [20], there is saving in the number of additions at the digital filters stage. This can be clearly shown in the example below. For ^{th} order is shown in Table 3.

Algorithm | Additions | Multiplications |

[19] | 12847524 | 210795 |

[20] | 12791451 | 179355 |

Proposed method | 12269949 | 179355 |

For a

#### 3.4.3. Speed performance and comparison studies

The computation speed of the proposed method is compared with [19] and [20]. CPU elapsed time is used in the evaluation process in all the performed numerical experiments. The codes were all written in MATLAB7 and simulations were run with a 3GHz Intel Core2 with 2GB RAM and the average time is used in the discussion. The images used for the experiments were the Pepper and Lena images, as shown in Figure 5.

Table 4 shows the simulation time for GMs computation on the Pepper image of size 128×128 for orders of 5 to 55, in a step of 10. The same experiment was repeated on the Lena image of size 512×512. The simulation times are shown in Table 5.

Moment order ( s = p + 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 |

Moment order ( s = p + 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 |

The tables clearly show that the proposed method requires less time than [19] and [20] to compute GMs of the same order. They also show that the time saving increases as the order of moments increases. In Figure 6 and Figure 7 we provide a comparison of required CPU time between [19], [20] and the proposed method.

## 4. A Reduced 2D digital filter structures for fast computation of geometric moments

In the previous works, the linear transformation is performed using an external PC to relate the outputs of the digital filter structure to generate the moments. However, finding of a relationship between the geometric or orthogonal moments and the digital filters outputs has been stood as the main meaning of similar works [19]-[20].

In all the above aforementioned literatures, the basic concept involved the computation of geometric and other types of moments using the accumulator grid structure has remain unchanged over the past decades.

First we summarize the designing modality of 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,

The impulse response for a 2-D image becomes:

and the transfer function

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

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

Thereafter, a recurrence relationship between the previous and the next outputs of each digital filter for the row and columns as shown in Figure 8 can be obtained:

By taking the inverse 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

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, ^{th} order geometric moments, where the maximum

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

where, *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,

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 [19]. Figure.3. shows the proposed digital filter structure and the structure used in [19]. As can be seen from Figure 11(a) and (b), the proposed filter structure used three less digital filters. The difference between them is maximum

#### 4.2.1. Artifical test image

Artificial test images of small size are used to prove validity of the proposed architecture. To illustrate the workings, an artificial image with size of

Consider the dimension of the input image is

n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

x R | 0 | 1 | 4 | 2 | 6 | 3 | 5 |

y 0 | 0 | 1 | 5 | 7 | 6 | 9 | 14 |

y 1 | 0 | 1 | 6 | 13 | 6 | 15 | 29 |

y 2 | 0 | 1 | 7 | 20 | 6 | 21 | 50 |

y 3 | 0 | 1 | 8 | 28 | 6 | 27 | 77 |

n | 3 | 6 | n | 3 | 6 | n | 3 | 6 | n | 3 | 6 |

y 0 | 7 | 14 | 13 | 29 | 20 | 50 | 28 | 77 | |||

y 00 | 7 | 21 | 13 | 42 | 20 | 70 | 28 | 105 | |||

y 01 | 7 | 28 | 13 | 55 | 20 | 90 | |||||

y 02 | 7 | 35 | 13 | 68 | |||||||

y 03 | 7 | 42 |

The highlighted outputs can be collected as

If we derive the moments of the same example with the proposed method, the endpoint of the procedure is also 6. However, the results of the digital filter outputs are listed in Tables 8 and 9. In this case, according to Figure 11(a), it is well-known that the number of the digital filter is deduced up to maximum

n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

x T | 0 | 5 | 2 | 3 | 4 | 6 | 1 |

y | 0 | 5 | 7 | 3 | 7 | 6 | 7 |

y T | 0 | 5 | 3 | 6 | 7 | 7 | 7 |

y 00 | 0 | 5 | 8 | 14 | 7 | 14 | 21 |

y 10 | 0 | 5 | 13 | 27 | 7 | 21 | 42 |

y 20 | 0 | 5 | 18 | 45 | 7 | 28 | 70 |

y 30 | 0 | 5 | 23 | 68 | 7 | 35 | 105 |

n | 3 | 6 | n | 3 | 6 | n | 3 | 6 | n | 3 | 6 |

y 00 | 14 | 21 | 27 | 42 | 45 | 70 | 68 | 105 | |||

y 01 | 14 | 35 | 27 | 69 | 45 | 115 | |||||

y 02 | 14 | 49 | 27 | 96 | |||||||

y 03 | 14 | 63 |

Based on (4.13) and (4.14), we can derive the digital filter outputs’ matrix (

#### 4.2.2. Real test image

The images used for the experiments were the Pepper (128×128) and Lena (512×512) images as shown in Figure 12(a) and (b). As shown in Figure 13(a) and (b) the number of additions for digital filter processes are compared in [19] and the proposed method.

## 5. Conclusions

Orthogonal moments are widely used in image analysis and as pattern features in pattern classification. The computation of orthogonal moments can be achieved via geometric moments. Hatamian introduced cascaded digital filters, where each filter operates as an accumulator to generate geometric moments.

One of the weaknesses in using the outputs of the cascaded digital filters to generate the GMs is that the filter outputs increase exponentially as the orders of the moments increase. This work proposes a new formulation to solve this problem by sampling at earlier instances of

Also we showed a reduced method where the number of digital filters used in the generating of geometric moments is reduced by