Актуальность проблемы. Гигантские объемы данных дистанционного зондирования Земли (информационные потоки до 128 Мбит/с при объеме одного изображения до 1 Гбайт, суточный объем принимаемой информации — до 60 Гбайт), а также потребность их интерпретации в реальном времени (в задачах мониторинга лесных пожаров, наводнений и пр.) требуют высокой производительности ЭВМ, привлекаемых к их обработке. Как известно, существует два основных способа повышения производительности вычислительных систем: увеличение тактовой частоты вычислителя и распределение вычислительной нагрузки между несколькими функциональными устройствами, действующими одновременно (параллельно). На сегодняшний день очевидно, что только повышением быстродействия микропроцессора требуемой производительности достичь нереально. Многопроцессорная обработка является здесь безальтернативным средством получения результатов за требуемое время, при этом используемые алгоритмы должны допускать свое параллельное исполнение. Вместе с тем, на сегодняшний день не существует доступных программных средств, поддерживающих процесс разработки прикладных программ решения задач обработки изображений (ОИ) на многопроцессорных ЭВМ. Проведение методических и практических исследований, направленных на создание таких программных средств, является, таким образом, актуальной научной задачей.
В 70-х годах прошлого века для поддержки решения задач, допускающих массовую обработку информации (в том числе, задач ОИ) были созданы специализированные мелкозернистые SIMD-комплексы, состоящие из очень большого (до нескольких десятков тысяч, а в проектах — сотни тысяч) числа синхронно действующих однобитных процессорных элементов с собственной памятью, объединенных соединительной сетью. Характерной особенностью таких ЭВМ стал вертикальный (или пословно-параллельный, поразрядно-последовательный) подход к обработке данных (вертикальная обработка, ВО). Модель данных, используемая при ВО, не нашла широкого распространения вне спецпроцессоров, в частности, неисследованными на сегодняшний день являются вопросы реализации вертикальной обработки изображений (ВОИ) на ЭВМ общего назначения. Между тем, для исследования этих вопросов существуют следующие предпосылки:
1. Производительность поразрядно-последовательных вычислений растет с уменьшением разрядности обрабатываемых данных, что позволяет сделать более эффективной обработку малоразрядных данных, например полутоновых малоградационных изображений.
2. При ВО не существует ограничений на размер обрабатываемых данных, что позволяет выполнять вычисления с произвольной точностью.
3. Алгоритмическая база ВОИ на SIMD-системах эффективно реализуется на ЭВМ общего назначения побитовыми логическими операциями между машинными словами и их сдвигамисовременные 64-разрядные микропроцессоры позволяют одновременно обрабатывать 64 пиксела изображения.
4. Массовый параллелизм ВО позволяет использовать для ее реализации универсальные многопроцессорные ЭВМ.
Представленные в диссертации исследования проводились в рамках:
• Планов НИР ИВМиМГ СО РАН.
• ФЦНТП Миннауки РФ «Исследования и разработки по приоритетным направлениям развития науки и техники» (проект № 2.37.04.01.04).
• Программы № 13 фундаментальных исследований Президиума РАН «Изменение окружающей среды и климата: природные катастрофы» (проект № 13.10).
• ФЦП «Государственная поддержка интеграции высшего образования и фундаментальной науки» (проект И1 061 202).
• Проектов РФФИ №№ 03−07−90 239 и 99−07−90 422.
Целью диссертационной работы является разработка и исследование методов вертикальной обработки изображений на традиционных вычислительных средствах, а также разработка и реализация программных комплексов ВОИ на универсальных, в том числе многопроцессорных, ЭВМ.
Научную новизну работы раскрывают ее следующие результаты:
1. Создана методика использования ВО при решении задач обработки изображений на универсальных, в том числе многопроцессорных, ЭВМ.
2. Разработаны вертикальные версии алгоритмов, играющих ключевую роль при решении задач ОИ (попиксельной арифметики, вычисления статистических характеристик изображения, геометрических трансформаций, дискретной топологии), ориентированные на универсальные ЭВМ.
3. На многопроцессорных комплексах МВС-1000/М и RM600-E30 (ИВМиМГ СО РАН) разработана и реализована библиотека параллельной обработки изображений PLVIP, основанная на ВО, и создана Unix-среда параллельной обработки изображений.
4. С использованием разработанных алгоритмов и технологий решены прикладные задачи цифровой картографии (аппроксимация растровой карты высот по известным горизонталям и масштабирование растровой карты высот) и предобработки изображений (угловое выравнивание изображения печатного текста).
Методы исследования. Основные результаты работы получены с использованием методов цифровой обработки изображений, системного и прикладного программирования, дискретной геометрии и топологии.
Практическая ценность. Среда параллельной обработки изображений и библиотека PLVEP являются инструментами создания прикладных параллельных программ. Разработанные и реализованные программные решения внедрены в практику оперативной работы Западно-Сибирского регионального центра приема и обработки спутниковых данных (г. Новосибирск) и Центра ДЗЗ Югорского НИИ информационных технологий (г. Ханты-Мансийск). Материалы аналитического обзора средств высокопроизводительной обработки изображений использовались при проведении лекций и лабораторных занятий в Высшем колледже информатики НГУ.
Апробация работы. Результаты работы докладывались и обсуждались на Международной научно-методической конференции «Новые информационные технологии в университетском образовании» (Томск, 2000 г.), Конференциях молодых ученых ИВМиМГ СО РАН (Новосибирск, 2001;2002 гг.), Международных конференциях молодых ученых по математике, математическому моделированию и информационным технологиям (Новосибирск, 2001;2002 гг.), Международной конференции «Automation, Control and Information Technology» (Новосибирск, 2002 г.), VI Российско-Немецком семинаре «Распознавание образов и понимание изображений» (пос. Катунь Алтайского края, 2003 г.), Международной конференции «Математические методы в геофизике» (Новосибирск, 2003г), Международной конференции по вычислительной математике МКВМ-2004 (Новосибирск, 2004 г.), а также на объединенном семинаре ИВМиМГ (2004 г.), семинарах Кафедры математических методов геофизики НГУ (1998;2004 гг.), Лаборатории обработки изображений ИВМиМГ СО РАН (1998;2004 гг.) и Лаборатории цифровых методов обработки изображений ИАЭ СО РАН (2004 г.).
Результаты исследований неоднократно отмечались наградами: третья премия Конференции молодых ученых ИВМиМГ СО РАН (2001 г.), грант победителя Конкурса научных проектов молодых ученых, посвященного 45-летию СО РАН (2002 г.), третья премия за лучший доклад молодого ученого на VI Российско-Немецком семинаре «Распознавание образов и понимание изображений» (2003 г.).
Публикации. По теме диссертации опубликовано 10 печатных работ [25−30, 53−55].
Личный вклад автора. Основные научные и практические результаты диссертации получены автором лично. П. А. Киму принадлежит первичная постановка задачи аппроксимации растровой карты высот. Ряд алгоритмов ВОИ базируется на традиционных версиях классических алгоритмов, алгоритмы массовой арифметики основаны на известных поразрядных алгоритмах. При разработке и создании параллельных технологий обработки изображений были использованы достижения и опыт специалистов ИВМиМГ СО РАН (В.Э. Малышкина [14, 15], Я. И. Фета [34, 35, 47], О. Л. Бандман [1], П. А. Кима [51, 52], А. П. Важенина [3, 4] и др.). Из печатных работ, опубликованных диссертантом в соавторстве, в диссертацию вошли только те результаты, в получении которых он принял непосредственное творческое участие на всех этапах: от постановки задач и теоретического анализа алгоритмов до написания программ и проведения вычислительных экспериментов.
Структура и объем работы. Диссертация написана на 147 листах, состоит из введения, четырех глав, заключения и приложения, содержит 27 иллюстраций, 5 таблиц и список используемой литературы из 78 наименований.
4.5. Выводы.
4.1. Предложен и реализован с использованием библиотеки PLVIP алгоритм восстановления растровой карты высот земной поверхности по набору горизонталей. Для алгоритма рассмотрено несколько способов распараллеливания. Прямое распараллеливание разрезанием изображений на полосы оказалось эффективным только для небольшого (2−3) числа процессоров, при большем числе процессоров более эффективным оказался способ, обеспечивающий балансировку нагрузки на процессоры. Данный пример подтверждает правильность требования на библиотеку PLVIP обеспечивать альтернативные способы распараллеливания вычислений.
4.2. Предложен и реализован с использованием библиотеки PLVIP алгоритм масштабирования растровой карты высот. Алгоритм ориентирован на карты с небольшими локальными перепадами высот, резкие скачки уровней сглаживаются алгоритмом.
4.3. Разработан алгоритм углового выравнивания изображения печатного текста, вертикальная реализация которого использовалась в качестве одной из компонент блока предварительной обработки экспериментального читающего автомата на персональной ЭВМ типа IBM PC. Временные и качественные характеристики алгоритма позволяют считать его реализацию эффективной.
4.4. На примере скалярного произведения векторов с многоразрядными компонентами показан высокоточный характер вертикальной обработки. Показано, что точность вычислений, достигнутая простым увеличением числа битовых плоскостей обрабатываемых векторов-изображений, превосходит точность, обеспечиваемую стандартными средствами.
— 137 -ЗАКЛЮЧЕНИЕ.
В заключение сформулируем основные результаты диссертации.
1. Для реализации алгоритмов обработки изображений на ЭВМ общего назначения, в том числе многопроцессорных, предложено использовать метод вертикальной обработки, предложенный В. Шуманом в 60-х годах прошлого века и ранее применявшийся при вычислениях на специализированных SIMD-архитектурах.
2. Разработана методика применения вертикальной обработки к решению задач обработки изображений на универсальных многопроцессорных ЭВМ.
3. Разработаны вертикальные реализации базовых алгоритмов обработки изображений, ориентированные на универсальные ЭВМ.
4. На многопроцессорных комплексах МВС-1000/М и RM600-E30 реализована мобильная библиотека параллельной обработки изображений PLVIP, основанная на вертикальной обработке. Создана программная оболочка библиотеки PLVIP — Unix-среда параллельной обработки изображений, упрощающая удаленную разработку параллельных программ. Данные программные средства внедрены в оперативную работу Центра ДЗЗ Югорского НИИ информационных технологий (г. Ханты-Мансийск) и ЗападноСибирского регионального центра приема и обработки спутниковых данных (г. Новосибирск).
5. С использованием разработанных алгоритмов и технологий решены прикладные задачи цифровой картографии (аппроксимация растровой карты высот земной поверхности по известным горизонталям и масштабирование растровой карты высот) и предобработки изображений (угловое выравнивание изображения печатного текста).
