H.264/AVC 알고리즘 이해와 프로그램 분석

제1장 영상 압축과 국제 표준/11
1.1 영상 정보의 압축 부호화 11
1.1.1 디지털 데이터의 압축 11
1.1.2 중복 정보의 제거 12
1.1.3 동영상 압축 부호화 표준 15
1.1.4 MPEG 국제 표준 16
1.1.5 H.261/H.263 국제 권고 18
1.2 H.264/AVC 동영상 압축 표준 19
1.2.1 연합 비디오 팀 구성 19
1.2.2 H.264/AVC 비디오 부호화 표준 20
1.2.3 프로파일과 레벨 22
1.2.4 정수 DCT 변환과 양자화 23
1.2.5 비트율-왜곡 최적화 26
1.2.6 매크로블록 모드 결정 27
1.2.7 문맥 기반 적응적 가변 길이 부호화 29
1.2.8 문맥 기반 적응적 이진 산술 부호화 35
1.2.8.1 이진화 35
1.2.8.2 문맥 모델링 36
1.2.8.3 잔여 데이터의 부호화 과정 39
1.2.8.4 테이블 기반 이진 산술 부호화 41

제2장 H.264/AVC 부호기 소프트웨어 분석/43
2.1 소프트웨어 다운로드 및 입력 파일 변수 설정 43
2.2 H.264/AVC 부호기 주요 데이터 구조 51
2.2.1 4×4 인트라 예측 모드를 위한 버퍼 53
2.2.2 16×16 인트라 예측 모드를 위한 버퍼 54
2.2.3 8×8 인트라 예측 모드를 위한 버퍼 55
2.2.4 인트라 색차 예측 모드를 위한 버퍼 56
2.2.5 움직임 보상을 위한 화소 값의 저장 57
2.2.6 잔여 영상의 화소 값 저장 58
2.2.7 움직임 벡터 저장 61
2.3 H.264/AVC 부호기의 주요 함수 64
2.3.1 인터 모드를 위한 움직임 예측 및 P8×8 모드결정 72
2.3.1.1 PartitionMotionSearch 함수 73
2.3.1.2 sub_macroblock_mode_decision 함수 80
2.3.2 최종 모드 결정 87

제3장 H.264/AVC 부호기 구조 및 주요 알고리즘/127
3.1 프로파일과 레벨 128
3.2 베이스라인 프로파일 129
3.2.1 디블록킹 필터 129
3.2.1.1 디블록킹 필터의 동작 129
3.2.1.2 경계 강도 130
3.2.1.3 디블록킹 필터의 적용 여부 결정 133
3.2.2 변환과 양자화 134
3.2.2.1 DCT 135
3.2.2.2 4×4 잔여 블록의 변환과 양자화 137
3.2.2.2.1 4×4 DCT로부터의 4×4 정수 DCT 유도 137
3.2.2.2.2 역변환 141
3.2.2.2.3 양자화 141
3.2.2.2.4 역양자화 144
3.2.2.3 16×16 인트라 모드에서 4×4 휘도 DC 계수 블록의 변환과 양자화 145
3.2.2.4 2×2 색차 DC 계수 블록의 변환과 양자화 149
3.2.2.5 계수 재배열 151
3.3 메인 프로파일 151
3.3.1 B 슬라이스 152
3.3.1.1 참조 영상 152
3.3.1.2 예측 방식 152
3.3.1.3 양방향 예측 153
3.3.1.4 다이렉트 예측 153
3.3.2 가중치 예측 154
3.3.3 인터레이스 영상 154
3.4 확장 프로파일 156
3.4.1 SP와 SI 슬라이스 123
3.4.2 데이터 분할 슬라이스 157
3.5 움직임 예측 및 모드 결정 방법 158
3.5.1 인터 모드와 인트라 모드 158
3.5.2 H.264/AVC의 매크로블록 모드 결정 방법 160
3.5.2.1 비트율-왜곡 최적화 기법 160
3.5.2.2 H.264/AVC 부호기의 복잡도 161
3.5.2.3 H.264/AVC의 모드 결정 과정 162
3.5.2.4 참조 소프트웨어의 고속 모드 결정 방법 163
3.5.3 가변 부호화 비트율을 위한 고속 인터 모드 결정 방법 165
3.5.3.1 양자화 계수에 따른 모드 분포의 변화 165
3.5.3.2 부 최적 모드 결정 방법의 이용 166
3.5.3.3 가변 부호화 비트율을 위한 고속 모드 결정 방법 168
3.5.4 H.264/AVC의 고속 움직임 예측 방법 170
3.5.4.1 UMHexagonS 170
3.5.4.1.1 초기 탐색점 예측 (initial search point prediction) 171
3.5.4.1.2 Unsymmetrical-Cross Search 176
3.5.4.1.3 Uneven Multi-Hexagon-grid Search 176
3.5.4.1.4 Extended Hexagon-based Search (EHS) 177
3.5.4.1.5 소스 코드 177
3.5.4.2 Center Biased Fractional Pel Search (CBFPS) 180
3.5.4.2.1 H.264/AVC의 계층적 부화소 탐색 방법 180
3.5.4.2.2 CBFPS 방법의 탐색 단계 181
3.5.4.2.3 소스 코드 182
3.6 비트율 제어 183
3.6.1 예비 지식 183
3.6.1.1 Chicken and Egg Dilemma 183
3.6.1.2 기본단위(basic unit)의 정의 184
3.6.1.3 유동 트래픽 모델 (A Fluid Flow Traffic Model) 184
3.6.1.4 왜곡 예측을 위한 선형 모델 (A Linear Model for MAD Prediction) 185
3.6.2 H.264/AVC 비트율 제어 알고리즘 185
3.6.2.1 비트율 제어의 전체 흐름 185
3.6.2.2 GOP 단위 비트율 제어 186
3.6.2.2.1 GOP 내의 비트 총합 186
3.6.2.2.2 각 GOP의 초기 양자화 변수 설정 187
3.6.2.3 화면 단위 비트율 제어 189
3.6.2.3.1 부호화 이전 단계 189
3.6.2.3.1.1 B-화면 양자화 변수 결정 189
3.6.2.3.1.2 P-화면 양자화 변수 결정 190
3.6.2.3.2 부호화 이후 단계 194
3.6.2.4 기본 단위 비트율 제어 195
3.7 엔트로피 코딩 195
3.7.1 문맥 기반 적응적 가변 길이 부호화 195
3.7.1.1 가변 길이 부호화(Variable Length Coding, VLC) 196
3.7.1.2 Exp-Golomb 엔트로피 부호화 197
3.7.1.2.1 unsigned Exp-Golomb codes에 대한 매핑 과정 200
3.7.1.2.2 singed Exp-Golomb codes에 대한 매핑 과정 200
3.7.1.2.3 coded block pattern (cbp)에 대한 매핑 과정 202
3.7.1.2.4 절삭형 Exp-Golomb codes에 대한 매핑 과정 208
3.7.1.3 문맥 기반 적응적 가변 길이 부호화 208
3.7.1.3.1 Coefficients와 trailing ones의 수 부호화 210
3.7.1.3.2 각각의 trailing one의 부호 부호화 219
3.7.1.3.3 남아있는 0이 아닌 coefficients의 level 부호화 219
3.7.1.3.4 마지막 coefficient 앞에 존재하는 모든 0의 수 부호화 222
3.7.1.3.5 각 0의 위치 부호화 225
3.7.2 문맥 기반 적응적 이진 산술 부호화 228
3.7.2.1 문맥 기반 적응적 이진 산술 부호화 구조 228
3.7.2.2 문맥 기반 적응적 이진 산술 부호화 230
3.7.2.2.1 이진화 230
3.7.2.2.2 단항 및 절삭형 단항 이진화 방법 231
3.7.2.2.3 k차 Exp-Golomb 이진화 방법 232
3.7.2.2.4 고정 길이 이진화 방법 233
3.7.2.2.5 기본 이진화의 연결 방법 235
3.7.2.2.6 예외적인 이진화 방법 235
3.7.2.3 문맥 모델링 236
3.7.2.3.1 매크로블록 타입, 예측 모드, 조절 정보의 부호화 241
3.7.2.3.2 매크로블록과 서브 매크로블록의 부호화 241
3.7.2.3.3 매크로블록 스킵 플래그 242
3.7.2.3.4 매크로블록 타입 243
3.7.2.3.5 예측 모드의 부호화 243
3.7.2.3.6 Luma 4×4에 대한 인트라 예측 모드 243
3.7.2.3.7 Chroma에 대한 인트라 예측 모드 244
3.7.2.3.8 참조 화면 인덱스 244
3.7.2.3.9 움직임 벡터 차 성분 245
3.7.2.3.10 제어 정보의 부호화 246
3.7.2.3.11 매크로블록 기반 양자화 변수 변화 246
3.7.2.3.12 슬라이스 끝 플래그 246
3.7.2.3.13 매크로블록 페어 필드 플래그 247
3.7.2.4 잔여 데이터의 부호화 과정 247
3.7.2.4.1 부호화 블록 패턴 248
3.7.2.4.2 부호화 블록 플래그 249
3.7.2.4.3 변환 계수의 스캔 249
3.7.2.4.4 중요한 맵 249
3.7.2.4.5 레벨 정보 250
3.7.2.5 잔여 데이터의 문맥 모델링 250
3.7.2.5.1 부호화 블록 패턴의 문맥 모델링 250
3.7.2.5.2 부호화 블록 플래그의 문맥 모델링 251
3.7.2.5.3 중요한 맵의 문맥 모델링 252
3.7.2.5.4 레벨 정보의 문맥 모델링 252
3.7.2.6 확률 평가 253
3.7.2.6.1 확률 상태 업데이트 254
3.7.2.7 테이블 기반 이진 산술 부호화 255
3.7.2.7.1 이진 산술 부호화 255
3.7.2.7.2 정규 부호화 모드에서 구간 세분화 256
3.7.2.7.3 재정규화 258

제4장 복호기 구조와 알고리즘/261
4.1 복호기 구조 261
4.2 복호 전체 루틴 262
4.3 복호기 초기화 과정 264
4.3.1 H.264/AVC 파일 열기 264
4.3.2 startcode와NALU type 264
4.3.3 SPS 복호 266
4.3.4 PPS 복호 268
4.3.4.1 PPS 복호 예제 271
4.3.5 슬라이스 복호 272
4.4 매크로블록 복호 과정 279
4.4.1 매크로블록의 초기화 start_macroblock() 279
4.4.2 NAL에서 매크로블록의 데이터 읽어 오기 read_one_macroblock() 281
4.4.2.1 NAL에서 데이터 읽어 오기 281
4.4.2.2 read_one_macroblock() 함수 282
4.4.2.3 readMotionInfoFromNAL() 함수 285
4.4.2.4 NAL에서 부호화 블록 패턴과 DCT 계수 읽어 오기 289
4.4.3 매크로블록 복호 decode_one_macroblock() 294
4.5 H.264/AVC 비디오 비트스트림 297
4.5.1 NAL 단위 구문 297
4.5.2 SPS RBSP 구문 300
4.5.3 스케일링 인덱스 구문 308
4.5.4 PPS RBSP 구문 308
4.5.5 RBSP 슬라이스 추적 비트 구문 313
4.5.6 매크로블록 계층 구문 332
4.5.7 잔여 데이터 의미론법 343
4.5.8 잔여 블록에 대한 CAVLC 복호 346
4.5.9 잔여 블록에 대한 CABAC 복호 349

제5장 H.264/AVC 응용을 위한 코덱 최적화/363
5.1 H.264/AVC 복호기 최적화 364
5.1.1 FFMPEG 구동 365
5.1.1.1 Tool 설치 366
5.1.1.2 FFMPEG 다운로드 366
5.1.1.3 FFMPEG 구동 366
5.1.2 FFMPEG에 구현된 H.264/AVC 복호기 구조 367
5.1.3 SIMD 명령어를 이용한 최적화 368
5.1.3.1 IDCT 관련 최적화 369
5.1.3.2 디블록킹 필터 최적화 370
5.1.3.3 움직임 보상 함수 최적화 371
5.2 H.264/AVC 부호기 최적화 379
5.2.1 x264 구동 379
5.2.2 알고리즘 최적화 379
5.2.2.1 고속 모드 결정 380
5.2.2.2 고속 움직임 예측 382
5.2.3 x264 구조 383

참고문헌/386
찾아보기/389

머리말

디지털 영상신호를 포함한 멀티미디어 데이터를 실제 응용분야에 적용하기 위해서는 먼저 주어진 데이터를 효율적으로 압축하는 일이 매우 중요하다. 영상신호 압축을 위한 국제 표준화 기구로는 영상회의와 같은 비디오 응용을 위해 결성된 ITU-T와 비디오/오디오 데이터의 저장 또는 전송 등 다양한 응용분야를 위한 ISO/IEC가 있다. 2001년 말에 ITU-T와 ISO/IEC가 함께 JVT(Joint Video Team)를 구성하여 기존의 MPEG-2, H.263, MPEG-4 비디오 압축 부호화 표준보다 압축 성능이 향상된 H.264/AVC 비디오 부호화 표준을 제정하였다. 최근에 완성된 비디오 압축 표준인 H.264/AVC는 그 성능이 우수하여 현재 전 세계적인 차세대 동영상 압축 기술로 평가받고 있다. 특히, 디지털 TV, 위성 및 지상파 DMB, IPTV 등 차세대 멀티미디어 서비스와 접목되면서 다채널 고화질의 영상 압축, 인터넷이나 케이블 모뎀에서의 영상 전달, 디지털 데이터 방송, 차세대 휴대전화 등 동영상의 교환에 그 응용이 기대된다.
H.264/AVC 표준에서는 비디오 압축 성능을 높이기 위해 기존의 비디오 부호화 표준에 비해 더 작은 크기인 4×4 블록 단위까지의 움직임 보상과 1/4 화소 단위의 움직임 예측, CAVLC와 CABAC과 같은 향상된 엔트로피 부호화 방식, 그리고 새로운 비용함수를 이용한 R-D 최적화 방법 등을 사용하였다. 또한, 주관적 화질의 향상을 위해 부호화 과정 중에 디블록킹 필터를 추가하고, 정수 기반의 4x4 DCT를 사용하여 기존의 비디오 부호화 표준 방식의 부호기와 복호기 사이에 발생했던 DCT 계수 불일치 문제(mismatch problem)를 해결하였다.
따라서 H.264/AVC 비디오 부호화 표준을 이해하고, 나아가 여러 응용 분야에 적용하기 위해서 H.264/AVC에서 사용하고 있는 여러 알고리즘에 대한 원리를 명확하게 이해하고 알고리즘들을 구현한 참조 소프트웨어의 세밀한 구조 및 동작에 대한 분석이 요구된다. 그런 가운데 H.264/AVC 비디오 부호화 알고리즘에 대한 상세한 설명과 함께 소스 코드의 분석에 대한 지도안의 필요성을 절실히 느끼게 되어 2006년 H.264/AVC 참조 소프트웨어 9.5를 기반으로 초판을 집필하게 되었고, 2007년에 H.264/AVC 참조 소프트웨어 11.0을 기반으로 개정판을 만들었다. 개정판 출판 이후에도 H.264/AVC 참조 소프트웨어가 계속하여 갱신되면서 이에 대한 한층 더 심도있는 분석의 필요성을 느끼게 되었다. 2008년에는 H.264/AVC 참조 소프트웨어 13.2를 기반으로 내용을 개정하여 H.264/AVC 알고리즘 이해와 프로그램 분석에 관한 전면 개정판을 냈고, 이번에는 최근에 갱신된 H.264/AVC 참조 소프트웨어 버전 16.0를 기반으로 다시 개정판을 만들게 되었다.
이 책의 구성은 다음과 같다. 먼저 제1장에서는 H.264/AVC 표준을 이해하기 위해 필요한 일반적인 비디오 데이터 압축에 사용되는 기본적인 부호화 방법과 H.264/AVC 부호화 표준에 포함된 주요 기술을 간단히 소개하였다. 제2장에서는 H.264/AVC 공개 소프트웨어인 JM 16.0을 기반으로 H.264/AVC 참조 소프트웨어의 전반적인 데이터 구조를 이해하기 위한 주요 구조체를 소개하고, 주요 함수들의 구조 및 역할을 자세히 분석하여 H.264/AVC 부호기의 전체적인 동작을 쉽게 이해할 수 있도록 설명하였다. 제3장에서는 H.264/AVC 부호기의 주요 알고리즘과 그에 해당하는 소프트웨어 동작을 이해하기 위해 H.264/AVC 부호기의 기본 구조를 움직임 예측, 모드 결정, 비트율 제어, 엔트로피 부호화, 정수기반 4×4 DCT 등의 알고리즘에 대한 상세한 설명과 함께 이에 해당하는 소스코드도 같이 분석하였다. 제4장에서는 H.264/AVC 국제 표준 문서에 명시된 복호기의 구조와 비트스트림 신택스를 설명하였다. 마지막으로, 제5장에서는 그 동안에 H.264/AVC 관련 연구와 여러 프로젝트를 수행하면서 얻은 경험을 기반으로 H.264/AVC 부호기와 복호기의 최적화에 대해 다루었다. 특히, JM 버전 기반의 코드가 아닌 FFMPEG과 x264와 같은 리눅스 기반의 공개 소스 동작과 최적화에 대해 언급했고, 실시간 부호기와 복호기의 구현에 대한 방법을 제시하였다.
이 책은 광주과학기술원 정보통신공학과 영상통신연구실에서 그동안 H.264/AVC 비디오 부호화 방식에 대한 연구를 통한 알고리즘의 이해와 이에 관련된 프로젝트를 통해 축적한 기술들을 포함하고 있다. 무엇보다도 바쁜 가운데 이 책을 준비하는데 많은 도움을 준 영상통신연구실 학생들에게 깊은 고마움을 전하며, 이 책의 출판을 맡아 수고해 주신 도서출판 두양사 관계자 여러분께도 감사를 표한다.
마지막으로, 이 책이 멀티미디어 분야의 실무자들이나 학생들이 H.264/AVC 비디오 부호화 표준을 이해하는데 도움이 되기를 기대하며, 혹시 이 책의 미흡한 부분에 대한 여러분들의 의견을 보내주시면 이 책을 개선하는데 최대한 반영하도록 노력하겠다.

2009년 08월
호요성, 김승환