ВВЕДЕНИЕ

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

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

Анализ задач, решаемых ВИС и ДЭС, показывает, что:

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

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

Однако во всех разноуровневых звеньях таких систем присутствуют однотипные базовые алгоритмы, имеющие одинаковую структуру. Такими алгоритмами являются алгоритмы линейной пространственно-временной обработки на основе методов дискретного преобразования Фурье и цифровых сверток, алгоритмы нелинейных поточечных преобразований, алгоритмы ранговой обработки. Очевидно, чем более однотипными и простыми средствами реализуются базовые алгоритмы, тем эффективнее оказываются АСОИз в целом. Базовые алгоритмы, входящие в различные звенья, должны синтезировать по критерию максимальной эквивалентной пропускной способности или вычислительной производительности. Базовые алгоритмы, в свою очередь, определяют архитектуру специализированных процессов, их реализующих.

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

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

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

В настоящее время появляются быстрые алгоритмы дискретного преобразования Хартли (ДПХ). Часто их приводят в качестве альтернативы БПФ. Очевидно, что необходимо детальное исследование этих алгоритмов с целью вестороннего исследования их свойств и ответа на вопрос: что лучше?

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

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

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

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

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