# П╕двищення ефективност╕ стиснення кольорових зображень у формат╕ Png (укр.)

Олександр Володимирович Шпортько

Шпортько О. В. П╕двищення ефективност╕ стиснення кольорових зображень у формат╕ PNG : дис. ... канд. техн. наук : спец. 01.05.03 "Математичне та програмне забезпечення обчислювальних машин ╕ систем" / О. В. Шпортько ; Р╕вненський державний гуман╕тарний ун╕верситет. - Р╕вне, 2010. - 195 с. Дисертац╕я присвячена питанню п╕двищення ефективност╕ стиснення без втрат у растрових граф╕чних форматах (на приклад╕ формату PNG), що використовують предиктори, словниковий алгоритм LZ77, контекстно-незалежне кодування та ╕х комб╕нац╕╕ за допомогою вдосконалення ╕ врахування вза╓мод╕╕ цих та застосування альтернативних чи нових метод╕в ╕ алгоритм╕в кодування. У напрямку прискорення кодування у формат╕ PNG вдосконалено метод пошуку однакових посл╕довностей потоку даних шляхом вибору найкоротших хеш-ланцюг╕в та метод точного розрахунку розм╕р╕в блок╕в динам╕чних код╕в HUFF. Для зменшення коеф╕ц╕╓нт╕в стиснення у затвердженому стандарт╕ формату PNG у середньому на понад 3.9 % вперше реал╕зовано п╕сляпроцесний метод скорочення розм╕ру стиснутого блоку у формат╕ DEFLATE ╕ метод попереднього анал╕зу зображень з розбиттям на м╕н╕мальн╕ та однор╕дн╕ блоки рядк╕в. У напрямку внесення модиф╕кац╕й у цей формат розроблено методи для генерування р╕зницевих кольорових моделей як з ц╕лими, так ╕ з д╕йсними коеф╕ц╕╓нтами, вдосконалено структуру розкладу алгоритму LZ77 та використано пал╕тру для групового статистичного кодування, що дало змогу у випадку ╕х сум╕сно╕ реал╕зац╕╕ з алгоритмом коригування значень предиктора в середньому зменшити коеф╕ц╕╓нт стиснення б╕льше, н╕ж на 12 %. Ключов╕ слова: кольорове зображення, стиснення без втрат, граф╕чний формат 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 - тези допов╕дей на м╕жнародних конференц╕ях.


Повний текст дисертац╕§ та автореферат м╕ститься у файлах-додатках

(посилання Иллюстрации/приложения на ц╕й стор╕нц╕ перед анотац╕╓ю)