Содержание к диссертации
Введение
1 Анализ существующих методов обнаружения объектов искусственного происхождения 22
1.1 Постановка задачи обнаружения 22
1.1.1 Основные положения 22
1.1.2 Понятие характеристических точек объекта обнаружения 27
1.1.3 Понятие априорной неопределенности в задачах обнаружения 36
1.2 Методы обнаружения объектов искусственного происхождения 37
1.2.1 Пороговые методы обнаружения 37
1.2.2 Методы дистантного сопоставления с эталоном 39
1.2.3 Контурные методы обнаружения 43
1.2.4 Согласованная фильтрация 48
1.2.5 Текстурные методы обнаружения 51
1.3 Требования к разрабатываемому методу обнаружения объектов искусственного происхождения 56
1.4 Выводы 59
2 Разработка метода обнаружения объектов искусственного происхождения в условиях неопределенности исходных данных средствами вейвлет-анализа 60
2.1 Постановка задачи 60
2.2 Основные положения вейвлет-анализа 61
2.3 Предварительная обработка данных 69
2.3.1 Постановка задачи предварительной обработки данных 69
2.3.2 Выделение вейвлет-максимумов 69
2.3.3 Адаптивная вейвлет-фильтрация в условиях неопределенности исходных данных 74
2.3.4 Пространственная и многомасштабная сегментация сигналов 83
2.4 Выделение векторов характеристических признаков сегментов 89
2.5 Выводы 99
3 Разработка алгоритмов обнаружения объектов искусственного происхождения методами вейвлет-анализа 101
3.1 Анализ требований к алгоритмам обнаружения и первичной классификации объектов искусственного происхождения 101
3.2 Особенности быстрых алгоритмов вейвлет-преобразования 103
3.3 Базовый комплексный алгоритм обнаружения и первичной классификации объектов искусственного происхождения 104
3.3.1 Алгоритм адаптивной декомпозиции/реконструкции анализируемых сигналов в оптимальных вейвлет-базисах 104
3.3.2 Алгоритм адаптивной вейвлет-фильтрации оптимальными порогами 109
3.3.3 Алгоритм многомасштабной сегментации сигналов 110
3.3.4 Алгоритм выделения масштабных и локальных векторов характеристических вейвлет-признаков 113
3.3.5 Комплексный алгоритм обнаружении объектов искусственного происхождения методами вейвлет-анализа 116
3.4 Теоретическая оценка вычислительной трудоемкости 120
3.5 Оптимизация разработанных быстрых алгоритмов обнаружения и первичной классификации методами параллельных вычислений 130
3.6 Синтез оптимальных конфигураций аппаратных средств поддержки вычислительного процесса 13 7
3.7 Выводы .147
4 Программная реализация и результаты экспериментальных исследований оптимизированных алгоритмов обнаружения объектов искусственного происхождения методами вейвлет-анализа 149
4.1 Основные требования к программной модели разработанного метода и методика проведения экспериментальных исследований 149
4.2 Постановка задачи обнаружения с позиции экспериментального исследования предложенного метода 150
4.3 Методика проведения экспериментов 153
4.4 Результаты экспериментальных исследований разработанной программной модели обнаружения объектов искусственного происхождения методами вейвлет-анализа 158
4.4.1 Оценка зависимости типа базисных вейвлет-функций, используемых для представления данных, от особенностей анализируемых сигналов 158
4.4.2 Оценка зависимости значений порога вейвлет-фильтрации по мягкой и жесткой схемам от параметров анализируемого сигнала 161
4.4.3 Оценка зависимости количества ненулевых коэффициентов от значения порога вейвлет-фильтрации и уровня шумов 166
4.4.4 Оценка зависимости вероятности обнаружения объектов от особенностей сигналов и параметров выделения значимых вейвлет-коэффициентов 169
4.5 Применение предложенной методики для решения задачи обнаружения на реальных данных 172
4.6 Выводы 179
Заключение 182
Библиографический список использованных источников
- Понятие характеристических точек объекта обнаружения
- Предварительная обработка данных
- Особенности быстрых алгоритмов вейвлет-преобразования
- Результаты экспериментальных исследований разработанной программной модели обнаружения объектов искусственного происхождения методами вейвлет-анализа
Введение к работе
Задача совершенствования методов цифровой обработки сигналов, в общем, и методов обнаружения объектов искусственного происхождения, в частности, является одной из важнейших во многих отраслях науки и техники: гидролокации, сейсморазведке, обработке изображений, видео и звука, медицине и т.п.
Актуальность проблемы обуславливается расширением сферы применения методов обнаружения, внедрением новой теоретической и алгоритмической базы, использованием новых методов оптимизации на уровне аппаратных и программных средств поддержки вычислительного процесса.
В диссертации рассматриваются теоретические проблемы решения задач обнаружения и первичной классификации объектов искусственного происхождения методами вейвлет-анализа
Актуальность диссертации подтверждается использованием полученных результатов в х/д НИР работах кафедры Вычислительной техники Технологического института Южного федерального университета в г. Таганроге: 12232 «Разработка программной оболочки формирования подводного рельефа по гидроакустическим измерениям и информационно-аналитического комплекса борьбы за живучесть», х/д НИР 12234 «Программные средства формирования подводного рельефа по гидроакустическим измерениям и поиска навигационных опасностей естественного и искусственного происхождения», х/д НИР 12236 «Разработка комплекта программной документации, отладка и проведение стендовых испытаний программного комплекса формирования трехмерного изображения морского дна и поиска навигационных опасностей естественного и искусственного происхождения по данным ГАСМ», х/д НИР 12238 «Разработка и исследование систем автоматизации проектирования
проблемно-ориентированных вычислительных устройств на базе ПЛИС», в совместных проектах с ОАО НИИ Системотехники, а также применением их в учебном процессе.
Диссертация посвящена постановке и решению задач локализации, обнаружения и первичной классификации объектов искусственного происхождения при неопределенности исходных данных методами вейвлет-анализа. В ней решена комплексная задача цифровой обработки сигналов и изображений, включающая в себя поиск, анализ и классификацию объектов искусственного происхождения. При этом проводится обнаружение как объектов, присутствующих в базе эталонов, так и обозначенных только своими характерными признаками.
До последнего времени, одним из основных способов анализа первичной или вторичной информации, отражающей состояние интересующей исследователя среды, являлось визуальное наблюдение. Однако с ростом производительности вычислительных систем сбора и обработки данных возрастает роль автоматизированных методов выделения и классификации разного рода объектов. При применении таких систем делается попытка заменить человека автоматом для ответа на некоторые вопросы с учетом требований к скорости и точности решения поставленной задачи, а также, если такая замена диктуется невозможностью выполнения заданных требований человеком.
Важный научный интерес и практическое значение в таком случае представляет собой проблема построения вычислителей, способных выделять и классифицировать изображения объектов. Одной из малоисследованных задач является задача построения системы, способной производить автоматическое выделение двумерных и трехмерных объектов из окружающей среды с последующей их классификацией при наличии неопределенности в исходных данных. Нечеткость данных, ровно как
неполнота их, требуют применения нетривиальных методов анализа. При этом необходимо создание систем, способных синтезировать определенный интуитивный и логический подход к анализу ситуации и принимать решения относительно поставленной задачи.
Таким образом, проблема построения систем, оперирующих методами выделения и первичной классификации искусственных объектов с учетом наличия неопределенности при представлении исходных данных, является актуальной и востребованной.
В настоящее время известно множество методов обнаружения объектов: пороговые, дистантные, контурные, текстурные, фрактальные, методы фильтрации и т.д. [6$, 82, 87, 100, 102]. Основными недостатками этих методов являются: отсутствие инвариантности относительно масштабного и пространственного сдвига, низкая помехоустойчивость, отсутствие быстрых вычислительных алгоритмов и возможности их параллельной реализации.
Любой реальный объект характеризуется наличием многочисленных искажений вследствие присутствия шумов различной природы, неопределенности геометрического и масштабного положения, погрешностей съема информации, что чрезвычайно осложняет решение указанной выше задачи. Исходя из этого, используемый метод должен принимать во внимание описанные выше особенности анализируемых сигналов и не содержать указанные недостатки вышеперечисленных методов обнаружения и первичной классификации реальных объектов различной физической природы.
Проведенное исследование состава и возможностей современных методов цифровой обработки сигналов показало, что наиболее перспективным направлением в этом случае является вейвлет-анализ.
Отдельные методы и алгоритмы данной теории позволяют решать практически все выделенные выше подзадачи обнаружения, однако, только в
разрозненном виде. Их объединение дает ключ к созданию универсальной системы, которая может проводить обнаружение и комплексный анализ объектов искусственного происхождения. Проблема эффективного применения комплекса методов и алгоритмов вейвлет-анализа к решению такой нестандартной и неординарной задачи как задача обнаружения и классификации объектов, оптимизация вычислительного процесса и разработка эффективных средств аппаратной поддержки для них является на сегодняшний день одной из самых сложных и до конца не проработанных проблем.
Использование аппарата вейвлет-анализа позволяет быстро и эффективно решить задачу шумоподавления и получить инвариантное относительно пространственного и масштабного сдвига представление сигнала, характеризующее его физическую природу. Положенные в основу разработанного метода обнаружения быстрые алгоритмы вейвлет-анализа дают возможность оптимизировать вычислительный процесс методами параллельных вычислений, а используемые процедуры адаптации к физической природе обрабатываемых сигналов повышают эффективность предложенных алгоритмов и расширяют сферу их применения.
Впервые основные идеи вейвлет-анализа были сформулированы в трудах Морле и Гроссмана [ПО], опубликованных в журнале «SIAM. J. of Math. Anal.» в 1984 году. В основе их теории положены ортогональные кусочно-постоянные функции Хаара, предложенные последним в 1910 [2].
Основанными направлениями использования вейвлет-анализа до настоящего времени являлись: решение задач гармонического анализа шумоподавления и сжатия данных в сейсмологии, медицине, экономическом анализе, а также решение отдельных задач цифровой обработки изображений и звука.
В диссертационной работе предложен метод использования средств теории вейвлет-анализа в задаче обнаружения объектов искусственного происхождения в условиях неопределенности исходных данных. Предложен комплексный подход к обнаружению и первичной классификации объектов различной физической природы, объединяющий все преимущества быстрых алгоритмов вейвлет-анализа с оптимизацией последних методами параллельных вычислений. Разработан комплексный алгоритм, соединяющий как существующие, так и предложенные в данной работе процедуры первичной обработки, выделения векторов характеристических признаков и классификации объектов. Теоретически и экспериментально доказана эффективность разработанного алгоритма, приведены результаты его практического применения и даны рекомендации к дальнейшему использованию.
Основные положения, выносимые на защиту
На защиту выносится:
метод обнаружения объектов искусственного происхождения в условиях неопределенности исходных данных средствами вейвлет-анализа;
алгоритмы и программная реализация решения задач адаптивной фильтрации, многомасштабной сегментации, выделения признаков и первичной классификации обнаруженных объектов;
реализация аппаратных и программных средств поддержки предложенных алгоритмов методами параллельных вычислений;
результаты применения предложенного подхода для решения практической задачи поиска навигационных опасностей по данным гидроакустического сканирования.
Основные научные результаты.
разработан метод обнаружения объектов искусственного происхождения в условиях неопределенности исходных данных средствами вейвлет-анализа;
разработан алгоритм адаптивной вейвлет-фильтрации, отличающийся от существующих алгоритмов возможностью адаптации к параметрам сигналов, одновременным выделением максимумов вейвлет-коэффициентов, локальных перепадов и компактного кода анализируемого сигнала;
разработан алгоритм многомасштабной сегментации, базирующийся на анализе динамики изменения кривых вейвлет-максимумов, полученных на этапе фильтрации. Особенностью данного алгоритма также является возможность одновременного выделения векторов локальных и масштабных характеристических признаков сегментов;
разработан быстродействующий комплексный алгоритм обнаружения и первичной классификации объектов искусственного происхождения, включающий в себя предварительную обработку данных, фильтрацию, сегментацию, выделение компактного кода данных и векторов характеристических признаков, а также первичную классификацию обнаруженных объектов;
предложен способ параллельной реализации разработанного комплексного алгоритма обнаружения на базе программных и аппаратных средств поддержки вычислительного процесса;
решена задача поиска навигационных опасностей по данным гидроакустического сканирования.
Объектом исследования в диссертационной работе являются высокопроизводительные алгоритмы и методы обнаружения
объектов искусственного происхождения в условиях неопределенности исходных данных, методы цифровой обработки сигналов, методы вейвлет-анализа, методы оптимизации вычислений, а также программные и аппаратные средства поддержки вычислительного процесса. Целью работы в теоретическом плане являются:
разработка метода первичной обработки, анализа исследуемых данных, обнаружения и первичной классификации объектов искусственного происхождения в условиях неопределенности средствами вейвлет-анализа;
повышение эффективности разработанных алгоритмов введением процедур адаптации к природе анализируемых данных и их оптимизация методами параллельных вычислений;
разработка оптимальной конфигурации аппаратных средств поддержки вычислений разработанных алгоритмов комплексного решения задачи обнаружения и первичной классификации объектов искусственного происхождения.
Целью работы в практическом плане является:
разработка программной реализации разработанных алгоритмов;
разработка программной модели обнаружителя и поиск по ней наилучших параметров адаптации к конкретным объектам различной физической природы,
апробация и внедрение теоретических и практических результатов исследований.
Основными задачами работы являлись следующие:
- провести анализ существующих методов обнаружения объектов
искусственного происхождения;
доказать возможность и целесообразность применения методов вейвлет-анализа для решения задач обнаружения и классификации объектов различной физической природы;
доказать возможность адаптации и оптимизации предложенных алгоритмов вейвлет-обработки сигналов с точки зрения их аппаратной и программной реализации.
разработать и теоретически обосновать алгоритмы: адаптивного вейвлет разложения/восстановления анализируемых сигналов, фильтрации, многомасштабной сегментации, выделения векторов характеристических признаков и особенностей исследуемых данных, локализации объектов искусственного происхождения и их первичной классификации;
разработать оптимальную конфигурацию аппаратных и программных средств поддержки вычислений;
практически проверить теоретически полученные результаты путем использования их для решения задачи обнаружения объектов искусственного происхождения.
Методы выполнения исследований.
Для теоретических исследований использовались методы теории вейвлет-анализа, цифровой обработки сигналов, численные методы, методы математического моделирования, методы параллельных вычислений, распознавания образов и решения задач классификации.
Кроме того, проводились экспериментальные исследования на модельных и реальных объектах и сигналах, а также апробация разработанных алгоритмов на ЭВМ.
Практическая ценность и рекомендации по применению. Результаты исследований, описанных в диссертации, находят применение для решения комплексной задачи
обработки сигналов и обнаружения объектов искусственного происхождения в условиях неопределенности исходных данных. Комплексное исследование объектов различной физической природы средствами вейвлет-анализа, метод построения адаптивного обнаружителя и параллельная реализация на уровне аппаратуры позволяют в короткий срок поставить и решить задачу обнаружения, комплексной обработки и компактного хранения сигналов.
Все это влечет за собой повышение эффективности и качества работы систем обнаружения и первичной классификации путем:
введения концептуально новых и эффективных методов обработки данных;
использования комплексных методов обработки, позволяющих одновременно достигать несколько целей;
упрощения аппаратных и программных средств поддержки в результате применения быстрых вычислительных алгоритмов;
сокращения временных затрат на общую обработку и возможность работы в реальном времени, благодаря наличию оптимизированных алгоритмов и оптимальных конфигураций аппаратной базы обнаружителя.
Достоверность разработанных методики и алгоритмов была проверена при решении следующих задач:
постановка задачи обнаружения объектов для гидроакустических данных;
поиск и локализация объектов, отсутствующих в базе, но имеющих определенные характеристические признаки;
комплексная обработка сигналов, включающая адаптивное шумоподавление, анализ многомасштабной геометрии, выделение компактного кода хранения базы эталонов и обнаруженных объектов;
- первичная классификация реальных объектов.
Полученные модели и методы целесообразно использовать при построении автоматизированных систем целеуказания, сопровождения объектов, обнаружения навигационных опасностей или артефактов неизвестной природы в анализируемых сигналах при реализации отдельных алгоритмов разработанного метода в составе других комплексных приложениях цифровой обработки сигналов.
Апробация работы.
Результаты работы докладывались и обсуждались на Международных и Всероссийских конференциях, в том числе на:
научно-техническом семинаре с международным участием «Микропроцессорные системы мониторинга, диагностики и управления сложными техническими объектами, организационными техническими системами и комплексами». -Таганрог, 2004 г
VIII Всероссийской научной конференции студентов и аспирантов. «Техническая кибернетика, радиоэлектроника и системы управления». - Таганрог, 2004.
L Научно-технической конференции профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ. -Таганрог, 2004.
III Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление». - Таганрог, 2005.
Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в науке, инженерии и управлении». - Таганрог, 2005.
Всероссийской научной конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления». - Таганрог, 2006.
Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в науке, инженерии и управлении» - Таганрог, 2006.
Результаты работы используются в учебном процессе в дисциплине «Проектирование проблемно-ориентированных вычислительных систем» и представлены в виде методических указаний к выполнению лабораторной работы «Реализация быстрого вейвлет-преобразования на цифровых сигнальных процессорах семейства SHARC ADSP-2106x».
Публикации.
Результаты, полученные в диссертации, нашли отражение в 14 печатных работах, среди них 10 статей.
Структура работы
Материал основной части диссертационной работы изложен на 222 страницах машинописного текста. Диссертация состоит из введения, четырех разделов, списка литературы из 135 наименований, содержит 5 таблиц, 48 рисунков и 2 приложений на 26 листах.
Содержание работы.
Первый раздел работы посвящен аналитическому обзору существующих подходов к решению задачи обнаружения объектов искусственного происхождения и носит постановочный характер. В разделе вводятся такие опорные понятия для решаемой задачи обнаружения как понятие объекта искусственного происхождения, априорной неопределенности и векторов характеристических признаков. В нем проводится подробное исследование большинства стандартных методов обнаружения с целью выявления их основных возможностей, особенностей реализации, а также основных
достоинств и недостатков. Раздел завершается сравнительной характеристикой всех рассмотренных методов и обоснованием необходимости создания комплексного метода обнаружения объектов искусственного происхождения в условиях неопределенности исходных данных, в котором отсутствуют указанные недостатки.
Второй раздел является ядром теоретического обоснования предложенного метода обнаружения. Он содержит основы самой теории вейвлет-анализа, теоретические предпосылки создания отдельных элементов метода, а также его алгоритмический и методологический базис в целом. В данном разделе проводится подробное сравнение возможностей методов и алгоритмов теории вейвлет-анализа. На основании этого делается вывод о целесообразности применения вейвлет-методов цифровой обработки сигналов для решения задачи обнаружения объектов искусственного происхождения. Большое внимание в разделе уделено вопросам объединения преимуществ отдельных алгоритмов вейвлет-анализа с целью поиска новых путей их использования и создания метода обнаружения объектов искусственного происхождения. В частности, делается вывод о многозначности результатов работы большинства алгоритмов вейвлет-обработки сигналов. Это дает возможность сокращения общего количества этапов разрабатываемого метода посредством универсализации используемых для обнаружения признаков. В данном разделе определяется и теоретически обосновывается общее количество этапов метода, а именно: очистка сигнала от шумов, разделения его на зоны повышенного интереса, а также первичная классификация локализованных объектов. Далее проводится подробное теоретическое описание каждой составляющей синтезированного метода в отдельности. В частности, обосновывается необходимость адаптивного решения задачи фильтрации в целях устранения неопределенности, связанной с присутствием шумов различной физической
природы в исходной форме анализируемого сигнала. В разделе также показано, что полученные после фильтрации коэффициенты определяют не только чистую форму сигнала, но и дополнительно производят компактный код данных, определяют локальные вейвлет-максимумы, точки перепадов анализируемого сигнала и даже часть локальных признаков обнаруживаемых объектов. Вследствие этого синтезирован улучшенный алгоритм шумоподавления, путем развития стандартных алгоритмов вейвлет-фильтрации. Высокая эффективность данного алгоритма была достигнута посредством введения процедуры расчета адаптивного порога, минимизирующего риски потерь данных, а также введением дополнительной возможности одновременного выделения максимумов вейвлет-коэффициентов, локальных перепадов и компактного кода анализируемого сигнала. Следующим рассмотренным и теоретически обоснованным этапом метода обнаружения является этап многомасштабной сегментации анализируемого сигнала. Данная процедура позволяет разделять сигнал на так называемые зоны повышенного интереса, вероятность обнаружения объектов искусственного происхождения в которых близка к единице. В разделе был выполнен подробный анализ существующих теоретических предпосылок к развернутому исследованию данных на многих масштабах представления. Как результат такой работы, была предложена и теоретически обоснована процедура многомасштабной сегментации обрабатываемого сигнала, базирующаяся на анализе динамики изменения кривых вейвлет-максимумов, полученных на этапе фильтрации. Ее особенностью также является возможность одновременного выделения векторов локальных и масштабных характеристических признаков сегментов с обновлением их динамики для каждого достигнутого уровня разложения. Последним рассмотренным этапом обнаружения является непосредственно этап первичной классификации обнаруженных объектов. В разделе приводится
анализ алгоритмов классификации, на основании которого были сделаны выводы о целесообразности применения рассмотренных методов для определения типопринадлежности обнаруженного объекта. Кроме того, в разделе рассмотрены случаи принятия решения об обнаружении объектов искусственного происхождения в случае отсутствия их эталонной формы в базе искомых объектов. Данная ситуация охватывает класс задач обнаружения объектов, определенных только рядом своих характерных признаков и является частным случаем поставленной комплексной задачи обнаружения. Раздел завершается выводами по проделанной работе и синтезом схемы метода обнаружения, включающей в себя все разработанные и обоснованные ранее этапы.
Третий раздел диссертационной работы посвящен алгоритмической составляющей разработанного метода обнаружения объектов искусственного происхождения и способам реализации вычислительного процесса на программном и аппаратном уровне. Введением в данный раздел является анализ требований к алгоритмам обнаружения, определяющих общие черты вычислительного процесса и ход обнаружения в целом. Далее, в разделе последовательно рассмотрены следующие этапы предложенного метода обнаружения с точки зрения их алгоритмической реализации: быстрые алгоритмы адаптивной декомпозиции/реконструкции сигнала в базисе вейвлет-функций; алгоритм адаптивной вейвлет-фильтрации с оптимальными порогами; алгоритм многомасштабной сегментации анализируемого сигнала; алгоритм выделения векторов масштабных локальных и глобальных признаков сегментов; алгоритм первичной классификации обнаруженных объектов, присутствующих в базе эталонов и алгоритм обнаружения объектов. В представленном материале рассмотрены структурные схемы данных алгоритмов и особенности их реализации. На базе разработанных алгоритмов далее проводится синтез комплексного
алгоритма обнаружения и первичной классификации объектов искусственного происхождения методами вейвлет-анализа. Большое внимание уделено организации вычислительного процесса, при котором включение процедур может вестись последовательным или конвейерным способом, то есть по мере продвижения по уровням декомпозиции сигнала. Далее, в разделе рассматриваются методы повышения эффективности и оптимизации вычислительного процесса. На основании проведенного выше анализа особенностей структуры и операционного базиса алгоритмов вейвлет-анализа делается вывод о целесообразности реализации предложенной процедуры обнаружения методами параллельных вычислений. Как продолжение данной работы выполняется анализ современных средств аппаратной реализации алгоритмов цифровой обработки сигналов, применимых для решения поставленной задачи. В результате чего сделан вывод о целесообразности применения современных процессоров цифровой обработки сигналов, объединенных в вычислители специального вида - многопроцессорные комплексы. В качестве дополнительного преимущества выделенного множества аппаратных средств поддержки выделяется полное соответствие операционного состава синтезированных быстрых алгоритмов операционному базису процессоров, а также возможность наиболее эффективного использования естественного параллелизма алгоритмов вейвлет-анализа. Результатом проведенной в данном направлении работы является предложенная совокупность последовательных и параллельных схем реализации комплексного алгоритма обнаружения на базе многопроцессорных комплексов цифровой обработки сигналов. В данном разделе проводится теоретический анализ быстродействия и вычислительной трудоемкости разработанного комплексного алгоритма обнаружения, а также определяются зависимости характеристик алгоритма от параметров разложения, свойств анализируемого
сигнала и аналитического базиса вейвлет-функций. Приводятся формулы расчета основных характеристик комплексного алгоритма обнаружения, и осуществляется сравнительный анализ различных реализаций последнего. Проведенный анализ вычислительной трудоемкости и быстродействия алгоритмического состава предложенного метода обнаружения позволил провести сравнение параметров работы алгоритмов для последовательного и параллельного вариантов для случаев реализации на ЭВМ и многопроцессорных комплексах. Данный раздел завершается выводами относительно разработанного комплексного алгоритма, его быстродействия и вычислительной трудоемкости, а также анализом полученных характеристик оптимизированной алгоритмической базы предложенного метода.
В четвертом разделе приводятся результаты экспериментального исследования и практического применения разработанной методики обнаружения. Введением в раздел является анализ требований к программной реализации предложенной методики, а также постановка задачи обнаружения с позиции его экспериментального исследования. Далее предлагается методика проведения экспериментов, регламентирующая основные этапы исследования, структуру и связи оцениваемых параметров, строение программной модели системы, для проведения наиболее полного исследовании, а также определяется набор модельных данных для проведения экспериментов. На основании экспериментального исследования проводится анализ предложенного метода и приводятся результаты оценки зависимостей перечисленных ниже параметров от характеристик анализируемых сигналов, а именно: зависимость типа используемых для представления данных базисных вейвлет-функций от особенностей сигналов, зависимость значений порога вейвлет-фильтрации по мягкой и жесткой схемам от уровня шума, зависимость количества ненулевых коэффициентов от значения порога вейвлет-фильтрации и уровня шумов, зависимость
вероятности обнаружения объектов от особенностей сигналов и параметров выделения значимых вейвлет-коэффициентов. В результате проведения экспериментального исследования предложенного метода проводится выделение наиболее значимых параметров алгоритмов, определяются их оптимальные значения и ограничиваются диапазоны их изменения. После этого, решена реальная задача по данным гидроакустического сканирования акватории с затонувшим теплоходом «Адмирал Нахимов», в ходе которой проверена работоспособность предложенного метода и получены желаемые результаты. В завершении главы проводится систематизация полученных результатов, и делаются выводы относительно проделанной работы.
В заключении излагаются основные результаты диссертационной работы.
Понятие характеристических точек объекта обнаружения
Характеристическими точками объекта будем называть множество точек {Ch(} распределенных в п мерном пространстве признаков объекта, позволяющих выделить качественное или количественное различие объектов внутри одного класса или между классами.
В качестве характеристических признаков объекта в каждой конкретной ситуации можно понимать различные физические (и другие) параметры, выделенные искусственно в результате специальной его обработки, или естественные, априори присущие объекту. К искусственным параметрам объекта можно отнести гистограммы распределения значений амплитуд или пространственные спектры частот. К естественным признакам можно отнести геометрические характеристики контура объекта или его текстуру.
Первыми рассматриваемыми характеристиками объектов являются их геометрические характеристики. В качестве основных из них можно выделить площадь объекта и его положение [84]. Площадь объекта можно определить как А = J jb(x, y)dxdy, (1.6) о где b(x,y) - характеристическая функция объекта, которая принимает значения 1 внутри объекта О и 0 во всех точках, находящихся вне его.
Положение объекта также является важным признаком, позволяющим не только оценить сам объект, но и определить «направление» алгоритма его анализа (например, проведение некоторой оценки вдоль его центральной оси).
Характеристической точкой объекта в таком случае будет его геометрический центр - центр масс (хс,ус). Центр масс является такой точкой объекта, в которой можно сконцентрировать всю массу объекта без изменения его первого момента относительно любой оси. Первый момент относительно оси х в двумерном случае рассчитывается как: хс J \b(x,y)dxdy = j Jxb(x,y)dxdy. (1.7) о 0 Первый момент относительно оси у: Ус { \b(x, y)dxdy = J jyb(x, y)dxdy. (1.8) о о Непосредственные величины (хс,ус) находятся из предположения, что площадь объекта не нулевая.
Далее, одними из простейших отличительных свойств можно считать «яркостные» признаки объекта. Наиболее важным признаком такого класса, например, в теории обработки изображений, можно считать светлоту объекта [68]. Светлота выражается через такие признаки объекта, как, например, его спектральную интенсивность излучения. Измерение яркостных признаков объекта ведется либо в отдельных точках объекта, либо в их окрестностях.
Например, можно выделить характерную среднюю амплитуду сигнала в некоторой окрестности (2Z +1) х (2L +1) характеристической точки объекта с координатами (xch,ych) [68]. Л) = [і/(2 + 1)2]І %8(х + т,у + п). (1.9) m=-Ln=-L
Такое выражение, как уже указывалось выше, является одним из самых простых и применимых, однако можно использовать и другие признаки, полученные, например, при переходе к новым яркостным признакам, выполнив линейные (нелинейные) обратимые или необратимые преобразования. Измерение яркостных характеристических точек объекта является особо важным процессом при маркировке (интерпретации) или выделении полученных объектов. Если ввести представление дискретного сигнала - массива чисел s0(x,y,i) как реализацию двумерного случайного процесса, описываемого совместными распределениями вероятностей, то полученные распределения вероятностей значений амплитуд сигнала можно использовать для создания некоторого класса признаков объекта - гистограммных признаков [29].
То есть распределение вероятностей значений амплитуд сигнала первого порядка можно определить как P(b) = VT{S0 (Х, у) = Ъ], где О b Jmax -1 - уровни квантования. Распределение частот первого порядка, оценивающее P(b) :P{b) = N{b)lМ, где М - полное число точек объекта в окне с центром (хс, ус), a N(b) - число элементов в окне, имеющих уровень Ь. Форма гистограммы распределения частот дает много сведений об объекте. Для того, чтобы охарактеризовать гистограмму распределения вводят следующие параметры.
Предварительная обработка данных
В условиях неопределенности исходной информации чрезвычайно важным является решение задачи подготовки данных в виде, приемлемом для дальнейшего исследования.
Для этого необходимо не только провести очистку сигнала от шума, априори присутствующего во всех типах исходных данных, но и определить участки наибольшего интереса, вероятность обнаружения искомых объектов внутри границ которых, близка к единице, а также выделить характеристические признаки сигналов внутри этих участков.
Таким образом, можно выделить следующие этапы предварительной обработки данных: - очистка исходного сигнала от шума; - выделение наиболее значимых коэффициентов разложения, достаточных для восстановления сигнала с заданной точностью; - пространственная и масштабная сегментация сигналов с выделением областей наибольшего интереса; - определение векторов характеристических признаков выделенных сегментов для дальнейших этапов обнаружения.
Следует также учесть, что для повышения эффективности обнаружения, все приведенные выше этапы предварительной обработки данных должны проводиться одновременно, то есть являться многими целями одной теоретической и алгоритмической базы.
Согласно проведенному в п. 2.2 исследованию, представление сигналов в форме многоуровневой вейвлет-декомпозиции позволяет проводить раздельный анализ каждого пространственного и частотного диапазона.
Часть коэффициентов вейвлет-преобразования при этом чрезвычайно важна, а часть может быть опущена ввиду их малого вклада в формирование свойств сигнала. Такими коэффициентами априори являются коэффициенты малой амплитуды, представляющие собой мелкомасштабную реакцию сигнала на вейвлет-преобразование. Эта часть коэффициентов может быть отброшена.
Оставшиеся коэффициенты большой амплитуды полностью определяют свойства сигнала и позволяют восстановить его первоначальную форму путем реконструкции обратным вейвлет-преобразованием. В [117] доказывается, что максимумы модуля вейвлет-преобразования определяют полное прямое и обратное представление сигнала в вейвлет-базисе.
Следовательно, возможно восстановление сигнала f(t) с ограниченным спектром по нерегулярной выборке коэффициентов Wf{u, х) с погрешностью не более 10"2 [121]. Это обстоятельство также позволяет заключить, что ограниченное множество максимумов вейвлет-преобразования также выгодно использовать для хранения и передачи обрабатываемых данных.
Кроме того, оставляемая часть коэффициентов имеет больший смысл, нежели просто материал для обратного восстановления. Как следует из теории вейвлет-анализа, использование такой части разложения на каждом уровне позволяет достичь следующих целей: 1. Компактное представление информации вейвлет-разложения; 2. Исключение влияния шумовых компонент на формирование сигналов; 3. Локализация перепадов амплитуды и частоты сигналов, а также разделение его на сегменты; 4. Измерение локальной гладкости пространственной формы сигналов; 5. Определение характеристических точек сегментов.
Все перечисленные выше задачи предлагается решать через выделение максимумов коэффициентов вейвлет-преобразования и подсчет отдельных параметров на их основе.
Синтезируем метод, позволяющий осуществлять адаптивное выделение вейвлет-максимумов на каждом уровне разложения и проводить анализ сигнала по их локальным значениям и характеру изменения в окрестностях особых точек. Как уже говорилось в п. 2.2, коэффициенты вейвлет-преобразования фактически измеряют изменения сигнала /(f) в окрестностях анализируемых точек и с размерами, пропорциональными масштабному параметру s.
Тогда, под вейвлет-максимумом будем понимать строгий максимум в правой и левой окрестностях анализируемой точки ujp с размерами, пропорциональными s К кр ] К \ЧР - х\и К WP I VJ кР +1] (2-! 8 где dj - соответствующий вейвлет-коэффициент, полученный в результате дискретного вейвлет-преобразования.
На пространственно-масштабной плоскости (u,s), получаемой как результат многоуровневого вейвлет-разложения, выделим последовательности точек, то есть кривые максимумов s(u), по всем масштабам разложения, сходящиеся к абсциссам характеристических точек анализируемого сигнала. В данном случае, кривые максимумов могут являться как непрерывными, так и иметь разрывы на плоскости (u,s).
Особенности быстрых алгоритмов вейвлет-преобразования
При работе с сигналами различной физической природы чрезвычайно важным является решение задачи их разделения на области наибольшего интереса, вероятность обнаружения искомого объекта внутри которых близка к единице. То есть проведение пространственной сегментации с заданными параметрами в автоматическом режиме.
Однако локализация сегментов в пространстве является не единственным средством выделения «областей наибольшего интереса». В соответствии со способностью вейвлет-анализа к масштабной и частотной локализации свойств и особенностей сигнала синтезируем метод дополнительного деления данных на масштабные и частотные поддиапазоны.
Способность аппарата вейвлет-анализа к масштабному и частотному разделению сигналов следует непосредственно из свойств вейвлет-преобразования. Частотно-временное разрешение аналитического вейвлет-преобразования Wf(u,s) = (f,i//us\ в свою очередь зависит от частотно-временной протяженности так называемых вейвлет-атомов y/us [109].
Энергетическая протяженность частотно-временного вейвлет-атома соответствует прямоугольнику с центром в (U,TJ/S) и размерами sat по времени и ja/s по частоте [122]. Площадь прямоугольника остается постоянной при любом масштабе, однако разрешение по времени и по частоте зависит от s (см. рис. 2.10.а). Более мелкие масштабы уменьшают временную протяженность, но увеличивают частотный носитель, сдвигая его в направлении высоких частот. Последовательности таких прямоугольников Гейзенберга, образованных вейвлет-функциями посредством сдвигов и изменения масштабного коэффициента, покрывают всю частотно-временную плоскость. Вейвлет-преобразование сигнала переводит сигнал множество значений f(t) в пространство время-масштаб (частота) как показано на рис. 2.10.6. sa, fa s sa, \ f XT Щ a) 6) Рис. 2.10 Примеры частотно-временных атомов а - прямоугольники Гейзенберга для двух вейвлетов разного масштаба, б - покрытие частотно-временной плоскости прямоугольниками вейвлет базиса.
Каждое разложение анализируемого сигнала f(t) в базисе вейвлетов определенного масштаба создает некоторое функциональное пространство VJ [48]. Дерево разложений сигнала по нескольким уровням соответственно создает ограниченное семейство функциональных подпространств fj\j&z, каждый элемент которого - представление сигнала в соответствующем масштабном поддиапазоне [29]. Последовательность образования элементов множества fJ jJeZ образуют иерархию вложенных подпространств ... с V j с... с Vі сГсГ сК2с... с Vj с..., (2.32) отличающихся друг от друга перемасштабированием независимых переменных s = aJ.
Переход анализируемой функции /(/) вверх или вниз по иерархии осуществляется масштабным сдвигом его представления в базисе вейвлет-функций соответствующего уровня ДО є Vі о f(ajt) є Vj+l, f{t) є Vі о f(t/aJ) є VjA. (2.33) Так как каждое подпространство из Y)jez образуется разложением исходной функции в базисе масштабирующих функций q us, то f{t) на каждом уровне декомпозиции представляется в виде низкочастотной аппроксимации исходного сигнала.
Однако, как следует из приведенной выше теории вейвлет-анализа, переход функции от одного уровня иерархии (2.32) к другому неминуемо влечет за собой потерю или приобретение некоторого количества информации. При переходе вниз по иерархии к менее детальным масштабам, происходит потеря высокочастотных компонент сигнала, то есть элементов, по масштабу меньших а1. Для образования более детальных подпространств требуется добавление дополнительной высокочастотной части сигала.
Результаты экспериментальных исследований разработанной программной модели обнаружения объектов искусственного происхождения методами вейвлет-анализа
В качестве основной схемы адаптивной процедуры декомпозиции и реконструкции анализируемого сигнала в базисах вейвлет-функций предлагается использование стандартной процедуры вейвлет-разложения, расширенной дополнительными модулями адаптивного выбора оптимального вейвлет-базиса и определения максимальной глубины разложения.
Процедуру определения оптимального вейвлет-базиса следует строить на основании оценки, приведенной в п. 2.3. Ее использование позволит повысить эффективность предложенного метода обнаружения, привнеся дополнительную адаптивность, хотя это не является обязательным элементом разработанного алгоритма для таких ситуаций, когда определенный минимальный словарь базисов уже создан и существуют определенные указания по применению его элементов, выбранных эвристическими методами.
Выбор максимального уровня разложения предлагается осуществлять на основании полученных экспериментальным путем эвристических данных об оптимальной глубине декомпозиции. Адаптивное определение предела разложения целесообразно применять в тех случаях, когда необходимо не столько обнаружить в сигнале отдельные эталонные объекты, сколько выделить сегменты сигнала, где наблюдаются отдельные нарушения регулярности, превышающие установленные пределы.
То есть ожидается присутствие неоднородностей неизвестной природы, которые предстоит проанализировать и обработать.
Телом алгоритма является процедура вейвлет-разложения анализируемого сигнала в выбранном базисе вейвлет-функций по полной или частичной схеме Мала, основанная на серии циклических сверток, один шаг которых описан в п. 2.2.
Структурная схема работы алгоритма адаптивной декомпозиции и восстановления анализируемого сигнала в оптимальном вейвлет-базисе представлена на рис. 3.1.
На первом этапе оцениваются заданные априори параметры разложения и делаются установки для работы всего алгоритма. Здесь так же выделяется подмножество предпочтительных базисов вейвлет-функций. Далее, проводится оценка выделенного подмножества с точки зрения минимизации погрешности разложения/восстановления анализируемого сигнала в данном базисе и соответствия характеристик материнского вейвлета физической сути анализируемого сигнала.
Однако, как уже говорилось выше, данный этап может быть упрощен путем задания всех установленных параметров разложения напрямую, непосредственно перед работой алгоритма.
На следующем этапе работы алгоритма проводится серия разложений в базисе выбранных вейвлет-функций путем применения циклических сверток полной или частичной схемы декомпозиции Мала с коэффициентами фильтров разложения, полученных при выборе оптимального базиса вейвлет-представления сигнала или заданных заранее.
На каждом цикле декомпозиции проводится анализ детализирующих компонент с точки зрения целесообразности перехода на следующий уровень. В случае необходимости, последовательность сверток повторяется, иначе следует переход к формированию результатов работы алгоритма.
Результатом работы является совокупность аппроксимирующих и детализирующих компонент сигнала, распределенных по уровням декомпозиции так, как показано на рис. 3.2.
Следует отметить, что при разложении сигнала по частичному и полному алгоритму Малла, вне зависимости от количества уровней декомпозиции, увеличения отведенного для представления сигнала объема памяти не происходит. Данное утверждение совершенно логично и следует из замены частей сигнала, предназначенных для разложения, результирующими коэффициентами, длина которых равна половине исходной.
Данный факт является существенным преимуществом перед многими другими алгоритмами представления сигналов в базисах, где необходимым является введение дополнительных резервов памяти для хранения преобразованных данных.
Здесь, под СА(І) И с)(і) понимаются коэффициенты аппроксимации и детализации г-го уровня декомпозиции, a cAA(i), cDA(i), cAD(i) и cDL i) -их коэффициенты разложения на уровне / +1.
При такой процедуре формирования и хранения результирующих значений достигается экономия не только требуемого объема памяти, но и снижение времени доступа. Последний факт обусловлен использованием фиксированных значений адресов доступа к компонентам разложения, напрямую рассчитываемых исходя из значения глубины декомпозиции, а также их фиксированным размером.
