Пусть, например, изображение хранится в квадратной матрице X с элементами xi,j N строк на N столбцов. Обрабатывая матрицу, имеем временную сложность алгоритма как минимум кратной N3. Для уменьшения размеров обрабатываемой матрицы изображение разбивают на несколько фрагментов размером n на n, n << N, которые обрабатывают отдельно. Тогда вместо N3 будем иметь N2 х n сложность алгоритма.
Сжатие графической информации приводит к потерям, потому что из сжатого выходного массива невозможно при декодировании получить исходный массив. Но будем сжимать изображение таким образом, чтобы потери как можно меньше воспринимались глазом. Например, можно уменьшить количество бит для хранения одного пиксела. Пусть пикселы исходного изображения имеют формат RGB Truecolor 8:8:8. Перекодируем изображение в формат 5:5:5 (то есть каждая цветовая составляющая будет иметь 25 = 32 градации), отбрасывая младшие четыре бита изображения. Мы также можем использовать свойство глаза наиболее хорошо различать цвет в области зеленого и кодировать изображение в формат RGB 4:5:4, и каждый пиксел будет занимать два байта.
Можно перевести исходное изображение в другую цветовую модель и отформатировать его. Дальнейшее усовершенствование алгоритмов заключается в индексировании цветов.
Рассмотрим собственно кодирование. Оно состоит из двух этапов: кодирования контуров и текстур, лежащих в них. Контуры представляются в виде матрицы с битовыми элементами, которые равны 1, если точки входят в границу области – контур и 0 – иначе. Данную матрицу можно энтропийно сжать с эффективностью ~1.2 – 1.3 бита на пиксел контура. Текстура (содержимое) каждой области приближается к среднему уровню свойства ее области двумерным полиномом (линейным, квадратным или кубическим – в зависимости от реализации и требований к качеству). При декодировании прибавляют зернистость в текстуру с помощью гауссова псевдослучайного фильтра с уже известной среднеквадратичной ошибкой. Данный метод позволяет добиться сжатия изображения в 20 – 75 раз с приемлемым качеством изображения, но временные затраты при этом весьма велики. С помощью данного метода мы также можем (с небольшими дополнительными вычислениями) параллельно перевести изображение в векторную форму.
5. КОДИРОВАНИЕ ЗВУКА И ВИДЕО
Кодирование звука
Персональные компьютеры получили возможность работать со звуковой информацией с начала 90-х годов. Каждый компьютер, имеющий звуковую плату, микрофон и колонки, может записывать, сохранять и воспроизводить звуковую информацию.
Звук представляет собой звуковую волну с непрерывно меняющимися амплитудой и частотой. Чем больше амплитуда, тем он громче для человека, чем больше частота сигнала, тем выше тон. Программное обеспечение компьютера в настоящее время позволяет непрерывный звуковой сигнал преобразовывать в последовательность электрических импульсов, которые можно представить в двоичной форме. Для «перевода» символьной информации в понятную компьютеру форму достаточно иметь таблицу соответствия между символами этого языка и их двоичными кодами. В 1983 г. ведущие производители компьютеров и музыкальных синтезаторов разработали стандарт, определивший такую систему кодов. Он получил название MIDI (Musical Instrument Digital Interface) – цифровой интерфейс для музыкальных инструментов. Этот стандарт определяет еще и физические характеристики линий передачи, протоколы связи и многое другое. В результате все MIDI-устройства совместимы между собой.
Процесс преобразования звуковых волн в двоичный код в памяти компьютера можно представить в следующем виде:
Если преобразовать звук в электрический сигнал (например, с помощью микрофона), мы увидим плавно изменяющееся с течением времени напряжение. Для компьютерной обработки такой аналоговый сигнал нужно каким-то образом преобразовать в последовательность двоичных чисел. Поступим следующим образом. Будем измерять напряжение через равные промежутки времени и записывать полученные значения в память компьютера. Этот процесс называется дискретизацией (или оцифровкой), а устройство, выполняющее его, – аналого-цифровым преобразователем (АЦП).
Процесс воспроизведения звуковой информации, сохраненной в памяти ЭВМ, имеет обратную направленность:
Для того чтобы воспроизвести закодированный таким образом звук, нужно выполнить обратное преобразование (для него служит цифро-аналоговый преобразователь – ЦАП), а затем сгладить получившийся ступенчатый сигнал (рис. 
22).
Рис. 22. Принципы работы АЦП и ЦАП
Приёмы и методы работы со звуковой информацией пришли в вычислительную технику сравнительно недавно. К тому же, в отличие от числовых, текстовых и графических данных, у звукозаписей не было столь же длительной и проверенной истории кодирования. В итоге методы кодирования звуковой информации двоичным кодом далеки от стандартизации. Компании разработали довольно много своих корпоративных стандартов, но среди них можно выделить два основных направления.
1. Метод FM (Frequency Modulation) основан на том, что теоретически любой сложный звук можно разложить на последовательность простейших гармонических сигналов разных частот, каждый из которых представляет собой правильную синусоиду, а следовательно, может быть описан числовыми параметрами, т.е. кодом. В природе звуковые сигналы имеют непрерывный спектр, т.е. являются аналоговыми. Их разложение в гармонические ряды и представление в виде дискретных цифровых сигналов выполняют специальные устройства – аналогово-цифровые преобразователи (АЦП). Обратное преобразование для воспроизведения звука, закодированного числовым кодом, выполняют цифро-аналоговые преобразователи (ЦАП). При таких преобразованиях неизбежны потери информации, связанные с методом кодирования, поэтому качество звукозаписи обычно получается не вполне удовлетворительным и соответствует качеству звучания простейших электромузыкальных инструментов с характерной для электронной музыки окраской. В то же время данный метод кодирования обеспечивает весьма компактный код, поэтому нашёл применение ещё в те годы, когда ресурсы средств вычислительной техники были явно недостаточны.
2. Метод таблично-волнового (Wave-Table) синтеза лучше соответствует современному уровню развития техники. В заранее подготовленных таблицах хранятся образцы звуков для множества различных музыкальных инструментах. В технике такие образцы называют сэмплами. Числовые коды выражают тип инструмента, номер его модели, высоту тона, продолжительность и интенсивность звука, динамику его изменения, некоторые параметры среды, в которой происходит звучание, а также прочие параметры, характеризующие особенности звучания. Поскольку в качестве образцов берутся реальные звуки, то качество звучания получается очень высоким и приближается к звучанию реальных музыкальных инструментов.
