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

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ

1. ВВЕДЕНИЕ.

2. ВЫБОР НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ, АНАЛИЗ МАТЕМАТИЧЕСКОГО СОДЕРЖАНИЯ ЗАДАЧ ЦИФРОВОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ, ТРЕБОВАНИЯ К АППАРАТУРНО-ОРИЕНТИРОВАННЫМ АЛГОРИТМАМ.

2.1. Анализ требований, предъявляемых к алгоритмам, ориентированным на аппаратную реализацию

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

2.3. Анализ методов вычислений и определение критериев оценки разрабатываемых алгоритмов. бо

2.4. Дискретные линейные "преобразования в качестве альтернативного подхода при аппаратурной реализации ДКП.

2.5. Выбор аппаратурных методов для реализации типовых вычислительных процедур ДКП.•.-'.

2.6. Выводы.

3. РАЗРАБОТКА И ИССЛЕДОВАНИЕ АППАРАТУРНО-ОРИЕНТИРОВАННЫХ АЛГОРИТМОВ ДИСКРЕТНЫХ КОСИНУСНЫХ ПРЕОБРАЗОВАНИЙ.

3.1. Синтез алгоритмов типовых процедур реализации ДКП.

3.2 Разработка алгоритмов ДКП, оптимизированных под операции ЦОИ функционирующих в жестких временных ограничениях

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

3.3.1. Методика оценки погрешностей дискретизации и восстановления непрерывных изображений.

3.3.2. Погрешности при квантовании непрерывных* изображений по уровню и временной дискретизации.

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

3.4. Методика анализа погрешностей ДКП построенного на базе типовых и модифицированных процедур ДЛП.

3.5. Выводы.

4. ВОПРОСЫ РЕАЛИЗАЦИИ И АНАЛИЗА ОСНОВНЫХ ПАРАМЕТРОВ

РАЗРАБОТАННЫХ АЛГОРИТМОВ

4.1. Варианты реализации вычислительных структур, использующих разработанные алгоритмы. Параметры аппаратурных реализаций алгоритмов ДКП.

4.2. Характеристики типовых схем, применяемых при построении аппаратурных блоков ДКП.

4.3. Сравнительный анализ основных показателей алгоритмов ДКП, разработанных на основе типовых и модифицированных вычислительных процедур ДЛП.

4.4. Выводы.

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

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

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

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

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

Следует отметить, что перечисленные выше задачи требуют использования высокопроизводительных ЭВМ (порядка 109 -1014 операций с плавающей запятой в секунду). Существующие ныне персональные ЭВМ не в состоянии обеспечить требуемую производительность.

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

На современном этапе развития систем цифровой обработки сигналов доминируют два направления. Собственно DSP (Digital Signal Processing), когда для цифровой обработки сигналов используется сигнальный процессор специальной архитектуры, ориентированный на решение задач данного класса. NSP (Native Signal Processing), когда высокопроизводительный процессор общего назначения используется как для выполнения управляющих функций, так и для цифровой обработки сигналов, причем технологическая и исполнительная подсистемы практически совпадают. Концепция NSP наиболее широко используется в достаточно простых системах ЦОС для медленно меняющихся процессов либо в системах искусственного масштаба времени. В сложных системах реального времени (как правило, многопроцессорных с параллельной обработкой) используется почти исключительно концепция DSP.

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

Решение данной проблемы - использование новейшей элементной базы и разработка алгоритмов ориентированных на аппаратную обработку сигналов.

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

Однако имеется несколько проблем снижающих эффективность решения указанных задач ЦОИ с помощью систолических матриц.

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

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

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

В-четвертых,в качестве процессорных элементов используются процессоры с фоннеймановской архитектурой, что заведомо ухудшает достоинства матричной архитектуры, поскольку отдельные операции выполняются последовательно во времени.

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

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

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

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

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

В-третьих, они допускают уменьшение размерности в ходе выполнения вычислений.

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

• высокая степень интеграции;

• поддержка современными средствами автоматизации проектирования;

• возможность проведения на одном рабочем месте проектирования и изготовления (программирования) специализированной СБИС;

• простота внесения изменений в проект на любой стадии проектирования;

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

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

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

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

Основными направлениями исследования являются:

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

2)Анализ методов вычислений и определение критериев оценки разрабатываемых алгоритмов.

3)Синтез аппаратурно-ориентированных алгоритмов дискретных косинусных преобразований (ДКП), обеспечивающих необходимую производительность.

4) Разработка методики анализа погрешностей модифицированного алгоритма ДКП учитывающей специфику работы проектируемых спецвычислителей.

5) Исследование и сравнительный анализ основных показателей разработанных алгоритмов ДКП с соответствующими известными алгоритмами с учетом аппаратурной реализации в СВИС ПЛ.

Перечисленные направления исследований определяют структуру диссертации. Диссертация включает введение (первый раздел), три основных раздела, заключение приложения и список использованных источников.

4.4. Выводы

В данной главе проведен сравнительный анализ ряда аппаратурно-ориентированных алгоритмов дискретных косинусных преобразований, разработанных и исследованных в третьей главе, а также классического способа реализации указанных преобразований с помощью *длинных" операций. Сравнения алгоритмов проводились по пяти параметрам: операционная сложность алгоритмов, время получения решения (при распараллеливании вычислений), производительность вычислительного конвейера, реализующего алгоритмы преобразований, а также аппаратурная сложность (в условных вентилях) и время задержки блока ДЛП (в условных единицах времени' задержки на одном условном вентиле). Необходимость проведения подобных оценок объясняется, во-первых, назначением разработанных и исследуемых .алгоритмов как алгоритмов, ориентированных на аппаратурную реализацию, а во-вторых необходимостью показать справедливость предельных оценок относительной эффективности алгоритмов, в условиях конкретных схемных решений. Результаты сравнений позволяют утверждать, что: алгоритмы унитарных ДЛП по сравнению с классическим способом реализации этих преобразований характеризуются значительно меньшими аппаратурными затратами (в 2-5 раз) и на порядок более высокой производительностью вычислительного конвейера, при этом время получения решения для них, как правило, также меньше (в 1.5-4 раза); эффективность алгоритмов унитарных преобразований, основанных на двумерных ДЛП и предусматривающих выполнение унитарного преобразования в рамках единого итерационного процесса (ДКП на базе КП, ДКП на базе тригонометрического ДЛП) в значительной степени определяется степенью распараллеливания операции М-арного суммирования, выполняемого на каждой итерации этих алгоритмов; несмотря на возможность получения меньшего времени решения по сравнению с ДЛП-методами (в 1.2-2 раза) при максимальном распараллеливании 'длинных" операций в классическом варианте, подобный подход сопряжен с большими аппаратурными затратами;

- наименьшей сложностью характеризуется метод, основанный на обычном алгоритме ССЖШС, по соотношению сложности и быстродействия предпочтительнее алгоритм на базе тригонометрического ДЛП (соответственно в 1.2-1.5 раза сложнее и примерно в 1.5-1.6 раза быстрее варианта на СОРШ1С); при обработке чисел небольшой разрядности, а также, когда требуется небольшая точность вычислений, могут применяться модифицированные алгоритмы ДЛП вращений, в том числе разработанный модифицированный ДЛП ОДКП;

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

Основными научными результатами, полученными в этой главе, можно считать

- разработку графов . зависимости алгоритмов унитарных ДЛП на основе выражений, приведенных в третьей главе;

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

- на основе анализа известных функциональных схем ДЛП СОИШС и графов зависимости алгоритмов унитарных ДЛП получены оценки параметров основных вариантов аппаратурных блоков (конвейерный и на одном АЛУ) для наиболее алгоритмов унитарных ДЛП, выделенных в четвертой главе как наиболее эффективных;

- на основе сравнительного анализа вариантов аппаратурных блоков унитарных ДЛП показано, что реализация унитарных преобразований с помощью специальных ДЛП в рамках одного итерационного процесса позволяет в общем случае уменьшить время выполнения преобразований (для тригонометрического ДЛП -до 1.5 раз) по сравнению с поэтапной реализацией на вещественных блоках ДЛП, то есть, подтверждаются временные показатели алгоритмов, приведенные выше (напомним, что там речь шла о больших выигрышах во времени, но для предельного случая распараллеливания); в то же время относительные показатели аппаратурной сложности оказываются в ряде случаев более предпочтительными, чем показатели операционной сложности унитарных ДЛП за счет учета накладных расходов и сложности аппаратурной реализации отдельных операций, а также благодаря возможности выделения в отдельный аппаратурный блок оборудования, необходимого для выполнения одной итерации ДЛП метода. Так, для алгоритмов ДКП на базе модифицированных процедур ДЛП сложность аппаратурной реализации оказывается выше, чем для реализации на ССЖВЮ на 25-50%, в то время как операционная сложность для этих методов выше в 1.8-3 раза.

Таким образом, показано, что модифицированные ДЛП, реализующие дискретные косинусные преобразования, по сравнению с поэтапной реализацией ДКП, позволяют при аппаратурной реализации уменьшать время выполнения преобразования в среднем в 1.5 раза, при увеличении затрат на 20-30%, либо существенно снижать аппаратурные затраты (до 60%) за счет сокращения накладных расходов при незначительном увеличении времени преобразования (10-20%), либо - добиваться одновременного снижения затрат и уменьшения времени вычислений.

5. ЗАКЛЮЧЕНИЕ

В данной работе проведены исследования возможности реализации дискретных косинусных преобразований в виде аппаратурно-ориентированных алгоритмов дискретных линейных преобразований (ДЛГТ) . Разработаны алгоритмы унитарных ДЛП, реализующих заданные преобразования в рамках единого итерационного процесса как укрупненных макроопераций, а также модифицированный алгоритм ОДКП «сквозной» обработки изображений. Благодаря уравниванию времен решения прямой и обратной задачи в процедуре обобщенной линейной фильтрации, разработанный алгоритм позволяет объединять систолические процессорные блоки прямого и обратного ДКП. Проведено сравнение полученных алгоритмов и оценка характеристик специализированных аппаратурных блоков, построенных на базе разработанных и существующих методов выполнения унитарных преобразований.

Основной научный результат состоит в разработке новых аппаратурно-ориентированных алгоритмов дискретных косинусных преобразований, оптимизированных под операции ЦОИ реального Бремени.

Главные теоретические и практические результаты, полученные в работе, можно сформулировать следующим образом:

1) На основе анализа задач ЦОИ (кодирование, улучшение, анализ и восстановление) и методов линейной обработки сигналов из ряда классических унитарных преобразований выбран набор универсальных преобразований, наиболее часто применяемых в области обработки изображений;

2) в результате анализа свойств и показателей качества выделенных унитарных преобразований обоснован выбор базового унитарного преобразования (ДКП) для дальнейшей аппаратурной реализации;

3) разработаны алгоритмы ДКП на основе дискретных линейных преобразований, обладающие меньшей операционной сложностью по сравнению с классическими подходами их реализации, удовлетворяющим основным требованиям, предъявляемым к аппаратурно-ориентированным алгоритмам технологией производства СБИС, и позволяющих при одинаковой производительности в 2-3 раза уменьшить время решения задачи при одновременном снижении аппаратурных затрат.

4) разработан модифицированный алгоритм ДКП, отвечающий требованиям, предъявляемым к алгоритмам ЦОС реального режима времени, обладающий высокой точностью и параллельностью вычислений;'

5) разработана методика анализа погрешностей модифицированных ДЛП алгоритмов, учитывающая характерные особенности ДЛП подхода и свойств изображений.

6) проведен сравнительный анализ аппаратурной сложности и производительности разработанных алгоритмов;

7) разработана методика проектирования вычислительной структуры ДКП по заданным входным параметрам.

Направлениями дальнейших исследований в области создания ДКП алгоритмов обработки изображений могут являться:

- дальнейшее исследование области сходимости предложенных и -известных методов, получение аналитических оценок для области сходимости, разработка способов уменьшения числа итераций ДЛП методов; исследование возможностей и особенностей применения разработанных унитарных ДЛП при решении различных задач анализа и зо бражений;

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

- разработка новых структур вычислительных устройств на базе предложенных методов ДЛП; разработка библиотеки проектов аппаратурноориентированных алгоритмов линейной фильтрации для перспективной серии ПЛИС фирмы Altera Flex 10К и подобных САПР; дальнейшее исследование «граничных» ошибок ДКП подхода блочной обработки изображений с целью модификации алгоритма и устранения их влияния на качество воспроизведется подвижных картин.

1. Сверхбольшие интегральные схемы и современная обработка сигналов: Пер. с англ./Под ред. С.Гуна, Х.Уайтхауза, Т.Кайлата.- М.: Радио и связь, 1989.- 472с.:ил.

2. Кун С. Матричные процессоры на СВИС: Пер. с англ.- М. : Мир, 1991.-672с.

3. Систолические структуры: Пер. с англ./Под ред. У.Мура, Э.Маккейба, Р. Уркхарта.- М.: Радио и связь, 1993.-416с.

4. Духнич Е.И. Синтез класса алгоритмов и вычислительных структур для реализации дискретных линейных преобразований. Диссерт. На соискание уч. степени д.т.н., Таганрог, 1985.- 306с.

5. Voider J.Е., The CORDIC Trigonometric Computing Technique.// IRE Trans. On Electronic Computers. 1959. -Vol. EC-8 (3).- pp. 330-334.

6. Духнич Е.И., Орлов Б. К. Устройство для вычисления тригонометрических функций. A.C. 1003079 Бюллетень 9, 1983г.

7. Блейхут Р.З. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ.- М.:Мир, 1989.-448с.,ил.

8. Самарский A.A., Гулин A.B. Численные методы: Учеб. пособие для вузов.-М.: Наука. Гл. ред. физ.-мат. лит., 198 9.-432 с.-ISBN 5-02-013996-3.

9. Авторское свидетельство N 741274. Устройство для вычисления синусно-косинусных произведений. (Духнич Е.И., 14итраков В.А.).Опубл. БИ N 22.- 1980.

10. Духнич Е.И., Деревенсков С. О. ДЛП-алгоритмы многомерных вращений для СБИС-реализации // Многопроцессорные вычислительные структуры: Междуведомственный тематический научный сборник сборник.-Таганрог: ТРТИ, 1995. Вып. 15-16. с25-27.

11. Деревенсков С.О. Быстрый ДЛП-алгоритм многомерного вращения вектора /Волгоград. Гос. Техн. ун-т,- Волгоград, 1995.-4с.- Деп. В ВИНИТИ. № 2442 В95.

12. Лукьянов B.C., Тесленко A.B. Устройство ввода видеоинформации в IBM PC/AT // Автоматизация технологических процессов в машиностроении: Межвузовский сборник научных трудов Часть 1. Волгоград: Издательство ВГТУ, 1997. - с. 163-169.

13. Духнич Е.И., Тесленко A.B. Систолическая реализация модифицированного алгоритма дискретного косинусного преобразования. // Тезисы докладов I межвузовской научно14.