03.11.2017 admin

4.1 Базисы преобразования изображений


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

S=A–1PA=ATPA


Хорошо известно, что у симметричных матриц P=PT собственные числа вещественны и совпадают по модулю с сингулярными числами, а собственные вектора ортогональны, их называют еще сингулярными векторами. Спектр S является диагональной матрицей спектра, если матрица A совпадает с матрицей V сингулярного разложения P=VSVT.

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

Ортогональные матрицы относятся к матрицам вращения. Умножение любого вектор-столбца или вектор-строки на нее поворачивает вектор, не меняя его длины. Таким образом, умножение на матрицу слева и справа, трактуемое как нахождение некоторого обобщенного спектра, не меняет дисперсию элементов изображения (разброс значений). На этом этапе никакого сжатия информации, не происходит. Так зачем же она, эта матрица? Она необходима для подготовки к сжатию применением матрицы F фильтра – сближающего отсчеты тривиальным умножением их на коэффициент, меньший 1.

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

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

Следует отчетливо понимать, что и фильтрация сама по себе тоже не приводит к сжатию. Замена одних значений спектра изображения на другие, приглаженные, ничего формально не меняет. В самом деле, нет разницы, хранить в файле число 125 или, скажем, 110. Откуда сжатие? Дело все в том, что при понижении амплитуд значения некоторых пикселей сливаются, в спектре появляются цепочки одинаковых элементов. Примитивное сжатие реализуется так, например, что вместо хранения всех элементов цепочки мы можем хранить одно значение. Указав дополнительно, сколько таких элементов в цепи.

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

Едва ли не в середине прошлого века тогда еще студент Хаффман предложил иную идею сжатия. Сначала выясняется, какая цепочка одинаковых точек достигаем максимальной длины. Разрешено подсчитывать длины прерываемых иными точками цепочек. Численному значению пикселя наиболее длинной цепочки присваивается максимально короткий бинарный код, например, 1. Для второй по длине цепочки код удлиняется, но он тоже короткий, скажем, 01. И т.п. Вместо значений пикселей хранятся эти коды и, разумеется, их расшифровки.

Не путайте механизмы нахождения спектра и фильтрации с самим сжатием, они лишь создают почву для него, поджимая спектры по амплитуде. Если нет алгоритма Хаффмана, под рукой, сжимайте методом PNG. Это сжатие примерно так и устроено. Кстати, парадоксально, но факт. Ортогональное преобразование с фильтрацией могут рассматриваться как лишние, ненужные и вредные операции, которые только портят картинку и создают ненужные всем хорошо известные проблемы разводов и ореолов. Именно поэтому и появился PNG без них, и этот алгоритм получил широкое распространение.

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

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

Hide

Rambler's Top100