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

• Автор: Русин, Евгений Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Новосибирск
• Количество страниц: 147 с. : ил.

ВВЕДЕНИЕ.

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

1.1. Характерные особенности алгоритмов обработки изображений.

1.2. Средства высокопроизводительной обработки изображений

1.2.1. Применение универсальных многопроцессорных ЭВМ.

1.2.2. Аппаратные средства последовательного выполнения операций клеточной логики.

1.3. Вертикальная обработка.

1.3.1. История вертикальной обработки.

1.3.2. Специализированные комплексы вертикальной обработки изображений.

1.4. Особенности параллельных систем вертикальной обработки.

1.4.1. Последовательное устройство управления.

1.4.2. Массив процессорных элементов
1.4.3. Соединительная сеть
1.4.4. Параллельная память
1.4.5. Система вводавывода.
1.5. Вертикальная обработка изображений на традиционных ЭВМ.
1.6. Выводы.
ГЛАВА 2. АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ВЕРТИКАЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ НА УНИВЕРСАЛЬНЫХ ЭВМ.
ж 2.1. Основные понятия и определения
2.2. Вертикальное представление данных в универсальной ЭВМ и
язык описания алгоритмов
2.2.1. Формат битовой плоскости изображения.
2.2.2. Расширение синтаксиса константных выражений
2.2.3. Расширенная индексация массивов
2.2.4. Параметризация типов данных
2.2.5. Дополнительные типы данных и операции
2.3. Базовые алгоритмы обработки битовых плоскостей.
2.3.1. Логические операции и присваивание плоскостей
2.3.2. Вычисление массы битовой плоскости.
2.3.3. Сдвиг битовой плоскости.
2.3.4. Проверки равенства двух плоскостей и
пустоты плоскости.
2.4. Алгоритмы арифметики изображений.
2.4.1. Алгоритмы сложения.
2.4.2. Алгоритмы вычитания
2.4.3. Алгоритмы умножения
2.4.4. Алгоритмы деления
2.4.5. Алгоритмы вычисления суммы значений пикселов.
2.4.6. Алгоритмы вычисления скалярного произведения изображений.
2.5. Базовые алгоритмы обработки полутоновых изображений
2.5.1. Сдвиг изображения
2.5.2. Построение гистограммы изображения.
2.5.3. Построение вертикального профиля изображения.
2.5.4. Построение горизонтального профиля изображения.
2.5.5. Аппроксимация множества уровня.
2.5.6. Утоньшение объекта бинарного изображения
методом ЗонгаСуня
2.5.7. Поворот изображения на малый угол
2.5.8. Построение поля евклидовых расстояний
бинарного изображения.
2.6. Выводы.
ГЛАВА 3. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЕРТИКАЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ НА УНИВЕРСАЛЬНЫХ МНОГОПРОЦЕССОРНЫХ ЭВМ.
3.1. Особенности организации систем обработки изображений на базе вертикального представления данных
на универсальных многопроцессорных ЭВМ
3.1.1. Многопроцессорные ЭВМ ССКЦ.
3.1.2. Распараллеливание алгоритмов вертикальной обработки изображений.
3.1.3. Требования к библиотеке параллельной вертикальной обработки изображений
на универсальных многопроцессорных ЭВМ
3.2. Библиотека параллельной обработки изображений РЬУТР
3.2.1. Форматы данных библиотеки.
3.2.2. Подпрограммы библиотеки.
3.2.3. Среда параллельной обработки изображений
3.3. Выводы
ГЛАВА 4. ВЫПОЛНЕНИЕ ВЫЧИСЛЕНИЙ НА ОСНОВЕ ВЕРТИКАЛЬНОГО ПРЕДСТАВЛЕНИЯ ДАННЫХ НА УНИВЕРСАЛЬНЫХ ЭВМ
4.1. Восстановление растровой карты высот
земной поверхности по набору горизонталей
4.1.1. Постановка задачи.
4.1.2. Алгоритм решения
4.1.3. Реализация вертикальной обработкой
4.1.4. Расчеты с помощью библиотеки VI
4.2. Масштабирование растровой карты высот.
4.3. Угловое выравнивание изображения печатного текста.
4.3.1. Постановка задачи.
4.3.2. Описание алгоритма
4.3.3. Реализация вертикальной обработкой
4.4. Высокоточные вычисления на базе вертикальной обработки
4.5. Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


В начале главы приводится сжатое описание используемых многопроцессорных ЭВМ высокопроизводительного кластера МВС М и сервера 0 и интерфейса передачи сообщений I как средства распараллеливания алгоритмов. В качестве основной стратегии распараллеливания алгоритмов ВОИ предлагается разрезание изображений на горизонтальные полосы. В свете этого анализируется эффективность алгоритмической базы операций с битовыми плоскостями, в результате чего формулируются рекомендации по распараллеливанию алгоритмов ВОИ. На основании этих рекомендаций, из предложенных во второй главе алгоритмов выделены перспективные для распараллеливания разрезанием на полосы все алгоритмы массовой арифметики и большинство алгоритмов обработки изображений. Предлагается альтернативный вариант распараллеливания алгоритма построения поля евклидовых расстояний. Далее формулируются требования к системе параллельной вертикальной ОИ на базе используемых программноаппаратных средств возможность обработки изображений как распределенных между процессорами, так и находящихся на одном процессоре, вычислительная топология звезда и пара I как средство реализации. РЬУ1Р, а также программная оболочка для нее среда параллельной обработки изображений, созданная для упрощения трудоемкого процесса удаленной разработки параллельных программ в среде ОС ишх. Четвертая глава посвящена решению практических задач на базе ВО. Рассматриваются две задачи цифровой картографии, решенные автором в среде параллельной обработки изображений с помощью библиотеки РЬУ1Р восстановление растровой карты высот земной поверхности по набору горизонталей и масштабирование растровой карты высот. Для алгоритма решения первой задачи рассматривается три способа распараллеливания неэффективность базового способа распараллеливания и эффективность для большого числа процессоров способа, обеспечивающего динамическую балансировку загрузки процессоров, подтверждает справедливость требования на библиотеку Р1. У1Р обеспечивать альтернативные способы организации параллельных вычислений. Выделяются узкие места всех трех параллельных алгоритмов, намечаются пути их устранения. Далее рассматривается реализация с помощью ВО решения задачи углового выравнивания изображения печатного текста, которая использовалась в качестве одной из компонент блока предобработки экспериментального читающего автомата на персональной ЭВМ. Отмечается временная и качественная эффективность алгоритма. Автор благодарен своим научным руководителям, кандидату физикоматематических наук Павлу Алексеевичу Киму и доктору технических наук, профессору Валерию Павловичу Пяткину, за постоянное внимание к работе, практические рекомендации, организационную помощь и моральную поддержку, а также всему коллективу Лаборатории обработки изображений ИВМиМГ СО РАН за полезные обсуждения результатов работы на лабораторных семинарах и отчетных сессиях. ГЛАВА 1. Цифровая обработка изображений ЦОИ относится к самым ранним применениям ЭВМ, ее основам посвящены как классические , , так и современные монографии. Под самим цифровым изображением ЦИ понимается двумерная пространственнодискретизованная проекция некоторой физической картины. При этом, каждому элементу дискретизации ЦИ, носящему название пиксел от английского i , приписывается значение из некоторого, как правило дискретного, набора чисел. Операцией ЦОИ называется функция, ставящая в соответствие ЦИ другое ЦИ. Основное предназначение операций ЦОИ улучшение изображения для его дальнейшего использования. При этом можно выделить два типа такого улучшения визуальное, критерием качества которого является удобство восприятия изображения для глаза человека, и улучшение для дальнейшей обработки ЭВМ, качество которого определяется эффективностью применения последующих алгоритмов извлечения признаков, распознавания и т. При выборе системы дискретизации изображений мозаики обычно останавливаются на одном из двух вариантов квадратной или шестиугольной гексагональной решетке . Во втором варианте элементом дискретизации является правильный шестиугольник, имеющий по одному общему ребру с каждым из своих соседей рис.