Дискретизация и квантование изображений (стр. 8 из 16)
, (4.25)
и пусть собственные векторы, связанные с ними, расставлены в том же порядке. Тогда матрица собственных векторов [Ф] обладает тем свойством, что умножение ее на вектор-изображение g(образованный лексикографической расстановкой) дает вектор
G = [ Ф ]g , (4.26)
имеющий некоррелированные компоненты, причем компоненты вектора G оказываются расставленными в порядке убывания их дисперсий [29], что является свойством дискретного варианта разложения Карунена - Лоэва, фактически описанного соотношениями (4.24) - (4.26).
Полезность преобразования Карунена — Лоэва ( КЛ, или ковариационного) для сокращения избыточности изображений очевидна. Массив отсчетов изображения заменяется набором переменных, имеющих различные статистические веса ). Сжатие можно получить, отбрасывая переменные с малым статистическим весом и сохраняя остальные. Если, например, оставить M<N2компонент вектора G и передать их вместе со специальной информацией о том, какие компоненты сохранены, то можно сузить ширину полосы в N2/M раз. В приемнике из принятых М чисел образуют N2 - компонентный вектор путем подстановки нулей вместо N2-М непереданных компонент. Из этого нового вектора, обозначенного как G' , с помощью преобразования
gc = [ Ф ]TG’ (4.27)
восстанавливается исходное изображение. В процессе сжатия возникает средняя квадратическая ошибка
|| g - gc || = 
(4.28)
особенность КЛ - преобразования состоит в том, что из всех линейных преобразований именно оно обеспечивает минимальную величину этой ошибки.
Из соотношений (4.25) и (4.26) видно, что число операций, необходимых для выполнения КЛ - преобразования, пропорционально N4, так как исходный массив содержит N2 отсчетов. Для типичных значений N ( N = 256 или 512 ) такое число чрезмерно велико. Еще труднее вычислить собственные значения и собственные векторы ковариационной матрицы [Cg] размером N2 
N2 Эксперименты показал, что очень многие элементы этой матрицы близки к нулю, т.е. коэффициент корреляции между отсчетами быстро стремится к нулю с увеличением расстояния между соответствующими точками изображений. Расстояние, при котором коэффициент корреляции между яркостями элементов изображения становится настолько малым, что его можно приравнять нулю (например, 5 или 10 % максимального значения), называется радиусом корреляции отсчетов; его можно выразить через целое число отсчетов. Зная это расстояние, все изображение можно разбить на блоки, размер которых больше радиуса корреляции, но сравним с ним. Если размер каждого блока равен Р, то можно вычислить. ковариационную матрицу всех блоков, имеющую размер P2 
P2:
[Cgp] =
, (4.29)где Q=N/P,agi- вектор, построенный из отсчетов i-го блока. Тогда, если [Фp] - матрица собственных векторов, связанных с P2собственными значениями, расположенными так же, как в формуле (4.25), то операции по сокращению избыточности для каждого из блоков выполняются по формулам (4.26) и (4.27),. как для полного изображения, но матрица [Ф] заменяется на [Фp]. Как правило, радиус корреляции большинства изображений имеет такую величину, что Р=16 является разумным компромиссом между размером ковариационной матрицы и скоростью, с которой коэффициент корреляции отсчетов приближается к нулю [30]. Длительность вычислений, выполняемых при сжатии видеоинформации поблочно, пропорциональна Q2/P4.
Хотя разложение изображения на блоки и делает сжатие видеоинформации методом КЛ - преобразования реально осуществимым процессом, но эффективность его остается недостаточной. Большой объем вычислений препятствует использованию подобных методов для обработки изображений типа телевизионных.
Создание алгоритмов быстрых преобразований (Фурье, Адамара и т.д.) существенно повлияло на многие области применения цифровой обработки сигналов. Аналогичным образом оно - сказалось и на методах сокращения избыточности изображений. Любое линейное преобразование, подобное разложению Карунена - Лоэва, переводит изображение в новую систему координат. В силу свойств КЛ - преобразования случайные компоненты изображения в новых координатах оказываются некоррелированными. Резонно спросить: будут ли другие преобразования, особенно быстрые типа БПФ, обладать такими же полезными свойствами? К счастью, ответ оказывается положительным. Хотя быстрые преобразования и не приводят к полной некоррелированности компонент, как в случае КЛ - преобразования, но все же они дают очень хорошие результаты. Их достоинства, связанные с быстротой вычислений, полностью компенсируют некоторое понижение эффективности сжатия, характерное для них.
Схемы сжатия на основе быстрых преобразований можно описать примерно так же, как и схемы с КЛ - преобразованием. Дополнительным достоинством быстрых алгоритмов является их разделимость, так что двумерные преобразования можно выполнить с 'помощью одномерных операций. Кроме того, их проще описать математически. Если матрица [W] соответствует оператору ортогонального унитарного одномерного преобразования (как, например, матрицы ядер преобразований Фурье, Адамара и т.д. [31] ), то «поворот» изображения в новую систему координат выполняется по формуле
[ G ] = [ W ]T [ g ] [ W ] , (4.30)
гдe ,[g] - исходная матрица отсчетов изображения размером N
N, a [G] - преобразование матрицы [g]. Нетрудно заметить, что формула (4.30) описывает двухэтапное преобразование: сначала по строкам изображения, а затем по столбцам преобразований от строк. Записывая преобразование (4.30) в явном виде через элементы матриц, получим:G(m,n) =
(4.31)
=
где второе равенство является следствием разделимости ядра преобразования. Свойством разделимости обладает ядро преобразования Фурье, наиболее часто применяемого на практике:
(m,n,j,k) = exp [- 
] =(4.32)
= exp [ -
] exp [ - 
] ,а также ядра менее известных преобразований, таких, как преобразования Адамара и Хаара. Более подробно этот вопрос рассмотрен в работе Эндрюса [31].
Собственные значения 
i , получаемые методом КЛ - преобразования, соответствуют фактическим величинам дисперсий проекций вектора-изображения на координатные оси пространства, в котором вñå компоненты изображения некоррелированы. В системах координат, получаемых при быстром преобразовании, коэффициенты преобразования (т.е. элементы матрицы [G] ) равны проекциям вектора - изображения на оси координат, полученным с помощью матрицы преобразования [W], но не являются дисперсиями. Однако как при КЛ - преобразовании, так и в пространствах быстрых преобразований происходит концентрация энергии. В первом случае наибольшие
дисперсии (и, следовательно, наибольшие энергии) связаны с теми столбцами матрицы [Ф] или [Фр], которые соответствуют предпочтительным (или «естественным») направлениям наибольшего изменения видеоинформации. Аналогично в пространстве быстрого преобразования наибольшими являются коэффициенты, которые соответствуют предпочтительным (или «естественным») направлениям вектора-изображения. С этой точки зрения сжатие в пространстве преобразований (как для преобразования Карунена - Лоэва, так и для быстрых преобразований) является по существу разложением изображения в ряд по базисным векторам (или базисным изображениям, так как каждый вектор должен описывать двумерную структуру) и таким усечением разложения, при котором ошибка мала, а число отбрасываемых составляющих - большое. Усечение оказывается возможным потому, что небольшое число компонент содержит основную часть энергии изображения.
Для иллюстрации рассмотрим схему сжатия в пространстве-преобразовании, основанную на преобразовании Фурье. Из соотношений (4.31) и (4.32) видно, что (т, п)-й коэффициент преобразования G(m,n) является проекцией исходного изображения g(j,k) на базисный вектор (или базисное изображение), образованный при помощи (т, п)-го значения ядра Фурье
( m , n) = exp ( 
) . (4.33)Для типичных изображений характерно, что в области пространственных частот элементы с малыми индексами велики по сравнению с элементами с большими индексами. Таким образом, структура изображения обычно имеет низкочастотный характер. Низкочастотные составляющие определяют контуры предметов, а также яркость и контрастность изображения. Высокочастотные - составляющие создают резкие линии и определяют общую четкость изображения, но суммарная энергия их невелика. Так, 95% энергии типичного изображения может приходиться на низкочастотные составляющие, занимающие 5% от общей площади двумерной пространственно - частотной области преобразования Фурье. Сохраняя эти спектральные составляющие и достаточно много высокочастотных компонент, чтобы резкость изображения была приемлема для человеческого глаза, можно добиться существенного уменьшения объема избыточной информации.