Введение

Основные процедуры в методе восстановления резкости – преобразования Ван-Циттера, конволюции и деконволюции, инверсная или винеровская с модификациями фильтрации, обработка обобщенным градиентным оператором наиболее оптимально организуются в виде поточных параллельно-конвейерных процессов, что соответствует применению (особенно в бортовых вариантах модели распределенной среды) [3, 4].

Для пополнения пространства операций задачи восстановления резкости разработана порождающая проблемно-ориентированную компьютерную арифметику (ПОКА) обобщенная бинарная билинейная операция (ОББО)) [3,4] со сплошным спектром состояний, в числе которых свертка позиционных кодов, умножение кодов и промежуточные состояния, управляемая параметром взаимного сдвига частичных результатов в ромбе операции умножения или величиной аддитивного возмущения ее базовой таблицы. Однако вычислительная сложность ОББО соответствует вычислительной сложности операции свертки массивов и требует снижения ее, т.е. организации быстрых модификаций операции. Кроме того, большинство операций, включаемых в набор ПОКА для задач коррекции резкости на изображениях требуют снижения их сложностей для повышения вычислительной эффективности решения задачи коррекции.

Реализация быстрых вариантов операций проблемно-ориентированной компьютерной арифметики

Математически ОББО строится как свертка двух Z-преобразований массивов (или как свертка двух полиномов) с формированием классического ромба столбцов с выполнением суммирования вдоль столбцов в ромбе с передачей возможных переносов в старшие по номеру столбцы, если взаимный сдвиг на оси порядков этих столбцов уменьшен. Управление этим сдвигом осуществляется выполнением схемы скалярного перемножения результата свертки с нормирующим вектoром ρс={βсi}, где i – и индекс, и степень вещественного основания βс. Z-преобразование (и полиномы), а также сами массивы представляют собой представление структурированной переменной в позиционной системе. Для операции умножения кортежей А и В, при этом, в соответствии с выше указанным, можно записать

AxB=(A**B, ρс)                                           (1)

и в результате вычисления (1) получим, как принято считать в соответствии с определением скалярного произведения, скаляр Σ{A**B}i {βсi}, т.е. новый позиционный код из коэффициентов его позиционного представления. Если βс=βс0, где βс0 – основание системы счисления, представляющей кортежи без искажений, записанные в полиномиальной форме А=Σ {A}i βсi0 и В==Σ {В}i βсi0, то полученный результат и будет результатом выполнения операции умножения. При увеличении неравенства βс>>βс0 достигается состояние ОББО – выполнение свертки, при βс=1 – наступает вырожденное состояние ОББО. ОББО – операция со сплошным спектром состояний (включающим состояния: ** – свертки, х – умножения и вырожденное состояние при βc (параметр состояния операции) равном единице). Если операнды ОББО не Z-преобразования и не полиномы, то кортежи {A}i и {В}i в регистрах операндов размещаются в соответствии с принятой арабской позиционной системой, что легко достигается простой переиндексацией элементов кортежей.

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

При деконволюции (уменьшении апертуры функции рассеяния точки (ФРТ)) алгоритмы класса Фурье-преобразований, сверток, линейных фильтраций, реализуемые в алгебре с операциями «сложить» и «умножить», более эффективно осуществляются на основе операций, таких, например, как, восьми- четырех- или двухточечное преобразование Фурье, Адамара, Уолша, представимых довольно легко таблично и организуемых однотактной выборкой значений из таблицы, размещаемой в согласованно структурируемой памяти компьютера [2]. Однако легко заметить, что этим таблицам однозначно соответствуют таблицы восьми-, четырех- или двухточечных сверток векторов соответствующих размерностей. При этом, вычислительное устройство, реализующее вычислительные процессы на основе «классической» арифметики, работает на порядки эффективнее, если в этой арифметической системе заменить двухместную операцию умножения, скажем, на перечисленные выше билинейные, то есть удовлетворяющие условиям дистрибутивности и тому подобным условиям табличные операции. Возврат вычислителя в традиционную арифметическую систему не только реализуется элементарно, но и обеспечивается при этом гораздо более эффективная реализация той же операции умножения. Примером тому теорема о замене классического алгоритма умножения целых чисел (алгоритма сложности n² (n – разрядность операции с учетом того, что можно считать разрядности входных операндов одинаковыми, заменяя нулями отсутствующие старшие разряды у «малоразрядного» операнда)) тремя быстрыми преобразованиями Фурье (БПФ) (с вычислительной сложностью результирующей операции ; строго говоря, здесь еще присутствует аддитивная добавка в виде 3n, где 2n – количество операций при покомпонентном перемножении спектральных образов (достаточно использовать спектры первого и второго квадрантов спектральных координат) и n – вычислительные затраты на использование нормирующего вектора при приведении результата от свертки к умножению, но в данных расчета будем иметь в виду, что размерности решаемых задач не менее n =256, и тогда добавкой в 3n можно пренебречь).

При моделировании на ПК двумерной свертки двух изображений размерностью 512х512 пикселов в индексной палитре (глубина цвета 1 байт) с реализацией модели конвейерно-параллельного вычислителя с условным распараллеливанием на 4 ветви, тактовой длиной 512 табличных операций с таблицами арифметической системы, представляющими собой табличные математические процессоры свертки размерностью 2х2 вместо операции умножения, получено сокращение времени процедуры свертки по сравнению с использованием «традиционного» ускорения процедурой 512-точечного БПФ (конвейер в графе Баттерфляй) около 29 раз.

Расчетное сокращение времени составило примерно 3×512×512×16/(4×256×256)=48 раз (в числителе – типовой расчет затрат тактов на использование БПФ, в знаменателе – расчет числа выборок из памяти для восстановления суммированием со сдвигом полноразмерной свертки).

Необходимость распараллеливания конвейерных (потоковых) алгоритмов и спецсредств для операций типа свертки играет важную роль и является одним из основных вычислительных элементов в координируемой коррекции – коррекции по формулам Ван Циттера, в вычислении значений погрешностей на сравниваемых изображениях, в фильтрации и обработке изображений масками. Количество повторений операции огромно, а что касается изображений высокого разрешения, размеры которых в одном спектральном канале (которых может быть десять и десятки) до 10¹² байт на отображаемую площадь обзора в 10 кв.км, а в системах со сверхразрешением число байт увеличивается на порядок. С учетом того что вычислительная сложность операции свертки имеет вид квадратичной зависимости, то число элементарных умножений байтов друг на друга в свертках достигает значений 10²⁶ -10 ²⁸. Уровень быстродействия современной элементной базы, для выполнения сверток в обозримое время- 20 минут на Земле и доли секунд на борту, требует высокой степени распараллеливания даже поточно выполняемых операций. Элементная база соответствующего аппаратного средства, построенного на принципе подключения необходимых модулей к конвейерно-параллельному тактируемому коммутатору – регистры с мультиплексными схемами, запоминающие устройства (ПЗУ и ОЗУ), программируемые логические матрицы, т.к. все алгоритмы (включая БПФ) просчитываются с требованием выдачи байтных кодов, т.е. всего 256 различных результатов (независимо от длины алгоритма), которые запоминаются как таблица специальной (однотактной) операции [1,5]. Предлагаемая архитектура обладает высокой степенью живучести за счет коммутируемой взаимозамены модулей, а набор табличных операций позволяет реализовать и «стандартную» арифметическую систему (представлением свертки или умножения табличными Фурье образами или на основе теоремы Рисса-Фреше об операторах и функционалах и рекомендуется в основном для применения в беспилотных авиасредствах.

Заключение

В результате дообработки космических изображений с применением обобщенных операций и их эмуляции на ПК повышена их резкость (и, соответственно, реализуемое изображениями пространственное разрешение на местности) строго за счет подавления остаточной ФРТ до 1,2 – 1,4 раз.

Подавлена остаточная ФРТ на изображениях спутников ObrView-3, БКА-1-3, Канопус, «Ресурс-ДК», Ikonos, QuickBird (входящих в ряд разработок мирового уровня: ObrView-3, Spot-5, Pleiades-1A, Pleiades-1B - спутники с технологией сверхразрешения; БКА-1-3, Канопус, «Аркон», «Ресурс-ДК», Ikonos, QuickBird спутники с высоким разрешением).

Работа выполнена при финансовой поддержке РФФИ в рамках научного проекта № 14-07-00171 "Разработка теоретических основ методов моделирования и алгоритмов представления в обобщенных операциях трактов преобразования дистанционных данных с максимизацией эффективности обработки информации (цифровых космических изображений)".