О поисковом синтезе предиктора для сжатия изображений

  • Павел [Pavel] Александрович [A.] Чернов [Chernov]
Ключевые слова: предиктор, сжатие изображений без потерь, GAP, поисковый синтез, генетический алгоритм

Аннотация

В области сжатия полутоновых изображений без потерь высокие результаты сжатия обеспечиваются предиктивной схемой сжатия. Одним из предикторов является предиктор GAP (Gradient Adjusted Prediction). В данной статье исследуется возможность поискового синтеза предиктора, наподобие предиктора GAP, рассмотрена возможность поискового синтеза оптимальных модельных параметров предиктора для каждого возможного контекста предиктора GAP, при этом исходные изображения разбивались на контексты с множествами окрестных точек.

При реализации поискового синтеза предиктора, наподобие предиктора GAP, использован классический генетический алгоритм, однако с целью улучшения работы классического генетического алгоритма было проведено исследование генераторов псевдослучайных чисел с равномерным распределением, построенных по методу мультипликативного датчика. Синтез генераторов псевдослучайных чисел с равномерным законом распределения был автоматизирован, автоматически выполняется проверка статистической гипотезы о типе распределения обеспечиваемого генератором псевдослучайных чисел, для этого вычисляется значение распределения Хи-квадрат, выполняется упрощенный расчет Гамма-функции и численное интегрирование по формуле Симпсона. В итоге были использованы генераторы псевдослучайных чисел не встроенные в инструментальные средства программирования, а подобранные самостоятельно, периоды подобранных генераторов псевдослучайных чисел находятся в диапазоне от 402 544 072 до 2 544 344 962.

Дискретный характер определения контекстов GAP в оригинальном GAP приводит к заметному завышению энтропии ошибки предсказания. Так, для контекста 32 разница энтропии, достигнутой в результате оптимизации модельных параметров, и энтропии достигнутой оригинальным GAP предиктором, составляет 0,1148 bpp, для контекста 33 – 0,02568 bpp, для контекста 8 – 0,07011 bpp, для контекста 9 – 0,00925 bpp. Предиктор GAP имеет не много возможностей для улучшения предсказания за счет определения оптимальных параметров работы предиктора для каждого возможного контекста. Однако по причине малой вычислительной сложности предиктора GAP важно исследовать возможности по улучшению эффективности предиктора GAP.

Сведения об авторе

Павел [Pavel] Александрович [A.] Чернов [Chernov]

магистр по направлению «Информатика и вычислительная техника», e-mail: pavel_chernov_articles@mail.ru

Литература

1. Meyer B., Tischer P. Glicbawls — Grey Level Image Compression by Adaptive Weighted Least Squares // Proc. Data Compression Conf. Snowbird, 2001. Pp. 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. 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.
Опубликован
2022-10-24
Раздел
Математическое и программное обеспечение вычислительных систем, комплексов и компьютерных сетей (технические науки) (2.3.5)