Устройство для параллельной обработки трехмерных сцен Советский патент 1990 года по МПК G06F15/16 G06T15/00 G06F15/173 

Изобретение относится к вычислительной техник., предназначено для обработки трехмерных сцен, причем каждому элементу сцены соответствует . свой обрабатывающий процессор, а в аимодействие между процессорами осуществляется по непосредственным связям между ними, что обуславливает. Bi,icoKoe быстродействие, обуславливающее возможные применения хщя иного технического решения, и является усовершенстворанием устройства по овт.св. № 1456965.

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

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

На фиг. и 2 представлен пример реализации устройства параллельной обработки трехмерных сцен; на фиг.З - конструкция блока поворота и схемы, согласно которым в устройстве аппа- ратно реализуется операция поворота содержимого последнего слоя А X А X 1 матрицы вокруг центра этого слоя на угол, не кратньт 90 ; на фиг. 4 - конструкция блоков сжатия и растяжения и схемы, согласно которым в устройстве аппаратно реализуется операция сжатия содер; .имого последнего слоя А X А X 1 матрицы на коэффициент К относительно прямой, проходящей через

tsD

&0

О

центр квадрата Л X А и параллельной стороне этого квадрата.

Устройство (фиг.1 и 2) состоит из трехмерной матрицы 1 Л X А X А процессоров, блока 2 управления, блоков 3 цоворота, блоков 4 сжатия, блоков 5 растяжения, блока 6 памяти, первьм и последний слои матрицы 1

тий: длины ( отрезка для R ; площади ((E) плоской фигуры Ь - для объема трехмерной фигуры Е - для R , Множества Е .. 6 S назовем т-м объектом

г т п-мерной сцены S. Сцену S

формата F для которой одновременно вьтолняются выражения: F

ммеют соответственно входы 7 и выхо- ю и Е и (V-, jels) (i k)(E|nE. ды 8. В спою очередь матрица 1 сое-

гонт из А процессоров 9. Каждый про- ф) назовем Шд-нарным ( или га цессор 9 включает в себя первый ре-уровневым) п-мерным изображением форгистр 10 операнда, второй регистр 11мата F Каждое т -нарное изобраЬперлнда, узел 12 памяти, элемент формата // может быть представЙЛИ 13, блок элементов И, включающийлено т - значной числовой Функцией ft себя элементы И 14 - 24 и элемент ИЛИ-НЕ 25. Блок .управления содержит узел 26 определения объема, узел 27

.fAAt-t. ---- , . ., .

Ф, принимающей в каждой точке aCF такое значение Ф(а), когда справедливым оказывается высказывание:

оперативной памяти, программно-адре-20 V. . суемьш регистры 23 - 30, управляющий Ф(Ь));Ф(ЬеЕ)) Л((Ф(а) Ф(Ь))

ГфоЦессор 31, который состоит из регистра 32 команды, мультиплексора 33 адреса, арифметико-логического узла 34, дешифратора 35, элементов И 36 и 25 торых справедливы выражения:

ИЛИ 37 выбора блоков 3 поворота, элементов ИЛИ 38 и 39 выбора блоков 4 сжатия, элементов И 40 и ИЛИ 41 выбора блоков 5 растяжения, узла 42 микропрограммного управления. Узел 42 микропрограммного управления содержит генератор 43 синхронизирующих импульсов, дешифратор 44 команды, генератор 45 выработки адреса микроолова, регисту 46 адреса микрослова, узел 47 памяти микрослов, регистр 48 fикpocлoвa, дешифраторы 49 кода микрооперации, дешифратор 50 кода режима ввода-вывода, элементы И 51 30

35

Ф. vv.w tij п (bfa)). Разо бьем пространство R

на классы точечных множеств Pg R (где leL, L 1,2,3,...,00), для ко- орых справедливы выражения:

(VieL) (Va,(a,b)6 (1 )

где р (a,b) - расстояние между точка- ми а и Ъ множества Pg 5 р - постоянная,

(neL)ju% ) (2)

(Vi.jeL)(i / j)((ip f

)J ,

r.(W

R

(3) (4).

и (;

Реь (1 и Множества PjCR , одновременно .

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

58.Блоки поворота 3, сжатия 4 и

растяжения 5 (фиг. 3 и 4) могут ленное из конечного множества пиксе- быть выполнены одинаковыми по конст- р(Д „аэовем Р -дискретным объек- рукции и содержат элементы КПИ 59 д5 (Ъ.,вЬ) . Р -дискретной моделью

Л CiVlin i. lljriI V,ll il - -LV J f

a 6p - постоянной этого разбиения. Точечное множество Ц

и составeeix f

и элементы И 60.

Описание работы устройства целесообразно начать с определения ряда используемых терминов, п-мерной сценой S формата F назовем некото рое семейство S 1 1,2,3,..., THg) точечных множеств Ь п-мерного эвклидового прост- R, удовлетворяющее выражению () (IV (((Нн1) 0)Л

. f. .. ч-т A.rhl /т: ч ..л

множества пел назовем F ный объект Е У

(Х.

дискретLJ Рр , составленный из всех пикселов Pg (где 1вЬ, LcCL), для которых выполняется ° (5lGLf)()(54.

где

ч i - JJ г,:у 111 ч«- | -р//| л - f

§Р постоянная (). Вычислитeл.Jнyю процедуру по формированию Р -дискретной модели ff (E) множества f(E) из множества F, где

( я гле ) - п-мер- f(S) образ множе тва Е С R« при tr Mei, п-м1.риого миожсст а Е, (по-. отображении f:E-.f(E), назовем

,, аппя-дискретизирующим отображением г ,моиятие п-мернои меры (Ч (Ь ; япля -j. 5г .,-::

етс-. ..естественным обобиглнием поняделирующим отображение f: (E).

V. . Ф(Ь));Ф(ЬеЕ)) Л((Ф(а) Ф(Ь))

торых справедливы выражения:

Ф. vv.w tij п (bfa)). Разо бьем пространство R

на классы точечных множеств Pg R (где leL, L 1,2,3,...,00), для ко- орых справедливы выражения:

(VieL) (Va,(a,b)6 (1 )

где р (a,b) - расстояние между точка- ми а и Ъ множества Pg 5 р - постоянная,

(neL)ju% ) (2)

(Vi.jeL)(i / j)((ip f

)J ,

r.(W

R

(3) (4).

и (;

Реь (1 и Множества PjCR , одновременно .

Р -пиксельного разбиения R ;

ленное из конечного множества пиксе- р(Д „аэовем Р -дискретным объек- (Ъ.,вЬ) . Р -дискретной моделью

Л CiVlin i. lljriI V,ll il - -LV J f

a 6p - постоянной этого разбиения. Точечное множество Ц

и составeeix f

ленное из конечного множества пиксе- р(Д „аэовем Р -дискретным объек- 5 (Ъ.,вЬ) . Р -дискретной моделью

множества пел назовем F ный объект Е У

(Х.

дискретLJ Рр , составленный из всех пикселов Pg (где 1вЬ, LcCL), для которых выполняется ° (5lGLf)()(54.

где

ч i - JJ г,:у 111 ч«- | -р//| л - f

§Р постоянная (). Вычислитeл.Jнyю процедуру по формированию Р -дискретной модели ff (E) множества f(E) из множества F, где

дискретизирующим отображением г ,мо

-j. 5г .,-::

делирующим отображение f: (E).

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

ми, роль пикселов Pg выполняют кубики 1 X 1 X 1 , а выполнение геометрических преобразований пространства . R 5 к числу которых относятся преобразования поворота, переноса, сжатия и растяжения, заменено в устрой/

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

,(п) W,

Ф, (PV)

1, если Р, СЕ, гд

М (п О, «если PJ СЕ F,

: p(L,

10

- 15

общий принцип построения Р -дискретной модели fP(E) множества f(E) (где, Р: и некоторый произвольньй

есЬе

p -дискретный объект; f - биек- тивное отображение f : R R ) из объекта Е, входящего в состав бинарного п-мерного изображения Зц некоторого формата . Результатом такого построения должно стать бинарное п-мерное изображение Sg формата F, , содержащее объект f (Е) . Поскольи S я являются бинарными

КУ S ,

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

и el

Изобретение относится к вычислительной технике и предназначено для обработки трехмерных сцен и является усовершенствованием изобретения по авт.св. N 1456965. Цель изобретения - сокращение времени выполнения операции изменения масштаба обрабатываемых объектов и поворота на углы, кратные 90°, и расширение области применения за счет увеличения диапазона углов поворота и разрешающей способности обрабатываемых сцен. В устройстве каждому элементу обрабатываемой сцены соответствует свой процессор, выполняющий логическую обработку бинарных трехмерных изображений. Взаимодействие между процессорами осуществляется по непосредственным связям. Введение блоков сжатия и растяжения, увеличение количества элементов И в блоке элементов И процессора, соответствующее подключение блоков поворота к трехмерной матрице процессоров и введение блока памяти позволяют достичь упомянутых положительных эффектов. 3 з.п. ф-лы, 4 ил.

Ф

(nl Р 1, если P;, cf (Е), где 1 е I, ;

,Cn

(Ы

О, если Cf ЧЕ) F2

(

и eeu

F4E)

Построение Р дискретной модели образа f(E) предполагает определение меры ( О f (Е));для каждого сцены S.,. Из равенства Е . следует:/. f(E) fyf(F;),

где LpCL, отсюда P; (L() .

(Uf(p r)) .u ((P. V)

«. 4Ue icUc . - -/«v. /

Так как (Yi, jeL){:(i j)(PpP- , a f - биективное о.тображение f: , TO f(Ppaf(P5) $.

Таким образом из (1) и свойства

W

аддитивности меры вытекает

ф.СР)

i, если (f(E)nP pyV8 )

(nt

О, (E)OPe)/(M (Pj) Jg. (6)

Выражения (5) и (6) полностью определяют зависимость значений Ф от значений Ф на области определе- Г . Так как ) f (F, то fS (E)nf ф-(гце Г ЕДГ), поэтому значения ФгСР ) соответствующие пикселам , равняются 0. Р -дискретизирующее отображение допускает возможность одновременного выполнения над всеми пикселями Рр сцены Sg выражений (5) и (6). Простейший способ осуществления такого распараллеливания.

(

F4E)

,ч.р

f (Е)

w 4pfn f(E)) 2:/u1pfof(pf))

I leLr

J

I -I€LE

Используя введенную функцию Oj(Pj ), можно записать

,,W(pftf№)) Г ГЛГмсЛ .

.(.V

X Ф, (Р) ,

где G1CL, , причем (iSL, aj( 5 Ф(). Из оп

(5)

)С(

определения

Р дискретной модели множества f(E) следует

(nt

0

5

непосредственно вытекающий из выражений (5) и (6), состоит в применении для каждого пиксела р С Г пары многовходовой аналоговой сумматор - пороговый элемент (вход 1-го порогог вого элемента соединен с выходом 1-го аналогового сумматора). Каждый 1-й сумматор служит для реализации и.ражения (5), каждьш 1-й пороговый элемент - для реализации выражения (6), Варьируя значением . , можно упростить данный способ аппаратной реализации Р -дискретизирующего

16

отображения путем замены аналоговьк элементов на простейшие цифровые элементы. Действительноj если для выбранного значения оР высказыва- ние (V; eL) Of (РР ) /( S{ истинно, то для формирования значе; ния Фй () нет необходимости вычис- ;лять З), а достаточно реализовать i булевую функцию

) 4Ф,(1). (7)

1 t/tj(p

где Ф(Р; ) и ) вьшолняют уже роль булевых переменных (1 - истин- :но, О ложно). В зависимости от того, какое из значений ) (О или 1) пикселов k-ro п-мерногр бинарного изобр, ;ения образует Р - дискретную модель объекта Е, можно говорить о позитивном или негативно м преде тавлениг объекта Е в изоб- ражении. Переход от позитивного :представления объекта Е к его негативному представлению равнозначен :замене функции Ф (Р) на функцию Ф,(

Выражение (7) -в случае негатив- ;ного представления объектов Е и f (Е) имеет вид

(8)

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

ф,(р) - Л ф..

;eqe

Зависимость (8) является ма-ема 580, 270°); отображений, моделирую

35

Оу, Ог на углы, кратные 90 (90,

тическои основой для реализации в предлагаемом устройстве Р -дискрети- зирующих отображений, 1иоделирующих перенос, поворот, сжатие р -дискрет ных объектов. Применительно к дискретизирующим отображениям f,, моделирующим перенос, повороты,сжатия объекта Е, негативное представление отличается от позитивного тем, что образующие при выполнении тих отображений пустые области Г (E) в случае негативного представления ЧЕ) заполняются единицами. В устройстве содержимое регистров 10 или II одноименного операнда всех процессоров 9 матрицы 1 или слов узла 12 памяти, имеющих одинаковый адрес, образует трехмерное поле значений Ф ( некоторого k-ro би- нарного тре::мерного изображения формата F . Формат Р Чфедставляет собой куб А X А II А и состоит из А

3078

трехмерных пикселов кубиков 1 X 1 X (фиг.I), где 1 1,2,...,А. Каждому кубику Р куба F взаимно- с однозначно соответствует процессор 9 матрицы 1. Особенностью моделирования Р -дискретизирующим отображением (Q) поворота Р дискрет- ного объекта произвольный

Q угол является невозможность сохранения в Р -дискретном объекте f (Q) числа кубиков (Q) и их относительного положения, характерных для кубиков PgCQ. Важным исключением из

5 этого правила является -поворот

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

Q Необходимым требованием к устройству обработки трехмерных сцен является требование обеспечения возможности поворота объектов сцен на большой диапазон пространственных углов,Дан25 ная проблема решается в предлагаемом устройстве путем частичной депаралле- лизации процедуры поворота, при этом моделирование поворота Р дискретно- го объекта на заданный угол осущест30 вляется при помощи последовательного выполнения следующих аппаратно-реали- зованных дискретизирующих отображений: отображений, моделирующих поворот произвольного бинарного изображения формата F вокруг осей Ох,

580, 270°); отображений, моделирую

35

Оу, Ог на углы, кратные 90 (90,

щих поворот произвольных плоских бинарных изображений формата Q (где F, - октант квадрата А X А) на углы из диапазона 0(

(21

ЭТОМ октант F,|g состоит из квадратов 1 X 1 (пикселов РХ ) , входящих в состав квадрата (размером А X А); поворот вокруг центра на углы, кратные 90 ; симметрии относитепьно взаимно-ортогональных прямых, проходящих через квадрата и параллельных сторонам F ; преобразо, ваниях, выражающихся через компози- J

цию двух первых видов преобразований; не отображаются друг на друга, Между пикселами (X 1,2,... ,.,А ) и пикселами Pg послед5

него (относительно направления В) слоя А X А X 1 матрицы 1 существует взаимно-однозначное соответствие. Способ аппаратной реализации Р -диск ретизирующего отображения P - f«(P

(где f : - поворот плоское ти на угол Oi вокруг центра F) в блоках 3 предлагаемого устройства не отличается от способа реализации

ЗЙ

ная

-(4

величина , Р -дискретизирутощее отображение f J(F,) вызывает отображение (Fp. Точность поворота произвольног

глр i...jvijo/ 3 блоках поворота прототипа и заключается в использовании мно- говходовых элементов И. В то же время, если в прототипе число мйого- входовых элементов И используемых при моделировании поворота плоского фрагмента изображения на один единственный угол, соответствует числу пикселов (где F. fl - квад10

моделирования

Р -дискретного -объекта

угол м, (т.е. диапазонixf fco eiy j,

не превышает точности

поворота пиксела

женного

(т .

(X-f

pCT(- Р С

на

моделирования Fj, располо-

ниого на расстоянии г (Ре) г-г

,Q . -.//«им ,. МЙКО / Q 1 е. (Х л; -0( ) гд «зкс 1 1мин ofhi .(iv. / //«aw JMMtf

Wry -(Х.-ЭО

t

:,, CF

«e

l-n.-«V ITЧ Г„JJ Tl

pafff F )jTO в предлагаемом устройстве вится шире.

б, т ci

Поскольку с уменьшением значения г.гу, диапазон o(f - 0( f

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

Из-за погрешности дискретизации каждый р -дискретный объект f (E) является -дискретной моделью образа JQ f(E) не одного преобразования f :

таких участков t

возможно (il

J

0( v стан сущестзование которых диапазон iX - перекрывает не один, а несколько углов 0 М поворота, образуя множество М j СМ перекрыва мых углов.

3 случае выполнения этого услови

многовходо.вые,элементы И блоков 3,. используемые при моделировании пово рота бинарного изображения формата f Q (для реализации поворота участ ка FT ЭТОГО изображения) на угол СК.,, могут быть использованы и при моделировании поворотов изображения

формат - f-fit

лы

, а

, а целого множества П(f Е) преобразований f, образы f(E) которых имеют одну ту же Р -дискретную (Е), Среди преобразований fen(f jE) есть однотипные преобразо- вания(повороты вокруг одной точки, сжатия относительно одной/ прямой и

сР/

35

т.п.). Отсюда образу .(Pje) пиксела

3MaTaF,/g . на другие (ra(Mj-)- П уг вокруг центра F (m/M j ) число углов множества Мт) .Разобьем октант F/fft на зоны Yi - , .где

( (21 Дл

с F-tI( названные участки Fj, , удовлетворяющие условию т(М-(-) т(М ) - 1. Каждый j-й блок 3 предлагаемого устройства, управляемый собственным сигналом поворота. (Cnj), включает в себя только те многовходовые элементы

можно дать в соответствие мне- .Q жество П(Х(, Р

преобразований по- вокруг центра F ,

соответствуют r-tx

пикселам Р,

И, которгле ,(, - эе

cfP(f

ci,Uj ,

ворота f

углы поворота в которых отличаются,

а образы fp (РХ имеют одну и ту же

где € И. Отсюда параллельньпЧ поворот бинарного изображения формата

ра) Ш

на угол Л М вокруг центра F

(г

моделируется в устройстве путем од1 -дискретную модель f(P. Поэтому 45 современной подачи управляю111 5Х сиг- моделирование поворота )

(2)я,.

Р -дискретизирующим отображением

,:/(РЙ7 осу цествляется с точностью

д;yгLв J,.. .;

Пусть задано конечное множество М {0(;} (из диапазона 0 - 45®) значений углов, поворот на которые бинарного изображения формата предполагается реализовать в блоках 3 устройства. Пусть F-, - участок , образованньй времи пикселами расстояние rCPgj,; которых до центра F удовлетворяет неравен-- ству r(, где г - постоян5(

капов СП на те блоки 3, чьи соответствующие образы fp/(Fj; при объединении дают (с допустимой степенью точности) образ f (F).

На фиг.3 показано, как объедине™ fP4:s.

блока 3, блока 3, Ь-го блока 3 дает образ повернутого

fi( J1fP(F

октанта F

(1) 1/85f

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

612307

ная

10

величина , Р -дискретизирутощее отображение f J(F,) вызывает отображение (Fp. Точность i поворота произвольного

-- т10

моделирования

Р -дискретного -объекта

угол м, (т.е. диапазонixf fco eiy j,)

не превышает точности

поворота пиксела

женного

(т .

(X-f

pCT(- Р С

на

моделирования Fj, располо-

ниого на расстоянии г (Ре) г-г

,Q . -.//«им ,. МЙКО / Q 1 е. (Х л; -0( ) где «зкс 1 1мин ofhi .(iv. / //«aw JMMtfx

Wry -(Х.-ЭО

t

:,, CF

JJ Tl

е вится шире.

б, т ci

Поскольку с уменьшением значения г.гу, диапазон o(f - 0( f

. JQ . 25 JQ

таких участков t

возможно (il

J

0( v стано- сущестзование которых диапазон iX - перекрывает не один, а несколько углов 0 М поворота, образуя множество М j СМ перекрываемых углов.

3 случае выполнения этого условия

многовходо.вые,элементы И блоков 3,. используемые при моделировании поворота бинарного изображения формата f Q (для реализации поворота участка FT ЭТОГО изображения) на угол СК.,, могут быть использованы и при моделировании поворотов изображения

формат - f-fit

лы

) ,

35

3MaTaF,/g . на другие (ra(Mj-)- П уг- вокруг центра F (m/M j ) - число углов множества Мт) .Разобьем октант F/fft на зоны Yi - , .где

( (21 Дл

с F-tI( названные участки Fj, , удовлетворяющие условию т(М-(-) т(М ) - 1. Каждый j-й блок 3 предлагаемого устройства, управляемый собственным сигналом поворота. (Cnj), включает в себя только те многовходовые элементы

- .Q

- ,

соответствуют r-tx

пикселам Р,

И, которгле ,(, - эе

cfP(f

ci,Uj ,

где € И. Отсюда параллельньпЧ поворот бинарного изображения формата

ра) Ш

на угол Л М вокруг центра F

(г

моделируется в устройстве путем оду 45 современной подачи управляю111 5Х сиг- тт

5 современной подачи управляю111 5Х сиг- тт

(

капов СП на те блоки 3, чьи соответствующие образы fp/(Fj; при объединении дают (с допустимой степенью точности) образ f (F).

На фиг.3 показано, как объедине™ fP4:s.

блока 3, блока 3, J-J AJIVJ Ь-го блока 3 дает образ повернутого

fi( J1 8 fP(FP

октанта F

(1) 1/8f

Достоинством предлагаемого устройства является возможность осуще.ст- вления с его помощью высокоскоростного изменения масштаба Р -дискрет- ных объектов на большой диапазон маештабных коэффициентов. Значительное расширение диапазона масштабных коэффициентов достигнуто в устройстве благодаря частичной депараллелиза- ции процедуры изменения масштаба, когда изменение масштаба Р -дискретного объекта на заданный коэффициент k осутцествляеТся при помощи последовательного выполнения Р -дискретизи- рующих отображений,вьтолняе1 1ых над прямоугольными участками F бинарного изображения формата и моделирующих преобразования сжатия (растяжения) плоскости к прямо PR, проходящей через центр квадрата F J и параллельной стороне Р . Множество представляет в общем случае прямоугольник, две параллельные стороны которого перпендикулярны прямой РР и имеют длину

м

F/2 (или А), две другие стороны параллельны PR, причем как минимум одна из них лежит на стороне .

Длины сторон F имеквадрата F

ют целые значения. Возможные варианты (сжатые в k раз), отличающиеся степенью распараллеливания операции сжатия, а также объемом используемого оборудования, приведены на фиг,4 в,г,д. Присжатии плоскости в k раз к прямой PR (т.е. при выполнении преобразования . ) обргз fj;(a) точки сама точка а лежат н i общем перпендикуляре к прямой PR, принадлежат .одной и той же полуплоскости с грани1,ай PR, расстояние р(к(а), PR) (от точки fц(а) до PR) и (ajPR) (от точки а до PR) связаны зависимостью: p(f,(a), PR) kp(a, PR). Если , отображение называется сжатием, при k 1 - растяжением-,Част

ный случай FU показан на фиг,4е и представляет собой прямоугольник размером А/2 X 1 (где А - четное),сос- тоя1 дий из А/2 квадратиков-пикселов образ fK( показан на фиг.4з; образ f(FjJ - на фиг,4и. Аппаратная реализация Р -дискретизи- рующего отображения РМ j;(i /y v моделирующего сжатие бинарного изображения формата F|J состоит в применении иноГовходовых элементов ИЛИ 59,входы которых соединяются с входами 8 устройства в соответствии с выражением (8) (или в соответствии с (7)), При малых значениях k (примерно в пределах 0.k.0,3) использование цифро-.

вых элементов 59 для моделирования сжатия в k раз требует значительного снижения порогового значения 0 (аналога oj в (6)), что приводит к существенному снижению точности моделирования преобразования сжатия.

Для предотвращения этого при малых значениях k целесообразна замена т-входовых элементов 59 на пары т-входовой аналоговый сумматор - пороговый элемент, реализующие непосредственно выражения (5) и (6) и

моделирующие сжатие с большей точностью, В этом случае выход порогового элемента соединяется с входом элемента И 60, Образу f ( пиксела С F по аналогии с Пр;(,1) можно дать в соответствие множество n,(f, преобразований сжатия fj : прямой PR, кoэффиl eн- ты k сжатия в которых отличаются, а образы f( имеют одну и ту же

5 Р -дискретную модель f|,(P . Поэтому моделирование сжатия ( осуществляется с точностью до коэффици0

0

5

0

0

5

ентов К, Пусть задано конечное множество D { К; 1 (из диапазона О - 1) зна,чений коэффициентов сжатия к PR.

,, Пусть FW - участок прямоугольника 7fiH , образованньй всеми пикселами расстояние G(P которых до прямой PR удовлетворяет неравенству G( где G; - постоянная величина. Р -дискретизирующее отображение (F выбывает отобра кение (. Точность .моделирования преобразования сжатия произвольного Р -дискретного объекта коэффициент k к прямой PR (т.е. диапазон кДцёК ) не превьш1ает точности моделирования сжатия к пря- 5 мой PR пиксела , расположенного на расстоянии. G(PS) GW (т.е. к «оке). Пусть

мич 2 6 Gi,tG«.+ . Поскольку с уменьше „V МИЧ ..МЙКС

нием значения Gy диапазон К „ и становится шире, возможно существование таких участков F, в которых диапазон К и - перекрывает не один, а несколько коэффициентов k€D сжатия к прямой PR, образуя множество D CD перекрываемых коэффициентов. 3 случае вьшолнения этого условия элементы 59 и 60 блоков 4, используемые при сжатии бинарного изображения формата F (для сжатия

13

участка F этого изображения) на коэффициент k 6 D,, могут быть использованы и при моделировании сжатия изображения формата F: на другие m( коэффициенты прямой PR (m(Dy.) - число коэффициентов множества D-iJ/). Разобьем FM на зоны F-,, , - названные участки прямоугольника Fд, удовлетворяю:дие условию m(D{) in(D.P - 1, Каждый j-й блок 4 предлагаемого устройства, управляе- №,1Й собственным сигналом сжатия (CCJ), включает в себя только те элементы 59 и 60, которые соответствуют пикселам Р С f (), где keDyy. Отсюда параллелыгое сжатие бинарного изображения формата FJ на коэффициент k6D к прямой PR моделируется в устройстве путем одновременной подачи управляющих сигналов СС на те блоки 4, чьи образы i (,7) при объединении дают образ fГ (F . Аьалогич мным образом в блоках 5 устройства

реализуется растяжение бинарного изoбpaJкeния формата Fj, на коэффициент k Г от прямой PR, Роль управляющих сигналов выполняют в этом случае сигналы растяжения (СР), поступающие на управляющие входы элементов 60 блоков 5. Конструкция и работа блока 2 управления предлагаемого устройства в основном совпадает с конструкцией и работой блока управления прототипа. Однако команда . ПВЗ А1 в предлагаемом устройстве имеет иной смысл: Сформировать сцену А1 из сцены А1 путем сдвига исход кого содержимого этой сцены на шаг вдоль В с поворотом октанта последнего слоя АХАХ сцены вокруг Ох на угол, номер которого хранится в регистре 30, и записью результата поворота в первый слой результирующей сцены. Кроме того, в систему команд устройства дополнительно введена команда СЖ А1 Сформировать сцену А из сцены А путем сдвига исход ного содержимого этой сцены на шаг вдаль 3 со сжатием прямоугольного участка А X 1 последнего слоя А X А X 1 сцены к прямой, проходящей через центр квадрата А X А этого слоя, и параллельной стороне квадрата на коэффициент, номер которого хранится в регистре 30, и записью результата сжатия в первьй слой результирующей сцены. В управляющем

: 5

--12307

процессоре 31 реализуется принцип i микропрограммного управления. Согласно этого принципа высшим уровнем внутреннего языка управления являет- ется язык команд программы. Управление на этом уровне осуществляется последоватепьным извлечением команд из узла 27 памяти и их выполнением,

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

Регистр 32 команды предназначен для хранения выполняемой команды. В процессе ее выполнения сигналы с вы- ходов разрядов ащресной части регистра 32 группами, соответствующими от2Q дельным адресам А1, А2 сцен-операндов, через выходы АЛЛ мультиплексора 33 подключаются к адресным входам узлов 12 памяти процессоров 9. Управление мультиплексором 33 произ25 водится разрядом РУАВ регистра А8 мккрослова. Если этот разряд равен О, то к адресным входам узлов 12 подключается код А1, если 1 - подключается код А2.

3Q Узел 42 микропр-ограмьшого управления слулсит для генерации управляющих сигналов, Дпя каждого состояния управляющего процессора 31 существует отдельное микрослово. Узел 47 памяти хранит эти микрослова, содержащие копии управляющих сигналов (сигналов микрооперации), треб тоютхся для каждого состояния управляющего процессора 31. С целью выработки последова.Q тельности управляющих сигналов содержимое регистра 46 аДреса микрослова с помощью генератора 45 изменяется по каждому импульсу -С1, вырабатывае- генератором 43. По следов ат ел ьдг ность микрослов образует микропрограм- bfy. Микрослово содержит управляющее поле, разряды которого используются для генерации сигналов требуемых микроопераций, а также .поле следующего м iкpoaдpeca и поле кода микроветвления. Часть управляющего поля микрослова образует поле управления матрицей , в это поле входят разряд управления адресными входами матрицы (РУАБ), разряды кода микрооперации (Ш-Ю), разряд разрешения записи в узел 12 (ЗЛП), разряд управления считыванием содержимого узла 12 памяти в регистры 10 (СР8), разряд управле35

50

15

16

иня считыванием содержимого узла 12 в регистры 11 (СР9), три разряда кода рйжима ввода-вывода (РВВ), разряд зфпуска операции определения объема (фБ). Содержимое разрядов РВВ регист pi 48 соответствует следующим режи- работы устройства: 001 - Пово- рЬт на угол, некратный Old - 0вод информации в матрицу 1 из ре- riiCTpa Oil - Вывод информации и матрицы 1 в регистр 100 - Сжатие/растяжение.

Ддя повьппения скорости выполне- поворотов содержимого матрицы li на углы, кратные 90° , вокруг осей QX, Оу, Oz, увеличения скорости вы- флнения межпроцессорных передач Е|ДОЛЬ осей Ох, Оу, Oz блок элементов 20 И каждого процессора 9 может допол- йительно содержать двухвходовые элементы И 18 - 24, предназначенные для {реализации поворота содержимого мат- |)ицы на углы 180 и 270 вокруг Ох, 25 180 и 270° вбкруг Оу, 90, 180 и 270 бокруг Oz соответственно. Управляющие входы этих элементов И соединены С соответствующими выходами дешифратора 49 кода микроопераций.Информа- ЗО Ционные входы соединяются с вькода- Ии процессора 9, чьи кубики Р 1 при повороте на соответствующий угол, Кратньш 90°, вокруг одной из трех названных осей отображаются на куби- ки pf в процессорах 9 которых находятся указанные входы. В случае построения матрицы 1 из типовых интегральных модулей, каждьш из которых содержит внутри себя 24 процессора Q 9, образующих относительно поворотов на углы, кратные 90, вокруг Ох, Оу, Oz замкнутую систему, возможно многократное повьппение скорости обработки сцен без существенного понижения надежности и габаритов устройства (поскольку все ортогонально-кольцевые межпроцессорные связи располагались бы внутри модуля). При включении в состав процессоров 9 элементов И 18 - 24 поле КМО регистра 48 содержит четыре разряда, содержимое которых соответствует следующим микрооперациям и командам (включаемых в этом случае в систе2 у команд устройства) : 1) 0000 - 01002, ИНЕ А1, 2; 2) 0001 - Поворот на 90° вокруг Ох. ПВ1 А1, А2; 3) 0010 - Поворот

-- -.« /ч 1 А О

123071Ь

4) ООП - Сдвиг на шаг вдоль В,СДВ А1, А2; 5) 0100 - Поворот на 180

:вокруг Ох, ПВ4 А1,А2; 6) 0101 - Поворот на 270® вокруг Ох ПВ5 А1,А2; 7) О.ПО - Поворот на ISO вокруг Оу, ПВб А1,А2; 8) 0111 - Поворот на 270° вокруг Оу, ПВ7 А1, А2;

9) 1000 - Поворот на-90° вокруг Oz, jO ПВ8 Al, А2; 10) 1001 - Поворот на

.180 вокруг Oz, ПВ9 Al, А2;

.11) 1010 - Поворот на 270 вокруг Oz, ПВШ А, А2.

г Е устройстве имеется возможность

55

на

вокруг ОУ,, ПВ2 А1, А2;

обработки mg-нарных (где 2) дискретных изображений формата i (где п 5: 3) ,отличающихся высоким разрешением. Обработка таких изображений осуществляется в устройстве трехмерными б лнарными фрагментами (формата обрабатываемыми в устройстве с предельной степенью параллелиза- цик, последовательно фрагмент за ф Ьагментом, функцию хранения фрагментов т -нарных изображений может выполнять в этом случае память на узлах 12. Однако максимально достижимьш объем этой памяти сильно ограничен из-за небольших размеров кристалла типового модуля матрицы 1, поэтому устройство может дополнительно содержать блок 6 памяти (фиг.1), связанный с матрицей 1 посредством двух магистралей ввода вывода по А проводных связей (7 или 8) каждая. При наличии в составе устройства блока 6 в блок 2 управления дополнительно вводится программно-адресуемый регистр 58, в регистр 48 вводятся разряды ЗП (запись в память 6) и ЧП (чтение памяти 6), система команд устройства дополняется командами: ВВЫВ А1 - Записать содержимое последнего (относительно В) слоя А X А X 1 сцены А1 в память 6 по адресу, хранящемуся в регистре ВВВ А1 - Записать бинарное изображе ние формата X А), хранящееся в памяти 6 по адресу, код которого расположен в регистре 58, в первый (относительно В) слой А X А X 1 сце ны с адресом Al.

Рассмотрим выполнение каждой из введенных команд. При этом будем считать, что объекты сцен-операндов А1, А2 представлены в негативном вид

Команда ПВЗ А1. Микрослово этой команды содержит: РУАВ О, СР8 1,

Е устройстве имеется возможность

5

обработки mg-нарных (где 2) дискретных изображений формата i (где п 5: 3) ,отличающихся высоким разрешением. Обработка таких изображений осуществляется в устройстве трехмерными б лнарными фрагментами (формата обрабатываемыми в устройстве с предельной степенью параллелиза- цик, последовательно фрагмент за ф Ьагментом, функцию хранения фрагментов т -нарных изображений может выполнять в этом случае память на узлах 12. Однако максимально достижимьш объем этой памяти сильно ограничен из-за небольших размеров кристалла типового модуля матрицы 1, поэтому устройство может дополнительно содержать блок 6 памяти (фиг.1), связанный с матрицей 1 посредством двух магистралей ввода вывода по А проводных связей (7 или 8) каждая. При наличии в составе устройства блока 6 в блок 2 управления дополнительно вводится программно-адресуемый регистр 58, в регистр 48 вводятся разряды ЗП (запись в память 6) и ЧП (чтение памяти 6), система команд устройства дополняется командами: ВВЫВ А1 - Записать содержимое последнего (относительно В) слоя А X А X 1 сцены А1 в память 6 по адресу, хранящемуся в регистре ВВВ А1 - Записать бинарное изображение формата X А), хранящееся в памяти 6 по адресу, код которого расположен в регистре 58, в первый (относительно В) слой А X А X 1 сцены с адресом Al.

Рассмотрим выполнение каждой из введенных команд. При этом будем считать, что объекты сцен-операндов А1, А2 представлены в негативном виде.

Команда ПВЗ А1. Микрослово этой команды содержит: РУАВ О, СР8 1,

КМО ООП, ЗЛП , РВВ 001. При выполнении микрокоманды по импульсу С1 на адресных входах узлов 12 установится код А , будут подготовлень элементы 17, 52 и 53, а также элеметы И 36, чьи образы fp{( при объединении дают f() ( (у: - угол номер которого расположен в регистр 30), будут подготовлены двухвходо- вые элементы И выбранных блоков 3. С приходом С2 производится запись содержимого А в регистры 10, при этом информация с выходов 8 поступает на многовходовые элементы И выбранных блоков 3 и через двухвходо- вые элементы И выбранных блоков 3 поступает на входы 7. В момент прихода СЗ содержимое регистров 10 со сдвигом на шаг записывается в узел 12 памяти по a дpecy А, в первьпд слой АХАХ 1 сцены А1 записывается изображение повернутого октанта F,,g последнего слоя А X. А X 1 преды- д ущего содержимого А1 , Далее осуществляется переход к микропрограмме извлечения следующей команды программы. Поворот всего квадрата F осуществляется программно за восемь этапов (соответственно числу октант

.тон F

(2)

1/8

входящих в ),

Команда С/К А., Т шкрослово этой команды содержит: РУАВ О, СР8 1 КМО ООП., ЗЛП 1, РВВ 100. При вьтолнении микрокоманды по импульсу С1 на адресных входах узлов 12 установится код А1, будут подготовлены элементы 17, 52 и 53 и элементы 38 (или 40), чьи образы f() при объединении дают ffCFJ b (где k - коэффициент, номер которого хранится 3 регистре 30; F - крайний верхний прямоугольник А X 1 квадрата ), будут подготовлены элементы И 60 выбранных блоков 4 (или 5). С приходом С2 производится запись содержимого А1 в регистры 10, при этом информация с выходов 8 поступает на элементы 59 выбран1а1х блоков 4 (или 5) и через элементы 60 этих блоков поступает на входы 7. В момент при- хада СЗ содержимое регистров 10 со сдвигом на шаг записывается в узды 12 по адресу АГ, в первый слой А X А X 1 сцены А1 записывается сжатое изображение прямоугольника F. Сжатие (растяжение) всей сцены А X А X А осуществляется программно

, fO

15

20

25

612307 3

с использованием дополнительных (рабочих) сцен и примененчем команд ИНЕ А1, А2 и СДВ А1, А2.

Команда ВВЫВ А. 1 1икрослово этой команды содержит: РУАВ О, СРЗ 1, ЗЛП 1, КМО ООП, ЗП 1, ЧП 0. При выполнении микрокоманды по импульсу С1 на адресных входах узлов 12 устано-вится код AJ , будут подготовлены элементы 17,52, 53 и 55,. С приходом С2 про зводится запись содержимого Ai в регистры 10, при этом инфоркащш с выходов 8 поступает на входы данных блока 6. В момент прихода С3 содержимое регистров 10 со сдвигом на шаг записывается в узел 12 по адресу А1, а сигнал с выхода элемента -55 инициирует в памяти 6 операцию Запись.

Команда ВВВ А1. 1 1нкрослово этой команды содержит: РУАВ О, СР8 1, ЗЛП 1, КМС ООП, ЗП О, ЧП 1. Перед выполнением команды на выходных регистрах памяти 6 находится информация, извлеченная из памяти 6 по адресу, хранящемуся в регистре 58, однако связь выходов этих регистров с входами 7 блокирована. 30 Блокировка может быть осуществлена при помощи А ключей И, управляемых триггером, которьй сбрасывается CI, а устанавливается СЧП (ключи и триггер включаются в этом случае в состав блока 6). При выполнении микрокоманды по импульсу С1 на адресных входах узлов 12 установится код А1, будут подготовлены элементы 17,52, 53 и 56. С приходом С2 производится запись содержимого А1 в регистры 10 и осуществляется разблокирование связей выходных регистров памяти 6 с входами 7 матрицы. В момент прихода СЗ содержимое регистров 10 со сдвигом на шаг записывается в узел 12 по адресу А, а в первый слой АХАХ 1 сцень А1 записывается информация, извлеченная из памяти б. С приходом следующего импульса С1 производится блокирование выходов памяти 6. Команда ПВ4 А1, А2. Микропрограмма этой команды включает микрослова: 1) - РУАБ. О, 2) - РУАВ 1, то 0100, ЗЛП к в результате вьтолнения первого микрослова содержимое А1 располагается в регистрах 10, По С1 в регистр микрослова вызывается второе микрослово микропрограммы, С приходом СЗ.

35

40

45

50

55

19

161

производится запись содержимого регистров 10 в память 12 через под-: готовленные элементы И 18 с поворотом на 180° вокруг Ох. Аналогичным ;образом выполняются и другие команды :вида ПЗ N А1,А2 (отличшошиеся кодом ЖО) . Повороты на углы 0 :+ k 90 вьшолняются программно.Сжатие ;р -дискретных изображений формата F IK прямой PR на коэффициенты К КГ Kj :выполняется программно. Изменение Iмасштаба Р дискретных изображений ;формата F® на коэффициент k относи- тельно оси Ох (т.е. операция одновре- |менного сжатия в k раз к плоскости ;zOx и в k раз к плоскости уОх) выполняется программно. Формула изобретения

2, Устройство по п., о т ли чающееся тем, что, с целью

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

Г

35

XSO.

Ш

f

2

jgj

ш

1323 Л

.-f

г;р1

даг

i%a

- 8

-Йз

a

W

Т

Я7.

ff:

1

/7/

Г

5 f

/f

tl

/(ЛЯ

PI

шн

г

Фиг.З

Ah