Устройство для интерполяции

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ЯО 1264202)4 С 06 Г 15/35 ОПИСАНИЕ ИЭОБРЕТЕНИК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54 (57 ти ет пол ний юл. Ф 38 А;А.Александров, уляйкин и И.В,ШахГ ато 53) 56) н 9 21 А У 94УстрИ 1 етчик ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(088. 8)Великобританиил. Н 04 И 5/22, 1983.свидетельство СССРС 06 Г 15/353, 1980.еликобританиил. С 06 Р 15/20, 1975. 681.32Заявка0956,торско040, клявка В3045,Изо ычис окра цнн за с грир я ко ойст ойство для инткРпопяции ретенне относится к обласительной техники и позволя ить время выполнения интер искретизированных изображе ет аппаратной реализации вания по контуру и запомирдинат точки интерполяции. о содержит шесть элементов8, 13, 15, четыре элемеи4, 9, О, два реверсивных 5, 6 счетчик управления ель частоты 12, элемент1264202 НЕ 14, блок 16 памяти, три регистра17, 19, 21, два сумматора 18, 20,вычитатель 22 и блок 23 управления.Блок 23 выполнен на триггерах 31-33,генераторе 34 импульсов и элементеИЛИ-НЕ 35. Изменение координат, связанное с переходом к следующей Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах обработки двумерных массивов данных, в частности, в системах обработки и преобразования изображений.Цель изобретения - повышение быстродействия за счет аппаратной реализации интегрирования по контуру и запоминания координат точки интерполяции.На Фиг, 1 изображена Функциональная схема устройства; на Фиг. 2 структура дискретизированного изображения и.положение точки интерполяции, на Фиг. 3 - схема Формирования интерполяционного отсчета; на Фиг. 4 - схема изменения адреса при интерполяции; на Фиг. 5 - временная диаграмма работы блока управления. Устройство содержит первый 1 и второй 2 элементы И, первый 3 и второй 4 элементы ИЛИ, первый 5 и второй 6 реверсивные счетчики, третий 7 и четвертый 8 элементы И, третий 9 и четвертый 10 элементыЛИ, счетчик 11 управления, делитель 12 частоты, пятый элемент И 13, элемент НЕ 14, шестой элемент И 15, блок 16 памяти, первый регистр 17, первый сумматор 18, второй регистр 19, второй сумматор 20, третий регистр 21, вычитатель 22 и блок 23 управления. Разряды двоичного числа с выходарегистра 21 поступают на вход вычитаемого вычитателя 22 со сдвигом на два разряда в сторону младших разрядов (деление на четыре), а с выхода регистра 19 на вход уменьшаемого вычитателя 22 со сдвигом на (ш + 1) разрядов в сторону младших разрядов точке интерполяции, осуществляетсяподачей импульсов на входы 24 и 25устройства, при этом направлениеизменения координат управляется состоянием входов 26 и 27, устройства,1 з.п, Ф-лы, 5 ил. Гп1(деление на 2 ), где ш - числоразрядов делителя 12.Входами устройства являются входы24, 25 и 26, 27 соответственно пер 5 вой, второй координаты и реверса направлений первой и второй координаты,вход 28 начальной установки адреса,вход 29 запуска . Выходом 30 устройства служит выход вычитателя 22.Блок 23 управления содержит двутактные 0-триггеры 31-33, генератор34 импульсов, элемент ИЛИ-НЕ 35.Устройство работает следующим образом,15 Для удобства назовем Функцию 2Г(х, У) изображением,Состоянием старших разрядов реверсивных счетчиков 5 и 6, соединенныхс адресными входами блока 16 памяти,20 определяет выдаваемый на выход блока 16 элемент,дискретизованного.изображения (Фиг. 2), Емкости счетчиков 5 и 6 (их части, содержащейстаршие разряды) равны соответственно Ь и К, Части счетчиков 5 и 6, соответствующие младшим (остальным)разрядам имеют одинаковые емкости2 , так что общие емкости этих счетчиков 5 и 6 Ь 2 и К 230Числа Х и У на счетчиках 5 и 6 определяют положение точки интерполяции на плоскости (Фиг. 2), при этомстаршие их разряды определяют ноложение этой точки с точностью до одного элемента растра, а младшие -орасстояние до ближаишего столбца истроки. Однако то, какой отсчетдискретизованного изображения вы- "дается на выход блока 16 памяти, за 40висит только от состояния старшихразрядов счетчиков 5 и 6. Поэтому,1 не ограничивая общности, можно счи 1264202тать содержимое старших разрядов целой частью числа Х (либо У), содержимое младших - дробной, т.е. размер элемента растра равен единице (размер всего растра на фиг, 2 составляет ЬхК).На Фиг. 3 изображены четыре ближайших к точке интерполяции Р,(х, у) отсчета дискретизованного йзобра-,. - жения (Фиг. 2): тоЕ= й(Р). Е= й(Р),Уравнение плоскости проходящей через отсчеты в точках (Р , Р Р, ) 15 следующее;Е=2, + (2.-2 )БХ++(Е - 2, )6 У, (1) где БХ и БУ - числа на младших раз рядах счетчиков 5 и 6, не превосходящие единицы,Аналогичные уравнения для плоское-тей через точки (Р , Р, , Р, ), 25следующие:Ео + (211 Ео ) 6 ) +Ео 1 )(1 Х)э (2)21 + ("1 о - Ес ) (1 - ЬХ)+ ЗО,35При линейной интерполяции по тремточкам (Р , Р , Р ) в качествеинтерполяционного значения отсчетав точке (Х, У) можно взять отсчет вэтой точке уравнения (1);40Ев 1 = Ео + (Ео 1 - Еоо ) 6 Х +Аналогично, используя уравнения (2) и (4), можно построить отсчет ЕЕ , Тогда за интерполяционное значение в точке (Х, У) при интерполяции по четырем точкам (Ед Э Е, Е, Е ) принимают:15 О2 = - (Е +2 +2 +Е )4 4 ( (4 а и чз1 (Домножив это выражение на 2" (емкость младших разрядов счетчиков 5и 6), получают выражение, в соответствии с которым осуществляют вычисления: 2 = .,1,Е (1 - Б Х 2 )+ Е ),Действительно, после установки реверсивных счетчиков 5 и 6 в состоя ние, соответствующее точке Р (х, у),ц )на вход 29 запуска устройства подают отрицательный импульс, инициирующий работу блока 23 управления.Этот импульс устанавливает триггеры 31 и 32 в состояния "1" и "0" соответственно. На первом входе блока 23 управления присутствует уровень "1", который устанавливается с момента окончания предыдущего цикла интерполяции (фиг, 5). По положительному Фронту очередного тактовогд импульса генератора 34 "О" с информационного входа триггера 3 1 переписывается на его выход, а на выход триггера 32 записывается "1" с выхода триггера 3 1. По второму и последующим импульсам в триггер 32 записывается "О" с выхода триггера 3 1. На третьем выходе блока управления 23 Формируется положительный импульс (см. Фиг, 5). Этот импульс устанавливает в нулевое состояние счетчик 11, делитель 12 и регистры 17, 19 и 21. С выхода третьего разряда установленного в О счетчика 11 уровень "О" поступает на вход признака окончания цикла блока 23 управления. С этого момента сигнал на первом выходе блока управления 23 устанавливается в нулевое состояние, что блокирует входы 24- 27 устройства и вызывает появление уровня 0" на входах элементов ИЛИ 3, 4, 9 и 10.Уровни сигналов на управляющих входах счетчиков 5 и б повторяют состояние второго разряда счетчика12642 511. Так как последний обнулен, то счетчик 5 суммирует (нулевой уровень на входе управления) импульсы, поступающие с второго выхода блока 23 управления на его счетный вход5 (фиг. 5), На счетный вход счетчика 6 импульсы не поступают, так как элемент И 13 блокирован нулем на его втором входе,Каждый импульс на втором выходе 10 блока управления увеличивает содержимое счетчика 5 на единицу его младшего разряда. Одновременно увеличивается число в счетчике 11, ем; кость которого, как и младших разря дов счетчиков 5 и 6; равна 2В интервале между импульсами число на выходе блока 16 памяти определяется старшими разрядами счетчиков 5 и 6, Это число заносится по фрон ту сигнала на входе синхронизации записи в регистр 17, Затем по фронту сигнала на входе записи происходит его накопление (добавление к прежнему содержимому) в регистре 19 25 с помощью сумматора 18, число на выходе которого перед очередной записью в регистр 19 равно сумме со-. ,держимого этого регистра и числа в регистре 17. 30 вПосле поступления с второго входаблока 23 управления первой серии из2 импульсов содержимое младших разрядов счетчика 5 становится равным35исходному (так как их емкость равна2 ), число на адресном входе блока16 памяти, соединенном со старшимиразрядами счетчика 5, увеличиваетсяна единицу. Как следует из фиг, 4,где изображен участок растра точекотсчетов Функции Г(х, у), содержащийсоответствует перемещению точки (Х,У) по прямой вдоль оси Х на единицу45(фиг. 2) в точку А. Причем поскольку начальное положение в точке Рпо отношению к растру дискретизации(например к точке Р ) определяетсясодержимым младших разрядов счетчиков 5 и Ь, т,е. их содержимое в точ 50ке Р соответствует поступлению6 Х 2 и 6 У 2 импульсов, от началаинтерполяции в точке Р до моментапересечения вертикали Р , Р(фиг. 4) в точке Л , соответствующего увеличению на единицу числа напервом адресном входе блока 16 памяти, с второго выхода блока 23 управ 02,ления поступает (2 - Ъ Х 2") импульсов.При изменении числа Х на счетчике 5, соответствующем перемещению точки(Х, У) из точки Р до точки А число на выходе блока 16 памяти соответствует отсчету в точке Р , т,е. равно 7, так как старшие разряды счетчика 5 при этом не изменяются. Поскольку с второго выхода блока 23 управления на этом этапе на счетный вход счетчика 5 и вход синхронизации регистра 19 поступает (2 - 8 Х 2") импульсов, а перед началом интерноляции регистр 19 был обнулен, его со,держимое при прохождении точкой (Х, У) точки А равно (2. - о Х 2 ) Е,В точке А содержимое регистра 19 становится равным (2 - Я Х 2 )2 ++ о Х 2 / 1 К этому моменту блок 23 управления вырабатывает 2 импульсов, вследствие чего первый разряд счетчика 11 после прохожденияточкой (Х, У) точки А устанавливается в "1", выход элемента И 15 - в"О", а импульсы с второго выходаблока 23 управления через элементИ 13 и ИЛИ 4 начинают поступать навход реверсивного счетчика 6, который их суммирует, так как на его. управляющем входе по прежнему присутствует 0 с выхода второго разрядасчетчика 11, На счетный вход счетчика 5 импульсы не поступают. Так какна этом этапе изменяется число У,то движение точки (Х, У) происходитпо вертикали из точки А в точку Б,в которой число в регистре 19 становится равным 2 -ЬХ 2)К +ЬХ 2 К 3++ И 2 -дУ 2 )К+ ЬУ.2 К) аК моменту прохождения точки Б число поступивших импульсов составит (т1)2 , и на выходе первого разряда счетчика 11 устанавливается "О", а на выходе второго - "1". которая, пройдя на управляющие входы счетчиков 5 и 6, реверсирует направление счета. Следующие 2 импульсов со второго выхода схемы управления поступают на счетный вход счетчика 5, а :точка (Х, У) перемещается по горизонтали из точки Б в точку В и число в регистре 19 увеличится на1 ЬХ 2 Е+ (2 - б Х 2 )Е Четвертая серия из 2 импульсов соответствует перемещению из точки В в точку Р Число в регистре 19 увеличивается еще на ф 2 Ео + (22 )Еои становится равным выражению в Фигурных скобках в выражении (6). 1 О 15 Одновременно накопление происходит и в регистре 21, однако занесение информации в него (по сигналуна входе записи) осуществляется поотрицательному Фронту выходного сигнала делителя 12. Поскольку емкостьэтого счетчика равна 2, накоплениечисла с выхода регистра 17 в регистре21 происходит по окончании каждой 20серии из 2 импульсов, т.е. при прохождении точкой (Х, У) точек А, Б,В и Р . Число в регистре 17 в этимоменты равно соответственно ЕЕ, , Е Е так как перед началом25интерполяции содержимое регистровобнуляется, то при прохождении точкиР в регистре 21 накопляется величина (Е, + Е + Е, + Е, ).К моменту окончания последней серии из 2 импульсов их общее числос начала интерполяции составляет4 х 2, Поскольку емкость делителя 12равна 2, последний импульс сериипереведет его в нулевое начальное З 5состояние, Первый, второй и третийразряды счетчика 11 устанавливаютсяв состояния соответственно "0", "0".и "1". Появление единичного уровняна выходе третьего разряда счетчика ,4011, соединенного с входом признакаокончания цикла блока 23 управлениядеблокирует 0-триггер 33 "1" с П информационного входа этого триггерапереписывается на выход по положительному фронту очередного (4 х 2 +(фиг. 5), При этом дальнейшее формированиеимпульсов на втором выходеблока 23 управления прекращается, ана первом ее выходе устанавливаетсяуровень "1", разрешающий прохождениесигналов с входов 24-27 через элементыИ 1, 2, 7 и 8,По первому импульсу на втором выходе блока 23 управления в регистре19 присутствует "О" по второму импульсу серии - число Е и т.д.; по последнему (4 х 2 + 1)-му импульсу в регистр 19 заносится последний отсчет с выхода сумматора 18.Накопленная в этом регистре сумма42 суммирований становится численно равна выражению в Фигурных скобках формулы (6) .На выход 30 устройства поступаетчисло с вычитателя 22, На вход вычитаемого вычитателя 22 поступает величина (Е + Е+ Е, + Е, ) свыхода регистра 21 со сдвигом в сторону младших разрядов, соответствующим делению на четыре; на вход уменьшаемого - число с выхода регистра19, равное значению выражения в фигурных скобках в Формуле (6) со сдвигом, соответствующим делению на 2Тогда на выходе вычитателя 22 и выходе 30 устройства имеется число,соответствующее первой части Формулы (6) - расчитанный интерполяционный отсчет в точке Р (Х, Т),На этом цикл интерполяции в точке Р, заканчивается. Устройство готово к вводу координат очереднойточки интерполяции.Продолжительность всего вычислимтельного процесса составляет 4 х 2 =2периодов тактовой частотыгенератора 34.После завершения интерполяции вочередной точке Р (Х, У), устройство переходит в режим ввода координат следующей точки (Х , У ). Приэтом на втором выходе блока 23 управления импульсы отсутствуют, поддерживается нулевой уровень (на выходах элементов И 13, 15 "О"), а напервом - уровень "1".Подавая импульсы на входы 24 и25 внешнее устройство, в качествекоторого могут быть использованы,например, дифференциальные числоимпульсные датчики каких-либо измеряемых параметров, осуществляет изменение координат Х и У, связанное спереходом к следующей точке интерполяции. Направление изменения координат определяется состоянием входов 26 и 27, также контролируемыхвнешним устройством,Количество импульсов, подаваемых на входы 24 и 25 устройства, определяется изменением координат при переходе к следующей точке интерполяции:126420210направления первой и второй координаты устройства соответственно, выходы третьего и четвертого элементовИ подключены к первым входам третьего и четвертого элементов ИЛИ соответственно, выходы которых подключены к входам управления режимомсчета первого и второго реверсивныксчетчиков соответственно, входы10 сброса которых соединены с входомначальной установки адреса устройст"ва, вход запуска которого соединенс одноименным входом блока управления, первый выход которого подключен15 к вторым входам с первого по четвертый элементов И, второй выход блокауправления подключен к входам синхронизации первого и второго регистров, первым входам пятого и шестого20 элементов И и к входу делителя часи з о б р е т е н и я тоты, выход которого подключен квходу синхронизации третьего регистра и счетному входу счетчика управления, выход первого разряда которого подключен к второму входу пятогоэлемента И и через элемент НЕ к второму входу шестого элемента И, выходы пятого и шестого элементов Иподключены к вторым входам второгои первого элементов ИЛИ соответственно, выход второго разряда счетчика управления подключен к вторым, входам третьего и четвертого элементов ИЛИ, выход третьего разряда счетчика управления подключен к входупризнака окончания цикла управления,третий выход которого подключен квходам сброса счетчика управления,делителя частоты и с первого по третий регистров, выход первого регистра подключен к входу первого слагаемого второго сумматора, выход которого подключен к информационному входу третьего регистра, выход которогоподключен к входу второго слагаемоговторого сумматора и со сдвигом надва разряда,в сторону младших разрядов к входу вычитаемого вычитателя,выход второго регистра подключен сосдвигом на (ш + 1) разрядов в сторо"ну младших разрядов к входу уменьшаемого вычитателя, где ш - число разрядов делителя частоты, выход вычитателя является выходом устройства. 9И = 2 Х - Х;МЕ = 2 й -Ч 1,Формула причем очередным вводом координатыпредыдущей точки (содержимое счетчиков 5 и 6) сохраняются. Это позволяет получить значительное сокращениевремени ввода предлагаемого устройства при интерполяции для массиваточек Р (Х, У, ), расположенныхна изображении большого формата.Это связано с тем, что средняя величина изменения координат при переходе от интерполяции в одной точке кследующей меньше средней величинысамых координат, определяющей времяввода при отсутствии хранения координат предыдущей точки. 1, Устройство для интерполяции, содержащее два элемента И, два элемента ИЛИ, два реверсивных счетчика, делитель частоты, счетчик управления, блок памяти, три регистра, первый сумматор и блок управления, первые входы первого и второго элементов И являются входами первой и второй координаты устройства соответственно, выходы первого и второго элементов И подключены к первым входам нервого и второго элементов ИЛИ соответственно, выходы которых подключены к счетным входам первого и второго реверсивных счетчиков соответственно, выходы групп старших разрядов которых подключены к адрес ным входам первой и второй группы блока памяти, выход которого подключен к информационному входу первого регистра, выход которого подключен к входу первого слагаемого первого сумматора, выход которого подключен к информационному входу второго45 регистра, выход которого подключен к входу второго слагаемого первого сумматора, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства за счет аппаратной реализации интегрирования поконтуру и запоминания координатточки интерполяции, в него введены второй сумматор, вычитатель, третий и четвертый элементы ИЛИ, с третьего 5по шестой элементы И и элемент НЕ, первые входы третьего и четвертогоэлементов И являются входами реверса 2. Устройство по и. 1, о т л и - ч а ю щ е е с я тем, что блок управления содержит генератор импульсов,12 б 4 202 д элемент ИЛИ-НЕ и три триггера, входысинхронизации которых соединены спервым входом элемента ИЛИ-НЕ и выходом генератора импульсов, инверсныйвход установки первого триггера является входом запуска блока и соеди-нен с инверсным входом сброса второго триггера, информационный вход которого подключен к выходу первоготриггера, информационный вход которого подключен к шине информационно 12го нуля блока, информационный вход и1инверсный вход сброса третьего триггера подключены к входу приэнакаокончания цикла блока, выход третье го триггера подключен к второму входуэлемента ИЛИ-НЕ и является первымвыходом блока, выход элемента ИЛИ-НЕявляется вторым выходом блока, выход второго триггера подключен ктретьему входу элемента ИЛИ-НЕ и является третьим выходом блока./РНРП ймхоР оставитель А.Ушаковехред. М.Ходанич КорРектоР Е.Сирохма Редактор Л.Пчелинская аказ 5564/50 оизводственно-полиграфическое предприятие,.г. Ужгород Проектная,Тираж ВНИИПИ Государст по делам изобр 035, Москва, Ж671 Подписноеенного комитета СССРтений и открытийРаушская наб., 4/5