소스코딩

소스코딩은 어떤규칙에 의해서 정보를 압축시켜 전송량을 줄이고자하는 절차이다.

엔트로피는 심벌당 평균 정보량 이다. (불확실성의 측정량)

H(x)=∑p∙log_2 (1/p)

엔트로피는 사건의 확률이 같을때, 최대가 된다.

 (예시)  00, 01, 10, 11 네개의 심볼이 p=1/4 확률로 발생하면, 엔트로피는 2 bits

Shannon's 1st theorem : 정보를 코딩하는데 필요한 bit의 개수는 적어도 그 엔트로피 이상 필요

% 허프만 코딩 p=[0.2 0.15 0.13 0.12 0.1 0.09 0.08 0.07 0.06];    % 어떤 사건이 일어날 확률들 h={'1' '0'}; M=length(p);  N=M-1; p=p(:); % make p a column vector if M>2   pp(:,1)=p;   for n=1:N      [pp(1:M-n+1,n),o(1:M-n+1,n)]=sort(pp(1:M-n+1,n),1,'descend'); % in descending order      if n==1, ord0=o; end  % Original descending order      if M-n>1        pp(1:M-n,n+1)=[pp(1:M-1-n,n); sum(pp(M-n:M-n+1,n))];      end   end   for n=N:-1:2      tmp=N-n+2; oi=o(1:tmp,n);      for i=1:tmp, ht{oi(i)}=h{i}; end      h=ht; h{tmp+1}=h{tmp};      h{tmp}=[h{tmp} '1'];      h{tmp+1}=[h{tmp+1} '0'];   end   for i=1:length(ord0), ht{ord0(i)}=h{i}; end   h=ht; end L=0; for n=1:M   L=L+p(n)*length(h{n});% Average codeword length end H=-sum(p.*log2(p)); % Entropy

>> L,H,pp,o,h
L =    3.1000
H =     3.0731

pp =
0.2000 0.2000 0.2000 0.2200 0.2600 0.3200 0.4200 0.5800
0.1500 0.1500 0.1700 0.2000 0.2200 0.2600 0.3200 0.4200
0.1300 0.1300 0.1500 0.1700 0.2000 0.2200 0.2600 0
0.1200 0.1300 0.1300 0.1500 0.1700 0.2000 0 0
0.1000 0.1200 0.1300 0.1300 0.1500 0 0 0
0.0900 0.1000 0.1200 0.1300 0 0 0 0
0.0800 0.0900 0.1000 0 0 0 0 0
0.0700 0.0800 0 0 0 0 0 0
0.0600 0 0 0 0 0 0 0

o =
1 1 1 6 5 4 3 2
2 2 7 1 1 1 1 1
3 3 2 2 2 2 2 0
4 8 3 3 3 3 0 0
5 4 4 4 4 0 0 0
6 5 5 5 0 0 0 0
7 6 6 0 0 0 0 0
8 7 0 0 0 0 0 0
9 0 0 0 0 0 0 0

h =
Columns 1 through 8
'00' '110' '101' '011' '010' '1111' '1110' '1001'
Column 9
'1000'

부연설명을 하자면, 1 ~9까지의 심벌의 발생확률이 p라고 했을때,
100심벌을 전송한다고 가정해 보자!
메시지를 2진코드로 4bit씩 그대로 코딩하면, 400bit 가 필요한 반면,
허프만코딩은 20*2+(15+13+12+10)*3+(9+8+7+6)*4=310bit 로 정보를 압축할 수 있다.

이와달리, 심벌들의 발생과 확률분포가 필요없이 주어진 소스 시퀀스에 대한 codetable을 만들어 사용하는 Lempel-Ziv-Welch 코딩도 있다.
Lempel-Ziv 알고리즘은 허프만을 대신해 파일압축을 위한 기본으로 널리 이용되고 있다.

지금까지는 통계적 중복성 제거 를 통한 정보압축이었다.


시각적/청각적 특징 을 기반한 정보의 압축으로는
영상의 디지털화 형식(원래 RGB=8:8:8 → Ycbcr=8:2:2, 8:4:4), 음성의 마스킹 효과가 있다.


시간적 중복성 제거
영상에서 움직임 예측 및 움직임 보상 이론


공간적 중복성 제거
예로는, JPEG의 압축기술인 DCT를 들 수 있다.

DCT(Discrete Cosine Transform)은 직교 변환을 이용한 것으로, 공간상의 영상 데이터를 주파수상의 에너지 분포로 변환시키는 것이다.

F(u,v)=(1/4)∙C(u)C(v)∑_(i=0~7)∑_(j=0~7)f(i,j)cos((2i+1)uπ/16) cos((2j+1)vπ/16)
여기서 C(x)={(1/√2 ,x=0 @ 1 ,otherwise)}

Xr=[]; X=[]; for u=0:7            for v=0:7                      for i=0:7                                 for j=0:7                     x(i+1,j+1)=cos((2*i+1)*u*pi/16).*cos((2*j+1)*v*pi/16);                                 end                      end                      Xr=[Xr x];                 subplot(8,8,u*8+v+1), imshow(x,[-1,1])            end            X=[X; Xr]; Xr=[]; end

64개의 DCT 기본함수

용량큰 JPEG를 화면에 뿌려줄때, 흐릿하다가 좀 뒤에 또렷해지는 것은...
위에 저주파의 신호부터 지그재그로 읽어들이는 도중에 먼저 화면에 뿌리고, 고주파의 신호까지 완벽히 읽은 뒤에 마지막으로 다시 화면에 뿌려주기 때문일 것이다.

부연설명을 하자면, 영상을 DCT변환하면 수직·수평 저주파 계수들의 값은 크고, 고주파로 갈 수록 값이 작아지는데, 이를 양자화하는데서 압축을 하면 정보량을 많이 줄일 수 있다.
 

RGB = imread('autumn.tif');         I = rgb2gray(RGB);         J = dct2(I);         imshow(log(abs(J)),[]), colormap(jet), colorbar         J(abs(J)<10) = 0;         K = idct2(J);         figure, imshow(I)         figure, imshow(K,[0 255])

웨이블릿 변환

 정지영상압축 표준인 JPEG2000에서 매우 중요한 부분을 차지하고 있으며, MPEG-4, H.264등에도 사용되고 있다. 또한 잡음제거, 에지 검출과 같은 다양한 영상신호 처리에 응용된다.
웨이블릿 변환에 사용되는 기저 함수의 집합은 하나의 기본 웨이블릿 기저 함수에 대한 시간축 방향으로의 확대 및 축소 그리고 평행 이동을 통해 얻어진다. 기본 웨이블릿 기저 함수는 특별한 형태의 band-pass 필터로 생각할 수 있다. 웨이블릿 변환에서는 주파수 대역이라는 용어 대신에 스케일(scale)이라는 용어를 주로 사용한다.


Ψ_j,k(t) : 웨이블릿 크기 압축계수(scale, j), 시간축으로의 이동 전이계수(translattion, k)

DWT : f(t)=∑_(j⊂Z)C_0*Φ_0,j(t)+∑_(k≥0))∑_(j⊂Z)d_k,j*Ψ_k,j(t)

load wbarb; wavelet = 'haar'; % Define wavelet of your choice level = 2; % Define wavelet decomposition level [C S] = wavedec2(X,level,wavelet); % Compute multilevel 2D wavelet decomposition % decomposition vector C = [ A(N) | H(N) | V(N) | D(N) | ... | H(1) | V(1) | D(1) ] % the corresponding bookkeeping matrix S % Define colormap and set rescale value colormap(map); rv = length(map); % Plot wavelet decomposition using square mode A = cell(1,level); H = A; V = A; D = A; for k = 1:level A{k} = appcoef2(C,S,wavelet,k); % Extract 2-D approximation coefficients [H{k} V{k} D{k}] = detcoef2('a',C,S,k); % Extract 2-D detail coefficients A{k} = wcodemat(A{k},rv); % Extended pseudocolor matrix scaling % approximation coefficients H{k} = wcodemat(H{k},rv); % hori. detail coefficients V{k} = wcodemat(V{k},rv); % vert. detail coefficients D{k} = wcodemat(D{k},rv); % diag. detail coefficients end dec = cell(1,level); dec{level} = [A{level} H{level} ; V{level} D{level}]; for k = level-1:-1:1 dec{k} = [imresize(dec{k+1},size(H{k})) H{k} ; V{k} D{k}]; end figure(1); image(dec{1}); title(['Decomposition at level ',num2str(level)]); % Peak Signal To Noise Rate X0 = waverec2(C,S, wavelet); error=X-X0; s_error=error^2; ms_error=sum(sum(s_error),2)/(256*256); Peak_SNR=10*log(255*255/ms_error) % Analyze Frequency Characteristic of above wavelet filters [D_L, D_H, R_L, R_H] = wfilters(wavelet); den = [1]; figure(2); freqz(D_L, den); figure(3); freqz(D_H, den); figure(4); subplot(221); stem(D_L); title('Decomposition low-pass filter'); subplot(222); stem(D_H); title('Decomposition high-pass filter'); subplot(223); stem(R_L); title('Reconstruction low-pass filter'); subplot(224); stem(R_H); title('Reconstruction high-pass filter'); xlabel(['The four filters for ' wavelet])



 



마찬가지로,,, 대부분의 정보는 왼쪽 위에 모서리에 집중되어 있다.

참고로, wfilters의 종류에 따른 웨이블릿 필터의 주파수응답(Fig2, 3)과 임펄스응답(Fig4)을 확인 할 수도 있다.