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

•6 ОА

НШОНАЛЬЖЯ АКАДЕМИЯ НАУК АРМЕНИИ

я А П г Ш93

- " ИНСТИТУТ ПРОБЛЕМ ИНФОРМАТИКИ № АВТОМАТИЗАЦИИ

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

удк 681.325.5:681.327.12.001.362

БАБАЯН КАИРА АРЩ^УНОВНА

СИНТЕЗ И АНАЛИЗ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ, УЧИТЫВАЮЩИХ "ПСИХОФИЗИЧЕСКИЕ" СВОЙСТВА ЗРЕНИЯ, И ИХ ПРИЛОЖЕНИЕ В СЖАТИИ ИЗОБРАЖЕНИЙ

05-13.16. - применение ВТ, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

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

Ереван - 1993г.

Работа выполнена в Институте Проблем Информатики и Автоматизации Национальной Академии Наук Армении.

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

профессор Агаян G.G.

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

член кор. Инженерной Академии РА

Мкртчян С.О.

кандидат технических наук

Арутшян Г.А.

Ведущая организация: Институт радиофизики « электроники , Национальной Академии Наук Армении .

<ир®э шя ра)

Защита состоится ^_"_ 1993 г. в _ часов

на заседании специализированного Совета к 005.21.01 при Институте проблем информатики и автомати^цаи Национальной Академии Наук Армении по адресу: 375044, Ереван-44, ул.Севака,1.'

С диссертацией можно ознакомиться в библиотеке Института проблем информатики и автоматизации ШН РА.

. Автореферат разослан »_"_ 1993 г.

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

Совета к 005.21.01 У?. V/iftfe^---—\

доктор физ-мат. наук, профессор Агаян С.С.

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

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

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

В настоящее время большое внимание уделяется построена ортогональных преобразований с заранее заданный сзо£ствамй, 2 том числе структурой ортогональных матриц, основанных тгкгз л на особенностях человеческого зрения. Так, в работах Ля, вззлэ-по-преобразование, учитывающее психофизические свойства зр:нпя, хорошо отобракающее свойство потери чувствительное?:! л остропг зрения, начиная от "центра" изображения к пзркЗярст, когсрсе позволило разработать алгоритм улучшения соотнозекия спгзая/гум при передаче изображений". Однако, матрицы предлоги елого прзс-5-разования не являются ортогональными. Хороио известно, т:о последнее условие позволило бы, в частности, обеспечить суг'-с-:-вование обратного преобразования, построить эфВектпвшй з,тс-ритм его вычисления, сохранить определению фгзичостгэ сигналов при обработке. Естественно, возникает вопрос построения класса быстрых ортогональных преобразований, утлгтааггг.гз.

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

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

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

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

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

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

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

а) вводимый класс преобразований, 0) предлагаемые системы сжатия изображений.

Научная новизна. Введены и изучены классы ортогональных матриц с различными структурными свойствами (центрированные, (m,t)-центрированные, со смещенным центром и многоцентрирован-ные) соответствующие психофизическим особенностям человеческого зрения; параметрическое (га,t)-центрированное преобразование; предложены алгоритмы их. построения; разработаны быстрый последовательный (требующий, вместо 0(MZ), o(MiogM) арифметических операций) и параллельный (соответствующий моделям PRAM и SIMD) алгоритмы вычисления преобразований по построенным матрицам. Разработаны алгоритмы сжатия сигналов, на основе введенных преобразований; на сигнале - кардиограмме показана их эффективность (в смысле точности и скорости) по сравнению с использованием таких "классических" ортогональных преобразований, как

s

преобразования-Уолта, Хаара, косинусное преобразование. Разработана архитектура специализированного/последоЪзтельного (унифя-цированного) и параллельного (с модульной структурой) процессоров, эффективно реализующих введенные преобразования; предложена система сжатия изображений на основе архитектур разработанных процессоров.

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

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

Апробация работы. Основные положения и результаты работы были доложены и опубликованы в тезисах докладов: 1_ Всесоюзной конференции по распознаванию образов и анализу изображений РОАИ-1-91 (Минск, 1991), конференции по проблемам создания систем обработки и анализа изображений (Ташкент, 1992), конференции по однородным вычислительным средам и систолическим структурам (Львов, 1992), на открытых семинарах ИПИА АН РА, ЕрПИ и МШЖ.

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

Структура работы. Диссертация состоит из введения, трех глав, списка литературы, включающего 79 наименований, приложения и изложена на ^/¿'•страницах.

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

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

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

В 51 и дан краткий обзор областей применения дискретных ортогональных преобразований и их преимущества. Показаны важность и необходимость построения ортогональных матриц, основываясь на особенностях человеческого зрения. При этом приводится математическая постановка исследуемой в диссертации задачи, а шенно: Пусть на изображении размера 2Н*2М выделено некоторое множество элементов (Е - множество индексов этих элементов). Необходимо построить ортогональную квадратную матрицу А порядка 2и так, чтобы при стремлении к заранее заданному множеству Е абсолютные значения этих элементов возрастали.

В последующих параграфах изучены честные случаи приведенной задачи при различных расположениях Е.

В §1.2 введены понятия центрированных и (тД)-центрированных матриц, соответствующих случаю, когда множество Е расположено в центре матрицы.

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

Пусть матрица а удовлетворяет условиям:

а) существуют индексы 11,12,...,1т (ск^<N-1; к=Т7т; 1 <ш<н) такие, что для всех 1=1к,1к+1,...,я-1

|51 ,1 = 1в(. при 1+л=1к+Ы-1

к

(в дальнейшем строки 11,1г,...,1т будем называть строками сохраняющими условие ганкелевости);

б) существует возрастающая по абсолютным значениям последовательность из 1-а<т элементов на пересечении последнего столбца матрицы сит строк сохраняющих условие ганкелевости.

Определение 1.2.1. Квадратную матрицу О порядка N. удовлетворяли-» вышеуказанным двум условиям, назовем (ш,^)-ганкелевой матрицей.

к

Пример 1-.2.1. (4,4)-ганкелева маафица порока 4.

8 6 -12 1

~Э 0 1-2

5-1-2 3

-1 2 3-4

Определение 1.2.2. Квадратную матрицу А=[а1 (1,Д=575РРГ) порядка 2Н, симметричную ' относительно главной диагонали и зеркально-симметричную относительно оси абсцисс и оси ординат по модулю элементов, назовем зеркально-симметричной матрицей.

Другими словами, матрица А=[а1 ..] ¿=б,2Я-1) зеркально-симметричная, если она удовлетворяет*следующим условиям:

|а | = |а. .|

lav.2N-i-J

' a2N- i - i , j ' " "ai.jl

i,i = O.H-1

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

G GR

А =

-RGR

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

'.о о.....1

о 0...1 о

R

.0 О

Определение 1.2.4. Зеркально-симметричную матрицу А порядка 2N, верхний левый квадрант G которой является (иД)-ганкеле-вой матрицей, назовем (m.t)-центрированной матрицей.

(и,N)-центрированную матрицу назовем просто центрзровгпной: матрицей.

Определение 1.2.3. Матрицу н , полученную мз Н стиранием

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

а - верхний левый квадрант матрицы А - может быть и ядром-(т,Ю-ганквлевой матрицей.

Пример 1.2.4. Ортогональная центрированная матрица ка пйрядка 6.

' 1.5 3 1 1 3 1,5 -3 1 1.5 1,5 1 -3

"3—Т

1 -1,5 3|-1.5 1

1 -1,5 I 3 -3 I 1,5 -1

-3 1 1.5 -1,5 -1 3

1.5 3 1-1-3 -1,5

В матрице Ав б качестве матрицы с взята (3,3)-ганкелева матрица

1,5 3 1 6(3.3) = -3 1 1.5 1 -1.5 3

Приводятся алгоритмы построения ортогональных центрированных матриц.

Утверждение 1.2.1. Пусть о - ортогональная ш.Ю-ганкелева матрица (с ядром-(М,ы)-ганкелевой матрицей) порядка N (порядка (м+1)). Тогда матрица А вида (1.2.4) является ортогональной центрированной матрицей порядка 2М (порядка 2(м+1)).

В §1.3 предложены алгоритмы построения (ш, 1;)-центрированных ортогональных матриц при 1<ю<н и кит, оснсвывашше на следующих утверждениях.

Утверждение 1.3.1. Пусть с - ортогональная (N,1)-ганкелева матрица порядка N. Тогда матрица А, определенная по (1.2.4), является ортогональной (Ы, t Ьцвнтрированной матрицей.

Утверждение 1.3.2. Пусть матрица А-ортогональная центрированная матрица порядка вида (1.2.4), а в - ортогональная (Нг,Ы2)- ганквлева матрица порядка л2. Тогда матрица с

с =

С » В

о ® яв

в в ви С в ивя

является ортогональной (т,г)-центрированной матрицей порядка Н, где пр^г^+г^-!, н=2Г11Ыг.

Пусть БХ(а,в,с,0 и П(а,в,с,в,е,р,о,н) - массивы Бомера-Холла и Плоткина соответственно, т.е.

а в с d

бх(а,в,0,е) — -в а —d 0

—с . d А -в

• —d -с в а

а в с d е р 5" н

-в а d -с р -в -н g

-с -d а в g н -е -р

n(a,b,c,d,e,p,g,h)= —d с -в а н -g р -е

-е -р -g -н а в с d

-р е -н g -в а d с

-g н е -с d а -в

-н -g р- е -d -с в а

Согласно теореме Бомера-Холла, если к - квадратные матрицы порядка d, удовлетворяющие условиям:

к. к] = к к* и ¿к к] = rpin , где 1,з = TT?', р>л, г = 4,8, - j=»

то BX(KlfK2,K3,K4) и П(кл,к2,кэ,к4,кэ,кв,к7,кв) - ортогональные матрицы.

Пусть к-(mt ,t. )-ганкелевы матрицы порядка d (i=TTr;r=4;8), удовлетворяющие вышеприведенным условиям, а t*=ST3 зависит от значений элементов первых строк и последних столбцов матрицы Утвергдение 1.3.3- Пусть g = П <kt ,к2 ,кз ,к, ,к3,ка,к7дв) или о = БХ (Kt ,к2 ,кэ.к4)- ортогональные матрицы. Тогда матрица А, определенная по (1.2.4), является (т.г)-центрированной матрицей порядка 2rd, где m=mi+log2i- ; t=tt-t-t*.

Пусть А - ортогональная центрированная матрица порядка 211, э - символ кронекеровского произведения, Wn - матрица Уолаа порядка гп, т.е. ... : • - • ,

1 1 * 1 -1

Утверждение 1.3.4. Матрица, а м гп вида:

А = A,® w

П Г)

N. 2

является ортогональной (m*,t*)- центрированной матрицей порядка US"*1. ГДв t=t*i ro*=m+2n-1.

Пример 1.3.2. (3.2)-центрированная матрица ав порядка 8, построенная из матрицы G с ядром - (з,2)-ганкелевой матрицей.

111 •о о -1 а -с -1 О а 1

0 а -1 а -с 1 -с 0 1

1 1 -1

где а = и о = - являются числами Фибоначчи.

В §1.4 рассмотрены смещенные (го,t)-центрированные, смещенные центрированные (соответствующие случаю, когда в ортогональной матрице множество Е расположено в произвольном месте) и многоцентрированные (соответствующие случаю, когда в ортогональной матрице несколько множеств Е) матрицы.

Предложены алгоритмы построения ортогональных матриц рассматриваемых классов.

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

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

_ 1

1 1 1. 1 1

1 О о а -а

1 с -а О О

1 а О

1 -а О

1 -с а О О

1 О -с а а

1-1-1 1 -1

-с -о -с с

при стремлении к которым абсолютные значений элементов возрастают.

Пример 1.4.1. Смещенная центрированная матрица в порядка 8.

в =

1 2 2 1 -4 3 3 -4

-2 -3 -3 . -2 1 4 4 1

-3 4 4 -3 2 1 1 2

-3 4 -4 3 -2 -1 1 2

-2 -3 3 2 -i -4 4 1

1 2 -2 -1 4 -3 3 -4

4 1 -1 -4 -3 -2 2 3

4 1 1 4 3 ч2 2" 3

В §1.5 рассмотрены параметрические (т.Ю-центрированные ортогональные преобразования, синтезируемые матрицами а , элементы которых являются параметрами, при любых значениях которых сохраняется (т, г ¡-центрированная структура. Матрицы а ^ порядка 2" строятся на основе (тД)-ганке левых параметрических матриц в :

а = а . (е., е,

раг к г 1 * 2

2 ,2

9к; v 1г,.

V

с н

раг

Ей -ЙО И

Р'аг раг

а И

где ?/2г - матрица Уолша-Адамара порядка г*, э - является кро-некеровским произведением ортогональных матриц второго порядка, соответствующих различным углам и направлениям поворота в ; и 1<^<4 (3= ТТк).В зависимости от 8.и д.. строится класс матриц одинаковой (тД)-центрированной структуры.

В §1.6 разработан быстрый алгоритм вычисления (тД)-центрированных (центрированных) ортогональных преобразований.

Алгоритм основан на факторизации матрицы преобразования вида (1.2.4).

= (а © i « xi,

[ п в ^ о )]).

А =

(I2® G)(Wt® 1N)

Утверждение .6.2. Предложен алгоритм вычисления (шД)-центрированного преобразования с матрицей А, определенной по (1.з.^о), требующий ИАку) и ) операций сложения и умножения

соответственно, где

ц( А )=2Ип2п+2п(ги+^(а))=2"/гл'(п+1 )+ц.(й))

мл"

г>(А п

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

В частности, если G - ганкелевая или обратно-циклическая матрица порядка 2'", то преобразование с матрицей аы обладает быстрым алгоритмом вычисления, т.е. требует

= N ( п + 5 + 6aiogN )

v(ANi2n) = N ( 5 + epiogN )

если G - ганкелера матрица и

H(AN2n) = 2" N ( 2п + 4 + 3alogN ) V(AN_2n) = N ( 1 + 3plogN ) .

если G - обратно-циклическая матрица.

На рис. 1.6.1 представлен граф быстрого вычисления (m,t)-центрированного ортогонального преобразования по произвольной матрице А вида (1.2.8) порядка к=8.

В § 1.7 разработан параллельный алгоритм (m,t)-центрированных преобразований. Алгоритм реализуем как в модели PRAM (Parallel Random Access Machine), так и В модели SIMD (Single Instruction-Multiple Data).

Предложенный алгоритм является по порядку оптимальным по ускорению и эффективности, т.е.

где

5k(N)=0(K), (Ek (Ю=0(1 )),

Т. (Ю

'Sk(N) = ~чггт i К к 4

ъ ъ"««.

0)

Рис.1.6.1. Графы быстрых алгоритмов вычислений: а) центрированного преобразования для порядка N=8; б) преобразования по матрице 0.

Sk(N) Tt(N)

--г™'=тпгш-к

- критерии ускорения и эффективности соответственно; к - число процессоров системы, N - характерный размер задачи (в' данном случае - длина входной последовательности), Tl(N) и тк(Н)-время реализации (число шагов) последовательного и параллельного алгоритмов соответственно.

Вышеуказанный алгоритм по быстродействию превышает быстрый последовательный алгоритм пропорционально числу используемых процессорных элементов)

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

В главе 2 разработаны и программно реализованы алгоритмы сжатия одномерных и двумерных сигналов посредством введенных в первой главе ортогональных центрированных и (m, t)-центрированных преобразований.

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

Пусть х = (xQ,x1,...,xN_1) - случайный вектор с нулевым средним и с ковариационной матрицей R, а т - некоторое фиксированное целое число (KmN), S(m) - матрица выбора размера m*n.

Необходимо найти такое ортогональное преобразование с матрицей н и такую матрицу выбора спектральных коэффициентов s(m),

р(х,Н S S3X) = р-(х,х ) -► min ,

где р - метрика (среднеквадратическое отклонение).

Общая схема кодирования сигналов (изображений) посредством ортогональных преобразований приведена на рис. 2.1.1.

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

Эксперименты проведены на симметричных сигналах и сигналах-кардиограммах. Произведенное сжатие показало, что алгоритмы сжа-

14

Рис. 2.1.1.

тия посредством "психофизических" преобразований точно восстанавливают симметричные сигналы. Эксперименты на сигналах-кардиограммах показали,что для различных коэффициентов сжатия (равных 2, 2.2, 4 и 8), "психофизические" преобразования в смысле среднеквадратичной ошибки имеют лучше показатели, чем "классические" преобразования Уолаа и Хаара.

В таблице 2.2.1 приведены значения среднеквадратических отклонений сжатия изображений при использовании преобразований Уолша, Хаара и "психофизических" преобразований (например, для коэффициента сжатия ш=4 значения среднеквадратических отклонений сжатия изображений при использовании преобразований Уолша, Хаара и "психофизических" преобразований равны соответственно 8^4.517, 8Н=4.628 И £р=4.387).

Таблица 2.2.1.

Среднекваратические отклонения

Коэф-т сж. пр-ние Хаара пр-ние Уолша "психофиз-йе" пр~ния

2.0 2.593 2.046 1.538

2.2 3.601 3.368 2.492

4.0 4.628 4.517 4.387

8.0 7.352 7.352 7.352

В §2.3 приведены алгоритмы сжатия двумерных сигналов (изображений) с помощью "психофизических" преобразований. Эксперименты проведены на изображении томограммы сечения головного мозга человека.

Анализ реультатов экспериментов показал, что алгоритмы сжатия, основанные на "психофизических" преобразованиях превосходят по точности результаты, полученные при использовании алго-

ритмов с преобразованиями Уолша и Хаара, а по скорости-алгоритмы с косинусными преобразованиями.

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

Б §2.4 приведен алгоритм сжатия двумерных сигналов (изображений), основанный на "психофизических" преобразованиях, аналогичный алгоритму сжатия, предложенному в §2.3, с той лишь разницей, что при выборе наиболее информативных коэффициентов преобразования используются значения дисперсий.

На рис. 2.4.1 представлена диаграмма дисперсий коэффициентов двумерного центрированного преобразования по (1.3.2). Исходное изображение описывается статистически, как марковский процесс первого порядка с коэффициентами корреляции р1 и рг (р1=р^=0,95) для строк и столбцов случайных величин в обоих

Бис. 2.4.1. Матрица дисперсий коэффициентов " двумерного "психофического" пребразования

Из .представленной на рисунке диаграммы дисперсий коэффициентов видно, что "психофизические" преобразования (также, как и преобразования Уолша) обеспечивают сосредоточение энергия в-небольшом числе коэффициентов в непосредственной близости от| начала координат и и V (и и V - координаты коэффициентов преобразованного пространства (трансформанты). Это обстоятельство позволяет использовать известные метода отбора коэффициентов преобразования и в алгоритмах сжатия данных посредством "психофизических" преобразований.

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

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

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

Нэ рис. 3.2.2. приведена блок-схема данного устройства. Оно содержит блоки ОЗУ 1-3, ПЗУ 4, арифметическое устройство 5» индексные устройства 6-8, мультиплексоры 9-13, группу элементов ШМ 14, регистр адреса 15 и устройство управления, содержащее генератор синхроимпульсов 16, счетчик операндов 17 и счетчик итераций 18.

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

Рис. 3.2.2. Блок-схема однопроцессорного устройства "психофизических" преобразований

Процессор Кол - во операций Объем памяти (слов) Кол-во сумма торов Кол-во ум повителей Кол-во ре гист-ров БТ2 Выполняемые операции

Процессор 0(Шо§11) т 2 1 9 БПФ • ОБПФ БПУА свертка

Устройство для выполнения ДОП ' 0№О£Ю 2И 5 2' 8 0(Н31ов5К БПФ ОБПФ

Устр-ву.,, ДЛЯ ОП цифровых сигналов по Уолшу-Адамару ОДОоёЮ N 1 N БПУА.

Процессор "психофизических" преобразований ООПоеМ 7Н 2 2 8 0(Мэ1ов5М БПФ ОБПФ БПУА. БПХаара свертка "ПСИХО- физич." пр-ния ганкеле вые пр-ния

*) ДОГТ- дискретные ортогональные преобразования

**) ОП - ортогональные преобразования

Разработанный .процессор обладает унифицированностью, т.е. мокет работать в нескольких режимах, реализуя, кроме "психофизических", ' также и ряд "классических" преобразований - Фурье, Уолша, Хаара, преобразования по матрицам ганкелева типа и т. д. Причем, как показывает сравнительный анализ;по основным показателям данный процессор не уступает по эффективности и сложности известным процессорам преобразований Фурье и Уолша. В частности, критерий А=5Тг ' принимает значение, соответствующее значению этого критерия для аналогичных однопроцессорных устройств ортсгсязльнкх преобразований (а'=0Ш31о§5Ш , он использует ту же эл-гменткук базу, его архитектура незначительно усложнена. Кроме г:г;, прс^зсор позволяет реализовать преобразования входных

выборок раМичной длины (N=0,1,... ,2, ш-некоторое фиксированное число), а также без изменений используется и для прямого и для обратного (ш^)-центрированного преобразования.

Рис. 3-4.1 Блок-схема параллельного устройства "психофизических" преобразований

В §§ 3-3 и 3.4 с целью дальнейшего повышения быстродействия, предложены архитектуры процессоров параллельной обработки информации, реализуЕсао соответственно класс дискретных ортогональных преобразовании (в частности, преобразования по матрицам ганкелеза типа) и "психофизические" преобразования.

Процессор Длина входной выборки Кол-во АУ Число тактов работы БТг Выполняемые операции

Итеративный процессор Фурье N=2™ т О (И Юв'Ю ДПФ

Параллельный процессор Уолша-Адамара Н=2т 21 т2т_1"1 о (и ДПУА

(1 ,т-1 ■

Процессор преобразо-ния по ганкелевым матрицам 11=2" 2т-» ,4пн-1 0(К 1о§3Ю ДПФ ОДПФ ДПУА пр-ния по ганке левым матрицам

Процессор "психофизических" преобразо- N=2"" 5пм-1 1ов3Н) "психофизические преобразования

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

Режим работы процессора- зависит от выполняемого преобразования (прямое или обратное преобразование по ганкелевым матрицам, быстрые прямое или обратное пробразования Фурье, прямое или обратное преобразование Уолша-Адамара).

На рис. 3.4.1 представлена блок - схема параллельного устройства "психофизических'« преобразований, содержащего информационные входа \о.. блоки коммутации 20-.. , осуществляющие перестановку "полная тасовка", устройства Зс-••, осуществляющие преобразования синтезируемые при помощи ганкелевых матриц и блок коммутации 4, осуществляющий

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

В таблице 3.4.1 приведен сравнительный анализ предложенных параллельных процессоров с итеративным процессором Фурье и параллельным процессором Уолша-Адамара, который позволяет выделить следующие их преимущества: высокое быстродействие и малая занимаемая площадь ^Ба^сНШ^'л); простая модульная архитектура; возможность реализации на одном процессоре прямого и обратного преобразования; многофункциональность процессора преобразований синтезируемых по ганкелевым матрицам.

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

Основные результаты работы.

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

2. Разработаны быстрые алгоритмы вычисления преобразований, построенных ка основе синтезируемых матриц. Показано, что для вычисления введенных преобразований вместо • о(М2) требуется о(М1ойМ) арифметических операций, где м -длина входного сигнала. Предложен по порядку оптимальный (в смысле критериев ускорения и эффективности), соответствующий моделям РНАЫ и БШ>, параллельный алгоритм вычисления синтезированных преобразований. 3- Разработаны^ алгоритмы сжатия сигналов, используя предложенные преобразования. На сигнале-кардиограмме показана эффективность (в смысле точности и скорости) применения введенных преобразований по сравнению с использованием "классических" преобразований Уолша, Хаара и косинусного преобразования. 4. Разработана архитектура спецпроцессоров последовательной и параллельной обработки информации, реализующих предложенные преобразования. Показано, что:

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

ортогональных преобразований,

б) параллельный процессор обладает модульной структурой. 5. Показано, что для последовательного процессора оценка быстродействия и занимаемой площади равна STz=o(N3log3N) и для параллельного процессора - STz=o(NlogsN).

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

Публикации

1. С.С. Агаян, К.О. Егиазарян, Н.А. Бабаян. "Семейство центрированных быстрых ортогональных преобразований".- Тезисы докладов I Всесоюзной конференции "Распознавание образов и анализ изображений: новые информационные технологии" РОАИ-1-91, Минск, 1991, с. 19-22.

2. S.S. Agayan, К.О. Egiazaryan, N.A. Babayan. "A family of Past Orthogonal Transforms Reflecting Psychophysical Properties of Vision"-"Pattern Recognition and Image Analysis: Advances .in Mathematical Theory and Application",- Published in Cooperation with the Scientific Council on Cybernetics, Scientific Russian Academy of Sciences, Interperiodica Publishing, 7.2, № 1,-March 1992, p.1-8.

3. C.C. Агаян, Д.З.Геворкян, Н.А. Бабаян. "Специализированный параллельный процессор ортогональных преобразований, учитывающих психофизические свойства зрения".- Тезисы докладов конференции "Проблемы создания систем обработки, анализа и понимания изображений", Ташкент, 1992, 2с.

4. С.С. Агаян, Д.З.Геворкян, Н.А. Бабаян. "Параллельный процессор ортогональных "психофизических" 'преобразований". -"Однородные вычислительные среды и систолические структуры", Львов, 1992, 12 с.

5. Н.А. Бабаян "Архитектура процёсоров "психофизических" преобразований и обработка сигнала".- Препринт ИПИА АН РА, 1992, 15 с. \