Chapter 3 Multimedia Systems Technology: Coding and Compression 멀티미디어 시스템 기술: 부호화와 압축 M. Y. Sung

3.1 개요 Large volume 해결 대역폭(bandwidth) 높이기: ~GB/sec 비트 수 줄이기: 데이터 압축(data compression) 1948, Claude Shannon: 정보이론(Information Theory)의 아버지 엔트로피(entrophy): 소스 내용의 정보량을 측정 통신 시스템 모델 정보를 효율적으로 전송  압축(compression) 소스 부호화(source coding) 신뢰성 있는 통신  오류 제어(error control) 채널 부호화(channel coding) M. Y. Sung

M. Y. Sung

3.1 개요 압축(compression) 감지의 질(perceptual quality)을 유지하면서 비트 수가 최소가 되게 부호화(coding) 무손실 부호화(lossless coding): 완벽한 복원(decoding) computer program, data, medical imaging 손실 부호화(lossy coding): 정보 손실 있으나 지각의 질은 그대로 audio, video 부호화(coding)와 복호화(decoding)에 걸리는 시간이 최소가 되게 코딩 체계 설계 압축의 조건(constraints) (예) Videoconferencing Delay: 150 ms 이하 Compression과 Decompression 시간:50 ms 이하 (예) Retrieval based 응용: on-demand video services 임의 접근 시간: 500 ms 이내 M. Y. Sung

3.2 이미지 압축 데이터 중복성(redundancy) 공간 중복성 (Spatial redundancy, statistical redundancy): 이웃하는 픽셀 사이 스펙트럼 중복성 (Spectral redundancy): 색상 요소 사이 정신 시각적 중복성 (Psycho-visual redundancy): 눈의 감지 특성 이미지 압축 시스템 변환기(Transformer): 입력 이미지 데이터  압축 이미지 표현 (Lossless) 양자화기(Quantizer): 압축 표현에 이용되는 제한된 심볼들 생성 (Lossy) Scalar quantization: element 단위 Vector quantization: block 단위 부호화기(Coder): 각 심볼에 코드(bits-stream)를 할당 (Lossless) FLC(Fixed Length Coding) VLC(Variable Length Coding): entrophy coding(최소 비트 할당) 압축 방법 Lossless: 이미지의 정확성이 중요한 medical imaging Lossy 주어진 비트울(bit-rate)에서 가능한한 신뢰성 있게 주어진 신뢰성을 보장하는 한도 내에서 비트율을 최소로 M. Y. Sung

M. Y. Sung

3.3 압축 기술의 용어정리(Taxonomy) 부호화(Encoding)의 분류 엔트로피 코딩(Entrophy coding): Lossless 모든 데이터를 비트의 연속으로 간주 정보의 의미(semantics) 무시 소스 코딩(Source coding): Lossless or Lossy 원래 신호의 타입을 고려 엔트로피 코딩 보다 더 많이 압축 실제로, 엔트로피 코딩 + 소스 코딩 M. Y. Sung

엔트로피 측정 엔트로피 물리학: 입자들의 무질서도 정보이론: 정보의 양 메시지 mi의 정보내용 Ii Ii =log(1 / Pi ) (비트) Pi : mi의 발생확률 신호원의 엔트로피 H(m) = n i=0 Pi Ii (비트) n i=0 Pi log(1 / Pi ) = - n i=0 Pi log Pi (비트) 모든 메시지가 같은 발생 확률을 가질 때 엔트로피는 최대가 됨 M. Y. Sung

3.4 엔트로피 코딩 기술 실행-길이 코딩 (Run-length Coding) (c1, l1), (c2, l2), ... (ck, lk)로 이미지 요소 표현: cㅑ: color, li: length (예) 11111111111333333333322222222211111 (1,11), (3,10), (2,9), (1,5) 반복 제거 (Repetition Suppression) 특정 문자를 특수 글자(flag)과 반복 회수로 표현 (예) 98400000000000000000000000000000000 984f32 패턴 대치 (Pattern Substitution) 자주 반복되는 패턴을 어떤 코드로 대치 교재 p82-83 예 허프만 코딩 (Huffman Coding) 문자 발생 빈도수에 기반: 자주 나오는 문자에 적은 수의 비트 할당 p83 codebook 예 M. Y. Sung

M. Y. Sung

M. Y. Sung

이진 트리 형태의 허프만 코딩 발생확률 p(A)=0.16 p(B)=0.51 p(C)=0.09 p(D)=0.13 p(E)=0.11 코드 w(A)=001 w(B)=1 w(C) =011 w(D)=000 w(E)=010 P(ADCEB) =1.00 P(ADCE) =0.49 P(B) =0.51 P(CE) =0.20 P(AD) =0.29 P(C) =0.09 P(E) =0.11 P(D) =0.13 P(A) =0.16 1 M. Y. Sung

3.5 소스 코딩 기술 소스 코딩 의미 기반 코딩(semantic-based coding) lossless or lossy 소스 코딩 종류 변환 코딩 (Transform Encoding) 퓨리에 변환 (FFT, Fast Fourier Transform) 이산 여현 변환 (DCT, Discrete Cosine Transform) 차분 코딩 (Differential Encoding) 차분 펄스 코드 변조 (DPCM, Differential Pulse Coded Modulation) 델타 변조 (DM, Delta Modulation) 적응적 ADPCM (Adaptive DPCM) 벡터 양자화 (Vector Quantization) M. Y. Sung

M. Y. Sung

3.5 소스 코딩 기술 변환 코딩 (Transform Encoding) 공간/시간 도메인을 주파수 도메인(frequency domain)으로 이미지의 스펙트럼 표현(spectral representation)은 색상과 휘도의 변화를 빠르게 파악할 수 있게 함 DC(Direct Current) 요소와 저주파수 AC(Alternating Current) 요소들이 원래 이미지 신호에 대한 정보를 가장 많이 포함 처음 k 개 AC 계수(coefficient)만 사용(k는 응용에 따라 다름) 주요 계수(the most significant coefficients)는 더 정밀하게 코딩 DCT: JPEG, DCT 계수 생성 M. Y. Sung

3.5 소스 코딩 기술 차분 코딩 (Differential Encoding) DPCM (Differential Pulse Code Modulation) 예측 값(predicted value) 과의 차이를 코딩 fpredicted(ti) = factual(ti-1) f(ti) = factual(ti) - factual(ti-1) Delta Modulation DPCM과 유사하나 차분 오류를 단일 비트 또는 숫자로 표현 현 샘플이 한 단계 증가되었는지 한 단계 감소되었는지를 코딩 ADPCM (Adaptive DPCM) 시변 함수(time-varying function)를 이용하여 예측 값을 외삽(extrapolation) 다양한 예측 함수(prediction function) 이용 M. Y. Sung

M. Y. Sung

DPCM 부호화/복호화 예 6 비트 크기(-16 ~ +15) DPCM 경우 (a)부호화 이전의 데이터 14 19 25 36 43 55 66 52 48 34 (b) DPCM부호화 데이터 +14 +5 +6 +11 +7 +12 +11 -14 +4 -14 (c)복원된 데이터 M. Y. Sung

ADPCM 부호화/복호화 예 (a)부호화 이전의 데이터 18 35 53 68 88 65 42 28 48 67 18 35 53 68 88 65 42 28 48 67 (b)DPCM부호화 데이터 +15 +15 +15 +15 +15 -10 -15 -15 +13 + (c)복원된 데이터(DPCM시) 15 30 45 60 75 65 50 35 48 63 (스케일 변화정보) ×2 ×2 ×2 ×1 ×2 ×2 ×2 ×1 ×2 +15 +10 +9 +7 +15 -8 -12 -7 +15 +12 (b) DPCM부호화 데이터 +15 +20 +18 +14 +15 -16 -24 -14 +15 +24 (c)복원된 데이터 15 35 53 67 82 66 42 28 43 67 M. Y. Sung

DM(Delta Modulation) 부호화/복호화 예 16 =LDM 16 24 36 24 36 24 36 24 =LADM 16 40 89 75 24 32 66 19 (a) 부호화 이전의 데이타 + + + + - - + - (b) DM으로 부호화된 데이타 16 32 48 64 48 32 48 32 (c) DM으로 복원된 데이타 + + + - - + + - (d) ADM으로 부호화된 데이타 16 40 76 52 16 40 76 52 (e) ADM으로 복원된 데이타 DM코드화와 ADM코드화의 비교 : LDM =LADM = 16, p = 3/2, q = 2/3인 경우의 ADM코드화와 DM코드화의 예를 나타내고 있다. (a)의 데이터는 DM을 통해(b)와 같이 부호화되고 (c)와 같이 복원된다. 이때, LDM 은 변하지 않는다. (d)는 ADM을 이용하여 부호화된 데이터를 , (e)는 ADM을 이용하여 복원된 데이터를 나타낸다. 정보의 배열에 따라 LADM 의 크기가 동적으로 변화된다. ADM ++, -- L = L × p -+, +- L = L × q M. Y. Sung

3.5 소스 코딩 기술 벡터 양자화 (Vector Quantization) 입력 데이터를 블록(vector; 예, 2x2 pixels)으로 나눔 블록의 형태에 대한 codebook과 position index 필요 이미지의 각 벡터를 가장 잘 매치되는 codebook의 code로 표현 (교재 p88 Fig.3.5 참조) 일치하는 코드가 없는 경우 근접 패턴으로 코딩  decoding 시 왜곡(distortion) 생김 error(codebook 항목과 이미지 벡터와의 차이)의 양자화 레벨과 error 전송 여부에 따라 lossless lossy 다양한 실제 이미지 벡터에 근접하는 codebook 생성 가능 speech 코딩에 좋음 최적 codebook 생성과 최적 패턴 매치 검색 알고리즘 연구 필요 M. Y. Sung

M. Y. Sung

3.6 이미지 압축 시스템 이미지 압축 시스템: 아날로그 형태  디지털 형태 부호화기 (Encoder) 복호화기 (Decoder) Encoder Phase I: 영상 준비 과정 (Picture Preparation Phase) 샘플링, 픽셀들을 블록으로 Phase II: 영상 처리 (Picture Processing) 손실 소스 코딩, DCT Phase III: 양자화 (Quantization) 계수들을 정수로 (계수의 중요도에 따라 양자화 레벨 다르게) Phase IV: 엔트로피 코딩 (Entrophy Coding) 디지털 데이터 스트림을 무손실 코딩 Adaptive compression schemes: Phase II와 Phase III 반복 Decoder: Encoder의 역(inverse) 과정 symmetric: 압축 시간과 복원 시간이 같음, 화상회의 등 대화형(interactive) 응용 asymmetric: 압축 시간과 복원 시간이 다름, 시청각 학습 프로그램 등 프레젠테이션 응용 M. Y. Sung

M. Y. Sung

M. Y. Sung

M. Y. Sung

3.7 압축 시스템 표준 JPEG: ISO & IRU-TS, still image MPEG: IEC/JTC1/SC29/WG11, video & audio H.261: Study Group XV, Video Coded for Audiovisual Services at px64 Kbps ITU-TS H.263: videophone ISO JBIG: bilevel image DVI: Intel de facto standard, presentation (cf. 용어) 법적 표준 (de jure) & 업계 표준 (de facto) M. Y. Sung

3.8 JPEG Joint Photographic Experts Group: Continuous tone (multilevel) still images 압축 국제 표준 (1992) 공간 중복성(spatial redundancy) 제거: 질 손상 없이 1/10 ~ 1/50 압축 응용: photovideotex, color facsimile, medical imaging, desktop publishing, graphics arts, newspaper wire photo transmission 요구사항 부호화기는 매개변수화(parametraizable)되어야 함 어떤 종류의 continuous tone digital image에도 적용 가능해야 함 CPU와 특수 하드웨어에서 구현 가능하도록 계산 복잡도가 제어 가능해야 함, 압축은 실시간에 완료되어야 함 높은 성능을 요구하는 응용에 대해서도 하드웨어 상에서 적절한 가격으로 구현 가능해야 함 아래의 모드를 제공해야 함 Progressive encoding: multiple scans, image build up in multiple coarses Losless encoding Hierarchical encoding: multiple resolutions M. Y. Sung

3.8 JPEG JPEG 압축 (compression) 과정 데이터 블록 준비(Preparation of Data Blocks) 소스 인코딩 단계 (Source Encoding step) 이산 여현 변환 (Discrete Cosine Transform, DCT): Forward DCT 양자화 (Quantization) 엔트로피 인코딩 단계 (Entrophy Encoding step) 실행 길이 코딩 (Run Length Coding) 허프만 또는 산술적 코딩 (Huffman or Arithmetic Coding) JPEG 복원 (decompression) 과정 엔트로피 디코딩 단계 (Entrophy Decoding step) 소스 디코딩 코딩 (Source Decoding step) 역 양자화 (Dequantization) 역 이산 여현 변환(Inverse Discrete Cosine Transform, IDCT) M. Y. Sung

M. Y. Sung

M. Y. Sung

3.8 JPEG DCT 기반 코딩의 2 모드 순차 모드(Sequential mode): 8x8 block by block left-to-right, block-row by clock-row tom-to-bottom 순으로 FDCT & Quantizing  64개 DCT 계수들을 즉시 entrophy encoding (코딩된 순서대로 보여줌) 점진적 모드(Progressive mode): 같은 순서로 처리  64개 DCT 계수들을 Quantizer와 Entrophy encoder 사이에 image-sized coefficient memory buffer 더하고 이 곳에 저장  매 다중 스캔(multiple scans) 마다 부분적으로 entrophy encoding (silhouette먼저 보여 주고 점진적으로 세밀하게 보여 줌) 데이터 블록 준비 (Preparation of Data Blocks) 순차 손실 모드 (Sequential lossy mode): 8x8 sampled values (예) VGA standard: 640x480 image, YUV=4:1:1 sub-sampling  4800 blocks (Y) + 1200 blocks (U) + 1200 blocks (V) M. Y. Sung

M. Y. Sung

3.8 JPEG Forward Discrete Cosine Transform 64개 점을 아래와 같이 표현 f(x,y), 0  x  7, 0  y  7, x와 y는 공간 도메인 DCT 가 64 개의 점을 주파수 도메인에 아래와 같이 변환 c=g(Fu, Fv), c는 계수, Fu와 Fv는 아래의 변환식으로 구한 공간 주파수 0  x  7, 0  y  7 에 대하여 F(u,v)=0.25*C(u)*C(v)*7x=0 7y=0f(x,y)*cos(((2x+1)*u*)/16)*cos(((2y+1)*v*)/16) u, v = 0 일 때, C(u) = C(v) = 1/ (21/2) 이외의 경우, C(u) = C(v) = 1 DCT 계산 결과 64 개 DCT 계수 생성 DC(Direct Current) 계수: vector (0,0) 계수 AC(Alternating Current) 계수: 나머지 vector들 많은 계수들이 0또는 0에 근접한 값을 가짐  코딩 않음 복호화기(decoder)에서는 IDCT(Inverse DCT)로 원래 값 복원 M. Y. Sung

3.8 JPEG 직관(Intuition)적 해석 이미지의 각 샘플 값은 약간씩 변화하므로 낮은 주파수의 계수가 크고 높은 주파수의 계수는 작음: 신호 에너지가 낮은 공간 주파수에 몰려 있음 (예) 단색 벽 이미지 이웃하는 픽셀 사이의 신호의 진폭은 거의 같으므로 x, y 각 방향으로 변화가 거의 없음: 주파수 0가 크고 나머지 주파수는 거의 0일 것임 주파수(frequency): x, y 축에서의 변화율 (예) 가는 흑색 라인 이미지 어떤 블록은 영향 없고, 영향 있는 블록에서 이웃하는 값이 크게 변할 것임: 높은 주파수 중 하나의 계수가 클 것임 일반적으로, continuous-tone image에는 가는 선이 거의 없을 것이므로 저주파수에 많은 정보가 들어 있게 됨  JPEG의 기본 전제 DCT 자체는 lossless, DCT 계수 양자화 과정은 lossy M. Y. Sung

3.8 JPEG 양자화 (Quantization) fundamentally lossy: many-to-one mapping 각 DCT 계수를 해당되는 양자화 테이블의 해당 행력 값으로 나눔 FQ(u,v) = IntegerRound(F(u,v)/Q(u,v)) (양자화 계수 테이블 예) Quantum(i,j)=4+3*(i+j) DC 계수: 64 이미지 샘플의 평균, 앞 블록 DC 계수와의 차를 코딩, 이미지 에너지의 중요부분 포함 Zig-Zag sequencing: 낮은 주파수의 계수가 높은 주파수의 계수보다 먼저 나오게, 하여 인접하는 0의 개수 늘임 엔트로피 코딩 (Entrophy Coding): lossless DC 계수 코딩 Symbol1=비트 수(허프만 테이블의 가변길이 코드), Symbol2=값 자체(가변길이 정수코드) (예) =1023, symbols1=1010 (10D), Symbol2=1111111111 AC 계수 코딩 zig-zag sequence를 intermediate symbol sequence로 Symbol1=(실행길이, 크기), Symbol2=AC 계수 값 자체 (예) 44 7 12 18 7 3 3 5 2 0 0 5 3 2 0 2 2 0 0 … 0  (0,44), (0,12), (0,18), (1,7), (0,3), (0,3), (0,5), (0,2), (2,5), (0,3), (0,2), (1,2), (0,2) intermediate symbol을 data stream으로 Symbol1: 수정 허프만 테이블의 가변길이 코드, Symbol2: 가변길이 정수 코드 M. Y. Sung

M. Y. Sung

M. Y. Sung

Custom quantization tables can be put in image/scan headers. Example of the luminance quantization table is shown in Figure 6. (from ‘JPEG: Still Image Data Compression Standard’, Pennebaker, Mitchell, Van Nostrand Reinhold Publisher, 1993). 16 11 12 14 12 10 16 14 13 14 18 17 16 19 24 40 26 24 22 22 24 49 35 37 29 40 58 51 61 60 57 51 56 55 64 72 92 78 64 68 87 69 55 56 80 109 81 87 Fig. 6 95 98 103 104 103 62 77 113 121 112 100 120 92 101 103 99 Eye is most sensitive to low frequencies (upper left corner), less sensitive to high frequencies (lower right corner). Custom quantization tables can be put in image/scan headers. M. Y. Sung

Quantization Tables (cont.) Example of the luminance quantization table (from ‘JPEG: Still Image Data Compression Standard’, Pennebaker, Mitchell, Van Nostrand Reinhold Publisher, 1993). 16 11 12 14 12 10 16 14 13 14 18 17 16 19 24 40 26 24 22 22 24 49 35 37 29 40 58 51 61 60 57 51 56 55 64 72 92 78 64 68 87 69 55 56 80 109 81 87 95 98 103 104 103 62 77 113 121 112 100 120 92 101 103 99 Eye is most sensitive to low frequencies (upper left corner), less sensitive to high frequencies (lower right corner). Custom quantization tables can be put in image/scan headers. M. Y. Sung

136 138 140 144 145 147 155 140 140 147 140 148 155 156 143 144 148 150 152 154 155 144 146 145 149 150 153 160 152 155 156 150 145 144 140 145 146 148 143 158 150 140 156 157 156 140 146 156 145 145 146 148 156 160 140 145 88 image block pixmap DCT하기에 앞서 각 화소값에서 [ 2p-1 ] ( p는 화소정밀도 레벨)만큼을 뺀 다음에 계산하여야 함 여기서 p=8, 28-1=128 M. Y. Sung

(2) DTC coeffecient -18 15 -8 23 -9 14 19 21 -34 24 -8 10 11 14 7 -18 15 -8 23 -9 14 19 21 -34 24 -8 10 11 14 7 9 -8 -4 6 -5 4 3- -1 10 6 -5 4 -4 4 2 1| 8 -2 -3 5 -3 3 4 6 4 -2 -4 6 -4 4 2- -1 4 -3 -4 5 6 3 1 1 0 -8 -4 3 2 1 4 0 (2) DTC coeffecient M. Y. Sung

4 7 10 13 16 19 22 25 7 10 13 16 19 22 25 28 13 16 19 22 25 28 31 16 19 22 25 28 31 34 19 22 25 28 31 34 37 22 25 28 31 34 37 40 25 28 31 34 37 40 43 25 28 31 34 37 40 43 46 (3) Quantization Table 양자화 계수(i, j) = 4 + 3(i + j) M. Y. Sung

-3 2 0 0 0 0 0 3 -3 2 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (4) Quantized Coef M. Y. Sung

Difference Encoding applied to DC coefficients PREDICTOR Diffi = DCi - DCi-1 i>0 DC0 DC1 DC2 DC3 DC4 DC5 DC6 DC7 DC8 DC0 Diff1 Diff2 Diff3 Diff4 Diff5 Diff6 Diff7 Diff8 Difference Encoding applied to DC coefficients M. Y. Sung

DC 계수 인코딩 테이블 차분 DC 계수값 해당 비트 길이 비트 길이의 BCD 표현 0 0 0000 ±1 1 0 001 0 0 0000 ±1 1 0 001 ±2∼3 2 0010 ±4∼7 3 0011 ±8∼15 4 0100 ±16∼31 5 0101 ±32∼63 6 0110 ±64∼127 7 0111 ±128∼255 8 1000 ±256∼511 9 1001 ±512∼1023 10 1010 M. Y. Sung

3.8 JPEG 압축과 이미지의 질: 교재 p101 Table 3.2 참조 수신측 처리: step size 곱해서 정규화(normalized) 해제한 후 IDCT에 입력 FQ’(u,v) = FQ(u,v)*Q(u,v)) f(x,y)=0.25*7x=0 7y=0C(u)*C(v)*F(x,y)*cos(((2x+1)*u*)/16)*cos(((2y+1)*v*)/16) u, v = 0 일 때, C(u) = C(v) = 1/ (21/2) 이외의 경우, C(u) = C(v) = 1 연산의 계층적 모드 (Hierarchical Mode of Operations) frame의 연속으로 코딩 down-sampling(low-pass filtering & sub-sampling)  작은 이미지부터 해상도를 증가시키면서 코딩 (교재 p102 Fig.3.14 참조) M. Y. Sung

M. Y. Sung

3.8 JPEG 다중-요소 이미지 (Multiple-Component Images) 1~ 255 이미지 요소: 색상, 스펙트럼 밴드(spectral bands), 채널(channel).. 모든 샘플은 정밀도가 p 비트인 부호 없는 정수 [0, 2p - 1] DCT 기반 코딩: p=8 또는 p=12 예측 코딩(Predictive coding): 2  p  6 component Ci는 샘플 차원(sample dimension) xi * yi 가짐 Hi : Horizontal sampling factor, 1  Hi  4 Vi : Vertical sampling factor, 1  Vi  4 X: 최대 xi Y: 최대 yi xi = X * Hi / Hmax yi = Y * Vi / Vmax M. Y. Sung

M. Y. Sung 256 256

Image Preparation (Components and Resolution) A./Components with the same resoltion X1 X2 X3 A1 A2 An B1 B2 Bn C1 C2 Cn = X2 = X3 X1 Y1 Y2 Y3 = Y2 = Y3 Y1 B./Components with different resolution X1 X2 X3 = 2X2 = 2X3 X1 = Y2 = Y3 Y1 A1 A2 An B1 B2 Bn C1 C2 Cn Y1 A gray scale will have single component RGB will have 3 equal components YUV color image processing will use: Y2 Y3 = 4X2 = 4X3 X1 = 4Y2 = 4Y3 Y1 M. Y. Sung

Components and their Resolutions Level 0: Level 1: Level 2: H0 = 2 (X = 6) H1 = 2 (X = 6) H2 = 1 (X = 6/2 ) V0 = 2 (Y= 4 ) V1 = 1 (Y = 4/2 ) V2 = 1 (Y = 4/2 ) C0 0 1 2 3 4 5 C2 C1 * 1 2 3 * * M. Y. Sung

3.8 JPEG 부호화 순서와 다중-요소 이미지의 인터리빙 (Encoding Order and Interleaving for Multi-Component Images) MCU (Minimum Coded Unit): 최대 10개 데이터 원소 포함 최대 4 개 요소(components)까지 인터리빙 됨 교재 p104 Fig.3.16 참조 다중 테이블 이용 다중-요소와 인터리빙 포함할 경우 적절한 데이터 테이블 필요 같은 요소 안에 있는 모든 샘플에 대하여 같은 양자화 테이블 및 엔트로피 코딩 테이블을 적용해야 함 JPEG decoder는 최대 4개 양자화 테이블을 저장할 수 있음 기타 JPEG은 성공적인 JPEG 이미지 교환(exchange)을 위하여 interchange format syntax를 정의 M. Y. Sung

M. Y. Sung

Image Preparation (MCU Examples) Consider example of 4 components C1, C2, C3, C4 C1 : H1=2, V1=2; C2 : H2=2, V2=1; C3 : H3=1, V3=2; C4 : H4=1, V4=1 as shown in Figure of the next slide The considered individual elements dki of components Ci for building our MCUs are denoted as follows: C1:d001 d011 d021 d031 d041 d051 d101 d111 d121 d131 …… d341 d351 C2:d002 d012 d022 d032 d042 d052 d062 d072 d082 d092 …… d142 d152 C3: d003 d013 d023 d103 d113 d123 d203 d213 d223 d303 d313 d323 C4: d004 d014 d024 d104 d114 d124 The resulting MCUs are: MCU1: d001 d011 d101 d111 d002 d012 d003 d103 d004 MCU2: d021 d031 d121 d131 d022 d032 d013 d113 d014 MCU3: d041 d051 d141 d151 d042 d052 d023 d123 d024 MCU4: d201 d211 d301 d311 d102 d112 d203 d303 d104 M. Y. Sung

C1 C2 C3 C4 d00 MCU1 MCU4 MCU2 MCU3 d10 Components for MCU Example 1 0 1 2 3 4 5 3 2 C2 C3 C4 C1 MCU1 MCU4 MCU2 MCU3 0 1 2 d10 4 M. Y. Sung Components for MCU Example

M. Y. Sung

3.9 JBIG Images Bitonal(black & white) & grey-scale: JBIG (Joint Bi-level Image Group) Continuous-tone: JPEG (Joint Photographic Experts Group) 무손실 예측 기법(lossless predictive methods) ISO/IEC standard 11544:1993 : 압춛 쳬계(compression scheme)만 정의 JBIG Interchange Recommendation: JBIG 압축 데이터를 TIFF(Tagged Image File Format)로 저장하는 방법 정의 특징 점진적(progressive)/순차(sequential) coding 호환: 점진적으로 코딩된 이미지가 순차적으로 복원될 수 있음 무손실 픽셀 당 비트수: 1 ~ 255, 8 이상의 경우 다른 알고리즘이 더 효율적 X-rays(픽셀 당 12 비트 이용하고 변형, distortion 불허) 등의 medical imaging에 이용 데이터 준비: an image  bit planes  resolution layers (base leyer & differential layers) stripes  bi-level bitmaps Q-coder(Huffman coder와 유사)로 압축 M. Y. Sung

3.10 MPEG Moving Picture Experts Group 다수의 압축된 오디오와 비디오 비트-스트림을 하나의 비트-스트림으로 결합 데이터 스트림 문법(data stream syntax) 정의 적시성 제어 (timing control) 오디오와 비디오 비트-스트림의 인터리빙 오디오와 비디오 비트-스트림의 동기화 MPEG 비트-스트림:교재 p116 Fig.3.22 참조: pack(packet들로 구성) 시스템 계층(system layer): 인터리빙된 데이터를 demultiplexing하기 위한 제어 정보 제공 압축 계층(compression layer): 데이터 STD(System Target Decoder): 이상적인 디코더 pack과 packet의 헤더를 해석하여 오디오와 비디오 디코더에게 기본 비트-스트림(elementary bit-stream)을 전달 DTS(Decoding Time Stamp)가 지시하는 시간에 버퍼로부터 하나의 access unit(picture 또는 audio acess unit)의 비트들이 디코딩됨 PTS(Presentation Time Stamp)에 의해 오디오와 비디오 디코딩의 동기화가 제어됨 M. Y. Sung

M. Y. Sung

3.10 MPEG MPEG 오디오 압축 32, 44.1 48 KHz 지원, 16 비트 양자화하면 1.5 Mbps 요구 압축 후 monophonic channel: 32 ~ 192 Kbps Stereophonic channel: 128 ~ 384 Kbps 384 샘플 윈도우로 세그먼트화하여 750 Hz 넓이의 32 개 sub-band로 filtering (각 샘플 윈도우 당 750 x 32 x 2 = 48 KHz sampling rate)  다시 각 sub-band 당 1.5 KHz sampling rate, 각 윈도우(sub-band) 당 12 샘플로 간축화(32:1 decimated) FFT(Fast Fourier Transform)로 각 sub-band의 global masking threshold(청각 심리 모델을 이용한 최소 가청 한계) 계산 임계 대역(critical banf): masking 효과가 일어나는 주파수 폭 M. Y. Sung

Figure 12: MPEG Audio Encoding Steps. amplitude Strong tonal signal Region where weaker Signals are masked frequency Figure 12: MPEG Audio Encoding Steps M. Y. Sung

Masking Threshold Curves Masking Curves 250Hz 500Hz 1kHz 2kHz 4kHz 60dB Critical Band Rate Masking Threshold Curves M. Y. Sung

그림 8-2 청각이 감지할 수 있는 최소 레벨과 주파수 포인트 1 고요할 때의 최소가청한계는 주파수에 의존 청각이 감지할 수 있는 최소 레벨의 음 2 120 80 압 음 (dB) 그림에 나타나 있는 것처럼,고요할 때 인간의 귀는 음의 주파수(음의 높낮이)에 따라 최소가청한계가 달라집니다. 들리는 부분 고요할 때의 최소가청한계 B A 40 들림 들리지 않는 부분 들리지 않음 20 40 100 200 400 1k 2k 4k 10k 20k 주파수[Hz] 그림 8-2 청각이 감지할 수 있는 최소 레벨과 주파수 M. Y. Sung

그림 8-3 마스킹 효과 포인트 1 2 마스킹 효과와 가청한계 마스킹 효과와 크리티컬 밴드 120 마스킹 효과와 가청한계 마스킹 효과와 크리티컬 밴드 1 2 120 조용한 환경에서는 잔잔한 음이 들리지만 폭풍이 일면 그것은 들리지 않는다. 이것을 “마스킹 효과”라 하는데 이때 마스킹하는 음을 ‘마스커’ 마스킹되어 들리지 않는 음을 ‘마스키’라 합니다. 들림(마스커) A 80 음 들리지 않 음(마스키) 마스킹 효과 압 들림 (dB) B C 크리티컬 밴드 (임계대역) 40 들리지 않는 부분 200 400 1k 2k 4k 주파수[Hz] 그림 8-3 마스킹 효과 M. Y. Sung

그림 8-4 크리티컬 밴드(임계대역) 포인트 1 2 [Hz] 크리티컬 밴드(임계대역) 마스커나 마스키의 주파수에 따라 다르게 된다. 2 주파수에 따른 크리티컬 밴드 폭의 변화 4k 120 주파수 1kHz 이상에서는, 주파수와 크리티컬 밴드 폭은 비례합니다.그림은 대수표시이기 때문에 마스킹 효과의 그래프는 대략 같은 모양으로 보입니다. 2k 1k 크리티컬 밴드 폭 400 80 음 200 100 압 100Hz 100Hz (dB) [Hz] 마스킹 효과 40 100Hz 20 40 100 200 400 1k 2k 4k 10k 20k 주파수[Hz] 그림 8-4 크리티컬 밴드(임계대역) M. Y. Sung

} { 시간적 마스킹 효과 마스커와 마스키의 시간차가 짧은 경우 1 포인트 2 120 80 압 음 (dB) 40 압 음 (dB) 40 2 시간적 마스킹 효과 50 시간[ms] 작은 음 시간적 마스킹 효과에 의해, 큰 음 바로 위에 작은 음을 내도 들리지 않는 것을 “전향성 마스킹”이라 합니다. 흥미로운 것은,큰 음 직전에도 시간적 마스킹 효과가 있어 작은 음은 들리지 않는다는 것입니다. 큰 음 (마스커) 들리지 않는 부분 들리지 않음(마스키) } 전향성 마스킹 들리지 않음 (마스키) 후방성마스킹 { 시간적 마스킹 효과 마스커와 마스키의 시간차가 짧은 경우 M. Y. Sung

3.10 MPEG MPEG 비디오 압축 오디오와 비디오 신호를 채널 당 1.5 Mbps로 압축 압축된 오디오와 비디오의 동기화와 멀티플렉싱 지원 asymmetrical: 복원보다 압축에 더 많은 계산 필요 비디오 프레임들 사이의 시간 중복성(temporal redundancy) 및 비디오 프레임 내부의 공간 중복성 제거 GOP(Group pf Pictures): 시간 중복성 제거와 임의 접근(random access) 지원 위해 프레임 형태 Intra pictures (I-Frame): 각 GOP의 첫번 프레임, 임의 접근 지점, 자체가 DCT 인코딩 됨, JPEG 이미지에 해당 Predicted picture (P-Frame): I 또는 P-Frame으로부터 전방으로(forward) 움직임 보상된 예측 오류(motion-compensated prediction errors)가 DCT 인코딩 됨 Bi-directional (interpolated) pictures (B-Frames): I 또는 P-Frame으로부터 양방으로(bi-directional) 움직임 보상된 예측 오류가 DCT 인코딩 됨 D-pictures: 각 블록의 DC 요소만 저장 M. Y. Sung

M. Y. Sung

M. Y. Sung

3.10 MPEG 움직임 보상(Motion Compensation) 예측법(prediction): 과거 영상으로부터 현재 영상을 추측 보간법(interpolation): multi-resolution technique, 낮은 시간 해상도(frame rate) 를 코딩하고 이로부터 높은 해상도의 신호를 보간법으로 구하고 수정 항목(correction term)을 더함, 과거와 미래의 영상을 결합하여 움직임 보상 움직임 표현(Motion Representation) 16x16 Macro block 단위로 코딩 움직임 측정(Motion Estimation) 비디오 프레임들로부터 움직임 정보를 추출하는 것 Block matching: mismatch 비용을 최소화 해야 함 MPEG 문법(syntax): 특정 응용의 고유한 기능들을 배려한 계층적 구조와 비트-스트림을 정의 계층적 구조: 교재 p113 Table 3.3 참조 비트-스트림(Bit-stream): bit(binary digits)들의 연속 M. Y. Sung

(1) Inter-frame 예측 (2) motion vector 와 움직임보상 프레임간 예측(옵션) 포인트 움직임 벡터 (이동량) 시간의 진행방향 프레임1 시각t1에 원 매크로블록이 있던 위치 그림 5-4 움직임 벡터의 예 프레임2  시각 t1에 있어서 이동 매크로블록 (시각 t2) 검색범위 (시각 t1) 프레임간 프레임 1(시각 t1)과 프레임 2(시각t2)에서 비행기의 이동을 XY이차원좌표상의 이동량으로 표시한 것을 “움직임 벡터”라고 합니다. M. Y. Sung

Figure 3: Individual compression steps for P-frames. 차분 현재 화면 매치 윈도우 허프만 부호기 차분 0100110 참조 화면 (이전 화면) 움직임 벡터 M. Y. Sung

Figure 7: B-frame Compression 뒷 화면 참조 현재 목표 화면 - [ 1 / 2 ( + ) ] = 앞 화면 참조 DTC + 정량화 +RLE 움직임 벡터 (2개) 허프만 부호기 0001110… Figure 7: B-frame Compression M. Y. Sung

M. Y. Sung

3.10 MPEG MPEG 시스템 MPEG의 3 부분 video coding audio coding system coding: system multiplexer와 동기화된 MPEG 스트림을 생성하는 encoder 정의 시스템 코딩의 목적 멀티플렉싱 입력 데이터 스트림과 출력 데이터 스트림의 제어(coordination) VPU(Video Presentation Unit): uncoded digitalized picture in units  coded VAU(Video Access Unit): elementary stream APU(Audio Presentation Unit): uncoded digitalized audio samples  AAU(Audio Access Unit): elementary stream 클록 조절(adjustment of clocks) 버퍼 관리 임의 접근 후 멀티플렉스된 스트림을 파싱(parsing) 디코더에 있는 코드화된 정보 버퍼(coded information buffer)를 관리 코드화된 정보 버퍼의 절대 시간을 식별 M. Y. Sung

M. Y. Sung

3.10 MPEG MPEG 시스템 적시성과 동기화(Timing and Synchronization) 하나의 공통 시스템 클록(common system clock)이 생성하는 타임 스탬프(time stamp)로 정확한 프레젠테이션 시간, 디코딩 시간, 시스템 클록 자체의 값 표시 PTS(Presentation Time Stamps) DTS(Decoding Time Stamps) STR(System Clock Reference) 디코딩 sample rate는 인코딩 sample rate와 정확하게 같다고 전제하므로 정확한 동기화를 위해서는 일정한 지연시간(constant delay)이 요구됨 디코딩 시스템에는 동기화를 위해 time master가 필요하며 다음 중 하나로 설정될 수 있음 decoder information stream source external time base M. Y. Sung

M. Y. Sung

3.10 MPEG MPEG 시스템 MPEG 스트림 MPEG 스트림 생성의 가장 중요한 기능 = 멀티플렉싱 입력 데이터 스트림과 출력 데이터 스트림의 제어(coordination) 클록 조절(adjustment of clocks) 버퍼 관리 3 코딩 계층(coding layers) stream layer pack layer: zero or more packets, SCR 값 포함, 자원 예약 정보 포함(첫번 pack에 최대 data rate) packet layer: elementary streams로부터 실제 데이터 전송, 각 packet 당 한 elementary stream MPEG 디코딩 과정(decoding process) MPEG은 디코더가 아니고 디코딩 과정 정의 비트-스트림 디멀티플렉싱  motion information, quantizer step size, macroblock type, quantized DCT coefficients등의 정보로  quantized input to IDCT  움직임 보상 위해 예측 결과에 더해짐(양방향 예측 위해 두 개의 참조 영상 이용) decoded data 교재 p118 Fig.3.23 참조 M. Y. Sung

M. Y. Sung

3.10 MPEG MPEG-2, MPEG-3, MPEG-4, MPEG-7 MPEG-1: 1993, 1.5 Mbps 이하, VTR(SIF) 영상, Video CD, 2 채널 스테레오 MPEG-2: 1995, Laser Disc 급 이상의 고화질 비디오, 4~80Mbps, HDTV, DVD 등 방송용, 5 채널 입체 음향 MPEG-4: 1999, 오디오비주얼 프로그램의 고 압축율, 저전송율 코딩, 24 kbps~2Mbps, 객체 지향 부호기법, 이동 비디오 전화, 멀티미디어 데이터베이스 MPEG-7: 내용 기반 검색(content base retrieval)이 필요한 응용, 설명기법과 색인 기술 집합의 표준화, 색인정의언어 표준화, 색인의 코딩방식 표준화, 현재 연구 중 M. Y. Sung

3.11 H.261 ISDN(Integrated Services Digital Network) at px64 Kbps (p=1,…,30) 상에서 Videoconferencing과 videophone 서비스를 위한 비디오 압축 표준 videoconferencing: p>6, 384 Kbps 이상, 최대 1.92 Mbps(p=30) 특징 최대 코딩 지연시간(coding delay)이150 ms, bidirectional direct video communication 저가 VLSI 구현 가능 H.261 입력 영상은 CIF(Common Interchange Format), QCIF(Quarter CIF)로 표현 가능 CIF: Y:C=360:180, 352:176 visible lines, 288:144 active lines QCIF: Y:C=180:90, 176:88 visible lines, 144:72 active lines Videophone 서비스: 48:1 압축율과 64 Kbps 채널 필요 M. Y. Sung

3.12 H.263 MPEG-1, MPEG-2 특성 가지는 teleconferencing 응용 표준 64 Kbps에서 동작 hybrid DPCM/DCT video coding method 지원 H.261과 H.263 기술 DCT motion ompensation variable-length coding scalar quantiation macro block structure H.263의 PB 프레임 기술 P-프레임과 B-프레임의 두 프레임을 하나의 단위로 코딩 P-프레임: 이전 P-프레임으로부터 예측 B-프레임: 이전 P-프레임과 현 P-프레임으로부터 예측 압축비: H.263:H.261=2.5:1 M. Y. Sung

과제 2 : ~10월 31일 교재 p121 연습문제 1, 2, 3, 4, 5, 6 M. Y. Sung