Устройство для интерполяции Советский патент 1986 года по МПК G06F17/17 

НЕ 14; блок 16 памяти, три регистра 17, 19, 21, два сумматора 18,. 20, вычитатель 22 и блок 23 управления Блок 23 выполнен на триггерах 31-33, генераторе 34 импульсов и элементе ИЛИ-НЕ 35, Изменение координат, связанное с переходом к следующей

точке интерп оляции, осуществляется подачей импульсов на входы 24 и 25 устройства, при этом направление изменения координат управляется состоянием входов 26 и 27, устройства, 1 ЗоП, ф-лы, 5 ил.

Изобретение относится к области вычислительной техники и позволяет сократить время вьтолнения интерполяции дискретизированных изображений за счет аппаратной реализации интегрирования по контуру и. запоминания координат точки интерполяции. Устройство содержит шесть элементов И 1, 2, 7, 8, 13, 15, четьфе элемеита ИЛИ 3, 4, 9, 10, два реверсивных счетчика 5, 6 счетчик управления 11, делитель частоты 12, элемент W

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

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

На фиг, 1 изображена функ7диональная схема устройства; на фиг. 2 структура дискретизированного изображения и.положение точки интерполяции J на фиг. 3 - схема формирования интерполяционного отсчета; на фиг« 4 - схема изменения адреса при интерполяцииJ на фиг, 5 - временная диаграмма работы блока управления.

Устройство содержит первый 1 и второй 2 элементы И, первый 3 и второй 4 элементы ИЛИ, первый 5 и второй 6 реверсивные счетчики, третий 7 и четвертый 8 элементы И, третий 9 и четвертый 1-0 элементы ИЛИ, счетчик 11 управления, делитель 12 частоты, пятый элемент И 13, элемент НЕ 14, шестой элемент И 15, блок 16 памяти, первый регистр 17, первый сумматор 18, второй регистр 19, второй сумматор 20, третий регистр 21, вычитатель 22 и блок 23 управления.

Разряды двоичного числа с выхода регистра 21 поступают на вход вычитаемого вьгчитателя 22 со сдвигом на два разряда в сторону младших разрядов (деление на четыре), а с выхода регистра 19 на вход уменьшаемого вычитателя 22 со сдвигом на (т + 1) разрядов в сторону младших разрядов

(деление на 2

), где m - число

разрядов делителя 12.

Входами устройства являются входы 24, 25 и 26, 27 соответственно первой, второй координаты и реверса направлений первой и второй- координаты, вход 28 начальной установки адреса, вход 29 запуска. Выходом 30 устройства служит выход вычитателя 22,

Блок 23 управления содержит двутактные D-триггеры 31-33, генератор 34 импульсов, элемент ИЛИ-НЕ 35.

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

Для удобства назовем функцию Z f(x, у) изображением.

Состоянием старших разрядов реверсивных счетчиков 5 и 6, соединенных с адресными входами блока 16 памяти, определяет выдаваемый на выход блока 16 элемент .дискретизованного. изображения (фиг. 2). Емкости счетчиков 5 и 6 (их части, содержащей старшие разряды) равны соответственно L и К. Части счетчиков 5 и 6, соответствующие младшим (остальным) разрядам имеют одинаковые емкости

так что общие емкости этих счетчиков 5 и 6 Lи К-2

Числа X и Y на счетчиках 3 и 6 определяют положение точки интерполяции на плоскости (фиг. 2), при этом старшие их разряды определяют положение этой точки с точностью до одного элемента растра, а младшие расстояние до ближайшего столбца и строки. Однако то, какой отсчет дискретизованного изображения вы- дается на выход блока 16 памяти, зависит только от состояния старших разрядов счетчиков 5 и 6. Поэтому, не ограничивая обш;ности, можно считать содержимое старших разрядов целой частью числа X (либо Y), содержимое младших - дробной, т.е. размер элемента растра равен единице (размер всего растра на фиг. 2 составляет LxK).

На фиг. 3 изображены четьфе ближайших к точке интерполяции Рц. (х, у) отсчета дискретизованного йзобра-.жения (фиг. 2): f(Po, ). f(Po, f(P. f(P.. ). Уравнение плоскости проходящей через отсчеты в точках следующее: (Zo, Z z, + (Z,,. - z,j6x + „)S Y, to где SX и SY - числа на младши рядах счетчиков 5 и 6, не прев щие единицы. Аналогичные уравнения для ш тей через точки (, Р„, ) и (Р 41 No следукяцие: Z Z,, + (Z,, - Z, )6Y + - Z )(1 ); + (Z - Z,, )(1 -6 I 11 10 n « (Z,, - Z,, )(1 -SY), )(1 Z Z. + (Zo„ - Z.. - z, )x. + (Z. При линейной интерполяции п точкам (Р„ Р.- ) в качес интерполяционного значения отс в точке (X, Y) можно взять отс зтой точке уравнения (1); - I 00 Аналогично, используя уравн (2) и (4), можно построить отс ... Zy. Тогда за интерпол но значение в точке (X, Y) при терполяции по четырем точкам (Z Z ) принимают: i(2., Zu Z, ,o(i -«X) + + , (1 - SY) z,5Yi + + tz,5x + z (1 -Sx)l H. Lz,Y 2;;(i -SY)} - Z,

Домножив это вьфажение на 2(емкость младших разрядов счетчиков 5 . и 6), получают выражение, в соответствии с которым осуществляют вычисления:

1 /г

Z, ( 2-) - 2 |+ Z 6Х 2 + Z , (2 -6 Y 2) + ) 5 + 2„бх-2 ,0 (2 SX-2) + Z,6Y 2 6Y-2)) -| (Z + Z Z ). Действительно, после установки реверсивных счетчиков 5 и 6 в состояние, соответствующее точке Р (х, у), 1на вход 29 запуска устройства подают отрицательный импульс, инициирующий работу блока 23 управления. Этот импульс устанавливает триггеры 31 и 32 в состояния 1 и О соответственно. На первом входе блока 23 управления присутствует уровень 1, который устанавливается с момента окончания предыдущего цикла интерполяции (фиг. 5). По положительному фронту очередного тактовогЬ импульса генератора 34 О с информационного входа триггера 31 переписывается на его выход, а на выход триггера 32 записывается 1 с выхода триггера 31. По второму и последующим импульсам в триггер 32 .записывается О с выхода триггера 31. На третьем выходе блока управления 23 формируется положительный импульс (см. фиг. 5). Этот импульс устанавливает в нулевое состояние счетчик 11, делитель 12 и регистры 17, 19 и 21. С выхода третьего разряда установленного в О счетчика 11 уровень О поступает на вход признака окончания цикла блока 23 управления. С этого момента сигнал на первом выходе блока управления 23 устанавливается в нулевое состояние, что блокирует входы 2427 устройства и вызьтает появление уровня О на входах элементов ИЛИ 3, 4, 9 и 10. Уровни сигналов на управляющих входах счетчиков 5 и 6 повторяют состояние второго разряда счетчика 11. Так как последний обнулен, то счетчик 5 суммирует (нулевой уровен на входе управления) импульсы, поступающие с второго выхода блока 23 управления на его счетный вход (фиг. 5). На счетный вход счетчика 6 импульсы не поступают, так как элемент И 13 блокирован нулем на его втором входе, Каждьй импульс на втором выходе блока управления увеличивает содержимое счетчика 5 на единицу его младшего разряда. Одновременно увел чивается число в счетчике 11, емг кость которого, как и младших раэрядон счетчиков 5 и 6, равна 2 . . В интервале между импульсами число на выходе блока 16 памяти определяется старшими разрядами счетчиков 5 и 6, Это число заносится по фронту сигнала на входе синхронизации записи в регистр 17, Затем по фронту сигнала на входе записи происходит его накопление (добавление к прежнему содержимому) в регистре 19 с помощью сумматора 18,число на вы ходе которого перед очередной записью в регистр 19 равно сумме со.держимого этого регистра и числа в регистре 17. После поступления с,второго вход блока 23 управления первой серии из 2 импульсов содержимое младших раз рядов счетчика 5 становится равным исходному (так как их емкость равна 2 ), число на адресном входе блока 16 памяти, соединенном со старшими разрядами счетчика 5, .увеличивается на единицу. Как следует из фиг, 4, где изображен участок растра точек отсчетов функции f(x, у), содержащи точки Р , Р„ ,. Р, , , Р , это соответствует перемещению точки (X, Y) по прямой вдоль оси X на единицу (фиг, 2) в точку А, Причем пбскольку начальное положение в точке Р по отношению к растру дискретизации (например к точке Р, ) определяется содержимым младших разрядов счетчиков 5 и Ь, т.е, их содержимое в точ ке Р соответствует поступлению |5Х2 и i5Y-2 импульсов, от начала интерполяции в точке Р до момента пересечения вертикали Р , Р. (фиг. 4) в Точке Л , соответствующе го увеличению на единицу числа на первом адресном входе блока 16 памя ти, с второго выхода блока 23 упра ения поступает (2 -5Х2 ) импульов. При изменении числа X на счетчике , соответствующем перемещению точки (X, Y) из точки Рц до точки А число а Выходе блока 16 памяти соответстует отсчету в точке Р , т.е. раво ZQJ, , так как старшие разряды счетика 5 при этом не изменяются. Посольку с второго выхода блока 23 правления на этом этапе на счетный ход счетчика 5 и вход синхронизации егистра 19 поступает ( Х-2 мпульсов, а перед началом интерполяии регистр 19 был обнулен, его соержимое при прохождении точкой (X, ) точки А равно (2.-S Х-2) - Z,, , В точке А содержимое регистра 19 тановится равным (2 - S Х-2)Zoo -ь6Х2 Хр,. К этому моменту блок 23 управления вырабатывает 2 импульсов, вследствие чего первый разряд счетчика 11 после прохождения точкой (X, Y) точки А устанавливает 1, выход элемента И 15 - в а импульсы с второго выхода блока 23 управления через элемент И 13 и ИЛИ 4 начинают поступать на вход реверсивного счетчика 6, который их суммирует, так как на его. управляющем входе по прежнему присутствует О с выхода второго разряда счетчика 11. На счетный вход счетчика 5 импульсы не поступают. Так как на этом этапе изменяется число Y, то движение точки (X, Y) происходит по вертикали из точки А в точку Б, в которой число в регистре 19 становится равным .(2 -SX 2-)Z +&Х.2.г„,3 + -ь (2 -5Y-2)Z, +&Y-2 -Z,,l . К моменту прохождения точки Б число поступивших импульсов составит 2 , и на выходе первого разряда счетчика 11 устанавливается О, а на выходе второго - 1. которая, пройдя на управляющие входы счетчиков 5 и 6, реверсирует направление счета. Следующие 2 импульсов со второго выхода схемы управления поступают на счетный вход счетчика 5, а :точка (X, Y) перемещается по горизонтали из точки Б в точку В и число в регистре 19 увеличится на 5X-2 Z,, + (.2)Zj . Четвертая серия из 2 импульсов соответствует перемещению из точки Б.в точку Р, . Число в регистре 19 увеличивается еще на + (2 -SY-2)-Z Л и становится равным выражению в фигурных скобках в выражении (6), Одновременно накопление происходит и в регистре 21, однако занесение информации в него (по сигналу на входе записи) осуществляется по отрицательному фронту выходного сиг нала делителя 12. Поскольку емкость этого счетчика равна 2, накопление числа с выхода регистра 17 в регист 21 происходит по окончании каждой серии из 2 импульсов, т.е. при про хождении точкой (X, Y) точек А, Б, В и Ру. Число в регистре 17 в эти так как перед начало 10 00, интерполяции содержимое регистров обнуляется, то при прохождении точк р в регистре 21 накопляется величи на (Z,, + Z,, + Z -t- Z,,). к моменту окончания последней се рии из 2 импульсов их общее число с начала интерполяции составляет 4 -Поскольку емкость делителя равна 2, последний импульс серии переведет его в нулевое начальное состояние. Первый, второй и третий разряды счетчика 11 устанавливаются в состояния соответственно О и 1. Появление единичного уровня на выходе третьего разряда счетчика 11, соединенного с входом признака окончания цикла блока 23 управления деблокирует D-триггер 33 1 с D ин формационного входа этого триггера переписьшается на выход по положительному фронту очередного (4 х 2 + 1)-го импульса генератора 34 (фиг. -5). При этом дальнейшее форми рование импульсов на втором выходе блока 23 управления прекращается, а на первом ее выходе устанавливается уровень 1, разрешающий прохождени сигналов с входов 24-27 через элеме ты И 1, 2, 7 и 8. По первому импульсу на втором выходе блока 23 управления в регистре 19 присутствует О по второму импульсу серии - число ZOQ и т.д.; по последнему (4 х 2 + 1)-му импульсу в регистр 19 заносится последний отсчет с выхода сумматора 18. Накопленная в этом регистре сумма 4 2 суммирований становится численно равна выражению в фигурных скобках формулы (6). На выход 30 устройства поступает число с вычитателя 22. На вход вычитаемого вычитателя 22 поступает величина (Z + Z-, + Z выхода регистра 21 со сдвигом в сторону младших разрядов, соответствующим делению на четыре; на вход уменьшаемого - число с в 5кода регистра 19, равное значению выражения в фигурных скобках в формуле (6) со сдвигом, соответствующим делению на . Тогда на выходе вычитателя 22 и выходе 30 устройства имеется число, соответствующее первой части формулы (6) - расчитанный интерполяционный отсчет в точке Р (Х, Y). На этом цикл интерполяции в точке Р заканчивается. Устройство готово к вводу коордийат очередной точки интерполяции. Продолжительность всего вычислительного процесса составляет 4x2 2() периодов тактовой частоты генератора 34. После завершения интерполяции в очередной тЪчке Р (X, Y), устройство переходит в режим ввода координат следующей точки (Х, Y ). При этом на втором выходе блока 23 управления импульсы отсутствуют, поддерживается нулевой уровень (на выходах элементов И ТЗ, 15 О), а на 13, 15 первом - уровень 1. Подавая импульсы на входы 24 и 25 внешнее устройство, в качестве которого могут быть использованы, например, дифференциальные числоимпульсные датчики каких-либо измеряемых параметров, осуществляет изменение координат X и Y, связанное с. переходом к следующей точке интер- поляции. Направление изменения координат определяется состоянием входов 26 и 27, также контролируемых внешним устройством. Количество импульсов, подаваемых на входы 24 и 25 устройства, опрееляется изменением координат при ереходе к следующей точке интерпояции: . N 2lx - X(; N, - Yl, причем очередным вводом координаты предыдущей точки (содержимое счетчи ков 5 и 6) сохраняются. Это позволя ет получить значительное сокращение времени ввода предлагаемого устройства при интерполяции для массива точек (Xj, Yj), расположенных на изображении большого формата. Это связано с тем, что средняя вели чина изменения координат при перехо де от интерполяции в одной точке к следукнцей меньше средней величины самых координат, определяющей время ввода при отсутствии хранения координат предьщущей точки. Формула изобретени 1. Устройство для интерполяции, содержащее два элемента И, два элемента ИЛИ, два реверсивных счетчика, делитель частоты, счетчик управ ления, блок памяти, три регистра, первый сумматор и блок управления, первые входы первого и второго элементов И являются входами первой и второй координаты устройства соответственно, выходы первого и второг элементов И подключены к первым вхо дам первого и второго элементов ИЛИ соответственно, выходы которых подключены к счетным входам первого и второго реверсивных счетчиков соответственно, выходы групп старших разрядов которых подключены к адрес ным входам первой и второй группы блока памяти, выход которого йодклю чен к информационному входу первого регистра, выход которого подключен к входу первого слагаемого первого сумматора, выход которого подключен к информационному входу второго регистра, выход которого подключен к входу второго слагаемого первого сумматора, отличающееся тем, что, с целью повьппения быстродействия устройства за счет аппарат ной реализации интегрирования по контуру и запоминания координат точки интерполяции, в него введены второй сумматор, вычитатель, третий и четвертый элементы ИЛИ, с третьег по шестой элементы И и элемент НЕ, первые входы третьего и четвертого элементов И являются входами реверс направления первой и второй координаты устройства соответственно, выходы третьего и четвертого элементов И подключены к первым входам третьего и четвертого элементов ИЛИ соответственно, выходы которых подключены к. входам управления режимом счета первого и второго реверсивных счетчиков соответственно, входы сброса котррьк соединены с входом начальной установки адреса устройства, вход запуска которого соединен с одноименным входом блока управления, первый выход которого подключен к вторым входам с первого по четвертьй элементов И, второй выход блока управления подключен к входам синхронизации первого и второго регистров, первым входам пятого и шестого элементов И и к входу делителя частоты, выход которого подключен к входу синхронизации третьего регистра и счетному входу счетчика управления, выход первого разряда которого подключен к второму входу пятого элемента.И и через элемент НЕ к второму входу шестого элемента И, выходы пятого и шестого элементов И подключены к вторым входам второго и первого элементов ИЛИ соответственно, выход второго разряда счетчика управления подключен к вторым входам третьего и четвертого элементов ИЛИ, выход третьего разряда счетчика управления подключен к входу признака окончания цикла управления, третий выход которого подключен к входам сброса счетчика управления, делителя частоты и с nepisoro по третий регистров, выход первого регистра подключен к входу первого слагаемого второго сумматора, выход которого подключен к информационному входу третьего регистра, выход которого подключен к входу второго слагаемого второго сумматора и со сдвигом на два разряда .в сторону младших разрядов к входу вычитаемого вычитателя, выход второго регистра подключен со сдвигом на (т 1) разрядов в сторону младших разрядов к входу уменьшаемого вычитателя, где m - число разрядов делителя частоты, выход вычитателя является выходом устройства. 2. Устройство по п. 1, о т л и чающееся тем, tiTo блок управления содержит генератор импульсов.

элемент ИЛИ-НЕ и три триггера, входы синхронизации которых соединены с первым входом элемента ИЛИ-НЕ и выходом генератора импульсов, инверсный вход установки первого триггера является входом запуска блока и соединен с инверсным входом сброса второго триггера, информационный вход которого подключен к выходу первого триггера, информационный вход которого подключен к шине информационноsy

Afjraffufue fHiSp/f tif фи&2

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

Cvefnvt/f(5, e/4o/ ufue

Sx

jUffsra u/t/f