Сравнение и корреляция

отождествления данных. Корреляционная привязка фрагментов изображений. Обнаружение объектов и стерео

отождествление.

и коэффициенты корреляции
2. Информационный поиск: индексы и алгоритмы.
3. Признаковое

описание изображений.
4. Корреляционная привязка фрагментов изображений.
5. Корреляционное стерео отождествление.

сходства
(коэффициенты
корреляции)
Описывают ли эти данные один и тот же объект

(объекты одного класса)?

Имеется ли связь между объектами, описываемыми этими данными, и насколько она сильна?

Насколько схожи/различны объекты, описываемые этими данными?

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

размера

кругов одного размера

всех кругов

всех кругов

x' = a11x + a12y
y' = a21x + a22y

Преобразования и эквивалентность

2D-преобразования: аффинные преобразования

математических объектов, остающееся неизменным при преобразованиях определённого типа.
Концепция инварианта

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

центра тяжести образа;
положение центра тяжести образа, рассматриваемого как бинарный;
периметр образа;
отношение

квадрата периметра к площади образа;
формат;
компактность;
периметр и площадь описанного прямоугольника минимальной площади;
отношение площади описанного прямоугольника к площади образа;
отношение квадрата периметра описанного прямоугольника к его площади;
формат описанного прямоугольника;
относительные длина и ширина образа.

рассчитываются через статические моменты:




что для бинарной фигуры имеет вид:




а для

полутонового изображения

F (формата) по контурным точкам образа строится матрица рассеяния

где

и

находятся собственные числа этой матрицы

Для определения ориентации находятся собственные векторы матрицы рассеяния:



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

описанного прямоугольника рассчитываются по следующим формулам, где Т1 и Т2

- стороны описанного прямоугольника:

Отношение площади описанного прямоугольника к площади образа рассчитывается по формуле:

Отношение квадрата периметра описанного прямоугольника к его площади рассчитывается по формуле:

Формат описанного прямоугольника:


Относительные длина и ширина:

объектов в составе образа);
число дыр (есть ли дыры внутри объекта);
число

Эйлера (число объектов минус число дыр).

Множество A связно,
множество B несвязно (в нем 4 объекта),
в множестве C 3 дыры.

Топологические преобразования: тело нельзя разрывать или склеивать, но можно бесконечно сжимать и растягивать (резиновые преобразования)

С

Эйлерова характеристика есть топологический инвариант

Гомеоморфность бублика и кружки

образ в декартовой системе координат (x,y); B(x,y) - значение функции

интенсивности (x,y);
xc, yc - координаты центра тяжести образа.

моменты, инвариантные к изменению масштаба:



моменты, инвариантные к повороту:

где

Метрические оценки степени
сходства
Сравнение (сопоставление) данных
Совпадение/Несовпадение
Сходство/Различие
Классы эквивалентности
Инварианты
Меры различия
(метрики,
расстояния)
Меры сходства
(коэффициенты
корреляции)
Описывают ли эти данные

один и тот же объект (объекты одного класса)?

Имеется ли связь между объектами, описываемыми этими данными, и насколько она сильна?

Насколько схожи/различны объекты, описываемые этими данными?

этом изменения значений одной или нескольких из этих величин сопутствуют

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

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

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

определяется как математическое ожидание произведения отклонений случайных величин


где M  —

математическое ожидание.

Свойства ковариации:
Ковариация двух независимых случайных величин X и Y равна нулю.
Абсолютная величина ковариации двух случайных величин X и Y не превышает среднего геометрического их дисперсий:


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

                                                                                   ,

(верхняя строка), но не описывает наклон линейной зависимости (средняя строка),

и совсем не подходит для описания сложных, нелинейных зависимостей (нижняя строка).

дисперсии) — это доля дисперсии зависимой переменной, объясняемая рассматриваемой моделью

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

Линейная регрессия:

+ ξ

квадратом так называемого множественного коэффициента корреляции между зависимой переменной и

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

Коэффициент детерминации принимает значения от 0 до 1. Чем ближе значение коэффициента к 1, тем сильнее зависимость. При оценке регрессионных моделей это интерпретируется как соответствие модели данным. Для приемлемых моделей предполагается, что коэффициент детерминации должен быть хотя бы не меньше 50% (в этом случае коэффициент множественной корреляции превышает по модулю 70%). Модели с коэффициентом детерминации выше 80% можно признать достаточно хорошими (коэффициент корреляции превышает 90%). Значение коэффициента детерминации 1 означает функциональную зависимость между переменными.

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

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


Свойства взаимной информации:

метрическом смысле объекты должны с большей вероятностью иметь большее сходство

и меньшее различие (принадлежать к одному классу эквивалентности).
Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970. 320 pp.

компактный класс

локально компактные классы

некомпактные классы

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

|
a
b
A
B
d(a,b) = | b – a |
b – a
x
x
y
d(a,b)

= √(xa-xb)2+(ya-yb)2

плоскости со следующей квазиметрикой.
Пусть задана некая выпуклая фигура (структурирующий элемент)

S с полюсом O, граница которой ∂S не содержит полюс и описывается в ее собственных полярных координатах непрерывной циклической функцией (переменным радиусом) rS(θ), θ∈[0,2π).
Размером фигуры S назовем максимальное значение ее радиуса r(S). Фигуру с центром O и размером r будем обозначать S(O,r).
Эксцентриситетом e(S) фигуры S назовем максимальное отношение rS(θ)/rS(θ-π), θ∈[0,2π).
Определим квазирасстояние dS(A,B) как размер r такой фигуры S(A,r), которая касается точки B: B∈∂S(A,r).

0, dS(A,B) = 0 ⇔ A = B
2) dS(A,B) ≤

e(S) dS(B,A), 1 ≤ e(S) < ∞
3) dS(A,B) + dS(B,C) ≥ dS(A,C)

dS(A,B)

dS(B,A)

θ

d(A,B) = dS(A,B) rS(θBA) = dS(B,A) rS(θAB)

d(A,B)

A

B

Частный случай – круговая фигурная квазиметрика совпадает с центрально симметричной евклидовой метрикой e(S)=1.

u, v и вектор их суммы
Определение: "Вектор" это такой математический

объект, для которого определены операции сложения векторов и умножения вектора на число.

Примечание: Как и "чисел", "векторов" в математике множество. Например, функции также образуют векторное пространство.

расстояний предложенная Германом Минковским:

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

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

Примеры:

"Манхэттенская
метрика" (метрика
городских кварталов)

Х

Y

d(X,Y) = S(X∪Y) - S(X∩Y)

между точками p и q это длина отрезка pq.
В

Декартовых координатах, если p = (p1, p2,…, pn) и q = (q1, q2,…, qn)
две точки в Евклидовом пространстве, длина отрезка p q равна:

Расстояние Чебышева

в метриках Минковского:

функциями:
ρ(f1,f2) = ∫x∈[a,b] | f1(x) – f2 (x) | dx
ρ(f1,f2)

= √ ∫x∈[a,b] ( f1(x) – f2 (x) )2 dx

метрика L1

метрика L2

метрика L∞

есть естественная метрика, определённая на множестве всех непустых компактных подмножеств

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

Пример:
Расстояние между кривыми

есть естественная метрика, определённая на множестве всех непустых компактных подмножеств

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

Х

Y

DH(Х,Y)

метрика является необычным примером метрики. Название этой метрики произошло из-за

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










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

(также редакционное расстояние и) между двумя строками в теории информации

и компьютерной лингвистие — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Впервые задачу упомянул в 1965 году советский математик Владимир Иосифович Левенштейн.
Если к списку разрешённых операций добавить транспозицию (два соседних символа меняются местами), получается расстояние Дамерау — Левенштейна.

Расстояние Левенштейна и его обобщения применяются:
для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированого текста или речи).
для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» — файлы.
в биоинформатике для сравнения генов, хромосом и белков.

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

кратчайшим образом.
Обычно действия обозначаются так: D (delete) — удалить, I (insert) — вставить, R (replace) — заменить, M (match) — совпадение.

Например, для 2-х строк «CONNECT» и «CONEHEAD» можно построить следующую таблицу преобразований:






Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии, разную вероятность разных ошибок при вводе текста и т. д. В общем случае:
w(a, b) — цена замены символа a на символ b
w(ε, b) — цена вставки символа b
w(a, ε) — цена удаления символа a

определения степени сходства объектов (данных).
Большинство коэффициентов нормированы и находятся

в диапазоне от 0 (сходство отстутствует) до 1 (полное сходство).

сходства, которая является числом общих элементов (признаков) двух сравниваемых объектов:

Коэффициент

сходства Жаккара:




Меры включения
Это несимметричные меры, которые показывают степень сходства (включения) одного объекта относительно другого:

A

B

                                         или                     .

меры включения Сёренсена



меры включения Жаккара                             .

векторами — операция над двумя векторами, результатом которой является число (скаляр),

не зависящее от системы координат и характеризующее длины векторов-сомножителей и угол между ними. Данной операции соответствует умножение длины данного вектора x на проекцию другого вектора y на данный вектор x.
Эта операция обычно рассматривается как коммутативная и линейная по каждому сомножителю.
Обычно используется одно из следующих обозначений:

или (обозначениеили (обозначение Дирака, часто применяемое
в квантовой механике для векторов состояния):
     .
Обычно предполагается что скалярное
произведение положительно определено, то есть
             для всех       .

 A • B = |A| |B| cos(θ)

=
〈A,B〉
|| A || || B ||
|| A || =

; || B || =

√〈A,A〉

√〈B,B〉

Нормированный коэффициент линейной корреляции:

g0) = 〈f - f0,g - g0〉 / (|| f

- f0 || || g - g0 ||)
есть скалярное произведение нормированных центрированных функций:
f*(x) = (f(x) - f0) / || f(x) - f0 ||,
g*(x) = (g(x) - g0) / || g(x) - g0 ||,
KN(f*,g*) = (f*,g*).

f(x)

x

g(x) = a + bf(x)

x

f0

g0

f(x), g(x)

x

Функции имеют
существенные различия

g0) = 〈f - f0,g - g0〉 / (|| f

- f0 || || g - g0 ||)
есть скалярное произведение нормированных центрированных функций:
f*(x) = (f(x) - f0) / || f(x) - f0 ||,
g*(x) = (g(x) - g0) / || g(x) - g0 ||,
KN(f*,g*) = (f*,g*).

f(x)

x

g(x) = a + bf(x)

x

f0

g0

f*(x), g*(x)

x

Центрированные и нормированные
функции совпадают

f0,g - g0) = (f - f0,g - g0) /

(|| f - f0 || || g - g0 ||)
есть скалярное произведение нормированных центрированных изображений:
f*(x,y) = (f(x,y) - f0) / || f(x,y) - f0 ||,
g*(x,y) = (g(x,y) - g0) / || g(x,y) - g0 ||,
KN(f*,g*) = (f*,g*).

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

d(F,G) = f* ∧ g*,
KN(f,g) = cos(f ∧ g) = cos(d(F,G)).

cos(f ∧ g) | = | cos( d(F,G) ) |,

откуда следует неравенство треугольника для коэффициентов корреляции:
| KN(f,g) | ≥ KN(f,w) KN(w,g) – √(1 – K2N(f,w)) √(1 – K2N(w,g)),
поскольку
cos(a + b) = cos(a) cos(b) – sin(a) sin(b),
sin(a) = √(1 – cos2(a)).

Пример. Если
KN(f,w) = KN(w,g) = 1/√2 = 0,707…,
то корреляция двух крайних изображений между собой может оказаться даже нулевой:
| KN(f,g) | ≥ 0.
Это объясняет многие известные примеры «плохого» поведения теоретически «хороших» мер сходства на реальных данных.

документов представляет собой процесс выявления в некотором множестве документов (текстов

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

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

Запрос — это формализованный способ выражения информационных потребностей пользователем системы. Для выражения информационной потребности используется язык поисковых запросов — это формализованный способ выражения информационных потребностей пользователем системы. Для выражения информационной потребности используется язык поисковых запросов, синтаксис — это формализованный способ выражения информационных потребностей пользователем системы. Для выражения информационной потребности используется язык поисковых запросов, синтаксис варьируется от системы к системе. Кроме специального языка запросов — это формализованный способ выражения информационных потребностей пользователем системы. Для выражения информационной потребности используется язык поисковых запросов, синтаксис варьируется от системы к системе. Кроме специального языка запросов, современные поисковые системы — это формализованный способ выражения информационных потребностей пользователем системы. Для выражения информационной потребности используется язык поисковых запросов, синтаксис варьируется от системы к системе. Кроме специального языка запросов, современные поисковые системы позволяют вводить запрос на естественном языке.

Объект запроса — это информационная сущность, которая хранится в базе информационно-поисковой системы (ИПС). Процесс занесения объектов поиска в ИПС называется индексацией. ИПС не всегда хранит точную копию объекта, нередко вместо неё хранится суррогат или индекс.

поиска информации в Интернете.
Под поисковой системой обычно подразумевается сайтПод поисковой

системой обычно подразумевается сайт, на котором размещён интерфейс (фронт-энд) системы.

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

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

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

Поиск по базе данных проиндексированных документов включает:
Нахождение документов, соответствующих поисковому запросу
Ранжирование документов в соответствии с их релевантностью поисковым запросам
Кластеризацию (группировку) документов

от прямой, а точки, найденные поисковой системой (retr), находятся в

овале. Области красного цвета представляют ошибки поисковой системы. Красная область слева - это релевантные точки, не найденные системой (пропуск событияНа этом рисунке релевантные точки (rel) находятся слева от прямой, а точки, найденные поисковой системой (retr), находятся в овале. Области красного цвета представляют ошибки поисковой системы. Красная область слева - это релевантные точки, не найденные системой (пропуск события), красная область справа - найденные, но нерелевантные точки (ложная тревога).

Точность - это пропорция левой зелёной области по отношению к овалу (горизонтальная стрелка).



Полнота - это пропорция левой зелёной области к области слева от прямой (диагональная стрелка).

Определяется как отношение числа найденных релевантных документов к общему числу найденных документов

Отношение числа найденных релевантных документов, к общему числу релевантных документов в базе

словам с учётом возможных произвольных ошибок в написании ключевого слова

и/или целевого запроса.
Поисковые индексы – структуры данных, используемые при поиске:
векторные и кластерные модели;
модели на основе ключевых слов.
Инвертированные файлы
Сигнатурные файлы
Поисковые метрики - меры сходства или различия между словами:
Расстояния Хемминга, Левенштейна, Дамерау-Левенштейна, Джаро, Джаро-Уинклера и др.
Методы поиска
Последовательный поиск (полный перебор всех слов словаря);
Метод расширения выборки (query extension);
Метод n-грамм;
Поиск с использованием хеширования;
Методы, основанные на неравенстве треугольника (триангуляционные деревья).

относится большинство современных технологий поиска, используемых в информационно-поисковых системах, в

том числе – системах поиска в сети Интернет, обрабатывающих запросы на естественных языках (Google, Yandex…).

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

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

указателя в конце книги. ИФ – множество пар

адрес вхождения ключевого слова в документ>. Детализация адреса слова может быть различной: на уровне документа, абзаца, непосредственного места слова в тексте. Основным недостатком ИФ является его большой объём. Если не применять специальные методы сжатия списков вхождений, то размер ИФ может превышать размер исходного текстового массива в 2-3 раза.
Сигнатурные файлы (СФ) содержат сигнатуры данных, представляющие собой их упрощенные профили, в которых каждый элемент кодируется одним битом (есть вхождение ключевого фрагмента или нет такого вхождения). Размер СФ составляет порядка 50% от исходных данных. Основным недостатком сигнатурных файлов является то, что множество сигнатур однозначно определяет множество документов, но не каждый документ конкретно. Поэтому после предварительной выборки данных по сигнатурам необходима их дополнительная обработка с целью уточненной проверки на соответствие запросу.
В настоящее время разработаны методы построения сжатых ИФ, вследствие чего область применения СФ несколько сузилась. Сжатые ИФ существенно превосходят СФ по производительности для коротких запросов, но проигрывают им на длинных и очень длинных запросах. В среднем короткие запросы встречаются гораздо чаще, поэтому в большинстве систем на сегодняшний день преимущество отдается ИФ.

словаря и сравнение каждого из них с запросом в соответствии

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

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

Метод n-грамм. Идея метода заключается в построении инвертированного файла, в котором роль документов играют слова, а роль слов – подстроки длины n, называемые n-граммами. Основной недостаток метода – большой размер вспомогательного индексного файла (в 10-20 раз больше размера исходного словаря).

основе методов хеширования, состоит в подборе отображения (хеш-функции) слова, например,

во множество чисел или строк, сохраняющего основные характеристики исходного слова и устойчивого к наиболее распространённым ошибкам. Такая функция позволяет разбить слова словаря на группы и производить последовательный поиск внутри группы, вычисляемой по поисковому шаблону. Например, для разбиения на группы иногда используют хеширование по некоторому количеству первых символов слова (метод trie-деревьев). Другим известным примером является хеш-функция Soundex, встроенная в коммерческие СУБД Sybase, MS SQL Server, Oracle.

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

это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства

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

Пример двоичного дерева поиска

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

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

красно-чёрным деревьям дополнительно применяются следующие требования:
Узел либо красный, либо чёрный.
Корень — чёрный.
Все листья — черные.
Оба потомка каждого красного узла — черные.
Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.

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

Пример красно-чёрного дерева

Если изображение рассматривается не как полутоновое, а как бинарное, то

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

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

Иногда при этом еще проверяется то условие, что в "окаймлении" согласованного окна число единиц не превышает некоторого порога ("согласованная фильтрация с окаймлением").

для вычисления расстояний между изображениями используется следующая формула:


где f(x,y), g(x,y)

- функции интенсивности, X – апертура зоны поиска;
величина α∈[1,∞] - определяет характеристики используемой метрики.

Нормированный коэффициент корреляции






со свойствами.
1) -1 ≤ k(f,g) ≤1;
2) k(f,g) = 1 ⇔ g = af + b; a>0, b;
3) k(f,g) = -1 ⇔ g = af + b; a<0, b.

Примеры двумерных корреляционных полей:
1. Высокое отношение сигнал/шум
2. Среднее отношение сигнал/шум
3.

Наличие ложного пика
4. Низкое отношение сигнал/шум

1

2

3

4

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

Различные алгоритмы её решения называются алгоритмами стереоотождествления (matching procedures).

Стратегия стереоотождествления определяет общую схему решения задачи автоматического стереоотождествления. Наиболее распространенная стратегия - иерархическое отождествление.

Методы стереоотождествления:

изображений
Нормированный коэффициент корреляции

из четырех уровней для тестового изображения

стереотождествления по четырехуровневой пирамиде изображений с использованием:
(а)- только 4-го уровня

пирамиды;
(б)- 4 и 3-го уровней;
(в)- 4,3,2 уровней;
(г)- 4,3,2,1 уровней.

Сопоставление с использованием пирамиды изображений

(а) (б) (в) (г)

классическим корреляционным методом.
Сопоставление с использованием пирамиды изображений
ЦМР, вычисленная с

помощью пирамиды изображений обладает большей гладкостью и точностью.

точки высокой кривизны градиента яркости, центр тяжести области, концы линий,

точки экстремальных значений признаков

Линии

Прямые или криволинейные структуры, границы областей

Области

Сегментированные области, специфические формы (эллипсы, прямоугольники и т.д.)

Структуры

Комбинации ХЧ

пар)

пар)



Геометрическая фильтрация пар точек (большинство ложных пар удалены)

≤ km ≤ 1
Km не зависит от

Морфологический проектор преобразования яркости F(f(x,y)).

Сравнение форм:

Описание формы

>

≤ km ≤ 1
Km не зависит от

Морфологический проектор преобразования яркости F(f(x,y)).

Сравнение форм:

Описание формы

>

Но это уже тема следующей лекции…