Обґрунтування двох розроблених алгоритмів, аналіз результатів їх застосування для прискорення тривалих операцій в процесі кодування зображень у форматі PNG. Алгоритм мінімізації розміру стиснутих блоків. Організація вибору предикторів для рядків пікселів.
Аннотация к работе
В мережі Інтернет, наприклад, нараховується більше 16 млн. сторінок, що містять зображення у цьому форматі, щороку кількість таких сторінок збільшується на понад 1 млн. Популярності формату PNG сприяють, насамперед, прийнятні показники стиснення та висока швидкість декодування, а саме ці критерії ефективності є визначальними для форматів графічних файлів. На цей час для переважної більшості форматів компресії зображень з втратами (наприклад, для JPEG) можна забезпечити потрібний КС (в роботі коефіцієнт стиснення - це відношення розмірів стиснутого до нестиснутого файлів зображення) за рахунок погіршення якості, а КС у форматах компресії зображень без втрат, до яких належить і PNG, залежить, власне, лише від перепадів яскравостей кольорів їх пікселів та самого алгоритму стиснення, не регулюється програмно і становить в середньому лише 30 - 70 %. Дослідження та аналіз ефективності алгоритмів кодування, що використовуються у форматі PNG і програмного забезпечення, яке застосовується для збереження зображень у цьому форматі. Розробка методів для генерування різницевих кольорових моделей, які дають змогу зменшити КС зображень у форматах, що використовують предиктори та контекстно-незалежне кодування. Методи дослідження - алгоритми стиснення зображень розроблено з застосуванням методів теорій кодування та програмування, прогнозовані оцінки довжин кодів блоків обчислено з використанням положень теорії інформації та теорії ймовірності, вибір варіанту компресії для кожного з мінімальних блоків рядків здійснено методом динамічного програмування, оцінювання параметрів нерівномірностей розподілів частот елементів виконано методами математичної статистики, оцінку складності алгоритмів прискорення стиснення проведено методами теорії алгоритмів.З цією метою: розглянуто принципи дії способів кодування, що послідовно використовуються у форматі PNG (предикторів і контекстно-залежного словникового алгоритму LZ77, які зменшують міжелементну надлишковість, та контекстно-незалежного канонічного алгоритму HUFF, котрий усуває кодову надлишковість), різновиди та особливості алгоритмів для їх реалізації; проведений аналіз літературних джерел, у яких досліджувалися ці алгоритми; вказано тестові набори файлів зображень (ACT і KTCI), апаратне, системне та прикладне програмне забезпечення для апробації запропонованих у роботі алгоритмів; конкретизовано та обґрунтовано завдання дослідження. (де - значення i-го елемента, а логарифм тут і надалі береться за основою 2) і досягає цього значення лише у випадку, коли всі - цілі числа, а ентропія джерела зменшується зі збільшенням нерівномірності розподілу ймовірностей між елементами (що й виконують предиктори) і, по-друге, в процесі використання предиктора обчислюють і надалі кодують відхилення значення чергової компоненти піксела від прогнозованого цією функцією значення , тобто .(2) Зрозуміло, що розраховувати довжину цього блоку для чергової послідовності елементів можна, безпосередньо генеруючи та використовуючи ці коди: підрахувати абсолютні частоти кожного елемента; сформувати за цими частотами коди HUFF; визначити їх довжини та обчислити суму добутків частоти кожного елемента на довжину його коду HUFF. Тому, враховуючи, що у стиснутих блоках PNG-файлів зберігаються коди HUFF літералів/довжин та зміщень і їх додаткові біти, заміна q довжини lenq, що виконується, починаючи з літерала sk за зміщення offsetq, ефективна лише тоді, коли ,(4) де lm - довжина коду HUFF літерала/довжини заміни m, dm - кількість додаткових бітів для запису довжини заміни m, - довжина коду HUFF зміщення m, - кількість додаткових бітів для запису зміщення m. Тому далі в підрозділі описується пять розроблених способів вибору предикторів для рядків пікселів: безпосередній ентропійний спосіб, який обирає для рядка пікселів предиктор, що породжує мінімальну довжину ентропійного коду (3); ентропійний спосіб після застосування коротких замін LZ77, що виконує аналогічний вибір після емуляції цих замін для результатів дії предикторів; комбінований ентропійний спосіб, який порівнює між собою КС двох попередніх способів; комбінований ентропійний спосіб з додатковим попіксельним розкладом алгоритмом LZ77 оригіналу зображення, що обирає предиктор за мінімальною ентропією лише для тих рядків, для яких, за результатами попереднього прогнозування, стиснення алгоритмом LZ77 виявляється неефективним; ентропійний спосіб з прогнозуванням результатів розкладів алгоритму LZ77, який емулює стиснення у форматі PNG з використанням результатів застосування вибраних предикторів декількох попередніх рядків.В дисертації розвязано актуальну наукову задачу підвищення ефективності стиснення зображень без втрат у растрових графічних форматах, зокрема, і у форматі PNG, що використовують предиктори, словниковий алгоритм LZ77, контекстно-незалежне кодування та їх комбінування за допомогою вдосконалення і врахування взаємодії цих та застосування альтернативних чи нових методів і алгоритмів кодування. Вдосконалено метод пошуку однакових послідовностей