1 Introduction

Moment invariants are defined as a function of the image moments, which have the property to remain unchangeable or invariant under certain group of image transformations, like rotation, translation, scaling, convolution, etc [16]. Due to this property, one can represent object features independently of the aforementioned deformations. As a result, the moment invariants descriptors have been attracting the interest of the scientific community and have become an important tool for the recognition and the classification of deformed objects. Indeed, the notion of moment invariants has been effectively applied in various domains such as image analysis [4, 28, 37, 53, 60, 64,65,66], pattern recognition [5, 15, 19, 50], image retrieval [2, 3, 46, 47], medical image analysis [6, 13, 20] and image watermarking [14, 54, 62]. In this diversity of applications the moment invariants were proved to be a very powerful tool for feature representation and extraction.

Generally, the family of moments and moment invariants can be categorized into two main groups: (1) non-orthogonal moments that is based on non-orthogonal kernel function, such as the geometric or the complex basis. (2) the orthogonal moments, where the basis function is typically represented by a continuous or discrete orthogonal polynomials. As well-known, the orthogonality property insures that no information redundancy over the extraction features and provide high description capability, which is considered as a major advantage over non-orthogonal ones. Moreover, according to the definition domain of the used polynomials basis, orthogonal moments can be further divided into moments defined in polar coordinate or Cartesian coordinate. One advantage of the moments defined in the Cartesian coordinate is the facility of obtaining scale and translation invariants in comparison with those defined in polar coordinate. While rotation invariants can be easily achieved in polar coordinate. A complete classification of the existing families of image moment is illustrated in Fig. 1.

Fig. 1
figure 1

Classification of the categories of image moment invariants

Full size image

Recently, the rapid development of the 3D imaging technologies and scanning devices, such as Computer Tomography (CT), Magnetic Resonance Imaging (MRI) and Light Detection And Ranging (LiDAR). Has leads to a variety of applications, like 3D surface image reconstruction [55] and 3D image registration [30], to tackle the problem of 3D object recognition and representation. As one of the most important tools in 3D image analysis, three-dimensional moment invariants has gained an increasing interest in latest years, especially in pattern recognition applications [7, 34, 43, 51, 59]. The reason is due to their capability to extract shape features independently of 3D geometric deformations. Actually, there are three methods for deriving invariants: (1) The normalization method, which is based on image normalization and aims to transform a distorted image input into its corresponding normal form, such that it is invariant to certain deformations [17, 18, 21, 39, 61]. (2) The indirect method, it relies on the algebraic relation between the image moments and geometric ones, in order to express moment invariants as a linear combination of Geometric Moment Invariants. Due to the simplicity of the indirect method, it has been extensively discussed [4, 36, 37, 40, 60]. (3) The direct method, it seeks to directly derive invariants from the image moments [9, 10, 56, 57, 67]. In fact, the main advantage of this method, is that moment invariants can be algebraically derived from orthogonal moments without the requirement of calculating the normalization parameters of the deformed image, or using the indirect methods to achieve the invariance through the Geometric Moment Invariants. So far, only few research studies concerning the derivation of moments invariants utilizing the direct method has been presented [38, 56], and no such paper dealing with the derivation of three-dimensional Rotation, Scaling and Translation (RST) moment invariants, using the direct method, has been published.

Motivated by the excellent properties of the Krawtchouk moments, which are the discrete orthogonality, the simplicity of implementation, representation in matrix form, the capability to extract local features and the high tolerance to different kinds of noise [4, 7, 60]. Also, noticing that the orthogonal moments, especially discrete orthogonal moments, have shown more robustness against image noise and high discrimination power for object detection and recognition in comparison with the non-orthogonal moments [16]. In the top of that, the study of the Krawtchouk Moment Invariants, using direct derivation method, for 3D image analysis and representation has not been carried out in the literature.

In this paper, we introduce a new set of discrete orthogonal moment invariants, named Direct Krawtchouk Moment Invariants (DKMI). This new set is algebraically derived from Krawtchouk Moments based on the corresponding Krawtchouk polynomials. Moreover, the proposed invariants can be used for the extraction of 3D shape features independently of rotation, scaling and translation deformations. As already mentioned, this proposed set will eliminate the need for the image normalization process or the computation of geometric moments to achieve the desired invariants.

It is well-known that the description of deformed objects with respect to geometric transformations as translation, scale and rotation, has a high significance in many computer vision tasks and very useful in pattern recognition. Therefore, the potential applications of the proposed three-dimensional moment invariants, can be found in variety of fields: such as the recognition of complex activities [31, 32], human motion identification and computer interaction [12, 33]. In addition, their applicability can be extended to object matching and tracking, where the tracked object usually encounters some appearance variations in-plane rotation, translation and scale change [23,24,25,26,27].

In summary, we will initially provide a short overview of the indirect derivation method of some existing moment invariants, namely Tchebichef, Krawtchouk and Hahn Moment Invariants. Then, we will present the detailed process for the direct derivation of our new set of invariants from 3D Krawtchouk Moments. Subsequently, several numerical experiments are presented, so as to validate the effectiveness of the proposed DKMI. First, we investigate their RST invariance and noise robustness. Second, the effect of image size on their numerical stability is discussed. Then, the recognition performance of the new DKMI is compared with the traditional indirect invariants in pattern recognition application. Finally, a comparison of computational speed between the proposed descriptors and the traditional ones is presented.

The rest of this paper is structured as follows: In Section 2, we present the traditional indirect method for deriving discrete orthogonal moment invariants. In Section 3, we introduce the proposed Direct Krawtchouk Moment Invariants. Section 4, is devoted to provide the appropriate experiments to demonstrate the usefulness of our proposed invariants. Finally, concluding remarks are presented in Section 5.

2 Classical 3D moment invariants

The usual method for obtaining rotation, scaling and translation moment invariants is to express the image moments as a linear combination of geometric ones, and then make use of rotation, scaling and translation geometric invariants instead of geometric moments.

2.1 Geometric moment invariants

The (n + m + k)-th order geometric moments mnmk of an image f(x, y, z) with the size N × M × K is defined using the discrete sum approximation as:

$$ m_{nmk}=\sum\limits_{x = 1}^{N}\sum\limits_{y = 1}^{M}\sum\limits_{z = 1}^{K}x^{n} y^{m} z^{k} f(x,y,z). $$
(1)

And the corresponding central geometric moments μnmk, which are translation invariants, are given by:

$$ \mu_{nmk}=\sum\limits_{x = 1}^{N}\sum\limits_{y = 1}^{M}\sum\limits_{z = 1}^{K}(x-x_{0})^{n} (y-y_{0})^{m} (z-z_{0})^{k} f(x,y,z), $$
(2)

where (x0, y0, z0) denotes the centroid coordinates of the 3D object, that are given by:

$$ x_{0}=\frac{m_{100}}{m_{000}},~y_{0}=\frac{m_{010}}{m_{000}},~z_{0}=\frac{m_{001}}{m_{000}}. $$
(3)

The 3D image rotation is usually performed as a series of three 2D rotations about each axis. In this section we consider the Euler Angle Sequence (x − y − z), which is commonly used in aerospace engineering and computer graphics. The 3D rotation matrix associated with the Euler Angle Sequence (x − y − z), is defined by the rotation along x axis by angle ϕ, along y axis by angle 𝜃 and along z axis by angle ψ:

$$ R_{xyz}(\phi,\theta,\psi)=R_{x} (\phi) R_{y} (\theta) R_{z} (\psi) $$
(4)
$$R_{xyz}(\phi,\theta,\psi)= \left( \begin{array}{lll} 1 & 0 & 0 \\ 0 & cos\phi & sin\phi \\ 0 & -sin\phi & cos\phi \end{array}\right) \left( \begin{array}{lll} cos\theta & 0 & -sin\theta \\ 0 & 1 & 0 \\ sin\theta & 0 & cos\theta \end{array}\right) \left( \begin{array}{lll} cos\psi & sin\psi & 0 \\ -sin\psi & cos\psi & 0 \\ 0 & 0 & 1 \end{array}\right) $$
$$ =\left( \begin{array}{lll} cos \theta~cos \psi~ & cos \theta~sin \psi~ & -sin \theta \\ sin \phi~sin \theta~cos \psi - cos\phi~sin \psi~ & sin \phi~sin \theta~sin \psi + cos \phi~cos \psi~ & cos \theta~sin \phi \\ cos \phi~sin \theta~cos \psi + sin\phi~sin \psi~ & cos \phi~sin \theta~sin \psi - sin \phi~cos \psi~ & cos \phi~cos \theta \end{array}\right). $$
(5)

In general way, the 3D rotation matrix can be expressed as a linear transformation of the 3D object coordinates, by:

$$ \left( \begin{array}{l} x^{\prime}\\ y^{\prime}\\ z^{\prime} \end{array}\right)= \left( \begin{array}{lll} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array}\right) \left( \begin{array}{lll} x \\ y \\ z \end{array}\right)= \left( \begin{array}{l} a_{11} x + a_{12} y + a_{13} z \\ a_{21} x + a_{22} y + a_{23} z\\ a_{31} x + a_{32} y + a_{33} z \end{array}\right). $$
(6)

Hence, in analogy with the geometric rotation invariants of the 2D case, we can obtain the (n + m + k)-th order of 3D Geometric Moment Invariants (GMI), which are independent of rotation, scaling and translation transforms, by the following formula:

$$ \nu_{nmk}= m_{000}^{-\gamma} \sum\limits_{x = 0}^{N-1} \sum\limits_{y = 0}^{M-1} \sum\limits_{z = 0}^{K-1} \left\{\begin{array}{l} [a_{11} (x-x_{0})+a_{12} (y-y_{0})+a_{13 }(z-z_{0})]^{n} \\ \times [a_{21} (x-x_{0})+a_{22} (y-y_{0})+a_{23} (z-z_{0})]^{m} \\ \times [a_{31} (x-x_{0})+a_{32} (y-y_{0})+a_{33} (z-z_{0})]^{k} \end{array}\right\} f(x,y,z) , $$
(7)

where \(\gamma = \frac {n+m+k}{3} + 1\).

By using the trinomial theorem, which is given by:

$$ (x+y+z)^{n}= \sum\limits_{i = 0}^{n} \sum\limits_{s = 0}^{n-i} \frac{n!}{i!s!(n-i-s)!} x^{i} y^{s} z^{n-i-s}, $$
(8)

the (7) can be further expressed in terms of central moments, as introduced in [7, 16], as follows:

$$ \begin{array}{ll} \nu_{nmk} & =\displaystyle m_{000}^{-\gamma} \sum\limits_{i = 0}^{n} \sum\limits_{s = 0}^{n-i} \sum\limits_{j = 0}^{m} \sum\limits_{t = 0}^{m-j} \sum\limits_{e = 0}^{k} \sum\limits_{f = 0}^{k-e} \frac{n!}{i!s!(n-i-s)!}\frac{m!}{j!t!(m-j-t)!}\frac{k!}{e!f!(k-e-f)!} \\ &\displaystyle \times a_{21}^{i}a_{22}^{s}a_{23}^{n-i-s} a_{21}^{j}a_{22}^{t}a_{23}^{m-j-t} a_{21}^{e}a_{22}^{f}a_{23}^{k-e-f} \mu_{i+j+e,s+t+f,n+m+k-i-s-j-t-e-f} . \end{array} $$
(9)

2.2 Indirect derivation of orthogonal moment invariants

Before presenting the traditional indirect method for deriving 3D Tchebichef, Krawtchouk and Hahn Moment Invariants, using geometric moment invariants, let us introduce some necessary notations and useful relations. Firstly, we need to provide the definition of the generalized hypergeometric functions 2 F1(⋅) and 3 F2(⋅):

$$ _{2}F_{1}(a_{1},a_{2};b;z)=\sum\limits_{k = 0}^{\infty}\frac{(a_{1})_{k}(a_{2})_{k}}{(b)_{k}} \frac{z^{k}}{k!}, $$
(10)
$$ _{3}F_{2}(a_{1},a_{2},a_{3};b_{1},b_{2};z)=\sum\limits_{k = 0}^{\infty}\frac{(a_{1})_{k}(a_{2})_{k}(a_{3})_{k}}{(b_{1})_{k}(b_{2})_{k}} \frac{z^{k}}{k!}, $$
(11)

where (a)k is the Pochhammer symbol, also called raising factorial, given by:

$$ (a)_{k}=a(a + 1)(a + 2)...(a+k-1)= \frac{\Gamma(a+k)}{\Gamma(a)}, $$
(12)

and Γ(n) = (n − 1)! is the gamma function.

We can also introduce the falling factorial denoted by 〈x〉k defined as:

$$ \langle x\rangle_{k} = (-1)^{k} (-x)_{k} . $$
(13)

As mentioned in [11], 〈x〉k can be expanded as:

$$ \langle x\rangle_{k} =\sum\limits_{i = 0}^{k}S_{1}(k,i)x^{i}, $$
(14)

where S1(k, i) are the Stirling numbers of the first kind, obtained by the following recurrence relation:

$$ S_{1}(k,i)=S_{1}(k-1,i-1)-(k-1)S_{1}(k-1,i), k \geq 1, i \geq 1, $$
(15)

with S1(k,0) = S1(0, i) = 0, and S1(0, 0) = 1.

2.2.1 Indirect Tchebichef moment invariants

The Tchebichef polynomials was introduced by Pafnuty Chebychev in [52], and firstly used in image analysis by Mukundan et al. [37] as a basis function for image moments. The (n + m + k)-th order 3D Tchebichef Moments, for an image function f(x, y, z) of the size N × M × K is defined as:

$$ TM_{nmk}=\sum\limits_{x = 0}^{N-1}\sum\limits_{y = 0}^{M-1}\sum\limits_{z = 0}^{K-1}\bar{t}_{n}(x,N)\bar{t}_{m}(y,N)\bar{t}_{k}(z,N)f(x,y,z), $$
(16)

where \(\bar {t}_{n}(x;N)\) is the n-th order weighted Tchebichef polynomials defined by:

$$ \bar{t}_{n}(x;N)=t_{n}(x;N)\sqrt{\frac{w_{t}(x)}{\rho_{t}(n)}}, $$
(17)

and tn(x; N) is n-th order discrete orthogonal Tchebichef polynomials, with respect to the weight function wt(x) and normalization function ρt(n), which are defined respectively by :

$$ w_{t}(x)= 1, $$
(18)

and

$$ \rho_{t}(n)= 2n!{N+n \choose 2n + 1}. $$
(19)

The classical Tchebichef orthogonal polynomials with x = 0,1,..., N − 1, are defined in terms of generalized hypergeometric function as:

$$ t_{n}(x;N)=(1-N)_{n}\:_{3} F_{2}(-n,-x,1+n;1,1-N;1), $$
(20)

and can be expanded as:

$$ t_{n}(x;N)=\sum\limits_{i = 0}^{n} A_{n,i} x^{i}, $$
(21)

with

$$ A_{n,i} = \sum\limits_{k=i}^{n} \frac{(-1)^{n-k} (N-1-k)! (n+k)!}{(k!)^{2} (N-1-n)! (n-k)!} S_{1}(k,i). $$
(22)

Substituting (21) to (16), the Tchebichef Moments can be written in terms of geometric moments as:

$$ TM_{nmk}= \frac{1}{\rho_{t}(n)\rho_{t}(m)\rho_{t}(k)} \sum\limits_{p = 0}^{n}\sum\limits_{q = 0}^{m}\sum\limits_{r = 0}^{k} A_{n,p} A_{m,q} A_{k,r} m_{pqr}, $$
(23)

and by replacing mpqr in (23) by νpqr of (9) we can obtain Tchebichef Moment Invariants (TMI) of the order n + m + k, which are rotation, scaling and translation invariants of Tchebichef Moments.

2.2.2 Indirect Krawtchouk moment invariants

The Krawtchouk polynomials was introduced by Mikhail Kravchuk in [22], and applied in image analysis by Yap et al. [60] as a basis function of discrete Krawtchouk Moments. The (n + m + k)-th order 3D Krawtchouk Moments, for an image f(x, y, z) of the size N × M × K is defined as:

$$ KM_{nmk}=\sum\limits_{x = 0}^{N-1}\sum\limits_{y = 0}^{M-1}\sum\limits_{z = 0}^{K-1}\bar{k}_{n}(x;p_{x},N)\bar{k}_{m}(y;p_{y},N)\bar{k}_{k}(z;p_{z},N)f(x,y,z), $$
(24)

where \(\bar {k}_{n}(x;p,N)\) is the n-th order weighted Krawtchouk polynomials defined by:

$$ \bar{k}_{n}(x;p,N)=k_{n}(x;p,N)\sqrt{\frac{w_{k}(x)}{\rho_{k}(n)}}, $$
(25)

and kn(x; p, N) are the Krawtchouk polynomials with x = 0,1,..., N − 1,0 < p < 1, which forms a discrete orthogonal basis, with respect to the weight function:

$$ w_{k}(x)={N \choose x} p^{x}(1-p)^{N-x}, $$
(26)

and the squared norm:

$$ \rho_{k}(n)=(-1)^{n} \left( \frac{1-p}{p} \right)^{n}\frac{n!}{(-N)_{n}}. $$
(27)

Generally, the Krawtchouk polynomials of the n-th order can be expressed in terms of the generalized hypergeometric function (10) as follows:

$$ k_{n}(x;p,N)=\:_{2}F_{1} \left( -n,-x;-N;\frac{1}{p} \right), $$
(28)

where x, n = 0,1,..., N − 1, N > 0, 0 < p < 1. And can be expanded as a linear combination of monomials xi as:

$$ k_{n}(x;p,N)=\sum\limits_{i = 0}^{n} C_{n,i} x^{i}, $$
(29)

with

$$ C_{n,i} = \sum\limits_{k=i}^{n} \frac{(-1)^{k} n! (N-k)!}{(p)^{k} N! (n-k)! k!} S_{1}(k,i), $$
(30)

According to [60], the Krawtchouk Moments can be written in terms of geometric moments as:

$$ KM_{nmk}= \frac{1}{\rho_{k}(n)\rho_{k}(m)\rho_{k}(k)} \sum\limits_{p = 0}^{n}\sum\limits_{q = 0}^{m}\sum\limits_{r = 0}^{k} C_{n,p} C_{m,q} C_{k,r} m_{pqr}, $$
(31)

by replacing mpqr in of (31) by νpqr (9) we can obtain Krawtchouk Moment Invariants (KMI) of the order n + m + k, which are rotation, scaling and translation invariants of Krawtchouk Moments.

As well-known the Krawtchouk moments are well suited for extracting local features according to any ROI (Region Of Interest) of the 3D image [7]. In fact, the 3D Krawtchouk Moments (24) involves three binomial distribution parameters px, py and pz of Krawtchouk polynomials, which correspond respectively to the x-axis, y-axis and z-axis.

These parameters can be used to shift the Region of Interest to the desired position. Where, px is used to shift the ROI horizontally along x-axis, if px < 0.5 the ROI is shifted to the left, while for px > 0.5 the ROI is shifted to the right. While, py is used to shift the ROI horizontally along y-axis, for py < 0.5 we shift the ROI to the left, while for py > 0.5 the ROI is shifted to the right. Finally, pz is used to shifting the ROI vertically along z-axis, when pz < 0.5 the ROI is shifted to bottom while pz > 0.5 the ROI is shifted to top.

For detailed discussion about the Krawtchouk Moments, we refer readers to [4, 7, 60].

2.2.3 Indirect Hahn moment invariants

The discrete orthogonal Hahn polynomials has been firstly introduced in the field of image analysis by Zhu et al. in [64]. Similarly to 3D Tchebichef and Krawtchouk Moments, we can define the (n + m + k)-th order 3D Hahn Moments, for an image f(x, y, z) of the size N × M × K, as follows:

$$ HM_{nmk}=\sum\limits_{x = 0}^{N-1}\sum\limits_{y = 0}^{M-1}\sum\limits_{z = 0}^{K-1}\bar{h}_{n}^{(a,b)}(x;N)\bar{h}_{m}^{(a,b)}(y;N)\bar{h}_{k}^{(a,b)}(z;N)f(x,y,z), $$
(32)

where \(\bar {h}_{n}^{(a,b)}(x;N)\) is the normalized Hahn polynomials \(h_{n}^{(a,b)}(x;N)\), which can be obtained by utilizing the squared norm and weight function as:

$$ \bar{h}_{n}^{(a,b)}(x;N)=h_{n}^{(a,b)}(x;N)\sqrt{\frac{w_{h}(x)}{\rho_{h}(n)}}, $$
(33)

ρh(n) denotes the squared norm, defined by:

$$ \rho_{h}(n)=\frac{\Gamma(a+n + 1)\Gamma(b+n + 1)(a+b+n + 1)_{N}}{(a+b + 2n + 1)n!(N-n-1)!}, $$
(34)

and wh(x) is the weight function associated with the discrete Hahn polynomials:

$$ w_{h}(x)=\frac{\Gamma(N+a-x)\Gamma(b + 1+x)}{\Gamma(N-x)\Gamma(x + 1)}. $$
(35)

The n-th order Hahn polynomials is defined by using hypergeometric function as:

$$ h_{n}^{(a,b)}(x;N)= \frac{(-1)^{n} (b + 1)_{n} (N-n)_{n}}{n!} \:_{3}F_{2} (-n,-x,n + 1+a+b;b + 1,1-N;1), $$
(36)

with x, n = 0,1,..., N − 1, a > − 1 and b > − 1.

The \(h_{n}^{(a,b)}(x;N)\) can be expanded as:

$$ h_{n}^{(a,b)}(x;N)=\sum\limits_{i = 0}^{n} B_{n,i} x^{i}, $$
(37)

with

$$ B_{n,i} = \sum\limits_{k=i}^{n} \frac{(b+n)! (a+b+k+n)!}{(n-k)! (b+k)! (a+b+n)! k! } S_{1}(k,i). $$
(38)

In a similar way to the 3D Krawtchouk Moments, the 3D Hahn Moments can be written in terms of the geometric moments as:

$$ HM_{nmk}= \frac{1}{\rho_{h}(n)\rho_{h}(m)\rho_{h}(k)} \sum\limits_{p = 0}^{n}\sum\limits_{q = 0}^{m}\sum\limits_{r = 0}^{k} B_{n,p} B_{m,q} B_{k,r} m_{pqr}, $$
(39)

To obtain 3D Hahn Moment Invariants (HMI), we can simply replace the geometric moments mpqr in (39) by the geometric moment invariants νpqr defined by (9).

3 Proposed approach: direct derivation of 3D moment invariants

In the previous section we have briefly discussed the indirect method for obtaining rotation, scale and translation invariance of some existing discrete orthogonal moments, which make use of the respective invariants of the geometric moments. In this current section, we introduce a direct derivation method of a new set of 3D object shape descriptors based on Krawtchouk polynomials, where the rotation, scaling and translation invariants are achieved directly from the Krawtchouk Moments. It worth noting that, the proposed method could be easily generalized in order to derive invariants from the other discrete orthogonal moments.

As previously mentioned in Section 2.2.2, the Krawtchouk polynomials can be defined in terms of monomials xi:

$$ k_{n}(x;p,N)=\sum\limits_{i = 0}^{n} C_{n,i} x^{i}, $$
(40)

with

$$ C_{n,i} = \sum\limits_{k=i}^{n} \frac{(-1)^{k} n! (N-k)!}{(p)^{k} N! (n-k)! k!} S_{1}(k,i). $$
(41)

For notation simplicity, we introduce a matrix representation of (40) as:

$$ K_{m}(x)=C_{m} X_{m}(x), $$
(42)

where Km(x) = (k0(x; p, N), k1(x; p, N),..., kn(x; p, N))T , Xm(x) = (x0, x1,..., xn)T and Cm = (Cn, i) with 0 ≤ i ≤ n ≤ m.

From (41) we can deduce that Cm is a lower triangular matrix, and since all its diagonal elements \(C_{i,i}=\left (\frac {-1}{p}\right )^{i} \frac {(N-1)!}{N!} \) are different from zero, the matrix Cm is non singular (invertible). As a result of the above analysis, we can give the following Lemma.

Lemma 1

The corresponding inverse formula of (40), which can be used to represent xi in terms of Krawtchouk polynomials ks(x; p, N) with s ≤ i, is given by:

$$ x^{i} =\sum\limits_{s = 0}^{i} D_{i,s} k_{s}(x;p,N), $$
(43)

where Di, s is an element of the matrix Dm = (Di, s) with 0 ≤ s ≤ i ≤ m, and Dm is the inverse matrix of Cm of (42). The elements of the matrix Dm are given as follows:

$$ D_{i,s}=\sum\limits_{m=s}^{i} S_{2}(i,m) \frac{(-1)^{s} m! N! p^{m}}{(m-s)!(N-m)! s!}, $$
(44)

and S2(i, m) is the Stirling numbers of the second kind, which can be computed by using the following recurrence relation:

$$ S_{2}(i,m)=S_{2}(i-1,m-1)-iS_{2}(i-1,m), i \geq 1, m \geq 1, $$
(45)

with S2(i, 0) = S2(0, m) = 0, and S2(0, 0) = 1.

Similar proof of Lemma 1 can be found in [63], with slight modifications.

It is important to note, that the Stirling numbers of the first and second kinds can be considered inverses of one another, and satisfy the following property:

$$ \sum\limits_{l = 0}^{max(k,j)+ 1} S_{1}(l,j)S_{2}(k,l)=\delta_{j,k} $$
(46)

and

$$ \sum\limits_{l = 0}^{max(k,j)+ 1} S_{1}(k,l)S_{2}(l,j)=\delta_{j,k}, $$
(47)

where δj, k is the Kronecker delta.

3.1 3D translation invariants

Let ft(x, y) be the translated version of the original image f(x, y), we have:

$$ f^{t}(x,y)=f(x-x_{0},y-y_{0}). $$
(48)

We can define the Krawtchouk Moments \(KM_{nm}^{t}\) of the translated image as follows:

$$ KM_{nmk}^{t}=\sum\limits_{x = 0}^{N-1}\sum\limits_{y = 0}^{M-1}\sum\limits_{z = 0}^{K-1} k_{n}(x-x_{0};p,N)k_{m}(y-y_{0};p,M) k_{k}(z-z_{0};p,K)f(x,y,z). $$
(49)

To simplify the previous expression, we give the following proposition:

Proposition 1

The Krawtchouk Moments \(KM_{nmk}^{t}\) of a translated image ft(x, y, z) can be written in terms of KMuvw of the original image f(x, y, z) as:

$$ \begin{array}{ll} KM_{nmk}^{t}= &\displaystyle \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{m}\sum\limits_{e = 0}^{k} \sum\limits_{s = 0}^{i}\sum\limits_{t = 0}^{j}\sum\limits_{f = 0}^{e} \sum\limits_{u = 0}^{s}\sum\limits_{v = 0}^{t}\sum\limits_{w = 0}^{f} {i \choose s} {j \choose t} {e \choose f} \\ &\displaystyle \times C_{n,i}C_{m,j}C_{k,e}D_{s,u}D_{t,v}D_{f,w} (-1)^{i-s+j-t+e-f} x_{0}^{i-s} y_{0}^{j-t} z_{0}^{e-f} KM_{uvw}. \end{array} $$
(50)

The proof of Proposition 1 is given in Appendix A.

As can be concluded from the Proposition 1, the Krawtchouk Moments of any translated image by a translation vector (x0, y0, z0) can be expressed in terms of the Krawtchouk moments of the original image.

At this point, the translation moment invariants can be directly derived from the Krawtchouk moments, by replacing the vector (x0, y0, z0) by the image centroid coordinates \((\bar {x}, \bar {y}, \bar {z})\). Where the centroids of x-, y- and z-coordinate, denoted respectively by \(\bar {x}, \bar {y}, \bar {z}\), and can be derived as:

$$ \begin{array}{ll} &\displaystyle \bar{x}=\frac{C_{0, 0} KM_{100}-C_{1,0} KM_{000}}{C_{1,1} KM_{000}}, \bar{y}=\frac{C_{0, 0} KM_{010}-C_{1,0} KM_{000}}{C_{1,1} KM_{000}} \\ &\displaystyle \text{ and } \bar{z}=\frac{C_{0, 0} KM_{001}-C_{1,0} KM_{000}}{C_{1,1} KM_{000}}. \end{array} $$
(51)

Hence, any effect of image translation on the \(KM_{nmk}^{t}\), can be canceled by this translation normalization. Which makes \(KM_{nmk}^{t}\) translation invariant. And along this paper, will be denoted by \(I_{nmk}^{t}\):

$$ \begin{array}{ll} I_{nmk}^{t}= &\displaystyle \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{m}\sum\limits_{e = 0}^{k} \sum\limits_{s = 0}^{i}\sum\limits_{t = 0}^{j}\sum\limits_{f = 0}^{e} \sum\limits_{u = 0}^{s}\sum\limits_{v = 0}^{t}\sum\limits_{w = 0}^{f} {i \choose s} {j \choose t} {e \choose f} \\ &\displaystyle \times C_{n,i}C_{m,j}C_{k,e}D_{s,u}D_{t,v}D_{f,w} (-1)^{i-s+j-t+e-f} (\bar{x})^{i-s} (\bar{y})^{j-t} (\bar{z})^{e-f} KM_{uvw}. \end{array} $$
(52)

3.2 3D Rotation and scale invariants

In this subsection, we discuss the direct derivation of rotation and scaling invariants of a 3D object from the Krawtchouk Moments.

Suppose that fd(x, y, z) is a deformed version of the original object f(x, y, z), which has been transformed according to (6), we have

$$ f^{d}(x,y,z)=f(a_{11} x + a_{12} y + a_{13} z , a_{21} x + a_{22} y + a_{23} z, a_{31} x + a_{32} y + a_{33} z). $$
(53)

The Krawtchouk Moments of the deformed object fd(x, y, z) is defined as

$$ \begin{array}{ll} \displaystyle KM_{nmk}^{d}=\sum\limits_{x = 0}^{N-1}\sum\limits_{y = 0}^{M-1}\sum\limits_{z = 0}^{K-1} & k_{n}(a_{11} x + a_{12} y + a_{13} z;p,N) k_{m}(a_{21} x + a_{22} y + a_{23} z;p,M) \\ &\displaystyle \times k_{k}(a_{31} x + a_{32} y + a_{33} z;p,K)f(x,y,z), \end{array} $$
(54)

To simplify the previous equation, we give the following proposition:

Proposition 2

The Krawtchouk Moments \(KM_{nmk}^{d}\) of any deformed image fd(x, y, z) can be written in terms of KMuvw of the original image f(x, y, z) as:

$$ \begin{array}{ll} KM_{nmk}^{d}= &\displaystyle \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{m}\sum\limits_{e = 0}^{k} \sum\limits_{s = 0}^{i}\sum\limits_{t = 0}^{j}\sum\limits_{f = 0}^{e} \sum\limits_{u = 0}^{s}\sum\limits_{v = 0}^{t}\sum\limits_{w = 0}^{f} \sum\limits_{r = 0}^{\delta}\sum\limits_{l = 0}^{\sigma}\sum\limits_{d = 0}^{\epsilon} \\ &\displaystyle \frac{i!}{s!u!(i-s-u)!} \frac{j!}{t!v!(j-t-v)!} \frac{e!}{f!w!(e-f-w)!} C_{n,i}C_{m,j}C_{k,e} \\ &\displaystyle \times D_{\delta,r}D_{\sigma,l}D_{\epsilon,d} a_{11}^{s} a_{12}^{u} a_{13}^{i-s-h} a_{21}^{t} a_{22}^{v} a_{23}^{j-t-v} a_{31}^{f} a_{32}^{w} a_{33}^{e-f-w} KM_{rld}~, \end{array} $$
(55)

where δ = s + t + f, σ = u + v + w and 𝜖 = i − s − h + j − t + e − f − w.

The proof of Proposition 2 is given in Appendix B.

The above Proposition 2 shows that The Krawtchouk Moments of any 3D scaled and rotated object, can be expressed as a linear combination of The Krawtchouk Moments KMrld of the original object. Based on this relationship, we can construct a set of rotation and scaling invariants \(I_{nmk}^{rs}\)from the Krawtchouk Moments, as follows:

$$ \begin{array}{ll} I_{nmk}^{rs}= &\displaystyle \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{m}\sum\limits_{e = 0}^{k} \sum\limits_{s = 0}^{i}\sum\limits_{t = 0}^{j}\sum\limits_{f = 0}^{e} \sum\limits_{u = 0}^{s}\sum\limits_{v = 0}^{t}\sum\limits_{w = 0}^{f} \sum\limits_{r = 0}^{\delta}\sum\limits_{l = 0}^{\sigma}\sum\limits_{d = 0}^{\epsilon} \\ &\displaystyle \frac{i!}{s!u!(i-s-u)!} \frac{j!}{t!v!(j-t-v)!} \frac{e!}{f!w!(e-f-w)!} C_{n,i}C_{m,j}C_{k,e} \\ &\displaystyle \times (\lambda)^{\gamma} D_{\delta,r}D_{\sigma,l}D_{\epsilon,d} a_{11}^{s} a_{12}^{u} a_{13}^{i-s-h} a_{21}^{t} a_{22}^{v} a_{23}^{j-t-v} a_{31}^{f} a_{32}^{w} a_{33}^{e-f-w} KM_{rld}~, \end{array} $$
(56)

where \( \gamma = -\frac {i+j+e + 3}{3}\) and λ = KM000 are used for scale normalization. And aij are corresponding to the elements of the rotation matrix (5). Where it’s angles vales are given by \( \phi = \frac {1}{2} tan^{-1}((u KM_{011}- v KM_{000})/(KM_{020}-KM_{002})) \), \( \theta = \frac {1}{2} tan^{-1}((u KM_{101}- v KM_{000})/(KM_{200}-KM_{002})) \) and \( \psi = \frac {1}{2} tan^{-1}((u KM_{110}- v KM_{000})/(KM_{200}-KM_{020})) \) with u = 2C22 C00/(C11)2 and v = 2C22(C10)2/C00(C11)2.

Based on (56), we can directly derive the 3D rotation, scaling and translation invariants of Krawtchouk moments \(I_{nmk}^{rst}\), if we replace the Krawtchouk Moments KMrld on the right sides of (56) by the direct translation invariants \(I_{nmk}^{t}\) of (52). The 3D moment invariants \(I_{nmk}^{rst}\) developed in this section, will be denoted along the rest of this paper by the Direct Krawtchouk Moment Invariants (DKMI).

4 Experimental results and discussion

In this section, several numerical experiments are carried out to validate the effectiveness of the newly introduced moment invariants. This section is divided into four subsections. In the first one, we investigate the invariability property of the proposed Moment Invariants against different geometric deformations and noise degradation. In the second subsection, we will demonstrate the numerical stability of the proposed invariants, conjointly with the illustration of the image size effect on the traditional moment invariants. In the third subsection, the classification performance of the proposed moment invariants is effectively compared with the traditional Geometric, Tchebichef, Krawtchouk and Hahn Moment Invariants, using the McGill 3D Shape Benchmark [45]. Finally, we provide a comparative analysis concerning the computational time in the last subsection.

It is important to note that all algorithms are implemented in MATLAB 8.5, and all numerical experiments are performed under Microsoft Windows environment on a PC with Intel Core i3 CPU 2.4 GHz and 4 GB RAM.

4.1 Invariability

In this experiment, the property of invariability of the proposed invariants is examined under various sets of rotation, scaling and translation transformations. Moreover, the effect of different densities of noise on their numerical accuracy is investigated. As well, the influence of the Krawtchouk polynomials parameter p on the invariability of our introduced invariants have been also illustrated in this subsection.

The 3D Airplane and Vertebra Model, which shown in Fig. 2, are firstly affected by various deformations of rotation, scaling, translation and noise adding. Then, moment invariants of the original and the transformed objects are computed up to the sixth order (n, m, k ≤ 2), using three cases: (A) p1 = p2 = p3 = 0.4, (B) p1 = p2 = p3 = 0.5 and (C) p1 = p2 = p3 = 0.6. Subsequently, the relative error between moment invariants coefficients of the original and the transformed images is calculated as follow:

$$ Relative Error (f, g)=\frac{||MI(f)-MI(g)||}{|| MI(f)||}, $$
(57)

where ||⋅||, f and g denote respectively the Euclidean norm, the original and the transformed images. It worth noting that a low relative error leads to high numerical accuracy.

Fig. 2
figure 2

3D test objects: Airplane (a), Medical Vertebra Model (b), of size 128 × 128 × 128 voxels

Full size image

To verify translation invariance, the test objects are transformed according to a translation vector that takes values between (-16, -16, -16) and (16, 16, 16) with step (4, 4, 4). Consequently, the relative errors of the invariants are presented in Fig. 3. Similarly, scale invariance of the proposed invariants is examined by using the test objects, which are transformed by scaling factors starting from 0.75 to 1.25 with step 0.05. Then, the corresponding results are depicted in Fig. 4.

Fig. 3
figure 3

Relative errors for Airplane (a) and Vertebra Model (b) of the proposed invariants between the original objects and the translated versions

Full size image
Fig. 4
figure 4

Relative errors for Airplane (a) and Vertebra Model (b) of the proposed invariants between the original objects and the scaled ones

Full size image

To demonstrate the rotation invariance, we are conducted in this experiment to verify the rotation invariability about each of the three axis (x-axis, y-axis and z-axis). In fact, the test images is rotated about each axis by a rotation angle varying between 0∘ and 90∘ with interval 10∘. Accordingly, the relative errors of the introduced invariants about the x-axis, y-axis z-axis are respectively presented in Figs. 5, 6 and 7.

Fig. 5
figure 5

Relative errors for Airplane (a) and Vertebra Model (b) of the proposed invariants against rotation about the x-axis by different angle varying from 0∘ to 90∘

Full size image
Fig. 6
figure 6

Relative errors for Airplane (a) and Vertebra Model (b) of the proposed invariants against rotation about the y-axis by different angle varying from 0∘ to 90∘

Full size image
Fig. 7
figure 7

Relative errors for Airplane (a) and Vertebra Model (b) of the proposed invariants against rotation about the z-axis by different angle varying from 0∘ to 90∘

Full size image

Finally, in order to depict the noise robustness of the proposed moment invariants. In a similar way to the previous experiments, the test objects have been corrupted by different densities of Salt-and-Pepper noise varying from 0% to 5% with interval 0.5%. Then, the corresponding results are presented in Fig. 8.

Fig. 8
figure 8

Relative errors for Airplane (a) and Vertebra Model (b), between the corrupted 3D objects and the original test objects, by using the proposed invariants

Full size image

Examining the Figs. 3–8, it is clear that the relative error rates is very low (in the order of 10− 5), which indicate that the proposed moment invariants exhibit good performance and express high numerical accuracy under different geometric transformations, as well as, in the presence of noisy effects. Moreover, one can observe the influence of the parameter p on the invariability property of DKMI, where the special case (B) p1 = p2 = p3 = 0.5 gives the best performance, which could help in choosing the best parameters for pattern recognition applications. As a conclusion, this new set of invariants could be highly useful to extract features for pattern recognition and 3D object classification.

4.2 Numerical stability

Generally, the computation of moments and moment invariants includes a significant number of factorial and power terms, which can undoubtedly leads to overflow and finite precision errors, especially for moment invariants of high orders. Consequently, the classification accuracy will be highly influenced by numerical instability, when higher order moment invariants are required to provide additional description of the image contents [8, 48].

Therefore, in this subsection we will examine the image size effects on the numerical stability of the proposed moment invariants. In fact, we will use the Airplane test image, shown in Fig. 2, with variety of sizes: 32 × 32 × 32,48 × 48 × 48,⋯ ,128 × 128 × 128. Indeed, we are particularly interested, in this experiment, to the maximum moment’s order, which can be correctly computed without overflow.

In Table 1, we depict respectively in the second, third and fourth columns the maximum computation order (n + m + k), concerning GMI, KMI and the proposed DKMI for different image sizes. It worth noting that, the computation of (n + m + k)-th order of RST moment invariants , using (9) or (56), depends on computing translation invariants up to the (3n + 3m + 3k)-th order, which means that the maximum order that could be theoretically computed is equal to \((\frac {N-1}{3} + \frac {M-1}{3} + \frac {K-1}{3})\).

Table 1 Image size effect on the maximum computation order of the proposed invariants in comparison with the traditional Geometric and Krawtchouk moment invariants, for different image sizes
Full size table

The results presented in Table 1 clearly show that the computation of GMI is numerically unstable which is reflected in the limited number of moment invariants that can be correctly computed. Whereas, Geometric Moment Invariants up to the order \((\frac {N-1}{3} + \frac {M-1}{3} + \frac {K-1}{3})\) must be theoretically computed. This limitation is practically associated with the finite precision errors and overflow conditions. Moreover, the traditional KMI produce similar results, which is mainly inherited the use of Geometric Moment Invariants. And can be justified by the fact that the traditional KMI is expressed as a linear combination of Geometric Moment Invariants. In the contrary, the proposed invariants presents high numerical stability due to the reason that these invariants are explicitly derived from the Krawtchouk Moments, which have the orthogonality property. In fact, the main advantage of Direct Krawtchouk Moment Invariants, relies on the fact that the Krawtchouk polynomials kn(x; p, N) have a limited range of values and can be computed exactly for any value of x ∈ [0, N − 1], while the geometric basis xn can leads to overflow problem for large values of x. Finally, it is important to note that, although the computation of DKMI is very accurate, we can not achieve the theoretical maximum moment’s order.

4.3 3D object recognition

In the current subsection, the recognition accuracy of the proposed moment invariants is evaluated on the public 3D image database [45], where all images are of size 128 × 128 × 128 voxels. In fact, this experiments is conducted on a testing set composed of ten classes, each one contains three different objects. All images in this set are affected by different transformations (4 translations + 4 scaling + 4 rotations + 4 mixed transforms), in order to generate 480 objects per database, some samples are shown in Fig. 9. Moreover, to study the noise robustness of proposed invariants, five additional testing sets are created by adding different densities of Salt-and-Pepper noise {1%; 2%; 3%; 4%; 5%}.

Fig. 9
figure 9

Some examples from the used dataset

Full size image

The recognition performance of our proposed method is compared with the classical Geometric, Tchebichef, Krawtchouk and Hahn Moment Invariants. In addition, the k-Nearest Neighbors classifier with k = 1 is employed for the classification task with 5-folds cross validation, where moment invariants up to the 9-th order (n, m, k ≤ 3) are used to construct the features vector. For each testing set, the correct recognition rates are obtained and summarized in Table 2.

Table 2 Comparative analysis of 3D object classification accuracy by using the Geometric, Tchebichef, Krawtchouk, Hahn and the proposed Direct Krawtchouk Moment Invariants
Full size table

As can be clearly observed from Table 2, the average recognition accuracy of our proposed method are significantly higher than those obtained by classical methods. In addition, experimental results on the datasets corrupted by additive noise, demonstrate that the proposed descriptors are more effective than the existing ones. Eventually, our new invariants could be a highly useful in the field of 3D object recognition.

4.4 Computational time

To test the computational efficiency of the proposed method. In this current numerical experiment, we have used a set of five test images, shown in Fig. 10, selected from the public McGill 3D Shape Benchmark [45]. The average computational time of the proposed invariants and the existing methods, is measured for the five images using two different resolutions 64 × 64 × 64 and 128 × 128 × 128 voxels. Subsequently, the TRR (Time Reduction Rate) of our proposed invariants is calculated using the following formula:

$$ TRR=\frac{1- Time_{1}}{Time_{2}}\times 100, $$
(58)

where Time1 and Time2 are respectively the average times of the proposed and the traditional moment invariants. Moreover, this experiment is conducted for different maximum moment invariants orders 3, 6 and 9. The corresponding average times and TRR are summarized in Table 3.

Fig. 10
figure 10

The five test images used in computational time evaluation

Full size image
Table 3 Comparative analysis of average computation times in (Second) and Time Reduction Rate, between the proposed moment invariants and the traditional one for different image sizes
Full size table

It should be noted that in this experiment, we will compare the results of the proposed method with only the classical Krawtchouk Moment Invariants. Since the Tchebichef and Hahn Moment Invariants follow the same computational process for extracting invariants from the geometric moments.

Based on the results of Table 3, it can be clearly seen that the computation of the proposed invariants is much faster than traditional method. Moreover, the presented time reduction rates was very significant for both resolutions 64 × 64 × 64 and 128 × 128 × 128 voxels. In fact, this improvement in speed is achieved because the computation of the translation invariants are performed by transforming the original 3D image to the geometric center, and then the calculation of Krawtchouk moments is carried out. Instead of computing translation invariants by using (52), which is very time consuming. Eventually, this introduced new set of invariants could be very useful for object classification and recognition, especially for real time applications or when large databases are used.

5 Conclusion

The main contribution of this paper relies on the derivation of a new set of moment invariants, namely Direct Krawtchouk Moment Invariants. Where we have established a theoretical framework for the direct computation of this set of moment invariants from the Krawtchouk Moments, using some algebraic properties of Krawtchouk polynomials. This new set can be used for extracting shape features independently of geometric rotation, scaling and translation distortions, and can be employed as pattern features for 3D object classification applications.

Accordingly, several numerical experiments are performed, including invariability to geometric transforms and noise robustness, numerical stability, object classification accuracy and computational efficiency. As demonstrated in the numerical experiment section, the proposed 3D invariants DKMI are not only accurate, but also provide very fast computation even for high moment invariants orders. In addition, this new set shows sufficient stability and discrimination power to be used as pattern feature. To conclude, the proposed Direct Krawtchouk Moment Invariants are potentially useful as features descriptor for 3D object recognition, and the method described in this paper can be easily generalized for the construction of moment invariants from other discrete orthogonal moments.

In our future works, we plan to introduce new sets of 3D moment invariants based on the proposed direct method and other orthogonal polynomials, like Racah, and dual Hahn orthogonal polynomials. Also, we will concentrate on generalizing the proposed method for extracting 3D affine moment invariants. Finally, we will focus on some potential applications of the proposed 3D invariants in the fields of action recognition, 3D image retrieval and medical image analysis.