Stop Thinking, Just Do!

Sung-Soo Kim's Blog

The JPEG Compression Algorithm

tagsTags

29 April 2019


Article Source


The JPEG Compression Algorithm

Overview

JPEG은 Joint Photographic Expert Group의 약자다. 원래는 ISO(국제 표준화 기구)와 CCITT(국제 전신 전화 자문)의 영상전문가들의 협력을 의미하지만, 요즘 “JPEG”이란 단어는 가장 널리 쓰이는 정지압축영상의 파일형식(.jpg, .jpeg) 또는 그와 관련된 표준이란 의미로 많이 쓰인다. 정식 명칭은 ‘Digital Compression and Coding of Tone Still Image’이며, 이는 ISO/IEC 10918-1(ITU 권고 T.81)로 표준화되어 있고, 정지 영상이나 연속적인 톤의 이미지를 표현하기 위한 압축 표준이다. JPEG은 손실(loss)압축방식과 무손실(lossless)압축 방식 둘 다 지원한다.

실/무손실이 무슨 뜻이냐고요? 말 그대로 손실압축방식이라면 바로 어떤 사진이나 그림의 데이터 정보의 압축을 했을 때 원래 갖고 있던 정보량이 약간 손실된 체로 압축을 한다는 뜻이고, 무손실이라면 압축을 해도, 그 정보량이 변하지 않는다는 뜻이다. 따라서 무손실압축방식(lossless)의 경우는 영상의 손실을 줄 수 없는 의료 영상과 같은 중요한 데이터에 쓰인다.

그러나 대부분의 경우, 우리가 흔히 접하는 JPEG 영상은 DCT(Discrete Cosine Transform,이산여현변환)이라는 아주 놀라운 수학변환공식에 기반을 둔 유손실 압축 방식을 이용한 것이다.

이처럼 사람들이 jpg을 선호하는 이유는, 사람의 눈이 상당히 둔감하기 때문에 얼핏보기에는 화질을 거의 떨어뜨리지 않으면서, 데이터량은 수십배가량 줄일 수 있기 때문이지요. 이런 일이 가능한 이유는 정지영상의 특성을 이용하여, 수학적으로 아주 멋지고 훌륭한 알고리즘 (DCT, Arithmetic Coding 등)을 세계적인 석학들과 과학자분들이 수십년간의 연구와 노력 끝에 발명해 내셨기 때문이다.

JPEG Algorithm

1) 여러 개의 화소가 모여 하나의 영상 화면을 이룬다.

일단 영상은 화소(pixel)라는 최소단위의 아주 작은 점, 수백~수만개가 모여 네모난 하나의 화면을 구성합니다. 한 화면을 구성하는 pixel수에 따라 소위 1024x768 이니 800x640이니 하는 해상도(resolution)를 나타낸다. 1024x768 이라면 가로로 1024줄, 세로로 768줄의 총 786432개의 화소로 구성된 네모난 화면을 말합니다. 따라서 화소수가 많을 수록 화질은 선명하겠죠? 하나의 화소는 명도, 채도 등에 따라 정수값을 갖게 되는데, 설계하는 사람 마음이다만, 예를 들어 명도별로 0~255까지 쓸 수 있다고 가정하고 0이면 검은색 255이면 흰색이라고 정한다면, 128은 회색이 되겠고 200이면 칙칙한 회색이 되겠죠? 그러면 1024x768 영상은 0~255값을 갖는 거대한 1024행*728열의 수학적인 행렬이 되는 것이다.

2) 정지영상(ex. 사진)을 보면, 한 pixel 주위는 서로 비슷한 색이 모여있다.

여러분께서 예전에 바닷가에서 친구들과 찍은 사진을 한 장을 꺼내보시면, 발 근처에는 황토색 모래가 쭈욱 있고, 머리 위에는 하늘색 하늘이 펼쳐져 있고, 뒤에는 시퍼런 수평선과 바다가 보이고, 머리에는 검은색 머리가 바람에 휘날리고 있을 겁니다. 사진의 부분부분마다 비슷한 색상이 모여 있지요? 즉, 하나의 화소 입장에서 보면 확률적으로 나랑 비슷한 색을 가진 놈이 근처에 있을 확률이 높은 것이다. 이런 확률적 특성을 이용해서 화면을 잘잘히 쪼개서 무언가를 해보면 데이터량이 줄어들 수 있지 않을까 해서 생각해낸 방법이 바로 JPEG이다!

3) 화면 행렬을 두부판 썰 듯 8x8 행렬로 쪼갠다.

이제 영상을 잘잘하게 쪼개봅시다. 1024x728 화면행렬을 8x8짜리 정사각형 행렬로 쪼개면, 총 가로 128 x 세로 91개의 8x8행렬로 나뉜다. 영상이론에서는 이 8x8 행렬을 블록(block)이라고 부르고, 영상압축의 아주 기본 단위로 여깁니다. JPEG의 압축은 이 블록단위로 행해진다.

4) encoding (정보 압축하기)

이 8x8의 블록 행렬은 여러가지 수학적인 변환에 의해 아래와 같은 과정으로 정보량이 줄어듭니다.

  • DCT : 이 연산을 하면 왼쪽 위쪽으로 큰 숫자들이 몰린다. 제일 좌측 상단에 있는 큰 숫자를 DC(저주파)값, 나머지 63개의 숫자들은 AC(고주파)값이라고 부릅니다. 특히 DC값 및 이 근처에 있는 숫자들은 블록전체의 명도를 좌지우지하는 매우 중요한 정보를 담고 있다.

  • 양자화(Quantization) : 전체적인 데이터량을 줄이기 위해 양자화 행렬이라는 설계자가 만든 임의의 정수행렬로 나눈다. 그러면 작은 값들는 0으로 바뀌겠지요? 이렇게 0이 되어 사라진 숫자들 때문에, 약간의 정보손실(loss)가 발생하는 것이다.

  • 지그재그 스캐닝허프만 코딩 테이블을 이용한 비트열 압축 : 지그재그 줄세우기로 만들어진 정수열을 이진수로 바꾼 후, 그 이진수의 인근값 특성 및 확률(0 또는 1이 연속으로 몇 개가 계속되는지 등등)을 이용한 허프만 코딩(자세한 설명은 생략하겠습니다.)을 이용해서 8x8행렬이 불과 몇 개의 0과 1의 조합으로 줄어들게 된다.

이처럼 원래의 8x8 정수 행렬이 DCT, 양자화, 지그재그 스캐닝, 허프만 코딩 등의 과정을 거치면서, 데이터량이 엄청나게 줄어드는 것을 확인할 수 있다. 단 양자화 과정에서 아주 작은 AC 값들은 손실되기 때문에 원래 영상에 비해 약간 화질이 저하되는 손실압축방식이 되는 것이다.

5) decoding (압축풀어서 보기)- encoding과정의 역순으로 진행된다. 그렇게 복원된 영상과 원래의 영상값을 비교해보자. 별로 차이는 안나지만 다르죠? 색상으로 변환되면 사람의 눈으로 볼 때는 별차이를 못느끼지만 이 엄연한 값의 차이 때문에 JPEG을 손실압축방식(lossy compression)이라고 부른다.


comments powered by Disqus