Технологія стиску зображень в автоматизованих системах на основі вейвлет-перетворень

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

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

АВТОРЕФЕРАТ

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

05.13.06 - автоматизовані системи управління та прогресивні інформаційні технології

ТЕХНОЛОГІЯ СТИСКУ ЗОБРАЖЕНЬ В АВТОМАТИЗОВАНИХ СИСТЕМАХ НА ОСНОВІ ВЕЙВЛЕТ-ПЕРЕТВОРЕНЬ

Виконав Різуненко Андрій Олексійович

Харків - 2005



АНОТАЦІЯ

Різуненко А.О. Технологія стиску зображень в автоматизованих системах на основі вейвлет-перетворень. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - автоматизовані системи управління і прогресивні інформаційні технології. Полтавський військовий інститут зв'язку. Полтава, 2005 р.

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

вейвлет інформаційний автоматизація зображення



1. ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми дослідження. Збільшення об'ємів передаваємої інформації, зокрема відеоінформації, впливає на якість функціонування автоматизованих систем переробки інформації і управління (АСПІУ). Якість та ефективність функціонування АСПІУ знижується внаслідок підвищення навантаження на канали зв'язку. В автоматизованих системах, які функціонують в режимі реального часу, для якісної передачі цифрових зображень необхідно підвищувати швидкість передачі інформації (збільшувати пропускну здатність каналів зв'язку), що потребує значних фінансових витрат. Одним із варіантів вирішення цієї проблеми є впровадження методів стиску зображень в системи передачі інформації. За останні десять років спостерігається зростання кількості програмних продуктів (ПП), що використовують методи стиску зображень без втрат інформації. Дані методи відіграють важливу роль в АСПІУ, до складу яких входять підсистеми збереження та обробки зображень (наприклад, в криміналістиці та юриспруденції; у медицині і мікробіології; у друкарській справі; при обробці радіолокаційних і інфрачервоних знімків у задачах картографування місцевості, зондування поверхні Землі; у космічній і військовій справі та ін).

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

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] - запропоновано метод швидкого обчислення двовимірного вейвлет-перетворення Хаара.

2. ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

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

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

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

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

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

, , ,

де R, G, B - матриці значень точок зображення в колірній моделі RGB;

Yz', Uz', Vz' - матриці значень точок зображення в новій колірній моделі.

Зворотне перетворення представлене в модифікованому виді:

, , (1)

Для усунення другого недоліку запропоновано відокремити знакову площину матриць Uz^/ і Vz^/ з наступним записом двовимірного масиву двійкових чисел в одномірний масив байт-знаків. Процедура формування двійкових чисел знаків колірнорізнісних компонент.

Якщо 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)

де MIHH_n, MILH_n, MIHL_n, MILL_n, HLH_n, LHL_n - проміжні значення.

Відповідно до формул (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 є симетричними вейвлетами. Це означає те, що фільтри аналізу і синтезу передбачають повне відновлення сигналу. Друга вимога збереження повного відновлення сигналу пов'язана з забезпеченням парності довжини сигналу після кожного рівня його вейвлет-декомпозиції. При наявності сигналу непарної довжини після проріджування втрачається частина інформації або додається один зайвий відлік. Тому при використанні трьох ітерацій вейвлет-декомпозиції необхідно мати сигнал довжиною мінімум 2³ елементів. Для розробленого методу стиску дана умова означає, що ширина і висота зображення повинні бути кратні 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.

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