Advanced
Fast Intra Prediction Mode Decision based on Rough Mode Decision and Most Probable Mode in HEVC
Fast Intra Prediction Mode Decision based on Rough Mode Decision and Most Probable Mode in HEVC
Journal of Broadcast Engineering. 2014. Mar, 19(2): 158-165
Copyright © 2014, The Korean Society of Broadcast Engineers
  • Received : January 03, 2014
  • Accepted : March 18, 2014
  • Published : March 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
승호 이
상효 박
의선 장
esjang@hanyang.ac.kr

Abstract
최신 동영상 압축 표준 기술인 HEVC (High Efficiency Video Coding)는 기존의 AVC/H.264와 비교하여 동일 화질 대비 약 2배의 높은 압축률을 보여준다. 하지만 이러한 성능을 얻기 위하여 복잡한 연산이 필요한 기법들을 많이 도입한 결과, HEVC의 시간 복잡도는 AVC/H.264보다 더욱 증가하게 되었다. 이러한 문제를 해결하기 위하여 다양한 고속 알고리즘 연구가 진행되고 있다. 본 논문에서는 HEVC에 구현된 RMD (Rough Mode Decision)의 결과와 MPM (Most Probable Mode)을 활용하여 고속화된 최적 예측 모드 결정 방법을 제안한다. 제안한 방법은 RMD 과정에서 계산한 예측 방향과 MPM 도출 과정에서 계산한 예측 방향을 비교하여 최적 예측 방향을 선정한다. 이 방법을 All-Intra 환경에서 실험한 결과, 평균 0.8%의 BD-rate 손실이 발생하였고 전체 부호화 실행 시간은 평균 26% 감소하였다.
Keywords
Ⅰ. 서 론
최근 초고해상도 및 초고화질 영상 서비스에 대한 관심이 매우 높아지고 영상 서비스의 수요가 폭발적으로 증가하면서 매우 많은 양의 영상 데이터를 효율적으로 관리해야하는 점이 부각되고 있다. 이러한 흐름에 맞춰 ISO/IEC 산하의 Moving Picture Experts Group (MPEG)과 ITU-T 산하의 Video Coding Experts Group (VCEG)가 Joint Collaborative Team on Video Coding (JCT-VC)을 구성하여 2010년 1월부터 High Efficiency Video Coding (HEVC) 개발에 착수하였고, 2013년 1월에 HEVC의 표준화를 완료하였다 [1] .
HEVC는 이전의 동영상 압축 표준 기술은 AVC/H.264와 비교하여 동일 화질 대비 최대 약 2배까지의 높은 압축률을 보여줌으로써 초고화질 영상의 효율적인 관리가 가능해졌다 [2] . 그러나 HEVC 개발 초기에는 압축률을 극대화하기 위하여 복잡하고 정밀한 기법이 많이 포함하였기 때문에 부호화 연산의 시간 복잡도가 상당히 증가하였다 [3] . 예측 모드를 결정하기 위하여 계산하는 예측 모드의 수가 AVC/H.264에서는 9가지인 반면, HEVC에서는 최대 35가지를 지원한다는 점을 예로 들 수 있다. 이에 따라 압축 효율과 화질을 유지하되, 시간 복잡도를 줄이기 위한 연구의 필요성이 대두되었다.
HEVC에서의 인트라 예측 모드 결정 방법은 영상을 효과적으로 압축시키는 좋은 방법이지만 전체 부호화 시간에서 적지 않은 비중을 차지하기 때문에 시간 복잡도가 매우 높은 편이다 [4] . 또한 조건에 따라 기존 AVC/H.264보다 최대 3배까지 복잡도가 증가하기도 한다 [5] . 이러한 문제를 해결하기 위하여 예측 방향 개수를 최적화하는 방법 [6] , RD (Rate-Distortion) cost 연산 횟수를 최소화하는 방법 [7] [8] [9] 등 다양한 연구가 진행되어왔으나 더욱 많은 연구가 필요한 실정이다. 이에 본 논문은 BD-rate의 손실을 최소화하고 전체 부호화 시간의 단축을 위하여 새로운 고속 인트라 예측 모드 결정 방법을 제안한다.
본 논문의 구성은 다음과 같다. 2장에서는 HEVC의 인트라 예측 모드와 고속 인트라 예측의 핵심 기술인 Rough Mode Decision과 Most Probable Mode에 대하여 설명한다. 그리고 3장에서 이를 활용한 새로운 제안 방법을 설명하고 4장에서 제안 방법을 적용한 실험에 대하여 설명하며 5장에서 결론을 맺는다.
Ⅱ. HEVC의 인트라 예측 모드
HEVC의 인트라 예측 모드 결정 방법과 AVC/H.264의 인트라 예측 모드 결정 방법을 비교했을 때, 가장 큰 차이점은 PU (Prediction Unit)의 크기와 예측 방향의 수이다. AVC/H.264의 PU 크기는 최대 16x16이었으나 HEVC의 PU 크기는 최대 64x64로서 그 크기가 이전보다 커지게 되었고 PU의 단위도 다양해졌다. 또한 AVC/H.264의 예측 모드는 최대 9가지를 지원하지만 HEVC는 최대 35가지를 지원함으로써 좀 더 다양한 방향을 계산할 수 있게 되었다. 그 결과, HEVC는 AVC/H.264보다 유연하면서도 보다 정밀한 예측이 가능하게 되었지만, 인트라 예측 모드를 결정하기 위한 RDO 연산 실행 횟수가 급격하게 많아져 매우 높은 시간 복잡도를 갖게 되었다.
이러한 문제점을 해결하기 위하여 HEVC에는 Rough Mode Decision (RMD) 과정과 Most Probable Mode (MPM)이 추가되었다. RMD는 하다마드 변환을 이용하여 빠르게 SATD (Sum of Absolute Transformed Difference) cost를 계산하고 그 값을 기반으로 최적 예측 모드의 후보를 몇 가지를 골라내어 RMD 후보군을 생성하는 과정이다. 이 방법은 35가지의 모든 예측 모드에 대한 RDO 연산을 하지 않아도 되기 때문에 시간 복잡도를 상당히 많이 감소시킬 수 있다 [10] . MPM은 인트라 예측 모드를 계산하고 있는 PU에서 자기 자신과 근접해 있는 다른 PU의 최종 예측모드를 참조하여 계산한 최고 확률 모드를 의미한다. 만약 인접한 PU가 화면 간 예측 모드를 사용하거나 참조 불가능 등과 같은 제약 조건에 해당한다면, 그 조건에 맞게 DC나 Planar 등의 예측 모드로 대체하게 된다. 이 MPM을 기존 RMD 후보군과 함께 고려하면 좀 더 좋은 압축 성능을 낼 수 있으나 현재 HEVC에는 이 MPM을 추가하고, 대신 RMD 후보군의 크기를 줄임으로써 최종적으로 RDO 연산을 줄이고 시간 복잡도를 감소시키는 방안으로 적용되어있다 [11] .
표 1 은 All-Intra 환경에서 HEVC의 예측 모드 연산의 비중을 나타낸다. 전체 부호화 시간 중에서 RMD 과정에서 후보군을 생성하는 연산 소요 시간과 최적 예측 모드를 계산하는 RDO 연산의 소요 시간을 계산하였다. 표 1 을 보았을 때, 현재 HEVC에는 위 두 가지 기법이 적용되어 있지만 여전히 전체 부호화 과정의 많은 부분을 차지하고 있다. 그렇기 때문에 전체 부호화 실행 시간을 효과적으로 단축하기 위해서는 인트라 예측 모드에 대한 고속화 연구가 이루어져야 한다고 볼 수 있다.
All-Intra 환경에서 인트라 예측 모드 연산 처리 시간 비중
PPT Slide
Lager Image
Table 1. The run time portion of intra prediction in All-Intra environment
그리고 전체 부호화 시간을 효과적으로 줄이기 위해 위 두 가지 기법을 이용하여 고속화를 적용한 알고리즘이 계속 연구되어 왔다 [7] [8] . 그러나 이러한 알고리즘은 추가적인 CU (Coding Unit) 및 TU (Transform Unit)의 정보가 필요하거나 각 PU별로 추가적인 MPM을 검색하기 때문에 그에 따른 추가 연산과 메모리가 필요하다. 또한 CU의 계층 구조에 대한 정보를 이용하기 때문에 CU의 계층 구조 정보를 완벽히 이용할 수 없는 경우, 즉 64x64 크기의 CU 블록이 많은 초고해상도 영상에서는 불리하다는 단점이 있다. 이러한 점을 극복하고자 본 논문에서는 추가적인 정보 없이 RMD 과정을 통하여 생성한 RMD 후보군과 인접한 PU로부터 계산하는 MPM을 이용하여 RDO 연산을 최소화하는 방법을 다음 장과 같이 제안한다.
Ⅲ. RMD와 MPM을 활용한 최적 예측 모드 결정 방법
HEVC는 RMD 과정과 MPM을 통하여, HEVC 인트라 예측 모드의 부호화 시간을 효과적으로 줄여왔다. 그러나 표 2 와 같이 PU 크기에 따라 RMD를 통해 선정한 여러 예측 모드 후보들에 대해서 여러 번의 RDO 연산을 수행해야 하므로 여전히 복잡도가 높다.
PU 크기에 따른 RMD 후보군의 크기
PPT Slide
Lager Image
Table 2. RMD subset size for each PU size
또한 여기에 덧붙여서 MPM을 통해 결정된 모드에 대해서도 RDO 연산을 수행해야 한다. 이러한 여러 예측 모드 후보에 대한 RDO 연산 과정을 최소화하기 위하여, 아래와 같이 RDO 연산을 통한 최적 예측 모드 결정 과정과 RMD 후보군 및 MPM의 연관성을 분석하였다.
표 3 은 RMD 후보군과 MPM을 활용하여 계산한 정보를 나타낸 것이다. 표 3 에 명시된 P_A, P_B|A, P_B는 각각 식 (1), 식 (2), 식 (3)와 같이 계산한다.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
RMD 과정을 통하여 계산한 SATD cost 값이 제일 작은 예측 모드와 MPM에 대한 비율
PPT Slide
Lager Image
Table 3. Ratio of prediction mode which has the least SATD cost value through RMD and Most Probable Mode
RMD_best는 RMD 후보군 중에서 SATD cost가 제일 낮은 모드를 의미하며, P_A는 전체 인트라 예측 연산에서 RMD_best가 MPM에 해당하는 비율을 의미한다. 그리고 P_B|A는 인트라 예측 연산이 A의 경우에 해당할 때, RMD 후보군과 MPM에 대해 RDO 연산을 행하여도 RMD_best가 그대로 최적 예측 모드로 선정된 비율을 의미한다. P_B는 전체 인트라 예측 연산에서 RMD_best가 MPM이면서 동시에 최적 예측 모드인 비율을 의미한다.
표 3 의 비율을 계산하기 위하여 Class A 1개, Class B 1개, Class C 2개, Class D 3개의 영상을 무작위로 선정하였다. 실험에 사용된 영상은 Class A의 Traffic, Class B의 Cactus, Class C의 PartyScene, BasketballDrill, Class D의 RaceHorses, BlowingBubbles, BasketballPass 등 모두 7가지 영상이다. 참조 소프트웨어는 HEVC reference model (HM) 10.0을 사용하였고 QP는 22, 27, 32, 37로 설정하였으며 All-Intra 환경에서 실험을 실시하였다. 그리고 각 QP별로 조건에 맞는 블록의 수를 계산하고 그 결과의 합계를 구한 다음, 7가지의 영상에 대하여 각각 P_A, P_B|A, P_B를 계산하였다.
실험 결과, P_A는 약 71%로 나타났는데 이는 전체 인트라 예측 연산에서 RMD_best가 MPM에 해당할 확률이 약 71%에 이른다는 것을 의미한다. 그리고 P_B|A는 약 78%으로 나타났는데 이는 현재 인트라 블록에서 RMD_best가 MPM에 해당한다는 것만 확인하면, RMD_best가 아닌 나머지 RMD 후보군 및 MPM에 대한 RDO 연산을 하지 않아도 약 78%의 확률로 최적 예측 모드를 결정할 수 있다는 것을 의미한다.
이 결과를 바탕으로 그림 1 의 음영 부분과 같이, RMD_best와 MPM을 비교하는 조건을 추가함으로써 나머지 예측 모드 후보에 대한 RDO 연산을 생략하는 고속 인트라 예측 모드 결정 방법을 제안한다. 본 제안 방법은, 먼저 기존 HEVC 부호화 과정인 35가지 예측 모드에 대한 RMD 과정 및 인접 PU를 활용한 MPM 계산 과정 후에 적용된다. RMD 후보군 중에서 제일 최적의 인트라 예측 모드일 것으로 예상되는 RMD_best가 MPM에 해당하는 경우, 해당 모드를 제일 최적의 인트라 예측 모드라고 판단하고 현재 깊이의 CU에서의 나머지 모드에 대한 RDO 연산을 생략한다. 이 때, 비교 대상인 MPM은 인접한 PU의 최적 예측 모드를 사용하지 못하는 경우에 대체되는 DC나 Planar 모드 등도 포함한다. 그리고 현재 CU가 마지막 깊이에 해당하지 않는다면 다음 깊이의 CU에 대한 인트라 예측 연산을 진행한다. 만약 RMD_best가 MPM에 해당하지 않는다면, 기존 HEVC 부호화 과정대로 RMD 후보군과 MPM에 대하여 모두 RDO 연산을 실행한 후, 다음 깊이의 CU에 대한 인트라 예측 연산을 진행한다.
PPT Slide
Lager Image
제안하는 방법의 알고리즘 Fig. 1. Algorithm of the proposed method
본 제안 알고리즘을 정확도 측면에서 살펴볼 경우, 표 3 의 P_B 값이 약 55%라는 것을 알 수 있다. 이는 제안 알고리즘의 예측 결과와 기존 HEVC 알고리즘의 예측 결과가 같은 경우가 전체 인트라 예측 연산에서 약 55%를 차지한다는 것을 의미한다. 그리고 P_A와 (100 – P_B|A)를 곱하여 전체 인트라 예측 연산에 대해 그 비율을 계산하면 약 16%의 값을 구할 수 있는데, 이는 제안 알고리즘의 예측 결과가 기존 HEVC 알고리즘의 예측 결과보다 정확하지 못한 경우가 전체 인트라 예측 연산에서 약 16%인 것을 의미한다. 그러나 이 경우, RMD_best가 제 1의 최적 예측 모드가 되지 않더라도 제 2 또는 제 3의 최적 예측 모드가 될 수 있기 때문에 BD-rate 손실을 최소화할 수 있을 것으로 예상한다.
즉, 제안 알고리즘은 전체 인트라 예측 연산에 대해 55% 확률로 빠르면서도 정확하게 계산할 수 있고 16%의 확률로 정확하지는 않지만 제 2 또는 제 3의 최적 예측 모드를 빠르게 계산할 수 있다. 그리고 나머지 29%의 확률로 기존 HEVC 알고리즘을 사용하기 때문에 제안 알고리즘의 정확도는 약 84%정도로 예상할 수 있다.
Ⅳ. 실험 결과
본 논문에서는 제안하는 방법을 실험하기 위하여 HM 10.0을 사용하였다. 또한 표 4 에 명시된 환경에서 실험을 진행하였고 표 5 에 명시된 영상들을 실험에 사용하였다.
실험 환경
PPT Slide
Lager Image
Table 4. Test environment
실험 영상
PPT Slide
Lager Image
Table 5. Test sequence
새로 제안한 방법의 결과의 우수성을 증명하기 위하여 기존 HM 10.0 외에도 참고 문헌 [8] , [9] 의 고속 인트라 예측 알고리즘을 HM 10.0에 구현하였다. 그리고 기존 HM 10.0 부호화기에 대하여 제안 알고리즘을 비롯한 여러 고속 알고리즘이 각각 적용된 부호화기의 BD-rate 손실률과 전체 부호화 시간 증감률을 각각 계산하였다. 참고 문헌 [8] 의 경우, 해당 고속 알고리즘은 제안 알고리즘처럼 RMD와 MPM을 활용하여 RDO 연산 횟수를 간소화하는 과정도 포함하고 있으나, 제안 알고리즘과의 비교 범주에서 벗어나는 CU 조기 결정 과정도 함께 포함되어 있다. 그래서 참고 문헌 [8] 의 알고리즘에서 RMD와 MPM을 활용하는 과정만 구현하였고, 제안 알고리즘과 다르게 현재 깊이 CU의 RMD_best가 MPM에 해당하면서 또한 상위 CU의 최적 예측 모드와 동일해야만 현재 깊이 CU의 인트라 예측 연산을 생략하고 다음 깊이 CU에 대한 인트라 예측 연산을 하도록 하였다.
실험 영상들에 대해 각 QP별로 부호화를 실시한 후 각각의 비교 결과, 그리고 그 비교 결과를 Class별로 분류한 결과로 정리하였다. 기존 HEVC 알고리즘의 부호화 시간 t_HM10.0과 고속 알고리즘의 부호화 시간 t_fast에 따른 전체 부호화 시간 증감률 △t는 식 (4)와 같이 계산한다.
PPT Slide
Lager Image
표 6 은 기존 HM 10.0 부호화기에 대해 각기 다른 고속 예측 알고리즘이 적용된 HM 10.0 부호화기 및 제안 알고리즘이 적용된 HM 10.0 부호화기를 비교하여 성능을 측정한 결과다. 실험 결과, 제안 알고리즘이 기존 HM 10.0보다 평균 0.8% 정도의 BD-rate 손실률을 보였으나 전체 부호화시간은 평균 26% 감소했음을 확인하였다. Class별로 분석한 결과, 대체적으로 저해상도 영상일수록 BD-rate 손실률이 높아지고 전체 부호화 시간의 감소율이 낮아지는 반면, 고해상도 영상일수록 BD-rate 손실률이 낮아지고 전체 부호화 시간의 감소율이 높아지는 경향이 있었다.
BD-rate 손실률 및 부호화 시간 감소율
PPT Slide
Lager Image
Table 6. Reduction of BD-rate and encoding time
또한 다른 고속 알고리즘과 비교하여도 전체 부호화 시간을 상당히 줄어든 것을 알 수 있었다. 참고 문헌 [9] 의 알고리즘을 적용한 결과와 비교했을 때, 제안 알고리즘이 약 8% 정도 부호화 시간을 더 많이 단축할 수 있었다. 이는 참고 문헌 [9] 의 알고리즘에서 모든 크기의 블록에 대해 RDO 연산을 해야 하는 예측 모드가 최소 2개에서 최대 5개까지 있기 때문에 제안 알고리즘에 비해 전체 부호화 시간이 늘어난 것으로 생각된다. 또한 참고 문헌 [9] 의 알고리즘에는 64x64 크기의 CU 블록 예측 연산에 대한 고속화 과정이 적용되어 있지 않기 때문에, 비슷한 픽셀 값을 가진 64x64 크기의 CU 블록이 많을 것으로 예상할 수 있는 고해상도 영상일수록 제안 알고리즘이 참고 문헌 [9] 의 알고리즘보다 더 유리한 것으로 생각된다.
Ⅴ. 결 론
본 논문에서는 기존 HEVC의 인트라 예측 모드 결정 과정에서 사용되는 RMD와 MPM만을 활용한 방법을 제안하였다. 최소한의 정보만을 활용하여 RDO 연산을 최소화하면서 동시에 최대한 정확하게 결과를 계산한다는 점이 제안한 방법의 핵심이다. 그 결과, BD-rate 손실률을 최대 1%로 억제하면서 전체 부호화 시간을 평균 26%가량 감소시킬 수 있었다. 본 논문에서 제안한 알고리즘은 RMD 후보군 중에서 SATD cost 값이 제일 작은 예측 모드만 골라 MPM과 비교하였으나, 참고 문헌 [9] 의 알고리즘처럼 특정한 기준을 만들고 해당 기준에 적합한 여러 예측 모드와 MPM을 비교하는 방법 등 여러 방식으로 응용할 수 있을 것으로 예상한다. 또한 다른 기법과 병합하여 사용한다면 보다 더 좋은 성능을 보일 수 있을 것으로 기대한다.
BIO
이 승 호
- 2014년 : 한양대학교 컴퓨터공학부 학사
- 2014년 ~ 현재 : 한양대학교 컴퓨터·소프트웨어학과 석사과정
- 주관심분야 : 영상압축, HEVC/H.265
박 상 효
- 2011년 : 한양대학교 컴퓨터전공 학사
- 2011년 ~ 현재 : 한양대학교 컴퓨터·소프트웨어학과 석박사통합과정
- 주관심분야 : 영상압축, MPEG-H HEVC/H.265, MPEG IVC, MPEG VCB
장 의 선
- 1991년 : 전북대학교 전자계산기학 학사
- 1994년 : State University of New York at Buffalo, 전기컴퓨터공학 석사
- 1995년 : U.S. Army Research Lab, Research Associate
- 1996년 : State University of New York at Buffalo, 전기컴퓨터공학 박사
- 1996년 ~ 2002년 : 삼성종합기술원 책임연구원
- 1996년 ~ 2000년 : MPEG-4 Project Editor
- 1999년, 2003년, 2011년 : ISO/IEC Certificate of Appreciation (공로상) 수상
- 2002년 ~ 현재 : 한양대학교 컴퓨터공학부 교수
- 2004년 ~ 2010년 : MPEG RVC AdHoc Group 의장
- 2005년 : 대통령 표창 수상
- 2005년 ~ 현재 : SIGNAL PROCESSING: IMAGE COMMUNICATION, Area Editor
- 2011년 ~ 현재 : IEEE Senior member
- 주관심분야 : 영상처리, MPEG 표준, 3D 그래픽스, 미디어 부호화, 하드웨어/소프트웨어 동시설계
References
JCT-VC 2013 “High Efficiency Video Coding (HEVC) text specification draft 10 (for FDIS & Last Call), Document JCTVC-L1003 Geneva
JCT-VC 2013 “Comparison of Compression Performance of HEVC Draft 10 with AVC for UHD-1 material”, Document JCTVC-M0166 Incheon
JCT-VC 2011 “Report on the evaluation of HM versus JM”, Document JCTVC-D181 Daegu
Bossen F. , Bross B. , Suhring K. , Flynn D. 2012 “HEVC Complexity and Implementation Analysis” Circuits and Systems for Video Technology, IEEE Transactions on 22 (12) 1685 - 1696    DOI : 10.1109/TCSVT.2012.2221255
Vanne J. , Viitanen M. , Hamalainen T. , Hallpuro A. 2012 “Comparative Rate-Distortion-Complexity Analysis of HEVC and AVC Video Codecs” Circuits and Systems for Video Technology, IEEE Transactions on 22 (12) 1885 - 1898    DOI : 10.1109/TCSVT.2012.2223013
Gwon D. , Lee S. , Choi H. 2012 “HEVC Intra Prediction Performance Analysis and Complexity Reduction Method” Proceeding of the Korean Society of Broadcast Engineer Conference November Vol. 2012, No. 11 176 - 179
Kim J. , Yang J. , Lee H. , Jeon B. 2011 “Fast Intra Mode Decision of HEVC based on Hierarchical Structure” Information, Communications and Signal Processing (ICICS) 2011 8th International Conference on December
Shen L. , Zhang Z. , An P. 2013 “Fast CU Size Decision and Mode Decision Algorithm for HEVC Intra Coding” Consumer Electronics, IEEE Transactions on 59 (1) 207 - 213    DOI : 10.1109/TCE.2013.6490261
Zhang M. , Zhao C. , Xu J. 2012 “An Adaptive Fast Intra Mode Decision in HEVC” Image Processing (ICIP), 2012 19th IEEE International Conference on September
JCT-VC 2010 “Encoder improvement of unified intra prediction”, Document JCTVC-C207 Guangzhou
Zhao L. , Zhang L. , Ma S. , Zha D. 2011 “Fast Mode Decision Algorithm for Intra Prediction in HEVC” Visual Communications and Image Processing (VCIP) Conference November