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

На правах рукописи

ЛБПСКИЙ Александр Евгеньевич

ВЕРОЯТНОСТНЫЕ И ВОЗМОЖНОСТНЫЕ МОДЕЛИ ОПИСАНИЯ НЕОПРЕДЕЛЕННОСТИ В ЗАДАЧАХ ОБРАБОТКИ И АНАЛИЗА ИЗОБРАЖЕНИЙ

Специальности.

05 13 18-Математическое моделирование,

численные методы и комплексы программ

05 13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Таганрог - 2008

003444975

Работа выполнена в Технологическом институте Южного федерального университета в г Таганроге

Научный консультант

Доктор физико-математических наук, профессор А Н КАРКИЩЕНКО

Официальные оппоненты

Доктор физико-математических наук, профессор А М НАХУШЕВ (НИИ прикладной математики и автоматизации КБНЦ РАН, г Нальчик)

Доктор физико-математических наук, профессор А И. ЧУЛИЧКОВ (Московский государственный университет, г.Москва)

Доктор физико-математических наук, профессор А В ЯЗЕНИН (Тверской государственный университет, г Тверь)

Ведущая организация

Вычислительный цешр им А А Дородницына Российской академии наук

Защита состоится 16 октября 2008 г в 14 часов на заседании диссертационного совета Д 212 208 22 при Южном федеральном университете по адресу 347928, г Таганрог, пер Некрасовский, 44

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу г Ростов-на-Дону, ул Пушкинская, 148

Автореферат разослан «J7_» июля 2008 г

Просим Вас присылать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу 347928, г Таганрог, пер Некрасовский, 44, диссертационный совет Д 212 208 22

Ученый секретарь диссертационного совета, доктор технических наук, профессор

А Н Целых

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Интенсивное развитие за последние 40 лет технических средств регистрации и обработки изображений привело к бурному росту числа методов и алгоритмов обработки и анализа изображений По широте используемого математического аппарата эти методы покрывают практически все разделы современной математики В то же время привлечение разнообразного математического аппарата не всегда сопровождалось качественным анализом разработанных методов и алгоритмов Как правило, при анализе алгоритмов доминировал статистический подход, выбор параметров алгоритмов осуществлялся путем обучения по выборке образов некоторого класса Это не всегда позволяло найти качественные аналитические закономерности работы алгоритмов для разных классов изображений, найти оптимальные значений параметров, спрогнозировать результаты работы «похожих» алгоритмов или применение алгоритмов для других классов изображений и т д Кроме того, одним из ключевых требований, предъявляемых к методам обработки и анализа изображений, является необходимость учитывать высокую степень неопределенности обрабатываемой графической информации, связанной как с действием внешних факторов (аппаратным зашумлением, оцифровкой и квантованием изображений, перекрытием объектов, наличием бликов, теней и т д), так и с необходимостью выделять небольшое число информативных признаков на изображении сложных объектов

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

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

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

0 локальных признаках,

в) нахождение минимальных, информативных, устойчивых к зашумлению векторных представлений и описаний изображений,

г) оценка количества неопределенности в том или ином представлении объектов,

д) ранжирование неопределенностей

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

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

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

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

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

4 Аксиоматически ввести и исследовать индексы неточности в классах нижних I верхних вероятностей, предложить способы продолжения индексов неточности на множе ство всех монотонных мер, рассмотреть применения индекса неточности для исследовани мер информативности

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

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

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

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

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

2 Разработан и исследован метод усреднения локально-интерполяционных оценок На дены оптимальные значения параметров метода

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

4 Исследован локально-аппроксимативный подход к оцениванию кривизны плоской кр1 вой Найдены значения систематической и случайной ошибок оценки кривизны, получе! ной локально-аппроксимативным методом при некоррелированном зашумлении кривой

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

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

7 Исследована неаддитивная (монотонная) усредненная стохастическая мера информати ности при аддитивном стационарном некоррелированном зашумлении дискретной криво Найдены асимптотические выражения для смещения и случайной ошибки стохастическ

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

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

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

10 В рамках исследования степени неточности мер информативности, аксиоматически введены и описаны линейные индексы неточности в классе нижних (верхних) вероятностей Предложен и исследован один способ продолжения индекса неточности на множество всех монотонных мер Рассмотрен индекс неточности меры информативности по длине

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

12 Решена обратная задача вероятностной аппроксимации найдено множество тех мер доверия, для которых заданная вероятностная мера является ближайшей в среднеквадратичном Найдено семейство экстремальных точек выпуклого класса ближайших мер доверия и рассмотрены некоторые применения найденных описаний в теории игр

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

Реализация результатов работы Некоторые методы и алгоритмы выделения низкоуровневых признаков изображений и формирования векторных представлений были реализованы в макете программного комплекса по обработке изображений Отдельные положения диссертационной работы внедрены в учебный процесс в Таганрогском технологическом институте Южного федерального университета

Ряд результатов диссертационной работы получен при выполнении 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 печатные работы, из них 1 работ - в изданиях рекомендованных ВАК Кроме того, результаты исследований отраж ны в 5-ти отчетах о НИР

Объем и структура работы Диссертация состоит из введения, пяти тематич ских глав, заключения, списка литературы и приложений Общий объем основного тек - 349 стр , включая 19 рисунков и 10 таблиц Список литературы изложен на 14 стр и с держит 153 наименования

СОДЕРЖАНИЕ РАБОТЫ

Первая глава диссертации посвящена исследованию локально-интерполяционн оценок кривизны

Если Г гладкая кривая, то ее кривизна k(g) в точке g е Г может быть определи как производная 0's(%) функции наклона 0(g) (угол между касательной и положительнь направлением оси Ох) по длине дуги s

Реально имеется только дискретная кривая Г, выделенная тем или иным методом i оцифрованном изображении Поэтому вместо вычисления кривизны к(g) вычисляют н которую ее оценку ¿E(g), где е - вектор параметров Простейшую оценку можно получи если перейти в определении кривизны от производных к конечным разностям Среди п раметров оценки кривизны одним из важнейших является положительный параметр (б дем обозначать его через s), характеризующий величину окрестности Uc(g) с центром точке g, в пределах которой вычисляется оценка, либо в пределах которой наиболее зн чимы для вычисления оценки точки кривой Зависимость оценки кривизны от параметра будем обозначать через кс(g)

Любая е-оценка кривизны kt{g) оцифрованной кривой Г в точке g характеризует некоторыми качественными величинами Одной из важнейших качественных величин я ляется разность st = \kt - , называемая систематической ошибкой и характеризующ 6

величину отклонения оценки от точного значения Будем считать, что систематическая ошибка обусловлена только неточностью метода вычисления оценки Если рассматривать зависимость систематической ошибки от величины £ - окрестности вычисления оценки, то потребуем, чтобы выполнялось условие 1) для гладкой кривой lim s,(g) = 0 Кроме того, как правило, изображение, на котором выделяется кривая, является зашумленным Характер неточности зашумления может быть разным Ниже будем считать, что неточность имеет аддитивный вероятностный характер Тогда оценка кривизны будет случайной величиной Kt(g), которая качественно характеризуется величиной смещения bt = |E[A"J-it|, где Е[] - оператор математического ожидания, и величиной случайной ошибки (дисперсии) o2[^J Потребуем, чтобы для случайной оценки кривизны Kt{g) также выполнялись условия 2) lim|E[ATА-к.1 = 0, 3) lima2 ГК 1 = 0, которые назовем условиями устойчивости оценки кривизны к зашумлению изображе1шя Если <s2yKt\ = 0{£~a), |Е[Kt]-kt\ = 0(s'p), то величина min{a/2,/?} определяет порядок устойчивости оценки кривизны

Можно выделить два основных подхода к вычислению оценок функции кривизны В первом подходе вычисление оценки кривизны оцифрованной кривой Г в точке g е Г осуществляется в два этапа Сначала с помощью разностного оператора кривизны находятся первичные оценки в некоторых точках кривой из е -окрестности с центром в точке g Затем осуществляется усреднение (сглаживание) полученных первичных оценок Во втором подходе осуществляется гладкая аппроксимация дискретной кривой Г, после чего вычисляется кривизна гладкой аппроксимирующей кривой в исследуемой точке Вычисление оценки кривизны только с помощью разностных операторов практически не применяется, поскольку такая оценка будет очень чувствительной к значениям отдельных данных Для того чтобы уменьшить эту чувствительность осуществляют усреднение (сглаживание) полученных в пределах е -окрестности первичных оценок кривизны Из всего многообразия процедур усреднения (сглаживания) можно выделить два основных способа В первом случае вычисляются первичные оценки кривизны в одной точке g, но с разными шагами интерполяции в пределах е -окрестности, после чего осуществляется усреднение полученных оценок В другом способе сглаживаются первичные оценки кривизны, вычисленные в разных точках е -окрестности Такую схему сглаживания можно реализовать с помощью интегрального оператора свертки разностных оценок кривизны и некоторого сглаживающего ядра В качестве сглаживающих ядер чаще всего используется постоянное ядро (равномерное усреднение) или ядро Гаусса Математической основой построения сглаживающего оператора является известное в теории приближений усреднение функций по Соболеву Применение оператора сглаживания для выделения низкоуровневых признаков на изображении впервые было тспользовано J Canny при построения детектора края Позднее методика Canny была применена для вычисления оценок кривизны Для того чтобы различать два указанных способа усреднения, первый способ будем называть собственно усреднением, а второй - сглаживанием

Для «хороших» оценок и правильно найденных значений параметров все три качественные характеристики-критерии (смещение, систематическая и случайная ошибки) должны быть небольшими Задача нахождения векторного параметра е, при котором минимизируются несколько критериев, является многокритериальной задачей Один из путей решения такой задачи - минимизировать «свертку» критериев, например, их сумму или минимизировать так называемую среднеквадратичную ошибку s\ + b\ + a2 [ATt]

Таким образом, для заданного метода вычисления оценки кривизны возникают следующие задачи

а) найти значения (или оценки) трех качественных характеристик оценок кривизны,

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

в) найти оптимальное значение векторного параметра е , минимизирующего среднеквадратичную ошибку

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

В разделе 1 3 исследуются оценки кривизны, полученные методом локальной ин терполяции оцифрованной кривой Пусть плоская элементарная кривая Г задана в явно\ виде функцией у = у(х) и рассматривается в пределах некоторого «т-окна» начала коор динат -т<х<т Если кривая Г является регулярной, то ее кривизна вычисляется п формуле к = у"(0)/(1 + (У(О))2)3'2 На самом деле мы имеем дискретную кривую В раздет 13 рассматривается дискретная кривая ГеС^0), заданная в "окне" [~т,т], те Г = Г„ = . Кривизна оценивается в точке 5 = 0 Простейший способ это сделат

- построить интерполяционный многочлен, проходящий через точки {(5, у,то ест

осуществить локальную интерполяцию оцифрованной кривой Оценкой кривизны к™ то гда можно считать кривизну интерполяционного многочлена в данной точке Такой подхо был реализован, например, в алгоритме Веппе! и МасБопаИ Интерполирование окружно стью рассматрвиалось в алгоритме СЬе^епкоу и БгаЬо Кроме того, во многих детектор углов и алгоритмах сегментации кривых используется так называемая мера расстояни между хордой и стягиваемой ее дугой кривой В главе 1 показано, что эта мера связана радиусом интерполирующей окружности Поэтому все методы детекции углов и сегмент ции кривых, основанные на вычислении этой меры, можно отнести к методам первог подхода В частности, мера расстояния между хордой и стягиваемой ее дугой использов лась в таких популярных алгоритмах, как в алгоритме Оои§1аз-Реискег, алгоритм 11Шкож5к1 и 11озепГеЫ, в алгоритме 11атег и др

Рассмотрим интерполяционный многочлен Лагранжа Р2т(х^У) = ' ПР

ходящий через точки {(«»У,)}".„» У = (л)> гДе Цх)= и)(х ~ 'Ч5 ~ 0 изна

означает, что в указанном произведении пропущен множитель при / = 5 Тогд = = -Р2"т(0,у)(1 + (^,(0,у))2)"У2 =(Ь(т),у)(1 + (а(т),у)2)"Э/2 - оценка кривизнь где а = а (и) = (Г „(О), /я(0)). Ь = Ь (и) = (Г„(0), ,£(<)))

Для систематической ошибки оценки кривизны кривой у(х) класса С:"+| имее КГ-^О^^^КО^^'И+^У2-^^), ф)е(-т,т) и Ы<||Ь(т)||||у|| |У;"""(с) + с'уа""2)(с)\ В частности, если координаты вектора у значений оцифр ванной кривой равномерно по т ограничены, а кривая у(х) имеет равномерно ограниче ные по области и по от производные, то систематическая ошибка не больше, чем мал 0(4"™)

Предположим теперь, что точечные значения {(^У,)}™ _„, кривой подвергнуты адд тивному некоррелированному стационарному нормальному зашумлению Щ^а), т е им 8

V

ОН"-»-!)" "

ется последовательность )}"_„> где У = (У_т, ,Ут) - вектор нормально распределенных некоррелированных случайных величин У1=у,+£1, ЛЧ0,сг2), $ = -т, Тогда оценка кривизны

у) = С(У) = (Ь(и),¥)(1 + (а(т), У)2)"*2 (1)

- случайная величина Пусть у(0) - проекция вектора V е Я2"*' на Я2"

Теорема 1.1. Плотность распределения вероятностей случайной величины К™ при зашумлении Щ,(сг) равна

^<„0,У) = р^ { (1 + (а<0),у(0))2)' ехрVе0' -у(0))2

где ^(у<0,,0 = + (а<0), у(0))2)' -(Ь<°>,у'0»))

Смещение и случайная ошибка оценки кривизны найдены для т-локально четной точечной функции {(5,^,)}™ „> те У-, = У, Для всех з = ~т, ,т Так как = -а1 и ¿>_, = Ъ,, то в этом случае (а,у) = 0 и к^ = (Ь,у) = /о"(0)уо + 2^ " ,С(0)у,

Теорема 1.2 .Для смещения Ь(К^) случайной оценки кривизны т-локально четной функции, полученной методом локального интерполирования по формуле (1) при зашумлении Щ^а), справедливо неравенство

1||а||2 <т2|^|тах{о,1 -Щ\*\? а2} * |«)|

\

Следствие 1.2. При тех же условиях и а -> 0 имеем

Последняя теорема и следствие показывают, что смещение оценки к^ мало зависит от размера «окна» т и является малой одного порядка с дисперсией зашумления

Теорема 1.3. Для случайной ошибки оценки кривизны (I), полученной методом локальной интерполяции т-локально четной оцифрованной кривой при зашумлении Щ^о) справедливо неравенство

Таким образом, можно сделать следующие выводы при некоррелированном нормальном зашумлении оцифрованной кривой оценка случайной кривизны к™, полученная методом интерполирования в «окне» [~т,т], имеет 1) систематическую ошибку, которая может быть сколь угодно уменьшена при увеличении размера окна т, 2) смещение, которое мало зависит от размера «окна» т и является малой одного порядка с дисперсией зашумления, 3) случайную ошибку, которая не может быть уменьшена при увеличении размера окна т

В разделе 1 4 рассматривается усреднение первичных оценок кривизны, найденных в одной точке, но для разных значений шагов интерполяции в пределах «окна» размером т Предположим, что известны точечные значения {(^.У,)}" оцифрованной плоской кривой, заданные в "окне" [~т,т\ Рассмотрим следующую схему оценивания кривизны в точке .5 = 0

1) Для всех 1 = 1, ,т построим интерполяционный многочлен Р, 2„(х,у) второго порядк проходящий через точки О,у,), s = -1,0,1 Найдем оценки кривизны к,'1(у) в точке s = О как кривизны многочленов Р12„(х,у)

2) Вычислим а-усредненную оценку кривизны = а,к}'*(у), а = (а,, ,а„),гд неотрицательные коэффициенты а,, 1-1, ,т, - веса усреднения должны удовлетворят условию = 1

Такое усреднение использовалось, например, в алгоритмах Freeman и Davis, Beus Tiu Для простоты исследуется упрощенная оценка кривизны у), полученная методо

а-усреднения локально-интерполяционных оценок Пусть точечная функция {(лу,)}™_ является т-локально четной, те у_,=у, для всех s = -m, ,т Тогда Ау, =0, 1 = 1, ,п Поэтому к™(у) = /Г2ш(0,у) = А2у,//2 и ^>(y,o) = £,>А-(У) = Zm^V'2 Тог систематическая ошибка будет равна s(Ä£2')= х* е[0,м], и не мож

быть сколь угодно уменьшена Предположим, что точечные значения у подвергнуты дитивному сферическому нормальному зашумлению Y = y+с, где 1; ~ /У(0,ст2/

Тогда оценка кривизны, полученная методом усреднения локально-интерполяционнь

оценок будет случайной величиной К™ и а2 [К'*1] = 4а1

В ч

стности, при равномерном усреднении (те а,=1/т для всех 1 = 1, ,т) имее с2[К^}< 7я-4сг2Д45(ги + 1)2) и, таким образом, случайная ошибка является уменьшаем

при увеличении размера окна т В случае равномерного усреднения рассматривается з дача о нахождении оптимального размера окна т, при котором среднеквадратичн ошибка 5(/я) = з2 о2[Х^2>] будет наименьшей Оптимальное значение тар1 разме

фа\у"(х)\~

окна должно удовлетворять условию

-1, при эт

3(т„р,)= 5« л"!о"|>'"(х')| Предлагается процедура уточнения размера «окна» т при вычи

лении оценки кривизны методом усреднения локально-интерполяционных оценок

В случае произвольного а -усреднения рассматривается задача о нахождении тако оптимального весового вектора а, при котором среднеквадратичная ошиб 5(а) = л2 (^2,(у,а)) + о2[^,2)(у,а)] будет наименьшей Тогда 5"(а) = 4сг25(а), где

5(а)=г2(х>,/)2+[е:,^2)2]> г=

Теорема 1.4, Вектор весовых коэффициентов а, минимизирующий среднеквадр тичную ошибку 52 (^,2>(У>а)) + ст2[^12>(У>а)] является точкой минимума квадратичн

функции §(а) в симплексе а, > 0, / = 1, ,т, «/ = 1

Таким образом, можно сделать следующие выводы при некоррелированном но мальном зашумлении оцифрованной кривой оценка кривизны у), полученная метод усреднения локально-интерполяционных оценок в «окне» [-т,т], имеет 1) систем

тическую ошибку = + которая не может быть сколь угодно умень-

шена при изменении размера окна т, 2) случайную ошибку о2[К(т2)]< 7л'а2/(45т2), которая может быть сколь угодно уменьшена при увеличении размера окна т (порядок устойчивости - не меньше 1), 3) оптимальный размер окна (в общем случае, оптимальные весовые коэффициенты), при котором среднеквадратичная ошибка вычисления оценки кривизны будет наименьшей

В разделе 1 5 рассматривается вычисление оценок кривизны методом аналитического сглаживания первичных локально-интерполяционных оценок Такой подход был предложен Canny для выделения краев на изображении В качестве оценки ifce(g) кривизны плоской оцифрованной кривой Г в точке g используется результат ^-усреднения (по Соболеву) самой функции кривизны к(g) (или ее оценки, полученной тем или иным методом) с помощью интегрального оператора свертки

Ш== to, * *Х0=(<рс * № = to'. * 0)(g)=,

где срс - некоторое ядро усреднения, 0(g) - угол между касательной и положительным направлением оси Ох, в[(g) - производная функции наклона 0(g) по длине дуги s Пусть (г,),:,,1 - некоторое разбиение отрезка [t-s,t + е] д.[О,L] (L - длина кривой Г), Дгг - i-й шаг разбиения, k(rt) - дискретная функция локально-интерполяционных оценок кривизны вточках г,, ¡ = 0,1, ,л-1 Будем считать, что к(т1) = -^(в(т,^)-§(т,)},гд,е б(г,) -оценки функции наклона в точках т, Выполним е-усреднение функции к - получим оценку

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

Теорема 1 5. Для систематической ошибки аналитического е - сглаживания первичных оценок кривизны верна оценка

= |*,(0 - *(0| S С, +£С,(*,Г) + С3(е ,Г)(* у ,£> 0,

где q - порядок точности численного интегрирования, п - число точек разбиения, С,(г,Г), ¡ = 1,2,3, -ограниченные сверху по е константы В частности, если п = 0{\j г2), то sc = | kc(t) - k(t) | < С (с, Г)£, е > 0, где константа С(е, Г) ограничена сверху по £

Пусть Г - плоская кривая, имеющая естественную параметризацию w(t) = x{t)i+y(t)i Рассмотрим дискретизацию Td этой кривой Vd = (w(/t))^, w(;4) = x,i + yj Предположим, что дискретная кривая Г^ подвергнута аддитивному сферическому нормальному зашумлению Wd, (сг) вида Y = у + 4, где \ ~ N(0, сг2/) Тогда аналитическое е-сглаживание локально-интерполяционных оценок к кривизны к кривой Г в точке g = w(r) будет случайной величиной, которую обозначим через Кс В случае вероятностного зашумления кривой для тех индексов г = 0,1, ,п-1, для которых Дх, * 0, первичные оценки функции наклона будут случайными величинами 0(, а £- сглаживание локально-интерполяционных оценок - случайной величиной Ке = , где

Лемма 1.8 Плотность распределения случайной величины 0, = arctg{(Y^-Y,)lbx), дг,*0, N(y„a-2), / = 0,1, ,и-1, равна

Теорема 1.6. Смещение случайной величины Кс = ^"^'сД^)©, £-сглаживания локально-интерполяционных оценок при зашумлении Л^Дет) равно

b(Kc) = -2<72Y^to^c,(£)sm в, cos3 3,+R, где |*| S, ^^Jc/*)^)3

Лемма 1.11. Плотность распределения системы случайных величин (0,,©^,), 0, = arctg((Yltl - У,)/Ах,), Ах,ф0,Y,~ Щу„а2), равна

Ч = 1°ф(-1^д(АУ. -Ax;g,,A^„-AxltlrgO), -f < s,t < f,

где B(u,v) = u2 + uv + v2

Теорема 1.7. Случайная ошибка величины Кс = s-сглаживания ло

кально-интерполяционных оценок при зашумлении И£,(<т) равна

Дх, *0 '

где Ъ,(е) = ^cos29„i = 0,1, ,л-1, ¿>ч(е) = 6„(г) = 0,причем Н = 0(<т4)

Если с('*)1«о " РавномеРное разбиение отрезка [i-£\i + £], Дг, = 2е/п, т Дг, = -х: = (2etgat)/n, tga, = (x,tl -х,)/Дг, и справедливо следствие

Следствие 1.4. Яр« указанных условиях случайная ошибка величины Кс аналитиче ского е-сглаживания локально-интерполяционных оценок в случае зашумления ^,(ст

равна о2[Кс] = С5(¿г,Г)+ Н, где |#| < С5 (s, Г)ы константы С5(с,Г), С5(г,Г) ограничены по е

Таким образом, можно сделать следующие выводы при некоррелированном нор мальном зашумлении оцифрованной кривой Г оценка кривизны kc(t), полученная мето дом аналитического е - сглаживания локально-интерполяционных оценок в окн [t-e,t + г], имеет 1) систематическую ошибку, которая может быть сделана сколь угоди малой с уменьшением s, 2) смещение и случайную ошибку, которые можно уменьшить з счет увеличения размера окна е или за счет уменьшения числа локально интерполяционных оценок л, 3) оптимальные значения размера сглаживающего окна е числа первичных оценок кривизны п, при которых суммарная ошибка вычисления оценк кривизны методом аналитического сглаживания будет наименьшей

Во второй главе диссертации исследуется локально-аппроксимативный подход вычислению оценок кривизны В этом случае оператор вычисления оценки кривизны С определенный на множестве всех оцифрованных кривых Cd(Z2) имеет вид С = С° А, гд A C\(Z2)—>C,(R1) - некоторый оператор гладкой аппроксимации дискретной кривой окрестности той точки, в которой кривизна оценивается, С - оператор вычисления кри визны, заданный на множестве гладких кривых С'(Л2) Аппроксимация может быть явно и неявной В явной аппроксимации в качестве аппроксимирующей кривой чаще всего и пользуются алгебраические кривые Явная аппроксимация рассматривалась в алгоритм

Lee, Haralick и Deguchi, в алгоритмах Tsai и Chen, Mokhtarian и Mackworth, Peí и Lin, Ratta-rangsi и Chin

При неявной аппроксимации аппроксимирующая функция А ищется в виде Л = L'g о Lz, где Lr (Lz) - оператор, определенный на множестве всех гладких кривых C'(R2) (оцифрованных кривых Cd(Z2)), ставящий в соответствие кривой Г некоторую (вообще говоря, векторную) характеристику q(r) Характеристика q должна быть определенной и для гладких и для цифровых кривых Такая схема аппроксимации была применена в детекторе Харриса, где оценки кривизны вычислялись по изменению интенсивности функции изображения в четырех перпендикулярных направлениях в пределах некоторой окрестности (то есть в качестве характеристики q(r) рассматривался вектор изменения интенсивностей в разных направлениях полутонового изображения, содержащего кривую) Аналогичный подход используется в ряде алгоритмов по активным контурам

В разделе 2 2 исследуются оценки кривизны, найденные методом явной локальной

аппроксимации кривой В этом подходе точечные значения {g,}™ , g, = (х,,У,), параметризованной кривой Г с вектор-функцией g(') = (*(')> у('))> -т < t <, т, аппроксимируются некоторой регулярной кривой с вектор-функцией вида р„(/) = (x„(í),>'„(0)> гДе

Х.0) = x.(f, с">) = (cw,<p(/)) = ±c\%(t), у St) = y.(t, с(») = (cw,<p(0) = £c\%{t),

ЫО t-0

{Фк 2т('))м " линейно независимая на Nm = {-т, ,т} система дважды непрерывно-дифференцируемых на (-т,т) базисных функций В качестве критерия аппроксимации в

этом разделе будем рассматривать среднеквадратичное отклонение J|p„(s)-gJ . Тогда вектор-коэффициенты с'" = (с<*>, ,с<")г, c(v) ,с[у))Т аппроксимирующей кривой можно найти методом наименьших квадратов Производные = ((cw,q>w(0)), (с(у',фс,)(0))), ' = 1,2, аппроксимирующей вектор-функции будут оценками значений соответственно первой и второй производной оцифрованной вектор-функции {g,}™ _я в точке g0 Так как кривизна к регулярной параметризованной кривой

g(t)-(x(t),y(tj) вычисляется по формуле к = |g'xg"|/|g'|', то величину

^я1 =|Ря(0)хРл(0)|/|р'„(0)|3 можно считать m-оценкой кривизны в точке g0, полученной методом локальной аппроксимации кривой Для простоты рассматривается задача вычисления кривизны и m - оценки кривизны в точке х = 0 кривой класса С2, заданной в явной форме функцией у(х) и удовлетворяющей условию /(0) = 0 (т е касательная к кривой в точке х = 0 параллельна оси Ох) Тогда точное значений кривизны со знаком в начале координат будет равно к = У(0) Пусть {(^Л)}^,,, - точечные оцифрованные значения этой кривой Для нахождения «-оценки кривизны к¡¡} в начале координат аппроксимируем эти значения функцией вида >'„(',c) = (c,q»(í)) = ^¡_0c,^,(f), где {фк 2|Я(')}*=о ■ линейно независимая на Nm система базисных функций Теперь в качестве m-оценки у) кривизны оцифрованной кривой {(•s,>'1)}™_ m в точке х = 0 можно взять величину

к£'„ =yZ(0,c) = (c,<p"(0)) = £^ct$(0) Вектор коэффициентов с найдем методом наименьших квадратов, минимизируя функцию среднеквадратичного отклонения Тогда с бу-

дет решением матричного уравнения Лс = Ь, где А = (а1к)"4ш0, ал = __тФ,(8)ФЛ5)• ф£з)у, Если {фк2Л')}1.о - система многочленов Чебышева, те ортонормиро-ванная система евклидова пространства Р\-т,т\ многочленов степени не больше 2т с скалярным произведением = ^¡^.„Р^Е^), то с = А 'Ь и = (Л~'Ь,ф"(0)) Тогд

= 2* " оценка кривизны

Предложение 2.1. Максимальное значение систематической ошибки вычислен т—оценки кривизны кривой, задаваемой многочленом степени I, п<1<, 2т, методом по кальной аппроксимации с помощью ортонормированной системы многочленов {фк1т^Ж„о

Раено =||уИ|^^/2]+1(&2лД0))2

Предположим, что точечные значения {(¿.Х,)}^ „, кривой подвергнуты некоррели рованному стационарному гауссовскому зашумлению УЦ^а), т.е имеется последователь ность где У = - вектор нормально распределенных независимы

случайных величин = у, + , ~ N(0,а2), 5 = -т, ,т Тогд

= X"2.(0) - случайная оценка кривизны Теорема 2.1. Случайная ошибка вычисления т- оценки кривизны регулярно кривой на плоскости методом локальной аппроксимации с помощью ортонормированно системы многочленов {фцт(*)Уы пРи зашумлении УЦц{а) равн

Ак^а^ХФ^т)2

Следствие 2.1. Наименьшая ненулевая случайная ошибка вычисления т-оценк кривизны регулярной кривой на плоскости методом локальной аппроксимации многочл нами степени не больше 2т при зашумлении УЦ^сг) будет равн

о2[АГ'3:I] =-ШяЦ-

В этом же разделе решается задача нахождения оптимальных значений параметре метода локальной аппроксимации В целом относительно вычисления оценок кривизн методом явной локальной аппроксимации, можно сделать следующие выводы При неко релированном нормальном зашумлении оцифрованной кривой оценка кривизны к^\у имеет 1) систематическую ошибку, которая может быть уменьшена при уменьшении р мера окна т, 2) случайную ошибку, которая может быть сколь угодно уменьшена пр увеличении размера окна т Порядок устойчивости оценки кривизны - 2 5

В разделе 2 2 кривизна оценивается методом неявной локальной аппроксимаци оцифрованной кривой Ниже часто будем использовать понятие нормированной оценк кривизны Пусть кГ = - кривизна гладкой кривой Г в точке g

Определение 2.1. Функцию = ^(§). зависящую от параметра е > 0, будем н зывать нормированной е-оценкой кривизны (е-весом) кривой в точке g, если онаудо летворяет условиям l)Q<v <\ для любого £->0, 2) кт у' (%)/е = С\к1 для гладк

£-> I I

кривой Г, где С > 0 - некоторая константа, не зависящая от точки g

Тогда г-оценкой кривизны кривой в точке g будет функция кс(%) = С Заметим, что иногда удобнее, чтобы вместо условий 1) и 2) вес удовлетворял условия

1') -1 ^ v, ^ I для любого е > 0, 2') lim vUg)/e = Скг(g) для гладкой кривой Г Такое определение веса будет соответствовать вычислению оценки кривизны «со знаком»

Пусть р - некоторая метрика в Z2 Зафиксируем точку g(i0,J0) е Г и рассмотрим е -окрестность f/£(g) = {(j,/t) p(s-i0,k- j0) S г}, причем величина е > 0 такая, что кривая Г пересекает окружность ôUe(g) ровно в двух точках Через /лс{%) и /7£(g) обозначим площади областей, расположенных по разные стороны от кривой Г в пределах окрестности Uc(g), а через S^g) площадь окрестности t/£(g) Рассмотрим две нормированные разности площадей pc(g) и /7£(g) a) v'1)(g) = |//£(g)-/7i(g)|/max{iu£(g),^£(g)}, 6)v™(g) = |l-2//£(g)/5'£(g)| Будем называть вес v£2) и соответствующую оценку кривизны к[2] линейными, а вес v£° и оценку к{р нелинейными Показано, что выбор функций v£" и v[2) не случаен, так как они обеспечивают минимум функционала дисперсии функции случайной величины F(çj) = в2 j^j-^-- l|)J для точек высокой и низкой кривизны соответственно и

некоторого класса функций <р(1), 0 < t < 1, удовлетворяющих условиям а) 0 < ç(t) < 1, б) <р(0) = 0, ç)(l) = 1 Здесь М£ - случайная площадь, ограниченная зашумленной кривой

Теорема 2.2 В случае вычисления нормированной оценки кривизны в точке g е Г е С3 в евклидовой метрике верно равенство v£'(g) = + о(е), s —> 0

Таким образом, k(cn(g) = - оценка кривизны

Следствие 2.3. Для систематической ошибки вычисления оценки кривизны klJ\g) в точке g g Г б С3 справедливо неравенство |i(g) - 1 (g)| < -Щ-р k2 (g)e + o(e), где q = -¿7max||i"(^)| < arcsin(£'/r)j, з(ф) - функция почярногоуравнения кривой в окрестности точки g

Аналогичные результаты получены для веса v'2)(g) и оценки ki2)(g), а также - в случае вычисления веса и оценки кривизны в равномерной метрике

Предположим, что дискретная плоская кривая без самопересечений Г = (gt , g к ~хк1 + Ук1> подвергнута вероятностному зашумлению -/VJ2((crXJ)l,(ijy г)г} В результате получим случайную кривую f = (Gt)^, G, = Xti + Yki, где Xk=xk+ijk, Yk = y k+4k, цк, - случайные некоррелированные величины, причем Щт]к] = ] = 0, <s2[r/t ] = cr2t,

Пусть D(T) - область, ограниченная замкнутой ломаной без самопересечений с вершинами в точках g0 = g„, дискретной кривой Г, a p{D{T)) - площадь области D(f) В работе оценена случайная ошибка линейного веса V'2) и линейной оценки кривизны К12) в равномерной метрике Пусть /Jc(gs) = ^(D(T)nUt(gs)) Обозначим через r£J(0 = {£,, ,ks} те индексы к, для которых gt е Us(gs ) Относительно соотношений между величиной е и значениями точечных дисперсий а]к и а\к предполагается выполнение условий 1)/3||г£ДГ)Дг££(Г)|>о| = 0 (Д - симметрическая разность множеств), 2) почти наверное Г не имеет самопересечений

Предложение 2.5. Пусть плоская дискретная кривая Г подвергнута зашумлению 2((°«,f)<>гX)• причем параметры этого зашумления, точка gs и £>0 удовлетворяют условиям 1), 2) Тогда почти наверное выполняются равенства

1) Е[Л(С,)] = л,(В.). 2) 02[Я(С,)] = £2(<(1 +<, + + + +

Следствие 2.8. Если выполняются условия предложения, то для зашумления Л//,'(с) такого, что 3<|г4ДГ)| < 2г/сг, Д2 £, <4г2, почти наверное спра-

ведлива оценка а2 [/¡£(СЛ)] < 18£2<т2 + еа}

Следствие 2.10. Если выполняются условия предложения, то для случайной ошибки вычисления оценки кривизны и зашумления J/fl (с) почти наверное справедлива оценка

В разделе 2 3 рассматривается также класс Сс1(г) непрерывных параметризованных плоских оцифрованных кривых Г без самопересечений, заданных функциями g(i)= x(/)i+y(0j. a<t<b, и удовлетворяющих для фиксированного конечно! разбиения r = {tk}ks0 отрезка [а,Ь] условиям 1)либо х(г) = const, либо у(/)~ const н [ft,i,+1) для всех к, 2) x(tk)zZ для всех к, 3) x(fH1)>x(i4), х(г4_,)*х(г4+1) для всех к 4) для любого j e[x(a),x(i>)] найдется такое к, что x(lk) = j

Пусть Л^,(г,(а4)4) ((г, сг)) - класс целочисленных одномерных аддитивны некоррелированных (стационарных в широком смысле) зашумлений вида n(i) = £(0j> on ределенных на кривых класса Сс.(т), такой, что если кривая Г е Сс2(г) задана функцие! g(0, te[a,b] (т = {tk- разбиение отрезка [а,6]), то a) g(0 + ?(0je Ссг(г) для любо реализации £(г) случайной функции £(/), б) %(tk), 1,бг- некоррелированные случайны величины, в) o2[^(tk)\ = а] (сг2[£(/4)] = сг2) для всех (,€г

В разделе 2 3 рассматривается вычисление веса и кривизны в равномерной метрике Без ограничения общности можно предположить, что кривая Г проходит через начало ко ординат, а вес и кривизна рассматриваются в точке о - начале координат Тогда можн считать, что существует tke т x(tk) = 0, y(tk) = 0 и y(tk) = 0 для любой реализации (т е все реализации случайной кривой проходят через начало координат) Рассмотрим т-ок рестность начала координат (те Z) в равномерной метрике - квадра Um =Utl(o) = l~m,m]2 Будем считать, что (x(t) a<,t<b} = \-m,m\ Пуст gk =y(mm(x"'(i))), Gk = F(mm(i"'(i))), crt2=a2[Gt] Тогда Gk - независимые случайны величины В силу условия а) для зашумления Ж:](г,(ак)к) следует, что случайные вели чины Gk могут принимать только целочисленные значения gk, gk ± 1, , gk ±1 с вероят

ностями Ро\ pi\\ , соответственно C£l3r__lp\l) = Ь Р^Р = > 5 = 1,2, .,/

к = -т ,т, где I - размах зашумления) Тогда E[6't] = gt и =<r2[GJ] = 2^'i=|52p'') к = -т ,т Если вероятностные распределения зашумлений во всех пикселях одинаков те Р',к) ~ Ps > s = 1,2, ,1 для всех к = -т, ,т (такое целочисленное одномерное зашум ление назовем однородным), то о1 [G] = _ls2ps Через D" ={(х,у) х - x(t)

у й у(0>а - обозначим область, расположенную с одной стороны от кривой в

пределах окрестности 11 т Пусть //„(>>) - площадь области £>™, а размер т "окна" £/ш удовлетворяет условию тш Такое "окно" будем называть "большим" Тогда

случайная величина /¿„(Г) может принимать целые значения /лт(у)±г, г = О, ,1(2т-\), с вероятностями = „.у»-, П" „'"У,"

Предложение 2.7 Случайная ошибка вычисления веса У^2) в случае зашумления Л/~., (г,(ст4) будет равна а2 = & частности, для стационарного за-

шумления Л/^'^сг) имеем о2^"']13-^

Следствие 2.11 При тех же предположениях я2[^12)] = ^ част-

ности, для стационарного зашумления У1/"/,0' (г, сг) о2 [] = .

Теорема 2.4. Пусть кривая ГеСсДг) подвергнута зашумлению ,(гДо"»)*) и >И Тогда ^ где С,(/г) = -^ В случае стационарного

зашумления /^¡"(г.сг) имеем |у^-Е[^|)]|<^тС,(А)сг, где сг2 =2^[ к2рк

Следствие 2.12. При тех же предположениях для смещения вычисления оценки случайной кривизны АГ^' справедливо неравенство < ^-С,(/г)а[^т(]/)] В случае

зашумления Ж™(т,а) имеем <

Если оцениваемая кривизна является достаточно большой, то справедливы более сильные оценки Пусть = —-р-

Теорема 2.5. Если кривая ГеСс_(г) подвергнута зашумлению Л/1,(гДсг^) и то < где С2(/г) = и^г В случае зашумления

Следствие 2.13. При тех же предположениях для смещения вычисления оценки случайной кривизны справедливо неравенство |^>-Е[^,)Л<-^гС2(/1)о'2[//Л1(Г)] В случае зашумления имеем -Е^"] < -Е[^"]| < £С2(И)ст2

Следствие 2.15 Если у^1 > Л >тах{А(/,и1),/г0}, то справедлива оценка

Теорема 2.6 Пусть кривая ГеСг .(г) подвергнута зашумлению , (г,(сг();) и у!»>Ъ>Щ,т) Тогда <у2[С]<^[А,(Г)](с,(/г)- (Г)]), =

Следствие 2 16. При тех же предположениях и у'," > И > Ы1,т) верно неравенство

Следствие 2.17. При тех же предположениях и к > 1г0 верна оценка ^

Решается также задача нахождения оптимальных значений параметров метода В третьей главе исследуется робастность (устойчивость) векторных представл ний при изменении информативности низкоуровневых особенностей Под векторнъ представлением кривой в этой главе будем понимать множество вектор А = {В,,В2, ,В_,}, каждый вектор которого это - упорядоченное множество значений и которых функций от контрольных точек кривой (точек с большим значением информати ного признака, например, оценки кривизны), обладающие свойствами

1) все векторы множества Л инвариантны относительно сдвига, поворота и масштабир вания контура,

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

Кроме векторных представлений рассматриваются также описания кривых, не удо летворяющие свойству 2

Другая задача, решаемая в этой главе - получение минимальных устойчивых к з шумлению полигональных представлений кривых Эта задача относится к задачам нахо дения аппроксимирующей ломаной, удовлетворяющей определенному условию оптимал ности Такая задача для разных критериев оптимальности рассматриалась в работ С M Williams, U Ramer, J Sklansky, V Gonzalez, T Pavlidis, A Колесникова и др

В разделе 3 2 для описания векторных представлений дискретных кривых рассма

ривается понятие меры информативности Пусть T = (g,)"J), gk =xti + yti, - плоская ди кретная кривая и Т ■ некоторый класс плоских спрямляемых кривых без самопересеч ний -представлением плоской кривой r = (g,)^ будем называть пару (В,А(В,У упорядоченного множества точек кривой В = {g,, ,g,(j, g, €Г, j = l, ,/, и множест кривых Л(В, Т) = {а^, ,А,.}, Л, еЧ*, s = l, ,/-1, таких, что 1) g, - начало, a g, -к нец кривой Л, , s = l, ,/-1, 2) ¿(А^ ,Г;) = inf с/(Л,Г(1 ), где - часть кривой Г, закл ченная между точками g, и g, Если два ¥-представления (5', А') и (В", А') опред ляяютодну кривую, то будем писать ((В',А') ~ (В",А"))

Определение 3.2 f -мерой информативности на 2Г назовем функцию множес fi, удовлетворяющую условиям I) /i(0) = O, //(Г) = 1 (нормированность), 2) если Ас, то fx(A)<fj(B) (монотонность), 3) если (A,K(A,^))~(B,k{B,"V)), то fi(A) = fi(B).

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

ния К'е и Kse из 2Г в l"q (n<N, 0<q<oo), действующие по правилам К'с Л = |gf J

(ke [л](g, ))' ATf А = }' | [r](g, )) , A e 21 , где ks - некоторая с -оценка кр

визны Первое отображение ставит в соответствие полигональному представлению А уп рядоченное множество оценок кривизны дискретной кривой А Второе отображение с вит в соответствие полигональному представлению А упорядоченное множество оцен кривизны дискретной кривой Г в точках представления А Очевидно, что К'С(Г) = К*(Г Определим на 2' функции информативности по кривизне

4дл)=||<(4/1|к;(Г)||?, (

причем будем считать, что ДЛ) = 0, если множество А имеет мощность не больше двух, а //*ДА) = 0 для А = 0 Нетрудно видеть, что /^ДГ) = /и'ДГ) = 1 и функция множеств является аддитивной мерой Назовем р'чс функцией информативности по локальной (глобальной) кривизне При q = 1 получим так называемые усредненные функции информативности. Усредненную функцию информативности ц дискретной кривой Г можно представить в виде

= Ле2г, (3)

где со{%,А) - неотрицатетьное значение признака представления А кривой Г в ge А

Рассмотрим функцию информативности по локальной кривизне, определенную на 2Г, где Г = - замкнутая дискретная плоская кривая, gn = g() Через , г = 1,2, обо-

значим функцию множеств вида (2), в которой оценка кривизны цеА, / = 1,2,

вычисляется методом геометрического сглаживания (глава2), те а) =

^%(8)-ДД8)[/тах{//Де),ад-А(8)}, б) к™М(8) = С<2)|1-2А(ё)/5'£(е)|, где ад - площадь г-окрестности с центром в точке g, - площадь области Л,

С£' - константы, зависящие от выбранной метрики (см главу 2)

Пусть Л = с Г - некоторое полигональное представление замкнутой кри-

вой Г = gл = g0, Д(Л) - внутренний угол многоугольника представления А в вер-

шине gt, В (А) - множество всех внутренних углов представления А. Тогда справедливо следующее предложение

Предложение 3 3 Пусть е <, 0 5 тш ц — и кривизна оценивается в евклидовой

метрике Тогда справедливы следующие свойства функций множеств и

1) = /фмНъЩъ^Т, ^е =

= ~> V ' монотонная мера на 2Г, 3) если Г - выпуклое множест-

во, то мера ^ будет примитивной, то есть /-^{А) = 1 для любого множества А е2Г, |/1[>3, 4) если замкнутая область Г, ограниченная многоугольником Г, является выпуклой, то /1^1(А) = Ц')(А)1у/]{Т) - монотонная мера на 2Г и (2 п-рух

Предложение 3 4. Пусть 0 < ц < 1 и Г - такой выпуклый многоугольник, что все его внутренние углы не превосходят величины я"(1 -С0), где ?0 - корень уравнения + = О < / < 1 Тогда р™ будет монотонной мерой на 2Г, если 0 5^пип ^

В пункте 3 2 3 рассматривается обобщение усредненной меры информативности Пусть Г - плоская дискретная кривая, /л - усредненная мера информативности на 2' вида (3) и А) = <о(%,Г) = си(£) для всех geA и А е 2' Тогда мера р равна р{А) = ^(в). Л е 2Г, и является аддитивной Предположим, что дискрет-

ная плоская кривая Г = ёк=х1[1 + ук], подвергнута вероятностному зашумлению

-/Кг2((СГ1()|'(<т..1 )г) ^ результате получим случайную кривую Г = ^, -Хки-Ук},

где Хк=хк + т]к, Ук-ук+!;к, т]к,4к - случайные некоррелированные величины, причем Е[%] = Е[&] = 0> о2[?;1] = сг2|, = В этом случае признаковые характеристики

й>(С) = П(й) будут случайными величинами, также как и значение меры М(Л) = Для фиксированного Ае 2Г Для каждого случайного исхода

функция множеств М(Л) будет аддитивной мерой Семейство случайных величин |м(Л) Ае2В} удовлетворяет всем условиям определения элементарной ортогональной стохастической меры Предположим, что существует такое базовое множество В с Г, что случайные величины П(§), geB, независимы Пусть р(А) =

А е 2В, где по-прежнему а>(ъ) = <о(g, Г), Е [П^)] = /п(, ст2 [£Г2(е>] = сг2

В разделе 3 3 поставлена задача о нахождении такого полигонального представления контура Г - базового множества В, мощности не больше заданного числа к, для которого суммарная дисперсия Хмсв®2^^] по всем подмножествам полигонального представления была бы минимальной, а сумма квадратов математических ожиданий всех представлений была бы максимальной Для упрощения выкладок вместо

математических ожиданий нормированных мер информативности Е[М(Л)], Ас. В, будем использовать математические ожидания ненормированных мер 8(А), АсЪ Введем следующий критерий /(В) = £ о2[М(Л)]/]>]14=в.5,(Л), |в|:2Л Тогда требуется найти такое множество В, |в| < к, для которого /(В) -> шю Кроме того, выбор множества В должен быть таким, чтобы случайные признаки ЗД»), geB, были независимыми Пусть

Предложение 3 5. Если кривая Г подвергнута зашумлению Д,(а^г)г), то

длялюбого В е 2Г справедливо равенство /(В) = В(В) - 5г(в)^.1(в) ^Д(В)}

Теорема 3.1. Если кривая Г подвергнута зашумлению И^2((сг,,),,(сгуг)г), то для любого g е В и Ь е Г \ В имеет место следующее равенство

/((В \ е) и ь)- /(В)=(ВХ«Ь -/",)+^ - <тг,) +о(г),

где а(В) = (В)+(В))-щДВ), г = ^(т1 + т1) + -Б^(а1+а[)

Формула из теоремы 3 1 используется для построения алгоритмической процедуры нахождения полигонального представления, минимизирующего функцию критерия /

В пункте 3 2.4 рассматривается усредненная мера информативности, когда значение признака о>(ё,А) в точке g представления А зависит как от координат самой точки g,тaк и некоторых соседних с ней точек Рассмотрен случай, когда аК&,А) = для всех

g е А и А е 2Г, > 2, где gДА) - точка, следующая за точкой g в упорядоченном представлении А В этом случае мера информативности /и может быть как монотонной, так и немонотонной

Предположим, что дискретная плоская замкнутая кривая Г = gi = +

подвергнута вероятностному зашумлению у1/,2((сгт/),,(<т1 Д) В результате получим слу-

чайную кривую Г = Gk = + где Xk = xk+7¡k, Yk=yk+$t, rjt,4k - случай-

ные некоррелированные величины, причем E[77t] = Е[£4] = 0, я2[;/,] = с2к, o2[¿;,] = а2к В этом случае признаковые характеристики w(G, А) = Cl(g,g+(A)) будут случайными величинами, также как и значение меры M(/0 = ]>^f2(g,g+(/l))/£íern(g,g+(r)) Пусть

п(вЛ.(вДЫ)) = П14+1(Л),если А = {gv E[filu,G4)] = тк(А), а2[ц м(Л)]=о?(Я), К[П,_,,(В),П,,+,(В)]= ¿,(B), S(A) = Zim,(A), к?(Л) = к[п,,^А),П„л1,)_1жл0)(В)]+ о?(Л)-г K[nil+l(^£l,j(ltl)^(I4lw(B)], К(Л,В) = £(*В(Л)

Предложение 3.6. Мера Е[М()] является монотонной мерой на 2В тогда и только тогда, когда для любого А е 2В и любого he В\ А верно неравенство Дт(Л,{Ь})(52(В) + К(В,В))>Мв(Л,{Ь})£(В),г0<; Дм(Л,{Ь}) = /и,(Ли{11}) +

Ь))~т,(А), MBM,{h})=i,B(^u{h})+ *в,(Ли{Ь})-*в(Я) В пункте 3 2 5 рассматривается стохастическая мера информативности по длине в качестве признакового значения a>(g,A) = &Kg,gt(A)) полигонального представления А в точке g используется длина звена ломаной ¡u(g,A) = |Ag(^)|, где Ag(A) = g-g,(A) Предположим, что дискретная плоская замкнутая кривая Г = (gt , g, = x^i + yk¡, подвергнута зашумлению Щ2(а) (зашумление типа «дискретный белый гауссовский шум»), в результате получим случайную кривую f = (Gí)^, Gt = g, + п,, где nk = r¡k\ + , rjk, £k ~ N(0,a2) В этом случае признаковые характеристики új(G,A) = ü(g, А) = ||G - G+ (Л)|| = ||AG(/í)|| будут случайными величинами Пусть a(g) (J3(g)) - внутренний угол многоугольника А (многоугольника В) в вершине g, y(g) - угол между векторами g+M)-g и g+(B)-g, L(A) - длина ломаной с вершинами в точках множества А

Теорема 3.2. Для математического ожидания стохастической меры информативности по длине Е[М()] на 2В при зашумлении Щ 2(сг) справедливо равенство

E[M(^)]=^+^qM,B)+0(^/A2(/(,B)), Ае 2В, гЭе С, (Л, В) =-¿(Л)£8 J|Agf + ¿WlJMP + 4£^cos^cos^cos(tfg)+M)

Теорема 3.3. Для дисперсии стохастической меры информативности по длине а2[М()] на 2В при зашумлении М^2(а) справедливо асимптотическое равенство

°2[М(Л)] = -^С2(Л,В) + о(<т7Д2(Л,В)), Ае2в, где C2(A,B) = 7^(L2(B)£teicos2^ +

Величина случайной ошибки - дисперсия стохастической меры информативности характеризует степень устойчивости меры информативности кривой к зашумлению кривой Можно поставить задачу о нахождении полигонального представления фиксированной мощности А е 2В, |л| = к, минимизирующего величину дисперсии стохастической меры информативности по длине Из теоремы 3 3 следует, что при небольшой интенсивности зашумления а решением указанной задачи будет полигональное представление

А - arg min С2(Л,В), которое можно считать наиболее устойчивым к зашумлению относительно данной меры информативности

В разделе 3 3 рассматривается получение минимального полигонального представления кривой методом нечеткой кластеризации Минимальное полигональное представление кривой должно состоять из тех точек g кривой Г, которые обладают высокой информативностью относительно заданного множества признаков {<»,}1е( Сами информативности можно считать некоторыми функциями точек кривой <»((g), gel", iel Предположим, что öJ,(g) e [0,1] для всех g е Г, ie I и ¿u,(g) i &>(h), если точка h е Г является более информативной, чем точка g е Г относительно признака с\ Функция а> (g) характеризует степень принадлежности точки g множеству информативных точек кривой Г относительно г-го признака Поэтому множество информативных точек кривой Г относительно i - го признака можно рассматривать как нечеткое множество {(g, а>1 (g)), g е Г} с функцией

принадлежности а,. Для некоторого фиксированного значения ае[0,1] рассмотри а - срез нечеткого множества Г - множество Ва = {g 6 Г. й>(g) > а} Множество Ва явля ется некоторым представлением контура Г Необходимо найти такое значение параметр а б [0,1], чтобы представление Ва было, с одной стороны, минимальным, а с другой - "хо рошим" Рассматривается представление Ва контура Г, «е[0,1] с функцией принадлеж

ности //"(g) = 1*0^'па В°' Предположим, что универсальное множество - множество то

V ' в а

чек дискретной кривой Г - конечное Для построения идентифицирующего функционал вводится так называемое нечеткое отношение похожести на Г r(g,h), то есть рефлек сивное, симметричное нечеткое отношение, удовлетворяющее неравенств |r(g,h)-r(g,e)|<l-r(h,e) для всех e,g,her Следуя EH Ruspini, множество Ва буд нечетким г —представлением множества Г, если ^herKg,h)//"(h)äiu(g) для все g е Г В разделе 3 3 рассматривается отношение похожести /-(g, h) = 1 - |cy(g) - ft)(h)| Кро ме отношения похожести в задаче нечеткой кластеризации могут быть использованы другие отношения Например, желательно, чтобы точки минимального полигональног представления достаточно далеко располагались друг от друга на кривой Г Для учета это го требования можно ввести нечеткое отношение различия, т е симметричное, антиреф лексивное нечеткое отношения r(g,h), удовлетворяющее условию |r(g,h)-r(g,e)| < z"(h,e) для всех c,g,h б Г Заметим, что приведенное здесь определение нечеткого отношени различия согласуется с используемым выше опредепением нечеткого отношения похоже сти Пусть /(g) - функция принадлежности точки g <е Г множеству информативных точек

Назовем множество Bj8={ger /(g) > ß] с функцией принадлежности Ppig) {/(g) № нечетким Т~пРедстаелением множества Г, если ^.(1 -r(g,h))(\-/Jß(h))

1 — У(g) для всех geT В качестве отношения различия можно использовать функци r(g,h) = /(g,h)/i, где /(g,h) - длина дуги кривой Г, заключенной между точками g,h е Г L - длина кривой Г Если в качестве функции принадлежности /(g) взять функцию ин формативности кривой в данной точке /(g) = tu,(g), то может быть поставлена задача нахождении (г, г) - представления кривой Г необходимо найти такое множество В, кото рое удовлетворяет системе неравенств Хьев("_1|В'^)~®Д',)|)(аДЬ) > a>,(g) 22

— —л»д(Ь)|)(1 — шг(Ь))> 1 — (й) для всех geГ В работе предложен алгоритм нахождения (г,г)-представления Доказаны достаточные условия, при выполнении которых алгоритм находит оптимальное решение

В разделе 3 4 исследуется зависимость изменения характеристик центроидного представления при небольшой вариации координат и информативности контрольных точек Под устойчивым векторным представлением или описанием будем понимать такое представление (описание), вектора (значения) которого непрерывно и равностепенно по числу точек зависят от векторов информативности контрольных точек Точнее, если

© = ш = (¿)- два вектора информативности контрольных точек, а у = (у()"~',

V = (у()""'- соответствующие векторы представления (т<п), то существует такая константа с, не зависящая от й и чисча контрольных точек п, что ¡V- у| <с||со- со||2

Пусть В = %к =хк1 + ук}, к = 0, ,и —1, - множество контрольных точек кри-

вой, имеющих большую информативность, те сок = а)(%к)>Н, к = 0, ,и-1, где й>0 -некоторое пороговое значение Обозначим через = (х,)"^, ул = (х),"^ > = (^ОГо' Тройку (хл,У),,<аА) назовем скелетом кривой Рассмотрим векторное представление ={р»>са- «»*.«>*}> где оА =хс\ + ус\, ' Ус ^И'^УМ/ТЛЧ ' центР

масс скелета (хА,уА,са4), Р,,=(л)"^> А о*), / = 0, ,л-1, - вектор длин радиус-

векторов контрольных точек относительно центра масс он - расстояние между

точками g и Ь), с4 с, = ш>у,, у, = (г = 0, ,п-1, g„ =ё0)~ вектор коси-

нусов углов между соседними ради)с-векторами контрольных точек

В этом разделе сформулирован ряд результатов об изменении центра масс векторного представления, векторных характеристик рл и сА, дескриптора Фурье этих характеристик при добавлении к скелету кривой новых контрольных точек или при изменении информативности этих точек Например, если Т{ (Г2) - отображение, устанавливающее

соответствие между компонентами исходного вектора рА = (сА = (с, ) и вектором

характеристик р'к = (а')"=о (с'л = (с')"^), полученного после добавления в скелет новых контрольных точек, то справедлива теорема

Теорема 3.7.1) (рА)-рА|2 < «/(о„,о'й)^ , 2) если р, > ¿/(оА,Од), / = 0, ,п-1,то

¡^-'¿^^М^Т,^ (л 1 +Р,;1,)2. где о„), 1 = 0, ,и- 1

Следствие 3 11. Если к векторному представлению 1Н добавляются новые контрольные точки то 1) ||(р„> — рА¡}2 < ^¡тгх^о,,^),

2) Иг2(са)-С4||2

Следствие 3 12.Если имеются скелеты и (хЛ,уЛ,(о'11), то

№<р.)-РЛ2 ^ К - »Л, - < -«>д +

В разделе 3 5 оцениваются вероятности уклонения центров масс векторного представления при целочисленном одномерном зашумлении кривой

Теорема 3.9. Пусть 5 = (x,y,v^) - скелет оцифрованной кривой Г е Ссг(т), где вес v™' = (vü>(g))e&s» v^'(g)~¿.h, g e S, вычислены в окрестности Um(g) методом геометрич ского сглаживания, 1<т Если S = (x,Y,y¡11)) - случайный скелет кривой при з

шумлении yV¡<°>(r,o')> 0,0 - центры масс скелетов S и S соответственно, а £>0, т> тате, что <^>-Le[^(f)](^o[^(f)]+l), И, = то

где q, = +-.„,Р*;ш Р? , * = 0, ,/

Четвертая глава посвящена развитию математического аппарата, связанного с и мерением количества такого типа неопределенности как неточность При этом будем пр держиваться неопределенностно-обусловленного подхода в теории информации, появи шегося в начале 80-х годов прошлого века в работах RR Yager, U Hohle, M Higas G J Klir и др Если X - некоторое конечное множество взаимно исключающих альтерн тив, то функция неточности g(A), характеризует ту или иную (в зависимости от конкр ной теории неточности) качественную степень того, что истинная альтернатива содержи ся во множестве альтернатив Ac X Например, так называемая примитивная мера дов

рия, т е мера вида ij^ (А) - j^' ^ А,ВсХ, В*0, характеризует степень доверия

го, что множество А содержит истинную альтернативу, если известно, что все возможнь альтернативы составляют множество В В свою очередь, примитивная мера правдопод

бия г(в)(^) = |о ЛпВ = 0'' ^ЯсЛ", В±0, характеризует степень правдоподобия тог

что множество А может содержать истинную альтернативу Функция неточности xapai ризует качественную степень принадлежности истинной альтернативы рассматриваемо множеству с некоторой неточностью Поэтому в каждой теории неточности должен б] обоснован выбор функционала v (называемый индексом неточности), с помощью котор го для каждой функции g этой теории вычисляется количество неточности, связанной g В теории возможностей, как показал Хартли в 1928 году, для измерения количества н точности, связанной с выбором множества альтернатив из некоторого подмножества (такая неточность называется неспецифичностью), следует использовать функцион

я(^) = 1ое2|В|, называемый мерой Хартли Для измерения количества неопределенн

сти, задаваемой вероятностной мерой р (такой тип неточности называют конфликте используют функционал, известный с 1948 года в теории информации как энтропия Шэ нона S(p) = —^ р(х) Iog2 р(х) Позднее появились обобщения классических теор возможностей и вероятностей Поэтому возникла задача исследования таких обобщен классических мер неопределенности, которые с одной стороны наследовали бы основн свойства меры Хартли и энтропии Шэннона, а с другой стороны отражали специфику т или иной теории неточных вероятностей Наиболее популярным обобщением классич ской теории возможностей является теория свидетельств (теория Демпстера-Шефера) О новным объектом исследования этой теории является так называемая функция (мера) дов рия, которая может быть представлена в виде áf = 2]fi!_рДе функция миоже

m (так называемое основное вероятностное назначение) такова, что m(0) = 0, т(В) > О для всех Ве2х, и = 1 В классе всех функций доверия Bel(X) для измерения

количества неточности D Dubois и H Prade предложили использовать меру = m(.B)log2|B|, которая является обобщением меры Хартли Пусть

g(B) = 1 -g(B), Be 2хдвойственная мера к мере g, Pr(Z) - множество всех вероятностных мер на X, Ма(Х) - множество всех монотонных нормированных мер на X, те g е М0(Х), если 1) g(0) = O, g(X) = l, 2) из ЛсВ следует, что g(A)<g(B), А,Ве2х Класс мер, двойственных к мерам доверия называют классом лер правдоподобия и обозначают Р1(Х) Аксиоматика индекосв неточности на множетсве мер доверия рассматривалась в работах G J Klir, D Harmanec, A Г Броневича

В данной главе в качестве функций неточности рассматриваются, в основном, так называемые нижние и верхние вероятности, которые можно считать нижними и верхними огибающими некоторого семейства вероятностных мер Точнее, монотонная нормированная мера g е М0(Х) называется нижней (верхней) вероятностью, если существует вероятностная мера р € Рг(ЛТ) такая, что g(A) < р(Л) (g(A) > р(А) ) для всех Ае2* Множество всех нижних (верхних) вероятностей будем обозначать через Mlow(X) (MV(X)), а через М(Х) - множество всех или нижних или верхних вероятностей

Определение 4.1. Индексом неточности на множестве М(Х) назовем функционал V М(Х) —> R, удовлетворяющий свойствам J) v(g) = 0, если g s l'r(X), 2) v(g,)>v(g2) Cv(gi)2v(g2); для всех gl,g2e.M,m(X) (gi,g1 eM,p{X)) таких, что g, <g2, 3) v(î]{x)) = \

Mr{x))=V

Простейший индекс неточности можно определить с помощью разности сопряженных мер если В е 2х, то vB (g) = | g (В)—g(B) j - индекс неточности на M (X)

Определение 4.3 Назовем индекс неточности v е 1(М(Х)) линейным на М(Х), если для любого множества {gj}kj=i сМ(Х) и любых таких чисел что

Tj^jSj еМ(Х) справедливо равенство =

Через 10(М(Х)) обозначим класс всех линейных индексов неточности на М(Х) Пусть mg и ms - преобразование и двойственное преобразования Мебиуса меры g соответственно, те = sW^^m^D^B), B,De2*, = gW^^Wn^D), B,De2x, B*0 Для положительного линейного функционала через pf(B) = fi^UiB)) обозначим так называемую дескриптивную меру

Теорема 4.1. Положительный линейный функционал f е !0(М1т(Х)) тогда и только тогда, когда выполняются условия а) У,п кВт'1' (D) = 0 для всех хеХ, б) m"' (X) = 1,

в) m" (D) < 0 для всех De 2х \ {0, X}

Следствие 4.2. Любой линейный индекс неточности f на множестве М,^{Х) можно представить в виде f(g) = l-^1Dç.xq(D)g(D), где функция множеств q удовле-

творяет условиям I) q(0) = q(X) = 0,2) q{D) > О для всех D е 2х, 3) xeBg{D) = 1 для

всех х е X Причем это представление единственно

Теорема 4.2 Положительный линейный функционал f е 1а(М1<т(ХУ) тогда и только тогда, когда выполняются условия a) apf + ¡Зт^ е Р1{Х), где а + /3 = \, а>О,

/'/(М) = 0 для всех хеХ Используя приведенные выше результаты, нетрудно доказать, что нормированная обобщенная мера Хартли Gtf°(g) = ^Ae2^Bmg(A)\ogw\A\ е la(Mhw(X))

Определение 4.4 Линейный индекс неточности у на М(Х) назовем симметричным по дополнению, если m^(D) = тк (D) для любого De 2х \ {0, X)

Через 1,(М(Х)) обозначим класс всех симметричных по дополнению индексов не точности на М(Х)

Теорема 4.3. Положительный линейный функционал v е It(M(X)) тогда и тольк тогда, когда v = Хо^в^«ЛЦ^о > где а„(£>)>0 для всех De 2х \{0,Х}

Пусть 2 х\{0,Л"} = ©и© прямое разбиение алгебры 2х Ол© = 0 и АеФ «ЛеФ Предложение 4.9. Множество всех крайних точек (крайнее множество) выпуклог множества It(M(X)) состоит из множества всех простейших индексов неточност {v, Аеф) для некоторого прямого разбиения Ф

Показано, что для нижних вероятностей вида g(A) = mm {pt(A), р2(А)}, Ае2х рх,р2 бРг(^Г), линейный симметричный индекс неточности имеет смысл расстояния меж ду вероятностными мерами р, и р2 В общем случае, для нижней (верхней) огибающе семейства вероятностных мер, линейный симметричный индекс неточности имеет смы диаметра множества вероятностных мер

Далее в этой главе рассматривается продолжение индекса неточности на мно жество всех монотонных нормированных мер Ма(Х) Для корректного продолже ния индекса неточности на М0(Х) необходимо выделить два типа неопределенно сти, которые можно описать с помощью монотонных мер - неточность и противоре чивость Считая, что точное описание недетерминистской системы может быт осуществлено с помощью вероятностной меры, под неточностью будем понимат неопределенность описания недетерминистской системы, связанную с интерваль ным оцениванием вероятностного описания Под противоречивостью будем пони мать неопределенность, которую нельзя связать с интервальными оценками точног вероятностного описания. Любая мера g е Mhw(X)uМ11р(Х) определяет неточност

описания системы вероятностной мерой Если же g е M0(X)\[Mlaw(X)u М1гр(Х)}, т

информация, задаваемая мерой g, для некоторых множеств альтернатив будет про тиворечивой Предположим, что для измерения количества неточности мы исполь зуем индекс неточности / е I(Mlm (X)) Тогда количество неточности в этой мер ge М0(Х), рассматриваемой в качестве нижней оценки вероятностной меры, мож быть вычислено с помощью функционала /tap(g) = inf {/(//) ре МЫ{Х), р < g}

Аналогично, можно ввести индекс противоречивости f^ig) меры g е Ма(Х), рассматриваемой в качестве нижней оценки вероятностной меры, по формуле /„(*) = mf{/№) MzM^XlMZg]

Лемма 4.5. Справедливы равенства 1) fL„p(g) = "if {/(min(p,g)) р е Рг(ЛГ)}, 2) A,te) = 'nf{/(mm(/7,f)) РеРг(Х)}

В некоторых случаях мы не знаем, какой оценкой вероятности является монотонная мера g е MQ(X) верхней или нижней9 Ответ на этот вопрос можно дать, проанализировав значения индексов неточности и противоречивости этой меры Например, если индексы неточности и противоречивости /lmp(g) и /¡„c(g) соответственно построены с помощью функционала / е 1(М1<пг{Х)), то меру g следует считать нижней оценкой вероятности, если /imp (s) > fto(s) (т е количества неточности в этой мере больше количества противоречивости) и верхней оценкой вероятности - в противном случае Другими словами, если для функционала /j(g) = /tap(g)-/^(g) верно неравенство /s(g)>0, то мера g - скорее нижняя оценка вероятности, чем верхняя

Предложение 4.10. Если f &I,(Mltn¥(X)),mo fs(g) = fig) для всех g е Мд(Х) В этой же главе рассматриваются применения индексов неточности к оцениванию априорной информативности недетерминистских систем, в частности, полигональных представлений кривых

В пятой главе рассматривается задача аппроксимации мер доверия вероятностными мерами. В теории неточных вероятностей существует две различных постановки задачи аппроксимации Первая постановка связана с нижней (верхней) аппроксимацией монотонных мер более «простыми» мерами, «близкими» к вероятностным мерам Такими мерами в первую очередь являются 2-монотонные меры (емкости Шоке), i-аддитивные меры и др Необходимость аппроксимации нижних вероятностей 2-монотонными мерами обусловлена важными приложениями этой задачи в теории проверки статистических гипотез (теорема Хьюбера-Штрассена) Задача верхней (нижней) аппроксимации монотонных мер вероятностными мерами рассматривалась в работах A Chateauneuf, J Y Jafíray и M Grabisch

Другая постановка задачи аппроксимации в теории неточных вероятностей связана с нахождением для заданной монотонной меры такой более «простой» меры, которая минимизировала бы некоторый критерий невязки между двумя мерами Такая постановка находит применение в коалиционной теории игр Кроме того, задача нахождения «ближайшей» меры к заданной нижней вероятности может иметь приложения в ранжировании возможностей появления того или иного события в тех случаях, когда на основании неточных вероятностей этого сделать нельзя (например, нижние и верхние оценки вероятностей появления нескольких событий - одинаковы) В работах P.L Hammer, R Holzman и Е Boros рассматривалась задача безусловной псевдобулевой оптимизации функций множеств многочленами заданного порядка В этой главе рассматривается вторая постановка задачи аппроксимации в классе мер доверия

Пусть X - конечное множество, М0(Х) - множество всех монотонных нормированных мер на алгебре 2х, h-V^fi' ^¡(.А) = т}к(А)~ ¿ = 1, ,п, АсХ С нижней вероятностью g можно связать функцию множеств ре =^(g + g) - средняя часть неточности, задаваемой парой (g,g)

Теорема 5.1. Для любой меры доверия g е Ве1(Х) существует единственная веро ятностная мера pg такая, что норма |/>г - /?г||2 будет минимальной, приче

Р, = • Где а»= Pg({**}) = i+^'Z^x^-4^*Ы), х„еХ, k = 1, ,п

Следствие 5.2. При тех же условиях, что и в теореме 5 1 справедливы равенств l^-4 = mm{||p-g||2 p6PrW},K-4 = mm{||P-f||2 реРг(Х)}

Отдельно рассматривается задача вероятностной аппроксимации симметричных ме доверия

Определение 5.1. Меру доверия g назовем симметричной, если из |#| = |С| следуе что mg{B) = mg(C)

Пусть pQ - равновероятная мера ( р0 ({х}) = 1/|ЛГ| для всех х е X ) Предложение 5.5. Если g е Ве10(Х), то g < pg = р0

Ближайшую меру можно рассматривать как результат действия линейного преобр зования и преобразования сдвига на меру доверия Линейное преобразование будем наз вать преобразованием ближайшей меры Саму ближайшую меру тогда можно записать виде pg = p0+LK\g\, LK[g] - линейный оператор, определенный на линейном простра стве всех функций множеств g (g(0) = 0) с матрицей К К(А,В) = £,(А,В)/2"~2,

Лемма 5.4. Оператор LK имеет собственные значения Л, = 1 и = 0 геометрич ской (и алгебраической) кратности |х|-1 и 2^' - |Х| соответственно

В этой главе решается и обратная задача для заданной вероятностной меры р тр буется найти множество Belp{X) всех таких мер доверия, которые наименее уклоняли бы в среднеквадратичном от заданной вероятности р, те Belp(X) <r Bel(X) и pg = р , всех g е Belp(X)

Теорема 5.2. Класс Belp(X) состоит из функций множеств g = • г

числа т(В), Ве 2х, удовлетворяет условиям 1) т(В)>0, Ве 2х, 2) ^~

3> »=1, ,\х\-\

Кроме того, решается задача нахождения крайних точек множества Belp(X) Пус 1Z{X) - множество всех разбиений множества X

Теорема 5 3. Пусть ВеЩХ) и т(В) = - ße<S Тог

gß = *£,ecßm(B)%) и 8g = - экстремальные меры класса Ве!р(Х)

Алгебраическое описание класса Ве!р(Х) применено к решению задачи оцениван выигрышей коалиций игроков при заданных полезностях отдельных игроков

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

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

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

дом сглаживания локально-интерполяционных оценок Найдены оптимальные значения параметров метода

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

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

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

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

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

8 В рамках исследования степени неточности мер информативности, аксиоматически введены и описаны в терминах свойств дескриптивных мер линейные индексы неточности в классе нижних (верхних) вероятностей Исследован важный выпуклый класс так называемых симметричных по дополнению индексов неточности Найдено алгебраическое описание этого класса Предложен один способ продолжения индекса неточности на множество всех монотонных мер Рассмотрен индекс неточности меры информативности по длине

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

Основные результаты диссертации опубликованы в работах

Статьи в ведущих рецензируемых научных журналах и изданиях, входящих в перечень ВАК

1 Каркищенко А Н , Лепский А Е , Безуглов А В Об одном способе векторного и анали тического представления контура изображения // Изв ТРТУ "Материалы Всерос научно техн конф "Интел САПР-97", Таганрог ТРТУ, №2(8), 1998, с 107-111.

2 Каркищенко А Н , Лепский А Е Оценивание кривизны точек плоского зашумленно контура Некоторые вероятностные модели // Изв ТРТУ "Материалы Всерос научно техн конф "Интел САПР-98", Таганрог ТРТУ, №3(13), 1999, с 194-197

3 Лепский А Е Оценка числовых характеристик случайного веса в одномерной модел зашумления контура плоского изображения // Изв ТРТУ "Материалы Всерос научно техн конф "Интел САПР-98", Таганрог ТРТУ, №3(13), 1999, с 197-200

4 Лепский А Е Об оценивании кривизны плоского зашумленного контура // Обозрени прикладной и пром мат-ки, М изд-во ТВП, Т 6, В 1, 1999, с 171

5 Броневич А Г, Лепский А Е Аксиоматический подход в определении полигонально представления контура изображения // Обозрение прикладной и пром мат-ки, М изд-в ТВП, Т 7 , вып 2, 2000, с 322-323

6 Лепский А Е Оценка вероятности уклонения центроида полигонального предсгавлени плоского зашумленного контура // Обозрение прикладной и пром мат-ки, М, изд-во ТВ Т 7 , 2000, с 379-380

7 Каркищенко А Н, Лепский А Е Об устойчивости центра масс, векторов и дескриптор Фурье векторного представления контура изображения // Автоматика и телемеханика, №3 2001, с 141-151

8 Лепский А Е О систематической ошибке оценивания кривизны контура методом анали тического сглаживания // Обозрение прикладной и пром мат-ки, М изд-во ТВП, Т вып 1,2001, с 254-255

9 Лепский А Е Об аппроксимации одного класса бета-распределений нормальным зако ном // Обозрение прикладной и пром мат-ки, М , изд-во ТВП, Т 8 вып 2,2001, с 633-634

10 Броневич А Г, Лепский А Е Операторы свертки нечетких мер // Обозрение прикла ной и пром мат-ки, М изд-во ТВП, Т 8 вып 2, 2001, с 748-749

11 Броневич А Г, Каркищенко А Н , Лепский А Е Разности функций множеств // Обозр ние прикладной и пром мат-ки, М изд-во ТВП, Т 9 вып 1,2002, с 117-118

12 Каркищенко А Н , Броневич А Г , Лепский А Е Неаддитивные меры приложения к об работке информации с высокой неопределенностью // Вестник Южного научного центр РАН, т 1, вып 3, 2005, с 90-95

13 Броневич А Г., Лепский А Е Аксиоматический подход к задаче нахождения оптимал ного полигонального представления контура // Интеллектуальные системы, т 9, вып 1 2005,с 121-134

14 Лепский А Е Об устойчивости центра масс векторного представления в одной вероя ностной модели зашумления контура изображения // Автоматика и телемеханика, № 2007,с 82-92

15 Лепский А Е Оптимальное проецирование нижних вероятностей на семейство веро: ностных мер // Вестник Ростовского государственного университета путей сообщения, № 2007, с 139-143

16 Каркищенко А Н, Лепский А Е Индекс неточности и его применение к оценивани априорной информативности систем // Известия РАН ТиСУ, №1, 2008, с 94-100

17 Лепский А Е Симметричный линейный индекс неточности в классе нижних вероятн стей // Известия РАН ТиСУ, №2, 2008, с 35-42

Материалы и тезисы конференций, статьи в сборниках, журналах

18 Лепский А.Е Кривизна и вес точки контура плоского изображения объекта // Материалы Всерос науч -техн конф с междун участием "Компьютерные технологии в инж и управл деятельности", ТРТУ, Таганрог, 1999, с 21-22

19 Броневич А Г, Лепский А Е Два подхода к получению минимального полигонального представления контура // Тезисы докл междун науч конф «Искусственный интеллект-2000», п Кацивели, Крым, 2000, с 173-175

20 Лепский А Е, Бачило С А, Рыбаков О С Оптимальный выбор параметров в задаче оценивания кривизны контура в одной вероятностной задаче зашумления изображения // VI Междун конф «Радиолокация, навигация, связь», Т 2 Воронеж, 2000, с 859-863

21 Броневич А Г, Лепский А.Е Некоторые эффективные подходы к распознаванию изображений трехмерных объектов по внешнему контуру // В сб трудов Седьмой нац конф по искусств интеллекту с междун участием КИИ-2000, т 2, Переславль-Залесский, 2000, с 557-565

22 Лепский А Е О нахождении минимального представления контура изображения как решение задачи нечеткой кластеризации // Сб трудов Междун конф по мягким вычислениям и измерениям SCM-2000, т 1, Санкт Петербург, 2000, с 190-193

23 Лепский А Е, Бачило С А, Рыбаков О С Анализ двух методов оценивания кривизны искретной плоской зашумленной кривой // Сб трудов 3-й междун конф «Цифровая об-аботка сигналов и ее применение», М, 2000, с 12-14

24 Броневич А Г, Лепский А Е Два подхода к получению минимального полигонального представления контура // «Искусственный интеллект», №3,2000, Донецк, с 421-427

25 Лепский А Е Исследование устойчивости оценок кривизны к уровню зашумления контура II В сб трудов Междун конгресса «Искусственный интеллект в XXI веке», т 2, М Физматлит, 2001, с 516-524

26 Броневич А Г, Лепский А Е Применение теории нечетких мер к оцениванию информативности полигонального представления контура изображения II Сб трудов Межд науч -практич семинара «Интегрированные модели и мягкие вычисления в искусственном интеллекте», М Наука, Физматлит, 2001, с 112-116

27 Лепский А Е, Броневич А Г, Бачило С А Выделение контрольных точек на основе меры информативности контура // В сб трудов 4-й междун конференции «Цифровая обработка сигналов и ее применение», М, 2002, с 288-291

28 Lepskiy А, Bronevich А, Bachilo S A Extraction of control points based on ал informative quantity measure // Proc of the 4-th International Conference "Digital signal processing and its applications", Moscow, Russia, 2002, p 291

29 Bronevich A G , Lepskiy A E Operators for convolution of fuzzy measures, Soft Methods in Probability, Statistics and Data Analysis // ed Przemyslaw Grzegorzewski - Heidelberg, New-York Physical-Verl, 2002, pp 84-91

30 Лепский A E Инвариантные нормы на пространстве кривых // Труды межд конф «Искусств интел системы» (IEEE AIS'02) и «Интеллектуальные САПР» (CAD-2002) - М Физматлит, 2002, с 440-447

31 Лепский А Е Нахождение минимального представления контура изображения как решение задачи нечеткой кластеризации // Известия вузов России Радиоэлектроника, Xsl, 2002, с 35-39

32 Броневич А Г , Лепский А Е Аксиоматический подход к определению индексов неточности нечеткой меры // Сб трудов 2 междун научно-пракг Семинара «Интегрированные модели и мягкие вычисления в искусственном интеллекте» - М. Физматлит, 2003, с 127-130

/

{

33 Bronevich A., Lepskiy A. Geometrical fuzzy measures in image processing and pattern rec ognition // Proc of the 10th IFSA World Congress, Istanbul, Turicey, 2003, pp 151-154.

34 Каркищенко АН, Лепский А.Б Методы вычисления степени неточности в класс нижних вероятностей И В сб трудов всерос научной конф по нечетким системам и мяг ким вычислениям НСМВ-2006. - М. Физматлит, 2006, с 140-149.

35. Lepskiy А Е. The Linear Imprecision Indices on the Lower Probabilities // Proc of the 11 IPMU Conference, Paris, 2006, pp.1724-1731.

36. Лепский A E О вероятностной мере, наименее уклоняющейся от симметричной час неточности // Материалы IX Междун. конф "Интел системы и компьют науки", т 1, ч 2, М.- Изд-во мех -матем. фак-та МГУ, 2006, с.172-174

37 Лепский А Е Вероятностная аппроксимация мер доверия // Сб. трудов IV-й Межд н учко-пракшч. конференции "Интегрированные модели и мягкие вычисления в иску© венном интеллекте" В 2-х томах, т 1 - М.- Физматлит, 2007, с.212-219

38 Bronevich А, Lepskiy A Measuring uncertainty with imprecision indices // Proc of the Fi International Symposium on Imprecise Probabilities and Their Applications (ISIPTA'07), Pragu 2007, pp 47-56

39. Lepskiy A., Bronevich A Various representations and algebraic structure of linear imprec sion indices // Proc of the 5th EUSFLAT Conference, Ostrava, Chezh Republic, 2007, v pp 297-304

40 Гончаров А В., Горбань А С., Каркищенко A H., Лепский А Е Поиск портретных из бражений по содержанию // Сб работ участников конкурса «Интернет-математика 2007 - Екатеринбург изд-во Урал ун-та, 2007, с 56-64.

41 Каркищенко А Н, Лепский А Е Применение понятия информативности в распознав нии образов // Материалы восьмой междун науч.-техн конф «Искусственный интелле Интеллектуальные системы», Донецк- изд «Наука i оевпа», 2007, с 208-213.

42. Lepskiy А Е. The class of nearest belief functions to a given probability measure // Proc о the NAFIPS'08, New York, 2008, # 60608.

Личный вклад автора в работах, выполненных в соавторстве, включает-

[1,2] - предложен метод геометрического сглаживания для оценивания кривизны, [19,21,24] - исследование векторных представлений едивых,

[20, 23] - аналитическое решение задачи оптимального выбора параметров в методе гео метрического сглаживания;

[5, 13,26,27,28, 33] - исследование меры информативности по кривизне,

[7] - решение задачи об изменении характеристик центроидного представления при н

большой вариации координат и информативности контрольных точек;

[10,11,29] - описание некоторых классов монотонных мер с помощью разностей функци

множеств,

[12] - общая постановка задачи оценивания кривизны, ,

[16, 32,34,38,39] - исследование линейного индекса неточности, определение и исслед вание симметричного по дополнению индекса неточности,

введение.

глава 1. локально-интерполяционные оценки кривизны.

1.1. Введение.

1.2. Необходимые сведения из дифференциальной геометрии кривых на плоскости.

1.2.1. Способы задания кривой.

1.2.2. Касательная к кривой. Длина кривой.

1.2.3. Кривизна кривой.

1.2.4. Классы кривых и классы вероятностных зашумлений.

1.3. Исследование оценки кривизны, полученной методом локальной интерполяции оцифрованной кривой.

1.3.1. Оценки кривизны методом локальной интерполяции оцифрованной кривой.

1.3.2. Систематическая ошибка оценки кривизны.

1.3.3. Распределение вероятностей случайной оценки кривизны при некоррелированном нормальном зашумлении кривой.

1.3.4. Смещение случайной оценки кривизны.

1.3.5. Случайная ошибка оценки кривизны.

1.3.6. Упрощенная оценка кривизны методом локальной интерполяции.

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

1.5. Оценка кривизны методом аналитического сглаживания локально-интерполяционных оценок.

1.5.1. Усреднение функций по Соболеву.

1.5.2. е-усреднение кривизны.

1.5.3. Аналитическое сглаживание локально-интерполяционных оценок кривизны.

1.5.4. Систематическая ошибка аналитического сглаживания первичных оценок кривизны.

1.5.5. Смещение аналитического сглаживания первичных оценок кривизны при сферическом нормальном зашумлении кривой.

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

1.5.7. Оптимальные значения параметров аналитического сглаживания первичных оценок кривизны.

1.6. Выводы.

глава 2. локально-аппроксимативные оценки кривизны.

2.1. Введение.

2.2. Оценивание кривизны методом явной локальной аппроксимации кривой.

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

2.2.2. Систематическая ошибка оценки кривизны.

2.2.3. Случайная ошибка оценки кривизны.

2.2.4. Оптимальные значения параметров нахождения оценки кривизны.

2.3. Оценивание кривизны методом неявной локальной аппроксимации оцифрованной кривой.

2.3.1. Метод геометрического сглаживания.

2.3.2. Систематические ошибки оценок кривизны в методе геометрического сглаживания.

2.3.3. Случайная ошибка линейной оценки кривизны в случае одномерного коррелированного зашумления непрерывной кривой.

2.3.4. Случайная ошибка линейной оценки кривизны в случае двумерного некоррелированного зашумления дискретной кривой.

2.3.5. Числовые характеристики случайной площади в целочисленной одномерной модели зашумления кривой.

2.3.6. Устойчивость вычисления линейного случайного веса и оценки кривизны в целочисленной одномерной модели зашумления кривой.

2.3.7. Смещения нелинейного случайного веса и оценки кривизны в целочисленной одномерной модели зашумления кривой.

2.3.8. Случайные ошибки нелинейного веса и оценки кривизны в целочисленной одномерной модели зашумления кривой.

2.3.9. Числовые характеристики случайной абсолютной величины отклонения веса.

2.3.10. Нахождение оптимальных значений размера окна.

2.4. Выводы.

глава 3. полигональные и векторные представления кривых.

3.1. Введение.

3.2. Меры информативности как способ агрегирования низкоуровневых особенностей.

3.2.1. Аксиоматика меры информативности дискретной плоской кривой.

3.2.2. Способы определения мер информативности контура.

3.2.2.1. Усредненные функции информативности кривой.

3.2.2.2. Функции информативности по локальной кривизне.

3.2.3. Стохастическая аддитивная усредненная мера информативности.

3.2.3.1. Числовые характеристики стохастической аддитивной меры информативности.

3.2.3.2. Нахождение оптимального устойчивого полигонального представления кривой.

3.2.4. Стохастическая монотонная усредненная мера информативности.

3.2.5. Стохастическая мера информативности по длине.

3.2.5.1. Числовые характеристики длин сторон зашумленного многоугольника.

3.2.5.2. Числовые характеристики стохастической меры информативности по длине.

3.3. Получение минимального полигонального представления кривой методом нечеткой кластеризации.

3.4. Устойчивость векторных представлений дискретной кривой.

3.4.1. Устойчивость центра масс векторного представления контура.

3.4.2. Устойчивость характеристик векторного представления контура.

3.4.3. Устойчивость дескриптора Фурье.

3.4.4. Применение теории для расчета вероятностных оценок изменения характеристик зашумленного контура.

3.5. Вероятность уклонения центра масс векторного представления при целочисленном одномерном зашумленнии кривой.

3.6. Выводы.

глава 4. линейный индекс неточности и его применение в задачах анализа изображений.

4.1. Введение.

4.2. Основные определения и обозначения.

4.3. Измерение количества неточностей в классе нижних (верхних) вероятностей с помощью разностей сопряженных мер.

4.3.1. Сопряженная (двойственная) функция множеств.

4.3.2. Разность сопряженных мер.

4.3.3. Усреднение разностей сопряженных мер.

4.4. Аксиомы индекса неточности в классе нижних (верхних) вероятностей.

4.5. Линейный индекс неточности.

4.5.1. Положительные функционалы на конусе мер.

4.5.2. Представления линейного индекса неточности.

4.5.2.1. Описание линейного индекса неточности через преобразование Мебиуса дескриптивных мер.

4.5.2.2. Описание линейного индекса неточности через свойства дескриптивных мер.

4.6. Симметричный по дополнению индекс неточности.

4.6.1. Общий вид линейного симметричного по дополнению индекса неточности.

4.6.2. Крайнее множество линейных симметричных по дополнению индексов неточности.

4.7. Продолжение индекса неточности на множество всех монотонных мер.

4.8. Индекс неточности мер информативности по длине.

4.8.1. Индекс неточности мер информативности по длине на алгебре, порожденной вершинами правильного и-угольника.

4.8.2. Некоторые интерпретации индекса неточности меры информативности.

4.9. Выводы.

глава 5. вероятностная аппроксимация мер доверия и её приложения.

5.1. Введение.

5.2. Мера и центральная компонента неопределенности.

5.3. Среднеквадратичная аппроксимация функции доверия вероятностной мерой.

5.4. Векторное представление ближайшей меры. Алгебраические свойства преобразования ближайшей меры.

5.5. Величина невязки среднеквадратичной аппроксимации.

5.6. Симметричные меры доверия.

5.7. Меры доверия, наименее уклоняющиеся от заданной вероятности.

5.8. Среднеквадратичная аппроксимация функций доверия к-аддитивными мерами.

5.9. Равномерная аппроксимация функций доверия.

5.10. Экстремальные меры доверия, ближайшие к вероятностной мере.

5.10.1. Некоторые множества экстремальных мер доверия, ближайших в среднеквадратичном к равновероятной мере.

5.10.2. Экстремальные меры доверия, ближайшие в среднеквадратичном к произвольной вероятностной мере.

5.10.3. Оценка числа экстремальных мер доверия, ближайших в среднеквадратичном к равновероятной мере.

5.11. Задача оценки выигрышей коалиций при заданных полезностях отдельных игроков.

5.12. Выводы.

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

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

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

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

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

Решению этих и смежных задач посвящена настоящая диссертационная работа.

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

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

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

К низкоуровневым особенностям, прежде всего, относят края изображения, кривизну кривой, описывающей край объекта и некоторые другие.

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

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

2,3].

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

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

1) для получения аналитических характеристик формы объекта [2]. Существуют различные аналитические характеристики формы: функция кривизны контура, функция наклона контура, дескрипторы Фурье, моменты изображения и т.д. Одной из основных аналитических характеристик изображения кривой является функция ее кривизны. Функция кривизны вместе с функцией наклона однозначно определяют кривую.

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

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

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

Для плоской гладкой кривой кривизну k(g) в точке g можно определить как скорость изменения направления касательного вектора при движении точки по кривой, т.е. k(g) = 0[(g), где 0(g) - функции наклона (угол между касательной и положительным направлением оси Ох) и производная берется по длине дуги s . Точки, где направление касательного вектора быстро изменяется, являются точками высокой кривизны. Эти точки будут более информативными, чем точки кривой с низкой кривизной в том смысле, что положение именно этих точек на изображении определяет форму объекта. Проведенные еще в 50-х годах прошлого века психологические исследования [4] показали, что человеческое восприятие остается практически инвариантным при замене контурного изображения его полигональным представлением, построенным по точкам высокой кривизны. Поэтому точки высокой кривизны (в литературе их часто называют контрольными, доминантными или угловыми точками) служат, прежде всего, для построения высокоуровневых описаний изображений объектов.

Кривизна относится к тем понятиям классической (в данном случае, дифференциальной) геометрии, которые не имеют однозначного аналога в цифровой геометрии, занимающейся изучением свойств точечных множеств, полученных в результате дискретизации плоских или пространственных фигур. Действительно, если Г - гладкая кривая на плоскости R2, то кривизну можно рассматривать как результат действия на Г некоторого, вообще говоря, нелинейного оператора CurR\ k(g) = Смгд[r](g) для всех geT, определенного на множестве CX(R2) всех гладких кривых плоскости R2. В цифровой геометрии все геометрическое объекты рассматриваются на некотором базовом дискретном множестве (сетке), например, на Z2. Переход с плоскости R2 на сетку Z2 осуществляется с помощью некоторого оператора дискретизации D:R2 —> Z2, который является всюду определенным, сюръектив-ным, но не инъективным. Оператор D ставит в соответствие гладкой кривой

Г с R2 оцифрованную кривую Т = D(Y)aZ2. Пусть CD{Z2) = {f = £>(Г): ГеСЧД2)}. Возникает вопрос, как определить «кривизну» оцифрованной кривой Г, если оператор вычисления кривизны CurR, заданный на множестве C\R2), не определен на множестве CD(Z2)1 Аналогичный вопрос возникает при попытке перенести многие понятия классической геометрии на множество Z2. В общем случае под оценкой кривизны дискретной (оцифрованной) кривой Г в точке gef будем понимать такую скалярную функцию кЕ(g), зависящую от векторного параметра £, что для гладкой кривой Ге Cl(R2) выполняется равенство limкс(g) = k(g) для всех geT, где £0 - некоторое

L->E0 значение вектора параметров. Чаще всего параметр е характеризует размер окрестности, в пределах которой вычисляется оценка. Пусть £c(g) =

CurZc[r](g). Теоретически существует три подхода к определению оператора кривизны Сиг2г на CD(Z2):

1) CurzjE = CurR о /£, где /Е: CD(Z2) —> C'(fi2) - оператор локальной интерполяции цифровой кривой;

2) Curz е = CurR о Аг, где Аг: CD(Z2) —> C'(i?2) - некоторый оператор гладкой локальной аппроксимации цифровой кривой;

3) CurZL = М(Curz ],.,Cutгде М - оператор агрегирования (усреднения), a \Curz^P^ - операторы кривизны, найденные 1-м или 2-м способами.

Заметим, что во втором подходе кроме явных способов построения гладкой аппроксимации дискретной кривой существуют и неявные схемы следующего вида. Пусть X = R или X — Z и кривой Гс!2 оператор £Л,(Г) ставит в соответствие некоторую локальную характеристику (вообще говоря, векторную) q. Например, ^(Г) - площадь, ограниченная кривой Г в пределах некоторой окрестности; q(r) - вектор изменения интенсивностей в разных направлениях полутонового изображения, содержащего кривую; д(Г) -отношение длины хорды, стягиваемой кривой к расстоянию от кривой до хорды. Характеристика q должна быть определенной и для гладких и для цифровых кривых. Тогда аппроксимирующий оператор А можно искать в виде А = Z"1 о Lz. Так как оператор Lz является сюръективным, но не инъек-тивным, то оператор L"1 не определяется однозначно. Причем степень неопределенности в выборе L"1 будет тем меньше, чем точнее будет определен класс аппроксимирующих кривых в С1 (Л2). В качестве такого класса обычно используются алгебраические кривые. Неявная схема аппроксимации обладает следующей очень важной особенностью. Если характеристика q =LZ(T) является устойчивой к зашумлению кривой Г (например, <у(Г) - площадь, ограниченная кривой Г в пределах некоторой окрестности), то и оценка кривизны, полученная с помощью такой схемы, будет устойчивой к зашумлению изображения.

Кроме алгоритмов оценивания кривизны широко распространены так называемые детекторы углов, не связанные явно с вычислением кривизны. Как правило, в этих алгоритмах неявно вычисляется некоторая функция от кривизны. В настоящее время известно около 100 алгоритмов оценки кривизны и детекторов углов плоских оцифрованных кривых. Кратко охарактеризуем основные алгоритмы оценивания кривизны в соответствии с вышеуказанной схемой классификации.

Если в первом подходе / - интерполяционный многочлен, то этот подход связан с заменой дифференциального оператора кривизны разностным (сеточным) аналогом. Например, если 6(g) - функции наклона кривой, то оценка кривизны в точке g; может быть найдена по формуле (g/) = (^Cg/+1) - ))/('y(g/+i) - -yCgf-i)), где s(g) - функция длины кривой (нижний индекс кривизны указывает на то, что оценка вычисляется на трехточечном шаблоне ={-1,0,1}). Для параметризованной кривой (x(t),y(t)), teT, Т - дискретное множество, оценку функции в можно найти на том же шаблоне по формуле 0(gi) = artcg((y(ti+[)-у((ы))/(х01+[)-х((^))). Недостатком этого метода является то, что полученные таким образом оценки кривизны существенно будут зависеть от дискретизации кривой и будут совершенно неустойчивыми к зашумлению кривой. Этот способ можно сделать менее чувствительным к значениям отдельных данных, если вычислять значения разностных производных не на трехточечном шаблоне S{, а па некотором большем шаблоне. Такой способ оценки кривизны рассматривался в 70-х годах прошлого века в алгоритме Bennet и MacDonald [5] по выделению угловых точек. В алгоритме Freeman и Davis [6] вычислялись первичные оценки кривизны с помощью алгоритма [5], а затем реализовывался третий подход - рассматривалось усреднение s подряд идущих первичных оценок для разных ^ значений шагов интерполяции (обычно выбирались 3<s<6). Некоторой разновидностью этого алгоритма является алгоритм Beus и Tiu [7], в котором, кроме всех шагов предыдущего алгоритма, осуществлялось усреднение полученных оценок по всем sx <s<s2, где s{,s2 - заданные параметры (обычно, =4, j2=7). Замена дифференциальных операций конечными разностями при вычислении оценок кривизны рассматривалась также в работах Ansari и Delp [8], Melen и Ozanian [9].

Кроме интерполирования многочленами в ряде алгоритмов применяется интерполирование окружностью. Так, например, в известном детекторе Chetverikov и Szabo [10] определялась окружность наименьшего радиуса, описанная вокруг треугольника, вписанного в оцифрованную кривую, одна из вершин которого — точка оценки кривизны. Кроме того, во многих детекторах углов и алгоритмах сегментации кривых используется так называемая мера расстояния между хордой и стягиваемой ее дугой кривой. В главе 1 будет показано, что эта мера связана с радиусом интерполирующей окружности. Поэтому все методы детекции углов и сегментации кривых, основанные на вычислении этой меры, можно отнести к методам первого подхода. В частности, мера расстояния между хордой и стягиваемой ее дугой использовалась в таких популярных алгоритмах, как в алгоритме Douglas-Peucker [11], алгоритме Rutkowski и Rosenfeld [12], в алгоритме Ramer [13] и др.

Второй подход к вычислению оценок кривизны основан на гладкой аппроксимации дискретной кривой и нахождению кривизны аппроксимирующей функции. Причем, как указывалась выше, аппроксимация может быть явной и неявной. Явная квадратичная аппроксимация дискретных данных в 90-е годы прошлого века была реализована, например, в алгоритмах [14] и [15]. Явная аппроксимация окружностью рассматривалась, например, в алгоритмах [16]. Предварительное сглаживание кривой с помощью гауссовского ядра рассматривалось в алгоритмах Mokhtarian и Mackworth [17], Pei и Lin [18], Rattarangsi и Chin [19]. Выделение точек высокой кривизны для различных значений параметров гладкости ядра получило развитие в так называемом пространственно-масштабном представлении {scale-space representation). В ряде алгоритмов была реализована неявная схема аппроксимации. В частности, широкое распространение получили алгоритмы неявной аппроксимации, в которых в качестве характеристики я(Г) рассматривался вектор изменения интенсивностей в разных направлениях полутонового изображения, содержащего кривую. Например, в работе [20] по активным контурам был предложен следующий алгоритм оценивания кривизны по изменению интенсивности в точке. В каждой точке (х,у) изображения рассматривается функция <р(х,у), численно равная углу градиента изображения в данной точке. Затем в направлениях (р + кл/2, к = 0,1,2,3, оценивается изменение функции (р(х,у). Показано, что это изменение является функцией координат градиента функции изображения, который оценивается численно с помощью известных разностных схем. Изменение функции (р(х,у) будет оценкой кривизны в данном направлении. Тот же подход - вычисление оценки кривизны по изменению интенсивности функции изображения в четырех перпендикулярных направлениях в пределах некоторой окрестности, был применен в так называемом детекторе Харриса [21]. Этот алгоритм основан на том наблюдении, что для точек высокой кривизны такие изменения будут достаточно большими по всем направлениям; для точек низкой кривизны в двух колли-неарных направлениях изменения интенсивности будут большими, а в перпендикулярном направлении - небольшими; наконец, если точка вообще не является краевой, то эти изменения будут небольшими по всем направлениям. Преимуществом этого подхода является то, что он пригоден и для оценивания кривизны полутонового изображения, на котором не выделены кривые. Более того, используя этот подход можно совместить процедуру выделения краев и выделения точек высокой кривизны.

Третий подход к вычислению оценок кривизны связан с применением агрегирующего (усредняющего) оператора к первичным оценкам кривизны, найденным первым или вторым способами. Применение такого оператора интегрирует информацию о кривизне, полученную с помощью других процедур. Так в алгоритме Freeman и Davis [6] осуществлялось усреднение первичных оценок кривизны, найденных с помощью разностного оператора кривизны. В алгоритме Chetverikov и Szabo [10] усредняющий оператор применялся к первичным оценкам кривизны, найденным методом интерполирования дискретных данных окружностью. Общий подход применения усредняющего оператора, а именно усредняющего интегрального оператора Соболева, был реализован в так называемом детекторе Кэнни [22], который является наиболее популярным (и в определенном смысле оптимальным) способом выделения краев на изображении. Применительно к оцениванию кривизны детектор Кэнни представляет собой свертку первичных дифференциальных оценок кривизны (или оценок первообразных кривизны — функции наклона в) с усредняющим гладким ядром (например, с равномерным или с гауссовским ядрами).

Завершая обзор основных методов вычисления оценок кривизны, можно сделать следующий вывод. Первый способ вычисления оценки кривизны сам по себе, без дальнейшего агрегирования информации, применялся только в ранних алгоритмах. Позднее, для того чтобы сделать алгоритмы более ро-бастными к дискретизации и зашумлению кривой, разностный подход к вычислению оценок кривизны стали дополнять процедурой усреднения. Параллельно с этим широкое распространение получил и второй - аппроксимативный подход. Причем в этом подходе можно выделить два направления - явная и неявная аппроксимация. Второе направление - неявная аппроксимация позволяет совмещать вычисление оценок кривизны с другими процедурами низкоуровневой обработки. Кроме того, и первый и второй подходы в некоторых алгоритмах дополняются процедурой агрегирования. Подчеркнем, что такая классификация алгоритмов является достаточной условной. Действительно, если оценка кривизны вычисляется по схеме усреднения разностных оценок: Curzг- M(Curz\,.,Curzp^), то оператор А = Сиг~\ °

M(Curzl,.,Curz'^), А: CD(Z2) С1 (R2) можно считать оператором гладкой аппроксимации цифровой кривой.

Существуют различные критерии оценки качества алгоритмов детекции угловых точек и оценивания кривизны. Основными критериями оценивания качества таких алгоритмов являются следующие [10]:

1) селективность, т.е. частота правильной детекции угловых точек должна быть высокой, а неправильной детекции — низкой;

2) каждая угловая точка должна детектироваться единожды;

3) точность расположения угловых точек или точность оценки кривизны;

4) робастность к зашумлению;

5) робастность к параметрам;

6) легкость настройки параметров;

7) скорость работы алгоритма.

В настоящей работе основное внимание будет уделено анализу точности и устойчивости к зашумлению оценок кривизны. Под точностью (систематической ошибкой) оценки kc(g) кривизны k(g) в точке geT будем понимать величину sc = \ke(g)-k(g)\. Если дискретная кривая подвергнута аддитивному вероятностному зашумлении, то оценка кривизны будет случайной величиной ^c(g), которая качественно характеризуется величиной смещения bz = |E[ATJ - |, где Е[-] - оператор математического ожидания, и величиной случайной ошибки (дисперсии) Оценку A"£(g) будем называть устойчивой к заданному зашумлению при выполнении условий: a) lim|E[^J-/cl = 0; б) 1пп<т2[^] = 0. Если <52[Кг] = 0(£-а), |Е|Хе]-/се| = €—€—

0(е~р), то числа а,{3>0 характеризуют степень устойчивости оценки кривизны к зашумлению.

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

С точки зрения точности и устойчивости к зашумлению способы оценивания кривизны можно (достаточно условно) разделить на две группы: локально-интерполяционные и локально-аппроксимативные.

К локально-интерполяционным оценкам будем относить те, в которых реализуется первый из указанных выше подходов, связанный с локальной интерполяцией дискретных данных и последующим вычислением кривизны интерполирующей функции, дополненный, быть может, процедурой агрегирования оценок. К этой группе методов можно отнести: 1) методы, связанные с заменой дифференциального оператора кривизны разностным аналогом; 2) методы усреднения дифференциальных оценок (например, алгоритм Freeman и Davis и др.); 3) методы, основанные на использовании сглаживающих интегральных операторов (детектор Кэнни).

К другой группе методов, назовем их методами локально-аппроксимативного оценивания кривизны, будем относить те, в которых реализуется второй из указанных выше подходов, дополненный, быть может, процедурой агрегирования первичных оценок кривизны. К этой группе методов можно отнести: 1) методы явной аппроксимации дискретных данных функциями из некоторого класса; 2) методы неявной аппроксимации, в том числе основанные на вычислении изменения интенсивностей в разных направлениях полутонового изображения (детектор Харриса и др.).

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

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

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

Методы первой группы основаны на замене оцифрованной кривой Г такой кривой из некоторого фиксированного класса, которая удовлетворяла бы определенным условиям «близости». Наиболее популярными аппроксимативными способами представления кривой являются методы, использующие многочлены Безье и В-сплайны [23, 24]. Применение этих методов требует предварительного определения узлов сплайнов или точек-ориентиров, а эта задача практически равносильна общей постановке задачи представления кривой.

Методы второй группы предполагает выбор некоторого множества точек на кривой Г и замену каждого участка кривой между двумя соседними точками другой кривой из фиксированного класса, исходя из определенных условий оптимальности. В качестве класса интерполяционных кривых чаще всего рассматриваются отрезки прямых, дуги окружностей [25], алгебраические кривые небольшого порядка. Кусочно-липейная интерполяция в литературе называется полигональным представлением кривой.

Таким образом, задача получения полигонального представления кривой (в том числе замкнутой кривой - контура) состоит в построении ломаной (многоугольника в случае полигональной аппроксимации замкнутого контуpa) с вершинами на кривой, которая сохраняла бы основную информацию о форме кривой.

Существуют два основных подхода к решению этой задачи: эвристический и оптимизационный. К алгоритмам первого подхода относят алгоритмы, основанные на выделении доминантных точек, алгоритмы, основанные на применении процедур слияния и разбиения сторон многоугольника (например, методы, использующие «подбор концевых точек» - алгоритмы Douglas-Peucker и др.), генетические алгоритмы [26], алгоритмы многократного сглаживания [27], алгоритмы, использующие нечеткую логику [28] и др. Эти алгоритмы, как правило, являются быстрыми, но не оптимальными.

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

1) многоугольник с фиксированным числом вершин должен иметь наименьший периметр [29];

2) максимальное расстояние от точек кривой до сторон многоугольника должно быть минимальным [13, 30, 31];

3) число сторон многоугольника вместе с погрешностью аппроксимации должно быть минимальным [32-35];

4) площадь симметрической разности между множеством, ограниченным замкнутой кривой и множеством, ограниченным многоугольником, должна быть минимальной [36, 37];

5) погрешность аппроксимации многоугольником с фиксированной длиной стороны должна быть минимальной [38].

Таким образом, алгоритмы второго подхода являются алгоритмами нелинейной оптимизации с ограничениями. Заметим, что большинство из указанных выше алгоритмов являются субоптимальными. Как правило, для улучшения сходимости и уменьшения числа итераций оптимизационных алгоритмов предварительно строится «хорошее» полигональное приближение к оптимальному решению путем определенного выбора точек высокой кривизны. После чего «запускается» тот или иной метод нелинейного программирования. Следует отметить, что лучшие из оптимизационных алгоритмов при нахождении оптимальных полигональных представлений замкнутых оцифрованных кривых, содержащих п точек, имеют вычислительную сложность порядка О(п^) [39].

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

В работах [40, 41] был предложен новый подход к решению задачи нахождения минимального полигонального представления замкнутой кривой, основанный на применении монотонной меры информативности, определенной на упорядоченных подмножествах точек кривой. Примерами таких мер могут быть нормированная (к длине всего контура) длина замкнутой ломаной с вершинами в точках подмножества, или нормированная (к площади, ограниченной кривой) площадь многоугольника с вершинами в точках подмножества, если многоугольник - выпуклый. В указанных работах были исследованы как общие свойства мер информативности контура, так и свойства конкретных мер. Были также рассмотрены различные постановки задач нахождения оптимального полигонального представления по мере информативности, найдены условия, накладываемые на меру информативности, позволяющие организовать эффективную процедуру поиска оптимального контура.

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

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

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

1) инвариантность относительно определенной группы геометрических (обычно - аффинных) преобразований плоскости;

2) компактность представления;

3) однозначность восстановления полигонального представления с точностью до гомотетии.

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

Существуют несколько подходов к построению векторных представлений. Первый подход предполагает, что если сравниваемое изображение кривой и модельная кривая принадлежат одному классу, то существует геометрическое преобразование из некоторой группы, которое минимизирует меру расхождения между двумя кривыми. Поэтому в этом подходе векторное представление должно, прежде всего, обеспечивать однозначность восстановления полигонального представления и обладать высокой геометрической информативностью (т.е. содержать «много» геометрической информации о кривой). Например, в работе [42] рассматривалось векторное представление контура, состоящее из двух векторов - вектора отношений длин сторон многоугольника к длине первого ребра и вектора внутренних углов многоугольника. Зная положение и ориентацию первой стороны многоугольника (4-е параметра) по такому векторному представлению можно однозначно найти положение и ориентацию всех сторон многоугольника. Указанное векторное представление использовалось для решения оптимизационной задачи нахождения такого соответствия между двумя контурами, один из которых задан векторным представлением, при котором величина среднеквадратичной ошибки расстояний от всех точек кривой до ближайших сторон многоугольника будет наименьшей.

Более сложное векторное представление рассматривалось в работе [43]. Это представление состояло из векторов, содержащих не только информацию о сторонах и углах полигонального представления, но и интервальную информацию о возможных диапазонах изменения этих параметров для указанного класса объектов.

Другой подход к построению векторного представления - символьное представление, ставит в соответствии полигональному представлению кривой (или всей кривой) некоторое множество геометрических примитивов (например, ломаных определенного вида) и множество отношений между этими примитивами. Эти множества кодируются некоторыми символами, которые в дальнейшем на этапе распознавания классифицируются с помощью так называемых синтаксических (структурных) методов распознавания [44]. Такие представления в диссертации не рассматриваются.

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

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

При использовании меры информативности для описания представлений дискретной кривой Г, мы можем столкнуться с неопределенностью вычисления значения меры информативности ju(A) представления А, если нам известны только значения информативных признаков а>{g) всех точек geT. Эта неопределенность обусловлена тем, что в мере информативности /и{А) может агрегироваться информация не только об отдельных точках представления А, но и более сложная информация о структурной зависимости между информативностями отдельных точек относительно выбранного признака хп. Такая информативная неопределенность присуща любой неаддитивной мере и связана с информационной недостаточностью или с отсутствием описания структурной зависимости между информативностями отдельных точек. Таким образом, количество неопределенности об объекте, описываемом мерой информативности, связано с количеством информации об этом объекте.

Существуют разные подходы к определению информативности (количества информации) объекта или системы. Это и вероятностный подход, в котором количество информации определяется как величина, равная изменению неопределенности системы при осуществлении некоторого опыта а [45]: 1{ос) = S{p)-Sa(p). Сама неопределенность системы S(p), следуя К. Шеннону [46], определяется как степень неопределенности нахождения системы в одном из состояний: S(p) = р, log2 pt, если нахождение системы в этих состояниях описывается вероятностным распределением р = {/?,}. Это и вычислительный (или алгоритмический) подход [47], в котором количество информации об образе равно длине его наименьшего описания в некотором стандартном языке (например, длине наименьшей программы для стандартной машины Тьюринга). Это и комбинаторный (или алгебраический) подход [48], в котором количество информации, заключенной в слове определяется логарифмом числа различных слов, которые можно получить из данного слова путем всевозможных перестановок его букв. Существуют и, время от времени, появляются все новые и новые подходы.

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

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

В диссертационной работе будем придерживаться неопределенностно-обусловленного подхода в теории информации, появившегося в начале 80-х годов прошлого века в работах R.R. Yager [49], U. Hohle [50], М. Higashi, G.J. Klir [51], согласно которому понятие неопределенности тесно связано с понятием информации, в том смысле, что неопределенность входит в любую проблемную ситуацию как результат некоторой информационной недостаточности системы. Предположим, что мы можем измерить количество неопределенности, содержащейся в данной системе, и в этой системе выполняются какие-либо действия, связанные с получением значимой информации от системы. Тогда количество информации, полученной в результате выполнения этих действий, может быть измерено как количество уменьшенной неопределенности.

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

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

Функция неточности характеризует качественную степень принадлежности истинной альтернативы рассматриваемому множеству с некоторой неточностью. Поэтому в каждой теории неточности должен быть обоснован выбор функционала (называемого индексом неточности), с помощью которого для каждой функции /л этой теории вычисляется количество неточности, связанной с ju. В теории возможностей, как показал Хартли в 1928 году, для измерения количества неточности, связанной с выбором множества альтерназываемая примитивная мера доверия, т.е. мера вида натив из некоторого подмножества В (такая неточность называется неспецифичностью), следует использовать функционал H(rj^) = log2|i?|, называемый мерой Хартли. Для измерения количества неопределенности, задаваемой вероятностной мерой р (такой тип неточности называют конфликтом), используют энтропию Шэннона S(p).

После того как появились обобщения классических теорий возможностей и вероятностей, возникла задача исследования обобщений классических мер неопределенности. Эти обобщения должны были, с одной стороны наследовать основные свойства меры Хартли и энтропии Шэннона, а с другой стороны, отражать специфику конкретной теории неточности. Наиболее популярным обобщением классической теории возможностей является теория свидетельств (теория Демпстера-Шефера [52]), основным объектом исследования которой является так называемая функция (мера) доверия, представи-мая в виде /1 = т{В)т]^ , где т(0)- 0, т(В)> 0 для всех Be 2х, и д^хт(В) = ]. В классе всех функций доверия Bel(X) для измерения количества неточности D. Dubois и Н. Prade [53] предложили использовать так называемую обобщенную меру Хартли

GH(/i) = £ m(5)log2|5|.

Ве2х\{0]

Обзор мер неопределенности в других теориях неточности можно найти в [54]. В ряде работ [55, 56] рассматривалась аксиоматика мер неопределенности. В то же время оставался открытым вопрос об определении и описаниях индекса неточности в более широких классах мер, чем меры доверия. Наиболее широким классом функций неточности является класс так называемых нижних (верхних) вероятностей, т.е. таких монотонных нормированных мер /л, которые являются нижними (верхними) оценками вероятностных мер. Относительно мало исследовались алгебраические свойства, представления и описания самих индексов неточности в тех или иных классах монотонных мер. Кроме того, представляет интерес исследование индексов неточности на мерах информативности.

В общем случае мера информативности (1 может быть довольно громоздким описанием полигонального представления В, так как для своего задания она должна быть определена на всех 2'в' подмножествах представления В. Поэтому для ряда задач удобней использовать более простое представление, связанное с монотонной мерой (1. Таким представлением может быть монотонная мера из некоторого класса, аппроксимирующая в том или ином смысле монотонную меру (1. Простейшей такой мерой является вероятностная мера. Представляет интерес исследование свойств вероятностной меры, аппроксимирующей заданную монотонную меру, а также решение обратной задачи — описание класса тех монотонных мер, для которых заданная вероятностная мера будет аппроксимирующей мерой.

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

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

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

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

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

4. Аксиоматически ввести и исследовать индексы неточности в классах нижних и верхних вероятностей, предложить способы продолжения индексов неточности на множество всех монотонных мер, рассмотреть применения индекса неточности для исследования мер информативности.

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

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

Материалы диссертационной работы распределены по главам в соответствии перечисленным задачам.

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

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

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

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

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

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

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

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

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

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

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

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

В главе 5 решается задача аппроксимации меры доверия вероятностной мерой, минимизирующей среднеквадратичную невязку. Исследуются различные представления ближайшей вероятностной меры. Доказывается, что вероятностная мера, минимизирующая среднеквадратичную невязку с мерой доверия, минимизирует и среднеквадратичную невязку с сопряженной мерой и со средней частью неточности. Показывается, что понятие «ближайшей» меры можно использовать для ранжирования возможностей появления событий в тех случаях, когда нижние и верхние вероятности не позволяют однозначно решить задачу ранжирования. Исследуются алгебраические, спектральные и аппроксимативные свойства преобразования, ставящего в соответствие мере доверия ближайшую в среднеквадратичном вероятностную меру. Подробно исследуются свойства ближайшей в среднеквадратичном меры в классе так называемых симметричных мер доверия. Доказывается, что для симметричной меры доверия ближайшая вероятностная мера является равновероятной и будет мажорировать саму симметричную меру доверия. Рассматривается задача аппроксимации мер доверия /t-аддитивными мерами в среднеквадратичной метрике, связанной с преобразованием Мебиуса, а также равномерная аппроксимация мер доверия.

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

В приложении приведены копии актов о внедрении и использовании результатов работы.

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

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

2. Разработан и исследован метод усреднения локально-интерполяционных оценок. Найдены оптимальные значения параметров метода.

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

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

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

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

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

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

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

10. В рамках исследования степени неточности мер информативности, аксиоматически введены и описаны линейные индексы неточности в классе нижних (верхних) вероятностей. Предложен и исследован один способ продолжения индекса неточности на множество всех монотонных мер. Рассмотрен индекс неточности меры информативности по длине.

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

12. Решена обратная задача вероятностной аппроксимации: найдено множество тех мер доверия, для которых заданная вероятностная мера является ближайшей в среднеквадратичном. Найдено семейство экстремальных точек выпуклого класса ближайших мер доверия и рассмотрены некоторые применения найденных описаний в теории игр.

Основные результаты работы докладывались на Всероссийской научно-технической конференции «Интеллектуальные САПР» 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-й конференции Европейского сообщества по нечеткой логике и технологиям EUS-FLAT (Острава, 2007), на конференции Северо-Американского общества по обработке нечеткой информации NAFIPS (Нью-Йорк, 2008).

По теме диссертации опубликованы 42 печатные работы, из них 17 работ - в изданиях рекомендованных ВАК. Кроме того, результаты исследований отражены в 5-ти отчетах о НИР. Исследования по теме диссертации были поддержаны 4 грантами РФФИ: 98-01-ООО 13-а, 07-07-00067-а, 07-0708036-3, 08-07-00129-а.

Диссертация состоит из введения, пяти тематических глав, заключения, списка литературы и приложений. Общий объем основного текста - 349 стр., включая 19 рисунков и 10 таблиц. Список литературы изложен на 14 стр. и содержит 153 наименования.

5.12. Выводы

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

2. Показано, что вероятностная мера р , минимизирующая среднеквадратичную невязку с мерой доверия g, минимизирует и среднеквадратичную невязку с сопряженной мерой g и со средней частью неточности р .

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

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

4. Исследованы свойства ближайшей в среднеквадратичном меры в классе так называемых симметричных мер доверия. Показано, что для симметричной меры доверия ближайшая вероятностная мера является равновероятной и будет мажорировать саму симметричную меру доверия.

5. Рассмотрена задача аппроксимации мер доверия к-аддитивными ме * i рами в среднеквадратичной метрике, связанной с преобразованием Мебиуса, а также равномерная аппроксимация мер доверия.

6. Рассмотрена и решена обратная задача вероятностной аппроксимации: для заданной вероятностной меры р найдено множество тех мер доверия Belp(X), для которых мера р является ближайшей в среднеквадратичном. Показано, что множество «ближайших» мер доверия является выпуклым и задается системой линейных уравнений и неравенств в 2'*' -1 -м пространстве.

7. Найдено семейство экстремальных точек выпуклого класса Belp{X) и получены оценки мощности крайнего множества этого класса.

8. Алгебраическое описание класса Belp(X) применено к решению задачи оценивания выигрышей коалиций игроков при заданных полезпостях отдельных игроков.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

7. В рамках исследования степени неточности мер информативности, аксиоматически введены понятия индекса неточности в классе нижних (верхних) вероятностей и линейного индекса неточности, как линейного положительного функционала определенного вида. Даны различные описания линейных индексов неточности: в терминах описания дескриптивных мер, преобразования Мёбиуса этих мер и др. Исследован важный класс линейных

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

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

8. Решена задача аппроксимации меры доверия вероятностной мерой, минимизирующей среднеквадратичную невязку. Получены различные представления ближайшей вероятностной меры. Доказано, что вероятностная мера, минимизирующая среднеквадратичную невязку с мерой доверия, минимизирует и среднеквадратичную невязку с сопряженной мерой и со средней частью неточности. Показано, что понятие «ближайшей» меры можно использовать для ранжирования возможностей появления событий в тех случаях, когда нижние и верхние вероятности не позволяют однозначно решить задачу ранжирования. Исследованы алгебраические, спектральные и аппроксимативные свойства преобразования, ставящего в соответствие мере доверия ближайшую в среднеквадратичном вероятностную меру. Рассмотрены свойства ближайшей в среднеквадратичном меры в классе так называемых симметричных мер доверия. Показано, что для симметричной меры доверия ближайшая вероятностная мера является равновероятной и будет мажорировать саму симметричную меру доверия. Рассмотрена задача аппроксимации мер доверия ^-аддитивными мерами в среднеквадратичной метрике, связанной с преобразованием Мебиуса, а также равномерная аппроксимация мер доверия.

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

1. Nixon M.S., Aguado A.S. Feature Extraction and 1.age Processing. - Newnes,1. Oxford, 2002.

2. Прэтт У. Цифровая обработка изображений. В 2-х книгах, кн.2. М.: Мир,1982.

3. Young I.T., Gerbrands J.J., van Vliet L.J. Fundamentals of Image Processing.

4. Delft University of Technology, Netherlands, 1998.

5. Attneave F. Some informational aspects of visual perception // Psychol. Rev.,61, 1954, pp. 183-193.

6. Bennet J.R., MacDonald J.S. On the Measurement of Curvature in a Quantised

7. Environment// IEEE Trans, on Computers, C-24(8), 1975, pp.803-820.

8. Freeman H., Davis L.S. A corner finding algorithm for chain-coded curves //

9. EE Trans. Computers, 26, 1977, pp.297-303.

10. Beus H.L., Tiu S.S.H. An improved corner detection algorithm based on chaincoded plane curves // Pattern Recognition, 20, pp.291-296, 1987.

11. Ansari N., Delp E.J. On detection dominant points // Pattern Recognition, 24,pp.441-451, 1991.

12. Melen Т., Ozanian T. A fast algorithm for dominant point detection on chaincoded contours // Proc. 5th Int. Conf. Comput. Anal. Images Pattern, 1993, pp.245-253.

13. Chetverikov D., Szabo Zs. A Simple and Efficient Algorithm for Detection of High Curvature Points in Planar Curves // Proc. 23rd Workshop of the Austrian Pattern Recognition Group, 1999, pp. 175-184.

14. Douglas D.H., Peucker Т.К. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature // The Canadian Cartographer, 10(2), 1973, pp.112-122.

15. Rutkowski W.S., Rosenfeld A. A comparison of corner-detection techniques for chain-coded curves // Technical Report TR-623, Computer Science Center, University of Maryland, 1978.

16. Ramer U. An iterative procedure for the polygonal approximation of plane closed curves // Computer Graphics Image Processing, 1, 1972, pp.244-256.

17. Tsai D.M., Chen M.F. Curve Fitting Approach for Tangent Angle and Curvature Measurements // Pattern Recognition, 27(5), 1994, pp.699-711.

18. Lee С. K., Haralick M., Deguchi K. Estimation of Curvature from Sampled Noisy Data // ICVPR '93, 1993, pp. 536-541.

19. Mokhtarian F., Mackworth A. Scale-based description and recognition of planar curves and two dimensional shapes // IEEE Trans. Pattern Anal. Mach. In-tell. 8, 1986, pp.34-43.

20. Pei S.-C., Lin C.-N. The detection of dominant points on digital curves by scale space filtering // Pattern Recognition, 25, 1992, pp. 1307-1314.

21. Rattarangsi A., Chin R.T. Scale-based detection of corners of planar curves // IEEE Trans. Pattern Anal. Mach. Intell. 14, 1992, pp.430-449.

22. Kass M., Witkin A., Terzopoulos D. Snakes: Active Contour Models // Int. J. CompVis., 1(4), 1988, pp.321-331.

23. Harris C., Stephens M.A. Combined Corner and Edge Detector // Proc. Fourth Alvey Vision Conference, 1988, pp. 147-151.

24. Canny J. A Computational Approach to Edge Detection // IEEE Trans, on PAMI, 8(6), pp.679-698, 1986.

25. Павлидис Т. Алгоритмы машинной графики и обработки изображений. -М.: Радио и связь, 1986.

26. Medioni G., Yasumoto Y. Corner detection and curve representation using cubic B-splines // Comput. Vision. Graph. Image Process. 39, 1987, pp.267-278.

27. Pei S.-C., Homg J.-H. Optimum approximation of digital planar curves using circular arcs // Pattern Recognition. 29 (3), 1996, pp.383-388.

28. Huang S.-C., Sun Y.-N. Polygonal approximation using genetic algorithms // Pattern Recognition. 32, 1999, pp.1409-1420.

29. Saint-Marc P., Chen J.-S., Medioni G. Adaptive smoothing: A general tool for early vision // IEEE Trans. Pattern Anal. Machine Intell. 13 (6), 1991, pp.514529.

30. Li L.Chen W. Corner detection and interpretation on planar curves using fuzzy reasoning//IEEE Trans. P AMI 21 (11), 1999, pp. 1204-1210.

31. Sklansky J., Chazin R.L., Hansen B.J. Minimum-perimeter polygons of digitized silhouettes // IEEE Trans. Comput., 21, 1972, pp.260-268.

32. Williams C.M. An efficient algorithm for the piecewise linear approximation of planar curves // Comput. Graph Image Process, 8, 1978, pp.286-293.

33. Sklansky J., Gonzalez V. Fast polygonal approximation of digitized curves // Pattern Recognition, 12, 1980, pp.327-331.

34. Pavlidis Т., Horowitz S.L. Segmentation of plane curves // IEEE Trans. Comput., 23, 1974, pp.860 870.

35. Kurozumi Y., Davis W.A. Polygonal approximation of the minimax method // Comput. Graph Image Process, 19, 1982, pp.248-264.

36. Dunham J.G. Optimum uniform piecewise linear approximation of planar curves // IEEE Trans. Pattern Anal. Mach. Intell. 8, 1986, pp.67-75.

37. Ray B.K., Ray K.S. Determination of optimal polygon from digital curve using LI norm // Pattern Recognition, 26, 1993, pp.505-509.

38. Wall K., Danielson P.-E. A fast sequential method for polygonal approximation of digitized curves // Comput. Vis. Graph. Image Process, 28, 1984, pp.220-227.

39. Wu J.-S., Leou J.-J. New polygonal approximation schemes for object shape representation//Pattern Recognition, 26, 1993, pp.471-484.

40. Rannou F., Gregor J. Equilateral polygon approximation of closed contours // Pattern Recognition, 29, 1996, pp.1105-1115.

41. Kolesnikov A., Franti P. Polygonal approximation of closed discrete curves // Pattern Recognition, 40, 2007, pp. 1282-1293.

42. Броневич А.Г., Лепский А.Е. Аксиоматический подход к задаче нахождения оптимального полигонального представления контура // Интеллектуальные системы, т. 9, вып.1-4, 2005, с.121-134.

43. Chen J.-M., Ventura J.A. Optimization models for shape matching of noncon-vex polygons // Pattern Recognition, 28, No.6, 1995, pp.863-877.

44. Sangineto E. An abstract representation of geometric knowledge for object classification // Pattern Recognition Letters, 24, 2003, pp.1241-1250.

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

46. Яглом A.M., Яглом И.М. Вероятность и информация. М.: Наука, 1973.

47. Шеннон К. Математическая теория связи // В кн. «Работы по теории информации и кибернетике». М.: ИЛ, с.243-332, 1963.

48. Колмогоров А.Н. Три подхода к определению понятия «количество информации» // Новое в жизни науки и технике. Сер. «Математика, кибернетика», №1, 1991, с.24-29.

49. Гоппа В.Д. Введение в алгебраическую теорию информации. М.: Наука. Физматлит, 1995.

50. Yager R.R. Entropy and specificity in a mathematical theory of evidence // International Journal of General Systems, 9(4), 1983.

51. Hohle U. Entropy with respect to plausibility measures // In Proceedings of the 12th IEEE International Symposium on Multiple-Valued Logic, Paris, 1982.

52. Higashi M., Klir G.J. Measures of uncertainty and information based on possibility distributions // International Journal of General Systems, 1983, 9(1).

53. Shafer G. A Mathematical Theory of Evidence. Princeton, N.J.: Princeton University Press, 1976.

54. Dubois D., Prade H. A note on measures of specificity for fuzzy sets // International Journal of General Systems 10(4), 1985, pp.279-283.

55. Klir G.J. Uncertainty and information: foundations of generalized information theory. John Wiley & Sons, Inc., 2006.

56. Harmanec D. Measures of uncertainty and information / http//ensmain.rug.ac.be/~ipp.

57. Bronevich A., Klir G.J. Axioms for Uncertainty Measures on Belief Functions and Credal Sets // Proc. of NAFIPS 2008, New York, 2008, # 60602.

58. Klette R., Rosenfeld A. Digital geometry: geometric methods for digital picture analysis. San Francisco, Morgan Kaufmann, 2004.

59. Figueiredo O. Advances in discrete geometry applied to the extraction of planes and surfaces from 3D volumes. These, Ecole Polytechnique federale de Lausanne, Lausanne, EPFL, 1999.

60. Александров А.Д., Нецветаев Н.Ю. Геометрия. М.: Наука, 1990.

61. Новиков С.П., Фоменко А.Т. Элементы дифференциальной геометрии и топологии. М.: Наука, 1987.

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

63. Marji М., Klette R., Siy P. Corner Detection and Curve Partitioning Using Arc-Chord Distance // Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, V.3322, 2004, pp.512-521.

64. Самарский А.А. Введение в численные методы. М.: Наука, 1982.

65. Никольский С.М. Курс математического анализа, Т.Н. М.: Наука, 1983.

66. Liu Н.С., Srinath M.D. Partial Shape Classification Using Contour Matching in Distance Transformation // IEEE Trans. On Pattern anal. And Mach. Intel., v.12, №11, 1990.

67. Гонсалес P., Вудс P. Цифровая обработка изображений. M.: Техносфера, 2006.

68. Никифоров А.Ф., Уваров И.Б. Специальные функции математической физики. М.: Наука, 1984.

69. Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. Приближение функций, дифференциальные и интегральные уравнения. -М.: Наука, 1967.

70. Нечеткие множества и теория возможностей. Последние достижения / под ред. Р.Р.Ягера. М., Радио и связь, 1986.

71. Сендов Б. Некоторые вопросы теории приближения функций и множеств в хаусдорфовой метрике // Успехи мат. наук, т.24, №5, 1969, с.141-178.

72. Pei S.-C., Horng J.-H. Optimum approximation of digital planar curves using circular arcs // Pattern Recognition. 29 (3), 1996, pp.383-388.

73. Horng J.-H. An adaptive smoothing approach for fitting digital planar curves with line segments and circular arcs // Pattern Recognition Letters, 24, 2003, pp.565-577.

74. Митропольский А.К. Теория моментов. M.: гос. изд. колх. и совх. литры, 1933.

75. Гихман И.И., Скороход А.В. Введение в теорию случайных процессов. -М. Наука 1977.

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

77. Рыжов А.П. Элементы теории нечетких множеств и ее приложений. М. изд-во МГУ, 2003.

78. Karkishchenko A.N. Invariant Fuzzy Measures on a Finite Algebra // Proc. of the North American Fuzzy Information Processing Society NAFIPS'96, USA, Berkeley, June 20-22, v.l, 1996.

79. Murofushi Т., Sugeno M. An interpretation of fuzzy measures and the Choquet integral as an integral with respect to a fuzzy measure // Fuzzy Sets and Systems, v.29, 1989, pp.201-227.

80. Данилов В.И. Лекции по теории игр. М., Российская экономическая школа, 2002.

81. Хьюбер Дж. П. Робастность в статистике. М.: Мир, 1984.

82. Klir G.J., Bronevich A. Measures of Uncertainty and Uncertainty-Based Information in GIT: A Historical Overview // NAFIPS'2008, New York, 2008, #60601.

83. Chateauneuf A., Jaffray J.Y. Some characterizations of lower probabilities and other monotone capacities through the use of Mobius inversion // Mathematical Social Sciences, 17, 1989, pp.263-283.

84. Denneberg D. Representation of the Choquet integral with the a -additive Mobius transform // Fuzzy Sets and Systems, 92, 1997, pp. 139-156.

85. Marinacci M. Ambiguous Games // Games and Economic Behavior 31, 2000, pp.191-219.

86. Справочная математическая библиотека. Функциональный анализ / под ред. С.Г. Крейна. М: Наука, 1964.

87. Ауман Р., Шепли Л. Значения для неатомических игр. М.: Мир, 1977.

88. Walley P. Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, 1991.

89. Кузнецов В.П. Интервальные статистические модели. М.: Радио и связь, 1991.

90. Прудников А.П., Брычков Ю.А., Марычев О.И. Интегралы и ряды. М.: Наука, 1981.

91. Эдварде Р. Функциональный анализ. М.: Мир, 1969.

92. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1981.

93. Дюбуа Д., Прад А. Теория возможностей. Приложения к представлению знаний в информатике. М.: Радио и связь, 1990.

94. Huber P.J., Strassen V. Minimax tests and the Neymann-Pearson lemma for capacities // The Annals of Statistics, v.l, No.2, 1973, pp.251-263.

95. Grabisch M. On lower and upper approximation of fuzzy measures by k-order additive measures // In 7th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU'98), Paris, France, 1998, pp.1577-1584.

96. Hammer P.L., Holzman R. On approximations of pseudo-Boolean functions // ZOR Methods and Models of Operations Research, 36: 1992, pp.3-21.

97. Boros E., Hammer P.L. Pseudo-Boolean optimization // Discrete Applied Mathematics 123, 2002, pp. 155-225.

98. Denneberg D., Grabisch M. Interaction transform of set function over a finite set//Information Sciences, 121, 1999, pp.149-170.

99. Smets P. The application of the matrix calculus to belief functions // International Journal of Approximate Reasoning 31, 2002, pp. 1-30.

100. Каркищенко A.H. О классе инвариантных нечетких мер на конечной алгебре // Мат-лы Международной конференции по мягким вычислениям и измерениям SCM-98. Санкт-Петербург, 1998, с.53-56.

101. Калужнин JI.A., Сущанский В.И. Преобразования и перестановки. М.: Наука, 1979.

102. Wallner A. Extreme points of coherent probabilities in finite spaces // International Journal of Approximate Reasoning, 44, 2007, pp.339-357.

103. Стенли P. Перечислительная комбинаторика. M.: Мир, 1990.

104. Айгнер М. Комбинаторная теория. М.: Мир, 1982.

105. Брёнстед А. Введение в теорию выпуклых многогранников. М.: Мир, 1988.

106. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинаторная теория многогранников). М.: Наука, 1981.

107. Каркищенко А.Н., Броневич А.Г., Бутенков С.А., Лепский А.Е. и др. Исследование возможности построения системы понимания изображений ограниченного класса сцен для задачи «Автопоиск» // Отчет о НИР. Руководитель А.Н. Каркищенко. 1997, 139с.

108. Каркищенко А.Н., Броневич А.Г., Бутенков С.А., Лепский А.Е. и др. Разработка методов распознавания изображений ограниченного класса сцен для задачи «Автопоиск» // Отчеты о НИР. Руководитель А.Н. Каркищенко. 1999, 2000, 2001 гг.

109. Каркищенко А.Н., Лепский А.Е., Безуглов А.В. Об одном способе векторного и аналитического представления контура изображения // Изв. ТРТУ. "Материалы Всерос. научно-техн. конф. "Интел. САПР-97", Таганрог: ТРТУ, №2(8), 1998, с.107-111.

110. Лепский А.Е. Кривизна и вес точки контура плоского изображения объекта // Материалы Всерос. науч.-техн. конф. с междун. участием "Компьютерные технологии в инж. и управл. деятельности", ТРТУ, Таганрог, 1999, с.21-22.

111. Каркищенко А.Н., Лепский А.Е. Оценивание кривизны точек плоского зашумленного контура. Некоторые вероятностные модели // Изв. ТРТУ. "Материалы Всерос. научно-техн. конф. "Интел. САПР-98", Таганрог: ТРТУ, №3(13), 1999, с. 194-197.

112. Лепский А.Е. Оценка числовых характеристик случайного веса в одномерной модели зашумления контура плоского изображения // Изв. ТРТУ. "Материалы Всерос. научно-техн. конф. "Интел. САПР-98", Таганрог: ТРТУ, №3(13), 1999, с. 197-200.

113. Лепский А.Е. Об оценивании кривизны плоского зашумленного контура // Обозрение прикладной и пром. мат-ки, М; изд-во ТВП, Т.6., В.1, 1999, с.171.

114. Броневич А.Г., Лепский А.Е. Два подхода к получению минимального полигонального представления контура // Тезисы докл. междун. науч. конф. «Искусственный интеллект-2000», п. Кацивели, Крым, 2000, с. 173-175.

115. Лепский А.Е., Бачило С.А., Рыбаков О.С. Оптимальный выбор параметров в задаче оценивания кривизны контура в одной вероятностной задаче зашумления изображения // VI Междун. конф. «Радиолокация, навигация, связь», Т.2. Воронеж, 2000, с.859-863.

116. Лепский А.Е. О нахождении минимального представления контура изображения как решение задачи нечеткой кластеризации // Сб. трудов Междун. конф. по мягким вычислениям и измерениям SCM-2000, т.1, Санкт Петербург, 2000г., с. 190-193.

117. Лепский А.Е., Бачило С.А., Рыбаков О.С. Анализ двух методов оценивания кривизны дискретной плоской зашумленной кривой // Сб. трудов 3-й междун. конф. «Цифровая обработка сигналов и ее применение», М., 2000, с. 12-14.

118. Броневич А.Г., Лепский А.Е. Аксиоматический подход в определении полигонального представления контура изображения // Обозрение прикладной и пром. мат-ки, М; изд-во ТВП, Т.7., вып.2, 2000, с.322-323.

119. Лепский А.Е. Оценка вероятности уклонения центроида полигонального представления плоского зашумленного контура // Обозрение прикладной и пром. мат-ки, М; изд-во ТВП, Т.7., 2000, с.379-380.

120. Броневич А.Г., Лепский А.Е. Два подхода к получению минимального полигонального представления контура // «Искусственный интеллект», №3, 2000, Донецк, с.421-427.

121. Каркищенко А.Н., Лепский А.Е. Об устойчивости центра масс, векторов и дескриптора Фурье векторного представления контура изображения // Автоматика и телемеханика, №3, 2001, с. 141-151.

122. Лепский А.Е. Исследование устойчивости оценок кривизны к уровню зашумления контура // В сб. трудов Междун. конгресса «Искусственный интеллект в XXI веке», т.2, М.: Физматлит, 2001, с.516-524.

123. Лепский А.Е. О систематической ошибке оценивания кривизны контура методом аналитического сглаживания // Обозрение прикладной и пром. мат-ки, М; изд-во ТВП, Т.8. вып.1, 2001, с.254-255.

124. Лепский А.Е. Об аппроксимации одного класса бета-распределений нормальным законом // Обозрение прикладной и пром. мат-ки, М; изд-во ТВП, Т.8. вып.2, 2001, с.633-634.

125. Броневич А.Г., Лепский А.Е. Операторы свертки нечетких мер // Обозрение прикладной и пром. мат-ки, М; изд-во ТВП, Т.8. вып.2, 2001, с.748-749.

126. Лепский А.Е., Броневич А.Г., Бачило С.А. Выделение контрольных точек на основе меры информативности контура // В сб. трудов 4-й междун.конференции «Цифровая обработка сигналов и ее применение», М. 2002, с.288-291.

127. Lepskiy A., Bronevich A., Bachilo S.A. Extraction of control points based on an informative quantity measure // Proc. of the 4-th International Conference "Digital signal processing and its applications", 2002, Moscow, Russia, p.291.

128. Броневич А.Г., Каркищенко A.H., Лепский А.Е. Разности функций множеств // Обозрение прикладной и пром. мат-ки, М; изд-во ТВП, Т.9. вып. 1, 2002, с. 117-118.

129. Bronevich A.G., Lepskiy А.Е. Operators for convolution of fuzzy measures, Soft Methods in Probability, Statistics and Data Analysis // ed.: Przemyslaw Grzegorzewski . Heidelberg; New-York: Physical-Verl., 2002, pp.84-91.

130. Лепский А.Е. Инвариантные нормы на пространстве кривых // Труды межд. конф. «Искусств, интел. системы» (IEEE AIS'02) и «Интеллектуальные САПР» (CAD-2002). М.: Физматлит, 2002, с.440-447.

131. Лепский А.Е. Нахождение минимального представления контура изображения как решение задачи нечеткой кластеризации // Известия вузов России. Радиоэлектроника, №1, 2002, с.35-39.

132. Броневич А.Г., Лепский А.Е. Аксиоматический подход к определению индексов неточности нечеткой меры // Сб. трудов 2 междун. научно-практ. Семинара «Интегрированные модели и мягкие вычисления в искусственном интеллекте». М.: Физматлит, 2003, с. 127-130.

133. Bronevich A., Lepskiy A. Geometrical fuzzy measures in image processing and pattern recognition // Proc. of the 10th IFSA World Congress, 2003, Istanbul, Turkey, pp. 151-154.

134. Каркищенко A.H., Броневич А.Г., Лепский А.Е. Неаддитивные меры: приложения к обработке информации с высокой неопределенностью // Вестник Южного научного центра РАН, т.1, вып.З, 2005, с.90-95.

135. Каркищенко А.Н., Лепский А.Е. Методы вычисления степени неточности в классе нижних вероятностей // В сб. трудов всерос. научной конф.по нечетким системам и мягким вычислениям НСМВ-2006. М: Физматлит, 2006, с. 140-149.

136. Lepskiy А.Е. The Linear Imprecision Indices on the Lower Probabilities // Proc. of the 11th IPMU Conference, Paris, pp. 1724-1731.

137. Лепский А.Е. О вероятностной мере, наименее уклоняющейся от симметричной части неточности // Материалы IX Междун. конф. "Интел, системы и компьют. науки", т.1, ч.2, М.: Изд-во мех.-матем. фак-та МГУ, 2006, с. 172-174.

138. Лепский А.Е. Об устойчивости центра масс векторного представления в одной вероятностной модели зашумления контура изображения // Автоматика и телемеханика, №1, 2007, с.82-92.

139. Лепский А.Е. Вероятностная аппроксимация мер доверия // Сб. трудов IV-й Межд. научно-практич. конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте". В 2-х томах, т.1. — М.: Физматлит, 2007, с.212-219.

140. Bronevich A., Lepskiy A. Measuring uncertainty with imprecision indices // Proc. of the Fifth International Symposium on Imprecise Probabilities and Their Applications (ISIPTA'07), Prague, 2007, pp.47-56.

141. Лепский А.Е. Оптимальное проецирование нижних вероятностей на семейство вероятностных мер // Вестник Ростовского государственного университета путей сообщения. 2007. №3, с. 139-143.

142. Lepskiy A., Bronevich A. Various representations and algebraic structure of linear imprecision indices // Proc. of the 5th EUSFLAT Conference, Ostrava, Chezh Republic, 2007, v.l, pp.297-304.

143. Гончаров A.B., Горбань A.C., Каркищенко A.H., Лепский А.Е. Поиск портретных изображений по содержанию // Сб. работ участников конкурса «Интернет-математика 2007». Екатеринбург: изд-во Урал, ун-та, 2007, с.56-64.

144. Каркищенко А.Н., Лепский А.Е. Применение понятия информативности в распознавании образов // Материалы восьмой междун. науч.-техн. конф.

145. Искусственный интеллект. Интеллектуальные системы», Донецк: изд. «Наука i освгга», 2007, с.208-213.

146. Каркищенко А.Н., Лепский А.Е. Индекс неточности и его применение к оцениванию априорной информативности систем // Известия РАН. ТиСУ, №1.-2008, с.94-100.

147. Лепский А.Е. Симметричный линейный индекс неточности в классе нижних вероятностей // Известия РАН. ТиСУ, №2. 2008, с.35-42.

148. Lepskiy А.Е. The class of nearest belief functions to a given probability measure // Proc. of the NAFIPS'08, New York. 2008, # 60608.