# New Algorithm for Constructing and Computing Scale Invariants of 3D Tchebichef Moments

Authors: Haiyong Wu; Jean Louis Coatrieux; Huazhong Shu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Scale invariants of Tchebichef moments are usually achieved by a linear combination of corresponding invariants of geometric moments or via an iterative algorithm to eliminate the scale factor. According to the properties of Tchebichef polynomials, we propose a new approach to construct scale invariants of Tchebichef moments. An algorithm based on matrix multiplication is also provided to efficiently compute the 3D moments and invariants. Several experiments are carried out to validate the effectiveness of our descriptors and algorithm.


---

## Body

## 1. Introduction

Since the introduction of geometric moment invariants by Hu [1], moments and moment’s functions have been extensively applied in pattern recognition [2, 3]. Due to the nonorthogonal kernel function of geometric moments, they suffer from high degree of information redundancy and are sensitive to noise, especially when higher order moments are concerned. Teague [4] introduced orthogonal continuous Legendre and Zernike moments, which can represent the image with minimal information redundancy and can be easily used for image reconstruction. The main drawback of the aforementioned moments is the discretization error, which accumulates with the increasing of moment order [5]. To resolve this problem, discrete orthogonal polynomials have been utilized to construct moments, such as Tchebichef [6], Krawtchouk [7], and Hahn [8]. Their basis functions exactly satisfy the orthogonality, which means they do not require any numerical approximation and spatial domain transformation. It makes them superior to the conventional continuous moments in terms of image representation capability.Recently, the problem of moment invariance has been extensively investigated. For example, the invariants of Legendre moments have been achieved through image normalization method and indirect method. Chong et al. [9] proposed a direct method to construct the translation and scale Legendre moment invariants. Ong et al. [10] generalized this method to 3D directly. Following this way, Zhu et al. [11] derived translation and scale invariants of Tchebichef moments. However, Khalid pointed out that one weakness of this method is the high computational cost, especially when image size is large and higher order moments are concerned. Therefore, this method is suitable only for a set of binary images with small size [12]. Another difficulty of aforementioned scale invariants is how to determinate their parameters, which need to be selected carefully to keep a compromise between numerical stability and complexity.Inspired by the method proposed by Zhang et al. [13], we propose in this paper an improved approach to construct 3D scale invariants of Tchebichef moments. Instead of normalizing by lower order moments, scale factors are eliminated by utilizing the orthogonality of coefficients. This method avoids enormous computing caused by iteration. Moreover, we propose an algorithm based on matrix multiplication to efficiently compute the 3D moments and invariants.The remaining of this paper is organized as follows: in Section2, Tchebichef polynomials and derivation of corresponding scale invariants are described in detail. Section 3 discusses an efficient way for computing 3D moments and invariants. Experimental results for evaluating the performance of the proposed descriptors are given in Section 4. Finally, conclusions are provided in Section 5.


## 2. Improved Scale Invariants of 3D Tchebichef Moments

In this section, the falling factorial is introduced to build a mutual relationship between Tchebichef polynomials and power series. In order to separate the scale factor, Tchebichef polynomials need to be transformed into power series firstly. Then, these separated power series are expressed through Tchebichef polynomials. By this way, moments of scaled image can be expressed as a linear combination of the original moments. We use the Stirling numbers instead of tedious iterations to obtain scale invariants, because the recursive procedure is an inherent deficiency of descriptors reported in [9–11].


### 2.1. Some Properties of Tchebichef Polynomials

The squared-norm of scaled Tchebichef polynomials is defined as [6]
(1)tn(x)=(1-N)nρ(n,N)∑k=0n(-n)k(-x)k(1+n)k(k!)2(1-N)k,n,x=0,1,2,…,N-1,
where (a)k is the Pochhammer symbol given by
(2)(a)k=a(a+1)(a+2)⋯(a+k-1),k≥1,(a)0=1,
and ρ(n,N) is the squared-norm defined by
(3)ρ(n,N)=(N+n)!(2n+1)(N-n-1)!.
The falling factorial 〈a〉k is defined as [14]
(4)〈a〉k=(-1)k(-a)k=a(a-1)(a-2)⋯(a-k+1),k≥1,〈a〉0=1.Using (4), (1) can be rewritten as
(5)tn(x)=∑k=0ncnk〈x〉k,
where
(6)cnk=1ρ(n,N)(n+k)!(1-N)n(k!)2(n-k)!(1-N)k.
Let UM(x)=(t0(x),t1(x),…,tM(x))T   and VM(x)=(1,〈x〉1,…,〈x〉M)T be two column vectors, where the superscript  T indicates the transposition. Using (5), we have
(7)UM(x)=CMVM(x),
where CM=(cnk),0≤k≤n≤M, is a lower triangular matrix whose size is (M+1)×(M+1). The matrix CM is invertible because its diagonal elements are not zero; therefore,
(8)VM(x)=CM-1UM(x)=DMUM(x),
where DM=(dnk),0≤k≤n≤M. DM is a lower triangular matrix too, and its elements are given by [15]
(9)dnk=(-1)n+kρ(k,N)(2k+1)(n!)2(1-N)n(n+k+1)!(n-k)!(1-N)k.The falling factorial〈a〉n and the power series xn can be expanded mutually:
(10)〈x〉n=∑i=0ns1(n,i)xi,xn=∑i=0ns2(n,i)〈x〉i,
where s1(n,i) is the Stirling number of the first kind, satisfying the following recurrence relations:
(11)s1(0,0)=1,s1(0,i)=s1(n,0)=0,n≥1,i≥1,s1(n,i)=s1(n-1,i-1)-(n-1)s1(n-1,i),
and s2(n,i) is the Stirling number of the second kind, satisfying
(12)s2(0,0)=1,s2(0,i)=s2(n,0)=0,n≥1,i≥1,s2(n,i)=s2(n-1,i-1)+is2(n-1,i).The relationship between Tchebichef polynomials and power series has been established via the falling factorial, which is the fundamental of our descriptors.


### 2.2. Scale Invariants of 1D Tchebichef Moments

The 1D Tchebichef moment of orderp for an N-length signal f(x) is defined as
(13)Tpf=∑x=0N-1tp(x)f(x).
Let g(x) be a scaled version of f(x) with a scale factor 1/λ; that is, g(x)=f(x/λ); then the Tchebichef moment of order p of g(x) has the form of
(14)Tpg=∑x=0N-1tp(x)g(x)=λ∑x=0N-1tp(λx)f(x).
From (5), (8), and (10), we can see that
(15)tn(λx)=∑k=0n∑i=0k∑j=0i∑m=0jcnks1(k,i)λis2(i,j)djmtm(x).
Substituting (15) into (14), we have
(16)Tpg=∑k=0p∑i=0k∑j=0i∑m=0jcpks1(k,i)λi+1s2(i,j)djmTmf.Equation (16) shows that the Tchebichef moment of the scaled signal can be expressed as a linear combination of the original ones. Based on this relationship, we derive the following theorem.Theorem 1.
For a given integerp, let
(17)Ipf=∑k=0p∑i=0k∑j=0i∑m=0jcpks1(k,i)Γf-(i+1)s2(i,j)djmTmf,
with Γf=T0f. Then Ipf is invariant to image scaling.The proof is given in the appendix.


### 2.3. Scale Invariants of 3D Tchebichef Moments

The(p+q+r)th Tchebichef moment of a 3D image f(x,y,z) is defined by
(18)Tpqrf=∑x=0N-1∑y=0N-1∑z=0N-1tp(x)tq(y)tr(z)f(x,y,z).Let us assume that the original imagef is scaled with factors 1/λ, 1/μ, and 1/ξ, along x-direction, y-direction, and z-direction, respectively. That is, g(x,y,z)=f(x/λ,y/μ,z/ξ). The (p+q+r)th moments of scaled image g are given by
(19)Tpqrg=λμζ∑x=0N-1∑y=0N-1∑z=0N-1tp(λx)tq(μy)tr(ζz)f(x,y,z).
Similarly to 1D case, we can rewrite (19) as
(20)Tpqrg=∑k=0p∑i=0k∑j=0i∑m=0jcpks1(k,i)λi+1s2(i,j)djm×∑n=0q∑s=0n∑w=0b∑v=0wcqns1(n,b)μb+1s2(b,w)dwv×∑e=0r∑h=0e∑a=0h∑l=0acres1(e,h)ζh+1s2(h,a)dalTmvlf.
To construct the 3D moment invariants, we need the following lemma.Lemma 2.
Let(21)Γf=T100fT000f-c10d00,Θf=T010fT000f-c10d00,Λf=T001fT000f-c10d00.
Then, one has Γg=λΓf, Θg=μΘf, and Λg=ζΛf.Proof.
Using (6), (9), and (19), we have
(22)Γg=T100gT000g=c10d00T000f+λc11d10T000f+λT100fT000f=c10d00+λ(T100fT000f+c11d10).
Taking c10d00+c11d10=0 into account, we have Γg=λΓf. The other two relationships can be demonstrated in a similar way.Using (20) and Lemma 2, we can construct the scale invariants of 3D Tchebichef moments, which are described in following theorem.Theorem 3.
For given integersp, q, r, let
(23)Ipqrf=∑k=0p∑i=0k∑j=0i∑m=0jcpks1(k,i)Γf-(i+1)s2(i,j)djm×∑n=0q∑b=0n∑u=0b∑v=0ucqns1(n,b)Θf-(b+1)s2(b,u)duv×∑e=0r∑h=0e∑a=0h∑l=0acres1(e,h)Λf-(h+1)s2(h,a)dalTmvlf,
where Γf, Θf, and Λf are defined in Lemma 2. Then, Ipqrf is invariant to image scale.The proof is similar to that of Theorem1 since the kernel function is separable, and so it is omitted here.


## 2.1. Some Properties of Tchebichef Polynomials

The squared-norm of scaled Tchebichef polynomials is defined as [6]
(1)tn(x)=(1-N)nρ(n,N)∑k=0n(-n)k(-x)k(1+n)k(k!)2(1-N)k,n,x=0,1,2,…,N-1,
where (a)k is the Pochhammer symbol given by
(2)(a)k=a(a+1)(a+2)⋯(a+k-1),k≥1,(a)0=1,
and ρ(n,N) is the squared-norm defined by
(3)ρ(n,N)=(N+n)!(2n+1)(N-n-1)!.
The falling factorial 〈a〉k is defined as [14]
(4)〈a〉k=(-1)k(-a)k=a(a-1)(a-2)⋯(a-k+1),k≥1,〈a〉0=1.Using (4), (1) can be rewritten as
(5)tn(x)=∑k=0ncnk〈x〉k,
where
(6)cnk=1ρ(n,N)(n+k)!(1-N)n(k!)2(n-k)!(1-N)k.
Let UM(x)=(t0(x),t1(x),…,tM(x))T   and VM(x)=(1,〈x〉1,…,〈x〉M)T be two column vectors, where the superscript  T indicates the transposition. Using (5), we have
(7)UM(x)=CMVM(x),
where CM=(cnk),0≤k≤n≤M, is a lower triangular matrix whose size is (M+1)×(M+1). The matrix CM is invertible because its diagonal elements are not zero; therefore,
(8)VM(x)=CM-1UM(x)=DMUM(x),
where DM=(dnk),0≤k≤n≤M. DM is a lower triangular matrix too, and its elements are given by [15]
(9)dnk=(-1)n+kρ(k,N)(2k+1)(n!)2(1-N)n(n+k+1)!(n-k)!(1-N)k.The falling factorial〈a〉n and the power series xn can be expanded mutually:
(10)〈x〉n=∑i=0ns1(n,i)xi,xn=∑i=0ns2(n,i)〈x〉i,
where s1(n,i) is the Stirling number of the first kind, satisfying the following recurrence relations:
(11)s1(0,0)=1,s1(0,i)=s1(n,0)=0,n≥1,i≥1,s1(n,i)=s1(n-1,i-1)-(n-1)s1(n-1,i),
and s2(n,i) is the Stirling number of the second kind, satisfying
(12)s2(0,0)=1,s2(0,i)=s2(n,0)=0,n≥1,i≥1,s2(n,i)=s2(n-1,i-1)+is2(n-1,i).The relationship between Tchebichef polynomials and power series has been established via the falling factorial, which is the fundamental of our descriptors.


## 2.2. Scale Invariants of 1D Tchebichef Moments

The 1D Tchebichef moment of orderp for an N-length signal f(x) is defined as
(13)Tpf=∑x=0N-1tp(x)f(x).
Let g(x) be a scaled version of f(x) with a scale factor 1/λ; that is, g(x)=f(x/λ); then the Tchebichef moment of order p of g(x) has the form of
(14)Tpg=∑x=0N-1tp(x)g(x)=λ∑x=0N-1tp(λx)f(x).
From (5), (8), and (10), we can see that
(15)tn(λx)=∑k=0n∑i=0k∑j=0i∑m=0jcnks1(k,i)λis2(i,j)djmtm(x).
Substituting (15) into (14), we have
(16)Tpg=∑k=0p∑i=0k∑j=0i∑m=0jcpks1(k,i)λi+1s2(i,j)djmTmf.Equation (16) shows that the Tchebichef moment of the scaled signal can be expressed as a linear combination of the original ones. Based on this relationship, we derive the following theorem.Theorem 1.
For a given integerp, let
(17)Ipf=∑k=0p∑i=0k∑j=0i∑m=0jcpks1(k,i)Γf-(i+1)s2(i,j)djmTmf,
with Γf=T0f. Then Ipf is invariant to image scaling.The proof is given in the appendix.


## 2.3. Scale Invariants of 3D Tchebichef Moments

The(p+q+r)th Tchebichef moment of a 3D image f(x,y,z) is defined by
(18)Tpqrf=∑x=0N-1∑y=0N-1∑z=0N-1tp(x)tq(y)tr(z)f(x,y,z).Let us assume that the original imagef is scaled with factors 1/λ, 1/μ, and 1/ξ, along x-direction, y-direction, and z-direction, respectively. That is, g(x,y,z)=f(x/λ,y/μ,z/ξ). The (p+q+r)th moments of scaled image g are given by
(19)Tpqrg=λμζ∑x=0N-1∑y=0N-1∑z=0N-1tp(λx)tq(μy)tr(ζz)f(x,y,z).
Similarly to 1D case, we can rewrite (19) as
(20)Tpqrg=∑k=0p∑i=0k∑j=0i∑m=0jcpks1(k,i)λi+1s2(i,j)djm×∑n=0q∑s=0n∑w=0b∑v=0wcqns1(n,b)μb+1s2(b,w)dwv×∑e=0r∑h=0e∑a=0h∑l=0acres1(e,h)ζh+1s2(h,a)dalTmvlf.
To construct the 3D moment invariants, we need the following lemma.Lemma 2.
Let(21)Γf=T100fT000f-c10d00,Θf=T010fT000f-c10d00,Λf=T001fT000f-c10d00.
Then, one has Γg=λΓf, Θg=μΘf, and Λg=ζΛf.Proof.
Using (6), (9), and (19), we have
(22)Γg=T100gT000g=c10d00T000f+λc11d10T000f+λT100fT000f=c10d00+λ(T100fT000f+c11d10).
Taking c10d00+c11d10=0 into account, we have Γg=λΓf. The other two relationships can be demonstrated in a similar way.Using (20) and Lemma 2, we can construct the scale invariants of 3D Tchebichef moments, which are described in following theorem.Theorem 3.
For given integersp, q, r, let
(23)Ipqrf=∑k=0p∑i=0k∑j=0i∑m=0jcpks1(k,i)Γf-(i+1)s2(i,j)djm×∑n=0q∑b=0n∑u=0b∑v=0ucqns1(n,b)Θf-(b+1)s2(b,u)duv×∑e=0r∑h=0e∑a=0h∑l=0acres1(e,h)Λf-(h+1)s2(h,a)dalTmvlf,
where Γf, Θf, and Λf are defined in Lemma 2. Then, Ipqrf is invariant to image scale.The proof is similar to that of Theorem1 since the kernel function is separable, and so it is omitted here.


## 3. Computing 3D Moments and Invariants

To achieve the scale invariance of 3D moments, (23) implies that it needs to compute a 12-level nested loop. Since the structure of (23) is symmetric, we introduce a new algorithm based on matrix multiplication to reduce the number of loops.


### 3.1. Computing 3D Moments

Let us begin with discussion of the 1D case. LetM=(M0,M1,…,Mp)T be a column vector constituted by the (0~p)th moments of f(x). From (5), it is well known that
(24)M=[M0M1⋯Mp]=[t0(1)t0(2)⋯t0(N-1)t1(1)t1(2)⋯t1(N-1)⋯tp(1)tp(2)⋯tp(N-1)][f(0)f(1)⋯f(N-1)].Yap et al.  [7] proposed a matrix form of moments for a 2D image
(25)M=K1AK2T,
where M is an m×n matrix of Tchebichef moments, K1={ti(x)}i=0,x=0i=m-1,x=N-1, K2={tj(y)}j=0,y=0j=n-1,y=N-1, and A={f(x,y)}i,j=0i,j=N-1.Exchanging the order of summation, we rewrite (18) as
(26)Tpqrf=∑z=0N-1tr(z){∑x=0N-1∑y=0N-1tp(x)tq(y)f(x,y,z)}.
By combining (24) with (25), an effective algorithm to calculate (26) can be derived as follows.Step 1.
ComputingN 2D images along z-direction by (25), we can get temporary matrices  (see Figure 8), where Mij′(k) denotes the element of ith row and jth column in the kth plane of z-direction.Step 2.
Alongz-direction, we rearrange the temporary matrices obtained in Step 1 and get a (p+1) matrix with size of N×(q+1). Then the required 3D moments are achieved after they are premultiplied by the kernel function matrices; that is,
(27)[M000⋯M0q0M001⋯M0q1⋯M00r⋯M0qr]=[t0(0)t0(1)⋯t0(N-1)t1(0)t1(1)⋯t1(N-1)⋯tr(0)tr(1)⋯tr(N-1)]×[M00′(0)⋯M0q′(0)M00′(1)⋯M0q′(1)⋯M00′(N-1)⋯M0q′(N-1)],[M100⋯M1q0M101⋯M1q1⋯M10r⋯M1qr]=[t0(0)t0(1)⋯t0(N-1)t1(0)t1(1)⋯t1(N-1)⋯tr(0)tr(1)⋯tr(N-1)]×[M10′(0)⋯M1q′(0)M10′(1)⋯M1q′(1)⋯M10′(N-1)⋯M1q′(N-1)],⋮,[Mp00⋯Mpq0Mp01⋯Mpq1⋯Mp0r⋯Mpqr]=[t0(0)t0(1)⋯t0(N-1)t1(0)t1(1)⋯t1(N-1)⋯tr(0)tr(1)⋯tr(N-1)]×[Mp0′(0)⋯Mpq′(0)Mp0′(1)⋯Mpq′(1)⋯Mp0′(N-1)⋯Mpq′(N-1)].
The matrix representation is usually considered very effective in software packages such as MATLAB. But in Section4, our experiment shows that it performs well in C++ too.


### 3.2. Computing 3D Invariants

Equation (23) has a similar structure  to the definition of 3D moments. Exchanging the order of  summation, we can rewrite (23) as
(28)Ipqrf=∑m=0p∑v=0q∑l=0rθ1(p,m)θ2(q,v)θ3(r,l)Tmvlf,
where (29a)θ1(p,m)=∑k=mp∑i=mk∑j=micpks1(k,i)Γf-(i+1)s2(i,j)djm,(29b)θ2(q,v)=∑n=vq∑b=vn∑u=vbcqns1(n,b)Θf-(b+1)s2(b,u)duv,(29c)θ3(r,l)=∑e=lr∑h=le∑a=lhcres1(e,h)Λf-(h+1)s2(h,a)dal.Therefore, the algorithm presented in the previous subsection can be applied to compute the invariants. Let us denote matrices{cij}i,j=0i,j=p, {s1(i,j)}i,j=0i,j=p, diag(τf1,τf2,…,τfp+1), {s2(i,j)}i,j=0i,j=p, and {dij}i,j=0i,j=p by C, S1, Δ, S2, and D, respectively. They are all lower triangular matrices, and (29a) can be evaluated by a matrix way; that is, Ξ=C*S1*Δ*S2*D, where Ξ denotes the matrix {θ1(i,j)}i,j=0i,j=p. The same procedure will be repeated in computing (29b) and (29c).


## 3.1. Computing 3D Moments

Let us begin with discussion of the 1D case. LetM=(M0,M1,…,Mp)T be a column vector constituted by the (0~p)th moments of f(x). From (5), it is well known that
(24)M=[M0M1⋯Mp]=[t0(1)t0(2)⋯t0(N-1)t1(1)t1(2)⋯t1(N-1)⋯tp(1)tp(2)⋯tp(N-1)][f(0)f(1)⋯f(N-1)].Yap et al.  [7] proposed a matrix form of moments for a 2D image
(25)M=K1AK2T,
where M is an m×n matrix of Tchebichef moments, K1={ti(x)}i=0,x=0i=m-1,x=N-1, K2={tj(y)}j=0,y=0j=n-1,y=N-1, and A={f(x,y)}i,j=0i,j=N-1.Exchanging the order of summation, we rewrite (18) as
(26)Tpqrf=∑z=0N-1tr(z){∑x=0N-1∑y=0N-1tp(x)tq(y)f(x,y,z)}.
By combining (24) with (25), an effective algorithm to calculate (26) can be derived as follows.Step 1.
ComputingN 2D images along z-direction by (25), we can get temporary matrices  (see Figure 8), where Mij′(k) denotes the element of ith row and jth column in the kth plane of z-direction.Step 2.
Alongz-direction, we rearrange the temporary matrices obtained in Step 1 and get a (p+1) matrix with size of N×(q+1). Then the required 3D moments are achieved after they are premultiplied by the kernel function matrices; that is,
(27)[M000⋯M0q0M001⋯M0q1⋯M00r⋯M0qr]=[t0(0)t0(1)⋯t0(N-1)t1(0)t1(1)⋯t1(N-1)⋯tr(0)tr(1)⋯tr(N-1)]×[M00′(0)⋯M0q′(0)M00′(1)⋯M0q′(1)⋯M00′(N-1)⋯M0q′(N-1)],[M100⋯M1q0M101⋯M1q1⋯M10r⋯M1qr]=[t0(0)t0(1)⋯t0(N-1)t1(0)t1(1)⋯t1(N-1)⋯tr(0)tr(1)⋯tr(N-1)]×[M10′(0)⋯M1q′(0)M10′(1)⋯M1q′(1)⋯M10′(N-1)⋯M1q′(N-1)],⋮,[Mp00⋯Mpq0Mp01⋯Mpq1⋯Mp0r⋯Mpqr]=[t0(0)t0(1)⋯t0(N-1)t1(0)t1(1)⋯t1(N-1)⋯tr(0)tr(1)⋯tr(N-1)]×[Mp0′(0)⋯Mpq′(0)Mp0′(1)⋯Mpq′(1)⋯Mp0′(N-1)⋯Mpq′(N-1)].
The matrix representation is usually considered very effective in software packages such as MATLAB. But in Section4, our experiment shows that it performs well in C++ too.


## 3.2. Computing 3D Invariants

Equation (23) has a similar structure  to the definition of 3D moments. Exchanging the order of  summation, we can rewrite (23) as
(28)Ipqrf=∑m=0p∑v=0q∑l=0rθ1(p,m)θ2(q,v)θ3(r,l)Tmvlf,
where (29a)θ1(p,m)=∑k=mp∑i=mk∑j=micpks1(k,i)Γf-(i+1)s2(i,j)djm,(29b)θ2(q,v)=∑n=vq∑b=vn∑u=vbcqns1(n,b)Θf-(b+1)s2(b,u)duv,(29c)θ3(r,l)=∑e=lr∑h=le∑a=lhcres1(e,h)Λf-(h+1)s2(h,a)dal.Therefore, the algorithm presented in the previous subsection can be applied to compute the invariants. Let us denote matrices{cij}i,j=0i,j=p, {s1(i,j)}i,j=0i,j=p, diag(τf1,τf2,…,τfp+1), {s2(i,j)}i,j=0i,j=p, and {dij}i,j=0i,j=p by C, S1, Δ, S2, and D, respectively. They are all lower triangular matrices, and (29a) can be evaluated by a matrix way; that is, Ξ=C*S1*Δ*S2*D, where Ξ denotes the matrix {θ1(i,j)}i,j=0i,j=p. The same procedure will be repeated in computing (29b) and (29c).


## 4. Experimental Results

In this section, we first evaluate the efficiency of our computing algorithm, which is compared with geometric moment invariants [16], Legendre invariants [10], and Zhu’s invariants [11]. Then we illustrate the performance of the proposed descriptors based on a 3D MRI image. Classification abilities of four invariants are tested on character sets finally.A 3D silhouette image shown in Figure1 is composed of 128 binary images with size of 128×128. It is used to evaluate the computational speed of the algorithm described in Section 3. Figure 2 shows the computational time required to calculate the invariants of order up to 18. It should be noted that the program is implemented in C++ on a PC with Intel Core 2 Duo P8400 2.4 GHz CPU, 4 GB RAM. Figure 2 implies that our descriptors require less computation time when the order of invariants increases, because we apply the proposed algorithm for computing the Tchebichef moments as well as the invariants. The geometric moments and corresponding invariants are calculated directly through nested loops. For Zhu’s invariants and Legendre invariants, we utilize our method to obtain their 3D moments firstly, and then nested loops are used to compute moment invariants. Since there are no nested loops in our algorithm, the required time increases little with the order growing.Figure 1
A 3D silhouette.Figure 2
Comparison of mean time elapsed (s).The Volume Library [16] contains regular volume data mainly coming from CT or MRI scanners. Figure 3 shows a 3D MRI head image selected from this library. We resize this head image with the factors of 0.5, 1, 1.5, and 2 along x-axis, y-axis, and z-axis, respectively, which form a test set consisting of 64 images with different sizes. In order to measure “invariant” performance of the descriptors, we also adopt the deviation σ/μ,which was proposed by Chong et al. [9]. Here σ and μ  denote the standard deviation and mean of invariants with the same order, respectively. Figure 4 illustrates the standard deviation of the geometric invariants, Legendre invariants, Zhu’s invariants, and the proposed descriptors with the same order. It shows that the geometric invariants have the worst performance. Since high order of geometric moments has large variation in the dynamic range of values [6], this leads to unstable relative errors. Our descriptors have a slightly lower relative error than Zhu’s invariants and Legendre invariants.Figure 3
A 3D MRI head image.Figure 4
Standard deviation of lower order invariants for a nonuniformly scaled 3D MRI image.Moments of higher orders are generally considered more sensitive to image noise. To test the robustness of our invariants for degraded images, we add Gaussian noise (with meanμ=0 and variance σ varying from 0.01 to 0.3) and salt-and-pepper noise (with different noise densities from 0.01 to 0.3) to Figure 1, respectively. We rearrange the scale invariants of an image following the scheme through the path (0,0,0) → (1,0,0) → (0,1,0) → (0,0,1) → (2,0,0) → (1,1,0) → (1,0,1) → (0,2,0) → (0,1,1) → (0,0,2) → ⋯→ (0,0,m) and so on, to construct an invariant vector If(m), where m is the maximum order of moment invariants. In this experiment, m=4 is chosen; that is, the length of If(m) equals 35.The relative error of the invariant vector corresponding to the original imagef and the degraded image f~ is defined as
(30)e(f,f~)=∥If-If~∥∥If∥,
where ∥·∥ is the Euclidean norm.Relative errors caused by Gaussian and salt-and-pepper noise are depicted in Figures5 and 6, respectively. We can observe that the relative error increases when increasing the noise level, and the proposed descriptors are more robust to noise than the other three competitors.Figure 5
Relative errors of four descriptors with respect to additive Gaussian noise.Figure 6
Relative error of four descriptors with respect to additive salt-and-pepper noise.In the last experiment, we test the classification ability of our descriptors in both noise-free and noisy conditions. A classifier is required to identify the class of an unknown input object. We utilize the second and third order of invariants to form a feature vector. Therefore, the length of the vector equals 16. During the classification, the feature of an unknown object is compared with the training feature of a particular class. The Euclidean distance is frequently utilized as the classification measure, which is defined by(31)d(Vs,Vt(k))=∥Is-It∥,
where Vs and Vt(k) are feature vectors of the unknown sample and the k class, respectively. We define the classification rule such that an unknown input object will belong to the nearest class. The average classification accuracy is defined as
(32)η=NumberofcorrectlyclassifiedimagesThetotalnumberofimages×100%.An original set of alphanumeric characters with size of64×64×64 shown in Figure 7 is used in this experiment. The reason for such a choice is that the elements in subsets {6,b,d}, {9,p,q}, and {a,c,o,0,e} may be confused due to the similarity. Every element is scaled with the factors {0.5, 1, 1.5, and 2} along x-, y-, and z-axes, respectively, forming a testing set including 11 classes and 704 images. Additive salt-and-pepper noise with different noise densities 0.01, 0.02, 0.03, and 0.04 is added to the test set. The feature vectors based on the proposed invariants, geometric invariants, Legendre invariants, and Zhu’s invariants are used to classify these images. The comparison result is listed in Table 1. We can see that there are few differences among the four descriptors in noise-free case. However, with the increase of noise density, our method is more robust than the other three.Table 1
Classification results.
Noise-free
1%
2%
3%
4%
Geometric invariants
97.16
87.07
81.25
68.04
50.85
Legendre invariants
97.87
89.06
83.95
74.15
56.96
Zhu’s invariants
98.30
90.91
85.94
76.28
57.24
Proposed invariants
98.72
92.61
89.25
80.97
61.36Figure 7
Original alphanumeric characters as a training set for invariant character recognition.Figure 8


## 5. Conclusions

We have presented a new method to derive the scale invariance of 3D Tchebichef moments. To reduce the computation time, we have proposed an efficient algorithm based on matrix multiplication for computing both 3D moments and 3D invariants. Experimental results show that our method has better classification ability, it is more robust to noise than the existing moment-based methods, and it is very effective.



---

*Source: 813606-2013-04-16.xml*