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

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

Упакова Анастасия Геннадьевна

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

Специальность 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

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

2 4 ИЮЛ 2014

005550782

Москва 2014

005550782

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Рязанский государственный радиотехнический университет» (РГРТУ) на кафедре «Электронные вычислительные машины» Научный руководитель: Костров Борис Васильевич, почетный

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

Официальные оппоненты: Сушкова Людмила Тихоновна, доктор

технических наук, заведующая кафедрой биомедицинских и электронных средств и технологий ФГБОУ ВПО «Владимирский государственный университет имени А.Г. и Н.Г. Столетовых»

Можаров Геннадий Петрович, кандидат технических наук, доцент кафедры компьютерных систем и сетей ФГБОУ ВПО «Московский государственный технический уныерситет им. Н.Э. Баумана»

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

Защита диссертации состоится 25 сентября 2014 г. в 13:00 ч. на заседании диссертационного совета Д 212.147.03 при МГУП имени Ивана Федорова по адресу 127550 Москва, ул. Прянишникова, д. 2а.

С диссертацией можно ознакомиться в библиотеке МГУП имени Ивана Федорова. Электронная версия диссертации размешена: http://mgup.ru

Автореферат разослан «/5» 2014 г.

Ученый секретарь л /

доктор технический наук В.Н. Агеев

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

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

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

Степень разработанности темы. На данный момент проблеме фильтрации изображений уделяется все больше и больше внимания. Существенный вклад в развитие методов цифровой обработки изображений внесли Э.Прэтг, Р.Гонзалес, Л.П. .Ярославский, В.К. Злобин, В.В. Еремеев, A.M. Трахтман, В.А. Сойфер, Я.А. Фурман.

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

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

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

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

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

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

- исследование проявления в спектрах помех, возникающих в процессе формирования и передачи изображения;

- разработка и исследование алгоритмов и операторов фильтрации изображения;

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

- проектирование программной системы, реализующей данные алгоритмы.

Научная новизна состоит в разработке алгоритмов фильтрации в

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

На защиту выносятся следующие новые научные результаты:

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

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

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

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

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

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

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

Реализация и внедрение. Диссертация выполнена в Рязанском государственном радиотехническом университете в рамках:

-НИР 36-09; НИР 4-11 Г; НИР 10-12Г.

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на 15-й всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2010); 16-й всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2011); международной научно-технической конференции «Космонавтика. Радиоэлектроника. Геоинформатика», посвященной 90-летию со дня рождения академика В.Ф. Уткина (Рязань, 2013); 5-й межвузовской школе-семинаре «Задачи системного анашза, управления и обработки информации» (Москва, 2014).

Публикации. По теме диссертации опубликовано 16 работ, в том числе 8 статей, 4 из которых в изданиях, рекомендуемых ВАК РФ, и 4 тезиса доклада в материалах международной и всероссийских конференций. В Объединенном фонде электронных ресурсов «Наука и образование» зарегистрировано два пакета прикладных программ для ЭВМ (№19926 от 19.02.2014, №19927 от 19.02.2014). В Федеральной службе но интеллектуальной собственности, патентам и товарным маркам зарегистрированы две программы для ЭВМ (свидетельство №2014612292 от 24.02.2014, № 2014612721 от 05.03.2014).

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ В первой главе приводится анализ средств формирования АКИ, вводится понятие цифрового изображения, приводится анализ фильтрации пространственными и частотными методами.

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

Цифровое изображение — это конечный набор числовых значений точек, являющихся некоторой функцией распределения яркости от точки к точке на плоскости /(х, у), где .т и у - декартовы координаты, описывающие плоскость изображения. Изображение можно представить в матричной или векторной форме. В диссертации используется матричное представление изображения:

/

Ау =

/о.о /о,1 "' /о,Лг-1 /ко Ал ■"" Лл;-1

(1)

\f\f-i,о Л/-и "• /\/-1,л-1)

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

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

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

Т^Л^ .(2)

где и —множество искаженных элементов изображения, /?(х,у) - значения яркости искаженных элементов;

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

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

И,М - размеры изображения.

Считается, что если изображение с уровнем СКО ниже 4,2, то обработанное изображение неотличимо от оригинала, поскольку человеческий глаз не воспринимает разницу изображений, с уровнем от 4,2 до 8 дает хорошее качество фильтрации, с уровнем выше 8 — неприемлемое качество.

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

где а — {т — \),Ь = (п — 1), тхп - размеры маски, •и,(5,7) — ядро свертки, - искаженное изображение.

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

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

(3)

исходное изображения, /(х,у) - отфильтрованное изображение;

а Ъ 5 = 1 Г=1

(4)

Дискретное двумерное преобразование Фурье матрицы изображения определяется в виде ряда:

1 Л/—1Л'—I —Ил{иХ-т-Л')

= — х Ем - , (5)

№ х=0у=0

где м,у - пространственные частоты.

Обратное дискретное двумерное преобразование Фурье имеет вид:

М-Ш-1 -<2Я-(ШГ + "') Ях,у)= I л/ .V . (6)

и = 0 у = О

Эти равенства образуют пару двумерных дискретных преобразований Фурье

(ДПФ).

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

п

УКГ(р,х) = н"=> , (7)

где 1У = ехрУ(2/Т //и), р1 и х1 - разрядные коэффициенты чисел р их, представленных в т -ичной системе счисления.

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

Таблица 1 - Сравнительные характеристики ограничения спектра для разных оснований ортогональных функций_

Основные системы счисления т = 2 т = 4

Количество отличающихся пикселей 0 122

Среднеквадратичное отклонение (СКО) 0 0,1654

Время выполнения 256*256 (с) 0,0151 0,0586

Время выполнения 64*64 (с) 0,0016 0,0038

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

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

где Н,у - матрица Уолша.

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

1) синхронные искажения с постоянной частотой диадного ряда;

2) синхронные искажения с произвольным шагом;

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

В основе всех алгоритмов фильтрации изображений с синхронными искажениями лежит алгоритм восстановления изображения с синхронными искажениями с постоянной частотой диадного ряда. Методология алгоритмов фильтрации изображений с первыми двумя типами искажений приведена в работах Кострова Б.В. Наиболее интересный случай представляет собой алгоритм фильтрации изображений с синхронными искажениями с произвольным шагом и с перепадом яркости в самом искажении. Пример изображения с таким искажением и его спектр приведены на рисунке 1. Данные искажения в основном возникают при стыковке двух и более изображений с разными уровнями яркости и с яркостными изменениями ПЗЗ датчика.

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

- высчитывается перепад яркости на искажении и ищется точка, которая и будет средней яркостью между крайними точками искажения:

(8)

а обратное -

(9)

Р =

м

(10)

где Р - искомая точка, к - шаг искажения, М - количество взятых элементов для расчета точки;

б) : ил ил гмо

Рисунок 1 — Изображение с синхронным искажением с перепадом яркости его квазидвумерный спектр: а - изображение с синхронным искажением с перепадом яркости: б - его квазидвумерный спектр первой строки

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

+ , (11)

где к= Р~Р(Ц) , у = Ш2.

к/2

Соответственно с правой стороны получается

П1,у) = ^(1^)-(у-Дг/2)-/г. (12)

Алгоритм позволяет обработать изображение с синхронными искажениями с перепадом яркости и снизить СКО=14 до величины, меньшей двух.

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

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

к | Ллеслптах;^Л7и| ^^

где кх - шаг сдвига для каждой строки, кх=\,п — 1, п - шаг помехи, Рх^/п и

FxkN,„ - значение спектральной составляющей с номером Nln, к как верхний индекс показывает принадлежность к значению, полученному в результате сдвига;

- к полученному спектру применяется полосовой усредняющий фильтр:

Г 1, если и ^ Nom

H (u, у) = •! F {и + l.y) + F (и — 1,}') (14)

4 '7 —----—, если и = Nom,

I 2

где Nom — номера выбитых строк;

- восстанавливается изображение путем перехода из частотной области в пространственную по формуле (9);

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

позволяет понизить СКО от 16 до величины, меньшей двух.

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

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

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

- групповые искажения;

- импульсные искажения типа «соль и перец».

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

- выполняется прямое преобразование Уолша по формуле (8):

F = Hwg, (15)

где g - искаженное изооражение.

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

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

М(и) =

О, если

0. если 5 5 (16)

1 во всех остальных cлvчaяx,

где М(и) - номера строк возможного расположения групповой помехи, -некоторый порог;

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

Г Р(и,у),и£М Р(и,у) = - 1,>р + Г(н +1,>'), и е М; (17)

I 2

- выполнить обратное преобразование Уолша.

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

0,/(х,>-) = 0,хеМ

128,х й М (18)

255,/(.-с, V) = 255, х е М,

где М - матрица-вектор выбитых строк.

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

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

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

- применяется теорема об ограничении нетригонометрического спектра:

/^^¿Л* (19)

В(х,у) =

у _

где 5 = 2к~], N. = —, х = 1,ЛГ;

- к полученному ограниченному спектру применяется дискретное ооратное преобразование Уолша:

М-1 С II Л

(20)

= л о (",#йЦм:7

где /(х, у) - «усечённое изображение»;

Рисунок 2 - Графики зависимости СКО от количества выбитых пикселей при различных методах: а - пространственно-частотный метод; б - частотный метод; в - пространственный метод

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

А*, у) = теё{я(х, >•,£)}; (21)

к=\,п

- вычитается полученное изображение из изображения с импульсными искажениями:

(22)

где Г - матрица изображения с импульсными искажениями, f - матрица нового изображения, М - маска импульсных помех;

- используются значения полученной маски:

Ь = Г + М, (23)

где Ь - изображение без помех.

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

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

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

Таблица 2 - Сравнительные характеристики СКО для постранственного.

% выбитых пикселей на изображении СКО (простр) СКО (двум.) СКО (квазидв.)

0.01 8,29 2,11 1.58

0.02 8,32 2,89 2.36

0.04 8,44 4,12

0.005 8.25 1,48 1.02

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

, \17(и,у)ирк Я(х,у)=0,

= \ л <24)

[ 0 при Я(х,у) = \,

где 0(и,у) - спектр с помехой, /*Уи,у) - спектр изображения без постоянной составляющей.

Алгоритм восстановления спектра изображения без постоянной составляющей состоит в следующем:

-восстанавливается первая составляющая по формуле:

0(1,у) = -£0(и,у)-, (25)

и=2

- путем сравнения с соседними элементами определяются те первые составляющие, в которых есть групповые искажения (рисунок 3);

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

- по номерам строк строится битовая маска групповых искажений:

В(и,у) = \ ' (26)

где М - матрица-вектор выбитых строк;

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

Г С{и,у),и<£М д(и,у)=\ С{и-\,у) + С{и + \,у),и& М , (27)

где М - номера выбитых строк;

- пересчитываются постоянные составляющие по формуле (25);

- восстановление из частотной области.

Рисунок 3 - Первая строка квазидвумерного спектра изображения

Четвертая глава посвящена разработке программного комплекса, моделированию БПУ в ПЛИС и практическому применению алгоритмов.

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

Предложена модель реализации БПУ в ПЛИС фирмы Altera. Как известно, ПЛИС в последнее время пользуется все большей и большей популярностью, в то же время при своей компактности и малом весе обладает достаточно высокой производительностью. Из таблицы 3 видно, что при преобразовании строки размерностью 1x512 элементов необходимо потратить 28 мкс. Для формирования строки 1x512 в тепловизионном датчике с частотой 25 Гц затрачивается около 57 мкс, что вдвое превышает заявленную скорость обработки. Скорость передачи со спутника «Канопус-В» 61.44 Мбит/с (т.е. строка размерностью 1x512 передается за 120 мкс).

Таблица 3 - Временные характеристики БПУ в ПЛИС

Количество элементов Время просчета

1x8 220 не

1x64 2240 не

1x512 17920 нс/28160 не

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ:

Основные результаты диссертационного исследования состоят в следующем.

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

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

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

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

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

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

7.Разработаны алгоритмы восстановления спектра без постоянной составляющей.

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

9. Спроектирован программный комплекс, реализующий данные алгоритмы.

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

Работы, опубликованные в научных журналах, входящих в перечень ведущих рецензируемых журналов и изданий ВАК РФ

1. Костров Б.В., Упакова А.Г. Квазидвумерная фильтрация синхронных помех на изображении // Проектирование и технологии электронных средств №1. 2012. С. 32-35.

2. Костров Б.В., Гринченко H.H., Степанов Д.С., Упакова А.Г. Алгоритм передачи изображения с восстановлением постоянной составляющей // Известия

Тульского государственного университета. Технические науки. Выпуск 9. Часть 1. г. Тула. 2013 г. С. 244-250.

3. Злобин В.К., Костров Б.В., Конкин Ю.В., Упакова А.Г. Алгоритм устранения искажений средней яркости по полю изображений// Известия Тульского государственного университета. Технические науки. Выпуск 9. Часть 2. г. Тула. 2013 г. С.118-124.

4. Упакова А.Г. Фильтрация изображений с импульсными помехами на основе теории дискретных сигналов на конечных интервалах // Современные проблемы науки и образования. 2014. № 2.

URL: www,science-education.ru/116-12304

5. Костров Б.В., Бабаев С.И., Упакова А.Г. Построение базиса в обобщенной системе ортогональных функций// Вестник Рязанского государственного радиоуниверситета № 1 (Вып. 47). Рязань, 2014. С.18-21 .

Работы, опубликованные в других изданиях

6. Костров Б.В., Саблина В.А., Свирина (Упакова) А.Г. Изучение секвентных спектров синхронных помех // Методы и средства обработки и хранения информаци: межвуз сб. науч. тр. РГРТУ. Рязань. 2010 г. С. 8-12.

7. Костров Б.В., Некрасова О.С., Свирина (Упакова) А.Г. Метод квазивумерной фильтрации групповых помех // Методы и средства обработки и хранения информации: межвуз сб. науч. тр. РГРТУ. Рязань. 2010 г. С. 152-156.

8. Костров Б.В., Некрасова О.С., Свирина (Упакова) А.Г. Квазидвумерный метод выделения шумовых выбросов на изображении // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 15-й всеросс. науч.-техн. конф. - Рязань: РГРТУ, 2010. С.368.

9. Свирина (Упакова) А.Г. Визуализация алгоритма быстрого преобразования Уолша // Вычислительные машины, комплексы, системы и сети. Приложение к межвуз. сб. науч. тр. «Методы и средства обработки и хранения информации». Рязань: РГРТУ, 2011. С. 15-16

10. Костров Б.В., Свирина (Упакова) А.Г. Квазидвумерная фильтрация несинхронных помех на изображении // Новые информационные технологии в научных исследованиях и в образовании. Тез. докл. 16-й всеросс. науч.-техн. конф. - Рязань: РГРТУ, 2011. С.253.

11. Костров Б.В., Упакова А.Г., Баюков К.И. Реализация преобразования Уолша в пакете прикладных программ Matlab. Определение наиболее эффективного алгоритма // Информатика и прикладная математика: межвуз сб. науч. тр. РГУ им. С.А. Есенина. Рязань. 2013 г. С.38-41.

12. Упакова А.Г. Построение базиса на основе систем функций, арифметически кратных двоичной системе И 6-я междунар. науч.-техн. конф. «Космонавтика. Радиолектроника. Геоинформатика» / Рязань: РГРТУ. 2013. С. 271-272.

Свидетельства о регистрации программ для ЭВМ

13. Костров Б.В., Упакова А.Г. Свидетельство о регистрации электронного ресурса ОФЭРНиО № 19926. Программный пакет «Обработка изображений с

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

14. Костров Б.В., Упакова А.Г. Свидетельство о регистрации электронного ресурса ОФЭРНиО № 19927. Программный пакет «Обработка изображений с синхронными помехами на основе теории дискретных сигналов на конечных интервалах».

15. Упакова А.Г. Свидетельство о государственной регистрации программы для ЭВМ «IMFWT» .N»2014612292/7 Федеральная служба по интеллектуальной собственности, патентам и товарным маркам. Зарегистрировано в Реестре программ для ЭВМ 24.02.2014.

16. Упакова А.Г., Костров Б.В., Гринченко H.H., Громов А.Ю. Свидетельство о государственной регистрации программы для ЭВМ «MULTFWT» Лд2014612721// Федеральная служба по интеллектуальной собственности, патентам и товарным маркам. Зарегистрировано в Реестре программ для ЭВМ 05.03.2014.

Угтакова Анастасия Геннадьевна

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

АВТОРЕФЕРАТ

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

Отпечатано в ООО «Полиграф» Заказ № 116. Тираж 100 экз.

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «Рязанский государственный радиотехнический университет»

04201460572

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

Упакова Анастасия Геннадьевна АЛГОРИТМЫ ФИЛЬТРАЦИИ ИЗОБРАЖЕНИЙ В КВАЗИДВУМЕРНЫХ КОНЕЧНЫХ БАЗИСАХ

Специальность 05.13.17 — «Теоретические основы информатики»

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

Научный руководитель: почетный работник высшего профессионального образования РФ, доктор технических наук, профессор Костров Б.В.

Москва-2014

Содержание

ВВЕДЕНИЕ.........................................................................................................4

1 АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ ФИЛЬТРАЦИИ ИЗОБРАЖЕНИЙ..............................................................................................10

1.1 Формирование АКИ..........................................................................10

1.2 Пространственная фильтрация изображений..................................22

1.3 Частотная фильтрация изображений...............................................28

1.4 Спектральный анализ в базисе ВКФ................................................33

2КВАЗИДВУМЕРНАЯ ФИЛЬТРАЦИЯ ИЗОБРАЖЕНИЙ С СИНХРОННЫМИ И НЕСИНХРОННЫМИ ИСКАЖЕНИЯМИ...................43

2.1 Квазидвумерная фильтрация изображений.....................................43

2.2 Алгоритмы квазидвумерной фильтрации

изображений с синхронными искажениями....................................47

2.3 Алгоритмы квазидвумерной фильтрации

изображений с несинхронными искажениями................................60

2.4 Алгоритмы квазидвумерной фильтрации

изображений с синхронными искажениями со

случайным изменением яркости......................................................65

3 КВАЗИДВУМЕРНАЯ ФИЛЬТРАЦИЯ ИЗОБРАЖЕНИЙ С ИСКАЖЕНИЯМИ, ВОЗНИКАЮЩИМИ В ПРОЦЕССЕ ПЕРЕДАЧИ........71

3.1 Алгоритм квазидвумерной фильтрации изображений

с групповыми искажениями.............................................................71

3.2 Алгоритмы квазидвумерной фильтрации

изображений с импульсными искажениями...................................76

3.3 Алгоритм передачи изображений без постоянной

составляющей...................................................................................82

3.4 Алгоритм устранения групповых искажений в

спектре...............................................................................................86

4ПРОГРАММНЫЙ КОМПЛЕКС И МОДЕЛИРОВАНИЕ БПУ НА ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ МАТРИЦАХ...............................93

4.1 Структура и основные модули программного

комплекса..........................................................................................93

4.2 Модуль реализации БПУ в ПЛИС...................................................100

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

ЗАКЛЮЧЕНИЕ..............................................................................................114

СПИСОК ЛИТЕРАТУРЫ..............................................................................115

ПРИЛОЖЕНИЕ..............................................................................................127

ВВЕДЕНИЕ

Актуальность работы. С конца прошлого века человечество получает снимки из космоса о поверхности Земли. Фонд аэрокосмических изображений (АКИ), накопленный за полвека, является одним из наиболее информативных источников сведений о динамических явлениях и процессах, протекающих в природе. В настоящее время АКИ используются во многих отраслях человеческой деятельности: в географических и гидрологических исследованиях Земли, в сельском хозяйстве, лесоводстве, исследовании окружающей среды. На спутниках устанавливаются различные типы видеодатчиков для получения все более качественных снимков. Далее, эти снимки передаются по каналам связи на Землю в пункты обработки АКИ. Во время передачи изображения могут возникать различные помехи, мешающие дальнейшему использованию снимков по назначению. В связи с этим достаточно остро встает вопрос о фильтрации изображений с помехами, т.е. приближение изображения к идеальному (исходному). Поскольку данная задача является актуальной и сложной, то необходимо найти наиболее эффективные методы ее решения. Известные на сегодняшний момент методы фильтрации изображений делятся на пространственные и спектральные, последние более удобные для проведения исследований и анализа свойств изображений [24, 30, 91, 92, 93, 96].

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

Степень разработанности темы. На данный момент проблеме фильтрации изображений уделяется все больше и больше внимания. Существенный вклад в развитие методов цифровой обработки изображений внесли Э.Прэтт, Р.Гонзалес, Ярославский Л.П., Злобин В.К., Еремеев В В., A.M. Трахтман, Сойфер В.А., Фурман Я.А.

В настоящее время разработано достаточно много алгоритмов и методов восстановления изображения. Все алгоритмы по восстановлению изображений можно разделить на две категории: восстановление в пространственной и частотной области. Алгоритмы восстановления в пространственной области хорошо описаны [24, 25], так же в этих монографиях говориться и о восстановлении в частотной области. Как известно, в пространственной области алгоритмы строятся на непосредственной обработке каждого пикселя, из-за чего возникают различные шумы или размытие изображения. При обработке в частотной области этих проблем можно избежать. При переходе от пространственной области к частотной используются ортогональные функции [90]. В настоящее время наибольшее распространение получил переход через преобразование Фурье. Так же в качестве ортогональных функциях в своих работах Трахтман A.M., Костров Б.В. предлагают использовать преобразование Уолша. В традиционном понимании, ортогональное преобразование применяют последовательно к строкам и столбцам изображения, что несет огромные вычислительные затраты. Методология применения одностороннего (квазидвумерного) преобразования была предложена Костровым Б. В. Однако, разработка и исследование практически работающих алгоритмов еще недостаточно освещены в научных работах.

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

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

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

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

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

- исследование проявления в спектрах помех, возникающих в процессе формирования и передачи изображения;

- разработка и исследование алгоритмов и операторов фильтрации изображения;

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

- проектирование программной системы, реализующей данные алгоритмы.

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

На защиту выносятся следующие новые научные результаты:

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

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

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

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

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

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

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

Реализация и внедрение. Диссертация выполнена в Рязанском государственном радиотехническом университете в рамках:

- НИР 36-09 «Информационная система предупреждения и прогнозирования развития чрезвычайных ситуаций на техногенных комплексах хранения горюче-смазочных материалов», выполняемой по Государственному контракту №П2390 от 18.11.2009 г. в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг., реализация мероприятия №1.2.2. «Проведение научных исследований под руководством кандидатов наук», руководитель проекта Б.В. Костров;

- НИР 4-11Г «Разработка методов и информационных технологий мониторинга потенциально-опасных объектов и ландшафтных образований», выполненной в соответствии с заданием Министерства образования и науки Российской Федерации;

- НИР 10-12Г «Разработка методов и информационных технологий обработки многоспектральных изображений для мониторинга ландшафтных образований», выполненной в соответствии с заданием Министерства образования и науки Российской Федерации;

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

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на 15-й всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и образовании» (Рязань, 2010); на 16-й всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и образовании» (Рязань, 2011); на международной научно-технической конференции «Космонавтика. Радиоэлектроника. Геоинформатика», посвященная 90-летию со дня рождения академика В.Ф. Уткина (Рязань, 2013); на 5 межвузовской школе-семинаре «Задачи системного анализа, управления и обработки информации» (Москва, 2014).

Публикации. По теме диссертации опубликовано 16 работ, в том числе 8 статей, 5 из которых в изданиях, рекомендуемых ВАК РФ, и 4 тезиса доклада в материалах международной и всероссийских конференций. В Объединенном Фонде электронных ресурсов «Наука и образование» зарегистрировано два пакета прикладных программ для ЭВМ (№19926 от 19.02.2014, №19927 от 19.02.2014). В Федеральной службе по интеллектуальной собственности, патентам и товарным маркам зарегистрированы две программы для ЭВМ (свидетельство №2014612292 от 24.02.2014, № 2014612721 от 05.03.2014).

Структура и объем работы. Диссертация состоит из введения, 4-х глав, заключения, списка литературы и приложений, которые содержат 133 с. Основной текст работы содержит 114 е., 89 рисунков, 5 таблиц. Список литературы включает 101 наименование.

1 АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ ФИЛЬТРАЦИИ ИЗОБРАЖЕНИЙ. 1.1 Формирование АКИ

Перспективным методом исследования поверхности нашей планеты является применение искусственных спутников Земли. Дистанционное зондирование Земли (ДЗЗ) - измерение характеристик поверхности Земли авиационными и космическими средствами, оснащенными съемочной аппаратурой, с различными геометрическими, спектральными и энергетическими характеристиками. Съемка поверхности Земли выполняется, как правило, несколькими устройствами. В процессе полета эти устройства способны регистрировать информацию в инфракрасной, видимой и радиолокационной области спектра энергетического потока, отраженного от объектов на местности. Далее эти снимки передаются в наземные пункты приема и обработки информации. Информация со спутников поступает и хранится в цифровом виде. На Земле обработка информации осуществляется с помощью ЭВМ. В настоящее время информационные технологии обработки изображений относятся к числу наиболее динамично развивающихся технологий, применяемых в робототехнике, медицине, сельском хозяйстве и т.д. (рисунок 1.1)[12, 24, 25, 29, 58, 78].

Различные датчики сканирующего типа составляют основу съемочных платформ формирования различных изображений. Приведем классификацию сканирующих устройств [29, 34]. Можно отметить, отличительный признак данной классификации - механизм сканирования, реализованный в различных датчиках. Таким образом, все типы сканирующих устройство можно разделить на 5 групп:

1. датчики, которые построенны на основе приборов с зарядовой связью (ПЗС-линейка);

2. однолучевые датчики с конической или плоскостной разверткой;

3. датчики сканового типа;

4 радиолокационные станции различного базирования и принципа действия.

5. тепловизионные и телевизионные приборы и системы, которые устнавливаются, как правило, на атмосферных летательных аппаратах.

Рисунок 1.1- Этапы формирования и обработки космических изображений Принципиальная схема съемки прибором с зарядовой связью приведена на рисунке 1.2 [36, 54, 88, 89].

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

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

Рисунок 1.2 - Принципиальная схема съемки прибором с зарядовой связью

Схема устройства и принцип действия однолучевого мультиспектрального сканера поясняется рисунком 1.3.

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

ПЗС - линейка

\ Оптическая система

Проекция «линейки» на