Оценка сходства структурных объектов как множеств компонент
Рассматриваются вопросы сопоставления изображений визуальных объектов в системах компьютерного зрения. Предложены меры сходства, учитывающие искажение и появление ложных компонент в структурном описании. Проведен анализ свойств методов. Описаны результаты компьютерного моделирования для реальных изо...
Saved in:
| Published in: | Системні дослідження та інформаційні технології |
|---|---|
| Date: | 2011 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50085 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Оценка сходства структурных объектов как множеств компонент / В.А. Гороховатский // Систем. дослідж. та інформ. технології. — 2011. — № 1. — С. 57-70. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860263236365975552 |
|---|---|
| author | Гороховатский, В.А. |
| author_facet | Гороховатский, В.А. |
| citation_txt | Оценка сходства структурных объектов как множеств компонент / В.А. Гороховатский // Систем. дослідж. та інформ. технології. — 2011. — № 1. — С. 57-70. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Рассматриваются вопросы сопоставления изображений визуальных объектов в системах компьютерного зрения. Предложены меры сходства, учитывающие искажение и появление ложных компонент в структурном описании. Проведен анализ свойств методов. Описаны результаты компьютерного моделирования для реальных изображений.
Розглянуто питання зіставлення зображень візуальних об’єктів у системах комп’ютерного зору. Запропоновано міри схожості, які враховують викривлення та появу хибних компонент у структурному описі. Проведено аналіз властивостей методів, описано результати комп’ютерного моделювання для реальних зображень.
Problems of image comparison of visual objects in systems of computer vision are considered. The measures of similarity which takes into account distortion and occurrence of the false component in the structural description are suggested. The analysis of properties of methods is implemented, results of computer modeling for real images are described.
|
| first_indexed | 2025-12-07T18:57:46Z |
| format | Article |
| fulltext |
© В.А. Гороховатский, 2011
Системні дослідження та інформаційні технології, 2011, № 1 57
УДК 004.932.2
ОЦЕНКА СХОДСТВА СТРУКТУРНЫХ ОБЪЕКТОВ КАК
МНОЖЕСТВ КОМПОНЕНТ
В.А. ГОРОХОВАТСКИЙ
Рассматриваются вопросы сопоставления изображений визуальных объектов в
системах компьютерного зрения. Предложены меры сходства, учитывающие
искажение и появление ложных компонент в структурном описании. Проведен
анализ свойств методов. Описаны результаты компьютерного моделирования
для реальных изображений.
ВВЕДЕНИЕ
Распознавание образов решает проблемы построения и применения фор-
мальных операций над отображениями объектов в некотором пространстве
признаков, что отражается в отношениях эквивалентности между объекта-
ми. Эти отношения выражают принадлежность к классам, рассматриваемым
как самостоятельные семантические единицы. Наиболее часто в целях клас-
сификации используются следующие методы интеллектуального анализа
данных: ранжирование, сравнение, непосредственное оценивание [1–6].
Путем перехода от изображения к множеству ключевых точек (КТ) или
множеству информативных фрагментов удается достичь существенного
снижения объема информации, в то время как характеристики распознава-
ния (достоверность, помехозащищенность) при этом практически не сни-
жаются. При представлении изображений в пространствах КТ визуальные
данные можно рассматривать как мультимножества [7], т.к. значения при-
знаков КТ бывают достаточно близкими между собой. КТ представляет со-
бой числовой вектор фиксированной размерности с вещественными значе-
ниями, связанный с точкой пространства координат. Одним из наиболее
эффективных современных способов построения описания в виде множест-
ва КТ есть применение детектора SIFT (Scale-invariant feature transform —
масштабно-инвариантное преобразование признаков), который формирует
КТ как вектор размерностью 128 [8]. Множество КТ является базой для
формирования компонентного представления, например, путем построения
отношений между КТ. Будем рассматривать распознаваемый визуальный
объект как многоэлементную совокупность (объединение) компонент, а
значение вектора признаков для компоненты назовем дескриптором. Ком-
понентное представление позволяет осуществлять структурный анализ ви-
зуальной информации в виде составных объектов. Выбор типов дескрипто-
ров и компонент в значительной мере влияет на свойства классов в плане их
разделения между собой. Основной задачей компонентного сопоставления
объектов есть надежное функционирование систем в неполном пространст-
ве признаков, а также исключение ложных компонент. Для этих целей необ-
ходима разработка специальных мер сходства [4, 7, 8].
В.А. Гороховатский
ISSN 1681–6048 System Research & Information Technologies, 2011, № 1 58
Цель работы — формализация и анализ свойств мер сходства и рас-
стояний на множествах КТ применительно к задаче сопоставления изобра-
жений в условиях неполного представления и ложных воздействий.
Задачи исследования — построение мер сходства для конечных мно-
жеств дескрипторов, изучение особенностей применения мер для визуальных
объектов, описание сходства в терминах соответствий и отношений на мно-
жестве признаков, анализ и оценка эффективности предлагаемых подходов.
КЛЮЧЕВЫЕ ТОЧКИ И КОМПОНЕНТЫ
Компонента — это либо одиночная КТ, либо некоторое множество КТ,
сформированное путем построения отношений. Отношения дают возмож-
ность анализировать комбинации признаков, которые в информационном
плане часто являются более значимыми для распознавания, чем сами при-
знаки [1]. В этом аспекте не накладывается никаких требований на способ
построения компонент, в частности, допускается их пространственное пере-
сечение. В то же время сами КТ характеризуют свойства изображения в
конкретных точках. Рис. 1 иллюстрирует схему компонентного представле-
ния объектов.
Задача отнесения объекта к некоторому классу решается путем оценки
сходства множеств. Сходство отличается
тем, что вычисляемые величины сравнива-
ются не со шкалой, а относительно друг
друга, это дает возможность наряду с упо-
рядочиванием различать между собой
объекты, которые могут включать схожие
элементы. Современные технологии для
построения сходства-различия в качестве
первого этапа предполагают сравнение пар
дескрипторов объект-эталон и получение
локальных характеристик. Затем локальные
значения интегрируются с целью получения
глобальной (общей) меры соответствия
[7–10].
Для решения задачи оценки сходства-различия применимы не все клас-
сические меры и метрики. Например, метрики Хаусдорфа и ближнего (даль-
него) соседа фактически формируются по величине одного из расстояний
между элементами и по этой причине не могут считаться устойчивыми к
локальным искажениям. С другой стороны, интегрально учитывающая схо-
жесть всех без исключения элементов величина «средней связи», которая
вычисляется как среднее арифметическое всевозможных попарных расстоя-
ний между элементами, обладает хорошей помехозащищенностью относи-
тельно аддитивных помех, однако, к локальным искажениям она также не-
устойчива. Наиболее близкими к требуемым свойствам являются меры,
связанные с операциями пересечения и симметрической разности множеств.
Они вычисляются путем подсчета соответствий элементов (голосование).
Подсчет эквивалентных компонент реализует аппроксимацию полного
Рис. 1. Объект в виде компонент
из пар КТ
Оценка сходства структурных объектов как множеств компонент
Системні дослідження та інформаційні технології, 2011, № 1 59
соответствия объектов. Голосование компонент высоких уровней в виде со-
вокупности КТ позволяет учесть внутреннее сходство структур объектов. В
соответствии со значениями мер формируются оценки классов для реализа-
ции задач распознавания (рис. 2).
ПРИМЕНЕНИЕ АССОЦИАТИВНЫХ МЕР И МЕТРИК
В задачах анализа двумерных сигналов и оценки биометрической информа-
ции различают три типа мер сходства-различия [3–5, 11, 12]: ассоциативные,
выражающие отношения числа совпадающих признаков к общему их числу
(коэффициенты связи, парные функции); корреляционные («косинусные»
меры); показатели расстояния в метрическом пространстве.
Выбор конкретных мер зависит в первую очередь от цели их примене-
ния или исследования. Существующие меры тесно связаны между собой в
том плане, что оценивают в конечном итоге вероятность того, что сравни-
ваемые объекты будут идентичными. Достаточно простыми в вычислитель-
ном плане есть ассоциативные меры, которые сводятся к «подсчету» числа
нужных элементов, что отражает меру частичного соответствия объектов.
Кроме того, ассоциативные меры легко распространяются на случай анализа
компонент. При применении мер для элементов сравниваемых множеств
необходимо ввести некоторый критерий эквивалентности.
Пусть U — некоторый универсум дескрипторов U∈λ . Обозначим
21, ΛΛ — конечные множества дескрипторов, U⊂ΛΛ 21, , )1(
1
11 }{ µλ ==Λ ii ,
)2(
1
22 }{ µλ ==Λ ii , (1), ( 2 )µ µ — мощности множеств. Введем на U некоторое
расстояние ),( 0λλρ между дескрипторами U∈0,λλ , которое определяет
нормированное метрическое пространство ),( ρU=ℑ , ]1,0[: →×UUρ .
В качестве ρ может быть использована произвольная метрика, чаще всего
для КТ применяют евклидово или манхэттенское расстояние в веществен-
ном векторном пространстве nR , nRU ⊆ . Распространенными способами
нормировки дескрипторов есть деление на норму вектора или на макси-
мальное значение среди компонент [11].
Рассмотрим правило ϕ , соответствующее попаданию дескриптора λ
внутрь шара радиуса δ с центром в 0λ
δλλρϕ ≤),(: 0 . (1)
Правило (1) определяет для каждого из множеств 21, ΛΛ некоторое се-
мейство шаров с параметрами δ , ρ и устанавливает бинарное отношение
неразличимости дескрипторов [2]. Принадлежность шару означает эквива-
лентность 0, λλ . Параметр δ определяет степень точности при установле-
Рис. 2. Схема обработки данных при распознавании
В.А. Гороховатский
ISSN 1681–6048 System Research & Information Technologies, 2011, № 1 60
нии неразличимости. С увеличением δ растет размер конгломератов экви-
валентных КТ. Заметим, что ]1,0[∈δ в силу нормированной метрики ρ .
Правилом (1) задаются эквивалентные подмножества элементов как между
множествами 21, ΛΛ , так и внутри каждого из них. Выполнение условия (1)
проверяется посредством предиката
⎩
⎨
⎧ ≤
=
,else 1,
,),( ,0
]),,([ 0
0
δλλρ
δλλρL
равного 0 или 1 в зависимости от истинности неравенства и определяющего
некоторое подмножество эквивалентных элементов. Применение L озна-
чает переход к представлению компоненты в виде дихотомического
признака. Вторым способом анализа есть пороговая обработка вида
⎩
⎨
⎧ ≤
=
,else 1,
,),( ),,(
]),,([ 00
0
δλλρλλρ
δλλρδL
где при выполнении правила (1) сходство элементов равно значению метри-
ки ),( 0λλρ . Области формирования близких значений для L и δL совпа-
дают, однако при использовании δL сохраняются значения метрики
),,( 0λλρ которые можно использовать как веса элементов.
Применим ассоциативные меры сходства с целью определения величи-
ны близости множеств 21, ΛΛ [3–5]. Определим для множеств 21, ΛΛ на ос-
нове (1) операции пересечения 21 Λ∩Λ=C и разности 21
1 \ ΛΛ=A ,
12
2 \ ΛΛ=A . Обозначим мощности полученных множеств как )(Cc µ= ,
).( ),( 21 AbAa µµ == Наиболее популярны в задачах обработки сложных
сигналов меры, полученные на основе множеств 21,, AAC : функция Жак-
кара );/(1 cbacK ++= функция Съеренсена )/(22 bacK += ; функция Дей-
ка );2/(23 cbacK ++= функция Кульчинского );2/()(4 abbaK += процент
несогласия );/()(5 cbabaK +++= функция Соукала и Снита
))(2/(6 baccK ++= ; несимметричный трансформированный коэффициент
Дейка )),(min(/)),(min(7 bacbacK +−= и другие.
Ассоциативные меры обладают такими достоинствами, как универ-
сальность и быстродействие вычислений. Кроме того, они, как правило, без-
размерны и ограничены отрезком ]1;0[ . Каждая из мер имеет свои особен-
ности. Например, мера 7K задана отрезком ]1;1[− , а 2K ненормирована,
т.к. пересечение может превышать величину симметрической разности.
Значения отдельных функций, например, 2K , 4K не определены при сов-
падении множеств, т.к. при этом выполняется 0== ba , поэтому меры нуж-
но доопределить для этих случаев. Заметим также, что меры 51, KK можно
выразить друг через друга. Значение )( ba + — мощность симметрической
разности множеств 21, ΛΛ , широко используемой в интеллектуальном ана-
Оценка сходства структурных объектов как множеств компонент
Системні дослідження та інформаційні технології, 2011, № 1 61
лизе данных, связанном с проблемами грануляции информации [2, 6]. Вели-
чина )( ba + есть расстояние между множествами 21, ΛΛ [6]. Значе-
ние )2( cba ++ соответствует сумме мощностей ).2()1( µµ + Одним из кри-
териев выбора конкретной функции есть относительная важность событий
совпадения или несовпадения элементов. Например, функция 3K придает
вдвое больший вес совпадающим элементам, а функция 6K — несовпа-
дающим. Самым естественным вариантом функции сходства есть отноше-
ние числа совпадающих признаков к их общему числу.
В работе [3] обсуждается понятие эквивалентности мер в том плане,
что две идентичные меры приводят к одной и той же последовательности
объектов, упорядоченных по их сходству, близкие объекты остаются близ-
кими и т.д. Например, можно показать, что свойством эквивалентности об-
ладает континуум мер сходства, представленных формулой:
]2)2)(1[(/2 ccbacK αα −+++= , (2)
где ∞<<− α1 . Нетрудно заметить, что при 0=α из (2) имеем функцию
2K , при 1=α — функцию 1K , тогда 3=α соответствует величине 6K ,
поэтому споры о том, какой из коэффициентов лучше, считаются беспред-
метными. Определение эквивалентности мер приводит к необходимости
использования на практике именно неэквивалентных мер, оценивающих
разносторонние свойства анализируемых объектов. Если, например, выво-
ды, полученные на основе корреляционных мер сходства, совпадут с выво-
дами анализа на основе евклидовой метрики, то с уверенностью можно ут-
верждать, что они действительно основаны на свойствах исходных данных,
а не на способе их извлечения [3]. Выражения для функций 71 ,..., KK и (2)
могут быть обобщены для количественных признаков, принимающих ко-
нечное множество числовых значений [5]. Здесь величины a,b,c для выра-
жений 71 ,..., KK вычисляются следующим образом:
∑∑ =−==
ki
ki
ki
kiki cba
,
21
,
2121 ),(min ,)],(min),([max λλλλλλ . (3)
В случае фиксированного соответствия между компонентами сравни-
ваемых множеств, как это применено в модификациях корреляционных
подходов при анализе изображений [9], реализация мер сходства упрощает-
ся и приобретает вид векторно-пространственной модели, когда необходимо
осуществить сопоставление и подсчитать число сходных компонент векто-
ров. В то же время для более общего случая в силу наличия геометрических
преобразований нет возможности точно установить соответствие компонент
в процессе измерений, поэтому требуется осуществлять перебор на неко-
тором подмножестве соответствий. Наиболее полный вариант анализа соот-
ветствий реализуется путем перебора всевозможных пар ),( 21
ki λλ элемен-
тов. Количество сравнений при этом оценивается произведением
).2()1(12 µµµ =
Схема применения более сложных в вычислительном аспекте корреля-
ционных мер или расстояний для задач компонентного представления прак-
В.А. Гороховатский
ISSN 1681–6048 System Research & Information Technologies, 2011, № 1 62
тически не отличается от использования ассоциативных мер. Преимущество
метрик состоит в возможности построения на их основе быстродействую-
щих процедур поиска [6]. Принципиальным моментом, позволяющим осу-
ществить анализ структуры объектов, есть включение в процесс обработки
отбора близких дескрипторов, что дает возможность оценить частичное
сходство. Оценка сходства путем подсчета совпадений элементов приводит
к мысли о возможности применения на множестве соответствий расстояния
Хемминга [5], в классическом представлении подсчитывающего число раз-
личающихся элементов для двух последовательностей одинаковой длины.
Для оценки степени соответствия множеств 21, ΛΛ можно предложить сле-
дующую модификацию метрики Хемминга
,]),,([][),( )1(
1
)2(
1
211
12
21 ∑ ∑= =
−=ΛΛ
µ µ δλλρµρ
i k kiH L (4)
где в качестве нормировочного коэффициента используется произведение
мощностей 12µ . Значение Hρ принадлежит отрезку ]1,0[ . Метрика (4) по
сравнению с другими обладает важным свойством структурного анализа
данных внутри сравниваемых множеств. Запишем выражение для метрики
),( 21 ΛΛΛρ на основе обработки δL в следующем виде:
∑ ∑= =
−
Λ =ΛΛ )1(
1
)2(
1
211
12
21 ]),,([][),( µ µ δ δλλρµρ i k kiL . (5)
Соотношение (5) как линейную комбинацию метрик можно считать
метрикой [11]. Метрика (5) является модификацией расстояния «средней
связи», однако, в отличие от (4) не отражает напрямую числа различающих-
ся элементов множеств и поэтому носит символический характер «средней
температуры». Сумма значений в пределах порога δ при фиксированном
12µ может дать лишь приближенную оценку числа таких элементов. Заме-
тим, что в случае, когда для всех элементов первого множества выполняется
правило (1), величина (5) равна значению метрики средней связи. В частном
случае ненулевое значение метрики (5) может быть получено даже по одной
паре схожих компонент, что может быть недопустимым с точки зрения дос-
товерности решения. В таком случае метрику (5) нужно дополнить логиче-
ским условием вида
⎪⎩
⎪
⎨
⎧ >ΛΛ
=ΛΛ Λ
Λ
,else ,
,N ),,(
),( L
21
21
ε
ε
ε
ρ
ρ
ρ
N
(6)
где εN — некоторое пороговое значение для минимально допустимого
числа соответствий, LN — реальное число соответствий, полученное в про-
цессе вычисления (5) и равное числу неединичных значений предиката ;L
ερ — некоторое символическое значение метрики, означающее ситуацию
«полного отсутствия» сходства при введенных ограничениях. Логический
анализ вида (6) дает возможность обеспечить заданную достоверность при-
нятия решения о сходстве, определяемую числом имеющихся соответствий.
Еще один вариант модификации метрики средней связи можно получить
нормировкой на число LN близких элементов
Оценка сходства структурных объектов как множеств компонент
Системні дослідження та інформаційні технології, 2011, № 1 63
∑ ∑= =
−
Λ =ΛΛ )1(
1
)2(
1
211
L
21 ]),,([]N[),( µ µ δλλρρ i k ki
NL , (7)
где предикат NL отличается от δL заменой 1 на 0. Принципы, использован-
ные при построении (4)–(7), можно распространить и на другие метрики.
СХОДСТВО В ТЕРМИНАХ АНАЛИЗА СООТВЕТСТВИЙ
Опишем множество 12
iθ соответствий элемента 11 Λ∈iλ во множестве 2Λ в
виде ]}),,([:{ 21*2212 δλλρλθ kiki LΛ∈= , где *L — один из рассмотренных пре-
дикатов. В частных случаях множество 12
iθ может включать лишь один
элемент (однозначное соответствие) или вообще не содержать элементов
∅=12
iθ (пустое соответствие). Аналогичным образом описываются множе-
ства соответствий 11
iθ и 22
iθ внутри объектов 21, ΛΛ . Совместный анализ
множеств соответствий 11
iθ , 22
iθ может использоваться для оценки потен-
циальных возможностей различения объектов в пространстве дескрипторов.
Учитывая, что мощности множеств соответствий и несоответствий для ко-
нечных множеств связаны между собой однозначным образом, меру множе-
ства соответствий считаем мерой сходства.
Основой для вычисления сходства (4), (5) компонентных объектов яв-
ляется прямоугольная матрица расстояний ),(),( 21
kiki λλρρ = , )1(,...,1 µ=i ;
)2(,...,1 µ=k . Строка матрицы ),( kiρ соответствует расстояниям i -го деск-
риптора первого объекта до каждого из дескрипторов второго. Перейдем от
матрицы расстояний к ее представлению в виде матрицы соответствий
),( kiΘ тех же размеров путем реализации отображения →Ω ),(: kiρ
),( kiΘ→ , и на основе ),( kiΘ определим функцию сходства. Построение
матрицы ),( kiΘ и ее анализ сводится к нескольким возможным вариантам.
Во-первых, должен быть выбран однозначный или множественный тип со-
ответствия 12
iθ дескрипторов, который определяется количеством элемен-
тов множества 2Λ , которые могут считаться эквивалентными элементу из
1Λ . При однозначном типе множество 12
iθ содержит максимум один эле-
мент, тогда строка матрицы ),( kiΘ может содержать только один неединич-
ный элемент (единица означает отсутствие соответствия). При множествен-
ном соответствии в строке ),( kiΘ может быть произвольное или строго
фиксированное число элементов (в пределах от 0 до )2(µ ).
Во-вторых, в зависимости от применяемого предиката задается бинар-
ный или многозначный вид соответствия. Бинарная обработка реализуется
предикатом L и матрица ),( kiΘ приобретает двоичный вид. При много-
значном представлении матрица ),( kiΘ , кроме единиц, содержит элементы
),( kiρ , т.е. ]]),,([|),([),( δρρ δ kiLkiki =Θ , где отличие от 1 означает соот-
ветствие.
В.А. Гороховатский
ISSN 1681–6048 System Research & Information Technologies, 2011, № 1 64
Каждый из вариантов обработки имеет свои особенности применения.
Например, при множественном многозначном представлении имеем матри-
цу, каждая строка которой содержит определенное число элементов со зна-
чениями из отрезка ],0[ δ , что при построении общего сходства требует до-
полнительных действий по выбору одного из них либо нормировки. Учет
множественных соответствий предполагает при формировании общего
сходства выбор одного из вариантов для веса соответствия: все соответствия
равноценны с весом 1; соответствия равноценны с весом, равным m/1 , где
m — их число в строке; вес соответствия определяется величиной ),( kiρ и
т.д. Однако множественные соответствия в целом оказываются устойчивее к
действию помех, чем однозначные [7, 10]. Кроме того, при получении одно-
значных соответствий по сравнению с множественными необходимы до-
полнительные вычисления, связанные с поиском оптимумов, ранжирова-
нием и т.д. В методах SIFT получил применение вариант однозначного
способа установления соответствий с дополнительной проверкой надеж-
ности такого решения путем анализа величины второго оптимума [8].
Опишем теперь сходство как функцию ).,( kiΘ Одним из вариантов
есть выражение
∑ ∑= =
−
Λ Θ=ΛΛ )1(
1
)2(
1
1
12
21 ),(][),( µ µµρ i k ki , (8)
представляющие собой значение метрики (4), (5) с учетом типа соответст-
вия. Для случая однозначных бинарных соответствий значение суммы в (8)
есть число строк, содержащих ноль, что соответствует числу «одинаковых»
элементов множеств. В случае многозначных бинарных соответствий сумма
в соотношении (8) означает общее число всех не совпавших элементов (с
учетом повторений). Для других типов соответствия значение (8) можно
отнести к модификациям метрик: ближнего соседа (однозначные соответст-
вия), m ближайших соседей (фиксированное число m наиболее сходных
элементов), метрики средней связи (многозначные). Во всех перечисленных
модификациях учитываются близкие элементы множеств, для сходства ко-
торых выполнена пороговая обработка δL .
Заметим, что нормировка в (8) играет важную роль для анализа сходст-
ва. Например, при бинарных однозначных соответствиях для двух одинако-
вых множеств с различающимися элементами (без повторений) значение
суммы в (8) равно )1(12 µµ − , или ]1)2()[1( −µµ , а величина (8) для этой си-
туации равна )2(/11 µρ −=Λ . В то же время для идентичных множеств
0=Λρ . Это говорит о необходимости применения различных подходов для
этих ситуаций, по-своему отражающих событие совпадения множеств. На-
пример, более практичным вариантом для случая неповторяющихся элемен-
тов вместо метрики (8) может оказаться сходство
∑ ∑= =
− Θ−= )1(
1
)2(
1
1 )],(1[)]]2(),1([min[ µ µµµ i k kiK , (9)
равное 1 при полном совпадении. Выражение (9) точнее отражает суть со-
поставления множеств компонент как подсчет относительной доли одина-
ковых элементов. В то же время (8) более универсально и не требует допол-
нительной проверки повторяемости элементов.
Оценка сходства структурных объектов как множеств компонент
Системні дослідження та інформаційні технології, 2011, № 1 65
При построении мер сходства в задачах распознавания, когда анализи-
руемый объект (например, множество 2Λ ) поочередно сравнивается с базой
эталонов, нормировка при определении доли однозначных соответствий
может быть реализована путем деления на ),1(µ которое в данном случае
отражает максимально возможное их число. Тогда мера сходства есть доля
элементов эталона, которые нашли свое соответствие в объекте, и вычисля-
ется как ),1(/ µη=K где числитель η равен числу установленных соответ-
ствий.
Важным для задач анализа визуальных данных является также распо-
ложение нулей в матрице соответствий. Понятно, что если в каждой строке
и каждом столбце содержится только один ноль, то мы имеем дело с одно-
временным соответствием нескольких пар элементов разных множеств, что
должно отражаться на значении метрики. Этим качеством описанные мет-
рики и меры сходства не обладают, что говорит о необходимости их даль-
нейшего усовершенствования. В некоторой мере это учтено в мерах на ос-
нове отношений, изложенных ниже.
На базе значений i -той строки матриц ),( kiρ или ),( kiΘ может быть
сформирована промежуточная мера сходства типа элемент-множество, на
основе которой в дальнейшем можно вычислить сходство двух множеств.
Особенно актуален такой вид сходства для тех задач распознавания, где для
каждого структурного элемента объекта вначале осуществляется оценка
класса, а затем по совокупности полученных оценок принимается глобаль-
ное решение о классе объекта. С другой стороны, практика задач компью-
терного зрения показывает, что результат распознавания по сходству мно-
жеств часто оказывается более достоверным в условиях помех, чем
принятие решения по совокупности локальных решений.
МЕРЫ НА МНОЖЕСТВЕ ОТНОШЕНИЙ
Введем на универсуме U дескрипторов некоторое отношение UR ,
U...UURU ×××⊆ . Для конкретности рассмотрим бинарные отношения
UURU ×⊆ и сформулируем принципы построения и сравнения отношений
из множества UR . Наиболее применимы в анализе данных отношения не-
различимости (равенство), предшествования (ранжирование) и соседства
[2]. При анализе изображений дополнительно рассматривают два типа от-
ношений: амплитудные и пространственные [7]. Амплитудные отношения
характеризуют связь на множестве значений дескрипторов (неразличи-
мость), пространственные — связь между их координатами, отражающую
важные для визуальных данных геометрические аспекты (соседство).
Бинарное амплитудное отношение URr ∈11 для элементов ∈11, ji λλ
1Λ∈ множества 1Λ может быть описано в виде совокупности
)},(|),{( 111111
jiji Rr λλλλ= , где ),( 11
jiR λλ (или ][ 11rR ) — правило, форми-
рующее отношение. Примером ),( 11
jiR λλ могут быть предикаты ., δLL
В.А. Гороховатский
ISSN 1681–6048 System Research & Information Technologies, 2011, № 1 66
Конкретно для элементов первого множества отношение имеет вид:
}),(|),{( 111111 δλλρλλ ≤= jijir или }.|),{( 1111 Lr ji λλ= Аналогично можно
описать отношение 12r и между элементами множеств 21, ΛΛ . Пространст-
венное бинарное отношение для элементов 111, Λ∈ji λλ имеет вид
)},(|),{( 111111
jicjic ccRccr = или конкретно }),(|),{( 111111
cjicjic ccccr δρ ≤= , где
11, ji cc — координаты элементов 11, ji λλ , cρ — метрика в координатном
пиксельном пространстве, cδ — порог, определяющий размер пространст-
венной окрестности, в пределах которой элементы 11, ji λλ считаются удов-
летворяющими отношению cR . Как правило, координатные отношения
имеют смысл близости или соседства. Величина cδ должна быть согласова-
на с соответствующим значением для множества 2Λ с учетом допустимых
геометрических преобразований и определяет возможность «склеивания» (в
плане совместного анализа) для пары компонент между собой. Другой при-
мер правила cR может быть связан с заданием бинарных пространственных
отношений в виде дуальных графов [12], отражающих связь пар компонент.
Правило для формирования отношения 12r представим в виде
конъюнкции
)),((&)),((:][ 212112 δλλρδλλρ ≤≤ lkjirR .
Установим теперь правило cRR & для одновременного применения
221112 ,, cc rrr в виде
&)),((&)),((:],,[& 2121221112 δλλρδλλρ ≤≤ lkjiccc rrrRR
)),((&)),((& 2211
cljcckic cccc δρδρ ≤≤ , (10)
которое означает выполнение (1) для каждой из пар элементов (амплитуд-
ное отношение 12r ) и двух условий для соответствующих координат, реали-
зующих пространственное отношение .2,1, =kr kk
c В целом выражение (10)
можно представить как новое отношение 12
4r для четверки:
),,(|)),(),,(),,(),,{( 21122222111112
4 jilljjkkii rccccr λλλλλλ=
)},(),,(),,( 222211112112
ljckiclk ccrccrr λλ . (11)
Отношение (11) можно трактовать как установление соответствия для
пары точек двух разных объектов, причем координаты точек, в свою оче-
редь, включены в пространственные отношения 2211, cc rr внутри каждого из
объектов. Выражение (11) можно использовать для построения новых ком-
понент. Оно легко распространяется на произвольное число пар компонент,
пространственное отношение которых фиксирует некоторую геометрию ви-
зуального объекта.
Оценка сходства структурных объектов как множеств компонент
Системні дослідження та інформаційні технології, 2011, № 1 67
В целом отношение (11) построено на метриках ,ρ cρ и может быть
использовано в выражениях для ассоциативных мер 71 ,..., KK и метриках
типа (4)–(7). При этом фактически будет реализован подсчет количества
отношений, установленных для элементов двух множеств. Здесь вместо
предиката L необходимо использовать новый предикат ,rL проверяющий
выполнение отношения вида (11). В метриках на основе обработки δL и
сходствах, связанных с ранжированием, дополнительно можно численно
оценивать степень выполнения отношения (11). Примером такой оценки
есть сумма ).,(),( 2121
lkji λλρλλρ +
Некоторые координатные подмножества точек, применяемые в ряде за-
дач компьютерного зрения, дают возможность построить геометрические
инварианты относительно аффинных преобразований [10]. В этом случае
координатные отношения точек в виде значений геометрических инвариан-
тов могут быть дополнены значениями соответствий их дескрипторов, уста-
навливаемых посредством (10), (11), что в целом даст возможность усовер-
шенствовать существующие подходы и повысить достоверность решений.
Применение отношений по сравнению с использованием одиночных
дескрипторов в плане достоверности распознавания имеет существенно
лучшие показатели. Заметим, что предлагаемая схема анализа визуальных
данных путем построения отношений может быть успешно расширена на
любую арность (число элементов), которые они содержат. С другой сторо-
ны, увеличение числа элементов приводит к усилению интегральных ка-
честв системы сопоставления, одновременно снижая устойчивость к ло-
кальным искажениям элементов множеств. Учитывая направленность таких
схем обработки на устранение локальных искажений, целесообразно приме-
нять только двух- или трехместные отношения КТ, причем в целях ускоре-
ния вычислений использовать не полные, а целенаправленно сформирован-
ные усеченные подмножества отношений [10].
ЭКСПЕРИМЕНТЫ
Предварительный расчетный анализ рассмотренного разнообразия мер
структурного соответствия показал следующее. Меры 42 , KK в силу своих
особенностей не обладают свойством непрерывности при изменении объема
информации, выражающемся в числе дескрипторов, в меньшую или боль-
шую сторону. Мера 7K также слабо реагирует на изменения структуры
объекта. Метрика (5) при удачно выбранном пороге δ практически не отли-
чается от метрики (4), и ее целесообразно применять лишь с нормировкой
на число «близких» элементов аналогично (7). Среди остальных мер из на-
бора 71 ,..., KK следует выделить ,,, 531 KKK в одинаковой степени реаги-
рующие на добавление и удаление дескрипторов списка, а при необходимо-
сти выбора предпочтение следует все-таки отдать мере 1K , более точно
отражающей уровень структурных изменений по сравнению с 3K .
В целях более тщательного качественного анализа обсуждаемых мер
для практических наборов признаков проведены компьютерные экспери-
В.А. Гороховатский
ISSN 1681–6048 System Research & Information Technologies, 2011, № 1 68
менты на реальных изображениях. В качестве компонент использованы
множества КТ, полученные применением варианта детектора SIFT для базы
данных, содержащей 30 полутоновых изображений аквариумных рыбок
размером 100100× пикселей, описанной в [7]. На рис. 3 показано изображе-
ние одного из эталонов, а также размещенные в оверлейном режиме на нем
и еще на трех эталонах дескрипторы (темные точки). Число дескрипторов на
выделенном эталоне равно 42.
По результатам моделирования представлена таблица значений мер при
сравнении выбранного эталона в пространстве признаков с собой (стол-
бец 1) и с другими 4-мя эталонами с примерно таким же числом признаков.
Наряду со значениями мер 71 ,..., KK и метрик (4), (5) в таблицу включены
значения меры для бинарных соответствий на базе отношения 12r , вычис-
ленной как rrK µη /9 = , где rη — число полученных соответствий пар, rµ
— общее число пар. Рассмотрены две разновидности: 1
9K — однозначные
соответствия с нормировкой на число пар в 1Λ и 2
9K — многозначные
соответствия (порог) с нормировкой на произведение числа пар. В целях
сравнения приведены также аналогичные значения мер 1
8K , 2
8K для оди-
ночных соответствий, установленных по оптимуму сходства. Для сопостав-
ления дескрипторов использовано евклидово расстояние векторов, а значе-
ние порога выбрано ,113,0=δ что соответствует 1% от максимального
значения метрики, равного .128 Как видим из таблицы, значения мер (4) и
(5) отличаются, только начиная со 2-го знака после запятой, что говорит об
удачно выбранном пороге δ , отражающем близость дескрипторов. При
этом меры (4) и (5) на «своем» эталоне дают величину сходства около 0,88,
что несколько отклоняется от минимально возможного значения, равного 0.
Несмотря на это, с применением всех обсуждаемых мер без помех дости-
гается безошибочное распознавание на анализируемой базе из 30 эталонов.
Значения мер для реальных изображений, приведенные в таблице, в целом
подтверждают предварительные оценки.
Оценим теперь свойства мер с точки зрения влияния на их величину
искажений типа исключения КТ или появления ложных КТ. Уровень поме-
хи добавления ложного элемента задавался вероятностью ,1β а вероятность
2β отражала событие исключения признака из списка КТ. Заметим, что для
ряда мер, где нормировка происходит путем деления на величину ,12µ дей-
ствие этих двух типов помех имеет некоторые различия. В частности, бы-
вают ситуации, когда исключение общих дескрипторов не изменяет значе-
ния меры, что означает ее нечувствительность к таким искажениям.
Рис. 3. Эталоны и характерные признаки
Оценка сходства структурных объектов как множеств компонент
Системні дослідження та інформаційні технології, 2011, № 1 69
Координаты и значения ложных дескрипторов в эксперименте формирова-
лись с использованием равномерного распределения. В таблице в качестве
примера приведены величины сходства исходного и искаженного множеств
дескрипторов объекта на рис. 3 при значениях 25,01 =β и ,25,02 =β что
соответствует изменению примерно четвертой части состава дескрипторов.
Из таблицы путем сравнения с первым столбцом видим, что все рассматри-
ваемые меры в той или иной степени реагируют на локальные искажения,
однако более точно отражают действие таких помех меры ),( 51 KK 98 , KK
и метрики (4), (5). Мера 7K не реагирует на искажения такого типа. Анализ
пар в мерах 2
8K , 2
9K по отношению к одиночным соответствиям, как ви-
дим, обеспечивает большую чувствительность к помехам исключения, а
также более высокую достоверность решений относительно других этало-
нов базы, т.к. локальные оптимумы мер относительно глобального оптиму-
ма здесь менее значительны, чем в мерах ,1
8K 1
9K . Отметим, что для мер
(4), (5) при помехе исключения наблюдаются значения ниже, а у мер ,2
8K
2
9K выше, чем у эталона. Это объясняется изменением базы суммирования
при помехе исключения и говорит о сложности использования в этих мерах
пороговых способов для принятия решений. Несмотря на эти особенности,
все обсуждаемые меры обеспечивают правильное распознавание изображе-
ния на рис. 3 для используемой базы данных при заданном уровне помех.
Т а б л и ц а . Значения мер для множеств дескрипторов
Функция 1 2 3 4 5 25,01 =β 25,02 =β
1K 1 0,68 0,64 0,54 0,76 0,85 0,89
2K 84 4,21 3,53 2,38 6,33 5,5 6,8
3K 1 0,81 0,78 0,70 0,86 0,92 0,94
4K 0 0,28 0,14 0,15 0,19 0,5 0,5
5K 0 0,31 0,36 0,46 0,24 0,15 0,11
6K 1 0,51 0,47 0,37 0,61 0,73 0,79
7K 1 0,90 0,71 0,72 0,81 1 1
(4) 0,8775 0,9494 0,9324 0,9259 0,9365 0,8992 0,874
(5) 0,8826 0,9520 0,9355 0,9296 0,9400 0,9034 0,8792
1
8K 1 0,7142 0,9523 0,5952 0,9047 0,8461 1
2
8K 0,1224 0,0676 0,0505 0,0741 0,0663 0,1007 0,1260
1
9K 1 0,53 0,74 0,46 0,62 0,87 1
2
9K 0,0107 0,0044 0,0028 0,0046 0,0043 0,0073 0,0115
ВЫВОДЫ
Методы вычисления мер эквивалентности для компонентного представле-
ния визуальных объектов в условиях искажений компонент сводятся к по-
В.А. Гороховатский
ISSN 1681–6048 System Research & Information Technologies, 2011, № 1 70
строению частичных мер для множеств, учитывающих модель искажений.
Основная идея состоит в построении модификаций, связанных с раздельным
анализом сходства-различия комбинаций компонент. Применение аппарата
соответствий сосредотачивает решение проблемы на выделении наиболее
значимых данных, а построение отношений для дескрипторов позволяет
обеспечить высокую достоверность решений. С точки зрения вычислитель-
ных затрат и возможности реагирования на определенный уровень частич-
ных искажений предпочтение следует отдать мерам ,1K ,8K ,9K (4), (5).
Впервые показано, как формализовать и применить метрические
подходы для сопоставления структурных визуальных объектов в признако-
вом пространстве, изучены особенности известных подходов и обсужден
синтез мер с новыми свойствами.
Практически важным есть сравнение принципов построения и норми-
ровки мер, получение конкретных характеристик на используемой экспери-
ментальной базе изображений, что подтверждает целесообразность приме-
нения предложенных модификаций в задачах компьютерного зрения.
Перспективы исследования состоят в разработке теоретических основ
для построения интегрированного сходства по совокупности разнотипных
признаков, включающих как значения, так и отношения разной арности, а
также оценка предельных характеристик методов в задаче распознавания
объектов при действии фоновых и локальных мешающих воздействий.
ЛИТЕРАТУРА
1. Поспелов Д.А. Искусственный интеллект. Модели и методы: Справочник. — В
3-х кн. Кн. 2. — М.: Радио и связь, 1990. — 304 с.
2. Миркин Б.Г. Анализ качественных признаков и структур. — М.: Статистика,
1980. — 319 с.
3. Шитиков В.К. Количественная гидроэкология: методы системной идентифи-
кации. — Тольятти: ИЭВБ РАН, 2003. — 463 с.
4. Баклицкий В.К. Методы фильтрации сигналов в корреляционно-экстремальных
системах навигации. — М.: Радио и связь, 1986. — 216 с.
5. Елисеева И.И. Группировка, корреляция, распознавание образов (Статистические
методы классификации и измерения связей). — М.: Статистика, 1977. — 144 с.
6. Каграманян А.Г. Метрические свойства грануляции информации // Бионика
интеллекта. — 2007. — № 1 (66). — С. 17–24.
7. Гороховатский В.А. Структурное распознавание изображений на основе моде-
лей голосования признаков характерных точек // Реєстрація, зберігання і
обробка даних. — 2008. — Т. 10, № 4. — С. 75–85.
8. Lowe D.G. Distinctive Image Features from Scale-Invariant Keypoints // Interna-
tional Journal of Computer Vision. — 2004. — 60, № 2. — Р. 91–110.
9. Путятін Є.П. Методи та алгоритми комп’ютерного зору: навч. посіб. — Х.:
ТОВ «Компанія СМІТ», 2006. — 236 с.
10. Гороховатский В.А. Иерархия пространственных отношений структурных
признаков в задачах сопоставления визуальных объектов // Системи
управління, навігації та зв’язку. — Київ: Центральний наук.-досл. ін-т наві-
гації і управління, 2008. — Вип. 3 (7). — С. 85–89.
11. Айвазян С.А., Бухштабер В.М., Енюков И.С, Мешалкин Л.Д. Прикладная стати-
стика: Классификация и снижение размерности: справ. изд. — М.: Финансы
и статистика, 1989. — 607 с.
12. Дуда Р. Распознавание образов и анализ сцен. — М.: Мир, 1976. — 512 с.
Поступила 26.01.2009
|
| id | nasplib_isofts_kiev_ua-123456789-50085 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-12-07T18:57:46Z |
| publishDate | 2011 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Гороховатский, В.А. 2013-10-04T18:57:08Z 2013-10-04T18:57:08Z 2011 Оценка сходства структурных объектов как множеств компонент / В.А. Гороховатский // Систем. дослідж. та інформ. технології. — 2011. — № 1. — С. 57-70. — Бібліогр.: 12 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50085 004.932.2 Рассматриваются вопросы сопоставления изображений визуальных объектов в системах компьютерного зрения. Предложены меры сходства, учитывающие искажение и появление ложных компонент в структурном описании. Проведен анализ свойств методов. Описаны результаты компьютерного моделирования для реальных изображений. Розглянуто питання зіставлення зображень візуальних об’єктів у системах комп’ютерного зору. Запропоновано міри схожості, які враховують викривлення та появу хибних компонент у структурному описі. Проведено аналіз властивостей методів, описано результати комп’ютерного моделювання для реальних зображень. Problems of image comparison of visual objects in systems of computer vision are considered. The measures of similarity which takes into account distortion and occurrence of the false component in the structural description are suggested. The analysis of properties of methods is implemented, results of computer modeling for real images are described. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Оценка сходства структурных объектов как множеств компонент Оцінка подібності структурних об’єктів як множин компонент Estimation of structural objects similarity as sets of components Article published earlier |
| spellingShingle | Оценка сходства структурных объектов как множеств компонент Гороховатский, В.А. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| title | Оценка сходства структурных объектов как множеств компонент |
| title_alt | Оцінка подібності структурних об’єктів як множин компонент Estimation of structural objects similarity as sets of components |
| title_full | Оценка сходства структурных объектов как множеств компонент |
| title_fullStr | Оценка сходства структурных объектов как множеств компонент |
| title_full_unstemmed | Оценка сходства структурных объектов как множеств компонент |
| title_short | Оценка сходства структурных объектов как множеств компонент |
| title_sort | оценка сходства структурных объектов как множеств компонент |
| topic | Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| topic_facet | Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50085 |
| work_keys_str_mv | AT gorohovatskiiva ocenkashodstvastrukturnyhobʺektovkakmnožestvkomponent AT gorohovatskiiva ocínkapodíbnostístrukturnihobêktívâkmnožinkomponent AT gorohovatskiiva estimationofstructuralobjectssimilarityassetsofcomponents |