Содержание к диссертации
Введение
Глава I. Аналитический обзор многопроцессорных систем, методов автоматизированного дешифрирования аэрокосмических изображений и их реализация с использованием метода параллельных вычислений 13
1.1. Аналитический обзор многопроцессорных систем, их классификация 13
1.2. Методы и алгоритмы автоматизированного дешифрирования аэрокосмических изображений 27
1.2.1. Алгоритмы фильтрации и улучшения качества изображений 32
1.2.2. Алгоритмы сегментации изображений 41
1.2.3. Методы обработки гиперспектральных изображений 52
1.3. Применение параллельных вычислений в задачах автоматизированной обработки аэрокосмических
Глава II. Программное обеспечение и аппаратная реализация вычислительного кластера 70
2.1. Аппаратная реализация вычислительногокластера 70
2.2. Программное обеспечение вычислительногокластера 73
2.2.1. Структура программного обеспечения
2.2.2. Операционная система вычислительного кластера 78
2.3. Система параллельного программирования МРІ 82
2.3.1. Общие положения МРІ 82
2.3.2. Типы обмена данными в МРІ 84
2.4. Производительность вычислительного кластера МВС-1000 и эффективность параллельных программ 88
2.4.1. Оценка производительности вычислительного
2.4.2. Эффективность параллельных программ 89
Глава III. Теоретические основы и экспериментальные исследования алгоритмов высокопроизводительной обработки аэрокосмических изображений методом параллельных вычислений 94
3.1. Применение метода параллельных вычислений для алгоритмов фильтрации скользящими порядковыми
3.2. Методология расчета оптимальных параметров вычислительного кластера и оценки эффективности распараллеливания алгоритмов обработки аэрокосмических изображений скользящими пространственными фильтрами 103
3.3. Алгоритм выделения малоразмерных объектов заданного размера на аэрокосмических изображениях 113
3.4. Технология параллельного дешифрирования гиперспектральных изображений для выделения антропогенных и природных объектов характерных для средней полосы России . 127
Заключение 149
Список литературы 150
- Методы и алгоритмы автоматизированного дешифрирования аэрокосмических изображений
- Программное обеспечение вычислительногокластера
- Оценка производительности вычислительного
- Алгоритм выделения малоразмерных объектов заданного размера на аэрокосмических изображениях
Введение к работе
Интенсивное развитие средств дистанционного зондирования Земли аэрокосмического базирования, увеличение объемов и информативности аэрокосмической информации приводит к непрерывному расширению круга задач, решаемых с использованием данных дистанционного зондирования. Дистанционное зондирование из космоса находит все более широкое применение при решении задач контроля загрязнений окружающей среды, в картографии, в исследованиях природных ресурсов, климатологии, океанографии, для мониторинга земной поверхности, для наблюдения за пожарами и др. Необходимость обработки больших объемов данных и требования к оперативности получения результатов обуславливают интенсивное внедрение компьютерных технологий обработки изображений. Несмотря на стремительный прогресс в развитии аппаратных компьютерных средств, возможностей даже самых быстродействующих компьютеров последовательной архитектуры не достаточно для оперативного решения ряда задач обработки изображений, полученных методами дистанционного зондирования. Для решения задач анализа, преобразования и обработки большого объема аэрокосмической информации с минимальными временными затратами требуется мобилизации всех возможностей доступных аппаратно-программных средств. На сегодняшний день средствами, позволяющими существенно время вычислений, являются высокопроизводительные многопроцессорные системы различных архитектур, в частности вычислительный
кластер, который при относительно невысокой стоимости обеспечивает высокопроизводительную обработку изображений.
Несмотря на то, что сами по себе вопросы компьютерной обработки изображений и распараллеливания вычислений достаточно хорошо изучены, вопросы применения различных алгоритмов распараллеливания для решения реальных задач обработки изображений рассмотрены явно недостаточно. Поэтому задача создания технологии высокопроизводительной обработки аэрокосмических изображений с использованием параллельных вычислений является весьма актуальной.
Методы обработки аэрокосмических изображений разделяются на два класса: предварительной (первичной) обработки изображений, и тематической обработки (дешифрирования) изображений. Для повышения производительности методов обработки аэрокосмических изображений было необходимо провести исследования методов распараллеливания вычислений и создать оптимальные или близкие к ним методы обработки изображений с использованием распараллеливания, значительно повышающие эффективность процедур обработки аэрокосмических изображений.
Целью диссертационной работы является разработка технологии высокопроизводительной обработки аэрокосмических изображений с использованием метода параллельных вычислений.
Для достижения поставленной цели необходимо было решить следующие задачи:
Проанализировать существующее программное обеспечение и архитектуры многопроцессорных систем для выбора системы, обеспечивающей решение задач высокопроизводительной обработки аэрокосмической информации и оптимальной с точки зрения критерия эффективность/стоимость.
Создать и ввести в действие многопроцессорный аппаратно-программный комплекс.
Провести анализ существующих алгоритмов обработки изображений, выбрать и разработать алгоритмы, эффективность которых может быть повышена за счет распараллеливания.
Выбрать и разработать программное обеспечение, позволяющее реализовать параллельную обработку аэрокосмических изображений.
Провести экспериментальные исследования по обработке реальных изображений, полученных методами дистанционного зондирования, с использованием метода параллелельных вычислений. Проанализировать полученные результаты.
При решении поставленных задач использовались методы теории информации, математической статистики, дешифрирования и обработки изображений. Экспериментальные исследования включали полевые и заверочные работы по изучению земных покрытий на территории, занимающей площадь около 3500 кв.км., выполненные автором в 2003-2004гг.
Результаты исследований изложены в трех главах.
В первой главе рассмотрены существующие многопроцессорные системы, методы и алгоритмы распараллеливания в задачах обработки изображений. Рассмотрены современная технология и методы предварительной и тематической обработки аэрокосмических изображений. Выполненный обзор позволил изучить и проанализировать существующие многопроцессорные системы и различное программное обеспечение с целью выбора системы, являющейся оптимальной для решения задач обработки аэрокосмических изображений с точки зрения критерия эффективность/стоимость . В результате проведенного анализа методов автоматизированной обработки аэрокосмических изображений выбраны алгоритмы, эффективность которых может быть повышена за счет распараллеливания.
В Главе II приведено описание созданного и введенного в действие многопроцессорного комплекса, его программного обеспечения и основных принципов его работы. На основе анализа архитектур многопроцессорных систем, выполненного в Главе 1, были выработаны определенные требования на основе критерия эффективность/стоимость к многопроцессорной
системе, предназначенной для решения задач обработки аэрокосмических изображений. На основе этих требований был создан и введен в эксплуатацию вычислительный кластер, позволяющий сокращать время обработки аэрокосмических изображений за счет создания эффективных параллельных приложений .
В главе III описана разработанная методология выбора оптимальных параметров вычислительного кластера и расчета эффективности распараллеливания алгоритмов обработки изображений скользящими пространственными фильтрами. Подробно описан разработанный автором алгоритм автоматизированного выделения малоразмерных объектов заданного размера, позволяющий с высокой достоверностью выделять малоразмерные объекты с сохранением разрешающей способности исходных снимков. Приведены результаты экспериментальных исследований его работы на реальных аэрокосмических изображениях. Изложена разработанная технология параллельного дешифрирования гиперспектральных изображений высокого разрешения для выделения набора объектов характерных для средней полосы России.
Научное значение и новизна работы. В настоящей работе разработаны и реализованы на практике теория и методы предварительной и тематической параллельной обработки аэрокосмических изображений. Результаты исследований позволяют повысить эффективность и оперативность обработки данных дистанционного зондирования.
На защиту выносятся следующие оригинальные разработки и результаты:
Методология расчета оптимальных параметров вычислительного кластера и оценки эффективности распараллеливания при использовании алгоритмов обработки аэрокосмических изображений скользящими пространственными фильтрами.
Алгоритм выделения малоразмерных объектов заданного размера на аэрокосмических изображениях, позволяющий достоверно выделять объекты с высокой точностью выделения контуров.
Технология параллельного дешифрирования гиперспектральных изображений для выделения антропогенных и природных объектов характерных для средней полосы России.
Практическая часть работы заключалась в создании программно-аппаратного комплекса, обеспечивающего параллельную обработку данных дистанционного зондирования. Разработанные методы используются в лабораторных занятиях по следующим курсам для студентов факультета прикладной космонавтики МИИГАиК:
Дешифрирование аэрокосмических снимков.
Технология тематической обработки данных дистанционного зондирования.
Работы выполнялись в рамках федеральной научно-технической программы «Интеграция».
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались:
- на 58 научно-технической конференции студентов, аспирантов и молодых ученых, проходившей в Московском Государственном университете геодезии и картографии (МИИГАиК); на Международной научно-технической конференции, посвященной 225-летию со дня основании МИИГАиК.
Основные результаты выполненных исследований представлены в 5 научных статьях, опубликованных в открытой печати, и в методических указаниях по выполнению лабораторных работ.
Структура и объем диссертационной работы.
Работа состоит из введения, трех глав, заключения, списка литературы и приложения.
Диссертация изложена на 156 страницах текста, содержит 57 рисунков и 13 таблиц, приложение содержит 14 страниц. Список литературы включает 80 наименований, из них 32 на иностранных языках, на б страницах.
Автор выражает благодарность научному руководителю доктору технических наук, профессору Малинникову В.А., а так же к. т.н. Марчукову B.C. и к. т.н. Меньшикову К.С. за постоянную поддержку, помощь и консультации в процессе работы. Автор признателен д.т.н., профессору Журкину И.Г. за
поддержку выбранного направления исследований на 58 научно-технической конференции студентов, аспирантов и молодых ученых, проходившей в Московском Государственном университете геодезии и картографии (МИИГАиК).
Автор считает своим долгом поблагодарить Институт прикладной математики им. М.В. Келдьппа РАН и лично Лациса А.О., Абрамову В.А. за плодотворное сотрудничество по введению в эксплуатацию вычислительного кластера.
Неоценимую помощь в исследовании местности Серпуховского района оказали Кочнов В.Б. и Кочнова Е.В., которых автор сердечно благодарит.
Методы и алгоритмы автоматизированного дешифрирования аэрокосмических изображений
Для аэрокосмических средств наблюдения окружающей среды характерным является использование регистрации отражения света и собственного излучения Земли в разных спектральных интервалах: визуальные наблюдения (0,40 — 0,64 мкм), фотографирование (0,40 — 0,92 мкм), спектрофотомет-рирование (0,40 — 2,5 мкм), телевизионная съемка (0,45 — 0,75 мкм), тепловая инфракрасная съемка (2,6 — 5,5 и 8,0 — 14,0 мкм), многоспектральная съемка (0,32 — 12,5 мкм), микроволновая съемка (0,3 см и более), а также активные методы локации [1, б, 11, 15, 21, 22, 24, 26, 29, 30, 44].
Фотографирование дает наиболее детальную информацию о пространственной структуре земной поверхности. Космические фотографии используются главным образом для контурного дешифрирования, выделения природных образований, прослеживания их границ, изучения внутренней структуры. Многозональное фотографирование - синхронное фотографирование одного и того же участка многообъективной фотокамерой с разными комбинациями фотопленок и светофильтров.
Спектрофотометрирование. Измерение спектральной отражательной способности природных и антропогенных образований осуществляется наземно и с самолетов. По космическим спектрам характеризуются все основные типы природных образований . Телевизионные съемки наиболее перспективны для наблюдения быстро меняющихся природных явлений.
Инфракрасная съемка дает пространственно-временное распределение радиационных температур системы Земля-атмосфера. По результатам измерений в видимой и ближней ИК-области спектра возможно распознавание сельскохозяйственных культур, прогнозирование урожая, контроль за состоянием сельскохозяйственных посевов, исследование за грязненности стоков вод, осмотр земель с целью создания реестра, исследование загрязнения окружающей среды, обнаружение залежей минералов.
Данные, полученные в средней ИК-области, могут использоваться при оценке состояния растительности, влажности почвы, уровня грунтовых вод, обнаружения источников тепловых потерь, идентификации горных пород, прогнозирования урожая.
Многоспектральные съемки - съемки во многих узких спектральных интервалах с помощью фотоэлектронного устройства, светофильтров и сканеров, как с самолетов, так и с космических аппаратов. Данный вид съемок особенно перспективен для изучения сельскохозяйственных угодий и посевов.Достоинства оптических методов дистанционного зондирования :высокое пространственное разрешение; - большое информационное содержание; - возможность наглядной интерпретации данных зондирования . Общим и наиболее существенным недостатком оптических методов дистанционного зондирования является сильная зависимость результатов зондирования от состояния атмосферы и погодных условий.
Основные достоинства радиотехнических методов дистанционного зондирования:- всепогодность; зо - возможность зондирования через растительность и облака; - возможность контроля значительных толщ земной поверхности и льда; - чувствительность к состоянию "шероховатости" по верхности, а также к содержанию влаги в поверхностном и подповерхностном слоях.
К недостаткам радиолокационных методов следует отнести их меньшее пространственное разрешение, большие габариты антенн.
Методы активной радиолокации используют для картирования ледовых полей, лесных массивов, растительности, для некоторых целей геологии и археологии. Пассивная радиолокация в СВЧ-диапазоне позволяет измерить температуру морской поверхности, изучать термодинамику морского льда, использовать влагосодержание почвы и растительности, обнаруживать линзы подземных вод, исследовать скрытые формы рельефа местности.
Современные методы визуально-инструментального и автоматизированного дешифрирования космических фотографических и сканерных изображений позволяет определять следующие элементы содержания топографических карт. Побережья морей, озер, рек и водохранилищ - береговые линии, типы берегов, расчлененность берегового контура, морские течения и их направления, абразивные береговые формы, береговую растительность и др.; - Гидрографическая сеть - форма русел, направления течений, морфометрические показатели речных систем и др.; - Рельеф - формы и морфологические особенности рельефа, геоморфологические объекты, разрывные нарушения и др.; - Растительный покров и грунты - состав растительности, границы и состояние различных форм растительного покрова и др.; - Населенные пункты, дорожная сеть и другие объекты антропогенного ландшафта. Задачей автоматизированного тематического дешифрирования аэрокосмических изображений является получение классифицированного изображения, которое представляет собой набор ограниченного числа известных классов, идентифицируемых как определенные типы объектов.
Программное обеспечение вычислительногокластера
Программное обеспечение вычислительного кластера МВС-1000 состоит из трех основных частей: резидентного управляющего ядра; системы очередей и запуска задач; системы коммуникаций. Резидентное управляющее ядро вычислительного кластера образует совокупность экземпляров операционной системы Linux, загруженных на управляющей машине и на каждом узле. Главной задачей резидентного управляющего ядра является обеспечить доступность каждого из узлов для управляющих воздействий со стороны управляющей машины - например, для запуска или завершения на узле ветви той или иной параллельной программы. Кроме того, резидентное управляющее ядро должно обеспечить симметричный доступ всех узлов и управляющей машины к единой файловой системе, на которой расположены, в частности, домашние директории пользователей. Для этой цели управляющая сеть сконфигурирована как отдельный сетевой сегмент, со стандартными протоколами TCP/IP; узлы - как nfs - клиенты, а управляющая машина -как nfs - сервер. Управляющей машине разрешается выполнение команд rsh на узлах от имени пользователя root. Никаких специальных служб или системных процессов на узлах не запускается - все управление узлами происходит по инициативе управляющей машины, посредством команд rsh.
Система очередей и запуска задач целиком реализована на управляющей машине. Она предназначена для управления узлами как единым процессорным ресурсом из одной точки, без явного доступа администратора или пользователей на узлы. Для работы на вычислительном кластере пользователь должен войти на управляющую машину по протоколу ssh. Подготовка программ и исходных данных осуществляется обычным образом, как на любой Linux - машине.
Если пользователю требуется запустить параллельную программу на N процессорах, он вводит специальную команду запуска параллельной программы на счет, в которой указывается исполняемый модуль ветви параллельной программы, а также требуемое число процессоров.
Если в системе имеется указанное число свободных процессоров, программа запускается на требуемом числе процессоров . В противном случае программа ставится в очередь на запуск. По завершении программы, или по истечении отведенного ей времени счета (по умолчанию - 5 часов) , выделенные задаче процессоры принудительно освобождаются системой запуска от всех процессов пользователя, запустившего задачу, после чего процессоры вновь становятся свободными. Как пользователь, так и администратор системы могут принудительно завершить задачу, или изъять ее из очереди, если она еще не вошла в счет.
Важным свойством системы запуска является императивность дисциплины доступа к процессорам. Так, если пользователь попытается, вручную или программно, получить доступ к процессору, который не был выделен системой запуска какой-либо его задаче, система запуска не даст ему это сделать. С другой стороны, если, в случае аппаратной или программной ошибки, системе запуска не удастся подготовить свободный процессор к запуску на нем ветви параллельной программы, или не удастся освободить процессор после завершения работы программы, или вообще не удастся получить доступ к процессору, процессор будет автоматически заблокирован, то есть, исключен из числа используемых. В любом случае гарантируется, что процессор, который система считает свободным, действительно свободен от ранее выполнявшихся на нем программ, а доступ пользователя - любым способом - возможен только к тем процессорам, которые ему предоставила система запуска.
Система очередей и запуска задач позволяет задачам заказывать только процессорный ресурс, но не пространство на локальных магнитных дисках вычислительных узлов. Локальное дисковое пространство можно использовать только для размещения временных файлов, то есть таких, которые уничтожаются по завершении задачи. Предоставление пользовательским программам возможности долговременного (между запусками задач) хранения данных на локальных дисках осложняется тем, что одна и та же задача попадает при различных запусках на различные узлы. Возможность оставить на некотором наборе узлов свои файлы, а затем запустить задачу, которой будут выделены именно эти узлы, требует для своей реализации серьезных изменений в системе очередей и запуска задач.
Оценка производительности вычислительного
Вычислительная производительность кластера грубо оценивается, как сумма вычислительной производительности его узлов. В настоящее время ведутся исследования степени влияния аппаратных характеристик кластера на его вычислительные способности [45]. Однако очевидно, что реальная его производительность сильно зависит от эффективности сети. Обычно выбор сетевых технологий происходит из соображений соотношения следующих критериев: стоимости, производительности и масштабируемости. Для построения вычислительных кластеров используют самое разное сетевое оборудование: Fast Ethernet, Gigabit Ethernet, Myrinet и другие.
Для исследования общей производительности вычислительного кластера был вьшолнен стандартный для таких случаев тест LINPACK, описанный в 1.1. По результатам этого теста производительность вычислительного кластера состав В идеале решение задачи на Р процессорах должно выполняться в Р раз быстрее, чем на одном процессоре, или/и должно позволить решить задачу с объемами данных, в Р раз большими. На самом деле такое ускорение практически никогда не достигается. Причина этого хорошо иллюстрируется законом Амдала [50]: (і) s V 4/+(1-/)/ ) где S - ускорение работы программы на Р процессорах, a f -доля непараллельного кода в программе.
Для МРР систем (механизм передачи сообщений) непараллельная часть кода образуется за счет операторов, выполнение которых дублируется всеми процессорами. Оценить эту величину из анализа текста программы практически невозможно. Такую оценку могут дать только реальные просчеты на различном числе процессоров.
Из формулы (1) следует, что Р-кратное ускорение может быть достигнуто, только когда доля непараллельного кода равна 0. Очевидно, что добиться этого практически невозможно .
Из таблицы 1 хорошо видно, что если, например, доля последовательного кода составляет 2%, то более чем 50-кратное ускорение в принципе получить невозможно. С другой стороны, по-видимому, нецелесообразно запускать такую программу на 2048 процессорах с тем, чтобы получить 4 9-кратное ускорение. Тем не менее, такая задача достаточно эффективно будет выполняться на 16 процессорах, а в некоторых случаях потеря 37% производительности при выполнении задачи на 32 процессорах может быть вполне приемлемой [5]. В некотором смысле, закон Амдала устанавливает предельное число процессоров, на котором программа будет выполняться с приемлемой эффективностью в зависимости от доли непараллельного кода. Эта формула не учитывает накладные расходы на обмены между процессорами, поэтому в реальной жизни ситуация может быть хуже.
Поэтому следующим шагом в тестировании возможностей вычислительного кластера с целью выявления доли последовательного кода конкретной программы было создание простого распараллеленного алгоритма для вычисления суммы значений из большого массива. Массив случайных чисел построчно передавался на заданное количество узлов. На каждом узле полученных данных суммировались и после того, как все результаты были получены, программа вычисляла окончательный результат, и выводила его на экран. Для тестирования был выбран этот алгоритм, так как он с одной стороны достаточно прост, а с другой - реальные изображения представляют собой тот же самый большой массив и в то же время распараллеливание по данным является целесообразным при обработке реальных аэрокосмических изображений. Оценка прироста производительности при запуске программы на разном количестве узлов производилась при помощи измерения времени, затраченного на выполнение вычислений. Так же для сравнения был выполнен запуск программы без применения алгоритма распараллеливания. представлен результат для массива размером 1000*1000 пикселей.
Из приведенного графика (рис. 2.4.2) видно, что производительность кластера возрастает не прямо пропорционально количеству задействованных вычислительных узлов. Это объясняется тем, что с возрастанием количество экземпляров программы возрастает объем межпрограммных взаимодействий. И в какой то момент времени это приводит к увеличению временных затрат.
Алгоритм выделения малоразмерных объектов заданного размера на аэрокосмических изображениях
На основе алгоритмов фильтрации скользящими окнами автором была разработана методика выделения малоразмерных объектов заданного размера, которая позволяет достоверно выделять объекты интереса с высокой точностью выделения контура. Для этих целей могут быть использованы аэроснимки и космические снимки земной поверхности сверхвысокого разрешения (порядка 1м). В работе были использованы аэроснимки и снимки с космического аппарата Иконос.
Рассмотрим решение этой тематической задачи дешифрирования на примере выделения зданий [39]. На рисунке 3.3.1 приведен аэроснимок в панхроматическом диапазоне. На снимке представлены следующие объекты: лесная растительность, луга, пашни, автомобильные дороги, здания сельского типа. интерпретации выделение зданий не вызывает затруднений, так как они легко дешифрируются по белому (почти белому) тону, характерной форме и размеру, а также по приуроченности к автомобильным дорогам. Однако, автоматизированные методы дешифрирования, например, посредством классификации исходного изображения методом пороговой обработки или кластерного анализа не позволяют достичь удовлетворительного результата, так как, наряду со зданиями, выделяются участки открытого грунта и автомобильных дорог, так как их тон практически совпадает с тоном зданий. Поэтому для автоматического выделения зданий исходные изображения должны быть подвергнуты предварительной обработке, с целью получения модифицированных изображений с более контрастированными строениями сельского типа. Для решения этой задачи обычно используется разностный алгоритм Розенфельда [3 6].
Эффективность этого алгоритма основана на свойстве медианной фильтрации сглаживать все объекты, размер которых меньше половины размера окна используемого медианного фильтра. Поэтому при вычислении разности между исходным и обработанным медианным фильтром изображений получается модифицированное изображение, на котором более ярким тоном отображаются объекты размером менее половины размера окна и интенсивностью более высокой, чем интенсивность фона в близлежащей окрестности. В данной работе для автоматизированного обнаружения зданий сельского типа, которые характеризуются определенными линейными размерами (примерно 12 пикселей), предлагается следующий модифицированный разностный алгоритм.
На первом этапе исходное изображение обрабатывается медианными фильтрами с двумя различными размерами окон 25x25 элементов и 11x11 элементов. В результате получается два модифицированных изображения, причем на первом будут сглажены все объекты с линейными размерами менее 13 пикселей, на втором менее б пикселей. На втором этапе вычисляется разность между вторым и первым изображением, полученным на первом этапе (рис. 3.3.2) . Двукратное применение медианной фильтрации позволяет избежать контрастирования ярких объектов, размер которых меньше размера зданий сельского типа.
На третьем этапе полученное разностное изображение подвергается пороговой обработке. Результат показан на рисунке 3.3.3.
Анализ результата работы этого алгоритма показывает, что он позволяет в автоматизированном режиме с высокой вероятностью правильного обнаружения (90%) выделять здания сельского типа. Вместе с тем, как видно из анализа изображения на рисунке 3.3.3, применение медианной фильтрации с большим размером окна приводит к снижению разрешающей способности и, как следствие, к потере информации о контурах зданий. При использовании этого алгоритма изображение, полученное после первой пороговой обработки, на четвертом этапе обрабатывается максимизирующим фильтром с большим размером окна (в два раза превышающим размер выделяемых объектов) . Полученное изображение умножается на исходное. В результате получается изображение (рис. 3.3.4.), на котором выделены небольшие участки, содержащие здания сельского типа, и сохранена разрешающая способность исходного снимка.
Похожие диссертации на Разработка технологии высокопроизводительной обработки аэрокосмических изображений методом параллельных вычислений
