Описание картинки частотами «визуальных слов»

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

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

Каждый объект c номером  можно описать вектором признаков . Каждому объекту можно приписать метку класса . Множество известных наблюдений изображено на рисунке 2.5.

Рисунок Множество известных наблюдений

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

Функция  называется решающее правило или классификатор. Любое решающее правило делит пространство признаков на решающие регионы, разделенные решающими границами. На рисунке  изображена решающая граница.

Рисунок   Решающая граница

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

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

Найдём гиперплоскость, максимизирующую отступ между положительными и отрицательными примерами.

 положительные :

 (2.2)

 отрицательные  :

 (2.3)

Для опорных векторов:

 (2.4)

Расстояние от точки до гиперплоскости:

 (2.5)

Поэтому отступ равен:

 (2.6)

 

Отступ между положительными и отрицательными примерами приведен на рисунке 2.7.

Рисунок 2.7 – Отступ между положительными и отрицательными примерами

 

Максимизируем отступ по формуле (2.7).

Минимизируем  (2.7),

при условии .

Решается эта задача с помощью метода множителей Лагранжа (смотри формулу 2.8).

 (2.8)

Для большей части векторов вес равен 0. Все вектора, для которых вес больше 0, называются опорными. Вес определяется только опорными векторами (см. формулу (2.9)).

 (2.9)

Решающая функция:

 (2.10)

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

Так как у нас множество классов, используем многоклассовый SVM (Метод Опорных Векторов). На практике МОВ для нескольких классов получается путем комбинации нескольких двухклассовых МОВ. Например, обучением МОВ для каждого класса против всех остальных, применяя все МОВ к образцу, назначим класс, МОВ для которого выдал наиболее достоверное решение. Либо обучим МОВ для каждой пары классов: каждый МОВ голосует за классы, выбирается класс с наибольшим числом голосов.

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

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

В завершение обзора алгоритма «Bag of features» можно сказать, что метод имеет следующие особенности. К достоинствам модели можно отнести устойчивость её результатов при незначительных изменениях обучающей выборки. При этом усредняющая суть данного метода хорошо вписывается в подход с автоматически полученной обучающей выборкой. Среди недостатков стоит отметить принципиальную проблемность тех ситуаций, когда в анализируемом изображении представлено более одного экземпляра объекта из обучающей выборки или ситуацию, когда этот объект представлен частично. Также недостатком алгоритма является высокая вычислительная сложность на этапе обучения.