автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Организация средств визуализации изображений в компьютерных системах поддержки диалога

РГ6 од

2 ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

На правах рукописи

ХАРИТОНЕНКО ИГОРЬ ОЛЕГОВИЧ

УДК 681.3.053

ОРГАНИЗАЦИЯ СРЕДСТВ ВИЗУАЛИЗАЦИИ ИЗОБРАЖЕНИЙ В КОМПЬЮТЕРНЫХ СИСТЕМАХ ПОДДЕРЖКИ ДИАЛОГА

05.13.05 - Элементы и устройства вычислительной техники и систем управления

Автореферат диссертации на соискание ученой степени кандидата технических наук

Одесса 1993

Работа выполнена на кафедре прикладной математики и вычислительной техники Одесского института низкотемпературной техники и энергетики.

Научные руководители: ^

академик АНТ Украины, доктор технических наук, профессор Коноплев Игорь Дмитриевич, кандидат технических наук, доцент Чмырь Игорь Алексеевич

Официальные оппоненты: доктор технических наук, прфессор Спокойный Юрий Ефимович, кандидат технических наук, с.н.с. Мещеряков Владимир Иванович

Ведущая организация: Одесский научно-исследовательский институт телевизионной техники

Защита состоится 30 1993 г. в на

заседании специализированного совета К 068.19.04 по присуждению ученой степени кандидата технических наук в Одесском политехническом университете по адресу: 270044, г. Одесса, пр. Шевченко, 1.

Автореферат разослан

"29" ¿¿ал 1993 г.

Ученый секретарь специализированного совета К 068.19.04 , к.т.н.

Капинос В.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. В области электронной обработки данных наиболее приемлемой формой общения конечного пользователя с компьютером является диалог. Получение информации этим методом позволяет значительно сократить объем дополнительных сведений, с которыми необходимо ознакомиться прежде, чем решать с помощью ЭВМ основную задачу..

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

Таким образом, конкурентоспособность диалоговых систем во многом зависит от решения проблемы повышения скорости вывода видеоинформации. В особенности, это актуально при использовании персональных компьютеров. Хотя проблеме повышения скорости вывода видеоинформации посвящено значительное количество работ, большинство из них рассматривают эту проблему применительно к САПР, тренажерным комплексам, АСУ и т.д. Однако, учитывая что ориентация на концепцию диалогового общения является более универсальной, чем ориентация на любую из перечисленных, существующие подходы не будут достаточно эффективны при использовании в системе поддержки диалога. Следовательно, разработка методов и средств ускоренного вывода видеоинформации в системах поддержки диалога на персональных компьютерах является актуальной проблемой, а решение ее приведет к улучшению потребительских качеств систем, ориентированных на диалог.

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

Метопы прпяегтрния исследований. При решении поставленных в диссертации задач использовались аналитические и вычислительные методы современного математического аппарата, а именно:

а) теория вероятностей и математическая статистика;

б) линейная алгебра и матричный анализ;

в) объектно-ориетгированное программирование.

Научная новизна. На защиту выносятся следующие результаты, впервые полученные в настоящей работе:

1. Метод формирования описания иллюстративной графики, базирующийся на компрессии информации и использующий модель изображения, описываемую переключающимся дискретным источником.

2. Аналитические оценки коэффициентов двумерного преобразования Уолша-Адамара для входного процесса, описываемого набором векторов, удовлетворяющих условию Липшица.

3. Способ отбора коэффициентов двумерного преобразования Уолша-Адамара, обеспечивающий меньшее среднеквадратичное отклонение при компрессии реалистических изображений по сравнению с традиционным зональным отбором, выполняемым, исходя из особенностей зрительного восприятия.

4. Структура метафайла и организация служебной информации, отвечающие как требованию высокой скорости доступа к элементам сценария при его интерпретации, так и возможности внесения изменений в диалоговый процесс.

5. Архитектура компьютера, позволяющая аппаратно выполнять специфические функции человеко-машинного диалога.

6. Структуры устройств, позволяющих в системе диалогового общения выполнять визуализацию изебражений в реальном масштабе времени.

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

Внедрение научных результатов. Полученные в диссертации результаты внедрены в НИИ "Шторм" (г. Одесса) и ИИЦ Гипрохиммаш (г. Киев).

Апробация работы. Результаты работы над диссертацией обсуждались

на:

- всесоюзной конференции "Организация управления производством в новых условиях хозяйствования" в 1990г. в г. Одессе;

- международной конференции-ярмарке "Технология программирования 90-х" в 1991г. в г. Киеве;

- семинаре "Инструментальные средства програмирования" в 1992г. в г. Одессе.

Публикации, Основные результаты диссертационной работы отражены в [1...8].

Объем н структура пнгсертанноннон работы. Диссертация содержит введение, пять глав, заключение, список использованной литературы, включающий в себя 85 наименований и приложения. Объем диссертации

составляет 129 страниц, включая 104 страницы основного текта, 17 страниц рисунков, 2 страницы таблиц и б страниц списка литературы.

СОДЕРЖАНИЕ РАБОТЫ

Первая глава содержит анализ литературных источников, из которых следует, что в области организации средств визуализации изображении в системах поддержки диалога остаются нерешенными следующие задачи:

1. Определение числа классов изображений, достаточного для эффективного ведения диалога пользователя с компьютером.

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

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

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

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

Вторая глава диссертации посвящена вопросам организации управляющей 'Структуры диалогового процесса - сценария диалога и проблемам, связанным с его хранением. Проблема формирования содержащихся в сценарии описаний видеообъектов рассмотрена с позиций общей теории систем, что позволяет любой из существующих методов создания описания отнести к одной из двух групп: атрибутивному и неатрибутивному.

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

Исходя из цели обеспечения эффективного диалога, выделены три класса видеообъектов, достаточные для покрытия запросов зрительного восприятия человека: чертежные, иллюстративные и реалистические.

Отмечено, что при создания описания чертежной графики, с точки зрения компактности и простоты, наиболее эффективны методы, относящиеся к группе атрибутивных.

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

При оценке методов с позиции эффективности компрессии информации основополагающее значение имеет их соответствие модели источника, порождающего эту информацию. Анализ существующих методов показал, что ни один из них не может быть использован в составе системы поддержки диалога. Основные причины - значительный расход оперативной памяти, большое количество вычислительных операций либо низкий коэффициент компрессии, что объясняется недостаточно точно выбранной моделью, описывающей изображение. В связи с этим разработку эффективного алгоритма компрессии с низким расходом оперативной памяти предложено вести на основе блочного кодирования переключающегося дискретного источника О) , учитывающего области локальной статистической однородности изображений и описываемого в виде:

¿0" {(1)0,0)

где О)о,0)1 ,...,0)т - П1 источников, воспроизводящих символы алфавита 5 ;

О)0 ~ управляющий источник над алфавитом О = | 1 ГП |

Показано, что стоимость кодирования () изображения, разбитого на блоки размером в N пикселов, составляет:

(3 = 1(^2 ( к + 1) + N • ( 1 - р (к))

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

Прн этом возрастание числа направлений от к! до кг приводит к уменьшению стоимости кодирования, если выполняется условие:

Ар > ( 1(^2 ( кг + 1) - 1(^2 ( к1 + 1 ) ) Ж

Следовательно, можно утверждать, что, с одной стороны, необходимо из всех возможных направлений выбрать только те, которые обеспсчи-

вают требуемый рост Ар, а с другой, - найти пути сокращения длины кода по сравнению с ( к + I).

Показано, что для блока /3 (х,у,х), где X - позиция блока в строке; у - номер строки; ъ - номер плоскости, наиболее вероятно совпадение с блоками (х-I ,у,г), (х , у - 1 , г) , /Зз ( х , у, т. - 1 ) ,

$4 ( х ,У, 1 — 2 ), /?5 ( х , у, 2 — 3 ). Учитывая, что поиск совпадающих блоков должен выполнятся только над массивом, содержащим изображение, получаем:

- если х> 0,у = = 1;

- е'сли'х= 0,у> 0;г = 1;

и у?2 ~ если х> о > У > о;2 = 1;

у53 - если х= 0,у> 0;г= 2;

убШ/Зги^З - если х> 0,у> 0;г= 2;

и уЗз и /54 - если х= 0,у> 0;г= 3;

р1 и /32 и /З3 и /34 и - если х> 0,у> 0 ; г = 4.

Это может быгь представлено в виде переключающегося дискретного источника:

СО

= {(1)0,(01,(02,(03,0)4 },

в котором управляющий источник Ù)о задается переключающей функцией D = 2 U+( X ) U U+( у) , где U+ - ступенчатая функция, а источники Û)i ,...,Ù)4 описываются марковской моделью первого порядка над алфавитом S = | 0 255 J..

Для кодирования каждого из элементарных источников предложено использовать адаптивный алгоритм "кодирование по степени новизны", с тем отличием, что кодированию подвергаются не блоки, а направления. На каждом шаге проверяется наличие совпадения с блоком, соответствующим наиболее короткой ветви кодово-понскового дерева данного источника, т.е. поиск начинается в том направлении, где вероятность совпадения наиболее высока. В случае успеха это позволяет выполнять поиск бытсрес, чем при полном переборе и кодировать совпавший блок только одним битом. Если совпадения нет, то на первое место перемещается направление, соответствующее первому из совпавших блоков.

Сравнение с наиболее распространенными в настоящее время архиваторами показало следующее: данный метод позволяет добиться более высокого сжатия, чем у LZSS.EXE, построенного на основе ЬХ метода, а одному из наиболее эффективных ARJ.EXE, использующему двухступенчатое кодирование, уступает не более, чем 15-20% (см. таблицу).

Файл Исходный размер (байт) Метод Хаффма-на (байт) RLE (байт) LZSS (байт) ARJ (байт) Адаптивный (байт)

a.bit 32187 8096 11555 ■ 8092 5705 7652

b.bit 32187 11978 15929 9859 5572 6439

c-bit 112027 44872 43775 40619 31711 36473

Отмечено, что предлагаемый метод, сочетающий эффективную компрессию и низкий расход памяти (приблизительно в 25 раз меньший, чем у ARJ.EXE), может использоваться в составе крупных программных систем.

Результаты экспериментальной оценки времени визуализации на IBM-совместимых персональных компьютерах похазали, что данный метод не позволяет повысить скорость вывода изображений при использовании стандартного оборудования. Основная причина - "семантический разрыв", т.е. различие принципов, лежащих в основе предлагаемого метода компрессии и фон-Неймановского компьютера. Отмечено, что это явление не может быть полностью устранено в рамках стандартного оборудования.

Далее в третьей главе рассматривается проблема компрессии реалистических видеообъектов. Исходя из имеющихся в литературе результатов, из огромного многообразия подходов были выделены методы компрессии, построенные на основе двумерного преобразования Уолша-Адамара:

B(n,n) = 4r-H(n)-X(n,n)-H(n), П

где п = 2' , i = 1,2,3

X ( П , П ) - массив входных значений

В ( Л , П ) — массив коэффициентов преобразования

Н ( П ) - матрица Адамара, состоящая из базисных ортогональных функции. Его достоинство, связанное с простотой вычисления, полностью компенсирует некоторое снижение коэффициента компрессии по сравнению с другими преобразованиями. .

Большинство исследований в области компрессии изображений касается в большей степени разработки быстрых алгоритмов ортогональных преобразований, в то время, как эффективность сжатия, в первую очередь, определяется эффективностью методов, следующих за преобразованием. К ним относится метод, известный как зональное кодирование. Он может быть представлен в виде двух этапов.

На первом этапе информация разбивается на неперекрывающиеся блоки размером N * N. Затем каждый из блоков подвергается ортогональному преобразованию. Обычно используют блоки с N = 8.

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

В работе получены аналитические оценки коэффициентов матрицы В для входного процесса, описываемого набором векторов, удовлетворяющих условию Липшица:

max I xj-i - xi I < л , где 0 < i < N.

Согласно имеющимся в литературе данным этот класс векторов является достаточно точной моделью, описывающей реалистические изображения

Показано, что для N = 8 значения коэффициентов преобразования определяются выражением:

max lb [i , j] I = SA 2r+s_1,

где r - номер младшего ненулевого разряда в двоичной комбинации i , S - номер младшего ненулевого разряда в двоичной комбинации j,

О < i < 8 , 0 < j < 8.

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

Кс = 4 приведено ниже (сохраняемые области выделены черным цветом).

Полученные экспериментально данные для тестовых изображений с различной детальностью подтверждают правильность предлагаемой методики отбора, которая несколько отличается от традиционной. Она обеспечивает приблизительно на 5-10% меньше среднеквадратнческое отклонение при восстановлении изображений и их лучшее субъективное восприятие.

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

Четвертая глава посвящена вопросам программной реализации средств визуализации диалоговой системы. Указывается, что инерционные свойства системы будут в большей степени зависеть от скорости интерпретации описаний видеообъектов, чем от скорости генерации описаний. Поскольку в состав системы обязательно входит человек, проблема повышения потребительских характеристик не может рассматриваться только как совокупность физических показателей. В связи с этим при разработке системы были учтены такие проблемы, как обеспечение удобства формирования и редактирования сценария диалога, наличие речевого сопровождения действий пользователя, присутствие вынужденных пауз, связанных с принятием решения человеком.

Отмечено, что реализация столь крупной системы на персональном компьютере, работающем в операционной среде MS/DOS, может быть успешно решена только путем динамического распределения оперативной памяти на каждом шаге диалога.

Рассмотрена организация метафайла — описания сценария диалога, хранимого на дисковой памяти компьютера. Он состоит из двух частей: описания интерпретируемых объектов и описания процесса взаимодействия этих обьектов с пользователем. Метафайл имеет ссгментно-странич-ную организацию. Каждый сегмент содержит описание одного из объектов либо управляющей информации. Размер страницы был выбран исходя из максимального размера метафайла, максимального размера

сегмента, допустимых потерь, вызванных неполным использованием последней страницы в сегменте, и минимизации размера таблицы интерпретации сценария. Эти требования во многом противоречивы. Поиск компромиссного решения привел к размеру страницы 256 байт. Это, при длине указателей страницы в 2 байта, позволяет формировать метафайлы до 16 МБайт. С другой стороны, учитывая, что размер сегмента не может превышать 64 КНайт, для указателя длины сегмента можно использовать один байт. При меньшем размере страницы возрастают трудности с организацией процесса корректировки метафайла на этапе генерации.

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

Показано, что для удобства генерации и редактирования сценария, метафайл удобно разбивать на несколько логически законченных сценарных блоков. Служебная информация SIT, описывающая процесс взаимодействия элементов сценария с пользователем, имеет смешанную списково-табличную организацию. Она построена таким образом, что в пределах одном сцены диалога функционируют только табличные указатели. Это способствует достижению высокой скорости поиска информации" в метафайле. В момент перехода к другой сцене происходит поиск по списку, что не сказывается на субъективном восприятии динамики ведения диалога в силу инерционности аудио-визуальных возможностей человека. С другой стороны, списковая структура позволяет просто и наглядно организовать процесс редактирования сценария.

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

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

Отмечается, что практическая работа с системой "Процессор Диалога", разработанной с учетом описанных принципов компрессии, поиска и чтения информации, показала приемлемость ее потребительских характеристик.

ва" при реализации диалоговых систем. Показано, что существующие концепции построения компьютеров с не фон-Неймановской архитектурой могут быть дополнены эротематическнм компьютером. Его архитек-

посвящена вопросам устранения "семанл1Чсского разры-

тура базируется на ряде предположении о структуре человеко-машинного диалога:

1. Компьютер в процессе диалога является активным партнером, а пользователь пассивным - отвечающим. Все необходимые для ведения диалога вопросы хранятся в компьютере.

2. На очередной ответ пользователя компьютер всегда выбирает только один следующий вопрос. .. .

3. При выборе очередного вопроса учитывается как ответ пользователя на текущем шаге диалога, так и ответы, сделанные на предыдущих.

4. Существует стандартный, не зависящий от семантики диалога процесс, позволяющий выбрать очередной вопрос, как реализацию на полученный ответ.

5. При анализе вопроса и формировании ответа могут использоваться "внешние" но отношению к стандартному процессы.

В сформулированных предложениях вопрос понимается не в лингвистическом смысле, как вопросительное предложение, а в эротематиче-ском, как совокупность субъекта и предпосылки.

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

Ii рамках предложенной концепции разработаны устройства интерпретации описания реалистических к иллюстратавных видеообъектов, использующие предложенные в главе 3 методы декомпрессии.

В результате анализа различных вариантов показано, что устройство интерпретации описания реалистических видеообъектов, разработанное на основе процессора быстрого преобразования Уолша-Адамара с последовательной органзацией, обеспечивает визуализацию в реальном времени. г/риведена структурная схема устройства н временная диаграмма, поясняющая его работу. Использование разреженности матрицы входных данных позволяет снизить число рабочих тактов приблизительно на 30% по сравнению со стандартным построчно-столбцевым вычислением. Отмечается, что процессоры с другой организацией хуже согласуются с потоком входных данных и поэтому не рациональны.

Показано, что при длительности вычисления базовой операции равной 160 нсек, на декомпрессию и вывод изображения размером 320*200 пикселов уйдет около 22 мсек. С другой стороны, исполнение процессора в виде БИС, содержащей коммутатор, два буфера общим объемом 136 байт, устройство управления и арифметическое устройство, состоящее из

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

Указано, что основными причинами, не позволяющими эффективно организовать работу алгоритма декомпрессии иллюстративной графики на стандартной аппаратуре, являются сложность обработки кодов переменной длины, а также выполнение копирования блоков через процессор, что требует постоянной перенастройки сегментных регистров. Кроме того, большое число операций с памятью и наличие циклов не позволяет эффективно использовать очередь команд, снижая производительность процессора. С другой стороны, простота алгоритма декомпрессии, заключающаяся в циклическом повторении малого набора простых операций с памятью, позволяет достичь низких затрат при аппаратной реализации. Обработка кодов переменной длины при аппаратном исполнении также • весьма проста и состоит из занесения порции информации в сдвиговый регистр с последующей по-тактовой загрузкой данных в цифровой компаратор. Упрощает задачу и то, что максимальная длина кода не превышает 5 бит. Структурная схема устройства приведена ниже.

Dac D

Dbvte

Буфер словаря

CSD

Буферный регистр

|CSr

Rav

Устройство управления

Dac В

Bword

CSr, CSTI

Дешифратор кодов

CST4

RAv

ОЗУ таблиц 4*6 слов

системная шина

CSi

CS4

Addr

RAV

Видеопамять

RAv

Вспомогательный регистр

Dac - сигнал запроса к контроллеру ПДП; CS - сигнал выборки элемента; Addr - адрес в пределах плоскости; R/W - сигнал записи/чтения

Показано, что число тактов, необходимых на декомпрессию и вывод изображения определяется формулой:

2т = Бу Ъг ( 4Бх - рцч (2Бх - 5 )) ,

где Ох, Юу, Лх - размеры изображения,

РШ ~ вероятность совпадения строк.

Если теперь принять длительность такта равной 80 нсек (типовое время выборки микросхем памяти 1ВМ АТ компьютеров) и рцч = 0*5 , получаем, что декомпрессия и вывод 16-цветного изображения размером 640*350 пикселов займет порядка 27 мсек. В работе приведены оценки времени визуализации при использовании разработанного устройства в компьютере 1ВМ АТ 286/12 для трех тестовых изображении. Они ' составляют соответственно 0.069, 0.058 и 0.31 сек, тогда как при использовании стандартного оборудования - 0.65, 0.65 и 2.61 сек.

Сравнение значений скорости визуализации с аналогичными показателями для визуализации без компрессии позволяют говорить о значительном ускорении процесса. Это объясняется не только высокой производительностью предлагаемого устройства, но и сокращением в Кс раз продолжительности чтения описания с диска и объема пересылок через системную шину. Отмечено, что использование для этих целей высокопроизводительных многоканальных устройств, в основу которых не заложена компрессия/декомпрессия информации, не будет столь эффективно. Учитывая высокую скорость обработки, при которой на вывод изображения в четверть экрана затрачивается менее 10 мсек, данное устройство можно использовать для горизонтального и вертикального перемещения изображений в реальном масштабе времени. Вместе с тем, невысокая сложность описанного выше устройства позволяет рассчитывать на его реализацию в виде БИС.

В заключении подведены итоги работы и сформулированы основные результаты, которые сводятся к следующему.

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

пых устройств визуализации. При выполнении исследований решены следующие задачи:

1. Показано, что при неизменных параметрах, определяемых техническими характеристиками компьютера, ускорение визуализации изображения может быть достигнуто путем сокращения объема его описания.

2. Разработан метод создания описания иллюстративной графики, базирующийся на компрессии информации. В его основу положена построенная с учетом статистической модели изображения адаптация к изменениям яркости и цвета в сочетании с динамическим кодированием направлений поиска информационной избыточности. Приведены экспериментальные оценки коэффициента компрессии Кс и времени визуализации для тестовых изображений.

3. Получены'аналитические оценки коэффициентов двумерного преобразования Уолша-Адамара для входного процесса, описываемого набором липшицевых векторов. На основании этих оценок, при Кс равном 2 и 4, получены зоны отбора коэффициентов преобразования, соответствующие значениям с максимальной амплитудой. Для тестовых изображений с различной детальностью, получены экспериментальные оценки среднеквадратичного отклонения и усредненных значений коэффициен- ^ тов преобразования при традиционном и предлагаемом способах отбора.

4. Предложены структура метафайла и организация служебной информации, отвечающие как требованию высокой скорости доступа к элементам сценария при его интерпретации, так и возможности внесения изменений в диалоговый процесс.

5. Предложена архитектура компьютера, позволяющая аппаратно * выполнять специфические функции человеко-машинного диалога. Предлагаемый компьютер рассматривается как расширение классического однопроцессорного компьютера с фон-Неймановской организацией и позволяющая за счет устранения "семантического разрыва" повысить потребительские характеристики систем поддержки диалога.

6. На основании предложенных методов компрессии видеоинформации разработаны устройства восстановления изображений по их описанию, позволяющие добиться высоких динамических показателей при . интерпретации сценария диалога. Простота устройств позволяет реализовать их в виде ВИС, включаемых в состав видеоконтроллеров.

1. В основу организации средств визуализации изображений диалоговых компьютерных систем с хранимым сценарием должна быть положена компрессия информации. Это, с одной стороны, позволяет за счет сокращения в Кс раз объема хранимой на диске информации

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

2. Предлагаемый метод компрессии описания видеообъектов, относящихся к иллюстративной графике, позволяет:

- снизить по сравнению с алгоритмами на основе LZ метода требования к объему оперативной памяти, необходимой для хранения служебной информации, с 100-300 КБайт до 120-150 байт. Это объясняется тем, что в отличие от методов универсального кодирования, предлагаемый использует статистическую модель изображения, а следовательно, позволяет организовать поиск информационной избыточности без применения сложных и громоздких структур;

- добиться более высокого коэффициента компрессии, чем при использовании методов сжатия графической информации RLE и Skip-on-Equal, статистических Хаффмана и Шеннона-Фано, а также универсального кодирования LZ;

- проще, чем при статистическом кодировании организовать шифри-рование и дешифрирование кодов переменной длины, поскольку исполь- — зование направлений поиска совпадающих блоков (максимальное количество равно 5), а не самих блоков (до 256), значительно сокращает длину этого кода.

3. Согласно полученным оценкам коэффициентов преобразования Уолша-Адамара, для двумерного входного сигнала, описывыемого набором липшнцевых векторов с одинаковой величиной скачка А вдоль строк и столбцов, зоны отбора коэффициентов несколько отличаются от традиционных, полученных исходя из особенностей зрительного восприятия. Педлагаемый способ отбора, полученный на основе этих оценок, позволяет добиться меньшего среднеквадратичного отклонения декомп- . рессированных изображений, что подтверждается результатами экспериментов. Субъективная оценка качества для тестовых изображений не показала ухудшения восприятия по сравнению с традиционным отбором. Напротив, изображение характеризуется лучшей передачей элементов с высокой детальностью, что компенсирует некоторое ухудшение при отоборжении резких яркостных переходов не совпадающих с границами блоков.

4. Наличие "семантического разрыва" не позволяет эффективно организовать процесс интерпретации описаний видеообъектов при использовании стандартного оборудования. Различие принципов, лежащих в основе фон-Неймановского компьютера и предлагаемых методов компрессии/декомпрессии приводит к низкой скорости обработки. С

другой стороны, алгоритмы легко реализуемые в рамках стандартного оборудования (например RLE), обладают низкими показателями Кс-Существенно уменьшить влияние "семантического разрыва" можно за счет дополнения стандартной архитектуры специализированным видеоконтроллером, аппаратно выполняющим операции, лежащие в основе предлагаемых методов декомпрессии. С другой стороны, повышать скорость компрессии можно лишь за счет оптимизации на программном уровне. Это связано с наличием значительных временных промежутков, вызванных продумыванием сцены при генерации диалоговых приложений, во время которых и может выполняться компрессия.

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

— сокращением в Кс раз времени считывания описания изображения с диска и передачи его по системной шине;

— увеличением приблизительно в 5 раз средней скорости записи в видеопамять по сравнению с EGA и VGA адаптерами, доступ к которым разрешен только во время обратного хода луча развертки;

— применением специализированных средств выполнения базовой операции преобразования Уолша-Адамара и обработки кодов переменной длины в сочетании с конвейеризацией прцессов.

Высокая скорость декомпрессии, при которой на вывод изображения в четверть экрана затрачивается менее 10 мсек, позволяет использовать данные устройства для горизонтального и вертикального перемещения изображений в реальном масштабе времени.

Основные результаты диссертационной работы содержатся в следующих работах:

1. Харитоненко И.О., Цевух И.В. Кластеризация случайных процессов методом выдвигания кластеров//Сб. рефератов НИОКР, 1986, Сер. AT N5, ВИМИ;

2. Баранов П.Е., Муранов A.C., Харитоненко И.О., Цевух И.В. Классификатор номеховой обстановки. Авт. свид. СССР N1299301, МКИ G 01 S 7/30. Заявлено 15.07.85;

3. Харитоненко И. О., Португал И. В. Использование быстрых алгоритмов машинной графики в-пакетах программ АСУ/Всесоюзная конференция "Организация управления производством", Одесса, 1990, с. 139-140.

4. Чмырь И. А., Ус М. Ф., Харитоненко И. О. "Процессор диалога" - инструментальная система для разработки диалоговых приложений/

Международная конференция "Технология программирования 90-х", Киев, 1991, с. 57-58.

5. Чмырь И. А., Харитоненко И. О. Проблемы разработки высокопроизводительных программно-аппаратных средств компрессии/декомпрессии изображений/Семинар " Инструментальные средства программирования", Одесса, 1992, с. 83-84.

6. Харитоненко И.О. Применение специализированных графических процессоров для повышения эффективности САПР//Вопросы радиоэлектроники. Сер. ТРТО. -1991. -N3, с. 96-101;

7. Чмырь И.А., Харитоненко И.О. Архитектура компьютера, ориентированная на диалоговый процесс//Вопросы радиоэлектроники. Сер. ТРТО. -1992. -N3, С. 15-21;

8. Харитоненко И.О. Метод адаптивней компрессии цветных игобрг-жений//Вопросы радиоэлектроники. Сер. ТРТО. -1992. N3, с. 102-107.

И.О. Харитоненко