Быстрый способ построения моментных инвариантов на изображении с использованием аппроксимации

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

M - 1 N - 1

M ks = ЕЕ m k n^sx ( m , n ) k , s = 0,1,- (1) m = 0 n = 0

Здесь x ( m , n ) - матрица, отсчетами которой являются яркости пикселей изображения; M х N -размеры изображения.

За последние сорок лет моментные инварианты, предложенные Ху, стали классическим инструментом распознавания образов. Приведенный им в [5] набор характеристик включает семь инвариантов:

^Ф 1 = ^М 20 + ^М 02 ,

^Ф 2 = ^{( м} 20 ^{- М} 02 ^{) 2} + ⁴ М п ,

^Ф 3 = ^{( м} 30 ^- 3 ^М 12 ^{) 2 +(} 3 ^М 21 ^{- М} 03 ^{) 2 ,}

ф 4 = (м30 + М12 ) +(м21 + М03 ) ,

^Ф 5 = ^{( м} 30

-

3 М 12 Х м з0 ⁺ М 12 ^)[( М з0 ⁺ М 12 ^{) 2 -} 3 ⁽ М 21 ⁺ М 03 ^{) 2 ] + (} 3 М 21

-(м21 + М03 )2

Ф 6 = (м20  М02 )[(м30 + М12 )   (м21 + М03 )]++4м11 (м30 + М12 )(М21 + М03 )■

^ф 7

= (3М21 - М03 )(М30 + М12 )[(м30 + М12 )2 - 3(м21 + М03 )2 ]- (м30 - 3М12 )(М21 + М03 )(3(м30 + М12 )2 - (м21 + М03 )2 ^}-

Основным отличием соотношений (2) является их инвариантность к повороту 2 - D объекта. С тех пор множество работ было посвящено обобщению и улучшению инвариантных признаков, предложенных Ху, а также попыткам применить их в приложениях из разных областей знаний. Например, в [2] и [1] было предложено использовать моментные инварианты для распознавания силуэтов самолетов на изображении, в [9] моментные инварианты применяются при сравнении с эталоном и совмещении снимков, полученных со спутника. Ряд авторов используют инварианты для распознавания символов. В [7] и [6] предложено использовать инварианты для изменений контраста, а в [8] для классификации текстур, в [3] описаны инварианты к линейным преобразованиям.

Много усилий исследователи прилагают для нахождения эффективных алгоритмов вычисления моментов. Возможность параллельно-рекурсивного вычисления локальных моментных характеристик для обработки изображений при использовании информационной технологии "скользящего окна" показана в монографии [10] (глава 8). Целью данной работы стала разработка быстрого способа вычисления моментных инвариантов, построенных на основе локальных характеристик, рассчитанных в “скользящем окне”.

• 2.    Построение моментных инвариантов в режиме “скользящего окна”

Во многих случаях использование моментов, вычисленных по всему изображению, является необязательным. Можно ограничиться “локальными” моментами, рассчитанными только на ограниченной области - по так называемому «скользящему окну» обработки (например, при обнаружении и распознавании объектов ограниченность области вытекает из конечности размеров объектов). Обычно окно задается прямоугольным и симметричным D : - M * <  m <  M * ; - N * <  n <  N * , где M * , N * - параметры, задающие границы окна по координатам. Тогда для каждой точки изображения с координатами ( m , n ) локальные моментные характеристики порядка ( k , s ) определяются выражением:

Mks(m,n)= Е Еmknsx(m -m1,n -n1), (3) (mj, n1) e D где x(m, n) - матрица, отсчетами которой являются яркости пикселей изображения; D - область, задающая окно обработки. Размеры окна выбираются, исходя из условий решаемой задачи.

Для такого окна можно применить параллельнорекурсивный алгоритм вычисления моментных характеристик [4], в соответствии с которым организуется покоординатная рекурсия с использованием моментов младших порядков, определенных для предыдущего положения окна:

k

P k ( n l, n Z ^{P (} n l -1^,,J + ( ^Mk xnn l ⁺ M 1, n 2 )

I = 0

-(M +1)kx( n - M -1 n2),

M kk n l , n j ) = Z C P ⁽ n l, n 2 ^-N^- M 2 ) s P ⁽ n l, n 2 ⁺ M 2 )

j = 0

• - M 2 ^{+ 1 )} s И к ⁽ n l, n 2 ^- M 2 ¹ ' ,

0 <  к <  K ,0 <  s <  K - к.                    (4)

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

• •    вычисление “скользящим окном” по изображению степенных моментов с применением параллельнорекурсивного алгоритма,

• •    пересчет инвариантов по известным формулам.

Общую сложность U такого алгоритма можно оценить как сумму двух слагаемых:

U = U P + U,(5)

где

UP = up + up, и ц = (K +1)( K + 3)( K + 8)

a                   6’ и = K (K + 2)( K + 7)

U m.

Здесь K - порядок моментов; U ¹ - оценка сложности расчета треугольной матрицы степенных моментов, необходимых для вычисления инвариантов;

UP - количество операций сложения на каждый отсчет обрабатываемого изображения [4]; Um -количество операций умножения на отсчет [4]; U1 - сложность собственно пересчета инварианта, она зависит от того, какой именно инвариант выбран.

• 3.    Вычисление моментных инвариантов через обобщенные моменты

Как было показано в работе [10], наиболее эффективным рекурсивным способом вычисляются обобщенные моменты с некоторым классом полиномиальных базисов:

H k _S ⁽ n 1 , n 2 ) = Z Z q k ^{( m}1 ) q_s ^{( m} 2 ) *

( ^m 1 . ^m 2 ) ' D                                   (6)

* x ( n 1 - m 1 , n ₂ - m ₂ ),

k где qk (m) = Zakim* - одномерный полином к -го i=0

порядка с коэффициентами { a_ki } ^k = ₀ ( a kk * 0); D -область, задающая окно обработки. Однако, несмотря на вычислительную эффективность, напрямую использовать обобщенные моменты для нахождения моментных инвариантов (2) нельзя. Возможный способ использования этих моментов состоит в том, чтобы сначала пересчитать по ним степенные моменты, а затем уже искать инварианты. Однако этот способ практически обесценивает выигрыш в вычислительных затратах, который имелся за счет использования обобщенных моментов.

В данной работе предлагается следующая процедура нахождения моментных инвариантов:

• •    расчет обобщенных моментов,

• •    вычисление инвариантов через обобщенные моменты.

Таким образом, сначала по изображению рассчитываются обобщенные моменты для полиномиального базиса (6), коэффициенты разложения которого по базису подбираются таким образом, чтобы вычислительная сложность алгоритма была минимальной [10]. При этом локальные обобщенные моменты порядка ( k, s ) для каждой точки изображения с координатами ( m, n ) рассчитываются по формулам:

P ₀ ( m , n ) = p ₀ ( m - 1, n ) + x ( m + M * , n ) - x ( m - M * - 1, n ),

P _k ( m , n ) = P _k ( m - 1, n ) + P _k - 1 ( m - 1, n ) + q_k ( - M * ) x ( m + M * , n ),  0 <  k <  K ;

P k 0 ( m , n ) = P k 0 ( m , n - 1 ) + Ц 0 ( m , n + N * ) - M 0 ( m , n - N * - 1 ),

Pks(m, n) = Pks(m, n -1) + Pk,s-1(m, n -1) + qs (-N *) Pk (m, n + N *),  0 < s < S, где x(m, n) - матрица, отсчетами которой являются яркости пикселей изображения; K, S - наибольшие порядки моментов соответственно по двум координатам; M* x N* - размеры «скользящего окна».

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

Будем использовать древовидную аппроксимацию, которая предполагает следующий порядок действий. В процессе предварительной обработки область значений используемых обобщенных моментов, представляющая собой многомерный ги- перкуб, последовательно разбивается по осям и порождает в памяти ЭВМ древовидную структуру. В каждой из областей, полученных в результате разбиения, осуществляется аппроксимация функции решений. В простейших вариантах древовидная аппроксимация может быть кусочно-постоянной и кусочно-линейной [11]. Области с малой ошибкой аппроксимации принимаются за терминальные вершины дерева. Те области, в которых ошибка велика, подвергаются дальнейшему разбиению.

Общая сложность U снова может быть оценена как сумма двух слагаемых:

U = U ^; + U a ,

где

U ^; = U ; + U ^ ,

u ; = 2 K + 2, U ; = K ,

U a = U kp or U ki ,

U kp = L + 1, U kl = 2 M + L .

Здесь K - порядок моментов; L - максимальная глубина построенного дерева (мы строим оценку «сверху»); M - количество обобщенных моментов, используемых при аппроксимации; U ^; - оценка сложности вычисления обобщенных моментов с полиномиальным базисом специального вида; U ; -количество операций сложения на каждый отсчет обрабатываемого изображения [10]; U ; - количество операций умножения на отсчет [10]; U ^ p - сложность кусочно-постоянной древовидной аппроксимации; U ; - сложность кусочно-линейной древовидной аппроксимации.

• 4.    Экспериментальное исследование

• 5.    Заключение

• 6.    Благодарность

  Работа выполнена при поддержке Министерства Образования РФ, Администрации Самарской области и Американского фонда гражданских исследований и развития (CRDF Project SA-014-02) в рамках российско-американской программы "Фундаментальные исследования и высшее образование" (BRHE), а также при поддержке Российского фонда фундаментальных исследований (РФФИ), проект № 04-01-96507.

Были проведены экспериментальные исследования погрешности полученных инвариантов в зависимости от сложности метода их аппроксимационного вычисления. В качестве моментных инвариантов использовались семь инвариантов Ху. Эксперименты проводились на тестовом изображении “Лена” размерами 256 x 256 пикселов. На рисунке 1 приведен график относительной погрешности кусочнопостоянной аппроксимации третьего моментного инварианта (2) в зависимости от сложности расчета инварианта (количества операций на отсчет).

Сложностъ, операций/пиксел

Рис.1. График зависимости относительной погрешности расчета инварианта от сложности вычисления.

Отдельной точкой показана сложность метода точного вычисления моментных инвариантов в режиме “скользящего окна” (5). Можно заметить, что с увеличением сложности точность аппроксимации инварианта приближается к этому значению. Однако зачастую изображения содержат некоторый уровень шумов, который делает бессмысленным вы- числение точных инвариантов. Поэтому можно воспользоваться предложенным методом, допустив наличие небольшой погрешности вычисления.

В работе рассмотрен аппроксимационный метод вычисления моментных инвариантов в “скользящем окне” по изображению. Указанный метод позволяет снизить затраты времени при вычислении инвариантов. Заметим, что необязательно аппроксимировать именно инварианты Ху. В общем случае можно брать достаточно общие интегральные характеристики, рассчитанные по изображению.