Генератор изображений

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИРЕСПУБЛИК 15 О Об Р 15/ НИЕ .ИЗОБРЕТЕНИЯ П Яфщг;ПЯГЦД 1. слитель оров е ре- изобДля стве ение очнои электр И. Вяткин,азурок,н 19 я квыч ено для оизведення ремени, Цель нформативноображения. рический ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОРСИОМУ СВИДЕТЕЛЬСВ 1(71) Институт автоматикиметрии СО АН СССР(57) Изобретение относиттельной технике и преднацифрового синтеза и воспизображений в реальномизобретения - повышениести формируемого кадра иГенератор содержит геоме 2процессор 1 и конвейерный вычииз однотипных клеточных процесс2, осуществляющих преобразованибер многоугольников в элементражения телевизионного растра,преобразования в растр в устроГиспользовано рекурсивное подделэкрана на клетки с помощью клет га процессора 2, содержащего сумматор4, делитель на два 5, селекторы пересеченных 8, внутренних 9, суммы 11клеток, узел 16 приоритета и блок 13памяти масок. Вычисление занятых многоугольником клеток по точкам пересечения его ребра с краями и серединойклетки, определение ребер, принадлежащих к клетке, с помощью узла 16,маскирование многоугольников в каждомиз процессоров 2 конвейера позволяетсократить время на обработку каждогомногоугольника при достаточной простое используемого устроиИзобретение относится к вычислительной технике, а именно к разделу машинной графики, и может быть использовано для моделирования окружающей обстановки с помощью ЭВМ в реальном времени при проектировании либо в различных типах тренажеров в качестве систем визуализации.Цель изобретения - повышение информативности Формируемого кадра изображенияНа фиг. 1 приведена структурная схема генератора; на Фиг. 2 - способ задания ребер для обработки клеточным 15 процессором, на Фиг. 3 - подделение клетки в клеточном процессоре; на фиг. 4 - схема селектора пересеченных клеток; на Фиг. 5 - схема селектора суммы клеток; на фиг,б - схема селектора внутренних клеток; на ,Фиг. 7 - пример многоугольника, формирование позиционных кодов для которого приведено в таблице; на фиг. 8 схема блока памяти масок клеточного процессора; на Фиг. 9 - схема узла приоритета.Генератор (фиг. 1) содержит геометрический процессор 1 и процессор формирования элементов изображения, состоящий из конвейерного вычислителя, выполненного на клеточных процессорах 2, каждый из которых содержит входной регистр 3, сумматор 4, делитель на два 5 блок 6 памяти позиционных коЭ35 дов, выход 7 кода внутренних клеток, селектор 8 пересеченных клеток, селектор 9 внутренних клеток, выход 10 кода суммы клеток, селектор 11 суммы клеток, выход 12 кода маски, блок 13 памяти масок, выход 14 селектора 9, выход 15 селектора 8 и узел 16 приоритета. Клеточные процессоры 2 соединены через блоки буферной памяти, выполненные в виде двух узлов 17 переключаемой памяти, В клеточном процессоре 2 обозначены также выход 18 узла 16, выходы 19 и 20 первой и второй групп входного регистра 3, выход 21 селектора 11, В конвейерном вычи 50 слителе обозначены вход 22 и выходы 23 адреса клетки и признака готовно- . сти маски клеточного процессора 2. Кроме того, каждый клеточный процессор 2, начиная с второго, содержит узел 24 формирования признака готов 55 ности маски, Процессор формирования элементов изображения содержит также фильтр 25, смеситель 26, вычислитель 27 цвета и блок 28 буферной памятиэлементов изображения, Генератор подключается через цифроаналоговые преобразователи 29 к отображающему устройству 30.Селектор 8 пересеченных клеток(Аиг. б содержит блок 36 элементовИ-НЕ, регистр 37 и ключ 38.Блок 13 памяти масок (фиг. 81 содержит узел 39 памяти типа "первымвошел, первым вышел", дешифратор 40,регистр 41, мультиплексор 42, узел43 оперативной памяти, узел 44 управления записью, управляемый инвертор45 и регистр 46.Узел 16 приоритета (фиг, 9) содержит группы 47 и 48 регистров и схему49 приоритета.Генератор работает следующим образом.В генераторе в качестве элементаразложения при преобразовании многоугольников в элементы изображения(ЭИ) телевизионного раствора используется уменьшающаяся от уровня куровню в четыре раза клетка, первоначальный размер которой равен площадиэкрана отображающего устройства 30.Количество уровней подделения определяется используемым форматом разложения в растр и точностью фильтрацииизображения. Фильтрация используетсяпля устранения дефектов, возникающихпри квантовании изображений, и заключается в подделении ЗИ растра на более мелкие части с последующим вычислением площади, занимаемой многоугольником в каждом ЭИ. На каждомуровне происходит определение занятыхмногоугольником клеток и сравнение ихс маской, сформированной от предыдущих многоугольников. Если клетка,в которой лежит текущий многоугольник,оказалась полностью занята предыдущими многоугольниками, то она на следующий уровень обработки не поступает,Таким образом, процесс подделения осуществляется в виде квартернарного де"рева и реализован с помощью конвейераоднотипных клеточных процессоров.Число процессоров определяется количеством уровней подделения и конечным5 15222 размером клетки, до которой осуществляется разложение многоугольника.Из геометрического процессора 1 поступают многоугольники в прямом приоритетном порядке, что позволяет5 сократить время обработки закрытых частей многоугольников за счет использования многоуровневого маскирования. Общепринятое описание многоугольников в виде набора вершин внданном устройстве заменено описанием набора линий, проходящих через ребра многоугольника и заданных их пересечениями с краями экрана: Х , Х- с 151 верхней и нижней границами экрана в случае, когда ребра вертикальные (наклон больше 45); У 1, У - с левой и правой границами экрана в случае горизонтальных ребер (с наклоном меньше 45 ) (Фиг. 2). Такое задание позволяет сократить по сравнению с прототипом число выполняемых операцийдля определения элементов, занятых обрабатываемым многоугольником, и ис ключить из обработки случаи, связанные с образованием невыпуклых многоуголь-ников, Невыпуклости при задании многоугольников вершинами могут образовываться за счет неточности вычислений и округления координат, поступающих из геометрического процессора 1.На вход первого клеточного процессора 2 поступают ребра многоугольников, заданные пересечениями с краями экрана. Ребра с соответствующими признаками записываются во входные регистры 3 клеточного процессора 2. За; тем вычисляется середина ребра по Формулам: 40 Х 1+ Х 2 +Х2 2- или У245 Эти вычисления осуществляют сумматор 4 и делитель на два 5, реализованный монтажным сдвигом. Все клетки, образованные при обработке многоугольников, делятся на внутренние, полностью 50 лежащие внутри многоугольника, и пересеченные одним или несколькими ре - брами. По трем координатам (фиг. 3) 1 Х 1, Хили У 1 У р У определя ется позиционный код внутренних и суммы пересеченных и внутренних клеток с помощью блока б памяти позиционных кодов. Деление клеток на внутренние и пересеченные позволяет фор 40мировать маски клеток на каждом уров - не обработки, а не только за счет накопления с нижних уровней. Эта ускоряет процесс маскирования и сакра" щает время для ксррекции масок с нижнего уровня на верхний . Из блока 6 на селекторы пересеченных клеток 8, внутренних клеток 9 и суммы (пересеченных и внутренних 7 клеток 11 поступают сформированные позиционные коды с выходов 7 и 1 О. На выходе селектора 8 образуется позиционный код пересеченных клеток для каждого ребра путем логического вычитания позиционного кода внутренних клеток, кода суммы внутренних и пересеченных клеток и позиционного кода масок из блока 13 памяти масок на блоке 31 и записи результата в регистр 32. В селекторах 11 и 9 па мере поступления ребер, относящихся к обрабатываемому многоугольнику, происходит накопление соответствующих позиционных кодов, а в узлах 17 - координат трех пересечений ребер до тех пор, пака не поступит признак последнего ребра, При поступлении признака последнего ребра.на ключи 35 и 38 происходит маскирование многоугольника позиционным кодом, хранящимся в блоке 13 памяти масок, для обрабатываемых на текущем уровне клеток, который образовался от обработки в данных клетках предыдущих многоугольников. Коды незамасированных клеток записываются по входу разрядов данных в узел 17. На фиг. 7 приведен пример четырехугольника, пересекающего клетку,в таблице показана формирование позиционного кода пересеченных каждым ребром этого четырехугольника клеток, а также получение окончательного позиционного кода внутренних клеток и суммы внутренних и пересеченных клеток.Блок 13 памяти масок (фиг. 8) включает собственно узел 43 оперативной памяти (масок текущего уровня ), а также узел 39 памяти типа "первым вошел, первым вышел, который служит для приема заполненной маски с последующего уровня. Адрес в память масок поступает как с текущего уровня обработки клетки (на фиг. 1 не показаны), так и со следующего уровня. Запись в узел 39 происходит при наличии сигнала переполнения памяти масок с узла 24, Чтение узла 39 разрешено, если он непуст или в данный момент не выполняется цикл чтение - модификация - запись узла 43 со стороны клеточного процессора 2 текущего уровня. При5 чтении узла 39 младшие биты адреса поступают на дешифратор 40, формирующий четырехразрядный позиционный код маски текущего уровня с единственным установленным битом, соответствующим полностью заполненной маске последующего уровня. Этот код и оставшиеся разряды адреса маски записываются в регистр 41. Если узел 39 пуст, то ни одного бита маски старшего уровня сформировано не будет. Условием записи информации в регистр 41 служит окончание цикла чтение - модификация - запись узла 43, Выход регистра 41 подключен к нулевому вхо ду мультиплексора 42, на другой вход которого поступает адрес клетки текущего уровня. Этот мультиплексорподключает входы адреса узла 43 и входы узла 44 управления записью либо к 25 выходу регистра 41, либо к адресу, поступающему из клеточного процессора 2 текущего уровня. Выход узла 43 подключен к управляемому инвертору 45, наличие которого позволяет не проиэводить очистку узла 43 в начале очеред. ного кадра. Управление инвертором 45 осуществляется с узла 44 управления записью. Выход управляемого инвертора 45 подключен к входу регистра 46,35который предназначен для хране-ния считанного из узла 43 че-тырехразрядного кода маски текущего уровня и выдачи ег о кле точному процессору 2. Емкость четырех- ,разрядного узла 43 увеличивается от уровня к уровню в четыре раза.Для повышения производительности процессоров предусмотрена параллельная запись в узлы 17 информации для четырех клеток, а также чтение только тех ребер, которые пересекают рассматриваемую (одну из четырех )клетку в случае, если нет на нее маски и если эта клетка не лежит вне многоугольни 5 О ка, Эту Функцию выполняет узел 16 приоритета, который ведет эффективный поиск нужных ребер в узлах 17, Позиционный код пересеченных ребром кле - ток поступает на последовательные вхо 55 ды данных групп регистров 47 и 48, каждая из которых разделена на четыре группы, соответствующие каждой из четырех образованных клеток - О, 1, 2,3. Параллельные выходы регистров 47 и 48 групп соединены с входом схемы 49 приоритета и подключаются к ней в зависимости от обрабатываемой в данный момент клетки. В то время, как часть регистров группы 47 используется для записи позиционных кодов ребер, другая часть регистров группы 48 используется для чтения из узлов 17, С каждым новым ребром записывается позиционный код пересечения в эти ре-. гистры. На выходе каждого из регистров, соответствующего одной из четырех выбранных клеток, образуется позиционный код всех ребер, пересекших эту клетку. Те ребра, которые пересекали данную выбранную клетку, отметятся нулями, а которые не пересекали - единицами, Этот коц поступает на вход схемы 49, на выходе 18 которой формируется адрес первого ребра, пересекающего выбранную клетку, и поступает на узел 17, Если нет больше ребер, которые пересекали эту клетку, выбирается следующая, пока не выберутся все клетки и ребра, пересекающие их . Выбор незамаскированных клеток, обрабатываемых на данном уровне, осуществляется приоритетной схемой (не показана), аналогичной схеме 49, а также рядом схем не показаны), осуществляющих управление работой клеточного процессора 2.После выборки последнего ребра в последней клетке данного уровня чтение данного узла 17 переключаемой памяти прекращается, и он переключается на запись нового многоугольника или нового фрагмента многоугольника, а другой узел 17 переключается на чтение того, что было записано ранее.Информация с узла 17 поступает на вход следующего клеточного процессора 2 и обрабатывается аналогичньм образом на следующем уровне, Маски, сформированные на жених уровнях, передаются на верхние вместе с их адресами через узел 24.Последний клеточный процессор 2 в конвейерном вычислителе Формирует описание ЭИ, которое поступает на фильтр 25. Координаты пересечения ребра с клеткой на выходе этого клеточного процессора 2 уже не используются, а выходной инйормацией является ЭИ высокого разрешения с селектора. 9 внутренних клеток. Количество элементов разложения, на которое подделяется ЭИ, зависит от требуемого качества9 15222изображения. В случае использованияподделения 2 х 2 последний клеточныйпроцессор 2 может быть реализован точно так же, как остальные процессоры,5Возможно использование более точногоподцеления каждого ЭИ, например, 4 х 4и точнее, что требует увеличения объема блока 6 памяти позиционных кодови установления перед последним клеточОным процессором 2 перекодировщика длясогласования входного формата.В фильтре 25 происходит вычислениеплощади, занимаемой многоугольникамив каждом ЭИ. Вычисленная площадь пода 15ется на смеситель 26, туда же поступает цвет данного пиксела, который вычисляется в вычислителе 27 цвета покоэффициентам уравнений для цветаданного многоугольника и координатам щЭИ, поступающих из конвейерного вычислителя, Вычислитель 27 цвета позволяет осуществить линейную интерполяциюцвета для создания округлых объектов,а также вычислить туман в каждой точке изображения. В смесителе 26 происходит окончательное вычисление цветаЭИ для трех компонентов цвета с учетом занимаемой многоугольником площади в данном ЭИ. 30Окончательный цвет ЭИ записываетсяв блок 23, представляющий память длятрех компонент цвета всех ЭИ кадра ссумматором на входе, Если ЭИ заняттекущим многоугольником не полностью,то значение цвета суммируется с цветом других многоугольников, лежащихв этом же ЭИ, Одна часть блока 28 используется клеточными процессорами 2для формирования изображения, а дру Огая в это время считывается синхроннос телевизионной разверткой и черезцифроаналоговые преобразователи 29три компоненты цвета в аналоговом виде подаются на отображающее устройство 30,В генераторе возможно дальнейшееповышение числа отображаемых в кадремногоугольников, если на последнемуровне конвейерного вычислителя под Оключить параллельно несколько узлов,каждый из которых будет содержатьклеточный процессор, фильтр, вычисли-.тель цвета, смеситель и видеобуфер.Объединение этих узлов осуществляется через селектор перед цифроаналоговыми преобразователями. Таким образомосуществляется параллельная обработканескольких ЭИ. В зависимости от числа 40 ообрабатываемых параллельно ЭИ изменяется и число клеточных процессоров,К генератору псд;лючается ЭВМ универсального типа, осушествляющая управление работой всех узлов и используемая для подкачки баз данных и тестового контроля.Формула изобретенияГенератор изображений, содержащиигеометрический процессор и процессорформирования элементов изображения,выход геометрического процессора соединен с входом пропессора формирования элементов изображения, выход которого является выходом генератора, причем процессор формирования элементов изображения содержит блок буферной памяти элементов изображения, Выход которого является выходом процессора формирования элементов изображения, смеситель, выход которого соединен с информационным входом блока буферной памяти элементов изображения, фильтр и вычислитель цвета, выходы которых соединены с первым и вторым входами смесителя соответственно, входы задания коэффициентов вычислителя цвета соединены с соответствующими разрядами выхода геометрического процессора, о т л и ч а ю щ и й с я тем, что, с целью повышения информативности формируемого кадра изображения, в гроцессор формирования элементов изображения введен конвейерный вычислитель, разряды входа которого соединены с входами соответствующих разрядов процессора формирования элементов изображения, а первый и второй выходы - с входом фильтра и с входом координат элементов изображения вычислителя цвета соответственно, причем конвейерный вычислитель содержит М клеточных процессоров и Мблоков буферной памяти, информационный вход первого клеточного процессора является входом конвейерного вычислителя, выход а-го клеточного процессора (а - 1,М) соединен через а-й блок буферной памяти с информационным входом (а+) -го клеточного процессора, первый и второй выходы конвейерного вычислителя соединены с соответствующими выходами М- о клеточного процессора, выходы адреса клетки и признака готовности маски Ъ - го клеточного процессора (Ъ = 2,М) подключены к одНомер ребра Позиционныйкод внутренних клеток свыхода 7 Позиционныйкод внутренних клетокна выходе 14 Позиционный код суммы внутренних и пересеченных клеток с выхода 10 Позиционныйкод суммыклеток навыходе 21 Позиционный код пересеченных кле -ток на выходе 151 1110 1111 ОООО 0001 1110 2 1101 1111 ОООО 1101 3 0111 ОООО 1011 0111 0111 1111 0000 1011 0111 11 152224 ноименным входам (Ъ) -го клеточного процессора, причем каждый из М клеточных процессоров содержит входной регистр, сумматор, делитель на. два, блок памяти позиционных кодов, селек 5 торы пересеченных и внутренних клетоки суммы клеток, узел приоритета и блок памяти масок, причем в каждом клеточном процессоре информационный вход входного регистра является инфор мационным входом клеточного процессора, разряды первой и второй групп выхода входного регистра соединены с ,соответствующими разрядами адресного входа блока памяти позиционных кодов, выхода клеточного процессора и соответственно с разрядами входов первого и второго слагаемых сумматора, разряды выхода которого соединены через 20 делитель на два с соответствующими разрядами выхода клеточного процессора и адресного входа блока памяти позиционных кодов, выход кода внутренних клеток которого соединены с пер выми входами селекторов пересеченных и внутренних клеток, а выход коца суммы внутренних и пересеченных клеток - с первым входом селектора суммы клеток и с вторым входом селектора 012пересеченных клеток, третий вход которого и вторые входы селекторов внутренних и суммы клеток соединены с выходом кода маски блока памяти масок, вход кода внутренних клеток которого соединен с выходом селектора внутренних клеток, выходы селекторов внутренних и суммы клеток соединены с соответствующими разрядами выхода клеточного процессора, выходы селектора пересеченных клеток соединены через узел приоритета с адресными разрядами выхода клеточного процессора, входы признака готовности маски и адреса клетки а-го клеточного процессора соединены с одноименными выходами (а+1)- го клеточного прсцессора, вход адреса клетки текущего уровня блока па.мяти масок каждого клеточного процессора соединен с разрядами адреса его информационного входа, а каждый Ь-й клеточный процессор содержит узел формирования признака готовности маски, выход признака готовности маски которого является одноименным,выходом Ь"го клеточного процессора, а входы соединены с выходами блока памяти ма,сок и селектора внутренних клеток.522240юнак юесдеМи рюК цуиад ясенем р/48 Тираж 668ударственного комитета по и113035, Москва, ЖПодписноезобретениям и открытиям при ГКНТ ССС Раушская наб., д. 4/5 35,нно-издательский комбинат "Пате 11 роизводс г.1 аказВНИИПИ Сост Техр тель А. УшаковЛ,Сердюкова Корректор од, ул. Гагарина, 101