컨텍스트 적응형 이항 산술 코드화

Context-adaptive binary arithmetic coding

컨텍스트 적응형 이항 산술 부호화(CAB)AC)는 H.264/MPEG-4 AVC[1][2] 및 HEVC(High Efficiency Video Coding) 표준에 사용되는 엔트로피 인코딩의 일종이다. 그것은 비록 그것이 사용되는 비디오 코딩 표준이 전형적으로 손실 압축 애플리케이션에 사용되기는 하지만 무손실 압축 기법이다. CABAC는 비디오 인코딩에 사용되는 대부분의 다른 엔트로피 인코딩 알고리즘보다 훨씬 우수한 압축을 제공하는 것으로 유명하며, H.264/AVC 인코딩 체계를 이전보다 더 나은 압축 기능을 제공하는 핵심 요소 중 하나이다.[3]

H.264/MPEG-4 AVC에서 CABAC는 표준의 기본 프로필(확장 프로필은 아님)에서만 지원되며, 이는 표준의 기본 프로필에서 사용되는 문맥 적응형 가변 길이 코딩(CAVLC)으로 알려진 단순한 방식보다 더 많은 양의 디코딩이 필요하기 때문이다. CABAC는 또한 병렬화 및 벡터화가 어렵기 때문에 다른 형태의 병렬화(공간 영역 병렬화 등)가 그 사용과 결합될 수 있다. HEVC에서 CABAC는 표준의 모든 프로파일에 사용된다.

알고리즘.

CABAC는 산술 코딩을 기반으로 하며, 비디오 인코딩 표준의 필요성에 맞게 몇 가지 혁신과 변화를 제공한다.[4]

  • 그것은 복잡성을 낮게 유지하고 더 자주 사용되는 기호의 비트에 대한 확률 모델링을 가능하게 하는 이진 기호를 암호화한다.
  • 코딩 모드는 일반적으로 국소적으로 잘 상관되기 때문에 확률의 더 나은 모델링을 가능하게 하여 현지 상황에 따라 적응적으로 선택된다.
  • 정량화된 확률 범위와 확률 상태를 사용하여 곱셈 없는 범위 구분을 사용한다.

CABAC에는 다양한 상황에 대한 다중 확률 모드가 있다. 먼저 모든 비이진 기호를 이진 기호로 변환한다. 그런 다음 각 비트에 대해 코더는 사용할 확률 모델을 선택한 다음, 확률 추정을 최적화하기 위해 근처 요소의 정보를 사용한다. 데이터를 압축하기 위해 산술 코딩이 최종적으로 적용된다.

영어에서 H264 비디오 압축 표준 내에서 사용되는 엔트로피 인코딩 CABAC 방법

컨텍스트 모델링은 코딩 기호의 조건부 확률의 추정치를 제공한다. 적절한 컨텍스트 모델을 활용하면, 주어진 심볼 간 중복성은 인코딩을 위해 현재 심볼 부근에 이미 코드화된 기호에 따라 다른 확률 모델 사이를 전환하여 이용할 수 있다. 컨텍스트 모델링이 대부분의 CAB를 담당함AC는 CAVLC 엔트로피 코딩 방법에 비해 비트 전송률 약 10% 절약

데이터 기호를 코딩하는 것은 다음 단계를 포함한다.

  • 이진화: CABAC는 이진 산술 코딩을 사용하며, 이는 이진 결정(1 또는 0)만 인코딩됨을 의미한다. 2진수 값이 아닌 기호(예: 변환 계수 또는 운동 벡터)는 "이항화"되거나 산술 코딩 전에 2진수 코드로 변환된다. 이 과정은 데이터 기호를 가변 길이 코드로 변환하는 과정과 유사하지만 전송 전 바이너리 코드는 (산술 코더에 의해) 추가로 인코딩된다.
  • 이항 기호의 각 비트(또는 "bin")에 대해 단계가 반복된다.
  • 컨텍스트 모델 선택: "컨텍스트 모델"은 이항 기호의 빈 하나 이상에 대한 확률 모델이다. 이 모델은 최근 코드화된 데이터 기호의 통계에 따라 사용 가능한 모델 중에서 선택할 수 있다. 컨텍스트 모델은 각 빈이 "1" 또는 "0"일 확률을 저장한다.
  • 산술 인코딩: 산술 코더는 선택한 확률 모델에 따라 각 빈을 인코딩한다. 각 bin에는 ("0"과 "1"에 해당하는) 두 개의 하위 범위가 있다는 점에 유의하십시오.
  • 확률 업데이트: 선택한 컨텍스트 모델은 실제 코드화된 값을 기반으로 업데이트된다(예: bin 값이 "1"이면 "1"의 주파수 카운트가 증가한다).

예

1. 값 MVDx, 즉 의 모션 벡터 차이의 이진화 x 방향의

MVDx 바이나라이제이션
0 0
1 10
2 110
3 1110
4 11110
5 111110
6 1111110
7 11111110
8 111111110

이진화된 코드 워드의 첫 번째 비트는 빈 1이고, 두 번째 비트는 빈 2이다.

2. 각 빈에 대한 컨텍스트 모델을 선택하십시오. 이전에 코드화된 MVD 값을 기준으로 빈 1에 대해 3개 모델 중 하나를 선택한다. 이전에 코드화된 두 값(ek)의 L1 규범이 계산된다.

ek 빈 1의 컨텍스트 모델
0 ≤ ek < 3 모델 0
3k≤ e < 33 모델 1
33 ≤ ek 모델 2

e가k 작으면 현재의 MVD가 작을 가능성이 높고, 반대로k e가 크면 현재의 MVD가 더 클 가능성이 크다. 우리는 그에 따라 확률표(콘텍스트 모델)를 선택한다. 나머지 빈은 4개의 추가 컨텍스트 모델 중 하나를 사용하여 코드화된다.

빈 컨텍스트 모델
1 e에k 따라 0, 1 또는 2
2 3
3 4
4 5
5이상 6

3. 각 빈을 인코딩한다. 선택한 컨텍스트 모델은 빈에 "1"이 포함될 확률과 빈에 "0"이 포함될 확률의 두 가지 확률 추정치를 제공한다. 이러한 추정치는 산술 코더가 빈을 인코딩하는 데 사용하는 두 개의 하위 범위를 결정한다.

4. 컨텍스트 모델을 업데이트한다. 예를 들어 bin 1에 대해 컨텍스트 모델 2를 선택하고 bin 1의 값이 "0"인 경우, "0"s의 주파수 카운트가 증가된다. 이것은 다음에 이 모델을 선택할 때 "0"의 확률이 약간 더 높아진다는 것을 의미한다. 모델의 총 발생 횟수가 임계값을 초과하면 "0"과 "1"의 주파수 카운트가 축소되며, 이는 사실상 최근 관측치에 더 높은 우선 순위를 부여한다.

산술 디코딩 엔진

산술적 디코더는 이 기준서에 자세히 설명되어 있다. 그것은 세 가지 뚜렷한 특성을 가지고 있다.

  1. 확률 추정은 "최소 개연성 기호" (LPS, 두 이진 결정 "0" 또는 "1" 중 가장 개연성이 낮은 64개의 확률 상태 사이의 전환 프로세스에 의해 수행된다.
  2. 범위 R 산술 코더의 현재 상태를 나타내는 것은 각 단계에서 새로운 범위를 계산하기 전에 미리 설정된 값의 작은 범위로 정량화하여 조회표(즉, 곱셈표)를 사용하여 새로운 범위를 계산할 수 있게 한다.
  3. 거의 균일한 확률 분포를 갖는 데이터 기호에 대해 단순화된 인코딩 및 디코딩 프로세스가 정의된다.

디코딩 프로세스의 정의는 산술적 인코딩과 디코딩의 저복잡성 구현을 용이하게 하기 위해 설계되었다. 전체적으로 CABAC는 더 큰 계산 복잡성을 희생하면서 CAVLC 기반 코딩에 비해 향상된 코딩 효율성을 제공한다.

역사

1986년 IBM의 연구원인 Kottappuram M. A. Mohiuddin과 Jorma Johannen Rissanen은 곱셈이 없는 이진 산술 코딩 알고리즘에 대해 특허를 출원했다.[5][6] 1988년에는 R.B.를 포함한 IBM의 연구팀이 참가하였다. Arps, T.K. Truong, D.J. Lu, W. B. Pennebaker, L. Mitchell, G. G. Langdon은 Q-Coder라는 적응형 이진 산술 코딩(ABAC) 알고리즘을 제시했다.[7][8]

위의 특허와 연구 논문은 IBM과 미쓰비시 전기의 다른 여러 논문들과 함께, 후에 CCITT와 공동 사진 전문가 그룹에 의해 1992년에 JPEG 이미지 압축 형식의 적응형 이진 산술 코딩 알고리즘의 기초로 인용되었다.[5] 그러나 허프먼 인코딩과 산술 코딩 모두에 대한 옵션을 가지고 있는 JPEG 파일 형식의 인코더와 디코더는 일반적으로 허프먼 인코딩 옵션만 지원하는데, JPEG의 산술 코딩 특허가[9] JPEG 표준의 연령이 되어 그 이후 만료되었지만, 원래 특허 우려 때문이었다.[10]

1999년 유영준(텍사스 인스트루먼트), 권영갑(권영갑)과 안토니오 오르테가(남캘리포니아대)는 문맥 적응형 이진 산술 코딩 형식을 제시했다.[11] 현대의 컨텍스트 적응형 바이너리 산술 코딩(CABAC) 알고리즘은 2003년에 H.264/MPEG-4 AVC 포맷과 함께 상업적으로 도입되었다.[12] AVC 포맷 특허의 대부분은 파나소닉, 고도카이사 IP브릿지, LG전자가 보유하고 있다.[13]

참고 항목

참조

  1. ^ 리처드슨, Iain E. G, H.264 / MPEG-4 Part 10 백서, 2002년 10월 17일.
  2. ^ Richardson, Iain E. G. (2003). H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia. Chichester: John Wiley & Sons Ltd.
  3. ^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 April 2014). Fundamentals of Multimedia. Springer Science & Business Media. ISBN 978-3-319-05290-8.
  4. ^ Marpe, D, Schwarz, H 및 Wiegand, T, H.264/AVC 비디오 압축 표준, IEEE Trans의 컨텍스트 기반 적응형 바이너리 산술 코딩. 비디오 기술을 위한 회로 및 시스템, 13권, 7번 페이지 620–636, 2003년 7월.
  5. ^ a b "T.81 – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES" (PDF). CCITT. September 1992. Retrieved 12 July 2019.
  6. ^ 미국 특허 4,652,856
  7. ^ Arps, R. B.; Truong, T. K.; Lu, D. J.; Pasco, R. C.; Friedman, T. D. (November 1988). "A multi-purpose VLSI chip for adaptive data compression of bilevel images". IBM Journal of Research and Development. 32 (6): 775–795. doi:10.1147/rd.326.0775. ISSN 0018-8646.
  8. ^ Pennebaker, W. B.; Mitchell, J. L.; Langdon, G. G.; Arps, R. B. (November 1988). "An overview of the basic principles of the Q-Coder adaptive binary arithmetic coder". IBM Journal of Research and Development. 32 (6): 717–726. doi:10.1147/rd.326.0717. ISSN 0018-8646.
  9. ^ "Recommendation T.81 (1992) Corrigendum 1 (01/04)". Recommendation T.81 (1992). International Telecommunication Union. 9 November 2004. Retrieved 3 February 2011.
  10. ^ JPEG 스틸 이미지 데이터 압축 표준, W. B. Pennebaker 및 J. L. Mitchell, Kluwer Academic Press, 1992. ISBN 0-442-01272-1
  11. ^ Ortega, A. (October 1999). "Embedded image-domain compression using context models". Proceedings 1999 International Conference on Image Processing (Cat. 99CH36348). 1: 477–481 vol.1. doi:10.1109/ICIP.1999.821655.
  12. ^ "Context-Based Adaptive Binary Arithmetic Coding (CABAC)". Fraunhofer Heinrich Hertz Institute. Retrieved 13 July 2019.
  13. ^ "AVC/H.264 – Patent List" (PDF). MPEG LA. Retrieved 6 July 2019.