Линейный интерполятор

)5 605 В 9/3 Е ЕНИЯ ГОСУДАРСТЗЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОП РИТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗО К АВТОРСКОМУ СВИДЕТЕЛ(71) Ленинградский институт авиационного приборостроения(5 б) Авторское свидетельство СССРВ 1439534, кл. С 05 В 19/18,20.04.87,ЯО; 5381 6 А(57) Изобретение относится к линейным интерполяторам и может быть использовано в телевизионной технике всистемах интерактивной графики, вустройствах селекции видеосигналасложной формы и генераторах границспецэффектов на основе светового пера, а также в автоматике и вычислительной технике в устройствах графического отображения информации. Це1538166 Составитель А.АнТехред М,Дидык Гратилло Корректор О,ципл акт КНТ СССР роизводственно-издательский комбинат "Патент", г, Ужгород агарина, 10 Заказ 169 Тираж 659 ПодписноВНИИПИ Государственного комитета по изобретениям и открытиям 113035, Москва, Ж, Раушская наб д, 4/51538166лью изобретения является расширение области применения линейного интерполятора, Интерполятор содержит первый 1, второй 2, третий 3 блоки сум" мирования, первый 4, второй 5, третий 6 коммутаторы, блок 7 вычисления оценочной функции, четвертый коммутатор 8, регистр 9 оценочной функции, блок 10 формирования сигналов интерполяции, блок 11 элементов ИЛИ, блок 12 счетчиков адресных сигналов, блок 13 сравнения, блок 14 управления, блок 15 формирования адресов, блок 16 памяти, блок 17 выбора ширины линии и блок 18 стробирования, Введениеблоков формирования ацресов, памяти,выбора ширины линии, стробирования,а также новых связей в линейный интерполятор расширяет область его применения за счет возможности автоматического расширения интерполируемойлинии при одновременномустранениидефектов в точках сопряжения интервалов интерполяции путем формирования расширенной начальной точки интерполяции1 з.п. Ф-лы, 7 ил.Изобретение относится к линейным 20 интерполяторам, может быть использовано в телевизионной технике в системах интерактивной графики, в устройствах селекции видеосигнала сложной формы и генераторах границ 25 спецэффектов на основе светового пера, а также в автоматике и вычислительной технике, в устройствах графического отображения информации и является усовершенствованием устройст ва по авт. св. В 1439534,Целью изобретения является расширение области применения линейного интерполятора.На Фиг,1 представлена Функциональ ная схема линейного интерполятора; на фиг.2 - функциональная схема блока управления; на фиг,3 - временные диаграммы работы блока управления; на Фиг.4 - блок формирования адресов; 40 на Фиг.5 - блок памяти; на Фиг.б блок сравнения; на Фиг.7 - образование дефектов на изгибах расширенной линии (а) и способ их устранения Фигурой расширения начальной точки ли нии (б).Линейный интерполятор (фиг.1) содержит первый 1, второй 2, третий 3 блоки суммирования, первый 4, второй 5, третий 6 коммутаторы, блок 7 вычисления оценочной функции, четвертый коммутатор 8, регистр 9 оценочной функции,блок 10 Формирования сигналов интерполяции, блок 11 элементов ИЛИ, блок 12 счетчиков адресных сигналов, блок 13 сравнения, блок 14 управления, блок 15 формирования адресов, блок 16 памяти, блок 17 выбора ширины линии, блок 18 стробирования. Блок 14 (фиг.2) содержит делитель 19 частоты, первый мультивибратор 20, первый 21 триггер, элемент И-НЕ 22, первый 23 элемент И, второй 24, третий 25, четвертый 26 мультивибраторы, второй 27 элемент И, второй 28 триг" гер.Блок формирования адресов (фиг.4) содержит инвертор 29, элемент ИЛИ 30, элемент И 31, инвертор 32, триггер 33 и счетчик адресов 34.Блок памяти (фиг.5) содержит элемент 35 памяти (ПЗУ фигуры расширения) и элемент 36 памяти (ПЗУ линии расширения).Блок сравнения (фиг.6) содержит элементы 371, 37.2 сравнения, стробирующие элементы 38,1 и 38.2, триггеры 39.1 и 39.2 и элемент И-НЕ 40Интерполятор работает следующим образом. Элементарные перемещения в процессе интерполяции отрезка, заданного координатами начальных и конечных точек по оси Х (Ха и Хь) и У ( Уа и Уь), осуществляются на основании расчета в каждом такте интерполяции значения оценочной функции 1;, при этом, если 11; ) О, осуществляется элементарное перемещение по координатам Х и У (шаг Б.), если П; б О, осуществляется элементарное перемещение по координате с большим перемещением. Расширение отрезка линии ведется по координате с меньшим перемещениемйХ = (Ха Хь) и ЬУ = (а 8) при этом расширение начальной точки интерполяции выполняется фигурой .расширения (фиг.7 б).5Перед выполнением первого шага интерполяции в первом 1 и втором 2 блоках суммирования происходит вычи" тание поступающих на их входы кодов начальных и конечных значений координат Х и Т соответственно. На выходах данных первого 1 и второго 2 блоков суммирования выставляются значения разностей ЬХ и 67, на знаковых вы" ходах - значения переносов Р и Рч разностейЬХ и ЬУ соответственно,Разности 6 Х и О по координатам Х и 7 с выходов данных первого 1 и второго 2 блоков суммирования поступают яа входы третьего блока 3 суммиройания, осуществляющего операциюЕЬХ У.Одновременно, коды ЬХ и 7 поступают на соответствующие входы первого коммутатора 4, который пропускает на выход меньшее (М) из ЬХ и ЬУ по сигналу переноса Р со знакового,.выхода третьего блока 3 суммирования, вычисляющего значение АЕ.Четвертый коммутатор 8 предназначен для осуществления первого шага алгоритма интерполяции. В качестве начального значения оценочной функ-. ции Ч выбирается значение меньшего (М) из ЬХ и ЬУ, выставленное на выходе первого коммутатора 4. Знак Рд для первого шага интерполяции вырабатывается в коммутаторе 8 в соответствии с правилом: М ) О; Р = 1; М = О;Дальнейшие значения оценочной функции рассчитываются следующим образом:П;, ) О (Р=1); П, щП-ЬЕ 1 Ц,с О (Р= О); и, = М - Ц-,.1.После поступления на вход блока 14 управления сигнала разрешения интерполяции (СРИ) на его втором выходе формируется сигнал Р, который записывает в блок 12 счетчиков адресных сигналов значения координат Х 1 и Уц начальной точки интерполяции и сбрасывает триггеры 39.1 и 39.2 в блоке 13 сравнения. Одновременно на четвертом выходе блока 14 управления формируется сигнал Р, который подключает сигналы с выходов первого коммутатора 4, поступающие на вторые входы четвертого коммутатора 8, к входу данных регистра 9 оценочной функции. На знаковый вход регистра 9 поступает сигнал Р, выработанный в соответствии с приведенным правилом, 6Эти сигналы будут записаны в регистр9 по сигналу Га с пятого выхода блока 14 управления,Таким образом, интерполятор полностью подготовлен к выполнению первого шага интерполяции. В то же время, на восьмом выходе блока 14 управления сформирован сигнал Г 1 С, который блокирует генерацию управляющихпоследовательностей Рц и Р в блоке14, запрещая процесс интерпоцяции,и разрешает работу элемента 35 памяти (ПЗУ фигуры) в блоке 16 памяти.При этом на вторые адресные входыблока 16 памяти с выходов блока 15формирования адресов поступают теку 166 51 О15 щие адреса точек фигуры расширения, а на первые адресные входы блока 16 с выхода блока 17 выбора ширины линии - постоянный для заданной ширины линии код расширения. Блок 15 форми 20 рования адресов производит последовательную выборку адресов, по которымв элементе 35 памяти "зашиты" коды 25 расширения, В каждый момент временикоды адреса с выхода блока 15 и кодрасширения с выхода блока 17 образуют адрес, выбирающий из элемента 35памяти "зашитую" в него информацию онаправлении перехода от одной точки 30 фигуры расширения к последующей, После выбора из элемента 35 памяти всейинформации о данной (определенной кодом расширения) фигуре расширения на первом выходе блока 16 вырабатывается сигнал, блокирующий генерацию адресов в блоке 15 формирования адресов,40Расширение точки интерполяции посигналу Р 1 С с блока 14 управления производится ромбом (фиг.7 б). Выбор ромба в качестве фигуры расширения точки обусловлен тем, что наряду с простотой формирования он обеспечивает достаточное качество устранения дефектов при изменении направления интерполируемой линии по сравнению с идеальной фигурой расширения - кругом, Расширение линии в процессе интерполяции осуществляется по сигналу ЫЖЕ с седьмого выхода с блока 14 управления по информации, считываемой из элемента 36 памяти, Процесс считывания информации из элемента 36 .памяти аналогичен описанному процессу считывания информации иэ элемента 35 памяти. Фигурой расширения в данном случае является линия, длина ко1538166 мирование на своих выходах импульсныхпоследовательностей для управленияблоком 12 счетчиков адресных сигналов, Управляющие импульсные последовательности формируются в блоке 10из сигнала с частотой Рц, поступающего на его четвертый вход с первоговыхода блока 14 управления, Управляют формированием выходных импульсныхпоследовательностей сигналы переносаР, Р 9, Р, Р с выходов соответственно первого 1, второго 2, третьего . 3 блоков суммирования, а также с зна"кового выхода регистра 9 оценочнойфункции. Сигнал Рч стробирует сигнал Рц для получения последовательности в канале меньшей координатнойразности, Сигнал Р,переключает коммутатор в блоке .10 таким образом,чтобы в канал большего проходили всеимпульсы Рв, а в канал меньшегопростробированные Рч. Сигналы Р и Росуществляют выбор выхода блока 10, 5 на котором появится выходная последовательность импульсов, управляющаяработой блока 2 счетчиков адресныхсигналов.В промежутках времени между им-пульсами Рц будет производиться расширение каждой интерполированной точки линией расширения, сформированной . по указанному правилу (длина линиирасширения равна толщине расширяемойлинии, а ее направление параллельнооси координаты с меньшим приращением).Расширение линий осуществляется подачей сигнала ЬИЕ с седьмого выходаиз блока 4 на третий вход блока 16памяти, а также сигналом Р со знакового выхода третьего 3 блока суммирования,. Сигнал Р определяет направление, вдоль которого будет расположена линия расширения. Сам же процессрасширения аналогичен расширению начальной точки интерполяции Ха, 7 впо сигналу Р 16.1 О 15 кения, блокируя выдачу сигнала "Оста ляции будут генерироваться управляю 35 40 45 50 55 торой равна толщине расширенной линии, а.направлена она параллельнооси координаты с меньшим приращением,Информация с вторых выходов блока 16 памяти поступает на первые входы блока 18 стробирования и в виде импульсов с длитЕльностью, равной длительности стробирующих импульсов Р т,поступает на вторые входы блока 11элементов ИЛИ, проходит через него и поступает на счетные входы блока 2счетчиков адресных сигналов. Выходные сигналы блока 12 счетчиков будут являться кодами координат точек, образующих в совокупности фигуру расширения. Сигнал Р 1 С с восьмого выхода блока 14 управления также поступает на седьмой вход блока 13 сравнов в случае, когда интервал интериполяции мал и координаты конечной точки интерполяции Хь и У оказываются внутри фигуры расширения.После того, как будет расширена начальная точка интерполяции с координатами Х р и 7 е, блок 14 управления снимет сигнал Р 16, выставит сигнал Ь 1 БЕ иразрешит процесс интерпощие последовательности Р и Р ). Попервому импульсу Р из блока 14 в регистр 9 оценочной функции будут записаны начальное значение функции 0 и знак Р. После выполнения первого шага интерполяции четвертый коммутатор 8 подключит выходы данных и знака блока 7 вычисления оценочной функции к входам данных и знака регистра9 оценочной функции. Работой блока 7вычисления оценочной функции управляют второй 5 и третий 6 коммутаторы, переключаемые сигналом переноса Р со знакового выхода регистра 9 оценочной функции. В том случае, когдаР, 1 (П ) О), на вторые входы блока 7, соединенные с выходами третьего коммутатора 6, проходит результатпредыдущего цикла вычислений, а напервые входы, соединенные с выходамивторого 5 коммутатора, проходит кодразности Ь 2. При Р = О (70) напервые входы блока 7, соединенные свыходами второго 5 коммутатора, проходит код оценочной функции Ч, а навторые входы проходит код И меньшегоиз ЬХ и П с выходов третьего 6 коммутатора. Блок 10 формирования сигналов интерполяции осуществляет форПосле того, как на выходах блока 12 счетчиков адресных сигналов будет сформирован код координаты конечной точки интерполяции Хте = Хь и те = У, на выходе блока 13 сравтекнения будет сформирован сигнал оста- нова, который запретит дальнейший процесс интерполяции, Последняя точка Хв, Уе будет расширена линией расширения и интерполятор будет ждать поступления новых координат Ха, Уа1538166Х 41, У и сигнала разрешения интерполяции на его входы.Блок 13 сравнения служит для остановки процесса интерполяции при достижении конечного значения коор 5 динат Хь, У. Он состоит из двух 0+1. разрядных элементов 37,1 сравнения по координате Х и 37.2 по координате У (фиг.б). На первую группу 0 входов элементов сравнения поступает Н-разрядный код значения текущей координаты с выходов счетчиков блока 12, а на вторую группу входов элементов сравнения поступает код конечно го значения координаты интерполяции. На один из Рвходов заведен постоян ный уровень логической "1", а другой из 1 Э 1 входов (седьмой вход блока 13 сравнения) соединен с восьмым выходом 20 блока 14 управленияКогда в блоке 14 управления формируется сигнал Р 1 С (производится расширение начальной точки интерполяции), на вторых входах элементов сравнения выставляется код, 25 превышающий код конечного значения координаты интерполяции на, единицу И+1 (старшем) разрядеТаким образом, исключается возможность срабатывания элементов 37.1 и 37.2 сравнения при 30 расширении начальной точки интерполяции. Это может произойти в том случае, когда расстояние между начальной и конечной точками интерполяции меньше половины выбранной ширины ли 35 нии (конечная точка интерполяции попадает в область фигуры расширения начальной точки интерполяции). После окончания расширения начальной точки сигнал Р 1 С снимается и элементы 3.1 40 и 37,2 сравнения работают только по Б разрядам (И+ разряды совпадают). При совпадении кодов текущего и конечного значений координат на выходе элементов сравнения формируются сиг налы, которые через соответствующие элементы И 38.1 и 38.2, служащие для блокировки входов триггеров 39.1 и ,39,2 от импульсных помех в моменты переключения разрядов счетчиков блока 12 адресных сигналов, взводят триггеры 39.1 и 39.2. Необходимость использования триггеров возникает в связи с возможностью неодновременного достижения конечной координаты по каналам Х и У. Сигналы с выходов триг 55 геров 39.1 и 39.2 суммируются на элемента И-НЕ 40 и поступают на первый вход блока 14 управления. В начале 10следующего такта интерполяции триггера сбрасываются в "0" по сигналу с. второго выхода блока 14 управлений.Блок 14 управления служит для синхронизации работы всех блоков интерполятора и работает следующим образом.Сигнал разрешения интерполяции поступает на вход первого 20 мультивибратора (фиг,2). На выходе этого мультивибратора Формируется импульс длительностью не менее чем время, необходимое для расширения начальной точки интерполяции фигурой расширения максимального размера, Выходной импульс мультивибратора 20 является сигналом РТС для управления блоком 13 сравнения и блоком 1 б памяти. На элементе И-НЕ 22 осуществляется Формирование сигнала ЫИЕ (выход 7 блока 14 управления) из сигнала РХС и внешнего сигнала останова, поступающего из блока 13 сравнения. Сигнал ЫИЕ разрешает работу интерполятора и расширение интерполируемой линии. Первый триггер 21 служит для привязки начала сигнала ЫИЕ, поступающего на второй вход первого 23 элемента И, к фронту тактовой частоты Гг. На вход делителя 19 частоты поступает внешний сигнал тактовой частоты РтКоэФфициент деления делителя 19 частоты выбирается исходя из двух соображений. Во-первых, необходимо, чтобы интерполятор работал синфазно с внешним ОЗУ, в которое записывается сигнал по координатам интерполируемых точек. Во-вторых, периода времени,. равного периоду частоты Гт, должно быть достаточно для расширения точки интерполируемой линии до максимальной ширины. Первый 23 элемент И разрешает прохождение частоты Гт на выходы второго 25 и третьего 26 мультивибраторов при наличии сигнала ЫИЕ. Второй 25 мультивибратор работает по заднему, а третий 26 мультивибратор - по переднему фронтам(частоты Р . Импульсные последовательтности с частотами Гц и Гс сдвинуты друг относительно друга на время, необходимое для расчета направления шага в блоке 7 вычисления оценочнбй функции и используются: Г - для управления регистром 9 оценочной функции, а Г - для формирования сигналов интерполяции в блоке 10.Второй элемент И 27 запрещает прохождение импульсов Г во время имадресные входы блока 16 поступает код,ширины линии с выхода блока 17 выбораширины линии. Сочетания кодов адресаи кодов ширйны образуют совместныйадресный код элементов памяти, по которому происходит выборка данных, Физически это означает следующее.При построении фигуры расширениякаждой точке ее составляющей присваивается порядковый номер. Для различных Фигур расширенияпод однимпорядковым номером находятся точки сразличным местоположением в фигуре 15 расширения, Для выбора Фигуры расширения служит код ширины. Перебираякоды адреса при Фиксированном кодеширины, на выходе элементов памятиполучим коды данных, которые пред" 20 ставляют собой сигналы единичного приращения по координатам Х и У для управления счетчиками блока 12 адресных сигналов, Таким образом, по кодамданных в блоке 12 будут сформированы.25 координаты точек, составляющих Фигуру расширения, Сигналы, поступающиена третий и пятый управляющие входыблока 16 памяти, осуществляют выборэлементов 35 и 36 памяти. Когда на 30 седьмом выходе блока 14 управлениясформирован сигнал 1.1 ИЕ, происходитвыбор элемента 36 памяти (ПЗУ линии),а когда на восьмом выходе блока 14сформирован сигнал Р 1 С - происходитвыбор элемента 35 памяти (ПЗУ фигуры).Это обеспечивает подачу соответствующих управляющих сигналов (длярасширения линии или фигуры соответственно) на счетные входы блока 12адресных сигналов. На старший адресный вход элемента 36 памяти поступает сигнал Р со знакового выхода третьего 3 блока суммирования, С помощью этого адресного сигнала осуществляется формирование управляющих сигналов или для счетчика по координатеХ, или по У блока 2 счетчиков адресных сигналов.Так как точки интерполируемой линии расширяются линией, длина которой 50равна толщине расширенной линии. анаправлена она параллельно оси координаты с меньшим приращением, то спомощью сигнала Р находится координата с меньшим приращением (Р =1,ХУ; Р =О, Х ( У).Элементы 35 и 36 памяти запрограммированы таким образом, что послеформирования управляющих импульсов 11 1538166 пульсов Рл. Сигнал разрешения интерполяции поступает также и на четвертый мультивибратор 26, который формирует импульс Р на втором выходе блока 14. управления. По сигналу Р происходят начальная установка счетчиков,в блоке 12 счетчиков адресных сигналов и сброс триггеров 39.1 и 39.2 в блоке 13,сравнения (Фиг.6). Импульс Р также взводит второй 28 триггер, выходной сигнал Р которого поступает на четвертый выход блока 14 управления и является управляющим сигналом для четвертого коммутато.ра 8.Блок 15 формирования адресов работает следующим образом.Импульс Р,1, поступающий на первый вход блока, инвертируется на инверторе 29 и поступает на первый вход элемента ИЛИ 30 (Фиг. 4), на второй вход которого поступают импульсы Ри. На выходе элемента ИЛИ 30 формируются сигнал сброса для счетчика 34 адресов и через инвертор 36, сигнал начальной установки для триггера 33., ПЬследовательность импульсов Рто поступает на первый вход элемента И 34, который пропускает последовательность Рто на счетный вход счетчика 34адресов во время, когда на втором входе элемента И 31, соединенном с выходом триггера 33, присутствует разрешающий сигнал, По сигналу ВТОР с выхода блока 16 памяти происходит сброс триггера 33. На его выходе появляется сигнал, .запрещающий прохождение последовательности Ртк через элемент И 31. Таким образом, сброс счетчика 34 адресов осуществляется импульсом Р перед циклом генерации адресов для расширения начальной точки интерполяции и каждым импульсом Р перед циклом генерации адресов для, расширения каждой точки интерполируемой линии. Работой счетчика 34 адресов управляет триггер 31. Выходные сигналы счетчика 34 адресов являются сигналами адреса для блока 16 памяти.Блок 16 памяти служит для формирования управляющих импульсов для счетчиков блока 12 при расширении и работает следующим образом.На вторые адресные входы блока 16 памяти (Фиг.5) поступают адреса точек Фигуры расширения с выхода блока 15 Формирования адресов, На первыедля блока 12 на первом выходе блока 16 появляется сигнал ВТОР (пусть для расширения необходимо Я адресов, тогда.на 8+1 адреса на выходе блока 16 памяти появится сигнал ЯТОР).5Блок 17 выбора ширины линии служит для задания кода ширины линии на адресных входах блока 16 памяти и представляет собой шифратор, преобра О зующий позиционный код в двоичный.Блок 18 стробирования служит для стробирования выходных сигналов блока 16 с целью устранения импульсных помех в моменты переключения адресов 15 и может быть выполнен на элементах И,Таким образом, введение новых блоков и связей расширяет область применения линейного .интерполятора за счет возможности автоматического.расшире О ния интерполируемой линии при одно- временноМ устранении дефектов в точках сопряжения интервалов расширенной начальной точки интерполяции.25формула изобретения 1. Линейный интерполятор,по авт,св, У 1439534, о т л и ч а ю щ и й -с я тем, что, с целью расширения об О ласти применения, в него введены блок выбора ширины линии, блок формирования адресов, блок памяти, блок стробирования и блок элементов ИЛИ, первая группа входов которого подключена к выходам блока формирования сигналов интерполяции, вторая группа входов подключена к выходам блока стробирования, а выходы - к счетным входам блока счетчиков адресных сигналов, 40 при этом выходы блока выбора ширины линии соединены с первой группой адресных входов блока памяти, втораягруппа адресных входов которого подключена к выходам блока формирования адресов, первый и второй входы блока формирования адресов подключены соответственно к первому и второму выходам блока управления, а третйй вход объединен со стробирующим входом блока стробирования и подключен к50 шестому выходу блока управления, седьмой выход блока управления подключен к третьему адресному входу блока.памяти, четвертый адресный вход которого соедийен со знаковым выходом третьего блока суммирования, а управляющий вход блокирования соединен сседьмым входом блока сравнения ивосьмым выходом блока управления,первый выход блока памяти подключенк четвертому входу блока формирования адресов, а остальные подключенысоответственно к информационным входам блока стробирования,2, Интерполятор по п,1, о т л и -ч а ю щ и й с я тем, что блок управления содержит делитель частоты,первый, второй, третий и четвертыймультивибраторы, первый и второйэлементы И, первый, второй триггерыи элемент И-НЕ, при этом входы первого и четвертого мультивибраторовобъединены и являются входом разрешения интерполяции блока, выход первого мультивибратора соединен с первым входом элемента И-НЕ и являетсявосьмым выходом блока, второй входэлемента И-НЕ является входом останова блока, выход элемента И-НЕ подключен к информационному входу первого триггера и является седьмым выходом блока, выход делителя частотысоединен с первым входом первого элемента И, второй вход которого соединен с выходом первого триггера, авыход - с входами второго и третьегомультивибраторов, причем выход второго мультивибратора является пятымвыходом блока, инверсный выход третьего мультивибратора подключен кпервому входу второго элемента И иявляется третьим выходом блока, прямой выход третьего мультивибратораподключен к сбросовому входу второго триггера и является первым выходомблока, выход четвертого мультивибратора подключен к установочному входувторого триггера и является вторымвыходом блока, вход делителя частотыподключен к входу синхронизации первого триггера, второму входу второгоэлемента И и является входом тактовой частоты блока, выходы второготриггера и второго элемента И являются соответственно четвертым и шестымвыходами блока.