Арзуманян Роман Вадимович, Южный Федеральный Университет (347922, РФ, г. Таганрог, ул. Чехова, д. 22), аспирант
Arzumanyan Roman Vadimovich, PhD student of department of Intellectual and Multiprocessor Systems, Institute of Computer Technology and Information Security of Southern Federal University (Checkhova str. 22. Taganrog, Russian Federation)
Статья посвящена разработке быстрого программного алгоритма арифметического кодирования для задач сжатия цифровых изображений. Предметом данной работы является задача исследования зависимости сложности алгоритма арифметического кодера от различных критериев сложности помимо размера входа. Задачей работы является поиск тех составных частей алгоритма арифметического кодера, которые являются наиболее вычислительно сложными с последующей оптимизацией производительности их программной реализации. Целью данной работы является разработка быстрого алгоритма арифметического кодера в составе видеокодека для сжатия изображений без учёта межкадровой разницы для применения новых кодеков. Предложен новый метод нахождения сложности алгоритма в среднем и оптимизированный программный алгоритм арифметического кодера, проведено теоретическое исследование с последующим проведением вычислительного эксперимента, при этом использована выборка спутниковых снимков акватории Азовского моря. Увеличена производительность программной реализации арифметического кодера на примере видеокодека VP9. Скорость работы арифметического кодера увеличена на 7%. Полученные практические результаты позволяют увеличить скорость работы новейших алгоритмов сжатия цифровых фото- и видеоизображений и делают возможным их применение на мобильных вычислительных платформах, в том числе в составе бортовой электроники БПЛА. Теоретические результаты данной работы расширяют методы анализа сложности алгоритма в среднем для тех случаев, когда количество шагов алгоритма зависит не только от размеров входа, но также и от неизмеримых критериев, например, от схемы обращения к общей оперативной памяти со стороны параллельных процессоров.
This article is devoted to the development of fast arithmetical encoding algorithm for compressing digital images. Subject of this paper is the research of arithmetical encoder complexity dependency on set of criteria beside the problem input size. The task of this article is to research those encoder compartments, which are the most computationally expensive and optimize their implementations. Aim of this research is the development of fast arithmetical encoder as a part of still image codec for compressing the images coming during distant aquatory objects scanning. New mean algorithm complexity estimation method is proposed as well as optimized arithmetical encoder algorithm based on mentioned method. Theoretical research is conducted, results of which are proved with numerical experiment. Actual set of satellite images of Azov sea aquatory was used. Performance of arithmetical encoder is improved by 7%. New method for mean algorithm complexity assessment is proposed which is based on partitioning of inputs array into equivalence classes. Obtained practical results allows increasing newest image compression techniques performance and using them on mobile computational platforms including those, which are installed on UAVs. Theoretical results of this article expands set of methods for assessing the mean algorithm complexity for those cases when number of steps doesn’t depend on problem’s input size but rather on non-measureable criteria such as memory access pattern to RAM from multiple ALUs.
The authors declare that there are no conflicts of interest present.