Підвищення ефективності стиснення кольорових зображень у форматі PNG
Обґрунтування двох розроблених алгоритмів, аналіз результатів їх застосування для прискорення тривалих операцій в процесі кодування зображень у форматі PNG. Алгоритм мінімізації розміру стиснутих блоків. Організація вибору предикторів для рядків пікселів.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | автореферат |
| Язык | украинский |
| Дата добавления | 13.08.2015 |
| Размер файла | 214,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Національний університет “Львівська політехніка”
УДК 004.04
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Підвищення ефективності стиснення кольорових зображень у форматі PNG
01.05.03 математичне та програмне забезпечення
обчислювальних машин і систем
ШПОРТЬКО Олександр Володимирович
Львів - 2011
Дисертацією є рукопис.
Робота виконана у Рівненському державному гуманітарному університеті Міністерства освіти і науки, молоді та спорту України.
Науковий керівник:доктор технічних наук, професор
Бомба Андрій Ярославович,
Рівненський державний гуманітарний університет,
професор кафедри інформатики та прикладної математики.
Офіційні опоненти:доктор технічних наук, професор
Воробель Роман Антонович,
Фізико-механічний інститут ім. Г. В. Карпенка
НАН України,
завідувач відділу обчислювальних методів і
систем перетворення інформації;
доктор фізико-математичних наук, професор
Провотар Олександр Іванович,
Київський національний університет ім. Тараса Шевченка,
завідувач кафедри інформаційних систем
факультету кібернетики.
Захист відбудеться 26 травня 2011 р. о 16 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, м. Львів, вул. С. Бандери, 12).
З дисертацією можна ознайомитись у науково-технічній бібліотеці Національного університету “Львівська політехніка” (79013, м. Львів, вул. Професорська, 1).
Автореферат розіслано 22 квітня 2011 р.
Вчений секретар
спеціалізованої вченої ради,
доктор технічних наук, професорР. А. Бунь
Загальна характеристика роботи
Актуальність теми. У сучасному світі зображення є невід'ємною складовою мультимедійної інформації, що найчастіше створюється, накопичується і зберігається на цифрових носіях та передається каналами зв'язку. Компресія відповідних файлів дає змогу пропорційно підвищити швидкість обміну інформацією по мережі та зменшити обсяги використання дискового простору. Тому проблема підвищення ефективності стиснення зображень не втрачає своєї актуальності останні десятиліття і, ймовірно, не втратить у найближчому майбутньому.
На сьогодні для збереження без втрат фотореалістичних зображень з невисокою роздільною здатністю чи синтезованих ілюстрацій та емблем, космічних знімків, у галузях діяльності людини, де спотворення неприпустимі (наприклад, у медицині чи картографії), як один з основних використовується формат PNG. В мережі Інтернет, наприклад, нараховується більше 16 млн. сторінок, що містять зображення у цьому форматі, щороку кількість таких сторінок збільшується на понад 1 млн. Популярності формату PNG сприяють, насамперед, прийнятні показники стиснення та висока швидкість декодування, а саме ці критерії ефективності є визначальними для форматів графічних файлів. На цей час для переважної більшості форматів компресії зображень з втратами (наприклад, для JPEG) можна забезпечити потрібний КС (в роботі коефіцієнт стиснення - це відношення розмірів стиснутого до нестиснутого файлів зображення) за рахунок погіршення якості, а КС у форматах компресії зображень без втрат, до яких належить і PNG, залежить, власне, лише від перепадів яскравостей кольорів їх пікселів та самого алгоритму стиснення, не регулюється програмно і становить в середньому лише 30 - 70 %. Тому підвищення ефективності стиснення зображень у форматі PNG, враховуючи поширеність та стрімке збільшення їх кількості, є на сьогодні актуальною задачею.
Теоретичною та методологічною основою роботи стали праці таких вчених, як C. Shannon, D. Knuth, D. Huffman (HUFF), J. Ziv, A. Lempel, W. Pratt, R. Gonzalez, R. Woods, D. Salomon, J. Miano, T. Boutell, P. Deutsch, Д. Ватолін, О. Ратушняк, М. Смірнов, В. Юкін, а також результати досліджень текстів програм та функціонування існуючого програмного забезпечення для стиснення зображень.
Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася, керуючись метою та завданнями Національної програми інформатизації (Закон України № 74/98-ВР від 4 лютого 1998 року), у напрямку тематики науково-дослідної роботи "Підвищення ефективності стиснення зображень без втрат у сучасних графічних форматах" (№ державної реєстрації 0110U004001) кафедри інформатики і прикладної математики Рівненського державного гуманітарного університету (РДГУ). Автором у цій НДР проведено дослідження можливостей підвищення ефективності стиснення зображень у форматі PNG.
Мета і завдання дисертаційної роботи. Метою дослідження є зменшення КС та прискорення найтриваліших етапів компресії зображень як у межах діючого, так і в модифікованому стандарті формату PNG за допомогою вдосконалення і врахування взаємодії використаних та застосування альтернативних чи нових методів і алгоритмів кодування, які кардинально не впливають на час декодування.
Для досягнення поставленої мети у роботі розв'язано такі завдання:
1. Дослідження та аналіз ефективності алгоритмів кодування, що використовуються у форматі PNG і програмного забезпечення, яке застосовується для збереження зображень у цьому форматі.
2. Розробка алгоритмів для прискорення виконання найтриваліших етапів стиснення зображень у форматі PNG.
3. Виявлення можливостей та розробка алгоритмів і програмного забезпечення для зменшення КС зображень у діючому стандарті формату PNG.
4. Дослідження можливостей та розробка алгоритму використання декількох ковзних вікон для результатів застосування різних предикторів у процесі формування модифікованого розкладу LZ77.
5. Розробка методів для генерування різницевих кольорових моделей, які дають змогу зменшити КС зображень у форматах, що використовують предиктори та контекстно-незалежне кодування.
6. Вивчення можливостей та розробка алгоритму для застосування палітри в процесі стиснення зображень без втрат.
Об'єкт дослідження - процеси стиснення даних без втрат.
Предмет дослідження - методи компресії 24-бітних RGB-зображень у форматі PNG.
Методи дослідження - алгоритми стиснення зображень розроблено з застосуванням методів теорій кодування та програмування, прогнозовані оцінки довжин кодів блоків обчислено з використанням положень теорії інформації та теорії ймовірності, вибір варіанту компресії для кожного з мінімальних блоків рядків здійснено методом динамічного програмування, оцінювання параметрів нерівномірностей розподілів частот елементів виконано методами математичної статистики, оцінку складності алгоритмів прискорення стиснення проведено методами теорії алгоритмів.
Наукова новизна одержаних результатів. В процесі виконання дисертаційного дослідження створено нові та вдосконалено існуючі методи і алгоритми, які дають змогу зменшити КС зображень без втрат, зокрема:
1. Вперше одержано метод зменшення розміру стиснутого блоку у форматі DEFLATE за допомогою: розрахунку розподілів частот для визначення розмірів альтернативних стиснутих блоків без їх попередньої генерації; вибору найкоротшого блоку з альтернативних; ітеративного відкидання неефективних замін у найкоротшому стиснутому блоці з подальшим його формуванням. В процесі реалізації цього методу вдосконалено (з метою прискорення) метод точного розрахунку розмірів блоків динамічних кодів HUFF шляхом врахування принципу генерації цих кодів.
2. Вперше розроблено метод попереднього аналізу зображень, в якому реалізовано розбиття на мінімальні та однорідні блоки рядків з метою визначення для кожного з них оптимального способу кодування методом динамічного програмування.
3. Вперше розроблено методи генерування альтернативних різницевих кольорових моделей для кожного зображення як з цілими, так і з дійсними коефіцієнтами, які орієнтовані на формати стиснення зображень без втрат, що використовують предиктори та контекстно-незалежне кодування.
4. Вдосконалено метод словникового стиснення для забезпечення можливості одночасного використання результатів застосування декількох альтернативних предикторів та механізм формування "лінивого" і майже оптимального розкладів цього методу на прикладі алгоритму LZ77 з використанням результатів попереднього аналізу зображень.
5. Вдосконалено метод пошуку однакових послідовностей елементів потоку, що використовує хешування, шляхом вибору найкоротших хеш-ланцюгів, реалізація якого дозволила не лише зменшити КС зображень для швидких розкладів словникового алгоритму LZ77, а й суттєво прискорити формування розкладів цього алгоритму загалом.
6. Отримав подальший розвиток метод групового статистичного кодування за допомогою використання палітри в процесі стиснення трикомпонентних зображень без втрат.
Практична цінність дисертації. Розроблені методи, алгоритми і способи для стиснення зображень без втрат використовуються для підвищення ефективності стиснення у форматі PNG та можуть бути використані з цією ж метою у інших графічних форматах. Зокрема, у середньому по набору зображень Archive Comparison Test (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 і розповсюджуються як безкоштовне сервісне програмне забезпечення. Основні фрагменти коду цих програм захищені двома авторськими свідоцтвами [13; 14]. Утиліта MinPNG застосовується як на домашніх ПК, так і в організаціях, зокрема в Рівненській обласній клінічній лікарні, інженерному центрі "Імпульс" та Рівненській міській бізнес-довідці (ТзОВ-фірма "ВІЗА"). Алгоритм вибору найкоротших хеш-ланцюгів використовується в процесі розробки прикладного програмного забезпечення у ВАТ "Алмаз ССС".
Основні результати дисертаційної роботи використовуються у спецкурсі "Проблеми оптимізації і керування процесами", що вивчається студентами спеціальностей "Інформатика" та "Прикладна математика" факультету математики та інформатики, у процесі викладання інших дисциплін в РДГУ.
Особистий внесок здобувача. Всі наукові результати, подані в дисертації, отримані здобувачем особисто. У працях, опублікованих у співавторстві, здобувачеві, окрім отримання та аналізу результатів числових експериментів, належать: [8, 11] - ідеї та реалізації запропонованих алгоритмів; [15] - вибір і адаптація модифікацій формату PNG та їх комбінацій.
Апробація результатів дисертації. Результати дослідження та основні положення роботи доповідалися і обговорювалися на: IX Всеукраїнській міжнародній конференції з оброблення сигналів і зображень та розпізнання образів (Київ, листопад 2008 р.); X, XI, XII Міжнародних науково-технічних конференціях "Системний аналіз та інформаційні технології" (Київ, травень 2008-2010 рр.) [18-20]; III, IV Міжнародних конференціях "Комп'ютерні науки та інформаційні технології" (Львів, вересень 2008 р., жовтень 2009 р.) [16, 17]; науково-технічній конференції "Обчислювальні методи і системи перетворення інформації" (Львів, жовтень 2010 р.) [15]; секції математичного моделювання та обчислювальних методів XIX, XX, XXI наукових сесій наукового товариства ім. Шевченка (Рівне, березень 2008-2010 рр.); звітних наукових конференціях РДГУ (Рівне, березень 2008 р., лютий 2009 та 2010 рр.). У повному обсязі результати дослідження доповідалися і обговорювалися на: засіданні наукового семінару секції інформатики при Західному науковому центрі НАН та МОН України (Львів, травень 2010 р.); засіданні наукового семінару "Образний комп'ютер" при Міжнародному науково-навчальному центрі інформаційних технологій і систем НАН та МОН України (Київ, червень 2010 р.); засіданні наукового семінару кафедри інформаційних систем КНУ ім. Т. Г. Шевченка (Київ, вересень 2010 р.); розширеному засіданні наукового семінару кафедри інформатики та прикладної математики РДГУ (Рівне, жовтень 2010 р.).
Публікації. Основні результати дисертаційного дослідження опубліковані у 20 наукових працях, з них 2 авторські свідоцтва, 12 статей (в т. ч. 11 у фахових виданнях з технічних наук, включених до переліку ВАК України), 3 матеріали доповідей та 3 тези доповідей на міжнародних конференціях.
Структура та обсяг роботи. Дисертація складається з вступу, чотирьох розділів, висновків, додатків та списку використаних джерел. Робота містить 145 сторінок основного тексту, 24 рисунки на 11 сторінках, 52 таблиці на 25 сторінках, список використаних джерел з 79 найменувань на 8 сторінках, 6 додатків на 38 сторінках. Загальний обсяг дисертації - 195 сторінок.
Основний зміст роботи
У вступі подано загальну характеристику дисертації: обґрунтовано актуальність теми; визначено зв'язок роботи з науковими програмами, планами, темами; сформульовано мету та основні завдання дослідження; вказано наукову новизну і практичне значення одержаних результатів; означено особистий внесок та наведено дані про публікації здобувача.
У першому розділі визначено шляхи підвищення ефективності стиснення зображень у форматі PNG. З цією метою: розглянуто принципи дії способів кодування, що послідовно використовуються у форматі PNG (предикторів і контекстно-залежного словникового алгоритму LZ77, які зменшують міжелементну надлишковість, та контекстно-незалежного канонічного алгоритму HUFF, котрий усуває кодову надлишковість), різновиди та особливості алгоритмів для їх реалізації; проведений аналіз літературних джерел, у яких досліджувалися ці алгоритми; вказано тестові набори файлів зображень (ACT і KTCI), апаратне, системне та прикладне програмне забезпечення для апробації запропонованих у роботі алгоритмів; конкретизовано та обґрунтовано завдання дослідження.
У розділі наголошено, що, по-перше, середня довжина коду HUFF не може бути меншою ентропії джерела
(1)
(де - значення i-го елемента, а логарифм тут і надалі береться за основою 2) і досягає цього значення лише у випадку, коли всі - цілі числа, а ентропія джерела зменшується зі збільшенням нерівномірності розподілу ймовірностей між елементами (що й виконують предиктори) і, по-друге, в процесі використання предиктора обчислюють і надалі кодують відхилення значення чергової компоненти піксела від прогнозованого цією функцією значення , тобто
.(2)
Другий розділ роботи містить обґрунтування двох розроблених алгоритмів та аналіз результатів їх застосування для прискорення тривалих операцій в процесі кодування зображень у форматі PNG.
2.1. Алгоритм вибору найкоротших хеш-ланцюгів у процесі пошуку однакових послідовностей для формування розкладу алгоритму LZ77, який розроблений з метою прискорення пошуку найдовшої однакової послідовності у словнику для послідовності елементів буфера. Нехай для послідовності елементів буфера s1 ... slen довжини len (len>=lenKey, де lenKey - кількість елементів ключа) у результаті перегляду хеш-ланцюга вже знайдена однакова послідовність у словнику. Очевидно, що метою подальшого пошуку є відшукання у словнику однакової послідовності довжини хоча б len+1 для послідовності елементів буфера s1 ... slen+1, яку назвемо розширеною. Основна ідея цього алгоритму полягає в тому, що пошук розширеної послідовності у словнику можна продовжити не лише серед послідовностей, в яких ключі початку співпадають з ключем початку буфера s1 ... slenKey, а й серед послідовностей, в яких ключі з другого елемента співпадають з ключем з другого елемента розширеної послідовності s2 ... slenKey+1, або ключі з третього елемента співпадають з ключем з третього елемента розширеної послідовності s3 ... slenKey+2 і т.д. аж до ключа slen-lenKey+2 ... slen+1. Тобто подальший пошук можна виконувати по хеш-ланцюгах довільного ключа, що повністю належить розширеній послідовності буфера. Певна річ, що аналізувати неопрацьовані ключі розширеної послідовності буфера та переходити до елементів іншого хеш-ланцюга доцільно лише тоді, коли їх кількості менші від числа елементів, які залишилося переглянути в активному хеш-ланцюгу. Застосування даного алгоритму дає змогу, наприклад, прискорити формування "жадібного" розкладу алгоритму LZ77 для синтезованих зображень у випадку аналізу всіх елементів хеш-ланцюгів максимум у 30 разів.
2.2. Алгоритми розрахунків довжин блоків кодів HUFF. Зрозуміло, що розраховувати довжину цього блоку для чергової послідовності елементів можна, безпосередньо генеруючи та використовуючи ці коди: підрахувати абсолютні частоти кожного елемента; сформувати за цими частотами коди HUFF; визначити їх довжини та обчислити суму добутків частоти кожного елемента на довжину його коду HUFF. На практиці ж розраховувати довжину блоку кодів HUFF можна значно швидше, безпосередньо не генеруючи ці коди для кожного елемента. Розглянемо два способи виконання таких розрахунків.
2.2.1. Враховуючи, що середня довжина коду HUFF близька до ентропії, наближено обчислювати довжину блоку цих кодів доцільно за допомогою довжини ентропійного коду. Нехай кожен з елементів зустрічається разів в послідовності довжини . Згідно статистичного означення ймовірності, , тому загальна довжина ентропійного коду послідовності, враховуючи (1), наближається до значення
.(3)
Застосування цієї формули для наближеного розрахунку довжини блоків кодів HUFF дає змогу прискорити такі обчислення відносно варіанту безпосередньої генерації для блоків літералів/довжин в середньому на 96.5 %, а для блоків зміщень - на 80.8 %. Додатково прискорити такі розрахунки відповідно на 0.3 % і на 0.5 % можливо за допомогою масиву значень добутків малих частот на їх двійкові логарифми (для частот до 15 включно).
2.2.2. Для точного обчислення довжин блоків кодів HUFF в роботі проаналізований ітеративний принцип генерації цих кодів. Встановлено, що внаслідок поєднання двох найменших частот довжина блоку кодів HUFF збільшується на суму цих частот. Цей принцип дозволяє ітеративно обчислювати розмір таких блоків без генерації самих кодів елементів: до отримання однієї частоти серед всіх додатних частот знаходимо дві найменші, збільшуємо довжину блоку на суму цих частот і надалі замість цих двох частот розглядаємо їх суму. З метою прискорення цих розрахунків, в роботі рекомендується сортувати додатні частоти елементів за спаданням та ітеративно вставляти суму двох останніх частот перед попередньою аналогічною сумою. Застосування такого алгоритму дає змогу прискорити точні розрахунки довжин блоків кодів HUFF відносно варіанту безпосередньої генерації для блоків літералів/довжин в середньому на 87 %, а для блоків зміщень - на 78 %. Застосування однозв'язного списку в процесі вставок сум двох найменших частот дає змогу додатково прискорити ці розрахунки відповідно на 5 % і 4 %, а окреме опрацювання малих частот - ще на 4 % і 3.5 %.
У третьому розділі наведено п'ять розроблених підходів для зменшення КС зображень у діючому стандарті формату PNG.
3.1. Алгоритм мінімізації розміру стиснутих блоків базується на відкиданні неефективних замін розкладу LZ77, що замінюються відповідними літералами. Заміни LZ77 вважаються ефективними, якщо вони записуються не більшою кількістю бітів, ніж окремі літерали, які вони замінюють. Тому, враховуючи, що у стиснутих блоках PNG-файлів зберігаються коди HUFF літералів/довжин та зміщень і їх додаткові біти, заміна q довжини lenq, що виконується, починаючи з літерала sk за зміщення offsetq, ефективна лише тоді, коли
,(4)
де lm - довжина коду HUFF літерала/довжини заміни m, dm - кількість додаткових бітів для запису довжини заміни m, - довжина коду HUFF зміщення m, - кількість додаткових бітів для запису зміщення m. За результатами дослідження ефективності замін LZ77 різної довжини встановлено, що короткі заміни виявляються ефективними, як правило, для стиснутих блоків, в яких інші короткі заміни тієї ж довжини теж враховуються. Тому для кожного вхідного блоку даних пропонується такий алгоритм мінімізації розміру відповідного стиснутого блоку: створити альтернативні стиснуті блоки з різними максимальними довжинами неврахованих замін; обрати серед них найкоротший блок (використовуючи алгоритми попереднього розділу); ітеративно зменшити його довжину; використати сформований блок для зберігання даних у PNG-файлі.
Зменшення довжини обраного блоку з альтернативних можливе за рахунок відкидання неефективних врахованих та врахування ефективних відкинутих замін згідно (4). Але врахування ефективних замін зменшує частоти окремих елементів і, відповідно, може збільшити після перерахунку довжини їх кодів HUFF. Тому серед замін, неефективних з попередніми кодами HUFF, можуть виявитися ефективні з перерахованими такими кодами. Відкидання ж неефективних замін збільшує частоти окремих елементів та, відповідно, може зменшити після перерахунку довжини їх кодів HUFF, тому серед замін, ефективних з попередніми кодами HUFF, можуть виявитися неефективні з перерахованими такими кодами. Ось чому для обраного найкоротшого блоку з альтернативних у випадку, коли він не враховує всі заміни, доцільно після аналізу ефективності замін, коротших 24, перерахувати довжини кодів HUFF елементів розподілів та ітеративно проаналізувати ефективність цих замін ще раз. Додаткові ітерації для перевірки ефективності замін недоцільні, оскільки вони суттєво не впливають на довжину обраного стиснутого блоку та значно сповільнюють виконання алгоритму.
Застосування даного алгоритму дає змогу для базової програми зменшити КС переважної більшості синтезованих з шумами та фотореалістичних зображень, в яких всі заміни не враховуються, на 2 - 6 %, хоча й сповільнює кодування в середньому на 10 %. Цей алгоритм використовується також у процесі попереднього аналізу зображень для визначення прогнозованих довжин кодів елементів/довжин та зміщень модифікованого "лінивого" та майже оптимального розкладів LZ77.
3.2. Організація вибору предикторів для рядків пікселів. На початку цього підрозділу проаналізовано вплив окремих предикторів, алгоритму LZ77 та кодування HUFF на КС зображень у форматі PNG. Встановлено, що ключову роль в процесі стиснення різних зображень і навіть окремих їх фрагментів можуть відігравати як алгоритм LZ77, так і кодування HUFF, причому перший з цих способів кодування найкраще проявляє себе на синтезованих, а другий - на фотореалістичних фрагментах. Тому розклад LZ77 та кодування HUFF у поєднанні з алгоритмом мінімізації розміру стиснутих блоків потрібно застосовувати в процесі стиснення кожного зображення. алгоритм кодування піксель зображення
Крім цього, як показали результати експериментів, для кожного рядка зображення слід обирати той предиктор, який дозволить підсилити дію ключового алгоритму стиснення чергового фрагменту і допоможе цим забезпечити найменший загальний КС. Зокрема, для синтезованих фрагментів зображень найменші КС забезпечує NonePredict, LeftPredict чи RightPredict, а для фотореалістичних - AveragePredict чи PaethPredict. Ось чому не існує універсального предиктора, застосування якого сприяло б найкращому стисненню всіх типів зображень. Навіть для суміжних фрагментів зображень найефективнішими можуть виявитися різні предиктори. Тому далі в підрозділі описується п'ять розроблених способів вибору предикторів для рядків пікселів: безпосередній ентропійний спосіб, який обирає для рядка пікселів предиктор, що породжує мінімальну довжину ентропійного коду (3); ентропійний спосіб після застосування коротких замін LZ77, що виконує аналогічний вибір після емуляції цих замін для результатів дії предикторів; комбінований ентропійний спосіб, який порівнює між собою КС двох попередніх способів; комбінований ентропійний спосіб з додатковим попіксельним розкладом алгоритмом LZ77 оригіналу зображення, що обирає предиктор за мінімальною ентропією лише для тих рядків, для яких, за результатами попереднього прогнозування, стиснення алгоритмом LZ77 виявляється неефективним; ентропійний спосіб з прогнозуванням результатів розкладів алгоритму LZ77, який емулює стиснення у форматі PNG з використанням результатів застосування вибраних предикторів декількох попередніх рядків. Перші три з цих п'яти способів вибору предикторів для рядків пікселів орієнтуються на кодування HUFF, два останніх - додатково намагаються спрогнозувати результати розкладу LZ77. Порівняння результатів застосування цих п'яти способів з розробленими раніше іншими дослідниками показало, що для кожного рядка зображення найефективнішим може виявитися один з п'яти варіантів компресії: без застосування предикторів, з використанням LeftPredict, з застосуванням RightPredict, з використанням безпосереднього ентропійного способу вибору предикторів та з застосуванням ентропійного способу вибору предикторів після імітації коротких замін LZ77.
3.3. Алгоритми фрагментування, які вдосконалено та розроблено в роботі, орієнтовані на зменшення КС кодування HUFF за рахунок збільшення нерівномірностей розподілів в результаті зміщення меж як між блоками рядків зображення, так і між частинами розкладу LZ77. Застосування досліджених алгоритмів фрагментування дало змогу зменшити середній КС зображень лише на соті долі відсотка, що вказує на однорідність результатів дії предикторів. Для подальшого практичного використання обрано розроблений алгоритм розбиття на блоки рядків, оскільки він має найвищу, у порівнянні з іншими дослідженими алгоритмами фрагментування, швидкість виконання.
3.4. Для зменшення КС розкладів алгоритму LZ77 в роботі розроблено два підходи: алгоритм мінімізації зміщень таких розкладів та алгоритм врахування прогнозованих довжин кодів елементів розподілів в процесі формування модифікованого "лінивого" / майже оптимального розкладів цього алгоритму. Застосування першого з цих підходів скорочує відставання від результатів програми з майже оптимальним розкладом у середньому на 15%, а другого - додатково зменшує КС у середньому на 0.1 %.
3.5. Алгоритм попереднього аналізу зображень з розбиттям на мінімальні та однорідні блоки рядків застосовується для розбиття зображень на однорідні блоки та визначення для кожного з них найефективнішого (з п'яти зазначених вище) варіанту компресії з використанням методу динамічного програмування. Цей алгоритм складається з наступних кроків.
Ш Визначити для кожного рядка пікселів номер предиктора, що забезпечує мінімальний ентропійний КС окремих елементів та номер предиктора, який дає змогу досягнути мінімального КС після виконання коротких замін LZ77. Запам'ятати для кожного рядка частоти окремих елементів після застосування першого з цих предикторів.
Ш Віднести кожен рядок до окремого мінімального блоку рядків.
Ш Ітеративно, за допомогою збережених частот елементів, поєднувати між собою суміжні мінімальні блоки рядків, що забезпечують мінімальне збільшення прогнозованого розміру закодованих даних та сумарно не перевищують 32 Кб (розміру словника LZ77), доки це збільшення не перевищує 250 бітів. Приклад меж мінімальних блоків рядків для тестового зображення наведено на рис. 1 зліва (восьмий мінімальний блок тестового зображення складається лише з останнього рядка, що містить однакові піксели). Як видно з цього прикладу, мінімальні блоки складаються з рядків, що мають близькі нерівномірності розподілів елементів.
рис. 1. Межі мінімальних та однорідних блоків тестового зображення
Ш Визначити для кожного мінімального блоку рядків i після стиснення кожним з п'яти варіантів компресії j (0 - без застосування предикторів, 1 - з використанням LeftPredict, 2 - з застосуванням RightPredict, 3 - з використанням ентропійного поелементного способу вибору предикторів, 4 - з застосуванням ентропійного способу вибору предикторів після виконання коротких замін LZ77) прогнозовані розміри кодів sizei, j в бітах (, де m - кількість створених мінімальних блоків рядків) з використанням алгоритму мінімізації розміру стиснутих блоків. Запам'ятати також для кожного мінімального блоку рядків і кожного варіанту компресії частоти елементів розподілів літералів/довжин та зміщень (а не лише окремих елементів, як це було для рядків). Для реалізації цього кроку до пікселів зображення почергово застосовується кожен з п'яти варіантів компресії, виконується "жадібний" розклад LZ77 отриманих результатів та визначаються мінімальні розміри стиснутих блоків у межах кожного з мінімальних блоків рядків.
Ш Визначити методом динамічного програмування для кожного мінімального блоку рядків i оптимальний варіант компресії compresi та обрати відповідні частоти елементів розподілів літералів/довжин і зміщень цього варіанту для подальшого аналізу (можливість застосування цього методу забезпечує максимальний розмір мінімальних блоків рядків (32 Кб), який гарантує залежність прогнозованого розміру чергового стиснутого блоку в основному лише від попереднього блоку). Для цього: визначити під час прямого ходу методу динамічного програмування мінімальний накопичений прогнозований розмір від початку зображення до кожного мінімального блоку рядків i включно за умови застосування до нього варіанта компресії :
;
(finek, j - штраф за відхилення варіанта компресії чергового мінімального блоку рядків j від варіанта компресії попереднього блоку k); обчислити мінімальний прогнозований розмір всього зображення minSize з умови мінімуму по всіх варіантах компресії накопичених розмірів до останнього блоку включно:
;
визначити оптимальний варіант компресії кожного блоку compresi під час зворотного ходу методу динамічного програмування так, щоб забезпечити отриманий мінімальний розмір:
,
Ш Віднести кожен мінімальний блок рядків до окремого однорідного блоку.
Ш Ітеративно поєднати суміжні однорідні блоки рядків з однаковими варіантами компресії в однорідні блоки рядків, забезпечуючи щоразу мінімальне збільшення прогнозованого розміру закодованих даних, доки це збільшення не перевищує 1000 бітів (межі однорідних блоків рядків для тестового зображення наведено на рис. 1 справа). Бачимо, що однорідні блоки рядків дають змогу поєднати мінімальні блоки рядків з близькими нерівномірностями розподілів та ліквідовують найменші такі блоки для зменшення загального КС зображення.
Ш Розрахувати за алгоритмом генерації кодів HUFF для кожного однорідного блоку рядків прогнозовані довжини кодів розподілів літералів/довжин та зміщень з використанням прогнозованих частот цих розподілів для подальшого ефективного кодування цих блоків алгоритмом LZ77 з "лінивим" чи майже оптимальним розкладом у різні стиснуті блоки формату PNG.
Уточнити розраховані для кожного однорідного блоку рядків прогнозовані довжини кодів HUFF розподілів літералів/довжин замін та зміщень (у випадку відсутності обмежень по часу) можна з розподілів, що утворюються за результатами додаткового проходу по даних зображення з застосуванням обраних предикторів, "лінивого" розкладу LZ77, кодування HUFF та алгоритму мінімізації розміру стиснутих блоків.
Застосування цього алгоритму попереднього аналізу та "лінивого" розкладу LZ77 сумісно з алгоритмом мінімізації розміру стиснутих блоків дає змогу зменшити КС у середньому на 3.9 %, хоча й сповільнює кодування у 4.5 рази. Використання ж майже оптимального розкладу замість "лінивого" у цій же програмі дозволяє зменшити КС у середньому на 4.3 %, сповільнюючи кодування у 7.5 рази.
Наприкінці розділу описано інтерфейс розробленої утиліти MinPNG для зменшення КС зображень у форматі PNG.
Четвертий розділ роботи розкриває можливості підвищення ефективності стиснення зображень у форматі PNG шляхом його модифікацій. У ньому наведено два розроблених способи зменшення міжелементної та один - кодової надлишковості.
4.1. Використання декількох ковзних вікон для результатів застосування різних предикторів у процесі формування модифікованого розкладу алгоритму LZ77. У цьому підрозділі описано розроблений алгоритм LZPR, що застосовується для зменшення міжелементної надлишковості за допомогою використання декількох ковзних вікон. Цей алгоритм дає змогу обрати найефективніший предиктор не лише для цілого рядка пікселів, а й для будь-якого його фрагменту. У випадку формування, наприклад, "жадібного" розкладу, під час кожної ітерації даний алгоритм виконує пошук найдовшої однакової послідовності у декількох ковзних вікнах. У випадку наявності такої послідовності чергові елементи буфера кодують трійкою чисел <довжина; зміщення від закінчення закодованої частини потоку; номер застосованого предиктора>, інакше в закодовані дані записується перший елемент буфера з ковзного вікна предиктора з найменшою ентропією (рис. 2). Після цього закодовані елементи у всіх ковзних вікнах переносяться з буфера в словник і кодування продовжується ітеративно до закінчення елементів потоку.
рис. 2. Застосування алгоритму LZPR до потоку "3, 4, 6, 0, 3, 4, 6, 2, 3, 5, 1"
Застосування алгоритму LZPR дає змогу зменшити середній КС зображень набору ACT у випадку використання трьох альтернативних словників та формування попіксельного (а не поелементного) розкладу LZ77 на понад 2.1 % у порівнянні з найкращим на сьогодні способом стиснення у стандарті формату PNG.
4.2. Застосування різницевих кольорових моделей для підвищення ефективності використання предикторів в процесі стиснення RGB-зображень без втрат. У цьому підрозділі обґрунтовано та описано способи формування та переходу до альтернативних різницевих кольорових моделей для кожного RGB-зображення у форматах, що використовують неадаптивні предиктори, з метою покращення КС контекстно-незалежних алгоритмів за рахунок міжкомпонентної декореляції. Найефективнішими серед досліджених виявилися різницеві кольорові моделі з цілими коефіцієнтами. У цьому випадку, формуючи різницеві кольорові моделі для кожного зображення, необхідно оцінити доцільність заміни значень компоненти Rij різницями Rij-Gij або Rij-Bij, значень Gij різницями Gij-Rij або Gij-Bij та значень Bij різницями Bij-Rij або Bij-Gij, враховуючи використання предикторів. Для цього досліджувані ентропійні довжини записано у вигляді матриці аналізу A (у межах кожного піксела компонента R має індекс 0, G - 1, B - 2):
,(5)
де вказує на застосування будь-якого лінійного статичного предиктора (в роботі використано LeftPredict) згідно (2), а L - на обчислення довжини ентропійного коду, наприклад, використовуючи (3). Тоді, для забезпечення однозначності декодування, різницева кольорова модель визначається щонайбільше двома недіагональними елементами різних рядків матриці A, які серед елементів, менших за діагональні елементи своїх рядків, сумарно найбільше від них відхиляються (забезпечують максимальні зменшення ентропійних довжин кодів). У випадку наявності таких елементів, індекс рядка кожного з них визначає зменшувану компоненту, а індекс стовпця - компоненту, що від неї віднімається. Наприклад, вибір елемента a12 вказує, що в альтернативній кольоровій моделі для кожного піксела зображення необхідно значення компоненти G зменшити на значення компоненти B. Формуються такі різницеві кольорові моделі за наступним алгоритмом.
Ш Розрахувати для кожної компоненти всіх пікселів зображення результати дії обраного лінійного предиктора.
Ш Обчислити ентропійні довжини кодів компонентів і різниць компонентів результатів дії обраного предиктора та зберегти їх в матриці A згідно (5).
Ш Занести значення 0 у змінні index11, index12, index21 та index22, що визначають можливі різниці альтернативної кольорової моделі.
Ш Визначити в матриці A два елементи, які не належать головній діагоналі, не симетричні відносно неї, менші за діагональні елементи своїх рядків, і сумарно найбільше від них відхиляються. Якщо такі елементи присутні, то занести в змінні index11 та index12 відповідно номер рядка та номер стовпця першого елемента, а в змінні index21 та index22 - номер рядка та номер стовпця другого елемента. Інакше визначити в матриці A недіагональний елемент, менший за діагональний елемент свого рядка. Якщо і такий елемент відсутній, то перейти до останнього кроку алгоритму. Інакше занести в змінну index11 номер рядка цього елемента, а в змінну index12 - номер його стовпця.
Ш Якщо значення змінних index11 та index22 однакові, то переставити значення змінних index11 з index21 та index12 з index22, тобто змінити черговість віднімання компонентів кольорової моделі.
Ш Зменшити для кожного піксела зображення значення компоненти з індексом index11 на значення компоненти з індексом index12.
Ш Якщо значення змінних index21 та index22 різні, тобто друга різниця кольорової моделі визначена, то зменшити для кожного піксела зображення значення компоненти з індексом index21 на значення компоненти з індексом index22.
Ш Завершити формування та перехід до різницевої кольорової моделі і виконати подальше стиснення перетвореного зображення з використанням предикторів.
Розраховані різницеві кольорові моделі за цим алгоритмом для зображень набору ACT наведено у табл. 1, їх застосування дає змогу зменшити КС зображень в середньому на 4.6 % в основному за рахунок фотореалістичних зображень.
Таблиця 1 Різницеві кольорові моделі для стиснення зображень набору ACT з застосуванням предикторів
|
№ файла |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
Різницева модель |
R,G-R,B |
RGB |
R,G-R,B-G |
R,G-B,B-R |
R,G-R,B-G |
R-G,G,B-G |
RGB |
R,G-R,B-G |
4.3. Використання палітри для групового статистичного кодування трикомпонентних зображень без втрат дає змогу ефективніше зберігати кольори пікселів кожного зображення. Для цього запропоновано перетворити значення кольорів пікселів (як правило, після застосування предикторів) за наступним алгоритмом.
Ш Згрупувати кольори пікселів по паралелепіпедах (тут і надалі - прямокутних), що не перетинаються.
Ш Зберегти в палітрі найменші значення компонентів пікселів, що належать кожному з утворених паралелепіпедів та їх розміри по кожній осі.
Ш Подати значення кольору кожного піксела у вигляді індекса в палітрі паралелепіпеда, якому він належить, та зміщеннях по кожній координаті у середині паралелепіпеда.
Таке перетворення дає змогу замість ентропійного кодування трьох компонентів пікселів використати групове кодування: ентропійне кодування лише індексів відповідних паралелепіпедів в палітрі та рівномірне кодування зміщень пікселів відхилень по кожній координаті в середині цих паралелепіпедів.
Формування паралелепіпедів реалізується для кожного зображення в два етапи: спочатку виконується швидке початкове розбиття простору кольорів RGB на 64 рівновеликих паралелепіпеди з відкиданням тих з них, які не містять пікселів аналізованого зображення, після чого отримані паралелепіпеди ітеративно розбиваються так, щоб максимально зменшити загальний КС. Під час розбиття паралелепіпедів враховується, що, з одного боку, кожне розбиття зменшує діапазон значень по осі поділу для утворюваних паралелепіпедів і тому підвищує ефективність рівномірних кодів, з іншого боку, розбиття довільного паралелепіпеда призводить до створення нового кольору в палітрі і поділу його пікселів між двома утвореними паралелепіпедами, тобто зменшує нерівномірність розподілу частот елементів, внаслідок чого збільшується ентропія джерела (1).
Використання палітри після контекстно-залежного алгоритму LZPR дозволяє додатково зменшити КС зображень у середньому на 1.4 % та прискорити декодування на понад 7 %, хоча й сповільнює кодування на 38 %.
Наприкінці підрозділу показано, що сукупне застосування досліджених модифікацій формату PNG та алгоритму компенсування відхилень предикторів з формату JPEG-LS дає змогу зменшити КС на понад 12 %, а також описано особливості застосування розробленого комплексу ModifyPNG, який реалізує таке стиснення.
У додатках роботи містяться авторські свідоцтва на комп'ютерні програми, розроблені за результатами дослідження, акти впровадження та довідка про використання у навчальному процесі результатів дослідження, результати застосування арифметичного кодування замість HUFF для модифікацій формату PNG, фрагменти програм мовою C, що реалізують запропоновані в роботі методи і алгоритми.
Висновки
В дисертації розв'язано актуальну наукову задачу підвищення ефективності стиснення зображень без втрат у растрових графічних форматах, зокрема, і у форматі PNG, що використовують предиктори, словниковий алгоритм LZ77, контекстно-незалежне кодування та їх комбінування за допомогою вдосконалення і врахування взаємодії цих та застосування альтернативних чи нових методів і алгоритмів кодування. При цьому отримано наведені нижче основні наукові і практичні (в середньому по набору зображень ACT) результати:
1. Вдосконалено метод пошуку однакових послідовностей елементів потоку шляхом вибору найкоротших хеш-ланцюгів, що дало змогу, наприклад, прискорити формування розкладу алгоритму LZ77 для випадку аналізу всіх елементів цих ланцюгів у понад 13 разів.
2. Вперше запропоновано і реалізовано післяпроцесний метод зменшення розміру стиснутого блоку у форматі DEFLATE за допомогою: розрахунку розподілів частот для визначення розмірів альтернативних стиснутих блоків без їх попередньої генерації; вибору найкоротшого блоку з альтернативних; ітеративного відкидання неефективних замін у найкоротшому стиснутому блоці з наступним його формуванням. Реалізація цього методу хоча й сповільнює кодування на 10 %, але дозволяє зменшити КС переважної більшості синтезованих з шумами та фотореалістичних зображень на 2 - 6 %. В процесі реалізації цього методу вдосконалено метод точного розрахунку розмірів блоків динамічних кодів HUFF за допомогою врахування принципу формування цих кодів без їх безпосередньої генерації, що дало змогу прискорити виконання таких обчислень на понад 85 %.
3. Вдосконалено механізм формування "лінивого" / майже оптимального розкладів алгоритму словникового стиснення LZ77 шляхом використання результатів попереднього аналізу зображень для прогнозування довжин кодів елементів, що дало змогу зменшити КС на 0.1 %, хоча й сповільнило кодування на 30 % / 8.3 %.
4. Проведено аналіз ефективності стиснення зображень у випадку застосування різноманітних предикторів, існуючих і розроблених ентропійних та емпіричних способів вибору предикторів для окремих рядків, різних способів кодування, за результатами якого виділено п'ять варіантів компресії, кожен з яких може виявитися оптимальним для чергового блоку рядків: без використання предикторів, з застосуванням LeftPredict, з використанням RightPredict, з застосуванням безпосереднього ентропійного способу вибору предикторів та з використанням ентропійного способу вибору предикторів після застосування коротких замін алгоритму LZ77.
5. Вперше розроблено метод попереднього аналізу зображень з розбиттям на мінімальні та однорідні блоки рядків з метою визначення для кожного з них оптимального варіанту компресії (з п'яти наведених у попередньому пункті) за допомогою методу динамічного програмування, реалізація якого у сукупності з методами та способами попередніх пунктів хоча й сповільнює кодування стосовно швидких варіантів стиснення у форматі PNG у понад 4.5 рази, але зменшує КС більш ніж на 3.9 % та досягає по цьому показнику найменших значень серед відомого програмного забезпечення, яке стискує зображення у форматі PNG.
6. Вдосконалено структуру розкладу алгоритму словникового стиснення LZ77 (алгоритм LZPR) шляхом використання декількох ковзних вікон та формування літералів з найменшою ентропією, що дало змогу зменшити КС на понад 2.1 %.
7. Вперше розроблено ряд методів для генерування різницевих кольорових моделей як з цілими, так і з дійсними коефіцієнтами, орієнтованих на зменшення довжини контекстно-незалежного коду у випадку використання предикторів. Застосування цих моделей дає змогу зменшити КС фотореалістичних зображень на понад 7 % у форматах без втрат, які використовують таке кодування і не виконують міжкомпонентну декореляцію.
8. Отримав подальший розвиток метод групового статистичного кодування за допомогою використання палітри в процесі стиснення трикомпонентних зображень без втрат, що дозволило зменшити КС на понад 1.4 %, хоча й сповільнило кодування на 38 %. Сумісна реалізація методу формування різницевих кольорових моделей з цілими коефіцієнтами, алгоритму коригування значень предиктора, алгоритму LZPR, алгоритму мінімізації розміру стиснутих блоків та даного методу дає змогу зменшити КС стосовно швидких варіантів стиснення у форматі PNG на понад 12 % та досягає по цьому показнику найменших на сьогодні значень відносно інших споріднених програм, що створює передумови для їх успішного спільного застосування у графічних форматах та архіваторах.
Список опублікованих праць за темою дисертації
1. Шпортько О. В. Аналіз зображень перед стисненням у форматі PNG / О. В. Шпортько // Комп'ютинг. - 2010. - Т. 9, вип. 2. - С. 192-204.
2. Шпортько О. В. Використання різницевих кольорових моделей для стиснення RGB-зображень без втрат / О. В. Шпортько // Відбір і обробка інформації. - 2009. - № 31 (107). - С. 90-97.
3. Шпортько О. В. Вибір найкоротшого з альтернативних стиснутих блоків динамічних кодів Хафмана у форматі PNG / О. В. Шпортько // Комп'ютинг. - 2009. - Т. 8, вип. 2. - С. 58-67.
4. Шпортько О. В. Використання палітри для групового статистичного кодування RGB-зображень без втрат / О. В. Шпортько // Відбір і обробка інформації. - 2009. - № 30 (106). - С. 125-132.
5. Шпортько О. В. Оптимізація використання статичних предикторів у процесі стиснення зображень без втрат / О. В. Шпортько // Відбір і обробка інформації. - 2008. - № 28 (104). - С. 82-89.
6. Шпортько О. В. Вибір найкоротших хеш-ланцюгів у процесі пошуку однакових послідовностей / О. В. Шпортько // Відбір і обробка інформації. - 2008. - № 29 (105). - С. 85-90.
7. Шпортько О. В. Алгоритм оптимізації результатів розкладу LZ77 за рахунок мінімізації зміщень / О. В. Шпортько // Вісник Національного університету водного господарства та природокористування. - 2009. - Вип. 2 (46), Ч. 1. - С. 378-385.
8. Бомба А. Я. Ентропійні способи вибору предиктора для рядка пікселів у форматі PNG / А. Я. Бомба, О. В. Шпортько // Управляющие системы и машины. - 2010. - № 3. - С. 8-25.
...Подобные документы
Програмний продукт "Графічний кодер чорно-білих зображень". Аналіз технологій одержання компактних подань відеоінформації способом організації кодування й пошук шляхів підвищення їх ефективності. Кодування зображень на основі зміни градації яскравості.
дипломная работа [1,8 M], добавлен 29.06.2009Основні теоретичні відомості алгоритмів стиснення зображень: класи зображень та їх представлення в пам'яті, алгоритми та принципи групового кодування. Огляд та аналіз сучасних програмних засобів конвертування. Тестування, опис роботи програмного засобу.
курсовая работа [2,9 M], добавлен 15.03.2014Основні поняття теорії інформації та їх роль у визначенні фундаментальних меж представлення інформації. Телевізійні стандарти стиснення. Кодер і декодер каналу. Стандарти стиснення двійкових та півтонових нерухомих зображень. Кодування бітових площин.
дипломная работа [8,1 M], добавлен 02.10.2014Створення алгоритму фрактального стиснення з втратами для зображень. Основні принципи методу, його обґрунтування та алгоритм реалізації. Характеристика типової схеми фрактального стиснення. Побудова алгоритму, його представлення та афінне перетворення.
курсовая работа [932,1 K], добавлен 10.07.2017Синтез, обґрунтування і дослідження моделей мультиграничної сегментації на основі зв’язків покриттів. Введення і дослідження операцій на класах еквівалентностей або толерантностей для перетворень результатів сегментації для отримання областей зображень.
автореферат [199,1 K], добавлен 11.04.2009Розробка резидентної програми за допомогою мови асемблер, яка дозволить перехопити зміст текстового та графічного екрану у файл (відповідно TXT і BMP). Вибір та обґрунтування методу розв'язки даної задачі. Алгоритм і реалізація програми, системні вимоги.
курсовая работа [14,9 K], добавлен 08.08.2009Імовірнисний підхід у теорії ощадливого кодування. Оцінка інформативності ознак та їх оптимальна градація. Застосування імовірнісних методів для підвищення ефективності ощадливого кодування відеоінформації. Ефективні алгоритми кодування інформації.
реферат [1,6 M], добавлен 29.06.2009Бібліотека документів, зображень, музична бібліотека та бібліотека відеозаписів. Алгоритм відкриття бібліотеки. Створення архівів файлів за допомогою спеціалізованих програм — архіваторів. Вибір методу стиснення. Видалення файлів після стиснення.
лабораторная работа [685,4 K], добавлен 13.02.2016Стиснення даних як процедура перекодування даних, яка проводиться з метою зменшення їх об'єму, розміру, обсягу. Знайомство с особливостями стиснення інформації способом кодування серій. Загальна характеристика формату ZIP, аналіз основних функцій.
презентация [1,8 M], добавлен 14.08.2013Модель обробки файлів растрових зображень. Середній квадрат яскравості. Фільтри для виділення перепадів і границь. Опис та обґрунтування вибору складу технічних та програмних засобів. Опис інтерфейсу програми. Зображення діалогового вікна програми.
курсовая работа [664,3 K], добавлен 30.06.2009Розробка, дослідження та реалізація методів вирішення завдань аналізу, розпізнавання і оцінювання зображень як один із провідних напрямків інформатики. Класифікація та аналіз існуючих методів розпізнавання образів, переваги та недоліки їх застосування.
статья [525,8 K], добавлен 19.09.2017Комп’ютерне моделювання системи сегментації та розпізнавання облич на зображеннях. Підвищення швидкодії моделювання за кольором шкіри та покращення якості розпізнавання при застосуванні робастних boosting-методів. Розробка алгоритмів функціонування.
дипломная работа [1,6 M], добавлен 02.07.2014Історія створення мови С#. Аналіз алгоритмів кодування даних. Розробка системи в середовищі Visual Studio 2008 Express. Схема шифрування алгоритму DES. Дослідження алгоритму RC2. Приклади хешів RIPEMD-160. Програмна реалізація основних процедур системи.
дипломная работа [1,7 M], добавлен 25.10.2012Сучасні методи захисту текстової інформації. Порівняльний аналіз шифру Бекона з іншими відомими шифрами. Практичне використання алгоритмів кодування тексту. Написання програми "Шифр Бекона", використані компоненти для реалізації алгоритму, їх властивості.
курсовая работа [606,8 K], добавлен 28.03.2016Растрові формати зображень tiff, bmp, pcx, gif, jpeg, png, опис растрової графічної інформації. Зручність та недоліки векторних форматів. Зберігання і обробка зображень, що складаються з ліній, або можуть бути розкладені на прості геометричні об'єкти.
контрольная работа [2,5 M], добавлен 19.09.2009Використання методів обробки сигналів, які базуються на використанні малохвильової теорії. Вимоги до алгоритмів компресії та критерії порівняння алгоритмів. Застосування вейвлет-перетворень. Критерії оцінювання оптимальності вибору малохвильових функцій.
реферат [1,1 M], добавлен 26.05.2019Області застосування методів цифрової обробки зображень. Динамічний діапазон фотоматеріалу. Графік характеристичної кривої фотоплівки. Загальне поняття про High Dynamic Range Imaging. Тональна компресія та відображення. Головні стегано-графічні методи.
контрольная работа [1,6 M], добавлен 10.04.2014Призначення та область застосування програм, які орієнтовані на перетворення зображень з плоского в об’ємне. Основні стадії формування тривимірного зображення. Класифікація моделей і методів візуалізації. Особливості створення карти глибин по пікселям.
курсовая работа [325,8 K], добавлен 04.06.2010Алгоритм кодування графічних даних та сутність методу довгих серій. Інформація про палітру у стандартному форматі RGB та 256-кольорову палітру PCX. Системні вимоги до розробки та реалізація бібліотеки ASM-86, сумісної з мовою програмування Pascal.
практическая работа [19,4 K], добавлен 15.06.2009Розробка резидентної програми на асемблері, яка дозволить перехопити зміст текстового та графічного екрану у файл. Виникнення проблеми нереентерабельності ДОС. Визначення поточного режиму екрану і спосіб запису. Графічне заповнення структури BMP файла.
курсовая работа [13,2 K], добавлен 12.08.2009
