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

Попов, Сергей Борисович

Математическое моделирование, численные методы и комплексы программ

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

доктора технических наук: Попов, Сергей Борисович
город: Самара
год: 2010
специальность ВАК РФ: 05.13.18

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

Автореферат диссертации по теме "Моделирование и формирование структуры распределенных систем обработки крупноформатных изображений на основе динамической организации данных"

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

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

0046

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

0265

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

1 4 ОПТ 2010

Самара 2010

004610265

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)» (СГАУ) на кафедре технической кибернетики и в Учреждении Российской академии наук Институте систем обработки изображений РАН

Научный консультант: член-корреспондент РАН,

доктор технических наук, профессор Сойфер Виктор Александрович

Официальные оппоненты: доктор технических наук, доцент

Востокин Сергей Владимирович

Ведущая организация: Учреждение Российской академии наук Институт проблем управления сложными системами РАН, г. Самара

Защита состоится «29» октября 2010 г. в 10 часов на заседании диссертационного совета Д 212.215.05 при государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)» по адресу:

443086, г. Самара, Московское шоссе, 34, ауд. 209.

С диссертацией можно ознакомиться в библиотеке СГАУ.

Автореферат разослан « 23 » сентября 2010 г.

Ученый секретарь диссертационного совета

доктор технических наук, профессор Кораблин Михаил Александрович

доктор технических наук, профессор Султанов Альберт Ханович

д.т.н., профессор

А.А. Калентьев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Одной из важнейших проблем использования вычислительной техники является "отображение задач вычислительной математики на архитектуру вычислительных систем". Эта проблема была обозначена академиком Г.И. Марчуком как фундаментальное научное направление, кратко называемое "проблемой отображения".

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

Основным подходом к решению проблемы отображения является анализ вычислительной задачи, выявляющий параллелизм и возможности использования распределенных данных, выполняемый на основе математически эквивалентных преобразований модели информационной структуры алгоритма решения исследуемой задачи, или, более обобщенно, модели информационной технологии ешения задачи. Построение моделей алгоритмов, разработка методов их преобразования и анализа применительно к задачам линейной алгебры, математической физики рассматривались в работах В.А. Вальковского, В.В. оеводина, Вл.В. Воеводина, А.П. Ершова, В.П. Иванникова, В.А. Крюкова, В.Е. отова, АЛ. Ластовецкого, В.Э. Малышкина, А.Г. Марчука, Н.Н. Миренкова, L.J. - aer, M.I. Colé, J. Dongarra, I. Foster, L. Lamport и др.

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

В частности, это актуально в области компьютерной обработки изображений. В той области исследований следует отметить ведущие отечественные школы В.А. ойфера, В.В. Сергеева, В.С. Киричука, Я.А. Фурмана, Ю.А. Брюханова, К.К. асильева и др. Разработка систем параллельной обработки изображений ведется .П. Пяткиным. В области создания распределенных систем параллельной бработки изображений можно отметить работы групп исследователей из ниверситетов США, Испании (University of Extremadura), Италии (University of 'aples "Parthenope"), Нидерландов (Delft University of Technology, University of

Amsterdam), Франции (Université Paris Sud, University of Burgundy) и Японии (Kyushu University). В работах, связанных с параллельной обработкой изображений, в основном рассматриваются вопросы построения параллельных алгоритмов обработки изображений, адаптации последовательных алгоритмов применительно к параллельным архитектурам ВС.

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

Естественный при обработке изображений параллелизм, основанный на декомпозиции данных, позволяет достаточно легко адаптировать последовательные реализации широкого спектра задач обработки для их выполнения на многоядерных процессорах. Однако с увеличением размеров изображений время их обработки все более определяется временем, затрачиваемым на операции ввода/вывода. В таких условиях при обработке крупноформатных изображений с использованием относительно простых в вычислительном отношении задач эффективность использования многоядерных процессоров резко падает. Существующие тенденции развития вычислительной техники еще более обостряют проблему: все увеличивающийся разрыв между производительностью процессоров и быстродействием устройств постоянного хранения данных существенно снижает показатели общей эффективности ВС при решении прикладных задач. Вместе с тем скорость передачи данных в локальных сетях растет существенно быстрее, чем аналогичный показатель для дисковых запоминающих устройств (ЗУ). В настоящее время скорость обмена данными в сетях на базе технологии Gigabit Ethernet (ЮЬЕ) находится приблизительно на одном уровне с дисками типовых конфигураций компьютера, но при переходе на технологию lOGbE ситуация кардинально изменится — визуализация крупноформатного изображения будет выполняться быстрее при удаленном, а не локальном хранении данных. В таких условиях использование распределенных систем для хранения и обработки крупноформатных изображений становится актуальным.

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

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

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

Цель и задачи исследования

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

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

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

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

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

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

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

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

Методы исследования

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

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

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

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

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

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

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

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

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

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

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

едиктивной оценки времени выполнения задачи обработки.

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

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

4. Алгоритм децентрализованной динамической балансировки много-оцессорных систем при распараллеливании выполнения операций обработки

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

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

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

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

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

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

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

Апробация работы

Основные результаты работы докладывались на 27 научных конференциях и семинарах: Второй Всесоюзной конференции «Методы и средства обработки сложной графической информации», г. Горький, 1985; Всесоюзной конференции «Методы и средства обработки сложной графической информации», г. Горький, 1988; Втором Республиканском семинаре "Проблемы создания систем обработки, анализа и распознавания изображений", г. Ташкент, 1989; Всесоюзном симпозиуме "Методы и применение голографической интерферометрии", г. Куйбышев, 1990; Первой Международной конференции «International Conference On Information Technologies For Image Analysis and Pattern Recognition (ITIAPR'90)», г. Львов, 1990; Четвертой Всесоюзной конференции «Методы средства обработки сложной графической информации», г. Горький, 1991; Второй Всероссийской с участием стран СНГ конференции «Распознавание образов и анализ изображений: Новые информационные технологии», г. Ульяновск, 1995; Пятом Международном семинаре «Распределенная обработка информации», г. Новосибирск, 1995; Третьей конференции «Распознавание образов и анализ изображений: Новые информационные технологии», г. Нижний Новгород, 1997; Пятой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-5-2000), г. Самара, 2000; Международной конференции «Математическое моделирование - 2001», г. Самара, 2001; Научно-методической конференции «Телематика 2002», г. С-Петербург, 2002; Шестой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-6-2002), г. Великий Новгород, 2002; Втором Международном научно-практическом семинаре

«Высокопроизводительные параллельные вычисления на кластерных системах», г. Нижний Новгород, 2002; Третьем Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах», г. Нижний Новгород. 2003; Международной конференции «Распределенные вычисления и Г'рид-технологии в науке и образовании», г. Дубна, 2004; Седьмой Международной конференции «International Conference on Pattern Recognition and Image Análisis: New Information Technologis» (PRIA-7-2004), r. Санкт-Петербург, 2004; Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений», г. Новороссийск, 2005; Второй Международной конференции «Distributed Computing and Grid-Technologies in Science and Education», г. Дубна, 2006; Всероссийской научной конференции «Научный сервис в сети Интернет: технологии параллельного программирования», г. Новороссийск, 2006; Четырнадцатой Всероссийской научно-методической конференции «Телематика'07», г. Санкт-Петербург, 2007; Всероссийской научной конференции «Научный сервис в сети Интернет: многоядерный компьютерный мир», г. Новороссийск, 2007; Тринадцатой Всероссийской конференции «Математические методы распознавания образов», Ленинградская обл., г. Зеленогорск, 2007; Седьмом Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах»,

г. Нижний Новгород, 2007; Всероссийской научной конференции «Научный сервис в сети Интернет: решение больших задач», г. Новороссийск, 2008; Третьей Международной конференции «Distributed Computing and Grid-Technologies in Science and Education», г. Дубна, 2008; Всероссийской суиеркомпьютерной конференции «Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность», г. Новороссийск, 2009.

Связь с государственными и международными программами

Основные результаты диссертации получены в рамках научно-исследовательских работ (НИР) по международным, государственным, межвузовским и региональным научно-техническим программам: грантам Российского фонда фундаментальных исследований №№ 02-01 -00119-а, 02-01-08055-инно, 03-01-00109-а, 04-07-90149-а, 04-07-96500-р2004поволжье_в, 05-01-08043-офи_а, 06-08-01024-а, 07-07-00210-а, 10-07-00553-а; программе фундаментальных исследований Президиума РАН «Проблемы создания национальной научной распределенной информационно-вычислительной среды на основе развития GRID технологий и современных телекоммуникационных сетей» по направлению № 4 "Оптимизация вычислительных архитектур под конкретные классы задач, информационная безопасность сегевых технологий, применение распределенных информационно-вычислительных систем"; гранту Президента России по поддержке ведущих научных школ - НШ-3086.2008.9 «Разработка теоретических основ и создание информационноых технологий обработки изображений и компьютерной оптики»; Российско-американской программе "Фундаментальные исследования и высшее образование" ("BRHE" CRDF Project SA-014, 2002-2010 гг.); государственной научно-технической программе "Перспективные информационные технологии" (1994-1999 гг.).

Публикации

По теме диссертации опубликовано 62 работы, в том числе 3 монографии, 22 статьи в ведущих рецензируемых журналах и изданиях, входящих в перечень ВАК, 36 статей в сборниках, трудах конференций и тезисов докладов, получено 6 свидетельств о регистрации программы для ЭВМ и патент на изобретение.

Структура и объем работы

Диссертация состоит из введения, четырех разделов, заключения, списка использованных источников и приложений. Она содержит 258 страниц основного текста, 56 рисунков, 11 таблиц. Библиографический список включает 208 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность работы, дана ее общая характеристика, сфорулированы цель и задачи исследования.

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

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

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

Рисунок 1 - Типология операций обработки изображений

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

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

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

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

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

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

Модель информационной технологии обработки изображений строится как мпозиция итераторов обработки изображений на основе нотации алгебры С5Р и фавита алгебры изображений Г. Риттера.

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

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

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

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

Таблица I - Основные элементы алфавита модели обработки изображений

Обозначение Определение

X = {(*,.) е Ж2: х, 6 , х, е } Область определения изображения, где 2„ = {0,1,...,п-1}

Г с {7",К",с} Область значений изображение определяющий типологию изображения

а е Ж* ={(х,а(х)):1еХс 22,а(х)ег}, а(х) Изображение, значение пиксела изображения в точке х 6 X

Х|, =1 = {(.с,,х,):дг, = е 2„,} Множество точек, принадлежащих одной строке

Множество точек, принадлежащих одному столбцу

е(х)={х+у^у6н} Произвольная окрестность точки х, задаваемое множеством точек Н с 2г

Частичное изображение, часть изображения я, размешенное на вычислительном уме /

Область определения частичного изображения, размещенного на вычислительном узле 1

х, = Цхн, 1=1 Область определения распределенного изображения - дизъюнктивное объединение областей определения всех его частичных изображений

■- = 11%. 11*3 • Л_«*,. , = 1Р 1=1,Г 1=1,/>.У=1./' Распределенное изображение с различными способами декомпозиции: одномерная без пересечения, с частичным перекрытием фрагментов, то же в двумерном случае

1" Ех.н 1ь/ \ {а(х),УхеХ а е К*", а (х) = , „ 1ь(у).Уу6(Х + Н)\Х Расширение изображения а е на отсчеты за пределами области определения исходного изображения Ь е *

г,, = х,+н = Ц(хг|, + н) Область определения расширения распределенного изображения

а„Г = и»;;|Ь , где к ~ («ет/(А (Н))-|)/2 1' Расширение распределенного изображения

а^М^хеХ^, а"Г = 6 (х,|.+н)пх,= ■=1 [ь(у).у, 6 (хЛ +н)\(хг|, ихг),_, Расширение частичного изображения Значения Ь(у) или задаются константой, или доопределяются значениями пикселей изображения а одним из трех способов: доопределение ближайшим отсчетом; циклическое доопределение; зеркальное доопределение.

В общем случае итератор - это совокупность трех составляющих (Х,/\7), где X - множество итерируемых объектов, Р - оператор преобразования объекта; Т -оператор упорядочивания на множестве объектов.

1. Итератор применяется к некоторому множеству объектов X. Если множество пустое, то никаких действий не выполняется.

2. Итератор выполняет однотипные действия над некоторой упорядоченной последовательностью объектов: \/хе X, /•"(*).

3. Упорядоченность обеспечивается наличием некоторого оператора упорядочивания, который последовательно перебирает элементы множества.

4. То, каким образом задано множество, влияет на реализацию оператора упорядочивания, но не влияет на работу итератора в целом.

Аналогично конструкции CSP h*Q, которая обозначает традиционный цикл while b do Q , введено обозначение итератора для случая произвольной реализации оператора упорядочивания {дг :X}*F(jt), которое соответствует оператору foreach (х) do F(x), реализованному в большинстве современных языков программирования, е(Х,1фг)) = {дг:Х}*Г(дг).

В диссертации сформулированы основные правила преобразований итераторов, где var(F(x)) - множество изменяемых переменных процесса, acc(F(x)) - множество используемых переменных процесса.

L1. Расщепление итератора. Если Z = X U У таким образом, что X П Y = 0, то

{x:Z}* F(x) = {.г: Х] * F(x);{x: К} * F[x) ИЛИ Q(Z, F(x)) = (*));в(К, F(x)).

L2. Слияние итераторов по множествам.

Если ХЛУ = 0,то = Z = XIJK.

L3. Слияние итераторов по преобразованиям. Если Vr.v :дг>- у выполняется var(F(j))Па«.'(С(у)) = 0, ТО {jt: X} * F(je);{x: X} * G(x) = {х: X} *(F(x)\G(x)). L4. Параллельная декомпозиция итератора по данным. Если Z = XUУ и X П К = 0, то {л-: Z} * F{x) = {дг:Х}*/г(дг);{л :У}* F(x) = {л: X) * ^(jr) ||{jr:K}* F(x), при условии, что Мхе X,Vyб Y выполняется var(F{x)){\acc(F(у)) = var(F(y))riacv(F(x)) = 0. L5. Параллельная декомпозиция итератора по преобразованиям. {х: X} *(F(x)-,G{x)) = {jf: X} * F(x) || {x: X} * G(x), при условии, что Vjc.ve X выполняется var(F(x))Пacc{G(у)) = шг(G(.г))П«.'<-' L6. Вложенные итераторы.

Пусть x = [jx, и X, ПXj = 0, Vi, j Лф j, тогда {.r:X}*f(.r) = {X,.:X}*({jr:X,}*F(jr)).

i-i

Правая часть данного равенства определяет итератор по подмножествам 0(х,/г(х,)). L7. Параллельная декомпозиция вложенных итераторов.

Пусть X = (jx, и Х.пх, =0,V/,j:i> j, тогда {*:X}*F(.r) = 11 ({л : X,} * )),

.-1 i

при УСЛОВИИ, ЧТО var(e(Xi,/r(.r)))n<Kf(0(XJ,/r(A:))) = 0,Vi,y:i * j.

Эквивалентность и корректность данных правил преобразований доказана в рамках теории CSP.

Итераторы, реализующие основные операции обработки изображений, определены в диссертации следующим образом.

Пусть а б F* - произвольное изображение, имеющее область определения X, и F(a(x)) - процесс, использующий значение пиксела изображения в точке хеХ, тогда итератор, обеспечивающий применение данного процесса ко всем точкам изображеиия, определяется следующим образом в(а,/-'(а(х))) = {х: х} * /-'(а(х)).

В таблице 2 представлены модели основных типовых операций обработки изображений и их параллельные композиции на основе распределения данных. В таблице предполагается, что ае¥х, се У* - произвольные изображения, имеющие одинаковую область определения X, соответствующие им распределенные изображения а4 и с, определены с помощью одинаковой декомпозиции области определения X,, задана операция редукции у, формирующая некоторую характеристику изображения, такая что $ = $у/(а(х)), V е Р, Эе: 5 = луг = гул.

Таблица 2 - Модели основных типовых операций обработки изображений

Типовая операция обработки изображений Формальная модель операции

Операция поэлементного преобразования в общем виде РО( а.с.Ф) = {х: X} * (с(х) := Ф(а(х)))

Операция линейного поэлементного преобразования PO_Lin(a,c,a,p) = {х: X} * (с(х) := а ■ а(х) + р)

Операция табличного поэлементного преобразования PO_LUT(as,LUT) = {х :Х} * (с(х) := LUT( а(х)))

Операция поэлементного преобразования двух изображений РО _ Unl(a, b,e, а,р,х,8) = {х-.Х}* (с(х) := а ■ а(х) + /3 • Ь(х)+ * • а(х)- Ь(х) + 5)

Параллельная декомпозиция поэлементного преобразования РО( а„с„Ф) = [^({х: Х„,} *(с(х) := ф(а(х))))

Операции оценки характеристик изображения в общем виде RO(a,s,yJ) = (л := *);{*:X} * ( v := лу/(а(х)))

Операция суммирования значений всех пикселов изображения ЯО(а,л,+. 1) = (i := 0);{х: X} * (л := .v + а(х))

Параллельная декомпозиция операции оценки характеристик изображения ЯО(а„л,у,/) = «o(aj>ii,*,,/,/);(* := р

Операция локальной обработки скользящим окном в общем виде ZJVO(a|" ,c,H,f) = {x: X} * в(Н, F (x,y)) = = {x:X}*({y:H}*F(x,y))

Операция локальной обработки скользящем окном в терминах операции редукции над отсчетами окрестности обработки 1ЖО[ a {x:X}* \c,H, y,/,,/) = л' := г;{у :Н}*(л:= луЛ(у,а|"(х + у))); ,c(x):=/(.v)

Операция обработки КИХ-фильтром F!R(a\b, {x:X}* Í :=0;{y : H}* (s := .v + h(y)a|' (x + у))Л c{\):=s/q )

Параллельная декомпозиция операции локальной обработки скользящим окном в общем виде Шо(а„|ь ,C„II,F)= (¡ÍJVoja^f .C^.II.F)

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

Введем функцию / = !?(«), определяющую время выполнения итератора 0(Х,/•'(.?)) в зависимости от количества элементов множества X, и ее обозначение при записи модели в(Х,/г(лг))[1?(л)], где п = сагс!(Х).

В диссертации сформулированы правила формирования функций времени выполнения итератора при выполнении преобразований.

Для Ы и 12: в(г.^))[1?(я + А)] = 0(хл,(т))[1>(я)];в(У,^(л))[д(*)], где п = сагс1(Х), к = сагс!(У) и саг<1(г) = п +к.

Для ЬЗ:

({х: X} * /гДО, (п)];({,: X} * С (х))[А (п)] = ({дс: X} * (Г(дг);С(х)))[д(я)], где п = сап!(Х) и, в общем случае, б(п) *!?,(") + Л (и).

Для М, Ь5 И Ь7: (е(Х,^(л))[^(н)]Цв(К.С(д:))[1?,.(Л)])[тах(^.(н),1?1.(А))], где п = саг(1{Х), к = саги (У).

Для Ь6: Если Х = ух,, V/ к^сап!(Х,) и Х,ПХ, = 0,У/,./:1*у,то

В ходе экспериментальных исследований было установлено, что для

итераторов, в теле которых нет операций чтения/записи данных с внешних

запиминающих устройств (ВЗУ), операций коммуникации, хорошей моделью

функции времени выполнения итератора является линейная функция

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

если X = УX,, V/ к = сап1(Х,), п = сап1(Х) = Р к , X, П Х; = 0,V/,7:/ * у, модель функции

1-1

времени выполнения итератора определяется следующим образом

где 00 - накладные расходы на формирование параллельных ветвей итератора.

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

({дс: X} * • «];({*: X] * С(дг))[в„ • п] = ({*: X}*(^(дс);С(дг)))[в(и) * б„ ■ А ■ я],

где п = саг(1(Х).

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

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

е(*. *■(,))[>(« •*)>{*,: х} *({*: X,} * (*))[>(*)].

е(Х.Г(*))[0(п) = *Г ■ л] = {X :Х} * 1) •

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

Завершают первую главу диссертации примеры построения информационных моделей типичных задач обработки изображений, которые часто используются как при исследовании различных реализаций систем обработки изображений, так и в специализированных тестах (фирмы Intel, портала www.ixbl.com) при сравнении производительности вычислительных систем. В каждом примере сначала строится модель, формируемая как простая последовательность типовых операций, а затем с помощью эквивалентных преобразований - модель, допускающая отображение на параллельные вычислительные системы. Рассмотрены следующие примеры: 1) эквализация гисто1раммы; 2) линейное повышение контрастности; 3) выделение контуров с помощью оператора Собела; 4) каскадная медианная фильтрация; 5) последовательная обработка изображения набором КИХ-фильтров с произвольной маской.

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

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

Рисунок 2 - Экспериментальные Рисунок 3 - Зависимость

зависимости времени выполнения эффективности параллельной обработки обработки от размера изображения от размера изображения

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

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

В диссертации представлена модель доступа к данным на ВЗУ, которая учитывает особенности конкурентного выполнения процессов пользователя и служебных процессов операционной системы. Модели операций чтения/записи данных с диска определены следующим образом: 1(a) = ({х :Х}*(с?а(х) -> SKIP)) || SYSTEM _ READ, SYSTEM_READ = (-*о/)*(READ(B)[ú„ пй]-{Ь :В}*(с\Ь~> SKIP)), 0(a) = (({x :X}*(c!a(x)—» SKIP));(cleof -> SKIP)) || SYSTEM_WRITE, SYSTEM_WRITE = (-*"/)*(({/):B}*((<:?/; -» SKlP)\(c1 eof ->SKIP))\,WRITE{B)[úw • ;>„]).

В общем случае (как это отмечено в работах Ластовецкого и Донгара) точная модель времени выполнения операций ввода/вывода может быть получена лишь в виде некоторой экспериментальной зависимости от объема передаваемых данных l(a)[t?(n)], /1 = card(a е F") и 0(а)[|>(и)],« = carci(a eF").

Для большеформатных изображений такая зависимость может приближаться к линейной l(a)[= úR ■ л], и = card [я е F*) и 0(а)[=д№ •л],н = «/г</(аеРх), что подтверждается результатами экспериментов, показанных на рисунке 4.

Модель коммуникационных взаимодействий программ должна, с одной стороны, быть достаточно простой и конструктивной, а с другой стороны, отражать особенности выполнения процессов обработки изображений с помощью итераторов. Существующие модели времени выполнения коммуникационных операций в большинстве случаев не учитывают возможность совмещения процессов передачи данных и их обработки. В диссертации предложен а конструктивная модель и методы оценивания ее параметров которые позволяют учесть указанные особенности. Ниже представлены модели коммуникационных взаимодействий, определяющие операции передачи и получения изображения: S(a) = (({х: X} * (с!а(х) -> SKIP)\.{c\eof -> SK1P))\\SYSTEM _SEND

SYSTEM_SEND = (л»/)*(({&: fl} *((< ?/) -> SKIP)\(cTeof S/C/P)));CO,UV/(B)[1?„ +■ //„])

R(a) = ({x: X} * (c?a(x) -> SKIP)) || SYSTEM _RECV

SYSTEM_RECV = (-*of)*(cOMM(B)[ú0 +1?, n„}:{b:B} * [c\h ^ SKIP)).

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

{X,: Х}^(/?(Х,)[^ ];5(Х,))[(так(1Эл.13„ + й, • »))■ *], где Х = , п = сагс1(Х,).

(=1

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

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

Рисунок 4 - Экспериментальная Рисунок 5 - Зависимость эффективности зависимость времени чтения данных от размера изображения с учетом

изображения от размера изображения операций ввода/вывода

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

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

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

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

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

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

Выполняется предварительная декомпозиция на 2Р блоков:

Фрагмент распределенного изображения аг[т на /и-ом узле хранения содержит

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

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

= х,|2,„-2 и х,|,,„., и хч|2т и , х^^х^их^.их^.их^, ,

Именно данные основных блоков Х?|,1п_, и Х^ формируются на т-ом узле в

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В процессе работы системы фрагменты не перемещаются. Фрагменты только дублируются или удаляются. Фрагменты дублируются:

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

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

Фрагменты удаляются в процессе оптимизации системы хранения или по команде пользователя:

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

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

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

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

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

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

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

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

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

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

В диссертации проведено аналитическое исследование эффективности предложенного алгоритма для идеализированного случая несбалансированной вычислительной системы, у которой производительность одного из узлов выше остальных в ц>1 раз. Показано, что если распределенная система состоит из четырех узлов (М = 4), то предлагаемый алгоритм может равномерно распределить нагрузку даже при трехкратном превышении производительности одного из узлов над остальными. Более производительный узел обеспечит обработку половины строк изображения, а на долю остальных узлов достанется по 1/6 части.

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

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

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

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

0,25 0,20 0,15 0,10 0,05 О

1.0 1.4 1,8 2,2 2,6 3,0 Коэффициент производительности

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

Проведены вычислительные эксперименты по сравнению времени решения задач обработки изображений с использованием предлагаемой динамической балансировки и без нее. Эксперименты проводились на вычислительном кластере НР сЗООО, имеющем 14 вычислительных узлов. Исследовались режимы монопольного использования и разделяемого доступа, различные модели нагрузки. Эксперименты показали, что при возрастании вычислительной нагрузки вдвое на 7 узлах (из 14) использование предлагаемой динамической балансировки

Относительное сокращение времени обработки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• мастер-сервис размещен на управляющем узле вычислительного кластера и дополнительно совмещает функции всех узел-сервисов системы.

Система параллельной обработки крупноформатных изображений реализована на вычислительном кластере HP сЗООО на базе 7 сдвоенных блейд серверов HP ProLiant BL2x220c G5 в качестве вычислительных узлов и 1-го сервера HP ProLiant BL260c в качестве управляющего узла. Основные характеристиками кластера: I управляющий узел (CPU: Quad-Core Intel Xeon 5430 2.66 GHz, cache 12 Mb, 1333MHz; RAM: 4Gb DDR2-667; HDD: 240Gb) и 14 вычислительных узлов (2 CPU: Quad-Core Intel Xeon 5430 2.33 GHz, cache 12 Mb, 1333MHz; RAM: 8Gb DDR2-667;

HDD: 120Gb). Данная система использоватась в качестве тестовой при проведении вычислительных экспериментов, описанных в диссертации.

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

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

Приведены две системы технического зрения (СТЗ), при разработке которых в качестве исследовательской системы использовалась сервис-ориентированная распределенная система обработки изображений.

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

СТЗ "Система регистрации железнодорожных составов цистерн" успешно внедрена и работает на ОАО "Самара-терминал" (г. Сызрань) и на Уфимском нефтеперерабатывающем заводе.

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

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

использованием описанной СТЗ позволяет выявить в 5-7 раз большее количество разрывов по сравнению с визуальным наблюдением.

Рисунок 8 - Пользовательский экран Рисунок 9 - Пользовательский экран СТЗ рабочего места оператора системы для обнаружения локальных

регистрации железнодорожных неоднородностей

составов цистерн

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

Монографии

1. Мясников, В.В. Теоретические основы цифровой обработки изображений [Текст] / В.В. Мясников, С.Б. Попов, В.В. Сергеев, В.А. Сойфер // Методы компьютерной обработки изображений / под общ. ред В.А. Сойфера; М.В. Гашников [и др.] — 2-ое изд., испр. - М.: Физматлит, 2003. - Часть I. - С. 13-298.

2. Гашников, М.В. Компрессия изображений [Текст] / М.В. Гашников, Н.И, Глумов, С.Б. Попов, В.В. Сергеев // Методы компьютерной обработки изображений / под общ. ред В.А. Сойфера; М.В. Гашников [и др.] - 2-ое изд., испр. - М.: Физматлит, 2003. - Часть II, Глава 6. - С.385-458.

3. Computer Image Processing, Part I: Basic concepts and theory [Текст] / edited by Victor A. Soifer; V.V. Myasnikov, S.B. Popov, V.V. Sergeyev, V.A. Soifer - VDM Verlag, 2010.-286 p.

4. Gashnikov, M.V. Image Compression [Текст] / M.V. Gashnikov, N.I. Glumov, S.B. Popov, V.V. Sergeyev // Computer Image Processing, Part II: Methods and algorithms / edited by Victor A. Soifer; A.V. Chernov [et al.] - VDM Verlag, 2010. - Chapter 6. -P.87-160.

Статьи в eedyufuxрецензируемых журналах и изданиях, входящих в перечень ВАК

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

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

7. Popov, S.B. Investigation of Modifications of Algorithms for Fractal Image Encoding [Текст] / S.B. Popov, I.A. Khasanov // Pattern Recognition and Image Analysis. -1996. - Vol. 6, No. 1.-p. 174.

8. Popov, S.B. Architecture of the Software for Image Processing in OS/2 [Текст] / S.B. Popov, V.V. Sergeyev, N.I. Frolova II Pattern Recognition and Image Analysis. -1996. - Vol. 6, No.2. - p.432.

9. Glumov, N.I. Some Application Shells of Image Processing for IBM PCs [Текст] / N.I. Glumov, V.V. Myasnikov, S.B. Popov, P.V. Raudin, V.V. Sergeyev, N.I. Frolova, A.V. Chernov // Pattern Recognition and Image Analysis. - 1996. - Vol. 6, No. 2. - p.372.

10. Popov, S.B. Scalable Automatic System of Image Processing with the Possibilities of Adaptation and Distributed Processing [Текст] / S.B. Popov // Pattern Recognition and Image Analysis. - 1998. - Vol.8, No.3. -pp.380-381.

11. Gashnikov, M.V. Software System for Transmitting Large-Size Images via the Internet [Текст] / M.V. Gashnikov, N.l. Glumov, S.B. Popov, V.V. Segreyev, E. A Farberov // Pattern Recognition and Image Analysis. - 2001. - Vol. II, No.2. -pp.430-432.

12. Попов, С.Б. Кластерная технология формирования и параллельной фильтрации больших изображений [Текст] / С.Б. Попов, В.А. Сойфер, А.А. Тараканов, В.А. Фурсов // Компьютерная оптика. - 2002. - Вып. 23. - С.75-78.

13. Никоноров, А.В. Сравнительный анализ моделей цветообразования при офсетной многокрасочной печати [Текст] / А.В. Никоноров, С.Б. Попов // Компьютерная оптика. - 2002. - Вып. 23. - С.79-83.

14. Никоноров, А.В. Принцип согласованности оценок в задаче идентификации моделей цветовоспроизведения [Текст] / А.В. Никоноров, С.Б. Попов, В.А. Фурсов // Компьютерная оптика. - 2002. - Вып. 24. - С.148-151.

15. Дроздов, М.А. Кластерная технология определения восстанавливающих фильтров и обработки больших изображений [Текст] / М.А. Дроздов, Д.И. Зимин, С.Б. Попов, С.А. Скуратов, В.А. Фурсов // Компьютерная оптика. -2003. - Вып. 25. - С.175-182.

16. Nikonorov, A. Identifying Color Reproduction Models [Текст] / Nikonorov A., Popov S., Fursov V. // Pattern Recognition and Image Analysis. — 2003. - Vol. 13, No.2. -pp. 315-318.

17. Volotovskii, S.G. Machine Vision System for Registration of Oil Tank Wagons [Текст] / Volotovskii S.G., Kazanskii N.L., Popov S.B., Khmelev R.V. // Pattern Recognition and Image Analysi. - 2005. - Vol. 15, No. 2. - pp.461-463.

18. Волотовский, С.Г. Система технического зрения для распознавания номеров железнодорожных цистерн с использованием модифицированного коррелятора в метрике Хаусдорфа [Текст] / С.Г. Волотовский, Н.Л. Казанский, С.Б. Попов, Р.В. Хмелев // Компьютерная оптика. - 2005. - Вып. 27. - С. 177-184.

19. Буланов, А.П. Система технического зрения для регистрации железнодорожных составов цистерн [Текст] / Буланов А.П., Волотовский С.Г., Казанский Н.Л., Попов С.Б., Хмелев Р.В., Шумаков С.М. //Автоматизация в промышленности. -2005.-№6.-С. 57-59.

20. Игнатов, Н.А. Моделирование системы управления динамометрическим стендом [Текст] / Н.А. Игнатов, Н.Л. Казанский, Ю.И. Корнев, С.Б. Попов // Вестник Самарского государственного технического университета. Серия Физико-математические науки. -2005. -Вып. 38. - С.115-121.

21. Волотовский, С.В. Распознавание номеров железнодорожных цистерн с использованием быстрой локализации и модификации алгоритма сравнения объекта с эталоном по среднеквадратической метрике Хаусдорфа [Текст] / С.В. Волотовский, Н.Л. Казанский, С.Б. Попов, Р.В. Хмелев // Обозрение прикладной и промышленной математики. - 2005. - Том 12, № 3. - С. 714.

22. Попов, С.Б. Концепция распределенного хранения и параллельной обработки крупноформатных изображений [Текст] / С.Б. Попов // Компьютерная оптика. -2007. - Том 31, № 4. - С. 77-85.

23. Казанский, H.JT. Система технического зрения для определения количества гель-частиц в растворе полимера [Текст] / Н.Л. Казанский, С.Б. Попов // Компьютерная оптика. - 2009. - Том 33, № 3. - С. 325-331.

24. Kazanskiy, N. L. Machine Vision System for Singularity Detection in Monitoring the Long Process [Текст] / N. L. Kazanskiy and S. B. Popov // Optical Memory and Neural Networks (Information Optics). - 2010. - Vol. 19, No. 1. - pp. 23-3 0.

25. Попов, С.Б. Моделирование информационной структуры параллельной обработки изображений [Текст] / С.Б. Попов // Компьютерная оптика. — 2010. — Том 34, № 2. - С.231-242.

26. Казанский, H.JI. Использование волноводного резонанса для создания нанооптических спектральных пропускающих фильтров [Текст] / НЛ. Казанский, П.Г. Серафимович, С.Б. Попов, С.Н. Хонина // Компьютерная оптика. - 2010. - Том 34, № 2. - С.162-168.

Свидетельства о регистрации программ для ЭВМ и патент на изобретение

27. Программное обеспечение обработки изображений IPS 1.0 RSX11M / Бамбулевич К.Э., Васин А.Г., Маслов A.M., Попов С.Б., Сергеев В.В., Сойфер В.А. // Гос. фонд алгоритмов и программ СССР, № 50850000495, 1985.

28. Система регистрации железнодорожных составов цистерн / Волотовский С.Г., Казанский Н.Л. Попов С.Б. // Свидетельство об официальной регистрации программ для ЭВМ № 2004611969 по заявке № 2004611381 от 29 июня 2004 г. Зарегистрировано в Реестре программ для ЭВМ 26 августа 2004 г.

29. Программное обеспечение распознавания номеров на основе анализа топологии контуров/ Волотовский С.Г., Казанский Н.Л., Попов С.Б. // Свидетельство об официальной регистрации программ для ЭВМ № 2004611970 по заявке № 2004611382 от 29 июня 2004 г. Зарегистрировано в Реестре программ для ЭВМ 26 августа 2004 г.

30. Программное обеспечение распознавания номеров на основе анализа взаимных отклонений геометрических форм объекта и эталона I Хмелев Р.В., Казанский Н.Л., Попов С.Б. // Свидетельство об официальной регистрации программ для ЭВМ № 2004611971 по заявке № 2004611383 от 29 июня 2004 г. Зарегистрировано в Реестре программ для ЭВМ 26 августа 2004 г.

31. Спектральный идентификатор моделей цветовоспроизведения / Никоноров A.B., Попов С.Б., Фурсов В.А. И Свидетельство об официальной регистрации программ для ЭВМ № 2007614955 по заявке № 2007613925 от 5 октября 2007 г. Зарегистрировано в Реестре программ для ЭВМ 3 декабря 2007 г.

32. Модуль реализации модели цветовоспроизведения Нойгебауэра-Юла-Нейлсона/ Никоноров A.B., Попов С.Б., Фурсов В.А. // Свидетельство об официальной регистрации программ для ЭВМ № 2008611512 по заявке № 2008610367 от 5 февраля 2008 г. Зарегистрировано в Реестре программ для ЭВМ 25 марта 2008 г.

33. Способ распознавания разрывов струи раствора на изображении / Казанский Н.Л., Козин Н.Е., Попов С.Б., Фурсов В.А. // Патент РФ на изобретение № 2336563 от 20.10.2008 года по заявке № 2006115915/09 от 10.05.2006 года. Бюл. №29.

Подписано в печать 30.06.2010 г. Тираж 100 экз. Формат 60x84 1/16. Бумага офсетная. Усл. печ.л. 2,0

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

Введение

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

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

1.2. Типология и основные особенности технологий обработки изображений.

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

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

1.5. Формальная модель итератора преобразования данных.

1.6. Модели типовых операций обработки изображений.

1.6.1. Формальная модель операции поэлементного преобразования.

1.6.2. Формальная модель операции оценки характеристик изображения.

1.6.3. Формальная модель операции локальной обработки скользящим окном.

1.7. Модель предиктивной оценки времени выполнения задачи обработки.

1.8. Моделирование базовых задач обработки изображений.

1.8.1. Модель задачи эквализации гистограммы.

1.8.2. Модель задачи линейного повышения контрастности.

1.8.3. Модель задачи выделения контуров.

1.8.4. Модель каскадной медианной фильтрации.

1.8.5. Модель технологии последовательной обработки изображения набором КИХ-фильтров.

Выводы.

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

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

2.2. Модели локального хранения данных (изображений).

2.3. Модели коммуникационной среды при параллельной обработке на распределенных системах.

2.4. Проблемы согласования потенциального параллелизма с распределением данных.

2.5. Распределенное изображение и декомпозиция данных.

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

2.7. Организация данных и визуализация распределенных изображений.

Выводы.:.

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

3.1. Методы организации параллельной обработки изображений.

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

3.3. Балансировка вычислительной нагрузки при пространственном распараллеливании вычислений.

3.4. Динамическая организация размещения данных распределенных изображений.

3.5. Алгоритм динамического распределения вычислительной нагрузки.

Выводы.

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

4.1. Архитектура программных средств систем обработки изображений.

4.2. Система обработки изображений с модульной динамической структурой.

4.3. Организация программного обеспечения распределенной обработки изображений.

4.4. Программная система передачи крупноформатных изображений по сети Internet.

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

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

4.7. Кластерная система параллельной обработки крупноформатных изображений.

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

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

Выводы.

Введение 2010 год, диссертация по информатике, вычислительной технике и управлению, Попов, Сергей Борисович

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

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

АЛ. Ластовецкого, В.Э. Малышкина, А.Г. Марчука, Н.Н. Миренкова, L.J. Baer, M.I. Colé, J. Dongarra, I. Foster , L. Lamport и др. [13-15, 18, 19, 4850,58, 60, 67, 128, 139, 160]

В работах В.В. Воеводина [22, 23] была выдвинута гипотеза о том, что в конкретных вычислительных областях типовых информационных структур немного. Разработка моделей информационных технологий в конкретных прикладных областях является актуальной задачей, поскольку открывает новые подходы к разработке специализированных программных средств, эффективно решающих задачи определенного класса на распределенных ВС, и спецпроцессоров, реализующих быстрое выполнение целевых алгоритмов.

В частности, это актуально в области компьютерной обработки изображений. В этой области исследований следует отметить ведущие отечественные школы В.А. Сойфера, В.В. Сергеева, В.С. Киричука, Я.А. Фурмана, Ю.А. Брюханова, К.К. Васильева и др. Разработка систем параллельной обработки изображений ведется В.П. Пяткиным [117]. В области создания распределенных систем параллельной обработки изображений можно отметить работы групп исследователей из университетов США, Испании (University of Extremadura), Италии (University of Naples "Parthenope"), Нидерландов (Delft University of Technology, University of Amsterdam), Франции (Université París Sud, University of Burgundy) и Японии (Kyushu University). В работах, связанных с параллельной обработкой изображений, в основном рассматриваются вопросы построения параллельных алгоритмов обработки изображений, адаптации последовательных алгоритмов применительно к параллельным архитектурам ВС [163].

Естественный при обработке изображений параллелизм, основанный на декомпозиции данных, позволяет достаточно легко адаптировать последовательные реализации широкого спектра задач обработки для их выполнения на многоядерных процессорах. Однако с увеличением размеров изображений время их обработки все более определяется временем, затрачиваемым на операции ввода/вывода [180]. В таких условиях при обработке крупноформатных изображений с использованием относительно простых в вычислительном отношении задач эффективность использования многоядерных процессоров резко падает. Существующие тенденции развития вычислительной техники [177] еще более обостряют проблему: все увеличивающийся разрыв между производительностью процессоров и быстродействием устройств постоянного хранения данных существенно снижает показатели общей эффективности ВС при решении прикладных задач. Вместе с тем скорость передачи данных в локальных сетях растет существенно быстрее, чем аналогичный показатель для дисковых запоминающих устройств (ЗУ). В настоящее время скорость обмена данными в сетях на базе технологии Gigabit Ethernet (ЮЬЕ) находится приблизительно на одном уровне с дисками типовых конфигураций компьютера, но при переходе на технологию lOGbE ситуация кардинально изменится - визуализация крупноформатного изображения будет выполняться быстрее при удаленном, а не локальном хранении данных. В таких условиях использование распределенных систем для хранения и обработки крупноформатных изображений становится актуальным [30, 43, 57, 113, 130].

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

Цель и задачи исследования

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

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

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

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

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

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

Методы исследования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы

Основные результаты работы докладывались на 27 научных конференциях и семинарах: Второй Всесоюзной конференции «Методы и средства обработки сложной графической информации», г. Горький, 1985; Всесоюзной конференции «Методы и средства обработки сложной графической информации», г. Горький, 1988; Втором Республиканском семинаре "Проблемы создания систем обработки, анализа и распознавания изображений", г. Ташкент, 1989; Всесоюзном симпозиуме "Методы и применение голографической интерферометрии". г.Куйбышев, 1990; Первой Международной конференции «International Conference On Information Technologies For Image Analysis and Pattern Recognition (ITIAPR'90)», г. Львов, 1990; Четвертой Всесоюзной конференции «Методы средства обработки сложной графической информации», г. Горький, 1991; Второй Всероссийской с участием стран СНГ конференции «Распознавание образов и анализ изображений: Новые информационные технологии», г. Ульяновск, 1995; Пятом Международном семинаре «Распределенная обработка информации», г.Новосибирск, 1995; Третьей конференции «Распознавание образов и анализ изображений: Новые информационные технологии», г. Нижний Новгород, 1997; Пятой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-5-2000), г. Самара, 2000; Международной конференции «Математическое моделирование - 2001», г. Самара, 2001; Научно-методической конференции «Телематика 2002», г. С-Петербург, 2002; Шестой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-б-2002), г. Великий Новгород, 2002; Втором Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах», г. Нижний Новгород, 2002; Третьем Международном научно-практическом семинаре

Высокопроизводительные параллельные вычисления на кластерных системах», г. Нижний Новгород, 2003; Международной конференции «Распределенные вычисления и Грид-технологии в науке и образовании», г. Дубна, 2004; Седьмой Международной конференции «International Conference on Pattern Recognition and Image Analisis: New Information Technologis» (PRIA-7-2004), г. Санкт-Петербург, 2004; Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений», г. Новороссийск, 2005; Второй Международной конференции «Distributed Computing and Grid-Technologies in Science and Education», г. Дубна, 2006; Всероссийской научной конференции «Научный сервис в сети Интернет: технологии параллельного программирования», г. Новороссийск, 2006; Четырнадцатой Всероссийской научно-методической конференции «Телематика'07», г. Санкт-Петербург, 2007; Всероссийской научной конференции «Научный сервис в сети Интернет: многоядерный компьютерный мир», г. Новороссийск, 2007; Тринадцатой Всероссийской конференции «Математические методы распознавания образов», Ленинградская обл., г. Зеленогорск, 2007; Седьмом Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах», г. Нижний Новгород, 2007; Всероссийской научной конференции «Научный сервис в сети Интернет: решение больших задач», г. Новороссийск, 2008; Третьей Международной конференции «Distributed Computing and Grid-Technologies in Science and Education», г. Дубна, 2008; Всероссийской суперкомпьютерной конференции «Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность», г. Новороссийск, 2009.

Связь с государственными и международными программами

Основные результаты диссертации получены в рамках научно-исследовательских работ (НИР) по международным, государственным, межвузовским и региональным научно-техническим программам: грантам Российского фонда фундаментальных исследований №№ 02-01-00119-а, 02-01 -08055-инно, 03-01 -00109-а, 04-07-90149-а, 04-07-96500-р2004поволжьев, 05-01-08043-офиа, 06-08-01024-а, 07-07-00210-а, 10-07-00553-а; программе фундаментальных исследований Президиума РАН «Проблемы создания национальной научной распределенной информационно-вычислительной среды на основе развития GRID технологий и современных телекоммуникационных сетей» по направлению № 4 "Оптимизация вычислительных архитектур под конкретные классы задач, информационная безопасность сетевых технологий, применение распределенных информационно-вычислительных систем"; гранту Президента России по поддержке ведущих научных школ — НШ-3086.2008.9 «Разработка теоретических основ и создание информационноых технологий обработки изображений и компьютерной оптики»; Российско-американской программе "Фундаментальные исследования и высшее образование" ("BRHE" CRDF Project SA-014, 2002-2010 гг.); государственной научно-технической программе "Перспективные информационные технологии" (1994-1999 гг.).

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

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

Выводы:

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

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

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

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

Заключение

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

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

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

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

Библиография Попов, Сергей Борисович, диссертация по теме Математическое моделирование, численные методы и комплексы программ

1. Д.Н., Храмов А.Г., Шамалова Г.В. // Журнал технической физики. — 1990. Том 60, вып. 6. - С. 157-161.

2. Арнольд, К. Язык программирования Java Текст. / К. Арнолд, Дж. Гослинг, Д. Холмс. М.: Вильяме, 2001. - 624 с. - ISBN 5-84590215-0.

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

4. Бахман, П. Программные системы: Применение. Разработка. Обоснование Текст. / П. Бахман [и др.]; под ред. П. Бахмана. М.: Мир, 1988. - 288 с. - ISBN 5-03-001114-5.

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

6. Вальковский, В. А. Элементы параллельного программирования Текст. /В. А. Вальковский, В. Е. Котов, А. Г. Марчук, Н. Н. Миренков.-М.: Радио и связь, 1983. -239 с.

7. Вальковский, В. А. Формальные модели параллельных программ и вычислений Текст. / Вальковский В. А. — Новосибирск: Изд-во НГУ, 1984.-88 с.

8. Вальковский, В. А. Синтез параллельных программ и систем на вычислительных моделях Текст. / В.А. Вальковский, В.Э. Малышкин. Новосибирск: Наука, 1988. - 128 с.

9. Вирт, Н. Алгоритмы и структуры данных Текст. / Н. Вирт. — М.: Мир, 1989. 360 с. - ISBN 5-03-001045-9.

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

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

12. Воеводин, В. В. Математические основы параллельных вычислений Текст. / В. В. Воеводин М.: МГУ, 1991. - 345 с.

13. Воеводин, В. В. Отображение проблем вычислительной математики на архитектуру вычислительных систем Текст. / В. В. Воеводин // Вычислительные методы и программирование. — 2000. — Т. 1. — С. 3744.

14. Воеводин, В. В. Параллельные вычисления Текст. / В. В. Воеводин, Вл. В. Воеводин. СПб. : БХВ-Петербург, 2002. - 608 с. - ISBN 594157-160-7.

15. Востокин, C.B. Графическая объектная модель параллельных процессов и ее применение в задачах численного моделирования Текст. / C.B. Востокин. Самара: Изд-во Самарского научного центра РАН, 2007. - 286 с. - ISBN 978-5-93424-284-9.

16. Гамма, Э. Приемы объектно-ориентированного проектирования. Паттерны проектирования Текст. / Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес. СПб.: Питер, 2001.-368 с. - ISBN 5-272-00355-1.

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

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

19. Грузман, И.С. Цифровая обработка изображений в информационных системах Текст. / И.С. Грузман, B.C. Киричук, В.П. Косых, Г.И. Перетягин, A.A. Спектор. Новосибирск: Изд-во НГТУ, 2002. -352 с.- ISBN: 5-7782-0330-6.

20. Дудин, Е. Б. Информационно-вычислительные технологии в распределенной среде. Обзор Текст. / Е. Б. Дудин, Э. Г. Захарова, Ю.

21. Зубарев, Ю. Б. Цифровая обработка сигналов информатика реального времени Текст. / Ю.Б. Зубарев, В.В. Витязев, В.П. Дворкович. - 1999.

22. Евстигнеев, В.А. Сводимые графы и граф-модели в программировании Текст. / В.А. Евстигнеев, В.Н. Касьянов. -Новосибирск: Изд-во ИДМИ, 1999. 288 с. - ISBN 5-88119-125-0.

23. Ершов, А. П. Об операторных схемах над общей и распределенной памятью Текст. / А. П. Ершов // Кибернетика. 1968. - № 4. - С. 6371.

24. Ершов, А. П. Современное состояние теории схем программ Текст. / А. П. Ершов // Проблемы кибернетики. М.: Наука, 1973. - Вып. 27. -С. 87-110.

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

26. Кнут, Д.Э. Искусство программирования, том 3. Сортировка и поиск Текст. / Д. Э. Кнут 2-е изд. - М.: Вильяме, 2009. - 824 с. - ISBN 978-5-8459-0082-1

27. Корнеев, В.В. Параллельные вычислительные системы Текст. / В.В. Корнеев. -М.: Нолидж, 1999. 320 с. - ISBN 5-89251-065-4.

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

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

30. Мальцев, А.И. Алгебраические системы Текст. / А. И. Мальцев. — М.: Наука, 1970.-392 с.

31. Марчук, Г. И. Проблемы вычислительной техники и фундаментальные исследования Текст. / Марчук Г. И., Котов В. Е. // Автоматика и вычислительная техника. — 1979. — № 2. С. 3-14.

32. Миано, Дж. Форматы и алгоритмы сжатия изображений в действии Текст. / Дж. Миано. М.: Триумф, 2003. 336 с. - ISBN 5-89392-078-3.

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

34. Московский, A.A. Распределенный архив изображений дистанционного зондирования земли Текст. / Московский A.A., Первин А.Ю., Тютляева Е.О., Шевчук Е.В. // Программные продукты и системы. 2009. - № 2. - С. 48-0 - 48-5. - ISSN 0236-235Х.

35. Никоноров, A.B. Параллельная реализация двумерных БИХ-фильтров в распределенной системе обработки изображений Текст. /

36. A.B. Никоноров, М.Г. Милюткин, В.А. Фурсов // Вычислительные методы и программирование. 2010. - Т. 11. - С. 88-94.

37. Сергеев, В.В. Параллельно-рекурсивные КИХ-фильтры для обработки изображений Текст. / В.В.Сергеев // Компьютерная оптика. 1992.-Т. 10-11.-С. 186-201. - ISSN 0134-2452.

38. Таненбаум Э. Распределенные системы. Принципы и парадигмы Текст. / Э. Таненбаум, М. ван Стеен. СПб.: Питер, 2003. - 877 с. -ISBN 5-272-00053-6.

39. Хмелев Р.В. Совместное использование структурного анализа и метрики Хаусдорфа при сравнении объекта и эталона Текст. / Р.В. Хмелев // Компьютерная оптика. 2005. - Вып. 27. - С. 174-176.

40. Xoap, Ч. Взаимодействующие последовательные процессы Текст. / Ч. Хоар. М:Мир, 1989. - 264с.

41. Фаулер, М. Архитектура корпоративных программных приложений Текст. / М. Фаулер. М.: Вильяме, 2004. - 544 с. - ISBN 5-8459-05796.

42. Эндрюс, Г.Р. Основы многопоточного, параллельного и распределенного программирования Текст. / Г.Р. Эндрюс. — М.: Вильяме, 2003. 512 с. - ISBN 5-8459-0388-2.

43. Alexander, W. Е. Parallel Image Processing with the Block Data Parallel Architecture Text. / W. E. Alexander, D. S. Reeves, C. S. Gloster // Proceedings of the IEEE. 1996. - Vol. 84, N. 7. - P. 947-968.

44. Aritsugi, M. Several partitioning strategies for parallel image convolution in a network of heterogeneous workstations Text. / M. Aritsugi, H. Fukatsu, Y. Kanamori // Parallel Computing. 2001. - Vol. 27, N. 3. - P. 269-293.-ISSN 01678191.

45. Ballard, D. Computer Vision Text. / D. Ballard, C. Brown. Prentice Hall, 1982. - 544 c. - ISBN 978-0131653160.

46. Boisvert, R. F. Mathematical Software: Past, Present and Future Text. / R. F. Boisvert // Mathematics and Computers in Simulation. 2000. - Vol. 54,-P. 227-241.

47. Buchnev, A.A. Software Complex for Processing Aerospace Images Text. / Buchnev A.A., Pyatkin V.P. // Pattern Recognition and Image Analysis. 1999. - Vol. 9, № 2. - P. 308-310.

48. Caarls, W. Skeletons and Asynchronous RPC for Embedded Data- and Task Parallel Image Processing Text. / W. Caarls, P. P. Jonker, H. Corporaal // IEICE Transactions on Information and Systems. 2006. -Vol. E89-D, N. 7. - P. 2036-2043.

49. Cameron, K. W. Predicting and Evaluating Distributed Communication Performance Text. / K. W. Cameron , R. Ge // Proceedings of the 2004 ACM/IEEE Conference on Supercomputing. 2004. - P. 1-15.

50. Chapuis, R. Fast prototyping of parallel vision applications using functional skeletons Text. / R. Chapuis, J. Serot, D. Ginhac, J. Derutin // Journal of Machine Vision and Applications. 2001. - Vol. 12, N. 6. -P. 271-290.

51. Chen, W. LogGPO: An accurate communication model for performance prediction of MPI programs Text. / W. Chen, J. Zhai, J. Zhang, W. Zheng // Science in China Series F: Information Sciences. — 2009. Vol. 52, N. 10.-P. 1785-1791.-ISSN 1009-2757.

52. Chernov, A.V. Program system for distributed image processing Text. / Chernov A.V., Myasnikov V.V., Myasnikov E.V., Sergeev V.V. // Pattern Recognition and Image Analysis. 2003. - Vol. 13, N. 2. - P. 228-230.

53. Cole, M.I. Algorithmic Skeletons: Structural Management of Parallel Computation Text. / M.I. Cole. Cambdridge, MA, USA: MIT Press, 1989. - 224 c. -ISBN 978-0262530866.

54. Congiusta, A. Service-oriented middleware for distributed data mining on the grid Text. / A. Congiusta, D. Talia, P. Trunfio // Journal of Paralleland Distributed Computing. 2008. - Vol. 68, N. 1. - P. 3-15. - ISSN 07437315.

55. Crookes, D. Architectures for high performance image processing: The future Text. / D. Crookes // Journal of Systems Architecture. 1999. -Vol. 45, N. 10.-P. 739--748. - ISSN 13837621.

56. Czarnul, P. Towards Efficient Parallel Image Processing on Cluster Grids using GIMP Text. / P. Czarnul , A. Ciereszko , M. Fraczak // Lecture Notes in Computer Science, Vol. 3037. — Berlin, Heidelberg: Springer, 2004.-P. 451-458.

57. Deng, Y. Dynamic and scalable storage management architecture for Grid Oriented Storage devices Text. / Y. Deng, F. Wang, N. Helian, S. Wu, C. Liao // Parallel Computing. 2008. - Vol. 34, N. 1. - P. 17-31. - ISSN ' 01678191.

58. Denoulet, J. An architecture based on reconfigurability and asynchronism for real-time image processing Text. / J. Denoulet, A. Merigot // Journal of Real-Time Imaging. 2008. - Vol. 3, N. 3. - P. 119-130.

59. Deris, M. M. An efficient replicated data access approach for large-scale distributed systems Text. / M. M. Deris, J. H. Abawajy, A. Mamat // Future Generation Computer Systems. 2008. - Vol. 24, - P. 1-9.

60. Ducourthial, B. Parallel asynchronous computations for image analysis Text. / B. Ducourthial, A. Merigot // Proceedings of IEEE. 2002. - Vol. 90, N. 7.-P. 1218-1229.

61. Falcou, J. Quaff: efficient C++ design for parallel skeletons Text. / J. Falcou, J. Serot, T. Chateau, J. Lapreste // Parallel Computing. 2006. -Vol. 32, N. 7-8. - P. 604-615. - ISSN 01678191.

62. Fallacies of Distributed Computing Electronic resource. Режим доступа:http://en.wikipedia.org/wiki/FallaciesofDistributedComputing, дата доступа: 14.06.2010.

63. Foster, I. Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering Text. / I. Foster. Addison Wesley, 1995.-430 c.-ISBN 978-0201575941.

64. Gonzalez, R. C. Digital Image Processing Text. / R.C. Gonzalez, R.E. Woods. 3rd Edition - Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 2006.- ISBN 013168728X.

65. Grosu, D. Cooperative load balancing in distributed systems Text. / D. Grosu, A. T. Chronopoulos, M. Y. Leung // Concurrency and Computation: Practice and Experience. 2008. - Vol. 20, N. 16. - P. 1953-1976. - ISSN 15320626.

66. Hockney, R. The communication challenge for MPP: Intel Paragon and Meiko CS- 2 Text. / R. Hockney // Parallel Computing. 1994. - Vol. 20, N. 3.-P. 389-398.

67. EEMBC ConsumerBench Data Book Electronic resource. Режим доступа: http://www.eembc.org/benchmark/digitalentertainmentsl.php, дата доступа: 14.06.2010.

68. Jonker, P. P. Application Driven Design Of Embedded Real-Time Image Processors Text. / P. P. Jonker , W. Caarls // Proceedings of ACIVS 2003 (Advanced Concepts for Intelligent Vision Systems). 2003. - P. 1-8.

69. Jonker, P. P. Distributed bucket processing: A paradigm embedded in a framework for the parallel processing of pixel sets Text. / P. P. Jonker, J. G. E. Oik, C. Nicolescu // Parallel Computing. 2008. - Vol. 34, N. 12. - P. 735-746. - ISSN 01678191.

70. Juhasz, Z. An Analitical Method for Predicting the Performance of Parallel Image Processing Operations Text. / Z. Juhasz // The Journal of Supercomputing. 1998. -Vol. 12, N. 1/2.-P. 157-174.

71. Lamport, L. Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers Text. / L. Lamport. — Addison-Wesley Professional, 2002. 384 c. - ISBN 978-0321143068.

72. Lastovetsky, A. L. High performance heterogeneous computing Text. / A.L. Lastovetsky, J.J. Dongarra. Hoboken, New Jersey: John Wiley & Sons, Inc., 2009. - 267 c. - ISBN 978-0-470-04039-3.

73. Lee, C. Parallel image processing applications on a network of workstations Text. / C. Lee, M. Hamdi // Parallel Computing. 1995. -Vol. 21, N. l.-P. 137-160.

74. Lee, E. F. A framework for comparing model of computations Text. / E. F. Lee, A. Sangiovanni-Vincentelli // IEEE Trans, on CAD of Integrated Circuits and Systems. 1998. - Vol. 17, N. 12. - P. 1217-1229.

75. Merigot, A. Parallel processing for image and video processing: Issues and challenges Text. / A. Merigot, A. Petrosino // Parallel Computing. 2008. - Vol. 34, N. 12. - P. 694-699. - ISSN 01678191.

76. Miller, J.W.V. Image processing benchmark study Text. / J. W. V. Miller, C. Eddy, F. M. Waltz, R. Hack, J. Wood, D. Stokes // Proceedings of SPIE. 1998. - Vol. 3521, N. 20. - P. 20-26. - ISSN 0277786X.

77. Milner, R. A Calculus of Communicating Systems Text. / R. Milner. -Springer Verlag, 1980. 171 c. - ISBN 978-3-540-10235-9. - (Lecture Notes in Computer Science, Vol. 92, 1980).

78. Morrow, P.J. Efficient implementation of a portable parallel programming model for image processing Text. / P.J. Morrow [et al.] // Concurrency: Practice and Experience. 1999. - Vol. 11. - P. 671-685.

79. Najjar, W. A. Advances in the dataflow computational model Text. / W. A. Najjar, E. A. Lee, G. R. Gao // Parallel Computing. 1999. - Vol. 25,-P. 1907-1929.

80. Nolle, M. PIPS A general purpose Parallel Image Processing System Text. / M. Nolle , G. Schreiber , H. Schulz-Mirbach // DAGM -Symposium Mustererkennung. - 1994. - P. 609-623.

81. Nunez, A. New techniques for simulating high performance MPI applications on large storage networks Text. / A. Nunez, J. Fernandez, J. D. Garcia, F. Garcia, J. Carretero // Journal of Supercomputing. 2010. -Vol. 51.-P. 40-57.

82. Oh, M. Large-scale image sensing by a group of smart image sensors Text. / M. Oh, K. Aizawa // Parallel Computing. 2008. Vol. 34, N. 12. -P. 710-717.-ISSN 01678191.

83. Pallas MPI Benchmarks PMB, Part MPI-1 Text. / Pallas GmbH. - 2000. -35 c.

84. Patterson, D. A. Latency lags bandwith Text. / D. A. Patterson // Communications of the ACM. 2004. - Vol. 47, N. 10. - P. 71 -75.

85. Persa, S. Evaluation of Two Real Time Low Level Image Processing Architectures Text. / S. Persa , C. Nicolescu , P. Jonker // 1APR Workshopon Machine Vision Application (MVA2000). Tokyo: The University of Tokyo, 2000. - P. 295-298.

86. Pitas, I. Parallel Algorithms for Digital Image Processing, Computer Vision and Neural Networks Text. / I. Pitas New York: John Wiley & Sons, 1993. - 410 c. - ISBN 978-0471935667.

87. Ramaswamy, S. A framework for exploiting task and data parallelism on distributed memory multicomputers Text. / S. Ramaswamy, S. Sapatnekar, P. Baneijee // IEEE Transactions on Parallel and Distributed Systems. 1997. - Vol. 8. - P. 1098-1116.

88. Ritter, G. X. Handbook of Computer Vision Algorithms in Image Algebra Text. / G.X. Ritter, J.N. Wilson. 2 ed. - BocaRaton: CRC Press Inc, 2000. - 448 c. - ISBN 978-0849300752.

89. Roscoe, A.W. The Theory and Practice of Concurrency Text. / A.W. Roscoe. Prentice Hall, 1997. 565 c. - ISBN 0136744095.

90. Schneider, S. Concurrent and Real-Time Systems: The CSP approach Text. / S. Schneider. Wiley, 1999. - 526 c. - ISBN 0471623733.

91. Seinstra, F. J. A software architecture for user transparent parallel image processing Text. / F. J. Seinstra, D. Koelma, J. M. Geusebroek // Parallel Computing. 2002. - Vol. 28, N. 7-8. - P. 967-993. - ISSN 01678191.

92. Seinstra, F. J. User transparency: a fully sequential programming model for efficient data parallel image processing Text. / F. J. Seinstra, D.

93. Koelma // Concurrency and Computation: Practice and Experience. 2004.- Vol. 16, N. 6. P. 611-644. - ISSN 1532-0626.

94. Serot, J. Skeletons for parallel image processing: an overview of the SKIPPER project Text. / J. Serot, D. Ginhac // Parallel Computing. -2002.-Vol. 28, N. 12.-P. 1685-1708. ISSN 01678191.

95. Shen, Z. Distributed computing model for processing remotely sensed images based on grid computing Text. / Z. Shen, J. Luo, G. Huang, D. Ming, W. Ma, H. Sheng // Information Sciences. 2007. - Vol. 177, N. 2.- P. 504-518. ISSN 00200255.

96. Sobolewski, M. SORCER: Computing and Metacomputing Intergrid Text. / M. Sobolewski // ICEIS 2008 International Conference on Enterprise Information Systems, June 2008. — P. 74-85.

97. Squyres, J. M. A toolkit for parallel image processing Text. / J. M. Squyres , A. Lumsdaine , R. L. Stevenson // Parallel and Distributed Methods for Image Processing II. 1998. - P. 69-80. - (Proceedings of SPIE, Vol. 3452).

98. Taniguchi, R.-i. Software platform for parallel image processing and computer vision Text. / R.-i. Taniguchi, Y. Makiyama, N. Tsuruta, S. Yonemoto, D. Arita // Proceedings of SPIE. 1997. - Vol. 3166, N. 2. - P. 2-10.- ISSN 0277786X.

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

100. Wang, R. Y. Modeling Communication Pipeline Latency Text. / R. Y. Wang , A. Krishnamurthy , R. P. Martin , Т. E. Anderson , D. E. Culler // Proc. 1998 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems. 1998.

101. Weems, С. C. Image understanding architecture: a status report Text. / C. C. Weems // Proceedings of SPIE. 1995. - Vol. 2368. - P. 235-246.

102. Wu, R. Parallel execution time prediction of the multitask parallel programs Text. / R. Wu, J. Sun, J. Chen // Performance Evaluation. -2008. Vol. 65, N. 10. - P. 701-713. - ISSN 01665316.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00