이진 산술 부호화 방식

이진 산술 부호화 방식(, CABAC)는 H.264/MPEG-4 AVC 및 고효율 비디오 코딩 (HEVC) 표준에서 사용되는 엔트로피 부호화의 한 형태이다. 이는 비디오 코딩 표준에서 일반적으로 손실 압축 응용 프로그램에 사용되지만, 비손실 압축 기술이다. CABAC는 비디오 인코딩에 사용되는 대부분의 다른 엔트로피 인코딩 알고리즘보다 훨씬 더 나은 압축을 제공한다는 점에서 주목할 만하며, 이전 버전에 비해 H.264/AVC 인코딩 방식에 더 나은 압축 기능을 제공하는 핵심 요소 중 하나이다.

H.264/MPEG-4 AVC에서 CABAC는 표준의 메인 및 상위 프로필에서만 지원되며(확장 프로필은 제외), 표준의 베이스라인 프로필에서 사용되는 문맥 적응 가변 길이 부호화 (CAVLC)로 알려진 더 간단한 방식보다 디코딩에 더 많은 처리가 필요하기 때문이다. CABAC는 병렬화 및 벡터화가 어려워 공간 영역 병렬 처리와 같은 다른 형태의 병렬 처리가 함께 사용될 수 있다. HEVC에서는 CABAC가 표준의 모든 프로필에서 사용된다.

 알고리즘 
CABAC는 산술 부호화를 기반으로 하며, 비디오 인코딩 표준의 필요에 맞게 몇 가지 혁신과 변경이 이루어졌다.
 이진 기호를 인코딩하여 복잡성을 낮게 유지하고 모든 기호의 더 자주 사용되는 비트에 대한 확률 모델링을 허용한다.
 확률 모델은 지역 문맥에 따라 적응적으로 선택되어 확률을 더 잘 모델링할 수 있다. 이는 코딩 모드가 일반적으로 지역적으로 잘 연관되어 있기 때문이다.
 양자화된 확률 범위 및 확률 상태를 사용하여 곱셈 없는 범위 분할을 사용한다.

CABAC는 다양한 문맥에 대한 여러 확률 모드를 가지고 있다. 먼저 모든 비이진 기호를 이진으로 변환한다. 그런 다음, 각 비트에 대해 코더는 사용할 확률 모델을 선택하고, 인접 요소의 정보를 사용하여 확률 추정치를 최적화한다. 마지막으로 산술 부호화가 데이터를 압축하는 데 적용된다.
alt=|center|섬네일|800x800px|H264 비디오 압축 표준 내에서 사용되는 엔트로피 인코딩의 CABAC 방식
문맥 모델링은 코딩 기호의 조건부 확률을 추정한다. 적절한 문맥 모델을 활용하여 인코딩할 현재 기호의 인접 부분에서 이미 코딩된 기호에 따라 다른 확률 모델 간에 전환함으로써 주어진 기호 간 중복성을 활용할 수 있다. 문맥 모델링은 CAVLC 엔트로피 코딩 방식에 비해 CABAC의 비트레이트 절감 효과인 약 10%의 대부분을 담당한다.

데이터 심볼을 코딩하는 과정은 다음 단계를 포함한다.
 이진화: CABAC는 이진 산술 코딩을 사용하는데, 이는 이진 결정(1 또는 0)만 인코딩된다는 것을 의미한다. 비이진 값 심볼(예: 변환 계수 또는 움직임 벡터)은 산술 코딩 전에 "이진화"되거나 이진 코드로 변환된다. 이 과정은 데이터 심볼을 가변 길이 코드로 변환하는 과정과 유사하지만, 이진 코드는 전송 전에 (산술 코더에 의해) 추가로 인코딩된다.
 이진화된 심볼의 각 비트(또는 "빈")에 대해 단계가 반복된다.
 문맥 모델 선택: "문맥 모델"은 이진화된 심볼의 하나 이상의 빈에 대한 확률 모델이다. 이 모델은 최근 코딩된 데이터 심볼의 통계에 따라 사용 가능한 모델 선택에서 선택될 수 있다. 문맥 모델은 각 빈이 "1" 또는 "0"일 확률을 저장한다.
 산술 부호화: 산술 코더는 선택된 확률 모델에 따라 각 빈을 인코딩한다. 각 빈에는 두 개의 서브 범위만 존재한다("0"과 "1"에 해당).
 확률 업데이트: 선택된 문맥 모델은 실제 코딩된 값에 따라 업데이트된다(예: 빈 값이 "1"인 경우 "1"의 빈도 수가 증가한다). 이는 다음에 이 모델이 선택될 때 "1"의 확률이 약간 더 높아진다는 것을 의미한다. 모델의 총 발생 횟수가 임계값을 초과하면 "0"과 "1"의 빈도 수가 축소되어 최근 관측에 더 높은 우선순위를 부여하는 효과를 가져온다.

 예시 
 MVDx 이진화 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 7 11111110 8 111111110

1. x 방향의 움직임 벡터 차이인 MVDx 값을 이진화한다.

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

 ek 빈 1에 대한 문맥 모델 0 ≤ ek < 3 모델 0 3 ≤ ek < 33 모델 1 33 ≤ ek 모델 2

2. 각 빈에 대한 문맥 모델을 선택한다. 이전 코딩된 MVD 값에 따라 3개 모델 중 하나가 빈 1에 대해 선택된다. 이전에 코딩된 두 값의 L1 노름, ek는 다음과 같이 계산된다.

 빈 문맥 모델 1 ek에 따라 0, 1 또는 2 2 3 3 4 4 5 5 이상 6
만약 ek가 작다면, 현재 MVD가 작은 크기를 가질 확률이 높고, 반대로 ek가 크다면 현재 MVD가 큰 크기를 가질 가능성이 더 높다. 우리는 이에 따라 확률표(문맥 모델)를 선택한다. 나머지 빈들은 4가지 추가 문맥 모델 중 하나를 사용하여 코딩된다.

3. 각 빈을 인코딩한다. 선택된 문맥 모델은 두 가지 확률 추정치를 제공한다. 즉, 빈이 "1"을 포함할 확률과 "0"을 포함할 확률이다. 이러한 추정치는 산술 코더가 빈을 인코딩하는 데 사용하는 두 개의 서브 범위를 결정한다.

4. 문맥 모델을 업데이트한다. 예를 들어, 빈 1에 대해 문맥 모델 2가 선택되었고 빈 1의 값이 "0"이었다면, "0"의 빈도 수가 증가한다. 이는 다음에 이 모델이 선택될 때 "0"의 확률이 약간 더 높아진다는 것을 의미한다. 모델의 총 발생 횟수가 임계값을 초과하면 "0"과 "1"의 빈도 수가 축소되어, 결과적으로 최근 관측에 더 높은 우선순위를 부여한다.

 산술 디코딩 엔진 
산술 디코더는 표준에 자세히 설명되어 있다. 세 가지 뚜렷한 특징이 있다.

확률 추정은 "가장 가능성 낮은 기호"(LPS, 두 이진 결정 "0" 또는 "1" 중 가장 가능성이 낮은 것)에 대한 64개의 개별 확률 상태 간의 전환 프로세스에 의해 수행된다.
산술 코더의 현재 상태를 나타내는 범위 은 각 단계에서 새 범위를 계산하기 전에 미리 설정된 작은 값 범위로 양자화되어, 룩업 테이블(즉, 곱셈 없이)을 사용하여 새 범위를 계산할 수 있도록 한다.
거의 균일한 확률 분포를 가진 데이터 기호에 대한 단순화된 인코딩 및 디코딩 프로세스가 정의되어 있다.
디코딩 프로세스의 정의는 산술 인코딩 및 디코딩의 낮은 복잡도 구현을 용이하게 하도록 설계되었다. 전반적으로 CABAC는 CAVLC 기반 코딩에 비해 향상된 코딩 효율성을 제공하지만, 계산 복잡도가 더 높다.

 역사 
1986년, IBM 연구원인 Kottappuram M. A. Mohiuddin과 Jorma Johannes Rissanen은 곱셈 없는 이진 산술 부호화 알고리즘에 대한 특허를 출원했다. 1988년, R.B. Arps, T.K. Truong, D.J. Lu, W. B. Pennebaker, L. Mitchell 및 G. G. Langdon을 포함한 IBM 연구팀은 Q-Coder라는 적응형 이진 산술 부호화(ABAC) 알고리즘을 발표했다.

위의 특허와 연구 논문들, 그리고 IBM과 미쓰비시 전기의 여러 다른 논문들은 1992년 CCITT와 Joint Photographic Experts Group에 의해 JPEG 이미지 압축 형식의 적응형 이진 산술 부호화 알고리즘의 기초로 인용되었다. 그러나 허프먼 부호화와 산술 부호화 옵션을 모두 가진 JPEG 파일 형식의 인코더 및 디코더는 일반적으로 허프먼 부호화 옵션만 지원하는데, 이는 원래 특허 문제 때문이었다. 하지만 JPEG의 산술 부호화 특허는 JPEG 표준의 오래된 특성으로 인해 만료되었다.JPEG Still Image Data Compression Standard, W. B. Pennebaker and J. L. Mitchell, Kluwer Academic Press, 1992.  움직임 비디오 압축에서 적응형 이진 산술 부호화의 첫 번째 보고된 사용은 1989년 IBM 연구원들이 MPEG 그룹에 제출한 제안서에 있었다.DCT Coding for Motion Video Storage using Adaptive Arithmetic Coding, C. A. Gonzales. L. Allman, T. McCarthy, P. Wendt and A. N. Akansu, Signal Processing: Image Communication, 2, 145, 1990.Encoding of motion video sequences for the MPEG environment using arithmetic coding, E. Viscito and C. Gonzales, SPIE Visual Communications and Image Processing '90, October 2–4, 1990. 이 제안은 산술 부호화의 사용을 인트라프레임 JPEG에서 인터프레임 비디오 코딩으로 확장했다.

1999년, Youngjun Yoo (텍사스 인스트루먼트), Young Gap Kwon 및 Antonio Ortega (서던캘리포니아 대학교)는 문맥 적응형 이진 산술 부호화의 한 형태를 발표했다. 현대적인 문맥 적응형 이진 산술 부호화(CABAC) 알고리즘은 2003년 H.264/MPEG-4 AVC 형식과 함께 상업적으로 도입되었다. AVC 형식의 대부분의 특허는 파나소닉 홀딩스, 고도 가이샤 IP 브리지 및 LG전자가 보유하고 있다.

 같이 보기 
 산술 부호화
 데이터 압축
 비손실 압축
 문맥 적응 가변 길이 부호화

 각주 

분류:데이터 압축
분류:MPEG
분류:영상 압축