7. Сжатие графических изображений

Проблема сжатия графических изображений появилась сравнительно недавно в связи с необходимостью хранения, создания изображений (мультимедиа) и их трансформации (программы - морфинги), а также при повсеместном внедрении издательских систем. Очень интенсивно распространяется в настоящее время организация баз данных в виде гипертекстовых структур [48]. Последние широко практикуются в среде INTERNET, включая специализированные HTTP - серверы (в них хранятся данные в виде гипертекстовых структур. Дополнительная необходимость в хранении изображений появляется при передаче в цифровой форме видеофильмов и при использовании программ - аниматоров. Оптическое изображение, в отличие от символьных данных, имеет гораздо большую информационную ёмкость. Оценим, например, информационную ёмкость одного кадра телевизионного изображения, предполагая, что оно состоит из 625 строк, количество дискретных элементов по строке по стандарту должно быть не меньше 1,25*625 = 781. Предположим, формируется чёрно - белое изображение с количеством градаций яркости в каждой точке, выраженным 8-разрядным двоичным кодом (меньше нельзя по тому же стандарту ) . Тогда, если предположить, что все точки изображения некоррелированы (т.е. независимы), то одно изображение содержит 3.9Мбайт. Если нужно передавать кадры со стандартной скоростью 25 кадров в секунду, необходимая пропускная способность информационного канала должна быть не меньше 100Мбайт в секунду, или 800 Мбод. Это астрономическая цифра, недостижимая на практике.

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

Качество изображения и особенно его цветопередача - вопрос весьма субъективный, зависящий как от конкретного человека (возьмём, например, дальтоника), так и от особенностей человеческого восприятия цвета, интенсивности и чёткости. Достаточно подробно об этом можно узнать в специальной литературе, например, в [49].

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

Один из наиболее распространённых стандартов сжатия статических (неподвижных) изображений - видеостандарт JPEG. Он основан на существующей корреляции элементов изображения и на разумных требованиях к его качеству. В основе этого стандарта лежит представление всего изображения в виде совокупности фрагментов (т.е., всё поле изображения разделяется на одинаковые квадраты фиксированного размера). Величина одного фрагмента 8*8 или 16*16 пикселов.

Алгоритм сжатия состоит из трёх последовательных процедур: дискретного косинус - преобразования, ранжирования полученного спектра с последующим его округлением и собственно кодирования. Рассмотрим эти процедуры по порядку.

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

Графическое монохромное изображение можно рассматривать как трёхмерное колебание (две координаты самого изображения плюс яркость пиксела). Исходя из этого, ДКП представляет собой двумерное Фурье - преобразование по двум пространственным координатам, в котором аргументом является яркость самого пиксела. Тогда прямое ДКП имеет вид:

,

(2.24)

а обратное ДКП записывается формулой:

.

(2.25)

Здесь величины i , j - координаты конкретного пиксела; х , у - текущие координаты по горизонтали и вертикали соответственно; DCT( i, j ) - значение амплитуды i,j - й двумерной гармонической составляющей; pixel ( x,y ) - величина яркости соответствующего пиксела; N - число пикселов в фрагменте изображения (64 или 256 ).

Как следует из выражений (2.24) и (2.25), для вычисления одной точки спектра (и обратного преобразования) требуется N умножений, как правило, в комплексной форме, и столько же сложений. Это операции громоздкие, поэтому коммерческие версии алгоритма используют специальные процедуры, ускоряющие вычисления (декомпозицию матриц, быстрое преобразование Фурье, переход на целочисленную арифметику и т.д.; более подробно эти процедуры можно изучить в специальной литературе).

После окончания вычислений результаты заносят в память в виде двумерной матрицы, причём записывают их "змейкой". Для этого каждую гармонику предварительно нумеруют по правилу k=i+j , т.е. от двухбуквенной индексации переходят к однобуквенной. Порядок расположения пронумерованных таким образом гармоник иллюстрируется на рис.2.16. Поясним изображение. В левом верхнем углу располагается гармоника с индексом 1, следующая, 2-я гармоника помещается справа, т.е. смещена на позицию по горизонтали; 3-я гармоника смещается на позицию по вертикали, а 4-я располагается уже по диагонали и т.д. Последняя, 64-я гармоника находится в правом нижнем углу. Из рис. 2.18 видно, почему размещение называется "змейкой".

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

Для организации округления вначале формируют специальную весовую матрицу (или матрицу округления). Матрица состоит из коэффициентов, как правило, целочисленных, и имеет размер 8*8. Каждый коэффициент матрицы спектра, сформированной на предыдущем этапе, делится на соответствующий коэффициент матрицы округления; полученные при этом значения округляются до определённого знака после запятой. При этом достаточно малые числа округляются до нуля (это очень важно!).

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

a = ( 1 + i + j ) * q,

(2.26)

где q - число, называемое фактором качества; чем больше q, тем меньше коэффициенты взвешенной матрицы спектра, тем большим будет округление, следовательно, тем хуже качество восстановленного по взвешенной матрице изображения. Значения q лежат в пределах от 2 до 25. Качество восстановленного изображения чаще всего оценивается субъективно, поэтому конкретные рекомендации по выбору q заранее дать проблематично. Завышенные значения q приводят к размыванию границ изображения, потерям мелких деталей а иногда - к так называемому муар - эффекту, когда отдельные линии (чаще на границах контуров ) превращаются в несколько параллельных линий. Качество иногда проверяют по специальным, тестовым картинкам, аналогичным контрольным кадрам телевидения.

Для примера на рис.2.17 приведена матрица округления при факторе качества q = 4. Как видно из рисунка, коэффициенты матрицы возрастают в направлении слева направо и сверху вниз. Отсюда видно, что округлению подвергаются в основном высшие гармоники спектра, т.е. при сжатии изображения мы отказываемся от чёткого изображения деталей.

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

Описанная выше процедура сжатия применяется для монохромного (т.е. чёрно - белого) изображения; при сжатии цветного изображения её применяют трижды для каждой из основных составляющих цвета.

Стандарт JPEG применяется для передачи статических изображений. В нём каждое следующее изображение кодируется независимо от предыдущих, поэтому коэффициент сжатия сравнительно невелик (как правило, хорошее изображение восстанавливается при коэффициенте сжатия порядка 8 - 10 ).Намного большее сжатие получается для динамических изображений, характерных для видеофильмов; для них используются специальные алгоритмы сжатия семейства MPEG.