Composite algorithm for screen video key frames compression.pdf Экранное видео - видео происходящего на экране пользователя. При этомфиксируется активность пользователя: движения курсора мыши, скроллинг, сво-рачивание и открытие свёрнутого окна, перемещение окна, ввод текста и т. д.Сжатие видео - одна из наиболее трудоёмких по времени задач, которые при-ходится решать не только профессионалам, но и рядовым пользователям. Однимиз типов видеоданных, сжатие которых необходимо осуществлять в режиме ре-ального времени, является экранное видео. Как правило, это видео высокого раз-решения. Причём зачастую о полезности программ, осуществляющих сжатие изапись на жёсткий диск этого типа видеоданных, можно говорить только в томслучае, когда их можно запустить в фоновом режиме.Поскольку при сжатии видео ключевые кадры кодируются независимо от дру-гих кадров, существует необходимость в быстрых алгоритмах сжатия изображе-ний. В соответствии с классификацией изображений, приведённой в [1], кадрыэкранного видео относятся к дискретно-тоновым изображениям. Для сжатия та-ких изображений, как правило, используются алгоритмы без потерь информации,так 0 TDкак при сжатии дискретнопоказано в разд. 3 «Результаты тестирования», такой комбинированный алгоритмпозволяет значительно увеличить степень сжатия по сравнению с алгоритмамисемейства LZO, способными сжимать экранное видео в режиме реального време-ни на широком спектре компьютеров пользователей.1. Схема комбинированного алгоритма сжатияБыл предложен следующий комбинированный алгоритм сжатия:На первом этапе исходное изображение обрабатывается гибридным алгорит-мом версии 2. На выходе получается 3 массива:1. Массив флагов. В этом массиве избыточность данных минимальна, поэтомуфлаги записываются в выходной поток без дополнительного сжатия.Гибридныйалгоритмверсии 2Массив сдвигов иколичествМассив флаговПиксели оста точногоизображенияАлгоритмХаффманаПредобработка(вычислениеразностей)LZOДанные послепредобработкиРезультирующие данныеСжатыеданныеСжатые данныеИсходные данныеРис. 1. Схема комбинированного алгоритма, разработанного для сжатияключевых кадров экранного видео2. Массив байтов сдвигов и количеств. В этом массиве также содержатся раз-личные служебные данные (кроме флагов), используемые гибридным алгорит-мом. Все данные, попадающие в этот массив, имеют однобайтовую природу. Дан-ные в этом массиве имеют большую избыточность, по сравнению с массивомфлагов. Действительно, для кадра экранного видео оказывается, что различныезначения таких параметров, как количество подряд идущих пикселей одного цве-та, а также расстояние до ближайшего встреченного пикселя такого же цвета, неявляются равновероятными. То есть такие данные имеют статистическую избы-точность. Поэтому для дополнительного сжатия этих данных можно использоватьодин из статистических методов сжатия. Было принято решение использовать ал-горитм Хаффмана, так как кодирование метода Хаффмана работает достаточнобыстро для осуществления сжатия в режиме реального времени.3. Массив пикселей. Будем называть этот массив остаточным изображением.Это те пиксели исходного изображения, которые не были заменены в ходе коди-рования гибридным алгоритмом некоторыми служебными данными. Как правило,статистическая избыточность в этом массиве невысока (например, алгоритмХаффмана обычно способен сжать остаточное изображение всего на 1 - 3 %). За-то в этих данных присутствует некоторая пространственная избыточность. Частов остаточном изображении можно увидеть группы подряд идущих пикселей повертикали или горизонтали близких цветов. Такой тип пространственной избы-точности характерен для остаточного изображения, так как гибридный алгоритмне может его устранить.Было принято решение провести следующую предобработку: новое значениедля каждой компоненты пикселя, начиная со второго, вычисляется как разность ссоответствующей компонентой предыдущего пикселя:с_coded[i] = (с[i] - c[i−1]) % 256; (язык Си++).После этой предобработки вместо различных последовательностей пикселейблизкого цвета появляются значения, близкие к нулю. И только первый пиксель вгруппе пикселей близкого цвета после такой предобработки получает значение,далёкое от нуля.Затем применяется алгоритм LZO, который обеспечивает дополнительноесжатие при минимальных временных затратах. Было принято решение использо-вать алгоритм LZO_X_999 с уровнем сжатия 6 как обеспечивающий максималь-ное сжатие при допустимых затратах времени. Как будет показано в разд. 3 «Ре-зультаты тестирования» степень сжатия предложенной схемы сжатия не ниже, адля некоторых типов изображений значительно выше, чем у LZO_X_999 с уров-нем сжатия 6.2. Гибридный алгоритм второй версииГибридный алгоритм является органическим соединением двух алгоритмов:RLE и сдвигового. Рассмотрим вначале каждый из этих алгоритмов в отдель-ности.2.1. R L EВ качестве составной части гибридного алгоритма используется специальноразработанная реализация RLE, адаптированная для сжатия экранного видео. Ка-нонический алгоритм RLE способен выявлять только горизонтальную или верти-кальную избыточность (в зависимости от способа обхода пикселей изображения)[6, с. 289]. В состав гибридного алгоритма входит реализация RLE, способная вы-являть как горизонтальную, так и вертикальную избыточность.Вспомогательные структуры данных. При кодировании и декодировании ис-пользуется массив флагов, где один флаг соответствует одному пикселю исходно-го изображения. Если этот флаг равен 0, соответствующий ему пиксель ещё небыл закодирован, иначе - данный пиксель уже закодирован. Уже закодированныепиксели пропускаются при кодировании.На каждом шаге алгоритма происходит подсчёт количества подряд идущиходинаковых пикселей в трёх направлениях: вправо от текущего пикселя, вниз оттекущего пикселя, а также в прямоугольнике, левым верхним углом которого яв-ляется текущий пиксель. Затем для кодирования выбирается то направление, в ко-тором было найдено максимальное количество одинаковых пикселей. Для боль-шинства типов изображений, например для непрерывно-тоновых, не имеет смыс-ла вводить такое направление поиска, как прямоугольник с текущим пикселем вкачестве левого верхнего угла. Но в случае кадров экранного видео использованиетакой области поиска оправдано, так как часто встречаются именно прямоуголь-ные области одного цвета.Обход пикселей изображения выполняется построчно сверху вниз, но если наданном шаге выбрана вертикальная либо прямоугольная группа пикселей, то ус-танавливаются соответствующие флаги в массиве флагов, после этого происходитвозврат на исходную строку. При этом возможна следующая ситуация: пиксельp[i] уже был закодирован ранее, попав в вертикальную или прямоугольную груп-пу пикселей одинакового цвета. Пусть текущий пиксель - это p[i−1]. Допустимтакже, что пиксель p[i+1] имеет такой же цвет, как p[i−1]. В этом случае p[i−1] иp[i+1] могут быть закодированы, как горизонтальная группа пикселей.Рассмотрим способ выбора флагов, записываемых в выходной массив:1. В случае одиночного пикселя в массив флагов записывается один бит, рав-ный 0.2. В случае выбора прямоугольной области в массив флагов записывается по-следовательность битов 11.3. В случае выбора горизонтальной области в массив флагов записывается по-следовательность битов 100.4. В случае выбора вертикальной области в массив флагов записывается по-следовательность битов 101.Самый короткий однобитовый флаг соответствует одиночному пикселю, таккак тестирование показало, что при кодировании кадров экранного видео частота,с которой встречается одиночный пиксель, значительно превышает сумму частотвсех остальных случаев. Частота, с которой встречается прямоугольная область,оказалась несколько выше частот встречаемости горизонтальной и вертикальнойобластей, поэтому для прямоугольной области была выбрана более короткая по-следовательность флагов.Используется следующий формат закодированных данных.В первом случае: .Во втором случае: .В третьем и четвёртом случаях: .При этом под количество пикселей отводится 2 байта во втором случае; 1 байтв третьем и четвёртом случаях.Коэффициент сжатия в наихудшем случае: 25 / 24.Коэффициент сжатия в наилучшем случае: 42 / (256 · 256 · 24).Преимущества:1. У такой реализации RLE повышена способность выявлять пространствен-ную избыточность по сравнению с канонической реализацией.Но при этом сохраняется главный недостаток канонического алгоритма RLEпри сжатии экранного видео:1. Если при построчном обходе пикселей изображения часто чередуются цве-та, причём даже в том случае, когда набор цветов ограничен (например, текст),эффективность сжатия резко падает.2.2. С д в и г о в ы й а л г о р и т мИдея алгоритма: если при построчном обходе пикселей изображения неза-долго до текущего пикселя встречался пиксель такого же цвета, то 3 байта, коди-рующие цвет пикселя, можно заменить на 1-байтовую ссылку на пиксель с такимже цветом, а точнее - указать, на сколько пикселей нужно сдвинуться назад отно-сительно текущего пикселя остаточного изображения, чтобы получить нужныйцвет. Таким образом, может быть выстроено множество списков. Обход пикселейизображения выполняется построчно сверху вниз.Вспомогательные структуры данных. Для ускорения работы алгоритма, какпри кодировании, так и при декодировании используется хэш-таблица. При коди-ровании ключом хэш-таблицы является цвет, а значением - номер пикселя в оста-точном изображении последнего просмотренного пикселя с таким цветом. Придекодировании ключом хэш-таблицы является номер последнего просмотренногопикселя с таким цветом в остаточном изображении, а значением - цвет.В случае, когда цвет встретился впервые или количество пикселей в оста-точном изображении до предыдущего пикселя с таким же цветомчасть которого занимает текст (эти цифры получены опытным путём). За счётприменения идей сдвигового алгоритма также устранён недостаток алгоритмаRLE - в случае частого чередования цветов при построчном обходе пикселей изо-бражения в условиях ограниченного количества этих цветов степень сжатия зна-чительно выше, чем при сжатии RLE [4].Стоит отметить, что гибридный алгоритм плохо поддаётся распараллелива-нию, так как в случае независимой обработки различных частей исходного изо-бражения разными потоками будет утеряна информация о связях между этимичастями, вследствие чего степень сжатия снизится.3. Результаты тестированияБыли протестированы следующие алгоритмы: LZO_X_1, LZO_X_999 с уров-нем сжатия 1, 4, 6, 9; гибридный алгоритм второй версии, представленный комби-нированный алгоритм, использующий LZO_X_999 с уровнем сжатия 6. Также втестировании принимала участие реализация алгоритма, соответствующего стан-дарту Deflate [6, с. 95], от Microsoft. Соответствующий класс реализован в .NETframework 2.0. Для алгоритмов семейства LZO приведены также время финально-го сжатия алгоритмом Хаффмана, а также размер закодированного изображенияпосле финального сжатия.При тестировании каждое изображение имело разрешение 1024.768 и глубинуцвета в 32 бита. Таким образом, размер исходного изображения составляет1024·768·4 байтов. Тестирование проводилось на платформе со следующими ха-рактеристиками: процессор Intel Core 2 Duo E6750 2,66 ГГц; оперативная памятьDDR2 2Гб; операционная система Windows XP. На момент написания данной ра-боты тестовая платформа находится в среднем сегменте по производительности.Замечание 1: для гибридного алгоритма второй версии данные о размере сжа-тых данных и времени сжатия приведены с учётом финальной обработки методомХаффмана, так как гибридный алгоритм был изначально спроектирован для ис-пользования совместно с методом Хаффмана.Для тестирования использовались скриншоты трёх типов:1. Изображения, типичные для Windows XP (10 штук);2. Изображения, значительную часть которых занимает текст (8 штук);3. Изображения, содержащие графики, диаграммы (10 штук);Эти скриншоты доступны по ссылке [7]. Рис. 2 - 4 представляют собойуменьшенные копии некоторых тестовых изображений, сохранённые в градацияхсерого цвета.По результатам тестирования, представленным в табл. 1 - 3, видно, что фи-нальное сжатие методом Хаффмана позволяет значительно увеличить коэффици-ент сжатия алгоритмов семейства LZO при сравнительно небольших затратахвремени (порядка 7 - 10 мс на кодирование и столько же на декодирование).Алгоритм, соответствующий стандарту Deflate и LZO_X_1, продемонстрировалнаихудшие результаты на большинстве тестов. Из серии алгоритмов LZO наи-больший коэффициент сжатия имеет LZO_X_999 с уровнем сжатия 9. Но этот ал-горитм выполняется слишком долго для его запуска в режиме реального временина значительной части компьютеров, используемых пользователями. При тести-ровании было установлено, что из алгоритмов серии LZO максимальная степеньсжатия, при условии возможности запуска алгоритма в режиме реального временина подавляющей части компьютеров, используемых пользователями, достигаетсяпри использовании LZO_X_999 с уровнем сжатия 6.Рис. 2. Уменьшенная копия изображения WinXP_0.bmpРис. 3. Уменьшенная копия изображения text_4.bmpРис. 4. Уменьшенная копия изображения diagram_0.bmpСам по себе гибридный алгоритм демонстрирует меньшую степень сжатия посравнению со схемой сжатия на его основе. Рассмотрим более подробно результа-ты тестирования комбинированного алгоритма, использующего LZO_X_999 суровнем сжатия 6, и LZO_X_999 с уровнем сжатия 9 (с использованием финаль-ного сжатия методом Хаффмана).Т а б л и ц а 1Усреднённые данные о сжатии изображений, типичных для Windows XPАлгоритм / ПараметрВремякодирования /декодирования(мс)Размерпосле основногосжатияРазмерпосле сжатияалгоритмомХаффмана1. LZO_X_999, уровень 1 56 / 11 147886,6 1244052. LZO_X_999, уровень 4 56, 6 / 10 129921,8 112427,43. LZO_X_999, уровень 6 67,7 / 9 120198,5 106388,64. LZO_X_999, уровень 9 370,6 / 8,8 113822,4 101859,95. LZO_X_1 11,2 / 11,7 159182,3 1421596. Гибридный алгоритм v. 2 54,2 / 33,5 1173887. Комбинированный алгоритм, ис-пользующий LZO_X_999, уровень 6 58,1 / 24,6 91029,18. Комбинированный алгоритм, ис-пользующий LZO_X_999, уровень 9 64,1 / 23,1 906799. Deflate 48,6 / 12 157206,5Т а б л и ц а 2Усреднённые данные о сжатии изображений,значительную часть которых занимает текстАлгоритм / ПараметрВремя кодирова-ния / декодирова-ния (мс)Размер послеосновногосжатияРазмер послесжатия алгорит-мом Хаффмана1. LZO_X_999, уровень 1 56,1 / 10,9 164025,4 118184,12. LZO_X_999, уровень 4 57,4 / 9,6 133731,6 102429,13. LZO_X_999, уровень 6 72,6 / 8,5 110345,4 91106,84. LZO_X_999, уровень 9 880 / 7,8 94430,6 81288,45. LZO_X_1 11,8 / 11 176658,4 138447,36. Гибридный алгоритм V. 2 62,4 / 33 98180,37. Комбинированный алгоритм, ис-пользующий LZO_X_999, уровень 6 62,5 / 26,7 89682,68. Комбинированный алгоритм, ис-пользующий LZO_X_999, уровень 9 65 / 26,8 895789. Deflate 50,6 / 10,9 126848,4Т а б л и ц а 3Усреднённые данные о сжатии изображений,содержащих графики и диаграммыАлгоритм / ПараметрВремя кодирова-ния / декодирова-ния (мс)Размер послеосновногосжатияРазмер послесжатия алгорит-мом Хаффмана1. LZO_X_999, уровень 1 53,9 / 9,1 124239,5 106542,42. LZO_X_999, уровень 4 55,4 / 8,7 113404,2 98963,63. LZO_X_999, уровень 6 65,4 / 8,6 107833,9 95126,44. LZO_X_999, уровень 9 293,5 / 7,6 103002,1 91764,15. LZO_X_1 10,1 / 10,3 136494,8 124248,76. Гибридный алгоритм V. 2 60,2 / 32 112324,17. Комбинированный алгоритм, ис-пользующий LZO_X_999, уровень 6 62,5 / 27,6 94742,18. Комбинированный алгоритм, ис-пользующий LZO_X_999, уровень 9 68,2 / 26,6 94522,59. Deflate 47,1 / 10,9 145175,6По данным, представленным в табл. 4, видно, что комбинированный алгоритмимеет превосходство по степени сжатия на всех изображениях, типичных дляWindows XP (в среднем на 17 %). На изображениях, значительную часть которыхзанимает текст, оба алгоритма демонстрируют близкие результаты (в среднемразличие около 1,5 %), что подтверждается критерием знаков и критерием Вил-коксона [8]. Так, количество типичных и нетипичных сдвигов равны. А суммырангов в соответствии с критерием Вилкоксона в типичном и нетипичном направ-лении равны соответственно 30 и 25 (очень близки). На изображениях, содержа-щих графики и диаграммы, оба алгоритма также демонстрируют близкие резуль-таты (в среднем различие менее чем на 1 %). Количество сдвигов в типичном на-правлениях 4,5, в нетипичном направлении - 3,5. Сумма рангов в соответствиис критерием Вилкоксона в типичном направлении равна 22, в нетипичном случае- 14.Т а б л и ц а 4Данные о размере закодированного файла (в байтах) для 28 тестовых изображенийНазваниеисходногофайлаКомбини-рованныйалгоритмLZO_X_999уровень 6НазваниеисходногофайлаКомбини-рованныйалгоритмLZO_X_999уровень 9WinXP_0.bmp 113975 128252 diagram_0.bmp 94224 94236WinXP_1.bmp 82631 96198 diagram_1.bmp 103741 101878WinXP_2.bmp 52561 60342 diagram_2.bmp 106732 98256WinXP_3.bmp 74150 81067 diagram_3.bmp 87839 91097WinXP_4.bmp 156418 180901 diagram_4.bmp 106887 106721WinXP_5.bmp 109818 136935 diagram_5.bmp 90874 87176WinXP_6.bmp 75795 94816 diagram_6.bmp 153883 159781WinXP_7.bmp 78706 84810 diagram_7.bmp 79009 77775WinXP_8.bmp 76326 93963 diagram_8.bmp 66592 70697WinXP_9.bmp 89911 106602 diagram_9.bmp 57640 63647text_0.bmp 102958 101112 text_4.bmp 84089 79868text_1.bmp 106795 109794 text_5.bmp 85699 96272text_2.bmp 63057 69093 text_6.bmp 91144 88090text_3.bmp 98198 98203 text_7.bmp 85521 86422Замечание: для критерия знаков и критерия Вилкоксона в качестве типичногонаправления сдвига был выбран случай, когда степень сжатия комбинированногоалгоритма выше.ЗаключениеПредставленный в данной работе комбинированный алгоритм, основанный нагибридном алгоритме и LZO, подтвердил свою эффективность при тестировании.Такой комбинированный алгоритм позволяет увеличить степень сжатия изобра-жений, типичных для Windows XP, в среднем на 17 % по сравнению с лучшимипо степени сжатия представителями семейства алгоритмов LZO, способнымисжимать экранное видео в режиме реального времени на широком спектре ком-пьютеров пользователей (LZO_X_999 с уровнем сжатия 6). При этом комбиниро-ванный алгоритм и LZO_X_999 с уровнем сжатия 6 обеспечивают близкие степе-ни сжатия изображений, содержащих текст, диаграммы или графики. Поэтомупредставленный комбинированный алгоритм может быть использован на практи-ке для сжатия кадров экранного видео.На данный момент комбинированный алгоритм встроен в кодек для обработкиэкранного видео Butterfly Screen Video Codec, ориентированный на минимизациюиспользования процессорного времени при сохранении высокой степени сжатия.Представленный комбинированный алгоритм используется не только при сжатииключевых кадров, но и при сжатии изменившихся частей промежуточных кадров.Поэтому разработка представленного в данной работе комбинированного алго-ритм является очередным шагом в оптимизации по уровню использования сис-темных ресурсов и степени сжатия кодека Butterfly Screen Video Codec.

Скачать электронную версию публикации