Контекст формы

Контекст формы — это дескриптор функции, используемый при распознавании объектов . Серж Белонги и Джитендра Малик предложили этот термин в своей статье «Сопоставление с контекстами формы» в 2000 году. ^[1]

Теория [ править ]

Контекст формы предназначен для описания форм, который позволяет измерять сходство форм и восстанавливать соответствия точек. ^[1]Основная идея состоит в том, чтобы выбрать n точек на контурах фигуры. Для каждой точки p _i на форме рассмотрим n − 1 векторов, полученных путем соединения p _i со всеми остальными точками. Набор всех этих векторов представляет собой богатое описание формы, локализованной в этой точке, но слишком подробное. Основная идея заключается в том, что распределение по относительным позициям является надежным, компактным и высокодискриминационным дескриптором. Итак, для точки p _i грубая гистограмма относительных координат остальных n − 1 точек,

h_{i}(k)=\#\{q\neq p_{i}:(q-p_{i})\in {\mbox{bin}}(k)\}

определяется как контекст формы $p_{i}$ . Обычно бины считаются однородными в логарифмически-полярном пространстве. Тот факт, что контекст формы является богатым и различительным дескриптором, можно увидеть на рисунке ниже, на котором показаны контексты формы двух разных версий буквы «А».

(a) и (b) — это выбранные краевые точки двух фигур. (c) представляет собой диаграмму логарифмических интервалов, используемых для вычисления контекста формы. (d) — это контекст формы для точки, отмеченной кружком на (a), (e) — это контекст для точки, отмеченной ромбом на (b), и (f) — это контекст для треугольника. Как можно видеть, поскольку (d) и (e) являются контекстами формы для двух тесно связанных точек, они очень похожи, тогда как контекст формы в (f) сильно отличается.

Чтобы дескриптор функции был полезен, он должен иметь определенные инварианты. В частности, он должен быть инвариантным к перемещению, масштабированию, небольшим возмущениям и, в зависимости от приложения, вращению. Трансляционная инвариантность естественным образом влияет на формирование контекста. Масштабная инвариантность достигается путем нормализации всех радиальных расстояний на среднее расстояние $\alpha$ между всеми парами точек в форме ^[2]^[3] хотя можно также использовать срединное расстояние. ^[1]^[4] Эмпирически продемонстрировано, что контексты формы устойчивы к деформациям, шуму и выбросам. ^[4] используя эксперименты по сопоставлению синтетических наборов точек. ^[5]

Можно обеспечить полную вращательную инвариантность в контексте формы. Один из способов — измерить углы в каждой точке относительно направления касательной в этой точке (поскольку точки выбираются на ребрах). В результате получается полностью вращательно-инвариантный дескриптор. Но, конечно, это не всегда желательно, поскольку некоторые локальные особенности теряют свою различительную силу, если их не измерять относительно того же кадра. Многие приложения фактически запрещают инвариантность вращения, например, отличие «6» от «9».

Использование в сопоставлении форм [ править ]

Полная система, использующая контексты фигур для сопоставления фигур, состоит из следующих шагов (которые будут более подробно описаны в разделе «Детали реализации» ):

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

Подробности реализации [ править ]

Шаг 1: Поиск списка точек на краях фигуры [ править ]

Этот подход предполагает, что форма объекта по существу определяется конечным подмножеством точек на внутренних или внешних контурах объекта. Их можно просто получить с помощью детектора ребер Канни и выбора случайного набора точек на краях. Обратите внимание, что эти точки не обязательно и, как правило, не соответствуют ключевым точкам, таким как максимумы кривизны или точки перегиба . Предпочтительно отбирать форму с примерно одинаковым интервалом, хотя это не критично. ^[2]

Шаг 2: Вычисление контекста фигуры [ править ]

Подробно этот шаг описан в разделе «Теория» .

матрицы затрат : Вычисление Шаг 3

Рассмотрим две точки p и q , которые имеют нормализованные гистограммы K -бина (т.е. контексты формы) g ( k ) и h ( k ). Поскольку контексты формы представляют собой распределения, представленные в виде гистограмм, естественно использовать χ ² тестовая статистика как «стоимость контекста формы» сопоставления двух точек:

C_{S}={\frac {1}{2}}\sum _{k=1}^{K}{\frac {[g(k)-h(k)]^{2}}{g(k)+h(k)}}

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

C_{A}={\frac {1}{2}}{\begin{Vmatrix}{\dbinom {\cos(\theta _{1})}{\sin(\theta _{1})}}-{\dbinom {\cos(\theta _{2})}{\sin(\theta _{2})}}\end{Vmatrix}}

Это половина длины хорды единичной окружности между единичными векторами с углами $\theta _{1}$ и $\theta _{2}$ . Его значения также варьируются от 0 до 1. Теперь общая стоимость сопоставления двух точек может быть взвешенной суммой двух затрат:

C=(1-\beta )C_{S}+\beta C_{A}\!\,

Теперь для каждой точки pi _ее на первой фигуре и точки q _j на второй фигуре рассчитайте стоимость, как описано, и назовите C _{i , j} . Это матрица затрат.

Шаг 4: Поиск соответствия, которое минимизирует общую стоимость [ править ]

Теперь соответствие один к одному $\pi (i)$ который соответствует каждой точке pi _{на форме 2 ,} на форме 1 и q _j что минимизирует общую стоимость сопоставления,

H(\pi )=\sum _{i}C\left(p_{i},q_{\pi (i)}\right)

необходим. Это можно сделать в $O(N^{3})$ время, используя венгерский метод , хотя существуют более эффективные алгоритмы. ^[6]Чтобы обеспечить надежную обработку выбросов, можно добавить «фиктивные» узлы, которые имеют постоянную, но достаточно большую стоимость сопоставления с матрицей затрат. Это приведет к тому, что алгоритм сопоставления будет сопоставлять выбросы с «фиктивным», если реального соответствия нет.

Шаг 5: Моделирование трансформации [ править ]

Учитывая набор соответствий между конечным набором точек на двух фигурах, преобразование $T:\mathbb {R} ^{2}\to \mathbb {R} ^{2}$ можно оценить для отображения любой точки из одной фигуры в другую. Существует несколько вариантов этого преобразования, описанных ниже.

Аффинный [ править ]

Аффинная модель является стандартным выбором: $T(p)=Ap+o\!$ . Решение методом наименьших квадратов для матрицы $A$ а вектор поступательного смещения o получается следующим образом:

o={\frac {1}{n}}\sum _{i=1}^{n}\left(p_{i}-q_{\pi (i)}\right),A=(Q^{+}P)^{t}

Где $P={\begin{pmatrix}1&p_{11}&p_{12}\\\vdots &\vdots &\vdots \\1&p_{n1}&p_{n2}\end{pmatrix}}$ с аналогичным выражением для $Q\!$ . $Q^{+}\!$ является псевдообратным $Q\!$ .

Тонкая пластинчатая шлица [ править ]

Модель тонкого пластинчатого сплайна (TPS) является наиболее широко используемой моделью преобразований при работе с контекстами форм. 2D-преобразование можно разделить на две функции TPS для моделирования преобразования координат:

T(x,y)=\left(f_{x}(x,y),f_{y}(x,y)\right)

где каждый из ƒ _x и ƒ _y имеет вид:

f(x,y)=a_{1}+a_{x}x+a_{y}y+\sum _{i=1}^{n}\omega _{i}U\left({\begin{Vmatrix}(x_{i},y_{i})-(x,y)\end{Vmatrix}}\right),

и функция ядра $U(r)\!$ определяется $U(r)=r^{2}\log r^{2}\!$ . Точные сведения о том, как найти параметры, можно найти в другом месте. ^[7]^[8]но по сути это включает в себя решение линейной системы уравнений . Энергию изгиба (меру того, какое преобразование необходимо для выравнивания точек) также будет легко получить.

Регуляризованный TPS [ править ]

Приведенная выше формулировка TPS содержит требование точного совпадения пар точек на двух фигурах. Для зашумленных данных лучше всего смягчить это точное требование. Если мы позволим $v_{i}$ обозначают значения целевой функции в соответствующих местах $p_{i}=(x_{i},y_{i})$ (Обратите внимание, что для $f_{x}$ , $v_{i}$ бы $x'$ координата x точки, соответствующей $p_{i}$ и для $f_{y}$ это будет координата Y, $y'$ ), ослабление требований равнозначно минимизации

H[f]=\sum _{i=1}^{n}(v_{i}-f(x_{i},y_{i}))^{2}+\lambda I_{f}

где $I_{f}\!$ это энергия изгиба и $\lambda \!$ называется параметром регуляризации. Это ƒ , которое минимизирует H [ ƒ ], можно найти довольно простым способом. ^[9] Если использовать нормализованные координаты для $(x_{i},y_{i}){\mbox{ and }}(x'_{i},y'_{i})$ , то масштабная инвариантность сохраняется. Однако если использовать исходные ненормализованные координаты, то параметр регуляризации необходимо нормализовать.

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

Шаг 6: Вычисление расстояния между фигурами [ править ]

Теперь расстояние между двумя фигурами $P\!$ и $Q\!$ . Это расстояние будет представлять собой взвешенную сумму трех потенциальных членов:

Расстояние контекста формы : это симметричная сумма затрат на сопоставление контекста формы по точкам наилучшего соответствия:

D_{sc}(P,Q)={\frac {1}{n}}\sum _{p\in P}\arg {\underset {q\in Q}{\min }}C(p,T(q))+{\frac {1}{m}}\sum _{q\in Q}\arg {\underset {p\in P}{\min }}C(p,T(q))

где T (·) — предполагаемое преобразование TPS, которое отображает точки в Q в точки в P .

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

D_{ac}(P,Q)={\frac {1}{n}}\sum _{i=1}^{n}\sum _{\Delta \in Z^{2}}G(\Delta )\left[I_{P}(p_{i}+\Delta )-I_{Q}(T(q_{\pi (i)})+\Delta )\right]^{2}

где $I_{P}\!$ и $I_{Q}\!$ — это изображения в оттенках серого ( $I_{Q}\!$ это изображение после деформации) и $G\!$ — это оконная функция Гаусса.

Стоимость трансформации : окончательная стоимость. $D_{be}(P,Q)\!\,$ измеряет, насколько необходимо преобразование, чтобы привести два изображения в соответствие. В случае TPS это энергия изгиба.

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

Результаты [ править ]

Распознавание цифр [ править ]

Авторы Серж Белонги и Джитендра Малик протестировали свой подход на базе данных MNIST . На данный момент на базе проверено более 50 алгоритмов. В базе данных имеется обучающий набор из 60 000 примеров и тестовый набор из 10 000 примеров. Частота ошибок для этого подхода составила 0,63% при использовании 20 000 обучающих примеров и 3-NN. На момент публикации этот уровень ошибок был самым низким. В настоящее время самый низкий уровень ошибок составляет 0,18%. ^[10]

сходству по силуэтов Поиск

Авторы экспериментировали с базой данных силуэтов форм MPEG-7, выполняя основной эксперимент CE-Shape-1 часть B, который измеряет производительность поиска на основе сходства. ^[11]База данных содержит 70 категорий фигур и 20 изображений в каждой категории фигур. Производительность схемы поиска проверяется путем использования каждого изображения в качестве запроса и подсчета количества правильных изображений в 40 лучших совпадениях. Для этого эксперимента авторы увеличили количество точек, выбранных из каждой формы. Кроме того, поскольку фигуры в базе данных иногда поворачивались или переворачивались, авторы определили расстояние между эталонной фигурой и фигурой запроса как минимальное расстояние между фигурой запроса и неизмененной ссылкой, вертикально перевернутой или горизонтальной ссылкой. перевернул. ^[1]^[2]^[3]^[4] Благодаря этим изменениям они получили коэффициент возврата 76,45%, который в 2002 году был лучшим.

Распознавание 3D-объектов [ править ]

Следующий эксперимент, проведенный с контекстами форм, включал 20 распространенных предметов домашнего обихода из библиотеки изображений объектов Колумбии (COIL-20) . Каждый объект имеет 72 представления в базе данных. В эксперименте метод обучался на нескольких равноотстоящих видах для каждого объекта, а оставшиеся виды использовались для тестирования. Был использован классификатор 1-NN. Авторы также разработали алгоритм редактирования , основанный на сходстве контекста формы и кластеризации k-медоидов , что улучшило их производительность. ^[4]

Поиск товарного знака [ править ]

Контексты фигур использовались для извлечения товарных знаков из базы данных, наиболее совпадающих с товарным знаком, заданным в запросе (полезно при обнаружении нарушений прав на товарный знак). Алгоритм не пропустил ни одного визуально похожего товарного знака (проверено авторами вручную). ^[2]

Внешние ссылки [ править ]

Ссылки [ править ]

^ Перейти обратно: ^а ^б ^с ^д ^Это С. Белонги и Дж. Малик (2000). «Соответствие контекстам формы». Семинар IEEE по контентному доступу к библиотекам изображений и видео (CBAIVL-2000) . дои : 10.1109/ИВЛ.2000.853834 .
^ Перейти обратно: ^а ^б ^с ^д С. Белонги; Дж. Малик и Дж. Пузича (апрель 2002 г.). «Сопоставление фигур и распознавание объектов с использованием контекстов фигур» (PDF) . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 24 (4): 509–521. дои : 10.1109/34.993558 . S2CID 129468 .
^ Перейти обратно: ^а ^б С. Белонги; Дж. Малик и Дж. Пузича (июль 2001 г.). «Сопоставление фигур» (PDF) . Восьмая международная конференция IEEE по компьютерному зрению (июль 2001 г.) .
^ Перейти обратно: ^а ^б ^с ^д С. Белонги; Дж. Малик и Дж. Пузича (2000). «Контекст формы: новый дескриптор для сопоставления форм и распознавания объектов» (PDF) . НИПС 2000 .
^ Х. Чуи и А. Рангараджан (июнь 2000 г.). «Новый алгоритм нежесткого сопоставления точек». ЦВПР . Том. 2. С. 44–51. дои : 10.1109/CVPR.2000.854733 .
^ Р. Джонкер и А. Волгенант (1987). «Алгоритм кратчайшего увеличивающего пути для плотных и разреженных задач линейного назначения». Вычисление . 38 (4): 325–340. дои : 10.1007/BF02278710 . S2CID 7806079 .
^ MJD Пауэлл (1995). «Метод тонких пластинчатых сплайнов для преобразования кривых в кривые в двух измерениях». Вычислительные методы и приложения (CTAC '95) . дои : 10.1142/9789814530651 .
^ Ж. Дюшон (1977). «Сплайны, минимизирующие инвариантные к вращению полунормы в пространствах Соболева». Конструктивная теория функций многих переменных . Конспект лекций по математике. Том. 571. С. 85–100. дои : 10.1007/BFb0086566 . ISBN 978-3-540-08069-5 .
^ Г. Вахба (1990). Сплайновые модели для данных наблюдений . Соц. Промышленная и прикладная математика. ISBN 9780898712445 .
^ Ковсари, Камран; Хейдарисафа, Моджтаба; Браун, Дональд Э.; Мейманди, Киана Джафари; Барнс, Лаура Э. (3 мая 2018 г.). «RMDL: случайное многомодельное глубокое обучение для классификации». Материалы 2-й Международной конференции по информационным системам и интеллектуальному анализу данных . стр. 19–28. arXiv : 1805.01890 . Бибкод : 2018arXiv180501890K . дои : 10.1145/3206098.3206111 . ISBN 9781450363549 . S2CID 19208611 .
^ С. Жаннен и М. Бобер (март 1999 г.). «Описание основных экспериментов по движению/форме MPEG-7. Технический отчет ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690, MPEG-7, Сеул». {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[shape_1-1] Перейти обратно: ^а ^б ^с ^д ^Это С. Белонги и Дж. Малик (2000). «Соответствие контекстам формы». Семинар IEEE по контентному доступу к библиотекам изображений и видео (CBAIVL-2000) . дои : 10.1109/ИВЛ.2000.853834 .

[shape_2-2] Перейти обратно: ^а ^б ^с ^д С. Белонги; Дж. Малик и Дж. Пузича (апрель 2002 г.). «Сопоставление фигур и распознавание объектов с использованием контекстов фигур» (PDF) . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 24 (4): 509–521. дои : 10.1109/34.993558 . S2CID 129468 .

[shape_3-3] Перейти обратно: ^а ^б С. Белонги; Дж. Малик и Дж. Пузича (июль 2001 г.). «Сопоставление фигур» (PDF) . Восьмая международная конференция IEEE по компьютерному зрению (июль 2001 г.) .

[shape_4-4] Перейти обратно: ^а ^б ^с ^д С. Белонги; Дж. Малик и Дж. Пузича (2000). «Контекст формы: новый дескриптор для сопоставления форм и распознавания объектов» (PDF) . НИПС 2000 .

[5] Х. Чуи и А. Рангараджан (июнь 2000 г.). «Новый алгоритм нежесткого сопоставления точек». ЦВПР . Том. 2. С. 44–51. дои : 10.1109/CVPR.2000.854733 .

[6] Р. Джонкер и А. Волгенант (1987). «Алгоритм кратчайшего увеличивающего пути для плотных и разреженных задач линейного назначения». Вычисление . 38 (4): 325–340. дои : 10.1007/BF02278710 . S2CID 7806079 .

[7] MJD Пауэлл (1995). «Метод тонких пластинчатых сплайнов для преобразования кривых в кривые в двух измерениях». Вычислительные методы и приложения (CTAC '95) . дои : 10.1142/9789814530651 .

[8] Ж. Дюшон (1977). «Сплайны, минимизирующие инвариантные к вращению полунормы в пространствах Соболева». Конструктивная теория функций многих переменных . Конспект лекций по математике. Том. 571. С. 85–100. дои : 10.1007/BFb0086566 . ISBN 978-3-540-08069-5 .

[9] Г. Вахба (1990). Сплайновые модели для данных наблюдений . Соц. Промышленная и прикладная математика. ISBN 9780898712445 .

[Kowsari2018-10] Ковсари, Камран; Хейдарисафа, Моджтаба; Браун, Дональд Э.; Мейманди, Киана Джафари; Барнс, Лаура Э. (3 мая 2018 г.). «RMDL: случайное многомодельное глубокое обучение для классификации». Материалы 2-й Международной конференции по информационным системам и интеллектуальному анализу данных . стр. 19–28. arXiv : 1805.01890 . Бибкод : 2018arXiv180501890K . дои : 10.1145/3206098.3206111 . ISBN 9781450363549 . S2CID 19208611 .

[11] С. Жаннен и М. Бобер (март 1999 г.). «Описание основных экспериментов по движению/форме MPEG-7. Технический отчет ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690, MPEG-7, Сеул». {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]