Моделювання динаміки фінансування проектів та програм створення но
вої техніки на основі детермінованого та імовірнісного подання
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний аерокосмічний університет ім. М.Є. Жуковського
“Харківський авіаційний інститут”
РІЗУНЕНКО Андрій Олексійович
УДК 004.932
МЕТОДИ ТА ІНФОРМАЦІЙНА ТЕХНОЛОГІЯ СТИСКУ ЗОБРАЖЕНЬ
В АВТОМАТИЗОВАНИХ СИСТЕМАХ НА ОСНОВІ ВЕЙВЛЕТ-ПЕРЕТВОРЕНЬ
05.13.06 – автоматизовані системи управління та
прогресивні інформаційні технології
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Харків – 2005
Дисертацією є рукопис
Робота виконана в Полтавському військовому інституті зв’язку, Міністерство оборони України.
Науковий керівник: | кандидат технічних наук
Стрюк Олексій Юрійович,
Полтавський військовий інститут зв’язку,
доцент кафедри телекомунікаційних систем та мереж.
Офіційні опоненти: | доктор технічних наук, професор
Федорович Олег Євгенович,
Національний аерокосмічний університет
ім. М.Є. Жуковського “Харківський авіаційний інститут”,
завідувач кафедри інформаційних управляючих систем;
кандидат технічних наук
Бохан Костянтин Олександрович,
Харківський університет Повітряних Сил,
науковий співробітник науково-дослідного відділу
інформаційно-обчислювального центру.
Провідна установа: | Національний технічний університет “Харківський політехнічний інститут”, кафедра системного аналізу і управління, Міністерство освіти і науки України, м. Харків.
Захист відбудеться “ 13 ” травня 2005 р. о 1200 годині на засіданні спеціалізованої вченої ради Д64.062.01 у Національному аерокосмічному університеті ім. М.Є. Жуковського "Харківський авіаційний інститут" за адресою: 61070, м. Харків, вул. Чкалова, 17, радіотехнічний корпус, ауд. 232.
З дисертацією можна ознайомитись у бібліотеці Національного аерокосмічного університету ім. М.Є. Жуковського "Харківський авіаційний інститут".
Автореферат розісланий “ 05 ” квітня 2005 р.
Вчений секретар
спеціалізованої вченої ради _____________________ М.О. Латкін
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми дослідження. Збільшення об’ємів передаваємої інформації, зокрема відеоінформації, впливає на якість функціонування автоматизованих систем переробки інформації і управління (АСПІУ). Якість та ефективність функціонування АСПІУ знижується внаслідок підвищення навантаження на канали зв’язку. В автоматизованих системах, які функціонують в режимі реального часу, для якісної передачі цифрових зображень необхідно підвищувати швидкість передачі інформації (збільшувати пропускну здатність каналів зв’язку), що потребує значних фінансових витрат. Одним із варіантів вирішення цієї проблеми є впровадження методів стиску зображень в системи передачі інформації. За останні десять років спостерігається зростання кількості програмних продуктів (ПП), що використовують методи стиску зображень без втрат інформації. Дані методи відіграють важливу роль в АСПІУ, до складу яких входять підсистеми збереження та обробки зображень (наприклад, в криміналістиці та юриспруденції; у медицині і мікробіології; у друкарській справі; при обробці радіолокаційних і інфрачервоних знімків у задачах картографування місцевості, зондування поверхні Землі; у космічній і військовій справі та ін).
У зазначених ПП неприпустиме застосування методів стиску з втратами через важливість даних, що оброблюються. Аналіз методів стиску зображень без втрат показав:
1. Ступінь стиску фотореалістичних сильнонасичених зображень не перевищує 1,5–2 рази.
2. Перспективним напрямком удосконалення методів стиску зображень є створення комбінованих методів, що використовують перетворення колірної моделі, ортогональне перетворення вихідних даних і методи беззбиткового кодування значень трансформант перетворення.
3. Ефективність побудови префіксних кодів (різні реалізації словникових методів, кодування Хаффмана) пов'язана з проблемою обмеженості обчислювальних ресурсів і істотною затримкою при формуванні коду. Уникнути зазначених проблем дозволяє метод послідовного формування коду в процесі одержання імовірнісних оцінок для символів, що входять у повідомлення – метод арифметичного кодування.
Таким чином, задача розробки методу стиску зображень без втрат з використанням цілочисельного ортогонального перетворення та комбінованого беззбиткового кодування коефіцієнтів, що спрямована на забезпечення збільшення ступеня стиску в порівнянні з існуючими методами, є актуальною.
Зв'язок з науковими програмами, планами, темами. Дослідження в дисертаційній роботі проводилися у відповідності з наступними нормативними актами:
1. Концепція розвитку Єдиної національної системи звязку України до 2010 р. Четверта редакція.
2. Законом України „Про Загальнодержавну (Національну) космічну програму України на 2003-2007 роки” (№ 203-IV від 24.10.2002 р.).
3. Планами НДР ПВІЗ: шифр „Тест”, „Інтеграція”.
4. Планами НДР ІРЕ НАНУ: шифр „Радикал”.
Мета і задачі досліджень. Метою дисертаційної роботи є підвищення ефективності автоматизованих систем переробки, збереження та передачі зображень шляхом зменшення об’ємів запам’ятовуючих пристроїв і зменшення навантаження на канали зв’язку за рахунок методів компактного представлення зображень без втрат якості відновлених даних. Для досягнення поставленої мети необхідно вирішити наступні задачі:
1. Проаналізувати існуючі методи стиску зображень. Дослідити існуючі методи стиску кольорових фотореалістичних зображень без втрат якості відновлених даних.
2. Розробити метод цілочисельного перетворення колірної моделі зображення.
3. Розробити метод цілочисельного перетворення просторово залежних елементів компонент зображення в набір незалежних коефіцієнтів (трансформант зображення).
4. Дослідити статистичні властивості трансформант для виявлення ділянок зображення з різною збитковістю.
5. Розробити метод компактного представлення трансформант перетворення при використанні методів беззбиткового кодування.
6. Розробити метод відновлення зображення за трансформантами перетворення.
7. За методами компактного представлення зображення розробити ядро інформаційної технології підтримки процесів стиску та відновлення зображень.
Об'єкт дослідження. Процес перетворення, збереження та передачі зображень в автоматизованих системах переробки інформації і управління.
Предмет дослідження. методи та інструментальні засоби стиску зображень в автоматизованих системах переробки інформації і управління.
Методи дослідження. дослідження властивостей цілочисельного вейвлет-перетворення (ЦВП) проводилися на базі теорії ортогональних перетворень. розробка методу кодування значень трансформант базувалася на теорії кодування інформації. вибір колірної моделі ґрунтувався на теорії обробки і передачі зображень. розробка аналітичних виразів для визначення значень теоретичного ступеня стиску, що забезпечується запропонованим методом, виконувалася відповідно до положень теорії зв'язку і кодування. оцінка експериментальних даних, отриманих у ході роботи, проводилася відповідно до положень математичної статистики.
Наукова новизна отриманих результатів полягає в розробці і дослідженні методів стиску зображень без втрат, що базуються на ЦВП і кодуванні значень трансформант перетворення цілочисельним арифметичним кодуванням (АК), при цьому:
1) отримано вперше:–
метод групування високочастотних трансформант вейвлет-перетворення, який базується на незалежній обробці знакових блоків вейвлет-коефіцієнтів та колірних компонент зображення, а також блоків старших та молодших бітових площин вейвлет-коефіцієнтів, що дозволяє більш ефективно враховувати статистичні властивості різних масивів зображення при їх кодуванні;–
аналітичні вирази для оцінки ступеня стиску зображень, які відрізняються від існуючих врахуванням різної збитковості блоків, що незалежно оброблюються;
2) удосконалено метод цілочисельного перетворення колірної моделі зображення на основі запропонованої процедури, що зменшує величину елементів складової яскравості зображення та додатково знижує ентропію даної складової на 3-5%;
3) отримали подальший розвиток:–
метод швидкого обчислення вейвлет-перетворення Хаара на основі запропонованого формування вейвлет-коефіцієнтів після одного проходу за матрицею значень компонент зображення, що дозволяє зменшити час знаходження коефіцієнтів в 1,5 рази;–
метод цілочисельного АК джерел з різною потужністю алфавіту, на основі виконаної модифікації алгоритму закінчення кодування, що дозволяє кодувати коефіцієнти з різною розрядністю.
Новизна отриманих результатів, підтверджується відсутністю аналогічних результатів у теорії і практиці систем кодування, обробки і передачі зображень.
Практична цінність отриманих результатів. Практична значимість отриманих результатів полягає в наступному:
1. Розроблено програмне забезпечення, яке реалізує методи стиску зображень без втрат, заснованого на ЦВП й АК. ступінь стиску, що забезпечується розробленою інформаційною технологією, перевищує ступінь стиску формату PNG на 15–20%, формату JPEG-LS на 3–5%, значення часу стиску тотожне часу стиску зображень форматами PNG і JPEG-LS.
2. Розроблено програмне забезпечення методу відновлення зображень, що забезпечує повну ідентичність відновлених після стиску зображень вихідним.
Робота над дисертацією проводилася автором у відповідності з державними планами НДР і програмами, що виконуються в інституті та інших організаціях:– “
Розробка науково-методичних засад підвищення відмовостійкості, живучості, оперативності та безпеки телекомунікаційних мереж різного призначення”, шифр “Тест” (ПВІЗ, м. Полтава, інв. № 289-Н, 2003);– “
Розробка концептуальних засад створення навчальної цифрової телекомунікаційної мережі та складових компонент автоматизованої системи інформаційного забезпечення навчального процесу і наукових досліджень інституту”, шифр “Інтеграція” (ПВІЗ, м. Полтава, інв. № 4563, 2004);– “
Дистанционное зондирование окружающей среды и биологических объектов радиофизическими методами”, шифр “Радикал” (ИРЭ НАНУ, г. Харьков, №U01004006443, 2004).
Особистий внесок автора. Внесок автора в публікації, виконані в співавторстві, полягає в наступному: у статті [1] – запропоновано алгоритм адаптивного кодування різних даних (статичних зображень, звуку, відеоданих) у комп'ютерних мережах; в наукових працях [2, 8] – досліджено властивості тестового пакета вихідних зображень і цих же зображень після ЦВП, показана зміна статистичних властивостей бітових площин зображення, що створює передумови для більш ефективного їх стиску; у статті [3] – запропоновано метод цілочисельного перетворення колірної моделі зображення; у статті [4] – розроблено метод цілочисельного АК трансформант вейвлет-перетворення з адаптивною моделлю відновлення відліків для джерел з різним алфавітом, а також запропоновано метод блокового кодування трансформант зображення для підвищення завадостійкості методу; у статті [6] – розглянуто доведення умови декодування відліків вейвлет-трансформант зображення, запропоновано алгоритм завершення АК; у тезах [9] – показано оцінку впливу зміни колірної моделі на ступінь стиску зображень; у тезах [11] – запропоновано метод швидкого обчислення двовимірного вейвлет-перетворення Хаара.
Апробація результатів дисертації. Основні результати дисертації доповідалися і були схвалені на наступних науково–технічних конференціях та семінарах: 7-му та 8-му Міжнародних молодіжних форумах “Радіоелектроніка і молодь у ХХІ столітті” (м. Харків, 2003 – 2004 р.), 3-й та 4-й Міжнародних науково-технічних конференціях “Проблеми інформатики і моделювання” (м. Харків, 2003 – 2004 р.), Міжвузівській науково-технічній конференції „Факультету „Телекомунікації” 5 років!” (м. Полтава, 2004 р.), міжгалузевому науково-технічному семінарі “Критичні комп'ютерні технології і системи” (м. Харків, 2004 р.), науково-технічному семінарі „Синтез, обробка та відображення інформаційних моделей” (м. Харків, 2004 р.), науково–технічних семінарах кафедри телекомунікаційних систем та мереж Полтавського військового інституту зв’язку (м. Полтава 2001–2004 р.).
Публікації. Основні положення дисертаційної роботи викладені в 11 наукових працях, з яких 4 статті у журналах, 2 статті у збірниках наукових праць, 5 робіт є тезами конференцій.
Структура й обсяг роботи. Дисертаційна робота складається із вступу, 4 розділів, висновків, додатків, викладена на 190 сторінках, у тому числі: 8 рисунків на 8 окремих сторінках, список використаних літературних джерел з 132 найменувань на 11 окремих сторінках, 4 додатки на 29 окремих сторінках.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтована актуальність теми й наукових задач; сформульована мета дисертаційної роботи; показані об’єкт, предмет, наукова новизна і практична значимість отриманих результатів; відображені особистий внесок здобувача, дані щодо реалізації та апробації; публікації результатів досліджень.
У першому розділі відображено роль методів стиску зображень без втрат в АСУ і телекомунікаційних мережах зв'язку, приведено їх класифікацію. показано можливість ефективного стиску зображень з використанням ЦВП. визначаються напрямки досліджень, пов'язані з розробкою методу стиску зображень без втрат.
Аналіз методів стиску зображень показав, що за останнє десятиліття зростає роль методів стиску без втрат. Сучасні інформаційні технології, що використовують ці методи, застосовуються: у криміналістиці – для стиску і збереження зображень відбитків пальців в автоматизованих системах обліку і збереження відеоінформації; у юриспруденції – для збереження зображень виступаючих як докази в суді; у медицині – для стиску рентгенівських і томографічних знімків в електронних картотеках; в архівній справі – для компактного представлення і збереження історично цінних зображень в цифровому вигляді; в друкарській справі – для збереження зображень, що друкуються; у військовій справі – для компактного представлення зображень, які піддаються подальшому редагуванню; у системах дистанційного зондування Землі – для стиску різних фотознімків, що передаються зі штучних супутників Землі й ін. Аналіз існуючих методів стиску зображень показав, що досягти більш високих ступенів стиску дозволяють методи, які використовують ортогональні перетворення для формування трансформант зображення. Одним із перспективних видів ортогональних перетворень є ЦВП. Воно володіє такими властивостями як обмеженість базисних функцій у часі, можливість використання цілочисельних операцій для обчислення вейвлет-коефіцієнтів, порівняно проста реалізація алгоритму і його швидке виконання. Такі переваги дозволили вибрати його в якості базового при розробці методу стиску зображень.
В розділі сформульована наукова задача дисертації, проведена її декомпозиція на ряд часткових задач. обґрунтовано розробку методу стиску зображень без втрат якості відновлених даних, що включає етапи цілочисельного перетворення колірної моделі, ЦВП елементів компонент в набір коефіцієнтів, комбінованого беззбиткового кодування коефіцієнтів.
У другому розділі розглянуті питання цілочисельного перетворення колірної моделі зображень та ЦВП колірних компонент . Удосконалено цілочисельний метод зміни колірної моделі зображення. Розроблено алгоритм кодування/декодування високочастотних трансформант ЦВП.
При аналізі існуючих методів перетворення колірної моделі зображення було виявлено, що найбільш розповсюджені з них мають такі недоліки:–
використання нецілочисельних операцій при формуванні нових колірних компонент, що викликає похибку при зворотному перетворенні;–
значення колірнорізнісних компонент у всіх колірних моделях можуть приймати як додаткові, так і від’ємні значення (необхідно один біт для представлення знаку), що викликає збільшення розрядності двійкових слів, які використовуються для опису компонент.
Уникнути першого недоліку можна застосувавши цілочисельний метод перетворення колірної моделі зображення. Удосконалене пряме перетворення має вигляд:
, , ,
де R, G, B – матриці значень точок зображення в колірній моделі RGB;
Yz', Uz', Vz' – матриці значень точок зображення в новій колірній моделі.
Зворотне перетворення представлене в модифікованому виді:
, , .
Для усунення другого недоліку запропоновано відокремити знакову площину матриць Uz/ і Vz/ з наступним записом двовимірного масиву двійкових чисел в одномірний масив байт-знаків. Процедура формування двійкових чисел знаків колірнорізнісних компонент представлена наступним виразом:
VБЗН= (1)
де VБЗН – масив біт знакової площини компоненти Uz/ (Vz/), N – кількість елементів матриці Uz/ (Vz/). Далі виконується запис двійкового потоку VБЗН в одномірний масив байт-знаків, що позначається як VЗН . Якщо VБЗН виявиться не кратним 8, то останній байт VЗН [N/8+1] масиву VЗН буде неповним. Тому необхідно вилучити останні біти:
VЗН [N/8+1]<<8 – r, (2)
де r – кількість біт останнього неповного байта, << – операція зсуву вліво. Відповідно до виразу (2) останній байт буде складатися з r старших розрядів і (8–r) нулів.
У результаті дослідження основних методів ЦВП у якості базових було обрано два: ЦВП Хаара (далі ВП 2,2), що забезпечує мінімальний час виконання перетворення, і ЦВП Коена-Добеші-Фово (далі ВП 5,3), що забезпечує максимальний ступінь стиску.
Виконання ВП 2,2 у цілочисельному вигляді записується так:
(3)
(4)
зворотне перетворення:
де - операція округлення з відкиданням залишку;
- значення матриці вихідної компоненти зображення (верхній індекс означає рівень декомпозиції, нижній – номер значення в матриці).
Розкладання компонентів зображення за формулами (3) і (4), що застосовується до рядків (стовпців) матриці значень компонент зображення називається одноканальним ЦВП. Повторне застосування перетворення до стовпців (рядків) матриці значень зображення називається двоканальним. Результатом двоканального ЦВП є формування матриць .
При такому формуванні матриць необхідно двовимірну матрицю відліків зображення перетворити в одномірний масив. Запропонований спосіб виконання ВП 2,2 дозволяє здійснити необхідні обчислення в двовимірній матриці в одному програмному циклі.
Декомпозиція зображення за допомогою ВП 2,2 може бути представлена так:
(5)
(6)
(7)
(8)
реконструкція у вигляді:
(9)
(10)
(11)
(12)
де MIHHn, MILHn, MIHLn, MILLn, HLHn, LHLn – проміжні значення.
Відповідно до формул (5-12) результатом прямого ЦВП є одномірні масиви , а результатом зворотного – вихідна двовимірна матриця елементів зображення. Запропонований спосіб дозволяє скоротити час обчислення вейвлет-коефіцієнтів Хаара в 1,5 рази (табл. 1).
Виконання однорівневої вейвлет-декомпозиції зображення дозволяє отримати тільки 75 % високочастотних коефіцієнтів від їх загальної кількості. Збільшити кількість високочастотних коефіцієнтів (для цифрового опису яких необхідно менше число біт) можливо шляхом ітераційного застосування ВП до тієї частини низькочастотних коефіцієнтів, що залишилися. Оптимальна кількість повторів ВП була визначена теоретично. у відповідності до виразу (13) достатньо обмежитися трьома рівнями декомпозиції, оскільки подальша декомпозиція зображення не призводить до суттєвого підвищення ступеня стиску (так як кількість низькочастотних коефіцієнтів вже після третього рівня декомпозиції складає менше 2% від їх загальної кількості).
, (13)
де – обєм цифрового опису низькочастотної області;
– обєм цифрового опису вихідного зображення;
n – кількість повторів ВП.
Таблиця 1
Час формування вейвлет-коефіцієнтів Хаара існуючим та запропонованим методами (обчислювальна платформа – Celeron 1 ГГц, 128 Мбайт ОЗП)
Метод формування вейвлет-коефіцієтів Хаара | Об’єм зображення, Кбайт
117 | 768 | 3708
Класичний, мс | 46,5 | 84 | 300
Розроблений, мс | 29 | 55 | 205
Експериментальне визначення кількості ітерацій ЦВП (рис. 1) підтвердило результати теоретичних розрахунків.
Рис. 1. Залежність ступеня стиску зображень в колірній моделі RGB з різною частотою колірного перепаду від кількості рівней декомпозиції (для ВП 2,2)
Для створення ефективного методу стиску зображень на основі ЦВП необхідне знання статистичних властивостей високочастотних (ВЧ) трансформант даного перетворення. Аналіз властивостей бітових площин (БП) ВЧ трансформант дозволив виділити масиви з різними статистичними властивостями, а саме: блок знаків вейвлет-коефіцієнтів , 3-х розрядний блок старших і 4-х розрядний блок молодших БП (рис. 2). Обґрунтування такого розбиття трансформант підтверджується значенням ступеня стиску зображень при кодуванні блоків різної розрядності (табл. 2) та кількістю ненульових елементів в старших і молодших БП блоків різної розрядності (табл. 3).
Рис. 2. Схема групування трансформант ЦВП: а) подання вихідних ВЧ трансформант ВП; б) розбиття ВЧ трансформант ЦВП на старші та молодші БП
Таблиця 2
Значення ступенів стиску зображень при кодуванні блоків різної
розрядності (колірна модель Yz/Uz/Vz/ і ВП 5,3)
Розрядність блоків
трансформант, біт |
Середня ступінь стиску, раз
3 | 4 | 2,22
4 | 3 | 2,35
2 | 5 | 2,11
5 | 2 | 2,27
Елементи блоку формуються відповідно до виразів (1) і (2), а блоки і за формулами (14) і (15):
, (14)
, (15)
де – операція логічного додавання числа 0?0F (15 у десятковій системі числення);
– значення і-го ВЧ вейвлет-коефіцієнту.
Особливістю машинного подання відємних значень ВЧ трансформант є те, що вони відображаються в додатковому коді. Для зменшення відмінності в представленні від’ємних і додатних значень вейвлет-коефіцієнтів пропонується додатковий код від’ємних коефіцієнтів перетворити в прямий за допомогою вирівнювання (16):
(16)
При вирівнюванні (16) відбувається не тільки перетворення додаткового коду від’ємних коефіцієнтів, але і зменшення величини їх модуля на одиницю, що позитивно впливає на результуюче значення ступеня стиску.
Таблиця 3
Процентне співвідношення суми ненульових елементів до їх загальної кількості
в старших та молодших БП при різному розбитті трансформант зображень
Частота колірного перепаду | Колірні компоненти зображення
Yz/ | Uz/ | Vz/
Спосіб розбиття ВЧ трансформант зображення, біт
3-4-х | 2-5-х | 3-4-х | 2-5-х | 3-4-х | 2-5-х
0,9-0,99 | 103,1 | 114,1 | 100 | 111 | 100,9 | 112,3
0,8-0,89 | 98,1 | 107,9 | 94,8 | 104,6 | 94,9 | 104,7
0,7-0,79 | 93,9 | 99,1 | 91,4 | 95,5 | 92,1 | 97,3
Всього | 98,4 | 107 | 95,4 | 103,7 | 96 | 104,8
Таким чином, було отримано метод групування ВЧ трансформант ЦВП, який базується на незалежній обробці знакових блоків вейвлет-коефіцієнтів та колірних компонент зображення, а також блоків старших та молодших БП вейвлет-коефіцієнтів. Включення етапу групування блоків ВЧ трансформант дозволяє незалежно обробляти (кодувати) блоки з однаковими статистичними властивостями.
Третій розділ присвячений питанням беззбиткового кодування і декодування знакових масивів колірнорізнісних компонентів і вейвлет-коефіцієнтів, молодших і старших БП ВЧ трансформант ЦВП. Запропоновано метод кодування зображень, представлених незалежними блоками. розглянуто особливості програмної реалізації даних методів.
Зосередження основної енергії зображення в молодших БП (близько 85 % значень елементів ВЧ трансформант знаходяться в діапазоні [-15; 15]) дозволяє застосувати для кодування відліків блоку арифметичний метод, а для блоку - метод довжин серій.
За основу для розробки арифметичного кодера був узятий відомий QM - кодер фірми IBM для кодування тексту. модифікація алгоритму завершення кодування зображення дозволила розробити ефективний арифметичний кодер для джерел з різним алфавітом. Оскільки АК відноситься до статистичних методів беззбиткового кодування, то доцільно обробляти зображення незалежними блоками з однаковими статичними властивостями. при кодуванні зображення чотирма незалежними блоками (К=4), внаслідок найбільш ефективного врахування статистичних властивостей даних блоків, спостерігається підвищення ступеня стиску на 5 % (рис. 3).
Особливістю розробленого кодера довжин серій є те, що при читанні першого нуля (ознаки лічильника) із закодованого потоку, декодер записує “0” у вихідний потік. таким чином, максимальна кількість нулів, що задається одним напівбайтом, дорівнює 8, а відповідно одним байтом буде кодуватися серія максимум із 16 нулів.
Рис. 3. Залежність ступеня стиску від кількості блоків зображення, що незалежно оброблюються (для ВП 2,2)
Стиск зображень виконується в наступній послідовності:
1. Введення в систему вихідних даних – цифрового зображення в колірній моделі RGB (у вигляді матриці 24-бітних цілих чисел по 8 біт на кожну колірну складову).
2. Зміна колірної моделі RGB на Yz/Uz/Vz/.
3. Виділення знакової площини колірнорізнісних компонент зображення.
4. Виконання ЦВП із компонентами зображення.
5. Виділення блоку знаків вейвлет-коефіцієнтів.
6. Групування ВЧ трансформант зображення.
7. Кодування знакових блоків колірнорізнісних компонентів і вейвлет-коефіцієнтів методом АК джерел з великою потужністю алфавіту (ВАК), блоків молодших БП методом АК джерел з малою потужністю алфавіту (МАК), блоків старших БП методом довжин серій.
8. Формування файлу стиснутого представлення вихідного зображення.
Відновлення зображення здійснюється в зворотній послідовності. результат повного відновлення (“біт у біт”) стиснутого зображення залежить від оберненості всіх етапів у методі стиску. Метод цілочисельного перетворення колірної моделі зображень передбачає повне відновлення значень вихідної моделі. Результат повного відновлення коефіцієнтів при зворотному ЦВП залежить від двох умов:–
відповідного розрахунку фільтрів аналізу і синтезу ЦВП;–
відповідного продовження сигналу кінцевої довжини після закінчення послідовності при ЦВП.
Базисні функції, що застосовуються в цілочисельних ВП 2,2 і ВП 5,3 є симетричними вейвлетами. Це означає те, що фільтри аналізу і синтезу передбачають повне відновлення сигналу. Друга вимога збереження повного відновлення сигналу пов'язана з забезпеченням парності довжини сигналу після кожного рівня його вейвлет-декомпозиції. При наявності сигналу непарної довжини після проріджування втрачається частина інформації або додається один зайвий відлік. Тому при використанні трьох ітерацій вейвлет-декомпозиції необхідно мати сигнал довжиною мінімум 23 елементів. Для розробленого методу стиску дана умова означає, що ширина і висота зображення повинні бути кратні 8. Запропонований спосіб доповнення ширини і (або) висоти зображення до необхідних величин записується наступними виразами:
, значень
, значень
де і – кількість стовпців і рядків зображення кратні восьми;
і – кількість стовпців і рядків вихідного зображення.
Четвертий розділ присвячений розробці ядра інформаційної технології стиску зображень без втрат. Розглядаються питання переповнення стеку даних і обмеження роботи арифметичного кодера і кодера довжин серій. Приведено порівняльні оцінки ступеня і часу стиску розроблених і існуючих методів стиску і відновлення зображень без втрат. Розроблено аналітичні вирази для оцінки теоретичного ступеня стиску зображень запропонованим методом. Оцінена завадостійкість розробленого методу і розраховано обсяг службових даних для різних режимів роботи.
При дослідженні характеристик ВАК і МАК доведено умови виключення від’ємного переповнення при масштабуванні накопичених ймовірностей символів, переповнення розрядної сітки при цілочисельному множенні, показані обмеження при застосуванні методів. Обмеженість реалізацій даних методів АК пов'язана із змінними, що використовуються для представлення значень лічильників частот, а також залежить від закодованої послідовності і точності арифметичних операцій. Значення лічильників частот представляється ?-бітами, розрядність арифметичного коду ?-бітами, тоді коректна робота програми забезпечується при
і , (17)
де ? – необхідна точність арифметичних операцій.
Для ВАК ? = 14, в = 16, е = 31, ?обто умова (17) виконується, для МАК ? = 7, в = 9, е = 16, ?о теж свідчить про коректну роботу програми. Ситуацій переповнення кодера довжин серій не виникає, тому що він не використовує будь-яких арифметичних операцій крім додавання (серій нулів). Результати обчислення обсягів службових даних при АК трансформант зображення представлені в табл. 4.
Метою збільшення кількості блоків К (тобто зменшення обсягів окремих блоків) є підвищення завадостійкості методу стиску зображень. Так у режимі неблокової обробки (К=1) перекручування одного байта стиснутих даних веде до втрати всього зображення; у режимі роздільної обробки колірних компонент зображення (К=4) і різних рівнів вейвлет-декомпозиції (К=8) втрата всього зображення можлива при виникненні помилки в 73,4% Vстис; у режимі роздільної обробки кожної високочастотної матриці окремого рівня декомпозиції (К=29) втрата всього зображення можлива при виникненні помилки в 47,4% Vстис. Приклади вимушеного спотворення (інвертування першого байту блоку, що незалежно оброблюється) закодованої послідовності відображено на рис. 4.
Таблиця 4
Максимальний і середній обсяги службових даних при арифметичному
кодуванні блоків для різних режимів обробки зображень
Режим обробки | Кількість блоків, що оброблюються | Максимальний об’єм
службових даних, байт | Середній об’єм
службових даних, байт
1. | К=1 | 108 | 108
2. | К=4 | 127 | 125
3. | К=8 | 179 | 174
4. | К=29 | 980 | 913
Таким чином, завадостійкість пропонованого методу стиску, на відміну від існуючих (що використовують кодування Хаффмана, кодування довжин серій, словникові методи), у яких перекручення будь-якого символу приводить до зриву подальшого відновлення зображення, можна вважати прийнятною.
Значення теоретичного ступеня стиску зображень може бути визначене в такий спосіб:
,
де
m – кількість рівнів декомпозиції зображення;
і – обсяг цифрового представлення вихідного зображення і службових даних;
, і – число елементів у знаковому блоці вейвлет-коефіцієнтів, колірнорізнісних компонентах і блоці молодших БП;
, – ентропія елементів у знаковому блоці вейвлет-коефіцієнтів, блоці колірнорізнісних компонент і молодших БП;
, і – середня збитковість елементів у знаковому блоці вейвлет-коефіцієнтів, блоці колірнорізнісних компонент і молодших БП;
– число значущих (ненульових) елементів у блоках старших БП;
– число серій нульових елементів у i-тому блоці даних.
Значення ступеня стиску, обумовлене даною формулою, відрізняється не більше ніж на 10 % від практично знайденого значення. Практично ступінь стиску визначається за допомогою програми, що реалізує запропонований метод для тестового пакета з 300 нестиснутих (у форматі BMP) сильнонасичених зображень. Результати порівняння ступенів стиску забезпечуваних розробленим методом і деякими існуючими представлені на рис. 5 а.
На основі порівняльного аналізу розроблених методів стиску і відновлення зображень зроблено наступний висновок: розроблений метод стиску зображень без втрат перевершує за ступенем стиску формат PNG на 15–20%, формат JPEG-LS на 3–5%.
Час виконання стиску зображення визначається часом, необхідним для виконання всієї сукупності процедур, що складають алгоритм стиску:
, c
де: – час, що затрачується на процедуру зміни колірної моделі;
– час стиску знакового блоку колірнорізнісних компонент Uz/ і Vz/;
– час виконання прямого ЦВП;
– час стиску знакового блоку вейвлет-коефіцієнтів;
– час стиску блоків молодших БП;
– час стиску блоків старших БП;
– час групування ВЧ трансформант ЦВП зображення;
– час виконання додаткових процедур;
m – кількість рівнів вейвлет-декомпозиції зображення;
k – кількість колірних компонент зображення;
– кількість блоків молодших і старших БП, які незалежно оброблюються (залежить від обраного режиму роботи, тобто від К).
До додаткових процедур відносяться:–
операція читання заголовка файлу;–
операція запису низькочастотної області третього рівня декомпозиції;–
операція формування стиснутого файлу із закодованих блоків.
Результат оцінки часу стиску (відновлення) зображень представлений на рис. 5 б. Аналіз діаграми дозволяє зробити висновок про те, що час стиску зображень, який забезпечується розробленим методом, тотожний часу стиску форматами PNG і JPEG-LS (рис. 5 б).
а) б)
Рис. 5. Порівняльна оцінка розробленого і деяких існуючих методів стиску
зображень без втрат: а) за ступенем стиску; б) за часом стиску.
У додатках приведені вихідні програмні коди розроблених методів стиску та відновлення зображень, а також програми для оцінки відповідності вихідних зображень відновленим.
ВИСНОВКИ
Головним результатом проведених досліджень є розроблений автором метод стиску-відновлення кольорових фотореалістичних цифрових зображень, заснований на ЦВП й АК. Розроблений метод дозволяє підвищити ступінь стиску зображень, а метод відновлення забезпечує повну ідентичність (“біт у біт”) декодованих зображень після їх стиску. Використання розроблених методів у інформаційних технологіях АСПІУ дозволяє зменшити об’єми запам'ятовуючих пристроїв і знизити навантаження на канали зв'язку за рахунок компактного представлення зображень. Розробка нового методу стиску зображень містить у собі наступні основні етапи, описані в дисертаційній роботі.
1. Аналіз існуючих методів стиску зображень без втрат, який показав, що вони забезпечують мале значення (1,5–2 разів) ступеня стиску. У той же час, ріст кількості ПП, що використовують для обробки зображень тільки методи стиску без втрат, вимагає створення нових більш ефективних (за ступенем стиску) методів компактного представлення зображень (розділ 1). Отже, існує необхідність в удосконаленні методів стиску зображень без втрат.
2. Визначено, що одним із шляхів вирішення даної задачі є розробка комбінованого методу стиску зображень без втрат, що включає в себе зміну колірної моделі вихідних зображень, ортогональне перетворення, кодування значень трансформант перетворення (розділ 2).
3. Аналіз існуючих методів перетворення колірної моделі зображень, який показав, що їхнє застосування в розробленому методі забезпечує підвищення ступеня стиску зображень на 15–25%. Цілочисельне перетворення колірної моделі RGB, у якій представлені вихідні зображення, у модель Yz/Uz/Vz/ дозволяє не тільки зосередити енергію в складовій яскравості, але й зменшити її ентропію на 3-5% у порівнянні зі складовою яскравості існуючих колірних моделей (розділ 2).
4. Використання ЦВП для декореляції відліків компонент вихідного зображення базується на таких його перевагах: базисні функції обмежені в часі, що дозволяє аналізувати локальні властивості окремих ділянок зображення; вихідне зображення не розкладається на квадрати n?n елементів; існує можливість використання цілочисельних операцій для формування трансформант ЦВП; порівняно проста реалізація алгоритму і його швидке виконання.
Розроблений метод формування вейвлет-коефіцієнтів Хаара після одного проходу за матрицею колірних компонент зображення дозволяє скоротити час виконання даного перетворення в 1,5 рази (розділ 2).
5. Необхідність застосування різних методів беззбиткового кодування трансформант зображення викликана наявністю в них ділянок з різними статистичними властивостями. Для більш ефективного врахування статистичних властивостей блоків зображення розроблено метод їх групування (розділ 2).
6. Для стиску блоків молодших БП трансформант зображення запропоновано метод цілочисельного АК, що використовує адаптивну модель відновлення відліків. Головна відмінність арифметичного кодера від існуючих полягає в можливості кодування джерел з різною потужністю алфавіту (розділ 3). Блок старших БП кодується методом довжин серій (розділ 3).
7. Для підвищення завадостійкості методу стиску запропоновані варіанти кодування транформант роздільно: за колірними компонентами, за рівнями вейвлет-декомпозиції зображення і за високочастотними матрицями ЦВП (розділ 3).
8. Розроблені аналітичні вирази для розрахунку обсягу незалежно стиснутих блоків і ступеня стиску зображень у цілому показують, що середній ступінь стиску знаходиться в межах 1,9–2,85 раз у залежності від типу ЦВП і насиченості даних. Експериментально визначений ступінь стиску виявився менше теоретичного на 7–10% (розділ 4).
9. Оцінка часу стиску зображень запропонованим методом тотожна часу стиску, що забезпечується форматами PNG і JPEG-LS і складає приблизно 0,6 с для зображень об’ємом 800 Кбайт (експеримент проводився на ЕОМ Celeron 1 ГГц із 128 Мбайт ОЗП).
10. Достовірність нових наукових положень дисертації підтверджена: коректним використанням математичного апарату теорії ортогональних перетворень, теорії зв’язку та кодування інформації, теорії обробки і передачі зображень та математичної статистики; задовільною збіжністю результатів математичного моделювання з експериментальними даними.
Використання засобів, що реалізують розроблені методи стиску і відновлення зображень у складі різних комплексів автоматизованих систем переробки інформації і управління, дозволяє скоротити необхідний об’єм запам'ятовуючих пристроїв на 45-55%.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1. Резуненко А.А., Стрюк А.Ю. Методы целочисленного преобразования цветовых координат видеоданных // Радіоелектронні і комп’ютерні системи, Харків: ХАІ. – 2004. – №1(5). – С. 13-16.
2. Стрюк А.Ю., Клименко К.С., Резуненко А.А. Статистические свойства видеоданных, подвергнутых дискретному вейвлет-преобразованию // Зб. наук. пр. К.: ІПМЕ, НАНУ. – 2003. – Вип. 22. – С. 198-201.
3. Резуненко А.А., Клименко Л.А. Метод целочисленного арифметического кодирования видеоданных // Інформаційно-керуючі системи на залізничному транспорті, Харків, УДАЗТ. – 2004. – №2 (46). – С. 13-16.
4. Резуненко А.А., Стрюк А.Ю. Метод комбинированного кодирования высокочастотных трансформант вейвлет-преобразования // Інформаційно-керуючі системи на залізничному транспорті, Харків, УДАЗТ. – 2004. – №3 (47). – С. 66-70.
5. Резуненко А.А. Оценка характеристик арифметического кодирования видеоданных, представленных независимыми блоками // Радіоелектронні і комп’ютерні системи, Харків: ХАІ. – 2004. – №4(8). – С. 25-30.
6. Рубан І. В., Колмиков М.М., Резуненко А.А. Адаптивный алгоритм сжатия данных в компьютерных сетях // Зб. наук. пр. “Системи обробки інформації”. – Харків, ХВУ. – 2003. – Вип. 4. – С.67-72.
7. Резуненко А.А. Метод сжатия графических изображений на основе рекурсивного описания блочных полей // Мат. 7-го Междунар. молодежного форума “Радиоэлектроника и молодежь в ХХI веке”. – Харьков: ХНУРЭ, 2003. – С. 145.
8. Стрюк А.Ю., Резуненко А.А. Метод сжатия видеоданных с использованием вейвлет-преобразования // Мат. 3-ей Междунар. научно-техн. конф. “Проблемы информатики и моделирования”. – Харьков: НТУ “ХПИ”, 2003. – С. 24.
9. Резуненко А.А., Дядык Д.Ф. Оценка влияния смены цветовых моделей на эффективность методов сжатия видеоданных // Мат. 8-го Междунар. молодежного форума “Радиоэлектроника и молодежь в ХХI веке”. – Харьков: ХНУРЭ, 2004. – С. 77.
10. Резуненко А.А., Способы кодирования изображений независимыми блоками // Зб мат. міжвузівс. науково-техн. конф. „Факультету ”Телекомунікації” 5 років!”.–Полтава: ПВІЗ, 2004.–С. 58.
11. Резуненко А.А., Стрюк А.Ю. Способ быстрого вычисления двумерного вейвлет-преобразования Хаара // Мат. 4-ой Междунар. научно-техн. конф. “Проблемы информатики и моделирования”. – Харьков: НТУ “ХПИ”, 2004. – С. 49.
АНОТАЦІЯ
Різуненко А. О. Методи та інформаційна технологія стиску зображень в автоматизованих системах на основі вейвлет-перетворень. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – автоматизовані системи управління і прогресивні інформаційні технології. Полтавський військовий інститут зв’язку. Полтава, 2005 р.
У дисертаційній роботі показано, що підвищення ефективності функціонування автоматизованих систем переробки інформації і управління можливе шляхом зменшення об’ємів запам'ятовуючих пристроїв і зниження навантаження на канали зв'язку, за рахунок компактного представлення зображень. Розроблено метод стиску зображень без втрат, що базується на застосуванні ЦВП й арифметичного кодування трансформант перетворення. Стиск зображень забезпечується за рахунок зниження статистичної збитковості трансформант вейвлет-перетворення. Ступінь стиску без втрат фотореалістичних зображень складає в середньому 1,9–2,85 рази. Розроблено метод відновлення зображень, що забезпечує повну ідентичність відновлених після стиску зображень вихідним. Запропоновані методи реалізовані у вигляді інженерних методик, алгоритмів та програмних засобів для стиску зображень без втрат якості відновлених даних.
Ключові слова: зображення, метод стиску без втрат, вейвлет-перетворення, арифметичне кодування.
АННОТАЦИЯ
Резуненко А. А. Методы и информационная технология сжатия изображений в автоматизированных системах на основе вейвлет-преобразований. – Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 – автоматизированные системы управления и прогрессивные информационные технологии. Полтавский военный институт связи. Полтава, 2005 г.
Диссертация посвящена разработке метода сжатия изображений без потерь, позволяющего повысить эффективность функционирования автоматизированных системах переработки информации и управления путем уменьшения объемов запоминающих устройств и уменьшения нагрузки на каналы связи.
Проведен анализ существующих методов сжатия изображений и показано, что современные методы сжатия фотореалистичных изображений без потерь обеспечивают малое значение (1,5-2 раз) степени сжатия, что мотивирует исследователей совершенствовать данные методы их компактного представления. Более высокие степени сжатия изображений достигаются при применении в методе аппарата ортогональных преобразований, этапа смены цветовой модели, комбинированного безизбыточного кодирования коэффициентов преобразования при эффективном учете статистических свойств различных участков изображения.
Усовершенствован метод целочисленного преобразования цветовой модели, который позволяет снизить энтропию яркостной составляющей изображений на 3-5 %. Использование цветового пространства Yz/Uz/Vz/ позволяет повысить степень сжатия по сравнению с изображениями, представленными в цветовой модели RGB на 15 – 25 %. Предложен способ отделения знаковых плоскостей цветоразностных компонент (Uz/ и Vz/), что позволяет обрабатывать их точно также как и яркостную составляющую.
Детальный анализ и исследование способов целочисленного вейвлет-преобразования позволил выбрать в качестве базовых вейвлет-преобразование Хаара, как наиболее быстродействующее; и вейвлет-преобразование Коэна-Добеши-Фово, обеспечивающее максимальную степень сжатия. Определено число итераций вейвлет-преобразования. При разложении изображений достаточно ограничиться тремя уровнями вейвлет-преобразования, т. к. все последующие итерации преобразования мало влияют не степень сжатия (прирост степени сжатия составит не более 1%).
Изменение статистических свойств изображения после вейвлет-преобразования вызывает необходимость группирования высокочастотных трансформант с целью более эффективного их кодирования. Оценка степени сжатия изображений при различной разрядности блоков старших и младших битовых плоскостей позволила разработать эффективный метод группирования трансформант. Разработанные методы преобразования цветовых координат и группирования высокочастотных вейвлет-трансформант изображения позволили построить схемы сжатия (восстановления) исследуемых данных.
Анализ существующих методов безизбыточного кодирования показал, что префиксные методы кодирования трансформант изображения требуют больших вычислительных ресурсов и обладают существенной временной задержкой при формировании кода. Последовательное формирование кода на основе накопления вероятностных оценок символов характерно для метода арифметического кодирования. Поэтому наилучшим для сжатия потока
