Fast normalized covariance based similarity measure for fractal video compression with Quadtree partitioning

Author Name(s): Yuvaraj.K*, B. Deepa, S. Geetha Reddy
Author Email: yuvaraj.kunati@gmail.com

Abstract

Fast normalized covariance based similarity measure for fractal video compression with quadtree partitioning is proposed in this paper. To increase the speed of fractal encoding, a simplified expression of covariance between range and overlapped domain blocks within a search window is implemented in frequency domain. All the covariance coefficients are normalized by using standard deviation of overlapped domain blocks and these are efficiently calculated in one computation by using two different approaches, namely, FFT based and sum table based. Results of these two approaches are compared and they are almost equal to each other in all aspects, except the memory requirement. Based on proposed simplified similarity measure, gray level transformation parameters are computationally modified and isometry transformations are performed using rotation/reflection properties of IFFT. Quadtree decompositions are used for the partitions of larger size of range block, that is, 16 × 16, which is based on target level of motion, compensated prediction error. Experimental result shows that proposed method can increase the encoding speed and compression ratio by 66.49% and 9.58%, respectively, as compared to NHEXS method with increase in PSNR by 0.41 dB. Compared to H.264, proposed method can save 20% of compression time with marginal variation in PSNR and compression ratio.

Introduction

The emerging multimedia applications such as video conferencing, video over mobile phones, video email, and wireless communications require an effective video coding standard to achieve a low bit rate with good quality. Performance of video coding standard depends on parameters such as quality of reconstructed video, compression ratio, and encoding time. Fractal based video compression [1] is an alternative to accomplish high compression ratio with good quality reconstructed output video than the existing video standards (MPEG, H.263, H.264). Recently, various researchers proposed different algorithms to improve the fractal encoding speed.

Jacquin [2] proposed an innovative technique which is based on the fractal theory of iterated function system for image compression. It reduces an affine redundancy of an image by using its self-similarity properties. Video sequences contain temporal redundancies between consecutive frames that can be easily removed by using fractal based technique. Fractal coding has received attention of researcher due to its advantages of independent resolution, high decoding speed, and high compression ratio [3, 4]. But high encoding time is main drawback of fractal based method; due to this it is not useful for real time applications. The motivation of this method is that it gives high compression ratio with good quality output which is useful for storage and transmission of bulky videos. To increase the encoding speed with keeping motivational parameters, a fast fractal video coder system is proposed.

Cube-based [5, 6] and frame based [7] fractal compression methods are used frequently for video compression. In cube-based compression, the video is divided into groups of frames, each of which in turn is partitioned into three-dimensional (3D) domain and range blocks; however, it has high computing complexity and low compression ratio. In frame based compression, each frame is encoded using the previous frame as a domain pool which introduces and spreads the error between the frames and it can be used to obtain a high compression ratio. Wang proposed a fixed block size hybrid compression algorithm [8] and an adaptive partition instead of fixed-size partition [9], which merges the advantages of cube-based and frame based fractal compression method. Another hybrid coder scheme which combines neighbourhood vector quantization with fractal coding to compress the video as a 3D volume was proposed by Yao and Wilson [10]. Fractal approach for 3D search less [11], prediction of error frame for low bit rate video [12], and wavelet transform based video coding approach [13, 14] are also considered for compression of videos.

Conclusion

In this paper, a quadtree partition based fast normalized covariance for fractal video compression is presented. A simplified normalized covariance for similarity measure, eight isometry transformations using IFFT properties, and modified new gray level transformation parameters are proposed and estimated using FFT to improve the encoding speed and output quality. Meanwhile, this method can use FFT based or sum table based approaches to normalize the covariance matrix, which further increases the encoding speed significantly. They are used for the calculation of mean and standard deviation of all overlapped blocks in one computation. The results of using these approaches are almost equal in all perspective. The main drawback of sum table based method is that it required large memory space to store the tables as compared to the FFT based method. Quadtree partition helps to achieve high compression ratios with good quality output. The proposed methods can save the encoding time by 98.17% and 66.49%, compression ratio is increased by 129% and 9.58%, and the output quality increased by 4.12 dB and 0.41 dB in comparison with CPM/NCIM and NHEXS methods, respectively. In comparison to H.264, this method saves 20% of compression time with marginal degradation in frame quality and compression ratio.

References

  1. S. Lazar and L. T. Bruton, “Fractal block coding of digital video,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 4, no. 3, pp. 297–308, 1994. View at Publisher · View at Google Scholar · View at Scopus
  2. E. Jacquin, “Image coding based on a fractal theory of iterated contractive image transformations,” IEEE Transactions of Image Processing, vol. 1, no. 1, pp. 18–30, 1992. View at Publisher · View at Google Scholar · View at Scopus
  3. Fisher, Fractal Image Compression: Theory and Application, Springer, New York, NY, USA, 1995. View at Publisher · View at Google Scholar · View at MathSciNet
  4. Zheng, G. Liu, and X. Niu, “An improved fractal image compression approach by using iterated function system and genetic algorithm,” Computers & Mathematics with Applications, vol. 51, no. 11, pp. 1727–1740, 2006. View at Publisher · View at Google Scholar · View at Scopus
  5. U. Barthel and T. Voye, “Three-dimensional fractal video coding,” in Proceedings of the IEEE International Conference on Image Processing, vol. 3, pp. 260–263, IEEE, Washington, DC, USA, 1995. View at Publisher · View at Google Scholar
  6. -C. Wang and C.-H. Hsieh, “Efficient fractal video coding algorithm using intercube correlation search,” Optical Engineering, vol. 39, no. 8, pp. 2058–2064, 2000. View at Publisher · View at Google Scholar · View at Scopus
  7. Wang and C.-H. Lai, “A hybrid fractal video compression method,” Computers and Mathematics with Applications, vol. 50, no. 3-4, pp. 611–621, 2005. View at Publisher · View at Google Scholar · View at MathSciNet · View at Scopus
  8. Wang, R. Liu, and C.-H. Lai, “Adaptive partition and hybrid method in fractal video compression,” Computers & Mathematics with Applications, vol. 51, no. 11, pp. 1715–1726, 2006. View at Publisher · View at Google Scholar · View at MathSciNet · View at Scopus
  9. Wang and C.-H. Lai, “Grey video compression methods using fractals,” International Journal of Computer Mathematics, vol. 84, no. 11, pp. 1567–1590, 2007. View at Publisher · View at Google Scholar · View at MathSciNet · View at Scopus
  10. Yao and R. Wilson, “Hybrid 3D fractal coding with neighbourhood vector quantisation,” EURASIP Journal on Applied Signal Processing, vol. 16, pp. 2571–2579, 2004. View at Publisher · View at Google Scholar
  11. V. Lima, W. R. Schwartz, and H. Pedrini, “3D searchless fractal video encoding at low bit rates,” Journal of Mathematical Imaging and Vision, vol. 45, no. 3, pp. 239–250, 2013. View at Publisher · View at Google Scholar · View at Scopus
  12. Brijmohan and S. H. Mneney, “Low bit-rate video coding using fractal compression of wavelet subtrees,” in Proceedings of the 7th IEEE AFRICON Conference in Africa: Technology Innovation, pp. 39–44, September 2004. View at Scopus
  13. Zhang, L. M. Po, and Y. L. Yu, “Wavelet transform based variable tree size fractal video coding,” in Proceedings of the IEEE International Conference on Image Processing, pp. 294–297, IEEE, Santa Barbara, Calif, USA, 1997. View at Publisher · View at Google Scholar
  14. Yu, J. Zhou, S. Yu, and D. Chi, “Fractal-based wavelet transform coding for low-bit-rate video,” in Electronic Imaging and Multimedia Systems, vol. 2898 of Proceedings of SPIE, pp. 226–237, Beijing, China, November 1996.
  15. -S. Kim, R.-C. Kim, and S.-U. Lee, “Fractal coding of video sequence using circular prediction mapping and noncontractive interframe mapping,” IEEE Transactions on Image Processing, vol. 7, no. 4, pp. 601–605, 1998. View at Publisher · View at Google Scholar · View at Scopus
  16. Belloulata, S. Zhu, and Z. Wang, “A fast fractal video coding algorithm using cross-hexagon search for block motion estimation,” ISRN Signal Processing, vol. 2011, Article ID 386128, 10 pages, 2011. View at Publisher · View at Google Scholar
  17. Zhu, Y. Hou, Z. Wang, and K. Belloulata, “Fractal video sequences coding with region-based functionality,” Applied Mathematical Modelling. Simulation and Computation for Engineering and Environmental Systems, vol. 36, no. 11, pp. 5633–5641, 2012. View at Publisher · View at Google Scholar · View at MathSciNet · View at Scopus
  18. Zhu, L. Li, and Z. Wang, “A novel fractal monocular and stereo video codec with object-based functionality,” Eurasip Journal on Advances in Signal Processing, vol. 2012, article 227, 2012. View at Publisher · View at Google Scholar · View at Scopus
  19. Belloulata, A. Belalia, and S. Zhu, “Object-based stereo video compression using fractals and shape-adaptive DCT,” AEU—International Journal of Electronics and Communications, vol. 68, no. 7, pp. 687–697, 2014. View at Publisher · View at Google Scholar · View at Scopus
  20. Zhu, L. Li, J. Chen, and K. Belloulata, “An automatic region-based video sequence codec based on fractal compression,” International Journal of Electronics and Communications, vol. 68, no. 8, pp. 795–805, 2014. View at Publisher · View at Google Scholar · View at Scopus
  21. Zhu, D. Zhao, and L. Zhang, “A novel high efficiency fractal multiview video codec,” Mathematical Problems in Engineering, vol. 2015, Article ID 613714, 12 pages, 2015. View at Publisher · View at Google Scholar · View at Scopus
  22. D. Kamble, N. V. Thakur, L. G. Malik, and P. R. Bajaj, “Fractal video coding using modified three step search algorithm for block matching motion estimation,” Advances in Intelligent Systems and Computing, vol. 332, pp. 151–162, 2015. View at Publisher · View at Google Scholar
  23. J. H. Hii, C. E. Hann, J. G. Chase, and E. E. W. Van Houten, “Fast normalized cross correlation for motion tracking using basis functions,” Computer Methods and Programs in Biomedicine, vol. 82, no. 2, pp. 144–156, 2006. View at Publisher · View at Google Scholar · View at Scopus
  24. B. Dhok, R. B. Deshmukh, and A. G. Keskar, “Efficient fractal image coding using fast fourier transform,” International Journal on Computing, vol. 1, no. 2, 2011. View at Google Scholar
  25. E. Chaudhari and S. B. Dhok, “Acceleration of fractal video compression using FFT,” in Proceedings of the 15th International Conference on Advanced Computing Technologies (ICACT ’13), pp. 1–4, September 2013. View at Publisher · View at Google Scholar · View at Scopus
  26. J. Sullivan and R. L. Baker, “Efficient quadtree coding of images and video,” IEEE Transactions on Image Processing, vol. 3, no. 3, pp. 327–331, 1994. View at Publisher · View at Google Scholar · View at Scopus
  27. K. Jain, Fundamentals of Digital Image Processing, PHI Publications, 1989.
  28. -M. Zhou, C. Zhang, and Z.-K. Zhang, “An efficient fractal image coding algorithm using unified feature and DCT,” Chaos, Solitons & Fractals, vol. 39, no. 4, pp. 1823–1830, 2009. View at Publisher · View at Google Scholar · View at Scopus
  29. CIPR Video Sequences, http://www.cipr.rpi.edu/resource/sequences/.
  30. 264/AVC Software Coordination, http://iphome.hhi.de/suehring/tml/.

1,014 total views, no views today

Download PDF File

About the author: admin