An Empirical Study of Entropy-Conserving Binarization in H.264/AVC CABAC

기술 요약: H.264/AVC CABAC에서의 엔트로피 보존 이진화에 관한 경험적 연구

문제 정의
현대 비디오 코덱(H.264/AVC, HEFC, VVC)은 심볼 스트림을 압축하기 위해 컨텍스트 적응형 이진 산술 부호화(CABAC)에 의존한다. CABAC는 두 단계로 작동한다. 첫째, 이진화(binarization) 기법은 다중 심볼 값을 이진 결정(bin)으로 변 변환하며, 둘째, 이진 산술 코더(M-coder)는 적응형 컨텍스트 모델을 사용하여 이 bin들을 압축한다. H.264 표준은 기하학적 꼬리 분포(geometric-tailed distributions)에 최적화된 절단 유니리(Truncated Unary) 및 $k$차 Exp-Golomb(UEG) 방식을 채택하고 있다. 이론적인 대안들—예를 들어 정형 허프曼 코드(canonical Huffman codes)나 Srivastava의 엔트로피 보존 이진화(ECB)—이 존재하지만, 실제 프로덕션급 CABAC 파이프라인 내에서의 경험적 성능은 검증되지 않았다. 특히 ECB는 $m$진 소스를 $m-1$개의 이진 문자열로 매핑할 때 전체 엔트로피를 이론적으로 보존하지만, 적응형 컨텍스트 모델링과의 상호작용 및 디코더 복잡도에 대해서는 표준 구현과 엄격하게 벤치마킹된 바가 없다. 또한, 이진화 방식에 따른 레이트 차이가 이진화 자체에 의한 것인지, 아니면 결과물인 bin 스트림에 컨텍스트를 할당하는 전략에 의한 것인지도 불분분하다.

방법론
저자들은 ITU-T H.264 Section 9.3을 엄격히 준수하여 Java로 H.264/AVC CABAC 인코더와 디코더를 처음부터 직접 구현하였다. 이 구현은 네 가지 교체 가능한 이진화 구성을 갖춘 공유 M-coder 백엔드를 특징으로 한다:

1. UEG: 표준 H.264 방식 (절단 유니리 접두사 + Exp-Golomb 접미사).
2. ECB: $m$진 심볼을 $m-1$개의 이진 문자열로 매핑하는 Srivastava의 엔트로피 보존 방식.
3. Huffman: 모든 bin 위치에 대해 단일 공유 컨텍스트를 사용하는 정형 허프만 코딩.
4. HuffmanPos: 각 bin 위치마다 하나의 컨텍스트를 사용하는 정형 허프만 코딩.

이 설계는 두 가지 변수를 격리한다: 이진화의 선택(UEG vs. ECB vs. Huffman)과 컨텍스트 할당 전략(단일 컨텍스트 vs. 위치별 컨텍스트). Huffman과 HuffmanPos는 동일한 코드워드(따라서 동일한 심볼당 bin 개수)를 공유하지만, 컨텍스트 연결 방식에서만 차이가 나므로, 저자들은 이를 통해 bin 개수의 효과와 컨텍스트 적응의 효과를 분리할 수 있었다.

연구는 다음 세 가지 소스 클래스에 대해 평가를 수행하였다:

• 합성 분포: 균등(Uniform), 편향(Biased), 기하(Geometric), 라플라스(Laplacian) 분포 ($N=10,000$).
• 절차적 DCT 잔차(Procedural DCT Residuals): 사인파 경사(sinusoidal gradients), 가우시안 범프(Gaussian bumps), 직사각형 형태를 가진 256×256 절차적 생성 이미지로, 단계 $Q \in \{2, 4, 8, 16, 32\}$로 양자화됨.
• Kodak 자연 사진: 동일한 DCT 파이프라인을 거친 Kodak True Color Image Suite의 전체 24개 이미지.

벤치마크는 2,480회의 왕복 시험(round-trip trials)으로 구성되었으며, 모두 비트 단위의 정확성이 검증되었다. 성능은 경험적 1차 섀넌 엔트로피(empirical first-order Shannon entropy) 대비 코딩 오버헤드($\eta$)와 디코더 지연 시간으로 측정되었다.

주요 결과

• 희소성 기반 교차점(Sparsity-Driven Crossover): 절차적 이미지에서 $Q=8$ 지점에서 교차점이 확인되었다. 이보다 낮은 구간(더 풍부한 분포)에서는 단일 컨텍스트 Huffman이 ECB보다 우수했다. 이보다 높은 구간(더 희소한 분포)에서는 ECB가 Huffman을 크게 앞질렀으며, $Q=32$에서 27 퍼센트 포인트의 우위를 점했다. 그러나 자연 Kodak 이미지의 경우, 이 교차점은 테스트된 범위 아래로 이동하였다. 즉, 모든 양자화 단계에서 ECB가 단일 컨텍스트 Huffman보다 우수했으며, $Q$가 증가함에 따라 그 격차가 벌어졌다.
• 컨텍스트 할당의 지배력: Huffman과 HuffmanPos의 비교를 통해, 낮은 엔트로피 영역에서는 bin 개수보다 컨텍스트 할당 전략이 레이트 효율의 결정적 요인임이 밝혀졌다. HuffmanPos(Huffman과 동일한 bin 개수를 사용하지만 위치별 컨텍스트 적용)는 단일 컨텍스트 Huffman보다 일관되게 우수한 성능을 보였으며, 대부분의 소스 셀에서 ECB의 성능과 일치하거나 약간 상회하였다. $Q=3로 절차적 이미지에서 HuffmanPos는 $\eta = -0.83\%$를 달성하였는데, 이는 열등한 단일 컨텍스트 Huffman과 동일한 수의 bin을 사용했음에도 불구하고 ECB의 $-0.69\%$와 통계적으로 구별할 수 없는 수준이었다.
• 디코더 지연 시간 트레이드오프: ECB의 레이트 효율성은 상당한 계산 비용을 수반한다. 현재의 ECB 구현은 $O(N \cdot m)$의 디코더 복잡도를 가지며, 심볼 배열에 대해 $m-1$번의 패스(pass)가 필요하다. 큰 알파벳(예: $m=834$)의 경우, ECB는 UEG보다 710배 느렸다. 반면, HuffmanPos는 단일 컨텍스트 Huffman 대비 상수 배의 오버헤드(628% 느림)만을 발생시키면서도 유사한 레이트 효율성을 달나성했다.
• 하위 엔트로피 코딩(Sub-Entropy Coding): 여러 방식(ECB, HuffmanPos, 그리고 Kodak에서의 UEG)이 음의 오버헤드($\eta < 0$)를 달성하여, 경험적 1차 엔트로피 미만으로 코딩되었다. 저자들은 이를 소스 코딩 한계의 위반이 아니라, M-coder가 주변 엔트로피 추정기가 무시하는 조건부 구조(DCT 블록 내 및 블록 간의 공간적 상관관계)를 포착했기 때문이라고 설명한다.

의의 및 주장
본 논문은 프로덕션 이진 산술 코더 내에서 ECB를 경험적으로 평가한 첫 사례라고 주장한다. 주요 기여는 레이트 차이를 유발하는 메커니즘을 격리해낸 것이다: 즉, 낮은 소스 엔트로피에서는 컨텍스트 할당 전략이 이진화의 심볼당 bin 개수보다 더 중요하다는 것을 보여주었다. 연구는 적절한 위치별 컨텍스트 할당 전략(HuffmanPos)과 결합된다면 표준 이진화(Huffman)가 이론적으로 최적인 이진화(ECB)의 레이트 효율성을 달성할 수 있음을 입증하였다.

저자들은 ECB가 이론적 이점은 있으나, 현재의 $O(N \cdot m)$ 구현은 실용적인 용도로는 너무 비용이 많이 든다고 겸허히 결론지었다. 저자들은 인터리브드 싱글 패스(interleaved single-pass) 디코더를 사용하면 이론적으로 이 지연 시간 격차를 $O(N)$으로 좁힐 수 있다고 제안했으나, 이 변형 모델은 본 연구에서 구현되지 않았다. 본 연구는 자연 이미지의 경우, HuffmanPos가 테스트된 방식 중 레이트 효율성과 디코더 복잡도 사이에서 가장 유리한 트레이드오프를 제공한다고 시사한다. 모든 코드, 벤치마크 및 원시 데이터는 오픈 소스로 공개되었다.