Войти в мой кабинет
Регистрация
ГОТОВЫЕ РАБОТЫ / ДИССЕРТАЦИЯ, ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

Разработка системы распознавания образов.

irina_krut2019 4080 руб. КУПИТЬ ЭТУ РАБОТУ
Страниц: 136 Заказ написания работы может стоить дешевле
Оригинальность: неизвестно После покупки вы можете повысить уникальность этой работы до 80-100% с помощью сервиса
Размещено: 06.03.2020
Магистерская диссертация 137 страницы, 58 рисунков, 73 источника, 2 приложения; 9 листов графического материала формата А1. СИСТЕМА РАСПОЗНАВАНИЯ ОБРАЗОВ, ЗНАКОВОЕ ПРЕДСТАВЛЕНИЕ ИЗОБРАЖЕНИЙ, РАСПОЗНАВАНИЕ ЛИЦ, ИДЕНТИФИКАЦИЯ ЛИЦ, ДЕТЕКЦИЯ ЛИЦ Объектом исследования являются современные системы распознавания образов. Цель выпускной квалификационной работы - разработка системы распознавания образов на основе знакового представления изображений и разработка нового эффективного алгоритма обнаружения и идентификации людей. В процессе работы были получены следующие теоретические и прикладные результаты: а) проводились исследования свойств знакового представления изображений и его информативности; б) разработан метод классификации знаковых представлений для задач распознавания образов; в) на основе предложенного метода классификации знаковых представлений разработан общий алгоритм классификации знаковых представлений и его модификаций для решения актуальных задач распознавания образов;г) разработана научно-исследовательская схема алгоритмов обнаружения и распознавания людей, а также обнаружения нечетких повторений в больших наборах изображений. Полученные результаты показывают, что разработанные на основе знакового представления изображений алгоритмы распознавания позволяют достичь высоких показателей качества, которые, в ряде случаев, превосходят современные аналоги.
Введение

Распознавание образов и анализ изображений является одной из наиболее активных областей искусственного интеллекта. Стремительное совершенствование аппаратных возможностей различных устройств для хранения, передачи, обработки и извлечения информации требует постоянного развития существующих и разработки новых способов идентификации и анализа изображений и сигналов. Из совокупности задач распознавания образов и анализа изображений можно выделить отдельную категорию задач, которые связаны с распознаванием лиц. С каждым годом эта сфера привлекает к себе внимание все больше исследователей, о чем говорит статистика количества публикаций на тему распознавания лиц, которые входят в каталог ScienceDirect, являющейся одной из ведущих библиотек, предлагающих публикации из более чем 2500 рецензируемых журналов и свыше 11000 книг. В процессе разработки алгоритма распознавания лиц, стабильным к изменениям условий освещения, была предложена идея знакового представления изображения, которая описывается компактным образом с использованием соотношения наборов пикселей на квазипорядке. Доказана эффективность предложенного подхода. Алгоритмы показывают высокие уровни точности и полноты распознавания, и для ряда задач выходит за пределы текущего уровня. Распознавание лиц представляет собой широкую задачу, а именно: распознавание лиц на изображениях (обнаружение лица, основные этапы распознавания), поиск этого лица по базе данных изображений человека (распознавание), антропометрические характеристики лица (овала лица, контуров губ, носа, бровей, центров зрачков, уголки глаз), оценка возраста, определение пола, распознавание эмоций. Интерес к проблеме идентификации лица человека в фотографии возник в рамках развития способов криминологии в конце XIX века. Первый метод идентификации человека основан на сравнении отношений между расстояниями между точками измерения человеческого лица. Для их применения нужно знать угол съемки (на практике используются фото модели головы, для всех возможных углов, для заданного шага в широте и долготе угла обзора) и точность характеристик человеческого тела. С появлением электронно-вычислительных машин, естественно, хочется перенести существующие методы в программу компьютерной обработки изображения, однако исследователи на пути столкнулись с целым рядом проблем. [1] Во-первых, автоматическое позиционирование для судебно-медицинских характеристик лица (форма лица, высота лба, кончик носа, точки ушей, уголки губ, уголки глаз) – задача, которая плохо оформлена и трудна. Во-вторых, современные возможности цифровых средств визуализации не дают возможности обеспечить нужное пространственное разрешение (в том числе разрешение яркости) для автоматического обнаружения этих точек. Такие ситуации не позволяют использовать существующие методы идентификации лиц и требуют разработки новых способов. Одна из первых ссылок на алгоритмы распознавания людей в СССР, специально разработанные для компьютеров и не требующие человеческого вмешательства, дана в монографии B.C. Файна, опубликованной в 1970 году. В монографии обсуждается применение теории непрерывных групп, включая идентификацию людей. Для того чтобы сформировать цифровое изображение, применялось входное устройство, которое создавало 108х64 элементов (пикселей) при 64 градациях яркости. В качестве информационной характеристики используется локальные экстремумы координата функции яркости изображения и ее градиентный режим. [1] Самые современные методы идентификации человека основываясь на работе Matthew Turk и Alex Pentland, они предложили метод распознавания лиц, основанный на методе анализа главных компонент (PCA), известном как "Eigenfaces" (собственные лица), также известный как преобразование Каруне-на-Лоэва (Кагhunen-Loeve). Суть метода состоит в том, что вектор признаков проецируется из большой размерности Ф исходного пространства в подпространство малой размерности Ф', которое, таким образом, строит основу, чтобы обеспечить статистическую независимость компонента вектора признаков, и в этом случае процесс распознавания лиц является тестовым изображением f, присвоенным определенному типу подпространства Cli*, если d{f’, Cli* } = mini d, {f’, Cli}, где d - метрика в пространстве Ф', а f’= Prф , f - проекция вектора признаков на подпространство Ф'. Многие исследователи отмечают, что преимущественный недостаток данного метода заключается в очень большой чувствительности к переменам в условиях регистрации изображений. При достаточно объемных выборках минимальное расстояние в пространстве Ф' соответствует полученным при схожих условиях освещения изображениям различных людей, а не изображениям одного и того же человека. [2, 3, 4, 5, 6, 7, 8, 9, 10] Проблемы воздействия на качество идентификации освещенности являются сходными для всякого метода анализа изображений при работе с фотографиями, которые получались в условиях естественных. По этой причине важным направлением исследования в настоящей области является разработка способов, которые бы обладали наименьшей чувствительностью изменениям условий освещения. Имеющиеся методы условно могут быть разделены на два подхода. Первый состоит в предварительной обработке фотографии, к примеру, с помощью нормализации изображения путем выравнивания гистограммы яркостей. Более перспективный второй подход имеет переход от исходного изображения к специальному представлению, устойчивому к изменениям условий освещения. Одним из примеров являются различные методы выделения краев изображения (методы Превитта, Кенни, Собеля). В работе В. Froba и С. Kublbeck предлагается использовать функцию яркости изображения в направлении градиентного поля для формирования информационной характеристики проблемы обнаружения лица. [11] Вытекает отметить, что выбор какого-либо определенного представления изображений является более экспериментальным, чем теоретический, так как на сегодняшний день нет универсальной модели, позволяющей учитывать общие условия регистрации изображений. Наиболее эффективным для задач распознавания лиц с точки зрения точности и полноты распознавания является представление изображения как "самооценки" изображения (SQI, Self Quotient Image), а также использование локального двоичного шаблона (local Binary Patterns, LBP). Эти методы могут значительно улучшить качество распознавания лиц, однако, в некоторых случаях, уровень предложения не является удовлетворительным. [12] В настоящей выпускной квалификационной работе предложен метод знакового представления изображений – метод представления данных о изображениях для задачи распознавания образа, который естественно позволяет учитывать искажающие функции яркости изображения, обусловленные формированием изображения, тем самым обеспечивая переход от начального представления сигнала или изображения к некоторым признакам, идея которых находит применение в некоторых работах по распознаванию изображений и анализу случайно протекающих процессов. Аналог, представленный символом, представляет собой цепной код, впервые который предложен Фрименом (H.Freeman) описание формы объекта. Код цепи – это способ определения контура с использованием соседних последовательностей пикселей xi, т. е. ?(x_i)?_(i=1)^N двумерного вектора xi, имеющего целочисленные координаты, причем если ?xi = xi+1 – xi = (l, m), где i ? {1,…, N - 1}, то l, m ? {-1,0,1}. Таким образом, в цепочке код, следующий пиксель по отношению к предыдущему положению пикселя по паре цифр (l, m) или эквивалента, их символы кодируются. [13] Наиболее близкими аналогами, обозначенными символом, являются хорошо известные морфологические методы, предложенные Ю.П. Пытьевым. Морфологический подход Пытьева основан на идее деления изображения на области, соответствующие постоянной яркости изображения, а само изображение представлено в виде взвешенной ортогональной характеристической функции, которая отличается только от подмножества областей, соответствующих постоянному значению яркости. Набор изображений можно получить из исходного изображения, действуя на некоторую функцию значений яркости, называемую "формой" изображения. В предложенном подходе мы рассмотрим полное и оконное знаковое представление. Множественность изображений, соответствующих полному символьному представлению, согласуется с понятием формы Пытьева в строго увеличенном классе преобразования яркости. Однако набор изображений, соответствующий символу оконного представления, представлен более широким, чем изображение, представленное по Пытьеву. [14, 15, 16] M.В. Харинова разработала монографию, в которой исвытекается использование псевдотроичной системы для построения изображений локальных изоморфизмов и изоморфизмов изображений. В однородном изображении изображение может изменять значение яркости пикселя, сохраняя при этом порядок соотношения между исходной яркостью пикселей (большой/маленький/равный). В локально изоморфных изображениях требуется сохранить порядок отношений яркости только для соседних пикселей. Полное знаковое представление в предложенном методе, соответствует изображению изоморфному, тогда как знаковое оконное представление соответствует локально изоморфному изображению. [17] М.В. Болдин и соавторы в своей монографии используют не параметрический подход для анализа, согласно которому в основе выводов лежат признаки функций. Подобный подход в некотором смысле является частным случаем анализа ранжированных значений. [18] Якобс (С. Jacobs) и соавторы предлагают метод поиска изображений визуального сходства, в основе которого лежит на вэйвлет-преобразование. В результате вэйвлет-преобразования изображения получают матрицу коэффициентов того же размера, что и само изображение, в то время как символы первых n максимальных коэффициентов вэйвлет-преобразования, и индексы указанных коэффициентов в матрице вейвлет-преобразования используются в качестве графа. Наиболее интересной проблемой является устойчивость к воздействию шума изображения символьного представления, и разработка способов классификации образов на базе символьных представлений. [19] Важнейшей характеристикой всякого представления изображения является инвариантность представления определенных изменений самого изображения, которое, естественно, называется мерой устойчивости. Стабильность является важным атрибутом представления изображений с практической точки зрения, так как реальная система обработки изображений не обрабатывает идеальные изображения, а искажает и шумит изображения. Таким образом, небольшие изменения не должны существенно влиять на исход системы технического зрения, а скорее демонстрировать устойчивость к шуму, который является характеристикой зрительной системы человеческого организма. Мера стабильности – одинаковое представление некоторых числовых характеристик мощности начального изображения. Естественный способ объяснить это искажение изображения, чтобы доказать закон вероятности некоторых распределений искажений. В рамках данной выпускной квалификационной работы определены и исследованы мери устойчивости для условных представлений статистически независимых аддитивных шумовых ситуаций. Разработанные наиболее распространенные современные методы распознавания образов, основаны на предположении о векторном представлении информации о изображении в метрическом линейном пространстве признаков. Так присутствие в пространстве признаков мери позволяет использовать простой метод классификации, основанный на измерении расстояния между тестом и эталонным изображением. Присутствие в пространстве признаков линейной структуры дает возможность применять разные алгоритмы кластеризации признаков, такие как метод k - среднего (k-means) значения, метод классификации на основе нейронных сетей, а также относится к разбиению пространства признаков на гиперплоскости, соответствующие его ядру. Символьное представление изображения представляет собой отношение квазипорядка на множестве пикселов изображения, которое не может быть непосредственно представлено в виде вектора в некоторых линейных пространствах признаков, что делает невозможным прямое применение большинства существующих способов машинного обучения и моделирования. Кроме того, актуальна разработка способов классификации знакового представления, признаков близости специальных мер и представления признаков на их основе в задачах распознавания образов. Введение и развитие представления изображений обосновано на основе способов и алгоритмов рас познавания образов и только в том случ., если определенные критерии качества нового метода позволяют решить задачу распознавания образов с лучшем качеством, чем аналоги, с практической точки зрения. Критериями качества образцов могут быть показатели первого и второго рода ошибок, показатели точности и полноты поиска заданного изображения в тестовом наборе, а также объем вычислительных ресурсов, необходимых для решения задачи. Оценка качества алгоритма распознавания в этом смысле является сложной задачей, заключающейся, как правило, в статистической оценке рассматриваемых показателей через тестовые наборы. С точки зрения исследования, результаты проводимой оценки качества являются ценными только при условии, что их могут повторить другие исследователи для сравнения недавно разработанных алгоритмов с существующими. По этой причине алгоритмы должны быть оценены на общедоступном наборе тестовых изображений. Для того чтобы увидеть, что результаты оценки также дают практическую ценность, нужно, чтобы выборка, используемая для оценки, была репрезентативной. Проблема репрезентативности выборки является чрезвычайно сложной и часто не затрагивается. Для задач распознавания лиц репрезентативной мерой может быть, к примеру, количество фотографий, представленных в выборке, или количество полученных изображений, характерных для съемки сцены. Также для того, чтобы сделать тестовый набор изображений, пригодных для автоматического статистического алгоритма оценки качества, нужно сделать набор изображений с описанием метаданных изображения объекта данного класса. Примерами такого рода метаданных могут быть возраст, пол, координаты центра зрачка, идентификатор человека, данные о относительном положении источника света и угол камеры. По этой причине нужно разработать комплекс программ, осуществляющих статистическую оценку качественных показателей алгоритмов по распознаванию образов на общедоступных тестовых изображениях. Вместе с тем нужно предусмотреть возможность быстрой реализации программного обеспечения для добавления новых алгоритмов на испытательный комплекс программ, а также новых наборов изображений и новых форматов метаданных. Подход, который предложен в рамках выпускной квалификационной работы, учитывает не только проблемы распознавания лиц, но и другие проблемы анализа изображений. А именно, рассмотрена задача обнаружения размытых изображений, повторяющихся в больших множествах. Размытое повторение - это изображение одной и той же сцены, полученное при аналогичных условиях. К примеру, несколько последовательных кадров видеопоследовательности можно считать размытым повторением. Сложность проблемы обусловлена несколькими причинами. Во-первых, понятие "нечеткое повторение" не является строгим и может толковаться по-разному в различных ситуациях. Во-вторых, несмотря на то, что несколько последовательных кадров серии видео размыты и повторяются, очевидно, что в течение значительного периода времени кадры далеко отдельные друг от друга, размытыми, скорее всего, не будут. Иными словами, решение проблемы обнаружения нечетких повторений – это отношение допуска на множестве изображений (в отличие от отношения эквивалентности, отсутствует транзитивность). И, наконец, главная проблема связана с большим количеством коллекций современных изображений. К примеру, в современных интернет-поисковых системах индекс содержит около 109 изображений, по этой причине простое сравнение всех пар изображений требует недопустимо больших вычислительных ресурсов. Эта проблема актуальна для систем информационно-поисковых, так как одним из основных требований к таким системам являются различные результаты, выдаваемые пользователю. По этой причине нужно разработать методику обнаружения нечетких повторений, которая, с одной стороны, должна быть достаточно простой для анализа больших наборов изображений в обозримом будущем и, с другой стороны, должна быть достаточно надежной для обеспечения показателей точности и полноты классификации изображений. Целью данной выпускной квалификационной работы является разработка системы распознавания лиц на базе знакового представления изображения и создание универсального способа классификации образов, включая новый эффективный алгоритм обнаружения, идентификации людей. Задачи исследования: исследовать характеристики знакового представления изображений; проанализировать их устойчивость к аддитивным шумам на изображениях; создать метод классификации, основанный на знаковом представлении; составить эффективные алгоритмы для идентификации и обнаружения образов; разработать комплекс программ для оценки статистических показателей качества алгоритмов распознавания образов. Научные результаты, выносимые на защиту: Исследованы свойства оконного знакового представления; Определены оценки устойчивости, изучены геометрические структуры множества знаковых представлений; Составлены способы классификации знаковых представлений, в основе которых лежат функции расстояния, которые дают возможность увеличить разделяющие способности классификаторов; На базе предложенных способов классификации составлены общие алгоритмы классификации знаковых представлений, которые позволяют эффективно решать задачи, связанные идентификацией и детекцией образов. Выпускная квалификационная работа включает в себя введение, четыре главы, заключение, список использованных источников и два приложения. Первая глава посвящена описанию понятия знакового представления изображения и изучению его свойств, связанных с задачами распознавания лиц и анализа изображений. Рассмотрены примеры оконного и полного знаковых представлений. [19] Также в этой главе формулируется и доказывается гипотеза, позволяющая определить, в каком случае произвольное отношение множества пикселов представляет собой оконное знаковое представление. Построена процедура по восстановлению изображения, которая исчерпывающе описывает совокупность изображений, характеризующих знаковое представление. Изучена мера неопределенности и мера информативности знакового представления изображения. [20, 21] Рассмотрена группа преобразований, характеризующихся инвариантным знаковым представлением. Изучена структура и свойства классов эквивалентности, образованных изображениями, относящимися к общим знаковым представлениям. [22] Охарактеризована мера устойчивости знакового представления, являющаяся свойством его оставаться без изменений при незначительных искажениях изображений. Для заданной закономерности распределения шума получена аналитическая оценка устойчивости знаковых представлений с использованием алгебраических подходов к изучению групповых свойств инвариантного преобразования знакового представления. В отдельности рассматривался вариант с нормальным распределением шума. Результаты статистического моделирования подтверждают справедливость установленных аналитических оценок устойчивости знаковых представлений. Вторая глава посвящена исследованиям и разработке общих способов классификации знаковых представлений. Рассмотрены неметрические и метрические способы классификации знаковых представлений. В начале главы рассмотрены неметрические способы классификации, строится классификатор на основе деревьев решений и байесовский классификатор знаковых представлений. Во второй части второго раздела вводятся понятия расстояния и метрики на знаковых представлениях. Предлагается подход к построению функции расстояния, в основе которого лежит измерение количества информации с помощью неаддитивных мер. Показывается, как может быть построена метрика по энтропии Шеннона, а также функция расстояния по относительной энтропии. Рассмотрены задачи построения эталонного образа для осуществления классификации по функции расстояния. [23, 24, 25, 26] В третьей главе описывается решение актуальных вопросов, связанных с распознаванием образов и анализом изображения при помощи алгоритмов и способов знакового представления изображения. Описывается решение задач по идентификации образов, детекции образов на изображении и обнаружении нечетких копий в большой коллекции изображений. [27, 28, 29, 30, 31, 32, 33] Детекция лиц представляет собой важный предварительный этап практически всякой задачи по распознаванию лиц. Приведен литературный обзор применяющихся в настоящее время способов и подходов к детекции лиц, который показывает, что основная проблема состоит сильном влиянии освещения на точность и полноту детекции. Знаковое представление изображений сохраняет устойчивость к изменениям в условиях освещения и дает возможность добиться высоких показателей точности и полноты в сравнении с аналогами, это также относится к изображениям, имеющим низкое разрешение. Описаны алгоритмы по детекции лиц, которые реализуют описанные во второй главе методы классификации знаковых представлений. Исследована проблема с множественной детекцией лиц, заключающаяся в том, что детектором лиц возвращается совокупность пересекающихся и вложенных результатов, которые требуют кластеризции на отдельные лица. [33, 34, 35] Существует две основные постановки задачи идентификации лиц: первая задача – биометрическая идентификация по изображению лица, состоит в том, что наблюдаемое лицо относят к одному из классов, вторая задача – информационный поиск, состоит в нахождении на лицо-запрос наиболее похожих лиц. Для каждой постановки написаны алгоритмы, которые реализуют предложенные способы классификации знаковых представлений. [58] Актуальной задачей является выявление в больших коллекциях изображения нечетких дубликатов для систем информационно-поисковых, так как разнообразие поисковой выдачи является одним из критериев качества поиска. В этой связи появляются задачи, связанные с группировкой изображений, которые представляют собой нечеткий дубликат. Нужно заметить, что эта задача не представляет собой основной цели исследования, а только показывает возможности использования знакового представления изображений для задач анализа изображений. В конце третьей главы приводится обоснование актуальности этой задачи, содержится исследование современных способов решения. Рассмотрены алгоритмы описывающие обнаружение нечетких дубликатов, которые основаны на знаковом представлении. Предложен способ уменьшения оперативной памяти и процессорного времени для эффективности решения задачи. Четвертая глава посвящена реализации алгоритмов, которые были рассмотрены в третьей главе, и проблемам оценки качества этих алгоритмов. Программные модули, которые были разработаны в процессе исследований, в первую очередь, предназначаются для изучения разработанных алгоритмов, а именно, статистических оценок ошибки 1-го и 2-го рода, а также точности и полноты на тестовой коллекции изображений. Модули программ выполняются как динамически подключаемые библиотеки и применяются в процессе разработки сторонних приложений. Реализация программная осуществлялась с использованием открытого ПО на языках программирования Python и С++, использовались открытые библиотеки Py lab, Open MP, Boost, Open CV и другие. В выпускной квалификационной работе значительное внимание отведено вопросам оценки качества разработанных алгоритмов распознавания. Эксперименты по оценке качества разработанных алгоритмов проводились с использованием общедоступных тестовых баз изображений. Помимо качественных показателей, использовались оценки точности и полноты, распространенные в информационном поиске. Относительно каждой рассматриваемой задачи обсуждалась интерпретация данных и особенности применения показателей. В работе содержатся результаты проведенных оценок качества разработанных алгоритмов идентификации, детекции лиц, обнаружение нечетких дубликатов. [36, 37, 38, 39, 40] В приложении 1 содержится краткий обзор существующих тестовых наборов, которые участвовали в тестировании разработанных алгоритмов. Приложение 2 содержит примеры программной реализации разработанных модулей. Результаты исследования использовались в публикациях сборников: а) Актуальные проблемы информационной безопасности. Теория и практика использования программно-аппаратных средств. СамГТУ Самара. б) Информационно-измерительные и управляющие системы. СамГТУ Самара.
Содержание

Введение 7 1 Знаковое представление изображений и его свойства 20 1.1 Введение знакового представления изображений 20 1.2 Исследование свойств знакового представления изображений 22 1.2.1 Восстановление множества изображений по знаковому представлению 22 1.2.2 Информативность и неопределенность знакового представления 25 1.2.3 Структура множества инвариантных преобразований изображений 35 1.3 Устойчивость знаковых представлений 38 1.3.1 Определение устойчивости знакового представления изображений 39 1.3.2 Выражения для вычисления F-устойчивости полного знакового представления 40 1.3.3 Гауссовская устойчивость полных знаковых представлений изображений 43 1.3.4 Устойчивость оконного знакового представления 46 1.3.5 Численная оценка устойчивости знакового представления 47 1.4 Выводы 48 2 Методы классификации знаковых представлений изображений 50 2.1 Неметрические методы классификации 50 2.1.1 Байесовский классификатор 50 2.1.2 Деревья решений 53 2.2 Метрические методы классификации 54 2.2.1 Введение метрики на знаковых представлениях 54 2.2.2 Классификация знаковых представлений на основе функций расстояния 60 2.2.3 Оценка ошибок классификации знаковых представлений изображений 61 2.3 Выводы 64 3 Применение знакового представления изображений в задачах распознавания образов 66 3.1 Алгоритмы классификации знаковых представлений 66 3.1.1 Построение знакового представления по изображению и вычисление расстояния 66 3.1.2 Алгоритм классификации знаковых представлений на основе функции правдоподобия 69 3.1.3 Алгоритм классификации знаковых представлений на основе функций расстояния 71 3.2 Детекция лиц 74 3.2.1 Обзор современных способов детекции лиц 74 3.2.2 Детекция лиц на основе знакового представления 79 3.3 Идентификация лиц 82 3.3.1 Обзор современных способов идентификации лиц 83 3.3.2 Распознавание лиц на основе алгоритмов классификации знаковых представлений 85 3.3.3 Стратегии идентификации лиц 86 3.4 Обнаружение нечетких дубликатов в больших коллекциях изображений 87 3.4.1 Обзор современных способов поиска нечетких дубликатов изображений 89 3.4.2 Алгоритмы обнаружения нечетких дубликатов изображений на основе знакового представления 90 3.5 Выводы 91 4 Реализация и оценка качества алгоритмов распознавания, основанных на знаковом представлении изображений 93 4.1 Оценка качества алгоритмов и результаты экспериментов 93 4.1.1 Методы статистической оценки показателей качества алгоритмов распознавания образов 94 4.1.2 Оценка показателей качества детекции лиц 96
Список литературы

1. Ahonen T. Face recognition with local binary patterns. L.: Lecture Notes in Computer Science 3021, 2004. 2. Albiol A. An unsupervised color image segmentation algorithm for face detection applications. L.: in Proceedings of International Conference on Image Processing, 2001. 3. Ballard D.H. Generalizing the hough transform to detect arbitrary shapes. L.: Pattern recognition, 1981. 4. Bao P. Canny edge detection enhancement by scale multiplication. L.: Transactions on Pattern Analysis and Machine Intelligence, 2005. 5. Bradski G.R. Learning OpenCV. Computer vision with the OpenCV library. L.: O'Reilly Media, 2008. 6. Canny J. A. computational approach to edge L.: Trans Pattern Analysis and Machine Intelligence, 1986. 7. Breiman J. H. Friedman R. A. Classification and regression trees. L.: Cole Advanced Books & Software, 1984. 8. Terrillion M. N., Shirazi H., Fukamachi S. Comparative performance of different skin chrominance models and chrominance spaces for the automatic detection of human faces in color images. L.: In Proceedings of the International Conference on Face and Gesture Recognition, 2000. 9. DeMenthon D. Video retrieval of near-duplicates using k- nearest neighbor retrieval of spatio-temporal descriptors. L.: Multimedia Tools and Applications, 2006. 10. Foo J. Zobel, R. Detection of near-duplicate images for web search. L.: Proceedings of the 6th ACM International Conference on Image and Video Retrieval, 2007. 11. Duda R.O. Pattern classification. L.: Wiley-Interscience, 2001. 12. Escolano F. Information Theory in Computer Vision and Pattern Recognition. L.: Springer Verlag, 2009. 13. Delac M. Face Recognition. L.: I-TECH Education and Publishing, 2007. 14. Zhao R. Chellappa P.J. Face recognition: A literature survey. L.: ACM Computing Surveys (CSUR), 2003. 15. Phillips H., Wechsler J., Huang, P.J. The feret database and evaluation procedure for face-recognition algorithms. L.: Image and Vision Computing, 1998. 16. Phillips H., Moon S.A., Rizvi P.J. The feret evaluation methodology for face-recognition algorithms. L.: Transactions on Pattern Analysis and Machine Intelligence, 2000. 17. Wang W., Josephson Q. Filtering image spam with near-duplicate detection. L.: In Proceedings of the Fourth Conference on Email and AntiSpam, 2007. 18. Foo J.J. Advances in Databases: Concepts, Systems and Applications. L.: Advances in Databases: Concepts, Systems and Applications, 2008. 19. Foo J.J. Advances in Multimedia Modeling. L.: Advances in Multimedia Modeling, 2006. 20. Freeman H. Computer processing of line-drawing images. L.: ACM Computing Surveys (CSUR), 1974. 21. Freund Y. A decision-theoretic generalization of on-line learning and an application to boosting. L.: Journal of Computer and System Sciences, 1997. 22. Froba B. Audio- and Video-Based Biometric Person. L.: Springer Berlin, 2001. 23. Froba B. Robust face detection at video frame rate based on edge orientation features. L.: Proceedings of the Fifth International Conference on Automatic Face and Gesture Recognition, 2002. 24. Phillips T.W. Scruggs A.J. Frvt 2006 and ice 2006 large-scale results. L.: National Institute of Standards and Technology, 2007. 25. Garcia C. Face detection in color images using wavelet packet analysis. L.: ICMCS Proceedings, 1999. 26. Georghiades A.S. From few to many: Illumination cone models for face recognition under variable lighting and pose. L.: Trans. Pattern Anal. Mach. Intelligence, 2001. 27. Georghiades A.S. From few to many: Illumination cone models for face recognition under variable lighting and pose. L.: Transactions on Pattern Analysis and Machine Intelligence, 2001. 28. Grother P. Face recognition vendor test 2002 performance metrics. L.: Proceedings 4th International Conference on Audio Visual Based Person Authentication, 2003. 29. Grother P.J. Report on the evaluation of 2d still-image face recognition algorithms: NIST Interagency Report 7709. L.: National Institute of Standards and Technology, 2010. 30. Hemaspaandra E. The complexity of kemeny elections. L.: Theoretical Computer Science, 2005. 31. Jacobs C.E. Fast multiresolution image querying. L.: Computer Graphics, 1995. 32. Jesorsky O. Robust face detection using the hausdorff distance. L.: Audio- and Video-Based Person Authentication, 2001. 33. Jesorsky O. Robust face detection using the hausdorff distance. L.: Proceedings of the Third International Conference on Audio- and Video-Based Biometric Person Authentication, 2001. 34. Klir George J. Uncertainty and Information. L.: Foundations of Generalized Information Theory, 2006. 35. Koschan A. A comparative study on color edge detection. L.: In Proceedings of the 2nd Asian Conference on Computer Vision, 1995. 36. Kuncheva L.I. Combining pattern classifiers: methods and algorithms / L.I. Kuncheva. — Wiley-Interscience, 2004. 37. Lee K. C. Acquiring linear subspaces for face recognition under variable lighting. L.: Transactions on Pattern Analysis and Machine Intelligence, 2005. 38. Lienhart R., Kuranov A., Pisarevsky V. Empirical analysis of detection cascades of boosted classifiers for rapid object detection. L.: Proceedings of the 25th DAGM-Symposium, 2003. 39. Lindeberg T. Edge detection and ridge detection with automatic scale selection. L.: International Journal of Computer Vision, 1998. 40. Liu C. Gabor-based kernel pea with fractional power polynomial models for face recognition. L.: Transactions on Pattern Analysis and Machine Intelligence, 2004. 41. Martinez A. M. The AR face Database. L.: CVC technical report: CVC Technical Report 24, 1998. 42. Rodriguez F., Cardinaux S., Bengio J. Measuring the performance of face localization systems. L.: Image and Vision Computing, 2006. 43. Moon H. Computational and performance aspects of pea-based face- recognition algorithms. L.: Perception, 2001. 44. Phillips P., Flynn T. Overview of the face recognition grand. L.: Computer Society Conference on Computer Vision and Pattern Recognition, 2005. 45. Phillips P. Face recognition grand challenge. L.: Biometric Consortium Conference, 2004. 46. Pratt W.K. Digital Image Processing. L.: Wiley, 1978. 47. Romdhani S. A mult-iview non-linear active shape model using kernel pea. L.: 10th British Machine Vision Conference, 1999. 48. Ruiz-del Solar J. Illumination compensation and normalization in eigenspace-based face recognition: A comparative study of different pre-processing approaches. L.: Pattern Recognition Letters, 2008 49. Samaria F. Parameterisation of a stochastic model for human face identification. L.: Workshop on Applications of Computer Vision, 1994. 50. Saradha A. A hybrid feature extraction approach for face recognition systems. L.: International Journal on Graphics, Vision and Image Processing, 2005. 51. Schapire R.E. The boosting approach to machine learning: An overview. L.: Workshop on Nonlinear Estimation and Classification, 2003. 52. Shih F. Y. Automatic extraction of head and face boundaries and facial features. L.: Information Computer Graphics Science, 2004. 53. Stark J.A. Adaptive image contrast enhancement using generalizations of histogram equalization. L.: Transactions on Image Processing, 2000. 54. Turk M. Eigenfaces for recognition. L.: Journal of Cognitive Neuroscience, 1991. 55. Viola P. Robust real-time face detection. L.: International Journal of Computer Vision, 2004. 56. Vizilter Yu.V. Projective morphoogies and their application in structural analysis of digital images. L.: Journal of Computer and Systems Sciences International, 2008. 57. Voorhees E.M. Overview of tree 2003. L.: Text Retrieval Conference. NIST, 2003. 58. Walley P. Statistical reasoning with imprecise probabilities. L.: London: Chapman and Hall, 1991. 59. Wang H. Face recognition under varying lighting conditions using self quotient image. L.: Int. Conf. Automatic Face and Gesture Recognition, 2004. 60. Wang J. Digital Libraries: Universal and Ubiquitous Access to Information. L.: Digital Libraries: Universal and Ubiquitous Access to Information, 2008. 61. Wang J. A new face detection method based on shape information. L.: Pattern Recogn, 2000. 62. Xu L. A new curve detection method: Randomized Hough transform(RHT). L.: Pattern Recognition Letters, 1990. 63. Вапник В.Н. Теория распознавания образов. М.: Наука, 1974. С. 86. 64. Визильтер Ю.В. Обобщенная проективная морфология // Компьютерная оптика. 2008. 65. Полевой Н.С. Криминалистическая кибернетика: Учебник / Под ред. Н.С. Полевой. 2-е изд. М.: МГУ, 1989. С. 26. 66. Пытъев, Ю.П. Морфологический анализ изображений // Доклад АН СССР. 1983. 67. Российский семинар по Оценке Методов Информационного Поиска: Пособие / Под ред. И. Некрестьянов, М. Некрестьянова. СПб.: НУ ЦСИ, 2008. С. 46. 68. Стенли Р. Перечислительная комбинаторика: Учебник / Под ред. Р. Стенли. М.: Мир, 1990. С. 440. 69. Файн B.C. Опознавание изображений (основы непрерывно-групповой теории и ее приложения): Учебник / Под ред. B.C. Файн. М.: Наука, 1970. С 103. 70. Харинов М.В. Запоминание и адаптивная обработка информации цифровых изображений: Пособие / Под ред. P.M. Юсупов. СПб.: университет СПб, 2006. С. 32. 71. Корганова О.Г., Кузьмин В.В. Методы распознавания образов // Сборник научных статей ИИУС. 2018. № 1/16. 72. Корганова О.Г, Кузьмин В.В. К вопросу распознавания образов с помощью модели знакового представления данных // Сборник научных статей ИИУС. 2018. № 1/16. 73. Корганова О.Г., Кузьмин В.В. Распознавание лиц с помощью модели знакового представления данных // Сборник научных статей ИИУС. 2018. № 1/16.
Отрывок из работы

1 ЗНАКОВОЕ ПРЕДСТАВЛЕНИЕ ИЗОБРАЖЕНИЙ И ЕГО СВОЙСТВА В настоящем разделе описывается понятие знакового представления изображения и проводится исследование его свойств. Изучается вопрос при каких условиях произвольное отношение на множестве пикселов становится знаковым представлением. Описывается построение процедуры восстановления изображений по знаковым представлениям. Рассмотрены меры информативности и неопределенности знаковых представлений. Изучается совокупность преобразований, которые не оказывают влияния на знаковые представления. Описывается и изучается такое понятие, как устойчивость знакового представления к влиянию на изображение шумов. 1.1 Знаковое представление изображения Функция неотрицательная f : ? >R+, здесь R+ = [0, +?), данная в точках сетки целочисленной ? = IN x IM , IN = {1,..., N}, IN = {1,..., M} и принимающая значения в интервале [0, +?), называется изображением. Пара чисел x = (x1,x2), x1 ? IN, x2 ? IM , будет называться пикселом. Как ? обозначим совокупность изображений f : ? >R+. Множества f : ? >Z+ , а также f : ? > [0,1], здесь Z+. Под яркостью изображений f в точке х при работе с цветными изображениями будет пониматься значение в этой точке цветовой компоненты L в процессе перехода от исходной модели в модель цвета HSL (яркость, насыщенность, тон). Определение 1.1 В случае выполнения условия: при (x, у) ? ?, тогда f(x) ? f(y); при (х, у) ? ?, (у, х) ? ?, тогда f(x) < f(y), тогда соотношение ? ? ?x? называется знаковым представлением изображения f ? F. Рассмотрим примеры полного и оконного знакового представления. Если знак указывает на свойство связности ? = {(x, у) ? ?2 | f(x) ? f(y)}, в котором содержатся все пары точек ?. Вытекает заметить, что значение полного знакового представления изображения f зависит однозначно от условия связности отношения. ? (?) = {(x, у) ? ?2 | f(x) ? f(y)}, y ? O?(x)} (1.1) O?(x) = {y ? ?| |x1 - y1| + |x2 – y2| < ?} (1.2) Пример оконного знакового представления приведен на рисунке 1.1. Обозначим через ?? класс изображения, которые соответствуют знаковому представлению ?. Допустим ? является некоторым знаковым представлением изображения f ? ?, а ?Tr является транзитивным замыканием отношения ?. Очевидно, что ?Tr является также знаковым представлением f, имеем ??Tr = ??. Анализ можно ограничисть отношением рефлексивным и передаточным (отношения квази-последовательные), которые представлены набором ?. Пример оконного знакового представления для разных параметров окрестности пикселя Рис. 1.1 Совокупность изображений ?? похожи на морфологические понятия Пытьева. Допустим Ф является семейством отображений ?: R+ > R+, имитирующим условия получения изображения. Совокупность изображения Vf ={?оf|??Ф} называется формой морфологии Пытьева. Можем видеть, если как Ф обозначить класс всех возрастающих изображений, тогда Vf С ??. В иных случаях совокупность ?? является более широким, по сравнению с совокупностьм Vf . [41] При условии ?=1 оконное знаковое представление соответствует псевдотроичному представлению изображения Харинова М.Б., заключающемся в беспараметричном представлении изображений в 3 градациях яркости, которые соответствуют сегментам смешанного типа, локальных минимумов и локальных максимумов. [42] 1.2 Исследование свойств знакового представления изображений 1.2.1 Восстановление множества изображений по знаковому представлению Выразим достаточные и необходимые условия, когда произвольное соотношение ? C ?2 представляет собой оконное знаковое представление f ? ?. Ориентированный граф (G?=(?,E?), где ? - совокупность его вершин, а E? - совокупность дуг совпадает ? совокупностьм. Если (х,у)??, то направление соответствующей дуги графа: от х вершины к у вершине. Вводим обозначение Е – совокупность (включая петли) всех дуг, соединяющих смежные пикселы, обозначим граф (G_? ) ?=(?, E\Е?) (здесь, по большому счету, граф (G_? ) ? не есть дополнительный к G?). Отношение эквивалентности ? = (? ? ?-1)Tr , где ?-1 является обратным отношением к ?, другими словами, ?-1={(x,у)??2 | (у,х)??}, и связанное с ? отношением разбитие множества вершин ? на фактормножества vi. Нужно отметить, что такое разбитие однозначно определяется. Класс эквивалентности будет соответствовать связанному множеству пикселов, которые характеризуются одинаковой яркостью, если ? будет являтья оконным знаковым представлением определенного изображения. Затем вводим на множестве V = {v1,..., vn} следующие графы всех классов для эквивалентности отношения ?: G_?^? = (V, E_?^?) и = G ?_?^? (V, E ?_?^?), где (vi, vj) ? E_?^?, если существует такая пара (х, у) ? E_?^?, что х ? vi и у ? vj; аналогично, (vi, vj) ? E ?_?^?, если существует такая пара (x, у) Е \ Е?, что х ? vi и у ? vj. Следовательно, граф G_?^? = (V, E_?^?), является продолжением графа G? = (?, E?) на множестве классов V. Отношение смежности пикселов также может быть перенесено на классы эквивалентности. Предположим, что классы vi и vj являются смежными классами эквивалентности, если существуют смежные пикселы х ? vi и у ? vj. Обозначим как E? совокупность (включая петли) всех дуг между смежными классами, можно увидеть, что G ?_?^? = (V, E? \? E?_?^?). Считаем, что функция f определена также на классах эквивалентности, другими словами, f(v)=f(х), если у?V и х?v. Ниже приводится утверждение, содержащее достаточные и необходимые условия, что произвольный граф G? = (?, E?) – это граф оконного знакового представлением определенного изображения f. Утверждение 1.1. Граф G? = (?, E?) является оконным знаковым представлением определенного изображения f лишь тогда, когда: а) E? С E, здесь Е — совокупность пар всех смежных вершин; б) G ?_?^? — ациклический граф; в) G ?_?^? — асимметричный граф на множестве ребер E?, т. е. (vi, vj) ? ? E?_?^? для vi ? vj в тогда и только тогда, когда (vi, vj) ? ? E?_?^?. Доказательство нужности. Примем G? = (?, E?) графом знакового представления какого-то изображения f. Следовательно по определению E? С E. Докажем, что граф G ?_?^? является ациклическим. Если допустить, что на графе этом имелся цикл, который состоит из вершин v1,... ,vk, то тогда выполнялись бы неравенства f(v1) > f(v2) > … > f(vk) > f(v1), что является невозможным. Нужность доказана. Доказательство достаточности. Допустим все условия утверждения выполняются. Покажем, что тогда должна существовать такая функция f : ? > R+ граф G? будет знаковым представлением для которой. Это доказывается при помощи итерационного построения последовательности транзитивных ациклических графов G(k)=(V, E(k)), k = 1,2,..., n, так, что: а) E(1) = (? E ??_?^?)Tr; б) E(1) ? E(2) ? … ? E(n) ? E(?). Данная процедура будет продолжаться до того момента, пока граф G(n)=(V, E(n)) на определенном шаге n не будет асимметричным, другими словами для всякой пары (vi,vj)?VхV разных вершин (vi?vj) условие: (vi, vj) ? E(n) будет соблюдаться только тогда, когда (vi, vj) ? E(n) . Опишем построение графа G( k+1)=(V, E (k+1)), на k шаге, если имеем транзитивный ациклический граф G(k)=(V, E(k)). Предположим, что граф G(k) является не асимметричным (если G(k) транзитивный асимметричный граф, в дальнейшем построении графов нет нужности). Тогда есть пара вершин таких (vi, vj)?VхV, что (vj, vi) ? E(k) и (vi, vj) ? E(k). К графу G(k) добавим дугу (vi, vj), и получим граф (V, E(k) ?-{(vi,vj)}. Это будет граф ациклический, поскольку в противном случае имелся бы цикл v1,...,vi, vj,...,vk, который содержит дугу (vi, vj), однако это является невозможным, поскольку из-за транзитивности графа G(k) это значило бы, что (vj, vi)?E(k , а это является противоречием выбора пары вершин (vj, vi). Затем построим транзитивное замыкание этого графа, выбираем G(k+1) = (V, (E(k) ?-{(vi,vj)})Tr), который соответствует всем требуемым условиям. Так как совокупность V х V является конечным, то на каком-то шаге мы непременно построим транзитивный, ациклический, асимметрический, граф G(n). Граф этот представляет собой граф определенного соотношения строгого порядка, следовательно есть функция f : V > R+, и (vi, vj) ? Е(n) тогда и только тогда, когда f(vi) > f(vj). Затем функцию f с класса эквивалентности распространяем на остальные пиксели ? при помощи f(x) = f(y), если х?v. Построенная функция f : ? > R+ очевидно соответствует всем требуемым условиям. Замечание 1.1. В доказательстве 1.1 утверждения фактически был показан способ построения возможных изображений, соответствующих этому знаковому представлению. Тем не менее, путем перебора всех возможных вариантов мы не перечислим, таким образом, все возможные изображения с точностью увеличивающегося монотонного преобразования, потому что все классы будут упорядочены отношениями строгого порядка. Однако могут быть случаи, когда изображение f будет отвечать существующему знаковому представлению, при этом найдутся индексы i и j такие, что для несмежных классов vi и vj будет справедливо соотношение f(vi) = f(vj). Для исчерпывающего описания множества ??, должна быть модифицирована процедура формирования транзитивных ациклических графов, которая была рассмотрена при доказательстве 1.1. Предположим G(1) = (G ?_?^?)Tr. Примем G(k) = (V(k), (E(k) ) – порожденный ациклический транзитивный граф на шаге k и граф G(k) не является графом отношения строгого порядка. В таком случае существует пара вершин (vi, vj)?V(k)хV(k), где (vi, vj) ? E(k) и (vj, vi) ? E(k). Затем строим граф G(k+1), либо как в утверждении 1.1, т.е. G(k+1) = (V, (E(k) ?-{(vi,vj)})Tr), либо с помощью слияния вершин vi и vj в одну вершину vi ? vj, т. е. получим граф G(k+1) = (V(k+1), (E(+))Tr), где V(k+1) = (V(k) ?-{ vi ? vj })\\(\{vi} ?{vj}), а E* = {(vl, vm) ? Е(k) | vl ? {vi, vj}, vm ? {vi, vj}} ? {(vi ? vj, vm) | (vi, vm) ? Е(k)} ? { (vi ? vj, vm) | (vj, vm) ? Е(k)} ? { (vm , vi ? vj) | (vm , vi) ? Е(k)} ? { (vm , vi ? vj) | (vm , vi) ? Е(k)}. Применяя такой же метод, что и в доказательстве 1.1, можно доказать получение на каждом шаге ациклического транзитивного графа G(k), а построение графов завершится непременно на каком-то графе G(n) отношений строгого порядка. Пользуясь данной процедурой, могут быть перечислены всевозможные изображения, которые соответствуют данному знаковому представлению. 1.2.2 Информативность и неопределенность знакового представления Энтропия Шеннона представляет собой один из "естественных" способов информативности изображения, который широко применяется при оценке информативности изображений в теории распознавания образов, теории кодирования и цифровой обработки изображения. [43, 44, 45, 46] Допустим f : ? > Z+ является изображением, а hf (i) = |{x??|f(x)=i}| - гистограммой f изображения. Функция hf (i) очевидно не равна нулю на определенном конечном множестве чисел. Тогда вероятность появления пиксела p(i)=Р{f(x)=i} с значением яркости i может быть оценена как: p ?(i)=hf (i) / |?|. Допустим А={i?Z+|hf (i)>0} — совокупность значений яркости, значение функции hf (i) для которых не равно нулю. Мера информативности изображений U(f) может быть определена с помощью энтропии Шеннона: U(f) = - c|?| ?_(i?A)-?p ?(i) ln??p ?(i)? ?, (1.3) здесь с — величина постоянная, которая определяется условием нормирования, а множителем |?| задается пропорциональная зависимость информативности от числа пикселов. Информативность изображения также может быть введена аксиоматически. [47, 48] Теперь проанализируем, каким образом происходит измерение информационного наполнения, знаковых представлений, их неопределенность, ведущая к потере данных яркости изображений. Характеристики эти описывать будем при помощи функционалов неопределенности U ?(?) и информативности U(?), которые заданы на ? отвечающих заданным свойствам. Очевидно, что функционалы U ?(?) и U(?) должны как-то быть связаны с U(f). Данная связь может быть определена на основании принципа из теории информации. [49] Свойство 1. Допустим ???, а Umax(?)=maxf???U(f) — информативность самого информативного изображения с знаковым представлением ?, следовательно: U ?(?) и U(?) = Umx(?), (1.4) Свойство 2. Допустим, изображения эквивалентные содержат в себе одинаковую информацию. Если ??? является связным соотношением, то класс ?? состоит из изображений, эквивалентных между собой, а в знаковом представлении т сохраняется все необходимая информация о изображении. Таким образом, при полном знаковом представлении считаем, что U ?(?) = 0 и U(?) = Umax. Свойство 3. Примем ?1, ?2 ? ? и ?1 C ?2. Предположим, что значение неопределенности знакового представления ?1 не менее неопределенности знакового представления ?2, т.е. U ?(?1) ? U ?(?2). Равенство достигается, к примеру, в случае ?1= ?2Tr. Свойство 4. Примем G? = (?, ?) является графом знакового представления ???, а также множества ?1,...,?m, которым определяются компоненты связности графа G?. Из соотношения (1.4) может легко быть получено выражение, описывающее меру неопределенности знакового представления: U ?(?)=Umax(?)-U(?). Допустим ???, отношение ?=???-1 тогда представляет собой отношение эквивалентности. Модельное изображение, граф знакового представления, соответствующего ему, и гистограмма яркости модельного изображения приведена на рис. 1.2. Модельное изображение и граф знакового представления, соответствующего ему, гистограмма яркости модельного изображения а - модельное изображение и оконного знакового представления, соответствующий ему; б - гистограмма яркости изображения модельного. Рис. 1.2 Допустим V={v1,...,vn} классы эквивалентности, храктеризуемые соотношением ? на ?. Считаем (vi, vj) ???, когда есть такая пара значений (xl, xk)?? , чтобы xk ? vj и xl ? vi. На рис. 1.3 приведен граф отношения ?? и граф отношения эквивалентности ? для изображения модельного. Утверждение 1.2. Допустим ???, ?=???-1 и ?? представляет собой продолжение отношения ?, возникающие на множестве классов V = {v1,...,vn}, рожденных ?, и р(i) =|vi|/|?|: Umax(?) = - c|?| ?_(i=1)^n-?p(i) ln??p(i)? ?, (1.5) Затем получим выражение, описывающее меру неопределенности U ?(?) знакового представления на основе предположений следующих. Основываясь на свойствах 1-4 можно из утверждения 1.2 получить следствия следующего характера. Граф отношения эквивалентности ? и граф отношения ?? для модельного изображения а - модельное изображение и граф соответствующего ему оконного знакового представления; б - гистограмма яркостей модельного изображения. Рис. 1.3 Следствие 1. Допустим ? = ?, другими словами, ? является отношением эквивалентности, V={v1,...,vn} является совокупностьм классов эквивалентности, рожденных ?, р(i) = |vi|/|?|. Следовательно U ?(?) = -c|?|?_(i=1)^n-?p(i) ln??p(i)? ?. Доказательство. Компонентами связности графа G? в этом случае будут множества v1,...,vn, и ?_(k=1)^n-?U(?_vk )=U(?)?. Так как ?_vk — это связные отношения, U(?_vk ) = 0, т. е. U(?) = 0 и U ?(?) = Umax(?), откуда уже вытекает требуемое доказательство. Следствие 2. Примем G? — это граф отношения ? ? ? и ?1,…,?m, — его компоненты связности, причем ?? — это связные отношения и р(i) = |?i | / |?|, i=1,…,m. Тогда U ?(?) = -c|?|?_(i=1)^m-?p(i) ln??p(i)? ?. Доказательство. Согласно определению Umax(?), существует f ? ?? такое, что Umax(?) = U(f). Поскольку любое отношение ??i связанное, то две любые функции класса ???i. считаются эквивалентными. Следовательно, Umax(??i) = Umax(fi), где fi является сужением функции f на множестве ?i. Имеем: ?_(i=1)^m-?U(?_?i )=U(?)=?_(i=1)^m-?U(f_i)?? и U ?(?) = Umax(?) - U(?) = U(f) – ?_(i=1)^m-?U(f_i)?. Обозначим как V = {v1,...,vn} разбитие множества ?, индуцированное соотношением эквивалентностей ?=???-1. Очевидно, что разбитие {v1,...,vn} будет более мелким по сравнению с разбиением {?1,…,?m}, т.е. каждое совокупность ?k можно представить как объединение множеств vi. Следовательно, может быть выбрано отображение ?: f(?) > {1,... ,m} так, что ?k = {х ? ?| ?(f(x)) = k}. Выполняться это будет при ?(f(vi)) = k. если vi С ?k. Тогда из-за аддитивности информативности U на ?, будем иметь U ?(?) = U(f) – ?_(i=1)^m-?U(f_i )=U(f°?)?. Изображение f°? определяется из равенства ?(f(x))=k, когда х ? ?k1 и расчеты его информативности могут быть проведены по соотношению: U(f°?) = -c|?|?_(i=1)^m-?p(i) ln??p(i)? ?, где р(i) = |?i | / |?|. Замечание 1.2. Сформулированный результат в следствии 1 можно представить в более простом виде. При выполнении условий следствия 2, отношения ???-1 представляет собой отношение эквивалентности, с которым связано разбитие U ?(? ? ?-1) = U ?(?) и {?1,…,?m} в соответствие со следствием 1. Утверждение 1.3. Допустим ??? и ?С???-1— является отношением эквивалентности. Следовательно U ?(?)? U ?(?). Доказательство утверждения. Допустим ?1 — ???, видим, что это является транзитивным, антисимметричным и рефлексивным отношением, другими словами, ?1??. Можем заметить дальше, что ?1??_1^(-1) =(???) ? (???)-1 =?. С учетом замечания 1.2, будем иметь U ?(?)=U ?(?). Видим, что ?1C? , основываясь на сделанных предположениях получим U ?(?) ? U ?(?1)., следовательно U ?(?)? U ?(?). Утверждение 1.3 дает возможность введения следующей оценки U ?. Допустим Eq (? ? ?^(-1)) – совокупность отношений эквивалентности в соотношении ???^(-1). Следовательно U ?_up(?) = min{U ?(?)|??Eq(???^(-1)) } , согласно утверждению 1.3, U ?(?) ? U ?_up(?) для всех ? ? ?. Вычисление значения U(f) и Umax(?) не представляет особенной сложности, тогда как вычисление значений U ?_up(?) представляет собой достаточно трудоемкую задачу. В процессе доказательства утверждения 1.1 была рассмотрена итерационный метод построения ациклических транзитивных графов на основании знакового представления. Данный алгоритм может быть модифицирован на основании принципа минимальной информативности, другими словами, из всех вариантов формирования вершин графа на каждом шаге будет выбираться вариант, приводящий к минимуму информативности. Допустим G? = (V, Е?) — граф, где Е? — совокупность дуг, которые соответствуют соотношению эквивалентности ???^(-1), индуцирующее, в свою очередь, разбитие множества ? на фактормножества V = {v1,..., vn}. Алгоритм 1.1 представленный на рисунке 1.4 позволяет строить разбитие {?1,..., ?m} множества ?. Алгоритм 1.1 построение разбития множества ? согласно принципу минимальной информативности Рис. 1.4 Примем р(i) = |?i | / |?| тогда U ?(?) может быть оценена следующим образом: U ?up(?) ? - c|?| ?_(i=1)^m-?p(i) ln??p(i)? ?, (1.6) Рассмотрим вычисление U(f), Umax(?f) и U ?_up(?f) на модельном изображении. Для того, чтобы вычислить U(f) нужно определить для каждого уровня яркости число пикселов на изображении. На рисунке 1.2б) приведена гистограмма модельного изображения, которое содержит шесть градаций яркости, имеющие частоты появления 2/20, 2/20, 6/20, 7/20, 2/20, 1/20. Подставив значение частоты в формулу (1.3), будем иметь, U(f) = 31,38 с. В основе определения Umax(?) лежит анализ классов эквивалентности соотношения ???^(-1). На рисунке 1.3а) приведен граф соотношения ???^(-1), который состоит из семи компонент связности, которые содержат соответственно 2, 6, 7, 1, 2, 1, 1 элементов. Подставив эти значения в формулу (1.5), будем иметь Umax(?) = 32,77 с. В данном случае U(f) < Umax(?), поскольку разным классам эквивалентности соотношения ???^(-1) соответствует идентичное значение яркости изображения. Граф продолжения отношения ? на классы эквивалентности vi, которые порождены отношением эквивалентности ? ? ?^(-1) представлен на рис. 1.3а. Изображение восстановленное по знаковому представлению согласно принципу минимальной информативности а - изображение модельное; б - изображение, которое было восстановлено по знаковому представлению модельного изображения согласно принципу минимальной информативности. Рис. 1.5 Используя алгоритм 1.1 на графе G(0) определим путь с максимальной стоимостью. Здесь это путь ?1 = {0,1,2,5,6}, | ?1| = 17. Путем удаления вершин ?1, построим граф G(0) , который состоит из не связных компонентов ?2 = {4}, |?2| = 2 и ?3 = {3}, |?3| = 1. В соответствии с (1.6) U ?up(?f) ? 10.36с.
Не смогли найти подходящую работу?
Вы можете заказать учебную работу от 100 рублей у наших авторов.
Оформите заказ и авторы начнут откликаться уже через 5 мин!
Похожие работы
Диссертация, Информационные технологии, 105 страниц
3150 руб.
Диссертация, Информационные технологии, 80 страниц
7000 руб.
Диссертация, Информационные технологии, 68 страниц
650 руб.
Диссертация, Информационные технологии, 103 страницы
3090 руб.
Служба поддержки сервиса
+7(499)346-70-08
Принимаем к оплате
Способы оплаты
© «Препод24»

Все права защищены

Разработка движка сайта

/slider/1.jpg /slider/2.jpg /slider/3.jpg /slider/4.jpg /slider/5.jpg