Шпортько, О. В. та Шпортько, Л. В. та Бомба, А. Я. (2022) ФОРМУВАННЯ РОЗКЛАДУ МОДИФІКОВАНОГО АЛГОРИТМУ LZ77 У ФОРМАТІ DEFLATE З ОРІЄНТАЦІЄЮ ДОВЖИН ОДНАКОВИХ ПОСЛІДОВНОСТЕЙ НА ЦІЛІ ПІКСЕЛІ. Вісник Національного університету водного господарства та природокористування (1(97)). с. 244-260.

Text Vt9721 (1).pdf Download(301kB)

Анотація

Проаналізовано взаємовплив основних етапів стиснення зображень без втрат та формату словникової компресії Deflate. Обґрунтована доцільність перерозподілу довжин суміжних замін модифікованого алгоритму LZ77 з їх орієнтацією на цілі пікселі в процесі прогресуючого ієрархічного стиснення зображень без втрат. Встановлено, що під час першого проходу цього алгоритму з пошуком однакових послідовностей по найближчих опрацьованих раніше пікселях орієнтацію на цілі пікселі доцільно застосовувати для всіх графічних файлів, а в процесі другого проходу з пошуком однакових послідовностей в словнику – лише для дискретнотонових зображень. Подано результати застосування різних розкладів модифікованого алгоритму LZ77 для стиснення зображень набору ACT. Показано, що застосування комбінованої орієнтації розкладу модифікованого алгоритму LZ77 на цілі пікселі дає змогу додатково зменшити коефіцієнти стиснення окремих зображень на 0.01–0.02 bpb, сповільнюючи при цьому кодування в середньому лише на 0.05 с.

Title in English

FORMATION OF THE DECOMPOSITION OF THE MODIFIED LZ77 ALGORITHM IN DEFLATE FORMAT WITH ORIENTATION OF LENGTHS OF THE SAME SEQUENCES ON WHOLE PIXELS

English abstract

The article analyzes the interaction of the main stages of lossless image compression and the format of Deflate dictionary compression. The advantages and disadvantages of «greedy» and «lazy» schedules of the LZ77 algorithm as part of the Deflate format are described. The expediency of redistribution of adjacent substitution lengths of the modified LZ77 algorithm with their orientation on whole pixels in the process of progressive hierarchical compression of lossless images is substantiated. It is established that during the first pass of this algorithm with search of identical sequences of the nearest previously processed pixels the orientation on whole pixels should be applied to all graphic files, and during the second pass with the search of identical sequences in the dictionary – only for discrete images. The results of the application of different schedules of the modified LZ77 algorithm for image compression of the ACT set are presented. According to the results of the study, the following conclusions were made: 1. It is possible through additional pre-passage of image pixels in search of identical sequences, starting from the nearest previously processed pixels to increase the efficiency of the classical algorithm LZ77 with dictionary search in the process of progressive hierarchical compression of lossless images. This additional pass allows to reduce the compression ratios due to the same sequences which are not included in the dictionary, and the use of smaller offsets for the nearest processed pixels. 2. Vocabulary algorithms reduce the compression ratios of primarily artificial discrete-tone images significantly, as such images contain many of the same adjacent sequences of brightness of the pixel components. 3. It is possible to further reduce the compression ratio of the modified LZ77 algorithm for individual images by a maximum of 0.02 bpb by combining its decomposition into whole pixels. This orientation allows not to increase the compression ratios for all images and slows down the encoding by an average of only 0.05 s.

Перегляд елементу

Завантажень