Моделирование потоковых сетей и методы организации двумерных массивов данных при обработке изображений тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Попов, Сергей Борисович

• Попов, Сергей Борисович
• кандидат технических наук
• 1998

Оглавление диссертации кандидат технических наук Попов, Сергей Борисович

ОГЛАВЛЕНИЕ

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

ВВЕДЕНИЕ

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

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

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

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

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

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

Выводы

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

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

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

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

Выводы

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

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

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

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

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

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

Выводы

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

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

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

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

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

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

Выводы

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ 1

ПРИЛОЖЕНИЕ 2

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

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Моделирование потоковых сетей и методы организации двумерных массивов данных при обработке изображений»

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В третьей главе предлагаются принципы программной реализации формальной модели системы обработки изображений. Приводится описание разработанных программных средств моделирования пото-

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

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

Научная новизна работы.

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

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

3. Определены общие условия корректности формируемых потоковых сетей при обработке изображений в АСОИз.

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

5. Предложена модульная архитектура типа клиент-сервер программного обеспечения АСОИз.

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

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

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

На защиту выносятся:

- трехуровневая организация двумерных массивов данных, используемая при обработке изображений в АСОИз;

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

- алгоритмы организации потоковых сетей обработки изображений;

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

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

- алгоритмы и программные средства АСОИз системного уровня.

Практическая ценность работы.

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

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

Публикации и апробации работы. Результаты, полученные в ходе работы над диссертационной работой, докладывались на Всесоюзных конференциях "Методы и средства обработки сложной графической информации" (Горький, 1988 и 1991 гг.), на 2-м Республиканском семинаре "Проблемы создания систем обработки, анализа и распознавания изображений" (Ташкент, 1989 г.), на 2-ой и 3-й Всероссийских с участием стран СНГ конференциях "Распознавание образов и анализ изображений: Новые информационные технологии" (Ульяновск, 1995г. и Нижний Новгород, 1997г.), на Пятом Международном семинаре "Распределенная обработка информации" (Новосибирск, 1995г.).

Вошедшие в диссертацию результаты исследований опубликованы в шестнадцати работах.

1. ПРОБЛЕМЫ ОРГАНИЗАЦИИ ДАННЫХ И ПРОЦЕССА

ВЫЧИСЛЕНИЙ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ ОБРАБОТКИ ИЗОБРАЖЕНИЙ

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

изображений

Основной особенностью компьютерной обработки изображений является большой объем данных, с которым приходится оперировать, проводя вычисления. При разработке алгоритмов обработки изображений большое количество усилий направлено на преодоление "проклятия размерности" /51/. Минимальный объем изображения в реальных применениях равен 256x256x8 бит = 64 байта. Современные приложения оперируют изображениями с размерами от 512x512x8 бит = 256 Кбайт до 4096x4096x32 бит = 64 Мбайт. Для систем обработки данных дистанционного зондирования Земли типичный объем цифрового снимка высокого разрешения составляет несколько сотен Мбайт/13/.

Другой особенностью изображений как данных является их дву-мерность, причем изображение является не просто матрицей чисел, а матрицей, соседние отсчеты которой некоторым образом связаны между собой/4, 20/.

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

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

- согласования двумерной структуры данных большинства алгоритмов обработки изображений и последовательного характера хранения на внешнем запоминающем устройстве или поступления данных изображений.

Результатом решения этих задач является последовательный характер большинства алгоритмов и методов обработки изображений. Это проявляется, с одной стороны, в структуре вычислений "внутри" алгоритма. Очень популярно использование построчной, последовательной развертки отсчетов изображений и преобразований, имеющих локальный характер (поэлементных или на основе скользящего окна)/! 1, 14, 44, 45, 64/. С другой стороны, значительное число методов сложной обработки изображений могут быть реализованы как последовательное применение некоторых законченных типовых операций над изображениями. Именно это обстоятельство определяет эффективность применения АСОИз, построенных на базе универсальных ЭВМ, к решению широкого спектра исследовательских и прикладных задач обработки и анализа видеоинформации/16/.

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

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

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

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

обработки изображений

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

При рассмотрении программной системы различают три характерных уровня:

- внешний (функциональный);

- концептуальный;

- внутренний.

Внешний уровень - это функциональное проявление системы с точки зрения пользователя; на концептуальном уровне логически описывают внутреннюю структуру, осуществляющую исполнение внешних функций; а их физическая, программная реализация рассматривается на внутреннем уровне.

В существующей научно-технической литературе программные средства АСОИз описываются в основном на внешнем функциональном уровне, реже и менее подробно затрагиваются вопросы логической внутренней структуры и программной реализации/16, 18, 19, 41, 56, 61/.

С точки зрения пользователя можно выделить следующие типы внешней организации программных средств обработки изображений/59/:

- библиотеки функций, пакеты прикладных программ обработки изображений;

- программные средства с вызовом функций, системы на базе меню;

- программные системы с командным языком;

- программные системы с проблемно-ориентированным языком высокого уровня;

- программные средства на базе визуальной среды управления и манипулирования объектами системы.

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

цессе своего развития эволюционируют в сторону улучшения взаимодействия с пользователем.

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

Развитие программ такого рода в сторону большей интерактивности привело к созданию программных систем с вызовом функций/43/. Реализованы они, как правило, в виде большой диалоговой программы, осуществляющей вызовы и управление всеми прикладными модулями. Формы диалога очень разнообразны - от простейших «кнопочных» до иерархических многоуровневых меню. Однако при большом числе прикладных модулей (свыше трех десятков) системы такого типа становятся очень громоздкими, добавление нового модуля приводит к перестроению всей системы. Подобная организация имеет свои плюсы (простота общения с системой даже для неподготовленного пользователя), и минусы (сравнительно ограниченные возможности по выбору режимов обработки, сложность расширения состава прикладных и служебных функций). Попыткой преодоления указанных недостатков являются системы, где все прикладные модули разбиты на несколько групп, и для каждой такой группы создается диалоговая программа/31/. Прикладные модули различных групп обмениваются данными через общую базу данных на внешнем запоминающем уст-

ройстве. Логическим завершением такой эволюции является набор прикладных задач.

В системах этого типа пользователь средствами командного языка операционной системы последовательно вызывает самостоятельные задачи, каждая из которых реализует какой-либо законченный алгоритм обработки или определенную служебную функцию. Управляющая подсистема в виде библиотеки подпрограмм на стадии компоновки присоединяется к каждой задаче для организации доступа к изображениям в общей базе данных и координации изменений данных. По такому принципу построено большинство интерактивных АСОИз исследовательского характера/1, 22, 32, 41, 61/. Недостатком такой архитектуры следует признать избыточность обращений к базе данных на внешних запоминающих устройствах для хранения промежуточных изображений, что существенно снижает эффективность процесса обработки.

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

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

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

Появление современных операционных систем, имеющих графические средства организации диалога, интерфейс на базе объектно-ориентированной модели SOM (System Object Model)/62/, реальную многозадачность, позволяет создать АСОИз, имеющие удобную визуальную среду управления и манипулирования объектами системы. Их отличительными чертами являются не только новый способ организации диалога, но и возможность качественно иной организации управления прикладными модулями, расширение перечня объектов, которыми можно манипулировать в системе.

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

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

Структура программного обеспечения АСОИз

Язык Меню Панели

Подсистема организации диалога

Результаты Сообщения

Рис. 1.1.

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

Итак, в состав программного обеспечения систем обработки изображений входят:

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

- подсистема организации диалога;

- подсистема управления базой данных изображений;

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

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

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

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

С точки зрения реализации алгоритмов на ЭВМ, а также по специфике использования их в составе систем обработки изображений целесообразно выделить три основных класса задач: синтеза, обработки и анализа изображений/44, 45, 64/.

Синтез изображений обычно определяют как формирование изображения по некоторому описанию - алгоритму построения с набором необходимых параметров. Преобразование осуществляющее синтез, по множеству параметров Р формирует изображение У:

Задачей анализа является получение некоторой оценки (или описания) обрабатываемого изображения. Под оценкой можно понимать, например, некоторые интегральные характеристики исходного изображения, геометрические характеристики различных объектов на изображении, отнесение исходного изображение или его частей к заданным классам. Преобразование анализа Еа по множеству изображений {Х} определяет необходимые параметры из множества Р:

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

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

Методы глобальной обработки изображений характеризуются тем,

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

где Р^] - оператор преобразования для точки у^,

г, _/ - здесь и далее целочисленные координаты точек цифрового изображения.

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

Программы поэлементной обработки каждую точку исходного изображения X преобразуют в соответствующую ей точку выходного изображения 7:

где хи еХ, уи еУ.

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

З'/г^-М' Уие7'

Уч=р{хи)

При обработке изображения блоками входное изображение X разбивается на блоки одного размера {Хк1\Х = \^Хк1), над которыми и

к,1

производится некоторая совместная обработка:

гк1=р{хк1).

В рамках каждого блока производится внутренняя "глобальная" обработка. Формируемые блоки объединяются в результирующее изображение:

к,1

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

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

Формально этот процесс можно представить следующим образом. На 7-ом шаге формируются с помощью преобразования необходимые элементы решения, представляемые, в общем случае, некоторым множеством параметров Б1 и множеством изображений {X}1

{{*}',5'} = *'({ЛГ},5./>), {X) с О'{XY.SC О',

1=0 1=0

где {X}, Б, Р - множества входных изображений, входных параметров и собственных параметров преобразования ^ соответственно. Любое из этих множеств на некотором конкретном шаге может быть пустым.

{Х}°, 5° - исходные множества изображений и параметров для рассматриваемой задачи.

Шаги решения с соответствующими элементами решения удобно

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

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

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

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

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

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

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

Еще одним препятствием повышения производительности рассмотренных методов организации работы с данными изображений является необходимость ожидания завершения предыдущего шага решения, несмотря на то, что определенная часть информации на его выходе готова значительно ранее. Более эффективной в вычислительном отношении является схема с параллельным выполнением всех шагов алгоритма и непосредственной передачей части данных от одной операции к другой по мере готовности/10, 16, 39, 67/. Фактически здесь формируется некоторый поток данных, элементы которого преобразуются на каждом шаге и передаются последующему для дальнейшей обработки. При этом результаты выводятся с той же скоростью, с которой производится и ввод, но, возможно, после некоторой задержки. Системы, реализующие подобную схему вычислений, называются потоковыми сетями!5, 12, 26/. Использование потоковой обработки изображений предполагает решение проблем управления выполнением программ, синхронизации их работы и доступа к данным, контроля готовности данных, требуемых на очередном шаге. В настоящее время из-за сложности анализа процесса вычислений в потоковых сетях произвольного вида обычно рассматриваются только конвейеры из последовательно соединенных программ/67/, когда данные одного входного

изображения по цепочке передаются и обрабатываются квазипарал-лельно выполняющимися программами обработки изображений. Если рассматривается обработка по нескольким распараллеленным веткам, то оговаривается их идентичный характер работы с данными (одинаковые задержки и т.п.)/71, 72/.

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

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

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

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

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

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

Объединяющим при этом является понятие информационного поля, введенное в /4/, которое является удобной абстракцией для описания различных способов задания информационного потока данных независимо от порождающего его источника. Информационным полем называется тройка (2, Ж, д), где 2 - конечное множество, называемое носителем информационного поля (точки множества принято называть позициями); множество значений (градаций), являющееся некоторой шкалой (шкалой отношений, порядка или наименований); q -частичное отображение 2 Информационными полями в нашем случае могут быть изображения и их фрагменты, многозональная информация, графические препараты, спектры, гистограммы, пирамидальные структуры, многомерные поля, маски и т.п.

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

С другой стороны, "физически" изображения хранятся на ВЗУ в виде одномерной структуры. В качестве носителя информационного поля здесь выступает одномерный массив данных, множество значений которого может отличаться от соответствующего множества значений в пользовательской модели. Согласование этих двух представлений данных изображений осуществляется подсистемой управления базой данных изображений. Рассмотрим основные форматы хранения данных изображений на ВЗУ. Основной тенденцией здесь является хранение одного изображения в одном файле. Это обеспечивает достаточную гибкость при манипуляциях с большим количеством изображений и при переносе изображений из одной системы в другую. В настоящее время существует свыше 100 достаточно распространенных

формата хранения данных изображений. Такое количество вызвано как историческими причинами, так и многообразием факторов, которые желательно учесть при разработке формата файла: способ использования изображения, его размеры, параметры дискретизации и квантования, необходимость сжатия при хранении (и способ, каким это сжатие осуществляется, например, с потерей точности или без), наличие дополнительной информации, которую необходимо хранить вместе с изображением. По результатам опросов /53, 57/, наиболее популярным форматом файлов изображений является формат TIFF (Tagged Image File Format). По разным оценкам от 48 до 89 % пользователей используют его совместно с другими форматами. Далее идет группа форматов, получивших примерно равное распространение (от 30 до 50 %): BMP, РСХ/РСС, GIF, PICT. Форматы BMP (Bit-Map) и РСХ/РСС (PC graphiX / PC Clip art) получили широкое распространение вследствие их тесной связи с операционной системой Microsoft Windows, как И формат PICT - на компьютерах Macintosh фирмы Apple. Формат GIF (Graphics Interchange Format) был разработан ассоциацией CompuServe, чтобы дать пользователям независимую от используемой вычислительной техники возможность обмениваться файлами цветных изображений.

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

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

Для снятия проблем согласования данных при организации потоковых сетей обработки изображений предлагается ввести промежуточный уровень организации данных изображений - концептуальный/39, 40/. Концептуальная модель описывает глобальную логическую организацию данных на системном уровне и обеспечивает совместное использование в системе всего множества пользовательских и физических моделей организации данных Это своего рода ограничение на процесс согласования двух других моделей, которое состоит в следующем: прикладная программа получает данные изображения (отсчеты двумерной матрицы) в порядке построчной развертки, точнее в виде упорядоченной последовательности строк изображения (УПСИ). Таким образом, независимо от того, как данные используются внутри прикладной программы, на входе она получает их в виде УПСИ и на выходе обязана формировать их также в виде УПСИ.

Таким образом мы приходим к трехуровневому описанию организации данных изображений в АСОИз, каждый из которых представлен соответствующим набором моделей:

- пользовательские модели;

- концептуальная модель;

- физические модели хранения.

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

жений) согласовывает через концептуальную модель различные пользовательские модели прикладных программ и физическую модель хранения данных на ВЗУ.

Выводы

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

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

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

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

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

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

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

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

Рассмотрим условия, при которых можно организовать обработку изображений потоковыми методами. Пусть задан граф решения задачи обработки изображений <7 = (У,Е), где V - множество вершин, Е -множество дуг. Будем различать вершины, соответствующие глобальным и локальным операциям, а также вершины, обозначающие начальные данные и результаты решения, то есть разобьем множество вершин на непересекающиеся подмножества V = ¥с и У£ и Ув, где Ув

- подмножество вершин глобальных операций, ¥£ - подмножество вершин локальных операций, - подмножество вершин, соответствующие начальным данным или результатам решения. Вершины операций обозначаются кружками, причем вершины глобальных операций дополнительно помечаются перечеркивающей вертикальной чертой. Вершины данных обозначаются точками. Элементы решения - дуги, соответствующие изображениям (подмножество Е1 с Е ), будем выделять толстыми линиями, а дуги, показывающие передачу обычных параметров (подмножество ЕР <=£), будем изображать тонкими линиями. Ниже приводятся примеры графов двух типичных алгоритмов обработки: операции линейного контрастирования (рис. 2.1) и алгоритма исследования метода комбинированного блочного двухуровневого ко-дирования(рис. 2.2).

На рис. 2.1 точка а определяет исходное изображение, точка Ь -результирующее изображение, вершина 1 соответствует операции определения статистических характеристик изображения, вершина 2 -

Граф решения задачи линейного контрастирования

Рис. 2.1.

Граф технологии исследования комбинированного алгоритма блочного двухуровневого кодирования

Рис. 2.2.

операции линейного контрастирования, дуга (1,2) показывает передачу необходимых статистических характеристик.

Комбинированный метод блочного двухуровневого кодирования

использует раздельное кодирование для низкочастотной составляющей изображения и высокочастотной невязки. Низкочастотная составляющая изображения кодируется простыми интерполяционными методами, а высокочастотная составляющая - методом блочного двухуровневого кодирования /60/. На рис. 2.2 точка а также определяет исходное изображение, вершина 1 - операцию сглаживания локальным окном, вершина 2 - кодер интерполятора, вершина 3 - декодер интерполятора, вершины 4 и 8 - операцию поэлементного вычитания двух изображений, вершина 5 - операцию блочного двухуровневого кодирования, вершина 6 - соответствующую операцию декодирования, вершина 7 - операцию поэлементного сложения двух изображений и вершина 9 определяет операцию определения статистических характеристик изображения.

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

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

1. Для глобальных операций последующими могут являться только вершины, соответствующие данным. То есть

\/{и,у) еЕ

2. Дуги-параметры в качестве одной из вершин должны иметь вершину, соответствующую начальным данным или результатам решения, то есть

еЕР => и <=У0 vv еУ0.

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

Любой граф решения можно разбить на подграфы (возможно тривиальные, то есть состоящие из одной вершины-операции), допускающие потоковую организацию/12, 33/.

При рассмотрении структуры графов определим два их типа. Граф первого типа, рассматриваемый как неориентированный, не имеет циклов. То есть, если из одной вершины выходит две ветви, то они нигде дальше не соединяются. Граф второго типа, рассматриваемый как неориентированный, содержит один или несколько циклов. Две последовательные ветви такого графа могут соединятся в двух и более вершинах.

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

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

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

изображений

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

1. Модель должна отображать пространственно-временную структуру параллельного вычисления, т.е. должна содержать в себе элементы, соответствующие операциям и локальным состояниям.

2. Модель должна содержать информацию о всех возможных последовательностях событий и быть инвариантной к конкретным наборам исходных данных.

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

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

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

Во второй группе базовым понятием считается последовательный процесс. Исследуются методы параллельной и квазипараллельной композиции таких процессов, причем основное внимание уделяется способам их взаимодействия. Сюда следует отнести теорию взаимодействующих последовательных процессов (алгебра CSP - communicating sequential processes) Ч. Хоара /47/, исчисление параллельных процессов Милнера /47/, теорию трасс Мазуркевича /5/, методы крупноблочного параллельного программирования Евреинова и Миренкова /27/, макроконвейерный принцип Глушкова /26/. Все они исходят из требований параллельного программирования и предназначены для обоснования и проверки программных конструкций и методов структурного и семантического анализа программ.

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

При разработке формальной модели процессов обработки изображений в автоматизированных системах в данной работе за основу была взята математическая теория взаимодействующих последовательных процессов Хоара/47/. Основными позитивными чертами этой теории являются:

- развитое понятие процесса, учитывающее особенности синхронизации и параллельного выполнения процессов, включая модель обмена данными между различными процессами;

- удобная техника работы с протоколами (последовательностью событий) процессов, позволяющая легко выделять и анализировать результаты работы модели;

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

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

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

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

При конструировании моделей необходимо учитывать следующие особенности организации вычислений, вытекающие из введенной ранее организации данных изображений:

- данные изображений поступают в порядке построчной развертки в виде упорядоченной последовательности строк изображения;

- программа, осуществляющая синтез, обработку или анализ изображения, начнет последовательно считывать данные или формировать их только при наличии полного набора входных параметров;

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

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

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

get_рр - ввод параметров и инициализация программы; put_рр - передача выходных параметров и завершение; a?line - ввод очередной строки изображения а из упорядоченной последовательности; a?eof- получение признака конца данных при вводе очередной строки

изображения а\ alline - запись очередной строки изображения а;

aleof - запись признака конца данных для упорядоченной последовательности строк изображения а;

op, opl, op2,... - процедуры обработки текущего блока (блоков) данных изображения.

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

Р(х, у)= a->x->y->SKIP, то параллельная композиция Р2 = (Р(Ъ, с)\\Р(с, d)) фактически означает, что

Р2 = (а —> с—> SKIP) || (а-> сч> SKIP).

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

В соответствии с выделенными в п. 1.3 основными типами программ в АСОИз определим для них формальные математические модели в виде процессов.

Процесс 1. Программа синтеза, которая последовательно генерирует N строк изображения с помощью операции ор и выводит их последовательно в виде упорядоченной последовательности, может быть определена следующим образом:

SYNTHESIS (out) = (get_рр->п:= 0);

(п < N)*( opjsynt —> out ¡line = n+1); (outleof put_pp -> SKIP).

Процесс выводит по каналу out N строк обмена line и в завершение -признак окончания потока данных eof. Это позволяет последующим программам, использующим выходные данные, не привязываться жестко к значению N.

Процесс 2. Программа анализа одного изображения, получающая

данные из упорядоченной последовательности строк изображения,

выполняющая гомогенную обработку ор каждой строки:

ANALYSIS (in)=(get_рр ->DO_ANALYSIS),

DO ANALYSIS=(in?line ->op_a DO ANALYSIS

I in?eof put_pp SKIP).

Здесь eof определяет состояние программы при получении признака завершения упорядоченной последовательности строк изображения в момент чтения очередной строки.

Процесс 3. Программа, анализирующая совместно два изображения:

ANALYSIS2(inl, in2)=(get_рр DO_ANALYSIS2), DO_ANALYSIS2-(inl?line (in2?line ->op DO ANALYSIS2

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Попов, Сергей Борисович

Выводы

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

С++, который решает задачу анализа параллельного вычисления на корректность.

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

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

7. Проведен теоретический анализ и экспериментальные сравнительные исследования эффективности разработанных программных средств при решении типовых задач обработки изображений, получены условия целесообразности применения потоковых методов организации вычислений (время передачи данных между прикладными программами с использованием программных каналов обмена должно быть ориентировочно в два раза меньше, чем время передачи данных через промежуточные файлы на ВЗУ), показано, что использование разработанной программной системы для решения широкого круга задач обработки позволяет сократить время вычислений в полтора - два раза, причем увеличение производительности процессора ПК существенно повышает эффективность использования потоковых сетей обработки изображений, отмечается, что при увеличении количества используемых в потоковой сети прикладных программ и снижении их средней вычислительной сложности может быть достигнуто пятикратное увеличение скорости обработки данных.

8. Разработанные в диссертационной работе методы, алгоритмы и программные средства были использованы в рамках НИОКР по договору № 6/97 от 01.06.97 темы «Разработка и экспериментальная отработка алгоритмов учета искажающих факторов сквозного тракта для повышения выходных характеристик специального комплекса КА «Ресурс-ДК», выполненной в Самарском филиале Межотраслевой ассоциации "СОВИНФОРМСПУТНИК" по заказу Центрального специализированного конструкторского бюро (г. Самара) и по договору № 8/97 от 01.10.97 темы "Разработка программного обеспечения специализированной базы данных цифровых изображений", выполненной там же по заказу Института систем обработки изображений РАН в рамках проектов 01.01.01, 01.01.02, 01.02.01 и 01.02.03 Федеральной научно-технической программы "Наукоемкие технологии" (см. акт использования результатов диссертации в Приложении 2).

Список литературы диссертационного исследования кандидат технических наук Попов, Сергей Борисович, 1998 год

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

1. Автоматизированная система контроля сферических оптических поверхностей (АСКОП) «Тень» / Арефьев Е.Ю., Демидов Е.В., Живописцев Е.С., Пелипенко В.И., Попов С.Б., Сисакян И.Н., Сойфер В.А. И Препринт 245, ФИАН СССР, 1982. - 18 с.

2. Автоматизированная система технологического контроля оптических поверхностей на базе микро-ЭВМ «Электроника-60» / Арефьев Е.Ю., Живописцев Е.С., Попов С.Б., Сисакян И.Н., Сойфер В.А. // Автоматизация экспериментальных исследований. -Куйбышев: КуАИ, 1983. - С.116-121.

3. Александров В.В., Горский Н.Д. Базы видеоданных: состояние и тенденции развития // Прикладная информатика. - М.: Финансы и статистика, 1987. - Вып. 1(12). - С.24-52.

4. Александров В.В., Горский Н.Д. Представление и обработка изображений: Рекурсивный подход. - Л.: Наука, 1985. - 192 с.

5. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. - Новосибирск: Наука. Сиб. отд-ние, 1990. - 253 с.

6. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. - М.: Радио и связь, 1990. -256 с.

7. Белоусова М.П., Сергеев В.В. Организация обменов данными при геометрических преобразованиях изображений // Оптическая запись и обработка информации. - Куйбышев: КуАИ, 1988. -С.66-70.

8. Белоусова М.П., Сергеев В.В., Тахтаров Я.Е. Пакет прикладных программ обработки изображений и цифровой голографии. Система управления базой данных. - Куйбышев: КуАИ, 1987. - 39с.

9. Биркгоф Г., Барти Т. Современная прикладная алгебра. - М.: Мир, 1976. - 400 с.

10. Васин А.Г., Фролова Л.Г. Исследование алгоритмов управления вычислительным процессом в конвейерной программной системе обработки изображений // Оптическая запись и обработка информации. - Куйбышев: КуАИ, 1988. - С.70-76.

11. Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных системах научных исследований. - М.: Наука, 1982.-215с.

12. Воеводин В.В. Математические модели и методы в параллельных процессах. - М.: Наука, 1986. - 296 с.

13. Гарбук C.B., Гершензон В.Е. Космические системы дистанционного зондирования Земли. - М.: Издательство А и Б, 1997. - 296 с.

14. Глумов Н.И., Коломиец Э.И., Сергеев В.В. Информационная технология обнаружения объектов на изображении в режиме скользящего окна // Научное приборостроение. - 1993. - № 1. -С.72-88.

15. Глушков В.М., Капитонова Ю.В., Летичевский A.A. Теория структур данных и синхронные вычисления // Кибернетика. - 1976. -№ 6. -С.2-15.

16. Гуторова Н.Г., Михелевич Е.Г., Тихоцкий А.И. Вопросы построения гибкого математического обеспечения обработки изображений // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 3. - М.:Наука, 1992. - 320 с. -С.249-265.

17. Деннис Д.Б., Фоссин Д.Б., Линдерман Д.П. Схемы потока данных // Теория программирования. - Новосибирск: ВЦ СО АН СССР, 1972. - 4.2. -С.7-43.

18. Дымков В.И., Синицын И.Н. Элементы концепции персональных систем обработки изображений // Системы и средства информатики. - М.: Наука, 1989. - С.66-74.

19. Искусственный интеллект: В 3 кн. Кн.1. Системы общения и экспертные системы / Под ред. Э.В. Попова. - М.: Радио и связь, 1990. - 464 с.

20. Искусственный интеллект: В 3 кн. Кн.2. Модели и методы / Под ред. Д.А. Поспелова. - М.: Радио и связь, 1990. - 304 с.

21. Карп P.M., Миллер P.E. Параллельные схемы программ // Кибернетический сборник. - М.: Мир, 1975. - Вып. 13. - С.5-61.

22. Контроль фазового микрорельефа элементов компьютерной оптики / Арефьев Е.Ю., Голуб М.А., Овчинников К.В., Попов С.Б., Си-сакян И.Н., Сойфер В.А., Тихонов Д.Н., Храмов А.Г., Шамалова Г.В. / / Журнал технической физики, - 1990. - Т.60, вып. 6. -С.157-161.

23. Котов В.Е. Сети Петри. - М.: Наука, - 1984. - 160 с.

24. Кунг С.Ю., Джол Д.Т. Волновые матричные СБИС-процессоры обработки изображений // СБИС для распознавания образов и обработки изображений / Под ред. К. Фу. - М.: Мир, 1988. -С.141-165.

25. Ли Э.А., Мессершмитт Д.Дж. Синхронные потоки данных в задачах ЦОС // ТИИЭР, - 1987. - Т.75, № 9. - С. 107-119.

26. Макроконвейерные вычисления над структурами данных / Глуш-ков В.М., Капитонова Ю.В., Летичевский A.A., Горлач С.П. // Кибернетика. - 1981. - №4. - С.13-21.

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

28. Михелевич Е.Г. Связь структуры изображений, алгоритмов их обработки и адресации памяти // Тезисы докладов II Республиканского семинара "Проблемы создания систем обработки, анализа и распознавания изображений". - Ташкент, 1989. - Ч.2.- С.17-18.

29. Мясников В.В., Попов С.Б. Использование сигнального процессора в задачах обработки изображения // Научно-исследовательские разработки и высокие технологии двойного применения: Материалы 1-ой Поволжской научно-технической конференции, 21-23 февраля 1995 г., г. Самара. В 2 ч. - Самара, 1995. - 4.1. - С. 100.

30. Надд Г.Р. Параллельные системы обработки изображений // СБИС для распознавания образов и обработки изображений / Под ред. К. Фу.-М.: Мир, 1988.-С.112-140.

31. Некоторые прикладные оболочки обработки изображений для IBM PC / Глумов Н.И., Мясников В.В., Попов С.Б., Раудин П.В., Сергеев В.В., Фролова Н.И., Чернов A.B. // Тезисы докладов 2-ой Всероссийской с участием стран СНГ конференции "Распознавание образов и анализ изображений: Новые информационные технологии". - Ульяновск, 1995. - 4.4. - С.68-69.

32. Опыты по реконструктивной томографии с использованием автоматизированной системы обработки изображений / Арефьев Е.Ю., Багбая И.Д., Овчинников К.В., Попов С.Б., Сисакян И.Н., Сойфер В.А. // Компьютерная оптика: Автоматизация проектирования и технологии, вып.2, - Москва: МЦНТИ, 1987 - С.31-35.

33. Ope О. Теория графов. - М.: Наука, 1980. - 336 с.

34. Питерсон Дж. Теория сетей Петри и моделирование систем. - М.: Мир, 1984. - 264 с.

35. Погосянц Г.М. Последовательные и параллельные процессы в задачах описания и моделирования архитектуры вычислительных устройств // Системы и средства информатики. - М.: Наука, 1989. - С.182-191.

36. Попов С.Б. Масштабируемая АСОИз с возможностями адаптации и распределенной обработки // Тезисы докладов III конференции "Распознавание образов и анализ изображений: Новые информационные технологии". - Нижний Новгород, 1997. - 4.2. -С.167-171.

37. Попов С.Б. Распределенная обработка изображений в операционной системе OS/2 // Распределенная обработка информации: Труды Пятого Международного семинара. - Новосибирск. - 1995. -С.287-289.

38. Попов С.Б., Сергеев В.В. Модульное программное обеспечение с динамической структурой для обработки изображений // Тезисы докладов II Республиканского семинара "Проблемы создания систем обработки, анализа и распознавания изображений". - Ташкент, 1989.-Ч.1.- С.55-56.

39. Попов С.Б., Сергеев В.В. Реализация программных сетей обработки изображений в операционной системе ОС-PB СМ // Методы и средства обработки сложной графической информации. Тезисы докладов Всесоюзной конференции, сентябрь 1988: В 2 ч. - Горький, 1988. - 4.2.-С.112-113.

40. Попов С.Б., Сергеев В.В., Фролова Н.И. Архитектура программных средств обработки изображений в OS/2 // Тезисы докладов 2-ой Всероссийской с участием стран СНГ конференции "Распознавание образов и анализ изображений: Новые информационные технологии". - Ульяновск, 1995. - 4.4. - С.118-124.

41. Принципы построения и организация данных интерактивной системы для обработки изображений на IBM PC / Попов С.Б., Сергеев В.В., Храмов А.Г., Усачев A.B., Тахтаров Я.Е. // Тезисы докладов IV Всесоюзной конференции «Методы средства обработки сложной графической информации». - Горький, 1991. - С.66.

42. Программные системы / Под ред. П. Бахманна. - М.: Мир, 1988. -288 с.

43. Прототип системы для разработки и тестирования методов анализа и оценивания информации, представленной в виде изображений. (ОС Windows 95) / Гуревич И.Б., Журавлев Ю.И., Поликарпова Н.С., Сметанин Ю.Г., Хилков A.B. // Тезисы докладов III конференции "Распознавание образов и анализ изображений: Новые информационные технологии". - Нижний Новгород, 1997. -4.2.-С.118-124.

44. Прэтт У.К. Цифровая обработка изображений. - М.: Мир, 1982. -Кн.1. - 312 с.

45. Прэтт У.К. Цифровая обработка изображений. - М.: Мир, 1982. -Кн.2. - 480 с.

46. Система управления базой данных изображений для персональных ЭВМ Монитор-С / Попов С.Б., Сергеев В.В., Храмов А.Г., Усачев A.B., Тахтаров Я.Е. // Тезисы докладов Всесоюзного симпозиума "Методы и применение голографической интерферометрии". - Куйбышев, 1990. - С.72.

47. Хоар Ч. Э. Р. Взаимодействующие последовательные процессы. -М:Мир, 1989. - 264с.

48. Хювенен Э., Сеппянен Й. Мир Лиспа: Введение в язык Лисп и функциональное программирование. - М.: Мир, 1990. - Том 1. -448 с.

49. Хювенен Э., Сеппянен Й. Мир Лиспа: Методы и системы программирования. - М.: Мир, 1990. - Том 2. - 320 с.

50. Чукин Ю.В. Структуры данных для представления изображений // Зарубежная радиоэлектроника. - 1983.-№8.-С.85-108.

51. Ярославский Л.П. Цифровая обработка сигналов в оптике и голографии: Введение в цифровую оптику. - М.: Радио и связь, 1987. -296 с.

52. Ярославский Л.П., Мерзляков Н.С. Цифровая голография. - М.: Наука, 1982.-219 с.

53. Advanced Imaging Image File Format Survey Results // Advanced Imaging. - 1994. - Vol.9, No.6. - P. 10.

54. An Automated Working Place for Processing Image Sequences on the Basis of a Workstation and a Mass Parallel Processor / Berezovskii A.V., Kozlachkov V.A., Korshever 1.1., Manakov K.V., Makhaev V.M. // Pattern Recognition and Image Analysis. - 1996. - Vol.6, No.2. -P.350-351.

55. Bhandarkar S.M., Arabnia H.R., Smith J.W. A Reconfigurable Architecture for Image Processing and Computer Vision // International Journal of Pattern Recognition and Artificial Intelligence. - 1995. -Vol.9, No.6.-P.201-229.

56. Buxbaum D. Imaging for PC/Windows Now: for Business, Sciences & the Arts // Advanced Imaging. - 1994. - Vol.9, No.6. - P.20-24,26-28,30,32.

57. Callaghan V. The Image File Format Mess: What's Your TIFF? //Advanced Imaging. - 1994. - Vol.9, No.3. - P.44-49,85.

58. Classification and overview of research in real-time imaging / P. Sinha, S.V. Gorinsky, P.A. Laplante, A.D. Stoyenko, T.J. Marlowe // Journal of Electronic Imaging. - 1996. - Vol.5, No.4. - P.466-478.

59. Davis A.W. The Latest Image Manipulation Software for Video, Publishing & Graphie Arts //Advanced Imaging. - 1994. - Vol.9, No.3. -P.22-27.

60. Delp E.J., Mitchell O.R. Image compression using block trancation coding // IEEE Transaction on Communications. - 1979. - Vol.COM-27, No.9. - P.1335-1342.

61. Interactive software system for the picture synthesis, processing and analysis / Vasiljev Y., Maslov A.M., Murysin S.L., Popov S.B., Ser-geev V.V., Takhtarov Ya. E., Usachev A.V., Frolova L.G., Frolova N.I., Khramov A.G. // Proceedings of First International Conference On Information Technologies For Image Analysis and Pattern Recognition (ITIAPR'90), Lviv, USSR, Oct. 22-28, 1990. - Lviv, 1990. -Vol.2. - P. 94-98.

62. OS/2 2.0 Technical Library System Object Model Guide and Reference. - IBM Doc. 10G6309.

63. Popov S.B., Sergeyev V.V., Frolova N.I. Architecture of the Software for Image Processing in OS/2 // Pattern Recognition and Image Analysis. - 1996. - Vol.6, No.2. - P.432.

64. Russ J.C. The Image Processing Handbook. - CRC Press, 1992. -445 p.

65. Shapiro L.G., Haralick R.M., Goulish M.J. INSIGHT: A Dataflow Language for Programming Vision Algorithms // Proc. CVPR'86: IEEE Comput. Vision and Pattern Recogn., Miami Beach, Fla, June 22-26, 1986. - Washington, D.C., 1986, - P.375-380.

66. Some Application Shells of Image Processing for IBM PCs / Glumov N.I., Myasnikov V.V., Popov S.B., Raudin P.V., Sergeyev V.V., Frolova N.I., Chernov A.V. // Pattern Recognition and Image Analysis. - 1996. - Vol.6, No.2. - P.372.

67. Stevens W.R., Hunt B.R. Software Pipelines in Image Processing // Computer Graphics and Image Processing. - 1982. - Vol.20. -P.90-95.

68. Stroustrup B. The C++ Programming Language. - Addison-Wesley, 1991.

69. Tamura H., Yokoya N. Image Database Systems: A Survey // Pattern Recognition - 1984. - Vol.17, No.l. - P.29-43.

70. Wada B.T. A Virtual Memory System for Picture Processing // Communication of the ACM. - 1984. - Vol.27, No.5. - P.444-454.

71. Yalamanchili S., Aggarwal J. K. Analysis of a model for parallel image processing // Pattern Recognition. - 1985. - Vol.18, No.l. -P.l-16.

72. Yalamanchili S., Aggarwal J. K. A system organization for parallel image processing // Pattern Recognition. - 1985. - Vol.18, No.l. -P.17-29.