Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,222

TRENDS AND PROGRESS EVALUATION OF IMAGES AND VIDEO COMPRESSION FOR NETWORKS

Vostrikov A.A. 1
1 ITMO University
В работе проанализирован процесс развития алгоритмов сжатия статических изображений и видеоинформации, стандартизированных и не стандартизированных форматов их хранения и передачи; оценены основные факторы, влияющие на дальнейшее развитие подходов к устранению избыточности передаваемой и хранимой визуальной информации. В этом ряду упомянуты технологии сжатия, ставшие стандартами за последние годы. Например, H.265 и WebP. Затронуты новые подходы к сжатию изображений на основе недавно открытых матричных базисов варьируемой размерности – так называемых М-матрицах: матрицах Адамара‒Эйлера, Адамара‒Ферма, Адамара‒Мерсенна. С учетом стремительного распространения мобильных персональных средств коммуникации предлагается оценить возможности способа сокращения объема передаваемой визуальной информации, основанного не на устранении информационной избыточности внутри потока с неизменными параметрами изображений, а на адаптации свойств контента к характеристикам воспроизводящего устройства.
The development of algorithms for static images and video compression and both standardized and non-standardized layouts for storage and transmission have been analyzed in the paper. There are main factors evaluated, which have influence upon further development of approaches to redundancy elimination from digital visual information, transmitted or stored. Amongst those approaches the new technologies, that became standards in recent years, are mentioned. For example H.265 and WebP. New approaches to images compression based on just discovered matrix basis of variable dimensions, so called M-matrices, like Hadamard-Euler, Hadamard-Fermat, Hadamard-Mersenne matrices. With taking into account rapid spreading of personal mobile communication means, it is offered to evaluate perspectives of visual information volume decreasing method, based not on redundancy elimination in a stream with fixed image parameters, but on content properties adaptation to characteristics of consuming appliance.
images compression
video compression
discrete-cosine transformation
wavelet transformation
orthogonal transformation
orthogonal basis
metadata
1. Balonin N.A., Mironovskii L.A. Matritsy Adamara nechetnogo poryadka // Informatsionno-upravlyayushchie sistemy. 2006. no. 3. pp. 46–50.
2. Balonin N.A., Sergeev M.B., Mironovskii L.A. Vychislenie matrits Adamara-Mersenna // Informatsionno-upravlyayushchie sistemy. 2012. no. 5. pp. 92–94.
3. Balonin N.A., Sergeev M.B., Mironovskii L.A. Vychislenie matrits Adamara-Ferma // Informatsionno-upravlyayushchie sistemy. 2012. no. 6. pp. 90–93.
4. Balonin N.A., Sergeev M.B. O dvukh sposobakh postroeniya matrits Adamara-Eilera // Informatsionno-upravlyayushchie sistemy. 2013. no. 1. pp. 7–10.
5. Balonin Yu.N., Vostrikov A.A., Sergeev M.B. O prikladnykh aspektakh primeneniya M-matrits // Informatsionno-upravlyayushchie sistemy. 2012. no. 1 (56). pp. 92–93.
6. Balonin Yu.N., Sergeev M.B. M-matritsa 22-go poryadka // Informatsionno-upravlyayushchie sistemy. 2011. no. 5 (54). pp. 87–90.
7. Semenov Yu.A. Standart MPEG-7 URL: http://book.itep.ru/2/25/mpeg_7.htm (data obrashcheniya: 20.11.2012).
8. Funktsiya_Uolsha // Vikipediya. URL: http://ru.wikipedia.org/wiki/Funktsiya_Uolsha (data obrashcheniya: 20.11.2012).
9. Cherkashin P. Budushchee interneta: nuzhen «umnyi» vizual’nyi poisk // CNew/analitaika URL: http://www.cnews.ru/reviews/index.shtml?2012/11/14/509824 (data obrashcheniya: 20.11.2012).
10. A new image format for the Web. URL: https://developers.google.com/speed/webp/ (data obrashcheniya: 20.11.2012).
11. Podilchuk C.I., Jayant N.S., and Farvardin N. Three-dimensional subband coding of video, IEEE Transactions on Image Processing, vol. 4, no. 2, pp. 125–139, February 1995.
12. Taubman D. and Zakhor A. Multirate 3-D subband coding of video,” IEEE Transactions on Image Processing, vol. 3, no. 5, pp. 572–588, September 1994.
13. Wajcer D., Stanhill D., and Zeevi Y. Representation and coding of images with nonseparable two-dimensional wavelet, Proceedings of the IEEE International Conference on Image Processing, Chicago, USA, October 1998.
14. H.264 and VP8 for still image coding: WebP? // Diary Of An x264 Developer URL: http://x264dev.multimedia.cx/archives/541 (data obrashcheniya: 20.11.2012).
15. H.265 // Vikipediya. – URL: http://ru.wikipedia.org/wiki/H.265 (data obrashcheniya: 20.11.2012).
16. Harashima H., Aizawa K., and Saito T. Modelbased analysis synthesis coding of videotelephone images – conception and basic study of intelligent image coding, Transactions IEICE, 1989, vol. E72, no. 5, pp. 452–458.
17. Pong K.K. and Kan T.K. Optimum loop filter in hybrid coders IEEE Transactions on Circuits and Systems in Video Technology, 1997, vol. 4, no.2, pp. 158–167.
18. Shen K. and Delp E.J. Wavelet based rate scalable video compression, IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, no. 1, February 1999, pp. 109–122.
19. Saenz M., Salama P., Shen K. and Delp E.J. An evaluation of color embedded wavelet image compression techniques, Proceedings of the SPIE/IS&T Conference on Visual Communications and Image Processing (VCIP), January 23–29, 1999, San Jose, California, pp. 282–293.
20. Jayant,N.S. Johnston J.D. and Safranek R.J. Signal compression based on models of human perception, Proceedings of the IEEE, vol. 81, no. 10, October 1993, pp. 1385–1422.
21. Llados-Bernaus R., Robertson M.A. and Stevenson R.L. A stochastic technique for the removal of artifacts in compressed images and video, in Recovery Techniques for Image and Video Compression and Transmission, Kluwer, 1998.
22. O’Rourke T. and Stevenson R.L. Improved image decompression for reduced transform coding artifacts, IEEE Transactions on Circuits and Systems for Video Technology, vol. 5, no. 6, pp. 490–499, December 1995.
23. WebP, a new image format for the Web // The Chcomius Blog URL: http://blog.chromium.org/2010/09/webp-new-image-format-for-web.html (data obrashcheniya: 20.11.2012).

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

Основными стимулами для этого являются следующие факторы:

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

Последний стимул привёл к появлению сервисов планетарного масштаба, позволяющих людям мгновенно обмениваться изображениями и видео или предоставлять собственные визуальные материалы на всеобщее обозрение на длительное время. Не последнюю роль в этом играют, конечно, так называемые «социальные сети», которые также стремятся дать пользователям все необходимые возможности для применения визуальной информации наряду с текстом. Например, количество размещаемых новых изображений в сети Facebook удваивается каждые два года [9].

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

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

Стандарты и не стандартизованные решения в сжатии цифровой визуальной информации

Сжатие изображений. Десятки лет дискретное косинусное преобразование (ДКП) было основой алгоритмов сжатия изображений. Наиболее популярным из них стал алгоритм, закрепленный стандартом, группой .jpg» и получивший название.jpg. Основные недостатки подобных алгоритмов известны как специалистам, так и рядовым пользователям. В частности, артефакты сетчатого характера при значительных коэффициентах сжатия и размытие контрастных границ.

Позже с развитием производительности вычислительных систем и благодаря определенным достижениям в теории так называемых «вейвлет-базисов» на смену ДКП (или, точнее сказать, в дополнение к ДКП) пришло дискретное вейвлет-преобразование (ДВП). Группа.jpg и в этом случае отметилась созданием стандарта на основе ДВП со значительной функциональностью. Стандарт появился в конце 2000-го года и получил название.jpg2000. В результате различных тестов отмечено увеличение качества сжатых и затем восстановленных изображений по сравнению с.jpg при одинаковых коэффициентах сжатия ориентировочно на 20 %. Особенно очевидное различие отмечается при больших коэффициентах, поскольку.jpg2000 не вносит искажения в восстановленные изображения, приводящие к появлению «блоков».

Следует также отметить, что ДВП в различных вариациях применялось и в не стандартизованном виде, в том числе в виде аппаратных кодеков, выполняющих обработку в реальном времени, например, в виде интегральных схем ADV601/ADV611 корпорации «Analog Devices». Они также показывали очень неплохие результаты, однако со временем всё же были вытеснены.jpg2000. В том числе компания «Analog Devices» в очень скором времени после опубликования стандарта.jpg2000 начинает выпускать популярный по сегодняшний день аппаратный однокристальный.jpg2000-кодек ADV202/ADV212.

Следует отметить, что в составе стандарта, применяемого для сжатия видео – MPEG4, есть режим VTC (Visual Texture Coding – кодирование визуальных текстур), также позволяющий сжимать «неподвижные изображения» с использованием ДВП. Однако по сравнению с.jpg2000 он очень беден в плане функциональности.

Некоторой экзотикой в ряду применяемых базисов для преобразования изображений с целью сжатия можно назвать систему функций Уолша и соответственно так называемое преобразование Уолша‒Адамара [8]. В частности, разработанный компанией «Google Inc.» формат WebP [23] наряду с ДКП использует и базис функций Уолша. WebP рассматривается сообществом в качестве прогрессивной замены формату.jpg, однако на момент написания статьи распространение и известность WebP не стали сколь-нибудь значимыми. Более того, ряд авторов высказывает свой скепсис по поводу преимуществ нового алгоритма [14].

Тем не менее нельзя не отметить наличие дополнительных механизмов, введенных в WebP для увеличения коэффициента сжатия. Среди них наличие нескольких режимов предсказания, позволяющих в ряде случаев передавать не отдельные сжатые блоки (участки) изображений, а только разницу (ошибку предсказания) между соседними блоками. В совокупности все примененные подходы по утверждению разработчиков при «сжатии без потерь» увеличивают эффективность сжатия в WebP относительно PNG на 26 %, а для режима «сжатия с потерями» – относительно.jpg – на 25–34 %. Оценка эквивалентности качества при этом основана на метрике SSIM [10].

Собственно алгоритмы, основанные на ДКП и ДВП, в совокупности с механизмами предсказания содержимого соседствующих пространственных областей или без них призваны устранить избыточность в передаваемой/хранимой информации. В данном случае речь идёт не о чисто информационной избыточности – в этом случае более чем 2–3-кратного сжатия не достичь, а избыточности в смысле восприятия зрительной системой человека. Например, известно, что мелкие детали зрительных образов (пространственно высокочастотные) гораздо менее важны для качества восприятия изображения, чем крупные (пространственно низкочастотные). Поэтому высокочастотные составляющие изображения можно с нужной степенью «грубости» устранить из изображения, внося информационные потери, но не сильно ухудшая качество восприятия. Причём в составляющих цветности такие искажения заметны существенно меньше, чем в яркостной составляющей, и этот факт также используется.

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

Сжатие видео. Воспроизводимое видео представляется в виде последовательно сменяющих друг друга изображений с заданной частотой. Поэтому алгоритмы сжатия изображений вполне применимы и для отдельных видеокадров, о чём свидетельствует существование форматов хранения видеофайлов «Motion.jpg» (видеокадры сжимаются как отдельные изображения алгоритмом.jpg) и «Motion.jpg2000» (видеокадры сжимаются алгоритмом.jpg2000). Однако для видео они всё же не так эффективны, как алгоритмы, эксплуатирующие идею межкадровой (временной) избыточности, когда сжатию подвергается разница между соседними кадрами, а не видеокадр в целом. Очевидно, что в этом случае удаётся достичь гораздо более высоких коэффициентов сжатия, т.к. разница между видеокадрами в общем случае очень мала из-за незначительного временного интервала.

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

В дополнение к сокращению межкадровой избыточности активно используются различные механизмы предсказания изменений в видеопоследовательности и дополнительного уменьшения необходимости сжимать и сохранять всю извлекаемую информацию. Наиболее известные на сегодняшний день алгоритмы сжатия видео, которые в той или иной степени утилизируют упомянутые выше идеи – H.261, H.263, H.264 и алгоритмы группы MPEG: MPEG1, MPEG2, MPEG4. Важно отметить, что для всех этих алгоритмов многократно продемонстрирована целесообразность и достаточность применения ДКП (а не ДВП) для устранения пространственной избыточности.

В 2013 году появился новый стандарт сжатия видеоизображений H.265 [15]. Разработчики с его помощью надеются ориентировочно на вдвое сократить пропускную способность каналов, необходимую для передачи, по сравнению с лучшими из существующих кодеков. При разработке стандарта были сформулированы следующие требования:

  • поддержка сжатия без информационных потерь и сжатия без видимых искажений;
  • поддержка форматов кадра от QVGA (320×240) до 4К и 8K (UHDTV);
  • поддержка цветовой дискретизации до 4:4:4, широкого цветового охвата и альфа-канала, повышенной глубины цвета;
  • поддержка постоянной и переменной частоты кадров (до 60 кадров в секунду и выше).

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

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

Возможности улучшения характеристик алгоритмов сжатия. В последние 10–15 лет попытки усовершенствовать существующие алгоритмы сжатия изображений выразились в значительном числе опубликованных научных работ и защищенных диссертаций. В целом однако обобщение заявляемых авторами результатов показывает, что количественная оценка «улучшений» при объективном подходе составляет 10–20 %, реже 30 %, и варьируется в зависимости от типа обрабатываемого изображения (серые или цветные фотографии, черно-белый текст, картографические изображения и т.д.). Например, классической задачей одно время было устранение сетчатых артефактов на изображении, прошедшем прямое и обратное.jpg-преобразование при относительно больших коэффициентах сжатия [17, 22, 21]. Но кроме этого интересные результаты были получены при использовании нелинейной декомпозиции с помощью вейвлет-функций [13], при применении цветовых преобразований для цветных изображений [19] и с использованием модели восприятия изображений системой зрения человека [20].

В плане замены ДКП на ДВП в технологиях сжатия видеоинформации значительная работа была проделана в двух различных направлениях. Первый вариант – это кодирование ошибки предсказания с помощью ДВП [18], второй – так называемая 3D вейвлет-декомпозиция [11, 12]. И хотя данные технологии показали увеличение качества по сравнению с существовавшими подходами при сходных коэффициентах сжатия, тем не менее большинство из них предназначены для обеспечения развития функциональности; например, введения масштабируемости и прогрессивной передачи (сокращение разрешения или размытие части общего изображения).

Однако при концентрации только на поиске возможностей увеличения коэффициентов сжатия игнорируется ряд современных научно-технических достижений. В связи со стремительным развитием мобильных технологий и возрастающей потребности пользователей интернета в видеоинформации помимо собственно поиска прорывной технологии сжатия более актуальными сегодня кажутся разработка и внедрение технологий эффективного масштабирования передаваемых изображений в реальном времени в зависимости от характеристик потребителя (приёмника) информации. Для иллюстрации можно привести пример, когда портативному устройству с относительно низким разрешением дисплея в составе, допустим, Web-страницы, передаются изображения формата «Full HD». Это, очевидно, нецелесообразно, а, значит, состав передаваемого контента становится зависимым от свойств терминала. Таким образом, определяя характеристики приёмника контента, на уровне либо компании, предоставляющей Web-сервер, либо интернет-провайдера, либо даже на уровне маршрутизаторов, можно существенно сократить требуемый информационный трафик.

Тенденции и будущее технологий сжатия цифровой визуальной информации

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

Классификация подходов к кодированию изображений и видео

Поколение

Подход

Технология

0

Прямое кодирование аналогового сигнала

Импульсно-кодовое преобразование (ИКП)

1

Устранение избыточности

ДКП, ДВП, …

2

Структурное кодирование

Сегментация изображения

3

Анализ и синтез

Кодирование на основе моделей

4

Распознавание и восстановление

Кодирование на основе базы знаний

5

Интеллектуальное кодирование

Семантический анализ и кодирование

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

В стандарте MPEG7 сделан ещё один шаг уже на пути к 5-му поколению. В нём специфицируется некоторый стандартный способ описания различных типов аудио-визуальной информации. Элементы, являющиеся описанием аудио-визуального контента, известны также как «метаданные». Как только аудио-визуальный контент описан в терминах метаданных, изображение оказывается подготовленным к процессу кодирования. Следует отметить, что в этом случае то, что будет закодировано, – это не само изображение, а метаданные, его описывающие. Например, в случае с лицом человека достаточно задать массив его атрибутов для синтеза на стороне воспроизведения. Фон, на котором лицо должно быть изображено после восстановления, можно закодировать достаточно грубо или не кодировать вовсе, а на стороне воспроизведения создать любой нейтральный вариант.

Так как описательные характеристики контента должны иметь смысл в контексте приложения, для разных приложений они будут различными. Это подразумевает, что один и тот же контент может быть описан различным образом в зависимости от конкретного приложения. Для визуальной части контента, например, нижним уровнем абстракции будет описание формы, размера, текстуры, цвета, движения (траектории), позиции (например, «где на сцене может размещаться объект») и т.д. А для аудио-контента: ключ, тональность, темп, вариации темпа, положение в звуковом пространстве. Высшим уровнем представления является семантическая информация в виде такого описания: «Это сцена с лающей коричневой собакой слева и голубым мячом, падающим справа, с фоновым звуком проезжающих авто». Допускается существование промежуточных уровней абстракции. Более подробно с MPEG7 можно ознакомиться, например, в [7].

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

Применение новых базисов. В настоящее время активно развивается направление исследований, связанное с недавно открытыми оригинальными ортогональными базисами [1, 6, 2, 3, 4]. Появление минимаксных структурированных малоуровневых ортогональных матриц (матрицы Адамара‒Мерсенна, Адамара‒Эйлера, Адамара‒Ферма), алгоритмическое получение которых возможно для любых порядков, открывают принципиально новые возможности для обратимого преобразования изображений с различными целями [5]. Причём в этом случае применением одного аппарата могут решаться сразу несколько актуальных задач в области обработки изображений, которые ранее, как правило, отделялись друг от друга. Первые эксперименты показывают, что одновременно можно осуществлятьсжатие, защиту от несанкционированного доступа и защиту от преднамеренного искажения.

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

Заключение

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

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

Рецензенты:

Симаков В.В., д.т.н., профессор, генеральный директор ОАО «Конструкторское бюро опытных работ», г. Москва;

Юлдашев З.М., д.т.н., профессор, заведующий кафедрой биотехнических систем Санкт-Петербургского электротехнического университета (ГЭТУ), г. Санкт-Петербург.

Работа поступила в редакцию 01.07.2013.