Методы генерации признаков

11.1. Генерация признаков на основе линейных преобразований

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

11.1.1. Базисные вектора

Пусть

Рассмотрим унитарную матрицу $$A_{N\times N}$$. Для действительной матрицы $$A_{N\times N}$$ условие унитарности обозначает, что матрица $$A_{N\times N}$$ ортогональная, т.е. $$A_{N\times N}^{-1}=A_{N\times N}^T$$. Для комплексной матрицы $$A_{N\times N}$$ условие унитарности обозначает, что $$A_{N\times N}^{-1}=A_{N\times N}^H$$, где матрица $$A_{N\times N}^H$$ - транспонированная (сопряженная).

Пусть$$y=A^H X= \left( \begin{gathered} a_0^H \\ a_1^H \\ \vdots \\ a_{N-1}^H \end{gathered} \right) \cdot X$$ где $$a_0^H,a_1^H,\ldots,a_{N-1}^H$$ – строки из транспонированных столбцов $$a_i$$ и $$A=(a_0,a_1,\ldots,a_{N-1})$$. Тогда$$x=(AA^{-1})x=(AA^H)x=AA^H x=Ay=\sum_{i=0}^{N-1}y(i)a_i.$$

Вектора $$a_i$$ называются базисными векторами. Таким образом, в силу ортогональности $$a_i$$ между собой, y(i) – это проекция вектора $$x$$ на базисные вектора.

11.1.2. Случай двумерных образов.

Пусть $$x(i,j),\;i,j=0,1,\ldots,N-1$$ – двумерные измерения. Очевидно, что представление его в виде вектора размерности $$N^2$$ неэффективно. Альтернативой является преобразование $$x$$ через базисные матрицы.

Пусть $$U_{N\times N}$$ и $$V_{N\times N}$$ – унитарные матрицы. Определим матрицу преобразования $$X$$ в $$Y$$:$$Y=U^HXV.$$

Учитывая, что $$\def\I{\mathop{I}} UU^H=\I\limits^{.}$$ и $$\def\I{\mathop{I}} VV^H=\I\limits^{.}$$, имеем$$X=UYV^H$$

Следовательно$$X=\sum_{i=0}^{N-1}\sum_{J=0}^{N-1}Y(i,j)\cdot u_i\cdot\nu_j^H$$

Пусть

Тогда$$A_{ij}=u_i\nu_j^H= \begin{pmatrix} u_{i,0}\nu_{j,0}^* u_{i,0}\nu_{j,1}^* \ldots u_{i,0}\nu_{j,N-1}^* \\ u_{i,1}\nu_{j,0}^* u_{i,1}\nu_{j,1}^* \ldots u_{i,1}\nu_{j,N-1}^* \\ \vdots \vdots \ddots \vdots \\ u_{i,N-1}\nu_{j,0}^* u_{i,N-1}\nu_{j,1}^* \ldots u_{i,N-1}\nu_{j,N-1}^* \end{pmatrix}.$$

Таким образом (11.1) есть выражение $$x$$ в терминах $$N^2$$ базисных матриц. Если $$Y$$ – диагональная, то (X=\sum_{i=0}^N-1) – это разложение по базисным матрицам или образам.

Также возможна следующая запись:$$Y(i,j)=X,\langle A_{ij}\rangle.$$

Тогда$$\langle A,B\rangle=\sum_{m=0}^{N-1}\sum_{n=0}^{N-1}A(m,n)\cdot B^*(m,n).$$

11.2. Преобразование Карунена-Лоева

Пусть $$x$$ – вектор измерений образа. Целью преобразования является построение такого вектора признаков, что$$E\left[y(i)y(j)\right]=0\text{ при } i\neq j.$$ т.е. чтобы признаки были взаимно некоррелированны.

Пусть

Будем считать, что$$y=A^T x$$

Обозначим $$R_y=E\left[yy^T\right]$$, тогда$$R_y=E\left[yy^T\right]=E\left[A^T xx^T A\right]=A^T R_x A,$$ где $$R_x$$ – симметричная матрица и ее собственные вектора ортогональны.

Выберем в качестве $$a_i$$ собственные вектора матрицы $$R_x$$. Тогда $$R_y$$ – диагональная матрица, у которой на диагонали стоят собственные значения $$R_x:\lambda_i,\; i=0,1,\ldots,N-1$$. Таким образом$$R_y=A^T\cdot R_x\cdot A= \Lambda.$$

Если $$R_x$$ положительно определенная матрица, то собственные значения $$\lambda_i>0,\;i=0,1,\ldots,N-1$$.

Описанное преобразование называется преобразованием Карунена-Лоева. Оно имеет фундаментальное значение, т.к. оно приводит к построению некоррелированных признаков.

11.2.1. Свойства преобразования Карунена-Лоева

Пусть $$x=Ay$$ или $$x=\sum_{i=0}^{N-1}y(i)a_i$$ – разложение по базисным векторам.

Определим новый $$m$$ -мерный вектор $$(m<N)$$:$$\widehat{x}=\sum_{i=0}^{m-1}y(i)a_i$$ где $$\widehat{x}$$ – проекция $$x$$ на подпространство. Если мы аппроксимируем $$x$$ с помощью $$\widehat{x}$$, то ошибка есть (выбираем те векторов, $$m$$ для которых ошибка минимальна):$$\begin{aligned} E\|x-\widehat{x}\|^2=E \left[ \left\| \sum_{i=0}^{N-1}y(i)a_i \right\|^2 \right] =E \left[ \sum_i\sum_j(y(i)a_i^T)(y(i)a_i) \right]=\\ =\sum_{i=m}^{N-1}E \left[ y^2(i) \right] =\sum_{i=m}^{N-1}a_i^T E \left[ xx^T \right] a_i=\sum_{i=m}^{N-1}a_i^T\lambda_i a_i =\sum_{i=m}^{N-1}\lambda_i. \end{aligned}$$

Тогда очевидно, что выбирать нужно $$m$$ базисных векторов с максимальными собственными значениями.

Отметим еще раз соотношение преобразования Карунена-Лоева с методом селекции признаков. В методе селекции признаков в качестве критерия выступали дискриминантные свойства полученного вектора признаков. В преобразовании Карунера-Лоева в качестве критерия выступает наилучшее приближение исходных измерений.

11.2.2. Применение преобразования Карунена-Лоева к задаче классификации. В данном случае основная концепция заключается в том, что подпространство главных собственных значений может быть использовано для классификации.

Алгоритм:

11.2.3. Декомпозиция сингулярных значений.

Пусть задана матрица $$A$$ ранга $$r$$. Покажем, что существуют такие унитарные матрицы $$U_{N\times N}$$ и $$V_{N\times N}$$, что$$X=U\cdot \begin{bmatrix} \Lambda^{\frac12}0\\ 00 \end{bmatrix} \cdot V^H,\; Y= \begin{bmatrix} \Lambda^{\frac12}0\\ 00 \end{bmatrix} =U^H\cdot X\cdot V,$$ где $$\Lambda_{r\times r}^{\frac12}$$ – диагональная матрица с элементами $$\sqrt{\lambda_i}$$ и $$\lambda_i$$ – $$r$$ ненулевых собственных значений матрицы $$X^H X$$. Иначе существуют такие унитарные матрицы $$U_{N\times N}$$ и $$V_{N\times N}$$, что преобразованная $$X$$ путем $$U^H XV$$ есть диагональная матрица. Следовательно$$X=\sum_{i=0}^{r-1}\sqrt{\lambda_i}\cdot u_i\cdot \nu_i^H$$ где $$u_i$$ и $$\nu_i$$ – первые $$r$$ столбцов матриц $$U_{N\times N}$$ и $$V_{N\times N}$$ соответственно, т.е. $$u_i$$ и $$\nu_i$$ – собственные вектора матриц $$XX^H$$ и $$X^HX$$ соответственно.

Собственные значения $$\lambda_i$$ называются сингулярными значениями матрицы $$X$$. Преобразование (11.2) – преобразование сингулярных значений или спектральное представление $$X$$.

Если $$X$$ аппроксимировать следующим образом$$\widehat{X}=\sum_{i=0}^{k-1}\sqrt{\lambda_i}\cdot u_i\cdot \nu_i^H, k\leq r-1,$$ то $$\widehat{X}$$ есть сумма $$k$$ одноранговых матриц и имеет ранг равный $$k$$. Можно показать, что квадратичная ошибка$$\varepsilon^2=\sum_{m=0}^{N-1}\sum_{n=0}^{N-1} \left| X(m,n)-\widehat{X}(m,n) \right|^2$$ является минимальной для всех $$k$$ -ранговых матриц. Ошибка аппроксимации есть$$\varepsilon^2=\sum_{i=k}^{r-1}\lambda_i,$$ следовательно, и в данном случае нужно выбирать максимальное $$\lambda_i$$.

Таким образом, $$\widehat{X}$$ есть наилучшая аппроксимация в смысле нормы Фробениуса. Данная аппроксимация напоминает преобразование Карунена-Лоева.

11.3. Дискретное преобразование Фурье (ДПФ)

Преобразования типа Карунена-Лоева есть результат специальной обработки (оптимизации) применительно к конкретной выборке требует больших вычислительных затрат. Если разложить по некоторому заданному базису, то можно снизить затраты, правда снизив требования к разложению.

11.3.1. Одномерное дискретное преобразование Фурье

Пусть $$x(0),x(1),\ldots,x(N-1)$$ – $$N$$ исходных измерений. Тогда ДПФ определяется следующим образом:$$y(k)=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}x(n)\exp \left( -j\frac{2\pi}{N}kn \right),$$ где $$k=0,1,\ldots,N-1$$ и $$\exp\{\alpha_j\}=\cos(\alpha)+j\sin(\alpha)$$.

Обратное преобразование есть:$$x(k)=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}y(n)\exp \left( j\frac{2\pi}{N}kn \right),$$ где $$n=0,1,\ldots,N-1$$

Определим$$W_N=\exp \left\{ -j\frac{2\pi}{N} \right\}.$$

Тогда$$\exp \left( -j\frac{2\pi}{N}kn \right)=W_N^{kn}.$$

Пусть $$y=W^Hx$$, тогда $$x=Wy$$,$$W^H=\frac{1}{\sqrt{N}}\cdot \begin{pmatrix} 11\ldots1\\ 1W_N\ldotsW_N^{N-1}\\ 1W_N^2\ldotsW_N^{2(N-1)}\\ \vdots\vdots\ddots\vdots\\ 1W_N^{N-1}\ldotsW_N^{(N-1)(N-1)} \end{pmatrix}.$$

Утверждается, что $$W$$ – унитарная симметрическая матрица. Пусть $$W^*$$ – сопряженная матрица: $$W^*=W^H=W^{-1}$$. Тогда базисные вектора – это столбцы матрицы $$W$$. Таким образом, имеет место разложение по заданному базису (по определению $$x=\sum_{i=0}^{N-1}y(i)a_i$$ – разложение по базисным векторам).

Прямое вычисление $$y=W^Hx$$ или $$x=Wy$$ имеет сложность $$O(N^2)$$, однако, специфика структуры матрицы $$W$$ позволяет строить алгоритмы сложности $$O(N\ln N)$$.

ДПФ можно рассматривать как разложение последовательности $$X(n)$$ в множество $$N$$ базисных последовательностей $$h_k(n)$$:$$X(n)=\sum_{k=0}^{N-1}y(k)h_k(n),$$ где$$h_k(n)= \left\{ \begin{aligned} \frac{1}{N}\exp \left\{ j\frac{2\pi}{N}kn \right\}, \text{ при }n=0,1,\ldots,N-1,\\ 0,\text{ иначе}. \end{aligned} \right.$$ $$y(k)$$ - коэффициенты разложения, а последовательности $$h(k)n$$ ортогональные:$$(h_k,h_l)=\delta_{kl}= \left\{ \begin{aligned} 1,\text{ при }k=l,\\ 0,\text{ иначе}. \end{aligned} \right.$$

11.3.2. Двумерные ДПФ

Пусть $$X(i,j),\;i,j=0,1,\ldots,N-1$$ – двумерные измерения. Тогда двумерное ДПФ есть:$$Y(k,l)=\frac{1}{N}\sum_{m=0}^{N-1}\sum_{n=0}^{N-1}X(m,n)W_N^{k\times m}W_N^{l\times n}.$$ Обратное преобразование:$$X(m,n)=\frac{1}{N}\sum_{k=0}^{N-1}\sum_{l=0}^{N-1}Y(k,l)W_N^{-k\times m}W_N^{-l\times n}.$$

Данную запись компактно можно переписать в следующем виде:$$Y=W^HXW^H,\; X+WYW.$$

Данное преобразование – это преобразование с базисными матрицами или образами $$w_iw_j^T,\;i,j=0,1,\ldots,N-1$$. Число требуемых операций "в лоб" равно $$O(N^3)$$. Учитывая специфическую структуру $$W$$, существуют методы сложности $$O(N^2\ln N)$$.

11.3.3. Дискретное косинусное преобразование (ДКП)

Данное преобразование имеет вид:$$y(k)=\alpha(k)\sum_{n=0}^{N-1}x(n)\cos \left( \frac{\pi(2n+1)k}{2N} \right), \;k=0,1,\ldots,N-1,$$ где$$x(n)=\sum_{k=0}^{N-1}\alpha(k)y(k)\cos \left( \frac{\pi(2n+1)k}{2N} \right), \;n=0,1,\ldots,N-1,$$ где $$\alpha(k)= \left\{ \begin{aligned} \sqrt{\frac1N},\text{ при }k=0,\\ \sqrt{\frac2N},\text{ иначе}. \end{aligned} \right$$.

Его можно переписать в векторной форме: $$y=C^Tx$$, где$$C(n,k)= \left\{ \begin{aligned} \sqrt{\frac1N},\text{ при }k=0,0\leq n\leq N-1,\\ \sqrt{\frac2N}\cos\left(\frac{\pi(2n+1)k}{2N}\right),\text{ при }k=1,2,\ldots,N-1,\;0\leq n\leq N-1. \end{aligned} \right.$$ и $$C$$ – действительная матрица, причем $$C^{-1}=C^T$$.

Двумерное ДПФ определяется так$$Y=C^TXC\text{ и }X=CYC^T.$$

11.3.4. Дискретное синусное преобразования (ДСП)

Данное преобразование вычисляется аналогично косинусному через матрицу:$$S(k,n)=\sqrt{\frac{2}{N-1}}\sin\left(\frac{\pi(k+1)(n+1)}{N+1}\right),\;k,n=0,1,\ldots,N-1.$$

Вычислительная сложность затрат на ДКП и ДСП есть $$O(N\ln N)$$.

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

11.4. Преобразования Адамара и Хаара

Преобразование Адамара и Хаара имеют такие же вычислительные достоинства, как и ДПФ, ДКП, ДСП. Их матрицы состоят из $$\pm 1$$, поэтому они вычисляются через сложения и вычитания без умножений.

11.4.1. Преобразование Адамара

Определение. Унитарная матрица Адамара порядка $$n$$ – это $$N\times N$$ матрица, где $$N=2^n$$, сгенерированная по следующему итерационному правилу$$H_n=H_1\oplus H_{n-1},$$ где$$H_1=\frac{1}{\sqrt{2}} \begin{pmatrix} 11\\ 1-1 \end{pmatrix}$$ и $$\oplus$$ обозначает кронекерово произведение двух матриц:$$A\oplus B= \begin{pmatrix} A(1,1)BA(1,2)B\ldotsA(1,N)B\\ A(2,1)BA(2,2)B\ldotsA(2,N)B\\ \vdots\vdots\ddots\ldots\\ A(N,1)BA(N,2)B\ldotsA(N,N)B \end{pmatrix}.$$

Распишем $$H_2$$:$$H_2=H_1\oplus H_1=\frac12 \begin{pmatrix} 1111\\ 1-11-1\\ 11-1-1\\ 1-1-11 \end{pmatrix}.$$

По аналогии можно выписать все $$H_n,\;n=1,2,\ldots$$. Нетрудно установить ортогональность $$H_n,\;n=1,2,\ldots$$:$$H_n^{-1}=H_n^T=H_n.$$

Для вектора $$x$$ из $$N$$ образцов пара преобразований есть: $$y=H_nx,\; x=H_ny$$

Преобразование Адамара имеет очень хорошие "упаковочные" свойства. Алгоритм для вычисления выделений и сложений достаточно быстрый: $$O(N-\ln N)$$.

11.4.2. Преобразование Хаара

Начальной точкой для определения преобразования Хаара являются функции Хаара, которые являются непрерывными и определенными на замкнутом сегменте $$[0,1]$$.

Порядок $$k$$ функций Хаара единственным образом раскладывается через два целых числа $$p$$ и $$q$$:$$k=2^p+q-1,\;k=0,1\ldots,L-1,\;L=2^n,$$

Определение. Функции Хаара:$$\begin{aligned} h_0(z)\equiv h_{00}(z)=\frac{1}{\sqrt{L}},\;z\in[0,1];\\ h_k(z)\equiv h_{pq}(z)=\frac{1}{\sqrt{L}}\cdot \left\{ \begin{aligned} 2^{\frac{p}{2}},\text{ при }\frac{q-1}{2^p}\leq z<\frac{q-0.5}{2^p},\\ -2^{\frac{p}{2}},\text{ при }\frac{q-0.5}{2^p}\leq z<\frac{q}{2^p},\\ 0,\text{ для остальных } z\in[0,1]. \end{aligned} \right. \end{aligned}$$

11.5. Генерация признаков на основе нелинейных преобразований. Выделение текстуры изображений.

Пусть дано изображение или его часть (область). Задача состоит в генерации признаков, которые впоследствии будут использоваться при классификации.

Определение. Цифровое изображение (монохромное) есть результат процесса дискретизации непрерывной функции $$I(x,y)$$ в виде двумерного массива $$I(m,n)$$, где $$m=0,1,\ldots,N_x-1$$, $$n=0,1,\ldots,N_Y-1$$. Значение функции $$I(x,y)$$ – интенсивность, число градаций $$N_g$$ – глубина изображения.

Определение. Генерацией признаков называется эффективное кодирование необходимой для классификации информации, содержащейся в оригинальных (исходных) данных.

11.5.1. Региональные признаки. Признаки для описания текстуры.

Дадим не точное определение текстуры.

Определение. Текстурой называется распределение оттенков серого цвета среди пикселов в регионе.

Рассмотрим основные типы характеристик:

Отметим, что в основе подхода лежит гипотеза о том, что внутри региона значения интенсивностей описываются одинаково, т.е. одним и тем же распределением вероятностей.

Пусть интенсивность внутри региона есть случайная величина. Тогда, при условии, что внутри региона характеристики одинаковы, данная случайная величина внутри региона одинаково распределенная, чем обеспечивается свойство однородности в регионе.

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

Данные признаки появляются при анализе пространственных соотношений по распределению серых цветов.

11.5.1.1. Признаки, основанные на статистиках первого порядка. Пусть $$I$$ – интенсивность случайной величины, представляющая собой значение (уровень интенсивности) серого цвета в регионе. Пусть также $$P(I=I-0)$$ – вероятность, того что интенсивность в регионе равна $$I_0$$.

Определение. Гистограммой первого порядка называется величина $$P(I)$$, равная отношению числа пикселов с уровнем интенсивности $$I_0$$ к общему числу пикселов в регионе и обозначается $$\def\I{\mathop{I}} P(\I\limits^{.})$$.

Рассмотрим центральный момент:$$\def\I{\mathop{I}} \mu_i=\sum_{\I\limits^{.}=0}^{N_g-1}(\I\limits^{.}-m_1)P(\I\limits^{.}),$$ где $$m_1$$ – среднее значение интенсивности – первый момент, который в общем случае определяется из формулы:$$\def\I{\mathop{I}} m_k=\sum_{\I\limits^{.}=0}^{N_g-1}I^k P(\I\limits^{.})$$ при $$k=1$$

Среди центральных моментов наиболее часто используются

В качестве признаков, основанных на статистиках первого порядка, также может использоваться абсолютный момент:$$\def\I{\mathop{I}} \widetilde{\mu}_i=\sum_{\I\limits^{.}=0}^{N_g-1}\left|\I\limits^{.}-m_1\right|\cdot P(\I\limits^{.})$$ и энтропия:$$\def\I{\mathop{I}} H=-E\left[\log_2 P(\I\limits^{.})\right] =-\sum_{\I\limits^{.}=0}^{N_g-1}P(\I\limits^{.})\log_2(P(\I\limits^{.})),$$ которая определяет меру равномерности распределения. Чем энтропия выше, тем распределение равномернее.

11.5.1.2. Признаки, основанные на статистиках второго порядка. Матрицы сочетаний. Пусть $$d$$ – относительное расстояние между пикселами, $$\varphi$$ – ориентация. Тогда можем ввести метрику следующим образом:$$\rho(p_1,p_2)=\max \left\{ |p_1x-p_2x|,|p_1y-p_2y| \right\},$$ причем пикселы рассматриваются в парах.

Рассмотрим соседство для четырех пикселей. Пусть $$\varphi=\left\{0^{\circ},45^{\circ},90^{\circ},135^{\circ}\right\}$$, т.е у нас имеется горизонтальное, вертикальное, диагональное и антидиагональное соседство.

Обозначим через $$\def\I{\mathop{I}} P_{\varphi} \left( \I\limits^{.}(m,n),\I\limits^{.}(m_1,n_1) \right) $$ совместную плоскость. Рассмотрим $$\varphi=0^{\circ}$$. $$\def\I{\mathop{I}} P_{\varphi} \left( \I\limits^{.}(m,n))=I_1,\I\limits^{.}(m\pm d,n)=I_2) \right) $$ – вероятность того, что точки, расположенная на горизонтали $$\rho=d$$ имеют интенсивности $$I_1$$ и $$I_2$$, равные отношению числа пар пикселов с расстоянием $$d$$ и значением $$I_1$$ и $$I_2$$ к общему числу пикселов в регионе.

Аналогично считается $$\def\I{\mathop{I}} P_{\varphi} \left( \I\limits^{.}(m,n)= I_1,\I\limits^{.}(m\pm d,n\mp d)=I_2) \right) $$ для $$\varphi=45^{\circ}$$ ; $$\def\I{\mathop{I}} P_{\varphi} \left( \I\limits^{.}(m,n)= I_1,\I\limits^{.}(m,n\mp d)=I_2) \right) $$ для $$\varphi=90^{\circ}$$ ; $$\def\I{\mathop{I}} P_{\varphi} \left( \I\limits^{.}(m,n)= I_1,\I\limits^{.}(m\pm d,n\pm d)=I_2) \right) $$ для $$\varphi=135^{\circ}$$. Каждый такой массив называют матрицей сочетаний или матрицей пространственной зависимости.

Рассмотрим конкретный пример матрицы $$\def\I{\mathop{I}} \I\limits^{.}$$. Пусть $$N_g=4$$, т.е. уровни интенсивности изменяются от 0 до 3. Пусть также матрица $$\def\I{\mathop{I}} \I\limits^{.}$$ задана следующим образом:$$\def\I{\mathop{I}} \I\limits^{.}= \begin{pmatrix} 0022\\ 1100\\ 3233\\ 3222 \end{pmatrix}.$$

Т.к. просмотр происходит в обе стороны, то общее количество пар равно 24.

Рассмотрим $$\varphi=0^{\circ}$$ и $$d=1$$. $$\def\I{\mathop{I}} 0\leq{\I\limits^{.}}_1,{\I\limits^{.}}_2\leq 3 $$. Очевидно, что матрица $$A$$ является симметрической.$$\def\I{\mathop{I}} A= \begin{pmatrix} P(0,0)P(0,1)\\ P(0,1)P({\I\limits^{.}}_1,{\I\limits^{.}}_2) \end{pmatrix} =\frac{1}{24} \begin{pmatrix} 4110\\ 1200\\ 1063\\ 0032 \end{pmatrix}$$

Для $$\varphi=45^{\circ}$$ и $$d=1$$ матрица $$A$$ выглядит следующим образом:$$A=\frac{1}{18} \begin{pmatrix} 0121\\ 1011\\ 2103\\ 1130 \end{pmatrix}$$

Существуют следующие основные виды признаков, основанные на статистиках второго порядка:

Угловой момент второго порядка: $$ASM=\sum_{i=0}^{N_g-1}\sum_{j=0}^{N_g-1}(P(i,j))^2 $$ – мера гладкости изображения. При малой вариации $$ASM\approx 1$$, а при больших вариациях (например при увеличении) контраста $$ASM\rightarrow 0$$.

Контраст (по заданной паре): $$CON=\sum_{n=0}^{N_g-1}n^2 \left\{ \sum_{i=0}^{N_g-1}\sum_{j=0}^{N_g-1}P(i,j) \right\} $$ – мера локальной дисперсии серого.

Момент обратной разности: $$IDF=\sum_{i=0}^{N_g-1}\sum_{j=0}^{N_g-1}\frac{P(i,j)}{1+(i-j)^2} $$. Момент обратной разности имеет большое значение для слабоконтрастных изображений.

Энтропия: $$H=\sum_{i=0}^{N_g-1}\sum_{j=0}^{N_g-1}P(i,j)\log_2 P(i,j) $$ – мера равномерности. Энтропия связана с фиксированной ориентацией и фиксированным расстоянием.

11.6. Признаки формы и размера

Рассмотрим методы генерации признаков, описывающих структуру. Существует два основных пути описания формы:

11.6.1. Признаки Фурье

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

Пусть $$x_k, y_k$$, где $$k=0,1,\ldots,N-1$$, – координаты последовательных точек границы; $$u_k=x_k+j*y_k$$ – комплексные числа. Для $$N$$ точек $$u_k$$ определим ДФП (DFT):$$f_l=\sum_{k=0}^{N-1}u_k\exp \left( -j\cdot\frac{2\pi}{N}\cdot l\cdot k \right), \;l=0,1,\cdot,N-1,$$

где $$f_l$$ – Фурье-описание границы.

Рассмотрим, как изменяется $$f_l$$ при сдвиге, повороте, масштабировании и сдвиге начальной точки.

Сдвиг описывается следующим образом: $$x'_k=x_k+\Delta x$$, $$y'_k=y_k+\Delta y$$ и $$u'_k=u_k+\Delta u$$. Тогда$$f'_l=f_l+\Delta u\delta(l),\text{ где }\delta= \left\{ \begin{aligned} 1,\text{ при }l=0\\ 0,\text{ при }l\neq 0 \end{aligned} \right. .$$

При $$l=0\quad f'_0\neq f_0$$, т.к.$$f'_0=f_0+\Delta u\delta(0)=f_0+\Delta u\neq f_0.$$

При $$l\neq 0\quad f'_l\neq f_l$$, т.к.$$f'_l=f_l+\Delta u\delta(l)=f_l+\Delta u\cdot 0 = f_l.$$

Поворот описывается следующим соотношением: $$u'_k=u_k\cdot\exp(j\theta)$$. Следовательно, $$f'_l=f_l\cdot\exp(j\theta)$$, т.е. поворот не меняет модулей, а именно $$|f'_l|=|f_l|$$.

Масштабирование описывается следующим соотношением: $$u'_k=a\cdot u_k$$. Следовательно, $$f'_l=a\cdot f_l$$. Т.к.$$\frac{f'_i}{f_i}=a\text{ и }\frac{f'_j}{f_j}=a,$$ то масштабирование не меняет соотношения$$\frac{f'_i}{f'_j}=\frac{f_i}{f_j}$$

Сдвиг начальной точки определяется следующим образом: $$u'_k=u_{k-k_0)$$. Следовательно$$f'_l=f_l\cdot\exp \left( -j\cdot\frac{2\pi}{N}\cdot k_0\cdot l \right),$$ т.е. сдвиг начальной точки сохраняет модули: $$|f'_l|=|f_l|$$.

11.6.2. Цепной код

Определение. Цепным кодом называется кодирование (запоминание) последовательности поворота вектора по пикселям на границе описываемой области – маршрута обхода.

Из построенного цепного кода конструируются следующие признаки:

Недостатком представления изображения цепным кодом является появления шума. Способом борьбы с данным недостатком является использование более мелкой (точной) сетки.

11.6.3. Геометрические свойства фигуры

Пусть $$P$$ – периметр фигуры, $$A$$ – площадь фигуры. Рассмотрим следующие свойства: некруглость фигуры и энергию изгиба.

11.6.3.1. Некруглость фигуры определяется по следующей формуле:$$r=\frac{P^2}{4\pi A}.$$

Рассмотрим два крайних значения для данного свойства. Наиболее лучшее (наибольшая "круглость") значение должно быть для круга, оно равно$$r=\frac{P^2}{4\pi A}=\frac{(2\pi R)^2}{4\pi\cdot\pi R^2}= \frac{4\pi^2 R^2}{4\pi^2 R^2}=1.$$

Более худший вариант (меньшая "круглость") наблюдается у квадрата. Соответствующее значение равно$$r=\frac{P^2}{4\pi A}=\frac{(4a)^2}{4\pi\cdot a^2}= \frac{16a^2}{4\pi a^2}=\frac{4}{\pi}.$$

11.6.3.2. Энергия изгиба. Пусть задано $$n$$ точек фигуры. Тогда Энергия изгиба описывается следующей формулой:$$E(n)=\frac{1}{P}\sum_{i=0}^n-1|k_i|^2,$$ где $$k_i=\theta_{i+1}-\theta_i$$ и $$\theta_i=\arctan\frac{y_{i+1}-y_i}{x_{i+1}-x_i}$$. $$k_i$$ характеризует изменение угла в вершине.

11.6.4. Скелетизация

Определение. Скелетизацией называется построение скелета, описывающего форму фигуры.

Определение. Скелетом называется множество всех центров вписанных в фигуру максимальных окружностей.

MAT (Medial Area Transform) определяется как скелет плюс функция ширины фигуры.