Классификация на основе сравнения с эталоном

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

В качестве эталонов могут рассматриваться следующие объекты:

В этих примерах признаки не выделены, но можно измерить сходство. Например, сравнение слов: кошка ~ мошка ~ кора ~ норка и.т.д. Или силуэт объекта в сцене, чье положение и ориентация заранее не известны (применительно к машинному зрению, робототехнике).

8.1. Мера близости, основанная на поиске оптимального пути на графе

Рассмотрим строчный образ (слово). В данном случае можно выделить два критерия, на основе которых можно строить меру близости:

Пусть $$\def\I{\mathop{I}} r_1r_2\ldots r_{\I\limits^{.}}$$ – эталон, $$\def\J{\mathop{J}} t_1t_2\ldots t_{\J\limits^{.}}$$ – пробный образ, причем $$\def\I{\mathop{I}} \def\J{\mathop{J}} \I\limits^{.}\neq\J\limits^{.}$$. Построим соответствие между эталоном и пробным образом по следующему правилу: каждому символу в первом слове должен соответствовать хотя бы один символ во втором слове и каждому символу во втором слове должен соответствовать хотя бы один символ в первом слове, (но соответствие между символами не взаимнооднозначное, в частности, поскольку $$\def\I{\mathop{I}} \def\J{\mathop{J}} \I\limits^{.}\neq\J\limits^{.}$$ ).

Введем меру следующим образом:$$\rho(r_i,t_i)= \left\{ \begin{aligned} 1,r_i\neq t_i \\ 0,r_i=t_i \end{aligned} \right.$$

В качестве меры сходства двух слов принимаем соответствие, при котором суммарный вес всех дуг (изображенных на рисунках) минимален:$$\nu(\overline{r},\overline{t})=\min_S\mu(S), \text{ где } \mu(S)=\sum_{(i,j)\in S} \rho(r_i,t_j).$$

Через $$\nu(\overline{r},\overline{t})$$ далее будем обозначать меру близости двух слов $$\overline{r}$$ и $$\overline{t}.$$

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

Определение. Редакторским расстоянием называется минимальное общее число изменений, вставок и потерь, требуемое для изменения образа $$A$$ в образ $$B$$:$$\def\I{\mathop{I}} D(A,B)=\min_j\left[C(j)+\I\limits^{.}(j)+R(j)\right],$$ где минимизация происходит по всем возможным комбинациям символьных преобразований таких, чтобы получить $$B$$ из $$A$$.

Пусть$$d(i,j|i-1,j-1)= \left\{ \begin{aligned} 1,\text{ при }t(i)=r(i) \\ 0,\text{ при }t(i)\neq r(i) \end{aligned} \right..$$ Тогда$$d(i,j|i-1,j)=d(i,j|i,j-1)=1.$$

Построим таблицу, в которой столбцы – это символы образа, строки – символы эталона. Количество точек в матрице есть $$\def\I{\mathop{I}} \def\J{\mathop{J}} \I\limits^{.}\cdot\J\limits^{.} $$.

По данной таблице построим граф по следующему правилу. Если отображается точка $$(r_2,t_1)$$, то далее выбираем $$(r_2,t_2)$$, $$(r_3,t_2)$$ или $$(r_3,t_1)$$ (т.е. возможны три варианта). Соответствие слов реализуется в виде маршрута в графе. Этот маршрут обязательно начинается с точки $$(r_1,t_1)$$ (иначе появится изолированная точка) и заканчивается в $$\def\I{\mathop{I}} \def\J{\mathop{J}} (r_{\I\limits^{.}},t_{\J\limits^{.}} $$.

	$$t_1$$	$$t_2$$	$$t_3$$	$$\ldots$$	$$\def\J{\mathop{J}} t_{\J\limits^{.}}$$
$$r_1$$	$$\circ$$	$$\circ$$	$$\circ$$	$$\ldots$$	$$\circ$$
$$r_2$$	$$\circ$$	$$\circ$$	$$\circ$$	$$\ldots$$	$$\circ$$
$$r_3$$	$$\circ$$	$$\circ$$	$$\circ$$	$$\ldots$$	$$\circ$$
$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\ddots$$	$$\vdots$$
$$\def\I{\mathop{I}} r_{\I\limits^{.}}$$	$$\circ$$	$$\circ$$	$$\circ$$	$$\ldots$$	$$\circ$$

Таким образом, получили задачу выбора кратчайшего пути на графе от точки $$(r_1,t_1)$$ до точки $$\def\I{\mathop{I}} \def\J{\mathop{J}} (r_{\I\limits^{.}},t_{\J\limits^{.}} $$, где каждая вершина имеет свою стоимость: 0 или 1.

8.2. Задача сравнения контуров

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

Каждой такой деформации припишем элементарную работу:

Задача состоит в поиске такого преобразования, чтобы затраченная работа была минимальной, т.е. надо найти$$f_{\Sigma}\rightarrow\min_S.$$

Эта задача сводится к установлению соответствия узлов одной ломаной узлам другой. При этом не требуется взаимно-однозначное соответствие, но требуется сохранение монотонности. Задача установления такого соответствия, которое минимизирует общую работу по деформации ломаных, также сводится к поиску минимального пути на графе такого же типа, как и рассмотренный в предыдущем пункте. В графе каждая дуга получает вес $$f(|l_1-l_2|)$$ – работу по сжатию или растяжению, а для каждой вершины – вес $$f(|\varphi_1-\varphi_2|)$$ – работу по изменению угла.

8.3. Задача сравнения речевых команд

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

Ядром IWR-систем является совокупность эталонов и мера. Отрезок сигнала (см. рис.) $$[0,T]$$ разбивается на сегменты, т.е. сигнал квантуется (с перекрытием). С каждым сегментом связывается вектор коэффициентов Фурье.

Обработка звука происходит в два этапа.

Первый этап. Строим цепочку $$r(i)$$, $$\def\I{\mathop{I}} i=1,\ldots,\I\limits^{.} $$ – разговорные сегменты. Далее строим преобразование Фурье с разбиением на $$t_f=512$$ отрезков. Обозначим через $$x_i(n)$$, $$n=0,\ldots,511$$ – отчеты для $$i$$ -ого сегмента, $$\def\I{\mathop{I}} i=1,\ldots,\I\limits^{.} $$. Тогда$$X_i(m)=\frac{1}{\sqrt{512}}\sum_{n=0}^{511}x_i(n)\cdot\exp\left(-j\frac{2\pi}{512}\right),\; m=0,\ldots,511.$$

Рассмотрим первые $$l,\;l\ll t_f$$ (пусть $$l\approx 50$$ ), коэффициентов Фурье в качестве вектора признаков:$$\def\I{\mathop{I}} r(i)= \left[ \begin{gathered} X_i(0) \\ X_i(1) \\ \vdots \\ X_i(l-1) \end{gathered} \right], \;l=1,\ldots,\I\limits^{.}$$

Второй этап. Определяем ограничения в графе соответствия сегментов эталонной и тестируемой команд.

Глобальные ограничения – ограничения поля для оптимального маршрута, например, $$|i-j|\leq k$$ (рис. слева).

Локальные ограничения – монотонность на сети маршрутов (рис. справа).

Ограничения конечной точки.

Стоимость $$d$$ – Евклидово расстояние между $$r(i_k),t(j_k)$$:$$d(i_k,j_k|i_{k-1},j_{k-1})=\|r(i_k)-t(j_k)\|=d(i_k,j_k).$$

Таким образом, и эта задача также сводится к поиску кратчайшего пути на графе.

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

Задача поиска кратчайшего пути на графе может быть решена методом динамического программирования. Пусть $$(i_0,j_0)$$ – начальный узел (отправной город), $$(i_f,j_f)$$ – конечный узел (город – пункт назначения). Тогда задача состоит в поиске оптимального маршрута через промежуточные узлы (города):$$(i_0,j_0)\xrightarrow{opt}(i_f,j_f)$$

Пусть $$(i,j)$$ – промежуточный узел. Тогда по принципу оптимальности Беллмана имеем$$(i_0,j_0)\xrightarrow{opt}(i_f,j_f)= \left((i_0,j_0)\xrightarrow{opt}(i,j)\right)\oplus \left((i,j)\xrightarrow{opt}(i_f,j_f)\right),$$ причем $$D_{\min}(i_k,j_k)=\min_{(i_{k-1},j_{k-1})} \left[ D_{\min}(i_{k-1},j_{k-1})+d(i_k,j_k|i_{k-1},j_{k-1}) \right]$$.