- 1 - JPEG 1. Introduction 2. Compression Algorithm 3. Compression Process 4. JPEG Data format

Concept   JPEG (Joint Photographic Experts Group) 은 H.261( 통신미디어용 ) 과 함께 MPEG( 저장, 방송용 ) 의 기초가 되는 표준   컬러정지영상의 압축표준, 알고리즘 자체를 이름   기본방식은 ADCT(Adaptive DCT)   확장방식은 Arithmetic 코딩 을 채택   1bpp 보다 적은 bit rate 에서 화면재생을 위한 coding 가능   흑백, true color 엔 좋은 효율이나, 인위적 영상 ( 컴퓨터, 만화영화 ) 의 index color 에는 효율이 GIF 보다 못함.   평균 15:1 의 압축률 1. Introduction

Goals  Recognizable image : 0.25bit/pixel  Excellent quality image : 1.00 bpp  Almost original image : 4 bpp  Video image format in Europe (YUV)  720*576*8 bits/sample for luminance  360*576*8 bits/sample for each chrominance 1. Introduction

History   1987 년대 ISO 와 ITU-T 의 협력에 의해 개발   ISO Working group 은 주요 처리 담당   ITU-T 는 ISO 에서 개발된 JPEG 관련 팩스밀리, 비디오 텍스 같은 응용분야를 담당 1.4 Usage   전자 스틸 카메라, 영상 데이터베이스, 정지 화상 전송장치   저해상도는 표시계   고해상도는 인쇄계 등 여러 해상도에 응용 가능. 1. Introduction

영상 데이터 정보는 각각의 변화량이 적은 pixel 간의 값을 가지는데, 인간이 인식하는 것은 각 각의 pixel 값이 아닌 pixel 간의 모음이다. 이 모음에 있는 중복성 (redundancy) 을 없애 data 양을 줄 임 2.Compression Algorithm JPEG 방식 기본 방식 (Baseline) Lossless 가역방식 영상 열화를 허용하지 않는 응용 Lossy 비가역방식 DCT 방식 확장 방식 (Extended) 높은 압축률 에서도 실용적인 영상품질 공간적 (Spatial) 예측 방식

Compression Algorithm 2.1 Lossy( 비가역방식 )  10:1 ~ 40:1 의 압축률. 인간이 감지 못하는 정도의 왜곡.  Base line type( 기본방식 )  1 화소 1 색당 8 비트 할당. sequential mode, huffman coding  Extended type( 확장방식 )  1 화소 1 색당 8~12 비트 할당하여 광범위에 응용가능.  sequential mode, progressive mode, huffman coding, arithmatic coding.  Sequential mode  일반적 코딩 방식으로 DCT 에 기반한 순차 스캔.  좌상에서 우하로 block 과 line 에따라 순차적으로 부호화.  Progressive mode  저해상도 복호 영상으로 시작해 점차 해상도 높임  단시간에 큰 복호영상 얻음

- 7 - Sequential Mode Progressive Mode 2.Compression Algorithm

- 8 - Extended Type - Progressive Mode   Spectral-Selection (S-S) DCT 계수 64 개를 복수의 영역으로 분해한 후 첫 스캔에서 저주파측의 영역 을 부호화하고 차례로 나머지 영역을 부호화 저해상도 영상이 먼저 재현되고 차례로 해상도가 향상   Successive-Approximation (S-A) 각 DCT 계수의 상위 비트를 우선 전송하고 나머지 비트를 순차적으로 전송 우선 계조가 엉성한 영상이 전송되고 순차적으로 계조가 세밀 2.Compression Algorithm

Compression Algorithm

Sequential lossless mode ( 가역 방식 )   2:1 ~ 3:1 정도의 압축률, 완벽한 이미지 재생 가능.   DCT mode 에서 쓰는 DC 성분의 코딩 모델보다 확장된 코딩 기술사용.   근접한 a, b, c 값은 sample 된 x 값을 추정하는데 쓰임.   Source data 의 정밀도를 낮추고, predictor 값을 구하기 위해 point transform (2pt 로 이미지 value 를 나눔 ) 사용. 2.Compression Algorithm

Compression Algorithm

Sequential lossless mode ( 가역 방식 )   공간적 예측과 엔트로피 ( 가변장 ) 부호화   엔트로피 ( 가변장 ) 부호화 발생 확률이 높은 부호어 짧은 비트 할당 발생 확률이 낮은 부호어 긴 비트 할당 부호의 평균길이가 엔트로피 (entropy) 에 가깝게 함. 2.Compression Algorithm

원영상 양자화 엔트로피 부호화 테이블 압축데이터 2.Compression Algorithm

Hierarchical Mode ( 계측형부호화방식 )   피라미드 코딩이라고도 함   하나의 영상 file 에 여러 해상도 갖는 동일 영상을 한번에 저장.   전체를 대강 나타낸 축소영상의 부호화 이후, 축소영상을 순차적으로 확대 하기위한 차분 정보의 부호화.   저해상도 이미지를 얻기 위해선, 고해상도 이미지 (N × N) 를 수직과 수평 방향으로 각각 2 : 1 씩 down sampling 하면 image 는 N/2 × N/2 pixel 로 나타 나며, 그 후엔 LPF 를 사용하여 alising 제거 2.Compression Algorithm

Hierarchical multi-resolution encoding 2.Compression Algorithm   고해상도 이미지 얻기 위한 Upsampling 은 다음과 같다. x1=(a+d)/2 x2=(a+b)/2 x3=(b+c)/2 x4=(c+d)/2 x5=(a+b+c+d)/4 cx3b x4x5X2 dx1a

휘도 신호 Y 색차 신호 Cr 색차 신호 Cb Y CbCrY 최소부호화단위 (MCU) Y 전체 Cr 전체 Cb 전체 스캔 1 스캔 2 스캔 3 인터리브 방식 비인터리브 방식 2.4 영상부호화 방식에따라   Non-intereave: 각성분마다 한장의 영상형성.   Interleave: Y, Cr, Cb 마다의 부호화 data 로 MCU 마다 구성 2.Compression Algorithm

A1A2 An B1B2 Bn C1C2 Cn X Y A1,B1,C1,A2,B2,C2….An,Bn,Cn Scan 1 Data Unit encoded order, Interleaved A1,A2,….An B1,B2,….Bn C1,C2,….Cn Scan 1 Scan 2 Scan 3 Data Unit encoded order, Non-interleaved 2.Compression Algorithm

Sequential DCT (Base line) Progressive DCT Seqnential lossless Hierarchical Four JPEG mode of operation 2.Compression Algorithm

영상 → Preprocessing( 전처리 ) → Transform( 변환 ) → Quantization( 양자화 ) → Encoding( 부호화 ) → 비트 스트림 3.1 Preprocessing( 전처리 )   RGB 성분을 밝기성분인 Y, 색성분 U, V 로 변환 (color space 변환 )   압축률 향상을 위해 image 의 잡음 제거 (filtering)   U, V 의 성분을 2 나 4 pixel 당 하나만 취해 data 양을 1/2,1/4 로 줄인다. (color subsampling) 2 3.Compression Process

Transform( 변환 )   영상이 갖고 있는 정보의 중복성을 찾아내는 과정   DCT(Discrete Cosine Transform) 가 대표적 방법   통상적으로 영상의 계조도 변화가 적어 DCT 계수는 DC 와 낮은 주파수는 큰 값, 높은 주파수는 작은 값을 갖음 3.Compression Process

변환방법으로 고속계산 가능한 2 차원 DCT 를 보면, 7 7 F(u,v) =1/4C(u)C(v) Σ Σ f(i,j) cos[(2i+1)uπ/16] cos[(2j+1)vπ/16] i=0 j=0 C(u),C(v) = 1/Γ2 (u,v=0) = 1 (u,v≠ 0 ) F(0,0) 을 DC 성분 (8*8 block 의 평균치 ) 이라 하고 나머지 63 계수를 AC 계수라 한다. 역 변환 IDCT 의 식은 다음과 같다. 7 7 f(i,j) =1/4Σ ΣC(u)C(v) F(u,v) cos[(2i+1)uπ/16] cos[(2j+1)vπ/16] u=0 v=0 3.Compression Process

DC : Direct Current, AC : Alternate Current …. 매크로블록 (16x16) 지그재그 스캔 8 8 블록 (8x8) 3.Compression Process

Quantization( 양자화 ) DCT 로 얻어진 64 개의 계수를 어떤 수로 나눠 유효자리의 비트 수를 줄이는 과정. 양자화된 계수 ｒ (u,v) = round ( F(u,v) / Q(u,v) ) round 는 소수를 정수화 F(u,v) 는 DCT 계수 Q(u,v) 는 양자화 테이블 값 양자화 테이블은 색 단위 설정이 가능하다. 3.Compression Process

Luminance quantization matrix (example only ) 3.Compression Process

Chrominanace quantization matrix (example only ) 3.Compression Process

부호화 Run- length Encoding   같은 값의 연속 data 를 값 (Run) 과 개수 (length) 의 조합으로 표현   ABCDDDDDEEEEEEE (15 바이트 )  ABC*5D*7E(9 바이트 )   만화, 팩스 같은 배경 없는 영상에 탁월한 효과   빠른 속도가 필요한 압축에 쓰임 3.Compression Process

Entropy Coding data 를 표시할수 있는 최소의 bit 수로 코딩 Huffman Coding 가변장 부호화 (Variable Length Coding) 데이터의 발생 빈도수와 인코딩 bit 수는 반비례 알고리즘  데이터당 비트 평균치를 최소화하는 코드생성 첫째 확률테이블생성, 둘째 실제적 압축 DC 계수는 앞 블럭 DC 계수의 차분을 부호화 AC 계수는 zig-zag scan 으로 부호화. Pkzip,Arj 등에 사용된다. 3.Compression Process

Huffman Coding

Huffman Coding

Huffman Coding

Huffman Coding RKKKKKKK KKKRRKKK KKRRRRGG KKBCCCRR GGGMCBRR BBBMYBBR GGGGGGGR GRRRRGRR 1. 일곱가지색에의한 8*8 샘플 영상

빨강색 (R) 파랑색 (K) 녹 색 (G) 검정색 (B) 남 색 (C) 자홍색 (M) 노랑색 (Y) 빈도수 색상 2. 샘플 영상의 색 빈도수 표 노랑색 남 색 자홍색 녹 색 검정색 빨강색 파랑색 3. 표 2 에의한 Huffman 코드 Huffman Coding

Arithmetic Coding 한 data 값에 하나의 부호어를 정해서 bit 수를 줄임. 첫째 확률테이블생성, 둘째 실제적 압축의 과정. Huffman Coding 보다 효율이 약간 좋으나, 코드복잡, H/W 구현이 어려움 확률테이블에는 입력 데이타에 대해 0 과 1 사이의 범위 할당. 각 범위의 크기는 직접적으로 문자의 빈도수에 비례. 범위는 하나의 낮은 값과 하나의 높은 값으로 구성 데이터 발생빈도수가 높은 것 => 적은 비트, 넓은 범위 할당 데이터 발생빈도수가 낮은 것 => 많은 비트, 좁은 범위 할당 3.Compression Process

RED Green Blue RED GreenBlue RED GreenBlue [0.0, 0.2) [0.2,0.8) [0.8,1.0) 빨강 초록 파랑 할당된 범위 (0≤x<1) 확률화소 초록 - 초록 - 빨강의 축소된 출력범위 3.Compression Process

  JPEG 압축 data 는 entropy coded data 를 포함하는 entropy coded segment 와 header information 을 포함하는 marker segment 로 구성.   Non-hierarchical 과 hierarchical 이 있다.   계층형은 전체를 대강 나타낸 축소영상을 부호화   화상의 차분정보를 부호화   같은 영상으로 다른 해상도영상을 얻을 수 있음 4.JPEG Format

Image, Frame, Scan 단계의 데이터 구조 계층. Image Data 구조계층 비계층형 부호화의 경우 프레임 SOI [ 테이블 등 ] EOI 이미지 종료 마커이미지 선두 마커 필요에 따라 삽입 (DHT, DQT, DAC, DRI, COM, APP 등 ) 계층형 부호화의 경우 계층형부호화임을 표시 SOIEOI DHP [ 테이블 등 ] 프레임 1 [ExP] [ 테이블 등 ] 프레임 n 프레임 2 … 필요에 따라 삽입 (DHT, DQT, DAC, DRI, COM, APP 등 ) 필요에 따라 삽입 4.JPEG Format

Frame Data 구조계층 SOF 프레임 헤더 스캔 1 [DNL] 스캔 m 스캔 2[ 테이블 등 ] ….. 프레임 선두 마커 1. 프레임 헤더 이하의 데이터 길이 2. 1 화소당 정밀도 ( 비트수 ) 3. 영상의 라인수 4. 1 라인당 화소수 5. 색 성분의 사양 영상의 라인수 지정 ( 통상 프레임 헤더만으로 지정 ) 필요에 따라 삽입 (DHT, DQT, DAC, DRI, COM, APP 등 ) 4.JPEG Format

Scan Data 구조계층 SOS 스캔 헤더 스캔 선두 마커 1. 스캔 헤더 이하의 데이터 길이 ( 바이트 단위 ) 2. 스캔 내 색 성분수 3. 스펙트럼 선택개시 4. 스펙트럼 선택종료 5. 연속근사 비트 단위 …. … 에러 감시, 회복용의 주기적 인터벌 마커 4.JPEG Format

  Marker 표시 모든 마커 코드는 2 바이트로 표시 첫번째 바이트 : FFH 로 시작 두번째 바이트 : 00H, FFH 외 다른 1 바이트 코드 예 : DQT(Define Quantization Table(s)) FFDBH[ 표 4-1] 필 비트 ( 채워넣기 비트 ) 마커 코드 직전이 엔트로피 부호화로 끝나 바이트 경계에 도달하지 않았을 경우 경계에 도달할 때까지 ‘1’ 을 써 넣는다. 마커 코드마커 세그먼트 길이 마커 세그먼트 데이터 2 바이트 최대 65,533 바이트 4.JPEG Format

Original image (512x512, bytes) JPEG compressed image (30349 bytes) 4.JPEG Format