DOI: https://doi.org/10.15588/1607-3274-2019-2-16

EFFICIENT COMPUTATION OF THE INTEGER DCT-II FOR COMPRESSING IMAGES

I. O. Prots’ko, R. D. Kuzminskij, V. M. Teslyuk

Abstract


Actuality. Ensuring the efficiency and versatility of modern media for processing visual information requires the development of
various methods for the effective implementation of the discrete cosine transform. In accordance with the requirements of modern
video standards, providing high-definition compressed visual information is achieved on the basis of adaptively block-dimensional
transforms, which requires efficient computational schemes for the implementation of discrete cosine transform of variable dimensions.
The purpose of the work is to create a generalized structural scheme for the efficient computation of an integer discrete cosine
transform on the basis of cyclic convolutions of dimensions equal to the integer power of two, which provides low computational
complexity and the possibility of using visual information compression systems on the basis of adaptively block-dimensional transforms.
Method. The use of hashing arrays for efficient synthesis of algorithms and structure schemes for computing an integer discrete
cosine transform on the basis of cyclic convolutions is proposed.
Results. The result of the study is the development of a generalized structural scheme for the implementation of an integer discrete
cosine transform of dimensions equal to the integer power of the two for the compression of visual information on the basis of
adaptively block-dimensional transforms.
Conclusions. In the study, we apply the approach of bringing the basis of an integral discrete cosine transform to a set of left cyclic
submatrices, which allows us to calculate transforms based on cyclic convolutions. The basic idea of using an appropriate
mathematical apparatus is to use hashing arrays containing a brief description of the block-cyclic structure of the transform basis. On
the basis of the received set of cyclic submatrices of the transform core, a generalized structural scheme for the effective implementation
of an integer discrete cosine transform of small dimensions equal to an integer power of the two is developed. The computation
of the corresponding set of cyclic convolutions and the combining of their results by the structural scheme ensures the implementation
of adaptively block-dimensional transforms for compression of visual information.

Keywords


integer discrete cosine transformation, cyclic convolution, hashing array, image compression, adaptive blockdimensional transform.

References


Digital Technologies in Agriculture: adoption, value added and overview [Electronic resource]. Access mode: https://medium.com/remote-sensing-in-agriculture/digitaltechnologies-in-agriculture-adoption-value-added-andoverview-d35a 1564ff67

Jayant N. S., Noll P. Digital Coding of Waveforms: Principles and Applications to Speech and Video. Englewood Cliffs, NJ: Prentice-Hall, 1984, 216 p.

Video coding standards, AVS China, H.264/MPEG-4 PART 10, HEVC, VP6, DIRAC and VC-1 [Electronic resource]. Access mode: https://www.springer.com/in/book/9789400767416

H.265: High efficiency video coding. ITU 1 [Electronic resource]. Access mode: https://www.itu.int/rec/T-REC-H.265

Reznik Y. A., Chivukula R. K. Design of fast transforms for high-resolution image and video coding, Applications of Digital Image Processing. San Diego, California, SPIE 7443 Optical Engineering and Applications, 2009, pp. 1–18. DOI:10.1117/12.847190

Prots’ko I. Algorithm of Efficient Computation of DCT I–IV Using Cyclic Convolutions, International Journal of Circuits, Systems and Signal Processing, 2013, Vol. 7, Issue 1, pp. 1–9.

Pei S.-C., Ding J.-J. The integer transforms analogous to discrete trigonometric transforms / S.-C. Pei, // IEEE Transactions on Signal Processing, 2000, Vol. 48, Issue 12, pp. 3345–3364. DOI: 10.1109/78.886998

Zeng Y., Cheng L., Bi G., Kot A. C. Integer DCTs and fast algorithms, IEEE Transactions on Signal Processing, 2001, Vol. 49, pp. 2774–2782. DOI: 10.1109/78.960425

[Hong Y.M., Kim Il-K., Lee T., Cheon M.-S., Alshina E., Han W.-J., Park J.-H. New fast DCT algorithms based on Loeffler’s factorization, Applications of Digital Image Processing XXXV. San Diego, Proceedings Volume 8499, 2012. https://doi.org/10.1117/12.970324

Hnativ L.O. Integer cosine transforms for high-efficiency image and video coding, Cybernetics and Systems Analysis, 2016, Vol. 52, No. 5, pp. 802–816. DOI: 10.1007/s10559-016-9881-7

Joshi R., Reznik Y., Sole J., Karczewicz M. Recursive factorization for 16 and 32-point transforms using 4 and 8-point HM 3.0 core transforms, MPEG/JCT-VC input documentm21026, 97th MPEG meeting. Torino, 2011, pp. 244–252.

Prots’ko I., Rikmas R., Teslyuk V. The efficient computation of integer DCT based on cyclic convolutions, Computer Sciences and Information Technologies (CSIT’2018). Lviv, Proceeding of the International Scientific and Technical Conference, 2018, pp. 245–248.

Siu W.-C. eds.: Lim Y. C., Kwan H. K., Siu W.-C. Transform Domain Processing for Recent Signal and Video Applications, Trends in Digital Signal Processing. Taylor & Francis Group, LLC, 2016, pp. 201–261.

Blahut R. E. Fast algorithms for signal processing. Cambridge, University Press, 2010, 469 p. https://doi.org/10.1017/CBO9780511760921.001

Cheng C., Parhi K. K. Hardware Efficient Fast DCT Based on Novel Cyclic Convolution Structures, IEEE Transactions on signal processing, 2006, Vol. 54, No. 11, pp. 4419–4434. DOI: 10.1109/TSP.2006.881269

Meher P. K. Systolic designs for DCT using a lowcomplexity concurrent convolutional formulation, IEEE Transactions on Circuits & Systems for Video Technology, 2006, Vol. 16, No. 9, pp. 1041–1050. DOI: 10.1109/TCSVT.2006.880191


GOST Style Citations


1. Digital Technologies in Agriculture: adoption, value added and overview [Electronic resource]. – Access mode: https://medium.com/remote-sensing-in-agriculture/digital-technologies-in-agriculture-adoption-value-added-and-overview-d35a1564ff67
2. Jayant N. S. Digital Coding of Waveforms: Principles and Applications to Speech and Video / N. S. Jayant, P. Noll. – Englewood Cliffs, NJ : Prentice-Hall, 1984. – 216 p.
3. Video coding standards – AVS China, H.264/MPEG-4 PART 10, HEVC, VP6, DIRAC and VC-1 [Electronic resource]. – Access mode: https://www.springer.com/in/book /9789400767416
4. H.265: High efficiency video coding – ITU 1 [Electronic resource]. – Access mode: https://www.itu.int/rec/T-REC-H.265
5. Reznik Y. A. Design of fast transforms for high-resolution image and video coding / Y. A. Reznik, R. K. Chivukula // Applications of Digital Image Processing – San Diego, California: SPIE 7443 Optical Engineering and Applications, 2009. – P. 1–18. DOI: 10.1117/12.847190
6. Prots’ko I. Algorithm of Efficient Computation of DCT I–IV Using Cyclic Convolutions / I. Prots’ko // International Journal of Circuits, Systems and Signal Processing. – 2013. – Vol. 7, Issue 1. – P. 1–9.
7. Pei S.-C. The integer transforms analogous to discrete trigonometric transforms / S.-C. Pei, J.-J. Ding // IEEE Transactions on Signal Processing. – 2000. – Vol. 48, Issue 12. – P. 3345–3364. DOI: 10.1109/78.886998
8. Integer DCTs and fast algorithms / [Y. Zeng, L. Cheng, G. Bi, A. C. Kot] // IEEE Transactions on Signal Processing. – 2001. – Vol. 49. – P. 2774–2782. DOI: 10.1109/78.960425
9. New fast DCT algorithms based on Loeffler’s factorization / [Y. M. Hong, Il-K. Kim, T. Lee et al. ] // Samsung Electronics Co., Ltd. (Korea, Republic of) Woo-Jin Han Gachon Univ. (Korea, Republic of) Jeong-Hoon Park Samsung Electronics Co., Ltd. (Korea, Republic of) Applications of Digital Image Processing XXXV. – San Diego, Proceedings Volume 8499, 2012. https://doi.org/10.1117/12.970324
10. Hnativ L. O. Integer cosine transforms for high-efficiency image and video coding / L. O. Hnativ // Cybernetics and Systems Analysis. – 2016. – Vol. 52, No. 5. – P. 802–816. DOI:10.1007/s10559-016-9881-7
11. Recursive factorization for 16 and 32-point transforms using 4 and 8-point HM 3.0 core transforms / [R. Joshi, Y. Reznik, J. Sole, M. Karczewicz] // MPEG/JCT-VC input documentm21026, 97th MPEG meeting. – Torino, 2011. – P. 244–252.
12. Prots’ko I. The efficient computation of integer DCT based on cyclic convolutions / I. Prots’ko, R. Rikmas, V. Teslyuk // Computer Sciences and Information Technologies (CSIT’2018). – Lviv : Proceeding of the International Scientific and Technical Conference, 2018. – P. 245–248.
13. Siu W.-C. Transform Domain Processing for Recent Signal and Video Applications / W.-C. Siu // Trends in Digital Signal Processing
/ eds.: Y. C. Lim, H. K. Kwan, W.-C. Siu. – Taylor & Francis Group, LLC. 2016. – P. 201–261.
14. Blahut R. E. Fast algorithms for signal processing / R. E. Blahut. – Cambridge : University Press, 2010. – 469 p. https://doi.org/10.1017/CBO9780511760921.001
15. Cheng C. Hardware Efficient Fast DCT Based on Novel Cyclic Convolution Structures / C. Cheng, K. K. Parhi // IEEE Transactions
on signal processing. – 2006. – Vol. 54, No. 11. – P. 4419–4434. DOI: 10.1109/TSP.2006.881269
16. Meher P. K. Systolic designs for DCT using a low-complexity concurrent convolutional formulation / P. K. Meher // IEEE Transactions on Circuits & Systems for Video Technology. – 2006. – Vol. 16, No. 9. – P. 1041–1050. DOI: 10.1109/TCSVT.2006.880191






Copyright (c) 2019 I. O. Prots’ko, R. D. Kuzminskij, V. M. Teslyuk

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.