Microsoft Word Уч пособие 22 09. doc

Дискретное косинусное преобразование

Более эффективным, чем Фурье преобразование, является ДКП [12]. Преимущества ДКП связаны с тем, что в отличие от комплексного спектра на выходе ДПФ, при ДКП формируются вещественные спектральные коэффициенты преобразования. Кроме того, эти коэффициенты с ростом частоты убывают быстрее, чем коэффициенты ДПФ.
Рассмотрим двумерное ДКП изображения размером N столбцов и M
строк. Двумерное ДКП вычисляется по формулам:

_{ } 2
M 1 N 1
_ 2n  1u _
 2m  1v _

Z u,v 
uv _{ }
f n,mcos_
2N
_cos_{ 2M
} ,(8.14)

m0 n0
   

где u  0,N 1,
v  0,M 1, при k=(u,v)
k   ^{1 2 ,}


_ 1,
k  0 _.
иначе

Двумерное ДКП разделимо:

_ M 1_{ 2}
N 1
_ 2n  1u _^
_ 2m  1v _^

Z u,v 
v^ _ ^ u _
f n,mcos_
^cos_{ }^

N
 ^
m0
n0
_ 2N
^  ^2M ^


_ M 1
  _
 2m  1v _^

 v^ _
Z u,mcos_
^ , (8.15)


 m0
 
_ 2M


N 1


_2n  1u _

где
Z u,m 
2 N u _
n0
f n,mcos_{ 2N}
_ является одномерным

ДКП по строке m.
В соответствии с (8.15) двумерное преобразование ДКП можно выполнить как два последовательных одномерных преобразований ДКП. Сначала выполняется одномерное ДКП по строкам, а затем - по столбцам. В этом случае обратное ДКП (ОДКП) вычисляется в соответствии с уравнениями:

Z u,m 
^{M 1} vZ u,vcos^{2m  1v } , (8.16)

_
v0
_ _2M _

Z n,m 
N 1
uZ u,mcos^{2n  1u } . (8.17)

_
u 0
_ _2N _

С целью повышения быстродействия и сохранения локальных свойств изображения преобразование ДКП выполняется не над всем изображением, а разбивается на блоки, размер которых существенно меньше размера изображения.
При размере блока 8x8 элементов, длина последовательности N=8.
ДКП с точностью до множителей  k  можно представить в
матричном виде как произведение матрицы преобразования на вектор- столбец входных данных:

1	1	1	1	1	1	1	1	
				 	 	 	 ^ 

^Z₀   ^f₀ 
 _Z   _f 

	 	 	 	 	  ^^^f2 ^
 	 	 			 	  f     3 

^ 1 ^ _
^ 1 ^

^Z₂ ^ _
_Z  _

 ₃  _{ }
, (8.18)

_Z 
4
^     
    
_  _f 

f


4

Z




  _
 ₅  _
  
    
  ^
 
 ₅ 

_Z 
6
^   
    
   ^
 _f 
6


_Z

7 ^
^  
     
  ^





_ f

7 ^

где   cos 4  0,707;
  cos 8  0,924 ;
  sin 8  0,383 ;

  cos 16  0,981;   cos3 16  0,831;   sin3 16  0,556 ;
  sin 16  0,195 . На рисунке 8.9 приведены одномерные базисные функции ДКП для N=8.

3

2

1
₁ k=0

0
0
-1

1

7

6
n ₀

-1 _{0 1}

5

4
2 3 4 5 6 7

1

0

-1 _{0 1}

2 3 4 5 6 7

k=1
1 _1
1 k=7

0
n ₀ ⁿ
0
^-1 -1

0 1 2 3 4 5 6 7


k=2
1


₀ n
0 1 2 3 4 5 6 7
1

0
0 1 2 3 4 5 6 7

-1 _-1
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
Рисунок 8.9 Базисные функции ДКП, n-порядковый номер отсчета входной последовательности, k-номер выходного значения коэффициента ДКП.
Значимые коэффициенты ДКП сосредоточены в области НЧ. Покажем на примере преимущество использования ДКП перед ДПФ при сжатии изображений. Возьмем изображение размером 512x512. Выполним преобразования. Оставим матрицу коэффициентов 100x100. Остальные коэффициенты обнулим. Выполним обратные преобразования.
Полученные восстановленные изображения приведены на рисунке
8.10. Видно, что ДКП позволяет получить более высокое качество восстановленного изображения, чем ДПФ.

7. Сжатие данных по методу JPEG

В 1992 ISO (International Organization for Standartization - Международная организация по стандартизации), ITU и международной электротехнической комиссией IEC (International Electrotechnical Comission- Международный электротехнический комитет) был установлен стандарт JPEG для сжатия неподвижных изображений [56]. В формате записи изображений JPEG применен метод сжатия данных с использованием ДКП, т.е. метод сжатия данных с потерями информации. Аббревиатура JPEG означает название организации, разработавшей этот стандарт, - Joint Photographic Experts Group (Объединенная группа экспертов по фотографии).

а)б)
Рисунок 8.10 Изображение, восстановленное по 3,8% коэффициентов: а) по алгоритму ОДПФ; б) по алгоритму ОДКП.
Метод предусматривает сжатие неподвижных изображений как полутоновых, так и цветных. При разработке метода предъявлялись следующие основные требования:

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

Схема кодера JPEG представлена на рисунке 8.11. Рассмотрим более общий случай сжатия цветных изображений, каждый элемент которых представлен 3 - мя байтами, по байту на каждый цветовой компонент (R,G и В).


блоки 8x8



ДКП




Квантова- тель




Энтропий- ный кодер




Поток сжатых данных


Таблица квантую- щих коэфф.




Таблица кодов

Рисунок 8.11 Схема кодера JPEG.

Кодирование изображения начинается с того, что оно разбивается на отдельные блоки размером 16x16 отсчетов, которые затем кодируются (сжимаются) независимо друг от друга. Далее, в каждом блоке осуществляют переход от 3-х матриц спектральных коэффициентов для красного, зеленого и синего компонентов изображения, к трем матрицам,
представляющим яркостный (Y), и два цветоразностных компонента
изображения Cb и Cr . Поскольку острота зрения при наблюдении
чисто хроматических изображений существенно ниже, чем в случае наблюдения изображений, имеющих яркостный контраст, переход к компонентам Сb и Сr выгоден, так как позволяет при их кодировании использовать меньшее количество отсчетов в блоке и за счет этого получить дополнительное сжатие [52]. Более того, хроматические компоненты квантуются грубее. Преобразование цветового координатного пространства RGB в пространство YCrCb в соответствии с (3.1) позволяет декоррелировать RGB компоненты сигнала. Затем матрица, имеющая размер 16x16 отсчетов, разбивается на 4 матрицы яркости Y размером 8x8 отсчетов каждая и две матрицы цветности размером 8x8 (Сb) и (Cr) в соответствии с тем, как показано на рисунке 8.12.