Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Національний аерокосмічний університет ім. М.Є. Жуковського

"Харківський авіаційний інститут"

УДК 004.932

05.12.13 - радіотехнічні пристрої та засоби телекомунікацій

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

Метод стиску зображень на основі контекстного моделювання в системах телекомунікацій

Дядик Дмитро Федорович

Харків - 2008

Дисертацією є рукопис.

Робота виконана у Військовому інституті телекомунікацій та інформатизації Національного технічного університету України "КПІ", Міністерство оборони України.

Науковий керівник: кандидат технічних наук, доцент Стрюк Олексій Юрійович, Військовий інститут телекомунікацій та інформатизації Національного технічного університету України "КПІ", докторант науково-організаційного відділу.

Офіційні опоненти:

- доктор технічних наук, старший науковий співробітник Бараннік Володимир Вікторович, Харківський університет Повітряних Сил імені Івана Кожедуба, провідний науковий співробітник науково-дослідного відділу наукового центру;

- кандидат технічних наук, доцент Корольова Наталія Анатоліївна, Українська державна академія залізничного транспорту, доцент кафедри "Транспортний зв'язок".

Захист відбудеться "06" березня 2009 р. о 12.00 годині на засіданні спеціалізованої вченої ради Д64.062.07 у Національному аерокосмічному університеті ім. М.Є. Жуковського "Харківський авіаційний інститут" за адресою: 61070, м. Харків, вул. Чкалова, 17, радіотехнічний корпус, ауд. 232.

З дисертацією можна ознайомитись у бібліотеці Національного аерокосмічного університету ім. М.Є. Жуковського "Харківський авіаційний інститут".

Автореферат розісланий "19" січня 2009 р.

Вчений секретар спеціалізованої вченої ради В.В. Лукін.

Анотація

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.12.13 - радіотехнічні пристрої та засоби телекомунікацій. Національний аерокосмічний університет ім. М.Є. Жуковського "Харківський авіаційний інститут". Харків, 2008 р.

У дисертаційній роботі показано, що підвищення ефективності функціонування телекомунікаційних систем можливе шляхом зменшення об'ємів запам'ятовуючих пристроїв і зниження навантаження на канали зв'язку за рахунок компактного представлення зображень. Розроблено комбінований метод стиску зображень без втрат інформації, що базується на застосуванні вдосконаленого методу зміни кольорової моделі зображень, цілочислового вейвлет-перетворення, вдосконаленого контекстного моделювання РРМ та арифметичного кодування. Ступінь стиску для півтонових та повнокольорових зображень підвищено на 15-17%.

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

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

Ключові слова: зображення, метод стиску без втрат, кольорова модель зображення, контекстне моделювання.

Аннотация

Дядык Д.Ф. Метод сжатия изображений на основе контекстного моделирования в системах телекоммуникаций. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.13 - радиотехнические устройства и средства телекоммуникаций. Национальный аэрокосмический университет им. М.Е. Жуковского "Харьковский авиационный институт". Харьков, 2008 г.

Диссертация посвящена разработке методов преобразования и кодирования изображений без потерь информации, с целью повышения степени сжатия. Данные методы стали основой для разработки комбинированного метода сжатия полутоновых и полноцветных изображений, который позволяет уменьшить объёмы запоминающих устройств и снизить нагрузку на каналы передачи данных в системах телекоммуникаций.

Проведена классификация существующих изображений с точки зрения эффективности применения к данным классам различных методов сжатия. Проведён анализ существующих алгоритмов сжатия изображений и форматов их представления, а также составляющих этапов комбинированных методов сжатия.

Разработана обобщённая схема комбинированного метода сжатия изображений без потерь, которая включает этапы анализа цветовых и статистических свойств изображения, смены цветовой модели изображения, ортогонального преобразования, контекстного моделирования и безизбыточного кодирования. Усовершенствован целочисленный метод смены цветовой модели изображений RCT, позволяющий уменьшить значение энтропии яркостной составляющей Y. Проведён анализ методов ортогонального преобразования и выбрано вейвлет-преобразование вида CDF22 с фильтрами (5/3) для преобразования изображений, значение вероятности цветового перепада которых превышает 0,6.

Предложен метод разделения высокочастотных и низкочастотных массивов трансформант вейвлет-преобразования с целью построения более точных моделей сжимаемых данных, что даёт возможность повысить точность оценки сжимаемых символов и повысить степень сжатия.

Анализ методов моделирования сжимаемого потока данных позволил выделить методы контекстного моделирования как эффективные методы оценки вероятности символов потока. В частности, выбран алгоритм контекстного моделирования РРМ для использования в комбинированном методе сжатия изображений. Исследованы свойства данного алгоритма и выделены проблемы оценки максимального порядка контекста и частоты символа ухода. Для нахождения данных параметров алгоритма разработан метод оценки максимального порядка контекста алгоритма РРМ и метод определения значения частоты символа ухода, позволяющие повысить степень сжатия изображений всех классов при использовании алгоритма РРМ.

Проведён анализ алгоритмов безизбыточного кодирования. Для использования в комбинированном методе сжатия изображений выбран арифметический QM-кодер, имеющий ряд преимуществ по сравнению с другими кодерами и являющийся свободным от патентных ограничений.

С целью аналитической оценки степени сжатия изображений, для методов сжатия на основе контекстного моделирования и арифметического кодирования разработан метод предварительной оценки степени сжатия. Данный метод позволяет без необходимости практической реализации и использования алгоритмов контекстного моделирования и арифметического кодирования оценить степень сжатия аналитически. Погрешность оценки, получаемой с помощью разработанного метода, не превышает 1-2%.

На основании разработанной схемы комбинированного метода сжатия изображений без потерь разработаны метод, алгоритм, программную реализацию и вариант структурной схемы устройства сжатия изображений без потерь информации при восстановлении. Проведено сравнение разработанного метода с алгоритмами сжатия изображений без потерь информации популярных форматов: GIF, PNG, JPEG-LS, JPEG-2000. В качестве параметров оценки алгоритмов сжатия выбраны: степень сжатия, время сжатия и вычислительная сложность алгоритмов. Разработанный метод позволил повысить степень сжатия полутоновых и полноцветных изображений средней и высокой насыщенности на 15-17%. Время сжатия и вычислительная сложность разработанного алгоритма превышает существующие на 23-29%.

Использование инструментальных средств, реализующих разработанные методы сжатия и восстановления изображений в составе телекоммуникационных систем, позволит сократить объемы запоминающих устройств и нагрузку на каналы передачи данных.

Ключевые слова: изображение, метод сжатия без потерь, цветовая модель изображения, контекстное моделирование.

Abstract

Diadyk D.F. Method of image compression on the basis of context modeling in the systems of telecommunications - Manuscript.

The thesis to maintaining the scientific degree of Candidate of Technical Sciences by speciality 05.12.13 - radio devices and a means of telecommunications. National Aerospace University "Kharkiv Aviation Institute", Kharkiv, 2008.

In the thesis it has been demonstrated that the increase of efficiency functioning of the telecommunication systems is possible by diminishing volumes of memory devices and lowering loading on communication channels, due to compact presentation of images. The combined method of image compression has been developed without information losses, that is based on application the coloured image model method changing, the whole numbered wavelet-transformation, context modeling and arithmetic encoding. The degree of compression without the losses of the half-toned and full-coloured images has been increased on the 15-17%.

The method of the preliminary assessment of image compression degree for the methods of compression on the principles of the PPM context modeling and the arithmetic encoding has been developed.

The proposed methods have been realized as algorithms and program facilities for the compression of images without the losses of information.

Keywords: image, method of compression without the losses, coloured model of image, context modeling.

1. Загальна характеристика роботи

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

"Концепція розвитку зв'язку України до 2010 року", "Концепція розвитку телекомунікацій в Україні до 2010 року", "Концепція розвитку Єдиної Національної системи зв'язку України на 2000-2010 роки", а також Національні програми інформатизації України визначають наступні основні напрямки розвитку телекомунікаційних систем:

- розробка нових технологій і систем обробки та передачі інформації;

- підвищення ємності та пропускної спроможності телекомунікаційних мереж з застосуванням перспективних технологічних рішень;

- підвищення ефективності використання телекомунікацій з врахуванням обмеженості ресурсів, що можуть бути задіяні для їх розвитку;

- зменшення собівартості і підвищення якості отриманої користувачем інформації.

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

Передача зображень, стиснутих без втрат, вимагає високошвидкісних каналів, а їх зберігання - значних об'ємів пам'яті. Це пов'язано з невисокими ступенями стиску для існуючих методів стиску без втрат (3-4 для зображень середньої насиченості та 1,5-2 рази для зображень високої насиченості). Тому розробка комбінованого методу стиску зображень без втрат на основі сучасних методів перетворення та кодування даних, здатного підвищити ступінь стиску зображень в порівнянні з існуючими методами, є актуальною задачею.

Зв'язок з науковими програмами, планами, темами. Дослідження, результати яких викладені в дисертаційній роботі, проводилися в 2004-2008 рр. у Полтавському військовому інституті зв'язку та Військовому інституті телекомунікацій та інформатизації Національного технічного університету України "КПІ" у відповідності з наступними нормативними актами та планами НДР:

1. "Концепція розвитку зв'язку України до 2010 року" - постанова Кабінету Міністрів України №2238, затверджена 9 грудня 1999 року.

2. "Концепція розвитку телекомунікацій в Україні до 2010 року" - розпорядження Кабінету Міністрів України №316-р, затверджене 7 червня 2006 року.

3. "Національна програма інформатизації" - Закон України №74/98-ВР від 4 лютого 1998 року.

4. "Загальнодержавна цільова науково-технічна космічна програма України на 2008-2012 роки" - Закон України №608-VI від 30 вересня 2008 року.

5. Планом НДР МОУ: шифр "Еврика".

6. Планом НДР НАУ "ХАІ": ГР "0106U001071".

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

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

Для досягнення поставленої мети необхідно вирішити наступні задачі:

1. Провести класифікацію існуючих зображень по ефективності застосування до них різноманітних методів стиску.

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

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

4. Вибрати метод цілочислового перетворення компонент зображення в набір коефіцієнтів (трансформант зображення).

5. Розробити метод компактного представлення трансформант перетворення при використанні методів кодування на основі імовірнісної оцінки при моделюванні.

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

Об'єкт дослідження. Процеси аналізу, обробки, перетворення та кодування зображень в телекомунікаційних системах.

Предмет дослідження. Методи та інструментальні засоби стиску зображень в телекомунікаційних системах.

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

Наукова новизна отриманих результатів полягає в розробці і дослідженні методів перетворення, моделювання та кодування зображень з метою стиску без втрат, а також комбінованого методу стиску зображень, що базується на розробленому методі зміни кольорової моделі зображень, вейвлет-перетворенні, контекстному моделюванні та арифметичному кодуванні, при цьому:

- удосконалено метод зміни кольорового представлення зображень в частині адаптивного визначення головної кольорової компоненти Y на основі аналізу вихідних кольорових складових зображень, що дозволяє підвищити ефективність стиску даної компоненти по параметру ступінь стиску;

- вперше розроблено метод визначення максимального порядку контексту алгоритму РРМ, який, на відміну від відомих, визначає та використовує статистичні властивості зображень, що дозволяє аналітично визначити найбільш ефективний порядок контексту алгоритму РРМ за параметром "ступінь стиску" для певного виду зображень;

- удосконалено метод визначення ймовірності символу переходу алгоритму РРМ в частині знаходження частоти символу переходу на основі статистичних даних стискаємого виду зображень, що дозволяє аналітично визначити частоту символу переходу для даного методу та підвищити ступінь стиску;

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

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

Практична цінність отриманих результатів полягає в наступному:

1. Розроблено алгоритм та програмну реалізацію методу зміни кольорового представлення зображень, що дозволяє зменшити ентропію компоненти Y на 7-8% для кольорової моделі RCT.

2. Розроблено алгоритм та програмну реалізацію методу визначення максимального порядку контексту алгоритму РРМ, які дозволяють визначити максимальний порядок контексту для стискаємого типу зображень, що дає можливість підвищити ступінь стиску зображень.

3. Розроблено алгоритм та програмну реалізацію методу визначення частоти символу переходу алгоритму РРМ, які дозволяють на основі статистичних даних зображень визначити частоту символу переходу, що дає можливість підвищити ступінь стиску зображень на 5-7%.

4. Розроблено програмну реалізацію методу попередньої оцінки ступеня стиску зображень, що дозволяє без необхідності практичної реалізації алгоритму моделювання РРМ та арифметичного кодування визначити ступінь стиску зображень.

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

Особистий внесок автора. Внесок автора в публікації, виконані в співавторстві, полягає в наступному: у роботах [1, 3] - проведено аналіз доцільності застосування методів контекстного моделювання для стиску зображень та вибрано алгоритм контекстного моделювання РРМ для застосування в комбінованому методі стиску зображень; у роботі [2] - запропоновано метод перетворення кольорової моделі зображення на основі адаптивного визначення кольорової моделі зображення з найменшим ступенем насиченості; у роботі [7] - запропоновано модель кодування трансформант вейвлет-перетворення, на основі контекстного моделювання; у роботі [9] - проведений аналіз математичного апарату методу контекстного моделювання; у роботах [4, 8] - запропоновано метод вибору максимального порядку контексту для алгоритму контекстного моделювання РРМ; у роботах [10, 12] - запропоновано метод попередньої оцінки ступеня стиску даних для методів на основі контекстного моделювання РРМ та арифметичного кодування та представлено аналітичний вираз для даної оцінки; у роботах [6, 11] - запропоновано комбінований метод стиску зображень без втрат інформації, який забезпечує підвищення ступеня стиску зображень в порівнянні з існуючими алгоритмами.

Апробація результатів дисертації. Основні результати дисертації доповідалися і були схвалені на наступних науково-технічних конференціях та семінарах: 1-й, 2-й та 3-й Міжнародних науково-технічних конференціях "Гарантоздатні (надійні та безпечні) системи, сервіси та технології" (м. Полтава - 2006 р, м. Кіровоград - 2007, 2008 рр.), 9-й, 10-й Міжнародних студентських науково-технічних конференціях "Графіка XXI-сторіччя" (м. Севастополь, 2006, 2007 рр.), 5-й Міжнародній конференції "Інтернет, освіта, наука - 2006" (м. Вінниця, 2006 р.), Міжнародній науково-технічній конференції "Інтегровані комп'ютерні технології в машинобудуванні" (м. Харків, 2004, 2005, 2006 рр.), 15-й Міжнародній науково-технічній конференції "Інформаційні технології: наука, техніка, освіта, здоров'я" (м. Харків, 2007 р.), 1-й Всеукраїнській науково-технічній конференції "Комп'ютерна математика в науці, інженерії та освіті" (м. Полтава, 2007 р.), науково - технічних семінарах кафедри телекомунікаційних систем та мереж Полтавського військового інституту зв'язку (м. Полтава 2004 - 2007 рр.), 4-му науково-практичному семінарі "Пріоритетні напрямки розвитку телекомунікаційних систем та мереж спеціального призначення" (Київ, 2007 р.).

Публікації. Основні положення дисертаційної роботи викладені в 12 наукових працях, з яких 4 статті у журналах та 2 статті у збірниках наукових праць, що включені до переліку ВАК України, 6 робіт є тезами конференцій.

Структура й обсяг роботи. Дисертаційна робота складається із вступу, 4 розділів, висновків, додатків, викладена на 154 сторінках, у тому числі: список використаних літературних джерел з 156 найменувань на 15 окремих сторінках, 4 додатки на 9 окремих сторінках.

2. Основний зміст роботи

У вступі обґрунтована актуальність теми й наукових задач; сформульована мета дисертаційної роботи; показані об'єкт, предмет, наукова новизна і практична значимість отриманих результатів; відображені особистий внесок здобувача, дані щодо реалізації та апробації; публікації результатів досліджень.

У першому розділі проаналізовано роль методів стиску зображень без втрат в телекомунікаційних системах. Запропоновано класифікацію видів існуючих растрових зображень по ефективності застосування до них різних методів стиску. Проведений аналіз існуючих методів стиску зображень та форматів їх представлення. На основі аналізу побудована узагальнена схема комбінованого методу стиску зображень без втрат інформації.

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

Тому проведено класифікацію зображень та сформовано 7 класів зображень з метою більш повного подальшого аналізу методів стиску зображень та їх властивостей:

1. Двокольорові зображення (приклад: сканований текст).

2. Індексовані зображення (приклад: Web графіка).

3. Півтонові зображення (приклад: рентгенівські знімки).

4. Штучні зображення без плавних перепадів кольорів (приклад: топографічні карти).

5. Штучні зображення з плавними перепадами кольорів (приклад: презентації).

6. Фотореалістичні зображення з невисокою ступінню насиченості (приклад: фотографії повітряних об'єктів, на фоні однорідного неба).

7. Фотореалістичні зображення з високою ступінню насиченості (приклад: фотографії ландшафту місцевості ).

Основу поділу зображень на класи склали кольорові, структурні та статистичні властивості зображень. Представлено параметри для оцінки методів стиску зображень, серед яких виділено основні: ступінь стиску зображень, час стиску, обчислювальна складність.

На основі аналізу існуючих комбінованих методів стиску запропоновано узагальнену схему побудови методів стиску зображень, що складається з 5 етапів, при цьому деякі етапи в конкретних методах стиску можуть не використовуватися. Проведений аналіз складових етапів даної схеми.

Для порівняльного аналізу існуючих методів стиску вибрано алгоритми стиску зображень без втрат інформації популярних форматів представлення зображень: BMP, GIF, TIFF, JPEG-LS, JPEG-2000. Порівняння проведено за параметром ступеня стиску. Дане порівняння підтвердило доцільність та правильність запропонованої класифікації зображень та визначило класи зображень, на які орієнтовані вибрані алгоритми стиску.

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

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

Запропоновано удосконалений метод зміни кольорової моделі зображення, який дозволяє зменшити ентропію кольорової складової яскравості методу RCT на 7-8%. Даний метод базується на знаходженні кольорової компоненти вихідного зображення з найменшою ступінню насиченості. Вирази для прямого та зворотного перетворення мають вигляд:

- пряме перетворення

- обернене перетворення

,

де - кольорові складові зображення (червона, зелена, синя);

- одержані кольорові складові зображення;

- частота перепаду яскравості - параметр, що характеризує насиченість кольорової складової і визначається відповідно виразу:

,

де - відлік вихідного зображення.

Порівняння розробленого методу з методом RCT проведено за параметром ентропія кольорової складової Y на тестовому пакеті, що складається з 200 кольорових зображень класів 4, 5, 6, 7 з параметрами:

- формат зображень BMP;

- глибина кольору 24 біт/піксель;

- ймовірність кольорового перепаду Рпер = 0,4-0,99;

- розмір зображень: ширина від 300 до 1200 пікселів, висота від 250 до 980 пікселів.

Результати порівняння представлені в табл. 1.

кодування зображення запам'ятовуючий зв'язок

Таблиця 1

Значення ентропії компоненти Y для методу RCT та розробленого методу

Клас зображень	4	5	6	7	Середнє значення
Y компонента RCT методу	7,24	7,35	6,91	7,68	7,29
Y компонента розробленого методу	6,73	7,14	6,01	7,04	6,73

Середнє значення ентропії головної кольорової компоненти Y для розробленого методу менше, ніж методу RCT, на 7-8%, що дасть можливість підвищити ефективність стиску даної компоненти. Розроблений метод також має меншу обчислювальну складність, адже виключені операції ділення, множення та дві операції складання для кожного пікселя зображення при прямому та оберненому перетворенні.

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

Серед видів ЦВП, що застосовуються в алгоритмах стиску зображень виділено 3 види фільтрів ЦВП (з фільтрами (2/2), (2/6), (5/3)) та проведено дослідження їх властивостей за параметром ентропії зображень на тестовому пакеті з 300 зображень, розподілених на 7 класів, відповідно до запропонованої класифікації. Результати порівняння представлені на рис. 1.

Рис. 1. Значення ентропії для різних видів ЦВП

За отриманими результатами зроблено наступні висновки:

- застосування ЦВП доцільно для зображень класів 3, 5, 6, 7 (середнього та високого ступеня насиченості);

- для декореляції елементів зображення вибрано ЦВП виду CDF22 з фільтрами (5/3).

Таким чином, в розділі розроблено та вибрано методи декореляції елементів зображень з метою зменшення їх надмірності та підвищення ступеня стиску зображень.

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

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

В якості алгоритму кодування вибрано арифметичне кодування, прототип QM-кодера, що має ряд переваг: адаптивна модель оновлення, висока швидкість, цілочислове обчислення.

Головними параметрами алгоритму контекстного моделювання є: максимальний порядок контексту та ймовірність символу переходу. Від вибору значень даних параметрів залежить ефективність стиску даних.

Для визначення порядку контексту розроблено метод апріорної оцінки максимального порядку контексту для стискаємого типу даних. Основу методу складає визначення мінімальної ентропії контекстного дерева для моделей з різними максимальними порядками контексту:

порядок D, тобто ,

де - значення максимального порядку контексту.

Ентропія контекстного дерева визначається шляхом оцінки ентропії кожної контекстної моделі з врахуванням запропонованого параметру - коефіцієнту використання контексту за виразами:

де - значення порядку контексту;

;

- символ переходу;

- частота появи символу переходу в контексті ;

- загальна кількість оцінених символів.

Оцінку ефективності розробленого методу проведено шляхом отримання практичного результату - значень ентропії контекстних дерев для порядків контексту від 0 до 3 на тестовому пакеті з 7 класів зображень. Результати представлені на рис. 2.

Рис. 2. Значення ентропії контекстних дерев для різних порядків максимального контексту

Для підтвердження результатів проведено порівняння ступеня стиску даних зображень при застосуванні контекстних моделей з порядками максимального контексту від 0 до 3 на тестовому пакеті зображень. Результати представлені на рис. 3.

Рис. 3. Значення ступеня стиску для різних порядків максимального контексту

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

За допомогою розробленого методу визначені максимальні порядки контекстів для запропонованої схеми побудови комбінованого методу стиску відповідно для кожного класу зображень: 1-й клас - 12, 2-й клас - 3, 4-й клас - 2, 3, 5, 6 і 7-й класи - 1.

Іншим важливим параметром алгоритму РРМ є ймовірність символу переходу, що визначається за допомогою існуючих статичних або адаптивних методів оцінки. Класичним методом оцінки ймовірності символу переходу є метод РРМА:

,

де - частота використання контексту .

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

1. Побудова -мірної матриці перехідних ймовірностей, визначення частоти символу переходу для всіх значень.

2. Визначення загальної частоти переходів:

.

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

,

де - загальна кількість оброблених символів.

4. Визначення кількості операцій масштабування:

,

де - операція виділення цілої частини числа;

- максимальне значення лічильника символів, дорівнює 16383.

5. Визначення максимального значення частоти символу переходу:

.

6. Визначення середнього значення частоти символу переходу:

.

Результати порівняння розробленого методу з методом PPMA представлені на рис. 4.

Рис. 4. Порівняння ступеня стиску для класичного і розробленого методів

В результаті застосування розробленого методу оцінки частоти символу переходу підвищено ступінь стиску зображень тестового пакету на 5-7 %.

За допомогою розробленого методу проведена оцінка частоти символів переходу для запропонованої схеми комбінованого методу стиску зображень без втрат. Результати представлені в табл. 2.

Таблиця 2

Значення частоти символу переходу для кожного класу зображень

Клас зображень	1	2	3	4	5	6	7
	260	211	28	164	67	43	25

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

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

На основі розробленої схеми комбінованого методу стиску зображень без втрат, а також вибраних та розроблених методів перетворення та кодування зображень розроблено комбінований метод стиску зображень без втрат.

Розроблений комбінований метод стиску складається з наступних етапів:

1. Аналіз глибини кольору зображення (визначення кольоровості та повнокольоровості зображення).

2. Використання розробленого методу зміни кольорової моделі зображення для повнокольорових зображень (глибина кольору 24 біт/піксель).

3. Визначення насиченості зображення .

4. Застосування ЦВП для зображень з насиченістю .

5. Застосування методу контекстного моделювання РРМ з параметрами, вибраними відповідно для кожного типу зображень (визначається на основі даних етапів 1 та 3).

6. Застосування арифметичного кодування оцінених ймовірностей символів потоку.

На основі даного методу розроблено алгоритм, програмну реалізацію методу та варіант структурної схеми апаратного пристрою стиску зображень без втрат інформації.

Алгоритм розробленого комбінованого методу стиску порівняно з алгоритмами стиску без втрат популярних форматів представлення зображень: GIF, PNG, JPEG-LS, JPEG-2000. Порівняння проводилося на сформованому тестовому пакеті зображень, що складається з 300 зображень, розподілених на 7 класів, відповідно до запропонованої класифікації.

Аналіз результатів показав, що стиск двокольорових та індексованих зображень (класи 1 та 2) найбільш ефективно за допомогою алгоритму стиску формату GIF. Застосування розробленого методу для стиску півтонових та повнокольорових зображень (класи 3-7) дозволяє підвищити ступінь стиску даних зображень на 15-17%, по відношенню до алгоритмів стиску популярних форматів. Проведено порівняння часу стиску для тестового пакету зображень. Результати порівняння представлені на рис. 5.



Рис. 5. Порівняння часу стиску для алгоритмів стиску зображень без втрат

Результати показали більші затрати часу на стиск для розробленого комбінованого методу стиску в порівнянні з існуючими алгоритмами на 27-29%. Це пояснюється обчислювальною складністю алгоритму контекстного моделювання, внесок якого складає близько 50%, від загального часу.

Проведено аналіз обчислювальної складності розробленого методу та порівняно з алгоритмом стиску зображень без втрат, що реалізований в форматі представлення зображень JPEG-2000. Проаналізовано основні етапи алгоритмів та визначено арифметичні операції для їх реалізації. Результати представлені в табл. 3.

Таблиця 3

Порівняння обчислювальної складності розробленого методу стиску з алгоритмом стиску формату JPEG-2000

Операції	JPEG-2000	Розроблений метод
	Зміна кольорової моделі	ЦВП	Кодування	Зміна кольорової моделі	ЦВП	Кодування
Додавання	2	4	12	5	4	9
Віднімання	2	0	0	3	0	6
Множення	1	0	6	0	0	6
Ділення	0	1	12	0	1	9
Побітовий зсув	1	1	6	0	1	0

Всі арифметичні операції переведені в час виконання (число тактів) для архітектури процесорів Intel х86. Обчислювальна складність алгоритму формату JPEG-2000 складає 210 тактів на кожний піксель зображення, розробленого методу - 278 тактів, що на 24% більше.

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

де - ймовірність появи символу в контексті .

Для практичного підтвердження і знаходження похибки визначення ступеня стиску проведена аналітична та практична оцінка ступеня стиску (табл. 4).

Таблиця 4

Порівняння теоретичного і практичного значення ступеня стиску зображень

Клас зображень	Аналітичне значення ступеня стиску	Практичне значення ступеня стиску
1	23,56	23,91
2	9,21	9,32
3	3,28	3,34
4	9,42	9,48
5	2,98	3,03
6	3,39	3,46
7	2,28	2,32
Середнє значення	7,73	7,84

Аналіз отриманих результатів показав, що похибка при визначенні теоретичного (попереднього) значення ступеня стиску по відношенню до практичних результатів не перевищує 1-2%. Дані значення дозволяють зробити висновок про адекватність вибраної моделі алгоритму та точність результатів для розробленого методу попередньої оцінки ступеня стиску зображень.

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

Висновки

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

Головним результатом проведених досліджень є розроблені автором методи перетворення та кодування півтонових та повнокольорових цифрових зображень. Розроблено комбінований метод стиску зображень без втрат, який дозволяє підвищити ступінь стиску зображень на 15-17%. Використання розроблених методів у телекомунікаційних системах дозволить зменшити об'єми запам'ятовуючих пристроїв і знизити навантаження на канали зв'язку за рахунок більш компактного представлення зображень.

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

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

4. Вдосконалено метод визначення ймовірності символу переходу алгоритму РРМ в частині знаходження частоти символу переходу, на основі статистичних даних стискає мого виду зображень, що дозволяє аналітично визначити частоту символу переходу для даного методу та підвищити ступінь стиску.

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

6. Практичне значення отриманих результатів полягає в тому, що основні положення дисертації реалізовані у вигляді методів, алгоритмів, програмних засобів та структурної схеми пристрою.

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

8. Подальші дослідження можуть бути направлені на вдосконалення запропонованого науково-методичного апарату розробки методів стиску зображень: детальний аналіз статистичних властивостей зображень і вдосконалення кольорової моделі представлення зображень, з метою зменшення збитковості компоненти яскравості та компонент різниці кольорів; дослідження можливостей застосування в комбінованих методах стиску зображень різновидностей вейвлет-перетворення, з більш складними видами базисних функцій; розробка нових або вдосконалення існуючих методів моделювання даних, в тому числі методів контекстного моделювання, з метою більш точної оцінки ймовірності символів стискаємих даних.

Список опублікованих праць за темою дисертації

1. Дядик Д.Ф. Підвищення ступеня стиску зображень за рахунок оптимальної стратегії моделювання / Д.Ф. Дядик, О.Ю. Стрюк // Системи обробки інформації, 2004, №12(40), с. 60-63.

2. Дядик Д.Ф. Адаптивний метод перетворення кольорових координат відео даних / Д.Ф. Дядик, С.В. Гаркуша, О.Ю. Стрюк // Радіоелектронні і комп'ютерні системи, 2006, №6(18), с. 177-181.

3. Дядык Д.Ф. Выбор алгоритма контекстного моделирования при разработке метода сжатия изображений / Д.Ф. Дядык, А.Ю. Стрюк // Системи обробки інформації, 2006, №9(58), с. 20-25.

4. Дядык Д.Ф. Выбор порядка контекста при разработке метода сжатия изображений / Д.Ф. Дядык, А.Ю. Стрюк // Інформаційні технології та комп'ютерна інженерія, 2007, №1(8), с. 197-204.

5. Дядык Д.Ф. Метод оценки вероятности ухода алгоритма РРМ при сжатии изображений / Д.Ф. Дядык // Радиоэлектронные и компьютерные системы., 2007, №8(27), с. 35-40.

6. Дядык Д.Ф. Комбинированный метод сжатия изображений без потерь информации / Д.Ф. Дядык, А.Ю. Стрюк // Радиоэлектронные и компьютерные системы, 2008, №7(34), с. 171-175.

7. Стрюк О.Ю. Оптимальна модель кодування трансформант вейвлет-перетворення в алгоритмі стиску зображень / О.Ю. Стрюк, Д.Ф. Дядик // Міжнародна науково-технічна конференція "Інтегровані комп'ютерні технології в машинобудуванні", НАУ "ХАІ", 2005 р. - С. 298.

8. Стрюк А.Ю. Методика оценки эффективности при выборе порядка контекста / А.Ю. Стрюк, Д.Ф. Дядык // Мат. IX Междунар. студ. научно-технической конференции "Графика XXI-века", СевНТУ, 2006 г. - с. 119-122.

9. Дядык Д.Ф. Алгоритм контекстного моделирования для методов сжатия изображений / Д.Ф. Дядык, А.Ю. Стрюк // Міжнародна науково-технічна конференція "Інтегровані комп'ютерні технології в машинобудуванні", НАУ "ХАІ", 2006 р. - С. 279.

10. Дядык Д.Ф. Аналитическое выражение для оценки степени сжатия изображений / Д.Ф. Дядык, А.Ю. Стрюк // Мат. Всеукр. Научно-технической конференции "Комп'терна математика в інженерії, науці та освіті" (CMSEE-2007), ПолтНТУ, 2007 г. - С. 16.

11. Невсевро А.С. Усовершенствование метода сжатия изображений / А.С. Невсевро, В.Н. Жадан, Д.Ф. Дядык // Мат. X Междунар. студ. научно-технической конференции "Графика XXI-века", СевНТУ, 2007 г. - с. 139-141.

12. Стрюк О.Ю. Математичне моделювання алгоритму стиску зображень без втрат інформації / О.Ю. Стрюк, Д.Ф. Дядик // Мат. IV-го науково-практичного семінару "Пріоритетні напрямки розвитку телекомунікаційних систем та мереж спеціального призначення", ВІТІ НТУУ "КПІ", 2007 р. - С. 153.

Размещено на Allbest.ru

...