Содержание к диссертации
Введение
Глава 1. Математические методы морфологического анализа изображений и моделирования случайности и нечёткости (обзор литературы) 12
1.1 Морфологический анализ изображений 12
1.1.1 Пространство полутоновых изображений 13
1.1.2 Форма изображения 15
1.1.3 Независимость изображений по форме 17
1.1.4 Морфологические методы решения прикладных задач анализа изображений [42] 20
1.1.5 Морфологический анализ изображений при изменениях геометрических параметров сцены и условий регистрации 29
1.2 Математическое моделирование случайности и нечёткости 29
1.2.1 Теория вероятностей 29
1.2.2 Теория возможностей Заде и её аналоги 33
1.2.3 Теория возможностей Пытьева 34
Глава 2. Математические модели случайной формы изображения 41
2.1 Геометрическая форма объекта и форма его изображения 42
2.2 Вероятностная модель случайной формы изображения
2.2.1 Основные определения и модель регистрации изображения 46
2.2.2 Идентификация 48
2.2.3 Обучение идентификации 50
2.3 Возможностная модель случайной формы изображения 51
2.3.1 Основные определения и модель регистрации изображения 51
2.3.2 Идентификация 52
2.3.3 Согласованность вероятностной и возможностной моделей идентификации 53
2.3.4 Обучение идентификации 57
Глава 3. Численные методы решения задач идентифи кации объектов по их изображениям и моделирования вероятностной случайности возможностными методами 59
3.1 Численное решение задачи идентификации объектов со случайными геометрическими формами в вероятностной постановке 59
3.1.1 Разбиение семейства форм изображений 59
3.1.2 Упрощённая постановка задачи идентификации и её решение 80
3.1.3 Обучение идентификации 87
3.2 Приближённое решение задачи идентификации объектов со случай ными геометрическими формами в возможностной постановке 89
3.2.1 Упрощённая постановка задачи идентификации и её решение 89
3.2.2 Обучение идентификации 93
3.3 Построение вероятностной модели стохастического эксперимента по его возможностной модели 94
Глава 4. Программный комплекс для решения задач идентификации и выделения объектов на изображениях и компьютерного моделирования случайности возможностными методами 97
4.1 Программный модуль для компьютерного моделирования вероятностной случайности возможностными методами 97
4.2 Идентификация объектов со случайными геометрическими формами
4.2.1 Тестирование программного модуля для построения оптимальных вероятностных и возможностных правил идентификации на реальных данных 101
4.2.2 Тестирование программного модуля для построения оптимальных вероятностных и возможностных правил идентификации на модельных данных 103
4.3 Программный модуль для построения алгоритмов поиска известного объекта со случайной формой на предъявленном изображении 108
Заключение 114
Список использованных обозначений и сокращений
- Морфологические методы решения прикладных задач анализа изображений [42]
- Вероятностная модель случайной формы изображения
- Упрощённая постановка задачи идентификации и её решение
- Идентификация объектов со случайными геометрическими формами
Морфологические методы решения прикладных задач анализа изображений [42]
В отличие от многих других методов анализа изображений, в том числе морфологических (таких как методы теории распознавания образов [35—37], методы математической морфологии Матерона-Серра [3, 4] и др.), рассматриваемые в настоящем разделе методы морфологического анализа изображений Пытьева [5-9, 38—42] могут быть с успехом применены при решении таких задач, как узнавание объектов на изображениях, зарегистрированных при существенно отличающихся условиях освещения, выделение структурных отличий (отличий по форме) изображений, снятых разными камерами или в разных спектральных диапазонах и т. п. Иными словами, методы морфологического анализа изображений Пытьева позволяют решать указанные задачи в ситуациях, характеризующихся принципиальной неизвестностью и неконтролируемостью условий регистрации изображений. Математической основой данного свойства служит идея анализа изображений в терминах инвариантов относительно неизвестных и неконтролируемо изменяющихся условий регистрации.
Рассмотрим типовую схему регистрации полутонового изображения, см. рис. 1.1. Для регистрации обычно используется аппаратура (фотоаппарат, видеокамера и др.), основными элементами которой являются: 1) объектив, осуществляющий фокусировку светового потока; 2) матрица светочувствительных детекторов, осуществляющая преобразование падающего на неё света в выходной электрический сигнал, который в современной аппаратуре оцифровывается и представляется в виде матрицы целых или вещественных чисел. В случае регистрации полутоновых изображений все светочувствительные детекторы, составляющие матрицу, одинаковы.
Введём на поверхности, которую образует матрица светочувствительных детекторов (как правило, это плоскость), координаты ж1, х2 Є (—оо, оо). Множество пар (ж1, ж2), соответствующих центрам светочувствительных детекторов, которое обозначим Х, называется полем зрения. Таким образом, между множеством детекторов матрицы и полем зрения X установлено взаимно-однозначное соответствие:
1) каждому детектору соответствует точка х = (ж1, х2) поля зрения X, где х1} х2 Є (—оо, оо) — координаты цента детектора в выбранной системе;
2) каждой точке х = (ж1, х2) Є X соответствует детектор матрицы, центр которого имеет координаты ж1, х2
Пусть на сг-алгебре S3 подмножеств поля зрения X определена мера /І. Например, если поле зрения X конечно, то есть X = {хі, ..., жп}, то /І может быть определена на алгебре У{Х) всех подмножеств множества X как считающая мера, то есть такая, что ц({х}) = 1, х Є X. Если же X — прямоугольное подмножество координатной плоскости, то в качестве /І может выступать мера Лебега, определённая на а-алгебре всех борелевских подмножеств X.
Математической моделью полутонового изображения в морфологическом анализе является интегрируемая с квадратом функция /() : X — (—оо, оо):
Значения функции /() интерпретируются следующим образом: для всякой точки (ж1, х2) = х Є X величина f(x) есть выходной сигнал светочувствительного детектора, центр которого имеет координаты ж1, х2 Є (—оо,оо). Данный выходной сигнал, который принято называть яркостью изображения в точке ж, определяется выражением (1.1). Множество всех функций, определённых на Х, принимающих значения на (—оо, оо) и удовлетворяющих (1.2), с естественными линейными операциями, скалярным произведением
Ключевым понятием морфологического анализа изображений является понятие формы изображения. Первое математическое определение формы изображения, данное в [5], основано на математической связи изображений сцены, полученных при одинаковых условиях освещения, но с использованием разной регистрирующей аппаратуры. Данная связь является следствием выражения (1.1).
Пусть /i, J2 Є С2(Х) — два изображения одной сцены, зарегистрированные разными камерами при одинаковых освещении и ракурсе. Если эти камеры отличаются только функциями и{) в (1.1), причём функции щ{) и щ{-), соответствующие двум данным камерам, обратимы, то найдётся такая функция F(-) : (—00,00) — (—00,00), что fi(x) = (/2(2;)), хєХ. (1.3) Верно и обратное — найдётся такая функция F (-) : (—00, 00) — (—00, 00), что J2\X) = г \}\\Х)), х Є X. (1.4) Рисунок 1.2 — Два изображения одного и того же фрагмента стены, отличающиеся контрастностью.
Пример подобных изображений приведён на рис. 1.2. В связи с (1.3), (1.4) дадим следующее определение [5].
Заметим, что интерпретация определения 1.1 может быть гораздо более широкой, чем интерпретация, связанная с рассуждениями, приведшими к этому определению. Действительно, если fi Є V/2, /і, /2 Є ііКX\ то: — либо изображения f\ и /2 связаны равенствами (1.3), (1.4), в этом случае верно также и /2 V/1, а изображения /і, /2 можно считать эквивалентными по форме в том смысле, что все детали сцены, которые можно увидеть на одном из них, можно увидеть и на другом, независимо от того, какими камерами и при каких условиях освещения зарегистрированы /і и /2; — либо верно только равенство (1.3), в то время как (1.4) нарушено, в этом случае некоторые детали сцены, различимые на изображении /2, не различимы на /і (радикальным примером такой ситуации может служить случай, когда изображение /і получено при отсутствии освещения и f\(x) = 0, х Є X).
Таким образом, форма Vf изображения / Є С2{X) может быть интерпретирована как множество изображений сцены, представленной на /, несущих о геометрической форме объектов этой сцены, их расположении относительно регистрирующей аппаратуры и взаимном расположении такую же или меньшую информа цию, что и /. При этом изображения из Vf могут быть зарегистрированы разными камерами, при разных условиях освещения, в разное время года (если речь идёт, например, о снимках поверхности Земли из космоса) и т.д. Так, изображения f\ и /2, приведённые на рис. 1.3 слева, зарегистрированы с использованием одной и той же камеры, но при существенно отличающихся условиях освещения, при этом они связаны равенством (1.3), т.е. f\ Є V/2, график функции F(-) приведён на рис. 1.3 справа.
Можно показать, что форма Vf всякого изображения / Є С?{Х) является линейным многообразием (вообще говоря, не замкнутым) в пространстве С?ЛХ\ Если в дополнении к этому V/ замкнута, т. е. является линейным подпространством С?[Х\ то ей может быть поставлен в соответствие оператор Пу ортогонального проецирования (или иначе проектор) на Vf. Результат действия оператора Пу; на изображение д Є С?{Х) определяется как решение задачи наилучшего приближения1 д изображениями из V/, т. е.
Вероятностная модель случайной формы изображения
Форма таких кривых определяется значениями параметров acur, ainc Є (—оо,оо), при этом параметр а,[пс равен котангенсу угла наклона еловых иголок относительно еловой ветки (горизонтали на рис. 2.1 и 2.2), а асш будем интерпретировать как параметр, определяющий кривизну иголок, так как при асш = 0 линия {ж Є X : Sacur,ainc( ) = с}, с Є (—оо, оо) представляет собой объединение двух лучей, исходящих из одной точки. В силу (2.1) изображение / Є V cur;a;nc может иметь произвольную яркость f(x) при х Є Хсеп, а на множествах Xtop и Abot области постоянной яркости изображения / представляют собой объединения линий уровня функции sa а. (), т. е. состоят из линий, имеющих одинаковую кривизну и наклон, заданные параметрами асш и а,[пс соответственно. Эти линии соответствуют иголкам еловой ветки. В связи с этим множество V cur;a;nc будем называть формой изображения еловой ветки с кривизной иголок асш и наклоном иголок относительно ветки 2ІПС. В данном примере случайная форма изображения еловой ветки есть случайный элемент, принимающий значения на V — множестве всех форм, близких к V cur;a;nc при некоторых асш Є Acur, ainc Є А[ПС, где Асш и Дпс — подмножества числовой прямой, в пределах которых лежат значения параметров асш и 2inc. Вопросы определения близости на множестве форм изображений рассмотрены в главе 3.
В дальнейшем V будем обозначать семейство форм изображений, на котором принимает свои значения всякая случайная форма изображения.
В случае, если V — параметрическое семейство форм изображений, то есть V = \у.ф \ ф Є Ф}, где Ф — множество, на котором принимает значения параметр ф формы изображения 1 , и на а-алгебре A подмножеств множества Ф определена мера v (-) : srf — [0, оо), то на сг-алгебре / = \у.ф : ф Є А } А є &/ (2.2) подмножеств семейства V может быть определена мера v: v(A) = v ({ф : Уф Є 4}), А є srf. (2.3)
Определение 2.1. Вероятностной моделью случайной формы изображения назовём вероятностное пространство (V, &/, Рг), где srf — сг-алгебра подмножеств семейства V, и Рг — вероятность, определённая на srf.
Определение 2.2. Случайной формой изображения, моделью которой является (V, JZ/, Рг), назовём канонический случайный элемент У вероятностного пространства (V, JZ/, Рг), принимающий значения в V, распределение вероятностей которого есть Рг (см. раздел A.1.2 приложения A).
В силу довольно сложной природы вероятностного пространства (V, , Рг) — в нём множество элементарных исходов V является семейством подмножеств пространства изображений С?[Х) — не существует универсального конструктивного способа задания вероятностной меры Рг. Однако она может быть задана в случае, если V={"Ц/, єФ} — параметрическое семейство форм изображений, и параметр ф является случайным элементом со значениями в Ф, т. е. задано вероятностное пространство (Ф, &/ , Рг,/,), где srf — сг-алгебра подмножеств множества Ф, удовлетворяющая (2.2), и Piy, : srf — [0,1] — распределение вероятностей параметра ф. Тогда для определения Рг может быть использовано выражение (2.3), в котором вместо v следует читать Рг,/,, и вместо v — Рг.
Как было указано выше, изображение g Є С?{Х) некоторого объекта несёт информацию: 1) О геометрической форме изображённого объекта и его ориентации в про странстве. В морфологическом анализе изображений математическим объектом, предназначенным для моделирования этой информация, является форма изображения, которая в настоящем разделе считается случайным элементом, принимающим значения в V. 2) Об условиях регистрации, при которых получено д.
Для моделирования условий регистрации зададим множество Л функций, определённых на семействе форм изображений V, принимающих значения в С2ЛХ) и таких, что VA Є Л А(У) Є V, V Є V. (2.4) Определим содержательную интерпретацию каждой отдельной функции, удовлетворяющей (2.4), и всего множества Л в целом.
Учёт информации о геометрической форме объекта и его ориентации в пространстве, выраженной формой его изображения V Є V, определяет изображение д данного объекта с точностью до множества V, т. е. позволяет утверждать лишь, что д Є V. Функция А(-) каждой форме изображения V Є V ставит в соответствие единственное изображение д = X(V) Є V. Таким образом, функция А(-) несёт информацию, которая вместе с информации о геометрической форме объекта и его ориентации в пространстве позволяет полностью определить, каким будет изображение д данного объекта. Вся информация, которая может быть получена по изображению д, разделяется на две части — пункты 1, 2, перечисленные выше, — и всю информацию по пункту 1 (и только по пункту 1) несёт форма изображения V, следовательно, функция А(-) несёт всю информацию по пункту 2 (и только по пункту 2).
Таким образом, всякую функцию А(-) : V — С2(Х), удовлетворяющую (2.4), будем считать математической моделью некоторых условий регистрации. В связи с этим множество Л, являющееся подмножеством множества всех функций, удовлетворяющих (2.4), будем интерпретировать как математический объект, несущий информацию об ограничениях, которым удовлетворяют условия регистрации изображений. Пусть в добавок ко всему изображение искажается случайным аддитивным шумом. Тогда с учётом всего вышесказанного модель регистрации изображения со случайной формой У (см. определение 2.2) определяется следующей схемой: = \{У) + v, (2.5) где Л неизвестная функция из множества Л, моделирующая неизвестные условия регистрации; — У — случайная форма изображения с распределением Рг; — v — случайное изображение, моделирующее случайный шум; далее будем считать v абсолютно непрерывным относительно меры и, определенной на сг-алгебре с подмножеств пространства изображений С?ЛХ\ а плотность его распределения обозначим piv -) : С?АХ)
Упрощённая постановка задачи идентификации и её решение
В соответствии с определением 2.1, вероятностной моделью случайной формы изображения называется вероятностное пространство (V, A, Рг), множеством элементарных событий в котором является семейство V форм изображений, то есть семейство подмножеств пространства изображений С?ЛХ\ Пусть А Є A и требуется эмпирически, то есть на основе серии наблюдений, оценить вероятность Рг(Л). Рассмотрим серию L независимых испытаний, каждое из которых представляет собой стохастический эксперимент, модель которого есть (V, A, Рг). Если бы мы могли наблюдать результаты Vі, ..., VL этих экспериментов, то оценкой вероятности Рт(А) была бы частота индикаторная функция множества А. Однако в задачах анализа изображений формы Vі, ..., VL недоступны непосредственному наблюдению. Вместо этого наблюдению доступны изображения /і, ..., //,, являющиеся реализациями случайных элементов где v\ — независимые случайные элементы со значениями в С?ЛХ\ моделирующие аддитивный шум.
Рассмотрим метод разбиения семейства V, позволяющий получать оценки вероятностей событий А Є A по обучающей выборке изображений (3.2)
Теорема 3.1. Пусть V, Vi, V2 — линейные подпространства С?{Х), ортогональные проекторы на которые обозначим П, Пі, П2 соответственно. Пусть размерность V ограничена, т. е. dim V 00. Тогда і def . г- I ii-pf тт-гн2 итт тт.г12 г ,- п2 ( -ь нтт-гн 1 \ л а = mi ЦПіП/Ц — 1І2І1/ J Є L (л), П/ = 1 О, (3.3) если и только если оператор П(Пі — П2)П неотрицательно определён. Величина h строго положительна, если и только если оператор П(Пі — П2)П неотрицательно определён и гапкП(Пі — П2)П = dim V, тогда h совпадает с минимальным ненулевым собственным значением П(Пі — П2)П. Доказательство. В силу того, что П, Пі, П2 ортогональные проекторы, верно следующее: Неотрицательная определённость оператора П(Пі — ІІ2)П эквивалентна неотрицательной определённости квадратичной формы (3.4), что доказывает первое утверждение теоремы. Так как оператор П(Пі— ІІ2)П принимает значения на подпространстве V, размерность dim V которого ограничена, число г = гапкП(Пі — ІІ2)П dim V оо. В силу самосопряжённости ортогональных проекторов П, Пі, П2 самосопряжён и оператор П(Пі — П2)П. Обозначим hi, его собственные значения, перенумерованные так, что hi Ф 0, г = 1, ..., г, и ai, Й2, ... — соответствующие им собственные векторы, образующие ортонормированный базис в С?{Х), первые dim V из которых принадлежат V. Тогда (3.4) можно переписать в виде
Пусть V, Vi, V2 — формы изображений, являющиеся линейными подпространствами С2АХ), например, формы изображений еловых веток, определённые согласно (2.1). В соответствии с теоремой 3.1 ранг оператора П(Пі — П2)П и его знакоопределённость определяют сравнительную близость форм V, Vi и различие форм V, V2 (одно в сравнении с другим). Действительно, всякое изображение /єУ ближе к форме Vi, чем к форме V2, т. е. если и только если оператор П(Пі — ІІ2)П неотрицательно определён. Причём неравенство (3.6) становится строгим для всех / Є V : / 0, если и только если оператор П(Пі — ІІ2)П неотрицательно определён и гапкП(Пі — ІІ2)П = dim V. Если же оператор П(Пі — ІІ2)П знакопеременен, то найдутся по крайней мере два изображения /i, J2 Є V, такие что /і ближе к Vi, чем к V2, но /2, напротив, ближе к V2, чем к Vi, т. е.
Определение 3.2. Если форма V /г-близка к V\ в сравнении с V2 или к V2 в сравнении с Vi, будем говорить, что сравнительная h-близость формы V к формам Vi, V2 определена. В противном случае будем говорить, что сравнительная h-близость формы V к формам Vi, V2 не определена.
Доказанная выше теорема 3.1 определяет связь сравнительной близости форм изображений, понимаемой согласно определениям 3.1-3.2, со знакоопределённостью оператора П(Пі — П2)П, его рангом и величиной h в (3.3). Докажем теорему, предоставляющую конструктивный метод определения указанных характеристик оператора П(Пі — П2)П, а значит и проверки сравнительной близости форм изображений. Теорема 3.2. Пусть выполнены условия теоремы 3.1, и dimV оо, s = 1, 2. Пусть в подпространствах V, Vi, V2 заданы ортонормированные базисы
Идентификация объектов со случайными геометрическими формами
Пусть Q = {бо 1, ... , LOk}, и A = P(Q). Предложенный в разделе 3.3 метод построения вероятностной модели (Г2, A, Рг) стохастического эксперимента по заданной возможностной модели (Г2, A, Р) — см. 1)-6) на стр. 95 — реализован в среде Scilab. На его основе разработаны программные модули, позволяющие строить компьютерные модели вероятностной случайности возможностными методами, а именно:
1) С участием пользователя строить вероятность Рг, с которой максимально согласована возможность Р, посредством специализированного графического интерфейса. Блок-схема данного процесса представлена на рис. 4.1, 4.2. Специализированный графический интерфейс пользователя, см. рис. 4.3, разработан с использованием технологии Qt и языка python [62, 63].
2) Выбирать вероятность Рг случайно из класса вероятностей, с которыми максимально согласована возможность Р, в автоматическом режиме (без участия пользователя). Блок-схема данного алгоритма также дана на рис. 4.1, однако, в отличии от предыдущего пункта, в процессе, помеченном « », U Построение вероятности Рг, с которой максимально согласована возможность Р Q = бо Є Q : р(бо ) 0} \ Конец Положить рг(бо ) = 0 при си Є Vt \ Q На настоящей блок-схеме использованы обозначения р(ш) = Р({ш}), рт(ш) = Рг({о;}), ш Є Q. Выбрать си Є Vt irk Выбрать рг(б 7) Є (pr,pr), где рг и рг — решения задач линейного программирования (3.75) Q = Q \ {си} Блок-схема алгоритма построения вероятности Рг, с которой максимально согласована заданная возможность Р. выбирается случайно из множества Qo = и Є Q : р( х ) = тахр(б /) ,ав процессе, помеченном « », рг(б 7) выбирается случайно на отрезке (рг,рг).
3) Реализовывать стохастический эксперимент с заданной возможностной моделью (Г2, A, Р). Для этого сначала с использованием алгоритма, описанного в пункте 2) выше, случайно выбирается вероятность Рг, а затем с использованием стандартного генератора случайных чисел реализуется стохастический эксперимент с вероятностной моделью (Г2, A, Рг). Выбор UJ Є Q с участием пользователя, см. рис. 4. Построить множество Qo = UJ Є Q :р(бо ) = maxp(w )
Для каждого си Є Qoнайти решения pr(uj) иpr((x ) задач линейногопрограммирования (3.75) Отобразить на экране отрезки (pr(u;),pf(u;)), си Є Г2о (см. рис. 4.3(a) Пользователь выбирает ZJ Е &о щелчком мыши по соответствующему отрезку (pr(uJ), рг(б 7)) irk Выбор рг(б 7) Є (pr,pr) с участием пользователя, см. рис. 4.1 Отображать в пределах отрезка (рг(а;), рт(б 7)) на экране подвижную линию, управляемую перемещениями мыши Пользователь выбирает значение рг(б 7) Є (pr(oJ), рг(б 7)) перемещением подвижной линии на экране и закрепляет выбор щелчком мыши (см. рис. 4.3(6)) ГКонец (б) Выбор пользователем рг(ш). Переход в режим ввода пользователем значения рг(б 7) Є (pr,pr) (а) Выбор пользователем йеП. Рисунок 4.2 — Блок-схема процесса выбора пользователем элементарного события си Є Г2 с последующим выбором значения рг(б 7), см. рис. 4.1. (а) Выбор П, см. рис. 4.2(a). По = {2, 3}. Вертикальные отрезки, ограниченные белыми треугольными маркерами, — предложенные пользователю отрезки (pr(),pr()), По (б) Пользователь ьыбрал = 3и рг() (кружок Б нижней части окна). (Б) Построение вероятности Рг завершено. Нижняя гистограмма — распределение Рг.
Рисунок 4.3 — Графический интерфейс для построения вероятности Рг, с которой максимально согласована возможность Р, с участием пользователя, см. 1) на стр. 97. Q = {1, ..., 5}. Верхние гистограммы — заданное пользователем распределение возможности Р. Процесс построения Рг соответствует блок-схемам, представленным на рис. 4.1, 4.2.
Предложенные в разделах 3.1 и 3.2 численные методы приближёного построения оптимальных критериев (правил идентификации) в задаче идентификации объектов со случайными геометрическими формами по их изображениям реализованы в среде Scilab. Полученный программный модуль для построения оптимальных вероятностных (см. раздел 3.1 и задачу (3.42)) и возможностных (см. раздел 3.2 и задачу (3.58)) правил идентификации протестирован на реальных данных в задаче идентификации породы ели по изображению её ветки, а также на модельных данных, полученных с использованием программного модуля, рассмотренного в разделе 4.1.
Для тестирования программного модуля в задаче идентификации породы ели по изображению её ветки было зарегистрировано по 100 изображений веток голубой и европейской елей, см. рис. 2.1 на стр. 43. Тестирование проводилось следующим образом, см. блок-схему на рис. 4.4:
1) Множества T1 и T2 изображений веток голубой и европейской елей разбивались случайным образом на две части каждое. Первые части, которые обозначим T1 и T2, содержащие по L изображений, использовались для приближённого построения оптимальных вероятностного и возможностного критериев с использованием численных методов, предложенных в разделах 3.1 и 3.2 соответственно.
2) По изображениям из множеств (T1 T2) \ (T1 T2) проводилась идентификация породы ели с использованием построенных на предыдущем этапе критериев и контроль качества идентификации.