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

• Кирнос, Эдуард Анатольевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Кирнос, Эдуард Анатольевич

Содержание

Введение

1 Морфологический анализ изображений

1.1 Морфологический анализ монохромных изображений.

1.2 Морфологический анализ изображений ламбертовых объектов.

1.2.1 Понятие ламбертовости объекта.

1.2.2 Эффективная размерность множества точных данных.

1.2 3 Эффективная размерность множества измеренных с ошибками сигналов

2. Логические решающие функции

2.1 Основные понятия.

2.1.1. Разнотипность характеристик (переменных) ф 2.1.2 Решающая функция и стратегия природы.

2.1.3 Байесовская решающая функция.

2.1.4 Таблица данных (обучающая выборка).

2.1.5 Элементарные высказывания и наборы высказываний.

2 2 Алгоритм "CORAL"

2.3 Алгоритм "TEMP"

2.4 Алгоритм "R-метод"

2 5 Алгоритм обучения и распознавания типа "Кора"

2 5.1 Постановка задачи.

2.5.2 Описание алгоритма.

3. Анализ результатов

3 1 Метод морфологического анализа монохромных изображений

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

3.3 Параметрические алгоритмы распознавания.

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

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

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

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

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

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

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

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

Параметрические алгоритмы хорошо зарекомендовали себя, в частности, в задачах медицинской диагностики, где необходимо на основе измерений некоторых косвенных характеристик (например, артериального давления, ЭКГ и т.д.) предсказать заболевание, поскольку прямое измерение некоторых характеристик (например, характеристик, которые могут быть получены только при хирургической операции) связано со значительным риском. Все параметрические алгоритмы основаны на анализе эмпирической информации, представленной в виде таблиц данных. Параметрические алгоритмы производят построение устойчивых представительных наборов для каждого класса объектов таблицы данных. Каждый объект таких таблиц данных характеризуется значениями признаков где п — количество признаков. Для булевых признаков наиболее известным алгоритмом распознавания является алгоритм "Кора"[79-80,87,94], предназначенный для определения логических закономерностей в виде конъюнкций значений признаков и метод "тупиковых тестов" [89,90,97,98]. Решающее правило в обоих случах задается в виде алгоритмической процедуры: для распознавания объекта используется голосование либо по конъюнкциям, либо по "тупиковым тестам".

Для разнотипных признаков известны такие алгоритмы распознавания, как "TEMP", "R-метод", "CORAL" — эти алгоритмы основаны на построении представительных наборов в виде так называемых деревьев решений [16,17,30-33].

Цель диссертационной работы состоит:

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

2. В изучении влияния состава обучающей выборки на качество распознавания объектов в шуме параметрическими алгоритмами и морфологическими алгоритмами;

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

4. В сравнительном анализе качества распознавания параметрических алгоритмов и морфологических алгоритмов.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Кирнос, Эдуард Анатольевич

Заключение

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

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

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

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

4. Проведен сравнительный анализ качества распознавания всех вышеуказанных параметрических и морфологических алгоритмов на примере задачи распознавания искаженных шумом изображений. Показано, что: a) Алгоритм типа "Кора" дает наилучшие результаты при распознавании данных в шуме в классе всех рассмотренных параметрических алгоритмов; b) Качество распознавания алгоритма ламбертовой морфологии лучше при распознавании изображений ламбертовых объектов в классе рассмотренных морфологических алгоритмов; c) При распознавании изображений качество распознавания морфологических алгоритмов заметно лучше по сравнению с качеством распознавания рассмотренных параметрических алгоритмов;

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

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

Все результаты были получены с использованием средств разработки Matlab 6.0, Visual С++ 6.0, Borland С++ Builder 5.0, Assembler for Motorola64K.

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

1. Пытпъев Ю.П. Морфологический анализ изображений. // Кибернетика и теория регулирования, М., Докл. АН СССР, 1983, т. 269, №5, с. 1061-1065.

2. Пытпъев Ю.П. Морфологический анализ изображений. // Докл. АН СССР, 1983, т. 196, №5, с. 1062-1064.

3. Yu.P.Pyt'ev Morphological Image Analyssis j j Pattern Recognition And Image Analysis, 1993, vol. 3, no. 61, pp. 19-28.

4. Пытъев Ю.П., Чуличков А.И. ЭВМ анализирует форму изображения. // Знание, сер Математика, Кибернетика. Москва, 1988.

5. Пытъев Ю.П. Морфологические понятия в задачах анализа изображений. // Докл. АН СССР, 1975, т. 224, с. 1283-1286.

6. Пытъев Ю.П., Задорожный С.С., Лукьянов А.Е. Об автоматизации сравнительного морфологического анализа электронно-микроскопических изображений. // Изв. АН СССР, сер. Физическая, т. 4, 111 е., 1977.

7. YuP.Pyt'ev, A Yu.Pyt'ev Effective Dimentionality and Data Compression. // Pattern Recognition And Image Analysis, 1997, vol. 7, no 4, pp. 393-406.

8. Вондаренко С.П., Пытъев Ю.П. Об эффективном ранге модели линейных измерений с ошибкой. // ЖВМ и МФ, 1995, т. 35, №1, с. 7-23.

9. Пытъев Ю.П., Вондаренко С.П., Поляков Д.В. О фактической размерности измерений, выполненных на линейном приборе с ошибкой. // Вестн. Моск. Унта, сер.З, Физика, Астрономия, 1995, т. 36, JV°4, с. 22-28.

10. Gilland D.S., Lund J.R., Vogel C.R. Quantifying information content for ill-posed problems. // Inverse Problems, 1990, no. 6, pp. 725-736.

11. Пытъев Ю.П. К теории нелинейных измерительно-вычислительных систем. // Математическое Моделирование, 1992, т. 4, N°2, с. 76-94.

12. Пытъев Ю.П. Математические методы интерпретации эксперимента. // М.: Высшая Школа, 1989, 351 с.

13. Андерсон Т. Введение в многомерный статистический анализ. // Пер. с англ. М.:Физматгиз, 1963.

14. Лбов Г.С., Старцева Н.Г. Сложность распределений в задачах классификации. // Докл. РАН. 1994. т. 338, №5, с. 592-594.

15. Лбов Г.С., Старцева Н.Г. Логические решающие функции и вопросы статистической устойчивости решений. / / Новосибирск: Изд-во Ин-та математики, 1999, 211с.

16. Лбов Г. С. Методы обработки разнотипных экспериментальных данных. // Новосибирск: Наука, 1981.

17. Лбов Г.С., Котюков В.И., Машаров Ю.П. Метод обнаружения логических закономерностей на имперических таблицах. // Вычислительные системы, 1976, вып. 67, с. 29-42.

18. Lbov G.S., Berikov V.B. Recursive method of formation of the recognition decision rule in the class of logical functions. // Pattern Recognition and Image Analysis. 1993, vol. 3, no. 4, pp. 428-431.

19. Лбов Г. С., Котюков В.И., Манохин А.Н. Об одном алгоритме распознавания в пространстве разнотипных признаков. // Вычислительные системы, 1973, вып. 55, с. 98-107.

20. Лбов Г. С., Манохин А.Н. Распознавание образов при разнотипных признаках в условиях малой выборки. //В кн.: Статические проблемы управления. Вильнюс, 1976, вып. 14, с. 57-63.

21. Лбов Г. С. Логические функции в задачах эмпирического предсказывания. // Вычислительные системы, 1978, вып. 76, с. 34-64.

22. Лбов Г.С., Манохин А.Н. Логические и линейно-логические функции оценивания // Тез.докл. Новосибирск, 1978, с. 58-69.

23. Лбов Г. С. Об одном непараметрическом подходе в задачах эмпирического предсказания //В кн.: адаптивные системы и их приложения. Новосибирск, 1978, с. 78-81.

24. Хант Э. Искусственный интеллект // М., Мир, 1978, 560 с.

25. Кендал М., Стюарт А. Статистические выводы и связи // М., Наука, 1973, 899 с.

26. Ковалевский В.А. Методы оптимальных решений и распознавания изображений // М., Наука, 1976, 328 с.

27. Гладун В. П. Эвристический поиск в сложных средах // Киев, Наукова думка, 1977, 166 с.

28. Миркин Б.Г. Анализ качественных признаков // М., Статистика, 1976, 250 с.

29. Starceva N.G. Convergence of mathematical expectation of error probability for averaged startegy // Pattern Recognition and Image Analysis. 1994, vol. 4, no.2, pp. 110-115.

30. Starceva N.G. Influance of volume of sample and complexity distribution on quality of classification // Pattern Recognition and Image Analysis. 1992, vol. 2, no. 3, pp. 265-270.

31. Старцева Н.Г. О статистической устойчивости в задачах классификации // Докл. РАН. 1992. Т.323, №5, с. 441-444.

32. Старцева Н.Г. Сходимость математического ожидания вероятности ошибки к усредненной стратегии // Докл. РАН. 1995. Т.341, JV°5, с. 235-240.

33. Раудис Ш. Ограниченность выборки в задачах классификации // Статистические проблемы узнавания. Вильнюс, 1976. Вып. 18, с. 1-185.

34. Старцева Н.Г. Влияние сложности распределений на качество классификации для независимых переменных // Докл. РАН. 1997. Т.355, №4, с. 461-463

35. Starceva N.G. The average loss in classification problems with a limited sample size // Pattern Recognition and Image Analysis. 1997, vol. 8, no. 1, pp. 8-13.

36. Стронгин Р.Г. Численные методы в многоэкстремальных задачах // М., Наука, 1978.

37. Жилинскас А.Г. Поиск оптимума // М., Наука, 1989.

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

39. Кейслер Г., Чен Ч. Теория моделей // М., Мир, 1977.

40. Lbov G.S. Logical decision rules for automatic discovery of knowlege in expert systems database. // Internat. J.Pattern Recognition and Artificial Intelligence. 1989, vol. 3, no. 1, pp. 135-145.

41. Lbov G.S. Recognition of states of a dynamic object. // Pattern Recognition and Image Analysis. 1993, vol. 3, no. 2, pp. 185-187.

42. Lbov G.S., Starceva N.G., Berikov V.B. LASTAN a system for logical analysis of statical observation. // Pattern Recognition and Image Analysis. 1992, vol. 2, no. 1, pp. 56-61.

43. Лбов Г.С., Старцева Н.Г. Об одном понятии сложности стратегии природы в распознавании образов // Анализ данных в экспериментальных системах. Новосибирск, 1986, Вып. 117: Вычислительные системы, с. 91-102.

44. Лбов Г. С. Метод анализа многомерных разнотипных временных рядов в классе логических решающих функций // Докл. РАН. 1994. Т.339, JV°6, с. 750753.

45. Блощицын В.Я. О мерах информативности логических высказываний // Докл. "Технология разработки экспертных систем". Кишинев, 1987, с. 12-14.

46. Боровков А.А. О задаче распознавания образов // Теория вероятностей и ее применение. 1971, Т.16, N>1, с. 132-136.

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

48. Ларичев О.И., Мечитов А.И., Мошкович Е.М., Фурмес Е.М. Выявление экспертных знаний // М., Наука, 1989.

49. Викентъев А.А., Лбов Г.С. О метризациях булевой алгебры предложений и информативности высказываний экспертов // Докл. РАН. 1998. Т.361, №2, с. 174-176

50. Vikent'iev A.A., Lbov G.S. Setting the metric and informativeness on statement of experts. // Pattern Recognition and Image Analysis. 1997, vol. 7, no. 2, pp. 175-183.

51. Гладун В.П. Планирование решений // Киев, Наукова думка, 1987.

52. Домбровская Т.В., Черкашин Н.Т. Некоторые непараметрические алгоритмы распознавания образов большой размерности // Мат. статистика и ее приложение. Томск, 1980, JV»6, с. 118-124.

53. Донской В.И, Вашта А.И. Дискретные модели принятия решений при неполной информации // Семфирополь: Таврия, 1992.

54. Лбов Г. С., Неделъко В.М. Байесовский подход к решению задачи прогнозирования на основе информации экспертов и таблицы данных. // Докл. РАН. 1997. Т.357, JV«1, с. 29-32.

55. Манохин А.Н. Об одном подходе к прогнозироавнию перспективных объектов. // Вычислительные системы. Новосибирск, 1978, Вып. 74, с. 108-128.

56. Миркин Б.Г. Проблема группового выбора // М., Наука, 1974.

57. Michalski R.S. Variable-valued logic. // Proc. Symp. Multiple Volued Logic. Mor-gentown, 1974.

58. Michalski R., Bratko I., Kubat M. Machine Learning and Data Mining, Methods and Applications. // N.Y.: John Wiley & Sons, 1998.

59. Ojelanki K., Ngwenyama L., Bryson N. A formal method for analysing and in-tegrationing the rule-sets of multiple experts. // Inform. Systems. 1992, V.17, N 1, pp. 1-16.

60. Сухарев А.Г. Оптимальный поиск экстремума. // М.: Издательство МГУ, 1975.

61. Цыпкин Я.З. Адаптация и обучение в автоматических системах. // М., Наука, 1968.

62. Кендэл М. Временные ряды. // М., Финансы и статистика, 1981.

63. Hughes G. On the mean accuracy of statistical pattern recognizers. // JEEE Trans. Inform. Theory, 1968, IT-14, pp. 55-63.

64. Пикялис B.C. Сравнение методов вычисления ожидаемой ошибки классификации. // Автоматика и телемеханика, 1976, JV°5, с 59-63.

65. Okamoto М. An asymptotic expansion for the distribution of the linear discriminant function, j j Ann.Math. Stat., 1999, vol. 2, N 4, pp. 1286-1301.

66. Поляк JI.X. Аксиоматический подход к распознаванию динамических образов. // В кн.: Математическое моделирование в социологии: методы и задачи. Новосибирск, Ин-т экономики и организации промышленного производства СО АН СССР, 1977, с.139-164.

67. Трунов А.А. Алгоритм постоения кусочно-линейных логических решающих правил распознавания. // Материалы XXI обл. науч.-техн. конф., Новосибирск, НТО радиотехники им. А.С.Попова, 1978, с.43.

68. Журавлев Ю.И., Исаев И.В. Построение алгоритмов распознавания, корректных для данной выборки. // ЖВМ и МФ, 1979, Том 19, JV°3, с. 728-738.

69. Кочетков Д В. Распознающие алгоритмы, инвариантные относительно преобразований пространства признаков. // Распознавание, классификация, прогноз: Мат. методы и их применение. М.: Наука. 1988. Вып. 1. С. 82-113.

70. Кочетков Д.В. Распознающие алгоритмы, инвариантные относительно преобразований пространства признаков. // Распознавание, классификация, прогноз: Мат. методы и их применение. М.: Наука. 1989. Вып. 11. С. 178-206.

71. SenYho О. V. A Prediction Algorithm Based on the Procedure of Weighted Voting Using a System of Hyperparallelepipeds in a Multidimensional Feature Space. // Pattern Recognition and Image Analysis, 1993, vol.3, no. 3, pp.283-284.

72. Ganster E., Gelautz M., Pmz A., Binder M., Pehamberger H., Bammer M., Krocza J. Initial Results of Automated Melanoma Recognition. // Proceedings of the 9th Scandinavian Conference on Image Analysis, Uppsala, Sweden, June 1995, Vol.1, pp. 209-218.

73. Bezdek J.G. Pattern Recognition with Fuzzy Objective Function Algorithms. // Plenum Press, New-York, 1981.

74. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений. // Сб. "Дискретный анализ". Вып. 7. Новосибирск, ИМ СО АН СССР. 1966. С. 3-11.

75. Рудаков К. В. Об алгебраической теории универсальных и локальных ограничений для задач классификации. // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. М.: Наука, 1989. с. 176-200.

76. Сироджа И.Б Структурно-аналитический метод машинного распознавания объектов с разнотипными признаками. // Теория R-функций и актуальные проблемы прикладной математики. Киев: Наукова думка. 1986. С.212-243.

77. Bezdek J.С. A review of probabilistic, fuzzy, and neural models for pattern recognition. // FUZZY LOGIC AND NEURAL NETWORK HANDBOOK, Chen C.H. eds, ch.2, McGraw-Hill, 1996.

78. Бонгард M.M. Проблема узнавания. // M., Наука. 1967, 320с.

79. Вайнцвайг М.Н. Алгоритм обучения распознаванию образов "Кора". // В кн.: Алгоритмы обучения распознаванию образов. М., 1973, с. 110-115.

80. Журавлев Ю.И., Дмитриев А.Н., Кренделев Ф.П. О математических принципах классификации предметов и явлений. // Дискретный анализ, 1966, вып. 7, с. 3-15

81. Хант Э., Марин Док., Стоун Ф. Моделирования процесса формирования понятий на вычислительной машине. // М., Мир, 1970.

82. Горелик А.А., Скрипник В.А. Методы распознавания. // М., Высшая школа, 1977, 222с.

83. Голендер В.Е., Розенблит А.Б. Алгоритм выявления экспериментальных закономерностей и восстановление функциональной зависимости. / / Распознавание образов, 1974, с. 208-226.

84. Гаврилко В.П., Загоруйко П. Г. Универсальный алгоритм эмпирического предсказывания. // Вычислительные системы, 1975, вып. 55, с. 134-138.

85. Загоруйко П.Г. Эмпирическое предсказывание. // Новосибирск, Наука, 1979, 120 с.

86. Дюкова Е.В. Об одной параметрической модели алгоритмов распознавания типа "Кора". // М.: ВЦ АН СССР, сер. Сообщения по пркладной математике.

87. Дюкова Е.В. О сложности реализации некоторых процедур распознавания. // Ж. Вычислительная математика и математическая физика, 1987, т. 21, JV°1, с. 144-227.

88. Дюкова Е.В. Об одном алгоритме построения тупиковых тестов. // Сборник работ по дискретной математике, М.: ВЦ АН СССР, 1976, JV°1, с. 167-185

89. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания. // Поблемы кибернетики, М.: Наука, 1982, JV°39, с. 165-199.

90. Е. A. Kirnos, Yu. P. Pyt'ev, E. V. Djukova Training the "Kora" Type Algorithms. // Pattern Recognition and Image Analysis. 2002, vol. 12, no. 1, pp. 19-24.

91. Кирнос Э.А., Пытпъев Ю.П. О параметрических алгоритмах распознавания // Вестник Московского Университета. Серия 3. Физика, Астрономия. 2003. JV°1, с. 16-18.

92. Е. A. Kirnos, Yu. P. Pyt'ev Training the algorithms based on logical decision functions. // Pattern Recognition and Image Analysis. 2004, vol. 14, no.3, pp. 394406.

93. Дюкова E. В. Алгоритмы распознавания типа YKopaY: сложность реализации и метрические свойства. // Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука, 1989. Вьтп.2. С. 99-125.

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

95. Баскакова Л.В., Журавлев Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств. // Журн. вьтчисл. матем. и матем. физики. 1981. Т.21, е 5. С.1264-1275.