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

РГ8 ОД

о / т

штт наук Беларуси

ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ШСТИТУТ ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ

На правах рукописи ДОЛГИХ МИХАИЛ НИКОЛАЕВИЧ

УДК 531.51.01:681.325.5.06

РАЗВИТИЕ И РЕАЛИЗАЦИЯ ЕНСТШХ АЛГОРИТМОВ ДИСКРЕТНЫХ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ С РЕКУРСИВНОЙ СТРУКТУРОЙ В СИСТЕМАХ ОБРАБОТКИ ИЗОБРАЖЕНИЙ

Специальность: 05.13.16 - Применение вычислительной техникг

математического . моделирования и математических нетолов в научных исследованиях

Автореферат диссертации на соисг.ание ученой степени кандидата технических наук

минск - 1993

Работа выполнена в Институте технической кибернетики АН Беларуси.

Научный руководитель: доктор технических наук

A.M. КРОТ

Официальные оппоненты: доктор технических наук, профессор

P.I. САДЫХОВ, кандидат технических наук О-В. ПОДРОБНЫЙ

Ведущая организация: Минский радиотехнический институт

. 30

Зашита диссертации состоятся » 13 » ноьфя 1993 г. в

на заседают специализированного совета по защите диссертаций

Д006.24.01 при ордена Трудового Красного Знамени Институте

технической кибернетики АН Беларуси (220012, Минск-?2. ул. сурганова, 6, конференц-зал).

С диссертацией можно ознакомиться в библиотеке института. Автореферат разослан ''_"октября 1993 г.

Ученый секретарь Специализированного

совета, д.т.н. <__. 7 ' Г.И. Алексеев

'

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТ»

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

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

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

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

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

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

4. Создание и применение программною обеспечения на осьове реализованных процедур для систем шаровой ооработки изображений в видимой и 1'К- областях сне.-.три.

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

Методы исследования. Теоретические исследования в

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

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

Новые научные результат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Способ параллельного вычисления ДПФ на основе применения структурированного подхода и рекурсивной схемн индексирования при реализации алгоритмов БПФ на параллельных вычислителях типа «ver* long i»structiom woru" (vliw).

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

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

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

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Эффективное по времени и точности вычисление ДПФ остается актуальной проблемой для всех разделов ЦОС

N-1 kn

x(k) - i xfn)«^ , fc - о, l,..., и-i, (i)

n»0

где Ии - exp(-i- -22.), j - /Т\

Например, при реализации алгоритмов БПФ на параллельном специализированном процессоре обработки данных "Электроника МТ-70" типа vliw влияние архитектуры снижает эффективность

традиционного способа индексирования данных на основе вложенных циклов. Реальная'производительность вычислительных средств при реализации алгоритмов БПФ зависит от затрат на выполнение арифметических операций и от затрат на индексирование данных. Таким образом, при больших объемах обрабатываемых данных в общее время вычислений (т1иЛ, помимо операций сложения и умножения <т1), значительный вклад вносят операции управления данными (т.,)

т4ьо - т, + т2 . (2)

Последнее прямо связано с простотой схемы для реализации алгоритма, но при анализе его вычислительной сложности не рассматривается. Для вычислительных устройств с параллельной архитектурой наименьшее число арифметических операций не является гарантией минимизации времени выполнения алгоритма. Известная схема индексирования данных при реализации БПФ вложенными циклами минимизирует число обращений к регистровому файлу при вычислении коэффициентов преобразования за счет разрушения нетривиальной структуры рекордных алгоритмов. Схема индексирования вложенными циклами реализует пошаговое вычисление ДО*-. Это означает, что переход от стадии м( к м1и происходит только после преобразования множества всех N чисел на входе в н чисел ла выходе каждого этапа. С другой стороны, значения адресов векторов данных сограняются постоянными в течение, всех этапов расчета ДГФ при реализации процедур прореживания. Для минимизации затрат на индексирование при программной реализации БПФ следует вычислять адреса векторов данных заранее (непосредственно перед расчет ли коэффициентов ЛФ). Решение задачи разделения вычислительных фаз БПФ для последовательностей длиной степени два (н - 2°) дает рекурсивная схема. Большинство быстрых алгоритмов вычисления ДПФ обладахя важным свойством рекурсивности. Этим фик.ом* определяется простота алгоритма, когда коэффициенты преобразования на разных этапах получаются из оператора ДПФ, вычисляемого каждый раз через самого сеоя. Предложенная в работе рекурсивная схема индексирования (РСИ) для реялизации быстрых алгоритмов вычисления ДПФ формирует этапы вычислений из групп разлагаемых ДПФ меньшей длины до получения базовых

а) Одна базовая б) Две базовых

операция операции

А(Хп), ВСХп) - базовые операции преобразования; ГОШ - рекурсивная процедура, выполняющая

индексирование; Ех - выход:

Р - флаг для выбора базовой операции

преобразования

Ри! 1 Структурированные блок-диаграммы (тесурсивннх щг'прдур для реализации алгоритмов Б1М> с регулярной '"П,т-/ктурой

элементарных ДПФ (рис. I). РСИ использует основное свойство повторяемости и для вычисления коэффициентов преобразования, и для определения порядка выполнения базовых арифметических операций перед их выполнением. В работе исследовались быстрые алгоритмы действительного преобразования Фурье (АДБПФ) при реализации их на быстродействующем периферийном процессоре (БПП) "Электроника МТ-70» типа vliw с конвейерным процессором команд. Благодаря применению рекурсивного индексирования, параллельный вычислитель получает в начале работы вместе с исходными числовыми данными правила их соединения• В этом случае время, необходимое для индексирования векторов данных, будет оказывать наименьшее влияние на общее время выполнения алгоритма (2). Рекурсивная схема сохраняет принцип прореживания и для алгоритма действительного быстрого преобразования Фурье по расщепляемому основанию (АДБПФ-РО) Крота-Минервиной с двумя базовыми операциями, когда н-точечное ДПФ разлагается на одно . N/2-точечное и два "/4-точечных ДПФ (см. рис. I).

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

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

Вторая глава посвящена разработке новых модификаций быстрого алгоритма собственного преобразования оператора свертки (СПОС), предложенного A.M. Кротом, над полем действительных чисел с предельной вычислительной сложностью для эффективного вычисления ДПФ. СПОС матричного оператора циклической свертки (ЦС) является ДИФ (П. НЧДПФ является СНОС для опер?.горя кооокикличегкой свертки <К1Ю). к./шсл^пт ДПФ па

основе ряда НЧДПФ меньшей длины есть реализация схемы вычисления ЦС посредством ряда КЦС меньших размеров:

КЦС —♦ НЧДПФ —> ДПФ —> ЦС . Вычисления коэффициентов для алгоритма СПОС над л производятся только в действительном поле, что позволяет существенно упростить программные реализации и может быть эффективно использовано при проектировании спецпроцессоров цифровой обработки. Наименьшие теоретические оценки вычислительной сложности, известные для алгоритма СПОС над и, ставят задачу построения эффективной схемы его реализации.

В работе описана факторизация матрицы действительного СПОС, соответствующая предельной оценке вычислительной сложности исследуемого алгоритма. СПОС для КЦС имеет вид НЧДПФ:

К-1 п пк

х» " £ *ЛЛ ' к " и-1- <3>

п*0

где - ехр(-Зтг/я), хп - исходная последовательность,

хк - последовательность коэффициентов НЧДПФ. Коэффициенты действительного НЧДПФ удовлетворяют свойству эрмитовой симметрии: - х* , к » о, 1,..., N/2-1, где * - символ

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

М(Н) = 1/2Н(1одгН-1) ; (4)

А(М) =» з/2М(1одгН-1) - ЗМ(Н) , (5)

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

-ю-

Р »Р О я

0

р в и/4 о

о О р н n/4

ЕН/8 в а4 '

ЕМ/2 0

0 с1 2 „N/16+1 2

<,N/16-1

2 пЫ/8-1 2

ЕИ/2 О

0 ЕН/8 « В4

где - единичная н/2хм/2 матрща, <гн - матрица перестановки столбцов по закону двоичной инверсии,

"2И

-с м'г_1 2и

N/2-1 1

1-1, N/4+1,..., N/4—1, N/2-1;

Н/'

N/4

ЕЫ/8 0

О ЕН/16® сН/4 2

ЕН/8 О

О Еы/16в ГИ/4 2

где -соз(1т1/М)

N/2-1;

ЕЫ/8 ЕИ/8

^/Хб* Ь2 -1И/16в Ь

ЕЫ/8 ЕЫ/8

1 О О -1

р в n/8 о

0 р н н/8

р в ы/8 0

о р н n/8

Е2 Е2

Ъ2

Е2 О

0 гЫ/4 2

11/4

1 '

Рис. 2. Представление матрицу действительного '"НОС в виде произведения слаОозаполненных матриц на основе факторизации ее по столбцам

iMlowim1 гн

множителей для организации вычислений двухточечных КЦС. Каждая и. таких сверток выполняется за м-чимальное число арифметических операций, равное 3 действительным умножениям и 3 сло.тениям, н1! основе предварительнрй организации вычислений. В целом, быстрый алгоритм СПОС над и может эффективно быть выполнен на основе РСИ для обеих модификаций, при использовании схемы индексирования с вложенными'циклами общее число процедур для о, ганиздции вычислений сокращается без ущерба для функционально., эквивалентности. ■

В работе показаны результаты тестирования программных реализаций предложенных модификаций быстрого алгоритма действительного НЧДПФ и алгоритм^ действительного ДПФ, разработанного на его основе. Характеристики этих алгоритмов приведены в сравнении с наиболее известный! программными реализациями быстрых алгоритмов вычисления действительного НЧДПФ и действительного ДПФ Кули-Тыоки, Соренсенс-Джонса, Крота-Минервиной и других. Результаты сравнения показывают преимущество разработанных модифицированных быстрых алгоритмов вычисления НЧДПФ и ДПФ над некоторыми из них по времени выполнения и точности. Основные положения, определяющие достигнутые преимущества:

т алгоритмы имеют регулярную частично-рекурсивную структуру;

- вычисления коэффициентов пр' образований выполняются только в чисто действительной арифметике;

- взвешивание на поворачивающие множители выполняется только за 3 действительных умножения и 3 действительных сложения;

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

действительного НЧДПФ поззоляет сократить время преобразования в 1.3-2.2 раза по сравнению с алгоритмами выполнения действительного »-точечного НЧДПФ на основе БПФ и при этом повысить точность вычислений больше, чем на порядок.

Третья глава посвящена применению быстрых алгоритмов дискретных ортогональных преобразований, рассмотренных в работе, и эффективных способе» их реализации при выполнении

- га -

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

В задачах сжатия информации на основе спектрального представления НЧДПФ (3) занимает промежуточную позииш между ДПФ и преобразованием Карунена-Лоэва (ГШ). ПКЛ является лучшим по точности, но не имеет эффективных быстрых алгоритмов. В результате применения предложенного модифицированного алгоритма быстрого вычисления НЧДПФ точность восстановления после выполнения процедуры сжатия была увеличена на порядок по сравнению со сжатием на основе ДПФ (рис. 4). Сокращение числа используемых коэффициентов преобразования после выполнения двумерного действительного обрабатыьаемого изображения

достигается фиксированием порогового уровня. Коэффициент сжатия Кс» определяется из отношения общего числа коэффициентов преобразования ^ к числу сохраненных в процессе сжатия коэффициентов йсощ.

Способом усиления информационных признаков объектов на "Ифропх фотографических изображениях является щ.-шенение дискретного преобразования Гильбер.а (ДПГ). В матричном виде ДПГ определяется следущим образом

Vх - ^'(лл*) - <б>

где - матрица ДПГ, и - матрицы прямого и обратного ДПФ, ;т - диагональная матрица, соответствующая коэ^чшиенту пропускания фильтра Гильберта - Звдп(к), тдо здп(к) - стыковая функция. Матри'/а ДПГ имеет сложный вид для факторизашш. Эффективное по быстродействию вычисление ДиГ ->с; ществляется на основе применения БГС>. Сокращен!, з времеш1 и повышение точности при вычислении ДЛГ достигается за счет использования раэработашщ в диссертации рациональной схемы индексирования и мочифицироьшпюго быстрого .лгоритма вычисле1гая НЧ| ;ф с продельной оценкой вычислительной сложности. Результатом применения лпуг.!"рного "ГТ к исходному изображению является

■Я Г

•-••••ЯМ

а) Восстановленное изображение после процедуры сжатия на основе НЧДПФ

"я.. 1; АЛ'

б) Восстановленное изображение после процедуры сжатия на основе ДПФ

преобра- уровень к •У £

зование порога

нчдда 0.012 1.5 0.7 0.016

ДПФ 0.С1 1.5 1.6 0.254

Рис. 4. Рпаим^связь к со средним значением ошибки у и СКО - с при выполнении сжатия на основе спектрального представления

выделение огибающих, приводящее к подчеркиванию границ и контуров на изображении.

ДПФ обладает свойств« и инвариантности относительно сдвигов по пространственным координатам. Проблема сохранения инвариантности ЛИФ' при геометрическом преобразовании, связанном с изменением масштаба, решается с помощь») дискретного преобразования Меллина (ДГ1М)

Кьи * £ х(ехр(пДЬ)| • |ехр(-}пкЛЬ Лм) | . (7)

ДПМ решетчатой фушанш хп - х(нДу), где п-лу - ехр(п-лн), эквивалентно ДПФ решетчатой функции х(вхр(п))

ы-1

Х^ - £ х(ехр(п)) , к - О.....Н 1 . (8)

п = 0

В более общем случае дискретное преобра^ >вшше, инвариантное и к деформациям масштабирования, и поворота может бить реализовано на основе применения логарифшческо- лолярного геометрического преобразования нлоскосчп пространственных ко рдаат

и = еп1:[1п[п* + п=)] ; (9)

v - еп^аг^д^/п,^ , (10)

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

Дли реализации процедур обнаружения и '^вмещения .ыфровых изображений применяется корреляционная привязка. Осуществление процедуры обнаружения объекта хы размерим н (хмг на цифровом фотоизображении э г размером м,хм2 на основе корреляционно-экстремальной привязки, заключается п расчете двумерной нормированной взаимной корреляционной . функции г 5, где N^N^=N■2", м|=м_=м=2<5 (р а). Для определения двумерной функции корреляции с максимальными значениями г и оценки

11 к, "5

смещений п1 и т»7 необходимо Гфоввсти вычисления дчя пгех

вариантов положения окна в зоне поиска. Обойти большую трудоемкость метода и сократить время вычипений в 1.4 раза (м = 64, н - в, 16 градаций яркости) позволяет организация вычисления ДПФ на основе РСИ и .модифицированного алгоритма действительного СПОС. Кроме корреляционно-экстремального метода привязки цифровых изображений для решения подобной задачи в работе рассмотрен пример использобания свойства инвариантности ДПФ и энергетического пространственного спектра изображения относительно пространственных сдвигов.

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

сократить время трудоемких процедур обработки изображений ■ позволяет использование в составе вычислительных комплексов спецпроцессора цифровой обработки "ЭЛЕКТРОНИКА МТ-70" типа уын, при этом время выполнения ДПФ сокращается в два раза. Применение разработанной эффективной рекурсивной схемы индексирования для реализации алгоритмов БПФ последовательностей длины степени два позволили увеличить быстрочействие процедур цифровой обработки в 1.4-1.в раза; в I.6-8.0 раза сократить объем передаваемой информации для задач

- 17 -

сжатия на основе ДПФ и НЧДПФ.

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

ОСНОВЫЕ РЕЗУЛЬТАТЫ И ШБОДИ РАБОТЫ

1. Решена задача. повлиения производительности систем спектральной цифровой обработки сигналов и изображулий посредством оригинальной программной реализации быстрых алгоритмов дискретных ортогональных преобразований с регулярной структурой и с наименьшим числом обращений к памяти данных на основе рекурсивной схемы индексирования.

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

2. Созданы эффективные программы на языке ПА.;КАЛЬ, реа^и'ущие алгоритмы действительного БПФ - АДБПФ и АДБПФ-РО на основе РСИ для параллельное, периферийного вычисителя "Электроника 1.ТГ-70" и ПЭВМ (см. рис.1), которые приняты в Государственный фонд алгоритмов и програ^г. При N = л 09В рги сокращает время вычисления коэффициентов Действительного ДПФ по сравнению со схемой индексирования вложенными циклами

- в 2.1 раза для БПП при реализации АДБПФ;

- в 1.8 раза для ПЭВМ при реализации АДБПФ-РО.

3. Разработаны модифицированные быстрые алгоритмы вычисления действительного НЧДПФ для последовательностей длины стопени два, обеспечивающие достижение наименьшей сценки вычислительной сложности („и. рис.3). В разработанной

• программной реализации псе вычисления производятся -одько в действительной нри^метике, двухточечные косоц'тог'чсские спе^тки

данных и поворачивающих множителей выполняются за минимальное члсл<~ арифметических операций, благодаря предварительной подготовке и хранению отсчетов косинусной функции. Применение разработанного быстрого алгоритма вычисления действительного НЧДПФ сокращает время выполнения преобразования в 1.3-2.2 раза и повышает точность вычислений на порядок. При организации вычисления коэффициентов действительного ' ДЧФ на основе разработанного алгоритма расчета НЧДПФ время выполнения преобразования сокращается в 1.2 раза.

4. Программные реализации быстрых алгоритмов дискретных преобразований Фурье, Гильберта, Меллина применены в процедурах цифровой обработки изображений :' сжатия информации по спектральным признакам; выделения огибающей изображения исслпуемого объекта ; обработки изображений с деформациями сдвига, поворота и масштабирования; при реализации процедур привязки объектов на цифровых изображениях. Реализация процедуры компрессии с коэффициентом сжатия Г.5-2.0 на основе разработанного быстрого алгоритма действительного НЧДПФ восстанагливает изооражение точнее, чем ни основе ДПФ. Процедура коррепшолно-экстремальной привязки цифровых изображетмй на основе алгоритма расчета ДПФ через НЧДПФ выполняется в I.* раса быстрее, чем корреляционная привязка на основе традиционных алгоритмов шчисления ДПФ.

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

в системе обработки и идентификации фотографических изображений?

в системе ИК- термографии, в цифровом сканирующем инфракрасном спектрорчлиометре "Клин";

в приемно-регистристрирующей системе слабосветяшихся объектов в видимой облаетл спектра.

Перечисленные системы цифровой обработки изображений в видимой и ИК- областях спектра приняты к использованию и. штлрпнн в то "Точные приборы" (г. Москва), АНК ИТМО им. Лнкопа ЛИ Беларуси, лаборатории экспериментальных средств и мчтол~п обработки оптической информации Белгосуниверситета.

- 19 -

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРГАШИ

1. Долгих М.Н. Программное обеспечение периферийного вычислителя ЭЛЕКТРОНИКА МГ-70 в задачах цифровой обработки сигналов.-Минск, 1988.-46 с.(Препринт / Ин-т техн. кибернетики АН БССР,- n 36).

2. Долгих V м.н. . Расширен!" ■ базового программного обеспечения спецпроцессора ЭЛЕКТРОНИКА МТ-70//Артсчатизаиия испытаний технических объектов/ Минск: Ин-т техн. кибернетики АН БССР. 1989.-С. II9-I3I.

3. Крот A.M., Долгих М.Н. Моделировашю не;-шективиых алгоритмов цифровой обработки сигналов на параллельном процессоре // Conference of young scientists KOVAÖOV 89, Czechoslovakia, october 4-8, 1989: Тез. ДОКЛ.-С. 4.

4. Драгун В.Л., Долгих М.Н., Филатов С.А., Козлова А.П. Алгоритмы быстрого преобразования Фурье в системах анализа ИК-изображений.-Минск, 1990.-30 с. (Препринт / Ин-т гепло- и массообмена им. A.B. Ликова АН БССР, n 13).

5. Крот A.M., Долгих М.Н. Рекурсивная программа быстрого преобразования Фурье одномерных последовательностей для быстродействующего периферийного процессора ЭЛЕКТРОНИКА мт-70 // Ино. бюл. "Алгоритмы и программы".- 1091, н 3 . -С. 1j.

6. Крот A.M., Долгих М.Н. Рекурсивная программа для вычисления действительного быстрого преобразования Фурье по расщепляемому основанию // Инф. бюл. "Алгиртмы н программы". -1991, N 3 .-С. 10

7. Долгих М.Н. Копию,с программ управления фотометрической системой // Инф. бюл. "Алгоритмы и npoi, -мин".-I9o6, n Л .-С. 8.

8. Драгун У.Л., Холадава A.A., Ф1латп$ С.Д., До$г1х М.М. i iiiui. Диягностыка эахворввннн^ пи лрасторньнх спектральных прыкметих метадам! шшчалыгай 14 тьрмаграфи / necui АН БССР. Сер. OiüJi. 1991. н 2.-С. 100-109.

э. Долгих м.н. Эффективная рекурсивная схема индексирования для илгоргтмов дейсшпельноп РИФ // Высокопроизводительные вычислительные системы в управлении и научных исследованиях. 1'ез. докл. Ме«д. конф. Алма-Ата, сентябрь, I.'9J.-C. 46.

гх) -

10. Драгун В.Л., Филатов С.А., Долгих М.Н., Белова A.B., Козлова Л. П. Вычислительная ИК-термография: идентификация объектов. Мшгск, 1991.-26 с. (Препринг/Ин-т тепло- и массообмена им. A.B. Лыкова АН БССР, N 6).

11. Драгун В.Л., Долгих М.И., Филатов С.А. Применение многопроцессорной системы для обработки ИК изображений / Весц! АН БССР. Сер. фиэ.-энерг. 1991. Nl.-C. 73-77:

12. Долгих М.Н. Реализация алгоритмов действительного быстрого преобразовать Фурье на основе рекурсивной схемы индексирования // Средства автоматизированных систем испытаний / Минск: Ин-т техн. кибернетики АН Беларуси. 1992.-С. 86-100.

13. Крот A.M., Долгих М.Н. К вопросу о реализации быстрых алгоритмов собственных преобразований операторов свертки в поле действительных чисел.-Минск, 1992.-60 с. (Препринт/Ин-т техн. кибернетики АН Беларуси; N II).

14. Крот A.M., Долгих М.Н. Применение быстрых алгоритмов дискретных ортогональных преобразований в задачах сжатия и распознавания цифровых изображений.-Минск, 1993.-62 с. (Нренринт/Ин-т техн. кибернетики АН Беларуси; No).

Подписано к печати II.10.1993 г.'

Форлт «0xR4 t/16. Объем I иеч.л. Тираж 100 экз. заказ 152

Отпечатано на ротапринте Института технической кибернетики ЛИ Рл.ЛЛру<ЧГ, рргкпз, Мшгск, ул. Сургпновй, 6»