Содержание к диссертации
Введение
Глава 1. Анализ проблем и формулировка задачи распознавания изображений 11
1.1. Постановка задачи распознавания изображений 11
1.2. Анализ известных подходов и методов 15
1.3 Формулировка задач исследования 19
Выводы к главе 1 25
Глава 2. Распознавание изображений на основе показателей сопряженности 26
2.1. Общая схема классификации с помощью мер близости 26
2.2. Построение классификаторов на основе показателей сопряженности 30
2.3. Сравнительные оценки вычислительной сложности 36
2.4. Кластеризация изображений с помощью показателей сопряженности 46
Выводы к главе 2 53
Глава 3. Построение алгоритмов отбора информативных данных 54
3.1. Анализ методов снижения размерности пространства признаков 54
3.2. Алгоритм отбора информативных областей на изображении 60
3.3. Обоснование меры мультиколлинеарности 62
3.4. Границы для показателя диагонального преобладания 67
3.5. Исследование связи с качеством распознавания лиц 68
Выводы к главе 3 71
Глава 4. Экспериментальные исследования алгоритмов анализа и распознавания изображений 72
4.1. Результаты исследования в задаче распознавания случайных векторов 72
4.2. Результаты исследования в задаче распознавания цифр 77
4.3. Анализ информативности изображений в задаче распознавания разрывов струи полимера 87
4.3. Исследование качества распознавания в пространстве суммирующих инвариантов 95
Выводы к главе 4 103
Заключение 105
Список использованных источников 108
Приложение А 117
Графики результатов в экспериментах по распознаванию цифр 117
Приложение Б 123
Исходный текст программы для эксперимента по распознаванию цифр 123
- Анализ известных подходов и методов
- Построение классификаторов на основе показателей сопряженности
- Алгоритм отбора информативных областей на изображении
- Результаты исследования в задаче распознавания цифр
Введение к работе
Актуальность
Системы распознавания образов в настоящее время получили широкое распространение. Трудно назвать такую сферу деятельности, где такие системы не используются. Особенно широкое распространение получили системы распознавания и понимания изображений. Связано это с тем, что информация о многих объектах и явлениях в настоящее время регистрируется и хранится в виде цифровых изображений.
Распознавание образов как научное направление возникло и развивается с конца 50-х годов прошлого века. Большой вклад в развитие теории распознавания образов внесли отечественные ученые С.А. Айвазян, М.А. Айзерман, М.М. Бонгард, Э.М. Браверманн, В.Н. Вапник, К.В. Воронцов, В.М. Глушков, А.Л. Горелик, Ю.И. Журавлев, Н.Г. Загоруйко, А.Г. Ивахненко, В.А. Ковалевский, Г.С. Лбов, Л.И. Розоноэр, К.В. Рудаков, В.А. Скрипкин, А.А. Харкевич, ЯЗ. Цыпкин, А.Я. Червоненкис, М.И. Шлезингер, и др. За рубежом основоположником работ в области распознавания образов является Ф. Розенблатт, предложивший модель деятельности мозга - персеп-трон. Большой вклад в развитие теории распознавания внесли также зарубежные ученые: Ф. Гонсалес, Р. Дуда, Дж. Ту, К. Фукунага, К. Фу, П. Харт и др.
Системы распознавания образов предназначены для классификации входных изображений на некоторые группы. Первые системы разрабатывались для читающих автоматов, в которых решалась задача распознавания знаков, изображающих букву или цифру. В последние годы повышенное внимание со стороны исследователей получило распознавание лиц. Связано это, с одной стороны, с тем, что распознавание лиц, является одним из наиболее сложных приложений анализа и понимания изображений, с другой стороны, с бурным ростом спроса на автоматические системы видеоконтроля и видеонаблюдения.
Несмотря на широкую коммерциализацию рынка программных продуктов распознавания и доступность ряда работающих технологий, интенсивность исследований в области распознавания не снижается, т.к. требуемый уровень надежности таких систем пока еще недостаточен. Актуальность проблемы подтверждается продолжающимся ростом числа конференций по распознаванию, таких как ICAFGR (International Conference on Automatic Face and Gesture Recognition) или AVBPA
(Audio- and-Video-based Biometric Person Authentication), созданием систематических эмпирических тестов- для; проверки качества методов распознавания, например, FERET (Face Recognition Technology) или FRVT (Face Recognition Vendor Test) и др:
Способ классификации изображений, основанный на вычислении мер близости между ними, является одним их самых первых подходов к решению задачи распознавания образов. Экспериментальные исследования различных методов распознавания, использующих эту идею, подтверждают ее" эффективность. Часто такие эксперименты осуществляются в пространстве признаков, где в качестве значений признаков используются значения яркостей отсчетов» цифрового изображения.
В рамках этого направления наиболее широко используются' следующие меры близости: евклидово расстояние, манхэттенская' метрика, расстояние Махаланобиса. Сравнительные исследованиям показывают, что качество распознавания при применении различных мер близости может существенно различаться. Более того, эти различия существенным образом-зависят также от конкретных особенностей задачи (характер искажений, взаимного расположениявекторов образов в классе и др:). В связи с этим естественно возникает вопрос о применению других мер близости, которые в определенных условиях могут дать лучший» результат, по сравнению с широко используемыми.
В задачах линейной регрессии в качестве меры, почти линейной- зависимости векторов^ независимых переменных широко используются так называемые меры мультиколлинеарности: определитель, минимальное собственное число, показатели парной и максимальной сопряженности [2]. В задачах поиска и распознавания изображений эти меры пока не нашли заметного применения. В работе [41] показатель максимальной сопряженности и показатель сопряженности с нуль-пространством впервые предложено использовать для формирования признакового пространства.
Важной* отличительной чертой указанных показателей сопряженности является, то, что они характеризуют близость не с отдельным вектором, являющимся представителем класса (например, с вектором, являющимся' средним значением векторов класса), а с пространством, образованным всеми векторами анализируемого класса. Представляется, что это должно приводить к более полному учету всей имеющейся информации о классе в каждой конкретной ситуации. Указанное обстоятельство послужило мотивом для проведения всесторонних исследований эффективности мер
сопряженности в задачах распознавания. Ясно, что отсутствуют методы, являющиеся всегда наилучшими. Поэтому одной из задач исследований является выявление условий, при которых показатели сопряженности «работают» лучше.
Другой важной проблемой распознавания и анализа изображений является формирование признакового пространства. В задачах распознавания изображений в качестве признакового пространства часто используются непосредственно сами отсчеты значений яркости. При этом высокое разрешение изображений приводит к большим размерностям пространства признаков и значительным вычислительным затратам. Известным способом преодоления этой трудности является отбор наиболее информативных признаков, например, путем использования матрицы весов или перехода к системе признаков меньшей размерности, например, с помощью разложения Карунена-Лоэва (Principal Component Analysis - РСА), что также требует значительных вычислительных затрат. Поэтому актуальна задача построения и исследования эффективных и простых в вычислительном отношении алгоритмов отбора информативных признаков. В настоящей работе исследуется возможность использования для этой цели мер мультиколлинеарности.
Следует подчеркнуть, что более чем за 40-летнюю историю развития теории» распознавания образов разработан огромный арсенал эффективных методов и алгоритмов, реализуемых на различных этапах распознаваниями обеспечивающих повышение качества классификации. Поэтому, предпринимая исследование, связанное с изучением эффективности некоторой меры близости в задачах распознавания; следует отдавать отчет в том, что такое исследование должно быть проведено в сочетании с наиболее общепризнанными процедурами и технологиями, получившими распространение в области распознавания изображений.
Такими «типовыми» процедурами; направленными на существенное повышение качества распознавания являются разбиение классов на подклассы (кластеризация образов), а также применение в качестве признаков инвариантов. Поэтому наряду с исследованиями эффективности обычных схем принятия решений, представляет интерес исследование мер мультиколлинеарности и сопряженности в сочетании с указанными известными алгоритмами. В частности, актуально проведение исследований алгоритма,кластеризации образов, построенного на основе показателей сопряженности, а также исследование эффективности показателей сопряженности в пространст-
ве инвариантов. Более того, эти исследования целесообразно провести на 3-D моделях.
Таким образом, актуальной является задача разработки и исследования методов и алгоритмов распознавания изображений, использующих меры мультиколлинеарности, в частности, показатели сопряженности для отбора информативных признаков, распознавания и кластеризации в качестве меры расстояния, в том числе в пространстве инвариантов.
Исследования по теме диссертации выполнялись при поддержке российско-американской программы «Фундаментальные исследования и высшее образование», а также грантов РФФИ (гранты №01-01-00097, №03-01-00109, №05-01-08043-офи_а, №06-08-01024).
Цель и задачи исследований
Целью работы является достижение более высоких показателей качества в задачах распознавания и анализа изображений за счет применения для отбора информативных данных и принятия решений о принадлежности классу показателей сопряженности и мультиколлинеарности, и выявление условий, при которых они более эффективны. В соответствии с поставленной целью в рамках диссертационной работы решаются следующие задачи.
Построение решающих правил, основанных на использовании в качестве мер близости показателей сопряженности, и установление диапазона значений показателя мультиколлинеарности векторов образов, при которых достигается повышение качества распознавания изображений.
Сравнительное исследование вычислительной сложности показателей сопряженности и разработка методики их выбора с учетом числа обучающих объектов и размерности пространства признаков.
Исследование мер мультиколлинеарности в качестве критериев отбора информативных данных на изображениях и построение алгоритмов формирования векторов признаков по этим критериям.
Исследование возможности повышения качества распознавания за счет применения показателей сопряженности в алгоритмах кластеризации обучающих объектов.
5. Исследование возможности повышения качества распознавания с применением показателей сопряженности в пространстве суммирующих инвариантов, в т.ч. трехмерных изображений лиц.
Методы исследований
В диссертационной работе используются методы теории распознавания образов, цифровой обработки изображений, а также математического анализа, линейной алгебры и теории групп.
Научная новизна работы
В диссертации получены следующие новые научные результаты.
Разработаны новые решающие правила принятия решений в задачах распознавания на основе показателей сопряженности с пространством, натянутым на векторы анализируемого класса, и/или нуль-пространством соответствующей транспонированной матрицы, обеспечивающие повышение качества распознавания в значительном диапазоне значений показателя мультиколлинеарности векторов образов.
Предложена и обоснована методика выбора одного из показателей (сопряженности с пространством и/или с нуль-пространством) в зависимости от размерности пространства признаков и числа обучающих объектов.
Разработан новый алгоритм формирования признакового пространства, для случая использования в качестве признаков значений отсчетов яркости изображений, основанный на отборе информативных областей изображений по показателям мультиколлинеарности.
Показана возможность повышения качества распознавания за счет применения показателей сопряженности в алгоритмах кластеризации обучающих объектов.
Показана возможность повышения качества распознавания, в т.ч. трехмерных изображений лиц, при использовании решающих правил на основе показателей сопряженности в пространстве суммирующих инвариантов.
Апробация работы
Основные результаты работы докладывались на следующих конференциях:
Международной конференции «The 12th ISPE International Conference on Concurrent Engineering: Research and Applications», Даллас, США, 25-29 июля 2005;
Международной конференции «The IASTED International Conference on Automation, Control, And Applications», Новосибирск, Россия, 20-24 июня, 2005;
Всероссийской научной конференции «Математическое моделирование и краевые задачи», Самара, Россия, 29-31 мая, 2006;
Международной конференции «The 3th International Conference on Pattern Analysis (ICPA 2006)», Будапешт, Венгрия, 26-28 мая, 2006;
Международной конференции «The International Conference on Machine Learning and Data Mining MLDM'2007», Лейпциг, Германия, 18-20 июля, 2007;
Международной конференции «The IEEE International Conference on Advanced Video and Signal based Surveillance», Лондон, Великобритания, 5-7 Сентября 2007,
а также представлялись на следующих выставках:
Третья окружная выставка «Российским инновациям - российский капитал», первый приз в категории «информационные технологии», Самара, 14-15 апреля 2005;
Пятая межрегиональная выставка «Промышленный салон - 2006», Самара, 10-13 октября, 2006;
Российская национальная выставка в Китае, Пекин, Китай, 17-22 ноября, 2006.
Основные положения диссертации, выносимые на защиту:
Решающие правила принятия решений в задачах распознавания, основанные на использовании показателей сопряженности с пространством, натянутым на векторы анализируемого класса, и/или нуль-пространством соответствующей транспонированной матрицы, обеспечивающие повышение качества распознавания в значительном диапазоне значений показателя мультиколлинеарности векторов образов.
Методика выбора одного из показателей (сопряженности с пространством и/или с нуль-пространством) в зависимости от размерности пространства признаков и числа обучающих объектов.
Алгоритм формирования признакового пространства, для случая использования в качестве признаков значений отсчетов яркости изображений, основанный на отборе информативных областей изображений по показателям мультиколлинеарности.
Результаты экспериментов, показывающие возможность повышения качества распознавания в значительном диапазоне значений показателя мультиколлинеарности векторов образов, за счет применения показателей сопряженности, в т.ч. в задаче кластеризации, в пространстве суммирующих инвариантов и трехмерных изображений лиц.
Анализ известных подходов и методов
Не будет преувеличением сказать, что распознавание образов и, в частности, распознавание изображений, несмотря на использование серьезных теоретических результатов из различных разделов кибернетики, в значительной степени является наукой экспериментальной, в том смысле, что качество решающих правил, в конечном итоге, должно проверяться на тестовых и реальных задачах. В настоящей работе такими базовыми задачами являются распознавание цифр и распознавание лиц.
Оправданием такого выбора является то, что исследуемые в работе решающие правила применимы для распознавания любых изображений. Выбранные же задачи замечательны тем, что распознавание цифр - это одна из первых задач распознавания образов, которая возникла в 50-х годах прошлого века в связи с необходимостью построения читающих автоматов, а задача распознавания лиц актуальна в настоящее время, в связи с расширяющимся спросом на системьъвидеоконтроля и видеонаблюдения. В этой связи ниже приводится краткий анализ методов и проблем, связанных с решением указанных двух задач.
В первых работах в области распознавания образов само слово «образ», как правило, использовалось для обозначения напечатанного или написанного от руки знака, изображающего букву или цифру. Математическим аппаратом постановки и решения задач распознавания образов с момента их возникновения явилась теория статистических решений. Классические результаты теории статистических решений явились базой для построения решающих правил, обеспечивающих определение класса, к которому принадлежит предъявленный знак.
В настоящее время математический аппарат, привлекаемый для решения задач распознавания знаков, заметно расширился. В частности, используются методы алгебры логики, методы математического программирования и др. Тем не менее, методы, в которых решение о принадлежности некоторому классу принимается на основе вычисления некоторой меры близости в евклидовом пространстве, остаются основой многих современных, в т.ч. основанных на статистической теории принятия решений, алгоритмов распознавания цифр. В данном случае классификация основана на среднем расстоянии между описаниями предъявленного знака и каждого знака из множества известных.
Задача распознавания лиц в последние два десятилетия наиболее популярна [91, 92]. Об этом свидетельствует резкое возрастание числа публикаций, обзорных работ [94] и интернет-ресурсов (например, Face-rec.org [38] и др.). С использованием появившихся в последние годы баз лиц, значительно расширен набор тестов, включивших в себя такие новые эксперименты: обработка изображений лиц высокого разрешения (от 5 до 6 мега-пикселей); распознавание трехмерных изображений; предобработка изображений лиц, устраняющая влияние изменения позы и освещения.
Распознавание по внешнему облику. В английской терминологии называемый как Appearance based или иногда View-based подход является наиболее популярным. Суть подхода заключается в представлении лица как многомерного вектора признаков, компоненты которого составляются из отсчетов интенсивности пикселей изображения лица.
В рамках этого подхода наиболее широко используются методы классического линейного анализа, основанные на разложениях РСА, ICA, LDA. Вектор признаков раскладывается на коэффициенты определенного базиса, размерность которого, как правило, значительно меньше размерности исходного пространства признаков. После этого отыскивается сходство между разложениями- (векторами коэффициентов) по данному базису неизвестного лица и лиц базы данных.
Все подобные преобразования можно записать как линейное преобразование W из одного пространства признаков размерности N в другое - размерности N: x = JVx, где х - вектор признаков в новом пространстве размерности N. При этом N= N. Алгоритмы распознавания, использующие в качестве мер близости показатели сопряженности, основанные на РСА и LDA подходах исследуются в третьей главе настоящей работы. Нелинейный анализ является более сложным в реализации, по сравнению с линейными моделями. В свою очередь, линейный анализ может рассматриваться как аппроксимация нелинейного анализа. В нелинейном анализе используются нелинейные модели для исследования нелинейных множеств. Основой метода является анализ главных компонент ядра (Kernel РСА) [80], віслючающий в себя нелинейную трансформацию из исходного пространства признаков размерности N в пространство признаков размерности N. Эта группа методов представляет интерес для отдельного исследования, но находится за пределами настоящей работы.
В реальных приложениях распознавания лиц системы, реализующие идею распознавания по внешнему облику, сталкиваются с трудностями, заключающимися в наличии лишь ограниченного числа изображений обучающей выборки, и при этом их значительной вариабельности, особенно в мимике. В работе [66] показано, что если отсутствует необходимый объем данных для обучения системы, качество классификации может быть невысоким. Теме генерации дополнительных образцов для обучающей выборки посвящена работа [87].
Распознавание по моделям лица. Модельное распознавание лиц заключается в конструировании модели человеческого лица, которая бы позволяла учитывать различные вариации. Априорная информация о лице человека тщательно используется для построения таких моделей, например, учитывается относительное расположение различных элементов лица (глаз, носа, рта) [50], [89]. Интегрируя и форму, и текстуру лица, Куте [34, 37] разработал двумерную модель лица. Более сложная трехмерная модель лица включает в себя информацию о трехмерной структуре человеческого лица.
Другими словами, в этом случае на одном из этапов распознавания лиц также могут использоваться некоторые меры близости. Таким образом, задача построения и исследования эффективности новых решающих правил, основанных на применении в качестве мер близости показателей сопряженности является актуальной. Это может существенно расширить арсенал эффективных методов и алгоритмов распознавания, использующих самые разнообразные методы и подходы.
К задаче исследования показателей сопряженности в качестве мер близости в решающих правилах распознавания изображений приводят следующие рассуждения качественного характера. Одним из наиболее важных факторов, который часто приводит к снюкению качества распознавания, является почти линейная зависимость векторов признаков - столбцов матрицы X. С другой стороны, известно, что для характеристики почти линейной зависимости векторов независимых переменных в задачах линейной регрессии широко используются так называемые меры мультикол-линеарности.
Построение классификаторов на основе показателей сопряженности
Пусть х - вектор, являющийся образом объекта, предъявленного для установления его принадлежности к k -му классу, а ХЛ - JVxM-матрица, составленная из векторов образов объектов, принадлежащих &-му классу.
Геометрически указанная мера близости представляет собой косинус угла между вектором х и столбцовым пространством матрицы Хк, которое в свою очередь является подпространством линейного векторного пространства L.
Наряду с показателем сопряженности (2.5) введем в рассмотрение показатель сопряженности с нуль-пространством того же пространства:
Здесь Тк - матрица, составленная из собственных векторов, соответствующих нулевым собственным значениям матрицы Вк = XkXTk, а Хк - TVxM-матрица, составленная из векторов образов объектов, принадлежащих к -му классу. Если рассматривать матрицу Вк как матрицу вырожденного линейного оператора, то геометрическая интерпретация этой меры представляет собой косинус угла между вектором х и нуль пространством этого линейного оператора.
Таким образом, показатели (2.5) и (2.6), при заданных х и Хк, эквивалентны и выбор одного из них для построения классификатора должен определяться лишь удобством в организации вычислительного процесса и традиционным требованием уменьшения числа операций. В соответствии с описанным выше принципом классификации по минимуму расстояния, сформулируем правило использования показателей сопряженности (2.5), (2.6) как функций расстояния при построении решающей функции f(x).
Для оценки эффективности классификатора, построенного по указанным правилам, необходимо экспериментально сравнить качество его распознавания с качеством распознавания классификаторов, основанных на других мерах. Помимо уже обсуждавшегося евклидова расстояния, рассмотрим другие наиболее употребляемые меры, используемые для распознавания образов.
Эта мера была предложена Г. Минковским, как приложение к геометрии водителя такси одного из самых населенных районов Нью-Йорка и геометрически пред ставляет собой расстояние между двумя точками в гиперпространстве, вычисленное под прямыми углами вдоль координатных осей.
Эту меру целесообразно использовать в ситуации, когда векторы признаков различных классов обнаруживают тенденцию располагаться вдоль координатных осей.
Очевидно, что эта неметрическая мера близости достигает максимума равного единице, когда направления векторов ък и х совпадают. Значение этой меры, близкое к единице, говорит о высокой степени сходства между векторами. Поэтому в данном случае, строго говоря, следует использовать меру \-Dk. Легко убедиться в том, что при наличии только одного эталона для каждого класса, показатель сопряженности (2.5) будет эквивалентен косинусу угла.
Все вышеприведенные меры обладают тем недостатком, что вычисляют расстояние только между двумя векторами. Даже при наличии нескольких векторов в обучающей выборке для отдельного к -го класса, необходимо представлять их одним эталонным вектором гк. Предложенные в настоящей работе показатели сопряженности свободны от этого недостатка и вычисляют близость между неизвестным вектором х и подпространством, образованным всем множеством векторов, относящихся к к -му классу. Экспериментальное исследование классификаторов, построенных на основе описанных выше показателей сопряженности для сравнения с другими, приведенными выше мерами близости, проводилось с использованием стандартной базы данных ORL. ORL была сформирована за период между апрелем 1992 года по апрель 1994 года исследовательской лаборатории AT&T Кембриджского университета (АТТ). Данная база содержит изображения лиц сорока человек. Для каждого человека имеется 10 различных ракурсов с произвольной мимикой. Таким образом, база данных содержит 400 изображений. На рис. 2.1 приведены примеры изображений пяти лиц из базы данных ORL.
Проведено несколько экспериментов. В первом из них векторы х формировались путем построчной развертки изображений лиц, т.е. в качестве признаков использовались значения яркостей отсчетов. Размер изображений оригинальной базы данных ORL равен 112x96. Таким образом, каждое изображение представлялось в виде вектора х, размерностью 10752x1. Из различных наборов этих векторов составлялись матрицы Хк для каждого класса [8 , 54 ].
Вся база данных разбивалась на две части: обучающую и тестовую выборки по 200 изображений в каждой, по пять изображений каждого лица. С целью выявления зависимости качества распознавания от числа векторов в классе использовалось только фиксированное число изображений из обучающей выборки: от одного (только 40 изображений) до пяти (все 200 изображений). При этом тестовая выборка во всех экспериментах не изменялась.
Существование между показателями сопряженности указанной выше связи (2.8) ставит вопрос о целесообразности выбора одного из них с точки зрения вычислительных затрат. Очевидно, что объем вычислений будет определяться двумя факто рами: размерностью пространства векторов признаков N и числом векторов обучающей выборки для каждого класса. Здесь и далее будем считать число векторов обучающей выборки для каждого класса одинаковым и равным М. Заметим, что ранее буква М использовалась для обозначения числа векторов обучающей выборки в целом. Данное переобозначение сделано в целях удобства. Далее смысл обозначения М будет понятен из контекста.
Алгоритм отбора информативных областей на изображении
Задача снижения размерности пространства признаков, образованного векторами, составленными из отсчетов-изображений, может быть сформулирована следующим образом. Пусть все изображеншкобучающей выборки имеют одинаковые размеры N{x.N2, так что каждое изображение представляется NXN2 xl -вектором, компонентами которого являются значения яркостей пикселей изображения, «развернутые» по строкам или столбцам. Предположим, что число изображений в обучающей выборке равно М. Следовательно, в соответствии с обозначениями первой главы из векторов обучающей выборки можно построить NxM-матрицу X.
Задача редукции признакового пространства состоит в построении из Х матрицы меньшей размерности - пхМ (п N), содержащей М пх 1 -векторов х;, полученных путем исключения из векторов х, одноименных малоинформативных компонентов. Технически эта задача сводится к исключению из матрицы X некоторого (возможно значительного) числа строк, являющихся источником сильной мульти-коллинеарности, что по существу означает исключение из всех обучающих изображений неинформативных областей. Заметим, что соответствующая информационная матрица А в этом случае станет матрицей с размерами п х п .
При решении задачи распознавания изображений интуитивно ясно, что сходные для всех классов области изображений несут в себе меньшее количество информации. С другой стороны, понятно, что эти области как раз и являются источниками почти линейной зависимости векторов признаков, а их удаление должно уменьшать мультиколлинеарность векторов признаков. Исходя из приведенных рассуждений качественного свойства, ставится задача снижения размерности векторов признаков, компонентами которых являются значения яркости отсчетов изображений, путем отбора наиболее информативных областей на изображении с использованием мер мультиколлинеарности.
Ниже приводится описание предложенного нового алгоритма, который инвариантен к использованию конкретного показателя мультиколлинеарности [12 ]. Этот алгоритм позволяет выявлять наиболее информативные области на изображениях с целью снижения размерности (редукции) признакового пространства без существенной потери качества распознавания. Алгоритм реализуется в виде следующей последовательности шагов.
По информационной матрице вычисляется одна из мер мультиколлинеарности (1.4)-(1.7). Полученное значение присваивается всем отсчетам своего фрагмента на поле анализируемого изображения. Шаг 6. Задается или определяется пороговое значение показателя мультиколли-неарности. Все пиксели изображения с равным ему или более высоким, чем заданный порог, значением яркости, включаются в число компонентов всех векторов х, обучающих объектов.
Заметим, что схема формирования векторов образов из оставшихся отсчетов изображений (порядок обхода) не имеет значения. Важно, чтобы эта схема была одинаковой для всех М векторов. В результате реализации описанного выше алгоритма, в зависимости от выбранного порога, может быть достигнуто существенное снижение размерности признакового пространства. Важнейшим, с точки зрения вычислительной сложности и эффективности отбора данных, в описанном алгоритме является обоснование и выбор меры мультиколлинеарности.
В настоящем разделе приводятся результаты сравнительного исследования мер мультиколлинеарности, описанных в разделе 1.3 с целью выбора меры информативности признаков (отсчетов изображений). Кратко опишем эти меры и их свойства.
1. Определитель информационной матрицы (1.4) может выступать в качестве меры мультиколлинеарности, если матрица Грама определенным образом нормирована. Например, можно вместо исходной матрицы А рассматривать матрицу Ж0, полученную из нее по правилу А= A/trA. При такой нормировке сумма собственных значений равна единице. Поэтому, если det(Jty близок к нулю, то минимальное собственное значение также близко к нулю и, следовательно, задача плохо обусловлена. При отсутствии нормировки определитель может быть достаточно большим даже при близком к нулю минимальном собственном значении за счет большой величины максимального собственного значения.
2. Спектральное число обусловленности (1.5) также может выступать в качестве меры мультиколлинеарности. Однако в данном случае не требуется специальная нормировка матрицы А, т.к. число обусловленности не чувствительно к параметру масштаба. Эта мера широко используется в теории возмущений для анализа ошибок в решениях [1, 19]. В работе [18] показана связь между числом обусловленности и определителем матрицы. В частности, приводится следующая оценка сверху числа обусловленности K(A) (trMA)/dQtA. (3.3)
3. Универсальной мерой мультиколлинеарности является минимальное собственное значение (1.6). Она отражает как масштаб, зависящий от физической размерности независимых переменных, так и мультиколлинеарность (сопряженность) соответствующих им векторов.
4. Показатель максимальной сопряженности (1.7) наряду с минимальным собственным значением и числом обусловленности, является наиболее сильной мерой мультиколлинеарности. Если ЯФ\, гарантируется невырожденность задачи. Недостатком этой меры является вычислительная сложность, связанная с необходимостью вычисления обратной матрицы. Но даже если мы готовы пойти на эти затраты возникает «замкнутый круг»: для того чтобы сделать заключение о степени линейной зависимости векторов образов, необходимо знать обратную матрицу, но если векторы действительно почти линейно-зависимы, вычисление обратной матрицы становится серьезной проблемой.
Приведенные формулы показывают тесную связь показателя диагонального преобладания с другими мерами мультиколлинеарности. Поэтому есть основания предполагать, что оценки информативности по показателю диагонального преобладания могут быть достаточно сильными, в частности, сравнимыми с показателями мультиколлинеарности, вычисляемыми по собственным значениям. Вместе с тем, показатель диагонального преобладания во многих отношениях является более предпочтительным [14], в частности, он обладает вычислительной простотой, т.к. не требует вычисления собственных значений.
Таким образом, хотя определитель, число обусловленности и минимальное собственное значение являются достаточно полными характеристиками мультиколлинеарности, их использование нецелесообразно, так как связано со значительными вычислительными трудностями. Наиболее подходящим для оценки информативности данных в вычислительном отношении является показатель диагонального преобладания. В силу ограничений он не всегда дает гарантированные оценки. Однако в данном случае это не существенно, поскольку задача заключается в отборе наиболее информативных данных, для которых область его существования достигается. Следует также заметить, что точность вычисления показателя диагонального преобладания (в отличие от других мер) не зависит от степени мультиколлинеарности векторов образов.
Результаты исследования в задаче распознавания цифр
Следующий эксперимент призван показать, что условия, которые были сформированы с использованием множества случайных векторов, на самом деле, являются достаточно типичными в задачах распознавания. Для этого была использована одна из первых, изучавшихся в теории распознавания, задач — распознавание изображений цифр, подверженных типичной модели искажений и помех. Цель эксперимента - показать, что качество распознавания цифр может быть заметно улучшено за счет применения показателей сопряженности.
При этом ставилась также задача обеспечить высокую надежность результатов. Для этого проводилось большое число экспериментов, а по их результатам в работе строились доверительные интервалы оценки качества распознавания с использованием, как показателей сопряженности, так и других мер близости.
Ниже приводится описание проведенного эксперимента. Для большей ясности описание представлено в виде последовательности отличающихся содержанием этапов. На самом деле, в интересах сокращения времени формирования модельных примеров и проведения расчетов, в компьютерной программе некоторые этапы были совмещены.
Этап 2 — формирование матриц классов и распознаваемых образов. Путем построчной развертки полученные изображения цифр были преобразованы в векторы размерности 320x1. Для каждой цифры (класса) были сформированы матрицы X, ( = 0,9) размерности 320хМ Для этого произвольным образом выбиралось одно из исходных изображений, которое подвергалось случайным искажениям. Использовались следующие типичные искажения. Поворот. Изображение поворачивалось относительно центра на произвольный угол до 25 градусов по (или против) часовой стрелки. При этом пиксели, выходящие за пределы окна 20x16 удалялись, а появляющиеся свободные области заполнялись цветом фона (белый). Сдвиг. Изображение сдвигалось вдоль осей на случайно выбранную величину до трех пикселей. При этом пиксели, выходящие за пределы окна 20x16 удалялись, а появляющиеся свободные области заполнялись цветом фона. Размытие. Размытие осуществлялось с помощью гауссова фильтра со скользящим окном, размером 3x3. Шум. На изображение накладывался гауссов шум с нулевым средним и заданным значением дисперсии (отношение сигнал/шум - 1).
По аналогии с экспериментом по распознаванию произвольных векторов для матриц Хк, соответствующих генерируемым классам, рассчитывался показатель диагонального преобладания. Как и следовало ожидать, с ростом числа эталонов в классе, показатель диагонального преобладания снижался.
Далее для каждого класса (цифры) были сгенерированы по 1000 векторов, для которых должна решаться задача о принадлежности к классу - тестовая выборка. Эти векторы формировались из приведенных выше исходных изображений. Для этого произвольным образом (с использованием равномерно распределенных случайных чисел) выбиралось одно из пяти исходных изображений (рис. 4.5) и подвергалось тем же искажениям, которые использовались при формировании векторов эталонов. Примеры сформированных искаженных изображений тестовой выборки приведены на рис. 4.7. Таким образом, была сформирована тестовая выборки из 10000 изображений.
Для каждого сформированного указанным образом набора данных проверялась степень мультиколлинеарности. Для этого формировалось расширенное пространство путем добавления сгенерированного случайного вектора, подлежащего распозна ванию, к матрице Хк. Далее с использованием полученной (М+1)-матрицы Хк строилась информационная матрица Ак =Х[ХЛ размерности (М+1)х(М+1), для которой в соответствии с (1.8) вычислялось значение приведенного показателя диагонального преобладания ф.
Наборы данных (матрица класса и случайный вектор распознаваемого образа) группировались по значениям показателя диагонального преобладания информационной матрицы. Цель этой группировки состояла в том, чтобы выявить, как качество распознавания зависит от степени мультиколлинеарности распознаваемого вектора тестовой выборки и векторов образов класса. При этом представляло также интерес установить, какая часть случайным образом сформированных тестовых векторов приводит к таким значениям мультиколлинеарности, при которых имеет место преимущество показателей сопряженности. Заметим, что о высокой степени мультиколлинеарности векторов свидетельствует близость значения приведенного показателя диагонального преобладания ф к нулю.
Сгенерированная тестовая выборка подавалась на вход классификатора. В эксперименте были использованы два типа классификаторов. Классификатор по евклидовой метрике. В этом случае использовалось правило «it ближайших соседей» (в данном случае к=М), то есть определялось расстояние до каждого отдельного эталона. Классификатор по показателю сопряженности с подпространством. При этом значение показателя сопряженности вычислялось по соотношениям (2.5), (2.6) с использованием сформированных матриц Хк. Эксперимент ставился таким образом, чтобы установить, с одной стороны, для какой доли тестовой выборки качество распознавания по показателям сопряженности выше, с другой стороны, как качество распознавания зависит от степени мультиколлинеарности. Для этого из тестовой выборки (10000 векторов) формировались выборки нарастающего объема птест от 100 (1% тестовой выборки) до 10000 (100% тестовой выборки), притом таким образом, что при переходе к каждой следующей выборке в нее включались векторы, доставляющие минимальное значение показателя диагонального преобладания среди оставшихся векторов. В результате такой схемы формирования с ростом объема выборки одновременно увеличивается значение показателя диагонального преобладания расширенной информационной матрицы.
Сопоставляя полученные интервалы и графики можно утверждать, что для примерно 62% случаев, для которых показатель диагонального преобладания имеет меньшие значения, качество классификации с использованием решающих правил на основе показателей сопряженности оказывается выше. На основе этого результата может быть сформулировано следующее конструктивное правило выбора меры близости в каждом конкретном случае. Для каждого распознаваемого вектора определяется ближайший класс по показателям сопряженности. Далее этот вектор присоединяется матрице Хк ближайшего класса и вычисляется значение показателя диагонального преобладания соответствующей информационной матрицы. Если величина этого показателя оказывается меньше некоторого установленного порога, то результат распознавания фиксируется. В противном случае, применяется решающее правило, основанное на евклидовом расстоянии.
