Стиснення RGB-зображень без втрат із використанням палітри
Розглянуто та обґрунтовано можливості стиснення RGB-зображень без втрат за допомогою палітрування. Описано варіант алгоритму для реалізації такого стиснення з розбиттям результату на трендову та шумову складові. Наведено результати застосування програми, розробленої згідно із запропонованим алгоритм...
Збережено в:
| Опубліковано в: : | Системні дослідження та інформаційні технології |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50041 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Стиснення RGB-зображень без втрат із використанням палітри / О.В. Шпортько // Систем. дослідж. та інформ. технології. — 2010. — № 2. — С. 26-36. — Бібліогр.: 5 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50041 |
|---|---|
| record_format |
dspace |
| spelling |
Шпортько, О.В. 2013-10-03T19:46:19Z 2013-10-03T19:46:19Z 2010 Стиснення RGB-зображень без втрат із використанням палітри / О.В. Шпортько // Систем. дослідж. та інформ. технології. — 2010. — № 2. — С. 26-36. — Бібліогр.: 5 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50041 004.043 Розглянуто та обґрунтовано можливості стиснення RGB-зображень без втрат за допомогою палітрування. Описано варіант алгоритму для реалізації такого стиснення з розбиттям результату на трендову та шумову складові. Наведено результати застосування програми, розробленої згідно із запропонованим алгоритмом для стиснення зображень набору ACT. Рассмотрены и обоснованы возможности сжатия RGB-изображений без потерь с помощью палитрования. Описан вариант алгоритма для реализации такого сжатия с разбитием результата на трендовую и шумовую составляющие. Приведены результаты применения программы, разработанной согласно предложенного алгоритма для сжатия изображений набора ACT. The possibilities of RGB-image compression without losses using a palette are considered. A version of the algorithm for realization of the compression with partition of the result into a trend and noise components is described. The results of using the program developed according to the offered algorithm for compression of the images of the ACT set are presented. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Стиснення RGB-зображень без втрат із використанням палітри Сжатие RGB-изображений без потерь с использованием палитры Loss-free compression of RGB-images using a palette Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Стиснення RGB-зображень без втрат із використанням палітри |
| spellingShingle |
Стиснення RGB-зображень без втрат із використанням палітри Шпортько, О.В. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| title_short |
Стиснення RGB-зображень без втрат із використанням палітри |
| title_full |
Стиснення RGB-зображень без втрат із використанням палітри |
| title_fullStr |
Стиснення RGB-зображень без втрат із використанням палітри |
| title_full_unstemmed |
Стиснення RGB-зображень без втрат із використанням палітри |
| title_sort |
стиснення rgb-зображень без втрат із використанням палітри |
| author |
Шпортько, О.В. |
| author_facet |
Шпортько, О.В. |
| topic |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| topic_facet |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| publishDate |
2010 |
| language |
Ukrainian |
| container_title |
Системні дослідження та інформаційні технології |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| format |
Article |
| title_alt |
Сжатие RGB-изображений без потерь с использованием палитры Loss-free compression of RGB-images using a palette |
| description |
Розглянуто та обґрунтовано можливості стиснення RGB-зображень без втрат за допомогою палітрування. Описано варіант алгоритму для реалізації такого стиснення з розбиттям результату на трендову та шумову складові. Наведено результати застосування програми, розробленої згідно із запропонованим алгоритмом для стиснення зображень набору ACT.
Рассмотрены и обоснованы возможности сжатия RGB-изображений без потерь с помощью палитрования. Описан вариант алгоритма для реализации такого сжатия с разбитием результата на трендовую и шумовую составляющие. Приведены результаты применения программы, разработанной согласно предложенного алгоритма для сжатия изображений набора ACT.
The possibilities of RGB-image compression without losses using a palette are considered. A version of the algorithm for realization of the compression with partition of the result into a trend and noise components is described. The results of using the program developed according to the offered algorithm for compression of the images of the ACT set are presented.
|
| issn |
1681–6048 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50041 |
| citation_txt |
Стиснення RGB-зображень без втрат із використанням палітри / О.В. Шпортько // Систем. дослідж. та інформ. технології. — 2010. — № 2. — С. 26-36. — Бібліогр.: 5 назв. — укр. |
| work_keys_str_mv |
AT športʹkoov stisnennârgbzobraženʹbezvtratízvikoristannâmpalítri AT športʹkoov sžatiergbizobraženiibezpoterʹsispolʹzovaniempalitry AT športʹkoov lossfreecompressionofrgbimagesusingapalette |
| first_indexed |
2025-11-25T22:31:28Z |
| last_indexed |
2025-11-25T22:31:28Z |
| _version_ |
1850565238414376960 |
| fulltext |
© О.В. Шпортько, 2010
26 ISSN 1681–6048 System Research & Information Technologies, 2010, № 2
УДК 004.043
СТИСНЕННЯ RGB-ЗОБРАЖЕНЬ БЕЗ ВТРАТ ІЗ
ВИКОРИСТАННЯМ ПАЛІТРИ
О.В. ШПОРТЬКО
Розглянуто та обґрунтовано можливості стиснення RGB-зображень без втрат
за допомогою палітрування. Описано варіант алгоритму для реалізації такого
стиснення з розбиттям результату на трендову та шумову складові. Наведено
результати застосування програми, розробленої згідно із запропонованим ал-
горитмом для стиснення зображень набору ACT.
У файлах, що передаються каналами зв’язку, найчастіше містяться дані од-
ного з чотирьох основних типів: тексти, зображення, відео або звук. І якщо
для зберігання однієї сторінки неформатованого тексту достатньо 4 Кб, то
фотореалістичне растрове зображення 10×15 см без стиснення може займати
кілька Мб, записи пісень — десятки Мб, а записи фільмів — декілька Гб.
Добре, що більшість із цих файлів мають високий рівень надлишковості.
Саме зменшення надлишковості дозволяє стискати файли, і тим самим під-
вищувати швидкість обміну інформацією по мережі та зменшувати об’єми
використання дискового простору. Тому зараз, в епоху інформаційної циві-
лізації, коли значна частина інформації зберігається в електронному вигляді,
проблема стиснення зображень залишається актуальною.
Більшість відомих алгоритмів, які дозволяють стиснути зображення в
десятки разів (JPEG, фрактальних та вейвлет-перетворень), призводять до
незначних втрат якості зображень, що непомітно для фотореалістичних зо-
бражень з високою роздільною здатністю, але впливає на якість зображень
із невисокою роздільною здатністю з фрагментами ділової графіки чи дис-
кретно-тоновими переходами. Крім того, існують класи зображень, для яких
спотворення неприпустимі (наприклад рентгенівські знімки). Алгоритми
стиснення зображень без втрат хоча й стискають зображення значно слабше,
але не призводять до погіршення їхньої якості. Зараз найдинамічніше розви-
ваються алгоритми стиснення зображень із втратами, хоча й алгоритми стис-
нення зображень без втрат теж із кожним роком підвищують свої показники.
ОСНОВНІ ПІДХОДИ ДО СТИСНЕННЯ ЗОБРАЖЕНЬ БЕЗ ВТРАТ. АНАЛІЗ
ОСТАННІХ ДОСЯГНЕНЬ І ПУБЛІКАЦІЙ. ПОСТАНОВКА ЗАДАЧІ
Більшість сучасних графічних форматів для збереження кольору кожного
пікселя використовують три компоненти [1]. Наприклад, у кольоровій моде-
лі RGB — це яскравість червоної (R), зеленої (G) та синьої (B) компоненти.
Під кожну компоненту відводиться, як правило, 1 байт. Тому розмір файла
зображення у нестисненому вигляді приблизно дорівнює потроєному добут-
ку кількостей пікселів по вертикалі (height) та горизонталі (width).
Інший спосіб зберігання кольору пікселів зображення передбачає вико-
ристання палітри. Палітра — це одномірний масив трибайтових елементів,
Стиснення RGB-зображень без втрат із використанням палітри
Системні дослідження та інформаційні технології, 2010, № 2 27
кожен з яких визначає колір [2]. При такому способі збереження зображення
колір кожного пікселя задається індексом в палітрі (наприклад у форматі
GIF). Зазвичай, використовуються палітри з 2, 16 чи 256 кольорів [3]; (від-
повідно 1, 4 чи 8 бітам на індекс кольору пікселя). Палітри з більшою кіль-
кістю кольорів хоча й можливі, але на практиці не використовуються, оскі-
льки вимагають більше байтів для зберігання самої палітри і, головне,
значно більше бітів для зберігання індексу кольору кожного пікселя.
Розмір файла палітрового зображення у нестисненому вигляді приблизно
дорівнює сумі розміру палітри та добутку кількостей пікселів по горизонта-
лі та вертикалі, помноженій на розмір індексу кольору пікселя. Наприклад,
під час використання палітри з 256 кольорів розмір файла складає приблиз-
но 256*3+height*width байт, тобто майже втричі менше, ніж при зберіганні
згідно з кольоровою моделлю RGB. На жаль, кількість різних кольорів паліт-
рового зображення не може перевищувати кількості кольорів у палітрі. То-
му сучасні фотореалістичні зображення, що містять сотні тисяч різних ко-
льорів, найчастіше використовують трикомпонентні кольорові моделі (RGB,
YCrCb, HLS та ін.). Проблема використання палітри для стиснення таких
зображень без втрат до цього часу залишалася невирішеною. Більшість су-
часних графічних форматів стиснення без втрат (BMP, PNG) дозволяють
зберігати зображення як із використанням палітри, так і без неї.
Сучасні архіватори та формати графічних файлів для стиснення зобра-
жень без втрат найчастіше використовують як один із основних етапів алго-
ритмів словникового методу [1, 3]. Такі алгоритми намагаються замінити
наступні незакодовані символи посиланням на аналогічні символи у вже
закодованій частині. Фотореалістичні зображення стискаються словникови-
ми алгоритмами неефективно, оскільки, як правило, вони містять багато по-
дібних, але неоднакових кольорів. Словникові алгоритми належать до класу
контекстно-залежних, тому що використовують опрацьовану раніше послі-
довність. Алгоритми цього методу покликані усувати залежності між різни-
ми послідовностями елементів.
Для покращення стиснення даних результати дії словникових алгорит-
мів доцільно стиснути одним із контекстно-незалежних алгоритмів (ариф-
метичним чи Хафмана). Ідея використання цих алгоритмів полягає у заміні
елементів з більшою частотою послідовностями меншої кількості бітів, ніж
для елементів з меншою частотою. При цьому середня довжина коду еле-
мента після застосування контекстно-незалежного методу згідно з теоремою
Шеннона має наближатися до величини:
∑−=
i
ii spspH )(log)( , (1)
де )( isp — ймовірність появи елемента is , а всі логарифми тут і надалі бе-
руться за основою 2. Цю величину також називають ентропією джерела [1].
Вона зменшується під час збільшення нерівномірності розподілу ймовірнос-
тей між елементами.
Для аналізу ефективності запропонованого алгоритму ми використали
програму WinRar версії 4.00 із застосуванням лише основного алгоритму,
що послідовно виконує LZ-кодування та стиснення Хафмана (LZ+Huff).
Основну увагу при розробці алгоритмів стиснення без втрат приділя-
ють показникам компресії: коефіцієнту стиснення (КС), тобто відсотку
зменшення початкового розміру файла або усередненому значенню ентро-
О.В. Шпортько
ISSN 1681–6048 System Research & Information Technologies, 2010, № 2 28
пії, тобто кількості бітів, що всередньому витрачається на кодування одного
пікселя (bpp). Оскільки між цими показниками існує взаємно-однозначна
відповідність, то ми скористалися лише першим, тому що він використо-
вується для оцінки стиснення не лише зображень.
Врахуємо, що згідно з [4]: «Відхилення між значеннями сусідніх еле-
ментів у зображеннях найчастіше зумовлені двома причинами: «сильними»
коливаннями, що обумовлюються зображеними об’єктами — трендом, і
«слабкими» фоновими коливаннями — шумом. Тому можливі два проти-
лежні типи моделей:
• внесок шуму незначний у порівнянні з внеском тренду;
• внесок тренду незначний у порівнянні з внеском шуму.
Око людини насамперед орієнтується на контури об’єктів (тренд) і
менш чутливе до фонових коливань (шуму). Тому під час передачі даних по
мережі для забезпечення прогресуючого стиснення доцільно спочатку пере-
давати дані тренду і лише після цього — шуму.
МЕТА ДОСЛІДЖЕННЯ
Обґрунтування можливості та опис відповідного алгоритму для стиснення
довільних RGB-зображень без втрат із використанням палітри та словнико-
вих методів. Основною вимогою до алгоритму є досягнення максимальних
КС у практично незмінних витратах часу.
АЛГОРИТМ СТИСНЕННЯ RGB-ЗОБРАЖЕНЬ БЕЗ ВТРАТ ІЗ
ВИКОРИСТАННЯМ ПАЛІТРИ
З’ясуємо спочатку глибинні причини майже потрійного стиснення дискрет-
но-тонових зображень у разі використання палітри з 256 кольорами. У ко-
льоровій моделі RGB значення кожної компоненти лежить у межах від 0 до
255. Отже, загалом ця модель адресує 16777216256256255 =×× кольорів.
При використанні ж палітри індексується лише 256 кольорів, тобто для збе-
рігання індексу кольору використовується 8 бітів замість 24.
Надлишкова індексація характерна для кольорової моделі RGB і у ви-
падку зберігання фотореалістичних зображень, адже в кожному з них викорис-
товується лише невеличка частина спектру кольорів (наприклад, в зображен-
нях набору Archiv Comparison Test (ACT) — менше 1% (номер 6 у табл. 1)).
Т а б л и ц я 1 . Характеристики зображень набору ACT
Номер
файла
Назва
файла
Розмір,
Кб
Розміри
пікселів
Кількість
різних
кольорів
Використання
спектру, %
Різні кольо-
ри серед
пікселів, %
1 Clegg.bmp 2101 814 × 880 127696 0,76 17,83
2 Frymire.bmp 3622 1118 × 1105 3622 0,02 0,29
3 Lena.bmp 769 512 × 512 148279 0,88 56,56
4 Monarch.bmp 1153 768 × 512 78617 0,47 19,99
5 Peppers.bmp 769 512 × 512 111344 0,66 42,47
6 Sail.bmp 1153 768 × 512 75748 0,45 19,26
7 Serrano.bmp 1464 629 × 794 1313 0,01 0,26
8 Tulips.bmp 1153 768 × 512 118233 0,70 30,07
Стиснення RGB-зображень без втрат із використанням палітри
Системні дослідження та інформаційні технології, 2010, № 2 29
Максимальна кількість різних кольорів у зображенні у найгіршому ви-
падку не перевищує кількості пікселів. Наприклад, у фотореалістичному
зображенні Lena.bmp (рис. 1) використовується 148279 кольорів 262144 пік-
селями, тобто 0,88% кольорів від можливих. Розглядаючи навіть проекцію
кольорів пікселів цього зображення на площину RG (рис. 4), можна поміти-
ти, що використовується менше 30% індексованого простору площини.
Для зменшення надлишкової індексації кольоровою моделлю сфор-
муємо палітру тренду, виконуючи такі кроки:
1. Розіб’ємо множину допустимих значень кольорів на сегменти мак-
симального фіксованого розміру [5], що не перекриваються між собою (на-
приклад, для RGB — це множина прямокутних паралелепіпедів). Оскільки
наперед невідомо, в яких сегментах містяться кольори пікселів обраного
зображення, то множина сегментів має повністю покривати множину допус-
тимих значень кольорової моделі.
2. Визначимо кількість кольорів пікселів та межі їх знаходження у
кожному сегменті. Звузимо межі кожного сегменту до меж знаходження
кольорів пікселів у ньому.
3. Поєднаємо між собою сусідні сегменти, якщо їх сукупний розмір не
перевищує максимального фіксованого.
Рис. 1. Зображення
Lena.bmp
Рис. 2. Зображення
Lena.bmp в палітрі з 63
кольорів
Рис. 3. Зображення
Lena.bmp в палітрі з 256
кольорів
Рис. 4. RG-проекція кольорів пікселів зображення Lena.bmp
0
48
96
144
192
240
0 48 96 144 192 240 R
G
О.В. Шпортько
ISSN 1681–6048 System Research & Information Technologies, 2010, № 2 30
4. Збережемо в палітрі координати лише тих сегментів, які містять ко-
льори пікселів. Тоді колір кожного пікселя можна розбити на дві складові —
індекс сегменту в палітрі (тренд) та зміщення кольору всередині сегменту
(шум). Оскільки у найгіршому випадку кожен вихідний сегмент може міс-
тити кольори пікселів, то початкова кількість сегментів не може перевищу-
вати максимально допустимої кількості кольорів палітри.
5. Доповнимо палітру до максимально можливої кількості кольорів, ви-
користовуючи поділ окремих сегментів так, щоб максимально збільшити КС.
Як зазначалося вище, трендову та шумову складові доцільно зберігати
окремо для забезпечення прогресивної передачі даних по мережі. Варіант
програми, що реалізує пропонований алгоритм, взагалі розбиває зображення
на два файли, які містять відповідно дані трендової та шумової моделі. При
цьому множина всіх допустимих значень кольорів на початку програми роз-
бивається на 256 сегментів-паралелепіпедів розміром 643232 ×× значення.
Саме такі сегменти будемо розглядати надалі. Кількість сегментів-
паралелепіпедів, що реально використовуються окремими зображеннями,
після четвертого кроку алгоритму, як правило, не перевищує 100. Напри-
клад, зображення Lena.bmp використовує 63 паралелепіпеда з 256 (рис. 2)
кольорів.
Розглянемо результати застосування запропонованого алгоритму для
стиснення різнотипних зображень згаданого вище набору ACT. Файл трен-
ду, отриманий у результаті виконання запропонованого алгоритму, під час
використання палітри з 256 кольорів без стиснення займає третю частину
вхідного файла. Його доцільно стиснути алгоритмом LZ+Huff. Причому
розмір стиснутого файла тренду завжди буде меншим від розміру стиснуто-
го аналогічного вхідного зображення (номери 2, 5, 8 у табл. 2). Це пов’язано
як із застосуванням палітри, так і зі зведенням кольорів сегментів до єдино-
го кольору палітри, тобто ліквідації шумів.
Зовсім інші підходи застосовуються для стиснення файлів шумів. Ви-
користання контекстно-залежних алгоритмів типу LZ тут неефективне,
оскільки повторення послідовностей практично відсутні. Файли шумів мож-
на відразу закодувати ентропійним алгоритмом, але такий підхід несуттєво
підвищує КС.
Т а б л и ц я 2 . Результати стиснення файлів набору ACT (Кб) при застосу-
ванні та без застосування палітри
Без поділу паралелепіпедів З поділом паралелепіпедів
Номер
файла
LZ+Huff
файла
тренду
Файл
шуму Всього
LZ+Huff
файла
тренду
Файл
шуму Всього
LZ+Huff
файла
зображення
1 103 1398 1501 116 1186 1302 500
2 138 2288 2426 140 1073 1213 235
3 78 510 588 186 370 556 701
4 87 766 853 216 542 758 789
5 58 508 566 140 387 527 641
6 134 767 901 289 548 837 867
7 46 863 909 60 285 345 102
8 113 767 880 232 603 835 938
Разом 757 7867 8624 1379 4994 6373 4773
Стиснення RGB-зображень без втрат із використанням палітри
Системні дослідження та інформаційні технології, 2010, № 2 31
Нами пропонується спосіб зберігання шумів шляхом безпосереднього
запису зміщень кольорів усередині сегменту з урахуванням його розміру.
Якщо, наприклад, максимальний сегмент-паралелепіпед має розміри
643232 ×× значення, то для зберігання зміщення в ньому необхідно
⎡ ⎤ ⎡ ⎤ ⎡ ⎤ біт.16)64(log)32(log)32(log =++ Тобто, навіть у випадку максималь-
них розмірів усіх паралелепіпедів (для хаотичних зображень) результат па-
літрування перевищить розмір вхідного файла лише на опис цих сегментів.
Наприклад, для опису паралелепіпедів, що не перевищують згаданого мак-
симального, достатньо 40 бітів: 24 — для опису базового кольору паралеле-
піпеда в палітрі і 16 — його розмірів. Для запису зміщень в паралелепіпедах
меншого розміру знадобиться менша кількість біт. Саме завдяки цьому і до-
сягається стиснення файлів шумів. Інша перевага безпосереднього запису
зміщень кольорів усередині паралелепіпеда полягає у максимальній швид-
кості обробки даних, оскільки при цьому не виконуються ніякі перетворен-
ня. Результати стиснення шумів зображень набору ACT лише завдяки вра-
хуванню розмірів сегментів-паралелепіпедів (без п’ятого кроку алгоритму)
наведено в табл. 2, у номері 3.
Підвищити КС файлів шумів можна завдяки поділу окремих паралеле-
піпедів. Навіть безпосереднє розбиття довільного паралелепіпеда навпіл
зменшує кількість значень по осі поділу вдвічі, а кількість бітів — на один
для кожного зміщення паралелепіпеда. Тому розбиття таким чином парале-
лепіпедів із максимальною кількістю точок покращує показники стиснення.
Досягнути ж кращих КС можна завдяки оптимальному розбиттю паралеле-
піпедів. Розглянемо, наприклад, RG-проекцію зміщень кольорів пікселів
окремого умовного паралелепіпеда (рис. 5), розбиття якого посередині ребра
по осі R (штрих-пунктирна лінія) створить два паралелепіпеда: перший — у
діапазоні [0; 15] і другий — [16; 31] по цій осі. Тобто сумарного зменшення
розміру від такого поділу не відбудеться. Якщо ж розбити цей паралелепі-
пед по значенню 7=R (пунктирна лінія), то можна буде створити лівий па-
ралелепіпед у діапазоні [0; 5] та правий — [10; 31], що дозволить сумарно
зменшити розмір по цій осі на 4 значення.
Отже, досягнути додаткового зменшення розмірів сегментів-
паралелепіпедів у результаті поділу можна завдяки врахуванню положення
Рис. 5. RG-проекція зміщень кольорів пікселів окремого умовного паралелепіпеда
0
8
16
24
0 8 16 24 R
G
О.В. Шпортько
ISSN 1681–6048 System Research & Information Technologies, 2010, № 2 32
зміщень у ньому. Зменшення розмірів паралелепіпедів призводить до змен-
шення кількості бітів для збереження зміщень, тобто до покращення показ-
ників стиснення.
Виведемо формулу для підрахунку зменшення кількості бітів у записі
зміщень кольорів у результаті поділу паралелепіпеда по значенню i осі R
на два паралелепіпеди — правий і лівий. Нехай діапазон значень ребра па-
ралелепіпеда до поділу по осі R знаходиться в межах [minR; maxR], по осі G
— ]max;[min GG , а по осі B — .]max;[min BB Позначимо countPoint зага-
льну кількість зміщень у паралелепіпеді, а ,)(count jR )(count jG ,
)(count jB — кількості зміщень, які мають значення j відповідно по R , G
та B . Очевидно, що:
∑∑∑
===
===
B
Bj
G
Gj
R
Rj
jBjGjR
max
min
max
min
max
min
)(count)(count)(countcountPoint . (2)
Позначимо також i праву межу лівого, а i ліву межу правого паралеле-
піпедів при поділі по осі R .
ji
jR
iRj
0)(count
,min
max
>
=
= , ji
jR
Rij
0)(count
max,1
min
>
+=
= .
Кількість бітів, необхідних для запису зміщень кольорів паралелепіпеда
до поділу, дорівнює:
⎡ ⎤
⎡ ⎤
⎡ ⎤ ⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
+−+
++−+
++−
=
)1minmax(log
)1minmax(log
)1minmax(log
countPointcountBit
BB
GG
RR
. (3)
Якщо знехтувати зменшенням розмірів лівого та правого паралелепіпе-
дів після поділу по інших осях, то кількість бітів, яка знадобиться для запи-
су зміщень кольорів у цих сегментах, відповідно складе:
⎡ ⎤
⎡ ⎤
⎡ ⎤ ⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
+−+
++−+
++−
= ∑
= )1minmax(log
)1minmax(log
)1min(log
)(countitcountLeftB
min BB
GG
Ri
jR
i
Rj
i (4)
та
⎡ ⎤
⎡ ⎤
⎡ ⎤ ⎟⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎝
⎛
+−+
++−+
++−
= ∑
= )1minmax(log
)1minmax(log
)1max(log
)(countBitcountRight
max
BB
GG
iR
jR
R
ij
i . (5)
Тоді очевидно, що зменшення кількості бітів від поділу сегменту по
значенню i осі R складе:
( )iii BitcountRightitcountLeftBcountBitprice +−= . (6)
Умовою оптимального розбиття сегменту-паралелепіпеда по осі R є
максимальне зменшення кількості бітів:
i
RRi
R pricemaxprice
max,min=
= . (7)
Стиснення RGB-зображень без втрат із використанням палітри
Системні дослідження та інформаційні технології, 2010, № 2 33
Підставимо послідовно (3) – (5) в (6) та (6) в (7), розкриємо дужки та,
врахувавши (2), після зведення отримаємо:
⎡ ⎤
⎡ ⎤
⎡ ⎤
⎟⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
⎟⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎜
⎝
⎛
+−+
++−−
−+−
=
∑
∑
=
=
=
)1(maxlog)(count
)1min(log)(count
)1min(maxlogcountPoint
maxprice
max
min
max,min
iRjR
RijR
RR
R
ij
i
Rj
RRi
R (8)
або
⎡ ⎤ −+−= )1min(maxlogcountPointprice RRR
⎡ ⎤
⎡ ⎤ ⎟⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎜
⎝
⎛
+−+
++−−
−
∑
∑
=
=
=
)1(maxlog)(count
)1min(log)(count
min
max
min
max,min
iRjR
RijR
R
ij
i
Rj
RRi
.
Формули для знаходження оптимального розбиття паралелепіпеда по
осях G та B отримуються аналогічно. Умовою загального оптимального
розбиття сегменту-паралелепіпеда є максимальне зменшення кількості бітів
від поділу по довільній осі
( )BGR price,price,pricemaxprice = ,
а місцем — площина, щодо якої цей максимум досягається. Оскільки для
зберігання опису паралелепіпеда витрачається 40 бітів, то поділ доцільно
виконувати лише тоді, коли виграш від оптимального розбиття перевищує
це значення.
Розглянемо тепер практичні аспекти реалізації знаходження оптималь-
ного розбиття паралелепіпеда по кожній з осей, які дозволяють пришвидши-
ти виконання обчислень, на прикладі осі R згідно з (8).
1. Зменшення кількості бітів від розбиття паралелепіпеда по довільно-
му значенню осі не залежить від його розмірів та від значень зміщень, а за-
лежить, насамперед, від значень проекцій точок на аналізовану вісь.
2. Для всіх i , таких, що 0)(count =tR , ii priceprice = , проводити роз-
рахунки зменшення кількості біт згідно з (8) не потрібно.
3. Послідовно змінюючи i, перераховувати щоразу дві внутрішні суми
у (8) не потрібно, адже відносно попередньої перша сума збільшується на
)(count iR , а друга — зменшується на цю ж величину.
У мові C алгоритм знаходження оптимального розбиття паралелепіпеда
може бути реалізовано так:
//розрахуємо кількість проекцій зміщень паралелепіпеда на всі значення осей
memset(countR, ∗32,0 sizeof(UBYTE4));
memset(countG, ∗32,0 sizeof(UBYTE4));
memset(countB, ∗64,0 sizeof(UBYTE4));
О.В. Шпортько
ISSN 1681–6048 System Research & Information Technologies, 2010, № 2 34
=p firstPoint; //індекс першої точки паралелепіпеда
//перебираємо зміщення паралелепіпеда
for (index 0= ; index< countPoint; index++)
}]min]3[Dataimage[count{ ++−∗ RpR ;
}]min]13[Dataimage[count{ ++−+∗ GpG ;
}]min]23[Dataimage[count{ ++−+∗ BpB ;
][nextPoint pp = ; //перехід до наступного зміщення паралелепіпеда
0plusBit = ; //ініціалізуємо змінну максимального зменшення кількості біт
if )min(max RR > //якщо розбиття паралелепіпеда по осі R можливе
0{countLeft = ; //ініціалізація першої внутрішньої суми
countPointt{countRigh = ; //ініціалізація другої внутрішньої суми
1)minR(maxcountBitcountPointp +−∗= R ; //стале зменшуване осі
for )index;minmaxindex;0(index ++−<= RR //перебираємо всі значення
осі R
)0]index[count({if >R // index вказує на праву межу лівого паралелепі-
педа
]index[count{countLeft R=+ ;
]index[countt{countRigh R=− ;
1index1index += ; // 1index вказує на ліву межу правого паралелепіпеда
)0]1index[count(while =R
++index1 ; //посуваємо нижню межу правого паралелепіпеда
//підрахуємо зменшення кількості біт від чергового розбиття
)countRight1)(indexcountBitcountLeft(plus ∗++∗−= p
1))index1min(maxcountBit +−− RR ;
if )0plus( >
if )plusplusBit( < //знайдено оптимальніше розбиття
)plusplusBit( = ; //оптимальніше зменшення кількості біт
1tupMega = ; //індекс осі з оптимальнішим розбиттям
indexminmega += R ; //значення осі, де досягається оптимальніше
розбиття.
Описаний алгоритм оптимального поділу сегментів-паралелепіпедів,
хоча й дозволяє цілком зменшити розміри файлів шумів, проте негативно
впливає на стиснення файлів трендів (номери 5–7, у табл. 2). Це пов’язано зі
створенням нових значень у палітрі, що зменшує кількості повторень і тим
самим негативно впливає на стиснення алгоритмами LZ. З іншого боку, по-
діл сегментів зменшує нерівномірність розподілу, що призводить до збіль-
шення ентропії (1) і негативно впливає на стиснення алгоритмом Хафмана.
Загалом, використання алгоритму оптимального поділу паралелепіпедів під-
вищує КС по набору ACT на 18,47% (номери 2, 3, у табл. 3). У цій же
таблиці наведено КС при безпосередній компресії зображення алгорит-
мом LZ+Huff та кращою на сьогодні програмою для цього набору ERI 5.1
Стиснення RGB-зображень без втрат із використанням палітри
Системні дослідження та інформаційні технології, 2010, № 2 35
(за даними http://www.compression.ru/arctest/act/act-tif.htm). Крім того,
збільшення кількості кольорів палітри до максимально можливої значно
покращує якість трендового зображення (див. рис. 2, 3). Час палітрування
та виконання програми згідно з описаним алгоритмом наведено в табл. 4.
Т а б л и ц я 3 . КС файлів набору ACT (%) при та без застосування палітри
Номер файла КС без поділу
паралелепіпедів
КС з поділом
паралелепіпедів
КС LZ+Huff
файла зображення КС ERI 5,1
1 28,56 38,03 76,20 83,48
2 33,02 66,51 93,51 94,81
3 23,54 27,70 8,84 39,92
4 26,02 34,26 31,57 61,67
5 26,40 31,47 16,64 56,31
6 21,86 27,41 24,80 53,95
7 37,91 76,43 93,03 94,67
8 23,68 27,58 18,65 55,85
Разом 29,22 47,69 60,83 76,26
Т а б л и ц я 4 . Час палітрування та виконання програми (С) для файлів
набору ACT (на комп’ютері з частотою процесора 300 МГц)
Без поділу паралелепіпедів З поділом паралелепіпедів
Номер файла Тривалість
палітрування
Тривалість
програми
Тривалість
палітрування
Тривалість
програми
1 2 5 2 5
2 2 8 4 10
3 1 2 2 2
4 1 2 2 3
5 1 1 1 3
6 1 2 2 4
7 1 3 2 3
8 1 3 2 3
Разом 10 26 17 33
Запропонований алгоритм дозволяє досягнути кращих КС стосовно ба-
зового алгоритму для фотореалістичних зображень із десятками тисяч різ-
них кольорів (номери 3–6, 8, у табл. 3), хоча й значно програє на зображен-
нях із розсіяним спектром (номер 1), великими однаковими ділянками
(номери 2, 7) і, як наслідок, загалом по набору ACT. Виконується запропо-
нований алгоритм майже стільки ж часу, скільки триває зчитування і запис
файлів на диск.
Для подальшого вдосконалення наведеного алгоритму пропонуємо:
• забезпечити можливість необмеженого розширення палітри;
• зберігати опис та використовувати поділені сегменти-паралелепі-
педи у файлах шумів для запобігання погіршення стиснення файлів тренду;
• реалізувати стиснення за допомогою палітрування з використанням
предикторів;
О.В. Шпортько
ISSN 1681–6048 System Research & Information Technologies, 2010, № 2 36
• використовувати описаний алгоритм після LZ-алгоритму, що дозво-
лить компактніше зберігати однакові ділянки зображення.
ВИСНОВКИ
1. Запропонований алгоритм стиснення RGB-зображень без втрат за
допомогою палітрування виконує розбиття результату на трендову та шумо-
ву складові. Трендова складова містить наближену палітрову копію зобра-
ження. У шумовій — зберігаються відхилення оригіналу від палітрової ко-
пії. Описаний алгоритм дозволяє стиснути дані при створенні палітри
головним чином завдяки зменшення надлишкової індексації трикомпонент-
ної кольорової моделі.
2. Трендова складова розбиття займає менше третини стиснених даних,
і, тому може бути використана для ефективної прогресивної передачі даних
по мережі. Ефективне стиснення трендової частини можливе традиційними
алгоритмами (наприклад LZ+Huff).
3. Шумова складова розбиття ефективно стискується за допомогою за-
пропонованого алгоритму оптимального розбиття сегментів-паралелепіпе-
дів, що загалом підвищує КС у півтора рази. Таке розбиття дозволяє не
тільки підвищити якість, але й збільшити розміри трендової складової
результату.
4. Розроблений алгоритм пропонує кращі результати стиснення стосо-
вно базового алгоритму на фотореалістичних зображеннях із десятками ти-
сяч кольорів, хоча й поступається на інших типах зображень і відстає від
найкращих на сьогодні алгоритмів стиснення. Ідея палітрування фото-
реалістичних зображень у комбінації з іншими алгоритмами стиснення
дозволяє досягти кращих загальних показників компресії і буде втілюватися
в життя й надалі.
ЛІТЕРАТУРА
1. Сэломон Д. Сжатие данных, изображений и звука. — М.: Техносфера, 2006. —
336 с.
2. Миано Дж. Форматы и алгоритмы сжатия изображений в действии: Учеб. по-
соб. — М.: Триумф, 2003. — 336 с.
3. Методы сжатия данных. Устройство архиваторов, сжатие изображений и ви-
део / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. — М.: ДИАЛОГ–
МИФИ, 2003. — 384 с.
4. Бредихин Д.Ю. Сжатие графики без потерь качества. — 2004. — http://www.
compression.ru/download/articles/i_lless/bredikhin_2004_lossless_image_compr
ession_doc.rar.
5. Ратушняк О.А. Алгоритмы сжатия изображений без потерь с помощью сор-
тировки параллельных блоков // Тез. докл. конф. молодых ученых по мате-
матике, мат. моделированию и информатике. — Новосибирск, 2001. —
С. 48–49.
Надійшла 23.04.2008
|