Lib.ru : Шпортько Олександр Володимирович. Підвищення ефективності стиснення кольорових зображень у форматі Png (укр.)

Повний текст дисертаці§ та автореферат міститься у файлах-додатках
(посилання Иллюстрации/приложения на цій сторінці перед анотацією)

Вступ

Актуальність теми. У сучасному світі зображення є невід'ємною складовою мультимедійно§ інформаці§, що найчастіше створюється, накопичується і зберігається на цифрових носіях та передається каналами зв'язку. Компресія відповідних файлів дає змогу пропорційно підвищити швидкість обміну інформацією по мережі та зменшити обсяги використання дискового простору. Тому проблема підвищення ефективності стиснення зображень не втрачає своє§ актуальності протягом останніх десятиліть і, ймовірно, не втратить у найближчому майбутньому.

На сьогодні для збереження без втрат космічних знімків, фотореалістичних зображень з невисокою роздільною здатністю чи синтезованих ілюстрацій та емблем, у галузях діяльності людини, де спотворення неприпустимі (наприклад, у медицині [8, с. 641] чи картографі§), як один з основних використовується формат PNG [62]. В мережі Інтернет, наприклад, нараховується більше 16 млн. сторінок, що містять зображення у цьому форматі, щороку кількість таких сторінок збільшується на понад 1 млн. Популярності формату PNG сприяють, насамперед, прийнятні показники стиснення та висока швидкість декодування, а саме ці критері§ ефективності є визначальними для форматів графічних файлів. І якщо для переважно§ більшості форматів компресі§ зображень з втратами (наприклад, для JPEG та ін. [28; 22; 38; 60; 65; 77]) можна забезпечити потрібний КС (в роботі коефіцієнт стиснення - це відношення розмірів стиснутого до нестиснутого файлів зображення [37, с. 21], виражене в процентах) за рахунок погіршення якості, то КС у форматах компресі§ зображень без втрат, до яких належить і PNG, залежить, власне, лише від перепадів яскравостей кольорів §х пікселів та самого алгоритму стиснення, не регулюється програмно і становить в середньому лише 30 - 70 %. Тому підвищення ефективності стиснення зображень у форматі PNG, враховуючи поширеність та стрімке збільшення §х кількості, є на сьогодні актуальною задачею.

Теоретичною та методологічною основою роботи стали праці таких вчених, як C. Shannon, D. Knuth, D. Huffman, J. Ziv, A. Lempel, W. Pratt, R. Gonzalez, R. Woods, D. Salomon, J. Miano, T. Boutell, P. Deutsch, Д. Ватолін, О. Ратушняк, М. Смірнов, В. Юкін, а також результати досліджень текстів програм та функціонування існуючого програмного забезпечення для стиснення зображень.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася, керуючись метою та завданнями Національно§ програми інформатизаці§ (Закон Укра§ни N 74/98-ВР від 4 лютого 1998 року), у напрямку тематики науково-дослідно§ роботи "Підвищення ефективності стиснення зображень без втрат у сучасних графічних форматах" (N державно§ реєстраці§ 0110U004001) кафедри інформатики і прикладно§ математики РДГУ. Автором у цій НДР проведено дослідження можливостей підвищення ефективності стиснення зображень у форматі PNG.

Мета і завдання дисертаційно§ роботи. Метою дослідження є зменшення КС та прискорення найтриваліших етапів компресі§ зображень як у межах діючого, так і в модифікованому стандарті формату PNG за допомогою вдосконалення і врахування взаємоді§ використаних та застосування альтернативних чи нових методів і алгоритмів кодування, які кардинально не впливають на час декодування.

Для досягнення поставлено§ мети у роботі розв'язано такі завдання:

1. Дослідження та аналіз ефективності алгоритмів кодування, що використовуються у форматі PNG і програмного забезпечення, яке застосовується для збереження зображень у цьому форматі.

2. Розробка алгоритмів для прискорення виконання найтриваліших етапів стиснення зображень у форматі PNG.

3. Виявлення можливостей та розробка алгоритмів і програмного забезпечення для зменшення КС зображень у діючому стандарті формату PNG.

4. Дослідження можливостей та розробка алгоритму використання декількох ковзаючих вікон для результатів застосування різних предикторів у процесі формування модифікованого розкладу LZ77.

5. Розробка методів для генерування різницевих кольорових моделей, які дають змогу зменшити КС зображень у форматах, що використовують предиктори та контекстно-незалежне кодування.

6. Вивчення можливостей та розробка алгоритму для застосування палітри в процесі стиснення зображень без втрат.

Об'єкт дослідження - процеси стиснення даних без втрат.

Предмет дослідження - методи компресі§ 24-бітних RGB-зображень [29] у форматі PNG. Означена підмножина зображень обрана невипадково, оскільки такі зображення зустрічаються найчастіше. І це не дивно, адже трикомпонентні зображення найкраще відповідають фізіологічним основам кольорового зору людини [31, с. 37], кольорова модель RGB відображає роботу комп'ютерних диспле§в [25, с. 16], а 8-ми бітна частота дискретизаці§ найчастіше використовується у найпоширеніших ОС сімейства Windows [25, с. 17]. Колір довільного піксела таких зображень формується злиттям яскравостей червоно§, зелено§ та синьо§ компоненти, кожна з яких є рівнозначною і подається цілим числом з діапазону [0; 255].

Методи дослідження - алгоритми стиснення зображень розроблено з застосуванням методів теорій кодування та програмування, прогнозовані оцінки довжин кодів блоків обчислено з використанням положень теорі§ інформаці§ та теорі§ ймовірності, вибір варіанту компресі§ для кожного з мінімальних блоків рядків здійснено методом динамічного програмування, оцінювання параметрів нерівномірностей розподілів частот елементів виконано методами математично§ статистики, оцінку складності алгоритмів прискорення стиснення проведено методами теорі§ алгоритмів.

Наукова новизна одержаних результатів. В процесі виконання дисертаційного дослідження створено нові та вдосконалено існуючі методи і алгоритми, які дають змогу зменшити КС зображень без втрат, зокрема:

1. Вперше одержано метод зменшення розміру стиснутого блоку у форматі DEFLATE за допомогою: розрахунку розподілів частот для визначення розмірів альтернативних стиснутих блоків без §х попередньо§ генераці§; вибору найкоротшого блоку з альтернативних; ітеративного відкидання неефективних замін у найкоротшому стиснутому блоці з подальшим його формуванням. В процесі реалізаці§ цього методу вдосконалено (з метою прискорення) метод точного розрахунку розмірів блоків динамічних кодів HUFF.

2. Вперше розроблено метод попереднього аналізу зображень, в якому реалізовано розбиття на мінімальні та однорідні блоки рядків з метою визначення для кожного з них оптимального способу кодування методом динамічного програмування.

3. Вперше розроблені методи генерування альтернативних різницевих кольорових моделей для кожного зображення як з цілими, так і з дійсними коефіцієнтами, які орієнтовані на формати стиснення зображень без втрат, що використовують предиктори та контекстно-незалежне кодування.

4. Вдосконалено метод словникового стиснення для забезпечення можливості одночасного використання результатів застосування декількох альтернативних предикторів та механізм формування "лінивого" і майже оптимального розкладів цього методу на прикладі алгоритму LZ77 з використанням результатів попереднього аналізу зображень.

5. Вдосконалено метод пошуку однакових послідовностей потоку, що використовує хешування, шляхом вибору найкоротших хеш-ланцюгів, реалізація якого дозволила не лише зменшити КС зображень для швидких розкладів словникового алгоритму LZ77, а й суттєво прискорити формування розкладів цього алгоритму загалом.

6. Отримав подальший розвиток метод групового статистичного кодування за допомогою використання палітри в процесі стиснення трикомпонентних зображень без втрат.

Практична цінність дисертаці§. Розроблені методи, алгоритми і способи стиснення зображень без втрат використовуються для підвищення ефективності стиснення у форматі PNG та можуть бути використані з цією ж метою у інших графічних форматах, зокрема, у середньому по набору зображень ACT:

1. Застосування алгоритму вибору найкоротших хеш-ланцюгів у процесі пошуку однакових послідовностей як в одному, так і у декількох словниках дає змогу прискорити формування розкладу LZ77 у випадку аналізу всіх елементів цих ланцюгів більше, ніж у 13 разів, а у разі перегляду до 128 §х елементів - на 9 %.

2. Використання розроблених алгоритмів наближених і точних розрахунків довжини блоків динамічних кодів HUFF без §х генераці§ прискорюють виконання таких обчислень відносно варіанту з формуванням цих кодів на понад 85 %.

3. Реалізація алгоритму мінімізаці§ розміру стиснутих блоків у форматі PNG дозволяє зменшити КС переважно§ більшості синтезованих з шумами та фотореалістичних зображень на 2 - 6 %, хоча й сповільнює кодування на 10 %.

4. Розроблений метод попереднього аналізу зображень з розбиттям на мінімальні та однорідні блоки рядків з метою визначення для кожного з них оптимального способу кодування за допомогою методу динамічного програмування дозволяє зменшити КС відносно швидких варіантів стиснення на понад 3.9 %, сповільнюючи кодування більш ніж у 4.5 рази.

5. Використання алгоритму LZPR у випадку застосування трьох альтернативних ковзаючих вікон LZ77 та формування попіксельного розкладу дає змогу зменшити КС зображень на понад 2.1 % у порівнянні з найкращим на сьогодні способом стиснення у стандарті формату PNG, прискорюючи при цьому кодування у 4.6 рази, а декодування - на 4.3 %.

6. Застосування описаного методу генерування та переходу до альтернативних різницевих кольорових моделей з цілими коефіцієнтами для кожного зображення у форматі PNG дає змогу зменшити КС на 4.6 % (максимально - на понад 12 %) в основному за рахунок фотореалістичних знімків, хоча й сповільнює кодування більше, ніж на 10 %.

7. Розроблений алгоритм використання палітри для групового статистичного кодування трикомпонентних зображень без втрат дозволяє додатково зменшити §х КС на 1.4 % та прискорити декодування на понад 7 %, хоча й сповільнює кодування на 38 %.

Реалізація результатів дослідження. Розроблені з використанням результатів дисертаці§ утиліта MinPNG для створення зображень у форматі PNG з низькими КС і комплекс програм ModifyPNG для компресі§ зображень з застосуванням досліджених модифікацій цього формату та §х вихідні тексти доступні для завантаження з Web-сторінки http:\\apserver.org.ua/peregl.php?=5 і розповсюджуються як безкоштовне сервісне програмне забезпечення. Основні фрагменти коду цих програм захищені двома авторськими свідоцтвами (додаток А). Утиліта MinPNG застосовується як на домашніх ПК, так і в організаціях, зокрема в Рівненській обласній клінічній лікарні, інженерному центрі "Імпульс" та Рівненській міській бізнес-довідці (ТзОВ-фірма "ВІЗА"). Алгоритм вибору найкоротших хеш-ланцюгів використовується в процесі розробки прикладного програмного забезпечення у ВАТ "Алмаз ССС". Відповідні акти впровадження містяться у додатку Б.

Основні результати дисертаційно§ роботи використовуються у спецкурсі "Проблеми оптимізаці§ і керування процесами", що вивчається студентами спеціальностей "Інформатика" та "Прикладна математика" факультету математики та інформатики, у процесі викладання інших дисциплін в РДГУ (додаток В).

Особистий внесок здобувача. Всі наукові результати, подані в дисертаці§, отримані здобувачем особисто. У працях, опублікованих у співавторстві, здобувачеві, окрім отримання та аналізу результатів числових експериментів, належать: [4; 5] - іде§ та реалізаці§ запропонованих алгоритмів; [6] - вибір і адаптація модифікацій формату PNG та §х комбінацій.

Апробація результатів дисертаці§. Результати дослідження та основні положення роботи доповідалися і обговорювалися на: секці§ математичного моделювання та обчислювальних методів XIX, XX, XXI наукових сесій наукового товариства ім. Шевченка (Рівне, березень 2008-2010 рр.); звітних наукових конференціях РДГУ (Рівне, березень 2008 р., лютий 2009 та 2010 р.); науково-технічній конференці§ "Обчислювальні методи і системи перетворення інформаці§" (Львів, жовтень 2010 р.) [6]; X, XI, XII Міжнародних науково-технічних конференціях "Системний аналіз та інформаційні технологі§" (Ки§в, травень 2008-2010 рр.) [48; 54; 57]; III, IV Міжнародних конференціях "Комп'ютерні науки та інформаційні технологі§" (Львів, вересень 2008 р., жовтень 2009 р.) [49; 56]; IX Всеукра§нській міжнародній конференці§ з оброблення сигналів і зображень та розпізнання образів (Ки§в, листопад 2008 р.). У повному обсязі результати дослідження доповідалися і обговорювалися на: засіданні наукового семінару секці§ інформатики при Західному науковому центрі НАН та МОН Укра§ни (Львів, травень 2010 р.); засіданні наукового семінару "Образний комп'ютер" при Міжнародному науково-навчальному центрі інформаційних технологій і систем НАН та МОН Укра§ни (Ки§в, червень 2010 р.); засіданні наукового семінару кафедри інформаційних систем КНУ ім. Т. Г. Шевченка (Ки§в, вересень 2010 р.); розширеному засіданні наукового семінару кафедри інформатики та прикладно§ математики РДГУ (Рівне, жовтень 2010 р.).

Публікаці§. Основні результати дисертаційного дослідження опубліковані у 20 наукових працях, з них 2 - авторські свідоцтва, 12 статей (в т. ч. 11 - у фахових виданнях з технічних наук, включених до переліку ВАК Укра§ни), 3 - матеріали доповідей та 3 - тези доповідей на міжнародних конференціях.

Шпортько Олександр Володимирович Підвищення ефективності стиснення кольорових зображень у форматі Png (укр.)

Шпортько Олександр Володимирович
Підвищення ефективності стиснення кольорових зображень у форматі Png (укр.)