Развитие и реализация быстрых алгоритмов дискретных ортогональных преобразований с рекурсивной структурой в системах обработки изображений Долгих, Михаил Николаевич

Введение к работе

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

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

Поставленная цель определила следующие основные задачи:

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

1. Синтез новых шдифицировагашх алгоритмов быстрых ортогональных преобразований (ДПФ, нечетно-частотного ДПФ -НЧДПФ) для вычисления операторов свертки над полем действительных чисел с наименьшей оценкой вычислительной сложности и регулярной структурой.

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

3. Создание и применение программною обеспечения на осьове реализованных процедур для систем цифровой ооработки изображений в видимой и УК- областях cnucrpu.

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

Методы исследования. Теоретические исследования в диссертационной работе проводились на ос.юве методов матричной алгебры, теории сложности вычислений и цифровой обработки сигналов, теории структурированного программирования. Экспериментальные исследования выполнялись с помощью моделирования ьа ЭВМ в составе цифровых яніомг»шзировннн"х

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

1. Предложена новая методика реалигэции параллельных
вычислений для выполнения одно- и двумерных рекурсивных
алгоритмов БПФ на основе структурированного подхода и новой
схемы векторизации данных.

2. Разработана и реализована эффективная рекурсивная схема
индексирования (РСИ) для алгоритмов БПФ с регулярной структурой
на параллелных процессорах и ЭВМ с архитектурой Фон Неймана.

3. Разработан модифицированный алгоритм быстрого
собственного преобразования для матричных операторов свертки
(СПОС) над полем действительных чисел с наименьшей оценкой
вычислительной сложности.

4. Реализованы процедуры цифровой обработки изображений - сжатия информации на основе ортогональных преобразований; выделения - контуров на цифровых изображениях; идентификации изображен^ с деформациями сдвига, поворота и масштабирования; корреляционной привязки объектов на изображениях - с использованием предложенных в диссертации рекурсивной схемы индексирования и неизбыточных быстрых алгоритмов.

5. Разработано программное обеспечение для систем цифровой обработки изображений в видимой и ИК- областях спектра на основе реализованных процедур.

Практическая ценность. Результаты диссертационной работы нашли применение в цифровых системах обработки изображений,-созданных как на базе ЭВМ с архитектурой фон Неймана, так и на базе специализированных параллельных вычислителей. Разработанный и реализованный в работе способ рекурсивного индексирования может бчть применен при программной реализации быстрых алгоритмов спектрального анализа с регулярной структурой, а так же при проектировании специализированных вычислителей и комплектов СБИС, ориентированных на цифровую обработку сигналов.

Реализация результатов. Полученные в диссертационной работе результаты использовались в Институте технической кибернетики АНБ, в Академическом научном комплексе (ЛИК)

- 4 -"Институт тепло- и массообмена им. А.В. Лыкова" АНБ и в Белгосуниверситете. Результаты внедрения подтверждены соответствующими актами. Четыре программных продукти приняты в Государственный и Республиканский фонды алгоритмов и программ (ГосФАП СССР и РФАП Беларуси).

Апробация работы. Основные научные результаты работы
докладывэпись и обсуждались на конференции БГУ "Применение
лазерной и оптоэлектронной техники в народном хозяйстве»
(г.Минек, сентябрь 1985 г.), Зональной научно-технической
конференции «Обработка информации в автоматизированных системах
научных исследований" (г.Пенза, апрель 1989 г.), Международной
конференции молодых ученых "kovacov -89^й (ЧСФР, г.Ковачев,
октябрь 1989 г.), Всесоюзной научно-технической конференции
"Надежность машин, математическое и машинное моделирование
задач динамики. Моделирование-91^м (г.Кишинев, май 1991 г.),
Международной конференции "Высокопроизводительные

вычислительные системы" (г.Алма-Ата, сентябрь 1991 г.).

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

Основные положения, выносимые на зашиту.

1. Новый способ реализации алгоритмов БПФ с регулярной структурой на основе рекурсивной схемы индексирования векторов данных.

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

3. Способ параллельного вычисления ДПФ на основе применения структурированного подхода и рекурсивной схеми индексирования при реализации алгоритмов БПФ на параллельных

ВЫЧИСЛИТеЛЯХ ТИПа "VERY LONG INSTRUCTION WORD" (VLIW).

4. Кодифицированный быстрый алгоритм собственного преобразования оператора свертки (СПОС) над погем действительных чисел с наименьшим числом действительь.м операций.

5. Программное обеспечения систен обработки цифровых изображений в видимой и ПК- обласінх ппклра но основе

- 5 -разработанных и реализованлых процедур ЦОС: сжатия информации, выделения контуров, обработки изображении с деформациями сдвига, поворота и масштабирования, привязки объектов на цифровых изображениях.

Стпуктура и объем работы, диссертационная работа состоит из введения, четырех глав и заключения, изложегшнх на 117 страницах машинописного текста, иллюстрирована 78 рисунками и таблицами, размещенными на 84 страницах. Список литературы включает 188 наименований, приложение содержит 27 страниц.