WebP의 Lossless Compression
WebP 이미지 포맷의 lossless compression은 여러 단계의 변환(transform)을 거친 후 entropy coding을 통해 완성된다.
Entropy coding 이전에 적용될 수 있는 변환들을 요약해보면 다음과 같다.
- Spatial transform: 이웃한 pixel 간의 연관성을 이용해 entropy를 줄이는 단계
- Color transform: R, G, B 값을 decorrelate 시키는 단계
- Green subtract transform: 각 R, B 값에서 G 값을 뺌
- Color indexing transform: 사용된 색의 종류가 적을 때, color array와 index로 치환하는 변환
그리고 이미지를 encoding 하는 데에는 다음과 같은 방법이 사용된다.
- Huffman coded literal
- LZ77 backward reference: 반복된 pixel 값을 length, distance로 표현하는 방법
- Color cache coding: 이전에 나타난 pixel 값들을 LRU 캐싱하여 새로운 pixel을 reconstruct 할 때 사용하는 방식
Google의 documentation을 참고하여 글을 작성하지만, 나도 아직 이해하지 못한 부분이 많아 번역한 정보의 나열 형식이 될 것 같다. (ㅠㅠ)
이 글 이상의 상세 내용이 필요한 사람은 아래 링크들을 참고하기 바란다.
1. Trnasforms
1.1 Predictor (Spatial) Transform
Spatial prediection은 이웃한 pixel들이 서로 연관(correlate)되어 있다는 것을 활용한, entropy를 줄이는 변환 과정이다.
일전의 PNG의 filtering이나 WebP lossy compression의 intra-prediction와 크게 다르지 않다.
아래 pixel의 연속을 살펴보자. (O는 decoding된 pixel, X는 아직 decoding 되지 않은 pixel이다.)
O O O O O O O O O O O
O O O O O O O O O O O
O O O O TL T TR O O O O
O O O O L P X X X X X
X X X X X X X X X X X
X X X X X X X X X X XTarget pixel P는 이미 decoding된 pixel로부터 prediction 하게 되고 (scan-line 순서), 실제 값과 예측 값의 차이(residual)만 encoding 하는 것이다.
또한 어떤 prediction mode*를 사용했는지에 따라 여러 개의 사각형 구역으로 나뉘게 된다.
(* 예를 들어, left(L), top(T), top-left(TL), top-right(TR) 등이 있다. 더 자세한 mode들은 Link 참고)
이런 식으로 residual만 남기게 되면 pixel 간의 correlation이 반영돼 entropy가 낮아지게 되고, 이후의 압축 효율은 좋아진다!
1.2 Color (de-correlation) Transform
Color transform의 목적은 각 픽셀의 R, G, B 값을 decorrelate 시키는 것이다.
Green(G) 값은 그대로 두고, blue(B)를 G를 기준으로 변환하고, red(R)를 G 기준으로 변환한 다음 또 B 기준으로 변환한다. (아니, 오히려 더 correlate 시키는거 아닌가? ㅠㅠ)
좀 더 자세하게 살펴보자.
우선 Predictor transform과 마찬가지로 같은 transform mode를 사용하는 block들로 나눠지는데, 여기에는 Color transform element가 3가지 존재한다
typedef struct {
uint8 green_to_red;
uint8 green_to_blue;
uint8 red_to_blue;
} ColorTransformElement;나누어진 각 block에는 고정된 값을 가지는 green_to_red, green_to_blue, red_to_blue를 가지고 delta를 계산하여 red, blue 각각에 더해준다.
어떻게 동작하는 지는 아래 C 코드를 참고하자.
void ColorTransform(uint8 red, uint8 blue, uint8 green,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
uint32 tmp_red = red;
uint32 tmp_blue = blue;
// Applying transform is just adding the transform deltas
tmp_red += ColorTransformDelta(trans->green_to_red, green);
tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
tmp_blue += ColorTransformDelta(trans->red_to_blue, red);
*new_red = tmp_red & 0xff;
*new_blue = tmp_blue & 0xff;
}
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}이러한 과정이 R, G, B를 decorrelate 시키기 위함이라고 하는데, 아직 왜 필요한 지 이해를 잘 못하겠다. 그리고 이 과정을 decorrelate라고 하는 이유도. 이렇게 하면 압축이 더 잘 되기 때문일텐데, 왜일까? 후에 이해한다면 수정해놓겠다. (TODO!)
1.3 Subtract Green Transform
Subtract green transform은 각 픽셀의 red, blue 값을 green 값으로 빼는 것을 의미한다.
이 transform이 존재한다면, decoder는 아래와 같이 red, blue에 green을 더해줘야한다.
void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
*red = (*red + green) & 0xff;
*blue = (*blue + green) & 0xff;
}이 변환은 먼저 설명한 color transform의 특별한 방법이라고 보면 된다. 하지만 여기는 동적인 부분도 없고 추가적인 데이터도 필요하지 않다. 즉, 더 간단하게 변환하기 때문에 종종 쓸모있다고 한다.
1.4 Color Indexing (plalette) Transform
만약 이미지가 지닌 pixel 값의 종류가 많지 않다면, color index table을 만들어 pixel 값을 table index로 치환하는 것이 좋을 것이다.
사실 이 과정은 어쩌면 너무나 익숙한 방식이다. GIF나 PNG에서 이미 사용하고 있는 방법이기 때문이다.
Color indexing transform은 이러한 과정을 지칭한다. 이미지에 사용된 unique한 ARGB 값의 수를 확인하고, 그 수가 threshold (256)보다 낮다면 color table을 만들어 pixel 값을 table index 값으로 치환시키는 것이다.
2. Encoding of Image Data
이미지는 우선 fixed-size block(보통 16x16)들로 나뉜다. 각 block은 각자의 entropy code를 이용해 모델링되며, 몇몇 block은 이를 공유할 수도 있다.
각 pixel은 3가지 방법 중 하나로 encoding 될 수 있다.
- Huffman coded literal: 각 채널이 독립적으로 entropy coding 된다.
- LZ77 backward reference: 이미지의 다른 곳에서 사용된 pixel 값을 복사한다.
- Color cache code: 최근 사용된 색이라면, color cache에서 가져온다.
2.1 LZ77 Backward Reference
Backward reference란 length와 distance의 조합이라고 생각하면 된다.
Length는 scan-line 상에서 pixel이 몇 개나 복사될 지를 나타내고, distance는 복사할 pixel이 이전에 어디 있었는지 그 위치를 나타낸다.
이 length와 distance는 LZ77의 prefix coding을 통해 저장된다.
LZ77 prefix coding은 큰 정수를 2 파트로 나눈다. (prefix code와 extra bits)
Prefix code는 entropy code를 통해 저장되고, extra bits는 entropy code 없이 있는 그대로 저장된다. (뭔 소리인지... 크흠)
2.2 Color Cache Coding
Color cache coding은 새로운 픽셀을 reconstruct 하기 위해 이미 사용한 이미지 일부분을 사용하는 것을 말한다.
즉, 사용한 color는 LRU cache에 등록하고, 다음 pixel에 사용될 경우 빠르게 lookup 할 수 있도록 하는 것이다. 물론 만약 hit 되지 않는다면 local palette를 사용할 수 있다.
아래 보이는 그림에서, 스캔이 진행됨에 따라 각 시점에 local color cache가 어떻게 갱신되는지 볼 수 있다.
(출처: developers.google.com)
Comment
어렵다. 후.
다행히 코드를 함께 보면서 조금 이해할 수는 있었다.
그렇지만 여전히 entropy coding 부분은 이해가 많이 부족한 것 같다.
많이 부족한 탓에 정보의 나열 식의 글이 되어버렸지만, 차차 개선해 나가자.
Reference
