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

На правах рукописи

ФОМЕНКО Людмила Николаевна

ОПТИМАЛЬНЫЕ БАЗИСЫ В МАТЕМАТИЧЕСКИХ МОДЕЛЯХ АЛГОРИТМОВ РАСПОЗНАВАНИЯ И СЖАТИЯ ИНФОРМАЦИИ

Специальность 05.13.18 - Математическое моделирование, численные

методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Ростов-на-Дону 2004

Работа выполнена на кафедре прикладной математики и

вычислительной техники государственного образовательного учреждения высшего профессионального образования - Ростовского государственного строительного университета

Научный руководитель: доктор технических наук, профессор

Белявский Григорий Исаакович

Официальные оппоненты: доктор технических наук, профессор

Лябах Николай Николаевич

кандидат технических наук, доцент Мермелыптейн Геннадий Гаврилович

Ведущая организация: Таганрогский государственный радиотехнический университет (ТРТУ)

Защита состоится «9 » декабря 2004 г. в 13 часов на заседании диссертационного совета К 218.010.01 по техническим наукам в Ростовском государственном университете путей сообщения, по адресу: 344038, г. Ростов-на-Дону, пл. Народного ополчения, 2, конференц-зал.

С диссертацией можно ознакомиться в научной библиотеке РГУПС. Автореферат разослан << У» ноября 2004 г.

Отзывы на автореферат, в двух экземплярах, заверенные печатью, просим направлять по адресу: 344038, г. Ростов-на-Дону, пл. Народного ополчения, 2, РГУПС, диссертационный совет К 218.010.01.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент

М. А. Бутакова

90905--7-

з

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования

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

Одной из современных, остро стоящих проблем является работа с различного рода сигналами. В настоящее время специалисты, занимающиеся обработкой и анализом информации, содержащейся в сигналах, работают в двух направлениях: 1) разработка математических методов описания классов и на их основе построение оптимальных процедур распознавания, 2) сжатие информации путем раскладывания суммарного сигнала по более простым сигналам, т.е. по базису.

Тема диссертационной работы относится к современным технологиям извлечения полезной информации из большого набора данных. Актуальность обусловливается: 1) решением задач, связанных с синтезом нелинейных решающих правил, в которых используется идеология представления класса маломерным подпространством, а, следовательно, решается задача подбора такого маломерного подпространства, то есть выбор некоторого оптимального базиса; 2) разработкой алгоритмов построения оптимальных вейвлет-базисов. Особенность исследования заключается в охвате обоих направлений, поскольку и в первом, и во втором случае решается задача

выбора оптимального базиса.

Цель и задачи исследования

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

Вытекающие из поставленной цели основные задачи:

1) исследовать эллипсоидное решающее правило, задача синтеза которого представлена в изолированной постановке;

2) рассмотреть задачу обучения для цилиндрического решающего правила как задачу идентификации на выборке подпространства;

3) провести анализ разложения Карунена - Лоэва;

4) выбрать преобразования, наилучшим образом аппроксимирующие преобразование Карунена - Лоэва;

5) разработать алгоритмы построения базисов;

6) применить на практике созданные алгоритмы.

Объекты и методы исследования

Объектами научного исследования являлись задачи обучения для эллипсоидных и цилиндрических решающих правил, преобразование Карунена-Лоэва, алгоритмы построения оптимальных базисов Хаара и Хаара-Уолша.

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

Теоретическая база исследования

Теоретические исследования основывались на разработках отечественных и зарубежных ученых в области общей теории распознавания образов и вейвлет-технологий.

Научная новизна исследования заключается в следующем.

• Метод подпространств в распознавании образов относится к достаточно часто используемым приемам. В работе он реализован в виде двух решающих правил - эллипсоидного и цилиндрического, для которых решены задачи обучения. Для эллипсоидного решающего правила задача обучения рассматривалась как задача построения эллипсоида минимального объема, содержащего выборку. Известны алгоритмы ее решения. К новому результату относится разработанный в диссертации алгоритм одноранговой модификации. Задача обучения для цилиндрического решающего правила рассматривалась как задача идентификации подпространства малой размерности. К новому относится то, что при ее решении доказан факт взаимооднозначного соответствия подпространства и орбиты группы невырожденных линейных преобразований. В результате получено общее решение задачи идентификации подпространства.

• Вейвлет-преобразование для сжатия сигналов широко применяется в научно-технической практике. В исследовании к новому относится задача выбора «наилучшего» вейвлет-базиса по отношению к ансамблю сигналов. Задача выбора решена в трех постановках, как: 1) задача оптимальной перестановки; 2) задача поиска на бинарном дереве; 3) задача наилучшего разбиения множества индексов на непересекающиеся подмножества.

Основные положения, выносимые на защиту:

1. Эллипсоидное и цилиндрическое решающие правила, для которых решены задачи обучения в изолированной постановке.

2. Алгоритмы обучения для эллипсоидного и цилиндрического решающих правил и их теоретическое обоснование.

3. Три метода построения оптимальных вейвлет-базисов.

4. Алгоритмы построения оптимальных вейвлет-базисов и их теоретическое обоснование.

Практическая значимость исследования

Составлены алгоритмы, реализованные в среде VBA-Excel для обработки изображений с мелким сдвигом и разложения сигналов по экстремальным вейвлет-базисам, что позволяет сжимать и экономно хранить информацию для последующего ее экспресс-анализа в медицине, машиностроении, строительстве, геологии и других областях. Достоверность результатов работы

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

Апробация и внедрение результатов исследования

Основные результаты диссертационной работы докладывались и обсуждались на Девятой Всероссийской школе-коллоквиуме по стохастическим методам (Ростов-на-Дону, 2002 г.), Третьем Всероссийском симпозиуме по прикладной и промышленной математике (весенняя сессия, Ростов-на-Дону, 2002 г.), методологических семинарах кафедры прикладной математики и вычислительной техники (Ростов-на-Дону, 2002,2003, 2004 гг.), совещании руководителей и специалистов ВНИГРИуголь в области геологии и геофизики (Ростов-на-Дону, май 2004 г.).

Отдельные научные разработки диссертационного исследования используются в учебном процессе РГСУ при чтении лекций и проведении практических занятий в группах студентов специальности прикладная информатика по дисциплине «Интеллектуальные информационные системы».

Публикации

По теме диссертации опубликовано шесть печатных работ, список которых приведен в конце автореферата.

Объем и структура диссертации

Диссертация состоит из введения, трех глав, заключения, списка используемых источников (82 наименования), двух приложений, содержащих коды программ, связанных с исследованием. Материалы работы изложены на 134 страницах, включая 29 рисунков, 7 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе «Синтез нелинейных решающих правил и их геометрическая интерпретация» сделана попытка поиска компромисса между кусочно-линейными решающими правилами и квадратичными решающими правилами.

В разделе 1.1 рассматривается задача обучения для эллипсоидного решающего правила вида:

где - положительно определенные симметрические матрицы,

Имеется в виду, что мы относим к классу с номером такой наблюдаемый вектор, который попадет внутрь эллипсоида, и

*) Нумерация (обозначения) определений, утверждений и теорем соответствует обозначениям диссертационной работы, в то время как для формул, рисунков и таблиц использована сквозная нумерация.

отказываемся от распознавания в случае, если он окажется одновременно внутри двух и более эллипсоидов. Задача обучения заключается в следующем: по имеющейся выборке представителей к-го класса требуется найти параметры правила Для

упрощения записи индекс к опущен. При этом выборка должна находиться внутри эллипсоида, т.к. для всех элементов выборки с1(х) = к . Косвенным показателем качества обучающего правила является объем эллипсоида. Возникает матричная оптимизационная задача, связанная с поиском эллипсоида минимального объема. Эта задача решалась в ряде работ. В случае большой размерности пространства признаков рассмотренные в этих работах методы неприменимы из-за огромных вычислительных затрат, а решающее правило становится слишком громоздким и практически трудно применимым. Поэтому предлагаются матрицы определенного вида с предположением, что спектр этих матриц имеет следующую структуру:

Такие матрицы можно представить в виде:

Структура матрицы позволяет предложить алгоритм

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

тт(-1п((1 + (В;!1,1)) + т тах(Вг(х} - а)^ -а) + (1,х1 - а)2)) (2)

где - размерность пространства признаков.

В следующих разделах рассматривается цилиндрическое решающее правило:

А{к)4<0ААиН*вР]*к

0, в остальных случаях

Здесь А(к) - матрица полного ранга размера т^ХП, причем т^ <П

подпространство размерности которое обозначим через

Далее индекс к будем опускать.

Установлено, что задача обучения сводится к идентификации подпространства Для решения этой задачи необходимо выбрать

параметризацию подпространства Н. С этой целью подпространству Н ставится в соответствие система линейных однородных уравнений, которая определяется матрицей Однако, однородные системы с

различными матрицами коэффициентов могут иметь одинаковое множество решений, поэтому на множестве матриц вводится

соответствующее отношение эквивалентности.

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

Утверждение 1.2. Пусть В - матрица полного ранга размера ПУ.т\ - орбита матрицы Тогда существует такая матрица что

- единичная матрица размерности Таким образом, матрица позволяет выбрать единственную матрицу из , то есть осуществить проектирование

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

Уравнение определяет в пространстве линейное

имеется выборка векторов V = {х^Д^,...,*/}. Требуется «провести» подпространство Н таким образом, чтобы оно было как можно ближе к данной выборке. В качестве критерия близости взята сумма квадратов:

^ЦЛл^-Ц2 . В результате показано, что задача идентификации подпространства

сводится к задаче:

^ттТг(АМт)

В (4) В- заранее выбранная по каким-то соображениям матрица

проектирования. Получено общее решение задачи идентификации:

где Л - ковариационная матрица. Отдельно рассмотрен случай, когда

матрица А состоит из одной строки, при этом матрица проектирования

состоит из одного столбца. Оптимальная оценка будет иметь вид: Предложено несколько способов выбора вектора

1) Выбор Ь — е^ означает, что ошибки могут находиться только в ]-ом

столбце матрицы наблюдений. Иными словами, только }-ая переменная измеряется с ошибкой. Сумма квадратов ошибок измерений совпадает с единицей, деленной на ^й диагональный элемент матрицы Л"1. Если рассматривать выбор Ъ в этом классе, то оптимальное решение будет

иметь вид: Ь = егде ] =аг§гпахг^1. Назовем такое решение

наилучшимрегрессионнымрешением.

2) Мы можем разделить переменные на две группы: переменные, измеряемые с ошибками и переменные, измеряемые без ошибок. Пусть

- множество индексов, для которых переменные измеряются с ошибками. Определим матрицу-столбец следующим образом:

Обозначим такую матрицу-столбец через

Оптимальный выбор заключается в выборе вектора где

3) Пусть все переменные измеряются с ошибками. В этом случае задача выбора наилучшего вектора будет выглядеть следующим образом:

(Ь,Ь)

тш

(Я~1Ь,Ь)

4) Если известны отношения среднеквадратических отклонений ошибок

07

измерений: то вектор выбирается равным

а\

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

Кроме квадратичного критерия в работе использован минимаксный критерий. Для него задача идентификации подпространства рассматривается в следующей постановке:

n

а р /=1

(5)

где - распределение вероятностей на выборке.

В главе приводится пример эмпирического вычисления константы Хаббла.

Вторая глава «Сжатие сигналов с использованием экстремальных вейвлет-базисов» посвящена ортогональным преобразованиям, которые представляют собой один из способов сжатия информации. Рассматривается задача выбора из вейвлет-пакета оптимального базиса.

Определение 2.1. Будем называть ансамблем векторов совокупность К векторов Г = (Х(]),Х(2).....Х{К)), где каждый вектор

Х^ = (ху\х2/ = 1,2,..., К является элементом пространства .

Все векторы ансамбля запишем в виде матрицы X = (Х(1), Х(2),..„ Х(К)). Размерность матрицы X равна ЫхК.

1 ^

Определение 2.2. Вектор М- — назовем средним вектором

ансамбля.

Определение 2.3. Ковариационной матрицей ансамбля назовем матрицу

С = — XX1-ММУ. К

Рассмотрим ортонормированный базис

6 Я ,то

базис, для которого выполнено = где S¡ j = 1

есть

функция Кронекера.

Обозначим матрицу базисных векторов через

матрица С/ имеет размерность N х N. Для нее, т т

очевидно, выполняется соотношение С/С/ =С/ С1 = Е. Любой вектор ансамбля можно разложить по выбранному базису, т.е.

n

у=1

(6)

По каналу связи вместо координат вектора Х^ можно передавать

(О

коэффициенты разложения а^. Сжатие информации произойдет в том

случае, если по каналу связи будет передаваться часть коэффициентов разложения (6). При этом теряется часть информации, которая содержится в

векторе Если потерю информации измерять как норму разности

то возникает задача выбора базиса, для которого

величина была бы минимальной. Такое разложение называют

разложением Карунена-Лоэва.

Поскольку преобразование Карунена-Лоэва обладает большим набором полезных свойств для осуществления сжатия информации, то оно было выбрано в качестве «идеала» для подражания. В связи с этим на множестве ортогональных преобразований вводится метрика и задача выбора оптимального преобразования ставится как задача выбора наиболее близкого преобразования из заданного множества ортогональных преобразований. Пусть - ортогональное преобразование, - по-прежнему означает преобразование Карунена-Лоэва. Определим коэффициент кодирования преобразования:

вг^КО/ехр Н(1¥Х). (7)

В (7) = где ^ 0 = (г(С)

n

1

2N

1=1

К

у=1

Таким образом, коэффициент максимален, когда минимальна.

Показатель экспоненты можно интерпретировать, например, как

энтропию (с точностью до постоянного слагаемого и постоянного множителя) суммы независимых нормально распределенных случайных величин или как логарифм от объема эллипсоида рассеивания, если добавить постоянное слагаемое. Как нетрудно понять, максимизация коэффициента эквивалентна минимизации объема эллипсоида рассеивания. Преобразование Карунена-Лоэва доставляет минимум на множестве всех ортогональных преобразований, и мы будем говорить, что преобразование наилучшим образом аппроксимирует преобразование Карунена-Лоэва на некотором

подмножестве ортогональных преобразований, если щГ доставляет минимум Н на подмножестве ИЛ Мы можем оценить близость преобразования IV к преобразованию С/ вычислением

(1х^,и) = \НС¥Х)-Н(иЦ. (8)

Отметим, что (8) определяет метрику на группе ортогональных преобразований, если отождествить преобразования , для которых

Н0¥Х)~Н0¥Х). Выше мы упомянули, что Н(1*¥Х) можно интерпретировать как логарифм объема эллипсоида рассеивания. Поэтому

Н(Щ) = НРУХ) » где (/¡(А)

диагональный элемент матрицы

Как уже отмечалось ранее, преобразование Карунена-Лоэва £/ доставляет минимум Н. Следовательно, задача минимизации Н эквивалентна задаче минимизации с1х. Таким образом, вычисляется ближайшее к преобразованию Карунена-Лоэва ортогональное преобразование в рассматриваемой метрике.

Далее рассматриваются три варианта выбора оптимального вейвлет-базиса.

В первом случае используется классический базис Хаара. Будем считать, что размерность пространства признаков N = 2^, Рассмотрим Хааровскую фильтрацию: О = {1,2,...,.^} - множество номеров координат

пространства Я*, = },..., = причем

4"-и=А^иА^ и А^ПА^, =0. Эту фильтрацию можно

изобразить в виде бинарного дерева:

Рис. 1. Бинарное дерево

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

правилом: П — 1 слою дерева или сигма-алгебре Рп_\ соответствуют 2

л-1

базисных вектора

сконструированных следующим образом:

Обозначим через Наг стандартное хааровское преобразование. Рассмотрим матрицу Р перестановок координат. Будем рассматривать множество IV - Хааровских преобразований вида: Наг[р)=НагР и на этом множестве необходимо выбрать такое преобразование, чтобы доставить минимум Н{Наг{Р)х) по матрице перестановок

Постановка задачи. Рассмотрим целевую функцию

где У = Наг(Р)Х = НагРХ. Задача выбора оптимального базиса формулируется как задача выбора оптимальной перестановки

ттН(Наг(Р)Х). Она сводится к задаче булевого программирования и

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

Для построения второго метода сжатия информации используется вейвлет-пакет, также порождаемый бинарным деревом. Определим два оператора:

(9)

Показано, что исходное пространство разлагается в прямую сумму подпространств одинаковой размерности, тогда размерность исходного

пространства должна быть кратна степени числа два, т.е. При

этом мы можем рассмотреть Ь уровней разбиения. Доказано, что из ансамбля

(Хт,Х®.....Х^) задача выбора оптимального базиса сводится к задаче

поиска на бинарном дереве. Предлагается алгоритм решения, сложность которого существенно ниже сложности построения преобразования Карунена-Лоэва.

Далее рассмотрен специальный базис Хаара. Множество базисов порождается деревом, на каждом уровне которого дробится только одна вершина. В качестве базисных векторов будем выбирать векторы и, которые

имеют следующую структуру: компонента вектора где

причем для базисных векторов выполняется

1ц Г) 1у = 0. Это обеспечивает ортонормированность базисных векторов. Задача о наилучшем базисе сводится к задаче выбора наилучшего разбиения множества индексов {1,2,..., Ы] на непересекающиеся подмножества

индексов {/;}" |. Предложен метод ее решения, использующий эффективный

тест, который позволяет оптимально разбивать произвольное множество индексов на два подмножества.

Третья глава «Некоторые применения алгоритмов распознавания и сжатия сигналов» посвящена реализации разработанных в первой и второй главах диссертации методов.

Первая из рассмотренных проблем связана с распознаванием классов, представленных большой галереей эталонов. В диссертации задача решается при помощи цилиндрического решающего правила, которое оказывается в несколько раз эффективней корреляционного метода по вычислительным затратам и сопоставима с ним по качеству распознавания. Эффективность метода демонстрируется на распознавании букв Б и В. На рис. 2 приведены порождающие модели букв В и Б, причем для черных клеток вероятность черного цвета равна 0,9, для серых клеток вероятность черного цвета равна 0,5, для белых - 0,1.

Е51 о

Рис. 2. Порождающие модели букв В и Б.

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

360.027,180.991,160.992,94.8517,43.2542,20.3851,19.9794,10.2979,

0.222022.

Структура собственных чисел позволяет сделать вывод, что основная информация содержится в первых четырех собственных векторах ковариационной матрицы, так как на долю первых четырех чисел приходится 89,4% суммарной дисперсии. Было построено цилиндрическое решающее правило для буквы В. Для проверки его эффективности было сгенерировано 10000 изображений буквы Б и подсчитано число изображений, оказавшихся внутри цилиндров. Данные приведены в табл. 1.

Таблица 1

Результатыраспознавания

545,973 485,976 287,553 132,762 ПраадХКЭДОбИ 9939 9569 9417 113_115

Во второй строке таблицы приведены пороги для цилиндрического решающего правила с одним, двумя и т.д. собственными векторами. В третьей строке таблицы приведено количество букв Б, распознанных как В, из выборки в 10000 элементов. Последний элемент третьей строки - это количество букв Б, распознанных как В для метода максимального правдоподобия (корреляционного метода). Как видно из табл. 1, цилиндрическое решающее правило сопоставимо с корреляционным методом по качеству распознавания и более, чем в два раза требует меньше вычислительных затрат.

Вторая задача посвящена сжатию данных экспериментальных наблюдений по технологии электрического зондирования (ЭЗ) геологических сред. Описывается сущность ЭЗ как способа «электробурения» геологических разрезов, физико-геологические предпосылки и особенности различных модификаций ЭЗ, с помощью которых удается получить сведения о

количестве и толщинах слоев горных пород, их удельном электрическом сопротивлении.

К наиболее применяемым модификациям ЭЗ относятся вертикальное электрическое зондирование (ВЭЗ), дипольное осевое зондирование (ДОЗ), электропотенциальное томографическое зондирование (ЭПТЗ). Для них «идеальными» считаются геологические разрезы, в которых по мере увеличения глубины каждый последующий слой по своей толщине больше суммы толщин предыдущих слоев. Однако, на практике такие ситуации крайне редки. Поэтому процесс изучения по данным ЭЗ геологических разрезов на глубину (интерпретация кривых) в большинстве случаев весьма сложен. К тому же кривые искажаются за счет влияния приповерхностных неоднородностей, если на них попадают (над ними размещаются) питающие и приемные линии.

Интерпретацию кривых ЭЗ возможно упростить, применяя методы сжатия информации. Это показано на примере геологического разреза на участке поля шахты «Степная» в Восточном Донбассе. При обработке сигналов применен третий метод, исследованный во второй главе диссертации.

На рис. 3 приведен график первой точки зондирования после предварительной обработки (данные подверглись центрированию и нормированию).

Отн. ед. ______________________________

ЗА 1 К

2Д - V \

1*1 \ ол -1Л

Рис. 3. График первой точки ЭПТЗ(шахта «Степная»)

Был построен оптимальный вейвлет-базис из семи векторов для ансамбля из тридцати векторов (30 отсчетов). На рис. 4 изображен график восстановленного зондирования по этому базису.

Отн. едг

.1,0 J-

Рис. 4. Результат восстановления

Сравнение рис. 3 и рис. 4 позволяет говорить о том, что имеющиеся незначительные различия не повлияли на форму кривой, что важно для анализа информации. Погрешность результата сопоставления оказалась меньше допустимой при данных измерениях.

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

Список литературы включает 82 наименования.

В приложениях приводятся коды программ, связанных с диссертационным исследованием, написанные в среде VBA-Excel.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Белявский Г.И., Фоменко Л.Н. Об аппроксимации преобразования Карунена -Лоэва // Обозрение прикл. и промышл. матем. - 2001. - Т. 8. -Вып. 1.-С. 101.

2. Белявский Г.И., Фоменко Л.Н. Алгоритм распознавания, использующий хааровский базис // Обозрение прикл. и промышл. матем. - 2001. - Т. 8. -Вып. 2. - С. 535.

3. Белявский Г.И., Фоменко Л.Н. Синтез оптимального конечномерного базиса Хаара // Известия вузов. Северо-Кавказский регион. Естеств.науки. - 2004. - № 1. - С. 3-5.

4. Круглое В.Е., Фоменко Л.Н. Об одноранговой модификации решающего правила типа ближайшего соседа // Обозрение прикл. и промышл. матем. - 2002. - Т. 9. - Вып. 1. - С. 261.

5. Круглое В.Е., Фоменко Л.Н. Об одной задаче обучения для эллипсоидного решающего правила // Известия вузов. СевероКавказский регион. Естеств.науки. - 2003. - № 2. - С. 12-14.

6. Фоменко Л.Н. Задача обучения для цилиндрических решающих правил // Известия вузов. Северо-Кавказский регион. Естеств.науки. - 2003. -Приложение № 11. - С. 14-21.

В совместных работах авторский вклад Фоменко Л.Н. составляет примерно 70 процентов.

Подписано в печать 28.10.04. Формат 60x84 1/16. Бумага писчая. Ризограф. Уч.-издл.1,0. Тираж 100 экз. Заказ 268.

Редакционно-издательский центр

Ростовского государственного строительного университета. 334022, Ростов-на-Дону, 22, ул. Социалистическая, 162

»2158 2

РНБ Русский фонд

2005-4 18972

т ВВЕДЕНИЕ.

1. СИНТЕЗ НЕЛИНЕЙНЫХ РЕШАЮЩИХ ПРАВИЛ И ИХ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ.

1Л. Задача обучения для эллипсоидного решающего правила.^

1.2. Цилиндрические решающие правила.2 *

1.3. Параметризация подпространства.

1.4. Матричный инвариант.

1.5. Алгебраический метод наименьших квадратов идентификации подпространства. Общее решение задачи идентификации подпространства.

1.6. Уравнение регрессии.

1.7. Выбор вектора b.

1.8. Выбор матрицы В.

1.9. Минимаксный критерий.

Актуальность темы исследования

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

Одной из современных, остро стоящих проблем является работа с различного рода сигналами. В настоящее время специалисты, занимающиеся обработкой и анализом информации, содержащейся в сигналах, работают в двух направлениях: 1) разработка математических методов описания классов и на их основе построение оптимальных процедур распознавания, 2) сжатие информации путем раскладывания суммарного сигнала по более простым сигналам, т.е. по базису.

Для первого направления характерна разработка математических методов описания классов и на их основе построение оптимальных процедур распознавания. В этом случае происходит максимально возможное сжатие информации, так как вместо всех параметров сигнала достаточно хранить лишь номер класса, к которому данный сигнал можно соотнести. Иными словами, распознавание представляет собой задачу преобразования входной информации в выходную, где в качестве первой уместно рассматривать некоторые параметры и признаки распознаваемых объектов, а в качестве второй - заключение о том, к какому классу относится распознаваемый объект. При этом под классом понимается множество объектов, явлений или ситуаций, которым присущи некоторые общие свойства, позволяющие объединить их, рассматривать как сходные и в то же время отличать от объектов с другими свойствами, которые следует отнести к другим множествам [15, 25, 27, 31, 42, 47, 57, 65].

Следует пояснить, что когда появляется объект, подлежащий распознаванию, то с помощью технических средств наблюдений определяются его признаки. Далее данные о признаках изучаемого объекта поступают на вход алгоритма распознавания, который, используя априорные описания, определяет к какому классу может быть соотнесен этот объект. При этом каждая система распознавания «работает» для распознавания только данного вида объектов или явлений. Это создает определенную громоздкость операций и предопределяет поиск других подходов. Одним из них является использование систем сжатия информации как более универсальных.

Каждый объект (сигнал) - конкретный представитель класса обозначим через вектор - столбец X х2

XnJ где каждый элемент вектора отражает какие-либо свойства объекта и называется его признаком. Если при распознавании используется п признаков, то каждый объект можно представить в виде точки п- мерного евклидового пространства R". Для отличия одного сигнала от другого, будем приписывать вектору X верхний индекс, обозначающий порядковый номер в последовательности сигналов поступающих на вход распознающего устройства. Поскольку каждый элемент вектора сигнала Х^ = ^, \., х^ ] отмечается двумя индексами, условимся обозначать через х^ значение к -го признака у /-го сигнала.

В настоящее время предложено большое количество различных методов распознавания. Естественным требованием к распознающему устройству в отношении принимаемых им решений является отыскание соответствующих правил принятия решений (решающих правил) и выбор соответствующих критериев оптимальности [41].

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

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

В последние годы стало очевидным, что традиционный аппарат представления произвольных функций и сигналов (например, в виде рядов Фурье) оказывается в ряде случаев неадекватным для функций с локальными особенностями, в частности для импульсных цифровых сигналов. Соответственно в начале 90-х годов прошлого века был создан новый аппарат представления ^функций и сигналов [23, 24, 26, 32, 44, 55, 62, 63, 72] по вейвлет-базисам. Вейвлеты - это обобщенное название функций, имеющих вид коротких волновых пакетов с нулевым интегральным значением, достаточно сложной формой, локализованных по оси независимой переменной и способных к сдвигу по ней и сжатию (растяжению). Вейвлет-обработка сигналов обеспечивает возможность эффективного сжатия сигналов и их восстановления с малыми потерями информации, а также решение задач фильтрации сигналов.

Ко второму направлению относится вторая глава настоящей диссертации. В ней проведен анализ разложения Карунена-Лоэва. На множестве ортогональных преобразований введена метрика, позволяющая наилучшим образом аппроксимировать преобразование Карунена-Лоэва ортогональным преобразованием из определенного множества преобразований, например, вейвлет-пакета. Построены алгоритмы нахождения экстремальных преобразований, основанных на классическом базисе Хаара.

Из выше изложенного можно заключить, что тема диссертационной работы относится к современным технологиям извлечения полезной информации из большого набора данных. Актуальность обусловливается: 1) решением задач, связанных с синтезом нелинейных решающих правил в которых используется идеология представления класса маломерным подпространством, а, следовательно, решается задача подбора такого маломерного подпространства, то есть выбор некоторого оптимального базиса; 2) разработкой алгоритмов построения оптимальных вейвлет-базисов. Особенность диссертационного исследования заключается в охвате обоих направлений, поскольку и в первом, и во втором случае решается задача выбора оптимального базиса.

Цель и задачи исследования

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

Вытекающие из поставленной цели основные задачи:

1) исследовать эллипсоидное решающее правило, задача синтеза которого представлена в изолированной постановке;

2) рассмотреть задачу обучения для цилиндрического решающего правила как задачу идентификации на выборке подпространства;

3) провести анализ разложения Карунена - Лоэва;

4) выбрать преобразования, наилучшим образом аппроксимирующие преобразование Карунена - Лоэва;

5) разработать алгоритмы построения базисов;

6) применить на практике созданные алгоритмы.

Объекты и методы исследования

Объектами научного исследования являлись задачи обучения для эллипсоидных и цилиндрических решающих правил, преобразование Карунена-Лоэва, алгоритмы построения оптимальных базисов Хаара и Хаара-Уолша.

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

Теоретическая база исследования

Теоретические исследования основывались на разработках отечественных и зарубежных ученых в области общей теории распознавания образов и вейвлет-технологий [3, 15, 16, 20,25, 31, 61, 62, 72, 75, 77, 80, 81].

Научная новизна исследования заключается в следующем.

• Метод подпространств в распознавании образов относится к достаточно часто используемым приемам [6, 16, 31, 64, 67]. В нашей работе он реализован в виде двух решающих правил - эллипсоидного и цилиндрического, для которых решены задачи обучения. Для эллипсоидного решающего правила задача обучения рассматривалась как задача построения эллипсоида минимального объема, содержащего выборку. Известны алгоритмы ее решения [58]. К новому результату относится разработанный в диссертации алгоритм одноранговой модификации. Задача обучения для цилиндрического решающего правила рассматривалась как задача идентификации подпространства малой размерности. К новому относится то, что при ее решении доказан факт взаимооднозначного соответствия подпространства и орбиты группы невырожденных линейных преобразований. В результате получено общее решение задачи идентификации подпространства.

• Вейвлет-преобразование для сжатия сигналов применяется повсеместно в научно-технической практике [3, 24, 32, 62, 74]. К новому в нашем исследовании относится задача выбора «наилучшего» вейвлет-базиса по отношению к ансамблю сигналов. Задача выбора решена в трех постановках, как: 1) задача оптимальной перестановки; 2) задача поиска на бинарном дереве; 3) задача наилучшего разбиения множества индексов на непересекающиеся подмножества.

Практическая значимость исследования

Составлены алгоритмы, реализованные в среде VBA-Excel для обработки изображений с мелким сдвигом и разложения сигналов по экстремальным вейвлет-базисам, что позволяет сжимать и экономно хранить информацию для последующего ее экспресс-анализа в медицине, машиностроении, строительстве, геологии и других областях.

Достоверность результатов работы

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

Апробация и внедрение результатов исследования

Основные результаты диссертационной работы докладывались и обсуждались на Девятой Всероссийской школе-коллоквиуме по стохастическим методам (Ростов-на-Дону, 2002 г.), Третьем Всероссийском симпозиуме по прикладной и промышленной математике (весенняя сессия, Ростов-на-Дону, 2002 г.), методологических семинарах кафедры прикладной математики и вычислительной техники (Ростов-на-Дону, 2002, 2003, 2004 гг.), совещании руководителей и специалистов ВНИГРИуголь в области геологии и геофизики (Ростов-на-Дону, май 2004 г.).

Отдельные научные разработки диссертационного исследования используются в учебном процессе РГСУ при чтении лекций и проведении практических занятий в группах студентов специальности прикладная информатика по дисциплине «Интеллектуальные информационные системы».

Публикации

По теме диссертации опубликовано в шесть печатных работ [9, 10, 11, 33, 34, 52].

Объем и структура диссертации

Диссертация состоит из введения, трех глав, заключения, списка используемых источников (82 наименования), двух приложений, содержащих коды программ, связанных с исследованием. Материалы работы изложены на 134 страницах, включая 29 рисунков, 7 таблиц.

Основные выводы

Результаты применения метода распознавания с использованием цилиндрического решающего правила, позволяет существенно сократить вычислительную трудоемкость алгоритма для случая, когда класс описывается значительным количеством представителей (эталонов) в пространстве признаков большой размерности. К таким задачам распознавания, кроме рассмотренной в главе, относятся задача идентификации отпечатков пальцев, задача распознавания портретов, задача распознавания электроэнцефалограмм и электрокардиограмм.

Опыт использования оптимального вейвлет-базиса при обработке результатов электрического зондирования позволяет рекомендовать технологию оптимального вейвлет-анализа при большой коррелированности данных как технологию, позволяющую устранить несущественные для анализа детали (различного рода шумы, незначительные нарушения неоднородности данных, различного рода локальные ошибки измерений) и сосредоточить полезную для анализа информацию в нескольких главных коэффициентах разложения по оптимальному базису. Данный метод уступает методу, основанному на преобразовании Карунена-Лоэва, в пространствах небольшой размерности и становится хорошей альтернативой этому методу в пространствах большой размерности.

ЗАКЛЮЧЕНИЕ

Приведем основные результаты работы.

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

Для синтеза эллипсоидного и цилиндрического решающих правил разработаны эффективные алгоритмы.

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

Предложено и проанализировано три различных метода синтеза экстремального базиса, основанных на использовании вейвлета Хаара-Уолша.

В первом методе выбиралась оптимальная матрица перестановок координат. Эта задача была сведена к задаче квадратичного булевого программирования. Был разработан алгоритм ее решения, учитывающий специфику задачи, который позволяет определять локальные экстремумы целевой функции. Построенный базис состоит из двух элементов: независящий от ансамбля классический базис Хаара и матрицы перестановок координат вектора, которая зависит от ансамбля. Поскольку матрица перестановок хранится в виде двух строк индексов и вычисление перестановки не требует операций сложения и умножения этот базис является самым экономным.

Во втором методе был исследован вейвлет-пакет Хаара-Уолша. Задача заключалась в выборе оптимального базиса из вейвлет-пакета Хаара-Уолша. Для решения задачи синтеза оптимального базиса был применен метод динамического программирования, определяющий глобальный экстремум целевой функции.

Для третьего метода был применен специальный вейвлет Хаара. Задача была сведена к задаче наилучшего разбиения индексов и предложен алгоритм решения этой задачи.

В третьей главе диссертации применены методы, изложенные в первых двух главах для решения задачи распознавания и сжатия сигналов.

В результате применения метода распознавания с использованием цилиндрического решающего правила удалось существенно сократить вычислительную трудоемкость алгоритма по сравнению с корреляционным методом для случая, когда класс описывается значительным количеством представителей (эталонов) в пространстве признаков большой размерности. К таким задачам распознавания, кроме рассмотренной в главе, относятся: задача идентификации отпечатков пальцев, задача распознавания портретов, задача распознавания электроэнцефалограмм и электрокардиограмм.

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

1. Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. - М.: Наука, 1977.-224 с.

2. Андерсон Т. Статистический анализ временных рядов. М.: Мир, 1976. - 755 с.

3. Астафьева Н.М. Вейвлет-анализ: основа теории и примеры применения // Успехи физических наук. 1998. - Т. 166. - № 11. - С. 1145-1170.

4. Ахмед Н., Рао К. Ортогональные преобразования при обработке цифровых сигналов. М.: Связь, 1980. - 248 с.

5. Белман Р. Введение в теорию матриц. М.: Наука, 1976. - 351 с.

6. Белявский Г.И. Метод линейных подпространств в распознавании образов / В сб. Распознавание образов. Киев: ИК АН Украины, 1975. -С. 48-59.

7. Белявский Г.И. О применении разложения Карунена Лоэва к построению эталонов для читающих автоматов, там же. - С. 59-66.

8. Белявский Г., Буленкова Е. Синтез линейно-квадратичного решающего правила в изолированной постановке // Обозрение прикладной и промышленной математики. -1998. Т.5. - Вып. 2. - С. 201 - 202.

9. Белявский Г.И., Фоменко JI.H. Об аппроксимации преобразования Карунена-Лоэва//Обозрение прикл. и промышл. матем. 2001. - Т. 8. -Вып. 1.-С. 101.

10. Ю.Белявский Г.И., Фоменко Л.Н. Алгоритм распознавания, использующий хааровский базис // Обозрение прикл. и промышл. матем. 2001. - Т. 8 -Вып. 2. - С. 535.

11. П.Белявский Г.И., Фоменко Л.Н. Синтез оптимального конечномерного базиса Хаара // Известия вузов. Северо-Кавказский регион. Естеств.науки. 2004. - № 1. - С. 3-5.

12. Бобачев А.А., Марченко М.Н., Модин И.Н., Перваго Е.В., Урусова А.В., Шевнин В.А. Новые подходы к электрическим зондированиям горизонтально-неоднородных сред // Физика Земли. 1995. - № 12. -С. 79-90.

13. Богословский В.А., Жигалин А.Д., Хмелевской В.К. Экологическая геофизика: Учеб. Пособие. М.: Изд-во МГУ, 2000. - 256 е.: ил.

14. Вадзинский Р.Н. Справочник по вероятностным распределениям. -С.-Пб.: Наука, 2001.

15. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. -М.: Наука, 1974.-415 с.

16. Ватанабе С. Разложение Карунена Лоэва и факторный анализ / В сб. Автоматический анализ сложных изображений. - М.: Мир, 1969. -С. 276.

17. Гайдышев И. Анализ и обработка данных / Спец. справочник. С.-Пб.: Питер, 2001.

18. Геоэкологическое обследование предприятий нефтяной промышленности / Под ред. проф. В.А. Шевнина и доц. И.Н. Модина. -М.: РУССО, 1999.-511 с.

19. Горелик A.JL, Скрипкин В.А. Методы распознавания. Изд.2. М.: Высшая школа, 1984. - 219 с.

20. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов. -М.: Мир, 1988.-488 с.

21. Де Гроот М. Оптимальные статистические решения. — М.: Мир, 1974. -491 с.

22. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.-368 с.

23. Добеши И. (Ingrid Daubechies). Десять лекций по вайвлетам. Ижевск: РХД, 2001.

24. Дремин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их применение // УФН. 2001. - № 5. - С. 465-501.

25. Дуда Р., Харт П. Распознавание образов и анализ сцен: Пер.с англ. — М.: Мир, 1978.-510 с.

26. Кирушев В.А. Быстрый алгоритм сжатия изображений // Вестник молодых ученых. Прикл. матем. и механика. 1997. - № 1. - С. 4-10.

27. Киселев Н.В. Методы построения систем распознавания и классификации негауссовских сигналов. С.-Пб.: Ленинградский университет, 1986. - 186 с.

28. Ковалевский В.А. Методы оптимальных решений в распознавании изображений. -М.: Наука, 1976. 236 с.

29. Кравченко В.Ф., Рвачев В.А. «Wavelet-системы и их применение в обработке сигналов // Зарубежная радиоэлектроника. 1996. - № 4. -С.3-20.

30. Круглов В*Е., Фоменко Л.Н. Об одноранговой модификации решающего правила типа ближайшего соседа // Обозрение прикл. и промышл. матем. 2002. - Т. 9. - Вып. 1. - С. 261.

31. Круглов В.Е., Фоменко Л.Н. Об одной задаче обучения для эллипсоидного решающего правила // Известия вузов. СевероКавказский регион. Естеств.науки. 2003. - № 2. - С. 12-14.

32. Леман Э. Поверка статистических гипотез. М.: Наука, 1979. - 408 с.

33. Леман Э. Теория точечного оценивания. М.: Наука, 1991. - 448 с.

34. Мальцев А.В. Параметрическое распознавание образов по выборке фиксированного объема с погрешностями в признаках / Под ред. А.А. Грешилова. М.: Радио и связь, 1999.

35. Малоземов В.Н., Машарский С.М. Хааровские спектры дискретных сверток // Вычисл. мат. и матем. физ. 2000. - Т. 40. - № 6. - С. 954-960.

36. Марпл С. Цифровой спектральный анализ и его приложения. М., 1990.-584 с.

37. Матвеев Б.К. Электроразведка при поисках месторождений полезных ископаемых: Учебник для вузов. М.: Недра, 1982. - 375 с.

38. Миленький А.В. Классификация сигналов в условиях . неопределенности. М.: Сов. радио, 1975. - 328 с.

39. Минский М, Пейперт С. Персептроны. М.: Мир, 1973. С. 75-81.

40. Модин И.Н., Бобачев А.А. и др. Многоэлектродные электрические зондирования в условиях горизонтально-неоднородных сред / Разведочная геофизика. Обзор. АОЗТ «Геоинформмарк». Вып. 2. М., 1996.-50 с.

41. Новиков JI.B. Основы вейвлет-анализа сигналов. С.-Пб.: Изд-во СПбГТУ, 1999.

42. Петухов А.П. Введение в теорию базисов всплесков. С.-Пб.: Изд-во СПбГТУ, 1999.

43. Пытьев Ю.П. Методы математического моделирования измерительно-вычислительных систем. М.: Наука, Физматлит, 2002.

44. Розенфельд А. Распознавание и обработка изображений. М.: Мир, 1972.-230 с.

45. Сизиков B.C. Математические методы обработки результатов измерений. С.-Пб.: Политехника, 2001.

46. Справочник по специальным функциям / Под ред. М.Абрамовича и И. Стиган. М.: Наука, Физматлит, 1979 - 832 с.

47. Тихомиров М.М. Выпуклый анализ и его приложения. М.: МЦНМО, 2001.

48. Тюрин Ю.Н., Симонова Г.И. Знаковый анализ линейных моделей // Обозрение прикладной и промышленной математики. -1994. Т 1. -Вып. 2.-С. 214-278.

49. Фоменко JI.H. Задача обучения для цилиндрических решающих правил // Известия вузов. Северо-Кавказский регион. Естеств. Науки 2003. -Приложение № 11. - С. 14-21.

50. Хачай О.А., Кукса Ю.И., Хачай О.Ю. Вейвлет-анализ магнитовариационного мониторинга в сейсмоактивном районе // Геофизика. 2003. - № 5. - С. 66-69.

51. Хмелевской В.К. Геофизические методы исследования земной коры. -Дубна: Изд-во Междунар. ун-та природы, общества и человека Кн. 1. -1997; Кн. 2. - 1999.

52. Чуй К. Введение в вейвлеты. Пер. с англ. / Под ред. Жилейкина. М.: Мир, 2001.5 6. Шлезингер М.И. Взаимосвязь обучения и самообучения в распознавании образов // Кибернетика. 1968. - №2. - С. 42-57.

53. Шлезингер М.И. Математические средства обработки изображений. -Киев: Наукова думка, 1989. 198 с.

54. Шор Н. ^ Задачи минимизации матричных функций и недифференцируемая оптимизация // Обозрение прикладной и промышленной математики. 1995. - №2. - С. 113-138.

55. Электроразведка методом сопротивлений / Под ред. В.К. Хмелевского и В.А. Шевнина. М.: Изд. МГУ, 1994, - 160 с.бО.Эндрюс Г. Применение вычислительных машин для обработки изображений. М.: Энергия, 1977. - 351 с.

56. Ярославский Л.П. Введение в цифровую обработку изображений. М., 1979.-312 с.

57. АН S.T., Antoine J.-P., Gazeau J.-P., Coherent States Wavelets and their Generalizations. Springer, 2000.

58. Azhar Quddus and Moncef Gabbouj. Wavelet-based corner detection technique using optimal scale // Pattern Recognition Letters. 2002. - Vol. 23.-Is. 1-3.-Pp. 215-220.

59. Barnes E., An algorithm for separating patterns by ellipsoids // SIAM J. Alg. and Disc. Math. 1982. - № 6.

60. Bernd J. Digital Image Processing // Concepts, Algorithms and Scientific Applications. 1997. - 4th edition.

61. Bolshakov D.K., Modin I.N.,. Sapognikov B.G, Shevnin V.A. Noncontract resistivity measurements // EAGE 58th Conference. June, 1996. -Amsterdam. - The Nethrlands. - P051.

62. De Backer S, P. Scheunders P. A competitive elliptical clustering algorithm // Pattern recognition letters. 1999. - Vol. 20. - Pp. 1141-1147.

63. Deutsch Fr. Best Approximation in Inner Product Spaces. Springer, 2000.

64. Du-Ming Tsai and Cheng-Huei Chiang. Rotation-invariant pattern matching using wavelet decomposition // Pattern Recognition Letters. 2002. - Vol. 23. - Is. 1-3.-Pp. 191-201.

65. Jaideva C. Coswami, Andrew K. Chan. Fundamentals of Wavelets Theory, Algorithms, and Applications. A Willey-Interscience publication, New-York, 2002. -,314 p.

66. Mahmoud I. Khalil and Mohamed M. Bayoumi. Affine invariants for object recognition using the wavelet transform // Pattern Recognition Letters. -2002. Vol. 23. - Is. 1-3. - Pp. 57-72.

67. Meyer Y. Wavelets and Operators. Cambridge University Press, 1993.

68. Nuggehally S. Javant and Peter Noll. Digital Coding of Waveforms. -Principles and Applications to Speech and Video. Prentice-Hall, Englewood Cliffs, New Jersey, 1984.

69. Ronald R. Coifman, Yves Meyer, Mladen Victor Wickerhouzer. Wavelet analysis and signal processing, In Mary Beth Ruskai ey al. editors, Wavelet and Their Applications, Jones and Barlett, Boston, 1992. Pp. 153-178.

70. Shor N., Berezovsski O. New algorithms for constructing optimal circumscribed and inscribed ellipsoids // Optim. Methods Software. 1992. -Vol. l.-Pp. 283-289.

71. Sonka M., Hlavac V., Boyle R. Image Processing, Analysis, and Machine Vision. PWS Publishing, 1999. - 770 p.

72. Special issue on theory and application of filter banks and wavelet transforms // New York: Inst, of electrical a. electronics engineers, 1998. -Vol. 46. Nr. 4. - Pp. 829-1188.

73. Special issue on wavelet and time-frequency analysis / Torresani Bruno, spec. ed. Woodbury (N.Y.): Amer. inst. of physics, 1998. - J. of math. Physics. - Vol. 39. - Nr 8. - Pp. 3949-4248.

74. Struzic Zbigniew R. Oversampling the Haar wavelet transform / Struzic Z. R. Amsterdam, 2001. - 19 p.

75. Walter G.G., Xiaoping Shen. Wavelets and Other Orthogonal Systems. -Second Edition, Chapman & Hall/CRC, 2001.

76. Yu Tao, Ernest C.M. Lam and Yuan Y. Tang. Feature extraction using wavelet and fractal // Pattern Recognition Letters. 2001. - Vol. 22. - Is. 3-4. -Pp. 271-287.