Fast Quadtree Based Normalized Cross Correlation Method for Fractal Video Compression using FFT

다국어 초록 (Multilingual Abstract)

In order to achieve fast computational speed with good visual quality of output video, we propose a frequency domain based new fractal video compression scheme. Normalized cross correlation is used to find the structural self similar domain block for the input range block. To increase the searching speed, cross correlation is implemented in the frequency domain using FFT with one computational operation for all the domain blocks instead of individual block wise calculations. The encoding time is further minimized by applying rotation and reflection DFT properties to the IFFT of zero padded range blocks. The energy of overlap small size domain blocks is pre-computed for the entire reference frame and retaining the energies of the overlapped search window portion of previous adjacent block. Quadtree decompositions are obtained by using domain block motion compensated prediction error as a threshold to control the further partitions of the block. It provides a better level of adaption to the scene contents than fixed block size approach. The result shows that, on average, the proposed method can raise the encoding speed by 48.8 % and 90 % higher than NHEXS and CPM/NCIM algorithms respectively. The compression ratio and PSNR of the proposed method is increased by 15.41 and 0.89 dB higher than that of NHEXS on average. For low bit rate videos, the proposed algorithm achieve the high compression ratio above 120 with more than 31 dB PSNR.

목차 (Table of Contents)

• Abstract
• 1. Introduction
• 2. Related Work
• 3. The Fractal Block Coding
• 4. Normalized Cross Correlation for Motion Estimation
• 5. New Fractal Video Coding
• 6. Experimental Results
• 7. Conclusion
• References

참고문헌 (Reference)

1 Y. Zhang, "Wavelet Transform Based Variable Tree Size Fractal Video Coding" 2 : 294-297, 1997

2 C. Urmson, "Video Compression through Fractal Block Coding" 2 : 465-467, 1998

3 K. U. Barthel, "Three-Dimensional Fractal Video Coding" 3 : 260-263, 1995

4 K. Belloulata, "Object-Based Stereo Video Compression using Fractals and Shape-Adaptive DCT" 68 (68): 687-697, 2014

5 Y. Bnjmohan, "Low Bit-rate Video Coding Using Fractal Compression of Wavelet Subtrees" 1 : 39-44, 2004

6 H. Hartenstein, "Lossless Acceleration of Fractal Image Coding via the Fast Fourier Transform" 16 (16): 383-394, 2000

7 Z. Wang, "Image Quality Assessment : From Error Visibility to Structural Similarity" 13 (13): 600-612, 2004

8 A. E. Jacquin, "Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations" 1 (1): 18-30, 1992

9 Z. Yao, "Hybrid 3D Fractal Coding with Neighborhood Vector Quantization" 16 : 2571-2579, 2004

10 A. K. Jain, "Fundamentals of Digital Image Processing" PHI publications 1989

11 Y. Fisher, "Fractal(self-VQ)Encoding of Video Sequences" 2308 : 1359-1370, 1994

12 S. Zhu, "Fractal Video Sequences Coding with Region-Based Functionality" 36 (36): 5633-5641, 2012

13 Y. Fisher, "Fractal Image Compression: Theory and Application" Springer Verlag 1995

14 C. S. Kim, "Fractal Coding of Video Sequence using Circular Prediction Mapping and Noncontractive Interframe Mapping" 7 (7): 601-605, 1998

15 C. S. Kim, "Fractal Coding of Video Sequence by Circular Prediction Mapping" 5 : 75-88, 1997

16 M. S. Lazar, "Fractal Block Coding of Digital Video" 4 (4): 297-308, 1994

17 B. Hurtgen, "Fractal Approach to Low Rate Video Coding" 2094 : 120-131, 1993

18 S. D. Wei, "Fast Normalized Cross Correlation Based on Adaptive Multilevel Winner Update" 413-416, 2007

19 A. A. Eskinder, "Fast Motion Estimation for Quad-Tree Based Video Coder Using Normalized Cross-Correlation Measure" 7 (7): 2013

20 V. D. Lima, "Fast Low Bit-Rate 3D Searchless Fractal Video Coding" 189-196, 2011

21 G. J. Sullivan, "Efficient Quadtree Coding of Image and Video" 3 (3): 327-331, 1994

22 C. C. Wang, "Efficient Fractal Video Coding Algorithm using Intercube correlation Search" 8 (8): 2058-2064, 2000

23 S. B. Dhok, "Efficient Fractal Image Coding using Fast Fourier Transform" 1 (1): 2011

24 "CIPR Sequences"

25 Y. M. Zhou, "An Efficient Fractal Image Coding Algorithm using Unified Feature and DCT" 39 (39): 1823-1830, 2009

26 Y. L. Lin, "An Edge Property-Based Neighborhood Region Search Strategy for Fractal Image Compression" 62 (62): 310-318, 2011

27 M. Wang, "Adaptive Partition and Hybrid Method in Fractal Video Compression" 51 (51): 1715-1726, 2006

28 R. E. Chaudhari, "Acceleration of Fractal Video Compression using FFT" 1-4, 2013

29 S. Zhu, "A Novel Fractal Monocular and Stereo Video Codec with Objectbased Functionality" 227 : 1-12, 2012

30 M. Wang, "A Hybrid Fractal Video Compression Method" 50 (50): 611-621, 2005

31 송병철, "A Fast Normalized Cross Correlation-Based Block Matching Algorithm Using Multilevel Cauchy-Schwartz Inequality" 한국전자통신연구원 33 (33): 401-406, 2011

32 K. Belloulata, "A Fast Fractal Video Coding Algorithm Using Cross-Hexagon Search for Block Motion Estimation" 1-10, 2011

33 J. Wan, "A Fast Context-Based Fractal Mobile Video Compression with GA and PSO" 112-115, 2014