З

Значение формы

Значение формы (англ. Shape context) — характеристика описания, используется в распознавании объектов. Срок было предложено Сержем Белонг и Джинтендра Маликом в их статье "Matching with Shape Contexts" (2000).

Теория

Характеристика предназначена для описания форм с целью измерения их сходства и восстановления точечных соответствий. Основной идеей является выбор n точек контура формы. Для каждой точки p i формы рассматриваются n — 1, векторов, полученных путем соединения точки p i со всеми другими точками. Множество всех этих векторов описанием локализованной формы локализованной в этой точке, но это описание слишком детализированным. Ключевая идея заключается в том, что распределение по относительной позиции является надежным, компактным и характерным идентификатором. Таким образом, для точки p i, грубая гистограмма относительных координат остальных n — 1 точек,

Значение формы

определяется как форма контекста. Столбики гистограммы (англ. — Bins) обычно принимают равномерными в полярных координатах. Подтверждение факта, что форма контекста характерно идентификатором, можно увидеть на рисунке ниже, где изображены формы контекстов двух различных вариантов написания буквы «А».

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

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

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

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

Завершена система, использующая значения формы для сопоставления, состоит из следующих шагов:

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

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

Шаг 1: Определение списка точек на краях формы

Этот подход предполагает, что форма объекта, по сути, определяется конечным подмножеством точек, принадлежащих внутренним или внешним контурам объекта. Множество этих точек может быть получена с помощью детектора краев Канне (англ. — Canny edge detector) и выбора случайного набора точек из этих краев. Обратите внимание, что эти точки не должны и в большинстве случаев не соответствуют ключевым точкам, таким как максимумы кривизны или точкам перегиба (англ. — Inflection points). Желательно выбирать формы с примерно равномерным интервалом, хотя это не критично.

Шаг 2: Вычисление значения формы

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

Шаг 3: Расчет матрицы стоимости

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

Значение формы

Это значение изменяется в диапазоне от 0 до 1. Кроме показателя стоимости значение формы, может быть использован показатель добавленной стоимости, основанной на внешнем виде. Например, это может быть мера непохожести тангенса угла (применяется при распознавании цифр)

Значение формы

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

Значение формы

Теперь для каждой точки p i первой формы и точки q j второй формы, нужно рассчитать общую стоимость, как описано выше, и обозначить это значение C i, j. Рассчитанные значения стоимости для всех точек формируют матрицу стоимостей.

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

Теперь нужно найти такое попарное сопоставление каждой точки p i первой формы, с точкой q j второй формы, минимизирует общую стоимость сравнения:

Значение формы

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

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

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

Аффинное преобразование

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

Значение формы

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

Шаг 6: Вычисление значения формы

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

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

Значение формы

где T () — это рассчитано преобразования, превращает точки формы Q в точки формы P.

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

Значение формы

Где изображение в градациях серого цвета (изображение после преобразования) и гауссовского функция.

Стоимость преобразования: Окончательная стоимость измеряет преобразования, нужны, чтобы выровнять два изображения.

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

Результаты

Распознавание цифр

Авторы Серж Белонг и Джинтендра Малик испытали подход на базе данных рукописных цифр. Более 50 алгоритмов было протестировано на этой базе данных. База содержит 60,000 учебных образцов и 10,000 тестовых образцов. Коэффициент ошибок для этого подхода составил 0.63% для использованных 20,000 учебных образцов. На данный момент, самый низкий уровень ошибок составляет 0.35%.

Поиск торговых марок

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

Изображения по теме

  • Значение формы
Показать больше

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

Добавить комментарий

Проверьте также
Закрыть
Кнопка «Наверх»
Закрыть
Закрыть