비디오 영상 압축을 위한 해시 기반 정수 단위 움직임 추정 알고리즘 ; A hash-based search algorithm for integer motion estimation in HEVC

학위논문 (박사)-- 서울대학교 대학원 : 공과대학 전기·정보공학부, 2018. 8. 이혁재. ; 본 논문은 HEVC의 프레임 간 예측 (inter prediction)을 위한 해시 기반 정수 단위 움직임 탐색 알고리즘에 관한 연구이다. 일반적으로 해시 기반 탐색은 전처리 단계와 움직임 벡터 탐색의 2단계로 구성된다. 전처리 단계는 해시 함수를 이용하여 비슷한 특징을 가지는 블록들을 해시 테이블의 하나의 버켓에 저장함으로써, 데이터를 분류한다. 움직임 벡터 탐색 단계는 해시 테이블에서 현재 블록과 동일한 해시 키를 가진 버켓을 선택한 후, 그 버켓 안에 있는 블록들 중에서 RD cost가 가장 낮은 블록을 찾는다. 따라서 탐색 복잡도와 탐색 성능은 해시 함수에 따라 달라진다. 최근 몇 개의 해시 기반 움직임 벡터 탐색 알고리즘들이 제안되었는데, 그들은 몇 가지 제약사항이 있다. 첫째, 입력 영상과는 무관하게 고정된 해시 함수를 사용한다. 그 결과 탐색 복잡도가 입력 영상에 따라 크게 달라진다. 둘째, 대부분의 움직임 벡터가 현재 블록의 AMVP 주변에서 선택됨에도 불구하고, 참조 영상 안에 있는 모든 참조 블록을 탐색에 사용한다. 즉, IME 검색 범위를 제어할 수 있는 방법이 없다. 셋째, HEVC에서 허용되는 모든 PU 유형에 대해 해시 기반 검색을 지원하는 것이 거의 불가능하기 때문에 복잡성을 줄이기 위해 2Nx2N PU에만 적용된다. 제안된 해시 기반 탐색 알고리즘은 이러한 제약사항을 완화하였다. 첫째, CTU 단위 가변 해시 함수를 사용하여, 입력 영상과 무관하게 탐색 복잡도를 일정하게 유지한다. 이를 위하여 Product Quantization (PQ)을 기반으로 입력 영상의 데이터 분포에 적합한 해시 키의 길이와 해시 함수 구성을 갖는 해시 함수를 찾는다. 그리고 해시 함수를 찾기 위한 복잡도를 줄이기 위하여 현재 CTU와 비슷한 통계를 가지는 이전 CTU를 찾은 후, 그 CTU에서 사용한 해시 함수를 재사용하는 방법을 같이 사용한다. 둘째, 해시 테이블은 참조 블록이 속하는 CTU의 주소를 기반으로 CTU 단위로 생성된다. 그리고 움직임 벡터 탐색 단계에서 AMVP 주변의 CTU들만 탐색하도록 함으로써 불필요한 연산을 제거 할 수 있다. 또한 해시 기반 검색은 검색 복잡성을 줄이기 위해 8x8보다 작은 PU의 탐색으로 제한되고, 8x8보다 큰 PU를 검색하는 것은 하위 PU의 해시 기반 검색 결과를 사용하여 현재 블록의 검색 후보를 찾는 상향식 탐색을 사용한다. 그리고 제안된 알고리즘은 4x4 블록 단위로 해시 키를 생성한다. 그래서 하나의 PU 내의 모든 4x4 블록에 대해 해시 키를 만들고, 이 해시 키들 중 하나와 동일한 해시 키를 갖는 모든 블록을 탐색과정에서 사용한다. 그 결과 해시 기반 탐색의 성능을 높일 수 있다. 또한 하나의 해시 테이블을 이용하여 여러 가지 크기의 PU 탐색에 적용이 가능하다. 그 결과 제안하는 탐색 알고리즘은 참조 알고리즘 대비 낮은 탐색 복잡도를 가지면서 입력 영상과 무관하게 일정한 탐색 복잡도를 제공한다. 그리고 카메라 영상과 스크린 영상 모두에 대해서 비슷한 수준의 성능을 제공한다. 실험에 의하면 1080p 카메라 영상에서 0.36%의 압축 효율 손실로 전체 탐색 복잡도를 70% 정도 줄일 수 있고, 720p 카메라 영상은 0.33%의 압축 효율 손실로 복잡도를 40% 정도 줄일 수 있었다. 그리고 1080p 스크린 영상은 0.18%의 압축 효율 향상과 함께 복잡도를 50% 정도 줄일 수 있고, 720p 카메라 영상은 0.53%의 압축 효율 향상과 함께 복잡도를 20% 정도 줄일 수 있었다. 그리고 동일한 알고리즘을 프레임 내 예측을 위한 탐색 알고리즘에 적용한 경우 참조 알고리즘과 비교하여 약 50%의 복잡도로 `1~4%의 코딩 이득을 얻을 수 있었다. ; 제 1 장 서 론 1 제 1.1 절 연구의 배경 1 제 1.2 절 연구의 내용 2 제 1.3 절 공통 실험 환경 3 제 1.4 절 논문의 구성 4 제 2 장 배경 지식 5 제 2.1 절 High Efficiency Video Coding (HEVC) 5 제 2.2 절 정수 단위 움직임 탐색 ...