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

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

Корольов Анатолій Вікторович

УДК 621.327: 681.5

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

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

АВТОРЕФЕРАТ

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

Харків – 2003

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

Робота виконана в Харківському військовому університеті

Офіційні опоненти: – | доктор технічних наук, професор
Жихарев Володимир Якович,
професор кафедри "Виробництво радіоелектронних систем літальних апаратів" Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ” Міністерства освіти і науки України, м. Харків;

– | доктор технічних наук, професор
Лосєв Юрій Іванович,
професор кафедри Харківського військового університету Міністерства оборони України, м. Харків;

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

Провідна установа: | Одеська Національна Академія зв’язку

ім. О.С. Попова, кафедра Фізики оптичного зв’язку Державного комітету зв’язку та інформатизації України, м. Одеса.

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

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

З дисертацією можна ознайомитись в бібліотеці академії.

Відгук на автореферат просимо надсилати за адресою:
Україна, 61050, м. Харків, майдан Фейєрбаха, 7.

Автореферат розісланий 25.10.2003 р.

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

спеціалізованої вченої ради

к.т.н., доцент М.В. Книгавко

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

Актуальність теми. У відповідності з Національними програмами інформатизації України, Концепцією розвитку Єдиної Національної системи зв’язку України на 2000 – 2010 рр. та Національними космічними програмами України (1997 – 2002, 2003 – 2010 рр.) основними задачами розвитку телекомунікаційних систем є: розширення кола задач, розв'язуваних у реальному часі; зниження собівартості і підвищення якості доведеної до одержувача інформації. Успішне рішення поставлених задач пов'язано з необхідністю доведення інформаційних потоків обсягом порядку 103 Гбіт/с. У цей час технічні можливості підсистем обробки і передачі інформації є обмеженими. Це призводить до передачі у реальному часі не більш, ніж 0,4 % від усієї необхідної інформації. Використання підсистеми стиску відеоданих (ПСВ) дозволяє зменшити обсяги даних і підвищити пропускну здатність каналів зв'язку.

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

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

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

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

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

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

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

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

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

2. Розробити теоретичні основи статистичної оцінки кількості надмірності різних видів.

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

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

5. Необхідно розробити і дослідити метод відновлення зображень з контрольованою втратою якості.

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

7. Оцінити часові витрати на обробку і передачу відеоінформації, стиснутої на основі розроблених методів.

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

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

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

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

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

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

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

1.2. Метод компактного представлення масивів колірних координат на основі комбінованого поліадичного кодування трансформант дискретного косинусного перетворення (ДКП) і врахуванням обмеженого числа серій у низькочастотних складових (версія 2). Стиск зображення забезпечується усуненням структурної надмірності масивів колірних координат зниженням їхніх значень на мінімальне; психовізуальної надмірності по засобах контрольованого квантування високочастотних компонент ДКП; надмірності в низькочастотних компонентах, обумовленої обмеженим числом двійкових серій; структурної надмірності в змінній кількості стовпців трансформант ДКП.

1.3. Метод відновлення зображень на основі:

1) декодування кодових комбінацій за версією 1, що включає:

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

декодування комбінованих поліадичних кодів;

декодування кодів за числом двійкових серій;

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

2) декодування кодових комбінацій за версією 2, що складається з:

декодування комбінованих кодів трансформант ДКП;

декодування кодів за числом двійкових серій у низькочастотних складових ДКП;

деквантування високочастотних компонент ДКП;

виконання зворотного двовимірного ДКП.

2. На основі вперше розробленої теорії статистичної оцінки версифікаційної надмірності одержала подальший розвиток статистична теорія зв'язку. Розроблена теорія ґрунтується на:

- статистичній інтерпретації різних за фізичною природою видів надмірності;

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

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

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

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

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

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

збільшення стиску у середньому у 2 рази для сильнонасичених зображень, у 3,2 рази для середньонасичених зображень і в 2,5 рази для слабонасичених зображень;

відновлення зображень з високою якістю (ВСШ не менш 40 дБ).

2. Алгоритми швидкого формування та декодування кодів за числом серій, доведені до програмно-апаратної реалізації, в сукупності з отриманим виграшем у ступені стиску дозволили щодо відомих методів отримати зниження сумарного часу обробки і передачі інформації для швидкості передачі по каналу зв'язку (біт/с) і швидкості обробки (оп/с), а також для (біт/с) і (оп/с) на 55, 68 і 60 % відповідно для сильно-, середньо- і слабонасичених зображень, а для швидкості передачі по каналу зв'язку (біт/с) і швидкості виконання машинних операцій, рівної (оп/с) на 40 % для сильнонасичених та на 55 % для середньо- і слабонасичених зображень.

Результати дисертації використовувалися при виконанні експериментально-конструкторських робіт в центрі прийому наукової інформації НКАУ (акт реалізації від 05.09.2002 р.), в центрі управління польотами космічних апаратів (акт реалізації від 04.10.2002 р.), у військовій частині А 0117 (акт реалізації від 02.12.2002 р.), на НТ СКБ ПОЛІСВІТ (акт реалізації від 12.05.2003 р.), в ДП ПКТБ Укртрансзв’язок (акт реалізації від 20.05.2003 р.), на ЦКБ ЛОМО (акт реалізації від 21.05.2003 р.), в ФГУП НПО ім С.А. Лавочкіна (акт реалізації від 05.06.2003 р.), а також в навчальному процесі ХВУ (акт реалізації від 10.04.2003 р.).

Особистий внесок автора дисертаційної роботи в публікації, виконані в співавторстві, полягає в наступному: у статті [1] – розроблено і досліджено метод виключення надмірності у відеоінформаційній моделі польотної обстановки; у статті [2] – запропоновано спосіб компактного представлення бінарної інформації; у статті [3] – отримано метод рядково-вагового кодування графічної інформації; у статті [5] – розроблено метод компактного представлення кольорових зображень на основі виділення областей однакового кольору; у статті [6] – запропоновано метод стиску символьних даних; у статтях [8 – 10, 12, 14, 22, 53 – 56] – запропоновано метод виключення надмірності, що обумовлена структурною однорідністю фрагментів у окремому та послідовності кадрів кольорових зображень; у статті [11] – отримано модель оцінки ефективності перешкодостійкості стиснутих даних до помилок у каналі зв’язку; у статті [13] – отримано оцінку часових витрат на формування довжин серій; у статті [15] – розроблено метод стиску матриць ознак компонентів ДКП; у статті [16] – розроблено метод зонально-граничного відновлення компонент ДКП; у статтях [17, 25, 30] – розроблено метод компактного представлення окремих та послідовності кадрів на підставі зонально-граничного відбору коефіцієнтів трансформант ДКП; у статті [18] – розроблено гібридний спосіб стиску зображень на основі кодування довжин серій; у статті [19] – розроблено метод кодування зображень довжинами серій з підвищеною стійкістю до помилок у каналі зв'язку; у статті [20] – розроблено метод усунення надмірності зображень на основі обліку особливостей за ознаками: довжиною серії та амплітудами спектральних компонентів трансформант ДКП; у статті [21] – запропоновано спосіб адаптивної кластеризації кодової книги; у статті [27] – отримано вираз для оцінки середнього квадратичного відхилення у службовій частині кодової комбінації, що обумовлено помилками у каналі зв’язку; у статтях [23, 24, 28, 32] – розроблено метод стиску зображень на підставі скорочення надмірності, яка викликана обмеженим динамічним діапазоном компонент трансформант ДКП; у статті [26] – розроблено спосіб відновлення зображень за комбінованими кодами стовпців трансформант ДКП; у статті [29] – отримано метод відновлення компонент трансформант ДКП із врахуванням їх обмеженого динамічного діапазону; у статті [31] – запропоновано метод стиску зображень на основі хвильових перетворень масивів з непарними розмірами; [35] – запропоновано метод зниження надмірності масивів довжин серій та кольорових координат, що викликано обмеженістю діапазонів відповідно у довжинах серій та у значеннях кольорових координат; у статті [33] – отримано вираз для закону розподілу сплесків значень кольорових координат; у статті [34] – розроблено спосіб упаковки ознак стовпців масивів кольорових координат; у статті [36] – проведена оцінка кількості інформації на елемент зображення із врахуванням обмеженого числа серій; у статті [37] – запропонована конвеєрна організація відновлення зображень; у статті [38] – отримано оцінку кількості операцій на відновлення масивів кольорових координат та довжин серій; у статті [39] – проведено оцінку ступеня стиску масивів кольорових координат; у винаходах [57 – 60] – запропоновані ідеї та розроблені пристрої для формування, стиску, накопичення, перетворення і відображення графічної інформації; у винаходах [61, 62, 71] – запропоновані ідеї та розроблені пристрої для формування кольорових сигналів графічного зображення; у винаході [63] – запропоновано ідею і розроблено пристрій для порівняння кодів у процесі формування довжин серій; у винаходах [64 – 66, 68] – запропоновані ідеї і розроблені пристрої для стиску цифрових сигналів ТВ-зображень; у винаході [67] – запропоновано ідею і розроблено пристрій для адаптивного стиску кольорових сигналів ТВ-зображень; у винаході [69] – запропоновано ідею і розроблено пристрій для відображення інформації на екрані ТВ-приймача; у винаході [70] – запропоновано ідею і розроблено телевізійну систему з компресією цифрових сигналів кольорових зображень; у винаході [72] – запропоновано ідею і розроблено пристрій для формування помітних сегментів зображень.

Апробація результатів дисертації. Результати практичних і теоретичних досліджень, викладені в дисертаційній роботі, доповідалися та обговорювалися на 16 міжнародних, 11 всесоюзних, 5 республіканських, 12 Міністерства Оборони СРСР і України науково-технічних нарадах і конференціях, симпозіумах і семінарах, а також на семінарах “Синтез, обработка и отображение информационных моделей” Наукової ради НАНУ з проблеми “Теоретическая электротехника и электронное моделирование” (1980, 1985 – 2003 рр.), в цьому числі на:

II і IV Всесоюзних НТК “Диалог” человек – ЭВМ (Ленінград, 1982; Київ, 1985); 8 – 10 Всесоюзних симпозіумах АН СРСР з проблеми надмірності в інформаційних системах (Ленінград, 1983, 1986, 1989); Всесоюзній НТК “Методы и средства обработки сложной графической информации” (м. Горький, 1988); Всесоюзній НТК “Живучесть и реконфигурация информационно-вычислительных и управляющих систем” (Москва, 1989); Всесоюзній школі-семінарі “Передача, обработка и отображение информации” (Теберда, 1990, 1991, 1992); Республіканських НТК “Автоматизация, проектирование и управление производством” (Харків, 1982 – 1984); Республіканських НТК “Функционально-ориентированные вычислительные системы” (Харків, 1986, 1990); Міжгалузевій науковій конференції “Устройства отображения знакографической информации на газоразрядных индикаторах” (Москва, 1987); Міжнародній НТК “Функционально-ориентированные вычислительные системы (ФОВС – 93)” (Алушта, 1993); Міжнародних НТК “Представление, обработка и передача информации” (Сочи, 1992, 1993); Міжнародній НТК “Проблемы передачи и обработки данных” (Рибаче, 1994); III-й міжнародній конференції “Новые технологии в машиностроении” (Рибаче, 1994); Міжнародній НТК “Передача, обработка и отображение информации” (Домбай, 1994); 8 – 15 міжнародних школах-семінарах Перспективні системи управління на залізничному, промисловому та міському транспорті (Алушта, 1995 – 2002 рр.); Міжнародній НТК “Обработка информации и повышение надежности систем управления” (Харків, 1996); науково-технічних семінарах “Синтез, обработка и отображение информационных моделей” Наукової ради НАНУ з проблеми “Теоретическая электротехника и электронное моделиро-вание” (1980, 1985 – 2003 рр.); Міжнародній НТК “Проблемы информатики и моделирования” (Харків, 2001, 2002); Міжнародній НТК “Проблемы совершенствования систем управления и связи” (Харків, 1997); Науково-технічних конференціях МО СРСР і МОУ (Київ, 1982, 1983, 2002; Харків, 1981, 1984, 1986, 1996, 1999; в/ч 32103, 1979, 1981; в/ч 25840, 1974; в/ч 13991, 1979; в/ч 07378, 1978)

Публікації. За темою дисертації автором самостійно та у співавторстві опубліковано 212 наукових праць, що включають 98 наукових статей, 49 винаходів СРСР, 46 тез доповідей, 16 звітів з НДР, 3 навчальних посібники. При цьому основні положення докторської дисертації опубліковані в 56 статтях, з яких 41 написана разом з іншими авторами, 16 винаходах, а також у 44 матеріалах і тезах доповідей на конференціях. Усі статті опубліковані в журналах і збірниках наукових праць, що входять до переліку видань, дозволених ВАК України для публікацій матеріалів дисертації з технічних наук.

Обсяг і структура роботи. Дисертація складається із вступу, семи розділів, списку використаної літератури і додатків. Загальний обсяг дисертації складається із 368 сторінок, з них 62 ілюстрації на 27 сторінках, 26 таблиць на 13 сторінках, перелік використовуваних скорочень на 1 сторінці, списку використаної літератури з 275 джерел на 25 сторінках і додатків на 48 сторінках.

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

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

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

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

(1)

де – відповідно задані для конкретної ТС швидкість виконання машинних операцій, швидкість передачі даних і обсяг зовнішнього запам'ятовуючого пристрою (ЗЗУ); –задане значення відношення сигнал/шум.

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

, (2)

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

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

. (3)

Тому критерієм ефективності процесу стиску і передачі відеоданих служить значення часу при виконанні обмежень (1).

Аналіз відомих методів стиску і можливих напрямків їхнього розвитку виявив основну проблемну сторону забезпечення доведення необхідних обсягів ІП у реальному часі: відсутність узагальненого аналізу, формалізованого апарата і вимог до вибору видів надмірності, що послідовно усуваються. Це призводить до того, що вони із врахуванням існуючих швидкостей виконання машинних операцій і швидкостей передачі даних по каналу зв'язку забезпечують передачу у реальному часі обсягів ІП порядку – біт/с. Це менше необхідних інформаційних потоків від 10 до 104 разів.

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

У ДРУГОМУ РОЗДІЛІ розробляються теоретичні положення виключення версифікаційної надмірності зображень. Проводиться вибір основних версій ознак. Доводиться необхідність використання додаткової інформативної ознаки.

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

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

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

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

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

Другий етап узагальнення – загальні теоретичні положення усунення надмірності за сукупністю кількісних і якісних ознак різної фізичної природи. Основним моментом теоретичних положень другого етапу є теорема про необхідні та достатні умови інформативності послідовності ознак: якщо для фрагмента зображення виконується нерівність (необхідна умова):

і , (4)

і для ознаки існує невзаємоусуваєма або частково взаємоусуваєма ознака (достатня умова), то для матриці інформативності та ознаки виконується нерівність

, (5)

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

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

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

, (6)

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

– величина, обернено пропорційна кількості надмірності в матриці інформативності за ознакою .

На основі узагальнених досліджень різних сукупностей ознак обґрунтовано, що вимогам версифікаційної надмірності в більшому ступені відповідають наступні версії ознак:–

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

для стиску з контрольованою втратою якості – “амплітуди спектральних складових (просторово-спектральні характеристики)”, “кількість півтонів (психовізуальні характеристики)”, “максимальні значення динамічного діапазону”.

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

На основі теореми про непересікаємість класів доводиться, що додатковою інформативною ознакою є “число серій однакових двійкових елементів”. Теорема формулюється так: якщо n і – цілі позитивні числа, то для парних n виконується рівність

, (7)

де і – відповідно множина можливих двійкових послідовностей довжиною n елементів і підмножина послідовностей з множини , що мають число серій, яке дорівнює .

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

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

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

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

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

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

(8)

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

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

Розрахунки, проведені на основі отриманих виразів, показали, що за рахунок кодування за числом серій довжин одноколірних областей значення нижньої границі витрат кількості розрядів на один елемент знизились в середньому додатково у 2 рази; за рахунок поліадичного кодування масивів кодів за числом серій нижня границя витрат розрядів на один елемент зображення додатково щодо нижньої границі до поліадичного кодування знижується в середньому у 3 рази; сумарне скорочення версифікаційної надмірності за ознаками версії 1 (без врахування витрат розрядів на представлення колірних координат) знаходиться в інтервалі від 90 до 99 % у залежності від імовірності колірного перепаду.

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

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

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

(9)

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

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

, (10)

де – середнє квадратичне відхилення величини .

На основі проведеної статистичної оцінки версифікаційної надмірності (вирази (9), (10)) за версією 2 доведено, що забезпечується зменшення надмірності зображень від 84.3 до 99.7 % у залежності від імовірності колірного перепаду, а кількість інформації відповідно приймає значення в інтервалі від 0.024 до 3.5 розрядів на елемент зображення.

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

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

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

Схема процесу компактного представлення зображення складається з наступних етапів:

1. З вихідного фрагмента на основі оператора утворюється масив довжин серій і масив С колірних координат .

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

, (11)

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

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

(12)

де , і – параметри рекурентної системи.

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

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

.

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

; , (13)

де – відповідно кількість рядків і стовпців у масиві L.

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

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

, (14)

де – накопичений добуток максимальних значень для mдс – i – 1 рядка.

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

, (15)

де – ваговий коефіцієнт -го елементу масиву .

Часові витрати на стиск зображення за версією 1 із врахуванням рекурентного обчислення значень кодів за числом серій знаходяться за формулою

, (16)

де – розмір зображень відповідно по горизонталі та вертикалі.

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

Оцінка ступеня компактного представлення розробленого методу за версією 1 показала, що ступінь стиску масивів довжин одноколірних областей змінюється від 10 до 300 разів у залежності від імовірності колірного перепаду. Однак, ступінь стиску зображень із врахуванням витрат розрядів на представлення колірних координат знижується в середньому в 20 разів.

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

У П’ЯТОМУ РОЗДІЛІ розробляється метод компактного представлення зображень з контрольованою втратою якості за рахунок усунення версифікаційної надмірності за версіями 2.1 і 2.2. Проводиться оцінка ступеня стиску зображень розробленим методом.

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

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

Розглянемо вибір типу кодування для масивів довжин серій L. З погляду правильного сприйняття зображення найбільш значимою є інформація про структуру і форми об'єктів. Отже, для стиску масивів довжин серій необхідно використовувати кодування, що не вносить погрішності. Тому пропонується в масивах довжин одноколірних областей виключати версифікаційну надмірність на основі ознак версії 2.1. Даний вид версифікаційної надмірності скорочується в результаті комбінованого поліадичного кодування числа двійкових серій довжин одноколірних областей (вирази (11) – (15)).

Розглянемо вибір типу кодування для масивів колірних координат С. Для цього розглянемо особливості масивів колірних координат:

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

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

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

, (17)

де – ваговий параметр -го рядка трансформанти; – число рядків у масиві С.

З аналізу виразу (17) випливає, що для додаткового підвищення ступеня стиску масивів С необхідно розробити способи зниження значень компонент ДКП. Пропонується знижувати діапазон значень компонент такими способами:

1. Зменшенням діапазону колірних координат на мінімальне значення в масиві С.

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

2. Зменшення значень компонент ДКП за рахунок їхнього переквантування на основі матриці квантизації Q. У цьому випадку додатково усувається психовізуальна надмірність. Тому він найбільш ефективний для напівтонових зображень.

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

1. Знижувати значення кодів на основі переформатування трансформанти ДКП, що полягає в повороті її на 180о і переіндексації компонентів шляхом обходу трансформанти по Z-розгорненню.

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

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

, (18)

де – двійкове представлення квантованої (згладженої) компоненти ДКП ; – ваговий параметр -го розряду компонента ДКП.

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

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

, (19)

де – цифровий обсяг вихідного зображення;

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

; (20)–

кількість масивів у всьому кадрі; – кількість стовпців масиву , для яких формується один код;

, (21)

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

Розрахунки, проведені за формулами (19) – (21), показали, що значення коефіцієнта