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

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

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

Харківський національний університет радіоелектроніки

Автореферат

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

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

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

Карпенко Сергій Володимирович

Харків - 2009

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

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

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

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

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

кандидат технічних наук, доцент Корольова Наталія Анатоліївна, доцент кафедри Транспортний зв'язок Харківської державної академії залізничного транспорту, Міністерства транспорту та зв'язку України, м. Харків.

Вчений секретар спеціалізованої вченої ради Д 64.052.03 В.М. Безрук

Анотація

телекомунікаційний тривимірний зображення

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

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

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

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

Аннотация

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.02 - телекоммуникационные системы и сети - Харьковский национальный университет радиоэлектроники, Харьков, 2008.

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

Разработан метод сжатия видеоданных на основе трехмерного полиадического кодирования в двух режимах, а именно начиная со старшего и начиная с младшего элементов трехмерного полиадического числа. Компактное представление осуществляется за счет сокращения комбинаторной избыточности, обусловленной учетом закономерностей в динамических диапазонах элементов трехмерных структур данных одновременно по трем координатам.

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

Для снижения количества операций на обработку данных строятся конвейерные и параллельные схемы реализации трехмерного кодирования. Для этого используется свойство трехмерного полиадического кодирования, заключающееся в наличии возможности распараллеливания вычисления кода-номера для всего ТПЧ. Это следует из физических особенностей процесса трехмерной полиадической нумерации и выбора единой системы оснований. Параллельная реализация кодирования обеспечивает относительно последовательной реализации снижение времени обработки до 100 раз.

Для получения достоверной информации создается метод восстановления данных на основе трехмерного полиадического декодирования. Доказывается, что разработанное декодирование обеспечивает взаимно однозначное восстановление исходных данных. Разработаны методы восстановления трехмерных структур данных на основе рекуррентного, конвейерного и параллельного трехмерного полиадического декодирования. Построена методика оценки коэффициента сжатия видеоданных за счет трехмерного полиадического кодирования. Проведена оценка характеристик разработанного метода сжатия относительно коэффициента компрессии и среднего суммарного времени на обработку и передачу данных по ТС. Сравниваются характеристики разработанного и существующих методов компактного представления данных. Для разработанного метода обеспечивается: компактное представление видеоданных с коэффициентом сжатия, который изменяется в пределах от 2,8 до 4 раз в зависимости от степени насыщенности фрагментов изображений; величина выигрыша по степени сжатия относительно: методов, реализованных в формате JPEG в среднем на 35%; методов, которые в процессе обработки не вносят погрешность, в среднем в 2 раза. Время обработки и передачи данных по каналам связи для разработанного метода находится на уровне 3 сек. и на уровне 20 сек. соответственно для изображений с размерами и элементов.

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

Abstract

Karpenko S.V. Method of compact conception of images in the telecommunication systems on the basis of the three-dimensional polyadical encoding. - Manuscript.

Thesis on reception scientific degrees of the candidate of technical sciences on speciality 05.12.02 - telecommunication systems and networks Kharkov National University of Radio Electronics, Kharkov, 2008.

Dissertation work is devoted the increase of efficiency of functioning of the telecommunication systems. Above all things it is related to the decision of contradiction between the growings volumes of information which it is required in good time to process and pass with necessary authenticity and limited economic feasibilities of subsystems of treatment and communication of data. The method of compression of videoinformation is developed on the basis of the three-dimensional polyadical encoding in two modes, namely since a chief and since junior elements of three-dimensional polyadical number. Compact presentation is carried out due to reduction of combinatory surplus, conditioned the account of conformities to the law in the dynamic ranges of elements of three-dimensional structures of data simultaneously to on to three to the co-ordinates. For the decline of amount of operations on processing of data the conveyer and parallel charts of realization of three-dimensional code are built. For the receipt of reliable information the method of renewal of information is created on the basis of the three-dimensional.

Keywords: telecommunication system, compression of videoinformation, three-dimensional polyadical encoding, three-dimensional combinatory surplus, conveyer encoding.

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

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

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

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

Аналіз недоліків існуючих підходів до усунення надмірності виявив, що для підвищення ступеня компресії без внесення похибок необхідно розробляти нові методи компресії, які засновані на скороченні тривимірної надмірності за рахунок виявлення неоднорідностей в динамічних діапазонах тривимірних структур даних (ТСД) одночасно за трьома координатами.

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана в рамках: Концепції розвитку зв'язку України до 2010 року; Національної програми інформатизації України до 2010 року; Національної космічної програми України; Закону України “Про телекомунікації”; планів наукової та науково-технічної діяльності Харківського університету Повітряних Сил ім. І. Кожедуба та Національного авіаційного університету. Зокрема в рамках НДР “Розробка методів обробки інформації в інформаційно-телекомунікаційних системах” (шифр “ТОР-1”; №0101U000615; Інв. №15886), в якій здобувач був виконавцем.

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

1) обґрунтувати підхід для зниження тривимірної надмірності зображень;

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

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

4) розробити програмно-апаратні реалізації методів стиснення і відновлення зображень.

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

Предмет дослідження. Методи стиснення і відновлення відеоінформації в ТС на основі тривимірного поліадичного кодування (декодування).

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

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

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

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

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

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

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

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

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

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

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

2) досягти величини виграшу за коефіцієнтом компресії відносно: методів, реалізованих у форматі jpeg, від 30 до 40% залежно від ступеня насиченості зображень; методів, які в процесі обробки не вносять похибок, в середньому до 2 разів;

3) у разі обробки реалістичних зображень середніх розмірів (1600х1200 елементів) забезпечити виграш за часом обробки і передачі даних в ТС в середньому в 1,7 разів.

Результати дисертації використовувалися при виконанні експериментально-конструкторських робіт на ДНВП об'єднання Коммунар - НТ СКБ ПОЛіСВіТ (акт реалізації від 07.02.2008 р.). Отримані також висновки про впровадження результатів наукових досліджень, що представлені в звіті з науково-дослідної роботи НТ СКБ “Полісвіт” (акт реалізації від 08.12.2006 р.).

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

Апробація результатів дисертації. Результати практичних і теоретичних досліджень, які викладено в дисертаційній роботі, доповідались і були схвалені на науково-практичних школах семінарах, а також на 7 науково-технічних конференціях: VII, VIIІ міжнародних науково-технічних конференціях Проблемы информатики и моделирования (м. Харків 2007, 2008); Modern problems of Radio Engineering, Telecommunications and Computer Science. Proceedings of the International Conference TCSET'2008 (Lviv-Slavsko, Ukraine, February 20-24, 2008); Четвертій науковій конференції Харківського університету Повітряних Сил імені Івана Кожедуба (м. Харків, 2008); І міжнародній науково-практичній конференції Безпека та захист інформації в інформаційних і телекомунікаційних системах (м. Харків 2008); XVIII International Conference “New leading Technologies in Machine Building” (Rybachie, Ukraine, 2008); 21-ій міжнародній науково-практичній конференції Перспективные компьютерные, управляющие и телекоммуникационные системы для железнодорожного транспорта Украины” (м. Алушта, 2008).

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

Обсяг і структура роботи. Дисертація складається із вступу, чотирьох розділів, списку використаної літератури і 2 додатків. Загальний обсяг дисертації складається із 178 сторінок, з них 27 рисунків на 9 сторінках, 28 таблиць на 10 сторінках, перелік використаних скорочень на 1 сторінці, списку використаної літератури з 124 джерел на 11 сторінках і додатків на 4 сторінках.

2. Основний зміст роботи

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

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

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

. (1)

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

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

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

при . (2)

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

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

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

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

; , , ;

; ; ,

де , - динамічний діапазон відповідно для j-го стовпця та і-го рядка z-ої перетини ТСД; - динамічний діапазон для (j; i)-й вертикалі ТСД; - кількість перетинів (висота ТСД); , - кількість стовпців та кількість рядків ТСД.

В цьому випадку ТСД називаються тривимірними поліадичними числами (ТПЧ). Значення коду пропонується обчислювати за формулою:

,

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

.

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

У випадку якщо кількість елементів поліадичного числа вважається за невідому , а кількість розрядів на представлення коду ТПЧ є постійною, тобто , де - довжина машинного слова, то необхідно: здійснювати ТПК за рекурентною схемою; перед кожним додаванням до поточного значення коду-номера величини перевіряти умову на переповнювання машинного слова. Для виконання даних умов пропонується організувати кодування на основі наступних етапів (рис. 1).

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

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

Рис. 1. Схема тривимірного поліадичного кодування

Вертикальний напрямок обробки ТСД. На -м кроці обробки -й вертикалі перевіряється умова

, (3)

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

У разі виконання умови (3) код-номер розраховується на основі попереднього значення по формулі , де - значення коду-номера, отриманого для -го елементів -й вертикалі ТПЧ. Вертикальна обробка закінчується тоді, коли оброблені окремо всі вертикалі ТПЧ.

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

. (4)

Якщо значення величини не перевищує , то рекурентний вираз, який забезпечує формування коду-номера для елементів має вигляд , де - значення коду-номера для послідовності кодів-номерів . Інакше, коли нерівність (4) не виконується, то код-номер рівний , де - значення коду-номера, отримане для числа, яке складається з одного елементу .

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

,

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

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

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

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

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

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

Будь-яке ТПЧ можна відновити на основі коду-номера і векторів основ рядків, стовпців та вертикалей за формулою

. (5)

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

; (6)

; (7)

, (8)

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

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

Рис. 2. Схема рекурентного поелементного відновлення ТПЧ

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

Недоліки поелементного відновлення полягають в тому, що: для переходу до отримання чергового елементу потрібно виконати повну схему обчислень, яка витрачається на відновлення поточного елементу; необхідно виконувати два проходи по елементах ТСД.

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

; . (9)

Згідно виразам (9) формула (5) набере вигляду

; . (10)

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

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

. (11)

В цьому випадку вираз (5) прийме вигляд

; . (12)

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

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

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

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

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

.

Для відновлення другого рівня проводиться декодування коду .

.

Формування третього рівня, що містить елементи , здійснюється на основі співвідношення

.

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

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

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

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

,

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

Оцінка величини представлена на рис. 3.

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

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

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

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

- величина виграшу за ступенем стиску відносно: методів, реалізованих у форматі JPEG складає в середньому 35%; методів, які в процесі обробки не вносять похибок, в середньому дорівнює 2 разам.

На основі порівняння оцінок середнього часу на обробку та передачу даних по ТС для різних методів компресії отримано, що побудований метод рекурентного ТПК в напрямку починаючи з молодших елементів ТПЧ забезпечує без внесення похибки щодо існуючих методів такі результати: у разі обробки реалістичних зображень середніх розмірів величина виграшу за часом доведення даних в середньому рівна 1,7 разів. Час обробки і передачі даних по каналах зв'язку для розробленого методу знаходиться на рівні 3 сек. і на рівні 20 сек. відповідно для зображень з розмірами та елементів. Побудовані нові рішення схемотехнічних реалізацій для компресії зображень на основі ТПК.

Висновки

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

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

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

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

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

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

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

Результати дисертації використовуються: при обробці та передачі відеоданих в телекомунікаційних системах; при проведенні конструкторських і науково-дослідних робіт із створення нових технічних засобів і програмних виробів по обробці зображень, зокрема результати дисертації використовувалися при виконанні експериментально-конструкторських робіт на ДНВП об'єднання Коммунар - НТ СКБ ПОЛіСВіТ (акт реалізації від 07.02.2008 р.); при вивченні навчальних дисциплін по кодуванню та обробки даних в телекомунікаційних системах для підготовки фахівців у вищих навчальних закладах.

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

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

2. Для побудованого методу середній сумарний час обробки та передачі даних по каналах зв'язку (швидкість передачі 4,096 Мбіт/с) знаходиться на рівні 3 сек. и на рівні 20 сек. відповідно для зображень з розмірами і елементів. Забезпечуваний виграш за часом обробки і передачі даних в ТС в середньому складає 1,7 рази.

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

1. Карпенко С.В. Аналіз можливостей автоматизації робочого місця державного експерта з питань таємниці / С.В. Карпенко // Защита информации: сборник научных трудов. Вып. 12. - К.: НАУ. - 2005. С. 220-226.

2. Карпенко С.В. Використання методів дельфійського списку та ранжування загроз для автоматизації роботи експерта / С.В. Карпенко, А.О. Корченко // Моделювання та інформаційні технології: збірник наукових праць. - Вип. 34. К.: Інститут проблем моделювання в енергетиці НАН України ім. Г.Є.Пухова. - 2005. - С. 127-131.

3. Баранник В.В. Параллельная реализация трехмерного полиадического кодирования видеоданных / В.В. Баранник, С.В. Карпенко // Открытые информационные и компьютерные интегрированные технологии. - Харьков: НАКУ «ХАИ». - 2007. - Вып. 36. - С. 151-158.

4. Карпенко С.В. Создание подхода для исключения трехмерной избыточности изображений / С.В. Карпенко // Збірник наукових праць. - Х.: ХУ ПС. - 2007. - Вип. 3(15). - С. 90-93.

5. Баранник В.В. Сжатие данных на основе сокращения трехмерной структурной избыточности / В.В. Баранник, С.В. Карпенко // Открытые информационные и компьютерные интегрированные технологии. - Харьков: НАКУ «ХАИ». - 2007. - Вып. 38. - С. 177-187.

6. Баранник В.В. Трехмерное полиадическое декодирование / В.В. Баранник, С.В. Карпенко // Радиоэлектроника и информатика. - №3. - 2007. - С. 68-73.

7. Баранник В.В. Конвейерная реализация трехмерного полиадического декодирования / В.В. Баранник, С.В. Карпенко, А.К. Юдин // Збірник наукових праць ІПМЄ НАНУ. - К.: ІПМЄ НАНУ. - 2008. - Вип.46. - С. 27-33.

8. Баранник В.В. Трехуровневое трехмерное полиадическое декодирование / В.В. Баранник, С.В. Карпенко, А.К. Юдин // Збірник наукових праць ІПМЄ НАНУ. - К.: ІПМЄ НАНУ. - 2008. - Вип. 45. - С. 45-52.

9. Баранник В.В. Рекуррентное трехмерное полиадическое декодирование в направлении, начиная с младших элементов / В.В. Баранник, С.В. Карпенко // Авіаційна космічна техніка та технологія. - 2008. - № 1 - С. 75-78.

10. Баранник В.В. Трехмерное кодирование в информационно-телекоммуникационных системах / В.В. Баранник, С.В. Карпенко // Матер VII міжнародної науково-технічної конференції Проблемы информатики и моделирования. - Харків: НТУ ХПІ. - 2007. - С. 34.

11. Barannik V.V. Method of the 3-D Image Processing / V.V. Barannik, S.V. Karpenko // Modern problems of Radio Engineering, Telecommunications and Computer Science. Proceedings of the International Conference TCSET'2008, Lviv-Slavsko, Ukraine, February 20 - 24, 2008. - P. 115-117.

12. Баранник В.В. Кодирование трехмерных структур данных / В.В. Баранник, С.В. Карпенко, А.А. Красноруцкий // Четверта наукова конференція Харківського університету Повітряних Сил імені Івана Кожедуба, Харків, 2008. - С. 20.

13. Баранник В.В. Информационная технология трехуровневого декодирования / В.В. Баранник, С.В. Карпенко // І міжнародна науково-практична конференція Безпека та захист інформації в інформаційних і телекомунікаційних системах. - Харків: ХНЕУ. - 2008. - С. 60.

14. Карпенко С.В. Трехмерное конвейерное полиадическое декодирование данных в телекоммуникационных системах // XVIII International Conference “New leading Technologies in Machine Building”. - Rybachie, Ukraine, September 3-8 2008. - С. 71.

15. Баранник В.В. Метод параллельного трехмерного кодирования данных в информационных системах / В.В. Баранник, С.В. Карпенко // 21-я международная научно-практическая конференция Перспективные компьютерные, управляющие и телекоммуникационные системы для железнодорожного транспорта Украины”, Алушта, 2008 г. - С. 27.

16. Баранник В.В. Конвейерный способ трехмерного декодирования / В.В. Баранник, С.В. Карпенко // Матер VIIІ міжнародної науково-технічної конференції Проблемы информатики и моделирования. - Харків: НТУ ХПІ. - 2008. - С. 61.

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

...