Метод автоматизированного конструирования процедур анализа изображений с использованием генетических алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Буряк, Дмитрий Юрьевич

• Буряк, Дмитрий Юрьевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Буряк, Дмитрий Юрьевич

Введение.

1. Анализ основных подходов к построению процедур анализа изображений.

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

1.2. Подходы, основанные на использовании библиотек функций.

1.3. Алгоритмы вычисления оценок.

1.4. Методы автоматизированного конструирования отдельных элементов алгоритма распознавания.

1.5. Использование баз знаний.

1.6. Генетическое программирование.

1.7. Выводы.

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

2.1. Исходные данные.

2.2. Построение субоптимальной процедуры идентификации объектов одного класса.

2.3. Обоснование применения ГА для поиска оптимальных решений.

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

2.5. Построение субоптимальных процедур идентификации и обнаружения объектов нескольких классов.

2.6. Повышение устойчивости конструируемых процедур.

2.7. Инвариантность решающих процедур к сдвигу, повороту и масштабированию объекта на изображении.

2.8. Выводы.

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

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

3.2. Функционал оценки качества процедур идентификации и обнаружения объектов одного класса.

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

3.4. Выводы.

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

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

4.2. Базовые алгоритмы.

4.3. Алгоритм выполнения решающей процедуры.

4.4. Алгоритм оценки качества хромосомы.

4.5. Алгоритм формирования очередной популяции.

4.6. Алгоритм регенерации популяции.

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

4.8. Выводы.

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

Актуальность работы. Проблема разработки методов, позволяющих автоматизировать процессы выбора и настройки алгоритмического и программного обеспечения идентификации и обнаружения объектов на цифровых изображениях, является актуальной. Задачи идентификации и обнаружения объектов на цифровых изображениях возникают в самых различных областях науки и техники [1,3,6,18,23,29]. К настоящему времени разработано большое число методов, алгоритмов, моделей, которые позволяют решать различные задачи в этой области. Однако, проблема создания алгоритмов решения вновь возникающих задач идентификации и обнаружения является чрезвычайно трудоемкой, требующей наличия большого опыта в области анализа изображений.

Основное внимание в литературе при освещении вопросов создания процедур распознавания уделено применению специализированных библиотек функций [27,31,35,36,39,45,51], моделей алгоритмов вычисления оценок [7,8,9,10,12,13,19,20], методам, основанным на использовании моделей предметной области [33,43,44,47,54], а также теории генетического программирования [30,32,49,53]. Проведенный анализ показал, что существующие подходы к решению поставленной задачи обладают рядом недостатков, препятствующих их эффективному применению на практике. В работе предложен новый метод построения процедур идентификации и обнаружения объектов на цифровых изображениях, основанный на автоматическом выделение характерных локальных свойств объекта и применяющий теорию генетического программирования для конструирования на основе выделенных свойств решающих процедур, которые способны работать в реальном масштабе времени. Данный метод автоматически подстраивается под специфику каждой конкретной решаемой задачи и позволяет учитывать опыт, накопленный исследователями в области анализа изображений.

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

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

Задачи. Для достижения поставленной цели требуется:

• сформулировать принципы, которые позволили бы автоматизировать процесс конструирования процедур идентификации и обнаружения объектов на изображениях;

• разработать модели представления процедур идентификации и обнаружения объектов;

• разработать критерий оценки эффективности конструируемых решающих процедур;

• разработать метод отбора эффективных процедур идентификации и обнаружения;

• разработать программное обеспечение, реализующее данный метод;

• провести экспериментальное исследование эффективности предложенного метода.

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

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

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

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

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

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

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

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

• робототехника;

• системы контроля качества продукции на производстве.

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

• XI Международная научная конференция студентов и аспирантов по фундаментальным наукам "Ломоносов", Россия, Москва, 2002;

• 12-я Международная конференция по компьютерной графике ГРАФИКОН-2002, Россия, Нижний Новгород, 2002;

• 6-я Международная конференция "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ-6-2002), Россия, Великий Новгород, 2002;

• Ломоносовские чтения-2003, Россия, Москва, 2003;

• Всероссийская научно-техническая конференция "Методы и средства обработки информации" (МСО-2003), Россия, Москва, 2003;

• Семинар по обработке экспериментальных данных при помощи нейронных сетей и генетических алгоритмов под руководством Королева JI.H. и Поповой Н.Н. (факультет ВмиК МГУ).

• Научно-исследовательский семинар по автоматизации программирования под руководством Шура-Бура М.Р.

Публикации. Основные результаты работы изложены в 8-и научных публикациях [57-64].

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 126 страницах. Список литературы включает 64 наименования. В работе содержится 42 рисунка и 5 таблиц.

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

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

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

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

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

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

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Буряк, Дмитрий Юрьевич, 2004 год

1. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.:Наука, 1974. - 416с.

2. Вендров A.M. Проектирование программного обеспечения экономических информационных систем. М.: Финансы и статистика 2000.

3. Верхаген К., Дейн Р., Грун Ф., Йостен Й., Вербек П. Распознавание образов: состояние и перспективы. М.:Радио и связь, 1985. - 104с.

4. Гилл Ф., Мюррей У. Численные методы условной оптимизации. М.: Мир, 1977.

5. Гирсанов И.В. Математическая теория экстремальных задач. М.: Изд-во МГУ, 1970.

6. Горелик A.JL, Скрипкин В.А. Методы распознавания. М.:Высшая школа, 1984. - 208с.

7. Гуревич И.Б. Проблема распознавания изображений // Распознавание, классификация, прогноз. Москва: изд-во "Наука", - 1989. - выпуск 1, - с. 280329.

8. Докторович А.Б. Задача выбора оптимального алгоритма распознавания в одном классе алгоритмов голосования // Кибернетика. Киев, 1974. - № 4.

9. И. Енч В. Алгоритм оптимизации параметров одного класса распознающих алгоритмов // Труды Международного симпозиума по практическому применению методов распознавания образов, ВЦ АН СССР, -1973.- с. 237-245.

10. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. - № 3, - с. 1-11.

11. Журавлев Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение. Ташкент: изд-во "Фан", 1974.

12. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики, 1978. вып. 33, -с. 5-68.

13. Журавлев Ю.И. Алгоритмы распознавания, основанные на вычислении оценок. Содержательный смысл параметров, задающих алгоритм // Труды Международного симпозиума по практическому применению методов распознавания образов, ВЦ АН СССР, 1973.

14. Журавлев Ю.И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации // ДАН СССР, 1976. - т. 231,- № 3,-с. 532-535.

15. Журавлев Ю.И., Михалевич М. Алгоритмы распознавания, основанные на вычислении оценок для задач с пересекающимися классами // Труды ВЦ Польской АН. Варшава, 1974. - вып. 145.

16. Иванов В.А., Косых В.П. Алгоритм сравнения фрагментов изображений двух кристаллов для контроля внешнего вида микросхем // Автометрия. 1989. -№2. - С.29-34.

17. Ищук В.И. О поиске оптимальных весовых коэффициентов для одного класса алгоритмов вычисления оценок // Сборник работ по математической кибернетике, ВЦ АН СССР . 1976. - вып.1, - с. 186-194.

18. Камилов М.М. Об оптимизации и некоторых применениях алгоритмов вычисления оценок // Труды Международного симпозиума по практическому применению методов распознавания образов, ВЦ АН СССР. -1973.

19. Камилов М.М., Алиев Э.М. Выбор длины голосующих наборов в алгоритмах вычисления оценок // Вопросы кибернетики. Ташкент, 1971,- вып. 44.

20. Камилов М.М., Алиев Э.М., Ким А.Н. О вычислении s-порогов при распознавании объектов алгоритмами голосования // Вопросы кибернетики. -Ташкент, 1971. вып. 43.

21. Киричук Н.А., Косых В.П., Петунин А.И. Автоматическая классификация лейкоцитов человека с использованием комплекса "Зенит-К" // Автометрия. -№2. С.38-42

22. Красильников Н.Н. Теория передачи и восприятия изображений. М.: Радио и связь, 1986.

23. Кульянов Е.Г. Об оптимизации одного класса алгоритмов распознавания // Журнал вычислительной математики и математической физики. 1974. - т. 14, - № 3, - с. 756-767.

24. Лоран П.Ж. Аппроксимация и оптимизация. М.: Мир, 1975.

25. Орлов В. Концепция визуального программирования в IBM VisualAge Smalltalk. Материалы конференции "Индустрия программирования '96м.

26. Рязанов В.В. Оптимизация алгоритмов вычисления оценок по параметрам, характеризующим представительность эталонных строк // Журнал вычислительной математики и математической физики. 1976. - т. 16, - № 6.

27. Хорн Б.К.П. Зрение роботов. М.:Мир. - 1989. - 487с.

28. Discipulus. Owner's Manual. Register Machine Learning Technologies, Inc. 2000.

29. Open Source Computer Vision Library. Reference Manual. Intel Corporation, 2001.

30. Banzhaf W., Nordin P., Keller R.E., Francone F.D. Genetic Programming an Introduction: On the Automatic Evolution of Computer Programs and Its Applications. Dpunkt.verlag and Morgan Kaufmann Publishers, Inc. USA. 1998.

31. Buckner, J., Pahl, M., Stahlhut, O., Liedtke, C.-E. A Knowledge-Based System for Context Dependent Evaluation of Remote Sensing Data. // Lecture Notes in Computer Science. Springer-Verlag Heidelberg, 2002. Vol. 2449. - pp. 58-65.

32. Burnett, M. M. and Baker, M. J. A classification system for visual programming languages. J. Visual Languages and Computing, pp. 287-300, September 1994.

33. Chang, S. Visual languages: A tutorial and survey. IEEE Software, 4(l):29-39, January 1987.

34. J.H. Cornell and M. Brady. Generating and generalizing models of visual objects. Artificial Intell., 31: 159-183,1987.

35. Davies. Finding ellipses using the generalized Hough transform. Patterns Recognition Letters 9 (1989) 87-96.

36. Nikos Drakos. Visual Programming Languages: A Survey. CS 263 Final Project. Computer Based Learning Unit, University of Leeds. 1996.

37. Holland, J. Adaptation of natural and artificial systems. MIT Press, Cambridge, MA, 1975.

38. D.P. Huttenlocher and S. Ullman. Recognizing solid objects by alignment with an image. Int. J. Comput. Vision, 5(2): 195-212, Nov. 1990.

39. Rrechel D., Hess F., Comes R., Wangenheim A.V., Blasinger K. Mammalyzer II: A Decision Support System for Early Detection of Breast Cancer in Contrast Enhanced MRI. Springer Informatik Aktuell. Aachen, 1998.

40. Liedtke, C.--E., Buckner, J., Grau O., Growe S., Tonjes, R., "AIDA: A System for the Knowledge Based Interpretation of Remote Sensing Data", 3rd Int. Airborne Remote Sensing Conference & Exhibition, Copenhagen, Denmark,, Vol II, pp. 313-320, July 1997.

41. Fadia Markar. State of the art in visual programming languages. Universite de Geneve. Groupe Programmation Visuelle et Genie Logiciel Memoire de licence. 1997.

42. B.A. McArthur. Incremental Sythesis of Three-Dimensional Object Models Using Random Graphs. PhD thesis, Univ. of Waterloo, 1991.

43. Petrie Ch. Context maintenance. In Proceedings of AAAI-91. 1991. pp 288295.

44. A.R. Pope and D.G. Lowe. Learning object recognition models from images. In Proc. 4. Int. Conf. on Computer Vision, pages 296-301, Berlin, May 1993. IEEE Press.

45. Samuel A. Some studies in machine learning using the game of checkers. In Feigenbaum, E. and Feldman, J., editors, Computers and Thought. McGraw-Hill, New York. 1963.

46. J. Segen. Model learning and recognition of non-rigid objects. In Proc. Conf. Comput. Vision andPatt. Recognit., pp. 597-602,1989.

47. Shu, N. C. Visual Programming Languages: A Perspective and a Dimensional Analysis, pp. 11-34. Plenum Press, 1986.

48. Straub, B.-M., J., Gerke, M., Pahl, M. Automatic Mapping of Settlement Areas Using a Knowledge-Based Image Interpretation System. // Lecture Notes in Computer Science. Springer-Verlag Heidelberg, 2003. Vol. 2626. - pp. 355-364.

49. Teller A., Veloso M. PADO: Learning tree structured algorithms for orchestration into an object recognition system. Technical Report CMU-CS-95-101, Department of Computer Science. Carnegie Mellon University, Pittsburgh, PA.

50. J.J. Weng, N. Ahuja, and T.S. Huang. Learning recognition and segmentation of 3D objects from 2D images. In Proc. Int. Conf. Comput. Vision, pp. 121-128, 1993.

51. A.K.C. Wong and M. You. Entropy and distance of random graphs with application of structural pattern recognition. IEEE Trans. Patt. Anal. Mach. Intell., 7(5):599-609, Sept. 1985.

52. D. Yu. Buryak and Yu. V. Vizil'ter. Application of genetic algorithms for automated construction of image analysis procedures. Pattern Recognition and Image Analysis, Vol. 13, No. 1,2003, pp. 77-79.

53. D.Yu. Buryak and Yu.V. Vizil'ter. Automated construction of identification procedures for objects belonging to several classes. Programming and Computer Software. Vol. 29, No. 4, 2003, pp. 238-243.

54. D.Yu. Buryak and Yu.V. Vizil'ter. The use of genetic algorithms for the automated construction of the image analysis procedures. Pattern Recognition and Image Analysis, Vol. 13, No. 3, 2003, pp. 483-488.