Оптимизация интерполятора многомерного сигнала в пространстве уменьшенной размерности

Оптимизация интерполятора многомерного сигнала в пространстве уменьшенной размерности

М.В. Гашников1,2

1 Самарский национальный исследовательский университет имени академика С.П. Королёва, 443086, Россия, Самарская область, Самара, Московское шоссе, д. 34;

2ИСОИ РАН - филиал ФНИЦ «Кристаллография и фотоника» РАН, 443001, Россия, Самарская область, Самара, ул. Молодогвардейская, д. 151

Аннотация

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

Ключевые слова: оптимизация, интерполяция, многомерный сигнал, уменьшение размерности, компрессия.

Цитирование: Гашников, М.В. Оптимизация интерполятора многомерного сигнала в пространстве уменьшенной размерности / М.В. Гашников // Компьютерная оптика. -2019. - Т. 43, № 4. - С. 653-660. - DOI: 10.18287/2412-6179-2019-43-4-653-660.

Введение

Объём обрабатываемых данных в настоящее время непрерывно увеличивается, зачастую растёт также и размерность этих данных, что естественным образом влечёт за собой необходимость решать различные задачи обработки многомерных сигналов [1].

Широко распространёнными примерами таких сигналов являются не только видео- [2], но также мульти- и гиперспектральные данные [3] (в том числе полученные в результате дистанционного зондирования Земли [4- 5]). Такие данные могут содержать десятки и сотни спектральных компонент, благодаря чему обладают многими свойствами, присущими многомерным сигналам и массивам данных.

Задача интерполяции многомерных сигналов характеризуется достаточно большим количеством подходов к её решению, известных в настоящее время. Наиболее перспективными из них являются подходы, основанные на использовании искусственных нейронных сетей [6 - 7]. Наряду с ними, также быстро развивается подход на основе «compressed sensing» [8].

Чаще всего при решении прикладных задач, связанных с интерполяцией многомерных сигналов, используются подходы на основе метода опорных векторов [9], сплайнов [10] и обобщений метода наименьших квадратов [11]. В качестве менее распространенных подходов заслуживают упоминания тензорные интерполяторы [12], а также методы на основе Кронекеровских базисов [13] и локально оптимальных хорошо приспособленных базисных функций [14].

Наиболее важным достоинством упомянутых подходов является высокая точность интерполяции, по-

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

В работах [16 - 17] предложен подход к построению адаптивных параметризованных интерполяторов. Адаптивность этих алгоритмов основана на автоматическом переключении между простыми интерполирующими функциями в каждой точке сигнала. При этом использование быстрых вычислительных процедур на каждом этапе влечёт за собой низкую сложность алгоритма интерполяции в целом.

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

Предложенные адаптивные интерполяторы многомерного сигнала могут использоваться при реше-

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

В данной работе рассматривается применение адаптивных интерполяторов в задаче компрессии. Производится исследование эффективности адаптивных интерполяторов в рамках метода компрессии на основе иерархической сеточной интерполяции на реальных многомерных сигналах различных типов.

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

Пусть х(п) - многомерный сигнал, а п - вектор его аргументов. Пусть отсчёт х(п) необходимо интерполировать на основе множества ближайших опорных отсчётов {х(п + т): т е ©} . Здесь смещение т задаёт расположение опорного отсчёта относительно интерполируемого отсчёта, а © - множество этих смещений.

Пусть для интерполяции отсчёта х(п) используется одна из простых интерполирующих функций У(,) ({х(п+)}: т е ©), / - номер интерполирующей функции. Обозначим и(,) (п) значения этих интерполирующих функций:

и(п ) = У({х (п + т) : т е ©}) .

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

и

где и (п, Т) - конкретное интерполирующее значение, выбранное в точке п , Т - вектор параметров, /(п) -

вектор локальных признаков, которые также вычисляются на основе опорных отсчётов {х(п + т): т е ©}.

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

ХЕ

пеО. '

где О - это множество всех возможных индексов (аргументов) исходного многомерного сигнала, а X (п, Т) -собственно постинтерполяционные остатки

X

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

Кроме приведённого критерия, можно также использовать критерий минимизации энтропии [18] постинтерполяционных остатков, наиболее адекватный задаче компрессии, так как энтропия является хорошей оценкой объёма сжатых данных.

При использовании такого «энтропийного» критерия следует учесть, что во многих методах компрессии, в частности дифференциальных [19] и иерархических [20 - 21], постинтерполяционные остатки перед статистическим кодированием квантуются. Для определённости в данной работе при квантовании используется алгоритм квантования с равномерной [18] шкалой:

д

. 2ешах +1

где ещах - вносимая при квантовании максимальная [15] погрешность (параметр квантователя), д (п, Т) -квантованные постинтерполяционные остатки, а оператор [..] производит выделение целой части числа.

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

е-1

Н (Т) = - X ^ (Т)1п Мд (Т) ^щп,

q=-Q+1 '

где Мд (') - количество квантованных постинтерполяционных остатков, имеющих значение д, а Q = шах(д(й, Т)) - максимальная величина постин-

п

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

2. Уменьшение размерности параметрического пространства

Для уменьшения вычислительной сложности при интерполяции часто используются алгоритмы [1,15], основанные на усреднении (сглаживании) по набору соседних опорных отсчётов:

и

те©

где мощность множества |©| фактически задаёт количество опорных отчётов (здесь и далее в целях упрощения изложения для величин и, д, I опускается зависимость от параметра Т ).

Область расположения этих опорных отсчётов определяется прикладной задачей, и в некоторых случаях, например при дифференциальной [19] и иерархической [20 - 21] компрессии, эта область может быть разрывна и иметь весьма нетривиальную форму (см. далее).

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

использующие интерполяцию «в направлении» этих границ, игнорирующие «мешающие» отсчёты, принадлежащие соседним плавно изменяющимся областям. Для 2D-сигнала так работает, например, интерполятор Грэхема [22] и его обобщения, например интерполятор, инвариантный к двумерным границам четырёх направлений [15]. Естественно, на плавно изменяющихся участках сигнала такие нелинейные алгоритмы работают менее точно.

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

Пусть Ыс - количество принимаемых во внимание направлений границ областей (оно часто не совпадает с количеством опорных отсчётов). Пусть {5(с-1 (п): 0 < с < Ыс} - множество абсолютных значений разностей

5

между опорными отсчётами х (п + §), х (п + т) в каждом из рассматриваемых направлений (с - номер возможного направления границы).

В качестве опорных отсчётов х (п +§), х (п + х) обычно используются отсчёты, расположенные близко к интерполируемому отсчёту х(п). Конкретная схема расположения опорных отсчётов зависит от прикладной задачи, в рамках которой используется интерполяция. В частности, при компрессии сигнала множество доступных опорных отсчётов определяется порядком обхода сигнала при обработке, который, в свою очередь, зависит от используемого метода компрессии. В следующих параграфах статьи схема расположения опорных отсчётов конкретизируется для интерполяторов в рамках иерархических методов компрессии [20 - 21].

Величины разностей 5(с) (п) характеризуют наличие и степень выраженности границы областей в локальной окрестности отсчёта п . Для определения наличия и направления этой границы нужно использовать как минимум Ыс штук параметров /(с), с которыми сравниваются разности 5(с). Если в окрестности отсчёта граница отсутствует, то все разности 5(с) имеют близкие значения и используется «сглаживающая» интерполирующая функция вида (6):

и

те

Если же в локальной окрестности отсчёта есть граница, то соответствующие ей разности 5(с) заметно отличаются от остальных, а для интерполяции ис-

пользуется усреднённое значение и(' -1 (п) ближайших опорных отсчётов, расположенных в направлении этой границы (/ - номер этого направления):

и

Таким образом, выражения (8, 9) задают значения интерполирующих функций и(')(п) адаптивного интерполятора вида (1), а параметры /(с), с которыми сравниваются разности 5(с), составляют вектор параметров Т решающего для правила этого интерполятора. Следовательно, для поиска наилучших значений параметров / (с) необходимо решать оптимизационную задачу вида (2) или (5) в Ыс-мерном пространстве параметров ( (с).

Размерность Ыс параметрического пространства определяется прикладной задачей и с увеличением размерности сигнала быстро растёт, так же как и вычислительная сложность оптимизации интерполятора, которая производится в этом пространстве параметров. При ограничениях, характерных, например, для многих приложений компрессии, вычислительная сложность может стать неприемлемой уже для случаев двух- или трёхмерного сигнала.

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

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

Построим вариационный ряд [22] разностей 5(с)(п) и перенумеруем разности внутри него:

5(0) (п) < 5(1) (п) <5(2) (п) <.. < 5(Ыс-1) (п).

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

При построении интерполятора используются предположения, что если в окрестности текущего отсчёта сигнала нет границы гладких областей сигнала (или эта граница слабо выражена), то значения всех разностей 5(с) примерно одинаковы. Если же в этой окрестности есть достаточно выраженная граница, то разность, соответствующая направлению этой границы, будет минимальна, т.е. попадёт на первую позицию вариационного ряда 5(0).

При этом примерно одинаковы будут все остальные разности, и 5(0) будет существенно отличаться от

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

/

которая в данной работе используется для определения наличия локальной границы и играет роль признака /(п) в правиле (1) выбора интерполирующей функции каждого отсчёта.

Если признак (10) достаточно мал (меньше порога г), то в окрестности текущего отсчёта границы нет, и используется «сглаживающая» интерполяция вида (8). В обратном случае производится интерполяция вида (9) «вдоль» направления, соответствующего минимальной из разностей 8(с):

и(1)(п) = £ х(п + т)/1©|, /(п) < г,

и(п) =

и{2)(п) = ии\п), у = а^тт{5(с)},

/ (п)>г.

Таким образом, размерность пространства параметров адаптивного интерполятора уменьшена до единицы: интерполятор (11), в отличие от схемы (8, 9), является однопараметрическим (с единственным скалярным параметром г), что существенно упрощает его оптимизацию.

3. Оптимизация адаптивного интерполятора

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

При минимизации показателя (2) используется вспомогательный двумерный массив Л, элементы которого вычисляются следующим образом:

Л,ф= |х(п) - и«(й)|,

п: / (я )=ф

I е {1,2}, фе[0.М -1],

М = тах^п)).

п

Элемент Л^ф этого массива содержит сумму модулей постинтерполяционных остатков интерполирующей функции и(,), заданной одним из выражений (11), для отсчётов со значением признака (10), равным ф.

На основе статистики (12) значение Хе (г) показателя (2) для всех значений порога г вычисляется рекуррентной процедурой:

хе(м ) = £л,„

/ =0

хе(/) = хе(/+1)+л2>,-лм, 0 <г <м.

Оптимальное значение параметра V = ^пгт Хе (),

которое можно найти перебором в коротком массиве Хе (г) длины (М +1), является решением оптимизационной задачи (2).

При минимизации энтропии (5) квантованных постинтерполяционных остатков (4) собирается трёхмерная статистика:

N% , I е{1,2}, 0 < / < М, - Q < д < 0, 0 = тах(д(й)).

Элемент ^^ содержит количество отсчётов квантованных постинтерполяционных остатков (4), имеющих значение д, при значении признака (10), равном / при использовании интерполирующей функции и (,), которая задаётся одним из выражений (11).

Статистика используется рекуррентной процедурой вычисления количества N. (г) значений квантованных постинтерполяционных остатков, равных д, при всех значениях параметра Л

М-1

^ (0 ) = ^ ,

/=0

N (+1) = N () - №д + N(д ,0 < г < м.

Статистика N. (г) даёт возможность вычислить энтропию Н(г) квантованных постинтерполяционных остатков при всех значениях порога г с помощью выражения (5). Индекс минимального значения

V = ^тт Н (г),

который можно найти перебором в коротком массиве Н (г) длины М, является решением оптимизационной задачи (5).

4. Адаптивная интерполяция при иерархической компрессии

В данной работе также рассматривается применение адаптивного интерполятора многомерных сигналов в задаче иерархической компрессии [20, 21], при решении которой используется безызбыточное представление (см. рис. 1, 2) исходного многомерного сигнала X = {х(п)} в виде иерархического набора из Ь масштабных уровней X/:

X = и X/ , X/ = { (п)} = {х(п): п е I,},

где множество I задаёт индексы отсчётов масштабного уровня X/:

1Ь-1 = { 2Ь-1 п} , I, = { 2'п} \{+1 п}, 0 < / < Ь .

Таким образом, наиболее прореженный масштабный уровень представляет собой исходный сигнал, прореженный с шагом 2(Ь1). Любой из остальных масштабных уровней номер 1= (Ь-1)..0 представляет

1 =0

собой прореженный с шагом 21 сигнал, из которого исключены отсчёты прореженного с шагом 2+1 сигнала.

Рис. 1. Иерархическое представление 2О-сигнала: четыре отсчёта самого прореженного уровня и пять отсчётов менее прореженного уровня

ЙЗ

9

-Й

т

щщъ

0

•а

да

б

1& :

« - - л —

.......... .............

Рис. 2. Иерархическое представление 3О-сигнала: восемь отсчётов самого прореженного уровня и 19 отсчётов менее прореженного уровня, разнесённые на три отдельных рисунка

Нетрудно видеть, что описанное иерархическое представление безызбыточно:

X р п X 2 = 0 Ур ф 2.

При иерархической компрессии масштабные уровни X/ обрабатываются последовательно, в порядке (Ь - 1), (Ь - 2)..2, 1, 0. Отсчёты каждого уровня интерполируются на основе отсчётов менее прореженных уровней, постинтерполяционные остатки квантуются и кодируются энтропийным кодером (см. рис. 3).

С

Исходный сигнал

Интерполяция Восстановление

Вычисление постинтерполяционных остатков

Квантование

Энтропийное кодирование

Архив

Рис. 3. Место интерполятора в структуре методов компрессии многомерных сигналов

Запишем в явном виде интерполирующие функции адаптивного интерполятора в трехмерном случае для отсчётов масштабного уровня X/ с координатами вида п = 2' (2т +1, 2п +1, 2к +1). При этом описанные

ранее величины и (,), 5 (с), и (]) вычисляются отдельно на каждом иерархическом уровне номер «'» и далее помечаются дополнительным нижним индексом «'».

Разности 5 (с) вида (7) в трёхмерном случае принимают вид:

5(с) (2т + 1,2п +1,2к + 1) =

с = а + 2Ь + 3ё; аЬё = 000,100,010,001,

где а = 1 - а обозначает логическое отрицание.

Значения интерполирующих функций (1) трёхмерного адаптивного интерполятора для отсчётов масштабного уровня X' могут быть записаны в виде:

и (2т +1,2п +1,2к +1) =

= £ £ £ х,(т + а, п + Ь, к + ё))8,

а=0,1 4=0,1 ё=0,1

и,(2) (п) = и(л (п), ] = arg пип {5(с) (п)},

где

и(с) (2т + 1,2п + 1,2к +1) =

= (х1+1 (т + а,п + Ь,к + ё) + х1(т + а,п + Ь,к + ё))), с = а + 2Ь + 3ё; аЬё = 000,100,010,001.

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

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

и(1) (2т +1,2п +1) = (х,+1 (т, п) + х,+1 (т +1, п) + + х,+1 (т, п +1) + х,+1 (т +1, п +1))/4,

и(2) (п) №>), 5(0) (п) < 5((1) (п), ' (п) К'Чп), 5(0)(п) > 5(1)(п),

где

,

(2т +1,2п +1) = = (х,(т + а, п + Ь ) + х1(т + а, п + Ь ))), (24) с = а + Ь; аЬ = 00,01. а 5(0)(п), 5((1)(п) - разности вида (7), которые могут быть записаны в виде:

5,с) (2т +1,2п +1) =

с = а + Ь; аЬ = 00,01.

Для выбора интерполирующей функции также используется решающее правило (11). Таким образом, двумерный адаптивный интерполятор, кроме «усредняющей» функции (22), использует также интерполирующие функции (23) «вдоль» двух направлений.

5. Экспериментальное исследование адаптивного интерполятора Для исследования эффективности адаптивного интерполятора в составе иерархического метода компрессии проведены вычислительные эксперименты на реальных многомерных сигналах двух типов:

а) сигналы гиперспектрометра AVIRIS [23] размера 1086x614x224 (16 бит);

б) гиперспектральный набор сигналов «ТокуоТесЬ» [24] размера 500x500x31 (13 бит). Также проведено сравнение адаптивного интерполятора с усредняющим интерполятором. В качестве меры эффективности адаптивного интерполятора ис-

а

0 10 50 100 150200 250 Рис. 4. Выигрыш адаптивного интерполятора на тестовом многомерном сигнале «Flower» гиперспектрального набора «TokyoTech»

4Д,%

а

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

Д=

где ка - коэффициенты компрессии при использовании усредняющего и адаптивного интерполятора.

Типичные примеры результатов вычислительных экспериментов, проведённых при различных значениях максимальной погрешности етах, показаны на рис. 4 - 7. Результаты подтверждают существенный (до 17 %) выигрыш адаптивного интерполятора.

а

0 10 50 100 150200 250 Рис. 5. Выигрыш адаптивного интерполятора на тестовом многомерном сигнале «Party» гиперспектрального набора «TokyoTech»

0 10 50 100 150 200 250 Рис. 6. Выигрыш адаптивного интерполятора на тестовом многомерном сигнале «Cuprite» гиперспектрометра AVIRIS

Заключение

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

Благодарности

Исследование выполнено при финансовой поддержке РФФИ в рамках научных проектов

.........&тах

0 10 50 100 150200 250 Рис. 7. Выигрыш адаптивного интерполятора на тестовом многомерном сигнале «Low Altitude» гиперспектрометра AVIRIS

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

Литература

1. Woods, J. Multidimensional signal, image, and video processing and coding / J. Woods. - 2nd ed. - Academic Press, 2011. - 616 p.

2. Tekalp, A.M. Digital video processing / A.M. Tekalp. - 2nd ed. - Prentice Hall, 2015. - 624 p. - ISBN: 978-0-13399100-0.

3. Chang, Ch.-I. Hyperspectral data processing: Algorithm design and analysis / Ch.-I. Chang. - Hoboken, NJ: A John Wiley & Sons, Inc., 2013. - 1164 p. - ISBN: 978-0-47169056-6.

4. Grahn, H. Techniques and applications of hyperspectral image analysis / H. Grahn, P. Geladi John / Wiley & Sons, 2007 - 399 p. - ISBN: 978-0-470-01087-7.

5. Lillesand, T. Remote sensing and image interpretation / T. Lillesand, R.W. Kiefer, J. Chipman. - 7th ed. - John Wiley & Sons, 2015. - 768 p.

6. Dong, C. Image super-resolution using deep convolutional networks / C. Dong, C.C. Loy, K. He, X. Tang // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2016. - Vol. 38, Issue 2. - P. 295-307. - DOI: 10.1109/TPAMI.2015.2439281.

7. Hu, H. Image interpolation using classification-based neural networks / H. Hu, P.M. Holman, G. de Haan // IEEE International Symposium on Consumer Electronics. - 2004. -P. 133-137. - DOI: 10.1109/ISCE.2004.1375920.

8. Eldar, Y.C. Compressed sensing: Theory and applications and signal processing / Y.C. Eldar, G. Kutyniok. - Cambridge University Press, 2012. - 558 p. - ISBN: 978-1-10700558-7.

9. Vapnik, V. Statistical learning theory / V. Vapnik. - John Wiley & Sons, 1998.

10. Хакимов, Б.В. Моделирование корреляционных зависимостей сплайнами на примерах в геологии и экологии / Б.В. Хакимов. - СПб.: Нева, 2003. - 144 с.

11. Cohen, A. On the stability and accuracy of least squares approximations / A. Cohen, M.A. Davenport, D. Leviatan // Journal of Computational Mathematic. - 2013. - Vol. 13. -P. 819-834.

12. Баллани, Д. Многоуровневая тензорная аппроксимация PDE со случайными данными [Электронный ресурс] / Д. Баллани, Д. Кресснер, М.Д. Петерс. - 2016. - URL: http://poivs.tsput.ru/ru/Biblio/Publication/18899 (дата обращения 1.07.2019).

13. Caiafa, C.F. Computing sparse representations of multidimensional signals using kronecker bases / C.F. Caiafa, А. Cichocki // Neural Computation. - 2016. - Vol. 25, Issue 1. - P. 186-220.

14. Васин, Ю.Г. Хорошо приспособленные» базисы и задачи обработки экспериментальной информации: Учебное пособие // Ю.Г. Васин. - Горький: Горьк. гос. ун-т, 1979. - 129 с.

15. Методы компьютерной обработки изображений / М.В. Гашников, Н.И. Глумов, Н.Ю. Ильясова,

В.В. Мясников, С.Б. Попов, В.В. Сергеев, В.А. Сойфер,

A.Г. Храмов, А.В. Чернов, В.М. Чернов, М.А. Чичева,

B.А. Фурсов; под ред. В.А. Сойфера. - М.: Физматлит, 2003. - 784 с. - ISBN: 5-9221-0270-2.

16. Gashnikov, M.V. A differential image compression method using adaptive parameterized extrapolation / М^. Gashnikov // Optical Memory and Neural Networks. (Information Optics). - 2017. - Vol. 26, Issue 2. - P. 137144. - DOI: 10.3103/S1060992X17020023.

17. Максимов, А.И. Адаптивная интерполяция многомерных сигналов при дифференциальной компрессии / А.И. Максимов, М.В. Гашников, // Компьютерная оптика. - 2018. - Т. 42, № 4. - С. 679687. - DOI: 10.18287/2412-6179-2018-42-4-679-68.

18. Sayood, K Introduction to data compression / К. Sayood. -4th ed. - Waltham, MA: Morgan Kaufmann, 2012. - 768 p. - ISBN: 978-0-12-415796-5.

19. Salomon, D. Data compression. The complete reference / D. Salomon. - 4th ed - Springer-Verlag, 2007. - 1118 p.

20. Gashnikov, M. Compression method for real-time systems of remote sensing / M. Gashnikov, N. Glumov, V. Sergeyev // Proceedings of 15th International Conference on Pattern Recognition. - 2000. - Vol. 3. - P. 232-235. - DOI: 10.1109/ICPR.2000.903527.

21. Гашников, М.В. Бортовая обработка гиперспектральных данных в системах дистанционного зондирования Земли на основе иерархической компрессии / М.В. Гашников, Н.И. Глумов // Компьютерная оптика. - 2016. - Т. 40, № 4. - С. 543551. - DOI: 10.18287/2412-6179-2016-40-4-543-551.

22. Gonzalez, R.C. Digital image processing / R.C. Gonzalez, R.E. Woods. - 3th ed. - Upper Saddle River, NJ: Prentice Hall, 2007. - 976 p. - ISBN: 978-0-13-168728-8.

23. AVIRIS data - Ordering free AVIRIS standard data products [Electronical Resource]. - URL: http://aviris. jpl.nasa.gov/data/free_data.html

24. TokyoTech 31-band hyperspectral image dataset [Electronical Resource]. - URL: http://www.ok.sc.e.titech.ac.jp/res/MSI/MSIdata31.html (request date 19.03.2018).

Сведения об авторе

Гашников Михаил Валерьевич, 1975 года рождения, в 1998 году окончил Самарский государственный аэрокосмический университет имени академика С.П. Королёва (СГАУ), кандидат наук, доцент. В настоящее время работает доцентом кафедры геоинформатики и информационной безопасности Самарского национального исследовательского университета имени академика С.П. Королёва, а также по совместительству в Институте систем обработки изображений - филиале ФНИЦ «Кристаллография и фотоника» РАН.

Область научных интересов: обработка многомерных сигналов, компрессия сигналов, обработка космических снимков, геоинформационные технологии. Имеет более 90 публикаций, в том числе более 30 статей и две монографии (в соавторстве). E-mail: mgash@smr.ru .

ГРНТИ: 28.17.19, 28.21.15, 28.23.15 Поступила в редакцию 21 марта 2019 г. Окончательный вариант - 14 мая 2019 г.

Optimization of the multidimensional signal interpolator in a lower dimensional space

M.V. Gashnikov1'2

1Samara National Research University, Moskovskoye Shosse 34, 443086, Samara, Russia; 2IPSIRAS - Branch of the FSRC "Crystallography and Photonics" RAS, Molodogvardeyskaya 151, 443001, Samara, Russia

Abstract

Adaptive multidimensional signal interpolators are developed. These interpolators take into account the presence and direction of boundaries of flat signal regions in each local neighborhood based on the automatic selection of the interpolating function for each signal sample. The selection

of the interpolating function is performed by a parameterized rule, which is optimized in a parametric lower dimensional space. The dimension reduction is performed using rank filtering of local differences in the neighborhood of each signal sample. The interpolating functions of adaptive interpolators are written for the multidimensional, three-dimensional and two-dimensional cases. The use of adaptive interpolators in the problem of compression of multidimensional signals is also considered. Results of an experimental study of adaptive interpolators for real multidimensional signals of various types are presented.

Keywords: optimization, interpolation, multidimensional signal, dimension reduction, compression.

Citation: Gashnikov MV. Optimization of the multidimensional signal interpolator in a lower dimensional space. Computer Optics 2019; 43(4): 653-660. DOI: 10.18287/2412-6179-2019-43-4653-660.

Acknowledsements: The work was funded by the Russian Foundation for Basic Research under RFBR grants ## 18-01-00667, 18-07-01312 and the RF Ministry of Science and Higher Education within the state project of FSRC "Crystallography and Photonics" RAS under agreement 007-GZ/Ch3363/26.

References

[1] Woods J. Multidimensional signal, image, and video processing and coding. 2nd ed. Academic Press; 2011.

[2] Tekalp AM. Digital video processing. 2nd ed. Prentice Hall; 2015. ISBN: 978-0-13-399100-0.

[3] Chang Ch-I. Hyperspectral data processing: Algorithm design and analysis. Hoboken, NJ: A John Wiley & Sons, Inc; 2013. ISBN: 978-0-471-69056-6.

[4] Grahn H, John PG. Techniques and applications of hyperspectral image analysis, Wiley & Sons; 2007. ISBN: 9780-470-01087-7.

[5] Lillesand T, Kiefer RW, Chipman J. Remote sensing and image interpretation. 7th ed. John Wiley & Sons; 2015.

[6] Dong C, Loy CC, He K, Tang X. Image super-resolution using deep convolutional networks. IEEE Transactions on Pattern Analysis and Machine Intelligence 2016: 38(2): 295-307. DOI: 10.1109/TPAMI.2015.2439281.

[7] Hu H, Holman PM, Haan G. Image interpolation using classification-based neural networks. IEEE International Symposium on Consumer Electronics 2004: 133-137. DOI: 10.1109/ISCE.2004

[8] Eldar YC, Kutyniok G. Compressed sensing: Theory and applications and signal processing. Cambridge University Press; 2012. ISBN: 978-1-107-00558-7.

[9] Vapnik V. Statistical learning theory, John Wiley & Sons; 1998.

[10] Hakimov BV. Spline modelling of correlation relations in geological and ecological examples [In Russian]. Saint-Petersburg: "Neva" Publisher; 2003.

[11] Cohen A, Davenport MA, Leviatan D. On the stability and accuracy of least squares approximations. J Comput Math 2013; 13: 819-834.

[12] Ballani J, Kressner D, Peters M. Multilevel tensor approximation of PDEs with random data. 2016. Source: (https://arxiv.org/abs/1606.05505).

[13] Caiafa CF, Cichocki A. Computing sparse representations of multidimensional signals using kronecker bases. Neural Computation 2016; 25(1): 186-220.

[14] Vasin YG. Well adapted bases and experimental data processing problems. Tutorial [In Russian]. Gorky: Gorky State University Publisher; 1979.

[15] Soifer VA, ed. Computer image processing, Part II: Methods and algorithms. M .: Fizmatlit; 2003. ISBN: 5-92210270-2 (in Russian).

[16] Gashnikov MV. A differential image compression method using adaptive parameterized extrapolation. Optical Memory and Neural Networks. (Information Optics). 2017; 26(2): 137-144. DOI: 10.3103/S1060992X17020023.

[17] Maksimov AI, Gashnikov MV. Adaptive interpolation of multidimensional signals for differential compression. Computer Optics 2018; 42(4): 679-687. DOI: 10.18287/2412-6179-2018-42-4-679-687.

[18] Sayood K. Introduction to data compression. 4th ed. Waltham, MA: Morgan Kaufmann; 2012. ISBN: 978-0-12-415796-5.

[19] Salomon D. Data compression. The complete reference. 4th ed. Springer-Verlag; 2007.

[20] Gashnikov M, Glumov N, Sergeyev V. Compression method for real-time systems of remote sensing. ICPR 2000; 3: 232-235. DOI: 10.1109/ICPR.2000.903527.

[21] Gashnikov MV, Glumov NI. Onboard processing of hy-perspectral data in the remote sensing systems based on hierarchical compression. Computer Optics 2016; 40(4): 543-551. DOI: 10.18287/2412-6179-2016-40-4-543-551.

[22] Gonzalez RC, Woods RE. Digital image processing. 3th ed. Upper Saddle River, NJ: Prentice Hall; 2007. ISBN: 978-013-168728-8.

[23] AVIRIS data - Ordering free AVIRIS standard data products. Jet Propulsion Laboratory. Source: (http://aviris.jpl.nasa.gov/data/free_data.html).

[24] TokyoTech 31-band hyperspectral image dataset. Source: (http://www.ok.sc.e.titech.ac.jp/res/MSI/MSIdata31.html).

Author's information

Mikhael Valeryevich Gashnikov (b. 1975) graduated from S.P. Korolyov Samara State Aerospace University (SSAU), PhD and associate professor. He is the associate professor at the Geoinformatics and Information Security department at Samara National Research University, as well as part-time at the IPSI RAS - Branch of the FSRC «Crystallography and Photonics» RAS. He has 90 publications, including 30 scientific papers and 2 monograph (with coauthors). His research interests are currently focused on image compression, space images processing, geoinformation technologies. E-mail: mgash@smr.ru .

Received March 21, 2019. The final version - May 14, 2019.

660

KoMntroTepHaa onTHKa, 2019, tom 43, .№4