C&SA | Contents

Volume 61 >>> № 2 MARCH — APRIL 2025

-->

UDC 519.6, 004.932, 004.627

L.O. Hnativ¹

¹ V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

FAST INTEGER SINE AND COSINE TRANSFORMS TYPE IV
LOWCOMPLEXITY FOR VIDEO CODING

Abstract. Matrix methods for constructing integer sine and cosine transforms of type IV (IST-IV/ICT-IV) of order-8 and -16 are proposed, on the basis of which two integer transforms of type IV are constructed and fast algorithms for their calculation that require only operations with integers are developed. Algorithms for calculating IST-IV/ICT-IV of order-16 require 14.29% and 12.5% fewer multiplication operations and 22.11% and 20.83% more addition operations compared to known algorithms for discrete sine and cosine transformations type IV. The proposed fast IST-IV/ICT-IV compared to known fast discrete sine type VII and cosine type VIII transforms with integer approximation from the VVC standard (DST-VII/DCT-VIII) have 3.02 times less multiplicative complexity and require 47.41% fewer addition operations. Fast algorithms of low computational complexity for computing 2D separable integer cosine type II and sine type IV adaptive transforms for intra-prediction with 16x16 image blocks have been developed, which have 2.66 times lower multiplicative complexity and require 28.9% fewer addition operations compared to known separable transforms ICT-II (H.265)/DST-VII (VVC).

Keywords: discrete cosine tranform, discrete sine transform, integer cosine transform, integer sine transform, factorization, video coding, H.265, VVC (Versatile Video Coding), separable adaptive transform, MTS (Multiple Ttransform Selection).

full text

REFERENCES

1. Jain A.K. A sinusoidal family of unitary transforms. IEEE Trans. Pat. Anal. and Mach. Intel. 1979. Vol. 1, N 4. P. 356–365. https://doi.org/10.1109/ .

2. Wang Z., Hunt B.R. The discrete W transform. Appl. Math. and Comput. 1986. Vol. 16, N 1. P. 19–48. https://doi.org/10.1016/ .

3. Wang Z. Fast algorithms for the discrete W transform and for the discrete Fourier transform. IEEE Trans. Acoust., Speech, Signal Process. 1984. Vol. 32, N 8. P. 803–816. https://doi.org/10.1109/ .

4. Yip P., Rao K.R. Fast decimation-in-time algorithms for a family of discrete sine and cosine transforms. Circuits Systems and Signal Processes. 1984. Vol. 3, Iss. 4. P. 387–408. https://doi.org/10.1007/ .

5. Britanak V., Rao K.R., Yip P. Discrete cosine and sine transforms: General properties, fast algorithms and integer approximations. Oxford, UK: Academic Press; Elsevier, 2007. https://doi.org/10.1016/ .

6. Chivukula R.K., Reznik Y.A. Fast computing of discrete cosine and sine transforms of types VI and VII. Proc. SPIE 8135. Appl. of Digital Image Processing. XXX IV, 813505, Sept. 2011. https://doi.org/10.1117/ .

7. Clarke R.J. Transform coding of images. London: Academic Press, 1985. 429 p. https://doi.org/10.1016/ .

8. Kekre H.B., Solanki J.K. Comparative performance of various trigonometric unitary transforms for transform image coding. Int. J. Electronics. 1978. Vol. 44, N 3. P. 305–315. https://doi.org/10.1080/ .

9. Clarke R.J. Application at sine transform image coding. Electron. Lett. 1983. Vol. 19, N 13. P. 490–491. https://doi.org/10.1049/ .

10. Solomon D. Data compression: The complete reference. New York: Springer, 2004. 920 р. https://doi.org/10.1007/ .

11. Gonzalez R.C., Woods R.E. Digital image processing. 2nd ed. Indiana, USA: Prentice-Hall, 2002. 793 p. https://doi.org/10.1007/ .

12. Jain A.K. Image data compression: A review. Proceedings of the IEEE. 1981. Vol. 69, Iss 3. P. 349–389. https://doi.org/10.1109/ .

13. Han J., Saxena A., Rose K. Towards jointly optimal spatial prediction and adaptive transform in video/image coding. Proc. IEEE Int. Conf. Acoust., Speech, Signal Process (ICASSP). 2010. P. 726–729. https://doi.org/10.1109/ .

14. Clarke R.J. Relation between the Karhunen–Loeve and cosine transforms. IEE Proceedings F (Communications, Radar and Signal Processing). 1981. Vol. 128, N 6. P. 359–360. https://doi.org/10.1049/ .

15. Clarke R.J. Relation between the Karhunen–Loeve and sine transforms. Electron. Lett. 1984 Vol. 20, N 1. P. 12–13. https://doi.org10.1049/ .

16. Saxena A., Fernandes F.C. DCT/DST-based transform coding for intra prediction in image/video coding. IEEE Trans. Image Process. 2013. Vol. 22, N 10. P. 3974–3981. https://doi.org/10.1109/ .

17. Ye Y., Karczewicz M. Improved intra coding. ITU-T SG16Q6. Doc. VCEG-AG11, Shenzhen, China, 2007.

18. ITU-T Rec. H.265|ISO/IEC 23008-2: 2013. Information technology — High efficiency coding and media delivery in heterogeneous environments — Part 2: High efficiency Video Coding, 2013.

19. Yeo C., Tan Y.H., Li Z., Rahardia S. Mode-dependent fast separable KLT for block-based intra coding. Doc. JCTVC-B024, Geneva, CH, July 2010.

20. An J., Zhao X., Guo X., Lei S. Non-CE 7: Boundary-dependent transform for inter-predicted residue. ITU-T, Doc. JCTVC-G281, Geneva, CH., Nov. 2011.

21. Saxena A., Fernandes F.C., Reznik Y.A. Fast transforms for intra-prediction-based image and video coding. Proc. 2013 Data Compression Conf. 2013. P. 13–22. https://doi.org/10.1109/ DCC.2013.9 .

22. Reznik Y.A. Relationship between DCT-II, DCT-VI and DST-VII transforms. Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Process. (ICASSP). 2013. P. 5642–5646. https://doi.org/10.1109//ICASSP.2013.6638744.

23. M. Masera, M. Martina, G. Masera. Odd type DCT/DST for video coding: Relationships and low-complexity implementations. IEEE Int. Workshop on Signal Processing Systems. Lorient (FR). 2017. Р. 1–6. https://doi.org/10.1109/ SiPS.2017.8110009.

24. Hnativ L.O., Luts V.K. Integer modified sine-cosine transforms type VII. A construction method and separable directional adaptive transforms for intra prediction with chroma blocks in image/video coding. Cybernetics and Systems Analysis. 2021. Vol. 57, N 1. Р. 155–164. https://doi.org/10.1007/ .

25. Hnativ L.O. Discrete cosine-sine type VII transform and fast integer transforms for intra prediction of images and video coding. Cybernetics and Systems Analysis. 2021. Vol. 57, N 5. P. 827–835. https://doi.org/10.1007/s10559-021-00408-z .

26. Zhang Z. et al. Fast DST-VII/DCT-VIII with dual implementation support for versatile video coding. IEEE Transactions on Circuits and Systems for Video Technology. 2021. Vol. 31, N 1. P. 355–371. https://doi.org/10.1109/TCSVT.2020.2977118 .

27. Bross B., Wang Y.-K., Ye Y., Liu S., Sullivan G.J., Ohm J.-R. Overview of the versatile video coding (VVC) standard and its applications. Preprint submitted to IEEE Trans. Circuits and Systs. for Video Tech., December 2020. https://doi.org/10.1109/TCSVT.2021.3060525 .
28. X. Zhao X. et al. Transform coding in the VVC standard. IEEE Transactions on Circuits and Systems for Video Technology. 2021. Vol. 31, N 10. P. 3878–3890. https://doi.org/10.1109/TCSVT.2021.3087706 .

29. Zhang Z., Zhao X., Li X., Li Z., Liu S. Fast adaptive multiple transform for versatile video coding. Proc. Data Compress. Conf. (DCC). 2019. P. 63–72. https://doi.org/10.1109/DCC.2019.00022 .

30. Zhao X., Chen J., Karczewicz M., Zhang L., Li X., Chien W.-J. Enhanced multiple transform for video coding. Proc. Data Compress. Conf. (DCC). 2016. P. 73–82. https://doi.org/10.1109/DCC.2016.9 .

31. Shevchuk B.M., Zadiraka V.K., Gnativ L.O., Frayer S.V. Technology of multifunctional processing and transmission of information in monitoring networks. Kyiv: Nauk. Dumka, 2010. 378 p. https://doi.org/10.1007/s10559-016-9810-9 .

32. Hnativ L.O. High-order integer cosine transform: Construction method and fast algorithms for high-resolution image and video coding. Cybernetics and Systems Analysis. 2017. Vol. 53, N 4. P. 615–626, 2017. https://doi.org/10.1007/s10559-017-9964-0 .

33. Hnativ L.O. Integer cosine transforms: methods to construct new order 8, 16 fast transforms and their application. Cybernetics and Systems Analysis. 2014. Vol. 50, N 6. P. 913–929. https://doi.org/10.1007/s10559-014-9682-9 .

34. Hnativ L.O. Integer cosine transforms for high-efficiency image and video coding. Cybernetics and Systems Analysis. 2016. Vol. 52, N 5. P. 802–816. https://doi.org/10.1007/s10559-016-9881-7 .

35. Fuldseth A., Bjntegaard G., Sadafale M. et al. CE10: Core transform design for HEVC. ITU-T, Doc. JCTVC-G495, Geneva, CH, Nov. 2011.

36. Richardson I.E. H.264 and MPEG-4 video compression: Video coding for next-generation multimedia. Chichester: John Wiley~Sons, 2003. https://doi.org/10.1002/0470869605 .

UDC 519.6, 004.932, 004.627

FAST INTEGER SINE AND COSINE TRANSFORMS TYPE IV LOWCOMPLEXITY FOR VIDEO CODING

REFERENCES

FAST INTEGER SINE AND COSINE TRANSFORMS TYPE IV
LOWCOMPLEXITY FOR VIDEO CODING