PDF

Abstract:
Context algorithms for interpolation of multidimensional signals in the compression problem are researched. A hierarchical compression method for arbitrary dimension signals is considered. For this method, an interpolation algorithm based on the context modeling is proposed. The algorithm is based on optimizing parameters of the interpolating function in a local neighborhood of the interpolated sample. At the same time, locally optimal parameters found for more decimated scale signal levels are used to interpolate samples of less decimated scale signal levels. The context interpolation algorithm is implemented programmatically as part of a hierarchical compression method. Computational experiments have shown that using a context interpolator instead of an average interpolator makes it possible to significantly improve the efficiency of hierarchical compression.

Keywords:
interpolation, compression, multivariate signal, context modeling, image, maximum error.

Citation:
Gashnikov MV. Interpolation based on context modeling for hierarchical compression of multidimensional signals. Computer Optics 2018; 42(3): 468-475. DOI: 10.18287/2412-6179-2018-42-3-468-475.

References:

1. Cohen A, Davenport MA, Leviatan D. On the stability and accuracy of least squares approximations. Foundations of Computational Mathematics 2013; 13(5): 819-834. DOI: 10.1007/s10208-013-9142-3.
2. Blinov AO, Fralenko VP. Multidimensional approximation for modeling and optimization problems. Automation and Remote Control 2009; 70(4): 652-662. DOI: 10.1134/S0005117909040110
3. Butyrsky EuYu, Kuvaldin IA, Chalkin VP. Мultidimensional functions' approximation [In Russian]. Scientific instrument building 2010; 20(2): 82-92.
4. Tchobanou MK, Makarov DV. Image compression by using tensor approximation [In Russian]. Problems of development of advanced micro and nanoelectronic systems 2014; 4: 109-112.
5. Caiafa CF, Cichocki A. Computing sparse representations of multidimensional signals using kronecker bases. Neural Computation 2016; 25(1): 186-220. DOI: 10.1162/NECO_a_00385.
6. Gulakov KV. Modeling multidimensional objects on the basis of cognitive maps with neural network identification of parameters [In Russian]. The Thesis for the Candidate’s Degree in Technical Sciences. Bryansk, 2016.
7. Krapuhina NV, Brinza BV. A new approach to multidimensional approximation of technological data based on the use of the group method of argumentation and neural networks [In Russian]. Non-Ferrous Metals 2007; 5: 19-23.
8. Mobli M, Hoch JC. Nonuniform sampling and non-Fourier signal processing methods in multidimensional NMR. Prog Nucl Magn Reson Spectrosc 2014; 83: 21-41. DOI: 10.1016/j.pnmrs.2014.09.002.
9. Verstakov EV, Zakharchenko VD. The comparative analysis of approximation algorithms of two-dimensional signals by Proni method and matrix bunches method [In Russian]. Radio and Telecommunication Systems 2015; 1(17): 26-31.
10. Shcherba EV. Application analysis of interpolation and extrapolation methods as used for image restoration [In Russian]. Computer optics 2009; 33(3): 336-339.
11. Sahnoun S, Djermoun E-H, Brie D, Comon P. A simultaneous sparse approximation method for multidimensional harmonic retrieval. Signal Processing 2017; 131: 36-48. DOI: 10.1016/j.sigpro.2016.07.029.
12. Donoho DL. Compressed sensing. IEEE Trans Inform Theory 2006; 52(4): 1289-1306. DOI: 10.1109/TIT.2006.871582.
13. Candes EJ, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans Inform Theory 2006; 52(2): 489-509. DOI: 10.1109/TIT.2005.862083.
14. Bigot J, Boyer C, Weiss P. An analysis of block sampling strategies in compressed sensing. IEEE Trans Inform Theory 2016; 62(4): 2125-2139. DOI: 10.1109/TIT.2016.2524628.
15. Baraniuk RG, Cevher V, Duarte MF, Hedge C. Model-based compressive sensing. IEEE Trans Inform Theory 2010; 56(4): 1982-2001. DOI: 10.1109/TIT.2010.2040894.
16. Chkifa A, Cohen A, Schwab C. High-dimensional adaptive sparse polynomial interpolation and applications to parametric PDEs. Found Comput Math 2014; 14(4): 601-633. DOI: 10.1007/s10208-013-9154-z.
17. Rissanen JJ, Langdon GG. Universal modeling and coding. IEEE Trans Inform Theory 1981; 27(1): 12-23. DOI: 10.1109/TIT.1981.1056282.
18. Trullemans S, Van Holsbeeke L, Signer B. The context modelling toolkit: A unified multi-layered context modelling approach. Proceedings of the ACM on Human-Computer Interaction 2017; 1(1): 7. DOI: 10.1145/3095810.
19.  Li X, Orchard MT. New edge-directed interpolation. IEEE Trans Image Process 2001; 10(10): 1521-1527. DOI: 10.1109/83.951537.
20. Varathaguru M. Sabeenian RS. New edge-directed interpolation based-lifting DWT and MSPIHT algorithm for image compression. Circuits and Systems 2016; 7(9): 2242-2252. DOI: 10.4236/cs.2016.79195.
21. Tekalp AM. Digital video processing. 2nd ed. Upper Saddle River, NJ: Prentice Hall; 2015. ISBN: 978-0-13-399100-0.
22. Chang Ch-I. Hyperspectral data processing: Algorithm design and analysis. Hoboken, NJ: John Wiley & Sons, Inc; 2013. ISBN: 978-0-471-69056-6.
23. Borengasser M, Hungate WS, Watkins R. Hyperspectral remote sensing: Principles and applications. Boca Raton, London, New York: CRC Press; 2007. ISBN: 978-1-56670-654-4.
24. Schowengerdt RA. Remote sensing: models and methods for image processing. 3th ed. Burlington, San Diego: Academic Press; 2007. ISBN 978-0-12-369407-2.
25. Gashnikov MV, Glumov NI, Sergeyev VV. Compression method for real-time systems of remote sensing. ICPR 2000; 3: 232-235. DOI: 10.1109/ICPR.2000.903527.
26. Gashnikov MV. Minimizing the entropy of post-interpo­lation residuals for image compression based on hierarchical grid interpolation. Computer Optics 2017; 41(2): 266-275. DOI: 10.18287/2412-6179-2017-41-2-266-275.
27. Gonzalez RC, Woods RE. Digital image processing. 3th ed. Upper Saddle River, NJ: Prentice Hall; 2007. ISBN: 978-0-13-168728-8.
28. Sayood K. Introduction to data compression. 4th ed. Wal-tham, MA: Morgan Kaufmann; 2012. ISBN: 978-0-12-415796-5.
29. Vatolin D, Ratushnyak A, Smirnov M, Yukin V. Data compression methods. Archive program architecture, image and video compression [In Russian]. Moscow: “Dialog-MIFI” Publisher; 2002. ISBN: 5-86404-170-X.
30. Efimov VM, Kolesnikov AN. Effectiveness estimation of the hierarchical and line-by-line lossless compression algorithms [In Russian]. Proceedings of the III conference “Pattern recognition and image analisys” 1997; 1: 157-161.
31. Soifer VA, ed. Computer image processing, Part II: Methods and algorithms. VDM Verlag Dr Müller; 2010. ISBN: 978-3-6391-7545-5.

---

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20