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

 

ОПИСАНИЕ 333523

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства №

Заявлено 31.VI1.1970 (№ 1471070/18-24) с присоединением заявки №

Приоритет

Опубликовано 21.III.1972. Бюллетень № 11

Дата опубликования описания 10.V.1972

М, Кл. 6 06k 9/06

G 06f 5/00

Коми1е1 по делам изобретений и открытий при Совете Министров

СССР

УДК 621.391.19:681.325 (088.8) Автор изобретения

С. И. Хмельник

Заявитель

ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ ГЕОМЕТРИЧЕСКИ

ПРЕОБРАЗОВАН И Й ИЗОБРАЖЕН ИЯ

Изобретение относится к области вычислительной техники.

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

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

Цель предлагаемого изобретения заключается в построении автономного и быстродействующего устройства, в котором любое (из заданного множества) геометрическое преобра".îâàíèå фигуры в целом производится одной операцией над кодом всей фигуры (т. е. над всеми точками фигуры одновременно). Эта цель достигается применением специальной схемы, которая по номеру геометрического преобразования производит преобразование двоичного кода фигуры в целом и образует на выходе двоичный код преобразованной фигуры. При этом время преобразования фигуры в целом равно времени одной операции с кодом координаты одной точки этой фигуры на обычной ЦВМ (при постоянной системе элементов), благодаря чему значительно сокращается время решения соответствующих задач. Ограничение:состоит в том, что допускаются только аффинные преобразования на плоскости (поворот, сдвиг, смещение и т. п.).

15 Аппаратурно это выражается в том, что устройство содержит регистр числа, регистр множимого и регистр геометрического кода фигуры, причем выход регистра множимого соединен cO Bxo o 6 0K еНН, BblxO: û бло20 ка управления соединены с одним из управляющих входов регистра геометрического кода фигуры и входом регистра числа, выходы каждого разряда которого соединены с соответствующими управляющими входами регистра

25 геометрического кода фигуры.

Регистр геометрического кода фигуры содержит К выполненных на триггерах сдвиговых регистров-ярусов, первый из которых имеет два разряда, а каждый последующий—

30 вдвое больше предыдущего, и схемы выработки сигналов переноса по количеству пар триггеров каждого регистра, причем одни входы схем выработки сигналов переноса i-го яруса объединены и подключены к соответствующим входам, два друI Нх входа — к выходам дву .i соответствующих триггеров данного регистраяруса, четвертые входы каждой пары схем выработки сигналов переноса объединены и подсоединены к соответствующим двум выходам аналогичных схем (i — 2)-ro яруса, третьи выходы всех схем выработки сигналов переноса каждого яруса объединены вместе и подключены к сдвиговым входам всех, i+1, i+2, ..., к-х регистров-ярусов.

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

На чертежах обозначены: 1 — блок управления; 2 — регистр числа; 8 — регистр множимо- го; 4 — регистр геометрического кода фигуры;

5 — двухразрядные схемы выработки сигналов переноса; б — 12 — внешние связи схем 5„

18 — 15 — сдвиговые регистры-ярусы; 1б — 29— триггеры сдвиговых регистров-ярусов.

Регистр 2 служит для хранения двои-нного кода комплексного числа по основанию i ф 2.

Этот код в дальнейшем будем называть базисным. Например, если базисный код-1О11, то соответствующее ему комплексное число (1У2 )з+O У2)à+1. (jÓ2 )1

+ 1 (j У 2 )о = 1 — 1 У 2

Основным узлом устройства является регистр 4 геометрического кода фигуры, состоящий из совокупности регистров 18, 14, 15. Каждый из,этих регистров называется ярусом общего регистра геометрического кода, причем младший (первый) ярус (регистр 18) содержит 2 разряда, следующий (второй) ярус—

4,разряда, третий — 8 разрядов и т. д. Таким образом, ярус с номером к (к-ярус) содержит . 2" разрядов. В общем случае регистр содержит а ярусов и (2"+ — 2) разрядов и хранит код геометрической фигуры.

Каждый ярус регистра геометрического ко- да содержит 2 схем 5 выработки сигналов переноса и транспонирования. Входы б всех схем 5 каждого яруса объединены и соединены с выходом соответствующего триггера регистра 2. Входы 10 и 11 этих схем присоединены к выходам двух триггеров данного яруса. Сигналы переносов ла и лР возникают на выходах 9 и 12 соответственно и поступают на объединенные входы 8 переносов двух схем 5, принадлежащих ярусу с номером к+2. Сигнал транспонирования т возникает на выходе 7 схемы 5 и поступает на сдвиговые входы всех ярусов с номерами, не меньшими, чем к. Входы 8 переносов трех схем 5 двух младших ярусов подключены к схеме управления. К этой же схеме .присоединены входы регистра 2 и его сигналы управления.

Регистр множимого 8 имеет такую же раз. рядность,- как регистр геометрического кода и связан с последним через блок управления 1.

Устройство работает следующим образом.

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

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

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

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

18, 14, 15 ... являются сдвиговыми.

Сигнал транспонирования, поступающий из

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

55 2" —, причем перестановке подвергаются лишь разряды, связанные с теми схемами 5, которые ,по цепям 8, 9 и 8, 12 соединены со схемой 5 -яруса, выработавшей сигнал транспонирования т по цепи 7. Например, если сигнал т вы40 работался в схеме 5, соединенной с триггерами 20 и 21 (см. фиг. 2), "î перестановке подлежат разряды 20 и 21, 26 и 28, 27 и 29 и т. д.

Сигнал переноса ла вырабатывается на выходе 9 схемы 5, а лр — на выходе 12 этой же

45 схемы. Эти сигналы поступают затем в две другие схемы 5 старшего яруса. Таким образом, каждая схема 5 вырабатывает сигналы т, ла и лР. Эти сигналы являются функцией сигнала л, при шедшего на вход 8, сигнала 6, пришедшего на вход,б от триггера регистра 2, и сигналов а и Р, пришедших на входы 10 и 11 соответственно от триггеров регистра данного яруса, Формулы алгебры логики, связывающие эти велич|шы, имеют следующий вид:

55 ла= (Ил) а; тф= Рбл; т=б®л;

60 причем сигналы ла и лр вырабатываются с задержкой относительно сигнала т»а время 1, необходимое для транспонирования кода по сигналу т. При таком способе выработки и распростра65 нения сигналов ла, лр, т производится так на333573

60 зываемое «обратное сложение» кодов, которое эквивалентно следующей операции с числами:

bi = — ai — 6, где а — точка исходной фигуры;

bi — точка преобразованной фигуры; б — базисное число.

Обратное сложение начинается по сигналам л, поступающим из блока управления 1 вначале в схему б первого яруса, а затем (через время t) в схемы 5 второго яруса.

При 6=0 обратное сложение эквивалентно инвертированию (умно>кению на — 1):

И = — ai.

Операция bi=ai — 6 выполняется в два этапа:

1) инвертирование и 2) обратное сложение.

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

Умножение выполняется в такой последовательности: а) из кода частичного произведения, хранящегося в регистре 8, выделяется очередной код

П,к и передается через схему 1 на регистр 4. так, что младший разряд этого кода записывается в трипер 21 регистра фигуры; одновременно в триггеры 1б и 17 этого же регистра записываются «0» и «1» соответственно, а в регистре 8 все разряды кода Гt,ê заполняются «0»; б) код П,к в регистре фигуры складывается с базисным кодом h;6, находящимся в регистре

2, по формуле Гi,ê — б; в) результат суммирования по пункту б) логически складывается с кодом на регистре 8, причем разряд 17 кода регистра фигуры складывается с разрядом (i — 1, к) кода регистра 8.

В начале умножения в регистре 8 записан код множимого.

Процесс умножения начинается с выделения кода Li,ê, имеющего максимальный индекс к и минимальный индекс 1, и продолжается в сторону уменьшения к и увеличения i. В конце умножения в регистре 8 оказывается произведение кодов мно>кимого и отрицательного базисного числа. Это соответствует преобразованию каждой точки ai исходной фигуры в точку bi результирующей фигуры по формуле:

bi= — 6 ai.

Покомпонентное умножение отличается от обычного умножения, описанного выше, тем, гго замене подвергаются только те разряды а,,, у которых к — четное (нечетное). Обозначим (по-прежнему i — четное): при к — четном, О при к — нечетном.

Заметим, что младшему разряду базисного кода соответствует нулевая степень основапия (1 V2 ) =1, четному разряду базисного кода соответствует нечетная степень основания

j V2, а нечетному разряду — четная степень основания Д 2 .

Аналогично, четному (нечетному) номеру яруса кода фигуры соответствует нечетная (четная) степень основания jg2 в коде числа ai, определяющего точку фигуры. Поэтому замена, „соответствует операции умножения мнимой части каждой точки ai=xi+)yi на отрицательное базисное число И=х — 1бф; замена разрядов 4,» соответствует операции:

И = — бхi+1У t.

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

Предмет изобретения

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

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

i,i+1, i+2, ..., к-х регистров-ярусов.

Редактор Б. Нанкина

Составитель В. Кудрявцев

Техред Л. Богданова

Корректор Т. Бабакина

Заказ 1276)12 Изд. М 522 Тира>к 448 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Ж-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2