Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG
Предложены способы выбора предиктора для каждой строки пикселов и алгоритм разбиения изображения на блоки строк с помощью энтропии перед сжатием в формате PNG. Приведены фрагменты программ на языке C для оценки энтропии строк пикселов непосредственно и после применения контекстно-зависимого алгоритм...
Збережено в:
| Опубліковано в: : | Управляющие системы и машины |
|---|---|
| Дата: | 2010 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/82820 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG / А.Я. Бомба, О.В. Шпортько // Управляющие системы и машины. — 2010. — № 3. — С. 8-25. — Бібліогр.: 9 назв. — укр., рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860193945763446784 |
|---|---|
| author | Бомба, А.Я. Шпортько, О.В. |
| author_facet | Бомба, А.Я. Шпортько, О.В. |
| citation_txt | Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG / А.Я. Бомба, О.В. Шпортько // Управляющие системы и машины. — 2010. — № 3. — С. 8-25. — Бібліогр.: 9 назв. — укр., рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Предложены способы выбора предиктора для каждой строки пикселов и алгоритм разбиения изображения на блоки строк с помощью энтропии перед сжатием в формате PNG. Приведены фрагменты программ на языке C для оценки энтропии строк пикселов непосредственно и после применения контекстно-зависимого алгоритма. Описанные способы выбора предикторов строк позволяют уменьшить коэффициенты сжатия изображений набора ACT в формате PNG.
The methods are suggested of the choice of a predictor for every line of pixels and the algorithm of laying out of the image on the blocks of lines with the help of the entropy before a compression in the PNG format. The fragments of the programs in the C language for the estimation of the entropy of lines of pixels directly before and after the application of the context-dependent algorithm are presented. The described methods of the choice of predictors of lines make it possible to decrease the coefficients of the compression of a set of the ACT ratios in the PNG format.
Запропоновано способи вибору предиктора для кожного рядка пікселів та алгоритм розбиття зображення на блоки рядків за допомогою ентропії перед стисненням у форматі PNG. Наведено фрагменти програм мовою C для оцінки ентропії рядків пікселів безпосередньо та після застосування контекстно-залежного алгоритму. Описані способи вибору предикторів рядків дозволяють зменшити коефіцієнти стиснення зображень набору ACT у форматі PNG.
|
| first_indexed | 2025-12-07T18:07:52Z |
| format | Article |
| fulltext |
8 УСиМ, 2010, № 3
Новые методы в информатике
УДК 004.043
А.Я. Бомба, О.В. Шпортько
Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG
Предложены способы выбора предиктора для каждой строки пикселов и алгоритм разбиения изображения на блоки строк с
помощью энтропии перед сжатием в формате PNG. Приведены фрагменты программ на языке C для оценки энтропии строк
пикселов непосредственно и после применения контекстно-зависимого алгоритма. Описанные способы выбора предикторов
строк позволяют уменьшить коэффициенты сжатия изображений набора ACT в формате PNG.
The methods are suggested of the choice of a predictor for every line of pixels and the algorithm of laying out of the image on the blocks of
lines with the help of the entropy before a compression in the PNG format. The fragments of the programs in the C language for the estimation
of the entropy of lines of pixels directly before and after the application of the context-dependent algorithm are presented. The described methods of
the choice of predictors of lines make it possible to decrease the coefficients of the compression of a set of the ACT ratios in the PNG format.
Запропоновано способи вибору предиктора для кожного рядка пікселів та алгоритм розбиття зображення на блоки рядків за
допомогою ентропії перед стисненням у форматі PNG. Наведено фрагменти програм мовою C для оцінки ентропії рядків пік-
селів безпосередньо та після застосування контекстно-залежного алгоритму. Описані способи вибору предикторів рядків до-
зволяють зменшити коефіцієнти стиснення зображень набору ACT у форматі PNG.
Вступ. На даний час формат PNG [1] є одним
з основних для збереження зображень без втрат.
В Інтернеті, наприклад, нараховується понад
15 млн сторінок, що містять зображення у цьо-
му форматі. Популярності формату PNG спри-
яють, насамперед, прийнятні коефіцієнти сти-
снення (КС – відношення розміру стиснутих
до нестиснутих даних) та висока швидкість де-
кодування. Проблема зменшення розмірів фай-
лів зображень у цьому форматі є актуальною і
залишатиметься такою в найближчому майбу-
тньому, оскільки навіть часткове її розв'язання
дає змогу прискорити завантаження PNG-фай-
лів з мережі та підвищити ефективність вико-
ристання дискового простору.
База дослідження. Особливості етапів об-
робки даних зображень у форматі PNG
Піксели зображення записуються у PNG-фай-
ли найчастіше по рядках зверху вниз, а у кож-
ному рядку – послідовно зліва направо (як си-
мволи у текстах), формуючи тим самим вхідний
потік. Перед кодуванням ці піксели можуть бу-
ти попередньо оброблені предикторами. У PNG-
файлах, що використовуються сьогодні, стис-
нуті дані зберігаються у відокремлених блоках
згідно формату словникового стиснення DEFLA-
Ключові слова: безвтратне стиснення зображень, статичні предик-
тори, формат графічних файлів PNG.
TE [2]. Відповідно до цього формату, у стисну-
тих блоках містяться результати застосування
до вхідного потоку алгоритму LZH [3], згідно з
яким результати контекстно-залежного слов-
никового алгоритму LZ77 [4] стискаються кон-
текстно-незалежними кодами Хафмана [5]. Для
дослідження взаємовпливу етапів обробки да-
них зображень у форматі PNG нагадаємо прин-
ципи їх виконання.
Контекстно-залежний алгоритм LZ77 ба-
зується на заміні у вихідному потоці послідов-
ності чергових незакодованих неподільних еле-
ментів (літералів буфера) посиланням на ана-
логічну послідовність літералів, що починаєть-
ся серед закодованих елементів (у словнику), у
вигляді пари чисел <довжина; зміщення від за-
кінчення словника> [4]. За відсутності аналогіч-
ної послідовності літералів у словнику, перший
літерал буфера переноситься у вихідний потік
без змін. Після цього закодовані літерали пе-
реносяться з початку буфера в кінець словника
і кодування продовжується аналогічно аж до
закінчення літералів вхідного потоку. Наприк-
лад, потік кодів байтів пікселів 36 38 35 35 36
38 35 36 36 38 35 38 36 38 35 35 28 в закодова-
ному вигляді можна записати так: 36 38 35
35 <3; 4> 36 <3; 4> 38 <4; 12> 28.
Під час декодування кодів, отриманих за ал-
горитмом LZ77, окремі літерали копіюються у
УСиМ, 2010, № 3 9
вихідний потік без змін. Пари ж <довжина; змі-
щення> декодуються шляхом послідовного ко-
піювання з кінця вихідного потоку за вказаним
зміщенням в кінець вихідного потоку необхід-
ної кількості літералів. Природно, що алгоритм
декодування має розрізняти окремі літерали та
групи <довжина; зміщення>. Згідно з алгори-
тмом LZH, у форматі DEFLATE з цією метою
базові значення довжин замін та окремі літера-
ли кодуються разом. Після базових значень дов-
жин міститься визначена форматом кількість бі-
тів, що разом з базовим значенням визначають
довжину заміни. Зміщення зберігається після
відповідної довжини аналогічно – у вигляді ба-
зового значення та додаткових бітів.
В програмній реалізації для зменшення КС
алгоритму LZ77 [6] забезпечено можливість ви-
ходу зі словника в буфер під час кодування
повторів, запроваджено модифікований алго-
ритм аналізу альтернативних стиснутих блоків
та застосовано аналіз кількостей додаткових
бітів при записі зміщень.
Ідея використання динамічних кодів Хафма-
на [5], що найчастіше застосовуються після ви-
конання алгоритму LZ77 для стиснення літера-
лів і базових значень довжин, а також для від-
окремленого стиснення базових значень змі-
щень у кожному блоці стиснутих даних, поля-
гає у заміні чисел з більшою частотою (тут і
надалі – абсолютною) кодами меншої кількості
бітів, ніж для чисел з меншою частотою.
Згідно теореми Шеннона, елемент si з ймо-
вірністю появи p(si) найвигідніше кодувати –
log p(si) бітами (тут і надалі логарифм береться
за основою 2). Тоді середня довжина коду еле-
мента після застосування контекстно-незалеж-
ного алгоритму (такого, як кодування Хафма-
на) має наближатися до ентропії джерела [3]:
i
ii spspH log . (1)
Як відомо, ентропія джерела зменшується при
збільшенні нерівномірності розподілу ймовір-
ностей між елементами [7].
Алгоритм генерування динамічних кодів Хаф-
мана відомий ще з середини минулого століття
і зменшити його КС не видається можливим.
Можна лише намагатися після мінімізації ент-
ропії окремих рядків розбити зображення на
блоки рядків пікселів з близькими значеннями
ентропії. Це дозволить відокремити і локалізу-
вати рядки з високою ентропією (межі фраг-
ментів зображення або значні перепади яскра-
востей пікселів), підвищивши тим самим нерів-
номірності розподілу в суміжних блоках, і то-
му зменшити загальний КС.
Зменшити ентропію при обробці зображень
у форматі PNG намагаються також за допо-
могою предикторів, що прагнуть, використо-
вуючи значення відомих суміжних елементів,
спрогнозувати значення чергового елемента [3,
7]. Якщо піксел зображення характеризується
декількома компонентами (наприклад, R, G, B),
то предиктор кожної з них прогнозує значення
згідно з відповідними компонентами сусідніх
пікселів. У процесі використання цієї техноло-
гії обчислюють і надалі кодують відхилення
чергової компоненти від прогнозованого пре-
диктором значення [3]. Тому, у загальному ви-
падку, процес застосування предикторів до кож-
ної компоненти піксела у вузлі (i, j) можна за-
писати формулою
ij = Cij – predictij, (2)
де Cij – значення компоненти до застосування
предиктора, ij – значення компоненти після
застосування предиктора, predictij – значення
предиктора, обчисленого для обраної компо-
ненти.
Проаналізуємо розподіл частот значень ij.
Оскільки сусідні піксели зображення мають, як
правило, близькі кольори і тому близькі зна-
чення відповідних компонент, то часто значен-
ня предиктора буде збігатися зі значенням чер-
гового елемента, найчастіше – буде близьким
до цього значення і зрідка – значно відрізня-
тиметься від нього. Тобто більшість значень ij
будуть близькими до нуля. Такий перерозподіл
частот значень (а отже, і ймовірностей) значно
підвищує нерівномірність розподілу і тому змен-
шує ентропію джерела (згідно (1)), а отже, і
довжину закодованої послідовності [7]. Таким
чином, предиктори хоча й не виконують без-
посереднього стиснення даних, але зменшують,
10 УСиМ, 2010, № 3
насамперед, КС контекстно-незалежного алго-
ритму. Приклад перерозподілу частот значень
компонент після застосування предиктора на-
ведено на рис. 1.
Крім цього, окремі предиктори можуть роз-
бити існуючі або згенерувати нові повтори фраг-
ментів зображення і цим вплинути на КС алго-
ритму LZ77, про що буде сказано далі.
0
500
1000
1500
2000
2500
0 50 100 150 200 250
значення
ча
ст
от
и
а
0
4000
8000
12000
16000
20000
-126 -63 0 63 126
значення
ча
ст
от
и
б
Рис. 1. Розподіл частот значень зеленої компоненти даних
перших 64 Кб зображення Lena.bmp: а – до застосуван-
ня предиктора; б – після застосування LeftPredict
У стиснутих блоках формату PNG даним
кожного рядка передує окремий байт, що ви-
значає предиктор, який застосовується до ком-
понент всіх його пікселів [8]. Сьогодні форма-
том передбачено п'ять можливих значень цьо-
го байта, що визначає чотири різні предиктори:
0 – дані рядка не обробляються предикторами;
1 – LeftPredict; 2 – AbovePredict; 3 – AveragePre-
dict; 4 – PaethPredict. Для зручності опису цих
предикторів введемо позначення яскравостей су-
міжних елементів для елемента X згідно схеми:
LeftAbove Above
Left X
Тоді предиктори формату PNG, згідно стан-
дарту [1], мовою C запишемо так:
char LeftPredict(char Left, char Above,
char LeftAbove)
{return Left;}
char AbovePredict(char Left, char Above,
char LeftAbove)
{return Above;}
char AveragePredict(char Left, char
Above, char LeftAbove)
{return (Left+Above)/2;}
char PaethPredict(char Left, char
Above, char LeftAbove)
{int pp=Left+Above-LeftAbove;
int pa,pb,pc;
pa=abs(pp-Left);
pb=abs(pp-Above);
pc=abs(pp-LeftAbove);
if (pa<=pb && pa<=pc) return Left;
else if (pb<=pc) return Above;
else return LeftAbove;}.
Відхилення між значеннями сусідніх елеме-
нтів в зображеннях найчастіше зумовлені дво-
ма причинами: «сильними» коливаннями, обу-
мовленими зображеними об'єктами – трендом,
і слабкими фоновими коливаннями – шумом
[3]. Перші три згаданих предиктори описують
шумову модель і належать до лінійних статич-
них предикторів. Останній поєднує в собі тре-
ндову та шумову моделі і належить до нелі-
нійних статичних предикторів.
Проблема вибору таких статичних предик-
торів для кожного рядка зображення, що до-
зволяють зменшити загальний КС зображення,
залишалася невирішеною досі [8, с. 317]. Ниж-
че подамо способи її вирішення за допомогою
ентропії.
Вплив предикторів та їх комбінацій на
стиснення зображень у форматі PNG. Оцін-
ка ентропії рядків пікселів
Алгоритми, що використовуються у форматі
PNG для стиснення даних, орієнтовані на змен-
шення різних видів надлишковості: якщо LZ77
усуває надлишковості між однаковими фрагмен-
тами даних, то кодування Хафмана орієнтова-
не на зменшення надлишковостей між перева-
жаючими елементами розподілів. Алгоритм
LZ77 у цьому форматі може стискувати дані
максимум у 129, а кодування Хафмана – мак-
симум у вісім разів. Саме тому алгоритм LZ77 і
УСиМ, 2010, № 3 11
використовується у форматі PNG, хоча він і
зменшує нерівномірність розподілу між окре-
мими елементами і може зменшити ефектив-
ність кодування Хафмана. З іншого боку, у при-
родних зображеннях яскравості компонент су-
сідніх пікселів, як правило, близькі, але не од-
накові. Це робить малоефективним викорис-
тання для них алгоритму LZ77, і тому кодуван-
ня Хафмана у цьому випадку забезпечує хоча б
задовільні КС. Ключову роль в процесі стис-
нення різних зображень і навіть окремих їх фраг-
ментів можуть відігравати як алгоритм LZ77,
так і кодування Хафмана. Використання різних
предикторів (а також відмова від їх застосу-
вання) формату PNG неоднаково впливає на
КС цих алгоритмів. Відповідно для кожного
рядка зображення слід обирати той предиктор,
який дозволить підсилити дію ключового ал-
горитму стиснення чергового фрагменту і до-
поможе тим самим забезпечити найменший за-
гальний КС.
Дослідимо вплив різних варіантів предикто-
рів на прикладі стиснення восьми різнотипних
24-бітних природних зображень з стандартного
набору файлів Archive Comparison Test (ACT) у
форматі PNG, характеристики яких наведено в
табл. 1. Завантажити TIFF-версії файлів зобра-
жень цього набору можна, наприклад, з http: //
compression.ca/act/act-files.html. Тестування про-
водилося за допомогою програми CD [7], у яку,
крім вказаних раніше, було внесено такі мо-
дифікації: розмір блоків даних, збільшений до
64 Кб, відкинуто допоміжні текстові блоки та
запроваджено поєднання рядків у блоки, що
описано далі. Результати тестування наведено
в табл. 2, 3. Швидкість декодування зображень
майже не залежить від застосованих предикто-
рів або їх комбінацій і складає в середньому
для дискретно-тонових зображень 910 Кб/c, для
штучних з перешкодами – 545 Кб/с, а для не-
перервно-тонових – 330 Кб/с. Тому середній
час декодування всіх зображень набору скла-
дає лише 25 с.
Стиснення зображень у форматі PNG без за-
стосування предикторів відбувається шляхом
повторень та за наявності нерівномірності роз-
поділу значень яскравості пікселів. Але в при-
родних зображеннях аналогічні фрагменти та
однакові значення яскравості компонент трап-
ляються порівняно рідко, тому й таке стиснен-
ня призводить до високих КС (див. рис. 1,а та
варіант Без предикторів у табл. 2, 3). Стиснен-
ня зображень без застосування предикторів
ефективне, насамперед, для дискретно-тонових
штучних зображень з високою роздільною зда-
тністю. Це стиснення виконується найшвидше,
оскільки не вимагає виконання додаткових об-
числень значень предикторів.
Т а б л и ц я 1. Характеристика зображень набору ACT
№
фай-
ла
Назва
файла
Розмір,
Кб
Розміри
зобра
ження,
пікселів
Унікальних
кольорів
серед піксе-
лів, %
Особливості
1. Clegg.bmp 2101 814x880 17,83
Неперервно-тонове,
штучне, з шумами,
декілька великих
об'єктів
2. Frymire.bmp 3622
1118x11
05
0,29
Дискретно-тонове,
штучне, один вели-
кий об'єкт
3. Lena.bmp 769 512x512 56,56
Неперервно-тонове,
природне, декілька
великих об'єктів
4.
Mon-
arch.bmp
1153 768x512 19,99
Неперервно-тонове,
природне, один ве-
ликий і багато ма-
лих об'єктів
5. Peppers.bmp 769 512x512 42,47
Неперервно-тонове,
природне, декілька
великих об'єктів
6. Sail.bmp 1153 768x512 19,26
Неперервно-тонове,
природне, багато
середніх об'єктів
7. Serrano.bmp 1464 629x794 0,26
Дискретно-тонове,
штучне, один вели-
кий фрагментова-
ний об'єкт
8. Tulips.bmp 1153 768x512 30,07
Неперервно-тонове,
природне, декілька
великих об'єктів
Предиктор LeftPredict генерує горизонтальні
прирости яскравості між компонентами сусідніх
пікселів. Однакові прирости яскравості трапля-
ються в природних зображеннях, як правило, ча-
стіше, ніж однакові фрагменти, що покращує КС
алгоритму LZ77. Крім цього, застосування пре-
диктора LeftPredict підвищує нерівномірність
розподілу навколо нуля (рис. 1,б), зменшуючи
тим самим КС кодування Хафмана. Саме тому
середній КС зображень набору ACT із застосу-
ванням LeftPredict зменшився порівняно з варіан-
том без застосування предикторів на 11,72%. Але
12 УСиМ, 2010, № 3
зазначимо, що при застосуванні LeftPredict мож-
ливе зменшення довжини повторень, що були
між фрагментами оригіналу зображення, тому
можливе і підвищення загального КС (дані зо-
бражень №№ 2, 7 в рядку LeftPredict у табл. 2).
Отже, однозначно стверджувати, що стиснення з
використанням LeftPredict ефективніше від сти-
снення без застосування предикторів, неможли-
во. Середня тривалість компресії файлів набору
ACT цим способом перевищує тривалість коду-
вання без предикторів на 14,46%, оскільки за-
стосування предикторів потребує розрахунку їх
значень і породжує більше коротких збігів по-
слідовностей, що сповільнює формування роз-
кладу LZ77.
Т а б л и ц я 2. Розміри файлів зображень набору ACT у фор-
маті PNG після застосування різних предикто-
рів та їх комбінацій, Кб
Номер файла
Назва варіанта
1 2 3 4 5 6 7 8
Разом
Середній
КС, %
Без предикторів 502 248 702 812 650 894 104 958 4870 55,59
LeftPredict 447 331 502 645 441 793 135 738 4032 43,87
AbovePredict 481 349 471 645 454 808 143 710 4061 43,77
AveragePredict 1124 515 468 610 422 763 215 683 4800 47,06
PaethPredict 440 354 471 609 415 780 145 667 3881 41,77
Комбінування 1 441 347 476 705 514 838 146 889 4356 47,53
Комбінування 2 440 353 687 645 441 797 147 711 4221 46,77
Комбінування 3 440 352 463 606 414 772 147 667 3861 41,51
Комбінування 4 439 348 463 605 414 772 146 666 3853 41,46
Комбінування 5 463 311 463 607 415 763 132 669 3823 41,33
Комбінування 6 439 339 463 605 414 763 147 666 3836 41,34
Комбінування 4, 5
з аналізом блоків 439 243 463 600 414 757 104 663 3683 40,49
Аналогічно впливає на стиснення зображень
і застосування предиктора RightPredict, який ге-
нерує вертикальні прирости яскравості компо-
нент суміжних пікселів. Різні зображення ма-
ють різний рівень відмінностей пікселів по го-
ризонталі та вертикалі. Саме тому КС в рядках
LeftPredict та RightPredict табл. 2 різні. Саме
цим пояснюється різниця в часі кодування на
34,31% зображення № 1 для даних рядків у
табл. 3, оскільки це зображення містить суттє-
во меншу кількість однакових приростів яскра-
вості компонент пікселів у вертикальному на-
прямку стосовно горизонтального, що приско-
рює формування розкладу LZ77, але й підви-
щує КС. Крім цього, гірший КС з використан-
ням предиктора RightPredict стосовно LeftPre-
dict для більшої частини зображень набору по-
яснюється тим, що однакові прирости по вер-
тикалі трапляються, як правило, в сусідніх ряд-
ках. Зміщення ж між сусідніми пікселами по
вертикалі при обробці даних у форматі PNG до-
рівнює довжині рядка. Тобто вони значно біль-
ші від зміщень між сусідніми пікселами по го-
ризонталі і тому кодуються значно більшою кі-
лькістю додаткових біт.
Т а б л и ц я 3. Час кодування файлів зображень набору ACT у
форматі PNG варіантами програми з застосу-
вання різних предикторів та їх комбінацій (на
комп'ютері з частотою процесора 300 МГц), с
Номер файла
Назва варіанта
1 2 3 4 5 6 7 8
Разом
Без предикто-
рів 9,06 13,51 4,66 6,54 4,62 6,97 5,55 6,92 57,83
LeftPredict 12,62 13,84 4,89 8,40 5,61 7,20 5,88 7,75 66,19
AbovePredict 8,29 14,77 4,95 8,41 5,22 7,03 5,99 8,02 62,68
AveragePredict 17,30 15,93 5,05 9,61 5,93 7,30 6,42 8,46 76,00
PaethPredict 11,37 15,71 5,21 9,56 5,93 7,69 6,48 8,84 70,79
Комбінування 1 14,50 20,32 6,43 10,71 6,92 9,45 8,35 9,67 86,35
Комбінування 2 15,16 22,52 6,81 10,66 7,03 9,34 9,17 10,05 90,74
Комбінування 3 14,83 21,04 6,42 11,37 7,03 9,34 8,63 10,44 89,10
Комбінування 4 14,61 21,04 6,54 11,70 7,20 9,45 8,74 10,55 89,83
Комбінування 5 16,48 24,06 7,25 12,69 7,97 10,55 9,99 11,59 100,58
Комбінування 6 17,08 24,99 7,69 13,13 8,35 11,10 10,33 12,08 104,75
Комбінування
4, 5 з аналізом
блоків 49,21 67,89 20,04 42,35 25,93 30,10 28,35 37,35 301,22
Предиктор AveragePredict врівноважує вплив
сусідніх пікселів по горизонталі та вертикалі.
Він добре (відносно розглянутих варіантів) про-
гнозує яскравість компонент пікселів для зо-
бражень великих та розмитих природних об'єк-
тів, хоча й дуже чутливий до різких перепадів
кольорів (наприклад, ліній променів світла у зо-
браженні № 1) та чітких меж об'єктів штучних
зображень. Сповільнення кодування зображень з
використанням Average Predict пояснюється як
необхідністю виконання операції ділення для
розрахунку значення предиктора кожної компо-
ненти всіх пікселів, так і низькою ефективніс-
тю розкладу LZ77, що породжує багато елемен-
тів для кодування Хафмана.
Найкращі в середньому передбачення значень
яскравостей компонент пікселів генерує предик-
тор PaethPredict, який прогнозує значення у на-
прямку найменшого приросту. Цей предиктор
на дискретно-тонових зображеннях поступаєть-
УСиМ, 2010, № 3 13
ся лише предиктору LeftPredict та варіанту без
предикторів, а на неперервно-тонових зображен-
нях забезпечує КС, близькі до предиктора Ave-
ragePredict. Але, по-перше, нелінійний предик-
тор PaethPredict обчислюється найдовше з усіх
розглянутих предикторів, що негативно впли-
ває як на час кодування, так і на час декоду-
вання, і, по-друге, цей предиктор, як і попере-
дній, часто зменшує довжини повторень, що
були між фрагментами оригіналу зображення.
Як бачимо, застосування нелінійних комбі-
нованих предикторів в цілому ефективніше від
лінійних шумових на понад 2%, хоча й потре-
бує більшої кількості обчислень. З іншого бо-
ку, не існує універсального предиктора, засто-
сування якого сприяло б найкращому стиснен-
ню всіх типів зображень. Навіть для сусідніх
фрагментів зображень оптимальними можуть
виявитися різні предиктори. Тому для досягнен-
ня кращих коефіцієнтів стиснення необхідно ви-
користовувати комбінації предикторів. Зрозу-
міло, що комбінування предикторів сповільнює
кодування, але дає змогу не лише зменшити роз-
міри файлів зображень, але й завдяки цьому при-
скорити декодування.
За стандартом PNG [1] рекомендується оби-
рати той предиктор для кожного рядка, засто-
сування якого зумовлює мінімальну суму зна-
чень знакових байт (з діапазону [–128; 127]).
Справді, зменшення загальної суми значень ряд-
ка після використання предиктора свідчить про
наближення розподілу частот до симетрично-
го, але чи вказує цей критерій на зменшення
ентропії джерела? Результати застосування та-
кого способу вибору предиктора для кожного
рядка дають негативну відповідь на це запи-
тання (див. рядок Комбінування 1 в табл. 2).
Інший спосіб визначення оптимального пре-
диктора для кожного рядка полягає у пошуку
найбільшої кількості повторень однакових зна-
чень, що йдуть підряд (запропонований в [8,
с. 317]). Справді, повторення значень сприяє по-
кращенню показників стиснення алгоритмом
LZ77, але цей спосіб не враховує можливості
повторень груп різних байт, що також покра-
щують стиснення алгоритмом LZ77, та змін ен-
тропії джерела. Результати застосування тако-
го способу вибору оптимального предиктора
кожного рядка наведено у табл. 2, 3 в рядку
Комбінування 2.
В [3, 9] запропоновано обирати той предик-
тор, застосування якого зумовлює мінімальну
суму модулів значень знакових байтів (з діапа-
зону [–128; 127]). Зменшення загальної суми мо-
дулів значень рядка після використання пре-
диктора свідчить про збільшення нерівномір-
ності розподілу частот навколо нуля та покра-
щує результати застосування контекстно-неза-
лежного алгоритму. Результати застосування та-
кого способу вибору оптимального предиктора
кожного рядка наведено у табл. 2, 3 в рядку
Комбінування 3. Як видно з таблиць, такий спо-
сіб вибору предиктора рядка покращує середній
КС стосовно предиктора Піфа на 0,26%, при-
чому зменшення розмірів файлів спостеріга-
ється майже для всіх зображень, хоча він і спо-
вільнює кодування на 22%.
Для розробки ефективніших способів вибо-
ру предикторів рядків проаналізуємо вплив різ-
них предикторів на продуктивність базових ал-
горитмів стиснення формату PNG. Алгоритм
LZ77 досягає кращих КС зображень без засто-
сування предикторів або після дії предикторів
LeftPredict чи RightPredict. Кодування Хафма-
на найкраще стискає розподіли зображень піс-
ля дії предикторів (особливо після AveragePre-
dict або PaethPredict), оскільки вони підвищу-
ють нерівномірність розподілу. Обрати найкра-
щий з трьох варіантів використання предикто-
рів стосовно алгоритму LZ77 для кожного ряд-
ка пікселів неможливо без виконання трьох по-
передніх розкладів зображення з застосуванням
кожного з цих варіантів, оскільки однакові фраг-
менти даних можуть траплятися в різних ряд-
ках. Найкращий предиктор стосовно розкладу
Хафмана для кожного рядка пікселів оберемо з
умови мінімуму ентропії серед результатів їх
дій, до якої прямує середня довжина коду цьо-
го розкладу. Нехай кожен з елементів Si зустрі-
чається Ni разів в рядку довжиною
i
iNN .
Тоді p(si) = Ni /N і загальна довжина закодова-
них даних, враховуючи (1), наближається до
значення
14 УСиМ, 2010, № 3
i
ii NNNNHN loglog . (3)
Мовою C підпрограма для наближеного об-
числення ентропійного розміру блоку кодів
Хафмана за частотами елементів згідно (3) з
визначенням прогнозованого КС має вигляд:
double sizeEntropiCode(long * freq,
short countAllFreq, double &entropiKC)
{// freq - масив частот елементів
// countAllFreq – загальна кількість
частот в масиві
double size=0; long n=0;
for (long i=0; i<countAllFreq; i++)
{n+=freq[i]; // сумуємо частоти
if (freq[i]>1) // для існування log
size+=freq[i]*log(freq[i]); }
if (n) {size=(n*log(n)-size)/log(2);
entropiKC=size/(8*n); }
else {size=0; entropiKC=1; }
return size; } .
А фрагмент програми для визначення номе-
ра предиктора, що породжує дані з найменшою
ентропією елементів записується так:
for (i=0; i<=4; ++i) // цикл по преди-
кторах
{memset(freq, 0, sizeof(freq));
for (j=0; j<row_width; ++j) // цикл
по елементах рядка
freq[buffers[i][j]]++; // накопи-
чення частот елементів
size=sizeEntropiCode(freq, 256,
entropiKC);
if (size<minSize)
{predict1=i; // запам'ятали номер
предиктора
minSize=size;
entropiKC1=entropiKC; }}
KC1=entropiKC1; .
Середній КС зображень набору ACT з засто-
суванням ентропійного способу вибору преди-
кторів рядків зменшився в порівнянні з спосо-
бом вибору предикторів на основі найменшої
суми модулів значень знакових байтів на 0,05%
(рядок Комбінування 4 з табл. 2, 3), причому роз-
мір стиснутих файлів не збільшився для жодно-
го зображення, а час стиснення збільшився ли-
ше на 0,82%. Використання цього способу ефек-
тивне, насамперед, для природних зображень де-
кількох великих об'єктів. У фрагментах зобра-
жень, в яких ентропійний спосіб вибору пре-
дикторів рядків є найефективнішим, короткі за-
міни (3–4 літерали), як правило, не застосову-
ються. Оптимальними предикторами при тако-
му способі вибору найчастіше є AveragePredict
або PaethPredict.
Крім ентропії окремих елементів, для кож-
ного рядка пікселів слід оцінити також КС піс-
ля виконання коротких замін. Адже короткі за-
міни можуть суттєво збільшити частоти довжин
замін, що їм відповідають, та зменшити часто-
ти окремих літералів. А це, в свою чергу, при-
зводить до збільшення нерівномірності розпо-
ділу і, відповідно, до зменшення КС. Виконува-
ти попереднє стиснення LZ77 для результатів
дії всіх предикторів рядків недоцільно, оскіль-
ки це спричинює різке сповільнення процесу
кодування. Оцінювання КС рядка пікселів від-
бувалося після застосування триелементних за-
мін за допомогою хеш-таблиці по чотирьох ос-
танніх бітах трьох суміжних елементів, в якій
зберігаються абсолютні позиції останніх вхо-
джень подібних груп. З використанням значен-
ня цієї таблиці імітується розклад LZ77 з підра-
хунком частот літералів, триелементних замін та
їх зміщень і додаткових бітів, після чого визна-
чається загальний КС рядка. Мовою C фраг-
мент програми для визначення номера предик-
тора, що породжує дані з найменшим КС після
коротких замін записується, наприклад, так:
for (i=0; ii<=4; ++i) // цикл по пре-
дикторах
{memset(freq, 0, sizeof(freq));
// частоти літералів/довжин
memset(freqD, 0, sizeof(freqD));
// частоти баз зміщень
memset(hash, 0, sizeof(hash));
// елементи хеш-таблиці
plusBit=0; // додаткові біти зміщень
j=0; // позиція обробки рядка після
дії предиктора i
while (j<row_width-2)
if (hash[((buffers[i][j] & 15)<<8)+
((buffers[i][j+1] & 15)<<4)+
(buffers[i][j+2] & 15)])
{// подібні три байта вже були в рядку
freq[257]++; // частота триелементної
заміни
offset=j-hash[((buffers[i][j]&15)<<8)+
((buffers[i][j+1]&15)<<4)+(buffers[i][j+
+2]&15)]+1;
УСиМ, 2010, № 3 15
// збільшуємо частоту бази зміщення
freqD[codesDistance[offset]]++;
// накопичуємо додаткові біти зміщення
plusBit+=extrasDistance[codesDistan-
ce[offset]];
// дані оброблених триелементних груп
// записуємо в хеш-таблицю
hash[((buffers[i][j] & 15)<<8)+
((buffers[i][j+1] & 15)<<4)+(buf-
fers[i][j+2] & 15)]=j+1;
if (j+1<row_width-2)
hash[((buffers[i][j+1] & 15)<<8)+
((buffers[i][j+2] & 15)<<4)+(buf-
fers[i][j+3] & 15)]=j+2;
if (j+2<row_width-2)
hash[((buffers[i][j+2] & 15)<<8)+
((buffers[i][j+3] & 15)<<4)+(buf-
fers[i][j+4] & 15)]=j+3;
j+=3; }
else // подібна група відсутня – зано-
симо літерал
{freq[buffers[i][j]]++;
hash[((buffers[i][j] & 15)<<8)+
((buffers[i][j+1] & 15)<<4)+(buf-
fers[i][j+2] & 15)]=j+1;
j++; }
for (; j<row_width ; ++j) //останні по-
зиції рядка
freq[buffers[i][j]]++;
size=sizeEntropiCode(freq, 256, en-
tropiKC)+
sizeEntropiCode(freqD, 30, en-
tropiKCD)+plusBit;
if (size<minSize)
{predict2=i; // запам'ятали номер
предиктора
minSize=size; entropiKC2=entropiKC; }}
KC2=(double)minSize/(8*row_width); .
Середній КС зображень набору ACT з засто-
суванням ентропійного способу вибору предик-
торів рядків після імітації коротких замін LZ77
зменшився порівняно з середнім КС ентропій-
ного поелементного предиктора на 0,13% (ря-
док Комбінування 5 з табл. 2, 3), хоча покра-
щення спостерігається лише на дискретно-то-
нових зображеннях та неперервно-тонових зо-
браженнях, для яких короткі заміни ефективні.
Це й не дивно, адже розрахунок ентропійного
КС після імітації коротких замін найкраще з
розглянутих варіантів моделює стиснення у фор-
маті PNG. Середня тривалість компресії фай-
лів набору ACT внаслідок імітації коротких за-
мін під час вибору предикторів рядків зросла
на 11,96%. Оптимальними предикторами при
виборі за мінімальним ентропійним КС після за-
стосування коротких замін LZ77 найчастіше ви-
являються LeftPredict або RightPredict. Викорис-
тання цього способу ефективне, насамперед, для
природних зображень з багатьма об'єктами і для
штучних зображень.
Для різних зображень і навіть для різних
фрагментів одного зображення короткі заміни
LZ77 можуть виявитися як ефективними (тобто
кількість біт для зберігання заміни є не біль-
шою від кількості біт для зберігання окремих
елементів), так і неефективними, отже передба-
чити необхідність імітації коротких замін не-
можливо. Тому для кожного рядка пікселів обе-
ремо предиктор, що забезпечує прогнозований
мінімальний КС. Отримаємо цей КС за резуль-
татами порівняння мінімального поелементно-
го КС (в попередніх фрагментах програм – КС1)
та мінімального КС (КС2) після застосування
коротких замін LZ77 стосовно результатів дії
всіх предикторів, оскільки ці варіанти вибору
предикторів забезпечують в середньому найкра-
щі результати. Враховуючи те, що довгі ефек-
тивні заміни частково враховані в КС2 і не вра-
ховані в КС1, обирати предиктор, що забезпе-
чує КС2, будемо лише тоді, коли КС2 менший
за КС1 більше, ніж на 4%. Інакше обиратиме-
мо предиктор, що забезпечує КС1:
If (KC2<KC1-0.04) currentPredict=
=predict2;
else currentPredict=predict1; .
Такий комбінований спосіб вибору предик-
торів рядків хоча й поступається за середнім
КС на 0,01% ентропійному способу після ко-
ротких замін LZ77 і формується на 4,15% по-
вільніше від нього (рядок Комбінування 6 у
табл. 2, 3), але забезпечує не гірші КС за всіма
зображеннями набору стосовно способу вибо-
ру предикторів Комбінування 3 на основі най-
меншої суми модулів значень знакових байтів.
Розбиття зображень на блоки однорідних
рядків за допомогою ентропії
Звичайно, кожен рядок зображення можна
розмістити в окремому стиснутому блоці фор-
16 УСиМ, 2010, № 3
мату PNG. Але загалом таке стиснення не буде
найефективнішим, оскільки в заголовку кожного
стиснутого блоку динамічних кодів Хафмана
міститься опис довжин кодів його розподілів лі-
тералів/довжин та зміщень, який може займати
понад 1500 бітів, а такі витрати неприпустимі
для кожного рядка. З іншого боку, поєднання у
стиснутих блоках даних довільних суміжних
рядків в цілому зменшує нерівномірність роз-
поділу і може негативно вплинути на загальний
КС. Тому пропонується в процесі попереднього
аналізу зображень перед стисненням у форматі
PNG поєднати суміжні рядки з близькими про-
гнозованими ентропійними КС розподілів у бло-
ки. Кожен однорідний блок рядків в процесі
подальшого стиснення може належати одному,
а може бути й розбитим на кілька стиснутих
блоків, адже розмір стиснутого блоку, як пра-
вило, не перевищує 64 Кб. Але різні блоки ря-
дків мають обов'язково належати різним стис-
нутим блокам, оскільки вони мають різні ент-
ропійні КС (в попередніх фрагментах програм
– entropiKC1), а отже, і різні нерівномірності
розподілів. Зрозуміло, що поєднувати між со-
бою суміжні блоки рядків доцільно лише тоді,
коли прогнозоване збільшення довжини кодів
від їх поєднання не перевищує розміру заголо-
вка нового стиснутого блоку (тобто 1500).
Розрахуємо прогнозоване збільшення довжи-
ни кодів від поєднання двох суміжних блоків.
Нехай перший блок рядків містить l1 елементів
з прогнозованою ентропією (середньою довжи-
ною коду) e1, а другий – l2 елементів з ентропі-
єю e2. Тоді прогнозована довжина кодів пер-
шого блоку становить l1 e1, а другого – l2 e2.
Внаслідок поєднання блоків рядків з подібни-
ми нерівномірностями розподілу (див. рис. 1,б)
ентропія поєднання не може перевищити мак-
симуму ентропій поєднаних частин, отже про-
гнозована довжина коду поєднання не пере-
вищує (l1 + l2) max (e1 ; e2). Тому прогнозова-
не збільшення довжини коду внаслідок поєд-
нання двох суміжних блоків не перевищує
.
,
,
;max
21112
21221
22112121
'
eelee
eelee
eleleelllk
(4)
На практиці прогнозоване збільшення дов-
жини коду від поєднання залежить не лише від
кількості елементів вхідного блоку з меншою
ентропією, а й від кількості елементів іншого
вхідного блоку (наприклад, короткий перший
вхідний блок з високою ентропією не може
максимально збільшити ентропію другого дов-
гого вхідного блоку), тому розраховувати його
доцільно за формулою, що враховує відно-
шення розмірів вхідних блоків:
1 2 2 1 2 1 2''
1 2 1 2 1 1 2
log 1 ,
log 1 ,k
e e l l l l l
l
e e l l l l l
. (5)
Ентропійне кодування елементів розподілів
виконується у форматі PNG після формування
розкладу LZ77. Визначити наперед кількість еле-
ментів такого розкладу неможливо, але ця кіль-
кість елементів перебуває у монотонно не спад-
ній залежності від ентропії: чим менша ентро-
пія, тим більша ймовірність існування повторень
значень яскравості компонентів і, отже, тим мен-
ше елементів буде містити розклад LZ77. Про-
гнозована кількість елементів рядків обчислю-
валася після розкладу LZ77 як добуток почат-
кової кількості елементів рядків та мінімуму з
одиниці і ентропії, збільшеної у 4/3 рази (вважа-
ли, що рядки з ентропією понад 0,75 не підда-
ються стисненню LZ77). Алгоритм формування
блоків однорідних рядків представимо покроково:
1. Визначити для кожного рядка пікселів зо-
браження предиктор, що породжує коди з мі-
німальною ентропією згідно (3) та прогнозова-
ну кількість елементів після розкладу LZ77, як
описано раніше. Віднести кожен рядок до окре-
мого блоку рядків.
2. Розрахувати для всіх пар суміжних блоків
прогнозоване збільшення довжини коду вна-
слідок їх можливого поєднання за допомогою
(5), враховуючи максимум 64 тис. елементів з
кожного блоку. Визначити пару суміжних бло-
ків, що породжує найменше таке збільшення
довжини коду.
3. Якщо залишився лише один блок рядків
або найменше збільшення довжини коду пере-
вищує 1500 бітів, то завершити виконання ал-
УСиМ, 2010, № 3 17
горитму. Інакше – поєднати пару суміжних бло-
ків, що породжує це збільшення, і повернутися
до кроку 2.
Саме цей алгоритм формування блоків од-
норідних рядків за допомогою ентропії реалі-
зовано в модифікаціях програми, використаної
для тестування. Він дозволяє зменшити розмі-
ри більшості стиснутих зображень у форматі
PNG мінімум на 1 Кб.
Досягнути менших КС зображень можливо,
якщо: розбити їх на менші блоки однорідних
рядків згідно (4); для кожного блоку однорід-
них рядків обрати предиктори з умови мініму-
му розрахованих за допомогою (3) КС серед
п'яти варіантів компресії (без застосування пре-
дикторів, з використанням LeftPredict, з засто-
суванням RightPredict, з використанням ентро-
пійного поелементного способу вибору преди-
кторів та з застосуванням ентропійного спосо-
бу вибору предикторів після здійснення корот-
ких замін LZ77); укрупнити блоки однорідних
рядків, використовуючи (5). При цьому слід вра-
ховувати також відхилення від варіантів комп-
ресії, що забезпечують мінімальний КС для по-
переднього і наступного однорідних блоків ряд-
ків, адже зміна варіантів компресії між сусід-
німи блоками призводить до виникнення ново-
го стиснутого блоку (а, отже, і його заголовка)
і зменшує ймовірність повторень фрагментів
даних для алгоритму LZ77. Тобто автори про-
понують в процесі аналізу зображення оби-
рати предиктори, які мінімізують коефіці-
єнт стиснення кожного блоку однорідних ряд-
ків, а не лише ентропію компонент пікселів ок-
ремих рядків. Результати застосування такого
способу стиснення наведено у рядках Комбіну-
вання 4, 5 з аналізом блоків табл. 2, 3. Описа-
ний спосіб стиснення зображень, що обирає мі-
німальний КС для кожного блоку однорідних
рядків, хоча й виконується в середньому май-
же втричі повільніше від ентропійного варіан-
ту і майже у шість разів повільніше від стис-
нення без предикторів, (оскільки формує п'ять
додаткових розкладів LZ77), зате забезпечує
найменші КС для всіх зображень набору АСТ.
Висновки. Для підвищення ефективності
стиснення даних у форматах, що послідовно
використовують алгоритми декількох методів,
доцільно враховувати взаємний вплив цих ал-
горитмів. Під час попередньої обробки даних
перед стисненням у таких форматах для розра-
хунку параметрів компресії бажано опрацьову-
вати всі види надлишковостей, що обробляють-
ся їх окремими алгоритмами, а також розбива-
ти дані на однорідні блоки.
Для кожного рядка пікселів зображення пре-
диктори слід обирати залежно від обмежень на
час компресії: у випадку найшвидшого стиснен-
ня доцільно використати нелінійний предиктор
PaethPredict для всіх рядків; під час стандарт-
ного стиснення варто скористатися ентропій-
ним способом вибору предикторів (Комбінуван-
ня 4); для повільного максимального стиснен-
ня слід застосувати вибір предикторів на осно-
ві аналізу КС п'яти варіантів компресії кожно-
го блоку однорідних рядків.
Запропонований спосіб попередньої оброб-
ки з аналізом даних дозволяє отримати наймен-
ші КС зображень у форматі PNG, насамперед,
шляхом поділу зображень на блоки рядків пік-
селів з близькими значеннями ентропії та ви-
бору для кожного блоку рядків способу стис-
нення, що забезпечує для нього найменший КС.
Описані способи вибору предикторів рядків
та розбиття зображення на блоки однорідних
рядків за допомогою ентропії не потребують мо-
дифікації декодера чи програм перегляду зо-
бражень і за умови зменшення розмірів файлів
лише прискорюють їх роботу. Саме тому вони
можуть бути ефективно застосовані у процесі
компактного збереження даних у форматах, що
використовують різні предиктори для окремих
рядків пікселів, таких, як формат PNG.
1. Boutell T. PNG Specification, Vers. 1.0, PNG Develop-
ment Group, October, 1996.
2. L. Peter Deutsch DEFLATE Compressed Data Format
Specification, Vers. 1.3, RFC 1951, 1996.
3. Методы сжатия данных. Устройство архиваторов,
сжатие изображений и видео / Д. Ватолин, А. Ратуш-
няк, М. Смирнов и др. – М.: ДИАЛОГ-МИФИ, 2003. –
384 с.
4. Ziv J., Lempel A. A universal algorithm for sequential
data compression // IEEE Transactions on Inform. The-
ory. – May 1977. – 23, N 3. – P. 337–343.
18 УСиМ, 2010, № 3
5. Huffman D. A Method for the Construction of Mini-
mum Redundancy Codes // Proc. of the IRE. – 40,
N 9. – P. 1098–1101.
6. Бомба А.Я., Шпортько О.В. Алгоритм оптимізації
вибору фільтра для попереднього опрацювання зо-
бражень перед стисненням на основі методу «пре-
диктор – коректор» // Вісн. Нац. ун-ту «Львівська
політехніка». (Серія: Інформаційні системи та ме-
режі). – 2008. – № 621. – С. 46–54.
7. Бредихин Д.Ю. Сжатие графики без потерь каче-
ства. – http://www.compression.ru/download/articles/
i_lless/bredikhin_2004_lossless_image_compression_
doc.rar
8. Миано Дж. Форматы и алгоритмы сжатия изобра-
жений в действии: Учеб. пособие. – М.: Триумф,
2003. – 336 с.
9. Шпортько О.В. Використання альтернативних бло-
ків стиснутих даних у форматі PNG // Комп'ютерні
науки та інформаційні технології: Матеріали третьої
Міжнар. конф. CSIT'2008. – Львів: Вежа і Ко, 2008. –
С. 149–153.
Поступила 10.09.2009
Тел. для справок: (0362) 26-04-44, 64-72-87, 22-60-51 (Ровно)
E-mail: abomba@ukr.net, chportko@yandex.ru,
chportko@ukr.net
© А.Я. Бомба, А.В. Шпортько, 2010
А.Я. Бомба, О. В. Шпортько
Энтропийные способы выбора предиктора для строки пикселей в формате PNG
Введение. Сегодня формат PNG [1] – один из основных
для сохранения изображений без потерь. В Интернете,
например, насчитывается свыше 15 млн страниц, содер-
жащих изображения в этом формате. Популярности фор-
мата PNG способствуют, в первую очередь, приемлемые
коэффициенты сжатия (КС) – отношение размера сжа-
тых к несжатым данным и высокая скорость декодиро-
вания. Проблема уменьшения размеров файлов изобра-
жений в этом формате актуальна и будет оставаться та-
кой в ближайшем будущем, поскольку даже частичное
ее решение дает возможность ускорить загрузку PNG-
файлов из сети и повысить эффективность использова-
ния дискового пространства.
База исследования. Особенности этапов обработ-
ки данных изображений в формате PNG
Пикселы изображения записываются в PNG-файлы
чаще всего по строкам сверху вниз, а в каждой строке –
последовательно слева направо (как символы в текстах),
формируя тем самым входной поток. Перед кодирова-
нием эти пикселы могут быть предварительно обрабо-
таны предикторами. В PNG-файлах, используемых сего-
дня, сжатые данные сохраняются в раздельных блоках
согласно формату словарного сжатия DEFLATE [2]. В
соответствии с этим форматом, в сжатых блоках содер-
жатся результаты применения к входному потоку алго-
ритма LZH [3], согласно с которым результаты контек-
стно-зависимого словарного алгоритма LZ77 [4] сжима-
ются контекстно-независимыми кодами Хаффмана [5].
Для исследования взаимовлияния этапов обработки дан-
ных изображений в формате PNG напомним принципы
их выполнения.
Контекстно-зависимый алгоритм LZ77 базируется
на замене в выходном потоке последовательности оче-
Ключевые слова: сжатие изображений без потерь, статические
предикторы, формат графических файлов PNG.
редных незакодированных неделимых элементов (лите-
ралов буфера) ссылкой на аналогичную последователь-
ность литералов, начинающихся среди закодированных
элементов (в словаре), в виде пары чисел <длина; сме-
щение от окончания словаря> [4]. В случае отсутствия
аналогичной последовательности литералов в словаре,
первый литерал буфера переносится в выходной поток
без изменений. После этого закодированные литералы
переносятся с начала буфера в конец словаря и кодиро-
вание продолжается аналогично вплоть до окончания
литералов входного потока. Например, поток кодов бай-
тов пикселов 36 38 35 35 36 38 35 36 36 38 35 38 36 38 35
35 28 в закодированном виде можно записать так: 36 38
35 35 <3; 4> 36 <3; 4> 38 <4; 12> 28.
В процессе декодирования кодов, полученных по ал-
горитму LZ77, отдельные литералы копируются в выход-
ной поток без изменений. Пары же <длина; смещения>
декодируются путем последовательного копирования с
конца выходного потока по указанному смещению в ко-
нец выходного потока необходимого количества литера-
лов. Естественно, что алгоритм декодирования должен раз-
личать отдельные литералы и группы <длина; смещение>.
Согласно с алгоритмом LZH, в формате DEFLATE с этой
целью базовые значения длин замен и отдельные лите-
ралы кодируются. После базовых значений длин содер-
жится определенное форматом количество битов, кото-
рые вместе с базовым значением однозначно определя-
ют длину замены. Смещение сохраняется после соответ-
ствующей длины аналогично – в виде базового значения
и дополнительных битов.
В программной реализации для уменьшения КС ал-
горитма LZ77 [6] обеспечена возможность выхода из сло-
варя в буфер во время кодирования повторов, использо-
ван модифицированный алгоритм анализа альтернатив-
ных сжатых блоков и проведен анализ количеств допол-
нительных битов для записи смещений.
УСиМ, 2010, № 3 19
Идея использования динамических кодов Хаффмана
[5], чаще всего применяемых после выполнения алго-
ритма LZ77 для сжатия литералов и базовых значений
длин, а также для отдельного сжатия базовых значений
смещений в каждом блоке сжатых данных, заключается
в замене чисел с большей частотой (здесь и в дальней-
шем – абсолютной) кодами меньшего количества битов,
чем для чисел с меньшей частотой.
В соответствии с теоремой Шеннона, элемент si с ве-
роятностью появления p(si) выгоднее всего кодировать –
log p(si) битами (здесь и в дальнейшем логарифм берется
по основанию 2). Тогда средняя длина кода элемента
после применения контекстно-независимого алгоритма
(такого, как кодирование Хаффмана) должна прибли-
жаться к энтропии источника [3]:
i
ii spspH log . (1)
Как известно, энтропия источника уменьшается при
увеличении неравномерности распределения вероятно-
стей между элементами [7].
Алгоритм генерирования динамических кодов Хаф-
фмана известен еще со средины прошлого века и умень-
шить его КС не представляется возможным. Можно только
пытаться после минимизации энтропии отдельных строк
разбить изображение на блоки строк пикселов с близки-
ми значениями энтропии. Это позволит отделить и ло-
кализовать строки с высокой энтропией (границы фраг-
ментов изображения или значительные перепады яркости
пикселов), повысив тем самым неравномерности распре-
деления в смежных блоках, и поэтому уменьшить об-
щий КС.
Уменьшить энтропию при обработке изображений в
формате PNG пытаются также с помощью предикто-
ров, стремящихся, используя значение известных смежных
элементов, спрогнозировать значение очередного элемента
[3, 7]. Если пиксел изображения характеризуется несколь-
кими компонентами (например, R, G, B), то предиктор
каждой из них прогнозирует значение согласно соответ-
ствующим компонентам соседних пикселов. В процессе
использования этой технологии вычисляют и в дальней-
шем кодируют отклонение очередной компоненты от про-
гнозируемого предиктором значения [3]. Поэтому, в об-
щем случае, процесс применения предикторов к каждой
компоненте пиксела в узле (i, j) можно записать формулой
ijijij predictC , (2)
где Cij – значение компоненты до применения предикто-
ра, ij – значение компоненты после применения пре-
диктора, pregictij – значение предиктора, вычисленного
для выбранной компоненты.
Проанализируем распределение частот значений ij.
Поскольку соседние пикселы изображения имеют, как пра-
вило, близкие цвета и поэтому близкие значения соот-
ветствующих компонент, то часто значение предиктора
будет совпадать со значением очередного элемента, ча-
ще всего – будет близким к этому значению и изредка –
значительно отличаться от него. То есть большинство
значений ij будут близкими к нулю. Такое перераспре-
деление частот значений (а следовательно, и вероятно-
стей) значительно повышает неравномерность распреде-
ления и потому уменьшает энтропию источника (соглас-
но (1)), а значит, и длину закодированной последователь-
ности [7]. Таким образом, предикторы хотя и не выпол-
няют непосредственное сжатие данных, но уменьшают,
в первую очередь, КС контекстно-независимого алгорит-
ма. Перераспределение частот значений компонент по-
сле применения предиктора показано на рис. 1.
0
500
1000
1500
2000
2500
0 50 100 150 200 250
значения
ча
ст
от
ы
а
0
4000
8000
12000
16000
20000
-126 -63 0 63 126
значения
ча
ст
от
ы
б
Рис. 1 Распределение частот значений зеленой компоненты
данных первых 64 Кб изображения Lena.bmp: а – до
применения предиктора; б – после применения
LeftPredict
Кроме того, отдельные предикторы могут разбить су-
ществующие или сгенерировать новые повторы фрагмен-
тов изображения и этим повлиять на КС алгоритма LZ77, о
чем будет сказано далее.
В сжатых блоках формата PNG данным каждой стро-
ки предшествует отдельный байт, определяющий предик-
тор, применяемый к компонентам всех его пикселов [8].
Сегодня форматом предусмотрено пять возможных зна-
чений этого байта, который определяет четыре различ-
ных предиктора: 0 – данные строки не обрабатываются
предикторами; 1 – LeftPredict; 2 – AbovePredict; 3 – Ave-
ragePredict; 4 – PaethPredict. Для удобства описания
этих предикторов введем обозначение яркости смежных
элементов для элемента X по схеме:
LeftAbove Above
Left X .
Тогда предикторы формата PNG, согласно стандарту
[1], на языке C запишем так:
20 УСиМ, 2010, № 3
Char LeftPredict(char Left, char Above,
char LeftAbove)
{return Left;}
char AbovePredict(char Left, char Above,
char LeftAbove)
{return Above;}
char AveragePredict(char Left, char Above,
char LeftAbove)
{return (Left+Above)/2;}
char PaethPredict(char Left, char Above,
char LeftAbove)
{int pp=Left+Above-LeftAbove;
int pa,pb,pc;
pa=abs(pp-Left);
pb=abs(pp-Above);
pc=abs(pp-LeftAbove);
if (pa<=pb && pa<=pc) return Left;
else if (pb<=pc) return Above;
else return LeftAbove;}.
Как отмечено в [3], отклонения между значениями
соседних элементов в изображениях чаще всего предо-
пределены двумя причинами: «сильными» колебаниями,
обусловленными изображенными объектами – трендом,
и слабыми фоновыми колебаниями – шумом. Первые
три из упомянутых предикторов описывают шумовую
модель и принадлежат к линейным статическим предик-
торам. Последний объединяет в себе трендовую и шумо-
вую модели и принадлежит к нелинейным статическим
предикторам.
Проблема выбора таких статических предикторов для
каждой строки изображения, которые позволяют умень-
шить общий КС изображения, оставалась нерешенной до
сих пор [8, с. 317]. Далее рассмотрим способы ее реше-
ния с помощью энтропии.
Влияние предикторов и их комбинаций на сжатие
изображений в формате PNG. Оценка энтропии строк
пикселов
Алгоритмы, используемые в формате PNG для сжа-
тия данных, ориентированы на уменьшение разных ви-
дов избыточности: если LZ77 устраняет избыточности
между одинаковыми фрагментами данных, то кодирова-
ние Хаффмана ориентировано на уменьшение избыточ-
ности между преобладающими элементами распределе-
ний. Алгоритм LZ77 в этом формате может сжимать дан-
ные максимум в 129, а кодирование Хаффмана – макси-
мум в восемь раз. Именно поэтому алгоритм LZ77 и ис-
пользуется в формате PNG, хотя он и уменьшает нерав-
номерность распределения между отдельными элемен-
тами и может уменьшить эффективность кодирования
Хаффмана. С другой стороны, в естественных изобра-
жениях яркости компонент соседних пикселов, как пра-
вило, близки, но не одинаковы. Это делает малоэффек-
тивным использование для них алгоритма LZ77, и по-
этому кодирование Хаффмана в этом случае обеспечи-
вает хотя бы удовлетворительные КС. Ключевая роль в
процессе сжатия различных изображений и даже от-
дельных их фрагментов могут выполнять как алгоритм
LZ77, так и кодирование Хаффмана. Использование раз-
ных предикторов (в том числе и отказ от их примене-
ния) формата PNG неодинаково влияет на КС этих алго-
ритмов. Поэтому для каждой строки изображения сле-
дует выбирать тот предиктор, который позволит усилить
действие ключевого алгоритма сжатия соответствующе-
го фрагмента, чем и поможет обеспечить наименьший
общий КС.
Т а б л и ц а 1. Характеристики изображений набора ACT
№
фай-
ла
Название
файла
Раз-
мер,
Кб
Размеры
изображе-
ния, пиксе-
лов
Уникаль-
ных цветов
среди пик-
селов, %
Особенности
9. Clegg.bmp 2101 814x880 17,83
Непрерывно-тоно-
вое, искусствен-
ное, с помехами,
несколько боль-
ших объектов
10. Frymire.bmp 3622 1118x1105 0,29
Дискретно-тоно-
вое, искусствен-
ное, один большой
объект
11. Lena.bmp 769 512x512 56,56
Непрерывно-тоно-
вое, естественное,
несколько боль-
ших объектов
12. Monarch.bmp 1153 768x512 19,99
Непрерывно-тоно-
вое, естественное,
один большой и
много малых объ-
ектов
13. Peppers.bmp 769 512x512 42,47
Непрерывно-тоно-
вое, естественное,
несколько боль-
ших объектов
14. Sail.bmp 1153 768x512 19,26
Непрерывно-тоно-
вое, естественное,
много средних
объектов
15. Serrano.bmp 1464 629x794 0,26
Дискретно-тоно-
вое, искусствен-
ное, один большой
фрагментирован-
ный объект
16. Tulips.bmp 1153 768x512 30,07
Непрерывно-тоно-
вое, естественное,
несколько боль-
ших объектов
Исследуем влияние различных вариантов предикто-
ров на примере сжатия восьми разнотипных 24-битных
естественных изображений из стандартного набора фай-
лов Archive Comparison Test (ACT) в формате PNG, харак-
теристики которых приведены в табл. 1. Загрузить TIFF-
версии файлов изображений этого набора можно, напри-
мер, из http: //compression.ca/act/act-files.html. Тестирование
проводилось с помощью программы CD [7], в которую,
кроме указанных, были внесены такие модификации: раз-
мер блоков данных увеличен до 64 Кб, отброшены вспо-
могательные текстовые блоки и внедрено объединение
строк в блоки, как описано далее. Результаты тестирова-
ния приведены в табл. 2, 3. Скорость декодирования изо-
УСиМ, 2010, № 3 21
бражений почти не зависит от примененных предикто-
ров или их комбинаций и составляет в среднем для дис-
кретно-тоновых изображений 910 Кб/c, для искусствен-
ных с помехами – 545 Кб/с, а для непрерывно-тоновых –
330 Кб/с. Поэтому среднее время декодирования всех
изображений набора составляет только 25 с.
Т а б л и ц а 2. Размеры файлов изображений набора ACT в фор-
мате PNG после применения различных пре-
дикторов и их комбинаций, Кб
Номер файла
Название варианта
1 2 3 4 5 6 7 8
Вме-
сте
Сред-
ний
КС, %
Без предикторов 502 248 702 812 650 894 104 958 4870 55,59
LeftPredict 447 331 502 645 441 793 135 738 4032 43,87
AbovePredict 481 349 471 645 454 808 143 710 4061 43,77
AveragePredict 1124 515 468 610 422 763 215 683 4800 47,06
PaethPredict 440 354 471 609 415 780 145 667 3881 41,77
Комбинирование 1 441 347 476 705 514 838 146 889 4356 47,53
Комбинирование 2 440 353 687 645 441 797 147 711 4221 46,77
Комбинирование 3 440 352 463 606 414 772 147 667 3861 41,51
Комбинирование 4 439 348 463 605 414 772 146 666 3853 41,46
Комбинирование 5 463 311 463 607 415 763 132 669 3823 41,33
Комбинирование 6 439 339 463 605 414 763 147 666 3836 41,34
Комбинирования 4,
5 с анализом блоков
439 243 463 600 414 757 104 663 3683 40,49
Т а б л и ц а 3. Время кодирования файлов изображений на-
бора ACT в формате PNG вариантами про-
грамм с применением различных предикторов
и их комбинаций (на компьютере с частотой
процессора 300 МГц), с
Номер файла Название
варианта 1 2 3 4 5 6 7 8
Вместе
Без преди-
кторов
9,06 13,51 4,66 6,54 4,62 6,97 5,55 6,92 57,83
LeftPredict 12,62 13,84 4,89 8,40 5,61 7,20 5,88 7,75 66,19
AbovePredict 8,29 14,77 4,95 8,41 5,22 7,03 5,99 8,02 62,68
AveragePredict 17,30 15,93 5,05 9,61 5,93 7,30 6,42 8,46 76,00
PaethPredict 11,37 15,71 5,21 9,56 5,93 7,69 6,48 8,84 70,79
Комбиниро-
вание 1
14,50 20,32 6,43 10,71 6,92 9,45 8,35 9,67 86,35
Комбиниро-
вание 2
15,16 22,52 6,81 10,66 7,03 9,34 9,17 10,05 90,74
Комбиниро-
вание 3
14,83 21,04 6,42 11,37 7,03 9,34 8,63 10,44 89,10
Комбиниро-
вание 4
14,61 21,04 6,54 11,70 7,20 9,45 8,74 10,55 89,83
Комбиниро-
вание 5
16,48 24,06 7,25 12,69 7,97 10,55 9,99 11,59 100,58
Комбиниро-
вание 6
17,08 24,99 7,69 13,13 8,35 11,10 10,33 12,08 104,75
Комбинирова-
ния 4, 5 с ана-
лизом блоков
49,21 67,89 20,04 42,35 25,93 30,10 28,35 37,35 301,22
Сжатие изображений в формате PNG без применения
предикторов происходит путем повторений и при нали-
чии неравномерности распределения значений яркости
пикселов. Но в естественных изображениях аналогичные
фрагменты и одинаковые значения яркости компонентов
случаются сравнительно редко, поэтому и такое сжатие
приводит к высоким КС (см. рис. 1,а и вариант Без пре-
дикторов в табл. 2, 3). Сжатие изображений без приме-
нения предикторов эффективно, в первую очередь, для
дискретно-тоновых искусственных изображений с вы-
сокой разрешающей способностью. Это сжатие выпол-
няется быстрее всего, поскольку не требует выполнения
дополнительных вычислений значений предикторов.
Предиктор LeftPredict генерирует горизонтальные при-
росты значений яркости между компонентами соседних
пикселов. Одинаковые приросты значений яркости слу-
чаются в естественных изображениях, как правило, чаще,
чем одинаковые фрагменты, что улучшает КС алгорит-
ма LZ77. Кроме того, применение предиктора LeftPredict
повышает неравномерность распределения вокруг нуля
(рис. 1,б), уменьшая тем самым КС кодирования Хафф-
мана. Именно поэтому средний КС изображений набора
ACT с применением LeftPredict уменьшился в сравнении
с вариантом без применения предикторов на 11,72%. Но
отметим, что при применении LeftPredict возможно умень-
шение длины повторений, которые были между фрагмен-
тами оригинала изображения, поэтому возможно и по-
вышение общего КС (данные изображений № 2, 7 в строке
LeftPredict табл. 2). Следовательно, однозначно утверж-
дать, что сжатие с использованием LeftPredict эффектив-
нее сжатия без применения предикторов невозможно.
Средняя продолжительность компрессии файлов набора
ACT этим способом превышает продолжительность ко-
дирования без предикторов на 14,46%, поскольку при-
менение предикторов требует расчета их значений и по-
рождает больше коротких совпадающих последователь-
ностей, что замедляет формирование разложения LZ77.
Аналогично влияет на сжатие изображений и приме-
нение предиктора RightPredict, генерирующего вертикаль-
ные приросты значений яркости компонент смежных пик-
селов. Различные изображения имеют разный уровень от-
личий пикселов по горизонтали и вертикали. Именно поэ-
тому КС в строках LeftPredict и RightPredict табл. 2 раз-
личны. Этим объясняется разница во времени кодирова-
ния на 34,31% изображение № 1 для данных строк в
табл. 3, поскольку это изображение содержит существен-
но меньшее количество одинаковых приростов значений
яркости компонент пикселов в вертикальном направле-
нии относительно горизонтального, что ускоряет форми-
рование разложения LZ77 и повышает КС. Кроме этого,
худшие КС с использованием предиктора RightPredict от-
носительно LeftPredict для большей части изображений
набора объясняются тем, что одинаковые приросты по
вертикали встречаются, как правило, в соседних строках.
Смещение же между соседними пикселами по вертикали
при обработке данных в формате PNG равно длине стро-
ки, т.е. они значительно больше смещений между сосед-
ними пикселами по горизонтали и поэтому кодируются
значительно большим количеством дополнительных бит.
Предиктор AveragePredict уравновешивает влияние
соседних пикселов по горизонтали и вертикали. Он хо-
рошо (относительно рассмотренных выше вариантов)
прогнозирует значения яркости компонент пикселов для
22 УСиМ, 2010, № 3
изображений больших и размытых естественных объек-
тов, хотя и очень чувствителен к резким перепадам цве-
тов (например, линий лучей света в изображении № 1) и
четким границам объектов искусственных изображений.
Замедление кодирования изображений с использовани-
ем AveragePredict объясняется как необходимостью вы-
полнения операции деления для расчета значения пре-
диктора каждой компоненты всех пикселов, так и низ-
кой эффективностью разложения LZ77, порождающего
много элементов для кодирования Хаффмана.
Самые лучшие в среднем ожидания значений яркости
компонент пикселов генерирует предиктор PaethPredict,
прогнозирующий значение в направлении наименьшего
прироста. Этот предиктор на дискретно-тоновых изобра-
жениях уступает лишь предиктору LeftPredict и вариан-
ту без предикторов, а на непрерывно-тоновых изображе-
ниях обеспечивает КС, близкие к предиктору Average-
Predict. Но, во-первых, нелинейный предиктор PaethPre-
dict вычисляется дольше всех рассмотренных предикто-
ров, что негативно влияет как на время кодирования, так
и на время декодирования, и, во-вторых, этот предиктор,
как и предыдущий, часто уменьшает длины повторений,
которые были между фрагментами оригинала изобра-
жения.
Как видим, применение нелинейных комбинирован-
ных предикторов в целом эффективнее линейных шумо-
вых на более чем 2%, хотя и требует выполнения боль-
шего количества вычислений. С другой стороны, не су-
ществует универсального предиктора, применение ко-
торого способствовало бы наилучшему сжатию всех ти-
пов изображений. Даже для соседних фрагментов изо-
бражений оптимальными могут оказаться разные пре-
дикторы. Поэтому для достижения лучших коэффици-
ентов сжатия необходимо использовать комбинации пре-
дикторов. Понятно, что комбинирование предикторов за-
медляет кодирование, однако оно дает возможность не
только уменьшить размеры файлов изображений, но и
вследствие этого ускорить декодирование.
По стандарту PNG [1] рекомендуется выбирать тот
предиктор для каждой строки, применение которого пре-
допределяет минимальную сумму значений знаковых
байт (из диапазона [–128; 127]). Действительно, уменьше-
ние общей суммы значений строки после использования
предиктора свидетельствует о приближении распреде-
ления частот к симметричному, но указывает ли этот
критерий на уменьшение энтропии источника? Резуль-
таты применения такого способа выбора предиктора для
каждой строки дают негативный результат (см. строку
Комбинирования 1 в табл. 2).
Другой способ определения оптимального предикто-
ра для каждой строки заключается в поиске наибольше-
го количества повторений одинаковых последователь-
ных значений [8, с. 317]. Действительно, повторение зна-
чений способствует улучшению показателей сжатия алго-
ритмом LZ77, но этот способ не учитывает возможности
повторений групп различных байт, что также улучшают
сжатие алгоритмом LZ77, и изменений энтропии источни-
ка. Результаты применения такого способа выбора опти-
мального предиктора каждой строки приведены в табл. 2, 3
в строке Комбинирования 2.
В [3 и 9] предложено выбирать тот предиктор, при-
менение которого предопределяет минимальную сумму
модулей значений знаковых байтов (из диапазона [–128;
127]). Уменьшение общей суммы модулей значений стро-
ки после использования предиктора свидетельствует об
увеличении неравномерности распределения частот во-
круг нуля и улучшает результаты применения контекст-
но-независимого алгоритма. Результаты применения тако-
го способа выбора оптимального предиктора каждой стро-
ки приведены в табл. 2, 3 в строке Комбинирования 3.
Как следует из данных таблиц, такой способ выбора
предиктора строки улучшает средний КС относительно
предиктора Пифа на 0,26%, причем уменьшение разме-
ров файлов наблюдается почти для всех изображений,
хотя он и замедляет кодирование на 22%.
Для разработки более эффективных способов выбора
предикторов строк проанализируем влияние разных пре-
дикторов на производительность базовых алгоритмов сжа-
тия формата PNG. Алгоритм LZ77 достигает лучших КС
изображений без применения предикторов после воздей-
ствия предикторов LeftPredict или RightPredict. Кодиро-
вание Хаффмана лучше всего сжимает распределения
изображений после воздействия предикторов (особенно
после AveragePredict или PaethPredict), поскольку они
повышают неравномерность распределения. Выбрать луч-
ший из трех вариантов использования предикторов от-
носительно алгоритма LZ77 для каждой строки пикселов
невозможно без выполнения трех предварительных раз-
ложений изображения с применением каждого из этих
вариантов, поскольку одинаковые фрагменты данных мо-
гут встречаться в разных строках. Лучший предиктор
относительно разложения Хаффмана для каждой стро-
ки пикселов выберем из условия минимума энтропии сре-
ди результатов их действий, к которой стремится сред-
няя длина кода этого разложения. Пусть каждый из эле-
ментов Si встречается Ni раз в строке длиной
i
iNN .
Тогда NNsp ii / и общая длина закодированных
данных, учитывая (1), приближается к значению
i
ii NNNNHN loglog . (3)
На языке C подпрограмма для приближенного вы-
числения энтропийного размера блока кодов Хаффмана
по частотам элементов согласно (3) с определением про-
гнозируемого КС имеет вид:
double sizeEntropiCode(long * freq, short
countAllFreq, double &entropiKC)
{// freq – массив частот элементов
// countAllFreq – общее количество час-
тот в массиве
double size=0; long n=0;
for (long i=0; i<countAllFreq; i++)
УСиМ, 2010, № 3 23
{n+=freq[i]; // сумируем частоты
if (freq[i]>1) // для существования log
size+=freq[i]*log(freq[i]); }
if (n) {size=(n*log(n)-size) /log(2);
entropiKC=size/(8*n); }
else {size=0; entropiKC=1; }
return size; } .
Фрагмент программы для определения номера пре-
диктора, порождающего данные с наименьшей энтропи-
ей элементов записывается так:
for (i=0; i<=4; ++i) // цикл по предикторам
{memset(freq, 0, sizeof(freq));
for (j=0; j<row_width; ++j) // цикл по
элементам строки
freq[buffers[i][j]]++; // накопление
частот элементов
size=sizeEntropiCode(freq, 256, entropiKC);
if (size<minSize)
{predict1=i; // запомнили номер предик
тора
minSize=size; entropiKC1=entropiKC; }
KC1=entropiKC1; .
Средний КС изображений набора ACT с применением
энтропийного способа выбора предикторов строк умень-
шился в сравнении со способом выбора предикторов на
основе наименьшей суммы модулей значений знаковых
байтов на 0,05% (строка Комбинирования 4 из табл. 2, 3),
причем размер сжатых файлов не увеличился ни для од-
ного изображения, а время сжатия увеличилось только на
0,82%. Использование этого способа эффективно, в пер-
вую очередь, для естественных изображений нескольких
больших объектов. Для фрагментов изображений, в ко-
торых энтропийный способ выбора предикторов строк
является самым эффективным, короткие замены (три–че-
тыре литерала), как правило, не применяются. Оптималь-
ными предикторами при таком способе выбора чаще всего
есть AveragePredict или PaethPredict.
Кроме энтропии отдельных элементов, для каждой
строки пикселов следует оценить также КС после вы-
полнения коротких замен, так как они могут существен-
но увеличить частоты соответствующих длин замен и
уменьшить частоты отдельных литералов. А это, в свою
очередь, приводит к увеличению неравномерности рас-
пределения и, соответственно, к уменьшению КС. Вы-
полнять предварительное сжатие LZ77 для результатов
действия всех предикторов строк нецелесообразно, по-
скольку это приводит к резкому замедлению процесса
кодирования. Оценивались КС строки пикселов после при-
менения триэлементных замен с помощью хеш-таблицы
по четырем последним битам трех смежных элементов,
в которой сохраняются абсолютные позиции последних
вхождений подобных групп. Используя значение этой
таблицы, можно имитировать разложение LZ77 с подсче-
том частот литералов, триэлементных замен и их сме-
щений, а также дополнительных битов, после чего оп-
ределяется общий КС строки. На языке C фрагмент про-
граммы для определения номера предиктора, порож-
дающего данные с наименьшим КС, после коротких за-
мен записывается, например, так:
for (i=0; ii<=4; ++i) // цикл по предикторам
{memset(freq, 0, sizeof(freq)); // частоты
литералов/длин
memset(freqD, 0, sizeof(freqD)); // час
тоты баз смещений
memset(hash, 0, sizeof(hash)); // эле
менты хеш-таблицы
plusBit=0; // дополнительные биты смещений
j=0; // позиция обработки строки после
действия предиктора i
while (j<row_width-2)
if (hash[((buffers[i][j]& 15)<<8)+
((buffers[i][j+1]& 15)<<4)+
(buffers[i][j+2]& 15)])
{// подобные три байта уже были в строке
freq[257]++; // частота триэлементной
замены
offset=j-hash[((buffers[i][j]&15)<<8)+
((buffers[i][j+1]&15)<<4)+(buffers[i][j+
+2]&15)]+1;
// увеличиваем частоту базы смещения
freqD[codesDistance[offset]]++;
// накапливаем дополнительные биты
смещения
plusBit+=extrasDistance[codesDistan-
ce[offset]];
// данные обработанных триэлементных
групп
// записываем в хеш-таблицу
hash[((buffers[i][j]&15)<<8)+
((buffers[i][j+1]&15)<<4)+
+(buffers[i][j+2]&15)]=j+1;
if (j+1<row_width-2)
hash[((buffers[i][j+1]&15)<<8)+
((buffers[i][j+2]&15)<<4)+
(buffers[i][j+3]&15)]=j+2;
if (j+2<row_width-2)
hash[((buffers[i][j+2]&15)<<8)+
((buffers[i][j+3]&15)<<4)+
(buffers[i][j+4]&15)]=j+3;
j+=3; }
else // подобная группа отсутствует –
заносим литерал
{freq[buffers[i][j]]++;
hash[((buffers[i][j]&15)<<8)+
((buffers[i][j+1]&15)<<4)+(buf-
fers[i][j+2]&15)]=j+1;
j++; }
for (; j<row_width ; ++j) //последние
позиции строки
freq[buffers[i][j]]++;
size=sizeEntropiCode(freq,256, entropiKC)+
sizeEntropiCode(freqD, 30, entro-
piKCD)+plusBit;
if (size<minSize)
{predict2=i; // запомнили номер предиктора
minSize=size; entropiKC2=entropiKC; }
KC2=(double) minSize/(8*row_width); .
Средний КС изображений набора ACT с применени-
ем энтропийного способа выбора предикторов строк после
24 УСиМ, 2010, № 3
имитации коротких замен LZ77 уменьшился в сравнении
со средним КС энтропийного поэлементного предиктора
на 0,13% (строка Комбинирования 5 из табл. 2, 3), хотя
улучшение наблюдается только на дискретно-тоновых и
непрерывно-тоновых изображениях, для которых корот-
кие замены эффективны. Это и не удивительно, так как
расчет энтропийного КС после имитации коротких за-
мен лучше всего из рассмотренных вариантов модели-
рует сжатие в формате PNG. Средняя длительность комп-
рессии файлов набора ACT вследствие имитации корот-
ких замен во время выбора предикторов строк возросла
на 11,96%. Оптимальными предикторами в случае вы-
бора по минимальному энтропийному КС после приме-
нения коротких замен LZ77 чаще всего оказываются Left-
Predict или RightPredict. Использование этого способа эф-
фективно в первую очередь для естественных изобра-
жений с многими объектами и для искусственных изо-
бражений.
Для различных изображений и даже для разных фраг-
ментов одного изображения короткие замены LZ77 мо-
гут оказаться как эффективными (т.е. количество бит для
сохранения замены является не большим количества бит
для сохранения отдельных элементов), так и неэффек-
тивными, следовательно, предусмотреть необходимость
имитации коротких замен невозможно. Поэтому для каж-
дой строки пикселов выберем предиктор, обеспечиваю-
щий прогнозируемый минимальный КС. Получать этот
КС будем по результатам сравнения минимального по-
элементного КС (в предыдущих фрагментах программ –
КС1) и минимального КС (КС2) после применения ко-
ротких замен LZ77 относительно результатов действия
всех предикторов, поскольку эти варианты выбора пре-
дикторов обеспечивают в среднем наилучшие результа-
ты. Учитывая, что длинные эффективные замены частично
учтены в КС2 и не учтены в КС1, выбирать предиктор,
обеспечивающий КС2, будем только тогда, когда КС2
меньше КС1 более, чем на 4%. Иначе будем выбирать
предиктор, обеспечивающий КС1:
If (KC2<KC1-0,04) currentPredict=predict2;
Else currentPredict=predict1; .
Такой комбинированный способ выбора предикторов
строк хотя и уступает по среднему КС на 0,01% энтро-
пийному способу после коротких замен LZ77 и форми-
руется на 4,15% медленнее его (см. строку Комбиниро-
вания 6 в табл. 2, 3), но обеспечивает КС по всем изо-
бражениям набора не хуже способа выбора предикторов
Комбинирования 3 на основе наименьшей суммы моду-
лей значений знаковых байтов.
Разбиение изображений на блоки однородных строк
с помощью энтропии
Каждую строку изображения можно, конечно, разме-
стить в отдельном сжатом блоке формата PNG. Но в це-
лом такое сжатие не будет самым эффективным, посколь-
ку в заглавии каждого сжатого блока динамических ко-
дов Хаффмана содержится описание длин кодов его рас-
пределений литералов/длин и смещений, которое может
занимать свыше 1500 битов, а такие расходы недопусти-
мы для каждой строки. С другой стороны, объединение
в сжатых блоках данных произвольных смежных строк
в целом уменьшает неравномерность распределения и
может негативно повлиять на общий КС. Поэтому пред-
лагается в процессе предварительного анализа изображе-
ний перед сжатием в формате PNG объединить смеж-
ные строки с близкими прогнозируемыми энтропийны-
ми КС распределений в блоки. Каждый однородный блок
строк в процессе последующего сжатия может принад-
лежать одному, а может и быть разбит на несколько сжа-
тых блоков, поскольку размер сжатого блока, как пра-
вило, не превышает 64 Кб. Но разные блоки строк долж-
ны обязательно принадлежать различным сжатым бло-
кам, так как имеют разные энтропийные КС (в преды-
дущих фрагментах программ – entropiKC1), а следователь-
но, и разные неравномерности распределений. Понятно,
что объединять смежные блоки строк целесообразно толь-
ко тогда, когда прогнозируемое увеличение длины ко-
дов от их объединения не превышает размера заглавия
нового сжатого блока (т.е. 1500).
Рассчитаем прогнозируемое увеличение длины кодов
от объединения двух смежных блоков. Пусть первый
блок строк содержит l1 элементов с прогнозируемой эн-
тропией (средней длиной кода) e1, а второй – l2 элемен-
тов с энтропией e2. Тогда прогнозируемая длина кодов
первого блока составит l1 e1, а второго – l2 e2. Вслед-
ствие объединения блоков строк с подобными неравно-
мерностями распределения (см. рис. 1,б) энтропия объе-
динения не может превысить максимума энтропий объ-
единенных частей, следовательно прогнозируемая длина
кода объединения не превышает 2121 ;max eell . По-
этому прогнозируемое увеличение длины кода в резуль-
тате объединения двух смежных блоков не превышает
.
,
,
;max
21112
21221
22112121
'
eelee
eelee
eleleelllk
(4)
На практике прогнозируемое увеличение длины кода
от объединения зависит не только от количества элемен-
тов входного блока с меньшей энтропией, но и от коли-
чества элементов другого входного блока (например,
короткий первый входной блок с высокой энтропией не
может максимально увеличить энтропию второго длин-
ного входного блока), поэтому рассчитывать его целе-
сообразно по формуле, которая учитывает отношение
размеров входных блоков:
1 2 2 1 2 1 2''
1 2 1 2 1 1 2
log 1 ,
log 1 ,k
e e l l l l l
l
e e l l l l l
. (5)
Энтропийное кодирования элементов распределений
выполняется в формате PNG после формирования раз-
ложения LZ77. Предопределить количество элементов та-
кого разложения невозможно, но это количество элемен-
тов находится в монотонно неубывающей зависимости
от энтропии: чем меньше энтропия, тем больше вероят-
УСиМ, 2010, № 3 25
ность существования повторений значений яркости компо-
нентов и, следовательно, тем меньше элементов будут со-
держать разложение LZ77. Вычисляли прогнозируемое
количество элементов строк после разложения LZ77 как
произведение начального количества элементов строк и
минимума из единицы и энтропии, увеличенной в 4/3 раза
(считали, что строки с энтропией свыше 0,75 не подда-
ются сжатию LZ77). Алгоритм формирования блоков
однородных строк представим пошагово:
1. Определить для каждой строки пикселов изобра-
жения предиктор, порождающий коды с минимальной эн-
тропией согласно (3) и прогнозируемое количество эле-
ментов после разложения LZ77, как описано ранее. От-
нести каждую строку к отдельному блоку строк.
2. Рассчитать для всех пар смежных блоков прогно-
зируемое увеличение длины кода вследствие их возмож-
ного объединения с помощью (5), учитывая максимум
64 тыс. элементов из каждого блока. Определить пару
смежных блоков, порождающих наименьшее такое уве-
личение длины кода.
3. Если остался только один блок строк или наимень-
шее увеличение длины кода превышает 1500 битов, то
завершить выполнение алгоритма. Иначе объединить пару
смежных блоков, порождающих это увеличение и вер-
нуться к шагу 2.
Именно этот алгоритм формирования блоков одно-
родных строк с помощью энтропии реализован в моди-
фикациях программы, использованной для тестирова-
ния. Он позволяет уменьшить размеры большинства сжа-
тых изображений в формате PNG минимум на 1 Кб.
Достичь меньших КС изображений возможно, если:
разбить их на меньшие блоки однородных строк соглас-
но (4); для каждого блока однородных строк выбрать пре-
дикторы из условия минимума, рассчитанных с помо-
щью (3) КС среди пяти вариантов компрессии (без при-
менения предикторов, с использованием LeftPredict, с при-
менением RightPredict, с использованием энтропийного
поэлементного способа выбора предикторов и с приме-
нением энтропийного способа выбора предикторов по-
сле осуществления коротких замен LZ77); укрупнить бло-
ки однородных строк, используя (5). При этом следует
учитывать также отклонение от вариантов компрессии,
которые обеспечивают минимальный КС для предыду-
щего и следующего однородных блоков строк, посколь-
ку изменение вариантов компрессии между соседними
блоками приводит к возникновению нового сжатого
блока (а следовательно, и его заглавия) и уменьшает
вероятность повторений фрагментов данных для алго-
ритма LZ77. То есть предлагается в процессе анализа
изображения выбирать те предикторы, которые ми-
нимизируют коэффициент сжатия каждого блока од-
нородных строк, а не только энтропию компонент пик-
селов отдельных строк. Результаты применения такого
способа сжатия приведены в строках Комбинирования 4,
5 с анализом блоков табл. 2, 3. Описанный способ сжа-
тия изображений, выбирающий минимальный КС для каж-
дого блока однородных строк, хотя и выполняется в сред-
нем почти втрое медленнее энтропийного варианта и по-
чти в шесть раз медленнее сжатия без предикторов (по-
скольку формирует пять дополнительных разложений
LZ77), но обеспечивает наименьшие КС для всех изо-
бражений набора АСТ.
Заключение. Для повышения эффективности сжатия
данных в форматах, последовательно использующих ал-
горитмы нескольких методов, целесообразно учитывать
взаимное влияние этих алгоритмов. Во время предвари-
тельной обработки данных перед сжатием в таких фор-
матах для расчета параметров компрессии желательно
учитывать все виды избыточностей, обрабатываемых их
отдельными алгоритмами, а также выполнять разбиение
данных на однородные блоки.
Для каждой строки пикселов изображения предикто-
ры следует выбирать в зависимости от ограничений на
время компрессии: в случае самого быстрого сжатия целе-
сообразно использовать нелинейный предиктор PaethPre-
dict для всех строк; во время стандартного сжатия стоит
воспользоваться энтропийным способом выбора предик-
торов (Комбинирование4); для медленного максимально-
го сжатия следует применить выбор предикторов на ос-
нове анализа КС пяти вариантов компрессии каждого
блока однородных строк.
Предложенный способ предварительной обработки с
анализом данных позволяет получить наименьшие КС
изображений в формате PNG путем, в первую очередь,
разбиения изображений на блоки строк пикселов с близ-
кими значениями энтропии и выбора для каждого блока
строк способа сжатия, обеспечивающего для него наи-
меньший КС.
Описанные способы выбора предикторов строк и раз-
биения изображения на блоки однородных строк с по-
мощью энтропии не требуют модификации декодера или
программ просмотра изображений и при уменьшении
размеров файлов лишь ускоряют их работу. Именно поэ-
тому они могут быть эффективно применены в процессе
компактного сохранения данных в форматах, исполь-
зующих разные предикторы для отдельных строк пиксе-
лов, таких, как формат PNG.
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-82820 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:07:52Z |
| publishDate | 2010 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Бомба, А.Я. Шпортько, О.В. 2015-06-09T19:20:03Z 2015-06-09T19:20:03Z 2010 Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG / А.Я. Бомба, О.В. Шпортько // Управляющие системы и машины. — 2010. — № 3. — С. 8-25. — Бібліогр.: 9 назв. — укр., рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82820 004.043 Предложены способы выбора предиктора для каждой строки пикселов и алгоритм разбиения изображения на блоки строк с помощью энтропии перед сжатием в формате PNG. Приведены фрагменты программ на языке C для оценки энтропии строк пикселов непосредственно и после применения контекстно-зависимого алгоритма. Описанные способы выбора предикторов строк позволяют уменьшить коэффициенты сжатия изображений набора ACT в формате PNG. The methods are suggested of the choice of a predictor for every line of pixels and the algorithm of laying out of the image on the blocks of lines with the help of the entropy before a compression in the PNG format. The fragments of the programs in the C language for the estimation of the entropy of lines of pixels directly before and after the application of the context-dependent algorithm are presented. The described methods of the choice of predictors of lines make it possible to decrease the coefficients of the compression of a set of the ACT ratios in the PNG format. Запропоновано способи вибору предиктора для кожного рядка пікселів та алгоритм розбиття зображення на блоки рядків за допомогою ентропії перед стисненням у форматі PNG. Наведено фрагменти програм мовою C для оцінки ентропії рядків пікселів безпосередньо та після застосування контекстно-залежного алгоритму. Описані способи вибору предикторів рядків дозволяють зменшити коефіцієнти стиснення зображень набору ACT у форматі PNG. uk ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Новые методы в информатике Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG Энтропийные способы выбора предиктора для строки пикселов в формате PNG Entropy Methods of the Choice of a Predictor for the Line of Pixels in the PNG Format Article published earlier |
| spellingShingle | Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG Бомба, А.Я. Шпортько, О.В. Новые методы в информатике |
| title | Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG |
| title_alt | Энтропийные способы выбора предиктора для строки пикселов в формате PNG Entropy Methods of the Choice of a Predictor for the Line of Pixels in the PNG Format |
| title_full | Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG |
| title_fullStr | Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG |
| title_full_unstemmed | Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG |
| title_short | Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG |
| title_sort | ентропійні способи вибору предиктора для рядка пікселів у форматі png |
| topic | Новые методы в информатике |
| topic_facet | Новые методы в информатике |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/82820 |
| work_keys_str_mv | AT bombaaâ entropíinísposobiviboruprediktoradlârâdkapíkselívuformatípng AT športʹkoov entropíinísposobiviboruprediktoradlârâdkapíkselívuformatípng AT bombaaâ éntropiinyesposobyvyboraprediktoradlâstrokipikselovvformatepng AT športʹkoov éntropiinyesposobyvyboraprediktoradlâstrokipikselovvformatepng AT bombaaâ entropymethodsofthechoiceofapredictorforthelineofpixelsinthepngformat AT športʹkoov entropymethodsofthechoiceofapredictorforthelineofpixelsinthepngformat |