변환 계수를 이용한 고속 HEVC 부호화 알고리즘

국문 초록 (Abstract)

HEVC 인코더는 기본 처리 단위인 Coding Unit (CU), CU를 예측하는 단위인 Prediction Unit (PU), 예측 블록을 주파수 영역으로 변환하고 양자화하는 Transform Unit (TU)를 사용해 영상을 압축한다. HEVC가 이전 영상 압축 표준들과 구분되는 가장 큰 특성은 다양한 크기의 기본 처리 단위를 지원한다는 것이다. 이러한 처리 단위는 쿼드트리 (Quadtree) 구조로 이루어져 있어, 동일한 영상 블록에 대해 다양한 크기의 처리 단위로 연산을 수행한다. 이를 통해 HEVC는 이전 표준에 비해 두 배의 압축 효율을 낼 수 있게 되었지만, 연산 복잡도가 상당히 증가하게 되었다. 이를 해결하기 위해 본 논문에서는 자연 영상을 부호화할 때 나타나는 통계적 특성에 착안하여 고속 알고리즘을 제안하였다.
제안 알고리즘은 CU 범위를 제한하고, 움직임 추정과 화면 내 예측을 적절히 생략하는 방법으로 인코더의 복잡도를 낮추었다. 효과적으로 CU 수행 범위를 제한하기 위해, 큰 CU에서 얻은 정보를 사용해 CU 작은 CU의 수행 여부를 결정할 수 있도록 하였다. 이는 큰 CU의 인코딩 소요 시간이 상대적으로 짧으면서도 선택될 확률이 높다는 경향에 따른 것이다. 최대 CU에서 8×8 DCT 결과를 보고 Split Map을 작성하여 해당 영역에서의 최소 CU를 결정한다. 또한 화면 간 예측에서 가장 계산 복잡도가 높은 움직임 추정을 생략하기 위해 현재 CU에서의 최소 TU 정보를 사용하였다. 2N×2N PU 수행 결과 Merge/SKIP을 선택한 경우 이후 수행하는 PU에서 DCT 결과가 0인 부분에 대해 움직임 추정을 생략하도록 하였다. 추가적으로 휘도 성분의 DCT 결과를 통해 화면 내 예측을 생략하도록 하였다.
본 논문에서 CU 범위 제한, 움직임 추정과 화면 내 예측 생략을 수행하기 위해 사용한 정보는 각 경우에 맞는 TU 정보이다. 기존 알고리즘에서 주로 사용된 CBF (Coded Block Flag) 대신 작은 TU 정보를 수집하여 사용함으로써 블록 전체에 대한 연산 생략 여부를 결정하는 대신 블록 일부에 대한 연산을 선택적으로 생략할 수 있도록 하였다. 이를 통해 공격적으로 CU와 PU 연산을 생략하지 않고도 기존 알고리즘과 비슷한 시간 감소율을 얻으면서, 동시에 기존 알고리즘의 성능을 개선시키는 효과를 얻었다. 제안 알고리즘은 HM 10.0에 구현하였으며, 시뮬레이션 결과 원본 인코더에 비해 평균 64.0%의 부호화 시간을 절약할 수 있었으며, 평균 BD-BR 증가는 0.42%에 불과하였다.

다국어 초록 (Multilingual Abstract)

The emerging video compression standard HEVC (High Efficiency Video Coding) adopts the Quadtree structure. The structure includes CU (Coding Unit), PU (Prediction Unit), and TU (Transform Unit). CU is the basic unit of compression, which is predicted using various PUs. The residuals are then transformed into frequency domain for compression. The important thing about the Quadtree is various block size. For a single region, HEVC examines many times of predictions and transforms with the various block sizes. It makes HEVC encoder achieve half bit-rate of previous standard, but the computational complexity is highly increased. To alleviate this problem, this paper presents the fast algorithm which considers the statistical features of natural videos.
Proposed Algorithm reduces the computational complexity of HEVC encoder by limiting the range of CU and skipping the motion estimation and intra-prediction. To limit the CU range, the proposed algorithm makes use of the transformed residuals from the biggest CU. If the 8×8 DCT coefficients are all zero in certain sub-region of the biggest CU, then CU splitting in the corresponding region is limited dynamically due to the size of the region. CU split map is made to control the CU splitting. On the other hand, to skip the motion estimation effectively, the proposed method makes use of the smallest DCT coefficients. Similar to CU range limiting method, motion estimation is skipped when 2N×2N PU is merged and the sub-partition block has all-zero coefficients from the smallest TUs. Intra-prediction is also skipped when the all smallest TUs have all-zero coefficients in 2N×2N luma block.
The important information that the proposed method exploits is the result of small TUs. CBF (Coded Block Flag) value is widely used in other fast algorithms for HEVC. However, CBF cannot show the residual information in partial region. In other words, since the proposed method uses small TU information, not CBF, it can reduce the computation of partial blocks. By doing so, the proposed algorithm achieves 64.0% of encoding time reduction with only 0.42% of BD-BR increment.

목차 (Table of Contents)

• 1 서론 1
• 2 HEVC 인코더의 이해 5
• 2.1 CU (CODING UNIT) 6
• 2.2 PU (PREDICTION UNIT) 8
• 2.3 TU (TRANSFORM UNIT) 14
• 3 기존의 고속 HEVC 인코딩 알고리즘 15
• 3.1 ECU (EARLY CU) 15
• 3.2 FDM (FAST DECISION FOR MERGE RD COST) 16
• 3.3 CFM (CBF FAST MODE) 17
• 3.4 ESD (EARLY SKIP DETECTION) 19
• 3.5 기타 고속 알고리즘 20
• 4 제안한 고속 HEVC 인코딩 알고리즘 23
• 4.1 CODING UNIT (CU) 범위 제한 23
• 4.2 움직임 추정 생략 알고리즘 30
• 4.3 화면 내 예측 생략 40
• 5 제안 알고리즘의 성능 측정 결과 및 분석 43
• 5.1 성능 측정 결과 43
• 5.2 결과 분석 48
• 6 결론 51
• 참고문헌 53
• 국문초록 58
• ABSTRACT 60