При обычном ортогональном разложении сигнала все отсчеты входят в преобразование с одинаковыми коэффициентами, т.е. все отсчеты равнозначны. Идеей предлагаемого метода является построение такого преобразования, в котором различные отсчеты входили бы с различными коэффициентами [1]. Наибольший вес должен быть у наиболее информативных участков сигнала, наименьший - у наименее информативных.

Зависимость величины вклада некоторого участка сигнала от информативности этого участка достигается тем, что каждый из коэффициентов разложения X_k находится путем минимизации не суммы квадратов отклонений отсчетов сигнала x_n и базисного вектора b_{k, n}, а путем минимизации суммы взвешенных квадратов отклонений - методом наименьших взвешенных квадратов (МНВК):

. (3)

Рис.1 иллюстрирует проекцию двумерного сигнала на базисный вектор при одинаковых и разных (w₀ < w₁) весах компонент x₁ и x₂.

Рис.1. Иллюстрация расстояния в МНК (пунктирная линия) и МНВК (сплошная линия).

Распишем метод наименьших взвешенных квадратов для суммы первых двух функций Хаара (Уолша). В данном случае будем минимизировать сумму взвешенных квадратов отклонений анализируемого сигнала и суммы базисных векторов, умноженных на коэффициенты разложения X₀ и X₁. Обозначим B_{0, n} = X₀ • |b_{0, n}| и B_{1, n} = X₁ • |b_{1, n}|.

. (4)

Продифференцируем левую часть выражения (4) по B_{0, n}:

, (5)

после раскрытия скобок имеем:

. (6)

Аналогично, продифференцировав левую часть выражения (4) по B_{1, n} после раскрытия скобок имеем:

. (7)

Из (6) и (7) видно, что коэффициенты X₀ и X₁ для МНВК (в отличие от МНК) независимы только в случае если:

. (8)

Т.е. в общем случае минимум СКО сигнала и каждого из векторов X_k • b_{k, n} по отдельности не соответствует минимуму СКО сигнала и суммы этих векторов. Этот вывод важен для понимания последующих рассуждений.

На рис 2 показан пример дискретного сигнала, его некоторой весовой функции w_n и его аппроксимации первыми двумя функциями Хаара (Уолша) умноженными на коэффициенты разложений по формулам (2) и (3).

Рис.2. График w_n (слева); график x_n (справа) и его разложение МНК (пунктирная линия) и последовательным МНВК (сплошная линия).

При разложении МНВК, перед нахождением X₁, из анализируемого сигнала вычитается X₀ • b_{k, n} (последовательная схема разложения). Очевидно, что при разложении в соответствии с (2) вычитание излишне. Здесь w_n = 1 при n = 1, 2, …, 8; w_n = 3 при n = 9, 10, …, 16.

Применение МНВК для описания областей изображения

Определим прямоугольную область изображения как двумерную функцию f_{m, n} пространственных координат m и n. Значение функции в каждой точке, задаваемой парой координат, соответствует интенсивности изображения в этой точке. В цифровом представлении координаты m и n принимают дискретные значения: m = 0, 1, …, H - 1, n = 0, 1, …, W - 1. W и H - ширина и высота области изображения в пикселях, соответственно.

Для функции изображения в некоторой точке (m, n) можно определить градиент как двумерный вектор-столбец. Компонентами этого вектора являются частные производные функции f_{m, n} по m и n. Значение вектора градиента в каждой точке можно представить в виде комплексного числа g_{m, n} = gn_{m, n} + j • gm_{m, n}. gm соответствует частной производной вдоль оси m, а gn - частной производной вдоль оси n. Таким образом, функции f_{m, n} соответствует комплексная функция g_{m, n}. Значение градиента в каждой точке можно также записать через его длину и угол (действительные функции двух переменных a_{m, n} и ц_{m, n}).

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

Рис 3. Область тестового изображения (слева), визуализация амплитуды градиента (справа).

Разделим комплексную функцию значений градиента изображения от координат на "сигнальную" составляющую, в качестве которой будем использовать ц_{m, n}, и "весовую" составляющую, в качестве которой будем использовать a_{m, n}. Идея анализа ориентаций градиентов для выделения дескрипторов областей изображений не нова, различные подходы описаны в работах [2, 5-8].

Теперь необходимо, во-первых, адаптировать МНВК для разложения аргумента градиента, т.е. для разложения сигнала с областью значений [ - р, р), а во-вторых, т.к. полутоновое изображение является двумерным сигналом, описанное выше преобразование обобщить на двумерный случай.

Попытаемся построить некоторое отображение функции g_{m, n}, компактно описывающее распределение ориентаций градиента в пределах исследуемой области изображения. При этом должна быть учтена и амплитуда градиента: подобласти с высоким значением амплитуды градиента должны вносить больший вклад, чем подобласти с малым значением.

Для начала рассмотрим одномерный сигнал x_n.

Будем искать выходной вектор искомого отображения в виде:

. (9)

Внесем несколько замечаний по поводу используемых в дальнейшем обозначений. Здесь и далее будем обозначать a_q = |x_q|, ц_q = arg (x_q), A_q = |X_q|, Ц_q = arg (X_q). Также будем считать каждое комплексное число x_q эквивалентным вектору:

. (10)

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

Рис 4. Графики первых 4-х функций Хаара (слева) и их двумерный вариант (справа).

Найдем Ц_k.

Для начала необходимо определение адекватной метрики для множества комплексных чисел с единичным модулем.

Воспользуемся представлением комплексных чисел в виде векторов в декартовой системе координат и определим расстояние между двумя числами, через скалярное произведение. Найдем такое значение угла вектора, при котором максимизируется среднее значение скалярных произведений анализируемых векторов и единичного вектора u:

. (11)

Приведем (11) к виду формулы (3):

, (12)

где: и = arg (u).

Тогда выражение для расстояния между двумя числами (метрики) запишется следующим образом:

. (13)

Для любого K ? N можно найти вектор

Ц^K = (Ц_{K - 1, 0}, Ц_{K - 1, 1}, …, Ц_{K - 1, K - 1}):

, (14)

где:

, (15)

где: haar - функция Хаара с множеством значений {0, 1, - 1}.

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

; (16)

. (17)

Из (14) нас в первую очередь будут интересовать Ц_{k, k}. Ц_{0, 0} может быть расписан следующим образом:

. (18)

Ц_{k, k}, k ? 0, запишется следующим образом:

. (19)

Найдем A_k.

Введем вектор

Ш^K = (Ш_{K - 1, 0}, Ш_{K - 1, 1}, …, Ш_{K - 1, K - 2}):

. (20)

Теперь определим A_k как:

. (21)

Из формулы (19) следует, что при расчете Ц_k сигнал может быть эквивалентным образом представлен двумя комплексными числами. Это также следует из области значений функций Хаара. Найдем для двух произвольных комплексных чисел коэффициенты Ц₀ и Ц₁. Изменим Ц₁ на бесконечно малую величину Дц и зафиксируем. Найдем новое значение для Ц₀ выполнением условия (14) при условии неизменности Ц₁. Тогда Дц_k = Дц_k⁺ + Дц_k^-. Зафиксируем Дц_k. Из (13) и (20) следует:

. (22)

Продифференцировав по Дц_k⁺ получим:

. (23)

Т.к. Дц_k бесконечно мало, то в пределе получим:

. (24)

Отсюда и из условия Дц_k = Дц_k⁺ + Дц_k ^- получаем выражения для Дц_k⁺ через Дц_k:

, (25)

аналогично для Дц_k ^- получим:

. (26)

Теперь подставим Дц_k⁺ и Дц_k ^- в левую часть (22) и продифференцируем по Дц_k. В пределе получим:

. (27)

Сравнивая (13), (21) и (27) получим выражение для A_k:

; (28)

. (29)

С учетом введенных выше обозначений предлагаемое преобразование можно записать следующим образом:

; (30)

. (31)

В качестве компонент искомого вектора признаков используются K низкочастотных коэффициентов описанного разложения. Т.е. каждому анализируемому изображению ставится в соответствие K-компонентный вектор признаков (X₁, X₂, …, X_K) или точка в K-мерном метрическом пространстве (пространстве признаков). Коэффициенты |X_k^q| перед расчетом Dможно нормировать.

. (32)

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

. (33)

Для устранения эффекта обнуления меры близости только за счет весов, в формулу (33) добавим "стабилизирующее" слагаемое:

. (34)

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

В дальнейшем будем называть описанное преобразование методом WLSF (Weighted Least Squares Features). В ряде задач требуется учитывать ориентацию градиента с точностью до р (т.е. не различать переходы от светлого к темному и от темного к светлому), для этого введем две модификации метода - WLSF_2р и WLSF_р. Разница между WLSF_2р и WLSF_рзаключается в следующем:

1. в WLSF_2р угол ориентирования квадратной окрестности анализируемой области может принимать значения в интервале [0, 2р), в WLSF_р - [0, р);

2. в WLSF_р нулевой коэффициент X₀ рассчитывается по следующей формуле:

. (35)

Экспериментальные исследования и сравнительный анализ