Lossless Compression Scheme for Regular Images using Number Theoretic Transform

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Salila Hegde, Rohini Nagapadma

Salila Hegde and Rohini Nagapadma. Lossless Compression Scheme for Regular Images using Number Theoretic Transform. International Journal of Computer Applications 158(9):7-12, January 2017. BibTeX

	author = {Salila Hegde and Rohini Nagapadma},
	title = {Lossless Compression Scheme for Regular Images using Number Theoretic Transform},
	journal = {International Journal of Computer Applications},
	issue_date = {January 2017},
	volume = {158},
	number = {9},
	month = {Jan},
	year = {2017},
	issn = {0975-8887},
	pages = {7-12},
	numpages = {6},
	url = {http://www.ijcaonline.org/archives/volume158/number9/26934-2017912856},
	doi = {10.5120/ijca2017912856},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}


In this paper properties of number theoretic transforms are investigated and it is found that they can be used to compress the regular image effectively. NTT variants namely Fermat and Mersenne transforms are applied on test images of size 16x16 and the results are analyzed and a compression scheme is developed. The algorithm is implemented in MATLAB and results are analyzed and compared with DCT in terms of total number of zero coefficients and total number of pixels in error when inverse transform is applied. The study shows that the transform is error free and can compress regular data effectively. Further investigations on these transforms are to be carried out and algorithms need to be developed to compress other images as well in order to achieve lossless compression.


  1. B.Gold and C.M.Rader, 1969, Digital Processing of Signals.McGraw-Hill.
  2. R. Blahut, 1985,Fast algorithms for digital signal processing. Addison-Wesley Publishing Company.
  3. POLLARD, J.M,1971, 'The fast Fourier transform in a finite field', Math.Comput., 25, pp. 365-374.
  4. J. M. Pollard,1976, "Implementation of number-theoretic transforms,"Electron. Lett., pp. 378-379.
  5. AGARWAL, R.C, and COOLEY, J.W.,1977, 'New algorithms for digital convolution', IEEE Trans., ASSP-25, pp. 106-124
  6. R. C. Agarwal and C. S. Burrus, 1975, "Number theoretic transforms to implement fast digital convolution," Proc. ZEEE. vol. 63, PU.550.-560.
  7. E. Vegh and L. M. Leibowitz, 1975, "Fast complex convolution using number theoretic transforms," Naval Res. Lab., Washington, DC, NRL Rep. 7935.
  8. . S. Gudvangen, Hgskulen i Buskerud, AUI, EMR, Kongsberg, Norway , Practical applications of number theoretic transforms
  9. NUSSBAUMER, H.J.,1981,'New polynomial transform algorithms for multidimensional DFTs and convolutions', IEEE Trans., ASSP-29, pp. 74-83
  10. REED, I.S., and TRUONG, T.K.,1979,'A new hybrid algorithm for computinga fast discrete Fourier transform', IEEE Trans., C-28,pp. 487-492
  11. D.burton,1980,’Elementory number theory’.
  12. P. J. Nicholson, 1971, "Algebraic theory of finite Fourier transforms," J. Comput. Syst. Sci., vol. 5, pp. 524-547..
  13. AGARWALL, R.C, and BURRUS, C.S.,1974, 'Fast convolution usingFermat number transform with application to digital filtering', ibid., ASSP-22, pp. 87-97
  14. Tuukka Toivonen,Janne Heikkila.,2006, Video filtering with fermat number theoretic transforms using residue number system. IEEE transactions on circuits and systems for video technology.vol16,No1,
  15. Richard Conway, 2006,Modified Overlap Technique Using Fermat and Mersenne Transforms.. IEEE Transactions on circuits and systems-II: Express Briefs, VOL. 53, NO. 8.
  16. RADER, CM.,1972, 'Discrete convolution via Mersenne transform', IEEETrans., C-21, pp. 1269-1273
  17. S.Boussakta, A.Y.Md.Shakaff, F.Marir, A.G.J.Holt. 1988, Number Theoretic Transforms of Periodic Structures and their Applications.IEE Proceedings,Vol.135.Pt.G.No 2


Compression, NTT, Fermat, Mersenne, DCT, Rings, Fields.