About Search Synthesis of the Predictor for Image Compression
DOI:
https://doi.org/10.24160/1993-6982-2023-1-136-144Keywords:
multipredictor, predictor, lossless image compression, GAP, Blend-16, Blend-A13Abstract
In the field of lossless halftone image compression, high compression results are provided by a predictive compression scheme. One predictor is the GAP (Gradient Adjusted Prediction) predictor. This article explores the possibility of predictor search synthesis, like GAP predictor, considers the possibility of search synthesis of optimal predictor model parameters for each possible GAP predictor context, while the test images were divided into contexts with sets of neighborhood pixels.
When implementing the search synthesis of a predictor, like the GAP predictor, a classical genetic algorithm was used, however, in order to improve the operation of the classical genetic algorithm, a study was carried out on pseudo-random number generators with a uniform distribution, built using the multiplicative sensor method. The synthesis of pseudo-random number generators with a uniform distribution was automated, the statistical hypothesis on the type of distribution provided by the pseudo-random number generator is automatically tested, for this the value of the Chi-square distribution is calculated, a simplified calculation of the Gamma function and numerical integration according to the Simpson formula is performed. As a result, pseudo-random number generators were not built into the programming tools, but selected on their own, the periods of selected pseudo-random number generators are in the range from 402 544 072 to 2 544 344 962.
The discrete nature of defining GAP contexts in the original GAP leads to a noticeable overestimation of the entropy of the prediction error. Thus, for context 32, the difference between entropy achieved as a result of optimization of model parameters and entropy achieved by the original GAP predictor is 0.1148 bpp, for context 33 - 0.02568 bpp, for context 8 - 0.07011 bpp, for context 9 - 0.00925 bpp. The GAP predictor does not have many possibilities to improve prediction by determining optimal predictor performance parameters for each possible context. However, due to the low computational complexity of the GAP predictor, it is important to investigate opportunities to improve the effectiveness of the GAP predictor.
References
2. Ulacha G., Statinski R. On Context-based Predictive Techniques for Lossless Image Compression // Proc. XII Intern. Wopkshop Systems, Signal and Image Proc. Poznan, 2005. Pp. 990—993.
3. Балашов В.Н., Гольцов А.Г. Моделирование генераторов случайных чисел. М.: Изд-во МЭИ, 2009.
4. Гмурман В.Е. Теория вероятностей и математическая статистика. М.: Высшая школа, 2003.
5. Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. М.: Высшая школа, 1994.
6. Программа для ЭВМ № 2021618408. Поисковый синтез предиктора v1.0 / П.А. Чернов.
7. Карпенко, А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы вдохновленные природой. М.: Изд-во МГТУ им. Н. Э. Баумана, 2021.
8. Чернов П.А. Древовидная модель решения многомерных мультимодальных оптимизационных задач гибридными методами поиска // Вестник МЭИ. 2016. № 1. С. 18—25.
---\
Для цитирования: Чернов П.А. О поисковом синтезе предиктора для сжатия изображений // Вестник МЭИ. 2023. № 1. С. 136—144. DOI: 10.24160/1993-6982-2023-1-136-144.
#
1. Meyer B., Tischer P. Glicbawls — Grey Level Image Compression by Adaptive Weighted Least Squares. Proc. Data Compression Conf. Snowbird, 2001:503—515.
2. Ulacha G., Statinski R. On Context-based Predictive Techniques for Lossless Image Compression. Proc. XII Intern. Wopkshop Systems, Signal and Image Proc. Poznan, 2005:990—993.
3. Balashov V.N., Gol'tsov A.G. Modelirovanie Generatorov Sluchaynykh Chisel. M.: Izd-vo MEI, 2009. (in Russian).
4. Gmurman V.E. Teoriya Veroyatnostey i Matematicheskaya Statistika. M.: Vysshaya Shkola, 2003. (in Russian).
5. Amosov A.A., Dubinskiy Yu.A., Kopchenova N.V. Vychislitel'nye Metody dlya Inzhenerov. M.: Vysshaya Shkola, 1994. (in Russian).
6. Programma dlya EVM № 2021618408. Poiskovyy Sintez Prediktora v1.0. P.A. Chernov. (in Russian).
7. Karpenko, A.P. Sovremennye Algoritmy Poiskovoy Optimizatsii. Algoritmy Vdokhnovlennye Prirodoy. M.: Izd-vo MGTU im. N. E. Baumana, 2021. (in Russian).
8. Chernov P.A. Drevovidnaya Model' Resheniya Mnogomernykh Mul'timodal'nykh Optimizatsionnykh Zadach Gibridnymi Metodami Poiska. Vestnik MEI. 2016;1:18—25. (in Russian).
---
For citation: Chernov P.A About Search Synthesis of the Predictor for Image Compression. Bulletin of MPEI. 2023;1:136—144. (in Russian). DOI: 10.24160/1993-6982-2023-1-136-144.
