Microsoft Word - 12_Sona_Hakobyan_new


Mathematical Problems of Computer Science 42, 113--120, 2014. 

 

113 

 

 

 

 

Fast Slant-Hadamard Transform Algorithm 
 

Sonik R. Hakobyan 

 
Yerevan State University 

e-mail: sonahakobyan@ysu.am 

 

 

Abstract 

 
In this paper, we investigate an efficient algorithm for computation of parametric 

Slant-Hadamard transforms. We present the Slant-Hadamard matrix of order n2  as a 

product of sparse matrices, develop the appropriate fast Slant-Hadamard transform 

and its complexity. In the end we present the detailed example of factoring of Slant-

Hadamard transform matrix of order 8 and Matlab code for implementation  Slant-

Hadamard transform.  

Keywords: Slant-Hadamard transform algorithm, Sparse  matrix. 

 
 

 

 

 

 

1. Introduction 

A phenomenon characteristic of digital images is the presence of approximately constant or 

uniformly changing gray levels over a considerable distance or area. The slant transform is 

specifically defined for efficient representation of such images. It is a piecewise linear basis that 

follows the spirit of Walsh transform, possessing a discrete saw tooth-like basis vector which 

efficiently represents linear brightness variations along an image line. The slant transform has 

been used for signal compression and pattern recognition  as well as for Intel’s “indo” video 

compression algorithm [1-2]. The slant transform has the best compaction performance among 

the non-sinusoidal fast orthogonal transforms. 

Historically, Enomoto and Shibata conceived the first, eight-point slant transform in 1971 

andused it in TV image encoding. Its major innovation is given by the slant vector, which can 

properly follow the gradual changes in brightness of natural images. Pratt, Welch, and Chen have 

generalized it to any order 
n

2  and compared its performance with other transforms [2]. 

The slantlet transform has been successfully applied in compression and denoising. Currently, 

slant transforms are usually constructed via Hadamard or Haar transforms [5-7]. 

The most common fast slant transform methods [5] are based on the factorization of the slant 

transform matrix into a set of largely sparse matrices. 

 

 



Fast Slant-Hadamard Transform Algorithm 114

 

2. The Slant-Hadamard Transform 

The Slant-Hadamard transform is defined as X = Sx [8], where S - the Slant-Hadamard 

transform matrix of order N is generated recursively by the following formula: 

 

where 2
2

N
p = − , 2

n
N = , 

m
I  denotes an identity matrix of order m, and the parameters 

n
a  and

n
b  are given by 

1/ 2
2 2 1/ 2

1 12 2

3 1
                                          ,   ,                                     (2)

4 1 4 1
n n

N N
a b

N N
+ +

   −
= =   

− −     
 

and ( ) 








−
=

11

11

2

1
1S

 

is just a Hadamard matrix of order 2 [8]. 

 

Example 2.1: Below we present the Slant-Hadamard transform matrices of order 4 and 8 obtained 

from (1) and (2)

1 1 1 1 1 1 1 1

7 5 3 1 1 3 5 7
1 1 1 1 1 / 21

3 1 1 3 3 1 1 3
3 31 1 1 / 5

7 1 9 17 17 9 1 71 15 5 5 5 1 / 105(2) , (3)
1 1 1 1 1 1 1 1 1 1 1 14 8

3 31 1 1 1 1 1 1 1 1 1
1 / 5

5 5 5 5
1 3 3 1 1 3 3 1 1 / 5

1 3 3 1 1 3 3 1

S S

⋅

⋅

⋅

⋅

⋅

− − − −
 

− − − − 
− −  − − − −

 = =
− − − − − − 

 
− − − −− − 

  − − − −

− − − −

 
 

3. Construction of Parametric Slant-Hadamard Transform 

The forward and inverse parametric Slant-Hadamard transforms of order 2
n
 (n =1, 2, 3,...), are 

defined as xSX
n

2
= , XSx

T

n
2

=
 
[9-10], respectively, where x  is an input data vector and nS

2  
is 

generated recursively as 

 

 

 

 

           2

1
)( =nS  

nn
ba

01
 p

O ×2
nn

ba−

01

 

p
O ×2  

 

 

 

 

 

  









−

−
×

)1(

)1(

nSO

OnS
,                     (1)             

 

 

2×pO  pI  2×pO  pI  

nn
ab−

10

 

p
O ×2

nn
ab

10 −

 

p
O ×2

2×pO  pI  2×pO  
pI−



S. Hakobyan 115 






 ⊗=














= −

−−

−−

1
11

11

2222

1

22

22
22

1

2
nn

nn

nn

nn
SIQ

SO

OS
QS , 1>n , 

1
,

2 2 2
S H

+ + 
= =  

+ −   
 

where 
M

O
 
denotes the zero matrix of order M, “+” corresponds to 1 and “-” to -1, ⊗  denotes the Kronecker 

product, and 
n

Q
2  

is the recursion kernel matrix defined as 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

As in [9-10], we introduce the expressions for 
n

a
2  

and 
n

b
2  

to construct the parametric Slant-Hadamard 

transforms matrices of order 2
n 

                                 
n

n

n

n
a

2

22

22

2 )2(4

)2(3

β−
=

−

−

, 

n

n

n

n

n
b

2

22

2

22

2 )2(4

2

β

β

−

−
=

−

−

,                                         (3)                            

where 
22

2

22
22

−−
≤≤−

n

n

n β , 1
2

=a . 

It can be shown that for 22
2

2
−

>
n

nβ  the Slant-Hadamard transforms matrices lose their orthogonality. The 

parametric slant transform matrices fulfill the requirements of the classical slant transform matrix. 

However, the parametric slant transform matrix is a parametric matrix with parameters
n

2
84

...,,, βββ .

 

� When ,1
2

84
===== ββββ

n
L we obtain a classical slant transform 

� When 
22

2
2

−
=

n

n
β  for all 

n
2

β , 2≥n , we obtain a Walsh-Hadamard transform. 

� When ,
2

84
ββββ ====

n
L

 
for 44 ≤≤− β , we obtain a constant beta slant transform. 

� When 
n

2
84

... βββ ≠≠≠ , 22
2

22
22

−−
≤≤−

n

n

n β , ...,4,3,2=n , we refer to this case as a 

multiple betas slant transform [9-10]. In this case some of 
n

2
β

 
can be equal but not all of 

them. 

 

For n=2 and 0.4
4

−=β
 
we have the following multiple betas slant transform matrix of order 4. 

 

 

 

 

 

 
=nQ

2
 

nn ba
22

01
 p

O ×2

 
nn ba

22

01

−

 

p
O ×2

 

 

 

 

 

 

 

 

 

 

2×pO  pI  2×pO  pI  

nn ab
22

10

−
 p

O ×2

 
nn ab

22

10 −

 

p
O ×2

 

2×pO  pI  2×pO  pI  



Fast Slant-Hadamard Transform Algorithm 116

1 1 1 1

3 2 3 2 3 2 3 2

1 5 5 5 5
(2) .

1 1 1 14

3 2 3 2 3 2 3 2

5 5 5 5

S

 
 

+ − − + − −
 

=  
− −

 
 − + + −

− − 
   

 
Remark 3.1: Parametric slant transform matrices fulfill the following requirements of classical 

slant transform: 
 

� Its first row vector is of constant value.  
� Its second row vector represents the parametric slant vector.  
� Its basis vectors are orthonormal.  
� It has a fast algorithm. 
 

Remark 3.2: It is easy to verify that the parametric slant transform matrix can be represented as 

follows: 

,    2,  
4 41

,    2,2 2 2 2

M H for n

S
n C H for nn n n







=

=
>

 
 

 

where 













⊗=

−

−

1

1

2
0

0
2

22 n

n

nn C

C
MC , 

 

 

 

 

 

 

                                       (4) 

 

 

 

 

 

where 
22

1
,22 IMp

n
=−=

−
.  kmO ×  

denotes a zero matrix of size ,km ×  mI  
denotes an identity 

matrix of order m, ⊗  is the operator of Kronecker product, nH
2  

is the Walsh-Hadamard matrix 

of order 
n

2 , and the parameters na
2  

and nb
2  

are given in (3). 

 
 

 

 

 

 

 

 

                      
=nM

2
 

nb
2

0

01
 p

O ×2

 0

00

2
na

 pO ×2  

2×pO  pI  2×pO  ppO ×  

na
2

0

00
 p

O ×2

 0

10

2
nb−

 pO ×2  

2×pO  ppO ×  2×pO  pI  



S. Hakobyan 117 

4. Fast Slant-Hadamard Transform Algorithm 

The parametric Slant-Hadamard transform matrix can be represented [11-12] as 

( )( ) ,2,
2

1
11

222222
≥⊗⊗= −− nSIIHMS nnnn

n
 

where  
22

IM = ,  nM
2  

is given in (4). 

The slant transform matrix of order 2
n  

can be factored [11-12] as 

∏
=

−−
==

n

i

innn
SSSSSS n

1

1212
... , where ))(( 1

22222
−−− ⊗⊗⊗= iiniin IHIMISi . 

Below we represent in detail sparse matrices decomposition of Slant-Hadamard matrix of order 8. 

Consider the Slant-Hadamard matrix 1238
8

1
SSSS =

 
for 1

84
=== βββ . We have  

 

            

1

1 1 0 0 0 0 0 0

1 1 0 0 0 0 0 0

0 0 1 1 0 0 0 0

0 0 1 1 0 0 0 0
,  

0 0 0 0 1 1 0 0

0 0 0 0 1 1 0 0

0 0 0 0 0 0 1 1

0 0 0 0 0 0 1 1

S

−

−
=

−

−
5/1

5/1

5/1

5/1

21210000

10100000

12120000

01010000

00002121

00001010

00001212

00000101

2

⋅

⋅

⋅

⋅

−

−

−

−

−

−

=S
 

21/1

21/1

10001000

01000100

00450045

00100010

10001000

01000100

00540054

00010001

3

⋅

⋅

−

−

−

−

−

=S
 

Below the 8-point transform steps are given in detailed  ( xSSSS
1238

= , scaling coefficient 
8

1
 is omitted). 

Step 1: ,
1
xSy =

 
(the number of additions is 8). 

76

76

54

54

32

32

10

10

7

6

5

4

3

2

1

0

1

7

6

5

4

3

2

1

0

11000000

11000000

00110000

00110000

00001100

00001100

00000011

00000011

xx

xx

xx

xx

xx

xx

xx

xx

x

x

x

x

x

x

x

x

xS

y

y

y

y

y

y

y

y

y

−

+

−

+

−

+

−

+

=⋅

−

−

−

−

===
 

Step 2: ,
2
ySz =

 
(the number of additions is 12 and of multiplications is 8). 



Fast Slant-Hadamard Transform Algorithm 118

 

0 0 2

1 0 2 1 3

2 1 3

3 0 2 1 3

2

4 64

4 6 5 75

5 76

7

1/ 5

1/ 5

1/ 5

1 0 1 0 0 0 0 0

(2( ) ( ))2 1 2 1 0 0 0 0 1/ 5

0 1 0 1 0 0 0 0

( ( ) 2( ))1 2 1 2 0 0 0 0 1/ 5

0 0 0 0 1 0 1 0

(2( ) ( ))0 0 0 0 2 1 2 1 1/ 5

0 0 0 0 0 1 0 1

( (0 0 0 0 1 2 1 2 1/ 5

y y y

y y y y y

y y y

y y y y y
z S y

y yy

y y y yy

y yy

y

+

− + + ⋅− ⋅

−−

− − + + ⋅− ⋅
= = ⋅ =

+

− + + ⋅− ⋅

−−

−− ⋅
4 6 5 7

1/ 5

.

) 2( ))y y y y− + + ⋅

 

Step 3: ,
3
zSX =  (the number of additions is 10 and of multiplications is 4). 

   

0 40

0 4 1 51

2 62

3 73

3
1 54

5 0 4 1 5

6 2 6

7 3 7

4 / 21 5 / 21

/ 21 4 / 21

1 0 0 0 1 0 0 0

( ) ( )4 5 0 0 4 5 0 0 1/ 21

0 0 1 0 0 0 1 0

0 0 0 1 0 0 0 1
.

0 1 0 0 0 1 0 0

5 ( ) ( )5 4 0 0 5 4 0 0 1/ 21

0 0 1 0 0 0 1 0

0 0 0 1 0 0 0 1

z zz

z z z zz

z zz

z zz
X S z

z zz

z z z z z

z z z

z z z

+

− + +− ⋅

+

+
= = ⋅ =

−−

− − + +− ⋅

−−

−−  
The total number of additions is 30 and the total number of multiplication is 12. 

 

Now calculate the number of operations for nS
2

transform. 

1 1

1

1 1

2 2

22 2 2 2 2 2 2

2 2

( )( ) ( ) .
i i

n i i n i i n i i n i

i i

i

I
S I M I H I I M I

I I

I − −
− − − − −

− −

  
= ⊗ ⊗ ⊗ = ⊗ ⊗   −  

 

The x
II

II
I

ii

ii

in




























−
⊗

−−

−−

−
11

11

22

22
2

 

transform requires only
n

2  addition operations, and the yMI iin )(
22

⊗−

transform requires 6 2n i−⋅ operations ( 4 2
n i−

⋅  multiplications and 2 2
n i−

⋅ additions). Therefore, 

the  S
i  

requires 12 2n i n+ − +  addition and 4 2
n i−

⋅  multiplication operations.
 

So, the fast Slant-Hadamard transform of order n2  requires 22)1(2 −+=
+ n

nC n addition and 

42
1

2
−=

+× n
nC multiplication operations( 2>n ), with 84 =

+
C

 
and 4

4
=

×
C , where  

+
m

C  and 
x

m
C

 
are, 

respectively, the number of additions and multiplications required for the m – point fast 

algorithm [8]. 

 

% 1D FSHT Matlab code 

function M=M2N(n) 

if n==1 

    M=eye(2); 

else 

p=2^(n-1)-2; m=2^(2*n-2); 

a=sqrt(3*m/(4*m-1)) ; b=sqrt((m-1)/(4*m-1)); 

  



S. Hakobyan 119 

M=[[1 0 ;0 b] zeros(2,p) [0 0;a 0] zeros(2,p); 

      zeros(p,2) eye(p) zeros(p,2) zeros(p,p); 

      [0 0 ; 0 a] zeros(2,p) [0 1 ;-b 0] zeros(2,p); 

    zeros(p,2) zeros(p,p) zeros(p,2) eye(p)]; 

end 

end 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

function Y=FSHT(n,x) 

Y=x; 

for  i=1:n 

    Y=kron(eye(2^(n-i)),M2N(i))* kron(eye(2^(n-i)),kron(hadamard(2),eye(2^(i-1))))*Y; 

end 

end 
 

The 2D Slant-Hadamard transform can be defined as SHT(f) = SH  * f * HS ′ , where f is the image and  
HSandSH ′ are Slant-Hadamard matrix and its transpose [9].   

 

 

 

 

5. Cunclusion 

In this paper, an efficient algorithm for computation of parametric Slant-Hadamard transforms is 

investigated. The Slant-Hadamard matrix of order 
n

2  is presented as a product of sparse matrices and the 

appropriate fast Slant-Hadamard transform and its complexity are developed. In the end the detailed 

example of factoring of Slant-Hadamard transform matrix of order 8 and Matlab code for implementation  

Slant-Hadamard transform  on 1D case are presented.  Later the Slant-Hadamard transformation will be 

discussed which will be used in image processing. 

 

 

References 
 

[1] A. K. Jain, Fundamentals of Digital Image Processing. Prentice Hall Inc, Englewood Cliffs, NJ 
1989.  

[2] M. M. Anguh and R. R. Martin, “A truncation method for computing slant transforms with 
applications to image processing”, IEEE Transactions on  Communications, vol. 43, no. 6, pp. 2103-

2110, 1995.  

[3] I. W. Selesnick, “The slantlet transform”, IEEE Transactions on Signal Processing, vol. 47, no. 5, 
pp. 1304-1313, 1999. 

[4] N. Ahmed and K. R. Rao, Orthogonal Transforms for Digital Signal Processing, New York, 
Springer-Verlag, 1975. 

[5] J. F. Yang and C. P. Fang, “Centralized fast slant transform algorithms”, IEICE Transactions on 
Fundamentals of  Electronics,Communications and Computer Sciences, vol. E80A, no. 4, pp. 705-

711, 1997. 

[6] H. Sarukhanyan, S. Agaian, K. Egiazarian and J. Astola, “Reversible Hadamard Transforms”, Facta 
Universities (Nis), Series: Electronics and Energetics, vol. 20, no. 3, pp. 309-330, 2007. 

[7] S. Agaian, H. Sarukhanyan, K. Egiazarian and J. Astola, Hadamard Transforms, SPIE press, 
Bellingham, Washington, USA, 2011. 

[8] S. Agaian, K. Tourshan and J. P. Noonan, “Parametric Slant-Hadamard transforms with 
applications”, IEEE Signal Processing Letters, vol. 9, no. 11, pp. 375-377, 2002. 



Fast Slant-Hadamard Transform Algorithm 120

[9] S. Agaian, K. Tourshan and J. P. Noonan, “Parametric Slant-Hadamard transforms”, 
IS&T/SPIE’s 15

th
 Annual Symposium Electronic Imaging Science and Technology, Image 

processing: Algorithms and Systems II, pp. 20-24 , Santan Clara, California, 2003.  

[10] H. Sarukhanyan, “Hadamard matrices: construction methods and applications”, In Proc. 
of   The Workshop on Transforms and Filter Banks, 35p., Tampere, Finland, 1998.  

[11] H. Sarukhanyan, A. Anoyan, S. Agaian, K. Egiazarian and J. Astola, “Fast Hadamard 
transforms”, Proc. of International TICSP Workshop on Spectral Methods and Multirate 

Signal Processing, SMMSP'2001, Pula, Croatia, pp. 33-40, 2001. 

[12] S. Agaian, H .Sarukhanyan and K. Tourshan, “New classes of sequential slant hadamard 
Transform”, Proc. Of International TICSP Workshop on Spectral Methods and Multirate 

Signal Processing, SMMSP’02, Toulouse, France,  4p.,  2002. 

[13] S. Minasyan, D. Guevorkian, S. Agaian and H. Sarukhanyan, ”On “Slant-Like” fast 
orthogonal transforms of arbitrary order”, VIPromCom-2002, 4th EURASIP – IEEE 

Region 8 International Symposium on Video/Image Processing and Multimedia 

Communications, Zadar, Croatia, p. 6, 2002.  

 

 

Submitted 02.08.2014, accepted 28.11.2014. 
 

 

Սլանթ-Հադամարի ձևափոխության արագ ալգորիթմ 
 

Ս. Հակոբյան 
 

Ամփոփում 
 

Ուսումնասիրվում է պարամետրով Սլանթ–Հադամարի ձևափոխության 

արդյունավետ ալգորիթմը: 
n

2  կարգի Սլանթ-Հադամարի մատրիցը ներկայացվում է 

նոսր մատրիցների արտադրյալի տեսքով, ինչպես նաև մշակվում են Սլանթ-

Հադամարի արագ ձևափոխությունն ու նրա բարդությունը: Վերջում մանրամասն 

ներկայացվում են 8-րդ կարգի Սլանթ-Հադամարի ձևափոխության մատրիցի 

ֆակտորիզացիան և Սլանթ-Հադամարի ձևափոխությունը իրականացնող Matlab 

կոդը: 
 

 

 

Алгоритм быстрого преобразования Сланта-Адамара 
 

С. Акопян 

 

Аннотация 

 
В данной работе мы исследуем эффективный алгоритм параметрического преобразования 

Сланта-Адамара. Матрица Сланта-Адамара порядка n2  представлена в виде произведения 

разреженных матриц. Разработаны соответствующее быстрое преобразование Сланта-

Адамара и его сложность. Представлены подробный пример факторизации матрицы 

преобразования и Matlab код для реализации  преобразования Сланта-Адамара .