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

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

□03458833

Козин Никита Евгеньевич

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

Специальность: 05.13.17 - Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата технических наук

Самара 2008

003458833

Работа выполнена в Самарском государственном аэрокосмическом университете имени академика С.П.Королева и Институте систем обработки изображений РАН

Научный руководитель:

доктор технических наук, профессор В.А. Фурсов

Официальные оппоненты: доктор технических наук, профессор

A.Г Ташлинский

доктор физико-математических наук, доцент

B.6. Мясников

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

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

Защита диссертации состоится «13» февраля 2009 г. в 10 ч. на заседании диссертационного совета Д 212.215.07 в Самарском государственном аэрокосмическом университете имени академика С.П.Королева, по адресу: 443086, г. Самара, Московское шоссе, д. 34.

С диссертацией можно ознакомиться в библиотеке Самарского государственного аэрокосмического университета имени академика С.П.Королева.

Автореферат разослан «31» декабря 2008 г.

Ученый секретарь диссертационного совета, д.т.н., профессор У?""" / И.В. Белоконов

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

Актуальность.

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

Распознавание образов как научное направление возникло и развивается с конца 50-х годов прошлого века. Большой вклад в развитие теории распознавания образов внесли отечественные ученые С.А. Айвазян, М.А. Айзерман, М.М. Бонгард, Э.М. Бра-верманн, В.Н. Вапник, К.В. Воронцов, В.М. Глушков, A.JL Горелик, Ю.И. Журавлев, Н.Г. Загоруйко, А.Г. Ивахненко, В.А. Ковалевский, Г.С. Лбов, Л.И. Розоноэр, К.В. Рудаков, В.А. Скрипкин, А.А. Харкевич, Я.З. Цыпкин, АЛ. Червоненкис, М.И. Шлезингер, и др. За рубежом основоположником работ в области распознавания образов является Ф. Розенблатт, предложивший модель деятельности мозга - персептрон. Большой вклад в развитие теории распознавания внесли также зарубежные ученые: Ф. Гонсалес, Р. Дуда, Дж. Ту, К. Фукунага, К. Фу, П. Харт и др.

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

Несмотря на широкую коммерциализацию рынка программных продуктов распознавания и доступность ряда работающих технологий, интенсивность исследований в области распознавания не снижается, т.к. требуемый уровень надежности таких систем пока еще недостаточен. Актуальность проблемы подтверждается продолжающимся ростом числа конференций по распознаванию, таких как 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) и др.

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

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

3

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

Известно, что взаимная ориентация (степень сопряженности) векторов образов в классе оказывает существенное влияние на качество распознавания. В задачах линейной регрессии в качестве меры почти линейной зависимости векторов независимых переменных широко используются так называемые меры мультиколлинеарности: определитель, минимальное собственное число, показатели парной и максимальной сопряженности. В задачах поиска и распознавания изображений эти меры пока не нашли заметного применения. В работе Training in Pattern Recognition from a Small Number (ISPR - 2000, Barcelona, Spain. Vol. 2, p. 119-121) для анализа свойств признакового пространства впервые предложено использовать так называемые показатели максимальной сопряженности и сопряженности с нуль-пространством.

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

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

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

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

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

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

Исследования по теме диссертации выполнялись при поддержке российско-американской программы «Фундаментальные исследования и высшее образование», а также грантов РФФИ (гранты №01-01-00097, №03-01-00109, №05-01-08043-офи_а, № 06-08-01024).

Цель и задачи исследований.

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

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

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

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

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

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

Методы исследований.

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

Научная новизна работы.

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

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

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

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

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

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.

Основные положения диссертации, выносимые на защиту:

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

2. Методика выбора одного из показателей (сопряженности с пространством и/или с нуль-пространством) в зависимости от размерности пространства признаков и числа обучающих объектов.

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

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

Публикации.

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

Структура и объем работы.

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе приведена формулировка задачи распознавания изображений. Предполагается, что имеется М изображений каждого из К объектов. Каждое изображение представляется вектором х = [х1,х2,...,хЛ1]' размерности ЛГ, где х],хг,...,хк -

признаки. Векторы, соответствующие изображениям одного объекта, составляют класс. Совокупность векторов признаков всех классов образует обучающую выборку. Решение задачи распознавания состоит в конструировании решающей функции /:□" к» {0,1,2,...,К}, которая каждому вектору х ставит в соответствие некоторый класс. Для уменьшения числа неправильных классификаций вводится также класс с номером 0, соответствующий отказу в распознавании.

Из множества {х„х2,...,хм} векторов каждого класса составляется NхМ -матрица

Х = [Х1>12'">Хм] ■ (!)

Этой матрице ставятся в соответствие так называемая информационная М х М -матрица:

А=ХГХ (2)

и ковариационная N х N -матрица

В = ХХГ. (3)

Предполагается, что гапкА = м. Известно также, что собственные значения Л, (Л), (= 1,и матрицы А совпадают с ненулевыми собственными значениями матрицы В, а собственные векторы матрицы В, соответствующие ненулевым собственным значениям, образуют ортогональный базис (разложение Карунена-Лоэва).

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

(4)

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

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

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

д4=-'I * '-1 . 5

х'х

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

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

(6)

XX

Здесь Т4 - матрица, составленная из собственных векторов, соответствующих нулевым собственным значениям матрицы В„ = ,а X,- N х М -матрица, та же, что и в (5). Между показателями Д, и 5, существует связь:

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

= (8) или<3„=ТД,г, (9)

соответствующая решающая функция /(х) строится следующим образом. Вектор х принадлежит т -му классу, то сеть / (х) = т, т = 1,2,...К ,

если =тах^ , где (Ю)

(хгх)

х' 0 х

либо 5В = шш^ , где ^ - (11)

При использовании порогового значения Т„, решающая функция дополняется правилом

/(х) = 0, если или 5П^Г0. (12)

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

В разделе 2.3 приведены полученные в работе аналитические оценки числа необходимых арифметических операций л(*) для вычисления матриц и :

п (е>м) = 2Шг + +2А/Ч ИМ{2М -\) + Ыг(2М-\), (13)

¿(<г+3/-1) , , ч.'

+ (14)

На рис. 1, слева в качестве примера приведены построенные по полученным соотношениям графики зависимости числа арифметических операций для показателей Як (возрастающий) и ^ (убывающий) в зависимости от М при N =500. На рис. 1,

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

На рис. 2 в координатах М, N приведена построенная по совокупности точек, соответствующих точкам пересечения кривых на графиках (рис. 1), для которых имеет равенство правых частей (13), (14), кривая равных вычислительных затрат. В области ниже кривой более выгодно использовать решающее правило (15), построенное с использованием показателя сопряженности с нуль-пространством.

число операции

N

Рис. I. Зависимость объема вычислений от М при = 200 : аналитическая (щенка (слева); численный эксперимент (справа)

В разделе 2.2 диссертации приведен сравнительный пример распознавания лиц, взятых из известной базы данных СЖЬ, с использованием решающих правил (10)-(12). Сравнение проводилось с методами распознавания, основанными на следующих мерах близости: евклидово расстояние; Манхэттенская метрика; косинус угла между векторами (частный случай меры (5) для класса, состоящего из одного вектора) и расстояние Махаланобиса. Результаты представлены на рис. 3. Заметим, что преимущество построенных решающих правил начинает проявляться лишь при числе векторов в классе более грех. Этого следовало ожидать. Ясно, что в случае одного или двух векторов в классе результат не может существенно отличаться от случая одного эталона.

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

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

матриц X, = [х,] и Х2 = [х2]) (1); произвольный выбор вектора х,. из числа оставшихся и вычисление показателя сопряженности со столбцовыми пространствами матриц X, и Х2 (2); добавление этого вектора х, в качестве нового столбца к матрице, соответствующей ближайшему классу (3). Работа

Рис. 2.Кривая равных объемов вычислений

90% Процент распознавания

60%

Показатель сопряхсенности

[Г] Расстояние Махаланобиса

м

1 2 3 4 5 Рис. 3. Вероятность распознавания для различных мер в зависимости от числа векторов в обучающей выборке каждого класса

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

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

Третья глава посвящена задаче отбора наиболее информативных областей на изображениях при формировании векторов признаков из значений яркости отсчетов изображений. Предполагается, что все изображения обучающей выборки имеют одинаковые размеры Л7, х Ыг, так что каждое изображение представляется Л^ х 1 -

вектором, компонентами которого являются значения яркости пикселей изображения «развернутые» по строкам или столбцам. Предположим также, что число изображений в каждом классе обучающей выборки равно М, а из векторов обучающей выборки строится Л'хА/ -матрица X. При этом задача отбора информативных признаков состоит в построении из X матрицы меньшей размерности пхМ (п< N ) путем исключения из нее строк, являющихся источником сильной мультиколлинеарности. В работе предложен следующий итерационный алгоритм отбора информативных отсчетов изображений.

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

Шаг 1. Проверяется условие К> М. Если условие выполняется, значение к увеличивается на единицу и осуществляется переход к следующему шагу, если нет - к шагу 5.

Шаг 2. Изображения разбиваются на к2 прямоугольных фрагментов, путем деления каждой стороны на к частей, и вычисляется размерность соответствующего изображению вектора: К = пк*тк где пк=пы/к, тк = ткЛ\к. Результат округляется до ближайшего целого.

Шаг 3. Для каждого фрагмента, например, д-го изображения обучающей выборки, сформированных на шаге 2, составляется КхМ -матрица , с использованием которой формируется соответствующая информационная пхп -матрица А*,„ =х1.,х/,,, •

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

90% Процент распознавания

80% 75% 70% 65% 60%

ттп

Евклидово 0 расстояние

□

Показатель сопряжснност

-л/

1 2 4 Рис. 4. Качество распознавания в зависимости от числа кластеров в классе

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

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

1. Нормировка информационной матрицы А = {оа} такая, что

¡гК = Ы (для этого матрица А слева и справа умножается на диагональную матрицу 0 = й,}. где ¿„ = \Ца„).

2. Вместо спектрального числа обусловленности вводится в рассмотрение обратное спектральное число

обусловленности'. К"1 (Л) = Л^/. Близость этого числа к 0 свидетельствует о плохой обусловленности матрицы А.

3. Вместо показателя диагонального преобладания (4) рассматривается приведенный (к интервалу [0,1]) показатель диагонального преобладания ф = {ф-\)!(М-\).

Заметим, что близость всех мер к единице соответствует уменьшению степени мультиколлинеарности векторов образов.

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

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

Рис. 5. Зависимость показателей <1й(А) (а), А'"1 (А) (б), Л^Да) (в), ф (г) от размерности векторов х

а) б) в) г)

Рис. 6. Поля информативности, полученные с использованием det(A) (а), К-'(Х) (б), ;,„JA) (в), ф (г)

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

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

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

В разделе 4.1 диссертации приведены

процент распознанных лиц 90% т-~

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

Л ........1—-—I-1------1------г----1----1

76% 68% «0% 52% 44% 36% 28% 20%

100% 92% 84%

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

результаты по распознаванию цифр. В эксперименте использовались десять (0,..,9) выполненных пятью различными шрифтами цифр 20x16 пикселей. Для каждой цифры формировалось множество случайных реализаций путем сдвига (до трех пикселей), поворота (до 25 градусов), размытия и наложения гауссова шума. Тестовые (распознаваемые) векторы (по 1000 для каждой цифры, т.е. всего 10000) формировались с использованием той же модели искажений.

На рис. 8 приведена одна из получен-

процент распознанных цифр ■—- Евкяидот расстояние л- Сопряженноапь

100% 95% 90% 85% 80% 75% 70%

0,6 0,55 0.5 0,45 0,4 0,35 0,3 0,25 0,2 Рис. 8. Зависимость качества распознавания цифр от диагонального преобладания

ных характерных зависимостей числа распознаваемых объектов тестовой выборки от величины диагонального преобладания расширенной (построенной с использованием матрицы X и распознаваемого вектора) матрицы А = ХГХ . Приведенная зависимость, кроме прочего, позволяет обоснованно назначить диапазон значений показателя диагонального преобладания матрицы А, при котором применение показателей сопряженности предпочтительнее.

В разделе 4.2. описана запатентованная информационная технология распознавания разрывов струи полимера в лабораторном анализе. На этапе предварительной обработки кадров изображений в этой технологии для выделения струи используется разработанный в главе 3 диссертации алгоритм определения информативных областей на изображении. На рис. 9 показан фрагмент сформированной области.

В разделе 4.3 приведены результаты экспериментов, показывающие эффективность применения показателей сопряженности в пространстве суммирующих инвариантов. Эксперимент проводился на базе трехмерных изображений лиц Face Recognition Grand Challenge (FRGC), включающей 275 человек с общим числом 4007 изображений, в т.ч. 943 обучающих.

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

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

Эксперименты проводились для 2-D евклидовых преобразований в биометрической среде распознавания BEE v.2.0 и оформлены в виде ROC-диаграмм (receiver

operating characteristic), показанных на рис. 10. Сравнение полученных ROC-кривых показывает возможность достижения более высокого качества распознавания при использовании показателей сопряженности в качестве мер близости в пространстве суммирующих инвариантов.

Рис. 9. Выделенный фрагмент изображения струи

True positive rate

Сопряженность

Евклидово расстояние

False positive rate

o,ofl5 ода

QJ

Рис. 10. Сравнение качества распознавания для одного инварианта

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

8. Экспериментально показана возможность повышения качества распознавания лиц с применением решающих правил на основе показателей сопряженности в пространстве суммирующих инвариантов.

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

в ведущих рецензируемых научных изданиях определенных ВАК:

1. Козин, Н.Е. Поэтапное обучение радиальных нейронных сетей [Текст] / Н.Е. Козин, В.А. Фурсов // Компьютерная оптика - 2004. - № 26. - С. 136-139.

2. Козин, Н.Е. Построение классификаторов для распознавания лиц на основе показателей сопряженности [Текст] / Н.Е. Козин, В.А. Фурсов // Компьютерная оптика. - 2006. - № 28. - С. 160-163.

3. Kozin, N. Building of classifiers based on conjugation indices [Text] / Kozin N., Kulagina I., Fursov V. // Optical Memoiy & Neural Networks. - 2007. - Vol. 16, No. 3. -pp. 136-141.

4. Козин, Н.Е. Снижение размерности векторов признаков по критериям мультиколлинеарности [Текст] / Н.Е. Козин, В.А. Фурсов // Компьютерная оптика. - 2008. - Том 3, № 32. - С. 307-311.

5. Козин, Н.Е. Распознавание лиц по показателям сопряженности в пространстве суммирующих инвариантов [Текст] / Н.Е. Козин, В.А. Фурсов // Компьютерная оптика. - 2008. - Том 4, № 32.

в других изданиях:

6. Козин, Н.Е. Автоматизированный анализ параллелизма программ [Текст] / Козин Н.Е., Фурсов В.А. // Сборник трудов 4-го Международного научно-практического семинара и Всероссийской молодежной школы «Высокопроизводительные параллельные вычисления на кластерных системах». - Самара, 2004.

7. Kozin, N. Stage-wise learning of radial neural networks [Text] / Kozin N., Fursov V. // The 12th ISPE International Conference on Concurrent Engineering: Research and Applications. Conference Proceeding. - Ft. Worth/Dallas, USA, 2005. - pp. 391-396.

8. Kozin, N. Algorithm for parallel learning of radial neural networks [Text] / Kozin N., Fursov V. // The IASTED International Conference on Automation, Control, And Applications (ACIT-ACA 2005). Conference Proceedings. Novosibirsk, 2005. - pp. 481-485.

9. Устройство для распознавания печатных и рукопечатных символов [Текст]: пат. 2285952 Рос. Федерация / Фурсов В.А., Казанский H.JL, Козин Н.Е., Сойфер В.А.; заявитель и патентообладатель Институт систем обработки изображений Российской академии наук; опубл. 20.10.2006, Бюл. № 29.

10. Способ распознавания разрывов струи раствора на изображении [Текст]: пат. 2336563 Рос. Федерация / Фурсов В.А., Казанский H.JL, Козин Н.Е., Попов С.Б.; заявитель и патентообладатель Институт систем обработки изображений Российской академии наук; опубл. 20.10.2008, Бюл. № 29.

11. Kozin, N. Constructing of Classifier for Face Recognition on the Basis of the Conjugation Indexes [Text] / Kozin N., Fursov V. // The Third International Conference on Pattern Analysis (ICPA 2006). Conference Proceedings. Budapest, Hungary, 2006.

12. Козин, Н.Е. Анализ вычислительной сложности алгоритмов по показателям сопряженности [Текст] / Козин Н.Е. // Сборник трудов Третьей Всероссийской научной конференции «Математическое моделирование и краевые задачи». - Самара, 2006.

13. Козин, Н.Е. Исследование алгоритмов распознавания на основе метода собственных лиц [Текст] // Козин Н.Е. // Сборник трудов Научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении» (ГШТ-2006). - Самара, 2006.

14. Программа автоматического распознавания индексов «ПАРИ» [Текст]: свид. об официальной регистрации программы для ЭВМ № 2005611237 Рос. Федерация / Казанский H.JL, Козин Н.Е., Попов С.Б., Фурсов В.А..

15. Kozin, N. Building of Classifiers Based on Conjugation Indices [Text] / Kozin N., Fursov V. II Proceedings of International Conference on Machine Learning and Data Mining (MLDM 2007). Conference proceedings. Leipzig, Germany, 2007.

16. Kozin, N. Recognition Through Constructing the Eigenface Classifiers using Conjugation Indices [Text] / Kozin N., Fursov V. // IEEE International Conference on Advanced Video and Signal based Surveillance. Conference proceedings. London, United Kingdom, 2007.

Подписано в печать 30 декабря 2008 г.

Тираж 100 экземпляров.

Отпечатано с готового оригинал-макета.

СГАУ 443086, Самара, Московское шоссе, 34

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

Актуальность.

Цель и задачи исследований.

Методы исследований.

Научная новизна работы.

Апробация работы.

Основные положения диссертации, выносимые на защиту:.

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМ И ФОРМУЛИРОВКА ЗАДАЧИ РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ.

1.1. Постановка задачи распознавания изображений.

1.2. Анализ известных подходов и методов.

1.3 Формулировка задач исследования.

Выводы к главе 1.

ГЛАВА 2. РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ПОКАЗАТЕЛЕЙ СОПРЯЖЕННОСТИ.

2.1. Общая схема классификации с помощью мер близости.

2.2. Построение классификаторов на основе показателей сопряженности.

2.3. Сравнительные оценки вычислительной сложности.

2.4. Кластеризация изображений с помощью показателей сопряженности.

Выводы к главе 2.

ГЛАВА 3. ПОСТРОЕНИЕ АЛГОРИТМОВ ОТБОРА ИНФОРМАТИВНЫХ ДАННЫХ.

3.1. Анализ методов снижения размерности пространства признаков.

3.2. Алгоритм отбора информативных областей на изображении.

3.3. Обоснование меры мультиколлинеарности.

3.4. Границы для показателя диагонального преобладания.

3.5. Исследование связи с качеством распознавания лиц.

Выводы к главе 3.

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ АЛГОРИТМОВ АНАЛИЗА И РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ.

4.1. Результаты исследования в задаче распознавания случайных векторов.

4.2. Результаты исследования в задаче распознавания цифр.

4.3. Анализ информативности изображений в задаче распознавания разрывов струи полимера.

4.3. Исследование качества распознавания в пространстве суммирующих инвариантов.

Выводы к главе 4.

Актуальность

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

Распознавание образов как научное направление возникло и развивается с конца 50-х годов прошлого века. Большой вклад в развитие теории распознавания образов внесли отечественные ученые С.А. Айвазян, М.А. Айзерман, М.М. Бонгард, Э.М. Браверманн, В.Н. Вапник, К.В. Воронцов, В.М. Глушков, A.JI. Горелик, Ю.И. Журавлев, Н.Г. Загоруйко, А.Г. Ивахненко, В.А. Ковалевский, Г.С. Лбов, Л.И. Розоноэр, К.В. Рудаков, В.А. Скрипкин, A.A. Харкевич, Я. 3. Цыпкин, А .Я. Червоненкис, М.И. Шлезингер, и др. За рубежом основоположником работ в области распознавания образов является Ф. Розенблатт, предложивший модель деятельности мозга - персеп-трон. Большой вклад в развитие теории распознавания внесли также зарубежные ученые: Ф. Гонсалес, Р. Дуда, Дж. Ту, К. Фукунага, К. Фу, П. Харт и др.

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

Несмотря на широкую коммерциализацию рынка программных продуктов распознавания и доступность ряда работающих технологий, интенсивность исследований в области распознавания не снижается, т.к. требуемый уровень надежности таких систем пока еще недостаточен. Актуальность проблемы подтверждается продолжающимся ростом числа конференций по распознаванию, таких как 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-0 моделях.

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

Исследования по теме диссертации выполнялись при поддержке российско-американской программы «Фундаментальные исследования и высшее образование», а также грантов РФФИ (гранты №01-01-00097, №03-01-00109, №05-01-08043-офиа, №06-08-01024).

Цель и задачи исследований

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

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

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

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

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

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

Методы исследований

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

Научная новизна работы

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

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

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

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

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

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.

Основные положения диссертации, выносимые на защиту:

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

2. Методика выбора одного из показателей (сопряженности с пространством и/или с нуль-пространством) в зависимости от размерности пространства признаков и числа обучающих объектов.

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

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

Выводы к главе 4

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

7. Установлена связь между этими показателями и проведена сравнительная оценка вычислительной сложности показателей.

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

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

10. Для алгоритма кластеризации образов на основе показателей сопряженности предложена схема его параллельной реализации с использованием интерфейса обмена сообщениями MPI.

S Проведен краткий обзор некоторых подходов к снижению размерности признакового пространства и проведены эксперименты по исследованию эффективности метода главных компонент.

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

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

11. Экспериментально показана эффективность применения предложенных процедур отбора признаков, в частности, установлены допустимые объемы отбрасываемых данных, не приводящие к существенному снижению качества распознавания, при распознавании изображений лиц базы данных БЕКЕТ.

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

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

14. Экспериментально показана возможность повышения качества распознавания лиц с применением решающих правил на основе показателей сопряженности в пространстве суммирующих инвариантов.

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

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

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

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

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

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

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

1. Воеводин, В.В. Вычислительные основы линейной алгебры : учеб. пособие для вузов Текст. / В.В. Воеводин; М.: Наука, 1977. - 303 с.

2. Демиденко, Е.З. Линейная и нелинейная регрессии Текст. / Е.З. Демиденко; -М.: Финансы и статистика, 1981.

3. Демидович, Б.П. Основы вычислительной математики Текст. / Б.П. Демидович, И.А. Марон; М.: Наука, 1966. - 664 с.

4. Программа автоматического распознавания индексов «ПАРИ» Текст.: свид. об официальной регистрации программы для ЭВМ № 2005611237 Рос. Федерация / Казанский Н.Л., Козин Н.Е., Попов С.Б., Фурсов В.А.

5. Козин, Н.Е. Поэтапное обучение радиальных нейронных сетей Текст. / Н.Е. Козин, В.А. Фурсов // Компьютерная оптика. 2004. - № 26. - С. 136-139.

6. Козин, Н.Е. Построение классификаторов для распознавания лиц на основе показателей сопряженности Текст. / Н.Е. Козин, В.А. Фурсов // Компьютерная оптика. -2006. -№ 28. С. 160-163.

7. Козин, Н.Е. Анализ вычислительной сложности алгоритмов по показателям сопряженности Текст. / Козин Н.Е. // Сборник трудов Третьей Всероссийской научной конференции «Математическое моделирование и краевые задачи». Самара, 2006.

8. Козин, Н.Е. Снижение размерности векторов признаков по критериям мульти-коллинеарности Текст. / Н.Е. Козин, В.А. Фурсов // Компьютерная оптика. -2008. Том 3, № 32. - С. 307-311.

9. Козин, Н.Е. Распознавание лиц по показателям сопряженности в пространстве суммирующих инвариантов Текст. / Н.Е. Козин, В.А. Фурсов // Компьютерная оптика. 2008. - Том 4, № 32.

10. Маркус, М. Обзор по теории матриц и матричных неравенств Текст. / М. Маркус, X. Минк; пер. с англ. М.: Наука, 1972. - 232 с.

11. Нильсон, Н. Обучающиеся машины Текст. / Н. Нильсон; М.: Мир, 1967.

12. Самарский, A.A. Численные методы Текст. / A.A. Самарский, A.B. Гулин; М.: Наука, 1989. 432 с.

13. Методы компьютерной обработки изображений Текст. / под ред. В.А. Сойфера; М.: Физматлит, 2001. - 784 с.

14. Солодовников, В.В. Принцип сложности в теории управления Текст. / В.В. Солодовников, В.Ф. Бирюков, В.И. Тумаркин М.: Наука, 1977. - 342 с.

15. Уилкинсон, Дж. Алгебраическая проблема собственных значений Текст. / Дж. Уилкинсон; пер. с англ. М.: Наука, 1970. - 564 с.

16. Фурсов, В.А. Идентификация моделей систем формирования изображений по малому числу наблюдений Текст. / В.А. Фурсов; Самара: СГАУ, 1998. - 128 с.

17. Фурсов, В.А. Введение в идентификацию по малому числу наблюдений Текст. / В .А. Фурсов; МАИ, 1991. - 36 с.

18. Фурсов, В.А. Проблемы вычисления оценок по малому числу наблюдений Текст. / В.А. Фурсов // Сборник трудов молодежной школы "Математическое моделирование 2001". Самара, 2001.

19. Adini, Y. Face Recognition: the Problem of Compensating for Illumination Changes Text. / Y. Adini, Y. Moses, S. Ullman // Proceedings of IEEE Transactions on Pattern Analysis and Machine Intelligence. Conference proceedings. 1997. pp. 721-732.

20. Anderson, T.W. Asymptotic theory for principal component analysis Text. / T.W. Anderson//Ann. Statist. Section, 3, 1963. pp. 77-95.

21. Atkinson, R. An Introduction to Numerical Analysis Text. / R. Atkinson, A. Kendall // 2nd edition, John Wiley & Sons, New York, 1989.

22. Ball, G.H. Isodata, an iterative method of multivariate analysis and pattern classification Text. / G.H. Ball, D.J. Hall, // Proceedings of IFIPS Congress, Conference proceedings. 1965.

23. Bellman, R.E. Dynamic Programming Text. / R.E. Bellman // Princeton University Press, 1957.

24. Boston, N. Fusion of summation invariants in 3D human face recognition Text. / N. Boston, W.Y. Lin, K.C. Wong, Y. Hu // Proceedings of CVPR. Conference proceedings, vol. II, pp. 1369-1376, 2006.

25. Boston, N. 3D human face recognition using summation invariants Text. / N. Boston, W.Y. Lin, K.C. Wong, Y. Hu // Proceedings of ICASSP. Conference proceedings, vol. II,-pp. 341-344, 2006.

26. Brunzel, H. Feature reduction for classification of multidimensional data Text. / H. Brunzel, J. Eriksson // Pattern Recognition, 33, 2000, pp. 1741-1748.

27. Calibri, E. Differential and numerically invariant signature curves applied to object recognition Text. / E. Calabi, P.J. Olver, C. Shakiban, A. Tannenbaum, S. Haker // Intl. Journal of Computer Vision, vol. 26, no. 2, 1998. pp. 107-135.

28. Cartan, E. La methode du repere mobile, la theorie des groupes Continus, et les espaces generalises Text. / E. Cartan // Exposes de geometrie, no. 5, 1935.

29. Cartoux, J.Y. Face authentification or recognition by profile extraction from range images Text. / J.Y. Cartoux, J.T. Lapreste, M. Richetin // Proceedings of Workshop on Interpretation of 3D Scenes, Conference proceedings, 1989. pp. 194-199.

30. Cootes, T.F. Active appearance models Text. / T.F. Cootes, G.J. Edwards, C.J. Taylor // Proceedings of European Conference on Computer Vision, Conference proceedings. 1998. vol. 2,-pp. 484-498.35.