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

Shape context

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

Теория

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

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

Shapecontext.jpg

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

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

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

Использование в подборе формы

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

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

Детали реализации

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

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

Шаг 2: вычисление контекста формы

Этот шаг подробно описан в Теоретический раздел.

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

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

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

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

Теперь по каждой точке пя на первой фигуре и точке qj на второй фигуре рассчитайте стоимость, как описано, и назовите ее Cя,j. Это матрица затрат.

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

Результаты сопоставления

Теперь соответствие один-к-одному пя что соответствует каждой точке пя на форме 1 и qj на форме 2, что минимизирует общую стоимость сопоставления,

необходим. Это можно сделать в время, используя Венгерский метод, хотя есть более эффективные алгоритмы.[6]Чтобы иметь надежную обработку выбросов, можно добавить «фиктивные» узлы, которые имеют постоянную, но достаточно высокую стоимость сопоставления с матрицей затрат. Это заставит алгоритм сопоставления сопоставить выбросы с «фиктивным», если реального сопоставления нет.

Шаг 5: преобразование модели

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

Аффинный

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

Где с аналогичным выражением для . это псевдообратный из .

Тонкая шлицевая пластина

В тонкая шлицевая пластина (TPS) model - наиболее широко используемая модель для преобразований при работе с контекстами фигур. Двухмерное преобразование можно разделить на две функции TPS для моделирования преобразования координат:

где каждый из ƒИкс и ƒу имеют вид:

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

Регуляризованные TPS

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

куда энергия изгиба и называется параметром регуляризации. Этот ƒ что сводит к минимуму ЧАС[ƒ] можно найти довольно простым способом.[9] Если использовать нормализованные координаты для , то масштабная инвариантность сохраняется. Однако, если используются исходные ненормализованные координаты, необходимо нормализовать параметр регуляризации.

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

Шаг 6: Расчет расстояния формы

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

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

куда Т(·) - это оценочное преобразование TPS, которое отображает точки в 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-НН. Авторы также разработали редактирование алгоритм, основанный на подобии контекста формы и k-medoid кластеризация, улучшившая их производительность.[4]

Поиск торговой марки

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

внешняя ссылка

Рекомендации

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