Computer Graphics Study for Game 3. Image Processing(2)

Information 정보란 무엇인가? 정보란 확률적이다 Claude Shannon, “The Mathematical Theory of Communication” 정보의 단위로 비트를 사용 왜 비트인가? Yes or No

Information Ex) 주사위를 던져 짝수가 나올 사건 E1 주사위를 던져 짝수혹은 홀수가 나올 사건 E2 P(E1) = 0.5 이 사건의 정보량은 1 비트이다 주사위는 짝수 아니면 홀수이기 때문 주사위를 던져 짝수혹은 홀수가 나올 사건 E2 P(E2) = 1 이 사건의 정보량은 0 확률이 낮을 수록 정보량이 커진다 정보량 n = -log2P

Entropy 엔트로피 정보량 사건에 대해 모르는 정도의 양 검은색공과 흰색공이 하나씩 있을 때 정보량은 1 8개 검은공과 2개의 흰색공이 있을때 정보량 각 사건의 정보량의 평균을 구하면 됨 n = – (0.8)log2(0.8) – (0.2) log2(0.2) = 0.32… 등 확률일 때보다 정보량이 적다? 모르는 정도가 적다는 뜻이다

Entropy Ex) 알파벳의 정보량 n = 4.08 똑같은 확률로 발생한다면 n = 4.7548… 발생빈도가 다르기 때문에 정보량이 줄어든다 문자 발생확률 공백 0.1859 N 0.0574 A 0.0642 O 0.0632 B 0.0127 P 0.0152 C 0.0128 Q 0.0008 D 0.0317 R 0.0484 E 0.1031 S 0.0514 F 0.0208 T 0.0796 G U 0.0228 H 0.0467 V 0.0083 I 0.0575 W 0.0175 J X 0.0013 K 0.0049 Y 0.0164 L 0.0321 Z 0.0005 M 0.0198  

Redundancy 최대 엔트로피 상대 엔트로피 리던던시 사건이 등확률로 일어날 경우 일반적으로 실제 정보량은 최대 엔트로피보다 작다 상대 엔트로피 실제 엔트로피 / 최대 엔트로피 리던던시 1 – 상대 엔트로피 Max Entropy Redundancy Entropy

Compress 압축 리던던시를 줄이는 것 알파벳의 나열에 규칙이 있다면 엔트로피를 더 줄일 수 있다 압축의 한계는 엔트로피이다

Lossless VS Lossy 무손실 손실 일반적인 데이터 압축 가역적 압축 엔트로피가 압축의 한계 이미지나 사운드와같이 인간의 감각에 관련된 정보를 압축할 때 사용 인간이 느끼지 못하는 정보를 리던던시라고 생각함 엔트로피보다 더 정보량을 줄일 수 있다

Run Length Encoding RLE 반복되는 문자를 인코딩 Goooood 반복이 자주 없을경우 오히켜 크기가 커진다 (1,G) (5,o) (1,d) 반복이 자주 없을경우 오히켜 크기가 커진다 2D 렌더링 시에 RLE 를 이용하여 효과적인 투명블리팅이 가능하다

Lz77 LZ77 A B C D Output : (0,0)A A B C D Output : (0,0) A (1,1) B

A B C D Output : (0,0) A (1,1) B (1,1) C A B C D Output : (0,0) A (1,1) B (1,1) C (1,1) D A B C D Output : (0,0) A (1,1) B (1,1) C (1,1) D (7,4) A Output : (0,0) A (1,1) B (1,1) C (1,1) D (7,4) A (4,3)

Huffman Coding 허프만 코딩 빈도수가 높은 기호를 적은 비트로 표현 빈도수 대로 정렬 한 다음 가장 빈도수 낮은 것 부터 합쳐 나가면서 트리를 만든다 Ex) 00A11B11C11D74A43 1=6, 0=2, A=2, 4=2, B=1, C=1, D=1, 7=1, 3=1

Huffman Coding I : 01 0 : 101 A : 100 4 : 001 B : 110 C : 0001 D : 0000 7 : 1111 3 : 1110 1011011000101110010100010101000011110011000011110

GIF Graphics Interchange Format 256 컬러 기반의 비손실 압축 256개의 컬러 테이블을 만들고 각 픽셀은 이에 해당하는 인덱스만 저장 LZW (Lempel-Ziv-Welch)압축을 사용 LZ77의 개선 버전 특허권 문제로 PNG 등장

GIF

DCT Discreet Cosine Transform DFT 와 비슷하게 공간 좌표계에서 주파수 좌표계로 변환 일반적으로 type-II DCT 변형 알고리즘을 사용한다 저주파 성분에 에너지가 몰리는 Energy Compaction 효과가 있다

DCT JPEG나 MPEG 등과같은 이미지 손실 압축에 주로 사용된다. JPEG나 MPEG 같은 경우 주로 8*8 블락 단위로 DCT 를 적용한다 변형된 알고리즘들은 음성 처리에도 사용된다

JPEG Joint Photographic Experts Group ISO/ITU-T 표준 정지화상을 위한 손실압축 포맷 이미지를 어떻게 연속된 바이트로 바꾸는지에 대한 표준 JFIF(JPEG File Interchange Format) Exif(Exchangeable image file format) 다양한 서브포맷이 존재하지만 대부분 거의 사용되지 않음 저장시 YCbCr 컬러 좌표로 변환

JPEG 압축 방법 YCbCr 로 변환 DCT 적용 양자화 이 때 CbCr을 다운샘플링 하기도 한다 8*8 사이즈 블락라이징이 발생하는 이유 양자화 DCT 적용 결과를 양자화 한다 각 성분에 대해 특정 상수로 나누어 소수점 이하를 버리는 방식을 취한다 이 때 고주파를 잘 인식 못하는 것을 이용해 고주파 성분의 데이터를 대다수 0 에 가까운 값이 된다

JPEG 부호화 고주파 성분의 화질 열화가 심하다 색상과 채도 부분의 정보가 많이 파괴된다 8*8 성분을 지그재그로 0에 대해서만 RLE 인코딩 RLE 인코딩 결과를 허프만 코딩화 함 고주파 성분의 화질 열화가 심하다 의도적으로 고주파 성분을 손상시킴 고주파 성분이 대부분인 도형이나 문자 가 그려진 이미지에 적합하지 않음 색상과 채도 부분의 정보가 많이 파괴된다 HSL 공간상에서 고주파 성분이 많기 때문 YCbCr 공간상에서의 정보 파괴는 심하지 않다

Chroma Down Sampling

HSL deterioration

WAVELET Transform Wavelet Wavelet Transform 한정된 구간에서 지속되며 평균값이 0인 파동

WAVELET Transform Wavelet Transform 고 주파 성분과 저주파 성분을 분리 해 나감

WAVELET Transform

JPEG2000 Joint Photographic Experts Group 2000 Wavelet Transform 을 사용 압축 효율이 좋다 압축 과정이 복잡하고 느리다 리스케일링이 쉽다

JPEG2000

DXT S3 Texture Compression DXT1~DXT5 4X4 블록 64Bit/ 128Bit 고정 압축 비율 8:1 / 4:1 그래픽 하드웨어가 쉽게 압축/압축해제 할 수 있도록 설계 무작위 접근이 용이 노말맵에 적합하지 않음 3Dc, A8L8, V8U8 Alpha 채널을 이용하여 저장

DXT DXT1 두 개의 16 비트 컬러와 4X4 룩업 테이블로 구성 C0 > C1 C0 < C1 C2 = 2/3 C0 + 1/3 C1 C3 = 1/3 C0 + 2/3 C1 C0 < C1 C2 = 1/2 C0 + 1/2 C1 C3 = Transparent Black 즉 4X4 픽셀에 유사한 4가지 컬러만 가능 컬러 차이가 심할 경우 블락라이징 현상 8:1 압축비

DXT DXT2 / DXT3 DXT1 + 64bit Alpha 4bit per Alpha 4:1 압축 비 속도는 빨라지지만 색상 손실이 심해서 거의 사용되지 않음

DXT DXT4 / DXT5 DXT1 + 64bit Alpha 4:1 압축 비 a0 > a1 a0 < a1 a2 = 6/7a0 + 1/7a1 … a7 = 1/7a 0+ 6/7a1 a0 < a1 a2 = 4/5a0 + 1/5a1 … a7 = 1/5a 0+ 4/751 a6= 0 a7=255

DXT

Hasta Luego To be continued