Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 46

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

1Харьковский институт банковского дела Университета банковского дела НБУ, г. Харьков, Украина, е-mail:gorohovatsky-v@rambler.ru 2Харьковский национальный автомобильно-дорожный университет, г. Харьков, Украина, е-mail:assiada@list.ru

оптимальные методы сопоставления структурных описаний видеообъектов

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

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

Введение

В настоящее время для решения интеллектуаль­ных задач компьютерного зрения, связанных с рас­познаванием объектов в условиях действия фона и помех, эффективны структурные технологии, основанные на анализе особенностей изображе­ния в отдельных точках. Оценка свойств описания видео-объекта в виде конечного числа характер­ных признаков (ХП) позволяет за приемлемое вре­мя качественно разделить информацию об объекте и о фоновых образованиях [1-3]. Основой для фор­мирования ХП служит информация, содержащая­ся в некотором смысле «значимых» фрагментах. Распознавание на основе структурных описаний в виде множества ХП имеет следующие преимуще­ства: достаточно простое в вычислительном плане формирование признаков, сжатое признаковое пространство с возможностью управления его раз­мерностью в зависимости от задачи, устойчивость к влиянию фоновых искажений и ложных объек­тов.

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

Особый интерес при сопоставлении конечных множеств признаков в задачах искусственного ин­теллекта представляет применение оптимальных подходов, в основе которых лежит оптимизация значения некоторого критерия (в данном случае величины подобия описаний) путем комбинатор­ного перебора на конечном множестве вариантов [4]. Одним из эффективных способов структурного анализа данных, связанных с вычислением опти­мального сходства конечных множеств (описаний распознаваемых объектов), является венгерский метод (ВМ), названный комбинаторной оптими­зацией ограниченных множеств. Его можно рас­сматривать как решение задачи о назначениях для наиболее общего случая поиска максимального паросочетания в двудольном взвешенном графе [5­7]. Суть венгерского метода состоит в последова­тельном формировании оптимального решения за конечное число шагов. Решение задачи о назначе­ниях решает проблему установления степени сход­ства структурных описаний объектов в условиях несоответствия порядка их следования или нару­шения целостности описания из-за помех. Одним из достоинств применения ВМ при сопоставлении описаний является возможность оценки близости промежуточной величины сходства к оптимально­му варианту решения на каждой из итераций. Это позволяет контролировать процесс и при необхо­димости (в целях сокращения временных затрат) прекращать его при достижении заданной точ­ности. Такое свойство особенно важно для задач большой размерности, т.к. число векторов ХП в описаниях достигает двух-трех сотен.

Принцип оптимального сопоставления струк­турных описаний по сравнению с известными решениями (SIFT, SURF [1]), основанными на голосовании ХП, позволяет реализовать схему по­строения однозначных соответствий ХП из срав­ниваемых описаний, что в целом улучшает досто­верность распознавания.

Цель исследования анализ эффективности применения оптимальных подходов на примере венгерского метода для сопоставления описаний в виде множеств ХП.

БИОНИКА ИНТЕЛЛЕКТА. 2011. 3 (77). С. 85-88

ХНУРЭ

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

1. Формализация метода оптимального сопоставления описаний

Представим описание U визуального объекта в виде конечного множества U = [щ элементов щ , где m количество ХП в описании, щ ХП, ко­торый может представлять как дескриптор (значе­ние признака), так и геометрическую информацию (координаты ХП, значения аффинных инвариан­тов на основе этих координат и т.д.) [3].

Критерием при сопоставлении элементов яв­ляется значение некоторой метрики р), оце­нивающей различия щ,Uj, взятых из разных опи­саний щ є U1, Uj є U2. Методы с использованием голосования определяют число (сумму) голосов элементов, исходя из величин р) путем опти­мизации на конечном множестве или через оцен­ку с помощью некоторого порога. Оптимальные методы на основе р(щ щ) формируют некоторое оптимальное решение, например, минимизирую­щее сумму расстояний между описаниями с учетом однозначности соответствий элементов сравниваемых множеств.

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

m n

R(x) = X X Р, щ )Ху min , (1)

i =1 j=1

где щ єUl, єU2, m и n количества точек в описаниях U1U2; Xj є [0,1} — бинарный признак, отражающий соответствие i -го и j -го элементов из U1U2. Решение задачи (1) при ограничении на однозначность соответствия признаков из сопо­ставляемых множеств

m _

X Xij = 1 V/ = 1,n,

X x/j=1 Vj=1,m,

. i =1

минимизирует расстояние между U1,U2. Для при­кладных задач, где необходима максимизация целевой функции в (1), переход к задаче (1) осу­ществляют путем вычитания значений р ,Uj.) из максимального значения метрики.

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

"р11     р12     ...    р1п " р=   р21     р22     ... р2п

_рm1    рm2    ...    р/ип _

между всевозможными парами ХП щ є U1, щ є U2.

Реализация принципа однозначного голосова­ния элементов щ связана с анализом отдельных строк матрицы Р на предмет формирования го­лоса, равного 0 или 1. По полученному набору со­ответствий (голосов) можно вычислить значение критерия подобия двух описаний в виде суммы 5\ =X/^(i), где L(i) — предикат, равный 1, если голос отдается (соответствие установлено).

Реализация ВМ предполагает целенаправлен­ный выбор такой последовательности из гу} , сум­ма значений которой S2 = XРj будет минимальна на множестве возможных соответствий элементов описаний, и при этом из каждой строки и столб­ца матрицы Р будет выбран только один элемент, что в результате обеспечивает выбор оптимального по критерию S2 однозначного соответствия мно­жеств элементов описаний (паросочетание).

Реализация ВМ осуществляется путем целена­правленного эквивалентного преобразования ма­трицы Р с последовательным анализом строк и столбцов для получения матрицы с неотрицательны­ми элементами и системой m независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу. При достиже­нии ситуации с m независимыми нулями проблема выбора считается решенной, оптимальный вариант назначений определяется позициями независимых нулей в преобразованной матрице [5]. Пример фор­мирования паросочетания показан на рис. 1.

Рис. 1. Паросочетания для множеств ХП

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

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

При применении ВМ для сопоставления описа­ний U1,U2 их размерности m и n в общем случае могут отличаться. В этом случае в традиционном ВМ размер матрицы Р увеличивают до макси­мального среди m и n, а возникшие элементы за­полняют нулями [5-7]. Если исходная матрица не является квадратной, то дополнительно вводят не­обходимое количество строк (или столбцов), а их элементам присваивают значения, определяемые условиями задачи. Для задачи определения по­добия описаний полученным за счет расширения элементам необходимо присвоить некоторое мак­симальное значение среди возможных значений р,4j). Заметим, что для нашей задачи нецеле­сообразно усекать матрицу весов до квадратной традиционным способом в виде min(m,n), т.к. при этом может быть потеряна ценная информация об видео-объекте. С другой стороны, дальнейшее усложнение обработки за счет применения ВМ требует минимизации размеров матрицы на этапе предварительной обработки. Это достигается по­средством применения специальных методов сжа­тия структурных описаний [2]. Другим способом снижения затрат есть отбор в некотором смысле «значимых» строк и столбцов, например, содержа­щих большие по значению расстояния.

2. Геометрические признаки аффинных инвариантов

Особый интерес представляет применение оптимальных методов для геометрических призна­ков, построенных на основе координат ХП и отра­жающих пространственное расположение ХП объ­екта. Любое подмножество трех неколлинеарных точек объекта определяет аффинный базис, кото­рый задает на объекте систему координат. После выбора системы координат ХП можно представить с помощью аффинных инвариантов (АИ). После воздействия аффинного преобразования на объект значения АИ не изменяются [1]. Существуют раз­личные способы пространственной группировки АИ для сопоставления описаний. В работе [3] для отдельного ХП формируется подмножество АИ путем рассмотрения всевозможных базисов (раз­ные системы аффинных координат). Другим спо­собом является формирование подмножества АИ для всех ХП в одной и той же системе координат, т.е. для отдельного базиса. Такой способ представ­ления имеет вид значительного числа подмножеств (количество базисов) с небольшим количеством элементов. Данное представление удобно для при­менения ВМ из-за небольших по размеру матриц Р . Кроме того, оно дает возможность управлять количеством подмножеств (базисов) и принимать решение по неполному описанию.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа