THE 3D DCT (Discrete Cosine Transform):

A GENERALIZATION OF THE 2D DCT

 

par:

Michel J. DUMONTIER

Patrick GERLIER : Ingnieur EP

Dr Pascal LERAY Image Processing & Computer Graphics Expert

FRANCE TELECOM/CNET/DIH

 

Introduction:

The standard, classic, and well known 2D DCT is largely used in the MPEG or JPEG world, for very efficient image compression.

But the spatio-temporal 3D DCT (2 Dimensions plus time) has not yet been tested.
The present paper is dedicated to an APL implementation of the 3D DCT, defined as a generalization of the 2D DCT.

 

DESCRIPTION:
In this case, instead of 8*8 image blocs, we choose 8*8*8 spatio-temporal blocs.

A direct 3D DCT transforms the input bloc in the Fourier space.

A rounded vector B is obtained from this result.

 

An inverse 3D DCT decompression is obtained by the reverse process.

The result bloc is compared with the original bloc V13D.

The detailed implementation is shown here:

 

 

APL implementation:

 

The 3D DCT transform function:

VTDCT3D V

IO1

N3 1 2

VT0.015625MCOS+.N(MCOS+.N(MCOS+.NV))

 

The reverse 3D DCT transform function:

VTIDCT3D V

IO1

N3 1 2

VT(MCOS)+.N((MCOS)+.N((MCOS)+.NV))

 

 

 

Initialization function: COEFFCOS:

 

COEFFCOS

IO0

FAC1

PI3.141593653589

AFACcos(PI4)

BFACcos(PI16)

CFACcos(3PI16)

DFACcos(5PI16)

EFACcos(7PI16)

FFACcos(PI8)

GFACcos(3PI8)

(PI16).8

MCOS8 80

MCOS[0;]8 1A,A,A,A,A,A,A,A

MCOS[1;]8 1B,C,D,E,(-E),(-D),(-C),(-B)

MCOS[2;]8 1F,G,(-G),(-F),(-F),(-G),G,F

MCOS[3;]8 1C,(-E),(-B),(-D),D,B,E,(-C)

MCOS[4;]8 1A,(-A),(-A),A,A,(-A),(-A),A

MCOS[5;]8 1D,(-B),E,C,(-C),(-E),B,(-D)

MCOS[6;]8 1G,(-F),F,(-G),(-G),F,(-F),G

MCOS[7;]8 1E,(-D),C,(-B),B,(-C),D,(-E)

 

 

GLOBAL TEST FUNCTION: TST3D

On 8*8*8 Spatio-temporal blocs:

 

ZTST3D

IO1

COEFFCOS

ADCT3D V13D

B0.01טA100

ZIDCT3D B

Z'F6.1'FMT Z[1;;]

 

The cosine function COS:

zcos v

z2v

 

V13D is a 8*8*8 spatio-temporal bloc

V13D is loaded with a IOTA N coefficient

 

The result shows that the reconstructed V13D value is equivalent to the initial value.

V13D: 8 times this bloc:

 

 

1 2 3 4 5 6 7 8

9 10 11 12 13 14 15 16

17 18 19 20 21 22 23 24

25 26 27 28 29 30 31 32

33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48

49 50 51 52 53 54 55 56

57 58 59 60 61 62 63 64

The transformed matrix: B: (B is rounded from A)

 

91.92 6.45 0 0.68 0 0.21 0 0.06

51.54 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

5.39 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

1.61 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0.41 0 0 0 0 0 0 0

 

0.01 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

 

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

 

Conclusion:

 

Only 9 coefficients are different from 0.

All the energy is concentrated on the first coefficients.

(As for the classic 2D DCT transform)

But in the 3D case, the compression ratio is much more efficient:

 

Compression ratio possible evaluation:

2 coefficients using: 16bits

1 coefficients using: 10bits

5 coefficients using 8 bits

 

Total: 34 bits (< 9 octets, for 8*8*8 = 512 coefficients of 16 bits)

For this example, the compression ratio is:

1024/9 = 113

 

FURTHER RESEARCHES:

 

Several other examples could be tested, mainly for real images:

One could transform an animated spatio-temporal sequence, and test with the 3D DCT transform.

Test sequences could be choosen among images with low or high frequencies.

(classic DCT beeing more efficient for low frequencies)

But adaptive quantizing could be used, with, for ewample, neural nets in order to optimized the quantizing process.

 

GENERAL CONCLUSION:

 

This first result seem very promising.

Further implementations and links with real image sequences must be done and tested now.

 

But at present, APL implementation demonstrates a very efficient coding compacity, able to solve very complex algorithms in a very short time, without the complex requirements of C or C++.