Файл: Методы кодирования данных (Кодирование и методы кодирования).pdf

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

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

Глава 3. Кодирование видеосюжетов

Одно изображение занимает достаточно большой объём, что уж говорить о видео изображении? Если говорить о сжатии видео, алгоритмы компрессии без потерь неприемлемы.

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

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

3.1. H.262

Видеокодек H.262 входит в группу стандартов цифрового кодирования видео- и аудиосигналов MPEG-2 часть 2. Первоначально этот кодек мог кодировать видео с разрешением 720*480 точек при 30 кадрах в секунду, при дальнейшем усовершенствовании достигалось сжатие разрешения 1920*1080 точек при 30 кадрах в секунду.

Сжатие основано на устранении пространственной и временной избыточностей. Пространственную избыточность можно убрать сжимая кадры с помощью алгоритма компрессии статического изображения. С временной избыточностью посложнее: так как в большинстве случаев последующие кадры не слишком сильно отличаются от предыдущего, то для лучшей компрессии потока хочется передавать только перемещение объектов в кадре, а неизменные области брать из первого карда в последовательности. Для решения обеих этих задач в кодеке вводится понятие группа кадров (group of pictures - GOP), и кадры в группе делятся на три вида: основные I- (intrapictures), предсказанные P- (predicted) и двунаправленные B- (bidirectional) кадры. I-кадры – это входная точна для декодера, они кодируются независимо в соответствии с методом, используемым в стандарте JPEG. P-кадры кодируются на основе предсказания, путем ссылок на блоки предыдущих I- или P-кадров. B-кадры используют ссылки на два кадра, находящихся впереди и позади них. Группа кадров всегда должна начинаться с I-кадра, по нему предсказываются Р- и В-кадры. Количество P- и B- кадров может варьироваться в зависимости от желаемой степени сжатия: чем больше P- и B-кадров, тем больше сжатие, однако если I-кадр будет закодирован ошибочно, либо произойдет потеря информации в I- кадре, то ошибка будет тянуться на всю группу кадров.

Сжатие видеоизображения происходит следующим образом. Последовательность кадров разбивается на макроблоки 16х16 отсчетов как в алгоритме JPEG и разделяются на три типа кадров: I-, P- и B-кадры. I-кадры сжимаются с помощью алгоритма JPEG: в каждом макроблоке 16х16 отсчетов производится переход к цветовой системе YCrCb, компоненты Cr и Cb прореживаются до матриц 8х8 (удаляется каждая вторая строка и каждый второй столбец), производится ДКП матриц и их квантование, в заключении зиг-заг сканирование и сжатие получившейся последовательности отсчетов методом Хаффмана.

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

B-кадры при кодировании ссылаются на два кадра: впереди и позади них. То есть в них передаётся информация о том, как «собрать» кадр из двух окружающих. Благодаря тому, что передаётся не каждый кадр по отдельности, а ссылки на основные кадры. Стандарт MPEG2 хорошо подходит для хранения фильмов, однако из-за структуры группы кадров совершенно не годится для видеомонтажа. Так же возникают проблемы со сжатием видеосюжетов с быстродвижущимися объектами или с часто меняющимися планами. Объект будет размазан, а если I-кадр окажется не на моменте смены плана, то вся информация будет записана в P-кадр, что приведет к увеличению объема файла.

3.2. H.264

Видеокодек входит в группу стандартов MPEG4 часть 10. Эта рекомендация в настоящее время (2016 год) является стандартом сжатия видеоизображения. Используется для записи видео высокой четкости на Blu- ray и HD DVD, является стандартом для онлайн-видеохостингов, таких как сайт Youtube, а так же стандарт в системах цифрового телевещания [10]^[24]. По сравнению с H.262 данный кодек обеспечивает сжатие в два раза больше при неизменном качестве видеоизображения [11]^[25]. Достигается это благодаря существенному усложнению кодека.

В данном кодеке реализовано разбиение кадра не только на макроблоки 16x16, а так же 16x8, 8x16, 8x8, 8x4, 4x8, 4x4, в зависимости от наличия мелких деталей. При этом увеличивается четкость передачи мелких объектов и качество компенсация движения: обеспечивается большая точность представления векторов движения. При этом точность поиска вектора движения составляет 1/4 или 1/8 макроблока, чего не было в кодеке H.262. Изменено внутреннее кодирование I-кадра. Кодирование так же основано на алгоритме JPEG, но с некоторыми дополнениями. Перед операцией ДКП над макроблоком производится его пространственное предсказание (intra-prediction) по уже закодированным соседним макроблокам. Затем яр- костные и цветоразностные отсчеты предсказанного макроблока вычитаются из соответствующих отсчетов кодируемого макроблока, и над матрицей с разностными компонентами производится ДКП. В кодере предусмотрено 9 направлений внутреннего предсказания.

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

Энтропийное кодирование Хаффмана заменено более сложным и ресурсозатратным контекстным адаптивным двоичным арифметическим кодером (Context Adaptive Binary Arithmetic Coder, CABAC).

Каждый новый кодек и каждое нововведение основываются на увеличении мощности компьютеров. Кодек H.264 обязан своим появлением вы- ходу в продажу двухъядерного процессора от компании Intel. Все перечисленные выше улучшения усложняют алгоритм, и увеличивают время сжатия, по сравнению с MPEG-2. Но в настоящее время сложностей с кодированием видео с помощью H.264 не возникает даже на домашнем персональном компьютере. Кодер позволяет обрабатывать видео с разрешением до 4096х2304 точки при скорости 26,7 кадров в секунду.

3.3. H.265/HEVC

H.265/HEVC (High Efficiency Video Coding) – следующий разрабатываемый стандарт сжатия видеосюжетов. Создается в связи с необходимостью увеличить коэффициент сжатия видеопотока и для передачи видео d aормате UHDTV. Заявлено, что данный кодек позволит сжимать информацию в 50% эффективнее, чем H.264.

В данном алгоритме реализована поддержка большого диапазона размера блоков, от 64х64 до 8х8, а для увеличения точности компенсации движения мелких деталей используется блоки 4х4.

На начальном этапе кодирования изображение делится на одинаковые по размеру блоки – элементы кодового дерева (Coding Tree Unit - CTU) – это логический элемент, состоящий из трех блоков (Coding Tree Block - CTB). CTB содержит в себе блок яркостной и цветоразностных компонент. В зависимости от изображения для внутрикадрового или межкадрового предсказаний CTB может делиться на меньшее число отсчетов. Кодек поддерживает 35 направлений внутрикадрового предсказания.

Использование кодека H.265/HEVC даёт выигрыш в снижении битрейта порядка 51-74% в зависимости от характера видео. В настоящее время разработка кодека продолжается, однако уже сейчас существуют свободные библиотеки кодирования видео, основанные на существующих наработках, такие как OpenHEVC FFmpeg, DivX HEVC и др.

Заключение

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

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

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

В исследовательской части произведено сравнение алгоритмов коди- рования на различных сюжетах. Для исследования искажений кодирования алгоритмов с потерей данных были взяты JPEG и JPEG2000 для статических изображений.

Список использованных источников

1. Сэломон Д. Сжатие данных, изображений и звука. М.: Техносфера, 2004. 368 с.
2. Красильников Н.Н. Цифровая обработка 2D- и 3D-изображений: учебное пособие. СПб.: БХВ-Петербург, 2011. 608 с.
3. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Ватолин Д., Ратушняк А., Смирнов М., Юркин В. М.: ДИАЛОГ- МИФИ, 2002. 384 с.
4. Особенности графических форматов. // URL: courses.narod.ru/graphics.html (Дата обращения 14.04.2018)
5. HP Labs LOCO-I/JPEG-LS Home Page // URL: http://www.labs.hp.com/research/info_theory/loco/ (Дата обращения 14.04.2018)
6. Рубаков Г., Суслов А. JPEG, JPEG2000, JPEG-LS. Сжатие изображений с потерями и без // URL: http://rain.ifmo.ru/cat/view.php/theory/data- compression/jpeg-2006 (Дата обращения 13.04.2018)
7. Воробьев В.И., Грибунов В.Г. Теория и практика вейвлет- преобразования. СПб.: ВУС, 1999. 204 с.
8. H.262/MPEG-2 Part 2 // URL: https://en.wikipedia.org/wiki/H.262/MPEG- 2_Part_2 (Дата обращения 13.04.2018)
9. Гьен Д. Семейство форматов MPEG. Часть вторая - MPEG-2 // URL: http://www.3dnews.ru/170047
10. Таналин М. H.264 // URL: http://tanalin.com/articles/h264/
11. Гук И. Особенности сжатия видеоданных по рекомендации H.264 / MPEG 4 Part 10 // URL: http://www.kit-e.ru/articles/dsp/2006_2_20.php
12. История развития форматов видеосжатия // URL: https://habrahabr.ru/company/intel/blog/133198/
13. Орлов В.Г., Пушкарев А.В.; Современные и перспективные технологии телевидения высокой четкости // INTERMATIC. 2014. Ч. 5. М.: МИРЭА, 2014. С. 233-238.
14. CCD Binning // URL: http://www.andor.com/learning-academy/ccd- binning-what-does-binning-mean
15. Xiaodan Jin, Keigo Hirakawa Analysis and processing of pixel binning for color image sensor // URL: http://asp.eurasipjournals.springeropen.com/articles/10.1186/1687-6180-2012- 125
16. Bosoon P., Renfu Lu Hyperspectral Imaging Technology in Food and Agri- culture. New York: Springer, 2015. 403 с.
17. Интерполяция цифрового изображения // URL: http://www.cambridgeincolour.com/ru/tutorials-ru/image-interpolation.htm
18. YUV – Кодированный файл изображения YUV (YUV Encoded Image File) // URL: http://fileext.ru/yuv СанПин 2.2.2/2.4.1340-03 «Гигиенические требования к персональным электронно-вычислительным машинам и организации работы» // URL: http://www.rosteplo.ru/Npb_files/npb_shablon.php?id=707

1. СанПин 2.2.2/2.4.1340-03 «Гигиенические требования к персональным электронно-вычислительным машинам и организации работы» // URL: http://www.rosteplo.ru/Npb_files/npb_shablon.php?id=707 ↑

2. Рубаков Г., Суслов А. JPEG, JPEG2000, JPEG-LS. Сжатие изображений с потерями и без // URL: http://rain.ifmo.ru/cat/view.php/theory/data- compression/jpeg-2006 ↑

3. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Ватолин Д., Ратушняк А., Смирнов М., Юркин В. М.: ДИАЛОГ- МИФИ, 2002. 384 с. ↑

4. HP Labs LOCO-I/JPEG-LS Home Page // URL: http://www.labs.hp.com/research/info_theory/loco/ ↑

5. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Ватолин Д., Ратушняк А., Смирнов М., Юркин В. М.: ДИАЛОГ- МИФИ, 2002. 384 с. ↑

6. Таналин М. H.264 // URL: http://tanalin.com/articles/h264/ ↑

7. Орлов В.Г., Пушкарев А.В.; Современные и перспективные технологии телевидения высокой четкости // INTERMATIC. 2014. Ч. 5. М.: МИРЭА, 2014. С. 233-238. ↑

8. Сэломон Д. Сжатие данных, изображений и звука. М.: Техносфера, 2004. 368 с. ↑

9. Красильников Н.Н. Цифровая обработка 2D- и 3D-изображений: учебное пособие. СПб.: БХВ-Петербург, 2011. 608 с. ↑

10. Красильников Н.Н. Цифровая обработка 2D- и 3D-изображений: учебное пособие. СПб.: БХВ-Петербург, 2011. 608 с. ↑

11. Воробьев В.И., Грибунов В.Г. Теория и практика вейвлет- преобразования. СПб.: ВУС, 1999. 204 с. ↑

12. Красильников Н.Н. Цифровая обработка 2D- и 3D-изображений: учебное пособие. СПб.: БХВ-Петербург, 2011. 608 с. ↑

13. Xiaodan Jin, Keigo Hirakawa Analysis and processing of pixel binning for color image sensor // URL: http://asp.eurasipjournals.springeropen.com/articles/10.1186/1687-6180-2012- 125 ↑

14. СанПин 2.2.2/2.4.1340-03 «Гигиенические требования к персональным электронно-вычислительным машинам и организации работы» // URL: http://www.rosteplo.ru/Npb_files/npb_shablon.php?id=707 ↑

15. Интерполяция цифрового изображения // URL: http://www.cambridgeincolour.com/ru/tutorials-ru/image-interpolation.htm ↑

16. Гук И. Особенности сжатия видеоданных по рекомендации H.264 / MPEG 4 Part 10 // URL: http://www.kit-e.ru/articles/dsp/2006_2_20.php (Дата обращения 20.05.2016) ↑

17. Рубаков Г., Суслов А. JPEG, JPEG2000, JPEG-LS. Сжатие изображений с потерями и без // URL: http://rain.ifmo.ru/cat/view.php/theory/data- compression/jpeg-2006 ↑

18. Гьен Д. Семейство форматов MPEG. Часть вторая - MPEG-2 // URL: http://www.3dnews.ru/170047 ↑

19. H.262/MPEG-2 Part 2 // URL: https://en.wikipedia.org/wiki/H.262/MPEG- 2_Part_2 ↑

20. Bosoon P., Renfu Lu Hyperspectral Imaging Technology in Food and Agri- culture. New York: Springer, 2015. 403 с. ↑

21. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Ватолин Д., Ратушняк А., Смирнов М., Юркин В. М.: ДИАЛОГ- МИФИ, 2002. 384 с. ↑

22. Орлов В.Г., Пушкарев А.В.; Современные и перспективные технологии телевидения высокой четкости // INTERMATIC. 2014. Ч. 5. М.: МИРЭА, 2014. С. 233-238. ↑

23. YUV – Кодированный файл изображения YUV (YUV Encoded Image File) // URL: http://fileext.ru/yuv ↑

24. Таналин М. H.264 // URL: http://tanalin.com/articles/h264/ ↑

25. Гук И. Особенности сжатия видеоданных по рекомендации H.264 / MPEG 4 Part 10 // URL: http://www.kit-e.ru/articles/dsp/2006_2_20.php ↑