A feature­based approach to fractal image compression

DOI: 10.31673/2412-9070.2020.052226

Abstract

Recently a number of researches have demonstrated performance improvement in the video fractal compression compared to the current video transmission standards (MPEG, H.263, H.264). This article describes a current problem of relatively low fractal encoding speed. Indeed, high computational complexity is a sore point of fractal compression approach. It seems almost every paper on this subject touches the problem of encoding speed. Productive ideas and algorithms can be borrowed from the pattern recognition problem. In the course of recent decades feature points approach in computer vision has been demonstrating good performance in SLAM and pattern recognition. Technology of feature detection, description and tracking is being developed successfully and has effective applications in augmented reality like Android ARCore and IOS ARKit frameworks that are real-time engines. Similarities among parts of video frames are analyzed and used for both image registration and visual scene tracking therefore it fits highly to block matching task. Statistic properties for domain/range blocks matching has been analyzed on the basis of previous investigation for fractal compression. As a result, a simple algorithm is proposed based on computer vision approach. The approach includes a visual feature points extraction, feature descriptors calculation and fast NN-search in descriptor space. The key idea of the proposed approach is as follows. Only a limited number of domain blocks around the most salient points are subject to selection. Other blocks are not essential for matching as transforms would have big Lipschitz constant and will have worse contractive properties. Salient points should be unique as well. Further the descriptors for feature point are calculated. The algorithm has O(N log N) complexity for pixel number in the frame image, however if the number of domain blocks is limited the complexity could be almost linear. Python program for the algorithm test has been developed and shows that reconstruction result is acceptable in terms of encoding speed (< 2 s on 2 GHz CPU) and quality (PSNR) ~25 dB. The result of the proposed approach could be interesting for further improvement both for image and video compression. Further steps for quality increasing are also described.

Keywords: fractal image compression; computer vision method.

References
1. Michael F. Barnsley, Alan D. Sloan. Methods and apparatus for image compression by iterated function system. US4941193A, 1987.
2. Lima V., Sсhwartz W., Pedrini H. Fast Low Bit-Rate 3D Searchless Fractal Video Encoding. 10.1109/SIBGRAPI.2011.15. Р. 189–196.
3. Furao S., Hasegawa O. A Fast No Search Fractal Image Coding Method // Signal Processing: Image Communication. 2004. vol. 19, no. 5. P. 393–404.
4. Jacquin A. Fractal Theory of Iterated Markov Operators with Applications to Digital Image Coding: Doctoral Thesis, Georgia Institute of Technology, 1989.
5. Ruhl M., Hartenstein H. Optimal fractal coding is NP-hard: Proceedings DCC’97 Data Compression Conference / J. A. Storer, M. Cohn (eds.) // IEEE Computer Society Press, March 1997.
6. Dietmar Saupe. Lean domain pools for fractal image compression: Conference Proceedings of SPIE Electronic Imaging’96, Science and Technology, Still mage Compression II. San Jose, January 1996. Vol. 2669.
7. Fisher Y. Fractal image compression: theory and application. Springer-Verlag, New York, 1995.
8. Prem Melville, Vinhthuy Phan. Fractal Compression. 1997.
9. Faster fractal image compression using quadtree recomposition / D. Jackson, W. Mahmoud, W. A. Stapleton, P. Gaughan // Image and Vision Computing. 1997. Vol. 15, Issue 10. P. 759–767.
10. Abdul-Rahman Selim, Dessouky Hadhoud, Fathi Abd El-Samie. A simplified fractal image compression algorithm: International Conference on Computer Engineering and Systems // ICCES, 2008. P. 53–58. 10.1109/ICCES.2008.4772965, 2008
11. Saupe D. Accelerating fractal image compression by multi-dimensional nearest neighbor search: Proceedings DCC ’95 Data Compression Conference. Snowbird, UT, USA, 1995. P. 222–231.
12. Schwartz W. R., Pedrini H. Improved Fractal Image Compression Based On Robust Feature Descriptors // International Journ. of Image and Graphics. 2011. Vol. 11, No. 4. P. 571–587.
13. Dalal N., Triggs B. Histograms of Oriented Gradients for Human Detection: International Conference on Computer Vision and Pattern Recognition. Jun. 2005. P. 886–893.
14. Feature-Based Sparse Representation for Image Similarity Assessment / Li-Wei Kang, Chao-Yung Hsu, Hung-Wei Chen [et al.] // IEEE Transactions On Multimedia. October 2011. Vol. 13, No. 5.
15. Lowe D. Distinctive Image Features from Scale-Invariant Keypoints // International Journal of Computer Vision. 2004.
16. Rosten E., Drummond T. Machine learning for high-speed corner detection: European Conference on Computer Vision. 2006. Springer. P. 430–443. (The FAST corner detector).
17. Facciolo G., Limare N., Meinhardt E. Integral Images for Block Matching // Image Processing On Line. 2014.
18. Tomasi C., Kanade T. Detection and Tracking of Point Features // Carnegie Mellon University Technical Report CMU-CS-91-132. April 1991.
19. Lima V., Sсhwartz W., Pedrini H. Fast Low Bit-Rate 3D Searchless Fractal Video Encoding. P. 189–196. 10.1109/SIBGRAPI.2011.15.