Сжатие видеоданных графического интерфейса пользователя

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Д.В. Дружинин, А.В. Замятин 

СЖАТИЕ ВИДЕОДАННЫХ 

ГРАФИЧЕСКОГО ИНТЕРФЕЙСА 

ПОЛЬЗОВАТЕЛЯ

Учебное пособие

Томск

Издательство Томского государственного университета

2020

Сжатие видеоданных графического интерфейса пользователя

2

УДК 004.627
ББК 32.97

Д76

Дружинин Д.В., Замятин А.В.

Д76
Сжатие видеоданных графического интерфейса пользователя : 
учебное пособие. – Томск : Издательство Томского государственного университета, 2020. – 144 с.

ISBN 978-5-94621-934-1

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

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

Для студентов университетов и втузов.

УДК 004.627
ББК 32.97

Рецензенты:

кандидат технических наук, доцент А.В. Кудинов
доктор технических наук, профессор В.Г. Спицын

ISBN 978-5-94621-934-1

© Дружинин Д.В., Замятин А.В., 2020
© Томский государственный университет, 2020

Введение

3

ОГЛАВЛЕНИЕ

Введение ..........................................................................................................5
Глава 1. Анализ состояния проблемы ............................................................7

1.1. Сравнительный анализ видов видеоданных .....................................7
1.2. Сжатие ключевых кадров GUI-видео ..............................................15

1.2.1. Алгоритм группового кодирования ........................................15
1.2.2. Словарные алгоритмы сжатия .................................................16
1.2.3. Статистические алгоритмы сжатия.........................................20
1.2.4. Алгоритмы классификации блоков изображения..................22

1.3. Сжатие промежуточных кадров GUI-видео....................................23

1.3.1. Алгоритм отсечения неизменившихся блоков кадра ............23
1.3.2. Алгоритм оценки движения.....................................................25

1.4. Перспективные методы повышения 
эффективности сжатия GUI-видеоданных.............................................29

1.4.1. Использование вычислительных ресурсов видеокарты........29
1.4.2. Технологии определения изменившихся частей кадра 
в GUI-видео .........................................................................................33

Глава 2. Алгоритмическое обеспечение сжатия gui-видеоданных............37

2.1. Сжатие ключевых кадров GUI-видео ..............................................37

2.1.1. Сдвиговый алгоритм ................................................................38
2.1.2. Алгоритм пространственного группового кодирования.......40
2.1.3. Гибридный сдвигово-групповой алгоритм.............................43
2.1.4. Варианты алгоритма со сниженной 
пространственной избыточностью....................................................45

2.2. Сжатие промежуточных кадров GUI-видео....................................50

2.2.1. Алгоритм отсечения неизменившихся строк 
и столбцов в кадре ..............................................................................50
2.2.2. Адаптивный алгоритм отсечения 
неизменившихся областей в кадре....................................................55
2.2.3. Алгоритм оценки движения с учетом 
классификационных признаков.........................................................58

2.3. Требования и концептуальные основы создания 
программного обеспечения кодека для сжатия GUI-видеоданных .....64

2.3.1. Требования к программному обеспечению кодека ...............64

Сжатие видеоданных графического интерфейса пользователя

4

2.3.2. Концептуальные основы создания 
программного обеспечения кодека ...................................................65

Глава 3. Особенности практической реализации 
алгоритмов сжатия GUI-видеоданных.........................................................69

3.1. Сжатие ключевых кадров .................................................................69
3.2. Результаты экспериментальных исследований ..............................76

3.2.1. Сжатие ключевых кадров.........................................................77
3.2.2. Сжатие промежуточных кадров ..............................................86

Глава 4. Программное обеспечение кодека для сжатия
GUI-видеоданных ..........................................................................................95

4.1. Особенности программной реализации ..........................................95

4.1.1. Среда разработки программного обеспечения.......................95
4.1.2. Архитектура кодека..................................................................96
4.1.3. Программный интерфейс кодека...........................................102
4.1.4. Технология обработки данных ..............................................105

4.2. Подсистема высокопроизводительной обработки данных 
с использованием видеокарты...............................................................108

4.2.1. Реализация линейного и блочного сравнения 
изображений с помощью пиксельных шейдеров 
и Nvidia CUDA..................................................................................109
4.2.2. Алгоритм классификации блоков изображений, 
оптимизированный для выполнения на видеокарте......................111
4.2.3. Результаты экспериментальных исследований....................114

4.3. Результаты практического сравнения кодеков.............................118

Заключение...................................................................................................124
Список условных обозначений и сокращений ..........................................125
Список использованных источников и литературы .................................126

Введение

5

ВВЕДЕНИЕ

В начале XXI в. создание и применение видео различной 

природы стали доступными широкому кругу пользователей. Один 
из основных типов видео, распространенных среди пользователей 
персональных компьютеров (ПК), – видео графического интерфейса пользователя (Graphical User Interface видео, GUI-видео). 
Такое видео часто создают как необходимое дополнение к руководству пользователя информационно-программных комплексов 
или к описанию сценариев воспроизведения ошибок при взаимодействии команд разработчиков и инженеров по качеству программного обеспечения (ПО) для повышения эффективности их 
коммуникации.

Ввиду значительного объема видеоданных (данных, получаемых

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

Кроме того, приложения, осуществляющие фиксацию GUI-видео,

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

Сжатие видеоданных графического интерфейса пользователя

6

GUI-видеоданные существенно отличаются от традиционных

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

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

Глава 1. Анализ состояния проблемы

7

ГЛАВА 1.

АНАЛИЗ СОСТОЯНИЯ ПРОБЛЕМЫ

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

1.1. Сравнительный анализ видов видеоданных

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

Степень сжатия – отношение размера несжатых данных к раз
меру соответствующих им сжатых данных [4]. Максимальную 
степень сжатия данных каким-либо алгоритмом сжатия обозначим 
Cmax, минимальную – Сmin.

Видеоданные разделяют на традиционные (полученные с ви
деокамеры) и видеоданные графического интерфейса пользователя (Graphical User Interface видеоданные, GUI-видеоданные) –
отображение экрана персонального компьютера (ПК).

Кодек (англ. – codec) – программное обеспечение (ПО) преоб
разования видеоданных. В составе кодека будем выделять кодер и 
декодер, применяемые для кодирования и декодирования данных 
соответственно.

Сжатие видеоданных графического интерфейса пользователя

8

RGB (Red, Green, Blue – красный, зеленый, синий) – цветовая 

модель, в которой пиксель представлен тремя компонентами (R-, 
G-, B-компоненты).

С ростом возможностей персональных компьютеров большое 

количество пользователей получило возможность создавать, распространять и практически применять GUI-видео. GUI-видео часто создают как необходимое дополнение к руководству пользователя информационно-программных комплексов или к описанию 
сценария воспроизведения ошибок при взаимодействии команд 
разработчиков и инженеров по качеству ПО для повышения эффективности их коммуникации [129, 130]. Кроме того, GUI-видео 
создается рядовыми пользователями в режиме демонстрации 
собственного экрана компьютера с графическим интерфейсом 
пользователя собеседнику посредством телекоммуникационного 
ПО (Skype, Google Hangouts и др.) [76, 125].

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

Необходимость за ограниченное время сжимать изображения 

возникает не только при обработке GUI-видеоданных. Такая 
потребность возникает, например, в задачах дистанционного 
зондирования Земли, когда требуется оперативно сжимать значительные объемы данных, представляющих собой статические 
изображения. При этом вычисления проводят на бортовом компьютере спутника и пересылают по каналам связи, которые обладают сравнительно невысокой пропускной способностью [22–26, 28, 
35, 142, 143].

Глава 1. Анализ состояния проблемы

9

Программное обеспечение видеокомпрессии разделяют на две 

группы – симметричное и ассиметричное [4].

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

Симметричное ПО предъявляет одинаково жесткие требования 

на время, память и другие ресурсы компьютера как при кодировании, так и при декодировании. Примерами такого рода приложений могут служить видеопочта, видеотелефон, видеоконференции
[76, 125].

ПО, осуществляющее фиксацию GUI-видеоданных, разделяют 

на несколько групп, представленных в табл. 1.1.

Т а б л и ц а  1 . 1

Группы ПО для фиксации GUI-видеоданных

№
Группа ПО
Тип

1
Для мультимедийного общения 
(Skype, Google Hangouts и др.) [76, 125]
Симметричное

2, a
Для фиксации и локального 
сохранения GUI-видео

без оперативного сжатия
Ассиметричное

2, b
с оперативным сжатием
Симметричное

Стоит отметить, что приложения 1-й группы оперируют 

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

Сжатие видеоданных графического интерфейса пользователя

10

В настоящей работе решается задача разработки алгоритмиче
ского и программного обеспечения для фиксации и локального 
сохранения GUI-видео.

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

1. Требуется значительно больше дискового пространства. 

На практике при записи GUI-видеоданных без оперативного сжатия в минуту расходуется несколько гигабайт дискового пространства, в то время как с оперативным сжатием – порядка нескольких 
десятков мегабайт.

2. Требуется дополнительный этап обработки видеоданных, что 

увеличивает время, необходимое для формирования итогового видеофайла.

3. В случае записи на SSD-диск значительно быстрее расходу
ется его ресурс, напрямую связанный с количеством циклов перезаписи [105].

4. В случае записи на HDD значительно уменьшается производи
тельность записи данных другими приложениями за счет необходимости постоянного перемещения считывающей головки в разные 
секторы [105]. По результатам экспериментальных исследований,
на современном HDD уменьшение скорости записи составляет до 
трех раз, в то время как при оперативном сжатии эта проблема 
проявляется в гораздо меньшей степени.

Поэтому предпочтительным вариантом во второй группе ПО 

является вариант с оперативным сжатием, именно он и будет рассматриваться в дальнейшем в настоящей работе. 

Компонент приложений для фиксации и локального сохранения 

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

Глава 1. Анализ состояния проблемы

11

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

Видеоданные представляют собой последовательность кадров. 

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

Кадры видео разделяют на ключевые, сжимаемые независимо 

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

Все изображения разделяют на несколько классов [42]:
1. Монохроматическое (двухуровневое) изображение. В этом 

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

2. Полутоновое изображение (изображение в «градациях серо
го»). Каждый пиксель такого изображения может иметь 2n значений, где n – целое положительное число. 

3. Цветное изображение с непрерывным тоном. Такие изобра
жения имеют много сходных цветов, причем цвета сменяются 
плавно. Например, изображения с непрерывным тоном получают

Сжатие видеоданных графического интерфейса пользователя

12

ся при съемке на цифровую фотокамеру или при сканировании 
обычных фотографий. 

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

5. Цветное дискретно-тоновое (синтетическое) изображение. 

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

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

непрерывно-тоновых изображений. Такие алгоритмы эксплуатируют свойство непрерывно-тоновых изображений, которое и определило название этого класса изображений – наличие плавных 
цветовых переходов [42]. При этом устраняются малозаметные 
элементы, что сопровождается потерей информации. 

Дискретно-тоновые изображения в значительной мере отлича
ются от непрерывно-тоновых. При сжатии дискретно-тоновых 
изображений даже небольшой процент потерь может привести к 
значительному неприемлемому визуальному ухудшению их качества. Например, искажение всего нескольких пикселей буквы делает ее неразборчивой, преобразует привычное начертание в практически неразличимое [42, с. 120]. Поэтому применение алгоритмов, предназначенных для сжатия непрерывно-тоновых изображений, при обработке дискретно-тоновых изображений нецелесообразно. Этот же вывод распространяется на кадры GUI-видео, так 
как они в большинстве своем также относятся к классу дискретнотоновых изображений. В то же время в кадрах GUI-видео могут