Моделі, методи й інформаційні технології агрегативного кодування і стиску мультимедійних даних

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

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

ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ

Автореферат

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

МОДЕЛІ, МЕТОДИ Й ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ АГРЕГАТИВНОГО КОДУВАННЯ І СТИСКУ МУЛЬТИМЕДІЙНИХ ДАНИХ

Спеціальність 05.13.06 - інформаційні технології

Іванов Володимир Георгійович

Харків - 2008

Дисертація є рукописом

Робота виконана на кафедрі інформатики й обчислювальної техніки Національної юридичної академії України імені Ярослава Мудрого та кафедрі системного аналізу і управління Національного технічного університету “Харківський політехнічний інститут” Міністерство освіти і науки України.

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

доктор технічних наук, професор Шаронова Наталя Валеріївна, Національний технічний університет “Харківський політехнічний інститут”, Міністерство освіти і науки України, завідувач кафедри інтелектуальних комп'ютерних систем.

доктор технічних наук, професор Машталір Володимир Петрович, Харківський національний університет радіоелектроніки, Міністерство освіти і науки України, декан факультету комп'ютерних наук.

доктор технічних наук, доцент Файнзильберг Леонід Соломонович, Міжнародний науково-навчальний центр інформаційних технологій і систем Національної академії наук, Міністерство освіти і науки України, провідний науковий співробітник, м. Київ.

Захист відбудеться “20” березня 2008 р. о 14.30 годині на засіданні спеціалізованої вченої ради Д 64.050.07 у Національному технічному університеті “Харківський політехнічний інститут” МОН України за адресою: вул. Фрунзе 21, Харків-2, 61002.

З дисертацією можна ознайомитись у бібліотеці Національного технічного університету “Харківський політехнічний інститут” МОН України за адресою: вул. Фрунзе 21, Харків-2, 61002.

Автореферат розісланий “14 ” лютого 2008 р .

Вчений секретар

спеціалізованої вченої ради Гамаюн І.П.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

стиск зображення хаар перетворення

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

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

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

Основні ідеї дисертаційних досліджень спираються на праці А.П. Мановцева, В.А. Свириденка, А.А. Харкевича, Д.С. Лебедєва, Л.П. Ярославського, Е.М. Бравермана, Н.В. Завалішина, М.І. Шлезінгера, П.Ф. Полякова, І.Б. Сироджи, Е.П. Путятіна, Н. Ахмеда, К.Р. Рао, Г. Ендрюса, У. Претта, А.К. Джайна, М. Кунта, Р. Дуда, П. Харта, Д. Селомона, Яна Річардсона, Р. Гонсалеса, І. Дебеши, С. Малла, Д. Форсайта й ін.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота пов'язана з науково-дослідною діяльністю кафедри інформатики та обчислювальної техніки Національної юридичної академії України імені Ярослава Мудрого і виконувалася в рамках госпдоговірних тем: “Розробка й удосконалення методів спектрального аналізу і фільтрації сигналів в ортогональних базисах” (Харківський інститут інженерів залізничного транспорту); “Прикладні задачі обробки сигналів для промислової риборозвідки” (Харківський інститут радіоелектроніки); “Адаптація програмних засобів до обчислювального середовища замовника і їхнє правове забезпечення” (Ленінградське спеціальне конструкторсько-технологічне бюро ім. В.Я. Климова, продовження теми “Автоматизована система обробки температурних полів досліджуваних об'єктів” № 01860116829/1986); “Створення та впровадження автоматизованої системи кодування і пошуку зображень печаток і штампів АС “Кліше” (Науково-дослідний експертно-криміналістичний центр при УМВС у Харківській області, договір про науково-творче співробітництво); “Проблеми криміналістичного забезпечення діяльності правоохоронних органів” (затверджена постановою Президії АПрН України від 14 лютого 2002 р. № ДР 0102U002194, Інститут вивчення проблем злочинності АПрН України, м. Харків) у яких здобувач брав участь як науковий керівник або провідний науковий співробітник.

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

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

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

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

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

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

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

Проведення узагальнення методів JPEG і вейвлет-кодування для стиску звукових даних та розроблення методу стиску на основі поетапного виділення точок екстремума в структурі сигналу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результати дисертації впроваджені у вигляді моделей, методів, алгоритмів і пакетів прикладних програм при рішенні задач ефективного кодування та багатофункціональної обробки мультимедійних даних, що підтверджується актами і довідками впровадження наступних підприємств і організацій: Центра радіофізичного зондування землі ім. О.І. Калмикова НАН і НКА України (м. Харків), Науково-виробничого підприємства “Хартрон-Аркос”, Державного науково-виробничого підприємства “Об'єднання Комунар” (м. Харків), Харківського науково-дослідного інституту судових експертиз ім. засл. проф. М.С. Бокаріуса (м. Харків), Інституту вивчення проблем злочинності Академії правових наук України (м. Харків), а також у навчальному процесі кафедри криміналістики Національної юридичної академії України імені Ярослава Мудрого (м. Харків).

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

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися на: Всесоюзном научно-техническом симпозиуме по электромагнитной совместимости (Москва, 1986); Всесоюзной школе-семинаре по методам представления и обработки случайных сигналов и полей (Харьков-Туапсе, 1987); Всесоюзной научно-технической конференции “Проблемы создания и использования отраслевых информационно-диспетчерских систем на основе компьютеризации и перспективных средств связи” (Калуга, 1988); II Республиканском семинаре “Проблемы создания систем обработки, анализа и распознавания изображений” (Ташкент, 1989); Всесоюзной научно-технической конференции “Компьютерные методы исследования проблем теории и техники передачи дискретных сигналов по радиоканалам” (Евпатория, 1990); II Всесоюзной научно-технической конференции молодых ученых и специалистов с международным участием “Контроль, управление и автоматизация в современном производстве (КУА-90)” (Минск, 1990); II Всесоюзной конференции “Повышение эффективности средств обработки информации на базе математического и машинного моделирования” (Тамбов, 1991); конференции “Проблемы создания систем обработки, анализа и понимания изображений” (Ташкент, 1991); IV International Conference “Computer Analysis of Images and Patterns CAIP`91” (Dresden, 1991); XIV Международной конференции по когерентной и нелинейной оптике (КиНО - 91) (Ленинград, 1991); I Всесоюзной конференции “Распознавание образов и анализ изображений: Новые информационные технологии (РОАИ-I-91)” (Минск, 1991); 7<sup>th</sup> IFAC/IFIP/IFORS/IMACS/ISPE SYMPOSIUM INCOM`92 “Information control problems in manufacturing technology” (Toronto, Ontario, Сanada, 1992); 10^th, 11^th ISPE/IFAC International Conference on CAD/CAM, Robotics and Factories of the Future (CARs & FOF'94, '95) (Ottawa, Canada, 1994; Pereira, Colombia, South America, 1995); 4-ій Українській конференції з автоматичного управління за участю міжнародних спеціалістів “Автоматика 97” (Черкаси, 1997); ІІІ Международной конференции “Теория и техника передачи и обработки информации” (Харьков-Туапсе, 1997); Пятой Международной конференции по распознаванию образов и обработке информации (PRIP'99) (Минск, 1999); 3-й, 6-й Международных конференциях “Цифровая обработка сигналов и её применение” (Москва, 2000, 2004); Міжнародних конференціях з управління “Автоматика - 2000, 2001, 2003, 2004, 2005, 2006” (Львов-2000, Одеса-2001, Севастополь-2003, Киев-2004, Харьков-2005, Винница-2006); Х, XI, XII, XIII, XIV, XV міжнародних науково-практичних конференціях “Інформаційні технології: наука, техніка, технологія, освіта, здоров`я” (Харків, 2002, 2003, 2004, 2005, 2006, 2007); 1-ом Международном радиоэлектронном форуме “Прикладная радиоэлектроника. Состояние и перспективы развития” МРФ - 2002 (Харьков, 2002); Міжнародна науково-практична конференція “Актуальні проблеми криміналістики” (Харків, 2003); VI Международной конференции “Цифровая обработка сигналов и ее применение” (Москва, Россия, 2004); VII, VIII Всеукраїнських міжнародних конференціях “UkrObraz`2004, 2006”: “Оброблення сигналів і зображень та розпізнавання образів” (Київ, 2004, 2006); 5-й Международной конференции “Проблемы информатики и моделирования - 2005” (ПИМ-2005) (Харьков, 2005); VI Международной конференции “Кибернетика и высокие технологии XXI века (G&T sakv 2005)” (Воронеж, Россия, 2005); VII, VIII международных научно-практических конференциях “Современные информационные и электронные технологии” (СИЭТ`2001, 2006, 2007) (Одесса, 2001, 2006, 2007).

Публікації. За темою дисертаційних досліджень опубліковано 87 наукових праць: у тому числі 31 стаття у фахових виданнях ВАК України, 1 авторське посвідчення на винахід.

Структура й обсяг дисертації. Дисертація складається з вступу, 6 розділів, висновків, додатка та списку використаних джерел. Повний обсяг дисертації складає 326 сторінок, з них: 6 рисунків на окремих сторінках, 97 рисунків за текстом, 15 таблиць за текстом, додаток на 8 сторінках, список використаної літератури із 335 найменувань на 32 сторінках.

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

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

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

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

Відповідно до цієї моделі перетворення, що перерозподіляють або упаковують максимальну кількість інформації в найменше число коефіцієнтів, забезпечують найкраще наближення елементів блоку і, як результат, дають найменшу помилку відновлення. До таких перетворень належать перетворення Фур'є, Хаара, Уолша-Адамара і дискретне косінусне перетворення (ДКП, DCT), які найчастіше застосовуються для цілей стиску даних. Шляхом чисельного моделювання на ЕОМ проведено статичний аналіз ефективності того або іншого перетворення за критерієм нерівномірності розподілу дисперсій коефіцієнтів перетворення, а також їхньої залишкової кореляції для широкого класу тестових зображень (http://www.icsl.ucla.edu), що традиційно використовуються для аналізу алгоритмів стиску даних. Усі перетворення за ефективністю порівнювалися з перетворенням Карунена-Лоева (КЛ). Власні значення і власні вектори перетворення Карунена-Лоева були отримані в цьому розділі з використанням програмного середовища Matlab.

Підтверджено, що найкращими з погляду мінімізації середньо квадра-тичної помилки, яка дорівнює сумі відкинутих коефіцієнтів, є перетворення КЛ, що одночасно цілком декорелює вихідні дані, тобто коваріаційна матриця в результаті цього перетворення стає діагональною. Однак, якщо виграш у якості відновленого зображення Zelda складає приблизно 58 % при малих коефіцієнтах стиску (К_ст=1,3) і близько 23 % при великих (К_ст=4,57), то для сильнонасичених детальних зображень печаток (pechat) цей виграш складає уже відповідно 18 і 6 відсотків.

Вейвлет перетворення досліджуваних зображень проводилося з використанням двох пар фільтрів h і hЮ.

У силу особливостей розкладаючих фільтрів h і hЮ, вейвлет-перетворення, що були реалізовані за допомогою пари фільтрів при N=3, М=9 визначені - long (довгі), а за допомогою пари фільтрів при N=2, М=2 - short (короткі).

Для оцінки ефективності і показників якості розглянутих перетворень в просторі відібраних і квантованих коефіцієнтів з бібліотеки стандартних зображень (http://www.icsl. ucla.edu) були обрані кілька класів тестових зображень, а також використовувався архів зображень печаток і штампів автоматизованої системи “Кліше”. Ефективність того або іншого перетворення оцінювалася коефіцієнтом стиску (К_ст) при однакових значеннях середньоквадратичної помилки (СКП) відновленого зображення. Аналіз отриманих даних дозволяє зробити загальний висновок про те, що для перших трьох класів розглянутих реалістичних зображень (Zelda; Lena; Cameraman) найкращий стиск забезпечує вейвлет-перетворення на основі довгих фільтрів (Wav-long). Найбільш “незручним” для стиску є зображення Boat.bmp (найменший К_ст для всіх СКП). Наступним за критерієм “незручності” йдуть зображення Cameraman.bmp, Lena.bmp і Zelda.bmp.

Перевага вейвлет-перетворень перед ДКП і перетворенням Хаара в термінах jpeg-технологій є очевидною і складає 1,4-1,6 рази для однакової якості тестових зображень. У діапазоні з малими помилками всі перетворення мають практично рівні показники. Перетворення Карунена-Лоева при малих значеннях СКП (0,06) на зображенні Zelda.bmp дає істотний виграш у стиску в порівнянні з JPEG-DСТ, потім, зі збільшенням СКП ця ефективність дещо знижується, а на зображенні Cameraman.bmp вона вже і зовсім поступається методові JPEG-DСТ. Це перетворення поступається також за ефективністю стиску методові Wav-long для перших трьох класів наведених тестових зображень і всіх значень СКП відновлення. Дисперсійний же критерій оцінки стискаючих властивостей того або іншого перетворення в порівнянні з перетворенням КЛ завжди краще в останнього.

Звертають також на себе увагу результати моделювання процесів стиску ще одного класу зображень - відбитків печаток (Pechaty.bmp), що є вмістом архіву автоматизованої багатофункціональної системи “Кліше”.

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

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

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

Система рівнянь для знаходження коефіцієнтів Хаара при числі початкових відліків сигналу N=4 має вигляд:

(3)

де d₁…d₄-значення сигналу в дискретних точках; С₁…С₄-коефіцієнти Хаара.

При додаванні п'ятого відліку сигналу d₅ перше рівняння системи (3) розбивається на два

Після нескладних перетворень систему (3) можна записати

, де

Уведемо поняття базового вектора даних N^*, який визначимо по відношенню до числа початкових вхідних відліків сигналу N як , де n=1,2,…,(2ⁿN), причому n повинно давати min Ц(N/2ⁿ); Ц(* ) - ціла частина. Тоді, у свою чергу, базові вихідні відліки сигналу х* будуть формуватися з початкових вхідних відліків за правилом , якщо p=1,2,…,(N-N*); , якщо p=(N-N*+1), (N-N*+2),…,N*... Подальший процес обробки містить у собі отримання відповідних сум Хаара у вигляді

, (9)

де n=1,2,…,(logN*-1);i=1,2,…,N*/2ⁿ; а - базові відліки сигналу . Обчисливши (9), визначимо коефіцієнти Хаара

, (10)

де m=1,2,…,logN; j=2^m-1, а для виразу, що стоїть в квадратних дужках, m*=m-1, k=2j-1. З урахуванням прийнятої індексації коефіцієнт С₀₁ (вільний член) запишеться у вигляді

. (11)

Інші коефіцієнти визначаться за формулою

(12),

де i=1,2,…,(N-N*),х(·) - початкові відліки сигналу.

Наведені вирази описують обчислювальні процедури алгоритму швидкого дискретного перетворення Хаара і дозволяють уникнути обмежень, що накладаються на кількість початкових вхідних відліків сигналу, яке може бути як складеним, так і простим числом. Кількість операцій типу додавання-вирахування цього алгоритму дорівнює 2(N-1), що істотно менше обчислень, необхідних в раніше відомих алгоритмах, коли N=r_1·r₂…r_n і N=rⁿ, r?3. Так, при N=9 і N=10 обсяг обчислень по (9)-(12) складе відповідно 16 і 18 арифметичних операцій, водночас відомі алгоритми потребують 36 і 45 арифметичних операцій.

Проводиться узагальнення отриманих обчислювальних схем одномірного перетворення Хаара на двовимірне. Розглядається також зворотне перетворення Хаара над довільним числом точок, що зводиться до рішення системи рівнянь, у яких С-коефіцієнти, d-вихідні значення сигналу:

.

Уведемо поняття першого базового вектора даних N₁*, який визначимо відносно числа початкових вхідних відліків сигналу N як N₁*=2ⁿ, де

n=1,2,…,(2ⁿ<N), причому n повинно давати min Ц(N/2ⁿ); Ц(* ) - ціла частина виразу в дужках. Другий базовий вектор, N₂*= 2N₁*, дорівнює подвоєному значенню першого. В остаточному вигляді формули синтезу вихідних відліків сигналу запишуться як:

а індекси i та j визначають відповідність значень відліків звичайних перетворень (індекс i) і коли число вхідних відліків приймає будь-яке значення (індекс j):

i=2j-1, де j=1,2,…,k*і i=2j-N₂*, коли j=(k*+Y+1),…,N; j=1,2,…,k*,k*+Y+1,…,N, а k*=M/2 (для N₂*) і j=(k*+1),…,(k*+Y) (для N₁*); A_i=C₀+C₂(-1)ⁱ, де i=0,1; A_i=A_k-3+C_k(-1)ⁱ, де i=2,3,…,(N-4), k=Ц(i/2)+2; l=(N/2-2); Q=Ц((i+1)/2)-1.

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

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

Зазначається, що реалістичні зображення, як правило, нестаціонарні й мають складну значеннєву структуру, і це ускладнює розробку відповідної адекватної моделі їх опису. Тому доводиться шукати резерви класичних методів обробки, які б враховували як можливості використовуваних перетворень, так і властивості одержувача інформації у вигляді зображень. Один з підходів, що пропонується у цьому розділі, полягає в тому, що якщо у вже класичній схемі JPEG-компресії врахувати кореляцію однойменних коефіцієнтів у всіх фрагментах зображення і провести обробку косінусних коефіцієнтів у бітових площинах представлення даних, то можна дещо підвищити ступінь стиску і відповідно якість оброблюваних зображень. Статистична близькість однойменних відліків спектра суміжних фрагментів зображення дозволяє одержати послідовність цих відліків більш гладкої форми, а використання бітових площин у представленні даних повинно більш ефективно відбиватися на результатах роботи методів стиску без втрат. Подібна модифікація класичної схеми компресії по методу JPEG-технологій дозволяє підвищити ефективність обробки зображень типу портрет (Zelda.bmp) на 14 % при задовільній якості (Е=0,12 %).

Також розвинуто й модифіковано метод стиску зображень за допомогою багатомасштабної компенсації контурів (Multi Scale Edge Compensation - MSEC), у нашому випадку на основі вейвлет-перетворень з виділенням контурів (ВПВК), що є істотною модернізацією вейвлет-стиску, основаного на швидкому алгоритмі Малла.

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

Виділення контуру основане на перетворенні типу гаусіана:

, де .

Перетворення є симетричним (по координатах i та j) низькочастотним фільтром. Припустимо, що , якщо , і , якщо . Початкове зображення представлено тепер у вигляді суми двох зображень - тла і - контуру, . Число ненульових значень у контурі має складати 3%-5% від числа пікселів у зображенні, це правило легко реалізувати алгоритмічно - шляхом автоматичного визначення параметру окремо на кожному кроці розкладання. При відновленні зображення на кожному етапі потрібно провести зворотне вейвлет-перетворення тла і додати відповідний збережений контур.

У результаті проведених досліджень були отримані якісні і кількісні оцінки використання алгоритму стиску зображень на основі ВПВК, з яких випливає, що використання алгоритму ВПВК дозволяє зменшити кількість операцій як при розкладанні, так і при відновленні зображень у порівнянні з алгоритмом вейвлет-аналізу Малла, у якому використано два квадратурних дзеркальних фільтри при розкладанні і при відновленні. Визначено перевагу в ефективності запропонованого алгоритму кодування при незмінному значенні СКП=12 %, що забезпечує виграш у коефіцієнті стиску для тестових зображень 11%-13%. У розділі також розроблено методи компресії аудіоданих. Відзначається, що використання вейвлет-перетворень при обробці звукових сигналів досліджено недостатньо. Показано, що ефективність стиску сигналу збільшується, якщо перейти до так званої схеми вейвлет-пакетів. У якості зразків вихідних звукових сигналів використовувалися файли WAV-формату, що містять мовні повідомлення, а також музичні мелодії різного характеру звучання.

Ступінь стиску мовних сигналів, представлених у форматі МР3 для обраних частот дискретизації відповідно дорівнює: 8 кГц = 3,7; 11кГц = 4,2; 22 кГц = 5.4; 44 кГц = 8,6. Таким чином, при граничному обмеженні коефіцієнтів, який дорівнює 20, ступінь стиску мовного сигналу (К) після вейвлет-обробки перевищує показники формату МР3 на 20%. Середньоквадратичне відхилення (СКВ) початкових і відновленого мовних сигналів, при використанні граничної обробки після вейвлет-перетворення не перевищує 3,5% (для частоти дискретизації 8 кГц), що забезпечує високу якість мови при відтворенні.

Використовувані музичні композиції, у форматі МР3, мають ступінь стиску для відповідних частот дискретизації: 8 кГц = 3,9; 11 кГц = 4,5; 22 кГц = 5,8; 44 кГц = 9,2. Ці значення порівнянні з відповідними показниками, отриманими за допомогою вейвлет-аналізу і граничною обробкою масштабів. Значення СКВ (Е) знаходяться в діапазоні 0,5 - 3 % для всіх частот дискретизації.

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

Проведено узагальнення методів JPEG-кодування для стиску звукових сигналів шляхом можливості використання технологічних основ відомого формату компресії зображень JPEG для обробки аудіоданих. Відображені результати досліджень впливу основних ортогональних перетворень на ступінь стиску аудіосигналів різної структури й інтенсивності. Як ортогональні базиси використовувалися наступні перетворення: перетворення Фур'є; дискретне косінусне перетворення; перетворення Хаара. Для альтернативного порівняння ступеня стиску використовувався відомий формат представлення аудіоданих МР3 (Mpeg Audio Layer3).

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

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

Важливими характеристиками рівнобіжних структур Хаара для цифрової обробки сигналів є продуктивність P, обсяг обладнання Q і питома продуктивність V, які визначимо відповідно, як:

; ; .

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

Доцільним у практичному відношенні бачиться таке поняття, як “ефективність процесорного поля” Е:

,

де n_i - число процесорних елементів (ПЕ), яке необхідне для реалізації паралелізму в такті i, q - число тактів виконання паралельного алгоритму, що дорівнює log₂N. Величина Е - середнє завантаження процесорних елементів (ПЕ) при виконанні конкретного паралельного алгоритму. Для уточнення цього поняття вводимо характеристику “надмірність структури” або “коефіцієнт завантаження обладнання” R, що показує відношення сумарного числа працюючих процесорів М до числа непрацюючих М* при кожному такті рішення задачі й у цілому після її завершення:

; ; ,

де i у числівнику формули для міняється від log₂N до 1 із кроком мінус одиниця.

Для різних N побудовані таблиці значень коефіцієнтів R, M і M* і проведено їх порівняльний аналіз, який показує дуже низький коефіцієнт завантаження обладнання в паралельних структурах Хаара незалежно від довжини оброблюваної реалізації. Тому запропоновані базові паралельно-послідовні структури, що дають можливість синтезу схем швидких перетворень Хаара з високим коефіцієнтом завантаження обладнання при будь-якому значенні N довжини оброблюваної реалізації сигналу шляхом нарощування елементарних базових структур та їх з'єднуванням. Проведено аналіз ефективності запропонованого підходу для двох-, чотирьох- і восьмипроцесорних структур у порівнянні з паралельними структурами на підставі визначених здобувачем характеристик і критеріїв.

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

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

У шостому розділі розроблено методи стиску зображень на основі моделей виділення і кодування областей довільної форми. Ці методи належать до другого покоління і представляють зображення в термінах текстурних областей, оточених контурами. Пропонований у роботі метод контурно-текстурного кодування зображень на основі вирощування областей, який базується на ідеях М. Кунта, А. Ікономопулоса і М. Кошера і спрощено для монохроматичних зображень полягає в наступному. Задавши параметром , вибираємо будь-який елемент зображення (піксель). Якщо сусідні елементи за яскравістю відрізняються менш ніж на , поєднуємо їх з даним елементом в одну область і розглядаємо наступні сусідні елементи. Коли більше не залишається суміжних з даною областю елементів, які задовольняють зазначеній умові з параметром , процедура зупиняється і починається знову з будь-якого іншого елемента зображення, не включеного в першу область. Сегментація закінчується тоді, коли кожен елемент зображення приєднано до відповідної області. Ця процедура поділяє зображення на безліч суміжних областей, зміни рівня сірого всередині яких не мають різких розривів, тобто контурів. Для кодування зображення створюється бітова карта границь областей і для кожної області записується середнє значення рівня яскравості всіх її елементів. Отримані дані кодуються без втрат за стандартом JBIG-1. Отримано залежності коефіцієнта стиску від СКВ, які показують, що характеристики кодування тестових зображень за допомогою методу вирощування областей близькі до відповідних показників при кодуванні цих зображень методом JPEG-компресії. Перевага починає виявлятися тільки при досить великих значеннях СКВ (13 %), коли кількість областей, на які сегментовано зображення, стає малою. Відновлені зображення в таких випадках мають істотні перекручування, що виявляються по різному. У JPEG-кодованих зображеннях помітна структура сегментів і помітний ефект Гібса, при кодуванні вирощуванням областей виявляється груба мозаїчна структура, що також погіршує якість зображень.

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

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

Характеристики стиску зображень на основі автоматичної класифікації істотно поліпшуються, якщо перед класифікацією застосовується декорелююче перетворення - дискретне косінусне перетворення Фур'є або перетворення Хаара. На сильнонасиченому деталями класі зображень типу “Печатка” метод стиску на основі автоматичної класифікації є дуже ефективним і досягає значень коефіцієнта стиску близько 19,8 разів, що істотно вище результатів кодування в стандартах JPEG і JPEG2000, що дають стиск у 2-4 рази при тій самій якості відновленого зображення.

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

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

Результати комп'ютерної обробки показали, що в області малих СКВ ефективність кодування практично збігається з методом чіткої автоматичної класифікації. В області високих СКВ помітну перевагу має метод нечіткої класифікації, який досягає значення коефіцієнта стиску більш 50, що в процентному відношенні складає близько 25%. Недоліком методу нечіткої класифікації (c-середніх) є великий обсяг обчислень у порівнянні з алгоритмом k-середніх, причому це розходження швидко зростає зі збільшенням числа класів і може досягати декількох порядків. У випадку контрастних зображень, наприклад, зображення відбитка печатки особливості розподілу кількості елементів по класах при нечіткій класифікації відіграють негативну роль і в кількісному вираженні складають: для нечіткої класифікації стиск - 13,7 разів, час класифікації - 3 сек.; для автоматичної класифікації - відповідно 19,8 разів і 0,04 сек.

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

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

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

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

Подальша обробка виділених областей здійснюється з різним ступенем якості за допомогою JPEG-технологій на базі дискретного косінусного перетворення, а також за допомогою багатомасштабного вейвлет-аналізу, що дозволяє у залежності від типу зображення підвищити ефективність кодування у класичній схемі JPEG-компресії на 9 %-28 % і на 9 %-33 % при використанні вейвлет-методів.

Запропонований підхід (JPEG-об'єкт) дозволив також виявити резерви класичної схеми JPEG-кодування й одержати близькі кількісні характеристики в порівнянні з вейвлет-кодуванням, що в цілому створює передумови для формування нових технологій стиску зображень на основі об`єднання узагальнених Фур'є- та вейвлет-методів обробки сигналів, теорії інформації та методів розпізнавання образів.

ВИСНОВКИ

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

Основні результати та висновки роботи полягають у наступному:

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

...