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

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

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ЦИФРОВОЙ ФИЛЬТРАЦИИ И ОБРАБОТКИ ИЗОБРАЖЕНИЙ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (промышленность)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Новосибирск 2004

Работа выполнена в Новосибирском государственном техническом университете

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

профессор Воскобойников Юрий Евгеньевич

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

Спектор Александр Аншелевич;

кандидат технических наук, доцент

Зиновьев Виталий Николаевич.

Ведущая организация - ФГУП Сибирский научно-исследовательский

институт метрологии, г. Новосибирск

Защита состоится «16» марта 2004 г. в 10 часов на заседании диссертационного совета Д 212.173.05 при Новосибирском государственном техническом университете по адресу:

630092, г.Новосибирск, пр. К.Маркса, 20.

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

Автореферат разослан «13» февраля_2004 г.

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

д.т.н., профессор

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

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

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

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

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

Задачу преобразования зашумленных данных, можно разбить на два самостоятельных этапа.

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

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

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

В диссертации автором решены следующие задачи

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

2. Проведено исследование метрологических показателей разработанных алгоритмов и их сравнение с известными алгоритмами.

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

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

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

Моделирование и вычислительный эксперимент проводились с использованием математических пакетов (Matchcad, MatLab для предварительных исследований и проверки гипотез) и пакета программ, реализованных на С+ + (основной вычислительный эксперимент).

Научная новизна диссертационного исследования заключается.

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

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

3. Разработанные автором алгоритмы обобщены для обработки многомерных полей и изображений.

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

На защиту выносятся:

1. Созданные методы и алгоритмы нелинейной фильтрации изображений и многомерных сигналов: алгоритм взвешенной медианной фильтрации с рекурсивным формированием апертуры, пространственно взвешенный алгоритм.

2. Разработанный метод представления и хранения векторной графики с помощью сглаживающих сплайнов.

3. Алгоритмы выбора параметра сглаживания: основанный на методе L-кривой и по заданной ширине аппаратной функции сплайна в условиях многозначной кривой произвольной формы.

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

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

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

Апробация работы. Основные результаты и положения работы обсуждались на следующих конференциях:

1. Новосибирская межвузовская научно-студенческая конференция «Интеллектуальный потенциал Сибири» НГАСУ 18-19апреля 1999г. «Цифровая фильтрация векторных полей» (Диплом I степени).

2. Дни науки НГТУ 2000 (лучший доклад).

3. Региональная научно-техническая конференция студентов, аспирантов, молодых ученых(НТИ2001); НГТУ 11-13 декабря 2001 года «Алгоритм фильтрации с использованием дополнительной информации» (диплом II степени).

4. 59 научно-техническая конференция НГАСУ 2-4 апреля 2002 года «Алгоритм фильтрации с использованием дополнительной информации о корреляции сигнала».

5. 59 научно-техническая конференция НГАСУ 2-4 апреля 2002 года «Алгоритм векторизации изображений с использованием сглаживающих сплайнов».

6. 60 научно-техническая конференция НГАСУ 8-9 апреля 2003 года «Анализ структуры изображения модифицированным медианным фильтром».

7. 60 научно-техническая конференция НГАСУ 8-9 апреля 2003 года «Аппроксимация изолиний сложных изображений сглаживающими сплайнами». Некоторые результаты обсуждались на II и III международных отраслевых научно-технических выставках «Гидрометеорология-человеку», проходивших в Санкт-Петербурге (комплекс ЛенЭкспо) в мае 2000 • и апреле 2003 года.

Публикации. По теме диссертации опубликовано 8 печатных работ, из них 4 - в центральных журналах, 2 работы в зарубежных изданиях.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырёх глав, заключения, библиографии, приложений. Она содержит 125 страниц основного текста, 60 рисунков, 3 таблицы, приложение.

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

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

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

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

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

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

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

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

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

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

Модель 2. Аддитивный шум. Этот вид искажения возникает, например, в результате нестабильности характеристик различных технических устройств, влияния электромагнитных помех на усилительные каскады и аналоговые линии

связи. Влияние такого шума моделируется путем добавления к значению интенсивности каждой точки X,j (в случае векторного RGB сигнал — к каждому из цветовых компонент) шумовой составляющей Z,j с заданным распределением и чи-еловыми характеристиками. Поэтому каждая точка такого изображения содержит помимо полезного сигнала некоторую шумовую составляющую.

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

Обратимся к одному из алгоритмов поиска медианной величины. Значение ут п вычисляемое этим алгоритмом, определяется из условия

где Х)с , X, , Х} - значения исходного изображения, попавшие в апертуру, N -количество точек в окне фильтрации.

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

= xj*,-Xj\-ехр(-I=I..N,

(2)

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

(3)

Такой медианный фильтр назовем «медианный фильтр со взвешенной метрикой» (МФВМ).

Оценка эффективности алгоритмов сглаживания выполнялась на модельных изображениях путем анализа гистограмм, сравнения среднеквадратического отклонения (СКО) отфильтрованного зашумленного изображения от «эталонного»:

где СД - размеры изображения, х,^- точки отфильтрованного изображения, Зс,;

- точки эталонного изображения и коэффициента «гладкости», вычисленного по формуле:

(5)

Коэффициент 0 изменяется от 0 (в каждой точке происходит изменение яркости от минимального до максимального значений) до 1 - при полностью однородном изображении.

СКО и коэффициент 0 усреднялись по данным выборки из 50 случаев реализации воздействия шумовых искажений на модельное изображение.

Сравнение гистограмм, визуальный анализ результатов фильтрации, а также анализ зависимости и СКО от параметра проведенные в работе, показывают, что модифицированный фильтр обладает лучшей способностью удалять шумы, чем обычный медианный фильтр. Например, на рис.1 и рис.2, показан типичный вид зависимостей 0 (рис. 1) и СКО (рис.2) от параметра П. На графиках можно выделить три характерных участка: 1 — характеризует неустойчивый режим функционирования алгоритма; 2- «оптимальные» значения параметра сглаживания; 3- фильтр вырождается в обычный медианный. Как показывает

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

Выбор параметра

предлагается осуществлять на основе метода L-кривой,

использующегося в литературе для выбора параметра регуляризации при решении плохообусловленных СЛАУ.

Для этого строится кривая, по оси абсцисс откладывается величина невязки: а

по оси ординат: 1о§(0д) (img~ исходное изображение, /т^д-результат фильтрации изображения МФВМ), Типичная траектория такой кривой для шума модели 1 показана на рис.3. Точка максимальной кривизны кривой (участок 2) соответствует оценке оптимального параметра

Для улучшения фильтрующих свойств медианного фильтра в работе вводится рекурсивный режим формирования апертуры фильтра:

'Л,* = 1...г.ЛГ + 1 N-2 ,

4- л,.-, лг ,0<гй——, 1=1 N. (6)

*,= !. • ^ 'к =

/Ы

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

Такой фильтр назовем «медианный фильтр с рекурсивным формированием апертуры» (МФРФА). Комбинированный фильтр, использующий взвешенную метрику и рекурсивное формирование апертуры, назовем «МФВМ с рекурсивным формированием апертуры» (МФВМсРФА). Рекурсивность значительно улучшает сглаживание шумов, но накладывает некоторые ограничения на параметры настройки: глубина рекурсии большая 0.5 неизбежно приведет к искажению фронтов сигнала, а также возможна ситуация, когда сигнал в окне фильтра станет корневым, не изменяющимся при повторной фильтрации.

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

МФВМ, МФРФА и МФВМсРФА обеспечивают эффективное сглаживание сигналов в различных технических задачах. Например, есть класс задач, в которых разные обаасти обрабатываемого изображения должны быть сглажены в различной степени в соответствии с введенной априори системой приоритетов. В качестве примера такой задачи рассмотрим исходное изображение, приведенное на рис.4. Области с индексом 1 должны быть сглажены максимально, а искажение областей с индексом 4 недопустимо.

Рис 4 Модельное изображение Рис.5.Результат фильтрации

алгоритмом с дифференцированным сглаживанием

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

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

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

Проведенный в конце первой главы сравнительный анализ эффективности известных ранее (фильтр Винера, медианный, интервальный ФСС) и разработанных в диссертационной работе алгоритмов показывает, что в случае действия импульсных шумов (модель 1) предпочтительнее применять нелинейную фильтрацию (например, МФВМ). В случае распределенного аддитивного шума невысокой интенсивности (модель 2) результаты применения как нелинейных, так и линейных алгоритмов сравнимы. В случае аддитивного шума высокой интенсивности нелинейные алгоритмы теряют свои преимущества, приближаясь по своим характеристикам к линейной фильтрации.

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

Все разработанные алгоритмы обобщены для обработки векторных полей.

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

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

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

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

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

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

В работе рассматриваются два алгоритма выбора а: а) выбор на основе метода Ь-кривой; б) новый,метод, основный на задании ширины аппаратной функции сплайна.

Ь-кривой называют кривую, точки которой задаю!ся координатами

>7 . -»2 6

xL(a) = Цн*)-^ «1 ; yL(a) = In J(S"„ (X)fdx,

(7)

где y(x)~ зашумлеииые исходные данные, Sa(x)~ значение сглаживающего сплайна в узлах х, [а,Ь] - интервал построения сплайна.

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

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

Аппаратная» функция ha{t) сплайна характеризует систематическую ошибку сглаживания и дифференцирования: чем меньше "ширина" функции ha(t), тем меньше систематическая ошибка сглаживания. В качестве числовой характеристики аппаратной функции принимается ее ширина

(8)

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

Введем вторую характеристику, которую можно интерпретировать

как коэффициент передачи дисперсии погрешности в дисперсию случайной составляющей ошибки сглаживания:

а\=К(а)-а1^ (9)

Сформулируем задачу синтеза сглаживающего сплайна в виде следующей вариационной задачи:

¡пГ/Г(а)' при - <5(а) <8„р.

Решение этой вариационной задачи - единственный корень нелинейного уравнения

8{а) = 5„р (10)

Вычислительный эксперимент, результаты которого приведены в конце второй главы, показывает большую точность процедуры выбора а через точностные характеристики сплайна в сравнении с методом L-кривой. Следует также отметить, что для решения нелинейного уравнения (10) не требуется задание измеренных значений у, что позволяет априори вычислять значение параметра а.

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

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

- осуществлять преобразование растрового изображения в векторный формат;

- эффективно хранить и отображать векторные данные;

- проводить фильтрацию и сглаживание векторных данных при наличии минимальной априорной информации.

Третья глава диссертационной работы посвящена описанию программной реализации разработанных алгоритмов. Приводятся описание возможностей и интерфейса разработанных программ: a) "filterscan" - программа для проведения вычислительного эксперимента по нелинейной фильтрации изображений; б) "piton" программа для непараметрического представления произвольной кривой сглаживающими сплайнами. Интерфейс программ позволяет проводить визуальное и метрологическое сравнение свойств и характеристик предложенных алгоритмов, а их реализация на языке высокого уровня позволяет оценить реальное быстродействие и сделать вывод о возможности применения того или иного алгоритма в системах реального времени.

Модули программ написаны на языке С и легко интегрируются в пакеты программ для решения реальных практических задач.

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

Первая часть посвящена описанию решения задачи и программного обеспечения (ПО) для обработки метеорологической карты облачности. Данные сканирования атмосферы метеорологическим радиолокатором применяются для обеспечения безопасности полетов авиации, а также предупреждения ЧС, связанных с неблагоприятными явлениями природы в зоне атмосферных фронтов и условиях высокой грозовой активности. Результат сканирования атмосферы представляет собой изображение, каждая точка которого характеризует плотность среды в пространстве. Информационная ценность деталей изображения возрастает пропорционально плотности среды, или, соответственно, яркости точек изображения. В соответствии с условием задачи, области с небольшой яркостью (низкая плотность) допускают схематическое отображение, в то время как области с высокой яркостью, соответствующие высокой плотности среды в данной точке пространства, необходимо отображать с большей точностью восстановления.

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

векторный формат. Фильтрация и преобразование осуществляется методами и алгоритмами, разработанными в рамках данной диссертационной работы* На рис.7 показано изображение, полученное с метеолокатора, рис.8, демонстрирует результат обработки разработанным нелинейным фильтром,- рис.9 демонстрирует результат преобразования изолиний в векторный - формат и представления их сглаживающими сплайнами с выбором параметра а на основе метода L-кривой и по заданной ширине аппаратной функции сплайна:

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

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

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

Для исключения указанных недостатков в диссергационной. работе используется МФВМсРФА; В процессе вычислительного эксперимента проекционные данные фантома Шешта-Логана (Shepp-Logan), посчитанные для 60 углов с 721 параллельными лучами в каждой проекции, искажались 5% шумом с равномерным распределением. Восстановление производилось алгоритмом свертки с ядром типа 1/2?. Восстановленное изображение (рис.10) подвергалось обработке МФВМсРФА с апертурой 3 (окно 7x7=49 точек), дополненной 21 точками выходного сигнала в предыдущих положениях окна (рис.П)

Рис. 10. Восстановленный Рис. 11. Восстановленный <

фантом фантом после фильтрации

МФВМсРФА.

0.04 0.039 0.036 0,034 0.032 0,03

X

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

В заключении перечислены основные результаты и изложены выводы по диссертационной работе.

Предл КомО ФСС

Рис.13. Сравнительная эффективность алгоритмов фильтрации восстановленного фантома (СКО)

В приложении представлены акты о внедрении результатов диссертационной работы в гидрометеорологии (ЗСУГМС) и томографии (Институт Автоматики и Электрометрии СО РАН).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

3. Разработан алгоритм фильтрации с дифференцированным сглаживанием областей с различной информационной ценностью.

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

5. Разработанные автором алгоритмы фильтрации обобщены для обработки многомерных полей и изображений.

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

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

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

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Колкер А.Б. Взвешенные и рекурсивные алгоритмы векторной медианной фильтрации. Сборник научных трудов НГТУ. Новосибирск: Изд-во НГТУ ,2000-Вып.5(22).

2. Колкер А.Б. Аппроксимация изолиний изображений параметрическими сплайнами. Труды 12-й Байкальской международной конференции «Методы оптимизации и их приложения», Иркутск: Изд-во ИСЭМ СО РАН,2001с.

3. Колкер А.Б. Алгоритм фильтрации изображений с использованием дополнительной информации. НАУКА. ТЕХНИКА. ИННОВАЦИИ. // Региональная научная конференция студентов, аспирантов и молодых ученых: мат. конф. в 5-ти частях. Новосибирск: изд-во НГТУ, 2001. Часть1.-125с.

4. Воскобойников Ю.Е. Колкер А.Б. Адаптивный алгоритм фильтрации изображений и преобразования их в векторный формат.// Автометрия 2002, том 38,№4

5. Yu.E. Voskoboinikov and A.B. Kolker Adaptive filtering algorithm and conversion of images to a vector й>гтаг.(Адаптивная фильтрация и преобразование изображений в векторный формат) // Optoelectronics, Instrumentation and Data Processing №4,2002

6. Колкер А.Б. Алгоритм фильтрации изображений с использованием дополнительной информации о корреляции. // 60я научно-техническая конференция НГАСУ. мат. конф. Новосибирск: изд-во НГАСУ, 2003 ч.1

7. Воскобойннков Ю.Е. Колкер А.Б. Аппроксимация изолиний сглаживающими сплайнами. // Автометрия №4 2003

8. Yu.E. Voskoboinikov and A.B. Kolker Approximation of Image Isolines by Smoothing Splines. (Сплайн-аппроксимация изолиний изображений)// Optoelectronics, Instrumentation and Data Processing v.39 №4,2003

Соискатель

Подписано в печать3 .02.2004 г. Формат 84x60x1/16 Бумага офсетная. Тираж 100 экз. Печ.л.1,25 Заказ № 63 Отпечатано в типографии Новосибирского государственного технического университета 630092,г. Новосибирск, пр.К.Маркса,20

í-380 2

ВВЕДЕНИЕ

ГЛАВА 1. НЕЛИНЕЙНЫЕ АЛГОРИТМЫ ФИЛЬТРАЦИИ КОНТРАСТНЫХ ИЗОБРАЖЕНИЙ

1.1.Класс изображений

1.2.Модификация медианной процедуры

1.3.Комбинированная фильтрация с дифференцированным сглаживанием областей с различной информационной ценностью

1.4.Пространственно - взвешенная фильтрация изображений с квантованием по уровню

1.5.Фильтрация изображений с использованием дополнительной информации о корреляции

1.6. Обобщение алгоритмов для обработки векторных полей

1.7.Сравнительный анализ линейной и нелинейной фильтрации

Выводы

ГЛАВА 2. ПРЕДСТАЛЕНИЕ РАСТРОВЫХ ИЗОБРАЖЕНИЙ В ВЕКТОРНОМ ФОРМАТЕ

2.1. Растровая и векторная графика

2.2 Алгоритмы фрагментации и построения изолиний

2.3. Интерполяционный кубический сплайн

2.4.Сглаживающий кубический сплайн

2.5.Двумерная интерполяция с параметризацией исходной кривой

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

2.7.Гладкое сопряжение сглаживающих сплайнов

2.8.Выбор квазиоптимального параметра сглаживания

2.8.1 .Выбор а через критерий L-кривой

2.8.2.Выбор параметра а по заданным точностным характеристикам сглаживающего сплайна

2.8.3.Результаты вычислительного эксперимента 91 Выводы

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ 99 3.1. Программа для проведения вычислительного эксперимента по фильтрации и сглаживанию изображений "Filterscan" 100 3.2 Программа для непараметрического построения произвольной кривой "Piton" 103 Вывод

ГЛАВА 4. РЕШЕНИЕ ПРИКЛАДНЫХ ЗАДАЧ

4.1. Решение задачи обработки метеорологической карты облачности

4.1.1 Постановка задачи

4.1.2 Программное обеспечение для решения задачи обработки метеорологической карты облачности

4.1.3 Результаты обработки метеорологической карты облачности

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

4.2.1 Постановка задачи

4.2.2 Нелинейная фильтрация восстановленных изображений

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

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

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

Задачу преобразования зашумленных данных можно разбить на два самостоятельных этапа.

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

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

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

1) Разработка новых и адаптация известных методов фильтрации изображений к условиям задачи преобразования информации.

2) Проведено исследование метрологических показателей разработанных алгоритмов и их сравнение с известными алгоритмами.

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

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

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

Моделирование и вычислительный эксперимент проводились с использованием математических пакетов (MatchCad, MatLab для предварительных исследований и проверки гипотез) и авторского пакета программ, реализованных на С++ (основной вычислительный эксперимент).

Научная новизна диссертационного исследования заключается:

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

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

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

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

На защиту выносятся:

1. Созданные методы и алгоритмы нелинейной фильтрации изображений и многомерных сигналов: алгоритм взвешенной медианной фильтрации с рекурсивным формированием апертуры, пространственно взвешенный алгоритм.

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

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

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

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

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

Апробация работы. Основные результаты и положения работы обсуждались на следующих конференциях:

1. Новосибирская межвузовская научно-студенческая конференция «Интеллектуальный потенциал Сибири» НГАСУ 18-19апреля 1999г. «Цифровая фильтрация векторных полей» (Диплом I степени).

2. Дни науки НГТУ 2000 (лучший доклад).

3. Региональная научно-техническая конференция студентов, аспирантов, молодых ученых(НТИ2001); НГТУ 11-13 декабря 2001 года «Алгоритм фильтрации с использованием дополнительной информации» (диплом II степени).

4. 59 научно-техническая конференция НГАСУ 2-4 апреля 2002 года «Алгоритм фильтрации с использованием дополнительной информации о корреляции сигнала».

5. 59 научно-техническая конференция НГАСУ 2-4 апреля 2002 года «Алгоритм векторизации изображений с использованием сглаживающих сплайнов».

6. 60 научно-техническая конференция НГАСУ 8-9 апреля 2003 года «Анализ структуры изображения модифицированным медианным фильтром».

7. 60 научно-техническая конференция НГАСУ 8-9 апреля 2003 года «Аппроксимация изолиний сложных изображений сглаживающими сплайнами».

Некоторые результаты обсуждались на II и III международных отраслевых научно-технических выставках «Гидрометеорология-человеку», проходивших в Санкт-Петербурге (комплекс ЛенЭкспо) в мае 2000 и апреле 2003 года.

Публикации. По теме диссертации опубликовано 8 печатных работ, из них 4 - в центральных журналах, 2 работы в зарубежных изданиях.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырёх глав, заключения, библиографии, приложений. Она содержит 125 страниц основного текста, 60 рисунков, 3 таблицы.

Вывод

Разработанный пакет программ позволяет исследовать основные свойства и характеристики разработанных алгоритмов. Для запуска пакета необходима ЭВМ не менее Pentium II с объемом оперативной памяти не менее 32Мб. Интерфейс программ позволяет проводить визуальное и метрологическое сравнение свойств и характеристик алгоритмов. Реализация алгоритмов на языке высокого уровня позволяет оценить их реальное быстродействие и сделать вывод о возможности применения в системах реального времени. Модули программ написаны на языке С++ и легко интегрируются в пакеты программ для решения реальных практических задач.

Глава 4

РЕШЕНИЕ ПРИКЛАДНЫХ ЗАДАЧ 4.1. Решение задачи обработки метеорологической карты облачности 4.1.1. Постановка задачи

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

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

Поэтому, можно сформулировать следующие задачи:

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

• преобразования данных в векторный формат, их отображения для удобства наложения на другие информационные слои, интеграции в геоинформационные системы, а также для функционирования систем слежения.

4.1.2. Программное обеспечение для решения задачи обработки метеорологической карты облачности

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

Разработанные алгоритмы и программные модули внедрены в информационную систему комплексного мониторинга состояния * окружающей среды, разрабатываемую Западно-Сибирским Метеоагенством совместно с Западно-Сибирским Гидрометеоцентром, Управлением МЧС, Территориальным Управлением автодорог, Центром Мониторинга Среды.

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

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

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

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

Комплекс программ реализован на базе операционных систем OS2 и Linux. Программные модули системы, в основном, разработаны на языке С++. Фильтрация и преобразование данных осуществляется модулями программ filterscan и Piton (Глава 3, §3.1), интегрированными в систему.

4.1.3. Результаты обработки метеорологической карты облачности

На рис.4.1. показан пример изображения, полученного с метеорологической радиолокационной станции. Более темные области соответствуют более плотным и, следовательно, более опасным регионам, в то время как более светлые область менее опасны и могут быть сглажены в большей степени. На рис.4.2 показан результат фильтрации растровых данных рис.4.1 адаптивным алгоритмом с дифференцированным сглаживанием областей с различной информационной ценностью (глава 1, §1.3). На следующем этапе происходит преобразование в векторный формат (рис.4.3), используя алгоритмы, описанные в главе 2 (§2.2). Восстановление осуществляется сглаживающими кубическими сплайнами.

Рис. 4.1. Исходное изображение, полученное с радиолокационной станции

Рис.4.2. Изображение на выходе алгоритма фильтрации данных

Рис.4.3. Представление изолиний атмосферного поля сглаживающими кубическими сплайнами

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

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

Преобразование данных в векторный формат также позволяет осуществлять эффективное сжатие данных. Так изображение, показанное на рис.4.1 в исходном варианте имеет размер 520x520 точек, что соответствует массиву размером 270400 байт. Применяя схему сжатия без потерь

LZW, к изображению после уменьшения информационной избыточности алгоритмами фильтрации (рис.4.2.), удается обеспечить коэффициент сжа-^ тия 36 и упаковать в изображение в 7523 байт. Для представления того же объема данных в векторном формате необходимо отобразить 53 замкнутых изолинии, для этого требуется задать 845 пар значений координат (х,у). С учетом представления одной пары (х,у) 3 байтами (максимальный размер поля 4096x4096 точек) и необходимости отвести еще 53 двухбайтных слова под служебную информацию, изображение можно закодировать при помощи 2641 байт информации, что соответствует коэффициенту сжатия 102, что почти втрое большее значение, чем в случае сжатия растровых данных. Очевидно, что такой коэффициент сжатия возможен лишь ценой необратимых потерь тонких деталей изображения, что характерно для любого алгоритма сжатия с потерями. Эффективность в таком случае * достигается путем оптимизации «информационной избыточности», когда менее важные и малоинформативные детали изображения отображаются схематически, в то время как во фрагменты изображения с высокой информационной ценностью по возможности вносятся наименьшие искажения.

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

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

4.2.1. Постановка задачи

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

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

Для решения этой проблемы в работе [17] был предложен следующий подход: для восстановления изображения по проекционным данным использовать алгоритмы с малой величиной систематической ошибки, например, алгоритм [20], а затем выполнить фильтрацию восстановленного изображения. К сожалению, использование комбинированного алгоритма, представляющего собой последовательность процедур медианной фильтрации и интервального скользящего среднего [17], не позволяет в полной мере сохранять резкие перепады уровня изображения из-за совпадения спектров случайной ошибки восстановления и «контрастных элементов» восстанавливаемого изображения. Это приводит к искажению формы фронтов и контрастных объектов.

4.2.2. Нелинейная фильтрация восстановленных изображений

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

В процессе вычислительного эксперимента проекционные данные фантома Шеппа-Логана (Shepp-Logan) (рис.4.8), посчитанные для 60 углов с 721 параллельными лучами в каждой проекции, искажались 5% шумом с равномерным распределением. Восстановление производилось алгоритмом свертки с ядром -у [20]. Результат восстановления фантома по z зашумленным данным показан на рис.4.9.

Восстановленное изображение подвергается фильтрации взвешенно-рекурсивным фильтром с апертурой 3 (окно 7x7=49 точек), дополненной 21 точками выходного сигнала в предыдущих положениях окна. Взвешенная норма используется для компенсации излишней инерционности фильтра, вызванной наличием в окне фильтрации точек выходного сигнала в предыдущие моменты и равна Q=-600 (поскольку характеристики изображения обычно нормируются аппаратурой томографа, в реальных системах коэффициент Q может быть также подобран априори по данным тестовых фантомов), что приводит к незначительной «дефокусировке» фронтов изображения.

В качестве характеристики точности оценивались два параметра: средняя гладкость изображения 0 (Глава 1 (1.7)) и среднеквадратическое отклонение:

СКО = м s i (x,j-*j)2 (4Л)

NM где: N- количество точек изображения по вертикали, М -количество точек изображения по горизонтали, x,j точки изображения после фильтрации, хij- точки эталонного изображения.

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

Сравнение СКО и 0 изображений, отфильтрованных различными алгоритмами (рис.4.6, рис.4.7) показывает, что предложенный взвешенный медианный фильтр с рекурсивным формированием апертуры обеспечивает наилучшую гладкость и наименьшую среднеквадратическую ошибку из рассмотренных алгоритмов.

Рис.4.4. Профили фантомов: 1- восстановленного без фильтрации, 2- эталонного. 3-восстановленного, после фильтрации МФВМсРФА

Срез 205 линии

Рис 4.5. Сравнительный анализ свойств фильтров: {1 {эталонное изображение; {2} рез-т фильтрации комбинированным фильтром [17] (см.рис.4.13); {3 {-предложенным взвешенным рекурсивным медианным фильтром (см.рис.4.10)

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

0,993 0,992 0,991 0,99 0,989 0,988 0,987 0.986 0,985

Предл. Комб. ФСС

Рис.4.6. Гладкость & результатов фильтрации различными алгоритмами (для исх. восстановленного изображения ©=0.9196 , для эталонного- 0=0.9935)

0,042 0,04 0,038 0,036 0,034 0,032 0,03

Предл. Комб. ФСС.

Рис.4.7. СКО результатов фильтрации различными алгоритмами (для исх. восстановленного изображения СЖО=0,0623)

Рис.4 8 Фантом

Рис.4,10. МФВМсРФА

Рис.4.9. Восстановленный фантом

Рис 4.11. Обычный медианный фильтр

Рис.4.12. Интервальный ФСС

Рис.4.13. Комбинированный фильтр [2|

ЗАКЛЮЧЕНИЕ

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

• нелинейная фильтрация растровых данных;

• преобразование и хранение данных в векторном формате с применением сглаживающих сплайнов.

Для решения задач первого этапа в диссертационной работе:

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

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

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

5) Разработан алгоритм фильтрации с дифференцированным сглаживанием областей с различной информационной ценностью.

6) Проведен сравнительный анализ эффективности нелинейных и линейного (фильтра Винера) алгоритмов в условиях действия помех с различными уровнем шума и его распределением.

7) Разработанные автором алгоритмы фильтрации обобщены для обработки многомерных полей и изображений.

8) Разработано программное обеспечение для фильтрации данных предложенными алгоритмами.

Для решения задач второго этапа преобразования в диссертационной работе:

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

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

3) Сделаны выводы об эффективности применения и численной реализации алгоритмов поиска оптимального значения параметра сглаживания а посредством критерия L-кривой и через ширину аппаратной функции сплайна.

4) Разработанные алгоритмы позволяют выполнять фильтрацию изображений в векторном формате.

5) Разработано программное обеспечение, реализующее все предложенные алгоритмы.

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

Предложенный автором комплекс алгоритмов преобразования и отображения данных позволяет с высокой точностью выполнить преобразование данных в векторный формат. Это позволило решить техническую задачу передачи, обработки, анализа и хранения результатов сканирования атмосферы метеорологическим локатором. Разработанные алгоритмы обработки данных внедрены в Западно-Сибирском УГМС, что также подтверждается актом внедрения.

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

1. Банковский Ю.М., Галактионов В.А.,Михайлова Т.Н. Графор. Графическое расширение фортрана.-М.:Наука. Главная редакция физико-математической литературы, 1985

2. Беликова Т.П. Некоторые методы цифрового препарирования изображений // Цифровая обработка сигналов и ее применение.- М.:Наука, 1981. С.87-98.

3. Беликова Т.П., Ярославский Л.П. Использование адаптивных амплитудных преобразований для препарирования изображений // Вопросы радиоэлектроники, сер. Общетехническая. 1974, вып. 14. - С.88 - 98

4. Белявцев В.Г., Воскобойников Ю.Е. Алгоритмы фильтрации изображений с адаптацией размеров апертуры.//Автометрия №3 1998 с 18-27

5. Березовский М.В. Выбор параметра сглаживания сплайнов при отсутствии априорной информации о погрешности задания функции. Иркутск: Труды XII Байкальской международной конференции "Методы оптимизации и их приложения", том 4 2001

6. Боресков А.В., Шишкин Е.В. Шишкина Г.Е. Компьютерная графика: первое знакомство. Москва, Финансы и статистика, 1996 -176с.

7. Боресков А.В., Зайцев А.А., Шишкин Е.В. Начала компьютерной графики. -Москва, Диалог-МИФИ, 1993. 138с.

8. Ю.Бронников А. В., Воскобойников Ю. Е. Комбинированные алгоритмы нелинейной фильтрации зашумленных сигналов и изображений.// Автометрия №1 1990 с21-26

9. Быстрые алгоритмы в цифровой обработке изображений / Под ред. Т.С. Хуанга. М.:Радил и связь 1984.

10. Василенко Г.И. Теория восстановления сигналов. М.: Сов. радио. 1979.-272 с.

11. Воскобойников Ю.Е, Преображенский Н.Г. Седельников А.И. Математическая обработка эксперимента в молекулярной газодинамике.- Новосибирск: Наука, 1984.

12. Воскобойников Ю.Е. Выбор параметра регуляризации алгоритмов решения СЛАУ при неизвестном уровне погрешности задания исходных данных.// Иркутск: Труды XII Байкальской международной конференции "Методы оптимизации и их приложения", том 4 2001

13. Воскобойников Ю.Е. Оценивание оптимального параметра регуляри-зирующих алгоритмов восстановления изображений //Автометрия. 1995 №3. С. 68.

14. Воскобойников Ю.Е. Частотный подход к оценке точности сглаживания и дифференцирования экспериментальных данных на основе сглаживающих сплайнов. // Автометрия. 1986 №.1. С.38.

15. Воскобойников Ю.Е. Касьянова С.Н., Кисленко Н.П.,Трофимов О.Е. Использование алгоритмов нелинейной фильтрации для улучшения качества восстановленных томографических изображений.// Автометрия. 1997 №.3.

16. Голд Б., Рэйдер Ч. Цифровая обработка сигналов: Пер. с англ. / Под ред. A.M. Трахтмана. М.: Советское радио, 1973. - 368 с.

17. Грузман И.С., Киричук B.C., Косых В.П., Перетягин Г.И., Спектор А.А. Цифровая обработка изображений в информационных системах: Учебное пособие.- Новосибисрк: Изд-во НГТУ, 2000. 168.

18. Жирнов В.Т., Смирнов К.К., Трофимов О.Е. О численных методах решения задач томографии. В сб.: Методы и средства обработки изображений. -Новосибирск: ИАиЭ СО АН СССР, 1982, С. 105-114с.

19. Климов А.С. Форматы графических файлов. НИИП "ДиаСофт Лтд", 1995 -480с.

20. Леонов А.С., Ягола А.Г. Метод L-кривой всегда дает неустранимую систематическую ошибку//Вестн. Моск. ун-та. Физ.Астрон., 1997, т.З, №6, с. 17-19.

21. Новиков Л.В. Основы вейвлет-анализа сигналов. Учебное пособие.-ИАНП РАН Санкт-Петербург 1999. 152с ил.

22. Прокофьев Б.П., Сухарев Н.Н., Храмов Ю.Е Графические средства Turbo С Turbo С++/.- Москва, Финансы и статистика, 1992 160 с.

23. Прэтт У. Цифровая обработка изображений, М.: Мир, 1982. - 790 с

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

25. Тьюки Дж. Анализ результатов наблюдений.- М.: Мир, 1981. 160 с.

26. Шлихт Г.Ю. Цифровая обработка цветных изображений. М.,Издательство ЭКОМ, 1997. 336 с.

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

28. Ярославский Л.П. Цифровая обработка полей в оптических системах. Цифровая оптика / Новые физические принципы оптической обработки информации. М.: Наука, 1990. - С. 360 - 399.

29. Arce G., Paredes L. Recursive Weighted Median Filters Admitting Negative Weights and Their Optimization//IEEE trans on Signal Processing V.38 #3 2000.

30. Christopher John S. Ferro Scale and texture in digital image classification. // West Virginia University. Ms.D. theses 1998.

31. Chui C.K. Wavelets: a tutorial in theory and applications, Academic Press, 1992

32. Daubechies I. Ten Lectures on Wavelets. SI AM, 1992.

33. Gilles F. Houle and others A Multi-Layered Corroboration-Based Check Reader, University of Michigan USA 1996, pp 1-25

34. Grossman A., Morlet J. Decomposition of Hardly into square integrable * wavelets of constant shape // SI AM J. Math Anal. 1984 VI5. P.723-736 .

35. Hansen P.C The use of L-curve in regularization of discrete ill-posed problems // SIAM J.Sci Сотр., 1993. V14. PP1487-1503.

36. IEEE Trans, on Information Theory, Vol. 38, No. 2, March 1992 (специальный номер по вейвлетам)

37. Каш L. And other. A Robust Contour Preserving Image Reconstruction Algorithm For a New Quantum X-Ray Radiology System // UHA France 1999

38. Lindeberg T. Edge Detection and Ridge Detection with Automatic Scale Selection.//Computer Vision vol.30, no 2, pp 117-154 1998

39. Lim, Jae S. Two-Dimensional Signal and Image Processing. Englewood Cliffs, NJ: Prentice Hall, 1990. pp. 536-540.

40. Nieninen A., Heinonen P., Neuvo Y. A New Class of Detail-Treserving Filters for Image Processing // IEEE Trans on Pattern Analysys and Machine Intelligence. Vol PAMI-9 No 1 Jan 1987.

41. Nosratinia A. and Orchard M. T. A multi-resolution framework for backward motion compensation, in Proc. SPIE Symposium on Elec-tronic Imaging, (San Jose, С A), February 1995.

42. Parker J.R. Vector Templates and Handprinted Digit Recognition // University of Calgary 1995 , ppl-7

43. Perry. S. W. Adaptive Image Restoration: Preception Based Neural Network Models and Algorithms // Ph.D theses, University of Sydney Australia 1999, 155p

44. PearIman Said A., W. A New Fast and Efficient image Codec Based on Set Partitioning in Hierarchical Trees, IEEE Trans, on Circuits and Systems for Video Technology, V.6, June 1996

45. Felzenzwalb Pedro F., Huttenlocher Daniel P. Recognizing Flexible Objects//Cornell University Press. DAAL01-97-K-0104 issue. 1997.

46. СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

47. Колкер А.Б. Взвешенные и рекурсивные алгоритмы векторной медианной фильтрации. //Сборник научных трудов НГТУ. Новосибирск: Изд-во НГТУ ,2000- Вып.5(22).

48. Колкер А.Б. Аппроксимация изолиний изображений параметрическими сплайнами.// Труды 12-й Байкальской международной конференции «Методы оптимизации и их приложения», Иркутск: Изд-во ИСЭМ СО РАН,2001 с.

49. Воскобойников Ю.Е. Колкер А.Б. Адаптивный алгоритм фильтрации изображений и преобразования их в векторный формат.// Автометрия 2002, том 38,№4

50. Yu.E. Voskoboinikov and А.В. Kolker Adaptive filtering algorithm and conversion of images to a vector format (Адаптивная фильтрация и преобразование изображений в векторный формат) // Optoelectronics, Instrumentation and Data Processing №4, 2002

51. Колкер А.Б. Алгоритм фильтрации изображений с использованием дополнительной информации о корреляции. // 60я научно-техническая конференция НГАСУ. мат. конф. Новосибирск: изд-во НГАСУ, 2003 4.1

52. Воскобойников Ю.Е. Колкер А.Б. Аппроксимация изолиний сглаживающими сплайнами. // Автометрия №4 2003

53. Yu.E. Voskoboinikov and А.В. Kolker Approximation of Image Isolines by Smoothing Splines. (Сплайн-аппроксимация изолиний изображений)// Optoelectronics, Instrumentation and Data Processing v.39 №4, 2003