Сжатие изображений с потерей качества

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

Введем две N × N матрицы преобразования

T_c = {t_c(u,i)}, u,i = 0,1,...,N-1

и

T_r = {t_r(v,j)}, v,j = 0,1,...N-1.

Если двумерное изображение есть N×N матрица X, то N × N линейное преобразование для X можно записать как Y = T_c∙X∙T_r^T, где A^T означает транспонирование матрицы A. Матрицы T_c, T_r также называют ядрами преобразования. Строки этих матриц являются базисными функциями. Умножение X слева на матрицу T_c можно рассматривать как преобразование строк. Последующее умножение X справа на T_r можно интерпретировать как преобразование столбцов. Если преобразование симметрично, т.е. если T_c=T_r = T, то преобразование выполняется по формуле

Y = T∙X∙T ^T.

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

· Локализация большой части энергии в небольшом числе коэффициентов преобразования. Это позволило бы при кодировании с потерей качества после вычисления преобразования исключить из рассмотрения наименее информативные коэффициенты преобразования.

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

· Ортонормированность преобразования. Если это свойство выполняется, сумма ошибок аппроксимации коэффициентов преобразования в точности равна ошибке аппроксимации изображения в целом. При неортонормированном преобразовании ничтожно малая ошибка преобразования какого-либо коэффициента, вообще говоря, могла бы привести к значительному искажению изображения.

· Низкая сложность вычисления коэффициентов преобразования. В частности, желательно использовать так называемые сепарабельные преобразования, для которых вычисление коэффициентов преобразования матрицы X размера N×N могут быть выполнено поэтапно. Сначала вычисляется преобразование каждой из N строк матрицы X, затем поочередно вычисляется преобразование каждого из N полученных на первом этапе векторов коэффициентов преобразования.

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

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