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

> ¿с

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П.КОРОЛЕВА

На правах рукописи

ПОПОВ Сергей Борисович

__

МОДЕЛИРОВАНИЕ ПОТОКОВЫХ СЕТЕЙ И МЕТОДЫ ОРГАНИЗАЦИИ ДВУМЕРНЫХ МАССИВОВ ДАННЫХ ПРИ ОБРАБОТКЕ ИЗОБРАЖЕНИЙ

Специальность 05.13.16 -"Применение вычислительной техники, математического моделирования и математических методов

в научных исследованиях"

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор В.В. Сергеев

Самара 1998

ОГЛАВЛЕНИЕ

СПИСОК СОКРАЩЕНИИ........................................................................4

ВВЕДЕНИЕ...............................................................................................5

1. ПРОБЛЕМЫ ОРГАНИЗАЦИИ ДАННЫХ И ПРОЦЕССА ВЫЧИСЛЕНИЙ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ ОБРАБОТКИ ИЗОБРАЖЕНИЙ.......................................................... 16

1.1. Основные особенности компьютерной обработки изображений.............................................................................16

1.2. Обобщенная структура программных средств систем обработки изображений...........................................................18

1.3. Классификация алгоритмов обработки изображений............25

1.4. Методы организации обработки изображений в АСОИз.......27

1.5. Организация данных при обработке изображений................32

Выводы............................................................................................36

2. МОДЕЛЬ ПРОЦЕССОВ ОБРАБОТКИ ИЗОБРАЖЕНИЙ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ........................................38

2.1. Потоковая организация обработки изображений...................38

2.2. Формальный метод описания программ обработки изображений.............................................................................42

2.3. Модель системы обработки изображений с возможностью потоковой организации вычислений.............52

Выводы............................................................................................58

3. ПРОГРАММНОЕ МОДЕЛИРОВАНИЕ ПОТОКОВЫХ СЕТЕЙ ПРОЦЕССОВ ОБРАБОТКИ ИЗОБРАЖЕНИЙ..................................60

3.1. Принципы программной реализации модели взаимодействующих последовательных процессов...................60

3.2. Программный комплекс моделирования потоковых сетей задач обработки изображений.................................................64

3.3. Исследование типовых схем организации потоковых

сетей при обработке изображений.......................................... 68

3.4. Подсистема планирования организации вычислительного процесса потоковой обработки изображений........................76

Выводы.................................................................................................78

4. РЕАЛИЗАЦИЯ ПРОГРАММНЫХ СРЕДСТВ ПОТОКОВОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ В МНОГОЗАДАЧНЫХ ОПЕРАЦИОННЫХ СИСТЕМАХ.......................................................80

4.1. Модульный принцип построения программного обеспечения обработки изображений.....................................80

4.2. Возможности многозадачных операционных систем по организации межмодульных связей АСОИз...........................81

4.3. Структура программных средств системы обработки изображений с возможностью потоковой организации вычислений..............................................................................84

4.4. Анализ эффективности потоковых методов организации обработки изображений...........................................................87

4.5. Исследование эффективности модульного программного обеспечения при решении задач обработки и моделирования изображений..................................................98

Выводы..........................................................................................100

ЗАКЛЮЧЕНИЕ.....................................................................................102

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ...............................105

ПРИЛОЖЕНИЕ 1 .................................................................................114

ПРИЛОЖЕНИЕ 2 .................................................................................120

СПИСОК СОКРАЩЕНИЙ

АСОИз - автоматизированная система обработки изображений.

БС - базовая система (обработки изображений).

ИС - инструментальная система (обработки изображений).

ОС - операционная система.

ПК - персональный компьютер.

ПО - программное обеспечение.

ПС - прикладная система (обработки изображений).

УПСИ - упорядоченная последовательность строк изображения.

ЭВМ - электронно-вычислительная машина.

ВВЕДЕНИЕ

Диссертация посвящена разработке эффективных методов и средств потоковой организации обработки изображений в вычислительных системах на базе персональных компьютеров.

Актуальность темы.

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

На сегодня известно большое число автоматизированных систем обработки изображений (АСОИз), различающихся по сложности, составу реализуемых функций, режимам эксплуатации и т.д. Такое разнообразие обусловлено различными областями применения и, соответственно, различными целевыми функциями разработчиков систем, а также противоречивостью основных требований, которые необходи-

мо учесть при проектировании конкретной АСОИз. Каждый коллектив разработчиков решает этот комплекс задач, исходя из собственного опыта и приоритетов в отношении учитываемых требований.

По функциональному признаку АСОИз можно условно разделить на четыре группы /18/.

Базовые системы общего назначения реализуют в том или ином объеме основные, типовые задачи обработки изображений. Эти системы используют главным образом стандартные аппаратные и программные средства.

Функционально-ориентированные системы предназначены для выполнения отдельных вполне определенных задач управления и обслуживания специализированных устройств работы с изображениями (нестандартных устройств ввода - вывода изображений, электронных или электронно-оптических устройств их обработки). Сюда же можно отнести и системы, ориентированные на выполнение какой то узкой группы операций, например, системы архивации и хранения изображений документов /3/.

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

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

нию различен. Если прикладные системы тесно зависят от решаемой задачи или имеющейся аппаратуры, которые во многом определяют их облик, то при разработке базовых систем разработчик сталкивается с более серьезной проблемой учета всего комплекса общих, но достаточно противоречивых и трудно формализуемых требований. В то же время разработка базовых систем чрезвычайно важна и целесообразна вследствие специфики обработки изображений. Большинство используемых в этой области алгоритмов могут быть представлены как набор типовых операций над изображением, последовательное применение которых и составляет суть решения. БС включают в себя набор наиболее типичных и применяемых задач обработки, объединенных в систему специально разработанным программным обеспечением, которое обеспечивает унифицированный доступ к данным изображений, разработку новых задач и включение их в систему /19/. Особое место занимают инструментальные и учебно-исследовательские системы (ИС), построенные на базе персональных компьютеров (ПК). Их основной особенностью является ориентация на расширение, что позволяет использовать эти системы в качестве средства разработки нового алгоритмического наполнения не только базовых, но и прикладных систем, для предварительного макетирования ПС. Более того, существенный рост производительности персональных компьютеров общего назначения позволяет рассматривать инструментальные системы как основу для создания и тиражирования широкого круга ПС в самых различных областях применения. При этом прикладная система должна включать в себя ядро базовой системы, набор необходимых (возможно, не всех) типовых операций и разработанное в рамках ИС прикладное программное обеспечение для решения конкретной задачи. Эффективность и гибкость такого подхода закладывается на этапе создания инструментальной системы обработки изображений.

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

Как правило процессы обработки видеоинформации не могут быть полностью и однозначно формализованы, поэтому участие в них человека-оператора представляется необходимым. Следствием этого является требование интерактивности программного обеспечения. Режим диалога наиболее естественен и оптимален при взаимодействии человека с АСОИз.

Важным свойством интерактивных систем является диалоговая реактивность, то есть приемлемая с точки зрения пользователя производительность выполнения основных, часто повторяющихся функций системы. Естественно, это требование не исключает длительного времени выполнения принципиально сложных в вычислительном отношении операций (например, преобразования Фурье для двумерного массива больших размеров)/51/.

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

Современные технологии обработки крупноформатных изображений на персональных компьютерах в полной мере выявляют недостатки таких вычислительных систем: недостаточность мощности и объемов оперативной памяти даже у продвинутых моделей. Наиболее экономным способом получения необходимой вычислительной мощности в таких случаях является совместное использование для выполнения одного задания нескольких процессоров. При этом используемая программная система должна обладать свойством масштабируемости.

Ускоренное развитие вычислительной техники и разнообразие архитектур компьютеров повышают значимость понятия длительности жизненного цикла программного обеспечения. Для увеличения этого показателя необходимым является универсальность программного обеспечения. При реализации универсальности недостаточно просто включить в систему широкий набор общеупотребительных процедур, необходимо также чтобы программное обеспечение разрабатывалось с учетом требования расширяемости. Как важную составляющую универсальности можно выделить и информационную совместимость разнотипных АСОИз, особенно при создании интегрированных архивов данных или сложной последовательной обработке изображений на нескольких системах /3, 50/.

К сожалению, существующие программные комплексы обработки изображений для ПК не отвечают всей совокупности подобных требований, многие из которых объективно являются противоречивыми. Это делает актуальным разработку и реализацию нового подхода к организации обработки изображений на ПК, обеспечивающего повышение эффективности АСОИз инструментального и учебно-исследовательского типа за счет более полного учета специфики цифровых изображений как объектов обработки, особенностей типовых алгоритмов и сквозных информационных технологий решения при-

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

Общепризнанно, что наиболее продуктивный путь повышения производительности систем обработки данных заключается в распараллеливании вычислительного процесса. Для персональных компьютеров, работающих с многозадачными операционными системами (OS/2, Windows NT и т.д.), оно выражается в использовании потоковых методов организации вычислений с квазипараллельным (на одном процессоре) или истинно параллельным (на нескольких процессорах) выполнением программ и порционной передачей данных от одной программы к другой по мере готовности. Причем, если истинная параллельность является полезной для обрабатываемой информации любой природы, то позитивный эффект от квазипараллельности характерен именно для изображений, поскольку дает возможность устранить интенсивный свопинг (обмен между внешней и оперативной памятью) при многошаговой обработке больших объемов двумерных данных. Эффективная реализация этой возможности с учетом отмеченных особенностей обработки изображений требует расширения стандартных функций операционных систем ПК по межпрограммному обмену данными, уменьшения сопутствующих "накладных расходов" за счет регламентации процессов обмена, разработки специфичных алгоритмов информационного взаимодействия прикладных программных модулей.

Следует отметить, что потоковая сеть, описывающая произвольную информационную технологию обработки изображений, при ограниченных ресурсах буферной оперативной памяти далеко не всегда оказывается реализуемой. Ключевой проблемой здесь является ее анализ и обеспечение корректности (отсутствия тупиковых ситуаций).

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

Целью работы является разработка методов организации двумерных цифровых данных и алгоритмического обеспечения параллельной обработки изображений в АСОИз на основе ПК, разработка методов и средств моделирования и анализа потоковых сетей обработки изображений, создание на их основе прикладного программного обеспечения АСОИз, сочетающего высокую эффективность использования вычислительных ресурсов, масштабируемость, гибкость функций, универсальность, технологичность создания и включения новых программных модулей и относительно невысокую стоимость, а также исследование эффективности предлагаемого подхода к разработке программных средств в типовых задачах моделирования и обработки изображений.

В соответствии с поставленной целью определены основные задачи диссертации:

1. Разработка методов организации двумерных данных и эффективной технологии параллельной обработки изображений в АСОИз на базе персональных компьютеров.

2. Разработка математических моделей параллельно исполняемых программных модулей и в целом сетевого вычислительного процесса в АСОИз. Исследование проблемы корректности алгоритмов организации потоковых сетей.

3. Создание алгоритмов и программных средств моделирования и анализа потоковых сетей в соответствии с разработанными методами организации данных изображений и моделями программ их обработки.

4. Проведение моделирования потоковых сетей для типовых задач обработки изображений.

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

Структура и краткое содержание диссертации. Диссертация состоит из введения, четырех глав, заключения и приложения.

В первой главе рассматриваются основные особенности компьютерной обработки изображений. Дается обзо�