Содержание к диссертации
Введение
ГЛАВА 1. Локально-интерполяционные оценки кривизны 40
1.1. Введение 40
1.2. Необходимые сведения из дифференциальной геометрии кривых на плоскости 44
1.2.1. Способы задания кривой 44
1.2.2. Касательная к кривой. Длина кривой 45
1.2.3. Кривизна кривой 46
1.2.4. Классы кривых и классы вероятностных зашумлений 48
1.3. Исследование оценки кривизны, полученной методом локальной
интерполяции оцифрованной кривой 50
1.3.1. Оценки кривизны методом локальной интерполяции оцифрованной кривой 54
1.3.2. Систематическая ошибка оценки кривизны 57
1.3.3. Распределение вероятностей случайной оценки кривизны при некоррелированном нормальном зашумлений кривой 59
1.3.4. Смещение случайной оценки кривизны 62
1.3.5. Случайная ошибка оценки кривизны 70
1.3.6. Упрощенная оценка кривизны методом локальной интерполяции 74
1.4. Оценка кривизны методом усреднения локально-интерполяционных оценок 75
1.5. Оценка кривизны методом аналитического сглаживания локально-интерполяционных оценок 80
1.5.1. Усреднение функций по Соболеву 81
1.5.2. е-усреднение кривизны 84
1.5.3. Аналитическое сглаживание локально-интерполяционных оценок кривизны 86
1.5.4. Систематическая ошибка аналитического сглаживания первичных оценок кривизны 87
1.5.5. Смещение аналитического сглаживания первичных оценок кривизны при сферическом нормальном зангумлении кривой 89
1.5.6. Случайная ошибка аналитического сглаживания первичных оценок кривизны при сферическом нормальном зашумлении
кривой 94
1.5.7. Оптимальные значения параметров аналитического
сглаживания первичных оценок кривизны 98
1.6. Выводы 100
ГЛАВА 2. Локально-аппроксимативные оценки кривизны 103
2.1. Введение 103
2.2. Оценивание кривизны методом явной локальной аппроксимации кривой 105
2.2.1. Оценка кривизны методом явной локальной аппроксимации кривой с помощью многочленов Чебышева 106
2.2.2. Систематическая ошибка оценки кривизны 109
2.2.3. Случайная ошибка оценки кривизны 113
2.2.4. Оптимальные значения параметров нахождения оценки кривизны 115
2.3. Оценивание кривизны методом неявной локальной
аппроксимации оцифрованной кривой 116
2.3.1. Метод геометрического сглаживания 118
2.3.2. Систематические ошибки оценок кривизны в методе геометрического сглаживания 122
2.3.3. Случайная ошибка линейной оценки кривизны в случае одномерного коррелированного зашумления непрерывной кривой 129
2.3.4. Случайная ошибка линейной оценки кривизны в случае двумерного некоррелированного зашумления дискретной кривой 132
2.3.5. Числовые характеристики случайной площади в целочисленной одномерной модели зашумления кривой 138
2.3.6. Устойчивость вычисления линейного случайного веса и оценки кривизны в целочисленной одномерной модели зашумления кривой 141
2.3.7. Смещения нелинейного случайного веса и оценки кривизны
в целочисленной одномерной модели зашумления кривой 144
2.3.8. Случайные ошибки нелинейного веса и оценки кривизны в целочисленной одномерной модели зашумления кривой 152
2.3.9. Числовые характеристики случайной абсолютной величины отклонения веса 157
2.3.10. Нахождение оптимальных значений размера окна 161
2.4. Выводы 163
ГЛАВА 3. Полигональные и векторные представления кривых 166
3.1. Введение 166
3.2. Меры информативности как способ агрегирования низкоуровневых особенностей 170
3.2.1. Аксиоматика меры информативности дискретной плоской кривой 173
3.2.2. Способы определения мер информативности контура 175
3.2.2.1. Усредненные функции информативности кривой 176
3.2.2.2. Функции информативности по локальной кривизне 179
3.2.3. Стохастическая аддитивная усредненная мера
информативности 183
3.2.3.1. Числовые характеристики стохастической аддитивной меры информативности 184
3.2.3.2. Нахождение оптимального устойчивого полигонального представления кривой 186
3.2.4. Стохастическая монотонная усредненная мера информативности 191
3.2.5. Стохастическая мера информативности по длине 195
3.2.5.1. Числовые характеристики длин сторон зашумленного многоугольника 195
3.2.5.2. Числовые характеристики стохастической меры информативности по длине 204
3.3. Получение минимального полигонального представления кривой методом нечеткой кластеризации 207
3.4. Устойчивость векторных представлений дискретной кривой 215
3.4.1. Устойчивость центра масс векторного представления контура 218
3.4.2. Устойчивость характеристик векторного представления контура 223
3.4.3. Устойчивость дескриптора Фурье 225
3.4.4. Применение теории для расчета вероятностных оценок изменения характеристик зашумленного контура 227
3.5. Вероятность уклонения центра масс векторного представления при целочисленном одномерном зашумленнии кривой 228
3.6. Выводы 233
ГЛАВА 4. Линейный индекс неточности и его применение в задачах анализа изображений 235
4.1. Введение 235
4.2. Основные определения и обозначения 239
4.3. Измерение количества неточностей в классе нижних (верхних) вероятностей с помощью разностей сопряженных мер 240
4.3.1. Сопряженная (двойственная) функция множеств 241
4.3.2. Разность сопряженных мер 243
ч
4.3.3. Усреднение разностей сопряженных мер 244
4.4. Аксиомы индекса неточности в классе нижних (верхних) вероятностей 246
4.5. Линейный индекс неточности 249
4.5.1. Положительные функционалы на конусе мер 249
4.5.2. Представления линейного индекса неточности 253
4.5.2.1. Описание линейного индекса неточности через преобразование Мебиуса дескриптивных мер 253
4.5.2.2. Описание линейного индекса неточности через свойства дескриптивных мер 259
4.6. Симметричный по дополнению индекс неточности 263
4.6.1. Общий вид линейного симметричного по дополнению индекса неточности 264
4.6.2. Крайнее множество линейных симметричных по дополнению индексов неточности 269
4.7. Продолжение индекса неточности на множество всех монотонных мер 272
4.8. Индекс неточности мер информативности по длине 277
4.8.1. Индекс неточности мер информативности по длине на алгебре, порожденной вершинами правильного я-угольника 278
4.8.2. Некоторые интерпретации индекса неточности меры информативности 286
4.9. Выводы 289
ГЛАВА 5. Вероятностная аппроксимация мер доверия и её приложения 291
5.1. Введение 291
5.2. Мера и центральная компонента неопределенности 294
5.3. Среднеквадратичная аппроксимация функции доверия вероятностной мерой 296
5.4. Векторное представление ближайшей меры. Алгебраические свойства преобразования ближайшей меры 307
5.5. Величина невязки среднеквадратичной аппроксимации 310
5.6. Симметричные меры доверия 313
5.7. Меры доверия, наименее уклоняющиеся от заданной
вероятности 315
5.8. Среднеквадратичная аппроксимация функций доверия к-аддитивными мерами 323
5.9. Равномерная аппроксимация функций доверия 324
5.10. Экстремальные меры доверия, ближайшие к вероятностной
мере 325
5.10.1. Некоторые множества экстремальных мер доверия, ближайших в среднеквадратичном к равновероятной мере 326
5.10.2. Экстремальные меры доверия, ближайшие в среднеквадратичном к произвольной вероятностной мере 333
5.10.3. Оценка числа экстремальных мер доверия, ближайших в среднеквадратичном к равновероятной мере 336
5.11. Задача оценки выигрышей коалиций при заданных полсзностях
отдельных игроков 340
5.12. Выводы 342
Заключение 344
Литература
- Касательная к кривой. Длина кривой
- Распределение вероятностей случайной оценки кривизны при некоррелированном нормальном зашумлений кривой
- Оценка кривизны методом явной локальной аппроксимации кривой с помощью многочленов Чебышева
- Аксиоматика меры информативности дискретной плоской кривой
Введение к работе
Актуальность темы. Интенсивное развитие за последние 40 лет технических средств регистрации и обработки изображений привело к бурному росту числа методов и алгоритмов обработки и анализа изображений. По широте используемого математического аппарата эти методы покрывают практически все разделы современной математики. В то же время привлечение разнообразного математического аппарата не всегда сопровождалось качественным анализом разработанных методов и алгоритмов. Как правило, при анализе алгоритмов доминировал статистический подход, выбор параметров алгоритмов осуществлялся путем обучения по выборке образов некоторого класса. Это не всегда позволяло найти качественные аналитические закономерности работы алгоритмов для разных классов изображений, найти оптимальные значений параметров, спрогнозировать результаты работы «похожих» алгоритмов или применение алгоритмов для других классов изображений и т.д. Кроме того, одним из ключевых требований, предъявляемых к методам обработки и анализа изображений, является необходимость учитывать высокую степень неопределенности обрабатываемой графической информации, связанной как с действием внешних факторов (аппаратным зашумлением, оцифровкой и квантованием изображений, перекрытием объектов, наличием бликов, теней и т.д.), так и с необходимостью выделять небольшое число информативных признаков на изображении сложных объектов.
Необходимость выделения информативных признаков объектов на изображении в условиях неопределенности выдвигает на первый план решение следующих задач:
а) разработка робастных к зашумлению методов выделения локальных информатив
ных признаков объектов на изображении;
б) формирование робастных к зашумлению высокоуровневых представлений и опи
саний изображений объектов, являющихся результатом агрегирования информации
о локальных признаках;
в) нахождение минимальных, информативных, устойчивых к зашумлению вектор
ных представлений и описаний изображений;
г) оценка количества неопределенности в том или ином представлении объектов;
д) ранжирование неопределенностей.
Цели и задачи исследования. Целью настоящей диссертационной работы является разработка и анализ робастных к зашумлению методов и алгоритмов выделения низкоуровневых информативных признаков, методов формирования устойчивых к зашумлению высокоуровневых представлений и описаний изображений объектов, развитие математического аппарата, связанного с вычислением количества неопределенности мер информативности и с аппроксимацией таких мер.
В связи с поставленной целью необходимо было решить следующие задачи:
-
Исследовать на робастность к зашумлению изображений новые и ранее разработанные локально-интерполяционные методы оценивания кривизны оцифрованной кривой, описать законы распределения вероятностей случайных оценок кривизны.
-
Проанализировать на робастность к зашумлению изображений новые и ранее разработанные методы локально-аппроксимативного подхода к оцениванию кривизны, решить задачу выбора оптимальных значений параметров методов, минимизирующих среднюю ошибку.
-
Исследовать на устойчивость к зашумлению векторные представления и описания кривых, разработать методы нахождения наиболее устойчивых к зашумлению векторных представлений, исследовать меры информативности представлений кривых, агрегирующих локальные оценки кривизны.
-
Аксиоматически ввести и исследовать индексы неточности в классах нижних и верхних вероятностей, предложить способы продолжения индексов неточности на множество всех монотонных мер, рассмотреть применения индекса неточности для исследования мер информативности.
-
Рассмотреть решение задачи аппроксимации меры доверия вероятностной мерой, минимизирующей среднеквадратичную невязку, описать множество тех мер доверия, для которых заданная вероятностная мера является ближайшей в среднеквадратичном.
Методы исследования основаны на использовании теории вероятностей, теории неаддитивных мер, теории неточных вероятностей, теории нечетких множеств, функционального анализа, комбинаторики и комбинаторной геометрии, дифференциальной геометрии, численных методов.
Научная новизна. Данная диссертационная работа вносит существенный вклад в исследование качественных характеристик методов выделения низкоуровневых и формирования высокоуровневых признаков на зашумленных изображениях. Введенный класс стохастических аддитивных усредненных мер информативности позволяет ставить и решать задачи нахождения устойчивых к зашумлению представлений оцифрованной кривой. Найденные описания и свойства индексов неточности монотонных мер открывают принципиально новые возможности для оценок априорной информативности недетерминистских систем, а исследованная проблема аппроксимации мер доверия вероятностными мерами позволяет решать задачу компактного описания векторных представлений и ранжирования возможностей появления событий в тех случаях, когда нижние и верхние вероятности не позволяют однозначно решить задачу ранжирования.
В диссертационной работе получены следующие новые результаты:
-
Исследован локально-интерполяционный подход к оцениванию кривизны плоской кривой. Оценены систематическая погрешность, смещение и случайная ошибка оценки кривизны при некоррелированном нормальном зашумлении кривой.
-
Разработан и исследован метод усреднения локально-интерполяционных оценок. Найдены оптимальные значения параметров метода.
-
Исследовано вычисление оценки кривизны с помощью свертки первичных локально-интерполяционных оценок со сглаживающим ядром. Оценены смещение и случайная ошибка оценки кривизны, полученная методом сглаживания локально-интерполяционных оценок. Найдены оптимальные значения параметров метода.
-
Исследован локально-аппроксимативный подход к оцениванию кривизны плоской кривой. Найдены значения систематической и случайной ошибок оценки кривизны, полученной локально-аппроксимативным методом при некоррелированном зашумлении кривой.
-
Разработан и исследован метод геометрического сглаживания как модельный метод неявного локально-аппроксимативного подхода к оцениванию кривизны. Найдены систематические ошибки, смещения и случайные ошибки оценок кривизны, полученных этим методом для различных моделей зашумления кривой.
-
Введен и исследован класс усредненных мер информативности по кривизне. Определена усредненная функция информативности кривой относительно данного локального признака изображения. Исследован класс стохастических аддитивных усредненных мер информативности в случае вероятностного зашумления кривой. Решена задача нахождения полигонального представления кривой, ограниченной мощности, минимизирующего дисперсию стохастической меры информативности.
-
Исследована неаддитивная (монотонная) усредненная стохастическая мера информативности при аддитивном стационарном некоррелированном зашумлении дискретной кривой. Найдены асимптотические выражения для смещения и случайной ошибки стохастической
меры информативности по длине. Поставлена и решена задача нахождения полигонального представления, наиболее устойчивого относительно меры информативности по длине.
-
Поставлена и исследована задача нахождения полигонального представления кривой, состоящего из всех таких точек, информативные признаки которых удовлетворяют определенным нечетким отношениям близости и различия.
-
Оценены величины изменение векторных характеристик представлений и описаний дискретной кривой при изменении информативности контрольных точек. Получены вероятностные оценки изменения центра масс векторного представления кривой, подвергнутой стационарному некоррелированному зашумлению.
-
В рамках исследования степени неточности мер информативности, аксиоматически введены и описаны линейные индексы неточности в классе нижних (верхних) вероятностей. Предложен и исследован один способ продолжения индекса неточности на множество всех монотонных мер. Рассмотрен индекс неточности меры информативности по длине.
-
Решена задача аппроксимации меры доверия вероятностной мерой, минимизирующей среднеквадратичную невязку. Получены различные представления ближайшей вероятностной меры. Показано, что понятие «ближайшей» меры можно использовать для ранжирования возможностей появления событий в тех случаях, когда нижние и верхние вероятности не позволяют однозначно решить задачу ранжирования. Исследованы алгебраические, спектральные и аппроксимативные свойства преобразования, ставящего в соответствие мере доверия ближайшую в среднеквадратичном вероятностную меру.
-
Решена обратная задача вероятностной аппроксимации: найдено множество тех мер доверия, для которых заданная вероятностная мера является ближайшей в среднеквадратичном. Найдено семейство экстремальных точек выпуклого класса ближайших мер доверия и рассмотрены некоторые применения найденных описаний в теории игр.
Практическая ценность работы состоит в использовании найденных качественных характеристик базовых методов и алгоритмов выделения низкоуровневых признаков зашумленных оцифрованных кривых для анализа закономерностей работы алгоритмов в случае разных классов изображений, нахождения оптимальных значений параметров, прогнозирования работы «похожих» алгоритмов или применения алгоритмов для других классов изображений и т.д. Найденные оценки изменения векторных представлений и описаний при изменении информативности контрольных точек могут быть использованы при формировании устойчивых представлений и описаний кривых. Разработанные усредненные, в том числе стохастические меры информативности позволяют организовать вычислительно эффективные процедуры обработки информации, в том числе графической, за счет адекватного моделирования неопределенности. Предложенная аксиоматика и различные описания индекса неточности позволяют оценивать априорную неопределенность недетерминистских систем.
Реализация результатов работы. Некоторые методы и алгоритмы выделения низкоуровневых признаков изображений и формирования векторных представлений были реализованы в макете программного комплекса по обработке изображений. Отдельные положения диссертационной работы внедрены в учебный процесс в Таганрогском технологическом институте Южного федерального университета.
Ряд результатов диссертационной работы получен при выполнении 4-х грантов РФФИ (98-01-00013-а, 07-07-00067-а, 07-07-08036-3, 08-07-00129-а).
Апробация работы. Основные результаты работы докладывались на Всероссийской научно-технической конференции «Интеллектуальные САПР» CAD (п. Дивноморское, 1997, 1998, 2002), на Всероссийской научно-технической конференции с международным участием "Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1999), на VI Международной конференции «Радиолокация, нави-
гация, связь» (Воронеж, 2000), на Всероссийских симпозиумах по прикладной и промышленной математике (1999, 2000, 2001, 2002), на Международной научной конференции «Искусственный интеллект» (п. Кацивели, 2000), на Национальной конференции по искусственному интеллекту с международным участием КИИ (Переславль-Залесский, 2000), на Международной конференции по мягким вычислениям и измерениям SCM (Санкт Петербург, 2000), на Международной конференции «Цифровая обработка сигналов и ее применение» DSPA (Москва, 2000, 2002), на Международном научно-практическом семинара «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2001, 2003), на Международном конгрессе «Искусственный интеллект в XXI веке» (п. Дивноморское, 2001), на I Международном семинаре по мягким методам в вероятности и статистике SMPS (Варшава, 2002), на Международном конгрессе ассоциации нечетких систем IFSA (Турция, 2003), на 11-й Международной конференции по обработке информации и управлению в неопределенных экспертных системах IPMU (Париж, 2006), на Всероссийской научной конференции по нечетким системам и мягким вычислениям НСМВ (Тверь, 2006), на IX Международной конференции "Интеллектуальные системы и компьютерные науки" (Москва, 2006), на восьмой Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные системы» (Донецк, 2007), на 5-м Международном симпозиуме по неточным вероятностям и их применениям ISIPTA (Прага, 2007), на 5-й конференции Европейского сообщества по нечеткой логике и технологиям EUSFLAT (Острава, 2007), на конференции Северо-Американского общества по обработке нечеткой информации NAFIPS (Нью-Йорк, 2008).
Публикации. По теме диссертации опубликованы 42 печатные работы, из них 17 работ - в изданиях рекомендованных ВАК. Кроме того, результаты исследований отражены в 5-ти отчетах о НИР.
Объем и структура работы. Диссертация состоит из введения, пяти тематических глав, заключения, списка литературы и приложений. Общий объем основного текста — 349 стр., включая 19 рисунков и 10 таблиц. Список литературы изложен на 14 стр. и содержит 153 наименования.
Касательная к кривой. Длина кривой
Пусть Г - гладкая кривая, w(s) - ее естественная параметризация. Если P = w(s0) - точка на кривой, то вектор k = w"(.y0), ортогональный вектору w (s0), называют вектором кривизны, а его длину k = к кривизной кривой Г в точке g. Имеют место следующие свойства кривизны. 1) Кривизна кривой во всех точках равна нулю тогда и только тогда, когда кривая является отрезком прямой; 2) Кривизна дуги окружности радиуса R во всех точках равна \/R . Величину, обратную кривизне, называют радиусом кривизны кривой в точке. 3) Если f(t) = x(t)i + y(t)\ - произвольная параметризация кривой Г, то кривизна этой кривой в точке g = f (ґ0) равна И, , _ f fe) х Гfe) \x (t„)y"(t0) - x foMOl (o)= lf ( ! = И.)) +(у( . )Т где x - операция векторного произведения. 4) Если плоская кривая Г задана явно уравнением у = f(x), то ее кри визна в точке g = (xQ,f(x0)) вычисляется по формуле (i + (Ax0))2) 5) Кроме того, в тех точках, где первая производная равна нулю, кри визна равна модулю второй производной: кхоПгы]. ал)
В окрестности любой точки гладкой кривой систему координат можно выбрать таким образом, чтобы кривизна вычислялась по формуле (1.1).
6) Если плоская кривая Г задана явным уравнением г = г(ср) в полярной системе координат, то ее кривизна в точке g = ( р0,г((р0)) будет равна k( pQ) r2(%) + 2(rVo))2-K%K(%) 7\3/2
7) Пусть задана плоская кривая Г. Окружностью кривизны (соприкасающейся окружностью) кривой в точке g(x0,y0) называется предельное положение окружности, проведенной через точку g и две другие точки кривой, когда последние стягиваются к точке g. Радиус окружности кривизны равен радиусу кривизны в точке g, а центр окружности кривизны {г\ентр кривизны) (хг,уг) находится на нормали к кривой, проведенной в точке g в сторону вогнутости кривой. Координаты центра кривизны кривой в точке g = ( 0,/(. 0)), заданной в явном виде у = f(x) равны хг — х0 Л о)(1 + (Л 0))2) » Уг=Яхо) + + (/ ( о))2
8) Пусть w(s) - естественная параметризация плоской гладкой кривой Г и g = w( 0) - точка на Г. Введем функцию наклона 6(s) численно равную углу между положительным направлением оси Ох и вектором w ( ). Тогда (рис. 1.1) Aw O0) = w 0o + As) - w 00) = 2sin(A0(so)/2) = A0(so) + o(A0). Поэтому k(sQ)= lim Дг- Aw (s0) Ay 0 = # 00), e(s0) = jk(a)da Кривизна кривой в точке равна производной функции наклона.
9) Пусть 6(s), k(s) - функция наклона и кривизна плоской гладкой кривой Г соответственно (s - естественный параметр). Тогда координаты x(s), y(s) можно получить по формулам: x(s) = х(0) + Г k(a)cos0(a)da, y(s) - у(0) + \к(а) sin 9 (a) da или в комплексной форме z(s) = z(0)+ \ k(a)Qxp(i0(a))da, где z(0) = х(0) + (у(0) - начальная точка.
Замечание 1.1. В диссертационной работе часто будем рассматривать «кривизну со знаком»: если вращение касательной к кривой происходит против часовой стрелки, то кривизне будем приписывать положительный знак, в противном случае - отрицательный. При явном задании кривой у = f(x) знак кривизны совпадает со знаком второй производной f"(x0).
В В диссертационной работе исследование оценок кривизны будет осуществляться для следующих классов кривых: 1) С, С1, С" (п 2) - классы непрерывных, гладких и регулярных элементарных кривых на плоскости соответственно; 2) Cd - класс дискретных элементарных кривых на плоскости, т.е. таких упорядоченных множеств точек Г = {gj"ri, g = х\ + у J, xs, el, что ломаная с вершинами в r = {gJ"Zl0 - элементарная кривая. Без ограничения общности рассматриваемых в работе задач можно счи тать, что кривые класса Cd являются оцифрованными, т.е. точки этих кривых имеют целочисленные координаты. 3) Cd0) - подкласс класса Cd упорядоченных множеств r = {gi}" , 4) Cc.(j) - класс непрерывных параметризованных плоских оцифрованных кривых Г без самопересечений, заданных функциями g(t) = x(t)i + y(t)j, a t b, и удовлетворяющих для фиксированного конечного разбиения T = {tk}"k=0 отрезка [а,Ь] условиям: а) либо x(t) = const, либо y(t) = const на [tk,tk+l) для всех к; б) x(tk )EZ ДЛЯ всех к; в) Х( к+1) х( к) ( -!) х(!ы) Для всех к г) для любого j є [x(a),x(b)] найдется такое к, что x(tk) = j.диссертации большое внимание уделено исследованию устойчивости информативных признаков кривых к зашумлению. В работе будут рассматриваться только аддитивные вероятностные зашумления. Если кривая Г, заданная параметрической функцией f(t) = x(t)i + y(t)j, tєТ (T - дискретное множество для дискретных кривых, Т = [а,Ь] для непрерывных кривых) подвергнута такому зашумлению, то мы получим случайную кривую Г, заданную функцией F(t) = f(t) + n(t), t є Т, где n(t) = rj(t)i + (t)}, rj(t), %{t) -случайные функции (функции зашумления). Всюду в этой работе будем предполагать, что случайные функции 77(0 и g(t) взаимно не коррелируют друг с другом и имеют нулевые математические ожидания. Выделим некоторые классы таких зашумлений, используемых в диссертации:
1) п(") ЩгІР ) " классы случайных зашумлений вида n(t) = (t)\ и n(t) = 7](t)i + (t)\ соответственно, определенные на кривых класса Cd0) и Cd соответственно, где rj(t), (t) - дискретные стационарные в широком смысле некоррелированные гауссовские случайные функции {дискретный белый гауссовский шум) с постоянной дисперсией о-2;
2) jVcX{K) - классы случайных зашумлений вида n(/) = (Y)j, определенных на кривых класса С, где (/) - интегрируемый стационарный случайный процесс с ковариационной функцией К(т);
3) - /ДО хД О7 ),-) ( л х у)) " класс случайных зашумлений вида n(Y) = rj{t)\ + f (Oj , определенных на кривых класса Cd, где 77(0, (/) - дискретные (стационарные в широком смысле) некоррелированные случайные функции с точечными дисперсиями a2[r/(t)] = J2Xt и y2[ (t)] = cr2l (с постоянными дисперсиями у2х, а2). Если Ух = СГу = сг, то класс таких зашумлений будем обозначать через Аґ {&);
4) И/].ІІ(Т,(О" )І) (/ л)(г ")) класс целочисленных одномерных аддитивных некоррелированных (стационарных в широком смысле) зашумлений вида n(t) = %(t)\, определенных на кривых класса Сс.(т), такой, что если кривая ГєСс.(т) задана функцией f(/), /є[a,b] (T = {tk} l=0 - разбиение отрезка [а,Ь]),то: а) {(і) + 4(і)}єСс.(т) для любой реализации (t) случайной функции (/); б) %{tK), tkGT - некоррелированные случайные величины; в) cr2[(tk)] = о-2 (а2[ к)] = а2) для всех tk є г.
Распределение вероятностей случайной оценки кривизны при некоррелированном нормальном зашумлений кривой
Пусть точечная функция {(я, )} =_ является четной, т.е. y_s = ys для всех s = -т,...,т. Тогда (а(га),у) = 0. Заметим, что если Y = у + , где Ъ, - случайная величина, распределенная по сферическому нормальному закону N(0,a2I), то E[(a(w),Y)] = (а(т),у) = 0. Поэтому в качестве упрощенной оценки кривизны в точки х = 0 для симметричной кривой можно взять величину, равную І2)(У) = ,(0;У) = (b(m),y) = /0 (0)j;0 + 2ХГ=/Г(0)л В этом случае К ] = (b(w),Y). Тогда ЕЙ,] = (Ь(т),у)= С Ь{К) = ЦК]-к=0, [К ] = ст\\Ъ(т)\\. Следовательно, используя результат леммы 1.3, получим 2уІ2сг о[К] 7Г2(7 Другими словами, случайная ошибка будет неуменьшаемой при изменении размера «окна» т. Заметим, что систематическая ошибка оценки k{2) для симметричной кривой класса С2т+3 будет равна 2)-А:(0) = Р2"и(0;у)-/(0)= 1 (0)1, где г2т(х) - погрешность многочлена Лагранжа [63], с є(-т,т). Используя формулу (1.3) для г2"ш(0), получим (т!)2 (2т+\)/\ , і .(2/Н+2). КГ - « ) -Р - /т (с) + сУ (с) . (2т + 1)! Таким образом, если кривая у(х) имеет равномерно ограниченные по области и по т производные, то систематическая ошибка может быть сделана сколь угодно малой при увеличении размера «окна» т. \ \ 1.4. Оценка кривизны методом усреднения локально-интерполяционных оценок
В большинстве алгоритмов для уменьшения влияния отдельных дискретных данных на значение кривизны, осуществляется усреднение первичных оценок кривизны, найденных локально-интерполяционным методом. В этом разделе рассмотрим усреднение первичных оценок кривизны, найденных в одной точке, но для разных значений шагов интерполяции в пределах «окна» размером т. Такие усреднения используются, например, в популярных алгоритмах Freeman и Davis [6], Beus и Тій [7] и других. Исследуем, какими в этом случае будут основные качественные характеристики оценок кривизны в случае нормального некоррелированного зашумления кривой.
Предположим, что известны точечные значения {(л.у )} __ оцифрованной плоской кривой, заданные в "окне" [-т, т]. Рассмотрим следующую схему оценивания кривизны в точке 5 = 0: 1) Для всех 1 = 1,...,т построим интерполяционный многочлен Р,2т(х У) второго порядка, проходящий через точки (s,ys), s = -1,0,1. Найдем оценки кривизны kjll(y) в точке 5 = 0, как кривиз 3/2 ны многочленов PK2m(x\y)\ к%г(у) = / + ( (0;у)) 2) Вычислим а-усредненную оценку кривизны к )(у;а) = " octkf1(y), а = (а1,...,ат), где неотрицательные коэффициенты а,, 1 = \,...,т, -веса усреднения должны удовлетворять условию " %і - 1 Интерполяционный многочлен Рі2т(х У) второго порядка, проходящий через точки (s,ys), s = -1,0,1, можно записать в виде 2т(х У) = Уо+- гХ + г!гХ2, где Ау,=у,-у_І, А2у, = у, - 2у0 + у_,. Тогда Р, 2т(0;у) = Ау1/(21), //ff2m(;y) = AV/A2 и к\Х)т(у)=- ТзІ2- ТепеРЬ в качестве оценки кри (412+(АУі)2у визны в точке х = 0 можно взять линейный функционал от вектора оценок (ОУ)Г=Г У;«)=І; А ) Для простоты исследуем упрощенную оценку кривизны к(2)(у), полученную методом а-усреднения локально-интерполяционных оценок. Пусть точечная функция {(ЛД )} __ является четной, т.е. y_s=ys для всех s = -m,...,m. Тогда Ау,=0, 1 = 1,...,т. Поэтому kj%(y) = Pl";2m(0;y) = Alyl/l2 и Є(у;«) = Е; ЛЇЇ(У) = Е /Д Vа = 2Z - y0)/i2. Оценим систематическую ошибку оценки кривизны 2)(у;а), если известны точечные значения кривой класса С3, заданной явно четной функцией у(х). Тогда точное значение кривизны к = у"(0).
Оценка кривизны методом явной локальной аппроксимации кривой с помощью многочленов Чебышева
В этом подходе точечные значения {g,}" , gs=(xs,ys), параметризованной кривой Г с вектор-функцией g(t) = [x(t),y(t)), -m t m, аппроксимируются некоторой регулярной кривой с вектор-функцией вида р„(0 = (Лл(0»Л(0),где 4 (t) = { f k(t)}"k=0 -линейно независимая на Nm = {-m,-m + \,...,m-l,m} система дважды непрерывно-дифференцируемых на (-т,т) базисных функций. В качестве критерия аппроксимации в этом разделе будем рассматривать среднеквадратичное отклонение _ p„( )-gj Тогда вектор-коэффициенты cw =(c{Qx\...,c\ ))1, с(у) =(с{0у),...,с{пу))Т аппроксимирующей кривой можно найти методом наименьших квадратов. Производные р (0) = [(с( 1;),ф( )(0)),(с( ),ф( )(0))К / = 1,2, аппроксимирующей вектор-функции будут оценками значений соответственно первой и второй производной оцифрованной вектор-функции (gj в точке g0. Так как кривизна к регулярной параметризованной кривой g(t) = (x(t), y(t)) вычисляется по формуле & = g xg"/g , то величину к = р ,(0)хр"(0)/р (0) можно считать m-оценкой кривизны в точке g0, полученной методом локальной аппроксимации кривой.
В частности, если q (O = {0 (O}/U 0 (О = Л! к = 0,...,п, то pj,(0) = с,=(с?\с)Т, / = 1,2,и 43)=Clxc2/c,3.
Заметим, что такой способ вычисления оценок производных эквивалентен нахождению разностных производных по точечным данным, локально сглаженным с помощью многочлена /7-го порядка.
В этом разделе найдем вычислительно эффективные выражения для вычисления m-оценок кривизны, полученной методом локальной аппроксимации. Оценим величины систематической и случайной ошибок, а также смещения оценки кривизны. Найдем оптимальные значения параметров вычисления оценок кривизны таким методом.
Оценка кривизны методом явной локальной аппроксимации кривой с помощью многочленов Чебышева
Для простоты рассмотрим задачу вычисления кривизны и т -оценки кривизны в точке х = 0 кривой класса С2, заданной в явной форме функцией у(х) и удовлетворяющей условию у (0) = 0 (т.е. касательная к кривой в точке х = О параллельна оси Ох). Тогда точное значений кривизны со знаком в начале координат будет равно к = у"(0). Пусть {(s,ys)}"=_ - точечные оцифрованные значения этой кривой. Для нахождения т — оценки кривизны /с 3) в начале координат аппроксимируем эти значения функцией вида п yn{t;c) = (с,ф(0) = Y,ck0k(O, =0 где Ф(О = {0 (О}А=О - линейно независимая на Nm система базисных функций. Вообще говоря, функции фк{і) зависят от т. Если эту зависимость важно подчеркнуть, то будем писать фк2т(,0- Теперь в качестве т-оценки km\ =кт1(у) кривизны оцифрованной кривой {(ЛХ )}"!- точке х = 0 можно взять величину к%1 = у"(0;с) = (с,ф (0)) = 5 =0с Вектор коэффициентов с найдем методом наименьших квадратов, минимизируя функцию среднеквадратичного отклонения т т ( п \ ф(с)= S(У„Ш-У,У = Е ЦСМ -У, s=—m s=—m\k=0 / Имеем 107 т ґ и Л Ф С((с) = 0,/ = 0,...,и = 2 ) ЕСА ( )-Л ,/ = 0,...,и. л=-т VA=0 )
Последняя система равносильна матричному уравнению Ас = b, где Пусть Р[-т,т] - векторное пространство многочленов степени не больше 2т. В Р[-т,т] введем скалярное произведение по формуле: (P,g)o=Y =-mP S(s) (заметим, что (р,р)0 =YJ LmP2(s =:0 = Р так как степень многочленов не больше 2т). Тогда Р[—т,т] - евклидово пространство. Предположим, что Ф(О = {0 (О}А=О " линейно независимая на Nm система многочленов из Р[-т,т]. Тогда матрица А будет симметричной и положительно определенной. Следовательно, будет существовать обратная матрица А \ с = ЛчЬ и к\ = у О; А ]Ъ) = (/T b, p"(0)).
Пусть ?(t) = {фк 2m(t)}"k=Q " ортонормированная система многочленов из Р[-т,т]. Процедура ортонормирования (например, ортогонализация Грамма канонической системы многочленов \,t,...,t") относительно заданного скалярного произведения на множестве Nm однозначно определяет систему многочленов - получим так называемые многочлены Чебышева / k2m(t) (к степень многочлена) дискретного аргумента [67,68]. Отметим некоторые свойства многочленов Чебышева, которые нам понадобятся ниже: 1) фк 2m() = (-1)к фк 2m(t) = 0,1,...,2m. Это свойство означает, что многочлены ф2s(t) (ф25+і(0) содержат только четные (нечетные) степени переменной /. 2) ф2к+х2т (0) = 0, к = 0,1,...,m -1.
Аксиоматика меры информативности дискретной плоской кривой
В работах [40, 41] был аксиоматически введен в рассмотрение новый способ описания полигонального представления кривой посредством так называемых мер информативности. Мера информативности полигонального представления кривой представляет собой функцию множеств, определенную на всех подмножествах вершин полигонального представления, удовлетворяющую условиям нормировки, монотонности (множество из большего числа точек многоугольника имеет большую информативность), инвариантности относительно группы аффинных преобразований плоскости и удаления неинформативных точек. Примерами мер информативности являются нормированные длина ломаной и площадь многоугольника с вершинами в данных точках подмножества. Такие меры информативности называют мерами информативности по длине и площади соответственно. В указанных работах были исследованы алгебраические, геометрические и аналитические свойства мер информативности по длине и площади, поставлены и решены различные оптимизационные задачи нахождения минимального полигонального представления контура с помощью таких мер информативности. Меры информативности по длине и площади связаны с полигональной аппроксимацией кривой.
В этом разделе диссертации продолжено исследование мер информативности контура. В частности, в пункте 3.2.1 рассматривается обобщение введенной ранее меры информативности кривой, в случае кусочной аппроксимации этой кривой другими кривыми из некоторого класса VF.
В пункте 3.2.2 вводится и исследуется класс усредненных мер информативности по кривизне. Причем для построения таких мер используются методы оценки кривизны, исследованные в предыдущих главах. Изучаются свойства мер информативности по кривизне, в ряде случаев находятся эффективные выражения для их вычисления. В зависимости от способа и параметров оценки кривизны мера по кривизне может быть как аддитивной, так и неаддитивной (монотонной). Структура конкретных мер информативности по длине, по площади и кривизне показывает, что их можно рассматривать, как операцию агрегирования низкоуровневых особенностей на изображениях. Обобщая свойства конкретных мер информативности по длине, площади и кривизне, определяется усредненная функция информативности jU(A) = j iu?(g,A)/ ri ra)(g,r), Лє2г, кривой Г относительно данного локального признака w(g,A) изображения.
В пункте 3.2.3 исследуются усредненные меры информативности, у которых признаковые функции удовлетворяют условию co(g,A) - co{g,T) = co(g) для всех gG А и У4Є2Г.В этом случае соответствующая усредненная функция информативности будет аддитивной мерой. Если дискретная кривая r = (gfc) 0 подвергнута вероятностному зашумлению, в результате которого получается случайная кривая r = (GA)" , то признаковые характеристики co(G) = Q(g) будут случайными величинами, также как и значение М( ) усредненной аддитивной меры. Мера М(А) представляет собой иерархическую двухуровневую модель неточности полигонального представления кривой: неточность первого уровня определяется мерой jU, а неточность второго уровня - случайностью признаковых характеристик, от которых зависит мера /и. В этом пункте показано, что М(А) является элементарной ортогональной стохастической мерой, получены вычислительно эффективные формулы нахождения среднего значения и дисперсии такой меры. Кроме того, в этом пункте поставлена и решена задача нахождения для дискретной кривой Г такого полигонального представления В, В к, для которого суммарная дисперсия меры информативности Ел=в2[М(Л)] по всем подмножествам полигонального представления была бы минимальной, а сумма квадратов матема тических ожиданий всех подпредставлений ЕлсвЕ Е ЗДё)] была бы максимальной. Величина суммарной дисперсии характеризует устойчивость полигонального представления и всех его подмножеств к уровню зашумления кривой и зависит также от количества точек в полигональном представлении, а сумма квадратов математических ожиданий - степень информативности этого представления. Для решения указанной задачи вводится функция критерия /(B) = S Bo2[M(/i)]/2:/)cBE2[Eg a(g)]. Таким образом, требуется найти Вє2г, В А:, для которого /(B)— min. Получены вычислительно эффективные выражения для /(В), рассмотрены свойства функции критерия. Оптимальное полигональное представления ищется с помощью процедуры «включение-исключение». Для реализации этой процедуры находится главное значение в приращении / ((В \ g) u h) - /(В), g є В и h є Г \ В .
В пункте 3.2.4 рассматривается усредненная мера информативности ju, когда значения признаков co(g,A) зависят как от самой точки gG А, так и от следующей при обходе кривой точки g+ є А . Примерами таких мер являются меры информативности по длине и по площади. В этом пункте получены формулы для вычисления среднего значения Е[М(Л)] найдено необходимое и достаточное условие монотонности функции множеств Е[М(-)].
В пункте 3.2.5 рассматривается стохастическая мера информативности по длине при аддитивном стационарном некоррелированном нормальном зашумлении дискретной кривой. Получены асимптотические формулы для среднего значения и дисперсии случайной длины стороны зашумленного многоугольника, а также формула для ковариации длин соседних сторон зашумленного многоугольника. С помощью этих формул найдены асимптотические выражения для величины смещения и случайной ошибки стохастической меры информативности по длине. Поставлена и решена задача о нахождении полигонального представления, наиболее устойчивого относительно данной меры информативности.
