I have seen many persons asking DCT softwares in the Newsgroups:
comp.compression,comp.compression.research,news.answers,comp.answers.
I would like to inform you that I have implementations of the 2-D Fast
Cosine Transfroms (FCTs) of the following algorithms:
Row-Column approach:
---------------------
1) File "2dthough1daz.c" based on the 1-D algorithm of:
F. Arguello and E.L. Zapata, "Fast cosine transform based on the
succesive doubling method", Electronics Letters, Vol. 26, No. 19,
pp.1616-1618, Sept. 1990.
2) File "2dthough1dchan.c" based on the 1-D algorithm of:
S. C. Chan and K. L. Ho, "A new two-dimensional fast cosine transform
algorithm", IEEE Trans. on Signal Processing, Vol. 39, No. 2, pp. 481-485,
Feb. 1991.
3)File "2dthough1dhou.c" based on the 1-D algorithm of:
H.S. Hou, "A fast recursive algorithm for computing the discrete cosine
transform", IEEE Trans. on Accoustics, Speech and Signal Processing, Vol. 35,
No. 10, pp. 1455-1461, Oct. 1987.
4) File "2dthroughsrdif.c" based on the 1-D algorithm of:
C.A. Christopoulos and A. N. Skodras, "On the computation of the fast cosine
transform", Proceedings of the European Conference on Circuit Theory and Design
(ECCTD'93), Davos, Switzerland, pp. 1037-1042, Aug.30-Sept. 3, 1993.
5) Files "2dthrough1ddit.c" and "2dpruntriang1d.c"based on the 1-D algorithm of:
A.N. Skodras, "Fast discrete cosine transform pruning", IEEE Trans. on
Signal Processing. Accepted for pulication (I think it will appear on
June or July 1994).
Direct 2D-FCT
--------------
6) Files "VECTOR_RADIX_FCT.c" and "VR_rectangular_pruning.c" based on paper:
C.A. Christopoulos, J. Bormans, A.N. Skodras and J. Cornelis, "Efficient
computation of the two-dimensional fast cosine transform", SPIE Hybrid Image
and Signal Processing IV, 5-8 April 1994, Orlando, Florida, USA. Accepted.
7) File "VR_recursive_pruning.c" based on paper:
C.A. Christopoulos and A.N. Skodras, "Pruning the two-dimensional fast cosine
transform", To be presented at the VII European Signal Processing Conference ,
September 13-16, 1994, Edinburgh, Scotland.
A comparison of (almost) all the above papers can be found in:
8) C.A. Christopoulos, A.N. Skodras and J. Cornelis, "Comparative performance
evaluation of algorithms for fast computation of the two-dimensional DCT",
IEEE Benelux and ProRISC Workshop on Circuits, Systems and Signal Processing,
Papendal, Arnhen (The Netherlands), March 23-24, 1994. Accepted.
In paper 4, the split-radix FCT algorithm is presented in both an in-place
and a non-in-place version and they are compared with the algorithms of papers
1,2,3 in the points of memory requirements, compuational complexity, data
transfers and execution times in various Unix platforms.
In paper 5, a pruning algorithm is implemented (in file 2dpruntriang1d.c), which allows
the computation
of the No out of the N points (where N is power of 2 and No is can be any
number). This 1-D algorithm can be used for the computation of only a part of
the 2D coefficients in the zig-zag form. In file "2dthrough1ddit.c" no pruning is implemented but only the computation of the 2-D FCT through the 1-D DIS.
In paper 6 and in file "VR_rectangular_pruning.c" an in-place direct 2D FCT is given, which also allows the fast
computation of the N0xN0 out of the NxN points (where both N and No are powers
of 2), i.e. it has a limited pruning property. In file "VECTOR_RADIX_FCT.c" no pruning is
implemented and all NxN points are calculated.
In paper 7, a recursive pruning algorithms in implemented which allow the computation
of DCT points in the zig-zag order based on the 2D vector-radix FCT (not in the row-column method).
All these programs and papers can be given to anyone who want them. They can be
used for any input array (8x8,16x16,...1024x1024,..) so are also good
for full-frame image compression, as in many medical compression methods
or robot vision applications.
Especially the pruning algorithms that have been implemented are very useful in the
image compression field, since we know that only a certain number of the DCT coefficients
are required for a good reconstruction. In many applications also, only a limited
number of coefficients are used as in zonal coding, etc.
Unfortunately, the inverse 2D FCT is not implemented in any of the above programs.
However, it is very easy to implement the inverse, just reverse the flow-graph and
you got it!!
It has to be noted that the vector radix FCT presented in papers (6) and (7) is more
efficients than the row-columns approaches for the computation of the 2-D FCT, because
VR FCT require 25% less multiplications than the row-column methods (the additions are
the same). In addition less memory accesses and data transfers are required from the
VR FCT. For more details see paper (8) which is a comparison of various methods. The above are valid for the pruning algorithms also. Triangular pruning (paper 7) (in the
zig-zag order) is faster than row-column pruning using the method of 5, which is row-column pruning.
Persons interested in the above papers can send me an e-mail and I will send a copy to them.
I will try to put the papers in this public account but it will probably take some time,
so it is faster to send me e-mail. I would very much apperciate if people use these programs and find some bugs to inform me. It is also fair that if somebody uses the programs or papers to give a reverence to the corresponding paper and send me a copy of the paper, technical report, etc that will write.
Please do not hesitate to ask more details from me.
I hope that this will provide help to everybody that needs a fast 2D DCT program. I would also appreciate if people inform me for any bug that they found in the programs, although
I have tested all of them.
Charilaos Christopoulos
Vrije Universiteit Brussel
VUB - dept. ETRO-IRIS
Pleinlaan 2
1050 Brussels
Belgium
Tel: ++32 2 6412940
Fax: ++32 2 6412883
E-mail: chchrist@etro.vub.ac.be