[본문스크랩] jpeg과 JFIF

http://web.usxchange.net/elmo/jpeg.htm

jpeg 압축

JPEG과 JFIF

JPEG은 "Joint Photographic expert group"의 머리글자어(acronym)이고, JFIF는
"JPEG File Interchange Format"의 머리글자어이다. 우리가 보통 생활에서
jpeg화일을 말할때는 보통 JFIF파일을 일컫는 것이다. 만약에 여러분이
어떤 jpeg 화일을 memory dump해 보면 jpeg화일안에는 JFIF글자가 7번째
글자부터
있음을 알 것이다. TFIF는 jpeg압축 알고리즘을 사용한다. 여기서는 우리는
JFIF
화일에 대해서만 다루겠다.

jpeg 포맷에 대한 설명들은 인터넷에 별로 많이 없는 것 같다. jfif포맷에 대한
정보는 "C-cube microsystems, inc. spec"에는 jfif포맷에 대한 정보들이
많이 있는 것 같은데, 그런데 그 정보들은 jjfif에 대한 특별한 요구사항만을
기술한 것이고, 그리고 독자들은 이미 jpeg에 대한 specs들을 이미
알고 있다고 한 듯하다. 그리고 그곳에는 jpeg압축 알고리즘에 대한 이야기도
많이
있는데, 그러나 program을 할 수 있을 정도로 자세하게 설명하지는 않았다.

여러분은 "Independent JPEG Group"에서 만든 source코드로부터
jpeg에 대해서 공부할 수도 있겠지만, 그러나 그 코드는 "여러가지
platform"에서도 돌아가도록, 그리고 "최상으로 돌아가도록" 프로그램이
짜져 있어서, 그 프로그램을 분석하는데는 상당한 어려움이 있을 것이다.


jpeg에 대한 ISO규격들은 online으로 얻을 수 있다. 얻고자 하면
"Independent JPEG group information"에서 얻기 바란다.

난 ISO규격을 사지 않았다. 난 나의 대부분의 정보를 미국 국방부(DoOD)의
"National Imagery Transmission Format Standard(NITFS)"의 MIL-STD-188-198A
로부터 얻었다. 이 표준은 비록 JFIF랑은 같지 않지만, 그러나 jpeg의 압축과
복원에 대한 상당한 설명을 해주고 있다.

그리고 또 유용했던 논문은 Gregory K. Wallace가 쓴, "The JPEG still
Picture Compression Standard"라는 논문이 있다.




손실 압축

jpeg압축은 GIF, BMP, RLE, pkzip과 같은 압축과는 본질적으로 다른 면이
있다. 그런 압축방법들은 압축과 복원 과정에서 손실이 발생시키지
않고, 그리고 그 방법들은 "정보의 반복됨"을 이용하여 압축효과를
얻는 방법이다. jpeg은 연속적인 이미지, 예를들어 사진 같은 것을
압축하는데 쓰이는 방법이다. 이들 이미지들은 "정보의 반복됨"이 그리 많지
않아서 그 "정보의 반복됨"을 이용하여 압축을 할려고 하면 별로 좋은
결과를 얻지 못한다. 그래서 jpeg은 주어진 정보 중에서 압축전에 정보를
버리는데, 바로 이 때문에 JPEG은 "압축과 복원"을 거치면 손실이 발생한다.
이때문에 jpeg은 "손실 압축"이다. 이런 손실압축이 별로 마음에 안들지
모르지만
사진이라는 것에는 없애버려도 우리 인간이 알아챌 수 없는 그런 정보가
상당하기 때문에, 이런 정보를 버릴 수가 있다. 또 GIF와 8 bit BMP화일들은
256가지 색깔밖에 나타낼 수 없는데, jpeg은 항상 24비트이고ㅡ 그래서 대략
16.8백만 색깔을 표시할 수 있다는 것을 생각해 보자. jpeg이 별로 성능을
발휘할 수 없는 분야가 있다면, 그것은 "이미지 편집"의 분야일 것이다.
이미지를 편집할때는 이미지가 수시로 변경되고 수시로 압축되고 수시로
저장되어야 하기 때문이다. 압축을 할때마다 이미지 손실이 발생하기 때문이다.
마치 녹음된 오디오 테입으로 또다시 녹음을 하는 과정을 계속할때처럼...



색깔 세계

..........빨강
..........|
..........|
..........|
..........|
........../---------녹색
......../
....../
..../파랑

VGA카드는 빨강, 파랑, 녹색의 세 색깔의 강도를 조절함으로써 여러가지 색깔을
표시할 수 있다. 세 색깔축이 x, y, z좌표계의 축을 형성한다. 그러면
좌표에서 한점은 한 색깔을 나타낸다. 그런데 한 색깔을 나타낼려면 꼭
이처럼 (빨강, 파랑, 녹색) 쌍 방식으로만 할 수 있는 것은 아니다.
회색의 경우 빨강, 파랑, 녹색의 강도를 모두 같게해서 만들 수 잇다.

우리는 (빨강, 파랑, 녹색)의 값이 모두 같은 값을 갖는 x=y=z인 새로운 축을
생각할 수 있다.

..........빨강
..........| /
..........| /
..........| /
..........| /
........../---------녹색
......../
....../
..../파랑

이 축을 광도(luminance)라고 부를 수 있다. 그리고 우리는 이 광도에서 빨강과
파랑성분을 빼서(subtracting), 두 새로운 축을 만들어 낼 수가 있다.
이 두 새로운 축을 "빨강 색도(red chrominance)", "파랑 색도(blue
chrominance)"라고 한다. 광도는 Y로 표시하고, 파랑색도는 U, 빨강색도는
V로 표시한다. 이 새로운 세 축은 jpeg 이미지 파일에서 사용되는 세 성분이
된다. (빨강, 파랑, 녹색)의 색깔체계와 (광도, 빨강색도, 파랑색도) 사이의
색갈 변환은 다음의 식으로 가능하다.


Y = 0.299 R + 0.587 G + 0.114 B
U = -0.1687 R - 0.3313 G + 0.5 B + 128
V = 0.5 R - 0.4187 G - 0.0813 B + 128

R = Y + 1.402 (V-128)
G = Y - 0.34414 (U-128) - 0.71414 (V-128)
B = Y + 1.772 (U-128)

(RGB포맷에서는 R, G, B가 모두 양수값을 갖고 또 0에서 255 사이값만을 갖는
다는 것에 주위해야 한다)

YUV 포맷을 사용하는데는 이유가 있다. 인간의 눈은 색도(chrominance) 보다는
광도(luminance)에 훨씬 더 민감하게 반응하기 때문이다. 대개의 경우 jpeg은
압축전에 색도정보의 3/4를 버린다. 이렇게 버리면 이미지의 정보의 양은
1/2로 줄어든다. 예를들어 4개의 픽셀을 생각해 보자. 4개의 픽셀의 색깔성분은
원래 4 * 3 = 13개 였으나, 색도성분의 3/4를 버리면... 1 * 4 +
2 * 1 = 6개의 성분만이 남게 된다.


Data Unit과 Minimum Coded Units.


jpeg에는 2가지 데이타 유닛(data unit)이 있다. 기본 데이터 유닛은 8x8
블락이다. 이 데이타 유닛의 data들은 Y, U, V중에서 한가지 색깔만을
나타낸다.

jpeg은 위에서도 말했듯이 압축전에 색도 성분의 3/4를 버린다. jpeg 헤더에는
각각의 색깔성분에 대한 "수평 sample factor"와 "수직 sample factor"의
값을 가지고 있다. Y색깔은 최대한으로 sampling한다. 즉 각각의 픽셀에는
항상 Y가 존재한다. 값을 가지고 있다. 대개의 경우, (항상 그런 것은
아니지만), Y색깔의 "수평/수직 sample factor"는 2이고, 색도성분들에 대한
"수평/수직 sample factor"들은 1이다. 이경우 4개의 픽셀은 Y성분 4개,
(아래 그림처럼) U성분 1개, V성분 1개로 sampling된다.

+-------+-------+
| Y | Y |
| ____|___ |
| | | |
+---+U V +---+
||_______| |
|Y | Y |
+-------+-------+

"수평/수직 sample factor"중에서 제일 큰 값들이, Minumum Coded Unit(MCU)의
"폭/높이"가 된다.

위의 그림의 경우, MCU는 2개의 8x8 블락 높이에, 2개의 8xb 블락 폭으로
구성되어, 전체 4개의 8x8 블락으로 구성된다. 이 블락들은 화일에 Y성분들을
모두 저장하고, 그다음 U성분을 저장하고, 그다음 V성분을 저장한다. 이경우
MCU하나는 4개의 Y 8x8블락, 1개의 U 8x8 블락, 1개의 V 8x8블락을 포함하게
된다.

DOD의 NITFS문서는 다음과 같이 말하고 있다.

---------

"압축프로세서는 이미지의 오른쪽, 바닥쪽에 샘플을 넣어서 블락의 숫자가
"정수"가 되도록 하여야 한다. 만약에 이미지가 충분한 데이터가 없어서
이미지 오른쪽과 아래쪽에 8x8 블락을 만들 수가 없을 때는, 이미지
오른쪽에서는
가장 오른쪽값들을 오른쪽으로 계속 반복시키고, 이미지 아랫쪽에서는
가장 아랫쪽값들을 아래쪽으로 계속 반복시켜야 한다. 이미지를 복원시킬때는
header로부터 이런 여분의 샘플값들이 있다는 것을 알아내서 인위적으로
첨가시킨 이 샘플들을 지워야 한다."

---------

(가로가 150픽셀인 그림을 생각해 보자. 19 x 8 = 152이므로 만약에 위의 말이
맞다면 그림의 폭은 152가 되어야 말이 맞을 것이다. 그렇지만 152를 넓이로
해서 그 그림을 display할려고 하면 픽셀들이 깨졌다. 만약에 MCU의 정수배인
16 x 10 = 160을 사용해서 해보았더니 그림이 제대로 나왔다. 이것을 보면
정수배가 되어야 하는 것은 "블락크기"가 아니고, "MCU의 크기"였던 것 같다)




Discrete Cosine Transform

JPEG압축의 기본 아이디어는 공학에서 나온 것이다. 전기신호나 음파신호는
시간에 따라 진동하는 값으로 생각할 수 있다. 평면에 그려진 그림은
각각의 색깔성분이 x축과 y축에 따라 변화하는 것으로 생각할 수 있다.
Fast Fourier Transform(FFT)이랑 닮은 DCT는 이미지의 품질에는
별 영향을 미치지 못하는, 이미지의 "높은 주파수 정보"를 버리는데
사용된다. 여기서 주파수라는 것은 "시간상의 주파수"가 아니고 "공간상의
주파수"를 말한다.

64개의 data값이 있는 8x8블락 f(x, y)를 생각해보자. Forward DCT를 사용하면
프랜스폼된 F(x, y)를 얻을 수 있다. 그후 Inverse DCT를 사용하면 F(x,
y)로부터
fx, y)를 얻을 수가 있다. 이들 트랜스폼 공식은 다음과 같다.


7 7 [(2x+1)up] [(2y+1)vp]
F(u, v) = 1/4 C(u)C(v) Sigma Sigma f(x, y) cos[--------]cos[--------]
x=0 y=0 [ 16 ] [ 16 ]

7 7 [(2x+1)up] [(2y+1)vp]
f(x, y) = 1/4 Sigma Sigma C(u)C(v) F(u, v)cos[--------]*cos[--------]
u=0 v=0 [ 16 ] [ 16 ]


(여기서 u=0이면 C(u) = 1/sqrt(2)이고 u != 0이면 C(u) = 1)


이론적으로 이 트랜스폼에서는 정보손실이 일어나지 않는다. 그러나 실제로는
실수값이란게 정확하게 저장될 수 없다보니 항상 어느정도 손실이 일어난다.

위의 방정식들은 삼각함수와 수학함수를 써서 쉽게 프로그램할 수 있다.
그렇지만 위의 알고리즘을 수식 그대로 프로그램하면 위의 계산이 느려터져
실제적으로 사용할 수 없을 것이다.

복원시에는 IDCT를 하여야 하는데, Independent JPEG Group의 source에는
3가지 방식을 제공해주고 있다. 그 source 화일은 각각 jidctflt.c
jidctfst.c jidctint.c이다.






JPEG 압축


위에서 말했듯이 이미지는 8x8블락으로 조각내고, 각각의 8x8블락들이
모여 MCU(Minumum Coded UNIT)을 이룬다. 이미지는 MCU단위로 처리된다.
MCU내에서는 각각의 색깔들은 차레대로 8x8단위로 처리된다. Y성분이 처리되면
U가 처리되고, 그다음에는 V가 처리된다.


다음은 8x8블락을 압축하는 과정이다.

1. block의 각 값들을 shift한다.

2. block을 FDCT한다.

3. Quantize한다.

4. Subtract the last DC coefficient from the current DC coefficient

5. Zigzag the block

6. Zero run length encode the block

7. Break down the non-zero coefficients into variable-length binary
numbers & their lengths

8. Entropy encode the run lengths & binary number lengths

9. Write the entropy encoded information & binary numbers to the output


구체적으로 설명해 보면...


118 91 123 125 124 114 117 104
100 93 88 85 87 100 115 105
94 101 78 99 112 87 109 115
104 82 83 78 92 118 124 88
119 93 99 104 76 111 86 112
83 119 104 92 111 76 112 100
97 85 90 100 106 125 123 86
99 86 85 105 81 99 115 119

위의 주어진 data가 있을때

1. 위의 data가 0에서 255사이값을 갖으므로, 128을 빼서 -128에서 127값을
갖게한다. 이렇게하여 FDCT를 거치면 64개 값의 평균값은 DC성분으로 나올
것이다. 다음은 128을 뺀 값이다.

-10 -37 -5 -3 -4 -14 -11 -24
-28 -35 -40 -43 -41 -28 -13 -23
-34 -27 -50 -29 -16 -41 -19 -13
-24 -46 -45 -50 -36 -10 -4 -40
-9 -35 -29 -24 -52 -17 -42 -16
-45 -9 -24 -36 -17 -52 -16 -28
-31 -43 -38 -28 -22 -3 -5 -42
-29 -42 -43 -23 -47 -29 -13 -9

2. FDCT를 한다. 다음은 FDCT를 한 결과이다. 맨왼쪽 맨위쪽의 -217은 주파수가
0인 성분, 즉 DC성분이다. 나머지들은 모두 AC성분들이다.

-217.625 -32.686 15.582 16.972 -1.376 21.802 -7.132 2.729
15.022 5.594 -3.423 3.416 7.983 -1.074 3.717 10.550
21.737 -8.150 -13.483 -6.075 6.168 13.366 -0.490 3.289
23.404 24.748 -19.724 -10.992 -5.045 -3.321 7.425 9.585
12.124 4.600 4.754 4.605 6.875 20.625 30.096 -12.687
14.610 -9.347 -27.242 27.260 -9.347 7.631 -4.987 14.890
10.343 6.876 -4.990 -29.439 16.523 -18.653 -24.266 11.388
13.292 6.131 -5.968 -2.067 20.673 1.179 14.921 -16.733



3. 다음에는 quantization table을 사용해서 quantize한다. 여기서
quantization
이란 각각의 DC, AC성분 값들을 어떤 값으로 나눈다음, 정수화하는 것을
말한다.
quantization table은 각각의 성분들이 얼마나 중요하느냐에 따라 정해진다.
quantization을 심하게 하면 이미지 품질이 떨어지고, quantization을 약하게
하면 압축능률이 떨어진다. 이 quantization table은 jpeg file의 헤더에
들어가 있어, decompressor는 이미지를 복원시에는 각각의 계수를 이
quantization table값으로 곱할 것이다.


8 6 6 7 6 5 8 7
7 7 9 9 8 10 12 20
13 12 11 11 12 25 18 19
15 20 29 26 31 30 29 26
28 28 32 36 46 39 32 34
44 35 28 28 40 55 41 44
48 49 52 52 52 31 39 57
61 56 50 60 46 51 52 50

Quantization Table

위와 같은 quantization table을 사용하여 quantization을 하면

-27 -5 2 2 0 4 0 0
2 0 0 0 0 0 0 0
1 0 -1 0 0 0 0 0
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

가 된다.



4. 그 다음에는 DC성분을 "바로전의 블락의 DC"성분값으로 뺀다(subtract).
지금
계산하고 있는 블락이 이미지의 첫 블락인 경우에는 "바로전의 블락"이라는
것이 없으므로 0을 뺀다. DC성분의 값들이란 것이 보통 값이 크기 때문에
"현재값과 이전값의 차이를 코딩하는" ADPCM처럼 DC의 차이값을 저장하여
값의 크기를 줄이려는 것이다.


5. 그 다음에는 다음의 그림처럼 zigzag식으로 순서를 매긴다.

+----+----+----+----+----+----+----+----+
| 0 | 1 |5 |6 | 14 | 15 | 27 | 28 |
+----+----+----+----+----+----+----+----+
| 2 | 4 | 7 |13 | 16 | 26 | 29 | 42 |
+----+----+----+----+----+----+----+----+
| 3 | 8 | 12 | 17 | 25 | 30 | 41 | 43 |
+----+----+----+----+----+----+----+----+
|9 | 11 | 18 | 24 | 31 | 40 | 44 | 53 |
+----+----+----+----+----+----+----+----+
| 10 | 19 | 23 | 32 | 39 | 45 | 52 | 54 |
+----+----+----+----+----+----+----+----+
| 20 | 22 | 33 | 38 | 46 | 51 | 55 | 60 |
+----+----+----+----+----+----+----+----+
| 21 | 34 | 37 | 47 | 50 | 56 | 59 | 61 |
+----+----+----+----+----+----+----+----+
| 35 | 36 | 48 | 49 | 57 | 58 | 62 | 63 |
+----+----+----+----+----+----+----+----+

그럼 블락은


-27 -5 2 1 0 2 2 0
0 1 0 1 -1 0 0 4
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

처럼 된다.

그 다음에는 다음처럼 "zero run length encoding"(zero 데이터가 몇번 나왔고
어떤 데이터가 몇번 나왔고... 하는 방법으로 encoding하는 방법)을 한다.

-27 0 -5 0 2 0 1 1 2 0 2
2 1 1 1 0 -1 2 4 0 0

위의 숫자들은 다음을 뜻한다.


1. DC성분은 -27이다.
2. AC성분 0이 0개 이후에는, AC성분 -5가 온다.
3. AC성분 0이 0개 이후에는, AC성분 2가 온다.
4. AC성분 0이 0개 이후에는, AC성분 1가 온다.
5. AC성분 0이 1개 이후에는, AC성분 2가 온다.
6. AC성분 0이 0개 이후에는, AC성분 2가 온다.
7. AC성분 0이 2개 이후에는, AC성분 1가 온다.
8. AC성분 0이 1개 이후에는, AC성분 1가 온다.
9. AC성분 0이 0개 이후에는, AC성분 -1가 온다.
10. AC성분 0이 2개 이후에는, AC성분 4가 온다.
11. 나머지 AC성분들은 모두 0이다.


6. 그다음에는 "run length encoding"되어 나온 계수들(-5, 2, 1, 2, 2, 1
등등)은 "가변 길이의, 즉 길이가 정해지지 않는" 이진 숫자들로 변환과정을
거친다. 다시 말하면, 이들 계수 c는 다음처럼 변환된다.

c가 0보다 크면 첫번째 비트는 '1'이고, 우리가 아는 이진숫자의 형태를
갖는다.
예를들어 5인 경우 101으로 된다.

c가 0보다 작으면, c 첫번째 비트는 '0'이다.(음수의 경우 "1의 보수"와 상관이
있음을 알 수 있을 것이다)

즉
-17 01110
-16 01111
-15 0000
-14 0001
-13 0010
-12 0011
-11 0100
-10 0101
-9 0110
-8 0111
-7 000
-6 001
-5 010
-4 011
-3 00
-2 01
-1 0
0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
16 10000

[table_1]

위의 변환테이블처럼 변환된다.

복원과정은 "양수"인 경우는 신경을 안써도 되고, 음수인 경우는 (-14였던
0001의 경우...)

(a) 0001에 1을 더한다. 그러면 0010이 된다.
(b) 0010앞에 1을 앞쪽에 padding시킨다. 그러면 11110010이 된다.
(c) 11110010은 0xf2가 되어 unsigned char인 경우, -14가 된다.




8. 위의 "bitstring 계수"들의 비트 갯수들은 "zero run length"와 결합된다.
윗쪽 바이트(즉 0xf0의 위치에 있는 곳)는 "zero run length,
즉 0의 반복횟수"를 나타내고, 아랫쪽 바이트(즉 0x0f의 위치에 있는 곳)은
bitstring된 AC계수의 비트의 갯수를 나타낸다.


특별히 신경써야 하는 부분도 있는데,

(a) "zero run length"와 "bitstring의 길이"가 모두 0인 경우에는, 그 다음
나머지 모든 AC계수가 0이라는 것을 나타낸다.

(b) "zero run length"가 15이고, "bitstring의 길이"가 0인 경우에는,
"zero run length"가 16이라는 의미이다.


결국
(a) "(아까 설명한 대로 ADPCM처럼 변환되었던) DC성분의 길이"와
(b) "zero run length" + "bitstring의 길이"
가 entropy encoding된다.

entropy encoding이란 "자주 반복하는 데이터"에게는
짧은 비트열을, "자주 등장하지 않는 데이터에게는" 긴 비트열을 할당해서
인코딩하는 방법이다. JFIF에서는 entropy coding방법으로 Huffman코딩 방식을
사용한다.

Huffman coding방법이라는 것은, 어떤 데이터 집합과 그리고 그 데이터들의
각각의 출현확률이 정해져 있을때, 각 데이타 당 필요로 하는 비트 숫자를
최소화할 수 있는 code set을 찾는 방법이다.


huffman(x)를 x를 huffman coding시킨 bitstring을 나타낸다고 하고,
table_1(x)을 [table_1]을 통해 얻은 bitstring을 나타낸다고 하고,
bit_length(x)을 x라는 bitstring의 길이를 나타낸다고 하면,


결국

=======
-27 0 -5 0 2 0 1 1 2 0 2
2 1 1 1 0 -1 2 4 0 0
=======
은

huffman(bit_length(-27),
table_1(-27),

huffman((0 << 4) + bit_length(table_1(-5))),
table_1(-5),
huffman((0 << 4) + bit_length(table_1(2))),
table_1(2),
huffman((0 << 4) + bit_length(table_1(1))),
table_1(1),
huffman((1 << 4) + bit_length(table_1(2))),
table_1(2),
huffman((0 << 4) + bit_length(table_1(2))),
table_1(2),

huffman((2 << 4) + bit_length(table_1(1))),
table_1(1),
huffman((1 << 4) + bit_length(table_1(1))),
table_1(1),
huffman((0 << 4) + bit_length(table_1(-1))),
table_1(-1),
huffman((2 << 4) + bit_length(table_1(4))),
table_1(4),
huffman((0 << 4) + 0);

의 순서대로 저장될 것이다.