JPEG Image Compression Standard

데이터 압축 시스템 종류

• 압축 비율 = 오리지널 데이터 사이즈 / 압축 데이터 사이즈

• 압축의 두가지 종류

  • 손실이 없는 압축

    

    • RLE. 1이 4개 2가 3개 0이 2개 ….
    • 일반적인 우리가 쓰는 압축은 Lossless.
    • 텍스트 파일이나 실행 파일을 압축할 떄는 Losselss를 쓴다.

  • 손실이 있는 압축

  

  • 원래 7을 111 3비트로 표시.
    • 하지만 두비트로밖에 표현할 수 없는 환경이 되면 중요한 앞에 두비트만 살린다. 11 = 3.
  • 하지만 다시 3비트로 복구하면 110 = 6이 되어 버림. 손실이 생김
    • 멀티미디어데이타(오디오, 비디오, 이미지, 그래픽)같은 경우는 Lossy를 쓴다.
  • 손실이 생겨도 사람이 인식을 잘 못하기 때문.

Terminologies

• 캐릭터

  • input stream의 기본 데이터 하나

• String

  • 캐릭터의 연속. 시퀀스

• Input Stream

• Codeword

  • 캐릭터를 특정 비트 패턴으로 바꾼 것으로 예를 들어 1byte짜리 캐릭터를 매칭 테이블을 통해 010과 같은 3bit 형태로 변환한 것을 코드 워드라고 한다.

Run Length Encoding

• 반복되는 데이터를 run이라고 한다.
• 데이터에 반복이 있으면 압축률이 높다.
• 데이터에 반복이 없으면 오히려 효율이 떨어진다.
• 텍스트 데이터에 RLE를 쓰면 불리하다.
• 상황에 따라 알고리즘의 적용 방법이나 행태를 바꾸어야 한다. - adaptive
• RLE도 무손실 압축 방법의 하나로 반복되는 데이터(run이라고 함)를 압축하는 방법이다. text의 경우 별로 효과가 없지만 멀티미디어(예를 들어 a4스캔하면 흰 바탕이 쭉 연속되어있어서)에는 효과가 좋다.
• RLE와 일반 데이터를 섞어서 표현하는 압축방법도 있음. RLE가 사용된 부분엔 +기호를 붙여서 +4abcd+6e 이런식

Huffman Coding

• 허프만 코딩은 압축하고자 하는 문자열에서 자주 등장하는 문자는 짧은 비트로 표현하고 거의 등장하지 않는 문자는 긴 비트로 표현하는 가변길이 코딩이다. 즉 코드를 만들때 그 코드 값은 빈도수에 반비례해서 코드수를 배정한다. 이를 통해 효율적으로 압축할 수 있다.

• 여기까지는 유명한 허프만 코딩 알고리즘에 대해 다루고 있다. 간단히 요약하면 단 단어들의 빈도수를 센다. 가장 적게 사용된 빈도의 합을 부모노드로 하는 2진트리를 만든다. 반복한다. 모든 트리를 만들고 나서 왼쪽경로로 가면 0 오른쪽 경로로 가면 1 (반대도 가능) 이렇게 코드를 만든다.

• 허프만 코딩은 prefix property(접두어 속성)를 만족한다. prefix property란 하나의 코드가 어떤 단어의 코드를 접두어로 사용하지 않는 특성을 말한다. 이 특징의 장점은 비트를 쭉 읽기만 해도 바로 단어와 연결이 된다는 것이다.

예를 들어 0, 1, 01, 010은 접두어 코드가 아니다. 0이 01이나 010의 접두어가 될 수 있기 때문이다. 하지만 00, 010, 100, 101은 어느 코드도 다른 코드의 접두어가 되지 않기 때문에 접두어 코드라고 할 수 있다.

• 허프만 코딩은 가변길이이기에 유지 관리가 어렵고, 인코딩에 두 단계가 필요하므로 시간이 많이 걸린다. 즉 허프만 코딩을 위해선 전체 데이터를 쭉 읽은 뒤 갯수를 하나하나 세야하는 단점이 있었다. 그래서 수정된 허프만 코딩에서는 허프만 코드북을 사용한다. 코드북에는 허프만 코드가 미리 정의가 되어있기에 문자 출현 빈도수를 계산하는 과정을 생략할 수 있다.

• 팩스의 한 줄을 허프만 코딩을 이용해 압축하는 예제.

• 코드가 코드북에 적혀있으므로 찾아서 보고 적으면 된다. 64부터 2560까지는 구성 코드 워드를 보고 찾는다.

JPEG(Joint Photographic Experts Group)

• 정지 이미지 압축 표준

• 눈에 띄는 이미지 품질 저하 없이 20분의 1까지 압축 비율을 획득할 수 있다.

• 급격한 변화 없는, 완만하게 변화하는 이미지에 대해서는 잘 동작한다.

• 카툰이나 컴퓨터 그래픽, 흑백 이미지, 의학 이미지(이미지에서 아주 작은 암세포는 압축 과정에서 날아가 버릴 수도 있으니까)에는 상대적으로 좋지 않다.

  

• 위와 같이 high frequency data를 필터링해서 압축한다. JPEG의 가장 중요한 특징.

• 품질 수준을 내가 기술할 수 있다. 손실로 할 건지 무손실로 할건지 손실률(Q)을 통해서 결정할 수 있다.

JPEG Encoding Modes

• Sequential baseline encoding

  • 실제로 우리가 대부분 사용하는 모드이다
  • 이미지를 한 줄로 코딩한다. 옛날에 이미지가 한줄씩 한줄씩 뜨던 것을 생각해보자.

• Progressive Encoding

  • 이미지를 여러줄로 코딩한다.
  • 계속 덧칠하는 방식.

• Hierachical encoding

  

  • 피라미드 코딩.여러가지 레졸루션으로 코딩한다. 하나의 이미지에 여러 해상도를 갖고 있다.

• Lossless encoding

  • 손실이 발생하는 부분을 삭제하는 알고리즘. 압축률이 떨어지므로 사용하지 않음.

RGB color model

• 빛을 내는 I/O 디바이스들은 RGB 모델로 표현
• 모든 컬러는 정육면체 안에 한 점으로 표시
• 모든 실세계의 데이터는 n차원 공간상의 점으로 표시
• magenta, cyan, yellow는 빛을 흡수하는 색.
• 빛의 3원색 RGB, 색의 삼원색 CMY

YCbCr Color Model

• Y는 밝기 정보, Cb는 푸른색 정보, Cr은 붉은색 정보

  

• RGB를 위의 공식에 의해 YCbCr로 바꾸어서 YCbCr 정보가 JPEG이미지 정보에 들어간다.

• 다시 화면에 출력하기 위해서는 YCbCr을 위의 공식을 통해 RGB로 바꾸어서 출력

• 색상정보를 밝기 정보와 칼라정보로 분리시킨다.

• 인간의 시각은 칼라에 대해서는 둔감하다. 반면에 밝기 정보에 대해서는 민감하다. 그래서 Y정보는 그대로 두고 Cb와 Cr은 정보를 압축시킨다.예를 들어 RGB에 각각 8bit씩 써써 24bit를 썼다면, 이를 YCbCr로 바꾸어서 Y에 8, Cb에 4, Cr에 4bit만 쓰면 16bit로 줄일 수 있는 것이다.이렇게 칼라 정보의 해상도를 줄인다. 하지만 이렇게 해도 사람은 칼라 정보에 둔감하기에 눈치채지 못한다. 이렇게 압축률을 높히는 것.

JPEG 압축 과정

1. 이미지를 YCbCr모델로 변환한다
2. 컬러 컴포넌트를 줄인다.
3. Y, Cb, Cr화면 각각을 8x8픽셀 블록 단위로 나눈다. 그리고 각 블록에 128을 뺀다.(DCT를 실행하기 위해선 가운데가 원점에 있어야 하기에 128을 빼서 -128~127범위로 맞춰준다.)
4. high frequency data를 제거하는 DCT(discrete Cosine Transform)을 실행한다. 이게 가장 중요
5. DCT계수를 개량화한다.
6. 최종으로 나온 데이터를 엔트로피 인코딩을 한다.

Discrete Cosine Transform

• 하나의 블록에서 제일 처음 픽셀을 DC component라고 하고 나머지 63개를 AC component라고 한다.

• DC : 직류, AC : 교류

• DC component에는 전체를 대표하는 값이 들어가고 나머지 63개는 덜 중요한 정보들이 들어간다.

  

• 각 픽셀값들은 위의 forward 공식에 따라 변환된다.(디코딩은 inverse)

• 이 값을 DCT 계수라고 부른다.

• DCT Coefficients : DC요소의 변화에는 민감하지만 AC요소의 변화에는 둔감하다는 인간 시각 시스템의 특징을 압축에 이용한다.

Quantization

• 오리지널 값을 DCT를 거치고 나니 상당히 작은 값으로 변해있다. 우리는 이 작은 값들을 그냥 0로 만들어 버리고 싶다.

  

• Y에는 Luminance table, Cb Cr에는 Chrominance table을 이용하여 DCT계수들을 이로 나누어 반올림한 몫을 저장한다. 이를 Quantization이라고 한다. 여기서 많은 high frequency들이 0으로 변하므로 데이터의 양을 줄일 수 있다.

  

Zigzag Scanning

• 한 블록을 파일에 저장할 때 지그재그패턴으로 집어넣는다.
• 뒤로갈수록, 숫자가 커질수록 0에 가깝고 앞쪽에 있을 수록 0가 아닐 확률이 높다. 따라서 위와 같은 패턴으로 집어넣는다.
• 이를 diagonal zigzag pattern이라고 한다.

Descriptors for quantized coefficient

• quantized coefficient를 파일에 집어넣는 값을 descriptor라고 한다.

• 이 descriptor만 만들어 내서 파일에 차례대로 집어넣으면 된다.

• 제일 첫번째인 DC계수는 이전 블록의 DC계수값과의 차이로 저장되고 나머지 AC계수들은 (0의 run length + 그 뒤에 오는 non zero의 값)을 이용해 허프만 코딩북을 참고해서 저장된다.

• 만약 DC계수의 차가 3이라고 가정해보자. 3은 카테고리 2번에 속한다.

  허프만 코드 테이블에 따르면 카테고리 2는 코드길이 3에 011로 나타낸다.

  그리고 카테고리 2번에는 -3, -2, 2, 3 이렇게 4개가 속하기에 이 4개를 구분해주기 위해 3의 경우에는 뒤에 11을 덧붙인다.

  따라서 DC컴포넌트 3은 01111로 표현할 수 있다.

• AC의 경우에는 지그재그 패턴으로 가면서 0인것과 0이 아닌 것으로 그룹을 형성한다.

  0 -2를 보면, 처음에 zero run length를 계산한다. 0가 하나밖에 없으니까 1이고,

  다음 -2가 속한 카테고리를 찾는다. 2.

  그 후 1/2를 테이블에서 찾으면 5비트로 11011이라는 것을 찾을 수 있다.

  그리고 카테고리 2에서 -2는 01로 코딩을 하라고 되어 있으므로

  최종적으로 1101101이 된다.

  이렇게 데이터의 양을 줄일 수 있다.