Теоретичні основи та методи стиску зображень в телекомунікаційних системах

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

Міністерство транспорту та зв'язку України

Українська державна академія залізничного транспорту

Автореферат

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

05.12.02 телекомунікаційні системи та мережі

Теоретичні основи та методи стиску зображень в телекомунікаційних системах

Виконав Баранник Володимир Вікторович

Харків - 2006



АНОТАЦІЯ

Баранник В.В. Теоретичні основи та методи стиску зображень в телекомунікаційних системах. - Рукопис.

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

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

телекомунікаційний біноміальний поліадичний відеодані



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

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

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

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

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

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

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

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

- теоретичні основи біноміально-поліадичного кодування і декодування відеоданих. Дослідження характеристик біноміально-поліадичного представлення щодо ступеня стиску і часу на обробку;

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

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

2. Розробити і дослідити теоретичні основи тривимірного біноміально-поліадичного представлення відеоданих, що містять:

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

- метод тривимірного біноміально-поліадичного відновлення зображень.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Розроблено та досліджено метод тривимірного біноміально-поліадичного відновлення зображень. На відміну від інших методів він заснований на отриманні вихідних елементів зображень за значенням їх суми, за обмеженнями на їх динамічний діапазон і за значенням відповідного номера в зв'язному усіченому біноміально-поліадичному просторі.

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

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

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

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

2. Швидке біноміально-поліадичне кодування і декодування в двомірному і тривимірному просторах, які представлені у вигляді способів і алгоритмів та доведені до програмно - апаратних реалізацій, знижують час на обробку щодо звичайного біноміально-поліадичного представлення до 90%.

3. Швидке усічене двозв'язне представлення, доведене до програмно - апаратних реалізацій дозволяє додатково скоротити час на обробку до 4 разів і додатково підвищити ступінь стиску до 2,5 разів.

4. Запропоновані методи в порівнянні з відомими методами зменшують сумарний час обробки і передачі відеоданих для швидкості передачі даних (біт/с) і середньої швидкості виконання машинних операцій (м.о./с) в середньому для сильно-, середньо- і слабонасичених зображень відповідно від 1,8 до 3; від 1,75 до 3,5 і до 4 разів.

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

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

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

У ПЕРШОМУ РОЗДІЛІ обґрунтовано наявність існуючого протиріччя між необхідними об'ємами інформаційних потоків, які вимагається обробляти і передавати без внесення погрішностей в реальному часі і обмеженими технічними можливостями телекомунікаційних систем. Показано, що для вирішення даного протиріччя необхідно здійснювати компактне представлення відеоданих. Обґрунтовується вибір показників якості і формулюється критерій ефективності функціонування підсистем обробки і передачі відеоданих (ПОПВ).

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

; (1)

; ; ; ; , (2)

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

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

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

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

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

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

, ; ; , (3)

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

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

(4)

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

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

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

Теорема про нумерацію біноміально-поліадичних чисел. Для такої, що виконуються умови (3) можна сформувати код-номер :

(5)

де - сума попередніх елементів на -му кроці кодування; - поточне значення рівня -го елементу БП числа, ; - значення суми необроблених елементів з врахуванням -го рівня елементу .

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

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

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

; (6)

(7)

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

Порівняльна оцінка різних методів кодування показує, що: ступінь стиску фрагментів зображення для БП кодування залежно від ступеня насиченості приймає в середньому значення від 3 до 7 разів, що забезпечує середній виграш щодо біноміального кодування в 2 рази, щодо поліадичного кодування в 3 рази, а щодо методів статистичного кодування досягає 70%. Оцінка часових витрат на БП кодування і декодування виявила, що така обробка в реальному часі на обчислювальних засобах, що не використовують рівнобіжних процесів обробки, ускладнена.

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

ТРЕТІЙ РОЗДІЛ присвячено розробці швидкого біноміально-поліадичного кодування і декодування та оцінки часових витрат на швидку обробку відеоданих.

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

Для вирішення першого напряму формулюється і доводиться теорема.

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

; (8)

(9)

де - вектор обмежень на діапазони елементів БП числа на -му кроці нумерації, ; - сума -х необроблених елементів БП числа.

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

, , , , (10)

де - значення -го елемента БП числа; - індекс оброблених до -го кроку елементів БП числа, .

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

Одержане швидке кодування для значень елементів, які перевищують

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

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

, (11)

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

Доведення співвідношення (11) базується на властивості періодичності біноміально-поліадичного прямокутника. Кількість обчислень, які витрачаються на знаходження біноміально-поліадичних коефіцієнтів, при переході до симетричних обчислень скорочується в середньому від 60% до 95%.

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

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

(12)

(13)

(14)

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

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

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

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

У ЧЕТВЕРТОМУ РОЗДІЛІ розробляється усічене двозв'язне біноміально-поліадичне (УДБП) представлення. Проводиться оцінка часових витрат і ступеня стиску для розробленого представлення.

Необхідність розробки УДБП представлення обґрунтовується тим, що:

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

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

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

Додаткове збільшення ступеня стиску за рахунок усіченого БП представлення щодо звичного представлення приймає в середньому значення від 1,5 до 3 разів для та від 2 до 4 разів для . Однак, це значення знижується при обробці сильнонасичених фрагментів зображень, які містять різкі сплески.

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

; ;; , (15)

сформулюємо і доведемо теорему.

Теорема про кількість допустимих двозв'язних біноміально-поліадичних чисел. Кількість допустимих біноміально-поліадичних чисел з урахуванням додаткового зв'язку значення суми з меншою за значенням сумою , які задовольняють умовам (15), рівна

,(16)

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

.

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

Для формування коду-номера двозв'язному БП числу формулюється і доводиться теорема.

Теорема про нумерацію двозв'язних біноміально-поліадичних чисел. Для пари біноміально-поліадичних чисел, що складаються з елементів і зв'язаних сумами , які задовольняють умовам (15), можна сформувати код-номер за формулами

(17)

де - кількість допустимих пар в -у -мірному БП перетині; - кількість допустимих БП чисел з сумою, рівною в -у -мірному БП перетині; - сумарна кількість рядків (стовпців), що містять суму в -у -мірному БП перетині; - сумарне кількостей рядків (стовпців), що містять суму в -у -мірному БП перетині.

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

Додаткове збільшення ступеня стиску за рахунок двозв'язного БП представлення щодо звичайного біноміально-поліадичного представлення досягає в середньому від 2,2 до 3,5 разів для та від 4,1 до 7,7 разів для . При цьому ступінь стиску сильнонасичених фрагментів зображень для двозв'язного кодування перевищує в середньому в 1,7 рази ступінь стиску на основі усіченого кодування.

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

(18)

Додаткове збільшення ступеня стиску за рахунок усіченого двозв'язного БП представлення щодо біноміально-поліадичного представлення приймає в середньому значення від 4,3 до 5,7 разів для та від 6,88 до 9,12 разів для і в середньому до 2 разів щодо усіченого і двозв'язного представлень, виграш за часом кодування, знаходиться в інтервалі від 3 до 4,2 разів залежно від ступеня насиченості зображень.

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

Тоді УДБП декодування проводиться за аналогією з виразами (12) - (14). При цьому час відновлення початкових послідовностей на основі швидкого УДБП декодування менше в середньому до 3 разів часу відновлення на основі швидкого БП декодування.

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

У П'ЯТОМУ РОЗДІЛІ розробляється метод тривимірного біноміально-поліадичного кодування зображень. Для одержаного методу проводиться оцінка ступеня стиску і кількості операцій на обробку.

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

Теорема про нумерацію тривимірних біноміально-поліадичних чисел. Для будь-якого тривимірного біноміально-поліадичного числа (ТБПЧ), цілочисельні елементи якого задовольняють обмеженням

; , , , (19)

за відомими , , та можна сформувати код-номер :

(20)

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

Однак, така нумерація має наступні недоліки:

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

2. Вибрані комбінаторні ознаки слабо враховують нестаціонарність характеристик за вертикальними перетинами ТСВ.

Звідси витікає, що метод компактного представлення тривимірних структур відеоданих повинен містити наступні етапи:

Етап 1. Визначення ознакового простору. Пропонується варіант простору, заснований у відмінності від інших на:

- додатковому використанні властивості зв'язності біноміально-поліадичних чисел за вертикальним напрямом ТСВ. Оскільки зв'язне біноміально-поліадичне кодування більш стійке до нестаціонарності оброблюваних даних, ніж усічене;

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

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

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

, ; ,

де і - поточна і максимальна кількість елементів в -у БПЧ; --й елемент -го БПЧ; - сума елементів в попередніх БПЧ; - елемент ТСВ з координатами .

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

(21)

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

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

1. Організацію процесу розподілу елементів ТСВ за послідовностями, для яких можна сформувати один код-номер з врахуванням обмежень на довжину машинного слова.

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

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

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

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

. (22)

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

. (23)

Етап 5. Для зменшення кількості операцій, які витрачаються на кодування, пропонується обчислювати значення коду-номера ТСВ на поточному кроці обробки, використовуючи відоме значення БП коефіцієнта та значення коду-номера , що одержано на попередньому кроці обробки.

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

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

ШОСТИЙ РОЗДІЛ присвячено розробці методу відновлення зображень на основі тривимірного усіченого зв'язного біноміально-поліадичного декодування і порівнюються характеристики розроблених та існуючих методів стиску зображень. Проводиться порівняльна оцінка перешкодостійкості відеоданих, які стиснуті розробленим та відомими методами, до помилок в каналі зв'язку. Розробляється схемотехнічна реалізація запропонованих методів.

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

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

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

Методи стиску та відновлення зображень без внесення погрішностей на основі усунення двухознакової комбінаторної надмірності в двомірному і тривимірному просторах забезпечують збільшення стиску в середньому від 1,7 до 5 разів для сильно- і середньонасичених реалістичних зображень і в середньому в 3 рази - для слабонасичених зображень. Виграш за сумарним часом обробки і передачі відеоданих для швидкості передачі даних (біт/с) і середньої швидкості виконання машинних операцій (м.о./с) досягає в середньому для сильно-, середньо- і слабонасичених зображень відповідно від 1,8 до 3; від 1,75 до 3,5 і до 4 разів.



ВИСНОВКИ

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

Основні наукові результати:

І. Розроблено теоретичні основи біноміально-поліадичнного представлення відеоданих, які включають:

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

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

3. Швидке біноміально-поліадичне декодування, яке засновано на властивостях: симетричності, монотонності, одноперехідності і роздільності вагових БП коефіцієнтів. Дане декодування виключає необхідність в повному переборі за діапазоном значень відновлюваних відеоданих.

4. Усічене двузв'язне біноміально-поліадичне представлення відеоданих. Дане кодування ґрунтується на:

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

- системі виразів, які забезпечують усічене двузв'язне біноміально-поліадичне кодування та декодування.

ІІ. Розроблено метод тривимірного усіченого зв'язного біноміально-поліадичного кодування в плаваючому режимі без внесення погрішності. Даний метод дозволяє:

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

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

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

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

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

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

Основні практичні результати:

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

2. Для розробленого методу тривимірного біноміально-поліадичного кодування, для швидкості передачі даних (біт/с) і середньої швидкості виконання машинних операцій (м.о./с) часові витрати на обробку і передачу відеоданих знаходяться на рівні від 0,03 до 11 секунд залежно від класу і розміру зображень. Якнайменший виграш за сумарним часом на обробку та передачу стиснутих зображень по каналу зв'язку для розробленого методу щодо відомих методів для сильно-, середньо- і слабонасичених зображень рівний відповідно в середньому від 1,8 до 3; від 1,75 до 3,5 і до 4 разів.

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

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

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

3) скороченні сумарного часу обробки і передачі зображень без внесення погрішності по каналу зв'язку в середньому від 1,8 до 3; від 1,75 до 3,5 і до 4 разів відповідно для сильно-, середньо- і слабонасичених зображень.

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

Результати дисертаційної роботи доцільно використовувати:

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

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

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