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

ВВЕДЕНИЕ.

ГЛАВА 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. АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ВЕРТИКАЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ НА УНИВЕРСАЛЬНЫХ ЭВМ. w 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. Библиотека параллельной обработки изображений PLVIP.

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. Расчеты с помощью библиотеки PLVIP.

4.2. Масштабирование растровой карты высот.

4.3. Угловое выравнивание изображения печатного текста.

4.3.1. Постановка задачи.

4.3.2. Описание алгоритма.

4.3.3. Реализация вертикальной обработкой.

4.4. Высокоточные вычисления на базе вертикальной обработки.

4.5. Выводы.

Актуальность проблемы. Гигантские объемы данных дистанционного зондирования Земли (информационные потоки до 128 Мбит/с при объеме одного изображения до 1 Гбайт, суточный объем принимаемой информации - до 60 Гбайт), а также потребность их интерпретации в реальном времени (в задачах мониторинга лесных пожаров, наводнений и пр.) требуют высокой производительности ЭВМ, привлекаемых к их обработке. Как известно, существует два основных способа повышения производительности вычислительных систем: увеличение тактовой частоты вычислителя и распределение вычислительной нагрузки между несколькими функциональными устройствами, действующими одновременно (параллельно). На сегодняшний день очевидно, что только повышением быстродействия микропроцессора требуемой производительности достичь нереально. Многопроцессорная обработка является здесь безальтернативным средством получения результатов за требуемое время, при этом используемые алгоритмы должны допускать свое параллельное исполнение. Вместе с тем, на сегодняшний день не существует доступных программных средств, поддерживающих процесс разработки прикладных программ решения задач обработки изображений (ОИ) на многопроцессорных ЭВМ. Проведение методических и практических исследований, направленных на создание таких программных средств, является, таким образом, актуальной научной задачей.

В 70-х годах прошлого века для поддержки решения задач, допускающих массовую обработку информации (в том числе, задач ОИ) были созданы специализированные мелкозернистые SIMD-комплексы, состоящие из очень большого (до нескольких десятков тысяч, а в проектах - сотни тысяч) числа синхронно действующих однобитных процессорных элементов с собственной памятью, объединенных соединительной сетью. Характерной особенностью таких ЭВМ стал вертикальный (или пословно-параллельный, поразрядно-последовательный) подход к обработке данных (вертикальная обработка, ВО). Модель данных, используемая при ВО, не нашла широкого распространения вне спецпроцессоров, в частности, неисследованными на сегодняшний день являются вопросы реализации вертикальной обработки изображений (ВОИ) на ЭВМ общего назначения. Между тем, для исследования этих вопросов существуют следующие предпосылки:

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

2. При ВО не существует ограничений на размер обрабатываемых данных, что позволяет выполнять вычисления с произвольной точностью.

3. Алгоритмическая база ВОИ на SIMD-системах эффективно реализуется на ЭВМ общего назначения побитовыми логическими операциями между машинными словами и их сдвигами; современные 64-разрядные микропроцессоры позволяют одновременно обрабатывать 64 пиксела изображения.

4. Массовый параллелизм ВО позволяет использовать для ее реализации универсальные многопроцессорные ЭВМ.

Представленные в диссертации исследования проводились в рамках:

• Планов НИР ИВМиМГ СО РАН.

• ФЦНТП Миннауки РФ «Исследования и разработки по приоритетным направлениям развития науки и техники» (проект № 2.37.04.01.04).

• Программы №13 фундаментальных исследований Президиума РАН «Изменение окружающей среды и климата: природные катастрофы» (проект № 13.10).

• ФЦП «Государственная поддержка интеграции высшего образования и фундаментальной науки» (проект И0106\1202).

• Проектов РФФИ №№ 03-07-90239 и 99-07-90422.

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

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

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. С использованием разработанных алгоритмов и технологий решены прикладные задачи цифровой картографии (аппроксимация растровой карты высот земной поверхности по известным горизонталям и масштабирование растровой карты высот) и предобработки изображений (угловое выравнивание изображения печатного текста).

1. Бандман О.Л. Однородные структуры и параллельное микропрограммирование // Проблемы обработки информации. - Новосибирск, 1983. -(Вычислительные системы; выпуск 100). - 11-33.

2. Важенин А.П. Алгоритмы ускоренного высокоточного умножения для ассоциативного параллельного процессора // Математическое и архитектурное обеспечение параллельных вычислений. - Новосибирск, 1989. -С. 6-21.

3. Важенин А.П., Вартазарян А.Э., Фет Я.И. Морфологический подход к анализу вычислительных систем вертикальной обработки. - Препринт № 982. - Новосибирск: ВЦ СО РАН, 1993.

4. Гилмор П. Высокопараллельный процессор (МРР) // СуперЭВМ. Аппаратная и программная реализация. - М.: Радио и связь, 1991. -С. 215-266.

5. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. - Новосибирск: Наука (Сибирское отделение), 1966.

6. Иззо Н.Ф., Коулз В. Опознавание форменных элементов крови с помощью сканирующей системы // Электроника. - 1962. - Т. 35, № 17. -С. 21-27.

7. Карцев М.А. Арифметика цифровых машин. - М.: Наука, 1968. ^ -139-

8. Ким П.А. Шкаловое представление множеств, поддерживаемое ортогональной обработкой данных // Труды семинара «Экспертные системы», -М.:МДНТП, 1986.-С. 134-138.

9. Ким П.А. Язык СЕТЛ как основа СУБД // Экспериментальная информатика. - Новосибирск, 1981. - 12-20.

10. Колесников А.Н., Тришина Е.В. Параллельный алгоритм утоньшения бинарных изображений // Автометрия. - 1995. - № 6. - 7-14.

11. Корнеев В.Д. Параллельное программирование в MPI. - Новосибирск: Изд. СО РАН, 2000.

12. Крайзмер Л.П. и др. Ассоциативные запоминающие устройства. — Д.: Энергия, 1967.

13. Малышкин В.Э. Организация паралельных вычислений в крупноблочных линейных иерархических МВС // Программирование. - 1991. - №4. -С. 82-94.

14. Малышкин В.Э. Параллельное программирование мультикомпьютеров: Учеб. пособие. - Ярославль, 1999.

15. Методы компьютерной обработки изображений / Под ред. А.В. Сойфера. - М.: Физматлит, 2001.

16. Миренков Н.Н. Параллельное программирование для многомодульных ifhu вычислительных систем, - М.: Радио и связь, 1989.

17. Непомнящая А.Ш., Владыко М.А. Сравнение моделей ассоциативного вычисления // Программирование. - 1997. - № 6. — 41-50.

18. Однородные микроэлектронные ассоциативные процессоры / Под. ред. И. В. Прангишвили. - М . : Советское радио, 1973.

19. Озкарахан Э. Машины баз данных и управление базами данных. - М.: Мир, 1989. - 140-

20. Поттер Дж., Мейландер У.С. Матричные Супер-ЭВМ // ТИЭР. - 1989. - ^ ' Т. 77, №12.-С. 115-135.

21. Престон К., Дафф М.Дж.Б., Левьяльди С, Норгрен Ф., Ториваки Дз. Основы клеточной логики с приложениями к обработке изображений в медицине // ТИИЭР. - 1979. - Т. 67, № 5. - 149-185.

22. Престон К., Норгрен П.Е. Распознавание образов вычислительной маши- ^ ной с помощью процессора изображений // Электроника. - 1972. - Т. 45, № 22. - 26-27.

23. Прэтт У. Цифровая обработка изображений (в двух томах). - М: Мир, 1982.

24. Русин Е.В. Некоторые алгоритмы обработки бинарных изображений, опирающиеся на метод вертикального процессирования // Труды конференции молодых ученых. - Новосибирск: ИВМиМГ СО РАН, 2001. -С. 228-235. #

25. Русин Е.В. Об одном алгоритме углового выравнивания изображения печатного текста // Тезисы докладов 2-й Международной конференции молодых ученых и студентов «Актуальные вопросы современной науки». -Самара, 2001. - 107-108.

26. Русин Е.В. Об одном массовом алгоритме расчета поля расстояний до множества точек на дискретной растровой плоскости // Труды конференции молодых ученых. - Новосибирск: РГОМиМГ СО РАН, 2002. - 131-137. ^ « 27. Русин Е.В. Параллельная библиотека векторной арифметики на основе вертикальной обработки данных // Тезисы докладов Международной конференции молодых ученых по математическому моделированию и информационным технологиям. - Новосибирск, 2002. - 68.

28. Русин Е.В. Параллельный алгоритм аппроксимации матрицы высот земной поверхности по заданным горизонталям // Труды Международной конференции «Математические методы в геофизике». - Новосибирск: ИВМиМГ СО РАН, 2003, - Ч. 2. - 612-617.

29. Фет Я.И. Вертикальная обработка как основа крупноблочной архитектуры // Известия АН СССР (серия «Техническая кибернетика»).- 1986, № 5, 139-152.

30. Фет Я.И. Параллельные процессоры для управляюпщх систем. - М.: Энергоиздат, 1981.

31. Фостер К. Ассоциативные параллельные процессоры. - М.: Энергоиздат, 1981.

32. Фролов А.В., Фролов Г.В. Программирование видеоадаптеров CGA, EGA и VGA. - М.: Диалог МИФИ, 1992. ^ #