Адаптивная интерполяция на основе оптимизации решающего правила в многомерном признаковом пространстве

В настоящее время увеличение производительности вычислительных систем приводит к последовательному расширению области использования многомерных сигналов [1], примерами которых являются данные гиперспектральных сенсоров, видеопоследовательности, данные дистанционного зондирования Земли и т.д. Алгоритмы интерполяции многомерных сигналов можно, с незначительными оговорками, разделить на два класса [2]: неадаптивные и адаптивные. К наиболее распространённым неадаптивным алгоритмам можно отнести прямоугольную (несимметричную и симметричную) интерполяцию, а также билинейную и бикубическую интерполяцию. Эти алгоритмы имеют малую вычислительную сложность, но их точность невелика из-за отсутствия учёта локальных особенностей сигнала.

Класс адаптивных алгоритмов гораздо более обширен. Он включает, прежде всего, прямые обобщения на многомерный случай алгоритмов обработки двумерных сигналов, таких как контекстные алгоритмы вида NEDI [3–4] и DCCI [5], широкий спектр алгоритмов на основе нейронных сетей [6–7], а также многие другие алгоритмы [8–9]. Основным достоинством адаптивных алгоритмов является повышенная точность, за которую приходится расплачиваться существенным увеличением вычислительной сложности из-за усложнения интерполирующей функции и/или этапа настройки интерполяционной формулы.

В работах [10–11] предложен адаптивный интерполятор, автоматически переключающийся между несколькими простыми интерполирующими функциями. За счёт такого переключения этот интерполятор способен учитывать локальные особенности сигнала. Однако алгоритм оптимизации этого интерполятора существенным образом опирается на одномерность признакового пространства решающего правила, используемого для переключения между интерполирующими функциями, а также на специфику используемого признака. Кроме того, это решающее правило обеспечивает возможность переключения между всего двумя заранее заданными интерполирующими функциями специального вида.

В настоящей работе предлагается адаптивный алгоритм интерполяции, снимающий эти ограничения. Опишем структуру данной работы.

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

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

В третьем параграфе задача оптимизации решающего правила решается для случая многомерного признака за счёт использования дерева решений. Предлагается алгоритм, позволяющий производить разбиение вершин дерева решений с помощью упомянутого выше «одномерного» рекуррентного алгоритма.

В четвёртом параграфе предлагается модификация алгоритма оптимизации решающего правила для критерия минимизации энтропии квантованных постинтерполяционных остатков.

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

1.    Адаптивный интерполятор многомерного сигнала

Пусть x ( n ) - многомерный сигнал, а n - вектор его аргументов (все величины здесь и далее считаем целочисленными). Пусть задано несколько (немного) простых интерполирующих функций Ф У , с помощью которых можно вычислить соответствующее количество интерполирующих значений y i ( n ):

у / ( n ) = ^{ф y} ( ^Я ( n ) ) , i е [ 1, 1 ] , (1)

где i – номер интерполирующей функции, I задаёт количество интерполирующих функций, а ^Я ( n ) - это вектор, содержащий «опорные» отсчёты, на основе которых производится интерполяция отсчёта с координатами n :

Я ( n ) = { x ( Я + 0 ) : 0 е© } , (2)

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

В качестве простейших интерполирующих функций в этом случае можно использовать, например, усреднения по двум и четырём соседним отсчётам:

У 1 ( П 1 , n 2 ) = [ ( x ( П 1 , n 2 ) + x ( П 1 + 1, n 2 + 1 ))/ 2 ] ,        (4)

У 2 ( n 1 , n 2 ) = [ ( x ( n + 1, n 2 - 1 ) + x ( n - 1, n 2 + 1 ) )/2 ] , (5)

y ₃ ( n 1 , n ₂ ) = [ ( x ( n 1 , n ₂ ) + x ( n 1 + 1, n ₂ + 1 ) +

+ x ( n + 1, n ₂ - 1 ) + x ( n 1 - 1, n ₂ + 1 ) + 1)/4 ] .

Символ [...] здесь означает выделение целой части.

Пусть выбор интерполирующего значения в каждой точке сигнала выполняется посредством параметризованного решающего правила Ф ^r

У ( n , p ) = Уг ( n ) , ^г ( ^Я ) = ^{Ф r} ( f ( n ) , p ) , ⁽⁷⁾ где y ( n , p ) - это собственно результирующее интерполирующее значение (интерполирующий сигнал), p - вектор параметров решающего правила, f ( и ) -вектор локальных признаков в точке и . Таким образом, решающее правило Ф ^г в каждой точке сигнала «сравнивает» признак f ( и ) с векторным параметром p для вычисления номера интерполирующей функции г ( и ) в точке n .

Пусть локальный признак f ( n) вычисляется по тем же самых опорным отсчётам Я ( и )

f ( n ) = ^ф f ( ^Я ( n ) ) , ⁽⁸⁾

на основе которых происходит интерполяция (1).

Простейшими признаками в двумерном случае могут являться, например, диагональные разности, а также разности этих разностей вида f1 (n1,n2) = x(n1,n2)-x(n1 +1,n2 +1) , (9) f2 (n1,n2) = x(n1 +1,n2 -1)-x(n1 -1,n2 +1) , (10) f3 ( n1, n 2 ) = |fx ( n1, n 2 )|-| f, ( n1, n 2 )| . (11)

Вектор параметров решающего правила p подбирается для каждого сигнала отдельно на основе оптимизации некоторого критерия:

p = argn p i n s ( { x ( n ) } , { y ( n , p ‘ ) } ) , ⁽¹²⁾ где в качестве функции s может выступать некая мера близости (далее «погрешность») между исходным { x ( и )} и интерполирующим { y ( n , p ‘ )} сигналами.

Примерами такой функции являются [12] среднеквадратическое отклонение (СКО), сумма абсолютных значений постинтерполяционных остатков и т.д.

Во многих прикладных задачах интерполируемые значения известны, что позволяет вычислить эту погрешность непосредственно. Например, в некоторых методах [13–15] компрессии с ошибкой отсчёты сигнала интерполируются по отсчётам того же самого сигнала. Следовательно, на этапе компрессии погрешность можно вычислить (на этапе декомпрессии уже нельзя, так как исходный сигнал недоступен, а декомпрессированный сигнал искажён).

В других задачах, где интерполируемые значения недоступны, погрешность интерполяции часто можно оценить на основе дополнительной информации о сигнале, например, о его корреляционных свойствах. Для этого можно использовать подходы [16], которые применяются при оценке погрешности представления непрерывного сигнала дискретным.

Таким образом, будем далее предполагать, что погрешность интерполяции так или иначе возможно вычислить или оценить. Кроме того, следует отметить, что вместо (12) можно также использовать более специализированные критерии оптимизации, например, критерий минимума энтропии [13] квантованных постинтерполяционных остатков, наиболее подходящий для задачи компрессии сигналов, и предлагаемый в данной работе подход можно адаптировать также и для этого случая.

• 2.    Оптимизация решающего правила для случая одномерного признака и произвольного количества интерполирующих функций

Конкретизируем вид используемых решающих правил (7). Рассмотрим сначала случай, когда в каждой точке сигнала вычисляется одномерный (скалярный) признак f ( и ). Для простоты изложения (без ограничения общности) будем считать, что признак f ( и ) принимает значения в диапазоне [1, F ]. На практике этот диапазон обычно небольшой (сравним с диапазоном значений исходного сигнала).

Пусть в каждой точке сигнала решающее правило Ф r производит выбор из двух интерполирующих функций на основе сравнения признака f ( и ) с порогом t :

Ф r (f (n), p ) = Ф r (f (n), i <, i >, t ) = i <, f (и )< t, i >,f(n )> t,

где i < , i > - номера интерполирующих функций из множества всех доступных интерполирующих функций с номерами в диапазоне [1, I ] ( i <  - номер функции «слева от порога», i > - «справа от порога»). Таким образом, в ситуации одномерного признака вектор параметров p решающего правила Ф r ( f , p ) состоит из двух номеров интерполирующих функций i ^<, i ^> и порога t :

p = ( i < , i > , t ) .                                              (14)

Перед собственно интерполяцией для этого параметра должно быть найдено оптимальное по критерию (12) значение.

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

Алгоритм опирается на достаточно слабое требование существования способа вычисления погрешности s ({ x ( и )},{ у ( и , p )}) между сигналами в целом через погрешности e ( x ( и ), у ( и , p )) между отсчётами этих сигналов. Для простоты изложения под этим способом далее будем понимать суммирование:

• s ( { x ( и ) } , { у ( it,p ) } ) = £ e ( x ( и ) , у ( и , p ) ) . (15) ^г n

Нетрудно видеть, что это ограничение выполняется для большинства общеупотребимых видов погрешности, в частности для СКО и суммы абсолютных значений.

Введём в рассмотрение погрешность s < ( i , t ) интерполирующей функции номер i , вычисленную по отсчётам сигнала со значением признака, не превышающим порога t , а также аналогичную погрешность s > ( i , t ), вычисляемую по остальным отсчётам (погрешность «слева» от порога s < ( i , t ) и погрешность «справа» от порога s > ( i , t )):

• s < ( i , t ) = Z e ( x ( ” ) , y i ( и ) ) , i ^e[ 1, I ] , t ^e[ 1, F ] , (16) и : f ( и ) < t

s > ( i , t ) = Z e ( x ( и ) , y i ( и ) ) , i ^€[ 1’ I ] , t ^€[ 1’ F ] • (17) n: f ( n ) > t

Опишем предлагаемый алгоритм оптимизации решающего правила.

Этап 1. Заполнение матрицы погрешностей интерполяционных функций.

Перед собственно интерполяцией будем вычислять матрицу 5 ( i , f) размера I х F , содержащую погрешность интерполяционной функции номер i в точках сигнала со значением признака f ( и ), равным f' :

⁵ ( i , f ‘ ) =

= Z ^e ( ^{x ( Я )} , y i^{( Я )} ) ’ i ^G[ ^1, 1 ] ’ ^f '^ ^F ] .     ⁽¹⁸⁾

г f (Я) = f'

Этап 2. Рекуррентная схема поиска оптимального значения параметра.

Шаг 2a. Вычисление стартовых значений для запуска рекуррентной схемы.

Вычисляем значения погрешностей (16-17) интерполяционных функций при значении порога t = 1:

s < ( i ,1 ) = 0, i e [ 1, I ] ,                                      (19)

F s>(i,1) = Z5(i, f),i e[1,I].                         (20)

f = 1

Шаг 2b. Запуск рекуррентной схемы вычисления погрешности интерполяции.

Вычисляем значения погрешностей (16-17) интерполяционных функций при значениях порога t > 1 посредством рекуррентной схемы:

s < ( i , t ) = s < ( i , t - 1 ) + 5 ( i , t ) , i e [ 1, I ] , t e [ 2, F ] ,    (21)

s > ( i , t ) = s > ( i , t - 1 ) -5 ( i , t ) , i e [ 1, I ] , t e [ 2, F ] .     (22)

Шаг 2с. Определение наилучшей пары интерполирующих функций для каждого значения порога.

На основе значений погрешности определяем номера наилучших интерполирующих функций «слева» и «справа» от порога для каждого значения порога t :

i > ( t ) = argm in s > ( i , t ) , t e [ 1, F ] .                    (24)

Шаг 2d. Вычисление наименьшей возможной погрешности интерполяции для всех значений порога t :

s ( t ) = £ < ( i < ( t ) , t ) + ^s > ( i > ( t ) , t ) , t e [ 1, F ] .          (25)

Шаг 2e. Вычисление оптимального значения порога t , а также номеров i ^<, i ^> интерполирующих функций «слева» и «справа» от порога:

t = argmin e ( t ' ) , i < = i <  ( t ) , i > = i >  ( t ) .           (26)

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

u * ²⁾ = F ( 2 + 5 1 ) .

Далее эта оценка вычислительной сложности понадобится также для более общего случая, когда признак принимает значения в диапазоне [ F min , F max ):

u ^ ²⁾= ( F max - F n _ln )( 2 + 5 1 ) . (27)

3.    Оптимизация решающего правила для случая многомерного признака

Недостатком описанного выше «одномерного» алгоритма оптимизации является невозможность прямого обобщения на случай многомерного признака f (^Я). В данной работе предлагается алгоритм оптимизации решающего правила для случая многомерного признака, основанный на применении дерева решений [17].

При построении дерева решений происходит последовательное разбиение многомерного признакового пространства { f (Яг)}. Корневой узел дерева соответствует всему признаковому пространству целиком. Для этого узла выбирается оптимальная по погрешности вида (15) интерполирующая функция, а также вычисляется собственно погрешность интерполяции в узле.

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

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

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

[ ^Я, 7 ^я ] = [ (U ,1 ) ,..., ( F ,..., F m ) ] .

Пусть для каждого отсчёта сигнала решающее правило Ф ^r выбирает из двух интерполирующих функций на основании сравнения компоненты f m (^Я) признака f (^Я) с порогом t :

^Ф r ( ^f ( ^Я ) , p )

= Ф r

( f ( Я ) , m , i < , i > , t )

i <, fm (Я )< t, i > , fm ( Я )> t, где i <, i > – номера интерполирующих функций из набора всех доступных интерполирующих функций с номерами в диапазоне [1, I ]. Таким образом, при разбиении вершины дерева решений вектор параметров p решающего правила Фr (f, p) имеет вид p = (i <, i >, t, m), т.е. состоит из двух номеров интерполирующих функций i <, i >, порога t и номера компоненты признака m, по которой производится разбиение признакового пространства:

{ ^f ( ^Я ) } =

= { f ( Я ) : f ( Я ) < t } U { f ( Я ) : f ( Я ) > t } .

При разбиении узла для параметра p = ( i < , i > , t , m ) должно быть найдено оптимальное по критерию (12) значение. Для этого предлагается использовать алгоритм, описанный в предыдущем параграфе.

Этап 1. Заполнение массива погрешностей интерполяционных функций.

Будем вычислять трёхмерный массив 5 m ( i , f ' ) , содержащий погрешность интерполяционной функции номер i в точках сигнала со значением компоненты признака f_m , равной f' :

s m ( i , ^f ' ) = Е e ( x ^{( Я )} , y - -^{(Я )} ) ,

^Я : f m = f '                                           (29)

i е [ 1, I ] , m e [ 1, M ] , f' e [ 1, F ] .

Этап 2. Построение дерева решений.

Для каждой матрицы погрешностей 5m(i,fm) выполняется описанная в предыдущем параграфе одно- мерная «рекуррентная схема поиска оптимального значения параметра» (19–26) (см. «этап 2» в предыдущем параграфе). Наилучший по погрешности результат (и его номер m) задают искомый оптимальный параметр p = (i <, i >, t, m) при разбиении корневого узла.

На этом описание алгоритма разбиения корневого узла дерева завершено. Все остальные узлы разбиваются аналогичным образом, с учётом уменьшения области определения признака для каждого узла, которое задаётся выражением вида (28).

Вычислительная сложность предложенного алгоритма интерполяции в операциях на отсчёт может быть записана в виде:

U = Uy + Uf + Ue + U, + log2 N, где Nt – количество листьев дерева, log2Nt – вычислительная сложность выбора деревом, Uy, Uf, Ue, Ut – вычислительные сложности (в операциях на отсчёт) расчёта интерполирующих функций (1), признака f(Я), погрешности интерполяции (29) и построения дерева решений соответственно. Нетрудно видеть, что

U . <  N , Mu^ N = N , MF ( 2 + 5 1)/N x , (30)

где N x – количество отсчётов сигнала.

Табл. 1. Вычислительная сложность адаптивного интерполятора в зависимости от числа листьев дерева решений и количества отсчётов сигнала

Число листьев N t	Число отсчётов N x	Вычислит. сложность U
		2-D	3-D
10	10000	39	237
10	20000	35	167
10	100000	31	112
10	1 000000	30	100
100	10000	121	1484
100	20000	77	739
100	100000	42	240
100	1 000 000	35	115

Табл. 2. Вычислительная сложность NEDI в зависимости от количества отсчётов области оценивания

Размер области оценивания N s	Вычислительная сложность U n
	2-D	3-D
4	248	1168
16	728	2896
36	1528	5776
64	2648	9808
100	4088	14992
196	7928	28816
400	16088	58192
1024	41048	148048
1600	64072	230928

С учётом того, что согласно (27) каждое повтор- ное разбиение по одной и той же компоненте признака в среднем имеет примерно вдвое меньшую вычислительную сложность, последнюю оценку можно уточнить в сторону уменьшения:

min ( N_t ,2 M ) + log₂ ( max ( 1, N_t - 2 M ) )

U, « --------—Mu., tN                       a

x но в данной работе далее используется менее оптимистичная оценка (30).

Для дальнейшей конкретизации вычислительной сложности выберем пример реализации элементов алгоритма. В качестве интерполирующих функций (1) и признака f (^Я) рассмотрим D -мерные обобщения выражений (4–6) и (9–11) соответственно. В качестве погрешности интерполяции будем использовать квадратичную или абсолютную (модуль разности) ошибку (любая из них требует две операции на отсчёт). Тогда

I = 1 + 2 D ^{- 1}, F = 2 ( X _тах + 1 ) , U_£ = I ( M + 2 ) ,

U y = 2 D + 2 D ^{- 1} + 1, U f = 2 D ^{- 1} + 3 ■ 2 D ^{- 2} ( 2 D ^{- 1} - 1 ) .

Для сигнала с максимальным значением X max = 255 вычислительная сложность U адаптивного интерполятора (в операциях на отсчёт) показана в табл. 1. Для большинства практических ситуаций такая сложность приемлема. Кроме того, при увеличении размера сигнала сложность заметно уменьшается, так как сложность построения дерева решений, которое строится один раз для всего сигнала, оказывает меньшее влияние.

Для сравнения приведём вычислительную сложность U n адаптивного интерполятора NEDI [3–4] (в операциях на отсчёт), основанного на оптимизации интерполирующей функции по области оценивания размером в N s отсчётов (см. также табл. 2):

UK = 2NsNb (Nb +1) + (Nb )3 + (Nb )2 + 2N , где Nb – количество опорных отсчётов (далее равно 4 для двумерного сигнала и 8 для трёхмерного).

Из сравнения табл. 1 и 2 видно, что результаты близки только для коротких сигналов при минимальном размере области оценивания NEDI, при котором этот алгоритм обычно неустойчив. Во всех остальных ситуациях сложность предложенного адаптивного интерполятора заметно ниже, чем сложность NEDI.

Предложенный адаптивный алгоритм интерполяции может использоваться для интерполяции многомерных сигналов в задачах обработки видеопоследовательностей [18], данных гиперспектральных сенсоров [19], результатов дистанционного зондирования Земли [20] и т.п., в частности, в задачах компрессии [13–15] и совмещения разнородных сигналов [21].

4.    Оптимизация решающего правила по критерию минимума энтропии

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

В данной работе предлагается модификация описанного выше алгоритма, обеспечивающая возможность оптимизации решающего правила по критерию минимума энтропии квантованного разностного сигнала [14–16]. Эта модификация может использоваться, в частности, в дифференциальных, иерархических, интерполяционных и других методах компрессии сигналов, основанных на кодировании квантованного разностного сигнала.

Квантованный разностный сигнал

q ( Я , p ) = ^{ф q} ( x ( n ) - у ( n , p ) ) ^{-                  (31)}

это результат действия некоторой функции квантования Фq на разность между исходным x(Я) и интерполирующим у(n, p) сигналами. Пусть q (Я,p )e[i, Q ].

При компрессии хорошей оценкой объёма сжатых данных является ненормированная энтропия h ( Я , p ) сигнала q , которую необходимо минимизировать по параметру p решающего правила:

h(p) = -Z c(q',p)logc(q',pWmin,

1< q '< Qp где c(q', p) - это количество отсчётов квантованного разностного сигнала (31), равных q:

c (q\p ) = |{ n: q (Я, p ) = q '}|| •

Энтропия (32) не удовлетворяет ограничению (15). Опишем модификацию «одномерного» алгоритма оптимизации из параграфа 2 для критерия (32).

Введём в рассмотрение квантованный разностный сигнал для интерполяционной функции номер i q,-(n) = Фq (x(n)- y,(n)) ,(34)

а также количества отсчётов сигнала (34), равных q' , при значении скалярного признака f ( Я ), меньшем и большем порога t :

c< (i,q',t) = |{n : q,- (n) = q', f (n) < t}||, c> (i, q', t) = ||{n : q, (n) = q', f (n) > t}|| •(36)

Опишем модифицированный алгоритм оптимизации.

Этап 1. Заполнение трёхмерного массива, содержащего количество отсчётов сигнала (34), равных q' , при значении скалярного признака, равном f ' :

c ( , , q ' , f ' ) = |{ n : q , ( n ) = q ' , f ( n ) = f ' }|| •           (37)

Этап 2. Рекуррентная схема поиска оптимального значения параметра.

Шаг 2а. Указание начальных условий рекуррентной схемы вычисления значений (35–36):

c <( i, q ,1) = 0,(38)

c>(i, qл) = Z c(ii,q,f') •

1 < f '< F

Шаг 2b. Запуск рекуррентной схемы вычисления значений (35–36):

c< (i, q, t) = c< (i, q, t -1) + c(i, q, t), t e [2, F],(40)

c>(,',q,t) = c>(i,q,t-1)-c(,',q,t), t e[2,F].(41)

Шаг 2c. Вычисление количества отсчётов квантованного разностного сигнала (31), равных q , при условии использования пары интерполирующих функций с номерами i ^<, i ^> соответственно «слева» и «справа» от порога t :

c ⁺ ( i < , i > , q , t ) =

= c <  ( i < , q , t ) + c >  ( i > , q , t ) , t e [ 1, F ] .

Шаг 2d. Вычисление энтропии (32) при условии использования пары интерполирующих функций с номерами i <, i > соответственно «слева» и «справа» от порога t h (i <, i >, t) =

= - Z c ⁺( i < , i > , q , t ) log c ⁺( i < , i > , q , t ) .

1 < q '< Q

Шаг 2e. Поиск оптимальных значений параметров решающего правила в массиве значений энтропии:

i < , i > , t = arg min h ( i ' < , i ' > , t ' ) . (44) 1 < i < , i ' > < I ;1 < t '<, F ^v '

На этом описание модификации «одномерного» алгоритма оптимизации завершено. Этот алгоритм также может быть использован на каждом этапе «многомерного» алгоритма оптимизации на основе дерева решений, описанного в предыдущем параграфе.

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

Для исследования эффективности предложенного адаптивного интерполятора были проведены вычислительные эксперименты на реальных многомерных сигналах находящегося в открытом доступе гиперспектрального набора «TokyoTech» [22] (размер каждого сигнала 500 x 500 x 31). Примеры сечений тестовых сигналов показаны на рис. 1–2. Использовался алгоритм на основе оптимизации в многомерном признаковом пространстве, описанный в параграфах 2–3. Производилась интерполяция отсчётов с нечётными координатами по отсчётам с чётными координатами.

На рис. 3 в качестве иллюстративного примера приводятся погрешности при интерполяции одного двумерного сечения тестового сигнала функциями (4 – 6) и адаптивным интерполятором. Из рисунка видно, что интерполирующие функции ошибаются на диагональных контурах «неудобных» для них направлений, в то время как адаптивный интерполятор лучше срабатывает на всех диагональных контурах.

При экспериментах на гиперспектральных сигналах описанного набора «TokyoTech» в качестве меры эффективности использовалась оценка квадратичной погрешности s N между исходным x ( и ) и интерпо-лированым y ( n ) сигналом, нормированная на дисперсию сигнала D x и умноженная на 1000 для компактного представления в таблице результатов:

^s N ,

¹⁰⁰⁰         „       _^ ^2

—— Х( x ⁽ n ^{) -} y ⁽ n ) ) , N x D x n

где Nx – количество отсчётов сигнала, а Nt – ограни- чение на количество узлов дерева в эксперименте (вычислялись S20 и S200 для 10 и 100 узлов соответственно).

В качестве базы для сравнения использовался адаптивный алгоритм NEDI [3–4], погрешность вида (45) для которого обозначена S NEDI . Кроме самой погрешности, вычислялся также относительный выигрыш по погрешности адаптивного алгоритма у NEDI:

правила, оптимизированного в многомерном признаковом пространстве с помощью дерева решений.

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

(а)               (б)               (в)                 (г)

Рис. 3. Для сечения №10 сигнала «cd»

ошибки следующих интерполирующих функций:

(а) – усреднение по диагонали,

(б) – усреднение по другой диагонали,

(в) – усреднение по четырём диагональным соседям,

(г) – адаптивное переключение между (а ,б, в)

22 ^e NEDI ^e N

^ _N , = —2—- 100% . ^e NEDI

Тестовый набор интерполирующих функций включал усреднения по всем соседним опорным отсчётам, а также усреднения по диагоналям, аналогичные (4–6). В качестве признаков выступали разности по этим же диагоналям, аналогичные (9–11).

Полученные результаты (табл. 3) приведены для обработки блоками 100 x 100 x 31. Адаптивный алгоритм заметно выигрывает на большинстве сигналов (максимальный выигрыш – 40%, максимальный проигрыш – около 9%, средний выигрыш – 7% и 12% для различных параметров алгоритма).

Рис. 1. Тестовый многомерный сигнал «cloth5» (сечения № 0, 10, 20, 30)

Рис. 2. Тестовый многомерный сигнал «cd» (сечения № 0, 10, 20, 30)

Заключение

Предложен адаптивный интерполятор многомерного сигнала, выбирающий интерполирующую функцию в каждой точке сигнала посредством решающего

Табл. 3. Сравнение предложенного алгоритма интерполяции с алгоритмом NEDI

Сигнал	Погрешность s 2			Выигрыш
	2 s 10	2 s 100	2 s NEDI	Д 10	A 1go
Butterfly	2,87	3,07	3,15	2,7	8,8
Butterfly2	10,14	10,85	8,93	21,4	13,6
Butterfly5	2,43	2,57	2,67	3,9	9,1
Butterfly6	3,16	3,37	3,10	–8,6	–1,9
cd	1,64	1,84	1,81	–1,6	9,3
Character	7,12	7,28	7,48	2,6	4,8
ChartRes	29,87	30,59	39,21	22,0	23,8
Cloth3	25,08	26,94	41,86	35,6	40,1
Cloth4	12,26	12,75	18,88	32,5	35,1
Cloth5	5,92	6,14	9,25	33,7	36,0
color	2,31	2,33	2,48	6,2	6,8
doll	31,84	34,15	33,26	–2,7	4,3
fan2	8,57	8,79	9,42	6,7	9,1
fan3	10,16	10,70	9,11	17,6	11,6
flower	1,02	1,05	1,06	1,6	4,4
flower2	0,92	0,96	0,91	–5,8	–1,3
flower3	0,92	0,96	0,96	0,1	4,1
party	7,82	8,10	9,53	15,0	18,0
tape	6,61	6,79	7,84	13,4	15,8
tape2	4,75	4,65	8,00	41,9	40,6
Tshirts	42,58	45,22	48,02	5,8	11,3
Tshirts2	45,49	49,62	51,72	4,1	12,0
среднее	11,98	12,67	14,48	7,7	12,0

Вычислительный эксперимент, проведённый на реальных многомерных сигналах, подтвердил эффективность предложенного адаптивного интерполятора.

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 18-01-00667, также Министерства науки и высшего образования РФ в рамках Государственного задания ФНИЦ «Кристаллография и фотоника» РАН (соглашение № 007-ГЗ/Ч3363/26).