9512.net

# Refined Method for the Fast and Exact Computation of Moment Invariants

Refined Method for the Fast and Exact Computation of Moment Invariants
Humberto Sossa1 and Jan Flusser2
de Investigación en Computación - IPN Av. Juan de Dios Bátiz s/n, Esquina con Miguel Othón de Mendizábal Colonia Nueva Industrial Vallejo, C. P. 07700, México, D. F. Mexico 2 Institute of Information Theory and Automation Academy of Sciencies of the Czech Republic Pod vodárenkou vezi 4. 182 08 Prage 8, Czech Republic
1 Centro

Abstract. Geometric moments have been proven to be a very efficient tool for description and recognition of binary shapes. Numerous methods for effective calculation of image moments have been presented up to now. Recently, Sossa, Ya?ez and Díaz [Pattern Recognition, 34(2):271-276, 2001] proposed a new algorithm based on a morphologic decomposition of the image into a set of closed disks. Their algorithm yields approximative results. In this paper we propose a refinement of their method that performs as fast as the original one but gives exact results.

1 Introduction
Image moments and various types of moment-based invariants play a very important role in object recognition and shape analysis [3], [1]. The (p+q)th order Cartesian geometric moment Mpq of a two-dimensional grey-level image f ( x, y ) (for short 2D moment) is defined as

M pq = ∫

?∞ ?∞

x p y q f ( x, y )dxdy

p, q = 0,1,2,!

(1)

In a binary image the characteristic function takes only the values 1 or 0, supposing that for the interest region R holds f(x,y)= 1. Thus, the definition simplifies to the form

M pq = ∫∫ x p y q dxdy,
R

(2)

In the discrete case, the double integral must be replaced by a summation. The most common way how to do that is to employ the rectangular (i.e. zero-order) method of numeric integration. Then (1) turns to the well-known form

m pq = ∑∑ x p y q f ij ,
x =1 y =1

N

N

(3)

where N is the size of the image and f ij are the grey levels of individual pixels

(x, y ) ∈ Z 2 . Finally, for binary region R we get

A. Sanfeliu et al. (Eds.): CIARP 2004, LNCS 3287, pp. 487–494, 2004. ? Springer-Verlag Berlin Heidelberg 2004

488

Humberto Sossa and Jan Flusser

m pq =

∑∑ x ( )
x , y ∈R

p

yq.

(4)

Fast and exact computation of 2-D geometric moments of binary objects has been considered as an important problem for its importance in numerous image-processing applications. Since direct calculation of discrete moments from eq. (4) is time-consuming (it requires O(pqN2) operations), a large amount of effort has been spent in the last decade to develop more effective algorithms. Recently, Flusser [2] pointed out that the formula (4), commonly used in the literature for the calculation of the discrete moments of a rectangular block yields inaccurate results. In the same paper, Flusser presented a correction of the method originally proposed by Spiliotis and Mertzios [6]. In this paper we show that the recent method by Sossa et al. [5] also suffers by this inaccuracy and we propose how to correct it. We use the same block-wise image representation as Sossa et al. proposed in [5] but we present a different scheme to calculate the block moments. We show that the new method yields more accurate results than the original one.

2 Original Method by Sossa et al.
In [5], a novel approach to the calculation of geometric moments of binary image was introduced. This method was based on morphologic erosion of the original shape. The method performs in three basic steps: 1. Decompose the given image into a union of disjoint disks; 2. Compute the geometric moments for each of these disks; 3. Obtain the final moments as a sum of the moments computed for each disk. Various metrics defined on a discrete plane can be employed in Step 1. The use of different metrics leads to different image decompositions. Sossa et al. used d8 ''maximum'' metric defined as

d 8 (P1 , P2 ) = max{ x1 ? x2 , y1 ? y 2 }

(5)

where Pi is a point whose coordinates are ( xi , y i ) . It should be noted that a circular disk in d8 metric is a square in Euclidean metric. The basic algorithm used by Sossa et al. to obtain the desired decomposition of a binary region R ? Z 2 iteratively erodes R until the maximal disk completely contained in the original region R is obtained. Then this disk is eliminated from the region R and the remaining shape is assigned to R. The algorithm repeats this procedure until R becomes empty. To calculate the moments of a disk D p of radius r with center moments of this disk in d8 metric are:
r

( X c , Yc )

in

p ∈ Z 2 , Sossa et al. used eq. (4). The explicit formulae for the first ten geometric
m00 = (2r + 1)
2

m10 = m00 X c

m01 = m00Yc

m11 = m10Y

Refined Method for the Fast and Exact Computation of Moment Invariants

489

m20 =

m00 3 X c2 + r (r + 1) 3 m21 = m20Yc m30 = m10 X c2 + r (r + 1)

(

)

(

)

m03 = m01 Yc2 + r (r + 1)

m00 3Yc2 + r (r + 1) 3 m12 = m02 X c m02 =

(

)
(6)

(

)

To obtain these expressions, Sossa et al. used the well-known formulae for sums of integer powers:

∑k =
k =1

n

n (n + 1), 2

∑k2 =
k =1

n

n (n + 1)(2n + 1), 6

?n ? k 3 = ? (n + 1)? . ∑ ?2 ? k =1
n

2

For details on the Sossa et al. method we refer to [5].

3 Refined Method
In this Section, we present a refinement of Sossa et al. method, which uses different formulae for calculation of disk moments. To explain the idea, we recall the original definition of moments in the continuous domain:

where f ( x, y ) is, in this case, the characteristic function of a disk. Clearly, eq. (4) is only an approximation of eq. (7). An error M pq ? m pq is introduced due to the zero-order approximation and numeric integration of x y over each pixel of the disk. Below we show how to calculate the geometric moments of a disk exactly without any approximation. Given a closed disk D p of radius r with center ( X c , Yc ) in p ∈ Z
r
2

M pq = ∫

?∞ ?∞

x p y q f ( x, y )dxdy

(7)

p

q

with corner and

pixels centered in

( X c + r ,Yc + r ) . The characteristic function of this disk is

( X c ? r , Yc ? r ) , ( X c + r ,Yc ? r ) , ( X c ? r , Yc + r )

?1 if (x, y ) ∈ ( X c ? r ? 0.5, X c + r + 0.5) × (Yc ? r ? 0.5, Yc + r + 0.5) f ( x, y ) = ? ?0 otherwise.
According to eq. (7), the exact moments of the disk D p are given as
r

M pq

= =

∫ ∫

[

x p y q f ( x, y )dxdy 1 ( X c + r + 0.5) p+1 ? ( X c ? r ? 0.5) p+1 ? ( p + 1)(q + 1) (Yc + r + 0.5)q+1 ? (Yc ? r ? 0.5)q+1 .
?∞ ? ∞

[

]

]

(8)

490

Humberto Sossa and Jan Flusser

The reader can easily see that the corrected set of expressions for the first ten moments of the closed disk D p becomes:
2 M 10 = M 00 X c M 00 = (2r + 1) M M 20 = 00 3 X c2 + r (r + 1) + 0.25 3 M 21 = M 20Yc r

M 01 = M 00Yc M 02 =

M 11 = M 10Y

(

)

M 30 = M 10 X c2 + r (r + 1) + 0.25

(

)

M 03 = M 01 Yc2 + r (r + 1) + 0.25

M 00 3Yc2 + r (r + 1) + 0.25 3 M 12 = M 02 X c

(

)
(9)

(

)

4 Comparison of the Two Methods
While eq. (8) provides exact results, eq. (4) calculates some moments with errors due to the approximation. It can be shown that there is always M pq ≥ m pq ; the error

M pq ? m pq depends on the values of p and q. Comparing eqs. (9) and (6), we can
evaluate this errors easily, for instance

M 20 ? m20

1 6 X c2 r + 3 X c2 + 2r 3 + 3r 2 + 1.5r + 0.25 (2r + 1) ? 3 1 6 X c2 r + 3 X c2 + 2r 3 + 3r 2 + r (2r + 1) 3 1 (2r + 1)(0.5r + 0.25) = 3 1 = m00 . 12 =

( (

)

)

Similarly,

M 02 ? m02 =

m00 m m , M 30 ? m30 = 10 , M 21 ? m21 = 01 , 12 4 12 m m M 12 ? m12 = 10 , M 03 ? m03 = 01 . 12 4

(10)

On the other hand, for some moments both methods produce exact results:

M 00 ? m00 = 0, M 01 ? m01 = 0, M 10 ? m10 = 0, M 11 ? m11 = 0.
5 Impact on the Values of the Invariants

(11)

In object recognition we rarely use directly the geometric moments as the features because they are sensitive to particular position of the object in the image plane. Instead, we employ certain functions of moments, called moment invariants, that are

Refined Method for the Fast and Exact Computation of Moment Invariants

491

invariant to expected intraclass variations of the objects. Typically, shift and rotation invariance is required in many practical tasks. In this Section, we analyze how the values of various moment invariants differ depending on if m pq or M pq are used. Probably the most popular set of moment invariants was derived by Hu [3]. These features are invariant to translation and rotation of the object. In continuous domain the first two are defined as (12) φ1 = ? 20 + ? 02 , φ 2 = (? 20 ? ? 02 )2 ? 4?11 where

? pq = ∫

?∞ ?∞

∫ (x ? x ) ( y ? y ) f (x, y )dxdy
p q t t

(13)

is the central moment of the object f ( x, y ) and ( xt , y t ) are the coordinates of the object centroid. Hu also showed that scaling invariance can be achieved via normali. zation of each central moment by ? 00 It can be easily observed that both algorithms give the same position of object centroid:
( p+q+2 ) / 2

xt ≡

m10 M 10 m M 01 ≡ and yt ≡ 01 ≡ , m00 M 00 m00 M 00

Thus, central moments are affected exactly in the same way as geometric moments. However, since ?10 and ? 01 equal zero by definition, the relations (10) simplify to the form

m00 m , Μ 02 ? ? 02 = 00 , 12 12 Μ 30 ? ? 30 = 0 , Μ 21 ? ? 21 = 0 , Μ 12 ? ?12 = 0 , Μ 03 ? ? 03 = 0 Μ 20 ? ? 20 =
where

? pq

denotes the central moments calculated by traditional method while

Μ pq stands for the central moments calculated by the refined method.
Now we can observe an interesting fact: The only Hu's invariant whose values depend on the method of calculation is the first one. Clearly,

φ1 (Μ pq ) ? φ1 (? pq ) =

? 00
6

.

φ3 , φ4 , φ5 and φ7 contains only 3rd-order moments, so they cannot be affected. φ2 and φ6 stay also constant due to the error cancellation effect. The same observation
can be found in [4]. Another set of invariants called affine moment invariants (AMI's) was proposed by Flusser and Suk [1]. They are more general than Hu's invariants because they are invariant not only to rotation and scaling but to general affne transformation. Thanks to this, they can be successfully used in object recognition on images deformed by slant or anisotropic scaling. The first six AMI's are shown below.

492

Humberto Sossa and Jan Flusser
4 I 1 = (? 20 ? 02 ? ?11 ) / ? 00

2 2 7 I 3 = ? 20 ? 21 ? 03 ? ?12 ? ?11 (? 30 ? 03 ? ? 21 ?12 ) + ? 02 ? 30 ?12 ? ? 21 / ? 00

2 2 2 2 2 2 10 I 2 = ? 30 ? 03 ? 6? 30 ? 21?12 ? 03 + 4? 30 ?12 + 4? 21 ? 03 ? 3? 21 ?12 / ? 00

( (

(

)

(

)

))

I 4 = (? ? -6 ?30 ?11 ?12 ?03 -6 ? ?02 ?21 ?03 + 9? ?02 ?
3 20 2 03 2 20 2 20

2 12

2 + 12?20 ?11 ?21 ?03 + 6?20 ?11 ?02 ?30 ?03 -18?20 ?11 ?02 ?21 ?12 3 2 2 2 2 -8?11 ?30 ?03 -6?20 ?02 ?30 ?12 + 9?20 ?02 ?21 + 12?11 ?02 ?30 ?12

2 2 2 9 ? 04 ? 22 + 2? 31? 22 ?13 ? ? 40 ?13 ? ? 04 ? 31 ? 3? 22 )/ ?00 We can easily prove that, for the same reason as in the previous case, I 2

2 6 I 5 = ? 40 ? 04 ? 4? 31?13 + 3? 22 / ? 00

I6

( = (?

2 3 2 -6 ?11 ?02 ?30 ?21 + ?02 ?30 )/?11 00

)

40

stays the

same irrespective of the calculation algorithm. However, other AMI's change if Μ pq are used instead of

? pq . We can observe that, for instance,
I 1 (Μ pq ) ? I1 (? pq ) =

? 00
12

(? 20 ? ? 02 ) + ? 00 .
2

144

Similar (but more complicated) relations can be derived for other AMI's too. Summarizing the above analysis, we can conclude that when using Hu's invariants, one does not need to use the refined algorithm for moment calculation (with exception of φ1 ). On the other hand, the AMI's should be computed using the refined method if accurate values are required.

6 Numerical Experiments
In this Section, we experimentally demonstrate the difference between classical and new formula for moment calculation. From the theoretical analysis given above implies that some moments and moment invariants are identical regardless of the fact whether eq. (4) or eq. (8) is used. In this experiment we show the differences between second-order central moments, first Hu's invariant φ1 and six affne moment invariants I 1 ,…, I 6 for three binary images. In Fig. 1, one can see our test objects called ''Plane'', ''Duck'', and ''Snake'', respectively. In Table 1, the relative errors of the moments and of the invariants are shown. The errors we have investigated are defined as follows: Μ ? ? 02 Μ ? ? 20 φ (Μ ) ? φ1 (? 02 ) , e3 = 1 02 e1 = 20 , e2 = 02 , Μ 02 Μ 20 φ1 (Μ 02 ) I j (Μ 02 ) ? I j (? 02 ) e j +3 = , j = 1,…,6. I j (Μ 02 )

Refined Method for the Fast and Exact Computation of Moment Invariants

493

Fig. 1. Test objects used in the experiment: Plane(left), Duck(middle), and Snake(right). Table 1. Relative differences between traditional and new formulae for moment calculation. For simplicity, all values were multiplied by 104.
Plane Duck Snake e1 0.16 0.19 0.18 e2 0.23 0.41 54.89 e3 0.19 0.26 0.37 e4 0.40 0.81 56.73 e5 0 0 0 e6 0.21 0.41 -6.52 e7 0.63 1.24 2.02 e8 0.91 2.08 2.21 e9 1.63 3.27 145.07

The most important observation that is based on this experiment can be summarized in the following way. For elongated objects (where elongation is parallel to one of the axes) the relative errors can be high and might, in some cases, cause misclassification. An extreme case is a one-pixel thick horizontal line, for which ? 02 = 0 but

Μ 02 is proportional to its length. Relative errors of other objects are much smaller,
as can be seen in Table 1 when comparing Plane or Duck to Snake. Thus, when dealing with elongated objects, it is recommended to use the refined formula (8) for moment calculation. On the other hand, for objects having ''regular'' shapes traditional computation according to eq. (4) can be used without significant loss of accuracy.

7 Conclusion
In this paper, we presented a new method for calculating geometric moments and, consequently, of moment invariants of binary objects. This method is a refinement of Sossa et al. algorithm that was based on a decomposition of the object into disjoint disks. In the original paper by Sossa et al., zero-order approximation was used for numerical integration when calculating moments of the disks. In this paper we proposed an exact formula with no approximation. We analyzed (both theoretically and experimentally) the differences between these two formulae and the influence of the refined method on the values of moment invariants. We demonstrated that for some shapes the new method yields a significant increase in accuracy.

Acknowledgment
Financial support of this research was provided by the National Council of Science and Technology of Mexico (CONACYT) under projects No. 41529 and 40114Y, by the National Polytechnic Institute of Mexico (IPN) under project No. 20030658 and by the Grant Agency of the Czech Republic under the project No. 102/00/1711.

494

Humberto Sossa and Jan Flusser

References
1. J. Flusser and T. Suk, Pattern recognition by affne moment invariants, Pattern Recognition, 26(1):167-174, 1993. 2. J. Flusser, Refined moment calculation using image block representation, IEEE Transactions on Image Processing, 9(11):1977-1978, 2000. 3. M. K. Hu, Visual pattern recognition by moment invariants, IRE Transactions on Information Theory, 8:179-187, 1962. 4. W. G. Lin and S. S. Wang, A note on the calculation of moments, Pattern Recognition Letters, 15(11):1065-1070, 1994. 5. H. Sossa, C. Ya?ez and J. L. Díaz, Computing geometric moments using morphological erosions, Pattern Recognition, 34(2):271-276, 2001. 6. I. M. Spiliotis and B. G. Mertzios, Real-time computation of 2-D moments on binary images using image block representation, IEEE Transactions of Image Processing, 7(11):1609-1615, 1998.