В теории информации сжатие данных , кодирование источника [ 1] или уменьшение скорости передачи данных — это процесс кодирования информации с использованием меньшего количества битов , чем исходное представление. [2] Любое конкретное сжатие осуществляется либо с потерями , либо без потерь . Сжатие без потерь уменьшает количество битов за счет выявления и устранения статистической избыточности . Никакая информация не теряется при сжатии без потерь. Сжатие с потерями уменьшает количество битов, удаляя ненужную или менее важную информацию. [3] Обычно устройство, выполняющее сжатие данных, называется кодером, а устройство, выполняющее обращение процесса (декомпрессию), — декодером.
Процесс уменьшения размера файла данных часто называют сжатием данных. В контексте передачи данных это называется исходным кодированием: кодирование выполняется в источнике данных перед их сохранением или передачей. [4] Исходное кодирование не следует путать с канальным кодированием для обнаружения и исправления ошибок или с линейным кодированием — средством отображения данных в сигнал.
Сжатие полезно, поскольку оно уменьшает ресурсы, необходимые для хранения и передачи данных. Вычислительные ресурсы потребляются в процессах сжатия и распаковки. Сжатие данных требует компромисса между пространственно-временной сложностью . Например, схема сжатия видео может потребовать дорогостоящего оборудования для достаточно быстрой распаковки видео, чтобы его можно было просмотреть во время распаковки, а возможность полного распаковывания видео перед его просмотром может быть неудобной или требовать дополнительного хранилища. Разработка схем сжатия данных предполагает компромисс между различными факторами, включая степень сжатия, величину вносимых искажений (при использовании сжатия данных с потерями ) и вычислительные ресурсы, необходимые для сжатия и распаковки данных. [5]
Алгоритмы сжатия данных без потерь обычно используют статистическую избыточность для представления данных без потери какой-либо информации , поэтому процесс является обратимым. Сжатие без потерь возможно, поскольку большинство реальных данных демонстрируют статистическую избыточность. Например, изображение может иметь области цвета, которые не меняются на протяжении нескольких пикселей; вместо кодирования «красный пиксель, красный пиксель...» данные могут быть закодированы как «279 красных пикселей». Это базовый пример кодирования длин серий ; существует множество схем уменьшения размера файла за счет устранения избыточности.
Методы сжатия Лемпеля -Зива (LZ) являются одними из самых популярных алгоритмов хранения без потерь. [6] DEFLATE — это вариант LZ, оптимизированный по скорости декомпрессии и степени сжатия, но сжатие может быть медленным. В середине 1980-х годов, после работы Терри Уэлча , алгоритм Лемпеля-Зива-Уэлча (LZW) быстро стал методом выбора для большинства систем сжатия общего назначения. LZW используется в изображениях GIF , таких программах, как PKZIP , и аппаратных устройствах, таких как модемы. [7] Методы LZ используют модель сжатия на основе таблиц, в которой записи таблицы заменяются повторяющимися строками данных. Для большинства методов LZ эта таблица генерируется динамически на основе более ранних входных данных. Сама таблица часто кодируется Хаффманом . Подобные грамматические коды могут чрезвычайно эффективно сжимать часто повторяющиеся входные данные, например, коллекцию биологических данных об одном и том же или близкородственных видах, огромную коллекцию документов с разными версиями, интернет-архивы и т. д. Основная задача грамматических кодов — построение контекстно-свободная грамматика, производящая одну строку. Другие практические алгоритмы сжатия грамматики включают Sequitur и Re-Pair .
Самые сильные современные компрессоры без потерь используют вероятностные модели, такие как прогнозирование путем частичного сопоставления . Преобразование Берроуза -Уиллера также можно рассматривать как косвенную форму статистического моделирования. [8] В дальнейшем усовершенствовании прямого использования вероятностного моделирования статистические оценки могут быть связаны с алгоритмом, называемым арифметическим кодированием . Арифметическое кодирование — это более современный метод кодирования, который использует математические вычисления конечного автомата для создания строки закодированных битов из серии символов входных данных. Он может обеспечить превосходное сжатие по сравнению с другими методами, такими как более известный алгоритм Хаффмана. Он использует состояние внутренней памяти, чтобы избежать необходимости выполнять взаимно однозначное сопоставление отдельных входных символов с различными представлениями, использующими целое число бит, и очищает внутреннюю память только после кодирования всей строки символов данных. . Арифметическое кодирование особенно хорошо применяется для задач адаптивного сжатия данных, где статистика варьируется и зависит от контекста, поскольку его можно легко объединить с адаптивной моделью распределения вероятностей входных данных. Ранним примером использования арифметического кодирования была дополнительная (но не широко используемая) функция стандарта кодирования изображений JPEG . [9] С тех пор он применялся в различных других конструкциях, включая H.263 , H.264/MPEG-4 AVC и HEVC для кодирования видео. [10]
Программное обеспечение для архивирования обычно имеет возможность регулировать «размер словаря», при этом больший размер требует больше оперативной памяти во время сжатия и распаковки, но сжимает сильнее, особенно при повторяющихся шаблонах в содержимом файлов. [11] [12]
В конце 1980-х годов цифровые изображения стали более распространенными, и появились стандарты сжатия изображений без потерь . В начале 1990-х годов стали широко использоваться методы сжатия с потерями. [13] В этих схемах допускается некоторая потеря информации, поскольку удаление несущественных деталей может сэкономить место для хранения. Существует соответствующий компромисс между сохранением информации и уменьшением размера. Схемы сжатия данных с потерями разработаны на основе исследований того, как люди воспринимают рассматриваемые данные. Например, человеческий глаз более чувствителен к тонким изменениям яркости , чем к изменениям цвета. Сжатие изображений JPEG частично работает за счет округления несущественных битов информации. [14] Ряд популярных форматов сжатия используют эти различия восприятия, в том числе психоакустика для звука и психовизуальная техника для изображений и видео.
Большинство форм сжатия с потерями основаны на кодировании с преобразованием , особенно на дискретном косинусном преобразовании (DCT). Впервые он был предложен в 1972 году Насиром Ахмедом , который затем разработал рабочий алгоритм вместе с Т. Натараджаном и К. Р. Рао в 1973 году, прежде чем представить его в январе 1974 года . [15] [16] DCT является наиболее широко используемым методом сжатия с потерями, и используется в мультимедийных форматах изображений (например, JPEG и HEIF ), [17] видео (например, MPEG , AVC и HEVC) и аудио (например, MP3 , AAC и Vorbis ).
Сжатие изображений с потерями используется в цифровых камерах для увеличения емкости хранилища. Аналогично, DVD , Blu-ray и потоковое видео используют форматы кодирования видео с потерями . Сжатие с потерями широко используется в видео.
При сжатии звука с потерями методы психоакустики используются для удаления неслышимых (или менее слышимых) компонентов аудиосигнала . Сжатие человеческой речи часто выполняется с помощью еще более специализированных методов; Кодирование речи выделяется как отдельная дисциплина от сжатия звука общего назначения. Кодирование речи используется в интернет-телефонии , например, сжатие звука используется для копирования компакт-дисков и декодируется аудиоплеерами. [8]
Сжатие с потерями может привести к потере генерации .
Теоретическая основа сжатия обеспечивается теорией информации и, более конкретно, теоремой Шеннона о кодировании источника ; теории, специфичные для предметной области, включают алгоритмическую теорию информации для сжатия без потерь и теорию скорости-искажения для сжатия с потерями. Эти области исследований были по существу созданы Клодом Шенноном , опубликовавшим фундаментальные статьи по этой теме в конце 1940-х — начале 1950-х годов. Другие темы, связанные со сжатием, включают теорию кодирования и статистический вывод . [18]
Существует тесная связь между машинным обучением и сжатием. Система, которая предсказывает апостериорные вероятности последовательности с учетом всей ее истории, может использоваться для оптимального сжатия данных (путем использования арифметического кодирования выходного распределения). И наоборот, для прогнозирования можно использовать оптимальный компрессор (путем нахождения символа, который сжимает лучше всего, учитывая предыдущую историю). Эта эквивалентность использовалась в качестве оправдания использования сжатия данных в качестве эталона «общего интеллекта». [19] [20] [21]
Альтернативный вид может показать, что алгоритмы сжатия неявно отображают строки в векторы неявного пространства признаков , а меры сходства на основе сжатия вычисляют сходство в этих пространствах признаков. Для каждого компрессора C(.) мы определяем ассоциированное векторное пространство ℵ, такое, что C(.) отображает входную строку x, соответствующую векторной норме ||~x||. Исчерпывающему исследованию пространств признаков, лежащих в основе всех алгоритмов сжатия, препятствует пространство; вместо этого векторы признаков предпочитают исследовать три репрезентативных метода сжатия без потерь: LZW, LZ77 и PPM. [22]
Согласно теории AIXI , которая более подробно объясняется в Hutter Prize , наилучшее возможное сжатие x — это наименьшее возможное программное обеспечение, генерирующее x. Например, в этой модели сжатый размер zip-файла включает в себя как сам zip-файл, так и программное обеспечение для распаковки, поскольку вы не можете разархивировать его без того и другого, но может существовать еще меньшая комбинированная форма.
Примеры программного обеспечения для сжатия аудио/видео на базе искусственного интеллекта включают VP9 , NVIDIA Maxine , AIVC, AccMPEG. [23] Примеры программного обеспечения, которое может выполнять сжатие изображений с помощью искусственного интеллекта, включают OpenCV , TensorFlow , MATLAB ’s Image Processing Toolbox (IPT) и высокоточное генеративное сжатие изображений. [24]
В машинном обучении без учителя кластеризация k-средних может использоваться для сжатия данных путем группировки схожих точек данных в кластеры. Этот метод упрощает обработку обширных наборов данных, в которых отсутствуют предопределенные метки, и находит широкое применение в таких областях, как сжатие изображений . [25]
Сжатие данных можно рассматривать как частный случай различения данных . [26] [27] Различие данных заключается в создании различий с учетом источника и цели, а внесение исправлений воспроизводит цель с учетом источника и разницы. Поскольку при сжатии данных не существует отдельного источника и цели, сжатие данных можно рассматривать как различие данных с пустыми исходными данными, при этом сжатый файл соответствует отличию от ничего. Это то же самое, что рассматривать абсолютную энтропию (соответствующую сжатию данных) как частный случай относительной энтропии (соответствующей различению данных) при отсутствии исходных данных.
Термин «дифференциальное сжатие» используется, чтобы подчеркнуть связь между различиями данных.
Энтропийное кодирование возникло в 1940-х годах с введением кодирования Шеннона-Фано , [28] основы кодирования Хаффмана , которое было разработано в 1950 году . [29] Кодирование с преобразованием началось в конце 1960-х годов, с введением быстрого преобразования Фурье (БПФ). ) кодирование в 1968 году и преобразование Адамара в 1969 году. [30]
Важным методом сжатия изображений является дискретное косинусное преобразование (ДКП), метод, разработанный в начале 1970-х годов. [15] DCT является основой для JPEG, формата сжатия с потерями , который был представлен Объединенной группой экспертов по фотографии (JPEG) в 1992 году. [31] JPEG значительно сокращает объем данных, необходимых для представления изображения, за счет относительного небольшое снижение качества изображения и стал наиболее широко используемым форматом файлов изображений . [32] [33] Его высокоэффективный алгоритм сжатия на основе DCT во многом способствовал широкому распространению цифровых изображений и цифровых фотографий . [34]
Лемпель-Зив-Велч (LZW) — алгоритм сжатия без потерь, разработанный в 1984 году. Он используется в формате GIF , представленном в 1987 году. [35] DEFLATE — алгоритм сжатия без потерь, указанный в 1996 году, используется в портативной сетевой графике ( PNG) формат. [36]
Вейвлет-сжатие , использование вейвлетов для сжатия изображений, началось после разработки кодирования DCT. [37] Стандарт JPEG 2000 был представлен в 2000 году. [38] В отличие от алгоритма DCT, используемого в исходном формате JPEG, JPEG 2000 вместо этого использует алгоритмы дискретного вейвлет-преобразования (DWT). [39] [40] [41] Технология JPEG 2000, включающая расширение Motion JPEG 2000 , была выбрана в качестве стандарта кодирования видео для цифрового кино в 2004 году . [42]
Сжатие аудиоданных, не путать со сжатием динамического диапазона , потенциально может уменьшить полосу пропускания передачи и требования к хранению аудиоданных. Алгоритмы сжатия аудиоформатов реализуются программно в виде аудиокодеков . Как при сжатии с потерями, так и при сжатии без потерь избыточность информации снижается за счет использования таких методов, как кодирование , квантование , DCT и линейное предсказание , чтобы уменьшить объем информации, используемой для представления несжатых данных.
Алгоритмы сжатия звука с потерями обеспечивают более высокое сжатие и используются во многих аудиоприложениях, включая Vorbis и MP3 . Почти все эти алгоритмы основаны на психоакустике для устранения или уменьшения точности менее слышимых звуков, тем самым уменьшая пространство, необходимое для их хранения или передачи. [2] [43]
Приемлемый компромисс между потерей качества звука и размером передачи или хранилища зависит от приложения. Например, один компакт-диск (CD) емкостью 640 МБ содержит примерно один час несжатой музыки высокого качества , менее 2 часов музыки, сжатой без потерь, или 7 часов музыки, сжатой в формате MP3 со средней скоростью передачи данных . Цифровой диктофон обычно может хранить около 200 часов разборчивой речи в 640 МБ. [44]
Сжатие звука без потерь создает представление цифровых данных, которые можно декодировать до точной цифровой копии оригинала. Коэффициенты сжатия составляют около 50–60% от исходного размера, [45] что аналогично стандартному сжатию данных без потерь. Кодеки без потерь используют аппроксимацию кривой или линейное предсказание в качестве основы для оценки сигнала. Параметры, описывающие оценку и разницу между оценкой и фактическим сигналом, кодируются отдельно. [46]
Существует ряд форматов сжатия звука без потерь. См. список кодеков без потерь . Некоторые форматы связаны с отдельной системой, например, Direct Stream Transfer , используемый в Super Audio CD , и Meridian Lossless Packing , используемый в DVD-Audio , Dolby TrueHD , Blu-ray и HD DVD .
Некоторые форматы аудиофайлов сочетают формат с потерями и коррекцию без потерь; это позволяет удалить исправления и легко получить файл с потерями. К таким форматам относятся MPEG-4 SLS (масштабируемый до потерь без потерь), WavPack и OptimFROG DualStream .
Когда аудиофайлы подлежат обработке либо путем дальнейшего сжатия, либо для редактирования , желательно работать с неизмененным оригиналом (несжатым или сжатым без потерь). Обработка сжатого с потерями файла для какой-либо цели обычно дает конечный результат хуже, чем создание того же сжатого файла из несжатого оригинала. Помимо редактирования или микширования звука, сжатие звука без потерь часто используется для архивного хранения или в качестве мастер-копий.
Сжатие звука с потерями используется в широком спектре приложений. Помимо автономных аудиоприложений для воспроизведения файлов в MP3-плеерах или компьютерах, аудиопотоки с цифровым сжатием используются в большинстве видео-DVD, цифровом телевидении, потоковом мультимедиа в Интернете , спутниковом и кабельном радио и все чаще в наземном радиовещании. Сжатие с потерями обычно обеспечивает гораздо большее сжатие, чем сжатие без потерь, за счет отбрасывания менее важных данных на основе психоакустической оптимизации. [47]
Психоакустика признает, что не все данные в аудиопотоке могут быть восприняты слуховой системой человека . Большая часть сжатия с потерями уменьшает избыточность, сначала идентифицируя нерелевантные для восприятия звуки, то есть звуки, которые очень трудно услышать. Типичные примеры включают высокие частоты или звуки, которые возникают одновременно с более громкими звуками. Эти несущественные звуки кодируются с пониженной точностью или вообще не кодируются.
Из-за природы алгоритмов с потерями качество звука страдает от потерь цифрового поколения при распаковке и повторном сжатии файла. Это делает сжатие с потерями непригодным для хранения промежуточных результатов в профессиональных аудиоинженерных приложениях, таких как редактирование звука и многодорожечная запись. Однако форматы с потерями, такие как MP3 , очень популярны среди конечных пользователей, поскольку размер файла уменьшается до 5–20% от исходного размера, а в одном мегабайте можно хранить около минуты музыки с адекватным качеством.
Было разработано несколько собственных алгоритмов сжатия с потерями, которые обеспечивают более высокое качество звука за счет использования комбинации алгоритмов без потерь и с потерями с адаптивной скоростью передачи данных и более низкими коэффициентами сжатия. Примеры включают aptX , LDAC , LHDC , MQA и SCL6.
Чтобы определить, какая информация в аудиосигнале не имеет значения для восприятия, большинство алгоритмов сжатия с потерями используют преобразования, такие как модифицированное дискретное косинусное преобразование (MDCT), для преобразования дискретизированных сигналов во временной области в область преобразования, обычно в частотную область . После преобразования частоты компонентов можно расставить по приоритетам в зависимости от того, насколько они слышны. Слышимость спектральных составляющих оценивается с использованием абсолютного порога слышимости и принципов одновременной маскировки — явления, при котором сигнал маскируется другим сигналом, разделенным по частоте, — и, в некоторых случаях, временной маскировки — когда сигнал маскируется другим сигналом. разделенные временем. Контуры равной громкости также могут использоваться для взвешивания перцептивной важности компонентов. Модели сочетания человеческого уха и мозга, включающие такие эффекты, часто называют психоакустическими моделями . [48]
Другие типы компрессоров с потерями, такие как кодирование с линейным предсказанием (LPC), используемое с речью, представляют собой кодеры на основе источника. LPC использует модель речевого тракта человека для анализа звуков речи и определения параметров, используемых моделью для их воспроизведения в каждый момент. Эти изменяющиеся параметры передаются или сохраняются и используются для управления другой моделью в декодере, воспроизводящей звук.
Форматы с потерями часто используются для распространения потокового аудио или интерактивного общения (например, в сетях сотовой связи). В таких приложениях данные должны распаковываться по ходу потока данных, а не после передачи всего потока данных. Не все аудиокодеки можно использовать для потоковых приложений. [47]
Задержка связана с методами, используемыми для кодирования и декодирования данных. Некоторые кодеки анализируют более длинный сегмент данных, называемый кадром , для оптимизации эффективности, а затем кодируют его таким образом, что для декодирования требуется одновременно больший сегмент данных. Присущая алгоритму кодирования задержка может иметь решающее значение; например, при двусторонней передаче данных, например, при телефонном разговоре, значительные задержки могут серьезно ухудшить воспринимаемое качество.
В отличие от скорости сжатия, которая пропорциональна количеству операций, требуемых алгоритмом, здесь задержка относится к количеству сэмплов, которые необходимо проанализировать перед обработкой блока аудио. В минимальном случае задержка равна нулю (например, если кодер/декодер просто уменьшает количество бит, используемых для квантования сигнала). Алгоритмы временной области, такие как LPC, также часто имеют низкие задержки, отсюда их популярность при кодировании речи для телефонии. Однако в таких алгоритмах, как MP3, для реализации психоакустической модели в частотной области необходимо анализировать большое количество выборок, а задержка составляет порядка 23 мс.
Кодирование речи — важная категория сжатия аудиоданных. Модели восприятия, используемые для оценки того, какие аспекты речи может услышать человеческое ухо, обычно несколько отличаются от моделей, используемых для музыки. Диапазон частот, необходимых для передачи звуков человеческого голоса, обычно намного уже, чем тот, который необходим для музыки, и звук обычно менее сложен. В результате речь может быть закодирована с высоким качеством с использованием относительно низкой скорости передачи данных.
Обычно это достигается за счет комбинации двух подходов:
Самыми ранними алгоритмами, использовавшимися при кодировании речи (и сжатии аудиоданных в целом), были алгоритм A-law и алгоритм μ-law .
Ранние аудиоисследования проводились в Bell Labs . Там в 1950 году Ч. Чапин Катлер подал патент на дифференциальную импульсно-кодовую модуляцию (ДИКМ). [49] В 1973 году адаптивный DPCM (ADPCM) был представлен П. Каммиски, Никилом С. Джаянтом и Джеймсом Л. Фланаганом . [50] [51]
Перцептивное кодирование было впервые использовано для сжатия кодирования речи с помощью кодирования с линейным предсказанием (LPC). [52] Первоначальные концепции LPC восходят к работе Фумитады Итакуры ( Университет Нагои ) и Сюдзо Сайто ( Nippon Telegraph and Telephone ) в 1966 году . [53] В 1970-х годах Бишну С. Атал и Манфред Р. Шредер в Bell Labs разработал форму LPC, называемую адаптивным прогнозирующим кодированием (APC), алгоритм перцептивного кодирования, который использовал маскирующие свойства человеческого уха, а затем в начале 1980-х годов разработал алгоритм линейного прогнозирования с кодовым возбуждением (CELP), который достиг значительной степени сжатия для пора. [52] Перцептивное кодирование используется в современных форматах сжатия звука, таких как MP3 [52] и AAC .
Дискретное косинусное преобразование (DCT), разработанное Насиром Ахмедом , Т. Натараджаном и К. Р. Рао в 1974 году, [16] послужило основой для модифицированного дискретного косинусного преобразования (MDCT), используемого в современных форматах сжатия звука, таких как MP3, [54] Dolby . Цифровой , [55] [56] и AAC. [57] MDCT был предложен Дж. П. Принсеном, А. В. Джонсоном и А. Б. Брэдли в 1987 году, [58] после более ранней работы Принсена и Брэдли в 1986 году. [59]
Первая в мире коммерческая система сжатия звука для автоматизации вещания была разработана Оскаром Бонелло, профессором инженерных наук Университета Буэнос-Айреса . [60] В 1983 году, используя психоакустический принцип маскировки критических полос, впервые опубликованный в 1967 году, [61] он приступил к разработке практического приложения на основе недавно разработанного компьютера IBM PC , а в 1987 году была запущена система автоматизации вещания под название Аудиком . [62] 35 лет спустя почти все радиостанции мира использовали эту технологию, разработанную рядом компаний, поскольку изобретатель отказывается получать патенты на изобретения для своей работы. Он предпочитает объявить его общественным достоянием и опубликовать [63].
Сборник литературы по широкому спектру систем аудиокодирования был опубликован в журнале IEEE по выбранным областям связи ( JSAC ) в феврале 1988 года. аудиокодеры, почти все из которых используют методы восприятия, своего рода частотный анализ и внутреннее бесшумное кодирование. [64]
Несжатое видео требует очень высокой скорости передачи данных . Хотя кодеки сжатия видео без потерь работают с коэффициентом сжатия от 5 до 12, типичное видео со сжатием с потерями H.264 имеет коэффициент сжатия от 20 до 200. [65]
Двумя ключевыми методами сжатия видео, используемыми в стандартах видеокодирования, являются DCT и компенсация движения (MC). Большинство стандартов кодирования видео, таких как форматы H.26x и MPEG , обычно используют видеокодирование DCT с компенсацией движения (блочная компенсация движения). [66] [67]
Большинство видеокодеков используются наряду с методами сжатия звука для хранения отдельных, но дополняющих друг друга потоков данных в виде одного объединенного пакета с использованием так называемых форматов контейнеров . [68]
Видеоданные могут быть представлены как серия кадров неподвижного изображения. Такие данные обычно содержат большое количество пространственной и временной избыточности . Алгоритмы сжатия видео пытаются уменьшить избыточность и хранить информацию более компактно.
Большинство форматов и кодеков сжатия видео используют как пространственную, так и временную избыточность (например, посредством разностного кодирования с компенсацией движения ). Сходства могут кодироваться только путем сохранения различий между, например, соседними во времени кадрами (межкадровое кодирование) или соседними в пространстве пикселями (внутрикадровое кодирование). Межкадровое сжатие (временное дельта-кодирование ) (повторно) использует данные из одного или нескольких более ранних или более поздних кадров в последовательности для описания текущего кадра. С другой стороны, внутрикадровое кодирование использует только данные из текущего кадра, что фактически представляет собой сжатие неподвижного изображения. [48]
Форматы внутрикадрового видеокодирования, используемые в видеокамерах и при редактировании видео, используют более простое сжатие, в котором используется только внутрикадровое предсказание. Это упрощает программное обеспечение для редактирования видео, поскольку предотвращает ситуацию, в которой сжатый кадр ссылается на данные, которые удалил редактор.
Обычно при сжатии видео дополнительно используются методы сжатия с потерями , такие как квантование , которые уменьшают аспекты исходных данных, которые (более или менее) не имеют отношения к зрительному восприятию человека, за счет использования особенностей человеческого зрения. Например, небольшие различия в цвете труднее заметить, чем изменения в яркости. Алгоритмы сжатия могут усреднять цвет в этих похожих областях аналогично тому, как это используется при сжатии изображений JPEG. [9] Как и при любом сжатии с потерями, существует компромисс между качеством видео и скоростью передачи данных , стоимостью обработки сжатия и распаковки, а также системными требованиями. В сильно сжатом видео могут присутствовать видимые или отвлекающие артефакты .
Другие методы, помимо распространенных форматов преобразования на основе DCT, такие как фрактальное сжатие , поиск соответствия и использование дискретного вейвлет-преобразования (DWT), были предметом некоторых исследований, но обычно не используются в практических продуктах. Вейвлет-сжатие используется в кодировщиках неподвижных изображений и видеокодировщиках без компенсации движения. Интерес к фрактальному сжатию, похоже, ослабевает из-за недавнего теоретического анализа, показывающего сравнительную неэффективность таких методов. [48]
При межкадровом кодировании отдельные кадры видеопоследовательности сравниваются от одного кадра к другому, и кодек сжатия видео записывает различия с опорным кадром. Если в кадре есть области, где ничего не изменилось, система может просто выдать короткую команду, которая копирует эту часть предыдущего кадра в следующий. Если части кадра перемещаются простым образом, компрессор может выдать (немного более длинную) команду, которая сообщает декомпрессору сдвинуть, повернуть, осветлить или затемнить копию. Эта более длинная команда по-прежнему остается намного короче, чем данные, генерируемые внутрикадровым сжатием. Обычно кодер также передает остаточный сигнал, который описывает оставшиеся более тонкие различия с эталонным изображением. Используя энтропийное кодирование, эти сигналы остатков имеют более компактное представление, чем полный сигнал. В областях видео с большим количеством движения сжатие должно кодировать больше данных, чтобы успевать за большим количеством изменяющихся пикселей. Обычно во время взрывов, пламени, стад животных и в некоторых панорамных кадрах высокочастотная детализация приводит к снижению качества или увеличению переменного битрейта .
Сегодня [ по состоянию? ] почти все широко используемые методы сжатия видео (например, те, которые указаны в стандартах, одобренных ITU-T или ISO ), имеют одну и ту же базовую архитектуру, восходящую к H.261 , который был стандартизирован ITU-T в 1988 году. В основном они полагаются на DCT, применяемый к прямоугольным блокам соседних пикселей, и временное предсказание с использованием векторов движения , а также на этап внутриконтурной фильтрации.
На этапе прогнозирования применяются различные методы дедупликации и разностного кодирования, которые помогают декоррелировать данные и описывать новые данные на основе уже переданных данных.
Затем прямоугольные блоки оставшихся данных пикселей преобразуются в частотную область. На основном этапе обработки с потерями данные частотной области квантуются, чтобы уменьшить количество информации, не имеющей отношения к зрительному восприятию человека.
На последнем этапе статистическая избыточность в значительной степени устраняется с помощью энтропийного кодера , который часто применяет ту или иную форму арифметического кодирования.
На этапе дополнительной внутриконтурной фильтрации к восстановленному сигналу изображения могут быть применены различные фильтры. Вычисляя эти фильтры также внутри цикла кодирования, они могут помочь в сжатии, поскольку их можно применять к эталонному материалу до того, как он будет использован в процессе прогнозирования, и ими можно управлять, используя исходный сигнал. Самый популярный пример — фильтры деблокировки , которые размывают артефакты блокировки из-за разрывов квантования на границах блоков преобразования.
В 1967 году А. Х. Робинсон и К. Черри предложили схему сжатия полосы пропускания кодирования по длине серии для передачи аналоговых телевизионных сигналов. [69] DCT, который является фундаментальным для современного сжатия видео, [70] был представлен Насиром Ахмедом , Т. Натараджаном и К. Р. Рао в 1974 году. [16] [71]
H.261 , дебютировавший в 1988 году, представил на рынке распространенную базовую архитектуру технологии сжатия видео. [72] Это был первый формат кодирования видео , основанный на сжатии DCT. [70] H.261 был разработан рядом компаний, включая Hitachi , PictureTel , NTT , BT и Toshiba . [73]
Наиболее популярными стандартами кодирования видео , используемыми для кодеков, являются стандарты MPEG . MPEG-1 был разработан Группой экспертов по кинематографии (MPEG) в 1991 году и предназначен для сжатия видео качества VHS . На смену ему в 1994 году пришел MPEG-2 / H.262 , [72] который был разработан рядом компаний, в первую очередь Sony , Thomson и Mitsubishi Electric . [74] MPEG-2 стал стандартным видеоформатом для цифрового телевидения DVD и SD . [72] В 1999 году за ним последовал MPEG-4 / H.263 . [72] Он также был разработан рядом компаний, в первую очередь Mitsubishi Electric, Hitachi и Panasonic . [75]
H.264/MPEG-4 AVC был разработан в 2003 году рядом организаций, в первую очередь Panasonic, Godo Kaisha IP Bridge и LG Electronics . [76] AVC коммерчески представила современные алгоритмы контекстно-адаптивного двоичного арифметического кодирования (CABAC) и контекстно-адаптивного кодирования переменной длины (CAVLC). AVC является основным стандартом кодирования видео для дисков Blu-ray и широко используется веб-сайтами для обмена видео и потоковыми интернет-сервисами, такими как YouTube , Netflix , Vimeo и iTunes Store , веб-программами, такими как Adobe Flash Player и Microsoft Silverlight , а также различными HDTV вещает по наземному и спутниковому телевидению.
Алгоритмы генетического сжатия — это последнее поколение алгоритмов без потерь, которые сжимают данные (обычно последовательности нуклеотидов) с использованием как традиционных алгоритмов сжатия, так и генетических алгоритмов, адаптированных к конкретному типу данных. В 2012 году группа ученых из Университета Джонса Хопкинса опубликовала алгоритм генетического сжатия, который не использует для сжатия эталонный геном. HAPZIPPER был специально разработан для данных HapMap и обеспечивает более чем 20-кратное сжатие (уменьшение размера файла на 95%), обеспечивая в 2–4 раза лучшее сжатие и требует меньше вычислительных затрат, чем ведущие утилиты сжатия общего назначения. Для этого Чанда, Эльхайк и Бадер представили кодирование на основе MAF (MAFE), которое уменьшает гетерогенность набора данных за счет сортировки SNP по частоте их второстепенных аллелей, тем самым гомогенизируя набор данных. [77] Другие алгоритмы, разработанные в 2009 и 2013 годах (DNAZip и GenomeZip), имеют степень сжатия до 1200 раз, что позволяет хранить 6 миллиардов пар оснований диплоидных геномов человека в 2,5 мегабайтах (по отношению к эталонному геному или в среднем по множеству геномов). . [78] [79] Информацию об эталонных компрессорах данных генетики/геномики см. в [80]
Подсчитано, что общий объем данных, хранящихся на мировых устройствах хранения, может быть дополнительно сжат с помощью существующих алгоритмов сжатия с оставшимся средним коэффициентом 4,5:1. [81] Подсчитано, что совокупные технологические возможности мира для хранения информации обеспечивают 1300 эксабайт аппаратных цифр в 2007 году, но когда соответствующий контент оптимально сжат, это представляет собой только 295 эксабайт информации Шеннона . [82]
Общая цель исходного кодирования состоит в том, чтобы использовать или устранить «неэффективную» избыточность в источнике PCM и тем самым добиться снижения общей скорости источника R.
{{cite book}}
: CS1 maint: отсутствует местоположение издателя ( ссылка ){{citation}}
: CS1 maint: числовые имена: список авторов ( ссылка )По сути, вейвлет-кодирование — это вариант кодирования с преобразованием на основе DCT, который уменьшает или устраняет некоторые его ограничения. (...) Еще одним преимуществом является то, что вместо работы с блоками пикселей 8 × 8, как это происходит в JPEG и других методах блочного DCT, вейвлет-кодирование может одновременно сжимать все изображение.