본 논문에서는 차세대 비디오 표준인 High Efficiency Video Coding(HEVC)의 영상 부호화 과정의 시간복잡도 감소를 위한 효율적인 PredictionUnit(PU)레벨 움직임예측(Motion Estimation, ME) 병렬화의 구현 기법을 제시하고자 한다. 움직임예측 과정은 부호화기에서 80%의 복잡도를 차지하는 과정으로 고속 부호화의 걸림돌이 되고 있다. 이를 해결하기 위한 많은 기술들이 제안되었는데, 그 방법 중의 하나가 움직임예측 알고리즘의 병렬화이다. 이러한 병렬 ME 설계의 일환으로 ME의 일부인 Merge Estimation의 병렬화를 위한 Merge Estimation Region(MER)기반의 설계방법이 제안되었다. 하지만 HEVC Test Model reference software(HM)에 반영된 MER을 이용하여 실제로 병렬화 된 ME를 구현하는 과정에서는 알고리즘 측면에서 아직 고려되지 않은 문제들이 존재한다. 이에 본 논문에서는 HM을 바탕으로 MER을 사용한 안정적인 병렬 ME를 구현하기 위한 전략으로 각 PU의 정보를 독립적으로 사용하기 위한 부분 순차화 방법과 메모리 접근제한을 이용한 병렬화 방법을 제시한다. 실험을 통해 본 연구의 우수성이 확인되었는데, 제안된 방법에 기반을 둔 구현의 전체 부호화 시간이 순차적인 ME를 이용한 HM의 것보다 평균 25.64% 감소하였다.
본 논문에서는 차세대 비디오 표준인 High Efficiency Video Coding(HEVC)의 영상 부호화 과정의 시간복잡도 감소를 위한 효율적인 Prediction Unit(PU)레벨 움직임예측(Motion Estimation, ME) 병렬화의 구현 기법을 제시하고자 한다. 움직임예측 과정은 부호화기에서 80%의 복잡도를 차지하는 과정으로 고속 부호화의 걸림돌이 되고 있다. 이를 해결하기 위한 많은 기술들이 제안되었는데, 그 방법 중의 하나가 움직임예측 알고리즘의 병렬화이다. 이러한 병렬 ME 설계의 일환으로 ME의 일부인 Merge Estimation의 병렬화를 위한 Merge Estimation Region(MER)기반의 설계방법이 제안되었다. 하지만 HEVC Test Model reference software(HM)에 반영된 MER을 이용하여 실제로 병렬화 된 ME를 구현하는 과정에서는 알고리즘 측면에서 아직 고려되지 않은 문제들이 존재한다. 이에 본 논문에서는 HM을 바탕으로 MER을 사용한 안정적인 병렬 ME를 구현하기 위한 전략으로 각 PU의 정보를 독립적으로 사용하기 위한 부분 순차화 방법과 메모리 접근제한을 이용한 병렬화 방법을 제시한다. 실험을 통해 본 연구의 우수성이 확인되었는데, 제안된 방법에 기반을 둔 구현의 전체 부호화 시간이 순차적인 ME를 이용한 HM의 것보다 평균 25.64% 감소하였다.
In this paper, we propose an efficient parallelization technique of PU-level motion estimation (ME) in the next generation video coding standard, high efficiency video coding (HEVC) to reduce the time complexity of video encoding. It is difficult to encode video in real-time because ME has significa...
In this paper, we propose an efficient parallelization technique of PU-level motion estimation (ME) in the next generation video coding standard, high efficiency video coding (HEVC) to reduce the time complexity of video encoding. It is difficult to encode video in real-time because ME has significant complexity (i.e., 80 percent at the encoder). In order to solve this problem, various techniques have been studied, and among them is the parallelization, which is carefully concerned in algorithm-level ME design. In this regard, merge estimation method using merge estimation region (MER) that enables ME to be designed in parallel has been proposed; but, parallel ME based on MER has still unconsidered problems to be implemented ideally in HEVC test model (HM). Therefore, we propose two strategies to implement stable parallel ME using MER in HM. Through experimental results, the excellence of our proposed methods is shown; the encoding time using the proposed method is reduced by 25.64 percent on average of that of HM which uses sequential ME.
In this paper, we propose an efficient parallelization technique of PU-level motion estimation (ME) in the next generation video coding standard, high efficiency video coding (HEVC) to reduce the time complexity of video encoding. It is difficult to encode video in real-time because ME has significant complexity (i.e., 80 percent at the encoder). In order to solve this problem, various techniques have been studied, and among them is the parallelization, which is carefully concerned in algorithm-level ME design. In this regard, merge estimation method using merge estimation region (MER) that enables ME to be designed in parallel has been proposed; but, parallel ME based on MER has still unconsidered problems to be implemented ideally in HEVC test model (HM). Therefore, we propose two strategies to implement stable parallel ME using MER in HM. Through experimental results, the excellence of our proposed methods is shown; the encoding time using the proposed method is reduced by 25.64 percent on average of that of HM which uses sequential ME.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 ME의 효율적인 적용을 위한 HM 기반 병렬화 구현에서 발생하는 문제의 해결방법을 원인에 따라 제안하였다. 순서적인 처리를 바탕으로 구현된 HEVC의 특징 때문에 발생할 수 있는 병렬화의 문제는 CU레벨 정보의 일관성 문제와 함수 동시 호출로 인한 메모리 동시접근 문제가 있다.
0에는 MER의 기능적인 부분만 반영되어 있으며 실제 HM을 바탕으로 부호화기의 ME과정을 다양한 방법으로 병렬화하는 과정에서는 알고리즘 수준에서 고려되지 않았던 상황들이 발생한다[5]. 이에 본 논문에서는 MER이 반영된 HM6.0을 기반으로 PU레벨 병렬화 ME를 구현하는 과정을 실제로 수행하면서 발생한 문제점을 제시하고 해결방법을 제안한다.
제안 방법
18 % 이었다. Bit-rate의 경우 이미 MER을 사용한 코딩을 통해 발생하는 증가비율이 보고되어 있는데, 본 실험에서도 동일한 sequence에 대해 같은 증가 비율을 보이므로 시간측면에서의 복잡도 감소만을 결과로 제시한다.
그림1의 PU0, PU1 사각형은 각 PU에 각각의 thread가 할당되어 오른쪽방향으로 정보처리를 진행하면서 CU에 정보를 읽고 쓰는 과정을 보여준다. HM6.0의 inter prediction과정에서는 ME를 진행하기 전과 후에 각각 당시의 최적 참조 대상의 정보(①,③)를 읽은 후에 비교를 통해 무결성을 입증하고, 무결성이 확인되면 수행한 ME의 결과를 비교하여 정보를 갱신한다. 이때 서로 다른 thread에서 정보를 쓴 후(②) 다시 읽어오게 되면(④) PU1과 같이 뒤늦게 정보 갱신하는 PU에서는 ME를 진행하기 전에 저장된 최적 참조 후보의 정보와(③) 일치하지 않게 되므로 올바르지 않은 부호화가 진행되고 있음으로 인식된다.
순서적인 처리를 바탕으로 구현된 HEVC의 특징 때문에 발생할 수 있는 병렬화의 문제는 CU레벨 정보의 일관성 문제와 함수 동시 호출로 인한 메모리 동시접근 문제가 있다. 다수의 thread가 공유하는 정보영역을 접근함으로 인한 정보 불일치성을 해결하기 위해서는 부분 병렬화 구현 기법을 제안하였다. 또한 메모리 동시 접근 발생을 방지하기 위한 방법으로 제한적인 thread의 변수 및 함수 호출을 제안했다.
다수의 thread가 공유하는 정보영역을 접근함으로 인한 정보 불일치성을 해결하기 위해서는 부분 병렬화 구현 기법을 제안하였다. 또한 메모리 동시 접근 발생을 방지하기 위한 방법으로 제한적인 thread의 변수 및 함수 호출을 제안했다. 제안된 방법을 적용하여 각 thread를 제한적으로 병렬 구현을 하면 전체를 병렬화 한 경우와 비교하여 thread를 스케줄링하는 오버헤드와 제한된 부분에서의 지연시간이 추가로 발생하지만, 보다 안정된 병렬화를 구현할 수 있다.
시간 복잡도의 감소를 효과적으로 비교하기 위해 병렬화를 통한 전체 부호화 시간의 감소를 제시한다. 비교 대상은 HEVC 구현 환경을 대상으로 MER의 크기를 병렬화 경우와 동일하게 설정한 부호화 시간이다.
이를 위해서는 동시에 여러 thread에서 최적 참조 대상 정보에 접근할 수 없도록 임계영역을 설정해야 하는데, 현재의 HM software에 구현된 inter prediction과정에서는 하나의 참조 후보에 대해 해당 후보가 최적 참조 대상인지 검사하는 과정이 ME에 포함되어 한 번에 이루어지기 때문에 임계영역을 설정하기에 용이하지 않다. 이에 효과적인 병렬화 구현을 지원하기 위해HM6.0을 바탕으로 그림2 의 (b)와 같이 움직임 예측과정 알고리즘을 수정할 것을 제안한다.
대상 데이터
시간 복잡도의 감소를 효과적으로 비교하기 위해 병렬화를 통한 전체 부호화 시간의 감소를 제시한다. 비교 대상은 HEVC 구현 환경을 대상으로 MER의 크기를 병렬화 경우와 동일하게 설정한 부호화 시간이다. 실험환경은 표 1과 같다.
성능/효과
그림 3과 같은 구현을 위해서는 thread들이 공유하는 정보 영역에 lock과 관련한 정보와 ME의 수행 완료 여부를 판단할 수 있는 정보 공간이 추가로 할당되어야 한다. ME의 수행 여부를 읽고 쓰는 시간은 오버헤드로 작용하며 약간의 시간 증가를 야기하게 되는데 이상적인 병렬화 구현과 비교하여 1-5%의 시간증가가 발생하는 것을 실험을 통해 발견하였다.
64 %의 속도향상을 보였다. 가장 속도향상이 큰 경우는 양자화계수 27일 때 BQSquare 의 39.96 % 이었고 가장 적은 향상을 보인 경우는 양자화계수 32일 때 BasketballPass 의 10.18 % 이었다. Bit-rate의 경우 이미 MER을 사용한 코딩을 통해 발생하는 증가비율이 보고되어 있는데, 본 실험에서도 동일한 sequence에 대해 같은 증가 비율을 보이므로 시간측면에서의 복잡도 감소만을 결과로 제시한다.
본 실험에서 수행한 병렬화에 의해 전체 부호화 시간이 20 % 이상 감소하는 것으로 보아 제안한 방법을 바탕으로 안정화된 병렬화를 구현하여 평균 ME 시간을 감소시키는 것은 전체 부호화 과정의 시간 복잡도를 낮추기 위한 효과적인 방법임을 확인 할 수 있다.
본 실험에서는 PU레벨에서 병렬화를 설계함에 따라 4개의 PU로 이루어진 경우 모든 PU에 병렬화를 적용한다면 ME수행시간이 최대 75% 감소 될 것으로 직관적인 예측이 가능하다. 실험에서 도출된 평균 감소치인 25.
때문에 PU의 index가 0인 경우 PU의 정보영역에 접근할 실질적인 필요가 없기 때문에 index가 0인 PU를 할당 받은 thread의 경우 해당 함수의 호출과정을 생략하고 자체적으로 정보 값을 설정할 수 있도록 구현하는 것이 병렬화의 안정성 측면에서 우수한 구현에 유리하다. 실제 실험을 통해 Class D의 영상을 부호화하는 과정에서 처리되는 PU의 종류를 측정해본 결과 일부 시퀀스는 모든 PU의 index의 개수가 1개 혹은 2개로만 이루어졌음을 알 수 있었는데, 제안한 방법의 경우 index가 0인 경우의 함수 호출을 제한하기 때문에 대부분의 메모리 충돌문제를 해결할 수 있다.
본 실험에서는 PU레벨에서 병렬화를 설계함에 따라 4개의 PU로 이루어진 경우 모든 PU에 병렬화를 적용한다면 ME수행시간이 최대 75% 감소 될 것으로 직관적인 예측이 가능하다. 실험에서 도출된 평균 감소치인 25.64 % 은 Class D의sequence 영상들을 처리하는 과정의 PU가 대부분 부분 개수 1, 2인 경우로 구성되어 있다는 점을 반영하여 분석할 수 있다. 또한 전체 부호화 과정에서 ME를 제외한 다른 과정들은 병렬화가 되지 않았다는 것을 고려해야 한다.
또한 전체 부호화 과정에서 ME를 제외한 다른 과정들은 병렬화가 되지 않았다는 것을 고려해야 한다. 이 외에도 제안한 방법에서 사용된 locking 기법과 부분 병렬화로 1-5%의 오버헤드가 발생하는데, 이는 안정된 병렬화를 위해 병렬화 과정에서는 필수적으로 발생하는 오버헤드로 감안할 수 있다.
제안된 방법을 적용하여 각 thread를 제한적으로 병렬 구현을 하면 전체를 병렬화 한 경우와 비교하여 thread를 스케줄링하는 오버헤드와 제한된 부분에서의 지연시간이 추가로 발생하지만, 보다 안정된 병렬화를 구현할 수 있다. 이와 같은 병렬화 기법을 통해 안정된 병렬 ME를 구현함으로써 평균 부호화 시간을 25.64% 감소하는 효과가 있음을 실험하였다. 본 논문에서 제안한 구현기법은 안정성과 같은 장점을 바탕으로 향후 완벽히 독립적인 ME의 병렬화 구현을 위해 적용이 가능할 것으로 판단된다.
또한 메모리 동시 접근 발생을 방지하기 위한 방법으로 제한적인 thread의 변수 및 함수 호출을 제안했다. 제안된 방법을 적용하여 각 thread를 제한적으로 병렬 구현을 하면 전체를 병렬화 한 경우와 비교하여 thread를 스케줄링하는 오버헤드와 제한된 부분에서의 지연시간이 추가로 발생하지만, 보다 안정된 병렬화를 구현할 수 있다. 이와 같은 병렬화 기법을 통해 안정된 병렬 ME를 구현함으로써 평균 부호화 시간을 25.
제안한 병렬화 과정을 통해 부호기에서 ME를 병렬로 진행한 결과 병렬화하지 않은 경우에 비교하여 전체 부호화 시간 평균 25.64 %의 속도향상을 보였다. 가장 속도향상이 큰 경우는 양자화계수 27일 때 BQSquare 의 39.
후속연구
64% 감소하는 효과가 있음을 실험하였다. 본 논문에서 제안한 구현기법은 안정성과 같은 장점을 바탕으로 향후 완벽히 독립적인 ME의 병렬화 구현을 위해 적용이 가능할 것으로 판단된다.
질의응답
핵심어
질문
논문에서 추출한 답변
MVP list derivation 방법이 제안된 이유는?
이웃한 PU의 움직임정보가 ME과정을 통해 아직 처리되지 않은 경우 해당 Prediction Unit(PU)의 Merge/Skip 모드에 사용될 Motion Vector Prediction(MVP) 리스트 구성이 어려웠기 때문에, 상당수의 PU에서Merge/Skip 모드의 사용을 포기하는 형태로 병렬화를 구현하거나 병렬화 사이클 이후에 추가로 조작을 하는 형태로서 Merge/Skip 모드의 사용이 가능했다. Merge/Skip모드의 사용은 영상의 품질향상에 많은 기여를 하기 때문에, 이러한 문제를 해결하기 위해 Merge Estimation Region(MER) 을 이용한 MVP list derivation 방법이 제안되었다. MER의 설정으로 Merge Estimation 과정을 일반적인 ME과정에서 분리함으로써 움직임예측 과정에서 이웃한 PU의 움직임 정보 사용여부와 관계없이 독립적으로 Merge/Skip mode의 사용여부를 판단하는 것이 가능해졌다[4].
이전 AVC에는 없었던 Merge 모드에서 어떤 어려움이 있는가?
HEVC의 ME에서는 이전 AVC에는 없었던 Merge 모드를 사용하는데, 이를 병렬화에 완벽하게 적용하는 것에서 어려움이 제기되었다[4].이웃한 PU의 움직임정보가 ME과정을 통해 아직 처리되지 않은 경우 해당 Prediction Unit(PU)의 Merge/Skip 모드에 사용될 Motion Vector Prediction(MVP) 리스트 구성이 어려웠기 때문에, 상당수의 PU에서Merge/Skip 모드의 사용을 포기하는 형태로 병렬화를 구현하거나 병렬화 사이클 이후에 추가로 조작을 하는 형태로서 Merge/Skip 모드의 사용이 가능했다.
다수의 thread에서 CU레벨의 정보 영역을 혼잡스럽게 읽고 쓰는 과정이 발생하지 않도록 하기 위해 본 연구에서 제안한 것은?
첫째 병렬화의 문제로 제시된 정보의 일관성 문제를 해결하기 위해 다수의 thread에서 CU레벨의 정보 영역을 혼잡스럽게 읽고 쓰는 과정이 발생하지 않도록 조작이 필요하다. 이를 위해서는 동시에 여러 thread에서 최적 참조 대상 정보에 접근할 수 없도록 임계영역을 설정해야 하는데, 현재의 HM software에 구현된 inter prediction과정에서는 하나의 참조 후보에 대해 해당 후보가 최적 참조 대상인지 검사하는 과정이 ME에 포함되어 한 번에 이루어지기 때문에 임계영역을 설정하기에 용이하지 않다. 이에 효과적인 병렬화 구현을 지원하기 위해HM6.0을 바탕으로 그림2 의 (b)와 같이 움직임 예측과정 알고리즘을 수정할 것을 제안한다.
참고문헌 (6)
JCT-VC of ISO/IEC MPEG and ITU-T VCEG, "WD4: Working Draft 4 of High-Efficiency Video Coding," JCT-VC doc. JCTVC-F803, Torino, July 2011.
JCT-VC of ISO/IEC MPEG and ITU-T VCEG," Meeting report of the first meeting of the Joint Collaborative Team on Video Coding (JCT-VC)", JCT-VC doc. JCTVC-A200, Dresden, April, 2010
P. Atul, X. Chen, L. Ajay, "Video Coding Using the H.264/ MPEG-4 AVC Compression Standard. Elsevier Signal Processing : Image Communication", Signal processing, n. 19, p.793-849, 2004.
JCT-VC of ISO/IEC MPEG and ITU-T VCEG, "AHG10: Configurable and CU-group level parallel merge/skip," JCT-VC doc. JCTVC-H0082, San Jose, Feburary, 2012
JCT-VC of ISO/IEC MPEG and ITU-T VCEG, "HM6: High Efficiency Video Coding (HEVC) Test Model 6 Encoder Description," JCT-VC doc. JCTVC-H1002, San Jose, Feburary 2012
[Online] High Efficiency Video Coding Test Model software 6.0 available: https://hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.