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

Введение.

ГЛАВА 1. ЭФФЕКТИВНЫЕТЕГИИ ФОРМИРОВАНИЯ НЕКОТОРЫХ СИСТЕМ ИЗОБРАЖЕНИЙ С ПОМОЩЬЮЭВМ.

1.1. Содержательные постановки задач.

1.1.1. Восстановление изображений в геоинформационных системах.

1.1.2. Восстановление изображений скрытых объектов в медицинских исследованиях и диагностике.

1.1.3. Работа с банком арнаментовв художественном дизайне.

1.2. Обозначения, определения и допущения.

1.3. Формальные постановки задач.

1.3.1. Взаимосвязанные изображения, формируемые ЭВМ без видеоускорителя.

1.3.2. Формирование независимых изображений ЭВМ, обладающей платой видеоускорителя.

1.3.3. Формирование взаимосвязанных изображений на ЭВМ, обладающей платой видеоускорителя.

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

1.4.1. Сеть Петри не содержит контуров.

1.4.2. Взаимосвязи между изображениями отображаются сетью Петри содержащей единственный контур.

1.5. Эффективные стратегии восстановления изображений ЭВМ, снабженной видеоплатой.

1.5.1. Восстановление независимых изображений.

1.6. Формирование единичных изображений с центрально-осевой симметрией. симметрией.

Выводы.главы первой.

ГЛАВА 2. РЕГУЛЯРНЫЕ МЕТОДЫ ПОСТРОЕНИЯ ЭФФЕКТИВНЫХ СТРАТЕГИЙ ФОРМИРОВАНИЯ КОРТЕЖЕЙ ИЗОБРАЖЕНИЙ С ПОМОЩЬЮ ЭВМ.

2. 1. Формальные постановки задач.

2.2. Поиск глобально оптимальных решений.

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

2.3.1. Детерминированные методы.

2.3.1.1. Детерминированный спуск по дереву ветвлений в лучшем направлении.

2.3.1.2. Детерминированный поиск на полных соседних планах.

2.3.2. Рандомизированные методы.

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

2.3.2.2. Рандомированный спуск по дереву ветвлений в "лучшем" направлении.

2.4. Постановка и результаты эксперимента.

Выводы.главы второй.

ГЛАВА 3. ЭФФЕКТИВНЫЕ СТРАТЕГИИ ФОРМИРОВАНИЯ СИММЕТРИЧНЫХ ИЗОБРАЖЕНИЙ.

3.1. Допущения и определения.

3.2. Формальные постановки задач.

3.3. Свойства симметричных изображений.

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

Выводы главы третьей.

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

4.1. Обозначения и допущения.

4.2. Вероятностные модели ускорителей.

4.2.1. Модели матричного ускорителя.

4.2.2. Модели работы векторного видеоускорителя.

Выводы главы четвертой.

ГЛАВА 5. САПР ОПТИМАЛЬНЫХ СТРАТЕГИЙ ФОРМИРОВАНИЯ КОРТЕЖЕЙ ИЗОБРАЖЕНИЙ.

5.1. САПР оптимальных стратегий формирования кортежей независимых изображений.

5.1.1. Пакет прикладных программ " 1пс1ерш11".

5.1.2. Пакет прикладных программ " 1пс1ерш12".

5.2. САПР оптимальных стратегий формирования кортежей взаимосвязанных изображений.

5.2.1. Пакет прикладных программ " Берип 1".

5.2.2. Пакет прикладных программ " Берт 2".

5.2.3. Пакет прикладных программ " Берт 3".

5.2.4. Пакет прикладных программ " Берип 4".

5.3. Пакет визуализации сетей Петри "Рейтер'.

Выводы главы пятой.

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

Одним из первых указал на расточительность вычислительных ресурсов везде, где осуществляется компьютерная генерация либо распознавание изображений Патрик Генри Уилсон в своей монографии «Искусственный интеллект», изданной Массачусетским технологическим университетом в 1977 году и переизданной в СССР в 1980г. [36]. Там же им содержательно сформулирована общая проблема поиска оптимальной стратегии решения некоторой задачи с учетом сохранения в памяти периодически используемых элементов. Однако Уилсону не удалось дать формальную постановку проблемы поиска оптимальной стратегии и, как следствие, предложенные в его монографии процедуры оказались в общем случае малоэффективными.

Следующий важный шаг на пути формализации поиска оптимальной стратегии был сделан Карманом Парсайем, Марком Чигнелом, Гари Вонгом и Сетрагом Хошефианом во второй половине 80-х годов привлечением аппарата теории графов для поиска оптимальных стратегий формирования выходных файлов в интеллектуальных базах данных в их монографии «Интеллектуальные базы данных», изданной в Нью-Йорке в 1987 году [58].

В России (в СССР) аналогичный подход практически одновременно был продемонстрирован применительно к поиску оптимальных стратегий программных реализаций конечных алгоритмов Виктором Николаевичем Касьяновым в его монографии «Оптимизирующие преобразования программ», изданной в Москве в 1988 году [20]. В ней объединены ранее опубликованные идеи Ершова и Евстигнеева об использовании методов теории графов для 6 экономии памяти ЭВМ и эффективной декомпозиции алгоритмов. Однако и эти подходы, являясь скорее качественными, чем количественными, повысили наглядность постановки задач поиска соответствующих стратегий, но не позволили полностью формализовать их.

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

1. Привлечение методов дискретной оптимизации для их решения в общем случае;

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

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

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

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

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

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

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

Целью настоящей работы является поиск эффективных стратегий реализации первого этапа восстановления изображения (главы 1 - 3,5) и разработка обоснованных рекомендаций по выбору технических средств реализации второго (глава 4). При этом не имеет значения, какие операции конкретно используются для создания «электронного изображения», важны лишь их самые общие характеристики - время восстановления, объем требуемой для этого оперативной памяти, некоторые параметры, характеризующие изображение.

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

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

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

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

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

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

В данной работе на защиту выносится:

1. Классификация изображений (независимые и взаимосвязанные, симметричные и ассиметричные).

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

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

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

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

Апробация результатов работы. Основные положения диссертации докладывались на научной сессии «МИФИ-99»; на международной научно-практической конференции «Новые информационные технологии в университетском образовании» (г. Новосибирск, 1999 г.); на II Международной научно-практической конференции. «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права», МГАПИ (г. Сочи 1999) По материалам диссертации опубликовано восемь печатных работ.

Результаты, полученные в данной работе, были использованы в качестве учебных материалов в высших учебных заведениях, а также при серийном выпуске СБ-дисков, что подтверждено актами о внедрении (см. Приложение). 9

Выводы;

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

2. Предложены и программно реализованы методы решения задач в общем случае под управлением различных операционных систем;

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

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

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

123

Заключение

Основными итогами работы являются разработки :

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

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

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

1. Аиисимов Б .В., Курганов В.Д,, Злобин В.К. Распознавание и цифровая обработка изображении. М., Высшая школаД983, 295 с.

2. Арнхейм Р. Искусство и зрительное восприятие. Пер. с англ. М., Прогресс,19.71, 402с.

3. Бахман П. и др. Программные системы. Применение, разработка, обоснование. М., Мир, 1988, стр. 211 216.

4. Башков Е.А., Казак А.Б. Генераторы изображений для авиатренажеров. // Зарубежная радиоэлектроника, №8,1984, с. 60-68.

5. Баяковский Ю.М., Галактионов В.А., Кудин Б.В. Графический стандарты (обзор). Препринт., М., ИПМ АН СССР, 1984.

6. Бурков В.Н., Рубинштейн М.И. Комбинаторное программирование. М., Знание, 1977.

7. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных комбинаторных задач: Обзор. Тех. кибернетика № 4 , 1968, стр. 115 -127.

8. Бутаков В.А., Островский В.И., Фадеев И.Д. Обработка изображений на ЭВМ. М., Радио и связь, 1987.

9. Воробьева Г.И. Рандомизированный поиск локально-оптимальных стратегий построения кортежей изображений с помощью ЭВМ. //Межвузовский сборник научных трудов «Высокие технологии в технике, медицине и образовании» Воронеж.,1999 г., с.58-68.

10. Ю.Воробьева Г.И. САПР оптимальных стратегий генерации независимых изображений. //Сборник научных трудов «Научная сессия МИФИ» том 7. Москва, 1999 г., с.84-85.

11. П.Воробьева Г.И. Эффективная стратегия генерации одного класса взаимосвязанных изображений с помощью ЭВМ.// Труды СевероКавказского государственного технологического университета. Выпуск 6.Владикавказ.,1999г., CJ253-258.

12. Воробьева Г.И., Клебанова И.В. Регулярные методы поиска оптимальной стратегии обработки кортежей изображений при решении задач нефтегазовой промышленности.// Нефтегазовые технологии, 1999 г., №3 с.32-35., №4 с.17-21.

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

14. Гасов В.М, Коротаев А.И., Сенькин С.И. Отображение информации. Серия: Организация взаимодействия человека с техническими средствами АСУ. Книга 4. М., Высшая школа. 1990 г.

15. Гилой В. Интерактивная машинная графика: структуры данных, алгоритмы, языки. Пер. с англ., М., мир, 1981.

16. Гранант Д. Д. Роль моделей зрения человека в обработке изображений. // ТИИЭР, №5, 1981, с. 65-77.

17. Дученко H.H., Тимошенко Н.П. о принципах силуэтного метода синтеза изображений. // Электронное моделирование, № 4, т. 6, 1984, с. 45-49.

18. Завьялов Ю.С., Квасов Б.И., Мирошниченко B.JI. Методы сплайнфункций. М., 1980. 23.Зыков A.A. Теория конечных графов. Том 1, Новосибирск, Наука, 1969.

19. Иванов В.П., Батраков A.C. Трехмерная компьютерная графика. М., Радио и связь. 1995.

20. Иванов В.П., Компьютерный синтез изображений в задаче видеораспознавания образцов. // Тезисы докладов Всесоюзн. конф. "Оптическое изображение и регистрирующие среды", 4.2., JI., 1990, с. 127,128.

21. Иванов В.П., Батраков A.C. Синтез изображений объектов сложной формы методом трассирования лучей. // Программирование, № 2, 1989, с. 70-75.

22. Иванов В.П., Сечко A.M., Желанов С.А. Полутоновое иллюстрирование трехмерных функций с помощью ЭВМ. // Программирование, № 1,1987, с. 51-55.

23. Касьянов В.Н. Оптимизирующие преобразования программ. М. : Наука,1988, 336 с.

24. Кунт М., Джонсен О. Блочное кодирование графических материалов. ТИИЭР, т.6, №7, 1980, с.21-39.125

25. Марков Н.Г., Ковин P.B., Ананьина В.П., Гаряев Р.И., Захаров А.А., Савицкий Р.В. Геоинформационная система для решения задач гидрогеологии. // Информационные технологии, № 4. 1997, стр. 29-33.

26. Машинная графика и ее приложения. Сб.науч.тр. АН СССР. / Под ред. Мацокина A.M., Новосибирск, АН СССР и СО АН, 1983,137 с.

27. Тезисы докладов V Всесоюзной конференции по проблемам машинной графики "Машинная графика'89". Новосибирск, АН СССР и СО АН, 1989,176 с.

28. Методы передачи изображений. Сокращение избыточности. // Прэтт У.К., Сакрисон Д.Д., Мусман Х.Г.Д. и др. Под ред. Претта У.К. Пер. с англ., М., Радио и связь, 1963,

29. Ньюмен У., Спрулл Р. Основы интерактивной машинной графики. М., Мир, 1976.35.0чин Е.Ф. Вычислительные системы обработки изображений. М., Энергоатомиздат, 1989,133 с.

30. Павлидис Т. алгоритмы машинной графики. Пер. с англ., М., Радио и связь, 1986.

31. Прэтт У. Цифровая обработка изображений. Пер. с англ., М., Мир, 1982 Кн.1 -310 с., Кн.2-473 с,

32. Раушенбах Б.В. системы перспективы в изобразительном искусстве. М., Наука, 1986.

33. Роджерс Д., Адаме Дж. Математические основы машинной графики. Пер. с англ., М., Машиностроение, 1980, 240 с.

34. Роджерс Д. Алгоритмические основы машинной графики. Пер. с англ., М., Мир, 1989, 504 с,

35. Стронгин Р.Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы). М., Наука, 1978.

36. Тиори Т., Фрай Дж. Проектирование структур баз данных. В 2-х кн. Пер. с англ., М., мир, 1985,

37. Уайлд Д. Дж. Методы поиска экстремума. М.,"Наука", 1967.

38. П. Г. Уилсон. Искусственный интеллект», М.: Мир, 1980г, 171 с.

39. Фоли Дж., А. вен Дэм. Основы интерактивной машинной графики. М., Мир, 1985.

40. Фрир Дж. Построение вычислительных систем на базе перспективных микропроцессоров. Пер. с англ., М., Мир, 1990, 414 с.

41. Черчмен У., Акоф Р., Арноф JI. Введение в исследование операций, М., Наука, 1968.

42. Четвериков В.Н., Ревнуков Г.И., Самохвалов Э.Н. Базы и банки данных. М., Высшая школа, 1987.

43. Чэн Ш.-К. Принципы проектирования систем визуальной информации. М., Мир, 1994.

44. Эндерле Г., Энеи К., Пфафф Г. Программные средства машинной графики. Международный стандарт GKS. М., Радио и связь, 1988.126

45. Advances in computer graphics / Ed. By G.Enderie, M.Grave, F.Lillehagen. Berlin, Sringer-Verlag. 512 p.

46. Advances in computer graphics. Proc. of Computer Graphics Tokyo'86 / Ed. by T.L.Kunii, Tokyo, Springer, 1986, 504 p.

47. Bishop A. Computer simulation of the real world for the mechanical and industrial designer // computer Graphics'83/ Proc. of the Intern. Conf. (London, 83). Pinner: Online publ., 1983, XIV, 776 p.

48. Blinn J.F. A scan-line algorithm for computer display of parametrically defined surfaces II Computer Grathics. 1978, Vol.12, p. 345.

49. Blinn J., Newell M. Texture and reflection in computer generated images I I Communication of ACM. 1976, Vol. 19, № 10, p.542-547.

50. Bouville C., Brusq R. Generating high quality by ray-tracing // Computer Graphics forum, 1985, Vol.4, № 2, p. 567-579.

51. Braid I.C. Geometric modelling // Advances in Computer Graphics. Berlin, Springer-Verlag, 1981, p. 425-362.

52. Catmull E. Computer display of curved surfaces // Proc. IEEE. Conf. on Computer Graphics Pattern Recognition and Data Structure (N.Y., May 1975). New York, 1975, p. 456-459.

53. Computational geometry / Ed. by G.Toussaint. Amsterdam, North Holland, 1985,459 p.

54. Computer Graphics'81. Proc. of the Mem. Conf. Northwood (UK), Online publ., 1981, 545 p.

55. Computer Graphics'82. Proc. of the Intern. Conf. Northwood (UK), Online publ., 1982, XVIII, 392 p.

56. Computer Graphics'83. Proc. of the Intern. Conf. (Iondon'83), Pinner, Online publ., 1983, XIV, 776 p.

57. Computer Graphics 1887. Proc. of CG Intern. Conf 87 / Ed. by T.L.Kunii. tokyo, Springer, 1987, IX, 490 p.

58. McGregor J., Watt A. The art of graphics for the IBM PC. Workingham, Addison-Wesley, 1986, X, 454 p.

59. New advances in computer graphics. Proc. of CG International'89 / Ed. by R.A.Earnshaw, B.Wyvill, new York, Springer, 1989, X, 718 p.

60. Kamaran Parsaye, Mark Chignell, Setrag Kashafian, Harry Wong. Intelligent Databases. John Wiley & Sons, Inc., New York, 1989.

61. Rogers D.F., Earnshow R.A. Techniques for computer graphics. Berlin, Springer-Verlag, 1987, 512 p.

62. Selem G. Aki. Optimal parallel algorithms for selection, sorting and computing convex hulls // Computational Geometry / Ed. by G.Toussaint. Amsterdam, North Holland, 1985, 567 p.

63. Theoretical foundations of computer graphics and CAD / Ed. by R.A.Earnshaw. New York, Springer-Verlag, 1988,1242 p.

64. Указанные шкеты использовались при создании следующих учебных курсов:1. обучающие мультимедиа-системы по машиностроительным изделиям «Термит», «Болид», «Втулка»;2. программное обеспечение САПР «Обстановка»;

65. Внедрение вышеназванных пакетов привело к экономии оперативной памяти на17%.1. Председатель комиссии1. ЕОчин1. Члены комиссии:1. В.Анисимов1. ААртанов

66. Программное обеспечение САПР.3. Компьютерная графика.

67. Институт дискретной математики и информатики (ИДМИ) принял от Воробьевой Г.И. пакеты программ indepim 1 и Indepim 2, предназначенные для поиска оптимальных стратегий формирования независимых изображений.