지르키 알라쿠이얄라 박사, Google Inc., 2023년 3월 9일
개요
WebP 무손실은 ARGB 이미지의 무손실 압축을 위한 이미지 형식입니다. 이 무손실 형식은 완전히 투명한 픽셀에 대한 색상 값입니다. 순차적 데이터에 대한 범용 알고리즘 데이터 압축 (LZ77), 접두사 코딩 및 색상 캐시는 대량의 데이터 압축입니다. PNG보다 빠른 디코딩 속도 보다 높은 압축률을 자랑하며 25% 더 높은 압축률을 오늘의 PNG 형식입니다.
1 소개
이 문서에서는 무손실 WebP의 압축된 데이터 표현을 설명합니다. 이미지 이 문서는 WebP 무손실 인코더와 애플리케이션 아키텍처의 살펴보겠습니다.
이 문서에서는 C 프로그래밍 언어 구문을 광범위하게 사용하여
비트스트림을 확인하고 비트를 읽는 함수가 있다고 가정합니다.
ReadBits(n) 바이트는
각 바이트의 비트는 최소 유효 비트 우선 순서로 읽힙니다. 날짜
여러 비트가 동시에 읽히고, 정수는
원본 데이터로 변환합니다 반환된
정수는 원본 데이터의 최상위 비트이기도 합니다. 따라서
문
b = ReadBits(2);
위 문장은 아래의 두 문과 동일합니다.
b = ReadBits(1);
b |= ReadBits(1) << 1;
각 색상 구성요소, 즉 알파, 빨간색, 파란색, 녹색이 8비트 바이트를 사용하여 표현됩니다. 상응하는 유형을 uint8로 정의합니다. 가 전체 ARGB 픽셀은 부호 없는 픽셀인 uint32라는 유형으로 표현됩니다. 32비트로 구성된 정수입니다. 코드에서 이러한 값은 alpha(비트) 단위로 코드화됩니다. 31..24, 비트 23..16에서 빨간색, 비트 15..8에서 녹색, 비트 7..0에서 파란색, 하지만 형식의 구현은 내부적으로 다른 표현을 자유롭게 사용할 수 있습니다.
넓게 보면 WebP 무손실 이미지에는 헤더 데이터, 변환 정보 및 실제 이미지 데이터입니다. 헤더는 이미지의 너비와 높이를 포함합니다. WebP 무손실 이미지는 4개의 다른 유형의 변환을 거쳐 인코딩됩니다. 비트스트림의 변환 정보에는 필요한 역변환을 적용해야 합니다.
2 명명법
- ARGB : ARGB
- 알파, 빨간색, 녹색, 파란색 값으로 구성된 픽셀 값입니다.
- ARGB 이미지
- ARGB 픽셀을 포함하는 2차원 배열입니다.
- 색상 캐시
- 최근에 사용한 색상을 저장하기 위한 해시 주소가 지정된 작은 배열 더 짧은 코드로 다시 불러올 수 있습니다
- 색상 색인 생성 이미지
- 작은 정수를 사용하여 색인을 생성할 수 있는 색상의 1차원 이미지 (WebP 무손실 내 최대 256개)
- 색상 변환 이미지
- 다음과 같은 상관관계에 대한 데이터가 포함된 2차원 저해상도 이미지 색상 구성요소입니다.
- 거리 매핑
- 픽셀 값이 가장 작도록 LZ77 거리를 변경합니다. 2차원 근접도에 도움이 됩니다
- 엔트로피 이미지
- 어떤 엔트로피 코딩이 필요한지를 나타내는 2차원 저해상도 이미지 이미지의 정사각형마다 사용될 수 있어야 합니다. 즉, 각 픽셀은 접두사 코드.
- LZ77
- 사전 기반의 슬라이딩 윈도우 압축 알고리즘으로, 과거 기호의 시퀀스로 설명할 수 있습니다.
- 메타 접두어 코드
- 메타 접두사에서 요소의 색인을 생성하는 작은 정수 (최대 16비트)입니다. 표를 참고하세요.
- 예측기 이미지
- 어떤 공간 예측자를 나타내는 2차원 저해상도 이미지 정사각형에 사용됩니다
- 프리픽스 코드
- 더 적은 수의 비트가 사용되는 엔트로피 코딩을 수행하는 일반적인 방법 더 자주 사용하는 코드를 확인하세요.
- 접두어 코딩
- 더 큰 정수를 엔트로피로 코딩하여 정수의 몇 비트를 코딩하는 방법 암호화하고 나머지 비트를 원시로 코드화합니다. 이렇게 하면 엔트로피 코드에 대한 설명이 작을 때에도 비교적 작게 유지되도록 기호의 범위가 넓습니다.
- 스캔줄 순서
- 픽셀의 처리 순서 (왼쪽에서 오른쪽 및 상단에서 하단)로 드래그 앤 드롭합니다. 행이 완료되면 다음 행의 왼쪽 열에 표시됩니다.
3 RIFF 헤더
헤더의 시작 부분에는 RIFF 컨테이너가 있습니다. 이것은 다음과 같습니다.
- 문자열 'RIFF'입니다.
- 청크 길이의 32비트 리틀 엔디언 값으로, 전체 크기입니다. 30비트 필드입니다. 일반적으로 이 값은 페이로드 크기 (파일 크기 - 8바이트: 'RIFF'의 경우 4바이트 4바이트)을 제공합니다.
- 문자열 'WEBP' (RIFF 컨테이너 이름)
- 문자열 'VP8L' (무손실 인코딩된 이미지 데이터의 경우 FourCC).
- 무손실 스트림은 필수입니다.
- 1바이트 서명 0x2f
비트스트림의 처음 28비트는 이미지의 너비와 높이를 지정합니다. 너비와 높이는 다음과 같이 14비트 정수로 디코딩됩니다.
int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;
이미지 너비와 높이의 14비트 정밀도는 WebP 무손실 이미지를 16384✕16384픽셀로 변환합니다.
alpha_is_used 비트는 힌트일 뿐이며 디코딩에 영향을 주지 않습니다. 또한 0으로 설정해야 합니다.
int alpha_is_used = ReadBits(1);
version_number는 0으로 설정해야 하는 3비트 코드입니다. 다른 모든 값은 오류로 취급해야 합니다
int version_number = ReadBits(3);
변환 4개
변환은 이미지 데이터를 가역적으로 조작하여 텍스트 데이터에서 인트로피를 생성합니다. 그들은 최종 압축을 더 조밀하게 만들 수 있습니다.
이미지는 네 가지 유형의 변환을 거칠 수 있습니다. 1 비트는 변환의 존재 여부에 따라 달라집니다 각 변환은 한 번만 사용할 수 있습니다. 이 변환은 기본 수준 ARGB 이미지에만 사용됩니다. 서브해상도 이미지를 (색상 변환 이미지, 엔트로피 이미지, 예측자 이미지)에는 변환이 없습니다. 변환의 끝을 나타내는 0 비트도 아닙니다.
일반적으로 인코더는 이러한 변환을 사용하여 섀넌 엔트로피를 줄입니다. 추출해야 합니다. 또한 변환 데이터는 엔트로피를 기준으로 최소화합니다
while (ReadBits(1)) { // Transform present.
// Decode transform type.
enum TransformType transform_type = ReadBits(2);
// Decode transform data.
...
}
// Decode actual image data (Section 5).
변환이 존재하는 경우, 다음 두 비트는 변환 유형을 지정합니다. 변환에는 4가지 유형이 있습니다.
enum TransformType {
PREDICTOR_TRANSFORM = 0,
COLOR_TRANSFORM = 1,
SUBTRACT_GREEN_TRANSFORM = 2,
COLOR_INDEXING_TRANSFORM = 3,
};
변환 유형 다음에 변환 데이터가 나옵니다. 데이터 변환에 포함 역변환을 적용하는 데 필요한 정보와 변환 유형입니다. 역변환은 비트스트림에서 먼저 읽혀집니다.
다음으로 다양한 유형의 변환 데이터를 설명합니다.
4.1 예측자 변환
예측자 변환은 엔트로피를 줄이는 데 사용될 수 있으므로 더 크다는 것을 의미합니다. 예측기 변환에서 이미 디코딩된 픽셀 (스캔 라인에서)에서 현재 픽셀 값이 예측됩니다. 잔차 값 (실제 - 예측)만 인코딩됩니다. 그린 구성요소는 픽셀 내에서 14개의 예측자 중 어떤 것이 ARGB 이미지의 특정 블록을 나타냅니다. 예측 모드는 지정할 수도 있습니다 이미지를 정사각형으로 나눈 다음 동일한 예측 모드를 사용합니다
예측 데이터의 처음 3비트는 블록 너비와 높이를 숫자로 정의 비트의 숫자입니다.
int size_bits = ReadBits(3) + 2;
int block_width = (1 << size_bits);
int block_height = (1 << size_bits);
#define DIV_ROUND_UP(num, den) (((num) + (den) - 1) / (den))
int transform_width = DIV_ROUND_UP(image_width, 1 << size_bits);
변환 데이터에는 이미지의 각 블록에 대한 예측 모드가 포함됩니다. 그것은
은 픽셀의 녹색 구성요소가 픽셀의
14개의 예측자가 내부의 모든 block_width * block_height 픽셀에 사용됩니다.
ARGB 이미지의 특정 블록을 나타냅니다. 이 저해상도 이미지는
5장에 설명된 것과 동일한 기술을 사용해야 합니다.
블록 열의 수 transform_width는 2차원으로 사용됩니다.
있습니다. 픽셀 (x, y)의 경우 각 필터 블록을 계산할 수 있습니다.
주소 추가:
int block_index = (y >> size_bits) * transform_width +
(x >> size_bits);
예측 모드에는 14가지가 있습니다. 각 예측 모드에서 현재 픽셀 값은 값이 다음과 같은 하나 이상의 인접 픽셀에서 예측됩니다. 있습니다.
현재 픽셀 (P)의 인접 픽셀 (TL, T, TR, L)을 다음과 같습니다.
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 X
여기서 TL은 왼쪽 상단, T는 상단, TR은 오른쪽 상단, L은 왼쪽 상단을 의미합니다. 위치 모든 O, TL, T, TR, L 픽셀은 이미 처리되고 P 픽셀과 모든 X 픽셀을 알 수 없습니다.
앞서 살펴본 이웃 픽셀을 고려했을 때, 다양한 예측 모드는 정의하는 것으로 정의됩니다.
| 모드 | 현재 픽셀의 각 채널의 예측 값 |
|---|---|
| 0 | 0xff000000 (ARGB의 검은색 단색을 나타냄) |
| 1 | L |
| 2 | T |
| 3 | 튀르키예 |
| 4 | TL : 팀 리더 |
| 5 | 평균2(평균2(L, TR), T) |
| 6 | 평균2(L, TL) |
| 7 | 평균2(L, T) |
| 8 | 평균2(TL, T) |
| 9 | 평균2(T, TR) |
| 10 | 평균2(평균2(L, TL), 평균2(T, TR)) |
| 11 | 선택(L, T, TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Average2(L, T), TL) |
Average2는 각 ARGB 구성요소에서 다음과 같이 정의됩니다.
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
선택 예측자는 다음과 같이 정의됩니다.
uint32 Select(uint32 L, uint32 T, uint32 TL) {
// L = left pixel, T = top pixel, TL = top-left pixel.
// ARGB component estimates for prediction.
int pAlpha = ALPHA(L) + ALPHA(T) - ALPHA(TL);
int pRed = RED(L) + RED(T) - RED(TL);
int pGreen = GREEN(L) + GREEN(T) - GREEN(TL);
int pBlue = BLUE(L) + BLUE(T) - BLUE(TL);
// Manhattan distances to estimates for left and top pixels.
int pL = abs(pAlpha - ALPHA(L)) + abs(pRed - RED(L)) +
abs(pGreen - GREEN(L)) + abs(pBlue - BLUE(L));
int pT = abs(pAlpha - ALPHA(T)) + abs(pRed - RED(T)) +
abs(pGreen - GREEN(T)) + abs(pBlue - BLUE(T));
// Return either left or top, the one closer to the prediction.
if (pL < pT) {
return L;
} else {
return T;
}
}
ClampAddSubtractFull 및 ClampAddSubtractHalf 함수가 실행됩니다.
각 ARGB 구성요소에 대해 다음과 같이 안내합니다.
// Clamp the input value between 0 and 255.
int Clamp(int a) {
return (a < 0) ? 0 : (a > 255) ? 255 : a;
}
int ClampAddSubtractFull(int a, int b, int c) {
return Clamp(a + b - c);
}
int ClampAddSubtractHalf(int a, int b) {
return Clamp(a + (a - b) / 2);
}
일부 테두리 픽셀에는 특별한 처리 규칙이 있습니다. 만약 예측자 변환을 사용하여 이러한 픽셀의 모드 [0..13] 에 관계없이 이미지의 맨 왼쪽 상단 픽셀에 대한 예측값이 모두 0xff000000인 경우 맨 위 행의 픽셀은 L픽셀이고, 맨 왼쪽 열의 모든 픽셀은 T픽셀
가장 오른쪽 열에 있는 픽셀의 TR 픽셀을 처리하는 것은 탁월합니다. 맨 오른쪽 열의 픽셀은 [0..13]을 나타낼 수 있습니다. 대신 현재 픽셀과 동일한 행이 TR 픽셀로 사용됩니다.
최종 픽셀 값은 예측값의 각 채널을 더하여 얻습니다. 인코딩된 잔차 값으로 변환합니다.
void PredictorTransformOutput(uint32 residual, uint32 pred,
uint8* alpha, uint8* red,
uint8* green, uint8* blue) {
*alpha = ALPHA(residual) + ALPHA(pred);
*red = RED(residual) + RED(pred);
*green = GREEN(residual) + GREEN(pred);
*blue = BLUE(residual) + BLUE(pred);
}
4.2 색상 변환
색상 변환의 목표는 각 색상의 R, G, B 값을 데코레이션하는 것입니다. Pixel 색 변환은 녹색 (G) 값을 그대로 유지하고, 빨간색 (R) 값은 녹색으로, 파란색 (B) 값은 적색 값을 번갈아 가면서 나타납니다.
예측자 변환의 경우와 마찬가지로 먼저 이미지를 블록의 모든 픽셀에 동일한 변환 모드가 사용됩니다. 대상 세 가지 유형의 색 변환 요소가 있습니다.
typedef struct {
uint8 green_to_red;
uint8 green_to_blue;
uint8 red_to_blue;
} ColorTransformElement;
실제 색상 변환은 색상 변환 델타를 정의하여 수행됩니다. 이
색 변환 델타는 동일한 ColorTransformElement에 종속됩니다.
할 수 있습니다. 델타는
색 변환입니다. 그러면 반전 색상 변환은 이러한 델타를 추가하기만 합니다.
색상 변환 함수는 다음과 같이 정의됩니다.
void ColorTransform(uint8 red, uint8 blue, uint8 green,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
int tmp_red = red;
int tmp_blue = blue;
// Applying the transform is just subtracting 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;
}
ColorTransformDelta는
3.5 고정 소수점 숫자 및 부호 있는 8비트 RGB 색상 채널 (c) [-128..127]
다음과 같이 정의됩니다.
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
8비트 부호 없는 표현 (uint8)에서 부호 있는 8비트 표현으로 변환
ColorTransformDelta()를 호출하려면 1 (int8)이 필요합니다. 부호 있는 값
8비트 2의 보수 (즉, uint8 범위)로 해석되어야 합니다.
[128..255] 는 변환된 int8 값의 [-128..-1] 범위에 매핑됩니다.
곱셈은 더 높은 정밀도 (최소 16비트 정밀도). Shift 연산의 부호 확장 속성이 중요하지 않습니다. 여기에서 결과에서 최하위 8비트만 사용되고 거기에 부호가 있습니다. 확장 프로그램 이동과 부호 없는 이동은 서로 일치합니다.
이제 디코딩이 디코더에 적용되도록 할 수 있도록 색 변환 데이터의 콘텐츠를 반전 색상 변환을 사용하여 원래 빨간색 및 파란색 값을 복구합니다. 이 색 변환 데이터의 처음 3비트는 비트 수로 표현됩니다. 이는 예측자 변환과 같습니다.
int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;
색상 변환 데이터의 나머지 부분에는 ColorTransformElement가 포함됩니다.
각 블록에 해당하는 인스턴스입니다 각
ColorTransformElement 'cte'는 하위 해상도 이미지에서 픽셀로 처리됩니다.
알파 구성요소가 255, 빨간색 구성요소는 cte.red_to_blue, 초록색
구성요소는 cte.green_to_blue이고 파란색 구성요소는 cte.green_to_red입니다.
디코딩 중에 블록의 인스턴스 ColorTransformElement개가 디코딩되고
픽셀의 ARGB 값에 역색 변환이 적용됩니다. 따라서
반전 색상 변환은
ColorTransformElement 값을 빨간색 및 파란색 채널로 변환합니다. 알파 및 녹색
그대로 유지됩니다
void InverseTransform(uint8 red, uint8 green, uint8 blue,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
int tmp_red = red;
int tmp_blue = blue;
// Applying the inverse transform is just adding the
// color 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, tmp_red & 0xff);
*new_red = tmp_red & 0xff;
*new_blue = tmp_blue & 0xff;
}
4.3 녹색 변환 빼기
녹색 뺄셈 변환은 표시됩니다. 이 변환이 있으면 디코더는 값을 빨간색과 파란색 값으로 변경합니다. 이와 관련된 데이터가 없습니다. 사용됩니다. 디코더는 다음과 같이 역변환을 적용합니다.
void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
*red = (*red + green) & 0xff;
*blue = (*blue + green) & 0xff;
}
이 변환은 색상 변환을 사용하여 모델링할 수 있으므로 중복되지만 여기에는 추가 데이터가 없으므로 녹색의 뺄셈 변환은 더 적은 비트를 사용하여 코딩한다는 것을 의미합니다.
4.4 색상 색인 변환
고유한 픽셀 값이 많지 않은 경우 픽셀 값을 색상 색인 배열을 사용하고 픽셀 값을 배열의 색인으로 대체합니다. 색상 이를 수행합니다 (WebP 무손실의 맥락에서 구체적으로는 이를 팔레트 변환이라고 하지 마세요. WebP 무손실 인코딩에 있는 색상 캐시라는 동적 개념이 있습니다.)
색상 색인 변환은 이미지 이 값이 임곗값 (256)보다 작으면 256으로 구성된 ARGB 값이며, 이는 픽셀 값을 해당하는 색인: 픽셀의 녹색 채널이 모든 알파 값은 255로, 빨간색과 파란색 값은 모두 0으로 설정됩니다.
변환 데이터에는 색상 표 크기와 색상의 항목이 포함됩니다. 표에서 볼 수 있습니다. 디코더는 다음과 같이 색상 색인 변환 데이터를 읽습니다.
// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;
색상 표는 이미지 저장소 형식 자체를 사용하여 저장됩니다. 색상 표
RIFF 헤더, 이미지 크기 및
높이가 1픽셀이고 너비가 color_table_size이라고 가정합니다.
색상 표는 이미지 엔트로피를 줄이기 위해 항상 뺄셈으로 코딩됩니다. 델타
일반적으로 색상보다 엔트로피가 훨씬 적은 비율
작은 이미지의 경우 비용을 크게 절약할 수 있습니다. 디코딩 시
색상 표의 모든 최종 색상은 이전 셀에
각 ARGB 구성요소의 색상 구성요소 값을 개별적으로 저장하고
결과의 중요 8 비트.
이미지에 대한 역변환은 단순히 픽셀 값( 는 색상표에 대한 색인입니다.) 색인 생성 ARGB 색상의 녹색 구성요소를 기반으로 진행됩니다
// Inverse transform
argb = color_table[GREEN(argb)];
색인이 color_table_size 이상인 경우 argb 색상 값입니다.
0x00000000 (투명한 검은색)으로 설정해야 합니다.
색상 표가 작은 경우 (16 색상 이하) 여러 픽셀 단일 픽셀로 번들화됩니다. Pixel 번들은 여러 개 (2, 4, 8)를 픽셀을 단일 픽셀로 변환하여 이미지 너비를 각각 줄입니다. 픽셀 번들링을 통해 임베딩 레이어의 보다 효율적인 65픽셀을 사용하고, 산술적 코딩과 같은 이점을 고유값이 16개 이하인 경우에만 사용할 수 있습니다.
color_table_size는 결합된 픽셀 수를 지정합니다.
int width_bits;
if (color_table_size <= 2) {
width_bits = 3;
} else if (color_table_size <= 4) {
width_bits = 2;
} else if (color_table_size <= 16) {
width_bits = 1;
} else {
width_bits = 0;
}
width_bits의 값은 0, 1, 2 또는 3입니다. 값 0은 픽셀이 없음을 나타냅니다.
이미지에 대해 번들링이 수행되어야 합니다. 값이 1이면 두 픽셀이
각 픽셀의 범위는 [0..15]입니다. 값 2는
네 개의 픽셀이 결합되어 있고, 각 픽셀의 범위는 [0..3]입니다. 값 3
는 8개의 픽셀이 결합되어 있고 각 픽셀의 범위가 [0..1]임을 나타냅니다.
바이너리 값을 의미합니다
값은 다음과 같이 녹색 구성요소로 채워집니다.
width_bits= 1: 모든 x 값에 대해 x 게재됩니다. 0 (mod 2)인 경우 녹색 x의 값은 x + 1의 녹색 값은 x / 2에서 녹색 값의 최상위 비트 4개.width_bits= 2: 모든 x 값에 대해 x 게재됩니다. 0 (mod 4)인 경우 녹색 x의 값은 x + 1 ~ x + 3의 녹색 값은 x / 4에서 녹색 값의 더 중요한 비트로 올립니다.width_bits= 3: 모든 x 값에 대해 x 게재됩니다. 0 (mod 8)인 경우 녹색 x의 값은 녹색의 최하위 비트에 배치됩니다. x + 1 ~ x + 7의 녹색 값은 순서대로 배치됩니다. x / 8에서 녹색 값의 더 중요한 비트로 전달됩니다.
이 변환을 읽은 후 image_width는 width_bits에 의해 서브 샘플링됩니다. 이
후속 변환의 크기에 영향을 줍니다. 새 크기는
앞에 정의된 DIV_ROUND_UP입니다.
image_width = DIV_ROUND_UP(image_width, 1 << width_bits);
5 이미지 데이터
이미지 데이터는 스캔 라인 순서대로 된 픽셀 값의 배열입니다.
5.1 이미지 데이터의 역할
이미지 데이터는 다음과 같은 5가지 역할로 사용됩니다.
- ARGB 이미지: 이미지의 실제 픽셀을 저장합니다.
- 엔트로피 이미지: 메타 접두어 코드를 저장합니다 (자세한 내용은 'Decoding of Meta Prefix Codes').
- 예측자 이미지: 예측자 변환의 메타데이터를 저장합니다 (자세한 내용은 "예측자 변환")을 포함해야 합니다.
- 색상 변환 이미지:
ColorTransformElement값으로 생성됨 ('Color Transform'에 정의됨)이 포함되어 있습니다. 이미지를 생성합니다. - 색상 색인 생성 이미지:
color_table_size크기의 배열 (최대 256ARGB) 색상 색인 변환을 위한 메타데이터를 저장하는 데 사용됩니다 (자세한 내용은 "Color Indexing 변환")
5.2 이미지 데이터 인코딩
이미지 데이터의 인코딩은 역할과 무관합니다.
이미지는 먼저 고정 크기 블록 세트 (일반적으로 16x16픽셀)로 나뉩니다. 블록)을 사용합니다. 이러한 각 블록은 자체 엔트로피 코드를 사용하여 모델링됩니다. 또한 여러 블록이 동일한 엔트로피 코드를 공유할 수 있습니다.
사유: 엔트로피 코드를 저장하면 비용이 발생합니다. 이러한 비용은 통계적으로 유사한 블록이 엔트로피 코드를 공유하는 경우 해당 코드를 한 번만 사용할 수 있습니다. 예를 들어 인코더가 유사한 블록을 클러스터링하여 찾을 수 있고 데이터를 모으기 위해 데이터를 무작위로 섞는 것을 인코딩에 필요한 전체 비트 양을 줄일 때 이미지
각 픽셀은 다음 세 가지 메서드 중 하나를 사용하여 인코딩됩니다.
- 접두사로 코딩된 리터럴: 각 채널 (녹색, 빨간색, 파란색, 알파)은 독립적으로 코딩됩니다.
- LZ77 역참조: 일련의 픽셀이 참조의 다른 곳에서 복사됨 이미지
- 색상 캐시 코드: 짧은 곱셈 해시 코드 (색상 캐시)를 사용하여 인덱스)를 나타냅니다.
다음 하위 섹션에서는 각각에 대해 자세히 설명합니다.
5.2.1 프리픽스로 코딩된 리터럴
픽셀은 녹색, 빨간색, 파란색 및 알파라는 접두사 코딩된 값( 해당 주문)을 클릭합니다. 자세한 내용은 섹션 6.2.3을 참고하세요. 확인하세요.
5.2.2 LZ77 역참조
역참조는 길이 및 거리 코드의 튜플입니다.
- 길이는 스캔 행 순서에서 복사할 픽셀 수를 나타냅니다.
- 거리 코드는 이전에 본 차량의 위치를 나타내는 숫자입니다. 복사됩니다. 정확한 매핑은 아래에 설명되어 있습니다.
길이 및 거리 값은 LZ77 접두어 코딩을 사용하여 저장됩니다.
LZ77 접두사 코딩은 큰 정수 값을 두 부분, 즉 접두사 코드 및 추가 비트입니다. 접두어 코드는 엔트로피 코드를 사용하여 저장되며 추가 비트는 엔트로피 코드 없이 그대로 저장됩니다.
사유: 이 접근 방식은 엔트로피의 저장 요구사항을 줄여줍니다. 생성합니다. 또한 큰 값은 일반적으로 드물기 때문에 추가 비트는 값이 거의 없습니다. 따라서 이 접근 방식은 크게 다르지 않습니다
다음 표는 접두사 코드 및 값이 다를 수 있습니다.
| 값 범위 | 프리픽스 코드 | 추가 비트 |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 0 |
| 3 | 2개 | 0 |
| 4 | 3 | 0 |
| 5..6 | 4 | 1 |
| 7..8 | 5 | 1 |
| 9..12 | 6 | 2 |
| 2013년 13월 16일 | 7 | 2 |
| ... | ... | ... |
| 3072..4096 | 23 | 10 |
| ... | ... | ... |
| 524289..786432 | 38 | 18 |
| 786433..1048576 | 39 | 18 |
접두사 코드에서 (길이 또는 거리) 값을 얻기 위한 의사코드는 다음과 같습니다. 다음과 같습니다.
if (prefix_code < 4) {
return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;
거리 매핑
앞서 언급했듯이 거리 코드는 해당 지점의 위치를 나타내는 숫자입니다. 이전에 표시된 픽셀에서 픽셀을 복사할 수 있습니다. 이 하위 섹션 는 거리 코드와 이전 시점의 위치 사이의 매핑을 정의합니다. Pixel
120보다 큰 거리 코드는 스캔 라인 순서로 픽셀 거리를 나타냅니다. 120만큼 오프셋됩니다.
최소 거리 코드 [1..120] 은 특수 코드이며 될 수 있습니다. 이 인근 지역은 다음과 같이 120픽셀로 구성됩니다.
- 현재 픽셀보다 1~7행 위에 있고 최대 8열인 픽셀
왼쪽으로 또는 현재 픽셀에서 최대 7개 열까지 지정할 수 있습니다. [총계
이러한 픽셀 =
7 * (8 + 1 + 7) = 112]이어야 합니다. - 현재 픽셀과 같은 행에 있고 최대 8픽셀인 픽셀
열을 현재 픽셀의 왼쪽에 표시합니다. [이러한 픽셀
8개]
거리 코드 distance_code과 주변 픽셀 간의 매핑
오프셋 (xi, yi)는 다음과 같습니다.
(0, 1), (1, 0), (1, 1), (-1, 1), (0, 2), (2, 0), (1, 2),
(-1, 2), (2, 1), (-2, 1), (2, 2), (-2, 2), (0, 3), (3, 0),
(1, 3), (-1, 3), (3, 1), (-3, 1), (2, 3), (-2, 3), (3, 2),
(-3, 2), (0, 4), (4, 0), (1, 4), (-1, 4), (4, 1), (-4, 1),
(3, 3), (-3, 3), (2, 4), (-2, 4), (4, 2), (-4, 2), (0, 5),
(3, 4), (-3, 4), (4, 3), (-4, 3), (5, 0), (1, 5), (-1, 5),
(5, 1), (-5, 1), (2, 5), (-2, 5), (5, 2), (-5, 2), (4, 4),
(-4, 4), (3, 5), (-3, 5), (5, 3), (-5, 3), (0, 6), (6, 0),
(1, 6), (-1, 6), (6, 1), (-6, 1), (2, 6), (-2, 6), (6, 2),
(-6, 2), (4, 5), (-4, 5), (5, 4), (-5, 4), (3, 6), (-3, 6),
(6, 3), (-6, 3), (0, 7), (7, 0), (1, 7), (-1, 7), (5, 5),
(-5, 5), (7, 1), (-7, 1), (4, 6), (-4, 6), (6, 4), (-6, 4),
(2, 7), (-2, 7), (7, 2), (-7, 2), (3, 7), (-3, 7), (7, 3),
(-7, 3), (5, 6), (-5, 6), (6, 5), (-6, 5), (8, 0), (4, 7),
(-4, 7), (7, 4), (-7, 4), (8, 1), (8, 2), (6, 6), (-6, 6),
(8, 3), (5, 7), (-5, 7), (7, 5), (-7, 5), (8, 4), (6, 7),
(-6, 7), (7, 6), (-7, 6), (8, 5), (7, 7), (-7, 7), (8, 6),
(8, 7)
예를 들어 거리 코드 1은(0, 1)
주변 픽셀, 즉 현재 픽셀 (0 픽셀) 위에 있는 픽셀
1픽셀 차이, Y 방향의 1픽셀 차이).
마찬가지로 거리 코드 3는 왼쪽 상단 픽셀을 나타냅니다.
디코더는 거리 코드 distance_code를 스캔선 순서로 변환할 수 있음
거리 dist는 다음과 같습니다.
(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
dist = 1
}
여기서 distance_map는 위에 언급된 매핑이고 image_width는 너비입니다.
볼 수 있습니다
5.2.3 색상 캐시 코딩
색상 캐시는 최근 이미지에서 사용된 색상 집합을 저장합니다.
사유: 이런 식으로 최근에 사용한 색상을 가끔 언급할 수 있습니다. 출력하는 것보다 더 효율적으로 데이터를 내보낼 수 있습니다 (자세한 내용은 참조 문서 5.2.1 및 5.2.2)
색상 캐시 코드는 다음과 같이 저장됩니다. 첫째, 1개의 비트 값이 있고 는 색상 캐시가 사용되었는지 여부를 나타냅니다. 이 비트가 0이면 색상 캐시 코드가 없습니다. 존재하며 녹색 레코더를 디코딩하는 접두어 코드로는 기호 및 길이 접두사 코드. 그러나 이 비트가 1이면 색상 캐시는 다음 읽기 크기:
int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;
color_cache_code_bits는 색상 캐시 (1 <<
color_cache_code_bits)의 크기를 정의합니다. 허용되는 값의 범위
color_cache_code_bits는 [1..11]입니다. 호환되는 디코더는
다른 값의 비트스트림이 손상되었기 때문입니다.
색상 캐시는 크기가 color_cache_size인 배열입니다. 항목당 ARGB 1개 저장
color[색상] 색상은 (0x1e35a7bd * color) >> (32 -
color_cache_code_bits)로 색인을 생성하여 조회됩니다. 색상 캐시에서는 조회가 한 번만 수행됩니다. 없음
제공합니다.
이미지 디코딩 또는 인코딩 시작 시 모든 항목은 모든 색상으로 되어 있습니다. 캐시 값이 0으로 설정됩니다 색상 캐시 코드는 디코딩 시간을 단축할 수 있습니다. 색상 캐시의 상태는 역참조나 리터럴로 생성되었는지 확인하여 픽셀의 캐시에 스트림에 표시되는 순서를 따릅니다.
6 엔트로피 코드
6.1 개요
대부분의 데이터는 표준 접두어 코드를 사용하여 코딩됩니다. 따라서 코드는 다음과 같이 프리픽스 코드 길이를 전송함으로써 전송됩니다. 실제 프리픽스 코드가 아닙니다.
특히 이 형식은 공간 변형 접두사 코딩을 사용합니다. 기타 이미지의 다른 블록은 잠재적으로 다른 엔트로피를 사용할 수 있고 있습니다.
사유: 이미지의 영역마다 특성이 다를 수 있습니다. 따라서 서로 다른 엔트로피 코드를 사용할 수 있도록 함으로써 더 많은 유연성과 더 나은 압축이 가능합니다
6.2 세부정보
인코딩된 이미지 데이터는 여러 부분으로 구성됩니다.
- 접두어 코드 디코딩 및 빌드
- 메타 접두어 코드입니다.
- 엔트로피로 코딩된 이미지 데이터입니다.
주어진 픽셀 (x, y)에 대해 있습니다. 다음 코드는 다음과 같습니다 (비트스트림 순서).
- 프리픽스 코드 #1: 녹색 채널, 역참조 길이 및 색상 캐시
- 프리픽스 코드 #2, #3, #4: 빨간색, 파란색, 알파 채널에 사용됩니다. 각각 1개의 값으로 사용합니다.
- 프리픽스 코드 #5: 역참조 거리에 사용됩니다.
이제부터 이 세트를 프리픽스 코드 그룹이라고 합니다.
6.2.1 접두사 코드 디코딩 및 빌드
이 섹션에서는 비트스트림에서 접두사 코드 길이를 읽는 방법을 설명합니다.
접두어 코드 길이는 두 가지 방법으로 코딩할 수 있습니다. 사용된 메서드가 지정됨 1비트 값으로 표현합니다.
- 이 비트가 1이면 단순 코드 길이 코드입니다.
- 이 비트가 0이면 일반 코드 길이 코드입니다.
두 경우 모두 있습니다. 이는 비효율적일 수 있지만 형식상 허용됩니다. 설명된 트리는 완전한 바이너리 트리여야 합니다. 단일 리프 노드는 완전한 바이너리 트리로 간주되며 코드 길이 코드 또는 일반 코드 길이 코드 중 하나입니다. 단일 리프를 코딩할 때 일반 코드 길이 코드를 사용 중인 경우 한 개를 제외한 모든 코드 길이가 0입니다. 단일 리프 노드 값은 길이 1로 표시됩니다. 비트가 소비됩니다.
간단한 코드 길이 코드
이 변형은 접두사 기호가 1개 또는 2개만 있는 특수한 경우에 사용됩니다.
[0..255] 범위(코드 길이 1) 다른 모든 접두사 코드 길이는
0을 반환합니다.
첫 번째 비트는 기호의 수를 나타냅니다.
int num_symbols = ReadBits(1) + 1;
다음은 기호 값입니다.
이 첫 번째 기호는
is_first_8bits 범위는 각각 [0..1] 또는 [0..255]입니다. 두 번째
기호가 있는 경우 항상 [0..255] 범위 내에 있는 것으로 가정되고
8비트를 사용합니다.
int is_first_8bits = ReadBits(1);
symbol0 = ReadBits(1 + 7 * is_first_8bits);
code_lengths[symbol0] = 1;
if (num_symbols == 2) {
symbol1 = ReadBits(8);
code_lengths[symbol1] = 1;
}
두 기호는 달라야 합니다. 중복 기호는 허용되지만 비효율적입니다
참고: 또 다른 특별한 경우는 모든 접두사 코드 길이가 0(
비어 있는 프리픽스 코드). 예를 들어 거리의 접두어 코드는 다음과 같은 경우 비어 있을 수 있습니다.
역방향 참조는 없습니다 마찬가지로 알파, 빨간색 및
동일한 메타 접두어 코드 내에 있는 모든 픽셀이 생성된 경우 파란색이 비어 있을 수 있음
사용할 수 있습니다. 하지만 이 경우에는 특수한 처리가 필요하지 않습니다.
빈 접두사 코드는 단일 기호 0가 포함된 코드로 코딩할 수 있습니다.
일반 코드 길이 코드
접두사 코드의 코드 길이는 8비트이며 다음과 같이 읽힙니다.
먼저 num_code_lengths는 코드 길이의 수를 지정합니다.
int num_code_lengths = 4 + ReadBits(4);
코드 길이 자체는 접두어 코드를 사용하여 인코딩됩니다. 하위 수준 코드
code_length_code_lengths, 먼저 텍스트를 읽어야 합니다. 이 목록의 나머지 부분은
code_length_code_lengths (kCodeLengthCodeOrder의 주문에 따름)
0입니다.
int kCodeLengthCodes = 19;
int kCodeLengthCodeOrder[kCodeLengthCodes] = {
17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
};
int code_length_code_lengths[kCodeLengthCodes] = { 0 }; // All zeros
for (i = 0; i < num_code_lengths; ++i) {
code_length_code_lengths[kCodeLengthCodeOrder[i]] = ReadBits(3);
}
ReadBits(1) == 0인 경우 다양한 읽기 기호의 최대 개수
각 기호 유형(A, R, G, B, 거리)에 대한 (max_symbol)는 다음과 같이 설정됩니다.
글자 크기:
- G 채널: 256 + 24 +
color_cache_size - 기타 리터럴 (A, R, B): 256
- 거리 코드: 40
그렇지 않으면 다음과 같이 정의됩니다.
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
max_symbol가 기호 유형의 알파벳 크기보다 큰 경우
비트스트림이 잘못되었습니다.
그런 다음 code_length_code_lengths에서 접두사 테이블이 빌드되어 읽는 데 사용됩니다.
코드 길이가 max_symbol로 변경됩니다.
- 코드 [0..15] 는 리터럴 코드 길이를 나타냅니다.
- 값 0은 코딩된 기호가 없음을 의미합니다.
- 값 [1..15] 는 각 코드의 비트 길이를 나타냅니다.
- 코드 16은 이전의 0이 아닌 값 [3..6] 을 반복합니다.
3 + ReadBits(2)회. 코드 16이 0이 아닌 값 앞에 사용되는 경우 값을 방출하면 값 8이 반복됩니다. - 코드 17은 연속된 0 길이 [3..10], 즉
3 + ReadBits(3)회를 내보냅니다. - 코드 18은 길이가 [11..138]인 연속된 0을 내보냅니다. 즉,
11 + ReadBits(7)회.
코드 길이를 읽은 후에는 각 기호 유형 (A, R, G, B, 거리)는 각각의 알파벳 크기를 사용하여 형성됩니다.
정상 코드 길이 코드는 전체 결정 트리, 즉
0이 아닌 모든 코드의 2 ^ (-length)는 정확히 1이어야 합니다. 그러나
한 가지 예외는 단일 리프 노드 트리입니다. 여기서 리프 노드는
값이 1로 표시되어 있고 다른 값은 0으로 표시됩니다.
6.2.2 메타 프리픽스 코드 디코딩
앞서 언급했듯이 이 형식에서는 이미지의 여러 블록을 메타 접두어 코드는 이미지의 여러 부분에 사용할 접두어 코드입니다.
메타 접두어 코드는 이미지가 ARGB 이미지의 역할
1비트로 표시된 메타 접두사 코드에는 두 가지 가능성이 있습니다. 값:
- 이 비트가 0이면 이미지 더 이상 데이터가 저장되지 않습니다.
- 이 비트가 1인 경우 이미지는 여러 개의 메타 접두어 코드를 사용합니다. 이 메타 접두어 코드는 엔트로피 이미지로 저장됩니다 (아래 설명 참조).
픽셀의 빨간색과 녹색 구성 요소는 ARGB 이미지의 특정 블록을 나타냅니다.
엔트로피 이미지
엔트로피 이미지는 엔트로피 이미지의 서로 다른 부분에 사용되는 접두어 코드를 이미지
처음 3비트는 prefix_bits 값을 포함합니다. 엔트로피의 차원
이미지는 prefix_bits에서 파생됩니다.
int prefix_bits = ReadBits(3) + 2;
int prefix_image_width =
DIV_ROUND_UP(image_width, 1 << prefix_bits);
int prefix_image_height =
DIV_ROUND_UP(image_height, 1 << prefix_bits);
여기서 DIV_ROUND_UP은 앞에서 정의된 대로입니다.
다음 비트에는 너비 prefix_image_width 및 높이의 엔트로피 이미지가 포함되어 있습니다.
prefix_image_height입니다.
메타 프리픽스 코드 해석
ARGB 이미지에 있는 접두어 코드 그룹의 수는 엔트로피 이미지에서 가장 큰 메타 접두사 코드를 가져옵니다.
int num_prefix_groups = max(entropy image) + 1;
여기서 max(entropy image)는
학습합니다.
각 접두어 코드 그룹에는 5개의 접두어 코드가 있으므로 코드는 다음과 같습니다.
int num_prefix_codes = 5 * num_prefix_groups;
ARGB 이미지의 픽셀 (x, y)가 주어지면 해당하는 접두사를 얻을 수 있습니다. 다음 코드를 사용합니다.
int position =
(y >> prefix_bits) * prefix_image_width + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];
여기서는 PrefixCodeGroup 구조가 있다고 가정했습니다.
5개의 접두어 코드 집합을 나타냅니다. 또한 prefix_code_groups는
PrefixCodeGroup (크기: num_prefix_groups).
그런 다음 디코더는 접두사 코드 그룹 prefix_group를 사용하여 픽셀을 디코딩합니다.
(x, y), 이는 '엔트로피로 코딩된 이미지 디코딩
Data'를 참조하세요.
6.2.3 엔트로피로 코딩된 이미지 데이터 디코딩
이미지의 현재 위치 (x, y)의 경우 디코더는 먼저 해당하는 프리픽스 코드 그룹을 입력합니다 (이전 섹션에서 설명). 주어진 접두사 코드 그룹이 있으면 픽셀을 다음과 같이 읽고 디코딩합니다.
다음으로, 접두어 코드 #1을 사용하여 비트스트림에서 기호 S를 읽습니다. S는
0에서 다음 범위에 있는 정수
(256 + 24 + color_cache_size- 1).
S의 해석은 그 값에 따라 다릅니다.
- S < 256개
- 녹색 구성요소로 S를 사용합니다.
- 접두어 코드 #2를 사용하여 비트스트림에서 빨간색을 읽습니다.
- 접두어 코드 #3을 사용하여 비트스트림에서 파란색을 읽습니다.
- 접두어 코드 #4를 사용하여 비트스트림에서 알파를 읽습니다.
- S가 256 이상이고 일 < 256 + 24
- 길이 접두어 코드로 S - 256을 사용합니다.
- 비트스트림에서 길이의 추가 비트를 읽습니다.
- 길이 접두사 코드 및 추가 비트를 읽습니다.
- 접두어 코드 #5를 사용하여 비트스트림에서 거리 접두어 코드를 읽습니다.
- 비트스트림으로부터의 거리에 대해 추가 비트를 읽습니다.
- 거리 접두사 코드로부터 역참조 거리 D를 구합니다. 나머지 비트는 읽습니다.
- 다음에서 시작하는 픽셀 시퀀스에서 L개의 픽셀을 스캔 라인 순서대로 복사합니다. D픽셀을 뺀 값으로 설정됩니다.
- S가 256+24 이상인 경우
- S - (256 + 24)를 색상 캐시의 색인으로 사용합니다.
- 해당 색인의 색상 캐시에서 ARGB 색상을 가져옵니다.
7 형식의 전반적인 구조
다음은 ABNF (증강 배커스 나우르 형식) 형식을 보여줍니다. RFC 5234 RFC 7405 모든 세부정보를 다루지는 않습니다. 이미지 종료 (EOI) 픽셀 수 (image_width * image_height)로만 암시적으로 코딩됩니다.
*element는 element를 0회 이상 반복할 수 있음을 의미합니다. 5element
element가 정확히 5회 반복된다는 의미입니다. %b는 바이너리 값을 나타냅니다.
7.1 기본 구조
format = RIFF-header image-header image-stream
RIFF-header = %s"RIFF" 4OCTET %s"WEBPVP8L" 4OCTET
image-header = %x2F image-size alpha-is-used version
image-size = 14BIT 14BIT ; width - 1, height - 1
alpha-is-used = 1BIT
version = 3BIT ; 0
image-stream = optional-transform spatially-coded-image
7.2 변환의 구조
optional-transform = (%b1 transform optional-transform) / %b0
transform = predictor-tx / color-tx / subtract-green-tx
transform =/ color-indexing-tx
predictor-tx = %b00 predictor-image
predictor-image = 3BIT ; sub-pixel code
entropy-coded-image
color-tx = %b01 color-image
color-image = 3BIT ; sub-pixel code
entropy-coded-image
subtract-green-tx = %b10
color-indexing-tx = %b11 color-indexing-image
color-indexing-image = 8BIT ; color count
entropy-coded-image
7.3 이미지 데이터의 구조
spatially-coded-image = color-cache-info meta-prefix data
entropy-coded-image = color-cache-info data
color-cache-info = %b0
color-cache-info =/ (%b1 4BIT) ; 1 followed by color cache size
meta-prefix = %b0 / (%b1 entropy-image)
data = prefix-codes lz77-coded-image
entropy-image = 3BIT ; subsample value
entropy-coded-image
prefix-codes = prefix-code-group *prefix-codes
prefix-code-group =
5prefix-code ; See "Interpretation of Meta Prefix Codes" to
; understand what each of these five prefix
; codes are for.
prefix-code = simple-prefix-code / normal-prefix-code
simple-prefix-code = ; see "Simple Code Length Code" for details
normal-prefix-code = ; see "Normal Code Length Code" for details
lz77-coded-image =
*((argb-pixel / lz77-copy / color-cache-code) lz77-coded-image)
다음은 가능한 시퀀스의 예입니다.
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image