Возможные способы сжатия ЦИ

Введение

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

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

,

где , обычно называемая коэффициентом сжатия, есть

.

В задаче цифрового сжатия изображений различаются и могут быть использованы три основных вида избыточности данных:

• Кодовая избыточность,
• Межэлементная,
• Визуальная.

Сжатие данных достигается в том случае, когда сокращается или устраняется избыточность одного или нескольких из вышеуказанных видов.

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

Межэлементная избыточность.Межэлементная избыточность связана с межэлементными связями внутри изображения. Поскольку значение любого элемента ЦИ может быть достаточно точно предсказано по значениям его соседей, то информация, содержащаяся в отдельном элементе, оказывается относительно малой. Бóльшая часть вклада отдельного элемента в изображение является избыточной, она может быть «угадана» на основе значений соседних элементов. Для отражения подобной межэлементной связи введены различные термины, такие как пространственная избыточность, геометрическая избыточность, внутрикадровая избыточность. Объединением их всех является термин межэлементная избыточность.

Для уменьшения межэлементной избыточности в изображении двумерный массив пикселей должен быть преобразован в некоторый более рациональный (но обычно «не визуальный») формат. Например, для представления изображения может быть использована разность между соседними элементами.

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

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

Возможные способы сжатия ЦИ

Сжатие посредством использования малоранговых аппроксимаций изображения. Пусть — матрица ЦИ размерами с элементами , ( ). Для нее справедливо представление, называемое сингулярным разложением (SVD):

, (2.1)

где ― матрицы размерности и соответственно; , . При этом удовлетворяют соотношениям: , где ― единичная матрица соответствующего размера, т.е. являются ортогональными. Столбцы матрицы и матрицы называют соответственно левыми и правыми сингулярными векторами матрицы , величины ― сингулярными числами (СНЧ), а назовем сингулярной тройкой . (При рассматривается SVD матрицы .)

Сингулярное разложение (2.1) матрицы может быть представлено в форме внешних произведений:

(2.2)

В общем случае SVD матрицы определяется неоднозначно. Назовем вектор лексикографически положительным, если его первая ненулевая компонента положительна, а SVD (2.1) нормальным, если столбцы матрицы лексикографически положительны. Можно показать, что невырожденная матрица имеет единственное нормальное SVD, если ее СНЧ попарно различны. Таким образом, СНЧ и сингулярные векторы (СНВ), получаемые нормальным SVD, однозначно определяют матрицу ЦИ.

Пусть ― симметричная -матрица, элементы которой , с собственными значениями (СЗ) , и ортонормированными собственными векторами (СВ) , спектральное разложение (СР) которой определяется в соответствии с формулой:

(2.3)

где ― матрица СЗ; ― матрица СВ.

Разложение (2.3), так же, как и (2.1), может быть представлено в форме внешних произведений:

.

В силу симметричности ее спектр, т.е. множество всех СЗ, всегда действительный. СЗ, являясь корнями характеристического многочлена , определяются однозначно, в отличие от СР (2.3).

По аналогии с нормальным SVD, СР назовем нормальным, если элементы матрицы удовлетворяют соотношению: , а СВ , лексикографически положительны. Имеет место следующая теорема.

Теорема. Пусть — невырожденная симметричная -матрица, модули СЗ которой попарно различны. Тогда для нее существует единственное нормальное СР.

Как правило, матрица ЦИ не удовлетворяет свойству: . Поставим в соответствие произвольной две симметричные матрицы той же размерности по следующему правилу:

. (2.4)

Утверждение. Для матрицы ближайшей в смысле спектральной нормы матрицей ранга является матрица , причем . Для матрицы , называемой малоранговой аппроксимацией , справедливо также представление , где .

Утверждение. Пусть . Для матрицы построено нормальное СР (2.3). Ближайшей к в смысле спектральной нормы матрицей ранга является , причем . Для матрицы , называемой малоранговой аппроксимацией , справедливо также представление , где .

Малоранговые аппроксимации матрицы ЦИ могут быть использованы для сжатия изображения. Пусть матрица имеет размеры , тогда нужно хранить ее элементов. С учетом того, что матрицы оригинальных ЦИ, как правило, имеют значительные размеры, актуальным является вопрос о том, можно ли сократить это количество? Рассмотрим в качестве примера ЦИ на рис.2.2(а), размеры которого 480*640. Построим SVD матрицы ЦИ. Матрица есть наилучшее приближение ранга , при этом для восстановления матрицы требуется лишь слов памяти, в которых хранятся векторы и . Приближения исходного ЦИ для различных значений показаны на рис.2.2(б,в,г)

а б

в г

Рис.2.2. Исходное ЦИ (а); результат сжатия изображения путем использования аппоксимации ранга (б); (в); (г)

Для визуально ЦИ неотличимо от исходного, однако выигрыш в памяти здесь значительный: для исходного – 640*480=307200 слов памяти; при - (640+480)*110=123200, т.е. почти в 3 раза.

Малоранговые аппроксимации ЦИ производят его сжатие за счет обнуления высокочастотных составляющих сигнала.