ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЗАСТОСУВАННЯ СЛОВНИКОВИХ МЕТОДІВ КОМПРЕСІЇ ДЛЯ ПРОГРЕСУЮЧОГО ІЄРАРХІЧНОГО СТИСНЕННЯ ЗОБРАЖЕНЬ БЕЗ ВТРАТ

Завантажень

Завантажень за місяць протягом останнього року

Шпортько, О. В. та Шпортько, Л. В. та Бомба, А. Я. та Shportko, A. V. та Shportko, L. V. та Bomba, А. Ya. (2021) ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЗАСТОСУВАННЯ СЛОВНИКОВИХ МЕТОДІВ КОМПРЕСІЇ ДЛЯ ПРОГРЕСУЮЧОГО ІЄРАРХІЧНОГО СТИСНЕННЯ ЗОБРАЖЕНЬ БЕЗ ВТРАТ. Вісник Національного університету водного господарства та природокористування (4(96)). с. 130-145.

[img] Text
Vt9611 (1).pdf

Download(333kB)

Анотація

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

Title in English

IMPROVING THE EFFICIENCY OF VOCABULARY COMPRESSION METHODS FOR PROGRESSIVE HIERARCHICAL COMPRESSION OF IMAGES WITHOUT LOSSES

English abstract

The expediency and the method of layer-by-layer pixel travers for the implementation of progressive hierarchical compression of images without losses are substantiated. To bypass the images, a scheme is proposed, according to which the first layer processes at least 16 pixels on each of the axes (if any) with the same step on both rows and columns. In the next layers, the pixels are processed in two passes: the first one sequentially processes those contained at the intersection of diagonals of squares with vertices in adjacent pixels of previous layers, and the second – sequentially bypasses equally spaced pixels between adjacent pixels of the previous layers and first pass pixels. The input stream for encoding is formed from sequentially placed data of all layers and passes. Three main typical stages of lossless image compression are described. The principles of input stream compression by the contextdependent algorithm LZ77 on the second of these stages are considered. A modification of the LZ77 dictionary compression algorithm is proposed. It allows to increase the efficiency of progressive hierarchical compression by additional search for identical sequences not only in the dictionary, but also starting from the nearest previously processed pixels. Additional search for identical sequences either finds sequences that are generally scattered in the dictionary and thus increases the probability of finding them or uses smaller offsets than during search only in the dictionary, and therefore reduces the compression ratio of images. The results of the usage of the proposed algorithm for image compression of the ACT set are presented. It is shown that the application of the above modification of the LZ77 algorithm allows, for example, to further reduce the compression coefficient of discrete-tone images of this set by an average of 0.59 bpb. According to the results of the study, the following conclusions were made: 1. In the new versions of graphic formats and new lossless image compression formats, it is advisable to implement progressive hierarchical compression, thus it can significantly speed up decoding when the size of the output area is smaller than the image size. 2. Reducing the size of images compressed in a progressive hierarchical way is mostly achieved on the last layers, because the pixels used by both the dictionary algorithm and predictors have the highest level of correlation with the predicted pixel comparing with the previous layers. 3. An increase of the efficiency of the classical algorithm LZ77 in the process of progressive hierarchical compression of lossless images is possible by additional search for the same sequences starting from the nearest previously processed pixels. 4. Vocabulary algorithms reduce the compression coefficient of primarily artificial discrete-tone images significantly, because such images contain many identical adjacent sequences of brightness of the pixel components (for example, of the ACT set compression coefficient reduction is more than 1 bpb).

Тип елементу : Стаття
Ключові слова: прогресуюче стиснення зображень; стиснення без втрат; словникові методи компресії; модифікації алгоритму LZ77; progressive image compression; lossless compression; dictionary compression methods; modifications of the LZ77 algorithm
УДК: 004.043
Бібліографічний опис: Шпортько О. В. Підвищення ефективності застосування словникових методів компресії для прогресуючого ієрархічного стиснення зображень без втрат / О. В. Шпортько, Л. В. Шпортько, А. Я. Бомба // Вісник НУВГП, 2021. - Вип. 4(96). - С. 130-145.
Тематики: Видання університету > Вісник НУВГП > серія "Технічні науки" > 2021 > Вісник 4
Видання університету > Вісник НУВГП > серія "Технічні науки" > 2021
Видання університету
Користувач, що депонує: С. Й. Гипчинська
Дата внесення: 31 Трав 2022 11:16
Останні зміни: 31 Трав 2022 11:16
URI: http://ep3.nuwm.edu.ua/id/eprint/23567
Перегляд елементу Перегляд елементу

Завантажень

Завантажень за місяць протягом останнього року