Устройство для формирования графической информации Советский патент 1984 года по МПК G09G1/16 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах отображения информации на телевизионных индикаторах. Известно устройство для формирования графической информации на телевизионном индикаторе, содержащее последовательно соединенные счетчик адреса, ОЗУ, регистр и Формирователь tl л. . Недостатками этого устройства являются его сложность, обусловленная необходимостью использования ЗУ большой емкости для запоминания всех точек растра независимо от количества точек графика, а следовательно и то, что не зависимо от вида изображения, даже если надо отсгбразить на экране ЭЛТ одну точку, объем передаваемой об изображении информации всегда равен объему ЗУ, объем которого в свою очередь равен объему информационного рельефа экрана ЭЛТ. Это приводит к нерациональной длительной загрузке информа ционных магистралей под пересылку графической информации и нерациональному задействованию значительных объемов внешней памяти, для хранения графической информации. Наиболее близким по технической сущности к изобретению является уст ройство для формирования графической информации; содержащее четыре р гистра, три блока памяти, три элемента И, три счетчика и генератор импульсов.Данное устройство позволя ет отображать графическую информацию, предварительно сжатую с помощью четырехкаскадного одномерного самоадаптирующегося блочного кодиро вания. Сущность самоадаптирующегося блочного кодирования состоит в том, что любое изображение заранее разбивается на несколько блоков, каждый из которых разбивается в свою очередь также на несколько блоков и т.д. Вначале изображение заполняется максимальным колшчеством больших белых блоков, в которых отсутствует информация. Эти блоки кодируются префиксом О и из рассмотре ния в дальнейшем отбрасываются. А блоки, включающие в себя информа- цию, кодируются префиксом 1. Затем в этих блоках с префиксом 1 выделяются белые нулевые блоки мень шего размера, которые аналогично ко дируются префиксом О и из рассмот рения отбрасываются. Оставшиеся блоки кодируются префиксом 1 и подвергаются аналогичной обработке, и наконец, самые маленькие ненулевые блоки передаются неэакодированньвли с единичными префиксами. При этом коэффициент сжатия, т.е. отношения объема сжатой графической информации к объему информационного рельефа экрана ЭЛТ, в среднем равен шести. Следовательно, по сравнению с полнографическим дисплеем выигрыш в объеме внешней, памяти для хранения сжатой графической информации и времени загрузки информационных магистралей равен также в вреднем шести 2. Недостатком известного устройства является то, что достаточно высокий коэффициент сжатия получается для графических изображений, в которых фон занимает не менее 90% всей площади изображения и наиболее вероятную конфигурацию имеют блоки графической информации, состоящие из.одних нулей, т.е. в которых отсутствует информация. ДлА изображений, в которых фон занимает порядка 50% и менее всей площади коэффициент сжа.тия, получаемый в известном уст;ройстве, равен примерно единице и менее. Следовательно, по сравнению с. полнографическим дисплеем выигрыша во времени загрузки информационных магистралей и объемов внешней памяти не получается. Поэтому применение данного устройства целесообразно для ограниченного класса графических, изображений. Целью изобретения является упрощение устройства. Поставленная цель достигается тем, что устройство для формирования графической инфс мации, содержащее первый регистр, один из входов которого соединен с выходом первого блока памяти, вход которого соединен с выходом первого элемента И, один из входов-которого соединен с выходом второгорегистра д. один из входов которого соединен с выходом второго блока памяти, вход которого соединен с выходом второго элемента И, один из входов которого соединен с выходом третьего регистра, один из входов которого соединен с выходом третьего блока памяти, вход которого соединен с выходом третьего элемента И, один из. входов которого соединен с выходом четвертого регистра, вход которого соединен с другим входом третьего элемента И и выходом первого счетчика, вход которого соединен с другим входом третьего регистра, другим входом второго элемента И и выходом второго счетчика, вход которого соединен с другим входом второго регистра, другим входом первого элемента И и выходом первого счетчика, вход которого соединен с другим входом первого регистра и выходом генератора импульсов включает сумматор, пятый, шестой, седьмой и восьмой регистры, элемент НЕ, первый и второй элементы ИЖ, четвертый и пятый элементы И, выход первого регистра соединен с одним из входов сумматора, выход которого соединен с одним из входов пятого регистра и одним из входов шестого регистра, выход которого соединен с первым вхо дом первого элемента ИЛИ, первым входом пятого элемента И и одним из -входов седьмого регистра, выход которого соединен со вторым входом пе вого элемента ИЛИ, вторым входом пятого элемента И и с одним из входов восьмого регистра, выход которого соединен с входом элемента НЕ, выход которого соединен с треть входом пятого элемента И и третьим входом первого элемента ИЛИ, выход которого соединен с одним из входов четвертого элемента И, другой вход которого соединен с выходом пятого регистра, выходы четвертого и пятог элементов И соединены соответственн с первым и вторым входами второго элемента ИЛИ, выход которого соединен с другим входом сумматора, выхо которого является выходом устройства, другой вход пятого, шестого, седьмого и восьмого регистров соеди нен с выходом генератора импульсов. На фиг.1 представлена функциональная схема устройства для формирования графической информации;; на фиг.2 - примеры, поясняющие работу ус-тройства. Устройство для формирования графической информации содержит регистры 1-8, элементы И 9-13, элементы ИЛИ 14 и 15, элемент НЕ 16, блоки 17-19 памяти, счетчики 20-22, генератор 23 и сумматор 24, выход 25 устройства. Устройство работает следующим об разом. С помощью алгоритма двумерного предсказания в изображении уменьшается количество черных элементов, после чего изображение кодируется с помощью четырехкаскадного самоадаптирующегося блочного одномерного кода. Вследствие того, что количество нулевых белых блоков, кодируемых одним префиксом О, возрастает, то и результирующий коэффицие сжатия возрастает. Следовательно, время загрузки информационных магис тралей под пересылку закодированной графической информации уменьшается, кроме того, уменьшаются и требуемые объемы внешней памяти для хранения закодированной графической информации. Суть алгоритма двумерного пред сказания заключается в том, что на основании статистических данных вследствие присущей любому изображению корреляции элементов изображе ния можно значение текущего считыва емого элемента изображения предсказать на основании значений соседних ранее переданных элементов с вероятностью О, 5. Обозначим текущий элеент через X(s, а соседние ранее переданные элементы через х, х, Xj, Хц. Расположение элементов такое На основании статистических измерений ряда типичных графических изображений получают следующую формулу предсказания с вероятностью 0,5 . значения текущего элемента х на основании значений ранее переданных четырех элементов: хд х ( Wxj-x.-Xj (1) где операция умножения означает операцию логического умножения - конъюнкции, знак у - операцию логического сложения - .дизъюнкию, черточка: над Хц означает, что берется величина, обратная х,, т.е. отрицание к. В результате теперь исходную рецепторную матрицу можно перекодировать следующим образом. Если предсказываемое значение текущего элемента изображения совпадает с его реальным значением, то в новой рецепторной матрице пишется О, а если предсказываемое значение не совпадает с реальным значением текущего элемента, то в новой рецепторной матрице пишется.. Операция сравнения и выдачи сигнала ошибки может быть реализована с помощью суммирования по модулю два . V Х у о где у - сигнал ошибки; . xg - предсказываемое по формуле (1) значение текущего элемента изображения) xg - реальное значение текущего элемента изобра;:сения @ - логическая операция суммирования по модулю два. В новой матрице количество единиц уменьшается, а количество белых нулевых блоков возрастает. Результирующий коэффициент сжатия, измеренный для ряда типичных изображений, равен в среднем десяти, в то время как в известном устройстве он равен шести. Если в изображении встречаются отдельные черные элементы в окружении белых и отдельные белые элементы в окружении черных, то их значения по формуле (1) не предсказываются. В результате в новой рецепторной матрице на месте каждого одиночного элемента получают две ошибки предсказания, однако по сравнению с общим выигрышем проигрыш в кодировании таких одиночных элементов незначителен.

Кроме того, поскольку такие одиночные элементы обычно не несут сутцественной информации, можно с помощью спеииальных несложных схем инвертировать такие одиночные элементы с целью их устранения и повышения, та КИМ образом, общего коэффициента ежтия графического изображения. На фиг.2а представлена для примера фигура квадрата., подвергнутая перекодированию с помощью алгоритма двумерного предсказания по формулам (1 и (2) .В результате в новой рецепторной матрице (фиг.) остается всего три черных элемента, кодируемых единицами, т.е. всего-три раза предсказанное значение не совпад9ет с реальным значением . Несомненно коэффициент сжатия графического изображения,, изображенного на фиг.2, больше, чем графического изображения на фиг.2а.

Регистр 1 предназначен для приема в параллельном виде из блока 17 памяти кода засветки ненулевых блоков информации наименьших размеров (слов) и выдачи затем этого кода в последовательном виде под действием тактовых импульсов с выхода генератора 23 импульсов.

Регистр 2 предназначен для прием 3 параллельном виде из блока 18 памяти кодов управления словами в строках и выдачи затем этих кодов в последовательном виде под действием импульсов с выхода счетчика 20. Если очередной выдаваемый регистром 2 разряд равен единице, то это означает, что в очередном наименьшем блоке графической информации (слове есть информация. В этом случае этот единичный импульс, складываясь с им пульсом переноса, с выхода счетчика 20 проходит через первый элемент И 11 на управляющий вход блока 17 пмяти и инициирует считывание этого ненулевого блока наименьших размеров (слова) в параллельном виде в первый регистр 1. Если же очередной разряд на выходе регистра 2 равен нулю, это означает, что очередной наименьший блок графической информации (слова) равен нулю. В этом случае считывания кода засвета из блока 17 памяти не происходит, и под действием импульсов с выхода генератора 23 импульсов, с выхода регистра 1 считываются одни нули, что н необходимо выдавать,

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

случае этот единичный сигнал, складываясь на элементе И 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, соответствунзоие входы элемента И 11, регистра 2. Под действ 1Г ем этого импульса содержимое регистра 2 сдвигается вправо на один разряд, а записанный в крайней правой его ячейке разряд подается при этом на вход элемента И 11. / Счетчик 21 считает с периодом, равным числу слов в строке. По окон чании каждой строки, таким образом, он выдает на своем выходе импульс. переноса, поступающий на счетный вх счетчика 22, вход элемента И 12 и вход регистра 3. Под действием этого импульса содержимое регистра 3 сдвигается вправо на один разряд, а разряд, записанный до сдвига в краиней правой ячейке, подается при этом на вход элемента И 12. Счетчик 22 считает и выдает на своем выходе импульс переноса с периодичностью, равной частоте следования групп строк. Таким образом, п окончании развертки очередной групп строк на выходе счетчика 22 появляется импульс, который поступает на вход элемента И 13 и вход регистра Под действием этого импульса содержимое регистра 4 сдвигается вправо на один разряд, а разряд, находившийся до сдвига в правой крайней ячейке, подается на вход элемента И 13. -Элементы 1-4, 11-13, 17-19 и 2024 предназначены для декодирования графической информации, закодирован ной с помощью четырехкаскадного одномерного самоадаптирующегося блочного кода. Элементы 5-10 и 14-16 предназначены для получения исходного графическОго изображения. На один из вхо .дов сумматора 24 по модулю два пода ется рецепторная матрица, перекодированная с помощью ал оритма двумерного предсказания, . подаются ошибки в предсказании у. Если отображается, например, фигура квадрата (фиг.2а) то на один из входов сумматора 24 подается рецепторная матрица (фиг.2(У). Значение сигнала ошибки в предсказании сравнива ется с подсказанным по формуле {1) значением текущего элемента xg., подаваемым на другой вход сумматора 24. Если сигнал ошибки равен нулю, это означа ёт, что предсказанное зна чение х5 совпадает с реальным значением хо , и сигнал xV. проходит на выход сумматора 24. Если же сигнал равен единице, это означает, что значение хЪ. должно быть инвертировано, что и происходит на сумма торе 24. Формула его р&боты у ® х5 х , где у - подаваемый на первый вход сумматора 24 сигнал ошибки предсказания текущего элемента-, предсказанное значение текущего элемента, подаваемое на второй вход сумматора 24 истинное значение текущего элемента изображения, получаемое на выходе сумматора 24 на основе предсказанного значения xj и ошибки предсказания текущего элемента yj 0 - логическая операция суммирования по модулю два. , Элементы 5-10, 14-16 предназначены для получения значения хр формуле (1). Регистр 5 предназначен для задержки значения сигнала х на один такт и получения таким образом на его выходе значения соседнего сигнала х. Регистр 6 предназначен для задержки значения сигнала х на количество тактов, равное числу элементов разложения изображения в строке минус единица. На выходе регистра 6 таким образом имеем сигнал хз. Регистр 7 предназначен для задержки на один такт сигнала Xj, на его выходе получают сигнал Х2 . Регистр 8 предназначен для задержки на один такт сигнала Xj и получения на выходе регистра таким образом сигнала Хц. Элемент НЕ 16 предназначен для получения отрицания сигнала х, необходимого для вычисления х по формуле (1). Элемент ИЛИ 14 предназначен-для получения сомножителя х, x.c , входящего в формулу (1), элемент И 9 - дря получения первого слагаемого X t(xjV X.J.Y х ), входящего в Формулу (1), элемент И 10 - для получения второго слагаемого , входящего в формулу (1). На выходе элемента ИЛИ 15 получается искомое предсказываемое значение текущего элемента изображения х, получаемое по формуле (1). ; Выход 25 устройства предназначен для подачи декодированного сигнала рецепторной матрицы графического изображения намодулятор телевизи онного индикатора. Блок перекодирования графического изображения, работающий по алгоритму двумерного предсказания (по формуле 1), с целью уменьшения количества черных элементов в изображении реализуется на элементах 5-10, 14-16 и 24. Если необходимо, например, перекодировать рецепторную матрицу графического изображения квадрата, изображенную на фиг. 2с., то на один из входов сумматора 24, выход которого отсоединяется от выхода 25 устройства, и выход 25 подают поэлементно и построчно рецепторную матрицу графического изображения на фиг.

другой вход сумматора 24 соединен с выходом элемента ИЛИ 15, ас выхода сумматора 24 последовательно снимается перекодированная реьепторная матрица ошибок в предсказании,изобра женная на фиг.. После блочного кодирования коэффициент сжатия графического изображения на фиг.2б больше, чем графического изображения на фиг.2С, поскольку нулевых блоков, кодируемых одним префиксом О, на фиг.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 является перекодированным по алгоритму двумерного предсказания. Поэтому прежде, чем его подать на 5 модулятор телевизионного индикатора, надо его декодировать, что и происходит на сумматоре 24 по модулю два, который осуществляет декодирование по формуле (3).

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

5 устройстве по сравнению с известным увеличивается примерно на 40-60% для ряда самых разнообразных графических изображений. Если коэффициент сжатия, полученный для известного

Q устройства на ряде типичных графических изображений равен шести, то для предлагаемого устройства коэффициент сжатия в среднем равен десяти для тех же графических изображе5 НИИ. Предлагаемое устройство позволяет по сравнению с известным отображать более разнообразные графические изображения с коэффициентом сжатия 1. Вследствие этого предлагаемое устройство позволяет по сра0 внению с извес1.1ым получить в среднем больший примерно на 40-60% выигрыш во времени загрузки информационных магистралей под пересылку адресованной графической информации, а

5 также в объеме внешней памяти для хранения этой закодированной графической информации.

По сравнению с базовым объектом 0 .дисплейным комплексом АГАТ-2000 М, в котором для отображения графической информации используется структурно-символический метод (поле экрана разбито на знакоместа, каждое знакоместо описывается матрицей 7Х.16 точек, в каждом знакоместе может отображаться один из 73 заранее, выбранных графических элементов , в то время как число различных конфигураций графоэлементов в

0 знакоместе с учетом того, что во избежание черезстрочных мельканий информация в четном и нечетном полукадрах одинакова, равно 9 лагаемое устройство позволяет автоматически воспроизводить любое графическое изображение с исходной точностью, т.е. на участке lf.lQ могут быть отображены все возможные 2® конфигурации. При этом объем закоди0 рованной графической информации для предлагаемого усвройства в среднем даже меньше, чем в дисплейном комплексе АГАТ-2000 М. В дисплейном комплексе АГАТ-2000 М объем закодиро5 ванной графической информации равен

произведению количества знакомест (на количество двоичных разрядов, неовходимых для кодирования одного из 73 графоэлементов (32464 8. Коэффициент сжатия в базовом объекте в предположении, что информация в четном и нечетном полукадрах одинакова, равен отношению объема рецепторной матрицы изображения к объему .графической информации, закодирован.ной структурно-символическим методом

32-64

8

й- 32.648

Таким образом/ по сравнению с базовым объектом в предлагаемом устройстве коэффициент сжатия больше, а точность воспроизведения равна точности исходного изображения, т.е. намного выше, чем в базовом ; объекте.

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ, содержащее первый регистр,- один из входов которого соединен с. выходом первого блока памяти, вход которого соединен с выходом первого элемента И, один из входов которого соединен с выходом второго регистра, один из входов которого соединен с выходом второго блока памяти, вход которого соединен с выходом второго элемента И, один из входов которого соединен с выходом третьего регистра, один из входов которого соединен с выходом третьего блока памяти, вход которого соединен с выходом третьего элемента И, один из входов которого соединен с выходом четвертого регистра, вход которого соединен с другим входом третьего элемента И и выходом первого счетчика, вход которого соединен с другим входом третьего регистра, другим входом второго элемента И и выходом второго счетчика, вход которого соеди- , ней с другим.входом второго регистра,. другим входом первого элемента И и выходом первого счетчика, вход которого соединен с другим входом первого регистра и выходом генератора импульсов, отличающееся тем, что, с целью упрощения устройства, оно содержит сумматор, пятый, шестой, седьмой и восьмой регистры, элемент НЕ, первый и второй элементы ИЛИ, четвертый и пятый элементы И, выход первого регистра соединен с одним из входов сумматора, выход которого соединен с одним из входов пятого регистра и одним из входов шестрго регистра, выход которого соединен с первым входом первого элемента ИЛИ, первым входом пятого элемента И и одним из входов седь(Л мого регистра, выход которого соединен с вторым входом первого элемента ИЛИ, вторьтм входом пятого элемента И и с одним из входов восьмого регистра, выход которого соединен с входом элемента НЕ, выход которого соединен с третьим входом пятого элемента И и третьим входом первого элемента ИЛИ, выход которого соединен с одним из входов четвертого элемента И, другой вход которого соединен с выходом пятого регистра, выходы четвертого и пятого элементов И соединены соответственно с первым и вторым входами второго эле,мента ИЛИ, выход которого соединенс другим входом сумматора, выход ко.торого является выходом устройства, другой вход пятого, шестого, седьмого и восьмого регистров соединен с выходом генератора импульсов,