Декорелюючі методи стиснення та виділення ознак сигналів

31

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

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

АВТОРЕФЕРАТ дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Декорелюючі методи стиснення та виділення ознак сигналів

Спеціальність 01.04.03 - радіофізика

МУСАТЕНКО ЮРІЙ СЕРГІЙОВИЧ

УДК 621.391

Харків - 2001

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

Робота виконана в Київському національному університеті імені Тараса Шевченка.

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

Офіційні опоненти: доктор фізико-математичних наук, професор Омельченко Віктор Олександрович, Харківський державний технічний університет радіоелектроніки, професор кафедри мереж зв'язку;

кандидат фізико-математичних наук, Корнієнко Юрій В'ячеславович, Інститут радіофізики та електроніки імені Усикова НАН України, зав. відділом обробки зображень.

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

Захист відбудеться “21” лютого 2001 р. о 13¹⁵ годині на засіданні спеціалізованої вченої ради Д 64.052.03 при Харківському державному технічному університеті радіоелектроніки за адресою: 61166, м. Харкiв, пр. Леніна, 14, ауд. 4.

З дисертацією можна ознайомитись у бібліотеці Харківського державного технічного університету радіоелектроніки за адресою 61166, м. Харкiв, пр. Леніна, 14.

Анотації

Мусатенко Ю.С. Декорелюючі методи стиснення та виділення ознак сигналів. - Рукопис.

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

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

Ключові слова: зниження розмірності, перетворення Карунена-Лоева, хвилькове перетворення, розпізнавання образів, стиснення зображень.

Мусатенко Ю.С. Декоррелирующие методы сжатия и выделения признаков сигналов. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.04.03 - радиофизика. - Харьковский технический университет радиоэлектроники, Харьков, 2000.

Диссертация посвящена проблеме снижения размерности случайных полей для их дальнейшей обработки, что имеет важное значение в задачах распознавания образов, в частности в задаче распознавания излучения РЛС. Также исследуется проблема сжатия коррелированных изображений. В работе предложен быстрый метод построения приближенного базиса КЛ на основе оценки корреляционной матрицы произведением двух матриц. Продемонстрировано лучшее качество базиса по сравнению с приближенным вейвлет базисом КЛ для многих типов полей, в частности для некоторых типов радиолокационных сигналов записаных в растр. Проведено исследование качества двумерных базисов полученых как произведение одномерных с точки зрения их близости к точному базису КЛ. Базисы з такой структурой имеют вейвлет и предложеный методы построения базиса. Установлено, что для широкого класса изображений качество таких двумерных базисов принципиально не может достигать качества точного базиса КЛ. В работе предложен метод сжатия коррелированных сигналов на основе преобразования КЛ, которое, как известно, есть оптимальным для этой цели. Метод успешно использовано для сжатия изображений земной поверхности в разных длинах волн.

Ключевые слова: снижение размерности, преобразование Карунена-Лоева, вейвлет преобразование, разпознавание образов, сжатие изображений.

Musatenko Yu.S. Decorrelative methods for signal compression and sign selection. - Manuscript.

Thesis for a candidate degree in speciality 01.04.03 - radiophysics. - Kharkiv technical university of radioelectronics, Kharkiv, 2000.

The thesis is dedicated to problem of random field dimension reduction for it further processing. This task is important for pattern recognition, in particular, for recognition of radar emission. It is known that classical pattern recognition methods have limitations in processing signals with large number of samples. Most of them have complexity , where N - number of signals in the training set and d is number of samples per signal. In practice this allows to process signals with number of samples d < 1000. Many pattern recognition tasks require to process larger signals, in particular, recognition of radar emission requires to process random fields with number of samples 10⁴-10⁵. Therefore reduction of random field dimension is important problem. It is known that Karhunen-Loeve(KL) transform is most efficient tool for this purpose. However, it is known that complexity of KL basis construction directly from the KL theorem is also operations. Therefore it is needed to construct orthogonal bases with good approximation ability which may be build within the limited cost. In other words it is needed to find bases optimized for two parameters: amount of resources needed for basis construction and basis approximation efficiency.

The known such a method, which is optimized for these two parameters, is fast wavelet based algorithm for approximate KL basis construction. It has complexity O(NdLog(d)). However, usually basis quality, which gives this method, is much worse than true KL basis.

Some of radiophysical objects for which dimension reduction is pressing question are random fields. Objects like that are radar signals written as 2D image for optical processing, images of textured surface and so on. For many of them empirical or model considerations allow to conclude that independent accounting of vertical and horizontal correlation may allow to build orthogonal basis with good approximation ability and reduced computing cost. Therefore for random fields with properties like that fast two dimensional algorithm for approximate KL basis construction is suggested. It is demonstrated that for random fields with properties discussed above it has better basis quality compare to basis found by wavelet algorithm of approximate KL basis construction according to approximation criterion. In general case successive procedure for choice of basis which has the less reduced dimension for given approximation error is presented. The choice is made among bases, which may be build within limited cost.

The problem which is needed to investigate regarding considered fast algorithms for approximate KL basis construction is how much the approximate bases obtained by the fast algorithms are far from exact KL basis? Wavelet and 2D algorithms for approximate KL basis construction produce the basis which is constituted by product of two 1D bases. It is demonstrated that such basis structure does not allow to achieve basis quality close to true KL basis. Such a result is obtained using suggested method for best 2D KL basis construction which provides the best approximation of correlation matrix by product of two matrices. In order to overcome discovered limitations of approximate KL bases new procedure based on reversible pixels rearranging for their improving is suggested. Its efficiency is demonstrated on texture analysis problem.

The thesis presents new method for correlated signal compression based on KL transform which is known to be optimal for such a purpose. The idea of the method is to compress KL basic functions instead of signals themselves. The core of the method is in the suggested procedure for determining affordable distortion of basic functions provided the distortion of restored signals is no more than given threshold. This allows to achieve maximum compression for allowed distortion level. The procedure needs compression algorithm for single signal compression which allows to compress with predefined information loss and is able to produce size(loss) curve fast for given signal. For this purpose two well known compression methods are considered. Namely, JPEG and Embedded Zerotree Wavelet coding (EZW). It is shown that EZW suits for this purpose much better than JPEG. Its usage makes compression method more simple and fast. The suggested compression method is applied to multispectral images of Earth surface. It is shown that its usage provides compression gain 1.1-3 dB compare to separate compression of each signal. Also other signal sources are considered and general recommendations for usage of compression method are worked out. It is also concluded that noise present in signals decrease the algorithm efficiency and in such case preliminary filtration should be done.

Keywords: random field dimension reduction, Karhunen-Loeve transform, wavelet transform, pattern recognition, image compression.

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

Актуальність теми. Стрімкий розвиток електроніки створює нові можливості для проведення вимірювань з дуже високою часовою, частотною чи просторовою роздільною здатністю. Наслідком цього є значне зростання інформаційної місткості сигналів, з якими доводиться мати справу в системах обробки та аналізу сигналів, особливо, якщо це стосується систем реального часу. Наприклад, в галузі радіотехнічної розвідки, розпізнавання випромінювання РЛС існує необхідність обробки двовимірних полів в реальному часі. Проте, велика кількість відліків в полі, не дозволяє використовувати для цього класичні методи виявлення та розпізнавання. Причиною цього є те, що проведення виділення ознак класичними методами, типу дискримінантного аналізу, та обчислення параметрів класифікатора в такому разі є обчислювально дуже складним. До того ж, радіотехнічний пристрій, який ефективно реалізує подібний класифікатор, стає надзвичайно дорогим[1-5].

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

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

З розвитком комп'ютерної техніки і комп'ютерних мереж все гостріше постає проблема стиснення сигналів та випадкових полів при їх збереженні в базі даних чи передачі по каналу зв'язку. Досить часто в такому разі поля є висококорельованими і вилученням з них надлишкової інформації можна суттєво, до 2-5 разів, підвищити рівень стиснення, що отримується вже відомими методами. Це майже в таку ж кількість разів зменшує витрати на носії інформації - жорсткі диски, лазерні диски, чи на оренду каналу зв'язку. Згадана проблема постає при супутниковій зйомці земної поверхні в різних довжинах хвиль, де отримувані зображення є висококорельованими і їх успішна декореляція і подальше ефективне стиснення дозволить передати значно більше інформації за час проходження супутника над пунктом зв'язку. Розроблені на сьогодні методи, які вирішують ці задачі[7-8], не можуть вважатись достатніми.

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

Зв'язок роботи з науковими програмами, планами, темами.

Робота виконана в лабораторії оптичної обробки інформації та теорії середовищ радіофізичного факультету Київського університету імені Тараса Шевченка. Її результати отримані при проведенні фундаментальних і прикладних досліджень за такими темами. “Розробка та дослідження методів цифрового та оптоелектронного аналізу випадкових процесів”, № держреєст. 0194U007144. При виконанні цієї теми автором було розроблено метод двовимірного наближеного перетворення КЛ та проведено його порівняння з хвильковим наближеним перетворенням КЛ, опубліковано статті [5,6]. "Дослідження обернених задач статистичної та квантової оптики", № держреєст. 0197U014601. В межах цієї теми автором проведено дослідження обмежень двовимірних ортогональних перетворень утворених як добуток одновимірних, та створено метод стиснення корельованих сигналів на основі перетворення КЛ, опубліковано роботи [1-4,7-12,14-15]. “Розробка експертної системи радіоекологічного моніторингу, поточного та довгострокового прогнозу міграції радіонуклідів та біоіндикація їх впливу на лісові екосистеми зони відчуження ЧАЕС”, № держреєст. 0198U007544. Пошукач брав участь у розробці системи, підготовці даних для неї. “Розробка і виготовлення низькочастотних комплексів для реєстрації природних електромагнітних полів для наземного супроводу космічного експерименту “Попередження”. В межах цієї теми автором було запропоновано модель системи розпізнавання провісників землетрусів і опубліковано роботу [13].

Мета дисертаційної роботи полягає в:

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

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

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

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

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

Методи дослідження

Кореляційна теорія випадкових функцій (процесів і полів) за допомогою якої шукаються ефективні ортогональні розвинення оптимізовані за двома параметрами: обсягу ресурсів, необхідних для побудови базисів, і апроксимаційній здатності отримуваних перетворень;

Чисельне моделювання на ЕОМ методів зниження розмірності випадкових полів та їх порівняння з відомими методами на основі інтегральних спектрів коефіцієнтів перетворення;

Порівняння запропонованих методів стиснення випадкових полів з існуючими методами на основі залежності пікового відношення сигнал/шум від ступеня стиснення.

Наукова новизна одержаних результатів полягає в:

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

створенні методу побудови ефективного швидкого двовимірного наближеного перетворення КЛ для зниження розмірності випадкових полів.

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

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

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

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

Практичне значення роботи.

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

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

Особистий внесок здобувача.

В статтях [1, 7] автору належить ідея застосувати алгоритм найкращого двовимірного перетворення КЛ до аналізу двовимірних перетворень та ідея методу покращення якості двовимірних наближених базисів і проведене моделювання.

В роботах [4-6] автором запропоновано новий швидкий двовимірний алгоритм наближеного перетворення КЛ і здійснене порівняння з відомим алгоритмом на основі хвилькового перетворення.

В роботі [8] автором було запропоновано новий алгоритм побудови базису КЛ із зниженою вартістю для систем реального часу та виконано моделювання для сигналів типу текстур.

В статтях [3,9-11] та роботах [14-15] автору належить ідея нового методу стиснення корельованих сигналів на основі перетворення КЛ, ідея ефективного алгоритму перетворення КЛ з низьким споживанням пам'яті та ідея процедури відшукання оптимальних ступенів стиснення базисних функцій. Автором було створено програмне забезпечення для всіх запропонованих алгоритмів та отримані експериментальні результати.

В статтях [2,12] автором було запропоновано методику відшукання порядку в розташуванні острівців вісмуту, та програмно реалізовано відповідний алгоритм.

В роботі [13] автором було запропоновано модель розпізнаючої системи та проведене відповідне моделювання.

Апробація результатів роботи.

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

"Electronic Imaging '96", January 1996, San-Jose, California, USA;

"Aerosense '96", April 1996, Orlando, Florida, USA;

"Electronic Imaging '97", January 1997, San-Jose, California, USA;

"Correlation Optics '97", May 1997, Chernovtsy, Ukraine;

"Optical Information Science and Technology '97", August 1997, Moscow, Russia;

“Aerosense'98”, April 1998, Orlando, Florida USA;

“Syben'98”, May 1998, Zurich, Switzerland;

“Optical Science, Engineering and Instrumentation”, July 1998, San-Diego, California USA;

“Теория и техника передачи, приема и обработки информации'98”, октябрь 1998, Туапсе , Россия;

“Voice, Video and Data Communications”, November 1998, Boston, USA;

“Оброблення сигналів і зображень та розпізнавання образів'98”, листопад 1998, Київ, Україна.

Серія робіт, на основі якої написана дисертація, є лауреатом конкурсу на здобуття премії імені Тараса Шевченка за 1998р., яка щорічно присуджується Київським університетом імені Тараса Шевченка, і лауреатом конкурсу 1998р. “На здобуття премій молодих учених і студентів вищих навчальних закладів за кращі наукові роботи”, які присуджуються Національною Академією Наук України.

Публікації. Основні результати дисертації викладено в 12 статтях та 3 тезах конференцій. Загальна кількість статей автора 18 та 13 тез.

Структура та обсяг дисертації. Робота складається зі Вступу, п'ятьох розділів, висновку та списку використаної літератури. Загальний обсяг дисертації становить 168 сторінок в тому числі 45 рисунків, 3 таблиці та 116 назв бібліографічних джерел на 11 сторінках.

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

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

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

Представлені основні процедури виділення інформативних ознак сигналів. Наголошено на обчислювальній складності алгоритмів побудови оптимальних ортогональних базисів, оскільки саме вони принципово є визначальними для синтезу пристроїв виділення ознак і розпізнавання образів. Відзначено, що вони мають складність (де N - число сигналів в навчаючій вибірці, d - число відліків в сигналі), що не дозволяє здійснювати синтез розпізнаючого пристрою для сигналів та полів з кількістю відліків > 1000 засобами сучасної обчислювальної техніки. Розглянуто задачу розпізнавання випромінювання РЛС і зазначено, що вона вимагає здійснення розпізнавання сигналів з базою до 10⁴ -10⁵. Відзначено, що для реалізації такої системи, яка працює в реальному часі, потрібні нецифрові методи обробки сигналів. Для цієї мети використовуються оптичні процесори. В такому випадку сигнал записується в растр і обробляється як двовимірне випадкове поле. Зроблено висновок, що однією з проблем при реалізації такої системи є побудова ортогональних базисів для виділення ознак засобами обчислювальної техніки. Як зауважено вище, побудова таких базисів класичними методами є утруднена, тому актуальною є задача зниження розмірності випадкових полів при незначному погіршенні якості і низьких витратах на побудову відповідного базису. Це дозволить використовувати класичні підходи для розпізнавання сигналів в поданні зі зниженою розмірністю.

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

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

Цих недоліків позбавлені методи другої групи чи швидкі алгоритми побудови наближеного базису КЛ. Зараз зауважимо лише, що вони дозволяють зняти обмеження першої групи. Вони є швидкими і дозволяють працювати з великими навчаючими вибірками сигналів великої розмірності. Відзначено, що відомим на сьогодні швидким методом побудови наближеного базису КЛ є алгоритм на основі хвилькового перетворення[6]. Його складність є O(Nd log(d)) операцій. Однак, отримувані швидкими методами базиси часто виявляються значно гіршими за оптимальні в розумінні апроксимаційного критерію. Можна зробити висновок, що вказані методи потребують подальшого вдосконалення. Зокрема, виникає питання, чи існують методи, кращі за хвильковий алгоритм побудови наближеного базису КЛ, і в якій мірі подібні базиси далекі від оптимального?

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

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

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

Отримання оцінок близькості подібних наближених базисів до справжнього базису КЛ.

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

Розробка ефективного методу побудови базису КЛ на звичайному обладнанні без необхідності використовувати оперативну пам'ять надвеликого обсягу і обміну з диском.

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

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

В подальших розділах вирішуються сформульовані вище проблеми.

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

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

Як сказано вище, для швидкої роботи відомих методів побудови базису в реальних задачах розпізнавання та стиснення сигналів, необхідні дуже великі обсяги оперативної пам'яті. Бо при малих її обсягах інтенсивне використання операцій введення/виведення різко збільшує час обчислень і робить дані алгоритми непридатними до використання в системах з жорсткими вимогами до часу реакції. З метою подолати ці проблеми було запропоновано метод побудови базису КЛ з низьким споживанням ресурсів, який не вимагає великого обсягу оперативної пам'яті і має малу кількість операцій введення/виведення. Запропонований метод базується на алгоритмі з ВОБ. Складність вихідного методу з ВОБ можна подати у вигляді , якщо де ~1 в разі якщо вся інформація знаходиться в ОЗП і ~5-100 в разі якщо вся інформація знаходиться на диску. Складність запропонованого алгоритму є . Видно, що в запропонованому підході швидкість операцій введення/виведення має на порядок менше значення. Порівняння запропонованого алгоритму з алгоритмом з ВОБ для ансамблів зображень 125 реалізацій 256x256 та 16 реалізацій 800x800 показує, що на сучасному обладнанні запропонований алгоритм працює в 6 разів швидше ніж традиційний метод з ВОБ.

Результати представлені в цьому розділі опубліковані в роботах[2,4,8, 10-12, 14]

В третьому розділі розглянуто проблему пошуку ортогональних розвинень оптимізованих за двома показниками: обсягові ресурсів, необхідних для побудови базисів, і апроксимаційній здатності отримуваних перетворень. Розглянуто швидкі алгоритми наближеного перетворення КЛ, які, за рахунок деякого зниження якості базису, дозволяють швидко обробити навчаючу вибірку з великою кількістю елементів. В першій частині розділу розглядається теорія хвилькових(wavelet) перетворень і хвилькових пакетів. Також розглянуто алгоритм наближеного перетворення КЛ на основі хвилькового перетворення. Його основна ідея полягає в швидкому розвиненні ансамблю сигналів в великий набір базисів і швидкому пошуку серед них найкращого за деяким критерієм. Складність методу є операцій.

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

Основним конкурентом методу є згаданий вище алгоритм наближеного перетворення КЛ на основі хвилькового перетворення.

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

Рис. 1. Середньоквадратична похибка відновлення випадкового поля- зондуючих радіолокаційних сигналів записаних в растр, як функція кількості використаних коефіцієнтів для справжнього базису КЛ, наближеного базису КЛ отриманого двовимірним алгоритмом (2D), та наближеного хвилькового базису КЛ з фільтрами Хаара та Добічіс-4.

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

Результати розглянуті в цьому розділі опубліковані в роботах[4-6].

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

. (1)

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

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

Рис. 2. Середньоквадратична похибка відновлення модельних текстур як функція кількості використаних коефіцієнтів для справжнього базису КЛ (KL), базису отриманого двовимірним алгоритмом (2D), найкращого двовимірного базису (Best2D) та хвилькового базису КЛ з фільтрами Хаара (Haar) та Добічіс-4 (DB4).

Експерименти зі спеціально підготовленими випадковими полями показали, що в більшості випадків якість базису відшукуваного з умови (1) набагато гірша від якості точного базису КЛ. На підтвердження цього на Рис. 2 наведено графік середньоквадратичної похибки відновлення 64 модельних полів 32x32 як функцію кількості використаних коефіцієнтів для справжнього базису КЛ, базису отриманого двовимірним алгоритмом, найкращого двовимірного базису та хвилькового базису КЛ з фільтрами Хаара та Добічіс-4. Таким чином всі інші зазначені двовимірні базиси утворені як добуток одновимірних не можуть давати високоякісного наближення базису КЛ.

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

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

Результати представлені в цьому розділі опубліковані в роботах[1, 7].

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

Для ефективної побудови базису КЛ використано представлений в розділі 2 алгоритм відшукання базису КЛ з обмеженою кількістю операцій введення/виведення.

Розроблено методику стиснення сигналів із заданими втратами і отримання кривої залежності розміру стиснутого сигналу від енергії втрат (спотворень) для двох сучасних процедур стиснення: алгоритму JPEG та алгоритму на основі кодування “деревом нулів” коефіцієнтів хвилькового перетворення - EZW (Embeded Zerotree Wavelet coding). Показано, що з цієї точки зору алгоритм з кодуванням деревом нулів має значні переваги порівняно з JPEG.

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

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

Результати представлені в цьому розділі опубліковані в роботах[3, 9-13, 15].

Висновки

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

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

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

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

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

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

Створено нову методику стиснення корельованих даних із втратами на основі швидкого алгоритму точного перетворення КЛ. Вперше запропоновано процедуру, яка дозволяє здійснювати теоретично оптимальне стиснення корельованих сигналів. Показано, що даний метод дозволяє добитись підвищення ступеню стиснення в 1.1-2 рази, порівняно з існуючими методами.

На основі отриманих результатів можна сформулювати такі висновки роботи:

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

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

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

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

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

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

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

Список публікацій по темі дисертаційної роботи

Мусатенко Ю.С., Курашов В.Н. Найкраще двовимірне перетворення Карунена-Лоева // Вісник Київського університету. 1997. № 2. C.270-282.

Булавенко С.Ю., Курашов В.Н., Мусатенко Ю.С., Находкін М.Г. Методика кількісної обробки СТМ-зображень частково-впорядкованих систем // Вісник Київського університету. 1998. № 4. С.243-248.

Мусатенко Ю.С. Стиснення кольорових зображень з кодуванням кольору на основі перетворення Карунена-Лоева // Вісник Київського університету. 1998. #2. pp.337-352.

Nakhodkin M.G., Musatenko Yu.S., Kurashov V.N. Pattern recognition with fast feature extraction // Optical Memory and Neural Networks. 1997. v.6. #3. P.175-186.

Kurashov V.N., Musatenko Yu.S. Approximate Karhunen-Loeve transform for image processing // SPIE Proceedings. 1996. v.2166. P.72-83.

Musatenko Yu.S., Kurashov V.N., Chumakov A.G. Comparison of wavelet and Karhunen-Loeve representation in texture applications // SPIE Proceedings. 1996. v.2762. P.353-364.

Musatenko Yu.S., Kurashov V.N. Nonlinear improving of Karhunen-Loeve bases obtained by approximate 2D procedures // SPIE Proceedings. 1997. v.3026. P.315-326.

Musatenko Yu.S., Kurashov V.N. Optical field analysis by means of reduced Karhunen-Loeve representation with full elements accounting // SPIE Proceedings. 1997. v.3317. P.54-61.

Musatenko Yu.S., Kurashov V.N. Optimal image coding for compression of correlated image sets // SPIE Proceedings. 1998. v.3408. P. 486-497.

Musatenko Yu.S., Kurashov V.N. Optimal color coding for compression of true color images // SPIE Proceedings. 1998. v.3456. P. 185-196.

Musatenko Yu.S., Kurashov V.N. Correlated image set compression system based on new fast efficient algorithm of Karhunen-Loeve transform // SPIE Proceedings. 1998. v.3527. P. 518-529.

Bulavenko S.Yu., Kurashov V.N., Musatenko Yu.S. Analysis of arrangement regularity of bismuth islands on Si(111) 7x7 surface using Fourier rejection filter // Proceedings of the Eighth Inter. Workshop on Ion Beam Surface Diagnostics, Uzhgorod 1998, P. 173-174.

Musatenko Yu. S., S. I. Musatenko and V.N. Kurashov Model of satellite based earthquake precursor recognition system // SPIE Proceedings. 1998. v.3374. P.515-523.

Мусатенко Ю.С., Курашов В.Н. Алгоритм швидкого перетворення Карунена-Лоева з малим споживанням ресурсів // 4-та міжн. конф.”Теория и техника передачи, приема и обработки информации” Тези доповідей - ХТУРЕ, Туапсе 98, С. 77-78.

Мусатенко Ю.С. Система стиснення мультиспектральних зображень на основі швидкого перетворення Карунена-Лоева для супутникових систем зйомки земної поверхні // 4-та міжн. конф.”Теория и техника передачи, приема и обработки информации” Тези доповідей - ХТУРЕ, Туапсе 98, С. 79-80.

Перелік цитованих джерел.

Фрэнкс Л. Теория сигналов. М.: Сов. радио, 1974. 344с.

Игнатов В.А. Теория информации и передачи сигналов . М. Радио и связь, 1991. 280с.

Омельченко В.А. Спектральная теория распознавания сигналов. Х. Вища школа, 1983. 156c.

Фукунага К. Введение в статистическую теорию распознавания образов // Пер. с англ. М.: Наука, 1979. 368с.

Chumakov A.G., Kurashov V.N. Karhunen-Loeve basis synthesis for great capacity signal performance in optical processors // SPIE Proceedings. 1993. v.2108. P. 338-342.

Wickerhauser M.V. Two fast approximate wavelet algorithms for image processing, classification, and recognition // Opt. Eng. 1994. v.33. P. 2225-2235.

J.A. Sahri, A.G.Tescher Near-lossless bandwidth compression for radiometric data // Opt.Eng. 1991. v.30. No.7. P.934-939.

J.A. Sahri, A.G.Tescher, J.T.Reagan Practical transform coding of multispectral imagery // IEEE Signal Processing Magazine. 1995. P.32-43.

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

...