Radial Tchebichef Invariants for Pattern Recognition

� Abstract—This paper presents the mathematical framework of radial Tchebichef moment invariants, and investigates their feature representation capabilities for pattern recognition applications. The radial Tchebichef moments are constructed using the discrete orthogonal Tchebichef polynomials as the kernel, and they have a radial-polar form similar to that of Zernike moments. The discrete form of the moment transforms make them particularly suitable for image processing tasks. Experimental results showing the primary attributes such as invariance and orthogonality of the proposed moment functions are also given. Index Terms—Discrete transforms, feature extraction, image reconstruction, orthogonal functions, pattern recognition. I. INTRODUCTION ATTERN recognition and other similar applications require robust feature descriptors that are invariant to rotational transformations. Zernike and Pseudo-Zernike moments have been found to have the desirable qualities of orthogonality and robustness, which could be exploited in a variety of tasks involving identification or recognition of objects [1],[2]. However, moments constructed using continuous orthogonal polynomials such as Zernike functions require a coordinate transformation to the domain of the functions, which is usually the interior of a unit circle [3],[4]. Correspondingly, a discrete approximation of the moment integrals could also introduce numerical errors in the computation of feature descriptors. The primary motivation for developing discrete orthogonal invariants arises from the need to eliminate image coordinate transformations and the discretization step in the moment calculation. Radial Tchebichef invariants retain the basic form of Zernike moments (so that the rotational invariants can be derived easily), but use one- dimensional Tchebichef polynomials in the kernel [3], leading to a moment definition that operates directly in the image space. In other words, the most powerful characteristics of Tchebichef moments (discrete, orthogonal), and Zernike moments (rotational invariance) have been combined to create the proposed class of radial Tchebichef invariants. This paper presents the essential framework required for the computation of radial Tchebichef moments, and investigates the properties such as orthogonality, rotational invariance, and robustness with respect to input noise. The paper is organized as follows: The next section gives the definition of Tchebichef polynomials and moments. Radial Tchebichef moments are introduced in Section III, along with Zernike moments to make the similarities in the structure of the two types of moments evident. Section IV gives an outline of rotational invariants using radial Tchebichef moments. Key implementation aspects related to the computation of radial invariants are discussed in Section V. Experimental results demonstrating the invariance characteristics of these functions, and the reconstruction capability of the corresponding moments are given in Section VI. Concluding remarks are given in Section VII. II. TCHEBICHEF MOMENTS The Tchebichef moments of order p+q of an image f(x, y) of size N are defined using the scaled orthogonal Tchebichef polynomials tp,N (), as follows[5]. Tpq = ¦ ¦ � � 1 0 1 0 ,, ),()()(),(),( 1 N x N y NqNp yxfytxtNqNp UU p, q = 0, 1, … N�1, (1) where the polynomial functions are given by [6], ¸¸¹ · ¨¨© § ¸¸¹ · ¨¨© § � ¸¸¹ · ¨¨© § � �� � ¦ � k x p kp kp kN N pxt p k kp pNp 0 , 1 )1(!)( (2) The scale factor Np is introduced in the above equation to ensure numerical stability of higher order functions. The polynomials tp,N (x), satisfy the recurrence formula [7],[8]: 0)()/1( )()12)(12()()1( ,1 22 ,,1 �� ����� � � xtNpp xtNxpxtp Np NpNp p = 1,2 … N�2; x = 0,1,… N�1. (3) with initial conditions, t0(x) = 1, t1(x) = (2x�N+1)/N , (4) The squared-norm U(p, N) is equivalent to ^ ` 12 12111 )( 2 2 2 2 21 0 2 , � ¸¸¹ · ¨¨© § �¸¸¹ · ¨¨© § �¸ ¹ ·¨ © § � ¦ � p N p NN N xt N x Np � , p =0, 1, …, N�1. (5) Radial Tchebichef Invariants for Pattern Recognition Ramakrishnan Mukundan, Senior Member, IEEE P 0-7803-9312-0 /05/$20.00 ©2005 IEEE The squared norm satisfies the following recurrence relation: U(p, N) = )12( )12()( 2 22 � �� p p N pN U(p�1 , N). (6) The most important property of the set {tm,N (x)} that is utilized in a moment definition, is its orthogonality in the discrete domain[5],[9]: pq N x NqNp Npxtxt GU ),()()( 1 0 ,, ¦ � , (7) which leads to an exact image reconstruction formula (inverse moment transform), f(x, y) = ¦ ¦ � � 1 0 1 0 ,, )()( N p N q NqNppq ytxtT . (8) III. RADIAL MOMENTS Radial moments generally use a radial-polar coordinate system (r, T) and combine a one-dimensional orthogonal function in r with a circular function in T to form moments of an image f(r, T). In this section, we first review the definition of the popular Zernike moments and then introduce radial Tchebichef moments. The primary advantage of radial moments is that rotational invariants can be easily constructed by eliminating the corresponding phase component from a moment expression. A. Zernike Moments The Zernike moments have complex kernel functions based on Zernike polynomials, and are defined as [1] Znl = ³ ³ � � S T TT S 2 0 1 0 ),()( )1( ddrrrferRn jlnl , (9) where r d 1, j = (�1)½ , and the function Rnl(r) denotes a radial Zernike polynomial of order n and repetition l. In the above equation n is a non-negative integer, and l is an integer such that n�|l| is even, and |l| d n. The radial Zernike polynomials are real-valued functions defined as Rnl(r) = ¦ � � ¸ ¹ ·¨ © § ��¸ ¹ ·¨ © § �� �� 2/|)|( 0 2 ! 2 ||2! 2 ||2! )!()1( ln s sn s lsnlsns rsn (10) The above functions are continuous and orthogonal inside the unit circle |r|<1. This requires a coordinate transformation from the image space to the region [-1,1], as well as a discrete approximation of the integrals in (9). B. Radial Tchebichef Moments We can define a set of discrete orthogonal moments in a similar fashion, by combining the one-dimensional Tchebichef polynomials in (2) with a circular function. Since we use the discrete domain of the image space for these functions (Fig. 1), we allow the parameter r to vary from 0 to N/2, and the angle T to vary from 0 to 2S in n discrete steps, such that Tk = n kS2 , k = 0, 1, 2,…, n�1. (11) Fig. 1. Domain of definition of radial Tchebichef moment functions. The radial Tchebichef moments of order p and repetition q are defined using the equation � �¦ ¦ � � � 1 0 1 0 2 , ,)(),( 1 m r n k k n qkj mppq rfertmpn S T U S (12) where m = N/2, Tk is given by (11), and n denotes the maximum number of pixels along the circumference of the circle in Fig.1. The inverse moment transform is given by the following equation: ¦ ¦ | max 0 max 1 , )(),( p p q q jq mppq ertSrf TT (13) where pmax, qmax denote the maximum order and repetition of moments used. The real-valued components of radial Tchebichef moments can be obtained from (12): ¦ ¦ � � ¸ ¹ ·¨ © § 1 0 1 0 , )( ),(2cos)( ),( 1 m r n k kmp c pq rfn qkrt mpn S TS U ¦ ¦ � � ¸ ¹ ·¨ © § 1 0 1 0 , )( ),(2sin)( ),( 1 m r n k kmp s pq rfn qkrt mpn S TS U (14) so that )()( s pq c pqpq jSSS � (15) With the above definitions, the inverse moment transform (13) can be conveniently expressed in terms of real-valued functions: f(r, T) = ¦ ¦ °¿ ° ¾ ½ °¯ ° ® ­ �� max 0 max 1 )()()( 0 )sin()cos(2)( p p q q s pq c pq c pp qSqSSrt TT (16) 0 N�1 r T N/2 m pixels n pixels IV. ROTATIONAL INVARIANTS Consider an image rotation by an angle D about the centre of the image. Assuming that the image intensity values are preserved throughout the rotation, the Zernike moments Z cnl of the transformed image are related to the moments Znl of the original image by the equation, Z cnl = e�jlD Znl , nt0. (17) Any moment expression that is independent of the parameter D is obviously a rotation invariant. The primary rotation invariants of Zernike moments are Mn = Zn0 ; Mnl = |Znl|2 , (18) where nt0, and n�|l| is even. Similarly, we can write invariants of radial Tchebichef moments in the form Kp = Sp0 = )( 0 c pS = ¦ ¦ � � 1 0 1 0 , ),()(),( 1 m r n k kmp rfrtmpn T U (19) Kpq = |Spq|2 = � � � �2)(2)( spqcpq SS � , q>0. (20) V. IMPLEMENTATION ASPECTS As the parameters r and t are varied in (14), we require the Cartesian coordinates of the image pixel at the corresponding location, in order to obtain the intensity value. The pixel position can be obtained using the equations 2 2sin )1(2 2 2cos )1(2 N n k m rNy N n k m rNx �¸ ¹ ·¨ © § � �¸ ¹ ·¨ © § � S S r = 0,1,2,…., m�1; k = 0,1,2,…., n�1. (21) Like many image transforms, the radial Tchebichef moment equations in (14) are also separable, and this property can be used to considerably reduce the computation time. Thus the moments can be computed in a two-step process as shown below. Step 1: Compute one dimensional Tchebichef moments along each radius vector, and store them in an array. Qp (k) = ¦ � 1 0 , ),()(),( 1 m r kmp rfrtmp T U (22) Step 2: Compute the real-valued circular moments of the above function: )(2cos1 1 0 )( kQ n qk n S p n k c pq ¦ � ¸ ¹ ·¨ © § S (23) )(2sin1 1 0 )( kQ n qk n S p n k s pq ¦ � ¸ ¹ ·¨ © § S (24) Using the above scheme, the total number of iterations reduces from (pmax)(qmax)mn to (pmax)(qmax+m)n. For an image of size NxN, the value of m is N/2, and n is approximately 4N. Both m and n may be set to a higher value to improve the quality of reconstruction. The values of pmax, qmax depend on the order of invariants required (usually less than 6), or the order of moments used for reconstruction (usually N/2). The pseudo-code for the computation of moment invariants is given in Fig. 2 below. 1. Input: Image f(x, y), 0 d x, y d N�1. m = N/2, n = 6N. 2. Compute Tchebichef polynomials: for(r=0; r