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

ВВЕДЕНИЕ

ГЛАВА 1. Постановки задач.

ГЛАВА 2. Распознавание классов изображений, отличающихся мелким сдвигом.

2.1 Модель класса изображений, отличающихся мелким 23 сдвигом.

2.2 Цилиндрические решающие правила.

2.3 Цилиндрические решающие правила. Задача обучения. 26 Статистическая постановка.

2.4 Цилиндрические решающие правила. Задача обучения. 28 Минимаксный подход.

2.5 Экспериментальная верификация. Цилиндрические 29 решающие правила.

2.6 Эллипсоидные решающие правила.

2.7 Задача обучения. Эллипсоидные решающие правила. 34 Минимаксный подход.

2.8 Оценка параметров нормального закона при помощи 36 ' эллипсоида минимального объема.

2.9 Экспериментальная верификация. Эллипсоидные 39 решающие правила.

2.10 Построение цилиндрического решающего правила в 40 условиях конкуренции.

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

2.12 Определение границы при помощи цилиндрического 44 решающего правила.

2.13 Основные результаты и комментарии.

Глава 3. Измерения, использующие решетку, состоящую из эллипсов.

3.1 Особенности использования эллипсоидной решетки в 49 измерениях.

3.2 Основные предположения и основные элементы метода 51 распознавания эллипсоидной решетки.

3.3 Задача квантования изображения как задача определения 52 параметров смеси распределений. (Параметрический подход).

3.4 Обратная схема решения задачи квантования.

3.5 Непараметрические методы решения задачи квантования. 59 Критерий Ван Ризена.

3.6 Использование гистограммы распределения яркости 62 изображения для вычисления порога квантования.

3.7 Локализация и определение границ эллипсов.

3.8 Распознавание эллипсов.

3.9 Основные результаты и комментарии.

ГЛАВА 4. Распознавание изображений эллипсов и арок окружностей на основе линейных симметрий с приложением в импеданс-анализе свойств материалов и эллипсометрии.

4.1 Структура метода и основные предположения.

4.2 Методы выделения края изображения. Динамическое 81 программирование.

4.3 Методы выделения края изображения. Нелинейная 90 фильтрация.

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

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

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

В начале становления распознавания образов как науки В.А. Ковалевским было вьщелено два направления развития распознавания образов.

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

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

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

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

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

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

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

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

Диссертация состоит из четырех глав, введения и заключения. Основные результаты диссертации опубликованы в работах и доложены на конференциях с опубликованием тезисов [102- 110].

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

4.8 Основные результаты и комментарии.

К основным результатам главы относятся:

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

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

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

131 вычисления параметров кривой, что позволило сократить размерность пространства признаков; • Предлагаемые технологии обработки данных вошли в комплекс измерительных систем, предназначенных для импеданс -спектроскопии и эллипсометрии.

Заключение

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

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

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

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

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

1. Алберт А., Регрессия, псевдоинверсия и рекуррентное оценивание, М, Наука, 1977, 224 с.

2. Андерсон Т., Статистический анализ временных рядов, М, Мир, 1976, 1976,755 с.

3. Ахмед Н., Pao К., Ортогональные преобразования при обработке цифровых сигналов, М, Связь, 1980, 248 с.

4. Банвенист А., Обзор перспективных методов обнаружения изменений, там же, с 62-76.

5. Бассвиль М., Двумодельный подход для обнаружения изменений в АР -процессах в реальном масштабе времени, там же, с 131 158.

6. Бассвиль М., Обнаружение скачкообразных изменений среднего значения сигнала. Обобщение на аддитивные изменения в моделях пространства состояний, в сб. «Обнаружение изменения свойств сигналов и динамических систем», М, Мир, 1989, с 16-27.

7. Белман Р., Введение в теорию матриц, М, Наука, 1976, 351 с.

8. Белман Р., Заде Л., Принятие решений в расплывчатых условиях, Сб. Вопросы анализа и процедуры принятия решений, Мир,, 1976, с. 172215.

9. Белявский Г.И., Оптимальный пороговый фильтр для идентификации резких изменений сигнала, в сб. «Вопросы технической диагностики», Ростов на - Дону, 1980, с 72 - 76.

10. Белявский Г.И., О применении разложения Карунена Лоэва к построению эталонов для читающих автоматов, там же, с. 59 - 66.

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

12. Н.Белявский Г.И., Синтез оптимального линейного решающего правила для определения момента разладки, Всероссийская школа коллоквиум по стохастическим методам анализа и смежным вопросам, М, ТВП, 1995.

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

14. Ватанабе С., Разложение Карунена Лоэва и факторный анализ, в сб. «Автоматический анализ сложных изображений», М, Мир, 1969.

15. Вилски A.C., Обнаружение резких изменений в динамических системах, в сб. «Обнаружение изменения свойств сигналов и динамических систем, М, Мир, 1989, с. 29-43.

16. Даджион Д., Мерсеро Р., Цифровая обработка многомерных сигналов, М, Мир, 1988, 488 с.

17. Де Гроот М., Оптимальные статистические решения, М, Мир, 1974, 491 с.

18. Демьянов В.Ф., Малоземов В.Н., Введение в минимакс, М, Наука, 1972, с 368.

19. Дуда Р., Харт П., Распознавание образов и анализ сцен, М, Мир, 1976, 568 с.

20. Ермольев Ю.М., Методы стохастического программирования, М, Наука, 1976, 239 с.23.3агоруйко Н.Г., Методы распознавания и их применения, М, Советское радио, 1972, 206 с.

21. Заде Л.А., Понятие лингвистической переменной и его применение к принятию приближенных решений, М, Мир, 1976, 165 с.

22. Заде Л.А., Размытые множества и их применение в распознавании образов, в сб. «Классификация и кластер», М, Мир, 1980, с. 208 247.

23. Киселев Н.В., Методы построения систем распознавания и классификации негауссовских сигналов, Ленинградский университет, 1986, 186 с.

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

25. Кофман А., Введение в теорию нечетких множеств, М, Радио и связь, 1982,432 с.

26. Леман Э., Поверка статистических гипотез, М, Наука, 1979, 408 с.

27. Леман Э., Теория точечного оценивания, М, Наука, 1991, 448 с.

28. Марпл С., Цифровой спектральный анализ и его приложения, 1990, 584 с.

29. Мелихов А.Н., Берштейн Л.С., Конечные четкие и расплывчатые множества, Таганрог, ТРТИ, 1980, 191 с.

30. Минский М., Пейперт С., Персептроны, М, Мир, 1973, с. 75-81.

31. Розенфельд А., Распознавание и обработка изображений, М, Мир, 1972, 230 с.

32. Фу К., Структурные методы в распознавании образов, М,Мир,1977, 319 с.

33. Ширяев А.Н., Статистический последовательный анализ, М, Наука, 1969, 231с.

34. Шлезингер М.И., Взаимосвязь обучения и самообучения, в распознавании образов, Кибернетика, 2, 1968, с. 42 57.

35. Шлезингер М.И., Математические средства обработки изображений, Киев, Наукова думка, 1989,198 с.

36. Шор Н., Задачи минимизации матричных функций и недифференцируемая оптимизация, 2, 1995, с 113 138.

37. Эндрюс Г., Применение вычислительных машин для обработки изображений, М, Энергия, 1977, 351 с.41 .Ярославский Л.П., Введение в цифровую обработку изображений, 1979, 312 с.

38. Agrawal R., Shevgaonkar R., Sahasrabudhe S., A fresh looks at the Hough transform, Pat. Rec. Let., 17, 1996, pp. 1065 1068.

39. Alparone L.,Garzelli A., Decimated geometric filter for edge preserving smoothing of non - white noise, Pat. Rec. Let., 19, 1998, pp. 89 - 96.

40. Ballard D., Generalizing the Hough transform to detect arbitrary shapes, Pat. Rec. Let., 19, 1981, pp. Ill 122.

41. Barnes E., An algorithm for separating patterns by ellipsoids, SIAM J. Alg. and Disc. Math., 6, 1982.

42. Bernd J., Digital Image Processing. Concepts, Algorithms and Scientific Applications. 4th edition, 1997.

43. Bezdek J., Pattern recognition with Fuzzy Objective Function Algorithms, Plenum, New York.

44. Boukamp В., Immittance data of electrochemical systems, pp. 31 43

45. Biernacki C., Celeus G., Govaert G., An improvement of the NEC criterion for assessing the number of clusters in a mixture model. Pattern recognition letters 20, 1999, pp. 267-272.

46. Chun Та Ho, Ling - Hwei Chen, A high - speed algorithm for line detection, Pat. Rec. Let. 17, 1996, pp. 467 - 473.

47. Cui Y., Weng J., Reynolds H., Estimation of ellipse parameters using optimal minimum variance estimator, Pat. Rec. Let., 17, 1996, pp 309 316.

48. Canny J., A computational approach to edge detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8, 1986, pp. 679 698.

49. Dave R. N., Bhaswan K., Adaptive fuzzy с shells clustering and detection of ellipses, IEEE Trans. Neural Networks 3, 1992, pp. 643 - 662.

50. Daily, J.W., Riley, W.F. Experimental Stress Analysis, McGraw Hill International Editions, NY, 1991.

51. De Backer S., Scheunders P., A competitive elliptical clustering algorithm. Pattern recognition letters 20,1999, pp. 1141-1147.

52. Duda R., Hart P., Use the Hough transform to detect lines and curves in pictures, Comm. ACM, 15, 1972, pp. 11 15.

53. E1 Fallah A., Ford G., On mean curvature diffusion on nonlinear image filtering, Pat. Rec. Let., 19, 1998, pp. 433 - 437.

54. Fan J., Notes on Poisson distribution based minimum error thresholding, Pat. Rec. Let., 19, 1998, pp. 425 - 431.

55. Gath I., Dan H., Fuzzy clustering ring-shaped clusters. Pattern recognition letters 16, 1995, pp. 727-741.

56. Ho C., Chen L., A fast ellipse/circle detector using geometric symmetry, Pattern Recognition, 1995, 28(1), pp. 117-124.

57. Hu Z., Ma S., Uniform line parameterization, Pat. Rec. Let., 17, 1996, pp. 503 -507.

58. Jianiping F., Rong W., Liming Zh., Dingjia X., Fuxi G., Image sequence segmentation based on 2D temporal entropic thresholding. Pattern recognition letters 17, 1996, pp. 1101-1107.

59. Jansing E., Albert Th., Chenoveth D., Two dimensional entropic segmentation, Pat. Rec. Let., 20, 1999, pp. 329 - 336.

60. Khaled S. Al-Sultan, Maroof Khan M. Computational experience on four algorithms for the hard clustering problem. Pattern recognition letters 17, 1996, pp. 295-308.

61. Kittler J., Illingworth J., Minimum error thresholding, Pat. Rec. Let., 19, 1986, pp. 41-47.

62. Kurita T., Otsu N., Maximum likelihood thresholding based on population mixed models, Pat. Rec. Let., 19, 1998, pp 237 246.

63. Lei Y., Wong K., Ellipse detection based on symmetry, Pat. Rec. Let, 20, 1999, pp. 41 -47.

64. Levitt T., Domain independent object description and decomposition, Proceeding AAAI-84, 207-211.

65. Marr D., Hildreth E. Theory of edge detection, Computer vision, IEEE , Los Alamitos, CA, 1991, pp. 77 107.

66. McLaughlin R., Randomized Hough Transform: Improved ellipse detection comparison,, Pat. Rec. Let., 19, 1998, pp. 299 305.

67. McDonnel M., Box filtering techniques, Computer Graphics and image processing, 17(3), 1981, pp 65-70.

68. Nair P., Saunders A., Hough transform based ellipse detection algorithm, Pat. Rec. Let., 17, 1996, pp. 777 784.

69. Nagao M., Matsuyama T, A structural analysis of complex aerial photographs, Plenum Press, New York, 1980.

70. Park R. H., Yoon K., Choi W., Eight - point discrete Hartley transform as an edge operator and its interpretation in the frequency domain, Pat. Rec. Let., 19, 1998, pp. 569 -574.

71. Peng-Yeng Yin. Algorithms for straight line fitting using £-means. Pattern recognition letters 19, 31-41, 1998.

72. Pham D., Prince J., An adaptive C means algorithm for image segmentation in the presence inhomogeneities, Pat. Rec. Let., 20, 1999, pp. 57 - 68.

73. Pham T., Yan H., An effective algorithm for the segmentation of digital plane curves The isoparametric formulation, Pat. Rec. Let., 19, 1998, pp. 171 -176.

74. Pitas I., Venetsanopoulos, Nonlinear order statistic filters for image filtering and edge detection, signal processing, 1986, 10(10), pp. 573-584.

75. Rezaee R., Lelieveldt B., Reiber J., A new cluster validity index for the fuzzy c mean, Pat. Rec. Let., 19, 1998, pj) 237 - 246.

76. Risse T.,Hough transform for line recognition: Complexity of evidence accumulation and cluster detection, Comput. Vision Graphics Image process, 46, 1989, pp. 327-345.

77. Rosin P., Analyzing error of fit function for ellipses, Pat. Rec. Let., 17, 1996, pp. 1461 1470.

78. Rosin P., Ellipse fitting by accumulation five point fits, Pat. Rec. Let., 14, 1993, pp. 661 -669.

79. Rosin P.,A note on the least squares fitting of ellipses, Pat. Rec. Let., 14, 1993, pp. 799-808.

80. Ser P., Siu W., Memory compression for straight-line recognition using the Hough transform, Pat. Rec. Let., 16, 1995, pp 133 145.

81. Shankar B., Murthy C., Pal S., A new gray level based Hough transform for region extraction: An application to IRS image, Pat. Rec. Let., 19, 1998, pp. 197-204.

82. Shen L., Song X., Iguchi M., Yamamonto F., A metod for recognizing particle images, Pattern Recognition Letters 21(2000), pp. 21-30.

83. Shor N., Berezovsski O., «New algorithms for constructing optimal circumscribed and inscribed ellipsoids, Optim. Methods Software, Vol.1, 1992, pp. 283-289.

84. Sonka M., Hlavac V., Boyle R., Image Processing, Analysis, and Machine Vision, PWS Publishing, 1999, 770 p.

85. Starink J., Localization of circular objects, Pat. Rec. Let., 14, 1993, pp 895 -905.

86. Tyans S., Median Filtering, deterministic properties, In T S Huang, editor, Two-Dimencional Didital Signal Processing, volume II, Springer Verlag, Berlin, 1981.

87. Van Ryzin J. (1977), Classification and clustering, Acad. Press, Inc., NY, 1997

88. Wang D., Vagnucci A., Gradient inverse weighting smoothing schema and the evaluation of its performance, Computer Graphics and Image Processing, 1981,15

89. Wen W., Xia A., Verifying edges for visual inspection purposes, Pat. Rec. Let, 20, 1999, pp 237-246.

90. Wepner W, Huggins R, Ann. Rev, Mater.Sci,8,1978.

91. Yang J, Xiabo Li, Boundary detection using mathematical morphology, Pat. Rec. Let, 16, 1995, pp 237-246.

92. Yin P, Algorithms for straight line fitting using k means, Pat. Rec. Let, 19, 1998, pp 31 -41.

93. Yuen S, Shape from contour using symmetries, Proceeding of de First European Conference on Computer Vision, Antibes, France, 1990, pp. 437453

94. Yuen P. C, Feng G. C. A novel method for parameter estimation of digital arc. Pattern recognition letters 17, 1996, pp. 929-938,

95. Zahid N, Abouelala O, Limouri M, Essaid A Unsupervised fuzzy clustering. Pattern recognition letters 20, 1999, pp. 123-129.

96. Beliavski G, Bulenkova E, Localization of elliptic objects. The proceeding of Mexican-Hungarian workshop on factory automation and materials sciences. 9-11 March, 1999, pp. 210 223.

97. Castaneda-Miranda A, Bulenkova E, Beliavski, Castano V. Automatic optical alignment by numerical ellipse fitting. Optik 111, No. 5, , 2000, pp. 189-194.

98. Beliavski G, Bulenkova E, An Image Processing Using Ellipse Pattern Grids, The proceeding of ASSEN99, 23-25 August, Seoul, Korea, 1999, pp. 197-202.141

99. Белявский Г., Буленкова Е., Синтез линейно-квадратичного решающего правила в изолированной постановке. Обозрение прикладной и промышленной математики, т.5, вып. 2,М. 1998, с. 201 -202.

100. Белявский Г., Буленкова Е., Описание изображения, состоящего из эллипсов. Материалы конференции по применению прикладной математики и компьютерных технологий, Кисловодск, 1999, с. 18-19.

101. Белявский Г., Буленкова Е., Об оценке параметров нормального закона эллипсоидом минимального объёма. Известия вузов. Естественные Науки, СКНЦ, 3, 1999, с. 43 48.

102. Белявский Г., Буленкова Е., Применение преобразования Хо для распознавания эллипсов. Обозрение прикладной и промышленной математики, т 6, вып. 1, М. 1999. с. 118 121.

103. Белявский Г., Буленкова Е., Применение преобразования Хо для локализации циклических объектов, в сб. научных трудов 5-го Всероссийского симпозиума «Математическое моделирование и компьютерные технологии», Кисловодск, 20000, с 29 31.

104. Белявский Г., Буленкова Е., Нелинейная фильтрация сигналов, Обозрение прикладной и промышленной математики, т 2, вып. 2, М. 2000. с. 475-476.