Модифицированный подход к оптимизации производительности арифметического декодера для сжатия аэрофотоснимков

Статья посвящена разработке быстрого программного алгоритма арифметического кодирования для задач сжатия цифровых изображений. Предметом данной работы является задача исследования зависимости сложности алгоритма арифметического кодера от различных критериев сложности помимо размера входа. Задачей работы является поиск тех составных частей алгоритма арифметического кодера, которые являются наиболее вычислительно сложными с последующей оптимизацией производительности их программной реализации. Целью данной работы является разработка быстрого алгоритма арифметического кодера в составе видеокодека для сжатия изображений без учёта межкадровой разницы для применения новых кодеков. Предложен новый метод нахождения сложности алгоритма в среднем и оптимизированный программный алгоритм арифметического кодера, проведено теоретическое исследование с последующим проведением вычислительного эксперимента, при этом использована выборка спутниковых снимков акватории Азовского моря. Увеличена производительность программной реализации арифметического кодера на примере видеокодека VP9. Скорость работы арифметического кодера увеличена на 7%. Полученные практические результаты позволяют увеличить скорость работы новейших алгоритмов сжатия цифровых фото- и видеоизображений и делают возможным их применение на мобильных вычислительных платформах, в том числе в составе бортовой электроники БПЛА. Теоретические результаты данной работы расширяют методы анализа сложности алгоритма в среднем для тех случаев, когда количество шагов алгоритма зависит не только от размеров входа, но также и от неизмеримых критериев, например, от схемы обращения к общей оперативной памяти со стороны параллельных процессоров.

1. WebP Compression Study // https://developers.google.com/speed/webp/docs/webp_study.

2. T. Nguyen and D. Marpe, "Objective Performance Evaluation of the HEVC Main Still Picture Profile," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 25, no. 5, pp. 790-797, May 2015.

3. Arzumanyan R. V. Sukhinov А. I. Research on high-performance Google VP9 codec software implementation // Software systems and computation methods. — 2016. — vol. 1, № 2. — pp. 184–200.

4. Blahut, R. (2010). Fast Algorithms for Signal Processing. Cambridge: Cambridge University Press.

5. G. K. Wallace, "The JPEG still picture compression standard," in IEEE Transactions on Consumer Electronics, vol. 38, no. 1, pp. xviii-xxxiv, Feb. 1992.

6. Dvorkovich А.V., Dvorkovich V.P. Digital video-informational systems (theory and practice) // Technosphera. – 2012. -1009p.

7. Asaduzzaman, A.; Suryanarayana, V.R.; Rahman, M. Performance-power analysis of H.265/HEVC and H.264/AVC running on multicore cache systems // Intelligent Signal Processing and Communications Systems. 2013. - С. 174-179.

8. Sedgewick Robert, Wayne Kevin. Algorithms (Fourth edition). — Addison-Wesley, 2016.

9. Introduction to Algorithms / Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson. — 2nd edition. — McGraw-Hill Higher Education, 2001.

10. Welch William J. Algorithmic complexity: three NP-hard problems in computational statistics // Journal of Statistical Computation and Simulation. — 1982. — Vol. 15, no. 1. — P. 17–25. — URL: http://www.tandfonline.com/ doi/abs/10.1080/00949658208810560.

11. High efficiency video coding[Электронный ресурс] // sist.sysu.edu.cn.

12. 121. Sze V., Budagavi M. Parallelization of CABAC transform coefficient coding for HEVC // Picture Coding Symposium (PCS), 2012. — 2012. — May. — Pp. 509– 512.

13. Handbook of data compression / D. Grois, D. Marpe, A. Mulayoff et al. — Springer, 2010. — С. 1198.

14. Bit Twiddling Hacks [Электронный ресурс] // Stanford University.

15. Gervich L. R., Steinberg B. Y. Exaflops systems programming // Otktrytie systemi. - 2013. - №8.

16. Waren G. S.-jr. Algorithmic tricks for programmers. – 2nd ed. – М.: Williams, 2013. - 512 p.