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

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).

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

Завантажень