[논문]후보 선별과 최적후보 안정성을 이용한 고속 움직임 예측 알고리즘

김종남

doi:10.5909/jbe.2018.23.5.628

후보 선별과 최적후보 안정성을 이용한 고속 움직임 예측 알고리즘
Fast Motion Estimation Algorithm using Selection of Candidates and Stability of Optimal Candidates 원문보기

방송공학회논문지 = Journal of broadcast engineering, v.23 no.5, 2018년, pp.628 - 635

초록
AI-Helper

본 논문에서는 비디오 부호화에서 중요한 고속 움직임 예측 알고리즘을 제안한다. 기존의 전영역 탐색 방법의 많은 계산량으로 인하여 예측화질향상과 연산량 감축을 위한 연구가 진행되어 왔으며, 본 논문에서는 전영역 탐색기반의 방법과 비교하여 예측화질은 거의 유지하면서 무의미한 계산량을 줄이는 방법을 제안한다. 제안하는 알고리즘은 각 후보 지점에 대하여 부분 블록 에러 합을 계산하고, 이에 따라 다음 단계에서 진행할 후보들을 선별하고, 최소 에러지점의 최적후보에 대해 단계별 안정성을 비교 판단하여 그 다음 단계의 진행 여부를 결정함으로써 최적의 움직임 벡터를 계산한다. 이를 통하여 전체의 최소블록매칭에러를 갖는 지점을 조기에 발견하고, 불필요한 후보들을 더 빨리 제거함으로써 불필요한 계산량을 줄이고 계산속도 향상을 얻을 수 있다. 또한 제안하는 알고리즘은 단독으로 사용할 뿐만 아니라 기존의 고속 알고리즘들과 결합하여 사용해도 예측화질은 거의 유지하면서 계산량을 대폭 줄일 수 있으며, 실험결과에서 이를 검증한다.

Abstract ▼ AI-Helper

In this paper, we propose a fast motion estimation algorithm which is important in video encoding. So many fast motion estimation algorithms have been published for improving prediction quality and computational reduction. In the paper, we propose an algorithm that reduces unnecessary computation, while almost keeping prediction quality compared with the full search algorithm. The proposed algorithm calculates the sum of partial block matching error for each candidate, selects the candidates for the next step, compares the stability of optimal candidates with minimum error, and finds optimal motion vectors by determining the progress of the next step. By doing that, we can find the minimum error point as soon as possible and obtain fast computational speed by reducing unnecessary computations. Additionally, the proposed algorithm can be used with conventional fast motion estimation algorithms and prove it in the experimental results.

주제어

표/그림 (4)

그림 그림 1. 제안 알고리즘의 절차 Fig. 1. Procedure of the proposed algorithm
표 표 1. 알고리즘별 계산량(단위: 행) Table 1. Computational amount of each algorithm for sequences (Unit:rows)
표 표 2. 알고리즘별 상대적 계산 시간 비율 (단위: %) Table 2. Rate of Computational time of each algorithm for sequences (Unit: %)
표 표 3. 알고리즘별 예측화질(단위: dB) Table 3. Prediction quality of each algorithm for sequences (Unit: dB)

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 예측화질이 전영역 탐색방법과 거의 또는 완전히 동일하면서 계산량을 현저히 줄이는 고속 움직임 예측 방법을 제안한다. 제안하는 방법은 위에서 언급한 PDE 방법을 기반으로 하며, 무의미한 탐색 후보지점을 조기에 제거하면서 움직임벡터를 더 일찍 계산하도록 한다.
본 논문에서는 움직임 예측에서 전영역 탐색방법에 비하여 예측화질의 저하가 전혀 없거나 거의 없으면서 소요되는 계산량을 현저히 줄이는 방법을 제안하였다. 본 논문에서 제안한 방법은 탐색 영역의 후보지점 중에서 단계별 최소 에러를 갖는 최적의 후보를 찾고, 이를 통하여 얻는 최소의 블록매칭에러를 계산하고 단계별 부분블록매칭에러의 크기에 따라 다음 단계에서 우선 순위를 갖는 후보를 걸러내며, 단계별 부분블록매칭에러 지점이 변치 않는 횟수를 조사하여 그에 따라 최종 움직임벡터를 결정함으로써 불필요한 계산량을 현저히 줄일 수 있게 하였다.
본 논문에서는 탐색 영역전체에 대하여 부분블록에러의 합을 단계적으로 계산한다. 단계적으로 블록에러의 합을 계산하는 것은 그 블록의 행이나, 열, 또는 작은 서브 블록 별로 계산을 하는 것을 의미하며, 유효한 탐색 후보지점에 대해 작은 단위의 매칭 에러합을 계산한다.

제안 방법

CDMHS와 ARTZS방법을 제외한 나머지 방법들은 무손실 움직임 예측 방법으로서 기존의 전영역 탐색방법과 비교하여 예측화질의 저하가 전혀 없으며, 계산량만 줄이는 방법들이다. CDMHS와 ARTZS방법은 본 논문에서 제안하는 방법이 기존의 고속 움직임 방법들과 연동하여 사용가능하며, 예측화질 대비 계산량을 줄이는 방법임을 보이기 위하여 실험방법에 포함시켰다.
본 논문에서 제안하는 방법은 기존의 블록매칭에러값이 큰 영역을 유추하는 것이 아니라 단계별로 최소에러를 갖는 최적의 후보지점을 추가적인 계산 없이 가능한 일찍 찾아내어 불가능한 후보 벡터를 더 빨리 제거한다. 탐색영역내에 존재하는 최소의 블록 에러 지점을 더 빨리 찾기 위하여 부분블록에러합의 결과와 적절한 조건을 이용하여 최적의 후보를 대상으로 전체 블록에러를 계산함으로써 탐색영역내의 최소에러 지점을 더 빨리 계산한다.
본 논문에서 제안하는 방법은 무손실 예측 방법과 거의 동일한 예측화질을 추구하며, 계산량은 대폭 줄이도록 하였다. 각 방법들의 비교기준이 되는 무손실 움직임 예측 방법으로는 전영역 알고리즘 (FS)이 있으며, 고속의 무손실 움직임 예측방법으로는 PDE 알고리즘 (PDE) ^[11], Hadamard 변환을 이용한 고속 PDE 방법 (PDE HD)^[12], MSEA(Multilevel Successive Elimination Algorithm)^[9], CDMHS(Cross-Diamond Modified Hierarchical Search)^[6], ARTZS(Angle Restricted Test Zone Search)^[8]등이 있다.
표 2는 전영역 탐색 방법의 계산시간을 100%로 볼때 각 방법별 계산시간을 비율로 나타내었다. 본 논문에서 제안하는 알고리즘은 TH_t값에 따라 예측화질의 저하가 발생하기도 하며, TH_t값이 16일 경우는 전영역 탐색 방법과 비교하여 예측화질 저하가 없는 무손실 예측화질 방법이 된다.
본 논문에서는 움직임 예측에서 전영역 탐색방법에 비하여 예측화질의 저하가 전혀 없거나 거의 없으면서 소요되는 계산량을 현저히 줄이는 방법을 제안하였다. 본 논문에서 제안한 방법은 탐색 영역의 후보지점 중에서 단계별 최소 에러를 갖는 최적의 후보를 찾고, 이를 통하여 얻는 최소의 블록매칭에러를 계산하고 단계별 부분블록매칭에러의 크기에 따라 다음 단계에서 우선 순위를 갖는 후보를 걸러내며, 단계별 부분블록매칭에러 지점이 변치 않는 횟수를 조사하여 그에 따라 최종 움직임벡터를 결정함으로써 불필요한 계산량을 현저히 줄일 수 있게 하였다. 본 논문의 제안방법은 전영역 탐색 알고리즘과 비교하여 예측 화질의 저하가 전혀 없이 계산량을 최고 75%를 줄였으며, 미미한 화질저하를 감수한다면 더 많은 계산량을 줄일 수 있었다.
제안하는 방법은 위에서 언급한 PDE 방법을 기반으로 하며, 무의미한 탐색 후보지점을 조기에 제거하면서 움직임벡터를 더 일찍 계산하도록 한다. 이는 탐색 절차를 몇 단계로 나누는데, 먼저 탐색 영역내의 각 후보 지점에 대하여 부분 블록 에러 합을 계산하고, 이에 따라 다음 단계에서 진행할 후보들을 선별하고, 최소 에러지점의 최적후보에 대해 단계별 안정성을 비교 판단하여 그 다음 단계의 진행 여부를 결정함으로써 최적의 움직임 벡터를 계산한다. 다음 단계에서 진행할 후보들을 선별할 때 그때까지 계산한 부분 블록 에러 합을 이용하여 적절한 문턱치를 설정하고 이보다 작은 값을 갖는 후보에 대해서만 우선적으로 다음단계에서 탐색을 계속하고, 나머지는 모든 단계를 마친 후에 처리하는데, 이를 통하여 최적 움직임 벡터로서 가능성이 높은 후보에 대해 먼저 검사함으로써 추후에 불필요한 계산을 더 많이 줄일 수 있는 것이다.
본 논문에서는 예측화질이 전영역 탐색방법과 거의 또는 완전히 동일하면서 계산량을 현저히 줄이는 고속 움직임 예측 방법을 제안한다. 제안하는 방법은 위에서 언급한 PDE 방법을 기반으로 하며, 무의미한 탐색 후보지점을 조기에 제거하면서 움직임벡터를 더 일찍 계산하도록 한다. 이는 탐색 절차를 몇 단계로 나누는데, 먼저 탐색 영역내의 각 후보 지점에 대하여 부분 블록 에러 합을 계산하고, 이에 따라 다음 단계에서 진행할 후보들을 선별하고, 최소 에러지점의 최적후보에 대해 단계별 안정성을 비교 판단하여 그 다음 단계의 진행 여부를 결정함으로써 최적의 움직임 벡터를 계산한다.
본 논문에서 제안하는 방법은 기존의 블록매칭에러값이 큰 영역을 유추하는 것이 아니라 단계별로 최소에러를 갖는 최적의 후보지점을 추가적인 계산 없이 가능한 일찍 찾아내어 불가능한 후보 벡터를 더 빨리 제거한다. 탐색영역내에 존재하는 최소의 블록 에러 지점을 더 빨리 찾기 위하여 부분블록에러합의 결과와 적절한 조건을 이용하여 최적의 후보를 대상으로 전체 블록에러를 계산함으로써 탐색영역내의 최소에러 지점을 더 빨리 계산한다. 기존의 전영역 탐색 및 PDE, 그리고 PDE 변경 알고리즘들은 각 후보지점에 대하여 전체의 블록에러합을 계산을 한 후 다음 후보지 지점으로 이동하여 블록 에러합을 계산하는 구조를 가지고있다.

대상 데이터

제안 알고리즘의 객관적인 성능 평가를 위해, 720×480화소를 가진 “bus”, “bally”, “bicycle”, “flower garden”,“football”과 1920×1080 화소를 가진 “cactus”, 4096×2160 화소를 가진 “people on street”의 비디오 데이터를 이용하여 실험을 수행하였다.

데이터처리

움직임 벡터를 계산하는 매칭 블록의 크기는 16×16화소이며, 탐색영역의 범위는 ±15 화소, 비디오 프레임수는 95이다. 알고리즘의 성능평가를 위한 실험 결과는 움직임 벡터 계산을 위해 사용된 평균 계산량과 전영역 탐색방법에서의 계산시간과 각 방법별 계산시간의 비, 그리고 움직임 벡터의 정확도와 예측화질 평가를 위하여 PSNR(Peak Signal to Noise Ratio)로 나타내었다. 각 방법에 대한 계산량은 16×16 화소의 매칭블록의 크기에서 계산을 위해 사용된 행의 수로써 나타내었다.

성능/효과

264, Complex PDE, PDE HD, Proposed TH_t=16의 방법들은 화질저하가 FS방법에 비하여 없으며, 나머지는 손실이 발생함을 알 수 있다. CDMHS방법과 ARTZS방법은 연산량 감소는 많으나 무손실 방법에 비하여 예측화질 저하가 현저히 발생하며, CDMHS+Proposed TH_t=8 방법과 ARTZS+Proposed TH_t=8 방법은CDMHS와 비교하여 예측화질저하가 극히 미미함을 알 수 있으며, 무손실 방법들과 Proposed TH_t=4,8 방법들을 비교해 보면 예측화질의 저하가 미미함을 알 수 있다.
본 논문의 제안방법은 전영역 탐색 알고리즘과 비교하여 예측 화질의 저하가 전혀 없이 계산량을 최고 75%를 줄였으며, 미미한 화질저하를 감수한다면 더 많은 계산량을 줄일 수 있었다. 또한 다른 손실 예측 방법들과 결함하여 사용시 더욱 많은 계산량을 줄일 수 있으며, 결합된 기존의 방법들과 비교할때 예측화질저하는 미미함을 알 수 있었다. 제안한 알고리즘은 MPEG-4 AVC 및 HEVC에서 사용이 가능하며, 이를 이용하는 실시간 비디오 압축 응용분야에 유용하게 사용될 수 있을 것이다.
FS방법의 결과와 비교해 볼 때, 다른 고속의 무손실 예측방법들은 많은 연산량 감소가 있음을 알 수 있으며, 무손실 방법 중에서 제안 방법의 연산량 감소가 가장 많음을 알 수 있다. 또한 제안하는 방법의 TH_t값에 대해 연산량 대비 예측화질의 성능이 우수함을 알 수 있다. 표 1에서 CDMHS은 손실방법의 하나인데, 다른 방법에 비하여연산량 감소가 많음을 알 수 있으며, 이의 방법과 제안방법이 결합된 결과는 연산량 감소가 더욱 많음을 알 수 있다.
제안하는 방법은 각 단계에서 최적후보가 변경되지 않는 수를 조절하여 손실 예측 화질과 무손실 예측 화질을 쉽게 설정할 수 있는 장점을 가진다. 또한 제안하는 알고리즘은 기존의 손실 움직임 예측 방법들과 결합하여 사용할 때 추가적인 계산을 하지 않기 때문에 이들 방법들과 결함하여 사용할 때, 예측화질 대비 많은 계산량 감소를 얻을 수 있다.
본 논문에서 제안하는 알고리즘은 예측화질에 있어서는 전영역 탐색방법의 결과와 거의 동일하면서 계산량을 효율적으로 감축하는 것이다. 전술한 대로, 전영역 탐색방법과 비교하여 예측화질의 손실이 발생하지 않으면서 계산량을 줄일 수 있는 방법으로 SEA와 PDE방법이 있다.
본 논문에서 제안한 방법은 탐색 영역의 후보지점 중에서 단계별 최소 에러를 갖는 최적의 후보를 찾고, 이를 통하여 얻는 최소의 블록매칭에러를 계산하고 단계별 부분블록매칭에러의 크기에 따라 다음 단계에서 우선 순위를 갖는 후보를 걸러내며, 단계별 부분블록매칭에러 지점이 변치 않는 횟수를 조사하여 그에 따라 최종 움직임벡터를 결정함으로써 불필요한 계산량을 현저히 줄일 수 있게 하였다. 본 논문의 제안방법은 전영역 탐색 알고리즘과 비교하여 예측 화질의 저하가 전혀 없이 계산량을 최고 75%를 줄였으며, 미미한 화질저하를 감수한다면 더 많은 계산량을 줄일 수 있었다. 또한 다른 손실 예측 방법들과 결함하여 사용시 더욱 많은 계산량을 줄일 수 있으며, 결합된 기존의 방법들과 비교할때 예측화질저하는 미미함을 알 수 있었다.
이는 예측 화질의 손실을 초래할 수 있는데, 변경되지 않은 단계의 수를 조절함으로써 예측화질을 제어할 수 있다. 제안하는 방법은 각 단계에서 최적후보가 변경되지 않는 수를 조절하여 손실 예측 화질과 무손실 예측 화질을 쉽게 설정할 수 있는 장점을 가진다. 또한 제안하는 알고리즘은 기존의 손실 움직임 예측 방법들과 결합하여 사용할 때 추가적인 계산을 하지 않기 때문에 이들 방법들과 결함하여 사용할 때, 예측화질 대비 많은 계산량 감소를 얻을 수 있다.
또한 제안하는 방법의 TH_t값에 대해 연산량 대비 예측화질의 성능이 우수함을 알 수 있다. 표 1에서 CDMHS은 손실방법의 하나인데, 다른 방법에 비하여연산량 감소가 많음을 알 수 있으며, 이의 방법과 제안방법이 결합된 결과는 연산량 감소가 더욱 많음을 알 수 있다.

후속연구

또한 다른 손실 예측 방법들과 결함하여 사용시 더욱 많은 계산량을 줄일 수 있으며, 결합된 기존의 방법들과 비교할때 예측화질저하는 미미함을 알 수 있었다. 제안한 알고리즘은 MPEG-4 AVC 및 HEVC에서 사용이 가능하며, 이를 이용하는 실시간 비디오 압축 응용분야에 유용하게 사용될 수 있을 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	비디오 압축에서 움직임 예측 모듈은 무엇인가?	비디오 압축에서 움직임 예측 모듈은 비디오 데이터의 몇 가지 중복성 중에 시간적 중복성을 줄이는 기술이며, 이를 통하여 정지영상 압축보다 현저히 높은 압축률을 얻을 수 있다. 이러한 움직임 예측은 연속되는 비디오 프레임간의 유사한 영역을 찾는 것이며, 이웃하는 프레임에서 유사한 영역의 이동 변위를 움직임 벡터로 정의한다.
	블록 기반의 움직임 예측 알고리즘들 중 손실 움직임 예측 방법의 종류에는 무엇이 있는가?	본 논문에서는 전자를 손실 움직임예측이라 정의하고, 후자를 무손실 움직임예측이라 정의한다. 손실 움직임 예측 방법은 화질저하를 감수하면서 계산량을 대량으로 감축하는 방식인데, 단일모달 에러 표면 가정기법(unimodal error surface assumption), 피라미드 계층적탐색 기법, 비트 해상도 조절 기법, 가변탐색영역 기법, 중간 멈춤기법, 단순화된 에러 비교 방법 등을 포함한다[2-8]. 반면에 무손실 움직임 예측 방법은 예측화질의 저하 없이 계산량만 줄이는 방법인데, 계산량의 감소가 이전의 손실 움직임 예측방법보다 현저히 떨어진다.
	블록 매칭 움직임 예측 방법 중 전영역 탐색 방법의 장점과 단점은 무엇인가?	블록 매칭 움직임 예측 방법들에서 가장 기본적인 방법이 전영역 탐색 (full search)방법인데, 이는 설정된 탐색 영역에서 모든 탐색 후보점에 대하여 블록매칭 에러 (block matching error)를 계산하고 그 중에 최소의 에러를 갖는 후보 탐색지점을 찾는 것이다. 이 방법은 예측화질과 구현복잡도 측면에서는 우수하나, 계산량이 많으며, 특히 탐색 영역이 커진다면 계산량이 심각한 문제가 되기도 한다. 이를 해결하기 위해 고속 움임임 예측에 대한 많은 연구가 수행되어 왔다[1].

참고문헌 (12)

T. Tan, R. Weerakkody, and G. Sullivan, "Video quality evaluation methodology and verification testing of HEVC compression performance," IEEE Transactions on Circuits System & Video Technology, Vol. 26, No. 1, pp. 76-90, 2016.

상세보기
T. Lee, Y. Chan, and W. Siu, "Adaptive search range by neighbouring depth intensity weighted sum for HEVC texture coding," IEE Electron. Letters, Vol. 52 No. 12, pp. 1018-1020, 2016.

상세보기
H. Choi, J. Kim, S. Jung, "Fast Motion Estimation Algorithm using Importance of Search Range and Adaptive Matching Criterion," The Journal of Korea Institute of Signal Processing and Systems, Vol. 16, No. 4, pp. 129-133, 2015.
Z. Pan, j. Lei, Y. Zhang, X. Sun, and S. Kwong, "Fast motion estimation based on content property for low-complexity H.265/HEVC encoder," IEEE Transactions on Broadcasting, Vol. 63, No. 3, pp. 675-684, 2016.
P. Bhalge and S. Amdani, "Modified hexagonal search for motion estimation", Proceeding of International Conference on Intelligent Compuuting and Control Systems, pp. 94-96, 2017.
N. Alnajdawi, M , Alnajdawi, and S. Tedmori, "Employing a novel cross-diamond search in a modified hierarchical search motion estimation algorithm for video compression," Elsevier Information Sciences, Vol. 268, pp. 425-435, 2014.

상세보기
A. Paramkusam, "Efficient motion estimation algorithm on the layers," IEE Electron. Letters, pp. 467-468, 2017.
N. Vayalil, M. Paul, and Y. Kong, " A novel angle-restricted test zone search algorithm for performance improvement of HEVC", Proceeding of IEEE International Conference on Image Processing, pp. 6-10, 2017.
X.Q. Gao, C.J. Duanmu, and C.R. Zou, "A Multilevel Successive Elimination Algorithm for Block Matching Motion Estimation," IEEE Transactions on Image Processing, Vol. 9, No. 3, pp. 501-504, 2000.

상세보기
J. Kim, S. Byun, Y. Kim, and B. Ahn, "Fast Full Search Motion Estimation Algorithm Using Early Detection of Impossible Candidate Vectors," IEEE Transactions on Signal Processing, Vol. 50, No. 9, pp. 2355-2365, 2002.

상세보기
H.264/AVC reference software, http://iphome.hhi.de/suehring/tml/download/old_jm/
S. Jin and H. Lee, "Fast Partial Distortion Elimination Algorithm based on Hadamard Probability Model," IEE Electron. Letters, Vol. 44, No. 1, pp. 17-19, 2008.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증