Устройство для формирования графической информации

(19 09 и 1/1 Е ИЭОБРЕТЕНИ ОПИС ЛЬСТ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ АВТОРСКОМУ СВИ(56) 1. Друзин Я.В. и Коганер С.Э. Телевизионные системы отображения инФормации. Л., "Энергия", 1975, с.78.2. Авторское свидетельство СССР Р 732941, кл.0 09 0 1/16, 1980 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ, содержащее первый регистр, один из входов которого соединен с. выходом первого блока памяти, вход которого соединен с . выходом первого элемента И, один из входов которого соединен с выходом второго регистра, один из входов которого соединен с выходом второго блока памяти, вход которого соединен с выходом второго элемента И, один из входов которого соединен с выходом третьего регистра, один из входов которого соединен с выходом третьего блока памяти, вход которого соединен с выходом третьего элемента И, одинйэ входов которого соединен с выхо дом четвертого регистра, вход которого соединен с другим входом третьего элемента И и выходом первого счетчика, вход которого соединен с другим входом третьего регистра, другим входом второго элемента И и выходом второго счетчика, вход которого соединен с другим. входом втсрого регистра,другим входом первого элемента И ивыходом первого счетчика, вход которого соединен с другим входом первого регистра и выходом генератораимпульсов, о т л и ч а ю щ е е с ятем, что, с целью упрощения устройства, оно содержит сумматор, пятый,шестой, седьмой и восьмой регистры,элемент НЕ, первый и второй элементы ИЛИ, четвертый и пятый элементыИ, выход первого регистра соединенс одним из входов сумматора, выходкоторого соединен с одним из входовпятого регистра и одним из входовшестого регистра, выход которогосоединен с первым входом первогоэлемента ИЛИ, первым входом пятогоэлемента И и одним из входов седьмого регистра, выход которого соединен с вторым входом первого элементаИЛИ, вторым входом пятого элементаИ и с одним из входов восьмого регистра, выход которого соединен свходом элемента НЕ, выход которогосоединен с третьим входом пятогоэлемента И и третьим входом первогоэлемента ИЛИ, выход которого соединен с одним из входов четвертогоэлемента И, другой вход которого соединен с выходом пятого регистра,выходы четвертого и пятого элементов И соединены соответственно спервым и вторым входами второго элемента ИЛИ, выход которого соединен "с другим входом сумматора, выход ко,торого является выходом устройства,другой вход пятого, шестого, седьмого и восьмого регистров соединен свыходом генератора импульсов.1068982 ношения объема "сжатой" графическойинформации к объему информационногорельефа экрана ЭЛТ, в среднем равен шести. Следовательно, по срав. нению с полнографическим дисплеем 5 выигрыш в объеме внешне памяти дляхранения "сжатой" графической информации и времени загрузки информационных магистралей равен также ввреднем шести Г 2,Недостатком известного устройстваявляется то, что достаточно высокийкоэффициент сжатия получается дляграфических изображений, в которыхфон занимает не менее 90 всей площади изображения и наиболее вероятную конфигурацию имеют блоки графической информации, состоящие из.одних нулей, т.е. в которых отсутствует информация. Для изображений, вкоторых фон занимает порядка 50 именее всей площади коэффициент сжа,- тия, получаемый в известном устройстве,. равен примерно единице и менее. Следовательно, по сравнению сполнографическим дисплеем выигрышаво времени загрузки информационныхмагистралей и объемов внешней памяти не получается. Поэтому применениеданного устройства целесообразнодля ограниченного класса графических изображений.Целью изобретения является упрощение устройства. 10 20 гистра, три блока памяти, три элемента И, три счетчика и генератор 35 импульсов. Данное устройство позволясамоадаптирующегося блочного кодиро- А 0 50 65 Изобретение относится к автоматике и вычислительной технике и может быть использовано в системахотображения информации на телевизионных индикаторах,Известно устройство для формирования графической информации на телевизионном индикаторе, содержащеепоследовательно соединенные счетчикадреса, ОЗУ, регистр и формирова"тель 1 ,Недостатками этого устройстваявляются его сложность, обусловленная необходимостью использования ЗУбольшой емкости для запоминаниявсех точек растра независимо от количества точек графика, а следовательно и то, что не зависимо от вида изображения, даже если надо отобразить на экране ЭЛТ одну точку,объем передаваЕмой об изображенииинформации всегда равен объему ЗУ,объем кОторого в свою очерЕдь равен объему информационного рельефа экрана ЭЛТ. Это приводит к нерациональной длительной загрузке информационных магистралей под пересылку графической информации и нерациональному задействованию значительных объемов внешней памяти для хранения графической информации.Наиболее близким по технической сущности к изобретению является устройство для формирования графической информации, содержащее четыре реет отображать графическую информацию, предварительно "сжатую" с помощью четырехкаскадного одномерного.вания.Сущность самоадаПтирующегося блочного кодирования состоит в том, что любое изображение заранее разбивается на несколько блоков, каждый из которых разбивается в свою очередь также на несколько блоков и т.д. Вначале изображение заполняется максимальным количеством болЬ- ших белых блоков, в которых отсутствует информация. Эти блоки кодируются префиксом "О" и из рассмотрения в дальнейшем отбрасываются. А.блоки, включающие в себя информацию, кодируются префиксом "1". Затем в этих блоках с префиксом "1" выделяются белые нулевые блоки меньшего размера, которые аналогично кодируются префиксом "О" и из рассмотрения отбрасываются. Оставшиесяблоки кодируются префиксом ф 1" иподвергаются аналогичной обработке,и наконец, самые маленькие ненулевые блоки передаются неэакодированными с единичными префиксами. Приэтом коэффициент сжатия, т.е. отПоставленная цель достигается тем, что устройство для формирования графической информации, содержащее первый регистр, один из входов которого соединен с выходом первого блока памяти, вход которого соединен с выходом первого элемента И, один из входов которого соединен с выходом второго регистра один из входов которого соединен с выходом второго блока памяти, вход которого соединен с выходом второго элемента И, один из входов которого соединен с выходом третьего регистра, один из входов которого соединен с выходом третьего блока памяти, вход которого соединен с выходом третьего элемента И, один из.входов которого соединен с выходом четвертого регистра, вход которого соединен с другим входом третьего элемента И и выходОм первого счетчика, вход которого соединен с другим входом третьего регистра, другим входом второго элемента И и выходом второго счетчика, вход которого соединен с другим входом второго регистра, другим входом первого элемента И и выходом первого счетчика, вход которого соединен с другим входом первого регистра и выходом генератора импульсов; включает сумматор, пятый, шестой, седьмой и восьмой регистры, элемент НЕ, первый и второй элементы ИЛИ, четвертйй ипятый элементы И, выход первого регистра соединен с одним из входов сумматора, выход которого соединен с одним из входов пятого регистра и одним из входов шестого регистра, выход которого соединен спервым вхо дом первого элемента ИЛИ, первым входом пятого элемента И и одним из 1-входов седьмого регитра, выход которого соединен со вторым входом первого элемента ИЛИ, вторым входом 10 пятого элемента И и с одним из входов восьмого регистра, выход которого соединен с входом элемента НЕ, выход которого соединен с третьим входом пятого элемента И и третьим входом первого элемента ИЛИ, выход которого соединен с одним из входов четвертого элемента И, другой вход которого соединен с выходом пятого регистра, выходы четвертого и пятого элементов И соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход которого соединен с другим входом сумматора, выход которого является выходом устройства, другой вход пятого, шестого, седьмого и восьмого регистров соединен с выходом генератора импульсов.На Фиг,1 представлена функциональная схема устройства для Формирования графической информации; на 30 Фиг,2 - примеры, поясняющие работу устройства.Устройство для формирования графической информации содержит регистры 1-8, элементы И 9-13, элементы 35 ИЛИ 14 и 15, элемент НЕ 16, блоки 17-19 памяти, счетчики 20-22, .генератор 23 и сумматор 24, выход 25 устройства.Устройство работает следующим об разом.С помощью алгоритма двумерного предсказания в изображении уменьшается количество черных элементов, после чего изображение кодируется 45 с помощью четырехкаскадного само- адаптирующегося блочного одномерного кода, Вследствие того, что количество нулевых белых блоков, кодируемых одним префиксом "0", возрастает, то и результирующий коэффициент сжатия возрастает. Следовательно, время загрузки информационных магистралей под пересылку закодированной графической информации уменьшается, кроме того, уменьшаются и требуемые объемы внешней памяти для хранения закодированной графической информации. Суть алгоритма двумерного предсказания заключается в том, что на основании статистических данных 60 вследствие присущей любому иэображению корреляции элементов изображения можно значение текущего считываемого элемента изображения предсказать на основании значений соседних А 5ранее переданных элементов с вероятностью0,5. Обозначим текущий элемент через х, а соседние ранее переданные элементы через х, х, х, х. Расположение элементов такое х х хПредыдущая строка ху Текущая строка На основании статистических измерений ряда типичных графических изображений получают следующую формулу предсказания с вероятностью0,5 значения текущего элемента хб на.основании значений ранее переданных четырех элементов:х = х(х Чх Чх )Чх х,х (1) где операция умножения означает операцию логического умножения - коньюнкции, знак Ч - операцию логического сложения - дизъюнкию, черточка; над х означает, что берется величина, обратная х, т.е. отрицание Х,. В результате теперь исходную рецепторную матрицу можно перекодировать следующим образом. Если предсказываемое значение текущего элемента изо- бражения совпадает с его реальным значением, то в новой рецепторной матрице пишется "0", а если предска- зываемое значение не совпадает с реальным значением текущего элемента, то в новой рецепторной матрице пишется ."1". Операпия сравнения и выдачи сигнала ошибки может быть реализована с помощью суммирования по модулю два . у о + б у (2) сигнал ошибки;предсказываемое по формуле (1) значение текущего элемента иэображения 1 реальное значение текущего элемента и эобра;е ниялогическая операция суммирования по модулю два. где у ХП оВ новой матрице количество единиц уменьшается, а количество белых нулевых блоков возрастает. Результирующий коэффициент сжатия, измеренный для ряда типичных изображений, равен в среднем десяти, в то время как в известном устройстве он равен шести, Если в изображении встречаются отдельные черные элементы в окружении белых и отдельные белые элементы в окружении черных, то их значения по формуле (1) не предсказываются. В результате в новой рецепторной матрице на месте каждого одиночного элемента получают две ошибки предсказания, однако по сравнению с общим выигрышем проигрыш в кодировании таких одиночных элементв незначителенКроме того, поскольку такие одиночные элементы обычно не несут существенной информации, можно с помощьюспециальных несложных схем инвертировать такие одиночные элементы сцелью их устранения и повышения, таким образом, общего коэффициента сжа-тия графического изображения. Нафиг.2 ц, представлена для примера фигура квадрата, подвергнутая перекодированию с помощью алгоритма двумерного предсказания по формулам (1)и (2) . В результате в новой рецеп-,торной матрице (фиг.2 У) остаетсявсего три черных элемента, кодируемых единицами, т.е. всего три разапредсказанное значение хр не совпадает с реальным значением хр . Несомненно коэффициент сжатия графического изображения,.изображенногона фиг,21, больше, чем графическогоиэображения на Фиг.2 а.Регистр 1 предназначен для приема в параллельном виде из блока 17памяти кода засветки ненулевых блоков информации наименьших размеров(слов) и выдачи затем этого кода впоследовательном виде под действиемтактовых импульсов с выхода генератора 23 импульсов.Регистр 2 предназначен для приемаз параллельном виде из блока 18 памяти кодов управления словами встроках и выдачи затем этих кодов впоследовательном виде под действиемимпульсов с выхода счетчика 20.Если очередной выдаваемый регистром 352 разряд равен единице, то это означает, что в очередном наименьшемблоке графической информации (слове)есть информация. В этом случае этотединичный импульс, складываясь с импульсом переноса, с выхода счетчика20 проходит через первый элементИ 11 на управляющий вход блока 17 памяти и инициирует считывание этогоненулевого блока наименьших размеров (слова) в параллельном виде впервый регистр 1. Если же очереднойразряд на выходе регистра 2 равеннулю, это означает, что очереднойнаименьший блок графической информации (слова) равен нулю. В этом случае считывания кода засвета из блока 17 памяти не происходит, и поддействием импульсов с выхода генератора 23 импульсов, с выхода регистра 1 считываются одни нули, что н 55необходимо выдавать,Регистр 3 предназначен для приемав параллельном виде иэ блока 19 па"мяти кодов управления строками вгруппах строк и выдачи затем этих 6 Окодов и последовательном виде. Еслиочередной, выдаваемый регистром 3,разряд равен единице, это означает,что в очередной строке графическойинформации есть информация. В этом 65 случае этот единичный сигнал, складываясь на элементе И 12 с импульсом переноса, со счетчика 21 проходит через элемент И 12 на управляющий вход блока 18 памяти и иницииру"ет с него считывание очередногокода управления словами в этой очередной строке. Если же очередной выдаваемый регистром 3 разряд равеннулю, это означает, что очереднаястрока графической информации является нулевой,.т.е. в ней отсутствует информация. В этом случае считывания из блоков 17 и 18 памяти непроисходят, и с выхода регистров 1и 2 считываются одни нули,Регистр 4 предназначен для хранения и выдачи в последовательном видекода управления группами строк. Еслиочередной выдаваеМый им разряд равенединице, это означает, что в очередной группе строк есть информация. Вэтом случае этот сигнал, складываясьча элементе И 13 с импульсом переноса, с выхода счетчика 22 проходитчерез элемент И 13 на управляющийвход блока 19 памяти иинициируетсчитывание из него в регистр 3 кодауправления строками в очередной группе строк. Если же очередной выдаваемый регистром 4 разряд равен нулю,это означает, что в очередной группестрок графической информации отсутствует информация. В этом случае считывание кода управления строками в очередной группе строк из блока 19 памяти не происходит. В результате свыходов регистров 1-3 считываютсяодни нули.Блок 17 памяти предназначен дляхранения ненулевых кодов засветаблоков графической информации наименьших. размеров (слов), блок 18 памяти - для хранейия кодов управления словами в строках, причт хранятся в нем коды управления словамитолько для тех строк, в которых естьинформация. Блок 19 памяти предназначен для хранения кодов управлениястроками в группах строк, причем внем хранятся только коды управлениястроками ненулевых групп строк,Генератор 23 импульсов предйазначен для выдачи последовательноститактовых импульсов с частотой следования, равной частоте следования элементов разложения в строке. Во времяобратного хода луча ЭЛТ по кадру истроке выдача тактовых импульсоввременно прекращается.Счетчик 20 считает с периодом,равным числу элементов разложения вблоке графической информации наимень.ших размеров - слове. По окончанииочередного цикла счета он .выдает насвоем выходе импульс переноса, который поступает на счетный .ход счетчика 21, соответствующие входю эле1068982 гиндикатора мента И 11, регистра 2. Под действй ем этого импульса содержимое регис) тра 2 сдвигается вправо на один разряд, а записанный в крайней правой его ячейке разряд подается при этом на вход элемента И 11. 5Счетчик 21 считает с периодом, равным числу слов в строке. По окончании каждой строки, таким образом, он вь 1 дает на своем выходе импульс переноса, поступающий на счетный вход 10 счетчика 22, вход элемента И 12 и вход регистра 3. Под действием этого импульса содержимое регистра 3 сдвигается вправо на один разряд, а разряд, записанный до сдвига в крайней правой ячейке, подается при этом на вход элемента И 12.Счетчик 22 считает и выдает на своем выходе импульс переноса с периодичностью, равной частоте следования групп строк. Таким образом, по окончании развертки очередной группы строк на выходе счетчика 22 появляется импульс, который поступает на вход элемента И 13 и вход регистра 4. Под действием этого импульса содержимое регистра 4 сдвигается вправо на один разряд, а разряд, находившийся до сдвига в правой крайней ячейке, подается на вход элемента И 13. 30. Элементы 1-4, 11-13, 17-19 и 20- 24 предназначены для декодирования графической информации, закодированной с помощью четырехкаскадного одномерного самоадаптирующегося блочного кода.Элементы 5-10 и 14-16 предназна/ чены для получения исходного граФического изображения. На один из вхо дов сумматора 24 по модулю два пода-, ется рецепторная матрица, перекодированная с помощью алгоритма двумерного предсказания, т.е. подаются ошибки в предсказании у. Если отображается, например, Фигура квадрата (фиг.20,), то на один из входов сумматора 24 подается репепторная матрица (Фиг.2 о"). Значение сигнала ошибки в предсказании сравнивается с подсказанным по Формуле (1) значением текущего элемента хо подаваемым на другой вход сумматора 24. Если сигнал ошибки равен нулю, это означает, что предсказанное значение х" совпадает с реальным энаьчением х , и сигнал х. проходит на выход сумматора 24Если же сигнал равен единице, это означает, что значение хЪ должно быть инвертировано, что и происходит на сумма торе 24. Формула его работыЧХ" = Хо (3) где у - подаваемый на первый входсумматора 24 сигнал ошибки предсказания текущего элемента;х", - предсказанное значение текущего элемента, подаваемоена второй вход сумматора 24х" - истинное значение текущегоэлемента изображения, получаемое на выходе сумматора 24 на основе предсказанного значения х" и ошибкипредсказания текущего элемента у,О+ - логическая операция суммирования по модулю два.Элементы 5-10, 14-16 предназначены для получения значения х"поформуле (1).Регистр 5 предназначен для задержки значения сигнала х" на один такти получения таким образом на его выходе значения соседнего сигнала х у.Регистр б предназначен для задержкизначения сигнала х на количествотактов, равное числу элементов разложения изображения в строке минус единица. На выходе регистра б таким образом имеем сигнал х. Регистр 7предназначен для задержки на одинтакт сигнала хЗ, на его выходе получают сигнал х . Регистр 8 предна-значен для задержкина один тактсигнала х и получения на выходе регистра таким образом сигнала х. Элемент НЕ 16 предназначен для получения.отрицания сигнала х, необходимогодля вычисления х" по формуле (1).Элемент ИЛИ 14 предназначен для получения сомножителя хзчх ч х , входящего в формулу (1), элемент И 9дгя получения первого слагаемогох (хэви хч х ), входящего в формулу(.1), элемейт И 10 - для голучениявторого слагаемого ххх, входящегов формулу (1).На выходе элемента ИЛИ 15 получается искомое предсказываемое значение текущего элемента изображения х.",получаемое по формуле (1).Выход 25 устройства предназначендля подачи декодированного сигналарецепторной матрицы графического изображения на модулятор телевизионнРГО Блок перекодирования графического изображения, работающий по алгоритму двумерного предсказания (по формуле 1), с целью уменьшения количества черных элементов в изображении реализуется на элементах 5-10, 14-16 и 24. Если необходимо, например, перекодировать рецепторную матрицу графического изображения квадрата, изображенную на фиг.2 а, то на один из входов сумматора 24, выход которого отсоединяется от выхода 25 устройства, и выход 25 подают лоэлементно и построчно рецепторную матрицу графического иэображения на фиг.2 а, 1068982 10другой вход сумматора 24 соединен свыходом элемента ИЛИ 15, а с выходасумматора 24 последовательно снимается перекодированная рецепторнаяматрица ошибок в предсказании,изображенная на Фиг.2 Я, После блочного кодирования коэфФициент сжатия графического иэображения на фиг.26 больше, чем графического изображения нафиг.26, поскольку нулевых блоков,кодируемых одним префиксом "0", нафиг.2 о больше, чем на Фиг 2 а,При наличии единицы на выходе регистра 4 управления группами строк исигнала на выходе счетчика 22 происходит выборка управляющей информациизасветки очередной группы строкиз блока 19 памяти в регистр 3 управления строками в группах. Соответственно единица на выходе регистра 3управляет выборкой из блока 18 памяти кодов управления словами в строках. Эта информация переписываетсяв регистр 2 из блока 18 памяти. Единица на выходе второго регистра 2управляет выборкой очередного кодаслова (блока наименьших размеров)иэ блока 17 памяти в регистр 1, иэкоторого с помощью тактовых импульсов с генератора 23 импульсов кодсдвигается на вход сумматора 24. Поокончании сдвига кода слова на вы-ходе счетчика 20 вырабатывается сигнал сдвига содержимого регистра 2управления словами в строках. Приналичии единицы на выходе этого регистра производится очередная выборка кода слова из блока 17 памяти,а при наличии нуля выборка запрещена, и генератор 23 импульсов сдвигает в регистре 1 нули на вход сумматора 24, При появлении импульса свыхода счетчика 21 слов в строкахпроисходит сдвиг содержимого регистра 3 управления строками в группах,на выходе которого образуется информация управления для выборки очередной управляющей информации строки.При нуле на выходе регистра 3 выборка управляющей информации очереднойстроки запрещена, и в регистре 2управления словами в строках происходит сдвиг нулей, управляемый счетчиком 20. Таким образом, по всей выбранной строке сдвигаются нули, выборка кодов слов из блока 17 памятине производится, При наличии сигнала со счетчика 22 производится сдвигсодержимого регистра 4, которыйуправляет выборкой упрг.вляющей информации очередной группы строк изблока 19 памяти. Нуль на выходеэтого регистра показывает отсутствие информации на всем участке очередной группы строк, что приводит, ксдвигу во всех остальных регистрах,а выборка иэ блоков памяти не производятся. Счетчики 20-22 синхронизи роМаны с разверткой луча. Графическое изображение на выходе первого регистра 1 является перокодированным по алгоритму двумерного предсказания.Поэтому прежде, чем его подать на модулятор телевизионного индикатора, надо его декодировать, что и происходит на сумматоре 24 по модулю два, который осуществляет декодирование по формуле (3).10 Таким образом, предлагаемое устройство позволяет по сравнению с известным уменьшить объем памяти блоков памяти, так как сжатие графической информации в предлагаемом 15 устройстве по сравнению с известнымувеличивается примерно на 40-60 для ряда самых разнообразных графических изображений. Если коэффициент сжатия, полученный для известного устройства на ряде типичных графических изображений равен шести, то для предлагаемого устройства коэффициент сжатия в среднем равен десяти для тех же графических изображений. Предлагаемое устройство позволяет по сравнению с известным отображать более разнообразные графические изображения с коэффициентомсжатия1. Вследствие этого предлагаемое устройство позволяет по сравнению с извесчлым получить в среднем больший примерно на 40-60 выигрыш во времени загрузки информационных магистралей под пересылку адресованной графической информации, атакже в объеме внешней памяти дляхранения этой закодированной графи 25 ЗО 35 ческой информации. даже меньше, чем в дисплейном комплексе АГАТМ. В дисплейном комплексе АГАТМ объем закодированной графической информации равен По сравнению с базовым объектом дисплейным комплексом АГАТМ,в котором для отображения графической информации используется структурно-символический метод (полеэкрана разбито на 32164 знакоместа,каждое знакоместо описывается матрицей 7 Х 18 точек, в каждом знакоместе может отображаться один из 73заранее выбранных графических элементов, в то время как число различных конфигураций графоэлементов в 50 знакоместе с учетом того, что во избежание черезстрочных мельканий инФормация в четном и нечетном полукадрах одинакова, равно бзпредлагаемое устройство позволяет автоматически воспроизводить любое графическое изображение с исходной точностью, т.е. на участке 718 мокнутбыть отображены все возможные 2.ъконфигурации. При этом объем закоди рованной графической инФормации дляпредлагаемого усгройства в среднемФиг Составитель М.НемировскийА.Шишкина Техред М.Тепер Корректор й.Тяско Редакт 451 Подписноеного комитета СССРений и открытийРаушская наб., д.4/5 478/47 Тираж ВНИИПИ Государствепо делам изобре 3036, Москва, Жказ Филиал ППП "Патент", г.ужгород, ул.Проектная,4 произведению количества знакоместМа количество двоичных разрядов,необходимых для кодирования одногоиз 73 графоэлементов (3264 3. Коэффициент сжатия в базовом объектев предположении, что информация вчетном и нечетном полукадрах одинакова, равен отношению объема рецеп.торной матрицы изображения к объемуграфической информации, закодирован.ной структурно-символическим методом Таким образом, по сравнению сбазовым объектом в предлагаемом устройстве коэффициент сжатия больше, а точность воспроизведения равна точности исходного изображения, т.е.намного выше, чем в базовом 1 О объекте.