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

Presentation on theme: "- 1 - JPEG 1. Introduction 2. Compression Algorithm 3. Compression Process 4. JPEG Data format."— Presentation transcript:

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

2 - 2 - 1.1 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

3 - 3 - 1.2 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

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

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

6 - 6 - 1. 2.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 - 7 - Sequential Mode Progressive Mode 2.Compression Algorithm

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

9 - 9 - 2.Compression Algorithm

10 - 10 - 2.2 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

11 - 11 - 2.Compression Algorithm

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

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

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

15 - 15 - 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

16 - 16 - 휘도 신호 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

17 - 17 - 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

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

19 - 19 - 영상 → 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

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

21 - 21 - 변환방법으로 고속계산 가능한 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

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

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

24 - 24 - 1611101624405161 12 141926586055 1413162440576956 1417222951878062 182237566810910377 243555 8110411392 49647887103121120101 7292959811210010399 Luminance quantization matrix (example only ) 3.Compression Process

25 - 25 - 99 6647 99 562624 99 66262118 99 47241817 Chrominanace quantization matrix (example only ) 3.Compression Process

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

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

28 - 28 - Huffman Coding

29 - 29 - Huffman Coding

30 - 30 - Huffman Coding

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

32 - 32 - 19 17 14 7 4 2 1 빨강색 (R) 파랑색 (K) 녹 색 (G) 검정색 (B) 남 색 (C) 자홍색 (M) 노랑색 (Y) 빈도수 색상 2. 샘플 영상의 색 빈도수 표 11011 노랑색 1100 11010 남 색 자홍색 10 111 녹 색 검정색 00 01 빨강색 파랑색 3. 표 2 에의한 Huffman 코드 Huffman Coding

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

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

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

36 - 36 - 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

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

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

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

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