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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ТОЧНОЙ

МЕХАНИКИ И ОПТИКИ

л т

г - ' (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

г ^ 1397

На правах рукописи

БЕРТЯКОВ ВИКТОР АЛЬБЕРТОВИЧ

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

Специальность 05.13.13 - Вычислительные машины, комплексы,

системы и сети.

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

С.-Петербург - 1997

Работа выполнена в Санкт-Петербургском Государственном Институте Точной Механики и Оптики (Техническом Университете)

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

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

доктор технических наук, профессор Фомичев B.C. кандидат технических наук,

старший научный сотрудник Вишняков Ю.М.

Ведущая организация - НИИ телевидения

(С.-Петербург)

.г- /<ГЮ

Защита состоится " ^ " А Уу 1997г. в ^_ часов на заседании

специализированного совета К05326.04 при Санкт-Петербургском Государственном Институте Точной Механики и Оптики по адресу: 197101, Санкт-Петербург, ул. Саблинская, 14.

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

. Ь п уллсу

Автореферат разослан " " ^^Т 1 ^ 1997г.

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

I

совета к.т.н., доцент ъ ииЛ'ь' Поляков В.И

I. ВВЕДЕНИЕ .

Актуальность проблемы. Методы цифровой обработки изображений (ЦОИ) в настоящее время применяется во многих областях науки и техники.

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

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

Как правило, подобные системы содержат технические средства предварительной (или первичной) обработки символьной информации и специальные технические средства для вторичной обработки символов.

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

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

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

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

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

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

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

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

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

В соответствии с поставленной целью основными задачами работы являются:

• развитие алгоритмов спектральной обработки сигналов на предмет:

О установления взаимосвязи между двумерным ДПФ и двумерным

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

• разработка методики вычисления свертки/корреляции на основе модифицированного ДПХ;

• развитие конвейерных разрядно-срезовых алгоритмов нелинейной и линейной фильтрации;

• развитие методов конвейеризации спектральных и корреляционных алгоритмов

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

• разработка структур конвейерных процессоров на основе базовых модулей для реализации модифицированных алгоритмов:

О быстрых спектральных преобразований Фурье и Хартли; О модифицированного ДПХ; О свертки-корреляции;

О обобщенных разрядно-срезовых алгоритмов ранговой и линейной фильтрации

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

Научная новизна работы.

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

• разработан алгоритм корреляционного распознавания сигналов, реализуемый на основе двумерного модифицированного преобразования Хартли;

• разработаны модификации разрядно-срезового алгоритма ранговой фильтрации с последовательным маскированием, а также разрядно-срезового корреляционно-разностного алгоритма;

• разработан конвейерный корреляционно-разностный алгоритм сравнения объекта с эталоном по проекциям;

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

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

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

• предложены схемо-технические решения основных блоков конвейерных процессоров обработки и распознавания сигналов;

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

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

Основные результаты работы внедрены в ЛОНИИС (г. С.-Петербург), БГТУ и в ИТМО.

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

1. Модифицированный разрядно-срезовый алгоритм ранговой фильтрации с последовательным маскированием по фрагментам окна сканирования.

2. Модифицированный разряцно-срезовый алгоритм двумерной свертки с учетом осесимметричности ядра.

3. Алгоритм корреляционно-разностного распознавания символов на основе анализа проекций.

4. Методика корреляционного распознавания сигналов через модифицированное двумерное преобразование Хартли.

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

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

По теме диссертации опубликовано 4 работы. Структура и объем диссертации-

Диссертация состоит из введения, четырех глав, заключения и списка

литературы. Рукопись содержит_страниц текста,_рисунков и_таблиц.

Список литературы включает 93 наименования.

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

Во введении обосновывается актуальность темы диссертации, формулируется цель и задачи исследования.

Первая глава посвящена анализу методов и аппаратных средств обработки и распознавания сигналов.

Рассмотрены основные этапы при обработке и распознавании сигналов. Отмечается, что в общем виде задача автоматического распознавания образов формулируется так:

• множество подлежащих обработке изображений разбивается на конечное число классов, называемых образами;

• устройство распознавания (ЭВМ) должно принять решение к какому классу относится тот или иной объект.

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

На этапе предварительной обработки выполняется:

• подавление шума

• подавление помех

• локализация символов.

На этапе вторичной обработки решаются задачи:

• устранение геометрических искажений

• улучшение качества

• сокращение информационной избыточности

• собственно распознавание

Далее рассматриваются методы предварительной обработки сигналов, к которым относятся:

• линейная свертка (линейная фильтрация);

• ранговая фильтрация и взвешенная ранговая фильтрация (нелинейная фильтрация);

• эквализация гистограмм (нелинейная фильтрация).

При рассмотрении алгоритмов линейной фильтрации отмечается, что важное место среди них занимает операция перемножения матриц одинаковой размерности: ZN = ВМХМ, где и Xм исходные матрицы порядка И, а - результирующая матрица того же порядка. На данной основе выполняются процедуры линейной фильтрации двумерных сигналов, сводящиеся к вычислению функций двумерной апериодической свертки или корреляции

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

Первый тип архитектуры системы обработки видеоинформации предусматривает построение конструктивно законченного блока. Как правило, такой блок имеет модульную структуру и строится на базе специализированных СБИС (например, на основе БМК), что позволяет обеспечить аппаратную реализацию подлежащего исполнению алгоритма и оптимизировать структуру аппаратных средств под особенности алгоритма. К этому направлению можно отнести системы Series-151 и MaxVideo. В ряде случаев такие процессоры могут программироваться в целях выполнения тех или иных функций, как, например, WARP-процессор. Отличительной чертой такой архитектуры является наличие отдельных магистралей ввода/вывода данных и возможность автономного функционирования. Блок со спецпроцессором при этом может быть выполнен в стандартном конструктиве типа VME, САМАС, Multibus.

Второй тип архитектуры представляет собой ПЭВМ со специализированным сопроцессором в виде платы, подключаемой к магистрали ПЭВМ и конструктивно встраиваемый в ее корпус. Примером такой архитектуры могут служить наборы модулей фирмы Data Translation на базе сигнальных процессоров типа TMS и платы-акселераторы типа В008 фирмы INMOS на базе транспьютеров Т800. Указанные технические средства ориентированы на использование в качестве периферийных спецпроцессоров для построения систем на базе IBM PC/AT. Спецпроцессор, входящий в эту систему, имеет, как правило, конвейерную структуру и может выполнять процедуры обработки изображений, требующие больших вычислительных затрат в реальном масштабе времени. Выполнение тех или иных конкретных алгоритмов обработки видеоинформации производится программированием спецпроцессора, что увеличивает функциональную гибкость подобных систем и расширяет области возможного применения спецпроцессора.

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

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

Рассмотрена основная элементная база для построения спецпроцессоров, представленная следующими основными типами:

• комплекты БИС и СБИС для построения сигнальных процессоров (К1815, 1843, AM29C300)

• сигнальные процессоры (K1813,npD7720,TMS32OCXO)

• транспьютеры

• базовые матричные кристаллы и программируемые СБИС

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

Описаны специализированные процессоры конвейерной и систолической архитектуры на примерах WARP-процессора, операционных автоматов с жесткой логикой, структур с ортогональными связями между вычислительными ячейками (GAPP, МРР, DAP, АРР), линейно-последовательным типом связей (ISP), а также полу систолической конвейерной матрице TDC 1028.

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

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

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

Хн = [Х{1),Х(2\Х{3\... X{N)]

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

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

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

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

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

распространенных процедур как ВРФ, СЭГ и двумерная свертка при помощи разрядно-срезовых методов.

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

текущей суммы, которая принимает вид : В = + X X Znп & Ьчтп)

т п

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

п. Если Zmn = {ОД}, то выполняется процедура ранговой фильтрации с произвольной формой окна.

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

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

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

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

Матрица ядра свертки задана как (г — |&т)„||- Столбцы матрицы С обозначены как gn , а столбцы полосы изображения как Xj . Результатом обработки столбца является сумма пяти произведений Хт у-и g , представляющая собой

скалярное произведение векторов gn и Xj обозначаемая через gn X^ .

Результатом вычисления свертки является величина у! = 2 >

соответствующая отсчету свертки с номером .¡, расположенному в средней строке полосы шириной М.

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

Вычисление свертки при симметрии матрицы в относительно средней строки позволяет уменьшить размерность матрицы в до М(М+1)/2, что ведет к существенному сокращению вычислительной сложности алгоритма.

В ряде случаев ядро свертки может содержать вырожденные строки матрицы в, т.е. строки, содержащие только нулевые элементы. Очевидно, что при

формировании скалярных произведений векторов вида gn X] эти строки можно

не учитывать, благодаря чему требуется не (М+1)/2 базовых операций, а (М+1-1)/2 базовых операций, где 1 - число нулевых строк.

Если ядро свертки обладает симметрией не только относительно центральной строки, но и симметрично относительно центрального столбца, то для формирования каждого отсчета свертки достаточно вычислить только

(М+1)/2 скалярных произведений вида Xj , а не М скалярных

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

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

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

Под проекцией символа (или эталона) на ось X понимается вектор, каждый элемент которого равен сумме единичных бит в соответствующем столбце битовой карты, а под проекцией на ось У - вектор, каждый элемент которого равен сумме единичных бит в соответствующей строке битовой карты:

Рг X = [ргХ0, ргХх, ргХг,..., ргХм] Рг Г = [рг¥„ргГ1,ргГ2,...,рг¥м] Рг Рг Г,. =

Функция сходства проекций определяется как:

= 2|Рг*, -РгХ,*| (

= Е|РгГу-РгГ/|

/

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

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

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

Qce= 2N2 log2 N + N1 = JV2(21og2 N+ 1)

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

размерностей М и N: М < 7(2 log2 N + 1)

Рассмотрено применение специального или модифицированного преобразования Хартли, в котором искусственно выполнено разделение ядра по координатам:

Н"и = llxnricas(2xkm / N)cas(2n\n/ N)

л т

для вычисления двумерной свертки/корреляции.

Установлена взаимосвязь между традиционным двумерным

преобразованием Хартли и модифицированным преобразованием Хартли.

Ны = [нк1 + #*,_/ + H_kJ - Н_к<_, ] / 2

где в силу цикличности ядра (N-k)modN = -k; (N-l)modN = -1.

От компонент спектра Хартли можно перейти к компонентам спектра Фурье, используя известное соотношение:

Связь между компонентами спектра Фурье и компонентами модифицированного преобразования Хартли:

ра = {[я;,., + н:„\- j[Hi, - / 2

Если Х_„ = Х„ . Тогда:

Нц = Нк , Н_к = Н_к1 \Н к1 = Нк1

Fkl = {[Hi, + j[Hl, - н:к;}} / 2.

Если Хтп = Х_тп = Хт_п, то как преобразование Хартли, так и преобразование Фурье эквивалентны модифицированному преобразованию Хартли: Н ы = Я*; Fkl = Ны

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

• вычисляется модифицированное двумерное преобразование Хартли от функции Хтп и определяется функция Н к1;

• вычисляется модифицированное двумерное преобразование Хартли от функции gmn и определяется функция Gkl;

• путем перекомпоновки матриц Нл и находятся требуемые компоненты Нк ,, Нк1, Н_к I, , ;, б^ соответственно;

• по полученным компонентам и исходным матрицам и вычисляется матрица ФЛ;

• вычисляется модифицированное двумерное преобразование Хартли от функции Ф к1.

Отмечено, что функция Ф и упрощается если ядро свертки - функция gmn

- обладает симметрией. В частности, при симметрии gnn относительно двух осей

Фи = НиОк1 т.е. процедура вычисления функции Фш сводится к поэлементному умножению матриц НЛ и вЛ.

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

• конвейеризация микроопераций (микро конвейерный уровень);

• конвейеризация типовых (базовых) операций цифровой обработки сигналов (конвейерный уровень);

• конвейеризация процедур (макро конвейерный уровень).

Уровень конвейеризации выполнения микроопераций используется практически повсеместно в современной микропроцессорной технике, позволяя совместить во времени выборку операндов из памяти, ввод исходных данных с внешних портов, исполнение арифметико-логических операций в АДУ с выводом результата во внешние порты или записью в память. Такая конвейеризация реализуется и в однопроцессорных устройствах.

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

Л = + •+Х1)К + *о. к =

Серьезным недостатком вычислений по схеме Горнера является накопление погрешности вычислений по мере формирования результата.

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

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

Л, = У/,„-1 + п = •• -1

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

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

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

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

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

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

Отмечается, что задача проектирования алгоритмов для параллельно-конвейерных систем МПУШ-архитектуры трудно формализуема. В качестве примера рассмотрена организация макроконвейерных вычислений при выполнении БПФ и БПХ.

Вычисления на каждой итерации ш {М = 3м, Ш — 1, М) можно

представить как единую процедуру:

H к,m = Hk,m-1 +

Hw cos(2idc / NJ + HrW sin(2»fe /NJ + Hk+v,m-1 cos(4/ifc / + sin(4«fc / Нк+1,т = H-k,m-\ +

cos(2/r(* / ^ +1 / 3)) + Я*.., sin(2ff(Ar / iVm +1 / 3)) + cos(2^(2к/Nm + 2 / 3)) + Я,^., sin(2Tr(2* /N.+2/З)) Hk+2l,m ~ Hk,m-l +

Я^,COS(2TT(/;/ ЛГ. + 2/ 3)) + Я^яп(2я(Л/Nm+2/3)) + Hk+2i,m-i cos(2n(2k f Nn +1 / 3)) + НрХтЛ sm{2K{2k / Nm +1/3)) Nm=3"-J = 3-1; k = «из-1 - l),j» = (s -1)/ + (l-k)modl,s = 1,3

Компоненты , Hk+j m, Hk+2I образуют подвектор длиной 3™. Так как

N = 3М, то после m-ой итерации получается 3Л/_т подвекгоров. Каждая последующая итерация объединяет 3 подвектора, полученных на предыдущей итерации.

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

Далее, в качестве приложений, в которых могут быть использованы разработанные алгоритмы, рассматриваются задачи обработки и распознавания текстовой информации, вводимой в ЭВМ в виде полутонового изображения одного из стандартных форматов TIFF, PCX или BMP, а также задача моделирования опто-электронного тракта обработки данных дистанционного зондирования. Применение алгоритма корреляционно-разностного сравнения по проекциям совместно с методикой вычисления свертки через МДПХ и обобщенным разрядно-срезовым алгоритмом ранговой фильтрации подтвердило эффективность предложенных средств для решения данных задач.

Третья глава посвящена рассмотрению базовых вычислительных средств на основе транспьютеров для обработки и распознавания сигналов.

Рассмотрен один из отечественных перспективных СБИС - процессорный элемент транспьютерного типа (условно называемый сигнальным транспьютером СТ). СТ предназначен для построения асинхронных параллельно-конвейерных систем и обладает следующими основными техническими характеристиками: максимальная производительность - 100 Мфлоп/с(мантисса т=12), либо 25 Мфлоп/с (мантисса т=24); поддерживаются форматы данных действительные, с плавающей точкой, комплексные с плавающей точкой; объем внешней памяти до 4 Гслов (32-разрядные);

интерфейс внешней памяти - стандарт EMI (совместим с Т800); существует встроенный контроллер статической и динамической памяти; пропускная способность интерфейса внешней памяти - 40 Мбайт/с; интерфейс внешних портов - шесть параллельно-последовательных двунаправленных байтовых портов с обменом словами и массивами в режиме прямого доступа с пропускной способностью до 20Мбайт/с; объем внутренней памяти: 128 слов векторной памяти с возможностью расширения, плюс память программ 256 слов с возможностью расширения до 4Г слов. Система команд ориентирована на выполнение скалярных и векторных арифметико-логических операций, вычисление элементарных и тригонометрических функций, выполнения БПФ, поворота вектора и других преобразований, операций управления вычислительным процессом.

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

По своим функциональным характеристикам модули делятся на:

• вычислительный модуль (ВМ) для выполнения с высокой производительностью арифметических операций. ВМ является основным вычислительным блоком в составе спецпроцессоров и в рассматриваемом варианте имеет максимальную (пиковую) производительность до 100 Мфлоп/с при максимальной пропускной способности по каналам ввода/вывода до 260 Мбайт/с.

• модуль глобальной памяти или буферный модуль (БМ). Модуль является основой для построения буферной памяти или различных типов ОЗУ большой емкости и обеспечивает максимальную производительность до 50 Мфлоп/с при максимальной пропускной способности по каналам ввода/вывода до 40 Мбайт/с.

• модуль управления (МУ). На основе такого модуля организуется управление спецпроцессорами и приборами предварительной обработки сигналов.

• модуль источника питания (МИП) предназначен для энергоснабжения модулей в составе конвейерных систем.

• модуль преобразования форматов (МПФ) содержит в своем составе конвейерное устройство, осуществляющее преобразование данных из формата с фиксированной точкой, поступающих от приемных устройств в формат данных с плавающей точкой, который является основным для СТ. Кроме того, модуль осуществляет преобразование многоразрядных слов в последовательность байтов, обеспечивая тем самым соответствие данных, передаваемых по LINK-каналам, интерфейсу LINK-портов сигнального транспьютера.

В качестве примера применения описанных модулей рассмотрена структурная схема типового конвейерного процессора, ориентированного на выполнение векторных и матричных процедур (векторный процессор - ВП). Далее, развивая макроконвейерный принцип обработки, рассмотрено устройство ЦОС, построенное на основе ВП и ориентированное на нахождение обратных

матриц и решения СЛАУ. Отмечается принципиальная пригодность предложенных структур для реализации также корреляционно-разностного алгоритма распознавания символов по проекциям.

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

(для N — Гт). Устройство содержит Ш = N ВМ. В качестве базовых операций, выполняемых в ВЯ приняты: поворот вектора результатов Ьой

итерации:^ = где X = , Хх, Х2,. .., Л^] - вектор из г

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

отсчетами вектора X*: = ЕГХ \ где ¥ = [/0 ,/, ,/2 .. ,/,_15] -

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

При работе устройства в каждой ВЯ можно выделить следующие циклы:

• загрузка N исходных данных (или N отсчетов промежуточных результатов), занимающей N тактов;

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

• выдача результатов итерации в следующий ВЯ, которая длится те же N тактов.

Анализ временной диаграммы работы конвейера из т ВЯ в установившемся режиме (для N=8, г=2) показывает, что на выполнение БПФ одной группы данных потребуется ш макротактов, т.е. ш(Ы+4) тактов и N тактов на вывод результатов БПФ из последней ВЯ.

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

Далее рассмотрены особенности реализации конвейерного процессора БПХ по основанию г. Процессор содержит М одинаковых последовательно соединенных каскадов МС, причем каскад с номером т реализует т-тую итерацию БПХ. Каждый каскад разделен на два параллельно синхронно

функционирующих канала - канал МС3 для формирования синусных

составляющих и канал МСс для формирования косинусных составляющих. В свою очередь, МСs и МСс каждого каскада представляют собой устройство для выполнения r-точечного соответственно косинусного или синусного преобразования и состоят из г вычислительных ячеек (ВЯ). Сложение синусной и косинусной компонент результата m-й итерации алгоритма БПХ реализовано в последнем каскаде. Более общий случай процедуры БПХ, когда N = ГХГТ .. Гт.. .Гм также будет иметь M итераций, причем на ш -ой итерации выполняется Гт - точечная бабочка. Величина 1 здесь принимает значение / = NтА — Г^-- • гм-\ > а величина к изменяется от 0 до N-1. При этом предварительная перестановка исходных данных, необходимая до выполнения первой итерации, как и в процедурах БПФ, определяется не только сомножителями г , но и порядком их следования. После перехода от компонент преобразования Хартли к преобразованию Фурье, выполняемого отдельно, формируются окончательные значения действительной и мнимой части результата.

Произведена оценка временных и технических характеристик реализации процессора БПФ с ориентацией на применение СТ с развитой арифметикой в режиме плавающей запятой и максимальной производительностью Р=10оп/с. Время 7J выполнения процедуры БПФ на процессоре с производительностью Р

^ N(3 + 5 log, N)

равняется 1 j =-—-. Для N=16384 Q=114688 операций "бабочка",

Т'1=1,196мс. Время Т2 выполнения процедур БПФ на одном сигнальном

транспьютере: Т2 = ГБПФ + Тш + Ты, где Tbm = (N / 2 * log2 N)tbase;

Tin = Тш = N * t , где t - время передачи слова по каналу связи; N - число

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

т = т +т

х бпф ^ ■'out-

Число S сигнальных транспьютеров, требуемое для построения процессора БПФ: S = int(r2 / Тх) + 1, где int(x) - операция выделения целой части х.

Исходя из соотношений, для достижения максимальной

производительности (Р - 109 оп/с) процессор БПФ должен включать в себя 4 ВМ на основе СТ работающих параллельно.

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

т* N *

строчно-столбдового алгоритма БПФ. Для случая N = 128, когда все промежуточные результаты находятся в векторной памяти СТ, общее время

а/-1

преобразования составляет: Т = N * Д/п + £ Тт = 2,8 * 10" С Расчеты

т=1

показывают, что система, состоящая из М параллельно работающих СТ, когда "накачка" данных в (т+1)-ый СТ осуществляется на фоне работы ш-го СТ, является более высокопроизводительной (ш=1,М-1) по сравнению со структурой чисто конвейерного процессора БПФ без "накачки" данных между ступенями, для которого время аналогичного преобразования составляет

2 ^ьше + ~4*10~4С. Далее кратко представлены

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

Затем рассматривается конвейерный процессор свертки/корреляции через модифицированное двумерное преобразование Хартли (МДПХ). Основу процессора составляют два независимых процессора МДПХ, соединенных последовательно через блок весовой обработки. Каждый из таких процессоров

является многокаскадным устройством, реализующим вычисление На либо непосредственно через двумерное преобразование при малых размерах кадра изображения, когда его размер по каждой координате задан простым числом, либо через быстрое преобразование Хартли по каждой координате. В состав блока весовой обработки входит ОЗУ весовой функции, ОЗУ спектральных компонент, четыре умножителя и многовходовой сумматор.

ОЗУ весовой функции имеет четыре блока БЩ - БЩ, в которых хранятся компоненты весовой функции ОЗУ спектральных компонент также имеет четыре блока БП| - БП4 , однако каждый блок выполнен двухсекционным. Запись спектральных компонент выполняется в блоки синхронно и в естественном порядке поступления данных из первого процессора ДПХ, а порядок следования считываемых из блоков данных отличается от порядка их записи, что обеспечивает необходимую перестановку компонент матрицы. С выхода блока весовой обработки отсчеты функции Фл поступают на вход второго процессора ДПХ.

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

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

Подобные системы характеризуются большой гибкостью, широкими функциональными возможностями, живучестью за счет возможности параллельного резервирования процессов, а также производительностью, которая при производительности ВЯ конвейерных процессоров порядка 10& базовых операций ( или длительности такта конвейера порядка 10 нсек), числе ВЯ в каждом процессоре до 100 и числе таких процессоров в пределах от 10 до 50 составляет Р^ < 5 * 1011 базовых операций в секунду. Такая производительность достаточна для обработки сигналов в реальном времени во многих важнейших научно-технических и народнохозяйственных задачах.

В заключении приведены основные результаты работы.

III. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

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

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

3. Разработана методика вычисления свертки/корреляции через модифицированное преобразование Хартли.

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

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

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

Список работ, опубликованных по теме диссертации:

1. Бертяков В.А., Тропченко А.Ю. Конвейерный процессор для обработки изображений. Тезисы докладов Международной научно-технической конференции "Новые информационные технологии и системы". Пенза, 20-21 декабря 1994 г., - Пенза, ПГТУ, 1994, стр.

2. Бертяков В.А., Звездин Д.И., Тропченко А.Ю. Высокопроизводительные аппаратные средства для цифровой обработки изображений. Депонированная статья в ВИНИТИ № 1194-В95 от 26.04.1995, - 17 стр.

3. Бертяков В.А., Романов Ю.Ф., Тропченко А.Ю. Вычисление свертки на основе модифицированного двумерного преобразования Хартли. Депонированная статья в ВИНИТИ № 1085-В95 от 19.04.1995, - 12 стр.

4. Бертяков В.А..Тропченко А.Ю. Конвейерный процессор быстрого преобразования Хартли. Тезисы докладов II Межведомственной научно-технической конференции "Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах", Часть 1; - Пушкин, 1995, стр. 99-100.