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

Союз Советских Социалистических Республикелам ткрытий 1.391.19:681.32588,8) ете МинистровСССР 10.Ч.197 та опубликования опис Автор зобретен. Лмельн аявител ФРОВОЕ УСТРОЙСТВО ДЛЯ ГЕОМЕТРИЧЕ ПРЕОБРАЗОВАН И Й ИЗОБРАЖЕН ИЯ Изобретение относится к области вычислительной техники.В задачах, связанных с распознаванием образов или со слежением за движущимся ооъектом сложной и меняощейся формы, в конструкторских задачах, требующих перебора различных форм изделия, в устройствах выдачи данных из ЦВМ и т. п. случаях требуется производить геометрические преобразования фигур, изображаемых набором точек с двумя градациями яркости, Обычно такие преобразования, выполняются на ЦВМ, которая вычисляет координаты точек преобразованной фигуры по известным координатам точек исходной фигуры. Однако такой метод требует наличия ЦВМ, специального программирования и занимает много машинного времени, т. к, вычисление координат каждой точки требует нескольких операций (например, для вычисления новых координат точки при аффинном преобразовании фигуры на трехадресной машине требуется 4 операции сложения и 4 умножения),Цель предлагаемого изобретения заключается в построении автономного и быстродействующего устройства, в котором любое (из заданного множества) геометрическое преобразование фигуры в целом производится одной операцией над кодом всей фигуры (т. е. над всеми точками фигуры одновременно). Эта цель достигается применением специальной схемы, которая по номеру геометрического преобразования производит преобразование двоичного кода фигуры в целом и образует на 5 выходе двоичный код преобразованной фигуры, При этом время преобразования фигуры в целом равно времени одной операции с кодом координаты одной точки этой фигуры на обычной ЦВМ (при постоянной системе эле.10 ментов), благодаря чему значительно сокращается время решения соответствующих задач. Ограничение состоит в том, что допускаются только аффинные преобразования на плоскости (поворот, сдвиг, смещение и т. п.).15 Аппаратурно это выражается в том, что устройство содержит регистр числа, регистр множимого и регистр геометрического кода фигуры, причем выход регистра множимого соединен со входом блока управления, выходы бло ка управления соединены с одним из управляющих входов регистра геометрического кода фигуры и входом регистра числа, выходы каждого разряда которого соединены с соответствующими управляющими входами регистра 25 геометрического кода фигуры.Регистр геометрического кода фигуры содержит К выполненных на триггерах сдвиговых регистров-ярусов, первый из которых имеет два разряда, а каждый последующий - 30 вдвое больше предыдущего, и схемы выработки сигналов переноса по количеству пар триггеров каждого регистра, причем одни входы схем выработки сигналов переноса -го яруса объединены ч подключены к соответствующим входам, два других входа - к выходам двух соответствующих триггеров данного регистра- яруса, четвертые входы каждой пары схем выработки сигналов переноса объединены и подсоединены к соответствующим двум выходам аналогичных схем (с - 2) -го яруса, третьи выходы всех схем выработки сигналов переноса каждого яруса объединены вместе и подключены к сдвиговым входам всех , с+1, +2, , к-х регистров-ярусов.На фиг. 1 показана общая блок-схема устройства, фиг, 2 поясняет построение регистра геометрического кода фигуры.На чертежах обозначены: 1 - блок управления; 2 - регистр числа; 3 - регистр множимо. то; 4 - регистр геометрического кода фигуры;5 - двухразрядные схемы выработки сигналов переноса; б - 12 - внешние связи схем 5;13 - 15 - сдвиговые регистры-ярусы; 16 - 29 - триггеры сдвиговых регистров-ярусов.Регистр 2 служит для хранения двоичного кода комплексного числа по основанию 1 72. Этот код в дальнейшем будем называть базисным. Например, если базисный кодО 11, то соответствующее ему комплексное число+1 (1 У 2 ) =1 - 1 ф 2Основным узлом устройства является регистр 4 геометрического кода фигуры, состоящий из совокупности регистров 13, 14, 15. Каждый из;этих регистров называется ярусом общего регистра геометрического кода, причем младший (первый) ярус (регистр 13) содержит 2 разряда, следующий (второй) ярус - 4,разряда, третий - 8 разрядов и т. д, Таким образом, ярус с номером к (к-ярус) содержит . 2" разрядов. В общем случае регистр содержит а ярусов и (2"+ - 2) разрядов и хранит код геометрической фигуры.Каждый ярус регистра геометрического кода содержит 2 -схем 5 выработки сигналов переноса и транспонирования. Входы 6 всех схем 5 каждого яруса объединены и соединены с выходом соответствующего триггера регистра 2. Входы 10 и 11 этих схем присоединены к выходам двух триггеров данного яруса. Сигналы переносов лсс и лД возникают на выходах 9 и 12 соответственно и поступают на объединенные входы 8 переносов двух схем 5, принадлежащих ярусу с номером к+2. Сигнал транспонирования т возникает на выходе 7 схемы 5 и поступает на сдвиговые входы всех ярусов с номерами, не меньшими, чем к. Входы 8 переносов трех схем 5 двух младших ярусов подключены к схеме управления. К этой же схеме .присоединены входы регистра 2 и его сигналы управления.Регистр множимого 3 имеет такую же раз. рядность, как регистр геометрического кода и связан с последним через блок управления 1,Устройство работает следующим образом.В регистр геометрического кода записывается код фигуры, а в регистр базисного кода - код комплексного числа, определяющего вид преобразования, Затем по сигналам из схемы управления производится алгебраическое сложение или умножение геометрического и базисного кодов. Любая из этих операций состоит из циклов сдвига базисного кода, распространения переносов по схемам 5 и транспонирования геометрического кода.Арифметические операции между геометрическим и базисным кодами эквивалентны одноименной арифметической операции между каждым комплексным числом, изображающим некоторую точку фигуры, и базисным числом.Таким образом, сложение эквивалентно смещению фигуры, умножение - повороту, умно жение только мнимых или действительных частей - сдвигу. В общем случае на предлагаемом устройстве можно выполнить любое аффинное преобразование исходной фигуры.Рассмотрим теперь элементарные операции 25 транспонирования и распространения переносов. Транспонирование заключается в перестановке определенных разрядов ярусных регистров, в которые поступил сигнал транспонирования, Это осуществляется на схеме, аналогич ной схеме сдвига. Поэтому ярусные регистры13, 14, 15являются сдвиговыми.Сигнал транспонирования, поступающий из1-яруса в к-ярус, производит перестановку разрядов к-яруса, номера которых отличаются на 35 2" - , причем перестановке подвергаются лишьразряды, связанные с теми схемами 5, которые ,по цепям 8, 9 и 8, 12 соединены со схемой 5 -яруса, выработавшей сигнал транспонирования т по цепи 7. Например, если сигнал т вы работался в схеме 5, соединенной с триггерами 20 и 21 (см, фиг. 2), то перестановке подлежат разряды 20 и 21, 26 и 28, 27 и 29 и т. д,Сигнал переноса ла вырабатывается на выходе 9 схемы 5, а лр - на выходе 12 этой же 45 схемы, Эти сигналы поступают затем в дведругие схемы 5 старшего яруса. Таким образом, каждая схема 5 вырабатывает сигналы т, ла и лр. Эти сигналы являются функцией сигнала л, пришедшего на вход 8, сигнала 6, 50 пришедшего на вход,б от триггера регистра 2,и сигналов а и Д, пришедших на входы 10 и 11 соответственно от триггеров регистра данного яруса, Формулы алгебры логики, связывающие эти величшы, имеют следующий вид: 55ла= (Ил) а;лр=рбл;т=бл;60 причем сигналы ла и лр вырабатываются сзадержкой относительно сигнала т на время 1, необходимое для транспонирования кода по сигналу т.При таком способе выработки и распростра нения сигналов ла, лр, т производится так на.зываемое ооратное сложение кодов, котороеэквивалентно следующей операции с числами:ЬК= - аК - б,где аК - точка исходной фигуры;ЬК - точка преобразованной фигуры;б - базисное число,Обратное сложение начинается по сигналам л, поступающим из блока управления 1 вначале в схему б первого яруса, а затем (через время 1) в схемы 5 второго яруса.При 6=0 обратное сложение эквивалентно инвертированию (умножению на - 1):ЬК= - аК,Операция ЬК=аК - 6 выполняется в два этапа:1) инвертирование и 2) обратное сложение.Умножение геометрического и базисного кодов состоит в последовательной замене базисным кодом тех разрядов геометрического кода, которые имеют четный номер в данном ярусе и единичное значение,Умножение выполняется в такой последовательности:а) из кода частичного произведения, хранящегося в регистре 3, выделяется очеоедной код ГК,к и передается через схему 1 на регистр 4, так, что младший разряд этого кода записывается в трипер 21 регистра фигуры; одновременно в триггеры 1 б и 17 этого же регистра записываются О и 1 соответственно, а в регистре 3 все разряды кода ГК,к заполняются О;б) код ГК,к в регистре фигуры складывается с базисным кодом М, находящимся в регистре 2, по формуле ГК,к - б;в) результат суммирования по пункту б) логически складывается с кодом на регистре 3, причем разряд 17 кода регистра фигуры складывается с разрядом (К - 1, к) кода регистра 3.В начале умножения в регистре 3 записан код множимого.Процесс умножения начинается с выделения кода 1.К,к, имеющего максимальный индекс к и минимальный индекс К, и продолжается в сторону уменьшения к и увеличения К. В конце умножения в регистре 3 оказывается произведение кодов множимого н отрицательного базисного числа, Это соответствует преобразованию каждой точки аК исходной фигуры в точку ЬК результирующей фигуры по формуле:ЬК= - 6 аК,Покомпонентное умножение отличается отобычного умножения, описанного выше, тем,что замене подвергаются только те разрядыав, у которых к - четное (нечетное). Обозначим (попрежнему К - четное):,а при к - четном,Опри к - нечетном, 30 35 40 5 10 15 20 25 45 50 55 60 6Заметим, что младшему разряду базисного кода соответствует нулевая степень основапия (1 ф 2 )= 1, четному разряду базисного кода соответствует нечетная степень основания 1 37 2, а нечетному разряду - четная степень основания Д/2 .Аналогично, четному (нечетному) номеру яруса кода фигуры соответствует нечетная (четная) степень основания 11/2 в коде числа аК, определяющего точку фигуры. Поэтому замена , соответствует операции умножения мнимой части каждой точки аК=хК+1 уК на отрицательное базисное число ЬК=хК - 1 буК; замена разрядов ;соответствует операции: Ь К = - бхК+1 у К.Таким образом, на предлагаемом устройстве можно выполнить любую (из требуемых для аффинных преобразований) арифметическую операцию с каждой координатой каждой точки исходной фигуры одновременно. Это резко уменьшает время преобразования на данном устройстве по сравненгио с ЦВМ. Предмет изобретения 1. Цифровое устройство для геометрических преобразований изображения, содержащее рег истры и блок управления, отличающееся тем, что, с целью сокращения времени преобразования, вхыод регистра множимого соединен со входом блока управления, выходы которого соединены с одним из управляющих входов регистра геометрического кода фигуры и входом регистра числа, выходы каждого разряда которого соединены с другими управляющими водами регистра геометрического кода фигуры. 2. Устройство по п, 1, отличающееся тем, что в нем регистр геометрического кода фигуры содержит к выполненных на триггерах сдвиговых регистров-ярусов, первый из которых имеет два разряда, а каждый последующий - вдвое больше предыдущего, и схемы выработки сигналов переноса по количеству пар триггеров каждого регистра, причем одни входы схем выработки сигналов переноса К-го яруса объединены и подключены к соответствующим входам, два других входа - к выходам двух соответствующих триггеров данного регистра-яруса, четвертые входы каждой пары схемы выработки сигналов переноса объединены и подсоединены к соответствующим двум выходам аналогичных схем (К - 2)-го яруса, третьи выходы всех схем выработки сигналов переноса каждого яруса объединены вместе и подключены к сдвиговым входам всех К,К+1, К+2, , к-х регистров-ярусов.Со ста вн тель В. Кудря в Корректор Т. Бабакина Техр ова, Нанкин акт пография, пр. Сапунова, 2 каз 1276/12 Изд.522 Тираж 448НИИПИ Комитета по делам изобретений и открытий при СМосква, Ж, Раушская наб., д. 4/5 Подписно ете Министров ССС