A Study on Integer Motion Estimation in HEVC using Hash-based Search

학위논문 (석사)-- 서울대학교 대학원 : 공과대학 전기·정보공학부, 2018. 2. 채수익.HEVC 인코더에서 시간적으로 인접한 picture 간에 상관성이 높은 점을 이용하는 inter prediction 연산의 대부분은 reference picture에서 현재 block과 움직임이 유사한 prediction unit (PU)을 찾는 과정인 Integer Motion Estimation (IME)이 차지한다. 최근에 제안된 IME 알고리듬[4]은 HM 경우와 같이 TZ search 알고리듬 기반이지만 bottom-up 탐색 방법을 이용하여 motion vector predictor를 찾는데 기존 top-down 방식 대비 BD-rate은 0.03% 증가하였고 IME의 계산 복잡도는 25.3%로 감소하였다. 본 논문은 bottom-up IME 알고리듬을 기반으로 하되 가장 작은 CU의 IME에 적용된 TZ search 알고리듬을 LSH(locality sensitive hashing) 기반 search 방법으로 대체하여 코딩효율의 저하 없이 IME의 복잡도를 더 줄이는 가능성을 탐색하는 내용을 담고 있다. 시도한 hash-based IME 알고리듬은 크게 3단계로 구성되어 있다. 첫 번째 단계인 hash key generation에서는 입력 영상의 각 pel을 upper-left로 갖는 4x4 block의 pel값 평균을 구한 뒤, pel값 분포를 고려하여 hash key를 생성한다. 두 번째 단계인 hash table building에서는 앞서 생성한 hash key에 해당하는 bucket에 element를 저장한다. 본 논문에서는 IME 수행 시 RD-cost의 rate에 해당하는 값이 AMVP에 가까울수록 작다는 점에 착안하여 hash table을 picture 단위가 아닌 CTU단위로 만들었으며, 이미지의 특성을 고려하여 카테고리를 나눈 뒤 해당 정보를 hash 4x4 block의 위치 정보와 함께 저장하였다. 마지막 hash-based search 단계에서는 우선 AMVP 주변 CTU의 hash table을 찾은 후 현재 block으로부터 생성한 hash key에 해당하는 bucket을 찾는다. 이후, bucket의 element 중에서 탐색 범위 안에 위치하며 현재 block의 카테고리와 동일한 참조 block에 대해 RD-cost를 계산하여 움직임을 예측한다. 이에 더하여 bottom-up IME 알고리듬을 4x4 block에도 적용하여 IME의 복잡도를 줄이도록 노력하였다. HEVC 공통 실험 조건의 Class B 시퀀스(BasketballDrive, BQTerrace, Cactus, Kimono, ParkScene), Low Delay P (LDP) 환경에서 QP값 12, 14, 16, 18에 대하여 실험을 수행하였고, 성능 측정은 HM을 기준으로 하였다. 실험 결과에 의하면 제안한 hash-based IME 알고리듬은 bottom-up 방식과 동일한 BD-rate에서 IME 연산 복잡도가 HM 대비 44.6%로 감소하였다. 반면, BD-rate을 0.07%로 증가시킨 경우는 압축 결과물에서 육안으로 차이점을 확인 할 수 없었지만, IME 연산 복잡도는 HM 대비 16.7%로 감소하였다. 추가적으로 4x4 block에도 bottom-up IME 알고리듬을 적용하는 경우에는 bottom-up 방식과 동일한 BD-rate에서 IME 연산 복잡도가 HM대비 24.7%로 감소하였다. 반면, BD-rate을 0.04%로 증가시킨 경우는 IME 연산 복잡도가 HM 대비 13.7%로 감소하였다.제 1 장 서 론 1 1.1 연구의 배경 1 1.2 관련 연구 3 1.3 논문의 구성 4 제 2 장 HM 인코더의 Inter Prediction과 Bottom-up Motion Vector prediction 5 2.1 HM 인코더의 Inter Prediction 5 2.1.1 Merge Estimation 5 2.1.2 Advance Motion Vector Prediction (AMVP) 10 2.1.3 Integer Motion Estimation 11 2.2 Multiple Motion Vector Predictor with Bottom-up Motion Vector Prediction 14 제 3 장 Hash Table Methods 20 3.1 Hash Table 20 3.2 Hash Function 23 3.3 기존 Hash-based Search 알고리듬 24 제 4 장 시도한 Hash-based Integer Motion Vector Estimation 26 4.1 Hash Key Generation 28 4.1.1 SCM의 Hash Key Generation 28 4.1.2 시도한 Hash Key Generation 30 4.2 Hash Table Building 35 4.3 Diamond Shape Search Range와 Categorizing 38 4.4 Hash-based Integer Motion Vector Search와 4x4 block 단위 bottom-up IME 43 제 5 장 실험 결과 48 5.1 Hash Key별 기본 성능과 Overlapping 적용 실험 49 5.2 Search Range 변경 실험 54 5.3 Category Search 적용 실험 57 5.4 4x4 block 단위 bottom-up IME 62 제 6 장 결 론 63Maste