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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU» 1264202 А1 (51)4 G 06 F 15/353

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К ASTOPCHOMY СВИДЕТЕЛЬСТВУ (54) УСТРОЙСТВО ДЛЯ ИНТЕРПОЛЯЦИИ (57) Изобретение относится к области вычислительной техники и позволяет сократить время выполнения интерполяции дискретизированных изображений за счет аппаратной реализации интегрирования по контуру и запоминания координат точки интерполяции.

Устройство содержит шесть элементов

И 1, 2, 7, 8, 13 15, четыре элемента ИЛИ 3, 4, 9, !О, два реверсивных счетчика 5, 6 счетчик управления

11, делитель частоты 12, элемент (21) 3833762/24-24 (22) 02. 01. 85 (46) 15.10.86. Бюл, Ф 38 (72) P,À.Âàèåöèàí, А;А.Александров, С.Г.Глотов, О.П.Гуляйкин и И.В.Шахматов (53) 681.325(088.8) (56) Заявка Великобритании

Ф 2100956, кл. Н 04 N 5/22, 1983.

Авторское свидетельство СССР

У 942040, кл. G 06 F 15/353, 1980.

Заявка Великобритании

У 1413045, кл. G 06 F 15/20, 1975.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

1264202

HK 14, блок 16 памяти, три регистра

17, 19, 21, два сумматора 18, 20, вычитатель 22 и блок 23 управления.

Блок 23 выполнен на триггерах 31-33, генераторе 34 импульсов и элементе

ИЛИ-HE 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 з.п. b-лы, 5 ил.

tni 1 (деление на 2 ), где m — число разрядов делителя 12.

Входами устройства являются входы

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

Блок 23 управления содержит двутактные D-триггеры 31-33, генератор

34 импульсов, элемент ИЛИ-НЕ 35.

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

Для удобства назовем функцию 2

f(x, у) изображением.

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

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

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

40 висит только от состояния старших разрядов счетчиков 5 и 6. Поэтому, 1не ограничивая общности, можно счи1264202 тать содержимое старших разрядов целой частью числа Х (либо Y), содержимое младших — дробной, т.е. размер элемента растра равен единице (размер всего растра на фиг. 2 составляет ЬхК).

На фиг. 3 изображены четыре ближайших к точке интерполяции Р„,(х, у) отсчета дискретизованного йзобра-,.— жения (фиг. ?): то

Z.. К(Р„), Z., К(Р„), Уравнение плоскости проходящей через отсчеты в точках (P,, P,,Р ) !5 следующее: Z = Z, + (Z., Z )6X+

+(Z — Z, )Ь У, (1) где BX и 8Y — числа на младших раз- 20 рядах счетчиков 5 и 6, не превосходящие единицы.

Аналогичные уравнения для плоскос- тей через точки (Р,, Р,, P, ), д следующие: о1 (Z» 1 ) (о

Ео1 )(1 -Б Х)э (2)

Z = Z„„+ (Z — Е,, )(1 -hX)+ 30

+ (Z,, Z„)(1 - SY), (3)

+ (Еоо Его ) (! ) +

+ (z„, — z, )hx. (4) .35

При линейной интерполяции по трем точкам (Р,, Р„, Р ) в качестве интерполяционного значения отсчета в точке (Х, Y) можно взять отсчет в этой точке уравнения (1);

Z„, =Z.. + (Z., Z..)6Х+

Аналогично, используя уравнения (2) и (4), можно построить отсчет

Е„ ... Е„ . Тогда за интерполяционное значение в точке (Х, Y) при интерполяции по четырем точкам (Z д Э

Е, Е, Е ) принимают:

1 1 0

Z= — (Z+Z+Z+Z)

4 4 1 м 4з

1 Г

i(е (1 Sx)+ z.bx)+

+(Ео1 (1 — SY) + Е„S Y l + (5)

+ е x + z (1 -6x)) + 55

+ СZ„SY + Ю„(1 -S Y})3

Домножив это выражение на 2 " (емкость младших разрядов счетчиков 5

I и 6), получают выражение, в соответствии с которым осуществляют вычисления:

2 = „ (Е,, (1 — bx 2 ) +ЕSX2)+(Е„(2-6Y2)+

+Z.hY2)+(Z„-5Õ2+Z,(2

--hX 2 )) + (Z,îhY 2 + Еда(21 — Ву z")j) — — (к.. + г., + z

+Е ). (6) Действительно, после установки реверсивных счетчиков 5 и 6 в состоя ние, соответствующее точке Р (х, у), Ц

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

Этот импульс устанавливает триггеры

31 и 32 в состояния "1" и "0" соответственно. На первом входе блока 23 управления присутствует уровень "1.", который устанавливается с момента окончания предыдущего цикла интерполяции (фиг. 5).

По положительному фронту очередного тактовогд импульса генератора

34 "0" с информационного входа триггера 3 1 переписывается на его выход, а на выход триггера 32 записывается

"1" с выхода триггера 3 1. По второму и последующим импульсам в триггер 32 .записывается "0" с выхода триггера 3 1. На третьем выходе блока управления 23 формируется положительный импульс (см. фиг. 5). Этот импульс устанавливает в нулевое состояние счетчик 11, делитель 12 и регистры 17, 19 и 21. С выхода третьего разряда установленного в "0» счетчика 11 уровень "0" поступает на вход признака окончания цикла блока 23 управления. С этого момента сигнал на первом выходе блока управления 23 устанавливается в нулевое состояние, что блокирует входы 2427 устройства и вызывает появление уровня "0" на входах элементов

ИЛИ 3, 4, 9 и 10.

Уровни сигналов на управляющих входах счетчиков 5 и б повторяют состояние второго разряда счетчика

12642

11. Так как последний обнулен, то счетчик 5 суммирует (нулевой уровень на входе управления) импульсы, поступающие с второго выхода блока 23 управления на его счетный вход

5 (фиг. 5) . На счетный вход счетчика

6 импульсы не поступают, так как элемент И 13 блокирован нулем на его втором входе, Каждый импульс на втором выходе 10 блока управления увеличивает содержимое счетчика 5 на единицу его младшего разряда. Одновременно увеличивается число в счетчике 11 ем; кость которого, как и младших разря дов счетчиков 5 и 6; равна 2

В интервале между импульсами число на выходе блока 16 памяти определяется старшими разрядами счетчиков

5 и 6. Это число заносится по фрон- 20 ту сигнала на входе синхронизации записи в регистр 17. Затем по фронту сигнала на входе записи происходит его накопление (добавление к прежнему содержимому) в регистре 19 25 с помощью сумматора 18, число на выходе которого перед очередной записью в регистр 19 равно сумме со-. ,держимого этого регистра и числа в

1 регистре 17. 30

После поступления с второго входа блока 23 управления первой серии из

2 импульсов содержимое младших разрядов счетчика 5 становится равным

35 исходному (так как их емкость равна

2 ), число на адресном входе блока

16 памяти, соединенном со старшими разрядами счетчика 5, увеличивается на единицу. Как следует из фиг. 4, где изображен участок растра точек отсчетов функции У(х, у), содержащий соответствует перемещению точки (Х, Y) по прямой вдоль оси Х на единицу

45 (фиг. 2) в точку А. Причем поскольку начальное положение в точке Р по отношению к растру дискретизации (например к точке P, ) определяется содержимым младших разрядов счетчиков 5 и Ь, т,е. их содержимое в точ50 ке Р„ соответствует поступлению

6Х 2 и 6У 2 импульсов, от начала интерполяции в точке P до момента пересечения вертикали P „, Р,, (фиг. 4) в точке A, соответствующе- 55 го увеличению на единицу числа на первом адресном входе блока 16 памяти, с второго выхода блока 23 управ02 ,ления поступает (2 — 3 Х 2 ") импульсов.

При изменении числа Х на счетчике 5, соответствующем перемещению точки ! (Х, Y) из точки Р„ до точки А число на выходе блока 16 памяти соответствует отсчету в точке P, т.е. равно 7,„,, так как старшие разряды счетчика 5 при этом не изменяются. Поскольку с второго выхода блока 23 управления на этом этапе на счетный вход счетчика 5 и вход синхронизации регистра 19 поступает (2 — 8Х 2 ) импульсов, а перед началом интерноляции регистр 19 был обнулен, его со,держимое при прохождении точкой (Х, Y) точки А равно (2 .- S Х 2 ). Z, В точке А содержимое регистра 19 становится равным ((2 — Я Х.2 )2„ +

+ 5 X 2 . /„ 1 . К этому моменту блок

23 управления вырабатывает 2 импульсов, вследствие чего первый разряд счетчика 11 после прохождения точкой (Х, Y) точки А устанавливается в "1", выход элемента И 15 — в

"0", а импульсы с второго выхода блока 23 управления через элемент

И 13 и ИЛИ 4 начинают поступать на вход реверсивного счетчика 6, который их суммирует, так как на его. управляющем входе по прежнему присутствует "0" с выхода второго разряда счетчика 11. На счетный вход счетчика 5 импульсы не поступают. Так как на этом этапе изменяется число Y то движение точки (Х, Y) происходит по вертикали из точки А в точку Б, в которой число в регистре 19 становится равным ((2 — 5X 2 )Z, +ЬХ 2 Z,j+

+ ((2 -дУ.2 )Е, + ЬУ-2 .Е,,)

К моменту прохождения точки Б число поступивших импульсов составит (13 + 1)

2, и на выходе первого разряда счетчика 11 устанавливается "0", а на выходе второго — 1". которая, пройдя на управляющие входы счетчиков 5 и 6, реверсирует направление счета.

Следующие 2 импульсов со второго выхода схемы управления поступают на счетный вход счетчика 5, а

;точка (Х, Y) перемещается по горизон тали из точки Б в точку В и число в регистре 19 увеличится на

1264202 (ЬХ2Z + (2 — 6Х2)Z)

Четвертая серия из 2 импульсов соответствует перемещению из точки

В в точку Р„,. Число в регистре 19 увеличивается еще на

Z„+ и становится равным выражению в фигурных скобках в выражении (6).

1О

Одновременно накопление происходит и в регистре 21, однако занесение информации в него (по сигналу на входе записи) осуществляется по отрицательному фронту выходного сигнала делителя 12. Поскольку емкость этого счетчика равна 2, накопление числа с выхода регистра 17 в регистре

21 происходит по окончании каждой

hl серии из 2 импульсов, т.е. при прохождении точкой (Х, Y) точек А, Б, В и Р . Число в регистре 17 в эти моменты равно соответственно Z »

Z,„, Z,, Z, так как перед началом

25 интерполяции содержимое регистров обнуляется, то при прохождении точки

P в регистре 21 накопляется величина (Е,„+ Е„„+ Е, + Е„).

К моменту окончания последней се- ЭО з рии из 2 импульсов их общее число с начала интерполяции составляет

4 х 2 . Поскольку емкость делителя 12 равна 2, последний импульс серии переведет его в нулевое начальное З5 состояние. Первый, второй и третий разряды счетчика 11 устанавливаются в состояния соответственно "0", "0". и "1". Появление единичного уровня на выходе третьего разряда счетчика,4О

11, соединенного с входом признака окончания цикла блока 23 управления деблокирует D-триггер 33 "1" с D информационного входа этого триггера переписывается на выход по положи- 45 тельному фронту очередного (4 х 2 +

+ 1)-ro импульса генератора 34 (фиг..5). При этом дальнейшее формирование импульсов на втором выходе блока 23 управления прекращается, а на первом ее выходе устанавливается уровень "1", разрешающий прохождение сигналов с входов 24-27 через элементыИ1, 2, 7и8.

По первому импульсу на втором вы- 55 ходе блока 23 управления в регистре

19 присутствует "0" по второму импульсу серии — число Z, и т.д,; по последнему (4 х 2 + 1)-му импульсу в регистр 19 заносится последний отсчет с выхода сумматора 18.

Накопленная в этом регистре сумма

4 2 суммирований становится численно равна выражению в фигурных скобках формулы (6) .

На выход 30 устройства поступает число с вычитателя 22. На вход вычитаемого вычитателя 22 поступает величина (Z + Z„+ Z» + Z, ) с выхода регистра 21 со сдвигом в сторону младших разрядов, соответствующим делению на четыре; на вход уменьшаемого — число с выхода регистра

19, равное значению выражения в фигурных скобках в формуле (6) со сдвигом, соответствующим делению на 2

Тогда на выходе вычитателя 22 и выходе 30 устройства имеется число, соответствующее первой части формулы (6) — расчитанный интерполяционный отсчет в точке Р„ (Х, Y).

На этом цикл интерполяции в точке P заканчивается. Устройство готово к вводу координат очередной точки интерполяции.

Продолжительность всего вычислим тельного процесса составляет 4 х 2 =

2 периодов тактовой частоты генератора 34.

После завершения интерполяции в очередной точке P (Х, Y), устройство переходит в режим ввода координат следующей точки (Х, Y ). При этом на втором выходе блока 23 управления импульсы отсутствуют, поддерживается нулевой уровень (на выхо. дах элементов И 13, 15 "0"), а на первом — уровень "1".

Подавая импульсы на входы 24 и

25 внешнее устройство, в качестве которого могут быть использованы, например, дифференциальные числоимпульсные датчики каких-либо измеряемых параметров, осуществляет изменение координат Х и У, связанное с переходом к следующей точке интерполяции. Направление изменения координат определяется состоянием входов 26 и 27, также контролируемых внешним устройством.

Количество импульсов, подаваемых на входы 24 и 25 устройства, определяется изменением координат при переходе к следующей точке интерполяции:

f 264202

10 направления первой и второй координаты устройства соответственно, выходы третьего и четвертого элементов

И подключены к первым входам третьего и четвертого элементов ИЛИ соответственно, выходы которых подключены к входам управления режимом счета первого и второго реверсивнык счетчиков соответственно, входы

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

Zp элементов И и к входу делителя часи з о б Р е т е " Я тоты, выход котоРого подключен к входу синхронизации третьего регистра и счетному входу счетчика управления, выход первого разряда которого подключен к второму входу пятого элемента И и через элемент НЕ к второму входу шестого элемента И, выходы пятого и шестого элементов И подключены к вторым входам второго и первого элементов ИЛИ соответственно, выход второго разряда счетчика управления подключен к вторым, входам третьего и четвертого элементов ИЛИ, выход третьего разряда счетчика управления подключен к входу признака окончания цикла управления, третий выход которого подключен к входам сброса счетчика управления, делителя частоты и с первого по третий регистров, выход первого регистра подключен к входу первого слагаемого второго сумматора, выход которого подключен к информационному входу третьего регистра, выход которого подключен к входу второго слагаемого второго сумматора и со сдвигом на два разряда,в сторону младших разрядов к входу вычитаемого вычитателя, выход второго регистра подключен со сдвигом на (m + 1) разрядов в сторону младших разрядов к входу уменьшаемого вычитателя, где ш — число разрядов делителя частоты, выход вычитателя является выходом устройства.

N = 2 IX — Х ; х

N = 2 tY - 1э

Формула причем очередным вводом координаты предыдущей точки (содержимое счетчиков 5 и 6) сохраняются. Это позволяет получить значительное сокращение времени ввода предлагаемого устройства при интерполяции для массива точек Р „(Х„, Y, ), расположенных на изображении большого формата.

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

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

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

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

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

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

1264202

/ PAPPY

B od 2

ЛмхоУ5 в .г r

Aired

Яма юУ/

Фие К

Составитель А.Ушаков

Техред М.Ходанич корректор Е.Сирохман

Редактор Л.Пчелинская

Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Заказ 5564/50

Производственно-полиграфическое предприятие,.г. Ужгород, ул. Проектная, 4