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

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

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

УДК 629.391: 681.5

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

телекомунікаційних системах на підставі

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

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

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

Харків – 2006

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

Робота виконана в Харківському університеті Повітряних Сил ім. І. Кожедуба, Міністерства оборони України.

Науковий консультант

доктор технічних наук, професор Стасєв Юрій Володимирович заступник начальника Харківського університету Повітряних Сил ім. І. Кожедуба з навчальної та наукової роботи, Міністерства оборони України, м. Харків.

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

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

доктор технічних наук, професор Федорович Олег Євгенович, завідувач кафедри Інформаційні керуючі системи Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ”, Міністерства освіти і науки України, м. Харків;

доктор технічних наук, професор Хаханов Володимир Іванович, декан факультету комп‘ютерної інженерії і управління Харківського національного університету радіоелектроніки, Міністерства освіти і науки України, м. Харків.

Провідна установа

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

Захист відбудеться “19” 10 2006 р. о “ 1400” годині на засіданні спеціалізованої вченої ради Д .820.01 при Українській державній академії залізничного транспорту за адресою:

Україна, 61050, м. Харків, майдан Фейєрбаха, 7.

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

Україна, 61050, м. Харків, майдан Фейєрбаха, 7.

Автореферат розісланий “21” 08 2006 р.

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

спеціалізованої вченої ради М.В. Книгавко

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана в рамках Національної програми інформатизації України, Концепції розвитку Єдиної Національної системи зв’язку України на 2000 – 2010 рр., Національних космічних програм України (1997 – 2002, 2003 – 2007 рр.) та планами НДР МОУ, ХВУ, ХУПС. Основні результати дисертаційної роботи використовувалися у 14 звітах з НДР, у тому числі: Розробка методів і засобів обміну даними і виключення надмірності інформації (№ 3643); Розробка методів і засобів компактного представлення і розподілу відеоінформації (№ 3759); Інформаційно-телекомунікаційна мережа системи військової освіти МОУ (№ 26/1/241); Розробка методів та засобів стиску відеоданих (№ 3816); Розробка методів та засобів оптимізації структур систем телекомунікації відеоданих (№ 3822); Розробка методів та засобів автоматизації моніторингу Землі (№ 3824; № 3871; № 3899), Методи обробки інформації (№ 3865), Розподілення потоків в системах телекомунікацій (шифр Нива, № 3867), Розробка методів та засобів автоматизації доступу до даних дистанційного зондування Землі (№ 3885), Методи та способи скорочення часу обробки (№ 3893), Обробка інформації в розподілених системах (№ 3896), в 5 з яких автор був відповідальним виконавцем.

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

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 разів.

Результати дисертації використовувалися при виконанні експериментально-конструкторських робіт в ДП ПКТБ Укртрансзв'язок (акт реалізації від 20.04.2003 р.), на НТ СКБ ПОЛіСВіТ (акт реалізації від 04.11.2003 р.), в центрі прийому наукової інформації НКАУ (акт реалізації від 29.01.2004 р.), в центрі управління польотами космічних апаратів (акт реалізації від 17.02.2004 р.), на ФГУП НПО їм С.А. Лавочкіна (акт реалізації від 02.04.2004 р.), в ИРЕ НАНУ (акт реалізації від 7.04.2004 р.), а також в навчальному процесі ХУПС (акт реалізації від 7.10.2005 р.). Отримані також висновки про впровадження результатів наукових досліджень, що представлені в звітах з науково-дослідної роботи наступних організацій: НТ СКБ “Полісвіт”: вх. №373 від 18.12.02; вх. №65 від 25.02.03; вх. № 478 від 25.11.03; вх. № 479 від 25.11.03; ХНАУ: вх. № 28 від 28.01.03; вх. № 93 від 25.02.04; вх. № 181 від 27.04.04.

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

Апробація результатів дисертації. Результати практичних і теоретичних досліджень, які викладено в дисертаційній роботі, доповідались та обговорювались на 12 міжнародних, 10 конференціях Міністерства оборони України, науково – технічних конференціях і семінарах, а також на семінарах “Синтез, обробка і відображення інформаційних моделей” наукової ради НАНУ за проблемами “Теоретична електротехніка і електронне моделювання” (2001 – 2004 р.р.), яка включає:

14 – 16 міжнародні школи - семінари Перспективні системи управління на залізничному, промисловому та міському транспорті (г. Алушта, 2001 - 2003); науково – технічні семинари “Синтез, обробка і відображення інформаційних моделей” Наукової Ради НАНУ по проблеме “Теоретична електротехніка і електронне моделювання” (2001 – 2004 р.р.); І – ІІІ Міжнародних НТК “Проблемы информатики и моделирования” (Харьков, 2001 – 2003 р.р.); ХІ - ХІІ міжнародних НТК Інформаційні технології: наука, техніка, технологія, освіта, здоровя (Харків: НТУ ХПІ, 2003, 2004), міжнародна науково - практична конференція Современные технологии в менеджменте (Харків, Алушта, 2003), міжнародна науково-практична конференція Соціально-економічні та екологічні проблеми використання і охорони земель в умовах реформування земельних відносин (Харків: ХНАУ, 2003), І науково-технічної конференції “Проблеми розробки і удосконалення засобів телекомунікації систем управління в ЗСУ” (К.: МОУ, ВІТІ НТУУ “КПІ”, 2003), науково-технічна конференція Наукові проблеми розробки, модернізації та застосування інформаційних систем космічного і наземного базування (Житомир, 2004), науково-технічна конференція Актуальні проблеми створення і застосування авіаційних та космічних систем (К.: НАОУ, 2003), ІІ наукова конференція молодих вчених ХВУ (Харків, 2003), підсумкова наукова конференція (Харків: ХНАУ, 2003).

Публікації. За темою дисертації автором самостійно та у співавторстві опубліковано 85 наукових праць, які включають 55 наукових статей, 16 тез доповідей, 14 звітів про НДР. При цьому основні положення докторської дисертації опубліковано в 41 статті, з яких 23 написано автором самостійно, а також у 10 матеріалах і тезах доповідей на конференціях. Усі статті опубліковані в журналах і збірниках наукових праць, що входять до переліку видань, дозволених ВАК України для публікацій матеріалів дисертації з технічних наук.

Обсяг і структура роботи. Дисертація складається із вступу, шести розділів, списку використаної літератури і 9 додатків. Загальний обсяг дисертації складається із 411 сторінок, з них 42 ілюстрації на 27 сторінках, 21 таблиця на 10 сторінках, перелік використаних скорочень на 1 сторінці, списку використаної літератури з 262 джерел на 21 сторінці і додатків на 76 сторінках.

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

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

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

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

; (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. Знаходження позиції поточного БП числа, на яку необхідно розташувати черговий елемент ТСВ. При цьому вимагається забезпечити зменшення кількості операцій і значення