Содержание к диссертации
ВВЕДЕНИЕ 5
ГЛАВА 1. СИСТЕМЫ ВЕРТИКАЛЬНОЙ ОБРАБОТКИ И ОБРАБОТКА ИЗОБРАЖЕНИЙ 12
1.1. Характерные особенности алгоритмов обработки изображений 12
1.2. Средства высокопроизводительной обработки изображений.. 15
1.2.1. Применение универсальных многопроцессорных ЭВМ 15
1.2.2. Аппаратные средства последовательного выполнения операций клеточной логики 16
1.3. Вертикальная обработка 17
1.3.1. История вертикальной обработки 20
1.3.2. Специализированные комплексы вертикальной обработки изображений 22
1.4. Особенности параллельных систем вертикальной обработки 25
1.4.1. Последовательное устройство управления 26
1.4.2. Массив процессорных элементов 28
1.4.3. Соединительная сеть 29
1.4.4. Параллельная память 31
1.4.5. Система ввода-вывода 32
1.5. Вертикальная обработка изображений на традиционных ЭВМ 33
1.6. Выводы 35
ГЛАВА 2. АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ВЕРТИКАЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ НА УНИВЕРСАЛЬНЫХ ЭВМ 36
2.1. Основные понятия и определения 36
2.2. Вертикальное представление данных в универсальной ЭВМ и
язык описания алгоритмов 39
2.2.1. Формат битовой плоскости изображения 41
2.2.2. Расширение синтаксиса константных выражений 42
2.2.3. Расширенная индексация массивов 42
2.2.4. Параметризация типов данных 43
2.2.5. Дополнительные типы данных и операции 43
2.3. Базовые алгоритмы обработки битовых плоскостей 47
2.3.1. Логические операции и присваивание плоскостей 47
2.3.2. Вычисление массы битовой плоскости 47
2.3.3. Сдвиг битовой плоскости 49
2.3.4. Проверки равенства двух плоскостей и пустоты плоскости 50
2.4. Алгоритмы арифметики изображений 51
2.4.1. Алгоритмы сложения 51
2.4.2. Алгоритмы вычитания 52
2.4.3. Алгоритмы умножения 53
2.4.4. Алгоритмы деления 57
2.4.5. Алгоритмы вычисления суммы значений пикселов 63
2.4.6. Алгоритмы вычисления скалярного произведения изображений 64
2.5. Базовые алгоритмы обработки полутоновых изображений 67
2.5.1. Сдвиг изображения 67
2.5.2. Построение гистограммы изображения 68
2.5.3. Построение вертикального профиля изображения 71
2.5.4. Построение горизонтального профиля изображения 72
2.5.5. Аппроксимация множества уровня 73
2.5.6. Утоньшение объекта бинарного изображения методом Зонга-Суня 76
2.5.7. Поворот изображения на малый угол 81
2.5.8. Построение поля евклидовых расстояний бинарного изображения 85
2.6. Выводы 90
ГЛАВА 3. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЕРТИКАЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ НА УНИВЕРСАЛЬНЫХ МНОГОПРОЦЕССОРНЫХ ЭВМ 91
3.1. Особенности организации систем обработки изображений на базе вертикального представления данных на универсальных многопроцессорных ЭВМ 91
3.1.1. Многопроцессорные ЭВМ ССК1Д 91
3.1.2. Распараллеливание алгоритмов вертикальной обработки изображений 93
3.1.3. Требования к библиотеке параллельной вертикальной обработки изображений на универсальных многопроцессорных ЭВМ 97
3.2. Библиотека параллельной обработки изображений PLVIP 99
3.2.1. Форматы данных библиотеки 100
3.2.2. Подпрограммы библиотеки 101
3.2.3. Среда параллельной обработки изображений 104
3.3. Выводы 105
ГЛАВА 4. ВЫПОЛНЕНИЕ ВЫЧИСЛЕНИЙ НА ОСНОВЕ ВЕРТИКАЛЬНОГО ПРЕДСТАВЛЕНИЯ ДАННЫХ НА УНИВЕРСАЛЬНЫХ ЭВМ 107
4.1. Восстановление растровой карты высот земной поверхности по набору горизонталей 107
4.1.1. Постановка задачи 107
4.1.2. Алгоритм решения 109
4.1.3. Реализация вертикальной обработкой 118
4.1.4. Расчеты с помощью библиотеки PL VIP 121
4.2. Масштабирование растровой карты высот 125
4.3. Угловое выравнивание изображения печатного текста 128
4.3.1. Постановка задачи 128
4.3.2. Описание алгоритма 129
4.3.3. Реализация вертикальной обработкой 131
4.4. Высокоточные вычисления на базе вертикальной обработки 134
4.5. Выводы 136
ЗАКЛЮЧЕНИЕ 137
ЛИТЕРАТУРА 138
ПРИЛОЖЕНИЕ
Акты о внедрении результатов диссертационной работы 146
Введение к работе
Актуальность проблемы. Гигантские объемы данных дистанционного зондирования Земли (информационные потоки до 128 Мбит/с при объеме одного изображения до 1 Гбайт, суточный объем принимаемой информации - до 60 Гбайт), а также потребность их интерпретации в реальном времени (в задачах мониторинга лесных пожаров, наводнений и пр.) требуют высокой производительности ЭВМ, привлекаемых к их обработке. Как известно, существует два основных способа повышения производительности вычислительных систем: увеличение тактовой частоты вычислителя и распределение вычислительной нагрузки между несколькими функциональными устройствами, действующими одновременно (параллельно). На сегодняшний день очевидно, что только повышением быстродействия микропроцессора требуемой производительности достичь нереально. Многопроцессорная обработка является здесь безальтернативным средством получения результатов за требуемое время, при этом используемые алгоритмы должны допускать свое параллельное исполнение. Вместе с тем, на сегодняшний день не существует доступных программных средств, поддерживающих процесс разработки прикладных программ решения задач обработки изображений (ОИ) на многопроцессорных ЭВМ. Проведение методических и практических исследований, направленных на создание таких программных средств, является, таким образом, актуальной научной задачей.
В 70-х годах прошлого века для поддержки решения задач, допускающих массовую обработку информации (в том числе, задач ОИ) были созданы специализированные мелкозернистые SIMD-комплексы, состоящие из очень большого (до нескольких десятков тысяч, а в проектах - сотни тысяч) числа синхронно действующих однобитных процессорных элементов с собственной памятью, объединенных соединительной сетью. Характерной особенностью таких ЭВМ стал вертикальный (или пословно-параллельный, поразряд но-последовательный) подход к обработке данных (вертикальная обработка, ВО). Модель данных, используемая при ВО, не нашла широкого распространения вне спецпроцессоров, в частности, неисследованными на сегодняшний день являются вопросы реализации вертикальной обработки изображений (ВОИ) на ЭВМ общего назначения. Между тем, для исследования этих вопросов существуют следующие предпосылки:
1. Производительность поразрядно-последовательных вычислений растет с уменьшением разрядности обрабатываемых данных, что позволяет сделать более эффективной обработку малоразрядньтх данных, например полутоновых малоградационных изображений.
2. При ВО не существует ограничений на размер обрабатываемых данных, что позволяет выполнять вычисления с произвольной точностью.
3. Алгоритмическая база ВОИ на SIMD-системах эффективно реализуется на ЭВМ общего назначения побитовыми логическими операциями между машинными словами и их сдвигами; современные 64-разрядные микропроцессоры позволяют одновременно обрабатывать 64 пиксела изображения.
4. Массовый параллелизм ВО позволяет использовать для ее реализации универсальные многопроцессорные ЭВМ.
Представленные в диссертации исследования проводились в рамках:
• Планов НИР ИВМиМГ СО РАН.
• ФЦНТП Миннауки РФ «Исследования и разработки по приоритетным направлениям развития науки и техники» (проект № 2.37.04.01.04).
• Программы №13 фундаментальных исследований Президиума РАН «Изменение окружающей среды и климата: природные катастрофы» (проект № 13.10).
• ФЦП «Государственная поддержка интеграции высшего образования и фундаментальной науки» (проект И0106М202).
• Проектов РФФИ №№ 03-07-90239 и 99-07-90422.
Целью диссертационной работы является разработка и исследование методов вертикальной обработки изображений на традиционных вычисли тельных средствах, а также разработка и реализация программных комплексов ВОИ на универсальных, в том числе многопроцессорных, ЭВМ,
Научную новизну работы раскрывают ее следующие результаты:
1. Создана методика использования ВО при решении задач обработки изображений на универсальных, в том числе многопроцессорных, ЭВМ.
2. Разработаны вертикальные версии алгоритмов, играющих ключевую роль при решении задач ОИ (попиксельной арифметики, вычисления статистических характеристик изображения, геометрических трансформаций, дискретной топологии), ориентированные на универсальные ЭВМ,
3. На многопроцессорных комплексах МВС-1000/М и RM60G-E30 (ИВМиМГ СО РАН) разработана и реализована библиотека параллельной обработки изображений PLVIP, основанная на ВО, и создана Unix-среда параллельной обработки изображений.
4. С использованием разработанных алгоритмов и технологий решены прикладные задачи цифровой картографии (аппроксимация растровой карты высот по известным горизонталям и масштабирование растровой карты высот) и предобработки изображений (угловое выравнивание изображения печатного текста).
Методы исследования. Основные результаты работы получены с использованием методов цифровой обработки изображений, системного и прикладного программирования, дискретной геометрии и топологии.
Практическая ценность. Среда параллельной обработки изображений и библиотека PLVIP являются инструментами создания прикладных параллельных программ. Разработанные и реализованные программные решения внедрены в практику оперативной работы Западно-Сибирского регионального центра приема и обработки спутниковых данных (г. Новосибирск) и Центра ДЗЗ Югорского НИИ информационных технологий (г. Ханты-Мансийск). Материалы аналитического обзора средств высокопроизводительной обработки изображений использовались при проведении лекций и лабораторных занятий в Высшем колледже информатики НГУ.
Апробации работы. Результаты работы докладывались и обсуждались на Международной научно-методической конференции «Новые информационные технологии в университетском образовании» (Томск, 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], Я.И. Фета [345 35, 47], О.Л. Бэндман [1], П.А. Кима [51, 52], А.П. Важенина [3, 4] и др.). Из печатных работ, опубликованных диссертантом в соавторстве, в диссертацию вошли только те результаты, в получении которых он принял непосредственное творческое участие на всех этапах: от постановки задач и теоретического анализа алгоритмов до написания программ и проведения вычислительных экспериментов.
Структура и объем работы. Диссертация написана на 147 листах, состоит из введения, четырех глав, заключения и приложения, содержит 27 иллюстраций, 5 таблиц и список используемой литературы из 78 наименований.
В первой главе выделяется два основных подхода к организации высокопроизводительной ОИ - использование многопроцессорных ЭВМ общего назначения и специализированных систем вертикальной обработки. В результате аналитического обзора ЭВМ последнего класса определены характерные особенности реализации с их использованием алгоритмов ОИ- Предлагается гибридный подход к ОИ: проводить обработку на традиционных ЭВМ изображений, представленных набором разрядных плоскостей - в формате, определяющем ВО. Показывается, что такой подход расширяет алгоритмические возможности ВО и вместе с тем сохраняет ряд ее полезных свойств, отсутствующих при традиционном способе обработки данных.
Вторая глава посвящена алгоритмическому обеспечению ВОИ на базе универсальных ЭВМ. После введения необходимых определений рассмотрено расширение языка программирования С, использующееся при дальнейшем описании алгоритмов и предложенное с целью повышения наглядности этого описания. Распшрения отражают специфику алгоритмов и включают в себя параметрическое задание размеров изображений и разрядности значений пикселов, а также использование новых встроенных типов (битовых плоскостей) и операций над ними, В качестве формата единицы вертикальной обработки изображений для ЭВМ общего назначения, битовой плоскости, предлагается построчно-непрерывное представление, являющееся ком промиссным вариантом отображения двумерной топологии изображения на одномерное ОЗУ- На базе этого формата строятся более сложные типы данных: бинарное, целочисленное и действительнозначное изображение. Рассматривается реализация алгоритмической основы ВОИ - операций с битовыми плоскостями- На этой базе разрабатываются арифметические алгоритмы попиксельного сложения, вычитания, умножения, деления, суммирования значений пикселов и скалярного произведения изображений. Разрабатываются базовые алгоритмы обработки полутоновых изображений: вычисления гистограммы и профилей изображений, построения линии уровни значений пикелов, поворота на малый угол, утоньшения (скелетизации) по Зонгу-Суню, построения поля евклидовых расстояний бинарного изображения.
Третья глава содержит описание разработанных систем параллельной обработки изображений на базе ВО. В начале главы приводится сжатое описание используемых многопроцессорных ЭВМ (высокопроизводительного кластера МВС-1000/М и SMP-сервера RM600-E30) и интерфейса передачи сообщений MPI как средства распараллеливания алгоритмов. В качестве основной стратегии распараллеливания алгоритмов ВОИ предлагается разрезание изображений на горизонтальные полосы. В свете этого анализируется эффективность алгоритмической базы - операций с битовыми плоскостями, в результате чего формулируются рекомендации по распараллеливанию алгоритмов ВОИ- На основании этих рекомендаций, из предложенных во второй главе алгоритмов выделены перспективные для распараллеливания разрезанием на полосы (все алгоритмы массовой арифметики и большинство алгоритмов обработки изображений). Предлагается альтернативный вариант распараллеливания алгоритма построения поля евклидовых расстояний.
Далее формулируются требования к системе параллельной вертикальной ОИ на базе используемых программно-аппаратных средств: возможность обработки изображений как распределенных между процессорами, так и на-ходящихся на одном процессоре, вычислительная топология «звезда» и пара C+MPI как средство реализации. Рассматривается реализованная на этих принципах библиотека параллельной вертикальной обработки изображений PLVIP, а также проіраммная оболочка для нее - среда параллельной обработки изображений, созданная для упрощения трудоемкого процесса удаленной разработки параллельных программ в среде ОС Unix.
Четвертая глава посвящена решению практических задач на базе ВО. Рассматриваются две задачи цифровой картографии, решенные автором в среде параллельной обработки изображений с помощью библиотеки PLVTP -восстановление растровой карты высот земной поверхности по набору горизонталей и масштабирование растровой карты высот. Для алгоритма решения первой задачи рассматривается три способа распараллеливания; неэффективность базового способа распараллеливания и эффективность для большого числа процессоров способа, обеспечивающего динамическую балансировку загрузки процессоров, подтверждает справедливость требования на библиотеку PLVIP обеспечивать альтернативные способы организации параллельных вычислений. Выделяются узкие места всех трех параллельных алгоритмов, намечаются пути их устранения. Далее рассматривается реализация с помощью ВО решения задачи углового выравнивания изображения печатного текста, которая использовалась в качестве одной из компонент блока предобработки экспериментального читающего автомата на персональной ЭВМ. Отмечается временная и качественная эффективность алгоритма. Приводится пример высокой точности вычислений при применении ВО, достигаемой за счет произвольного увеличения разрядности обрабатываемых данных.
А Автор благодарен своим научным руководителям, кандидату физико-математических наук Павлу Алексеевичу Киму и доктору технических наук, профессору Валерию Павловичу Пяткину, за постоянное внимание к работе, практические рекомендации, организационную помощь и моральную поддержку, а также всему коллективу Лаборатории обработки изображений ИВМиМГ СО РАН за полезные обсуждения результатов работы на лабораторных семинарах и отчетных сессиях.
