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

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

НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ

УДК 621.377.624

Спеціальність 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем

Автореферат

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

кандидата технічних наук

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

Колганова Олена Олегівна

Київ - 2009



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

Робота виконана у Національному авіаційному університеті Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор Шутко Микола Олександрович, Національний авіаційний університет МОН України, професор кафедри аеронавігаційних систем

Офіційні опоненти: доктор технічних наук, професор Мислович Mихайло Володимирович, Інститут електродинаміки НАН України, завідувач відділу №12 ;

доктор фізико-математичних наук, професор Глазунов Микола Михайлович, Національний авіаційний університет МОН України, завідувач кафедри прикладної інформатики

Захист відбудеться 02.12.2009 р. о 15 годині на засіданні спеціалізованої вченої ради К 26.062.11 при Національному авіаційному університеті за адресою: 03058, Київ-58, просп. Космонавта Комарова, 1.

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

Автореферат розіслано 30.10. 2009 р.

Вчений секретар спеціалізованої вченої ради кандидат технічних наук, доцент Ю.М. Крамар



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

Актуальність теми. Алгоритми стиснення зображень - область машинної графіки, що швидко розвивається. Основний об'єкт прикладення зусиль у ній - зображення - специфічний тип даних, який має свої особливості. Першою особливістю зображення є те, що воно (як і відео) потребує для зберігання набагато більшого об'єму пам'яті, ніж текст. Наприклад, не дуже якісна ілюстрація на обкладинці книги розміром 500х800 точок займає 1,2 Мб - стільки ж, скільки художня книга з 400 сторінок (60 знаків у рядку, 42 рядки на сторінці). Як приклад можемо розглянути також, скільки тисяч сторінок тексту ми зможемо помістити на CD і як мало там поміститься нестиснутих фотографій високої якості. Ця особливість зображень визначає актуальність алгоритмів архівації графіки.

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

По-третє, легко помітити, що зображення на відміну, наприклад, від тексту має надмірність у двох вимірах. Тобто як правило, сусідні точки, як по горизонталі, так і по вертикалі, в зображенні близькі за кольором. Крім того, можна використовувати подібність між колірними площинами Red (червона), Green (зелена) і Blue (синя) в алгоритмах, що дає можливість створити ще більш ефективні алгоритми. Таким чином, при створенні алгоритму компресії графіки застосовуються особливості структури зображення.

Усі алгоритми стиснення зображень можна поділити на дві групи: алгоритми стиснення без втрат (RLE, LZW, Хаффмана, JBIG, Lossless JPEG й ін.); алгоритми стиснення з втратами (JPEG, фрактальний, wavelet-алгоритм, JPEG2000 й ін.). Один з нових і достатньо могутніх алгоритмів - JPEG. Алгоритм розроблений групою експертів в області фотографії спеціально для стиснення 24-бітових зображень - JPEG - Joint Photographic Expert Group - підрозділ в рамках ISO (Міжнародної організації по стандартизації). Практично він є стандартом де-факто для повнокольорових зображень. Оперує алгоритм областями 8x8, на яких яскравість і колір змінюється порівняно плавно. В цілому алгоритм заснований на дискретному косинусоїдальному перетворенні (ДКП), вживаному до матриці зображення для отримання деякої нової матриці коефіцієнтів. Внаслідок цього при розкладанні матриці такої області в подвійний ряд по косинусах значущими виявляються тільки перші коефіцієнти. Таким чином, стиснення в JPEG здійснюється за рахунок плавності зміни кольорів в зображенні. Для отримання початкового зображення застосовується зворотне перетворення.

Сучасні популярні стандарти MPEG4, DivX 5.x, JPEG2000 та відомі графічні програмні засоби Corel DRAW 9/10 широко використовують вейвлет-технології обробки зображень. Вейвлет-обробка сигналів забезпечує можливість досить ефективного стиснення сигналів і їх відновлення з малими втратами якості.

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконана в рамках державної науково-дослідної роботи 0108U008199 “Інфобанк-НАУ”.

Мета і завдання дослідження. Метою роботи є вирішення науково-технічної проблеми підвищення ефективності програмних засобів стиснення графічних даних в комп`ютерних системах передачі та зберігання інформації у базах даних. Для цього створено новий метод стиснення зображень, який має вищий коефіцієнт стиснення та кращу швидкодію декомпресії, ніж ті математичні методи, що використовуються у відомих фото- та відеокодеках JPEG, JPEG2000, MPEG4, DivX 6.x, Н.263.

Об'єкт дослідження - комп`ютерні системи обробки, зберігання та передачі графічних даних. програмний комп'ютерний декомпресія база

Предмет дослідження - алгоритми стиснення зображень.

Методи дослідження - сплайн-апроксимація за методом найменших квадратів; багатомасштабний аналіз цифрових послідовностей.

Наукова новизна одержаних результатів полягає в тому, що вперше:

розроблено сплайновий багатомасштабний розклад на основі процедури Берта (P.Burt) і Адельсона (E. Adelson), а не на основі вейвлет-перетворення;

запропоновано сплайновий багатомасштабний розклад із дробним та змінним кроком;

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

Практичне значення одержаних результатів:

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

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

запропоновані алгоритми дозволяють зменшити час основної операції декомпресії на 30-40% у порівнянні з «найшвидшою» на сьогодні технологією JPEG, тому можуть успішно застосовуватись для інтернет-систем передачі фото-, відеозображень в режимі on-line;

результати даної дисертаційної роботи використані при створенні банку даних космічних знімків на замовлення ДП «Дніпрокосмос».

Особистий внесок здобувача. Результати наукових досліджень, представлених у роботі, отримані автором самостійно. У наукових працях, опублікованих у співавторстві авторові належить: [1] - аналітичне виведення і застосування сплайн-функцій; [3] - розробка сплайнового багатомасштабного аналізу; [4] - розділ 2 “Методи побудови інтерполяційних сплайн-функцій”.

Апробація результатів дисертації. Основні наукові результати докладалися на таких наукових конференціях:

Перша міжнародна науково-технічна конференція “Теорія та методи обробки сигналів”, (Київ, 1-3 червня 2005 р.) / Національний авіаційний університет.

VII міжнародна науково-технична конференція “АВІА-2006”, (Київ, 25-27 вересня 2006 р.) / Національний авіаційний університет.

Міжнародна науково-технічна конференція “Обробка сигналів і негауссівських процесів” пам'яті проф. Кунченка Ю.П.”, (Черкаси, 21-26 травня 2007 р.) / Черкаський державний технологічний університет.

Друга міжнародна науково-технічна конференція “Теорія та методи обробки сигналів”, (Київ, 20-22 травня 2008 р.) / Національний авіаційний університет.

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

Структура та обсяг роботи. Дисертація складається з вступу, трьох розділів, висновків, списку літератури, що містить 99 найменувань, та додатку. Робота містить 59 ілюстрацій, 2 таблиці. Загальний обсяг роботи складає 126 сторінок, у тому числі 110 сторінок основного тексту.

Основний зміст

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

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

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

Стандартний конвеєр операцій, який використовується в алгоритмах стиснення зображень (на прикладі алгоритму JPEG) показано на рис. 2. Основною операцією при стисненні з втратами є дискретне косинусне перетворення в алгоритмі JPEG, або вейвлет-розклад у JPEG2000. В дисертаційній роботі пропонується на третьому кроці конвеєра проводити сплайновий багатомасштабний розклад.

Рис. 2. Конвеєр операцій, який використовується в алгоритмі JPEG

Другий розділ присвячено розробці сплайнового багатомасштабного розкладу, для побудови якого розглянуто багатомасштабний аналіз в контексті вейвлет-перетворень та використано пірамідне представлення і сплайн-апроксимація сигналу.

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

Теорія вейвлетів не є фундаментальною фізичною теорією, але вона дає зручний і ефективний інструмент для вирішення багатьох практичних завдань. В порівнянні з розкладанням сигналів на ряди Фур'є, вейвлети здатні з набагато вищою точністю представляти локальні особливості сигналів, аж до розривів 1-го роду (стрибків). На відміну від перетворень Фур'є, вейвлет-перетворення одновимірних сигналів забезпечує двовимірну розгортку, при цьому частота і координата розглядаються як незалежні змінні, що дає можливість аналізу сигналів відразу в двох просторах. Одна з головних і особливо плідних ідей вейвлетного представлення сигналів на різних рівнях декомпозиції (розкладання) полягає в розділенні функцій наближення до сигналу на дві групи: що апроксимує - грубу, з достатньо повільною часовою динамікою змін, і що деталізує - з локальною і швидкою динамікою змін на фоні плавної динаміки, з подальшим їх дробленням і деталізацією на інших рівнях декомпозиції сигналів (кратномасштабний або багатомасштабний аналіз). Розглянуті теоретичні основи побудови багатомасштабного вейвлет-аналізу дають можливість використати схему пірамідного представлення і для сплайн-аналізу.

Перспективним є поєднання багатомасштабного аналізу (БА) та сплайн-функцій, які використовуються для відновлення дискретної інформації. Сплайни у ряді ситуацій мають кращі апроксимаційні властивості, які забезпечують мінімально можливу при даній розмірності похибку. При їх застосуванні істотно зменшується обсяг обчислень. У розробку сплайнів суттєвий доробок внесли: Дж. Алберг, Е.Нільсон, С.Б. Стєчкін, Ю.М. Суботін, Ю.С. Зав'ялов, Б.І. Квасов, М.П.Корнійчук, А.О.Лигун, Б.Г. Марченко, В.П. Денисюк, О.П. Приставка та ін.

Базисні функції ермітова кубічного сплайна будуть визначаться за формулами:

, ,

, ,

, , ,

, ,

,

де

, ;

;

,;

;

;

, ;

;

, ;

; ; ;

; ;

, ; ; ;

де - кількість відліків на - му відрізку.

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

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

У вейвлет-алгоритмах розклад “шарами” ведеться зазвичай із кратністю 2, оскільки реалізація розкладу з кратністю не 2, або зі змінною кратністю потребує значних ускладнень та часових затрат на обробку. Розробка сплайнового БА дозволить під час розрахунку матриці планування за відомими формулами на кожному етапі отримати швидку реалізацію БА з кратністю не 2, або зі змінною кратністю. Тому таку сплайн-фільтрацію будемо називати багатомасштабною, а не кратномасштабною.

Нехай початкові дані представлені N дискретними відліками. За допомогою апроксимації сплайном згідно з формулами (1) знаходимо вихідну функцію f(t) (рис. 3).

Рис.3. Оброблюваний сигнал

Розглянемо спочатку приклад сплайн-розкладу із кратністю 2. Першим кроком буде проріджування вузлів “склеювання” сплайна у два рази, тобто матимемо вузлів. Апроксимація значень функції у цих вузлів дасть схожу функцію, але, звичайно з деякими похибками. Для збереження інформації про похибки знаходимо різниці між значеннями початкової та нової функцій у N вузлах. Частина таких різниць буде достатньо мала щоб можна було ними знехтувати. Тобто потрібно встановити поріг, нижче якого значення різниць приймаються рівними нулю. Кількість вагомих (тобто ненульових) деталізуючих коефіцієнтів першого рівня позначимо det1. Тоді результатом першого кроку проріджування буде значень, які потрібно зберігати для можливого відновлення початкової функції (рис.4).

Рис.4. Сплайн-апроксимація сигналу (а) і деталізуючі коефіцієнти (б) після першого кроку.

Другий крок. Знову аналогічно проріджуємо вузли склейки сплайна, отриманого після першого кроку. Тоді замість значень матимемо . І відповідно після другого кроку маємо для зберігання коефіцієнтів (рис. 5).

Рис.5. Сплайн-апроксимація сигналу (а) і деталізуючі коефіцієнти (б) після другого кроку

Відповідно третій крок дасть значень (рис.6).

Рис.6. Сплайн-апроксимація сигналу (а) і деталізуючі коефіцієнти (б) після третього кроку

Відновлення початкового сигналу відбувається в зворотному порядку:

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

Аналогічно додаються det2 та інтерполюються одержані коефіцієнти. Встановлено сигнал першого кроку стиснення.

Додаванням det1 та інтерполяцією відновлюється початковий сигнал.

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

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

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

Третій розділ містить:

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

- адаптивний сплайновий багатомасштабний розклад;

- порівняльний аналіз розроблених методів з відомими.

Двовимірний сплайновий багатомасштабний розклад. Нехай початкові дані представлені матрицею дискретних відліків. Побудова двовимірного сплайну відбувається за рахунок тензорного добутку одномірних сплайн-функцій. Однак така процедура займає багато часу через складність перемноження матриць. Адже множення великих матриць потребує багато операцій множення, додавання. Тому вигідніше апроксимувати сплайном спочатку дані по рядках матриці, а потім по стовпцях. Згідно з формулами (1) знаходимо спочатку функцію fі(п) по рядках, а потім fj(п) по стовпцях (рис.9). Розглянемо приклад сплайн-розкладу із кратністю 2:

1. Аналогічно до одномірного випадку, розглянутого в попередній главі, проводимо апроксимацію даних сплайном, щоб мати вузлів "склейки" сплайна. Так само проріджуємо точки по всіх п рядках.

2. Повторюємо таку процедуру по всіх п стовпцях. Тобто кількість коефіцієнтів зменшується з до . Сплайн будується так, щоб сума квадратів відхилень сплайна від апроксимованих точок була мінімальною.

3. Відновлюємо повну матрицю за допомогою інтерполяції сплайном (формула (1)) отриманих вузлів "склейки" спочатку по стовпцях, потім по рядках.

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

Тоді результатом першого кроку стиснення буде значень, які потрібно зберігати для можливого відновлення початкової функції (рис.10).

5. Знову аналогічно апроксимуємо дані, отримані після першого кроку. Тоді замість значень матимемо . І після другого кроку маємо для зберігання коефіцієнтів (рис.11).

6. Відповідно третій крок дасть значень (рис.12) і т.д.

Для відновлення сигналу потрібно зберігати вузли склейки останнього шару розкладу (рис.13) та ненульові відліки деталізуючих коефіцієнтів (права частина рис. 10 - 12). Аналогічно проводиться сплайн-розклад різницевої компоненти сигналу.

Розглянемо алгоритм адаптивного стиснення:

1. Аналогічно до попередньої схеми апроксимуємо перший рядок початкової матриці даних сплайном з вузлів "склейки". Проводимо цю операцію для всіх п рядків.

2. Повторюємо таку процедуру по всіх п стовпцях. Тобто кількість коефіцієнтів зменшується з до . Сплайн будується так, щоб сума квадратів відхилень сплайна від апроксимованих точок була мінімальною.

3. Знову аналогічно апроксимуємо дані, одержані після першого кроку. Тепер замість значень матимемо .

4. Відповідно третій крок дасть значень.

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

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

8. Знаходимо різниці значень матриці, знайденої в п.2, та відновленої у кожній з точок. Це будуть значення деталізуючих коефіцієнтів з урахуванням корекції похибки, позначимо їх det2k.

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

10. Аналогічно до п.8 розраховуємо відкореговані коефіцієнти деталізації у точках, які позначимо det1k.

11. Для зберігання залишаються значень функції у вузлах склейки сплайну, деталізуючі коефіцієнти det3 , та адаптовані до цієї функції det2k і det1k: . Загальна кількість значень, які будуть зберігатись у пам'яті: . Але оскільки більшість деталізуючих коефіцієнтів дорівнюють нулю, то насправді зберігання вагомих даних потребує набагато менше пам'яті.

Корекція деталізуючих коефіцієнтів у п.п. 8 і 10 дає змогу «підлаштовувати» їх для конкретного прикладу функції (або дискретних даних) з метою мінімізації похибки, тобто відбувається адаптація алгоритму до певного прикладу. Тому такий аналіз названо «адаптивним». Для відновлення сигналу потрібно зберігати вузли склейки останнього шару розкладу та ненульові відліки деталізуючих коефіцієнтів. Аналогічно проводиться сплайн-розклад різницевої компоненти сигналу.

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

Кількість операцій множення, додавання, необхідних для стиснення одного елементу, для наступних типів фотокодеків:

JPEG (на основі ДКП) - 8 операцій множення + 8 операцій додавання;

JPEG2000 (на основі чотиришарової схеми вейвлет-перетворення з 7 низькочастотними і 9 високочастотними коефіцієнтами) - біля 8*(1+1/4+1/16+1/64) операцій множення + 8*(1+1/4+1/16+1/64) операцій додавання, або 10,625 операцій множення + 10,625 операцій додавання.

Запропонований - біля 7,5*(1+1/4+1/16+1/64) операцій множення + 9*(1+1/4+1/16+1/64) операцій додавання або 9,97 операцій множення + 11,95 операцій додавання.

Кількість операцій множення, додавання, необхідних для декодування одного елементу, для наступних типів фотокодеків:

JPEG (на основі ДКП) - 8 операцій множення + 8 операцій додавання;

JPEG2000 (на основі чотиришарової схеми вейвлет-преобразования з 9 низькочастотними і 7 високочастотними коефіцієнтами) - біля 8*(1+1/4+1/16+1/64) операцій множення + 8*(1+1/4+1/16+1/64) операцій додавання, або 10,625 операцій множення + 10,625 операцій додавання.

Запропонований - біля 2,5*(1+1/4+1/16+1/64) операцій множення + 3*(1+1/4+1/16+1/64) операцій додавання або 3,32 операцій множення + 3,98 операцій додавання.

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

У даній роботі запропонований метод для стиснення з втратами порівнювався із стисненням на основі вейвлета Добеші 5-го порядку (застосування якого показало найкращі результати серед інших вейвлетів) за наступним алгоритмом:

1) розкладання на апроксимуючі і деталізуючі коефіцієнти;

2) обнулення малих деталізуючих коефіцієнтів (ДК) і пониження розрядності (квантування) тих ДК, що залишилися, до однакових середньоквадратичних відхилень між оригіналом та відновленими після стиснення зображень запропонованим і вейвлет методами;

3) архівація даних, що залишилися, ZIP-алгоритмом.

Для експериментальної оцінки можливостей розробленого алгоритму та порівняння його з відомими розглянемо приклад кольорового фотозображення:зразка знімок, наданий ДП «Дніпрокосмос».

Проведений порівняльний аналіз показав, що запропоновані алгоритми дають можливість або збільшити коефіцієнт стиснення зображень при тій самій якості на 5-15% та зменшити час основної операції декомпресії на 30-40%, в порівнянні з «найшвидшою» на сьогодні технологією JPEG, тому вони можуть успішно застосовуватись для інтернет-систем передачі фото-, відеозображень в режимі on-line.

У даній роботі пропонується використовувати вищезгаданий метод для стиснення з малими втратами, які можна знехтувати. Близько 20% елементів кожної палітри матимуть помилку в 1 од. градації сірого (з 256-ти), останні 80% - матимуть помилку 0. Очевидно, що такі втрати лежать нижче рівня природних шумів, що виникають при фотографуванні з космосу. Тоді алгоритм стиснення буде таким:

1) лінійне предиктивне кодування зображення на основі запропонованого методу;

2) архівація перетворених даних ZIP-алгоритмом.



Висновки

В дисертаційній роботі отримані такі результати:

Створено новий «сплайновий» багатомасштабний розклад, заснований на використанні пірамідного розкладу із сплайновою базисною функцією.

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

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

Зроблено варіант схеми сплайнового багатомасштабного розкладу з дробним та змінним кроком, що дозволяє підвищити ступінь стиснення на 3-5% (у порівнянні зі схемою з кроком 2).

Створено сплайновий багатомасштабний розклад з адаптивним розрахунком деталізуючих коефіцієнтів.

Обґрунтовано та експериментально показано, що запропоновані алгоритми дозволяють зменшити час основної операції декомпресії на 30-40%, в порівнянні з «найшвидшою» на сьогодні технологією JPEG, тому вони можуть успішно застосовуватись для інтернет-систем передачі фото-, відеозображень в режимі on-line.

Результати даної дисертаційної роботи використані при створенні банку даних космічних знімків на замовлення ДП «Дніпрокосмос».



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

1. Апаратна реалізація cплайн-Фур'є перетворення для обробки радіолокаційних сигналів / [Колганова О.О., Шутко В.М., Шелевицький І.В., Фіщук А.Л.]. - К.: НАУ, 2006. - С. 32-39 -(“Електроніка та системи управління”, № 3(9)) .

2. Колганова О.О. Алгоритми обробки зображень та їх особливості / Колганова О.О. - К.: НАУ, 2008.- С. 21-25. - (“Електроніка та системи управління”, № 1(15)).

3. Колганова О.О. Сплайновий багатомасштабний аналіз / Колганова О.О., Шутко М.О., Шутко В.М. - К.: ДП “Друкарня МВС України”, 2008.- С. 207-214.- (Вісник Інженерної академії, №1).

4. Сплайни в цифровій обробці даних і сигналів: [монографія] / [Шутко М.О., Шелевицький І.В., Шутко В.М., Колганова О.О.]. - Кривий Ріг: “Видавничий дім”, 2008. - 231 с.

5. LSS розклад функції Хевісайда : матеріали першої міжнар. наук.-техн. конф. [“Теорія та методи обробки сигналів”], (Київ, 1-3 червня 2005 р.) / Національний авіаційний університет. - К.: Нац. авіац. ун-т, 2005. - С. 99-100.

6. Сплайн-інтерполятори сигналів складної форми : матеріали VII міжнар. наук.-техн. конф. [“АВІА-2006”], (Київ, 25-27 вересня 2006 р.) / Національний авіаційний університет. - К.: Нац. авіац. ун-т, 2006 . - С. 23.22-23.25.

7. Особливості алгоритмів обробки зображень : праці міжнар. наук.-техн. конф. [“Обробка сигналів і негауссівських процесів” пам'яті проф. Кунченка Ю.П.”], (Черкаси, 21-26 травня 2007 р.) / Черкаський державний технологічний університет. - Черкаси: ЧДТУ, 2007. - С. 127-130.

8. Швидкодія алгоритмів стиснення зображень на основі сплайнового багатомасштабного аналізу : матеріали другої міжнар. наук.-техн. конф. [“Теорія та методи обробки сигналів”], (Київ, 20-22 травня 2008 р.) / Національний авіаційний університет. - К.: Нац. авіац. ун-т, 2008.- С. 123-124.



Анотація

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

Дисертація на здобуття наукового ступеня кандидата технічних наук зі спеціальності 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем.

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

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

Порівняльний аналіз розроблених методів з відомими показав, що запропоновані алгоритми дозволяють зменшити час основної операції декомпресії на 30-40%, в порівнянні з «найшвидшою» на сьогодні технологією JPEG, тому вони можуть успішно застосовуватись для інтернет-систем передачі фото-, відеозображень в режимі on-line.

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

Аннотация

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем.

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

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

Сравнительный анализ разработанных методов с известными показал, что предложенные алгоритмы позволяют уменьшить время основной операции декомпрессии на 30-40%, по сравнению с самой «быстрой» на сегодня технологией JPEG, потому они могут успешно применяться для интернет-систем передачи фото-, видеоизображений, в режиме on-line.

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



Summary

Kolganova O.O. Method of graphic information storage and transfer in databases given on the basis of spline multiresolution decomposition.- Manuscript.

Dissertation on the gaining of scientific degree of engineerings sciences candidate on speciality 01.05.03 - The mathematical and programmatic providing of calculable machines and systems.

The analysis of existent algorithms of graphic data compression is conducted in dissertation work. Coming from the analysis the research task is raising: development of the domestically produced codec for using in the system of compression of space pictures graphic information for storage them in a databases. To that purpose it is developed spline multiresolution decomposition for the construction of which a multiresolution analysis is considered in the context of wavelet-transformation and pyramid presentation and spline-approximation of signal is used. Bidimensional spline multiresolution decomposition is created. It is applied for the compression of the coloured image brightness and deffered components. The spline multiresolution decomposition with the adaptive calculation of a detail coefficients is offered. On the basis of developed spline multiresolution decomposition there are built the compression algorithms of graphic information are programmatic realized. They enable to improve quality of decompressed images or increase the compression factor at the same quality on 5-15% in comparison with wavelets.

The comparative analysis of the developed methods with known showed, that the offered algorithms allowed to decrease time of main operation of decompression on 30-40% compared to the most «quick» for today technology of JPEG. That is why that is why they can be successfully used for the internetsystems of photo-, video images transmission regime.

Keywords: algorithms of images compression, spline multiresolution decomposition, spline-approximation of graphic information.

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